Local Optimisation & Data Flow Analysis

An optimising compiler rewrites code to make it faster or smaller, and the constraint on every rewrite is the same.

A transformation is legal only if it preserves the program's observable behaviour on every input, not merely on the inputs the compiler happened to think about. That requirement is why optimisation needs analysis at all: the compiler must prove a fact about all executions before it may act.

Data-flow analysis is how that proof is computed. It answers questions of the form "what is guaranteed to be true at this point in the program", and each classical analysis answers one such question.

The second organising fact is that every data-flow analysis is defined by four choices: the direction it propagates, the facts it tracks, how it combines facts arriving from several predecessors, and what it does at each statement.

Once those four are fixed, the analysis writes itself, and the differences between reaching definitions, available expressions and live variables are entirely differences in those four choices.

The third is that the scope of an optimisation determines what it may assume. Within a basic block, control flows straight through and everything is known. Across blocks, control may arrive from several places and the compiler must consider all of them.

1. Basic Blocks and the Flow Graph

A basic block is a maximal sequence of instructions with one entry at the top and one exit at the bottom. No jump enters the middle and no jump leaves except at the end.

Blocks are found by identifying leaders, the first instruction of each block.

Three rules identify a leader. The first instruction of the program is one. Any target of a jump is one. Any instruction immediately following a jump is one.

Each block then runs from a leader up to but not including the next leader.

The flow graph has one node per basic block and an edge wherever control can pass from the end of one block to the start of another. Adding an entry and an exit node makes the graph self-contained.

Within a block, analysis is exact. There are no branches, so every instruction executes in order exactly once, and a fact established at one point holds at every later point until something changes it. That is what makes local optimisation cheap.

2. Local Optimisations

Seven transformations apply within a basic block, and each is examined by name.

Constant folding evaluates an expression whose operands are known constants at compile time. Replacing $3\times 4$ with $12$ removes a run-time multiplication.

Constant propagation replaces a variable with its value when that value is a known constant. It typically enables further folding, and the two are applied alternately until nothing changes.

Common subexpression elimination replaces a recomputation with a reference to the earlier result. It is legal only if no operand has changed in between, which the block's straight-line structure makes easy to check.

Copy propagation replaces a variable with the one it was copied from, so that after $x=y$ later uses of $x$ become uses of $y$. It rarely helps directly but exposes dead code.

Dead code elimination removes computations whose results are never used. It is usually the last step, because the other transformations create dead code as a side effect.

Strength reduction replaces an expensive operation with a cheaper equivalent. Multiplication by 2 becomes a shift, and a multiplication inside a loop becomes an addition.

Algebraic simplification applies identities: adding zero, multiplying by one, and similar cases disappear entirely.

The order matters and the transformations feed each other. Constant propagation enables folding, folding enables more propagation, copy propagation creates dead copies, and dead code elimination removes them. Real optimisers iterate until a pass changes nothing.

3. The DAG for a Basic Block

A directed acyclic graph represents a basic block with one node per computed value.

When an expression is constructed, the builder first checks whether a node with the same operator and the same children already exists, and reuses it if so. That check performs common subexpression elimination during construction, with no separate analysis.

Leaves are initial values of variables; interior nodes are operations. A variable name attaches to whichever node currently holds its value, so an assignment moves the label rather than creating a node.

Reading the DAG back out gives optimised code. Any node with no attached name and no parent is dead and its computation is simply omitted.

The DAG also reveals which expressions are worth keeping in registers, since a node with several parents is used several times.

One caution: pointer assignments and function calls invalidate the DAG's assumptions, because either may modify a variable the compiler cannot track. Real implementations conservatively kill the affected nodes at such points.

4. Global Data-Flow Analysis

Beyond a basic block, control may reach a point from several predecessors, and the compiler must account for all of them.

Every analysis is specified by four choices.

Direction: forward analyses propagate information along control flow; backward analyses propagate against it.

Domain: what facts are tracked — definitions, expressions, or variables.

Meet operator: how facts from several paths combine. Union gives a may analysis, asserting something holds on at least one path. Intersection gives a must analysis, asserting it holds on every path.

Transfer function: how a block changes the facts, usually expressed as generating some and killing others.

The equations take a standard shape. For a forward analysis:

$\text{IN}[B]={⨆}_{P\in \text{pred}(B)}\text{OUT}[P]$

$\text{OUT}[B]=\text{GEN}[B]\cup (\text{IN}[B]-\text{KILL}[B])$

The solution is computed iteratively: initialise, apply the equations repeatedly, and stop when nothing changes. Convergence is guaranteed because the facts form a finite lattice and each iteration only moves in one direction.

The result is a conservative approximation, not exact truth. A may analysis over-approximates and a must analysis under-approximates, and both err in the direction that keeps transformations safe.

5. The Four Classical Analyses

Reaching definitions supports constant propagation and use-definition chains. It is a may analysis because a definition reaching along any path must be considered.

Available expressions supports global common subexpression elimination. It is a must analysis because reusing a previous result requires that it was computed on every path, not merely one.

