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- -
Related Topics
Privacy Policy, Terms and Conditions, DMCA Policy and Compliant
Copyright © 2018-2024 BrainKart.com; All Rights Reserved. Developed by Therithal info, Chennai.