doc/ego/cs/cs1

   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
  28    (a)     (b)     (c)
  29 .TE
  30
  31 Fig. 7.1  Examples of Common Subexpression Elimination
  32 .DE
  33 If neither a nor b is changed in CODE,
  34 the instructions can be replaced by those of Fig. 7.1(b),
  35 which saves one multiplication,
  36 but costs an extra store instruction.
  37 If the value of x is not changed in CODE either,
  38 the instructions can be replaced by those of Fig. 7.1(c).
  39 In this case
  40 the extra store is not needed.
  41 .PP
  42 In the following sections we will describe
  43 which transformations are done
  44 by CS and how this phase
  45 was implemented.