util/ego/ra/ra_allocl.c

   1 /* $Id: ra_allocl.c,v 1.6 1994/06/24 10:27:27 ceriel Exp $ */
   2 /*
   3  * (c) copyright 1987 by the Vrije Universiteit, Amsterdam, The Netherlands.
   4  * See the copyright notice in the ACK home directory, in the file "Copyright".
   5  */
   6 /*  R E G I S T E R   A L L O C A T I O N
   7  *
   8  *  R A _ A L L O C L I S T . C
   9  */
  10
  11 #include <em_mnem.h>
  12 #include <em_spec.h>
  13 #include <em_pseu.h>
  14 #include <em_reg.h>
  15 #include "../share/types.h"
  16 #include "../share/debug.h"
  17 #include "../share/def.h"
  18 #include "../share/global.h"
  19 #include "../share/lset.h"
  20 #include "../share/cset.h"
  21 #include "../share/aux.h"
  22 #include "../share/alloc.h"
  23 #include "../share/map.h"
  24 #include "ra.h"
  25 #include "ra_aux.h"
  26 #include "ra_items.h"
  27 #include "ra_allocl.h"
  28 #include "ra_interv.h"
  29
  30 STATIC count_usage(p,item,nrloops,sloopcnt,dloopcnt)
  31         proc_p p;
  32         item_p item;
  33         short  nrloops, sloopcnt[], dloopcnt[];
  34 {
  35         /* Determine how many times the item is used in every loop.
  36          * We maintain a 'static' count and a 'dynamic' count. The dynamic
  37          * count estimates the number of times the item is used during
  38          * execution, i.e. it gives a higher mark to items used inside
  39          * a loop.
  40          */
  41
  42         lset loops;
  43         loop_p l;
  44         int i;
  45         short lev;
  46         Lindex ui,li;
  47         time_p u;
  48
  49         for (i = 0; i <= nrloops; i++) {
  50                 sloopcnt[i] = 0;
  51                 dloopcnt[i] = 0;
  52         }
  53         for (ui = Lfirst(item->it_usage); ui != (Lindex) 0;
  54                                           ui = Lnext(ui,item->it_usage)) {
  55                 u = (time_p) Lelem(ui);
  56                 loops = u->t_bblock->b_loops;
  57                 lev = Lnrelems(loops);
  58                 /* set of loops in which this usage of item occurs */
  59                 for (li = Lfirst(loops); li != (Lindex) 0; li=Lnext(li,loops)) {
  60                         l = (loop_p) Lelem(li);
  61                         sloopcnt[l->lp_id]++;
  62                         dloopcnt[l->lp_id] +=
  63                                 (IS_FIRM(u->t_bblock) ? loop_scale(lev) : 1);
  64                 }
  65         }
  66 }
  67
  68
  69
  70 STATIC alloc_p cons_alloc(item,timespan,stat_usecount,
  71                           dyn_usecount,inits,wholeproc,isloop,iswholeproc)
  72         item_p item;
  73         interv_p timespan;
  74         short stat_usecount,dyn_usecount;
  75         lset inits;
  76         alloc_p wholeproc;
  77         bool isloop,iswholeproc;
  78 {
  79         alloc_p x;
  80
  81         x = newalloc();
  82         x->al_id = ++alloc_id;
  83         x->al_item = item;
  84         x->al_timespan = timespan;
  85         x->al_susecount = stat_usecount;
  86         x->al_dusecount = dyn_usecount;
  87         x->al_inits = inits;
  88         x->al_wholeproc = wholeproc;
  89         x->al_isloop = isloop;
  90         x->al_iswholeproc = iswholeproc;
  91         return x;
  92 }
  93
  94
  95 STATIC insert_alloc(alloc,list_p)
  96         alloc_p alloc, *list_p;
  97 {
  98         alloc->al_next = *list_p;
  99         *list_p = alloc;
 100 }
 101
 102
 103
 104 #define MUST_INIT(i,b)   (i->it_type!=LOCALVAR ||contains(b->B_BEGIN,i->it_lives))
 105 #define MUST_UPDATE(i,b) (i->it_type==LOCALVAR &&contains(b->B_BEGIN,i->it_lives))
 106
 107 STATIC lset loop_inits(lp,item,header)
 108         loop_p lp;
 109         item_p item;
 110         bblock_p header;
 111 {
 112         /* Build the set of entry points to loop lp where item
 113          * must be initialized
 114          */
 115
 116         lset s = Lempty_set();
 117         if (header != (bblock_p) 0 && MUST_INIT(item,header)) {
 118                 Ladd(header,&s);
 119         }
 120         return s;
 121 }
 122
 123
 124
 125 #define IN_LOOP(b)      (Lnrelems(b->b_loops) > 0)
 126
 127 STATIC bblock_p init_point(item)
 128         item_p item;
 129 {
 130         /* Find the most appropriate point to initialize any register
 131          * containing the item. We want to do the initialization as
 132          * late as possible, to allow other items to be put in the
 133          * same register, before this initialization. Yet, as we want
 134          * to do the initialization only once, it must be done in a
 135          * basic block that is a dominator of all points where the
 136          * item is used (ultimately in the first block of the procedure).
 137          * This basic block should not be part of loop.
 138          */
 139
 140         bblock_p b,dom = 0;
 141         Lindex ti;
 142         time_p t;
 143
 144         for (ti = Lfirst(item->it_usage); ti != (Lindex) 0;
 145                                         ti = Lnext(ti,item->it_usage)) {
 146                 t = (time_p) Lelem(ti);
 147                 b = t->t_bblock;
 148                 dom = (dom == (bblock_p) 0 ? b : common_dom(dom,b));
 149         }
 150         while (IN_LOOP(dom)) {
 151                 /* Find a dominator of dom (possibly
 152                  * dom itself) that is outside any loop.
 153                  */
 154                 dom = dom->b_idom;
 155         }
 156         return dom;
 157 }
 158
 159
 160 STATIC add_blocks(b,s,span)
 161         bblock_p b;
 162         cset *s;
 163         interv_p *span;
 164 {
 165         Lindex pi;
 166
 167         if (!Cis_elem(b->b_id,*s)) {
 168                 Cadd(b->b_id,s);
 169                 add_interval(b->B_BEGIN,b->B_END,span);
 170                 for (pi = Lfirst(b->b_pred); pi != (Lindex) 0;
 171                                 pi = Lnext(pi,b->b_pred)) {
 172                         add_blocks((bblock_p) Lelem(pi),s,span);
 173                 }
 174         }
 175 }
 176
 177
 178
 179 STATIC whole_lifetime(item,ini_out,span_out)
 180         item_p item;
 181         bblock_p *ini_out;
 182         interv_p *span_out;
 183 {
 184         /* Find the initialization point and the time_span of the item, if
 185          * we put the item in a register during all its uses.
 186          */
 187
 188         bblock_p b, ini = init_point(item);
 189         cset s = Cempty_set(blength);
 190         Lindex ti;
 191         time_p t;
 192         interv_p span = (interv_p) 0;
 193
 194         for (ti = Lfirst(item->it_usage); ti != (Lindex) 0;
 195                                         ti = Lnext(ti,item->it_usage)) {
 196                 t = (time_p) Lelem(ti);
 197                 b = t->t_bblock;
 198                 add_blocks(b,&s,&span);
 199         }
 200         if (!Cis_elem(ini->b_id,s)) {
 201                 add_interval(ini->B_BEGIN,ini->B_END,&span);
 202         }
 203         Cdeleteset(s);
 204         *ini_out = ini;
 205         *span_out = span;
 206 }
 207
 208
 209
 210
 211 STATIC lset proc_inits(p,item,ini)
 212         proc_p p;
 213         item_p item;
 214         bblock_p ini;
 215 {
 216         lset s = Lempty_set();
 217
 218         if (item->it_type != LOCALVAR || item->i_t.it_off >= 0) {
 219                 /* only local variables need not be initialized */
 220                 Ladd(ini, &s);
 221         }
 222         return s;
 223 }
 224
 225
 226 STATIC bool updates_needed(lp,item)
 227         loop_p lp;
 228         item_p item;
 229 {
 230         /* See if the value of item is live after the loop has
 231          * been exited, i.e. must the item be updated after the loop?
 232          */
 233
 234         Lindex bi,si;
 235         bblock_p b,s;
 236
 237         for (bi = Lfirst(lp->LP_BLOCKS); bi != (Lindex) 0;
 238                                         bi = Lnext(bi,lp->LP_BLOCKS)) {
 239                 b = (bblock_p) Lelem(bi);
 240                 for (si = Lfirst(b->b_succ); si != (Lindex) 0;
 241                                         si = Lnext(si,b->b_succ)) {
 242                         s = (bblock_p) Lelem(si);
 243                         if (!Lis_elem(s,lp->LP_BLOCKS) && MUST_UPDATE(item,s)) {
 244                                 return TRUE;
 245                         }
 246                 }
 247         }
 248         return FALSE;
 249 }
 250
 251
 252
 253 STATIC short countuses(usage,b)
 254         lset usage;
 255         bblock_p b;
 256 {
 257         short cnt = 0;
 258         Lindex ti;
 259         time_p t;
 260
 261         for (ti = Lfirst(usage); ti != (Lindex) 0; ti = Lnext(ti,usage)) {
 262                 t = (time_p) Lelem(ti);
 263                 if (t->t_bblock == b) cnt++;
 264         }
 265         return cnt;
 266 }
 267
 268
 269
 270 STATIC allocs_of_item(p,item,loops,sloopcnt,dloopcnt,alloc_list_p)
 271         proc_p p;
 272         item_p item;
 273         lset loops;
 274         short *sloopcnt,*dloopcnt; /* dynamic arrays */
 275         alloc_p *alloc_list_p;
 276 {
 277         register Lindex li;
 278         loop_p lp;
 279         bblock_p header,ini;
 280         short susecount,dusecount;
 281         interv_p lt;
 282         alloc_p wholeproc;
 283
 284         /* The whole procedure may be used as timespan.
 285            The dynamic usecount of a procedure is taken to be the same
 286            as its static usecount; this number is not very important, as
 287            time-optimziation chooses loops first.
 288          */
 289         whole_lifetime(item,&ini,&lt);
 290         wholeproc = cons_alloc(item,lt,Lnrelems(item->it_usage),
 291                                Lnrelems(item->it_usage), proc_inits(p,item,ini),
 292                                (alloc_p) 0,FALSE,TRUE);
 293         insert_alloc(wholeproc, alloc_list_p);
 294         for (li = Lfirst(loops); li != (Lindex) 0; li = Lnext(li,loops)) {
 295                 lp = (loop_p) Lelem(li);
 296                 if (sloopcnt[lp->lp_id] != 0 && !updates_needed(lp,item)
 297                     && !((header = lp->LP_HEADER) == (bblock_p) 0 &&
 298                                 MUST_INIT(item,lp->lp_entry))) {
 299                         /* Item is used within loop, so consider loop
 300                          * as a timespan during which item may be put in
 301                          * a register.
 302                         if ((header = lp->LP_HEADER) == (bblock_p) 0 &&
 303                                 MUST_INIT(item,lp->lp_entry)) continue;
 304                          */
 305                         lt = loop_lifetime(lp);
 306                         susecount = sloopcnt[lp->lp_id];
 307                         dusecount = dloopcnt[lp->lp_id];
 308                         if (MUST_INIT(item,lp->lp_entry)) {
 309                                /* include header block in timespan */
 310                                add_interval(header->B_BEGIN,header->B_END,&lt);
 311                                susecount += countuses(item->it_usage,header);
 312                         } else {
 313                                 header = (bblock_p) 0;
 314                         }
 315                         insert_alloc(cons_alloc(item,lt,susecount,dusecount,
 316                                      loop_inits(lp,item,header),wholeproc,
 317                                      TRUE,FALSE),
 318                                           alloc_list_p);
 319                 } else if (sloopcnt[lp->lp_id] != 0) {
 320                         /* I confess: this is a hack.  I didn't expect the
 321                          * Spanish inquisition.
 322                          */
 323                         if (wholeproc->al_dusecount < dloopcnt[lp->lp_id])
 324                                 wholeproc->al_dusecount = dloopcnt[lp->lp_id];
 325                 }
 326         }
 327 }
 328
 329
 330
 331 alloc_p build_alloc_list(p,nrloops,itemlist)
 332         proc_p p;
 333         short nrloops;
 334         item_p itemlist;
 335 {
 336         short *sloopcnt,*dloopcnt; /* dynamic arrays */
 337         register item_p item;
 338         alloc_p alloc_list = (alloc_p) 0;
 339
 340         sloopcnt = (short *) newtable(nrloops);
 341         dloopcnt = (short *) newtable(nrloops);
 342         for (item = itemlist; item != (item_p) 0; item = item->it_next) {
 343                 count_usage(p,item,nrloops,sloopcnt,dloopcnt);
 344                 allocs_of_item(p,item,p->p_loops,sloopcnt,dloopcnt,
 345                                 &alloc_list);
 346         }
 347         oldtable(sloopcnt,nrloops);
 348         oldtable(dloopcnt,nrloops);
 349         return alloc_list;
 350 }
 351
 352
 353
 354 build_rivals_graph(alloclist)
 355         alloc_p alloclist;
 356 {
 357         /* See which allocations in the list are rivals of each other,
 358          * i.e. there is some point of time, falling in both
 359          * timespans, at which the items of both allocations are live.
 360          * Allocations with the same item (but different timespans) are
 361          * not considered to be rivals.
 362          * We use an auxiliary data structure "busy" for each allocation,
 363          * indicating when the item is live during the timespan of the
 364          * allocation.
 365          */
 366
 367         register alloc_p alloc,x;
 368
 369         for (alloc = alloclist; alloc != (alloc_p) 0; alloc = alloc->al_next) {
 370                 alloc->al_rivals = Cempty_set(alloc_id);
 371         }
 372         for (alloc = alloclist; alloc != (alloc_p) 0; alloc = alloc->al_next) {
 373                 alloc->al_busy =
 374                    (alloc->al_item->it_type == LOCALVAR ?
 375                         intersect(alloc->al_timespan,alloc->al_item->it_lives) :
 376                         copy_timespan(alloc->al_timespan));
 377                 for (x = alloclist; x != alloc; x = x->al_next) {
 378                         if (x->al_item != alloc->al_item &&
 379                             not_disjoint(alloc->al_busy,x->al_busy)) {
 380                                 Cadd(x->al_id,&alloc->al_rivals);
 381                                 Cadd(alloc->al_id,&x->al_rivals);
 382                                 if (alloc->al_regtype == x->al_regtype) {
 383                                         alloc->al_cntrivals++;
 384                                         x->al_cntrivals++;
 385                                 }
 386                         }
 387                 }
 388         }
 389 }