attempt at optimizing regions after graph generation....

4 files changed, 133 insertions, 31 deletions

diff --git a/ir.c b/ir.c
index dd7a8ac..f895323 100644
--- a/ir.c
+++ b/ir.c
@@ -172,6 +172,15 @@ void node_add_in(Proc *p, Node *a, Node *b) {
 	if (b) b->refs++;
 }
 
+void node_set_in(Proc *p, Node *n, int idx, Node *to) {
+	Node *in = n->in.data[idx];
+	if (in) in->refs--;
+	node_del_out(in, n);
+	node_add_out(p, to, n);
+	n->in.data[0] = to;
+	if (in->out.len < 1) node_kill(in, p);
+}
+
 void node_add(Proc *p, Node *src, Node *dest) {
 	node_add_in(p, dest, src);
 	if (!src) return;
@@ -712,11 +721,11 @@ zero_no_effect:	if (node_eql_i64(CAR(n), 0)) return CDR(n);
 
 	case N_PROJ:
 		if (T(CTRL(n), N_IF_ELSE) && CTRL(n)->type.t == T_TUPLE) {
-			if (CTRL(n)->val.tuple.data[n->val.i].type.lvl == T_XCTRL) {
+			/*if (CTRL(n)->val.tuple.data[n->val.i].type.lvl == T_XCTRL) {
 				return node_new_lit(p, (Value) {
 					.type = { .lvl = T_XCTRL, .t = T_NONE }
 				});
-			}
+			}*/
 			if (CTRL(n)->val.tuple.data[(n->val.i + 1) % CTRL(n)->val.tuple.len].type.lvl == T_XCTRL) {
 				return CTRL(CTRL(n));
 			}
@@ -734,26 +743,24 @@ zero_no_effect:	if (node_eql_i64(CAR(n), 0)) return CDR(n);
 		}
 		break;
 
-	case N_REGION:
-		{
-			int live_in = 0;
+	case N_REGION: if (0) {
+		int live_in = 0;
+		for (int i = 0; i < n->in.len; i++) {
+			if (IN(n, i)->type.lvl != T_XCTRL) live_in++;
+		}
+		if (live_in == 1) {
 			for (int i = 0; i < n->in.len; i++) {
-				if (IN(n, i)->type.lvl != T_XCTRL) live_in++;
-			}
-			if (live_in == 1) {
-				for (int i = 0; i < n->in.len; i++) {
-					if (IN(n, i)->type.lvl != T_XCTRL) {
-						return IN(n, i);
-					}
+				if (IN(n, i)->type.lvl != T_XCTRL) {
+					return IN(n, i);
 				}
 			}
-			if (live_in == 0) {
-				return node_new_lit(p, (Value) {
-					.type = { .lvl = T_XCTRL, .t = T_NONE }
-				});
-			}
 		}
-		break;
+		if (live_in == 0) {
+			return node_new_lit(p, (Value) {
+				.type = { .lvl = T_XCTRL, .t = T_NONE }
+			});
+		}
+	} break;
 
 	default:
 		break;
@@ -817,7 +824,7 @@ void proc_init(Proc *proc, Str name) {
 		.t = T_TUPLE,
 		.next = NULL
 	};
-	proc->stop = node_new(proc, N_STOP, NULL);
+	proc->stop = node_new_empty(proc, N_STOP);
 	proc->ctrl = proc->start;
 	proc->keepalive = node_new(proc, N_KEEPALIVE, NULL);
 	proc->name = name;
diff --git a/ir.h b/ir.h
index 54c56e2..adb1039 100644
--- a/ir.h
+++ b/ir.h
@@ -189,6 +189,7 @@ void node_kill(Node *n, Proc *p);
 void node_add(Proc *p, Node *src, Node *dest);
 void node_add_out(Proc *p, Node *a, Node *b);
 void node_add_in(Proc *p, Node *a, Node *b);
+void node_set_in(Proc *p, Node *n, int idx, Node *to);
 
 void node_remove(Proc *p, Node *src, Node *dest);
 Node *node_new_empty(Proc *p, NodeType t);
diff --git a/main.c b/main.c
index 8bb7fda..26f9534 100644
--- a/main.c
+++ b/main.c
@@ -241,7 +241,9 @@ void parse_if(Lexer *l, Proc *p) {
 	ctrl(p, if_true);
 	//assert(if_true->in.len > 0);
 	lex_expected(l, TM_LBRACE);
+	int pos = l->pos.ofs;
 	parse_block(l, p, &scope_true);
+	if_true->src_pos = (LexSpan) { .ofs = pos, .n = l->pos.ofs - pos };
 	ctrl_if = p->ctrl;
 	node_add(p, ctrl_if, p->keepalive);
 	//assert(ctrl_if->in.len > 0);
@@ -251,7 +253,9 @@ void parse_if(Lexer *l, Proc *p) {
 		}
 		ctrl(p, if_false);
 		lex_expect(l, TM_LBRACE);
+		pos = l->pos.ofs;
 		parse_block(l, p, &scope_false);
+		if_false->src_pos = (LexSpan) { .ofs = pos, .n = l->pos.ofs - pos };
 		ctrl_else = p->ctrl;
 		node_add(p, ctrl_else, p->keepalive);
 	}
@@ -379,6 +383,92 @@ void parse_args_list(Lexer *l, Proc *proc) {
 	lex_next(l);
 }
 
+Node *find_return(Node *n) {
+	if (n->op == N_RETURN) return n;
+	for (int i = 0; i < n->out.len; i++) {
+		Node *r = find_return(n->out.data[i]);
+		if (r) return r;
+	}
+	return NULL;
+}
+
+void proc_opt_fwd(Proc *p, Lexer *l, Node *n) {
+	fprintf(stderr, "%d %s\n", n->id, node_type_name(n->op));
+	if (n->walked == 2) return;
+	n->walked = 2;
+	switch (n->op) {
+	case N_START:
+		for (int i = 0; i < n->out.len; i++) {
+			if (!(NMASK(n->out.data[i]->op) & (NM_LIT | NM_PROJ))) {
+				proc_opt_fwd(p, l, n->out.data[i]);
+				break;
+			}
+		}
+		break;
+	case N_IF_ELSE:
+		if (n->out.len < 2) {
+			lex_error_at(l, n->src_pos, LE_ERROR, S("not all codepaths return"));
+		}
+		for (int i = 0; i < n->out.len; i++) {
+			Node *r = find_return(n->out.data[i]);
+			if (!r) {
+				lex_error_at(l, n->out.data[i]->src_pos, LE_ERROR, S("not all codepaths return"));
+			}
+			proc_opt_fwd(p, l, n->out.data[i]);
+		}
+		break;
+	case N_PROJ:
+		proc_opt_fwd(p, l, n->out.data[0]);
+		break;
+	case N_REGION:
+		/* cull empty if else */
+		if (n->out.len == 1 && n->in.len == 2
+				&& IN(n,0)->op == N_PROJ
+				&& IN(n,1)->op == N_PROJ
+				&& CTRL(IN(n,0)) == CTRL(IN(n,1))
+				&& CTRL(IN(n,0))->op == N_IF_ELSE) {
+			assert(n->out.data[0]->op != N_PHI);
+			assert(n->out.data[0]->in.data[0] == n);
+			Node *new_ctrl = CTRL(CTRL(CTRL(n)));
+			Node *out = n->out.data[0];
+			//node_remove(p, new_ctrl, CTRL(CTRL(n)));
+			// ^ is that needed?
+			// idea was to prevent deleting stuff unnecessarily,
+			// but i think the new node_set_in() function works
+			// completely fine for that original purpose.
+			node_set_in(p, out, 0, new_ctrl);
+			proc_opt_fwd(p, l, new_ctrl);
+			return;
+		}
+		for (int i = 0; i < n->out.len; i++) {
+			if (n->out.data[i]->op != N_PHI) {
+				proc_opt_fwd(p, l, n->out.data[i]);
+			}
+		}
+		break;
+	default:
+		break;
+	}
+}
+
+void proc_opt(Proc *p, Lexer *l) {
+	fprintf(stderr, "%ld\n", p->stop->in.len);
+	if (p->stop->in.len == 0) {
+
+		if (p->ret_type.t != T_NONE) {
+			lex_error(l, LE_ERROR, str_fmt(&p->arena, "no return statement in function expecting %S", type_desc(&p->ret_type, &p->arena)));
+		}
+	}
+	for (int i = 0; i < p->start->out.len; i++) {
+		Node *n = p->start->out.data[i];
+		if (n->op == N_LIT && n->out.len < 1) {
+			node_kill(n, p);
+			i--;
+		}
+	}
+	proc_opt_fwd(p, l, p->start);
+}
+
 Proc *parse_proc(Lexer *l, Unit *u) {
 	int has_ret = l->tok == TOK_FUNC;
 	DA_FIT(&u->procs, u->procs.len + 1);
@@ -404,6 +494,7 @@ Proc *parse_proc(Lexer *l, Unit *u) {
 	scope_pop(&proc->scope, proc);
 	lex_expected(l, TM_RBRACE);
 	lex_next(l);
+	proc_opt(proc, l);
 	return proc;
 }
 
@@ -530,8 +621,13 @@ void parse_unit(Lexer *l) {
 
 /* graph output */
 
+/* TODO: Print at every stage of graph compilation and generate a frame for
+ * each, so problems can be debugged visually as they occur.
+ */
+
 void node_print(Node *n, Proc *p) {
-	if (n->walked) return;
+	if (n->walked == 1) return;
+	n->walked = 1;
 	if (n->op == N_START) {
 		Str s = S("");
 		int c = n->val.tuple.len;
@@ -566,7 +662,6 @@ void node_print(Node *n, Proc *p) {
 		printf("\t%d [label=\"%s\", shape=record]", n->id, node_type_name(n->op));
 	}
 	printf("\n");
-	n->walked = 1;
 	for (int i = 0; i < n->out.len; i++) {
 		Node *o = n->out.data[i];
 		if (o->op == N_LIT) {
diff --git a/test.lang b/test.lang
index f46b8a0..5535a4e 100644
--- a/test.lang
+++ b/test.lang
@@ -1,17 +1,16 @@
 func main(a, b i64) i64 {
-	/*if a = b {
+	if a = b {
 		let t = a
 		a := b
 		b := t
 	} else {
-		let t = a
-		a := b
-		b := t
-	}*/
-	/* TODO: error on failing to return from a function */
-	if a < b {
-		return 237 + a + 812734 + b + 81753 + 2389
-	} else {
-		return 1 + a + 7 + 123897
+		a := 5
+		b := 10
+		if a = b {
+			let t = a
+			a := b
+			b := t
+		}
 	}
+	return a + b
 }