34 Code Optimization
Rajeswari Sridhar
In this module, we will understand the function preserving transformations and loop optimization techniques that would be carried out as a means of code optimization
34.1 Optimization
Function preserving transformations and loop optimization are the major optimizations that are carried out in every basic block. We considered the code for quick sort as an example to explain the optimizations that can be carried out in the previous module. The high level code is converted to three-address code and this will later represent as a control flow graph. For convenience, the control flow graph of quick sort program is given in figure 34.1.
From figure 34.1, blocks B5 and B6 alone are given in the above table for convenience as our focus will be these two blocks for applying function preserving transformation. We will discuss in detail the function preserving transformations and how this could be applied to our example in subsequent sections.
34.2 Function Preserving Transformation
The following are some of the function preserving transformation.
• Common Sub-expression Elimination
• Copy Propagation
• Dead-code elimination
• Constant Folding
The order in which one applies these transformations is also important for any particular block as an incorrect order may result in redundant code.
34.2.1 Common Sub-expression Elimination (CSE)
Common sub-expressions are so very frequently occurring in any scenario of code. E is called a common sub-expression if E was previously computed and the values of variables in E have not changed since the previous computation and this E is occurring at a particular point of time. Identifying E is easier with DAG as a basic block and this is identified as the node that have multiple tags associated
Consider the quick sort example and let us consider the basic block B5. The temporary variables t6 and t7 computes the expression 4 * i. Similarly, the temporary variables t8 and t10 computes the expression 4 * j between the computation of t6 and t7 and the value of the variable ‘i’ has not
changed. So is the case between the expressions t8 and t10 for the variable ‘j’. Thus we can say, t7 has a common expression with t6 and t10 have common sub-expression with t8. We will see how to eliminate this.
To eliminate common sub-expression, in the second occurrence of the common sub-expression, replace the expression with the first computed expression’s variable. So, in this example for the block B5, t6 has the result of the expression 4 * i and hence, wherever 4*i occurs within a basic block, we replace it with t6. So, is the case for 4 * j where we replace with t8. This common sub-expression is referred to as local common sub-expression as we are analyzing within a basic block. On the other hand, if this is carried out across basic blocks, the optimization is referred to global common sub-expression. A particular value of ‘i’ and ‘j’ both enters the basics 5 and 6 respectively. Thus the same value of ‘i’ and ‘j’ is being used by both these blocks and hence common sub-expression could be incorporated across these blocks also. If we try to trace back, 4 * i computed in block B2 and 4 * j computed in B3 hasn’t changed till B5 or B6. Hence, their values could be reused. So is the value of a[t2] and a[t4]. Table 34.1 explains the local and global common sub-expression elimination of the basic blocks B5 and B6
34.2.2 Copy Propagation
Assignments of the form f:= g denotes a copy statement. Copy statements, could be available in the code itself. In addition elimination of common sub-expression leads to creation of copy. Elimination of copy statements is called copy propagation as the assignments f:= g, can be transformed by using “g” for “f”. After that, we remove the assignment statement f := g. In the table 34.1, we had removed the assignments statements which are copies, like t7:= t6, t10:= t8, etc and have used t6 in place of t7 and t8 in place of t10. Copy propagation could be carried out only if the values of these variables haven’t changed during the sequence of statements.
Consider the following example flow graph, where copy propagation could be carefully carried out. Copies are also introduced due to CSE and this also needs to be eliminated. Consider the following figure 34.2 (a)
We could use a temporary variable and now the CSE is independent of the variables‘d’ and ‘e’. Applying copy propagation to the basic blocks 5 and 6 will result in the following optimized code.
34.2.3 Dead-code elimination
A variable is live at a point where its value can be used subsequently, else dead at that point. Due to analyzing the copy statements, the statement
x := t3
is dead, because ‘x’ is not going to be used as it would be replaced by t3. These statements are removed from the three-address code.
34.2.4 Constant Folding
During compile time deducing that a value is constant and using the constant instead of the variable is known as constant folding. Identification of constant folding would also lead to dead code. Consider the following example involving two statements:
a := 1
c := a+ b
Here, ‘a’ has the value ‘1’ and hence therefore a constant and the expressions that uses ‘a’ could be replaced with ‘1’. Thus the instructions get changed as follows:
a:= 1
c := 1 + b
After applying constant folding there is no use for the statement a: = 1 and hence need to be eliminated as dead code and the final code corresponds to the one statement “c : = 1 + b”
34.3 DAG for optimization The directed acyclic graph (DAG) as discussed in the previous modules could be used for optimization. One simp le optimization is identification of common sub-expressions. Consider the following sequence of statements
a := b+c
- b := a-d
- c := b+c
- d := a – d
The DAG for the same is given in figure 34.3.
common sub-expression.
Algebraic simplifications are typically applied using DAG as a means of optimization. Algebraic identities are used to convert multiplication to addition, exponentiation to multiplication, etc. Multiplicative identity and additive identity are also applied to generate optimized code. For example, the following identities are used:
• x + 0 = 0 + x = x
• x – 0 = x
• x * 1 = 1 * x = x
• x / 1 = x
• x ** 2 = x * x
• x * 2 = x + x
These optimizations are applied either in the basic block or DAG before applying other optimizations.
34.4 Loop Optimization
Running time of a program may be improved if the number of instructions in the inner loop is reduced. Outer loops could have more instructions which we are fine with it. There are three types of optimizations that are possible with loops: Code motion, induction variable elimination and reduction in strength.
34.4.1 Code motion
If a particular code is not in motion, then we may not have to re-compute this code repeatedly. For example, consider the following piece of code:
while (i <= limit – 2)
{
}
L1:
t1 = limit – 2
if (i > t1) goto L2
body of loop
goto L1
L2:
The outside while() loop compares, whether the variab le ‘i’ is less than “limit-2” and enters or exits the loop. After the exit of the loop, the value of the variable ‘i’ which is altered inside the
while() loop will be compared and correspondingly two branches are taken. The expression “limit-2” will evaluate to the same value as the body of the while loop does not alter the variable “limit” and hence this variable is non- motion variable. This expression is computed every time the while() loop is entered and hence could be avoided. The details after implementing code motion are given below:
t := limit – 2
while (i <= t)
t1 = limit – 2
L1:
if (i > t1) goto L2
body of loop
goto L1
L2:
Before entering the while() loop, the expression “limit-2” is computed and stored in a temporary variable, and the while() continues or exits by comparing this variable “t” with the value of “i”
34.4.2 Strength Reduction
Typically induction Variables control loop iterations. Strength reduction involves replacing costlier computation with cheaper ones. Consider the figure 34.4 which are the parts of the basic blocks B2 / B3 of the CFG of figure 34.1. The computation 4*j gets executed every time the loop is entered. We could replace this computation of multiplication with just subtraction as the index
variable ‘j’ gets decremented by “1” for all iterations. The procedure involves creating a new block above this basic block and declares the multiplication once. Subsequently, for the next
Summary: In this module we discussed, basic function preserving transformations for implementing code optimizations. Algebraic transformations are also discussed to generate optimized code. Loop Optimization is very important to generate optimized code as loops increase or decrease the computational complexity of any program and the various loop optimizations are also discussed. In the next module, we will discuss more on loops to try out other possible optimizations that could be carried out.