Liveness Analysis in Compiler Design: Data-Flow Equations and a Worked Example

A variable can hold a value yet be dead. Another may be live without appearing in the current statement because a later path reads it. Liveness analysis uses a control-flow graph, the USE, DEF, IN and OUT sets, and a fixed-point calculation to identify a genuinely dead assignment.

Related reading: liveness MCQs and SSA and control flow.

Liveness means a future use can still see the current value

A variable is live at a program point if at least one path uses its current value before redefining it. It is dead if no path can do so. Liveness concerns possible future use, not whether the variable contains a value or whether that value is non-zero.

This has two compiler uses. An assignment may be a dead store if its variable is not live immediately afterwards, provided removal preserves required side effects. Variables live at the same point also compete for registers, so liveness helps register allocation.

Liveness is a backward, may analysis. Backward means information travels from successors to predecessors. May means any successor path can keep a variable live. It belongs to later optimization, unlike top-down and bottom-up parsing in the compiler front end.

Liveness equations: compute USE, DEF, IN and OUT in order

A basic block is a straight-line sequence with one entry and one exit. A control-flow graph, or CFG, connects blocks that may execute consecutively. For every block B, liveness uses:

OUT[B] = union of IN[S] for every successor S of B
IN[B] = USE[B] union (OUT[B] - DEF[B])

USE[B] contains variables read before any definition in B. DEF[B] contains variables assigned in B. Statement order matters. In x = x + 1, the old x is read before the new one is written, so x belongs to both USE and DEF. In x = 1, it belongs to DEF but not USE.

Start with every IN and OUT set empty. Recompute all blocks from the previous round, then repeat until a complete round changes nothing. Code Optimization in Compiler Design: Basic Blocks, Data Flow and Worked Examples connects data flow to transformations and loop rewrites; liveness itself requires fixed-point propagation followed by statement-level tracing.

Worked example: solve a loop to a fixed point

Use this four-block program:

B1:
  i = 0
  sum = 0
  spare = 99
  goto B2

B2:
  if i < n goto B3 else goto B4

B3:
  sum = sum + a[i]
  i = i + 1
  goto B2

B4:
  avg = sum / n
  return avg

For a = [4, 7, 5] and n = 3, runtime takes sum from 0 to 4, then 11, then 16, and returns avg = 16/3. Liveness depends on uses and definitions, not these values.

The CFG edges are B1 -> B2, B2 -> B3, B2 -> B4 and B3 -> B2. B4 exits. The local sets are:

Now perform synchronous rounds, always reading the previous round's values.

• Round 0: Every IN and OUT is {}.

• Round 1: Because the previous OUT sets are empty, IN[B1] = {}, IN[B2] = {i, n}, IN[B3] = {sum, a, i} and IN[B4] = {sum, n}.

• Round 2: Successor information moves backwards. IN[B1] = {n}, IN[B2] = {sum, a, i, n}, IN[B3] = {sum, a, i, n} and IN[B4] = {sum, n}.

• Round 3: The loop information reaches the start, giving IN[B1] = {a, n}. The other three IN sets stay unchanged.

• Round 4: No IN or OUT set changes, so the fixed point has been reached.

The final result is:

Push the block result back to statements

Traverse B1 backwards from OUT[B1] = {sum, a, i, n}. After spare = 99, the live set is {sum, a, i, n}. spare is absent and the right-hand side has no side effect, so this store is dead. Before it, the set is unchanged.

Before sum = 0, the set becomes {a, i, n}. Before i = 0, it becomes {a, n}. The sum and i initialisations are not dead because their definitions reach the first loop test or body use before any guaranteed redefinition. The final IN[B1] also makes sense: a and n must arrive from outside, while B1 creates the initial i and sum values.

Liveness only proves that an assigned value is unused. Deleting spare = f() would require separate proof that evaluating f() has no required side effect or exception behaviour.

Avoid traps that produce plausible but wrong answers

1. Using intersection at a branch. At the fixed point, IN[B3] union IN[B4] = {sum, a, i, n}. Intersection gives only {sum, n}, incorrectly losing values needed on the loop-body path.

2. Scanning only once. Successor information must travel through the back-edge. A single backward round leaves IN[B1] = {}, although the fixed answer is {a, n}.

3. Ignoring statement order in USE. In B3, both sum and i are read before their new values are defined. Both therefore appear in USE[B3] and DEF[B3].

4. Reading live as definitely used. Liveness is a may analysis. One feasible successor path is enough.

5. Deleting every assignment missing from OUT. First check the expression for side effects and exception behaviour. The safe conclusion here is limited to the plain store spare = 99.

Turn the analysis into short exam-style checks

Try each question briefly before reading its answer.

1. What is OUT[B2]? It is {sum, a, i, n}, the union of IN[B3] and IN[B4].

2. What is IN[B1]? Subtracting DEF[B1] = {i, sum, spare} from OUT[B1] leaves {a, n}.

3. Which plain store is removable? spare = 99, subject to the side-effect condition.

4. What would intersection at the branch retain? {sum, n}. That is wrong because it drops variables required on one feasible successor path.

5. Which variables are both used and defined in B3? sum and i.

The short version and the next practical step

Use five steps: draw the blocks and successors, calculate ordered USE and DEF, initialise empty sets, apply the backward union equations until a round is unchanged, then inspect statement-level liveness before calling a store dead. In this example, remember IN[B1] = {a, n} and the dead plain store spare = 99.

For broader subject learning, continue through the CS Fundamentals category. Zero to Hero - Complete CS Course is an optional structured core-CS path, while GATE Guidance by Sanchit Sir is an optional route for a wider GATE CS plan.