util/ego/ra/ra_pack.c

   1 /* $Id: ra_pack.c,v 1.8 1994/06/24 10:27:56 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 _ P A C K . C
   9  */
  10
  11 #include <em_reg.h>
  12 #include "../share/types.h"
  13 #include "../share/debug.h"
  14 #include "../share/def.h"
  15 #include "../share/global.h"
  16 #include "../share/lset.h"
  17 #include "../share/cset.h"
  18 #include "../share/alloc.h"
  19 #include "../share/aux.h"
  20 #include "ra.h"
  21 #include "ra_aux.h"
  22 #include "ra_interv.h"
  23
  24
  25 short regs_occupied[NRREGTYPES];        /* #occupied registers for reg_pointer,
  26                                          * reg_any etc.
  27                                          */
  28 #define reg_available(t)        (regs_available[t] > regs_occupied[t])
  29
  30 STATIC initregcount()
  31 {
  32         int t;
  33
  34         for (t = 0; t < NRREGTYPES; t++) {
  35                 regs_occupied[t] = 0;
  36         }
  37 }
  38
  39 STATIC alloc_p make_dummy()
  40 {
  41         alloc_p x;
  42
  43         x = newalloc();
  44         /* x->al_profits = 0; */
  45         return x;
  46 }
  47
  48
  49 STATIC bool fits_in(a,b,cont_item)
  50         alloc_p a,b;
  51         bool *cont_item;
  52 {
  53         /* See if allocation a can be assigned the same register as b.
  54          * Both allocations should be of the same register-type.
  55          * Note that there may be several other allocations (mates) assigned to
  56          * the same register as b. A new candidate (i.e. 'a') is only
  57          * allowed to join them if it is not the rival of any resident
  58          * allocation.
  59          */
  60
  61         *cont_item = FALSE;
  62         if (a->al_regtype == b->al_regtype) {
  63                 while (b != (alloc_p) 0) {
  64                         if (Cis_elem(a->al_id,b->al_rivals)) break;
  65                         b = b->al_mates;
  66                         if (b != (alloc_p) 0 && a->al_item == b->al_item) {
  67                                 *cont_item = TRUE;
  68                         }
  69                 }
  70         }
  71         return b == (alloc_p) 0;
  72 }
  73
  74
  75 STATIC alloc_p find_fitting_alloc(alloc,packed)
  76         alloc_p alloc,packed;
  77 {
  78         /* Try to find and already packed allocation that is assigned
  79          * a register that may also be used for alloc.
  80          * We prefer allocations that have the same item as alloc.
  81          */
  82
  83         register alloc_p x;
  84         alloc_p cand = (alloc_p) 0;
  85         bool cont_item;
  86
  87         for (x = packed->al_next; x != (alloc_p) 0; x = x->al_next) {
  88                 if (fits_in(alloc,x,&cont_item)) {
  89                         cand = x;
  90                         if (cont_item) break;
  91                 }
  92         }
  93         return cand;
  94 }
  95
  96
  97 STATIC bool room_for(alloc,packed)
  98         alloc_p alloc,packed;
  99 {
 100         /* See if there is any register available for alloc */
 101
 102         return reg_available(alloc->al_regtype) ||
 103                 (find_fitting_alloc(alloc,packed) != (alloc_p) 0);
 104 }
 105
 106
 107
 108 STATIC alloc_p best_alloc(unpacked,packed,time_opt)
 109         alloc_p unpacked,packed;
 110         bool time_opt;  /* now unused */
 111 {
 112         /* Find the next best candidate */
 113
 114         register alloc_p x,best;
 115
 116         best = unpacked; /* dummy */
 117
 118         for (x = unpacked->al_next; x != (alloc_p) 0; x = x->al_next) {
 119                 if (x->al_profits > best->al_profits &&
 120                     room_for(x,packed)) {
 121                         best = x;
 122                 }
 123         }
 124         return (best == unpacked ? (alloc_p) 0 : best);
 125 }
 126
 127
 128
 129
 130 STATIC alloc_p choose_location(alloc,packed,p)
 131         alloc_p alloc,packed;
 132         proc_p p;
 133 {
 134         /* Decide in which register to put alloc */
 135
 136         alloc_p fit;
 137         offset dum;
 138
 139         fit = find_fitting_alloc(alloc,packed);
 140         if (fit == (alloc_p) 0) {
 141                 /* Take a brand new register; allocate a dummy local for it */
 142                 alloc->al_regnr = regs_occupied[alloc->al_regtype]++;
 143                 dum = tmplocal(p,(offset) alloc->al_item->it_size);
 144                 alloc->al_dummy = dum;
 145         } else {
 146                 alloc->al_regnr = fit->al_regnr;
 147                 alloc->al_dummy = fit->al_dummy;
 148         }
 149         return fit;
 150 }
 151
 152
 153
 154 STATIC update_lists(alloc,unpacked,packed,fit)
 155         alloc_p alloc,unpacked,packed,fit;
 156 {
 157         /* 'alloc' has been granted a register; move it from the 'unpacked'
 158          * list to the 'packed' list. Also remove any allocation from 'unpacked'
 159          * having:
 160          *  1. the same item as 'alloc' and
 161          *  2. a timespan that overlaps the timespan of alloc.
 162          */
 163
 164         register alloc_p x,q,next;
 165
 166         q = unpacked; /* dummy element at head of list */
 167         for (x = unpacked->al_next; x != (alloc_p) 0; x = next) {
 168                 next = x->al_next;
 169                 if (x->al_item == alloc->al_item &&
 170                     not_disjoint(x->al_timespan, alloc->al_timespan)) {
 171                         /* this code kills two birds with one stone;
 172                          * x is either an overlapping allocation or
 173                          * alloc itself!
 174                          */
 175                         q->al_next = x->al_next;
 176                         if (x == alloc) {
 177                                 if (fit == (alloc_p) 0) {
 178                                         x->al_next = packed->al_next;
 179                                         packed->al_next = x;
 180                                 } else {
 181                                         x->al_mates = fit->al_mates;
 182                                         fit->al_mates = x;
 183                                         x->al_next = (alloc_p) 0;
 184                                 }
 185                         }
 186                 } else {
 187                         q = x;
 188                 }
 189         }
 190 }
 191
 192
 193
 194 STATIC short cum_profits(alloc)
 195         alloc_p alloc;
 196 {
 197         /* Add the profits of all allocations packed in the same
 198          * register as alloc (i.e. alloc and all its 'mates').
 199          */
 200
 201         alloc_p m;
 202         short sum = 0;
 203
 204         for (m = alloc; m != (alloc_p) 0; m = m->al_mates) {
 205                 sum += m->al_profits;
 206         }
 207         return sum;
 208 }
 209
 210
 211
 212 STATIC alloc_p best_cumprofits(list,x_out,prev_out)
 213         alloc_p list, *x_out, *prev_out;
 214 {
 215         /* Find the allocation with the best cummulative profits */
 216
 217         register alloc_p x,prev,best_prev;
 218         short best = 0, cum;
 219
 220         prev = list;
 221         for (x = list->al_next; x != (alloc_p) 0; x = x->al_next) {
 222                 cum = cum_profits(x);
 223                 if (cum > best) {
 224                         best = cum;
 225                         best_prev = prev;
 226                 }
 227                 prev = x;
 228         }
 229         if (best == 0) {
 230                 *x_out = (alloc_p) 0;
 231         } else {
 232                 *x_out = best_prev->al_next;
 233                 *prev_out = best_prev;
 234         }
 235 }
 236
 237
 238
 239 STATIC account_regsave(packed,unpacked)
 240         alloc_p packed,unpacked;
 241 {
 242         /* After all packing has been done, we check for every allocated
 243          * register whether it is really advantageous to use this
 244          * register. It may be possible that the cost of saving
 245          * and restoring the register are higher than the profits of all
 246          * allocations packed in the register. If so, we simply remove
 247          * all these allocations.
 248          * The cost of saving/restoring one extra register may depend on
 249          * the number of registers already saved.
 250          */
 251
 252         alloc_p x,prev,checked;
 253         short time,space;
 254         short tot_cost = 0,diff;
 255
 256         initregcount();
 257         checked = make_dummy();
 258         while (TRUE) {
 259                 best_cumprofits(packed,&x,&prev);
 260                 if (x == (alloc_p) 0) break;
 261                 regs_occupied[x->al_regtype]++;
 262                 regsave_cost(regs_occupied,&time,&space);
 263                 diff = add_timespace(time,space) - tot_cost;
 264                 if (diff < cum_profits(x)) {
 265                         /* x is o.k. */
 266                         prev->al_next = x->al_next;
 267                         x->al_next = checked->al_next;
 268                         checked->al_next = x;
 269                         tot_cost += diff;
 270                 } else {
 271                         break;
 272                 }
 273         }
 274         /* Now every allocation in 'packed' does not pay off, so
 275          * it is moved to unpacked, indicating it will not be assigned
 276          * a register.
 277          */
 278         for (x = unpacked; x->al_next != (alloc_p) 0; x = x->al_next);
 279         x->al_next = packed->al_next;
 280         packed->al_next = checked->al_next;
 281         oldalloc(checked);
 282 }
 283
 284
 285
 286 STATIC bool in_single_reg(item,packed)
 287         item_p item;
 288         alloc_p packed;
 289 {
 290         /* See if item is allocated in only one register (i.e. not in
 291          * several different registers during several parts of its lifetime.
 292          */
 293
 294         register alloc_p x,m;
 295         bool seen = FALSE;
 296
 297         for (x = packed->al_next; x != (alloc_p) 0; x = x->al_next) {
 298                 for ( m = x; m != (alloc_p) 0; m = m->al_mates) {
 299                         if (m->al_item == item) {
 300                                 if (seen) return FALSE;
 301                                 seen = TRUE;
 302                                 break;
 303                         }
 304                 }
 305         }
 306         return TRUE;
 307 }
 308
 309
 310
 311 STATIC alloc_p find_prev(alloc,list)
 312         alloc_p alloc,list;
 313 {
 314         register alloc_p x;
 315
 316         assert ( alloc != (alloc_p) 0);
 317         for (x = list; x->al_next != alloc ; x = x->al_next)
 318                 assert(x != (alloc_p) 0);
 319         return x;
 320 }
 321
 322
 323 /* If an item is always put in the same register during different loops,
 324  * we try to put it in that register during the whole procedure.
 325  * The profits of the whole-procedure allocation are updated to prevent
 326  * account_regsave from rejecting it.
 327  */
 328
 329 STATIC repl_allocs(new,old,packed)
 330         alloc_p new,old,packed;
 331 {
 332         alloc_p x,next,prev,*p;
 333         short prof = 0;
 334
 335         new->al_regnr = old->al_regnr;
 336         new->al_dummy = old->al_dummy;
 337         prev = find_prev(old,packed);
 338         new->al_next = old->al_next;
 339         old->al_next = (alloc_p) 0;
 340         prev->al_next = new;
 341         new->al_mates = old;
 342         p = &new->al_mates;
 343         for (x = old; x != (alloc_p) 0; x = next) {
 344                 next = x->al_mates;
 345                 if (x->al_item == new->al_item) {
 346                         prof += x->al_profits;
 347                         *p = next;
 348                         oldalloc(x);
 349                 } else {
 350                         p = &x->al_mates;
 351                 }
 352         }
 353         new->al_profits = prof;
 354 }
 355
 356
 357
 358 STATIC assemble_allocs(packed)
 359         alloc_p packed;
 360 {
 361         register alloc_p x,m,next;
 362         alloc_p e;
 363         bool voidb;
 364
 365         for (x = packed->al_next; x != (alloc_p) 0; x = next) {
 366                 next = x->al_next;
 367                 for ( m = x; m != (alloc_p) 0; m = m->al_mates) {
 368                         if (in_single_reg(m->al_item,packed) &&
 369                             (e = m->al_wholeproc) != (alloc_p) 0 &&
 370                             e->al_profits > 0 &&
 371                             fits_in(e,x,&voidb)) {
 372                                 repl_allocs(e,x,packed);
 373                                 break;
 374                         }
 375                 }
 376         }
 377 }
 378
 379 pack(alloclist,time_opt,packed_out,not_packed_out,p)
 380         alloc_p alloclist, *packed_out,*not_packed_out;
 381         bool time_opt;
 382         proc_p p;
 383 {
 384         /* This is the packing system. It decides which allations
 385          * to grant a register.
 386          * We use two lists: packed (for allocations that are assigned a
 387          * register) and unpacked (allocations not yet assigned a register).
 388          * The packed list is in fact '2-dimensional': the al_next field is
 389          * used to link allations that are assigned different registers;
 390          * the al_mates field links allocations that are assigned to
 391          * the same registers (i.e. these allocations fit together).
 392          */
 393
 394         register alloc_p x;
 395         alloc_p packed,unpacked,fit;
 396
 397         initregcount();
 398         packed = make_dummy();
 399         unpacked = make_dummy();
 400         unpacked->al_next = alloclist;
 401         while ((x = best_alloc(unpacked,packed,time_opt)) != (alloc_p) 0) {
 402                 fit = choose_location(x,packed,p);
 403                 update_lists(x,unpacked,packed,fit);
 404         }
 405         assemble_allocs(packed);
 406         account_regsave(packed,unpacked);
 407         /* remove allocations that don't pay off against register
 408          * save/restore costs.
 409          */
 410         *packed_out = packed->al_next;
 411         *not_packed_out = unpacked->al_next;
 412         oldalloc(packed);
 413         oldalloc(unpacked);
 414 }