Skip to content
Tutorials Center
My learning

Topics

Lesson 38 of 61 ยท Intermediate Code and Optimization

Data-Flow Analysis

Learn data-flow analysis: reaching definitions, live variables and available expressions, solved with a worklist algorithm in runnable Python.

Local optimizations look at one basic block at a time. They cannot tell whether a variable assigned in one block is still needed in another, or whether an expression computed before an if is still valid after it. To answer questions that span the whole control flow graph, compilers use data-flow analysis: they compute facts about every program point by pushing information along the edges of the graph until nothing changes any more.

This lesson shows the idea once in general form and then four concrete analyses: live variables, reaching definitions, available expressions and very busy expressions. Each one answers a question an optimizer needs, such as "can I delete this assignment?" or "can I reuse this earlier result?". You will run a worklist solver that is short enough to read in one sitting.

The shape of every data-flow problem

A data-flow analysis needs four ingredients:

  1. A domain of facts, usually a set (a set of variables, of definitions, of expressions).
  2. A direction: forward (facts flow from the entry along the edges) or backward (from the exits against the edges).
  3. A transfer function per block that says how the block changes the facts: OUT = gen โˆช (IN โˆ’ kill) for a forward problem.
  4. A meet operator that combines facts where paths join: union ("may" problems, true on some path) or intersection ("must" problems, true on all paths).
Analysis Direction Meet Question answered
Reaching definitions forward union Which assignments might provide the value of x here?
Live variables backward union Might x be read later before it is overwritten?
Available expressions forward intersection Has a + b definitely been computed on every path, with unchanged operands?

Because a loop makes facts depend on themselves, the solver starts from a safe initial guess and iterates until a fixed point. It terminates because the sets only grow (or only shrink), and a finite domain cannot grow forever.

flowchart TD
    B1["B1<br/>a = 1; i = 0; s = 0"] --> B2["B2<br/>t = i #lt; 10; branch t"]
    B2 --> B3["B3<br/>s = s + a; i = i + 1"]
    B3 --> B2
    B2 --> B4["B4<br/>print s"]

A loop in a control flow graph. Facts about s and i must travel around the back edge until they stop changing.

Live variable analysis

A variable is live at a point if its current value might be read later, before any new assignment overwrites it. Liveness is a backward analysis. For each block compute:

  • use: variables read before being assigned inside the block (they must be live on entry),
  • def: variables assigned in the block.

Then live_out(B) is the union of live_in of all successors, and live_in(B) = use(B) โˆช (live_out(B) โˆ’ def(B)).

Liveness powers two important optimizations. A store to a variable that is dead right after the assignment can be deleted (dead-store elimination). And the number of variables live at the same time decides how many registers you need, which is the topic of register allocation.

The program below is the loop from the diagram, plus a useless assignment dead = 99. The solver keeps a worklist of blocks that must be (re)computed. When a block's live_in changes, only its predecessors are added again.

Python Live variables with a worklist

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Read the table. a, i and s are live at the loop header B2 because the loop body reads them, even though B2 itself only uses i. They stay live all the way back to the exit of B1. The variable dead is never read, so it is not live after its assignment and the second part of the output flags it. The solver needed only five steps because the blocks were visited in a good order (successors first, which is the natural order for a backward problem) and the back edge forced one extra visit.

Inside a block, the same recurrence runs one instruction at a time: walk the lines from last to first, remove the variable defined by the line, then add the variables it reads. That is exactly what the second loop in the code does.

Reaching definitions and available expressions

A definition is an assignment, such as x = a + b at some label. A definition reaches a point if there is a path from the definition to that point on which x is not reassigned. Reaching definitions answer "where could this value have come from?", which is what constant propagation, copy propagation and many loop optimizations need. The analysis is forward with union, because one path is enough.

An expression a + b is available at a point if on every path to that point it has been computed and neither a nor b has been assigned since. If it is available, a later computation of a + b is redundant and can reuse the earlier value. This is a must-analysis, so the meet is intersection, and the safe starting guess for the not-yet-visited blocks is the set of all expressions, not the empty set. (Starting from the empty set would make loops lose every fact.)

Both analyses fit one forward solver. Only the transfer function, the meet and the initial values differ. The program has a diamond shape: B1 branches to B2 and B3, which join in B4. The right branch reassigns a.

Python One solver, two analyses

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

