diff options
| -rw-r--r-- | Makefile | 2 | ||||
| -rw-r--r-- | doc/macros.txt | 7 | ||||
| -rw-r--r-- | ir.c | 1 | ||||
| -rw-r--r-- | ir.h | 19 | ||||
| -rw-r--r-- | main.c | 64 | ||||
| -rw-r--r-- | test.lang | 4 |
6 files changed, 66 insertions, 31 deletions
@@ -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, /) @@ -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 { @@ -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) */ @@ -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; @@ -1,7 +1,3 @@ -func square(x i64) i64 { - return x * x -} - func main(a, b i64) i64 { if a < b { let t = a |