peep.c

这是一个同样来自贝尔实验室的和UNIX有着渊源的操作系统, 其简洁的设计和实现易于我们学习和理解

#include "gc.h"

void
peep(void)
{
	Reg *r, *r1, *r2;
	Prog *p, *p1;
	int t;
/*
 * complete R structure
 */
	t = 0;
	for(r=firstr; r!=R; r=r1) {
		r1 = r->link;
		if(r1 == R)
			break;
		p = r->prog->link;
		while(p != r1->prog)
		switch(p->as) {
		default:
			r2 = rega();
			r->link = r2;
			r2->link = r1;

			r2->prog = p;
			r2->p1 = r;
			r->s1 = r2;
			r2->s1 = r1;
			r1->p1 = r2;

			r = r2;
			t++;

		case ADATA:
		case AGLOBL:
		case ANAME:
		case ASIGNAME:
			p = p->link;
		}
	}

loop1:
	t = 0;
	for(r=firstr; r!=R; r=r->link) {
		p = r->prog;
		if(p->as == AMOVW || p->as == AFMOVS || p->as == AFMOVD)
		if(regtyp(&p->to)) {
			if(regtyp(&p->from))
			if(p->from.type == p->to.type) {
				if(copyprop(r)) {
					excise(r);
					t++;
				} else
				if(subprop(r) && copyprop(r)) {
					excise(r);
					t++;
				}
			}
			if(regzer(&p->from))
			if(p->to.type == D_REG) {
				p->from.type = D_REG;
				p->from.reg = REGZERO;
				if(copyprop(r)) {
					excise(r);
					t++;
				} else
				if(subprop(r) && copyprop(r)) {
					excise(r);
					t++;
				}
			}
		}
	}
	if(t)
		goto loop1;
	/*
	 * look for MOVB x,R; MOVB R,R
	 */
	for(r=firstr; r!=R; r=r->link) {
		p = r->prog;
		switch(p->as) {
		default:
			continue;
		case AMOVH:
		case AMOVHZ:
		case AMOVB:
		case AMOVBZ:
			if(p->to.type != D_REG)
				continue;
			break;
		}
		r1 = r->link;
		if(r1 == R)
			continue;
		p1 = r1->prog;
		if(p1->as != p->as)
			continue;
		if(p1->from.type != D_REG || p1->from.reg != p->to.reg)
			continue;
		if(p1->to.type != D_REG || p1->to.reg != p->to.reg)
			continue;
		excise(r1);
	}

	if(debug['Q'] > 1)
		return;	/* allow following code improvement to be suppressed */

	/*
	 * look for OP x,y,R; CMP R, $0 -> OPCC x,y,R
	 * when OP can set condition codes correctly
	 */
	for(r=firstr; r!=R; r=r->link) {
		p = r->prog;
		switch(p->as) {
		case ACMP:
			if(!regzer(&p->to))
				continue;
			r1 = r->s1;
			if(r1 == R)
				continue;
			switch(r1->prog->as) {
			default:
				continue;
			case ABCL:
			case ABC:
				/* the conditions can be complex and these are currently little used */
				continue;
			case ABEQ:
			case ABGE:
			case ABGT:
			case ABLE:
			case ABLT:
			case ABNE:
			case ABVC:
			case ABVS:
				break;
			}
			r1 = r;
			do
				r1 = uniqp(r1);
			while (r1 != R && r1->prog->as == ANOP);
			if(r1 == R)
				continue;
			p1 = r1->prog;
			if(p1->to.type != D_REG || p1->to.reg != p->from.reg)
				continue;
			switch(p1->as) {
			case ASUB:
			case AADD:
			case AXOR:
			case AOR:
				/* irregular instructions */
				if(p1->from.type == D_CONST)
					continue;
				break;
			}
			switch(p1->as) {
			default:
				continue;
			case AMOVW:
				if(p1->from.type != D_REG)
					continue;
				continue;
			case AANDCC:
			case AANDNCC:
			case AORCC:
			case AORNCC:
			case AXORCC:
			case ASUBCC:
			case AADDCC:
				t = p1->as;
				break;
			/* don't deal with floating point instructions for now */
/*
			case AFABS:	t = AFABSCC; break;
			case AFADD:	t = AFADDCC; break;
			case AFADDS:	t = AFADDSCC; break;
			case AFCTIW:	t = AFCTIWCC; break;
			case AFCTIWZ:	t = AFCTIWZCC; break;
			case AFDIV:	t = AFDIVCC; break;
			case AFDIVS:	t = AFDIVSCC; break;
			case AFMADD:	t = AFMADDCC; break;
			case AFMADDS:	t = AFMADDSCC; break;
			case AFMOVD:	t = AFMOVDCC; break;
			case AFMSUB:	t = AFMSUBCC; break;
			case AFMSUBS:	t = AFMSUBSCC; break;
			case AFMUL:	t = AFMULCC; break;
			case AFMULS:	t = AFMULSCC; break;
			case AFNABS:	t = AFNABSCC; break;
			case AFNEG:	t = AFNEGCC; break;
			case AFNMADD:	t = AFNMADDCC; break;
			case AFNMADDS:	t = AFNMADDSCC; break;
			case AFNMSUB:	t = AFNMSUBCC; break;
			case AFNMSUBS:	t = AFNMSUBSCC; break;
			case AFRSP:	t = AFRSPCC; break;
			case AFSUB:	t = AFSUBCC; break;
			case AFSUBS:	t = AFSUBSCC; break;
			case ACNTLZW:	t = ACNTLZWCC; break;
			case AMTFSB0:	t = AMTFSB0CC; break;
			case AMTFSB1:	t = AMTFSB1CC; break;
*/
			case AADD:	t = AADDCC; break;
			case AADDV:	t = AADDVCC; break;
			case AADDC:	t = AADDCCC; break;
			case AADDCV:	t = AADDCVCC; break;
			case AADDME:	t = AADDMECC; break;
			case AADDMEV:	t = AADDMEVCC; break;
			case AADDE:	t = AADDECC; break;
			case AADDEV:	t = AADDEVCC; break;
			case AADDZE:	t = AADDZECC; break;
			case AADDZEV:	t = AADDZEVCC; break;
			case AAND:	t = AANDCC; break;
			case AANDN:	t = AANDNCC; break;
			case ADIVW:	t = ADIVWCC; break;
			case ADIVWV:	t = ADIVWVCC; break;
			case ADIVWU:	t = ADIVWUCC; break;
			case ADIVWUV:	t = ADIVWUVCC; break;
			case AEQV:	t = AEQVCC; break;
			case AEXTSB:	t = AEXTSBCC; break;
			case AEXTSH:	t = AEXTSHCC; break;
			case AMULHW:	t = AMULHWCC; break;
			case AMULHWU:	t = AMULHWUCC; break;
			case AMULLW:	t = AMULLWCC; break;
			case AMULLWV:	t = AMULLWVCC; break;
			case ANAND:	t = ANANDCC; break;
			case ANEG:	t = ANEGCC; break;
			case ANEGV:	t = ANEGVCC; break;
			case ANOR:	t = ANORCC; break;
			case AOR:	t = AORCC; break;
			case AORN:	t = AORNCC; break;
			case AREM:	t = AREMCC; break;
			case AREMV:	t = AREMVCC; break;
			case AREMU:	t = AREMUCC; break;
			case AREMUV:	t = AREMUVCC; break;
			case ARLWMI:	t = ARLWMICC; break;
			case ARLWNM:	t = ARLWNMCC; break;
			case ASLW:	t = ASLWCC; break;
			case ASRAW:	t = ASRAWCC; break;
			case ASRW:	t = ASRWCC; break;
			case ASUB:	t = ASUBCC; break;
			case ASUBV:	t = ASUBVCC; break;
			case ASUBC:	t = ASUBCCC; break;
			case ASUBCV:	t = ASUBCVCC; break;
			case ASUBME:	t = ASUBMECC; break;
			case ASUBMEV:	t = ASUBMEVCC; break;
			case ASUBE:	t = ASUBECC; break;
			case ASUBEV:	t = ASUBEVCC; break;
			case ASUBZE:	t = ASUBZECC; break;
			case ASUBZEV:	t = ASUBZEVCC; break;
			case AXOR:	t = AXORCC; break;
				break;
			}
			if(debug['Q'])
				print("cmp %P; %P -> ", p1, p);
			p1->as = t;
			if(debug['Q'])
				print("%P\n", p1);
			excise(r);
			continue;
		}
	}
}

