new layout, put LICENSE in root

1 files changed, 174 insertions, 0 deletions

diff --git a/live.c b/live.c
new file mode 100644
index 0000000..44806e1
--- /dev/null
+++ b/live.c
@@ -0,0 +1,174 @@
+#include "all.h"
+
+void
+liveon(BSet *v, Blk *b, Blk *s)
+{
+	Phi *p;
+	uint a;
+
+	bscopy(v, s->in);
+	for (p=s->phi; p; p=p->link) {
+		bsclr(v, p->to.val);
+		for (a=0; a<p->narg; a++)
+			if (p->blk[a] == b)
+			if (rtype(p->arg[a]) == RTmp)
+				bsset(v, p->arg[a].val);
+	}
+}
+
+static int
+phitmp(int t, Tmp *tmp)
+{
+	int tp;
+
+	tp = tmp[t].phi;
+	return tp ? tp : t;
+}
+
+static void
+phifix(int t1, short *phi, Tmp *tmp)
+{
+	int t, t2;
+
+	/* detect temporaries arguments
+	 * of the same phi node that
+	 * interfere and separate them
+	 */
+	t = phitmp(t1, tmp);
+	t2 = phi[t];
+	if (t2 && t2 != t1) {
+		if (t != t1) {
+			tmp[t1].phi = t1;
+			t = t1;
+		} else {
+			tmp[t2].phi = t2;
+			phi[t2] = t2;
+		}
+	}
+	phi[t] = t1;
+}
+
+static void
+bset(Ref r, Blk *b, int *nlv, short *phi, Tmp *tmp)
+{
+
+	if (rtype(r) != RTmp)
+		return;
+	bsset(b->gen, r.val);
+	phifix(r.val, phi, tmp);
+	if (!bshas(b->in, r.val)) {
+		nlv[KBASE(tmp[r.val].cls)]++;
+		bsset(b->in, r.val);
+	}
+}
+
+/* liveness analysis
+ * requires rpo computation
+ */
+void
+filllive(Fn *f)
+{
+	Blk *b;
+	Ins *i;
+	int k, t, m[2], n, chg, nlv[2];
+	short *phi;
+	BSet u[1], v[1];
+	Mem *ma;
+
+	bsinit(u, f->ntmp);
+	bsinit(v, f->ntmp);
+	phi = emalloc(f->ntmp * sizeof phi[0]);
+	for (b=f->start; b; b=b->link) {
+		bsinit(b->in, f->ntmp);
+		bsinit(b->out, f->ntmp);
+		bsinit(b->gen, f->ntmp);
+	}
+	chg = 1;
+Again:
+	for (n=f->nblk-1; n>=0; n--) {
+		b = f->rpo[n];
+
+		bscopy(u, b->out);
+		if (b->s1) {
+			liveon(v, b, b->s1);
+			bsunion(b->out, v);
+		}
+		if (b->s2) {
+			liveon(v, b, b->s2);
+			bsunion(b->out, v);
+		}
+		chg |= !bsequal(b->out, u);
+
+		memset(phi, 0, f->ntmp * sizeof phi[0]);
+		memset(nlv, 0, sizeof nlv);
+		bscopy(b->in, b->out);
+		for (t=0; t<f->ntmp; t++)
+			if (bshas(b->in, t)) {
+				phifix(t, phi, f->tmp);
+				nlv[KBASE(f->tmp[t].cls)]++;
+			}
+		if (rtype(b->jmp.arg) == RACall) {
+			assert(bscount(b->in) == 0 && nlv[0] == 0 && nlv[1] == 0);
+			b->in->t[0] |= retregs(b->jmp.arg, nlv);
+		} else
+			bset(b->jmp.arg, b, nlv, phi, f->tmp);
+		for (k=0; k<2; k++)
+			b->nlive[k] = nlv[k];
+		for (i=&b->ins[b->nins]; i!=b->ins;) {
+			if ((--i)->op == OCall && rtype(i->arg[1]) == RACall) {
+				b->in->t[0] &= ~retregs(i->arg[1], m);
+				for (k=0; k<2; k++)
+					nlv[k] -= m[k];
+				if (nlv[0] + NISave > b->nlive[0])
+					b->nlive[0] = nlv[0] + NISave;
+				if (nlv[1] + NFSave > b->nlive[1])
+					b->nlive[1] = nlv[1] + NFSave;
+				b->in->t[0] |= argregs(i->arg[1], m);
+				for (k=0; k<2; k++)
+					nlv[k] += m[k];
+			}
+			if (!req(i->to, R)) {
+				assert(rtype(i->to) == RTmp);
+				t = i->to.val;
+				if (bshas(b->in, i->to.val))
+					nlv[KBASE(f->tmp[t].cls)]--;
+				bsset(b->gen, t);
+				bsclr(b->in, t);
+				phi[phitmp(t, f->tmp)] = 0;
+			}
+			for (k=0; k<2; k++)
+				switch (rtype(i->arg[k])) {
+				case RAMem:
+					ma = &f->mem[i->arg[k].val & AMask];
+					bset(ma->base, b, nlv, phi, f->tmp);
+					bset(ma->index, b, nlv, phi, f->tmp);
+					break;
+				default:
+					bset(i->arg[k], b, nlv, phi, f->tmp);
+					break;
+				}
+			for (k=0; k<2; k++)
+				if (nlv[k] > b->nlive[k])
+					b->nlive[k] = nlv[k];
+		}
+	}
+	if (chg) {
+		chg = 0;
+		goto Again;
+	}
+	free(phi);
+
+	if (debug['L']) {
+		fprintf(stderr, "\n> Liveness analysis:\n");
+		for (b=f->start; b; b=b->link) {
+			fprintf(stderr, "\t%-10sin:   ", b->name);
+			dumpts(b->in, f->tmp, stderr);
+			fprintf(stderr, "\t          out:  ");
+			dumpts(b->out, f->tmp, stderr);
+			fprintf(stderr, "\t          gen:  ");
+			dumpts(b->gen, f->tmp, stderr);
+			fprintf(stderr, "\t          live: ");
+			fprintf(stderr, "%d %d\n", b->nlive[0], b->nlive[1]);
+		}
+	}
+}