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