Global Optimization
1. Scope
Global optimization works across basic blocks / whole function using CFG + data-flow facts. Bigger wins, needs safety proofs.
2. Techniques
| Opt | Needs | Example |
|---|---|---|
| Global CSE | available exprs | a=b+c on both branches → compute once in predecessor |
| Copy/const prop | reaching defs | propagate x=5 across blocks |
| Dead code elim | liveness | ifFalse branch never taken → delete |
| Loop-invariant motion | (see loop topic) | hoist c=2*3 out |
| Inlining | call graph | replace f(x) body for small f |
| Tail-call elim | return f(..) last |
reuse frame (no stack growth) |
3. Worked — global CSE
B1: t1=b+c; if E goto B2 else B3
B2: t2=b+c; ... → replace t2 with t1 (b,c not redefined on path)
Requires available-expressions proof that b+c computed on all incoming paths.
4. Cost/Risk
Needs fixpoint iteration; inlining bloats code; needs alias analysis for pointers.
5. Exam Points
- List global opts with safety condition — 7 marks, very frequent.
- Global CSE / dead-branch elim example — 5 marks, frequent.
- Local vs global difference — 3 marks, frequent.