THE INTERFERENCE GRAPH two values alive at once cannot share a register — color the graph
To place variables in a limited set of registers, a compiler builds an interference graph: a node per variable, an edge between two that are live at the same time (so they cannot share a register). Assigning registers becomes graph coloring — give adjacent nodes different colors, using as few colors (registers) as possible. Chaitin's insight was that register allocation is graph coloring; when colors run out, some variable is spilled to memory and the graph is recolored.
THE TECHNIQUE live-at-once = an edge; registers = colors; minimize colors
Four variables with an interference pattern; the demo greedily colors the graph and reports the registers needed — its chromatic number: live demo
HISTORY & CREDIT Gregory Chaitin, 1981
“Give each variable its own register.” — there are never enough. The question is which variables can share, and that is exactly which ones are never alive at the same time — a graph-coloring problem, not a bookkeeping one. cited
1981 · Gregory Chaitin et al. — “Register Allocation via Coloring”: model interference as a graph, allocate by coloring, spill when a node cannot be colored. lineage · graph coloring itself — Kempe's 1879 heuristic (simplify low-degree nodes) is the same trick Chaitin uses. now · Chaitin-Briggs coloring, and linear-scan for JITs, allocate registers in every backend.
Coloring is NP-hard in general, but the register graphs that arise are usually easy, and Kempe's simplify-and-select heuristic colors them fast. When it cannot, that is precisely the signal to spill. Chaitin 1981
RECOMMEND FOR I-13 registers needed for a triangle graph, computed
On the canonical compiler, greedily coloring three mutually-interfering variables plus an isolated one needs 3 colors (registers):
$ i13 run interference.i13 # greedy coloring, K3 + isolated node
ncolors = 3 -- the triangle forces 3; the isolated var reuses color 0
Recommend: the interference graph is N/A for I-13 — it compiles to a stack IVM, not registers. There is nothing to color: operands live on the operand stack, pushed and popped in evaluation order, and the “allocation” is the stack discipline itself (which i13 proves balanced, per region). Register allocation is the price of a register machine; a stack machine simply does not pay it. i13 traded peak speed for a model it can verify in one pass — and this whole classical pass is one of the things that trade removes.