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