[unix-history] / usr / src / lib / mip / optim.c

#ifndef lint
static char *sccsid ="@(#)optim.c	4.7 (Berkeley) 1/8/86";
#endif lint

# include "pass1.h"

# define SWAP(p,q) {sp=p; p=q; q=sp;}
# define RCON(p) (p->in.right->in.op==ICON)
# define RO(p) p->in.right->in.op
# define RV(p) p->in.right->tn.lval
# define LCON(p) (p->in.left->in.op==ICON)
# define LO(p) p->in.left->in.op
# define LV(p) p->in.left->tn.lval

	/* is p a constant without a name */
# define nncon(p)	((p)->in.op == ICON && (p)->tn.rval == NONAME)

int oflag = 0;

NODE *
fortarg( p ) NODE *p; {
	/* fortran function arguments */

	if( p->in.op == CM ){
		p->in.left = fortarg( p->in.left );
		p->in.right = fortarg( p->in.right );
		return(p);
		}

	while( ISPTR(p->in.type) ){
		p = buildtree( UNARY MUL, p, NIL );
		}
	return( optim(p) );
	}

	/* mapping relationals when the sides are reversed */
short revrel[] ={ EQ, NE, GE, GT, LE, LT, UGE, UGT, ULE, ULT };
NODE *
optim(p) register NODE *p; {
	/* local optimizations, most of which are probably machine independent */

	register o, ty;
	NODE *sp;
	int i;
	TWORD t;

	if( (t=BTYPE(p->in.type))==ENUMTY || t==MOETY ) econvert(p);
	if( oflag ) return(p);
	ty = optype( o=p->in.op);
	if( ty == LTYPE ) return(p);

	if( ty == BITYPE ) p->in.right = optim(p->in.right);
	p->in.left = optim(p->in.left);

	/* collect constants */

	switch(o){

	case SCONV:
	case PCONV:
		return( clocal(p) );

	case FORTCALL:
		p->in.right = fortarg( p->in.right );
		break;

	case UNARY AND:
		if( LO(p) != NAME || !andable(p->in.left) ) return(p);

		LO(p) = ICON;

		setuleft:
		/* paint over the type of the left hand side with the type of the top */
		p->in.left->in.type = p->in.type;
		p->in.left->fn.cdim = p->fn.cdim;
		p->in.left->fn.csiz = p->fn.csiz;
		p->in.op = FREE;
		return( p->in.left );

	case UNARY MUL:
		if( LO(p) != ICON ) break;
		LO(p) = NAME;
		goto setuleft;

	case MINUS:
		if( !nncon(p->in.right) ) break;
		RV(p) = -RV(p);
		o = p->in.op = PLUS;

	case MUL:
	case PLUS:
	case AND:
	case OR:
	case ER:
		/* commutative ops; for now, just collect constants */
		/* someday, do it right */
		if( nncon(p->in.left) || ( LCON(p) && !RCON(p) ) ) SWAP( p->in.left, p->in.right );
		/* make ops tower to the left, not the right */
		if( RO(p) == o ){
			NODE *t1, *t2, *t3;
			t1 = p->in.left;
			sp = p->in.right;
			t2 = sp->in.left;
			t3 = sp->in.right;
			/* now, put together again */
			p->in.left = sp;
			sp->in.left = t1;
			sp->in.right = t2;
			p->in.right = t3;
			}
		if(o == PLUS && LO(p) == MINUS && RCON(p) && RCON(p->in.left) &&
		   conval(p->in.right, MINUS, p->in.left->in.right)){
			zapleft:
			RO(p->in.left) = FREE;
			LO(p) = FREE;
			p->in.left = p->in.left->in.left;
		}
		if( RCON(p) && LO(p)==o && RCON(p->in.left) &&
		    conval( p->in.right, o, p->in.left->in.right ) ){
			goto zapleft;
			}
		else if( LCON(p) && RCON(p) &&
			 conval( p->in.left, o, p->in.right ) ){
			zapright:
			RO(p) = FREE;
			p->in.left = makety( p->in.left, p->in.type, p->fn.cdim, p->fn.csiz );
			p->in.op = FREE;
			return( clocal( p->in.left ) );
			}
		/* FALL THROUGH */

	case ASG MUL:
		/* change muls to adds or shifts */

		if( (o == MUL || o == ASG MUL) &&
		    nncon(p->in.right) && (i=ispow2(RV(p)))>=0){
			if( i == 0 ) /* multiplication by 1 */
				goto zapright;
			/* c2 will turn 'i << 1' into 'i + i' for us */
			else {
				p->in.op = (asgop(o) ? ASG LS : LS);
				o = p->in.op;
				p->in.right->in.type = p->in.right->fn.csiz = INT;
				RV(p) = i;
				}
			}

		/* change +'s of negative consts back to - */
		if( o==PLUS && nncon(p->in.right) && RV(p)<0 ){
			RV(p) = -RV(p);
			o = p->in.op = MINUS;
			}
		/* FALL THROUGH */
	case ASG AND:
	case ASG PLUS:
	case ASG MINUS:
	case RS:
	case LS:
		/* Operations with zero */
		if( nncon(p->in.right) && RV(p) == 0 ) {
			if( o == MUL || o == ASG MUL ||
			    o == AND || o == ASG AND ) {
				if( asgop(o) )
					p->in.op = ASSIGN;
				else if( optype(LO(p)) == LTYPE ) {
					p->in.op = FREE;
					LO(p) = FREE;
					p = p->in.right;
					}
				else
					p->in.op = COMOP; /* side effects */
				}
			else if( o == PLUS || o == MINUS ||
				 o == ASG PLUS || o == ASG MINUS ||
				 o == OR || o == ER ||
				 o == LS || o == RS )
				goto zapright;
			}
		if( o != LS && o != RS )
			break;
		/* FALL THROUGH */

	case ASG RS:
	case ASG LS:
		if( !ISUNSIGNED(p->in.left->in.type) )
			break;
		if( p->in.right->in.op == ICON &&
		    p->in.right->tn.lval < 0 ) {
			/*
			 * Technically negative shifts are illegal
			 * but we can support them, at least with
			 * constants; you take potluck with variables.
			 */
			p->in.right->tn.lval = -p->in.right->tn.lval;
			switch( o ){
			case LS:	p->in.op = RS; break;
			case ASG LS:	p->in.op = ASG RS; break;
			case RS:	p->in.op = LS; break;
			case ASG RS:	p->in.op = ASG LS; break;
				}
			}
		break;

	case ASG DIV:
	case DIV:
		if( nncon( p->in.right ) ){
			if( RV(p) == 0 ) uerror("division by zero");
			else if( RV(p) == 1 ) goto zapright;
			/* Unsigned division by a power of two */
			else if( (i=ispow2(RV(p)))>=0 &&
				 (ISUNSIGNED(p->in.left->in.type) ||
				  ISUNSIGNED(p->in.right->in.type)) ){
				p->in.op = (asgop(o) ? ASG RS : RS);
				p->in.right->in.type = p->in.right->fn.csiz = INT;
				RV(p) = i;
				}
			}
		break;

	case ASG MOD:
	case MOD:
		if( nncon(p->in.right) ){
			if( RV(p) == 0 ) uerror("modulus of zero");
			else if( RV(p) == 1 ){ /* mod by one gives zero */
				RV(p) = 0;
				if( asgop(o) )
					p->in.op = ASSIGN;
				else if( optype(LO(p)) == LTYPE ) {
					p->in.op = FREE;
					LO(p) = FREE;
					p = p->in.right;
					}
				else
					p->in.op = COMOP; /* side effects */
				}
			else if ((i=ispow2(RV(p)))>=0 &&
				 (ISUNSIGNED(p->in.left->in.type) ||
				  ISUNSIGNED(p->in.right->in.type)) ){
				/* Unsigned mod by a power of two */
				p->in.op = (asgop(o) ? ASG AND : AND);
				RV(p)--;
				}
			}
		break;

	case EQ:
	case NE:
	case LT:
	case LE:
	case GT:
	case GE:
	case ULT:
	case ULE:
	case UGT:
	case UGE:
		if( !LCON(p) ) break;

		/* exchange operands */

		sp = p->in.left;
		p->in.left = p->in.right;
		p->in.right = sp;
		p->in.op = revrel[p->in.op - EQ ];
		break;

		}

	return(p);
	}

