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

1 files changed, 50 insertions, 14 deletions

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;