ra_xform.c 12 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580
  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 _ X F O R M . C
  9. */
  10. #include <em_mnem.h>
  11. #include <em_spec.h>
  12. #include <em_pseu.h>
  13. #include <em_mes.h>
  14. #include <em_ego.h>
  15. #include <em_reg.h>
  16. #include "../share/types.h"
  17. #include "../share/debug.h"
  18. #include "../share/def.h"
  19. #include "../share/global.h"
  20. #include "../share/lset.h"
  21. #include "../share/aux.h"
  22. #include "../share/alloc.h"
  23. #include "ra.h"
  24. #include "ra_interv.h"
  25. #include "ra_xform.h"
  26. #include "ra_items.h"
  27. /* The replacement table is used to transform instructions that reference
  28. * items other than local variables (i.e. the address of a local or global
  29. * variable or a single/double constant; the transformation of an instruction
  30. * that references a local variable is very simple).
  31. * The generated code depends on the word and pointer size of the target
  32. * machine.
  33. */
  34. struct repl {
  35. short r_instr; /* instruction */
  36. short r_op; /* operand */
  37. };
  38. /* REGNR,NO and STOP should not equal the wordsize or pointer size
  39. * of any machine.
  40. */
  41. #define REGNR -3
  42. #define NO -2
  43. #define STOP -1
  44. #define PS 0
  45. #define PS2 1
  46. #define WS 2
  47. #define WS2 3
  48. #define LOAD_POINTER op_nop
  49. #define BLANK {0, STOP}
  50. #define NRREPLACEMENTS 13
  51. #define REPL_LENGTH 3
  52. struct repl repl_tab[NRREPLACEMENTS][REPL_LENGTH] = {
  53. /* 0 */ {{op_lil, REGNR}, BLANK, BLANK},
  54. /* 1 */ {{LOAD_POINTER,REGNR}, {op_loi,PS}, {op_loi,WS}},
  55. /* 2 */ {{LOAD_POINTER,REGNR}, BLANK, BLANK},
  56. /* 3 */ {{LOAD_POINTER,REGNR}, {op_loi,WS2}, BLANK},
  57. /* 4 */ {{op_sil,REGNR}, BLANK, BLANK},
  58. /* 5 */ {{LOAD_POINTER,REGNR}, {op_loi,PS}, {op_sti,WS}},
  59. /* 6 */ {{LOAD_POINTER,REGNR}, {op_sti,WS2}, BLANK},
  60. /* 7 */ {{op_lil,REGNR}, {op_inc,NO}, {op_sil,REGNR}},
  61. /* 8 */ {{op_lil,REGNR}, {op_dec,NO}, {op_sil,REGNR}},
  62. /* 9 */ {{op_zer,WS}, {op_sil,REGNR}, BLANK},
  63. /*10 */ {{op_lol,REGNR}, BLANK, BLANK},
  64. /*11 */ {{op_ldl,REGNR}, BLANK, BLANK},
  65. /*12 */ {{LOAD_POINTER,REGNR}, {op_cai,NO}, BLANK},
  66. };
  67. init_replacements(psize,wsize)
  68. short psize,wsize;
  69. {
  70. /* The replacement code to be generated depends on the
  71. * wordsize and pointer size of the target machine.
  72. * The replacement table is initialized with a description
  73. * of which sizes to use. This routine inserts the real sizes.
  74. * It also inserts the actual EM instruction to be used
  75. * as a 'Load pointer' instruction.
  76. */
  77. register int i,j;
  78. short load_pointer;
  79. struct repl *r;
  80. assert (psize == wsize || psize == 2*wsize);
  81. load_pointer = (psize == wsize ? op_lol : op_ldl);
  82. for (i = 0; i < NRREPLACEMENTS; i++) {
  83. for (j = 0; j < REPL_LENGTH; j++) {
  84. r = &repl_tab[i][j];
  85. if (r->r_op == STOP) break;
  86. if (r->r_instr == LOAD_POINTER) {
  87. r->r_instr = load_pointer;
  88. }
  89. switch (r->r_op) {
  90. /* initially r_op describes how to compute
  91. * the real operand of the instruction. */
  92. case PS2:
  93. r->r_op = 2*psize;
  94. break;
  95. case PS:
  96. r->r_op = psize;
  97. break;
  98. case WS2:
  99. r->r_op = 2*wsize;
  100. break;
  101. case WS:
  102. r->r_op = wsize;
  103. break;
  104. case NO:
  105. case REGNR: /* use offset of dummy local,
  106. * will be filled in later.
  107. */
  108. break;
  109. default: assert(FALSE);
  110. }
  111. }
  112. }
  113. }
  114. STATIC int repl_index(l)
  115. line_p l;
  116. {
  117. return itemtab[INSTR(l) - sp_fmnem].id_replindex;
  118. }
  119. STATIC bool is_current(alloc,t)
  120. alloc_p alloc;
  121. short t;
  122. {
  123. /* Is time t part of alloc's timespan? */
  124. return contains(t,alloc->al_timespan);
  125. }
  126. STATIC match_item(item,l)
  127. item_p item;
  128. line_p l;
  129. {
  130. /* See if the item used by l is the same one as 'item' */
  131. struct item thisitem;
  132. fill_item(&thisitem,l);
  133. if (item->it_type == LOCAL_ADDR && thisitem.it_type == LOCALVAR) {
  134. /* The usage of a local variable is also considered to
  135. * be the usage of the address of that variable.
  136. */
  137. thisitem.it_type = LOCAL_ADDR;
  138. }
  139. return item->it_type == thisitem.it_type && same_item(item,&thisitem);
  140. }
  141. STATIC alloc_p find_alloc(alloclist,l,t)
  142. alloc_p alloclist;
  143. line_p l;
  144. short t;
  145. {
  146. /* See if any of the allocations of the list applies to instruction
  147. * l at time t.
  148. */
  149. register alloc_p alloc,m;
  150. for (alloc = alloclist; alloc != (alloc_p) 0; alloc = alloc->al_next) {
  151. for (m = alloc; m != (alloc_p) 0; m = m->al_mates) {
  152. if (is_current(m,t) && match_item(m->al_item,l)) {
  153. return m;
  154. }
  155. }
  156. }
  157. return (alloc_p) 0;
  158. }
  159. STATIC replace_line(l,b,list)
  160. line_p l,list;
  161. bblock_p b;
  162. {
  163. if (b->b_start == l) {
  164. b->b_start = list;
  165. } else {
  166. PREV(l)->l_next = list;
  167. }
  168. PREV(list) = PREV(l);
  169. while (list->l_next != (line_p) 0) {
  170. list = list->l_next;
  171. }
  172. list->l_next = l->l_next;
  173. if (l->l_next != (line_p) 0) {
  174. PREV(l->l_next) = list;
  175. }
  176. oldline(l);
  177. }
  178. STATIC line_p repl_code(lnp,regnr)
  179. line_p lnp;
  180. offset regnr;
  181. {
  182. line_p head,*q,l,prev = (line_p) 0;
  183. int i,index;
  184. struct repl *r;
  185. q = &head;
  186. index = repl_index(lnp);
  187. for (i = 0; i < REPL_LENGTH; i++) {
  188. r = &repl_tab[index][i];
  189. if (r->r_op == STOP) break; /* replacement < REPL_LENGTH */
  190. switch(r->r_op) {
  191. case REGNR:
  192. l = int_line(regnr);
  193. break;
  194. case NO:
  195. l = newline(OPNO);
  196. break;
  197. default:
  198. l = newline(OPSHORT);
  199. SHORT(l) = r->r_op;
  200. break;
  201. }
  202. *q = l;
  203. l->l_instr = r->r_instr;
  204. PREV(l) = prev;
  205. prev = l;
  206. q = &l->l_next;
  207. }
  208. return head;
  209. }
  210. STATIC apply_alloc(b,l,alloc)
  211. bblock_p b;
  212. line_p l;
  213. alloc_p alloc;
  214. {
  215. /* 'l' is an EM instruction using an item that will be put in
  216. * a register. Generate new code that uses the register instead
  217. * of the item.
  218. * If the item is a local variable the new code is the same as
  219. * the old code, except for the fact that the offset of the
  220. * local is changed (it now uses the dummy local that will be
  221. * put in a register by the code generator).
  222. * If the item is a constant, the new code is a LOL or LDL.
  223. * If the item is the address of a local or global variable, things
  224. * get more complicated. The new code depends on the instruction
  225. * that uses the item (i.e. l). The new code, which may consist of
  226. * several instructions, is obtained by consulting a replacement
  227. * table.
  228. */
  229. line_p newcode;
  230. if (alloc->al_item->it_type == LOCALVAR) {
  231. if ((short) (alloc->al_dummy) == alloc->al_dummy) {
  232. TYPE(l) = OPSHORT;
  233. SHORT(l) = alloc->al_dummy;
  234. }
  235. else {
  236. TYPE(l) = OPOFFSET;
  237. OFFSET(l) = alloc->al_dummy;
  238. }
  239. } else {
  240. newcode = repl_code(l,alloc->al_dummy);
  241. replace_line(l,b,newcode);
  242. }
  243. }
  244. STATIC int loaditem_tab[NRITEMTYPES][2] =
  245. { /* WS 2 * WS */
  246. /*LOCALVAR*/ op_lol, op_ldl,
  247. /*LOCAL_ADDR*/ op_lal, op_lal,
  248. /*GLOBL_ADDR*/ op_lae, op_lae,
  249. /*PROC_ADDR*/ op_lpi, op_lpi,
  250. /*CONST*/ op_loc, op_nop,
  251. /*DCONST*/ op_nop, op_ldc
  252. };
  253. STATIC line_p load_item(item)
  254. item_p item;
  255. {
  256. /* Generate an EM instruction that loads the item on the stack */
  257. line_p l;
  258. switch (item->it_type) {
  259. case GLOBL_ADDR:
  260. l = newline(OPOBJECT);
  261. OBJ(l) = item->i_t.it_obj;
  262. break;
  263. case PROC_ADDR:
  264. l = newline(OPPROC);
  265. PROC(l) = item->i_t.it_proc;
  266. break;
  267. default:
  268. l = int_line(item->i_t.it_off);
  269. }
  270. l->l_instr = loaditem_tab[item->it_type][item->it_size == ws ? 0 : 1];
  271. assert(l->l_instr != op_nop);
  272. return l;
  273. }
  274. STATIC line_p store_local(size,off)
  275. short size;
  276. offset off;
  277. {
  278. line_p l = int_line(off);
  279. l->l_instr = (size == ws ? op_stl : op_sdl);
  280. return l;
  281. }
  282. STATIC line_p init_place(b)
  283. bblock_p b;
  284. {
  285. register line_p l,prev;
  286. prev = (line_p) 0;
  287. for (l = b->b_start; l != (line_p) 0; l = l->l_next) {
  288. switch(INSTR(l)) {
  289. case ps_mes:
  290. case ps_pro:
  291. case op_lab:
  292. break;
  293. default:
  294. return prev;
  295. }
  296. prev =l;
  297. }
  298. return prev;
  299. }
  300. STATIC append_code(l1,l2,b)
  301. line_p l1,l2;
  302. bblock_p b;
  303. {
  304. /* Append instruction l1 and l2 at begin of block b */
  305. line_p l;
  306. DLINK(l1,l2);
  307. l = init_place(b);
  308. if (l == (line_p) 0) {
  309. l2->l_next = b->b_start;
  310. b->b_start = l1;
  311. PREV(l1) = (line_p) 0;
  312. } else {
  313. l2->l_next = l->l_next;
  314. DLINK(l,l1);
  315. }
  316. if (l2->l_next != (line_p) 0) {
  317. PREV(l2->l_next) = l2;
  318. }
  319. }
  320. STATIC emit_init_code(list)
  321. alloc_p list;
  322. {
  323. /* Emit initialization code for all packed allocations.
  324. * This code looks like "dummy_local := item", e.g.
  325. * "LOC 25 ; STL -10" in EM terminology.
  326. */
  327. register alloc_p alloc,m;
  328. Lindex bi;
  329. bblock_p b;
  330. for (alloc = list; alloc != (alloc_p) 0; alloc = alloc->al_next) {
  331. for (m = alloc; m != (alloc_p) 0; m = m->al_mates) {
  332. for (bi = Lfirst(m->al_inits); bi != (Lindex) 0;
  333. bi = Lnext(bi,m->al_inits)) {
  334. /* "inits" contains all initialization points */
  335. b = (bblock_p) Lelem(bi);
  336. append_code(load_item(m->al_item),
  337. store_local(m->al_item->it_size,
  338. m->al_dummy),
  339. b);
  340. }
  341. }
  342. }
  343. }
  344. STATIC emit_mesregs(p,alloclist)
  345. proc_p p;
  346. alloc_p alloclist;
  347. {
  348. line_p l,m,x;
  349. alloc_p alloc;
  350. l = p->p_start->b_start;
  351. x = l->l_next;
  352. for (alloc = alloclist; alloc != (alloc_p) 0; alloc = alloc->al_next) {
  353. m = reg_mes(alloc->al_dummy,alloc->al_item->it_size,
  354. alloc->al_regtype,INFINITE);
  355. DLINK(l,m);
  356. l = m;
  357. }
  358. if (x != (line_p) 0) DLINK(l,x);
  359. }
  360. #define is_mesreg(l) (INSTR(l) == ps_mes && aoff(ARG(l),0) == ms_reg)
  361. rem_mes(p)
  362. proc_p p;
  363. {
  364. register bblock_p b;
  365. register line_p l,next;
  366. offset m;
  367. for (b = p->p_start; b != (bblock_p) 0; b = b->b_next) {
  368. for (l = b->b_start; l != (line_p) 0; l = next) {
  369. next = l->l_next;
  370. if (INSTR(l) == ps_mes
  371. && aoff(ARG(l),0) == ms_ego
  372. && ((m = aoff(ARG(l),1)) == ego_live
  373. || m == ego_dead)) {
  374. /* remove live/dead messages */
  375. rm_line(l,b);
  376. }
  377. }
  378. }
  379. }
  380. xform_proc(p,alloclist,nrinstrs,instrmap)
  381. proc_p p;
  382. alloc_p alloclist;
  383. short nrinstrs;
  384. line_p instrmap[];
  385. {
  386. /* Transform every instruction of procedure p that uses an item
  387. * at a point where the item is kept in a register.
  388. */
  389. register short now = 0;
  390. register line_p l,next;
  391. register bblock_p b;
  392. alloc_p alloc;
  393. for (b = p->p_start; b != (bblock_p) 0; b = b->b_next) {
  394. for (l = b->b_start; l != (line_p) 0; l = next) {
  395. next = l->l_next;
  396. if (is_mesreg(l) && ARG(l)->a_next != (arg_p) 0 &&
  397. aoff(ARG(l),4) != INFINITE) {
  398. /* All register messages for local variables
  399. * that were not assigned a register get
  400. * their 'count' fields* set to 0.
  401. */
  402. ARG(l)->a_next->a_next->a_next
  403. ->a_next->a_a.a_offset = 0;
  404. }
  405. if (is_item(l) &&
  406. (alloc = find_alloc(alloclist,l,now))
  407. != (alloc_p) 0 ) {
  408. apply_alloc(b,l,alloc);
  409. }
  410. now++;
  411. }
  412. }
  413. emit_init_code(alloclist);
  414. emit_mesregs(p,alloclist);
  415. rem_mes(p);
  416. }
  417. bool always_in_reg(off,allocs,size_out)
  418. offset off;
  419. alloc_p allocs;
  420. short *size_out;
  421. {
  422. /* See if the local variable with the given offset is stored
  423. * in a register during its entire lifetime. As a side effect,
  424. * return the size of the local.
  425. */
  426. alloc_p alloc,m;
  427. item_p item;
  428. for (alloc = allocs; alloc != (alloc_p) 0; alloc = alloc->al_next) {
  429. for (m = alloc; m != (alloc_p) 0; m = m->al_mates) {
  430. item = m->al_item;
  431. if (m->al_iswholeproc &&
  432. item->it_type == LOCALVAR &&
  433. item->i_t.it_off == off) {
  434. *size_out = item->it_size;
  435. return TRUE;
  436. }
  437. }
  438. }
  439. return FALSE;
  440. }
  441. rem_locals(p,allocs)
  442. proc_p p;
  443. alloc_p allocs;
  444. {
  445. /* Try to decrease the number of locals of procedure p, by
  446. * looking at which locals are always stored in a register.
  447. */
  448. offset nrlocals = p->p_localbytes;
  449. short size;
  450. while (nrlocals > 0) {
  451. /* A local can only be removed if all locals with
  452. * higher offsets are removed too.
  453. */
  454. if (always_in_reg(-nrlocals,allocs,&size)) {
  455. OUTVERBOSE("local %d removed from proc %d\n",
  456. nrlocals,p->p_id);
  457. nrlocals -= size;
  458. } else {
  459. break;
  460. }
  461. }
  462. p->p_localbytes = nrlocals;
  463. }
  464. rem_formals(p,allocs)
  465. proc_p p;
  466. alloc_p allocs;
  467. {
  468. /* Try to decrease the number of formals of procedure p, by
  469. * looking at which formals are always stored in a register.
  470. */
  471. offset nrformals = p->p_nrformals;
  472. offset off = 0;
  473. short size;
  474. if (nrformals == UNKNOWN_SIZE) return;
  475. while (off < nrformals) {
  476. if (always_in_reg(off,allocs,&size)) {
  477. OUTVERBOSE("formal %d removed from proc %d\n",
  478. off,p->p_id);
  479. off += size;
  480. } else {
  481. break;
  482. }
  483. }
  484. if (nrformals == off) {
  485. OUTVERBOSE("all formals of procedure %d removed\n",p->p_id,0);
  486. p->p_nrformals = 0;
  487. }
  488. }