1 #ifndef lint 2 static char sccsid[] = "@(#)c20.c 4.10 (Berkeley) 08/22/85"; 3 #endif 4 5 /* 6 * C object code improver 7 */ 8 9 #include "c2.h" 10 #include <stdio.h> 11 #include <ctype.h> 12 #include <sys/types.h> 13 14 char *malloc(); 15 char firstr[sizeof (char *)]; 16 char *currentb; 17 char *newa; 18 char *lasta; 19 char *lastr; 20 int ncore; 21 22 int ioflag; 23 int fflag; 24 25 long isn = 2000000; 26 27 struct optab *oplook(); 28 struct optab *getline(); 29 30 long lgensym[10] = 31 {100000L,200000L,300000L,400000L,500000L,600000L,700000L,800000L,900000L,1000000L}; 32 33 #define ALLOCSIZE 4096 34 35 /* 36 * Cheapo space allocator. Works much like the old one but uses malloc() 37 * and doesn't clash with stdio. Assumes that no one requests more than 38 * ALLOCSIZE bytes at a time. 39 */ 40 char * 41 xalloc(n) 42 int n; 43 { 44 register char *nextb = * (char **) currentb; 45 46 if (n == 0) { /* Free everything */ 47 currentb = firstr; 48 nextb = * (char **) currentb; 49 } 50 if (nextb == NULL) { 51 if ((nextb = malloc(ALLOCSIZE)) == NULL) { 52 fprintf(stderr, "Optimizer: out of space\n"); 53 exit(1); 54 } 55 ncore += (ALLOCSIZE/1024); 56 * (char **) currentb = nextb; 57 * (char **) nextb = NULL; 58 } 59 lasta = nextb + sizeof nextb; 60 lastr = nextb + ALLOCSIZE; 61 currentb = nextb; 62 newa = lasta; 63 lasta += XALIGN(n); 64 return(newa); 65 } 66 67 main(argc, argv) 68 char **argv; 69 { 70 register int niter, maxiter, isend; 71 int nflag,infound; 72 73 nflag = 0; infound=0; argc--; argv++; 74 while (argc>0) {/* get flags */ 75 if (**argv=='+') debug++; 76 else if (**argv=='-') { 77 if ((*argv)[1]=='i') ioflag++; 78 else if ((*argv)[1]=='f') fflag++; 79 else nflag++; 80 } else if (infound==0) { 81 if (freopen(*argv, "r", stdin) ==NULL) { 82 fprintf(stderr,"C2: can't find %s\n", *argv); 83 exit(1); 84 } 85 ++infound; 86 } else if (freopen(*argv, "w", stdout) ==NULL) { 87 fprintf(stderr,"C2: can't create %s\n", *argv); 88 exit(1); 89 } 90 argc--; argv++; 91 } 92 opsetup(); 93 maxiter = 0; 94 do { 95 (void) xalloc(0); 96 isend = input(); 97 niter = 0; 98 bmove(); 99 do { 100 refcount(); 101 do { 102 iterate(); 103 clearreg(); 104 niter++; 105 } while (nchange); 106 comjump(); 107 rmove(); 108 } while (nchange || jumpsw()); 109 addsob(); 110 output(); 111 if (niter > maxiter) 112 maxiter = niter; 113 } while (isend); 114 if (nflag) { 115 fprintf(stderr,"%d iterations\n", maxiter); 116 fprintf(stderr,"%d jumps to jumps\n", nbrbr); 117 fprintf(stderr,"%d inst. after jumps\n", iaftbr); 118 fprintf(stderr,"%d jumps to .+1\n", njp1); 119 fprintf(stderr,"%d redundant labels\n", nrlab); 120 fprintf(stderr,"%d cross-jumps\n", nxjump); 121 fprintf(stderr,"%d code motions\n", ncmot); 122 fprintf(stderr,"%d branches reversed\n", nrevbr); 123 fprintf(stderr,"%d redundant moves\n", redunm); 124 fprintf(stderr,"%d simplified addresses\n", nsaddr); 125 fprintf(stderr,"%d loops inverted\n", loopiv); 126 fprintf(stderr,"%d redundant jumps\n", nredunj); 127 fprintf(stderr,"%d common seqs before jmp's\n", ncomj); 128 fprintf(stderr,"%d skips over jumps\n", nskip); 129 fprintf(stderr,"%d sob's added\n", nsob); 130 fprintf(stderr,"%d redundant tst's\n", nrtst); 131 fprintf(stderr,"%d jump on bit\n", nbj); 132 fprintf(stderr,"%d field operations\n", nfield); 133 fprintf(stderr,"%dK core\n", ncore); 134 } 135 putc('\n',stdout); 136 fflush(stdout); exit(0); 137 } 138 139 input() 140 { 141 register struct node *p, *lastp; 142 struct optab *opp; register char *cp1; 143 static struct optab F77JSW = {".long", T(JSW,1)}; 144 145 lastp = &first; 146 for (;;) { 147 top: 148 opp = getline(); 149 if (debug && opp==0) fprintf(stderr,"? %s\n",line); 150 switch (opp->opcode&0377) { 151 152 case LABEL: 153 p = alloc(sizeof first); 154 if (isdigit(line[0]) && (p->labno=locdef(line)) || 155 (line[0] == 'L') && (p->labno=getnum(line+1))) { 156 p->combop = LABEL; 157 if (p->labno<100000L && isn<=p->labno) isn=1+p->labno; 158 p->code = 0; 159 } else { 160 p->combop = DLABEL; 161 p->labno = 0; 162 p->code = copy(line); 163 } 164 break; 165 166 case LGEN: 167 if (*curlp!='L' && !locuse(curlp)) goto std; 168 opp= &F77JSW; 169 case JBR: 170 if (opp->opcode==T(JBR,RET) || opp->opcode==T(JBR,RSB)) goto std; 171 case CBR: 172 case JMP: 173 case JSW: 174 case SOBGEQ: case SOBGTR: case AOBLEQ: case AOBLSS: case ACB: 175 p = alloc(sizeof first); 176 p->combop = opp->opcode; p->code=0; cp1=curlp; 177 if ((!isdigit(*cp1) || 0==(p->labno=locuse(cp1))) && 178 (*cp1!='L' || 0==(p->labno = getnum(cp1+1)))) {/* jbs, etc.? */ 179 while (*cp1++); while (*--cp1!=',' && cp1!=curlp); 180 if (cp1==curlp || 181 (!isdigit(*++cp1) || 0==(p->labno=locuse(cp1))) && 182 (*cp1!='L' || 0==(p->labno=getnum(cp1+1)))) 183 p->labno = 0; 184 else *--cp1=0; 185 p->code = copy(curlp); 186 } 187 if (isn<=p->labno) isn=1+p->labno; 188 break; 189 190 case MOVA: 191 p=alloc(sizeof first); 192 p->combop=opp->opcode; p->code=0; cp1=curlp+1; 193 if (cp1[-1]=='L' || isdigit(cp1[-1])) { 194 while (*cp1++!=','); *--cp1=0; 195 if (0!=(p->labno=locuse(curlp)) || 196 0!=(p->labno=getnum(curlp+1))) p->code=copy(cp1+1); 197 else {*cp1=','; p->code=copy(curlp);} 198 } else {p->code=copy(--cp1); p->labno=0;} 199 break; 200 201 case SET: 202 case COMM: 203 case LCOMM: 204 printf("%s\n",line); goto top; 205 206 case BSS: 207 case DATA: 208 for (;;) { 209 printf("%s%c",line,(opp->opcode==LABEL ? ':' : '\n')); 210 if (opp->opcode==TEXT) goto top; 211 if (END==(opp=getline())->opcode) {/* dangling .data is bad for you */ 212 printf(".text\n"); 213 break; 214 } 215 } 216 217 std: 218 default: 219 p = alloc(sizeof first); 220 p->combop = opp->opcode; 221 p->labno = 0; 222 p->code = copy(curlp); 223 break; 224 225 } 226 p->forw = 0; 227 p->back = lastp; 228 p->pop = opp; 229 lastp->forw = p; 230 lastp = p; 231 p->ref = 0; 232 if (p->op==CASE) { 233 char *lp; int ncase; 234 lp=curlp; while (*lp++); while (*--lp!='$'); ncase=getnum(lp+1); 235 if (LABEL!=(getline())->opcode) { 236 fprintf(stderr, "c2: garbled 'case' instruction\n"); 237 exit(-2); 238 } 239 do { 240 if (WGEN!=(getline())->opcode) { 241 fprintf(stderr, "c2: garbled 'case' instruction\n"); 242 exit(-3); 243 } 244 p = alloc(sizeof first); p->combop = JSW; p->code = 0; 245 lp=curlp; while(*lp++!='-'); *--lp=0; p->labno=getnum(curlp+1); 246 if (isn<=p->labno) isn=1+p->labno; 247 p->forw = 0; p->back = lastp; lastp->forw = p; lastp = p; 248 p->ref = 0; p->pop=0; 249 } while (--ncase>=0); 250 } 251 if (opp->opcode==EROU) 252 return(1); 253 if (opp->opcode==END) 254 return(0); 255 } 256 } 257 258 struct optab * 259 getline() 260 { 261 register char *lp; 262 register c; 263 static struct optab OPLABEL={"",LABEL}; 264 static struct optab OPEND={"",END}; 265 266 lp = line; 267 while (EOF!=(c=getchar()) && isspace(c)); 268 while (EOF!=c) { 269 if (c==':') { 270 *lp++ = 0; 271 return(&OPLABEL); 272 } 273 if (c=='\n') { 274 *lp++ = 0; 275 return(oplook()); 276 } 277 *lp++ = c; 278 c = getchar(); 279 } 280 *lp++ = 0; 281 return(&OPEND); 282 } 283 284 long 285 getnum(p) 286 register char *p; 287 { 288 register c; int neg; register long n; 289 290 n = 0; neg=0; if (*p=='-') {++neg; ++p;} 291 while (isdigit(c = *p++)) { 292 c -= '0'; n *= 10; if (neg) n -= c; else n += c; 293 } 294 if (*--p != 0) 295 return(0); 296 return(n); 297 } 298 299 locuse(p) 300 register char *p; 301 { 302 if (!isdigit(p[0]) || p[1] != 'f' && p[1] != 'b' || p[2]) return(0); 303 return (lgensym[p[0] - '0'] - (p[1] == 'b')); 304 } 305 306 locdef(p) 307 register char *p; 308 { 309 310 if (!isdigit(p[0]) || p[1]) return(0); 311 return (lgensym[p[0] - '0']++); 312 } 313 314 output() 315 { 316 register struct node *t; 317 int casebas; 318 319 t = &first; 320 while (t = t->forw) switch (t->op) { 321 322 case END: 323 fflush(stdout); 324 return; 325 326 case LABEL: 327 printf("L%d:", t->labno); 328 continue; 329 330 case DLABEL: 331 printf("%s:", t->code); 332 continue; 333 334 case CASE: 335 casebas=0; 336 337 default: std: 338 if (t->pop==0) {/* must find it */ 339 register struct optab *p; 340 for (p=optab; p->opstring[0]; ++p) 341 if (p->opcode==t->combop) {t->pop=p; break;} 342 } 343 printf("%s", t->pop->opstring); 344 if (t->code) printf("\t%s", t->code); 345 if (t->labno!=0) printf("%cL%d\n", 346 (t->code ? ',' : '\t'), 347 t->labno); 348 else printf("\n"); 349 continue; 350 351 case MOVA: 352 if (t->labno==0) goto std; 353 printf("mova%c\tL%d,%s\n","bwlq"[t->subop-BYTE],t->labno,t->code); 354 continue; 355 356 case JSW: 357 if (t->subop!=0) {/* F77JSW */ 358 printf(".long\tL%d\n",t->labno); continue; 359 } 360 if (casebas==0) printf("L%d:\n",casebas=isn++); 361 printf(".word L%d-L%d\n", t->labno, casebas); 362 continue; 363 case MOV: 364 if (!fflag) goto std; 365 if (t->forw) if(t->forw->op == CBR) goto std; 366 if (*t->code == '$') goto std; 367 if (t->subop == FFLOAT) 368 { 369 printf("movl\t%s\n", t->code); 370 continue; 371 } 372 if (t->subop == DFLOAT || t->subop == GFLOAT) 373 { 374 printf("movq\t%s\n", t->code); 375 continue; 376 } 377 if (t->subop == HFLOAT) 378 { 379 printf("movo\t%s\n", t->code); 380 continue; 381 } 382 goto std; 383 384 } 385 } 386 387 char * 388 copy(ap) 389 char *ap; 390 { 391 register char *p, *np; 392 char *onp; 393 register n; 394 int na; 395 396 na = nargs(); 397 p = ap; 398 n = 0; 399 if (*p==0) 400 return(0); 401 do 402 n++; 403 while (*p++); 404 if (na>1) { 405 p = (&ap)[1]; 406 while (*p++) 407 n++; 408 } 409 onp = np = (char *) alloc(n); 410 p = ap; 411 while (*np++ = *p++); 412 if (na>1) { 413 p = (&ap)[1]; 414 np--; 415 while (*np++ = *p++); 416 } 417 return(onp); 418 } 419 420 #define OPHS 560 421 struct optab *ophash[OPHS]; 422 423 opsetup() 424 { 425 register struct optab *optp, **ophp; 426 register int i,t; 427 428 for(i=NREG+5;--i>=0;) regs[i] = malloc(C2_ASIZE); 429 for (optp = optab; optp->opstring[0]; optp++) { 430 t=7; i=0; while (--t>=0) i+= i+optp->opstring[t]; 431 ophp = &ophash[i % OPHS]; 432 while (*ophp++) { 433 /* fprintf(stderr,"\ncollision: %d %s %s", 434 /* ophp-1-ophash,optp->opstring,(*(ophp-1))->opstring); 435 */ 436 if (ophp >= &ophash[OPHS]) 437 ophp = ophash; 438 } 439 *--ophp = optp; 440 } 441 } 442 443 struct optab * 444 oplook() 445 { 446 register struct optab *optp,**ophp; 447 register char *p,*p2; 448 register int t; 449 char tempop[20]; 450 static struct optab OPNULL={"",0}; 451 452 for (p=line, p2=tempop; *p && !isspace(*p); *p2++= *p++); *p2=0; p2=p; 453 while (isspace(*p2)) ++p2; curlp=p2; 454 t=0; while(--p>=line) t += t+*p; ophp = &ophash[t % OPHS]; 455 while (optp = *ophp) { 456 if (equstr(tempop,optp->opstring)) return(optp); 457 if ((++ophp) >= &ophash[OPHS]) ophp = ophash; 458 } 459 curlp = line; 460 return(&OPNULL); 461 } 462 463 refcount() 464 { 465 register struct node *p, *lp, *tp; 466 struct node *labhash[LABHS]; 467 register struct node **hp; 468 469 for (hp = labhash; hp < &labhash[LABHS];) 470 *hp++ = 0; 471 for (p = first.forw; p!=0; p = p->forw) 472 if (p->op==LABEL) { 473 labhash[p->labno % LABHS] = p; 474 p->refc = 0; 475 } 476 for (p = first.forw; p!=0; p = p->forw) { 477 if (p->combop==JBR || p->op==CBR || p->op==JSW || p->op==JMP 478 || p->op==SOBGEQ || p->op==SOBGTR || p->op==AOBLEQ || p->op==AOBLSS 479 || p->op==ACB || (p->op==MOVA && p->labno!=0)) { 480 p->ref = 0; 481 lp = labhash[p->labno % LABHS]; 482 if (lp==0 || p->labno!=lp->labno) 483 for (lp = first.forw; lp!=0; lp = lp->forw) { 484 if (lp->op==LABEL && p->labno==lp->labno) 485 break; 486 } 487 if (lp) { 488 tp = nonlab(lp)->back; 489 if (tp!=lp) { 490 p->labno = tp->labno; 491 lp = tp; 492 } 493 p->ref = lp; 494 lp->refc++; 495 } 496 } 497 } 498 for (p = first.forw; p!=0; p = p->forw) 499 if (p->op==LABEL && p->refc==0 500 && (lp = nonlab(p))->op && lp->op!=JSW) 501 decref(p); 502 } 503 504 iterate() 505 { 506 register struct node *p, *rp, *p1; 507 508 nchange = 0; 509 for (p = first.forw; p!=0; p = p->forw) { 510 if ((p->op==JBR||p->op==CBR||p->op==JSW) && p->ref) { 511 rp = nonlab(p->ref); 512 if (rp->op==JBR && rp->labno && p->labno!=rp->labno) { 513 nbrbr++; 514 p->labno = rp->labno; 515 decref(p->ref); 516 rp->ref->refc++; 517 p->ref = rp->ref; 518 nchange++; 519 } 520 } 521 #ifndef COPYCODE 522 if (p->op==CBR && (p1 = p->forw)->combop==JBR) {/* combop: RET problems */ 523 #else 524 if (p->op==CBR && (p1 = p->forw)->combop==JBR && 525 p->ref) {/* combop: RET problems */ 526 #endif 527 rp = p->ref; 528 do 529 rp = rp->back; 530 while (rp->op==LABEL); 531 if (rp==p1) { 532 decref(p->ref); 533 p->ref = p1->ref; 534 p->labno = p1->labno; 535 #ifdef COPYCODE 536 if (p->labno == 0) 537 p->code = p1->code; 538 #endif 539 p1->forw->back = p; 540 p->forw = p1->forw; 541 p->subop = revbr[p->subop]; 542 p->pop=0; 543 nchange++; 544 nskip++; 545 } 546 } 547 if (p->op==JBR || p->op==JMP) { 548 while (p->forw && p->forw->op!=LABEL && p->forw->op!=DLABEL 549 && p->forw->op!=EROU && p->forw->op!=END 550 && p->forw->op!=ALIGN 551 && p->forw->op!=0 && p->forw->op!=DATA) { 552 nchange++; 553 iaftbr++; 554 if (p->forw->ref) 555 decref(p->forw->ref); 556 p->forw = p->forw->forw; 557 p->forw->back = p; 558 } 559 rp = p->forw; 560 while (rp && rp->op==LABEL) { 561 if (p->ref == rp) { 562 p->back->forw = p->forw; 563 p->forw->back = p->back; 564 p = p->back; 565 decref(rp); 566 nchange++; 567 njp1++; 568 break; 569 } 570 rp = rp->forw; 571 } 572 xjump(p); 573 p = codemove(p); 574 } 575 } 576 } 577 578 xjump(p1) 579 register struct node *p1; 580 { 581 register struct node *p2, *p3; 582 583 if ((p2 = p1->ref)==0) 584 return; 585 for (;;) { 586 while ((p1 = p1->back) && p1->op==LABEL); 587 while ((p2 = p2->back) && p2->op==LABEL); 588 if (!equop(p1, p2) || p1==p2) 589 return; 590 p3 = insertl(p2); 591 p1->combop = JBR; 592 p1->pop=0; 593 p1->ref = p3; 594 p1->labno = p3->labno; 595 p1->code = 0; 596 nxjump++; 597 nchange++; 598 } 599 } 600 601 struct node * 602 insertl(np) 603 register struct node *np; 604 { 605 register struct node *lp; 606 607 if (np->op == LABEL) { 608 np->refc++; 609 return(np); 610 } 611 if (np->back->op == LABEL) { 612 np = np->back; 613 np->refc++; 614 return(np); 615 } 616 lp = alloc(sizeof first); 617 lp->combop = LABEL; 618 lp->labno = isn++; 619 lp->ref = 0; 620 lp->code = 0; 621 lp->refc = 1; 622 lp->back = np->back; 623 lp->forw = np; 624 np->back->forw = lp; 625 np->back = lp; 626 return(lp); 627 } 628 629 struct node * 630 codemove(ap) 631 struct node *ap; 632 { 633 register struct node *p1, *p2, *p3; 634 struct node *t, *tl; 635 int n; 636 637 p1 = ap; 638 /* last clause to avoid infinite loop on partial compiler droppings: 639 L183: jbr L179 640 L191: jbr L179 641 casel r0,$0,$1 642 L193: .word L183-L193 643 .word L191-L193 644 L179: ret 645 */ 646 if (p1->op!=JBR || (p2 = p1->ref)==0 || p2==p1->forw) 647 return(p1); 648 while (p2->op == LABEL) 649 if ((p2 = p2->back) == 0) 650 return(p1); 651 if (p2->op!=JBR && p2->op!=JMP) 652 goto ivloop; 653 p2 = p2->forw; 654 p3 = p1->ref; 655 while (p3) { 656 if (p3->op==JBR || p3->op==JMP) { 657 if (p1==p3) 658 return(p1); 659 ncmot++; 660 nchange++; 661 p1->back->forw = p2; 662 p1->forw->back = p3; 663 p2->back->forw = p3->forw; 664 p3->forw->back = p2->back; 665 p2->back = p1->back; 666 p3->forw = p1->forw; 667 decref(p1->ref); 668 return(p2); 669 } else 670 p3 = p3->forw; 671 } 672 return(p1); 673 ivloop: 674 if (p1->forw->op!=LABEL) 675 return(p1); 676 p3 = p2 = p2->forw; 677 n = 16; 678 do { 679 if ((p3 = p3->forw) == 0 || p3==p1 || --n==0) 680 return(p1); 681 } while (p3->op!=CBR || p3->labno!=p1->forw->labno); 682 do 683 if ((p1 = p1->back) == 0) 684 return(ap); 685 while (p1!=p3); 686 p1 = ap; 687 tl = insertl(p1); 688 p3->subop = revbr[p3->subop]; 689 p3->pop=0; 690 decref(p3->ref); 691 p2->back->forw = p1; 692 p3->forw->back = p1; 693 p1->back->forw = p2; 694 p1->forw->back = p3; 695 t = p1->back; 696 p1->back = p2->back; 697 p2->back = t; 698 t = p1->forw; 699 p1->forw = p3->forw; 700 p3->forw = t; 701 p2 = insertl(p1->forw); 702 p3->labno = p2->labno; 703 #ifdef COPYCODE 704 if (p3->labno == 0) 705 p3->code = p2->code; 706 #endif 707 p3->ref = p2; 708 decref(tl); 709 if (tl->refc<=0) 710 nrlab--; 711 loopiv++; 712 nchange++; 713 return(p3); 714 } 715 716 comjump() 717 { 718 register struct node *p1, *p2, *p3; 719 720 for (p1 = first.forw; p1!=0; p1 = p1->forw) 721 if (p1->op==JBR && ((p2 = p1->ref) && p2->refc > 1 722 || p1->subop==RET || p1->subop==RSB)) 723 for (p3 = p1->forw; p3!=0; p3 = p3->forw) 724 if (p3->op==JBR && p3->ref == p2) 725 backjmp(p1, p3); 726 } 727 728 backjmp(ap1, ap2) 729 struct node *ap1, *ap2; 730 { 731 register struct node *p1, *p2, *p3; 732 733 p1 = ap1; 734 p2 = ap2; 735 for(;;) { 736 while ((p1 = p1->back) && p1->op==LABEL); 737 p2 = p2->back; 738 if (equop(p1, p2)) { 739 p3 = insertl(p1); 740 p2->back->forw = p2->forw; 741 p2->forw->back = p2->back; 742 p2 = p2->forw; 743 decref(p2->ref); 744 p2->combop = JBR; /* to handle RET */ 745 p2->pop=0; 746 p2->labno = p3->labno; 747 #ifdef COPYCODE 748 p2->code = 0; 749 #endif 750 p2->ref = p3; 751 nchange++; 752 ncomj++; 753 } else 754 return; 755 } 756 } 757