From 7b235b3aab2bf22405e63f4f55114fca3c284185 Mon Sep 17 00:00:00 2001 From: WormHeamer Date: Fri, 8 Aug 2025 06:59:51 -0400 Subject: attempt at optimizing regions after graph generation.... --- ir.c | 45 +++++++++++++++++------------ ir.h | 1 + main.c | 99 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++-- test.lang | 19 ++++++------ 4 files changed, 133 insertions(+), 31 deletions(-) diff --git a/ir.c b/ir.c index dd7a8ac..f895323 100644 --- a/ir.c +++ b/ir.c @@ -172,6 +172,15 @@ void node_add_in(Proc *p, Node *a, Node *b) { if (b) b->refs++; } +void node_set_in(Proc *p, Node *n, int idx, Node *to) { + Node *in = n->in.data[idx]; + if (in) in->refs--; + node_del_out(in, n); + node_add_out(p, to, n); + n->in.data[0] = to; + if (in->out.len < 1) node_kill(in, p); +} + void node_add(Proc *p, Node *src, Node *dest) { node_add_in(p, dest, src); if (!src) return; @@ -712,11 +721,11 @@ zero_no_effect: if (node_eql_i64(CAR(n), 0)) return CDR(n); case N_PROJ: if (T(CTRL(n), N_IF_ELSE) && CTRL(n)->type.t == T_TUPLE) { - if (CTRL(n)->val.tuple.data[n->val.i].type.lvl == T_XCTRL) { + /*if (CTRL(n)->val.tuple.data[n->val.i].type.lvl == T_XCTRL) { return node_new_lit(p, (Value) { .type = { .lvl = T_XCTRL, .t = T_NONE } }); - } + }*/ if (CTRL(n)->val.tuple.data[(n->val.i + 1) % CTRL(n)->val.tuple.len].type.lvl == T_XCTRL) { return CTRL(CTRL(n)); } @@ -734,26 +743,24 @@ zero_no_effect: if (node_eql_i64(CAR(n), 0)) return CDR(n); } break; - case N_REGION: - { - int live_in = 0; + case N_REGION: if (0) { + int live_in = 0; + for (int i = 0; i < n->in.len; i++) { + if (IN(n, i)->type.lvl != T_XCTRL) live_in++; + } + if (live_in == 1) { for (int i = 0; i < n->in.len; i++) { - if (IN(n, i)->type.lvl != T_XCTRL) live_in++; - } - if (live_in == 1) { - for (int i = 0; i < n->in.len; i++) { - if (IN(n, i)->type.lvl != T_XCTRL) { - return IN(n, i); - } + if (IN(n, i)->type.lvl != T_XCTRL) { + return IN(n, i); } } - if (live_in == 0) { - return node_new_lit(p, (Value) { - .type = { .lvl = T_XCTRL, .t = T_NONE } - }); - } } - break; + if (live_in == 0) { + return node_new_lit(p, (Value) { + .type = { .lvl = T_XCTRL, .t = T_NONE } + }); + } + } break; default: break; @@ -817,7 +824,7 @@ void proc_init(Proc *proc, Str name) { .t = T_TUPLE, .next = NULL }; - proc->stop = node_new(proc, N_STOP, NULL); + proc->stop = node_new_empty(proc, N_STOP); proc->ctrl = proc->start; proc->keepalive = node_new(proc, N_KEEPALIVE, NULL); proc->name = name; diff --git a/ir.h b/ir.h index 54c56e2..adb1039 100644 --- a/ir.h +++ b/ir.h @@ -189,6 +189,7 @@ void node_kill(Node *n, Proc *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_remove(Proc *p, Node *src, Node *dest); Node *node_new_empty(Proc *p, NodeType t); diff --git a/main.c b/main.c index 8bb7fda..26f9534 100644 --- a/main.c +++ b/main.c @@ -241,7 +241,9 @@ void parse_if(Lexer *l, Proc *p) { ctrl(p, if_true); //assert(if_true->in.len > 0); 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); //assert(ctrl_if->in.len > 0); @@ -251,7 +253,9 @@ void parse_if(Lexer *l, Proc *p) { } ctrl(p, 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); } @@ -379,6 +383,92 @@ void parse_args_list(Lexer *l, Proc *proc) { lex_next(l); } +Node *find_return(Node *n) { + if (n->op == N_RETURN) return n; + for (int i = 0; i < n->out.len; i++) { + Node *r = find_return(n->out.data[i]); + if (r) return r; + } + return NULL; +} + +void proc_opt_fwd(Proc *p, Lexer *l, Node *n) { + fprintf(stderr, "%d %s\n", n->id, node_type_name(n->op)); + if (n->walked == 2) return; + n->walked = 2; + switch (n->op) { + case N_START: + for (int i = 0; i < n->out.len; i++) { + if (!(NMASK(n->out.data[i]->op) & (NM_LIT | NM_PROJ))) { + proc_opt_fwd(p, l, n->out.data[i]); + break; + } + } + break; + case N_IF_ELSE: + if (n->out.len < 2) { + lex_error_at(l, n->src_pos, LE_ERROR, S("not all codepaths return")); + } + for (int i = 0; i < n->out.len; i++) { + Node *r = find_return(n->out.data[i]); + if (!r) { + lex_error_at(l, n->out.data[i]->src_pos, LE_ERROR, S("not all codepaths return")); + } + proc_opt_fwd(p, l, n->out.data[i]); + } + break; + case N_PROJ: + proc_opt_fwd(p, l, n->out.data[0]); + break; + case N_REGION: + /* cull empty if else */ + if (n->out.len == 1 && n->in.len == 2 + && IN(n,0)->op == N_PROJ + && IN(n,1)->op == N_PROJ + && CTRL(IN(n,0)) == CTRL(IN(n,1)) + && CTRL(IN(n,0))->op == N_IF_ELSE) { + assert(n->out.data[0]->op != N_PHI); + assert(n->out.data[0]->in.data[0] == n); + Node *new_ctrl = CTRL(CTRL(CTRL(n))); + Node *out = n->out.data[0]; + //node_remove(p, new_ctrl, CTRL(CTRL(n))); + // ^ is that needed? + // idea was to prevent deleting stuff unnecessarily, + // but i think the new node_set_in() function works + // completely fine for that original purpose. + node_set_in(p, out, 0, new_ctrl); + proc_opt_fwd(p, l, new_ctrl); + return; + } + for (int i = 0; i < n->out.len; i++) { + if (n->out.data[i]->op != N_PHI) { + proc_opt_fwd(p, l, n->out.data[i]); + } + } + break; + default: + break; + } +} + +void proc_opt(Proc *p, Lexer *l) { + fprintf(stderr, "%ld\n", p->stop->in.len); + if (p->stop->in.len == 0) { + + if (p->ret_type.t != T_NONE) { + lex_error(l, LE_ERROR, str_fmt(&p->arena, "no return statement in function expecting %S", type_desc(&p->ret_type, &p->arena))); + } + } + for (int i = 0; i < p->start->out.len; i++) { + Node *n = p->start->out.data[i]; + if (n->op == N_LIT && n->out.len < 1) { + node_kill(n, p); + i--; + } + } + proc_opt_fwd(p, l, p->start); +} + Proc *parse_proc(Lexer *l, Unit *u) { int has_ret = l->tok == TOK_FUNC; DA_FIT(&u->procs, u->procs.len + 1); @@ -404,6 +494,7 @@ Proc *parse_proc(Lexer *l, Unit *u) { scope_pop(&proc->scope, proc); lex_expected(l, TM_RBRACE); lex_next(l); + proc_opt(proc, l); return proc; } @@ -530,8 +621,13 @@ void parse_unit(Lexer *l) { /* graph output */ +/* TODO: Print at every stage of graph compilation and generate a frame for + * each, so problems can be debugged visually as they occur. + */ + void node_print(Node *n, Proc *p) { - if (n->walked) return; + if (n->walked == 1) return; + n->walked = 1; if (n->op == N_START) { Str s = S(""); int c = n->val.tuple.len; @@ -566,7 +662,6 @@ void node_print(Node *n, Proc *p) { printf("\t%d [label=\"%s\", shape=record]", n->id, node_type_name(n->op)); } printf("\n"); - n->walked = 1; for (int i = 0; i < n->out.len; i++) { Node *o = n->out.data[i]; if (o->op == N_LIT) { diff --git a/test.lang b/test.lang index f46b8a0..5535a4e 100644 --- a/test.lang +++ b/test.lang @@ -1,17 +1,16 @@ func main(a, b i64) i64 { - /*if a = b { + if a = b { let t = a a := b b := t } else { - let t = a - a := b - b := t - }*/ - /* TODO: error on failing to return from a function */ - if a < b { - return 237 + a + 812734 + b + 81753 + 2389 - } else { - return 1 + a + 7 + 123897 + a := 5 + b := 10 + if a = b { + let t = a + a := b + b := t + } } + return a + b } -- cgit v1.2.3