1: /*
   2:  *		C compiler part 2 -- expression optimizer
   3:  */
   4: 
   5: #include "c1.h"
   6: #include <sys/param.h>      /* for MAX */
   7: 
   8: union tree *
   9: optim(tree)
  10: register union tree *tree;
  11: {
  12:     register op, dope;
  13:     int d1, d2;
  14:     union tree *t;
  15:     union { double dv; int iv[4];} fp11;
  16: 
  17:     if (tree==NULL)
  18:         return(NULL);
  19:     if ((op = tree->t.op)==0)
  20:         return(tree);
  21:     if (op==NAME && tree->n.class==AUTO) {
  22:         tree->n.class = OFFS;
  23:         tree->n.regno = 5;
  24:         tree->n.offset = tree->n.nloc;
  25:     }
  26:     dope = opdope[op];
  27:     if ((dope&LEAF) != 0) {
  28:         if (op==FCON) {
  29:             fp11.dv = tree->f.fvalue;
  30:             if (fp11.iv[1]==0
  31:              && fp11.iv[2]==0
  32:              && fp11.iv[3]==0) {
  33:                 tree->t.op = SFCON;
  34:                 tree->f.value = fp11.iv[0];
  35:             }
  36:         }
  37:         return(tree);
  38:     }
  39:     if ((dope&BINARY) == 0)
  40:         return(unoptim(tree));
  41:     /* is known to be binary */
  42:     if (tree->t.type==CHAR)
  43:         tree->t.type = INT;
  44:     switch(op) {
  45:     /*
  46: 	 * PDP-11 special:
  47: 	 * generate new &=~ operator out of &=
  48: 	 * by complementing the RHS.
  49: 	 */
  50:     case ASAND:
  51:         tree->t.op = ASANDN;
  52:         tree->t.tr2 = tnode(COMPL, tree->t.tr2->t.type, tree->t.tr2, TNULL);
  53:         break;
  54: 
  55:     /*
  56: 	 * On the PDP-11, int->ptr via multiplication
  57: 	 * Longs are just truncated.
  58: 	 */
  59:     case LTOP:
  60:         tree->t.op = ITOP;
  61:         tree->t.tr1 = unoptim(tnode(LTOI,INT,tree->t.tr1, TNULL));
  62:     case ITOP:
  63:         tree->t.op = TIMES;
  64:         break;
  65: 
  66:     case MINUS:
  67:         if ((t = isconstant(tree->t.tr2)) && (!uns(t) || tree->t.type!=LONG)
  68:          && (t->t.type!=INT || t->c.value!=0100000)) {
  69:             tree->t.op = PLUS;
  70:             if (t->t.type==DOUBLE)
  71:                 /* PDP-11 FP representation */
  72:                 t->c.value ^= 0100000;
  73:             else
  74:                 t->c.value = -t->c.value;
  75:         }
  76:         break;
  77:     }
  78:     op = tree->t.op;
  79:     dope = opdope[op];
  80:     if (dope&LVALUE && tree->t.tr1->t.op==FSEL)
  81:         return(lvfield(tree));
  82:     if ((dope&COMMUTE)!=0) {
  83:         d1 = tree->t.type;
  84:         tree = acommute(tree);
  85:         if (tree->t.op == op)
  86:             tree->t.type = d1;
  87:         /*
  88: 		 * PDP-11 special:
  89: 		 * replace a&b by a ANDN ~ b.
  90: 		 * This will be undone when in
  91: 		 * truth-value context.
  92: 		 */
  93:         if (tree->t.op!=AND)
  94:             return(tree);
  95:         /*
  96: 		 * long & pos-int is simpler
  97: 		 */
  98:         if ((tree->t.type==LONG || tree->t.type==UNLONG) && tree->t.tr2->t.op==ITOL
  99:          && (tree->t.tr2->t.tr1->t.op==CON && tree->t.tr2->t.tr1->c.value>=0
 100:            || uns(tree->t.tr2->t.tr1))) {
 101:             tree->t.type = UNSIGN;
 102:             t = tree->t.tr2;
 103:             tree->t.tr2 = tree->t.tr2->t.tr1;
 104:             t->t.tr1 = tree;
 105:             tree->t.tr1 = tnode(LTOI, UNSIGN, tree->t.tr1, TNULL);
 106:             return(optim(t));
 107:         }
 108:         /*
 109: 		 * Keep constants to the right
 110: 		 */
 111:         if ((tree->t.tr1->t.op==ITOL && tree->t.tr1->t.tr1->t.op==CON)
 112:           || tree->t.tr1->t.op==LCON) {
 113:             t = tree->t.tr1;
 114:             tree->t.tr1 = tree->t.tr2;
 115:             tree->t.tr2 = t;
 116:         }
 117:         tree->t.op = ANDN;
 118:         op = ANDN;
 119:         tree->t.tr2 = tnode(COMPL, tree->t.tr2->t.type, tree->t.tr2, TNULL);
 120:     }
 121:     again:
 122:     tree->t.tr1 = optim(tree->t.tr1);
 123:     tree->t.tr2 = optim(tree->t.tr2);
 124:     if (tree->t.type == LONG || tree->t.type==UNLONG) {
 125:         t = lconst(tree->t.op, tree->t.tr1, tree->t.tr2);
 126:         if (t)
 127:             return(t);
 128:     }
 129:     if ((dope&RELAT) != 0) {
 130:         if ((d1=degree(tree->t.tr1)) < (d2=degree(tree->t.tr2))
 131:          || d1==d2 && tree->t.tr1->t.op==NAME && tree->t.tr2->t.op!=NAME) {
 132:             t = tree->t.tr1;
 133:             tree->t.tr1 = tree->t.tr2;
 134:             tree->t.tr2 = t;
 135:             tree->t.op = maprel[op-EQUAL];
 136:         }
 137:         if (tree->t.tr1->t.type==CHAR && tree->t.tr2->t.op==CON
 138:          && (dcalc(tree->t.tr1, 0) <= 12 || tree->t.tr1->t.op==STAR)
 139:          && tree->t.tr2->c.value <= 127 && tree->t.tr2->c.value >= 0)
 140:             tree->t.tr2->t.type = CHAR;
 141:     }
 142:     d1 = MAX(degree(tree->t.tr1), islong(tree->t.type));
 143:     d2 = MAX(degree(tree->t.tr2), 0);
 144:     switch (op) {
 145: 
 146:     /*
 147: 	 * In assignment to fields, treat all-zero and all-1 specially.
 148: 	 */
 149:     case FSELA:
 150:         if (tree->t.tr2->t.op==CON && tree->t.tr2->c.value==0) {
 151:             tree->t.op = ASAND;
 152:             tree->t.tr2->c.value = ~tree->F.mask;
 153:             return(optim(tree));
 154:         }
 155:         if (tree->t.tr2->t.op==CON && tree->F.mask==tree->t.tr2->c.value) {
 156:             tree->t.op = ASOR;
 157:             return(optim(tree));
 158:         }
 159: 
 160:     case LTIMES:
 161:     case LDIV:
 162:     case LMOD:
 163:     case LASTIMES:
 164:     case LASDIV:
 165:     case LASMOD:
 166:     case UDIV:
 167:     case UMOD:
 168:     case ASUDIV:
 169:     case ASUMOD:
 170:     case ULASMOD:
 171:     case ULTIMES:
 172:     case ULDIV:
 173:     case ULMOD:
 174:     case ULASTIMES:
 175:     case ULASDIV:
 176:         tree->t.degree = 10;
 177:         break;
 178: 
 179:     case ANDN:
 180:         if (isconstant(tree->t.tr2) && tree->t.tr2->c.value==0) {
 181:             return(tree->t.tr1);
 182:         }
 183:         goto def;
 184: 
 185:     case CALL:
 186:         tree->t.degree = 10;
 187:         break;
 188: 
 189:     case QUEST:
 190:     case COLON:
 191:         tree->t.degree = MAX(d1, d2);
 192:         break;
 193: 
 194:     case PTOI:
 195:     case DIVIDE:
 196:     case ASDIV:
 197:     case ASTIMES:
 198:         if (tree->t.tr2->t.op==CON && tree->t.tr2->c.value==1) {
 199:             if (op==PTOI)
 200:                 return(optim(tnode(LTOI,INT,paint(tree->t.tr1,LONG), TNULL)));
 201:             return(paint(tree->t.tr1, tree->t.type));
 202:         }
 203:     case MOD:
 204:     case ASMOD:
 205:         if ((uns(tree->t.tr1) || tree->t.op==PTOI) && ispow2(tree))
 206:             return(pow2(tree));
 207:         if ((op==MOD||op==ASMOD) && tree->t.type==DOUBLE) {
 208:             error("Floating %% not defined");
 209:             tree->t.type = INT;
 210:         }
 211:     case ULSH:
 212:     case ASULSH:
 213:         d1 += 2 + regpanic;
 214:         d2 += 2 + regpanic;
 215:         panicposs++;
 216:         if (tree->t.type==LONG || tree->t.type==UNLONG)
 217:             return(hardlongs(tree));
 218:         if ((op==MOD || op==DIVIDE || op==ASMOD || op==ASDIV)
 219:          && (uns(tree->t.tr1) || uns(tree->t.tr2))
 220:          && (tree->t.tr2->t.op!=CON || tree->t.tr2->c.value<=1)) {
 221:             if (op>=ASDIV) {
 222:                 tree->t.op += ASUDIV - ASDIV;
 223:             } else
 224:                 tree->t.op += UDIV - DIVIDE;
 225:             d1 = d2 = 10;
 226:         }
 227:         goto constant;
 228: 
 229:     case ASPLUS:
 230:     case ASMINUS:
 231:         if (tree->t.tr2->t.op==CON && tree->t.tr2->c.value==0)
 232:             return(tree->t.tr1);
 233:         goto def;
 234: 
 235:     case LSHIFT:
 236:     case RSHIFT:
 237:     case ASRSH:
 238:     case ASLSH:
 239:         if (tree->t.tr2->t.op==CON && tree->t.tr2->c.value==0)
 240:             return(paint(tree->t.tr1, tree->t.type));
 241:         /*
 242: 		 * PDP-11 special: turn right shifts into negative
 243: 		 * left shifts
 244: 		 */
 245:         if (tree->t.type == LONG || tree->t.type==UNLONG) {
 246:             d1++;
 247:             d2++;
 248:         }
 249:         if (op==LSHIFT||op==ASLSH)
 250:             goto constant;
 251:         if (tree->t.tr2->t.op==CON && tree->t.tr2->c.value==1
 252:          && !uns(tree->t.tr1) && !uns(tree->t.tr2))
 253:             goto constant;
 254:         op += (LSHIFT-RSHIFT);
 255:         tree->t.op = op;
 256:         tree->t.tr2 = tnode(NEG, tree->t.tr2->t.type, tree->t.tr2, TNULL);
 257:         if (uns(tree->t.tr1) || uns(tree->t.tr2)) {
 258:             if (tree->t.op==LSHIFT)
 259:                 tree->t.op = ULSH;
 260:             else if (tree->t.op==ASLSH)
 261:                 tree->t.op = ASULSH;
 262:         }
 263:         goto again;
 264: 
 265:     constant:
 266:         if (tree->t.tr1->t.op==CON && tree->t.tr2->t.op==CON) {
 267:             const(op, &tree->t.tr1->c.value, tree->t.tr2->c.value, tree->t.type);
 268:             return(tree->t.tr1);
 269:         }
 270: 
 271: 
 272:     def:
 273:     default:
 274:         if (dope&RELAT) {
 275:             if (tree->t.tr1->t.type==LONG || tree->t.tr1->t.type==UNLONG)   /* long relations are a mess */
 276:                 d1 = 10;
 277:             if (opdope[tree->t.tr1->t.op]&RELAT && tree->t.tr2->t.op==CON
 278:              && tree->t.tr2->c.value==0) {
 279:                 tree = tree->t.tr1;
 280:                 switch(op) {
 281:                 case GREATEQ:
 282:                     return((union tree *)&cone);
 283:                 case LESS:
 284:                     return((union tree *)&czero);
 285:                 case LESSEQ:
 286:                 case EQUAL:
 287:                     tree->t.op = notrel[tree->t.op-EQUAL];
 288:                 }
 289:                 return(tree);
 290:             }
 291:         }
 292:         tree->t.degree = d1==d2? d1+islong(tree->t.type): MAX(d1, d2);
 293:         break;
 294:     }
 295:     return(tree);
 296: }
 297: 
 298: union tree *
 299: unoptim(tree)
 300: register union tree *tree;
 301: {
 302:     register union tree *subtre, *p;
 303: 
 304:     if (tree==NULL)
 305:         return(NULL);
 306:     again:
 307:     if (tree->t.op==AMPER && tree->t.tr1->t.op==STAR) {
 308:         subtre = tree->t.tr1->t.tr1;
 309:         subtre->t.type = tree->t.type;
 310:         return(optim(subtre));
 311:     }
 312:     subtre = tree->t.tr1 = optim(tree->t.tr1);
 313:     switch (tree->t.op) {
 314: 
 315:     case INCAFT:
 316:     case DECAFT:
 317:         if (tree->t.type!=subtre->t.type)
 318:             paint(subtre, tree->t.type);
 319:         break;
 320: 
 321:     case ITOL:
 322:         if (subtre->t.op==CON && subtre->t.type==INT && subtre->c.value<0) {
 323:             subtre = getblk(sizeof(struct lconst));
 324:             subtre->t.op = LCON;
 325:             subtre->t.type = LONG;
 326:             subtre->l.lvalue = tree->t.tr1->c.value;
 327:             return(subtre);
 328:         }
 329:         break;
 330: 
 331:     case FTOI:
 332:         if (uns(tree)) {
 333:             tree->t.op = FTOL;
 334:             tree->t.type = LONG;
 335:             tree = tnode(LTOI, UNSIGN, tree, TNULL);
 336:         }
 337:         break;
 338: 
 339:     case LTOF:
 340:         if (subtre->t.op==LCON) {
 341:             tree = getblk(sizeof(struct ftconst));
 342:             tree->t.op = FCON;
 343:             tree->t.type = DOUBLE;
 344:             tree->c.value = isn++;
 345:             tree->f.fvalue = subtre->l.lvalue;
 346:             return(optim(tree));
 347:         }
 348:         if (subtre->t.type==UNLONG)
 349:             tree->t.op = ULTOF;
 350:         break;
 351: 
 352:     case ITOF:
 353:         if (subtre->t.op==CON) {
 354:             tree = getblk(sizeof(struct ftconst));
 355:             tree->t.op = FCON;
 356:             tree->t.type = DOUBLE;
 357:             tree->f.value = isn++;
 358:             if (uns(subtre))
 359:                 tree->f.fvalue = (unsigned)subtre->c.value;
 360:             else
 361:                 tree->f.fvalue = subtre->c.value;
 362:             return(optim(tree));
 363:         }
 364:         if (uns(subtre)) {
 365:             tree->t.tr1 = tnode(ITOL, LONG, subtre, TNULL);
 366:             tree->t.op = LTOF;
 367:             return(optim(tree));
 368:         }
 369:         break;
 370: 
 371:     case ITOC:
 372:         /*
 373: 		 * Sign-extend PDP-11 characters
 374: 		 */
 375:         if (subtre->t.op==CON) {
 376:             char c;
 377:             c = subtre->c.value;
 378:             subtre->c.value = c;
 379:             subtre->t.type = tree->t.type;
 380:             return(subtre);
 381:         } else if (subtre->t.op==NAME && tree->t.type==INT) {
 382:             subtre->t.type = CHAR;
 383:             return(subtre);
 384:         }
 385:         break;
 386: 
 387:     case LTOI:
 388:         switch (subtre->t.op) {
 389: 
 390:         case LCON:
 391:             subtre->t.op = CON;
 392:             subtre->t.type = tree->t.type;
 393:             subtre->c.value = subtre->l.lvalue;
 394:             return(subtre);
 395: 
 396:         case NAME:
 397:             subtre->n.offset += 2;
 398:             subtre->t.type = tree->t.type;
 399:             return(subtre);
 400: 
 401:         case STAR:
 402:             subtre->t.type = tree->t.type;
 403:             subtre->t.tr1->t.type = tree->t.type+PTR;
 404:             subtre->t.tr1 = tnode(PLUS, tree->t.type, subtre->t.tr1, tconst(2, INT));
 405:             return(optim(subtre));
 406: 
 407:         case ITOL:
 408:             return(paint(subtre->t.tr1, tree->t.type));
 409: 
 410:         case PLUS:
 411:         case MINUS:
 412:         case AND:
 413:         case ANDN:
 414:         case OR:
 415:         case EXOR:
 416:             subtre->t.tr2 = tnode(LTOI, tree->t.type, subtre->t.tr2, TNULL);
 417:         case NEG:
 418:         case COMPL:
 419:             subtre->t.tr1 = tnode(LTOI, tree->t.type, subtre->t.tr1, TNULL);
 420:             subtre->t.type = tree->t.type;
 421:             return(optim(subtre));
 422:         }
 423:         break;
 424: 
 425:     case FSEL:
 426:         tree->t.op = AND;
 427:         tree->t.tr1 = tree->t.tr2->t.tr1;
 428:         tree->t.tr2->t.tr1 = subtre;
 429:         tree->t.tr2->t.op = RSHIFT;
 430:         tree->t.tr1->c.value = (1 << tree->t.tr1->c.value) - 1;
 431:         return(optim(tree));
 432: 
 433:     case FSELR:
 434:         tree->t.op = LSHIFT;
 435:         tree->t.type = UNSIGN;
 436:         tree->t.tr1 = tree->t.tr2;
 437:         tree->t.tr1->t.op = AND;
 438:         tree->t.tr2 = tree->t.tr2->t.tr2;
 439:         tree->t.tr1->t.tr2 = subtre;
 440:         tree->t.tr1->t.tr1->c.value = (1 << tree->t.tr1->t.tr1->c.value) -1;
 441:         return(optim(tree));
 442: 
 443:     case AMPER:
 444:         if (subtre->t.op==STAR)
 445:             return(subtre->t.tr1);
 446:         if (subtre->t.op==NAME && subtre->n.class == OFFS) {
 447:             p = tnode(PLUS, tree->t.type, subtre, tree);
 448:             subtre->t.type = tree->t.type;
 449:             tree->t.op = CON;
 450:             tree->t.type = INT;
 451:             tree->t.degree = 0;
 452:             tree->c.value = subtre->n.offset;
 453:             subtre->n.class = REG;
 454:             subtre->n.nloc = subtre->n.regno;
 455:             subtre->n.offset = 0;
 456:             return(optim(p));
 457:         }
 458:         if (subtre->t.op==LOAD) {
 459:             tree->t.tr1 = subtre->t.tr1;
 460:             goto again;
 461:         }
 462:         break;
 463: 
 464:     case STAR:
 465:         if (subtre->t.op==AMPER) {
 466:             subtre->t.tr1->t.type = tree->t.type;
 467:             return(subtre->t.tr1);
 468:         }
 469:         if (tree->t.type==STRUCT)
 470:             break;
 471:         if (subtre->t.op==NAME && subtre->n.class==REG) {
 472:             subtre->t.type = tree->t.type;
 473:             subtre->n.class = OFFS;
 474:             subtre->n.regno = subtre->n.nloc;
 475:             return(subtre);
 476:         }
 477:         p = subtre->t.tr1;
 478:         if ((subtre->t.op==INCAFT||subtre->t.op==DECBEF)
 479:          && tree->t.type!=LONG && tree->t.type!=UNLONG
 480:          && p->t.op==NAME && p->n.class==REG && p->t.type==subtre->t.type) {
 481:             p->t.type = tree->t.type;
 482:             p->t.op = subtre->t.op==INCAFT? AUTOI: AUTOD;
 483:             return(p);
 484:         }
 485:         if (subtre->t.op==PLUS && p->t.op==NAME && p->n.class==REG) {
 486:             if (subtre->t.tr2->t.op==CON) {
 487:                 p->n.offset += subtre->t.tr2->c.value;
 488:                 p->n.class = OFFS;
 489:                 p->t.type = tree->t.type;
 490:                 p->n.regno = p->n.nloc;
 491:                 return(p);
 492:             }
 493:             if (subtre->t.tr2->t.op==AMPER) {
 494:                 subtre = subtre->t.tr2->t.tr1;
 495:                 subtre->n.class += XOFFS-EXTERN;
 496:                 subtre->n.regno = p->n.nloc;
 497:                 subtre->t.type = tree->t.type;
 498:                 return(subtre);
 499:             }
 500:         }
 501:         if (subtre->t.op==MINUS && p->t.op==NAME && p->n.class==REG
 502:          && subtre->t.tr2->t.op==CON) {
 503:             p->n.offset -= subtre->t.tr2->c.value;
 504:             p->n.class = OFFS;
 505:             p->t.type = tree->t.type;
 506:             p->n.regno = p->n.nloc;
 507:             return(p);
 508:         }
 509:         break;
 510:     case EXCLA:
 511:         if ((opdope[subtre->t.op]&RELAT)==0)
 512:             break;
 513:         tree = subtre;
 514:         tree->t.op = notrel[tree->t.op-EQUAL];
 515:         break;
 516: 
 517:     case COMPL:
 518:         if (tree->t.type==CHAR)
 519:             tree->t.type = INT;
 520:         if (tree->t.op == subtre->t.op)
 521:             return(paint(subtre->t.tr1, tree->t.type));
 522:         if (subtre->t.op==CON) {
 523:             subtre->c.value = ~subtre->c.value;
 524:             return(paint(subtre, tree->t.type));
 525:         }
 526:         if (subtre->t.op==LCON) {
 527:             subtre->l.lvalue = ~subtre->l.lvalue;
 528:             return(subtre);
 529:         }
 530:         if (subtre->t.op==ITOL) {
 531:             if (subtre->t.tr1->t.op==CON) {
 532:                 tree = getblk(sizeof(struct lconst));
 533:                 tree->t.op = LCON;
 534:                 tree->t.type = LONG;
 535:                 if (uns(subtre->t.tr1))
 536:                     tree->l.lvalue = ~(long)(unsigned)subtre->t.tr1->c.value;
 537:                 else
 538:                     tree->l.lvalue = ~subtre->t.tr1->c.value;
 539:                 return(tree);
 540:             }
 541:             if (uns(subtre->t.tr1))
 542:                 break;
 543:             subtre->t.op = tree->t.op;
 544:             subtre->t.type = subtre->t.tr1->t.type;
 545:             tree->t.op = ITOL;
 546:             tree->t.type = LONG;
 547:             goto again;
 548:         }
 549: 
 550:     case NEG:
 551:         if (tree->t.type==CHAR)
 552:             tree->t.type = INT;
 553:         if (tree->t.op==subtre->t.op)
 554:             return(paint(subtre->t.tr1, tree->t.type));
 555:         if (subtre->t.op==CON) {
 556:             subtre->c.value = -subtre->c.value;
 557:             return(paint(subtre, tree->t.type));
 558:         }
 559:         if (subtre->t.op==LCON) {
 560:             subtre->l.lvalue = -subtre->l.lvalue;
 561:             return(subtre);
 562:         }
 563:         if (subtre->t.op==ITOL && subtre->t.tr1->t.op==CON) {
 564:             tree = getblk(sizeof(struct lconst));
 565:             tree->t.op = LCON;
 566:             tree->t.type = LONG;
 567:             if (uns(subtre->t.tr1))
 568:                 tree->l.lvalue = -(long)(unsigned)subtre->t.tr1->c.value;
 569:             else
 570:                 tree->l.lvalue = -subtre->t.tr1->c.value;
 571:             return(tree);
 572:         }
 573:         /*
 574: 		 * PDP-11 FP negation
 575: 		 */
 576:         if (subtre->t.op==SFCON) {
 577:             subtre->c.value ^= 0100000;
 578:             subtre->f.fvalue = -subtre->f.fvalue;
 579:             return(subtre);
 580:         }
 581:         if (subtre->t.op==FCON) {
 582:             subtre->f.fvalue = -subtre->f.fvalue;
 583:             return(subtre);
 584:         }
 585:     }
 586:     if ((opdope[tree->t.op]&LEAF)==0)
 587:         tree->t.degree = MAX(islong(tree->t.type), degree(subtre));
 588:     return(tree);
 589: }
 590: 
 591: /*
 592:  * Deal with assignments to partial-word fields.
 593:  * The game is that select(x) += y turns into
 594:  * select(x += select(y)) where the shifts and masks
 595:  * are chosen properly.  The outer select
 596:  * is discarded where the value doesn't matter.
 597:  * Sadly, overflow is undetected on += and the like.
 598:  * Pure assignment is handled specially.
 599:  */
 600: 
 601: union tree *
 602: lvfield(t)
 603: register union tree *t;
 604: {
 605:     register union tree *t1, *t2;
 606: 
 607:     switch (t->t.op) {
 608: 
 609:     case ASSIGN:
 610:         t2 = getblk(sizeof(struct fasgn));
 611:         t2->t.op = FSELA;
 612:         t2->t.type = UNSIGN;
 613:         t1 = t->t.tr1->t.tr2;
 614:         t2->F.mask = ((1<<t1->t.tr1->c.value)-1)<<t1->t.tr2->c.value;
 615:         t2->t.tr1 = t->t.tr1;
 616:         t2->t.tr2 = t->t.tr2;
 617:         t = t2;
 618: 
 619:     case ASANDN:
 620:     case ASPLUS:
 621:     case ASMINUS:
 622:     case ASOR:
 623:     case ASXOR:
 624:     case INCBEF:
 625:     case INCAFT:
 626:     case DECBEF:
 627:     case DECAFT:
 628:         t1 = t->t.tr1;
 629:         t1->t.op = FSELR;
 630:         t->t.tr1 = t1->t.tr1;
 631:         t1->t.tr1 = t->t.tr2;
 632:         t->t.tr2 = t1;
 633:         t1 = t1->t.tr2;
 634:         t1 = tnode(COMMA, INT, tconst(t1->t.tr1->c.value, INT),
 635:             tconst(t1->t.tr2->c.value, INT));
 636:         return(optim(tnode(FSELT, UNSIGN, t, t1)));
 637: 
 638:     }
 639:     error("Unimplemented field operator");
 640:     return(t);
 641: }
 642: 
 643: #define LSTSIZ  20
 644: struct acl {
 645:     int nextl;
 646:     int nextn;
 647:     union tree *nlist[LSTSIZ];
 648:     union tree *llist[LSTSIZ+1];
 649: };
 650: 
 651: union tree *
 652: acommute(tree)
 653: register union tree *tree;
 654: {
 655:     struct acl acl;
 656:     int d, i, op, flt, d1, type;
 657:     register union tree *t1, **t2;
 658:     union tree *t;
 659: 
 660:     acl.nextl = 0;
 661:     acl.nextn = 0;
 662:     op = tree->t.op;
 663:     type = tree->t.type;
 664:     flt = isfloat(tree);
 665:     insert(op, tree, &acl);
 666:     acl.nextl--;
 667:     t2 = &acl.llist[acl.nextl];
 668:     if (!flt) {
 669:         /* put constants together */
 670:         for (i=acl.nextl; i>0; i--) {
 671:             d = t2[-1]->t.type==UNSIGN||t2[0]->t.type==UNSIGN?UNSIGN:INT;
 672:             if (t2[0]->t.op==CON && t2[-1]->t.op==CON) {
 673:                 acl.nextl--;
 674:                 t2--;
 675:                 const(op, &t2[0]->c.value, t2[1]->c.value, d);
 676:                 t2[0]->t.type = d;
 677:             } else if (t = lconst(op, t2[-1], t2[0])) {
 678:                 acl.nextl--;
 679:                 t2--;
 680:                 t2[0] = t;
 681:             }
 682:         }
 683:     }
 684:     if (op==PLUS || op==OR) {
 685:         /* toss out "+0" */
 686:         if (acl.nextl>0 && ((t1 = isconstant(*t2)) && t1->c.value==0
 687:          || (*t2)->t.op==LCON && (*t2)->l.lvalue==0)) {
 688:             acl.nextl--;
 689:             t2--;
 690:         }
 691:         if (acl.nextl <= 0) {
 692:             if ((*t2)->t.type==CHAR || (*t2)->t.type==UNCHAR)
 693:                 *t2 = tnode(LOAD, tree->t.type, *t2, TNULL);
 694:             (*t2)->t.type = tree->t.type;
 695:             return(*t2);
 696:         }
 697:         /* subsume constant in "&x+c" */
 698:         if (op==PLUS && t2[0]->t.op==CON && t2[-1]->t.op==AMPER) {
 699:             t2--;
 700:             t2[0]->t.tr1->n.offset += t2[1]->c.value;
 701:             acl.nextl--;
 702:         }
 703:     } else if (op==TIMES || op==AND) {
 704:         t1 = acl.llist[acl.nextl];
 705:         if (t1->t.op==CON) {
 706:             if (t1->c.value==0) {
 707:                 for (i=0; i<acl.nextl; i++)
 708:                     if (sideeffects(acl.llist[i]))
 709:                         break;
 710:                 if (i==acl.nextl)
 711:                     return(t1);
 712:             }
 713:             if (op==TIMES && t1->c.value==1 && acl.nextl>0)
 714:                 if (--acl.nextl <= 0) {
 715:                     t1 = acl.llist[0];
 716:                     if (uns(tree))
 717:                         paint(t1, tree->t.type);
 718:                     return(t1);
 719:                 }
 720:         }
 721:     }
 722:     if (op==PLUS && !flt)
 723:         distrib(&acl);
 724:     tree = *(t2 = &acl.llist[0]);
 725:     d = MAX(degree(tree), islong(tree->t.type));
 726:     if (op==TIMES && !flt) {
 727:         d += regpanic+1;
 728:         panicposs++;
 729:     }
 730:     for (i=0; i<acl.nextl; i++) {
 731:         t1 = acl.nlist[i];
 732:         t1->t.tr2 = t = *++t2;
 733:         d1 = degree(t);
 734:         /*
 735: 		 * PDP-11 strangeness:
 736: 		 * rt. op of ^ must be in a register.
 737: 		 */
 738:         if (op==EXOR && dcalc(t, 0)<=12) {
 739:             t1->t.tr2 = t = optim(tnode(LOAD, t->t.type, t, TNULL));
 740:             d1 = t->t.degree;
 741:         }
 742:         t1->t.degree = d = d==d1? d+islong(t1->t.type): MAX(d, d1);
 743:         t1->t.tr1 = tree;
 744:         tree = t1;
 745:         if (tree->t.type==LONG || tree->t.type==UNLONG) {
 746:             if (tree->t.op==TIMES)
 747:                 tree = hardlongs(tree);
 748:             else if (tree->t.op==PLUS && (t = isconstant(tree->t.tr1))
 749:                    && t->c.value < 0 && !uns(t)) {
 750:                 tree->t.op = MINUS;
 751:                 t->c.value = - t->c.value;
 752:                 t = tree->t.tr1;
 753:                 tree->t.tr1 = tree->t.tr2;
 754:                 tree->t.tr2 = t;
 755:             }
 756:         }
 757:     }
 758:     if (tree->t.op==TIMES && ispow2(tree))
 759:         tree->t.degree = MAX(degree(tree->t.tr1), islong(tree->t.type));
 760:     paint(tree, type);
 761:     return(tree);
 762: }
 763: 
 764: sideeffects(tp)
 765: register union tree *tp;
 766: {
 767:     register dope;
 768: 
 769:     if (tp==NULL)
 770:         return(0);
 771:     dope = opdope[tp->t.op];
 772:     if (dope&LEAF) {
 773:         if (tp->t.op==AUTOI || tp->t.op==AUTOD)
 774:             return(1);
 775:         return(0);
 776:     }
 777:     if (dope&ASSGOP)
 778:         return(1);
 779:     switch(tp->t.op) {
 780:     case CALL:
 781:     case FSELA:
 782:     case STRASG:
 783:         return(1);
 784:     }
 785:     if (sideeffects(tp->t.tr1))
 786:         return(1);
 787:     if (dope&BINARY)
 788:         return(sideeffects(tp->t.tr2));
 789:     return(0);
 790: }
 791: 
 792: distrib(list)
 793: struct acl *list;
 794: {
 795: /*
 796:  * Find a list member of the form c1c2*x such
 797:  * that c1c2 divides no other such constant, is divided by
 798:  * at least one other (say in the form c1*y), and which has
 799:  * fewest divisors. Reduce this pair to c1*(y+c2*x)
 800:  * and iterate until no reductions occur.
 801:  */
 802:     register union tree **p1, **p2;
 803:     union tree *t;
 804:     int ndmaj, ndmin;
 805:     union tree **dividend, **divisor;
 806:     union tree **maxnod, **mindiv;
 807: 
 808:     loop:
 809:     maxnod = &list->llist[list->nextl];
 810:     ndmaj = 1000;
 811:     dividend = 0;
 812:     for (p1 = list->llist; p1 <= maxnod; p1++) {
 813:         if ((*p1)->t.op!=TIMES || (*p1)->t.tr2->t.op!=CON)
 814:             continue;
 815:         ndmin = 0;
 816:         for (p2 = list->llist; p2 <= maxnod; p2++) {
 817:             if (p1==p2 || (*p2)->t.op!=TIMES || (*p2)->t.tr2->t.op!=CON)
 818:                 continue;
 819:             if ((*p1)->t.tr2->c.value == (*p2)->t.tr2->c.value) {
 820:                 (*p2)->t.tr2 = (*p1)->t.tr1;
 821:                 (*p2)->t.op = PLUS;
 822:                 (*p1)->t.tr1 = (*p2);
 823:                 *p1 = optim(*p1);
 824:                 squash(p2, maxnod);
 825:                 list->nextl--;
 826:                 goto loop;
 827:             }
 828:             if (((*p2)->t.tr2->c.value % (*p1)->t.tr2->c.value) == 0)
 829:                 goto contmaj;
 830:             if (((*p1)->t.tr2->c.value % (*p2)->t.tr2->c.value) == 0) {
 831:                 ndmin++;
 832:                 mindiv = p2;
 833:             }
 834:         }
 835:         if (ndmin > 0 && ndmin < ndmaj) {
 836:             ndmaj = ndmin;
 837:             dividend = p1;
 838:             divisor = mindiv;
 839:         }
 840:     contmaj:;
 841:     }
 842:     if (dividend==0)
 843:         return;
 844:     t = list->nlist[--list->nextn];
 845:     p1 = dividend;
 846:     p2 = divisor;
 847:     t->t.op = PLUS;
 848:     t->t.type = (*p1)->t.type;
 849:     t->t.tr1 = (*p1);
 850:     t->t.tr2 = (*p2)->t.tr1;
 851:     (*p1)->t.tr2->c.value /= (*p2)->t.tr2->c.value;
 852:     (*p2)->t.tr1 = t;
 853:     t = optim(*p2);
 854:     if (p1 < p2) {
 855:         *p1 = t;
 856:         squash(p2, maxnod);
 857:     } else {
 858:         *p2 = t;
 859:         squash(p1, maxnod);
 860:     }
 861:     list->nextl--;
 862:     goto loop;
 863: }
 864: 
 865: squash(p, maxp)
 866: union tree **p, **maxp;
 867: {
 868:     register union tree **np;
 869: 
 870:     for (np = p; np < maxp; np++)
 871:         *np = *(np+1);
 872: }
 873: 
 874: const(op, vp, v, type)
 875: register int *vp, v;
 876: {
 877:     switch (op) {
 878: 
 879:     case PTOI:
 880:         (*vp) /= (unsigned)v;
 881:         return;
 882: 
 883:     case PLUS:
 884:         *vp += v;
 885:         return;
 886: 
 887:     case TIMES:
 888:         *vp *= v;
 889:         return;
 890: 
 891:     case AND:
 892:         *vp &= v;
 893:         return;
 894: 
 895:     case OR:
 896:         *vp |= v;
 897:         return;
 898: 
 899:     case EXOR:
 900:         *vp ^= v;
 901:         return;
 902: 
 903:     case UDIV:
 904:     case UMOD:
 905:         type = UNSIGN;
 906:     case DIVIDE:
 907:     case MOD:
 908:         if (type==UNSIGN && v!=0 && v<=1) {
 909:             if (op==UDIV || op==DIVIDE) {
 910:                 if (v==1)
 911:                     return;
 912:                 *vp = *(unsigned *)vp >= (unsigned)v;
 913:                 return;
 914:             } else {
 915:                 if (v==1) {
 916:                     *vp = 0;
 917:                     return;
 918:                 }
 919:                 if (*(unsigned *)vp >= (unsigned)v)
 920:                     *vp -= v;
 921:                 return;
 922:             }
 923:         }
 924:         if (v==0)
 925:             werror("divide check");
 926:         else
 927:             if (type==INT)
 928:                 if (op==DIVIDE || op==UDIV)
 929:                     *vp /= v;
 930:                 else
 931:                     *vp %= v;
 932:             else
 933:                 if (op==DIVIDE || op==UDIV)
 934:                     *(unsigned *)vp /= (unsigned)v;
 935:                 else
 936:                     *(unsigned *)vp %= (unsigned)v;
 937:             return;
 938: 
 939:     case RSHIFT:
 940:     rshift:
 941:         if (v<0) {
 942:             v = -v;
 943:             goto lshift;
 944:         }
 945:         if (type==INT)
 946:             *vp >>= v;
 947:         else
 948:             *(unsigned *)vp >>= (unsigned)v;
 949:         return;
 950: 
 951:     case ULSH:
 952:         type = UNSIGN;
 953: 
 954:     case LSHIFT:
 955:     lshift:
 956:         if (v<0) {
 957:             v = -v;
 958:             goto rshift;
 959:         }
 960:         if (type==INT)
 961:             *vp <<= v;
 962:         else
 963:             *(unsigned *)vp <<= (unsigned)v;
 964:         return;
 965: 
 966:     case ANDN:
 967:         *vp &= ~ v;
 968:         return;
 969:     }
 970:     error("C error: const");
 971: }
 972: 
 973: union tree *
 974: lconst(op, lp, rp)
 975: register union tree *lp, *rp;
 976: {
 977:     long l, r;
 978: 
 979:     if (lp->t.op==LCON)
 980:         l = lp->l.lvalue;
 981:     else if (lp->t.op==ITOL && lp->t.tr1->t.op==CON) {
 982:         if (lp->t.tr1->t.type==INT)
 983:             l = lp->t.tr1->c.value;
 984:         else
 985:             l = (unsigned)lp->t.tr1->c.value;
 986:     } else
 987:         return(0);
 988:     if (rp->t.op==LCON)
 989:         r = rp->l.lvalue;
 990:     else if (rp->t.op==ITOL && rp->t.tr1->t.op==CON) {
 991:         if (rp->t.tr1->t.type==INT)
 992:             r = rp->t.tr1->c.value;
 993:         else
 994:             r = (unsigned)rp->t.tr1->c.value;
 995:     } else
 996:         return(0);
 997:     switch (op) {
 998: 
 999:     case PLUS:
1000:         l += r;
1001:         break;
1002: 
1003:     case MINUS:
1004:         l -= r;
1005:         break;
1006: 
1007:     case TIMES:
1008:     case LTIMES:
1009:         l *= r;
1010:         break;
1011: 
1012:     case DIVIDE:
1013:     case LDIV:
1014:         if (r==0)
1015:             error("Divide check");
1016:         else
1017:             l /= r;
1018:         break;
1019: 
1020:     case MOD:
1021:     case LMOD:
1022:         if (r==0)
1023:             error("Divide check");
1024:         else
1025:             l %= r;
1026:         break;
1027: 
1028:     case AND:
1029:         l &= r;
1030:         break;
1031: 
1032:     case ANDN:
1033:         l &= ~r;
1034:         break;
1035: 
1036:     case OR:
1037:         l |= r;
1038:         break;
1039: 
1040:     case EXOR:
1041:         l ^= r;
1042:         break;
1043: 
1044:     case LSHIFT:
1045:         l <<= r;
1046:         break;
1047: 
1048:     case RSHIFT:
1049:         l >>= r;
1050:         break;
1051: 
1052:     default:
1053:         return(0);
1054:     }
1055:     if (lp->t.op==LCON) {
1056:         lp->l.lvalue = l;
1057:         return(lp);
1058:     }
1059:     lp = getblk(sizeof(struct lconst));
1060:     lp->t.op = LCON;
1061:     lp->t.type = LONG;
1062:     lp->l.lvalue = l;
1063:     return(lp);
1064: }
1065: 
1066: insert(op, tree, list)
1067: register union tree *tree;
1068: register struct acl *list;
1069: {
1070:     register d;
1071:     int d1, i;
1072:     union tree *t;
1073: 
1074: ins:
1075:     if (tree->t.op != op)
1076:         tree = optim(tree);
1077:     if (tree->t.op == op && list->nextn < LSTSIZ-2) {
1078:         list->nlist[list->nextn++] = tree;
1079:         insert(op, tree->t.tr1, list);
1080:         insert(op, tree->t.tr2, list);
1081:         return;
1082:     }
1083:     if (!isfloat(tree)) {
1084:         /* c1*(x+c2) -> c1*x+c1*c2 */
1085:         if ((tree->t.op==TIMES||tree->t.op==LSHIFT)
1086:           && tree->t.tr2->t.op==CON && tree->t.tr2->c.value>0
1087:           && tree->t.tr1->t.op==PLUS && tree->t.tr1->t.tr2->t.op==CON) {
1088:             d = tree->t.tr2->c.value;
1089:             if (tree->t.op==TIMES)
1090:                 tree->t.tr2->c.value *= tree->t.tr1->t.tr2->c.value;
1091:             else
1092:                 tree->t.tr2->c.value = tree->t.tr1->t.tr2->c.value << d;
1093:             tree->t.tr1->t.tr2->c.value = d;
1094:             tree->t.tr1->t.op = tree->t.op;
1095:             tree->t.op = PLUS;
1096:             tree = optim(tree);
1097:             if (op==PLUS)
1098:                 goto ins;
1099:         }
1100:     }
1101:     d = degree(tree);
1102:     for (i=0; i<list->nextl; i++) {
1103:         if ((d1=degree(list->llist[i]))<d) {
1104:             t = list->llist[i];
1105:             list->llist[i] = tree;
1106:             tree = t;
1107:             d = d1;
1108:         }
1109:     }
1110:     list->llist[list->nextl++] = tree;
1111: }
1112: 
1113: union tree *
1114: tnode(op, type, tr1, tr2)
1115: union tree *tr1, *tr2;
1116: {
1117:     register union tree *p;
1118: 
1119:     p = getblk(sizeof(struct tnode));
1120:     p->t.op = op;
1121:     p->t.type = type;
1122:     p->t.degree = 0;
1123:     p->t.tr1 = tr1;
1124:     p->t.tr2 = tr2;
1125:     return(p);
1126: }
1127: 
1128: union tree *
1129: tconst(val, type)
1130: {
1131:     register union tree *p;
1132: 
1133:     p = getblk(sizeof(struct tconst));
1134:     p->t.op = CON;
1135:     p->t.type = type;
1136:     p->c.value = val;
1137:     return(p);
1138: }
1139: 
1140: union tree *
1141: getblk(size)
1142: {
1143:     register union tree *p;
1144: 
1145:     if (size&01)
1146:         size++;
1147:     p = (union tree *)curbase;
1148:     if ((curbase += size) >= coremax) {
1149:         if (sbrk(1024) == (char *)-1) {
1150:             error("Out of space-- c1");
1151:             exit(1);
1152:         }
1153:         coremax += 1024;
1154:     }
1155:     return(p);
1156: }
1157: 
1158: islong(t)
1159: {
1160:     if (t==LONG || t==UNLONG)
1161:         return(2);
1162:     return(1);
1163: }
1164: 
1165: union tree *
1166: isconstant(t)
1167: register union tree *t;
1168: {
1169:     if (t->t.op==CON || t->t.op==SFCON)
1170:         return(t);
1171:     if (t->t.op==ITOL && t->t.tr1->t.op==CON)
1172:         return(t->t.tr1);
1173:     return(NULL);
1174: }
1175: 
1176: union tree *
1177: hardlongs(t)
1178: register union tree *t;
1179: {
1180:     switch(t->t.op) {
1181: 
1182:     case TIMES:
1183:     case DIVIDE:
1184:     case MOD:
1185:         if (t->t.type == UNLONG)
1186:             t->t.op += ULTIMES-TIMES;
1187:         else
1188:             t->t.op += LTIMES-TIMES;
1189:         break;
1190: 
1191:     case ASTIMES:
1192:     case ASDIV:
1193:     case ASMOD:
1194:         if (t->t.type == UNLONG)
1195:             t->t.op += ULASTIMES-ASTIMES;
1196:         else
1197:             t->t.op += LASTIMES-ASTIMES;
1198:         t->t.tr1 = tnode(AMPER, LONG+PTR, t->t.tr1, TNULL);
1199:         break;
1200: 
1201:     default:
1202:         return(t);
1203:     }
1204:     return(optim(t));
1205: }
1206: 
1207: /*
1208:  * Is tree of unsigned type?
1209:  */
1210: uns(tp)
1211: union tree *tp;
1212: {
1213:     register t;
1214: 
1215:     t = tp->t.type;
1216:     if (t==UNSIGN || t==UNCHAR || t==UNLONG || t&XTYPE)
1217:         return(1);
1218:     return(0);
1219: }

Defined functions

acommute defined in line 651; used 2 times
distrib defined in line 792; used 1 times
getblk defined in line 1140; used 19 times
hardlongs defined in line 1176; used 3 times
insert defined in line 1066; used 3 times
isconstant defined in line 1165; used 7 times
islong defined in line 1158; used 6 times
lconst defined in line 973; used 3 times
lvfield defined in line 601; used 2 times
optim defined in line 8; used 41 times
sideeffects defined in line 764; used 3 times
squash defined in line 865; used 3 times
tconst defined in line 1128; used 9 times
tnode defined in line 1113; used 42 times
unoptim defined in line 298; used 3 times
uns defined in line 1210; used 27 times

Defined variables

v defined in line 875; used 30 times
vp defined in line 875; used 21 times

Defined struct's

acl defined in line 644; used 6 times

Defined macros

LSTSIZ defined in line 643; used 3 times
Last modified: 1993-07-04
Generated: 2016-12-26
Generated by src2html V0.67
page hit count: 5836
Valid CSS Valid XHTML 1.0 Strict