CD Notes
Comprehensive guide to global (intraprocedural) optimization techniques including dataflow analysis frameworks, reaching definitions, live variables, and global optimization passes.
Introduction
Global optimization operates across basic block boundaries within a single function (intraprocedural scope). Unlike local optimizations that only see one block at a time, global optimization considers the entire control flow graph, enabling more powerful transformations by reasoning about what holds on all paths or any path to a program point.
Dataflow Analysis Framework
| Analysis | Direction | Meet | Purpose |
|---|---|---|---|
| Reaching Definitions | Forward | ∪ | Const prop |
| Available Expressions | Forward | ∩ | CSE |
| Live Variables | Backward | ∪ | Reg alloc |
| Very Busy Express. | Backward | ∩ | Code hoist |
Reaching Definitions
| A definition d | x = ... reaches point p if there is a path from d to p |
| B1 | d1: x = 5 GEN={d1, d2}, KILL={d3, d4, d5, d6} |
| d2 | y = 3 |
| B2 | d3: x = y + 1 GEN={d3, d4}, KILL={d1, d5} |
| d4 | z = x |
| B3 | d5: x = 10 GEN={d5, d6}, KILL={d1, d3} |
| d6 | y = x |
| Init | OUT[B] = GEN[B] for all B |
| If B1 | B2, B1→B3, B2→exit, B3→exit: |
Live Variables Analysis
| B1 | x = 5 DEF={x, y}, USE={} |
| B2 | z = x + y DEF={z}, USE={x, y} |
| B3 | w = x * 2 DEF={w}, USE={x} |
| CFG: B1 | B2, B1 → B3 |
| At end of B1 | x and y are live (used in successors) |
| This tells register allocator | keep x, y in registers after B1. |
Global Common Subexpression Elimination
Using available expressions analysis
Before: After:
B1: t1 = a + b B1: t1 = a + b
x = t1 x = t1
B2: (a, b unchanged) B2:
t2 = a + b ← available! t2 = t1 ← reuse!
y = t2 * 2 y = t2 * 2
Conditions for global CSE
1. Expression must be AVAILABLE (computed on ALL paths, operands unchanged)
2. The computed value must be accessible (stored in a variable/temp)
3. The temp holding the value must still be live (or re-computable)
Global Copy Propagation
| Replace use of x with y if | x = y is the ONLY reaching definition of x, |
| Before | After: |
| B1 | x = y B1: x = y |
| B2 | z = x + 1 B2: z = y + 1 (x replaced by y) |
Global Dead Code Elimination
Using live variables analysis
If variable x is NOT live at the point after "x = expr" and
expr has no side effects → the assignment is dead.
Example
B1: x = expensive() // x live here? Check OUT[B1]
y = x + 1
B2: y = 10 // overwrites y before any use
print(y)
Live variables at end of B1
y is live? → y defined in B2 before use → y NOT live after B1
x is live? → x used in "y = x+1" → x IS live in B1
So "y = x + 1" in B1 is DEAD (y overwritten in B2 without use)
Remove it. Then x has no use → "x = expensive()" ...
BUT expensive() might have side effects → KEEP the call, remove assignment:
expensive() // call without storing result
Partial Redundancy Elimination (PRE)
Strength Reduction (Global)
| Before | After: |
| Multiplication by loop variable | repeated addition |
| i*4 each iteration | just add 4 to previous result |
Interview Questions
- Q: What is the difference between local, global, and interprocedural optimization?
A: Local = within one basic block (no control flow), Global = across blocks within one function (intraprocedural, considers CFG), Interprocedural = across function boundaries (considers call graph). Each level is more powerful but more expensive. Most improvement comes from global optimizations.
- Q: Why do forward analyses use union at joins and available expressions uses intersection?
A: Reaching definitions uses union because we want to know ALL definitions that MIGHT reach a point (any path). Available expressions uses intersection because we want expressions guaranteed available on ALL paths (every path). Union = "exists a path", Intersection = "for all paths."
- Q: How does the iterative dataflow algorithm guarantee termination?
A: The domain forms a lattice with finite height. Transfer functions are monotone (values only move in one direction). Each iteration moves at least one value down the lattice. With finite height and monotonicity, a fixed point must be reached in at most O(height × nodes) iterations.
- Q: What is the relationship between SSA form and dataflow analysis?
A: SSA form encodes reaching definitions directly in the IR structure (each use linked to its unique definition). This eliminates the need for iterative reaching definitions analysis. Many analyses become simpler on SSA because def-use relationships are explicit, reducing global problems to local ones.
- Q: Can global optimization change the order of side effects?
A: No. A correct global optimization must preserve the observable order of side effects (I/O, volatile accesses, synchronization). Code motion (like hoisting expressions out of loops) is only safe if the moved code has no side effects or the side effects maintain their relative order.
Exam Focus
Revise definitions, diagrams, examples, and short-answer points for Global 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, global, global optimization techniques in compiler design
Related Compiler Design Topics