1 /* Id: pass2.h,v 1.124 2010/05/21 16:08:28 ragge Exp */ 2 /* $NetBSD: pass2.h,v 1.1.1.3 2010/06/03 18:57:56 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 #include "protos.h" 46 47 /* cookies, used as arguments to codgen */ 48 #define FOREFF 01 /* compute for effects only */ 49 #define INAREG 02 /* compute into a register */ 50 #define INBREG 04 /* compute into a register */ 51 #define INCREG 010 /* compute into a register */ 52 #define INDREG 020 /* compute into a register */ 53 #define INREGS (INAREG|INBREG|INCREG|INDREG) 54 #define FORCC 040 /* compute for condition codes only */ 55 #define QUIET 0100 /* tell geninsn() to not complain if fail */ 56 #define INTEMP 010000 /* compute into a temporary location */ 57 #define FORREW 040000 /* search the table for a rewrite rule */ 58 #define INEREG 0x10000 /* compute into a register, > 16 bits */ 59 #define INFREG 0x20000 /* compute into a register, > 16 bits */ 60 #define INGREG 0x40000 /* compute into a register, > 16 bits */ 61 62 /* 63 * OP descriptors, 64 * the ASG operator may be used on some of these 65 */ 66 #define OPSIMP 010000 /* +, -, &, |, ^ */ 67 #define OPCOMM 010002 /* +, &, |, ^ */ 68 #define OPMUL 010004 /* *, / */ 69 #define OPDIV 010006 /* /, % */ 70 #define OPUNARY 010010 /* unary ops */ 71 #define OPLEAF 010012 /* leaves */ 72 #define OPANY 010014 /* any op... */ 73 #define OPLOG 010016 /* logical ops */ 74 #define OPFLOAT 010020 /* +, -, *, or / (for floats) */ 75 #define OPSHFT 010022 /* <<, >> */ 76 #define OPLTYPE 010024 /* leaf type nodes (e.g, NAME, ICON, etc.) */ 77 78 /* shapes */ 79 #define SANY 01 /* same as FOREFF */ 80 #define SAREG 02 /* same as INAREG */ 81 #define SBREG 04 /* same as INBREG */ 82 #define SCREG 010 /* same as INCREG */ 83 #define SDREG 020 /* same as INDREG */ 84 #define SCC 040 /* same as FORCC */ 85 #define SNAME 0100 86 #define SCON 0200 87 #define SFLD 0400 88 #define SOREG 01000 89 #define STARNM 02000 90 #define STARREG 04000 91 #define SWADD 040000 92 #define SPECIAL 0100000 93 #define SZERO SPECIAL 94 #define SONE (SPECIAL|1) 95 #define SMONE (SPECIAL|2) 96 #define SCCON (SPECIAL|3) /* -256 <= constant < 256 */ 97 #define SSCON (SPECIAL|4) /* -32768 <= constant < 32768 */ 98 #define SSOREG (SPECIAL|5) /* non-indexed OREG */ 99 #define MAXSPECIAL (SPECIAL|5) 100 #define SEREG 0x10000 /* same as INEREG */ 101 #define SFREG 0x20000 /* same as INFREG */ 102 #define SGREG 0x40000 /* same as INGREG */ 103 104 /* These are used in rstatus[] in conjunction with SxREG */ 105 #define TEMPREG 01000 106 #define PERMREG 02000 107 108 /* tshape() return values */ 109 #define SRNOPE 0 /* Cannot match any shape */ 110 #define SRDIR 1 /* Direct match */ 111 #define SROREG 2 /* Can convert into OREG */ 112 #define SRREG 3 /* Must put into REG */ 113 114 /* find*() return values */ 115 #define FRETRY -2 116 #define FFAIL -1 117 118 /* INTEMP is carefully not conflicting with shapes */ 119 120 /* types */ 121 #define TCHAR 01 /* char */ 122 #define TSHORT 02 /* short */ 123 #define TINT 04 /* int */ 124 #define TLONG 010 /* long */ 125 #define TFLOAT 020 /* float */ 126 #define TDOUBLE 040 /* double */ 127 #define TPOINT 0100 /* pointer to something */ 128 #define TUCHAR 0200 /* unsigned char */ 129 #define TUSHORT 0400 /* unsigned short */ 130 #define TUNSIGNED 01000 /* unsigned int */ 131 #define TULONG 02000 /* unsigned long */ 132 #define TPTRTO 04000 /* pointer to one of the above */ 133 #define TANY 010000 /* matches anything within reason */ 134 #define TSTRUCT 020000 /* structure or union */ 135 #define TLONGLONG 040000 /* long long */ 136 #define TULONGLONG 0100000 /* unsigned long long */ 137 #define TLDOUBLE 0200000 /* long double; exceeds 16 bit */ 138 #define TFTN 0400000 /* function pointer; exceeds 16 bit */ 139 140 /* reclamation cookies */ 141 #define RNULL 0 /* clobber result */ 142 #define RLEFT 01 143 #define RRIGHT 02 144 #define RESC1 04 145 #define RESC2 010 146 #define RESC3 020 147 #define RDEST 040 148 #define RESCC 04000 149 #define RNOP 010000 /* DANGER: can cause loops.. */ 150 151 /* needs */ 152 #define NASL 0x0001 /* may share left register */ 153 #define NASR 0x0002 /* may share right register */ 154 #define NAREG 0x0004 155 #define NACOUNT 0x000c 156 #define NBSL 0x0010 157 #define NBSR 0x0020 158 #define NBREG 0x0040 159 #define NBCOUNT 0x00c0 160 #define NCSL 0x0100 161 #define NCSR 0x0200 162 #define NCREG 0x0400 163 #define NCCOUNT 0x0c00 164 #define NTEMP 0x1000 165 #define NTMASK 0x3000 166 #define NSPECIAL 0x4000 /* need special register treatment */ 167 #define REWRITE 0x8000 168 #define NDSL 0x00010000 /* Above 16 bit */ 169 #define NDSR 0x00020000 /* Above 16 bit */ 170 #define NDREG 0x00040000 /* Above 16 bit */ 171 #define NDCOUNT 0x000c0000 172 #define NESL 0x00100000 /* Above 16 bit */ 173 #define NESR 0x00200000 /* Above 16 bit */ 174 #define NEREG 0x00400000 /* Above 16 bit */ 175 #define NECOUNT 0x00c00000 176 #define NFSL 0x01000000 /* Above 16 bit */ 177 #define NFSR 0x02000000 /* Above 16 bit */ 178 #define NFREG 0x04000000 /* Above 16 bit */ 179 #define NFCOUNT 0x0c000000 180 #define NGSL 0x10000000 /* Above 16 bit */ 181 #define NGSR 0x20000000 /* Above 16 bit */ 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 extern NODE resc[]; 231 extern int p2autooff, p2maxautooff; 232 233 extern NODE 234 *talloc(void), 235 *eread(void), 236 *mklnode(int, CONSZ, int, TWORD), 237 *mkbinode(int, NODE *, NODE *, TWORD), 238 *mkunode(int, NODE *, int, TWORD), 239 *getlr(NODE *p, int); 240 241 void eoftn(struct interpass_prolog *); 242 void prologue(struct interpass_prolog *); 243 void e2print(NODE *p, int down, int *a, int *b); 244 void myoptim(struct interpass *); 245 void cbgen(int op, int label); 246 int match(NODE *p, int cookie); 247 int acceptable(struct optab *); 248 int special(NODE *, int); 249 int setasg(NODE *, int); 250 int setuni(NODE *, int); 251 int sucomp(NODE *); 252 int nsucomp(NODE *); 253 int setorder(NODE *); 254 int geninsn(NODE *, int cookie); 255 void adrput(FILE *, NODE *); 256 void comperr(char *str, ...); 257 void genregs(NODE *p); 258 void ngenregs(struct p2env *); 259 NODE *store(NODE *); 260 struct interpass *ipnode(NODE *); 261 void deflab(int); 262 void rmove(int, int, TWORD); 263 int rspecial(struct optab *, int); 264 struct rspecial *nspecial(struct optab *q); 265 void printip(struct interpass *pole); 266 int findops(NODE *p, int); 267 int findasg(NODE *p, int); 268 int finduni(NODE *p, int); 269 int findumul(NODE *p, int); 270 int findleaf(NODE *p, int); 271 int relops(NODE *p); 272 #ifdef FINDMOPS 273 int findmops(NODE *p, int); 274 int treecmp(NODE *p1, NODE *p2); 275 #endif 276 void offstar(NODE *p, int shape); 277 int gclass(TWORD); 278 void lastcall(NODE *); 279 void myreader(struct interpass *pole); 280 int oregok(NODE *p, int sharp); 281 void myormake(NODE *); 282 int *livecall(NODE *); 283 void prtreg(FILE *, NODE *); 284 char *prcook(int); 285 int myxasm(struct interpass *ip, NODE *p); 286 int xasmcode(char *s); 287 int freetemp(int k); 288 int rewfld(NODE *p); 289 void canon(NODE *); 290 void mycanon(NODE *); 291 void oreg2(NODE *p, void *); 292 int shumul(NODE *p, int); 293 NODE *deluseless(NODE *p); 294 int getlab2(void); 295 296 void conput(FILE *, NODE *); 297 298 extern char *rnames[]; 299 extern int rstatus[]; 300 extern int roverlap[MAXREGS][MAXREGS]; 301 302 extern int classmask(int), tclassmask(int); 303 extern void cmapinit(void); 304 extern int aliasmap(int adjclass, int regnum); 305 extern int regK[]; 306 #define CLASSA 1 307 #define CLASSB 2 308 #define CLASSC 3 309 #define CLASSD 4 310 #define CLASSE 5 311 #define CLASSF 6 312 #define CLASSG 7 313 314 /* used when parsing xasm codes */ 315 #define XASMVAL(x) ((x) & 0377) /* get val from codeword */ 316 #define XASMASG 0x100 /* = */ 317 #define XASMCONSTR 0x200 /* & */ 318 #define XASMINOUT 0x400 /* + */ 319 #define XASMALL (XASMASG|XASMCONSTR|XASMINOUT) 320 #define XASMISINP(cw) (((cw) & XASMASG) == 0) /* input operand */ 321 #define XASMISOUT(cw) ((cw) & (XASMASG|XASMINOUT)) /* output operand */ 322 323 /* routines to handle double indirection */ 324 #ifdef R2REGS 325 void makeor2(NODE *p, NODE *q, int, int); 326 int base(NODE *); 327 int offset(NODE *p, int); 328 #endif 329 330 extern int lineno; 331 extern int fldshf, fldsz; 332 extern int lflag, x2debug, udebug, e2debug, odebug; 333 extern int rdebug, t2debug, s2debug, b2debug, c2debug; 334 extern int g2debug; 335 extern int kflag; 336 #ifdef FORT 337 extern int Oflag; 338 #endif 339 340 #ifndef callchk 341 #define callchk(x) allchk() 342 #endif 343 344 #ifndef PUTCHAR 345 #define PUTCHAR(x) putchar(x) 346 #endif 347 348 extern int dope[]; /* a vector containing operator information */ 349 extern char *opst[]; /* a vector containing names for ops */ 350 351 #ifdef PCC_DEBUG 352 353 static inline int 354 optype(int o) 355 { 356 if (o >= MAXOP+1) 357 cerror("optype"); 358 return (dope[o]&TYFLG); 359 } 360 361 static inline int 362 asgop(int o) 363 { 364 if (o >= MAXOP+1) 365 cerror("asgop"); 366 return (dope[o]&ASGFLG); 367 } 368 369 static inline int 370 logop(int o) 371 { 372 if (o >= MAXOP+1) 373 cerror("logop"); 374 return (dope[o]&LOGFLG); 375 } 376 377 static inline int 378 callop(int o) 379 { 380 if (o >= MAXOP+1) 381 cerror("callop"); 382 return (dope[o]&CALLFLG); 383 } 384 385 #else 386 387 #define optype(o) (dope[o]&TYFLG) 388 #define asgop(o) (dope[o]&ASGFLG) 389 #define logop(o) (dope[o]&LOGFLG) 390 #define callop(o) (dope[o]&CALLFLG) 391 392 #endif 393 394 /* macros for doing double indexing */ 395 #define R2PACK(x,y,z) (0200*((x)+1)+y+040000*z) 396 #define R2UPK1(x) ((((x)>>7)-1)&0177) 397 #define R2UPK2(x) ((x)&0177) 398 #define R2UPK3(x) (x>>14) 399 #define R2TEST(x) ((x)>=0200) 400 401 /* 402 * Layout of findops() return value: 403 * bit 0 whether left shall go into a register. 404 * bit 1 whether right shall go into a register. 405 * bit 2 entry is only used for side effects. 406 * bit 3 if condition codes are used. 407 * 408 * These values should be synced with FOREFF/FORCC. 409 */ 410 #define LREG 001 411 #define RREG 002 412 #define RVEFF 004 413 #define RVCC 010 414 #define DORIGHT 020 415 #define SCLASS(v,x) ((v) |= ((x) << 5)) 416 #define TCLASS(x) (((x) >> 5) & 7) 417 #define TBSH 8 418 #define TBLIDX(idx) ((idx) >> TBSH) 419 #define MKIDX(tbl,mod) (((tbl) << TBSH) | (mod)) 420 421 #ifndef BREGS 422 #define BREGS 0 423 #define TBREGS 0 424 #endif 425 #define REGBIT(x) (1 << (x)) 426 #ifndef PERMTYPE 427 #define PERMTYPE(a) (INT) 428 #endif 429 430 /* Flags for the dataflow code */ 431 /* do the live/dead analysis */ 432 #define DO_LIVEDEAD 0x01 433 /* compute avail expressions */ 434 #define DO_AVAILEXPR 0x02 435 /* Do an update on the live/dead. One variable only */ 436 #define DO_UPDATELD 0x04 437 /* Do an update on available expressions, one variable has changed */ 438 #define DO_UPDATEEX 0x08 439 440 void emit(struct interpass *); 441 void optimize(struct p2env *); 442 443 struct basicblock { 444 DLIST_ENTRY(basicblock) bbelem; 445 SLIST_HEAD(, cfgnode) children; /* CFG - children to this node */ 446 SLIST_HEAD(, cfgnode) parents; /* CFG - parents to this node */ 447 int bbnum; /* this basic block number */ 448 unsigned int dfnum; /* DFS-number */ 449 unsigned int dfparent; /* Parent in DFS */ 450 unsigned int semi; 451 unsigned int ancestor; 452 unsigned int idom; 453 unsigned int samedom; 454 bittype *bucket; 455 bittype *df; 456 bittype *dfchildren; 457 bittype *Aorig; 458 bittype *Aphi; 459 SLIST_HEAD(, phiinfo) phi; 460 461 bittype *gen, *killed, *in, *out; /* Liveness analysis */ 462 463 struct interpass *first; /* first element of basic block */ 464 struct interpass *last; /* last element of basic block */ 465 }; 466 467 struct labelinfo { 468 struct basicblock **arr; 469 int size; 470 unsigned int low; 471 }; 472 473 struct bblockinfo { 474 int size; 475 struct basicblock **arr; 476 }; 477 478 struct varinfo { 479 struct pvarinfo **arr; 480 SLIST_HEAD(, varstack) *stack; 481 int size; 482 int low; 483 }; 484 485 struct pvarinfo { 486 struct pvarinfo *next; 487 struct basicblock *bb; 488 TWORD n_type; 489 }; 490 491 struct varstack { 492 SLIST_ENTRY(varstack) varstackelem; 493 int tmpregno; 494 }; 495 496 497 struct cfgnode { 498 SLIST_ENTRY(cfgnode) cfgelem; 499 struct basicblock *bblock; 500 }; 501 502 struct phiinfo { 503 SLIST_ENTRY(phiinfo) phielem; 504 int tmpregno; 505 int newtmpregno; 506 TWORD n_type; 507 int size; 508 int *intmpregno; 509 }; 510 511 /* 512 * Description of the pass2 environment. 513 * There will be only one of these structs. It is used to keep 514 * all state descriptions during the compilation of a function 515 * in one place. 516 */ 517 struct p2env { 518 struct interpass ipole; /* all statements */ 519 struct interpass_prolog *ipp, *epp; /* quick references */ 520 struct bblockinfo bbinfo; 521 struct labelinfo labinfo; 522 struct basicblock bblocks; 523 int nbblocks; 524 }; 525 526 extern struct p2env p2env; 527 528 /* 529 * C compiler second pass extra defines. 530 */ 531 #define PHI (MAXOP + 1) /* Used in SSA trees */ 532