compilers/pcc/pcc-1.0.0/mip/pass2.h

   1 /*      $Id: pass2.h,v 1.128 2011/01/11 12:48:23 ragge Exp $    */
   2 /*
   3  * Copyright(C) Caldera International Inc. 2001-2002. All rights reserved.
   4  *
   5  * Redistribution and use in source and binary forms, with or without
   6  * modification, are permitted provided that the following conditions
   7  * are met:
   8  *
   9  * Redistributions of source code and documentation must retain the above
  10  * copyright notice, this list of conditions and the following disclaimer.
  11  * Redistributions in binary form must reproduce the above copyright
  12  * notice, this list of conditionsand the following disclaimer in the
  13  * documentation and/or other materials provided with the distribution.
  14  * All advertising materials mentioning features or use of this software
  15  * must display the following acknowledgement:
  16  *      This product includes software developed or owned by Caldera
  17  *      International, Inc.
  18  * Neither the name of Caldera International, Inc. nor the names of other
  19  * contributors may be used to endorse or promote products derived from
  20  * this software without specific prior written permission.
  21  *
  22  * USE OF THE SOFTWARE PROVIDED FOR UNDER THIS LICENSE BY CALDERA
  23  * INTERNATIONAL, INC. AND CONTRIBUTORS ``AS IS'' AND ANY EXPRESS OR
  24  * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
  25  * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
  26  * DISCLAIMED.  IN NO EVENT SHALL CALDERA INTERNATIONAL, INC. BE LIABLE
  27  * FOR ANY DIRECT, INDIRECT INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  28  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  29  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  30  * HOWEVER CAUSED AND ON ANY THEORY OFLIABILITY, WHETHER IN CONTRACT,
  31  * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING
  32  * IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
  33  * POSSIBILITY OF SUCH DAMAGE.
  34  */
  35 #include <sys/types.h>
  36
  37 #ifndef MKEXT
  38 #include "external.h"
  39 #else
  40 typedef unsigned int bittype; /* XXX - for basicblock */
  41 #define BIT2BYTE(a)     (((a) + 31) / 32)
  42 #endif
  43 #include "manifest.h"
  44
  45 /* cookies, used as arguments to codgen */
  46 #define FOREFF  01              /* compute for effects only */
  47 #define INAREG  02              /* compute into a register */
  48 #define INBREG  04              /* compute into a register */
  49 #define INCREG  010             /* compute into a register */
  50 #define INDREG  020             /* compute into a register */
  51 #define INREGS  (INAREG|INBREG|INCREG|INDREG)
  52 #define FORCC   040             /* compute for condition codes only */
  53 #define QUIET   0100            /* tell geninsn() to not complain if fail */
  54 #define INTEMP  010000          /* compute into a temporary location */
  55 #define FORREW  040000          /* search the table for a rewrite rule */
  56 #define INEREG  0x10000         /* compute into a register, > 16 bits */
  57 #define INFREG  0x20000         /* compute into a register, > 16 bits */
  58 #define INGREG  0x40000         /* compute into a register, > 16 bits */
  59
  60 /*
  61  * OP descriptors,
  62  * the ASG operator may be used on some of these
  63  */
  64 #define OPSIMP  010000          /* +, -, &, |, ^ */
  65 #define OPCOMM  010002          /* +, &, |, ^ */
  66 #define OPMUL   010004          /* *, / */
  67 #define OPDIV   010006          /* /, % */
  68 #define OPUNARY 010010          /* unary ops */
  69 #define OPLEAF  010012          /* leaves */
  70 #define OPANY   010014          /* any op... */
  71 #define OPLOG   010016          /* logical ops */
  72 #define OPFLOAT 010020          /* +, -, *, or / (for floats) */
  73 #define OPSHFT  010022          /* <<, >> */
  74 #define OPLTYPE 010024          /* leaf type nodes (e.g, NAME, ICON, etc.) */
  75
  76 /* shapes */
  77 #define SANY    01              /* same as FOREFF */
  78 #define SAREG   02              /* same as INAREG */
  79 #define SBREG   04              /* same as INBREG */
  80 #define SCREG   010             /* same as INCREG */
  81 #define SDREG   020             /* same as INDREG */
  82 #define SCC     040             /* same as FORCC */
  83 #define SNAME   0100
  84 #define SCON    0200
  85 #define SFLD    0400
  86 #define SOREG   01000
  87 #define STARNM  02000
  88 #define STARREG 04000
  89 #define SWADD   040000
  90 #define SPECIAL 0100000
  91 #define SZERO   SPECIAL
  92 #define SONE    (SPECIAL|1)
  93 #define SMONE   (SPECIAL|2)
  94 #define SCCON   (SPECIAL|3)     /* -256 <= constant < 256 */
  95 #define SSCON   (SPECIAL|4)     /* -32768 <= constant < 32768 */
  96 #define SSOREG  (SPECIAL|5)     /* non-indexed OREG */
  97 #define MAXSPECIAL      (SPECIAL|5)
  98 #define SEREG   0x10000         /* same as INEREG */
  99 #define SFREG   0x20000         /* same as INFREG */
 100 #define SGREG   0x40000         /* same as INGREG */
 101
 102 /* These are used in rstatus[] in conjunction with SxREG */
 103 #define TEMPREG 01000
 104 #define PERMREG 02000
 105
 106 /* tshape() return values */
 107 #define SRNOPE  0               /* Cannot match any shape */
 108 #define SRDIR   1               /* Direct match */
 109 #define SROREG  2               /* Can convert into OREG */
 110 #define SRREG   3               /* Must put into REG */
 111
 112 /* find*() return values */
 113 #define FRETRY  -2
 114 #define FFAIL   -1
 115
 116 /* INTEMP is carefully not conflicting with shapes */
 117
 118 /* types */
 119 #define TCHAR           01      /* char */
 120 #define TSHORT          02      /* short */
 121 #define TINT            04      /* int */
 122 #define TLONG           010     /* long */
 123 #define TFLOAT          020     /* float */
 124 #define TDOUBLE         040     /* double */
 125 #define TPOINT          0100    /* pointer to something */
 126 #define TUCHAR          0200    /* unsigned char */
 127 #define TUSHORT         0400    /* unsigned short */
 128 #define TUNSIGNED       01000   /* unsigned int */
 129 #define TULONG          02000   /* unsigned long */
 130 #define TPTRTO          04000   /* pointer to one of the above */
 131 #define TANY            010000  /* matches anything within reason */
 132 #define TSTRUCT         020000  /* structure or union */
 133 #define TLONGLONG       040000  /* long long */
 134 #define TULONGLONG      0100000 /* unsigned long long */
 135 #define TLDOUBLE        0200000 /* long double; exceeds 16 bit */
 136 #define TFTN            0400000 /* function pointer; exceeds 16 bit */
 137
 138 /* reclamation cookies */
 139 #define RNULL           0       /* clobber result */
 140 #define RLEFT           01
 141 #define RRIGHT          02
 142 #define RESC1           04
 143 #define RESC2           010
 144 #define RESC3           020
 145 #define RDEST           040
 146 #define RESCC           04000
 147 #define RNOP            010000  /* DANGER: can cause loops.. */
 148
 149 /* needs */
 150 #define NASL            0x0001  /* may share left register */
 151 #define NASR            0x0002  /* may share right register */
 152 #define NAREG           0x0004
 153 #define NACOUNT         0x000c
 154 #define NBSL            0x0010
 155 #define NBSR            0x0020
 156 #define NBREG           0x0040
 157 #define NBCOUNT         0x00c0
 158 #define NCSL            0x0100
 159 #define NCSR            0x0200
 160 #define NCREG           0x0400
 161 #define NCCOUNT         0x0c00
 162 #define NTEMP           0x1000
 163 #define NTMASK          0x3000
 164 #define NSPECIAL        0x4000  /* need special register treatment */
 165 #define REWRITE         0x8000
 166 #define NDSL            0x00010000      /* Above 16 bit */
 167 #define NDSR            0x00020000      /* Above 16 bit */
 168 #define NDREG           0x00040000      /* Above 16 bit */
 169 #define NDCOUNT         0x000c0000
 170 #define NESL            0x00100000      /* Above 16 bit */
 171 #define NESR            0x00200000      /* Above 16 bit */
 172 #define NEREG           0x00400000      /* Above 16 bit */
 173 #define NECOUNT         0x00c00000
 174 #define NFSL            0x01000000      /* Above 16 bit */
 175 #define NFSR            0x02000000      /* Above 16 bit */
 176 #define NFREG           0x04000000      /* Above 16 bit */
 177 #define NFCOUNT         0x0c000000
 178 #define NGSL            0x10000000      /* Above 16 bit */
 179 #define NGSR            0x20000000      /* Above 16 bit */
 180 #undef  NGREG   /* XXX - linux exposes NGREG to public */
 181 #define NGREG           0x40000000      /* Above 16 bit */
 182 #define NGCOUNT         0xc0000000
 183
 184 /* special treatment */
 185 #define NLEFT           (0001)  /* left leg register (moveadd) */
 186 #define NOLEFT          (0002)  /* avoid regs for left (addedge) */
 187 #define NRIGHT          (0004)  /* right leg register */
 188 #define NORIGHT         (0010)  /* avoid reg for right */
 189 #define NEVER           (0020)  /* registers trashed (addalledges) */
 190 #define NRES            (0040)  /* result register (moveadd) */
 191 #define NMOVTO          (0100)  /* move between classes */
 192
 193
 194 #define MUSTDO          010000  /* force register requirements */
 195 #define NOPREF          020000  /* no preference for register assignment */
 196
 197 #define isreg(p)        (p->n_op == REG || p->n_op == TEMP)
 198
 199 extern  int fregs;
 200
 201 /* code tables */
 202 extern  struct optab {
 203         int     op;
 204         int     visit;
 205         int     lshape;
 206         int     ltype;
 207         int     rshape;
 208         int     rtype;
 209         int     needs;
 210         int     rewrite;
 211         char    *cstring;
 212 } table[];
 213
 214 /* Special needs for register allocations */
 215 struct rspecial {
 216         int op, num;
 217 #if 0
 218         int left;       /* left leg register */
 219         int noleft;     /* avoid regs for left */
 220         int right;      /* right leg register */
 221         int noright;    /* avoid right leg register */
 222         int *rmask;     /* array of destroyed registers */
 223         int res;        /* Result ends up here */
 224 //      void (*rew)(struct optab *, NODE *);    /* special rewrite */
 225 #endif
 226 };
 227
 228 struct p2env;
 229 extern  NODE resc[];
 230 extern  int p2autooff, p2maxautooff;
 231
 232 extern  NODE
 233         *talloc(void),
 234         *eread(void),
 235         *mklnode(int, CONSZ, int, TWORD),
 236         *mkbinode(int, NODE *, NODE *, TWORD),
 237         *mkunode(int, NODE *, int, TWORD),
 238         *getlr(NODE *p, int);
 239
 240 void eoftn(struct interpass_prolog *);
 241 void prologue(struct interpass_prolog *);
 242 void e2print(NODE *p, int down, int *a, int *b);
 243 void myoptim(struct interpass *);
 244 void cbgen(int op, int label);
 245 int match(NODE *p, int cookie);
 246 int acceptable(struct optab *);
 247 int special(NODE *, int);
 248 int setasg(NODE *, int);
 249 int setuni(NODE *, int);
 250 int sucomp(NODE *);
 251 int nsucomp(NODE *);
 252 int setorder(NODE *);
 253 int geninsn(NODE *, int cookie);
 254 void adrput(FILE *, NODE *);
 255 void comperr(char *str, ...);
 256 void genregs(NODE *p);
 257 void ngenregs(struct p2env *);
 258 NODE *store(NODE *);
 259 struct interpass *ipnode(NODE *);
 260 void deflab(int);
 261 void rmove(int, int, TWORD);
 262 int rspecial(struct optab *, int);
 263 struct rspecial *nspecial(struct optab *q);
 264 void printip(struct interpass *pole);
 265 int findops(NODE *p, int);
 266 int findasg(NODE *p, int);
 267 int finduni(NODE *p, int);
 268 int findumul(NODE *p, int);
 269 int findleaf(NODE *p, int);
 270 int relops(NODE *p);
 271 #ifdef FINDMOPS
 272 int findmops(NODE *p, int);
 273 int treecmp(NODE *p1, NODE *p2);
 274 #endif
 275 void offstar(NODE *p, int shape);
 276 int gclass(TWORD);
 277 void lastcall(NODE *);
 278 void myreader(struct interpass *pole);
 279 int oregok(NODE *p, int sharp);
 280 void myormake(NODE *);
 281 int *livecall(NODE *);
 282 void prtreg(FILE *, NODE *);
 283 char *prcook(int);
 284 int myxasm(struct interpass *ip, NODE *p);
 285 int xasmcode(char *s);
 286 int freetemp(int k);
 287 int rewfld(NODE *p);
 288 void canon(NODE *);
 289 void mycanon(NODE *);
 290 void oreg2(NODE *p, void *);
 291 int shumul(NODE *p, int);
 292 NODE *deluseless(NODE *p);
 293 int getlab2(void);
 294 int tshape(NODE *, int);
 295 void conput(FILE *, NODE *);
 296 int shtemp(NODE *p);
 297 int ttype(TWORD t, int tword);
 298 void expand(NODE *, int, char *);
 299 void hopcode(int, int);
 300 void adrcon(CONSZ);
 301 void zzzcode(NODE *, int);
 302 void insput(NODE *);
 303 void upput(NODE *, int);
 304 int tlen(NODE *p);
 305 int setbin(NODE *);
 306 int notoff(TWORD, int, CONSZ, char *);
 307 int fldexpand(NODE *, int, char **);
 308 void p2tree(NODE *p);
 309 int flshape(NODE *p);
 310
 311 extern  char *rnames[];
 312 extern  int rstatus[];
 313 extern  int roverlap[MAXREGS][MAXREGS];
 314
 315 extern int classmask(int), tclassmask(int);
 316 extern void cmapinit(void);
 317 extern int aliasmap(int adjclass, int regnum);
 318 extern int regK[];
 319 #define CLASSA  1
 320 #define CLASSB  2
 321 #define CLASSC  3
 322 #define CLASSD  4
 323 #define CLASSE  5
 324 #define CLASSF  6
 325 #define CLASSG  7
 326
 327 /* used when parsing xasm codes */
 328 #define XASMVAL(x)      ((x) & 0377)            /* get val from codeword */
 329 #define XASMVAL1(x)     (((x) >> 16) & 0377)    /* get val from codeword */
 330 #define XASMVAL2(x)     (((x) >> 24) & 0377)    /* get val from codeword */
 331 #define XASMASG         0x100   /* = */
 332 #define XASMCONSTR      0x200   /* & */
 333 #define XASMINOUT       0x400   /* + */
 334 #define XASMALL         (XASMASG|XASMCONSTR|XASMINOUT)
 335 #define XASMISINP(cw)   (((cw) & XASMASG) == 0)         /* input operand */
 336 #define XASMISOUT(cw)   ((cw) & (XASMASG|XASMINOUT))    /* output operand */
 337
 338 /* routines to handle double indirection */
 339 #ifdef R2REGS
 340 void makeor2(NODE *p, NODE *q, int, int);
 341 int base(NODE *);
 342 int offset(NODE *p, int);
 343 #endif
 344
 345 extern  int lineno;
 346 extern  int fldshf, fldsz;
 347 extern  int lflag, x2debug, udebug, e2debug, odebug;
 348 extern  int rdebug, t2debug, s2debug, b2debug, c2debug;
 349 extern  int g2debug;
 350 extern  int kflag;
 351 #ifdef FORT
 352 extern  int Oflag;
 353 #endif
 354
 355 #ifndef callchk
 356 #define callchk(x) allchk()
 357 #endif
 358
 359 #ifndef PUTCHAR
 360 #define PUTCHAR(x) putchar(x)
 361 #endif
 362
 363 extern  int dope[];     /* a vector containing operator information */
 364 extern  char *opst[];   /* a vector containing names for ops */
 365
 366 #ifdef PCC_DEBUG
 367
 368 static inline int
 369 optype(int o)
 370 {
 371         if (o >= MAXOP+1)
 372                 cerror("optype");
 373         return (dope[o]&TYFLG);
 374 }
 375
 376 static inline int
 377 asgop(int o)
 378 {
 379         if (o >= MAXOP+1)
 380                 cerror("asgop");
 381         return (dope[o]&ASGFLG);
 382 }
 383
 384 static inline int
 385 logop(int o)
 386 {
 387         if (o >= MAXOP+1)
 388                 cerror("logop");
 389         return (dope[o]&LOGFLG);
 390 }
 391
 392 static inline int
 393 callop(int o)
 394 {
 395         if (o >= MAXOP+1)
 396                 cerror("callop");
 397         return (dope[o]&CALLFLG);
 398 }
 399
 400 #else
 401
 402 #define optype(o)       (dope[o]&TYFLG)
 403 #define asgop(o)        (dope[o]&ASGFLG)
 404 #define logop(o)        (dope[o]&LOGFLG)
 405 #define callop(o)       (dope[o]&CALLFLG)
 406
 407 #endif
 408
 409         /* macros for doing double indexing */
 410 #define R2PACK(x,y,z)   (0200*((x)+1)+y+040000*z)
 411 #define R2UPK1(x)       ((((x)>>7)-1)&0177)
 412 #define R2UPK2(x)       ((x)&0177)
 413 #define R2UPK3(x)       (x>>14)
 414 #define R2TEST(x)       ((x)>=0200)
 415
 416 /*
 417  * Layout of findops() return value:
 418  *      bit 0 whether left shall go into a register.
 419  *      bit 1 whether right shall go into a register.
 420  *      bit 2 entry is only used for side effects.
 421  *      bit 3 if condition codes are used.
 422  *
 423  * These values should be synced with FOREFF/FORCC.
 424  */
 425 #define LREG            001
 426 #define RREG            002
 427 #define RVEFF           004
 428 #define RVCC            010
 429 #define DORIGHT         020
 430 #define SCLASS(v,x)     ((v) |= ((x) << 5))
 431 #define TCLASS(x)       (((x) >> 5) & 7)
 432 #define TBSH            8
 433 #define TBLIDX(idx)     ((idx) >> TBSH)
 434 #define MKIDX(tbl,mod)  (((tbl) << TBSH) | (mod))
 435
 436 #ifndef BREGS
 437 #define BREGS   0
 438 #define TBREGS  0
 439 #endif
 440 #define REGBIT(x) (1 << (x))
 441 #ifndef PERMTYPE
 442 #define PERMTYPE(a)     (INT)
 443 #endif
 444
 445 /* Flags for the dataflow code */
 446 /* do the live/dead analysis */
 447 #define DO_LIVEDEAD  0x01
 448 /* compute avail expressions */
 449 #define DO_AVAILEXPR 0x02
 450 /* Do an update on the live/dead. One variable only */
 451 #define DO_UPDATELD  0x04
 452 /* Do an update on available expressions, one variable has changed */
 453 #define DO_UPDATEEX  0x08
 454
 455 void emit(struct interpass *);
 456 void optimize(struct p2env *);
 457
 458 struct basicblock {
 459         DLIST_ENTRY(basicblock) bbelem;
 460         SLIST_HEAD(, cfgnode) parents; /* CFG - parents to this node */
 461         struct cfgnode *ch[2];          /* Child 1 (and 2) */
 462         int bbnum;      /* this basic block number */
 463         unsigned int dfnum; /* DFS-number */
 464         unsigned int dfparent; /* Parent in DFS */
 465         unsigned int semi;
 466         unsigned int ancestor;
 467         unsigned int idom;
 468         unsigned int samedom;
 469         bittype *bucket;
 470         bittype *df;
 471         bittype *dfchildren;
 472         bittype *Aorig;
 473         bittype *Aphi;
 474         SLIST_HEAD(, phiinfo) phi;
 475
 476         bittype *gen, *killed, *in, *out;       /* Liveness analysis */
 477
 478         struct interpass *first; /* first element of basic block */
 479         struct interpass *last;  /* last element of basic block */
 480 };
 481
 482 struct labelinfo {
 483         struct basicblock **arr;
 484         int size;
 485         unsigned int low;
 486 };
 487
 488 struct bblockinfo {
 489         int size;
 490         struct basicblock **arr;
 491 };
 492
 493 struct varinfo {
 494         struct pvarinfo **arr;
 495         SLIST_HEAD(, varstack) *stack;
 496         int size;
 497         int low;
 498 };
 499
 500 struct pvarinfo {
 501         struct pvarinfo *next;
 502         struct basicblock *bb;
 503         TWORD n_type;
 504 };
 505
 506 struct varstack {
 507         SLIST_ENTRY(varstack) varstackelem;
 508         int tmpregno;
 509 };
 510
 511
 512 struct cfgnode {
 513         SLIST_ENTRY(cfgnode) cfgelem;
 514         struct basicblock *bblock;
 515 };
 516
 517 struct phiinfo {
 518         SLIST_ENTRY(phiinfo) phielem;
 519         int tmpregno;
 520         int newtmpregno;
 521         TWORD n_type;
 522         int size;
 523         int *intmpregno;
 524 };
 525
 526 /*
 527  * Description of the pass2 environment.
 528  * There will be only one of these structs.  It is used to keep
 529  * all state descriptions during the compilation of a function
 530  * in one place.
 531  */
 532 struct p2env {
 533         struct interpass ipole;                 /* all statements */
 534         struct interpass_prolog *ipp, *epp;     /* quick references */
 535         struct bblockinfo bbinfo;
 536         struct labelinfo labinfo;
 537         struct basicblock bblocks;
 538         int nbblocks;
 539 };
 540
 541 extern struct p2env p2env;
 542
 543 /*
 544  * C compiler second pass extra defines.
 545  */
 546 #define PHI (MAXOP + 1)         /* Used in SSA trees */