A compiler builds an interference graph G = (V, E): each vertex is a virtual register (a live range from the source program), and an edge (u, v) means u and v are simultaneously live somewhere, so they can never share the same physical register. Allocating registers is exactly graph K-coloring — assign each vertex one of K colors (physical registers) so adjacent vertices differ. Deciding K-colorability is NP-complete in general, so real compilers (Chaitin 1981, Briggs 1994) use a two-phase heuristic instead of an exact solver:
SIMPLIFY:
while some node v has degree(v) < K:
remove v, push v on stack // v is guaranteed a free
// color once its ≤K-1
// neighbors are colored
if nodes remain (all degree ≥ K):
pick a spill candidate v (heuristic: e.g. lowest
spill-cost / highest degree), remove & push it anyway
— this is "optimistic" coloring: it MIGHT still get
a color later if its neighbors don't use every K.
SELECT (pop in reverse removal order):
reinsert v; let U = colors already used by v's
already-colored neighbors
if |U| < K: assign v the lowest color not in U
else: v is an ACTUAL spill — store/load it
from memory instead of a register
The key correctness argument is the simplify guarantee: any vertex with degree < K can always be colored once the rest of the graph is colored, because it has at most K−1 neighbors and therefore at least one of the K colors is free — that's why simplify never fails, only the optimistic spill picks can turn into real spills.
- K slider — number of physical registers actually available on the target machine.
- N / density — size and connectivity of the interference graph; denser graphs need more spills as N grows past K.
- Step / Auto Run — advance the simplify→select automaton one action at a time or continuously; sphere color = assigned physical register, dark grey = still on the stack, bright red = spilled to memory.
- The 3D layout itself is a live force-directed embedding (Hooke's-law spring on every interference edge, inverse-square repulsion between every pair of nodes) — it is not decorative, it is the standard spring-electrical graph-drawing model settling to equilibrium each frame.