ra_pack.c 9.1 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396
  1. /* $Id$ */
  2. /*
  3. * (c) copyright 1987 by the Vrije Universiteit, Amsterdam, The Netherlands.
  4. * See the copyright notice in the ACK home directory, in the file "Copyright".
  5. */
  6. /* R E G I S T E R A L L O C A T I O N
  7. *
  8. * R A _ P A C K . C
  9. */
  10. #include <em_reg.h>
  11. #include "../share/types.h"
  12. #include "../share/debug.h"
  13. #include "../share/def.h"
  14. #include "../share/global.h"
  15. #include "../share/lset.h"
  16. #include "../share/cset.h"
  17. #include "../share/alloc.h"
  18. #include "../share/aux.h"
  19. #include "ra.h"
  20. #include "ra_aux.h"
  21. #include "ra_interv.h"
  22. #include "ra_profits.h"
  23. short regs_occupied[NRREGTYPES]; /* #occupied registers for reg_pointer,
  24. * reg_any etc.
  25. */
  26. #define reg_available(t) (regs_available[t] > regs_occupied[t])
  27. static void initregcount()
  28. {
  29. int t;
  30. for (t = 0; t < NRREGTYPES; t++) {
  31. regs_occupied[t] = 0;
  32. }
  33. }
  34. static alloc_p make_dummy()
  35. {
  36. alloc_p x;
  37. x = newalloc();
  38. /* x->al_profits = 0; */
  39. return x;
  40. }
  41. static bool fits_in(alloc_p a, alloc_p b, bool *cont_item)
  42. {
  43. /* See if allocation a can be assigned the same register as b.
  44. * Both allocations should be of the same register-type.
  45. * Note that there may be several other allocations (mates) assigned to
  46. * the same register as b. A new candidate (i.e. 'a') is only
  47. * allowed to join them if it is not the rival of any resident
  48. * allocation.
  49. */
  50. *cont_item = FALSE;
  51. if (a->al_regtype == b->al_regtype) {
  52. while (b != (alloc_p) 0) {
  53. if (Cis_elem(a->al_id,b->al_rivals)) break;
  54. b = b->al_mates;
  55. if (b != (alloc_p) 0 && a->al_item == b->al_item) {
  56. *cont_item = TRUE;
  57. }
  58. }
  59. }
  60. return b == (alloc_p) 0;
  61. }
  62. static alloc_p find_fitting_alloc(alloc_p alloc, alloc_p packed)
  63. {
  64. /* Try to find and already packed allocation that is assigned
  65. * a register that may also be used for alloc.
  66. * We prefer allocations that have the same item as alloc.
  67. */
  68. alloc_p x;
  69. alloc_p cand = (alloc_p) 0;
  70. bool cont_item;
  71. for (x = packed->al_next; x != (alloc_p) 0; x = x->al_next) {
  72. if (fits_in(alloc,x,&cont_item)) {
  73. cand = x;
  74. if (cont_item) break;
  75. }
  76. }
  77. return cand;
  78. }
  79. static bool room_for(alloc_p alloc, alloc_p packed)
  80. {
  81. /* See if there is any register available for alloc */
  82. return reg_available(alloc->al_regtype) ||
  83. (find_fitting_alloc(alloc,packed) != (alloc_p) 0);
  84. }
  85. static alloc_p best_alloc(alloc_p unpacked, alloc_p packed, bool time_opt)
  86. {
  87. /* Find the next best candidate */
  88. alloc_p x,best;
  89. best = unpacked; /* dummy */
  90. for (x = unpacked->al_next; x != (alloc_p) 0; x = x->al_next) {
  91. if (x->al_profits > best->al_profits &&
  92. room_for(x,packed)) {
  93. best = x;
  94. }
  95. }
  96. return (best == unpacked ? (alloc_p) 0 : best);
  97. }
  98. static alloc_p choose_location(alloc_p alloc, alloc_p packed, proc_p p)
  99. {
  100. /* Decide in which register to put alloc */
  101. alloc_p fit;
  102. offset dum;
  103. fit = find_fitting_alloc(alloc,packed);
  104. if (fit == (alloc_p) 0) {
  105. /* Take a brand new register; allocate a dummy local for it */
  106. alloc->al_regnr = regs_occupied[alloc->al_regtype]++;
  107. dum = tmplocal(p,(offset) alloc->al_item->it_size);
  108. alloc->al_dummy = dum;
  109. } else {
  110. alloc->al_regnr = fit->al_regnr;
  111. alloc->al_dummy = fit->al_dummy;
  112. }
  113. return fit;
  114. }
  115. static void update_lists(alloc_p alloc, alloc_p unpacked, alloc_p packed, alloc_p fit)
  116. {
  117. /* 'alloc' has been granted a register; move it from the 'unpacked'
  118. * list to the 'packed' list. Also remove any allocation from 'unpacked'
  119. * having:
  120. * 1. the same item as 'alloc' and
  121. * 2. a timespan that overlaps the timespan of alloc.
  122. */
  123. alloc_p x,q,next;
  124. q = unpacked; /* dummy element at head of list */
  125. for (x = unpacked->al_next; x != (alloc_p) 0; x = next) {
  126. next = x->al_next;
  127. if (x->al_item == alloc->al_item &&
  128. not_disjoint(x->al_timespan, alloc->al_timespan)) {
  129. /* this code kills two birds with one stone;
  130. * x is either an overlapping allocation or
  131. * alloc itself!
  132. */
  133. q->al_next = x->al_next;
  134. if (x == alloc) {
  135. if (fit == (alloc_p) 0) {
  136. x->al_next = packed->al_next;
  137. packed->al_next = x;
  138. } else {
  139. x->al_mates = fit->al_mates;
  140. fit->al_mates = x;
  141. x->al_next = (alloc_p) 0;
  142. }
  143. }
  144. } else {
  145. q = x;
  146. }
  147. }
  148. }
  149. static short cum_profits(alloc_p alloc)
  150. {
  151. /* Add the profits of all allocations packed in the same
  152. * register as alloc (i.e. alloc and all its 'mates').
  153. */
  154. alloc_p m;
  155. short sum = 0;
  156. for (m = alloc; m != (alloc_p) 0; m = m->al_mates) {
  157. sum += m->al_profits;
  158. }
  159. return sum;
  160. }
  161. static void best_cumprofits(alloc_p list, alloc_p *x_out, alloc_p *prev_out)
  162. {
  163. /* Find the allocation with the best cummulative profits */
  164. alloc_p x,prev,best_prev;
  165. short best = 0, cum;
  166. prev = list;
  167. for (x = list->al_next; x != (alloc_p) 0; x = x->al_next) {
  168. cum = cum_profits(x);
  169. if (cum > best) {
  170. best = cum;
  171. best_prev = prev;
  172. }
  173. prev = x;
  174. }
  175. if (best == 0) {
  176. *x_out = (alloc_p) 0;
  177. } else {
  178. *x_out = best_prev->al_next;
  179. *prev_out = best_prev;
  180. }
  181. }
  182. static void account_regsave(alloc_p packed, alloc_p unpacked)
  183. {
  184. /* After all packing has been done, we check for every allocated
  185. * register whether it is really advantageous to use this
  186. * register. It may be possible that the cost of saving
  187. * and restoring the register are higher than the profits of all
  188. * allocations packed in the register. If so, we simply remove
  189. * all these allocations.
  190. * The cost of saving/restoring one extra register may depend on
  191. * the number of registers already saved.
  192. */
  193. alloc_p x,prev,checked;
  194. short time,space;
  195. short tot_cost = 0,diff;
  196. initregcount();
  197. checked = make_dummy();
  198. while (TRUE) {
  199. best_cumprofits(packed,&x,&prev);
  200. if (x == (alloc_p) 0) break;
  201. regs_occupied[x->al_regtype]++;
  202. regsave_cost(regs_occupied,&time,&space);
  203. diff = add_timespace(time,space) - tot_cost;
  204. if (diff < cum_profits(x)) {
  205. /* x is o.k. */
  206. prev->al_next = x->al_next;
  207. x->al_next = checked->al_next;
  208. checked->al_next = x;
  209. tot_cost += diff;
  210. } else {
  211. break;
  212. }
  213. }
  214. /* Now every allocation in 'packed' does not pay off, so
  215. * it is moved to unpacked, indicating it will not be assigned
  216. * a register.
  217. */
  218. for (x = unpacked; x->al_next != (alloc_p) 0; x = x->al_next);
  219. x->al_next = packed->al_next;
  220. packed->al_next = checked->al_next;
  221. oldalloc(checked);
  222. }
  223. static bool in_single_reg(item_p item, alloc_p packed)
  224. {
  225. /* See if item is allocated in only one register (i.e. not in
  226. * several different registers during several parts of its lifetime.
  227. */
  228. alloc_p x,m;
  229. bool seen = FALSE;
  230. for (x = packed->al_next; x != (alloc_p) 0; x = x->al_next) {
  231. for ( m = x; m != (alloc_p) 0; m = m->al_mates) {
  232. if (m->al_item == item) {
  233. if (seen) return FALSE;
  234. seen = TRUE;
  235. break;
  236. }
  237. }
  238. }
  239. return TRUE;
  240. }
  241. static alloc_p find_prev(alloc_p alloc, alloc_p list)
  242. {
  243. alloc_p x;
  244. assert ( alloc != (alloc_p) 0);
  245. for (x = list; x->al_next != alloc ; x = x->al_next)
  246. assert(x != (alloc_p) 0);
  247. return x;
  248. }
  249. /* If an item is always put in the same register during different loops,
  250. * we try to put it in that register during the whole procedure.
  251. * The profits of the whole-procedure allocation are updated to prevent
  252. * account_regsave from rejecting it.
  253. */
  254. static void repl_allocs(alloc_p new, alloc_p old, alloc_p packed)
  255. {
  256. alloc_p x,next,prev,*p;
  257. short prof = 0;
  258. new->al_regnr = old->al_regnr;
  259. new->al_dummy = old->al_dummy;
  260. prev = find_prev(old,packed);
  261. new->al_next = old->al_next;
  262. old->al_next = (alloc_p) 0;
  263. prev->al_next = new;
  264. new->al_mates = old;
  265. p = &new->al_mates;
  266. for (x = old; x != (alloc_p) 0; x = next) {
  267. next = x->al_mates;
  268. if (x->al_item == new->al_item) {
  269. prof += x->al_profits;
  270. *p = next;
  271. oldalloc(x);
  272. } else {
  273. p = &x->al_mates;
  274. }
  275. }
  276. new->al_profits = prof;
  277. }
  278. static void assemble_allocs(alloc_p packed)
  279. {
  280. alloc_p x,m,next;
  281. alloc_p e;
  282. bool voidb;
  283. for (x = packed->al_next; x != (alloc_p) 0; x = next) {
  284. next = x->al_next;
  285. for ( m = x; m != (alloc_p) 0; m = m->al_mates) {
  286. if (in_single_reg(m->al_item,packed) &&
  287. (e = m->al_wholeproc) != (alloc_p) 0 &&
  288. e->al_profits > 0 &&
  289. fits_in(e,x,&voidb)) {
  290. repl_allocs(e,x,packed);
  291. break;
  292. }
  293. }
  294. }
  295. }
  296. void pack(alloc_p alloclist, bool time_opt, alloc_p *packed_out, alloc_p *not_packed_out, proc_p p)
  297. {
  298. /* This is the packing system. It decides which allations
  299. * to grant a register.
  300. * We use two lists: packed (for allocations that are assigned a
  301. * register) and unpacked (allocations not yet assigned a register).
  302. * The packed list is in fact '2-dimensional': the al_next field is
  303. * used to link allations that are assigned different registers;
  304. * the al_mates field links allocations that are assigned to
  305. * the same registers (i.e. these allocations fit together).
  306. */
  307. alloc_p x;
  308. alloc_p packed,unpacked,fit;
  309. initregcount();
  310. packed = make_dummy();
  311. unpacked = make_dummy();
  312. unpacked->al_next = alloclist;
  313. while ((x = best_alloc(unpacked,packed,time_opt)) != (alloc_p) 0) {
  314. fit = choose_location(x,packed,p);
  315. update_lists(x,unpacked,packed,fit);
  316. }
  317. assemble_allocs(packed);
  318. account_regsave(packed,unpacked);
  319. /* remove allocations that don't pay off against register
  320. * save/restore costs.
  321. */
  322. *packed_out = packed->al_next;
  323. *not_packed_out = unpacked->al_next;
  324. oldalloc(packed);
  325. oldalloc(unpacked);
  326. }