Peephole Optimization: How Compilers Polish Machine Code

The Core Idea and the Sliding-Window Invariant

A peephole optimizer treats the instruction stream as a linear sequence and passes a small window — the "peephole", historically 2 to 4 instructions — across it. At each position it tests the window's contents against a set of rewrite rules. If a rule's left-hand pattern matches, the window is replaced by the rule's right-hand side, which is provably equivalent but cheaper (fewer instructions, cheaper opcodes, or better addressing modes).

The governing invariant is semantic equivalence: every rewrite must preserve the program's observable behavior — the same final register/memory state and the same side effects — under all inputs. Crucially the window need not be physically contiguous in memory; what matters is that the matched instructions are data- and control-independent of anything between them, so removing or reordering them changes nothing. Classic targets:

• Redundant load/store: store R1, x followed by load R1, x — the load is dead, delete it.
• Algebraic identities: add R1, 0, mul R1, 1, x & x ⇒ delete or simplify.
• Strength reduction: mul R1, 8 ⇒ shl R1, 3; x % 2 ⇒ x & 1.
• Jump chaining: a branch to an unconditional jump ⇒ retarget to the final label; a jump to the fall-through instruction ⇒ delete it.
• Dead instructions: a computation whose result is never read before being overwritten.

How It Works, Step by Step

The canonical driver is a single left-to-right scan with a fixed window, repeated until a fixed point:

peephole(code, rules, k):
  repeat:
    changed = false
    for i in 0 .. len(code) - 1:
      window = code[i .. i+k-1]      # up to k instructions
      for rule in rules:
        if rule.matches(window):
          code[i..] = rule.rewrite(window) + rest
          changed = true
          i = i - 1                   # rescan from i (loop's i++ lands back at i)
          break
  until not changed
  return code

Key mechanics:

• Restart-at-i: after a rewrite, matching resumes at the same index, so a cascade (rule A exposes rule B which exposes rule C) collapses in one outer iteration when possible. This is why a*2*2*2 can shrink to a<<3.
• Fixed point: the outer repeat loops until a full pass makes no change. Termination requires a measure that strictly decreases (e.g., instruction count or a lexicographic cost) on every rewrite; without it, cyclic rules could loop forever.
• Logical vs. physical window: mature implementations don't match raw bytes. They match over an IR or a normalized instruction list, often keying rules on opcode + operand shape, so "adjacent" means adjacent in a def-use sense, not in memory.

McKeeman's original 1965 formulation worked on assembly; modern compilers apply the same discipline to a typed IR (LLVM), to bytecode (JVM/V8), or to a low-level machine IR just before emission (GCC's peephole2 in the .md machine description).

Complexity Analysis

Let n be the number of instructions, k the window size, and r the number of rules. A single pass visits each of the n positions and tries r rules over a k-wide window, so one pass is O(n · r · k). Because k and r are compile-time constants (k is 2–4; r is fixed for a given target), a pass is Θ(n) in the input program size — this is the property that makes peephole cheap enough to run late and often.

• Best case: Θ(n) — one pass reaches a fixed point (no cascading).
• Worst case: O(n²) in pathological chains where each rewrite exposes exactly one more and the fixed-point loop must re-scan. Each rewrite strictly decreases instruction count, so there are at most n rewrites; bounding total re-scans gives O(n²). In practice compilers cap the iteration count (LLVM limits InstCombine iterations) to keep it near-linear.
• Space: O(k) for the window itself — effectively O(1). Rule dispatch is typically a hash/switch on the leading opcode, so matching is O(1) amortized rather than a linear scan of all r rules.

Contrast this with global optimizations built on the control-flow graph: dataflow fixed-point iteration is O((V+E)·height-of-lattice) and dominator/SSA construction adds more. Peephole buys most of its wins with none of that machinery — its comparative advantage is locality.

Trade-offs and When to Use It

Peephole optimization is a local optimizer, and its strengths and blind spots both flow from that.

