15 min read #compilers #Optimization

On this page

Register Allocation

The stage in compiler optimization that best demonstrates NP-hardness: mapping infinite virtual registers to a finite number of physical registers, and spilling to the stack when they do not fit. Graph coloring (Chaitin/Briggs) and linear scanning (Poletto/Sarkar) are two approximate solutions; the chordal graph property of SSA makes coloring easier.

Overview

The SSA form and optimization phases use infinite virtual registers—each new value gets its own %v1, %v2. The actual target machine has only a small number of physical registers (x86-64 has 16 general-purpose registers, ARM64 has 31) and is constrained by the calling convention. Register allocation is the process of mapping virtual registers to physical registers—when they don't fit, they spill to the stack. This is the part of compiler optimization that most clearly demonstrates NP-hardness—optimal register allocation is NP-complete (equivalent to graph coloring), so approximate algorithms are used in practice.

Prerequisite: Liveness Analysis

Liveness from data flow analysis directly provides input for register allocation:

For two virtual registers v1 and v2:
  If there exists a program point where v1 and v2 are both live
    → v1 and v2 cannot share the same physical register
    → There is an edge between v1 and v2 in the interference graph

Construction of live ranges: Starting from each definition point, follow the SSA def-use chain to all use points; the "segments" between them constitute the live range of that virtual register. If there are phi merges, connect the live ranges of the phi sources and targets.

Graph Coloring Allocation (Chaitin/Briggs)

Constructing the Interference Graph

Nodes = virtual registers; Edges = two virtual registers are simultaneously live at any point:

v1 is defined in BB1, last used in BB3
v2 is defined in BB2, last used in BB3
At the entry of BB3, both v1 and v2 are live → there is an edge v1 — v2

Coloring = Assigning a color (physical register) to each node, such that adjacent nodes have different colors

Algorithm (Chaitin-style):

while there are still nodes in the graph:
    if there exists a node n with degree(n) < K (K = number of available physical registers):
        Remove n from the graph and push n onto the stack       ← n can definitely be colored (adjacent nodes < K)
    else:
        Select node s with the lowest spill cost
        Mark s as spilled, remove it from the graph             ← Sacrifice it, place it on the stack
        Call spill_code(s): Generate store/load instructions to move s's value to the stack

Pop nodes from the stack one by one, assigning a color to each (ensuring no conflict with already-colored adjacent nodes)

Briggs' Improvement: Do not immediately conclude that nodes with degree < K are colorable—optimistically remove them first. If, during the pop phase, a node cannot be colored, then perform a spill. Briggs' optimistic coloring produces significantly fewer spills in practice than Chaitin's pessimistic algorithm (Chaitin actively spills all nodes with degree ≥ K, many of which could have been colored).

Spill Code Generation

When registers are insufficient, "spill" the value of a virtual register to the stack:

Before spill:                     After spill:
  v1 = ...                         v1 = ...
  ... = v1 (use)                   spill [v1_slot] = v1        ← Store immediately after definition
                                    v1_reload = load [v1_slot]  ← Load before use
                                    ... = v1_reload

However, spilling changes the live range—originally, v1 was only used at ... = v1, but spilling splits its live range into two segments (v1 and v1_reload), potentially making the interference graph sparser and thus alleviating coloring pressure. Rebuild the interference graph and re-allocate after spilling—this is an iterative process.

Linear Scanning (Poletto/Sarkar): Faster but More Spills

Linear scanning uses a simplified liveness model: instead of point-precise interference graphs, it relies on the linear order of live intervals:

Sort all virtual register live intervals by start position:
  Maintain a "currently active" list
  Scan each interval:
    expire_old_intervals()  ← Remove ended intervals, freeing their physical registers
    if there is a free register:
        Allocate it
    else:
        Select the currently active interval with the lowest spill cost, spill it
        Allocate the freed register to the new interval

The complexity of linear scanning is O(n log n) (due to sorting), which is much faster than graph coloring's O(n²) or higher. The cost: it produces more spills than graph coloring (because it doesn't look at the interference graph, it might spill two non-interfering intervals). Linear scanning is commonly used in JIT compilation—compilation time is paramount, and a few extra spills are acceptable.

Benefits of SSA for Register Allocation

In SSA form, the def-use relationships between variables naturally form a chordal graph structure—coloring chordal graphs can be solved optimally using a greedy algorithm in O(n). However, note that actual register allocation usually occurs after SSA destruction (inserting copies); the copies introduced by phi destruction may break the chordal graph property. Nevertheless, the coalescing phase will try to merge these copies as much as possible, keeping coloring efficient.

Coalescing: Eliminating Copies

v1 = ...
v2 = v1           ← Copy: requires a mov instruction
... = v2

If v1 and v2 are assigned the same register r:
  r = ...
  ... = r         ← Copy is eliminated

Coalescing is not without cost—merging v1 and v2 into a single node may increase its degree, making it uncolorable. Therefore, coalescing is conservative: it only coalesces copies that will not introduce spills after coloring. Briggs' conservative coalescing checks if the merged node's degree < K (available registers); George's conservative coalescing checks if all adjacent nodes of v1 are "already non-conflicting with v2 or have degree < K".

Calling Convention and Allocator Interactions

Physical registers are constrained not only by virtual register contention but also by the calling convention:

Argument registers (x86-64: rdi, rsi, rdx, rcx, r8, r9): The first 6 arguments of a function call must be placed in these registers.
Return value register (rax): The function return value is in rax.
Callee-saved (x86-64: rbx, rbp, r12–r15): If the called function modifies these registers, it must restore them before returning. The called function handles spill/restore; the caller does nothing.
Caller-saved (x86-64: rax, rcx, rdx, rsi, rdi, r8–r11): If the caller needs to use these registers before and after a call, it must handle spill/restore itself.

The register allocator must adhere to these constraints: spill callee-saved physical registers to the stack in the function prologue if they are used during allocation; before and after call instructions, do not assume that values in caller-saved physical registers will survive the call.

References

Chaitin (1982): "Register Allocation and Spilling via Graph Coloring" — The original paper on graph coloring allocation
Poletto/Sarkar (1999): "Linear Scan Register Allocation" — The original paper on linear scanning
LLVM: lib/CodeGen/RegAllocGreedy.cpp (default allocator), lib/CodeGen/RegAllocBasic.cpp (baseline) — Industrial-grade allocators, combining linear scanning and graph coloring

Keywords: register allocation, interference graph, graph coloring, Chaitin, Briggs, optimistic coloring, linear scan, spilling, spill code, splitting, coalescing, copy elimination, liveness, live range, chordal graph, register pressure, caller-saved, callee-saved, calling convention, prologue, epilogue, SSA-based allocation