{{Short description|Compiler optimization technique}} {{Use dmy dates|date=January 2020|cs1-dates=y}} '''Peephole optimization''' is an optimization technique performed on a small set of compiler-generated instructions, known as a peephole or window,<ref name="Muchnick_1997"/><ref name="Grune_2012"/> 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 {{code|x << 1}}. * 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.<ref name="McKeeman_1965"/>
==Replacements== Peephole optimization replacements include but are not limited to:<ref name="Fischer_2010"/> * 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.<ref name="Aho_2007"/>
==Examples== {{unreferenced section|date=March 2013}}
===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, <code>dup</code> (which duplicates and pushes the top of the stack) is known/assumed to be more efficient than <code>aload</code> (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 <syntaxhighlight lang="nasm"> 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 [(b+c)+e] MOV R0, d ; Copy the register to d </syntaxhighlight> but can be optimized to <syntaxhighlight lang="nasm"> 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 [(a)+e] MOV R0, d ; Copy the register to d </syntaxhighlight>
===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: <syntaxhighlight lang="asm"> PUSH AF PUSH BC PUSH DE PUSH HL CALL _ADDR POP HL POP DE POP BC POP AF </syntaxhighlight>
If there were two consecutive subroutine calls, they would look like this: <syntaxhighlight lang="asm"> 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 </syntaxhighlight>
The sequence <code>POP regs</code> followed by <code>PUSH</code> 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 <code>POP</code>/<code>PUSH</code> pair to appear in the peephole, and these would be removed in turn. Assuming that subroutine <code>_ADDR2</code> does not depend on previous register values, removing all of the redundant code in the example above would eventually leave the following code: <syntaxhighlight lang="asm"> PUSH AF PUSH BC PUSH DE PUSH HL CALL _ADDR1 CALL _ADDR2 POP HL POP DE POP BC POP AF </syntaxhighlight>
==See also== * Object code optimizers, discussion in relation to general algorithmic efficiency * Capex Corporation – produced the COBOL optimizer, an early mainframe object code optimizer for IBM Cobol * Superoptimization * Digital Research XLT86, an optimizing assembly source-to-source compiler<!-- can be seen as a predecessor to peephole optimization, although not named as such in 1981 -->
==References== <references>
<ref name="Grune_2012">{{cite book |author-first1=Dick |author-last1=Grune |author-link1=Dick Grune |author-first2=Henri |author-last2=Bal |author-link2=Henri E. Bal |author-first3=Ceriel |author-last3=Jakobs |author-first4=Koen |author-last4=Langendoen |title=Modern Compiler Design |date=20 July 2012 |edition=2 |url=https://books.google.com/books?id=zkpFTBtK7a4C&q=peephole |publisher=Wiley / John Wiley & Sons, Ltd |isbn=978-0-471-97697-4}}</ref> <ref name="Muchnick_1997">{{cite book |author-first=Steven Stanley |author-last=Muchnick |author-link=Steven Stanley Muchnick |title=Advanced Compiler Design and Implementation |url=https://books.google.com/books?id=Pq7pHwG1_OkC&q=peephole |date=1997-08-15 |publisher=Academic Press / Morgan Kaufmann |isbn=978-1-55860-320-2}}</ref> <ref name="McKeeman_1965">{{cite journal |author-last=McKeeman |author-first=William Marshall |title=Peephole optimization |journal=Communications of the ACM |volume=8 |issue=7 |date=July 1965 |doi=10.1145/364995.365000 |pages=443–444|s2cid=9529633 |doi-access=free }}</ref> <ref name="Fischer_2010">{{cite book |author-last1=Fischer |author-first1=Charles N. |author-last2=Cytron |author-first2=Ron K. |author-last3=LeBlanc, Jr. |author-first3=Richard J. |title=Crafting a Compiler |date=2010 |publisher=Addison-Wesley |isbn=978-0-13-606705-4 |url=http://bank.engzenon.com/download/560e7301-482c-43fd-9f80-16a9c0feb99b/Crafting_a_Compiler_by_Fischer_Cytron_and_LeBlanc.pdf |access-date=2018-07-02 |archive-url=https://web.archive.org/web/20180703050525/http://bank.engzenon.com/download/560e7301-482c-43fd-9f80-16a9c0feb99b/Crafting_a_Compiler_by_Fischer_Cytron_and_LeBlanc.pdf |archive-date=3 July 2018 |url-status=dead }}</ref> <ref name="Aho_2007">{{cite book |author-last1=Aho |author-first1=Alfred Vaino |author-link1=Alfred Vaino Aho |author-last2=Lam |author-first2=Monica Sin-Ling |author-link2=Monica Sin-Ling Lam |author-last3=Sethi |author-first3=Ravi |author-link3=Ravi Sethi |author-last4=Ullman |author-first4=Jeffrey David |author-link4=Jeffrey David Ullman |title=Compilers – Principles, Techniques, & Tools |edition=2 |date=2007 |publisher=Pearson Education |page=540 |url=http://www.informatik.uni-bremen.de/agbkb/lehre/ccfl/Material/ALSUdragonbook.pdf |access-date=2018-07-02 |url-status=live |archive-url=https://web.archive.org/web/20180610190208/http://www.informatik.uni-bremen.de/agbkb/lehre/ccfl/Material/ALSUdragonbook.pdf |archive-date=2018-06-10 |chapter=Chapter 8.9.2 Code Generation by Tiling an Input Tree}}</ref>
</references>
==External links== * [https://web.archive.org/web/20210609022810/ftp://ftp.cs.princeton.edu/pub/lcc/contrib/copt.shar The copt general-purpose peephole optimizer by Christopher W. Fraser] * [http://portal.acm.org/citation.cfm?id=365000 The original paper] {{wti}}
{{Compiler optimizations}}
Category:Compiler optimizations