util/ego/share/types.h

   1 /* $Id: types.h,v 1.8 1994/06/24 10:31:04 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 /* I N T E R N A L   D A T A S T R U C T U R E S   O F   E G O  */
   7
   8
   9 /* This file contains the definitions of the global data types.
  10  */
  11
  12
  13 /* TEMPORARY: */
  14 #define LONGOFF
  15
  16
  17 #define IDL 256 /* maximum identifier length */
  18 #define DYNAMIC 1
  19 #define NARGBYTES 14
  20 #define BMASK 0377
  21
  22 typedef struct argbytes argb_t;
  23 typedef char    byte;
  24 typedef byte    bool;
  25 typedef long    offset;
  26 typedef short   obj_id;
  27 typedef short   proc_id;
  28 typedef short   dblock_id;
  29 typedef short   block_id;
  30 typedef short   loop_id;
  31 typedef short   lab_id;
  32
  33
  34 typedef struct dblock     *dblock_p;
  35 typedef struct obj        *obj_p;
  36 typedef struct proc       *proc_p;
  37 typedef struct loop       *loop_p;
  38 typedef struct change     *change_p;
  39 typedef struct use        *use_p;
  40 typedef struct bblock     *bblock_p;
  41 typedef struct line       *line_p;
  42 typedef struct arg        *arg_p;
  43 typedef struct argbytes   *argb_p;
  44 typedef struct elemholder *elem_p;
  45 typedef struct elemholder *lset;
  46 typedef struct bitvector  *cset;
  47 typedef elem_p Lindex;
  48 typedef short  Cindex;
  49 typedef char   *Lelem_t;
  50 typedef short  Celem_t;
  51
  52 typedef union pext_t *pext_p;
  53 typedef union bext_t *bext_p;
  54 typedef union lpext_t *lpext_p;
  55
  56
  57 typedef struct call     *call_p;
  58 typedef struct formal   *formal_p;
  59
  60 /* Used-Definition Analysis */
  61 typedef struct local *local_p;
  62
  63 typedef struct cond_tab *cond_p;
  64
  65 #define TRUE    1
  66 #define FALSE   0
  67
  68 /* DATABLOCKS */
  69
  70 /* A datablock is a block of global data, declared by means of
  71  * a hol, bss, con or rom pseudo. The declaration may be in a file
  72  * that is inaccessible to EGO, in which case the pseudo is unknown.
  73  * Successive rom or con pseudos that are garanteed to be in the
  74  * same fragment (according to the EM definition) share the
  75  * same fragment number.
  76  */
  77
  78 #define DHOL     0
  79 #define DBSS     1
  80 #define DROM     2
  81 #define DCON     3
  82 #define DUNKNOWN 4
  83
  84
  85 /* The following constants are used by the debugging tools: */
  86 #define D_FIRST DHOL
  87 #define D_LAST  DUNKNOWN
  88
  89
  90 struct dblock {
  91         dblock_id d_id;         /* unique integer                       */
  92         byte     d_pseudo;      /* one of DHOL,DBSS,DROM,DCON,DUNKNOWN  */
  93         offset   d_size;        /* # bytes, -1 if unknown               */
  94         obj_p    d_objlist;     /* list of objects of the data block    */
  95         byte     d_flags1;      /* see below                            */
  96         byte     d_flags2;      /* free to be used by phases            */
  97         arg_p    d_values;      /* values, in case of ROM               */
  98         short    d_fragmnr;     /* fragment number                      */
  99         dblock_p d_next;        /* link to next block                   */
 100 };
 101
 102
 103 #define DF_EXTERNAL     01      /* Is name visible outside its module? */
 104
 105 /* OBJECTS */
 106
 107 /* An object is a row of successive bytes in one datablock
 108  * that are considered to be a whole. E.g. scalar variables,
 109  * arrays, I/O buffers etc. are objects.
 110  */
 111
 112 struct obj {
 113         offset   o_off;         /* offset within the block              */
 114         offset   o_size;        /* size of the object, 0 if not known   */
 115         obj_id   o_id;          /* unique integer                       */
 116         dblock_p o_dblock;      /* backlink to data block               */
 117         short    o_globnr;      /* global variable number               */
 118         obj_p    o_next;        /* link                                 */
 119 };
 120
 121
 122 /* PROCEDURES */
 123
 124 struct proc {
 125         proc_id  p_id;          /* unique integer                       */
 126         short    p_nrlabels;    /* #instruction labels in the proc      */
 127         offset   p_localbytes;  /* #bytes for locals                    */
 128         offset   p_nrformals;   /* #bytes for formals                   */
 129         byte     p_flags1;      /* see below                            */
 130         byte     p_flags2;      /* free to be used by phases            */
 131         bblock_p p_start;       /* pointer to first basic block         */
 132         cset     p_calling;     /* set of all procs called by this one  */
 133         lset     p_loops;       /* information about loops              */
 134         change_p p_change;      /* variables changed by this proc       */
 135         use_p    p_use;         /* variables used by this proc          */
 136         pext_p   p_extend;      /* pointer to any further information   */
 137         proc_p   p_next;        /* link                                 */
 138 };
 139
 140
 141 union pext_t {
 142    struct pext_il {
 143         call_p   p_cals;        /* candidate calls for in line expansion */
 144         short    p_size;        /* length of proc (EM-instrs or bytes)  */
 145         formal_p p_formals;     /* description of formals               */
 146         short    p_nrcalled;    /* # times proc is called (varying)     */
 147         long     p_ccaddr;      /* address of calcnt info on disk       */
 148         long     p_laddr;       /* address in EM-text file on disk      */
 149         short    p_orglabels;   /* original #labels before substitution */
 150         offset   p_orglocals;   /* original #bytes for locals           */
 151    } px_il;
 152 } ;
 153
 154 #define PF_EXTERNAL     01      /* proc is externally visible */
 155 #define PF_BODYSEEN     02      /* body of proc is available as EM text */
 156 #define PF_CALUNKNOWN   04      /* proc calls an unavailable procedure */
 157 #define PF_ENVIRON      010     /* proc does a lxa or lxl */
 158 #define PF_LPI          020     /* proc may be called indirect */
 159 #define PF_CALINLOOP    040     /* proc ever called in a loop? (transitively) */
 160 #define PF_GTO          0100    /* proc may be entered via GTO instruction */
 161
 162 #define CALLED_IN_LOOP(p)       p->p_flags1 |= PF_CALINLOOP
 163 #define IS_CALLED_IN_LOOP(p)    (p->p_flags1 & PF_CALINLOOP)
 164 #define IS_ENTERED_WITH_GTO(p)  (p->p_flags1 & PF_GTO)
 165 #define ENTERED_WITH_GTO(p)     p->p_flags1 |= PF_GTO
 166 #define BODY_KNOWN(p)           (p->p_flags1 & (byte) PF_BODYSEEN)
 167
 168
 169 /* LOOPS */
 170
 171  struct loop {
 172         loop_id  lp_id;         /* unique integer                       */
 173         short    lp_level;      /* nesting level, 0=outermost loop,
 174                                  * 1=loop within loop etc.              */
 175         bblock_p lp_entry;      /* unique entry block of loop           */
 176         bblock_p lp_end;        /* tail of back edge of natural loop    */
 177         lpext_p  lp_extend;     /* pointer to any further information   */
 178 };
 179
 180
 181
 182 union lpext_t {
 183    struct lpext_cf {
 184         lset     lpx_blocks;
 185         short    lpx_count;
 186         bool     lpx_messy;
 187    } lpx_cf;
 188    struct lpext_sr {
 189         lset     lpx_blocks;    /* basic blocks  constituting the loop  */
 190         bblock_p lpx_header;    /* header block, 0 if no one allocated yet */
 191         bool     lpx_done;      /* TRUE if we've processed this loop    */
 192         line_p   lpx_instr;     /* current last instruction in header block*/
 193    } lpx_sr;
 194    struct lpext_ra {
 195         lset     lpx_blocks;    /* basic blocks  constituting the loop  */
 196         bblock_p lpx_header;    /* header block, 0 if no one allocated yet */
 197    } lpx_ra;
 198 } ;
 199
 200 /* CHANGED/USED VARIABLES INFORMATION */
 201
 202
 203 struct change {
 204         cset     c_ext;         /* external variables changed           */
 205         short    c_flags;       /* see below                            */
 206 };
 207
 208 struct use {
 209         short    u_flags;       /* see below                            */
 210 };
 211
 212
 213 #define CF_INDIR 01
 214 #define UF_INDIR 01
 215
 216 #define CHANGE_INDIR(p)         (p->p_change->c_flags & CF_INDIR)
 217
 218 /* SETS */
 219
 220
 221 /* There are 2 set representations:
 222  *   - long    (lset), which is essentially a list
 223  *   - compact (cset), which is essentially a bitvector
 224  */
 225
 226
 227  struct elemholder {
 228         char       *e_elem;     /* pointer to the element               */
 229         elem_p     e_next;      /* link                                 */
 230 };
 231
 232 struct bitvector {
 233         short   v_size;         /* # significant bits                   */
 234         int     v_bits[DYNAMIC];/* a row of bits                        */
 235 };
 236
 237
 238
 239 /* BASIC BLOCKS */
 240
 241
 242 /* Note that the b_succ and b_pred fields constitute the
 243  * Control Flow Graph
 244  */
 245
 246
 247  struct bblock {
 248         block_id b_id;          /* unique integer                       */
 249         line_p   b_start;       /* pointer to first instruction         */
 250         lset     b_succ;        /* set of successor blocks              */
 251         lset     b_pred;        /* set of predecessor blocks            */
 252         bblock_p b_idom;        /* immediate dominator                  */
 253         lset     b_loops;       /* set of loops it is in                */
 254         short    b_flags;       /* see below                            */
 255         bext_p   b_extend;      /* pointer to any further information   */
 256         bblock_p b_next;        /* link to textually next block         */
 257 };
 258
 259
 260 union bext_t {
 261    struct bext_cf {
 262         short    bx_semi;       /* dfs number of semi-dominator         */
 263         bblock_p bx_parent;     /* parent in dfs spanning tree          */
 264         lset     bx_bucket;     /* set of vertices whose sdom is b      */
 265         bblock_p bx_ancestor;   /* ancestor of b in forest,             */
 266         bblock_p bx_label;      /* used by link/eval                    */
 267    } bx_cf;
 268    struct bext_ud {
 269         cset     bx_gen;        /* definition generated in b            */
 270         cset     bx_kill;       /* defs. outside b killed by b          */
 271         cset     bx_in;         /* defs. reaching beginning of b        */
 272         cset     bx_out;        /* defs. reaching end of b              */
 273         cset     bx_cgen;       /* generated copies                     */
 274         cset     bx_ckill;      /* killed copies                        */
 275         cset     bx_cin;        /* copies reaching begin of b           */
 276         cset     bx_cout;       /* copies reaching end of b             */
 277         cset     bx_chgvars;    /* variables changed by b               */
 278    } bx_ud;
 279    struct bext_lv {
 280         cset     bx_use;        /* variables used before being defined  */
 281         cset     bx_def;        /* variables defined before being used  */
 282         cset     bx_lin;        /* variables live at entry of b         */
 283         cset     bx_lout;       /* variables live at exit of b          */
 284    } bx_lv;
 285    struct bext_ra {
 286         short    bx_begin;      /* number of first instruction of block */
 287         short    bx_end;        /* number of last  instruction of block */
 288    } bx_ra;
 289 } ;
 290
 291
 292 #define BF_STRONG       01
 293 #define BF_FIRM         02
 294
 295 #define IS_STRONG(b)    (b->b_flags&BF_STRONG)
 296 #define IS_FIRM(b)      (b->b_flags&BF_FIRM)
 297
 298
 299 /* EM INSTRUCTIONS */
 300
 301 /* Kinds of operand types (l_optype field) */
 302
 303 #define OPNO            0
 304 #define OPSHORT         1
 305 #define OPOFFSET        2
 306 #define OPINSTRLAB      3
 307 #define OPOBJECT        4
 308 #define OPPROC          5
 309 #define OPLIST          6
 310
 311
 312 /* The following constants are used by the debugging tools: */
 313 #define OP_FIRST OPNO
 314 #define OP_LAST OPLIST
 315
 316 #define LDATA   0
 317 #define LTEXT   01
 318
 319 struct line {
 320         line_p   l_next;        /* link                                 */
 321         byte     l_instr;       /* instruction                          */
 322         byte     l_optype;      /* kind of operand, used as tag         */
 323         line_p   l_prev;        /* backlink to previous instruction     */
 324         union {
 325                 short   la_short;       /* short:          LOC 5        */
 326                 offset  la_offset;      /* offset:         LDC 20       */
 327                 lab_id  la_instrlab;    /* label:          BRA *10      */
 328                 obj_p   la_obj;         /* object:         LOE X+2      */
 329                 proc_p  la_proc;        /* proc:           CAL F3       */
 330                 arg_p   la_arg;         /* arguments:      HOL 10,0,0   */
 331         } l_a;
 332 };
 333
 334
 335 /* ARGUMENTS */
 336
 337
 338 /* String representation of a constant, partitioned into
 339  * pieces of NARGBYTES bytes.
 340  */
 341
 342 #define ARGOFF          0
 343 #define ARGINSTRLAB     1
 344 #define ARGOBJECT       2
 345 #define ARGPROC         3
 346 #define ARGSTRING       4
 347 #define ARGICN          5
 348 #define ARGUCN          6
 349 #define ARGFCN          7
 350 #define ARGCEND         8
 351
 352
 353 struct argbytes {
 354         argb_p   ab_next;
 355         short    ab_index;
 356         char     ab_contents[NARGBYTES];
 357 };
 358
 359
 360 struct arg {
 361         arg_p    a_next;        /* link                                 */
 362         short    a_type;        /* kind of argument                     */
 363         union {
 364                 offset  a_offset;       /* offset                       */
 365                 lab_id  a_instrlab;     /* instruction label            */
 366                 proc_p  a_proc;         /* procedure                    */
 367                 obj_p   a_obj;          /* object                       */
 368                 argb_t  a_string;       /* string                       */
 369                 struct {                /* int/unsigned/float constant  */
 370                         short   ac_length;      /* size in bytes        */
 371                         argb_t  ac_con;         /* its string repres.   */
 372                 } a_con;
 373         } a_a;
 374 };
 375
 376
 377
 378 /* Macros to increase readability: */
 379
 380 #define INSTR(lnp)      (lnp->l_instr & BMASK)
 381 #define TYPE(lnp)       lnp->l_optype
 382 #define PREV(lnp)       lnp->l_prev
 383 #define SHORT(lnp)      lnp->l_a.la_short
 384 #define OFFSET(lnp)     lnp->l_a.la_offset
 385 #define INSTRLAB(lnp)   lnp->l_a.la_instrlab
 386 #define OBJ(lnp)        lnp->l_a.la_obj
 387 #define PROC(lnp)       lnp->l_a.la_proc
 388 #define ARG(lnp)        lnp->l_a.la_arg
 389
 390
 391 /* Data structures for Use-Definition and Live-Dead Analysis */
 392
 393 struct local {
 394         offset  lc_off;         /* offset of local in stackframe        */
 395         short   lc_size;        /* size of local in bytes               */
 396         short   lc_flags;       /* see below                            */
 397         offset  lc_score;       /* score in register message, if regvar */
 398         local_p lc_next;        /* link, only used when building the list */
 399 };
 400
 401 /* values of lc_flags */
 402
 403 #define LCF_BAD         01
 404 /* Set when no ud-info for this local is maintained, e.g. when it is
 405  * overlapped by another local.
 406  */
 407 #define LCF_REG         02      /* register variable */
 408 #define LCF_LIVE        04      /* use by live-dead message generation */
 409
 410
 411 struct cond_tab {
 412         short   mc_cond;        /* Denotes a condition e.g. FITBYTE */
 413         short   mc_tval;        /* value for time optimization  */
 414         short   mc_sval;        /* value for space optimization */
 415         short mc_dummy; /* allignment */
 416 };
 417
 418 /* conditions: */
 419
 420 #define DEFAULT         0
 421 #define FITBYTE         1
 422 #define IN_0_63         2
 423 #define IN_0_8          3
 424