peep.c

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

	return R;
}

int
nochange(Reg *r, Reg *r2, Prog *p)
{
	Adr a[3];
	int i, n;

	if(r == r2)
		return 1;
	n = 0;
	if(p->reg != NREG && p->reg != p->to.reg) {
		a[n].type = D_REG;
		a[n++].reg = p->reg;
	}
	switch(p->from.type) {
	case D_SHIFT:
		a[n].type = D_REG;
		a[n++].reg = p->from.offset&0xf;
	case D_REG:
		a[n].type = D_REG;
		a[n++].reg = p->from.reg;
	}
	if(n == 0)
		return 1;
	for(; r!=R && r!=r2; r=uniqs(r)) {
		p = r->prog;
		for(i=0; i<n; i++)
			if(copyu(p, &a[i], A) > 1)
				return 0;
	}
	return 1;
}

int
findu1(Reg *r, Adr *v)
{
	for(; r != R; r = r->s1) {
		if(r->active)
			return 0;
		r->active = 1;
		switch(copyu(r->prog, v, A)) {
		case 1: /* used */
		case 2: /* read-alter-rewrite */
		case 4: /* set and used */
			return 1;
		case 3: /* set */
			return 0;
		}
		if(r->s2)
			if (findu1(r->s2, v))
				return 1;
	}
	return 0;
}

int
finduse(Reg *r, Adr *v)
{
	Reg *r1;

	for(r1=firstr; r1!=R; r1=r1->link)
		r1->active = 0;
	return findu1(r, v);
}

int
xtramodes(Reg *r, Adr *a)
{
	Reg *r1, *r2, *r3;
	Prog *p, *p1;
	Adr v;

	p = r->prog;
	if(debug['h'] && p->as == AMOVB && p->from.type == D_OREG)	/* byte load */
		return 0;
	v = *a;
	v.type = D_REG;
	r1 = findpre(r, &v);
	if(r1 != R) {
		p1 = r1->prog;
		if(p1->to.type == D_REG && p1->to.reg == v.reg)
		switch(p1->as) {
		case AADD:
			if(p1->from.type == D_REG ||
			   (p1->from.type == D_SHIFT && (p1->from.offset&(1<<4)) == 0 &&
			    (p->as != AMOVB || (a == &p->from && (p1->from.offset&~0xf) == 0))) ||
			   (p1->from.type == D_CONST && 
			    p1->from.offset > -4096 && p1->from.offset < 4096))
			if(nochange(uniqs(r1), r, p1)) {
				if(a != &p->from || v.reg != p->to.reg)
				if (finduse(r->s1, &v)) {
					if(p1->reg == NREG || p1->reg == v.reg)
						/* pre-indexing */
						p->scond |= C_WBIT;
					else return 0;	
				}
				switch (p1->from.type) {
				case D_REG:
					/* register offset */
					a->type = D_SHIFT;
					a->offset = p1->from.reg;
					break;
				case D_SHIFT:
					/* scaled register offset */
					a->type = D_SHIFT;
				case D_CONST:
					/* immediate offset */
					a->offset = p1->from.offset;
					break;
				}
				if(p1->reg != NREG)
					a->reg = p1->reg;
				excise(r1);
				return 1;
			}
			break;
		case AMOVW:
			if(p1->from.type == D_REG)
			if((r2 = findinc(r1, r, &p1->from)) != R) {
			for(r3=uniqs(r2); r3->prog->as==ANOP; r3=uniqs(r3))
				;
			if(r3 == r) {
				/* post-indexing */
				p1 = r2->prog;
				a->reg = p1->to.reg;
				a->offset = p1->from.offset;
				p->scond |= C_PBIT;
				if(!finduse(r, &r1->prog->to))
					excise(r1);
				excise(r2);
				return 1;
			}
			}
			break;
		}
	}
	if(a != &p->from || a->reg != p->to.reg)
	if((r1 = findinc(r, R, &v)) != R) {
		/* post-indexing */
		p1 = r1->prog;
		a->offset = p1->from.offset;
		p->scond |= C_PBIT;
		excise(r1);
		return 1;
	}
	return 0;
}

