1 /* Id: pass2.h,v 1.131 2012/03/22 18:51:41 plunky Exp */ 2 /* $NetBSD: pass2.h,v 1.1.1.5 2012/03/26 14:27:14 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(FILE *, NODE *); 285 char *prcook(int); 286 int myxasm(struct interpass *ip, NODE *p); 287 int xasmcode(char *s); 288 int freetemp(int k); 289 int rewfld(NODE *p); 290 void canon(NODE *); 291 void mycanon(NODE *); 292 void oreg2(NODE *p, void *); 293 int shumul(NODE *p, int); 294 NODE *deluseless(NODE *p); 295 int getlab2(void); 296 int tshape(NODE *, int); 297 void conput(FILE *, NODE *); 298 int shtemp(NODE *p); 299 int ttype(TWORD t, int tword); 300 void expand(NODE *, int, char *); 301 void hopcode(int, int); 302 void adrcon(CONSZ); 303 void zzzcode(NODE *, int); 304 void insput(NODE *); 305 void upput(NODE *, int); 306 int tlen(NODE *p); 307 int setbin(NODE *); 308 int notoff(TWORD, int, CONSZ, char *); 309 int fldexpand(NODE *, int, char **); 310 void p2tree(NODE *p); 311 int flshape(NODE *p); 312 int ncnt(int needs); 313 314 315 extern char *rnames[]; 316 extern int rstatus[]; 317 extern int roverlap[MAXREGS][MAXREGS]; 318 319 extern int classmask(int), tclassmask(int); 320 extern void cmapinit(void); 321 extern int aliasmap(int adjclass, int regnum); 322 extern int regK[]; 323 #define CLASSA 1 324 #define CLASSB 2 325 #define CLASSC 3 326 #define CLASSD 4 327 #define CLASSE 5 328 #define CLASSF 6 329 #define CLASSG 7 330 331 /* used when parsing xasm codes */ 332 #define XASMVAL(x) ((x) & 0377) /* get val from codeword */ 333 #define XASMVAL1(x) (((x) >> 16) & 0377) /* get val from codeword */ 334 #define XASMVAL2(x) (((x) >> 24) & 0377) /* get val from codeword */ 335 #define XASMASG 0x100 /* = */ 336 #define XASMCONSTR 0x200 /* & */ 337 #define XASMINOUT 0x400 /* + */ 338 #define XASMALL (XASMASG|XASMCONSTR|XASMINOUT) 339 #define XASMISINP(cw) (((cw) & XASMASG) == 0) /* input operand */ 340 #define XASMISOUT(cw) ((cw) & (XASMASG|XASMINOUT)) /* output operand */ 341 342 /* routines to handle double indirection */ 343 #ifdef R2REGS 344 void makeor2(NODE *p, NODE *q, int, int); 345 int base(NODE *); 346 int offset(NODE *p, int); 347 #endif 348 349 extern int lineno; 350 extern int fldshf, fldsz; 351 extern int ndebug; 352 extern int b2debug, c2debug, e2debug, f2debug, g2debug, o2debug; 353 extern int r2debug, s2debug, t2debug, u2debug, x2debug; 354 355 #ifdef FORT 356 extern int Oflag; 357 #endif 358 359 #ifndef callchk 360 #define callchk(x) allchk() 361 #endif 362 363 #ifndef PUTCHAR 364 #define PUTCHAR(x) putchar(x) 365 #endif 366 367 extern int dope[]; /* a vector containing operator information */ 368 extern char *opst[]; /* a vector containing names for ops */ 369 370 #ifdef PCC_DEBUG 371 372 static inline int 373 optype(int o) 374 { 375 if (o >= MAXOP+1) 376 cerror("optype"); 377 return (dope[o]&TYFLG); 378 } 379 380 static inline int 381 asgop(int o) 382 { 383 if (o >= MAXOP+1) 384 cerror("asgop"); 385 return (dope[o]&ASGFLG); 386 } 387 388 static inline int 389 logop(int o) 390 { 391 if (o >= MAXOP+1) 392 cerror("logop"); 393 return (dope[o]&LOGFLG); 394 } 395 396 static inline int 397 callop(int o) 398 { 399 if (o >= MAXOP+1) 400 cerror("callop"); 401 return (dope[o]&CALLFLG); 402 } 403 404 #else 405 406 #define optype(o) (dope[o]&TYFLG) 407 #define asgop(o) (dope[o]&ASGFLG) 408 #define logop(o) (dope[o]&LOGFLG) 409 #define callop(o) (dope[o]&CALLFLG) 410 411 #endif 412 413 /* macros for doing double indexing */ 414 #define R2PACK(x,y,z) (0200*((x)+1)+y+040000*z) 415 #define R2UPK1(x) ((((x)>>7)-1)&0177) 416 #define R2UPK2(x) ((x)&0177) 417 #define R2UPK3(x) (x>>14) 418 #define R2TEST(x) ((x)>=0200) 419 420 /* 421 * Layout of findops() return value: 422 * bit 0 whether left shall go into a register. 423 * bit 1 whether right shall go into a register. 424 * bit 2 entry is only used for side effects. 425 * bit 3 if condition codes are used. 426 * 427 * These values should be synced with FOREFF/FORCC. 428 */ 429 #define LREG 001 430 #define RREG 002 431 #define RVEFF 004 432 #define RVCC 010 433 #define DORIGHT 020 434 #define SCLASS(v,x) ((v) |= ((x) << 5)) 435 #define TCLASS(x) (((x) >> 5) & 7) 436 #define TBSH 8 437 #define TBLIDX(idx) ((idx) >> TBSH) 438 #define MKIDX(tbl,mod) (((tbl) << TBSH) | (mod)) 439 440 #ifndef BREGS 441 #define BREGS 0 442 #define TBREGS 0 443 #endif 444 #define REGBIT(x) (1 << (x)) 445 #ifndef PERMTYPE 446 #define PERMTYPE(a) (INT) 447 #endif 448 449 /* Flags for the dataflow code */ 450 /* do the live/dead analysis */ 451 #define DO_LIVEDEAD 0x01 452 /* compute avail expressions */ 453 #define DO_AVAILEXPR 0x02 454 /* Do an update on the live/dead. One variable only */ 455 #define DO_UPDATELD 0x04 456 /* Do an update on available expressions, one variable has changed */ 457 #define DO_UPDATEEX 0x08 458 459 void emit(struct interpass *); 460 void optimize(struct p2env *); 461 462 struct basicblock { 463 DLIST_ENTRY(basicblock) bbelem; 464 SLIST_HEAD(, cfgnode) parents; /* CFG - parents to this node */ 465 struct cfgnode *ch[2]; /* Child 1 (and 2) */ 466 int bbnum; /* this basic block number */ 467 unsigned int dfnum; /* DFS-number */ 468 unsigned int dfparent; /* Parent in DFS */ 469 unsigned int semi; 470 unsigned int ancestor; 471 unsigned int idom; 472 unsigned int samedom; 473 bittype *bucket; 474 bittype *df; 475 bittype *dfchildren; 476 bittype *Aorig; 477 bittype *Aphi; 478 SLIST_HEAD(, phiinfo) phi; 479 480 bittype *gen, *killed, *in, *out; /* Liveness analysis */ 481 482 struct interpass *first; /* first element of basic block */ 483 struct interpass *last; /* last element of basic block */ 484 }; 485 486 struct labelinfo { 487 struct basicblock **arr; 488 int size; 489 unsigned int low; 490 }; 491 492 struct bblockinfo { 493 int size; 494 struct basicblock **arr; 495 }; 496 497 struct varinfo { 498 struct pvarinfo **arr; 499 SLIST_HEAD(, varstack) *stack; 500 int size; 501 int low; 502 }; 503 504 struct pvarinfo { 505 struct pvarinfo *next; 506 struct basicblock *bb; 507 TWORD n_type; 508 }; 509 510 struct varstack { 511 SLIST_ENTRY(varstack) varstackelem; 512 int tmpregno; 513 }; 514 515 516 struct cfgnode { 517 SLIST_ENTRY(cfgnode) cfgelem; 518 struct basicblock *bblock; 519 }; 520 521 struct phiinfo { 522 SLIST_ENTRY(phiinfo) phielem; 523 int tmpregno; 524 int newtmpregno; 525 TWORD n_type; 526 int size; 527 int *intmpregno; 528 }; 529 530 /* 531 * Description of the pass2 environment. 532 * There will be only one of these structs. It is used to keep 533 * all state descriptions during the compilation of a function 534 * in one place. 535 */ 536 struct p2env { 537 struct interpass ipole; /* all statements */ 538 struct interpass_prolog *ipp, *epp; /* quick references */ 539 struct bblockinfo bbinfo; 540 struct labelinfo labinfo; 541 struct basicblock bblocks; 542 int nbblocks; 543 }; 544 545 extern struct p2env p2env; 546 547 /* 548 * C compiler second pass extra defines. 549 */ 550 #define PHI (MAXOP + 1) /* Used in SSA trees */ 551