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