#include "gc.h" int	emptyloop(Reg*, Reg*, Reg*);/* * bra is a conditional branch which may be the start of a loop * try to change the loop into a do loop */voidoptloop(Reg *bra){	Reg *entry, *cmp, *inc, *e, *tail, *loop;	Prog *p;	Adr *v, *t, a, b;	int off, cc; 	e = bra->s2;	if(!e || e->loop >= bra->loop)		return; 	if(!onlybra(bra))		return;	entry = findentry(bra);	cmp = findcmp(bra);	if(!entry || !cmp)		return;	v = &cmp->prog->from;	t = &cmp->prog->to;	inc = indvarinc(bra, cmp, v);	if(!inc || !loopinvar(bra, t))		return;	if(!notusedbra(bra, v))		return;	off = inc->prog->from.offset;	if(off != -1 && off != 1)		return;	cc = bra->prog->cc;	switch(cc){	case CCEQ:		break;	case CCLT:	case CCLE:		if(off > 0)			return;		break;	case CCGT:		if(off < 1)			return;		cc = CCLT;		break;	case CCGE:		if(off < 1)			return;		cc = CCLE;		break;	default:		return;	}	if(!isfor(entry, cmp, t) || blocklen(bra->s1) > MAXLOOP || emptyloop(bra, inc, cmp))		return;	if(debug['P'])		print("found inner loop: entry %P cmp %P inc %P exit %P\n",			entry->prog, cmp->prog, inc->prog, bra->prog); 	/*	 * have	 *	top	 * entry:	 *	...	 * 	CMP	v, t	 *	BRA	CC,e	 * want	 *	top	 * doend:	 *	DOEND	,do		DOEND	,do	 *	ADD	$-2048, v	MOVW	$3, REGTMP	 *	BRA	GE, do		DBRA	v, do	 *	JMP	e		JMP	e	 * entry:	 *	...	 *	SUB	t, v	or SUBR t, v	if incrementing	 *	BRA	CC, e	or BRA	CC', e	if incrementing	 *	ADD	$-1, v	or nothing	if CC == CCLT	 *				MOVW	v, REGTMP	 *				AND	$3, REGTMP	 *				SRA	$2, v	 *				ADD	$-1, v	 * do:	 *	DO	v,doend		DO	R2,doend	 */	excise(inc);	tail = entry->p1;	adddo(ADOLOCK, bra, tail);	loop = bra->s1;	tail = tail->s1;	mkreg(&b, REGTMP);	loop->prog->from = b;	tail = addinst(tail, AMOVW, mkconst(&a, 3), NREG, &b);	tail = adddbra(tail, v, loop);	addjmp(tail, AJMP, 0, e); 	bra->loop -= LOOP;	bra->prog->cc = cc;	if(cc != CCLT)		bra = addinst(bra, AADD, mkconst(&a, -1), v->reg, v);	bra = addinst(bra, AMOVW, v, NREG, mkreg(&b, REGTMP));	bra = addinst(bra, AAND, mkconst(&a, 3), NREG, &b);	bra = addinst(bra, ASRA, mkconst(&a, 2), NREG, v);	addinst(bra, AADD, mkconst(&a, -1), v->reg, v);	if(regzer(t))		return;	p = cmp->prog;	a = *t;	p->to = *v;	p->from = a;	p->as = ASUB;	if(off > 0)		p->as = ASUBR;} intonlybra(Reg *r0){	Reg *r; 	for(r = r0->s1; r; r = uniqs(r)){		switch(r->prog->as){		case ACALL:		case ARETURN:		case AMUL:		case ADIV:		case ADIVL:		case AMOD:		case AMODL:		case AFDIV:			return 0;		}		if(r == r0)			return 1;	}	return 0;} /* * r0 is the only exit from the loop * find the only entry */Reg *findentry(Reg *r0){	Reg *entry, *r; 	entry = 0;	for(r = r0->s1; r; r = uniqs(r)){		if(!uniqp(r)){			if(entry)				return 0;			entry = r;		}		if(r == r0)			return entry;	}	return 0;} /* * r is a branch * find the comparison to go along with it */Reg *findcmp(Reg *r){	for(r = uniqp(r); r; r = uniqp(r)){		if(!uniqs(r))			return 0;		if(r->prog->as == ACMP)			return r;		if(r->prog->as != ANOP)			return 0;	}	return 0;} /* * is the loop empty? */intemptyloop(Reg *r0, Reg *inc, Reg *cmp){	Reg *r; 	for(r = r0->s1; r && r != r0; r = uniqs(r)){		if(r == inc || r == cmp)			continue;		if(r->prog->as != ANOP && r->prog->as != AJMP){			return 0;		}	}	return 1;} /* * is the loop a for loop? */intisfor(Reg *entry, Reg *cmp, Adr *v){	Reg *r;	Prog *p;	int cmped; 	r = entry->p1;	if(!r || r->loop != entry->loop || r->s2)		return 0;	r = entry->p2;	if(entry->s2 || !r || r->prog->as != AJMP || r->p2link)		return 0;	cmped = 0;	for(r = entry; r; r = uniqs(r)){		p = r->prog;		switch(p->as){		case ABRA:			return cmped;		case ACMP:			if(r != cmp)				return 0;			cmped = 1;			break;		case ANOP:			break;		case AMOVW:			if(p->to.type != D_REG || p->to.reg != v->reg)				return 0;			break;		default:			return 0;		}	}	return 0;} /* * return the increment if a is a simple induction variable * for the loop with exit r */Reg *indvarinc(Reg *r, Reg *cmp, Adr *a){	Reg *inc;	Prog *p;	int u; 	if(a->type != D_REG)		return 0;	inc = 0;	for(r = r->s1; r; r = uniqs(r)){		p = r->prog;		u = copyu(p, a, 0, 0);		switch(u){		case 0:			break;		case 1:			if(r != cmp || !inc)				return 0;			break;		case 2:		case 3:			return 0;		case 4:			if(inc || p->as != AADD || !contyp(&p->from))				return 0;			inc = r;			break;		}	}	return inc;} /* * does v have the same value for every iteration of the loop * r is the exit from the loop */intloopinvar(Reg *r, Adr *v){	int u, entered; 	if(v->type == D_CONST)		return 1;	if(v->type != D_REG)		return 0;	entered = 0;	for(r = r->s1; r; r = uniqs(r)){		if(!uniqp(r))			entered = 1;		p = r->prog;		u = copyu(p, v, 0, 0);		switch(u){		case 0:			break;		case 1:			if(p->as != ACMP && p->as != AMOVW)				return 0;			break;		case 2:		case 4:			return 0;		case 3:			if(!entered || p->as != AMOVW			|| p->from.type != D_NAME && p->from.type != D_CONST			|| !unaliased(&p->from))				return 0;			break;		}	}	return 1;}