GRAPH COLORING registers are colors; the rest spills
Model machine registers as colors: build the interference graph (two variables that are live at the same time interfere), then k-color it, where k is the number of registers. Whatever cannot be colored is spilled to memory. The clique number is a hard floor: a K4 needs 4 colors, so with k=3 a spill is unavoidable no matter the ordering.
THE TECHNIQUE simplify, then select; spill if stuck
Simplify: repeatedly remove a node of degree < k and push it on a stack (Kempe’s lemma — it can always be colored later). If every node has degree ≥ k, mark a spill candidate. Select: pop each node, give it the lowest color no neighbour uses; if none is free, it spills to memory. Below: an interference graph, k colors, live. live demo
HISTORY & CREDIT the simplify step is 100 years older
“Chaitin invented graph-coloring register allocation” — he led the first implementation (1981); the reduction is hisErshov’s (1962), and simplify is Kempe’s (1879). cited
1879 · Alfred Kempe — the degree-reduction lemma (delete a vertex of degree < k, color the rest, color it last), from his (flawed) four-color proof. Simplify is his. 1962 · Andrei Ershov (USSR) reduces memory allocation to graph vertex-coloring; Cocke & Schwartz float it at IBM/NYU c.1971 but never implement it. 1981 · Chaitin et al. (six authors) — the first working allocator (PL.8 / IBM 801 RISC), and the NP-completeness proof (every graph is some program’s interference graph); the sole-author 1982 “Yorktown allocator” adds spilling. 1994 · Briggs, Cooper & Torczon — optimistic coloring (push the spill candidate anyway; a color often frees up at select). 2005–07 · Hack / Bouchez / Pereira-Palsberg — strict-SSA interference graphs are chordal → optimal coloring in linear time, so the NP-completeness is about the general formulation.
A K4 forces a spill at k=3 that no ordering can avoid — colorability is the clique number, not average degree. Chaitin, 1981–82
RECOMMEND FOR I-13 adjacency masks; a used-color mask; spill
The interference graph is adjacency bitmasks, coloring is a lowest-free-color scan, and the spill falls out:
$ i13 run color.i13 # K4 on {0,1,2,3}, k=3 registers
colors = [0, 1, 2, SPILL] node 3's neighbours use all 3 colors -> spills to memory
spills = 1 (K4 needs 4 colors > k=3; a spill is unavoidable)
triangle {0,1,2}, k=3 -> colors [0,1,2], spills = 0
Recommend:nothing new — the interference graph is per-node adjacency bitmasks; coloring scans each node’s neighbours to a used-color mask and takes the lowest color < k; if none, the node is marked spilled (verified K4 at k=3 → colors 0,1,2 and one spill; triangle → 0 spills). Kempe’s simplify is a degree test, all f64 + bitwise. Note: it consumes liveness (dart 136) — the interference edges come from “live at the same time.” A dense interference graph is an adjacency matrix (PS-004); the corpus flattens it to per-node masks, exact up to 63 nodes.