doc/ego/sr/sr2

   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
 217 Fig. 6.2 Example of complex Strength Reduction transformations
 218 .DE
 219 The expression '(6-i)*5' is recognized twice. The constant
 220 is 5.
 221 The step value is -3.
 222 The sign of i in the recognized expression is '-'.
 223 So the increment value of TMP is -(-3*5) = +15.