Think of a city's water pipes. If you want to know whether a house gets clean water, you cannot look at the house alone. You have to trace every pipe that could feed it, and check whether any of those pipes passes through a dirty tank on the way. A compiler asking "is the value of x here always 5?" or "will this variable ever be read again?" has the same problem: the answer depends on every path through the program that can reach the point in question.
In Code Optimization Techniques we saw global optimizations such as common subexpression elimination across blocks, constant propagation and dead code elimination, and we argued informally that they were safe. Data-flow analysis is how a compiler gathers those facts mechanically, for every point in the flow graph at once.
Data-flow analysis is a family of techniques that compute, for every program point, a set of facts that hold on all (or on some) execution paths reaching or leaving that point. Each analysis is described by equations relating the facts at the entry (IN) and exit (OUT) of every basic block, which are solved by repeated iteration until nothing changes.
We will work through the three classic analyses (reaching definitions, live variables and available expressions) on concrete flow graphs, showing every iteration, and then put them in one framework. All gen/kill sets and every iteration table here were computed by a small Python program, and the chapter matches its output exactly.
Points, Paths and Facts
Inside a basic block, there is a point before the first statement, between every two adjacent statements, and after the last statement. A path is a sequence of points that execution can follow: through statements within a block, and along flow-graph edges between blocks.
Because a program can have infinitely many paths (loops can go round any number of times), we cannot follow each path. Instead we summarise each block by its effect on the facts, and write equations:
IN[B]: the facts that hold at the point just before block B.
OUT[B]: the facts that hold at the point just after block B.
A transfer function says how B turns IN[B] into OUT[B] (or OUT into IN, for a backward analysis).
A meet (or confluence) operator says how facts from several paths combine where paths join: union (∪) for "on some path", intersection (∩) for "on all paths".
Every analysis must be conservative (safe): when it cannot be sure, it must lean towards the answer that cannot make an optimization break the program. For example, "x might be used later" is a safe guess for dead code elimination, because it just stops us from deleting something.
The Running Example
We will use one flow graph for the first two analyses. It sums some values in a loop. Each definition (an assignment) is numbered d1 to d8.
B1: d1: i = 0
d2: s = 0
d3: m = n - 1
B2: d4: t = i * 2
if t > m goto B4
B3: d5: s = s + t
d6: i = i + 1
goto B2
B4: d7: m = m - 1
if i < m goto B2
B5: d8: s = s + i
return s +------+
| B1 |
+------+
|
v
+------+ <-------------------+
+----> | B2 | ------+ |
| +------+ | t > m |
| | v |
| | +------+ |
| | | B4 | ---------+ i < m
| v +------+
| +------+ |
+----- | B3 | v
+------+ +------+
| B5 |
+------+
Edges: B1→B2, B2→B3, B2→B4, B3→B2, B4→B2, B4→B5Block | Predecessors | Successors |
|---|---|---|
B1 | (entry) | B2 |
B2 | B1, B3, B4 | B3, B4 |
B3 | B2 | B2 |
B4 | B2 | B2, B5 |
B5 | B4 | (exit) |
1. Reaching Definitions
A definition d of variable x reaches a point p if there is a path from the point just after d to p along which x is not redefined. If x is assigned on the path, that assignment kills d.
Why we care: if the only definition of i reaching a use is i = 0, we can replace that use by 0 (constant propagation). If no definition reaches a use, the variable may be used before it is initialised, which is worth a warning.
It is a forward, may analysis: facts flow along edges in the direction of execution, and a definition reaches a join point if it arrives along any path, so the meet is union.
gen and kill
gen[B]: definitions in B that reach the end of B (the last definition of each variable in B).
kill[B]: all other definitions in the program of variables that B assigns.
Block | Assigns | gen[B] | kill[B] | gen (bits d1..d8) | kill (bits) |
|---|---|---|---|---|---|
B1 | i, s, m | {d1, d2, d3} | {d5, d6, d7, d8} | 1110 0000 | 0000 1111 |
B2 | t | {d4} | { } | 0001 0000 | 0000 0000 |
B3 | s, i | {d5, d6} | {d1, d2, d8} | 0000 1100 | 1100 0001 |
B4 | m | {d7} | {d3} | 0000 0010 | 0010 0000 |
B5 | s | {d8} | {d2, d5} | 0000 0001 | 0100 1000 |
For B1: it assigns i, s and m, so it kills every other definition of those variables: d6 (i), d5 and d8 (s), d7 (m). B2 assigns only t, and t has no other definition, so kill[B2] is empty.
The equations
OUT[ENTRY] = { }
IN[B] = ∪ OUT[P] over all predecessors P of B
OUT[B] = gen[B] ∪ (IN[B] − kill[B])Read the second equation aloud: "a definition reaches the end of B if B creates it, or if it reached the start of B and B did not kill it."
The iterative algorithm
for each block B: OUT[B] = { } // start with nothing reaching anywhere
repeat
changed = false
for each block B (in order B1, B2, ...):
IN[B] = union of OUT[P] for predecessors P
newOUT = gen[B] ∪ (IN[B] − kill[B])
if newOUT != OUT[B]: OUT[B] = newOUT; changed = true
until not changedWith bit vectors, union is bitwise OR and "IN − kill" is IN AND (NOT kill), so each step is just a few machine instructions per word.
Iterations
Bits are in order d1 d2 d3 d4 | d5 d6 d7 d8. Each pass visits B1 to B5 in order, using values already updated in the same pass.
Block | Pass 1: IN | Pass 1: OUT | Pass 2: IN | Pass 2: OUT | Pass 3 |
|---|---|---|---|---|---|
B1 | 0000 0000 | 1110 0000 | 0000 0000 | 1110 0000 | no change |
B2 | 1110 0000 | 1111 0000 | 1111 1110 | 1111 1110 | no change |
B3 | 1111 0000 | 0011 1100 | 1111 1110 | 0011 1110 | no change |
B4 | 1111 0000 | 1101 0010 | 1111 1110 | 1101 1110 | no change |
B5 | 1101 0010 | 1001 0011 | 1101 1110 | 1001 0111 | no change |
Some steps explained:
Pass 1, B2: its predecessors are B1, B3, B4. Only OUT[B1] is non-empty so far, so IN[B2] = 1110 0000. B2 adds d4.
Pass 1, B3: IN = OUT[B2] = {d1, d2, d3, d4}. B3 kills d1, d2 (and d8) and adds d5, d6: OUT = {d3, d4, d5, d6}.
Pass 2, B2: now OUT[B3] and OUT[B4] are known, so IN[B2] = 1110 0000 OR 0011 1100 OR 1101 0010 = 1111 1110: the definitions from the loop body flow back around the back edges.
Pass 3 changes nothing, so we stop.
Final answer
Block | IN (reaching definitions) | OUT |
|---|---|---|
B1 | { } | {d1, d2, d3} |
B2 | {d1, d2, d3, d4, d5, d6, d7} | {d1, d2, d3, d4, d5, d6, d7} |
B3 | {d1, d2, d3, d4, d5, d6, d7} | {d3, d4, d5, d6, d7} |
B4 | {d1, d2, d3, d4, d5, d6, d7} | {d1, d2, d4, d5, d6, d7} |
B5 | {d1, d2, d4, d5, d6, d7} | {d1, d4, d6, d7, d8} |
Using the result: use-definition chains
A ud-chain lists, for a use of a variable, the definitions that reach it. Read it off IN[B] (plus earlier statements of the same block):
The use of
iint = i * 2(B2) is reached by d1 (i = 0) and d6 (i = i + 1). Two different definitions, so i is not a constant there.The use of
min B2 is reached by d3 and d7.The use of
tin B3 is reached only by d4.
The reverse, a du-chain, lists for each definition the uses it can reach. Both are used by constant propagation, copy propagation and code motion.
2. Live Variable Analysis
A variable x is live at a point p if the value of x at p may be used along some path starting at p before x is redefined. Otherwise x is dead at p.
Why we care: a register holding a dead variable can be reused for something else (register allocation), an assignment to a variable that is dead right after it is dead code, and a dead variable never needs to be stored back to memory at the end of a block.
Liveness looks into the future ("will this be used later?"), so it is a backward analysis: information flows from a block's successors to the block. "Used along some path" makes it a may analysis with union as the meet.
use and def
use[B]: variables used in B before any assignment to them in B (their value comes from outside B).
def[B]: variables assigned in B. (Strictly, the definition is "assigned in B before any use in B", but many books simply take all variables assigned in B. Both give the same IN[B], because a variable that is used before being assigned is already in use[B].)
Block | use[B] | def[B] | Reason |
|---|---|---|---|
B1 | {n} | {i, s, m} | n read in m = n - 1 |
B2 | {i, m} | {t} | t is assigned before it is tested |
B3 | {s, t, i} | {s, i} | s and i are read before being written |
B4 | {m, i} | {m} | m read in m = m - 1 |
B5 | {s, i} | {s} | s = s + i reads both |
The equations
IN[EXIT] = { }
OUT[B] = ∪ IN[S] over all successors S of B
IN[B] = use[B] ∪ (OUT[B] − def[B])"x is live on entry to B if B reads it before writing it, or if it is live on exit from B and B does not overwrite it."
Iterations
All IN sets start empty. Since the information flows backward, we visit blocks in reverse order: B5, B4, B3, B2, B1.
Block | Pass 1: OUT | Pass 1: IN | Pass 2: OUT | Pass 2: IN | Pass 3 |
|---|---|---|---|---|---|
B5 | { } | {i, s} | { } | {i, s} | no change |
B4 | {i, s} | {i, m, s} | {i, m, s} | {i, m, s} | no change |
B3 | { } | {i, s, t} | {i, m, s} | {i, m, s, t} | no change |
B2 | {i, m, s, t} | {i, m, s} | {i, m, s, t} | {i, m, s} | no change |
B1 | {i, m, s} | {n} | {i, m, s} | {n} | no change |
In pass 1, OUT[B4] = IN[B2] ∪ IN[B5] = { } ∪ {i, s}, because B2 has not been visited yet. In pass 2 the loop information arrives: IN[B2] = {i, m, s} flows into OUT[B4] and OUT[B3].
What the result tells us
t is live only between B2 and B3. On the B2 → B4 path t is dead, so a register holding t can be reused right after the test on that path.
m is dead on entry to B5 (IN[B5] = {i, s}). If m lived in a register, it would not need to be saved at the end of B4 on that path.
Only n is live on entry to the program. If some other variable showed up in IN[B1], it would be read before being assigned on some path: a possible "uninitialised variable" bug.
3. Available Expressions
An expression x op y is available at a point p if every path from the entry to p evaluates x op y, and after the last such evaluation on each path, neither x nor y is assigned.
Why we care: if b * c is available where we are about to compute b * c, the computation is redundant, and global common subexpression elimination can reuse the earlier result.
"On every path" makes it a must analysis, so the meet is intersection. It is a forward analysis.
e_gen[B]: expressions computed in B whose operands are not assigned afterwards in B.
e_kill[B]: expressions (anywhere in the program) with an operand assigned in B, unless recomputed later in B.
Note that for a = a - 1, the expression a - 1 is computed and then immediately killed by the assignment to a, so it is not generated.
Example
B1: a = b + c Edges: B1→B2, B2→B3, B3→B2 (loop), B2→B4
d = b * c
B2: e = a - d Universe of expressions U = {b+c, b*c, a-d, a-1}
if e <= 0 goto B4
B3: a = a - 1
goto B2
B4: f = b * c
g = b + cBlock | e_gen | e_kill |
|---|---|---|
B1 | {b+c, b*c} | {a-d, a-1} |
B2 | {a-d} | { } |
B3 | { } | {a-d, a-1} |
B4 | {b+c, b*c} | { } |
OUT[ENTRY] = { }
IN[B] = ∩ OUT[P] over all predecessors P of B
OUT[B] = e_gen[B] ∪ (IN[B] − e_kill[B])
Initialisation: OUT[B] = U for every block except the entryBlock | Pass 1: IN | Pass 1: OUT | Pass 2 |
|---|---|---|---|
B1 | { } | {b+c, b*c} | no change |
B2 | OUT[B1] ∩ OUT[B3] = {b+c, b*c} ∩ U = {b+c, b*c} | {b+c, b*c, a-d} | no change |
B3 | {b+c, b*c, a-d} | {b+c, b*c} | no change |
B4 | {b+c, b*c, a-d} | {b+c, b*c, a-d} | no change |
So on entry to B4, both b * c and b + c are available. b and c are never changed in the loop, so the values computed in B1 are still valid. It is tempting to rewrite B4 as f = d and g = a, but g = a is wrong: a holds b + c only until B3 changes it. The expression b + c is available, but the variable a may no longer hold its value. Global CSE handles this by saving the value into a fresh temporary at its computation (u = b + c; a = u in B1) and then using g = u in B4. For b * c, d is never reassigned, so f = d is fine (or use a temporary in the same way).
Why initialise to U and not to the empty set?
If we start with OUT[B] = { } for all blocks, then in pass 1, IN[B2] = OUT[B1] ∩ OUT[B3] = {b+c, b*c} ∩ { } = { }. Nothing in the loop generates b+c or b*c, so they never get back in. The iteration settles at IN[B4] = {a-d} only. We computed this too:
Initialisation | Final IN[B2] | Final IN[B4] |
|---|---|---|
OUT[B] = U (correct) | {b+c, b*c} | {a-d, b*c, b+c} |
OUT[B] = { } | { } | {a-d} |
Starting from { } is not unsafe, but it is needlessly pessimistic: it loses expressions whose only "justification" goes round a loop. For an intersection (must) analysis we start from the top, "everything is available", and let the equations remove what is not. For union (may) analyses we start from the bottom, { }, and let the equations add what is needed.
The General Framework
All these analyses fit one pattern: a direction, a meet operator, a transfer function and initial values. Once a compiler has a generic iterative solver, a new analysis is just a new row in this table.
Point | Reaching definitions | Live variables | Available expressions | Very busy (anticipated) expressions |
|---|---|---|---|---|
Facts | Sets of definitions | Sets of variables | Sets of expressions | Sets of expressions |
Direction | Forward | Backward | Forward | Backward |
May / must | May (some path) | May (some path) | Must (all paths) | Must (all paths) |
Meet | ∪ | ∪ | ∩ | ∩ |
Transfer | OUT = gen ∪ (IN − kill) | IN = use ∪ (OUT − def) | OUT = e_gen ∪ (IN − e_kill) | IN = e_use ∪ (OUT − e_kill) |
Boundary | OUT[ENTRY] = { } | IN[EXIT] = { } | OUT[ENTRY] = { } | IN[EXIT] = { } |
Initial value | OUT[B] = { } | IN[B] = { } | OUT[B] = U | IN[B] = U |
Main use | Constant propagation, ud-chains, uninitialised-variable detection | Register allocation, dead code elimination | Global common subexpression elimination | Code hoisting, partial redundancy elimination |
An expression is very busy at a point if, on every path from that point, it is evaluated before any of its operands is changed. Such an expression can safely be computed early ("hoisted") at that point, which can shrink code.
Why does the iteration always stop?
For these analyses the transfer functions are monotone: a bigger input never gives a smaller output. In a union analysis that starts from { }, every set can only grow from pass to pass; in an intersection analysis that starts from U, every set can only shrink. Each set is a subset of a finite universe (all definitions, all variables, all expressions), so it can change only a finite number of times. Hence the loop terminates. In practice, visiting blocks in a good order (reverse postorder for forward problems, the opposite for backward problems) makes it settle in a few passes, as in our examples.
Solved Problems
Problem 1: Liveness inside a block
No variable is live after statement 5. Find the live variables just before each statement.
1: a = b + c
2: d = a * 2
3: b = d - e
4: a = b + d
5: print(a, e)Solution. Go backwards, applying live_before = uses ∪ (live_after − defined variable).
Stmt | Live after | Defines | Uses | Live before |
|---|---|---|---|---|
5 | { } | - | a, e | {a, e} |
4 | {a, e} | a | b, d | {b, d, e} |
3 | {b, d, e} | b | d, e | {d, e} |
2 | {d, e} | d | a | {a, e} |
1 | {a, e} | a | b, c | {b, c, e} |
Notice that b is live before statement 1 but dead after it, even though b appears again in statement 4: statement 3 redefines b first. At most 3 variables are live at any point (just before statement 1, and between statements 3 and 4), which hints that 3 registers are enough for this block if values are kept in registers.
Problem 2: Reaching definitions question
In the running example, which definitions of s reach the statement s = s + i in B5?
Solution. IN[B5] = {d1, d2, d4, d5, d6, d7}. The definitions of s are d2, d5 and d8; of these, d2 (s = 0) and d5 (s = s + t) reach B5. d2 reaches along B1 → B2 → B4 → B5 (the loop body B3 never runs), d5 along any path through B3.
Problem 3: Is an expression available?
B1: x = p + q B1 → B2, B1 → B3, B2 → B4, B3 → B4
B2: p = 1
B3: y = p + q
B4: z = p + qIs p + q available at the start of B4?
Solution. OUT[B2] = { } because p = 1 kills p + q. OUT[B3] = {p+q}. IN[B4] = OUT[B2] ∩ OUT[B3] = { }. Not available: along B1 → B2 → B4 the old value is stale. (p + q is partially redundant: redundant on one path only. Partial redundancy elimination would insert a computation in B2 to make it fully redundant.)
Problem 4: Choose the analysis
Goal | Analysis |
|---|---|
Warn about use of an uninitialised variable | Reaching definitions (no definition reaches a use) or liveness on entry |
Decide if two variables can share one register | Live variables |
Remove a recomputation of a * b in another block | Available expressions |
Replace x by a constant | Reaching definitions (or constant propagation analysis) |
Delete an assignment whose value is never read | Live variables |
Common Mistakes
Using the wrong direction. Liveness is about the future, so it is backward; reaching definitions and available expressions are about the past, so they are forward.
Using the wrong meet. "Some path" (may) = union; "all paths" (must) = intersection.
Initialising a must analysis to the empty set. Start available expressions at U (except the entry), or you lose facts around loops.
Putting every assigned variable's definitions into gen. Only the last definition of each variable in a block is in gen[B].
Getting use[B] wrong. In
t = i * 2followed byif t > m, t is not in use[B]: it is assigned before it is read.Forgetting that x = x op y kills x op y. In
a = a - 1, a - 1 is not available afterwards.Stopping after one pass. With loops, values must flow around back edges. Iterate until a full pass changes nothing.
Confusing "expression available" with "variable still holds it". Use a temporary when applying global CSE.
Interview and Exam Questions
What is data-flow analysis used for?
To compute facts that hold at each program point over all paths, such as which definitions reach a point, which variables are live, and which expressions are available. Global optimizations and register allocation rely on these facts to be safe.
Write the data-flow equations for reaching definitions.
IN[B] = ∪ OUT[P] over predecessors P; OUT[B] = gen[B] ∪ (IN[B] − kill[B]); OUT[ENTRY] = { }; initialise all OUT to { }.
Why is live variable analysis a backward analysis?
Whether a variable is live depends on future uses, i.e. on what happens along paths after the point. Information flows from successors to predecessors: OUT[B] = ∪ IN[S], IN[B] = use[B] ∪ (OUT[B] − def[B]).
What is the difference between a may and a must analysis?
A may analysis records facts true on at least one path (meet = union, e.g. reaching definitions, liveness). A must analysis records facts true on every path (meet = intersection, e.g. available expressions).
Why must available expressions start from the universal set?
Intersection can only remove facts. Starting from { } would make IN at a loop header empty in the first pass, and expressions not regenerated in the loop would never return, giving an unnecessarily small result.
What is a ud-chain?
For a use of a variable, the list of definitions of that variable that reach it. It is derived from reaching definitions and used for constant and copy propagation.
Does the iterative algorithm always terminate?
Yes, for monotone transfer functions over finite sets: the sets only grow (union analyses from { }) or only shrink (intersection analyses from U), and they can change only finitely many times.
How is liveness used in register allocation?
Two variables that are live at the same point interfere and need different registers. Liveness builds the interference graph that the register allocator colours (see Code Generation & Register Allocation).
Summary
Data-flow analysis computes facts at every point using IN/OUT equations per block, a transfer function and a meet operator, solved by iterating until nothing changes.
Reaching definitions: forward, union, OUT = gen ∪ (IN − kill). In our example the use of i in B2 is reached by both d1 and d6, so i is not constant there.
Live variables: backward, union, IN = use ∪ (OUT − def). Drives register allocation and dead code elimination.
Available expressions: forward, intersection, initialised to U. Drives global common subexpression elimination.
Very busy expressions: backward, intersection; used for hoisting.
Bit vectors make the set operations fast; monotonicity and finite sets guarantee termination.
Once the global optimizations are done, the compiler still cleans up small local patterns in the target code. That is the topic of the next chapter, Peephole Optimization.