Register Allocation Is Graph Coloring

Symptom

You write a function with forty local variables. The x86-64 machine it runs on has sixteen general-purpose registers, two of which are effectively spoken for.

Something must decide which values live in registers and which live in memory. Get it right and the function runs at register speed. Get it wrong and every operation costs a load and a store, and on a modern machine an L1 hit is around 4 cycles against roughly 1 for a register, with an L2 miss costing 12 to 20 and a trip to DRAM 200 or more.

This is not a marginal optimization. On a tight loop, the difference between a value in a register and the same value spilled is frequently a factor of two or three in wall-clock time. And the compiler makes this decision hundreds of times per function, in a few milliseconds, for every function in your program.

The decision procedure is a graph problem from 1852, and it is NP-complete, and that turns out not to matter.

Statement

Build the interference graph. One vertex per value (more precisely, per live range). An edge between two values that are live at the same time, meaning both will be read later, so they cannot share a register.

Register allocation is graph coloring. Assigning $k$ physical registers to values without conflict is exactly $k$-coloring the interference graph. Chaitin proved the problem NP-complete for $k \ge 3$ by showing every graph is the interference graph of some program.

That last sentence is the twist, and it is why the NP-completeness result has become a historical curiosity in modern compilers rather than a constraint.

Argument

Why interference is the right relation. Two values can share a register exactly when their live ranges do not overlap. Liveness is computed by a backward dataflow analysis, itself a least fixed point over a lattice (T047): a variable is live at a point if some path from there reads it before writing it. Overlapping live ranges become edges, and now the question is purely graph-theoretic.

Chaitin’s algorithm, which is still the shape of every allocator.

1. Build the interference graph from liveness.
2. Simplify. Repeatedly remove any node with degree $< k$ and push it on a stack. Such a node is always colorable, because whatever its neighbours get, fewer than $k$ colors are taken and one remains.
3. Spill. If every remaining node has degree $\ge k$, pick one by a cost heuristic, mark it for spilling, remove it, and continue.
4. Select. Pop the stack, assigning each node a color not used by its already-colored neighbours.
5. Restart if anything was spilled, since spill code introduces new short live ranges.

Step 2 is the whole insight and it is a greedy argument that happens to be correct: degree $< k$ guarantees a color survives, so those nodes can be deferred without risk. The algorithm is not solving the NP-complete problem; it is identifying the easy part and dealing with the rest by giving up on it.

Why NP-completeness does not bite. Three reasons, and all three matter.

First, real interference graphs are sparse and structured, not adversarial. Chaitin’s construction produces a program for any graph, but no human or front end produces those programs.

Second, the greedy heuristic is very good. Briggs’s improvement — optimistic coloring, where a node marked for spilling is still pushed and only actually spilled if no color remains at select time — recovers many nodes that Chaitin’s version spills unnecessarily, because a high-degree node’s neighbours often share colors.

Third and decisively, SSA form makes the graph chordal, and chordal graphs color optimally in linear time. In SSA every value is assigned exactly once, and live ranges consequently form a structure with no induced cycle longer than three. LLVM, GCC’s modern allocator, and every JIT worth naming operate on SSA, so the theoretically intractable problem is being solved exactly, in linear time, on the graphs that actually arise. The hardness result survives; its relevance does not.

Spilling is the actual difficulty, and Chaitin said so. Choosing which value to spill is where the performance is. The standard cost model is

$$\text{cost}(v) = \frac{\sum_{\text{uses } u} 10^{\text{depth}(u)}} {\text{degree}(v)}$$

with $10^{\text{depth}}$ estimating execution frequency by loop nesting: a use inside a doubly nested loop counts 100 times one at the top level. Spill the value with the lowest cost per unit of interference relieved. A value used once outside any loop scores 1; the same value used once inside a triple-nested loop scores 1000, so the heuristic will spill the former a thousand times over before touching the latter, which is exactly right.

