Register Allocation

Register allocation is the compiler phase that maps an unlimited set of virtual registers — each representing a variable or temporary value in an intermediate representation — to the finite set of physical registers available on the target processor. It is the boundary where the abstract, unbounded world of the program meets the concrete, bounded world of hardware. A poor allocation forces the compiler to emit spill code that moves values between registers and memory, often dominating execution cost. A good allocation keeps the most frequently accessed values in registers, minimizing memory traffic and maximizing instruction throughput.

The problem is deceptively simple in statement and devastatingly hard in practice. The compiler must decide, for every point in the program, which values live in which registers, subject to the constraint that no two simultaneously live values may share the same register. The number of physical registers is typically between 8 and 32 for general-purpose architectures, while the number of virtual registers in a modern program may reach thousands. The gap is the source of the problem's difficulty.

From Liveness to Interference

The foundation of register allocation is live variable analysis, a data-flow analysis that determines, for each program point, which variables are live — meaning they will be read before being overwritten. Two variables interfere if there exists any program point where both are simultaneously live. The interference relation can be represented as an undirected graph: vertices are variables, edges connect interfering variables. This interference graph is the central data structure of register allocation.

The interference graph is not given; it is constructed by the compiler from the control flow graph through a process of liveness propagation. The quality of the graph depends on the precision of the liveness analysis. An imprecise analysis — one that conservatively marks variables live when they are not — produces a denser interference graph, making allocation harder. This is a recurring pattern in systems: the abstraction (the graph) is only as good as the analysis that produces it, and the difficulty of the downstream problem is a function of the upstream precision.

Graph Coloring and the NP-Complete Reality

Once the interference graph is built, register allocation becomes a graph coloring problem: assign a color (register) to each vertex such that no adjacent vertices share the same color, using at most R colors where R is the number of physical registers. Graph coloring is NP-complete for R ≥ 3, and register allocation inherits this hardness. The problem is not merely academic. Real programs produce interference graphs with hundreds of vertices and complex topology, and finding an optimal coloring is intractable.

The breakthrough that made graph-coloring register allocation practical was Greg Chaitin's 1981 formulation, implemented in the IBM PL.8 compiler. Chaitin recognized that the interference graph of real programs is not a worst-case random graph. It has structure: low degree vertices, sparse connectivity, and regions of high clustering. This structure can be exploited by heuristic algorithms. The Chaitin-Briggs allocator iteratively removes vertices of degree less than R (which are guaranteed to be colorable), colors the remaining core, and then reinserts the removed vertices in reverse order. This is not guaranteed to find an optimal coloring, but it finds good colorings quickly for the graphs that actually arise.

When the graph cannot be colored with R colors, the allocator must spill a variable to memory, effectively removing it from the graph and reducing the coloring problem's size. The choice of which variable to spill — spill heuristics — is as important as the coloring algorithm itself. Spill too aggressively and the program spends its time moving data; spill too conservatively and the allocator fails to color the graph at all.

Beyond Coloring: Linear Scan and Modern Variants

Graph coloring is not the only approach. Linear scan allocation, introduced by Poletto and Sarkar in 1999, abandons the graph entirely. It sorts variables by their live ranges and scans through the program, allocating registers to active variables and freeing them when variables die. Linear scan is faster than graph coloring — O(n) versus O(n²) or worse — and produces code within 10% of the quality of graph coloring for many programs. It has become the standard for just-in-time compilers where compilation speed matters as much as code quality.

Modern register allocators combine multiple techniques. The LLVM compiler infrastructure uses a hybrid approach: it builds an interference graph, applies coalescing to eliminate unnecessary register-to-register moves, splits live ranges to reduce register pressure, and then runs a coloring heuristic with iterative spilling. The trend is toward allocators that treat register allocation not as a single phase but as a constraint satisfaction problem solved by integer linear programming, genetic algorithms, or reinforcement learning. These approaches are slower but produce measurably better code for hot paths.

Register Allocation as Resource Allocation

Register allocation is not merely a compiler problem. It is an instance of the general problem of allocating scarce, reusable resources to competing demands under temporal constraints. The same mathematical structure appears in instruction scheduling (allocating functional units to operations), wireless frequency assignment (allocating channels to transmitters), and even ecological niche partitioning (allocating habitat resources to species). In each case, the problem is: entities need resources for intervals of time; entities that overlap in time cannot share the same resource; the number of resources is fixed; and the goal is to minimize the cost of unmet demand.

This structural unity is not metaphor. The interference graph of a program and the conflict graph of a wireless network are the same mathematical object. The Chaitin-Briggs heuristic and the greedy frequency-assignment algorithms used in cellular networks are the same algorithm. The insight that unifies them is that resource allocation under temporal constraints is a combinatorial problem whose difficulty depends not on the domain but on the density and topology of the interference structure. A compiler engineer and a network engineer face the same problem, even if they use different vocabulary.

Register allocation research has spent four decades refining graph coloring heuristics, but the real breakthroughs have come from questioning the graph itself. Coalescing, live range splitting, and rematerialization do not improve coloring — they improve the graph. The graph is not the problem; it is an approximation of the problem. And the quality of that approximation, not the elegance of the coloring algorithm, determines the quality of the generated code. The compiler community's obsession with graph coloring has been a case of optimizing the wrong abstraction.