start work on comparisons

There are two things I overlooked so far.

1. Binary instructions like cmp that do not have a result
   in registers need the size suffix sometimes, for example
   when comparing a spill location with a constant.

2. The register allocator needs to be adapted to support the
   comparison instruction: it is not possible to compare two
   spill locations without using a register.

6 files changed, 109 insertions, 22 deletions

diff --git a/lisc/emit.c b/lisc/emit.c
index a014727..1025ace 100644
--- a/lisc/emit.c
+++ b/lisc/emit.c
@@ -40,6 +40,36 @@ static char *rtoa[] = {
 	[R15D] = "r15d",
 };
 
+static char *rbtoa[] = {
+	[RXX] = "OH GOD!",
+
+
+	[RAX] = "al",
+	[RCX] = "cl",
+	[RDX] = "dl",
+	[RSI] = "sil",
+	[RDI] = "dil",
+	[R8] = "r8b",
+	[R9] = "r9b",
+	[R10] = "r10b",
+	[R11] = "r11b",
+
+	[RBX] = "bl",
+	[R12] = "r12b",
+	[R13] = "r13b",
+	[R14] = "r14b",
+	[R15] = "r15b",
+
+	[RBP] = "bpl",
+	[RSP] = "spl",
+
+};
+
+static char *ctoa[NCmp] = {
+	[Ceq] = "e",
+	[Csle] = "le",
+};
+
 static void
 eref(Ref r, Fn *fn, FILE *f)
 {
@@ -87,7 +117,7 @@ eop(char *op, Ref a, Ref b, Fn *fn, FILE *f)
 static void
 eins(Ins i, Fn *fn, FILE *f)
 {
-	static char *opi[] = {
+	static char *otoa[OLast] = {
 		[OAdd] = "add",
 		[OSub] = "sub",
 	};
@@ -103,7 +133,7 @@ eins(Ins i, Fn *fn, FILE *f)
 		}
 		if (!req(i.to, i.arg[0]))
 			eop("mov", i.arg[0], i.to, fn, f);
-		eop(opi[i.op], i.arg[1], i.to, fn, f);
+		eop(otoa[i.op], i.arg[1], i.to, fn, f);
 		break;
 	case OStore:
 		i.to = i.arg[1];
@@ -127,9 +157,19 @@ eins(Ins i, Fn *fn, FILE *f)
 	case OXDiv:
 		eop("idiv", i.arg[0], R, fn, f);
 		break;
+	case OXCmp:
+		eop("cmp", i.arg[0], i.arg[1], fn, f);
+		break;
 	case ONop:
 		break;
 	default:
+		if (OXSet <= i.op && i.op <= OXSet1) {
+			eop("mov $0,", i.to, R, fn, f);
+			fprintf(f, "\tset%s %%%s\n",
+				ctoa[i.op-OXSet],
+				rbtoa[BASE(i.to.val)]);
+			break;
+		}
 		diag("emit: unhandled instruction (3)");
 	}
 }
diff --git a/lisc/isel.c b/lisc/isel.c
index f08288d..6fdf5ff 100644
--- a/lisc/isel.c
+++ b/lisc/isel.c
@@ -40,15 +40,16 @@ newtmp(int type, Fn *fn)
 }
 
 static void
