CD Notes
Detailed guide to peephole optimization covering pattern matching, redundancy elimination, instruction simplification, jump optimization, and practical peephole optimization techniques.
Introduction
Peephole optimization examines a small sliding window (peephole) of consecutive instructions and replaces inefficient patterns with better alternatives. It is typically applied as a final pass after code generation, catching inefficiencies that other optimizations missed or that were introduced by the code generator itself.
How Peephole Optimization Works
Peephole window (typically 2-4 instructions)
Generated code: Peephole scans:
MOV R0, R1 ┌─────────────┐
MOV R1, R0 ←── │ MOV R0, R1 │ Match pattern:
ADD R2, R0 │ MOV R1, R0 │ "redundant reverse MOV"
... └─────────────┘ → Delete second MOV
Process
1. Slide window over instruction sequence
2. Match patterns in window against optimization rules
3. Replace matched patterns with improved code
4. Re-examine window (new pattern may emerge)
5. Repeat until no more matches
Categories of Peephole Optimization
1. Redundant Instruction Elimination
Redundant load after store
ST [x], R0 → ST [x], R0
LD R0, [x] (eliminated - R0 already has value)
Redundant move
MOV R0, R1 → (eliminated if R0 = R1 already)
Redundant push-pop
PUSH R0 → (both eliminated, net effect zero)
POP R0
Self-move
MOV R0, R0 → (eliminated)
Redundant comparison
SUB R0, R1, R2 → SUB R0, R1, R2
CMP R0, 0 (eliminated - SUB already sets flags)
2. Strength Reduction
| MUL R0, R0, 2 | SHL R0, R0, 1 (shift left) |
| MUL R0, R0, 4 | SHL R0, R0, 2 |
| MUL R0, R0, 8 | SHL R0, R0, 3 |
| MUL R0, R0, 3 | LEA R0, [R0 + R0*2] (x86) |
| MUL R0, R0, 5 | LEA R0, [R0 + R0*4] |
| MUL R0, R0, 7 | LEA R0, [R0*8 - R0] |
| DIV R0, R0, 2 | SHR R0, R0, 1 (unsigned) |
| DIV R0, R0, 4 | SHR R0, R0, 2 |
| MOD R0, R0, 8 | AND R0, R0, 7 (unsigned, 2^n) |
| x ** 2 | x * x |
3. Jump/Branch Optimization
Jump over jump
JZ L1 → JNZ L2 (invert condition, skip jump)
JMP L2
L1: ... L1: ...
Jump to jump (thread)
JMP L1 → JMP L2 (skip intermediate)
...
L1: JMP L2
Conditional jump to same target
JZ L1 → JMP L1 (unconditional - same target)
JMP L1
Jump to next instruction
JMP L1 → (eliminated)
L1: ... L1: ...
Branch chain elimination
CMP R0, 0
JZ L1 → (if L1 just does "JMP L2")
... Change to: JZ L2
L1: JMP L2
4. Algebraic Simplification
| ADD R0, R0, 0 | (eliminated - no effect) |
| SUB R0, R0, 0 | (eliminated) |
| MUL R0, R0, 1 | (eliminated) |
| OR R0, R0, 0 | (eliminated) |
| AND R0, R0, -1 | (eliminated) |
| XOR R0, R0, 0 | (eliminated) |
| SHL R0, R0, 0 | (eliminated) |
| ADD R0, R0, 1 | INC R0 (x86, shorter encoding) |
| SUB R0, R0, 1 | DEC R0 |
| XOR R0, R0, R0 | (recognized as: R0 = 0) |
| SUB R0, R0, R0 | (recognized as: R0 = 0) |
5. Machine-Specific Idioms
| MOV EAX, 0 | XOR EAX, EAX (shorter, faster) |
| CMP EAX, 0 | TEST EAX, EAX (shorter) |
| MOV EAX, [addr] | LEA EAX, [addr] (if only address needed) |
| MOV R0, R1 | (eliminated if can merge into next instr) |
| CMP R0, 0 | (unnecessary if previous instr set flags) |
Implementation: Rule-Based Pattern Matching
| Pattern | MOV Rx, Ry; MOV Ry, Rx |
| Condition | Rx ≠ Ry |
| Replace | MOV Rx, Ry |
| Pattern | ST [addr], Rx; LD Ry, [addr] |
| Condition | no intervening write to [addr] |
| Replace | ST [addr], Rx; MOV Ry, Rx |
| Pattern | JMP L; ...dead code...; L: |
| Replace | L: (remove jump and dead code between) |
| Pattern | MUL Rx, Rx, 2^n |
| Replace | SHL Rx, Rx, n |
Peephole Optimizer Architecture
| Window Buffer | (2-4 instructions) | |
|---|---|---|
| Pattern Matcher | → if match found: |
Peephole vs Other Optimizations
Peephole catches what others miss
- Code generator artifacts (redundant moves from register allocation)
- Cross-optimization residue (CSE + reg alloc creates redundant copies)
- Target-specific patterns (machine idioms)
- Low-level details (flag-setting side effects)
What peephole CANNOT do
- Long-range optimization (window too small)
- Loop optimization (needs loop structure awareness)
- Global dataflow improvements (no CFG view)
- Interprocedural optimization (function-level)
Interview Questions
- Q: Why is peephole optimization applied at the end of compilation?
A: Earlier optimizations work on IR which is machine-independent. Peephole works on actual machine instructions, catching machine-specific inefficiencies that only appear after code generation and register allocation. It serves as a final cleanup pass, fixing patterns that result from the interaction of previous passes.
- Q: Can peephole optimization be applied multiple times?
A: Yes, and it often should be. One peephole replacement may create a new pattern matchable by another rule. For example, eliminating a redundant move might expose a redundant load. Multiple passes continue until no more patterns match (fixed point).
- Q: What is the window size trade-off?
A: Larger windows can match more complex patterns and find more optimizations. However, larger windows have exponentially more possible patterns to check, making the optimizer slower and harder to maintain. In practice, 2-3 instruction windows catch the vast majority (>95%) of peephole opportunities.
- Q: How does peephole optimization relate to superoptimization?
A: Superoptimization exhaustively searches for the shortest/fastest instruction sequence equivalent to a given short code segment. It can discover non-obvious replacements that hand-written peephole rules miss. It is too slow for general use but can discover rules to add to the peephole table.
- Q: Does peephole optimization change the asymptotic complexity of programs?
A: No. Peephole only changes constant factors — replacing one instruction with a cheaper one, eliminating redundant operations. It cannot change algorithmic complexity (e.g., O(n²) to O(n log n)). For that, higher-level source transformations or algorithm selection are needed.
Exam Focus
Revise definitions, diagrams, examples, and short-answer points for Peephole 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, peephole, peephole optimization in compiler design
Related Compiler Design Topics