Peephole Optimization and the Sliding Window

Peephole optimization is the cheapest optimization in a compiler and the one most often misunderstood. It looks at a short sequence of instructions and replaces it with a shorter or faster sequence that has the same effect on the visible state. The window is small — two, three, or a handful of instructions — and the rewrites are local. What makes the technique worth a chapter of its own is not the size of the rewrites but the fact that they operate on the output of instruction selection, where the selector’s local decisions, described in Instruction Selection as Tree Tiling, have left patterns of waste that only become visible once the instructions are laid out in a stream.

The classic examples are a load followed by a store to the same address, a move into a register that is immediately overwritten, and a compare followed by a branch on the flags the compare set. Each is a two- or three-instruction pattern. Each is provably redundant or provably foldable. Together they account for a large fraction of the instructions a naive selector emits.

What the Window Sees

A peephole pass walks the instruction stream, and at each position it attempts to match the patterns in its rule set against the instructions starting there. A match produces a replacement, the stream is modified, and the walk continues — usually from a position a few instructions back, because a replacement can create a new opportunity with the instructions that precede it.

The state the pass needs is more than the instructions themselves. It needs to know which registers each instruction reads and writes, which flags it sets, whether it can trap, and whether it has side effects. Without that information a rewrite that looks safe may reorder a memory access across a store or delete an instruction whose result is observed by a handler. The standard implementation therefore annotates each instruction with a def-use summary before the pass runs, and the patterns are written in terms of those summaries rather than in terms of opcode names alone.

This is the point where peephole optimization shades into ordinary optimization. A rule that deletes a load because a preceding store to the same address defined the value is a local redundancy elimination, and the fact that its window is two instructions rather than a whole basic block is a restriction on scope, not on kind. The distinction matters because the restricted version is much cheaper to run and much easier to prove correct, and because the restricted version catches the cases that instruction selection creates, which is precisely what it is for.

The rule set is usually written in a domain-specific notation and compiled into a matcher, so that a target can add rules without touching the pass. Each rule states a pattern and a replacement, with costs attached. The matcher tries rules in order of decreasing specificity, or tries all of them and takes the cheapest replacement, depending on how much compile time the compiler is willing to spend.

A rule in the style of a table-driven peephole pass, with the window written on the left and the replacement on the right:

window:      store [B + d], R
             load  R2, [B + d]
replacement: store [B + d], R
             mov   R2, R

The rule is only legal when B and d are textually identical in both instructions, since without alias information any other address might refer to the same location.

The Recurring Rewrites

Four families of rewrite appear on nearly every target.

Redundant load elimination. A load from an address that a preceding store just wrote is replaced by the value stored, provided the address computation is identical and no intervening instruction aliases the location. The alias question is the hard part: without alias information, the pass must assume any store may alias any load, and the rule fires only when both use the same base register and the same displacement. That restriction makes the rule safe and makes it miss most cases in real code, which is why peephole passes on memory operations are usually paired with a stronger redundancy pass that has real alias analysis.

Move collapsing. A move into a register that is then used as the source of another move collapses into a single move, and a move whose destination is never read is deleted. Chains of moves through several registers collapse transitively. The rule set must be careful about partial writes: on a target where writing a 32-bit register zeroes the upper half of a 64-bit register, a move that was intended to preserve the upper half is not removable, and the pass needs a model of the write width to know the difference.

Compare-and-branch fusion. A comparison that sets condition flags followed by a branch that reads them becomes a single compare-and-branch instruction on targets that have one, which removes a branch and the instructions that would otherwise be needed to materialise the comparison’s result. On targets where the branch has a delay slot, the converse rewrite appears as well: an instruction whose result is needed only on the taken path, or one already on that path, is moved into the delay slot after the branch rather than left before it. Both rules are sensitive to the exact condition-code encoding, and the pass needs to know which flags a comparison sets and which a branch consumes.

Strength reduction of small operations. A multiply by a constant power of two becomes a shift, a multiply by three becomes a shift and an add, and a division by a constant becomes a multiply by a reciprocal plus a correction sequence. These rewrites are arithmetic identities, but they are only legal if the original instruction’s behaviour on overflow and on negative values matches the replacement’s. Signed division by a constant, in particular, needs a correction step for negative dividends, and a peephole rule that omits it produces wrong results for half the input domain.

