Algorithms for Compiler Design: PEEPHOLE OPTIMIZATION

7/24/2010 8:03:58 PM

Code generated by using the statement-by-statement code-generation strategy contains redundant instructions and suboptimal constructs. Therefore, to improve the quality of the target code, optimization is required. Peephole optimization is an effective technique for locally improving the target code. Short sequences of target code instructions are examined and replacement by faster sequences wherever possible. Typical optimizations that can be performed are:

  • Elimination of redundant loads and stores

  • Elimination of multiple jumps

  • Elimination of unreachable code

  • Algebraic simplifications

  • Reducing for strength

  • Use of machine idioms

Eliminating Redundant Loads and Stores

If the target code contains the instruction sequence:

  1. MOV R, a

  2. MOV a, R

we can delete the second instruction if it an unlabeled instruction. This is because the first instruction ensures that the value of a is already in the register R. If it is labeled, there is no guarantee that step 1 will always be executed before step 2.

Eliminating Multiple Jumps

If we have jumps to other jumps, then the unnecessary jumps can be eliminated in either intermediate code or the target code. If we have a jump sequence:

       goto L1
L1: goto L2

then this can be replaced by:

       goto L2
L1: goto L2

If there are now no jumps to L1, then it may be possible to eliminate the statement, provided it is preceded by an unconditional jump. Similarly, the sequence:

       if a < b goto L1
L1: goto L2

can be replaced by:

       if a < b goto L2
L1: goto L2

Eliminating Unreachable Code

An unlabeled instruction that immediately follows an unconditional jump can possibly be removed, and this operation can be repeated in order to eliminate a sequence of instructions. For debugging purposes, a large program may have within it certain segments that are executed only if a debug variable is one. For example, the source code may be:

#define debug 0
if (debug)
            print debugging information

This if statement is translated in the intermediate code to:

goto L2

L1 : print debugging information

L2 :

One of the optimizations is to replace the pair:

if debug = 1 goto L1

goto L2

within the statements with a single conditional goto statement by negating the condition and changing its target, as shown below:

Print debugging information

L2 :

Since debug is a constant zero by constant propagation, this code will become:

if 0 1 goto L2

Print debugging information

L2 :

Since 0 1 is always true this will become:

goto L2

Print debugging information

L2 :

Therefore, the statements that print the debugging information are unreachable and can be eliminated, one at a time.

Algebraic Simplifications

If statements like:

are generated in the code, they can be eliminated, because zero is an additive identity, and one is a multiplicative identity.

Reducing Strength

Certain machine instructions are considered to be cheaper than others. Hence, if we replace expensive operations by equivalent cheaper ones on the target machine, then the efficiency will be better. For example, x2 is invariable cheaper to implement as x * x than as a call to an exponentiation routine. Similarly, fixed-point multiplication or division by a power of two is cheaper to implement as a shift.

Using Machine Idioms

The target machine may have hardware instructions to implement certain specific operations efficiently. Detecting situations that permit the use of these instructions can reduce execution time significantly. For example, some machines have auto-increment and auto-decrement addressing modes. Using these modes can greatly improve the quality of the code when pushing or popping a stack. These modes can also be used for implementing statements like a = a + 1.

Most View
Installing and Configuring Windows Server 2008 R2 : Administration basics (part 2) - Windows Server 2008 R2 administration tools
The End Of The Beginning Or The Beginning Of The End? (Part 1)
Windows 8 vs. OS X Mountain Lion (Part 3)
Exchange Server 2010 : Outlook Integration (part 4) - Contact Integration
Windows 8 : Storage Spaces (part 2) - The Most Basic Storage Spaces Configuration of All: One Disk, One Space, No Resiliency
ASP.NET 3.5 : Caching ASP.NET Pages (part 3) - Caching Portions of ASP.NET Pages
Windows 7 : ADDING UAC SUPPORT TO YOUR APPLICATION (part 3) - Executing as a Separate Process - Creating the Secondary Project , Configuring the Secondary Project
Sony Vaio Fit 15 - A Fast Laptop With A Good Quality, High-Resolution Screen
Blu-Ray Players Awards – Q1 2013 : Sony BDP-S790, Sony BDP-S390, Panasonic DMP-BDT220
New Products For March 2013 (Part 2)
Popular Tags
Microsoft Access Microsoft Excel Microsoft OneNote Microsoft PowerPoint Microsoft Project Microsoft Visio Microsoft Word Active Directory Biztalk Exchange Server Microsoft LynC Server Microsoft Dynamic Sharepoint Sql Server Windows Server 2008 Windows Server 2012 Windows 7 Windows 8 Adobe Indesign Adobe Flash Professional Dreamweaver Adobe Illustrator Adobe After Effects Adobe Photoshop Adobe Fireworks Adobe Flash Catalyst Corel Painter X CorelDRAW X5 CorelDraw 10 QuarkXPress 8 windows Phone 7 windows Phone 8 BlackBerry Android Ipad Iphone iOS
Top 10
Silverlight Recipes : Controls - Creating a Custom Layout Container (part 3)
Silverlight Recipes : Controls - Creating a Custom Layout Container (part 2)
Silverlight Recipes : Controls - Creating a Custom Layout Container (part 1)
The BMW X4 – Strong Performance (Part 3)
The BMW X4 – Strong Performance (Part 2)
The BMW X4 – Strong Performance (Part 1)
The BMW X5 25d – Top Truck
The Champion – Widebody Gc8 Built For All The Right Reasons (Part 2)
The FPV GT-F – This Is The End (Part 2)
The FPV GT-F – This Is The End (Part 1)