allow compiling some massive functions

3 files changed, 142 insertions, 34 deletions

diff --git a/src/parser.y b/src/parser.y
index dd744c0..f41948f 100644
--- a/src/parser.y
+++ b/src/parser.y
@@ -516,12 +516,18 @@ call
 		INS_REPLACE($[placeholder],
 			insn_create(CALL, NOTYPE,
 				noclass(), imm_ref($[addr]), noclass(), 0));
+
+		/* make some optimization phases easier by splitting each call
+		 * into a separate block */
+		NEW_BLOCK(J, noclass(), noclass(), NULL);
 	}
 	| id reset_index "(" opt_call_args ")"
 	  "=>" placeholder reset_index "(" opt_call_rets ")" {
 		INS_REPLACE($[placeholder],
 			insn_create(CALL, NOTYPE,
 				noclass(), IDTOVAL($[id]), noclass(), 0));
+
+		NEW_BLOCK(J, noclass(), noclass(), NULL);
 	  }
 
 proc_ret
@@ -555,15 +561,24 @@ insn
 	| call
 	| return
 
-body
-	: insn ";" body
-	| label body
+labels
+	: labels label
 	| label
-	| insn ";"
+
+body
+	: body ";" labels insn
+	| body ";" insn
+	| labels insn
+	| labels
+	| insn
+
+body_opt_term
+	: body
+	| body ";"
 
 /** @todo add in return type checking? */
 function
