sr1 1.2 KB

1234567891011121314151617181920212223242526272829303132333435363738394041424344454647
  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. Fig. 6.1 An example of Strenght Reduction
  30. .DE
  31. In Fig. 6.1, a multiplication inside a loop is
  32. replaced by an addition inside the loop and a multiplication
  33. outside the loop.
  34. Clearly, this is a global optimization; it cannot
  35. be done by a peephole optimizer.
  36. .PP
  37. In some cases a related technique, \fItest replacement\fR,
  38. can be used to eliminate the
  39. loop variable i.
  40. This technique will not be discussed in this report.
  41. .sp 0
  42. In the example above, the resulting code
  43. can be further optimized by using
  44. constant propagation.
  45. Obviously, this is not the task of the
  46. Strength Reduction phase.