add simple unreachability

4 files changed, 50 insertions, 2 deletions

diff --git a/src/asm.c b/src/asm.c
index eb0bead..e177c4e 100644
--- a/src/asm.c
+++ b/src/asm.c
@@ -240,10 +240,10 @@ static void output_ret(struct fn *f, FILE *o)
 static void output_j(struct blk *b, struct fn *f, FILE *o)
 {
 	/* the jump is directly to a following block, no need to do anything */
-	if (!b->to)
+	if (!b->to || b->s1 == b->s2)
 		return;
 
-	fprintf(o, "j .%s.%lli\n", f->name, (long long int)b->s1->id);
+	fprintf(o, "j .%s.%lli\n", f->name, (long long int)b->s2->id);
 }
 
 static void output_branch(struct blk *b, struct fn *f, FILE *o)
diff --git a/src/nodes.c b/src/nodes.c
index 4c5e97a..294b531 100644
--- a/src/nodes.c
+++ b/src/nodes.c
@@ -48,6 +48,7 @@ struct blk *new_block(struct fn *f)
 {
 	struct blk *b = calloc(1, sizeof(struct blk));
 	b->id = ++f->nblk;
+	b->reachable = false;
 	b->insns = vec_create(sizeof(struct insn));
 	vec_append(&f->blks, &b);
 	return b;
@@ -82,6 +83,13 @@ void finish_function(struct fn *f, const char *name)
 
 	destroy_block(last_blk);
 
+	last_blk = blk_back(f->blks);
+	/* somewhat arbitrary restriction but I guess but makes the
+	 * implementation a bit simpler */
+	assert(last_blk->btype == RET);
+	last_blk->s1 = NULL;
+	last_blk->s2 = NULL;
+
 	foreach_blk(i, f->blks) {
 		struct blk *b = blk_at(f->blks, i);
 		if (!b->to)
diff --git a/src/opt.c b/src/opt.c
index 3036950..d52c9d0 100644
--- a/src/opt.c
+++ b/src/opt.c
@@ -1,5 +1,6 @@
 #include <qbt/opt.h>
 #include <qbt/regalloc.h>
+#include <qbt/unreachable.h>
 #include <qbt/ssa.h>
 #include <qbt/abi.h>
 
@@ -8,5 +9,6 @@ void optimize(struct fn *f)
 	ssa(f);
 	abi0(f);
 	/* ... do more stuff ... */
+	unreachable(f);
 	regalloc(f);
 }
diff --git a/src/unreachable.c b/src/unreachable.c
new file mode 100644
index 0000000..90a65bd
--- /dev/null
+++ b/src/unreachable.c
@@ -0,0 +1,38 @@
+#include <qbt/unreachable.h>
+
+void build_reachable_vec(struct vec *reachable, struct blk *cur)
+{
+	if (cur->reachable)
+		return;
+
+	cur->reachable = true;
+	vec_append(reachable, &cur);
+
+	if (cur->btype == RET)
+		return;
+
+	if (cur->btype == J)
+		cur->s1 = cur->s2;
+
+	if (cur->s1)
+		build_reachable_vec(reachable, cur->s1);
+
+	if (cur->s2)
+		build_reachable_vec(reachable, cur->s2);
+}
+
+void unreachable(struct fn *f)
+{
+	struct vec reachable = vec_create(sizeof(struct blk *));
+	struct blk *b = blk_at(f->blks, 0);
+	build_reachable_vec(&reachable, b);
+	foreach_blk(bi, f->blks) {
+		struct blk *b = blk_at(f->blks, bi);
+		if (!b->reachable)
+			destroy_block(b);
+
+	}
+
+	vec_destroy(&f->blks);
+	f->blks = reachable;
+}