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