ra.c 12 KB

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