doc/ego/cs/cs2

   1 .NH 2
   2 Specification of the Common Subexpression Elimination phase
   3 .PP
   4 In this section we will describe
   5 the window
   6 through which CS examines the code,
   7 the expressions recognized by CS,
   8 and finally the changes made to the code.
   9 .NH 3
  10 The working window
  11 .PP
  12 The CS algorithm is applied to the
  13 largest sequence of textually adjacent basic blocks
  14 B1,..,Bn, for which
  15 .DS
  16 PRED(Bj) = {Bj-1},  j = 2,..,n.
  17 .DE
  18 Intuitively, this window consists of straight line code,
  19 with only one entry point (at the beginning); it may
  20 contain jumps, which should all have their targets outside the window.
  21 This is illustrated in Fig. 7.2.
  22 .DS
  23 x := a * b;     (1)
  24 if x < 10 then  (2)
  25     y := a * b; (3)
  26
  27 Fig. 7.2 The working window of CS
  28 .DE
  29 Line (2) can only be executed after line (1).
  30 Likewise, line (3) can only be executed after
  31 line (2).
  32 Both a and b have the same values at line (1) and at line (3).
  33 .PP
  34 Larger windows were avoided.
  35 In Fig. 7.3, the value of a at line (4) may have been obtained
  36 at more than one point.
  37 .DS
  38 x := a * b;     (1)
  39 if x < 10 then  (2)
  40     a := 100;   (3)
  41 y := a * b;     (4)
  42
  43 Fig. 7.3 Several working windows
  44 .DE
  45 .NH 3
  46 Recognized expressions.
  47 .PP
  48 The computations eliminated by CS need not be normal expressions
  49 (like "a * b"),
  50 but can even consist of a single operand that is expensive to access,
  51 such as an array element or a record field.
  52 If an array element is used,
  53 its address is computed implicitly.
  54 CS is able to eliminate either the element itself or its
  55 address, whichever one is most profitable.
  56 A variable of a textually enclosing procedure may also be
  57 expensive to access, depending on the lexical level difference.
  58 .NH 3
  59 Transformations
  60 .PP
  61 CS creates a new temporary local variable (TMP)
  62 for every eliminated expression,
  63 unless it is able to use an existing local variable.
  64 It emits code to initialize this variable with the
  65 result of the expression.
  66 Most recurrences of the expression
  67 can simply be replaced by a reference to TMP.
  68 If the address of an array element is recognized as
  69 a common subexpression,
  70 references to the element itself are replaced by
  71 indirect references through TMP (see Fig. 7.4).
  72 .DS
  73 .TS
  74 l l l.
  75 x := A[i];              TMP := &A[i];
  76   . . . -->     x := *TMP;
  77 A[i] := y;                 . . .
  78                         *TMP := y;
  79 .TE
  80
  81 Fig. 7.4 Elimination of an array address computation
  82 .DE
  83 Here, '&' is the 'address of' operator,
  84 and unary '*' is the indirection operator.
  85 (Note that EM actually has different instructions to do
  86 a use-indirect or an assign-indirect.)