-sel(Ins *i, Fn *fn)
+sel(Ins i, Fn *fn)
 {
 	Ref r0, r1, ra, rd;
-	int t;
+	int t, ty, c;
 
-	switch (i->op) {
+	switch (i.op) {
 	case ODiv:
 	case ORem:
-		switch (fn->tmp[i->to.val].type) {
+		ty = fn->tmp[i.to.val].type;
+		switch (ty) {
 		default:
 			diag("isel: invalid division");
 		case TWord:
@@ -60,35 +61,42 @@ sel(Ins *i, Fn *fn)
 			rd = REG(RDX);
 			break;
 		}
-		r0 = i->op == ODiv ? ra : rd;
-		r1 = i->op == ODiv ? rd : ra;
-		emit(OCopy, i->to, r0, R);
+		r0 = i.op == ODiv ? ra : rd;
+		r1 = i.op == ODiv ? rd : ra;
+		emit(OCopy, i.to, r0, R);
 		emit(OCopy, R, r1, R);
-		if (rtype(i->arg[1]) == RCon) {
+		if (rtype(i.arg[1]) == RCon) {
 			/* immediates not allowed for
 			 * divisions in x86
 			 */
-			t = newtmp(fn->tmp[i->to.val].type, fn);
+			t = newtmp(ty, fn);
 			r0 = TMP(t);
 		} else
-			r0 = i->arg[1];
+			r0 = i.arg[1];
 		emit(OXDiv, R, r0, R);
 		emit(OSign, rd, ra, R);
-		emit(OCopy, ra, i->arg[0], R);
-		if (rtype(i->arg[1]) == RCon)
-			emit(OCopy, r0, i->arg[1], R);
+		emit(OCopy, ra, i.arg[0], R);
+		if (rtype(i.arg[1]) == RCon)
+			emit(OCopy, r0, i.arg[1], R);
 		break;
 	case OAdd:
 	case OSub:
 	case OCopy:
-		emit(i->op, i->to, i->arg[0], i->arg[1]);
+		emit(i.op, i.to, i.arg[0], i.arg[1]);
 		break;
 	default:
+		if (OCmp <= i.op && i.op <= OCmp1) {
+			c = i.op - OCmp;
+			emit(OXSet+c, i.to, R, R);
+			emit(OXCmp, R, i.arg[0], i.arg[1]);
+			break;
+		}
 		diag("isel: non-exhaustive implementation");
 	}
 }
 
 /* instruction selection
+ * requires use counts (as given by parsing)
  */
 void
 isel(Fn *fn)
@@ -100,7 +108,7 @@ isel(Fn *fn)
 	for (b=fn->start; b; b=b->link) {
 		curi = &insb[NIns];
 		for (i=&b->ins[b->nins]; i!=b->ins;) {
-			sel(--i, fn);
+			sel(*--i, fn);
 		}
 		nins = &insb[NIns] - curi;
 		free(b->ins);
diff --git a/lisc/lisc.h b/lisc/lisc.h
index 46fb163..1291fea 100644
--- a/lisc/lisc.h
+++ b/lisc/lisc.h
@@ -106,12 +106,20 @@ static inline int rtype(Ref r)
 { return req(r, R) ? -1 : r.type; }
 
 enum {
-	OXXX = 0,
+	Ceq,
+	Csle,
+	NCmp,
+};
+
+enum {
+	OXXX,
 	/* public instruction */
 	OAdd,
 	OSub,
 	ODiv,
 	ORem,
+	OCmp,
+	OCmp1 = OCmp + NCmp-1,
 	OStore,
 	OLoad,
 	/* reserved instructions */
@@ -120,6 +128,9 @@ enum {
 	OSwap,
 	OSign,
 	OXDiv,
+	OXCmp,
+	OXSet,
+	OXSet1 = OXSet + NCmp-1,
 	OLast
 };
 
diff --git a/lisc/parse.c b/lisc/parse.c
index 50e5d0a..d504113 100644
--- a/lisc/parse.c
+++ b/lisc/parse.c
@@ -23,6 +23,12 @@ OpDesc opdesc[OLast] = {
 	[OSwap]   = { "swap",  2, T },
 	[OSign]   = { "sign",  1, U },
 	[OXDiv]   = { "xdiv",  1, U },
+	[OXCmp]   = { "xcmp",  2, U },
+
+	[OCmp+Ceq]   = { "ceq",    2, U },
+	[OCmp+Csle]  = { "csle",   2, U },
+	[OXSet+Ceq]  = { "xsete",  0, U },
+	[OXSet+Csle] = { "xsetle", 0, U },
 };
 
 typedef enum {
@@ -40,6 +46,8 @@ typedef enum {
 	TSub,
 	TDiv,
 	TRem,
+	TCeq,
+	TCsle,
 	TPhi,
 	TJmp,
 	TJez,
@@ -123,6 +131,8 @@ lex()
 		{ "sub", TSub },
 		{ "div", TDiv },
 		{ "rem", TRem },
+		{ "ceq", TCeq },
+		{ "csle", TCsle },
 		{ "phi", TPhi },
 		{ "jmp", TJmp },
 		{ "jez", TJez },
@@ -242,7 +252,7 @@ blocka()
 }
 
 static Ref
-tmpref(char *v)
+tmpref(char *v, int use)
 {
 	int t;
 
@@ -252,6 +262,8 @@ tmpref(char *v)
 	if (ntmp++ >= NTmp)
 		err("too many temporaries");
 	strcpy(tmp[t].name, v);
+	tmp[t].ndef += !use;
+	tmp[t].nuse += use;
 	return TMP(t);
 }
 
@@ -263,7 +275,7 @@ parseref()
 
 	switch (next()) {
 	case TTmp:
-		return tmpref(tokval.str);
+		return tmpref(tokval.str, 1);
 	case TNum:
 		c = (Con){.type = CNum, .val = tokval.num};
 		strcpy(c.label, "");
@@ -400,7 +412,7 @@ parseline(PState ps)
 		closeblk();
 		return PLbl;
 	}
-	r = tmpref(tokval.str);
+	r = tmpref(tokval.str, 0);
 	expect(TEq);
 	switch (next()) {
 	case TW:
@@ -428,6 +440,12 @@ parseline(PState ps)
 	case TRem:
 		op = ORem;
 		break;
+	case TCeq:
+		op = OCmp+Ceq;
+		break;
+	case TCsle:
+		op = OCmp+Csle;
+		break;
 	case TPhi:
 		if (ps != PPhi)
 			err("unexpected phi instruction");
diff --git a/lisc/spill.c b/lisc/spill.c
index 30adb35..c4ca7a8 100644
--- a/lisc/spill.c
+++ b/lisc/spill.c
@@ -38,7 +38,7 @@ tmpuse(Ref r, int use, int loop, Fn *fn)
 		return;
 	t = &fn->tmp[r.val];
 	t->nuse += use;
-	t->ndef += 1 - use;
+	t->ndef += !use;
 	t->cost += loop;
 }
 
diff --git a/lisc/test/cup.ssa b/lisc/test/cup.ssa
new file mode 100644
index 0000000..64f2ab4
--- /dev/null
+++ b/lisc/test/cup.ssa
@@ -0,0 +1,10 @@
+# counts up
+
+@start
+@loop
+	%n0  =w phi @start -1988, @loop %n1
+	%n1  =w add 1, %n0
+	%cmp =w csle %n1, 1000
+	jez %cmp, @end, @loop
+@end
+	ret