home *** CD-ROM | disk | FTP | other *** search
/ minnie.tuhs.org / unixen.tar / unixen / PDP-11 / Trees / V7 / usr / doc / ctour / cdoc4 < prev   
Encoding:
Text File  |  1979-01-10  |  3.8 KB  |  164 lines
  1. .SH
  2. Delaying and reordering
  3. .PP
  4. Intertwined with the code generation routines are two other,
  5. interrelated processes.
  6. The first, implemented by a routine called
  7. .II delay,
  8. is based on the observation that
  9. naive code generation for the expression
  10. `a = b++' would produce
  11. .DS
  12. mov    b,r0
  13. inc    b
  14. mov    r0,a
  15. .DE
  16. The point is that the table for postfix ++ has to preserve
  17. the value of
  18. .II b
  19. before incrementing it;
  20. the general way to do this is to preserve its value in a register.
  21. A cleverer scheme would generate
  22. .DS
  23. mov    b,a
  24. inc    b
  25. .DE
  26. .II Delay
  27. is called for each expression input to
  28. .II rcexpr,
  29. and it searches for postfix ++ and \-\-
  30. operators.
  31. If one is found applied to a variable,
  32. the tree is patched to bypass the operator
  33. and compiled as it stands;
  34. then the increment or decrement itself is done.
  35. The effect is as if `a = b; b++' had been written.
  36. In this example, of course, the user himself could have done the same job,
  37. but more complicated examples are easily constructed, for example
  38. `switch (x++)'.
  39. An essential restriction is that the condition codes not
  40. be required.
  41. It would be incorrect to compile
  42. `if (a++) ...'
  43. as
  44. .DS
  45. tst    a
  46. inc    a
  47. beq    ...
  48. .DE
  49. because the `inc' destroys the required setting of the condition codes.
  50. .PP
  51. Reordering is a similar sort of optimization.
  52. Many cases which it detects are useful
  53. mainly with register variables.
  54. If
  55. .II r
  56. is a register variable,
  57. the expression `r = x+y' is best compiled
  58. as
  59. .DS
  60. mov    x,r
  61. add    y,r
  62. .DE
  63. but the codes tables would produce
  64. .DS
  65. mov    x,r0
  66. add    y,r0
  67. mov    r0,r
  68. .DE
  69. which is in fact preferred if
  70. .II r
  71. is not a register.
  72. (If
  73. .II r
  74. is not a register,
  75. the
  76. two sequences are the same size, but the
  77. second is slightly faster.)
  78. The scheme is to compile the expression as if it had been written
  79. `r = x; r =+ y'.
  80. The
  81. .II reorder
  82. routine
  83. is called with a pointer to each tree that
  84. .II rcexpr
  85. is about to compile;
  86. if it has the right characteristics,
  87. the `r = x' tree is constructed and passed recursively
  88. to
  89. .II rcexpr;
  90. then the original tree is modified to read `r =+ y'
  91. and the calling instance of
  92. .II rcexpr
  93. compiles that instead.
  94. Of course the whole business is itself recursive
  95. so that more extended forms of the same phenomenon are
  96. handled, like `r = x + y | z'.
  97. .PP
  98. Care does have to be taken
  99. to avoid `optimizing' an expression like `r = x + r'
  100. into `r = x; r =+ r'.
  101. It is required that the right operand of the expression on the right
  102. of the `=' be a ', distinct from the register variable.
  103. .PP
  104. The second case that
  105. .II reorder
  106. handles is expressions of the form `r = X' used as a subexpression.
  107. Again, the code out of the tables for
  108. `x = r = y'
  109. would be
  110. .DS
  111. mov    y,r0
  112. mov    r0,r
  113. mov    r0,x
  114. .DE
  115. whereas if
  116. .II r
  117. were a register it would be better to produce
  118. .DS
  119. mov    y,r
  120. mov    r,x
  121. .DE
  122. When
  123. .II reorder
  124. discovers that
  125. a register variable is being assigned to
  126. in a subexpression,
  127. it calls
  128. .II rcexpr
  129. recursively to
  130. compile the subexpression, then fiddles the tree passed
  131. to it so that the register variable itself appears
  132. as the operand instead of the whole subexpression.
  133. Here care has to be taken to avoid an infinite regress,
  134. with
  135. .II rcexpr
  136. and
  137. .II reorder
  138. calling each other forever to handle assignments to registers.
  139. .PP
  140. A third set of cases treated by
  141. .II reorder
  142. comes up when any name, not necessarily a register,
  143. occurs as a left operand of an assignment operator other than `='
  144. or as an operand of prefix `++' or `\-\-'.
  145. Unless condition-code tests are involved,
  146. when a subexpression like `(a =+ b)' is seen,
  147. the assignment is performed and the argument tree
  148. modified so that
  149. .II a
  150. is its operand;
  151. effectively
  152. `x + (y =+ z)' is compiled as `y =+ z; x + y'.
  153. Similarly, prefix increment and decrement are pulled out
  154. and performed first, then the remainder of the expression.
  155. .PP
  156. Throughout code generation,
  157. the expression optimizer is called whenever
  158. .II delay
  159. or
  160. .II reorder
  161. change the expression tree.
  162. This allows some special cases to be found that otherwise
  163. would not be seen.
  164.