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