![[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] / 43BSDTahoe / lib / mip|
Return to match.c CVS log | Up to [CSRG BSD Unix] / 43BSDTahoe / lib / mip |
1.1 root 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
This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.