Peephole Optimization in Compilers

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


Share on Google Plus

About Data Sciences by Venu

Hi, My name is Venugopala Chary and I'm Currently working as Associate Professor in Reputed Engineerng College, Hyderabad. I have B.Tech and M.tech in regular from JNTU Hyderabad. I have 11 Years of Teaching Experience for both B.Tech and M.Tech Courses.
    Blogger Comment
    Facebook Comment

0 comments:

Post a Comment