void
excise(Reg *r)
{
	Prog *p;

	p = r->prog;
	p->as = ANOP;
	p->from = zprog.from;
	p->to = zprog.to;
	p->reg = zprog.reg; /**/
}

Reg*
uniqp(Reg *r)
{
	Reg *r1;

	r1 = r->p1;
	if(r1 == R) {
		r1 = r->p2;
		if(r1 == R || r1->p2link != R)
			return R;
	} else
		if(r->p2 != R)
			return R;
	return r1;
}

Reg*
uniqs(Reg *r)
{
	Reg *r1;

	r1 = r->s1;
	if(r1 == R) {
		r1 = r->s2;
		if(r1 == R)
			return R;
	} else
		if(r->s2 != R)
			return R;
	return r1;
}

/*
 * if the system forces R0 to be zero,
 * convert references to $0 to references to R0.
 */
regzer(Adr *a)
{
	if(R0ISZERO) {
		if(a->type == D_CONST)
			if(a->sym == S)
				if(a->offset == 0)
					return 1;
		if(a->type == D_REG)
			if(a->reg == REGZERO)
				return 1;
	}
	return 0;
}

regtyp(Adr *a)
{

	if(a->type == D_REG) {
		if(!R0ISZERO || a->reg != REGZERO)
			return 1;
		return 0;
	}
	if(a->type == D_FREG)
		return 1;
	return 0;
}

