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