finish spiller, now needs testing!

3 files changed, 143 insertions, 5 deletions

diff --git a/lisc/lisc.h b/lisc/lisc.h
index f9e3222..ac5714a 100644
--- a/lisc/lisc.h
+++ b/lisc/lisc.h
@@ -172,6 +172,7 @@ void dumpss(Bits *, Sym *, FILE *);
 extern OpDesc opdesc[];
 void diag(char *);
 void *alloc(size_t);
+Blk *blocka(void);
 Fn *parsefn(FILE *);
 void printfn(Fn *, FILE *);
 
diff --git a/lisc/parse.c b/lisc/parse.c
index 1b9ad3b..e4c0f94 100644
--- a/lisc/parse.c
+++ b/lisc/parse.c
@@ -231,7 +231,7 @@ next()
 	return t;
 }
 
-static Blk *
+Blk *
 blocka()
 {
 	static Blk zblock;
diff --git a/lisc/spill.c b/lisc/spill.c
index e9a6219..cd34931 100644
--- a/lisc/spill.c
+++ b/lisc/spill.c
@@ -172,6 +172,7 @@ slot(int t)
 {
 	int s;
 
+	assert(sym[t].type == STmp);
 	s = sym[t].spill;
 	if (!s) {
 		s = 1 + ns++;
@@ -217,9 +218,11 @@ limit(Bits *b, int k, Bits *fst)
 	res = (Bits){{0}};
 	for (i=0; i<k && i<nt; i++)
 		BSET(res, tmp[i]);
-	if (curi)
-		for (; i<nt; i++)
+	for (; i<nt; i++) {
+		slot(tmp[i]);
+		if (curi)
 			emit(OLoad, SYM(tmp[i]), slot(tmp[i]), R);
+	}
 	return res;
 }
 
@@ -251,6 +254,92 @@ setloc(Ref *pr, Bits *v, Bits *w)
 		BSET(*w, t);
 }
 
+static Blk *elist; /* edge list created by edge() */
+static int ne;     /* length of elist */
+
+static Blk *
+edge(Blk *b, Blk **ps, Ins *ins, int nins)
+{
+	Blk *b1, *s;
+	Ins *ib;
+	Phi *p;
+	uint a;
+
+	s = *ps;
+	/* first, try adding at the beginning
+	 * or end of b or s
+	 *
+	 * todo, hey, is this overkill?
+	 */
+	if (b->s1 == s && !b->s2) {
+		ib = alloc((nins + b->nins) * sizeof(Ins));
+		memcpy(ib, b->ins, b->nins * sizeof(Ins));
+		memcpy(&ib[b->nins], ins, nins * sizeof(Ins));
+		free(b->ins);
+		b->nins += nins;
+		b->ins = ib;
+		return 0;
+	}
+	if (s->npred == 1) {
+		ib = alloc((nins + s->nins) * sizeof(Ins));
+		memcpy(ib, ins, nins * sizeof(Ins));
+		memcpy(&ib[nins], s->ins, s->nins * sizeof(Ins));
+		free(s->ins);
+		s->nins += nins;
+		s->ins = ib;
+		return 0;
+	}
+	/* last resort alloc a block */
+	b1 = blocka();
+	b1->link = elist;
+	elist = b1;
+	ne++;
+	sprintf(b1->name, "%s_%s", b->name, s->name);
+	ib = alloc(nins * sizeof(Ins));
+	memcpy(ib, ins, nins * sizeof(Ins));
+	b1->ins = ib;
+	b1->nins = nins;
+	b1->jmp.type = JJmp;
+	b1->s1 = s;
+	*ps = b1;
+	/* fix phis and predecessors */
+	for (p=s->phi; p; p=p->link)
+		for (a=0; a<p->narg; a++)
+			if (p->blk[a] == b)
+				p->blk[a] = b1;
+	for (a=0; a<s->npred; a++)
+		if (s->pred[a] == b)
+			s->pred[a] = b1;
+	return b1;
+}
+
+static void
+reload(Blk *b, Blk **ps)
+{
+	Bits v;
+	Blk *s, *e;
+	int z, t;
+	Ref sr;
+
+	s = *ps;
+	curi = insb;
+	v = s->in;
+	for (z=0; z<BITS; z++)
+		v.t[z] &= ~b->out.t[z];
+	for (t=Tmp0; t<ntmp; t++)
+		if (BGET(v, t)) {
+			sr = SLOT(sym[t].spill);
+			assert(sr.val);
+			*curi++ = (Ins){OLoad, SYM(t), {sr, R}};
+		}
+	if (curi != insb) {
+		e = edge(b, ps, insb, curi-insb);
+		if (e) {
+			e->loop = s->loop/s->npred;
+			e->out = v;
+		}
+	}
+}
 
 /* spill code insertion
  * requires spill costs, rpo, liveness
@@ -270,11 +359,14 @@ void
 spill(Fn *fn)
 {
 	Blk *b, *s1, *s2, *hd;
-	int n, z, l;
+	int n, z, l, t;
 	Bits v, w;
 	Ins *i;
 	int j, s;
 	Phi *p;
+	Ref sr;
+	Ins *ib;
+	uint a;
 
 	ns = 0;
 	sym = fn->sym;
@@ -378,7 +470,52 @@ spill(Fn *fn)
 		memcpy(b->ins, curi, b->nins * sizeof(Ins));
 
 		for (p=b->phi; p; p=p->link)
-			BCLR(v, p->to.val);
+			if (BGET(v, p->to.val))
+				BCLR(v, p->to.val);
+			else
+				p->to = slot(p->to.val);
 		b->in = v;
 	}
+
+	/* 3. fix phi nodes and
+	 * insert reload code between blocks */
+	ne = 0;
+	elist = 0;
+	for (b=fn->start;; b=b->link) {
+		if (b->s1)
+			reload(b, &b->s1);
+		if (b->s2)
+			reload(b, &b->s2);
+		curi = insb;
+		for (p=b->phi; p; p=p->link) {
+			t = p->to.val;
+			sr = SLOT(sym[t].spill);
+			if (sr.val)
+				*curi++ = (Ins){OStore, R, {SYM(t), sr}};
+			for (a=0; a<p->narg; a++) {
+				if (rtype(p->arg[a]) != RSym)
+					continue;
+				t = p->arg[a].val;
+				if (!BGET(p->blk[a]->out, t)) {
+					sr = SLOT(sym[t].spill);
+					assert(sr.val);
+					p->arg[a] = sr;
+				}
+			}
+		}
+		if (curi != insb) {
+			n = curi - insb;
+			ib = alloc((b->nins+n) * sizeof(Ins));
+			memcpy(ib, insb, n * sizeof(Ins));
+			memcpy(&ib[n], b->ins, b->nins * sizeof(Ins));
+			free(b->ins);
+			b->nins += n;
+			b->ins = ib;
+		}
+		if (!b->link) {
+			b->link = elist;
+			fn->nblk += ne;
+			break;
+		}
+	}
 }