When a graph-colouring register allocator cannot colour the interference graph with the registers it has, what does it do?
answer
- one node per live range
- edge means live at the same time
- k colours, k registers
- degree below k is always safe
- spilling shortens a range, not the value count
basics
~20 sIt spills. The allocator picks a value by cost, rewrites it to live in the stack frame with a store after its definition and a load before each use, which breaks one long live range into several short ones, then rebuilds the graph and tries to colour again.
solid answer
~50 sThe graph has one node per live range and an edge between any two ranges that are live at the same point, meaning they cannot share a register. Colouring it with `k` colours, where `k` is the number of allocatable registers, is the allocation. The usual heuristic repeatedly removes a node whose degree is below `k` — such a node can always be coloured once its neighbours are — and pushes it on a stack. When no such node remains, the allocator chooses a **spill candidate** using a cost model: many interferences, few uses, and not inside a hot loop. That value is rewritten to live in memory, with a store after its definition and a load before each use. Those tiny load-to-use ranges interfere with almost nothing, the graph's degree drops, and the allocator rebuilds and retries until it colours.
go deeper
Recall the shape of the problem: unlimited values in the intermediate form, a fixed number of machine registers, and a mapping between them.
Explain the graph — a node per live range, an edge for overlapping lifetimes — and the degree-below-k heuristic that colours it without searching.
Diagnose a real spill: identify the loop where pressure exceeds the register count, explain the inserted stores and loads, and name the upstream transform that lengthened the range.
Frame the trade-off across passes: how much lifetime-lengthening the pipeline should permit before allocation, and whether the compile-time cost of better allocation is worth the code it buys.
## Live ranges and the interference graph After the machine-independent passes are done, the code still refers to an unbounded number of values. The machine has a fixed, small set of registers. Allocation is the step that maps one onto the other. The classic formulation builds a graph: - **Nodes** are live ranges — a value from its definition to its last use, taking control flow into account, so one source variable can produce several independent ranges. - **Edges** connect two ranges that are simultaneously live at some point. An edge is a constraint: those two values must not be given the same register, because both still matter at the same moment. Colouring this graph with `k` colours, where `k` is the count of allocatable registers, *is* the allocation. Adjacent nodes get different colours; each colour is a register. ## The simplify heuristic Deciding whether an arbitrary graph can be coloured with `k` colours is NP-complete once `k` reaches three, so allocators do not search for an optimal answer. They use a degree-based heuristic: 1. Repeatedly find a node with **fewer than `k` neighbours**, remove it from the graph, and push it on a stack. Such a node is always colourable later: whatever its neighbours take, fewer than `k` colours are used, so one remains. 2. If every remaining node has degree `k` or more, pick a **spill candidate** and remove it. Some allocators remove it optimistically, hoping its neighbours end up sharing colours, and only spill for real if the colour assignment fails. 3. When the graph is empty, pop the stack and assign each node a colour not used by its already-coloured neighbours. ## What spilling actually is Spilling does not reduce the number of values. It **shortens** a live range. The value is given a slot in the stack frame; the compiler inserts a store immediately after the definition and a load immediately before each use. What was one range spanning a large region becomes a handful of ranges a few instructions long, each interfering with almost nothing. The graph's degree drops, and after a rebuild it usually colours. The cost is memory traffic, paid every time an affected use executes. That is why the candidate is chosen by a cost model rather than arbitrarily: | factor | pushes towards spilling | reason | |---|---|---| | degree in the graph | high | removing it unblocks many other nodes | | number of uses | low | fewer loads inserted | | loop nesting of its uses | shallow | a spill inside a hot loop is paid per iteration | | cheap to recompute | yes | rematerialise at the use instead of reloading | The last row is worth its own name: for a value that is a literal or a trivially recomputable expression, the allocator can emit the computation again at the use rather than a load — cheaper than memory, and it is also the repair for an over-eager hoist that lengthened a range in the first place. ## What else the allocator is juggling - **Copies.** Code arriving from earlier passes is full of moves between values. If the source and destination do not interfere, they can be **coalesced** into one node and the move disappears. Coalescing too aggressively merges nodes and raises degree, which can cause a spill — so allocators coalesce conservatively, only when it provably does not make the graph harder to colour. - **Constrained registers.** Some instructions demand specific registers, and calling conventions fix which registers survive a call. Those appear as pre-coloured nodes, which the colouring must work around rather than choose freely. - **Pressure created upstream.** Every earlier transform that lengthens a live range — hoisting an invariant expression, keeping a value alive across a call, aggressive scheduling that moves a definition earlier — hands the allocator a denser graph. A great deal of what looks like an allocator problem was created three passes earlier. ## Reading the symptom in the wild The signature of a spill-heavy function is a hot loop with stores and loads to stack slots that carry no obvious meaning in the source, and a performance cliff when a loop body grows just past the point where pressure exceeds the register count. The fix is rarely in the allocator: it is reducing the number of values live at once — splitting a loop, shortening lifetimes, or not hoisting something that was cheap to recompute.
- Why is a node with fewer than k neighbours always safe to remove first?Because its neighbours can use at most `k - 1` distinct colours between them, so at least one colour is always left for it whatever they take. Removing such nodes lowers the degree of everything they touched, which often exposes more of them — the graph unravels without any search. Only when no low-degree node remains does the allocator have to consider spilling.
- How can coalescing two copy-related values make allocation worse?Merging them produces one node carrying the union of both neighbour sets, so its degree can exceed the register count even though neither original did. That may turn a colourable graph into one that needs a spill, trading a cheap register-to-register move for memory traffic. Allocators therefore coalesce conservatively, only when the merged node is provably still easy to colour.
- What can a compiler do instead of reloading a spilled value?Rematerialise it: emit the computation again at the point of use. That works when the value is a literal or a short expression whose operands are still available, and it is usually cheaper than a memory access. It is also the natural repair when an earlier motion pass hoisted a cheap computation and lengthened its live range for no gain.
Two meetings that overlap in time cannot use the same room, so you need as many rooms as the worst overlap. When bookings exceed rooms, someone works from a desk downstairs and carries their papers up for each meeting — that carrying is the spill.
saying these in an interview costs you the question
- Thinks an interference edge means one value is computed from the other.
- Says spilling reduces how many values the function has.
- Believes the allocator searches for an optimal colouring.
- Ignores that pre-coloured registers constrain the colouring.
- Treats spills as an allocator defect rather than upstream pressure.
- Assumes coalescing every copy is always beneficial.