123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545 |
- /* $Id$ */
- /*
- * (c) copyright 1987 by the Vrije Universiteit, Amsterdam, The Netherlands.
- * See the copyright notice in the ACK home directory, in the file "Copyright".
- */
- /* C O N T R O L F L O W
- *
- * M A I N R O U T I N E
- */
- #include <stdlib.h>
- #include <stdio.h>
- #include <em_mnem.h>
- #include <em_pseu.h>
- #include <em_spec.h>
- #include <em_flag.h>
- #include <em_mes.h>
- #include "../share/types.h"
- #include "../share/debug.h"
- #include "../share/map.h"
- #include "../share/files.h"
- #include "../share/global.h"
- #include "../share/alloc.h"
- #include "../share/lset.h"
- #include "../share/cset.h"
- #include "../share/get.h"
- #include "../share/put.h"
- #include "../share/def.h"
- #include "../share/aux.h"
- #include "cf.h"
- #include "cf_succ.h"
- #include "cf_idom.h"
- #include "cf_loop.h"
- #define newcfbx() (bext_p) newstruct(bext_cf)
- #define oldcfbx(x) oldstruct(bext_cf,x)
- extern char em_flag[];
- static cset lpi_set; /* set of procedures used in LPI instruction */
- static cset cai_set; /* set of all procedures doing a CAI */
- /* The procedure getbblocks reads the EM textfile and
- * partitions every procedure into a number of basic blocks.
- */
- #define LABEL0 0
- #define LABEL 1
- #define NORMAL 2
- #define JUMP 3
- #define END 4
- #define AFTERPRO 5
- #define INIT 6
- /* These global variables are used by getbblocks and nextblock. */
- static bblock_p b, *bp; /* b is the current basic block, bp is
- * the address where the next block has
- * to be linked.
- */
- static line_p lnp, *lp; /* lnp is the current line, lp is
- * the address where the next line
- * has to be linked.
- */
- static short state; /* We use a finite state machine with the
- * following states:
- * LABEL0: after the first (successive)
- * instruction label.
- * LABEL1: after at least two successive
- * instruction labels.
- * NORMAL: after a normal instruction.
- * JUMP: after a branch (conditional,
- * unconditional or CSA/CSB).
- * END: after an END pseudo
- * AFTERPRO: after we've read a PRO pseudo
- * INIT: initial state
- */
- static void nextblock()
- {
- /* allocate a new basic block structure and
- * set b, bp and lp.
- */
- b = *bp = freshblock();
- bp = &b->b_next;
- b->b_start = lnp;
- b->b_succ = Lempty_set();
- b->b_pred = Lempty_set();
- b->b_extend = newcfbx(); /* basic block extension for CF */
- b->b_extend->bx_cf.bx_bucket = Lempty_set();
- b->b_extend->bx_cf.bx_semi = 0;
- lp = &lnp->l_next;
- #ifdef TRACE
- fprintf(stderr,"new basic block, id = %d\n",lastbid);
- #endif
- }
- static short kind(line_p lnp)
- {
- /* determine if lnp is a label, branch, end or otherwise */
- short instr;
- byte flow;
- if ((instr = INSTR(lnp)) == op_lab) return (short) LABEL;
- if (instr == ps_end) return (short) END;
- if (instr > sp_lmnem) return (short) NORMAL; /* pseudo */
- if ((flow = (em_flag[instr-sp_fmnem] & EM_FLO)) == FLO_C ||
- flow == FLO_T) return (short) JUMP; /* conditional/uncond. jump */
- return (short) NORMAL;
- }
- static line_p doread_line(proc_p *p_out)
- {
- /* read a line, and check pseudos for procedure addresses */
- line_p lnp = read_line(p_out);
- if (lnp && TYPE(lnp) == OPLIST && INSTR(lnp) != ps_mes) {
- arg_p arg = ARG(lnp);
-
- while (arg) {
- if (arg->a_type == ARGPROC) {
- Cadd(arg->a_a.a_proc->p_id, &lpi_set);
- arg->a_a.a_proc->p_flags1 |= PF_LPI;
- }
- arg = arg->a_next;
- }
- }
- return lnp;
- }
- static bool getbblocks(FILE *fp, short *kind_out, short *n_out, bblock_p *g_out, line_p *l_out)
- {
- bblock_p head = (bblock_p) 0;
- line_p headl = (line_p) 0;
- curproc = (proc_p) 0;
- /* curproc will get a value when we encounter a PRO pseudo.
- * If there is no such pseudo, we're reading only data
- * declarations or messages (outside any proc.).
- */
- curinp = fp;
- lastbid = (block_id) 0; /* block identier */
- state = INIT; /* initial state */
- bp = &head;
- for (;;) {
- #ifdef TRACE
- fprintf(stderr,"state = %d\n",state);
- #endif
- switch(state) {
- case LABEL0:
- nextblock();
- /* Fall through !! */
- case LABEL:
- lbmap[INSTRLAB(lnp)] = b;
- /* The lbmap table contains for each
- * label_id the basic block of that label.
- */
- lnp = doread_line(&curproc);
- state = kind(lnp);
- if (state != END) {
- *lp = lnp;
- lp = &lnp->l_next;
- }
- break;
- case NORMAL:
- lnp = doread_line(&curproc);
- if ( (state = kind(lnp)) == LABEL) {
- /* If we come accross a label
- * here, it must be the beginning
- * of a new basic block.
- */
- state = LABEL0;
- } else {
- if (state != END) {
- *lp = lnp;
- lp = &lnp->l_next;
- }
- }
- break;
- case JUMP:
- lnp = doread_line(&curproc);
- /* fall through ... */
- case AFTERPRO:
- switch(state = kind(lnp)) {
- case LABEL:
- state = LABEL0;
- break;
- case JUMP:
- case NORMAL:
- nextblock();
- break;
- }
- break;
- case END:
- *lp = lnp;
- #ifdef TRACE
- fprintf(stderr,"at end of proc, %d blocks\n",lastbid);
- #endif
- if (head == (bblock_p) 0) {
- *kind_out = LDATA;
- *l_out = headl;
- } else {
- *kind_out = LTEXT;
- *g_out = head;
- *n_out = (short) lastbid;
- /* number of basic blocks */
- }
- return TRUE;
- case INIT:
- lnp = doread_line(&curproc);
- if (feof(curinp)) return FALSE;
- if (INSTR(lnp) == ps_pro) {
- state = AFTERPRO;
- } else {
- state = NORMAL;
- headl = lnp;
- lp = &lnp->l_next;
- }
- break;
- }
- }
- }
- static void interproc_analysis(proc_p p)
- {
- /* Interprocedural analysis of a procedure p determines:
- * - all procedures called by p (the 'call graph')
- * - the set of objects changed by p (directly)
- * - whether p does a load-indirect (loi,lof etc.)
- * - whether p does a store-indirect (sti, stf etc.)
- * The changed/used variables information will be
- * transitively closed, i.e. if P calls Q and Q changes
- * a variable X, the P changes X too.
- * (The same applies for used variables and for use/store
- * indirect).
- * The transitive closure will be computed by main
- * after all procedures have been processed.
- */
- bblock_p b;
- line_p lnp;
- bool inloop;
- /* Allocate memory for structs and sets */
- p->p_use = newuse();
- p->p_change = newchange();
- p->p_change->c_ext = Cempty_set(olength);
- p->p_calling = Cempty_set(plength);
- for (b = p->p_start; b != (bblock_p) 0; b = b->b_next) {
- inloop = (Lnrelems(b->b_loops) > 0);
- for (lnp = b->b_start; lnp != (line_p) 0; lnp = lnp->l_next) {
- /* for all instructions of p do */
- switch(INSTR(lnp)) {
- case op_cal:
- Cadd(PROC(lnp)->p_id, &p->p_calling);
- /* add called proc to p_calling */
- if (inloop) {
- CALLED_IN_LOOP(PROC(lnp));
- }
- break;
- case op_cai:
- Cadd(p->p_id,&cai_set);
- break;
- case op_lpi:
- Cadd(PROC(lnp)->p_id, &lpi_set);
- /* All procedures that have their names used
- * in an lpi instruction, may be called via
- * a cai instruction.
- */
- PROC(lnp)->p_flags1 |= PF_LPI;
- break;
- case op_ste:
- case op_sde:
- case op_ine:
- case op_dee:
- case op_zre:
- Cadd(OBJ(lnp)->o_id, &p->p_change->c_ext);
- /* Add changed object to c_ext */
- break;
- case op_lil:
- case op_lof:
- case op_loi:
- case op_los:
- case op_lar:
- p->p_use->u_flags |= UF_INDIR;
- /* p does a load-indirect */
- break;
- case op_sil:
- case op_stf:
- case op_sti:
- case op_sts:
- case op_sar:
- p->p_change->c_flags |= CF_INDIR;
- /* p does a store-indirect */
- break;
- case op_blm:
- case op_bls:
- p->p_use->u_flags |= UF_INDIR;
- p->p_change->c_flags |= CF_INDIR;
- /* p does both */
- break;
- case op_mon:
- printf("mon not yet implemented\n");
- break;
- case op_lxl:
- case op_lxa:
- curproc->p_flags1 |= PF_ENVIRON;
- break;
- case op_lor:
- case op_str:
- if (SHORT(lnp) == 0) {
- curproc->p_flags1 |= PF_ENVIRON;
- }
- break;
- case ps_mes:
- if (aoff(ARG(lnp),0) == ms_gto) {
- ENTERED_WITH_GTO(curproc);
- }
- break;
- }
- }
- }
- }
- static void cf_cleanproc(proc_p p)
- {
- /* Remove the extended data structures of p */
- register bblock_p b;
- register Lindex pi;
- loop_p lp;
- for (b = p->p_start; b != (bblock_p) 0; b = b->b_next) {
- oldcfbx(b->b_extend);
- }
- for (pi = Lfirst(p->p_loops); pi != (Lindex) 0; pi = Lnext(pi,
- p->p_loops)) {
- lp = (loop_p) Lelem(pi);
- oldcflpx(lp->lp_extend);
- }
- }
- #define CH_CHANGE_INDIR(ch) ((ch->c_flags & CF_INDIR) != 0)
- #define USE_INDIR(us) ((us->u_flags & UF_INDIR) != 0)
- #define CALLS_UNKNOWN(p) (p->p_flags1 & (byte) PF_CALUNKNOWN)
- #define ENVIRON(p) (p->p_flags1 & (byte) PF_ENVIRON)
- static bool add_info(proc_p q, proc_p p)
- {
- /* Determine the consequences for used/changed variables info
- * of the fact that p calls q. If e.g. q changes a variable X
- * then p changes this variable too. This routine is an
- * auxiliary routine of the transitive closure process.
- * The returned value indicates if there was any change in
- * the information of p.
- */
- change_p chp, chq;
- use_p usp, usq;
- bool diff = FALSE;
- chp = p->p_change;
- chq = q->p_change;
- usp = p->p_use;
- usq = q->p_use;
- if (!BODY_KNOWN(q)) {
- /* q is a procedure of which the body is not available
- * as EM text.
- */
- if (CALLS_UNKNOWN(p)) {
- return FALSE;
- /* p already called an unknown procedure */
- } else {
- p->p_flags1 |= PF_CALUNKNOWN;
- return TRUE;
- }
- }
- if (CALLS_UNKNOWN(q)) {
- /* q calls a procedure of which the body is not available
- * as EM text.
- */
- if (!CALLS_UNKNOWN(p)) {
- p->p_flags1 |= PF_CALUNKNOWN;
- diff = TRUE;
- }
- }
- if (IS_CALLED_IN_LOOP(p) && !IS_CALLED_IN_LOOP(q)) {
- CALLED_IN_LOOP(q);
- diff = TRUE;
- }
- if (!Cis_subset(chq->c_ext, chp->c_ext)) {
- /* q changes global variables (objects) that
- * p did not (yet) change. Add all variables
- * changed by q to the c_ext set of p.
- */
- Cjoin(chq->c_ext, &chp->c_ext);
- diff = TRUE;
- }
- if (CH_CHANGE_INDIR(chq) && !CH_CHANGE_INDIR(chp)) {
- /* q does a change-indirect (sil etc.)
- * and p did not (yet).
- */
- chp->c_flags |= CF_INDIR;
- diff = TRUE;
- }
- if (USE_INDIR(usq) && !USE_INDIR(usp)) {
- /* q does a use-indirect (lil etc.)
- * and p dis not (yet).
- */
- usp->u_flags |= UF_INDIR;
- diff = TRUE;
- }
- if (ENVIRON(q) && !ENVIRON(p)) {
- /* q uses or changes local variables in its
- * environment while p does not (yet).
- */
- p->p_flags1 |= PF_ENVIRON;
- diff = TRUE;
- }
- return diff;
- }
- static void trans_clos(proc_p head)
- {
- /* Compute the transitive closure of the used/changed
- * variable information.
- */
- proc_p p,q;
- Cindex i;
- bool changes = TRUE;
- while(changes) {
- changes = FALSE;
- for (p = head; p != (proc_p) 0; p = p->p_next) {
- if (!BODY_KNOWN(p)) continue;
- for (i = Cfirst(p->p_calling); i != (Cindex) 0;
- i = Cnext(i,p->p_calling)) {
- q = pmap[Celem(i)];
- if (add_info(q,p)) {
- changes = TRUE;
- }
- }
- }
- }
- }
- void indir_calls()
- {
- Cindex i;
- proc_p p;
- for (i = Cfirst(cai_set); i != (Cindex) 0; i = Cnext(i,cai_set)) {
- p = pmap[Celem(i)]; /* p does a CAI */
- Cjoin(lpi_set, &p->p_calling);
- }
- Cdeleteset(lpi_set);
- Cdeleteset(cai_set);
- }
- int main(int argc, char *argv[])
- {
- FILE *f, *f2, *gf2; /* The EM input, EM output, basic block output */
- bblock_p g;
- short n, kind;
- line_p l;
- linecount = 0;
- fproc = getptable(&pname); /* proc table */
- fdblock = getdtable(&dname); /* data block table */
- lpi_set = Cempty_set(plength);
- cai_set = Cempty_set(plength);
- if ((f = fopen(lname,"r")) == NULL) {
- error("cannot open %s", lname);
- }
- if ((f2 = fopen(lname2,"w")) == NULL) {
- error("cannot open %s", lname2);
- }
- if ((gf2 = fopen(bname2,"w")) == NULL) {
- error("cannot open %s",bname2);
- }
- while (getbblocks(f,&kind,&n,&g,&l)) {
- /* read EM text of one unit and
- * (if it is a procedure)
- * partition it into n basic blocks.
- */
- if (kind == LDATA) {
- putunit(LDATA,(proc_p) 0,l,gf2,f2);
- } else {
- curproc->p_start = g;
- /* The global variable curproc points to the
- * current procedure. It is set by getbblocks
- */
- control_flow(g); /* compute pred and succ */
- dominators(g,n); /* compute immediate dominators */
- loop_detection(curproc); /* compute loops */
- interproc_analysis(curproc);
- /* Interprocedural analysis */
- cf_cleanproc(curproc);
- putunit(LTEXT,curproc,(line_p) 0,gf2,f2);
- /* output control flow graph + text */
- }
- }
- fclose(f);
- fclose(f2);
- fclose(gf2);
- indir_calls();
- trans_clos(fproc);
- /* Compute transitive closure of used/changed
- * variables information for every procedure.
- */
- if ((f = fopen(dname2,"w")) == NULL) {
- error("cannot open %s",dname2);
- }
- putdtable(fdblock,f);
- if ((f = fopen(pname2,"w")) == NULL) {
- error("cannot open %s",pname2);
- }
- putptable(fproc,f,TRUE);
- exit(0);
- return 0;
- }
|