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