Data flow analysis framework

Why it exists

Local optimisation sees one basic block at a time. To know that a value computed in one block can be reused in another, that a variable assigned in one block is never read afterwards, or that a variable always holds the same constant when control reaches a block, the compiler must follow all the paths through the flow graph. Data flow analysis collects such facts for every point of the program. The remarkable thing is that the many different analyses (reaching definitions, live variables, available expressions, constant propagation) are all instances of one framework: a few set equations per block and one iterative algorithm that solves them.

Prerequisites

You need the flow graph of basic blocks (basic blocks and control flow graphs).

Precise definitions

Program points and data flow values. A program point lies before or after each instruction; the point at the start of block $B$ is IN[$B$] and the one at its end is OUT[$B$]. The analysis associates a data flow value with each point: for reaching definitions a set of definitions, for live variables a set of variables, and so on. An execution is a path through the graph; the value at a point summarises what is true at that point for all (or some) executions that arrive there.

Transfer functions. The effect of a block on the data flow value is a function $f_B$ with OUT[$B$] = $f_B$(IN[$B$]) in a forward analysis (information flows along the control flow) or IN[$B$] = $f_B$(OUT[$B$]) in a backward one. The classical analyses are gen-kill problems:

$f_B(x) = \text{gen}_B \;\cup\; (x - \text{kill}_B).$

$\text{gen}_B$ are the facts the block creates, $\text{kill}_B$ are the facts it destroys.

Meet operator. Where paths join (several predecessors in a forward analysis, several successors in a backward one) the values are combined with a meet operator $\wedge$: union if "true on some path" is what is wanted (a may analysis), intersection if "true on all paths" (a must analysis).

Boundary and initial values. The value at the entry (forward) or at the exits (backward) is fixed by the problem (the empty set for the four standard analyses). All other points start at the identity (top) element of the meet: the empty set for union, the set of all facts $U$ for intersection (so that the first meet leaves the other operand unchanged).

The four standard analyses.

A fifth classical one, very busy (anticipated) expressions, is backward with intersection; it is outside the syllabus.

Iterative algorithm (forward, gen-kill).

OUT[ENTRY] = boundary;  for every other block B: OUT[B] = top
repeat
    for every block B other than ENTRY (in reverse postorder):
        IN[B]  = meet over all predecessors P of OUT[P]
        OUT[B] = f_B(IN[B])
until no OUT changes

The backward version swaps the roles: it starts from the exits, takes the meet of the INs of the successors to form OUT[$B$], computes IN[$B$] = $f_B$(OUT[$B$]), and visits the blocks in the reverse of the forward order. A pass that changes nothing ends the iteration, so the last pass only confirms the result.

Why it terminates and what it computes. The data flow values form a semilattice (a set with a meet operation that is idempotent, commutative and associative, with a top element). For finite sets of facts every chain of values is finite. If every transfer function is monotone ($x \le y$ implies $f(x) \le f(y)$), each value can only move in one direction (down the lattice) in each iteration, so the algorithm must stop. The result is the maximum fixed point (MFP) of the equations. It is always a safe approximation. The ideal answer is the meet over all paths (MOP): apply the transfer functions along each path from the entry to the point and take the meet of the results. In general MFP $\le$ MOP (the iterative solution may be less precise). When the framework is distributive, $f(x \wedge y) = f(x) \wedge f(y)$, the two are equal. All gen-kill problems are distributive, so their MFP is exactly the MOP; constant propagation is monotone but not distributive (the next page has the example).

Speed. The order in which blocks are visited does not change the result but changes the number of passes. A depth-first order (reverse postorder) lets information travel along an acyclic path in one pass; for typical reducible flow graphs the number of passes is bounded by the depth of loop nesting plus a small constant (the textbook states at most $d + 2$ with $d$ the largest number of back edges on an acyclic path), so two or three passes are usual. This bound is a statement about the worst case of the order, not an exact count.

How it works

The animation runs the iterative algorithm for reaching definitions on a flow graph with a loop. The code is the textbook-style loop with six definitions of i, j and a; the flow graph has the blocks B1, B2, B3, B4, with B2 → B3, B2 → B4, B3 → B4 and the back edge B4 → B2. Every step recomputes IN and OUT of one block in reverse postorder, with the equation written out. Pass 1 gives the sets their first values; B2 is visited when OUT[B4] is still empty, so pass 2 revises IN[B2] after B4 has been computed; pass 3 confirms that nothing changes (so the algorithm needs three passes counting the final confirming one).

Compare the other analyses on the same footing: live variables run the same loop backwards with use and def in place of gen and kill (liveness); available expressions use intersection and the universal set as the initial value (available expressions); constant propagation works on a different lattice (reaching definitions and constant propagation).

Worked examples

Cheat box

Traps and GATE patterns

Connections

The graph is built from basic blocks. The three bit-vector instances are reaching definitions, liveness and available expressions; their results enable the optimisations of local optimisation across block boundaries (global common subexpressions, dead code, constant folding).

PYQs

Self-check

Revision card

References