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