Live variables supports dead code elimination and register allocation. A variable dead at a point need not be kept in a register, and an assignment to a dead variable can be removed. It is backward because liveness depends on future uses, and a may analysis because a use on any path keeps the variable live.

Very busy expressions supports code hoisting, moving a computation earlier when it will certainly be needed.

The pattern is worth extracting. Analyses that justify removing work need must-information, because removal must be safe on every path. Analyses that justify keeping something need may-information, because any path that uses it forces retention.

6. Loop Optimisations

Loops repay optimisation disproportionately because their bodies execute many times.

A natural loop is identified from the flow graph using dominators. A node $d$ dominates $n$ if every path from entry to $n$ passes through $d$. A back edge runs from a node to one of its dominators, and the natural loop of that back edge is the set of nodes that can reach its source without passing through its target.

Loop-invariant code motion moves a computation whose operands do not change inside the loop out to a preheader block placed before the loop. The computation must be guaranteed to execute, or moving it could introduce a fault or a cost the original never paid.

Induction variable elimination recognises variables advancing by a constant each iteration and expresses them in terms of one another, often removing all but one.

Strength reduction within a loop replaces a multiplication by an induction variable with an addition. An array address computed as a base plus $4i$ becomes a running pointer incremented by 4.

Loop unrolling replicates the body to reduce the per-iteration test and branch overhead, at the cost of code size and possibly instruction cache pressure.

Loop fusion merges two loops over the same range so that the data is traversed once, improving locality. Loop fission does the reverse when the merged body causes register pressure.

7. Worked Examples

Example 1. Identify the basic blocks in this code.

1:  i = 0
2:  t = i * 4
3:  if i >= n goto 8
4:  a[t] = 0
5:  i = i + 1
6:  t = i * 4
7:  goto 3
8:  return

Apply the three leader rules.

Instruction 1 is a leader, being the first instruction of the program.

Instruction 3 is a leader, being the target of the goto at instruction 7.

Instruction 4 is a leader, immediately following the conditional jump at 3.

Instruction 8 is a leader, both as the target of the branch at 3 and as the instruction following the jump at 7.

Each block runs from a leader to just before the next.

Block A: instructions 1 and 2. Block B: instruction 3. Block C: instructions 4 through 7. Block D: instruction 8.

The flow graph has an edge from A to B, from B to C on the false branch, from B to D on the true branch, and from C back to B.

The edge from C to B is a back edge, since B dominates C — every path from entry to C passes through B. The natural loop is therefore the set containing B and C.

Example 2. Optimise this basic block, naming each transformation applied.

a = 5
b = a * 4
c = b + a * 4
d = c * 1
e = d + 0

Constant propagation replaces $a$ with 5 in each use, since $a$ is assigned a constant and never reassigned.

a = 5
b = 5 * 4
c = b + 5 * 4
d = c * 1
e = d + 0

Constant folding evaluates $5\times 4$ at compile time in both places.

a = 5
b = 20
c = b + 20
d = c * 1
e = d + 0

Algebraic simplification removes the multiplication by one and the addition of zero.

a = 5
b = 20
c = b + 20
d = c
e = d

Copy propagation replaces $d$ with $c$ and then $e$ with $c$.

a = 5
b = 20
c = b + 20
d = c
e = c

Constant propagation and folding again, since $b$ is now a known constant.

a = 5
b = 20
c = 40
d = c
e = c

Dead code elimination removes any assignment whose target is never used afterwards. If only $e$ is live at the block's exit, then $a$, $b$ and $d$ are all dead.

c = 40
e = c

And a final copy propagation plus dead code pass leaves e = 40.

Note the iteration. Each transformation exposed work for another, which is why real optimisers repeat the whole sequence until a pass changes nothing.

Example 3. Why is available expressions an intersection analysis while reaching definitions is a union analysis?

Available expressions justifies removing a computation, replacing it with a reference to a previously computed value.

For that to be safe, the expression must already have been computed on every path reaching this point, with no operand modified since. If even one path arrives without having computed it, the reference would read a value that was never produced.

Safety therefore requires the fact to hold on all paths, which is intersection.

Reaching definitions justifies keeping information about a variable's possible values.

A definition reaches a point if there is some path along which it is the most recent assignment. If a use might see that definition on any path, the analysis must report it, because ignoring it could lead the compiler to substitute a value that is wrong on that path.

Safety therefore requires including anything possible on any path, which is union.

The general principle is that the direction of conservatism follows the use. An analysis supporting removal must under-approximate — claim less than may be true — so it never removes something that was needed. An analysis supporting retention must over-approximate — claim more than may be true — so it never discards something that was needed.

Live variables follows the same logic: it is a union analysis because a use on any path forces the variable to be kept.

Example 4. Perform loop-invariant code motion on this loop and state the safety condition.

i = 0
L: if i >= n goto END
   x = y * z
   a[i] = x + i
   i = i + 1
   goto L
END:

The computation $y\times z$ uses only $y$ and $z$, neither of which is assigned anywhere inside the loop. It therefore computes the same value on every iteration and is loop-invariant.

