cmd/6c, cmd/8c: add fixjmp step to regopt.

The fixjmp step eliminates redundant chains of JMP
instructions that are produced by the compiler during
code generation.

It is already implemented in gc, and can be adapted to 6c/8c with
the exception that JMPs refer to destination by pc instead of by
pointer. The algorithm is modified to operate on Regs instead of Progs
for this reason. The pcs are already restored later by regopt.

R=goalng-dev, rsc
CC=golang-dev
https://codereview.appspot.com/6865046

2 files changed, 156 insertions, 2 deletions

diff --git a/src/cmd/8c/list.c b/src/cmd/8c/list.c
index c422905cd..16a41ac36 100644
--- a/src/cmd/8c/list.c
+++ b/src/cmd/8c/list.c
@@ -139,7 +139,7 @@ Dconv(Fmt *fp)
 		break;
 
 	case D_BRANCH:
-		sprint(str, "%d(PC)", a->offset-pc);
+		sprint(str, "%d", a->offset);
 		break;
 
 	case D_EXTERN:
@@ -264,6 +264,15 @@ char*	regstr[] =
 	"TR6",
 	"TR7",
 
+	"X0",	/*[D_X0]*/
+	"X1",
+	"X2",
+	"X3",
+	"X4",
+	"X5",
+	"X6",
+	"X7",
+
 	"NONE",	/*[D_NONE]*/
 };
 
diff --git a/src/cmd/8c/reg.c b/src/cmd/8c/reg.c
index 7a7bfe77b..6c87d70a5 100644
--- a/src/cmd/8c/reg.c
+++ b/src/cmd/8c/reg.c
@@ -30,6 +30,8 @@
 
 #include "gc.h"
 
+static	void	fixjmp(Reg*);
+
 Reg*
 rega(void)
 {
@@ -148,7 +150,6 @@ regopt(Prog *p)
 			r->p1 = R;
 			r1->s1 = R;
 		}
-
 		bit = mkvar(r, &p->from);
 		if(bany(&bit))
 		switch(p->as) {
@@ -376,6 +377,12 @@ regopt(Prog *p)
 	}
 
 	/*
+	 * pass 2.1
+	 * fix jumps
+	 */
+	fixjmp(firstr);
+
+	/*
 	 * pass 2.5
 	 * find looping structure
 	 */
@@ -547,6 +554,13 @@ brk:
 	if(!debug['R'] || debug['P'])
 		peep();
 
+	if(debug['R'] && debug['v']) {
+		print("after pass 7 (peep)\n");
+		for(r=firstr; r; r=r->link)
+			print("%04d %P\n", r->pc, r->prog);
+		print("\n");
+	}
+
 	/*
 	 * pass 8
 	 * recalculate pc
@@ -600,6 +614,14 @@ brk:
 		while(p->link && p->link->as == ANOP)
 			p->link = p->link->link;
 	}
+
+	if(debug['R'] && debug['v']) {
+		print("after pass 8 (fixup pc)\n");
+		for(p1=firstr->prog; p1!=P; p1=p1->link)
+			print("%P\n", p1);
+		print("\n");
+	}
+
 	if(r1 != R) {
 		r1->link = freer;
 		freer = firstr;
@@ -1289,3 +1311,126 @@ BtoR(int32 b)
 		return 0;
 	return bitno(b) + D_AX;
 }
+
+/* what instruction does a JMP to p eventually land on? */
+static Reg*
+chasejmp(Reg *r, int *jmploop)
+{
+	int n;
+
+	n = 0;
+	for(; r; r=r->s2) {
+		if(r->prog->as != AJMP || r->prog->to.type != D_BRANCH)
+			break;
+		if(++n > 10) {
+			*jmploop = 1;
+			break;
+		}
+	}
+	return r;
+}
+
+/* mark all code reachable from firstp as alive */
+static void
+mark(Reg *firstr)
+{
+	Reg *r;
+	Prog *p;
+
+	for(r=firstr; r; r=r->link) {
+		if(r->active)
+			break;
+		r->active = 1;
+		p = r->prog;
+		if(p->as != ACALL && p->to.type == D_BRANCH)
+			mark(r->s2);
+		if(p->as == AJMP || p->as == ARET || p->as == AUNDEF)
+			break;
+	}
+}
+
+/*
+ * the code generator depends on being able to write out JMP
+ * instructions that it can jump to now but fill in later.
+ * the linker will resolve them nicely, but they make the code
+ * longer and more difficult to follow during debugging.
+ * remove them.
+ */
+static void
+fixjmp(Reg *firstr)
+{
+	int jmploop;
+	Reg *r;
+	Prog *p;
+
+	if(debug['R'] && debug['v'])
+		print("\nfixjmp\n");
+
+	// pass 1: resolve jump to AJMP, mark all code as dead.
+	jmploop = 0;
+	for(r=firstr; r; r=r->link) {
+		p = r->prog;
+		if(debug['R'] && debug['v'])
+			print("%04d %P\n", r->pc, p);
+		if(p->as != ACALL && p->to.type == D_BRANCH && r->s2 && r->s2->prog->as == AJMP) {
+			r->s2 = chasejmp(r->s2, &jmploop);
+			p->to.offset = r->s2->pc;
+			if(debug['R'] && debug['v'])
+				print("->%P\n", p);
+		}
+		r->active = 0;
+	}
+	if(debug['R'] && debug['v'])
+		print("\n");
+
+	// pass 2: mark all reachable code alive
+	mark(firstr);
+
+	// pass 3: delete dead code (mostly JMPs).
+	for(r=firstr; r; r=r->link) {
+		if(!r->active) {
+			p = r->prog;
+			if(p->link == P && p->as == ARET && r->p1 && r->p1->prog->as != ARET) {
+				// This is the final ARET, and the code so far doesn't have one.
+				// Let it stay.
+			} else {
+				if(debug['R'] && debug['v'])
+					print("del %04d %P\n", r->pc, p);
+				p->as = ANOP;
+			}
+		}
+	}
+
+	// pass 4: elide JMP to next instruction.
+	// only safe if there are no jumps to JMPs anymore.
+	if(!jmploop) {
+		for(r=firstr; r; r=r->link) {
+			p = r->prog;
+			if(p->as == AJMP && p->to.type == D_BRANCH && r->s2 == r->link) {
+				if(debug['R'] && debug['v'])
+					print("del %04d %P\n", r->pc, p);
+				p->as = ANOP;
+			}
+		}
+	}
+
+	// fix back pointers.
+	for(r=firstr; r; r=r->link) {
+		r->p2 = R;
+		r->p2link = R;
+	}
+	for(r=firstr; r; r=r->link) {
+		if(r->s2) {
+			r->p2link = r->s2->p2;
+			r->s2->p2 = r;
+		}
+	}
+
+	if(debug['R'] && debug['v']) {
+		print("\n");
+		for(r=firstr; r; r=r->link)
+			print("%04d %P\n", r->pc, r->prog);
+		print("\n");
+	}
+}
+