Peephole Optimization in Compiler Design: Principles and Worked Examples

Peephole optimization is a local compiler optimization technique that repeatedly scans a short “window” of instructions (the peephole) and replaces inefficient or redundant instruction sequences with equivalent, more efficient ones. This differs from global optimizations because it focuses on local patterns and typically does not require whole-program analysis. Common peephole rewrite categories include eliminating redundant moves, simplifying arithmetic/boolean sequences, constant-related simplifications, and strength reductions for target instructions.

A core assumption is that many inefficient instruction sequences are “obvious” when viewed locally—for example, an add with zero, a mul by one, back-to-back register copies, or sequences that can be folded into a single instruction. In modern compilers, these transformations are often implemented as instruction-combining / local rewrite passes, sometimes with additional canonicalization steps; nevertheless, the conceptual “peephole” model remains useful for reasoning about optimizer behavior.

Key terms (for this topic)

• Peephole optimization
• Rewrite rule
• Instruction selection
• Fixed point iteration

Note: Peephole optimizations are typically validated for semantic equivalence—e.g., preserving flags, memory ordering, calling conventions, and side effects—especially on real ISAs with condition codes and aliasing.

Why peephole optimization matters (and where it fits)

Peephole optimization is often used for “last-mile” cleanup: after earlier passes have produced code that is functionally correct but not yet optimal for the target ISA. Even when compilers have sophisticated global optimizations, local patterns still occur frequently due to:

1. Instruction selection emitting conservative sequences.
2. Lowering of high-level constructs (e.g., short-circuit logic or arithmetic expressions) into primitive operations.
3. Register moves and temporaries introduced by code generation.

Where it typically appears in a pipeline

A typical compiler pipeline (conceptually) includes: front-end → IR → optimization passes (local and global) → instruction selection → peephole-like cleanups (sometimes after machine IR is available). Peephole opportunities increase once you have machine-like instructions and known target details (like flags usage and addressing modes).

Fundamental peephole algorithm (pattern scanning and replacement)

A peephole optimizer:

1. Chooses a small window size (e.g., 2–5 instructions).
2. Matches instruction sequences against a library of rewrite rules.
3. Applies a rule if it preserves semantics.
4. Re-scans (or continues sliding) to catch newly created patterns.
5. Repeats until no more improvements are possible (fixed point) or a budget is reached.

Typical constraints

• Semantics preservation: No change to observable behavior (register results, memory, I/O, flags, exceptions).
• Control-flow safety: Must not cross basic-block boundaries (unless the compiler is extremely careful).
• Side-effect awareness: Loads/stores, volatile operations, and memory fences constrain rewrites.
• Flag correctness: On many ISAs, arithmetic instructions modify condition codes; rewriting can change which instruction sets flags.

Worked examples (instruction-sequence rewrites)

Below are representative peephole optimizations you should recognize. The exact instruction syntax varies by ISA, but the patterns are widely applicable.

Example 1: Redundant move / self-move elimination

Before:

• mov r1, r1
• mov r2, r1
• mov r3, r2

A common peephole rule:

• Replace mov x, x with nothing (remove it).
• Collapse chains of copies when safe:
  • mov r2, r1; mov r3, r2 → mov r3, r1 (if no intervening use or clobber).

After (one possible rewrite):

• mov r3, r1

Why it works: Copy chains are local and can be eliminated if the intermediate register value is not used elsewhere and is not overwritten.

Example 2: Arithmetic identity simplification

Before:

• add rA, rB, #0 (or add rA, rA, #0)
• mul rC, rD, #1
• and rE, rF, #0xFFFFFFFF

After:

• mov rA, rB
• mov rC, rD
• mov rE, rF (for a full mask that preserves all bits on a fixed-width machine)

Key idea: If an operation does not change the value, replace it with a cheaper instruction (often a move or delete).

Example 3: Strength reduction with local patterns

Before:

• mul rX, rY, #2
• add rZ, rW, rW

Two classic strength-reduction peepholes:

• Multiplication by 2 can become a shift:
  • mul rX, rY, #2 → shl rX, rY, #1 (if semantics match for signed/unsigned and bit width).
• Doubling via add:
  • add rZ, rW, rW → shl rZ, rW, #1 (again, if ISA/flags semantics align).

Why it works: Shifts are often cheaper than general multiply on many architectures, and the pattern is local.

Example 4: Boolean simplification / redundant compare removal

Before:

• cmp rA, #0
• beq label
• cmp rA, #0 (duplicate compare before another branch)

After:

• Keep only one cmp if the flags/registers haven’t changed:
  • Remove the second cmp and reuse the condition codes from the first compare.

Safety condition: If any instruction between the two compares could alter condition flags, you cannot remove or reuse without proving flag preservation.

Example 5: Load/store redundancy (with aliasing constraints)

Before:

• load r1, [p]
• ... (no stores through aliasing pointers)
• load r2, [p]

Potential peephole rewrite:

• Replace the second load with a move from the first:
  • load r2, [p] → mov r2, r1

Critical constraint: Peephole optimizers typically avoid aggressive alias analysis. Many compilers only do this when they can guarantee no intervening store may change [p] (e.g., p is a known register-based pointer with no aliasing hazards inside the peephole window).

Visual “before/after” summary table

Peephole optimization vs. other local optimizations

Peephole optimization is often grouped with “local” or “machine-level” optimization passes, but it is distinguished by its explicit sliding-window pattern replacement.

Key contrasts:

• Constant folding evaluates expressions at compile time (often on IR).
• Common subexpression elimination (CSE) removes duplicated computations, usually with broader analysis than a tiny window.
• Instruction combining (often similar in spirit) merges or simplifies instruction trees/sequences, frequently powered by target-specific semantics.

In practice, a compiler may implement peephole-like rewrites via machine-instruction pattern matchers, DAG combines, or rule-based instruction selection cleanup.

Conceptual relationship diagram