almost there...

5 files changed, 134 insertions, 44 deletions

diff --git a/main.c b/main.c
index debb0ae..4f48ade 100644
--- a/main.c
+++ b/main.c
@@ -127,7 +127,7 @@ recurse:
 void parse_stmt(Lexer *l, Proc *p);
 
 /* TODO: return node from this! */
-void parse_block(Lexer *l, Proc *p, ScopeNameList *nl) {
+void parse_block(Lexer *l, Proc *p) {
 	Graph *g = &p->graph;
 	lex_next(l);
 	arena_reset(&p->scratch);
@@ -136,9 +136,6 @@ void parse_block(Lexer *l, Proc *p, ScopeNameList *nl) {
 		lex_expected_not(l, TM_EOF);
 		parse_stmt(l, p);
 	}
-	if (nl) {
-		scope_collect(&p->scope, g, nl, &p->scratch);
-	}
 	scope_pop(&p->scope, g);
 	lex_expected(l, TM_RBRACE);
 	lex_next(l);
@@ -163,7 +160,7 @@ void parse_assign(Lexer *l, Proc *p) {
 				str_fmt(&p->scratch, "possibly uninitialized %S",
 					type_desc(&e->type, &p->scratch)));
 	}
-	scope_update(b, e, &p->graph);
+	scope_update(&p->scope, b, e, &p->graph);
 }
 
 /* TODO: Implement a better system for this.
@@ -199,6 +196,7 @@ void parse_assign(Lexer *l, Proc *p) {
  *
  */
 
