Data-Flow Analysis Framework: short notes (Compiler Design)

Introduction

Global optimisations need facts that hold at a program point on every execution, or on some execution: "this definition of x may reach here", "y may be used later", "a + b has already been computed on every path to here", "z is always 3 here". Data-flow analysis computes such facts for every point of a flow graph by solving a system of equations, one pair per block, by repeated approximation until nothing changes.

All the standard analyses share one shape: a set of values, a direction (forward or backward), a meet operator that combines information where paths join, transfer functions for blocks, and an initial value. Learning that shape once makes reaching definitions, liveness, available expressions and constant propagation instances of the same algorithm. Questions ask for the direction and meet of an analysis, its equations, or the IN and OUT sets of a small flow graph.

Prerequisites

Basic Blocks and Control-Flow Graphs: blocks, predecessors and successors, and loops in the flow graph.
Sets, union and intersection, and the idea of a fixed point of an equation system.

Core concepts

Program points. Before and after each instruction; for a block $B$ , $IN[B]$ is the value at its start and $OUT[B]$ at its end.
Transfer function $f_B$ . Maps the value on one side of $B$ to the value on the other. For the classic bit-vector problems it has the form $f(x) = gen \cup (x - kill)$ .
Direction. Forward: information flows with control, $OUT[B] = f_B(IN[B])$ and $IN[B]$ combines predecessors' OUT. Backward: against control, $IN[B] = f_B(OUT[B])$ and $OUT[B]$ combines successors' IN.
Meet $\wedge$ . Combines values at a join. Union for "may" problems (a fact holds if it holds along some path); intersection for "must" problems (it holds along all paths).
Boundary value. The value at the entry (forward) or exit (backward).
Initial value. Where iteration starts for the other blocks: the empty set for union problems, the universal set for intersection problems.
Semilattice. The set of values with the meet; it must have a top element $\top$ with $x \wedge \top = x$ . The ordering $x \le y$ means $x \wedge y = x$ : $x$ is the safer, less precise value.

How it works

The four classic problems

Analysis	Domain	Direction	Meet	Transfer	Boundary	Initial
Reaching definitions	Sets of definitions	Forward	$\cup$	$gen_B \cup (x - kill_B)$	$OUT[\text{entry}] = \emptyset$	$OUT[B] = \emptyset$
Live variables	Sets of variables	Backward	$\cup$	$use_B \cup (x - def_B)$	$IN[\text{exit}] = \emptyset$	$IN[B] = \emptyset$
Available expressions	Sets of expressions	Forward	$\cap$	$e\_gen_B \cup (x - e\_kill_B)$	$OUT[\text{entry}] = \emptyset$	$OUT[B] = U$
Constant propagation	Map from variables to {undefined, constant, not-a-constant}	Forward	Lattice meet per variable	Evaluate the block on the map	Every variable undefined	Every variable undefined

Forward and backward analyses, may and must problems — Figure 1. A forward analysis computes OUT from IN and meets the OUT values of predecessors; a backward analysis computes IN from OUT and meets the IN values of successors. Reaching definitions and available expressions are forward, live variables backward; union marks a may problem and intersection a must problem.

The iterative algorithm

For a forward problem:

Text

OUT[entry] = boundary value
for each block B other than entry: OUT[B] = initial value (top)
while some OUT changes:
    for each block B other than entry:
        IN[B]  = meet of OUT[P] over predecessors P of B
        OUT[B] = f_B(IN[B])

A backward problem is the mirror image: swap IN and OUT and use successors. Visiting blocks in reverse postorder (roughly, program order) for forward problems, and in postorder for backward problems, makes information flow far in each pass. The algorithm needs one pass more than the number of passes that change something, since the last pass only confirms that nothing changes.

Gen and kill for a block

For reaching definitions, a block's $gen$ holds the definitions in it that are not overwritten later in the same block; its $kill$ holds every other definition, anywhere in the program, of a variable the block defines. The composition of the instructions' transfer functions gives the block's, because each has the form $gen \cup (x - kill)$ .

Example: reaching definitions

Text

B1: d1: x = 1
    d2: y = 2
B2: d3: x = x + 1
B3: d4: y = x * 2
B4: d5: x = y - 1

