1CS553 Lecture Induction Variables 1Induction Variables Announcements– HW1 due Monday– No office hours Thursday– No class Friday Last Time– Code Motion Today– Induction variablesCS553 Lecture Induction Variables 2Induction variables Induction variable identification– Induction variables– Variables whose values form an arithmetic progression– Useful for strength reduction, induction variable elimination, andloop transformations Why bother?– Automatic parallelization, . . . Simple approach– Search for statements of the form, i = i + c– Examine ud-chains to make sure there are no other defs of i in the loop– Does not catch all induction variables. Examples?CS553 Lecture Induction Variables 3Induction Variable Identification Types of Induction Variables– Basic induction variables (eg. loop index)– Variables that are defined once in a loop by a statement of the form,i=i+c (or i=i-c), where c is a constant integer– Derived induction variables– Variables that are defined once in a loop as a linear function ofanother induction variable– k = j + c1 or– k = c2 * j where c1 and c2 are loop invariantCS553 Lecture Induction Variables 4Example Induction Variables s = 0; for (i=0; i<N; i++) s += a[i];2CS553 Lecture Induction Variables 5Induction Variable Triples Each induction variable k is associated with a triple (i, c1, c2)– i is a basic induction variable– c1 and c2 are constants such that k = c1 + c2 * i when k is defined– k belongs to the family of i Basic induction variables– their triple is (i, 0, 1)– i = 0 + 1*i when i is definedCS553 Lecture Induction Variables 6Algorithm for Identifying Induction VariablesInput: A loop L consisting of 3-address instructions, ud-chains, and loop-invariantinformation.Output: A set of induction variables, each with an associated triple.Algorithm:1. For each stmt in L that matches the pattern i = i+c or i=i-c create the triple (i, 0, 1).2. Derived induction variables: For each stmt of L,– If the stmt is of the form k=j+ c1 or k=j* c2– and j is an induction variable with the triple (x, a, b)– and c1 and c2 are loop invariant– and k is only defined once in the loop– and if j is a derived induction variable belonging to the familty 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* c2CS553 Lecture Induction Variables 7Example: Induction Variable DetectionPicture from Prof David Walker’s CS320 slidesCS553 Lecture Induction Variables 8Algorithm for Strength ReductionInput: A loop L consisting of 3-address instructions and induction variable triples.Output: A modified loop with a new preheader.Algorithm:1. For each derived induction variable j with triple (i, a, b)– create a new j’– put computation t=b*c in preheader– after each definition of i in L, where i = i+c insert j’ = j’ + t– replace the definition of j with j=j’– initialize j’ at the end of the preheader to j’ = a+b*iNote:– j’ also has triple (i, a, b)– multiplication has been moved out of the loop3CS553 Lecture Induction Variables 9Example: Strength ReductionPicture from Prof David Walker’s CS320 slidesCS553 Lecture Induction Variables 10Algorithm for Induction Variable EliminationInput: A loop L consisting of 3-address instructions, ud-chains, loop-invariantinformation, and live-variable information.Output: A revised loop.Algorithm:1. For each basic induction variable i– If only uses are to compute other induction variables in its family and inconditional branches– Use a triple (j, c, d) in family, preferably with c = 0– Modify each conditional involving i so that b is used instead– if i relop x goto L# becomes if j relop y goto L# with y = c + d*x– Delete all assignments to the eliminated induction variable2. Apply copy propagation followed by dead code elimination to eliminate copiesintroduced by strength-reduction.3. Remove any induction variable definitions where the induction variable is onlyused and defined within that definition.CS553 Lecture Induction Variables 11Example: Induction Variable EliminationPicture from Prof David Walker’s CS320 slidesCS553 Lecture Induction Variables 12Summary Induction variable detection uses– strength reduction and induction variable elimination– data dependence analysis, which can then be used for parallelization Strength reduction– removes multiplications– the definition for some derived induction variables no longer dependdirectly on a basic induction variable Induction variable elimination– removes unnecessary induction variables4CS553 Lecture Induction Variables 13Next Time Reading– Ch 19 through 19.2 Lecture–
View Full Document
Unlocking...