#include "gc.h"

void
peep(void)
{
	Reg *r, *r1, *r2;
	Prog *p, *p1;
	int t, s;
/*
 * 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:
			p = p->link;
		}
	}

loop1:
	/*
	 * propigate move's by renaming
	 */
	t = 0;
	for(r=firstr; r!=R; r=r->link) {
		p = r->prog;
		if(p->as == AMOVL || p->as == AFMOVEF || p->as == AFMOVED)
		if(regtyp(p->from.type))
		if(anyvar(&p->to)) {
			if(copyprop(r)) {
				excise(r);
				t++;
			} else
			if(subprop(r) && copyprop(r)) {
				excise(r);
				t++;
			}
		}
	}
	if(t)
		goto loop1;
	for(r=firstr; r!=R; r=r->link) {
		p = r->prog;
		/*
		 * convert (A) ... A++ into (A)++
		 * and     A-- ... (A) into --(A)
		 */
		t = aregind(&p->from);
		if(t == D_NONE)
			goto out1;
		s = asize(p->as);
		if(s == 0)
			goto out1;
		r1 = findop(r, t, AADDL, s);
		if(r1 != R) {
			if(usedin(t, &p->to))
				goto out1;
			p->from.type += I_INDINC - I_INDIR;
			excise(r1);
			goto out1;
		}
		r1 = findop(r, t, ASUBL, s);
		if(r1 != R) {
			p->from.type += I_INDDEC - I_INDIR;
			excise(r1);
		}
	out1:
		t = aregind(&p->to);
		if(t == D_NONE)
			goto out2;
		s = asize(p->as);
		if(s == 0)
			goto out2;
		r1 = findop(r, t, AADDL, s);
		if(r1 != R) {
			p->to.type += I_INDINC - I_INDIR;
			excise(r1);
			goto out2;
		}
		r1 = findop(r, t, ASUBL, s);
		if(r1 != R) {
			if(usedin(t, &p->from))
				goto out2;
			p->to.type += I_INDDEC - I_INDIR;
			excise(r1);
		}
	out2:
		/*
		 * get rid of unneeded save/restore CCR
		 */
		if(p->from.type == D_CCR) {
			r1 = findccr(r);
			if(r1 != R) {
				excise(r);
				excise(r1);
			}
		}
		switch(p->as) {
		case ATSTB:
		case ATSTW:
		case ATSTL:
			if(findtst(r, r->prog, 0))
				excise(r);
		}
		/*
		 * turn TSTB (A); BLT; ORB $128,(A) into TAS (A); BLT; NOP
		 */
		if(p->as == ATSTB && (r1 = r->s1)) {
			if((r1->prog->as == ABLT && (r2 = r1->s1)) ||
			   (r1->prog->as == ABGE && (r2 = r1->s2))) {
				p1 = r2->prog;
				if(p1->as == AORB)
				if(p1->from.type == D_CONST)
				if(p1->from.u0.s0.offset == 128)
				if(r1 == uniqp(r2))
				if(tasas(&p->to, &p1->to)) {
					p->as = ATAS;
					excise(r2);
				}
			}
		}
	}
}

void
excise(Reg *r)
{

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

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;
}

/*
 * chase backward all cc setting.
 * returns 1 if all set same.
 */
int
findtst(Reg *r0, Prog *rp, int n)
{
	Reg *r;
	int c;

loop:
	n++;
	if(n >= 10)
		return 0;
	for(r=r0->p2; r!=R; r=r->p2link) {
		c = setcc(r->prog, rp);
		if(c > 0)
			continue;
		if(c == 0)
			return 0;
		if(findtst(r, rp, n) == 0)
			return 0;
	}
	r = r0->p1;
	if(r == R)
		return 1;
	c = setcc(r->prog, rp);
	if(c > 0)
		return 1;
	if(c == 0)
		return 0;
	r0 = r;
	goto loop;
}

/*
 * tests cc
 * returns -1 if no change
 * returns 1 if set the same
 * returns 0 if set different
 */
