Codegentarget

Peephole Optimization

A small window slid over the finished instruction stream, rewriting local patterns. Our backend's real peephole deletes `mov X, X` — an instruction that exists only because the register allocator happened to give a copy the same source and destination.

The question

What can a compiler still fix by looking at two or three adjacent instructions?

Source→Lexing→Tokens→Parsing→AST→Semantics→Typed→IR→Optimize→Codegen→Machine code→Link→Execute

What the program is here

The final machine instruction stream — physical registers, real opcodes, in emission order — viewed through a sliding window of two to four instructions. The window is the point: it is a representation deliberately small enough that matching is trivially cheap and every rewrite is provably local, which is what makes it safe to run at the very end when no analysis infrastructure survives.

What this phase may assume or do

A peephole rewrite is legal only if the replacement sequence has the same effect as the original on *everything observable outside the window*: every register live after the window, memory, and every implicit operand including the condition flags. That last one is the trap. Replacing mov rax, 0 with the shorter xor eax, eax is legal only where the flags are dead afterwards, because xor writes them and mov does not. A window has no liveness information unless it is given some, which is why real peepholes run with a liveness side-table rather than on text.

Key points

A peephole slides a two-to-four instruction window over the final stream and applies local rewrites — no analysis, no control flow, no whole-function view.
Most of what it removes is not in the source or the IR: it is an artefact created by the interaction of selection, allocation and block layout.
Our backend's real rule deletes mov X, X, which appears whenever the allocator gives a copy the same source and destination register.
Running the check once as a final pass rather than guarding every emission site is the entire structural argument for the pass existing.
Almost every other rule has a precondition — usually about the flags or about liveness — and a peephole that grows preconditions it cannot check has stopped being a peephole.
Because the rules are small and local, they are verifiable by a solver, and in LLVM's IR-level case they actually are.

The window our backend actually has

targetx86-64. mov reg, reg not writing flags is an x86 property; on ARM, movs does write flags and mov does not, so the mnemonic distinction carries the information. Note also the x86-specific subtlety that mov eax, eax is *not* a no-op in 64-bit mode — writing a 32-bit register zeroes the upper 32 bits — so the rule as written applies to the 64-bit form only. Our backend emits 64-bit operands exclusively, which is the only reason its one-line regex is sound.

Our backend's peephole is one line and it is not a toy: after all instructions have been emitted, it deletes every instruction matching mov X, X. That instruction is never written by any pattern deliberately. It appears because instruction selection emitted a copy for a three-address-to-two-address conversion, or because out-of-SSA turned a phi into a move, and then the register allocator happened to assign the same physical register to both ends of it.

That is the characteristic shape of peephole work: the redundancy is not in the source and not in the IR. It is an artefact created by the interaction of two backend phases, each of which was doing its job correctly. The selector could not know what the allocator would decide. The allocator was not asked to eliminate instructions. So a third pass, running after both, removes what neither could see.

The alternative would be to guard every emission site — check before emitting whether the move is redundant. Our backend deliberately does not, and the comment in codegen.ts says why: doing it at the emission sites means the check is duplicated at every site and forgotten at the next one added. Running it once as a final filter is the whole argument for having a peephole pass at all.

The rewrite our peephole performs, from src/compilers/sim/codegen.ts

Before

mov  rax, rbx
add  rax, rcx
mov  rax, rax
ret

After

mov  rax, rbx
add  rax, rcx
ret

Legal only when

A move from a register to itself changes no register, no memory and — on x86-64 — no flags, since mov does not write them. It is therefore removable unconditionally, whatever produced it. This is the rare peephole rule with no precondition at all, which is exactly why it is the one safe to implement as a text filter.

Illegal when

The same reasoning does not extend to the neighbouring rewrites. Turning mov rax, 0 into xor eax, eax is illegal if the flags are live afterwards, because xor clears them. Deleting a mov between two *different* registers is illegal unless the destination is provably dead, which needs liveness the window does not have. And on an architecture where a self-move has an architectural effect — some mov forms zero the upper half of a register, some ISAs use a self-move as a hint — the rule is not even sound.

What else fits in a window

The classic peephole catalogue is small and each entry is boring in isolation. Fold add rax, 4 followed by add rax, 4 into add rax, 8. Delete a jump to the immediately following label. Replace imul rax, rax, 8 with a shift, or a cmp against zero followed by a conditional jump with a test. Remove a load of a value that was just stored to the same address. Individually these save one instruction; collectively, applied over an entire program, they are the difference between output that looks machine-generated and output that looks written.

Two things make the catalogue worth having. First, most of the entries fire on artefacts of other phases rather than on anything a programmer wrote — jumps to the next instruction come from block layout, redundant loads come from spill code, self-moves come from allocation. Second, the rules compose: applying one rewrite frequently makes an adjacent one match, so a peephole pass is usually run to a fixed point over the window rather than in a single sweep.

The seductive failure is to keep adding rules until the pass is an optimizer. A peephole that needs liveness, aliasing or control-flow information is not a peephole any more; it is a badly-structured optimizer running at the wrong end of the pipeline, and it will eventually apply a rewrite whose precondition it cannot check.

