A variable is live at a point if its current value may still be read before it is overwritten. It is the classic backward, may dataflow: live_in = use ∪ (live_out − def), live_out = ∪ over successors of live_in, iterated to a fixpoint. It is the analysis that draws the interference graph for register allocation (dart 137): two variables interfere iff both are live at once.
THE TECHNIQUE sweep backward to a fixpoint
Facts flow from uses toward defs, so blocks are swept in reverse. Each block: live_in = use ∪ (live_out − def); a block’s live_out is the union of its successors’ live_in. Start empty at the exit, iterate until nothing changes. Below: a small program, variables a,b,c, solved to a fixpoint (sets shown as bitmasks). live demo
HISTORY & CREDIT Kildall unified it; he did not invent it
“Kildall invented dataflow analysis” — he inventedunified it (a lattice, monotone transfer functions, a fixpoint). Round-robin flow analysis ran in a Fortran compiler c.1961. cited
1961–63 · Vyssotsky & Wegner (Bell Labs) — the earliest dataflow inside a real compiler, flagging possibly-uninitialised variables (a liveness-flavoured check). 1969–71 · Frances Allen & John Cocke (IBM) build the CFG + interval optimisation substrate. 1973 · Gary Kildall — “A Unified Approach to Global Program Optimization” (POPL): the framework. Its four worked applications span forward problems (constant propagation, CSE, redundant loads) and a backward one — live-variable analysis, done by reversing the edges with an empty exit. What he did not invent is dataflow analysis itself. 1976–77 · Kam & Ullman generalise to monotone frameworks; the fixpoint gives the MFP, which equals the ideal meet-over-all-paths only for distributive frameworks.
Liveness JOINS with union from bottom (may); the boundary sits at the exit (live_out[exit]=∅). A loop’s back edge is exactly why one pass is not enough. Kildall, 1973
RECOMMEND FOR I-13 sets are bitmasks; the fixpoint is recursion
Variable sets are f64 bitmasks, the transfer function is use | (out & ~def) as bit ops, iterated to a fixpoint:
$ i13 run live.i13 # vars a=1 b=2 c=4 ; use / def per block ; backward
B0 use{} def{a} B1 use{a} def{b} B2 use{a,b} def{c} B3 use{c} def{}
live_in = [ {}=0 , {a}=1 , {a,b}=3 , {c}=4 ] (backward sweep to fixpoint)
Recommend:nothing new — a variable set is one f64 bitmask; use, def are per-block masks; the transfer live_in = use | (live_out − def) is bit-or and bit-and-not (x − (x & def)); successor union is bit-or; the backward sweep iterates to a fixpoint by recursion (verified live_in = [∅, {a}, {a,b}, {c}] = [0,1,3,4]). Note: it is the input to register allocation (dart 137) — two variables interfere exactly when both are live at some point, which builds the interference graph coloured next. A general CFG’s successor structure is a graph (adjacency), the corpus’s standing shape.