util/ego/ra/ra.h

   1 /* $Id: ra.h,v 1.7 1994/06/24 10:27:24 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 #define INFINITE        10000
  12 #define NRREGTYPES      (reg_float+1)
  13
  14 extern int nrinstrs;  /* number of instructions of current procedure */
  15 extern line_p *instrmap;
  16 /* Dynamic array: instrmap[i] points to i'th instruction */
  17
  18 extern cond_p alocaltab[NRREGTYPES][NRREGTYPES],
  19         alocaddrtab[NRREGTYPES][NRREGTYPES], aconsttab,
  20         adconsttab,aglobaltab,aproctab;
  21 extern cond_p olocaltab[NRREGTYPES],olocaddrtab[NRREGTYPES],
  22         oconsttab,odconsttab,oglobaltab,oproctab;
  23 extern cond_p regsav_cost;
  24
  25 /* Register Allocation */
  26 typedef struct item *item_p;
  27 typedef struct allocation *alloc_p;
  28 typedef struct interval *interv_p;
  29 typedef struct time *time_p;
  30
  31
  32
  33
  34 extern short regs_available[];  /* contains #registers of every type */
  35 extern short use_any_as_pointer;/* indicates whether general registers
  36                                    can be used as pointers
  37                                 */
  38
  39
  40 /* A thing that can be put in a register is called an "item". The are several
  41  * types of items: a local variable, the address of a local variable,
  42  * the address of a global variable, the address of a procedure,
  43  * a word-size constant and a doubleword- size constant.
  44  */
  45
  46 #define LOCALVAR        0
  47 #define LOCAL_ADDR      1
  48 #define GLOBL_ADDR      2
  49 #define PROC_ADDR       3
  50 #define CONST           4
  51 #define DCONST          5
  52
  53 #define NO_ITEM         6
  54 #define NRITEMTYPES     6
  55
  56 struct item {
  57         item_p    it_next;      /* link to next item is list            */
  58         short     it_type;      /* its type; see above                  */
  59         short     it_regtype;   /* preferred type of register           */
  60         short     it_size;      /* its size (in bytes)                  */
  61         short     it_lastlive;  /* temporary, used to build livetime    */
  62         lset      it_usage;     /* all points in text where item is used*/
  63         interv_p  it_lives;     /* intervals during which item is live  */
  64         bool      it_desirable; /* should this item be put in reg.?     */
  65         union {
  66                 obj_p   it_obj;         /* for GLOBL_ADDR               */
  67                 proc_p  it_proc;        /* for PROC_ADDR                */
  68                 offset  it_off;         /* for others                   */
  69         } i_t;
  70 };
  71
  72
  73 /* A 'point in time' is defined by a (line,basic block) pair */
  74
  75 struct time {
  76         line_p    t_line;       /* point in EM text                     */
  77         bblock_p  t_bblock;     /* its basic block                      */
  78 };
  79
  80
  81 struct interval {
  82         short    i_start;       /* number of first instruction          */
  83         short    i_stop;        /* number of last instruction           */
  84         interv_p i_next;
  85 };
  86
  87
  88 /* An item may be put in a register for the duration of a whole procedure
  89  * or part of a procedure (e.g. a loop). So a possible "allocation" looks
  90  * like: put item X in a register during the timespan T (which is a subset
  91  * of the timespan of the entire procedure). The packing process deals
  92  * with allocations, rather than items. One item may be part of several
  93  * possible allocations.
  94  */
  95
  96 struct allocation {
  97         item_p    al_item;      /* the item to be put in a register       */
  98         short     al_id;        /* unique identifying number              */
  99         short     al_regtype;   /* the register type to be used           */
 100         interv_p  al_timespan;  /* timespan during which item is in reg.  */
 101         short     al_profits;   /* gains of putting item in register      */
 102         cset      al_rivals;    /* set of allocations competing with it   */
 103         short     al_susecount; /* #usages during timespan (statically)   */
 104         short     al_dusecount; /* #usages (dynamically, estimate)        */
 105         lset      al_inits;     /* points where reg. must be initialized  */
 106         interv_p  al_busy;      /* used to compute rivals                 */
 107         short     al_regnr;     /* register nr.,if it is granted a reg.   */
 108         offset    al_dummy;     /* dummy local variable,if granted a reg  */
 109         alloc_p   al_mates;     /* link to allocations packed in same reg */
 110         alloc_p   al_wholeproc; /* alloc. for whole proc as timespan      */
 111         short     al_cntrivals; /* # unpacked rivals ; used for cost estim. */
 112         bool      al_isloop;    /* true if timespan consists of loop      */
 113         bool      al_iswholeproc;/*true if timespan consists of whole proc*/
 114         alloc_p   al_next;      /* link to next one in a list             */
 115 };
 116
 117 extern short alloc_id;  /* last al_id used for current procedure */
 118
 119 #define LP_BLOCKS       lp_extend->lpx_ra.lpx_blocks
 120 #define LP_HEADER       lp_extend->lpx_ra.lpx_header
 121 #define B_BEGIN         b_extend->bx_ra.bx_begin
 122 #define B_END           b_extend->bx_ra.bx_end
 123
 124 #define DLINK(l1,l2)    l1->l_next=l2; l2->l_prev=l1
 125
 126 struct item_descr {
 127         int     id_type;
 128         int     id_replindex;
 129 } ;
 130
 131 extern struct item_descr itemtab[];
 132
 133 #define newalloc()      (alloc_p) newstruct(allocation)
 134 #define  oldalloc(a)    oldstruct(allocation,a)
 135 #define newitem()       (item_p) newstruct(item)
 136 #define olditem(i)      oldstruct(item,i)
 137 #define newtime()       (time_p) newstruct(time)
 138 #define oldtime(t)      oldstruct(time,t)
 139 #define newinterval()   (interv_p) newstruct(interval)
 140 #define oldinterval(i)  oldstruct(interval,i)