-	: id reset_index "(" opt_params ")" "{" body "}" {
+	: id reset_index "(" opt_params ")" "{" body_opt_term "}" {
 		NEW_FUNCTION($[id]);
 	}
 
@@ -572,7 +587,7 @@ top
 	| function
 
 unit
-	: top unit
+	: unit top
 	| top
 	| error {
 		parser->failed = true;
diff --git a/src/regalloc.c b/src/regalloc.c
index cd21f5e..6265c6d 100644
--- a/src/regalloc.c
+++ b/src/regalloc.c
@@ -175,10 +175,26 @@ static void collect_lifetimes(struct blk *b, struct vec *hints,
 	}
 }
 
-static void build_active_between(struct vec *active, struct vec *lifetimes,
-                                 size_t start, size_t end)
+static void build_active_between(struct vec *active, struct vec *prev_active, struct vec *lifetimes,
+                                 size_t i, size_t start, size_t end)
 {
-	foreach_lifetime(li, *lifetimes) {
+	/* we really only need to look at previously active lifetimes and check
+	 * which ones are still active, no need to iterate all the way from the
+	 * start. Only works if prev_active is really the previous lifetime in
+	 * the lifetimes vector */
+	if (prev_active)
+	foreach_lifetime(li, *prev_active) {
+		struct lifetime l = lifetime_at(*lifetimes, li);
+		if (l.end <= start)
+			continue;
+
+		if (l.start >= end)
+			break;
+
+		vec_append(active, &l);
+	}
+
+	for (size_t li = i; li < vec_len(lifetimes); ++li) {
 		struct lifetime l = lifetime_at(*lifetimes, li);
 		if (l.used == 0)
 			continue;
@@ -188,17 +204,20 @@ static void build_active_between(struct vec *active, struct vec *lifetimes,
 		if (l.end <= start)
 			continue;
 
+		/* since lifetimes must be strictly ascending by start value, we
+		 * know that no other lifetimes can possibly be active after
+		 * this point */
 		if (l.start >= end)
-			continue;
+			break;
 
 		vec_append(active, &l);
 	}
 }
 
-static void build_active(struct vec *active, struct vec *lifetimes, size_t i)
+static void build_active(struct vec *active, struct vec *prev_active, struct vec *lifetimes, size_t i)
 {
 	struct lifetime ref = lifetime_at(*lifetimes, i);
-	build_active_between(active, lifetimes, ref.start, ref.end);
+	build_active_between(active, prev_active, lifetimes, i, ref.start, ref.end);
 }
 
 static void build_reserved(struct vec *reserved, struct vec *active,
@@ -279,10 +298,18 @@ static size_t highest_sreg(struct val f)
 	return 0;
 }
 
+static void swap_lifetimes(struct vec *a, struct vec *b)
+{
+	struct vec tmp = *a;
+	*a = *b;
+	*b = tmp;
+}
+
 static size_t build_rmap(struct vec *hints, struct vec *lifetimes,
                          struct vec *rmap)
 {
 	size_t max_callee_save = 0;
+	struct vec prev_active = vec_create(sizeof(struct lifetime));
 	struct vec active = vec_create(sizeof(struct lifetime));
 	struct vec reserved = vec_create(sizeof(struct val));
 
@@ -296,7 +323,7 @@ static size_t build_rmap(struct vec *hints, struct vec *lifetimes,
 
 		vec_reset(&active);
 		vec_reset(&reserved);
-		build_active(&active, lifetimes, li);
+		build_active(&active, &prev_active, lifetimes, li);
 		build_reserved(&reserved, &active, rmap);
 
 		struct val h = get_hint(hints, l.v);
@@ -315,10 +342,15 @@ static size_t build_rmap(struct vec *hints, struct vec *lifetimes,
 			max_callee_save = highest_sreg(f);
 
 		add_rewrite_rule(rmap, l.v, f);
+
+		/* store currently active in prev_active */
+		swap_lifetimes(&active, &prev_active);
+		vec_reset(&active);
 	}
 
 	vec_destroy(&active);
 	vec_destroy(&reserved);
+	vec_destroy(&prev_active);
 
 	return max_callee_save;
 }
@@ -457,7 +489,7 @@ static size_t do_call_saves(struct blk *b, struct vec *lifetimes,
 
 		vec_reset(&active);
 		vec_reset(&reserved);
-		build_active_between(&active, lifetimes, call_pos, call_pos);
+		build_active_between(&active, NULL, lifetimes, 0, call_pos, call_pos);
 		build_reserved(&reserved, &active, rmap);
 
 		/* what follows is a slight bit of index counting, a bit
diff --git a/src/ssa.c b/src/ssa.c
index 186d6b5..87bf453 100644
--- a/src/ssa.c
+++ b/src/ssa.c
@@ -34,24 +34,65 @@ static bool has_val(struct vec *map, struct val v)
 	return p.class != NOCLASS;
 }
 
+static bool entered(struct blk *b, int visited)
+{
+	return b->visited >= visited + 1;
+}
+
+static void enter(struct blk *b)
+{
+	b->visited++;
+}
+
+static bool done(struct blk *b, int visited)
+{
+	return b->visited >= visited + 2;
+}
+
+static void leave(struct blk *b)
+{
+	b->visited++;
+}
+
 static void build_params(struct blk *b, int visited)
 {
-	if (b->visited > visited)
+	if (done(b, visited))
 		return;
 
-	b->visited++;
+	/* recursive functionality made iterative by using an external
+	 * stack, just think of pushing to the stack as doing a recursive call
+	 * */
+	struct vec stack = vec_create(sizeof(struct blk *));
+	vec_append(&stack, &b);
 
+top:
+	if (vec_len(&stack) == 0) {
+		vec_destroy(&stack);
+		return;
+	}
+
+	b = vect_pop(struct blk *, stack);
 	if (return_blk(b)) {
 		b->s1 = NULL;
 		b->s2 = NULL;
 	}
 
-	if (b->s1)
-		build_params(b->s1, visited);
+	/* this is the first time here, queue up work for us */
+	if (!entered(b, visited)) {
+		/* put ourselves back onto the stack */
+		vec_append(&stack, &b);
+
+		if (b->s1)
+			vec_append(&stack, &b->s1);
+		if (b->s2)
+			vec_append(&stack, &b->s2);
 
-	if (b->s2)
-		build_params(b->s2, visited);
+		enter(b);
+		goto top;
+	}
 
+	/* second time through, do actual work now that dependencies (should) be
+	 * done */
 	struct vec generated = vec_create(sizeof(struct val));
 	struct vec forward = vec_create(sizeof(struct val));
 	struct vec required = vec_create(sizeof(struct val));
@@ -125,30 +166,50 @@ static void build_params(struct blk *b, int visited)
 	vec_destroy(&required);
 	vec_destroy(&forward);
 	vec_destroy(&generated);
+	leave(b); // mark us ready
+	goto top;
 }
 
 static void collect_params(struct blk *b, int visited)
 {
-	if (b->visited > visited)
+	if (done(b, visited))
 		return;
 
-	b->visited++;
+	struct vec stack = vec_create(sizeof(struct blk *));
+	vec_append(&stack, &b);
 
-	if (b->s1) {
-		collect_params(b->s1, visited);
-		foreach_blk_param(pi, b->s1->params) {
-			struct val p = blk_param_at(b->s1->params, pi);
-			vec_append(&b->args1, &p);
-		}
+top:
+	if (vec_len(&stack) == 0) {
+		vec_destroy(&stack);
+		return;
 	}
 
-	if (b->s2) {
-		collect_params(b->s2, visited);
-		foreach_blk_param(pi, b->s2->params) {
-			struct val p = blk_param_at(b->s2->params, pi);
-			vec_append(&b->args2, &p);
-		}
+	b = vect_pop(struct blk *, stack);
+	if (!entered(b, visited)) {
+		vec_append(&stack, &b);
+
+		if (b->s1)
+			vec_append(&stack, &b->s1);
+
+		if (b->s2)
+			vec_append(&stack, &b->s2);
+
+		enter(b);
+		goto top;
 	}
+
+	foreach_blk_param(pi, b->s1->params) {
+		struct val p = blk_param_at(b->s1->params, pi);
+		vec_append(&b->args1, &p);
+	}
+
+	foreach_blk_param(pi, b->s2->params) {
+		struct val p = blk_param_at(b->s2->params, pi);
+		vec_append(&b->args2, &p);
+	}
+
+	leave(b);
+	goto top;
 }
 
 static void add_rewrite_rule(struct vec *rmap, struct val from, struct val to)