cf.c 13 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. /* C O N T R O L F L O W
  7. *
  8. * M A I N R O U T I N E
  9. */
  10. #include <stdlib.h>
  11. #include <stdio.h>
  12. #include <em_mnem.h>
  13. #include <em_pseu.h>
  14. #include <em_spec.h>
  15. #include <em_flag.h>
  16. #include <em_mes.h>
  17. #include "../share/types.h"
  18. #include "../share/debug.h"
  19. #include "../share/map.h"
  20. #include "../share/files.h"
  21. #include "../share/global.h"
  22. #include "../share/alloc.h"
  23. #include "../share/lset.h"
  24. #include "../share/cset.h"
  25. #include "../share/get.h"
  26. #include "../share/put.h"
  27. #include "../share/def.h"
  28. #include "cf.h"
  29. #include "cf_succ.h"
  30. #include "cf_idom.h"
  31. #include "cf_loop.h"
  32. #define newcfbx() (bext_p) newstruct(bext_cf)
  33. #define oldcfbx(x) oldstruct(bext_cf,x)
  34. extern char em_flag[];
  35. STATIC cset lpi_set; /* set of procedures used in LPI instruction */
  36. STATIC cset cai_set; /* set of all procedures doing a CAI */
  37. /* The procedure getbblocks reads the EM textfile and
  38. * partitions every procedure into a number of basic blocks.
  39. */
  40. #define LABEL0 0
  41. #define LABEL 1
  42. #define NORMAL 2
  43. #define JUMP 3
  44. #define END 4
  45. #define AFTERPRO 5
  46. #define INIT 6
  47. /* These global variables are used by getbblocks and nextblock. */
  48. STATIC bblock_p b, *bp; /* b is the current basic block, bp is
  49. * the address where the next block has
  50. * to be linked.
  51. */
  52. STATIC line_p lnp, *lp; /* lnp is the current line, lp is
  53. * the address where the next line
  54. * has to be linked.
  55. */
  56. STATIC short state; /* We use a finite state machine with the
  57. * following states:
  58. * LABEL0: after the first (successive)
  59. * instruction label.
  60. * LABEL1: after at least two successive
  61. * instruction labels.
  62. * NORMAL: after a normal instruction.
  63. * JUMP: after a branch (conditional,
  64. * unconditional or CSA/CSB).
  65. * END: after an END pseudo
  66. * AFTERPRO: after we've read a PRO pseudo
  67. * INIT: initial state
  68. */
  69. STATIC nextblock()
  70. {
  71. /* allocate a new basic block structure and
  72. * set b, bp and lp.
  73. */
  74. b = *bp = freshblock();
  75. bp = &b->b_next;
  76. b->b_start = lnp;
  77. b->b_succ = Lempty_set();
  78. b->b_pred = Lempty_set();
  79. b->b_extend = newcfbx(); /* basic block extension for CF */
  80. b->b_extend->bx_cf.bx_bucket = Lempty_set();
  81. b->b_extend->bx_cf.bx_semi = 0;
  82. lp = &lnp->l_next;
  83. #ifdef TRACE
  84. fprintf(stderr,"new basic block, id = %d\n",lastbid);
  85. #endif
  86. }
  87. STATIC short kind(lnp)
  88. line_p lnp;
  89. {
  90. /* determine if lnp is a label, branch, end or otherwise */
  91. short instr;
  92. byte flow;
  93. if ((instr = INSTR(lnp)) == op_lab) return (short) LABEL;
  94. if (instr == ps_end) return (short) END;
  95. if (instr > sp_lmnem) return (short) NORMAL; /* pseudo */
  96. if ((flow = (em_flag[instr-sp_fmnem] & EM_FLO)) == FLO_C ||
  97. flow == FLO_T) return (short) JUMP; /* conditional/uncond. jump */
  98. return (short) NORMAL;
  99. }
  100. STATIC line_p doread_line(p_out)
  101. proc_p *p_out;
  102. {
  103. /* read a line, and check pseudos for procedure addresses */
  104. register line_p lnp = read_line(p_out);
  105. if (lnp && TYPE(lnp) == OPLIST && INSTR(lnp) != ps_mes) {
  106. register arg_p arg = ARG(lnp);
  107. while (arg) {
  108. if (arg->a_type == ARGPROC) {
  109. Cadd(arg->a_a.a_proc->p_id, &lpi_set);
  110. arg->a_a.a_proc->p_flags1 |= PF_LPI;
  111. }
  112. arg = arg->a_next;
  113. }
  114. }
  115. return lnp;
  116. }
  117. STATIC bool getbblocks(fp,kind_out,n_out,g_out,l_out)
  118. FILE *fp;
  119. short *kind_out;
  120. short *n_out;
  121. bblock_p *g_out;
  122. line_p *l_out;
  123. {
  124. bblock_p head = (bblock_p) 0;
  125. line_p headl = (line_p) 0;
  126. curproc = (proc_p) 0;
  127. /* curproc will get a value when we encounter a PRO pseudo.
  128. * If there is no such pseudo, we're reading only data
  129. * declarations or messages (outside any proc.).
  130. */
  131. curinp = fp;
  132. lastbid = (block_id) 0; /* block identier */
  133. state = INIT; /* initial state */
  134. bp = &head;
  135. for (;;) {
  136. #ifdef TRACE
  137. fprintf(stderr,"state = %d\n",state);
  138. #endif
  139. switch(state) {
  140. case LABEL0:
  141. nextblock();
  142. /* Fall through !! */
  143. case LABEL:
  144. lbmap[INSTRLAB(lnp)] = b;
  145. /* The lbmap table contains for each
  146. * label_id the basic block of that label.
  147. */
  148. lnp = doread_line(&curproc);
  149. state = kind(lnp);
  150. if (state != END) {
  151. *lp = lnp;
  152. lp = &lnp->l_next;
  153. }
  154. break;
  155. case NORMAL:
  156. lnp = doread_line(&curproc);
  157. if ( (state = kind(lnp)) == LABEL) {
  158. /* If we come accross a label
  159. * here, it must be the beginning
  160. * of a new basic block.
  161. */
  162. state = LABEL0;
  163. } else {
  164. if (state != END) {
  165. *lp = lnp;
  166. lp = &lnp->l_next;
  167. }
  168. }
  169. break;
  170. case JUMP:
  171. lnp = doread_line(&curproc);
  172. /* fall through ... */
  173. case AFTERPRO:
  174. switch(state = kind(lnp)) {
  175. case LABEL:
  176. state = LABEL0;
  177. break;
  178. case JUMP:
  179. case NORMAL:
  180. nextblock();
  181. break;
  182. }
  183. break;
  184. case END:
  185. *lp = lnp;
  186. #ifdef TRACE
  187. fprintf(stderr,"at end of proc, %d blocks\n",lastbid);
  188. #endif
  189. if (head == (bblock_p) 0) {
  190. *kind_out = LDATA;
  191. *l_out = headl;
  192. } else {
  193. *kind_out = LTEXT;
  194. *g_out = head;
  195. *n_out = (short) lastbid;
  196. /* number of basic blocks */
  197. }
  198. return TRUE;
  199. case INIT:
  200. lnp = doread_line(&curproc);
  201. if (feof(curinp)) return FALSE;
  202. if (INSTR(lnp) == ps_pro) {
  203. state = AFTERPRO;
  204. } else {
  205. state = NORMAL;
  206. headl = lnp;
  207. lp = &lnp->l_next;
  208. }
  209. break;
  210. }
  211. }
  212. }
  213. STATIC interproc_analysis(p)
  214. proc_p p;
  215. {
  216. /* Interprocedural analysis of a procedure p determines:
  217. * - all procedures called by p (the 'call graph')
  218. * - the set of objects changed by p (directly)
  219. * - whether p does a load-indirect (loi,lof etc.)
  220. * - whether p does a store-indirect (sti, stf etc.)
  221. * The changed/used variables information will be
  222. * transitively closed, i.e. if P calls Q and Q changes
  223. * a variable X, the P changes X too.
  224. * (The same applies for used variables and for use/store
  225. * indirect).
  226. * The transitive closure will be computed by main
  227. * after all procedures have been processed.
  228. */
  229. bblock_p b;
  230. line_p lnp;
  231. bool inloop;
  232. /* Allocate memory for structs and sets */
  233. p->p_use = newuse();
  234. p->p_change = newchange();
  235. p->p_change->c_ext = Cempty_set(olength);
  236. p->p_calling = Cempty_set(plength);
  237. for (b = p->p_start; b != (bblock_p) 0; b = b->b_next) {
  238. inloop = (Lnrelems(b->b_loops) > 0);
  239. for (lnp = b->b_start; lnp != (line_p) 0; lnp = lnp->l_next) {
  240. /* for all instructions of p do */
  241. switch(INSTR(lnp)) {
  242. case op_cal:
  243. Cadd(PROC(lnp)->p_id, &p->p_calling);
  244. /* add called proc to p_calling */
  245. if (inloop) {
  246. CALLED_IN_LOOP(PROC(lnp));
  247. }
  248. break;
  249. case op_cai:
  250. Cadd(p->p_id,&cai_set);
  251. break;
  252. case op_lpi:
  253. Cadd(PROC(lnp)->p_id, &lpi_set);
  254. /* All procedures that have their names used
  255. * in an lpi instruction, may be called via
  256. * a cai instruction.
  257. */
  258. PROC(lnp)->p_flags1 |= PF_LPI;
  259. break;
  260. case op_ste:
  261. case op_sde:
  262. case op_ine:
  263. case op_dee:
  264. case op_zre:
  265. Cadd(OBJ(lnp)->o_id, &p->p_change->c_ext);
  266. /* Add changed object to c_ext */
  267. break;
  268. case op_lil:
  269. case op_lof:
  270. case op_loi:
  271. case op_los:
  272. case op_lar:
  273. p->p_use->u_flags |= UF_INDIR;
  274. /* p does a load-indirect */
  275. break;
  276. case op_sil:
  277. case op_stf:
  278. case op_sti:
  279. case op_sts:
  280. case op_sar:
  281. p->p_change->c_flags |= CF_INDIR;
  282. /* p does a store-indirect */
  283. break;
  284. case op_blm:
  285. case op_bls:
  286. p->p_use->u_flags |= UF_INDIR;
  287. p->p_change->c_flags |= CF_INDIR;
  288. /* p does both */
  289. break;
  290. case op_mon:
  291. printf("mon not yet implemented\n");
  292. break;
  293. case op_lxl:
  294. case op_lxa:
  295. curproc->p_flags1 |= PF_ENVIRON;
  296. break;
  297. case op_lor:
  298. case op_str:
  299. if (SHORT(lnp) == 0) {
  300. curproc->p_flags1 |= PF_ENVIRON;
  301. }
  302. break;
  303. case ps_mes:
  304. if (aoff(ARG(lnp),0) == ms_gto) {
  305. ENTERED_WITH_GTO(curproc);
  306. }
  307. break;
  308. }
  309. }
  310. }
  311. }
  312. STATIC cf_cleanproc(p)
  313. proc_p p;
  314. {
  315. /* Remove the extended data structures of p */
  316. register bblock_p b;
  317. register Lindex pi;
  318. loop_p lp;
  319. for (b = p->p_start; b != (bblock_p) 0; b = b->b_next) {
  320. oldcfbx(b->b_extend);
  321. }
  322. for (pi = Lfirst(p->p_loops); pi != (Lindex) 0; pi = Lnext(pi,
  323. p->p_loops)) {
  324. lp = (loop_p) Lelem(pi);
  325. oldcflpx(lp->lp_extend);
  326. }
  327. }
  328. #define CH_CHANGE_INDIR(ch) ((ch->c_flags & CF_INDIR) != 0)
  329. #define USE_INDIR(us) ((us->u_flags & UF_INDIR) != 0)
  330. #define CALLS_UNKNOWN(p) (p->p_flags1 & (byte) PF_CALUNKNOWN)
  331. #define ENVIRON(p) (p->p_flags1 & (byte) PF_ENVIRON)
  332. STATIC bool add_info(q,p)
  333. proc_p q,p;
  334. {
  335. /* Determine the consequences for used/changed variables info
  336. * of the fact that p calls q. If e.g. q changes a variable X
  337. * then p changes this variable too. This routine is an
  338. * auxiliary routine of the transitive closure process.
  339. * The returned value indicates if there was any change in
  340. * the information of p.
  341. */
  342. change_p chp, chq;
  343. use_p usp, usq;
  344. bool diff = FALSE;
  345. chp = p->p_change;
  346. chq = q->p_change;
  347. usp = p->p_use;
  348. usq = q->p_use;
  349. if (!BODY_KNOWN(q)) {
  350. /* q is a procedure of which the body is not available
  351. * as EM text.
  352. */
  353. if (CALLS_UNKNOWN(p)) {
  354. return FALSE;
  355. /* p already called an unknown procedure */
  356. } else {
  357. p->p_flags1 |= PF_CALUNKNOWN;
  358. return TRUE;
  359. }
  360. }
  361. if (CALLS_UNKNOWN(q)) {
  362. /* q calls a procedure of which the body is not available
  363. * as EM text.
  364. */
  365. if (!CALLS_UNKNOWN(p)) {
  366. p->p_flags1 |= PF_CALUNKNOWN;
  367. diff = TRUE;
  368. }
  369. }
  370. if (IS_CALLED_IN_LOOP(p) && !IS_CALLED_IN_LOOP(q)) {
  371. CALLED_IN_LOOP(q);
  372. diff = TRUE;
  373. }
  374. if (!Cis_subset(chq->c_ext, chp->c_ext)) {
  375. /* q changes global variables (objects) that
  376. * p did not (yet) change. Add all variables
  377. * changed by q to the c_ext set of p.
  378. */
  379. Cjoin(chq->c_ext, &chp->c_ext);
  380. diff = TRUE;
  381. }
  382. if (CH_CHANGE_INDIR(chq) && !CH_CHANGE_INDIR(chp)) {
  383. /* q does a change-indirect (sil etc.)
  384. * and p did not (yet).
  385. */
  386. chp->c_flags |= CF_INDIR;
  387. diff = TRUE;
  388. }
  389. if (USE_INDIR(usq) && !USE_INDIR(usp)) {
  390. /* q does a use-indirect (lil etc.)
  391. * and p dis not (yet).
  392. */
  393. usp->u_flags |= UF_INDIR;
  394. diff = TRUE;
  395. }
  396. if (ENVIRON(q) && !ENVIRON(p)) {
  397. /* q uses or changes local variables in its
  398. * environment while p does not (yet).
  399. */
  400. p->p_flags1 |= PF_ENVIRON;
  401. diff = TRUE;
  402. }
  403. return diff;
  404. }
  405. STATIC trans_clos(head)
  406. proc_p head;
  407. {
  408. /* Compute the transitive closure of the used/changed
  409. * variable information.
  410. */
  411. register proc_p p,q;
  412. Cindex i;
  413. bool changes = TRUE;
  414. while(changes) {
  415. changes = FALSE;
  416. for (p = head; p != (proc_p) 0; p = p->p_next) {
  417. if (!BODY_KNOWN(p)) continue;
  418. for (i = Cfirst(p->p_calling); i != (Cindex) 0;
  419. i = Cnext(i,p->p_calling)) {
  420. q = pmap[Celem(i)];
  421. if (add_info(q,p)) {
  422. changes = TRUE;
  423. }
  424. }
  425. }
  426. }
  427. }
  428. indir_calls()
  429. {
  430. Cindex i;
  431. proc_p p;
  432. for (i = Cfirst(cai_set); i != (Cindex) 0; i = Cnext(i,cai_set)) {
  433. p = pmap[Celem(i)]; /* p does a CAI */
  434. Cjoin(lpi_set, &p->p_calling);
  435. }
  436. Cdeleteset(lpi_set);
  437. Cdeleteset(cai_set);
  438. }
  439. main(argc,argv)
  440. int argc;
  441. char *argv[];
  442. {
  443. FILE *f, *f2, *gf2; /* The EM input, EM output, basic block output */
  444. bblock_p g;
  445. short n, kind;
  446. line_p l;
  447. linecount = 0;
  448. fproc = getptable(pname); /* proc table */
  449. fdblock = getdtable(dname); /* data block table */
  450. lpi_set = Cempty_set(plength);
  451. cai_set = Cempty_set(plength);
  452. if ((f = fopen(lname,"r")) == NULL) {
  453. error("cannot open %s", lname);
  454. }
  455. if ((f2 = fopen(lname2,"w")) == NULL) {
  456. error("cannot open %s", lname2);
  457. }
  458. if ((gf2 = fopen(bname2,"w")) == NULL) {
  459. error("cannot open %s",bname2);
  460. }
  461. while (getbblocks(f,&kind,&n,&g,&l)) {
  462. /* read EM text of one unit and
  463. * (if it is a procedure)
  464. * partition it into n basic blocks.
  465. */
  466. if (kind == LDATA) {
  467. putunit(LDATA,(proc_p) 0,l,gf2,f2);
  468. } else {
  469. curproc->p_start = g;
  470. /* The global variable curproc points to the
  471. * current procedure. It is set by getbblocks
  472. */
  473. control_flow(g); /* compute pred and succ */
  474. dominators(g,n); /* compute immediate dominators */
  475. loop_detection(curproc); /* compute loops */
  476. interproc_analysis(curproc);
  477. /* Interprocedural analysis */
  478. cf_cleanproc(curproc);
  479. putunit(LTEXT,curproc,(line_p) 0,gf2,f2);
  480. /* output control flow graph + text */
  481. }
  482. }
  483. fclose(f);
  484. fclose(f2);
  485. fclose(gf2);
  486. indir_calls();
  487. trans_clos(fproc);
  488. /* Compute transitive closure of used/changed
  489. * variables information for every procedure.
  490. */
  491. if ((f = fopen(dname2,"w")) == NULL) {
  492. error("cannot open %s",dname2);
  493. }
  494. putdtable(fdblock,f);
  495. if ((f = fopen(pname2,"w")) == NULL) {
  496. error("cannot open %s",pname2);
  497. }
  498. putptable(fproc,f,TRUE);
  499. exit(0);
  500. }