Spill Cost Heuristics and the Choice of Victim

Spilling is the allocator’s admission that the graph is not colorable with the registers available. The admission is cheap; the decision of which value to spill is not. A spill turns one register into a stack slot plus a set of loads and stores, and the quality of the resulting code is dominated by where those loads and stores land: in a loop body they cost a memory access per iteration, in straight-line code they cost one each. The heuristic that picks the victim is therefore an attempt to predict dynamic behaviour from static structure, and every version of it is an approximation with a known failure mode.

Pricing a value

The natural cost of spilling a value is the number of times its loads and stores execute. A definition that is spilled needs a store at the definition; each use that is spilled needs a load before the use. If a value is defined once and used three times, a naive count gives four memory operations. The count is wrong in two directions.

It ignores the loop multiplier. A use inside a loop that runs a thousand times costs a thousand loads, and a use outside costs one. The standard correction weights each basic block by its estimated execution frequency, typically 10^depth for a block at loop nesting depth depth, and sums the weighted def and use counts. The weights are an estimate, not a measurement: the classic scheme assumes every loop trip count is ten, which is wrong for almost every loop and right in the sense that it ranks a loop body above straight-line code by a large factor. Compilers that have profile data use actual counts instead, which replaces the table entry for each block with a measured frequency; the estimates differ from the measurements most where the static rule is weakest, namely loops whose trip count is far from the assumed one.

It ignores the reuse that spilling creates. If two values are spilled to the same slot at different times, the slot is reused, and the second spill’s store may be dead if the first value is never read again. More importantly, a split can keep a value in a register for the duration of a loop body that would otherwise have reloaded it at every use, with a single store before the loop and a single load after. That is the live-range shaping described under splitting and rematerialization, and it changes the cost from per-iteration to per-loop.

The cost is usually normalized by degree, because the point of spilling is to reduce pressure: a value with many neighbors blocks many potential colorings, and removing it frees all of them. Chaitin’s rule is to spill the node minimizing cost / degree, which prefers values that are cheap and highly connected. The ratio has a defect that shows up on real graphs: a value with degree 2 and cost 4 has ratio 2, and a value with degree 50 and cost 80 has ratio 1.6, so the second is spilled first. That is the intended outcome only if removing the high-degree node relieves more pressure, and it does not always: when the graph is already dense, the neighbours of a high-degree node are likely to be connected to each other, so removing it frees fewer new colourings than its degree suggests.

Loops change the objective

The single most important structural fact about spilling is that the cost is not additive over the graph in the way the ratio assumes. Spilling one value inside a loop can force a reload in the loop preheader and a store in the exit, which is cheap, but it can also force the value’s loop-carried neighbors to be spilled, because the reloaded value now occupies a register for the whole body. The cascade is the reason production allocators do not simply pick the minimum ratio and stop: they recompute the graph after each spill and re-run the coloring, or they use a region-based decomposition where each loop nest is allocated separately.

The alternative to spilling at all is rematerialization. A value whose definition is cheap to recompute, such as a constant, an address computation from an invariant base, or a load from a known location, can be dropped from the graph and recomputed at each use instead of being stored and reloaded. The distinction matters for costs: a spilled constant costs a load from a stack slot, a rematerialized constant costs an immediate move, and the latter is strictly cheaper. Recognizing rematerializable values requires knowing which instructions are safe to duplicate and which have side effects, which is a property the instruction selector has to record.

Where the loads and stores go

After the victim is chosen, the value is rewritten to live in a stack slot, and the rewrite is not mechanical. Three placements are possible at each use: load into a fresh temporary immediately before the use, reuse a register that already holds the value if one is live, or, for a value used by a single instruction with a memory operand form, fold the load into the instruction. The third is only available when the target has such a form, and it is the reason spilled values sometimes cost nothing at all: add r1, [rbp-16] performs the load as part of the operation.

The store side is simpler but has its own subtlety. A store at the definition is required only if the value is read on some path from that definition before being redefined. A value defined and then killed on all paths needs no store, which is exactly the liveness information from the earlier analysis applied to the spilled form. Allocators that store unconditionally at every definition produce extra memory traffic that a dead-store pass would have to clean up.

