[unix-history] / usr / src / libexec / pcc / c2.vax / c20.c

#ifndef lint
static	char sccsid[] = "@(#)c20.c	4.11 (Berkeley) 6/23/90";
#endif

/*
 *	 C object code improver
 */

#include "c2.h"
#include <stdio.h>
#include <ctype.h>
#include <sys/types.h>

char *malloc();
char firstr[sizeof (char *)];
char *currentb;
char *newa;
char *lasta;
char *lastr;
int ncore;

int ioflag;
int fflag;

long	isn	= 2000000;

struct optab *oplook();
struct optab *getline();

long lgensym[10] =
  {100000L,200000L,300000L,400000L,500000L,600000L,700000L,800000L,900000L,1000000L};

#define ALLOCSIZE	4096

/*
 * Cheapo space allocator.  Works much like the old one but uses malloc()
 * and doesn't clash with stdio.  Assumes that no one requests more than
 * ALLOCSIZE bytes at a time.
 */
char *
xalloc(n)
int n;
{
	register char *nextb = * (char **) currentb;

	if (n == 0) {	/* Free everything */
		currentb = firstr;
		nextb = * (char **) currentb;
	}
	if (nextb == NULL) {
		if ((nextb = malloc(ALLOCSIZE)) == NULL) {
			fprintf(stderr, "Optimizer: out of space\n");
			exit(1);
		}
		ncore += (ALLOCSIZE/1024);
		* (char **) currentb = nextb;
		* (char **) nextb = NULL;
	}
	lasta = nextb + sizeof nextb;
	lastr = nextb + ALLOCSIZE;
	currentb = nextb;
	newa = lasta;
	lasta += XALIGN(n);
	return(newa);
}

main(argc, argv)
char **argv;
{
	register int niter, maxiter, isend;
	int nflag,infound;

	nflag = 0; infound=0; argc--; argv++;
	while (argc>0) {/* get flags */
		if (**argv=='+') debug++;
		else if (**argv=='-') {
			if ((*argv)[1]=='i') ioflag++;
			else if ((*argv)[1]=='f') fflag++;
			else nflag++;
		} else if (infound==0) {
			if (freopen(*argv, "r", stdin) ==NULL) {
				fprintf(stderr,"C2: can't find %s\n", *argv);
				exit(1);
			}
			++infound;
		} else if (freopen(*argv, "w", stdout) ==NULL) {
			fprintf(stderr,"C2: can't create %s\n", *argv);
			exit(1);
		}
		argc--; argv++;
	}
	opsetup();
	maxiter = 0;
	do {
		(void) xalloc(0);
		isend = input();
		niter = 0;
		bmove();
		do {
			refcount();
			do {
				iterate();
				clearreg();
				niter++;
			} while (nchange);
			comjump();
			rmove();
		} while (nchange || jumpsw());
		addsob();
		output();
		if (niter > maxiter)
			maxiter = niter;
	} while (isend);
	if (nflag) {
		fprintf(stderr,"%d iterations\n", maxiter);
		fprintf(stderr,"%d jumps to jumps\n", nbrbr);
		fprintf(stderr,"%d inst. after jumps\n", iaftbr);
		fprintf(stderr,"%d jumps to .+1\n", njp1);
		fprintf(stderr,"%d redundant labels\n", nrlab);
		fprintf(stderr,"%d cross-jumps\n", nxjump);
		fprintf(stderr,"%d code motions\n", ncmot);
		fprintf(stderr,"%d branches reversed\n", nrevbr);
		fprintf(stderr,"%d redundant moves\n", redunm);
		fprintf(stderr,"%d simplified addresses\n", nsaddr);
		fprintf(stderr,"%d loops inverted\n", loopiv);
		fprintf(stderr,"%d redundant jumps\n", nredunj);
		fprintf(stderr,"%d common seqs before jmp's\n", ncomj);
		fprintf(stderr,"%d skips over jumps\n", nskip);
		fprintf(stderr,"%d sob's added\n", nsob);
		fprintf(stderr,"%d redundant tst's\n", nrtst);
		fprintf(stderr,"%d jump on bit\n", nbj);
		fprintf(stderr,"%d field operations\n", nfield);
		fprintf(stderr,"%dK core\n", ncore);
	}
	putc('\n',stdout);
	fflush(stdout); exit(0);
}