A fifth family is target-specific: on x86, an xor of a register with itself is a shorter and faster way to zero it than a move from an immediate, and it breaks the dependency on the previous value of the register. Rules like this encode microarchitectural knowledge, and they age badly when the microarchitecture changes.

Window Size and the Cost of Searching

The natural question is why the window is small. A window of two instructions can be matched by checking every adjacent pair, which is linear work. A window of four needs a search over all four-instruction sequences that start at a position, and the number of candidate sequences grows with the product of the number of opcodes. A general window of size k over an instruction set of size n has n^k candidate patterns, and the rule set has to be authored and maintained against that space.

Real peephole implementations therefore use a mixture. The common rewrites are two-instruction patterns, checked directly. Larger rewrites are expressed as fixed sequences with wildcards for registers and immediates, so that the pattern space stays manageable. A few compilers allow a window of up to five or so with a hand-written matcher, but the number of rules does not grow linearly with the window size, because most combinations are meaningless.

There is a deeper reason the window stays small: the benefit of a rewrite depends on facts outside the window. A load is redundant only if no aliasing store intervenes, and the intervening instructions may be arbitrarily far away. A move is dead only if the register is not read later, which is a whole-function property. Peephole rules that ignore these facts are safe but weak; rules that assume them are unsafe. The resolution is to compute the global facts once and let the peephole pass consult them, which is exactly what a def-use annotation is.

The second reason is that rewrites interact. Applying rule A can enable rule B, and applying B first can prevent A. A pass that applies rules in a fixed order may reach a local minimum that a different order would have escaped. The usual mitigation is to iterate the pass until no rule fires, which terminates because each rule reduces a cost metric, and to order the rules so that the cheap and broadly applicable ones run first. Termination is not automatic: a pair of rules that undo each other would loop forever, and the standard safeguard is a rule-set check that no replacement is itself matched by a rule that reverses it.

Peepholes After Allocation

The most valuable placement of a peephole pass is not immediately after selection. It is after register allocation, when the allocator has inserted spill code and coalesced copies, because that is where the worst sequences appear.

A spill of a value that is used once produces a store followed by a load of the same location. If the value is in a register for the duration, the store and load can sometimes be replaced by the register itself, which is a local form of rematerialization. A copy that coalescing could not eliminate becomes a move between two registers, and a peephole rule can sometimes fold it into the following instruction’s addressing mode, turning a move plus an add into a single add with a different source register — the same fold that Folding Address Computation into Memory Operands describes from the selector’s side.

Post-allocation peepholes must respect the allocation. A rewrite that changes which registers an instruction reads or writes invalidates the allocator’s assumptions, so rules are restricted to transformations that preserve the register assignment — folding a move into an operand is fine, because the same registers are read, but introducing a new temporary is not. This restriction is why post-allocation peepholes are mostly about eliminating moves and folding addressing, and why the more ambitious rewrites run before allocation.

The placement also affects correctness around debug information. A rewrite that deletes a move makes the value that was in the source register unavailable under its old name, and a debugger reading that name sees the wrong value. Compilers handle this by emitting location lists that describe where a value lives across the rewrite, or by restricting the rewrites in code compiled without optimization. Neither approach is free, and the second is why unoptimized builds keep moves that optimized builds delete.

Limits

Peephole optimization cannot fix a bad instruction selection, and it cannot see across a basic block boundary. A redundant load whose defining store is in a different block is invisible to it. A move that is dead because of a later redefinition in another block is invisible too. The pass is a cleaner, not a planner, and its contribution is bounded by how much waste the selector and the allocator leave behind.

The technique also has a maintenance cost that grows with the target. Every architecture has idioms — instruction sequences that are shorter or faster than the obvious encoding — and each idiom needs a rule. Rules accumulate, some become obsolete when the microarchitecture changes, and the rule set becomes a place where knowledge about a specific chip is encoded in a compiler that must also target other chips. The alternative, encoding the same knowledge in the machine description’s pattern costs, moves the problem rather than solving it: the selector then makes the choice, but it makes it before the surrounding context is known, which is exactly the information the peephole pass has.