Reaching Definitions and the Monotone Dataflow Framework

A definition is a program point that writes a value to a variable. It reaches a program point if some execution path carries that write to the point without an intervening redefinition of the same variable. The question sounds local and turns out to be global: answering it for every point in a procedure is the first real analysis most compilers implement, and almost every later optimization consumes the result. Constant propagation needs to know whether a variable still holds the literal assigned three blocks earlier. Dead-store elimination needs to know whether a write is ever observed. Register allocation needs the use-def chains that reaching definitions produce.

The mechanism is worth understanding in its general form rather than as one algorithm, because the same shape — a lattice, a monotone transfer function, and a fixpoint iteration — recurs for liveness, availability, very busy expressions, and a dozen other properties.

What the analysis state is

For each program point, the state is a set of definitions. A definition is identified by the program point that performs the write, not by the variable name, so x = 1 in block B2 and x = 2 in block B5 are distinct definitions even though both assign to x. The set at a point lists every definition that may still be live on entry to that point.

That “may” is the whole design decision. A path-sensitive answer would list definitions separately for each path, which is exponential in the number of branches. The analysis instead merges the states of all paths that reach a point by set union. Union is the correct merge for a property that asks “can this be true”, because a definition needs to survive on only one path to matter. The cost is imprecision: after a merge, the analysis cannot say which of two definitions is the real one, so consumers must handle either.

Formally the states form a lattice ordered by subset inclusion. The bottom element is the empty set, meaning no definition reaches; the top is the set of all definitions, meaning nothing is known. Union is the least upper bound. Transfer functions map one state to another and are defined to be monotone: if S ⊆ T then f(S) ⊆ f(T). Monotonicity is what makes the fixpoint reachable by iteration from bottom, because the sequence of states produced is non-decreasing in the lattice order and the lattice has finite height.

Gen and kill, block by block

A basic block has two precomputed sets. GEN[B] holds the definitions inside B that survive to the end of the block — a write is killed by a later write to the same variable in the same block, so only the last write per variable qualifies. KILL[B] holds definitions elsewhere in the procedure that write the same variables as some definition in B.

The transfer function is then OUT[B] = GEN[B] ∪ (IN[B] − KILL[B]), and the dataflow equation IN[B] = ∪ OUT[P] over predecessors P. Both parts are monotone: union and set difference with a fixed set preserve inclusion. The functions are also distributive over union, which is a stronger property than monotonicity and matters later.

/* One bit per definition, indexed densely across the procedure. */
typedef struct { uint64_t *bits; } defset;

static void transfer(const bb *b, const defset *in, defset *out) {
    for (int w = 0; w < b->nwords; w++)
        out->bits[w] = b->gen[w] | (in->bits[w] & ~b->kill[w]);
}

The bitvector encoding is not incidental. With D definitions in a procedure, a set costs D bits and union costs D/64 machine words on a 64-bit target. A procedure with a thousand definitions therefore needs sixteen words per block per direction, and a union is sixteen OR instructions. The alternative — sorted lists or hash sets — costs allocation and pointer chasing per merge and loses the word-parallel merge entirely. This is why the classical formulation is taught in terms of bitsets.

Iterating to a fixpoint

Initialisation matters. OUT[B] starts empty for every block, which is the bottom of the lattice, and the entry block’s IN is empty. Starting from bottom and iterating upward computes the least fixpoint, which is the one that means “the smallest set of facts consistent with the equations”. Any larger fixpoint would also satisfy the equations but would claim definitions reach that cannot, and downstream optimizations would then be conservative in the wrong direction — they would refuse to transform, or worse, transform on a false premise.

The worklist algorithm visits a block only when one of its predecessors changed, which avoids re-scanning blocks whose input is stable:

/* Least-fixpoint iteration. Blocks carry index arrays for preds/succs and
   four bitsets of nwords uint64_t each: gen, kill, in, out. */
static void solve(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;

        defset in = union_of_pred_out(b);        /* meet over predecessors */
        if (defset_equal(&in, &b->in)) continue; /* stable: nothing downstream moves */
        b->in = in;
        transfer(b, &b->in, &b->out);

        for (int k = 0; k < b->nsucc; k++)
            if (!queued[b->succ[k]]) {
                queued[b->succ[k]] = 1;
                queue[qlen++] = b->succ[k];
            }
    }
}

Termination follows from monotonicity plus finite height. Each block’s IN set only grows, each set has at most D elements, so a block can change at most D times. The worst case is O(E · D) set merges for E edges, and in practice far fewer because most blocks settle after one or two passes. For reducible control flow, a round-robin pass in reverse postorder converges in a number of passes proportional to loop nesting depth plus one, which is why implementations that skip the worklist and just sweep in RPO are still common.

Where the framework stops being exact

The classical theory proves that if every transfer function distributes over the merge — that is, f(S ∪ T) = f(S) ∪ f(T) — then the fixpoint equals the merge-over-all-paths solution: the result of propagating states along each concrete path and merging at the join. Reaching definitions has this property, so its answer is exact with respect to the path-insensitive model.

Many useful analyses do not distribute. Constant propagation is the standard counterexample. If one path assigns x = 3 and another assigns x = 4, the merge produces “not a constant”, and a later x - x is then left unfolded even though its value is zero on both paths. Propagating each path separately would have kept the correlation between the two uses of x; merging at the join destroys it. Kam and Ullman showed the general result: for monotone but non-distributive frameworks the fixpoint is a safe over-approximation of the path-merged answer, never smaller. The analysis stays sound and loses precision, which is the trade every real optimizer accepts.

Three further limits are structural rather than theoretical.

Memory writes are not definitions of a variable but of a location, and a store through a pointer may alias any variable whose address escaped. Implementations either treat such a store as killing all address-taken variables, which is sound and blunt, or run a separate alias analysis whose results feed back into the kill sets. The precision of the reaching-definitions answer is therefore capped by the precision of the alias analysis, and alias analyses are themselves approximate.

Unreachable code produces empty IN sets and, if left in the graph, can make the fixpoint smaller than a reader expects. Most implementations delete unreachable blocks first, because a block with no incoming edge is a block whose state is meaningless and whose presence perturbs the iteration order.

Finally, the analysis is intraprocedural. A call to a function that writes through a pointer argument looks, from inside the caller, like a store to whatever that pointer may point at. Interprocedural versions exist and are considerably more expensive, which is why the intraprocedural answer is the one most passes consume.

What the answer buys

The immediate products are use-def chains and def-use chains: for each use, the set of definitions that reach it; for each definition, the set of uses it reaches. Dead-store elimination removes a definition whose def-use set is empty, provided the write has no side effect. Copy propagation replaces a use of y with x when the only reaching definition of y is y = x. Redundancy elimination looks for two computations with identical operands where no definition of those operands reaches the second.

The same lattice machinery reappears with the direction and the meet operator changed. Running the equations backward over the CFG, with intersection instead of union, yields liveness — the property that a variable’s value will be read before being overwritten, examined in Live-Variable Analysis and the Backward Direction of Dataflow. Replacing the bitset domain with a product of per-variable lattices gives constant propagation, and the fixpoint argument carries over unchanged, as described in Constant Propagation over a Flat Lattice.

The deeper consequence is that reaching definitions is a dense analysis: it stores a set at every program point, including points where most of the set is irrelevant. Storing one definition per use instead, with the def-use edges carrying the information, is the sparse formulation that motivates SSA, covered in SSA Construction and the Cost of Phi Placement.