schedule loop nesting computations earlier

4 files changed, 63 insertions, 26 deletions

diff --git a/all.h b/all.h
index 5784d9a..d2763eb 100644
--- a/all.h
+++ b/all.h
@@ -553,6 +553,8 @@ void filldom(Fn *);
 int sdom(Blk *, Blk *);
 int dom(Blk *, Blk *);
 void fillfron(Fn *);
+void loopiter(Fn *, void (*)(Blk *, Blk *));
+void fillloop(Fn *);
 
 /* mem.c */
 void memopt(Fn *);
diff --git a/cfg.c b/cfg.c
index ae54deb..bebf0fa 100644
--- a/cfg.c
+++ b/cfg.c
@@ -228,3 +228,50 @@ fillfron(Fn *fn)
 				addfron(a, b->s2);
 	}
 }
+
+static void
+loopmark(Blk *hd, Blk *b, void f(Blk *, Blk *))
+{
+	uint p;
+
+	if (b->id < hd->id || b->visit == hd->id)
+		return;
+	b->visit = hd->id;
+	f(hd, b);
+	for (p=0; p<b->npred; ++p)
+		loopmark(hd, b->pred[p], f);
+}
+
+void
+loopiter(Fn *fn, void f(Blk *, Blk *))
+{
+	int n;
+	uint p;
+	Blk *b;
+
+	for (b=fn->start; b; b=b->link)
+		b->visit = -1;
+	for (n=0; n<fn->nblk; ++n) {
+		b = fn->rpo[n];
+		for (p=0; p<b->npred; ++p)
+			if (b->pred[p]->id >= n)
+				loopmark(b, b->pred[p], f);
+	}
+}
+
+void
+multloop(Blk *hd, Blk *b)
+{
+	(void)hd;
+	b->loop *= 10;
+}
+
+void
+fillloop(Fn *fn)
+{
+	Blk *b;
+
+	for (b=fn->start; b; b=b->link)
+		b->loop = 1;
+	loopiter(fn, multloop);
+}
diff --git a/main.c b/main.c
index 6642ac2..f8d367f 100644
--- a/main.c
+++ b/main.c
@@ -49,6 +49,7 @@ func(Fn *fn)
 	ssa(fn);
 	filluse(fn);
 	ssacheck(fn);
+	fillloop(fn);
 	fillalias(fn);
 	loadopt(fn);
 	filluse(fn);
diff --git a/spill.c b/spill.c
index f9dcc49..5d1726e 100644
--- a/spill.c
+++ b/spill.c
@@ -1,23 +1,16 @@
 #include "all.h"
 
 static void
-loopmark(Blk *hd, Blk *b)
+aggreg(Blk *hd, Blk *b)
 {
 	int k;
-	uint n;
 
-	if (b->id < hd->id || b->visit == hd->id)
-		return;
-	b->visit = hd->id;
-	b->loop *= 10;
 	/* aggregate looping information at
 	 * loop headers */
 	bsunion(hd->gen, b->gen);
 	for (k=0; k<2; k++)
 		if (b->nlive[k] > hd->nlive[k])
 			hd->nlive[k] = b->nlive[k];
-	for (n=0; n<b->npred; n++)
-		loopmark(hd, b->pred[n]);
 }
 
 static void
@@ -46,32 +39,26 @@ tmpuse(Ref r, int use, int loop, Fn *fn)
 void
 fillcost(Fn *fn)
 {
-	int n, hd;
+	int n;
 	uint a;
 	Blk *b;
 	Ins *i;
 	Tmp *t;
 	Phi *p;
 
-	for (b=fn->start; b; b=b->link) {
-		b->loop = 1;
-		b->visit = -1;
-	}
-	if (debug['S'])
+	loopiter(fn, aggreg);
+	if (debug['S']) {
 		fprintf(stderr, "\n> Loop information:\n");
-	for (n=0; n<fn->nblk; n++) {
-		b = fn->rpo[n];
-		hd = 0;
-		for (a=0; a<b->npred; a++)
-			if (b->pred[a]->id >= n) {
-				loopmark(b, b->pred[a]);
-				hd = 1;
+		for (b=fn->start; b; b=b->link) {
+			for (a=0; a<b->npred; ++a)
+				if (b->id <= b->pred[a]->id)
+					break;
+			if (a != b->npred) {
+				fprintf(stderr, "\t%-10s", b->name);
+				fprintf(stderr, " (% 3d ", b->nlive[0]);
+				fprintf(stderr, "% 3d) ", b->nlive[1]);
+				dumpts(b->gen, fn->tmp, stderr);
 			}
-		if (hd && debug['S']) {
-			fprintf(stderr, "\t%-10s", b->name);
-			fprintf(stderr, " (% 3d ", b->nlive[0]);
-			fprintf(stderr, "% 3d) ", b->nlive[1]);
-			dumpts(b->gen, fn->tmp, stderr);
 		}
 	}
 	for (t=fn->tmp; t-fn->tmp < fn->ntmp; t++) {