Introduction: There are a number of ways in which a compiler can improve a program without changing the function it computes. Common-subexpression elimination, copy propagation, dead-code elimination, and constant folding are common examples of such function-preserving (or semantics-preserving) transformations; we shall consider each in turn.
Frequently, a program will include several calculations of the same value, such as an offset in an array. As mentioned in Section 9.1.2, some of these duplicate calculations cannot be avoided by the programmer because they lie below the level of detail accessible within the source language. For example, block £5 shown in Fig. 9.4(a) recalculates 4 * i and 4* j , although none of these calculations were requested explicitly by the programmer.
Global Common Subexpressions: An occurrence of an expression E is called a common subexpression if E waspreviously computed and the values of the variables in E have not changed sincethe previous computation. We avoid recomputing E if we can use its previouslycomputed value; that is, the variable x to which the previous computation of
E was assigned has not changed in the interim.2
Example: The assignments to t7 and t lO in Fig. 9.4(a) compute the common subexpressions 4 * i and 4 * j, respectively. These steps have been eliminated in Fig. 9.4(b), which uses t6 instead of t7 and t8 instead of t l O.
Example: Figure 9.5 shows the result of eliminating both global and local common subexpressions from blocks f?5 and BQ in the flow graph of Fig. 9.3. We first discuss the transformation of B5 and then mention some subtleties involving arrays. After local common subexpressions are eliminated, B§ still evaluates 4*i and 4* j , as shown in Fig. 9.4(b). Both are common subexpressions; in particular, the three statements
t 8 = 4*j
t 9 = a[ t 8 ]
a[ t 8 ] = x
in B<$ can be replaced by
t 9 = a[ t 4]
a[ t 4 ] = x
using £4 computed in block B3. In Fig. 9.5, observe that as control passes from the evaluation of 4 * j in B3 to B5, there is no change to j and no change to £4, so t4 can be used if 4 * j is needed.
Another common subexpression comes to light in B5 after £4 replaces t8. The new expression a [£4] corresponds to the value of a[j] at the source level. Not only does j retain its value as control leaves B3 and then enters f?5, but a[j], a value computed into a temporary £5, does too, because there are no assignments to elements of the array a in the interim. The statements
t 9 = a [ t 4]
a [ t 6 ] = t9
in j?5 therefore can be replaced by
a [ t 6 ] = t5
Analogously, the value assigned to x in block B5 of Fig. 9.4(b) is seen to be the same as the value assigned to t3 in block B2. Block B5 in Fig. 9.5 is the result of eliminating common subexpressions corresponding to the values of the source level expressions a[i] and a[j] from B5 in Fig. 9.4(b). A similar series of transformations has been done to BQ in Fig. 9.5.
The expression a[tl] in blocks B\ and BQ of Fig. 9.5 is not considered a common subexpression, although tl can be used in both places. After control leaves B\ and before it reaches BQ, it can go through B5, where there are assignments to a. Hence, a[tl] may not have the same value on reaching BQ as it did on leaving B\, and it is not safe to treat a[tl] as a common subexpression.