Peephole Optimization¶
Local rewrite method — instantiates Equivalence-Preserving Rewrite Optimization
Slides a small window along a linear sequence and replaces short, locally-matched runs with cheaper equivalents — greedy, local, and swept to a fixpoint.
Rewriters and code generators routinely leave behind short, silly local sequences — a value stored and immediately reloaded, a multiply that could be a shift, two adjacent operations that cancel. Peephole Optimization cleans these up by sliding a small window — the "peephole," usually two to a handful of adjacent items — along a linear sequence and, wherever a short pattern from a fixed table matches, swapping in a cheaper equivalent on the spot. What makes it this mechanism and not its whole-program siblings is radical locality: it carries no dataflow graph, no cost model, no global picture at all. It knows a small catalogue of local patterns and one habit — scan, match, replace, and sweep again until nothing fires. That narrowness is the point: it is cheap, fast, and safe precisely because it only ever reasons about what it can see through the hole.
Example¶
A 2-D image-editing app compiles a user's edit history into a linear stream of operations before rendering: rotate(90°) · rotate(−90°) · grayscale · grayscale · scale(2×) · scale(0.5×) · …. Much of it is redundant — the user undid and redid things. A peephole pass slides a two-op window down the stream, carrying a small table of local identities: two inverse rotations cancel, grayscale twice equals grayscale once (idempotent), scale(k)·scale(1/k) is a no-op.
The window over rotate(90°) · rotate(−90°) matches "inverse pair" and deletes both; over grayscale · grayscale it matches "idempotent" and drops one. It never asks what the whole pipeline computes — each rewrite is licensed by the local pattern alone. After one sweep the stream is shorter, and because deleting a pair can bring two new neighbours together (a fresh match), it sweeps again, repeating until a full pass changes nothing. The rendered image is pixel-identical; the pipeline just does far less work to produce it.
How it works¶
Three things define the method, and all three are local. A pattern table of short equivalences, each safe on syntactic match. A sliding window of a few adjacent items that moves along the sequence. And a sweep-to-fixpoint habit: because one replacement can expose another at the seam it just created, the pass re-runs until an entire scan fires no rule. What it deliberately lacks is what distinguishes it — no global analysis weighs whether a rewrite is worth it, so every table entry must be an unconditional local win, or carry a guard checkable entirely inside the window.
Tuning parameters¶
- Window size — how many adjacent items the peephole spans. A wider window matches longer patterns and catches more, but enlarges the table and slows every scan.
- Pattern table scope — how many local identities are encoded, and how target-specific. A richer table cleans more but is harder to keep correct; each entry must be a genuine local win.
- Sweep policy — single pass versus repeat-to-fixpoint. Re-sweeping catches the new matches earlier rewrites expose, at the cost of extra passes.
- Scan direction — forward, backward, or both. Some patterns (a definition and a later use) only line up when scanned in a particular direction.
- Guard strictness — how conservatively a rule checks its local preconditions (a live flag, a value read later in the window). Looser guards fire more often but risk deleting something with a local side effect.
When it helps, and when it misleads¶
Its strength is dirt-cheap, dependable local cleanup: it catches the small redundancies that whole-program analysis is overkill for, runs in near-linear time, and composes with heavier passes — it is the classic last-mile tidy-up run after a bigger optimizer or code generator.
Its ceiling is that same locality. Peephole is a greedy local search: it sees only inside the window, so it misses every improvement that requires non-local structure, and a locally-good rewrite can even foreclose a globally better one — a local optimum.[n1] A subtler trap is a rule that looks safe but ignores a side effect the window doesn't show (an instruction that also sets a condition flag read later). The classic misuse is trusting the pattern table without proving each entry preserves behaviour, or widening the window until the "peephole" is quietly doing a job that belongs to a real dataflow pass. The discipline: keep each rule provably meaning-preserving on its own, keep the window small, and let a whole-function optimizer own the non-local work.
How it implements the components¶
Peephole Optimization fills only the components a local, pattern-driven method owns:
rewrite_rule_set— it carries a table of short, local equivalences (inverse-pair cancellation, idempotent collapse, strength reduction) and applies them on syntactic match.rewrite_priority_strategy— its window scan is the strategy: which local site to examine next, in what direction, and re-sweeping to a fixpoint as new matches surface.
It does not enumerate a whole-function candidate space or select transforms by a cost model (that is Compiler Optimization Pass), it does not author the equivalence contract that certifies its patterns are safe (Algebraic Simplification Rulebook), and it does not verify that its output preserved behaviour (Golden-Output Regression Test, Property-Based Equivalence Test).
Related¶
- Instantiates: Equivalence-Preserving Rewrite Optimization — peephole is the narrow, local-window application of the pattern.
- Consumes: Algebraic Simplification Rulebook — its local pattern table draws on catalogued, precondition-guarded identities.
- Sibling mechanisms: Compiler Optimization Pass · Algebraic Simplification Rulebook · Normal-Form Reduction · Benchmark Harness · Golden-Output Regression Test
Editorial Notes¶
Form Classification¶
Form family: Analysis, Modeling & Optimization
Rationale: The mechanism applies a local equivalence table over a sliding window and iterates rewrites to a fixpoint to compute a cheaper sequence.
Nearest alternative: Control, Automation & Runtime — A compiler may execute it automatically, but it performs offline optimization rather than runtime actuation of an external target.
Review outcome: Adjudicated after independent review; high confidence.
Origin Attribution¶
Primary origin: Computer Science & Software Engineering
Origin pattern: Single lineage
Present-day reach: Specialized
Rationale: Peephole Optimization is rooted in computer science and software engineering: Compiler engineering established peephole optimization as local equivalence-preserving instruction rewriting.
Review outcome: Independent reviewer agreement; high confidence.
Notes¶
Peephole is usually run after a bigger optimizer or code generator, and re-run between other passes — its value compounds because earlier transforms leave exactly the kind of local litter it is built to sweep. That placement (cleanup, repeated, last) is part of using it well: it is a complement to whole-program optimization, not a substitute for it.
[n1] A local optimum is a state better than all its near neighbours yet worse than the global best; greedy local search — exactly what a peephole does — is prone to settling in one. It is why peephole is paired with, not a replacement for, optimizers that reason about global structure. ↩