.NH 2 Specification of the Common Subexpression Elimination phase .PP In this section we will describe the window through which CS examines the code, the expressions recognized by CS, and finally the changes made to the code. .NH 3 The working window .PP The CS algorithm is applied to the largest sequence of textually adjacent basic blocks B1,..,Bn, for which .DS PRED(Bj) = {Bj-1}, j = 2,..,n. .DE Intuitively, this window consists of straight line code, with only one entry point (at the beginning); it may contain jumps, which should all have their targets outside the window. This is illustrated in Fig. 7.2. .DS x := a * b; (1) if x < 10 then (2) y := a * b; (3) Fig. 7.2 The working window of CS .DE Line (2) can only be executed after line (1). Likewise, line (3) can only be executed after line (2). Both a and b have the same values at line (1) and at line (3). .PP Larger windows were avoided. In Fig. 7.3, the value of a at line (4) may have been obtained at more than one point. .DS x := a * b; (1) if x < 10 then (2) a := 100; (3) y := a * b; (4) Fig. 7.3 Several working windows .DE .NH 3 Recognized expressions. .PP The computations eliminated by CS need not be normal expressions (like "a * b"), but can even consist of a single operand that is expensive to access, such as an array element or a record field. If an array element is used, its address is computed implicitly. CS is able to eliminate either the element itself or its address, whichever one is most profitable. A variable of a textually enclosing procedure may also be expensive to access, depending on the lexical level difference. .NH 3 Transformations .PP CS creates a new temporary local variable (TMP) for every eliminated expression, unless it is able to use an existing local variable. It emits code to initialize this variable with the result of the expression. Most recurrences of the expression can simply be replaced by a reference to TMP. If the address of an array element is recognized as a common subexpression, references to the element itself are replaced by indirect references through TMP (see Fig. 7.4). .DS .TS l l l. x := A[i]; TMP := &A[i]; . . . --> x := *TMP; A[i] := y; . . . *TMP := y; .TE Fig. 7.4 Elimination of an array address computation .DE Here, '&' is the 'address of' operator, and unary '*' is the indirection operator. (Note that EM actually has different instructions to do a use-indirect or an assign-indirect.)