cf.c 12 KB

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