ra.c 12 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543
  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. /*
  7. * R E G I S T E R A L L O C A T I O N
  8. *
  9. */
  10. #include <stdlib.h>
  11. #include <stdio.h>
  12. #include <string.h>
  13. #include <em_reg.h>
  14. #include "../share/types.h"
  15. #include "../share/debug.h"
  16. #include "../share/global.h"
  17. #include "../share/files.h"
  18. #include "../share/get.h"
  19. #include "../share/put.h"
  20. #include "../share/lset.h"
  21. #include "../share/cset.h"
  22. #include "../share/map.h"
  23. #include "../share/alloc.h"
  24. #include "../share/go.h"
  25. #include "ra.h"
  26. #include "ra_items.h"
  27. #include "ra_allocl.h"
  28. #include "ra_lifet.h"
  29. #include "ra_profits.h"
  30. #include "ra_pack.h"
  31. #include "ra_xform.h"
  32. #define newrabx() (bext_p) newstruct(bext_ra)
  33. #define newralpx() (lpext_p) newstruct(lpext_ra)
  34. #define oldrabx(x) oldstruct(bext_ra,x)
  35. #define oldralpx(x) oldstruct(lpext_ra,x)
  36. void stat_regusage(alloc_p list);
  37. short alloc_id;
  38. static item_p items[NRITEMTYPES];
  39. int nrinstrs;
  40. line_p *instrmap;
  41. cond_p alocaltab[NRREGTYPES][NRREGTYPES],alocaddrtab[NRREGTYPES][NRREGTYPES],
  42. aconsttab,adconsttab,aglobaltab,aproctab;
  43. cond_p olocaltab[NRREGTYPES],olocaddrtab[NRREGTYPES],
  44. oconsttab,odconsttab,oglobaltab,oproctab;
  45. cond_p regsav_cost;
  46. short regs_available[] = {
  47. /* Actually machine dependent; this is for vax2 */
  48. 3, /* reg_any i.e. data regs */
  49. 0, /* reg_loop */
  50. 3, /* reg_pointer i.e. address reg. */
  51. 0 /* reg_float */
  52. } ;
  53. short use_any_as_pointer = 0;
  54. static cond_p getcondtab(f)
  55. FILE *f;
  56. {
  57. int l,i;
  58. cond_p tab;
  59. fscanf(f,"%d",&l);
  60. tab = newcondtab(l);
  61. for (i = 0; i < l; i++) {
  62. fscanf(f,"%hd %hd %hd",&tab[i].mc_cond,&tab[i].mc_tval,
  63. &tab[i].mc_sval);
  64. }
  65. assert(tab[l-1].mc_cond == DEFAULT);
  66. return tab;
  67. }
  68. void get_atab(FILE *f, cond_p tab[NRREGTYPES][NRREGTYPES])
  69. {
  70. int i,cnt,totyp,regtyp;
  71. fscanf(f,"%d",&cnt);
  72. for (i = 0; i < cnt; i++) {
  73. fscanf(f,"%d %d",&regtyp,&totyp);
  74. assert(regtyp >= 0 && regtyp < NRREGTYPES);
  75. assert(totyp >= 0 && totyp < NRREGTYPES);
  76. tab[regtyp][totyp] = getcondtab(f);
  77. }
  78. }
  79. void get_otab(FILE *f, cond_p tab[NRREGTYPES])
  80. {
  81. int i,cnt,regtyp;
  82. fscanf(f,"%d",&cnt);
  83. for (i = 0; i < cnt; i++) {
  84. fscanf(f,"%d",&regtyp);
  85. assert(regtyp >= 0 && regtyp < NRREGTYPES);
  86. tab[regtyp] = getcondtab(f);
  87. }
  88. }
  89. static int ra_machinit(void *param)
  90. {
  91. /* Read target machine dependent information for this phase */
  92. char s[100];
  93. FILE *f = (FILE *)param;
  94. for (;;) {
  95. while(getc(f) != '\n');
  96. fscanf(f,"%s",s);
  97. if (strcmp(s,"%%RA") == 0)break;
  98. }
  99. fscanf(f,"%hd",&regs_available[reg_any]);
  100. fscanf(f,"%hd",&regs_available[reg_pointer]);
  101. fscanf(f,"%hd",&regs_available[reg_float]);
  102. fscanf(f,"%hd",&use_any_as_pointer);
  103. get_atab(f,alocaltab);
  104. get_atab(f,alocaddrtab);
  105. aconsttab = getcondtab(f);
  106. adconsttab = getcondtab(f);
  107. aglobaltab = getcondtab(f);
  108. aproctab = getcondtab(f);
  109. get_otab(f,olocaltab);
  110. get_otab(f,olocaddrtab);
  111. oconsttab = getcondtab(f);
  112. odconsttab = getcondtab(f);
  113. oglobaltab = getcondtab(f);
  114. oproctab = getcondtab(f);
  115. regsav_cost = getcondtab(f);
  116. return 0;
  117. }
  118. static bblock_p header(loop_p lp)
  119. {
  120. /* Try to determine the 'header' block of loop lp.
  121. * If 'e' is the entry block of loop L, then block 'b' is
  122. * called the header block of L, iff:
  123. * SUCC(b) = {e} & PRED(e) = {b}
  124. * If lp has no header block, 0 is returned.
  125. */
  126. bblock_p x = lp->lp_entry->b_idom;
  127. if (x != (bblock_p) 0 && Lnrelems(x->b_succ) == 1 &&
  128. (bblock_p) Lelem(Lfirst(x->b_succ)) == lp->lp_entry) {
  129. return x;
  130. }
  131. return (bblock_p) 0;
  132. }
  133. static void ra_extproc(proc_p p)
  134. {
  135. /* Allocate the extended data structures for procedure p */
  136. loop_p lp;
  137. Lindex pi;
  138. bblock_p b;
  139. for (pi = Lfirst(p->p_loops); pi != (Lindex) 0;
  140. pi = Lnext(pi,p->p_loops)) {
  141. lp = (loop_p) Lelem(pi);
  142. lp->lp_extend = newralpx();
  143. lp->LP_HEADER = header(lp);
  144. }
  145. for (b = p->p_start; b != (bblock_p) 0; b = b->b_next) {
  146. b->b_extend = newrabx();
  147. }
  148. }
  149. static int ra_cleanproc(void *param)
  150. {
  151. /* Allocate the extended data structures for procedure p */
  152. proc_p p = (proc_p)param;
  153. loop_p lp;
  154. Lindex pi;
  155. bblock_p b;
  156. for (pi = Lfirst(p->p_loops); pi != (Lindex) 0;
  157. pi = Lnext(pi,p->p_loops)) {
  158. lp = (loop_p) Lelem(pi);
  159. oldralpx(lp->lp_extend);
  160. }
  161. for (b = p->p_start; b != (bblock_p) 0; b = b->b_next) {
  162. oldrabx(b->b_extend);
  163. }
  164. return 0;
  165. }
  166. static void loop_blocks(proc_p p)
  167. {
  168. /* Compute the LP_BLOCKS sets for all loops of p */
  169. bblock_p b;
  170. Lindex i;
  171. for (b = p->p_start; b != (bblock_p) 0; b = b->b_next) {
  172. for (i = Lfirst(b->b_loops); i != (Lindex) 0;
  173. i = Lnext(i,b->b_loops)) {
  174. Ladd(b,&(((loop_p) Lelem(i))->LP_BLOCKS));
  175. }
  176. }
  177. }
  178. static void make_instrmap(proc_p p, line_p map[])
  179. {
  180. /* make the instructions map of procedure p */
  181. bblock_p b;
  182. line_p l;
  183. int i = 0;
  184. for (b = p->p_start; b != (bblock_p) 0; b = b->b_next) {
  185. b->B_BEGIN = i; /* number of first instruction */
  186. for (l = b->b_start; l != (line_p) 0; l = l->l_next) {
  187. map[i++] = l;
  188. }
  189. b->B_END = i-1; /* number of last instruction */
  190. }
  191. }
  192. static bool useful_item(item_p item)
  193. {
  194. /* See if it may be useful to put the item in a register.
  195. * A local variable may always be put in a register.
  196. * Other items must be used at least twice.
  197. */
  198. int nruses = Lnrelems(item->it_usage);
  199. assert (nruses > 0); /* otherwise it would not be an item! */
  200. return nruses > 1 || item->it_type == LOCALVAR;
  201. }
  202. static void cleantimeset(lset s)
  203. {
  204. Lindex i;
  205. time_p t;
  206. for (i = Lfirst(s); i != (Lindex) 0; i = Lnext(i,s)) {
  207. t = (time_p) Lelem(i);
  208. oldtime(t);
  209. }
  210. Ldeleteset(s);
  211. }
  212. static item_p cat_items(item_p items[])
  213. {
  214. /* Make one item list out of an array of itemlists.
  215. * Remove items that are used only once.
  216. */
  217. item_p it;
  218. item_p *ip,head,next;
  219. int t;
  220. ip = &head;
  221. for (t = 0; t < NRITEMTYPES;t++) {
  222. for ( it = items[t]; it != (item_p) 0; it = next) {
  223. next = it->it_next;
  224. if (!it->it_desirable || !useful_item(it)) {
  225. cleantimeset(it->it_usage);
  226. olditem(it);
  227. } else {
  228. *ip = it;
  229. ip = &it->it_next;
  230. }
  231. }
  232. }
  233. *ip = (item_p) 0;
  234. return head;
  235. }
  236. static void clean_interval(interv_p list)
  237. {
  238. interv_p x,next;
  239. for (x = list; x != (interv_p) 0; x = next) {
  240. next = x->i_next;
  241. oldinterval(x);
  242. }
  243. }
  244. static void clean_allocs(alloc_p list)
  245. {
  246. alloc_p x,next;
  247. for (x = list; x != (alloc_p) 0; x = next) {
  248. next = x->al_next;
  249. clean_interval(x->al_timespan);
  250. Cdeleteset(x->al_rivals);
  251. Ldeleteset(x->al_inits);
  252. clean_interval(x->al_busy);
  253. clean_allocs(x->al_mates);
  254. oldalloc(x);
  255. }
  256. }
  257. static void cleanitems(item_p list)
  258. {
  259. item_p x,next;
  260. for (x = list; x != (item_p) 0; x = next ) {
  261. next = x->it_next;
  262. cleantimeset(x->it_usage);
  263. olditem(x);
  264. }
  265. }
  266. int ra_initialize(void *dummy)
  267. {
  268. init_replacements(ps,ws);
  269. return 0;
  270. }
  271. int ra_optimize(void *param)
  272. {
  273. proc_p p = (proc_p)param;
  274. item_p itemlist;
  275. alloc_p alloclist,packed,unpacked;
  276. offset locls;
  277. bool time_opt = (time_space_ratio == 100);
  278. if (IS_ENTERED_WITH_GTO(p)) return 0;
  279. ra_extproc(p);
  280. loop_blocks(p);
  281. alloc_id =0;
  282. locls = p->p_localbytes;
  283. build_itemlist(p,items,&nrinstrs);
  284. instrmap = (line_p *) newmap(nrinstrs-1); /* map starts counting at 0 */
  285. make_instrmap(p,instrmap);
  286. build_lifetimes(items);
  287. /* print_items(items,p); */
  288. /* statistics(items); */
  289. itemlist = cat_items(items); /* make one list */
  290. alloclist = build_alloc_list(p,Lnrelems(p->p_loops),
  291. itemlist);
  292. build_rivals_graph(alloclist);
  293. compute_profits(alloclist,time_opt);
  294. /* print_allocs(alloclist); */
  295. pack(alloclist,time_opt,&packed,&unpacked,p);
  296. stat_regusage(packed);
  297. xform_proc(p,packed,nrinstrs,instrmap);
  298. /* print_allocs(packed); */
  299. p->p_localbytes = locls;
  300. /* don't really allocate dummy local variables! */
  301. rem_locals(p,packed);
  302. rem_formals(p,packed);
  303. /* remove storage for real locals that
  304. *are always put in register .
  305. */
  306. clean_allocs(unpacked);
  307. clean_allocs(packed);
  308. cleanitems(itemlist);
  309. oldmap((short **)instrmap,nrinstrs-1);
  310. ra_cleanproc(p);
  311. return 0;
  312. }
  313. int main(int argc, char *argv[])
  314. {
  315. go(argc,argv,ra_initialize,ra_optimize,ra_machinit,no_action);
  316. exit(0);
  317. }
  318. /***************************************************************************/
  319. /***************************************************************************/
  320. /***************************************************************************/
  321. /* debugging stuff */
  322. char *str_types[] = {
  323. "local variable",
  324. "addr. of local",
  325. "addr. of external",
  326. "addr. of procedure",
  327. "constant",
  328. "double constant"
  329. };
  330. char *str_regtypes[] = {
  331. "any",
  332. "loop",
  333. "pointer",
  334. "float"
  335. };
  336. void print_items(item_p items[], proc_p p)
  337. {
  338. int t;
  339. item_p item;
  340. interv_p iv;
  341. fprintf(stderr, "BEGIN PROCEDURE %d\n",p->p_id);
  342. for (t = 0; t < NRITEMTYPES;t++) {
  343. for (item = items[t]; item != (item_p) 0;item = item->it_next) {
  344. fprintf(stderr, "\nitemtype = %s\n",str_types[t]);
  345. if (t == GLOBL_ADDR) {
  346. fprintf(stderr, "id of external = %d\n",
  347. item->i_t.it_obj->o_id);
  348. } else {
  349. fprintf(stderr, "offset = %ld\n",
  350. item->i_t.it_off);
  351. }
  352. fprintf(stderr, "regtype = %s\n",str_regtypes[item->it_regtype]);
  353. fprintf(stderr, "size = %d\n",item->it_size);
  354. fprintf(stderr, "#usages = %d\n", Lnrelems(item->it_usage));
  355. fprintf(stderr, "lifetime = {");
  356. for (iv = item->it_lives; iv != (interv_p) 0;
  357. iv = iv->i_next) {
  358. fprintf(stderr, "(%d,%d) ",iv->i_start,iv->i_stop);
  359. }
  360. fprintf(stderr, "} \n");
  361. }
  362. }
  363. fprintf(stderr, "END PROCEDURE %d\n\n",p->p_id);
  364. }
  365. void print_allocs(alloc_p list)
  366. {
  367. alloc_p al,m;
  368. item_p item;
  369. short t;
  370. interv_p iv;
  371. fprintf(stderr,"BEGIN ALLOCLIST of proc %d\n",curproc->p_id);
  372. for (m = list ; m != (alloc_p) 0; m = m->al_next) {
  373. for (al = m; al != (alloc_p) 0; al = al->al_mates) {
  374. item = al->al_item;
  375. t = item->it_type;
  376. fprintf(stderr,"\nitem: [type = %s, ",str_types[t]);
  377. switch(t) {
  378. case GLOBL_ADDR:
  379. fprintf(stderr,"id = %d]\n", item->i_t.it_obj->o_id);
  380. break;
  381. case PROC_ADDR:
  382. fprintf(stderr,"id = %d]\n", item->i_t.it_proc->p_id);
  383. break;
  384. default:
  385. fprintf(stderr,"offset = %ld]\n", item->i_t.it_off);
  386. }
  387. fprintf(stderr,"#usages(static) = %d\n",al->al_susecount);
  388. fprintf(stderr,"#usages(dyn) = %d\n",al->al_dusecount);
  389. fprintf(stderr,"#inits = %d\n",Lnrelems(al->al_inits));
  390. fprintf(stderr,"isloop = %d\n",al->al_isloop);
  391. fprintf(stderr,"timespan = {");
  392. for (iv = al->al_timespan; iv != (interv_p) 0;
  393. iv = iv->i_next) {
  394. fprintf(stderr,"(%d,%d) ",iv->i_start,iv->i_stop);
  395. }
  396. fprintf(stderr,"} \n");
  397. fprintf(stderr,"busy = {");
  398. for (iv = al->al_busy; iv != (interv_p) 0;
  399. iv = iv->i_next) {
  400. fprintf(stderr,"(%d,%d) ",iv->i_start,iv->i_stop);
  401. }
  402. fprintf(stderr,"} \n");
  403. fprintf(stderr,"profits = %d\n",al->al_profits);
  404. fprintf(stderr,"dummy local = %ld\n",al->al_dummy);
  405. fprintf(stderr,"regnr = %d\n",al->al_regnr);
  406. }
  407. }
  408. }
  409. short regs_needed[4];
  410. void stat_regusage(alloc_p list)
  411. {
  412. int i;
  413. alloc_p x;
  414. for (i = 0; i < 4; i++) {
  415. regs_needed[i] = 0;
  416. }
  417. for (x = list; x != (alloc_p) 0; x = x->al_next) {
  418. regs_needed[x->al_regtype]++;
  419. }
  420. /* fprintf(stderr, "data regs:%d\n",regs_needed[reg_any]); */
  421. /* fprintf(stderr, "address regs:%d\n",regs_needed[reg_pointer]); */
  422. }
  423. int cnt_regtypes[reg_float+1];
  424. void statistics(item_p items[])
  425. {
  426. item_p item,next;
  427. int t,r;
  428. int cnt;
  429. fprintf(stderr, "\nSTATISTICS\n");
  430. for (r = 0; r <= reg_float; r++) cnt_regtypes[r] = 0;
  431. for (t = 0; t < NRITEMTYPES;t++) {
  432. cnt = 0;
  433. for (item = items[t]; item != (item_p) 0;item = next) {
  434. if (useful_item(item)) {
  435. cnt++;
  436. cnt_regtypes[item->it_regtype]++;
  437. }
  438. next = item->it_next;
  439. }
  440. fprintf(stderr, "#%s = %d\n",str_types[t],cnt);
  441. }
  442. for (r = 0; r <= reg_float; r++) {
  443. fprintf(stderr, "#%s = %d\n",str_regtypes[r],cnt_regtypes[r]);
  444. }
  445. }