123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395 |
- /* $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 P Y P R O P A G A T I O N */
- #include <em_mnem.h>
- #include <em_pseu.h>
- #include <em_spec.h>
- #include "../share/types.h"
- #include "ud.h"
- #include "../share/debug.h"
- #include "../share/global.h"
- #include "../share/alloc.h"
- #include "../share/lset.h"
- #include "../share/cset.h"
- #include "../share/def.h"
- #include "../share/aux.h"
- #include "../share/locals.h"
- #include "../ud/ud_defs.h"
- #include "ud_copy.h"
- #include "ud_const.h"
- #include "ud_aux.h"
- line_p *copies; /* table of copies; every entry points to the
- * store-instruction.
- */
- short *def_to_copynr; /* table that maps a 'definition'-number to a
- * 'copy' number.
- */
- short nrcopies; /* number of copies in the current procedure
- * (length of copies-table)
- */
- #define COPY_NR(c) def_to_copynr[c]
- #define CHANGED(v,b) (Cis_elem(v,CHGVARS(b)) || Cis_elem(IMPLICIT_DEF(v),GEN(b)))
- #define COUNT 0
- #define MAP 1
- STATIC traverse_defs(p,action)
- proc_p p;
- int action;
- {
- bblock_p b;
- line_p l;
- bool found;
- short defcnt,v,cnt;
- defcnt = 1;
- if (action == COUNT) {
- nrcopies = 0;
- } else {
- copies = (line_p *) newmap(nrcopies);
- def_to_copynr = newtable(nrdefs);
- cnt = 1;
- }
- if (defcnt > nrexpldefs) return;
- for (b = p->p_start; b != (bblock_p) 0; b = b->b_next) {
- for (l = b->b_start; l != (line_p) 0; l = l->l_next) {
- if (defs[defcnt] == l) {
- if (is_copy(l)) {
- var_nr(PREV(l),&v,&found);
- if (found) {
- if (action == COUNT) {
- nrcopies++;
- } else {
- copies[cnt] = l;
- def_to_copynr[defcnt] =
- cnt++;
- }
- }
- }
- if (++defcnt > nrexpldefs) return;
- }
- }
- }
- }
- STATIC make_copytab(p)
- proc_p p;
- {
- /* Make a table of all copies appearing in procedure p.
- * We first count how many there are, because we
- * have to allocate a dynamic array of the correct size.
- */
- traverse_defs(p,COUNT);
- traverse_defs(p,MAP);
- }
- STATIC bool is_changed(varl,start,stop)
- line_p varl, start, stop;
- {
- /* See if the variable used by instruction varl
- * is changed anywhere between 'start' and 'stop'
- */
- register line_p l;
- short v;
- bool found;
- var_nr(varl,&v,&found);
- if (!found) {
- return TRUE; /* We don't maintain ud-info for this variable */
- }
- for (l = start; l != (line_p) 0 && l != stop; l = l->l_next) {
- if (does_expl_def(l) && same_var(varl,l)) return TRUE;
- if (does_impl_def(l) && affected(varl,v,l)) return TRUE;
- }
- return FALSE;
- }
- STATIC gen_kill_copies(p)
- proc_p p;
- {
- /* Compute C_GEN and C_KILL for every basic block
- * of p.
- */
- register line_p l;
- register bblock_p b,n;
- short v;
- bool found;
- short copycnt = 1, defcnt = 1;
- for (b = p->p_start; b != (bblock_p) 0; b = b->b_next) {
- C_GEN(b) = Cempty_set(nrcopies);
- C_KILL(b) = Cempty_set(nrcopies);
- }
- if (nrcopies == 0) return;
- for (b = p->p_start; b != (bblock_p) 0; b = b->b_next) {
- for (l = b->b_start; l != (line_p) 0; l = l->l_next) {
- if (copies[copycnt] == l) {
- var_nr(PREV(l),&v,&found);
- assert(found);
- for (n = p->p_start; n != (bblock_p) 0;
- n = n->b_next) {
- if (n != b && CHANGED(v,n) &&
- Cis_elem(EXPL_TO_DEFNR(defcnt),IN(n))) {
- Cadd(copycnt,&C_KILL(n));
- }
- }
- if (is_changed(PREV(l),l,(line_p) 0)) {
- Cadd(copycnt,&C_KILL(b));
- } else {
- Cadd(copycnt,&C_GEN(b));
- }
- if (++copycnt > nrcopies) return;
- }
- if (defs[defcnt] == l) defcnt++;
- }
- }
- }
- STATIC intersect_outs(bbset,setp,full_set)
- lset bbset;
- cset *setp,full_set;
- {
- /* Take the intersection of C_OUT(b), for all b in bbset,
- * and put the result in setp.
- */
- Lindex i;
- Ccopy_set(full_set,setp);
- for (i = Lfirst(bbset); i != (Lindex) 0; i = Lnext(i,bbset)) {
- Cintersect(C_OUT((bblock_p) Lelem(i)), setp);
- }
- }
- STATIC init_cin(p,full_set)
- proc_p p;
- cset full_set;
- {
- /* Initialize C_IN(b) and C_OUT(b), for every basic block b.
- * C_IN of the root of the CFG (i.e. the procedure entry block)
- * will contain every copy, as it trivially holds that for
- * every copy "s: A := B" there is no assignment to B on any
- * path from s to the beginning of the root (because PRED(root)=empty).
- * C_IN and C_OUT of the root will never be changed.
- * For all remaining blocks b, C_IN(b) is initialized to the set of
- * all copies, and C_OUT is set to all copies but those killed in b.
- */
- bblock_p b;
- bblock_p root = p->p_start;
- C_IN(root) = Cempty_set(nrcopies);
- Ccopy_set(full_set,&C_IN(root)); /* full_set is the set of all copies */
- /* C_OUT(root) = {all copies} - C_KILL(root) + C_GEN(root) */
- C_OUT(root) = Cempty_set(nrcopies);
- Ccopy_set(full_set,&C_OUT(root));
- Csubtract(C_KILL(root),&C_OUT(root));
- Cjoin(C_GEN(root),&C_OUT(root));
- for (b = root->b_next; b != (bblock_p) 0; b = b->b_next) {
- C_IN(b) = Cempty_set(nrcopies);
- Ccopy_set(full_set,&C_IN(b));
- C_OUT(b) = Cempty_set(nrcopies);
- Ccopy_set(full_set,&C_OUT(b));
- Csubtract(C_KILL(b),&C_OUT(b));
- }
- }
- STATIC solve_cin(p)
- proc_p p;
- {
- /* Solve the data flow equations for reaching
- * definitions of procedure p.
- * These equations are:
- * (1) C_OUT(b) = C_IN(b) - C_KILL(b) + C_GEN(b)
- * (2) C_IN(b) = C_OUT(p1) * .. * C_OUT(pn)
- * (3) C_IN(root) = {all copies} ;
- * where PRED(b) = {p1, .. , pn}
- * and '*' denotes set intersection.
- * We use the iterative algorithm of Aho&Ullman to
- * solve the equations.
- */
- register bblock_p b;
- bool change;
- cset newin,full_set;
- short n;
- /* initializations */
- full_set = Cempty_set(nrcopies);
- for (n = 1; n <= nrcopies; n++) {
- Cadd(n,&full_set);
- }
- newin = Cempty_set(nrcopies);
- init_cin(p,full_set);
- change = TRUE;
- /* main loop */
- while (change) {
- change = FALSE;
- for (b = p->p_start->b_next; b != (bblock_p) 0; b = b->b_next) {
- intersect_outs(b->b_pred, &newin,full_set);
- /* newin = C_OUT(p1) * .. * C_OUT(pn) */
- if (!Cequal(newin,C_IN(b))) {
- change = TRUE;
- Ccopy_set(newin, &C_IN(b));
- Ccopy_set(C_IN(b), &C_OUT(b));
- Csubtract(C_KILL(b), &C_OUT(b));
- Cjoin(C_GEN(b), &C_OUT(b));
- }
- }
- }
- Cdeleteset(newin);
- Cdeleteset(full_set);
- }
- copy_analysis(p)
- proc_p p;
- {
- /* Determine which copies procedure p has. Compute C_IN(b),
- * for every basic block b.
- */
- make_copytab(p); /* Make a table of all copies */
- gen_kill_copies(p); /* Compute C_GEN(b) and C_KILL(b), for every b */
- solve_cin(p); /* Solve equations for C_IN(b) */
- }
- bool is_copy(def)
- line_p def;
- {
- /* See if the definition def is also a 'copy', i.e. an
- * statement of the form 'A := B' (or, in EM terminology:
- * a sequence 'Load Variable; Store Variable').
- */
- line_p lhs;
- int instr;
- lhs = PREV(def);
- if (lhs == (line_p) 0) return FALSE;
- instr = INSTR(def);
- switch(INSTR(lhs)) {
- case op_lol:
- case op_loe:
- return instr == op_stl || instr == op_ste;
- case op_ldl:
- case op_lde:
- return instr == op_sdl || instr == op_sde;
- default:
- return FALSE;
- }
- /* NOTREACHED */
- }
- fold_var(old,new,b)
- line_p old, new;
- bblock_p b;
- {
- /* The variable referenced by the EM instruction 'old'
- * must be replaced by the variable referenced by 'new'.
- */
- line_p l;
- /* DEBUGGING:
- local_p loc;
- short nr;
- bool ok;
- if (TYPE(old) == OPOBJECT) {
- printf("global var.");
- } else {
- printf("local var. with off. %ld",off_set(old));
- find_local(off_set(old),&nr,&ok);
- assert(ok);
- loc = locals[nr];
- printf(",score %ld",loc->lc_score);
- }
- printf(" replaced by ");
- if (TYPE(new) == OPOBJECT) {
- printf("global var.");
- } else {
- printf("local var. with off. %ld",off_set(new));
- find_local(off_set(new),&nr,&ok);
- assert(ok);
- loc = locals[nr];
- printf(",score %ld",loc->lc_score);
- }
- printf("\n");
- END DEBUG */
- l = old;
- if (TYPE(l) != TYPE(new)) {
- l = newline(TYPE(new));
- l->l_instr = INSTR(new);
- repl_line(old,l,b);
- }
- switch(TYPE(new)) {
- case OPOBJECT:
- OBJ(l) = OBJ(new);
- break;
- case OPSHORT:
- SHORT(l) = SHORT(new);
- break;
- case OPOFFSET:
- OFFSET(l) = OFFSET(new);
- break;
- default:
- assert(FALSE);
- }
- }
- bool value_retained(copy,defnr,use,b)
- line_p copy,use;
- short defnr;
- bblock_p b;
- {
- /* See if the right hand side variable of the
- * copy still has the same value at 'use'.
- * If the copy and the use are in the same
- * basic block (defnr = 0), search from the
- * copy to the use, to see if the rhs variable
- * is changed. If the copy is in another block,
- * defnr is the definition-number of the copy.
- * Search from the beginning of the block to
- * the use, to see if the rhs is changed; if not,
- * check that the copy is in C_IN(b).
- */
- line_p rhs, start;
- rhs = PREV(copy);
- start = (defnr == 0 ? copy : b->b_start);
- return !is_changed(rhs,start,use) &&
- (defnr == 0 || Cis_elem(COPY_NR(defnr), C_IN(b)));
- }
|