Peephole Optimisation
A three-instruction window and a handful of patterns turn seven instructions into four.
Skip to the animationPeephole optimisation slides a window of two or three instructions over the generated code and replaces recognised patterns with cheaper equivalents, repeating until nothing changes.
Why there is anything to remove
Code generation translates each construct independently and never looks at neighbours. The output is correct and locally silly: a value loaded then immediately stored back, arithmetic with no effect, a jump to the next instruction, code after an unconditional branch.
Cleaning this up needs no analysis at all — just pattern matching over a tiny window, which is what makes the technique nearly free.
The standard rules
| Rule | Pattern | Becomes |
|---|---|---|
| Redundant load-store | MOV x,y ; MOV y,x | MOV x,y |
| Algebraic identity | ADD x,0 · MUL x,1 | delete |
| Strength reduction | MUL x,2 | SHL x,1 |
| Unreachable code | GOTO L ; ⟨no label⟩ | delete the instruction |
| Jump to next | GOTO L ; L: | delete the jump |
| Jump chaining | GOTO L1 where L1: GOTO L2 | GOTO L2 |
Each rule carries a safety condition. Deleting a redundant store is only valid if nothing jumps to it — a label there means control can arrive without having run the first instruction.
Run it to a fixed point
One rewrite frequently exposes another: deleting unreachable code can bring a jump next to its own target, which the jump-to-next rule then removes. So the optimiser repeats until a full pass changes nothing.
Why do these silly patterns appear at all? Array indexing and address arithmetic emit general formulas that turn into +0 and *1 by the hundred. Translating if and loop constructs independently produces jumps to the very next instruction constantly. The code generator could avoid some of it by special-casing, but that would complicate it enormously — it is cheaper to emit the obvious thing and clean up afterwards.
Local by design
The window sees a few instructions and nothing else. It cannot know whether a value is used later, whether a loop executes at all, or whether two distant expressions compute the same thing. Those questions need global dataflow analysis over the flow graph.
Peephole optimisation survives alongside all of that for three reasons: it is nearly free, it runs last on real target instructions rather than on intermediate code, and it reliably tidies the mess every earlier phase leaves behind — including the mess left by other optimisations.
Advantages and disadvantages
Advantages
- Trivial to implement — each rule is a couple of lines of pattern matching.
- Very cheap, with a fixed-size window regardless of program size.
- Runs on actual target instructions, so it catches waste no earlier phase could see.
Disadvantages
- Purely local; cannot perform any optimisation requiring wider context.
- Rules are machine specific, so the set must be rewritten per target.
- Every rule needs a safety condition, and a wrong one silently miscompiles.
Watch it work
Check yourself
question 1 / 4
One question at a time. Pick an answer to see why it is right or wrong, then move on — there is no score to keep and nothing is saved.