Peephole Optimization

The optimizer examines a small, sliding "peephole" window—typically a few consecutive instructions—within the generated assembly or intermediate code. It identifies specific, inefficient patterns and substitutes them with optimized sequences. This is a syntax-driven transformation based on predefined rewrite rules, not global program analysis.

Examples include:

• Replacing MUL R1, R2, 8 with SHL R1, R2, 3.
• Removing redundant loads/stores: LOAD R1, [addr] followed immediately by STORE R1, [addr].
• Simplifying ADD R1, R2, 0 to MOV R1, R2.

Peephole optimizations are highly target-dependent, exploiting the specific instruction set, latency, and cost model of the underlying hardware (e.g., CPU, NPU, GPU). The compiler's code generator or a separate post-pass applies these rules.

Key targets are:

• Strength Reduction: Substituting expensive operations (multiply, divide) with cheaper ones (shift, add).
• Instruction Selection: Choosing a single instruction that performs the work of multiple simpler ones (e.g., a fused multiply-add, FMA).
• Addressing Mode Optimization: Using more efficient memory addressing modes available on the target architecture.

This optimization is typically performed on a low-level intermediate representation (IR) or directly on the assembly code, after most high-level and machine-independent optimizations. It works on a linearized instruction stream where registers, memory addresses, and immediate values are explicit.

Common IRs include:

• LLVM's Machine IR (MIR)
• GCC's Register Transfer Language (RTL)
• Vendor-specific NPU/GPU assembly

Operating at this level allows the optimizer to make precise decisions about instruction scheduling, register pressure, and pipeline effects.

A core function is recognizing and folding common instruction idioms into more efficient forms. This goes beyond simple algebra to include sequences that represent higher-level operations.

Examples:

• Compare-and-Branch Sequences: Optimizing the instructions that set condition codes before a jump.
• Function Prologue/Epilogue: Streamlining stack frame setup and teardown sequences.
• Constant Propagation & Folding: Evaluating expressions with constants that appear in the instruction stream (e.g., folding ADD R1, 2, 3 into MOV R1, 5).

While peephole optimization works on linear instruction sequences, it is a foundational technique that enables higher-level optimizations like kernel fusion in NPU compilers. After a compiler fuses multiple tensor operations (e.g., Conv + Bias + ReLU) into a single kernel, peephole passes clean up the generated low-level code.

It optimizes the fused kernel by:

• Eliminating redundant register spills between originally separate operations.
• Optimizing the synchronization barriers or memory fences within the fused block.
• Applying strength reduction to the combined arithmetic operations.

The algorithm is typically a forward pass over the instruction list, using a finite-state machine or pattern matcher to identify rewrite opportunities within the peephole window.

Implementation Steps:

1. Slide a window (e.g., 2-5 instructions) over the instruction stream.
2. Match the window contents against a table of inefficient patterns.
3. Replace the matched sequence with a predefined efficient pattern.
4. Rescan the modified area, as a replacement may enable another optimization.

It is a fast, greedy algorithm with linear time complexity, making it suitable for final compilation stages.

Replaces expensive arithmetic operations with cheaper equivalents.

• Multiply by power of two: x * 8 → x << 3 (left shift).
• Divide by power of two: x / 4 → x >> 2 (arithmetic right shift for signed, logical for unsigned).
• Expensive constant multiplication: x * 9 → (x << 3) + x (using shifts and adds).
• Modulo by power of two: x % 16 → x & 15 (bitwise AND).

This directly reduces instruction latency and can improve instruction-level parallelism (ILP).

Evaluates constant expressions at compile time and propagates known values.

• Folding: int a = 5 * 10 + 2; → int a = 52;
• Propagation: After const int SIZE = 1024;, the compiler replaces subsequent uses of SIZE with the literal 1024. This enables further peephole opportunities, like turning i * SIZE into a shift if SIZE is a power of two.

This eliminates runtime computation and is a prerequisite for many other optimizations like dead code elimination.

Removes unnecessary memory operations by keeping values in registers.

• Sequence: store [x], R1 followed immediately by load R2, [x] → can be replaced with a register-to-register move move R2, R1 if no intervening code modifies memory location [x].
• Dead Store: A store to a location that is never read before being overwritten is eliminated.

