Live-Variable Analysis
A variable is live at a program point if the value it currently holds might be
used later — that is, if some path forward from here reads the variable before overwriting it.
If no such path exists, the variable is dead, and whatever we just stored in it was a
waste. Liveness is the mirror image of
reaching definitions:
where reaching definitions look back to ask "where did this value come from?", liveness looks
forward to ask "will this value ever be needed?". It is the second canonical instance of the
dataflow framework,
and its answers drive two of the most important back-end tasks: dead-code elimination and register
allocation.
Because the question is about the future, information flows backward through
the flow graph, against the direction of the edges. And because "used on some path" is enough
to keep a variable alive, the meet is union — liveness is a "may" analysis.
def and use, per block
Each block is summarised by two sets of variables (not definitions this time):
-
\text{use}_B — variables that are read in
B before being written in B
(upward-exposed uses). A use like the
a in b = a + 1 counts; but the
a in a = b*2; … if a<9 does not, because that read sees the
block's own earlier write.
-
\text{def}_B — variables assigned in
B. A definition breaks the forward flow of liveness: once
B writes x, whatever was live in
x beyond B no longer needs its old
value coming into B.
The dataflow equations are the backward mirror of reaching definitions — IN/OUT and pred/succ swap
places:
\text{IN}[B] \;=\; \text{use}_B \,\cup\, \big(\text{OUT}[B] - \text{def}_B\big), \qquad \text{OUT}[B] \;=\; \bigcup_{S \,\in\, \text{succ}(B)} \text{IN}[S].
The boundary condition sits at the exit: \text{OUT}[\text{EXIT}] = \varnothing
— nothing is live after the program ends (barring globals or return values, which are modelled as an
artificial use at EXIT). Every interior set starts at \varnothing and grows
to a fixed point.
A worked flow graph, read backward
Take a small loop over variables a, b, c. Blocks and their def/use sets:
B_1 a=0, B_2 b=a+1,
B_3 c=c+b, B_4 a=b*2; if a<9,
B_5 return c, with a back-edge B_4 \to B_2.
Reveal the live-OUT set that each block finally carries — reading from the exit upward:
Follow the logic at B_4. Its successors are B_5
(which needs c) and, round the back-edge, B_2
(which needs a — the loop counter — and c). So the
value of a that B_4 computes is live out of
B_4 only because of the back-edge. On the first backward pass we do
not yet know that a is live at B_2's entry, so
a is missing from \text{OUT}[B_4]; a second pass
adds it. That is the loop forcing iteration, exactly as before.
Iterating to a fixed point
Visiting blocks in reverse order B_5, B_4, B_3, B_2, B_1, here are the
live-OUT sets as they settle:
| Block (use / def) | OUT after pass 1 | OUT after pass 2 | Final |
|---|
| B_1 — def \{a\} | \{a,c\} | \{a,c\} | \{a,c\} |
| B_2 — use \{a\}, def \{b\} | \{b,c\} | \{b,c\} | \{b,c\} |
| B_3 — use \{b,c\}, def \{c\} | \{b,c\} | \{b,c\} | \{b,c\} |
| B_4 — use \{b\}, def \{a\} | \{c\} | \{a,c\} | \{a,c\} |
| B_5 — use \{c\} | \varnothing | \varnothing | \varnothing |
Only \text{OUT}[B_4] changes between the passes — gaining
a once the back-edge reveals that a is live at
B_2's entry. A third pass changes nothing, so we have converged.
A backward worklist solver
Liveness is another bit-vector problem, so variables become bits and the set algebra becomes bitwise
operations — but now the iteration runs backward: OUT is the union of successors' IN.
// Variables a, b, c map to bits 0, 1, 2.
const A = 1, B = 2, C = 4;
const fmt = (m: number): string => {
const out: string[] = [];
if (m & A) out.push("a");
if (m & B) out.push("b");
if (m & C) out.push("c");
return "{" + out.join(",") + "}";
};
interface Block { succ: number[]; use: number; def: number; }
// B1 a=0; B2 b=a+1; B3 c=c+b; B4 a=b*2, if a<9 -> B2; B5 return c.
const blocks: Block[] = [
{ succ: [1], use: 0, def: A }, // B1
{ succ: [2], use: A, def: B }, // B2
{ succ: [3], use: B | C, def: C }, // B3
{ succ: [1, 4], use: B, def: A }, // B4 (back-edge to B2)
{ succ: [], use: C, def: 0 }, // B5
];
const IN = blocks.map(() => 0);
const OUT = blocks.map(() => 0);
const order = blocks.map((_, i) => i).reverse(); // backward: visit exits first
let passes = 0, changed = true;
while (changed) {
changed = false; passes++;
for (const i of order) {
let outB = 0;
for (const s of blocks[i].succ) outB |= IN[s]; // OUT = union of successors' IN
OUT[i] = outB;
const inB = blocks[i].use | (outB & ~blocks[i].def); // IN = use ∪ (OUT − def)
if (inB !== IN[i]) { IN[i] = inB; changed = true; }
}
}
console.log(`fixed point after ${passes} passes`);
blocks.forEach((_, i) => console.log(`B${i + 1}: IN=${fmt(IN[i])} OUT=${fmt(OUT[i])}`));
The output matches the table: a appears in OUT[B4] only after the loop is
taken into account, and c is live almost everywhere because it is read at the very end and
threaded through the loop. Flip OUT = ∪ succ IN back to IN = ∪ pred OUT and
you would be computing reaching definitions — the two analyses are the same engine run in opposite
directions.
What liveness is for
-
Dead-code elimination. If a variable is assigned but not live immediately
after the assignment, the assignment is dead (assuming no side effects) and can be deleted. Repeating
this can cascade: deleting one dead store may make an earlier one dead too.
-
Register allocation. Two variables that are live at the same time cannot
share a register — they interfere. Liveness gives the interference graph, whose
colouring assigns variables to a limited set of registers. This is the single most important
consumer of liveness in a real compiler.
-
Building an accurate spill/reload picture and detecting some uses of uninitialised
values (a variable live at the procedure's entry was read before ever being written on some path).
Model each variable as a node. Draw an edge between two variables whenever they are simultaneously
live at some point — this is the interference graph, and liveness analysis is
exactly what tells you where two variables overlap. Now assign each variable a physical register such
that no two adjacent nodes get the same one: that is a graph colouring with
k colours, where k is the number of available
registers. If the graph is k-colourable, everything fits in registers; if
not, some variable must be spilled to memory. Chaitin's classic allocator does exactly
this, using the heuristic that any node with fewer than k neighbours can
always be coloured, so it is safe to remove and colour last. Without precise liveness the interference
graph would be far too dense, and you would spill variables that never actually conflicted.
Two traps sink students here. First, direction. Liveness flows backward: you begin at
EXIT with \text{OUT}[\text{EXIT}] = \varnothing and propagate upstream,
with \text{OUT}[B] built from successors' IN. Run it forward — or set
the boundary at ENTRY — and every result is wrong. Second, "may", not "must". A
variable is live if it is used on some future path, so the meet is union, not intersection. If
x is read on the then branch of an if but not the
else, it is still live before the branch — it might be needed. Using intersection would
declare it dead on the merged path and let dead-code elimination delete a store the program actually
depends on. Liveness deliberately over-approximates: keeping a variable that turns out unused
merely wastes a register, whereas dropping a live one is a miscompile.