/*
 * 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 AMOVM:
		if(v->type != D_REG)
			return 0;
		if(p->from.type == D_CONST) {	/* read reglist, read/rar */
			if(s != A) {
				if(p->from.offset&(1<<v->reg))
					return 1;
				if(copysub(&p->to, v, s, 1))
					return 1;
				return 0;
			}
			if(copyau(&p->to, v)) {
				if(p->scond&C_WBIT)
					return 2;
				return 1;
			}
			if(p->from.offset&(1<<v->reg))
				return 1;
		} else {			/* read/rar, write reglist */
			if(s != A) {
				if(p->to.offset&(1<<v->reg))
					return 1;
				if(copysub(&p->from, v, s, 1))
					return 1;
				return 0;
			}
			if(copyau(&p->from, v)) {
				if(p->scond&C_WBIT)
					return 2;
				if(p->to.offset&(1<<v->reg))
					return 4;
				return 1;
			}
			if(p->to.offset&(1<<v->reg))
				return 3;
		}
		return 0;
		
	case ANOP:	/* read, write */
	case AMOVW:
	case AMOVF:
	case AMOVD:
	case AMOVH:
	case AMOVHU:
	case AMOVB:
	case AMOVBU:
	case AMOVDW:
	case AMOVWD:
	case AMOVFD:
	case AMOVDF:
		if(p->scond&(C_WBIT|C_PBIT))
		if(v->type == D_REG) {
			if(p->from.type == D_OREG || p->from.type == D_SHIFT) {
				if(p->from.reg == v->reg)
					return 2;
			} else {
		  		if(p->to.reg == v->reg)
				return 2;
			}
		}
		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 ARSB:
	case ASLL:
	case ASRL:
	case ASRA:
	case AORR:
	case AAND:
	case AEOR:
	case AMUL:
	case ADIV:
	case ADIVU:
	case AADDF:
	case AADDD:
	case ASUBF:
	case ASUBD:
	case AMULF:
	case AMULD:
	case ADIVF:
	case ADIVD:

	case ACMPF:
	case ACMPD:
	case ACMP:
	case ACMN:
	case ACASE:
		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:	/* read, read */
	case ABNE:
	case ABCS:
	case ABHS:
	case ABCC:
	case ABLO:
	case ABMI:
	case ABPL:
	case ABVS:
	case ABVC:
	case ABHI:
	case ABLS:
	case ABGE:
	case ABLT:
	case ABGT:
	case ABLE:
		if(s != A) {
			if(copysub(&p->from, v, s, 1))
				return 1;
			return copysub1(p, v, s, 1);
		}
		if(copyau(&p->from, v))
			return 1;
		if(copyau1(p, v))
			return 1;
		return 0;

	case AB:	/* 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 ARET:	/* 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;
	}
}

int
a2type(Prog *p)
{

	switch(p->as) {

	case ACMP:
	case ACMN:

	case AADD:
	case ASUB:
	case ARSB:
	case ASLL:
	case ASRL:
	case ASRA:
	case AORR:
	case AAND:
	case AEOR:
	case AMUL:
	case ADIV:
	case ADIVU:
		return D_REG;

	case ACMPF:
	case ACMPD:

	case AADDF:
	case AADDD:
	case ASUBF:
	case ASUBD:
	case AMULF:
	case AMULD:
	case ADIVF:
	case ADIVD:
		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;
	} else if(v->type == D_CONST) {		/* for constprop */
		if(a->type == v->type)
		if(a->name == v->name)
		if(a->sym == v->sym)
		if(a->reg == v->reg)
		if(a->offset == v->offset)
			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;
		} else if(a->type == D_SHIFT) {
			if((a->offset&0xf) == v->reg)
				return 1;
			if((a->offset&(1<<4)) && (a->offset>>8) == v->reg)
				return 1;
		}
	}
	return 0;
}

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

	if(regtyp(v)) {
		if(a2type(p) == 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)) {
		if(a->type == D_SHIFT) {
			if((a->offset&0xf) == v->reg)
				a->offset = (a->offset&~0xf)|s->reg;
			if((a->offset&(1<<4)) && (a->offset>>8) == v->reg)
				a->offset = (a->offset&~(0xf<<8))|(s->reg<<8);
		} else
			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;
}

struct {
	int opcode;
	int notopcode;
	int scond; 
	int notscond; 
} predinfo[]  = { 
	{ ABEQ,	ABNE,	0x0,	0x1, }, 
	{ ABNE,	ABEQ,	0x1,	0x0, }, 
	{ ABCS,	ABCC,	0x2,	0x3, }, 
	{ ABHS,	ABLO,	0x2,	0x3, }, 
	{ ABCC,	ABCS,	0x3,	0x2, }, 
	{ ABLO,	ABHS,	0x3,	0x2, }, 
	{ ABMI,	ABPL,	0x4,	0x5, }, 
	{ ABPL,	ABMI,	0x5,	0x4, }, 
	{ ABVS,	ABVC,	0x6,	0x7, }, 
	{ ABVC,	ABVS,	0x7,	0x6, }, 
	{ ABHI,	ABLS,	0x8,	0x9, }, 
	{ ABLS,	ABHI,	0x9,	0x8, }, 
	{ ABGE,	ABLT,	0xA,	0xB, }, 
	{ ABLT,	ABGE,	0xB,	0xA, }, 
	{ ABGT,	ABLE,	0xC,	0xD, }, 
	{ ABLE,	ABGT,	0xD,	0xC, }, 
}; 

