qbe

commit ad012e9d558138b61881156ab8b31e74cd759825
parent 7dc3e5dcf60d1995857c85773cd15c9904ec9abd
Author: Quentin Carbonneaux <quentin.carbonneaux@yale.edu>
Date:   Fri,  7 Aug 2015 14:27:20 -0400

implement smarter compare+branch

Diffstat:
M
lisc/isel.c
 | 
129
+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++--------------
M
lisc/lisc.h
 | 
4
++++
M
lisc/parse.c
 | 
29
+++++++++++++++++++++--------

3 files changed, 132 insertions(+), 30 deletions(-)
diff --git a/lisc/isel.c b/lisc/isel.c
@@ -40,12 +40,53 @@ newtmp(int type, Fn *fn)
 }
 
 static int
+cneg(int cmp)
+{
+	switch (cmp) {
+	default:   diag("cneg: unhandled comparison");
+	case Ceq:  return Cne;
+	case Csle: return Csgt;
+	case Cslt: return Csge;
+	case Csgt: return Csle;
+	case Csge: return Cslt;
+	case Cne:  return Ceq;
+	}
+}
+
+static int
 islong(Ref r, Fn *fn)
 {
 	return rtype(r) == RTmp && fn->tmp[r.val].type == TLong;
 }
 
 static void
+selcmp(Ref arg[2], Fn *fn)
+{
+	Ref r;
+	int t;
+
+	t = -1;
+	if (rtype(arg[0]) == RCon) {
+		r = arg[1];
+		arg[1] = arg[0];
+		arg[0] = r;
+		if (rtype(r) == RCon) {
+			/* todo, use the constant
+			 * size to dimension the
+			 * constant */
+			t = newtmp(TWord, fn);
+			arg[0] = TMP(t);
+		}
+	}
+	if (islong(arg[0], fn) || islong(arg[1], fn))
+		emit(OXCmpl, R, arg[1], arg[0]);
+	else
+		emit(OXCmpw, R, arg[1], arg[0]);
+	if (t != -1)
+		emit(OCopy, TMP(t), r, R);
+}
+
+static void
 sel(Ins i, Fn *fn)
 {
 	Ref r0, r1, ra, rd;
@@ -92,35 +133,78 @@ sel(Ins i, Fn *fn)
 		break;
 	default:
 		if (OCmp <= i.op && i.op <= OCmp1) {
-			t = -1;
-			r0 = i.arg[0];
 			c = i.op - OCmp;
-			if (rtype(i.arg[0]) == RCon) {
-				if (rtype(i.arg[1]) == RCon) {
-					/* todo, use the constant
-					 * size to dimension the
-					 * constant */
-					t = newtmp(TWord, fn);
-					r0 = TMP(t);
-				} else {
-					r0 = i.arg[1];
-					i.arg[1] = i.arg[0];
-					c = COP(c);
-				}
-			}
+			if (rtype(i.arg[0]) == RCon)
+				c = COP(c);
 			emit(OXSet+c, i.to, R, R);
-			if (islong(r0, fn) || islong(i.arg[1], fn))
-				emit(OXCmpl, R, i.arg[1], r0);
-			else
-				emit(OXCmpw, R, i.arg[1], r0);
-			if (t != -1)
-				emit(OCopy, r0, i.arg[0], R);
+			selcmp(i.arg, fn);
 			break;
 		}
 		diag("isel: non-exhaustive implementation");
 	}
 }
 
+static Ins *
+flagi(Ins *i0, Ins *i)
+{
+	while (i>i0)
+		switch ((--i)->op) {
+		default:
+			return i;
+		case OCopy:
+		case OStore:
+		case OLoad:;
+		}
+	return 0;
+}
+
+static Ins *
+seljmp(Blk *b, Fn *fn)
+{
+	Ref r;
+	int c;
+	Ins *fi;
+
+	fi = &b->ins[b->nins];
+	if (b->jmp.type != JJez)
+		return fi;
+	r = b->jmp.arg;
+	b->jmp.arg = R;
+	assert(!req(r, R));
+	if (rtype(r) == RCon) {
+		b->jmp.type = JJmp;
+		if (!req(r, CON_Z))
+			b->s1 = b->s2;
+		b->s2 = 0;
+		return fi;
+	}
+	fi = flagi(b->ins, fi);
+	if (fi && req(fi->to, r)) {
+		assert(1 == fn->tmp[r.val].nuse);
+		if (fn->tmp[r.val].nuse == 1
+		&& OCmp <= fi->op && fi->op <= OCmp1) {
+			c = fi->op - OCmp;
+			if (rtype(fi->arg[0]) == RCon)
+				c = COP(c);
+			b->jmp.type = JXJc + cneg(c);
+			selcmp(fi->arg, fn);
+			return fi;
+		}
+		/* what if it is a comparison
+		 * that is used more than once?
+		 * !!!
+		 */
+		b->jmp.type = JXJc + Ceq;
+		return fi+1;
+	}
+	if (islong(r, fn))
+		emit(OXCmpl, R, CON_Z, r);
+	else
+		emit(OXCmpw, R, CON_Z, r);
+	b->jmp.type = JXJc + Ceq;
+	return &b->ins[b->nins];
+}
+
 /* instruction selection
  * requires use counts (as given by parsing)
  */
