qbe

commit 8ae9f786cbc1173e2530cf86b222549ac0106670
parent 0679df0b5620c032f4e2a17ab5faa94ff1ea3ce9
Author: Quentin Carbonneaux <quentin.carbonneaux@yale.edu>
Date:   Tue,  3 Nov 2015 16:47:47 -0500

add interference hints

Diffstat:
M
lisc/lisc.h
 | 
6
+++++-
M
lisc/rega.c
 | 
26
+++++++++++++++++---------
M
lisc/spill.c
 | 
26
+++++++++++++++++++++++++-
M
lisc/util.c
 | 
21
+++++++++++++++++++++

4 files changed, 68 insertions(+), 11 deletions(-)
diff --git a/lisc/lisc.h b/lisc/lisc.h
@@ -246,7 +246,10 @@ struct Tmp {
 	uint cost;
 	short slot;
 	short wide;
-	int hint;
+	struct {
+		int r;
+		ulong m;
+	} hint;
 	int phi;
 };
 
@@ -335,6 +338,7 @@ void idup(Ins **, Ins *, ulong);
 Ins *icpy(Ins *, Ins *, ulong);
 void *vnew(ulong, size_t);
 void vgrow(void *, ulong);
+int phicls(int, Tmp *);
 Ref newtmp(char *, Fn *);
 Ref getcon(int64_t, Fn *);
 void addcon(Con *, Con *);
diff --git a/lisc/rega.c b/lisc/rega.c
@@ -25,10 +25,7 @@ static int cpm, npm;   /* capacity and size of pm */
 static int *
 hint(int t)
 {
-	if (tmp[t].phi)
-		return &tmp[tmp[t].phi].hint;
-	else
-		return &tmp[t].hint;
+	return &tmp[phicls(t, tmp)].hint.r;
 }
 
 static int
@@ -75,6 +72,7 @@ radd(RMap *m, int t, int r)
 static Ref
 ralloc(RMap *m, int t)
 {
+	ulong regs;
 	int r;
 
 	if (t < Tmp0) {
@@ -87,10 +85,16 @@ ralloc(RMap *m, int t)
 		return TMP(r);
 	}
 	r = *hint(t);
-	if (r == -1 || BGET(m->b, r))
-		for (r=RAX; BGET(m->b, r); r++)
-			if (r+1 == RAX+NReg)
-				diag("rega: no more regs");
+	if (r == -1 || BGET(m->b, r)) {
+		regs = tmp[phicls(t, tmp)].hint.m;
+		regs |= m->b.t[0];
+		for (r=RAX; r<RAX+NReg && (regs & BIT(r)); r++)
+			;
+		if (r == RAX+NReg)
+			for (r=RAX; BGET(m->b, r); r++)
+				if (r+1 == RAX+NReg)
+					diag("rega: no more regs");
+	}
 	radd(m, t, r);
 	if (*hint(t) == -1)
 		*hint(t) = r;
@@ -323,6 +327,10 @@ doblk(Blk *b, RMap *cur)
 				i = dopm(b, i, cur);
 				continue;
 			}
+			if (isreg(i->to))
+			if (rtype(i->arg[0]) == RTmp)
+			if (*hint(i->arg[0].val) == -1)
+				*hint(i->arg[0].val) = i->to.val;
 			/* fall through */
 		default:
 			if (!req(i->to, R)) {
@@ -377,7 +385,7 @@ rega(Fn *fn)
 	end = alloc(fn->nblk * sizeof end[0]);
 	beg = alloc(fn->nblk * sizeof beg[0]);
 	for (t=Tmp0; t<fn->ntmp; t++)
-		tmp[t].hint = -1;
+		*hint(t) = -1;
 	for (b=fn->start, i=b->ins; i-b->ins < b->nins; i++)
 		if (i->op != OCopy || !isreg(i->arg[0]))
 			break;
diff --git a/lisc/spill.c b/lisc/spill.c
@@ -211,6 +211,16 @@ limit(Bits *b, int k, Bits *fst)
 }
 
 static void
+sethint(Bits *u, ulong r)
+{
+	int t;
+
+	for (t=Tmp0; t<ntmp; t++)
+		if (BGET(*u, t))
+			tmp[phicls(t, tmp)].hint.m |= r;
+}
+
+static void
 reloads(Bits *u, Bits *v)
 {
 	int t;
@@ -223,8 +233,10 @@ reloads(Bits *u, Bits *v)
 static Ins *
 dopm(Blk *b, Ins *i, Bits *v)
 {
+	int n;
 	Bits u;
 	Ins *i1;
+	ulong r;
 
 	/* consecutive moves from
 	 * registers need to handled
@@ -244,9 +256,15 @@ dopm(Blk *b, Ins *i, Bits *v)
 	if (i > b->ins && (i-1)->op == OCall) {
 		v->t[0] &= ~calldef(*(i-1), 0);
 		limit(v, NReg - NRSave, 0);
+		r = 0;
+		for (n=0; n<NRSave; n++)
+			r |= BIT(rsave[n]);
 		v->t[0] |= calluse(*(i-1), 0);
-	} else
+	} else {
 		limit(v, NReg, 0);
+		r = v->t[0];
+	}
+	sethint(v, r);
 	reloads(&u, v);
 	do
 		emiti(*--i1);
@@ -276,6 +294,7 @@ spill(Fn *fn)
 	int j, s;
 	Phi *p;
 	Mem *ma;
+	ulong r;
 
 	tmp = fn->tmp;
 	ntmp = fn->ntmp;
@@ -342,6 +361,7 @@ spill(Fn *fn)
 
 		/* 2. process the block instructions */
 		curi = &insb[NIns];
+		r = 0;
 		for (i=&b->ins[b->nins]; i!=b->ins;) {
 			assert(bcnt(&v) <= NReg);
 			i--;
@@ -400,11 +420,15 @@ spill(Fn *fn)
 						i->arg[m] = slot(t);
 					}
 				}
+			r = v.t[0] & (BIT(Tmp0)-1);
+			if (r)
+				sethint(&v, r);
 			reloads(&u, &v);
 			if (s != -1)
 				store(i->to, s);
 			emiti(*i);
 		}
+		assert(!r || b==fn->start);
 
 		for (p=b->phi; p; p=p->link) {
 			assert(rtype(p->to) == RTmp);
diff --git a/lisc/util.c b/lisc/util.c
@@ -166,6 +166,27 @@ vgrow(void *vp, ulong len)
 	*(Vec **)vp = v1;
 }
 
+int
+phicls(int t, Tmp *tmp /*, int c*/)
+{
+	if (tmp[t].phi)
+		return tmp[t].phi;
+	return t;
+#if 0
+	int t1;
+
+	t1 = tmp[t].phi;
+	if (!t1)
+		t1 = t;
+	if (t != t1) {
+		t1 = phitmp(t1, tmp, c);
+		if (c)
+			tmp[t].phi = t1;
+	}
+	return t1;
+#endif
+}
+
 Ref
 newtmp(char *prfx, Fn *fn)
 {