Register Allocation: Graph Coloring Visualizer

Program

Physical registers (k) 3

Playback speed 1.0×

Phase

–

Step

–

Colored / spilled

–

Interference edges

–

How it works

The engine runs real Chaitin/Chaitin-Briggs graph-coloring register allocation on the three-address code shown top-right. A backward liveness pass computes which virtual registers are live at each instruction; two registers interfere if one is defined while the other is still live. That produces the interference graph you see — a node per virtual register, an edge per conflicting pair.

liveIn[i]  = use[i] ∪ (liveOut[i] − def[i])
liveOut[i] = liveIn[i+1]
interfere(d,v)  iff  v ∈ liveOut[i] ∧ v ≠ def[i]
simplify: push r onto stack while deg(r) < k
select:   pop r, color := lowest free color among colored neighbours
          if none free → r is spilled

Simplify — nodes with fewer than k live neighbours are provably colorable, so they're peeled off and pushed onto a stack (moving right, off the graph). If every remaining node has degree ≥ k, the highest-degree node is pushed anyway as an optimistic spill candidate.
Select — nodes pop back off the stack in reverse order and get the lowest-numbered physical register (color) not already used by an already-colored neighbour. A spill candidate that finds no free color turns red: that virtual register has to live in memory, not a register.
k (physical registers) — fewer registers means a denser, harder-to-color graph and more spills; real CPUs give a compiler roughly 8–16 general-purpose registers to work with.
Program — switch the source snippet to change register pressure: "High pressure" keeps more values simultaneously live, so it spills sooner at low k.

Real-world relevance: this is the same algorithm (Chaitin 1981, refined by Briggs) that LLVM's and GCC's back ends use to map an unbounded pool of compiler-generated virtual registers onto the small, fixed set of physical registers a CPU actually has.

Building graph

Unallocated On simplify stack Colored (register) Spilled to memory

⚠ Couldn't load the 3D engineThree.js failed to load from the CDN. Check your connection and reload.