• Wins: near-linear time, no analysis, trivially parallelizable per basic block, and it catches exactly the redundancies that other passes create. Register allocation, instruction selection, and macro expansion all emit locally suboptimal code; peephole is the broom that follows them.
• Blind spots: anything requiring reasoning beyond the window. It cannot hoist a loop-invariant computation, cannot do global common-subexpression elimination across blocks, and cannot see that a value is dead three blocks later. Those need liveness, dominators, and a CFG.
• Placement matters: the standard recipe runs peephole after instruction selection and register allocation (to clean their leftovers) and sometimes between other passes to expose new opportunities. LLVM runs InstCombine repeatedly, interleaved with other passes, precisely because each pass feeds the next.

The right mental model: peephole is complementary, not competitive, with global optimization. Use it as the finishing polish, and lean on it heavily in JITs where compile-time budget forbids expensive whole-function analysis.

Real Systems and How They Do It

Every production compiler ships a peephole layer, though the branding differs:

• LLVM — InstCombine & DAGCombine: InstCombine is a peephole over LLVM IR with thousands of rules (x - x → 0, (a & b) | (a & c) → a & (b|c), canonicalizations that later passes rely on). LLVM even verifies many rules automatically via Alive2, an SMT-based tool that proves each rewrite correct. DAGCombine does the same on the selection DAG during backend lowering.
• GCC — define_peephole2: target maintainers write peephole patterns directly in the machine-description (.md) files, matching RTL and rewriting to better instruction sequences for that architecture.
• V8 / TurboFan & the JVM: JIT compilers apply peephole-style simplification on bytecode and on the sea-of-nodes IR to keep codegen fast.
• Superoptimizers: tools like Souper discover new peephole rules by exhaustively searching for shorter equivalent sequences and proving equivalence with an SMT solver — automating what McKeeman did by hand.

The standard references are the Dragon Book (Aho, Lam, Sethi, Ullman) §8.7 and Muchnick's Advanced Compiler Design and Implementation, which catalog the classic rule families.

Pitfalls, Edge Cases, and Variants

The naïve version is easy; the correct version is subtle. The recurring failure modes:

• Ignoring flags/side effects: replacing mul R1, 8 with shl R1, 3 is fine — until a later instruction reads the CPU's overflow/carry flag, which the two set differently. A rewrite must preserve all observable state, including condition codes and traps.
• Aliasing and volatility: deleting a redundant load is invalid if the memory is volatile or if a store through an aliasing pointer sits between the two — the second read may legitimately differ.
• Non-termination: a pair of rules that undo each other (A→B and B→A) loops forever. Guard against it by requiring every rewrite to reduce a well-founded cost measure, and by choosing a canonical form so only one direction is ever applied.
• Undefined behavior traps: "optimizing" x + 1 > x to true for signed x is a real, standards-permitted rewrite — but such UB-based peepholes surprise programmers and are why Alive2-style proofs matter.
• Signed/unsigned and width: x / 2 is shr for unsigned but needs a rounding adjustment for negative signed values — a shift alone is wrong.

Notable variants: logical (IR-level) peephole vs. physical (assembly-level) peephole; superoptimization, which searches for optimal short sequences rather than applying a fixed rulebook; and cross-block peephole, a mild extension that peeks across a fall-through boundary while respecting the CFG. In every variant, correctness beats cleverness — a single unsound rule can miscompile every program the compiler touches.

Peephole optimization vs. global (dataflow-based) optimization

Property	Peephole	Global optimization
Scope	Sliding window of k instructions	Whole function / CFG
Analysis needed	None (pattern match only)	Dataflow, dominators, liveness
Time complexity	O(n·k), ~O(n) for fixed k	O(n) to O(n²) or worse per pass
Space complexity	O(k)	O(V + E) for CFG + lattices
Catches	Local redundancy, strength reduction	Cross-block motion, GCSE, inlining
Typical role	Final cleanup pass	Core mid-end optimization