Dead-Code Elimination and Liveness Analysis

Liveness is a property of a variable at a specific program point: a variable `v` is live at point `p` if there exists some path in the control-flow graph (CFG) from `p` to a use of `v`, along which `v` is not redefined first. Liveness is inherently a backward question — whether `v` is live at `p` depends on what the program does after `p`, so information must be propagated from later points to earlier ones. This is the opposite flow direction from an analysis like reaching definitions, which propagates forward. Liveness is computed per CFG node (basic block or individual instruction) using two local sets. `use[n]` is the set of variables read in `n` before any local redefinition — variables `n` needs as input. `def[n]` is the set of variables assigned in `n`. The data-flow equations, instantiated from the general Data-Flow Analysis Framework, are: ``` IN[n] = use[n] ∪ (OUT[n] − def[n]) OUT[n] = ∪ (IN[s] for each successor s of n) ``` This is a may analysis (union at merge points, not intersection), because a variable is live if it is used along any possible future path, not all of them. The transfer function is monotone and the lattice (subsets of the variable universe, ordered by inclusion) has finite height, which is exactly what the general framework requires for a fixpoint to exist and be computable by iteration.

Dead-code elimination consumes the OUT-sets produced by liveness. An assignment `v = e` at point `p` is a candidate for deletion if `v ∉ OUT[p]` — no path forward reads `v` before it is redefined — and evaluating `e` has no observable side effect (no I/O, no memory write through a pointer, no exception that must be preserved, no volatile access). Removing such an instruction cannot change any observable behavior of the program, which is the correctness contract every optimization must uphold.

The overall pipeline has three phases: build the CFG and per-instruction `use`/`def` sets, run the backward fixpoint iteration to compute `IN`/`OUT` liveness sets at every point, then sweep the code deleting dead instructions — repeating, since deleting one dead instruction can make an operand of its definition dead in turn.

Step 1 — CFG and local sets. For each instruction (or basic block, for a coarser but cheaper analysis), compute `use` and `def` by simple syntactic inspection.

Step 2 — backward fixpoint. Initialize all `IN`/`OUT` sets to empty, then repeatedly apply the equations until nothing changes. Because it's a backward analysis, blocks are conventionally visited in reverse postorder of the CFG (i.e., postorder of the reverse CFG) for fast convergence, though any visitation order eventually reaches the same fixpoint.

Step 3 — dead-code sweep. Walk the code; delete any side-effect-free definition of a variable not in that point's `OUT` set. Because deletions change liveness, re-run liveness (or maintain it incrementally) until a full pass deletes nothing. ``` function LIVENESS(CFG): for each node n in CFG: IN[n] ← ∅ OUT[n] ← ∅ changed ← true while changed: changed ← false for each node n in reverse-postorder(reverse(CFG)): old_IN ← IN[n] OUT[n] ← ∪ { IN[s] : s ∈ succ(n) } IN[n] ← use[n] ∪ (OUT[n] − def[n]) if IN[n] ≠ old_IN: changed ← true return IN, OUT

