home *** CD-ROM | disk | FTP | other *** search
/ minnie.tuhs.org / unixen.tar / unixen / PDP-11 / Trees / V7 / usr / doc / ctour / cdoc2 < prev    next >
Encoding:
Text File  |  1979-01-10  |  5.3 KB  |  201 lines

  1. .SH
  2. Expression Optimization
  3. .PP
  4. Each expression tree, as it is read in, is subjected to
  5. a fairly comprehensive
  6. analysis.
  7. This is performed
  8. by the
  9. .II optim
  10. routine and a number of subroutines;
  11. the major things done are
  12. .IP 1.
  13. Modifications and simplifications
  14. of the tree so its value may be computed more efficiently
  15. and conveniently by the code generator.
  16. .RT
  17. .IP 2.
  18. Marking each interior node with an estimate of the number of
  19. registers required to evaluate it.
  20. This register count is needed to guide the code generation algorithm.
  21. .PP
  22. One thing that is definitely not done is
  23. discovery or exploitation of common subexpressions, nor is this done anywhere in the
  24. compiler.
  25. .PP
  26. The basic organization is simple: a depth-first scan of the tree.
  27. .II Optim
  28. does nothing for leaf nodes (except for automatics; see below),
  29. and calls
  30. .II unoptim
  31. to handle unary operators.
  32. For binary operators,
  33. it calls itself to process the operands,
  34. then treats each operator separately.
  35. One important case is
  36. commutative and associative operators, which are handled
  37. by
  38. .II acommute.
  39. .PP
  40. Here is a brief catalog of the transformations carried out by
  41. by
  42. .II optim
  43. itself.
  44. It is not intended to be complete.
  45. Some of the transformations are machine-dependent,
  46. although they may well be useful on machines other than the
  47. PDP-11.
  48. .IP 1.
  49. As indicated in the discussion of
  50. .II unoptim
  51. below, the optimizer can create a node type corresponding
  52. to the location addressed by a register plus a constant offset.
  53. Since this is precisely the implementation of automatic variables
  54. and arguments, where the register is fixed by convention,
  55. such variables are changed to the new form to simplify
  56. later processing.
  57. .RT
  58. .IP 2.
  59. Associative and commutative operators are processed by the
  60. special routine
  61. .II acommute.
  62. .RT
  63. .IP 3.
  64. After processing by
  65. .II acommute,
  66. the bitwise & operator is turned into a new
  67. .II andn
  68. operator; `a & b' becomes
  69. `a
  70. .II andn
  71. ~b'.
  72. This is done because the PDP-11 provides
  73. no
  74. .II and
  75. operator, but only
  76. .II andn.
  77. A similar transformation takes place for
  78. `=&'.
  79. .RT
  80. .IP 4.
  81. Relationals are turned around so the
  82. more complicated expression is on the left.
  83. (So that `2 > f(x)' becomes `f(x) < 2').
  84. This improves code generation since
  85. the algorithm prefers to have the right operand
  86. require fewer registers than the left.
  87. .RT
  88. .IP 5.
  89. An expression minus a constant is turned into
  90. the expression plus the negative constant,
  91. and the
  92. .II acommute
  93. routine is called
  94. to take advantage of the properties of addition.
  95. .RT
  96. .IP 6.
  97. Operators with constant operands are evaluated.
  98. .RT
  99. .IP 7.
  100. Right shifts (unless by 1)
  101. are turned into left shifts with a negated right operand,
  102. since the PDP-11 lacks a general right-shift operator.
  103. .RT
  104. .IP 8.
  105. A number of special cases are simplified, such as division or
  106. multiplication by 1,
  107. and shifts by 0.
  108. .LP
  109. The
  110. .II unoptim
  111. routine performs the same sort of processing for unary operators.
  112. .IP 1.
  113. `*&x' and `&*x' are simplified to `x'.
  114. .RT
  115. .IP 2.
  116. If
  117. .II r
  118. is a register and
  119. .II c
  120. is a constant or the address of a static or external
  121. variable,
  122. the expressions `*(r+c)'
  123. and `*r' are turned into a special kind of name node
  124. which expresses
  125. the name itself and the offset.
  126. This simplifies subsequent processing
  127. because such constructions can appear as
  128. the the address of a PDP-11 instruction.
  129. .RT
  130. .IP 3.
  131. When the unary `&' operator is applied to
  132. a name node of the special kind just discussed,
  133. it is reworked to make the addition
  134. explicit again;
  135. this is done because the PDP-11 has no `load address' instruction.
  136. .RT
  137. .IP 4.
  138. Constructions
  139. like
  140. `*r++' and
  141. `*\-\-r'
  142. where
  143. .II r
  144. is a register are discovered and marked
  145. as being implementable using the PDP-11
  146. auto-increment and -decrement modes.
  147. .RT
  148. .IP 5.
  149. If `!' is applied to a relational,
  150. the `!' is discarded
  151. and the sense of the relational is reversed.
  152. .RT
  153. .IP 6.
  154. Special cases involving reflexive
  155. use of negation and complementation are discovered.
  156. .RT
  157. .IP 7.
  158. Operations applying to constants are evaluated.
  159. .PP
  160. The
  161. .II acommute
  162. routine, called for associative and commutative operators,
  163. discovers clusters of the same operator at the top levels
  164. of the current tree, and arranges them in a list:
  165. for `a+((b+c)+(d+f))'
  166. the list would be`a,b,c,d,e,f'.
  167. After each subtree is optimized, the list is sorted in
  168. decreasing difficulty of computation;
  169. as mentioned above,
  170. the code generation algorithm works best when left operands
  171. are the difficult ones.
  172. The `degree of difficulty'
  173. computed is actually finer than
  174. the mere number of registers required;
  175. a constant is considered simpler
  176. than the address of a static or external, which is simpler
  177. than reference to a variable.
  178. This makes it easy to fold all the constants
  179. together,
  180. and also to merge together the sum of a constant and the address of
  181. a static
  182. or external (since in such nodes there is space for
  183. an `offset' value).
  184. There are also special cases, like multiplication by 1 and addition of 0.
  185. .II
  186. A special routine is invoked to handle sums of products.
  187. .II Distrib
  188. is based on the fact that it is better
  189. to compute `c1*c2*x + c1*y' as `c1*(c2*x + y)'
  190. and makes the divisibility tests required to assure the
  191. correctness of the transformation.
  192. This transformation is rarely
  193. possible with code directly written by the user,
  194. but it invariably occurs as a result of the
  195. implementation of multi-dimensional arrays.
  196. .PP
  197. Finally,
  198. .II acommute
  199. reconstructs a tree from the list
  200. of expressions which result.
  201.