int
setcc(Prog *p, Prog *rp)
{
	int s;

	s = asize(rp->as);
	switch(p->as) {
	default:
		if(debug['P'])
			print("unknown setcc %A\n", p->as);
		break;

	case ACMPB:
	case ACMPW:
	case ACMPL:
	case ABSR:
		return 0;

	case ABRA:
	case ABGE:
	case ABNE:
	case ABLE:
	case ABEQ:
	case ABHI:
	case ABLS:
	case ABMI:
	case ABPL:
	case ABGT:
	case ABLT:
	case ABCC:
	case ABCS:
	case APEA:
	case ALEA:
	case ANOP:

	case AFADDD:
	case AFMULD:
	case AFDIVD:
	case AFSUBD:
	case AFADDF:
	case AFMULF:
	case AFDIVF:
	case AFSUBF:
	case AADJSP:
		return -1;

	case AADDW:
	case AADDL:
	case ASUBW:
	case ASUBL:
	case ACLRL:
	case ACLRW:
		if(p->to.type >= D_A0 && p->to.type < D_A0+8)
			goto areg;

	case AADDB:
	case ASUBB:
	case AANDB:
	case AANDW:
	case AANDL:
	case AORB:
	case AORW:
	case AORL:
	case AEORB:
	case AEORW:
	case AEORL:
	case ALSLB:
	case ALSLW:
	case ALSLL:
	case ALSRB:
	case ALSRW:
	case ALSRL:
	case AASLB:
	case AASLW:
	case AASLL:
	case AASRB:
	case AASRW:
	case AASRL:
	case ATSTB:
	case ATSTW:
	case ATSTL:
	case ANEGB:
	case ANEGW:
	case ANEGL:
	case ACLRB:
		if(asize(p->as) != s)
			break;
		if(compat(&rp->to, &p->to))
			return 1;
		break;

	case AMOVW:
	case AMOVL:
		if(p->to.type >= D_A0 && p->to.type < D_A0+8)
			goto areg;
	case AMOVB:
		if(asize(p->as) != s)
			break;
		if(compat(&rp->to, &p->to))
			return 1;
		if(compat(&rp->to, &p->from))
			return 1;
	}
	return 0;

areg:
	if((rp->to.type&D_MASK) == p->to.type)
		return 0;
	return -1;
}

int
compat(Adr *a, Adr *b)
{
	int o;

	if(a->index != D_NONE)
		return 0;
	if(b->index != D_NONE)
		return 0;
	o = a->type;
	if((o >= D_R0 && o < D_R0+NREG) ||
	   (o >= D_A0 && o < D_A0+NREG))
		return o == b->type;
	o &= D_MASK;
	if(o >= D_A0 && o < D_A0+NREG) {
		if(o != (b->type&D_MASK))
			return 0;
		if(a->u0.s0.offset != b->u0.s0.offset)
			return 0;
		o = a->type & I_MASK;
		if(o == I_INDIR) {
			o = b->type & I_MASK;
			if(o == I_INDIR || o == I_INDDEC)
				return 1;
			return 0;
		}
		if(o == I_INDINC) {
			o = b->type & I_MASK;
			if(o == I_INDIR) {
				b->type += I_INDINC-I_INDIR;
				return 1;
			}
			if(o == I_INDDEC) {
				b->type += I_INDIR-I_INDDEC;
				return 1;
			}
			return 0;
		}
	}
	return 0;
}

int
aregind(Adr *a)
{
	int t;

	t = a->type;
	if(t >= (D_A0|I_INDIR) && t < ((D_A0+NREG)|I_INDIR))
	while(a->u0.s0.offset == 0 && a->index == D_NONE)
		return t & D_MASK;
	return D_NONE;
}