A peephole catalogue, with what each rule actually requirestarget

Pattern	Rewrite	Precondition
`mov X, X`target	delete	None on x86-64 with 64-bit operands. The one genuinely unconditional rule.
`add r, 4` ; `add r, 4`target	`add r, 8`	Nothing reads `r` or the flags between them, and the folded immediate still fits the field.
`jmp L` ; `L:`	delete the jump	The label is the next instruction and no other edge relies on the jump existing.
`mov [m], r` ; `mov r2, [m]`target	`mov r2, r`	No aliasing store between them, and the memory is not volatile — this rule needs information the window does not have.
`mov r, 0`target	`xor r32, r32`	The flags must be dead afterwards. Shorter encoding and breaks the dependence on the old value; illegal where the flags are live.
`cmp r, 0` ; `je L`target	`test r, r` ; `je L`	Shorter encoding, same flags for equality. Not equivalent for every condition code, so the rule is per-condition.

Why a table of local rewrites is verifiable

implementationAlive2 verifies LLVM IR-level rewrites, where "same behavior" must account for LLVM's undef and poison semantics — a large part of why the tool found real bugs. Machine-level peepholes are verified less systematically, because the semantics of a full instruction set including flags, partial-register writes and memory ordering are much harder to formalise than an IR's. Nothing here says your compiler's machine peephole table is verified; most are not.

A peephole rule is a small, self-contained equivalence claim: this short sequence computes the same thing as that short sequence, under a stated precondition. That is exactly the kind of statement an SMT solver can check exhaustively over all 64-bit inputs, and it is why peephole tables are one of the few parts of a production compiler that are formally verified in practice.

The Alive and Alive2 tools do this for LLVM's InstCombine — LLVM's IR-level peephole — by translating a proposed rule into a formula and asking a solver whether any input distinguishes the two sides, including in the treatment of undefined and poison values. Rules that had been in the compiler for years have been found unsound this way. The point generalises: the smaller and more local a transformation is, the more completely it can be verified, which is an argument for keeping peepholes genuinely small rather than a consolation prize for their limited power.

It also connects the other way. Superoptimization searches for the shortest sequence equivalent to a given one and proves the equivalence; run offline over common short sequences, it is a *generator* of peephole rules rather than a compilation technique. Souper does this for LLVM. So the modern peephole is increasingly a machine-generated, machine-verified table, which is a much better place for a compiler to be than a hand-written list of rules somebody was fairly confident about.

How it works

The steps, in the order the compiler takes them.

The full instruction stream is emitted with no attempt to avoid local redundancy at the emission sites.
A window of two to four consecutive instructions slides over the stream, together with whatever side information the pass is given — typically physical-register liveness.
At each position the window is matched against the rule table; the first rule whose pattern and precondition both hold fires.
The matched instructions are replaced in place, and the window is backed up so that a rewrite which enables an adjacent rewrite is caught.
The sweep repeats until no rule fires, or until an iteration cap, since some rule sets can cycle.

How it breaks

What the engineer observes when it goes wrong — not what goes wrong internally.

A rewrite that clobbers the flags is applied where the flags are live, and a conditional branch several instructions later goes the wrong way. The function returns wrong answers only on the inputs that reach that branch.
A load-after-store is folded across an aliasing store the window could not see, and a value read from memory is stale. The bug appears only when two pointers happen to overlap at run time.
Two rules rewrite into each other and the pass loops until it hits its iteration cap, adding seconds to every compilation with nothing to show for it.
A jump-to-next-label is deleted while another basic block still branches to that label through a path the pass did not model, and control falls through into the wrong block.
The rule table grows to hundreds of entries that fire in table order, and a reordering during a refactor silently changes generated code across an entire product.

When it helps

Cleaning up after phases that cannot see each other: allocation artefacts, out-of-SSA copies, block layout jumps, spill-reload pairs.
Backends that use macro expansion instead of a real selector — there, a peephole pass recovers much of what a pattern table would have given.
Code size, where a handful of shorter encodings across an entire binary is a measurable fraction of the instruction cache footprint.

When it hurts

When it is asked to do work that needs global information. A peephole cannot see whether a register is used two blocks later, and a rule that assumes it can is a latent miscompilation.
Debug builds, where deleting instructions further degrades the correspondence between source lines and machine code.
As a substitute for fixing the phase that produced the redundancy. If the allocator is generating thousands of self-moves, the peephole hides a coalescing problem rather than solving it.

What it costs

Every one of these is paid by something.

Running as a separate final pass buys a single place where local cleanups live and costs an extra sweep over every instruction, plus the liveness side-table most useful rules need.
A larger rule table buys smaller, faster code and costs correctness surface: every entry is an equivalence claim over all inputs, and an unsound one is a miscompilation that no test may reach.
Iterating to a fixed point buys the cascading rewrites that make the pass worthwhile and costs compile time plus the obligation to prove or cap termination.

What else you could do

What a different compiler or language does instead, and when that is better.