Edges: entry $\to B_1$ , $B_1 \to B_2$ , $B_2 \to B_3$ , $B_2 \to B_4$ , $B_3 \to B_4$ , $B_4 \to B_2$ , $B_4 \to$ exit. The definitions of x are $d_1, d_3, d_5$ ; those of y are $d_2, d_4$ .

Block	gen	kill
$B_1$	$d_1, d_2$	$d_3, d_4, d_5$
$B_2$	$d_3$	$d_1, d_5$
$B_3$	$d_4$	$d_2$
$B_4$	$d_5$	$d_1, d_3$

Iterating in the order $B_1, B_2, B_3, B_4$ , with every OUT starting empty:

Block	OUT after pass 1	OUT after pass 2	Final IN
$B_1$	$d_1, d_2$	$d_1, d_2$	$\emptyset$
$B_2$	$d_2, d_3$	$d_2, d_3, d_4$	$d_1, d_2, d_4, d_5$
$B_3$	$d_3, d_4$	$d_3, d_4$	$d_2, d_3, d_4$
$B_4$	$d_2, d_4, d_5$	$d_2, d_4, d_5$	$d_2, d_3, d_4$

Pass 3 changes nothing, so three passes are made. In pass 1, $B_2$ has not yet seen $OUT[B_4]$ , which is still empty; in pass 2 it picks up $d_4$ and $d_5$ through the back edge, giving $OUT[B_2] = \{d_3\} \cup (\{d_1, d_2, d_4, d_5\} - \{d_1, d_5\}) = \{d_2, d_3, d_4\}$ .

Reading the result: at the start of $B_2$ , x may come from $d_1$ or $d_5$ , so x is not a known constant there. $d_3$ does not reach the start of $B_2$ : every path back to $B_2$ passes $B_4$ , which redefines x. $d_2$ reaches $B_4$ because the path $B_1, B_2, B_4$ skips $B_3$ , the only other block that defines y. Visiting the blocks in the reverse order $B_4, B_3, B_2, B_1$ gives the same final sets after four passes.

Use-definition chains. Reaching definitions answer "which definitions can supply the value read here?". Restrict the IN set of a block to the definitions of the variable being read:

Use	Reaching definitions of that variable	Consequence
`x` in $d_3$ ( $B_2$ )	$d_1$ , $d_5$	two possible values; not a constant
`x` in $d_4$ ( $B_3$ )	$d_3$ only	the value is always the one computed in $B_2$
`y` in $d_5$ ( $B_4$ )	$d_2$ , $d_4$	depends on whether $B_3$ ran

These lists are the ud-chains of the uses. A unique reaching definition assigning a known constant is sufficient, not necessary, for constant replacement: all possible reaching definitions assigning the same known constant also permit it, provided no unmodeled modification intervenes (compare Constant Propagation).

Two definitions of one variable in a block. In a block d6: x = 1; d7: y = x; d8: x = y + 2, in a program where x is also defined by $d_9$ and y by $d_{10}$ elsewhere, $gen = \{d_7, d_8\}$ : $d_6$ is overwritten by $d_8$ before the block ends. $kill = \{d_6, d_9, d_{10}\}$ : the block kills its own earlier definition $d_6$ as well as the definitions in other blocks. A definition reaches the end of a block only if it is the last definition of its variable in the block.

New analyses described in words

Analysis	The fact at a point	Direction	Meet
Possibly uninitialised variables	some path from the entry reaches here without assigning `v`	Forward	$\cup$
Definitely assigned variables	`v` has been assigned on every path from the entry	Forward	$\cap$
Dominators	block $d$ lies on every path from the entry	Forward	$\cap$
Very busy (anticipated) expressions	`e` will be evaluated on every path from here before any operand changes	Backward	$\cap$

Related material. Very busy expressions are the anticipated expressions of partial-redundancy elimination (Dragon Book Section 9.5); they show that a backward must problem exists.

Why it terminates and what it computes

