8a, 8c, and 8l from inferno distribution

R=r
DELTA=19539  (19539 added, 0 deleted, 0 changed)
OCL=22109
CL=22109

1 files changed, 787 insertions, 0 deletions

diff --git a/src/cmd/8c/peep.c b/src/cmd/8c/peep.c
new file mode 100644
index 000000000..b30a57b0a
--- /dev/null
+++ b/src/cmd/8c/peep.c
@@ -0,0 +1,787 @@
+// Inferno utils/8c/peep.c
+// http://code.google.com/p/inferno-os/source/browse/utils/8c/peep.c
+//
+//	Copyright © 1994-1999 Lucent Technologies Inc.  All rights reserved.
+//	Portions Copyright © 1995-1997 C H Forsyth (forsyth@terzarima.net)
+//	Portions Copyright © 1997-1999 Vita Nuova Limited
+//	Portions Copyright © 2000-2007 Vita Nuova Holdings Limited (www.vitanuova.com)
+//	Portions Copyright © 2004,2006 Bruce Ellis
+//	Portions Copyright © 2005-2007 C H Forsyth (forsyth@terzarima.net)
+//	Revisions Copyright © 2000-2007 Lucent Technologies Inc. and others
+//	Portions Copyright © 2009 The Go Authors.  All rights reserved.
+//
+// Permission is hereby granted, free of charge, to any person obtaining a copy
+// of this software and associated documentation files (the "Software"), to deal
+// in the Software without restriction, including without limitation the rights
+// to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
+// copies of the Software, and to permit persons to whom the Software is
+// furnished to do so, subject to the following conditions:
+//
+// The above copyright notice and this permission notice shall be included in
+// all copies or substantial portions of the Software.
+//
+// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
+// IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
+// FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.  IN NO EVENT SHALL THE
+// AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
+// LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
+// OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
+// THE SOFTWARE.
+
+#include "gc.h"
+
+static int
+needc(Prog *p)
+{
+	while(p != P) {
+		switch(p->as) {
+		case AADCL:
+		case ASBBL:
+		case ARCRL:
+			return 1;
+		case AADDL:
+		case ASUBL:
+		case AJMP:
+		case ARET:
+		case ACALL:
+			return 0;
+		default:
+			if(p->to.type == D_BRANCH)
+				return 0;
+		}
+		p = p->link;
+	}
+	return 0;
+}
+
+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;
+		}
+	}
+
+	pc = 0;	/* speculating it won't kill */
+
+loop1:
+
+	t = 0;
+	for(r=firstr; r!=R; r=r->link) {
+		p = r->prog;
+		switch(p->as) {
+		case AMOVL:
+			if(regtyp(&p->to))
+			if(regtyp(&p->from)) {
+				if(copyprop(r)) {
+					excise(r);
+					t++;
+				}
+				if(subprop(r) && copyprop(r)) {
+					excise(r);
+					t++;
+				}
+			}
+			break;
+
+		case AMOVBLSX:
+		case AMOVBLZX:
+		case AMOVWLSX:
+		case AMOVWLZX:
+			if(regtyp(&p->to)) {
+				r1 = uniqs(r);
+				if(r1 != R) {
+					p1 = r1->prog;
+					if(p->as == p1->as && p->to.type == p1->from.type)
+						p1->as = AMOVL;
+				}
+			}
+			break;
+		case AADDL:
+		case AADDW:
+			if(p->from.type != D_CONST || needc(p->link))
+				break;
+			if(p->from.offset == -1){
+				if(p->as == AADDL)
+					p->as = ADECL;
+				else
+					p->as = ADECW;
+				p->from = zprog.from;
+			}
+			else if(p->from.offset == 1){
+				if(p->as == AADDL)
+					p->as = AINCL;
+				else
+					p->as = AINCW;
+				p->from = zprog.from;
+			}
+			break;
+		case ASUBL:
+		case ASUBW:
+			if(p->from.type != D_CONST || needc(p->link))
+				break;
+			if(p->from.offset == -1) {
+				if(p->as == ASUBL)
+					p->as = AINCL;
+				else
+					p->as = AINCW;
+				p->from = zprog.from;
+			}
+			else if(p->from.offset == 1){
+				if(p->as == ASUBL)
+					p->as = ADECL;
+				else
+					p->as = ADECW;
+				p->from = zprog.from;
+			}
+			break;
+		}
+	}
+	if(t)
+		goto loop1;
+}
+
+void
+excise(Reg *r)
+{
+	Prog *p;
+
+	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;
+}
+
+int
+regtyp(Adr *a)
+{
+	int t;
+
+	t = a->type;
+	if(t >= D_AX && t <= D_DI)
+		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 ACALL:
+			return 0;
+
+		case AIMULL:
+		case AIMULW:
+			if(p->to.type != D_NONE)
+				break;
+
+		case ADIVB:
+		case ADIVL:
+		case ADIVW:
+		case AIDIVB:
+		case AIDIVL:
+		case AIDIVW:
+		case AIMULB:
+		case AMULB:
+		case AMULL:
+		case AMULW:
+
+		case AROLB:
+		case AROLL:
+		case AROLW:
+		case ARORB:
+		case ARORL:
+		case ARORW:
+		case ASALB:
+		case ASALL:
+		case ASALW:
+		case ASARB:
+		case ASARL:
+		case ASARW:
+		case ASHLB:
+		case ASHLL:
+		case ASHLW:
+		case ASHRB:
+		case ASHRL:
+		case ASHRW:
+
+		case AREP:
+		case AREPN:
+
+		case ACWD:
+		case ACDQ:
+
+		case AMOVSL:
+		case AFSTSW:
+			return 0;
+
+		case AMOVL:
+			if(p->to.type == v1->type)
+				goto gotit;
+			break;
+		}
+		if(copyau(&p->from, v2) ||
+		   copyau(&p->to, v2))
+			break;
+		if(copysub(&p->from, 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);
+		copysub(&p->to, v1, v2, 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->active = 0;
+	return copy1(v1, v2, r0->s1, 0);
+}
+
+int
+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("; %D rar; return 0\n", v2);
+			return 0;
+
+		case 3:	/* set */
+			if(debug['P'])
+				print("; %D set; 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("; %D used+set and f=%d; return 0\n", v2, f);
+				else
+					print("; %D used 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("; %D used+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("; %D set 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("unknown op %A\n", p->as);
+		return 2;
+
+	case ANEGB:
+	case ANEGW:
+	case ANEGL:
+	case ANOTB:
+	case ANOTW:
+	case ANOTL:
+		if(copyas(&p->to, v))
+			return 2;
+		break;
+
+	case ALEAL:	/* lhs addr, rhs store */
+		if(copyas(&p->from, v))
+			return 2;
+
+
+	case ANOP:	/* rhs store */
+	case AMOVL:
+	case AMOVBLSX:
+	case AMOVBLZX:
+	case AMOVWLSX:
+	case AMOVWLZX:
+		if(copyas(&p->to, v)) {
+			if(s != A)
+				return copysub(&p->from, v, s, 1);
+			if(copyau(&p->from, v))
+				return 4;
+			return 3;
+		}
+		goto caseread;
+
+	case AROLB:
+	case AROLL:
+	case AROLW:
+	case ARORB:
+	case ARORL:
+	case ARORW:
+	case ASALB:
+	case ASALL:
+	case ASALW:
+	case ASARB:
+	case ASARL:
+	case ASARW:
+	case ASHLB:
+	case ASHLL:
+	case ASHLW:
+	case ASHRB:
+	case ASHRL:
+	case ASHRW:
+		if(copyas(&p->to, v))
+			return 2;
+		if(copyas(&p->from, v))
+			if(p->from.type == D_CX)
+				return 2;
+		goto caseread;
+
+	case AADDB:	/* rhs rar */
+	case AADDL:
+	case AADDW:
+	case AANDB:
+	case AANDL:
+	case AANDW:
+	case ADECL:
+	case ADECW:
+	case AINCL:
+	case AINCW:
+	case ASUBB:
+	case ASUBL:
+	case ASUBW:
+	case AORB:
+	case AORL:
+	case AORW:
+	case AXORB:
+	case AXORL:
+	case AXORW:
+	case AMOVB:
+	case AMOVW:
+
+	case AFMOVB:
+	case AFMOVBP:
+	case AFMOVD:
+	case AFMOVDP:
+	case AFMOVF:
+	case AFMOVFP:
+	case AFMOVL:
+	case AFMOVLP:
+	case AFMOVV:
+	case AFMOVVP:
+	case AFMOVW:
+	case AFMOVWP:
+	case AFMOVX:
+	case AFMOVXP:
+	case AFADDDP:
+	case AFADDW:
+	case AFADDL:
+	case AFADDF:
+	case AFADDD:
+	case AFMULDP:
+	case AFMULW:
+	case AFMULL:
+	case AFMULF:
+	case AFMULD:
+	case AFSUBDP:
+	case AFSUBW:
+	case AFSUBL:
+	case AFSUBF:
+	case AFSUBD:
+	case AFSUBRDP:
+	case AFSUBRW:
+	case AFSUBRL:
+	case AFSUBRF:
+	case AFSUBRD:
+	case AFDIVDP:
+	case AFDIVW:
+	case AFDIVL:
+	case AFDIVF:
+	case AFDIVD:
+	case AFDIVRDP:
+	case AFDIVRW:
+	case AFDIVRL:
+	case AFDIVRF:
+	case AFDIVRD:
+		if(copyas(&p->to, v))
+			return 2;
+		goto caseread;
+
+	case ACMPL:	/* read only */
+	case ACMPW:
+	case ACMPB:
+
+	case AFCOMB:
+	case AFCOMBP:
+	case AFCOMD:
+	case AFCOMDP:
+	case AFCOMDPP:
+	case AFCOMF:
+	case AFCOMFP:
+	case AFCOML:
+	case AFCOMLP:
+	case AFCOMW:
+	case AFCOMWP:
+	case AFUCOM:
+	case AFUCOMP:
+	case AFUCOMPP:
+	caseread:
+		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 AJGE:	/* no reference */
+	case AJNE:
+	case AJLE:
+	case AJEQ:
+	case AJHI:
+	case AJLS:
+	case AJMI:
+	case AJPL:
+	case AJGT:
+	case AJLT:
+	case AJCC:
+	case AJCS:
+
+	case AADJSP:
+	case AFLDZ:
+	case AWAIT:
+		break;
+
+	case AIMULL:
+	case AIMULW:
+		if(p->to.type != D_NONE) {
+			if(copyas(&p->to, v))
+				return 2;
+			goto caseread;
+		}
+
+	case ADIVB:
+	case ADIVL:
+	case ADIVW:
+	case AIDIVB:
+	case AIDIVL:
+	case AIDIVW:
+	case AIMULB:
+	case AMULB:
+	case AMULL:
+	case AMULW:
+
+	case ACWD:
+	case ACDQ:
+		if(v->type == D_AX || v->type == D_DX)
+			return 2;
+		goto caseread;
+
+	case AMOVSL:
+	case AREP:
+	case AREPN:
+		if(v->type == D_CX || v->type == D_DI || v->type == D_SI)
+			return 2;
+		goto caseread;
+
+	case AFSTSW:
+		if(v->type == D_AX)
+			return 2;
+		goto caseread;
+
+	case AJMP:	/* 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 == REGRET)
+			return 2;
+		if(s != A)
+			return 1;
+		return 3;
+
+	case ACALL:	/* funny */
+		if(REGARG && v->type == REGARG)
+			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;
+	}
+	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))
+		return 1;
+	if(v->type == D_AUTO || v->type == D_PARAM)
+		if(v->offset == a->offset)
+			return 1;
+	return 0;
+}
+
+/*
+ * either direct or indirect
+ */
+int
+copyau(Adr *a, Adr *v)
+{
+
+	if(copyas(a, v))
+		return 1;
+	if(regtyp(v)) {
+		if(a->type-D_INDIR == v->type)
+			return 1;
+		if(a->index == v->type)
+			return 1;
+	}
+	return 0;
+}
+
+/*
+ * substitute s for v in a
+ * return failure to substitute
+ */
+int
+copysub(Adr *a, Adr *v, Adr *s, int f)
+{
+	int t;
+
+	if(copyas(a, v)) {
+		t = s->type;
+		if(t >= D_AX && t <= D_DI) {
+			if(f)
+				a->type = t;
+		}
+		return 0;
+	}
+	if(regtyp(v)) {
+		t = v->type;
+		if(a->type == t+D_INDIR) {
+			if(s->type == D_BP && a->index != D_NONE)
+				return 1;	/* can't use BP-base with index */
+			if(f)
+				a->type = s->type+D_INDIR;
+//			return 0;
+		}
+		if(a->index == t) {
+			if(f)
+				a->index = s->type;
+			return 0;
+		}
+		return 0;
+	}
+	return 0;
+}