typedef struct {
	Reg *start;
	Reg *last;
	Reg *end;
	int len;
} Joininfo;

enum {
	Join,
	Split,
	End,
	Branch,
	Setcond,
	Toolong
};
	
enum {
	Falsecond,
	Truecond,
	Delbranch,
	Keepbranch
};

int 
isbranch(Prog *p)
{
	return (ABEQ <= p->as) && (p->as <= ABLE); 
}

int
predicable(Prog *p)
{
	if (isbranch(p)
		|| p->as == ANOP
		|| p->as == AXXX
		|| p->as == ADATA
		|| p->as == AGLOBL
		|| p->as == AGOK
		|| p->as == AHISTORY
		|| p->as == ANAME
		|| p->as == ASIGNAME
		|| p->as == ATEXT
		|| p->as == AWORD
		|| p->as == ADYNT
		|| p->as == AINIT
		|| p->as == ABCASE
		|| p->as == ACASE)
		return 0; 
	return 1; 
}

/* 
 * Depends on an analysis of the encodings performed by 5l. 
 * These seem to be all of the opcodes that lead to the "S" bit
 * being set in the instruction encodings. 
 * 
 * C_SBIT may also have been set explicitly in p->scond.
 */ 
int
modifiescpsr(Prog *p)
{
	return (p->scond&C_SBIT)
		|| p->as == ATST 
		|| p->as == ATEQ 
		|| p->as == ACMN
		|| p->as == ACMP
		|| p->as == AMULU
		|| p->as == ADIVU
		|| p->as == AMUL
		|| p->as == ADIV
		|| p->as == AMOD
		|| p->as == AMODU
		|| p->as == ABL;
} 

/*
 * Find the maximal chain of instructions starting with r which could
 * be executed conditionally
 */
int
joinsplit(Reg *r, Joininfo *j)
{
	j->start = r;
	j->last = r;
	j->len = 0;
	do {
		if (r->p2 && (r->p1 || r->p2->p2link)) {
			j->end = r;
			return Join;
		}
		if (r->s1 && r->s2) {
			j->end = r;
			return Split;
		}
		j->last = r;
		if (r->prog->as != ANOP)
			j->len++;
		if (!r->s1 && !r->s2) {
			j->end = r->link;
			return End;
		}
		if (r->s2) {
			j->end = r->s2;
			return Branch;
		}
		if (modifiescpsr(r->prog)) {
			j->end = r->s1;
			return Setcond;
		}
		r = r->s1;
	} while (j->len < 4);
	j->end = r;
	return Toolong;
}

Reg *
successor(Reg *r)
{
	if (r->s1)
		return r->s1; 
	else
		return r->s2; 
}

void
applypred(Reg *rstart, Joininfo *j, int cond, int branch)
{
	int pred; 
	Reg *r; 

	if(j->len == 0)
		return;
	if (cond == Truecond)
		pred = predinfo[rstart->prog->as - ABEQ].scond;
	else
		pred = predinfo[rstart->prog->as - ABEQ].notscond; 
	
	for (r = j->start; ; r = successor(r)) {
		if (r->prog->as == AB) {
			if (r != j->last || branch == Delbranch)
				excise(r);
			else {
			  if (cond == Truecond)
				r->prog->as = predinfo[rstart->prog->as - ABEQ].opcode;
			  else
				r->prog->as = predinfo[rstart->prog->as - ABEQ].notopcode;
			}
		}
		else if (predicable(r->prog)) 
			r->prog->scond = (r->prog->scond&~C_SCOND)|pred;
		if (r->s1 != r->link) {
			r->s1 = r->link;
			r->link->p1 = r;
		}
		if (r == j->last)
			break;
	}
}

void
predicate(void)
{	
	Reg *r;
	int t1, t2;
	Joininfo j1, j2;

	for(r=firstr; r!=R; r=r->link) {
		if (isbranch(r->prog)) {
			t1 = joinsplit(r->s1, &j1);
			t2 = joinsplit(r->s2, &j2);
			if(j1.last->link != j2.start)
				continue;
			if(j1.end == j2.end)
			if((t1 == Branch && (t2 == Join || t2 == Setcond)) ||
			   (t2 == Join && (t1 == Join || t1 == Setcond))) {
				applypred(r, &j1, Falsecond, Delbranch);
				applypred(r, &j2, Truecond, Delbranch);
				excise(r);
				continue;
			}
			if(t1 == End || t1 == Branch) {
				applypred(r, &j1, Falsecond, Keepbranch);
				excise(r);
				continue;
			}
		} 
	} 
}