Register Allocation With a Five-Clique
An optimizing compiler lowers a hot loop to three-address code with six live variables a, b, c, d, e, and f. The target has four general-purpose registers. The interference graph has edges a-b, a-c, a-d, a-e, b-c, b-d, b-e, c-d, c-e, d-e, forming a clique on {a, b, c, d, e}, plus edges a-f, b-f, and c-f. Variable f is not adjacent to d or e. The loop executes 1000 times. Per iteration, the estimated use counts are a: 2, b: 50, c: 50, d: 50, e: 50, and f: 20. The compiler currently spills nothing and fails register allocation. A teammate suggests spilling f because f has the fewest graph neighbours. Evaluate that suggestion, choose a spill if one is required, and describe the resulting allocation and spill code.
1. Show that the interference graph is not 4-colourable before any spill. Which substructure forces this?
Read the worked answer
The variables a, b, c, d, and e are pairwise adjacent: every pair among them has an edge. They form a clique of size 5. In any valid colouring, every pair of adjacent variables must receive different colours, so a clique of size k requires at least k colours. Therefore this graph needs at least 5 registers, but the target has only 4. The extra node f does not cause the problem; even without f the graph is not 4-colourable. At least one variable from the five-clique must be spilled. Spilling f cannot help because f is not in the clique and the remaining five clique variables still require five colours.
2. Using spill cost = use count / degree, compute the candidates' costs and choose a variable to spill. Why is f a poor choice despite having the lowest degree?
Read the worked answer
Degrees: a is adjacent to b, c, d, e, and f, so degree 5; b and c likewise degree 5; d and e are adjacent to the other four clique members, so degree 4; f is adjacent to a, b, and c, so degree 3. Costs: a = 2/5 = 0.4; b = 50/5 = 10; c = 50/5 = 10; d = 50/4 = 12.5; e = 50/4 = 12.5; f = 20/3 = 6.67. Among the clique members that can break the five-clique, a has by far the lowest cost, so spill a. Spilling f is poor because f is not in the clique: removing f leaves the five-clique intact and still requires five colours. The low degree of f is irrelevant to feasibility; the spill must come from the clique.
3. After spilling a, give a valid 4-colouring and describe where the spill store and loads must be placed.
Read the worked answer
Removing a leaves the clique b, c, d, e, which is K4 and needs four colours: assign b = R1, c = R2, d = R3, e = R4. Node f is adjacent only to b and c, so it may share a colour with d or e; assign f = R3. This is a valid 4-colouring. For the spilled variable a, the compiler inserts a store to a stack slot immediately after each definition of a in the loop, and a load from that slot immediately before each use. Because a is used twice per iteration, this adds one store and two loads per iteration, for 1000 stores and 2000 loads. The alternative of spilling d or e would add 50,000 stores and 100,000 loads, so the chosen spill is much cheaper even though a load/store pair is not free.