In the reaching-definitions output, B4 is reached by two definitions of a: [email protected] and [email protected]. That is the signature of a join. Because a may come from either branch, the optimizer cannot replace a in B4 by a constant. For available expressions the answer is different. The expression c * d is available at B4, so u = c * d can become u = z. But a + b is not available at B4: on the path through B2 the assignment a = a + 1 kills it, and on the path through B3 the assignment a = 7 kills the copy computed in B1. Intersection means one bad path is enough to reject the fact.

Very busy expressions and code hoisting

The three analyses above are the classic ones, but there is a fourth that completes the set: very busy expressions (also called anticipated expressions). An expression e is very busy at a point if, on every path leaving that point, e is evaluated before any of its operands is reassigned. In other words, no matter which way the program goes, it will definitely compute e soon, so the compiler may as well compute it now.

Analysis Direction Meet Question answered
Very busy expressions backward intersection Will a + b certainly be computed on every path from here, with unchanged operands?

It is a backward must-analysis. Going backward through an instruction, first remove every expression that uses the assigned variable (the assignment kills it), then add the expression that the instruction evaluates (it is computed right there, so it is busy just before the instruction). For the exit block the set after it is empty, because nothing is computed afterwards. At a branch, the meet is intersection: the expression must be busy on all successors. As with available expressions, a must-analysis starts from the optimistic value "everything" for the blocks not yet visited.

The payoff is code hoisting: an expression that is very busy at the end of a block can be computed once there, and every later copy replaced by the temporary. It does not make the program faster (each path still computes the value once), but it reduces code size, which is why it is also called code-size optimization. Hoisting is safe because every path would have evaluated the expression anyway.

The program uses the diamond shape from before. Both branches compute a + b, and both paths end in B4, which computes c - d. One branch also computes a * 2, and the other overwrites a first.

Python Very busy expressions and hoisting

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The solver finishes in four steps. At the end of B1 two expressions are very busy: a + b (both branches compute it before a changes) and c - d (it is computed in B4, which every path reaches). The expression a * 2 is not very busy: it is computed on the B2 path, but the B3 path never computes it, so the intersection removes it. The rewrite puts t1 = a + b and t2 = c - d in B1 and replaces the later computations, so four written computations become three. Compare this with available expressions on the same diamond: available expressions look backward in time for a computation that already happened (so a later copy can be reused), while very busy expressions look forward in time for one that is certain to happen (so an earlier copy can be created).

Why the algorithm terminates and is correct

The iteration works because of two properties. The transfer functions are monotone: more incoming facts never lead to fewer outgoing facts. And the domain is a finite lattice (here, subsets of a finite set), so the values can change in one direction only a limited number of times. The result is the maximal fixed point solution, and it is a safe approximation: it may include a fact that is never true at run time (a path that cannot actually execute), but it never misses one that could be true. "Safe" depends on the analysis. For liveness, safe means "too many live variables" is acceptable and "too few" is a bug. For available expressions, safe means "too few" is acceptable and "too many" would be a miscompilation.

Visiting blocks in a smart order makes the solver faster. Forward problems converge quickly in reverse postorder, backward problems in postorder. Beyond that, textbook speed-ups use bit vectors for the sets, so union and intersection become one machine instruction per word.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. Which description matches live variable analysis?

    A variable is live if some path after the point reads it, so facts flow backward from uses and the meet at a branch is union.
  2. 2. Why is the initial value of the OUT sets set to all expressions in available-expressions analysis?

    Must-analyses start optimistic (everything available) and remove facts that some path breaks. Starting from the empty set would lose valid facts around back edges.
  3. 3. In the sample program the expression a + b is not available at B4. What is the reason?

    Both paths into B4 change a. An expression is available only if it is computed on every path and its operands are unchanged afterwards.
  4. 4. What does a worklist algorithm do when the IN or OUT set of a block changes?

    Only neighbours that read the changed set need to be recomputed. The loop ends when the worklist is empty, which is the fixed point.

Summary

  • Data-flow analysis computes facts at every program point by iterating over a control flow graph until a fixed point is reached.
  • Each analysis is defined by a domain, a direction, per-block transfer functions and a meet operator.
  • Live variables are backward/union and enable dead-store elimination and register allocation; reaching definitions are forward/union; available expressions are forward/intersection.
  • A worklist re-processes only blocks whose inputs changed, and monotone transfer functions over a finite lattice guarantee termination.
  • Very busy expressions are backward/intersection and enable code hoisting, which shrinks code by computing a certain-to-be-needed expression once, earlier.
  • Results must be safe: they may be conservative, but they must never allow a transformation that changes the program's behavior.

Next: Static Single Assignment