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 41 typedef 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 200 extern int fregs; 201 202 /* code tables */ 203 extern 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 */ 216 struct 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 229 struct p2env; 230 #define NRESC 4 231 extern NODE resc[]; 232 extern int p2autooff, p2maxautooff; 233 234 extern 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 242 void eoftn(struct interpass_prolog *); 243 void prologue(struct interpass_prolog *); 244 void e2print(NODE *p, int down, int *a, int *b); 245 void myoptim(struct interpass *); 246 void cbgen(int op, int label); 247 int match(NODE *p, int cookie); 248 int acceptable(struct optab *); 249 int special(NODE *, int); 250 int setasg(NODE *, int); 251 int setuni(NODE *, int); 252 int sucomp(NODE *); 253 int nsucomp(NODE *); 254 int setorder(NODE *); 255 int geninsn(NODE *, int cookie); 256 void adrput(FILE *, NODE *); 257 void comperr(char *str, ...); 258 void genregs(NODE *p); 259 void ngenregs(struct p2env *); 260 NODE *store(NODE *); 261 struct interpass *ipnode(NODE *); 262 void deflab(int); 263 void rmove(int, int, TWORD); 264 int rspecial(struct optab *, int); 265 struct rspecial *nspecial(struct optab *q); 266 void printip(struct interpass *pole); 267 int findops(NODE *p, int); 268 int findasg(NODE *p, int); 269 int finduni(NODE *p, int); 270 int findumul(NODE *p, int); 271 int findleaf(NODE *p, int); 272 int relops(NODE *p); 273 #ifdef FINDMOPS 274 int findmops(NODE *p, int); 275 int treecmp(NODE *p1, NODE *p2); 276 #endif 277 void offstar(NODE *p, int shape); 278 int gclass(TWORD); 279 void lastcall(NODE *); 280 void myreader(struct interpass *pole); 281 int oregok(NODE *p, int sharp); 282 void myormake(NODE *); 283 int *livecall(NODE *); 284 void prtreg(NODE *); 285 char *prcook(int); 286 int myxasm(struct interpass *ip, NODE *p); 287 int xasmcode(char *s); 288 int freetemp(int k); 289 NODE *storenode(TWORD t, int k); 290 void storemod(NODE *, int k, int reg); 291 int rewfld(NODE *p); 292 void canon(NODE *); 293 void mycanon(NODE *); 294 void oreg2(NODE *p, void *); 295 int shumul(NODE *p, int); 296 NODE *deluseless(NODE *p); 297 int getlab2(void); 298 int tshape(NODE *, int); 299 void conput(FILE *, NODE *); 300 int shtemp(NODE *p); 301 int ttype(TWORD t, int tword); 302 void expand(NODE *, int, char *); 303 void hopcode(int, int); 304 void adrcon(CONSZ); 305 void zzzcode(NODE *, int); 306 void insput(NODE *); 307 void upput(NODE *, int); 308 int tlen(NODE *p); 309 int setbin(NODE *); 310 int notoff(TWORD, int, CONSZ, char *); 311 int fldexpand(NODE *, int, char **); 312 int flshape(NODE *p); 313 int ncnt(int needs); 314 void mainp2(void); 315 316 extern char *rnames[]; 317 318 extern int classmask(int), tclassmask(int); 319 extern void cmapinit(void); 320 extern int aliasmap(int adjclass, int regnum); 321 extern 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 343 void makeor2(NODE *p, NODE *q, int, int); 344 int base(NODE *); 345 int offset(NODE *p, int); 346 #endif 347 348 extern int lineno; 349 extern int ndebug; 350 extern int b2debug, c2debug, e2debug, f2debug, g2debug, o2debug; 351 extern int r2debug, s2debug, t2debug, u2debug, x2debug; 352 353 extern int dope[]; /* a vector containing operator information */ 354 extern char *opst[]; /* a vector containing names for ops */ 355 356 #ifdef PCC_DEBUG 357 358 static inline int 359 optype(int o) 360 { 361 if (o >= MAXOP+1) 362 cerror("optype"); 363 return (dope[o]&TYFLG); 364 } 365 366 static inline int 367 asgop(int o) 368 { 369 if (o >= MAXOP+1) 370 cerror("asgop"); 371 return (dope[o]&ASGFLG); 372 } 373 374 static inline int 375 logop(int o) 376 { 377 if (o >= MAXOP+1) 378 cerror("logop"); 379 return (dope[o]&LOGFLG); 380 } 381 382 static inline int 383 callop(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 445 void emit(struct interpass *); 446 void optimize(struct p2env *); 447 448 struct 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 472 struct labelinfo { 473 struct basicblock **arr; 474 int size; 475 unsigned int low; 476 }; 477 478 struct bblockinfo { 479 int size; 480 struct basicblock **arr; 481 }; 482 483 struct varinfo { 484 struct pvarinfo **arr; 485 SLIST_HEAD(, varstack) *stack; 486 int size; 487 int low; 488 }; 489 490 struct pvarinfo { 491 struct pvarinfo *next; 492 struct basicblock *bb; 493 TWORD n_type; 494 }; 495 496 struct varstack { 497 SLIST_ENTRY(varstack) varstackelem; 498 int tmpregno; 499 }; 500 501 502 struct cfgnode { 503 SLIST_ENTRY(cfgnode) cfgelem; 504 SLIST_ENTRY(cfgnode) chld; 505 struct basicblock *bblock; 506 }; 507 508 struct 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 */ 523 struct 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 532 extern struct p2env p2env; 533 534 /* 535 * C compiler second pass extra defines. 536 */ 537 #define PHI (MAXOP + 1) /* Used in SSA trees */ 538 539 enum { 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