From 851e79f9590b705a0fb168d16755caad03650348 Mon Sep 17 00:00:00 2001
From: Quentin Carbonneaux <quentin.carbonneaux@yale.edu>
Date: Fri, 10 Jul 2015 13:55:47 -0400
Subject: add rpo information to functions

---
 lisc/lisc.h  |  4 ++++
 lisc/parse.c |  5 +++++
 lisc/ssa.c   | 44 ++++++++++++++++++++++++++++++++++++++++++++
 3 files changed, 53 insertions(+)

diff --git a/lisc/lisc.h b/lisc/lisc.h
index da735f0..a26dc1e 100644
--- a/lisc/lisc.h
+++ b/lisc/lisc.h
@@ -89,6 +89,7 @@ struct Blk {
 	Blk *link;
 
 	char name[NString];
+	int rpo;
 	Blk **preds;
 	int npreds;
 };
@@ -108,6 +109,8 @@ struct Fn {
 	Blk *start;
 	Sym *sym;
 	int ntemp;
+	int nblk;
+	Blk **rpo;
 };
 
 
@@ -117,3 +120,4 @@ Fn *parsefn(FILE *);
 
 /* ssa.c */
 void fillpreds(Fn *);
+void fillrpo(Fn *);
diff --git a/lisc/parse.c b/lisc/parse.c
index ad57d7e..e17c264 100644
--- a/lisc/parse.c
+++ b/lisc/parse.c
@@ -54,6 +54,7 @@ static struct {
 } bmap[NBlks+1];
 static Blk *curb;
 static Blk **blink;
+static int nblk;
 
 static struct {
 	long long num;
@@ -203,6 +204,7 @@ blocka()
 	*b = zblock;
 	*blink = b;
 	blink = &b->link;
+	nblk++;
 	return b;
 }
 
@@ -443,6 +445,7 @@ parsefn(FILE *f)
 	curi = ins;
 	curb = 0;
 	lnum = 1;
+	nblk = 0;
 	fn = alloc(sizeof *fn);
 	blink = &fn->start;
 	ps = PLbl;
@@ -452,6 +455,8 @@ parsefn(FILE *f)
 	fn->sym = alloc(ntemp * sizeof sym[0]);
 	memcpy(fn->sym, sym, ntemp * sizeof sym[0]);
 	fn->ntemp = ntemp;
+	fn->nblk = nblk;
+	fn->rpo = 0;
 	return fn;
 }
 
diff --git a/lisc/ssa.c b/lisc/ssa.c
index e01bcc6..4703d0a 100644
--- a/lisc/ssa.c
+++ b/lisc/ssa.c
@@ -38,3 +38,47 @@ fillpreds(Fn *f)
 			addpred(b, b->s2);
 	}
 }
+
+static int
+rporec(Blk *b, int x)
+{
+	if (b->rpo >= 0)
+		return x;
+	if (b->s1)
+		x = rporec(b->s1, x);
+	if (b->s2)
+		x = rporec(b->s2, x);
+	b->rpo = x;
+	return x - 1;
+}
+
+void
+fillrpo(Fn *f)
+{
+	int n;
+	Blk *b, **p;
+
+	for (b=f->start; b; b=b->link)
+		b->rpo = -1;
+	n = rporec(f->start, f->nblk-1);
+	f->rpo = alloc(n * sizeof(Blk*));
+	for (p=&f->start; *p;) {
+		b = *p;
+		if (b->rpo == -1) {
+			*p = b->link;
+			/* todo, free block */
+		} else {
+			b->rpo -= n;
+			f->rpo[b->rpo] = b;
+			p=&(*p)->link;
+		}
+	}
+}
+
+void
+ssafix(Fn *f, Ref v)
+{
+	(void)f;
+	(void)v;
+	return;
+}
-- 
cgit 1.4.1