2.1 Function-Preserving Transformations
2.2 Common Sub expressions elimination:
The above code can be optimized using the common sub-expression elimination as t1: =4*i t2: =a [t1] t3: =4*j t5: =n t6: =b [t1] +t5
The common sub expression t 4: =4*i is eliminated as its computation is already in t1. And value of i is not been changed from definition to use.
2.3 Copy Propagation:
Assignments of the form f : = g called copy statements, or copies for short. The idea behind the copy-propagation transformation is to use g for f, whenever possible after the copy statement f: = g. Copy propagation means use of one variable instead of another. This may not appear to be an improvement, but as we shall see it gives us an opportunity to eliminate x.
For example: x=Pi;
The optimization using copy propagation can be done as follows:
Here the variable x is eliminated.
2.4 Dead-Code Eliminations:
A variable is live at a point in a program if its value can be used subsequently; otherwise, it is dead at that point. A related idea is dead or useless code, statements that compute values that never get used. While the programmer is unlikely to introduce any dead code intentionally, it may appear as the result of previous transformations. An optimization can be done by eliminating dead code.
Example: i=0; if(i=1)
Here, ‘if’ statement is dead code because this condition will never get satisfied.
2.5 Constant folding:
o We can eliminate both the test and printing from the object code. More generally, deducing at compile time that the value of an expression is a constant and using the constant instead is known as constant folding. o One advantage of copy propagation is that it often turns the copy statement into dead code.
For example, a=3.14157/2 can be replaced by a=1.570 there by eliminating a division operation.
2.6 Loop Optimizations:
o We now give a brief introduction to a very important place for optimizations, namely loops, especially the inner loops where programs tend to spend the bulk of their time. The running time of a program may be improved if we decrease the number of instructions in an inner loop, even if we increase the amount of code outside that loop. o Three techniques are important for loop optimization: §
2.7 Code Motion:
while (i <= limit-2) /* statement does not change Limit*/ Code motion will result in the equivalent of t= limit-2; while (i<=t) /* statement does not change limit or t */
2.8 Induction Variables :
As the relationship t 4:=4*j surely holds after such an assignment to t 4 in Fig. and t4 is not changed elsewhere in the inner loop around B3, it follows that just after the statement j:=j -1 the relationship t4:= 4*j-4 must hold. We may therefore replace the assignment t 4:= 4*j by t4:= t4-4. The only problem is that t 4 does not have a value when we enter block B3 for the first time. Since we must maintain the relationship t4=4*j on entry to the block B3, we place an initializations of t4 at the end of the block where j itself is initialized, shown by the dashed addition to block B1 in second Fig.
The replacement of a multiplication by a subtraction will speed up the object code if multiplication takes more time than addition or subtraction, as is the case on many machines.
2.9 Reduction in Strength: