Peephole Optimization

Code straight out of a simple code generator is correct but naïve. It stores a value it just loaded; it multiplies by two the long way; it jumps to a label that only jumps somewhere else. Each blemish is tiny and local — and that is exactly what makes it easy to fix. Peephole optimization slides a small window — a "peephole" of two or three instructions — along the generated code and, wherever the window matches a known-wasteful pattern, rewrites it into something cheaper.

The whole method is a set of local rewrite rules plus one crucial control loop: keep sweeping until nothing changes — a fixed point. It is the compiler's cleanup crew: cheap, dumb, and remarkably effective, catching the leftover clumsiness that global optimizations don't bother with and that the code generator couldn't see one statement at a time.

A sliding window over the code

Picture the generated instructions in a column and a little frame covering a couple of them at a time. At each position the optimizer asks: "does what I can see match a rule?" If so, it rewrites; then it slides on. Reveal the sweep — each stop finds a different idiom to fix:

Every rewrite is justified purely by what is inside the window — no global analysis, no dataflow — which is what keeps peephole optimization fast and simple. The power comes not from any single clever rule but from having many small ones and applying them relentlessly.

The classic rule families

Peephole rules cluster into a handful of recurring categories. A representative rule from each:

CategoryBeforeAfter
Redundant load/storeLD R1, x ; ST x, R1LD R1, x
Algebraic identityADD R2, R2, 0(deleted)
Strength reductionMUL R3, R3, 2SHL R3, R3, 1
Constant foldingADD R5, 2, 3LD R5, 5
Dead / useless codeMOV R4, R4(deleted)
Jump-to-jump (control flow)goto L1 ; … ; L1: goto L2goto L2
Machine idiomSUB R6, R6, R6XOR R6, R6, R6

Redundant load/store deletes a store whose value provably already sits in the register. Algebraic identities (x+0, x\times 1) and strength reduction (x\times 2 \Rightarrow x \ll 1, x\div 8 \Rightarrow x \gg 3) replace an expensive operation with a cheaper equivalent. Constant folding evaluates compile-time-known arithmetic. Jump-to-jump simplification short-circuits chains of branches. And machine idioms swap a generic instruction for the target's preferred fast form (clearing a register with XOR R,R,R is a genuine x86 idiom). None of them needs to understand the program — only the window.

Why you must sweep to a fixed point

The single most important property of peephole optimization is that one rewrite can enable another. Delete an x+0 that sat between a load and a store, and suddenly the load and store are adjacent — exposing a redundant-store pattern that was invisible before. So a single pass is never enough: you must run passes repeatedly until a whole sweep makes no change. Because each rewrite makes the code strictly smaller or cheaper by some measure, the process is guaranteed to terminate.

repeat: changed ← false slide the window across the whole instruction list: if the window matches a rewrite rule: apply the rewrite; changed ← true until not changed // fixed point: a full pass changed nothing

A peephole optimizer you can run

The optimizer below carries a few rules — redundant store, add/sub of zero, multiply-by-two, useless move, and jump-to-jump — and sweeps to a fixed point. The input is deliberately arranged so that deleting an ADD …, 0 in the first pass makes a load and store adjacent, which the second pass then collapses — the enabling cascade in action:

function isLabel(s: string): boolean { return /^\w+:/.test(s); } // One sweep of the window. Returns the new code and whether anything changed. function pass(code: string[]): { code: string[]; changed: boolean } { const out: string[] = []; let changed = false; for (let i = 0; i < code.length; i++) { const cur = code[i], nxt = code[i + 1] ?? ""; // Redundant store after load: LD Rn, m ; ST m, Rn -> keep the load, drop the store. const ld = cur.match(/^LD (R\d+), (\w+)$/); if (ld && nxt === `ST ${ld[2]}, ${ld[1]}`) { out.push(cur); i++; changed = true; continue; } // Algebraic identity: ADD/SUB Rn, Rn, 0 -> delete. if (/^(?:ADD|SUB) (R\d+), \1, 0$/.test(cur)) { changed = true; continue; } // Strength reduction: MUL Rn, Rm, 2 -> SHL Rn, Rm, 1. const mul = cur.match(/^MUL (R\d+), (R\d+), 2$/); if (mul) { out.push(`SHL ${mul[1]}, ${mul[2]}, 1`); changed = true; continue; } // Useless move: MOV Rn, Rn -> delete. if (/^MOV (R\d+), \1$/.test(cur)) { changed = true; continue; } // Jump-to-jump: goto L, where "L: goto M" exists -> goto M. const g = cur.match(/^goto (\w+)$/); if (g) { const tgt = code.find((s) => s.startsWith(g[1] + ":")); const gm = tgt?.match(/^\w+: goto (\w+)$/); if (gm) { out.push(`goto ${gm[1]}`); changed = true; continue; } } out.push(cur); // no rule fired: keep the instruction (and never delete across a label) } return { code: out, changed }; } let code = [ "LD R1, x", "ADD R9, R9, 0", // identity — deleting it makes LD and ST adjacent "ST x, R1", // redundant store, but not yet adjacent to the LD "MUL R3, R3, 2", // strength reduction "MOV R4, R4", // useless move "goto L1", // jump-to-jump "L1: goto L2", ]; let n = 0, changed = true; while (changed && n < 10) { const r = pass(code); code = r.code; changed = r.changed; n++; console.log(`--- after pass ${n} ---`); code.forEach((l) => console.log(" " + l)); } console.log(`reached a fixed point after ${n} passes`);

Pass 1 folds four idioms at once but cannot yet touch the store; pass 2 collapses the now-adjacent load/store; pass 3 finds nothing and the sweep halts. That "run again because a rewrite opened a new opportunity" is the entire discipline of peephole optimization.

Classic peephole optimizers work on a linear window and stop at block boundaries, but the idea generalises. Superoptimizers take the peephole concept to its logical extreme: given a short instruction sequence, search all possible shorter sequences and keep any that is provably equivalent — finding rewrites no human rule-writer anticipated. Peephole rules can also be learned or verified with an SMT solver to guarantee each rewrite preserves semantics on every input. But the humble sliding-window optimizer with a hand-written rule set remains a fixture of every back end precisely because it is so cheap and catches so much of the low-hanging fruit that earlier phases leave behind.

The dangerous peephole bug is rewriting across a label. If some instruction inside your window is the target of a jump from elsewhere, control can enter the window in the middle — so a rule that assumes the window runs top-to-bottom (like "delete this store because the value is still in the register") is simply wrong: a branch might reach the store without ever executing the load. Never delete or merge instructions across a label unless you have confirmed nothing branches into the region. This is the peephole echo of the basic-block idea — a window that spans a label is no longer single-entry.

The second discipline is iteration. Because rewrites enable one another, a single pass leaves easy wins on the table. Always loop to a fixed point — but bound the loop (each rewrite must make measurable progress) so a badly-written pair of rules that undo each other can't spin forever.