The simple code generator juggled two registers by hand. A real machine has a fixed, small pool — say k = 16 or 32 general registers — and a function full of variables and temporaries that vastly outnumber them. The allocator's job is to map that unbounded set of values onto k physical registers, keeping as much as possible out of memory. The beautiful insight, due to Chaitin and refined by Briggs, is that this is a graph problem in disguise.

Two values may share a register whenever they are never needed at the same time. So build a graph whose nodes are the values and whose edges join values that interfere — that are simultaneously live and therefore cannot share a register. Assigning registers so that no two interfering values collide is exactly colouring the graph with k colours, one colour per register. Register allocation is graph colouring.

Liveness builds the interference graph

The edges come from liveness analysis. A variable is live at a program point if its current value may be read later before being overwritten. Two variables interfere if there is a point where both are live at once — more precisely, an edge is added between a variable being defined and every other variable live at that definition (they must survive the write into different registers).

Compute live sets across the control-flow graph, walk each block backward adding an edge from each defined value to everything then live, and you have the interference graph. Its structure is everything the allocator needs: it has forgotten the code entirely and reduced allocation to pure combinatorics on a graph.

Simplify and select: the Chaitin–Briggs stack

Colouring is driven by one deceptively powerful observation about degree. It gives a sufficient condition for colourability and a way to peel the graph down to it:

if a node has fewer than k neighbours, then whatever colours those neighbours end up with, at most k-1 colours are blocked, so a free colour always remains for this node;
therefore we may remove any degree-<k node from the graph, push it on a stack, and colour it later — its removal can only lower its neighbours' degrees, exposing more removable nodes;
consequently a graph in which every node has degree < k is guaranteed k-colourable.

This gives the two-phase algorithm. Simplify: repeatedly remove a degree-<k node and push it, until the graph is empty. Select: pop nodes off the stack one at a time, giving each the lowest-numbered colour not used by its (already-coloured) neighbours. Because each node was removed while it had < k neighbours, a colour is always available on the way back up. Watch it run on a small interference graph with k = 3 registers:

The triangle A\text{–}B\text{–}C forces three distinct colours, so this graph needs all three registers; node D, which does not interfere with B, happily reuses B's register (R2). Four values, three registers, zero spills.

Optimistic colouring and real spills

What if simplify gets stuck — every remaining node has degree \ge k? Chaitin's original allocator would immediately pick a node to spill to memory. Briggs' improvement is optimistic colouring: push the high-degree node onto the stack anyway (marking it a potential spill) and carry on simplifying. On the way back up in select, that node might still find a free colour — because its many neighbours, by luck, may not have used all k colours. Optimism pays off surprisingly often and colours graphs Chaitin's method would have spilled.

If select really does find no colour for a node, that node becomes an actual spill: its value is kept in memory, with loads before each use and stores after each definition. Crucially, spilling changes the code — those new loads and stores are short-lived new values — so the interference graph is rebuilt and the whole simplify/select process repeats. After a round or two the graph colours cleanly and allocation is done.

build interference graph repeat: SIMPLIFY: while some node has degree < k, remove it and push on stack if stuck: push a high-degree node optimistically (potential spill) SELECT: pop each node, assign a colour not used by neighbours if some node gets no colour → mark it an ACTUAL spill until no actual spills (spilled values get loads/stores; graph is rebuilt and we go again)

Colouring by simplify/select, in code

The allocator below takes an interference graph as an adjacency map and k registers. It simplifies (removing degree-<k nodes, or optimistically pushing the highest-degree one when stuck), then selects colours off the stack. Run on the graph from the figure with k = 3:

type Graph = Record<string, string[]>; function allocate(g: Graph, k: number): Record<string, number> | null { const nodes = Object.keys(g); const removed = new Set<string>(); const stack: string[] = []; const liveDeg = (v: string) => g[v].filter((u) => !removed.has(u)).length; // SIMPLIFY while (removed.size < nodes.length) { let pick = nodes.find((v) => !removed.has(v) && liveDeg(v) < k); if (pick === undefined) { // Stuck: optimistically push the highest-degree remaining node. let best = "", bd = -1; for (const v of nodes) if (!removed.has(v) && liveDeg(v) > bd) { bd = liveDeg(v); best = v; } pick = best; console.log(`simplify: optimistic push ${pick} (degree ${bd} >= k)`); } else { console.log(`simplify: push ${pick} (degree ${liveDeg(pick)} < ${k})`); } removed.add(pick); stack.push(pick); } // SELECT const colour: Record<string, number> = {}; while (stack.length) { const v = stack.pop()!; const used = new Set<number>(); for (const u of g[v]) if (u in colour) used.add(colour[u]); let c = 0; while (used.has(c)) c++; if (c >= k) { console.log(`select: ${v} -> ACTUAL SPILL (no colour < ${k})`); return null; } colour[v] = c; console.log(`select: ${v} -> R${c + 1}`); } return colour; } // Interference graph: triangle A-B-C, plus D interfering with A and C only. const g: Graph = { A: ["B", "C", "D"], B: ["A", "C"], C: ["A", "B", "D"], D: ["A", "C"], }; const result = allocate(g, 3); console.log("--- assignment ---"); if (result) for (const v of Object.keys(g)) console.log(`${v} -> R${result[v] + 1}`); else console.log("needs a spill; rebuild graph and retry");

Drop k to 2 and rerun: the triangle A\text{–}B\text{–}C cannot be 2-coloured, so select reports an actual spill — the signal to spill a value to memory, rebuild, and try again.

Coalescing: deleting the copies

One more trick makes colouring earn its keep. A move x := y is pure overhead if x and y can be given the same register — then the copy is a no-op and can be deleted. Coalescing merges the two nodes in the interference graph into one (provided they do not interfere), so the allocator assigns them a single register and the move vanishes. Overdo it, though, and the merged super-node has so many neighbours it becomes uncolourable, forcing a spill. Conservative coalescing (Briggs) merges two nodes only when the result is provably still colourable — capturing most move savings without provoking spills.

Deciding whether a general graph is k-colourable is NP-complete — there is no known efficient algorithm that is always optimal. But the allocator does not need optimal. The simplify/select heuristic is linear-ish and, thanks to the degree-<k rule, colours the overwhelming majority of real interference graphs perfectly; where it can't, it spills and retries. It trades guaranteed optimality for guaranteed speed and near-optimal results in practice — the same bargain maximal munch strikes in instruction selection. Interestingly, the interference graphs of programs without goto spaghetti are often chordal, a class that is colourable optimally in polynomial time — which is part of why the heuristic does so well.

The degree-<k rule is a one-way guarantee. If a node has fewer than k neighbours it is definitely colourable — but a node with degree \ge k is not necessarily uncolourable. A node with many neighbours that among them use only a few colours still has a colour free. This is exactly why Briggs' optimistic push works: never assume a high-degree node must spill; push it and find out during select.

The second trap is treating a spill as the end. When select fails, you do not just leave that value in memory and keep the rest of the assignment — spilling inserts new load/store instructions, which create new short live ranges and thus a different interference graph. You must rebuild the graph and run simplify/select again. Allocation is a loop, not a single pass; forgetting the rebuild yields an inconsistent, incorrect assignment.