ispow2( c ) CONSZ c; {
	register i;
	if( c <= 0 || (c&(c-1)) ) return(-1);
	for( i=0; c>1; ++i) c >>= 1;
	return(i);
	}
Commit	Line	Data
262eaf56	1	#ifndef lint
95f51977	2	static char *sccsid ="@(#)optim.c 4.7 (Berkeley) 1/8/86";
262eaf56 RC	3	#endif lint
262eaf56 RC	4
69023ebb	5	# include "pass1.h"
ea305ab4 RC	6
	7	# define SWAP(p,q) {sp=p; p=q; q=sp;}
	8	# define RCON(p) (p->in.right->in.op==ICON)
	9	# define RO(p) p->in.right->in.op
	10	# define RV(p) p->in.right->tn.lval
	11	# define LCON(p) (p->in.left->in.op==ICON)
	12	# define LO(p) p->in.left->in.op
	13	# define LV(p) p->in.left->tn.lval
	14
3464f46e KM	15	/* is p a constant without a name */
	16	# define nncon(p) ((p)->in.op == ICON && (p)->tn.rval == NONAME)
	17
ea305ab4 RC	18	int oflag = 0;
	19
	20	NODE *
	21	fortarg( p ) NODE *p; {
	22	/* fortran function arguments */
	23
	24	if( p->in.op == CM ){
	25	p->in.left = fortarg( p->in.left );
	26	p->in.right = fortarg( p->in.right );
	27	return(p);
	28	}
	29
	30	while( ISPTR(p->in.type) ){
	31	p = buildtree( UNARY MUL, p, NIL );
	32	}
	33	return( optim(p) );
	34	}
	35
	36	/* mapping relationals when the sides are reversed */
	37	short revrel[] ={ EQ, NE, GE, GT, LE, LT, UGE, UGT, ULE, ULT };
	38	NODE *
	39	optim(p) register NODE *p; {
	40	/* local optimizations, most of which are probably machine independent */
	41
	42	register o, ty;
	43	NODE *sp;
	44	int i;
	45	TWORD t;
	46
	47	if( (t=BTYPE(p->in.type))==ENUMTY \|\| t==MOETY ) econvert(p);
	48	if( oflag ) return(p);
	49	ty = optype( o=p->in.op);
	50	if( ty == LTYPE ) return(p);
	51
	52	if( ty == BITYPE ) p->in.right = optim(p->in.right);
	53	p->in.left = optim(p->in.left);
	54
	55	/* collect constants */
	56
	57	switch(o){
	58
	59	case SCONV:
	60	case PCONV:
	61	return( clocal(p) );
	62
	63	case FORTCALL:
	64	p->in.right = fortarg( p->in.right );
	65	break;
	66
	67	case UNARY AND:
69d46158	68	if( LO(p) != NAME \|\| !andable(p->in.left) ) return(p);
ea305ab4 RC	69
	70	LO(p) = ICON;
	71
	72	setuleft:
	73	/* paint over the type of the left hand side with the type of the top */
	74	p->in.left->in.type = p->in.type;
	75	p->in.left->fn.cdim = p->fn.cdim;
	76	p->in.left->fn.csiz = p->fn.csiz;
	77	p->in.op = FREE;
	78	return( p->in.left );
	79
	80	case UNARY MUL:
	81	if( LO(p) != ICON ) break;
	82	LO(p) = NAME;
	83	goto setuleft;
	84
	85	case MINUS:
	86	if( !nncon(p->in.right) ) break;
	87	RV(p) = -RV(p);
	88	o = p->in.op = PLUS;
	89
	90	case MUL:
	91	case PLUS:
	92	case AND:
	93	case OR:
	94	case ER:
	95	/* commutative ops; for now, just collect constants */
	96	/* someday, do it right */
	97	if( nncon(p->in.left) \|\| ( LCON(p) && !RCON(p) ) ) SWAP( p->in.left, p->in.right );
	98	/* make ops tower to the left, not the right */
	99	if( RO(p) == o ){
	100	NODE t1, t2, *t3;
	101	t1 = p->in.left;
	102	sp = p->in.right;
	103	t2 = sp->in.left;
	104	t3 = sp->in.right;
	105	/* now, put together again */
	106	p->in.left = sp;
	107	sp->in.left = t1;
	108	sp->in.right = t2;
	109	p->in.right = t3;
	110	}
	111	if(o == PLUS && LO(p) == MINUS && RCON(p) && RCON(p->in.left) &&
3464f46e	112	conval(p->in.right, MINUS, p->in.left->in.right)){
ea305ab4 RC	113	zapleft:
	114	RO(p->in.left) = FREE;
	115	LO(p) = FREE;
	116	p->in.left = p->in.left->in.left;
	117	}
3464f46e KM	118	if( RCON(p) && LO(p)==o && RCON(p->in.left) &&
3464f46e KM	119	conval( p->in.right, o, p->in.left->in.right ) ){
ea305ab4 RC	120	goto zapleft;
ea305ab4 RC	121	}
3464f46e KM	122	else if( LCON(p) && RCON(p) &&
3464f46e KM	123	conval( p->in.left, o, p->in.right ) ){
ea305ab4 RC	124	zapright:
	125	RO(p) = FREE;
	126	p->in.left = makety( p->in.left, p->in.type, p->fn.cdim, p->fn.csiz );
	127	p->in.op = FREE;
	128	return( clocal( p->in.left ) );
	129	}
3464f46e	130	/* FALL THROUGH */
ea305ab4	131
3464f46e KM	132	case ASG MUL:
3464f46e KM	133	/* change muls to adds or shifts */
ea305ab4	134
3464f46e KM	135	if( (o == MUL \|\| o == ASG MUL) &&
	136	nncon(p->in.right) && (i=ispow2(RV(p)))>=0){
	137	if( i == 0 ) /* multiplication by 1 */
ea305ab4	138	goto zapright;
c09c8c00	139	/* c2 will turn 'i << 1' into 'i + i' for us */
3464f46e KM	140	else {
	141	p->in.op = (asgop(o) ? ASG LS : LS);
	142	o = p->in.op;
	143	p->in.right->in.type = p->in.right->fn.csiz = INT;
	144	RV(p) = i;
ea305ab4	145	}
ea305ab4 RC	146	}
	147
	148	/* change +'s of negative consts back to - */
	149	if( o==PLUS && nncon(p->in.right) && RV(p)<0 ){
	150	RV(p) = -RV(p);
	151	o = p->in.op = MINUS;
	152	}
3464f46e KM	153	/* FALL THROUGH */
	154	case ASG AND:
	155	case ASG PLUS:
	156	case ASG MINUS:
2cc78946 RC	157	case RS:
2cc78946 RC	158	case LS:
3464f46e KM	159	/* Operations with zero */
	160	if( nncon(p->in.right) && RV(p) == 0 ) {
	161	if( o == MUL \|\| o == ASG MUL \|\|
	162	o == AND \|\| o == ASG AND ) {
	163	if( asgop(o) )
	164	p->in.op = ASSIGN;
	165	else if( optype(LO(p)) == LTYPE ) {
	166	p->in.op = FREE;
	167	LO(p) = FREE;
	168	p = p->in.right;
	169	}
	170	else
	171	p->in.op = COMOP; /* side effects */
	172	}
	173	else if( o == PLUS \|\| o == MINUS \|\|
	174	o == ASG PLUS \|\| o == ASG MINUS \|\|
	175	o == OR \|\| o == ER \|\|
	176	o == LS \|\| o == RS )
	177	goto zapright;
	178	}
c09c8c00 DS	179	if( o != LS && o != RS )
	180	break;
	181	/* FALL THROUGH */
	182
	183	case ASG RS:
	184	case ASG LS:
	185	if( !ISUNSIGNED(p->in.left->in.type) )
	186	break;
	187	if( p->in.right->in.op == ICON &&
	188	p->in.right->tn.lval < 0 ) {
	189	/*
	190	* Technically negative shifts are illegal
	191	* but we can support them, at least with
	192	* constants; you take potluck with variables.
	193	*/
	194	p->in.right->tn.lval = -p->in.right->tn.lval;
	195	switch( o ){
	196	case LS: p->in.op = RS; break;
	197	case ASG LS: p->in.op = ASG RS; break;
	198	case RS: p->in.op = LS; break;
	199	case ASG RS: p->in.op = ASG LS; break;
	200	}
	201	}
3464f46e	202	break;
ea305ab4	203
3464f46e	204	case ASG DIV:
ea305ab4	205	case DIV:
3464f46e KM	206	if( nncon( p->in.right ) ){
	207	if( RV(p) == 0 ) uerror("division by zero");
	208	else if( RV(p) == 1 ) goto zapright;
	209	/* Unsigned division by a power of two */
	210	else if( (i=ispow2(RV(p)))>=0 &&
	211	(ISUNSIGNED(p->in.left->in.type) \|\|
	212	ISUNSIGNED(p->in.right->in.type)) ){
	213	p->in.op = (asgop(o) ? ASG RS : RS);
	214	p->in.right->in.type = p->in.right->fn.csiz = INT;
	215	RV(p) = i;
	216	}
2cc78946 RC	217	}
	218	break;
	219
3464f46e	220	case ASG MOD:
2cc78946	221	case MOD:
3464f46e KM	222	if( nncon(p->in.right) ){
	223	if( RV(p) == 0 ) uerror("modulus of zero");
	224	else if( RV(p) == 1 ){ /* mod by one gives zero */
	225	RV(p) = 0;
	226	if( asgop(o) )
	227	p->in.op = ASSIGN;
	228	else if( optype(LO(p)) == LTYPE ) {
	229	p->in.op = FREE;
	230	LO(p) = FREE;
	231	p = p->in.right;
	232	}
	233	else
	234	p->in.op = COMOP; /* side effects */
	235	}
	236	else if ((i=ispow2(RV(p)))>=0 &&
	237	(ISUNSIGNED(p->in.left->in.type) \|\|
	238	ISUNSIGNED(p->in.right->in.type)) ){
	239	/* Unsigned mod by a power of two */
	240	p->in.op = (asgop(o) ? ASG AND : AND);
	241	RV(p)--;
	242	}
2cc78946	243	}
ea305ab4 RC	244	break;
	245
	246	case EQ:
	247	case NE:
	248	case LT:
	249	case LE:
	250	case GT:
	251	case GE:
	252	case ULT:
	253	case ULE:
	254	case UGT:
	255	case UGE:
	256	if( !LCON(p) ) break;
	257
	258	/* exchange operands */
	259
	260	sp = p->in.left;
	261	p->in.left = p->in.right;
	262	p->in.right = sp;
	263	p->in.op = revrel[p->in.op - EQ ];
	264	break;
	265
	266	}
	267
	268	return(p);
	269	}
	270
	271	ispow2( c ) CONSZ c; {
	272	register i;
	273	if( c <= 0 \|\| (c&(c-1)) ) return(-1);
	274	for( i=0; c>1; ++i) c >>= 1;
	275	return(i);
	276	}