Live-Variable Analysis and the Backward Direction of Dataflow

A variable is live at a program point if some path from that point reads its current value before overwriting it. The definition is negative — live means “not dead yet” — and that phrasing carries the whole content of the analysis. Liveness is the dual of reaching definitions: the same equations, run backwards along the control-flow graph, merging with intersection rather than union, and with definitions killing and uses generating.

The duality is exact enough that an implementation can share the fixpoint engine and change four things: direction, merge operator, initial value, and the roles of the gen and kill sets. What does not transfer is the intuition about which imprecision is safe, and that is where implementations go wrong.

Reading the equations backwards

For a block B, let UEVAR[B] be the variables used before being defined in B, and VARKILL[B] the variables defined anywhere in B. Then

LIVE_IN[B]  = UEVAR[B] ∪ (LIVE_OUT[B] − VARKILL[B])
LIVE_OUT[B] = ∪ LIVE_IN[S]  over successors S

The first equation is the transfer function, applied in the backward direction: information flows from the end of the block to its start. The second is the merge at a successor join. A variable is live on exit from B if it is live on entry to any successor, because one path that reads it is enough to make the value observable.

Initialisation is the empty set for every block, which is the least element in the subset order, and iterating upward from it computes the least fixpoint: the smallest set of live variables consistent with the equations. Starting from “everything is live” would compute a larger fixpoint, also valid, also useless, because it would mark every variable live everywhere and no optimization could act.

/* Backward worklist: information flows from uses to definitions. */
static void liveness(bb *blocks, int nblocks) {
    int queue[MAX_BLOCKS], qlen = 0, queued[MAX_BLOCKS] = {0};
    for (int i = 0; i < nblocks; i++) { queue[qlen++] = i; queued[i] = 1; }

    while (qlen > 0) {
        bb *b = &blocks[queue[--qlen]];
        queued[b->idx] = 0;

        vset out = union_of_succ_in(b);              /* meet over successors */
        vset in  = vset_or(b->uevar, vset_diff(out, b->varkill));

        b->live_out = out;                           /* consumers read this per block */
        if (vset_equal(&in, &b->live_in)) continue;
        b->live_in = in;

        for (int k = 0; k < b->npred; k++)           /* walk the edges backwards */
            if (!queued[b->pred[k]]) {
                queued[b->pred[k]] = 1;
                queue[qlen++] = b->pred[k];
            }
    }
}

The exit block has an empty LIVE_OUT unless the procedure has multiple returns, in which case every return is a successor of a synthetic exit node and the union is taken there. Blocks with no successors inside the procedure — calls to functions that do not return, infinite loops with no exit — need careful handling, because treating them as having an empty live-out will mark variables live that are in fact dead on every path that actually continues. The standard resolution is to delete unreachable blocks before the analysis and to give every remaining block at least one successor, so that an empty successor set never stands for an unreachable region.

The two flavours, and which one is sound

Textbook liveness is a may analysis: a variable is live if some path reads it. The alternative, must liveness, requires every path to read it. The distinction decides the legality of transformations, and the two are not interchangeable.

Dead-code elimination needs may-liveness. If a definition’s variable is not live on any path out of the definition, no execution observes the value, and the store can go. This is sound precisely because the analysis over-approximates: if the analysis says dead, it is dead on every path.

Register allocation needs may-liveness too, but for a different reason. Two variables interfere if their live ranges overlap, meaning there is a point where both are live. Over-approximating liveness creates spurious interference, which costs registers but never produces a wrong assignment. Under- approximating would let the allocator place two genuinely simultaneous values in one register.

Analyses of the must flavour appear in optimizations that move a computation. Hoisting a load out of a loop, for instance, requires the address to be valid on every iteration, not merely on the iterations that execute the load. That is a must property over the paths that enter the loop, and it is why hoisting is legal only when the loop is known to execute at least once or the operation is known not to trap.

A worked interference picture

Consider a loop body that computes t = a + b, uses t in a store, then recomputes t from different operands. May-liveness gives t a live range that starts at the first definition and ends at the last use before the second definition. The two ranges are disjoint, so the allocator can reuse the register. A naive analysis that treated every definition as reaching every later use would union the ranges and force two registers for a value that never needs to hold two live copies.

The same picture explains why liveness must be recomputed after transformations that change the CFG. Splitting a critical edge inserts a block and changes which successors a variable’s liveness flows through; running the allocator on stale liveness is a classic source of miscompiles in compilers that order their own passes incorrectly.

Precision limits that show up in practice

Liveness is flow-insensitive about when within a path the read happens, and this costs precision in three recurring ways.

Aliasing. A store through a pointer may write any variable whose address has escaped, so the store kills the liveness of everything address-taken. In C this is the common case for any variable passed by address to an opaque function, and it is why address-taken variables are the dominant source of imprecision in the sets that the allocator consumes. The same alias information that reaching definitions needs is needed here, as discussed in Reaching Definitions and the Monotone Dataflow Framework.

Aggregate and partial writes. Writing one field of a struct does not kill the liveness of the whole struct in a field-sensitive analysis, but a field-insensitive one must assume it does or does not, depending on direction. Most production analyses are field-insensitive at the dataflow level and rely on SSA plus scalar replacement to recover the field structure, the approach described in Escape Analysis and Scalar Replacement of Aggregates.

Exceptional and non-local control flow. A call that may throw or longjmp creates edges the CFG does not show, so variables live only along those edges are missed. Compilers that must preserve setjmp/longjmp semantics treat every call as a potential join point to the setjmp site, which conservatively keeps many values live. Languages with exceptions handle this by modelling the unwind path as explicit edges; the analysis then sees them, at the cost of a larger graph.

From liveness to what the allocator needs

The direct product is interference: for every program point, every pair of variables simultaneously live interferes. Building the graph naively is quadratic in the number of variables per point, which is why implementations either build it per block and merge, or derive it from SSA where each variable has a single definition and interference reduces to a dominance question. Chaitin’s original formulation built the graph from liveness sets; graph colouring then assigns registers, and spilling splits a variable into pieces with shorter ranges. The interference graph built here is the direct input to register assignment.

Liveness also gives a cheap proxy for register pressure: the maximum number of simultaneously live values in a region. Passes that increase pressure — aggressive unrolling, inlining large callees, hoisting many loads — can be rejected on that number alone, without running the allocator. This is the practical reason liveness is computed early and kept available rather than recomputed on demand.

One more structural note. Liveness on a CFG with n blocks and v variables is O(n · v) bits of state and converges in at most O(n · v) block visits in the worst case, but a sweep ordered so that each block is visited after its successors converges in a number of passes bounded by the loop nesting depth. The analysis is therefore cheap enough that it is normally run several times per compilation, once after each CFG-modifying pass, rather than cached across passes.