ra_pack.c 9.3 KB

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