ra_allocl.c 9.3 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389
  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 _ A L L O C L I S T . C
  9. */
  10. #include <em_mnem.h>
  11. #include <em_spec.h>
  12. #include <em_pseu.h>
  13. #include <em_reg.h>
  14. #include "../share/types.h"
  15. #include "../share/debug.h"
  16. #include "../share/def.h"
  17. #include "../share/global.h"
  18. #include "../share/lset.h"
  19. #include "../share/cset.h"
  20. #include "../share/aux.h"
  21. #include "../share/alloc.h"
  22. #include "../share/map.h"
  23. #include "ra.h"
  24. #include "ra_aux.h"
  25. #include "ra_items.h"
  26. #include "ra_allocl.h"
  27. #include "ra_interv.h"
  28. STATIC count_usage(p,item,nrloops,sloopcnt,dloopcnt)
  29. proc_p p;
  30. item_p item;
  31. short nrloops, sloopcnt[], dloopcnt[];
  32. {
  33. /* Determine how many times the item is used in every loop.
  34. * We maintain a 'static' count and a 'dynamic' count. The dynamic
  35. * count estimates the number of times the item is used during
  36. * execution, i.e. it gives a higher mark to items used inside
  37. * a loop.
  38. */
  39. lset loops;
  40. loop_p l;
  41. int i;
  42. short lev;
  43. Lindex ui,li;
  44. time_p u;
  45. for (i = 0; i <= nrloops; i++) {
  46. sloopcnt[i] = 0;
  47. dloopcnt[i] = 0;
  48. }
  49. for (ui = Lfirst(item->it_usage); ui != (Lindex) 0;
  50. ui = Lnext(ui,item->it_usage)) {
  51. u = (time_p) Lelem(ui);
  52. loops = u->t_bblock->b_loops;
  53. lev = Lnrelems(loops);
  54. /* set of loops in which this usage of item occurs */
  55. for (li = Lfirst(loops); li != (Lindex) 0; li=Lnext(li,loops)) {
  56. l = (loop_p) Lelem(li);
  57. sloopcnt[l->lp_id]++;
  58. dloopcnt[l->lp_id] +=
  59. (IS_FIRM(u->t_bblock) ? loop_scale(lev) : 1);
  60. }
  61. }
  62. }
  63. STATIC alloc_p cons_alloc(item,timespan,stat_usecount,
  64. dyn_usecount,inits,wholeproc,isloop,iswholeproc)
  65. item_p item;
  66. interv_p timespan;
  67. short stat_usecount,dyn_usecount;
  68. lset inits;
  69. alloc_p wholeproc;
  70. bool isloop,iswholeproc;
  71. {
  72. alloc_p x;
  73. x = newalloc();
  74. x->al_id = ++alloc_id;
  75. x->al_item = item;
  76. x->al_timespan = timespan;
  77. x->al_susecount = stat_usecount;
  78. x->al_dusecount = dyn_usecount;
  79. x->al_inits = inits;
  80. x->al_wholeproc = wholeproc;
  81. x->al_isloop = isloop;
  82. x->al_iswholeproc = iswholeproc;
  83. return x;
  84. }
  85. STATIC insert_alloc(alloc,list_p)
  86. alloc_p alloc, *list_p;
  87. {
  88. alloc->al_next = *list_p;
  89. *list_p = alloc;
  90. }
  91. #define MUST_INIT(i,b) (i->it_type!=LOCALVAR ||contains(b->B_BEGIN,i->it_lives))
  92. #define MUST_UPDATE(i,b) (i->it_type==LOCALVAR &&contains(b->B_BEGIN,i->it_lives))
  93. STATIC lset loop_inits(lp,item,header)
  94. loop_p lp;
  95. item_p item;
  96. bblock_p header;
  97. {
  98. /* Build the set of entry points to loop lp where item
  99. * must be initialized
  100. */
  101. lset s = Lempty_set();
  102. if (header != (bblock_p) 0 && MUST_INIT(item,header)) {
  103. Ladd(header,&s);
  104. }
  105. return s;
  106. }
  107. #define IN_LOOP(b) (Lnrelems(b->b_loops) > 0)
  108. STATIC bblock_p init_point(item)
  109. item_p item;
  110. {
  111. /* Find the most appropriate point to initialize any register
  112. * containing the item. We want to do the initialization as
  113. * late as possible, to allow other items to be put in the
  114. * same register, before this initialization. Yet, as we want
  115. * to do the initialization only once, it must be done in a
  116. * basic block that is a dominator of all points where the
  117. * item is used (ultimately in the first block of the procedure).
  118. * This basic block should not be part of loop.
  119. */
  120. bblock_p b,dom = 0;
  121. Lindex ti;
  122. time_p t;
  123. for (ti = Lfirst(item->it_usage); ti != (Lindex) 0;
  124. ti = Lnext(ti,item->it_usage)) {
  125. t = (time_p) Lelem(ti);
  126. b = t->t_bblock;
  127. dom = (dom == (bblock_p) 0 ? b : common_dom(dom,b));
  128. }
  129. while (IN_LOOP(dom)) {
  130. /* Find a dominator of dom (possibly
  131. * dom itself) that is outside any loop.
  132. */
  133. dom = dom->b_idom;
  134. }
  135. return dom;
  136. }
  137. STATIC add_blocks(b,s,span)
  138. bblock_p b;
  139. cset *s;
  140. interv_p *span;
  141. {
  142. Lindex pi;
  143. if (!Cis_elem(b->b_id,*s)) {
  144. Cadd(b->b_id,s);
  145. add_interval(b->B_BEGIN,b->B_END,span);
  146. for (pi = Lfirst(b->b_pred); pi != (Lindex) 0;
  147. pi = Lnext(pi,b->b_pred)) {
  148. add_blocks((bblock_p) Lelem(pi),s,span);
  149. }
  150. }
  151. }
  152. STATIC whole_lifetime(item,ini_out,span_out)
  153. item_p item;
  154. bblock_p *ini_out;
  155. interv_p *span_out;
  156. {
  157. /* Find the initialization point and the time_span of the item, if
  158. * we put the item in a register during all its uses.
  159. */
  160. bblock_p b, ini = init_point(item);
  161. cset s = Cempty_set(blength);
  162. Lindex ti;
  163. time_p t;
  164. interv_p span = (interv_p) 0;
  165. for (ti = Lfirst(item->it_usage); ti != (Lindex) 0;
  166. ti = Lnext(ti,item->it_usage)) {
  167. t = (time_p) Lelem(ti);
  168. b = t->t_bblock;
  169. add_blocks(b,&s,&span);
  170. }
  171. if (!Cis_elem(ini->b_id,s)) {
  172. add_interval(ini->B_BEGIN,ini->B_END,&span);
  173. }
  174. Cdeleteset(s);
  175. *ini_out = ini;
  176. *span_out = span;
  177. }
  178. STATIC lset proc_inits(p,item,ini)
  179. proc_p p;
  180. item_p item;
  181. bblock_p ini;
  182. {
  183. lset s = Lempty_set();
  184. if (item->it_type != LOCALVAR || item->i_t.it_off >= 0) {
  185. /* only local variables need not be initialized */
  186. Ladd(ini, &s);
  187. }
  188. return s;
  189. }
  190. STATIC bool updates_needed(lp,item)
  191. loop_p lp;
  192. item_p item;
  193. {
  194. /* See if the value of item is live after the loop has
  195. * been exited, i.e. must the item be updated after the loop?
  196. */
  197. Lindex bi,si;
  198. bblock_p b,s;
  199. for (bi = Lfirst(lp->LP_BLOCKS); bi != (Lindex) 0;
  200. bi = Lnext(bi,lp->LP_BLOCKS)) {
  201. b = (bblock_p) Lelem(bi);
  202. for (si = Lfirst(b->b_succ); si != (Lindex) 0;
  203. si = Lnext(si,b->b_succ)) {
  204. s = (bblock_p) Lelem(si);
  205. if (!Lis_elem(s,lp->LP_BLOCKS) && MUST_UPDATE(item,s)) {
  206. return TRUE;
  207. }
  208. }
  209. }
  210. return FALSE;
  211. }
  212. STATIC short countuses(usage,b)
  213. lset usage;
  214. bblock_p b;
  215. {
  216. short cnt = 0;
  217. Lindex ti;
  218. time_p t;
  219. for (ti = Lfirst(usage); ti != (Lindex) 0; ti = Lnext(ti,usage)) {
  220. t = (time_p) Lelem(ti);
  221. if (t->t_bblock == b) cnt++;
  222. }
  223. return cnt;
  224. }
  225. STATIC allocs_of_item(p,item,loops,sloopcnt,dloopcnt,alloc_list_p)
  226. proc_p p;
  227. item_p item;
  228. lset loops;
  229. short *sloopcnt,*dloopcnt; /* dynamic arrays */
  230. alloc_p *alloc_list_p;
  231. {
  232. register Lindex li;
  233. loop_p lp;
  234. bblock_p header,ini;
  235. short susecount,dusecount;
  236. interv_p lt;
  237. alloc_p wholeproc;
  238. /* The whole procedure may be used as timespan.
  239. The dynamic usecount of a procedure is taken to be the same
  240. as its static usecount; this number is not very important, as
  241. time-optimziation chooses loops first.
  242. */
  243. whole_lifetime(item,&ini,&lt);
  244. wholeproc = cons_alloc(item,lt,Lnrelems(item->it_usage),
  245. Lnrelems(item->it_usage), proc_inits(p,item,ini),
  246. (alloc_p) 0,FALSE,TRUE);
  247. insert_alloc(wholeproc, alloc_list_p);
  248. for (li = Lfirst(loops); li != (Lindex) 0; li = Lnext(li,loops)) {
  249. lp = (loop_p) Lelem(li);
  250. if (sloopcnt[lp->lp_id] != 0 && !updates_needed(lp,item)
  251. && !((header = lp->LP_HEADER) == (bblock_p) 0 &&
  252. MUST_INIT(item,lp->lp_entry))) {
  253. /* Item is used within loop, so consider loop
  254. * as a timespan during which item may be put in
  255. * a register.
  256. if ((header = lp->LP_HEADER) == (bblock_p) 0 &&
  257. MUST_INIT(item,lp->lp_entry)) continue;
  258. */
  259. lt = loop_lifetime(lp);
  260. susecount = sloopcnt[lp->lp_id];
  261. dusecount = dloopcnt[lp->lp_id];
  262. if (MUST_INIT(item,lp->lp_entry)) {
  263. /* include header block in timespan */
  264. add_interval(header->B_BEGIN,header->B_END,&lt);
  265. susecount += countuses(item->it_usage,header);
  266. } else {
  267. header = (bblock_p) 0;
  268. }
  269. insert_alloc(cons_alloc(item,lt,susecount,dusecount,
  270. loop_inits(lp,item,header),wholeproc,
  271. TRUE,FALSE),
  272. alloc_list_p);
  273. } else if (sloopcnt[lp->lp_id] != 0) {
  274. /* I confess: this is a hack. I didn't expect the
  275. * Spanish inquisition.
  276. */
  277. if (wholeproc->al_dusecount < dloopcnt[lp->lp_id])
  278. wholeproc->al_dusecount = dloopcnt[lp->lp_id];
  279. }
  280. }
  281. }
  282. alloc_p build_alloc_list(p,nrloops,itemlist)
  283. proc_p p;
  284. short nrloops;
  285. item_p itemlist;
  286. {
  287. short *sloopcnt,*dloopcnt; /* dynamic arrays */
  288. register item_p item;
  289. alloc_p alloc_list = (alloc_p) 0;
  290. sloopcnt = (short *) newtable(nrloops);
  291. dloopcnt = (short *) newtable(nrloops);
  292. for (item = itemlist; item != (item_p) 0; item = item->it_next) {
  293. count_usage(p,item,nrloops,sloopcnt,dloopcnt);
  294. allocs_of_item(p,item,p->p_loops,sloopcnt,dloopcnt,
  295. &alloc_list);
  296. }
  297. oldtable(sloopcnt,nrloops);
  298. oldtable(dloopcnt,nrloops);
  299. return alloc_list;
  300. }
  301. build_rivals_graph(alloclist)
  302. alloc_p alloclist;
  303. {
  304. /* See which allocations in the list are rivals of each other,
  305. * i.e. there is some point of time, falling in both
  306. * timespans, at which the items of both allocations are live.
  307. * Allocations with the same item (but different timespans) are
  308. * not considered to be rivals.
  309. * We use an auxiliary data structure "busy" for each allocation,
  310. * indicating when the item is live during the timespan of the
  311. * allocation.
  312. */
  313. register alloc_p alloc,x;
  314. for (alloc = alloclist; alloc != (alloc_p) 0; alloc = alloc->al_next) {
  315. alloc->al_rivals = Cempty_set(alloc_id);
  316. }
  317. for (alloc = alloclist; alloc != (alloc_p) 0; alloc = alloc->al_next) {
  318. alloc->al_busy =
  319. (alloc->al_item->it_type == LOCALVAR ?
  320. intersect(alloc->al_timespan,alloc->al_item->it_lives) :
  321. copy_timespan(alloc->al_timespan));
  322. for (x = alloclist; x != alloc; x = x->al_next) {
  323. if (x->al_item != alloc->al_item &&
  324. not_disjoint(alloc->al_busy,x->al_busy)) {
  325. Cadd(x->al_id,&alloc->al_rivals);
  326. Cadd(alloc->al_id,&x->al_rivals);
  327. if (alloc->al_regtype == x->al_regtype) {
  328. alloc->al_cntrivals++;
  329. x->al_cntrivals++;
  330. }
  331. }
  332. }
  333. }
  334. }