lv.c 12 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587
  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. /* L I V E V A R I A B L E S A N A L Y S I S */
  7. #include <stdlib.h>
  8. #include <stdio.h>
  9. #include <em_mnem.h>
  10. #include <em_pseu.h>
  11. #include <em_spec.h>
  12. #include <em_mes.h>
  13. #include <em_ego.h>
  14. #include "../share/types.h"
  15. #include "lv.h"
  16. #include "../share/debug.h"
  17. #include "../share/global.h"
  18. #include "../share/lset.h"
  19. #include "../share/cset.h"
  20. #include "../share/def.h"
  21. #include "../share/files.h"
  22. #include "../share/alloc.h"
  23. #include "../share/map.h"
  24. #include "../share/get.h"
  25. #include "../share/put.h"
  26. #include "../share/aux.h"
  27. #include "../share/init_glob.h"
  28. #include "../share/locals.h"
  29. #include "../share/go.h"
  30. #include "../share/parser.h"
  31. #define newlvbx() (bext_p) newstruct(bext_lv)
  32. #define oldlvbx(x) oldstruct(bext_lv,x)
  33. short nrglobals;
  34. short nrvars;
  35. static int Slv;
  36. static bool mesgflag = FALSE; /* Suppress generation of live/dead info */
  37. static void app_block(line_p l, bblock_p b);
  38. static void clean_up()
  39. {
  40. local_p *p;
  41. for (p = &locals[1]; p <= &locals[nrlocals]; p++) {
  42. oldlocal(*p);
  43. }
  44. oldmap((short **)locals,nrlocals);
  45. }
  46. static bool is_dir_use(line_p l)
  47. {
  48. /* See if l is a direct use of some variable
  49. * (i.e. not through a pointer). A LIL is a
  50. * direct use of some pointer variable
  51. * (and an indirect use of some other variable).
  52. * A SIL is also a direct use.
  53. * A LOI, however, is not an direct use of a variable.
  54. * An an increment/decrement instruction is regarded
  55. * as a use here, and not as a definition, as the
  56. * variable is first used and than defined.
  57. */
  58. switch(INSTR(l)) {
  59. case op_dee:
  60. case op_del:
  61. case op_ine:
  62. case op_inl:
  63. case op_lde:
  64. case op_ldl:
  65. case op_lil:
  66. case op_loe:
  67. case op_lol:
  68. case op_sil:
  69. return TRUE;
  70. default:
  71. return FALSE;
  72. }
  73. /* NOTREACHED */
  74. }
  75. static bool is_indir_use(line_p l)
  76. {
  77. /* See if instruction l uses some variable(s) indirectly,
  78. * i.e. through a pointer or via a procedure call.
  79. */
  80. switch(INSTR(l)) {
  81. case op_blm:
  82. case op_bls:
  83. case op_cai:
  84. case op_cal:
  85. case op_lar:
  86. case op_ldf:
  87. case op_lil:
  88. case op_lof:
  89. case op_loi:
  90. case op_los:
  91. case op_mon:
  92. return TRUE;
  93. default:
  94. return FALSE;
  95. }
  96. /* NOTREACHED */
  97. return 0;
  98. }
  99. static bool is_def(line_p l)
  100. {
  101. /* See if l does a direct definition */
  102. switch(INSTR(l)) {
  103. case op_sde:
  104. case op_sdl:
  105. case op_ste:
  106. case op_stl:
  107. case op_zre:
  108. case op_zrl:
  109. return TRUE;
  110. default:
  111. return FALSE;
  112. }
  113. /* NOTREACHED */
  114. return 0;
  115. }
  116. static void def_use(proc_p p)
  117. {
  118. /* Compute DEF(b) and USE(b), for every basic block b
  119. * of procedure p. DEF(b) contains the variables that
  120. * are certain to be defined (assigned) in b
  121. * before being used. USE(b) contains the variables
  122. * that may be used in b, before being defined.
  123. * (Note that uncertainty arises in the presence of
  124. * pointers and procedure calls).
  125. * We compute these sets, by scanning the text of
  126. * the basic block from beginning till end.
  127. */
  128. bblock_p b;
  129. line_p l;
  130. short v;
  131. bool found;
  132. cset all_ind_uses;
  133. all_ind_uses = Cempty_set(nrvars);
  134. for (v = 1; v < nrlocals; v++) {
  135. if (!IS_REGVAR(locals[v])) {
  136. Cadd(LOC_TO_VARNR(v),&all_ind_uses);
  137. }
  138. }
  139. for (b = p->p_start; b != (bblock_p) 0; b = b->b_next) {
  140. USE(b) = Cempty_set(nrvars);
  141. DEF(b) = Cempty_set(nrvars);
  142. for (l = b->b_start; l != (line_p) 0; l = l->l_next) {
  143. if (is_def(l)) {
  144. /* An direct definition (i.e. not
  145. * through a pointer).
  146. */
  147. var_nr(l,&v,&found);
  148. if (found && !Cis_elem(v,USE(b))) {
  149. /* We do maintain live-dead info
  150. * for this variable, and it was
  151. * not used earlier in b.
  152. */
  153. Cadd(v, &DEF(b));
  154. }
  155. } else {
  156. if (is_dir_use(l)) {
  157. var_nr(l,&v,&found);
  158. if (found && !Cis_elem(v,DEF(b))) {
  159. Cadd(v, &USE(b));
  160. }
  161. }
  162. if (is_indir_use(l)) {
  163. /* Add variable that may be used
  164. * by l to USE(b).
  165. */
  166. Cjoin(all_ind_uses,&USE(b));
  167. }
  168. }
  169. }
  170. }
  171. Cdeleteset(all_ind_uses);
  172. }
  173. static void unite_ins(lset bbset, cset *setp)
  174. {
  175. /* Take the union of L_IN(b), for all b in bbset,
  176. * and put the result in setp.
  177. */
  178. Lindex i;
  179. Cclear_set(setp);
  180. for (i = Lfirst(bbset); i != (Lindex) 0; i = Lnext(i,bbset)) {
  181. Cjoin(L_IN((bblock_p) Lelem(i)), setp);
  182. }
  183. }
  184. static void solve_lv(proc_p p)
  185. {
  186. /* Solve the data flow equations for Live Variables,
  187. * for procedure p. These equations are:
  188. * (1) IN[b] = OUT[b] - DEF[b] + USE[b]
  189. * (2) OUT(b) = IN(s1) + ... + IN(sn) ;
  190. * where SUCC(b) = {s1, ... , sn}
  191. */
  192. register bblock_p b;
  193. cset newout = Cempty_set(nrvars);
  194. bool change = TRUE;
  195. for (b = p->p_start; b != (bblock_p) 0; b = b->b_next) {
  196. L_IN(b) = Cempty_set(nrvars);
  197. Ccopy_set(USE(b), &L_IN(b));
  198. L_OUT(b) = Cempty_set(nrvars);
  199. }
  200. while (change) {
  201. change = FALSE;
  202. for (b = p->p_start; b != (bblock_p) 0; b = b->b_next) {
  203. unite_ins(b->b_succ,&newout);
  204. if (!Cequal(newout,L_OUT(b))) {
  205. change = TRUE;
  206. Ccopy_set(newout, &L_OUT(b));
  207. Ccopy_set(newout, &L_IN(b));
  208. Csubtract(DEF(b), &L_IN(b));
  209. Cjoin(USE(b), &L_IN(b));
  210. }
  211. }
  212. }
  213. Cdeleteset(newout);
  214. }
  215. static void live_variables_analysis(proc_p p)
  216. {
  217. make_localtab(p);
  218. nrvars = nrglobals + nrlocals;
  219. def_use(p);
  220. solve_lv(p);
  221. }
  222. static void init_live_dead(bblock_p b)
  223. {
  224. /* For every register variable, see if it is
  225. * live or dead at the end of b.
  226. */
  227. short v;
  228. local_p loc;
  229. for (v = 1; v <= nrlocals; v++) {
  230. loc = locals[v];
  231. if (IS_REGVAR(loc) && Cis_elem(LOC_TO_VARNR(v),L_OUT(b))) {
  232. LIVE(loc);
  233. } else {
  234. DEAD(loc);
  235. }
  236. }
  237. }
  238. static line_p make_mesg(short mesg,local_p loc)
  239. {
  240. /* Create a line for a message stating that
  241. * local variable loc is live/dead. This message
  242. * looks like: "mes ms_ego,ego_live,off,size" or
  243. * "mes ms_ego,ego_dead,off,size".
  244. */
  245. line_p l = newline(OPLIST);
  246. arg_p ap;
  247. l->l_instr = ps_mes;
  248. ap = ARG(l) = newarg(ARGOFF);
  249. ap->a_a.a_offset = ms_ego;
  250. ap = ap->a_next = newarg(ARGOFF);
  251. ap->a_a.a_offset = mesg;
  252. ap = ap->a_next = newarg(ARGOFF);
  253. ap->a_a.a_offset = loc->lc_off;
  254. ap = ap->a_next = newarg(ARGOFF);
  255. ap->a_a.a_offset = loc->lc_size;
  256. return l;
  257. }
  258. static void block_entry(bblock_p b, bblock_p prev)
  259. {
  260. short v,vn;
  261. local_p loc;
  262. bool was_live, is_live;
  263. /* Generate a live/dead message for every register variable that
  264. * was live at the end of prev, but dead at the beginning of b,
  265. * or v.v. If prev = 0 (i.e. begin of procedure), parameters were
  266. * live, normal local variables were dead.
  267. */
  268. for (v = 1; v <= nrlocals; v++) {
  269. loc = locals[v];
  270. if (IS_REGVAR(loc)) {
  271. vn = LOC_TO_VARNR(v);
  272. if (prev == (bblock_p) 0) {
  273. was_live = loc->lc_off >= 0;
  274. } else {
  275. was_live = Cis_elem(vn,L_OUT(prev));
  276. }
  277. is_live = Cis_elem(vn,L_IN(b));
  278. if (was_live != is_live) {
  279. app_block(make_mesg((is_live?ego_live:ego_dead),loc),b);
  280. }
  281. }
  282. }
  283. }
  284. static void app_block(line_p l, bblock_p b)
  285. {
  286. line_p x = b->b_start;
  287. if (x != (line_p) 0 && INSTR(x) == ps_pro) {
  288. /* start of procedure; append after pro pseudo ! */
  289. if ((l->l_next = x->l_next) != (line_p) 0) {
  290. PREV(l->l_next) = l;
  291. }
  292. x->l_next = l;
  293. PREV(l) = x;
  294. } else {
  295. if ((l->l_next = x) != (line_p) 0) {
  296. PREV(l->l_next) = l;
  297. }
  298. b->b_start = l;
  299. PREV(l) = (line_p) 0;
  300. }
  301. }
  302. static void definition(line_p l, bool *useless_out, short *v_out, bool mesgflag)
  303. {
  304. /* Process a definition. If the defined (register-) variable
  305. * is live after 'l', then create a live-message and put
  306. * it after 'l'.
  307. */
  308. short v;
  309. bool found;
  310. local_p loc;
  311. *useless_out = FALSE;
  312. var_nr(l,&v,&found);
  313. if (found && IS_LOCAL(v)) {
  314. *v_out = v;
  315. loc = locals[TO_LOCAL(v)];
  316. if (IS_REGVAR(loc)) {
  317. /* Tricky stuff here. Make sure that a variable
  318. that is assigned to is alive, at least for
  319. a very very short time. Otherwize, the
  320. register allocation pass might think that it
  321. is never alive, and (incorrectly) use the
  322. same register for this variable as for
  323. another variable, that is alive at this point.
  324. If this variable is dead after the assignment,
  325. the two messages (ego_live, ego_dead) are right
  326. after each other. Luckily, this IS an interval.
  327. */
  328. if (!mesgflag) {
  329. appnd_line(make_mesg(ego_live,loc), l);
  330. l = l->l_next;
  331. }
  332. if (IS_LIVE(loc)) {
  333. DEAD(loc);
  334. } else {
  335. if (!mesgflag) {
  336. appnd_line(make_mesg(ego_dead, loc), l);
  337. }
  338. *useless_out = TRUE;
  339. }
  340. }
  341. }
  342. }
  343. static void use(line_p l, bool mesgflag)
  344. {
  345. /* Process a use. If the defined (register-) variable
  346. * is dead after 'l', then create a dead-message and put
  347. * it after 'l'.
  348. */
  349. short v;
  350. bool found;
  351. local_p loc;
  352. var_nr(l,&v,&found);
  353. if (found && IS_LOCAL(v)) {
  354. loc = locals[TO_LOCAL(v)];
  355. if (IS_REGVAR(loc) && IS_DEAD(loc)) {
  356. if (!mesgflag) {
  357. appnd_line(make_mesg(ego_dead,loc), l);
  358. }
  359. LIVE(loc);
  360. }
  361. }
  362. }
  363. static void nothing() { } /* No action to be undertaken at level 0 of parser */
  364. static void rem_code(line_p l1, line_p l2, bblock_p b)
  365. {
  366. line_p l,x,y,next;
  367. x = PREV(l1);
  368. y = l2->l_next;
  369. for (l = l1; l != l2; l = next) {
  370. next = l->l_next;
  371. oldline(l);
  372. }
  373. if (x == (line_p) 0) {
  374. b->b_start = y;
  375. } else {
  376. x->l_next = y;
  377. }
  378. if (y != (line_p) 0) {
  379. PREV(y) = x;
  380. }
  381. }
  382. #define SIZE(v) ((offset) locals[TO_LOCAL(v)]->lc_size)
  383. void lv_mesg(proc_p p, bool mesgflag)
  384. {
  385. /* Create live/dead messages for every possible register
  386. * variable of p. A dead-message is put after a "use" of
  387. * such a variable, if the variable becomes dead just
  388. * after the use (i.e. this was its last use).
  389. * A live message is put after a "definition" of such
  390. * a variable, if the variable becomes live just
  391. * after the definition (which will usually be the case).
  392. * We traverse every basic block b of p from the last
  393. * instruction of b backwards to the beginning of b.
  394. * Initially, all variables that are dead at the end
  395. * of b are marked dead. All others are marked live.
  396. * If we come accross a definition of a variable X that
  397. * was marked live, we put a live-message after the
  398. * definition and mark X dead.
  399. * If we come accross a use of a variable X that
  400. * was marked dead, we put a dead-message after the
  401. * use and mark X live.
  402. * So at any point, the mark of X tells whether X is
  403. * live or dead immediately before (!) that point.
  404. * We also generate a message at the start of a basic block
  405. * for every variable that was live at the end of the (textually)
  406. * previous block, but dead at the entry of this block, or v.v.
  407. * On the fly, useless assignments are removed.
  408. */
  409. bblock_p b;
  410. line_p l;
  411. line_p lnp, prev;
  412. bblock_p prevb = (bblock_p) 0;
  413. short v;
  414. bool useless;
  415. for (b = p->p_start; b != (bblock_p) 0; b = b->b_next) {
  416. block_entry(b,prevb); /* generate message at head of block */
  417. prevb = b;
  418. if (!mesgflag) {
  419. init_live_dead(b);
  420. }
  421. for (l = last_instr(b); l != (line_p) 0; l = prev) {
  422. /* traverse backwards! */
  423. prev = PREV(l);
  424. if (is_def(l)) {
  425. definition(l,&useless,&v,mesgflag);
  426. if (useless && /* assignment to dead var. */
  427. parse(prev,SIZE(v),&lnp,0,nothing)) {
  428. /* The code "VAR := expression" can
  429. * be removed. 'l' is the "STL VAR",
  430. * lnp is the beginning of the EM code
  431. * for the expression.
  432. */
  433. prev = PREV(lnp);
  434. rem_code(lnp,l,b);
  435. OUTVERBOSE("useless assignment ,proc %d,local %d", curproc->p_id,
  436. (int) locals[TO_LOCAL(v)]->lc_off);
  437. Slv++;
  438. }
  439. else {
  440. }
  441. } else {
  442. if (is_dir_use(l)) {
  443. use(l,mesgflag);
  444. }
  445. }
  446. }
  447. }
  448. }
  449. static void lv_extend(proc_p p)
  450. {
  451. /* Allocate extended data structures for Use Definition analysis */
  452. bblock_p b;
  453. for (b = p->p_start; b != (bblock_p) 0; b = b->b_next) {
  454. b->b_extend = newlvbx();
  455. }
  456. }
  457. static void lv_cleanup(proc_p p)
  458. {
  459. /* Deallocate extended data structures for Use Definition analysis */
  460. bblock_p b;
  461. for (b = p->p_start; b != (bblock_p) 0; b = b->b_next) {
  462. Cdeleteset(USE(b));
  463. Cdeleteset(DEF(b));
  464. Cdeleteset(L_IN(b));
  465. Cdeleteset(L_OUT(b));
  466. oldlvbx(b->b_extend);
  467. }
  468. }
  469. int lv_flags(void *param)
  470. {
  471. char *p = (char *)param;
  472. switch(*p) {
  473. case 'N':
  474. mesgflag = TRUE;
  475. break;
  476. }
  477. return 0;
  478. }
  479. int lv_optimize(void *param)
  480. {
  481. proc_p p = (proc_p)param;
  482. if (IS_ENTERED_WITH_GTO(p)) return 0;
  483. locals = (local_p *) 0;
  484. lv_extend(p);
  485. live_variables_analysis(p);
  486. lv_mesg(p,mesgflag);
  487. /* generate live-dead messages for regvars */
  488. lv_cleanup(p);
  489. clean_up();
  490. return 0;
  491. }
  492. int main(int argc,char *argv[])
  493. {
  494. go(argc,argv,init_globals,lv_optimize,no_action,lv_flags);
  495. report("useless assignments deleted",Slv);
  496. exit(0);
  497. }