input()
{
	register struct node *p, *lastp;
	struct optab *opp; register char *cp1;
	static struct optab F77JSW = {".long", T(JSW,1)};

	lastp = &first;
	for (;;) {
	  top:
		opp = getline();
		if (debug && opp==0) fprintf(stderr,"? %s\n",line);
		switch (opp->opcode&0377) {
	
		case LABEL:
			p = alloc(sizeof first);
			if (isdigit(line[0]) && (p->labno=locdef(line)) ||
			  (line[0] == 'L') && (p->labno=getnum(line+1))) {
				p->combop = LABEL;
				if (p->labno<100000L && isn<=p->labno) isn=1+p->labno;
				p->code = 0;
			} else {
				p->combop = DLABEL;
				p->labno = 0;
				p->code = copy(line);
			}
			break;
	
		case LGEN:
			if (*curlp!='L' && !locuse(curlp)) goto std;
			opp= &F77JSW;
		case JBR:
			if (opp->opcode==T(JBR,RET) || opp->opcode==T(JBR,RSB)) goto std;
		case CBR:
		case JMP:
		case JSW:
		case SOBGEQ: case SOBGTR: case AOBLEQ: case AOBLSS: case ACB:
			p = alloc(sizeof first);
			p->combop = opp->opcode; p->code=0; cp1=curlp;
			if ((!isdigit(*cp1) || 0==(p->labno=locuse(cp1))) &&
			  (*cp1!='L' || 0==(p->labno = getnum(cp1+1)))) {/* jbs, etc.? */
				while (*cp1++); while (*--cp1!=',' && cp1!=curlp);
				if (cp1==curlp ||
				  (!isdigit(*++cp1) || 0==(p->labno=locuse(cp1))) &&
				  (*cp1!='L' || 0==(p->labno=getnum(cp1+1))))
					p->labno = 0;
				else *--cp1=0;
				p->code = copy(curlp);
			}
			if (isn<=p->labno) isn=1+p->labno;
			break;

		case MOVA:
			p=alloc(sizeof first);
			p->combop=opp->opcode; p->code=0; cp1=curlp+1;
			if (cp1[-1]=='L' || isdigit(cp1[-1])) {
				while (*cp1++!=','); *--cp1=0;
				if (0!=(p->labno=locuse(curlp)) ||
					0!=(p->labno=getnum(curlp+1))) p->code=copy(cp1+1);
				else {*cp1=','; p->code=copy(curlp);}
			} else {p->code=copy(--cp1); p->labno=0;}
			break;

		case SET:
		case COMM:
		case LCOMM:
			printf("%s\n",line); goto top;

		case BSS:
		case DATA:
			for (;;) {
				printf("%s%c",line,(opp->opcode==LABEL ? ':' : '\n'));
				if (opp->opcode==TEXT) goto top;
				if (END==(opp=getline())->opcode) {/* dangling .data is bad for you */
					printf(".text\n");
					break;
				}
			}

		std:
		default:
			p = alloc(sizeof first);
			p->combop = opp->opcode;
			p->labno = 0;
			p->code = copy(curlp);
			break;

		}
		p->forw = 0;
		p->back = lastp;
		p->pop = opp;
		lastp->forw = p;
		lastp = p;
		p->ref = 0;
		if (p->op==CASE) {
			char *lp; int ncase;
			lp=curlp; while (*lp++); while (*--lp!='$'); ncase=getnum(lp+1);
			if (LABEL!=(getline())->opcode) {
				fprintf(stderr, "c2: garbled 'case' instruction\n");
				exit(-2);
			}
			do {
				if (WGEN!=(getline())->opcode) {
					fprintf(stderr, "c2: garbled 'case' instruction\n");
					exit(-3);
				}
				p = alloc(sizeof first); p->combop = JSW; p->code = 0;
				lp=curlp; while(*lp++!='-'); *--lp=0; p->labno=getnum(curlp+1);
				if (isn<=p->labno) isn=1+p->labno;
				p->forw = 0; p->back = lastp; lastp->forw = p; lastp = p;
				p->ref = 0; p->pop=0;
			} while (--ncase>=0);
		}
		if (opp->opcode==EROU)
			return(1);
		if (opp->opcode==END)
			return(0);
	}
}

