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