.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.