/*
 * the idea is to substitute
 * one register for another
 * from one MOV to another
 *	MOV	a, R0
 *	ADD	b, R0	/ no use of R1
 *	MOV	R0, R1
 * would be converted to
 *	MOV	a, R1
 *	ADD	b, R1
 *	MOV	R1, R0
 * hopefully, then the former or latter MOV
 * will be eliminated by copy propagation.
 */
int
subprop(Reg *r0)
{
	Prog *p;
	Adr *v1, *v2;
	Reg *r;
	int t;

	p = r0->prog;
	v1 = &p->from;
	if(!regtyp(v1))
		return 0;
	v2 = &p->to;
	if(!regtyp(v2))
		return 0;
	for(r=uniqp(r0); r!=R; r=uniqp(r)) {
		if(uniqs(r) == R)
			break;
		p = r->prog;
		switch(p->as) {
		case ABL:
			return 0;

		case AADD:
		case ASUB:
		case ASLW:
		case ASRW:
		case ASRAW:
		case AOR:
		case AORCC:
		case AORN:
		case AORNCC:
		case AAND:
		case AANDCC:
		case AANDN:
		case AANDNCC:
		case ANAND:
		case ANANDCC:
		case ANOR:
		case ANORCC:
		case AXOR:
		case AXORCC:
		case AMULLW:
		case ADIVW:
		case ADIVWU:
		case AREM:
		case AREMU:
		case ANEG:
		case ANEGCC:

		case AFADD:
		case AFADDS:
		case AFSUB:
		case AFSUBS:
		case AFMUL:
		case AFMULS:
		case AFDIV:
		case AFDIVS:
		case AFNEG:
		case AFNEGCC:
			if(p->to.type == v1->type)
			if(p->to.reg == v1->reg) {
				if(p->reg == NREG)
					p->reg = p->to.reg;
				goto gotit;
			}
			break;

		case AFMOVS:
		case AFMOVD:
		case AMOVW:
			if(p->to.type == v1->type)
			if(p->to.reg == v1->reg)
				goto gotit;
			break;
		}
		if(copyau(&p->from, v2) ||
		   copyau1(p, v2) ||
		   copyau(&p->to, v2))
			break;
		if(copysub(&p->from, v1, v2, 0) ||
		   copysub1(p, v1, v2, 0) ||
		   copysub(&p->to, v1, v2, 0))
			break;
	}
	return 0;

gotit:
	copysub(&p->to, v1, v2, 1);
	if(debug['P']) {
		print("gotit: %D->%D\n%P", v1, v2, r->prog);
		if(p->from.type == v2->type)
			print(" excise");
		print("\n");
	}
	for(r=uniqs(r); r!=r0; r=uniqs(r)) {
		p = r->prog;
		copysub(&p->from, v1, v2, 1);
		copysub1(p, v1, v2, 1);
		copysub(&p->to, v1, v2, 1);
		if(debug['P'])
			print("%P\n", r->prog);
	}
	t = v1->reg;
	v1->reg = v2->reg;
	v2->reg = t;
	if(debug['P'])
		print("%P last\n", r->prog);
	return 1;
}

/*
 * The idea is to remove redundant copies.
 *	v1->v2	F=0
 *	(use v2	s/v2/v1/)*
 *	set v1	F=1
 *	use v2	return fail
 *	-----------------
 *	v1->v2	F=0
 *	(use v2	s/v2/v1/)*
 *	set v1	F=1
 *	set v2	return success
 */
