util/ego/ra/ra_items.c

   1 /* $Id: ra_items.c,v 1.7 1994/06/24 10:27:44 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 _ I T E M S . 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/aux.h"
  21 #include "../share/alloc.h"
  22 #include "ra.h"
  23 #include "ra_aux.h"
  24 #include "ra_items.h"
  25
  26
  27 #include "itemtab.h"
  28 /* Maps EM mnemonics onto item types, e.g. op_lol -> LOCALVAR, op_ldc->DCONST,
  29  * generated from em_mmen.h and itemtab.src files.
  30  */
  31
  32 #define SMALL_CONSTANT(c)       (c >= 0 && c <= 8)
  33 /* prevent small constants from being put in a register */
  34
  35
  36 clean_tab(items)
  37         item_p items[];
  38 {
  39         int t;
  40
  41         for (t = 0; t < NRITEMTYPES;t++) {
  42                 items[t] = (item_p) 0;
  43         }
  44 }
  45
  46
  47
  48
  49 short item_type(l)
  50         line_p l;
  51 {
  52         int instr = INSTR(l);
  53         int t;
  54
  55         if (instr < sp_fmnem || instr > sp_lmnem) return NO_ITEM;
  56         t =  itemtab[instr - sp_fmnem].id_type;
  57         if (t == CONST && SMALL_CONSTANT(off_set(l))) return NO_ITEM;
  58         return t;
  59 }
  60
  61
  62
  63 bool is_item(l)
  64         line_p l;
  65 {
  66         return item_type(l) != NO_ITEM;
  67 }
  68
  69
  70 item_p item_of(off,items)
  71         offset off;
  72         item_p items[];
  73 {
  74         register item_p x;
  75
  76         for (x = items[LOCALVAR]; x != (item_p) 0; x = x->it_next) {
  77                 if (off == x->i_t.it_off) {
  78                         if (!x->it_desirable) break;
  79                                         /* don't put this item in reg */
  80                         return x;
  81                 }
  82         }
  83         return (item_p) 0;
  84 }
  85
  86
  87
  88 fill_item(item,l)
  89         item_p item;
  90         line_p l;
  91 {
  92         item->it_type = item_type(l);
  93         item->it_desirable = TRUE;
  94         switch(item->it_type) {
  95                 case GLOBL_ADDR:
  96                         item->i_t.it_obj = OBJ(l);
  97                         break;
  98                 case PROC_ADDR:
  99                         item->i_t.it_proc = PROC(l);
 100                         break;
 101                 default:
 102                         item->i_t.it_off = off_set(l);
 103         }
 104 }
 105
 106
 107
 108 STATIC bool desirable(l)
 109         line_p l;
 110 {
 111         /* See if it is really desirable to put the item of line l
 112          * in a register. We do not put an item in a register if it
 113          * is used as 'address of array descriptor' of an array
 114          * instruction.
 115         */
 116
 117         if (l->l_next != (line_p) 0) {
 118                 switch(INSTR(l->l_next)) {
 119                         case op_aar:
 120                         case op_lar:
 121                         case op_sar:
 122                                 return FALSE;
 123                 }
 124         }
 125         return TRUE;
 126 }
 127
 128
 129
 130 STATIC int cmp_items(a,b)
 131         item_p a,b;
 132 {
 133         /* This routine defines the <, = and > relations between items,
 134          * used to sort them for fast lookup.
 135          */
 136
 137         offset n1,n2;
 138
 139         switch(a->it_type) {
 140                 case GLOBL_ADDR:
 141                         assert(b->it_type == GLOBL_ADDR);
 142                         n1 = (offset) a->i_t.it_obj->o_id;
 143                         n2 = (offset) b->i_t.it_obj->o_id;
 144                         break;
 145                 case PROC_ADDR:
 146                         assert(b->it_type == PROC_ADDR);
 147                         n1 = (offset) a->i_t.it_proc->p_id;
 148                         n2 = (offset) b->i_t.it_proc->p_id;
 149                         break;
 150                 default:
 151                         n1 = a->i_t.it_off;
 152                         n2 = b->i_t.it_off;
 153         }
 154         return (n1 == n2 ? 0 : (n1 > n2 ? 1 : -1));
 155 }
 156
 157
 158
 159 bool same_item(a,b)
 160         item_p a,b;
 161 {
 162         return cmp_items(a,b) == 0;
 163 }
 164
 165
 166 STATIC bool lt_item(a,b)
 167         item_p a,b;
 168 {
 169         return cmp_items(a,b) == -1;
 170 }
 171
 172
 173
 174 /* build_itemlist()
 175  *
 176  * Build a list of all items used in the current procedure. An item
 177  * is anything that can be put in a register (a local variable, a constant,
 178  * the address of a local or global variable).
 179  * For each type of item we use a sorted list containing all items of
 180  * that type found so far.
 181  * A local variable is only considered to be an item if there is a
 182  * register message for it (indicating it is never accessed indirectly).
 183  * For each item, we keep track of all places where it is used
 184  * (either fetched or stored into). The usage of a local variable is also
 185  * considered to be a usage of its address.
 186  */
 187
 188
 189
 190 static item_p items[NRITEMTYPES];  /* items[i] points to the list of type i */
 191
 192
 193
 194 STATIC short reg_type(item)
 195         item_p item;
 196 {
 197         /* See which type of register the item should best be assigned to */
 198
 199         switch(item->it_type) {
 200                 case LOCALVAR:
 201                         return regv_type(item->i_t.it_off);
 202                         /* use type mentioned in reg. message for local */
 203                 case LOCAL_ADDR:
 204                 case GLOBL_ADDR:
 205                 case PROC_ADDR:
 206                         return reg_pointer;
 207                 case CONST:
 208                 case DCONST:
 209                         return reg_any;
 210                 default: assert(FALSE);
 211         }
 212         /* NOTREACHED */
 213 }
 214
 215
 216
 217 STATIC short item_size(item)
 218         item_p item;
 219 {
 220         /* Determine the size of the item (in bytes) */
 221
 222         switch(item->it_type) {
 223                 case LOCALVAR:
 224                         return regv_size(item->i_t.it_off);
 225                         /* use size mentioned in reg. message for local */
 226                 case LOCAL_ADDR:
 227                 case GLOBL_ADDR:
 228                 case PROC_ADDR:
 229                         return ps; /* pointer size */
 230                 case CONST:
 231                         return ws; /* word size */
 232                 case DCONST:
 233                         return 2 * ws; /* 2 * word size */
 234                 default: assert(FALSE);
 235         }
 236         /* NOTREACHED */
 237 }
 238
 239
 240
 241 STATIC init_item(a,b)
 242         item_p a,b;
 243 {
 244         a->it_type = b->it_type;
 245         switch(a->it_type) {
 246                 case GLOBL_ADDR:
 247                         a->i_t.it_obj = b->i_t.it_obj;
 248                         break;
 249                 case PROC_ADDR:
 250                         a->i_t.it_proc = b->i_t.it_proc;
 251                         break;
 252                 default:
 253                         a->i_t.it_off = b->i_t.it_off;
 254         }
 255         a->it_usage = Lempty_set();
 256         a->it_regtype = reg_type(b);
 257         a->it_size = item_size(b);
 258         a->it_desirable = b->it_desirable;
 259 }
 260
 261
 262
 263 STATIC add_item(item,t,items)
 264         item_p item;
 265         time_p t;
 266         item_p items[];
 267 {
 268         /* See if there was already a list element for item. In any
 269          * case record the fact that item is used at 't'.
 270          */
 271
 272         register item_p x, *q;
 273
 274         q = &items[item->it_type]; /* each type has its own list */
 275         for (x = *q; x != (item_p) 0; x = *q) {
 276                 if (same_item(x,item)) {
 277                         /* found */
 278                         if (!item->it_desirable) {
 279                                 x->it_desirable = FALSE;
 280                         }
 281                         Ladd(t,&x->it_usage);
 282                         return; /* done */
 283                 }
 284                 if (lt_item(item,x)) break;
 285                 q = &x->it_next;
 286         }
 287         /* not found, allocate new item; q points to it_next field of
 288          * the item after which the new item should be put.
 289          */
 290         x = newitem();
 291         x->it_next = *q;
 292         *q = x;
 293         init_item(x,item);
 294         Ladd(t,&x->it_usage);
 295 }
 296
 297
 298
 299 STATIC add_usage(l,b,items)
 300         line_p l;
 301         bblock_p b;
 302         item_p items[];
 303 {
 304         /* An item is used at line l. Add it to the list of items.
 305          * A local variable is only considered to be an item, if
 306          * there is a register message for it; else its address
 307          * is also considered to be an item.
 308          */
 309
 310         struct item thisitem;
 311
 312         fill_item(&thisitem,l); /* fill in some fields */
 313         if (!desirable(l)) {
 314                 thisitem.it_desirable = FALSE; /* don't put item in reg. */
 315         }
 316         if (thisitem.it_type == LOCALVAR && !is_regvar(thisitem.i_t.it_off)) {
 317                 /* Use address of local instead of local itself */
 318                 thisitem.it_type = LOCAL_ADDR;
 319                 thisitem.it_regtype = reg_pointer;
 320         }
 321         add_item(&thisitem,cons_time(l,b),items);
 322 }
 323
 324
 325
 326 build_itemlist(p,items,nrinstr_out)
 327         proc_p p;
 328         item_p items[];
 329         int    *nrinstr_out;
 330 {
 331         /* Make a list of all items used in procedure p.
 332          * An item is anything that can be put in a register,
 333          * such as a local variable, a constant etc.
 334          * As a side effect, determine the number of instructions of p.
 335          */
 336
 337         register line_p l;
 338         register bblock_p b;
 339         register cnt= 0;
 340
 341         clean_tab(items);
 342         for (b = p->p_start; b != (bblock_p) 0; b = b->b_next) {
 343                 for (l = b->b_start; l != (line_p) 0; l = l->l_next) {
 344                         if (is_item(l)) {
 345                                 add_usage(l,b,items);
 346                         }
 347                         cnt++;
 348                 }
 349         }
 350         *nrinstr_out = cnt;
 351 }