Move it to a preheader, a block inserted between the loop entry and the header.

i = 0
x = y * z
L: if i >= n goto END
   a[i] = x + i
   i = i + 1
   goto L
END:

The multiplication now executes once instead of $n$ times.

The safety condition is that the moved computation must be guaranteed to execute in the original program.

Here that fails in one case: if $n$ is zero or negative, the original loop body never runs and $y\times z$ is never computed. The transformed version computes it unconditionally.

For a multiplication that is harmless — the result is simply discarded. But if the computation could fault, such as a division that might divide by zero, or a memory access that might be out of bounds, then hoisting it introduces a fault the original program did not have.

The standard remedies are to hoist only computations that cannot fault, or to guard the preheader with a test that the loop executes at least once.

Example 5. Apply strength reduction and induction variable elimination to an array-indexing loop.

i = 0
L: if i >= n goto END
   t = i * 4
   p = base + t
   *p = 0
   i = i + 1
   goto L
END:

Recognise $i$ as a basic induction variable, since it increases by the constant 1 each iteration.

Recognise $t$ as a derived induction variable, since it is always $4i$. Because $i$ increases by 1 per iteration, $t$ increases by 4.

Strength reduction replaces the multiplication with an addition. Initialise $t$ before the loop and increment it inside.

i = 0
t = 0
L: if i >= n goto END
   p = base + t
   *p = 0
   i = i + 1
   t = t + 4
   goto L
END:

The multiplication is gone, replaced by an addition, which is cheaper on most machines.

Now $p$ is also a derived induction variable, always equal to $\text{base}+t$, so the same treatment applies.

p = base
limit = base + n * 4
L: if p >= limit goto END
   *p = 0
   p = p + 4
   goto L
END:

Induction variable elimination has removed $i$ and $t$ entirely, replacing the loop counter with the pointer itself and rewriting the termination test in terms of it.

The body now contains one store, one addition and one comparison, against the original's multiplication, two additions, a store and a comparison.

Example 6. Compute live variables at each point in this block, and state which assignments are dead.

1: a = b + c
2: d = a * 2
3: a = e + f
4: g = a + d

Live variable analysis runs backward, starting from the block's exit.

Assume only $g$ is live at the exit.

After instruction 4: $\{g\}$.

Before instruction 4, which uses $a$ and $d$ and defines $g$: remove $g$ from the live set because it is defined here, then add $a$ and $d$ because they are used. Live set is $\{a,d\}$.

Before instruction 3, which uses $e$ and $f$ and defines $a$: remove $a$, add $e$ and $f$. Live set is $\{d,e,f\}$.

Before instruction 2, which uses $a$ and defines $d$: remove $d$, add $a$. Live set is $\{a,e,f\}$.

Before instruction 1, which uses $b$ and $c$ and defines $a$: remove $a$, add $b$ and $c$. Live set is $\{b,c,e,f\}$.

Now check for dead assignments. An assignment is dead if its target is not live immediately after it.

Instruction 1 defines $a$. The live set after instruction 1 is $\{a,e,f\}$, which contains $a$, so this assignment is live — its value is used by instruction 2.

Instruction 2 defines $d$, and $d$ is live after it, so it is live.

Instruction 3 defines $a$, and $a$ is live after it, so it is live. Note that this $a$ is a different value from instruction 1's; the earlier one was already consumed.

Instruction 4 defines $g$, which is live at exit, so it is live.

No assignment is dead here. Had $g$ not been live at exit, instruction 4 would be dead, which would in turn kill instructions 3 and 2, and then 1 — a cascade that is exactly why dead code elimination is iterated.

Summary

An optimisation is legal only if it preserves observable behaviour on every input, and data-flow analysis is how that fact is proved rather than assumed.

A basic block has one entry and one exit. Leaders are the first instruction, any jump target, and any instruction after a jump. The flow graph joins blocks wherever control can pass.

Within a block, analysis is exact because control flows straight through. Constant folding, constant propagation, common subexpression elimination, copy propagation, dead code elimination, strength reduction and algebraic simplification all apply, and they feed each other, so the sequence is iterated.

A DAG for a basic block performs common subexpression elimination during construction, by reusing any node with the same operator and children. Nodes with no name and no parent are dead. Pointer writes and calls invalidate the assumptions and force conservative killing.

Every data-flow analysis is fixed by four choices: direction, domain, meet operator and transfer function. Union gives a may analysis and intersection a must analysis, and the solution is found by iterating to a fixed point.

Reaching definitions is forward and union; available expressions forward and intersection; live variables backward and union; very busy expressions backward and intersection.

Analyses justifying removal need must-information because removal must be safe on every path. Analyses justifying retention need may-information because any path that uses something forces keeping it.

Natural loops are found from dominators and back edges. Loop-invariant code motion needs the computation to be guaranteed to execute, or a faulting operation could be introduced. Strength reduction turns a multiplication by an induction variable into an addition, and induction variable elimination can remove the counter entirely.