Peephole optimization
{{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, 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.
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
{{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, 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 [(b+c)+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 [(a)+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
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
References
{{reflist|refs=
{{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}}
{{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}}
{{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 }}
{{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 }}
{{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}}
}}
External links
- [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}}