THE PEEPHOLE tiny local rewrites through a sliding window
Slide a small window over the instruction stream and apply local rewrite rules: x*1→x, x+0→x, push then pop→nothing, two constants folded into one, a store immediately reloaded. Each rule is trivially correct on its own; together they clean up the dumb code that earlier passes and naive code generation leave behind. Peephole optimization is the humblest pass — no global analysis, just a window a few instructions wide — and one of the most cost-effective.
THE TECHNIQUE a sliding window of local, provably-safe rewrites
A short op stream carries some obviously-removable ops (multiply-by-1, add-0, a dead op). The peephole scans and counts what it can safely delete: live demo
HISTORY & CREDIT William McKeeman, 1965
“Real optimization needs the whole program.” — some of the best wins fit in a window three instructions wide. Peephole optimization proves that local, provably-safe rewrites, applied everywhere, remove a startling amount of waste for almost no analysis. cited
1965 · William M. McKeeman — “Peephole Optimization” (CACM): a small window of local pattern rewrites over generated code. 1979–84 · Davidson & Fraser — retargetable peephole optimizers; rules derived from a machine description. now · LLVM's InstCombine, GCC's combine pass — peephole at industrial scale.
Each rule is a tiny theorem: this pattern equals that shorter one, always. The pass is just the theorems, applied wherever they match. Correctness scales because locality does. McKeeman 1965
RECOMMEND FOR I-13 removable ops in a stream, computed
On the canonical compiler, a stream tagged with removable patterns (two multiply-by-1, one add-0, one dead op) yields 4 safe deletions:
$ i13 run peephole.i13 # count locally-removable ops
removed = 4 -- 2x (mul by 1), 1x (add 0), 1x dead op
Recommend: a peephole that removes provably-dead ops is the one optimizer pass that fits i13's grain — and it already happened once: the panel removed the dead Op::Attr opcode (constructed nowhere) from the IVM (18→17). That is peephole optimization on the instruction set itself. A rewrite that only ever deletes what can never run does not violate EXECUTION ≠ COMMIT — it removes non-execution — so a dead-op peephole is safe to adopt where CSE is not.