Chapter 32 of 33

Peephole Optimization

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

LD R1, x

Load memory location x into register R1

ST x, R1

Store register R1 into memory location x

ADD R1, R2, R3

R1 = R2 + R3 (similarly SUB, MUL); #c means the constant c

SHL R1, R2, #k

R1 = R2 shifted left by k bits (= R2 × 2k)

BR L

Unconditional jump to label L

BLTZ R1, 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

ST a, R0
LD R0, a

ST a, R0

The load would put back the value that is already in R0

LD R0, a
ST a, R0

LD R0, a

The store would write back the value a already has

LD R0, a
LD R0, a

LD R0, a

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, 60

The 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

goto L1 ... L1: goto L2

goto L2 ... L1: goto L2

Jump to jump

if a < b goto L1 ... L1: goto L2

if a < b goto L2 ... L1: goto L2

Conditional jump to jump

goto L1 ... L1: if a < b goto L2 L3:

if a < b goto L2 goto L3 ...

Jump to conditional jump (valid when L1's code is reached only by this goto)

goto L1 immediately followed by L1:

(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      →  delete

Such 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 *p then p = p + 4

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
ret

x86'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
    ret

Why 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: 0

The 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, R2

The optimizer applied these rewrites, in this order:

#

Rule

Change

1

Algebraic simplification

Delete ADD R1, R1, #0

2

Redundant store

Now LD R1, x is followed by ST x, R1: delete the store

3

Redundant (duplicate) load

Now two LD R1, x are adjacent: delete the second

4

Strength reduction

MUL R2, R1, #8 → SHL R2, R1, #3

5

Conditional jump to jump

BLTZ R2, L1 → BLTZ R2, L3, since L1 holds just BR L3

6

Unused label

Nothing jumps to L1 any more: delete the label

7

Unreachable code

BR L3 now directly follows BR L2 without a label: delete it

8

Unreachable code

ST y, R2 also follows BR L2 without a label: delete it

9

Jump to next instruction

BR L2 is now immediately followed by L2:: delete it

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, R2

Eleven 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 L1 must 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, R0

Which 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 = 1

Rewrite 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 L7 followed by L7:

(goto removed)

Redundant jump / jump to next instruction

MUL R1, R1, #1

(removed)

Algebraic simplification

MUL R2, R3, #16

SHL R2, R3, #4

Strength reduction

x = x + 1 as load/add/store

INC x

Use of machine idioms

Code after return with no label

(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 L is 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.