Spilling

A register operand is part of the instruction and costs nothing extra. A spilled value costs a mov from memory before each use and a mov to memory after each definition, and those instructions have consequences beyond their count: they lengthen the dependence chain through the value, they consume load and store issue ports, and they occupy stack space that may or may not be in cache.

The good case is not terrible. A spill slot in the current stack frame is almost certainly in L1, and store-to-load forwarding on a modern core can satisfy a reload from a very recent store without going to cache at all. The bad case is genuinely bad: a spill inside a loop, reloaded every iteration, on a working set that has evicted the frame from L1. That is the difference between a few percent and several times slower, and it is why "the loop spills" is a real diagnosis rather than a stylistic complaint.

The transformation below is what a spill looks like in the instruction stream. Note the shape: two extra instructions for one use, and the arithmetic that used to be one instruction is now three with a memory dependence in the middle.

Since spilling is unavoidable above the peak-pressure bound, the decision that matters is which value loses. The heuristic in our engine is the classic one: cost is uses divided by the length of the live range, with a penalty for crossing a call, and the value with the lowest cost is spilled. Read it as "how much does this value get out of the register it is occupying" — a value read twenty times in a five-instruction range is earning its place, and one read twice across fifty instructions is not.

The call penalty deserves a sentence of its own. A value live across a call must either sit in a callee-saved register — which obliges the function to save and restore it — or be spilled around the call anyway. Since it is going to cost memory traffic in either case, it is a cheaper spill candidate than an equivalent value that does not cross a call. Our engine encodes that by reducing its cost, making it more likely to be chosen.

What our heuristic is missing is loop depth, and that omission is the most important thing to know about spill heuristics generally. A use inside a loop executed a thousand times is worth a thousand uses outside it, and every production allocator weights uses by estimated execution frequency — from static heuristics (loops are hot, error paths are cold) or from a real profile. An allocator that counts uses without weighting them will happily spill the inner-loop value and keep the one used once at function entry.

The awkward property of spilling is that it is not the end of the allocation — it is a modification of the program that the allocator must then re-analyse. Each inserted reload defines a new short-lived value that needs a register of its own, right at the point where pressure was already at its peak. Insert enough of them and the new temporaries create pressure that requires further spilling.

This is why a production Chaitin-Briggs allocator is a loop: build the graph, try to colour, insert spill code for whatever failed, rebuild, try again. It normally converges in two or three rounds because the reload temporaries are extremely short-lived and easy to colour, but the loop is genuinely necessary and an allocator that spills once and stops — as ours does — is producing an allocation that has not been checked against its own output.

The better answer, where it can be afforded, is not to make the decision all-or-nothing. *Live-range splitting* keeps a value in a register through the region where it is used and in memory through the region where it is not, inserting copies at the boundaries. That is strictly more expressive than spilling the whole range, and it is the single largest quality difference between a textbook allocator and a production one.

The most useful thing to know about spilling is that the allocator is rarely the right place to fix it. Register pressure is manufactured upstream, and by the time the allocator sees it the decision has been made by someone else.

Inlining is the largest source: bringing a callee's body into a loop brings its live values with it, and an inliner working to a size budget has no model of register pressure at all. Unrolling multiplies the working set by the unroll factor. Vectorization consumes vector registers and often forces integer pressure up alongside. And the scheduler, hoisting loads to hide latency, deliberately extends live ranges — which is the clearest example of two phases with opposite objectives running one after the other.

So when a hot loop spills, the productive question is which upstream decision put too many values in flight, not which allocator flag to turn. Reducing the inline budget for that call site, capping the unroll factor, or restructuring so the inner loop touches fewer values are all interventions that work; asking the allocator to be cleverer usually is not.