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