diff options
| -rw-r--r-- | ir.c | 149 | ||||
| -rw-r--r-- | ir.h | 94 | ||||
| -rw-r--r-- | main.c | 177 | ||||
| -rw-r--r-- | peephole.c | 6 | ||||
| -rw-r--r-- | peephole.h | 2 | ||||
| -rw-r--r-- | proc.c | 113 | ||||
| -rw-r--r-- | proc.h | 51 |
7 files changed, 306 insertions, 286 deletions
@@ -15,12 +15,12 @@ const char *node_type_name(NodeType t) { return names[t]; } -void node_die(Node *n, Proc *p) { +void node_die(Node *n, Graph *p) { assert(n->refs == 0); assert(n->op != N_DEAD); n->op = N_DEAD; - n->prev_free = p->free_list; - p->free_list = n; + n->prev_free = p->pool->free_list; + p->pool->free_list = n; } void node_del_out(Node *n, Node *p) { @@ -49,7 +49,7 @@ void node_del_in(Node *n, Node *p) { } } -void node_kill(Node *n, Proc *p) { +void node_kill(Node *n, Graph *p) { if (p->ctrl == n) { /* probably this is fine */ p->ctrl = CTRL(n); @@ -59,17 +59,17 @@ void node_kill(Node *n, Proc *p) { assert(n->refs == 0); } -void node_add_out(Proc *p, Node *a, Node *b) { - ZDA_PUSH(&p->perm, &a->out, b); +void node_add_out(Graph *p, Node *a, Node *b) { + ZDA_PUSH(p->pool->arena, &a->out, b); if (b) b->refs++; } -void node_add_in(Proc *p, Node *a, Node *b) { - ZDA_PUSH(&p->perm, &a->in, b); +void node_add_in(Graph *p, Node *a, Node *b) { + ZDA_PUSH(p->pool->arena, &a->in, b); if (b) b->refs++; } -void node_set_in(Proc *p, Node *n, int idx, Node *to) { +void node_set_in(Graph *p, Node *n, int idx, Node *to) { Node *in = n->in.data[idx]; if (in) in->refs--; node_add_out(p, to, n); @@ -78,7 +78,7 @@ void node_set_in(Proc *p, Node *n, int idx, Node *to) { if (in->out.len < 1) node_kill(in, p); } -void node_add(Proc *p, Node *src, Node *dest) { +void node_add(Graph *p, Node *src, Node *dest) { if (src) assert(src->op != N_DEAD); if (dest) assert(dest->op != N_DEAD); node_add_in(p, dest, src); @@ -92,7 +92,7 @@ void node_add(Proc *p, Node *src, Node *dest) { } } -void node_remove(Proc *p, Node *src, Node *dest) { +void node_remove(Graph *p, Node *src, Node *dest) { assert(dest->op != N_DEAD); node_del_in(dest, src); if (dest->refs < 1) node_die(dest, p); @@ -105,22 +105,22 @@ void node_remove(Proc *p, Node *src, Node *dest) { static int global_node_count = 0; -Node *node_new_empty(Proc *p, NodeType t) { +Node *node_new_empty(Graph *p, NodeType t) { Node *n; - if (p->free_list) { - n = p->free_list; + if (p->pool->free_list) { + n = p->pool->free_list; assert(n->op == N_DEAD); - p->free_list = n->prev_free; + p->pool->free_list = n->prev_free; memset(n, 0, sizeof(Node)); } else { - n = new(&p->perm, Node); + n = new(p->pool->arena, Node); } n->op = t; n->id = global_node_count++; return n; } -Node *node_newv(Proc *p, NodeType t, Node *ctrl, ...) { +Node *node_newv(Graph *p, NodeType t, Node *ctrl, ...) { Node *node = node_new_empty(p, t); va_list ap; va_start(ap, ctrl); @@ -134,7 +134,7 @@ Node *node_newv(Proc *p, NodeType t, Node *ctrl, ...) { return node; } -Node *node_dedup_lit(Proc *p, Value v) { +Node *node_dedup_lit(Graph *p, Value v) { /* TODO: this is probably real inefficient for large procedure graphs, * but does it matter? how many nodes are direct children of the start node? * how many literals even usually occur in a procedure? */ @@ -147,7 +147,7 @@ Node *node_dedup_lit(Proc *p, Value v) { return NULL; } -Node *node_new_lit(Proc *p, Value v) { +Node *node_new_lit(Graph *p, Value v) { Node *t = node_dedup_lit(p, v); if (t) return t; Node *n = node_new(p, N_LIT, NULL, p->start); @@ -155,121 +155,14 @@ Node *node_new_lit(Proc *p, Value v) { return n; } -Node *node_new_lit_i64(Proc *p, int64_t i) { +Node *node_new_lit_i64(Graph *p, int64_t i) { return node_new_lit(p, (Value) { { .lvl = T_CONST, .t = T_INT }, { .i = i } }); } -Node *node_new_lit_bool(Proc *p, int b) { +Node *node_new_lit_bool(Graph *p, int b) { return node_new_lit(p, (Value) { { .lvl = T_CONST, .t = T_BOOL }, { .i = b } }); } -/* procedures */ - -void proc_init(Proc *proc, Str name) { - memset(proc, 0, sizeof(Proc)); - proc->start = node_new(proc, N_START, NULL); - proc->start->type = (Type) { - .lvl = T_BOT, - .t = T_TUPLE, - .next = NULL - }; - proc->stop = node_new_empty(proc, N_STOP); - proc->ctrl = proc->start; - proc->keepalive = node_new(proc, N_KEEPALIVE, NULL); - proc->name = name; -} - -void proc_free(Proc *proc) { - arena_free(&proc->perm); - arena_free(&proc->scratch); -} - -/* scope */ - -NameBinding *scope_find(Scope *scope, Str name) { - for (ScopeFrame *f = scope->tail; f; f = f->prev) { - for (NameBinding *b = f->latest; b; b = b->prev) { - if (str_eql(b->name, name)) { - return b; - } - } - } - return NULL; -} - -ScopeFrame *scope_push(Scope *scope, Proc *proc) { - ScopeFrame *f; - if (scope->free_scope) { - f = scope->free_scope; - *f = (ScopeFrame) { 0 }; - scope->free_scope = f->prev; - } else { - f = new(&proc->perm, ScopeFrame); - } - f->prev = scope->tail; - scope->tail = f; - return f; -} - -ScopeFrame *scope_pop(Scope *scope, Proc *proc) { - ScopeFrame *f = scope->tail; - scope->tail = f->prev; - f->prev = scope->free_scope; - scope->free_scope = f; - for (NameBinding *b = f->latest; b; ) { - NameBinding *p = b->prev; - b->prev = scope->free_bind; - scope->free_bind = b; - node_remove(proc, b->node, proc->keepalive); - b = p; - } - return scope->tail; -} - -/* returns previous value */ -NameBinding *scope_bind(Scope *scope, Str name, Node *value, LexSpan pos, Proc *proc) { - NameBinding *prev = scope_find(scope, name); - NameBinding *b; - if (scope->free_bind) { - b = scope->free_bind; - *b = (NameBinding) { 0 }; - scope->free_bind = b->prev; - } else { - b = new(&proc->perm, NameBinding); - } - b->name = name; - b->prev = scope->tail->latest; - scope->tail->latest = b; - b->node = value; - b->src_pos = pos; - node_add(proc, value, proc->keepalive); - return prev; -} - -NameBinding *scope_update(NameBinding *b, Node *to, Proc *proc) { - Node *n = b->node; - node_add(proc, to, proc->keepalive); - b->node = to; - node_remove(proc, n, proc->keepalive); - return b; -} - -/* adds to keepalive so these aren't invalidated */ -void scope_collect(Scope *scope, Proc *proc, ScopeNameList *nl, Arena *arena) { - for (ScopeFrame *f = scope->tail; f; f = f->prev) { - for (NameBinding *b = f->latest; b; b = b->prev) { - node_add(proc, b->node, proc->keepalive); - ZDA_PUSH(arena, nl, (ScopeName) { b->name, b->node }); - } - } -} - -void scope_uncollect(Scope *scope, Proc *proc, ScopeNameList *nl) { - for (int i = 0; i < nl->len; i++) { - node_remove(proc, nl->data[i].node, proc->keepalive); - } -} - /* types */ int type_eql(Type *a, Type *b) { @@ -141,98 +141,48 @@ typedef struct Node { #define T(a,b) ((a)->op == b) #define T2(a,b,t) ((a)->op == t && (b)->op == t) - - -/* procedure graph */ - -typedef struct NameBinding { - struct NameBinding *prev; - LexSpan src_pos; - Str name; - Node *node; -} NameBinding; - -typedef struct ScopeFrame { - struct ScopeFrame *prev; - NameBinding *latest; -} ScopeFrame; - -typedef struct { - ScopeFrame *tail, *free_scope; - NameBinding *free_bind; -} Scope; +/* node graph */ typedef struct { - Str name; - Node *node; -} ScopeName; - -typedef DYNARR(ScopeName) ScopeNameList; - -/* - * TODO: move to having - typedef struct { - Arena *arena; - Node *start, *stop, *ctrl, *keepalive; - Node *free_list; - } Graph; - typedef struct { - Arena arena; - Str name; - Graph graph; - Scope scope; - } Proc; - * so that scope handling can be separated from the rest of IR - */ + Arena *arena; + Node *free_list; +} NodePool; typedef struct { - Arena perm, scratch; - Str name; + /* pointer so that e.g. there can be one pool per worker thread, + * instead of one per procedure graph */ + NodePool *pool; Node *start, *stop, *ctrl, *keepalive; - Node *free_list; - Type ret_type; - Scope scope; -} Proc; +} Graph; #define NODE_KEEP(p, n, ...)\ do { Node *keep_node = n;\ node_add_out(p, keep_node, p->keepalive); __VA_ARGS__;\ node_del_out(keep_node, p->keepalive); } while(0) -void node_kill(Node *n, Proc *p); -void node_die(Node *n, Proc *p); +void node_kill(Node *n, Graph *p); +void node_die(Node *n, Graph *p); void node_del_out(Node *n, Node *p); void node_del_in(Node *n, Node *p); -void node_kill(Node *n, Proc *p); +void node_kill(Node *n, Graph *p); -void node_add(Proc *p, Node *src, Node *dest); -void node_add_out(Proc *p, Node *a, Node *b); -void node_add_in(Proc *p, Node *a, Node *b); -void node_set_in(Proc *p, Node *n, int idx, Node *to); +void node_add(Graph *p, Node *src, Node *dest); +void node_add_out(Graph *p, Node *a, Node *b); +void node_add_in(Graph *p, Node *a, Node *b); +void node_set_in(Graph *p, Node *n, int idx, Node *to); -void node_remove(Proc *p, Node *src, Node *dest); -Node *node_new_empty(Proc *p, NodeType t); -Node *node_newv(Proc *p, NodeType t, Node *ctrl, ...); -Node *node_dedup_lit(Proc *p, Value v); +void node_remove(Graph *p, Node *src, Node *dest); +Node *node_new_empty(Graph *p, NodeType t); +Node *node_newv(Graph *p, NodeType t, Node *ctrl, ...); +Node *node_dedup_lit(Graph *p, Value v); -Node *node_new_lit(Proc *p, Value v); -Node *node_new_lit_bool(Proc *p, int b); -Node *node_new_lit_i64(Proc *p, int64_t i); +Node *node_new_lit(Graph *p, Value v); +Node *node_new_lit_bool(Graph *p, int b); +Node *node_new_lit_i64(Graph *p, int64_t i); int node_uninit(Node *n); int node_maybe_uninit(Node *n); #define node_new(...) node_newv(__VA_ARGS__, NULL) -void proc_init(Proc *proc, Str name); -void proc_free(Proc *proc); - -ScopeFrame *scope_push(Scope *scope, Proc *proc); -ScopeFrame *scope_pop(Scope *scope, Proc *proc); -NameBinding *scope_find(Scope *scope, Str name); -NameBinding *scope_bind(Scope *scope, Str name, Node *value, LexSpan pos, Proc *proc); -NameBinding *scope_update(NameBinding *b, Node *to, Proc *proc); -void scope_collect(Scope *scope, Proc *proc, ScopeNameList *nl, Arena *arena); -void scope_uncollect(Scope *scope, Proc *proc, ScopeNameList *nl); - #endif @@ -12,6 +12,7 @@ #include "strio.h" #include "ir.h" #include "peephole.h" +#include "proc.h" int no_opt = 0; @@ -41,7 +42,7 @@ Node *parse_expr(Lexer *l, Proc *p, Type *twant); * graph has been generated. */ -Node *ctrl(Proc *p, Node *n) { +Node *ctrl(Graph *p, Node *n) { if (!n) { p->ctrl = node_new_lit(p, (Value) { .type = { .lvl = T_XCTRL, .t = T_NONE } @@ -55,18 +56,19 @@ Node *ctrl(Proc *p, Node *n) { void parse_return(Lexer *l, Proc *p) { lex_next(l); Node *n; + Graph *g = &p->graph; if (p->ret_type.t == T_NONE) { - n = node_new(p, N_RETURN, p->ctrl); + n = node_new(g, N_RETURN, g->ctrl); } else { Node *e = parse_expr(l, p, &p->ret_type); - n = node_new(p, N_RETURN, p->ctrl, e); + n = node_new(g, N_RETURN, g->ctrl, e); } - n = node_peephole(n, p, l); + n = node_peephole(n, g, l); if (n->type.lvl != T_XCTRL) { - node_add(p, n, p->stop); + node_add(g, n, g->stop); } - ctrl(p, n); - ctrl(p, NULL); + ctrl(g, n); + ctrl(g, NULL); } Type parse_type(Lexer *l, Proc *proc) { @@ -94,6 +96,7 @@ Type parse_type(Lexer *l, Proc *proc) { } void parse_let(Lexer *l, Proc *p) { + Graph *g = &p->graph; recurse: lex_expect(l, TM_IDENT); Str name = l->ident; @@ -104,7 +107,7 @@ recurse: if (l->tok != TOK_EQL) { t = parse_type(l, p); if (l->tok != TOK_EQL) { - rhs = node_new(p, N_UNINIT, p->start); + rhs = node_new(g, N_UNINIT, g->start); rhs->type = t; } } @@ -112,11 +115,12 @@ recurse: lex_next(l); rhs = parse_expr(l, p, t.t == T_NONE ? NULL : &t); } - NameBinding *b = scope_bind(&p->scope, name, rhs, pos, p); + NameBinding *b = scope_bind(&p->scope, name, rhs, pos, g); if (b) { lex_error_at(l, pos, LE_WARN, S("shadowing previous declaration")); lex_error_at(l, b->src_pos, LE_WARN, S("declared here")); } + /* TODO: isn't this just a do while loop */ if (l->tok == TOK_COMMA) goto recurse; } @@ -124,17 +128,18 @@ void parse_stmt(Lexer *l, Proc *p); /* TODO: return node from this! */ void parse_block(Lexer *l, Proc *p, ScopeNameList *nl) { + Graph *g = &p->graph; lex_next(l); arena_reset(&p->scratch); - scope_push(&p->scope, p); + scope_push(&p->scope); while (l->tok != TOK_RBRACE) { lex_expected_not(l, TM_EOF); parse_stmt(l, p); } if (nl) { - scope_collect(&p->scope, p, nl, &p->scratch); + scope_collect(&p->scope, g, nl, &p->scratch); } - scope_pop(&p->scope, p); + scope_pop(&p->scope, g); lex_expected(l, TM_RBRACE); lex_next(l); } @@ -158,7 +163,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); + scope_update(b, e, &p->graph); } /* TODO: Implement a better system for this. @@ -195,6 +200,7 @@ void parse_assign(Lexer *l, Proc *p) { */ 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++) { int j, k; ScopeName *b4 = &before->data[i]; @@ -206,18 +212,18 @@ void merge_scope(Lexer *l, Proc *p, Node *region, ScopeNameList *before, ScopeNa Node *phi; if (!no) { if (yes->node == b4->node) continue; - phi = node_new(p, N_PHI, region, yes->node, b4->node); + phi = node_new(g, N_PHI, region, yes->node, b4->node); } else if (!yes) { if (no->node == b4->node) continue; - phi = node_new(p, N_PHI, region, b4->node, no->node); + phi = node_new(g, N_PHI, region, b4->node, no->node); } else { if (yes->node == b4->node && no->node == b4->node) continue; - phi = node_new(p, N_PHI, region, yes->node, no->node); + phi = node_new(g, N_PHI, region, yes->node, no->node); } - phi = node_peephole(phi, p, l); + phi = node_peephole(phi, g, l); NameBinding *b = scope_find(&p->scope, b4->name); assert(b); - scope_update(b, phi, p); + scope_update(b, phi, g); } } @@ -242,85 +248,86 @@ void merge_scope(Lexer *l, Proc *p, Node *region, ScopeNameList *before, ScopeNa */ void parse_if(Lexer *l, Proc *p) { + Graph *g = &p->graph; lex_next(l); Node *cond = parse_expr(l, p, &(Type) { .t = T_BOOL }); Node *ctrl_if = NULL, *ctrl_else = NULL; - Node *if_node = node_new(p, N_IF_ELSE, p->ctrl, cond); + Node *if_node = node_new(g, N_IF_ELSE, g->ctrl, cond); if_node->val = (Value) { .type = { .lvl = T_TOP, .t = T_TUPLE }, .tuple = { 0 } }; - ZDA_PUSH(&p->perm, &if_node->val.tuple, (Value) { .type = { .lvl = T_CTRL, .t = T_NONE } }); - ZDA_PUSH(&p->perm, &if_node->val.tuple, (Value) { .type = { .lvl = T_CTRL, .t = T_NONE } }); - if_node = node_peephole(if_node, p, l); - node_add(p, if_node, p->keepalive); - Node *if_true = node_new(p, N_PROJ, if_node); - Node *if_false = node_new(p, N_PROJ, if_node); + ZDA_PUSH(g->pool->arena, &if_node->val.tuple, (Value) { .type = { .lvl = T_CTRL, .t = T_NONE } }); + ZDA_PUSH(g->pool->arena, &if_node->val.tuple, (Value) { .type = { .lvl = T_CTRL, .t = T_NONE } }); + if_node = node_peephole(if_node, g, l); + node_add(g, if_node, g->keepalive); + Node *if_true = node_new(g, N_PROJ, if_node); + Node *if_false = node_new(g, N_PROJ, if_node); if_true->val.i = 0; if_false->val.i = 1; - if_true = node_peephole(if_true, p, l); - if_false = node_peephole(if_false, p, l); - node_remove(p, if_node, p->keepalive); + if_true = node_peephole(if_true, g, l); + if_false = node_peephole(if_false, g, l); + node_remove(g, if_node, g->keepalive); assert(if_true->in.len > 0); assert(if_false->in.len > 0); - node_add(p, if_true, p->keepalive); - node_add(p, if_false, p->keepalive); + 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, p, &scope_before, &p->scratch); + scope_collect(&p->scope, g, &scope_before, &p->scratch); if (cond->type.lvl == T_CONST) { if (cond->val.i) if_false->type.lvl = T_XCTRL; else if_true->type.lvl = T_XCTRL; } - ctrl(p, if_true); + ctrl(g, if_true); lex_expected(l, TM_LBRACE); int pos = l->pos.ofs; parse_block(l, p, &scope_true); if_true->src_pos = (LexSpan) { .ofs = pos, .n = l->pos.ofs - pos }; - ctrl_if = p->ctrl; - node_add(p, ctrl_if, p->keepalive); + 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, p); + scope_update(scope_find(&p->scope, scope_before.data[i].name), scope_before.data[i].node, g); } - ctrl(p, if_false); + ctrl(g, if_false); lex_expect(l, TM_LBRACE); pos = l->pos.ofs; parse_block(l, p, &scope_false); if_false->src_pos = (LexSpan) { .ofs = pos, .n = l->pos.ofs - pos }; - ctrl_else = p->ctrl; - node_add(p, ctrl_else, p->keepalive); + ctrl_else = g->ctrl; + node_add(g, ctrl_else, g->keepalive); } Node *region; if (ctrl_else) { assert(ctrl_if); assert(ctrl_else); - region = node_new(p, N_REGION, ctrl_if, ctrl_else); - node_add_out(p, region, p->keepalive); - node_remove(p, ctrl_if, p->keepalive); - node_remove(p, ctrl_else, p->keepalive); + region = node_new(g, N_REGION, ctrl_if, ctrl_else); + node_add_out(g, region, g->keepalive); + node_remove(g, ctrl_if, g->keepalive); + node_remove(g, ctrl_else, g->keepalive); } else { assert(ctrl_if); assert(if_false); - region = node_new(p, N_REGION, ctrl_if, if_false); - node_add_out(p, region, p->keepalive); - node_remove(p, ctrl_if, p->keepalive); + region = node_new(g, N_REGION, ctrl_if, if_false); + node_add_out(g, region, g->keepalive); + node_remove(g, ctrl_if, g->keepalive); assert(if_true->refs > 0); assert(if_false->refs > 0); } - ctrl(p, region); - node_remove(p, if_true, p->keepalive); - node_remove(p, if_false, p->keepalive); - assert(p->ctrl->in.len > 0); + ctrl(g, region); + node_remove(g, if_true, g->keepalive); + node_remove(g, if_false, g->keepalive); + 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, p, &scope_true); - scope_uncollect(&p->scope, p, &scope_false); - scope_uncollect(&p->scope, p, &scope_before); - node_del_out(region, p->keepalive); + scope_uncollect(&p->scope, g, &scope_true); + scope_uncollect(&p->scope, g, &scope_false); + scope_uncollect(&p->scope, g, &scope_before); + node_del_out(region, g->keepalive); /* make sure we're not orphaning any phi nodes*/ - if (p->ctrl->out.len < 1) { - ctrl(p, node_peephole(p->ctrl, p, l)); + if (g->ctrl->out.len < 1) { + ctrl(g, node_peephole(g->ctrl, g, l)); } } @@ -350,7 +357,8 @@ void parse_stmt(Lexer *l, Proc *p) { } void parse_args_list(Lexer *l, Proc *proc) { - Node *start = proc->start; + Node *start = proc->graph.start; + Graph *g = &proc->graph; int i = 0; struct { Str name; @@ -371,11 +379,11 @@ void parse_args_list(Lexer *l, Proc *proc) { Value v = (Value) { .type = parse_type(l, proc) }; lex_expected(l, TM_RPAREN | TM_COMMA); for (int j = 0; j < id; j++) { - Node *proj = node_new(proc, N_PROJ, proc->start); + Node *proj = node_new(g, N_PROJ, start); proj->type = v.type; proj->val.i = i++; ZDA_PUSH(&proc->perm, &start->val.tuple, v); - scope_bind(&proc->scope, idbuf[j].name, proj, idbuf[j].pos, proc); + scope_bind(&proc->scope, idbuf[j].name, proj, idbuf[j].pos, g); } id = 0; } @@ -393,6 +401,7 @@ Node *find_return(Node *n) { } void proc_opt_fwd(Proc *p, Lexer *l, Node *n) { + Graph *g = &p->graph; if (n->walked == 2) return; n->walked = 2; switch (n->op) { @@ -427,7 +436,7 @@ void proc_opt_fwd(Proc *p, Lexer *l, Node *n) { assert(n->out.data[0]->in.data[0] == n); Node *new_ctrl = CTRL(CTRL(CTRL(n))); Node *out = n->out.data[0]; - node_set_in(p, out, 0, new_ctrl); + node_set_in(g, out, 0, new_ctrl); proc_opt_fwd(p, l, new_ctrl); return; } @@ -443,19 +452,20 @@ void proc_opt_fwd(Proc *p, Lexer *l, Node *n) { } void proc_opt(Proc *p, Lexer *l) { - if (p->stop->in.len == 0) { + Graph *g = &p->graph; + if (g->stop->in.len == 0) { if (p->ret_type.t != T_NONE) { lex_error(l, LE_ERROR, str_fmt(&p->scratch, "no return statement in function expecting %S", type_desc(&p->ret_type, &p->scratch))); } } - for (int i = 0; i < p->start->out.len; i++) { - Node *n = p->start->out.data[i]; + for (int i = 0; i < g->start->out.len; i++) { + Node *n = g->start->out.data[i]; if (n->op == N_LIT && n->out.len < 1) { - node_kill(n, p); + node_kill(n, g); i--; } } - proc_opt_fwd(p, l, p->start); + proc_opt_fwd(p, l, g->start); } Proc *parse_proc(Lexer *l, Unit *u) { @@ -464,7 +474,7 @@ Proc *parse_proc(Lexer *l, Unit *u) { Proc *proc = &u->procs.data[u->procs.len++]; lex_expect(l, TM_IDENT); proc_init(proc, l->ident); - scope_push(&proc->scope, proc); + scope_push(&proc->scope); lex_next(l); if (l->tok == TOK_LPAREN) { parse_args_list(l, proc); @@ -480,22 +490,22 @@ Proc *parse_proc(Lexer *l, Unit *u) { lex_expected_not(l, TM_EOF); parse_stmt(l, proc); } - scope_pop(&proc->scope, proc); + scope_pop(&proc->scope, &proc->graph); lex_expected(l, TM_RBRACE); lex_next(l); proc_opt(proc, l); return proc; } -void uninit_check(Lexer *l, Proc *p, Node *n, LexSpan pos) { +void uninit_check(Lexer *l, Node *n, LexSpan pos) { if (node_uninit(n)) { lex_error_at(l, pos, LE_ERROR, - str_fmt(&p->scratch, "uninitialized %S", - type_desc(&n->type, &p->scratch))); + str_fmt(&l->arena, "uninitialized %S", + type_desc(&n->type, &l->arena))); } else if (node_maybe_uninit(n)) { lex_error_at(l, pos, LE_WARN, - str_fmt(&p->scratch, "possibly uninitialized %S", - type_desc(&n->type, &p->scratch))); + str_fmt(&l->arena, "possibly uninitialized %S", + type_desc(&n->type, &l->arena))); } } @@ -503,6 +513,7 @@ Node *parse_term(Lexer *l, Proc *p, Type *twant) { (void)twant; /* to be used for .ENUM_TYPE and stuff */ Node *node = NULL; NodeType op_after = N_START; + Graph *g = &p->graph; if (TMASK(l->tok) & (TM_MINUS | TM_PLUS | TM_NOT)) { Token t = l->tok; lex_next(l); @@ -514,7 +525,7 @@ Node *parse_term(Lexer *l, Proc *p, Type *twant) { default: return node; } if (post_op == N_START) return node; - return node_peephole(node_new(p, post_op, NULL, node), p, l); + return node_peephole(node_new(g, post_op, NULL, node), g, l); } if (l->tok == TOK_LPAREN) { lex_next(l); @@ -530,10 +541,10 @@ Node *parse_term(Lexer *l, Proc *p, Type *twant) { } else { lex_error(l, LE_ERROR, S("undeclared identifier")); } - uninit_check(l, p, node, l->pos); + uninit_check(l, node, l->pos); lex_next(l); } else if (TMASK(l->tok) & (TM_TRUE | TM_FALSE)) { - node = node_new_lit_bool(p, l->tok == TOK_TRUE); + node = node_new_lit_bool(g, l->tok == TOK_TRUE); lex_next(l); } else { lex_expected(l, TM_LIT_NUM); @@ -545,14 +556,14 @@ Node *parse_term(Lexer *l, Proc *p, Type *twant) { } val = (val * 10) + (l->ident.s[i] - '0'); } - node = node_new_lit_i64(p, val); + node = node_new_lit_i64(g, val); node->src_pos = l->pos; lex_next(l); } if (op_after != N_START) { - node = node_new(p, op_after, NULL, node_peephole(node, p, l)); + node = node_new(g, op_after, NULL, node_peephole(node, g, l)); } - return node_peephole(node, p, l); + return node_peephole(node, g, l); } NodeType tok_to_bin_op(Token t) { @@ -580,6 +591,7 @@ NodeType tok_to_bin_op(Token t) { /* TODO: operator precedence would be kinda nice actually, sad to say */ Node *parse_expr(Lexer *l, Proc *p, Type *twant) { LexSpan pos = l->pos; + Graph *g = &p->graph; Node *lhs = parse_term(l, p, twant); NodeType nt = tok_to_bin_op(l->tok);; if (lhs->refs <= 0) lex_error(l, LE_ERROR, S("dead lhs")); @@ -589,10 +601,10 @@ Node *parse_expr(Lexer *l, Proc *p, Type *twant) { /* necessary because if lhs is a deduplicated literal, it may be an input to rhs * and therefore culled by peephole optimizations */ Node *rhs; - NODE_KEEP(p, lhs, { + NODE_KEEP(g, lhs, { rhs = parse_expr(l, p, &lhs->type); }); - lhs = node_peephole(node_new(p, nt, NULL, lhs, rhs), p, l); + lhs = node_peephole(node_new(g, nt, NULL, lhs, rhs), g, l); } lhs->src_pos = (LexSpan) { pos.ofs, l->pos.ofs - pos.ofs }; if (twant) type_expected(twant, lhs, l); @@ -689,10 +701,11 @@ void node_print(Node *n, Proc *p) { } void proc_print(Proc *p) { - if (p->start) { + 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, p->start->id); - node_print(p->start, p); + 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); if (no_opt) { for (NameBinding *b = p->scope.free_bind; b; b = b->prev) { uint64_t id = (uintptr_t)b->node; @@ -240,7 +240,7 @@ static int node_equiv_input(Node *a, Node *b) { return 1; } -Node *node_new_zero(Proc *p, Node *n) { +Node *node_new_zero(Graph *p, Node *n) { Value v = { .type = { .lvl = T_CONST, @@ -257,7 +257,7 @@ static inline int is_zero(Node *n) { } /* needs lexer for error reporting */ -Node *node_idealize(Node *n, Proc *p, Lexer *l) { +Node *node_idealize(Node *n, Graph *p, Lexer *l) { type_check(n, l); /* stuff that needs to happen even if optimizations are disabled */ @@ -613,7 +613,7 @@ zero_no_effect: if (node_eql_i64(CAR(n), 0)) return CDR(n); return NULL; } -Node *node_peephole(Node *n, Proc *p, Lexer *l) { +Node *node_peephole(Node *n, Graph *p, Lexer *l) { assert(n->refs > 0); Node *r = node_idealize(n, p, l); if (r) { @@ -4,6 +4,6 @@ #include "ir.h" Value node_compute(Node *n, Lexer *l); -Node *node_peephole(Node *n, Proc *p, Lexer *l); +Node *node_peephole(Node *n, Graph *p, Lexer *l); #endif @@ -0,0 +1,113 @@ +#include <string.h> +#include "proc.h" + +/* procedures */ + +void proc_init(Proc *proc, Str name) { + memset(proc, 0, sizeof(Proc)); + Graph *g = &proc->graph; + proc->pool.arena = &proc->perm; + proc->scope.arena = &proc->perm; + g->pool = &proc->pool; + g->start = node_new(g, N_START, NULL); + g->start->type = (Type) { + .lvl = T_BOT, + .t = T_TUPLE, + .next = NULL + }; + g->stop = node_new_empty(g, N_STOP); + g->ctrl = g->start; + g->keepalive = node_new(g, N_KEEPALIVE, NULL); + proc->name = name; +} + +void proc_free(Proc *proc) { + arena_free(&proc->perm); + arena_free(&proc->scratch); +} + +/* scope */ + +NameBinding *scope_find(Scope *scope, Str name) { + for (ScopeFrame *f = scope->tail; f; f = f->prev) { + for (NameBinding *b = f->latest; b; b = b->prev) { + if (str_eql(b->name, name)) { + return b; + } + } + } + return NULL; +} + +ScopeFrame *scope_push(Scope *scope) { + ScopeFrame *f; + if (scope->free_scope) { + f = scope->free_scope; + *f = (ScopeFrame) { 0 }; + scope->free_scope = f->prev; + } else { + f = new(scope->arena, ScopeFrame); + } + f->prev = scope->tail; + scope->tail = f; + return f; +} + +ScopeFrame *scope_pop(Scope *scope, Graph *g) { + ScopeFrame *f = scope->tail; + scope->tail = f->prev; + f->prev = scope->free_scope; + scope->free_scope = f; + for (NameBinding *b = f->latest; b; ) { + NameBinding *p = b->prev; + b->prev = scope->free_bind; + scope->free_bind = b; + node_remove(g, b->node, g->keepalive); + b = p; + } + return scope->tail; +} + +/* returns previous value */ +NameBinding *scope_bind(Scope *scope, Str name, Node *value, LexSpan pos, Graph *g) { + NameBinding *prev = scope_find(scope, name); + NameBinding *b; + if (scope->free_bind) { + b = scope->free_bind; + *b = (NameBinding) { 0 }; + scope->free_bind = b->prev; + } else { + b = new(scope->arena, NameBinding); + } + b->name = name; + b->prev = scope->tail->latest; + scope->tail->latest = b; + b->node = value; + b->src_pos = pos; + node_add(g, value, g->keepalive); + return prev; +} + +NameBinding *scope_update(NameBinding *b, Node *to, Graph *g) { + Node *n = b->node; + 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_uncollect(Scope *scope, Graph *g, ScopeNameList *nl) { + for (int i = 0; i < nl->len; i++) { + node_remove(g, nl->data[i].node, g->keepalive); + } +} @@ -0,0 +1,51 @@ +#ifndef PROC_H +#define PROC_H + +#include "ir.h" + +typedef struct NameBinding { + struct NameBinding *prev; + LexSpan src_pos; + Str name; + Node *node; +} NameBinding; + +typedef struct ScopeFrame { + struct ScopeFrame *prev; + NameBinding *latest; +} ScopeFrame; + +typedef struct { + Arena *arena; + ScopeFrame *tail, *free_scope; + NameBinding *free_bind; +} Scope; + +typedef struct { + Str name; + Node *node; +} ScopeName; + +typedef DYNARR(ScopeName) ScopeNameList; + +typedef struct { + Str name; + Type ret_type; + Arena perm, scratch; + NodePool pool; + Graph graph; + Scope scope; +} Proc; + +void proc_init(Proc *proc, Str name); +void proc_free(Proc *proc); + +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); +void scope_collect(Scope *scope, Graph *g, ScopeNameList *nl, Arena *arena); +void scope_uncollect(Scope *scope, Graph *g, ScopeNameList *nl); + +#endif |