Peephole optimization

Peephole optimization

In compiler theory, peephole optimization is a kind of optimization performed over a very small set of instructions in a segment of generated code. The set is called a "peephole" or a "window". It works by recognising sets of instructions that don't actually do anything, or that can be replaced by a leaner set of instructions.

Replacement Rules [Crafting a Compiler with C++, Fischer/LeBlanc]

* Constant Folding: Evaluate constant subexpressions in advance.
* Strength Reduction: Replace slow operations with faster equivalents.
* 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.

Of course there can be other types of peephole optimizations involving simplifying the target machine instructions, assuming that the target machine is known in advance. Advantages of a given architecture and instruction sets can be exploited in this case.

Example

The following Java assembler code

... aload 1 aload 1 mul ...

can be replaced by

... aload 1 dup mul ...

This kind of optimization, like most peephole optimizations, makes certain assumptions about the efficiency of instructions. For instance, in this case, it is assumed that the dup operation (which duplicates and pushes the top of the stack) is more efficient than the aload X operation (which loads a local variable identified as X and pushes it on the stack).

Another example is to eliminate redundant load stores. a = b + c; d = a + e;is straightforwardly implemented as

MOV b, R0 # Copy b to the registerADD c, R0 # Add c to the register, the register is now b+cMOV R0, a # Copy the register to aMOV a, R0 # Copy a to the registerADD 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 optimised 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 aADD e, R0 # Add e to the register, which is now b+c+e [(a)+e] MOV R0, d # Copy the register to d
Furthermore, if the compiler knew that the variable a was not used again, the middle operation could be omitted.

Implementation

Modern architectures typically allow for many hundreds of different kinds of peephole optimizations, and it is therefore often appropriate for compiler programmers to implement them using a pattern matching algorithm. Fact|date=July 2008

References

External links

* [ftp://ftp.cs.princeton.edu/pub/lcc/contrib/copt.shar The copt general-purpose peephole optimizer by Christopher W. Fraser]
* [http://oarizo.com/downloads/misc/copt2.zip Source code for Vaughn Cato's peephole optimizer]
* [http://portal.acm.org/citation.cfm?id=365000 The original paper]


Wikimedia Foundation. 2010.

Игры ⚽ Поможем написать курсовую

Look at other dictionaries:

  • peephole optimization — noun An optimization that works by eliminating redundant instructions from a small area of code. The loop was more than twice as fast after I had applied peephole optimization …   Wiktionary

  • peephole-optimization — adjective noun …   Wiktionary

  • Compiler optimization — is the process of tuning the output of a compiler to minimize or maximize some attributes of an executable computer program. The most common requirement is to minimize the time taken to execute a program; a less common one is to minimize the… …   Wikipedia

  • Code generation (compiler) — In computer science, code generation is the process by which a compiler s code generator converts some intermediate representation of source code into a form (e.g., machine code) that can be readily executed by a machine (often a computer).… …   Wikipedia

  • Perl — This article is about the programming language. For other uses, see Perl (disambiguation). Perl Paradig …   Wikipedia

  • Xblite — Infobox programming language name = XBLite Summary paradigm = Procedural year = 2001 designer = David Szafranski developer = David Szafranski latest release version = 2.4.0 latest release date = release date|2008|04|15 typing = Static… …   Wikipedia

  • GNU Compiler Collection — Entwickler GCC Team Aktuelle Version 4.6.2 (26. Oktober 2011) Betriebssyste …   Deutsch Wikipedia

  • Algorithmic efficiency — In computer science, efficiency is used to describe properties of an algorithm relating to how much of various types of resources it consumes. Algorithmic efficiency can be thought of as analogous to engineering productivity for a repeating or… …   Wikipedia

  • HotSpot — Entwickler Sun Microsystems Aktuelle Version 20 Betriebssystem plattformübergreifend Programmier­sprache C/C++ …   Deutsch Wikipedia

  • Hotspot-Optimierung — Bei der Hotspot Optimierung handelt es sich um eine Optimierungs Technik, welche bei JIT Compilern Verwendung findet und das Laufzeitverhalten von Software während der Ausführung erheblich verbessert. Die Details dieses Verfahrens sollen hier… …   Deutsch Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”