int
asize(int a)
{

	switch(a) {
	case AFTSTD:
	case AFMOVED:
	case AFADDD:
	case AFSUBD:
	case AFMULD:
	case AFDIVD:
	case AFCMPD:
	case AFNEGD:
		return 8;

	case AFTSTF:
	case AFMOVEF:
	case AFADDF:
	case AFSUBF:
	case AFMULF:
	case AFDIVF:
	case AFCMPF:
	case AFNEGF:

	case ACLRL:
	case ATSTL:
	case AMOVL:
	case AADDL:
	case ASUBL:
	case ACMPL:
	case AANDL:
	case AORL:
	case AEORL:
	case ALSLL:
	case ALSRL:
	case AASLL:
	case AASRL:
	case ANEGL:
		return 4;

	case ACLRW:
	case ATSTW:
	case AMOVW:
	case AADDW:
	case ASUBW:
	case ACMPW:
	case AANDW:
	case AORW:
	case AEORW:
	case ALSLW:
	case ALSRW:
	case AASLW:
	case AASRW:
	case ANEGW:
		return 2;

	case ACLRB:
	case ATSTB:
	case AMOVB:
	case AADDB:
	case ASUBB:
	case ACMPB:
	case AANDB:
	case AORB:
	case AEORB:
	case ALSLB:
	case ALSRB:
	case AASLB:
	case AASRB:
	case ANEGB:
		return 1;
	}
	if(debug['P'])
		print("unknown asize %A\n", p->as);
	return 0;
}

int
usedin(int t, Adr *a)
{

	if((a->type&D_MASK) == t)
		return 1;
	if((a->index&D_MASK) == t)
		return 1;
	return 0;
}

Reg*
findccr(Reg *r)
{
	Prog *p;

	for(;;) {
		r = uniqs(r);
		if(r == R)
			break;
		p = r->prog;
		if(p->to.type == D_CCR)
			return r;
		if(setccr(p))
			break;
	}
	return R;
}

int
setccr(Prog *p)
{

	switch(p->as) {
	case ANOP:
		return 0;

	case AADDL:
	case AMOVL:
	case ACLRL:
		if(p->to.type >= D_A0 && p->to.type < D_A0+8)
			return 0;
	}
	return 1;
}

Reg*
findop(Reg *r, int t, int o, int s)
{
	Prog *p;
	Reg *r1;

	for(;;) {
		if(o == AADDL) {
			r1 = uniqs(r);
			if(r1 == R)
				break;
			if(uniqp(r1) != r)
				break;
		} else {
			r1 = uniqp(r);
			if(r1 == R)
				break;
			if(uniqs(r1) != r)
				break;
		}
		r = r1;
		p = r->prog;
		if(usedin(t, &p->from))
			break;
		if(usedin(t, &p->to)) {
			if(p->as == o)
			if(p->to.type == t)
			if(p->to.index == D_NONE)
			if(p->from.type == D_CONST)
			if(p->from.u0.s0.offset == s)
				return r;
			break;
		}
	}
	return R;
}

int
regtyp(int t)
{

	if(t >= D_R0 && t < D_R0+8)
		return 1;
	if(t >= D_A0 && t < D_A0+8)
		return 1;
	if(t >= D_F0 && t < D_F0+8)
		return 1;
	return 0;
}

int
anyvar(Adr *a)
{

	if(regtyp(a->type))
		return 1;
	return 0;
	if(a->type == D_AUTO || a->type == D_PARAM)
		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 MOVL
 * 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->type))
		return 0;
	v2 = &p->to;
	if(!regtyp(v2->type))
		return 0;
	for(r=uniqp(r0); r!=R; r=uniqp(r)) {
		if(uniqs(r) == R)
			break;
		p = r->prog;
		switch(p->as) {
		case ADIVUW:	/* these set Rn and Rn+1 */
		case ADIVUL:
		case ADIVSW:
		case ADIVSL:
		case ABSR:
			return 0;

		case AFMOVED:
		case AFMOVEF:
		case AMOVL:
			if(p->to.type == v1->type)
				goto gotit;
		}
		if(copyau(&p->from, v2) || copyau(&p->to, v2))
			break;
		if(copysub(&p->from, v1, v2, p, 0) || copysub(&p->to, v1, v2, p, 0))
			break;
	}
	return 0;

