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
