ra_pack.c 9.1 KB

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