Live Ranges
A value is live from its definition to its last use, and two values can share a register exactly when their ranges do not overlap. Our engine models ranges without holes — a real simplification, and this lesson says what it costs.
How does a compiler know when a value stops mattering?
A liveness solution over the CFG — for every program point, the set of values that have been defined and will still be read — collapsed into one interval per value over a linearised instruction order. The interval form exists because it is far cheaper to compare than the set form: overlap becomes two integer comparisons rather than a set intersection at every point.
The allocator is entitled to assume a value is dead after the last point at which liveness says it is live, and to reuse its storage from that point on. That assumption is only sound if liveness was computed to a fixed point over *all* paths, including back edges: a value that appears dead at the end of a loop body but is read at the top of the next iteration is live across the back edge, and an analysis that stopped after one pass would not know it. Liveness must also be conservative wherever it is uncertain — reporting a dead value as live wastes a register, while reporting a live value as dead corrupts the program.
Key points
- Liveness is a backward data-flow analysis iterated to a fixed point; the loop case is what makes iteration necessary.
- A live range is the interval from a value's definition to its last use, and overlap of intervals is what forbids sharing a register.
- The peak number of overlapping ranges is the function's minimum register demand, and the honest baseline for judging an allocation.
- Real live ranges have holes. Ours do not, which over-reports interference, over-estimates pressure and makes linear scan pessimistic.
- The over-approximation is deliberately in the safe direction: wasting a register is a cost, freeing a live one is a miscompilation.
- Phi operands are live at the end of their predecessor, not at the phi, and everything live out of a block is live to that block's terminator.
Backwards, to a fixed point
Liveness is a *backward* analysis, and the direction is not an implementation detail. The question "will this value be read again" is about the future, so information flows from uses back towards definitions: a value is live on entry to a block if the block reads it before writing it, or if it is live on entry to any successor and the block does not overwrite it.
Written that way it is one instance of [[data-flow-framework]], with the same machinery as every other: transfer functions per block, a meet operator (union, here, because a value live on *any* successor path is live), and iteration until nothing changes. Our implementation in regalloc.ts walks blocks in reverse order because a backward analysis converges faster that way — correctness does not depend on the order, only speed, which is true of every data-flow analysis.
The loop case is what forces the iteration. In a loop, a value defined in the body and used at the top of the next iteration must be live across the back edge, and you only discover that after processing the header once and coming back. Termination is the standard monotone-framework argument: the sets only grow, and the set of values is finite.
▸%0 = param 0 ; a▸%1 = param 1 ; b▸%2 = %0 * %1▸%3 = %0 + %1▸%4 = %2 - %3▸%5 = %4 * 2▸%6 = %5 + %2▸ret %6
Read it asRead it looking only for last uses. %0 and %1 are both read for the final time at point 3, so both are dead from point 4 onward and their registers are available. %2 is defined at point 2 and not read again until point 6, which makes it the longest-lived value in the function despite doing the least work in between.
One interval per value
The liveness solution is a set per program point, which is precise and awkward. Collapsing it into one interval per value — first definition to last use over a linear ordering of the instructions — trades precision for a representation in which "do these two conflict" is a.from <= b.to && b.from <= a.to. That is the trade every allocator makes before it does anything else.
The chart below is our engine's output for the IR above, given four registers. Four is the peak number of simultaneously live values, so nothing spills; give it three and %2 goes to memory, which is the chart in [[register-allocation]]. Notice %4 receiving rax at point 4: %1 held rax until point 3 and is dead afterwards, so the register is free. Every reuse in the chart is a live range that ended.
Read it asCount the bars crossing each column. Point 3 has four; every other point has three or fewer. That maximum is the function's register demand, and it is exactly why four registers suffice and three do not. It is also the number our engine reports as minimumRegisters, so a reader can distinguish a weak allocation from a demanding program.
The hole we do not model, and what it costs
Here is our engine's honest limitation. A real live range is not one interval; it is a set of intervals with *holes*. Consider a value defined at the top of a function, not touched at all through a long branch, and read once at the bottom. Its liveness is genuinely empty through the middle — nothing reads it there, and if it were spilled and reloaded around the region the program would behave identically. A precise allocator represents that as two intervals with a hole between them and hands the register to something else in the gap.
Our engine stores one from and one to per value and therefore has no way to express the hole. The consequences are specific rather than vague. Interference is over-reported: two values whose real live regions are disjoint but whose spans overlap are recorded as conflicting, so the interference graph has edges it should not. Peak pressure is over-estimated, so minimumRegisters reports a number that is an upper bound on the true demand. And linear scan becomes *pessimistic* in exactly the way its critics describe: an interval is held from its first to its last touch whether or not anything happens in between, so a long-lived, rarely-used value blocks a register for its whole span.
This matters for reading our simulator honestly, and it also happens to be the reason live-range *splitting* exists in production allocators. Splitting deliberately breaks one long range into several short ones with copies between them, which converts a hole you cannot exploit into two ranges you can. Our engine does not split either, which is the same limitation seen from the other side.
| Question | Our engine | A production allocator |
|---|---|---|
| Is this value live at point p?simplified | from <= p <= to — one comparison | Search a sorted list of sub-intervals |
| Value untouched through a long regionsimplified | Still occupies its register throughout | Hole in the interval; the register is reused there |
| Reported peak pressuresimplified | An upper bound — may exceed the true demand | The true simultaneous liveness |
| Interference edgessimplified | Over-approximated; some edges are spurious | Exact for the chosen program-point granularity |
| Effect on linear scansimplified | Pessimistic: a long sparse interval blocks a register for its whole span | The gap is available, so fewer spills |
| Live-range splittingsimplified | Not implemented | Standard — split at high-pressure points and insert copies |
Where a range ends is not obvious
Two details in our implementation are worth naming because they are where naive liveness code goes wrong, and both are visible in regalloc.ts.
The first is phi operands. A phi node at the top of a block conceptually reads its operands, but not *there* — an operand belonging to predecessor P is live at the end of P, not at the phi. Treating it as used at the phi would extend every loop-carried value across the whole loop header, over-constraining the allocator for no reason. Our usesOf deliberately returns nothing for a phi and handles the operands when computing the predecessor's live-out set.
The second is block ends. Anything live *out* of a block must be recorded as live at least to that block's terminator, or a loop-carried value will look dead at the back edge and the allocator will cheerfully hand its register to something else. That one line — touching every live-out value at the terminator point — is the difference between an allocator that works on straight-line code and one that works on loops.
How it works
The steps, in the order the compiler takes them.
- Compute, per block, the values used before being defined (
gen) and the values defined (kill). - Iterate backwards:
live-out(B)is the union oflive-inof its successors, plus any phi operand in a successor that belongs to this edge;live-in(B)isgen(B)pluslive-out(B)minuskill(B). - Repeat until no set changes. Termination follows from the sets only growing over a finite value space.
- Linearise the instructions into a single sequence of program points, so each value can be given one
fromand oneto. - For each value, record the first point at which it is defined and the last point at which it is read, and additionally extend to a block's terminator anything live out of that block.
- Count the uses along the way, and note whether the range spans a call — both are inputs to the spill heuristic later.
How it breaks
What the engineer observes when it goes wrong — not what goes wrong internally.
- Liveness is computed in one pass rather than to a fixed point, a loop-carried value looks dead at the back edge, its register is reused, and the loop computes the wrong result from the second iteration on.
- A phi's operands are treated as used at the phi, every loop-carried value stretches across the header, pressure rises artificially and the function spills for no reason.
- A value live out of a block is not extended to the block's terminator, and the allocator hands its register away at the branch. The corruption only appears on the path that actually takes the back edge.
- A value whose address was taken is treated as an ordinary SSA value, and the allocator keeps it in a register while another pointer writes to its memory. The two copies diverge.
- The range model has no holes, a long-lived rarely-used value blocks a register through a hot region, and the function spills something that a splitting allocator would have kept.
When it helps
- Register allocation, which is entirely built on it — no liveness, no allocation.
- Dead-code elimination: a definition whose value is never live is unreachable work, which is the same analysis read for a different purpose — see
[[liveness-analysis]]and[[dead-code-elimination]]. - Garbage-collector stack maps: knowing which slots hold live references at a safepoint is a liveness question, and getting it wrong either leaks or collects a live object.
- Debug information: a variable's location entry is valid exactly over the region where its value is live in a given place.
When it hurts
- Very large functions, where the interference derived from liveness is quadratic in the number of simultaneously live values and both time and memory become the problem.
- Code with heavy aliasing, where liveness of memory-resident values is bounded by what
[[alias-analysis]]can prove and is therefore conservative to the point of uselessness.
What it costs
Every one of these is paid by something.
- One interval per value buys constant-time overlap tests and a compact representation, and costs precision — every hole in a real live range is lost, which shows up as spurious interference and unnecessary spills.
- Intervals with holes buy precision and cost a more complex data structure, a slower overlap test, and considerably more implementation surface in every phase that touches ranges.
- Computing liveness to a fixed point buys correctness on loops and costs a repeated pass over the CFG; short-cutting it does not make it faster in any way that matters, it makes it wrong.
What else you could do
What a different compiler or language does instead, and when that is better.
- SSA-based liveness, which exploits the property that in strict SSA a value is live only within its definition's dominance region, allowing liveness to be computed without iteration at all.
- Live sets per program point, kept as bitvectors and never collapsed to intervals: maximum precision, and the memory cost is the number of points times the number of values.
- Live-range splitting: keep intervals but deliberately cut them at high-pressure points, inserting copies, so that a long range becomes several short ones. This is how production allocators recover most of what holes would have given them.
- Skip liveness entirely and keep everything in memory, as
-O0effectively does. Correct, slow, and maximally debuggable.
See it for yourself
The flag, dump or tool that shows you this directly.
- LLVM's live intervals:
llc -debug-only=regalloc file.llprints each virtual register's interval, including its holes, before allocation (needs a debug build). - The pressure directly:
llc -debug-only=machine-schedulerprints register-pressure sets while scheduling, which is liveness counted per point. - GCC:
-fdump-rtl-iraincludes the live ranges the integrated register allocator computed. - Ours:
livenessandliveRangesinsrc/compilers/sim/regalloc.ts, both exported and both exercised byscripts/compilers-sim.test.ts; the chart at/compilers/registersis their output.
Plausible wrong readings
Stated the way a confident engineer states them.
- "A variable is live for its whole scope." Scope is a source-level, lexical notion. Liveness is a data-flow notion about whether the value will be read again, and a variable in scope for fifty lines may be live for two.
- "Liveness is forward, because values flow forward." The value flows forward; the *question* is about future uses, so the analysis runs backward. Reaching definitions is the forward counterpart.
- "A value is dead after its last textual use." After its last *dynamic* use on every path, which on a loop back edge is not the same as the last line in the body.
- "A live range is one interval." It is one interval in our engine and in classic linear scan. In a precise allocator it is a set of intervals with holes, and the holes are where the extra registers come from.
Misconceptions
The claim, and what is actually true.
Go deeper
The same idea at increasing depth. Stop wherever it stops being useful.
overview
A value matters from the moment it is computed until the last time anything reads it. That span is its live range. Two values whose spans do not overlap can share the same register, because when the second one starts the first one no longer needs its storage. Finding the spans is what liveness analysis does, and it works backwards from uses because "will anyone read this again" is a question about the future.
practical
The practical consequence you will meet is the debugger saying "optimized out". That is liveness: the variable is in scope, its value is dead at that program point, and the register that held it has been given to something else. Shortening live ranges is also the most reliable source-level lever on register pressure — computing a value close to where it is used, rather than at the top of a function, genuinely reduces the number of things live at once.
advanced
The interesting question is granularity. Liveness is defined per program point, and the choice of what counts as a point — per instruction, per instruction with separate early and late slots, per basic block — changes both the precision and the cost by a large factor. Sub-instruction granularity is what lets an allocator see that a value dies at the same instruction where another is defined, so the two can share a register; block-level granularity misses that entirely and produces visibly worse code. Then there is the hole question, and then live-range splitting, which is best understood as deliberately manufacturing holes where the pressure is highest. All three are the same underlying trade: how much resolution you buy, and what you pay for it in analysis time on functions with thousands of values.
How much this depends on
Nothing in this domain is true of every compiler. These say how much.
from, one to, and everything in between is treated as occupied. Real allocators model a range as a set of intervals, which finds allocations ours cannot and makes linear scan meaningfully less pessimistic. The error is always conservative, so our allocations can be worse than necessary and cannot be wrong.LiveIntervals builds intervals directly from SSA definitions and uses rather than by running a separate backward analysis.If you were asked this in an interview
- Why is liveness a backward analysis, and what forces it to iterate?
- What is a hole in a live range, and what does an allocator that cannot represent one lose?
- A loop-carried value is corrupted from the second iteration onwards. Which part of the liveness computation would you suspect?