UNIX 6th Ed. - /usr/source/c/c12.c

   1: #
   2: /*
   3:  *		C compiler part 2 -- expression optimizer
   4:  *
   5:  */
   6: 
   7: #include "c1h.c"
   8: 
   9: optim(atree)
  10: struct tnode *atree;
  11: {
  12:     register op, dope;
  13:     int d1, d2;
  14:     struct tnode *t;
  15:     register struct tnode *tree;
  16: 
  17:     if ((tree=atree)==0)
  18:         return(0);
  19:     if ((op = tree->op)==0)
  20:         return(tree);
  21:     if (op==NAME && tree->class==AUTO) {
  22:         tree->class = OFFS;
  23:         tree->regno = 5;
  24:         tree->offset = tree->nloc;
  25:     }
  26:     dope = opdope[op];
  27:     if ((dope&LEAF) != 0)
  28:         return(tree);
  29:     if ((dope&BINARY) == 0)
  30:         return(unoptim(tree));
  31:     /* is known to be binary */
  32:     if (tree->type==CHAR)
  33:         tree->type = INT;
  34:     if ((dope&COMMUTE)!=0) {
  35:     acomm:  d1 = tree->type;
  36:         tree = acommute(tree);
  37:         tree->type = d1;
  38:         /*
  39: 		 * PDP-11 special:
  40: 		 * replace a&b by a NAND ~ b.
  41: 		 * This will be undone when in
  42: 		 * truth-value context.
  43: 		 */
  44:         if (tree->op!=AND)
  45:             return(tree);
  46:         tree->op = NAND;
  47:         tree->tr2 = block(1, COMPL, tree->tr2->type, 0, tree->tr2);
  48:     }
  49:     again:
  50:     tree->tr1 = optim(tree->tr1);
  51:     tree->tr2 = optim(tree->tr2);
  52:     if ((dope&RELAT) != 0) {
  53:         if ((d1=degree(tree->tr1)) < (d2=degree(tree->tr2))
  54:          || d1==d2 && tree->tr1->op==NAME && tree->tr2->op!=NAME) {
  55:             t = tree->tr1;
  56:             tree->tr1 = tree->tr2;
  57:             tree->tr2 = t;
  58:             tree->op = maprel[op-EQUAL];
  59:         }
  60:         if (tree->tr1->type==CHAR && tree->tr2->op==CON
  61:          && (dcalc(tree->tr1) <= 12 || tree->tr1->op==STAR)
  62:          && tree->tr2->value <= 127 && tree->tr2->value >= 0)
  63:             tree->tr2->type = CHAR;
  64:     }
  65:     d1 = max(degree(tree->tr1), islong(tree->type));
  66:     d2 = max(degree(tree->tr2), 0);
  67:     if (tree->tr1->type==LONG && dope&RELAT)
  68:         d1 = 10;
  69:     switch (op) {
  70: 
  71:     case LTIMES:
  72:     case LDIV:
  73:     case LMOD:
  74:     case LASTIMES:
  75:     case LASDIV:
  76:     case LASMOD:
  77:         tree->degree = 10;
  78:         break;
  79: 
  80:     /*
  81: 	 * PDP-11 special:
  82: 	 * generate new =&~ operator out of =&
  83: 	 * by complementing the RHS.
  84: 	 */
  85:     case ASSAND:
  86:         op = ASSNAND;
  87:         tree->op = op;
  88:         tree->tr2 = block(2, COMPL, tree->tr2->type, 0, tree->tr2);
  89:         goto again;
  90: 
  91:     case NAND:
  92:         if (isconstant(tree->tr2) && tree->tr2->value==0)
  93:             return(tree->tr1);
  94:         goto def;
  95: 
  96:     case CALL:
  97:         tree->degree = 10;
  98:         break;
  99: 
 100:     case QUEST:
 101:     case COLON:
 102:         tree->degree = max(d1, d2);
 103:         break;
 104: 
 105:     case MINUS:
 106:         if (t = isconstant(tree->tr2)) {
 107:             tree->op = PLUS;
 108:             if (t->type==DOUBLE)
 109:                 /* PDP-11 FP representation */
 110:                 t->value =^ 0100000;
 111:             else
 112:                 t->value = -t->value;
 113:             goto acomm;
 114:         }
 115:         goto def;
 116: 
 117:     case DIVIDE:
 118:     case ASDIV:
 119:     case ASTIMES:
 120:         if (tree->tr2->op==CON && tree->tr2->value==1)
 121:             return(tree->tr1);
 122:         if (ispow2(tree) == 0) {
 123: 
 124:         case MOD:
 125:         case ASMOD:
 126:             d1 =+ 2;
 127:             d2 =+ 2;
 128:         }
 129:         if (tree->type==LONG)
 130:             return(hardlongs(tree));
 131:         goto constant;
 132: 
 133:     case LSHIFT:
 134:     case RSHIFT:
 135:     case ASRSH:
 136:     case ASLSH:
 137:         if (tree->tr2->op==CON && tree->tr2->value==0)
 138:             return(tree->tr1);
 139:         /*
 140: 		 * PDP-11 special: turn right shifts into negative
 141: 		 * left shifts
 142: 		 */
 143:         if (op==LSHIFT||op==ASLSH)
 144:             goto constant;
 145:         if (tree->tr2->op==CON && tree->tr2->value==1)
 146:             goto constant;
 147:         op =+ (LSHIFT-RSHIFT);
 148:         tree->op = op;
 149:         tree->tr2 = block(1, NEG, tree->type, 0, tree->tr2);
 150:         goto again;
 151: 
 152:     constant:
 153:         if (tree->tr1->op==CON && tree->tr2->op==CON) {
 154:             const(op, &tree->tr1->value, tree->tr2->value);
 155:             return(tree->tr1);
 156:         }
 157: 
 158: 
 159:     def:
 160:     default:
 161:         tree->degree = d1==d2? d1+islong(tree->type): max(d1, d2);
 162:         break;
 163:     }
 164:     return(tree);
 165: }
 166: 
 167: unoptim(atree)
 168: struct tnode *atree;
 169: {
 170:     register struct tnode *subtre, *tree;
 171:     register int *p;
 172:     double static fv;
 173:     struct { int integer; };
 174: 
 175:     if ((tree=atree)==0)
 176:         return(0);
 177:     if (tree->op==CBRANCH) {
 178:         tree->btree = optim(tree->btree);
 179:         return(tree);
 180:     }
 181:     subtre = tree->tr1 = optim(tree->tr1);
 182:     switch (tree->op) {
 183: 
 184:     case FSEL:
 185:         tree->tr1 = block(2, RSHIFT, INT, 0, subtre,
 186:             block(1, CON, INT, 0, tree->bitoffs));
 187:         tree->op = AND;
 188:         tree->type = INT;
 189:         tree->tr2 = block(1, CON, INT, 0, (1<<tree->flen)-1);
 190:         return(optim(tree));
 191: 
 192:     case AMPER:
 193:         if (subtre->op==STAR)
 194:             return(subtre->tr1);
 195:         if (subtre->op==NAME && subtre->class == OFFS) {
 196:             p = block(2, PLUS, tree->type, 1, subtre, tree);
 197:             subtre->type = tree->type;
 198:             tree->op = CON;
 199:             tree->type = INT;
 200:             tree->degree = 0;
 201:             tree->value = subtre->offset;
 202:             subtre->class = REG;
 203:             subtre->nloc = subtre->regno;
 204:             subtre->offset = 0;
 205:             return(p);
 206:         }
 207:         break;
 208: 
 209:     case STAR:
 210:         if (subtre->op==AMPER)
 211:             return(subtre->tr1);
 212:         if (subtre->op==NAME && subtre->class==REG) {
 213:             subtre->type = tree->type;
 214:             subtre->class = OFFS;
 215:             subtre->regno = subtre->nloc;
 216:             return(subtre);
 217:         }
 218:         p = subtre->tr1;
 219:         if ((subtre->op==INCAFT||subtre->op==DECBEF)&&tree->type!=LONG
 220:          && p->op==NAME && p->class==REG && p->type==subtre->type) {
 221:             p->type = tree->type;
 222:             p->op = subtre->op==INCAFT? AUTOI: AUTOD;
 223:             return(p);
 224:         }
 225:         if (subtre->op==PLUS && p->op==NAME && p->class==REG) {
 226:             if (subtre->tr2->op==CON) {
 227:                 p->offset =+ subtre->tr2->value;
 228:                 p->class = OFFS;
 229:                 p->type = tree->type;
 230:                 p->regno = p->nloc;
 231:                 return(p);
 232:             }
 233:             if (subtre->tr2->op==AMPER) {
 234:                 subtre = subtre->tr2->tr1;
 235:                 subtre->class =+ XOFFS-EXTERN;
 236:                 subtre->regno = p->nloc;
 237:                 subtre->type = tree->type;
 238:                 return(subtre);
 239:             }
 240:         }
 241:         break;
 242:     case EXCLA:
 243:         if ((opdope[subtre->op]&RELAT)==0)
 244:             break;
 245:         tree = subtre;
 246:         tree->op = notrel[tree->op-EQUAL];
 247:         break;
 248: 
 249:     case NEG:
 250:     case COMPL:
 251:         if (tree->type==CHAR)
 252:             tree->type = INT;
 253:         if (tree->op == subtre->op)
 254:             return(subtre->tr1);
 255:         if (subtre->op==ITOL) {
 256:             subtre->op = tree->op;
 257:             subtre->type = INT;
 258:             tree->op = ITOL;
 259:         }
 260:     }
 261:     if (subtre->op == CON) switch(tree->op) {
 262: 
 263:     case NEG:
 264:         subtre->value = -subtre->value;
 265:         return(subtre);
 266: 
 267:     case COMPL:
 268:         subtre->value = ~subtre->value;
 269:         return(subtre);
 270: 
 271:     case ITOF:
 272:         fv = subtre->value;
 273:         p = &fv;
 274:         p++;
 275:         if (*p++==0 && *p++==0 && *p++==0) {
 276:             subtre->type = DOUBLE;
 277:             subtre->value = fv.integer;
 278:             subtre->op = SFCON;
 279:             return(subtre);
 280:         }
 281:         break;
 282:     }
 283:     tree->degree = max(islong(tree->type), degree(subtre));
 284:     return(tree);
 285: }
 286: 
 287: struct acl {
 288:     int nextl;
 289:     int nextn;
 290:     struct tnode *nlist[20];
 291:     struct tnode *llist[21];
 292: };
 293: 
 294: acommute(atree)
 295: {
 296:     struct acl acl;
 297:     int d, i, op, flt;
 298:     register struct tnode *t1, **t2, *tree;
 299:     struct tnode *t;
 300: 
 301:     acl.nextl = 0;
 302:     acl.nextn = 0;
 303:     tree = atree;
 304:     op = tree->op;
 305:     flt = isfloat(tree);
 306:     insert(op, tree, &acl);
 307:     acl.nextl--;
 308:     t2 = &acl.llist[acl.nextl];
 309:     if (!flt) {
 310:         /* put constants together */
 311:         for (i=acl.nextl;i>0&&t2[0]->op==CON&&t2[-1]->op==CON;i--) {
 312:             acl.nextl--;
 313:             t2--;
 314:             const(op, &t2[0]->value, t2[1]->value);
 315:         }
 316:     }
 317:     if (op==PLUS || op==OR) {
 318:         /* toss out "+0" */
 319:         if (acl.nextl>0 && (t1 = isconstant(*t2)) && t1->value==0) {
 320:             acl.nextl--;
 321:             t2--;
 322:         }
 323:         if (acl.nextl <= 0)
 324:             return(*t2);
 325:         /* subsume constant in "&x+c" */
 326:         if (op==PLUS && t2[0]->op==CON && t2[-1]->op==AMPER) {
 327:             t2--;
 328:             t2[0]->tr1->offset =+ t2[1]->value;
 329:             acl.nextl--;
 330:         }
 331:     } else if (op==TIMES || op==AND) {
 332:         t1 = acl.llist[acl.nextl];
 333:         if (t1->op==CON) {
 334:             if (t1->value==0)
 335:                 return(t1);
 336:             if (op==TIMES && t1->value==1 && acl.nextl>0)
 337:                 if (--acl.nextl <= 0)
 338:                     return(acl.llist[0]);
 339:         }
 340:     }
 341:     if (op==PLUS && !flt)
 342:         distrib(&acl);
 343:     tree = *(t2 = &acl.llist[0]);
 344:     d = max(degree(tree), islong(tree->type));
 345:     if (op==TIMES && !flt)
 346:         d++;
 347:     for (i=0; i<acl.nextl; i++) {
 348:         t1 = acl.nlist[i];
 349:         t1->tr2 = t = *++t2;
 350:         t1->degree = d = d==degree(t)? d+islong(t1->type): max(d, degree(t));
 351:         t1->tr1 = tree;
 352:         tree = t1;
 353:         if (tree->type==LONG) {
 354:             if (tree->op==TIMES)
 355:                 tree = hardlongs(tree);
 356:             else if (tree->op==PLUS && (t = isconstant(tree->tr1))
 357:                    && t->value < 0) {
 358:                 tree->op = MINUS;
 359:                 t->value = - t->value;
 360:                 t = tree->tr1;
 361:                 tree->tr1 = tree->tr2;
 362:                 tree->tr2 = t;
 363:             }
 364:         }
 365:     }
 366:     if (tree->op==TIMES && ispow2(tree))
 367:         tree->degree = max(degree(tree->tr1), islong(tree->type));
 368:     return(tree);
 369: }
 370: 
 371: distrib(list)
 372: struct acl *list;
 373: {
 374: /*
 375:  * Find a list member of the form c1c2*x such
 376:  * that c1c2 divides no other such constant, is divided by
 377:  * at least one other (say in the form c1*y), and which has
 378:  * fewest divisors. Reduce this pair to c1*(y+c2*x)
 379:  * and iterate until no reductions occur.
 380:  */
 381:     register struct tnode **p1, **p2;
 382:     struct tnode *t;
 383:     int ndmaj, ndmin;
 384:     struct tnode **dividend, **divisor;
 385:     struct tnode **maxnod, **mindiv;
 386: 
 387:     loop:
 388:     maxnod = &list->llist[list->nextl];
 389:     ndmaj = 1000;
 390:     dividend = 0;
 391:     for (p1 = list->llist; p1 <= maxnod; p1++) {
 392:         if ((*p1)->op!=TIMES || (*p1)->tr2->op!=CON)
 393:             continue;
 394:         ndmin = 0;
 395:         for (p2 = list->llist; p2 <= maxnod; p2++) {
 396:             if (p1==p2 || (*p2)->op!=TIMES || (*p2)->tr2->op!=CON)
 397:                 continue;
 398:             if ((*p1)->tr2->value == (*p2)->tr2->value) {
 399:                 (*p2)->tr2 = (*p1)->tr1;
 400:                 (*p2)->op = PLUS;
 401:                 (*p1)->tr1 = (*p2);
 402:                 *p1 = optim(*p1);
 403:                 squash(p2, maxnod);
 404:                 list->nextl--;
 405:                 goto loop;
 406:             }
 407:             if (((*p2)->tr2->value % (*p1)->tr2->value) == 0)
 408:                 goto contmaj;
 409:             if (((*p1)->tr2->value % (*p2)->tr2->value) == 0) {
 410:                 ndmin++;
 411:                 mindiv = p2;
 412:             }
 413:         }
 414:         if (ndmin > 0 && ndmin < ndmaj) {
 415:             ndmaj = ndmin;
 416:             dividend = p1;
 417:             divisor = mindiv;
 418:         }
 419:     contmaj:;
 420:     }
 421:     if (dividend==0)
 422:         return;
 423:     t = list->nlist[--list->nextn];
 424:     p1 = dividend;
 425:     p2 = divisor;
 426:     t->op = PLUS;
 427:     t->type = (*p1)->type;
 428:     t->tr1 = (*p1);
 429:     t->tr2 = (*p2)->tr1;
 430:     (*p1)->tr2->value =/ (*p2)->tr2->value;
 431:     (*p2)->tr1 = t;
 432:     t = optim(*p2);
 433:     if (p1 < p2) {
 434:         *p1 = t;
 435:         squash(p2, maxnod);
 436:     } else {
 437:         *p2 = t;
 438:         squash(p1, maxnod);
 439:     }
 440:     list->nextl--;
 441:     goto loop;
 442: }
 443: 
 444: squash(p, maxp)
 445: struct tnode **p, **maxp;
 446: {
 447:     register struct tnode **np;
 448: 
 449:     for (np = p; np < maxp; np++)
 450:         *np = *(np+1);
 451: }
 452: 
 453: const(op, vp, av)
 454: int *vp;
 455: {
 456:     register int v;
 457: 
 458:     v = av;
 459:     switch (op) {
 460: 
 461:     case PLUS:
 462:         *vp =+ v;
 463:         return;
 464: 
 465:     case TIMES:
 466:         *vp =* v;
 467:         return;
 468: 
 469:     case AND:
 470:         *vp =& v;
 471:         return;
 472: 
 473:     case OR:
 474:         *vp =| v;
 475:         return;
 476: 
 477:     case EXOR:
 478:         *vp =^ v;
 479:         return;
 480: 
 481:     case DIVIDE:
 482:     case MOD:
 483:         if (v==0)
 484:             error("Divide check");
 485:         else
 486:             if (op==DIVIDE)
 487:                 *vp =/ v;
 488:             else
 489:                 *vp =% v;
 490:         return;
 491: 
 492:     case RSHIFT:
 493:         *vp =>> v;
 494:         return;
 495: 
 496:     case LSHIFT:
 497:         *vp =<< v;
 498:         return;
 499: 
 500:     case NAND:
 501:         *vp =& ~ v;
 502:         return;
 503:     }
 504:     error("C error: const");
 505: }
 506: 
 507: insert(op, atree, alist)
 508: struct acl *alist;
 509: {
 510:     register d;
 511:     register struct acl *list;
 512:     register struct tnode *tree;
 513:     int d1, i;
 514:     struct tnode *t;
 515: 
 516:     tree = atree;
 517:     list = alist;
 518:     if (tree->op == op) {
 519:     ins:    list->nlist[list->nextn++] = tree;
 520:         insert(op, tree->tr1, list);
 521:         insert(op, tree->tr2, list);
 522:         return;
 523:     }
 524:     tree = optim(tree);
 525:     if (tree->op == op)
 526:         goto ins;
 527:     if (!isfloat(tree)) {
 528:         /* c1*(x+c2) -> c1*x+c1*c2 */
 529:         if ((tree->op==TIMES||tree->op==LSHIFT)
 530:           && tree->tr2->op==CON && tree->tr2->value>0
 531:           && tree->tr1->op==PLUS && tree->tr1->tr2->op==CON) {
 532:             d = tree->tr2->value;
 533:             if (tree->op==TIMES)
 534:                 tree->tr2->value =* tree->tr1->tr2->value;
 535:             else
 536:                 tree->tr2->value = tree->tr1->tr2->value << d;
 537:             tree->tr1->tr2->value = d;
 538:             tree->tr1->op = tree->op;
 539:             tree->op = PLUS;
 540:             if (op==PLUS)
 541:                 goto ins;
 542:         }
 543:     }
 544:     d = degree(tree);
 545:     for (i=0; i<list->nextl; i++) {
 546:         if ((d1=degree(list->llist[i]))<d) {
 547:             t = list->llist[i];
 548:             list->llist[i] = tree;
 549:             tree = t;
 550:             d = d1;
 551:         }
 552:     }
 553:     list->llist[list->nextl++] = tree;
 554: }
 555: 
 556: block(an, args)
 557: {
 558:     register int *p;
 559:     int *oldp;
 560:     register *argp, n;
 561: 
 562:     oldp = p = spacep;
 563:     n = an+3;
 564:     argp = &args;
 565:     do
 566:         *p++ = *argp++;
 567:     while (--n);
 568:     if (p >= &treespace[ossiz]) {
 569:         error("Exp. ov. pass 2");
 570:         exit(1);
 571:     }
 572:     spacep = p;
 573:     return(oldp);
 574: }
 575: 
 576: islong(t)
 577: {
 578:     if (t==LONG)
 579:         return(2);
 580:     return(1);
 581: }
 582: 
 583: isconstant(at)
 584: struct tnode *at;
 585: {
 586:     register struct tnode *t;
 587: 
 588:     t = at;
 589:     if (t->op==CON || t->op==SFCON)
 590:         return(t);
 591:     if (t->op==ITOL && t->tr1->op==CON)
 592:         return(t->tr1);
 593:     return(0);
 594: }
 595: 
 596: hardlongs(at)
 597: struct tnode *at;
 598: {
 599:     register struct tnode *t;
 600: 
 601:     t = at;
 602:     switch(t->op) {
 603: 
 604:     case TIMES:
 605:     case DIVIDE:
 606:     case MOD:
 607:         t->op =+ LTIMES-TIMES;
 608:         break;
 609: 
 610:     case ASTIMES:
 611:     case ASDIV:
 612:     case ASMOD:
 613:         t->op =+ LASTIMES-ASTIMES;
 614:         t->tr1 = block(1, AMPER, LONG+PTR, 0, t->tr1);
 615:         break;
 616: 
 617:     default:
 618:         return(t);
 619:     }
 620:     return(optim(t));
 621: }

Defined functions

Defined variables

Defined struct's