function DEAD_CODE_ELIMINATION(CFG): (IN, OUT) ← LIVENESS(CFG) repeat removed ← false for each instruction i : "v = e" in CFG, in any order: if v ∉ OUT[i] and e has no side effect and v is not address-taken / volatile / observable: delete i from CFG removed ← true if removed: (IN, OUT) ← LIVENESS(CFG) -- recompute (or update incrementally) until not removed return CFG ``` A subtlety in `use`/`def` computation: for an instruction like `x = x + y`, the read of `x` on the right-hand side happens before the write, so `use = {x, y}`, `def = {x}` — never treat `x` as merely defined when it also appears as an operand. For an instruction with multiple destinations or a call that may both read and write through pointers (aliasing), `use` must conservatively include everything that might be read, since liveness is a may-analysis and under-approximating `use` breaks soundness.

The diagram shows exactly why `c = a + b` in `B1` is dead: liveness flows backward from the `return a` in `B3` and the `print(t)` in `B2`, and neither path ever needs `c`. Note `a` and `b` are live out of `B1`, so `a = 1` and `b = 2` survive — only the unused computation of `c` is removed.

Time complexity. Let the CFG have `N` nodes (blocks) and `E` edges, and let `V` be the number of distinct variables/temporaries. Each iteration of the outer loop visits every node once and does set operations costing `O(V)` (using bitvectors, a union or difference is `O(V/w)` machine words for word size `w`). The number of iterations is bounded by the height of the lattice, which for a "may" analysis with union as the join is at most `V` (each `IN[n]` can only grow, one bit at a time, before hitting the full set). So the naive bound is:

In practice, using reverse-postorder visitation on (structured, reducible) CFGs, the number of passes needed is bounded by the loop-nesting depth plus a small constant, so real compilers observe near-linear behavior, `O(N + E)` per pass with very few passes (often 2–3, even for large functions). This matches the general fact that data-flow analyses with distributive transfer functions (liveness's transfer function is distributive, not just monotone) converge to the meet-over-all-paths solution in at most `d + 2` iterations, where `d` is a measure of graph depth (loop connectedness), for a suitable traversal order — a stronger and tighter bound than the raw lattice-height bound.

Space complexity. `O(N · V)` bits to store `IN` and `OUT` sets at every node (two bitvectors of length `V` per node), which is the dominant memory cost; local `use`/`def` sets add the same order.

Correctness argument. Three things must be shown: (1) the equations have a fixpoint, (2) iteration reaches it, (3) the fixpoint is a sound approximation to true liveness, and hence DCE is safe. Existence and reachability of the fixpoint. The lattice is the powerset of variables under `⊆`, a finite-height lattice; the transfer function `f(OUT) = use ∪ (OUT − def)` and the join `∪` are both monotone. By the Knaster–Tarski framework underlying the Data-Flow Analysis Framework, monotone functions on a finite-height lattice have a fixpoint, and starting from the bottom element (`∅`) and repeatedly applying monotone updates produces a strictly increasing chain (in the round it changes) that must stabilize within a bounded number of steps, since the sets can only grow and are capped at size `V`. Soundness relative to true liveness. True (meet-over-all-paths) liveness is defined as: `v` is live at `p` iff some CFG path from `p` reaches a use of `v` with no intervening redefinition. One shows by induction on path length that the fixpoint computed by the algorithm equals exactly this set — not merely an over-approximation — because liveness's transfer functions are distributive: `f(A ∪ B) = f(A) ∪ f(B)`. Distributivity means the iterative (maximum fixpoint) solution coincides precisely with the meet-over-all-paths solution; there is no precision loss from merging at join points, unlike analyses with only monotone (non-distributive) transfer functions. Safety of deletion. If `v ∉ OUT[p]` for the point right after instruction `i: v = e`, then by the soundness result above, no path from `p` reads `v` before it is overwritten. Removing `i` therefore cannot change the value observed by any future read of any variable (since no future read of `v` along any executable path exists), provided `e`'s evaluation itself has no side effect. This is precisely the condition guarded in the pseudocode.

Tradeoffs. Per-instruction granularity gives maximal precision (finds dead code inside a block) but costs more memory and bookkeeping than per-block granularity, which only tracks liveness at block boundaries and locally recomputes within a block. Iterating DCE with liveness recomputation to a fixpoint is more thorough but costs extra passes; production compilers typically bound the number of DCE+liveness rounds or interleave it with other cleanups (copy propagation, constant folding) so that newly-dead code surfaces incrementally rather than requiring full re-analysis every time.

Consider this small function (three-address code), computing a factorial-like loop, with one genuinely dead computation buried inside: ``` B0: n = input() acc = 1 dbg = n 2 ; computed but never used goto B1 B1: if n <= 1 goto B3 B2: acc = acc n n = n - 1 goto B1 B3: return acc ``` CFG: `B0 → B1`, `B1 → B2` and `B1 → B3`, `B2 → B1` (a loop).

Local sets:

Backward fixpoint iteration (processing in reverse-postorder of the reverse CFG: `B3, B2, B1, B0`, iterating to convergence): Round 1:

• `OUT[B3] = ∅` (exit block, no successors) → `IN[B3] = {acc} ∪ (∅ − ∅) = {acc}`
• `OUT[B2] = IN[B1] = ∅` (not yet computed) → `IN[B2] = {acc,n} ∪ (∅ − {acc,n}) = {acc,n}`
• `OUT[B1] = IN[B2] ∪ IN[B3] = {acc,n} ∪ {acc} = {acc,n}` → `IN[B1] = {n} ∪ ({acc,n} − ∅) = {acc,n}`
• `OUT[B0] = IN[B1] = {acc,n}` → `IN[B0] = {} ∪ ({acc,n} − {n,acc,dbg}) = {}`

Round 2 (re-visit since `IN[B1]` changed after `B2` was computed using a stale value):

• `OUT[B2] = IN[B1] = {acc,n}` → `IN[B2] = {acc,n} ∪ ({acc,n} − {acc,n}) = {acc,n}` — unchanged.
• `OUT[B1]`, `IN[B1]` unchanged. `OUT[B0]`, `IN[B0]` unchanged.

No further changes — fixpoint reached in 2 rounds (matching the expected small constant, here driven by one loop back-edge).

Result: `OUT[B0] = {acc, n}`. Check each definition in `B0`:

Only `dbg = n 2` is removed. Note `n = input()` defines a variable that is* live, but even if it weren't, it would be kept because `input()` has an observable side effect — a case the naive rule "delete if unused" would get wrong without the side-effect guard. After deletion, liveness is recomputed (here it doesn't change further, since `dbg` contributed nothing to any `use` set), and the sweep terminates with no more dead code found.

Liveness analysis and dead-code elimination grew out of the broader development of systematic data-flow analysis for optimizing compilers in the 1960s–70s, formalized with lattice-theoretic rigor once the connection to fixpoint theory (via Data-Flow Analysis Framework) was made explicit.

Every mainstream optimizing compiler — GCC, LLVM/Clang, the JVM's JIT (HotSpot's C2), .NET's RyuJIT, V8's TurboFan — runs liveness analysis and dead-code elimination as core, repeatedly-applied passes. Liveness is not only used for DCE: it is the direct input to register allocation, since two variables can share a register only if they are never simultaneously live (this is the interference-graph construction in Chaitin-style allocators). It also underlies dead store elimination (removing a write that is immediately overwritten with no intervening read), which matters heavily in tight numerical and systems code. In JIT compilers, cheap approximate liveness runs at every optimization tier because compile time itself is a runtime cost; ahead-of-time compilers like LLVM can afford more precise, iterative versions. Static analysis tools and linters reuse the same machinery to warn about "unused variable" and "unreachable code" diagnostics. The concept generalizes beyond compilers: liveness-style backward reachability appears in garbage collection (an object is "live" if reachable from a future use, closely paralleling variable liveness), in dependency-driven build systems, and in dataflow-based security analyses (taint tracking runs a structurally similar, though forward, analysis). The natural next step in a compiler's optimization pipeline is transforming the program into Static Single Assignment (SSA) Form, where each variable has exactly one definition, making liveness ranges contiguous and the interference graph for register allocation dramatically cheaper to build and reason about.

Ask the tutor: How does liveness analysis change when a variable's address is taken and passed to another function?