util/ego/ra/ra.c

   1 /* $Id: ra.c,v 1.14 1995/11/08 11:08:06 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 /*
   7  *   R E G I S T E R    A L L O C A T I O N
   8  *
   9  */
  10
  11 #include <stdio.h>
  12 #include <em_reg.h>
  13 #include "../share/types.h"
  14 #include "../share/debug.h"
  15 #include "../share/global.h"
  16 #include "../share/files.h"
  17 #include "../share/get.h"
  18 #include "../share/put.h"
  19 #include "../share/lset.h"
  20 #include "../share/map.h"
  21 #include "../share/alloc.h"
  22 #include "../share/go.h"
  23 #include "ra.h"
  24 #include "ra_items.h"
  25 #include "ra_allocl.h"
  26 #include "ra_profits.h"
  27 #include "ra_pack.h"
  28 #include "ra_xform.h"
  29
  30
  31 #define newrabx()       (bext_p)        newstruct(bext_ra)
  32 #define newralpx()      (lpext_p)       newstruct(lpext_ra)
  33 #define oldrabx(x)      oldstruct(bext_ra,x)
  34 #define oldralpx(x)     oldstruct(lpext_ra,x)
  35
  36 short alloc_id;
  37 static item_p items[NRITEMTYPES];
  38 int nrinstrs;
  39 line_p *instrmap;
  40
  41 cond_p alocaltab[NRREGTYPES][NRREGTYPES],alocaddrtab[NRREGTYPES][NRREGTYPES],
  42         aconsttab,adconsttab,aglobaltab,aproctab;
  43 cond_p olocaltab[NRREGTYPES],olocaddrtab[NRREGTYPES],
  44         oconsttab,odconsttab,oglobaltab,oproctab;
  45 cond_p regsav_cost;
  46
  47 short regs_available[] = {
  48         /* Actually machine dependent; this is for vax2 */
  49         3,      /* reg_any i.e. data regs */
  50         0,      /* reg_loop */
  51         3,      /* reg_pointer i.e. address reg. */
  52         0       /* reg_float */
  53 } ;
  54
  55 short use_any_as_pointer = 0;
  56
  57 STATIC cond_p getcondtab(f)
  58         FILE *f;
  59 {
  60         int l,i;
  61         cond_p tab;
  62
  63         fscanf(f,"%d",&l);
  64         tab = newcondtab(l);
  65         for (i = 0; i < l; i++) {
  66                 fscanf(f,"%hd %hd %hd",&tab[i].mc_cond,&tab[i].mc_tval,
  67                          &tab[i].mc_sval);
  68         }
  69         assert(tab[l-1].mc_cond == DEFAULT);
  70         return tab;
  71 }
  72
  73 get_atab(f,tab)
  74         FILE *f;
  75         cond_p tab[NRREGTYPES][NRREGTYPES];
  76 {
  77         int i,cnt,totyp,regtyp;
  78
  79         fscanf(f,"%d",&cnt);
  80         for (i = 0; i < cnt; i++) {
  81                 fscanf(f,"%d %d",&regtyp,&totyp);
  82                 assert(regtyp >= 0  && regtyp < NRREGTYPES);
  83                 assert(totyp >= 0  && totyp < NRREGTYPES);
  84                 tab[regtyp][totyp] = getcondtab(f);
  85         }
  86 }
  87
  88
  89 get_otab(f,tab)
  90         FILE *f;
  91         cond_p tab[NRREGTYPES];
  92 {
  93         int i,cnt,regtyp;
  94
  95         fscanf(f,"%d",&cnt);
  96         for (i = 0; i < cnt; i++) {
  97                 fscanf(f,"%d",&regtyp);
  98                 assert(regtyp >= 0  && regtyp < NRREGTYPES);
  99                 tab[regtyp] = getcondtab(f);
 100         }
 101 }
 102
 103
 104
 105 STATIC ra_machinit(f)
 106         FILE *f;
 107 {
 108         /* Read target machine dependent information for this phase */
 109         char s[100];
 110
 111         for (;;) {
 112                 while(getc(f) != '\n');
 113                 fscanf(f,"%s",s);
 114                 if (strcmp(s,"%%RA") == 0)break;
 115         }
 116         fscanf(f,"%hd",&regs_available[reg_any]);
 117         fscanf(f,"%hd",&regs_available[reg_pointer]);
 118         fscanf(f,"%hd",&regs_available[reg_float]);
 119         fscanf(f,"%hd",&use_any_as_pointer);
 120         get_atab(f,alocaltab);
 121         get_atab(f,alocaddrtab);
 122         aconsttab = getcondtab(f);
 123         adconsttab = getcondtab(f);
 124         aglobaltab = getcondtab(f);
 125         aproctab = getcondtab(f);
 126         get_otab(f,olocaltab);
 127         get_otab(f,olocaddrtab);
 128         oconsttab = getcondtab(f);
 129         odconsttab = getcondtab(f);
 130         oglobaltab = getcondtab(f);
 131         oproctab = getcondtab(f);
 132         regsav_cost = getcondtab(f);
 133 }
 134
 135
 136 STATIC bblock_p header(lp)
 137         loop_p lp;
 138 {
 139         /* Try to determine the 'header' block of loop lp.
 140          * If 'e' is the entry block of loop L, then block 'b' is
 141          * called the header block of L, iff:
 142          *      SUCC(b) = {e} & PRED(e) = {b}
 143          * If lp has no header block, 0 is returned.
 144          */
 145
 146         bblock_p x = lp->lp_entry->b_idom;
 147
 148         if (x != (bblock_p) 0 && Lnrelems(x->b_succ) == 1 &&
 149             (bblock_p) Lelem(Lfirst(x->b_succ)) == lp->lp_entry) {
 150                 return x;
 151         }
 152         return (bblock_p) 0;
 153 }
 154
 155
 156 STATIC ra_extproc(p)
 157         proc_p p;
 158 {
 159         /* Allocate the extended data structures for procedure p */
 160
 161         register loop_p lp;
 162         register Lindex pi;
 163         register bblock_p b;
 164
 165         for (pi = Lfirst(p->p_loops); pi != (Lindex) 0;
 166            pi = Lnext(pi,p->p_loops)) {
 167                 lp = (loop_p) Lelem(pi);
 168                 lp->lp_extend = newralpx();
 169                 lp->LP_HEADER = header(lp);
 170         }
 171         for (b = p->p_start; b != (bblock_p) 0; b = b->b_next) {
 172                 b->b_extend = newrabx();
 173         }
 174 }
 175
 176
 177
 178
 179 STATIC ra_cleanproc(p)
 180         proc_p p;
 181 {
 182         /* Allocate the extended data structures for procedure p */
 183
 184         register loop_p lp;
 185         register Lindex pi;
 186         register bblock_p b;
 187
 188         for (pi = Lfirst(p->p_loops); pi != (Lindex) 0;
 189            pi = Lnext(pi,p->p_loops)) {
 190                 lp = (loop_p) Lelem(pi);
 191                 oldralpx(lp->lp_extend);
 192         }
 193         for (b = p->p_start; b != (bblock_p) 0; b = b->b_next) {
 194                 oldrabx(b->b_extend);
 195         }
 196 }
 197
 198
 199
 200 STATIC loop_blocks(p)
 201         proc_p p;
 202 {
 203         /* Compute the LP_BLOCKS sets for all loops of p */
 204
 205         register bblock_p b;
 206         register Lindex i;
 207
 208         for (b = p->p_start; b != (bblock_p) 0; b = b->b_next) {
 209                 for (i = Lfirst(b->b_loops); i != (Lindex) 0;
 210                    i = Lnext(i,b->b_loops)) {
 211                         Ladd(b,&(((loop_p) Lelem(i))->LP_BLOCKS));
 212                 }
 213         }
 214 }
 215
 216
 217
 218
 219 STATIC make_instrmap(p,map)
 220         proc_p p;
 221         line_p map[];
 222 {
 223         /* make the instructions map of procedure p */
 224
 225         register bblock_p b;
 226         register line_p l;
 227         register int i = 0;
 228
 229         for (b = p->p_start; b != (bblock_p) 0; b = b->b_next) {
 230                 b->B_BEGIN = i; /* number of first instruction */
 231                 for (l = b->b_start; l != (line_p) 0; l = l->l_next) {
 232                         map[i++] = l;
 233                 }
 234                 b->B_END = i-1; /* number of last instruction */
 235         }
 236 }
 237
 238
 239
 240 STATIC bool useful_item(item)
 241         item_p item;
 242 {
 243         /* See if it may be useful to put the item in a register.
 244          * A local variable may always be put in a register.
 245          * Other items must be used at least twice.
 246          */
 247
 248         int nruses = Lnrelems(item->it_usage);
 249         assert (nruses > 0); /* otherwise it would not be an item! */
 250         return nruses > 1 || item->it_type == LOCALVAR;
 251 }
 252
 253
 254 STATIC cleantimeset(s)
 255         lset s;
 256 {
 257         register Lindex i;
 258         register time_p t;
 259
 260         for (i = Lfirst(s); i != (Lindex) 0; i = Lnext(i,s)) {
 261                 t = (time_p) Lelem(i);
 262                 oldtime(t);
 263         }
 264         Ldeleteset(s);
 265 }
 266
 267
 268
 269 STATIC item_p cat_items(items)
 270         item_p items[];
 271 {
 272         /* Make one item list out of an array of itemlists.
 273          * Remove items that are used only once.
 274          */
 275
 276         register item_p it;
 277         item_p *ip,head,next;
 278         int t;
 279
 280
 281         ip = &head;
 282         for (t = 0; t < NRITEMTYPES;t++) {
 283                 for ( it = items[t]; it != (item_p) 0; it = next) {
 284                         next = it->it_next;
 285                         if (!it->it_desirable || !useful_item(it)) {
 286                                 cleantimeset(it->it_usage);
 287                                 olditem(it);
 288                         } else {
 289                                 *ip = it;
 290                                 ip = &it->it_next;
 291                         }
 292                 }
 293         }
 294         *ip = (item_p) 0;
 295         return head;
 296 }
 297
 298
 299
 300
 301 STATIC clean_interval(list)
 302         interv_p list;
 303 {
 304         register interv_p x,next;
 305
 306         for (x = list; x != (interv_p) 0; x = next) {
 307                 next = x->i_next;
 308                 oldinterval(x);
 309         }
 310 }
 311
 312
 313
 314 STATIC clean_allocs(list)
 315         alloc_p list;
 316 {
 317         register alloc_p x,next;
 318
 319         for (x = list; x != (alloc_p) 0; x = next) {
 320                 next = x->al_next;
 321                 clean_interval(x->al_timespan);
 322                 Cdeleteset(x->al_rivals);
 323                 Ldeleteset(x->al_inits);
 324                 clean_interval(x->al_busy);
 325                 clean_allocs(x->al_mates);
 326                 oldalloc(x);
 327         }
 328 }
 329
 330
 331
 332 STATIC cleanitems(list)
 333         item_p list;
 334 {
 335         register item_p x,next;
 336
 337         for (x = list; x != (item_p) 0; x = next ) {
 338                 next = x->it_next;
 339                 cleantimeset(x->it_usage);
 340                 olditem(x);
 341         }
 342 }
 343
 344
 345 ra_initialize()
 346 {
 347         init_replacements(ps,ws);
 348 }
 349
 350
 351 ra_optimize(p)
 352         proc_p p;
 353 {
 354         item_p itemlist;
 355         alloc_p alloclist,packed,unpacked;
 356         offset locls;
 357         bool time_opt = (time_space_ratio == 100);
 358
 359         if (IS_ENTERED_WITH_GTO(p)) return;
 360         ra_extproc(p);
 361         loop_blocks(p);
 362         alloc_id =0;
 363         locls = p->p_localbytes;
 364         build_itemlist(p,items,&nrinstrs);
 365         instrmap = (line_p *) newmap(nrinstrs-1); /* map starts counting at 0 */
 366         make_instrmap(p,instrmap);
 367         build_lifetimes(items);
 368         /* print_items(items,p); */
 369         /* statistics(items); */
 370         itemlist = cat_items(items); /* make one list */
 371         alloclist = build_alloc_list(p,Lnrelems(p->p_loops),
 372                                      itemlist);
 373         build_rivals_graph(alloclist);
 374         compute_profits(alloclist,time_opt);
 375         /* print_allocs(alloclist); */
 376         pack(alloclist,time_opt,&packed,&unpacked,p);
 377         stat_regusage(packed);
 378         xform_proc(p,packed,nrinstrs,instrmap);
 379         /* print_allocs(packed); */
 380         p->p_localbytes = locls;
 381         /* don't really allocate dummy local variables! */
 382         rem_locals(p,packed);
 383         rem_formals(p,packed);
 384         /* remove storage for real locals that
 385          *are always put in register .
 386          */
 387         clean_allocs(unpacked);
 388         clean_allocs(packed);
 389         cleanitems(itemlist);
 390         oldmap(instrmap,nrinstrs-1);
 391         ra_cleanproc(p);
 392 }
 393
 394
 395
 396 main(argc,argv)
 397         int argc;
 398         char *argv[];
 399 {
 400         go(argc,argv,ra_initialize,ra_optimize,ra_machinit,no_action);
 401         exit(0);
 402 }
 403
 404
 405 /***************************************************************************/
 406 /***************************************************************************/
 407 /***************************************************************************/
 408
 409 /* debugging stuff */
 410
 411
 412
 413 char *str_types[] = {
 414         "local variable",
 415         "addr. of local",
 416         "addr. of external",
 417         "addr. of procedure",
 418         "constant",
 419         "double constant"
 420 };
 421
 422 char *str_regtypes[] = {
 423         "any",
 424         "loop",
 425         "pointer",
 426         "float"
 427 };
 428
 429
 430 print_items(items,p)
 431         item_p items[];
 432         proc_p p;
 433 {
 434         int t;
 435         item_p item;
 436         interv_p iv;
 437
 438         fprintf(stderr, "BEGIN PROCEDURE %d\n",p->p_id);
 439         for (t = 0; t < NRITEMTYPES;t++) {
 440                 for (item = items[t]; item != (item_p) 0;item = item->it_next) {
 441                         fprintf(stderr, "\nitemtype = %s\n",str_types[t]);
 442                         if (t == GLOBL_ADDR) {
 443                                 fprintf(stderr, "id of external = %d\n",
 444                                         item->i_t.it_obj->o_id);
 445                         } else {
 446                                 fprintf(stderr, "offset = %ld\n",
 447                                         item->i_t.it_off);
 448                         }
 449                         fprintf(stderr, "regtype = %s\n",str_regtypes[item->it_regtype]);
 450                         fprintf(stderr, "size = %d\n",item->it_size);
 451                         fprintf(stderr, "#usages = %d\n", Lnrelems(item->it_usage));
 452                         fprintf(stderr, "lifetime = {");
 453                         for (iv = item->it_lives; iv != (interv_p) 0;
 454                              iv = iv->i_next) {
 455                                 fprintf(stderr, "(%d,%d) ",iv->i_start,iv->i_stop);
 456                         }
 457                         fprintf(stderr, "} \n");
 458                 }
 459         }
 460         fprintf(stderr, "END PROCEDURE %d\n\n",p->p_id);
 461 }
 462
 463
 464 print_allocs(list)
 465         alloc_p list;
 466 {
 467         alloc_p al,m;
 468         item_p item;
 469         short t;
 470         interv_p iv;
 471
 472         fprintf(stderr,"BEGIN ALLOCLIST of proc %d\n",curproc->p_id);
 473         for (m = list ; m != (alloc_p) 0; m = m->al_next) {
 474                 for (al = m; al != (alloc_p) 0; al = al->al_mates) {
 475                         item = al->al_item;
 476                         t = item->it_type;
 477                         fprintf(stderr,"\nitem: [type = %s, ",str_types[t]);
 478                         switch(t) {
 479                         case GLOBL_ADDR:
 480                                 fprintf(stderr,"id = %d]\n", item->i_t.it_obj->o_id);
 481                                 break;
 482                         case PROC_ADDR:
 483                                 fprintf(stderr,"id = %d]\n", item->i_t.it_proc->p_id);
 484                                 break;
 485                         default:
 486                                 fprintf(stderr,"offset = %ld]\n", item->i_t.it_off);
 487                         }
 488                         fprintf(stderr,"#usages(static) = %d\n",al->al_susecount);
 489                         fprintf(stderr,"#usages(dyn) = %d\n",al->al_dusecount);
 490                         fprintf(stderr,"#inits = %d\n",Lnrelems(al->al_inits));
 491                         fprintf(stderr,"isloop = %d\n",al->al_isloop);
 492                         fprintf(stderr,"timespan = {");
 493                         for (iv = al->al_timespan; iv != (interv_p) 0;
 494                              iv = iv->i_next) {
 495                                 fprintf(stderr,"(%d,%d) ",iv->i_start,iv->i_stop);
 496                         }
 497                         fprintf(stderr,"} \n");
 498                         fprintf(stderr,"busy = {");
 499                         for (iv = al->al_busy; iv != (interv_p) 0;
 500                              iv = iv->i_next) {
 501                                 fprintf(stderr,"(%d,%d) ",iv->i_start,iv->i_stop);
 502                         }
 503                         fprintf(stderr,"} \n");
 504                         fprintf(stderr,"profits = %d\n",al->al_profits);
 505                         fprintf(stderr,"dummy local = %ld\n",al->al_dummy);
 506                         fprintf(stderr,"regnr = %d\n",al->al_regnr);
 507                 }
 508         }
 509 }
 510
 511
 512 short regs_needed[4];
 513 stat_regusage(list)
 514         alloc_p list;
 515 {
 516         int i;
 517         alloc_p x;
 518
 519         for (i = 0; i < 4; i++) {
 520                 regs_needed[i] = 0;
 521         }
 522         for (x = list; x != (alloc_p) 0; x = x->al_next) {
 523                 regs_needed[x->al_regtype]++;
 524         }
 525         /* fprintf(stderr, "data regs:%d\n",regs_needed[reg_any]); */
 526         /* fprintf(stderr, "address regs:%d\n",regs_needed[reg_pointer]); */
 527 }
 528
 529
 530
 531 int cnt_regtypes[reg_float+1];
 532
 533 statistics(items)
 534         item_p items[];
 535 {
 536         register item_p item,next;
 537         int t,r;
 538         int cnt;
 539
 540         fprintf(stderr, "\nSTATISTICS\n");
 541         for (r = 0; r <= reg_float; r++) cnt_regtypes[r] = 0;
 542         for (t = 0; t < NRITEMTYPES;t++) {
 543                 cnt = 0;
 544                 for (item = items[t]; item != (item_p) 0;item = next) {
 545                         if (useful_item(item)) {
 546                                 cnt++;
 547                                 cnt_regtypes[item->it_regtype]++;
 548                         }
 549                         next = item->it_next;
 550                 }
 551                 fprintf(stderr, "#%s = %d\n",str_types[t],cnt);
 552         }
 553         for (r = 0; r <= reg_float; r++) {
 554                 fprintf(stderr, "#%s = %d\n",str_regtypes[r],cnt_regtypes[r]);
 555         }
 556 }