Liveness Analysis

A variable is live at a program point if its current value may still be read later. A register holding a dead variable can be reused; an assignment to a variable that is dead immediately afterwards is useless and can be deleted. Liveness therefore drives two of the most important back-end decisions: register allocation and dead-code elimination.

Liveness is the standard backward, may data-flow problem. Examination questions ask for live-in and live-out sets of blocks, for the variables live at a particular instruction, or for the minimum number of registers a code fragment needs without spilling, which follows from the live sets.

Scan each block forward. A variable read before it is written in the block goes into $use$; a variable written before it is read goes into $def$. A variable read first and written later is in $use$ only. A variable written first and read later is in $def$ only (the read sees the block's own value).

Edges: $B_1 \to B_2$, $B_2 \to B_2$, $B_2 \to B_3$.

In $B_2$, $a$ and $c$ are read before being written, so they are in $use$, not $def$; only $b$ is written first.

Iterating backward in the order $B_3, B_2, B_1$ (reverse postorder of the reversed flow graph, the usual order for a backward problem) from empty sets:

In pass 1, $OUT[B_2]$ is computed while $IN[B_2]$ is still empty, so the self-loop adds nothing yet; pass 2 adds $a$ and $N$ to $OUT[B_2]$ but changes no IN set. Pass 3 changes nothing, so three passes are made; a loop that stops as soon as no IN set changes stops after pass 2. The order changes the count, not the result: visiting $B_1, B_2, B_3$ leaves $IN[B_1]$ empty after pass 1, so the IN sets settle only in pass 2 and either test makes three passes. $c$ and $N$ are live on entry to the program: $N$ is an input, but $c$ is read before it is ever assigned, a use of an uninitialised variable that liveness exposes.

Live sets inside $B_2$, working backward from $OUT[B_2] = \{a, c, N\}$:

$a$ is dead between b = a + 1 and a = b * 2, and $b$ is dead outside that stretch, so $a$ and $b$ never interfere.

Build the interference graph: one node per variable (or per live range), and an edge between two nodes if one is defined where the other is live (apart from the defined one itself). A $k$-colouring of this graph is an assignment of $k$ registers with no conflicts (see Graph Colouring).

For Example 1, the interfering pairs are $\{a, c\}$, $\{a, N\}$, $\{b, c\}$, $\{b, N\}$ and $\{c, N\}$. The triangle $b, c, N$ needs 3 colours, and 3 suffice because $a$ and $b$ can share a register. The loop needs 3 registers without spilling.

The copy exception. For a copy x = y, no edge is added between $x$ and $y$ merely because $y$ is live after the copy: both hold the same value, so they may share a register, and the copy can then be deleted. An edge $\{x, y\}$ appears only if some other definition of one of them happens while the other is live.

Working backward from nothing live at the end:

At most 3 values are live at once, so 3 registers are needed, and 3 suffice if each value (each definition with its uses) may get its own register. Renaming the definitions, x1 = 4, y1 = x1 + 2, z1 = x1 * y1, w1 = y1 - 1, x2 = z1 + w1, y2 = x2 * z1, gives an interference graph with chromatic number 3.

A trap: if each source name must stay in one register for the whole block, x and y each cover two separate live ranges and the name-level interference graph becomes the complete graph on $w, x, y, z$, needing 4 registers. The value-based count is the usual reading of "minimum number of registers", but check the wording.

For straight-line code, the minimum number of registers without spilling equals the maximum number of simultaneously live values, since the live ranges are intervals and an interval graph's chromatic number equals its largest clique. With loops and branches the interference graph can need more colours than the largest live set.

Edges: $B_1 \to B_2$, $B_1 \to B_3$, $B_2 \to B_4$, $B_3 \to B_4$, $B_4 \to B_1$, $B_4 \to B_5$.

Visiting $B_5, B_4, B_3, B_2, B_1$, the first pass already gives these sets and the second confirms them. Points worth noticing:

The interfering pairs are $\{a, b\}$, $\{a, x\}$, $\{b, x\}$ (all three are live together at the end of $B_1$) and $\{b, c\}$. There is no edge $\{c, x\}$: when $B_4$ defines $x$, $c$ is dead, and when $c$ is defined, $x$ is not live. The triangle $a, b, x$ needs 3 colours, and $c$ can share a register with $a$ or $x$: 3 registers.

The live sets between instructions are $\emptyset$, $\{a\}$, $\{a, b\}$, $\{a, b\}$, $\{c\}$: never more than 2. But t = a * b writes $t$ while $a$ and $b$ are both still live, and $t$ is never read. Unless the dead assignment is deleted first, the machine needs a third register to receive $t$. In general the registers needed at an instruction are $\lvert live_{after} \cup \{x\}\rvert$ for its target $x$; the bound "maximum live" assumes that dead assignments have been removed. After deleting t = a * b, 2 registers suffice.

An assignment x = e (with no side effects in e) is dead if x is not live immediately after it. Deleting it can make other variables dead, so the analysis and deletion are repeated until nothing changes. In Example 1 nothing is dead: every assignment's target is live right after it.

Common misconceptions.