remove Node.walked in favor of bit sets (1/32x the memory)HEADmaster

6 files changed, 66 insertions, 31 deletions

diff --git a/Makefile b/Makefile
index 265c2f9..01b4bbf 100644
--- a/Makefile
+++ b/Makefile
@@ -10,7 +10,7 @@ OBJ != find -type f -name '*.c' | sed 's/\.c$$/.o/'
 DEBUG = 0
 GDB != which gf2 2> /dev/null || which gdb
 
-CFLAGS_0 = -Os
+CFLAGS_0 = -Os -DNDEBUG
 CFLAGS_1 = -O0 -g3 -fsanitize=undefined
 LDFLAGS_1 = -g3 -fsanitize=undefined
 LDFLAGS_0 = -s
diff --git a/doc/macros.txt b/doc/macros.txt
index f39a30b..7b3c697 100644
--- a/doc/macros.txt
+++ b/doc/macros.txt
@@ -5,7 +5,7 @@
 
 macro SWAP($a, $b) {
 	let $tmp = $a
-	$a := b
+	$a := $b
 	$b := $tmp
 }
 
@@ -23,3 +23,8 @@ macro V2OP($name, $op) {
 		return vec2 { a.x $op b.x, a.y $op b.y }
 	}
 }
+
+V2OP(add, +)
+V2OP(sub, -)
+V2OP(mul, *)
+V2OP(div, /)
diff --git a/ir.c b/ir.c
index 31a090e..cde14a4 100644
--- a/ir.c
+++ b/ir.c
@@ -159,7 +159,6 @@ Node *node_new_empty(Graph *p, NodeType t) {
 		p->pool->free_list = n->prev_free;
 		n->in.len = 0;
 		n->out.len = 0;
-		n->walked = 0;
 		n->src_pos = (LexSpan) { 0 };
 		n->val = (Value) { 0 };
 	} else {
diff --git a/ir.h b/ir.h
index ae91b6c..403e054 100644
--- a/ir.h
+++ b/ir.h
@@ -110,21 +110,20 @@ typedef struct {
 } NodeList;
 
 typedef struct Node {
+	u32 id;
+	NodeType op;
 	union {
 		struct Node *prev_free;
 		struct {
-			NodeList in; /* note: index 0 used for control flow */
-			NodeList out;
-			int walked;
-			LexSpan src_pos;
-			union {
-				Type type;
-				Value val;
-			};
+			/* index 0 of in is control */
+			NodeList in, out;
 		};
 	};
-	int id;
-	NodeType op;
+	LexSpan src_pos;
+	union {
+		Type type;
+		Value val;
+	};
 } Node;
 
 /* convenience macros (lisp-inspired lol) */
diff --git a/main.c b/main.c
index 4c6c274..d33d3a0 100644
--- a/main.c
+++ b/main.c
@@ -1,5 +1,6 @@
 #include <stdio.h>
 #include <stdint.h>
+#include <stdbit.h>
 #include <stddef.h>
 #include <stdlib.h>
 #include <string.h>
@@ -16,6 +17,39 @@
 
 int no_opt = 0;
 
+/* bit set */
+
+typedef struct {
+	u64 cap;
+	u64 *data;
+} BitSet;
+
+void bitset_fit(BitSet *s, u32 sz, Arena *a) {
+	if (s->cap >= sz) return;
+	u32 c = stdc_bit_ceil(sz);
+	s->data = resize(a, s->data, s->cap, c);
+	for (u32 i = s->cap; i < c; i++) s->data[i] = 0;
+	s->cap = c;
+}
+
+static inline int bitset_has(BitSet *s, u32 n) {
+	if (n / 64 >= s->cap) return 0;
+	return !!((1L << (n & 63)) & s->data[n / 64]);
+}
+
+static inline void bitset_add(BitSet *s, u32 n, Arena *a) {
+	bitset_fit(s, (n / 64) + 1, a);
+	s->data[n / 64] |= (1L << (n & 63));
+}
+
+static inline void bitset_del(BitSet *s, u32 n) {
+	if (bitset_has(s, n)) {
+		s->data[n / 64] &= ~(1L << (n & 63));
+	}
+}
+
+/* units */
+
 typedef struct {
 	Arena *arena;
 	XAR(Proc) procs;
@@ -345,14 +379,14 @@ Node *find_return(Node *n) {
 	return NULL;
 }
 
-void proc_opt_fwd(Proc *p, Lexer *l, Node *n) {
+void proc_opt_fwd(Proc *p, Lexer *l, Node *n, BitSet *walked) {
 	Graph *g = &p->graph;
-	if (n->walked == 2) return;
-	n->walked = 2;
+	if (bitset_has(walked, n->id)) return;
+	bitset_add(walked, n->id, &p->scratch);
 	switch (n->op) {
 	case N_START:
 		for (u32 i = 0; i < n->out.len; i++) {
-			proc_opt_fwd(p, l, OUT(n, i));
+			proc_opt_fwd(p, l, OUT(n, i), walked);
 		}
 		break;
 	case N_IF_ELSE:
@@ -364,11 +398,11 @@ void proc_opt_fwd(Proc *p, Lexer *l, Node *n) {
 			if (!r) {
 				lex_error_at(l, OUT(n, i)->src_pos, LE_ERROR, S("not all codepaths return"));
 			}
-			proc_opt_fwd(p, l, OUT(n, i));
+			proc_opt_fwd(p, l, OUT(n, i), walked);
 		}
 		break;
 	case N_PROJ:
-		proc_opt_fwd(p, l, OUT(n, 0));
+		proc_opt_fwd(p, l, OUT(n, 0), walked);
 		break;
 	case N_REGION:
 		/* cull empty if else */
@@ -382,12 +416,12 @@ void proc_opt_fwd(Proc *p, Lexer *l, Node *n) {
 			Node *new_ctrl = CTRL(CTRL(CTRL(n)));
 			Node *out = OUT(n, 0);
 			node_set_in(g, out, 0, new_ctrl);
-			proc_opt_fwd(p, l, new_ctrl);
+			proc_opt_fwd(p, l, new_ctrl, walked);
 			return;
 		}
 		for (u32 i = 0; i < n->out.len; i++) {
 			if (OUT(n, i)->op != N_PHI) {
-				proc_opt_fwd(p, l, OUT(n, i));
+				proc_opt_fwd(p, l, OUT(n, i), walked);
 			}
 		}
 		break;
@@ -410,7 +444,8 @@ void proc_opt(Proc *p, Lexer *l) {
 			i--;
 		}
 	}
-	proc_opt_fwd(p, l, g->start);
+	BitSet walked = { 0 };
+	proc_opt_fwd(p, l, g->start, &walked);
 }
 
 Proc *parse_proc(Lexer *l, Unit *u) {
@@ -579,9 +614,9 @@ void parse_unit(Lexer *l, Unit *u) {
  * each, so problems can be debugged visually as they occur.
  */
 
-void node_print(Node *n, Proc *p) {
-	if (n->walked == 1) return;
-	n->walked = 1;
+void node_print(Node *n, Proc *p, BitSet *walked) {
+	if (bitset_has(walked, n->id)) return;
+	bitset_add(walked, n->id, &p->scratch);
 	if (n->op == N_START) {
 		Str s = S("");
 		int c = n->val.tuple.len;
@@ -634,16 +669,17 @@ void node_print(Node *n, Proc *p) {
 		}
 	}
 	for (u32 i = 0; i < n->out.len; i++) {
-		node_print(OUT(n, i), p);
+		node_print(OUT(n, i), p, walked);
 	}
 }
 
 void proc_print(Proc *p) {
+	BitSet walked = { 0 };
 	Graph *g = &p->graph;
 	if (g->start) {
 		Str d = type_desc(&p->ret_type, &p->scratch);
 		printf("\t\"%.*s %.*s\" -> %d\n", (int)p->name.n, p->name.s, (int)d.n, d.s, g->start->id);
-		node_print(g->start, p);
+		node_print(g->start, p, &walked);
 		if (no_opt) {
 			for (NameBinding *b = p->scope.free_bind; b; b = b->prev) {
 				uint64_t id = (uintptr_t)b->node;
diff --git a/test.lang b/test.lang
index 11f09d3..e57f630 100644
--- a/test.lang
+++ b/test.lang
@@ -1,7 +1,3 @@
-func square(x i64) i64 {
-	return x * x
-}
-
 func main(a, b i64) i64 {
 	if a < b {
 		let t = a