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 *
xalloc(n)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
main(argc,argv)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
input()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 *
getline()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
getnum(p)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
locuse(p)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
locdef(p)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
output()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 *
copy(ap)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
opsetup()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 *
oplook()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
refcount()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
iterate()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