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