2.11BSD#431 - /usr/src/lib/mip/match.c

   1: #if !defined(lint) && defined(DOSCCS)
   2: static char *sccsid ="@(#)match.c	4.4.1 (2.11BSD GTE) 1/17/95";
   3: #endif lint
   4: 
   5: # include "pass2.h"
   6: 
   7: # ifdef WCARD1
   8: # ifdef WCARD2
   9: # define NOINDIRECT
  10: # endif
  11: # endif
  12: 
  13: extern vdebug;
  14: 
  15: int fldsz, fldshf;
  16: 
  17: static int mamask[] = { /* masks for matching dope with shapes */
  18:     SIMPFLG,        /* OPSIMP */
  19:     SIMPFLG|ASGFLG,     /* ASG OPSIMP */
  20:     COMMFLG,    /* OPCOMM */
  21:     COMMFLG|ASGFLG, /* ASG OPCOMM */
  22:     MULFLG,     /* OPMUL */
  23:     MULFLG|ASGFLG,  /* ASG OPMUL */
  24:     DIVFLG,     /* OPDIV */
  25:     DIVFLG|ASGFLG,  /* ASG OPDIV */
  26:     UTYPE,      /* OPUNARY */
  27:     TYFLG,      /* ASG OPUNARY is senseless */
  28:     LTYPE,      /* OPLEAF */
  29:     TYFLG,      /* ASG OPLEAF is senseless */
  30:     0,      /* OPANY */
  31:     ASGOPFLG|ASGFLG,    /* ASG OPANY */
  32:     LOGFLG,     /* OPLOG */
  33:     TYFLG,      /* ASG OPLOG is senseless */
  34:     FLOFLG,     /* OPFLOAT */
  35:     FLOFLG|ASGFLG,  /* ASG OPFLOAT */
  36:     SHFFLG,     /* OPSHFT */
  37:     SHFFLG|ASGFLG,  /* ASG OPSHIFT */
  38:     SPFLG,      /* OPLTYPE */
  39:     TYFLG,      /* ASG OPLTYPE is senseless */
  40:     };
  41: 
  42: int sdebug = 0;
  43: 
  44: tshape( p, shape ) NODE *p; {
  45:     /* return true if shape is appropriate for the node p
  46: 	   side effect for SFLD is to set up fldsz,etc */
  47:     register o, mask;
  48: 
  49:     o = p->in.op;
  50: 
  51: # ifndef BUG3
  52:     if( sdebug ){
  53:         printf( "tshape( %o, ", p );
  54:         prcook( shape );
  55:         printf( " ) op = %s\n", opst[o] );
  56:         }
  57: # endif
  58: 
  59:     if( shape & SPECIAL ){
  60: 
  61:         switch( shape ){
  62: 
  63:         case SZERO:
  64:         case SONE:
  65:         case SMONE:
  66:         case SSCON:
  67:         case SCCON:
  68:             if( o != ICON || p->in.name[0] ) return(0);
  69:             if( p->tn.lval == 0 && shape == SZERO ) return(1);
  70:             else if( p->tn.lval == 1 && shape == SONE ) return(1);
  71:             else if( p->tn.lval == -1 && shape == SMONE ) return(1);
  72:             else if( p->tn.lval > -129 && p->tn.lval < 128 && shape == SCCON ) return(1);
  73:             else if( p->tn.lval > -32769 && p->tn.lval < 32768 && shape == SSCON ) return(1);
  74:             else return(0);
  75: 
  76:         case SSOREG:    /* non-indexed OREG */
  77:             if( o == OREG && !R2TEST(p->tn.rval) ) return(1);
  78:             else return(0);
  79: 
  80:         default:
  81: # ifdef MULTILEVEL
  82:             if( shape & MULTILEVEL )
  83:                 return( mlmatch(p,shape,0) );
  84:             else
  85: # endif
  86:             return( special( p, shape ) );
  87:             }
  88:         }
  89: 
  90:     if( shape & SANY ) return(1);
  91: 
  92:     if( (shape&INTEMP) && shtemp(p) ) return(1);
  93: 
  94:     if( (shape&SWADD) && (o==NAME||o==OREG) ){
  95:         if( BYTEOFF(p->tn.lval) ) return(0);
  96:         }
  97: 
  98: # ifdef WCARD1
  99:     if( shape & WCARD1 )
 100:         return( wcard1(p) & shape );
 101: # endif
 102: 
 103: # ifdef WCARD2
 104:     if( shape & WCARD2 )
 105:         return( wcard2(p) & shape );
 106: # endif
 107:     switch( o ){
 108: 
 109:     case NAME:
 110:         return( shape&SNAME );
 111:     case ICON:
 112:         mask = SCON;
 113:         return( shape & mask );
 114: 
 115:     case FLD:
 116:         if( shape & SFLD ){
 117:             if( !flshape( p->in.left ) ) return(0);
 118:             /* it is a FIELD shape; make side-effects */
 119:             o = p->tn.rval;
 120:             fldsz = UPKFSZ(o);
 121: # ifdef RTOLBYTES
 122:             fldshf = UPKFOFF(o);
 123: # else
 124:             fldshf = SZINT - fldsz - UPKFOFF(o);
 125: # endif
 126:             return(1);
 127:             }
 128:         return(0);
 129: 
 130:     case CCODES:
 131:         return( shape&SCC );
 132: 
 133:     case REG:
 134:         /* distinctions:
 135: 		SAREG	any scalar register
 136: 		STAREG	any temporary scalar register
 137: 		SBREG	any lvalue (index) register
 138: 		STBREG	any temporary lvalue register
 139: 		*/
 140:         mask = isbreg( p->tn.rval ) ? SBREG : SAREG;
 141:         if( istreg( p->tn.rval ) && busy[p->tn.rval]<=1 ) mask |= mask==SAREG ? STAREG : STBREG;
 142:         return( shape & mask );
 143: 
 144:     case OREG:
 145:         return( shape & SOREG );
 146: 
 147: # ifndef NOINDIRECT
 148:     case UNARY MUL:
 149:         /* return STARNM or STARREG or 0 */
 150:         return( shumul(p->in.left) & shape );
 151: # endif
 152: 
 153:         }
 154: 
 155:     return(0);
 156:     }
 157: 
 158: int tdebug = 0;
 159: 
 160: ttype( t, tword ) TWORD t; {
 161:     /* does the type t match tword */
 162: 
 163:     if( tword & TANY ) return(1);
 164: 
 165:     if( t == UNDEF ) t=INT; /* void functions eased thru tables */
 166: # ifndef BUG3
 167:     if( tdebug ){
 168:         printf( "ttype( %o, %o )\n", t, tword );
 169:         }
 170: # endif
 171:     if( ISPTR(t) && (tword&TPTRTO) ) {
 172:         do {
 173:             t = DECREF(t);
 174:         } while ( ISARY(t) );
 175:             /* arrays that are left are usually only
 176: 			   in structure references... */
 177:         return( ttype( t, tword&(~TPTRTO) ) );
 178:         }
 179:     if( t != BTYPE(t) ) return( tword & TPOINT ); /* TPOINT means not simple! */
 180:     if( tword & TPTRTO ) return(0);
 181: 
 182:     switch( t ){
 183: 
 184:     case CHAR:
 185:         return( tword & TCHAR );
 186:     case SHORT:
 187:         return( tword & TSHORT );
 188:     case STRTY:
 189:     case UNIONTY:
 190:         return( tword & TSTRUCT );
 191:     case INT:
 192:         return( tword & TINT );
 193:     case UNSIGNED:
 194:         return( tword & TUNSIGNED );
 195:     case USHORT:
 196:         return( tword & TUSHORT );
 197:     case UCHAR:
 198:         return( tword & TUCHAR );
 199:     case ULONG:
 200:         return( tword & TULONG );
 201:     case LONG:
 202:         return( tword & TLONG );
 203:     case FLOAT:
 204:         return( tword & TFLOAT );
 205:     case DOUBLE:
 206:         return( tword & TDOUBLE );
 207:         }
 208: 
 209:     return(0);
 210:     }
 211: 
 212: struct optab *rwtable;
 213: 
 214: struct optab *opptr[DSIZE];
 215: 
 216: setrew(){
 217:     /* set rwtable to first value which allows rewrite */
 218:     register struct optab *q;
 219:     register int i;
 220: 
 221: # ifdef MULTILEVEL
 222:     /* also initialize multi-level tree links */
 223:     mlinit();
 224: # endif
 225: 
 226:     for( q = table; q->op != FREE; ++q ){
 227:         if( q->needs == REWRITE ){
 228:             rwtable = q;
 229:             goto more;
 230:             }
 231:         }
 232:     cerror("bad setrew" );
 233: 
 234: 
 235:     more:
 236:     for( i=0; i<DSIZE; ++i ){
 237:         if( dope[i] ){ /* there is an op... */
 238:             for( q=table; q->op != FREE; ++q ){
 239:                 /*  beware; things like LTYPE that match
 240: 				    multiple things in the tree must
 241: 				    not try to look at the NIL at this
 242: 				    stage of things!  Put something else
 243: 				    first in table.c  */
 244:                 /* at one point, the operator matching was 15% of the
 245: 				    total comile time; thus, the function
 246: 				    call that was here was removed...
 247: 				*/
 248: 
 249:                 if( q->op < OPSIMP ){
 250:                     if( q->op==i ) break;
 251:                     }
 252:                 else {
 253:                     register opmtemp;
 254:                     if((opmtemp=mamask[q->op - OPSIMP])&SPFLG){
 255:                         if( i==NAME || i==ICON || i==OREG ) break;
 256:                         else if( shltype( i, NIL ) ) break;
 257:                         }
 258:                     else if( (dope[i]&(opmtemp|ASGFLG)) == opmtemp ) break;
 259:                     }
 260:                 }
 261:             opptr[i] = q;
 262:             }
 263:         }
 264:     }
 265: 
 266: match( p, cookie ) NODE *p; {
 267:     /* called by: order, gencall
 268: 	   look for match in table and generate code if found unless
 269: 	   entry specified REWRITE.
 270: 	   returns MDONE, MNOPE, or rewrite specification from table */
 271: 
 272:     register struct optab *q;
 273:     register NODE *r;
 274: 
 275:     rcount();
 276:     if( cookie == FORREW ) q = rwtable;
 277:     else q = opptr[p->in.op];
 278: 
 279:     for( ; q->op != FREE; ++q ){
 280: 
 281:         /* at one point the call that was here was over 15% of the total time;
 282: 		    thus the function call was expanded inline */
 283:         if( q->op < OPSIMP ){
 284:             if( q->op!=p->in.op ) continue;
 285:             }
 286:         else {
 287:             register opmtemp;
 288:             if((opmtemp=mamask[q->op - OPSIMP])&SPFLG){
 289:                 if( p->in.op!=NAME && p->in.op!=ICON && p->in.op!= OREG &&
 290:                     ! shltype( p->in.op, p ) ) continue;
 291:                 }
 292:             else if( (dope[p->in.op]&(opmtemp|ASGFLG)) != opmtemp ) continue;
 293:             }
 294: 
 295:         if( !(q->visit & cookie ) ) continue;
 296:         r = getlr( p, 'L' );            /* see if left child matches */
 297:         if( !tshape( r, q->lshape ) ) continue;
 298:         if( !ttype( r->in.type, q->ltype ) ) continue;
 299:         r = getlr( p, 'R' );            /* see if right child matches */
 300:         if( !tshape( r, q->rshape ) ) continue;
 301:         if( !ttype( r->in.type, q->rtype ) ) continue;
 302: 
 303:             /* REWRITE means no code from this match but go ahead
 304: 			   and rewrite node to help future match */
 305:         if( q->needs & REWRITE ) return( q->rewrite );
 306:         if( !allo( p, q ) ) continue;           /* if can't generate code, skip entry */
 307: 
 308:         /* resources are available */
 309: 
 310:         expand( p, cookie, q->cstring );        /* generate code */
 311:         reclaim( p, q->rewrite, cookie );
 312: 
 313:         return(MDONE);
 314: 
 315:         }
 316: 
 317:     return(MNOPE);
 318:     }
 319: 
 320: int rtyflg = 0;
 321: 
 322: expand( p, cookie, cp ) NODE *p;  register char *cp; {
 323:     /* generate code by interpreting table entry */
 324: 
 325: # ifdef NEWZZZ
 326:     register char c;
 327: # endif
 328:     CONSZ val;
 329: 
 330:     rtyflg = 0;
 331: 
 332:     for( ; *cp; ++cp ){
 333:         switch( *cp ){
 334: 
 335:         default:
 336:             PUTCHAR( *cp );
 337:             continue;  /* this is the usual case... */
 338: 
 339:         case 'T':
 340:             /* rewrite register type is suppressed */
 341:             rtyflg = 1;
 342:             continue;
 343: 
 344:         case 'Z':  /* special machine dependent operations */
 345: # ifdef NEWZZZ
 346:             switch( c = *++cp ) {
 347: 
 348:             case '1':
 349:             case '2':
 350:             case '3':
 351:             case 'R':
 352:             case 'L':   /* get down first */
 353:                 zzzcode( getlr( p, c ), *++cp );
 354:                 break;
 355:             default:   /* normal zzzcode processing otherwise */
 356:                 zzzcode( p, c );
 357:                 break;
 358:             }
 359: # else
 360:             zzzcode( p, *++cp );
 361: # endif
 362:             continue;
 363: 
 364:         case 'F':  /* this line deleted if FOREFF is active */
 365:             if( cookie & FOREFF ) while( *++cp != '\n' ) ; /* VOID */
 366:             continue;
 367: 
 368:         case 'S':  /* field size */
 369:             printf( "%d", fldsz );
 370:             continue;
 371: 
 372:         case 'H':  /* field shift */
 373:             printf( "%d", fldshf );
 374:             continue;
 375: 
 376:         case 'M':  /* field mask */
 377:         case 'N':  /* complement of field mask */
 378:             val = 1;
 379:             val <<= fldsz;
 380:             --val;
 381:             val <<= fldshf;
 382:             adrcon( *cp=='M' ? val : ~val );
 383:             continue;
 384: 
 385:         case 'L':  /* output special label field */
 386:             printf( "%d", p->bn.label );
 387:             continue;
 388: 
 389:         case 'O':  /* opcode string */
 390:             hopcode( *++cp, p->in.op );
 391:             continue;
 392: 
 393:         case 'B':  /* byte offset in word */
 394:             val = getlr(p,*++cp)->tn.lval;
 395:             val = BYTEOFF(val);
 396:             printf( CONFMT, val );
 397:             continue;
 398: 
 399:         case 'C': /* for constant value only */
 400:             conput( getlr( p, *++cp ) );
 401:             continue;
 402: 
 403:         case 'I': /* in instruction */
 404:             insput( getlr( p, *++cp ) );
 405:             continue;
 406: 
 407:         case 'A': /* address of */
 408:             adrput( getlr( p, *++cp ) );
 409:             continue;
 410: 
 411:         case 'U': /* for upper half of address, only */
 412:             upput( getlr( p, *++cp ) );
 413:             continue;
 414: 
 415:             }
 416: 
 417:         }
 418: 
 419:     }
 420: 
 421: NODE *
 422: getlr( p, c ) NODE *p; {
 423: 
 424:     /* return the pointer to the left or right side of p, or p itself,
 425: 	   depending on the optype of p */
 426: 
 427:     switch( c ) {
 428: 
 429:     case '1':
 430:     case '2':
 431:     case '3':
 432:         return( &resc[c-'1'] );
 433: 
 434:     case 'L':
 435:         return( optype( p->in.op ) == LTYPE ? p : p->in.left );
 436: 
 437:     case 'R':
 438:         return( optype( p->in.op ) != BITYPE ? p : p->in.right );
 439: 
 440:         }
 441:     cerror("bad getlr: %c", c );
 442:     /* NOTREACHED */
 443:     }
 444: # ifdef MULTILEVEL
 445: 
 446: union mltemplate{
 447:     struct ml_head{
 448:         int tag; /* identifies class of tree */
 449:         int subtag; /* subclass of tree */
 450:         union mltemplate * nexthead; /* linked by mlinit() */
 451:         } mlhead;
 452:     struct ml_node{
 453:         int op; /* either an operator or op description */
 454:         int nshape; /* shape of node */
 455:         /* both op and nshape must match the node.
 456: 		 * where the work is to be done entirely by
 457: 		 * op, nshape can be SANY, visa versa, op can
 458: 		 * be OPANY.
 459: 		 */
 460:         int ntype; /* type descriptor from mfile2 */
 461:         } mlnode;
 462:     };
 463: 
 464: # define MLSZ 30
 465: 
 466: extern union mltemplate mltree[];
 467: int mlstack[MLSZ];
 468: int *mlsp; /* pointing into mlstack */
 469: NODE * ststack[MLSZ];
 470: NODE **stp; /* pointing into ststack */
 471: 
 472: mlinit(){
 473:     union mltemplate **lastlink;
 474:     register union mltemplate *n;
 475:     register mlop;
 476: 
 477:     lastlink = &(mltree[0].nexthead);
 478:     n = &mltree[0];
 479:     for( ; (n++)->mlhead.tag != 0;
 480:         *lastlink = ++n, lastlink = &(n->mlhead.nexthead) ){
 481: # ifndef BUG3
 482:         if( vdebug )printf("mlinit: %d\n",(n-1)->mlhead.tag);
 483: # endif
 484:     /* wander thru a tree with a stack finding
 485: 	 * its structure so the next header can be located.
 486: 	 */
 487:         mlsp = mlstack;
 488: 
 489:         for( ;; ++n ){
 490:             if( (mlop = n->mlnode.op) < OPSIMP ){
 491:                 switch( optype(mlop) ){
 492: 
 493:                     default:
 494:                         cerror("(1)unknown opcode: %o",mlop);
 495:                     case BITYPE:
 496:                         goto binary;
 497:                     case UTYPE:
 498:                         break;
 499:                     case LTYPE:
 500:                         goto leaf;
 501:                     }
 502:                 }
 503:             else{
 504:                 if( mamask[mlop-OPSIMP] &
 505:                     (SIMPFLG|COMMFLG|MULFLG|DIVFLG|LOGFLG|FLOFLG|SHFFLG) ){
 506:                 binary:
 507:                     *mlsp++ = BITYPE;
 508:                     }
 509:                 else if( ! (mamask[mlop-OPSIMP] & UTYPE) ){/* includes OPANY */
 510: 
 511:                 leaf:
 512:                     if( mlsp == mlstack )
 513:                         goto tree_end;
 514:                     else if ( *--mlsp != BITYPE )
 515:                         cerror("(1)bad multi-level tree descriptor around mltree[%d]",
 516:                         n-mltree);
 517:                     }
 518:                 }
 519:             }
 520:         tree_end: /* n points to final leaf */
 521:         ;
 522:         }
 523: # ifndef BUG3
 524:         if( vdebug > 3 ){
 525:             printf("mltree={\n");
 526:             for( n= &(mltree[0]); n->mlhead.tag != 0; ++n)
 527:                 printf("%o: %d, %d, %o,\n",n,
 528:                 n->mlhead.tag,n->mlhead.subtag,n->mlhead.nexthead);
 529:             printf("	}\n");
 530:             }
 531: # endif
 532:     }
 533: 
 534: mlmatch( subtree, target, subtarget ) NODE * subtree; int target,subtarget;{
 535:     /*
 536: 	 * does subtree match a multi-level tree with
 537: 	 * tag "target"?  Return zero on failure,
 538: 	 * non-zero subtag on success (or MDONE if
 539: 	 * there is a zero subtag field).
 540: 	 */
 541:     union mltemplate *head; /* current template header */
 542:     register union mltemplate *n; /* node being matched */
 543:     NODE * st; /* subtree being matched */
 544:     register int mlop;
 545: 
 546: # ifndef BUG3
 547:     if( vdebug ) printf("mlmatch(%o,%d)\n",subtree,target);
 548: # endif
 549:     for( head = &(mltree[0]); head->mlhead.tag != 0;
 550:         head=head->mlhead.nexthead){
 551: # ifndef BUG3
 552:         if( vdebug > 1 )printf("mlmatch head(%o) tag(%d)\n",
 553:             head->mlhead.tag);
 554: # endif
 555:         if( head->mlhead.tag != target )continue;
 556:         if( subtarget && head->mlhead.subtag != subtarget)continue;
 557: # ifndef BUG3
 558:         if( vdebug ) printf("mlmatch for %d\n",target);
 559: # endif
 560: 
 561:         /* potential for match */
 562: 
 563:         n = head + 1;
 564:         st = subtree;
 565:         stp = ststack;
 566:         mlsp = mlstack;
 567:         /* compare n->op, ->nshape, ->ntype to
 568: 		 * the subtree node st
 569: 		 */
 570:         for( ;; ++n ){ /* for each node in multi-level template */
 571:             /* opmatch */
 572:             if( n->op < OPSIMP ){
 573:                 if( st->op != n->op )break;
 574:                 }
 575:             else {
 576:                 register opmtemp;
 577:                 if((opmtemp=mamask[n->op-OPSIMP])&SPFLG){
 578:                     if(st->op!=NAME && st->op!=ICON && st->op!=OREG &&
 579:                         ! shltype(st->op,st)) break;
 580:                     }
 581:                 else if((dope[st->op]&(opmtemp|ASGFLG))!=opmtemp) break;
 582:                 }
 583:             /* check shape and type */
 584: 
 585:             if( ! tshape( st, n->mlnode.nshape ) ) break;
 586:             if( ! ttype( st->type, n->mlnode.ntype ) ) break;
 587: 
 588:             /* that node matched, let's try another */
 589:             /* must advance both st and n and halt at right time */
 590: 
 591:             if( (mlop = n->mlnode.op) < OPSIMP ){
 592:                 switch( optype(mlop) ){
 593: 
 594:                     default:
 595:                         cerror("(2)unknown opcode: %o",mlop);
 596:                     case BITYPE:
 597:                         goto binary;
 598:                     case UTYPE:
 599:                         st = st->left;
 600:                         break;
 601:                     case LTYPE:
 602:                         goto leaf;
 603:                     }
 604:                 }
 605:             else{
 606:                 if( mamask[mlop - OPSIMP] &
 607:                     (SIMPFLG|COMMFLG|MULFLG|DIVFLG|LOGFLG|FLOFLG|SHFFLG) ){
 608:                 binary:
 609:                     *mlsp++ = BITYPE;
 610:                     *stp++ = st;
 611:                     st = st->left;
 612:                     }
 613:                 else if( ! (mamask[mlop-OPSIMP] & UTYPE) ){/* includes OPANY */
 614: 
 615:                 leaf:
 616:                     if( mlsp == mlstack )
 617:                         goto matched;
 618:                     else if ( *--mlsp != BITYPE )
 619:                         cerror("(2)bad multi-level tree descriptor around mltree[%d]",
 620:                         n-mltree);
 621:                     st = (*--stp)->right;
 622:                     }
 623:                 else /* UNARY */ st = st->left;
 624:                 }
 625:             continue;
 626: 
 627:             matched:
 628:             /* complete multi-level match successful */
 629: # ifndef BUG3
 630:             if( vdebug ) printf("mlmatch() success\n");
 631: # endif
 632:             if( head->mlhead.subtag == 0 ) return( MDONE );
 633:             else {
 634: # ifndef BUG3
 635:                 if( vdebug )printf("\treturns %d\n",
 636:                     head->mlhead.subtag );
 637: # endif
 638:                 return( head->mlhead.subtag );
 639:                 }
 640:             }
 641:         }
 642:     return( 0 );
 643:     }
 644: # endif

Defined functions

Defined variables

Defined struct's

Defined union's

Defined macros