Induction Variables and Reduction in Strength
Introduction: Another important optimization is to find induction variables in loops and optimize their computation. A variable x is said to be an. "induction variable" if there is a positive or negative constant c such that each time x is assigned, its value increases by c. For instance, i and tl are induction variables in the loop containing B2 of Fig. 9.5. Induction variables can be computed with a single increment (addition or subtraction) per loop iteration. The transformation of replacing an expensive operation, such as multiplication, by a cheaper one, such as addition, is known as strength reduction. But induction variables not only allow us sometimes to perform a strength reduction; often it is possible to eliminate all but one of a group of induction variables whose values remain in lock step as we go around the loop.
When processing loops, it is useful to work "inside-out"; that is, we shall start with the inner loops and proceed to progressively larger, surrounding loops. Thus, we shall see how this optimization applies to our quicksort example by beginning with one of the innermost loops: B3 by itself. Note that the values of j and £4 remain in lock step; every time the value of j decreases by 1, the value of t4 decreases by 4, because 4 * j is assigned to t4. These variables, j and t4, thus form a good example of a pair of induction variables.
When there are two or more induction variables in a loop, it may be possible to get rid of all but one. For the inner loop of B3 in Fig. 9.5, we cannot get rid of either j or t4 completely; t4 is used in B3 and j is used in B±. However, we can illustrate reduction in strength and a part of the process of induction-variable elimination. Eventually, j will be eliminated when the outer loop consisting of blocks B?,,B3, B± and B5 is considered.
Example: As the relationship £4 = 4 * j surely holds after assignment to £4 in Fig. 9.5, and £4 is not changed elsewhere in the inner loop around B3, it follows that just after the statement j = j - 1 the relationship £4 = 4 * j 4 must hold. We may therefore replace the assignment t4 = 4* j by t4 = t 4 - 4. The only problem is that £4 does not have a value when we enter block B3 for the first time. Since we must maintain the relationship £4 = 4 * j on entry to the block B3, we place an initialization of £4 at the end of the block where j itself is initialized, shown by the dashed addition to block B\ in Fig. 9.8. Although we have added one more instruction, which is executed once in block Bi, 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.
We conclude this section with one more instance of induction-variable elimination. This example treats i and j in the context of the outer loop containing B2, B3, B4, and B5.
Example: After reduction in strength is applied to the inner loops around B2 and B3, the only use of i and j is to determine the outcome of the test in block B4. We know that the values of i and t2 satisfy the relationship t2 = 4*i, while those of j and £4 satisfy the relationship ti = 4* j. Thus, the test t2 > ti can substitute for i > j. Once this replacement is made, i in block B2 and j in block B3 become dead variables, and the assignments to them in these blocks become dead code that can be eliminated. The resulting flow graph is shown in Fig. 9.9.
The code-improving transformations we have discussed have been effective. In Fig. 9.9, the numbers of instructions in blocks B2 and B3 have been reduced from 4 to 3, compared with the original flow graph in Fig. 9.3. In B5, the number has been reduced from 9 to 3, and in B6 from 8 to 3. True, Bi has grown from four instructions to six, but Bi is executed only once in the fragment, so the total running time is barely affected by the size of B\.