Peephole Optimization

When a compiler finishes turning your source code into machine instructions, the result is often technically correct but unnecessarily verbose. The code generator follows rules one at a time, and those rules leave trails — a value moved into a register only to be moved right back out, a branch that always jumps to the very next line, an arithmetic operation on zero that changes nothing.

Peephole optimization is the compiler pass that hunts down those trails. It slides a small window — the peephole — over the instruction stream and asks: "can I replace what's inside with something shorter or cheaper?" If a rule matches, it fires; the window slides forward; the process repeats. The name comes from peering through a hole so small you can only see a few instructions at a time.

First described formally by William McKeeman in 1965, the technique is one of the oldest tricks in the compiler toolbox and still one of the most effective. No matter how sophisticated the front end is, a peephole pass at the end can quietly erase whole classes of waste in a single linear scan.

Below is a short sequence of fictional assembly-like instructions — the kind a naive code generator might emit. Click Optimize to run the peephole pass: the optimizer slides a window of two instructions at a time and fires any matching rewrite rule.

<!-- {{c_html_intro}} -->
<p class="hint">{{hint_para}}</p>
<div class="panel">
  <div class="col">
    <div class="col-label">{{label_before}}</div>
    <ol id="before-list" class="instr-list"></ol>
  </div>
  <div class="arrow-col">&#8594;</div>
  <div class="col">
    <div class="col-label">{{label_after}}</div>
    <ol id="after-list" class="instr-list"></ol>
  </div>
</div>
<div class="trace-box">
  <div class="trace-label">{{label_trace}}</div>
  <ul id="trace-list"></ul>
</div>
<div class="btns">
  <button id="btn-optimize" type="button">{{btn_optimize}}</button>
  <button id="btn-reset" type="button" class="ghost">{{btn_reset}}</button>
</div>

/* {{c_css_intro}} */
* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; padding: .5rem; }
.hint { font-size: .88rem; color: #444; margin: 0 0 .8rem; line-height: 1.5; }
.panel { display: flex; align-items: flex-start; gap: .4rem; margin-bottom: .6rem; }
.col { flex: 1; min-width: 0; }
.col-label { font-size: .75rem; font-weight: 700; color: #5a7088; text-transform: uppercase;
             letter-spacing: .05em; margin-bottom: .3rem; }
.arrow-col { font-size: 1.4rem; color: #5a7088; padding-top: 1.6rem; flex: 0 0 auto; }
.instr-list { margin: 0; padding: 0; list-style: none; }
.instr-list li { font: 13px/1.7 ui-monospace, monospace; padding: .15rem .4rem;
                 border-radius: 5px; border: 1px solid transparent; margin-bottom: 2px; }
.instr-list li.removed { background: #fde8e8; border-color: #f5b7b7; color: #a02020; text-decoration: line-through; }
.instr-list li.kept    { background: #e8f5e9; border-color: #a5d6a7; }
.instr-list li.normal  { background: #f0f4f8; border-color: #d0d8e4; }
.trace-box { background: #f8f9fb; border: 1px solid #d0d8e4; border-radius: 8px;
             padding: .5rem .7rem; margin-bottom: .7rem; min-height: 2.5rem; }
.trace-label { font-size: .75rem; font-weight: 700; color: #5a7088; text-transform: uppercase;
               letter-spacing: .05em; margin-bottom: .3rem; }
#trace-list { margin: 0; padding-left: 1.1rem; }
#trace-list li { font-size: .82rem; color: #333; line-height: 1.55; }
#trace-list li.rule-fired { color: #0a7d33; }
#trace-list li.no-change  { color: #888; font-style: italic; }
.btns { display: flex; gap: .5rem; flex-wrap: wrap; }
button { font: 600 14px system-ui, sans-serif; padding: .45rem .9rem; border: 1px solid #1d3557;
         background: #1d3557; color: #fff; border-radius: 8px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }

// Code not found

Each fired rule is highlighted in the trace. Notice how every optimization is local: the pass never needs to look at the whole program, just two adjacent instructions. That locality is both the strength (linear time, single pass) and the limit (patterns that span more than a few instructions escape the window).

The peephole pass itself is easy to run: one linear scan, $O(n)$ time, where $n$ is the number of instructions. That simplicity is a big part of its appeal.

The hard questions are elsewhere:

• Rule correctness. Every rewrite rule must preserve the observable behavior of the program — the same registers must hold the same values at every point that the outside world can see. A wrong rule silently corrupts output. Proving all rules correct for a real ISA (with flags, memory aliasing and calling conventions) is substantial engineering.
• Rule completeness. The set of rules is never exhaustive. Patterns that span more than the window width escape detection entirely. Choosing the window size is a trade-off: wider windows catch more waste but slow down the pass and grow the rule table exponentially.
• Rule ordering and confluence. Firing one rule can expose a pattern for another. If the rules are not confluent — meaning they can be applied in any order and always reach the same normal form — the optimizer's output depends on the order rules are tried, which is a subtle correctness hazard.
• Superoptimization. Finding the optimal replacement for a window — not just a better one, but the best possible — is equivalent to a bounded program synthesis search, which is PSPACE-hard in general. Real compilers use hand-curated rule tables rather than searching.

So while the runtime is trivial, the design space of a peephole optimizer is anything but. Getting the rules right, complete enough, and confluent is where compiler engineers earn their keep.

Peephole optimization is not a curiosity — it ships inside every serious compiler:

• GCC and LLVM: both run multiple peephole-style passes under names like combine, simplify and instcombine. LLVM's InstCombine pass alone contains thousands of rewrite rules and fires hundreds of millions of times per compilation of a large project.
• JIT compilers: the Java HotSpot VM and V8 (JavaScript) apply peephole rewrites on the hot paths they compile at runtime, where even a 5 % speedup is worth a microsecond of compile time.
• Embedded and RISC-V toolchains: on microcontrollers where code must fit in kilobytes, removing a single redundant load instruction can matter enormously — the peephole pass is often the only optimization enabled at size-optimized build settings.
• Bytecode interpreters: Python's peephole.c (now flow_graph.c) has removed redundant LOAD/STORE pairs since Python 2.6.
• Teaching compilers: because the rules are simple and the results are visible, a peephole pass is typically the first optimization students implement when studying compiler construction.

The technique also appears in hardware: modern CPUs execute a micro-architectural version of peephole optimization internally, fusing adjacent instructions (e.g., compare-and-branch) into a single operation with no software involvement at all.

Peephole optimization is a masterclass in doing a lot with very little. A window two or three instructions wide, a handful of rewrite rules, and a single linear pass — and yet this tiny mechanism quietly erases redundant moves, dead stores, identity operations and useless branches in every program a serious compiler produces.

The lesson generalizes: many hard-looking problems yield to purely local reasoning if you pick the right window. And if local reasoning is not enough — if the waste only becomes visible across a larger context — that is the signal to reach for a more global analysis like program synthesis or dataflow analysis. The peephole pass is where compilers start, and for a surprising fraction of real programs, it is also where they finish.