![[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 [Research Unix] / researchv8dc / cmd / ccom / common|
Return to match.c CVS log | Up to [Research Unix] / researchv8dc / cmd / ccom / common |
1.1 root 1: /* @(#) match.c: 1.1 12/22/83 */
2:
3: # include "mfile2.h"
4:
5: int fldsz, fldshf;
6:
7: extern int zflag; /* non-zero to output stin line and cost for
8: ** each assembly instruction
9: */
10: # define VALUE (RESC1|RESC2|RESC3|RLEFT|RRIGHT)
11:
12: OPTAB *
13: match( p, q )
14: register NODE *p;
15: register OPTAB *q;
16: {
17: /* look for match in table */
18: /* given a tree, p, and a template q, returns the next template that
19: /* matches p */
20: /* q == NULL starts the process off */
21: /* match is not called recursively, so much of the setup can be done
22: /* into static variables */
23:
24: static NODE *r, *l;
25: static tl, tr, goal, tyop;
26: static pop, lflg;
27: int rr;
28:
29: if( !q ) {
30: /* startup code */
31:
32: q = ophead[pop=p->tn.op];
33: l = getlo( p, pop ); /* left child */
34: r = getro( p, pop ); /* right child */
35: tl = l->in.type;
36: tr = r->in.type;
37: lflg = asgop(pop); /* forces a match on lvalues */
38: if( p->tn.goal == CCC ) goal = (VALUE|RESCC);
39: else if( p->tn.goal == NRGS ) goal = VALUE;
40: else goal = ~0;
41: tyop = p->in.type;
42: }
43:
44: else {
45: if( fast ) return( (OPTAB *)0 ); /* only first match */
46: else q = q->nextop;
47: }
48: if( !q ) return( (OPTAB *)0 );
49:
50: # ifndef NODBG
51: if( sdebug ) {
52: printf( "match tree %d, op %s\n", p-node, opst[pop] );
53: }
54: # endif
55: for( ; q ; q = q->nextop ){
56:
57: /* some templates are no good for computing values */
58:
59: if( !( tl & q->ltype ) ) continue;
60: if( !( tr & q->rtype ) ) continue;
61:
62: if( !( goal & q->rewrite ) ) continue;
63:
64: # ifndef NODBG
65: if( sdebug ) {
66: printf( " try table entry, line %d, op %s\n",
67: q->stinline, opst[q->op] );
68: }
69: # endif
70: if( !( tyop & q->tyop ) ) {
71: # ifndef NODBG
72: if( sdebug ) {
73: printf(
74: "\tentry line %d fails tyop, %o vs %o\n",
75: q->stinline, tyop, q->tyop );
76: }
77: # endif
78: continue;
79: }
80:
81: if( q->rshape ){
82: if( rr=mspine( q->rshape, (q->lshape)?r:p, 0, sha[1] )){
83: sha[1][rr] = 0;
84: if( !q->lshape ) ustrip(pop);
85: }
86: else continue;
87: }
88: else {
89: sha[1][1] = sha[1][0] = (SHAPE *)0;
90: }
91:
92: if( q->lshape ){
93: if( !lflg && asgop(q->op) ){
94: /* q->op is an assignment op, pop isn't */
95: /* thus, the lhs => a register or temp */
96: rr = rtspine( q->lshape, p );
97: }
98: else rr = mspine( q->lshape, l, lflg, sha[0] );
99: if( rr ) sha[0][rr] = 0;
100: else continue;
101: }
102: else {
103: sha[0][1] = sha[0][0] = (SHAPE *)0;
104: }
105:
106: /* at this point, we have a match */
107:
108: # ifndef NODBG
109: if( sdebug ) {
110: printf( "table line %d matches tree %d\n",
111: q->stinline, p-node );
112: }
113: # endif
114:
115: return( q ); /* found match */
116: }
117: return( (OPTAB *)0 );
118: }
119:
120: ustrip( o )
121: {
122: /* strip out of sha[1] all shapes with op != o */
123: /* sty should do this someday, but for now, it's done here */
124: register i, j;
125:
126: for( j=i=0; sha[1][j]; ++j ) {
127: if( sha[1][j]->op == o ) sha[1][i++] = sha[1][j];
128: }
129: sha[1][i] = (SHAPE *)0;
130: }
131:
132: rtspine( ps, p )
133: SHAPE **ps;
134: NODE *p; {
135: /* special routine to put the lhs into a reg or a temp */
136: /* looks for reg and/or temp in s */
137: /* makes a list in sha[0] */
138: register rr;
139: register SHAPE *s;
140:
141: for( rr = 0; s = *ps; ++ps ) {
142: /* works because FREE, CCODES, REG, and TEMP are first */
143: switch( s->op ) {
144:
145: case FREE:
146: case CCODES:
147: continue;
148:
149: case REG:
150: case TEMP:
151: if( s->sh ) if( !spshape( s->sh, p ) ) continue;
152: if( rr >= NSHP-1 ) cerror( "too many shapes" );
153: sha[0][rr] = s;
154: ++rr;
155: continue;
156:
157: default:
158: break;
159: }
160:
161: break;
162: }
163:
164: return( rr );
165: }
166:
167: restrip( pls )
168: register SHAPE **pls;
169: {
170: /* throw away those shapes that can't be results */
171: register SHAPE **p;
172:
173: for( p=pls; *p = *pls; ++p, ++pls )
174: {
175: if( noresult( *p ) ) --p; /* overwrite if result is illegal */
176: }
177: }
178:
179: noresult( s )
180: register SHAPE *s;
181: {
182: if( !s ) return( 0 );
183: if( s->op == INCR || s->op == DECR ) return( 1 );
184: return( (s->sr && noresult(s->sr)) ||
185: (s->sl && noresult( s->sl )) );
186: }
187:
188: smspine( s, p, flag )
189: register NODE *p;
190: register SHAPE *s;
191: {
192: /* match the spine of s, including special shapes */
193: /* this is a submatch, called only by mspine */
194: /* flag is nonzero if STAR's must be skipped */
195:
196: register sop, pop;
197:
198: again:
199:
200: sop = s->op;
201: pop = p->tn.op;
202:
203: # ifndef NODBG
204: if( sdebug>1 )
205: {
206: printf( " smspine(%d[%s], %d[%s])\n",
207: s-shapes, opst[sop], p-node, opst[pop] );
208: }
209: # endif
210:
211: if( ( s->sh ) && !spshape( s->sh,p) ) return( 0 );
212: if( sop != pop )
213: {
214: if( sop == CCODES || sop == FREE ) return(1);
215: return( !flag && (sop==REG || sop==TEMP) );
216: }
217: if( sop == STAR )
218: {
219: flag = 0;
220: goto recurse;
221: }
222: switch( optype( sop ) )
223: {
224:
225: case BITYPE:
226: if( !smspine( s->sr, p->in.right, 0 ) ) return(0);
227: flag = asgop(sop);
228: /* FALLTHRU */
229:
230: case UTYPE:
231: recurse:
232: s = s->sl;
233: p = p->in.left;
234: goto again;
235:
236: default:
237: return( 1 );
238: }
239: }
240:
241: mspine( ps, p, flag, ppls )
242: register NODE *p;
243: register SHAPE **ps;
244: register SHAPE **ppls;
245: {
246: /* match the spine of s, including special shapes */
247: /* s points to a list of shapes */
248: /* those shapes that match are copied into **ppls, with a null at end */
249: /* flag = 1 forces regs and temps to match exactly */
250: /* rr, the number of matches, is returned */
251:
252: register SHAPE *s;
253: int pop, rr;
254:
255: # ifndef NODBG
256: if( sdebug )
257: {
258: printf( "\tmspine( %d, %d, %d )\n", ps-pshape, p-node, flag );
259: }
260: # endif
261: pop = p->tn.op;
262:
263: /* copy the wild-cards, and those where the op matches */
264: for( rr=0; s = *ps; ++ps )
265: {
266: switch( s->op )
267: {
268:
269: case REG:
270: case TEMP:
271: if( flag ) break;
272: if( s->sh ) if( !spshape(s->sh,p) ) continue;
273: /* FALLTHRU */
274:
275: case FREE:
276: case CCODES:
277: if( rr >= NSHP-1 ) cerror( "too many shapes" );
278:
279: # ifndef NODBG
280: if( sdebug )
281: {
282: printf(
283: "\t\tmspine( %d[%s], %d[%s] ), becomes %d\n",
284: s-shapes, opst[s->op], p-node,
285: opst[pop], rr );
286: }
287: # endif
288:
289: ppls[rr++] = s;
290: continue;
291:
292: default:
293: break;
294: }
295: break;
296: }
297:
298: /* now, either s is 0 or s has a "real" op */
299: /* the first condition survives the next two loops */
300:
301: /* we have matched the wild cards: find others where the op matches */
302:
303: for( ; (s= *ps) && s->op != pop; ++ps )
304: {
305: ;
306: }
307:
308: /* now, s is null or matches the op of p */
309: for( ; (s = *ps) && s->op == pop; ++ps )
310: {
311:
312: if( pop == STAR )
313: {
314: if( !smspine( s->sl, p->in.left, 0 ) ) continue;
315: }
316:
317: /* general case: check the subtrees also */
318: else if( s->sl )
319: {
320: if( s->sr )
321: {
322: if( !smspine( s->sr, p->in.right, 0 ) )
323: continue;
324: if( !smspine( s->sl, p->in.left, asgop(s->op)) )
325: continue;
326: }
327: else
328: {
329: if( !smspine( s->sl, p->in.left, flag ))
330: continue;
331: }
332: }
333: else if( s->sr && !smspine( s->sr, p->in.right, 0 ) )
334: continue;
335:
336: /* if we get this far, we are in good shape */
337:
338: if( s->sh ) if( !spshape( s->sh, p ) ) continue;
339: if( rr >= NSHP-1 ) cerror( "too many shapes" );
340:
341: # ifndef NODBG
342: if( sdebug )
343: {
344: printf( "\t\tmspine( %d[%s], %d[%s] ), becomes %d\n",
345: s-shapes, opst[s->op], p-node,
346: opst[pop], rr );
347: }
348: # endif
349:
350: ppls[rr++] = s;
351: }
352:
353: /* fall out and we are done */
354: return( rr );
355: }
356:
357:
358: tempok( p )
359: NODE *p;
360:
361: {
362: /* decide if the result of p is OK as a temp */
363: int o;
364: if( (o = p->tn.op) == TEMP ) return( 1 );
365: if( asgop(o) && o!=INCR && o!=DECR )
366: {
367: return( p->in.left->tn.op == TEMP );
368: }
369: return( 0 );
370: }
371:
372: int sideff;
373:
374: rmside( p )
375: NODE *p;
376:
377: {
378: /* p is a tree with side effects: remove them */
379: /* this is done in place */
380: int o;
381: NODE *q;
382:
383: o = p->tn.op;
384: switch( o )
385: {
386:
387: case INCR:
388: case DECR:
389: case ASG PLUS:
390: case ASG MINUS:
391: if( p->in.right->tn.op == ICON ) p->in.right->tn.op = FREE;
392: else
393: {
394: regrcl( p->in.right );
395: tfree( p->in.right );
396: }
397: q = p->in.left;
398: *p = *q;
399: q->tn.op = FREE;
400: rmside( p );
401: return;
402: }
403:
404: switch( optype( o ) )
405: {
406:
407: case BITYPE:
408: rmside( p->in.right );
409: case UTYPE:
410: rmside( p->in.left );
411: }
412: }
413:
414: expand( p, goal, cp, q )
415: NODE *p;
416: char *cp;
417: OPTAB *q;
418: {
419: /* generate code by interpreting table entry */
420:
421: CONSZ val;
422: NODE *q1, *q2;
423: int c;
424: TWORD t;
425:
426: #ifdef GDEBUG
427: if ((c = p->stn.op) == CALL || c == UNARY CALL)
428: dbnargs(p->stn.argsize);
429: #endif
430: for( ; *cp; ++cp )
431: {
432: switch( *cp )
433: {
434:
435: case '\\':
436: ++cp;
437: /* FALLTHRU */
438: default:
439: PUTCHAR( *cp );
440: continue; /* this is the usual case... */
441:
442: case '\n':
443: if( zflag )
444: { /* add stin line number of production as a comment */
445: printf( "\t\t%s %d", COMMENTSTR, q->stinline );
446: if( p->in.cst[CEFF] < INFINITY )
447: printf( " = %d", p->in.cst[CEFF] );
448: }
449: PUTCHAR( *cp );
450: continue;
451:
452: case 'Y':
453: /* don't check this string: deleted by match */
454: continue;
455:
456: case 'Z': /* special machine dependent operations */
457: zzzcode( p, &cp, q );
458: continue;
459:
460: case 'E': /* exit */
461: if( zflag )
462: { /* add stin line number of production as a comment */
463: printf( "\t%s\t%d = %d",
464: COMMENTSTR, q->stinline, p->in.cst[CEFF] );
465: }
466: PUTCHAR( '\n' );
467: return;
468:
469: # ifndef STACK
470: case 'D': /* test for dependency */
471: q1 = getadr( p, &cp );
472: if( cp[1] == '!' )
473: {
474: c=0;
475: ++cp;
476: }
477: else c=1;
478: q2 = getadr( p, &cp );
479: if( q1->tn.op != REG ) cerror( "bad D" );
480: if( ushare( q2, q1->tn.rval ) == c ) continue;
481: goto cream;
482: # endif
483:
484: case 'R': /* put an operand into a particular register */
485: /* if the operand is in the register, delete the line */
486: q1 = getadr( p, &cp );
487: c = (*++cp == '=');
488: q2 = getadr( p, &cp );
489: if( q1->tn.op != REG )
490: {
491: if( c ) goto cream;
492: continue;
493: }
494: if( q2->tn.op != REG )
495: {
496: if( c ) goto cream;
497: continue;
498: }
499: if( q1->tn.rval != q2->tn.rval )
500: {
501: if( c ) goto cream;
502: continue;
503: }
504: if( c ) continue;
505: cream:
506: /* clobber a line to newline, or up to an E */
507: while( *++cp != '\n' && *cp != 'E' )
508: {
509: if( *cp == '\\' ) ++cp; /* hide next char */
510: if( !*cp ) return;
511: }
512: continue;
513:
514: case 'F': /* this line deleted if FOREFF is active */
515: if( goal & FOREFF ) goto cream;
516: continue;
517:
518: case 'S': /* field size */
519: case 'H': /* field shift */
520: case 'M': /* field mask, in place */
521: case 'N': /* field mask, right shifted */
522: c = *cp;
523: if( cp[1] == '~' )
524: {
525: if( c == 'M' ) c = 'm';
526: else if( c == 'N' ) c = 'n';
527: else cerror( "bad ~ after S or H" );
528: ++cp;
529: }
530: else if( cp[1] == '?' )
531: {
532: if( c == 'H' ) c = 'h';
533: else cerror( "bad ? after S, M, or N" );
534: ++cp;
535: }
536: q1 = getadr(p,&cp);
537: if( q1->tn.op != FLD ) cerror( "bad FLD for %c", c );
538: fldsz = UPKFSZ(q1->tn.rval);
539: # ifdef RTOLBYTES
540: fldshf = UPKFOFF(q1->tn.rval);
541: # else
542: t = q1->tn.type;
543: if( t & (TLONG|TULONG) )
544: {
545: fldshf = SZLONG - fldsz - UPKFOFF(q1->tn.rval);
546: }
547: else if( t & (TSHORT|TUSHORT) )
548: {
549: fldshf = SZSHORT - fldsz - UPKFOFF(q1->tn.rval);
550: }
551: else if( t & (TCHAR|TUCHAR) )
552: {
553: fldshf = SZCHAR - fldsz - UPKFOFF(q1->tn.rval);
554: }
555: else fldshf = SZINT - fldsz - UPKFOFF(q1->tn.rval);
556: # endif
557: if( c == 'h' )
558: {
559: if( fldshf == 0 ) goto cream;
560: continue;
561: }
562: if( c=='S' || c=='H' )
563: {
564: printf( "%d", c=='S' ? fldsz : fldshf );
565: continue;
566: }
567: val = 1;
568: val <<= fldsz;
569: --val;
570: if( c=='M' || c == 'm' ) val <<= fldshf;
571: if( c=='m' || c == 'n' ) val = ~val;
572: # ifdef MYMASK
573: MYMASK(val);
574: # else
575: printf( "%ld" , val );
576: # endif
577: continue;
578:
579: case 'L': /* output special label field */
580: printf( "%d", p->bn.label );
581: continue;
582:
583: case 'C': /* for constant value only */
584: conput( q1 = getadr( p, &cp ) );
585: if( !sideff ) cerror( "constant with side effects?" );
586: continue;
587:
588: case 'I': /* in instruction */
589: insput( q1 = getadr( p, &cp ) );
590: if( sideff ) rmside( q1 );
591: continue;
592:
593: case 'A': /* address of */
594: adrput( q1 = getadr( p, &cp ) );
595: if( sideff ) rmside( q1 );
596: continue;
597:
598: case 'U': /* for upper half of address, only */
599: upput( q1 = getadr( p, &cp ) );
600: if( sideff ) rmside( q1 );
601: continue;
602: #ifdef TMPSRET
603: case 'T': /* grab a temp for structure return and give it */
604: /* to adrput */
605: q1 = talloc();
606: q1->tn.op = TEMP;
607: q1->tn.type = TSTRUCT;
608: q1->tn.lval = freetemp(p->stn.stsize / SZINT);
609: q1->tn.lval = BITOOR(q1->tn.lval);
610: adrput(q1);
611: tfree(q1);
612: continue;
613: #endif
614:
615: }
616: }
617: }
618:
619: NODE *
620: getlr( p, c )
621: NODE *p;
622:
623: {
624:
625: /* return the pointer to the left or right side of p, or p itself,
626: ** depending on the optype of p
627: */
628:
629: switch( c )
630: {
631:
632: case '1':
633: case '2':
634: case '3':
635: return( &resc[c-'1'] );
636:
637: case 'L':
638: return( optype( p->in.op ) == LTYPE ? p : p->in.left );
639:
640: case 'R':
641: return( optype( p->in.op ) != BITYPE ? p : p->in.right );
642:
643: }
644: cerror( "bad getlr: %c", c );
645: /* NOTREACHED */
646: }
647:
648: NODE *
649: getadr( p, pc )
650: NODE *p;
651: char **pc;
652:
653: {
654: /* like getlr, but allows (LL), (LR), etc. */
655: int c;
656: sideff = 1;
657: c = *++(*pc);
658: if( c == '-' )
659: {
660: c = *++(*pc);
661: sideff = 0;
662: }
663: if( c == '.' ) return( p );
664: else if( c != '(' ) return( getlr( p, c ) );
665:
666: for(;;)
667: {
668: switch( c = *++(*pc) )
669: {
670:
671: case ')':
672: return( p );
673:
674: case 'L':
675: p = getl( p );
676: continue;
677:
678: case 'R':
679: p = getr( p );
680: continue;
681:
682: default:
683: cerror( "bad table char in (): %c", c );
684: }
685: }
686: /* NOTREACHED */
687: }
688:
689: long pow2[] =
690: {
691: 01L, 02L, 04L,
692: 010L, 020L, 040L,
693: 0100L, 0200L, 0400L,
694: 01000L, 02000L, 04000L,
695: 010000L, 020000L, 040000L,
696: 0100000L, 0200000L, 0400000L,
697: 01000000L, 02000000L, 04000000L,
698: 010000000L, 020000000L, 040000000L,
699: 0100000000L, 0200000000L, 0400000000L,
700: 01000000000L, 02000000000L, 04000000000L,
701: 010000000000L, 020000000000L, 040000000000L,
702: };
703:
704: spshape( sh, p )
705: NODE *p;
706:
707: {
708: long val;
709: int t, i;
710:
711: if( !(sh&SPECIAL) ) cerror( "spshape" );
712: if( sh&SPTYPE )
713: {
714: # ifndef NODBG
715: if( sdebug )
716: printf( "SPTYPE(%d, %o), ttype=%o\n", p-node,
717: sh, p->tn.type );
718: # endif
719:
720: if( sh & p->tn.type ) return( 1 );
721: else return( 0 );
722: }
723: t = (sh&STMASK);
724: i = (sh&SVMASK);
725:
726: switch( t )
727: {
728:
729: case SRANGE0:
730: case SSRANGE:
731: if( i<0 || i>31 ) cerror( "bad shape range" );
732: case SVAL:
733: case SNVAL:
734: case NACON:
735:
736: if( p->tn.op != ICON || p->tn.name != (char *) 0 ) return( 0 );
737: if( t == NACON ) return(1);
738: val = p->tn.lval;
739: if( t==SVAL && val == i ) return( 1 );
740: else if( t==SNVAL && val == -i ) return( 1 );
741: else if( t==SRANGE0 && val>=0 && val<pow2[i] ) return( 1 );
742: else if( t==SSRANGE && val>= -pow2[i] && val<pow2[i] )return(1);
743: return( 0 );
744:
745: case SUSER:
746: return( special( sh, p ) );
747:
748: default:
749: cerror( "bad special call" );
750: /* NOTREACHED */
751: }
752: }
This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.