Graph Colouring Allocation

The whole algorithm rests on one observation, and it is worth stating carefully because everything else is bookkeeping. If a node has fewer than k neighbours, it can be coloured no matter what colours those neighbours end up with. There are at most k-1 of them, they can consume at most k-1 distinct colours, and there are k colours, so at least one is free. Therefore: remove it, remember it, and deal with it later — its colourability is already guaranteed.

Removing it helps, because it decrements its neighbours' degrees and may bring *them* below k. So the algorithm simplifies repeatedly, building a stack, and each node on the stack carries an implicit promise: "when you get to me, a colour will exist".

Chaitin's original algorithm stopped when nothing was below k and spilled immediately. Briggs's contribution was to notice that this is unnecessarily pessimistic: a node with k or more neighbours might still colour, because those neighbours may share colours among themselves. So push it *optimistically* — pick the cheapest one by the spill heuristic, push it anyway, and only spill it at assignment time if no colour turns out to be free. That optimism is free when it works and costs nothing when it does not, which is why every modern colouring allocator is Chaitin-*Briggs*.

Assignment reverses the process. Pop a node, look at the colours already given to its neighbours, and take any colour that is not among them. Because the stack was built by removing nodes whose degree was below k, most pops find a free colour by construction. The optimistically-pushed nodes are the ones that might not, and when one does not, it spills.

The chart below is what our engine actually produces for this function with three registers. %3 pops first and takes rax because nothing is coloured yet. %1 pops next and must avoid %3's rax, so it takes rcx. %0 avoids both and takes rdx. Then %2 pops — and its neighbours %0, %1 and %3 hold all three registers, so the optimism did not pay off and %2 spills. The remaining three pops find colours easily, because their only coloured neighbours are few.

The spill reason our engine records is not "no register was available". It is the reason %2 was the one chosen to be at risk in the first place: live across five instructions with only two uses, the worst ratio in the function. Reporting *why* rather than *that* is a deliberate design choice in the engine, because "the allocator spilled it" is not something a reader can learn anything from.

A production Chaitin-Briggs allocator has two more phases interleaved with these, and both matter more than the simplify loop does.

*Coalescing* merges the two ends of a copy instruction into one node when they do not interfere, deleting the copy. It is essential — out-of-SSA and two-address instruction selection generate copies by the thousand — and it is dangerous, because merging two nodes produces a node with the union of their edges and can push a colourable graph into an uncolourable one. Conservative coalescing rules (Briggs's and George's) exist precisely to merge only when the result is provably still colourable. [[coalescing-and-rematerialization]] is where this is argued.

*Live-range splitting* does the reverse: it cuts one long range into several short ones with copies between them, so that a value can live in a register where the pressure is low and in memory where it is high. Without splitting, a spill is all-or-nothing for the whole range, which is exactly the pessimism our engine exhibits.

And the loop is bigger than it looks. Inserting spill code creates new tiny live ranges for the reload temporaries, which changes the interference graph, which may require another round. Real allocators iterate the whole build-simplify-select-spill cycle until it converges, typically in two or three rounds.