Stack slot assignment is a separate allocation problem: each spilled value needs a slot, and values with disjoint live ranges can share one. The sharing problem is coloring again, with slot offsets instead of register numbers, and it is solved the same way: build interference over the spilled values’ live ranges and color with the stack frame as the resource. Alignment matters: a 16-byte vector value needs a 16-byte-aligned slot on a target whose vector loads require aligned addresses, and packing an 8-byte value into the leftover 8 bytes is only possible if the frame layout respects the alignment.

The spill loop and its termination

The classical structure is a loop: color, spill the chosen victims, rebuild, recolor. Termination is guaranteed only if every iteration spills at least one value that was not already spilled and if the set of spillable values is finite, which it is. The loop can still take many iterations on a large function, and each iteration costs a full liveness analysis plus graph construction, which is why production allocators limit the number of rounds or switch to a different algorithm when the first round spills heavily.

Briggs’ optimistic coloring changes the loop’s shape: because a stalled node is tried rather than pre-emptively spilled, the first coloring pass often reports a much smaller spill set, and the rebuild is smaller. The improvement is not in the heuristic’s accuracy but in the number of values that turn out to be colorable after all.

A cost model in code

The following computes static spill cost with loop-depth weights. The weights are a parameter rather than a measurement, because the structure of the model is what matters: a def and a use are treated as a store and a load, and every block’s contribution is scaled by the weight raised to its nesting depth.

def spill_costs(blocks, depth, defs, uses, weight=10):
    # blocks: list of block ids; depth[b] is loop nesting depth
    # defs[b], uses[b]: counts of definitions and uses of the value in block b
    total = 0
    for b in blocks:
        # a definition is a store; each use is a load, unless folded
        total += (defs[b] + uses[b]) * (weight ** depth[b])
    return total

def choose_victim(candidates, cost, degree):
    # candidates are uncolored, unspilled nodes; minimize cost per relief
    return min(candidates, key=lambda v: cost[v] / max(degree[v], 1))

The weight ** depth term grows fast: depth 3 with weight 10 is a factor of 1000, which means a single use in a triply nested loop outweighs a thousand uses in straight-line code. That is the intended behaviour and also the model’s weakness: a loop that runs twice is treated the same as a loop that runs a billion times. Profile data replaces the weight with an observed count and removes the guesswork; without it, the weight is a prior about which code matters. The interaction with linear scan is worth noting: its eviction rule compares end points rather than costs, so the model above is used to choose the spill set before the sweep, not during it.

Numbers worth knowing

A spilled value costs at least one store and one load per definition-use chain, each a memory access to a stack slot that is usually in L1, costing on the order of a few cycles when it hits and hundreds when it misses. A register-to-register move costs about one cycle. The ratio of a few hundred to one is why spilling inside a hot loop is worth almost any amount of extra work to avoid, and why the loop weight is large.

Frame size is the other number that constrains the choice. A stack frame larger than a page (4 KiB on most systems) spans multiple pages, which makes guard-page probes and stack-clash checking relevant; frames in the tens of kilobytes are common in functions with large local arrays, and the spilled slots are a small fraction of that. Slots are typically 8 bytes on a 64-bit target, and a function with 50 spilled values adds 400 bytes before alignment padding, which is negligible against the frame’s other contents.

The last number is the one that matters for the algorithm: the number of colors K. On x86-64 there are 16 general-purpose registers, of which the stack pointer, frame pointer, and often one scratch register are reserved, leaving about 13 usable; on AArch64 there are 31 general-purpose registers with fewer reserved, which is why the same function spills less there. The difference between 13 and 31 colors is not a simple factor of two in spill count: whether a value spills depends on the clique it belongs to relative to K, so a small increase in K can remove the spills of an entire region at once and leave the rest untouched. That is why register-rich architectures tolerate much sloppier allocation and why allocation quality matters most on register-poor ones.