Data-Flow Analysis
Almost every optimisation a compiler performs rests on a question of the form "what do I know about
the program's values at this point?" — is this variable definitely a constant here? is its current
value ever read again? has this expression already been computed on every path leading here?
Data-flow analysis is the single, unifying framework that answers all such questions.
It is one of the most powerful ideas in compiling precisely because it is not an optimisation but
the machinery underneath a whole family of them — reaching definitions, live variables, available
expressions, constant propagation — all the same algorithm with the pieces swapped out.
The setting is the
control-flow graph
of a function, and the currency is facts that flow along its edges. Each block transforms the
facts entering it into the facts leaving it; where edges merge, facts combine. Run that to a
fixed point and you have proved something true on every possible execution path — without
ever running the program.
The control-flow graph carries the facts
Recall the
CFG:
nodes are basic blocks (straight-line runs of
three-address code),
edges are the possible transfers of control. Data-flow analysis attaches to every block two sets of facts:
\textit{IN}[B], true on entry to B, and
\textit{OUT}[B], true on exit. A block relates them through its
transfer function, and the CFG's edges relate one block's output to the next block's
input. Solving the analysis means finding \textit{IN} and
\textit{OUT} for every block that are mutually consistent.
gen and kill: what a block produces and destroys
A block's transfer function is built from two constant sets that summarise what happens inside it:
- \textit{gen}[B] — the facts the block creates (e.g. for
reaching definitions, the definitions made in B that survive to its end).
- \textit{kill}[B] — the facts the block destroys (e.g.
definitions of a variable that B redefines, invalidating earlier ones).
- The block's output is what came in, minus what it killed, plus what it generated:
\textit{OUT}[B] = \textit{gen}[B]\cup(\textit{IN}[B]\setminus\textit{kill}[B]).
That single equation — generate, and pass through everything you didn't kill — is the transfer
function for a forward "may" analysis like reaching definitions. Swap in different notions of
\textit{gen}, \textit{kill}, and set operator and you
get a different analysis, but the shape never changes.
Direction and the meet operator
Two knobs specialise the framework. The first is direction. A
forward analysis pushes facts along the edges (a block's \textit{IN}
comes from its predecessors' \textit{OUT}s) — this is how reaching
definitions and available expressions work. A backward analysis pulls
facts against the edges (a block's \textit{OUT} comes from its successors'
\textit{IN}s) — this is how live-variable analysis works,
because whether a value is needed depends on the future.
The second knob is the meet (or join) operator — how facts combine where control-flow
paths merge. Union (\cup) gives a "may" analysis: a fact holds
if it holds on some incoming path (a definition may reach here). Intersection
(\cap) gives a "must" analysis: a fact holds only if it holds
on every incoming path (an expression is available only if computed on all paths). The
meet-over-all-paths solution is what we are really after; the iterative algorithm computes it.
| Analysis | Direction | Meet | Fact tracked | Enables |
|---|
| Reaching definitions | forward | \cup (may) | which defs reach a point | use-def chains, const prop |
| Live variables | backward | \cup (may) | values needed later | dead-code elim, allocation |
| Available expressions | forward | \cap (must) | expressions already computed | common-subexpr elim |
| Very busy expressions | backward | \cap (must) | exprs used on all future paths | code hoisting |
The iterative worklist algorithm
How do we solve the mutually-recursive \textit{IN}/\textit{OUT} equations? By
iterating to a fixed point. Initialise every set, then repeatedly recompute a block's
facts from its neighbours; when a block's output changes, its dependents might change too, so put them
back on a worklist. Keep going until nothing changes — the fixed point.
// Forward "may" analysis (reaching definitions).
OUT[B] = {} for all B ; worklist = all blocks
while worklist not empty:
pick B from worklist
IN[B] = union of OUT[P] for all predecessors P of B // meet
newOut = gen[B] ∪ (IN[B] − kill[B]) // transfer
if newOut ≠ OUT[B]:
OUT[B] = newOut
add all successors of B to the worklist // they may change
The worklist is just an efficiency trick — it avoids re-examining blocks whose inputs did not move.
Because facts are only ever added (the sets grow monotonically) and there are finitely many
possible facts, the loop must halt. Below, the same skeleton runs a real reaching-definitions analysis
on a small CFG with a loop.
Reaching definitions, worked in code
We solve reaching definitions for a four-block CFG — an entry, a loop head, a loop body (which redefines a
variable, killing the entry's definition), and an exit — and print the fixpoint
\textit{IN} sets.
type Block = { name: string; gen: string[]; kill: string[]; preds: string[] };
// d1: x defined in entry; d2: x defined in the loop body (d2 kills d1 and vice versa).
const cfg: Record<string, Block> = {
entry: { name: "entry", gen: ["d1"], kill: ["d2"], preds: [] },
head: { name: "head", gen: [], kill: [], preds: ["entry", "body"] },
body: { name: "body", gen: ["d2"], kill: ["d1"], preds: ["head"] },
exit: { name: "exit", gen: [], kill: [], preds: ["head"] },
};
const order = ["entry", "head", "body", "exit"];
const IN: Record<string, Set<string>> = {};
const OUT: Record<string, Set<string>> = {};
for (const b of order) { IN[b] = new Set(); OUT[b] = new Set(); }
const eq = (a: Set<string>, b: Set<string>) => a.size === b.size && [...a].every((x) => b.has(x));
let changed = true, passes = 0;
while (changed) {
changed = false; passes++;
for (const b of order) {
const blk = cfg[b];
const inSet = new Set<string>(); // IN = union of preds' OUT (may / forward)
for (const p of blk.preds) for (const d of OUT[p]) inSet.add(d);
const outSet = new Set<string>(blk.gen); // OUT = gen ∪ (IN − kill)
for (const d of inSet) if (!blk.kill.includes(d)) outSet.add(d);
IN[b] = inSet;
if (!eq(outSet, OUT[b])) { OUT[b] = outSet; changed = true; }
}
}
console.log(`fixed point reached in ${passes} passes`);
for (const b of order) console.log(`IN[${b}] = {${[...IN[b]].sort().join(",")}}`);
The interesting block is head: it is reached both from entry (carrying
d1) and from body (carrying d2), so at the fixed point
\textit{IN}[\texttt{head}] = \{d1, d2\} — both definitions of
x may reach the loop head. The analysis discovered that fact by chasing the back-edge around
until the sets stopped growing.
Why it always terminates: lattices and monotonicity
The framework's guarantees come from order theory. The possible values of each
\textit{IN}/\textit{OUT} set form a lattice — a partially
ordered set (here, sets of facts ordered by \subseteq) with a meet operation
combining any two elements. The transfer functions are monotonic: give them a bigger
input and they produce a no-smaller output; they never undo progress. A finite lattice plus monotone
transfer functions is exactly the condition of the Kleene fixed-point theorem: iterate
from the bottom element and you climb the lattice, strictly, until you reach the least fixed point
— and because the lattice has finite height, you get there in finitely many steps.
That is the deep reason data-flow analysis is trustworthy: it is not a heuristic that "usually works," it
is a computation with a proof of termination and a proof that its answer is a sound
over-approximation of every real execution. The full theory of
lattices and fixed points
makes this precise.
Because the approximation always errs in the safe direction — and which direction is safe flips
with the analysis. Live-variable analysis may report a variable live when it is actually dead; the cost is
a missed dead-code elimination, never a wrong deletion. Available-expressions analysis will only claim an
expression is available if it truly is on every path; if unsure, it says "not available" and you
miss a common-subexpression elimination, but you never reuse a stale value. This is the meaning of a
conservative (sound) analysis: it may leave optimisations on the table, but it never
performs an incorrect one. "May" analyses over-approximate; "must" analyses under-approximate; both
stay on the safe side of correctness. Optimisation is the art of being conservative without being timid.
A frequent muddle is to think you can pick forward/backward or union/intersection to taste. You cannot —
the question dictates both. "Which definitions reach here?" is inherently about the
past, so it is forward; and a definition reaching along any path counts, so it is union.
"Is this value used later?" is inherently about the future, so it is backward; used on
any future path counts, so union again. "Is this expression already computed on the way
here?" needs it computed on all paths to be safe, so it is intersection. Get the meet wrong —
use union where you needed intersection — and you will "prove" an expression is available when it was
computed on only one branch, and cheerfully reuse a value that was never computed on the other. The
direction and meet are part of the analysis's specification, not tuning parameters.