/*  * This file is part of the UCB release of Plan 9. It is subject to the license * terms in the LICENSE file found in the top-level directory of this * distribution and at http://akaros.cs.berkeley.edu/files/Plan9License. No * part of the UCB release of Plan 9, including this file, may be copied, * modified, propagated, or distributed except according to the terms contained * in the LICENSE file. */ #include "gc.h" Reg*rega(void){	Reg *r; 	r = freer;	if(r == R) {		r = alloc(sizeof(*r));	} else		freer = r->link; 	*r = zreg;	return r;} intrcmp(const void *a1, const void *a2){	Rgn *p1, *p2;	int c1, c2; 	p1 = (Rgn*)a1;	p2 = (Rgn*)a2;	c1 = p2->cost;	c2 = p1->cost;	if(c1 -= c2)		return c1;	return p2->varno - p1->varno;} voidregopt(Prog *p){	Reg *r, *r1, *r2;	Prog *p1;	int i, z;	long initpc, val, npc;	ulong vreg;	Bits bit;	struct	{		long	m;		long	c;		Reg*	p;	} log5[6], *lp; 	firstr = R;	lastr = R;	nvar = 0;	regbits = RtoB(D_SP) | RtoB(D_AX);	for(z=0; z<BITS; z++) {		externs.b[z] = 0;		params.b[z] = 0;		consts.b[z] = 0;		addrs.b[z] = 0;	} 	/*	 * pass 1	 * build aux data structure	 * allocate pcs	 * find use and set of variables	 */	val = 5L * 5L * 5L * 5L * 5L;	lp = log5;	for(i=0; i<5; i++) {		lp->m = val;		lp->c = 0;		lp->p = R;		val /= 5L;		lp++;	}	val = 0;	for(; p != P; p = p->link) {		switch(p->as) {		case ADATA:		case AGLOBL:		case ANAME:		case ASIGNAME:			continue;		}		r = rega();		if(firstr == R) {			firstr = r;			lastr = r;		} else {			lastr->link = r;			r->p1 = lastr;			lastr->s1 = r;			lastr = r;		}		r->prog = p;		r->pc = val;		val++; 		lp = log5;		for(i=0; i<5; i++) {			lp->c--;			if(lp->c <= 0) {				lp->c = lp->m;				if(lp->p != R)					lp->p->log5 = r;				lp->p = r;				(lp+1)->c = 0;				break;			}			lp++;		} 		r1 = r->p1;		if(r1 != R)		switch(r1->prog->as) {		case ARET:		case AJMP:		case AIRETL:			r->p1 = R;			r1->s1 = R;		} 		bit = mkvar(r, &p->from, p->as==AMOVL);		if(bany(&bit))		switch(p->as) {		/*		 * funny		 */		case ALEAL:			for(z=0; z<BITS; z++)				addrs.b[z] |= bit.b[z];			break; 		/*		 * left side read		 */		default:			for(z=0; z<BITS; z++)				r->use1.b[z] |= bit.b[z];			break;		} 		bit = mkvar(r, &p->to, 0);		if(bany(&bit))		switch(p->as) {		default:			diag(Z, "reg: unknown op: %A", p->as);			break; 		/*		 * right side read		 */		case ACMPB:		case ACMPL:		case ACMPW:			for(z=0; z<BITS; z++)				r->use2.b[z] |= bit.b[z];			break; 		/*		 * right side write		 */		case ANOP:		case AMOVL:		case AMOVB:		case AMOVW:		case AMOVBLSX:		case AMOVBLZX:		case AMOVWLSX:		case AMOVWLZX:			for(z=0; z<BITS; z++)				r->set.b[z] |= bit.b[z];			break; 		/*		 * right side read+write		 */		case AADDB:		case AADDL:		case AADDW:		case AANDB:		case AANDL:		case AANDW:		case ASUBB:		case ASUBL:		case ASUBW:		case AORB:		case AORL:		case AORW:		case AXORB:		case AXORL:		case AXORW:		case ASALB:		case ASALL:		case ASALW:		case ASARB:		case ASARL:		case ASARW:		case AROLB:		case AROLL:		case AROLW:		case ARORB:		case ARORL:		case ARORW:		case ASHLB:		case ASHLL:		case ASHLW:		case ASHRB:		case ASHRL:		case ASHRW:		case AIMULL:		case AIMULW:		case ANEGL:		case ANOTL:		case AADCL:		case ASBBL:			for(z=0; z<BITS; z++) {				r->set.b[z] |= bit.b[z];				r->use2.b[z] |= bit.b[z];			}			break; 		/*		 * funny		 */		case AFMOVDP:		case AFMOVFP:		case AFMOVLP:		case AFMOVVP:		case AFMOVWP:		case ACALL:			for(z=0; z<BITS; z++)				addrs.b[z] |= bit.b[z];			break;		} 		switch(p->as) {		case AIMULL:		case AIMULW:			if(p->to.type != D_NONE)				break; 		case AIDIVB:		case AIDIVL:		case AIDIVW:		case AIMULB:		case ADIVB:		case ADIVL:		case ADIVW:		case AMULB:		case AMULL:		case AMULW: 		case ACWD:		case ACDQ:			r->regu |= RtoB(D_AX) | RtoB(D_DX);			break; 		case AREP:		case AREPN:		case ALOOP:		case ALOOPEQ:		case ALOOPNE:			r->regu |= RtoB(D_CX);			break; 		case AMOVSB:		case AMOVSL:		case AMOVSW:		case ACMPSB:		case ACMPSL:		case ACMPSW:			r->regu |= RtoB(D_SI) | RtoB(D_DI);			break; 		case ASTOSB:		case ASTOSL:		case ASTOSW:		case ASCASB:		case ASCASL:		case ASCASW:			r->regu |= RtoB(D_AX) | RtoB(D_DI);			break; 		case AINSB:		case AINSL:		case AINSW:		case AOUTSB:		case AOUTSL:		case AOUTSW:			r->regu |= RtoB(D_DI) | RtoB(D_DX);			break; 		case AFSTSW:		case ASAHF:			r->regu |= RtoB(D_AX);			break;		}	}	if(firstr == R)		return;	initpc = pc - val;	npc = val; 	/*	 * pass 2	 * turn branch references to pointers	 * build back pointers	 */	for(r = firstr; r != R; r = r->link) {		p = r->prog;		if(p->to.type == D_BRANCH) {			val = p->to.offset - initpc;			r1 = firstr;			while(r1 != R) {				r2 = r1->log5;				if(r2 != R && val >= r2->pc) {					r1 = r2;					continue;				}				if(r1->pc == val)					break;				r1 = r1->link;			}			if(r1 == R) {				nearln = p->lineno;				diag(Z, "ref not found\n%P", p);				continue;			}			if(r1 == r) {				nearln = p->lineno;				diag(Z, "ref to self\n%P", p);				continue;			}			r->s2 = r1;			r->p2link = r1->p2;			r1->p2 = r;		}	}	if(debug['R']) {		p = firstr->prog;		print("\n%L %D\n", p->lineno, &p->from);	} 	/*	 * pass 2.5	 * find looping structure	 */	for(r = firstr; r != R; r = r->link)		r->active = 0;	change = 0;	loopit(firstr, npc);	if(debug['R'] && debug['v']) {		print("\nlooping structure:\n");		for(r = firstr; r != R; r = r->link) {			print("%ld:%P", r->loop, r->prog);			for(z=0; z<BITS; z++)				bit.b[z] = r->use1.b[z] |					   r->use2.b[z] |					   r->set.b[z];			if(bany(&bit)) {				print("\t");				if(bany(&r->use1))					print(" u1=%B", r->use1);				if(bany(&r->use2))					print(" u2=%B", r->use2);				if(bany(&r->set))					print(" st=%B", r->set);			}			print("\n");		}	} 	/*	 * pass 3	 * iterate propagating usage	 * 	back until flow graph is complete	 */loop1:	change = 0;	for(r = firstr; r != R; r = r->link)		r->active = 0;	for(r = firstr; r != R; r = r->link)		if(r->prog->as == ARET)			prop(r, zbits, zbits);loop11:	/* pick up unreachable code */	i = 0;	for(r = firstr; r != R; r = r1) {		r1 = r->link;		if(r1 && r1->active && !r->active) {			prop(r, zbits, zbits);			i = 1;		}	}	if(i)		goto loop11;	if(change)		goto loop1;  	/*	 * pass 4	 * iterate propagating register/variable synchrony	 * 	forward until graph is complete	 */loop2:	change = 0;	for(r = firstr; r != R; r = r->link)		r->active = 0;	synch(firstr, zbits);	if(change)		goto loop2;  	/*	 * pass 5	 * isolate regions	 * calculate costs (paint1)	 */	r = firstr;	if(r) {		for(z=0; z<BITS; z++)			bit.b[z] = (r->refahead.b[z] | r->calahead.b[z]) &			  ~(externs.b[z] | params.b[z] | addrs.b[z] | consts.b[z]);		if(bany(&bit)) {			nearln = r->prog->lineno;			warn(Z, "used and not set: %B", bit);			if(debug['R'] && !debug['w'])				print("used and not set: %B\n", bit);		}	}	if(debug['R'] && debug['v'])		print("\nprop structure:\n");	for(r = firstr; r != R; r = r->link)		r->act = zbits;	rgp = region;	nregion = 0;	for(r = firstr; r != R; r = r->link) {		if(debug['R'] && debug['v']) {			print("%P\t", r->prog);			if(bany(&r->set))				print("s:%B ", r->set);			if(bany(&r->refahead))				print("ra:%B ", r->refahead);			if(bany(&r->calahead))				print("ca:%B ", r->calahead);			print("\n");		}		for(z=0; z<BITS; z++)			bit.b[z] = r->set.b[z] &			  ~(r->refahead.b[z] | r->calahead.b[z] | addrs.b[z]);		if(bany(&bit)) {			nearln = r->prog->lineno;			warn(Z, "set and not used: %B", bit);			if(debug['R'])				print("set and not used: %B\n", bit);			excise(r);		}		for(z=0; z<BITS; z++)			bit.b[z] = LOAD(r) & ~(r->act.b[z] | addrs.b[z]);		while(bany(&bit)) {			i = bnum(bit);			rgp->enter = r;			rgp->varno = i;			change = 0;			if(debug['R'] && debug['v'])				print("\n");			paint1(r, i);			bit.b[i/32] &= ~(1L<<(i%32));			if(change <= 0) {				if(debug['R'])					print("%L$%d: %B\n",						r->prog->lineno, change, blsh(i));				continue;			}			rgp->cost = change;			nregion++;			if(nregion >= NRGN) {				warn(Z, "too many regions");				goto brk;			}			rgp++;		}	}brk:	qsort(region, nregion, sizeof(region[0]), rcmp); 	/*	 * pass 6	 * determine used registers (paint2)	 * replace code (paint3)

Lines 1–500 of 1273. Load more