Liveness Analysis
Is this value needed in the future? A backward, may analysis whose answer is the direct input to `[[register-allocation]]` — and the reason it must iterate is the back edge, where a loop-carried value has to stay live around a body that never mentions it.
How does a compiler know which values still matter at a given point, and why can it not work that out in a single pass?
The CFG annotated with, at the entry and exit of every block, the set of values that some future use will read before they are overwritten. It exists to answer the only question a register allocator actually needs: *which values must be simultaneously available here?* Two values whose live sets overlap cannot share a register, so this annotated graph is the direct input to the interference graph in [[interference-graph]].
Liveness must be a *may* analysis: a value is live if some path from here reads it before overwriting it, so the meet at a merge is union. The direction of safety is one-way. Reporting a value live when nothing reads it wastes a register. Reporting it dead when something reads it lets the allocator reuse its register, and the value is silently corrupted — no diagnostic, wrong answer far from the cause. The analysis is entitled to assume the CFG models every path, and must treat anything it cannot see — a call to unknown code, an exception edge — as potentially reading whatever it might reach.
Key points
- A value is live at a point if some path from there reads it before overwriting it — a question about the future, hence a backward analysis.
- Meet is union: needed on any successor path means needed here.
- Within a block, walk backwards — a use generates, a definition kills, and an instruction reads before it writes.
- A loop-carried value stays live across the whole body even where the body never mentions it, which is exactly why the analysis must iterate.
- Phi operands are live at the end of their predecessor, not at the phi; treating them otherwise over-constrains the allocator at the loop header.
- The output is the direct input to live ranges, interference and register pressure, and it decides what must survive a call.
- SSA does not remove the need for it, because the question is about program points rather than about values.
The question is about the future
A value is live at a point if there is a path from that point to a use of it, along which it is not first overwritten. That sentence is entirely about what happens *after* the point, so the analysis runs backwards. There is no forward formulation of it — see [[forward-vs-backward-analysis]] — and an attempt to build one produces reaching definitions, which answers a different question.
Within a block the rule is stated in terms of use and def: walking backwards, a use makes a value live and a definition kills it. Our engine's implementation is exactly that sentence — *walk the block backwards: a definition kills, a use generates* — and the order matters, because an instruction that both reads and writes a register reads it first.
At a block boundary, the live-out set is the union of the successors' live-in sets. Union, because the value only has to be needed on *one* successor path to require a register here.
1direction backward2meet union ("needed on some future path")3facts a set of values (virtual registers)4 5use[B] values read in B before being written in B6def[B] values written in B7out[B] union over successors S of in[S]8in[B] use[B] union (out[B] minus def[B])9 10boundary out[exit] = whatever the return reads, plus11 anything the ABI says survives the calluse[B] is "read before written in this block", not "read anywhere in this block". A block that writes %3 and then reads it does not need %3 live on entry.
A real analysis on a real loop
liveness() returns for this function at this commit. Two details are ours: a phi's operands are treated as live at the end of the corresponding *predecessor* rather than at the phi, which is why %5 is live-out of b2 and %7 is not live-in to b1; and the solver sweeps the block list in reverse rather than computing a true post-order. LLVM's live-interval representation additionally models holes, which ours does not.Here is liveness() from src/compilers/sim/regalloc.ts on a loop, and the case worth studying is %0 — the parameter k. It is read exactly once, in the loop header. The loop *body* never mentions it. And yet it must be live throughout the body, because after the body jumps back to the header, the header reads it again.
That is the loop-carried case, and it is why the analysis cannot be a single pass. Whatever order you visit blocks in, the body's live-out set depends on the header's live-in set, and the header's live-in set depends on the body's — the equations are mutually recursive around the back edge. The first sweep over the body necessarily uses a header live-in set that is not yet correct.
Concretely, our solver sweeps blocks in reverse order: b3, b2, b1, b0. On the first pass it processes b2 before b1, so b1's live-in is still empty and b2's live-out comes out as {%5} — the analysis believes %0 is dead in the loop body. On the second pass b1's live-in is {%0}, so b2's live-out becomes {%0, %5} and its live-in becomes {%0, %7}. The third pass changes nothing and the solver stops.
liveness()- b0entryentry
%0 = param 0 ; k jump b1
in {} / out {%0} - b1while.cond↺ loop header
%7 = phi n [0 from b0, %5 from b2] %3 = bool %7 < %0 branch %3 ? b2 : b3
in {%0} / out {%0, %7} — the phi defines %7, so it is not live-in - b2while.bodylatch
%5 = int %7 + 1 jump b1
in {%0, %7} / out {%0, %5} — %0 is live here despite never being mentioned - b3while.exit
ret %7
in {%7} / out {}
- b0→b1
- b1→b2
- b1→b3
- b2→b1
- b0idomb0(entry)
- b1idomb0
- b2idomb1
- b3idomb1
Read it asRead b2 twice. The instructions mention %7 and %5 and nothing else, yet %0 is in both its live-in and its live-out. That is the back edge doing its work: %0 must survive the body because the header will read it again on the next iteration. An allocator that trusted a single-pass answer would hand %0's register to something else inside the loop, and k would change value halfway through.
Phi operands are live at the predecessor
One detail in the sets above is worth its own paragraph, because it is a real design decision with a measurable consequence. A phi's operands are *not* used at the phi. They are used on the incoming edges, so they are live at the end of the corresponding predecessor and not at the top of the merge block.
Our engine says why in a comment: treating them as used at the phi would extend every loop-carried value across the whole header, which over-constrains the allocator. In the loop above, that is the difference between %5 being live only at the end of b2 and %5 being live across all of b1 as well — and in a loop with several carried variables that difference is several extra simultaneously-live values at the header, which is exactly where register pressure is already highest.
This is the liveness half of the same fact that [[phi-functions]] states about semantics: a phi describes an assignment that happens on an edge. The analysis has to agree with the semantics, or the allocator will make decisions the destruction pass cannot honour.
What the allocator does with it
rbx, rbp and r12-r15 survive a call and the rest do not; on AArch64 AAPCS it is x19-x28; on Windows x64 the split is different again. The liveness sets are target-independent; every decision made from them is not.The output feeds three things directly. Live ranges: the interval from a value's definition to its last use, which is what [[live-ranges]] charts. Interference: two values interfere when both are live at some program point, which builds the graph that [[graph-coloring-allocation]] colours. And pressure: the maximum number of simultaneously live values at any point, which is a lower bound on the registers needed and therefore tells you whether spilling is inevitable before any allocation is attempted.
It is also what decides which values must survive a call. A value live across a call site either lives in a callee-saved register or is spilled, because the callee is entitled to destroy the caller-saved ones. Our LiveRange carries a crossesCall flag for exactly this reason, and that flag is a [[calling-conventions]] question answered with liveness data.
Beyond allocation, the same analysis drives dead store elimination — a store to a location that is dead is removable — and the stack maps a garbage collector needs, where "which references are live at this safepoint" is the same question with references instead of registers.
The limits
Liveness is a may analysis, so it over-approximates: a value live on a path that never executes is still live. That costs a register and never correctness, which is the right direction for the error to go.
The bigger practical limitation in a simple implementation is *holes*. A value defined early, used once in the middle, and used again at the end is dead in between — but a live *interval* from first definition to last use has no way to say so. An allocator using intervals therefore keeps a register occupied through a region where the value is not needed. Real allocators model live ranges as sets of intervals with holes; ours does not, and says so, which makes our linear scan slightly pessimistic in exactly that case.
Finally, liveness is a question about program points rather than about values, which is why SSA does not make it go away. [[why-ssa-helps]] retires reaching definitions and constant propagation; liveness survives into every SSA backend unchanged, because "which values are simultaneously in flight *here*" is not something an operand name can encode.
How it works
The steps, in the order the compiler takes them.
- For each block compute
use— values read before being written in this block — anddef— values written in this block. - Initialise every exit block's live-out with whatever the return reads and whatever the ABI requires to survive, and every other block with the empty set.
- Iterate backwards: live-out is the union of the successors' live-in sets, plus, for each successor phi, the operand tagged with this block.
- Live-in is
useplus live-out minusdef; compute it by walking the block's instructions from last to first, deleting the definition and adding the uses. - Repeat until no block's sets change.
- Derive live ranges by scanning the linearised instruction order and recording, for each value, the first definition and the last point at which it is still in a live-out set.
- Build the interference graph by connecting every pair of values live at the same program point.
How it breaks
What the engineer observes when it goes wrong — not what goes wrong internally.
- The back edge is not modelled, or the analysis stops after one pass. A loop-carried value is reported dead inside the loop, the allocator reuses its register, and the loop produces wrong results after the first iteration — while a zero-iteration or one-iteration test passes.
- Phi operands are counted as used at the phi. Nothing is incorrect, but every loop-carried value is live across the header, pressure at the loop header rises, and a function spills that did not need to. The symptom is performance, not wrongness, and it is easy to blame on the allocator.
- A function has two returns and only one exit block is seeded. Values live only at the neglected return are reported dead, their registers are reused, and the function returns garbage on that path.
- The result is read as live-in where live-out was meant. Interference is computed against the wrong set, two overlapping values share a register, and a value is silently corrupted mid-function.
- A call is treated as not reading anything reachable. Values the callee needs are reported dead, and the corruption appears inside the callee, which is the hardest possible place to trace it back from.
When it helps
- Register allocation, without exception. No allocator of any design can work without it.
- Dead store elimination and dead code elimination in a non-SSA IR, where "nothing reads this" is precisely a liveness query.
- Emitting stack maps for a garbage collector or a deoptimization point, where the live set at a safepoint is what has to be described — see
[[deoptimization]]. - Diagnosing register pressure: the maximum live count at any point is a lower bound on registers needed, computable before attempting allocation.
When it hurts
- It never stops being needed, so the cost is unavoidable; what hurts is running it on very large functions with many values, where the sets and the rounds both grow.
- Interval-based approximations without holes, which report values live through regions where they are not needed and cause avoidable spills.
- Call-heavy code, where conservative assumptions about what a call reads inflate the live sets and force values into callee-saved registers or onto the stack.
What it costs
Every one of these is paid by something.
- Block-level live sets buy a cheap analysis with small memory; they pay precision inside a block, so an allocator wanting instruction-level detail has to walk the block again to recover it.
- Modelling live ranges as single intervals buys a simple allocator and fast linear scan; it pays holes — a value dead in the middle of its interval still occupies a register, which causes spills that a hole-aware allocator would avoid.
- Treating phi operands as live at the predecessor buys lower pressure at loop headers; it pays a special case in the analysis, and a bug there is a silent miscompilation rather than a slowdown.
- Conservative treatment of calls buys correctness without interprocedural information; it pays registers, because more values end up needing to survive a call than actually do.
What else you could do
What a different compiler or language does instead, and when that is better.
- Liveness on demand: rather than computing sets for the whole function, answer "is
%vlive at pointp?" by a backward walk fromp. Cheaper for a few queries, and an allocator asks about nearly everything, so it rarely wins there. - SSA-based liveness, which exploits the fact that a definition dominates all its uses: a value is live at a point exactly when the point is on a path from its definition to one of its uses, and that can be computed with dominance queries rather than a fixed point. Used in SSA-based allocators, and it is precise about holes almost for free.
- Live intervals with holes, as in LLVM's
LiveIntervals. Strictly more precise, more expensive to compute and maintain, and worth it under pressure — which is why production allocators use it and teaching ones do not. - Skip the analysis and use a fixed register assignment per variable, as a naive or debug-tier compiler does. Trivially correct, dramatically worse code, and instant — which is the right choice for
-O0.
See it for yourself
The flag, dump or tool that shows you this directly.
llc -debug-only=regalloc t.llprints live intervals and the allocator's decisions, including which values were spilled and why.llc -print-after=liveintervals t.llshows LLVM's interval representation, which is the hole-aware version of what this lesson computes.gcc -fdump-rtl-liveswrites the RTL-level liveness sets, which are readable and can be checked against a hand computation on a small function.- Our register-allocator interactive shows the live ranges, the interference graph and the peak pressure derived from
liveness()insrc/compilers/sim/regalloc.ts, on whatever AtlasLang you type.
Plausible wrong readings
Stated the way a confident engineer states them.
- "A value is live from its definition to its last use." That is the live *interval*, an approximation. A value is live only where a future use actually needs it, and the difference is the holes.
- "A value not mentioned in a block is dead there." The loop above is the counterexample:
%0is live in a block that never names it, because a later block will read it. - "SSA gives you liveness for free." SSA gives you use lists. Liveness is about program points, and an SSA backend still runs a real analysis — though it can use dominance to do it more cheaply.
- "If liveness is over-approximate, the code is just slower." Over-approximate is safe. Under-approximate is a corrupted value with no diagnostic, and the whole design of the analysis is arranged to err the safe way.
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 is live at a point if something is going to read it before anything overwrites it. Because that is a question about the future, the analysis runs backwards from the end of the function. Its answer tells the compiler which values need to be in registers at the same time, which is the input to register allocation.
practical
Two things to remember when reading real liveness output. A value can be live in a block that never mentions it — that is the normal case around a loop, not an anomaly. And the sets are block-level: an allocator that needs to know what is live between two specific instructions has to walk the block from its live-out set backwards. If you are debugging an allocator that corrupts a value, compute the liveness by hand for the two values that collided; it is usually faster than reading the allocator.
internals
Under SSA there is a cheaper formulation worth knowing. Because every definition dominates all its uses, a value is live at a point exactly when that point lies on some path from its definition to one of its uses — which means liveness can be answered with dominance queries and a walk up from each use, with no fixed point at all. This is the basis of SSA-based liveness and of SSA-based register allocation, and it comes with a bonus: the same walk naturally identifies holes, because it only marks the blocks actually between a definition and a use rather than everything in between textually. The reason the classical iterative version survives is that the backend destroys SSA before allocation in most compilers, so by the time liveness is needed the property that made the shortcut valid is gone. Compilers that allocate registers while still in SSA — exploiting the result that a strict SSA program's interference graph is chordal, and therefore optimally colourable in polynomial time — get the cheaper liveness as part of the same bargain.
How much this depends on
Nothing in this domain is true of every compiler. These say how much.
liveness() in src/compilers/sim/regalloc.ts on the SSA form of that function. Our solver uses a reverse round-robin sweep with an iteration guard, treats phi operands as live at the predecessor, and does not model holes. LLVM's LiveIntervals models holes and is correspondingly more precise under pressure.If you were asked this in an interview
- Is liveness forward or backward, and why does the question decide it?
- Show me a block where a value is live but never mentioned, and explain how the analysis discovers that.
- Why must the analysis iterate? Give the minimal program that forces a second round.
- Where are a phi node's operands live, and what does the other choice cost?
Connections
- Programming Languages & Runtime Internals — Stack maps and safepoints — what a collector scans when it stops the worldThe compiler computes which references are live at each safepoint using exactly this analysis and emits a map. What the collector does with that map, and how the safepoint protocol works at run time, is owned there.