cs2 2.4 KB

1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283848586
  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. Fig. 7.2 The working window of CS
  27. .DE
  28. Line (2) can only be executed after line (1).
  29. Likewise, line (3) can only be executed after
  30. line (2).
  31. Both a and b have the same values at line (1) and at line (3).
  32. .PP
  33. Larger windows were avoided.
  34. In Fig. 7.3, the value of a at line (4) may have been obtained
  35. at more than one point.
  36. .DS
  37. x := a * b; (1)
  38. if x < 10 then (2)
  39. a := 100; (3)
  40. y := a * b; (4)
  41. Fig. 7.3 Several working windows
  42. .DE
  43. .NH 3
  44. Recognized expressions.
  45. .PP
  46. The computations eliminated by CS need not be normal expressions
  47. (like "a * b"),
  48. but can even consist of a single operand that is expensive to access,
  49. such as an array element or a record field.
  50. If an array element is used,
  51. its address is computed implicitly.
  52. CS is able to eliminate either the element itself or its
  53. address, whichever one is most profitable.
  54. A variable of a textually enclosing procedure may also be
  55. expensive to access, depending on the lexical level difference.
  56. .NH 3
  57. Transformations
  58. .PP
  59. CS creates a new temporary local variable (TMP)
  60. for every eliminated expression,
  61. unless it is able to use an existing local variable.
  62. It emits code to initialize this variable with the
  63. result of the expression.
  64. Most recurrences of the expression
  65. can simply be replaced by a reference to TMP.
  66. If the address of an array element is recognized as
  67. a common subexpression,
  68. references to the element itself are replaced by
  69. indirect references through TMP (see Fig. 7.4).
  70. .DS
  71. .TS
  72. l l l.
  73. x := A[i]; TMP := &A[i];
  74. . . . --> x := *TMP;
  75. A[i] := y; . . .
  76. *TMP := y;
  77. .TE
  78. Fig. 7.4 Elimination of an array address computation
  79. .DE
  80. Here, '&' is the 'address of' operator,
  81. and unary '*' is the indirection operator.
  82. (Note that EM actually has different instructions to do
  83. a use-indirect or an assign-indirect.)