Basic blocks, DAGs and safe local optimization
Goal and semantic assumptions
Identify basic blocks and perform local rewrites without changing observable behavior. In the main worked example, variables are scalar mathematical integers, arithmetic is pure and nontrapping, and there are no pointers, calls, volatile operations or concurrency. Later sections explain why these restrictions matter. Optimization means preserving the specified language semantics, not merely making expressions look shorter.
1. Leaders, blocks and the control-flow graph
A basic block is a maximal straight-line instruction sequence entered only at its first instruction and exited only at its end. Standard leaders are the first instruction, every jump target, and every instruction immediately following a branch (when one exists). Partition at leaders. An edge connects a block to any block that may execute next; conditional branches can have a target edge and a fall-through edge. A return has no ordinary successor.
Worked numbered IR:
1: x=0 2: if p goto 5 3: x=1 4: goto 6 5: x=2 6: y=x+1 7: return y
Leaders are 1,3,5,6; blocks are [1,2], [3,4], [5], [6,7]. Edges are [1,2]→[5] and [1,2]→[3,4]; both latter blocks go to [6,7]. Line 5 falls through to line 6. A label alone need not create a branch, but an actual branch target starts a block. The value x=0 is overwritten on both paths before its use here; proving that fact uses more than just the first block in isolation.
2. Local common expressions and value identities
Within a block, t1=a+b followed by t2=a+b can reuse the first result if a and b still denote the same values and the operation is safe to reuse. A DAG node represents an operator applied to particular operand-value nodes; several variable names may label one node. After a=a+1, the name a refers to a new value node, so a+b is a different expression value even though the spelling is unchanged.
Worked block, with only a,t3,out live on exit:
t1=a+b t2=a+b a=a+1 t3=a+b dead=t2*0 out=t1+t2
First bind leaves a0,b0 to the incoming values. t1 and t2 share the node plus(a0,b0). Updating a creates plus(a0,1), called a1. t3 uses plus(a1,b0), which cannot be replaced by t1. dead has no later use and is not live on exit, so its pure computation can be removed. Replace uses of t2 with t1; no separate t2 assignment is needed. A valid result is t1=a+b; a=a+1; t3=a+b; out=t1+t1. For incoming a=2,b=5, the outputs are a=3,t3=8,out=14 in both versions. Local temporaries need not retain unused final values.
3. Copy propagation, folding and algebraic rewrites
Constant folding computes operations on known constants, such as t=3*4 becoming t=12. Constant propagation replaces uses of variables known constant; it is a distinct reasoning step. Copy propagation from u=v can replace a later use of u by v only while v still holds the copied value. In u=v; v=7; w=u+1, replacing u by the current v is wrong unless the old v was independently known to equal 7.
Strength reduction replaces an expensive operation with a cheaper equivalent, for example a suitable multiplication by a power of two with a shift when the type and language rules make them equivalent. Algebraic identities such as x+0=x and x*1=x are simple over mathematical integers. They cannot be applied blindly to every floating-point, overflow, exception or signed-zero model. Dead-code elimination removes an assignment whose produced value is unused, but only if removing its evaluation also preserves required effects.
4. Aliasing, calls and exceptions
For t1=*p; q=7; t2=p, the second load cannot generally reuse t1 because p and q might alias. Proving disjoint locations would change that conclusion. A procedure call may modify memory visible to the program, so memory-based value facts may need invalidation unless the call's effects are known.
Even an unused expression may trap, perform I/O or update volatile state. Under semantics where division-by-zero is observable, deleting unused z=1/0 changes behavior; liveness alone does not authorize deletion. Conversely, the worked scalar block explicitly excluded traps and effects, so removing dead was justified. Distinguish preserving a final scalar value from preserving the full program behavior.
Pitfalls and exam method
First list assumptions and exit-live variables. Next identify operand values and all redefinitions. Apply only justified rewrites, then run at least one test trace and reason about all legal inputs. Test inputs can reveal errors but do not prove equivalence. Do not reuse an expression solely because its text matches, and do not discard an output variable merely because it is never read inside the current block.
Original practice: six single-correct MCQs
These original teaching questions are not previous-year questions. Choose exactly one answer.
P01. For the numbered CFG example, the leader set is:
A. {1,2,4} B. {1,3,5,6} C. {1,5} D. Every instruction
Answer: B
A: Branch instructions do not automatically replace their block leaders.
B: First, branch successors and targets give 1,3,5,6.
C: This misses post-branch and merge leaders.
D: Straight-line neighbors can share a block.
P02. After t1=a+b; a=a+1; t3=a+b, can t3 be replaced by t1 under general integer inputs?
A. Always B. Only because spelling matches C. No, a has a new value D. Yes if t1 is a temporary
Answer: C
A: The operand value changed.
B: Text identity is insufficient.
C: The two additions use different versions of a.
D: Temporary naming does not restore operand equality.
P03. In the worked optimized block, incoming a=2,b=5 gives out=?
A. 7 B. 8 C. 14 D. 16
Answer: C
A: Seven is the shared original sum.
B: Eight is the later t3.
C: out=t1+t1=7+7=14.
D: This wrongly uses the updated sum twice.
P04. Which justifies removing an unused assignment?
A. Its result is dead and evaluation has no required effects B. Its variable name is short C. It contains division, always D. It is last in the block, always
Answer: A
A: Both value use and effects must be considered.
B: Names have no semantic relevance.
C: Division may trap under the specified model.
D: Exit-live values may be required later.
P05. In t1=*p; q=7; t2=p, why may reusing t1 for t2 be unsafe?
A. Pointers always hold different addresses B. p and q may alias C. Loads never have values D. The constant 7 cannot be stored
Answer: B
A: Different pointer names can denote the same address.
B: The store may change the loaded location.
C: A load produces a value, but it may change here.
D: Storing 7 is valid; aliasing is the issue.
P06. Which rewrite is constant folding?
A. t=3*4 becomes t=12 B. u=v replaces a use of u with v C. Two loads are merged after alias proof D. A loop is unrolled
Answer: A
A: A constant operation is evaluated during compilation.
B: This is copy propagation.
C: This is redundancy elimination.
D: Unrolling duplicates loop-body structure.
Sources and scope
Aligned to the official 2026 course. This lesson covers a bounded topic slice; no claim of 2027 completeness. All examples and exercises are original.
Sign in to keep your progress. Sign in