This is critical for performance on architectures where memory accesses are orders of magnitude slower than register operations, directly impacting arithmetic intensity.

Optimizes jumps and branches to streamline execution paths.

• Unconditional Jump Chaining: jmp L1 ... L1: jmp L2 → jmp L2.
• Branch to Next: A conditional branch that targets the very next instruction is removed.
• Inverted Logic: A conditional branch over an unconditional jump (if (!cond) goto L1; goto L2;) can be inverted to a single branch (if (cond) goto L2;).

These reduce the number of instructions fetched and improve the effectiveness of the CPU's branch prediction unit.

Merges multiple simple instructions into a single, more powerful one.

• Increment/Decrement: t = i; i = i + 1; → single INC instruction (if the original value of i in t is no longer needed).
• Test and Set/Clear: A sequence that tests a condition and sets a flag or register can often be replaced with a single compare-and-set instruction.
• Addressing Modes: On CISC architectures (like x86), sequences like MOV R1, [BASE] followed by ADD R1, OFFSET can be combined into MOV R1, [BASE+OFFSET].

This reduces instruction count and decode pressure.

Recognizes common, suboptimal code sequences and replaces them with optimal hardware-specific instructions.

• Zeroing a Register: XOR EAX, EAX is smaller and faster than MOV EAX, 0 on x86.
• Min/Max Operations: A sequence of compare and conditional moves can be replaced with a dedicated MIN or MAX instruction if available on the target ISA.
• Memory Barrier Sequences: Replaces a software sequence for synchronization with a single hardware memory fence instruction (e.g., MFENCE).

This leverages the full capability of the target intermediate representation (IR) and final instruction set.

A compiler optimization that identifies and eliminates redundant computations of identical expressions. It replaces repeated calculations with a single computed value stored in a temporary variable, reducing computational overhead.

• Example: Replacing y = (a + b) * c; z = (a + b) * d; with temp = a + b; y = temp * c; z = temp * d;.
• Scope: Works on a basic block or control flow graph, analyzing a larger region than a peephole.
• Interaction: CSE creates opportunities for peephole optimization by introducing temporary variables that may be further simplified.

A two-stage optimization. Constant propagation replaces variables known to have constant values with those literals. Constant folding evaluates constant expressions at compile time.

• Example: For const int x = 5; int y = x * 2 + 3;, propagation sets x to 5, and folding computes y = 13.
• Foundation for Peephole: Creates the constant values and simplified expressions that peephole patterns (e.g., strength reduction) can then match and replace with more efficient instructions.

Removes code that does not affect the program's observable output. This includes unreachable statements and computations whose results are never used.

• Types: Unreachable code (after a return) and dead stores (writing to a variable never read).
• Synergy with Peephole: Peephole optimizations can create dead code (e.g., simplifying x = x + 0 might leave an unused mov instruction). A robust compiler pipeline applies DCE after peephole passes to clean up these artifacts.

The compiler reorders machine instructions within a basic block to hide pipeline latencies, avoid hardware hazards, and improve instruction-level parallelism (ILP).

• Goal: Minimize pipeline stalls by ensuring operands are ready and functional units are utilized.
• Contrast with Peephole: Scheduling reorders existing instructions. Peephole replaces instruction sequences. They are complementary: peephole simplifies the sequence, then scheduling orders it optimally for the target microarchitecture.

The process of mapping an unlimited number of program variables (virtual registers) to a finite set of physical hardware registers.

• Key Challenge: Avoiding register spilling, where values are moved to slower memory.
• Interaction with Peephole: Peephole optimizations that reduce the number of instructions (e.g., using a lea for address calculation) can reduce register pressure and live ranges, simplifying the allocator's task. Conversely, poor allocation can introduce spill code that peephole may later optimize.

The final compiler phase that translates the optimized intermediate representation (IR) into target-specific machine code or assembly.

• Peephole's Role: Often implemented as a last-mile optimization pass directly on the assembly or machine code stream, just before binary emission. This allows it to exploit exact, target-specific instruction latencies, addressing modes, and quirks that are not visible at higher IR levels.
• Target-Specific: The pattern database for peephole optimization is unique to each CPU architecture (x86, ARM, RISC-V).