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