ra.c 12 KB

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