Coalescing and Rematerialization
Two ways to avoid paying. Coalescing merges a copy's source and destination into one register when they do not interfere, deleting the copy. Rematerialization recomputes a cheap value at each use instead of spilling and reloading it.
How does an allocator get rid of the register-to-register moves, and when is recomputing cheaper than remembering?
The interference graph annotated with *copy* edges — pairs of nodes joined by a move instruction that would disappear if both ended up in the same register — plus, for each value, a note on whether it can be recomputed from operands that are still available. Neither annotation is about conflict; both are about opportunity, which is why they sit alongside the interference graph rather than inside it.
Two nodes joined by a copy may be merged only if they do not interfere — if they did, one register could not hold both. Merging is additionally unwise unless it is conservative: the merged node inherits the union of both nodes' edges, so an aggressive merge can turn a colourable graph into an uncolourable one, which is why Briggs's and George's rules exist. Rematerialization is legal only if recomputing the value at the use point produces the same value: its operands must still be live and unchanged there, the computation must have no side effects, and it must not be able to trap where the original could not.
Key points
- Copies are manufactured by the backend — out-of-SSA phi resolution, two-address instruction selection, ABI argument shuffles — not written by programmers.
- Coalescing merges the two ends of a copy into one node when they do not interfere, and the copy disappears.
- A merged node inherits the union of both neighbour sets, so aggressive coalescing can make a colourable graph uncolourable — trading a
movfor a spill. - Conservative rules (Briggs, George) merge only when colourability is provably preserved; freezing a copy is always preferable to spilling.
- Rematerialization recomputes a cheap value at each use instead of spilling it: constants, addresses, immutable loads, cheap arithmetic on still-live operands.
- Its legality condition is that the recomputation yields the same value, has no side effects, and cannot trap where the original could not.
- Both techniques depend on the compiler still knowing what a value is — information that allocation is about to destroy.
Where all the copies come from
Register-to-register moves are not something programmers write. They are manufactured by the backend, in three places, and in quantity.
Out-of-SSA is the biggest source: every phi becomes a set of copies at the ends of its predecessors, and a function with loops has phis for every loop-carried value. Two-address instruction selection is the second: d = a + b on x86-64 becomes mov d, a; add d, b, and that mov exists purely because the machine's arithmetic is destructive. Calling conventions are the third: moving arguments into the ABI-mandated registers is a shuffle that may need a temporary to break a cycle.
Coalescing removes them the right way. If the two ends of a copy do not interfere, merge their nodes in the interference graph — one node, the union of both sets of edges — and the copy becomes a move from a register to itself, which is to say nothing at all. Our backend gets the cheap version of this for free: when the allocator happens to give both ends the same register, the emitted mov X, X is deleted by the peephole. That is coalescing by luck; real coalescing makes it happen on purpose.
add rcx, rdx ; %5 = %4 + %2 mov rax, rcx ; %6 = %5 (from out-of-SSA) add rax, 1 ; %7 = %6 + 1
add rcx, rdx ; %5 = %4 + %2 add rcx, 1 ; %7 = %5 + 1, with %5 and %6 sharing rcx
Only if %5 and %6 do not interfere — that is, %5 is not read anywhere after %6 is defined. A copy whose source dies at the copy is the ideal case, since the two live ranges are adjacent rather than overlapping. Conservatively, the merged node must also still be colourable: Briggs's rule permits the merge only if the merged node has fewer than k neighbours of significant degree, and George's permits it only if every neighbour of one node either already interferes with the other or has degree below k.
If %5 is read again after %6 is defined, both values must exist simultaneously and cannot share a register — merging them destroys one. And even when they do not interfere, an unconstrained merge can be a mistake: the merged node carries the union of both neighbour sets, and a graph that was colourable before the merge may not be after it. Aggressive coalescing that ignores this trades a deleted mov for a spill, which is a bad exchange.
Why coalescing is not obviously good
mov X, X. That is worth knowing when reading our output: surviving moves in it are not evidence about what a real allocator would do.Removing an instruction sounds unambiguously positive, which is why the failure mode surprises people. Merging two nodes produces a node whose neighbour set is the union of both. Its degree is therefore at least as large as either original and usually larger, and degree is exactly what determines colourability. Merge enough copies and the graph acquires a cluster of very-high-degree nodes that will not colour, and the allocator spills. Trading one mov for a load and a store per use is a clear loss.
The response, developed through the 1990s, is *conservative* coalescing: merge only when it is provable that the merged node is still colourable. Briggs's rule allows the merge when the merged node has fewer than k neighbours of significant degree. George's rule allows it when every neighbour of one node either already interferes with the other or has degree below k. Both are sufficient conditions rather than exact tests, and production allocators apply them together and iteratively, alternating with simplification.
The other half of the answer is *freezing*. When simplification is stuck and coalescing is blocked, an allocator can give up on a specific copy — mark it un-coalescable, which frees its two nodes to be simplified separately — rather than spilling. Freezing before spilling is the standard ordering, because keeping a mov is always cheaper than a spill.
| Strategy | Rule | Cost |
|---|---|---|
| None | Copies survive unless the allocator coincidentally assigns the same register | Thousands of surviving moves; decode bandwidth and code size |
| Aggressive | Merge any non-interfering copy | Can make a colourable graph uncolourable, trading a mov for a spill |
| Conservative (Briggs) | Merge if the merged node has fewer than k neighbours of significant degree | Misses some safe merges; never causes a spill |
| Conservative (George) | Merge if every neighbour of one node interferes with the other or has degree below k | Complementary to Briggs; the two are usually applied together |
| Iterated with freezing | Alternate simplify, coalesce, and freeze a copy when stuck, before ever spilling | More passes over the graph; the standard production answer |
Rematerialization: recompute instead of remember
The second technique attacks spilling rather than copying. If a value is cheap to recompute and its inputs are still available, then instead of storing it to a stack slot and loading it back, the allocator can simply recompute it at each use. A constant is the clearest case: mov rax, 42 at the use costs one instruction, exactly the same as the reload it replaces — but it needs no stack slot, no store after the definition, and no memory port.
The candidates are narrow and worth naming. Constants. Addresses of globals and of stack slots, which are a lea or an immediate. The result of a load from memory known to be immutable — a constant pool entry, a vtable slot in a language where those cannot change. A cheap arithmetic operation on values that are still live at the use. What all of these share is that the recomputation costs about as much as the reload and eliminates everything else about the spill.
The legality condition is where care is needed, and it is the same shape as every other legality condition in this domain. The operands must still hold the same values at the use point — which is exactly what SSA makes checkable, since a value in SSA has one definition and cannot have changed. The computation must have no side effects. And it must not be able to trap where the original could not: rematerializing a division at a point where the divisor might be zero introduces a fault the program did not have.
; %3 = 1000, spilled mov qword [rbp-16], 1000 ; store after the definition ... mov rax, [rbp-16] ; reload before each use add rcx, rax
; %3 = 1000, rematerialized ... add rcx, 1000 ; recomputed — here, folded into the operand entirely
Only if the value can be recomputed at the use point to exactly the same result: its operands are still live and unchanged there (guaranteed for an SSA value whose definition dominates the use), the computation is side-effect-free, and it cannot trap where the original definition could not. A literal constant satisfies all three trivially, which is why constants are the canonical case.
If the value came from a load whose memory could have been written between the definition and the use — the recomputed load may read a different value. If the computation can trap: rematerializing a / b at a use reached only when b is known non-zero, from a definition point where that was also known, is fine; hoisting it to a point where b may be zero introduces a fault. And it is a pessimization rather than an error if the recomputation is more expensive than the reload, which is why the candidate list is restricted to genuinely cheap operations.
Both are the same idea
Coalescing and rematerialization look unrelated and are two answers to one question: what is the cheapest way to make this value available where it is needed? Coalescing answers "put it where it already is" — merge the storage so no movement is needed at all. Rematerialization answers "do not move it, make another one".
Both are enabled by the same property, which is that the compiler knows what a value *is* and not merely where it sits. That is exactly what SSA provides and what allocation is about to destroy: after allocation there is no %3, only a register that holds different things at different times. Doing this work before that information is lost is not an accident of pass ordering; it is the reason the ordering is what it is.
How it works
The steps, in the order the compiler takes them.
- Annotate the interference graph with copy edges: pairs of nodes joined by a move instruction.
- For each copy edge whose endpoints do not interfere, test a conservative rule — Briggs's neighbour-degree bound or George's neighbour-containment condition.
- If the rule holds, merge the two nodes into one carrying the union of their edges, and delete the copy.
- When simplification stalls and no coalescing is permitted, freeze a copy — abandon merging it — and resume simplifying before considering any spill.
- For rematerialization, mark values whose definition is cheap and whose operands remain available: constants, address computations, immutable loads.
- When such a value would spill, insert a recomputation before each use instead of a store-and-reload pair, and remove its stack slot entirely.
How it breaks
What the engineer observes when it goes wrong — not what goes wrong internally.
- Coalescing is applied aggressively, the merged nodes push the graph past colourability, and the function spills where it previously did not. The generated code is slower after an optimization that removed instructions.
- A copy is coalesced whose endpoints do interfere — because interference was under-computed — and one of the two values is silently destroyed.
- No coalescing is performed at all, and the output is dense with register-to-register moves that consume decode bandwidth and code size even though the hardware eliminates most of them at rename.
- A load is rematerialized across a store that may alias, and the recomputed value differs from the original. The bug appears only when the two pointers actually overlap.
- A trapping operation is rematerialized to a point where its operands are not known safe, and the program faults on input that previously worked.
- Rematerialization is applied to something expensive, and a hot loop recomputes at every use what it should have loaded once.
When it helps
- Any backend that leaves SSA before allocation, which is most of them — the phi copies alone justify coalescing.
- Two-address targets such as x86-64, where instruction selection generates a copy for every three-address arithmetic operation.
- Code with many constants and address computations, where rematerialization eliminates spills outright rather than making them cheaper.
- High-pressure loops, where every register recovered is a spill avoided.
When it hurts
- When coalescing is unconstrained: the merged nodes' degrees rise and the graph stops colouring, which costs far more than the copies saved.
- When rematerialization is applied to anything but genuinely cheap computations, turning one reload into repeated work at every use.
- In debug builds, where merging two source-level values into one register makes both harder to report accurately.
What it costs
Every one of these is paid by something.
- Coalescing buys deleted instructions and one fewer live value, and costs graph density — every merge raises a node's degree and moves the graph closer to needing a spill.
- Conservative coalescing buys a guarantee that no merge causes a spill and costs the merges that were safe but unprovable, leaving copies that a bolder allocator would have removed.
- Rematerialization buys the elimination of a stack slot and the store that fills it, and costs repeated computation at every use — profitable only while the recomputation is at most as expensive as the reload it replaces.
What else you could do
What a different compiler or language does instead, and when that is better.
- Copy propagation on the machine IR before allocation removes some copies without touching the graph, and misses the ones that only become removable once registers are known.
- Leave the copies and rely on the hardware: modern x86 cores eliminate register-to-register moves at rename, so a surviving
movcosts decode bandwidth and code size but no execution resource. Compilers remove them anyway because those two costs are real. - SSA-based allocation, where the chordality of the interference graph makes it possible to decide coalescing and colouring with better guarantees than the classical conservative rules provide.
- Live-range splitting is the dual technique: coalescing merges ranges to remove copies, splitting divides them to reduce pressure, and a good allocator does both — see
[[spilling]].
See it for yourself
The flag, dump or tool that shows you this directly.
- LLVM's coalescer:
llc -print-after=simple-register-coalescing file.llshows the machine IR after copies have been merged. - Count what it removed:
llc -stats file.ll 2>&1 | grep -i coalesc. - Rematerialization in LLVM:
-statsalso reports rematerialized values, andllc -print-after=virtregrewritershows constants reconstituted at use sites rather than reloaded. - GCC:
-fdump-rtl-irareports coalescing decisions as part of the allocator dump. - Ours:
src/compilers/sim/codegen.tsperforms neither. It emitsmov X, Xwhen the allocator happens to assign both ends of a copy the same register, and the peephole filter deletes it — coalescing by coincidence, and labelled as such at/compilers/registers.
Plausible wrong readings
Stated the way a confident engineer states them.
- "Removing an instruction cannot make the code slower." Coalescing removes a
movand raises a node's degree. If that pushes the graph past colourability, the removedmovis replaced by a spill, which is much worse. - "Rematerialization is just constant folding." Folding evaluates at compile time and replaces the expression. Rematerialization keeps the computation and moves *copies of it* to the use sites, specifically to avoid occupying storage in between.
- "Coalescing is done by the peephole." A peephole can delete a
movfrom a register to itself. It cannot cause both ends of a copy to be assigned the same register, which is the part that does the work. - "The moves in unoptimized output are the programmer's fault." They come from phi resolution, from two-address instruction shapes, and from calling conventions. None of the three is visible in the source.
Misconceptions
The claim, and what is actually true.
Go deeper
The same idea at increasing depth. Stop wherever it stops being useful.
overview
Backends generate a lot of instructions that just move a value from one register to another. If the two registers could be the same register, the move disappears — that is coalescing. Separately, when a value would have to be pushed out to memory, sometimes it is cheaper to just compute it again wherever it is needed, especially if it is a constant. That is rematerialization. Both are ways of not paying for storage.
practical
You will mostly meet this as an explanation for something you see. Unoptimized x86-64 output is full of mov instructions between registers, and they come from phi resolution and from two-operand arithmetic rather than from anything in the source. In optimized output they are largely gone, and the mechanism that removed them is the allocator deliberately assigning both ends of each copy to the same register — not a later cleanup pass.
advanced
The instructive thing here is that coalescing is a genuinely two-sided optimization, which is rare. Almost every transformation in a compiler is "good unless the budget says otherwise"; coalescing can directly cause the failure of the phase it is embedded in, by raising node degrees past colourability. That is why the literature on it is about *restraint* — Briggs's and George's conditions are both sufficient conditions for safety rather than tests for profit, and freezing exists so that the allocator can abandon a merge rather than escalate to a spill. The general principle worth taking away is that an optimization operating inside a constrained resource allocation cannot be evaluated locally: removing an instruction is not obviously good if it consumes the resource that something more expensive was relying on.
How much this depends on
Nothing in this domain is true of every compiler. These say how much.
mov X, X that its peephole deletes arises when the allocator independently assigns both ends of a copy the same register — coalescing by coincidence, not by decision. Surviving moves in our output say nothing about what a coalescing allocator would produce.If you were asked this in an interview
- Why can coalescing a copy make the generated code worse?
- What must be true for a value to be rematerialized rather than spilled?
- Where do all the register-to-register moves in unoptimized x86-64 output come from?