Chapter 31 of 33

Data-Flow Analysis

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→B5

Block

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 changed

With 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 i in t = 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 m in B2 is reached by d3 and d7.

  • The use of t in 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 + c

Block

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 entry

Block

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 + q

Is 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 * 2 followed by if 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.