Version 5 (modified by guest, 10 years ago) (diff)

add references

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 two register allocation algorithms, simple linear scan and graph coloring. Although some of the code is shared between the two, as we only want to maintain a single algorithm, support for linear scan will be removed in a subsequent version.

In the meantime, there are three options for register allocation:

  • Linear scan
    The linear allocator is currently 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. It has no look-ahead. If say, a particular register will be clobbered by a function call, it does not know to avoid allocating to that register in the code before the call and subsequently inserts more spill/reload instructions than the other algorithms.
  • Graph coloring (enabled with -fregs-graph)
    The graph coloring algorithm operates on the code for a whole function at a time. From each function it extracts a register conflict graph. The conflict graph has a node for every vreg in the code and an edge between two vregs if they are in use at the same time and thus cannot share the same hreg. It 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. This algorithm tends to do better than the linear allocator because the conflict graph helps it avoid the look-ahead problem. The coloring allocator also tries to allocate the source and destination of register-to-register move instruction to the same hreg. This is done by coalescing (merging) move-related nodes. If this succeeds then the move instruction can be erased.
  • Graph coloring with iterative coalescing (enabled with -fregs-iterative)
    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.

Code map


If you decide to do some hacking on the register allocator, I would 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 worst, squeese and trivfunctions are for.

Design and Implementation of a Graph Coloring Register Allocator for GCC
Matz, 2003
For an overview of techniques for inserting spill code.

Attachments (7)

Download all attachments as: .zip