# Peephole optimization

> Mediated Wiki article. Canonical URL: https://mediated.wiki/source/Peephole_optimization
> Markdown URL: https://mediated.wiki/source/Peephole_optimization.md
> Source: https://en.wikipedia.org/wiki/Peephole_optimization
> Source revision: 1329643837
> License: Creative Commons Attribution-ShareAlike 4.0 International (https://creativecommons.org/licenses/by-sa/4.0/)

{{Short description|Compiler optimization technique}}
{{Use dmy dates|date=January 2020|cs1-dates=y}}
'''Peephole optimization''' is an [optimization technique](/source/Optimizing_compiler) performed on a small set of [compiler](/source/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](/source/pattern-matching) [algorithm](/source/algorithm).<ref name="Aho_2007"/>

==Examples==
{{unreferenced section|date=March 2013}}

===Replacing slow instructions with faster ones===
The following [Java bytecode](/source/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](/source/stack_(data_structure))) is known/assumed to be more efficient than <code>aload</code> (which loads a local [variable](/source/Variable_(programming)) and pushes it onto the stack).

===Removing redundant code===
The following [source code](/source/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](/source/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](/source/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 optimizer](/source/Object_code_optimizer)s, discussion in relation to general [algorithmic efficiency](/source/algorithmic_efficiency)
* [Capex Corporation](/source/Capex_Corporation) – produced the [COBOL](/source/COBOL) [optimizer](/source/program_optimization), an early mainframe [object code optimizer](/source/object_code_optimizer) for [IBM](/source/IBM) Cobol
* [Superoptimization](/source/Superoptimization)
* [Digital Research XLT86](/source/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](/source/Wiley_(publisher)) / [John Wiley & Sons, Ltd](/source/John_Wiley_%26_Sons%2C_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](/source/Academic_Press) / [Morgan Kaufmann](/source/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](/source/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](/source/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](/source/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

---
Adapted from the Wikipedia article [Peephole optimization](https://en.wikipedia.org/wiki/Peephole_optimization) by Wikipedia contributors ([contributor history](https://en.wikipedia.org/wiki/Peephole_optimization?action=history)). Available under [Creative Commons Attribution-ShareAlike 4.0 International](https://creativecommons.org/licenses/by-sa/4.0/). Changes may have been made.