ra_allocl.c 9.0 KB

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