When you proofread an essay, you do not re-plan the whole argument. You run your eyes along a few words at a time and fix small things: "the the" becomes "the", "in order to" becomes "to", a sentence that says nothing gets deleted. Each fix is tiny and local, but after a full read the essay is noticeably tighter.
Peephole optimization is the compiler's proofreading pass. The code generator translates each piece of intermediate code on its own, so where two pieces meet it often leaves silly sequences: a value stored to memory and immediately loaded back, a jump to the very next line, a jump to another jump. A peephole optimizer slides a small window over the target code and replaces such patterns with something shorter or faster.
Peephole optimization is a technique that examines a short sequence of consecutive instructions (the peephole, or window) and replaces it with a shorter or faster sequence that has the same effect, whenever it matches a known pattern. The window then slides on, and passes are repeated until no more improvements are found.
In this chapter we will go through the classic peephole transformations, run a small peephole optimizer on an example and verify the result, look at what real GCC output reveals (including a surprising detail about dividing negative numbers by 2), and solve exam-style problems. The optimizer, the simulator used to check it, and the C test program are all small programs we actually ran.
Why a Separate, Local Pass?
The optimizations in Code Optimization Techniques and Data-Flow Analysis work on intermediate code and look at whole functions. Peephole optimization is different in three ways:
It is local. It looks only at a few adjacent instructions, typically 2 to 4. It does not need flow graphs or data-flow equations, which makes it simple and fast.
It usually works on target code, after instruction selection, so it can use machine-specific tricks (special instructions, addressing modes). It can also be applied to intermediate code.
It cleans up after everyone else. Simple code generators and earlier passes leave predictable junk at the boundaries between translated statements. Peephole optimization removes it.
The window does not have to be a contiguous run in the final layout: some optimizers also look at the instruction a jump goes to, which is how jump-chain optimizations work.
A key property: each improvement can create new opportunities. Deleting one instruction may bring two others next to each other that now match a pattern. So the optimizer makes repeated passes until a pass changes nothing.
The Target Notation
We use a simple register machine, written in the load/store style common in compiler textbooks:
Instruction | Meaning |
|---|---|
| Load memory location x into register R1 |
| Store register R1 into memory location x |
| R1 = R2 + R3 (similarly SUB, MUL); |
| R1 = R2 shifted left by k bits (= R2 × 2k) |
| Unconditional jump to label L |
| Jump to L if R1 < 0 (similarly BGTZ for > 0) |
1. Redundant Load and Store Elimination
The most common pattern by far. The code generator translates a = b + c and then d = a + e separately, so the first ends by storing a and the second starts by loading a:
ST a, R0 // end of "a = b + c"
LD R0, a // start of "d = a + e": R0 already holds a!The load can be deleted: R0 already contains exactly the value of a. Similarly:
Pattern | Replacement | Why it is safe |
|---|---|---|
|
| The load would put back the value that is already in R0 |
|
| The store would write back the value a already has |
|
| The second load changes nothing |
Important condition: the second instruction must not have a label. If some jump lands on LD R0, a, then on that path R0 may hold something else, and the load is needed. In other words, both instructions must be in the same basic block. (Also, if a is a volatile variable such as a hardware register, every access is meaningful and none may be removed.)
Real compilers at -O0 produce exactly this pattern. Here is GCC 15.2 output (x86-64, Intel syntax) for int mins = hours * 60; return mins * 60; with optimization off:
imul eax, eax, 60
mov DWORD PTR -4[rbp], eax // store mins
mov eax, DWORD PTR -4[rbp] // load mins straight back into the same register
imul eax, eax, 60The third line is a textbook redundant load.
2. Unreachable Code Elimination
An instruction that immediately follows an unconditional jump (or a return) and has no label can never be executed: nothing falls into it and nothing jumps to it. Delete it, and keep deleting until you reach a label.
BR L2
LD R1, y // unreachable: no label, after an unconditional jump
ADD R1, R1, #1 // unreachable
L2: ...A typical source is debugging code controlled by a constant:
#define DEBUG 0
...
if (DEBUG) { print debugging info }
Intermediate code After constant propagation After peephole
if DEBUG == 1 goto L1 if 0 == 1 goto L1 goto L2
goto L2 goto L2 (print code and
L1: print debugging info L1: print debugging info L1 removed)
L2: ... L2: ... L2: ...0 == 1 is always false, so the conditional jump is deleted; then the print code follows an unconditional jump and nothing jumps to L1 any more, so it is unreachable; finally goto L2 jumps to the very next instruction and is removed too (see the next section).
3. Flow-of-Control Optimizations
Code generators for if, while and break often produce jumps to jumps. These can be short-circuited:
Pattern | Replacement | Name |
|---|---|---|
|
| Jump to jump |
|
| Conditional jump to jump |
|
| Jump to conditional jump (valid when L1's code is reached only by this goto) |
| (delete the goto) | Jump to next instruction |
After the first rewrite, if no other jump uses L1, the instruction L1: goto L2 may become unreachable (if it follows an unconditional jump) and can be deleted. The saving: one fewer jump executed every time that path is taken, and sometimes one fewer instruction in the program.
Why does the third pattern need care? It replaces one jump by a conditional jump plus a jump, so the code is the same length, but on the path through it we execute one jump fewer when the condition is true. It is only a win if the original goto is executed often, and it is only valid as written if nothing else jumps to L1 (otherwise L1 must stay).
4. Algebraic Simplification
Instructions that do nothing can be deleted:
ADD R1, R1, #0 // x = x + 0 → delete
SUB R1, R1, #0 // x = x - 0 → delete
MUL R1, R1, #1 // x = x * 1 → deleteSuch instructions are rarely written by programmers, but they appear after macro expansion, inlining, or constant propagation (for example, i = i + OFFSET where OFFSET turns out to be 0). Constant folding can also be done inside the window: LD R1, #3 followed by ADD R1, R1, #4 becomes LD R1, #7, provided the ADD has no label (no other path can reach it with a different R1).
5. Strength Reduction and Machine Idioms
Replace an expensive instruction by a cheaper one that has the same effect, and use special instructions the target machine provides:
Instead of | Use | Condition |
|---|---|---|
MUL R1, R2, #8 | SHL R1, R2, #3 | Integer, multiply by power of 2 |
MUL R1, R2, #2 | ADD R1, R2, R2 | Integer |
x = x + 1 | INC x (on machines that have it) | Machine idiom |
Separate add and load for | Auto-increment addressing mode | Machine idiom (e.g. ARM post-indexed load) |
MOV R1, #0 | XOR R1, R1, R1 | On x86 the XOR form is shorter |
Real GCC at -O2 shows these idioms. For int scale(int x) { return x * 8; } it produced:
lea eax, 0[0+rdi*8] // "load effective address" used as a cheap multiply by 8
retx86's address-calculation hardware can compute base + index * scale with scale 1, 2, 4 or 8, so the compiler borrows it for arithmetic. That is a machine idiom no generic optimizer would know.
A trap: dividing a signed number by 2
It is tempting to replace x / 2 by a right shift x >> 1. For unsigned numbers that is exactly right, and GCC compiles unsigned uhalf(unsigned x) { return x / 2; } to just mov eax, edi followed by a single shr eax (shift right by 1). But for signed int, GCC produced:
half: // int half(int x) { return x / 2; }
mov eax, edi
shr eax, 31 // eax = sign bit of x (1 if x is negative, else 0)
add eax, edi // add 1 to negative numbers
sar eax // arithmetic shift right by 1
retWhy the extra work? C's division rounds toward zero, but an arithmetic right shift rounds down (toward minus infinity). For negative odd numbers these differ. We ran this C test:
x = -3 x / 2 = -1 x >> 1 = -2
x = -1 x / 2 = 0 x >> 1 = -1
x = 7 x / 2 = 3 x >> 1 = 3
mismatches with corrected shift: 0The last line comes from checking (x + sign_bit(x)) >> 1 against x / 2 for over half a million values spread across the whole int range: no mismatch. The lesson: a peephole rule must be exactly right for every input of the type, not just for the "usual" ones. (Also note that in C, right-shifting a negative signed number is implementation-defined; GCC defines it as an arithmetic shift.)
Worked Example: Running a Peephole Optimizer
Here is a piece of target code that a naive code generator might produce. We implemented the patterns above as rules in a small Python program and let it repeat until nothing changed.
LD R1, x
ADD R1, R1, #0
ST x, R1
LD R1, x
MUL R2, R1, #8
BLTZ R2, L1
BR L2
L1: BR L3
ST y, R2
L2: ST z, R2
L3: ST w, R2The optimizer applied these rewrites, in this order:
# | Rule | Change |
|---|---|---|
1 | Algebraic simplification | Delete |
2 | Redundant store | Now |
3 | Redundant (duplicate) load | Now two |
4 | Strength reduction |
|
5 | Conditional jump to jump |
|
6 | Unused label | Nothing jumps to L1 any more: delete the label |
7 | Unreachable code |
|
8 | Unreachable code |
|
9 | Jump to next instruction |
|
10 | Unused label | Nothing jumps to L2 any more: delete the label |
Result:
LD R1, x
SHL R2, R1, #3
BLTZ R2, L3
ST z, R2
L3: ST w, R2Eleven instructions became five. Notice how the changes cascade: rule 1 made rule 2 possible, rule 2 made rule 3 possible, rule 5 made rules 6 to 10 possible. No single pass over the original code would have found all of them.
Was it correct? We ran both versions in a simulator with x = -5, -1, 0, 1, 7. The final memory (x, y, z, w) was identical in every case, and the number of instructions executed dropped from 8 to 4 (negative x) and from 9 to 5 (other x). Note that ST y, R2 was never executed even in the original: it sat after BR L3, so it was dead from the start.
How Peephole Optimizers Are Built
Pattern tables. Each rule is a pattern (with variables for registers, addresses, constants) and a replacement, plus conditions such as "no label on the second instruction". The optimizer tries every rule at every position.
Repeat until no change. If every rule makes the code strictly shorter or cheaper, this always terminates. Rules that do not shrink the code, such as retargeting a jump, need a guard: following a cycle of jumps like
L1: goto L2,L2: goto L1must stop instead of looping forever.Hand-written or generated. Some compilers generate peephole rules automatically from a machine description, or even by searching for the shortest equivalent sequences ("superoptimization").
Placement. Peephole passes are often run more than once: on intermediate code, after instruction selection, and after register allocation (which can introduce new redundant moves).
Point | Peephole optimization | Global (data-flow based) optimization |
|---|---|---|
Scope | A few adjacent instructions | A whole function |
Works on | Usually target code | Usually intermediate code |
Needs analysis? | Pattern matching only | Flow graph, data-flow analysis |
Machine-specific? | Often yes (idioms, addressing modes) | Usually no |
Cost | Very cheap, linear passes | More expensive |
Typical wins | Redundant loads/stores, jump chains, idioms | Global CSE, code motion, induction variables |
Solved Problems
Problem 1: Which loads can go?
1: ST a, R0
2: LD R0, a
3: ADD R0, R0, R1
4: L5: LD R0, a
5: ST b, R0Which instructions can a peephole optimizer delete?
Solution. Instruction 2 can be deleted: it reloads into R0 the value that instruction 1 just stored from R0, and it has no label. Instruction 4 cannot be deleted. First, R0 was changed by instruction 3, so it no longer holds a. Second, it has the label L5, so control may arrive there from elsewhere.
Problem 2: Jump chains
if x > 0 goto L1
...
L1: goto L2
...
L2: goto L3
...
L3: y = 1Rewrite the conditional jump using flow-of-control optimization.
Solution. Follow the chain: L1 holds goto L2, L2 holds goto L3. So the first instruction becomes if x > 0 goto L3. If no other jumps target L1 or L2, and the instructions before them are unconditional jumps, the two goto instructions become unreachable and are deleted.
Problem 3: Is this rule correct?
A student proposes the peephole rule "DIV R1, R1, #4 → SAR R1, R1, #2" (arithmetic shift right) for signed integers. Is it correct?
Solution. No. For x = -5, signed division rounding toward zero gives -1, but -5 shifted right by 2 gives -2 (rounded down). The rule is correct only for unsigned values, or for signed values known to be non-negative. A correct signed version adds 3 (that is, 22 - 1) to negative values before shifting.
Problem 4: Name the optimization
Before | After | Optimization |
|---|---|---|
| (goto removed) | Redundant jump / jump to next instruction |
| (removed) | Algebraic simplification |
|
| Strength reduction |
|
| Use of machine idioms |
Code after | (removed) | Unreachable code elimination |
Common Mistakes
Deleting a labelled instruction. A label means control can arrive from somewhere else, so the "previous instruction" assumption fails.
Treating a conditional jump like an unconditional one. Code after
if ... goto Lis reachable (the fall-through path); only code after an unconditional jump or return without a label is unreachable.Running only one pass. One change often enables another; repeat until nothing changes.
Using a shift for signed division. Shifts round down; C division rounds toward zero.
Removing accesses to volatile memory. A load from a hardware status register is not redundant even if it looks identical to the previous one.
Thinking peephole optimization is only for target code. The same idea works on intermediate code too.
Interview and Exam Questions
What is a peephole?
A small, sliding window of consecutive instructions (often 2 to 4) that the optimizer examines for patterns it can replace with shorter or faster equivalents.
List the common peephole optimizations.
Redundant load/store elimination, unreachable code elimination, flow-of-control optimizations (jump to jump, jump to next instruction), algebraic simplification, strength reduction, and use of machine idioms.
Why must the second instruction in "ST a, R0; LD R0, a" have no label to be deleted?
With a label, control can jump straight to the load from another place where R0 may not hold a. Both instructions must be in the same basic block.
Is peephole optimization machine dependent?
Mostly yes: it usually runs on target code and uses target-specific idioms and addressing modes. Some rules (jump chains, algebraic identities) are general and can run on intermediate code too.
Why are multiple passes needed?
A rewrite may bring together instructions that now match another pattern, as in our example where deleting a no-op add exposed a redundant store and then a duplicate load.
Why does GCC not compile signed x / 2 as a single shift?
An arithmetic shift rounds toward minus infinity, while C integer division rounds toward zero, so they differ for negative odd x. GCC adds the sign bit before shifting to correct the rounding.
What is a machine idiom? Give an example.
A special target instruction or addressing mode that does a common job cheaply, such as INC for x = x + 1, auto-increment addressing for walking arrays, or x86's lea used for multiply-and-add.
Summary
Peephole optimization slides a small window over (usually target) code and replaces patterns with shorter or faster equivalents.
Classic transformations: redundant load/store elimination, unreachable code elimination, flow-of-control optimizations (jump chains, jump to next), algebraic simplification, strength reduction and machine idioms.
Instructions with labels are boundaries: patterns must not span them.
Improvements cascade, so passes are repeated until no change. In our example 11 instructions became 5, verified by simulation.
Every rule must be exactly right for all values of the type: signed division by a power of two needs a sign correction, as real GCC output shows.
Peephole optimization is cheap, simple and effective, and is often run several times in a compiler. The next chapter, Code Generation & Register Allocation, covers the phase whose output it cleans up.