struct optab *
getline()
{
	register char *lp;
	register c;
	static struct optab OPLABEL={"",LABEL};
	static struct optab OPEND={"",END};

	lp = line;
	while (EOF!=(c=getchar()) && isspace(c));
	while (EOF!=c) {
		if (c==':') {
			*lp++ = 0;
			return(&OPLABEL);
		}
		if (c=='\n') {
			*lp++ = 0;
			return(oplook());
		}
		*lp++ = c;
		c = getchar();
	}
	*lp++ = 0;
	return(&OPEND);
}

long
getnum(p)
register char *p;
{
	register c; int neg; register long n;

	n = 0; neg=0; if (*p=='-') {++neg; ++p;}
	while (isdigit(c = *p++)) {
		 c -= '0'; n *= 10; if (neg) n -= c; else n += c;
	}
	if (*--p != 0)
		return(0);
	return(n);
}

locuse(p)
register char *p;
{
	if (!isdigit(p[0]) || p[1] != 'f' && p[1] != 'b' || p[2]) return(0);
	return (lgensym[p[0] - '0'] - (p[1] == 'b'));
}

locdef(p)
register char *p;
{

	if (!isdigit(p[0]) || p[1]) return(0);
	return (lgensym[p[0] - '0']++);
}

output()
{
	register struct node *t;
	int casebas;

	t = &first;
	while (t = t->forw) switch (t->op) {

	case END:
		fflush(stdout);
		return;

	case LABEL:
		printf("L%d:", t->labno);
		continue;

	case DLABEL:
		printf("%s:", t->code);
		continue;

	case CASE:
		casebas=0;

	default: std:
		if (t->pop==0) {/* must find it */
			register struct optab *p;
			for (p=optab; p->opstring[0]; ++p)
				if (p->opcode==t->combop) {t->pop=p; break;}
		}
		printf("%s", t->pop->opstring);
		if (t->code) printf("\t%s", t->code);
		if (t->labno!=0) printf("%cL%d\n",
							(t->code ? ',' : '\t'),
							t->labno);
		else printf("\n");
		continue;

	case MOVA:
		if (t->labno==0) goto std;
		printf("mova%c\tL%d,%s\n","bwlq"[t->subop-BYTE],t->labno,t->code);
		continue;

	case JSW:
		if (t->subop!=0) {/* F77JSW */
			printf(".long\tL%d\n",t->labno); continue;
		}
		if (casebas==0) printf("L%d:\n",casebas=isn++);
		printf(".word	L%d-L%d\n", t->labno, casebas);
		continue;
	case MOV:
		if (!fflag) goto std;
		if (t->forw) if(t->forw->op == CBR) goto std;
		if (*t->code == '$') goto std;
		if (t->subop == FFLOAT)
			{
			printf("movl\t%s\n", t->code);
			continue;
			}
		if (t->subop == DFLOAT || t->subop == GFLOAT)
			{
			printf("movq\t%s\n", t->code);
			continue;
			}
		if (t->subop == HFLOAT)
			{
			printf("movo\t%s\n", t->code);
			continue;
			}
		goto std;

	}
}

char *
copy(ap)
char *ap;
{
	register char *p = ap, *np;
	char *onp;
	register n;

	if (*p++ == 0)
		return(0);
	n = 1;
	do
		n++;
	while (*p++);
	onp = np = (char *) alloc(n);
	p = ap;
	while (*np++ = *p++);
	return (onp);
}

#define	OPHS	560
struct optab *ophash[OPHS];

opsetup()
{
	register struct optab *optp, **ophp;
	register int i,t;

	for(i=NREG+5;--i>=0;) regs[i] = malloc(C2_ASIZE);
	for (optp = optab; optp->opstring[0]; optp++) {
		t=7; i=0; while (--t>=0) i+= i+optp->opstring[t];
		ophp = &ophash[i % OPHS];
		while (*ophp++) {
/*			fprintf(stderr,"\ncollision: %d %s %s",
/*				ophp-1-ophash,optp->opstring,(*(ophp-1))->opstring);
*/
			if (ophp >= &ophash[OPHS])
				ophp = ophash;
		}
		*--ophp = optp;
	}
}

