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