sr2 6.3 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223
  1. .NH 2
  2. The model of strength reduction
  3. .PP
  4. In this section we will describe
  5. the transformations performed by
  6. Strength Reduction (SR).
  7. Before doing so, we will introduce the
  8. central notion of an induction variable.
  9. .NH 3
  10. Induction variables
  11. .PP
  12. SR looks for variables whose
  13. values form an arithmetic progression
  14. at the beginning of a loop.
  15. These variables are called induction variables.
  16. The most frequently occurring example of such
  17. a variable is a loop-variable in a high-order
  18. programming language.
  19. Several quite sophisticated models of strength
  20. reduction can be found in the literature.
  21. .[
  22. cocke reduction strength cacm
  23. .]
  24. .[
  25. allen cocke kennedy reduction strength
  26. .]
  27. .[
  28. lowry medlock cacm
  29. .]
  30. .[
  31. aho compiler design
  32. .]
  33. In these models the notion of an induction variable
  34. is far more general than the intuitive notion
  35. of a loop-variable.
  36. The definition of an induction variable we present here
  37. is more restricted,
  38. yielding a simpler model and simpler transformations.
  39. We think the principle source for strength reduction lies in
  40. expressions using a loop-variable,
  41. i.e. a variable that is incremented or decremented
  42. by the same amount after every loop iteration,
  43. and that cannot be changed in any other way.
  44. .PP
  45. Of course, the EM code does not contain high level constructs
  46. such as for-statements.
  47. We will define an induction variable in terms
  48. of the Intermediate Code of the optimizer.
  49. Note that the notions of a loop in the
  50. EM text and of a firm basic block
  51. were defined in section 3.3.5.
  52. .sp
  53. .UL definition
  54. .sp 0
  55. An induction variable i of a loop L is a local variable
  56. that is never accessed indirectly,
  57. whose size is the word size of the target machine, and
  58. that is assigned exactly once within L,
  59. the assignment:
  60. .IP -
  61. being of the form i := i + c or i := c +i,
  62. c is a constant
  63. called the \fIstep value\fR of i.
  64. .IP -
  65. occurring in a firm block of L.
  66. .LP
  67. (Note that the first restriction on the assignment
  68. is not described in terms of the Intermediate Code;
  69. we will give such a description later; the current
  70. definition is easier to understand however).
  71. .NH 3
  72. Recognized expressions
  73. .PP
  74. SR recognizes certain expressions using
  75. an induction variable and replaces
  76. them by cheaper ones.
  77. Two kinds of expensive operations are recognized:
  78. multiplication and array address computations.
  79. The expressions that are simplified must
  80. use an induction variable
  81. as an operand of
  82. a multiplication or as index in an array expression.
  83. .PP
  84. Often a linear function of an induction variable is used,
  85. rather than the variable itself.
  86. In these cases optimization is still possible.
  87. We call such expressions \fIiv-expressions\fR.
  88. .sp
  89. .UL definition:
  90. .sp 0
  91. An iv-expression of an induction variable i of a loop L is
  92. an expression that:
  93. .IP -
  94. uses only the operators + and - (unary as well as binary)
  95. .IP -
  96. uses i as operand exactly once
  97. .IP -
  98. uses (besides i) only constants or variables that are
  99. never changed in L as operands.
  100. .LP
  101. .PP
  102. The expressions recognized by SR are of the following forms:
  103. .IP (1)
  104. iv_expression * constant
  105. .IP (2)
  106. constant * iv_expression
  107. .IP (3)
  108. A[iv-expression] := \kx(assign to array element)
  109. .IP (4)
  110. A[iv-expression] \h'|\nxu'(use array element)
  111. .IP (5)
  112. & A[iv-expression] \h'|\nxu'(take address of array element)
  113. .LP
  114. (Note that EM has different instructions to use an array element,
  115. store into one, or take the address of one, resp. LAR, SAR, and AAR).
  116. .sp 0
  117. The size of the elements of A must
  118. be known statically.
  119. In cases (3) and (4) this size
  120. must equal the word size of the
  121. target machine.
  122. .NH 3
  123. Transformations
  124. .PP
  125. With every recognized expression we associate
  126. a new temporary local variable TMP,
  127. allocated in the stack frame of the
  128. procedure containing the expression.
  129. At any program point within the loop, TMP will
  130. contain the following value:
  131. .IP multiplication: 18
  132. the current value of iv-expression * constant
  133. .IP arrays:
  134. the current value of &A[iv-expression].
  135. .LP
  136. In the second case, TMP essentially is a pointer variable,
  137. pointing to the element of A that is currently in use.
  138. .sp 0
  139. If the same expression occurs several times in the loop,
  140. the same temporary local is used each time.
  141. .PP
  142. Three transformations are applied to the EM text:
  143. .IP (1)
  144. TMP is initialized with the right value.
  145. This initialization takes place just
  146. before the loop.
  147. .IP (2)
  148. The recognized expression is simplified.
  149. .IP (3)
  150. TMP is incremented; this takes place just
  151. after the induction variable is incremented.
  152. .LP
  153. For multiplication, the initial value of TMP
  154. is the value of the recognized expression at
  155. the program point immediately before the loop.
  156. For arrays, TMP is initialized with the address
  157. of the first array element that is accessed.
  158. So the initialization code is:
  159. .DS
  160. TMP := iv-expression * constant; or
  161. TMP := &A[iv-expression]
  162. .DE
  163. At the point immediately before the loop,
  164. the induction variable will already have been
  165. initialized,
  166. so the value used in the code above will be the
  167. value it has during the first iteration.
  168. .PP
  169. For multiplication, the recognized expression can simply be
  170. replaced by TMP.
  171. For array optimizations, the replacement
  172. depends on the form:
  173. .DS
  174. .TS
  175. l l l.
  176. \fIform\fR \fIreplacement\fR
  177. (3) A[iv-expr] := *TMP := (assign indirect)
  178. (4) A[iv-expr] *TMP (use indirect)
  179. (5) &A[iv-expr] TMP
  180. .TE
  181. .DE
  182. The '*' denotes the indirect operator. (Note that
  183. EM has different instructions to do
  184. an assign-indirect and a use-indirect).
  185. As the size of the array elements is restricted
  186. to be the word size in case (3) and (4),
  187. only one EM instruction needs to
  188. be generated in all cases.
  189. .PP
  190. The amount by which TMP is incremented is:
  191. .IP multiplication: 18
  192. step value * constant
  193. .IP arrays:
  194. step value * element size
  195. .LP
  196. Note that the step value (see definition of induction variable above),
  197. the constant, and the element size (see previous section) can all
  198. be determined statically.
  199. If the sign of the induction variable in the
  200. iv-expression is negative, the amount
  201. must be negated.
  202. .PP
  203. The transformations are demonstrated by an example.
  204. .DS
  205. .TS
  206. l l.
  207. i := 100; i := 100;
  208. while i > 1 loop TMP := (6-i) * 5;
  209. X := (6-i) * 5 + 2; while i > 1 loop
  210. Y := (6-i) * 5 - 8;\ \ \ \ \ \ \ --> X := TMP + 2;
  211. i := i - 3; Y := TMP - 8;
  212. end loop; i := i - 3;
  213. TMP := TMP + 15;
  214. end loop;
  215. .TE
  216. Fig. 6.2 Example of complex Strength Reduction transformations
  217. .DE
  218. The expression '(6-i)*5' is recognized twice. The constant
  219. is 5.
  220. The step value is -3.
  221. The sign of i in the recognized expression is '-'.
  222. So the increment value of TMP is -(-3*5) = +15.