1 /* Id: match.c,v 1.104 2015/11/17 19:19:40 ragge Exp */ 2 /* $NetBSD: match.c,v 1.1.1.7 2016/02/09 20:29:15 plunky Exp $ */ 3 /* 4 * Copyright (c) 2003 Anders Magnusson (ragge (at) ludd.luth.se). 5 * All rights reserved. 6 * 7 * Redistribution and use in source and binary forms, with or without 8 * modification, are permitted provided that the following conditions 9 * are met: 10 * 1. Redistributions of source code must retain the above copyright 11 * notice, this list of conditions and the following disclaimer. 12 * 2. Redistributions in binary form must reproduce the above copyright 13 * notice, this list of conditions and the following disclaimer in the 14 * documentation and/or other materials provided with the distribution. 15 * 3. The name of the author may not be used to endorse or promote products 16 * derived from this software without specific prior written permission 17 * 18 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR 19 * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES 20 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. 21 * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, 22 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT 23 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 24 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 25 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 26 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF 27 * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 28 */ 29 30 /* 31 * Copyright(C) Caldera International Inc. 2001-2002. All rights reserved. 32 * 33 * Redistribution and use in source and binary forms, with or without 34 * modification, are permitted provided that the following conditions 35 * are met: 36 * 37 * Redistributions of source code and documentation must retain the above 38 * copyright notice, this list of conditions and the following disclaimer. 39 * Redistributions in binary form must reproduce the above copyright 40 * notice, this list of conditionsand the following disclaimer in the 41 * documentation and/or other materials provided with the distribution. 42 * All advertising materials mentioning features or use of this software 43 * must display the following acknowledgement: 44 * This product includes software developed or owned by Caldera 45 * International, Inc. 46 * Neither the name of Caldera International, Inc. nor the names of other 47 * contributors may be used to endorse or promote products derived from 48 * this software without specific prior written permission. 49 * 50 * USE OF THE SOFTWARE PROVIDED FOR UNDER THIS LICENSE BY CALDERA 51 * INTERNATIONAL, INC. AND CONTRIBUTORS ``AS IS'' AND ANY EXPRESS OR 52 * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED 53 * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE 54 * DISCLAIMED. IN NO EVENT SHALL CALDERA INTERNATIONAL, INC. BE LIABLE 55 * FOR ANY DIRECT, INDIRECT INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 56 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 57 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 58 * HOWEVER CAUSED AND ON ANY THEORY OFLIABILITY, WHETHER IN CONTRACT, 59 * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING 60 * IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE 61 * POSSIBILITY OF SUCH DAMAGE. 62 */ 63 64 #include "pass2.h" 65 66 #ifdef HAVE_STRINGS_H 67 #include <strings.h> 68 #endif 69 70 void setclass(int tmp, int class); 71 int getclass(int tmp); 72 73 #ifdef PCC_DEBUG 74 static char *srtyp[] = { "SRNOPE", "SRDIR", "SROREG", "SRREG" }; 75 #endif 76 77 /* 78 * return true if shape is appropriate for the node p 79 * 80 * Return values: 81 * SRNOPE Cannot match this shape. 82 * SRDIR Direct match, may or may not traverse down. 83 * SRREG Will match if put in a regster XXX - kill this? 84 */ 85 int 86 tshape(NODE *p, int shape) 87 { 88 int o, mask; 89 90 o = p->n_op; 91 92 #ifdef PCC_DEBUG 93 if (s2debug) 94 printf("tshape(%p, %s) op = %s\n", p, prcook(shape), opst[o]); 95 #endif 96 97 if (shape & SPECIAL) { 98 99 switch (shape) { 100 case SZERO: 101 case SONE: 102 case SMONE: 103 case SSCON: 104 case SCCON: 105 if (o != ICON || p->n_name[0]) 106 return SRNOPE; 107 if (getlval(p)== 0 && shape == SZERO) 108 return SRDIR; 109 if (getlval(p) == 1 && shape == SONE) 110 return SRDIR; 111 if (getlval(p) == -1 && shape == SMONE) 112 return SRDIR; 113 if (getlval(p) > -257 && getlval(p) < 256 && 114 shape == SCCON) 115 return SRDIR; 116 if (getlval(p) > -32769 && getlval(p) < 32768 && 117 shape == SSCON) 118 return SRDIR; 119 return SRNOPE; 120 121 case SSOREG: /* non-indexed OREG */ 122 if (o == OREG && !R2TEST(p->n_rval)) 123 return SRDIR; 124 return SRNOPE; 125 126 default: 127 return (special(p, shape)); 128 } 129 } 130 131 if (shape & SANY) 132 return SRDIR; 133 134 if ((shape&INTEMP) && shtemp(p)) /* XXX remove? */ 135 return SRDIR; 136 137 if ((shape&SWADD) && (o==NAME||o==OREG)) 138 if (BYTEOFF(getlval(p))) 139 return SRNOPE; 140 141 switch (o) { 142 143 case NAME: 144 if (shape & SNAME) 145 return SRDIR; 146 break; 147 148 case ICON: 149 case FCON: 150 if (shape & SCON) 151 return SRDIR; 152 break; 153 154 case FLD: 155 if (shape & SFLD) 156 return flshape(p->n_left); 157 break; 158 159 case CCODES: 160 if (shape & SCC) 161 return SRDIR; 162 break; 163 164 case REG: 165 case TEMP: 166 mask = PCLASS(p); 167 if (shape & mask) 168 return SRDIR; 169 break; 170 171 case OREG: 172 if (shape & SOREG) 173 return SRDIR; 174 break; 175 176 case UMUL: 177 #if 0 178 if (shumul(p->n_left) & shape) 179 return SROREG; /* Calls offstar to traverse down */ 180 break; 181 #else 182 return shumul(p->n_left, shape); 183 #endif 184 185 } 186 return SRNOPE; 187 } 188 189 /* 190 * does the type t match tword 191 */ 192 int 193 ttype(TWORD t, int tword) 194 { 195 if (tword & TANY) 196 return(1); 197 198 #ifdef PCC_DEBUG 199 if (t2debug) 200 printf("ttype(0x%x, 0x%x)\n", t, tword); 201 #endif 202 if (ISPTR(t) && ISFTN(DECREF(t)) && (tword & TFTN)) { 203 /* For funny function pointers */ 204 return 1; 205 } 206 if (ISPTR(t) && (tword&TPTRTO)) { 207 do { 208 t = DECREF(t); 209 } while (ISARY(t)); 210 /* arrays that are left are usually only 211 * in structure references... 212 */ 213 return (ttype(t, tword&(~TPTRTO))); 214 } 215 if (t != BTYPE(t)) 216 return (tword & TPOINT); /* TPOINT means not simple! */ 217 if (tword & TPTRTO) 218 return(0); 219 220 switch (t) { 221 case CHAR: 222 return( tword & TCHAR ); 223 case SHORT: 224 return( tword & TSHORT ); 225 case STRTY: 226 case UNIONTY: 227 return( tword & TSTRUCT ); 228 case INT: 229 return( tword & TINT ); 230 case UNSIGNED: 231 return( tword & TUNSIGNED ); 232 case USHORT: 233 return( tword & TUSHORT ); 234 case UCHAR: 235 return( tword & TUCHAR ); 236 case ULONG: 237 return( tword & TULONG ); 238 case LONG: 239 return( tword & TLONG ); 240 case LONGLONG: 241 return( tword & TLONGLONG ); 242 case ULONGLONG: 243 return( tword & TULONGLONG ); 244 case FLOAT: 245 return( tword & TFLOAT ); 246 case DOUBLE: 247 return( tword & TDOUBLE ); 248 case LDOUBLE: 249 return( tword & TLDOUBLE ); 250 } 251 252 return(0); 253 } 254 255 #define FLDSZ(x) UPKFSZ(x) 256 #if TARGET_ENDIAN == TARGET_LE 257 #define FLDSHF(x) UPKFOFF(x) 258 #else 259 #define FLDSHF(x) (SZINT - FLDSZ(x) - UPKFOFF(x)) 260 #endif 261 262 /* 263 * generate code by interpreting table entry 264 */ 265 void 266 expand(NODE *p, int cookie, char *cp) 267 { 268 CONSZ val; 269 270 #if 0 271 printf("expand\n"); 272 fwalk(p, e2print, 0); 273 #endif 274 275 for( ; *cp; ++cp ){ 276 switch( *cp ){ 277 278 default: 279 putchar(*cp); 280 continue; /* this is the usual case... */ 281 282 case 'Z': /* special machine dependent operations */ 283 zzzcode( p, *++cp ); 284 continue; 285 286 case 'F': /* this line deleted if FOREFF is active */ 287 if (cookie & FOREFF) { 288 while (*cp && *cp != '\n') 289 cp++; 290 if (*cp == 0) 291 return; 292 } 293 continue; 294 295 case 'S': /* field size */ 296 if (fldexpand(p, cookie, &cp)) 297 continue; 298 printf("%d", FLDSZ(p->n_rval)); 299 continue; 300 301 case 'H': /* field shift */ 302 if (fldexpand(p, cookie, &cp)) 303 continue; 304 printf("%d", FLDSHF(p->n_rval)); 305 continue; 306 307 case 'M': /* field mask */ 308 case 'N': /* complement of field mask */ 309 if (fldexpand(p, cookie, &cp)) 310 continue; 311 val = 1; 312 val <<= FLDSZ(p->n_rval); 313 --val; 314 val <<= FLDSHF(p->n_rval); 315 adrcon( *cp=='M' ? val : ~val ); 316 continue; 317 318 case 'L': /* output special label field */ 319 if (*++cp == 'C') 320 printf(LABFMT, p->n_label); 321 else 322 printf(LABFMT, (int)getlval(getlr(p,*cp))); 323 continue; 324 325 case 'O': /* opcode string */ 326 #ifdef FINDMOPS 327 if (p->n_op == ASSIGN) 328 hopcode(*++cp, p->n_right->n_op); 329 else 330 #endif 331 hopcode( *++cp, p->n_op ); 332 continue; 333 334 case 'B': /* byte offset in word */ 335 val = getlval(getlr(p,*++cp)); 336 val = BYTEOFF(val); 337 printf( CONFMT, val ); 338 continue; 339 340 case 'C': /* for constant value only */ 341 conput(stdout, getlr( p, *++cp ) ); 342 continue; 343 344 case 'I': /* in instruction */ 345 insput( getlr( p, *++cp ) ); 346 continue; 347 348 case 'A': /* address of */ 349 adrput(stdout, getlr( p, *++cp ) ); 350 continue; 351 352 case 'U': /* for upper half of address, only */ 353 upput(getlr(p, *++cp), SZLONG); 354 continue; 355 356 } 357 358 } 359 360 } 361 362 NODE resc[NRESC]; 363 364 NODE * 365 getlr(NODE *p, int c) 366 { 367 /* return the pointer to the left or right side of p, or p itself, 368 depending on the optype of p */ 369 370 switch (c) { 371 372 case '1': 373 case '2': 374 case '3': 375 case 'D': 376 if (c == 'D') 377 c = 0; 378 else 379 c -= '0'; 380 if (resc[c].n_op == FREE) 381 comperr("getlr: free node"); 382 return &resc[c]; 383 384 case 'L': 385 return( optype( p->n_op ) == LTYPE ? p : p->n_left ); 386 387 case 'R': 388 return( optype( p->n_op ) != BITYPE ? p : p->n_right ); 389 390 } 391 cerror( "bad getlr: %c", c ); 392 /* NOTREACHED */ 393 return NULL; 394 } 395 396 #ifdef PCC_DEBUG 397 #define F2DEBUG(x) if (f2debug) printf x 398 #define F2WALK(x) if (f2debug) fwalk(x, e2print, 0) 399 #else 400 #define F2DEBUG(x) 401 #define F2WALK(x) 402 #endif 403 404 /* 405 * Convert a node to REG or OREG. 406 * Shape is register class where we want the result. 407 * Returns register class if register nodes. 408 * If w is: (should be shapes) 409 * - SRREG - result in register, call geninsn(). 410 * - SROREG - create OREG; call offstar(). 411 * - 0 - clear su, walk down. 412 */ 413 static int 414 swmatch(NODE *p, int shape, int w) 415 { 416 int rv = 0; 417 418 F2DEBUG(("swmatch: p=%p, shape=%s, w=%s\n", p, prcook(shape), srtyp[w])); 419 420 switch (w) { 421 case SRREG: 422 rv = geninsn(p, shape); 423 break; 424 425 case SROREG: 426 /* should be here only if op == UMUL */ 427 if (p->n_op != UMUL && p->n_op != FLD) 428 comperr("swmatch %p", p); 429 if (p->n_op == FLD) { 430 offstar(p->n_left->n_left, shape); 431 p->n_left->n_su = 0; 432 } else 433 offstar(p->n_left, shape); 434 p->n_su = 0; 435 rv = ffs(shape)-1; 436 break; 437 438 case 0: 439 if (optype(p->n_op) == BITYPE) 440 swmatch(p->n_right, 0, 0); 441 if (optype(p->n_op) != LTYPE) 442 swmatch(p->n_left, 0, 0); 443 p->n_su = 0; 444 } 445 return rv; 446 447 } 448 449 /* 450 * Help routines for find*() functions. 451 * If the node will be a REG node and it will be rewritten in the 452 * instruction, ask for it to be put in a register. 453 */ 454 static int 455 chcheck(NODE *p, int shape, int rew) 456 { 457 int sh, sha; 458 459 sha = shape; 460 if (shape & SPECIAL) 461 shape = 0; 462 463 switch ((sh = tshape(p, sha))) { 464 case SRNOPE: 465 if (shape & INREGS) 466 sh = SRREG; 467 break; 468 469 case SROREG: 470 case SRDIR: 471 if (rew == 0) 472 break; 473 if (shape & INREGS) 474 sh = SRREG; 475 else 476 sh = SRNOPE; 477 break; 478 } 479 return sh; 480 } 481 482 /* 483 * Check how to walk further down. 484 * Merge with swmatch()? 485 * sh - shape for return value (register class). 486 * p - node (for this leg) 487 * shape - given shape for this leg 488 * cookie - cookie given for parent node 489 * rew - 490 * go - switch key for traversing down 491 * returns register class. 492 */ 493 static int 494 shswitch(int sh, NODE *p, int shape, int cookie, int rew, int go) 495 { 496 int lsh; 497 498 F2DEBUG(("shswitch: p=%p, shape=%s, ", p, prcook(shape))); 499 F2DEBUG(("cookie=%s, rew=0x%x, go=%s\n", prcook(cookie), rew, srtyp[go])); 500 501 switch (go) { 502 case SRDIR: /* direct match, just clear su */ 503 (void)swmatch(p, 0, 0); 504 break; 505 506 case SROREG: /* call offstar to prepare for OREG conversion */ 507 (void)swmatch(p, shape, SROREG); 508 break; 509 510 case SRREG: /* call geninsn() to get value into register */ 511 lsh = shape & (FORCC | INREGS); 512 if (rew && cookie != FOREFF) 513 lsh &= (cookie & (FORCC | INREGS)); 514 lsh = swmatch(p, lsh, SRREG); 515 if (rew) 516 sh = lsh; 517 break; 518 } 519 return sh; 520 } 521 522 /* 523 * Find the best instruction to evaluate the given tree. 524 * Best is to match both subnodes directly, second-best is if 525 * subnodes must be evaluated into OREGs, thereafter if nodes 526 * must be put into registers. 527 * Whether 2-op instructions or 3-op is preferred is depending on in 528 * which order they are found in the table. 529 * mtchno is set to the count of regs needed for its legs. 530 */ 531 int 532 findops(NODE *p, int cookie) 533 { 534 extern int *qtable[]; 535 struct optab *q, *qq = NULL; 536 int i, shl, shr, *ixp, sh; 537 int lvl = 10, idx = 0, gol = 0, gor = 0; 538 NODE *l, *r; 539 540 F2DEBUG(("findops node %p (%s)\n", p, prcook(cookie))); 541 F2WALK(p); 542 543 ixp = qtable[p->n_op]; 544 l = getlr(p, 'L'); 545 r = getlr(p, 'R'); 546 for (i = 0; ixp[i] >= 0; i++) { 547 q = &table[ixp[i]]; 548 549 F2DEBUG(("findop: ixp %d str %s\n", ixp[i], q->cstring)); 550 if (!acceptable(q)) /* target-dependent filter */ 551 continue; 552 553 if (ttype(l->n_type, q->ltype) == 0 || 554 ttype(r->n_type, q->rtype) == 0) 555 continue; /* Types must be correct */ 556 557 if ((cookie & q->visit) == 0) 558 continue; /* must get a result */ 559 560 F2DEBUG(("findop got types\n")); 561 562 if ((shl = chcheck(l, q->lshape, q->rewrite & RLEFT)) == SRNOPE) 563 continue; 564 565 F2DEBUG(("findop lshape %s\n", srtyp[shl])); 566 F2WALK(l); 567 568 if ((shr = chcheck(r, q->rshape, q->rewrite & RRIGHT)) == SRNOPE) 569 continue; 570 571 F2DEBUG(("findop rshape %s\n", srtyp[shr])); 572 F2WALK(r); 573 574 /* Help register assignment after SSA by preferring */ 575 /* 2-op insns instead of 3-ops */ 576 if (xssa && (q->rewrite & RLEFT) == 0 && shl == SRDIR) 577 shl = SRREG; 578 579 if (q->needs & REWRITE) 580 break; /* Done here */ 581 582 if (lvl <= (shl + shr)) 583 continue; 584 lvl = shl + shr; 585 qq = q; 586 idx = ixp[i]; 587 gol = shl; 588 gor = shr; 589 } 590 if (lvl == 10) { 591 F2DEBUG(("findops failed\n")); 592 if (setbin(p)) 593 return FRETRY; 594 return FFAIL; 595 } 596 597 F2DEBUG(("findops entry %d(%s,%s)\n", idx, srtyp[gol], srtyp[gor])); 598 599 sh = -1; 600 601 #ifdef mach_pdp11 602 if (cookie == FORCC && p->n_op != AND) /* XXX - fix */ 603 cookie = INREGS; 604 #else 605 if (cookie == FORCC) 606 cookie = INREGS; 607 #endif 608 609 sh = shswitch(sh, p->n_left, qq->lshape, cookie, 610 qq->rewrite & RLEFT, gol); 611 sh = shswitch(sh, p->n_right, qq->rshape, cookie, 612 qq->rewrite & RRIGHT, gor); 613 614 if (sh == -1) { 615 if (cookie == FOREFF || cookie == FORCC) 616 sh = 0; 617 else 618 sh = ffs(cookie & qq->visit & INREGS)-1; 619 } 620 F2DEBUG(("findops: node %p sh %d (%s)\n", p, sh, prcook(1 << sh))); 621 p->n_su = MKIDX(idx, 0); 622 SCLASS(p->n_su, sh); 623 return sh; 624 } 625 626 /* 627 * Find the best relation op for matching the two trees it has. 628 * This is a sub-version of the function findops() above. 629 * The instruction with the lowest grading is emitted. 630 * 631 * Level assignment for priority: 632 * left right prio 633 * - - - 634 * direct direct 1 635 * direct OREG 2 # make oreg 636 * OREG direct 2 # make oreg 637 * OREG OREG 2 # make both oreg 638 * direct REG 3 # put in reg 639 * OREG REG 3 # put in reg, make oreg 640 * REG direct 3 # put in reg 641 * REG OREG 3 # put in reg, make oreg 642 * REG REG 4 # put both in reg 643 */ 644 int 645 relops(NODE *p) 646 { 647 extern int *qtable[]; 648 struct optab *q; 649 int i, shl = 0, shr = 0, sh; 650 NODE *l, *r; 651 int *ixp, idx = 0; 652 int lvl = 10, gol = 0, gor = 0; 653 654 F2DEBUG(("relops tree:\n")); 655 F2WALK(p); 656 657 l = getlr(p, 'L'); 658 r = getlr(p, 'R'); 659 ixp = qtable[p->n_op]; 660 for (i = 0; ixp[i] >= 0; i++) { 661 q = &table[ixp[i]]; 662 663 F2DEBUG(("relops: ixp %d\n", ixp[i])); 664 if (!acceptable(q)) /* target-dependent filter */ 665 continue; 666 667 if (ttype(l->n_type, q->ltype) == 0 || 668 ttype(r->n_type, q->rtype) == 0) 669 continue; /* Types must be correct */ 670 671 F2DEBUG(("relops got types\n")); 672 if ((shl = chcheck(l, q->lshape, 0)) == SRNOPE) 673 continue; 674 F2DEBUG(("relops lshape %d\n", shl)); 675 F2WALK(p); 676 if ((shr = chcheck(r, q->rshape, 0)) == SRNOPE) 677 continue; 678 F2DEBUG(("relops rshape %d\n", shr)); 679 F2WALK(p); 680 if (q->needs & REWRITE) 681 break; /* Done here */ 682 683 if (lvl <= (shl + shr)) 684 continue; 685 lvl = shl + shr; 686 idx = ixp[i]; 687 gol = shl; 688 gor = shr; 689 } 690 if (lvl == 10) { 691 F2DEBUG(("relops failed\n")); 692 if (setbin(p)) 693 return FRETRY; 694 return FFAIL; 695 } 696 F2DEBUG(("relops entry %d(%s %s)\n", idx, srtyp[gol], srtyp[gor])); 697 698 q = &table[idx]; 699 700 (void)shswitch(-1, p->n_left, q->lshape, INREGS, 701 q->rewrite & RLEFT, gol); 702 703 (void)shswitch(-1, p->n_right, q->rshape, INREGS, 704 q->rewrite & RRIGHT, gor); 705 706 sh = 0; 707 if (q->rewrite & RLEFT) 708 sh = ffs(q->lshape & INREGS)-1; 709 else if (q->rewrite & RRIGHT) 710 sh = ffs(q->rshape & INREGS)-1; 711 712 F2DEBUG(("relops: node %p\n", p)); 713 p->n_su = MKIDX(idx, 0); 714 SCLASS(p->n_su, sh); 715 return 0; 716 } 717 718 /* 719 * Find a matching assign op. 720 * 721 * Level assignment for priority: 722 * left right prio 723 * - - - 724 * direct direct 1 725 * direct REG 2 726 * direct OREG 3 727 * OREG direct 4 728 * OREG REG 5 729 * OREG OREG 6 730 */ 731 int 732 findasg(NODE *p, int cookie) 733 { 734 extern int *qtable[]; 735 struct optab *q; 736 int i, sh, shl, shr, lvl = 10; 737 NODE *l, *r; 738 int *ixp; 739 struct optab *qq = NULL; /* XXX gcc */ 740 int idx = 0, gol = 0, gor = 0; 741 742 shl = shr = 0; 743 744 F2DEBUG(("findasg tree: %s\n", prcook(cookie))); 745 F2WALK(p); 746 747 ixp = qtable[p->n_op]; 748 l = getlr(p, 'L'); 749 r = getlr(p, 'R'); 750 for (i = 0; ixp[i] >= 0; i++) { 751 q = &table[ixp[i]]; 752 753 F2DEBUG(("findasg: ixp %d\n", ixp[i])); 754 if (!acceptable(q)) /* target-dependent filter */ 755 continue; 756 757 if (ttype(l->n_type, q->ltype) == 0 || 758 ttype(r->n_type, q->rtype) == 0) 759 continue; /* Types must be correct */ 760 761 if ((cookie & q->visit) == 0) 762 continue; /* must get a result */ 763 764 F2DEBUG(("findasg got types\n")); 765 #ifdef mach_pdp11 /* XXX - check for other targets too */ 766 if (p->n_op == STASG && ISPTR(l->n_type)) { 767 /* Accept lvalue to be in register */ 768 /* if struct assignment is given a pointer */ 769 if ((shl = chcheck(l, q->lshape, 770 q->rewrite & RLEFT)) == SRNOPE) 771 continue; 772 } else 773 #endif 774 { 775 if ((shl = tshape(l, q->lshape)) == SRNOPE) 776 continue; 777 if (shl == SRREG) 778 continue; 779 } 780 781 F2DEBUG(("findasg lshape %d\n", shl)); 782 F2WALK(l); 783 784 if ((shr = chcheck(r, q->rshape, q->rewrite & RRIGHT)) == SRNOPE) 785 continue; 786 787 F2DEBUG(("findasg rshape %d\n", shr)); 788 F2WALK(r); 789 if (q->needs & REWRITE) 790 break; /* Done here */ 791 792 if (lvl <= (shl + shr)) 793 continue; 794 795 lvl = shl + shr; 796 qq = q; 797 idx = ixp[i]; 798 gol = shl; 799 gor = shr; 800 } 801 802 if (lvl == 10) { 803 F2DEBUG(("findasg failed\n")); 804 if (setasg(p, cookie)) 805 return FRETRY; 806 return FFAIL; 807 } 808 F2DEBUG(("findasg entry %d(%s,%s)\n", idx, srtyp[gol], srtyp[gor])); 809 810 sh = -1; 811 sh = shswitch(sh, p->n_left, qq->lshape, cookie, 812 qq->rewrite & RLEFT, gol); 813 814 sh = shswitch(sh, p->n_right, qq->rshape, cookie, 815 qq->rewrite & RRIGHT, gor); 816 817 #ifdef mach_pdp11 /* XXX all targets? */ 818 lvl = 0; 819 if (cookie == FOREFF) 820 lvl = RVEFF, sh = 0; 821 else if (cookie == FORCC) 822 lvl = RVCC, sh = 0; 823 else if (sh == -1) { 824 sh = ffs(cookie & qq->visit & INREGS)-1; 825 #ifdef PCC_DEBUG 826 if (sh == -1) 827 comperr("findasg bad shape"); 828 #endif 829 SCLASS(lvl,sh); 830 } else 831 SCLASS(lvl,sh); 832 p->n_su = MKIDX(idx, lvl); 833 #else 834 if (sh == -1) { 835 if (cookie == FOREFF) 836 sh = 0; 837 else 838 sh = ffs(cookie & qq->visit & INREGS)-1; 839 } 840 F2DEBUG(("findasg: node %p class %d\n", p, sh)); 841 842 p->n_su = MKIDX(idx, 0); 843 SCLASS(p->n_su, sh); 844 #endif /* mach_pdp11 */ 845 #ifdef FINDMOPS 846 p->n_su &= ~ISMOPS; 847 #endif 848 return sh; 849 } 850 851 /* 852 * Search for an UMUL table entry that can turn an indirect node into 853 * a move from an OREG. 854 */ 855 int 856 findumul(NODE *p, int cookie) 857 { 858 extern int *qtable[]; 859 struct optab *q = NULL; /* XXX gcc */ 860 int i, shl = 0, shr = 0, sh; 861 int *ixp; 862 863 F2DEBUG(("findumul p %p (%s)\n", p, prcook(cookie))); 864 F2WALK(p); 865 866 ixp = qtable[p->n_op]; 867 for (i = 0; ixp[i] >= 0; i++) { 868 q = &table[ixp[i]]; 869 870 F2DEBUG(("findumul: ixp %d\n", ixp[i])); 871 if (!acceptable(q)) /* target-dependent filter */ 872 continue; 873 874 if ((q->visit & cookie) == 0) 875 continue; /* wrong registers */ 876 877 if (ttype(p->n_type, q->rtype) == 0) 878 continue; /* Types must be correct */ 879 880 881 F2DEBUG(("findumul got types, rshape %s\n", prcook(q->rshape))); 882 /* 883 * Try to create an OREG of the node. 884 * Fake left even though it's right node, 885 * to be sure of conversion if going down left. 886 */ 887 if ((shl = chcheck(p, q->rshape, 0)) == SRNOPE) 888 continue; 889 890 shr = 0; 891 892 if (q->needs & REWRITE) 893 break; /* Done here */ 894 895 F2DEBUG(("findumul got shape %s\n", srtyp[shl])); 896 897 break; /* XXX search better matches */ 898 } 899 if (ixp[i] < 0) { 900 F2DEBUG(("findumul failed\n")); 901 if (setuni(p, cookie)) 902 return FRETRY; 903 return FFAIL; 904 } 905 F2DEBUG(("findumul entry %d(%s %s)\n", ixp[i], srtyp[shl], srtyp[shr])); 906 907 sh = shswitch(-1, p, q->rshape, cookie, q->rewrite & RLEFT, shl); 908 if (sh == -1) 909 sh = ffs(cookie & q->visit & INREGS)-1; 910 911 F2DEBUG(("findumul: node %p (%s)\n", p, prcook(1 << sh))); 912 p->n_su = MKIDX(ixp[i], 0); 913 SCLASS(p->n_su, sh); 914 return sh; 915 } 916 917 /* 918 * Find a leaf type node that puts the value into a register. 919 */ 920 int 921 findleaf(NODE *p, int cookie) 922 { 923 extern int *qtable[]; 924 struct optab *q = NULL; /* XXX gcc */ 925 int i, sh; 926 int *ixp; 927 928 F2DEBUG(("findleaf p %p (%s)\n", p, prcook(cookie))); 929 F2WALK(p); 930 931 ixp = qtable[p->n_op]; 932 for (i = 0; ixp[i] >= 0; i++) { 933 q = &table[ixp[i]]; 934 935 F2DEBUG(("findleaf: ixp %d\n", ixp[i])); 936 if (!acceptable(q)) /* target-dependent filter */ 937 continue; 938 if ((q->visit & cookie) == 0) 939 continue; /* wrong registers */ 940 941 if (ttype(p->n_type, q->rtype) == 0 || 942 ttype(p->n_type, q->ltype) == 0) 943 continue; /* Types must be correct */ 944 945 F2DEBUG(("findleaf got types, rshape %s\n", prcook(q->rshape))); 946 947 if (chcheck(p, q->rshape, 0) != SRDIR) 948 continue; 949 950 if (q->needs & REWRITE) 951 break; /* Done here */ 952 953 break; 954 } 955 if (ixp[i] < 0) { 956 F2DEBUG(("findleaf failed\n")); 957 if (setuni(p, cookie)) 958 return FRETRY; 959 return FFAIL; 960 } 961 F2DEBUG(("findleaf entry %d\n", ixp[i])); 962 963 sh = ffs(cookie & q->visit & INREGS)-1; 964 F2DEBUG(("findleaf: node %p (%s)\n", p, prcook(1 << sh))); 965 p->n_su = MKIDX(ixp[i], 0); 966 SCLASS(p->n_su, sh); 967 return sh; 968 } 969 970 /* 971 * Find a UNARY op that satisfy the needs. 972 * For now, the destination is always a register. 973 * Both source and dest types must match, but only source (left) 974 * shape is of interest. 975 */ 976 int 977 finduni(NODE *p, int cookie) 978 { 979 extern int *qtable[]; 980 struct optab *q; 981 NODE *l, *r; 982 int i, shl = 0, num = 4; 983 int *ixp, idx = 0; 984 int sh; 985 986 F2DEBUG(("finduni tree: %s\n", prcook(cookie))); 987 F2WALK(p); 988 989 l = getlr(p, 'L'); 990 if (p->n_op == CALL || p->n_op == FORTCALL || p->n_op == STCALL) 991 r = p; 992 else 993 r = getlr(p, 'R'); 994 ixp = qtable[p->n_op]; 995 for (i = 0; ixp[i] >= 0; i++) { 996 q = &table[ixp[i]]; 997 998 F2DEBUG(("finduni: ixp %d\n", ixp[i])); 999 if (!acceptable(q)) /* target-dependent filter */ 1000 continue; 1001 1002 if (ttype(l->n_type, q->ltype) == 0) 1003 continue; /* Type must be correct */ 1004 1005 F2DEBUG(("finduni got left type\n")); 1006 if (ttype(r->n_type, q->rtype) == 0) 1007 continue; /* Type must be correct */ 1008 1009 F2DEBUG(("finduni got types\n")); 1010 if ((shl = chcheck(l, q->lshape, q->rewrite & RLEFT)) == SRNOPE) 1011 continue; 1012 1013 F2DEBUG(("finduni got shapes %d\n", shl)); 1014 1015 if ((cookie & q->visit) == 0) /* check correct return value */ 1016 continue; /* XXX - should check needs */ 1017 1018 /* avoid clobbering of longlived regs */ 1019 /* let register allocator coalesce */ 1020 if ((q->rewrite & RLEFT) && (shl == SRDIR) /* && isreg(l) */) 1021 shl = SRREG; 1022 1023 F2DEBUG(("finduni got cookie\n")); 1024 if (q->needs & REWRITE) 1025 break; /* Done here */ 1026 1027 if (shl >= num) 1028 continue; 1029 num = shl; 1030 idx = ixp[i]; 1031 1032 if (shl == SRDIR) 1033 break; 1034 } 1035 1036 if (num == 4) { 1037 F2DEBUG(("finduni failed\n")); 1038 } else 1039 F2DEBUG(("finduni entry %d(%s)\n", idx, srtyp[num])); 1040 1041 if (num == 4) { 1042 if (setuni(p, cookie)) 1043 return FRETRY; 1044 return FFAIL; 1045 } 1046 q = &table[idx]; 1047 1048 sh = shswitch(-1, p->n_left, q->lshape, cookie, 1049 q->rewrite & RLEFT, num); 1050 if (sh == -1) 1051 sh = ffs(cookie & q->visit & INREGS)-1; 1052 if (sh == -1) 1053 sh = 0; 1054 1055 F2DEBUG(("finduni: node %p (%s)\n", p, prcook(1 << sh))); 1056 p->n_su = MKIDX(idx, 0); 1057 SCLASS(p->n_su, sh); 1058 return sh; 1059 } 1060 1061 #ifdef FINDMOPS 1062 /* 1063 * Try to find constructs like "a = a + 1;" and match them together 1064 * with instructions like "incl a" or "addl $1,a". 1065 * 1066 * Level assignment for priority: 1067 * left right prio 1068 * - - - 1069 * direct direct 1 1070 * direct REG 2 1071 * direct OREG 3 1072 * OREG direct 4 1073 * OREG REG 5 1074 * OREG OREG 6 1075 */ 1076 int 1077 findmops(NODE *p, int cookie) 1078 { 1079 extern int *qtable[]; 1080 struct optab *q; 1081 int i, sh, shl, shr, lvl = 10; 1082 NODE *l, *r; 1083 int *ixp; 1084 struct optab *qq = NULL; /* XXX gcc */ 1085 int idx = 0, gol = 0, gor = 0; 1086 1087 shl = shr = 0; 1088 1089 F2DEBUG(("findmops tree: %s\n", prcook(cookie))); 1090 F2WALK(p); 1091 1092 l = getlr(p, 'L'); 1093 r = getlr(p, 'R'); 1094 /* See if this is a usable tree to work with */ 1095 /* Currently only check for leaves */ 1096 if (optype(r->n_op) != BITYPE || treecmp(l, r->n_left) == 0) 1097 return FFAIL; 1098 1099 F2DEBUG(("findmops is useable\n")); 1100 1101 /* We can try to find a match. Use right op */ 1102 ixp = qtable[r->n_op]; 1103 l = getlr(r, 'L'); 1104 r = getlr(r, 'R'); 1105 1106 for (i = 0; ixp[i] >= 0; i++) { 1107 q = &table[ixp[i]]; 1108 1109 F2DEBUG(("findmops: ixp %d\n", ixp[i])); 1110 if (!acceptable(q)) /* target-dependent filter */ 1111 continue; 1112 1113 if (ttype(l->n_type, q->ltype) == 0 || 1114 ttype(r->n_type, q->rtype) == 0) 1115 continue; /* Types must be correct */ 1116 1117 F2DEBUG(("findmops got types\n")); 1118 1119 switch (cookie) { 1120 case FOREFF: 1121 if ((q->visit & FOREFF) == 0) 1122 continue; /* Not only for side effects */ 1123 break; 1124 case FORCC: 1125 if ((q->visit & FORCC) == 0) 1126 continue; /* Not only for side effects */ 1127 break; 1128 default: 1129 if ((cookie & q->visit) == 0) 1130 continue; /* Won't match requested shape */ 1131 if (((cookie & INREGS & q->lshape) == 0) || !isreg(l)) 1132 continue; /* Bad return register */ 1133 break; 1134 } 1135 F2DEBUG(("findmops cookie\n")); 1136 1137 /* 1138 * left shape must match left node. 1139 */ 1140 if ((shl = tshape(l, q->lshape)) != SRDIR && (shl != SROREG)) 1141 continue; 1142 1143 F2DEBUG(("findmops lshape %s\n", srtyp[shl])); 1144 F2WALK(l); 1145 1146 if ((shr = chcheck(r, q->rshape, 0)) == SRNOPE) 1147 continue; 1148 1149 F2DEBUG(("findmops rshape %s\n", srtyp[shr])); 1150 1151 /* 1152 * Only allow RLEFT. XXX 1153 */ 1154 if ((q->rewrite & (RLEFT|RRIGHT)) != RLEFT) 1155 continue; 1156 1157 F2DEBUG(("rewrite OK\n")); 1158 1159 F2WALK(r); 1160 if (q->needs & REWRITE) 1161 break; /* Done here */ 1162 1163 if (lvl <= (shl + shr)) 1164 continue; 1165 1166 lvl = shl + shr; 1167 qq = q; 1168 idx = ixp[i]; 1169 gol = shl; 1170 gor = shr; 1171 } 1172 1173 if (lvl == 10) 1174 return FFAIL; 1175 F2DEBUG(("findmops entry %d(%s,%s)\n", idx, srtyp[gol], srtyp[gor])); 1176 1177 /* 1178 * Now we're here and have a match. left is semi-direct and 1179 * right may be anything. 1180 */ 1181 1182 sh = -1; 1183 sh = shswitch(sh, p->n_left, qq->lshape, cookie, 1184 qq->rewrite & RLEFT, gol); 1185 sh = shswitch(sh, r, qq->rshape, cookie, 0, gor); 1186 1187 if (sh == -1) { 1188 if (cookie & (FOREFF|FORCC)) 1189 sh = 0; 1190 else 1191 sh = ffs(cookie & qq->visit & INREGS)-1; 1192 } 1193 F2DEBUG(("findmops done: node %p class %d\n", p, sh)); 1194 1195 /* Trickery: Set table index on assign to op instead */ 1196 /* gencode() will remove useless nodes */ 1197 p->n_su = MKIDX(idx, 0); 1198 p->n_su |= ISMOPS; /* XXX tell gencode to reduce the right tree */ 1199 SCLASS(p->n_su, sh); 1200 1201 return sh; 1202 } 1203 1204 /* 1205 * Compare two trees; return 1 if equal and 0 if not. 1206 */ 1207 int 1208 treecmp(NODE *p1, NODE *p2) 1209 { 1210 if (p1->n_op != p2->n_op) 1211 return 0; 1212 1213 switch (p1->n_op) { 1214 case SCONV: 1215 case UMUL: 1216 return treecmp(p1->n_left, p2->n_left); 1217 1218 case OREG: 1219 if (getlval(p1) != getlval(p2) || p1->n_rval != p2->n_rval) 1220 return 0; 1221 break; 1222 1223 case NAME: 1224 case ICON: 1225 if (strcmp(p1->n_name, p2->n_name)) 1226 return 0; 1227 /* FALLTHROUGH */ 1228 if (getlval(p1) != getlval(p2)) 1229 return 0; 1230 break; 1231 1232 case TEMP: 1233 #ifdef notyet 1234 /* SSA will put assignment in separate register */ 1235 /* Help out by accepting different regs here */ 1236 if (xssa) 1237 break; 1238 #endif 1239 case REG: 1240 if (p1->n_rval != p2->n_rval) 1241 return 0; 1242 break; 1243 case LS: 1244 case RS: 1245 case PLUS: 1246 case MINUS: 1247 case MUL: 1248 case DIV: 1249 if (treecmp(p1->n_left, p2->n_left) == 0 || 1250 treecmp(p1->n_right, p2->n_right) == 0) 1251 return 0; 1252 break; 1253 1254 default: 1255 return 0; 1256 } 1257 return 1; 1258 } 1259 #endif 1260
Indexes created Thu Jun 11 00:25:07 UTC 2026