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