util/ego/ra/ra_xform.c

   1 /* $Id: ra_xform.c,v 1.7 1995/11/08 11:08:09 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 _ X F O R M . C
   9  */
  10
  11 #include <em_mnem.h>
  12 #include <em_spec.h>
  13 #include <em_pseu.h>
  14 #include <em_mes.h>
  15 #include <em_ego.h>
  16 #include <em_reg.h>
  17 #include "../share/types.h"
  18 #include "../share/debug.h"
  19 #include "../share/def.h"
  20 #include "../share/global.h"
  21 #include "../share/lset.h"
  22 #include "../share/aux.h"
  23 #include "../share/alloc.h"
  24 #include "ra.h"
  25 #include "ra_interv.h"
  26 #include "ra_xform.h"
  27 #include "ra_items.h"
  28
  29
  30 /* The replacement table is used to transform instructions that reference
  31  * items other than local variables (i.e. the address of a local or global
  32  * variable or a single/double constant; the transformation of an instruction
  33  * that references a local variable is very simple).
  34  * The generated code depends on the word and pointer size of the target
  35  * machine.
  36  */
  37
  38
  39 struct repl {
  40         short   r_instr;        /* instruction          */
  41         short   r_op;           /* operand              */
  42 };
  43
  44 /* REGNR,NO and STOP should not equal the wordsize or pointer size
  45  * of any machine.
  46  */
  47 #define REGNR   -3
  48 #define NO      -2
  49 #define STOP    -1
  50 #define PS      0
  51 #define PS2     1
  52 #define WS      2
  53 #define WS2     3
  54
  55 #define LOAD_POINTER    op_nop
  56 #define BLANK           {0, STOP}
  57
  58 #define NRREPLACEMENTS  13
  59 #define REPL_LENGTH     3
  60
  61 struct repl repl_tab[NRREPLACEMENTS][REPL_LENGTH] = {
  62         /* 0 */ {{op_lil, REGNR},       BLANK,          BLANK},
  63         /* 1 */ {{LOAD_POINTER,REGNR},  {op_loi,PS},    {op_loi,WS}},
  64         /* 2 */ {{LOAD_POINTER,REGNR},  BLANK,          BLANK},
  65         /* 3 */ {{LOAD_POINTER,REGNR},  {op_loi,WS2},   BLANK},
  66         /* 4 */ {{op_sil,REGNR},        BLANK,          BLANK},
  67         /* 5 */ {{LOAD_POINTER,REGNR},  {op_loi,PS},    {op_sti,WS}},
  68         /* 6 */ {{LOAD_POINTER,REGNR},  {op_sti,WS2},   BLANK},
  69         /* 7 */ {{op_lil,REGNR},        {op_inc,NO},    {op_sil,REGNR}},
  70         /* 8 */ {{op_lil,REGNR},        {op_dec,NO},    {op_sil,REGNR}},
  71         /* 9 */ {{op_zer,WS},           {op_sil,REGNR}, BLANK},
  72         /*10 */ {{op_lol,REGNR},        BLANK,          BLANK},
  73         /*11 */ {{op_ldl,REGNR},        BLANK,          BLANK},
  74         /*12 */ {{LOAD_POINTER,REGNR},  {op_cai,NO},    BLANK},
  75 };
  76
  77
  78
  79
  80 init_replacements(psize,wsize)
  81         short psize,wsize;
  82 {
  83         /* The replacement code to be generated depends on the
  84          * wordsize and pointer size of the target machine.
  85          * The replacement table is initialized with a description
  86          * of which sizes to use. This routine inserts the real sizes.
  87          * It also inserts the actual EM instruction to be used
  88          * as a 'Load pointer' instruction.
  89          */
  90
  91         register int i,j;
  92         short load_pointer;
  93         struct repl *r;
  94
  95         assert (psize == wsize || psize == 2*wsize);
  96         load_pointer = (psize == wsize ? op_lol : op_ldl);
  97         for (i = 0; i < NRREPLACEMENTS; i++) {
  98                 for (j = 0; j < REPL_LENGTH; j++) {
  99                         r = &repl_tab[i][j];
 100                         if (r->r_op == STOP) break;
 101                         if (r->r_instr == LOAD_POINTER) {
 102                                 r->r_instr = load_pointer;
 103                         }
 104                         switch (r->r_op) {
 105                                 /* initially r_op describes how to compute
 106                                  * the real operand of the instruction. */
 107                                 case PS2:
 108                                         r->r_op = 2*psize;
 109                                         break;
 110                                 case PS:
 111                                         r->r_op = psize;
 112                                         break;
 113                                 case WS2:
 114                                         r->r_op = 2*wsize;
 115                                         break;
 116                                 case WS:
 117                                         r->r_op = wsize;
 118                                         break;
 119                                 case NO:
 120                                 case REGNR:     /* use offset of dummy local,
 121                                                  * will be filled in later.
 122                                                  */
 123                                         break;
 124                                 default: assert(FALSE);
 125                         }
 126                 }
 127         }
 128 }
 129
 130
 131
 132 STATIC int repl_index(l)
 133         line_p l;
 134 {
 135         return itemtab[INSTR(l) - sp_fmnem].id_replindex;
 136 }
 137
 138
 139
 140 STATIC bool is_current(alloc,t)
 141         alloc_p alloc;
 142         short t;
 143 {
 144         /* Is time t part of alloc's timespan? */
 145
 146         return contains(t,alloc->al_timespan);
 147 }
 148
 149
 150 STATIC match_item(item,l)
 151         item_p item;
 152         line_p l;
 153 {
 154         /* See if the item used by l is the same one as 'item' */
 155         struct item thisitem;
 156
 157         fill_item(&thisitem,l);
 158         if (item->it_type == LOCAL_ADDR && thisitem.it_type == LOCALVAR) {
 159                 /* The usage of a local variable is also considered to
 160                  * be the usage of the address of that variable.
 161                  */
 162                 thisitem.it_type = LOCAL_ADDR;
 163         }
 164         return item->it_type == thisitem.it_type && same_item(item,&thisitem);
 165 }
 166
 167
 168
 169 STATIC alloc_p find_alloc(alloclist,l,t)
 170         alloc_p alloclist;
 171         line_p l;
 172         short t;
 173 {
 174         /* See if any of the allocations of the list applies to instruction
 175          * l at time t.
 176          */
 177
 178         register alloc_p alloc,m;
 179
 180         for (alloc = alloclist; alloc != (alloc_p) 0; alloc = alloc->al_next) {
 181                 for (m = alloc; m != (alloc_p) 0; m = m->al_mates) {
 182                         if (is_current(m,t) && match_item(m->al_item,l)) {
 183                                 return m;
 184                         }
 185                 }
 186         }
 187         return (alloc_p) 0;
 188 }
 189
 190
 191 STATIC replace_line(l,b,list)
 192         line_p l,list;
 193         bblock_p b;
 194 {
 195         if (b->b_start == l) {
 196                 b->b_start = list;
 197         } else {
 198                 PREV(l)->l_next = list;
 199         }
 200         PREV(list) = PREV(l);
 201         while (list->l_next != (line_p) 0) {
 202                 list = list->l_next;
 203         }
 204         list->l_next = l->l_next;
 205         if (l->l_next != (line_p) 0) {
 206                 PREV(l->l_next) = list;
 207         }
 208         oldline(l);
 209 }
 210
 211
 212 STATIC line_p repl_code(lnp,regnr)
 213         line_p lnp;
 214         offset  regnr;
 215 {
 216         line_p head,*q,l,prev = (line_p) 0;
 217         int i,index;
 218         struct repl *r;
 219
 220         q = &head;
 221         index = repl_index(lnp);
 222         for (i = 0; i < REPL_LENGTH; i++) {
 223                 r = &repl_tab[index][i];
 224                 if (r->r_op == STOP) break;  /* replacement < REPL_LENGTH */
 225                 switch(r->r_op) {
 226                         case REGNR:
 227                                 l = int_line(regnr);
 228                                 break;
 229                         case NO:
 230                                 l = newline(OPNO);
 231                                 break;
 232                         default:
 233                                 l = newline(OPSHORT);
 234                                 SHORT(l) = r->r_op;
 235                                 break;
 236                 }
 237                 *q = l;
 238                 l->l_instr = r->r_instr;
 239                 PREV(l) = prev;
 240                 prev = l;
 241                 q = &l->l_next;
 242         }
 243         return head;
 244 }
 245
 246
 247
 248 STATIC apply_alloc(b,l,alloc)
 249         bblock_p b;
 250         line_p l;
 251         alloc_p alloc;
 252 {
 253         /* 'l' is an EM instruction using an item that will be put in
 254          * a register. Generate new code that uses the register instead
 255          * of the item.
 256          * If the item is a local variable the new code is the same as
 257          * the old code, except for the fact that the offset of the
 258          * local is changed (it now uses the dummy local that will be
 259          * put in a register by the code generator).
 260          * If the item is a constant, the new code is a LOL or LDL.
 261          * If the item is the address of a local or global variable, things
 262          * get more complicated. The new code depends on the instruction
 263          * that uses the item (i.e. l). The new code, which may consist of
 264          * several instructions, is obtained by consulting a replacement
 265          * table.
 266          */
 267
 268         line_p newcode;
 269
 270         if (alloc->al_item->it_type == LOCALVAR) {
 271                 if ((short) (alloc->al_dummy) == alloc->al_dummy) {
 272                         TYPE(l) = OPSHORT;
 273                         SHORT(l) = alloc->al_dummy;
 274                 }
 275                 else {
 276                         TYPE(l) = OPOFFSET;
 277                         OFFSET(l) = alloc->al_dummy;
 278                 }
 279         } else {
 280                 newcode = repl_code(l,alloc->al_dummy);
 281                 replace_line(l,b,newcode);
 282         }
 283 }
 284
 285
 286
 287 STATIC int loaditem_tab[NRITEMTYPES][2] =
 288 {       /*              WS              2 * WS */
 289         /*LOCALVAR*/    op_lol,         op_ldl,
 290         /*LOCAL_ADDR*/  op_lal,         op_lal,
 291         /*GLOBL_ADDR*/  op_lae,         op_lae,
 292         /*PROC_ADDR*/   op_lpi,         op_lpi,
 293         /*CONST*/       op_loc,         op_nop,
 294         /*DCONST*/      op_nop,         op_ldc
 295 };
 296
 297
 298 STATIC line_p load_item(item)
 299         item_p item;
 300 {
 301         /* Generate an EM instruction that loads the item on the stack */
 302
 303         line_p l;
 304
 305         switch (item->it_type) {
 306                 case GLOBL_ADDR:
 307                         l = newline(OPOBJECT);
 308                         OBJ(l) = item->i_t.it_obj;
 309                         break;
 310                 case PROC_ADDR:
 311                         l = newline(OPPROC);
 312                         PROC(l) = item->i_t.it_proc;
 313                         break;
 314                 default:
 315                         l = int_line(item->i_t.it_off);
 316         }
 317         l->l_instr = loaditem_tab[item->it_type][item->it_size == ws ? 0 : 1];
 318         assert(l->l_instr != op_nop);
 319         return l;
 320 }
 321
 322
 323 STATIC line_p store_local(size,off)
 324         short size;
 325         offset off;
 326 {
 327         line_p l = int_line(off);
 328
 329         l->l_instr = (size == ws ? op_stl : op_sdl);
 330         return l;
 331 }
 332
 333
 334
 335 STATIC line_p init_place(b)
 336         bblock_p b;
 337 {
 338
 339         register line_p l,prev;
 340
 341         prev = (line_p) 0;
 342         for (l = b->b_start; l != (line_p) 0; l = l->l_next) {
 343                 switch(INSTR(l)) {
 344                         case ps_mes:
 345                         case ps_pro:
 346                         case op_lab:
 347                                 break;
 348                         default:
 349                                 return prev;
 350                 }
 351                 prev =l;
 352         }
 353         return prev;
 354 }
 355
 356
 357
 358 STATIC append_code(l1,l2,b)
 359         line_p l1,l2;
 360         bblock_p b;
 361 {
 362         /* Append instruction l1 and l2 at begin of block b */
 363
 364         line_p l;
 365
 366         DLINK(l1,l2);
 367         l = init_place(b);
 368         if (l == (line_p) 0) {
 369                 l2->l_next = b->b_start;
 370                 b->b_start = l1;
 371                 PREV(l1) = (line_p) 0;
 372         } else {
 373                 l2->l_next = l->l_next;
 374                 DLINK(l,l1);
 375         }
 376         if (l2->l_next != (line_p) 0) {
 377                 PREV(l2->l_next) = l2;
 378         }
 379 }
 380
 381
 382
 383 STATIC emit_init_code(list)
 384         alloc_p list;
 385 {
 386         /* Emit initialization code for all packed allocations.
 387          * This code looks like "dummy_local := item", e.g.
 388          * "LOC 25 ; STL -10" in EM terminology.
 389          */
 390
 391         register alloc_p alloc,m;
 392         Lindex bi;
 393         bblock_p b;
 394
 395         for (alloc = list; alloc != (alloc_p) 0; alloc = alloc->al_next) {
 396                 for (m = alloc; m != (alloc_p) 0; m = m->al_mates) {
 397                         for (bi = Lfirst(m->al_inits); bi != (Lindex) 0;
 398                                                   bi = Lnext(bi,m->al_inits)) {
 399                                 /* "inits" contains all initialization points */
 400                                 b = (bblock_p) Lelem(bi);
 401                                 append_code(load_item(m->al_item),
 402                                             store_local(m->al_item->it_size,
 403                                                         m->al_dummy),
 404                                             b);
 405                         }
 406                 }
 407         }
 408 }
 409
 410
 411
 412 STATIC emit_mesregs(p,alloclist)
 413         proc_p  p;
 414         alloc_p alloclist;
 415 {
 416         line_p l,m,x;
 417         alloc_p alloc;
 418
 419
 420         l = p->p_start->b_start;
 421         x = l->l_next;
 422         for (alloc = alloclist; alloc != (alloc_p) 0; alloc = alloc->al_next) {
 423                 m = reg_mes(alloc->al_dummy,alloc->al_item->it_size,
 424                         alloc->al_regtype,INFINITE);
 425                 DLINK(l,m);
 426                 l = m;
 427         }
 428         if (x != (line_p) 0) DLINK(l,x);
 429 }
 430
 431 #define is_mesreg(l)    (INSTR(l) == ps_mes && aoff(ARG(l),0) == ms_reg)
 432
 433
 434
 435 rem_mes(p)
 436         proc_p p;
 437 {
 438         register bblock_p b;
 439         register line_p l,next;
 440         offset m;
 441
 442         for (b = p->p_start; b != (bblock_p) 0; b = b->b_next) {
 443                 for (l = b->b_start; l != (line_p) 0; l = next) {
 444                         next = l->l_next;
 445                         if (INSTR(l) == ps_mes
 446                             && aoff(ARG(l),0) == ms_ego
 447                             && ((m = aoff(ARG(l),1)) == ego_live
 448                                 || m == ego_dead)) {
 449                                 /* remove live/dead messages */
 450                                 rm_line(l,b);
 451                         }
 452                 }
 453         }
 454 }
 455
 456
 457
 458 xform_proc(p,alloclist,nrinstrs,instrmap)
 459         proc_p p;
 460         alloc_p alloclist;
 461         short nrinstrs;
 462         line_p instrmap[];
 463 {
 464         /* Transform every instruction of procedure p that uses an item
 465          * at a point where the item is kept in a register.
 466          */
 467
 468         register short now = 0;
 469         register line_p l,next;
 470         register bblock_p b;
 471         alloc_p alloc;
 472
 473         for (b = p->p_start; b != (bblock_p) 0; b = b->b_next) {
 474                 for (l = b->b_start; l != (line_p) 0; l = next) {
 475                         next = l->l_next;
 476                         if (is_mesreg(l) && ARG(l)->a_next != (arg_p) 0 &&
 477                                 aoff(ARG(l),4) != INFINITE) {
 478                                 /* All register messages for local variables
 479                                  * that were not assigned a register get
 480                                  * their 'count' fields* set to 0.
 481                                  */
 482                                 ARG(l)->a_next->a_next->a_next
 483                                         ->a_next->a_a.a_offset = 0;
 484                         }
 485                         if (is_item(l) &&
 486                             (alloc = find_alloc(alloclist,l,now))
 487                                              != (alloc_p) 0 ) {
 488                                 apply_alloc(b,l,alloc);
 489                         }
 490                         now++;
 491                 }
 492         }
 493         emit_init_code(alloclist);
 494         emit_mesregs(p,alloclist);
 495         rem_mes(p);
 496 }
 497
 498
 499
 500
 501 bool always_in_reg(off,allocs,size_out)
 502         offset off;
 503         alloc_p allocs;
 504         short *size_out;
 505 {
 506         /* See if the local variable with the given offset is stored
 507          * in a register during its entire lifetime. As a side effect,
 508          * return the size of the local.
 509          */
 510
 511         alloc_p alloc,m;
 512         item_p item;
 513
 514         for (alloc = allocs; alloc != (alloc_p) 0; alloc = alloc->al_next) {
 515                 for (m = alloc; m != (alloc_p) 0; m = m->al_mates) {
 516                         item = m->al_item;
 517                         if (m->al_iswholeproc &&
 518                             item->it_type == LOCALVAR &&
 519                             item->i_t.it_off == off) {
 520                                 *size_out = item->it_size;
 521                                 return TRUE;
 522                         }
 523                 }
 524         }
 525         return FALSE;
 526 }
 527
 528
 529 rem_locals(p,allocs)
 530         proc_p p;
 531         alloc_p allocs;
 532 {
 533         /* Try to decrease the number of locals of procedure p, by
 534          * looking at which locals are always stored in a register.
 535          */
 536
 537         offset nrlocals = p->p_localbytes;
 538         short size;
 539
 540         while (nrlocals > 0) {
 541                 /* A local can only be removed if all locals with
 542                  * higher offsets are removed too.
 543                  */
 544                 if (always_in_reg(-nrlocals,allocs,&size)) {
 545                         OUTVERBOSE("local %d removed from proc %d\n",
 546                                 nrlocals,p->p_id);
 547                         nrlocals -= size;
 548                 } else {
 549                         break;
 550                 }
 551         }
 552         p->p_localbytes = nrlocals;
 553 }
 554 rem_formals(p,allocs)
 555         proc_p p;
 556         alloc_p allocs;
 557 {
 558         /* Try to decrease the number of formals of procedure p, by
 559          * looking at which formals are always stored in a register.
 560          */
 561
 562         offset nrformals = p->p_nrformals;
 563         offset off = 0;
 564         short size;
 565
 566         if (nrformals == UNKNOWN_SIZE) return;
 567         while (off < nrformals) {
 568                 if (always_in_reg(off,allocs,&size)) {
 569                         OUTVERBOSE("formal %d removed from proc %d\n",
 570                                 off,p->p_id);
 571                         off += size;
 572                 } else {
 573                         break;
 574                 }
 575         }
 576         if (nrformals == off) {
 577                 OUTVERBOSE("all formals of procedure %d removed\n",p->p_id,0);
 578                 p->p_nrformals = 0;
 579         }
 580 }