Algorithms for Compiler Design: 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 1. In the loop formed by B2, I is a basic induction variable.

Figure 1: 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 T1 is also an induction variable, because the only assignment of T1 in the loop assigns a value to T1 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:

1. Find all of the basic induction variables by scanning the statements of loop L.

2. 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.

3. 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 1, we see that I is a basic induction variable, and T1 is the additional induction variable in the family of I, because the value of T1 at the point of assignment in the loop is expressed as T1 = 4 * I. Therefore, according to step 3b, we replace T1 = 4 * I by T1 = temp. And according to step 3c, we add temp = 4 * I to the preheader. We then append the statement temp = temp + 4 after Figure 1 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 2.

Figure 2: Modified flow graph.

By step 3f, replace T1 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 B1, the statement if temp ≤ temp2 goto B2 can be replaced by if temp ≤ 80 goto B2, and we can eliminate temp2 = 80, as shown in Figure 3.

Figure 3: Flow graph preheader modifications.