Peephole Optimization:
Redundant instruction elimination:
Consider the
following target code instructions
(1) MOVE R0, X
(2) MOV x, R0
In such case,
instruction (2) can be safely eliminated because whenever (2) is executed, (1)
ensures that the value of x is already there in R)
Such elimination
is not possible if (2) had a label associated with it, because in such a case
it is not certain that (1) will always be executed immediate before (2)
So, instruction
(2) can be eliminated provided the instructions (1) and (2) are in the same
basic block
Unreachable Code Elimination
Generally the
code following an unconditional jump Is unreachable and can be eliminated. The
same operation can be repeated to eliminated a sequence of instructions
Consider the
following C code and its intermediate code
#define debug 0
. . . .
if (debug)
{
print debugging information
}
if debug = 1 goto L1
goto L2
L1: print debugging information
L2:
Now, the
intermediate code can be transformed as shown below
if debug ≠ 1
goto L2
print debugging
information
L2:
As debug is set
0 at the beginning by constant propagation, the code is
if 0 ≠ 1
goto L2
print debugging
information
L2:
As the condition
is always true, it can be replaced by goto L2, and statements that print
debugging information are unreachable and can be eliminated.
Flow of Control Optimization:
The intermediate
code generated, sometimes contains jumps to jumps, jumps to conditional jumps,
or conditional jumps to jumps
These unnecessary jumps can be eliminated
in either the intermediate code or in the target code using the following
peephole optimizations (jump means an conditional jump)
Jumps
to Jumps
Consider the following jump sequence
goto
L1
.
. . .
L1:
goto L2
The jump sequence can be replaced by the
following sequence
goto
L2
….
L1:
goto L2
In the above sequence, if there are no
jumps to L1 and the statement L1: goto L2 is precede by an unconditional jump,
then the statement L1: goto L2 can be eliminated
Jumps
to conditional Jumps
Consider the following jump sequence
goto
L1
L1:
if a < b goto L2
L3:
The given, jump sequence can be replaced by
the following sequence, provided there is only one jump to L1, and L2 is
preceded by an unconditional jump
if
a < b goto L2
goto
L3
…..
L3:
Note: Even
though the two sequences have the same number of instructions, it is possible
to skip, sometimes, the conditional goto in the second sequence, whereas it is
not possible with the first sequence. So, the second sequence is superior to
the first one in execution time.
Simplifications
Either in the
target code or in the intermediate code, only a few algebraic identities occur
frequently enough that are worth considering them implementing
But, sometimes
the instructions may contain algebraic identities that can be eliminated
Consider the
following intermediate code instructions
x = x + 0
x = x* 1
which can be
eliminated
Reduction in Strength
This
transformation involves replacing expensive operations by equivalent cheaper
ones on the target machine
Some examples
are:
X2 is 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
Use of Machine Idioms
The target
machine may have some hardware instructions to implement certain operations
efficiently. Using such instructions in the target code can reduce execution
time significantly
For example,
some machines may have auto increment and auto decrements addressing modes.
These add or subtract one from an operand before or after using its value.
These modes can be used in code for statements such as x = x+1
