xref: /original-bsd/old/pcc/mip/match.c (revision 24da39fa)
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