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: highest
remaining 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
This 2D version runs the identical simplify/select automaton as the 3D edition, but the graph is drawn with a genuinely separate physics engine: a planar spring-electrical embedding, integrated with 2D vectors only (no z-axis to route around crowding). Every pair of nodes repels with an inverse-square force and every interference edge pulls like a Hookean spring toward a rest length:
F_repel(i,j) = k_rep / d² (push apart, all pairs)
F_spring(i,j) = k_spring · (d − L₀) (pull/push along each edge)
F_center(i) = −c · pos(i) (mild pull to keep the graph on-screen)
v += (F_repel + F_spring + F_center)/m · dt ; v *= e^(−damping·dt) ; pos += v·dt
Confined to the plane, this is a strictly harder embedding problem than the free 3D case: a graph that is not planar cannot settle into a crossing-free layout no matter how long it runs, so denser interference graphs visibly tangle their edges here in a way the 3D version's extra degree of freedom lets it avoid — a real, physically-grounded difference between the two, not just a rendering choice.
- 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; node color = assigned physical register, dark grey = still on the stack, bright red = spilled to memory.