cs1 1.2 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445
  1. .bp
  2. .NH 1
  3. Common subexpression elimination
  4. .NH 2
  5. Introduction
  6. .PP
  7. The Common Subexpression Elimination optimization technique (CS)
  8. tries to eliminate multiple computations of EM expressions
  9. that yield the same result.
  10. It places the result of one such computation
  11. in a temporary variable,
  12. and replaces the other computations by a reference
  13. to this temporary variable.
  14. The primary goal of this technique is to decrease
  15. the execution time of the program,
  16. but in general it will save space too.
  17. .PP
  18. As an example of the application of Common Subexpression Elimination,
  19. consider the piece of program in Fig. 7.1(a).
  20. .DS
  21. .TS
  22. l l l.
  23. x := a * b; TMP := a * b; x := a * b;
  24. CODE; x := TMP; CODE
  25. y := c + a * b; CODE y := x;
  26. y := c + TMP;
  27. (a) (b) (c)
  28. .TE
  29. Fig. 7.1 Examples of Common Subexpression Elimination
  30. .DE
  31. If neither a nor b is changed in CODE,
  32. the instructions can be replaced by those of Fig. 7.1(b),
  33. which saves one multiplication,
  34. but costs an extra store instruction.
  35. If the value of x is not changed in CODE either,
  36. the instructions can be replaced by those of Fig. 7.1(c).
  37. In this case
  38. the extra store is not needed.
  39. .PP
  40. In the following sections we will describe
  41. which transformations are done
  42. by CS and how this phase
  43. was implemented.