1 #ifndef lint 2 static char sccsid[] = "@(#)c20.c 4.11 (Berkeley) 06/23/90"; 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 = ap, *np; 392 char *onp; 393 register n; 394 395 if (*p++ == 0) 396 return(0); 397 n = 1; 398 do 399 n++; 400 while (*p++); 401 onp = np = (char *) alloc(n); 402 p = ap; 403 while (*np++ = *p++); 404 return (onp); 405 } 406 407 #define OPHS 560 408 struct optab *ophash[OPHS]; 409 410 opsetup() 411 { 412 register struct optab *optp, **ophp; 413 register int i,t; 414 415 for(i=NREG+5;--i>=0;) regs[i] = malloc(C2_ASIZE); 416 for (optp = optab; optp->opstring[0]; optp++) { 417 t=7; i=0; while (--t>=0) i+= i+optp->opstring[t]; 418 ophp = &ophash[i % OPHS]; 419 while (*ophp++) { 420 /* fprintf(stderr,"\ncollision: %d %s %s", 421 /* ophp-1-ophash,optp->opstring,(*(ophp-1))->opstring); 422 */ 423 if (ophp >= &ophash[OPHS]) 424 ophp = ophash; 425 } 426 *--ophp = optp; 427 } 428 } 429 430 struct optab * 431 oplook() 432 { 433 register struct optab *optp,**ophp; 434 register char *p,*p2; 435 register int t; 436 char tempop[20]; 437 static struct optab OPNULL={"",0}; 438 439 for (p=line, p2=tempop; *p && !isspace(*p); *p2++= *p++); *p2=0; p2=p; 440 while (isspace(*p2)) ++p2; curlp=p2; 441 t=0; while(--p>=line) t += t+*p; ophp = &ophash[t % OPHS]; 442 while (optp = *ophp) { 443 if (equstr(tempop,optp->opstring)) return(optp); 444 if ((++ophp) >= &ophash[OPHS]) ophp = ophash; 445 } 446 curlp = line; 447 return(&OPNULL); 448 } 449 450 refcount() 451 { 452 register struct node *p, *lp, *tp; 453 struct node *labhash[LABHS]; 454 register struct node **hp; 455 456 for (hp = labhash; hp < &labhash[LABHS];) 457 *hp++ = 0; 458 for (p = first.forw; p!=0; p = p->forw) 459 if (p->op==LABEL) { 460 labhash[p->labno % LABHS] = p; 461 p->refc = 0; 462 } 463 for (p = first.forw; p!=0; p = p->forw) { 464 if (p->combop==JBR || p->op==CBR || p->op==JSW || p->op==JMP 465 || p->op==SOBGEQ || p->op==SOBGTR || p->op==AOBLEQ || p->op==AOBLSS 466 || p->op==ACB || (p->op==MOVA && p->labno!=0)) { 467 p->ref = 0; 468 lp = labhash[p->labno % LABHS]; 469 if (lp==0 || p->labno!=lp->labno) 470 for (lp = first.forw; lp!=0; lp = lp->forw) { 471 if (lp->op==LABEL && p->labno==lp->labno) 472 break; 473 } 474 if (lp) { 475 tp = nonlab(lp)->back; 476 if (tp!=lp) { 477 p->labno = tp->labno; 478 lp = tp; 479 } 480 p->ref = lp; 481 lp->refc++; 482 } 483 } 484 } 485 for (p = first.forw; p!=0; p = p->forw) 486 if (p->op==LABEL && p->refc==0 487 && (lp = nonlab(p))->op && lp->op!=JSW) 488 decref(p); 489 } 490 491 iterate() 492 { 493 register struct node *p, *rp, *p1; 494 495 nchange = 0; 496 for (p = first.forw; p!=0; p = p->forw) { 497 if ((p->op==JBR||p->op==CBR||p->op==JSW) && p->ref) { 498 rp = nonlab(p->ref); 499 if (rp->op==JBR && rp->labno && p->labno!=rp->labno) { 500 nbrbr++; 501 p->labno = rp->labno; 502 decref(p->ref); 503 rp->ref->refc++; 504 p->ref = rp->ref; 505 nchange++; 506 } 507 } 508 #ifndef COPYCODE 509 if (p->op==CBR && (p1 = p->forw)->combop==JBR) {/* combop: RET problems */ 510 #else 511 if (p->op==CBR && (p1 = p->forw)->combop==JBR && 512 p->ref) {/* combop: RET problems */ 513 #endif 514 rp = p->ref; 515 do 516 rp = rp->back; 517 while (rp->op==LABEL); 518 if (rp==p1) { 519 decref(p->ref); 520 p->ref = p1->ref; 521 p->labno = p1->labno; 522 #ifdef COPYCODE 523 if (p->labno == 0) 524 p->code = p1->code; 525 #endif 526 p1->forw->back = p; 527 p->forw = p1->forw; 528 p->subop = revbr[p->subop]; 529 p->pop=0; 530 nchange++; 531 nskip++; 532 } 533 } 534 if (p->op==JBR || p->op==JMP) { 535 while (p->forw && p->forw->op!=LABEL && p->forw->op!=DLABEL 536 && p->forw->op!=EROU && p->forw->op!=END 537 && p->forw->op!=ALIGN 538 && p->forw->op!=0 && p->forw->op!=DATA) { 539 nchange++; 540 iaftbr++; 541 if (p->forw->ref) 542 decref(p->forw->ref); 543 p->forw = p->forw->forw; 544 p->forw->back = p; 545 } 546 rp = p->forw; 547 while (rp && rp->op==LABEL) { 548 if (p->ref == rp) { 549 p->back->forw = p->forw; 550 p->forw->back = p->back; 551 p = p->back; 552 decref(rp); 553 nchange++; 554 njp1++; 555 break; 556 } 557 rp = rp->forw; 558 } 559 xjump(p); 560 p = codemove(p); 561 } 562 } 563 } 564 565 xjump(p1) 566 register struct node *p1; 567 { 568 register struct node *p2, *p3; 569 570 if ((p2 = p1->ref)==0) 571 return; 572 for (;;) { 573 while ((p1 = p1->back) && p1->op==LABEL); 574 while ((p2 = p2->back) && p2->op==LABEL); 575 if (!equop(p1, p2) || p1==p2) 576 return; 577 p3 = insertl(p2); 578 p1->combop = JBR; 579 p1->pop=0; 580 p1->ref = p3; 581 p1->labno = p3->labno; 582 p1->code = 0; 583 nxjump++; 584 nchange++; 585 } 586 } 587 588 struct node * 589 insertl(np) 590 register struct node *np; 591 { 592 register struct node *lp; 593 594 if (np->op == LABEL) { 595 np->refc++; 596 return(np); 597 } 598 if (np->back->op == LABEL) { 599 np = np->back; 600 np->refc++; 601 return(np); 602 } 603 lp = alloc(sizeof first); 604 lp->combop = LABEL; 605 lp->labno = isn++; 606 lp->ref = 0; 607 lp->code = 0; 608 lp->refc = 1; 609 lp->back = np->back; 610 lp->forw = np; 611 np->back->forw = lp; 612 np->back = lp; 613 return(lp); 614 } 615 616 struct node * 617 codemove(ap) 618 struct node *ap; 619 { 620 register struct node *p1, *p2, *p3; 621 struct node *t, *tl; 622 int n; 623 624 p1 = ap; 625 /* last clause to avoid infinite loop on partial compiler droppings: 626 L183: jbr L179 627 L191: jbr L179 628 casel r0,$0,$1 629 L193: .word L183-L193 630 .word L191-L193 631 L179: ret 632 */ 633 if (p1->op!=JBR || (p2 = p1->ref)==0 || p2==p1->forw) 634 return(p1); 635 while (p2->op == LABEL) 636 if ((p2 = p2->back) == 0) 637 return(p1); 638 if (p2->op!=JBR && p2->op!=JMP) 639 goto ivloop; 640 p2 = p2->forw; 641 p3 = p1->ref; 642 while (p3) { 643 if (p3->op==JBR || p3->op==JMP) { 644 if (p1==p3) 645 return(p1); 646 ncmot++; 647 nchange++; 648 p1->back->forw = p2; 649 p1->forw->back = p3; 650 p2->back->forw = p3->forw; 651 p3->forw->back = p2->back; 652 p2->back = p1->back; 653 p3->forw = p1->forw; 654 decref(p1->ref); 655 return(p2); 656 } else 657 p3 = p3->forw; 658 } 659 return(p1); 660 ivloop: 661 if (p1->forw->op!=LABEL) 662 return(p1); 663 p3 = p2 = p2->forw; 664 n = 16; 665 do { 666 if ((p3 = p3->forw) == 0 || p3==p1 || --n==0) 667 return(p1); 668 } while (p3->op!=CBR || p3->labno!=p1->forw->labno); 669 do 670 if ((p1 = p1->back) == 0) 671 return(ap); 672 while (p1!=p3); 673 p1 = ap; 674 tl = insertl(p1); 675 p3->subop = revbr[p3->subop]; 676 p3->pop=0; 677 decref(p3->ref); 678 p2->back->forw = p1; 679 p3->forw->back = p1; 680 p1->back->forw = p2; 681 p1->forw->back = p3; 682 t = p1->back; 683 p1->back = p2->back; 684 p2->back = t; 685 t = p1->forw; 686 p1->forw = p3->forw; 687 p3->forw = t; 688 p2 = insertl(p1->forw); 689 p3->labno = p2->labno; 690 #ifdef COPYCODE 691 if (p3->labno == 0) 692 p3->code = p2->code; 693 #endif 694 p3->ref = p2; 695 decref(tl); 696 if (tl->refc<=0) 697 nrlab--; 698 loopiv++; 699 nchange++; 700 return(p3); 701 } 702 703 comjump() 704 { 705 register struct node *p1, *p2, *p3; 706 707 for (p1 = first.forw; p1!=0; p1 = p1->forw) 708 if (p1->op==JBR && ((p2 = p1->ref) && p2->refc > 1 709 || p1->subop==RET || p1->subop==RSB)) 710 for (p3 = p1->forw; p3!=0; p3 = p3->forw) 711 if (p3->op==JBR && p3->ref == p2) 712 backjmp(p1, p3); 713 } 714 715 backjmp(ap1, ap2) 716 struct node *ap1, *ap2; 717 { 718 register struct node *p1, *p2, *p3; 719 720 p1 = ap1; 721 p2 = ap2; 722 for(;;) { 723 while ((p1 = p1->back) && p1->op==LABEL); 724 p2 = p2->back; 725 if (equop(p1, p2)) { 726 p3 = insertl(p1); 727 p2->back->forw = p2->forw; 728 p2->forw->back = p2->back; 729 p2 = p2->forw; 730 decref(p2->ref); 731 p2->combop = JBR; /* to handle RET */ 732 p2->pop=0; 733 p2->labno = p3->labno; 734 #ifdef COPYCODE 735 p2->code = 0; 736 #endif 737 p2->ref = p3; 738 nchange++; 739 ncomj++; 740 } else 741 return; 742 } 743 } 744