ra_xform.c 12 KB

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