int
copyprop(Reg *r0)
{
	Prog *p;
	Adr *v1, *v2;
	Reg *r;

	p = r0->prog;
	v1 = &p->from;
	v2 = &p->to;
	if(copyas(v1, v2))
		return 1;
	for(r=firstr; r!=R; r=r->link)
		r->active = 0;
	return copy1(v1, v2, r0->s1, 0);
}

copy1(Adr *v1, Adr *v2, Reg *r, int f)
{
	int t;
	Prog *p;

	if(r->active) {
		if(debug['P'])
			print("act set; return 1\n");
		return 1;
	}
	r->active = 1;
	if(debug['P'])
		print("copy %D->%D f=%d\n", v1, v2, f);
	for(; r != R; r = r->s1) {
		p = r->prog;
		if(debug['P'])
			print("%P", p);
		if(!f && uniqp(r) == R) {
			f = 1;
			if(debug['P'])
				print("; merge; f=%d", f);
		}
		t = copyu(p, v2, A);
		switch(t) {
		case 2:	/* rar, cant split */
			if(debug['P'])
				print("; %Drar; return 0\n", v2);
			return 0;

		case 3:	/* set */
			if(debug['P'])
				print("; %Dset; return 1\n", v2);
			return 1;

		case 1:	/* used, substitute */
		case 4:	/* use and set */
			if(f) {
				if(!debug['P'])
					return 0;
				if(t == 4)
					print("; %Dused+set and f=%d; return 0\n", v2, f);
				else
					print("; %Dused and f=%d; return 0\n", v2, f);
				return 0;
			}
			if(copyu(p, v2, v1)) {
				if(debug['P'])
					print("; sub fail; return 0\n");
				return 0;
			}
			if(debug['P'])
				print("; sub%D/%D", v2, v1);
			if(t == 4) {
				if(debug['P'])
					print("; %Dused+set; return 1\n", v2);
				return 1;
			}
			break;
		}
		if(!f) {
			t = copyu(p, v1, A);
			if(!f && (t == 2 || t == 3 || t == 4)) {
				f = 1;
				if(debug['P'])
					print("; %Dset and !f; f=%d", v1, f);
			}
		}
		if(debug['P'])
			print("\n");
		if(r->s2)
			if(!copy1(v1, v2, r->s2, f))
				return 0;
	}
	return 1;
}

/*
 * return
 * 1 if v only used (and substitute),
 * 2 if read-alter-rewrite
 * 3 if set
 * 4 if set and used
 * 0 otherwise (not touched)
 */
int
copyu(Prog *p, Adr *v, Adr *s)
{

	switch(p->as) {

	default:
		if(debug['P'])
			print(" (???)");
		return 2;


	case ANOP:	/* read, write */
	case AMOVW:
	case AMOVH:
	case AMOVHZ:
	case AMOVB:
	case AMOVBZ:

	case ANEG:
	case ANEGCC:

	case AFCTIW:
	case AFCTIWZ:
	case AFMOVS:
	case AFMOVD:
	case AFRSP:
	case AFNEG:
	case AFNEGCC:
		if(s != A) {
			if(copysub(&p->from, v, s, 1))
				return 1;
			if(!copyas(&p->to, v))
				if(copysub(&p->to, v, s, 1))
					return 1;
			return 0;
		}
		if(copyas(&p->to, v)) {
			if(copyau(&p->from, v))
				return 4;
			return 3;
		}
		if(copyau(&p->from, v))
			return 1;
		if(copyau(&p->to, v))
			return 1;
		return 0;

	case AADD:	/* read read write */
	case ASUB:
	case ASLW:
	case ASRW:
	case ASRAW:
	case AOR:
	case AORCC:
	case AORN:
	case AORNCC:
	case AAND:
	case AANDCC:
	case AANDN:
	case AANDNCC:
	case ANAND:
	case ANANDCC:
	case ANOR:
	case ANORCC:
	case AXOR:
	case AMULLW:
	case ADIVW:
	case ADIVWU:
	case AREM:
	case AREMU:

	case AFADDS:
	case AFADD:
	case AFSUBS:
	case AFSUB:
	case AFMULS:
	case AFMUL:
	case AFDIVS:
	case AFDIV:
		if(s != A) {
			if(copysub(&p->from, v, s, 1))
				return 1;
			if(copysub1(p, v, s, 1))
				return 1;
			if(!copyas(&p->to, v))
				if(copysub(&p->to, v, s, 1))
					return 1;
			return 0;
		}
		if(copyas(&p->to, v)) {
			if(p->reg == NREG)
				p->reg = p->to.reg;
			if(copyau(&p->from, v))
				return 4;
			if(copyau1(p, v))
				return 4;
			return 3;
		}
		if(copyau(&p->from, v))
			return 1;
		if(copyau1(p, v))
			return 1;
		if(copyau(&p->to, v))
			return 1;
		return 0;

	case ABEQ:
	case ABGT:
	case ABGE:
	case ABLT:
	case ABLE:
	case ABNE:
	case ABVC:
	case ABVS:
		break;

	case ACMP:	/* read read */
	case ACMPU:
	case AFCMPO:
	case AFCMPU:
		if(s != A) {
			if(copysub(&p->from, v, s, 1))
				return 1;
			return copysub(&p->to, v, s, 1);
		}
		if(copyau(&p->from, v))
			return 1;
		if(copyau(&p->to, v))
			return 1;
		break;

	case ABR:	/* funny */
		if(s != A) {
			if(copysub(&p->to, v, s, 1))
				return 1;
			return 0;
		}
		if(copyau(&p->to, v))
			return 1;
		return 0;

	case ARETURN:	/* funny */
		if(v->type == D_REG)
			if(v->reg == REGRET)
				return 2;
		if(v->type == D_FREG)
			if(v->reg == FREGRET)
				return 2;

	case ABL:	/* funny */
		if(v->type == D_REG) {
			if(v->reg <= REGEXT && v->reg > exregoffset)
				return 2;
			if(v->reg == REGARG)
				return 2;
		}
		if(v->type == D_FREG) {
			if(v->reg <= FREGEXT && v->reg > exfregoffset)
				return 2;
		}

		if(s != A) {
			if(copysub(&p->to, v, s, 1))
				return 1;
			return 0;
		}
		if(copyau(&p->to, v))
			return 4;
		return 3;

	case ATEXT:	/* funny */
		if(v->type == D_REG)
			if(v->reg == REGARG)
				return 3;
		return 0;
	}
	return 0;
}

