major lifting: get rid of RReg

I've been septic since I introduced it, this commit
proves that it costs more than it helps.  I've also fixed
a bad bug in rega() where I alloc'ed the wrong size for
internal arrays.  Enums now have names so I can use them
to cast in gdb to get the name corresponding to a constant.

8 files changed, 97 insertions, 142 deletions

diff --git a/lisc/Makefile b/lisc/Makefile
index 444485c..799ec93 100644
--- a/lisc/Makefile
+++ b/lisc/Makefile
@@ -1,7 +1,7 @@
 BIN = lisc
 OBJ = parse.o ssa.o live.o isel.o spill.o rega.o emit.o main.o
 
-CFLAGS = -Wall -Wextra -std=c11 -g -pedantic
+CFLAGS = -Wall -Wextra -std=c99 -g -pedantic
 
 $(BIN): $(OBJ)
 	$(CC) $(LDFLAGS) $(OBJ) -o $@
diff --git a/lisc/emit.c b/lisc/emit.c
index a08ad52..76ce82c 100644
--- a/lisc/emit.c
+++ b/lisc/emit.c
@@ -75,7 +75,10 @@ static void
 eref(Ref r, Fn *fn, FILE *f)
 {
 	switch (rtype(r)) {
-	case RReg:
+	default:
+		diag("emitref: invalid reference");
+	case RTmp:
+		assert(r.val < Tmp0);
 		fprintf(f, "%%%s", rtoa(r.val));
 		break;
 	case RSlot:
@@ -85,8 +88,6 @@ eref(Ref r, Fn *fn, FILE *f)
 		fprintf(f, "$");
 		econ(&fn->con[r.val], f);
 		break;
-	default:
-		diag("emitref: invalid reference");
 	}
 }
 
@@ -102,7 +103,7 @@ emem(Ref r, Fn *fn, FILE *f)
 	case RCon:
 		econ(&fn->con[r.val], f);
 		break;
-	case RReg:
+	case RTmp:
 		assert(r.val < EAX);
 		fprintf(f, "(");
 		eref(r, fn, f);
@@ -178,7 +179,8 @@ eins(Ins i, Fn *fn, FILE *f)
 	case OStores:
 	case OStoreb:
 		fprintf(f, "\tmov%s ", stoa[i.op - OStorel]);
-		if (rtype(i.arg[0]) == RReg) {
+		if (rtype(i.arg[0]) == RTmp) {
+			assert(i.arg[0].val < Tmp0);
 			reg = RBASE(i.arg[0].val);
 			fprintf(f, "%%%s", rsub[reg][i.op - OStorel]);
 		} else
@@ -203,17 +205,17 @@ eins(Ins i, Fn *fn, FILE *f)
 		fprintf(f, "\n");
 		break;
 	case OAlloc:
-		eop("sub", i.arg[0], REG(RSP), fn, f);
+		eop("sub", i.arg[0], TMP(RSP), fn, f);
 		if (!req(i.to, R))
-			eop("mov", REG(RSP), i.to, fn ,f);
+			eop("mov", TMP(RSP), i.to, fn ,f);
 		break;
 	case OSwap:
 		eop("xchg", i.arg[0], i.arg[1], fn, f);
 		break;
 	case OSign:
-		if (req(i.to, REG(RDX)) && req(i.arg[0], REG(RAX)))
+		if (req(i.to, TMP(RDX)) && req(i.arg[0], TMP(RAX)))
 			fprintf(f, "\tcqto\n");
-		else if (req(i.to, REG(EDX)) && req(i.arg[0], REG(EAX)))
+		else if (req(i.to, TMP(EDX)) && req(i.arg[0], TMP(EAX)))
 			fprintf(f, "\tcltd\n");
 		else
 			diag("emit: unhandled instruction (2)");
diff --git a/lisc/isel.c b/lisc/isel.c
index 5b83081..a9e3ee2 100644
--- a/lisc/isel.c
+++ b/lisc/isel.c
@@ -122,12 +122,12 @@ sel(Ins i, Fn *fn)
 		default:
 			diag("isel: invalid division");
 		case TWord:
-			ra = REG(EAX);
-			rd = REG(EDX);
+			ra = TMP(EAX);
+			rd = TMP(EDX);
 			break;
 		case TLong:
-			ra = REG(RAX);
-			rd = REG(RDX);
+			ra = TMP(RAX);
+			rd = TMP(RDX);
 			break;
 		}
 		r0 = i.op == ODiv ? ra : rd;
