compilers/pcc/pcc-1.0.0/mip/match.c

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