struct optab *
oplook()
{
	register struct optab *optp,**ophp;
	register char *p,*p2;
	register int t;
	char tempop[20];
	static struct optab OPNULL={"",0};

	for (p=line, p2=tempop; *p && !isspace(*p); *p2++= *p++); *p2=0; p2=p;
	while (isspace(*p2)) ++p2; curlp=p2;
	t=0; while(--p>=line) t += t+*p; ophp = &ophash[t % OPHS];
	while (optp = *ophp) {
		if (equstr(tempop,optp->opstring)) return(optp);
		if ((++ophp) >= &ophash[OPHS]) ophp = ophash;
	}
	curlp = line;
	return(&OPNULL);
}

refcount()
{
	register struct node *p, *lp, *tp;
	struct node *labhash[LABHS];
	register struct node **hp;

	for (hp = labhash; hp < &labhash[LABHS];)
		*hp++ = 0;
	for (p = first.forw; p!=0; p = p->forw)
		if (p->op==LABEL) {
			labhash[p->labno % LABHS] = p;
			p->refc = 0;
		}
	for (p = first.forw; p!=0; p = p->forw) {
		if (p->combop==JBR || p->op==CBR || p->op==JSW || p->op==JMP
		  || p->op==SOBGEQ || p->op==SOBGTR || p->op==AOBLEQ || p->op==AOBLSS
		  || p->op==ACB || (p->op==MOVA && p->labno!=0)) {
			p->ref = 0;
			lp = labhash[p->labno % LABHS];
			if (lp==0 || p->labno!=lp->labno)
			for (lp = first.forw; lp!=0; lp = lp->forw) {
				if (lp->op==LABEL && p->labno==lp->labno)
					break;
			}
			if (lp) {
				tp = nonlab(lp)->back;
				if (tp!=lp) {
					p->labno = tp->labno;
					lp = tp;
				}
				p->ref = lp;
				lp->refc++;
			}
		}
	}
	for (p = first.forw; p!=0; p = p->forw)
		if (p->op==LABEL && p->refc==0
		 && (lp = nonlab(p))->op && lp->op!=JSW)
			decref(p);
}

