Reaching Definitions
A definition of a variable is any statement that assigns to it — d: x = ….
We say that definition reaches a program point p if there is a path
from the definition to p along which the variable is not
redefined. Intuitively: standing at p and asking "which assignment
might have set the value I'm about to read?", the reaching definitions are the complete list of
suspects. This is the first concrete instance of the
dataflow framework,
and the one every compiler course starts with.
It is a forward, union analysis — a "may" problem. Forward, because a definition flows
downstream from where it happens. Union, because a definition reaches a merge point if it
reaches along any one incoming edge; we are cataloguing possibilities, not certainties.
gen and kill, per block
Each basic block is summarised by two sets of definitions:
-
\text{gen}_B — definitions made in B that
survive to its end (a later definition of the same variable in the same block shadows an earlier
one, so only the last definition of each variable is generated).
-
\text{kill}_B — every definition, anywhere in the whole procedure,
of a variable that B redefines. If B assigns to
x, it kills all other definitions of x,
because after B those older assignments can no longer be the current value.
With those, the transfer function is the standard gen/kill form, and the meet is union over
predecessors:
\text{OUT}[B] \;=\; \text{gen}_B \,\cup\, \big(\text{IN}[B] - \text{kill}_B\big), \qquad \text{IN}[B] \;=\; \bigcup_{P \,\in\, \text{pred}(B)} \text{OUT}[P].
The boundary condition is \text{OUT}[\text{ENTRY}] = \varnothing — nothing is
defined before the program starts — and every interior \text{OUT}[B] is
initialised to \varnothing (the identity of union), then iterated to a fixed
point.
A worked flow graph
Here is the Dragon Book's running example: seven definitions d_1 \ldots d_7
across four blocks, with a loop back-edge from B_4 to
B_2. Variable i is defined by
d_1, d_4, d_7; j by
d_2, d_5; a by d_3, d_6.
Reveal the OUT set that each block ultimately contributes:
The interesting block is B_2. Because the back-edge carries
B_4's output back into B_2's input, the first
pass under-counts what reaches B_2; a second pass picks up the definitions
that flow around the loop. That is exactly why the analysis must iterate.
Iterating to a fixed point
Sweep the blocks in order B_1, B_2, B_3, B_4, recomputing IN then OUT, until
a whole pass changes nothing. Here are the OUT sets as they settle:
| Block (gen / kill) | OUT after pass 1 | OUT after pass 2 | Final |
|---|
| B_1 — gen \{d_1,d_2,d_3\} | \{d_1,d_2,d_3\} | \{d_1,d_2,d_3\} | \{d_1,d_2,d_3\} |
| B_2 — gen \{d_4,d_5\} | \{d_3,d_4,d_5\} | \{d_3,d_4,d_5,d_6\} | \{d_3,d_4,d_5,d_6\} |
| B_3 — gen \{d_6\} | \{d_4,d_5,d_6\} | \{d_4,d_5,d_6\} | \{d_4,d_5,d_6\} |
| B_4 — gen \{d_7\} | \{d_3,d_5,d_6,d_7\} | \{d_3,d_5,d_6,d_7\} | \{d_3,d_5,d_6,d_7\} |
Only B_2 changes between passes 1 and 2: the loop feeds d_6
(from B_3, via B_4) back around into it. Pass 3
would change nothing, so the analysis has reached its fixed point — three passes total including the
confirming one.
Solving it in code, with bitsets
Reaching definitions is the poster child for bit-vector dataflow: represent each set
of definitions as the bits of an integer, and union becomes bitwise OR, "minus kill" becomes AND-NOT.
The solver is a handful of lines.
// Definitions d1..d7 map to bits 0..6.
const D = (n: number) => 1 << (n - 1);
const fmt = (mask: number): string => {
const out: string[] = [];
for (let n = 1; n <= 7; n++) if (mask & D(n)) out.push("d" + n);
return "{" + out.join(",") + "}";
};
interface Block { pred: number[]; gen: number; kill: number; }
// The Dragon Book CFG: B1 -> B2 -> {B3, B4}, B3 -> B4, B4 -> B2 (back-edge).
const blocks: Block[] = [
{ pred: [], gen: D(1) | D(2) | D(3), kill: D(4) | D(5) | D(6) | D(7) }, // B1
{ pred: [0, 3], gen: D(4) | D(5), kill: D(1) | D(2) | D(7) }, // B2
{ pred: [1], gen: D(6), kill: D(3) }, // B3
{ pred: [1, 2], gen: D(7), kill: D(1) | D(4) }, // B4
];
const IN = blocks.map(() => 0);
const OUT = blocks.map(() => 0);
let passes = 0, changed = true;
while (changed) {
changed = false; passes++;
for (let i = 0; i < blocks.length; i++) {
let inB = 0;
for (const p of blocks[i].pred) inB |= OUT[p]; // IN = union of preds' OUT
IN[i] = inB;
const outB = blocks[i].gen | (inB & ~blocks[i].kill); // OUT = gen ∪ (IN − kill)
if (outB !== OUT[i]) { OUT[i] = outB; changed = true; }
}
}
console.log(`fixed point after ${passes} passes`);
blocks.forEach((_, i) => console.log(`B${i + 1}: IN=${fmt(IN[i])} OUT=${fmt(OUT[i])}`));
The printed OUT sets match the table exactly, and the pass counter confirms the loop needed a second
productive sweep plus a third to verify. Bitwise operators do the set algebra in a single machine
instruction each — this is why real analyses scale to enormous functions.
What reaching definitions buys you
The result is the raw material for several optimizations and diagnostics:
-
Use–definition chains. For each use of a variable, the reaching definitions give the
exact set of assignments that could supply its value — the ud-chain. This is the backbone of
many transformations.
-
Constant propagation. If every definition reaching a use assigns the
same constant, the use can be replaced by that constant.
-
Uninitialised-variable warnings. If a use is reached by a special "definition" placed
at ENTRY (meaning "undefined here"), the variable may be read before it is written — the compiler
emits a warning.
-
Loop-invariant detection. An operand is loop-invariant if every definition reaching
it comes from outside the loop (or is itself invariant), enabling code motion.
Only if they agree. Constant propagation via reaching definitions is a "must-agree" test layered on top
of a "may-reach" analysis. Suppose the definitions d1: x = 5 and d2: x = 5
both reach a use of x: even though there are two of them, they carry the same constant, so
the use is provably 5 on every path and we may substitute. But if d1: x = 5
and d3: x = 6 both reach, the value is ambiguous — it is 5 on one path and
6 on another — so the meet is "not a constant" (⊤ in the constant-propagation lattice) and
we must leave the use alone. Reaching definitions tells you the candidate set; agreement across that
set is the extra condition.
The commonest error in computing \text{kill}_B is to look only at nearby
code. The kill set is global: if block B contains
x = …, it kills every other definition of x in the entire
procedure — those in distant blocks, those inside unrelated loops, all of them — because after
B assigns x, none of those older assignments can be the current
value of x anymore. Forgetting a far-away definition in the kill set makes the analysis
over-report what reaches (a stale definition seems to survive), and any optimization built on
it — constant propagation especially — becomes unsound. Build a table "variable → all its definitions"
once, up front, and derive every kill set from it. Note the pleasant asymmetry: gen is local
to the block, kill is global to the procedure.