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