CD Notes
Guide to local optimization within basic blocks covering algebraic simplification, constant folding, copy propagation, dead code elimination, and DAG-based optimization approaches.
Introduction
Local optimization works within a single basic block — a straight-line sequence of code with no branches except at the end. Since there is no control flow to consider, local optimizations are simpler, faster, and always safe within their block. They form the foundation upon which global optimizations build.
Algebraic Simplification
Identity operations (remove entirely)
x + 0 → x x - 0 → x
x * 1 → x x / 1 → x
x ** 1 → x x OR 0 → x
x AND ~0 → x x XOR 0 → x
Annihilation
x * 0 → 0 x AND 0 → 0
x - x → 0 x XOR x → 0
Strength reduction
x * 2 → x + x or x << 1
x * 4 → x << 2
x * 2ⁿ → x << n
x / 2ⁿ → x >> n (unsigned) or (x + (x>>31)) >> n (signed)
x % 2ⁿ → x & (2ⁿ - 1) (unsigned)
Algebraic identities
x + x → 2 * x → x << 1
x * x → x²
-(−x) → x
NOT(NOT x) → x
(x + c1) + c2 → x + (c1 + c2) // constant reassociation
x * c1 * c2 → x * (c1 * c2)
Local Constant Folding and Propagation
Local Common Subexpression Elimination
Using value numbering within the block
Input: After CSE:
t1 = a + b t1 = a + b
t2 = a * c t2 = a * c
t3 = a + b t3 = t1 (same as t1)
t4 = t2 + t3 t4 = t2 + t1 (use t1 for t3)
t5 = a * c t5 = t2 (same as t2)
t6 = t4 + t5 t6 = t4 + t2 (use t2 for t5)
Value Number table
(a+b) → VN1, representative: t1
(a*c) → VN2, representative: t2
Hash: hash(PLUS, VN_a, VN_b) → look up → found VN1 → use t1
DAG-Based Optimization
Build a Directed Acyclic Graph for the basic block
- Leaves = initial values of variables/constants
- Internal nodes = operations
- Multiple names can point to same node (CSE)
Example block
a = b + c
d = a - e
b = a - e // same computation as d!
f = b + c // b has new value, c unchanged
DAG construction
Step 1: a = b + c
[+]→{a}
/ \
[b₀] [c₀]
Step 2: d = a - e
[-]→{d}
/ \
[+]→{a} [e₀]
Step 3: b = a - e (same [-] node exists!)
[-]→{d, b} ← b added to same node
/ \
[+]→{a} [e₀]
Step 4: f = b + c (b now has value of [-] node)
[+]→{f}
/ \
[-]→{d,b} [c₀] ← different from first [+]!
Optimized code from DAG (topological order)
a = b + c // [+] node with original b,c
d = a - e // [-] node
b = d // b gets same value as d (copy)
f = d + c // [+] node with new b (=d) and c
Local Dead Code Elimination
| If LHS variable is not in "needed" set | DEAD |
| Else | add RHS variables to "needed" set |
| a = x + y ← needed? a used in c, c used in z | YES |
| b = a - 1 ← needed? b not used later | DEAD! |
| c = a * 2 ← needed? c used in z | YES |
| d = b + c ← needed? d not used | DEAD (also b dead) |
| z = c + x ← needed? z is live at exit | YES |
Peephole Optimization (Local)
| ST [x], R0 | (remove second instruction) |
| JMP L1 | JMP L2 (jump threading) |
| L1 | JMP L2 |
| ADD R0, R0, 0 | (remove, no effect) |
| MUL R0, R0, 1 | (remove, no effect) |
| MOV R0, R0 | (remove, no effect) |
| MUL R0, R0, 2 | SHL R0, R0, 1 |
| MUL R0, R0, 8 | SHL R0, R0, 3 |
| CMP R0, 0 | (use zero flag from previous SUB) |
Instruction Combining
| Before | After (x86): |
| Before | After: |
| Before | After (if FMA available): |
Local Value Numbering (Complete Algorithm)
| 1. Get value numbers | VN(y), VN(z) |
| Replace instruction with | x = representative |
| For +, *, AND, OR, XOR | canonicalize order |
Interview Questions
- Q: Why are local optimizations applied before global ones?
A: Local optimizations simplify each basic block, making subsequent global analysis cheaper and more effective. They handle the "easy wins" (constant folding, obvious CSE) that don't need expensive dataflow analysis. Cleaner blocks also mean the CFG has fewer nodes/edges for global passes.
- Q: What is the advantage of DAG representation over linear code for optimization?
A: DAGs expose common subexpressions as shared nodes (automatic CSE detection), make dead code visible (nodes with no users), and allow flexible code generation (different traversal orders yield different instruction schedules). They also compact the representation of a basic block.
- Q: Can local optimizations produce incorrect code?
A: If implemented correctly, no. Local optimizations are provably safe because they only consider straight-line code with no control flow. Each transformation preserves the input-output behavior of the block. However, bugs in implementation (e.g., not checking if a variable is redefined between two uses) can produce incorrect results.
- Q: How does value numbering handle operations with side effects?
A: Operations with side effects (function calls, volatile reads) are given unique value numbers every time they appear — they are never treated as "common." For example, two calls to rand() get different value numbers even though the syntax is identical, because the results may differ.
- Q: What is the time complexity of local optimization?
A: Most local optimizations are O(n) where n is the number of instructions in the block. Value numbering uses hash table lookups (O(1) amortized per instruction). DAG construction is also O(n). This efficiency makes local optimizations practically free in compilation time, so they are always applied even at low optimization levels.
Exam Focus
Revise definitions, diagrams, examples, and short-answer points for Local Optimization Techniques in Compiler Design.
Interview Use
Prepare one clear explanation, one practical example, and one common mistake for this Compiler Design topic.
Search Terms
compiler-design, compiler design, compiler, design, code, optimization, local, local optimization techniques in compiler design
Related Compiler Design Topics