Three Registers, Seven Live Ranges: Choosing the Right Spill
A JIT compiler for a small register machine has three general-purpose registers free for allocation across a hot loop, after reserving two for temporaries. Liveness analysis over the loop body produces seven live ranges whose interference pairs are exactly: a–b, a–c, a–d, b–c, b–d, c–d, d–e, e–f, e–g, f–g; every other pair does not interfere. Dynamic counts over one run: live range a has 1 definition and 5 uses, all in the preheader and exit code, so each reference executes once; live range d has 2 definitions and 3 uses, all inside the innermost loop body, which executes 10 times. The remaining ranges are cold and execute once each. The allocator uses Chaitin-style simplify/select with optimistic spilling, and spilling a live range costs one store at each definition plus one load at each use. The team must decide whether any range has to be spilled and, if so, which one, because the wrong choice could add 50 memory operations per run instead of 6.
1. Run the simplify phase with K = 3 and show whether a spill is forced. Give the push order and identify where simplification gets stuck.
Read the worked answer
Degrees (number of interfering neighbours): a = 3, b = 3, c = 3, d = 4, e = 3, f = 2, g = 2.
The rule is that any node with degree < K (strictly fewer than 3 neighbours) can be removed and will certainly be colourable later.
- f has degree 2 → push f. g has degree 2 → push g.
- Removing f and g leaves e with only d as a neighbour → degree 1 → push e.
- Removing e leaves d with a, b, c → degree 3, not < 3. a, b, c, d each have degree exactly 3 and none drops below 3.
The simplify stack stalls with {a, b, c, d} still in the graph. Those four nodes form a K4 (every pair among them interferes), and a K4 needs four colours. With three registers a spill is therefore unavoidable - no ordering, no optimistic colouring and no coalescing decision can rescue it, because a clique of size 4 is a hard lower bound on the chromatic number and hence on register pressure.
2. The degree heuristic points at d (degree 4). Compute the spill-cost heuristic for a and d and state which range should actually be spilled, and why the two heuristics disagree.
Read the worked answer
The standard cost measure is weighted references divided by degree, using execution frequency as the weight.
- a: 1 definition + 5 uses = 6 accesses, all at weight 1 → weighted cost 6; degree 3 → 6/3 = 2.0
- d: 2 definitions + 3 uses = 5 accesses, all at weight 10 → weighted cost 50; degree 4 → 50/4 = 12.5
Spill the range with the lowest cost per degree, so the choice is a, not d.
The heuristics disagree because they answer different questions. Degree measures structural pressure - how much colouring slack is recovered by removing the node - which is why d, with four neighbours, breaks the K4 most effectively. Cost measures textual/dynamic traffic - how much memory traffic the spill will actually generate. Here a executes 6 times per run while d executes 50 weighted times, so spilling d buys a marginally easier graph at eight times the runtime cost. On an inner-loop variable, structural convenience loses to dynamic frequency; a good allocator always multiplies by loop weight before it divides by degree.
3. After spilling your chosen range, complete the colouring with 3 registers, verify no interference pair shares a register, and quantify the resulting memory traffic per run.
Read the worked answer
Remove a. Remaining graph: b–c, b–d, c–d, d–e, e–f, e–g, f–g. Degrees: b = 2, c = 2, d = 3, e = 3, f = 2, g = 2.
Simplify: push f (2), push g (2) → e drops to 1, push e; d drops to 2, push d; b drops to 1, push b; push c. Push order f, g, e, d, b, c.
Select in reverse with R0, R1, R2:
| Range | Register | Constraint check |
|---|---|---|
| c | R0 | first |
| b | R1 | conflicts with c(R0) |
| d | R2 | conflicts with b(R1), c(R0) |
| e | R0 | conflicts with d(R2) |
| g | R1 | conflicts with e(R0) |
| f | R2 | conflicts with e(R0), g(R1) |
Every edge joins distinct registers: b–d = R1/R2, c–d = R0/R2, d–e = R2/R0, e–f = R0/R2, e–g = R0/R1, f–g = R2/R1. Three registers suffice.
Traffic for the spilled a: 1 store at its single definition plus 5 loads at its 5 uses, each executing once → 6 memory operations per run. Had d been spilled: 2 stores + 3 loads = 5 operations per loop iteration x 10 iterations = 50 per run. The cost heuristic turns an 8x mistake into a 6-operation penalty, and because a lives in the preheader and exit, the reloads can often be folded into the surrounding address computation.