add if statements

6 files changed, 126 insertions, 32 deletions

diff --git a/dynarr.h b/dynarr.h
index b5c52b6..73576f5 100644
--- a/dynarr.h
+++ b/dynarr.h
@@ -16,8 +16,8 @@
 
 #define ZDA_GROW(da, n, zn) ZDA_FIT(da, (da)->len + n, zn)
 
-#define ZDA_PUSH(da, v, zn)\
-	(ZDA_GROW(da, 1, zn)[(da)->len++] = (v))
+#define ZDA_PUSH(zn, da, ...)\
+	(ZDA_GROW(da, 1, zn)[(da)->len++] = (__VA_ARGS__))
 
 #define ZDA_INIT_CAP 32
 
diff --git a/ir.c b/ir.c
index e3d64f5..dd8b66c 100644
--- a/ir.c
+++ b/ir.c
@@ -64,11 +64,19 @@ void type_err(Node *n, Lexer *l) {
 		if (i > 0) str_cat(&s, S(", "), &l->arena);
 		str_cat(&s, type_desc(&IN(n, i)->val.type, &l->arena), &l->arena);
 	}
-	lex_error_at(l, n->src_pos, LE_ERROR, str_fmt(&l->arena, "type error (%S)", s));
+	lex_error_at(l, n->src_pos, LE_ERROR, str_fmt(&l->arena, "type error %s (%S)", node_type_name(n->type), s));
 }
 
 int type_check(Node *n) {
 	switch (n->type) {
+	case N_PHI:
+		n->val.type = (Type) { .lvl = T_TOP, .t = IN(n, 1)->val.type.t };
+		for (int i = 2; i < n->in.len; i++) {
+			if (!type_base_eql(&IN(n, i)->val.type, &n->val.type)) {
+				return 0;
+			}
+		}
+		return 1;
 	case N_OP_NEG:
 		n->val.type = (Type) { .lvl = T_TOP, .t = T_INT };
 		return CAR(n)->val.type.t == T_INT;
@@ -103,7 +111,7 @@ int type_check(Node *n) {
 const char *node_type_name(NodeType t) {
 	const char *names[] = {
 		"N/A",
-		"start",
+		"start", "if-else", "region", "phi", "stop",
 		"projection",
 		"return",
 		"keepalive",
@@ -163,12 +171,12 @@ void node_kill(Node *n, Proc *p) {
 }
 
 void node_add_out(Proc *p, Node *a, Node *b) {
-	ZDA_PUSH(&a->out, b, &p->arena);
+	ZDA_PUSH(&p->arena, &a->out, b);
 	b->refs++;
 }
 
 void node_add_in(Proc *p, Node *a, Node *b) {
-	ZDA_PUSH(&a->in, b, &p->arena);
+	ZDA_PUSH(&p->arena, &a->in, b);
 	b->refs++;
 }
 
@@ -745,6 +753,8 @@ void proc_init(Proc *proc, Str name) {
 		.t = T_TUPLE,
 		.next = NULL
 	};
+	proc->stop = node_new_empty(proc, N_STOP);
+	proc->ctrl = proc->start;
 	proc->keepalive = node_new_empty(proc, N_KEEPALIVE);
 	proc->name = name;
 }
@@ -823,3 +833,13 @@ NameBinding *scope_update(Scope *scope, Str name, Node *to, Proc *proc) {
 	b->node = to;
 	return b;
 }
+
+/* adds to keepalive so these aren't invalidated */
+void scope_collect(Scope *scope, Proc *proc, ScopeNameList *nl, Arena *arena) {
+	for (ScopeFrame *f = scope->tail; f; f = f->prev) {
+		for (NameBinding *b = f->latest; b; b = b->prev) {
+			node_add_out(proc, b->node, proc->keepalive);
+			ZDA_PUSH(arena, nl, (ScopeName) { b->name, b->node });
+		}
+	}
+}
diff --git a/ir.h b/ir.h
index 251c198..ff75163 100644
--- a/ir.h
+++ b/ir.h
@@ -12,6 +12,7 @@ typedef enum {
 	T_TOP, /* may or may not be a constant */
 	T_CONST, /* known compile-time constant */
 	T_BOT, /* known not a constant */
+	T_CTRL /* bottom of control flow */
 } TypeLevel;
 
 typedef enum {
@@ -48,7 +49,7 @@ void type_err(struct Node *n, Lexer *l);
 
 typedef enum {
 	N_NONE,
-	N_START,
+	N_START, N_IF_ELSE, N_REGION, N_PHI, N_STOP,
 	N_PROJ,
 	N_RETURN,
 	N_KEEPALIVE,
@@ -101,9 +102,16 @@ typedef struct {
 } Scope;
 
 typedef struct {
+	Str name;
+	Node *node;
+} ScopeName;
+
+typedef DYNARR(ScopeName) ScopeNameList;
+
+typedef struct {
 	Arena arena;
 	Str name;
-	Node *start, *stop, *keepalive;
+	Node *start, *stop, *ctrl, *keepalive;
 	Node *free_list;
 	Scope scope;
 } Proc;
@@ -144,5 +152,6 @@ ScopeFrame *scope_pop(Scope *scope, Proc *proc);
 NameBinding *scope_find(Scope *scope, Str name);
 NameBinding *scope_bind(Scope *scope, Str name, Node *value, LexSpan pos, Proc *proc);
 NameBinding *scope_update(Scope *scope, Str name, Node *to, Proc *proc);
+void scope_collect(Scope *scope, Proc *proc, ScopeNameList *nl, Arena *arena);
 
 #endif
diff --git a/lex.h b/lex.h
index a9820a1..dc23296 100644
--- a/lex.h
+++ b/lex.h
@@ -13,6 +13,8 @@
 	X(RETURN, "return")\
 	X(TRUE, "true")\
 	X(FALSE, "false")\
+	X(IF, "if")\
+	X(ELSE, "else")\
 	X(LBRACE, "{")\
 	X(RBRACE, "}")\
 	X(LPAREN, "(")\
diff --git a/main.c b/main.c
index e39c00b..6da1bf2 100644
--- a/main.c
+++ b/main.c
@@ -12,7 +12,7 @@
 #include "strio.h"
 #include "ir.h"
 
-int no_opt = 0;
+int no_opt = 1;
 
 typedef struct {
 	DYNARR(Proc) procs;
@@ -35,7 +35,9 @@ Node *parse_expr(Lexer *l, Proc *p);
 
 void parse_return(Lexer *l, Proc *p) {
 	lex_next(l);
-	p->stop = node_new(p, N_RETURN, p->start, parse_expr(l, p));
+	Node *n = node_new(p, N_RETURN, p->ctrl, parse_expr(l, p));
+	node_add(p, n, p->stop);
+	p->ctrl = n;
 }
 
 void parse_let(Lexer *l, Proc *p) {
@@ -57,13 +59,16 @@ recurse:
 void parse_stmt(Lexer *l, Proc *p);
 
 /* TODO: return node from this! */
-void parse_block(Lexer *l, Proc *p) {
+void parse_block(Lexer *l, Proc *p, ScopeNameList *nl) {
 	lex_next(l);
 	scope_push(&p->scope, p);
 	while (l->tok != TOK_RBRACE) {
 		lex_expected_not(l, TM_EOF);
 		parse_stmt(l, p);
 	}
+	if (nl) {
+		scope_collect(&p->scope, p, nl, &p->arena);
+	}
 	scope_pop(&p->scope, p);
 	lex_expected(l, TM_RBRACE);
 	lex_next(l);
@@ -80,6 +85,76 @@ void parse_assign(Lexer *l, Proc *p) {
 	}
 }
 
+void merge_scope(Proc *p, ScopeNameList *na, ScopeNameList *nb) {
+	for (ScopeFrame *f = p->scope.tail; f; f = f->prev) {
+		for (NameBinding *b = f->latest; b; b = b->prev) {
+			int i, j;
+			for (i = 0; i < na->len && !str_eql(na->data[i].name, b->name); i++);
+			for (j = 0; j < nb->len && !str_eql(nb->data[j].name, b->name); j++);
+			if (i >= na->len && j >= nb->len) continue; /* no change */
+			Node *phi;
+			if (i >= na->len) {
+				phi = node_new(p, N_PHI, p->ctrl, b->node, nb->data[j].node);
+			} else if (j >= na->len) {
+				phi = node_new(p, N_PHI, p->ctrl, na->data[i].node, b->node);
+			} else {
+				phi = node_new(p, N_PHI, p->ctrl, na->data[i].node, nb->data[j].node);
+			}
+			node_add(p, phi, p->keepalive);
+			node_remove(p, b->node, p->keepalive);
+			b->node = phi;
+		}
+	}
+
+	for (int i = 0; i < na->len; i++) node_remove(p, na->data[i].node, p->keepalive);
+	for (int i = 0; i < nb->len; i++) node_remove(p, nb->data[i].node, p->keepalive);
+}
+
+void parse_if(Lexer *l, Proc *p) {
+	lex_next(l);
+	Node *cond = parse_expr(l, p);
+	Node *ctrl_if = NULL, *ctrl_else = NULL;
+	Node *if_node = node_new(p, N_IF_ELSE, p->ctrl, cond);
+	if_node->val = (Value) {
+		.type = { T_TOP, T_TUPLE, NULL },
+		.tuple = {
+			.len = 2,
+			.cap = 0,
+			.data = (Value[2]) {
+				{ .type = { T_CTRL, T_NONE, NULL } },
+				{ .type = { T_CTRL, T_NONE, NULL } },
+			}
+		}
+	};
+	Node *if_true = node_new(p, N_PROJ, if_node);
+	Node *if_false = node_new(p, N_PROJ, if_node);
+	ScopeNameList scope_before = { 0 }, scope_true = { 0 }, scope_false = { 0 };
+	if_true->val.i = 0;
+	if_false->val.i = 1;
+	scope_collect(&p->scope, p, &scope_before, &p->arena);
+	NODE_KEEP(p, cond, {
+		p->ctrl = if_true;
+		lex_expected(l, TM_LBRACE);
+		parse_block(l, p, &scope_true);
+		ctrl_if = p->ctrl;
+		if (l->tok == TOK_ELSE) {
+			NODE_KEEP(p, ctrl_if, {
+				p->ctrl = if_false;
+				lex_expect(l, TM_LBRACE);
+				parse_block(l, p, &scope_false);
+				ctrl_else = p->ctrl;
+			});
+		}
+	});
+	if (ctrl_else) {
+		p->ctrl = node_new(p, N_REGION, ctrl_if, ctrl_else);
+		merge_scope(p, &scope_true, &scope_false);
+	} else {
+		p->ctrl = node_new(p, N_REGION, ctrl_if, if_false);
+		merge_scope(p, &scope_before, &scope_true);
+	}
+}
+
 void parse_stmt(Lexer *l, Proc *p) {
 	/* TODO */
 	(void)l;
@@ -91,18 +166,20 @@ void parse_stmt(Lexer *l, Proc *p) {
 		parse_let(l, p);
 		break;
 	case TOK_LBRACE:
-		parse_block(l, p);
+		parse_block(l, p, NULL);
 		break;
 	case TOK_IDENT:
 		parse_assign(l, p);
 		break;
+	case TOK_IF:
+		parse_if(l, p);
+		break;
 	default:
 		lex_expected(l, TM_RBRACE);
 		break;
 	}
 }
 
-
 Type parse_type(Lexer *l, Proc *proc) {
 	(void)proc;
 	Type t = { .lvl = T_BOT };
@@ -137,7 +214,7 @@ void parse_args_list(Lexer *l, Proc *proc) {
 		lex_expect(l, TM_IDENT | TM_COMMA);
 		if (l->tok == TOK_COMMA) continue;
 		Value v = (Value) { .type = parse_type(l, proc) };
-		ZDA_PUSH(&start->val.tuple, v, &proc->arena);
+		ZDA_PUSH(&proc->arena, &start->val.tuple, v);
 		lex_expected(l, TM_RPAREN | TM_COMMA);
 		for (int j = 0; j < id; j++) {
 			Node *proj = node_new(proc, N_PROJ, proc->start);
diff --git a/test.lang b/test.lang
index 94869c8..00334c9 100644
--- a/test.lang
+++ b/test.lang
@@ -1,20 +1,6 @@
-/* comments! */
-
-/*
- * var f proc(i32)
- * var g func(i32) i32
- * let x = g
- */
-
-// also single-line now
-
-proc fib(x i64) {
-	return x & 1023
-}
-
 proc main(a, b i64) {
-	// let x = (a + -a) = (a xor a)
-	// let y = (a + a) = (a * 2)
-	// return (x & y & (a = a) & (a = ~a)) | ((a + a) = (a + 2))
-	return a - (b + b) - a
+	if a > 5 {
+		a := a - 5
+	}
+	return a
 }