int
a2type(Prog *p)
{

	switch(p->as) {
	case AADD:
	case AADDCC:
	case ASUB:
	case ASUBCC:
	case ASLW:
	case ASLWCC:
	case ASRW:
	case ASRWCC:
	case ASRAW:
	case ASRAWCC:
	case AOR:
	case AORCC:
	case AORN:
	case AORNCC:
	case AAND:
	case AANDCC:
	case AANDN:
	case AANDNCC:
	case AXOR:
	case AXORCC:
	case ANEG:
	case ANEGCC:
	case AMULLW:
	case AMULLWCC:
	case ADIVW:
	case ADIVWCC:
	case ADIVWU:
	case ADIVWUCC:
	case AREM:
	case AREMCC:
	case AREMU:
	case AREMUCC:
	case ANAND:
	case ANANDCC:
	case ANOR:
	case ANORCC:
		return D_REG;

	case AFADDS:
	case AFADDSCC:
	case AFADD:
	case AFADDCC:
	case AFSUBS:
	case AFSUBSCC:
	case AFSUB:
	case AFSUBCC:
	case AFMULS:
	case AFMULSCC:
	case AFMUL:
	case AFMULCC:
	case AFDIVS:
	case AFDIVSCC:
	case AFDIV:
	case AFDIVCC:
	case AFNEG:
	case AFNEGCC:
		return D_FREG;
	}
	return D_NONE;
}

/*
 * direct reference,
 * could be set/use depending on
 * semantics
 */
int
copyas(Adr *a, Adr *v)
{

	if(regtyp(v))
		if(a->type == v->type)
		if(a->reg == v->reg)
			return 1;
	return 0;
}

/*
 * either direct or indirect
 */
int
copyau(Adr *a, Adr *v)
{

	if(copyas(a, v))
		return 1;
	if(v->type == D_REG)
		if(a->type == D_OREG)
			if(v->reg == a->reg)
				return 1;
	return 0;
}

int
copyau1(Prog *p, Adr *v)
{

	if(regtyp(v))
		if(p->from.type == v->type || p->to.type == v->type)
		if(p->reg == v->reg) {
			if(a2type(p) != v->type)
				print("botch a2type %P\n", p);
			return 1;
		}
	return 0;
}

/*
 * substitute s for v in a
 * return failure to substitute
 */
int
copysub(Adr *a, Adr *v, Adr *s, int f)
{

	if(f)
	if(copyau(a, v))
		a->reg = s->reg;
	return 0;
}

int
copysub1(Prog *p1, Adr *v, Adr *s, int f)
{

	if(f)
	if(copyau1(p1, v))
		p1->reg = s->reg;
	return 0;
}