|Version 7 (modified by 9 years ago) (diff),|
The Register Allocator
The register allocator is responsible for assigning real/hardware regs (hregs) to each of the virtual regs (vregs) present in the code emitted by the native code generator. It also inserts spill/reload instructions to save vregs to the stack in situations where not enough hregs are available.
GHC currently provides three register allocation algorithms, one which does simple lineear scan and two version of graph coloring. Support for linear scan is likely to be removed in a subequent version.
- Linear scan
The linear allocator is turned on by default. This is what you get when you compile with
-fasm. The linear allocator does a single pass through the code, allocating registers on a first-come-first-served basis. It is quick, and does a reasonable job for code with little register pressure.
This algorithm has no look-ahead. If say, a particular hreg will be clobbered by a function call, it does not know to avoid allocating to it in the code before the call, and subsequently inserts more spill/reload instructions than strictly needed.
- Graph coloring (enabled with
The graph coloring algorithm operates on the code for a whole function at a time. From each function it extracts a register conflict graph which has a node for every vreg and an edge between two vregs if they are in use at the same time and thus cannot share the same hreg. The algorithm tries to assign hregs (represented as colors) to the nodes so that no two adjacent nodes share the same color, if it can't then it inserts spill code, rebuilds the graph and tries again.
Graph coloring tends to do better than the linear allocator because the conflict graph helps it avoid the look-ahead problem. The coloring allocator also tries harder to allocate the source and destination of reg-to-reg move instructions to the same hreg. This is done by coalescing (merging) move-related nodes. If this succeeds then the moves can be erased.
- Graph coloring with iterative coalescing (enabled with
Iterative coalescing is an improvement over regular graph coloring whereby coalescing passes are interleaved with coloring passes. Iterative coalescing does a better job than regular graph coloring, but is slower because it must alternate between the coloring and coalescing of nodes.
For an outline of the code see Commentary/Compiler/Backends/NCG/RegisterAllocator/Code
If you decide to do some hacking on the register allocator then take a look at (at least) these papers first:
Iterated Register Coalescing
George, Appel, 1996
Decribes the core graph coloring algorithm used.
A Generalised Algorithm for Graph-Coloring Register Allocation
Smith, Ramsey, Holloway, 2004
For a decription of how to deal with overlapping register sets, which aren't fully implemented yet. Explains what the
triv functions are for.
Design and Implementation of a Graph Coloring Register Allocator for GCC
For an overview of techniques for inserting spill code.
Breaking the allocator can result in compiled programs crashing randomly (if you're lucky) or producing the wrong output.
When working on the allocator, make sure to always turn on
-fasm-lint. Doing this makes the allocator call
GraphOps.validateGraph after every spill/color stage.
validateGraph checks that all the edges point to valid nodes, that no conflicting nodes have the same color, and if the graph is supposed to be colored then all nodes are really colored.
The main dump flags are
Shows the code and conflict graph after ever spill/color stage. Also shows spill costs, and what registers were coalesced.
Gives statistics about how many spills/reloads/reg-reg-moves are in the output program.
Gives the final output code.
Diverts dump outputs to files. This can be used to get dumps from each module in a nofib benchmark.
make EXTRA_HC_OPTS="-O2 -fregs-iterative -ddump-to-file -ddump-asm-regalloc-stages"
- work lists
- spill code
- spill candidates
- aliasing register sets
- checkSpills.report (49.1 KB) - added by 9 years ago.
checkSpills.tests (1.5 KB) - added by 9 years ago.
list of working nofib benchmarks to run with checkSpills.hs
checkSpills.hs (10.2 KB) - added by 9 years ago.
script to help test allocator performance over nofib suite
graph-colored.png (195.5 KB) - added by 9 years ago.
example colored register conflict graph
graph.png (81.5 KB) - added by 9 years ago.
example colored register conflict graph
graph.dot (4.4 KB) - added by 9 years ago.
graphviz source for graph.png
graph-colored.dot (3.6 KB) - added by 9 years ago.
graphviz source for graph-colored.png
Download all attachments as: .zip