xref: /csrg-svn/old/pcc/mip/optim.c (revision 25748)
117746Sralph #ifndef lint
2*25748Sdonn static char *sccsid ="@(#)optim.c	4.7 (Berkeley) 01/08/86";
317746Sralph #endif lint
417746Sralph 
518393Sralph # include "pass1.h"
616935Sralph 
716935Sralph # define SWAP(p,q) {sp=p; p=q; q=sp;}
816935Sralph # define RCON(p) (p->in.right->in.op==ICON)
916935Sralph # define RO(p) p->in.right->in.op
1016935Sralph # define RV(p) p->in.right->tn.lval
1116935Sralph # define LCON(p) (p->in.left->in.op==ICON)
1216935Sralph # define LO(p) p->in.left->in.op
1316935Sralph # define LV(p) p->in.left->tn.lval
1416935Sralph 
1524404Smckusick 	/* is p a constant without a name */
1624404Smckusick # define nncon(p)	((p)->in.op == ICON && (p)->tn.rval == NONAME)
1724404Smckusick 
1816935Sralph int oflag = 0;
1916935Sralph 
2016935Sralph NODE *
fortarg(p)2116935Sralph fortarg( p ) NODE *p; {
2216935Sralph 	/* fortran function arguments */
2316935Sralph 
2416935Sralph 	if( p->in.op == CM ){
2516935Sralph 		p->in.left = fortarg( p->in.left );
2616935Sralph 		p->in.right = fortarg( p->in.right );
2716935Sralph 		return(p);
2816935Sralph 		}
2916935Sralph 
3016935Sralph 	while( ISPTR(p->in.type) ){
3116935Sralph 		p = buildtree( UNARY MUL, p, NIL );
3216935Sralph 		}
3316935Sralph 	return( optim(p) );
3416935Sralph 	}
3516935Sralph 
3616935Sralph 	/* mapping relationals when the sides are reversed */
3716935Sralph short revrel[] ={ EQ, NE, GE, GT, LE, LT, UGE, UGT, ULE, ULT };
3816935Sralph NODE *
optim(p)3916935Sralph optim(p) register NODE *p; {
4016935Sralph 	/* local optimizations, most of which are probably machine independent */
4116935Sralph 
4216935Sralph 	register o, ty;
4316935Sralph 	NODE *sp;
4416935Sralph 	int i;
4516935Sralph 	TWORD t;
4616935Sralph 
4716935Sralph 	if( (t=BTYPE(p->in.type))==ENUMTY || t==MOETY ) econvert(p);
4816935Sralph 	if( oflag ) return(p);
4916935Sralph 	ty = optype( o=p->in.op);
5016935Sralph 	if( ty == LTYPE ) return(p);
5116935Sralph 
5216935Sralph 	if( ty == BITYPE ) p->in.right = optim(p->in.right);
5316935Sralph 	p->in.left = optim(p->in.left);
5416935Sralph 
5516935Sralph 	/* collect constants */
5616935Sralph 
5716935Sralph 	switch(o){
5816935Sralph 
5916935Sralph 	case SCONV:
6016935Sralph 	case PCONV:
6116935Sralph 		return( clocal(p) );
6216935Sralph 
6316935Sralph 	case FORTCALL:
6416935Sralph 		p->in.right = fortarg( p->in.right );
6516935Sralph 		break;
6616935Sralph 
6716935Sralph 	case UNARY AND:
6816936Sralph 		if( LO(p) != NAME || !andable(p->in.left) ) return(p);
6916935Sralph 
7016935Sralph 		LO(p) = ICON;
7116935Sralph 
7216935Sralph 		setuleft:
7316935Sralph 		/* paint over the type of the left hand side with the type of the top */
7416935Sralph 		p->in.left->in.type = p->in.type;
7516935Sralph 		p->in.left->fn.cdim = p->fn.cdim;
7616935Sralph 		p->in.left->fn.csiz = p->fn.csiz;
7716935Sralph 		p->in.op = FREE;
7816935Sralph 		return( p->in.left );
7916935Sralph 
8016935Sralph 	case UNARY MUL:
8116935Sralph 		if( LO(p) != ICON ) break;
8216935Sralph 		LO(p) = NAME;
8316935Sralph 		goto setuleft;
8416935Sralph 
8516935Sralph 	case MINUS:
8616935Sralph 		if( !nncon(p->in.right) ) break;
8716935Sralph 		RV(p) = -RV(p);
8816935Sralph 		o = p->in.op = PLUS;
8916935Sralph 
9016935Sralph 	case MUL:
9116935Sralph 	case PLUS:
9216935Sralph 	case AND:
9316935Sralph 	case OR:
9416935Sralph 	case ER:
9516935Sralph 		/* commutative ops; for now, just collect constants */
9616935Sralph 		/* someday, do it right */
9716935Sralph 		if( nncon(p->in.left) || ( LCON(p) && !RCON(p) ) ) SWAP( p->in.left, p->in.right );
9816935Sralph 		/* make ops tower to the left, not the right */
9916935Sralph 		if( RO(p) == o ){
10016935Sralph 			NODE *t1, *t2, *t3;
10116935Sralph 			t1 = p->in.left;
10216935Sralph 			sp = p->in.right;
10316935Sralph 			t2 = sp->in.left;
10416935Sralph 			t3 = sp->in.right;
10516935Sralph 			/* now, put together again */
10616935Sralph 			p->in.left = sp;
10716935Sralph 			sp->in.left = t1;
10816935Sralph 			sp->in.right = t2;
10916935Sralph 			p->in.right = t3;
11016935Sralph 			}
11116935Sralph 		if(o == PLUS && LO(p) == MINUS && RCON(p) && RCON(p->in.left) &&
11224404Smckusick 		   conval(p->in.right, MINUS, p->in.left->in.right)){
11316935Sralph 			zapleft:
11416935Sralph 			RO(p->in.left) = FREE;
11516935Sralph 			LO(p) = FREE;
11616935Sralph 			p->in.left = p->in.left->in.left;
11716935Sralph 		}
11824404Smckusick 		if( RCON(p) && LO(p)==o && RCON(p->in.left) &&
11924404Smckusick 		    conval( p->in.right, o, p->in.left->in.right ) ){
12016935Sralph 			goto zapleft;
12116935Sralph 			}
12224404Smckusick 		else if( LCON(p) && RCON(p) &&
12324404Smckusick 			 conval( p->in.left, o, p->in.right ) ){
12416935Sralph 			zapright:
12516935Sralph 			RO(p) = FREE;
12616935Sralph 			p->in.left = makety( p->in.left, p->in.type, p->fn.cdim, p->fn.csiz );
12716935Sralph 			p->in.op = FREE;
12816935Sralph 			return( clocal( p->in.left ) );
12916935Sralph 			}
13024404Smckusick 		/* FALL THROUGH */
13116935Sralph 
13224404Smckusick 	case ASG MUL:
13324404Smckusick 		/* change muls to adds or shifts */
13416935Sralph 
13524404Smckusick 		if( (o == MUL || o == ASG MUL) &&
13624404Smckusick 		    nncon(p->in.right) && (i=ispow2(RV(p)))>=0){
13724404Smckusick 			if( i == 0 ) /* multiplication by 1 */
13816935Sralph 				goto zapright;
139*25748Sdonn 			/* c2 will turn 'i << 1' into 'i + i' for us */
14024404Smckusick 			else {
14124404Smckusick 				p->in.op = (asgop(o) ? ASG LS : LS);
14224404Smckusick 				o = p->in.op;
14324404Smckusick 				p->in.right->in.type = p->in.right->fn.csiz = INT;
14424404Smckusick 				RV(p) = i;
14524404Smckusick 				}
14616935Sralph 			}
14716935Sralph 
14816935Sralph 		/* change +'s of negative consts back to - */
14916935Sralph 		if( o==PLUS && nncon(p->in.right) && RV(p)<0 ){
15016935Sralph 			RV(p) = -RV(p);
15116935Sralph 			o = p->in.op = MINUS;
15216935Sralph 			}
15324404Smckusick 		/* FALL THROUGH */
15424404Smckusick 	case ASG AND:
15524404Smckusick 	case ASG PLUS:
15624404Smckusick 	case ASG MINUS:
15718019Sralph 	case RS:
15818019Sralph 	case LS:
15924404Smckusick 		/* Operations with zero */
16024404Smckusick 		if( nncon(p->in.right) && RV(p) == 0 ) {
16124404Smckusick 			if( o == MUL || o == ASG MUL ||
16224404Smckusick 			    o == AND || o == ASG AND ) {
16324404Smckusick 				if( asgop(o) )
16424404Smckusick 					p->in.op = ASSIGN;
16524404Smckusick 				else if( optype(LO(p)) == LTYPE ) {
16624404Smckusick 					p->in.op = FREE;
16724404Smckusick 					LO(p) = FREE;
16824404Smckusick 					p = p->in.right;
16924404Smckusick 					}
17024404Smckusick 				else
17124404Smckusick 					p->in.op = COMOP; /* side effects */
17224404Smckusick 				}
17324404Smckusick 			else if( o == PLUS || o == MINUS ||
17424404Smckusick 				 o == ASG PLUS || o == ASG MINUS ||
17524404Smckusick 				 o == OR || o == ER ||
17624404Smckusick 				 o == LS || o == RS )
17724404Smckusick 				goto zapright;
17824404Smckusick 			}
179*25748Sdonn 		if( o != LS && o != RS )
180*25748Sdonn 			break;
181*25748Sdonn 		/* FALL THROUGH */
182*25748Sdonn 
183*25748Sdonn 	case ASG RS:
184*25748Sdonn 	case ASG LS:
185*25748Sdonn 		if( !ISUNSIGNED(p->in.left->in.type) )
186*25748Sdonn 			break;
187*25748Sdonn 		if( p->in.right->in.op == ICON &&
188*25748Sdonn 		    p->in.right->tn.lval < 0 ) {
189*25748Sdonn 			/*
190*25748Sdonn 			 * Technically negative shifts are illegal
191*25748Sdonn 			 * but we can support them, at least with
192*25748Sdonn 			 * constants; you take potluck with variables.
193*25748Sdonn 			 */
194*25748Sdonn 			p->in.right->tn.lval = -p->in.right->tn.lval;
195*25748Sdonn 			switch( o ){
196*25748Sdonn 			case LS:	p->in.op = RS; break;
197*25748Sdonn 			case ASG LS:	p->in.op = ASG RS; break;
198*25748Sdonn 			case RS:	p->in.op = LS; break;
199*25748Sdonn 			case ASG RS:	p->in.op = ASG LS; break;
200*25748Sdonn 				}
201*25748Sdonn 			}
20224404Smckusick 		break;
20316935Sralph 
20424404Smckusick 	case ASG DIV:
20516935Sralph 	case DIV:
20624404Smckusick 		if( nncon( p->in.right ) ){
20724404Smckusick 			if( RV(p) == 0 ) uerror("division by zero");
20824404Smckusick 			else if( RV(p) == 1 ) goto zapright;
20924404Smckusick 			/* Unsigned division by a power of two */
21024404Smckusick 			else if( (i=ispow2(RV(p)))>=0 &&
21124404Smckusick 				 (ISUNSIGNED(p->in.left->in.type) ||
21224404Smckusick 				  ISUNSIGNED(p->in.right->in.type)) ){
21324404Smckusick 				p->in.op = (asgop(o) ? ASG RS : RS);
21424404Smckusick 				p->in.right->in.type = p->in.right->fn.csiz = INT;
21524404Smckusick 				RV(p) = i;
21624404Smckusick 				}
21718019Sralph 			}
21816935Sralph 		break;
21916935Sralph 
22024404Smckusick 	case ASG MOD:
22118019Sralph 	case MOD:
22224404Smckusick 		if( nncon(p->in.right) ){
22324404Smckusick 			if( RV(p) == 0 ) uerror("modulus of zero");
22424404Smckusick 			else if( RV(p) == 1 ){ /* mod by one gives zero */
22524404Smckusick 				RV(p) = 0;
22624404Smckusick 				if( asgop(o) )
22724404Smckusick 					p->in.op = ASSIGN;
22824404Smckusick 				else if( optype(LO(p)) == LTYPE ) {
22924404Smckusick 					p->in.op = FREE;
23024404Smckusick 					LO(p) = FREE;
23124404Smckusick 					p = p->in.right;
23224404Smckusick 					}
23324404Smckusick 				else
23424404Smckusick 					p->in.op = COMOP; /* side effects */
23524404Smckusick 				}
23624404Smckusick 			else if ((i=ispow2(RV(p)))>=0 &&
23724404Smckusick 				 (ISUNSIGNED(p->in.left->in.type) ||
23824404Smckusick 				  ISUNSIGNED(p->in.right->in.type)) ){
23924404Smckusick 				/* Unsigned mod by a power of two */
24024404Smckusick 				p->in.op = (asgop(o) ? ASG AND : AND);
24124404Smckusick 				RV(p)--;
24224404Smckusick 				}
24318019Sralph 			}
24418019Sralph 		break;
24518019Sralph 
24616935Sralph 	case EQ:
24716935Sralph 	case NE:
24816935Sralph 	case LT:
24916935Sralph 	case LE:
25016935Sralph 	case GT:
25116935Sralph 	case GE:
25216935Sralph 	case ULT:
25316935Sralph 	case ULE:
25416935Sralph 	case UGT:
25516935Sralph 	case UGE:
25616935Sralph 		if( !LCON(p) ) break;
25716935Sralph 
25816935Sralph 		/* exchange operands */
25916935Sralph 
26016935Sralph 		sp = p->in.left;
26116935Sralph 		p->in.left = p->in.right;
26216935Sralph 		p->in.right = sp;
26316935Sralph 		p->in.op = revrel[p->in.op - EQ ];
26416935Sralph 		break;
26516935Sralph 
26616935Sralph 		}
26716935Sralph 
26816935Sralph 	return(p);
26916935Sralph 	}
27016935Sralph 
ispow2(c)27116935Sralph ispow2( c ) CONSZ c; {
27216935Sralph 	register i;
27316935Sralph 	if( c <= 0 || (c&(c-1)) ) return(-1);
27416935Sralph 	for( i=0; c>1; ++i) c >>= 1;
27516935Sralph 	return(i);
27616935Sralph 	}
277