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

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

Defined functions

Defined variables