Register Allocation: Graph Coloring, Linear Scan, and Spilling

Compilers Compilers 8 min read 1503 words Beginner ExcellentWiki Editorial Team

Register allocation is the compiler backend phase that maps the unlimited set of virtual registers used during intermediate code generation onto the finite set of physical registers available on the target processor. It is one of the most critical optimization stages — effective register allocation minimizes the number of load and store instructions (spills), which directly impacts execution speed. Poor allocation can double or triple the number of memory accesses in a function, negating gains from earlier optimization passes. This article covers the two dominant algorithms — graph coloring and linear scan — along with live range analysis, spill cost heuristics, and allocation for irregular register architectures.

The Register Allocation Problem

A typical RISC processor has 16 to 32 general-purpose registers. A modern compiler may generate code with hundreds of virtual registers that must be mapped to physical registers or spilled to memory. The allocation must satisfy two constraints:

Correctness — two values with overlapping live ranges cannot occupy the same physical register
Efficiency — the most frequently accessed values should be in registers, while infrequently accessed values are spilled

Live range analysis determines where each value is defined (defined) and used. A live range starts at the definition point and ends at the last use point. Two values interfere (their live ranges overlap) if one is live at the point where the other is defined.

Graph Coloring Register Allocation

Graph coloring is the classical register allocation algorithm, first described by Chaitin et al. in 1981 and refined by Briggs, Cooper, and Torczon in the 1990s. It models the allocation as a graph coloring problem.

Building the Interference Graph

Each virtual register becomes a node in the interference graph. An edge connects two nodes if their live ranges overlap. The graph is built by iterating over each instruction and adding interference edges between the instruction’s destination register and all registers live at that point (except the destination itself).

For a function with N virtual registers, the interference graph has N nodes. Dense graphs can have O(N²) edges. Optimizations use data structures like Briggs’ bit-matrix representation to manage the graph efficiently.

The Chaitin Algorithm

Chaitin’s original algorithm allocates registers in several phases:

Build — construct the interference graph and coalesce register-to-register copies (if x = y and x and y do not interfere, they can be assigned the same register)
Simplify — repeatedly remove any node with fewer than K neighbors (where K is the number of available registers), pushing it onto a stack. These nodes are trivially colorable
Spill — if no node has fewer than K neighbors, select a node to spill (store to memory). The spill candidate is chosen based on a cost heuristic
Select — pop nodes from the stack and assign colors (physical registers). If a node’s neighbors already use all K colors, the node is spilled
Rewrite — insert spill code (store and load instructions) for spilled values and re-run the allocator

Optimistic Coloring (Briggs)

Briggs improved Chaitin’s algorithm with optimistic coloring. In Chaitin’s original algorithm, a node was spilled immediately if it had K or more neighbors during simplify. Briggs’ insight: a high-degree node might still be colorable if its neighbors do not use all K distinct colors. Briggs’ algorithm attempts to color all nodes during the select phase; only nodes that actually cannot be colored are spilled.

This change significantly reduces spilling for realistic interference graphs. Most production graph coloring allocators (including GCC’s older allocator) use the Briggs variant.

Rematerialization

Some values are cheaper to recompute than to load from memory. Rematerialization identifies values that can be recomputed from constants or from values that are always available. For example, if a virtual register holds a constant like 42, spilling and reloading is wasteful — the allocator can instead re-materialize the constant at the use point. Rematerialization was formalized by Briggs and is implemented in both GCC and LLVM.

Linear Scan Register Allocation

Linear scan is a faster, simpler alternative to graph coloring, designed for just-in-time compilers where compilation speed matters more than allocation quality.

The Linear Scan Algorithm

Linear scan operates on a linear ordering of the basic blocks (typically a depth-first traversal or a near-topological order). It considers the live intervals of each virtual register — the range of instruction indices where the value is live.

