CD Notes
Comprehensive introduction to compiler code optimization covering optimization levels, classification, basic blocks, control flow graphs, and the role of optimization in the compilation pipeline.
What is Code Optimization?
Code optimization is the phase of compilation that transforms the intermediate representation to produce more efficient target code. The goal is to improve execution speed, reduce memory usage, or minimize power consumption — without changing the observable behavior of the program.
The term "optimization" is somewhat misleading since achieving truly optimal code is undecidable in general. In practice, compilers apply a series of heuristic transformations that improve code quality in most cases.
Optimization in the Compilation Pipeline
Classification of Optimizations
By scope
┌─────────────────────────────────────────────────────────┐
│ Local: Within a single basic block │
│ Examples: constant folding, algebraic simplification │
├─────────────────────────────────────────────────────────┤
│ Global (Intraprocedural): Across basic blocks within │
│ one function. Examples: CSE, loop optimizations │
├─────────────────────────────────────────────────────────┤
│ Interprocedural: Across function boundaries │
│ Examples: inlining, interprocedural constant prop. │
├─────────────────────────────────────────────────────────┤
│ Whole-program (Link-time): Across compilation units │
│ Examples: dead function elimination, devirtualization │
└─────────────────────────────────────────────────────────┘
By effect
Speed optimizations: reduce execution time
Space optimizations: reduce code/data size
Power optimizations: reduce energy consumption
Basic Blocks
A basic block is a maximal sequence of consecutive instructions such that:
- Flow of control only enters at the first instruction
- Flow of control only leaves at the last instruction
- No halt or branch except possibly the last instruction
| Algorithm | Partition into basic blocks |
| 1 | i = 1 ← Leader (first instruction) |
| 2 | j = 1 |
| 3 | t1 = 10 * i |
| 4 | t2 = t1 + j Block B1: {1, 2, 3, 4, 5, 6, 7} |
| 5 | t3 = 8 * t2 |
| 6 | a[t3] = 0.0 |
| 7 | j = j + 1 |
| 8 | if j <= 10 goto 3 ← ends B1 |
| 3 | t1 = 10 * i ← Leader (branch target) |
| ... Block B2 | {3, 4, 5, 6, 7, 8} |
| 9 | i = i + 1 ← Leader (after conditional) |
| 10 | if i <= 10 goto 3 Block B3: {9, 10} |
| 11 | ... ← Leader (after conditional) |
| Block B4 | {11, ...} |
Control Flow Graph (CFG)
A directed graph where
- Nodes = basic blocks
- Edges = possible flow of control
For the above example
┌───────┐
│ B1 │
│ i=1 │
│ j=1 │
└───┬───┘
↓
┌──→┌───────┐
│ │ B2 │←──────┐
│ │loop │ │
│ │body │───────┘ (j<=10)
│ └───┬───┘
│ ↓ (j>10)
│ ┌───────┐
└───│ B3 │ (i<=10, goto B2)
│ i=i+1 │
└───┬───┘
↓ (i>10)
┌───────┐
│ B4 │
│ exit │
└───────┘
Common Optimizations Overview
Dataflow Analysis Framework
Most optimizations are driven by dataflow analysis:
General framework:
For each basic block B:
OUT[B] = transfer_function(IN[B])
IN[B] = meet_function(OUT[predecessors])
Forward analysis: IN[B] = ∩/∪ OUT[P] for all predecessors P
Backward analysis: OUT[B] = ∩/∪ IN[S] for all successors S
Example - Reaching Definitions:
GEN[B] = definitions in B that reach end of B
KILL[B] = definitions elsewhere killed by definitions in B
IN[B] = ∪ OUT[P] for all predecessors P of B
OUT[B] = GEN[B] ∪ (IN[B] - KILL[B])
Iterate until fixed point (no changes).
Optimization Levels (GCC Example)
| -O0 | No optimization (fastest compilation) |
| -O1 | Basic optimizations |
| -O2 | Standard optimizations (recommended) |
| -O3 | Aggressive optimizations |
| -Os | Optimize for size |
Criteria for Optimization
A valid optimization must satisfy:
- Preservation of semantics: Output of optimized program must match original
- Safety: Optimization must be applicable (preconditions met)
- Profitability: Transformation should improve (not degrade) performance
Interview Questions
- Q: Why is code optimization an NP-hard problem in general?
A: Many optimization problems reduce to NP-hard graph problems. Optimal register allocation is graph coloring (NP-complete), optimal instruction scheduling is job-shop scheduling (NP-hard), and optimal code size is related to shortest superstring. Compilers use polynomial-time heuristics that work well in practice.
- Q: What is the difference between local and global optimization?
A: Local optimization works within a single basic block (no control flow to consider, simple analysis). Global optimization works across basic blocks within a function (must handle joins and branches using dataflow analysis). Global optimization is more powerful but more expensive and complex.
- Q: Can optimization change program behavior?
A: A correct optimization must preserve observable behavior (output, externally visible state). However, it may change non-observable aspects: memory layout, register usage, instruction order. Some optimizations (like strict aliasing assumptions) can change behavior of undefined-behavior programs.
- Q: Why do compilers apply optimizations in a specific order (pass ordering)?
A: Optimizations interact — one may enable another. Constant propagation enables constant folding, which enables dead code elimination. The order matters because applying them in the wrong sequence may miss opportunities. Finding the optimal pass order is itself an unsolved research problem.
- Q: What is phase ordering problem?
A: Different optimization passes can interfere or enable each other. The best sequence of passes depends on the program being compiled. No fixed ordering is optimal for all programs. Practical solutions include repeated application of passes until a fixed point, or using profile-guided selection of pass sequences.
Exam Focus
Revise definitions, diagrams, examples, and short-answer points for Introduction to Code Optimization 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, introduction, introduction to code optimization in compiler design
Related Compiler Design Topics