From 8b407058485dbad82d670c6cbcacbe1d993fb4aa Mon Sep 17 00:00:00 2001 From: WormHeamer Date: Tue, 28 Oct 2025 18:42:28 -0400 Subject: remove Node.walked in favor of bit sets (1/32x the memory) --- Makefile | 2 +- doc/macros.txt | 7 ++++++- ir.c | 1 - ir.h | 19 +++++++++-------- main.c | 64 +++++++++++++++++++++++++++++++++++++++++++++------------- test.lang | 4 ---- 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 #include +#include #include #include #include @@ -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 -- cgit v1.2.3