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".
- */
- /* R E G I S T E R A L L O C A T I O N
- *
- * R A _ P A C K . C
- */
- #include <em_reg.h>
- #include "../share/types.h"
- #include "../share/debug.h"
- #include "../share/def.h"
- #include "../share/global.h"
- #include "../share/lset.h"
- #include "../share/cset.h"
- #include "../share/alloc.h"
- #include "../share/aux.h"
- #include "ra.h"
- #include "ra_aux.h"
- #include "ra_interv.h"
- short regs_occupied[NRREGTYPES]; /* #occupied registers for reg_pointer,
- * reg_any etc.
- */
- #define reg_available(t) (regs_available[t] > regs_occupied[t])
- static void initregcount()
- {
- int t;
- for (t = 0; t < NRREGTYPES; t++) {
- regs_occupied[t] = 0;
- }
- }
- static alloc_p make_dummy()
- {
- alloc_p x;
- x = newalloc();
- /* x->al_profits = 0; */
- return x;
- }
- static bool fits_in(alloc_p a, alloc_p b, bool *cont_item)
- {
- /* See if allocation a can be assigned the same register as b.
- * Both allocations should be of the same register-type.
- * Note that there may be several other allocations (mates) assigned to
- * the same register as b. A new candidate (i.e. 'a') is only
- * allowed to join them if it is not the rival of any resident
- * allocation.
- */
- *cont_item = FALSE;
- if (a->al_regtype == b->al_regtype) {
- while (b != (alloc_p) 0) {
- if (Cis_elem(a->al_id,b->al_rivals)) break;
- b = b->al_mates;
- if (b != (alloc_p) 0 && a->al_item == b->al_item) {
- *cont_item = TRUE;
- }
- }
- }
- return b == (alloc_p) 0;
- }
- static alloc_p find_fitting_alloc(alloc_p alloc, alloc_p packed)
- {
- /* Try to find and already packed allocation that is assigned
- * a register that may also be used for alloc.
- * We prefer allocations that have the same item as alloc.
- */
- alloc_p x;
- alloc_p cand = (alloc_p) 0;
- bool cont_item;
- for (x = packed->al_next; x != (alloc_p) 0; x = x->al_next) {
- if (fits_in(alloc,x,&cont_item)) {
- cand = x;
- if (cont_item) break;
- }
- }
- return cand;
- }
- static bool room_for(alloc_p alloc, alloc_p packed)
- {
- /* See if there is any register available for alloc */
- return reg_available(alloc->al_regtype) ||
- (find_fitting_alloc(alloc,packed) != (alloc_p) 0);
- }
- static alloc_p best_alloc(alloc_p unpacked, alloc_p packed, bool time_opt)
- {
- /* Find the next best candidate */
- alloc_p x,best;
- best = unpacked; /* dummy */
- for (x = unpacked->al_next; x != (alloc_p) 0; x = x->al_next) {
- if (x->al_profits > best->al_profits &&
- room_for(x,packed)) {
- best = x;
- }
- }
- return (best == unpacked ? (alloc_p) 0 : best);
- }
- static alloc_p choose_location(alloc_p alloc, alloc_p packed, proc_p p)
- {
- /* Decide in which register to put alloc */
- alloc_p fit;
- offset dum;
- fit = find_fitting_alloc(alloc,packed);
- if (fit == (alloc_p) 0) {
- /* Take a brand new register; allocate a dummy local for it */
- alloc->al_regnr = regs_occupied[alloc->al_regtype]++;
- dum = tmplocal(p,(offset) alloc->al_item->it_size);
- alloc->al_dummy = dum;
- } else {
- alloc->al_regnr = fit->al_regnr;
- alloc->al_dummy = fit->al_dummy;
- }
- return fit;
- }
- static void update_lists(alloc_p alloc, alloc_p unpacked, alloc_p packed, alloc_p fit)
- {
- /* 'alloc' has been granted a register; move it from the 'unpacked'
- * list to the 'packed' list. Also remove any allocation from 'unpacked'
- * having:
- * 1. the same item as 'alloc' and
- * 2. a timespan that overlaps the timespan of alloc.
- */
- alloc_p x,q,next;
- q = unpacked; /* dummy element at head of list */
- for (x = unpacked->al_next; x != (alloc_p) 0; x = next) {
- next = x->al_next;
- if (x->al_item == alloc->al_item &&
- not_disjoint(x->al_timespan, alloc->al_timespan)) {
- /* this code kills two birds with one stone;
- * x is either an overlapping allocation or
- * alloc itself!
- */
- q->al_next = x->al_next;
- if (x == alloc) {
- if (fit == (alloc_p) 0) {
- x->al_next = packed->al_next;
- packed->al_next = x;
- } else {
- x->al_mates = fit->al_mates;
- fit->al_mates = x;
- x->al_next = (alloc_p) 0;
- }
- }
- } else {
- q = x;
- }
- }
- }
- static short cum_profits(alloc_p alloc)
- {
- /* Add the profits of all allocations packed in the same
- * register as alloc (i.e. alloc and all its 'mates').
- */
-
- alloc_p m;
- short sum = 0;
- for (m = alloc; m != (alloc_p) 0; m = m->al_mates) {
- sum += m->al_profits;
- }
- return sum;
- }
- static void best_cumprofits(alloc_p list, alloc_p *x_out, alloc_p *prev_out)
- {
- /* Find the allocation with the best cummulative profits */
- alloc_p x,prev,best_prev;
- short best = 0, cum;
- prev = list;
- for (x = list->al_next; x != (alloc_p) 0; x = x->al_next) {
- cum = cum_profits(x);
- if (cum > best) {
- best = cum;
- best_prev = prev;
- }
- prev = x;
- }
- if (best == 0) {
- *x_out = (alloc_p) 0;
- } else {
- *x_out = best_prev->al_next;
- *prev_out = best_prev;
- }
- }
- static void account_regsave(alloc_p packed, alloc_p unpacked)
- {
- /* After all packing has been done, we check for every allocated
- * register whether it is really advantageous to use this
- * register. It may be possible that the cost of saving
- * and restoring the register are higher than the profits of all
- * allocations packed in the register. If so, we simply remove
- * all these allocations.
- * The cost of saving/restoring one extra register may depend on
- * the number of registers already saved.
- */
- alloc_p x,prev,checked;
- short time,space;
- short tot_cost = 0,diff;
- initregcount();
- checked = make_dummy();
- while (TRUE) {
- best_cumprofits(packed,&x,&prev);
- if (x == (alloc_p) 0) break;
- regs_occupied[x->al_regtype]++;
- regsave_cost(regs_occupied,&time,&space);
- diff = add_timespace(time,space) - tot_cost;
- if (diff < cum_profits(x)) {
- /* x is o.k. */
- prev->al_next = x->al_next;
- x->al_next = checked->al_next;
- checked->al_next = x;
- tot_cost += diff;
- } else {
- break;
- }
- }
- /* Now every allocation in 'packed' does not pay off, so
- * it is moved to unpacked, indicating it will not be assigned
- * a register.
- */
- for (x = unpacked; x->al_next != (alloc_p) 0; x = x->al_next);
- x->al_next = packed->al_next;
- packed->al_next = checked->al_next;
- oldalloc(checked);
- }
- static bool in_single_reg(item_p item, alloc_p packed)
- {
- /* See if item is allocated in only one register (i.e. not in
- * several different registers during several parts of its lifetime.
- */
- alloc_p x,m;
- bool seen = FALSE;
- for (x = packed->al_next; x != (alloc_p) 0; x = x->al_next) {
- for ( m = x; m != (alloc_p) 0; m = m->al_mates) {
- if (m->al_item == item) {
- if (seen) return FALSE;
- seen = TRUE;
- break;
- }
- }
- }
- return TRUE;
- }
- static alloc_p find_prev(alloc_p alloc, alloc_p list)
- {
- alloc_p x;
- assert ( alloc != (alloc_p) 0);
- for (x = list; x->al_next != alloc ; x = x->al_next)
- assert(x != (alloc_p) 0);
- return x;
- }
- /* If an item is always put in the same register during different loops,
- * we try to put it in that register during the whole procedure.
- * The profits of the whole-procedure allocation are updated to prevent
- * account_regsave from rejecting it.
- */
- static void repl_allocs(alloc_p new, alloc_p old, alloc_p packed)
- {
- alloc_p x,next,prev,*p;
- short prof = 0;
- new->al_regnr = old->al_regnr;
- new->al_dummy = old->al_dummy;
- prev = find_prev(old,packed);
- new->al_next = old->al_next;
- old->al_next = (alloc_p) 0;
- prev->al_next = new;
- new->al_mates = old;
- p = &new->al_mates;
- for (x = old; x != (alloc_p) 0; x = next) {
- next = x->al_mates;
- if (x->al_item == new->al_item) {
- prof += x->al_profits;
- *p = next;
- oldalloc(x);
- } else {
- p = &x->al_mates;
- }
- }
- new->al_profits = prof;
- }
- static void assemble_allocs(alloc_p packed)
- {
- alloc_p x,m,next;
- alloc_p e;
- bool voidb;
- for (x = packed->al_next; x != (alloc_p) 0; x = next) {
- next = x->al_next;
- for ( m = x; m != (alloc_p) 0; m = m->al_mates) {
- if (in_single_reg(m->al_item,packed) &&
- (e = m->al_wholeproc) != (alloc_p) 0 &&
- e->al_profits > 0 &&
- fits_in(e,x,&voidb)) {
- repl_allocs(e,x,packed);
- break;
- }
- }
- }
- }
- void pack(alloc_p alloclist, bool time_opt, alloc_p *packed_out, alloc_p *not_packed_out, proc_p p)
- {
- /* This is the packing system. It decides which allations
- * to grant a register.
- * We use two lists: packed (for allocations that are assigned a
- * register) and unpacked (allocations not yet assigned a register).
- * The packed list is in fact '2-dimensional': the al_next field is
- * used to link allations that are assigned different registers;
- * the al_mates field links allocations that are assigned to
- * the same registers (i.e. these allocations fit together).
- */
- alloc_p x;
- alloc_p packed,unpacked,fit;
- initregcount();
- packed = make_dummy();
- unpacked = make_dummy();
- unpacked->al_next = alloclist;
- while ((x = best_alloc(unpacked,packed,time_opt)) != (alloc_p) 0) {
- fit = choose_location(x,packed,p);
- update_lists(x,unpacked,packed,fit);
- }
- assemble_allocs(packed);
- account_regsave(packed,unpacked);
- /* remove allocations that don't pay off against register
- * save/restore costs.
- */
- *packed_out = packed->al_next;
- *not_packed_out = unpacked->al_next;
- oldalloc(packed);
- oldalloc(unpacked);
- }
|