ra3 14 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386
  1. .NH 2
  2. The register allocation phase
  3. .PP
  4. .NH 3
  5. Overview
  6. .PP
  7. The RA phase deals with one procedure at a time.
  8. For every procedure, it first determines which entities
  9. may be put in a register. Such an entity
  10. is called an \fIitem\fR.
  11. For every item it decides during which parts of the procedure it
  12. might be assigned a register.
  13. Such a region is called a \fItimespan\fR.
  14. For any item, several (possibly overlapping) timespans may
  15. be considered.
  16. A pair (item,timespan) is called an \fIallocation\fR.
  17. If the items of two allocations are both live at some
  18. point of time in the intersections of their timespans,
  19. these allocations are said to be \fIrivals\fR of each other,
  20. as they cannot be assigned the same register.
  21. The rivals-set of every allocation is computed.
  22. Next, the gains of assigning a register to an allocation are estimated,
  23. for every allocation.
  24. With all this information, decisions are made which allocations
  25. to store in which registers (\fIpacking\fR).
  26. Finally, the EM text is transformed to reflect these decisions.
  27. .NH 3
  28. The item recognition subphase
  29. .PP
  30. RA tries to put the following entities in a register:
  31. .IP -
  32. a local variable for which a register message was found
  33. .IP -
  34. the address of a local variable for which no
  35. register message was found
  36. .IP -
  37. the address of a global variable
  38. .IP -
  39. the address of a procedure
  40. .IP -
  41. a numeric constant.
  42. .LP
  43. Only the \fIaddress\fR of a global variable
  44. may be put in a register, not the variable itself.
  45. This approach avoids the very complex problems that would be
  46. caused by procedure calls and indirect pointer references (see
  47. .[~[
  48. aho design compiler
  49. .] sections 14.7 and 14.8]
  50. and
  51. .[~[
  52. spillman side-effects
  53. .]]).
  54. Still, on most machines accessing a global variable using indirect
  55. addressing through a register is much cheaper than
  56. accessing it via its address.
  57. Similarly, if the address of a procedure is put in a register, the
  58. procedure can be called via an indirect call.
  59. .PP
  60. With every item we associate a register type.
  61. This type is
  62. .DS
  63. for local variables: the type contained in the register message
  64. for addresses of variables and procedures: the pointer type
  65. for constants: the general type
  66. .DE
  67. An entity other than a local variable is not taken to be an item
  68. if it is used only once within the current procedure.
  69. .PP
  70. An item is said to be \fIlive\fR at some point of the program text
  71. if its value may be used before it is changed.
  72. As addresses and constants are never changed, all items but local
  73. variables are always live.
  74. The region of text during which a local variable is live is
  75. determined via the live/dead messages generated by the
  76. Live Variable analysis phase of the Global Optimizer.
  77. .NH 3
  78. The allocation determination subphase
  79. .PP
  80. If a procedure has more items than registers,
  81. it may be advantageous to put an item in a register
  82. only during those parts of the procedure where it is most
  83. heavily used.
  84. Such a part will be called a timespan.
  85. With every item we may associate a set of timespans.
  86. If two timespans of an item overlap,
  87. at most one of them may be granted a register,
  88. as there is no use in putting the same item in two
  89. registers simultaneously.
  90. If two timespans of an item are distinct,
  91. both may be chosen;
  92. the item will possibly be put in two
  93. different registers during different parts of the procedure.
  94. The timespan may also consist
  95. of the whole procedure.
  96. .PP
  97. A list of (item,timespan) pairs (allocations)
  98. is build, which will be the input to the decision making
  99. subphase of RA (packing subphase).
  100. This allocation list is the main data structure of RA.
  101. The description of the remainder of RA will be in terms
  102. of allocations rather than items.
  103. The phrase "to assign a register to an allocation" means "to assign
  104. a register to the item of the allocation for the duration of
  105. the timespan of the allocation".
  106. Subsequent subphases will add more information
  107. to this list.
  108. .PP
  109. Several factors must be taken into account when a
  110. timespan for an item is constructed:
  111. .IP 1.
  112. At any \fIentry point\fR of the timespan where the
  113. item is live,
  114. the register must be initialized with the item
  115. .IP 2.
  116. At any exit point of the timespan where the item is live,
  117. the item must be updated.
  118. .LP
  119. In order to decrease these costs, we will only consider timespans with
  120. one entry point
  121. and no live exit points.
  122. .NH 3
  123. The rivals computation subphase
  124. .PP
  125. As stated before, several different items may be put in the
  126. same register, provided they are not live simultaneously.
  127. For every allocation we determine the intersection
  128. of its timespan and the lifetime of its item (i.e. the part of the
  129. procedure during which the item is live).
  130. The allocation is said to be busy during this intersection.
  131. If two allocations are ever busy simultaneously they are
  132. said to be rivals of each other.
  133. The rivals information is added to the allocation list.
  134. .NH 3
  135. The profits computation subphase
  136. .PP
  137. To make good decisions, the packing subphase needs to
  138. know which allocations can be assigned the same register
  139. (rivals information) and how much is gained by
  140. granting an allocation a register.
  141. .PP
  142. Besides the gains of using a register instead of an
  143. item,
  144. two kinds of overhead costs must be
  145. taken into account:
  146. .IP -
  147. the register must be initialized with the item
  148. .IP -
  149. the register must be saved at procedure entry
  150. and restored at procedure exit.
  151. .LP
  152. The latter costs should not be due to a single
  153. allocation, as several allocations can be assigned the same register.
  154. These costs are dealt with after packing has been done.
  155. They do not influence the decisions of the packing algorithm,
  156. they may only undo them.
  157. .PP
  158. The actual profits consist of improvements
  159. of execution time and code size.
  160. As the former is far more difficult to estimate , we will
  161. discuss code size improvements first.
  162. .PP
  163. The gains of putting a certain item in a register
  164. depends on how the item is used.
  165. Suppose the item is
  166. a pointer variable.
  167. On machines that do not have a
  168. double-indirect addressing mode,
  169. two instructions are needed to dereference the variable
  170. if it is not in a register, but only one if it is put in a register.
  171. If the variable is not dereferenced, but simply copied, one instruction
  172. may be sufficient in both cases.
  173. So the gains of putting a pointer variable in a register are higher
  174. if the variable is dereferenced often.
  175. .PP
  176. To make accurate estimates, detailed knowledge of
  177. the target machine and of the code generator
  178. would be needed.
  179. Therefore, a simplification has been made that substantially limits
  180. the amount of target machine information that is needed.
  181. The estimation of the number of bytes saved does
  182. not take into account how an item is used.
  183. Rather, an average number is used.
  184. So these gains are computed as follows:
  185. .DS
  186. #bytes_saved = #occurrences * gains_per_occurrence
  187. .DE
  188. The number of occurrences is derived from
  189. the EM code.
  190. Note that this is not exact either,
  191. as there is no one-to-one correspondence between occurrences in
  192. the EM code and in the assembler code.
  193. .PP
  194. The gains of one occurrence depend on:
  195. .IP 1.
  196. the type of the item
  197. .IP 2.
  198. the size of the item
  199. .IP 3.
  200. the type of the register
  201. .LP
  202. and for local variables and addresses of local variables:
  203. .IP 4.
  204. the type of the local variable
  205. .IP 5.
  206. the offset of the variable in the stackframe
  207. .LP
  208. For every allocation we try two types of registers: the register type
  209. of the item and the general register type.
  210. Only the type with the highest profits will subsequently be used.
  211. This type is added to the allocation information.
  212. .PP
  213. To compute the gains, RA uses a machine-dependent table
  214. that is read from a machine descriptor file.
  215. By means of this table the number of bytes saved can be computed
  216. as a function of the five properties.
  217. .PP
  218. The costs of initializing a register with an item
  219. is determined in a similar way.
  220. The cost of one initialization is also
  221. obtained from the descriptor file.
  222. Note that there can be at most one initialization for any
  223. allocation.
  224. .PP
  225. To summarize, the number of bytes a certain allocation would
  226. save is computed as follows:
  227. .DS
  228. .TS
  229. l l.
  230. net_bytes_saved = bytes_saved - init_cost
  231. bytes_saved = #occurrences * gains_per_occ
  232. init_cost = #initializations * costs_per_init
  233. .TE
  234. .DE
  235. .PP
  236. It is inherently more difficult to estimate the execution
  237. time saved by putting an item in a register,
  238. because it is impossible to predict how
  239. many times an item will be used dynamically.
  240. If an occurrence is part of a loop,
  241. it may be executed many times.
  242. If it is part of a conditional statement,
  243. it may never be executed at all.
  244. In the latter case, the speed of the program may even get
  245. worse if an initialization is needed.
  246. As a clear example, consider the piece of "C" code in Fig. 13.1.
  247. .DS
  248. switch(expr) {
  249. case 1: p(); break;
  250. case 2: p(); p(); break;
  251. case 3: p(); break;
  252. default: break;
  253. }
  254. Fig. 13.1 A "C" switch statement
  255. .DE
  256. Lots of bytes may be saved by putting the address of procedure p
  257. in a register, as p is called four times (statically).
  258. Dynamically, p will be called zero, one or two times,
  259. depending on the value of the expression.
  260. .PP
  261. The optimizer uses the following strategy for optimizing
  262. execution time:
  263. .IP 1.
  264. try to put items in registers during \fIloops\fR first
  265. .IP 2.
  266. always keep the initializing code outside the loop
  267. .IP 3.
  268. if an item is not used in a loop, do not put it in a register if
  269. the initialization costs may be higher than the gains
  270. .LP
  271. The latter condition can be checked by determining the
  272. minimal number of usages (dynamically) of the item during the procedure,
  273. via a shortest path algorithm.
  274. In the example above, this minimal number is zero, so the address of
  275. p is not put in a register.
  276. .PP
  277. The costs of one occurrence is estimated as described above for the
  278. code size.
  279. The number of dynamic occurrences is guessed by looking at the
  280. loop nesting level of every occurrence.
  281. If the item is never used in a loop,
  282. the minimal number of occurrences is used.
  283. From these facts, the execution time improvement is assessed
  284. for every allocation.
  285. .NH 3
  286. The packing subphase
  287. .PP
  288. The packing subphase takes as input the allocation
  289. list and outputs a
  290. description of which allocations should be put
  291. in which registers.
  292. So it is essentially the decision making part of RA.
  293. .PP
  294. The packing system tries to assign a register to allocations one
  295. at a time, in some yet to be defined order.
  296. For every allocation A, it first checks if there is a register
  297. (of the right type)
  298. that is already assigned to one or more allocations,
  299. none of which are rivals of A.
  300. In this case A is assigned the same register.
  301. Else, A is assigned a new register, if one exists.
  302. A table containing the number of free registers for every type
  303. is maintained.
  304. It is initialized with the number of non-scratch registers of
  305. the target computer and updated whenever a
  306. new register is handed out.
  307. The packing algorithm stops when no more allocations can
  308. or need be assigned a register.
  309. .PP
  310. After an allocation A has been packed,
  311. all allocations with non-disjunct timespans (including
  312. A itself) are removed from the allocation list.
  313. .PP
  314. In case the number of items exceeds the number of registers, it
  315. is important to choose the most profitable allocations.
  316. Due to the possibility of having several allocations
  317. occupying the same register,
  318. this problem is quite complex.
  319. Our packing algorithm uses simple heuristic rules
  320. and avoids any combinatorial search.
  321. It has distinct rules for different costs measures.
  322. .PP
  323. If object code size is the most important factor,
  324. the algorithm is greedy and chooses allocations in
  325. decreasing order of their profits attribute.
  326. It does not take into account the fact that
  327. other allocations may be passed over because of
  328. this decision.
  329. .PP
  330. If execution time is at prime stake, the algorithm
  331. first considers allocations whose timespans consist of loops.
  332. After all these have been packed, it considers the remaining
  333. allocations.
  334. Within the two subclasses, it considers allocations
  335. with the highest profits first.
  336. When assigning a register to an allocation with a loop
  337. as timespan, the algorithm checks if the item has
  338. already been put in a register during another loop.
  339. If so, it tries to use the same register for the
  340. new allocation.
  341. After all packing has been done,
  342. it checks if the item has always been assigned the same
  343. register (although not necessarily during all loops).
  344. If so, it tries to put the item in that register during
  345. the entire procedure. This is possible
  346. if the allocation (item,whole_procedure) is not a rival
  347. of any allocation with a different item that has been
  348. assigned to the same register.
  349. Note that this approach is essentially 'bottom up',
  350. as registers are first assigned over small regions
  351. of text which are later collapsed into larger regions.
  352. The advantage of this approach is the fact that
  353. the decisions for one loop can be made independently
  354. of all other loops.
  355. .PP
  356. After the entire packing process has been completed,
  357. we compute for each register how much is gained in using
  358. this register, by simply adding the net profits
  359. of all allocations assigned to it.
  360. This total yield should outweigh the costs of
  361. saving/restoring the register at procedure entry/exit.
  362. As most modern processors (e.g. 68000, Vax) have special
  363. instructions to save/restore several registers,
  364. the differential costs of saving one extra register are by
  365. no means constant.
  366. The costs are read from the machine descriptor file and
  367. compared to the total yields of the registers.
  368. As a consequence of this analysis, some allocations
  369. may have their registers taken away.
  370. .NH 3
  371. The transformation subphase
  372. .PP
  373. The final subphase of RA transforms the EM text according to the
  374. decisions made by the packing system.
  375. It traverses the text of the currently optimized procedure and
  376. changes all occurrences of items at points where
  377. they are assigned a register.
  378. It also clears the score field of the register messages for
  379. normal local variables and emits register messages with a very
  380. high score for the pseudo locals.
  381. At points where registers have to be initialized with items,
  382. it generates EM code to do so.
  383. Finally it tries to decrease the size of the stackframe
  384. of the procedure by looking at which local variables need not
  385. be given memory locations.