1 #ifndef lint 2 static char *sccsid ="@(#)match.c 4.5 (Berkeley) 10/15/86"; 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 ), SZLONG ); 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 645