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
0 comments:
Post a Comment