2.11BSD#431 - /usr/src/lib/c2/c20.c

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

Defined functions

Defined variables

Defined macros