@@ -230,6 +230,7 @@ flagi(Ins *i0, Ins *i)
 			return 0;
 		case OAdd:  /* flag-setting */
 		case OSub:
+		case OAnd:
 			return i;
 		case OCopy: /* flag-transparent */
 		case OStorel:
diff --git a/lisc/lisc.h b/lisc/lisc.h
index abf9c1f..3ae5c56 100644
--- a/lisc/lisc.h
+++ b/lisc/lisc.h
@@ -18,7 +18,7 @@ typedef struct Fn Fn;
 
 typedef enum { U, F, T } B3;
 
-enum {
+enum Reg {
 	RXX,
 
 	RAX, /* caller-save */
@@ -56,8 +56,9 @@ enum {
 	R14D,
 	R15D,
 
-	// NReg = R15 - RAX + 1
-	NReg = 3 /* for test purposes */
+	Tmp0, /* first non-reg temporary */
+
+	NReg = RDX - RAX + 1
 };
 
 #define RWORD(r) (r + (EAX-RAX))
@@ -90,7 +91,6 @@ enum {
 	RTmp,
 	RCon,
 	RSlot,
-	RReg,
 	NRef = (1<<14) - 1
 };
 
@@ -99,14 +99,13 @@ enum {
 #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}
 
 static inline int req(Ref a, Ref b)
 { return a.type == b.type && a.val == b.val; }
 static inline int rtype(Ref r)
 { return req(r, R) ? -1 : r.type; }
 
-enum {
+enum Cmp {
 	Ceq,
 	Csle,
 	Cslt,
@@ -118,7 +117,7 @@ enum {
 
 #define COP(c) (c==Ceq||c==Cne ? c : NCmp-1 - c)
 
-enum {
+enum Op {
 	OXXX,
 
 	/* public instructions */
@@ -154,7 +153,7 @@ enum {
 	NOp
 };
 
-enum {
+enum Jmp {
 	JXXX,
 	JRet,
 	JJmp,
@@ -211,6 +210,7 @@ struct Tmp {
 		TUndef,
 		TWord,
 		TLong,
+		TReg,
 	} type;
 	char name[NString];
 	uint ndef, nuse;
diff --git a/lisc/live.c b/lisc/live.c
index aec7701..64fcf6a 100644
--- a/lisc/live.c
+++ b/lisc/live.c
@@ -1,24 +1,14 @@
 #include "lisc.h"
 
 static void
-bset(Ref r, Blk *b, Bits *rb, int *nlv)
+bset(Ref r, Blk *b, int *nlv)
 {
-	Bits *bs;
-
-	switch (rtype(r)) {
-	case RTmp:
-		bs = &b->in;
-		BSET(b->gen, r.val);
-		break;
-	case RReg:
-		bs = rb;
-		break;
-	default:
+	if (rtype(r) != RTmp)
 		return;
-	}
-	if (!BGET(*bs, r.val)) {
+	BSET(b->gen, r.val);
+	if (!BGET(b->in, r.val)) {
 		++*nlv;
-		BSET(*bs, r.val);
+		BSET(b->in, r.val);
 	}
 }
 
@@ -33,7 +23,7 @@ filllive(Fn *f)
 	Phi *p;
 	int z, n, chg, nlv;
 	uint a;
-	Bits tb, rb;
+	Bits tb;
 
 	assert(f->ntmp <= NBit*BITS);
 	for (b=f->start; b; b=b->link) {
@@ -56,28 +46,18 @@ Again:
 		chg |= memcmp(&b->out, &tb, sizeof(Bits));
 
 		b->in = b->out;
-		rb = (Bits){{0}};
 		nlv = bcnt(&b->in);
-		bset(b->jmp.arg, b, &rb, &nlv);
+		bset(b->jmp.arg, b, &nlv);
 		b->nlive = nlv;
 		for (i=&b->ins[b->nins]; i!=b->ins;) {
 			i--;
-			switch (rtype(i->to)) {
-			default:
-				diag("live: unhandled destination");
-			case RTmp:
+			if (!req(i->to, R)) {
+				assert(rtype(i->to) == RTmp);
 				nlv -= BGET(b->in, i->to.val);
 				BCLR(b->in, i->to.val);
-				break;
-			case RReg:
-				nlv -= BGET(rb, i->to.val);
-				BCLR(rb, i->to.val);
-				break;
-			case -1:
-				break;
 			}
-			bset(i->arg[0], b, &rb, &nlv);
-			bset(i->arg[1], b, &rb, &nlv);
+			bset(i->arg[0], b, &nlv);
+			bset(i->arg[1], b, &nlv);
 			if (nlv > b->nlive)
 				b->nlive = nlv;
 		}
diff --git a/lisc/parse.c b/lisc/parse.c
index fc35800..5a06911 100644
--- a/lisc/parse.c
+++ b/lisc/parse.c
@@ -257,7 +257,7 @@ tmpref(char *v, int use)
 {
 	int t;
 
-	for (t=0; t<ntmp; t++)
+	for (t=Tmp0; t<ntmp; t++)
 		if (strcmp(v, tmp[t].name) == 0)
 			goto Found;
 	if (ntmp++ >= NTmp)
@@ -496,9 +496,12 @@ parsefn(FILE *f)
 	for (i=0; i<NBlk; i++)
 		bmap[i] = 0;
 	for (i=0; i<NTmp; i++)
-		tmp[i] = (Tmp){.name = ""};
-	ntmp = 1; /* first tmp is invalid */
-	ncon = 1; /* first con in 0 */
+		if (i < Tmp0)
+			tmp[i] = (Tmp){.type = TReg};
+		else
+			tmp[i] = (Tmp){.name = ""};
+	ntmp = Tmp0;
+	ncon = 1; /* first constant must be 0 */
 	curi = insb;
 	curb = 0;
 	lnum = 1;
@@ -531,11 +534,15 @@ printref(Ref r, Fn *fn, FILE *f)
 		[TUndef] = "?",
 		[TWord] = "w",
 		[TLong] = "l",
+		[TReg] = "",
 	};
 
 	switch (r.type) {
 	case RTmp:
-		fprintf(f, "%%%s", fn->tmp[r.val].name);
+		if (r.val < Tmp0)
+			fprintf(f, "R%d", r.val);
+		else
+			fprintf(f, "%%%s", fn->tmp[r.val].name);
 		return ttoa[fn->tmp[r.val].type];
 	case RCon:
 		switch (fn->con[r.val].type) {
@@ -554,9 +561,6 @@ printref(Ref r, Fn *fn, FILE *f)
 	case RSlot:
 		fprintf(f, "$%d", r.val);
 		break;
-	case RReg:
-		fprintf(f, "R%d", r.val);
-		break;
 	}
 	return "";
 }
diff --git a/lisc/rega.c b/lisc/rega.c
index ea26417..5aae3b6 100644
--- a/lisc/rega.c
+++ b/lisc/rega.c
@@ -31,13 +31,14 @@ rfind(RMap *m, int t)
 static Ref
 reg(int r, int t)
 {
+	assert(r < Tmp0);
 	switch (tmp[t].type) {
 	default:
-		assert(!"invalid temporary");
+		diag("rega: invalid temporary");
 	case TWord:
-		return REG(RWORD(r));
+		return TMP(RWORD(r));
 	case TLong:
-		return REG(r);
+		return TMP(r);
 	}
 }
 
@@ -75,6 +76,10 @@ ralloc(RMap *m, int t)
 	static int x;
 	int n, r;
 
+	if (t < Tmp0) {
+		BSET(m->br, t);
+		return TMP(t);
+	}
 	if (BGET(m->bt, t)) {
 		r = rfind(m, t);
 		assert(r != -1);
@@ -100,6 +105,12 @@ rfree(RMap *m, int t)
 {
 	int i, r;
 
+	if (t < Tmp0) {
+		t = RBASE(t);
+		assert(BGET(m->br, t));
+		BCLR(m->br, t);
+		return t;
+	}
 	if (!BGET(m->bt, t))
 		return -1;
 	for (i=0; m->t[i] != t; i++)
@@ -194,6 +205,12 @@ pmgen()
 	free(status);
 }
 
+static int
+isreg(Ref r)
+{
+	return rtype(r) == RTmp && r.val < Tmp0;
+}
+
 static Ins *
 dopm(Blk *b, Ins *i, RMap *m)
 {
@@ -203,7 +220,7 @@ dopm(Blk *b, Ins *i, RMap *m)
 
 	npm = 0;
 	i1 = i+1;
-	if (rtype(i->to) == RReg)
+	if (isreg(i->to))
 		for (;; i--) {
 			r = RBASE(i->to.val);
 			rt = i->arg[0];
@@ -215,13 +232,12 @@ dopm(Blk *b, Ins *i, RMap *m)
 			pmadd(rt, i->to);
 			if (i==b->ins
 			|| (i-1)->op!=OCopy
-			|| rtype((i-1)->to) != RReg)
+			|| isreg((i-1)->to))
 				break;
 		}
-	else if (rtype(i->arg[0]) == RReg)
+	else if (isreg(i->arg[0]))
 		for (;; i--) {
 			r = RBASE(i->arg[0].val);
-			assert(req(i->to, R) || i->to.type == RTmp);
 			if (req(i->to, R)) {
 				if (BGET(m->br, r)) {
 					for (n=0; m->r[n] != r; n++)
@@ -239,7 +255,7 @@ dopm(Blk *b, Ins *i, RMap *m)
 			BSET(m->br, r);
 			if (i==b->ins
 			|| (i-1)->op!=OCopy
-			|| rtype((i-1)->arg[0]) != RReg)
+			|| isreg((i-1)->arg[0]))
 				break;
 		}
 	else
@@ -273,21 +289,19 @@ rega(Fn *fn)
 	Ref src, dst;
 
 	tmp = fn->tmp;
-	end = alloc(fn->ntmp * sizeof end[0]);
-	beg = alloc(fn->ntmp * sizeof beg[0]);
+	end = alloc(fn->nblk * sizeof end[0]);
+	beg = alloc(fn->nblk * sizeof beg[0]);
 
 	/* 1. gross hinting setup */
-	for (t=0; t<fn->ntmp; t++)
+	for (t=Tmp0; t<fn->ntmp; t++)
 		tmp[t].hint = -1;
 	for (b=fn->start; b; b=b->link)
 		for (i=b->ins; i-b->ins < b->nins; i++) {
 			if (i->op != OCopy)
 				continue;
-			if (rtype(i->arg[0]) == RTmp
-			&& rtype(i->to) == RReg)
+			if (rtype(i->arg[0]) == RTmp && isreg(i->to))
 				tmp[i->arg[0].val].hint = RBASE(i->to.val);
-			if (rtype(i->to) == RTmp
-			&& rtype(i->arg[0]) == RReg)
+			if (rtype(i->to) == RTmp && isreg(i->arg[0]))
 				tmp[i->to.val].hint = RBASE(i->arg[0].val);
 		}
 
@@ -309,48 +323,38 @@ rega(Fn *fn)
 		 * successor
 		 */
 		if (b1 != b)
-			for (t=0; t<fn->ntmp; t++)
+			for (t=Tmp0; t<fn->ntmp; t++)
 				if (BGET(b->out, t))
 				if ((r = rfind(&beg[b1->id], t)) != -1)
 					radd(&cur, t, r);
 		for (x=0; x<2; x++)
-			for (t=0; t<fn->ntmp; t++)
+			for (t=Tmp0; t<fn->ntmp; t++)
 				if (x==1 || tmp[t].hint!=-1)
 				if (BGET(b->out, t))
 				if (!BGET(cur.bt, t))
 					ralloc(&cur, t);
 		/* process instructions */
 		end[n] = cur;
-		assert(rtype(b->jmp.arg) != RReg);
 		if (rtype(b->jmp.arg) == RTmp)
 			b->jmp.arg = ralloc(&cur, b->jmp.arg.val);
 		for (i=&b->ins[b->nins]; i!=b->ins;) {
 			i--;
 			if (i->op == OCopy /* par. moves are special */
-			&& (rtype(i->arg[0]) == RReg || rtype(i->to) == RReg)) {
+			&& (isreg(i->arg[0]) || isreg(i->to))) {
 				i = dopm(b, i, &cur);
 				continue;
 			}
-			switch (rtype(i->to)) {
-			default:
-				assert(!"unhandled destination");
-			case RTmp:
+			if (!req(i->to, R)) {
+				assert(rtype(i->to) == RTmp);
 				r = rfree(&cur, i->to.val);
 				if (r == -1) {
 					*i = (Ins){ONop, R, {R, R}};
 					continue;
 				}
-				i->to = reg(r, i->to.val);
-				break;
-			case RReg:
-				r = RBASE(i->to.val);
-				assert(BGET(cur.br, r));
-				BCLR(cur.br, r);
-				break;
-			case -1:;
+				if (i->to.val >= Tmp0)
+					i->to = reg(r, i->to.val);
 			}
-			switch (rtype(i->arg[0])) {
-			case RTmp:
+			if (rtype(i->arg[0]) == RTmp) {
 				/* <arch>
 				 *   on Intel, we attempt to
 				 *   use the same register
@@ -361,19 +365,10 @@ rega(Fn *fn)
 				if (tmp[t].hint == -1 && r)
 					tmp[t].hint = r;
 				i->arg[0] = ralloc(&cur, t);
-				break;
-			case RReg:
-				BSET(cur.br, RBASE(i->arg[0].val));
-				break;
 			}
-			switch (rtype(i->arg[1])) {
-			case RTmp:
+			if (rtype(i->arg[1]) == RTmp) {
 				t = i->arg[1].val;
 				i->arg[1] = ralloc(&cur, t);
-				break;
-			case RReg:
-				BSET(cur.br, RBASE(i->arg[1].val));
-				break;
 			}
 		}
 		b->in = cur.bt;
@@ -413,7 +408,7 @@ rega(Fn *fn)
 					src = rref(&end[b->id], src.val);
 				pmadd(src, dst);
 			}
-			for (t=0; t<fn->ntmp; t++)
+			for (t=Tmp0; t<fn->ntmp; t++)
 				if (BGET(s->in, t)) {
 					src = rref(&end[b->id], t);
 					dst = rref(&beg[s->id], t);
diff --git a/lisc/spill.c b/lisc/spill.c
index 6554316..ad461f0 100644
--- a/lisc/spill.c
+++ b/lisc/spill.c
@@ -34,7 +34,7 @@ tmpuse(Ref r, int use, int loop, Fn *fn)
 {
 	Tmp *t;
 
-	if (rtype(r) != RTmp)
+	if (rtype(r) != RTmp || r.val < Tmp0)
 		return;
 	t = &fn->tmp[r.val];
 	t->nuse += use;
@@ -77,7 +77,7 @@ fillcost(Fn *fn)
 		}
 	}
 	for (t=fn->tmp; t-fn->tmp < fn->ntmp; t++) {
-		t->cost = 0;
+		t->cost = t-fn->tmp < Tmp0 ? 1e6 : 0;
 		t->nuse = 0;
 		t->ndef = 0;
 	}
@@ -104,7 +104,7 @@ fillcost(Fn *fn)
 	}
 	if (debug['S']) {
 		fprintf(stderr, "\n> Spill costs:\n");
-		for (n=0; n<fn->ntmp; n++)
+		for (n=Tmp0; n<fn->ntmp; n++)
 			fprintf(stderr, "\t%-10s %d\n",
 				fn->tmp[n].name,
 				fn->tmp[n].cost);
@@ -145,8 +145,6 @@ static Bits *f;  /* temps to prioritize in registers (for tcmp1) */
 static Tmp *tmp; /* current temporaries (for tcmpX) */
 static int ntmp; /* current # of temps (for limit) */
 static uint ns;  /* current # of spill slots */
-static int nreg; /* # of registers available */
-static Bits br;  /* live registers */
 
 static int
 tcmp0(const void *pa, const void *pb)
@@ -168,6 +166,8 @@ slot(int t)
 {
 	int s;
 
+	if (t < Tmp0)
+		diag("spill: cannot spill register");
 	s = tmp[t].spill;
 	if (!s) {
 		s = ++ns;
@@ -237,24 +237,11 @@ setloc(Ref *pr, Bits *v, Bits *w)
 {
 	int t;
 
-	/* <arch>
-	 *   here we assume that the
-	 *   machine can always support
-	 *   instructions of the kind
-	 *   reg = op slot, slot
-	 *   if not, we need to add
-	 *   't' to 'w' before calling
-	 *   limit
-	 */
-	if (rtype(*pr) == RReg) {
-		nreg -= !BGET(br, pr->val);
-		BSET(br, pr->val);
-	}
 	if (rtype(*pr) != RTmp)
 		return 0;
 	t = pr->val;
 	BSET(*v, t);
-	if (limit(v, nreg, w) == t)
+	if (limit(v, NReg, w) == t)
 		/* if t was spilled by limit,
 		 * it was not live so we don't
 		 * have to reload it */
@@ -300,7 +287,6 @@ spill(Fn *fn)
 	for (n=fn->nblk-1; n>=0; n--) {
 		/* invariant: m>n => in,out of m updated */
 		b = fn->rpo[n];
-		assert(bcnt(&br) == 0);
 
 		/* 1. find temporaries in registers at
 		 * the end of the block (put them in v) */
@@ -345,32 +331,19 @@ spill(Fn *fn)
 		assert(bcnt(&v) <= NReg);
 
 		/* 2. process the block instructions */
-		nreg = NReg;
 		curi = &insb[NIns];
 		for (i=&b->ins[b->nins]; i!=b->ins;) {
-			assert(bcnt(&v) <= nreg);
+			assert(bcnt(&v) <= NReg);
 			i--;
 			s = 0;
-			switch (rtype(i->to)) {
-			default:
-				diag("spill: unhandled destination");
-			case RTmp:
+			if (!req(i->to, R)) {
+				assert(rtype(i->to) == RTmp);
 				j = i->to.val;
 				if (BGET(v, j))
 					BCLR(v, j);
 				else
-					limit(&v, nreg-1, &w);
+					limit(&v, NReg-1, &w);
 				s = tmp[j].spill;
-				break;
-			case RReg:
-				j = i->to.val;
-				if (BGET(br, j)) {
-					BCLR(br, j);
-					nreg++;
-				} else
-					limit(&v, nreg-1, &w);
-				break;
-			case -1:;
 			}
 			w = (Bits){{0}};
 			j = opdesc[i->op].nmem;