Induction Variable Elements
A variable is said to be an induction variable, if its value changes by a fixed quantity on each iteration of a loop
Consider the following TAC,
(1) mul = 0
(2) i = 1
(3) t2 = addr(a) – 4
(4) t4 = addr(b) -4
(5) t1 = 5 * i
(6) t3 = t2[t1]
(7) t5 = t4[t1]
(8) t6 = t3 * t5
(9) mul = mul + t6
(10)i = i + 1
(11)if, I <= 20 goto (5)
Here, two induction variables i and t1 are present. A thumb rule in elimination of induction variable is when there are two or more induction variables in a loop we can get rid of all but one
in the TAC, I gets incremented by 1 and t1 by 4 in each iteration of the loop. Now, removing i from the loop yields the following TAC
(1) mul = 0
(2) i = 1
(3) t2 = addr(a) – 4
(4) t4 = addr(b) – 4
(5) t1 = 0
(6) t1 = t1 + 4
(7) t3 = t2[t1]
(8) t5 = t4[t1]
(9) t6 = t3 * t5
(10)mul = mul + t6
(11)if, t1 < = 76 goto (6)
As loop iterates until i <= 20 it becomes t1 <= 76 as shown above
Algorithm for Identifying Induction Variables
Input: A loop L consisting of 3 address instructions, use-Definition Chain, and loop-invariant information.
Output: A set of induction variables, each with an associated triple.
Algorithm
For each statement in L that matches the pattern i = i + c or i = i – c create the triple (i, 0, 1)
Derived induction variables: For each statement of L
If the statement is of the form k = j + c1 or k = j * c2
j is an induction variable with the triple (x, a, b)
c1 and c2 are loop invariant
k is only defined once in the loop
if j is a derived induction variable belonging to the family of i then
The only def of j that reaches k must be in L
And no def of i must occur on any path between the definition of j and k
Then create the triple (x, a + c1, b) for k =j + c1 or (x, a*c2, b*c2) for k = j*c2
0 comments:
Post a Comment