iterate()
{
	register struct node *p, *rp, *p1;

	nchange = 0;
	for (p = first.forw; p!=0; p = p->forw) {
		if ((p->op==JBR||p->op==CBR||p->op==JSW) && p->ref) {
			rp = nonlab(p->ref);
			if (rp->op==JBR && rp->labno && p->labno!=rp->labno) {
				nbrbr++;
				p->labno = rp->labno;
				decref(p->ref);
				rp->ref->refc++;
				p->ref = rp->ref;
				nchange++;
			}
		}
#ifndef COPYCODE
		if (p->op==CBR && (p1 = p->forw)->combop==JBR) {/* combop: RET problems */
#else
		if (p->op==CBR && (p1 = p->forw)->combop==JBR &&
		    p->ref) {/* combop: RET problems */
#endif
			rp = p->ref;
			do
				rp = rp->back;
			while (rp->op==LABEL);
			if (rp==p1) {
				decref(p->ref);
				p->ref = p1->ref;
				p->labno = p1->labno;
#ifdef COPYCODE
				if (p->labno == 0)
					p->code = p1->code;
#endif
				p1->forw->back = p;
				p->forw = p1->forw;
				p->subop = revbr[p->subop];
				p->pop=0;
				nchange++;
				nskip++;
			}
		}
		if (p->op==JBR || p->op==JMP) {
			while (p->forw && p->forw->op!=LABEL && p->forw->op!=DLABEL
				&& p->forw->op!=EROU && p->forw->op!=END
				&& p->forw->op!=ALIGN
				&& p->forw->op!=0 && p->forw->op!=DATA) {
				nchange++;
				iaftbr++;
				if (p->forw->ref)
					decref(p->forw->ref);
				p->forw = p->forw->forw;
				p->forw->back = p;
			}
			rp = p->forw;
			while (rp && rp->op==LABEL) {
				if (p->ref == rp) {
					p->back->forw = p->forw;
					p->forw->back = p->back;
					p = p->back;
					decref(rp);
					nchange++;
					njp1++;
					break;
				}
				rp = rp->forw;
			}
			xjump(p);
			p = codemove(p);
		}
	}
}

xjump(p1)
register struct node *p1;
{
	register struct node *p2, *p3;

	if ((p2 = p1->ref)==0)
		return;
	for (;;) {
		while ((p1 = p1->back) && p1->op==LABEL);
		while ((p2 = p2->back) && p2->op==LABEL);
		if (!equop(p1, p2) || p1==p2)
			return;
		p3 = insertl(p2);
		p1->combop = JBR;
		p1->pop=0;
		p1->ref = p3;
		p1->labno = p3->labno;
		p1->code = 0;
		nxjump++;
		nchange++;
	}
}

struct node *
insertl(np)
register struct node *np;
{
	register struct node *lp;

	if (np->op == LABEL) {
		np->refc++;
		return(np);
	}
	if (np->back->op == LABEL) {
		np = np->back;
		np->refc++;
		return(np);
	}
	lp = alloc(sizeof first);
	lp->combop = LABEL;
	lp->labno = isn++;
	lp->ref = 0;
	lp->code = 0;
	lp->refc = 1;
	lp->back = np->back;
	lp->forw = np;
	np->back->forw = lp;
	np->back = lp;
	return(lp);
}

struct node *
codemove(ap)
struct node *ap;
{
	register struct node *p1, *p2, *p3;
	struct node *t, *tl;
	int n;

	p1 = ap;
/* last clause to avoid infinite loop on partial compiler droppings:
	L183:	jbr L179
	L191:	jbr L179
			casel r0,$0,$1
	L193:	.word L183-L193
			.word L191-L193
	L179:	ret
*/
	if (p1->op!=JBR || (p2 = p1->ref)==0 || p2==p1->forw)
		return(p1);
	while (p2->op == LABEL)
		if ((p2 = p2->back) == 0)
			return(p1);
	if (p2->op!=JBR && p2->op!=JMP)
		goto ivloop;
	p2 = p2->forw;
	p3 = p1->ref;
	while (p3) {
		if (p3->op==JBR || p3->op==JMP) {
			if (p1==p3)
				return(p1);
			ncmot++;
			nchange++;
			p1->back->forw = p2;
			p1->forw->back = p3;
			p2->back->forw = p3->forw;
			p3->forw->back = p2->back;
			p2->back = p1->back;
			p3->forw = p1->forw;
			decref(p1->ref);
			return(p2);
		} else
			p3 = p3->forw;
	}
	return(p1);
ivloop:
	if (p1->forw->op!=LABEL)
		return(p1);
	p3 = p2 = p2->forw;
	n = 16;
	do {
		if ((p3 = p3->forw) == 0 || p3==p1 || --n==0)
			return(p1);
	} while (p3->op!=CBR || p3->labno!=p1->forw->labno);
	do 
		if ((p1 = p1->back) == 0)
			return(ap);
	while (p1!=p3);
	p1 = ap;
	tl = insertl(p1);
	p3->subop = revbr[p3->subop];
	p3->pop=0;
	decref(p3->ref);
	p2->back->forw = p1;
	p3->forw->back = p1;
	p1->back->forw = p2;
	p1->forw->back = p3;
	t = p1->back;
	p1->back = p2->back;
	p2->back = t;
	t = p1->forw;
	p1->forw = p3->forw;
	p3->forw = t;
	p2 = insertl(p1->forw);
	p3->labno = p2->labno;
#ifdef COPYCODE
	if (p3->labno == 0)
		p3->code = p2->code;
#endif
	p3->ref = p2;
	decref(tl);
	if (tl->refc<=0)
		nrlab--;
	loopiv++;
	nchange++;
	return(p3);
}

comjump()
{
	register struct node *p1, *p2, *p3;

	for (p1 = first.forw; p1!=0; p1 = p1->forw)
		if (p1->op==JBR && ((p2 = p1->ref) && p2->refc > 1
				|| p1->subop==RET || p1->subop==RSB))
			for (p3 = p1->forw; p3!=0; p3 = p3->forw)
				if (p3->op==JBR && p3->ref == p2)
					backjmp(p1, p3);
}

backjmp(ap1, ap2)
struct node *ap1, *ap2;
{
	register struct node *p1, *p2, *p3;

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