add simple unreachability

7 files changed, 81 insertions, 2 deletions

diff --git a/include/qbt/nodes.h b/include/qbt/nodes.h
index 011d718..63bbc58 100644
--- a/include/qbt/nodes.h
+++ b/include/qbt/nodes.h
@@ -128,6 +128,8 @@ struct blk {
 
 	/* used to temporarily store label targets */
 	const char *to;
+	/* used by reachability analysis */
+	bool reachable;
 };
 
 struct fn {
@@ -253,6 +255,9 @@ struct label_map {
 #define blk_at(v, i)\
 	vect_at(struct blk *, v, i)
 
+#define blk_back(v)\
+	vect_at(struct blk *, v, vec_len(&v) - 1)
+
 #define blk_pop(v)\
 	vect_pop(struct blk *, v)
 
diff --git a/include/qbt/unreachable.h b/include/qbt/unreachable.h
new file mode 100644
index 0000000..0f0c39e
--- /dev/null
+++ b/include/qbt/unreachable.h
@@ -0,0 +1,8 @@
+#ifndef UNREACHABLE_H
+#define UNREACHABLE_H
+
+#include <qbt/nodes.h>
+
+void unreachable(struct fn *f);
+
+#endif /* UNREACHABLE_H */
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;
+}
diff --git a/tests/unreachable.qbt b/tests/unreachable.qbt
new file mode 100644
index 0000000..b97f9e1
--- /dev/null
+++ b/tests/unreachable.qbt
@@ -0,0 +1,18 @@
+in_jump() {
+	i27 r0 = 0;
+	-> after;
+
+	i27 r1 = 0;
+	=> (r1);
+
+	after:
+	=> (r0);
+}
+
+after_return() {
+	i27 r0 = 0;
+	=> (r0);
+
+	i27 r1 = 10;
+	=> (r1);
+}