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
tshape(p,shape)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
ttype(t,tword)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
setrew()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
match(p,cookie)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
expand(p,cookie,cp)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 *
getlr(p,c)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
mlinit()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
mlmatch(subtree,target,subtarget)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