Peephole Optimization: How Compilers Improve Code with Local Pattern Rewrites

Peephole optimization is a compiler technique that repeatedly examines a small, contiguous “window” of instructions—called a Peephole (or window—and replaces it with an equivalent sequence that runs faster or is smaller in code size, while preserving program semantics. Peephole optimization is commonly applied in the backend, after instruction selection, because the compiler can exploit machine-specific instruction patterns efficiently.

Why “local” helps

Because the transformation scope is small, peephole rules are:

• Easy to specify as pattern→replacement rules,
• Fast to apply (linear-ish scanning with a small lookahead),
• Useful for machine-dependent cleanups that higher-level passes may miss.

Canonical example transformations

Common peephole replacements include:

• removing redundant stack operations,
• simplifying arithmetic by algebraic identities,
• turning slow arithmetic sequences into faster machine idioms (e.g., shifts for multiply-by-powers-of-two),
• deleting “null sequences” (instructions that do nothing).

Mermaid overview:

Key takeaway: peephole optimization is about localized equivalence rewriting.

Footnotes

1. Peephole optimization - Wikipedia - Defines peephole optimization and provides examples like removing redundant stack ops and replacing multiplies with shifts. ↩ ↩² ↩³

Core idea: pattern matching on a sliding window

A peephole optimizer operates by scanning instructions and applying rules when it sees a specific short pattern. Wikipedia describes the technique as replacing a peephole (small instruction set) with a logically equivalent set that has better performance, e.g., removing redundant operations or simplifying multiplies.

In modern compilers, peephole behavior is often implemented as instruction-sequence pattern matching, possibly across multiple internal forms (IR, assembly, or machine code). LLVM has a dedicated peephole optimizer implementation for machine code (e.g., PeepholeOptimizer.cpp).

Footnotes

1. Peephole optimization - Wikipedia - Defines peephole optimization and provides examples like removing redundant stack ops and replacing multiplies with shifts. ↩

2. LLVM: lib/CodeGen/PeepholeOptimizer.cpp Source File - Documents LLVM’s peephole optimizer pass for machine code. ↩

Examples of peephole optimizations (with before/after)

Example 1: Remove redundant stack instructions around calls

A classic example is removing patterns like POP immediately followed by PUSH for the same registers. Wikipedia explains that such sequences are often redundant; removing one may expose another redundant pair, which can be removed in turn.

Before (two consecutive calls in Z80 example):

PUSH AF
PUSH BC
PUSH DE
PUSH HL
CALL _ADDR1
POP  HL
POP  DE
POP  BC
POP  AF
PUSH AF
PUSH BC
PUSH DE
PUSH HL
CALL _ADDR2
POP  HL
POP  DE
POP  BC
POP  AF

After (redundant pairs removed, leaving fewer stack operations):

PUSH  AF PUSH  BC PUSH  DE PUSH  HL
CALL  _ADDR1 CALL  _ADDR2
POP  HL POP  DE POP  BC POP  AF

(Conceptually: consecutive save/restore sequences can collapse if the intermediate state doesn’t matter.)

Keywords:

• Redundant stack operations
• Call sequence
• POP/PUSH redundancy

---

Example 2: Replace multiply by 2 with shift-left

Wikipedia gives examples such as replacing multiplication by $2$ with a left shift (e.g., x << 1).

Before:

x = x * 2

After:

x = x << 1

Benefits:

• Shifts are often cheaper than general multiplication on many ISAs.
• Encoding may be shorter depending on target instructions.

Keywords:

• Strength reduction
• Shift-left idiom
• Algebraic simplification

---

Example 3: Multiply by 8 via exponent adjustment (floating-point idea)

Wikipedia also mentions that floating-point multiplies by powers of two can be optimized by manipulating the exponent (e.g., adding 3 to exponent for multiply by $8$).

This illustrates a peephole principle: recognize specific local arithmetic patterns and use ISA/representation-specific equivalents.

Keywords:

• Floating-point exponent manipulation
• Machine-specific idioms

---

Example 4: Remove a null sequence / useless operations

Peephole optimization can delete useless operations that do not affect results (e.g., arithmetic with identities or instructions that are overwritten immediately). Wikipedia lists “null sequences” as part of the replacement repertoire.

Typical shapes:

• x + 0 → no-op,
• x * 1 → no-op,
• redundant move/copy where a value is immediately overwritten.

Keywords:

• Null sequence
• Dead instruction
• Redundant move elimination

Footnotes

1. Peephole optimization - Wikipedia - Defines peephole optimization and provides examples like removing redundant stack ops and replacing multiplies with shifts. ↩ ↩² ↩³ ↩⁴ ↩⁵ ↩⁶ ↩⁷ ↩⁸

Benefits (why peephole optimization matters)

1. Improves performance with cheap local fixes
   Peephole optimization aims to produce “shorter and faster” equivalent sequences, which directly reduces runtime cost for tight loops and hot instruction paths.

2. Reduces code size
   By replacing longer patterns with shorter instruction sequences, peephole optimization lowers instruction count and can improve instruction cache behavior. High-level descriptions of peephole objectives include reducing code size and improving speed.

3. Eliminates redundant instructions and memory traffic
   Examples include removing redundant stack ops and simplifying arithmetic sequences into faster idioms (e.g., shift-based multiply-by-powers-of-two).

4. Creates opportunities for subsequent optimizations
   Because peephole rewrites may remove instructions and expose new neighboring patterns, a transformation can enable further reductions (e.g., removing one redundant save/restore can reveal another).

5. Integrates well with machine-dependent code generation
   LLVM and other production compilers implement peephole-style passes in their backend to perform machine-code cleanups such as extension/comparison elimination.

Practical note about correctness

Peephole rewrites must preserve semantics under the compiler’s IR/program model. Research on LLVM peephole optimization emphasizes that correctness depends on careful handling of undefined behavior concepts (e.g., refinement assumptions enabled by the IR model).

Footnotes

1. Peephole optimization - Wikipedia - Defines peephole optimization and provides examples like removing redundant stack ops and replacing multiplies with shifts. ↩ ↩² ↩³

2. Compiler Design - Peephole Optimization (Tutorialspoint) - Lists objectives such as increasing code speed and reducing code size; describes techniques like constant folding/strength reduction. ↩

3. LLVM: lib/CodeGen/PeepholeOptimizer.cpp Source File - Documents LLVM’s peephole optimizer pass for machine code. ↩

4. Practical formal techniques and tools for developing LLVM’s peephole optimizations (Rutgers) - Discusses the importance of semantics preservation and careful treatment of undefined behavior in LLVM peephole optimizations. ↩

Where peephole optimization fits in the compiler pipeline

Peephole optimization is typically a backend (or late-stage) transformation because it acts on small instruction sequences produced by earlier steps (instruction selection / lowering). Descriptions in compiler literature emphasize that peephole works on small instruction windows and replaces them with better alternatives while preserving behavior.

In LLVM specifically, an implementation exists to perform peephole optimizations on machine code (e.g., optimizing sign/zero extension patterns).

Keywords:

• Backend optimization
• Instruction selection
• Canonicalization

Footnotes

1. Peephole optimization - Wikipedia - Defines peephole optimization and provides examples like removing redundant stack ops and replacing multiplies with shifts. ↩

2. LLVM: lib/CodeGen/PeepholeOptimizer.cpp Source File - Documents LLVM’s peephole optimizer pass for machine code. ↩