Linear scan, for when you cannot afford any of this. Poletto and Sarkar’s algorithm ignores the graph entirely, sorts live intervals by start point, and sweeps, evicting the interval that ends last whenever it runs out of registers. It is $O(n \log n)$ against graph coloring’s $O(n^2)$ or worse, and produces code typically within 10% of optimal. JVM’s C1 tier, and for years Firefox’s JavaScript JIT, used linear scan, because a JIT’s compile time is on the program’s critical path and 10% worse code compiled instantly beats optimal code compiled slowly. LLVM’s default allocator is a greedy variant of linear scan with splitting, not graph coloring, for the same reason.

Coalescing, the other half nobody mentions. A move between two non-interfering values can be eliminated by giving them the same register. But merging their nodes raises the degree and may make the graph uncolorable, so aggressive coalescing causes spills. Conservative coalescing (George and Appel) merges only when the result provably stays colorable, and iterated register coalescing interleaves it with simplification. This is where a large fraction of real allocator complexity lives, and it exists entirely to delete instructions SSA construction introduced.

Forbids

An optimal general-purpose allocator running in polynomial time, unless P = NP. The problem is genuinely hard in the worst case.

Spill-free allocation when live values exceed registers. If $k+1$ values are simultaneously live, one goes to memory. This is pigeonhole (T001) and no cleverness avoids it.

A single spill heuristic optimal for all programs. The cost model estimates frequency, and estimates are wrong; profile-guided allocation exists because static loop-depth heuristics misjudge real execution.

Ignoring the target’s register classes. x86-64’s constraints — div clobbers rdx:rax, some instructions require specific registers, floating point and general registers are disjoint — mean the pure coloring formulation is an idealization every real backend has to distort.

Does not forbid

It does not mean compilers give up on quality. This is the misreading of every NP-completeness result in a compiler. Heuristic allocators routinely produce optimal or near-optimal colorings on real code, and on SSA form the coloring step is exactly optimal in linear time. The hardness lives in spill placement and coalescing, which are where the engineering goes.

It does not mean you should hand-allocate registers. Compilers beat humans at this comprehensively and have since the 1980s. The register keyword in C is ignored by every modern compiler and was removed as meaningful in C++17.

It does not apply only to CPUs. GPU compilers allocate registers under far tighter pressure, because register usage determines occupancy: using more registers per thread means fewer resident warps and less latency hiding, so the allocator’s objective is not purely spill minimization. Wasm, eBPF, and database query JITs all face the same problem.

It does not mean more registers always help. ARM64 has 31 general-purpose registers against x86-64’s 16, which reduces spills, and also enlarges the context-switch and function-prologue cost. The x86-64 to AArch64 gap in real workloads is much smaller than the register count suggests, because the allocator was already handling the pressure.

It does not require the graph to be built at all. Linear scan skips it, and for JIT workloads that is the right tradeoff. Knowing the problem is graph coloring tells you what you are approximating, which is more useful than knowing the exact algorithm.

Boundary

• Idealized registers. Real ISAs have classes, aliasing (al/ax/eax/ rax), and instruction-specific constraints.
• Interacts with scheduling. Aggressive instruction scheduling lengthens live ranges and increases pressure; the two optimizations conflict and are usually run in a fixed order with a heuristic compromise.
• Whole-function scope. Interprocedural allocation across call boundaries is largely unexplored territory in production compilers, and the ABI’s caller/callee-saved split is the crude approximation everyone uses instead.
• Static cost models. Loop depth is a proxy for frequency. Profile-guided optimization replaces it with measurement and typically wins.
• SSA chordality applies to the coloring step only. Spilling remains NP-hard even on SSA, which is the honest statement of what 2005 changed.

The pattern worth keeping: an NP-complete problem in the middle of a hot path is not necessarily a problem. Find the tractable subclass your inputs actually fall into, and the theoretical hardness becomes a footnote about programs nobody writes.

Read next