@@ -133,7 +217,8 @@ isel(Fn *fn)
 
 	for (b=fn->start; b; b=b->link) {
 		curi = &insb[NIns];
-		for (i=&b->ins[b->nins]; i!=b->ins;) {
+		i = seljmp(b, fn);
+		while (i>b->ins) {
 			sel(*--i, fn);
 		}
 		nins = &insb[NIns] - curi;
diff --git a/lisc/lisc.h b/lisc/lisc.h
@@ -97,6 +97,7 @@ enum {
 #define R        (Ref){0, 0}
 #define TMP(x)   (Ref){RTmp, x}
 #define CON(x)   (Ref){RCon, x}
+#define CON_Z    CON(0)          /* reserved zero constant */
 #define SLOT(x)  (Ref){RSlot, x}
 #define REG(x)   (Ref){RReg, x}
 
@@ -146,6 +147,9 @@ enum {
 	JRet,
 	JJmp,
 	JJez,
+	JXJc,
+	JXJc1 = JXJc + NCmp-1,
+	JLast
 };
 
 struct OpDesc {
diff --git a/lisc/parse.c b/lisc/parse.c
@@ -80,7 +80,7 @@ static struct {
 static int lnum;
 
 static Tmp tmp[NTmp];
-static Con con[NCon];
+static Con con[NCon] = {[0] = {.type = CNum}};
 static int ntmp;
 static int ncon;
 static Phi **plink;
@@ -261,10 +261,11 @@ tmpref(char *v, int use)
 
 	for (t=0; t<ntmp; t++)
 		if (strcmp(v, tmp[t].name) == 0)
-			return TMP(t);
+			goto Found;
 	if (ntmp++ >= NTmp)
 		err("too many temporaries");
 	strcpy(tmp[t].name, v);
+Found:
 	tmp[t].ndef += !use;
 	tmp[t].nuse += use;
 	return TMP(t);
@@ -513,8 +514,8 @@ parsefn(FILE *f)
 		bmap[i] = 0;
 	for (i=0; i<NTmp; i++)
 		tmp[i] = (Tmp){.name = ""};
-	ntmp = 1;
-	ncon = 0;
+	ntmp = 1; /* first tmp is invalid */
+	ncon = 1; /* first con in 0 */
 	curi = insb;
 	curb = 0;
 	lnum = 1;
@@ -580,6 +581,15 @@ printref(Ref r, Fn *fn, FILE *f)
 void
 printfn(Fn *fn, FILE *f)
 {
+	static char *jtoa[JLast] = {
+		[JJez]      = "jez",
+		[JXJc+Ceq]  = "xjeq",
+		[JXJc+Csle] = "xjsle",
+		[JXJc+Cslt] = "xjslt",
+		[JXJc+Csgt] = "xjsgt",
+		[JXJc+Csge] = "xjsge",
+		[JXJc+Cne]  = "xjne",
+	};
 	Blk *b;
 	Phi *p;
 	Ins *i;
@@ -630,10 +640,13 @@ printfn(Fn *fn, FILE *f)
 			if (b->s1 != b->link)
 				fprintf(f, "\tjmp @%s\n", b->s1->name);
 			break;
-		case JJez:
-			fprintf(f, "\tjez ");
-			printref(b->jmp.arg, fn, f);
-			fprintf(f, ", @%s, @%s\n", b->s1->name, b->s2->name);
+		default:
+			fprintf(f, "\t%s ", jtoa[b->jmp.type]);
+			if (b->jmp.type == JJez) {
+				printref(b->jmp.arg, fn, f);
+				fprintf(f, ", ");
+			}
+			fprintf(f, "@%s, @%s\n", b->s1->name, b->s2->name);
 			break;
 		}
 	}