add union-find based phi-class computation

3 files changed, 51 insertions, 0 deletions

diff --git a/lisc/lisc.h b/lisc/lisc.h
index c577dea..83994e5 100644
--- a/lisc/lisc.h
+++ b/lisc/lisc.h
@@ -226,6 +226,7 @@ struct Tmp {
 	short spill;
 	short wide;
 	int hint;
+	int phi;
 };
 
 struct Con {
@@ -281,6 +282,8 @@ void printfn(Fn *, FILE *);
 /* ssa.c */
 void fillpreds(Fn *);
 void fillrpo(Fn *);
+int phirepr(Tmp *, int);
+void fillphi(Fn *);
 void ssafix(Fn *, int);
 
 /* live.c */
diff --git a/lisc/main.c b/lisc/main.c
index 1452ff6..b0fbd0e 100644
--- a/lisc/main.c
+++ b/lisc/main.c
@@ -110,6 +110,7 @@ main(int ac, char *av[])
 		fillpreds(fn);
 		filllive(fn);
 		fillcost(fn);
+		fillphi(fn);
 		spill(fn);
 		rega(fn);
 		goto RPODump;
@@ -123,6 +124,7 @@ main(int ac, char *av[])
 		fillpreds(fn);
 		filllive(fn);
 		fillcost(fn);
+		fillphi(fn);
 		spill(fn);
 		rega(fn);
 		fillrpo(fn);
diff --git a/lisc/ssa.c b/lisc/ssa.c
index 9002443..9608a93 100644
--- a/lisc/ssa.c
+++ b/lisc/ssa.c
@@ -89,6 +89,52 @@ fillrpo(Fn *f)
 	}
 }
 
+/* gets the representant for the phi class of t
+ */
+int
+phirepr(Tmp *tmp, int t)
+{
+	int tp;
+
+	tp = tmp[t].phi;
+	if (tp == 0)
+		tp = t;
+	else if (tp != t) {
+		tp = phirepr(tmp, tp);
+		tmp[t].phi = tp;
+	}
+	return tp;
+}
+
+/* fill union find data for phi classes
+ */
+void
+fillphi(Fn *fn)
+{
+	Blk *b;
+	Phi *p;
+	uint a;
+	int t, ta;
+	Tmp *tmp;
+
+	tmp = fn->tmp;
+	for (t=Tmp0; t<fn->ntmp; t++)
+		tmp[t].phi = 0;
+	for (b=fn->start; b; b=b->link)
+		for (p=b->phi; p; p=p->link) {
+			t = p->to.val;
+			if (tmp[t].phi == 0)
+				tmp[t].phi = t;
+			for (a=0; a<p->narg; a++) {
+				if (rtype(p->arg[a]) != RTmp)
+					continue;
+				ta = p->arg[a].val;
+				ta = phirepr(tmp, ta);
+				tmp[ta].phi = t;
+			}
+		}
+}
+
 static Ref *top, *bot;
 static Ref topdef(Blk *, Fn *, int);