doc/ego/sr/sr1

   1 .bp
   2 .NH 1
   3 Strength reduction
   4 .NH 2
   5 Introduction
   6 .PP
   7 The Strength Reduction optimization technique (SR)
   8 tries to replace expensive operators
   9 by cheaper ones,
  10 in order to decrease the execution time
  11 of the program.
  12 A classical example is replacing a 'multiplication by 2'
  13 by an addition or a shift instruction.
  14 These kinds of local transformations are already
  15 done by the EM Peephole Optimizer.
  16 Strength reduction can also be applied
  17 more generally to operators used in a loop.
  18 .DS
  19 .TS
  20 l l.
  21 i := 1; i := 1;
  22 while i < 100 loop\ \ \ \ \ \ \ -->     TMP := i * 118;
  23    put(i * 118);        while i < 100 loop
  24    i := i + 1;     put(TMP);
  25 end loop;          i := i + 1;
  26            TMP := TMP + 118;
  27         end loop;
  28 .TE
  29
  30 Fig. 6.1 An example of Strenght Reduction
  31 .DE
  32 In Fig. 6.1, a multiplication inside a loop is
  33 replaced by an addition inside the loop and a multiplication
  34 outside the loop.
  35 Clearly, this is a global optimization; it cannot
  36 be done by a peephole optimizer.
  37 .PP
  38 In some cases a related technique, \fItest replacement\fR,
  39 can be used to eliminate the
  40 loop variable i.
  41 This technique will not be discussed in this report.
  42 .sp 0
  43 In the example above, the resulting code
  44 can be further optimized by using
  45 constant propagation.
  46 Obviously, this is not the task of the
  47 Strength Reduction phase.