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