Home | | Compiler Design | Peephole Optimization

Chapter: Principles of Compiler Design : Code optimization

Peephole Optimization

A statement-by-statement code-generations strategy often produces target code that contains redundant instructions and suboptimal constructs.

PEEPHOLE OPTIMIZATION

A statement-by-statement code-generations strategy often produces target code that contains redundant instructions and suboptimal constructs. The quality of such target code can be improved by applying “optimizing” transformations to the target program.

 

A simple but effective technique for improving the target code is peephole optimization, a method for trying to improving the performance of the target program by examining a short sequence of target instructions (called the peephole) and replacing these instructions by a shorter or faster sequence, whenever possible.

 

The peephole is a small, moving window on the target program. The code in the peephole need not be contiguous, although some implementations do require this. It is characteristic of peephole optimization that each improvement may spawn opportunities for additional improvements.

 

Characteristics of peephole optimizations:

Redundant-instructions elimination

Flow-of-control optimizations

Algebraic simplifications

Use of machine idioms

Unreachable

Redundant Loads And Stores:

If we see the instructions sequence

(1)   MOV R0,a

(2)   MOV a,R0

 

we can delete instructions (2) because whenever (2) is executed. (1) will ensure that the value of a is already in register R0.If (2) had a label we could not be sure that (1) was always executed immediately before (2) and so we could not remove (2).

 

Unreachable Code:

 

Another opportunity for peephole optimizations is the removal of unreachable instructions. An unlabeled instruction immediately following an unconditional jump may be removed. This operation can be repeated to eliminate a sequence of instructions. For example, for debugging purposes, a large program may have within it certain segments that are executed only if a variable debug is 1. In C, the source code might look like:

 

#define debug 0

….

 

If ( debug ) {

Print debugging information

 

}

In the intermediate representations the if-statement may be translated as:

 

If debug =1 goto L1 goto L2

 

L1: print debugging information L2: ………………………… (a)

 

One obvious peephole optimization is to eliminate jumps over jumps .Thus no matter what the value of debug; (a) can be replaced by:

 

If debug ≠1 goto L2

Print debugging information

L2: …………………………… (b)

 

If debug ≠0 goto L2

Print debugging information

L2: …………………………… (c)

 

As the argument of the statement of (c) evaluates to a constant true it can be replaced

 

By goto L2. Then all the statement that print debugging aids are manifestly unreachable and can be eliminated one at a time.

 

Flows-Of-Control Optimizations:

The unnecessary jumps can be eliminated in either the intermediate code or the target code by the following types of peephole optimizations. We can replace the jump sequence

 

goto L1

….

 

L1: gotoL2 (d)

by the sequence

goto L2

….

 

L1: goto L2

 

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

 

if a < b goto L1

….

 

L1: goto L2 (e)

 

can be replaced by

If a < b goto L2

 

….

 

L1: goto L2

 

Ø     Finally, suppose there is only one jump to L1 and L1 is preceded by an unconditional goto. Then the sequence

 

goto L1

 

L1: if a < b goto L2 (f) L3:

 

may be replaced by

 

If a < b goto L2

goto L3

 

…….

 

L3:

 

 

While the number of instructions in(e) and (f) is the same, we sometimes skip the unconditional jump in (f), but never in (e).Thus (f) is superior to (e) in execution time

 

Algebraic Simplification:

 

There is no end to the amount of algebraic simplification that can be attempted through peephole optimization. Only a few algebraic identities occur frequently enough that it is worth considering implementing them. For example, statements such as

x := x+0 or

x := x * 1

 

are often produced by straightforward intermediate code-generation algorithms, and they can be eliminated easily through peephole optimization.

 

Reduction in Strength:

 

Reduction in strength replaces expensive operations by equivalent cheaper ones on the target machine. Certain machine instructions are considerably cheaper than others and can often be used as special cases of more expensive operators.

 

For example, x² is invariably cheaper to implement as x*x than as a call to an exponentiation routine. Fixed-point multiplication or division by a power of two is cheaper to implement as a shift. Floating-point division by a constant can be implemented as multiplication by a constant, which may be cheaper.

 

X2 → X*X

 

Use of Machine Idioms:

 

The target machine may have hardware instructions to implement certain specific operations efficiently. For example, some machines have auto-increment and auto-decrement addressing modes. These add or subtract one from an operand before or after using its value. The use of these modes greatly improves the quality of code when pushing or popping a stack, as in parameter passing. These modes can also be used in code for statements like i : =i+1.

 

i:=i+1 → i++

i:=i-1 → i- -

 

 


Study Material, Lecturing Notes, Assignment, Reference, Wiki description explanation, brief detail
Principles of Compiler Design : Code optimization : Peephole Optimization |


Privacy Policy, Terms and Conditions, DMCA Policy and Compliant

Copyright © 2018-2024 BrainKart.com; All Rights Reserved. Developed by Therithal info, Chennai.