Monotone transfer functions ( $x \le y \Rightarrow f(x) \le f(y)$ ) and a semilattice of finite height guarantee that each value can only move down a finite number of times, so the iteration stops.
The result is the maximum fixed point (MFP): the largest solution of the equations under the lattice order, which is the most precise safe answer the equations allow.
The ideal answer is the meet over all paths (MOP): apply the transfer functions along every path to the point and meet the results. Iteration meets at joins first, so in general $MFP \le MOP$ (MFP is safe but possibly less precise). If every transfer function is distributive, $f(x \wedge y) = f(x) \wedge f(y)$ , then $MFP = MOP$ .
The gen-kill problems are distributive. Constant propagation is monotone but not distributive (see the note Constant Propagation).

Choosing direction and meet

Ask two questions. Does the fact at a point depend on the past or the future? Definitions and computed expressions come from the past (forward); uses come from the future (backward). Must it hold on all paths or just some? "May reach" and "may be live" need some path (union); "is available" needs all paths (intersection).

Important properties and observations

Union problems start from $\emptyset$ ; intersection problems start from $U$ (except at the boundary). Starting available expressions from $\emptyset$ everywhere gives a correct but needlessly weak answer on loops.
The order of visiting blocks changes the number of passes, not the result.
Passes are bounded by the depth of the flow graph plus 2 for these bit-vector problems when blocks are visited in depth-first order; the depth is the largest number of retreating edges on any cycle-free path, 1 in the example, which needs 3 passes.
Precision versus safety. Reaching definitions and liveness may overestimate (a "may" answer that includes too much is safe for optimisation); available expressions may underestimate.
Instruction-level points follow from block-level IN or OUT by applying the instructions' transfer functions one at a time.

Common misconceptions.

"Liveness is forward." It is backward: whether a variable is used later depends on what follows.
"Available expressions uses union." It uses intersection: the expression must be computed on every path.
"The iteration's first pass gives the answer for loops." Back edges carry information that needs at least one more pass.

GATE examination perspective

Direction and meet. Consider a named analysis or a new one described in words.
Equations. Write IN and OUT for a forward or backward problem; know gen, kill, use and def.
Compute sets. Work on a small flow graph: gen and kill per block, then IN and OUT by iteration.
Initialisation trap. Universal set for intersection problems.
ud-chains. Apply this to a use of v, list the reaching definitions of v only; a unique known-constant definition is sufficient; multiple reaching definitions also allow replacement when all assign the same known constant and no unmodeled modification intervenes.
gen and kill with repeated targets. Only the last definition of each variable in a block is in $gen$ ; the earlier ones are in $kill$ .
Classify a new analysis. By the two questions: past or future (direction), all paths or some path (meet).
Properties. Monotone, distributive, MOP versus MFP, termination on a finite lattice.

Summary

A data-flow problem = domain, direction, meet, transfer functions, boundary and initial values.
Forward: $IN[B] = \bigwedge_{P \in pred(B)} OUT[P]$ , $OUT[B] = f_B(IN[B])$ . Backward: the mirror image.
Union for may problems, intersection for must problems.
Reaching definitions: forward, union. Liveness: backward, union. Available expressions: forward, intersection.
Iterate to a fixed point; monotone functions on a finite lattice terminate; distributive functions give MFP = MOP.
Example: $IN[B_2] = \{d_1, d_2, d_4, d_5\}$ , three passes in program order.
ud-chains in the example: x in $B_3$ is reached only by $d_3$ ; x in $B_2$ by $d_1$ and $d_5$ ; y in $B_4$ by $d_2$ and $d_4$ .

Basic Blocks and Control-Flow Graphs: prerequisite. The flow graph the equations are written over.
Liveness Analysis: dependent. The backward union problem and its use in register allocation.
Constant Propagation: dependent. A forward problem over a lattice that is not a set of facts.
Common Subexpression Elimination: dependent. Available expressions as a forward intersection problem.

Data-Flow Analysis Framework

Introduction

Prerequisites

Core concepts

How it works

The four classic problems

The iterative algorithm

Gen and kill for a block

Example: reaching definitions

New analyses described in words

Why it terminates and what it computes

Choosing direction and meet

Important properties and observations

GATE examination perspective

Summary

Sources

Next steps

Introduction

Prerequisites

Core concepts

How it works

The four classic problems

The iterative algorithm

Gen and kill for a block

Example: reaching definitions

New analyses described in words

Why it terminates and what it computes

Choosing direction and meet

Important properties and observations

GATE examination perspective

Summary

Related topics

Sources

Next steps