gotit:
	copysub(&p->to, v1, v2, p, 1);
	if(debug['P']) {
		print("gotit: %D->%D\n%P", v1, v2, r->prog);
		if(p->from.type == v2->type)
			print(" excise");
		print("\n");
	}
	if(p->from.type == v2->type)
		excise(r);
	for(r=uniqs(r); r!=r0; r=uniqs(r)) {
		p = r->prog;
		copysub(&p->from, v1, v2, p, 1);
		copysub(&p->to, v1, v2, p, 1);
		if(debug['P'])
			print("%P\n", r->prog);
	}
	t = v1->type;
	v1->type = v2->type;
	v2->type = 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->u0.active = 0;
	return copy1(v1, v2, r0->s1, 0);
}

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

	if(r->u0.active) {
		if(debug['P'])
			print("copyret 1\n");
		return 1;
	}
	r->u0.active = 1;
	if(debug['P'])
		print("copy %D->%D\n", v1, v2);
	for(; r != R; r = r->s1) {
		if(debug['P'])
			print("%P", r->prog);
		if(!f && uniqp(r) == R) {
			f = 1;
			if(debug['P'])
				print("; merge; f=%d", f);
		}
		t = copyu(r->prog, v2, A);
		switch(t) {
		case 2:	/* rar, cant split */
			if(debug['P'])
				print("; rar return 0\n");
			return 0;
		case 3:	/* set */
			if(debug['P'])
				print("; set; return 1\n");
			return 1;
		case 1:	/* used, substitute */
		case 4:	/* use and set */
			if(f) {
				if(debug['P'])
					print("; used and f; return 0\n");
				return 0;
			}
			if(copyu(r->prog, v2, v1)) {
				if(debug['P'])
					print("; sub fail; return 0\n");
				return 0;
			}
			if(debug['P'])
				print("; substitute");
			if(t == 4) {
				if(debug['P'])
					print("; used and set; return 1\n");
				return 1;
			}
			break;
		}
		if(!f) {
			t = copyu(r->prog, v1, A);
			if(!f && (t == 2 || t == 3 || t == 4)) {
				if(debug['P'])
					print("; f set used");
				f = 1;
			}
		}
		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)
{
	int t;

	switch(p->as) {

	default:
		if(debug['P'])
			print("unknown op %A\n", p->as);
		return 2;

	case APEA:	/* rhs addr */
		if(copyas(&p->to, v))
			return 2;
		goto caseread;

	case ALEA:	/* lhs addr, rhs store */
		if(copyas(&p->from, v))
			return 2;

	case AMOVL:	/* rhs store */
	case ACLRL:
	case AFMOVEF:
	case AFMOVED:
	case AFMOVEB:
	case AFMOVEW:
	case AFMOVEL:
	case ANOP:
		if(copyas(&p->to, v)) {
			if(s != A)
				return copysub(&p->from, v, s, p, 1);
			if(copyau(&p->from, v))
				return 4;
			return 3;
		}
		goto caseread;
			
	case AADDL:	/* rhs rar */
	case AADDW:
	case AADDB:
	case ASUBL:
	case ASUBW:
	case ASUBB:
	case AANDL:
	case AANDW:
	case AANDB:
	case AORL:
	case AORW:
	case AORB:
	case AEORL:
	case AEORW:
	case AEORB:
	case AASRL:
	case AASRW:
	case AASRB:
	case AASLL:
	case AASLW:
	case AASLB:
	case ALSRL:
	case ALSRW:
	case ALSRB:
	case ANOTL:
	case ANOTW:
	case ANOTB:
	case ANEGL:
	case ANEGW:
	case ANEGB:
	case AEXTBL:
	case AEXTWL:
	case AEXTBW:

	case AMULSL:
	case AMULUL:

	case AMOVW:	/* only sets part of register */
	case AMOVB:
	case ACLRW:
	case ACLRB:

	case AFADDD:
	case AFMULD:
	case AFDIVD:
	case AFSUBD:
	case AFNEGD:
	case AFADDF:
	case AFMULF:
	case AFDIVF:
	case AFSUBF:
	case AFNEGF:
		if(copyas(&p->to, v))
			return 2;
		goto caseread;

	case ADBF:	/* lhs rar */
		if(copyas(&p->from, v))
			return 2;
		goto caseread;

	case ACMPL:	/* read only */
	case ACMPW:
	case ACMPB:
	case AFCMPF:
	case AFCMPD:
	case ATSTL:
	case ATSTW:
	case ATSTB:
	case AFTSTF:
	case AFTSTD:
	caseread:
		if(s != A) {
			if(copysub(&p->from, v, s, p, 1))
				return 1;
			return copysub(&p->to, v, s, p, 1);
		}
		if(copyau(&p->from, v))
			return 1;
		if(copyau(&p->to, v))
			return 1;
		break;

	case ABRA:	/* no reference */
	case ABGE:
	case ABNE:
	case ABLE:
	case ABEQ:
	case ABHI:
	case ABLS:
	case ABMI:
	case ABPL:
	case ABGT:
	case ABLT:
	case ABCC:
	case ABCS:

	case AFBEQ:
	case AFBNE:
	case AFBGT:
	case AFBGE:
	case AFBLE:
	case AFBLT:

	case AADJSP:
	case ACASEW:
		break;

	case ADIVUW:	/* these set Rn and Rn+1 */
	case ADIVUL:
	case ADIVSW:
	case ADIVSL:
		t = v->type;
		if(t == p->to.type || t == p->to.type+1)
			return 2;
		goto caseread;

	case ARTS:	/* funny */
		t = v->type;
		if(t == D_R0 || t == D_F0)
			return 2;
		if(t >= D_R0 && t < D_R0+NREG)
		if(t-D_R0 > exregoffset)
			return 2;
		if(t >= D_A0 && t < D_A0+NREG)
		if(t-D_A0 > exaregoffset)
			return 2;
		if(t >= D_F0 && t < D_F0+NREG)
		if(t-D_F0 > exfregoffset)
			return 2;
		return 3;

	case ABSR:	/* funny */
		t = v->type;
		if(t >= D_R0 && t < D_R0+NREG)
		if(t-D_R0 > exregoffset)
			return 2;
		if(t >= D_A0 && t < D_A0+NREG)
		if(t-D_A0 > exaregoffset)
			return 2;
		if(t >= D_F0 && t < D_F0+NREG)
		if(t-D_F0 > exfregoffset)
			return 2;
		return 3;
	}
	return 0;
}

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

	if(a->type != v->type)
		return 0;
	if(regtyp(v->type))
		return 1;
	if(v->type == D_AUTO || v->type == D_PARAM) {
		if(v->u0.s0.offset == a->u0.s0.offset)
			return 1;
		return 0;
	}
	return 0;
}

