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
|
Last modified: 1985-08-25
Generated: 2016-12-26 |
Generated by src2html V0.67
page hit count: 1780 |
|