Data Flow Analysis

The prerequisite analysis layer for compiler optimization: iteratively propagating data flow facts on the control flow graph until convergence. The same gen/kill/meet/worklist framework, with a different direction and meet operation, solves three different problems: liveness, reaching definitions, and available expressions.

Overview

A compiler needs to know "which variables are in use, which definitions can reach here, and which expressions have already been computed" at every point in the program. This information cannot be derived from a single instruction; it must be propagated across the entire control flow. Data flow analysis is the process of iteratively propagating data flow facts on a program's Control Flow Graph (CFG) until all points converge.

Abstracting this into a unified framework (Kildall, 1973) allows the same iterative algorithm to solve multiple classes of analysis problems by changing the "direction," "meet operation," and "transfer functions." This article discusses this unified framework and then expands on three core instances: reaching definitions, liveness, and available expressions. These are also direct prerequisites for classic optimizations.

Unified Framework

The four components of data flow analysis:

• May Analysis (∪): Asks "what could it be?" — an over-approximation, preferring false positives over false negatives. Reaching definitions is a may analysis: a definition "may" reach a certain point.
• Must Analysis (∩): Asks "what must it be?" — an under-approximation, preferring false negatives over false positives. Available expressions is a must analysis: an expression "must" have been computed.

The transfer function is generally written as: out[B] = gen[B] ∪ (in[B] - kill[B]) (or ∩ replaces ∪, depending on the meet). gen represents new facts "produced" by the block, and kill represents old facts "invalidated" by the block.

Iterative Solution: Worklist Algorithm

Repeatedly scan the entire CFG until it stabilizes (reaches a fixed point):

for each block B: out[B] = ∅ (or top)
worklist = all blocks
while worklist not empty:
    B = worklist.pop()
    in[B] = meet(out[predecessors of B])
    old_out = out[B]
    out[B] = gen[B] ∪ (in[B] - kill[B])     ← Transfer function
    if out[B] changed:
        worklist.push(successors of B)        ← Propagate changes only

Termination is guaranteed by two conditions: the lattice height is finite (the set of facts has a maximum element) and the transfer functions are monotonic (new in → new out will not be less than the old one) — the fixed-point theorem. For engineering CFGs, convergence is usually fast (typically 3–5 rounds).

The ordering of the worklist affects convergence speed; processing nodes whose predecessors have already been updated (approximated by CFG topological order) is more efficient than random processing.

Three Classic Analyses

Reaching Definitions (Forward, May, ∪)

Problem: At program point p, which assignments (definitions) may reach p without being overwritten by subsequent assignments?

gen[B]:  The statement in this block that last assigns to variable x (earlier assignments are overwritten by later ones)
kill[B]: All assignments to x elsewhere, which are "killed" by the new assignment in this block

This forms the basis for constructing use-def chains. After SSA form is introduced, reaching definitions on SSA IR become sparse and no longer require iterative solving; however, it remains essential on conventional IR.

Liveness (Backward, May, ∪)

Problem: At program point p, will the value of variable x be used in the future (before its next definition)?

Direction changed to backward: propagate from exit to predecessors
gen[B]:  Variables that are "used" in this block but not "redefined" by this block before use
kill[B]: Variables that are "redefined" in this block but not "used" in this block before this definition (new value overwrites old value)

Liveness analysis directly determines register allocation: two variables can share the same register if they are not simultaneously active (see Register Allocation). This is the most frequently performed analysis in compiler optimization.

Available Expressions (Forward, Must, ∩)

Problem: At program point p, has the expression x + y definitely been computed, and have neither x nor y been reassigned?

gen[B]:  Expressions computed in this block (and x/y not redefined afterwards)
kill[B]: All expressions containing x or y, which are invalidated after an assignment to x or y in this block
meet:   ∩ (must) — available expressions at entry = intersection of out sets of all predecessors

Information from available expressions is directly used for CSE (Common Subexpression Elimination) — if x + y is available at the current point, the previous result is reused without recomputation.

MOP vs MFP: The Gap Between Ideal and Fixed-Point Solutions

• MOP (Meet Over all Paths): For program point p, collect "the facts carried when reaching p via all possible paths," then perform a meet on these facts. This is the ideal solution.
• MFP (Maximal Fixed Point): The solution obtained by the iterative fixed-point algorithm. MFP ≤ MOP (in the lattice order sense, MFP may be more conservative).

For distributive transfer functions — i.e., functions where f(a meet b) == f(a) meet f(b) — MFP = MOP, and the fixed point is the ideal solution. The transfer functions for reaching definitions and liveness are distributive; the transfer function for constant propagation is not distributive, so MFP is more conservative than MOP.

Sparse Data Flow under SSA

The entire iterative fixed-point framework is significantly simplified under SSA form:

• Each variable is defined only once → reaching definitions degenerates to "where is the definition for this use?" (direct def-use chain, no analysis needed).
• Liveness can be performed on the def-use graph — the live range of each definition consists of all use points reachable from its definition point, eliminating the need for iteration across the entire CFG.
• Many passes that "propagate facts across the entire CFG" degenerate into "single-pass propagation on the dominator tree" under SSA.

This is why SSA is called "sparse analysis" — data flow facts are attached only to def and use points, rather than every edge in the CFG.

References

• Kildall (1973): "A Unified Approach to Global Program Optimization" — The unified framework for data flow analysis
• Dragon Book: Chapter 9, Machine-Independent Optimizations — Contains complete gen/kill tables and fixed-point algorithms
• Cooper/Torczon: "Engineering a Compiler", Chapters 8–10

Keywords: data flow analysis, gen/kill, meet operator, forward/backward, may/must, reaching definitions, liveness, available expressions, fixed-point iteration, worklist algorithm, lattice, monotonicity, MOP, MFP, distributive function, sparse analysis, SSA