12.4 Data-Flow Analysis Framework

Many optimizations need facts that are not local to one instruction. Which definitions can reach this block? Which expressions are already available on every incoming path? Which values may be used in the future? A data-flow analysis computes such facts over the control-flow graph until they become consistent everywhere.

Instead of implementing every analysis from scratch, compilers reuse a framework with four choices:

• a domain of facts, usually represented as sets or lattice elements;

• a direction, forward or backward;

• a meet operator that combines predecessor or successor facts;

• a transfer function describing how each block changes facts.

The boundary condition says what is known at function entry or exit. Initialization for other blocks must match whether the analysis seeks a least or greatest fixed point.

Forward and backward equations

For a forward analysis:

IN[B]  = meet of OUT[P] for every predecessor P of B
OUT[B] = transfer_B(IN[B])

For a backward analysis:

OUT[B] = meet of IN[S] for every successor S of B
IN[B]  = transfer_B(OUT[B])

Reaching definitions is a forward may-analysis. Its meet is union because a definition reaches a block if it can arrive along any predecessor path:

OUT[B] = GEN[B] ∪ (IN[B] − KILL[B])

Available expressions is a forward must-analysis. Its meet is intersection because an expression is available only if it has been computed and not killed on every incoming path.

A worked reaching-definitions merge

Suppose x1 is defined before a branch, and the left arm defines x2 while the right arm leaves x unchanged. At the merge, the reaching set is {x1, x2}: some executions arrive with the old definition and others with the new one. If the merge block defines x3, its transfer kills both older definitions and generates {x3}.

The analysis reports possibilities, not runtime history. It does not claim that x1 and x2 both execute in one run; it says either may reach the merge. That distinction is essential when an optimizer consumes the result.

Iteration to a fixed point

Loops create cyclic equations. The header depends on the latch, which depends on the header. A worklist solver starts from the chosen initialization, applies transfers, and re-enqueues neighbors whenever a fact changes. It stops when processing every block produces no change: a fixed point.

Termination follows when the domain has finite height and transfer functions are monotone. Facts move in one allowed lattice direction and cannot oscillate forever. Reverse postorder often speeds forward analyses because information travels through acyclic regions before revisiting back edges; a reverse order often helps backward analyses. Order affects work, not the correct final solution.

Engineering a reusable solver

A generic solver should make direction, boundary, meet, equality, and transfer explicit. It should not bake union or forward traversal into its core. Facts are usually immutable values or efficiently copied bitsets; accidental mutation of a predecessor's set can corrupt several blocks at once.

Diagnostics matter too. A useful analysis debugger prints each block's IN, GEN/KILL or USE/DEF, and OUT, plus the iteration when a fact changed. Small diamond and loop CFGs make excellent golden tests. Verify the solution by substituting final facts back into every equation: after convergence, each equation must reproduce the stored result exactly.