10.5 ELIMINATING LOCAL COMMON SUBEXPRESSIONS | Algorithms for Compiler Design (Electrical and Computer Engineering Series)

10.4 ELIMINATING INDUCTION VARIABLES

We define basic induction variables of a loop as those names whose only assignments within the loop are of the form I = I ± C , where C is a constant or a name whose value does not change within the loop. A basic induction variable may or may not form an arithmetic progression at the loop header.

For example, consider the flow graph shown in Figure 10.10. In the loop formed by B 2, I is a basic induction variable.

Figure 10.10: Flow graph where I is a basic induction variable.

We then define an induction variable of loop L as either a basic induction variable or a name J for which there is a basic induction variable I , such that each time J is assigned in L , J 's value is some linear function or value of I . That is, the value of J in L should be C ₁ I + C ₂ , where C ₁ and C ₂ could be functions of both constants and loop invariant names. For example, in loop L, I is a basic induction variable; and T 1 is also an induction variable, because the only assignment of T 1 in the loop assigns a value to T 1 that is a linear function of I , computed as 4 * I.

Algorithm for Detecting and Eliminating Induction Variables

An algorithm exists that will detect and eliminate induction variables. Its method is as follows :

Find all of the basic induction variables by scanning the statements of loop L .
Find any additional induction variables, and for each such additional induction variable A , find the family of some basic induction B to which A belongs. (If the value of A at the point of assignment is expressed as C ₁ B + C ₂ , then A is said to belong to the family of basic induction variable B ). Specifically, we search for names A with single assignments to A within loop L , and which have one of the following forms:

where C is a loop constant, and B is an induction variable, basic or otherwise . If B is basic, then A is in the family of B . If B is not basic, let B be in the family of D , then the additional requirements to be satisfied are:
1. There must be no assignment to D between the lone point of assignment to B in L and the assignment to A .
2. There must be no definition of B outside of L reaches A .
Consider each basic induction variable B in turn . For every induction variable A in the family of B :
1. Create a new name, temp.
2. Replace the assignment to A in the loop with A = temp.
3. Set temp to C ₁ B + C ₂ at the end of the preheader by adding the statements:
4. Immediately after each assignment B = B + D , where D is a loop invariant, append:
  
  If D is a loop invariant name, and if C ₁ ‰ 1, create a new loop invariant name for C ₁ * D , and add the statements:
5. For each basic induction variable B whose only uses are to compute other induction variables in its family and in conditional branches, take some A in B 's family, preferably one whose function expresses its value simply, and replace each test of the form B reloop X goto Y by:
  
  Delete all assignments to B from the loop, as they will now be useless.
6. If there is no assignment to temp between the introduced statement A = temp (step 1) and the only use of A , then replace all uses of A by temp and delete the statement A = temp.
  
  In the flow graph shown in Figure 10.10, we see that I is a basic induction variable, and T 1 is the additional induction variable in the family of I , because the value of T 1 at the point of assignment in the loop is expressed as T 1 = 4 * I . Therefore, according to step 3b, we replace T 1 = 4 * I by T 1 = temp. And according to step 3c, we add temp = 4 * I to the preheader. We then append the statement temp = temp + 4 after Figure 10.10 statement (10), as per step 3d. And according to step 3e, we replace the statement if I ‰ 20 goto B2 by:
  
  The results of these modifications are shown in Figure 10.11.

Figure 10.11: Modified flow graph.

By step 3f, replace T 1 by temp. And by copy propagation, temp = 4 * I , in the preheader, can be replaced by temp = 4, and the statement I = 1 can be eliminated. In B 1, the statement if temp ‰ temp2 goto B 2 can be replaced by if temp ‰ 80 goto B 2, and we can eliminate temp2 = 80, as shown in Figure 10.12.

Figure 10.12: Flow graph preheader modifications.