Local optimisation; data flow analyses

Basic blocks and control-flow graphs

Definition. A basic block is a maximal straight-line sequence with one entry and one exit: control enters at its first instruction and leaves at its last. A control-flow graph (CFG) has basic blocks as nodes and an edge for each possible transfer of control.

Example. A conditional branch creates edges from its block to the then and else blocks.

Exam point. A leader is the first instruction, a branch target, or the instruction following a branch; leaders partition code into blocks.

Solved examples

Example 1 — find leaders. Instructions: 1 assign, 2 conditional jump to 5, 3 assign, 4 jump to 6, 5 assign, 6 return.

1. Instruction 1 is a leader.
2. Target 5 is a leader.
3. Instruction 3 follows conditional jump 2, so 3 is a leader.
4. Instruction 6 follows jump 4 and is also its target.
5. Leaders: 1,3,5,6; blocks are [1–2],[3–4],[5],[6].

Local common subexpression elimination

Definition. Within a basic block, an expression can be reused if it was computed earlier and its operands have not changed. A later assignment to an operand kills the expression's available value. Algebraic equivalence alone does not guarantee reuse unless the compiler's arithmetic semantics allow it.

Example. t1=a+b; x=a+b can reuse t1 if neither a nor b changes between the statements.

Exam point. Reuse is invalid after redefining an operand.

Solved examples

Example 1 — eliminate a repeated expression. Code: t1=a*b; c=a*b; d=t1+c.

1. First statement computes expression a*b into t1.
2. No assignment changes a or b before the second statement.
3. Replace c=a*b with c=t1.
4. Optimized: t1=a*b; c=t1; d=t1+c.

Example 2 — operand redefinition. Code: t1=a+b; a=7; c=a+b.

1. First a+b uses the old value of a.
2. Assignment a=7 changes an operand.
3. The old expression value no longer represents the new a+b.
4. Do not replace the final computation with t1.

DAG representation of a basic block

Definition. A directed acyclic graph represents computations in a basic block. Leaves represent input values; internal nodes represent operations; variable labels are attached to the node holding their current value. The graph exposes repeated expressions and dead computations.

Example. For a=b+c; d=b+c, one plus node can carry both labels a and d.

Exam point. Variable reassignment moves a variable label to a new value node; it does not mutate the old expression's meaning.

Solved examples

Example 1 — construct a DAG. Statements: x=a+b; y=x*c; z=a+b.

1. Create leaves for current values a,b,c.
2. Create plus node P=(a+b), label it x.
3. Create multiply node M=(P*c), label it y.
4. For z=a+b, find existing node P and add label z.
5. Only one addition node is needed.

Example 2 — reassignment. Code x=a+b; a=c+d; y=a+b.

1. First plus node uses the original a and b leaves.
2. Assignment to a changes its current-value label to node c+d.
3. The final a+b uses the new a value, so it is a different plus node.
4. The two plus expressions are not common.

Constant propagation

Definition. Constant propagation replaces a variable use by a constant when every path reaching that use gives the same known constant. A standard lattice has values UNDEF (no information yet), a constant c, and NAC (not a constant / conflicting values). Merging different constants yields NAC; NAC is absorbing under merge.

Lattice value	Meaning
UNDEF	no definition has contributed yet
c	value is known to be constant c
NAC	value is not one known constant

Example. If one predecessor gives x=3 and another gives x=3, the join remains 3; if they give 3 and 4, the join is NAC.

Exam point. A branch merge preserves a constant only when all reachable incoming facts agree.

Solved examples

Example 1 — one block transfer. Start with a=4,b=UNDEF. Execute b=a+2; c=b*3.

1. Before first statement, a=4.
2. b=a+2 evaluates to 6, so b=6.
3. c=b*3 evaluates to 18.
4. Out facts: a=4,b=6,c=18.

Example 2 — merge at a join. If branch 1 sets x=5 and branch 2 sets x=5, determine x at the join. Then change branch 2 to x=8.

1. Join equal constants: 5⊔5=5.
2. With the changed branch, 5⊔8=NAC.
3. x is constant 5 in the first case, not a known constant in the second.

Example 3 — propagate through a CFG. Entry sets x=2; block B1 sets y=x+3; B1 branches to B2 and B3; B2 leaves z unchanged; B3 sets z=y*2; B4 joins and computes w=y+z.

1. At B1, x=2, so y=5.
2. At B2, assume z has entry value 10; at B3, z becomes 10 from 5*2.
3. Both paths give z=10, so B4's join has y=5,z=10.
4. w=5+10=15 is constant.
5. The result is path-independent because both branches agree on z.

Data-flow equations and fixed points

Definition. A forward data-flow analysis computes facts flowing from predecessors. Equations often have IN[B]=join(OUT[P]) and OUT[B]=GEN[B]∪(IN[B]−KILL[B]). Iteration continues until values stop changing; finite lattices and monotone transfer functions guarantee convergence under standard conditions.

Example. Reaching definitions is a forward may-analysis; its join is union.

Exam point. Direction, join operator, GEN, KILL, and boundary conditions define the analysis.

Solved examples

Example 1 — reaching definitions. Definitions d1: x=1 in B1, d2: x=2 in B2; B3 is reached from both. Compute IN[B3].

1. OUT[B1] contains d1; OUT[B2] contains d2.
2. A may-analysis joins predecessor sets by union.
3. IN[B3]={d1,d2}.
4. Either definition may reach B3.

Example 2 — kill a definition. B3 executes d3: x=9. Find OUT[B3] for reaching definitions.

1. d3 generates a new definition of x.
2. It kills prior definitions of x, d1 and d2.
3. OUT[B3]=(IN[B3]−{d1,d2})∪{d3}={d3}.
4. Only d3 reaches the end of B3 for x.