Avoid the redundancy at the source: coalescing in the register allocator removes most self-moves before they are emitted, which is strictly better because it also reduces register pressure — see [[coalescing-and-rematerialization]].
A proper local optimizer over a basic block with real liveness and a dependence graph. More powerful, more expensive, and no longer local — at which point the useful comparison is with [[common-subexpression-elimination]].
A generated and solver-verified rule table (Souper, Alive2) instead of a hand-written one: better guarantees, and a build dependency on a solver.
Do nothing and let the hardware absorb it. A self-move on a modern x86 core is eliminated at register rename and costs no execution resource — though it still costs decode bandwidth and instruction cache space, which is why compilers remove it anyway.

See it for yourself

The flag, dump or tool that shows you this directly.

LLVM's IR-level peephole: opt -passes=instcombine -S file.ll and diff against the input. This is where most LLVM peephole activity actually is.
The machine-level one: llc -print-after=peephole-opt file.ll, and -print-after=machine-cp for the copy propagation that removes most redundant moves.
GCC: -fdump-rtl-peephole2 writes the RTL before and after the peephole pass.
See what survives to the bytes: objdump -d file.o and look for self-moves, jumps to the next instruction, and xor used to zero — the last is the peephole having fired.
Ours: emitAssembly in src/compilers/sim/codegen.ts ends with a single filter deleting mov X, X; the assembly explorer at /compilers/codegen shows the stream after it has run.

Plausible wrong readings

Stated the way a confident engineer states them.

"The peephole optimizer is where the compiler makes code fast." It is where the compiler stops embarrassing itself. The speed came from the middle-end.
"These redundancies are in my code." Almost none of them are. Self-moves, redundant jumps and spill-reload pairs are all artefacts of backend phases that could not see each other.
"Deleting a mov is always safe." Deleting a move from a register *to itself* is safe on x86-64 at 64-bit width. Deleting a move between different registers requires knowing the destination is dead, and the window does not know that.
"A bigger rule table is strictly better." Every rule is an unproven equivalence claim unless someone proved it, and rules that fire in table order make generated code sensitive to the order of a list.

Misconceptions

The claim, and what is actually true.

Peephole optimization looks at the source code.

It runs at the very end, on physical-register machine instructions. It has no access to types, names, control flow or anything else the frontend knew.

If the peephole can fix it, an earlier phase did something wrong.

Usually no single phase was wrong. The redundancy is emergent: the selector emitted a legitimate copy and the allocator made a legitimate assignment, and only their combination is redundant.

A peephole rule is obviously correct because it is short.

Shortness makes it checkable, not correct. The famous unsound rules in real compilers are all short, and they are unsound because of flags, poison values or partial-register writes rather than because of complexity.

Go deeper

The same idea at increasing depth. Stop wherever it stops being useful.

overview

After all the real work is done, a compiler slides a small window over the finished instruction list and deletes or shortens obviously silly local sequences: a move from a register to itself, a jump to the very next line, two additions of constants in a row. Each fix saves one instruction, and there are a lot of them.

practical

The reason to know this exists is diagnostic. If a disassembly is full of self-moves or of jumps to the following instruction, you are looking at unoptimized output or at a backend whose peephole did not run. If a hot loop reloads a value it stored two instructions earlier, that is spill code the peephole could not remove because it could not prove the memory does not alias — and the fix is upstream, in reducing pressure, not in the peephole.

advanced

The genuinely interesting property of peephole optimization is epistemic: it is the only part of a compiler where the transformations are small enough to be verified exhaustively. Alive2 checks LLVM's InstCombine rules against an SMT model of LLVM IR including poison and undef, and has found rules that were wrong for years. Souper goes further and *synthesises* rules by superoptimizing common sequences. The direction of travel is that a peephole table should be generated and proved rather than written and reviewed — and the reason that works here and not for, say, loop transformation is precisely the locality that also limits what a peephole can do. The constraint and the guarantee are the same property.

How much this depends on

Nothing in this domain is true of every compiler. These say how much.

targetEvery rule in this lesson is x86-64 specific, and specifically about which instructions write the condition flags. On AArch64 the flag-writing variants are separate mnemonics (add versus adds), so several of these rules are unnecessary there and others take a different form. On RISC-V there are no condition flags at all, which removes the entire class of precondition.

implementationThat a self-move costs nothing at run time on a modern x86 core is true of implementations that eliminate register-to-register moves at rename, which mainstream Intel and AMD cores have done for roughly a decade. It was not true on older cores, it is not true of every move form even now, and it is never true of the decode bandwidth and cache space the instruction occupies.

simplifiedOur peephole is a regular expression over emitted text with exactly one rule and no liveness information. That is honest for the rule it implements — a self-move needs no precondition — and would be unsound for any other rule in the catalogue above. A production peephole runs over machine instructions with a liveness side-table, not over strings.

If you were asked this in an interview

Give a peephole rewrite that is legal only when the condition flags are dead afterwards, and say how the pass would know.
Why does a compiler emit an instruction that another pass will immediately delete, instead of not emitting it?
Why are peephole rules the part of a compiler most amenable to formal verification?

Connections

Computer Architectureinstruction-decode register-renaming instruction-cache

Securityfuzzing