Peephole optimization - Misplaced Pages

(Redirected from Peephole optimizations) Compiler optimization technique

Peephole optimization is an optimization technique performed on a small set of compiler-generated instructions, known as a peephole or window, that involves replacing the instructions with a logically equivalent set that has better performance.

For example:

Instead of pushing a register onto the stack and then immediately popping the value back into the register, remove both instructions
Instead of multiplying x by 2, do x + x
Instead of multiplying a floating point register by 8, add 3 to the floating point register's exponent

The term peephole optimization was introduced by William Marshall McKeeman in 1965.

Replacements

Peephole optimization replacements include but are not limited to:

Null sequences – Delete useless operations
Combine operations – Replace several operations with one equivalent
Algebraic laws – Use algebraic laws to simplify or reorder instructions
Special case instructions – Use instructions designed for special operand cases
Address mode operations – Use address modes to simplify code

Implementation

Modern compilers often implement peephole optimizations with a pattern matching algorithm.

Examples

This section does not cite any sources. Please help improve this section by adding citations to reliable sources. Unsourced material may be challenged and removed. (March 2013) (Learn how and when to remove this message)

Replacing slow instructions with faster ones

The following Java bytecode:

aload 1
aload 1
mul

can be replaced with the following which executes faster:

aload 1
dup
mul

As for most peephole optimizations, this is based on the relative efficiency of different instructions. In this case, dup (which duplicates and pushes the top of the stack) is known/assumed to be more efficient than aload (which loads a local variable and pushes it onto the stack).

Removing redundant code

The following source code:

 a = b + c;
 d = a + e;

is straightforwardly compiled to:

MOV b, R0  ; Copy b to the register
ADD c, R0  ; Add  c to the register, the register is now b+c
MOV R0, a  ; Copy the register to a
MOV a, R0  ; Copy a to the register
ADD e, R0  ; Add  e to the register, the register is now a+e 
MOV R0, d  ; Copy the register to d

but can be optimized to:

MOV b, R0  ; Copy b to the register
ADD c, R0  ; Add c to the register, which is now b+c (a)
MOV R0, a  ; Copy the register to a
ADD e, R0  ; Add e to the register, which is now b+c+e 
MOV R0, d  ; Copy the register to d

Removing redundant stack instructions

If the compiler saves registers on the stack before calling a subroutine and restores them when returning, consecutive calls to subroutines may have redundant stack instructions.

Suppose the compiler generates the following Z80 instructions for each procedure call:

 PUSH AF
 PUSH BC
 PUSH DE
 PUSH HL
 CALL _ADDR
 POP HL
 POP DE
 POP BC
 POP AF

If there were two consecutive subroutine calls, they would look like this:

 PUSH AF
 PUSH BC
 PUSH DE
 PUSH HL
 CALL _ADDR1
 POP HL
 POP DE
 POP BC
 POP AF
 PUSH AF
 PUSH BC
 PUSH DE
 PUSH HL
 CALL _ADDR2
 POP HL
 POP DE
 POP BC
 POP AF

The sequence POP regs followed by PUSH for the same registers is generally redundant. In cases where it is redundant, a peephole optimization would remove these instructions. In the example, this would cause another redundant POP/PUSH pair to appear in the peephole, and these would be removed in turn. Assuming that subroutine _ADDR2 does not depend on previous register values, removing all of the redundant code in the example above would eventually leave the following code:

 PUSH AF
 PUSH BC
 PUSH DE
 PUSH HL
 CALL _ADDR1
 CALL _ADDR2
 POP HL
 POP DE
 POP BC
 POP AF

References

Muchnick, Steven Stanley (1997-08-15). Advanced Compiler Design and Implementation. Academic Press / Morgan Kaufmann. ISBN 978-1-55860-320-2.
Grune, Dick; Bal, Henri; Jakobs, Ceriel; Langendoen, Koen (2012-07-20). Modern Compiler Design (2 ed.). Wiley / John Wiley & Sons, Ltd. ISBN 978-0-471-97697-4.
McKeeman, William Marshall (July 1965). "Peephole optimization". Communications of the ACM. 8 (7): 443–444. doi:10.1145/364995.365000. S2CID 9529633.
Fischer, Charles N.; Cytron, Ron K.; LeBlanc, Jr., Richard J. (2010). Crafting a Compiler (PDF). Addison-Wesley. ISBN 978-0-13-606705-4. Archived from the original (PDF) on 2018-07-03. Retrieved 2018-07-02.
Aho, Alfred Vaino; Lam, Monica Sin-Ling; Sethi, Ravi; Ullman, Jeffrey David (2007). "Chapter 8.9.2 Code Generation by Tiling an Input Tree". Compilers – Principles, Techniques, & Tools (PDF) (2 ed.). Pearson Education. p. 540. Archived (PDF) from the original on 2018-06-10. Retrieved 2018-07-02.

External links

The dictionary definition of peephole optimization at Wiktionary

v t e Compiler optimizations
Basic block	Peephole optimization Local value numbering
Loop	Automatic parallelization Automatic vectorization Induction variable Loop fusion Loop-invariant code motion Loop inversion Loop interchange Loop nest optimization Loop splitting Loop unrolling Loop unswitching Software pipelining Strength reduction
Data-flow analysis	Available expression Common subexpression elimination Constant folding Dead store elimination Induction variable recognition and elimination Live-variable analysis Upwards exposed uses Use-define chain Reaching definitions
SSA-based	Global value numbering Sparse conditional constant propagation
Code generation	Instruction scheduling Instruction selection Register allocation Rematerialization
Functional	Deforestation Tail-call elimination
Global	Interprocedural optimization
Other	Bounds-checking elimination Compile-time function execution Dead-code elimination Expression templates Inline expansion Jump threading Partial evaluation Profile-guided optimization
Static analysis	Alias analysis Array-access analysis Control-flow analysis Data-flow analysis Dependence analysis Escape analysis Pointer analysis Shape analysis Value range analysis

Category:

Compiler optimizations