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

   1: #
   2: /*
   3:  *	 C object code improver
   4:  */
   5: 
   6: #include "c2h.c"
   7: 
   8: struct optab optab[] {
   9:     "jbr",  JBR,
  10:     "jeq",  CBR | JEQ<<8,
  11:     "jne",  CBR | JNE<<8,
  12:     "jle",  CBR | JLE<<8,
  13:     "jge",  CBR | JGE<<8,
  14:     "jlt",  CBR | JLT<<8,
  15:     "jgt",  CBR | JGT<<8,
  16:     "jlo",  CBR | JLO<<8,
  17:     "jhi",  CBR | JHI<<8,
  18:     "jlos", CBR | JLOS<<8,
  19:     "jhis", CBR | JHIS<<8,
  20:     "jmp",  JMP,
  21:     ".globl",EROU,
  22:     "mov",  MOV,
  23:     "clr",  CLR,
  24:     "com",  COM,
  25:     "inc",  INC,
  26:     "dec",  DEC,
  27:     "neg",  NEG,
  28:     "tst",  TST,
  29:     "asr",  ASR,
  30:     "asl",  ASL,
  31:     "sxt",  SXT,
  32:     "cmp",  CMP,
  33:     "add",  ADD,
  34:     "sub",  SUB,
  35:     "bit",  BIT,
  36:     "bic",  BIC,
  37:     "bis",  BIS,
  38:     "mul",  MUL,
  39:     "ash",  ASH,
  40:     "xor",  XOR,
  41:     ".text",TEXT,
  42:     ".data",DATA,
  43:     ".bss", BSS,
  44:     ".even",EVEN,
  45:     "movf", MOVF,
  46:     "movof",MOVOF,
  47:     "movfo",MOVFO,
  48:     "addf", ADDF,
  49:     "subf", SUBF,
  50:     "divf", DIVF,
  51:     "mulf", MULF,
  52:     "clrf", CLRF,
  53:     "cmpf", CMPF,
  54:     "negf", NEGF,
  55:     "tstf", TSTF,
  56:     "cfcc", CFCC,
  57:     "sob",  SOB,
  58:     "jsr",  JSR,
  59:     ".end", END,
  60:     0,  0};
  61: 
  62: char    revbr[] { JNE, JEQ, JGT, JLT, JGE, JLE, JHIS, JLOS, JHI, JLO };
  63: int isn 20000;
  64: 
  65: main(argc, argv)
  66: char **argv;
  67: {
  68:     register int niter, maxiter, isend;
  69:     extern end;
  70:     extern fin, fout;
  71:     int nflag;
  72: 
  73:     if (argc>1 && argv[1][0]=='+') {
  74:         argc--;
  75:         argv++;
  76:         debug++;
  77:     }
  78:     if (argc>1 && argv[1][0]=='-') {
  79:         argc--;
  80:         argv++;
  81:         nflag++;
  82:     }
  83:     if (argc>1) {
  84:         if ((fin = open(argv[1], 0)) < 0) {
  85:             printf("C2: can't find %s\n", argv[1]);
  86:             exit(1);
  87:         }
  88:     } else
  89:         fin = dup(0);
  90:     if (argc>2) {
  91:         if ((fout = creat(argv[2], 0666)) < 0) {
  92:             fout = 1;
  93:             printf("C2: can't create %s\n", argv[2]);
  94:             exit(1);
  95:         }
  96:     } else
  97:         fout = dup(1);
  98:     lasta = firstr = lastr = sbrk(2);
  99:     maxiter = 0;
 100:     opsetup();
 101:     do {
 102:         isend = input();
 103:         movedat();
 104:         niter = 0;
 105:         do {
 106:             refcount();
 107:             do {
 108:                 iterate();
 109:                 clearreg();
 110:                 niter++;
 111:             } while (nchange);
 112:             comjump();
 113:             rmove();
 114:         } while (nchange || jumpsw());
 115:         addsob();
 116:         output();
 117:         if (niter > maxiter)
 118:             maxiter = niter;
 119:         lasta = firstr;
 120:     } while (isend);
 121:     flush();
 122:     fout = 2;
 123:     if (nflag) {
 124:         printf("%d iterations\n", maxiter);
 125:         printf("%d jumps to jumps\n", nbrbr);
 126:         printf("%d inst. after jumps\n", iaftbr);
 127:         printf("%d jumps to .+2\n", njp1);
 128:         printf("%d redundant labels\n", nrlab);
 129:         printf("%d cross-jumps\n", nxjump);
 130:         printf("%d code motions\n", ncmot);
 131:         printf("%d branches reversed\n", nrevbr);
 132:         printf("%d redundant moves\n", redunm);
 133:         printf("%d simplified addresses\n", nsaddr);
 134:         printf("%d loops inverted\n", loopiv);
 135:         printf("%d redundant jumps\n", nredunj);
 136:         printf("%d common seqs before jmp's\n", ncomj);
 137:         printf("%d skips over jumps\n", nskip);
 138:         printf("%d sob's added\n", nsob);
 139:         printf("%d redundant tst's\n", nrtst);
 140:         printf("%d literals eliminated\n", nlit);
 141:         printf("%dK core\n", ((lastr+01777)>>10)&077);
 142:         flush();
 143:     }
 144:     exit(0);
 145: }
 146: 
 147: input()
 148: {
 149:     register struct node *p, *lastp;
 150:     register int op;
 151: 
 152:     lastp = &first;
 153:     for (;;) {
 154:         op = getline();
 155:         switch (op.op) {
 156: 
 157:         case LABEL:
 158:             p = alloc(sizeof first);
 159:             if (line[0] == 'L') {
 160:                 p->combop = LABEL;
 161:                 p->labno = getnum(line+1);
 162:                 p->code = 0;
 163:             } else {
 164:                 p->combop = DLABEL;
 165:                 p->labno = 0;
 166:                 p->code = copy(line);
 167:             }
 168:             break;
 169: 
 170:         case JBR:
 171:         case CBR:
 172:         case JMP:
 173:         case JSW:
 174:             p = alloc(sizeof first);
 175:             p->combop = op;
 176:             if (*curlp=='L' && (p->labno = getnum(curlp+1)))
 177:                 p->code = 0;
 178:             else {
 179:                 p->labno = 0;
 180:                 p->code = copy(curlp);
 181:             }
 182:             break;
 183: 
 184:         default:
 185:             p = alloc(sizeof first);
 186:             p->combop = op;
 187:             p->labno = 0;
 188:             p->code = copy(curlp);
 189:             break;
 190: 
 191:         }
 192:         p->forw = 0;
 193:         p->back = lastp;
 194:         lastp->forw = p;
 195:         lastp = p;
 196:         p->ref = 0;
 197:         if (op==EROU)
 198:             return(1);
 199:         if (op==END)
 200:             return(0);
 201:     }
 202: }
 203: 
 204: getline()
 205: {
 206:     register char *lp;
 207:     register c;
 208: 
 209:     lp = line;
 210:     while (c = getchar()) {
 211:         if (c==':') {
 212:             *lp++ = 0;
 213:             return(LABEL);
 214:         }
 215:         if (c=='\n') {
 216:             *lp++ = 0;
 217:             return(oplook());
 218:         }
 219:         *lp++ = c;
 220:     }
 221:     *lp++ = 0;
 222:     return(END);
 223: }
 224: 
 225: getnum(ap)
 226: char *ap;
 227: {
 228:     register char *p;
 229:     register n, c;
 230: 
 231:     p = ap;
 232:     n = 0;
 233:     while ((c = *p++) >= '0' && c <= '9')
 234:         n = n*10 + c - '0';
 235:     if (*--p != 0)
 236:         return(0);
 237:     return(n);
 238: }
 239: 
 240: output()
 241: {
 242:     register struct node *t;
 243:     register struct optab *op;
 244:     register int byte;
 245: 
 246:     t = &first;
 247:     while (t = t->forw) switch (t->op) {
 248: 
 249:     case END:
 250:         return;
 251: 
 252:     case LABEL:
 253:         printf("L%d:", t->labno);
 254:         continue;
 255: 
 256:     case DLABEL:
 257:         printf("%s:", t->code);
 258:         continue;
 259: 
 260:     default:
 261:         if ((byte = t->subop) == BYTE)
 262:             t->subop = 0;
 263:         for (op = optab; op->opstring!=0; op++)
 264:             if (op->opcode == t->combop) {
 265:                 printf("%s", op->opstring);
 266:                 if (byte==BYTE)
 267:                     printf("b");
 268:                 break;
 269:             }
 270:         if (t->code) {
 271:             reducelit(t);
 272:             printf("\t%s\n", t->code);
 273:         } else if (t->op==JBR || t->op==CBR)
 274:             printf("\tL%d\n", t->labno);
 275:         else
 276:             printf("\n");
 277:         continue;
 278: 
 279:     case JSW:
 280:         printf("L%d\n", t->labno);
 281:         continue;
 282: 
 283:     case SOB:
 284:         printf("sob	%s,L%d\n", t->code, t->labno);
 285:         continue;
 286: 
 287:     case 0:
 288:         if (t->code)
 289:             printf("%s", t->code);
 290:         printf("\n");
 291:         continue;
 292:     }
 293: }
 294: 
 295: /*
 296:  * Notice addresses of the form
 297:  * $xx,xx(r)
 298:  * and replace them with (pc),xx(r)
 299:  *     -- Thanx and a tip of the Hatlo hat to Bliss-11.
 300:  */
 301: reducelit(at)
 302: struct node *at;
 303: {
 304:     register char *c1, *c2;
 305:     char *c2s;
 306:     register struct node *t;
 307: 
 308:     t = at;
 309:     if (*t->code != '$')
 310:         return;
 311:     c1 = t->code;
 312:     while (*c1 != ',')
 313:         if (*c1++ == '\0')
 314:             return;
 315:     c2s = c1;
 316:     c1++;
 317:     if (*c1=='*')
 318:         c1++;
 319:     c2 = t->code+1;
 320:     while (*c1++ == *c2++);
 321:     if (*--c1!='(' || *--c2!=',')
 322:         return;
 323:     t->code = copy("(pc)", c2s);
 324:     nlit++;
 325: }
 326: 
 327: copy(ap)
 328: char *ap;
 329: {
 330:     register char *p, *np;
 331:     char *onp;
 332:     register n;
 333:     int na;
 334: 
 335:     na = nargs();
 336:     p = ap;
 337:     n = 0;
 338:     if (*p==0)
 339:         return(0);
 340:     do
 341:         n++;
 342:     while (*p++);
 343:     if (na>1) {
 344:         p = (&ap)[1];
 345:         while (*p++)
 346:             n++;
 347:     }
 348:     onp = np = alloc(n);
 349:     p = ap;
 350:     while (*np++ = *p++);
 351:     if (na>1) {
 352:         p = (&ap)[1];
 353:         np--;
 354:         while (*np++ = *p++);
 355:     }
 356:     return(onp);
 357: }
 358: 
 359: opsetup()
 360: {
 361:     register struct optab *optp, **ophp;
 362:     register char *p;
 363: 
 364:     for (optp = optab; p = optp->opstring; optp++) {
 365:         ophp = &ophash[(((p[0]<<3)+(p[1]<<1)+p[2])&077777) % OPHS];
 366:         while (*ophp++)
 367:             if (ophp > &ophash[OPHS])
 368:                 ophp = ophash;
 369:         *--ophp = optp;
 370:     }
 371: }
 372: 
 373: oplook()
 374: {
 375:     register struct optab *optp;
 376:     register char *lp, *op;
 377:     static char tmpop[32];
 378:     struct optab **ophp;
 379: 
 380:     op = tmpop;
 381:     for (lp = line; *lp && *lp!=' ' && *lp!='\t';)
 382:         *op++ = *lp++;
 383:     *op++ = 0;
 384:     while (*lp=='\t' || *lp==' ')
 385:         lp++;
 386:     curlp = lp;
 387:     ophp = &ophash[(((tmpop[0]<<3)+(tmpop[1]<<1)+tmpop[2])&077777) % OPHS];
 388:     while (optp = *ophp) {
 389:         op = optp->opstring;
 390:         lp = tmpop;
 391:         while (*lp == *op++)
 392:             if (*lp++ == 0)
 393:                 return(optp->opcode);
 394:         if (*lp++=='b' && *lp++==0 && *--op==0)
 395:             return(optp->opcode + (BYTE<<8));
 396:         ophp++;
 397:         if (ophp >= &ophash[OPHS])
 398:             ophp = ophash;
 399:     }
 400:     if (line[0]=='L') {
 401:         lp = &line[1];
 402:         while (*lp)
 403:             if (*lp<'0' || *lp++>'9')
 404:                 return(0);
 405:         curlp = line;
 406:         return(JSW);
 407:     }
 408:     curlp = line;
 409:     return(0);
 410: }
 411: 
 412: refcount()
 413: {
 414:     register struct node *p, *lp;
 415:     static struct node *labhash[LABHS];
 416:     register struct node **hp;
 417: 
 418:     for (hp = labhash; hp < &labhash[LABHS];)
 419:         *hp++ = 0;
 420:     for (p = first.forw; p!=0; p = p->forw)
 421:         if (p->op==LABEL) {
 422:             labhash[p->labno % LABHS] = p;
 423:             p->refc = 0;
 424:         }
 425:     for (p = first.forw; p!=0; p = p->forw) {
 426:         if (p->op==JBR || p->op==CBR || p->op==JSW) {
 427:             p->ref = 0;
 428:             lp = labhash[p->labno % LABHS];
 429:             if (lp==0 || p->labno!=lp->labno)
 430:             for (lp = first.forw; lp!=0; lp = lp->forw) {
 431:                 if (lp->op==LABEL && p->labno==lp->labno)
 432:                     break;
 433:             }
 434:             if (lp) {
 435:                 hp = nonlab(lp)->back;
 436:                 if (hp!=lp) {
 437:                     p->labno = hp->labno;
 438:                     lp = hp;
 439:                 }
 440:                 p->ref = lp;
 441:                 lp->refc++;
 442:             }
 443:         }
 444:     }
 445:     for (p = first.forw; p!=0; p = p->forw)
 446:         if (p->op==LABEL && p->refc==0
 447:          && (lp = nonlab(p))->op && lp->op!=JSW)
 448:             decref(p);
 449: }
 450: 
 451: iterate()
 452: {
 453:     register struct node *p, *rp, *p1;
 454: 
 455:     nchange = 0;
 456:     for (p = first.forw; p!=0; p = p->forw) {
 457:         if ((p->op==JBR||p->op==CBR||p->op==JSW) && p->ref) {
 458:             rp = nonlab(p->ref);
 459:             if (rp->op==JBR && rp->labno && p!=rp) {
 460:                 nbrbr++;
 461:                 p->labno = rp->labno;
 462:                 decref(p->ref);
 463:                 rp->ref->refc++;
 464:                 p->ref = rp->ref;
 465:                 nchange++;
 466:             }
 467:         }
 468:         if (p->op==CBR && (p1 = p->forw)->op==JBR) {
 469:             rp = p->ref;
 470:             do
 471:                 rp = rp->back;
 472:             while (rp->op==LABEL);
 473:             if (rp==p1) {
 474:                 decref(p->ref);
 475:                 p->ref = p1->ref;
 476:                 p->labno = p1->labno;
 477:                 p1->forw->back = p;
 478:                 p->forw = p1->forw;
 479:                 p->subop = revbr[p->subop];
 480:                 nchange++;
 481:                 nskip++;
 482:             }
 483:         }
 484:         if (p->op==JBR || p->op==JMP) {
 485:             while (p->forw && p->forw->op!=LABEL
 486:                 && p->forw->op!=EROU && p->forw->op!=END) {
 487:                 nchange++;
 488:                 iaftbr++;
 489:                 if (p->forw->ref)
 490:                     decref(p->forw->ref);
 491:                 p->forw = p->forw->forw;
 492:                 p->forw->back = p;
 493:             }
 494:             rp = p->forw;
 495:             while (rp && rp->op==LABEL) {
 496:                 if (p->ref == rp) {
 497:                     p->back->forw = p->forw;
 498:                     p->forw->back = p->back;
 499:                     p = p->back;
 500:                     decref(rp);
 501:                     nchange++;
 502:                     njp1++;
 503:                     break;
 504:                 }
 505:                 rp = rp->forw;
 506:             }
 507:             xjump(p);
 508:             p = codemove(p);
 509:         }
 510:     }
 511: }
 512: 
 513: xjump(ap)
 514: {
 515:     register int *p1, *p2, *p3;
 516:     int nxj;
 517: 
 518:     nxj = 0;
 519:     p1 = ap;
 520:     if ((p2 = p1->ref)==0)
 521:         return(0);
 522:     for (;;) {
 523:         while ((p1 = p1->back) && p1->op==LABEL);
 524:         while ((p2 = p2->back) && p2->op==LABEL);
 525:         if (!equop(p1, p2) || p1==p2)
 526:             return(nxj);
 527:         p3 = insertl(p2);
 528:         p1->combop = JBR;
 529:         p1->ref = p3;
 530:         p1->labno = p3->labno;
 531:         p1->code = 0;
 532:         nxj++;
 533:         nxjump++;
 534:         nchange++;
 535:     }
 536: }
 537: 
 538: insertl(ap)
 539: struct node *ap;
 540: {
 541:     register struct node *lp, *op;
 542: 
 543:     op = ap;
 544:     if (op->op == LABEL) {
 545:         op->refc++;
 546:         return(op);
 547:     }
 548:     if (op->back->op == LABEL) {
 549:         op = op->back;
 550:         op->refc++;
 551:         return(op);
 552:     }
 553:     lp = alloc(sizeof first);
 554:     lp->combop = LABEL;
 555:     lp->labno = isn++;
 556:     lp->ref = 0;
 557:     lp->code = 0;
 558:     lp->refc = 1;
 559:     lp->back = op->back;
 560:     lp->forw = op;
 561:     op->back->forw = lp;
 562:     op->back = lp;
 563:     return(lp);
 564: }
 565: 
 566: codemove(ap)
 567: struct node *ap;
 568: {
 569:     register struct node *p1, *p2, *p3;
 570:     struct node *t, *tl;
 571:     int n;
 572: 
 573:     p1 = ap;
 574:     if (p1->op!=JBR || (p2 = p1->ref)==0)
 575:         return(p1);
 576:     while (p2->op == LABEL)
 577:         if ((p2 = p2->back) == 0)
 578:             return(p1);
 579:     if (p2->op!=JBR && p2->op!=JMP)
 580:         goto ivloop;
 581:     p2 = p2->forw;
 582:     p3 = p1->ref;
 583:     while (p3) {
 584:         if (p3->op==JBR || p3->op==JMP) {
 585:             if (p1==p3)
 586:                 return(p1);
 587:             ncmot++;
 588:             nchange++;
 589:             p1->back->forw = p2;
 590:             p1->forw->back = p3;
 591:             p2->back->forw = p3->forw;
 592:             p3->forw->back = p2->back;
 593:             p2->back = p1->back;
 594:             p3->forw = p1->forw;
 595:             decref(p1->ref);
 596:             return(p2);
 597:         } else
 598:             p3 = p3->forw;
 599:     }
 600:     return(p1);
 601: ivloop:
 602:     if (p1->forw->op!=LABEL)
 603:         return(p1);
 604:     p3 = p2 = p2->forw;
 605:     n = 16;
 606:     do {
 607:         if ((p3 = p3->forw) == 0 || p3==p1 || --n==0)
 608:             return(p1);
 609:     } while (p3->op!=CBR || p3->labno!=p1->forw->labno);
 610:     do
 611:         if ((p1 = p1->back) == 0)
 612:             return(ap);
 613:     while (p1!=p3);
 614:     p1 = ap;
 615:     tl = insertl(p1);
 616:     p3->subop = revbr[p3->subop];
 617:     decref(p3->ref);
 618:     p2->back->forw = p1;
 619:     p3->forw->back = p1;
 620:     p1->back->forw = p2;
 621:     p1->forw->back = p3;
 622:     t = p1->back;
 623:     p1->back = p2->back;
 624:     p2->back = t;
 625:     t = p1->forw;
 626:     p1->forw = p3->forw;
 627:     p3->forw = t;
 628:     p2 = insertl(p1->forw);
 629:     p3->labno = p2->labno;
 630:     p3->ref = p2;
 631:     decref(tl);
 632:     if (tl->refc<=0)
 633:         nrlab--;
 634:     loopiv++;
 635:     nchange++;
 636:     return(p3);
 637: }
 638: 
 639: comjump()
 640: {
 641:     register struct node *p1, *p2, *p3;
 642: 
 643:     for (p1 = first.forw; p1!=0; p1 = p1->forw)
 644:         if (p1->op==JBR && (p2 = p1->ref) && p2->refc > 1)
 645:             for (p3 = p1->forw; p3!=0; p3 = p3->forw)
 646:                 if (p3->op==JBR && p3->ref == p2)
 647:                     backjmp(p1, p3);
 648: }
 649: 
 650: backjmp(ap1, ap2)
 651: struct node *ap1, *ap2;
 652: {
 653:     register struct node *p1, *p2, *p3;
 654: 
 655:     p1 = ap1;
 656:     p2 = ap2;
 657:     for(;;) {
 658:         while ((p1 = p1->back) && p1->op==LABEL);
 659:         p2 = p2->back;
 660:         if (equop(p1, p2)) {
 661:             p3 = insertl(p1);
 662:             p2->back->forw = p2->forw;
 663:             p2->forw->back = p2->back;
 664:             p2 = p2->forw;
 665:             decref(p2->ref);
 666:             p2->labno = p3->labno;
 667:             p2->ref = p3;
 668:             nchange++;
 669:             ncomj++;
 670:         } else
 671:             return;
 672:     }
 673: }

Defined functions

Defined variables