123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541 |
- /* $Id$ */
- /*
- * (c) copyright 1987 by the Vrije Universiteit, Amsterdam, The Netherlands.
- * See the copyright notice in the ACK home directory, in the file "Copyright".
- */
- /*
- * R E G I S T E R A L L O C A T I O N
- *
- */
- #include <stdlib.h>
- #include <stdio.h>
- #include <string.h>
- #include <em_reg.h>
- #include "../share/types.h"
- #include "../share/debug.h"
- #include "../share/global.h"
- #include "../share/files.h"
- #include "../share/get.h"
- #include "../share/put.h"
- #include "../share/lset.h"
- #include "../share/map.h"
- #include "../share/alloc.h"
- #include "../share/go.h"
- #include "ra.h"
- #include "ra_items.h"
- #include "ra_allocl.h"
- #include "ra_profits.h"
- #include "ra_pack.h"
- #include "ra_xform.h"
- #define newrabx() (bext_p) newstruct(bext_ra)
- #define newralpx() (lpext_p) newstruct(lpext_ra)
- #define oldrabx(x) oldstruct(bext_ra,x)
- #define oldralpx(x) oldstruct(lpext_ra,x)
- void stat_regusage(alloc_p list);
- short alloc_id;
- static item_p items[NRITEMTYPES];
- int nrinstrs;
- line_p *instrmap;
- cond_p alocaltab[NRREGTYPES][NRREGTYPES],alocaddrtab[NRREGTYPES][NRREGTYPES],
- aconsttab,adconsttab,aglobaltab,aproctab;
- cond_p olocaltab[NRREGTYPES],olocaddrtab[NRREGTYPES],
- oconsttab,odconsttab,oglobaltab,oproctab;
- cond_p regsav_cost;
- short regs_available[] = {
- /* Actually machine dependent; this is for vax2 */
- 3, /* reg_any i.e. data regs */
- 0, /* reg_loop */
- 3, /* reg_pointer i.e. address reg. */
- 0 /* reg_float */
- } ;
- short use_any_as_pointer = 0;
- static cond_p getcondtab(f)
- 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;
- }
- void get_atab(FILE *f, cond_p tab[NRREGTYPES][NRREGTYPES])
- {
- int i,cnt,totyp,regtyp;
-
- fscanf(f,"%d",&cnt);
- for (i = 0; i < cnt; i++) {
- fscanf(f,"%d %d",®typ,&totyp);
- assert(regtyp >= 0 && regtyp < NRREGTYPES);
- assert(totyp >= 0 && totyp < NRREGTYPES);
- tab[regtyp][totyp] = getcondtab(f);
- }
- }
- void get_otab(FILE *f, cond_p tab[NRREGTYPES])
- {
- int i,cnt,regtyp;
-
- fscanf(f,"%d",&cnt);
- for (i = 0; i < cnt; i++) {
- fscanf(f,"%d",®typ);
- assert(regtyp >= 0 && regtyp < NRREGTYPES);
- tab[regtyp] = getcondtab(f);
- }
- }
- static int ra_machinit(void *param)
- {
- /* Read target machine dependent information for this phase */
- char s[100];
- FILE *f = (FILE *)param;
- for (;;) {
- while(getc(f) != '\n');
- fscanf(f,"%s",s);
- if (strcmp(s,"%%RA") == 0)break;
- }
- fscanf(f,"%hd",®s_available[reg_any]);
- fscanf(f,"%hd",®s_available[reg_pointer]);
- fscanf(f,"%hd",®s_available[reg_float]);
- fscanf(f,"%hd",&use_any_as_pointer);
- get_atab(f,alocaltab);
- get_atab(f,alocaddrtab);
- aconsttab = getcondtab(f);
- adconsttab = getcondtab(f);
- aglobaltab = getcondtab(f);
- aproctab = getcondtab(f);
- get_otab(f,olocaltab);
- get_otab(f,olocaddrtab);
- oconsttab = getcondtab(f);
- odconsttab = getcondtab(f);
- oglobaltab = getcondtab(f);
- oproctab = getcondtab(f);
- regsav_cost = getcondtab(f);
- return 0;
- }
- static bblock_p header(loop_p lp)
- {
- /* Try to determine the 'header' block of loop lp.
- * If 'e' is the entry block of loop L, then block 'b' is
- * called the header block of L, iff:
- * SUCC(b) = {e} & PRED(e) = {b}
- * If lp has no header block, 0 is returned.
- */
- bblock_p x = lp->lp_entry->b_idom;
- if (x != (bblock_p) 0 && Lnrelems(x->b_succ) == 1 &&
- (bblock_p) Lelem(Lfirst(x->b_succ)) == lp->lp_entry) {
- return x;
- }
- return (bblock_p) 0;
- }
- static void ra_extproc(proc_p p)
- {
- /* Allocate the extended data structures for procedure p */
- loop_p lp;
- Lindex pi;
- bblock_p b;
- for (pi = Lfirst(p->p_loops); pi != (Lindex) 0;
- pi = Lnext(pi,p->p_loops)) {
- lp = (loop_p) Lelem(pi);
- lp->lp_extend = newralpx();
- lp->LP_HEADER = header(lp);
- }
- for (b = p->p_start; b != (bblock_p) 0; b = b->b_next) {
- b->b_extend = newrabx();
- }
- }
- static int ra_cleanproc(void *param)
- {
- /* Allocate the extended data structures for procedure p */
- proc_p p = (proc_p)param;
- loop_p lp;
- Lindex pi;
- bblock_p b;
- for (pi = Lfirst(p->p_loops); pi != (Lindex) 0;
- pi = Lnext(pi,p->p_loops)) {
- lp = (loop_p) Lelem(pi);
- oldralpx(lp->lp_extend);
- }
- for (b = p->p_start; b != (bblock_p) 0; b = b->b_next) {
- oldrabx(b->b_extend);
- }
- return 0;
- }
- static void loop_blocks(proc_p p)
- {
- /* Compute the LP_BLOCKS sets for all loops of p */
- bblock_p b;
- Lindex i;
- for (b = p->p_start; b != (bblock_p) 0; b = b->b_next) {
- for (i = Lfirst(b->b_loops); i != (Lindex) 0;
- i = Lnext(i,b->b_loops)) {
- Ladd(b,&(((loop_p) Lelem(i))->LP_BLOCKS));
- }
- }
- }
- static void make_instrmap(proc_p p, line_p map[])
- {
- /* make the instructions map of procedure p */
- bblock_p b;
- line_p l;
- int i = 0;
- for (b = p->p_start; b != (bblock_p) 0; b = b->b_next) {
- b->B_BEGIN = i; /* number of first instruction */
- for (l = b->b_start; l != (line_p) 0; l = l->l_next) {
- map[i++] = l;
- }
- b->B_END = i-1; /* number of last instruction */
- }
- }
- static bool useful_item(item_p item)
- {
- /* See if it may be useful to put the item in a register.
- * A local variable may always be put in a register.
- * Other items must be used at least twice.
- */
- int nruses = Lnrelems(item->it_usage);
- assert (nruses > 0); /* otherwise it would not be an item! */
- return nruses > 1 || item->it_type == LOCALVAR;
- }
- static void cleantimeset(lset s)
- {
- Lindex i;
- time_p t;
- for (i = Lfirst(s); i != (Lindex) 0; i = Lnext(i,s)) {
- t = (time_p) Lelem(i);
- oldtime(t);
- }
- Ldeleteset(s);
- }
- static item_p cat_items(item_p items[])
- {
- /* Make one item list out of an array of itemlists.
- * Remove items that are used only once.
- */
- item_p it;
- item_p *ip,head,next;
- int t;
- ip = &head;
- for (t = 0; t < NRITEMTYPES;t++) {
- for ( it = items[t]; it != (item_p) 0; it = next) {
- next = it->it_next;
- if (!it->it_desirable || !useful_item(it)) {
- cleantimeset(it->it_usage);
- olditem(it);
- } else {
- *ip = it;
- ip = &it->it_next;
- }
- }
- }
- *ip = (item_p) 0;
- return head;
- }
- static void clean_interval(interv_p list)
- {
- interv_p x,next;
- for (x = list; x != (interv_p) 0; x = next) {
- next = x->i_next;
- oldinterval(x);
- }
- }
- static void clean_allocs(alloc_p list)
- {
- alloc_p x,next;
- for (x = list; x != (alloc_p) 0; x = next) {
- next = x->al_next;
- clean_interval(x->al_timespan);
- Cdeleteset(x->al_rivals);
- Ldeleteset(x->al_inits);
- clean_interval(x->al_busy);
- clean_allocs(x->al_mates);
- oldalloc(x);
- }
- }
- static void cleanitems(item_p list)
- {
- item_p x,next;
- for (x = list; x != (item_p) 0; x = next ) {
- next = x->it_next;
- cleantimeset(x->it_usage);
- olditem(x);
- }
- }
- int ra_initialize(void *dummy)
- {
- init_replacements(ps,ws);
- return 0;
- }
- int ra_optimize(void *param)
- {
- proc_p p = (proc_p)param;
- item_p itemlist;
- alloc_p alloclist,packed,unpacked;
- offset locls;
- bool time_opt = (time_space_ratio == 100);
- if (IS_ENTERED_WITH_GTO(p)) return 0;
- ra_extproc(p);
- loop_blocks(p);
- alloc_id =0;
- locls = p->p_localbytes;
- build_itemlist(p,items,&nrinstrs);
- instrmap = (line_p *) newmap(nrinstrs-1); /* map starts counting at 0 */
- make_instrmap(p,instrmap);
- build_lifetimes(items);
- /* print_items(items,p); */
- /* statistics(items); */
- itemlist = cat_items(items); /* make one list */
- alloclist = build_alloc_list(p,Lnrelems(p->p_loops),
- itemlist);
- build_rivals_graph(alloclist);
- compute_profits(alloclist,time_opt);
- /* print_allocs(alloclist); */
- pack(alloclist,time_opt,&packed,&unpacked,p);
- stat_regusage(packed);
- xform_proc(p,packed,nrinstrs,instrmap);
- /* print_allocs(packed); */
- p->p_localbytes = locls;
- /* don't really allocate dummy local variables! */
- rem_locals(p,packed);
- rem_formals(p,packed);
- /* remove storage for real locals that
- *are always put in register .
- */
- clean_allocs(unpacked);
- clean_allocs(packed);
- cleanitems(itemlist);
- oldmap((short **)instrmap,nrinstrs-1);
- ra_cleanproc(p);
- return 0;
- }
- int main(int argc, char *argv[])
- {
- go(argc,argv,ra_initialize,ra_optimize,ra_machinit,no_action);
- exit(0);
- }
- /***************************************************************************/
- /***************************************************************************/
- /***************************************************************************/
- /* debugging stuff */
- char *str_types[] = {
- "local variable",
- "addr. of local",
- "addr. of external",
- "addr. of procedure",
- "constant",
- "double constant"
- };
- char *str_regtypes[] = {
- "any",
- "loop",
- "pointer",
- "float"
- };
- void print_items(item_p items[], proc_p p)
- {
- int t;
- item_p item;
- interv_p iv;
- fprintf(stderr, "BEGIN PROCEDURE %d\n",p->p_id);
- for (t = 0; t < NRITEMTYPES;t++) {
- for (item = items[t]; item != (item_p) 0;item = item->it_next) {
- fprintf(stderr, "\nitemtype = %s\n",str_types[t]);
- if (t == GLOBL_ADDR) {
- fprintf(stderr, "id of external = %d\n",
- item->i_t.it_obj->o_id);
- } else {
- fprintf(stderr, "offset = %ld\n",
- item->i_t.it_off);
- }
- fprintf(stderr, "regtype = %s\n",str_regtypes[item->it_regtype]);
- fprintf(stderr, "size = %d\n",item->it_size);
- fprintf(stderr, "#usages = %d\n", Lnrelems(item->it_usage));
- fprintf(stderr, "lifetime = {");
- for (iv = item->it_lives; iv != (interv_p) 0;
- iv = iv->i_next) {
- fprintf(stderr, "(%d,%d) ",iv->i_start,iv->i_stop);
- }
- fprintf(stderr, "} \n");
- }
- }
- fprintf(stderr, "END PROCEDURE %d\n\n",p->p_id);
- }
- void print_allocs(alloc_p list)
- {
- alloc_p al,m;
- item_p item;
- short t;
- interv_p iv;
- fprintf(stderr,"BEGIN ALLOCLIST of proc %d\n",curproc->p_id);
- for (m = list ; m != (alloc_p) 0; m = m->al_next) {
- for (al = m; al != (alloc_p) 0; al = al->al_mates) {
- item = al->al_item;
- t = item->it_type;
- fprintf(stderr,"\nitem: [type = %s, ",str_types[t]);
- switch(t) {
- case GLOBL_ADDR:
- fprintf(stderr,"id = %d]\n", item->i_t.it_obj->o_id);
- break;
- case PROC_ADDR:
- fprintf(stderr,"id = %d]\n", item->i_t.it_proc->p_id);
- break;
- default:
- fprintf(stderr,"offset = %ld]\n", item->i_t.it_off);
- }
- fprintf(stderr,"#usages(static) = %d\n",al->al_susecount);
- fprintf(stderr,"#usages(dyn) = %d\n",al->al_dusecount);
- fprintf(stderr,"#inits = %d\n",Lnrelems(al->al_inits));
- fprintf(stderr,"isloop = %d\n",al->al_isloop);
- fprintf(stderr,"timespan = {");
- for (iv = al->al_timespan; iv != (interv_p) 0;
- iv = iv->i_next) {
- fprintf(stderr,"(%d,%d) ",iv->i_start,iv->i_stop);
- }
- fprintf(stderr,"} \n");
- fprintf(stderr,"busy = {");
- for (iv = al->al_busy; iv != (interv_p) 0;
- iv = iv->i_next) {
- fprintf(stderr,"(%d,%d) ",iv->i_start,iv->i_stop);
- }
- fprintf(stderr,"} \n");
- fprintf(stderr,"profits = %d\n",al->al_profits);
- fprintf(stderr,"dummy local = %ld\n",al->al_dummy);
- fprintf(stderr,"regnr = %d\n",al->al_regnr);
- }
- }
- }
- short regs_needed[4];
- void stat_regusage(alloc_p list)
- {
- int i;
- alloc_p x;
- for (i = 0; i < 4; i++) {
- regs_needed[i] = 0;
- }
- for (x = list; x != (alloc_p) 0; x = x->al_next) {
- regs_needed[x->al_regtype]++;
- }
- /* fprintf(stderr, "data regs:%d\n",regs_needed[reg_any]); */
- /* fprintf(stderr, "address regs:%d\n",regs_needed[reg_pointer]); */
- }
-
- int cnt_regtypes[reg_float+1];
- void statistics(item_p items[])
- {
- item_p item,next;
- int t,r;
- int cnt;
- fprintf(stderr, "\nSTATISTICS\n");
- for (r = 0; r <= reg_float; r++) cnt_regtypes[r] = 0;
- for (t = 0; t < NRITEMTYPES;t++) {
- cnt = 0;
- for (item = items[t]; item != (item_p) 0;item = next) {
- if (useful_item(item)) {
- cnt++;
- cnt_regtypes[item->it_regtype]++;
- }
- next = item->it_next;
- }
- fprintf(stderr, "#%s = %d\n",str_types[t],cnt);
- }
- for (r = 0; r <= reg_float; r++) {
- fprintf(stderr, "#%s = %d\n",str_regtypes[r],cnt_regtypes[r]);
- }
- }
|