+#if 0
 void merge_scope(Lexer *l, Proc *p, Node *region, ScopeNameList *before, ScopeNameList *ntrue, ScopeNameList *nfalse) {
 	Graph *g = &p->graph;
 	for (int i = 0; i < before->len; i++) {
@@ -226,6 +224,7 @@ void merge_scope(Lexer *l, Proc *p, Node *region, ScopeNameList *before, ScopeNa
 		scope_update(b, phi, g);
 	}
 }
+#endif
 
 /* TODO: find out a way to encode known relations between nodes, based on the
  * conditional, within the body of an if statement --- e.g., for a statement
@@ -272,31 +271,41 @@ void parse_if(Lexer *l, Proc *p) {
 	assert(if_false->in.len > 0);
 	node_add(g, if_true, g->keepalive);
 	node_add(g, if_false, g->keepalive);
-	ScopeNameList scope_before = { 0 }, scope_true = { 0 }, scope_false = { 0 };
-	scope_collect(&p->scope, g, &scope_before, &p->scratch);
+
+	ScopeChangeList chg_if = { 0 };
+	ScopeChangeList chg_else = { 0 };
+
 	if (cond->type.lvl == T_CONST) {
 		if (cond->val.i) if_false->type.lvl = T_XCTRL;
 		else if_true->type.lvl = T_XCTRL;
 	}
+
 	ctrl(g, if_true);
 	lex_expected(l, TM_LBRACE);
 	int pos = l->pos.ofs;
-	parse_block(l, p, &scope_true);
+
+	scope_changelist_push(&p->scope, &chg_if, &p->scratch);
+	parse_block(l, p);
+	scope_changelist_pop(&p->scope, g);
+
 	if_true->src_pos = (LexSpan) { .ofs = pos, .n = l->pos.ofs - pos };
 	ctrl_if = g->ctrl;
 	node_add(g, ctrl_if, g->keepalive);
+
 	if (l->tok == TOK_ELSE) {
-		for (int i = 0; i < scope_before.len; i++) {
-			scope_update(scope_find(&p->scope, scope_before.data[i].name), scope_before.data[i].node, g);
-		}
 		ctrl(g, if_false);
 		lex_expect(l, TM_LBRACE);
 		pos = l->pos.ofs;
-		parse_block(l, p, &scope_false);
+
+		scope_changelist_push(&p->scope, &chg_else, &p->scratch);
+		parse_block(l, p);
+		scope_changelist_pop(&p->scope, g);
+
 		if_false->src_pos = (LexSpan) { .ofs = pos, .n = l->pos.ofs - pos };
 		ctrl_else = g->ctrl;
 		node_add(g, ctrl_else, g->keepalive);
 	}
+
 	Node *region;
 	if (ctrl_else) {
 		assert(ctrl_if);
@@ -320,11 +329,12 @@ void parse_if(Lexer *l, Proc *p) {
 	assert(g->ctrl->in.len > 0);
 	assert(region->in.data[0]);
 	assert(region->in.data[1]);
-	merge_scope(l, p, region, &scope_before, &scope_true, &scope_false);
-	scope_uncollect(&p->scope, g, &scope_true);
-	scope_uncollect(&p->scope, g, &scope_false);
-	scope_uncollect(&p->scope, g, &scope_before);
+
+	scope_changelist_merge(&p->scope, &chg_if, &chg_else, region, g, &p->scratch);
+	scope_changelist_discard(&chg_if, g);
+	scope_changelist_discard(&chg_else, g);
 	node_del_out(region, g->keepalive);
+
 	/* make sure we're not orphaning any phi nodes*/
 	if (g->ctrl->out.len < 1) {
 		ctrl(g, node_peephole(g->ctrl, g, l));
@@ -342,7 +352,7 @@ void parse_stmt(Lexer *l, Proc *p) {
 		parse_let(l, p);
 		break;
 	case TOK_LBRACE:
-		parse_block(l, p, NULL);
+		parse_block(l, p);
 		break;
 	case TOK_IDENT:
 		parse_assign(l, p);
diff --git a/proc.c b/proc.c
index 0877a91..7e983ca 100644
--- a/proc.c
+++ b/proc.c
@@ -102,26 +102,98 @@ NameBinding *scope_bind(Scope *scope, Str name, Node *value, LexSpan pos, Graph
 	return prev;
 }
 
-NameBinding *scope_update(NameBinding *b, Node *to, Graph *g) {
+NameBinding *scope_update(Scope *scope, NameBinding *b, Node *to, Graph *g) {
 	Node *n = b->node;
+	unsigned nestlvl = scope->nestlvl;
+	for (ScopeChangeList *l = scope->changes; l; l = l->prev) {
+		if (b->nestlvl < nestlvl) {
+			scope_changelist_update(l, b, n, to, g);
+		}
+		nestlvl--;
+	}
 	node_add(g, to, g->keepalive);
 	b->node = to;
 	node_remove(g, n, g->keepalive);
 	return b;
 }
 
-/* adds to keepalive so these aren't invalidated */
-void scope_collect(Scope *scope, Graph *g, ScopeNameList *nl, Arena *arena) {
-	for (ScopeFrame *f = scope->tail; f; f = f->prev) {
-		for (NameBinding *b = f->latest; b; b = b->prev) {
-			node_add(g, b->node, g->keepalive);
-			ZDA_PUSH(arena, nl, (ScopeName) { b->name, b->node });
+void scope_changelist_update(ScopeChangeList *l, NameBinding *b, Node *from, Node *to, Graph *g) {
+	for (unsigned i = 0; i < l->n; i++) {
+		ScopeChange *chg = XAR_GET(l, i);
+		if (chg->bind == b) {
+			node_add(g, to, g->keepalive);
+			node_remove(g, chg->to, g->keepalive);
+			chg->to = to;
+			return;
+		}
+	}
+	ScopeChange *chg = XAR_PUT(l, l->n++, l->arena);
+	node_add(g, from, g->keepalive);
+	node_add(g, to, g->keepalive);
+	chg->bind = b;
+	chg->from = from;
+	chg->to = to;
+}
+
+void scope_changelist_push(Scope *scope, ScopeChangeList *l, Arena *a) {
+	l->arena = a;
+	l->prev = scope->changes;
+	scope->changes = l;
+	scope->nestlvl++;
+}
+
+void scope_changelist_pop(Scope *scope, Graph *g) {
+	ScopeChangeList *l = scope->changes;
+	scope->changes = l->prev;
+	scope->nestlvl--;
+	for (unsigned i = 0; i < l->n; i++) {
+		ScopeChange *chg = XAR_GET(l, i);
+		scope_update(scope, chg->bind, chg->from, g);
+	}
+}
+
+#include <stdio.h>
+/* TODO: implement merge, probably will need scratch arena to build up
+ * a Xar of something like struct { NameBinding *b; Node *y, *n; }. if
+ * no match for the given bind is found in the opposite change list,
+ * it gets the "from" value found in the other.
+ **/
+typedef struct {
+	NameBinding *b;
+	Node *y, *n;
+} MergeChange;
+void scope_changelist_merge(Scope *scope, ScopeChangeList *y, ScopeChangeList *n, Node *region, Graph *graph, Arena *scratch) {
+	MergeChange *m = new_arr(scratch, MergeChange, y->n + n->n);
+	unsigned c = 0;
+	for (unsigned i = 0; i < y->n; i++) {
+		ScopeChange *chg = XAR_GET(y, i);
+		m[c].b = chg->bind;
+		m[c].y = chg->to;
+		m[c].n = chg->from;
+		c++;
+	}
+	unsigned yc = c;
+	for (unsigned i = 0; i < n->n; i++) {
+		ScopeChange *chg = XAR_GET(n, i);
+		for (unsigned j = 0; j < yc; j++) {
+			if (m[j].b == chg->bind) {
+				m[j].n = chg->to;
+				goto next;
+			}
 		}
+		m[c].b = chg->bind;
+		m[c].y = chg->from;
+		m[c].n = chg->to;
+		c++;
+next:
 	}
+	fprintf(stderr, "%u\n", c);
 }
 
-void scope_uncollect(Scope *scope, Graph *g, ScopeNameList *nl) {
-	for (int i = 0; i < nl->len; i++) {
-		node_remove(g, nl->data[i].node, g->keepalive);
+void scope_changelist_discard(ScopeChangeList *l, Graph *g) {
+	for (unsigned i = 0; i < l->n; i++) {
+		ScopeChange *chg = XAR_GET(l, i);
+		node_remove(g, chg->from, g->keepalive);
+		node_remove(g, chg->to, g->keepalive);
 	}
 }
diff --git a/proc.h b/proc.h
index 0aaa5dc..3ef49a9 100644
--- a/proc.h
+++ b/proc.h
@@ -9,6 +9,7 @@ typedef struct NameBinding {
 	LexSpan src_pos;
 	Str name;
 	Node *node;
+	unsigned nestlvl;
 } NameBinding;
 
 typedef struct ScopeFrame {
@@ -17,35 +18,36 @@ typedef struct ScopeFrame {
 } ScopeFrame;
 
 typedef struct {
-	Str name;
-	Value *from, *to;
+	NameBinding *bind;
+	Node *from, *to;
 	LexSpan from_pos, to_pos;
 } ScopeChange;
 
-typedef XAR(ScopeChange) ScopeChangeList;
-
-typedef struct {
-	Str name;
-	Value *from, *to;
-	LexSpan from_pos, to_pos;
-} ScopeChange;
-
-typedef struct {
-	Arena *arena;
+typedef struct ScopeChangeList {
 	XAR(ScopeChange);
+	struct ScopeChangeList *prev;
+	Arena *arena;
 } ScopeChangeList;
 
 typedef struct {
 	Arena *arena;
 	ScopeFrame *tail, *free_scope;
 	NameBinding *free_bind;
+	ScopeChangeList *changes;
+	unsigned nestlvl;
 } Scope;
 
 ScopeFrame *scope_push(Scope *scope);
 ScopeFrame *scope_pop(Scope *scope, Graph *g);
 NameBinding *scope_find(Scope *scope, Str name);
 NameBinding *scope_bind(Scope *scope, Str name, Node *value, LexSpan pos, Graph *g);
-NameBinding *scope_update(NameBinding *b, Node *to, Graph *g);
+NameBinding *scope_update(Scope *scope, NameBinding *b, Node *to, Graph *g);
+
+void scope_changelist_update(ScopeChangeList *l, NameBinding *b, Node *from, Node *to, Graph *g);
+void scope_changelist_push(Scope *scope, ScopeChangeList *l, Arena *a);
+void scope_changelist_pop(Scope *scope, Graph *g);
+void scope_changelist_merge(Scope *scope, ScopeChangeList *y, ScopeChangeList *n, Node *region, Graph *graph, Arena *scratch);
+void scope_changelist_discard(ScopeChangeList *l, Graph *g);
 
 typedef struct {
 	Str name;
diff --git a/test.lang b/test.lang
index b59ffe0..6dc6a5b 100644
--- a/test.lang
+++ b/test.lang
@@ -1,3 +1,9 @@
-func main(a, b, c i64) i64 {
-	return b xor ((a xor b) xor (b xor c) xor b)
+func main(a, b i64) i64 {
+	if a < b {
+		a := 4
+	} else {
+		a := 2
+		b := 5
+	}
+	return a + b
 }
diff --git a/xar.h b/xar.h
index e448889..e7b80e4 100644
--- a/xar.h
+++ b/xar.h
@@ -11,11 +11,11 @@
 #define XAR_MAX_DOUBLE 26
 
 typedef struct {
-	int n, chunks;
+	uint32_t n, chunks;
 	void *chunk[XAR_MAX_DOUBLE];
 } XarHdr;
 
-#define XAR(T) struct { int n, chunks; T *chunk[XAR_MAX_DOUBLE]; }
+#define XAR(T) struct { uint32_t n, chunks; T *chunk[XAR_MAX_DOUBLE]; }
 #define XAR_GET_T(xar, T, idx) (T*)(xar_get((XarHdr*)(xar), idx, sizeof(T)))
 #define XAR_PUT_T(xar, T, idx, a) (T*)(xar_put((XarHdr*)(xar), idx, sizeof(T), a))
 #define XAR_GET(xar, idx) XAR_GET_T(xar, typeof(**(xar)->chunk), idx)