sort live intervals by start point
active = []
for each interval i in order:
    expire old intervals from active
    if len(active) < K:
        allocate i to a free physical register
        add i to active
    else:
        spill the interval with the furthest end point
        if i.end > spilled.end:
            allocate i to spilled's register
            add i to active, retire spilled
        else:
            mark i as spilled

The algorithm scans live intervals in linear time (O(N log N) for sorting the intervals, O(N) for the main loop). It is significantly faster than graph coloring, which requires building and traversing the interference graph.

Quality Tradeoffs

Linear scan produces allocations that are typically 10-20% worse than graph coloring on benchmark suites. However, for JIT compilers (Java HotSpot C1, V8 TurboFan baseline), this tradeoff is acceptable because the compilation speed is critical. LLVM’s early allocator used linear scan; the current allocator uses a more advanced global algorithm (Greedy Register Allocator) that combines linear scan with live range splitting.

Spill Code Generation

When a value cannot be allocated to a register, the compiler generates spill code:

Store — at the value’s definition point, save it to a stack slot
Load — at each use point, reload it from the stack slot

Spill code is inserted during the rewrite phase of graph coloring or during allocation in linear scan. The spill location is a fixed offset from the stack pointer or frame pointer. The allocator attempts to minimize spill costs by:

Spilling values that are used infrequently (low reference count)
Spilling values that are defined far from their uses (short live ranges cost less to spill)
Spilling values in inner loops only as a last resort (spills inside loops are executed many times)

Register Allocation in Production Compilers

LLVM’s Greedy Register Allocator

LLVM’s default allocator combines the speed of linear scan with the quality of graph coloring. Key features:

Live range splitting — intervals can be split at any point; each split interval can be in a different physical register or spilled. This allows partial spilling — only the hot parts of a live range stay in registers
Region splitting — live ranges are split at basic block boundaries, producing intervals that the allocator can place in different registers per block
Eviction — the allocator can evict a previously allocated interval if the new interval is more important (hotter)

GCC’s Register Allocator

GCC uses IRA (Integrated Register Allocator), a global allocator that works on the RTL representation. IRA performs register class allocation and then delegates to LRA (Local Register Allocator) for final allocation within each class. LRA handles:

Register elimination (removing frame pointer references)
Hard register conflicts (e.g., call-clobbered registers)
Target-specific constraints (e.g., x86’s byte-register restrictions)

FAQ

What is the difference between global and local register allocation? Local allocation operates within a single basic block. Global allocation considers the entire function. Global allocation uses live range analysis across blocks and is significantly more effective.

How many physical registers are typically available? x86-64 has 16 general-purpose registers (with some reserved: stack pointer, frame pointer). ARM64 has 31. GPUs have hundreds. The number of allocatable registers is always less than the total due to reserved registers (stack pointer, thread-local storage, etc.).

What does “spill” mean? Spilling means moving a value from a register to memory (a stack slot) because there are not enough registers to hold all live values simultaneously. The spilled value is reloaded when it is next needed.

Can register allocation be perfect? Optimal register allocation is NP-complete (it reduces to graph coloring, which is NP-complete for arbitrary graphs). However, the interference graphs that arise from real programs have special structure that makes near-optimal allocation tractable.

How do compilers handle register allocation for irregular register files? x86 has many register constraints: byte operations must use AL/BL/CL/DL, shifts must use CL, and some instructions use fixed registers (EAX for divide, RDX:RAX for multiply). Modern allocators handle this through register class hierarchies — the allocator first assigns to the most constrained class (e.g., byte-addressable registers), then uses copy constraints to move values between classes. LLVM’s allocator models these constraints through register classes and allocation orders defined in TableGen.

What is register aliasing? On some architectures, registers overlap. x87 ST(0)–ST(7) and the x86 MMX registers share the same physical storage. Writing to an MMX register corrupts the corresponding x87 register. The register allocator must use aliasing information to prevent assigning overlapping registers to live values simultaneously. LLVM’s MCRegisterInfo provides alias analysis through register tuples.