123456789101112131415161718192021222324252627282930313233343536373839404142434445 |
- .bp
- .NH 1
- Common subexpression elimination
- .NH 2
- Introduction
- .PP
- The Common Subexpression Elimination optimization technique (CS)
- tries to eliminate multiple computations of EM expressions
- that yield the same result.
- It places the result of one such computation
- in a temporary variable,
- and replaces the other computations by a reference
- to this temporary variable.
- The primary goal of this technique is to decrease
- the execution time of the program,
- but in general it will save space too.
- .PP
- As an example of the application of Common Subexpression Elimination,
- consider the piece of program in Fig. 7.1(a).
- .DS
- .TS
- l l l.
- x := a * b; TMP := a * b; x := a * b;
- CODE; x := TMP; CODE
- y := c + a * b; CODE y := x;
- y := c + TMP;
- (a) (b) (c)
- .TE
- Fig. 7.1 Examples of Common Subexpression Elimination
- .DE
- If neither a nor b is changed in CODE,
- the instructions can be replaced by those of Fig. 7.1(b),
- which saves one multiplication,
- but costs an extra store instruction.
- If the value of x is not changed in CODE either,
- the instructions can be replaced by those of Fig. 7.1(c).
- In this case
- the extra store is not needed.
- .PP
- In the following sections we will describe
- which transformations are done
- by CS and how this phase
- was implemented.
|