123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549 |
- /* $Id$ */
- /*
- * (c) copyright 1987 by the Vrije Universiteit, Amsterdam, The Netherlands.
- * See the copyright notice in the ACK home directory, in the file "Copyright".
- */
- /* U S E - D E F I N I T I O N A N A L Y S I S */
- #include <stdlib.h>
- #include <stdio.h>
- #include <string.h>
- #include <em_spec.h>
- #include "../share/types.h"
- #include "ud.h"
- #include "../share/debug.h"
- #include "../share/global.h"
- #include "../share/lset.h"
- #include "../share/cset.h"
- #include "../share/def.h"
- #include "../share/files.h"
- #include "../share/map.h"
- #include "../share/get.h"
- #include "../share/put.h"
- #include "../share/alloc.h"
- #include "../share/aux.h"
- #include "../share/init_glob.h"
- #include "../share/locals.h"
- #include "../share/go.h"
- #include "ud_defs.h"
- #include "ud_const.h"
- #include "ud_copy.h"
- /* core allocation macros */
- #define newudbx() (bext_p) newstruct(bext_ud)
- #define oldudbx(x) oldstruct(bext_ud,x)
- short nrglobals;
- short nrvars;
- int Svalue,Svariable;
- cond_p globl_cond_tab,local_cond_tab;
- static cond_p getcondtab(FILE *f)
- {
- int l,i;
- cond_p tab;
- fscanf(f,"%d",&l);
- tab = newcondtab(l);
- for (i = 0; i < l; i++) {
- fscanf(f,"%hd %hd %hd",&tab[i].mc_cond,&tab[i].mc_tval,
- &tab[i].mc_sval);
- }
- assert(tab[l-1].mc_cond == DEFAULT);
- return tab;
- }
- static int ud_machinit(void *param)
- {
- char s[100];
- FILE *f = (FILE *)param;
- for (;;) {
- while(getc(f) != '\n');
- fscanf(f,"%s",s);
- if (strcmp(s,"%%UD") == 0)break;
- }
- globl_cond_tab = getcondtab(f);
- local_cond_tab = getcondtab(f);
- return 0;
- }
- static bool test_cond(short cond, offset val)
- {
- switch(cond) {
- case DEFAULT:
- return TRUE;
- case FITBYTE:
- return val >= -128 && val < 128;
- }
- assert(FALSE);
- /* NOTREACHED */
- return FALSE;
- }
- static short map_value(struct cond_tab tab[], offset val, bool time)
- {
- cond_p p;
- for (p = &tab[0]; ; p++) {
- if (test_cond(p->mc_cond,val)) {
- return (time ? p->mc_tval : p->mc_sval);
- }
- }
- }
- static int init_root(void *param)
- {
- /* Initialise the IN OUT sets of the entry block of the
- * current procedure. Global variables and parameters
- * already have a value at this point, although we do
- * not know which value. Therefor, implicit definitions
- * to all global variables and parameters are
- * put in IN.
- */
- bblock_p root = (bblock_p)param;
- short v;
- for (v = 1; v <= nrglobals; v++) {
- Cadd(IMPLICIT_DEF(GLOB_TO_VARNR(v)), &IN(root));
- }
- for (v = 1; v <= nrlocals; v++) {
- if (locals[v]->lc_off >= 0) {
- Cadd(IMPLICIT_DEF(LOC_TO_VARNR(v)),&IN(root));
- }
- }
- /* OUT(root) = IN(root) - KILL(root) + GEN(root) */
- Ccopy_set(IN(root),&OUT(root));
- Csubtract(KILL(root),&OUT(root));
- Cjoin(GEN(root),&OUT(root));
- return 0;
- }
- static void unite_outs(lset bbset, cset *setp)
- {
- /* Take the union of OUT(b), for all b in bbset,
- * and put the result in setp.
- */
- Lindex i;
- Cclear_set(setp);
- for (i = Lfirst(bbset); i != (Lindex) 0; i = Lnext(i,bbset)) {
- Cjoin(OUT((bblock_p) Lelem(i)), setp);
- }
- }
- static void solve_equations(proc_p p)
- {
- /* Solve the data flow equations for reaching
- * definitions of procedure p.
- * These equations are:
- * (1) OUT(b) = IN(b) - KILL(b) + GEN(b)
- * (2) IN(b) = OUT(p1) + .. + OUT(pn) ;
- * where PRED(b) = {p1, .. , pn}
- * We use the iterative algorithm of Aho&Ullman to
- * solve the equations.
- */
- bblock_p b;
- bool change;
- cset newin;
- /* initializations */
- newin = Cempty_set(nrdefs);
- for (b = p->p_start; b != (bblock_p) 0; b = b->b_next) {
- IN(b) = Cempty_set(nrdefs);
- OUT(b) = Cempty_set(nrdefs);
- Ccopy_set(GEN(b), &OUT(b));
- }
- init_root(p->p_start);
- /* Global variables and parameters have already a value
- * at the procedure entry block.
- */
- change = TRUE;
- /* main loop */
- while (change) {
- change = FALSE;
- for (b = p->p_start->b_next; b != (bblock_p) 0; b = b->b_next) {
- unite_outs(b->b_pred, &newin);
- /* newin = OUT(p1) + .. + OUT(pn) */
- if (!Cequal(newin,IN(b))) {
- change = TRUE;
- Ccopy_set(newin, &IN(b));
- Ccopy_set(IN(b), &OUT(b));
- Csubtract(KILL(b), &OUT(b));
- Cjoin(GEN(b), &OUT(b));
- }
- }
- }
- for (b = p->p_start; b != (bblock_p) 0; b = b->b_next) {
- Cdeleteset(KILL(b));
- Cdeleteset(OUT(b));
- }
- Cdeleteset(newin);
- }
- static short global_addr_cost()
- {
- return add_timespace(map_value(globl_cond_tab,(offset) 0,TRUE),
- map_value(globl_cond_tab,(offset) 0,FALSE));
- }
- short local_addr_cost(offset off)
- {
- return add_timespace(map_value(local_cond_tab,off,TRUE),
- map_value(local_cond_tab,off,FALSE));
- }
- static bool fold_is_desirable(line_p old, line_p new)
- {
- /* See if it is desirable to replace the variable used by the
- * EM instruction 'old' by the variable used by 'new'.
- * We do not replace 'cheaply addressable variables' by 'expensively
- * addressable variables'. E.g. if we're optimizing object code size,
- * we do not replace a local variable by a global variable on a VAX,
- * because the former occupies 1 or 2 bytes and the latter occupies
- * 4 bytes.
- * If 2 local variables are equally expensive to address, we replace
- * the first one by the second only if the first one is used at
- * least as many times as the second one.
- */
- local_p oldloc,newloc;
- short old_cost,new_cost,nr;
- bool ok;
- if (TYPE(old) == OPOBJECT) {
- /* old variable is a global variable */
- return TYPE(new) != OPOBJECT &&
- global_addr_cost() >=
- local_addr_cost(off_set(new));
- }
- find_local(off_set(old),&nr,&ok);
- assert(ok);
- oldloc = locals[nr];
- old_cost = local_addr_cost(off_set(old));
- if (TYPE(new) == OPOBJECT) {
- return oldloc->lc_score == 2 || /* old var. can be eliminated */
- old_cost > global_addr_cost();
- }
- find_local(off_set(new),&nr,&ok);
- assert(ok);
- newloc = locals[nr];
- new_cost = local_addr_cost(off_set(new));
- return old_cost > new_cost ||
- (old_cost == new_cost && oldloc->lc_score < newloc->lc_score);
- }
- #ifdef TRACE
- /*********** TRACING ROUTINES ***********/
- static void pr_localtab()
- {
- short i;
- local_p lc;
- printf("LOCAL-TABLE (%d)\n\n",nrlocals);
- for (i = 1; i <= nrlocals; i++) {
- lc = locals[i];
- printf("LOCAL %d\n",i);
- printf(" offset= %ld\n",lc->lc_off);
- printf(" size= %d\n",lc->lc_size);
- printf(" flags= %d\n",lc->lc_flags);
- }
- }
- void pr_globals()
- {
- dblock_p d;
- obj_p obj;
- printf("GLOBALS (%d)\n\n",nrglobals);
- printf("ID GLOBNR\n");
- for (d = fdblock; d != (dblock_p) 0; d = d->d_next) {
- for (obj = d->d_objlist; obj != (obj_p) 0; obj = obj->o_next) {
- if (obj->o_globnr != 0) {
- printf("%d %d\n", obj->o_id,obj->o_globnr);
- }
- }
- }
- }
- extern char em_mnem[];
- static void pr_defs()
- {
- short i;
- line_p l;
- printf("DEF TABLE\n\n");
- for (i = 1; i <= nrexpldefs; i++) {
- l = defs[i];
- printf("%d %s ",EXPL_TO_DEFNR(i),
- &em_mnem[(INSTR(l)-sp_fmnem)*4]);
- switch(TYPE(l)) {
- case OPSHORT:
- printf("%d\n",SHORT(l));
- break;
- case OPOFFSET:
- printf("%ld\n",OFFSET(l));
- break;
- case OPOBJECT:
- printf("%d\n",OBJ(l)->o_id);
- break;
- default:
- assert(FALSE);
- }
- }
- }
- static void pr_set(char *name, short k, cset s, short n)
- {
- short i;
- printf("%s(%d) = {",name,k);
- for (i = 1; i <= n; i++) {
- if (Cis_elem(i,s)) {
- printf("%d ",i);
- }
- }
- printf ("}\n");
- }
- static void pr_blocks(proc_p p)
- {
- bblock_p b;
- short n;
- for (b = p->p_start; b != 0; b = b->b_next) {
- printf ("\n");
- n = b->b_id;
- pr_set("GEN",n,GEN(b),nrdefs);
- pr_set("KILL",n,KILL(b),nrdefs);
- pr_set("IN ",n,IN(b),nrdefs);
- pr_set("OUT",n,OUT(b),nrdefs);
- pr_set("CHGVARS",n,CHGVARS(b),nrvars);
- }
- }
- static void pr_copies()
- {
- short i;
- printf("\nCOPY TABLE\n\n");
- for (i = 1; i <= nrdefs; i++) {
- if (def_to_copynr[i] != 0) {
- printf("%d %d\n",i,def_to_copynr[i]);
- }
- }
- }
- static void pr_cblocks(proc_p p)
- {
- bblock_p b;
- short n;
- for (b = p->p_start; b != 0; b = b->b_next) {
- printf ("\n");
- n = b->b_id;
- pr_set("CGEN",n,C_GEN(b),nrcopies);
- pr_set("CKILL",n,C_KILL(b),nrcopies);
- pr_set("CIN ",n,C_IN(b),nrcopies);
- pr_set("COUT",n,C_OUT(b),nrcopies);
- }
- }
- /*********** END TRACING ********/
- #endif
- static void ud_analysis(proc_p p)
- {
- /* Perform use-definition analysis on procedure p */
- make_localtab(p); /* See for which local we'll keep ud-info */
- #ifdef TRACE
- pr_localtab();
- #endif
- nrvars = nrglobals + nrlocals;
- make_defs(p); /* Make a table of all useful definitions in p */
- #ifdef TRACE
- pr_defs();
- #endif
- nrdefs = nrexpldefs + nrvars; /* number of definitions */
- gen_sets(p); /* compute GEN(b), for every basic block b */
- kill_sets(p); /* compute KILL(b), for every basic block b */
- solve_equations(p); /* solve data flow equations for p */
- #ifdef TRACE
- pr_blocks(p);
- #endif
- }
- static void clean_maps()
- {
- local_p *p;
- cset *v;
- oldmap((short **)defs,nrexpldefs);
- for (p = &locals[1]; p <= &locals[nrlocals]; p++) {
- oldlocal(*p);
- }
- oldmap((short **)locals,nrlocals);
- for (v = &vardefs[1]; v <= &vardefs[nrvars]; v++) {
- Cdeleteset(*v);
- }
- oldmap((short **)vardefs,nrvars);
- }
- static bool try_optim(line_p l, bblock_p b)
- {
- /* Try copy propagation and constant propagation */
- line_p def;
- offset val;
- short defnr;
- if (is_use(l) && (def = unique_def(l,b,&defnr)) != (line_p) 0) {
- if (is_copy(def)) {
- if (value_retained(def,defnr,l,b) &&
- fold_is_desirable(l,PREV(def))) {
- fold_var(l,PREV(def),b);
- OUTVERBOSE("vp:variable folded in proc %d",
- curproc->p_id,0);
- Svariable++;
- return TRUE;
- }
- } else {
- if (value_known(def,&val)) {
- fold_const(l,b,val);
- OUTVERBOSE("vp:value folded in proc %d",
- curproc->p_id,0);
- Svalue++;
- return TRUE;
- }
- }
- }
- return FALSE;
- }
- void value_propagation(proc_p p)
- {
- /* Apply value propagation to procedure p */
- bool changes;
- bblock_p b;
- line_p l, next;
- changes = TRUE;
- /* If a statement like A := B is folded to A := constant,
- * new opportunities for constant folding may arise,
- * e.g. the value of A might be statically known too now.
- */
- while (changes) {
- changes = FALSE;
- for (b = p->p_start; b != (bblock_p) 0; b = b->b_next) {
- for (l = b->b_start; l != (line_p) 0; l = next) {
- next = l->l_next;
- if (try_optim(l,b)) {
- changes = TRUE;
- }
- }
- }
- }
- oldmap((short **)copies,nrcopies);
- oldtable((short **)def_to_copynr,nrdefs);
- }
- static void ud_extend(proc_p p)
- {
- /* Allocate extended data structures for Use Definition analysis */
- register bblock_p b;
- for (b = p->p_start; b != (bblock_p) 0; b = b->b_next) {
- b->b_extend = newudbx();
- }
- }
- static void ud_cleanup(proc_p p)
- {
- /* Deallocate extended data structures for Use Definition analysis */
- register bblock_p b;
- for (b = p->p_start; b != (bblock_p) 0; b = b->b_next) {
- Cdeleteset(GEN(b));
- Cdeleteset(IN(b));
- Cdeleteset(C_GEN(b));
- Cdeleteset(C_KILL(b));
- Cdeleteset(C_IN(b));
- Cdeleteset(C_OUT(b));
- Cdeleteset(CHGVARS(b));
- oldudbx(b->b_extend);
- }
- }
- static int ud_optimize(void *param)
- {
- proc_p p = (proc_p)param;
- if (IS_ENTERED_WITH_GTO(p)) return 0;
- ud_extend(p);
- locals = (local_p *) 0;
- vardefs = (cset *) 0;
- defs = (line_p *) 0;
- ud_analysis(p);
- copy_analysis(p);
- #ifdef TRACE
- pr_copies();
- pr_cblocks(p);
- #endif
- value_propagation(p);
- ud_cleanup(p);
- clean_maps();
- return 0;
- }
- main(argc,argv)
- int argc;
- char *argv[];
- {
- go(argc,argv,init_globals,ud_optimize,ud_machinit,no_action);
- report("values folded",Svalue);
- report("variables folded",Svariable);
- exit(0);
- }
|