Code Generation and Register Allocation
A compiler has parsed a program, checked its types, and lowered it to three-address code (TAC). Every value now lives in an unlimited supply of temporaries — `t1`, `t2`, `t3`, and so on. It is as if the machine had infinite registers. Real machines do not. An x86-64 chip gives you sixteen general-purpose registers. Some are pinned to special duties (stack pointer, argument passing). A tight numerical loop might juggle fifty live temporaries at once. Somebody has to close that gap. Closing it well is the difference between code that runs at native speed and code that spills to memory on every other instruction. This is the job of code generation and register allocation, the last major phase of a classical compiler pipeline before assembly emission. Code generation walks the IR and emits concrete machine instructions. It chooses `add` versus `lea`, decides whether a multiply becomes a shift, and picks addressing modes. Register allocation then decides which of the infinitely many IR temporaries actually deserve one of the machine's scarce registers. It also decides which must live in memory instead. These two problems are usually solved together, because the quality of one constrains the other. A clever instruction selection can create opportunities for allocation. A good allocator can make aggressive instruction selection pay off. The stakes are concrete. LLVM, GCC, the JVM's C2 JIT, and V8's TurboFan all spend a large fraction of their compile time and engineering effort here. This is because register pressure directly governs memory traffic, and memory traffic dominates the running time of most real programs. A program with poor allocation can be two to five times slower than one that has been allocated well, even though both implement the identical algorithm. Register allocation is also one of the few classical compiler problems that is provably NP-hard in general. This is why production compilers use polynomial-time heuristics — graph coloring, linear scan — instead of exact solvers. They accept near-optimal answers in exchange for compiling a million-line codebase in seconds rather than years. This article builds the whole pipeline: how TAC becomes target instructions, how the compiler builds a live range for every variable, how those live ranges become a conflict graph, and how graph coloring (with its escape hatch, spilling) turns that graph into a register assignment. We also cover linear-scan allocation, the fast heuristic that just-in-time compilers prefer. We close with a full worked trace so the mechanics are not just described but seen.
- Code generation lowers Three-Address Code into real machine instructions via instruction selection, choosing concrete opcodes and addressing modes.
- Register allocation assigns the infinite IR temporaries to the machine's finite registers, spilling the rest to memory when necessary.
- Liveness analysis computes, for each program point, which variables' values will still be read later — the foundation everything else builds on.
- Liveness gives an interference graph: two variables conflict (can't share a register) if one is live where the other is defined.
- Graph coloring allocates registers by trying to color the interference graph with k colors (k = number of registers); nodes that can't be colored are spilled to memory.
- Linear-scan allocation trades some code quality for much faster compilation, making it the standard choice in JIT compilers under latency pressure.
Register allocation reduces to graph coloring on an interference graph built from liveness analysis — a beautiful correspondence between a data-flow property and a classical combinatorial problem.
The idea
Three-address code assumes a machine with unboundedly many named locations, each holding one value. Instruction selection is the process of covering this abstract IR with patterns that correspond to real machine instructions — turning `t1 = t2 + t3` into `add reg1, reg2, reg3` (or, on a load/store machine, several instructions), and recognizing composite patterns like `t1 = t2 * 4` that collapse into a single `lea` or shift instruction on a CISC target. Instruction selection is typically framed as tree pattern matching (each IR expression is a tree; each machine instruction is a small tree pattern with a cost) or as peephole rewriting on a sequence of naively generated instructions.
Register allocation is the separate, harder problem: given a stream of machine instructions that still refer to symbolic temporaries, decide a mapping from each temporary to either a physical register or a memory slot, such that the program's meaning is preserved. Two temporaries may share a register only if they are never simultaneously needed — this notion of "needed at the same time" is called interference, and it is derived from liveness: a variable is live at a program point if its current value will be read by some future instruction before being overwritten. The central theorem tying these together is that register allocation is equivalent to graph coloring: build a graph whose nodes are variables and whose edges connect interfering pairs, then a valid assignment to k registers is exactly a proper k-coloring of that graph. When no such coloring exists, some variables must be spilled — stored in memory and reloaded around each use — trading a register for load/store traffic.
How it works
The pipeline runs in five stages, each depending on the output of the last.
1. Instruction selection. Map each TAC statement (or small groups of them) to target instructions using either a maximal-munch tree-pattern matcher or a table-driven, dynamic- programming tiler (used by tools like BURG/`iburg`) that picks the least-cost cover of the IR expression tree.
2. Control-flow graph (CFG) construction. Group instructions into basic blocks (maximal straight-line sequences with one entry and one exit) and connect them by control edges (branches, fallthrough).
3. Liveness analysis. For every basic block B, compute `use[B]` (variables read in B before any local write) and `def[B]` (variables written in B before any local read). Then solve the backward data-flow equations to a fixed point: ``` IN[B] = use[B] ∪ (OUT[B] - def[B]) OUT[B] = ∪_{S ∈ succ(B)} IN[S] ```
4. Interference graph construction. Walk each block's instructions; at each instruction that defines variable `v`, add an edge from `v` to every variable in the live-out set of that instruction (excluding `v` itself, and — for a plain move `v = w` — excluding `w`, since `v` and `w` can share a register in that special case).
5. Coloring / spilling. Attempt to k-color the interference graph via Chaitin's simplify- select algorithm. If some node cannot be colored, either spill it to memory (rewrite the code to insert loads/stores) or, if it is deemed "spillable but rewarding," attempt coalescing — merging move-related nodes that do not interfere, to eliminate redundant `mov` instructions — before retrying. ``` ALGORITHM ChaitinBriggsAllocate(CFG, k) repeat Liveness ← ComputeLiveness(CFG) G ← BuildInterferenceGraph(CFG, Liveness) stack ← empty stack // ---- Simplify ---- worklist ← all nodes n in G with degree(n) < k // "low-degree" nodes while worklist is not empty: pick n from worklist push n onto stack remove n from G // may lower neighbors' degree update worklist with any neighbor now < k // ---- Optional Coalesce (Briggs-style conservative coalescing) ---- for each move instruction (a = b) with a,b not interfering: if merging a,b keeps combined degree < k for enough neighbors: merge a and b in G // one fewer variable to color if G is nonempty and no node has degree < k: // ---- Potential Spill ---- n ← ChooseSpillCandidate(G) // e.g. lowest cost / degree ratio push n onto stack, mark as "potential spill" remove n from G repeat Simplify // ---- Select ---- colors ← empty coloring spilled ← empty set while stack is not empty: n ← pop stack available ← {1..k} - {colors[m] : m adjacent to n, m already colored} if available is nonempty: colors[n] ← pick(available) else: add n to spilled // actual spill confirmed if spilled is empty: return colors else: RewriteWithSpillCode(CFG, spilled) // insert loads/stores // loop again: liveness changed, so recompute ``` The simplify step exploits a key structural fact: a node with fewer than k neighbors can always be colored, no matter how the rest of the graph turns out, because at most k−1 colors are forbidden to it. Removing such nodes first, and re-checking neighbors (whose degree drops), mimics the classic proof that graphs of bounded degeneracy are easy to color. Only when every remaining node has degree ≥ k does the algorithm gamble on a potential spill — removed optimistically, since it might still find a free color once its higher-degree neighbors are colored (this is Chaitin's insight, refined by Briggs into "optimistic coloring"). An alternative, much faster approach used in JIT compilers is linear-scan allocation: order variables by the start of their live intervals (a live range approximated as one contiguous interval rather than an exact liveness set), sweep through the intervals, and assign registers greedily, spilling the interval that ends furthest in the future when registers run out. ``` ALGORITHM LinearScanAllocate(intervals, k) sort intervals by start point active ← empty list (sorted by end point) for each interval i in sorted order: // expire old intervals for each j in active where j.end < i.start: remove j from active free register(j) if |active| == k: spill ← the interval in active ∪ {i} with the LARGEST end point if spill == i: assign i to memory (spill i) else: assign spill's register to i spill spill instead, add i to active else: assign i an unused register add i to active return assignment ```
Complexity & correctness
Liveness analysis. The data-flow equations form a monotone system over the lattice of subsets of variables, ordered by inclusion, and `IN`/`OUT` only grow across iterations (starting from empty sets). By the Knaster–Tarski fixed-point theorem, a monotone function over a finite lattice has a least fixed point reachable by iterating from the bottom element. Each block's sets can only grow, and the lattice has finite height (bounded by the number of variables), so the analysis terminates. With V variables and E CFG edges, and using bit-vectors for set operations, each iteration costs O(V · B) where B is the number of basic blocks, and the number of iterations is bounded by the CFG's structure (worst case O(B), typically far fewer with a good block ordering such as reverse postorder), giving a practical complexity around O(B² · V / w) for word size w — fast enough to run on functions with thousands of blocks.
Interference graph construction. Building the graph is O(I · V) in the worst case, where I is the number of instructions, since each instruction touches its live-out set; in practice average variable liveness is small and this is close to linear in code size.
Graph coloring is NP-hard. Deciding whether a graph is k-colorable for k ≥ 3 is one of Karp's original 21 NP-complete problems, and register-interference graphs offer no free structural guarantee (they can be arbitrarily dense). This is why compilers use the Chaitin–Briggs heuristic rather than an exact solver: it runs in low-order polynomial time — dominated by the simplify phase's O(V + E) stack construction and the select phase's O(V + E) re-coloring pass, so O(V + E) per round — and iterates a small, empirically bounded number of times (spilling typically converges in one or two extra rounds because spilled variables shrink their own live ranges into tiny intervals around each load/store). Correctness of simplify rests on an invariant: any node with degree < k, once its higher- degree neighbors are colored, is guaranteed a free color, because at most k−1 distinct colors can be used by fewer than k neighbors. Popping the stack in reverse removal order therefore never fails to color a node that was pushed during a genuine simplify step (not a potential spill). This is precisely the greedy-coloring guarantee for graphs with degeneracy less than k: repeatedly removing a low-degree node and later coloring in reverse order always succeeds. Potential spills are pessimistic placeholders — they might still get colored by luck (a neighbor's color happens to be unused), which is exactly what "optimistic coloring" checks for at select time, improving on Chaitin's original always-spill rule.
Linear scan runs in O(n log n) for n live intervals — dominated by the initial sort — with each interval processed in amortized O(1) using the active-list bookkeeping (or O(log n) with a priority queue for expiry). It sacrifices precision: because it approximates a variable's true liveness (which can be a union of disjoint ranges, e.g. across a loop) with one contiguous interval, it is provably suboptimal versus graph coloring on some inputs, but it typically allocates 3–20× faster, which is why HotSpot's C1 and early LLVM/JIT-tier compilers use it when compile latency, not peak code speed, is the binding constraint.
Spilling correctness. When a variable is spilled, the compiler must insert a store immediately after every definition and a load immediately before every use, using a fresh temporary confined to a tiny live range. This preserves semantics trivially — the value is never lost, only relocated — and shrinks that variable's contribution to the interference graph to near-zero, which is why re-running the algorithm after a spill round reliably makes progress toward a colorable graph.
Worked example
Consider this loop body, already in three-address code, computing a dot-product-like accumulation: ``` s = 0 L1: if i >= n goto L2 t1 = a[i] t2 = b[i] t3 = t1 * t2 s = s + t3 i = i + 1 goto L1 L2: return s ``` Assume 2 usable registers (`R1`, `R2`) after reserving others for the calling convention.
Step 1 — liveness (computed backward from `L2`).
| Program point | Live-out set |
|---|---|
| after `return s` | {} |
| before `L2: return s` | {s} |
| after `goto L1` | {s, i, n, a, b} |
| after `i = i + 1` | {s, i, n, a, b} |
| after `s = s + t3` | {s, i, n, a, b} |
| after `t3 = t1 * t2` | {t3, s, i, n, a, b} |
| after `t2 = b[i]` | {t2, t1, s, i, n, a, b} |
| after `t1 = a[i]` | {t1, t2, s, i, n, a, b} |
| before `if i>=n` | {s, i, n, a, b} |
| after `s = 0` | {s, i, n, a, b} |
Note `s`, `i`, `n`, `a`, `b` are live across the entire loop body, since the loop reads and writes them on every iteration. Only `t1`, `t2`, `t3` have short, block-local live ranges.
Step 2 — interference graph. `s`, `i`, `n`, `a`, `b` all interfere with each other (mutually live across the loop) and with whichever of `t1`, `t2`, `t3` overlap their definitions. `t1` interferes with `t2` (both live at `t3 = t1 * t2`) but not with `t3` (dead by the time `t3` is defined). This already shows: five variables mutually interfere, but we only have 2 registers.
Step 3 — attempted 2-coloring fails. A clique of size 5 needs 5 colors; 2 is impossible. The allocator must spill. It picks spill candidates by cost — here, `a` and `b` are excellent candidates because they are arrays, referenced only briefly per iteration (`a[i]`, `b[i]`), so spilling them to memory costs one load each per iteration rather than living in a register that constantly gets displaced. `n` is read once per iteration only for the comparison — also cheap to spill. Keep `s` and `i` in registers because they are both read and written every iteration (spilling them would cost a load and a store per iteration, roughly double the traffic).
Step 4 — rewrite with spill code and re-run. ``` s = 0 ; s -> R1 L1: n' = load(n_mem) if i >= n' goto L2 a' = load(a_mem) t1 = a'[i] b' = load(b_mem) t2 = b'[i] t3 = t1 * t2 s = s + t3 i = i + 1 ; i -> R2 goto L1 L2: return s ```
Step 5 — re-color. Now the only long-lived registers are `s` (R1) and `i` (R2); everything else (`n'`, `a'`, `t1`, `b'`, `t2`, `t3`) has a tiny, non-overlapping live range confined to one iteration, so the interference graph among them is sparse and 2-colorable using whichever register is momentarily free. The allocator succeeds on this second round — exactly the "repeat" loop in the pseudocode above, terminating because spilling strictly shrinks live ranges.
Common pitfalls & traps
| Pitfall | Why it happens | Fix |
|---|---|---|
| Forgetting the `def` side of a move `v = w` when building interference | Adding an edge `v–w` for a copy makes coalescing impossible | Special-case move instructions: no interference edge between move-related pairs unless a later def forces one |
| Treating liveness as forward analysis | Liveness is inherently backward (depends on future uses) | Always solve `IN`/`OUT` equations from exit to entry, iterating to a fixed point |
| Ignoring precolored/physical registers (e.g. calling-convention registers) | Causes incorrect codegen around calls, since some registers are pinned before allocation starts | Model ABI-fixed registers as precolored nodes in the graph from the start |
| Infinite spill loop | A "spilled" temporary is given a live range as large as the original, so it never becomes colorable | Confine spill temporaries to minimal live ranges around each individual use/def |
| Using linear scan's interval approximation on loop-heavy code without loop-aware widening | A variable live only in parts of a loop gets treated as live across the whole loop, wasting a register | Use extended live intervals or SSA-based allocators that track precise liveness |
| Choosing spill candidates by degree alone, ignoring use frequency | Spills a variable used inside a hot inner loop just because it has many neighbors | Weight spill cost by estimated execution frequency (loop depth), not just graph degree |
Pioneers & history
Register allocation as graph coloring is largely credited to Gregory Chaitin and his team at IBM, who in the early 1980s recognized that the register assignment problem for the IBM PL.8 compiler was structurally identical to graph coloring — a problem already deeply studied in combinatorics. Preston Briggs later refined Chaitin's always-spill rule into optimistic coloring, letting "potential spills" try their luck at select time, which measurably reduced unnecessary spill code. Massimiliano Poletto and Vivek Sarkar's linear-scan algorithm (late 1990s) gave just-in-time compilers a fast alternative when full graph coloring was too slow for online compilation.
Origins · 1 minGregory J. Chaitin and how this was discovered
Chaitin is better known in theoretical computer science for founding algorithmic information theory alongside Kolmogorov and Solomonoff, and for his work on Chaitin's constant Ω. Less widely known outside compiler circles is his 1981 paper "Register Allocation and Spilling via Graph Coloring," written while at IBM's Yorktown Heights lab, which turned an ad hoc engineering problem into a clean instance of a well-studied NP-hard combinatorial question — a reduction that still underlies register allocators in GCC and LLVM today.
Where this matters
Every ahead-of-time compiler backend relies on this pipeline: GCC's RTL and LLVM's `MachineFunction` passes both implement graph-coloring-style allocators (LLVM's "greedy" allocator is a modernized descendant of Chaitin–Briggs, layered with live-range splitting). Just-in-time compilers — the JVM's HotSpot C1, V8's earlier tiers, and .NET's RyuJIT — favor linear scan for its speed, reserving full graph coloring or heavier optimization for hot methods promoted to a higher optimization tier. GPU shader compilers and DSP toolchains apply the same liveness-and-coloring machinery under extreme register pressure, since GPUs often have only a handful of registers per thread before "occupancy" collapses. Even hardware synthesis tools borrow the interference-graph idea to assign signals to physical wires and flip-flops. Anywhere a program with unbounded named values must run on a machine with a fixed, small set of fast storage locations, this same reduction — liveness, interference, coloring, spilling — reappears.
Ask the tutor: How would live-range splitting change the interference graph and coloring outcome in the worked loop example above?
Why can't the compiler just give every variable its own register?
Real machines expose a small, fixed number of general-purpose registers — often 8 to 32 — while a typical function's Three-Address Code may define hundreds or thousands of temporaries across its lifetime. Register allocation exists precisely because that gap must be closed: many temporaries are never simultaneously alive, so they can safely share one physical register, and the ones that truly are simultaneously alive in excess of the register count must live in memory (a "spill") instead. Giving every variable a permanent register is simply impossible once demand exceeds supply, which happens in almost any nontrivial function.
What exactly is a "live range" and how does it differ from a variable's whole lifetime in the source?
A live range (or live interval) is the portion of the program between a variable's definition and its last use before being overwritten or going out of scope — not its entire textual scope. A variable declared at the top of a function but only used once, briefly, near the bottom has a short live range even though its declared scope spans the whole function. Live ranges are computed from the liveness data-flow analysis, and precise (not merely approximate) live ranges are what make graph-coloring allocators find tighter, more efficient colorings than interval-based ones.
Is graph coloring truly required, or could a compiler just use a simple heuristic like round-robin assignment?
Round-robin or first-fit assignment ignores which variables are simultaneously alive, so it will frequently overwrite a value that is still needed, producing incorrect code — it isn't a matter of quality but of correctness. The interference graph exists to encode exactly the constraint that must be respected: two variables may only share a register if they are never live at the same program point. Any valid allocator, fast or slow, must respect this constraint, which is mathematically identical to proper graph coloring.
How does spilling interact with the calling convention and other precolored registers?
Calling-convention-mandated registers (return-value register, stack pointer, argument registers at call sites) are modeled as precolored nodes in the interference graph — nodes whose color is fixed before the algorithm runs. These nodes still generate interference edges normally (e.g. any variable live across a call interferes with all caller-saved registers), but they are never pushed onto the simplify stack for coloring since their color is already decided. This correctly forces other variables to avoid those registers exactly where the ABI requires it.
Why does coalescing matter, and why is naive coalescing dangerous?
Coalescing merges two variables connected by a `mov` instruction (and not otherwise interfering) into a single node, letting the allocator assign them the same register and delete the redundant copy instruction entirely — a direct code-size and speed win. Naive (aggressive) coalescing is dangerous because merging two nodes also merges their neighbor sets, which can push a previously low-degree, easily colorable graph into one where nodes exceed degree k and become unspillable without extra work. Briggs' conservative coalescing rule only merges when the result still has few enough high-degree neighbors to remain safely colorable.
Does SSA form change how register allocation works?
Yes: representing the program in Static Single Assignment form gives each variable exactly one definition, which makes precise live-range computation and interference graph construction noticeably simpler, and — remarkably — interference graphs built from strict SSA programs are provably chordal, a graph class that is always colorable in polynomial time with a simple greedy algorithm (no NP-hardness barrier). Modern allocators exploit this by allocating registers directly on SSA form and inserting the necessary "copies" only when leaving SSA (at φ-node elimination), rather than allocating on raw non-SSA code.
Why do some compilers combine both graph coloring and linear scan instead of picking one?
Compile-time budget varies wildly by context: an ahead-of-time build run once and shipped to millions of users can afford minutes of optimization, while a JIT compiling a hot method inside a running server must finish in microseconds without stalling the application. Systems like LLVM and HotSpot use tiered compilation: a cheap allocator (often linear scan or a fast greedy pass) handles code on its first, unoptimized run, and a heavier graph-coloring-style allocator kicks in only once profiling shows the method is hot enough to justify spending more compile time on better code.