/*
 * indirect
 */
int
tasas(Adr *a, Adr *v)
{
	int t;

	if(a->index != D_NONE)
		return 0;
	if(v->index != D_NONE)
		return 0;
	t = a->type;
	if(t < I_INDIR+D_A0 && t >= I_INDIR+D_A0+8)
		return 0;
	if(v->type != t)
		return 0;
	if(a->u0.s0.displace != v->u0.s0.displace)
		return 0;
	return 1;
}

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

	if(copyas(a, v))
		return 1;
	t = v->type;
	if(regtyp(t)) {
		if((a->type & D_MASK) == t)
			return 1;
		if((a->index & D_MASK) == t)
			return 1;
	}
	return 0;
}

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

	if(copyas(a, v)) {
		t = s->type;
		if(t >= D_F0 && t < D_F0+8) {
			if(f)
				a->type = t;
			return 0;
		}
		if(t >= D_R0 && t < D_R0+8) {
			if(f)
				a->type = t;
			return 0;
		}
		if(!(t >= D_A0 && t < D_A0+8))
			return 1;
		switch(p->as) {
		default:
			return 1;

		case AMOVL:
		case AMOVW:
		case ACMPL:
		case ACMPW:
			break;

		case AADDL:
		case AADDW:
		case ASUBL:
		case ASUBW:
			if(a == &p->from && !regtyp(p->to.type))
				return 1;
			break;
		}
		if(f)
			a->type = t;
		return 0;
	}
	t = v->type;
	if(regtyp(t)) {
		if((a->type & D_MASK) == t) {
			if((s->type ^ t) & ~(NREG-1))
				return 1;
			if(f)
				a->type = (a->type & ~D_MASK) | s->type;
			return 0;
		}
		if((a->index & D_MASK) == t) {
			if(f)
				a->index = (a->index & ~D_MASK) | s->type;
			return 0;
		}
		return 0;
	}
	return 0;
}