![[BACK]](/cvsweb/icons/back.gif){kind=icon}
Return to match.c CVS log ![[TXT]](/cvsweb/icons/text.gif){kind=icon}
![[DIR]](/cvsweb/icons/dir.gif){kind=icon}
Up to [CSRG BSD Unix] / 43BSD / lib / mip|
Return to match.c CVS log | Up to [CSRG BSD Unix] / 43BSD / lib / mip |
1.1 ! root 1: #ifndef lint ! 2: static char *sccsid ="@(#)match.c 4.4 (Berkeley) 8/22/85"; ! 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
This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.