cs3 8.4 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250
  1. .NH 2
  2. Implementation
  3. .PP
  4. .NH 3
  5. The value number method
  6. .PP
  7. To determine whether two expressions have the same result,
  8. there must be some way to determine whether their operands have
  9. the same values.
  10. We use a system of \fIvalue numbers\fP
  11. .[
  12. kennedy data flow analysis
  13. .]
  14. in which each distinct value of whatever type,
  15. created or used within the working window,
  16. receives a unique identifying number, its value number.
  17. Two items have the same value number if and only if,
  18. based only upon information from the instructions in the window,
  19. their values are provably identical.
  20. For example, after processing the statement
  21. .DS
  22. a := 4;
  23. .DE
  24. the variable a and the constant 4 have the same value number.
  25. .PP
  26. The value number of the result of an expression depends only
  27. on the kind of operator and the value number(s) of the operand(s).
  28. The expressions need not be textually equal, as shown in Fig. 7.5.
  29. .DS
  30. .TS
  31. l l.
  32. a := c; (1)
  33. use(a * b); (2)
  34. d := b; (3)
  35. use(c * d); (4)
  36. .TE
  37. Fig. 7.5 Different expressions with the same value number
  38. .DE
  39. At line (1) a receives the same value number as c.
  40. At line (2) d receives the same value number as b.
  41. At line (4) the expression "c * d" receives the same value number
  42. as the expression "a * b" at line (2),
  43. because the value numbers of their left and right operands are the same,
  44. and the operator (*) is the same.
  45. .PP
  46. As another example of the value number method, consider Fig. 7.6.
  47. .DS
  48. .TS
  49. l l.
  50. use(a * b); (1)
  51. a := 123; (2)
  52. use(a * b); (3)
  53. .TE
  54. Fig. 7.6 Identical expressions with the different value numbers
  55. .DE
  56. Although textually the expressions "a * b" in line 1 and line 3 are equal,
  57. a will have different value numbers at line 3 and line 1.
  58. The two expressions will not mistakenly be recognized as equivalent.
  59. .NH 3
  60. Entities
  61. .PP
  62. The Value Number Method distinguishes between operators and operands.
  63. The value numbers of operands are stored in a table,
  64. called the \fIsymbol table\fR.
  65. The value number of a subexpression depends on the
  66. (root) operator of the expression and on the value numbers
  67. of its operands.
  68. A table of "available expressions" is used to do this mapping.
  69. .PP
  70. CS recognizes the following kinds of EM operands, called \fIentities\fR:
  71. .DS
  72. - constant
  73. - local variable
  74. - external variable
  75. - indirectly accessed entity
  76. - offsetted entity
  77. - address of local variable
  78. - address of external variable
  79. - address of offsetted entity
  80. - address of local base
  81. - address of argument base
  82. - array element
  83. - procedure identifier
  84. - floating zero
  85. - local base
  86. - heap pointer
  87. - ignore mask
  88. .DE
  89. .LP
  90. Whenever a new entity is encountered in the working window,
  91. it is entered in the symbol table and given a brand new value number.
  92. Most entities have attributes (e.g. the offset in
  93. the current stackframe for local variables),
  94. which are also stored in the symbol table.
  95. .PP
  96. An entity is called static if its value cannot be changed
  97. (e.g. a constant or an address).
  98. .NH 3
  99. Parsing expressions
  100. .PP
  101. Common subexpressions are recognized by simulating the behaviour
  102. of the EM machine.
  103. The EM code is parsed from left to right;
  104. as EM is postfix code, this is a bottom up parse.
  105. At any point the current state of the EM runtime stack is
  106. reflected by a simulated "fake stack",
  107. containing descriptions of the parsed operands and expressions.
  108. A descriptor consists of:
  109. .DS
  110. (1) the value number of the operand or expression
  111. (2) the size of the operand or expression
  112. (3) a pointer to the first line of EM-code
  113. that constitutes the operand or expression
  114. .DE
  115. Note that operands may consist of several EM instructions.
  116. Whenever an operator is encountered, the
  117. descriptors of its operands are on top of the fake stack.
  118. The operator and the value numbers of the operands
  119. are used as indices in the table of available expressions,
  120. to determine the value number of the expression.
  121. .PP
  122. During the parsing process,
  123. we keep track of the first line of each expression;
  124. we need this information when we decide to eliminate the expression.
  125. .NH 3
  126. Updating entities
  127. .PP
  128. An entity is assigned a value number when it is
  129. used for the first time
  130. in the working window.
  131. If the entity is used as left hand side of an assignment,
  132. it gets the value number of the right hand side.
  133. Sometimes the effects of an instruction on an entity cannot
  134. be determined exactly;
  135. the current value and value number of the entity may become
  136. inconsistent.
  137. Hence the current value number must be forgotten.
  138. This is achieved by giving the entity a new value number
  139. that was not used before.
  140. The entity is said to be \fIkilled\fR.
  141. .PP
  142. As information is lost when an entity is killed,
  143. CS tries to save as many entities as possible.
  144. In case of an indirect assignment through a pointer,
  145. some analysis is done to see which variables cannot be altered.
  146. For a procedure call, the interprocedural information contained
  147. in the procedure table is used to restrict the set of entities that may
  148. be changed by the call.
  149. Local variables for which the front end generated
  150. a register message can never be changed by an indirect assignment
  151. or a procedure call.
  152. .NH 3
  153. Changing the EM text
  154. .PP
  155. When a new expression comes available,
  156. it is checked whether its result is saved in a local
  157. that may go in a register.
  158. The last line of the expression must be followed
  159. by a STL or SDL instruction
  160. (depending on the size of the result)
  161. and a register message must be present for
  162. this local.
  163. If there is such a local,
  164. it is recorded in the available expressions table.
  165. Each time a new occurrence of this expression
  166. is found,
  167. the value number of the local is compared against
  168. the value number of the result.
  169. If they are different the local cannot be used and is forgotten.
  170. .PP
  171. The available expressions are linked in a list.
  172. New expressions are linked at the head of the list.
  173. In this way expressions that are contained within other
  174. expressions appear later in the list,
  175. because EM-expressions are postfix.
  176. The elimination process walks through the list,
  177. starting at the head, to find the largest expressions first.
  178. If an expression is eliminated,
  179. any expression later on in the list, contained in the former expression,
  180. is removed from the list,
  181. as expressions can only be eliminated once.
  182. .PP
  183. A STL or SDL is emitted after the first occurrence of the expression,
  184. unless there was an existing local variable that could hold the result.
  185. .NH 3
  186. Desirability analysis
  187. .PP
  188. Although the global optimizer works on EM code,
  189. the goal is to improve the quality of the object code.
  190. Therefore some machine-dependent information is needed
  191. to decide whether it is desirable to
  192. eliminate a given expression.
  193. Because it is impossible for the CS phase to know
  194. exactly what code will be generated,
  195. some heuristics are used.
  196. CS essentially looks for some special cases
  197. that should not be eliminated.
  198. These special cases can be turned on or off for a given machine,
  199. as indicated in a machine descriptor file.
  200. .PP
  201. Some operators can sometimes be translated
  202. into an addressing mode for the machine at hand.
  203. Such an operator is only eliminated
  204. if its operand is itself expensive,
  205. i.e. it is not just a simple load.
  206. The machine descriptor file contains a set of such operators.
  207. .PP
  208. Eliminating the loading of the Local Base or
  209. the Argument Base by the LXL resp. LXA instruction
  210. is only beneficial if the difference in lexical levels
  211. exceeds a certain threshold.
  212. The machine descriptor file contains this threshold.
  213. .PP
  214. Replacing a SAR or a LAR by an AAR followed by a LOI
  215. may possibly increase the size of the object code.
  216. We assume that this is only possible when the
  217. size of the array element is greater than some limit.
  218. .PP
  219. There are back ends that can very efficiently translate
  220. the index computing instruction sequence LOC SLI ADS.
  221. If this is the case,
  222. the SLI instruction between a LOC
  223. and an ADS is not eliminated.
  224. .PP
  225. To handle unforseen cases, the descriptor file may also contain
  226. a set of operators that should never be eliminated.
  227. .NH 3
  228. The algorithm
  229. .PP
  230. After these preparatory explanations,
  231. the algorithm itself is easy to understand.
  232. For each instruction within the current window,
  233. the following steps are performed in the given order :
  234. .IP 1.
  235. Check if this instruction defines an entity.
  236. If so, the set of entities is updated accordingly.
  237. .IP 2.
  238. Kill all entities that might be affected by this instruction.
  239. .IP 3.
  240. Simulate the instruction on the fake-stack.
  241. If this instruction is an operator,
  242. update the list of available expressions accordingly.
  243. .PP
  244. The result of this process is
  245. a list of available expressions plus the information
  246. needed to eliminate them.
  247. Expressions that are desirable to eliminate are eliminated.
  248. Next, the window is shifted and the process is repeated.