UNIX 7th Ed. - /usr/src/cmd/c/c12.c

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

Defined functions

Defined variables

Defined struct's

Defined macros