4.3BSD - /usr/src/lib/mip/optim.c

   1: #ifndef lint
   2: static char *sccsid ="@(#)optim.c	4.7 (Berkeley) 1/8/86";
   3: #endif lint
   4: 
   5: # include "pass1.h"
   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: 
  15:     /* is p a constant without a name */
  16: # define nncon(p)   ((p)->in.op == ICON && (p)->tn.rval == NONAME)
  17: 
  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:
  68:         if( LO(p) != NAME || !andable(p->in.left) ) return(p);
  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) &&
 112:            conval(p->in.right, MINUS, p->in.left->in.right)){
 113:             zapleft:
 114:             RO(p->in.left) = FREE;
 115:             LO(p) = FREE;
 116:             p->in.left = p->in.left->in.left;
 117:         }
 118:         if( RCON(p) && LO(p)==o && RCON(p->in.left) &&
 119:             conval( p->in.right, o, p->in.left->in.right ) ){
 120:             goto zapleft;
 121:             }
 122:         else if( LCON(p) && RCON(p) &&
 123:              conval( p->in.left, o, p->in.right ) ){
 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:             }
 130:         /* FALL THROUGH */
 131: 
 132:     case ASG MUL:
 133:         /* change muls to adds or shifts */
 134: 
 135:         if( (o == MUL || o == ASG MUL) &&
 136:             nncon(p->in.right) && (i=ispow2(RV(p)))>=0){
 137:             if( i == 0 ) /* multiplication by 1 */
 138:                 goto zapright;
 139:             /* c2 will turn 'i << 1' into 'i + i' for us */
 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;
 145:                 }
 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:             }
 153:         /* FALL THROUGH */
 154:     case ASG AND:
 155:     case ASG PLUS:
 156:     case ASG MINUS:
 157:     case RS:
 158:     case LS:
 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:             }
 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:             }
 202:         break;
 203: 
 204:     case ASG DIV:
 205:     case DIV:
 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:                 }
 217:             }
 218:         break;
 219: 
 220:     case ASG MOD:
 221:     case MOD:
 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:                 }
 243:             }
 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:     }

Defined functions

Defined variables

Defined macros