From 739b4852d2a826ba2985c7db2f5c778050f72250 Mon Sep 17 00:00:00 2001 From: WormHeamer Date: Thu, 7 Aug 2025 02:47:23 -0400 Subject: preliminary peephole optimization of if statements --- ir.c | 133 ++++++++++++++++++++++++++++++++++++++++++------------------------- 1 file changed, 84 insertions(+), 49 deletions(-) (limited to 'ir.c') diff --git a/ir.c b/ir.c index dd8b66c..bd3354b 100644 --- a/ir.c +++ b/ir.c @@ -11,8 +11,9 @@ extern int no_opt; #define IN(n, i) ((n)->in.data[i]) #define OUT(n, i) ((n)->out.data[i]) -#define CAR(n) IN(n, 0) -#define CDR(n) IN(n, 1) +#define CTRL(n) IN(n, 0) +#define CAR(n) IN(n, 1) +#define CDR(n) IN(n, 2) #define CAAR(n) CAR(CAR(n)) #define CADR(n) CDR(CAR(n)) #define CDAR(n) CAR(CDR(n)) @@ -50,6 +51,11 @@ int value_eql(Value *a, Value *b) { Str type_desc(Type *t, Arena *arena) { (void)arena; + switch (t->lvl) { + case T_CTRL: return S("ctrl"); + case T_XCTRL: return S("~ctrl"); + default: break; + } switch (t->t) { case T_TUPLE: return S("tuple"); case T_BOOL: return S("bool"); @@ -140,7 +146,7 @@ void node_die(Node *n, Proc *p) { void node_del_out(Node *n, Node *p) { for (int i = n->out.len - 1; i >= 0; i--) { if (n->out.data[i] == p) { - p->refs--; + if (p) p->refs--; n->out.len--; if (i < n->out.len) { n->out.data[i] = n->out.data[n->out.len]; @@ -153,7 +159,7 @@ void node_del_out(Node *n, Node *p) { void node_del_in(Node *n, Node *p) { for (int i = n->in.len - 1; i >= 0; i--) { if (n->in.data[i] == p) { - p->refs--; + if (p) p->refs--; n->in.len--; if (i < n->in.len) { memmove(&n->in.data[i], &n->in.data[i + 1], sizeof(Node*) * (n->in.len - i)); @@ -164,7 +170,6 @@ void node_del_in(Node *n, Node *p) { } void node_kill(Node *n, Proc *p) { - assert(n->refs > 0); while (n->refs > 0 && n->in.len > 0) node_remove(p, n->in.data[0], n); while (n->refs > 0 && n->out.len > 0) node_remove(p, n, n->out.data[0]); assert(n->refs == 0); @@ -172,17 +177,18 @@ void node_kill(Node *n, Proc *p) { void node_add_out(Proc *p, Node *a, Node *b) { ZDA_PUSH(&p->arena, &a->out, b); - b->refs++; + if (b) b->refs++; } void node_add_in(Proc *p, Node *a, Node *b) { ZDA_PUSH(&p->arena, &a->in, b); - b->refs++; + if (b) b->refs++; } void node_add(Proc *p, Node *src, Node *dest) { - node_add_out(p, src, dest); node_add_in(p, dest, src); + if (!src) return; + node_add_out(p, src, dest); if (dest->src_pos.n == 0) dest->src_pos = src->src_pos; else if (src->src_pos.n != 0) { int lo = dest->src_pos.ofs < src->src_pos.ofs ? dest->src_pos.ofs : src->src_pos.ofs; @@ -192,10 +198,12 @@ void node_add(Proc *p, Node *src, Node *dest) { } void node_remove(Proc *p, Node *src, Node *dest) { - node_del_out(src, dest); node_del_in(dest, src); if (dest->refs < 1) node_die(dest, p); - if (src->out.len < 1) node_kill(src, p); + if (src) { + node_del_out(src, dest); + if (src->out.len < 1) node_kill(src, p); + } } static int global_node_count = 0; @@ -215,10 +223,11 @@ Node *node_new_empty(Proc *p, NodeType t) { } int type_check(Node *); -Node *node_newv(Proc *p, NodeType t, ...) { +Node *node_newv(Proc *p, NodeType t, Node *ctrl, ...) { Node *node = node_new_empty(p, t); va_list ap; - va_start(ap, t); + va_start(ap, ctrl); + node_add(p, ctrl, node); for (;;) { Node *n = va_arg(ap, Node *); if (!n) break; @@ -244,7 +253,7 @@ Node *node_dedup_lit(Proc *p, Value v) { Node *node_new_lit(Proc *p, Value v) { Node *t = node_dedup_lit(p, v); if (t) return t; - Node *n = node_new(p, N_LIT, p->start); + Node *n = node_new(p, N_LIT, NULL, p->start); n->val = v; return n; } @@ -323,9 +332,8 @@ static inline int node_cmp_incompat(NodeType a, NodeType b) { Value node_compute(Node *n, Lexer *l) { Type lit_type = { .lvl = T_BOT }; - Node **in = n->in.data; - for (int i = 0; i < n->in.len; i++) { - Node *p = in[i]; + for (int i = 1; i < n->in.len; i++) { + Node *p = IN(n, i); if (p->val.type.lvl != T_CONST) { lit_type.lvl = T_BOT; break; @@ -346,39 +354,39 @@ Value node_compute(Node *n, Lexer *l) { if (lit_type.t == T_INT) { switch (n->type) { - case N_OP_NEG: v.i = -in[0]->val.i; break; - case N_OP_NOT: v.i = ~in[0]->val.i; break; - case N_OP_ADD: v.i = in[0]->val.i + in[1]->val.i; break; - case N_OP_SUB: v.i = in[0]->val.i - in[1]->val.i; break; - case N_OP_MUL: v.i = in[0]->val.i * in[1]->val.i; break; + case N_OP_NEG: v.i = -CAR(n)->val.i; break; + case N_OP_NOT: v.i = ~CAR(n)->val.i; break; + case N_OP_ADD: v.i = CAR(n)->val.i + CDR(n)->val.i; break; + case N_OP_SUB: v.i = CAR(n)->val.i - CDR(n)->val.i; break; + case N_OP_MUL: v.i = CAR(n)->val.i * CDR(n)->val.i; break; case N_OP_DIV: - if (in[1]->val.i == 0) { - lex_error_at(l, in[1]->src_pos, LE_ERROR, S("divisor always evaluates to zero")); + if (CDR(n)->val.i == 0) { + lex_error_at(l, CDR(n)->src_pos, LE_ERROR, S("divisor always evaluates to zero")); } - v.i = in[0]->val.i / in[1]->val.i; + v.i = CAR(n)->val.i / CDR(n)->val.i; break; - case N_OP_AND: v.i = in[0]->val.i & in[1]->val.i; break; - case N_OP_OR: v.i = in[0]->val.i | in[1]->val.i; break; - case N_OP_XOR: v.i = in[0]->val.i ^ in[1]->val.i; break; - case N_OP_SHL: v.i = in[0]->val.u << in[1]->val.u; break; - case N_OP_SHR: v.i = in[0]->val.u >> in[1]->val.u; break; - case N_CMP_EQL: v.type.t = T_BOOL; v.i = in[0]->val.i == in[1]->val.i; break; - case N_CMP_NEQ: v.type.t = T_BOOL; v.i = in[0]->val.i != in[1]->val.i; break; - case N_CMP_LES: v.type.t = T_BOOL; v.i = in[0]->val.i < in[1]->val.i; break; - case N_CMP_GTR: v.type.t = T_BOOL; v.i = in[0]->val.i > in[1]->val.i; break; - case N_CMP_LTE: v.type.t = T_BOOL; v.i = in[0]->val.i <= in[1]->val.i; break; - case N_CMP_GTE: v.type.t = T_BOOL; v.i = in[0]->val.i >= in[1]->val.i; break; + case N_OP_AND: v.i = CAR(n)->val.i & CDR(n)->val.i; break; + case N_OP_OR: v.i = CAR(n)->val.i | CDR(n)->val.i; break; + case N_OP_XOR: v.i = CAR(n)->val.i ^ CDR(n)->val.i; break; + case N_OP_SHL: v.i = CAR(n)->val.u << CDR(n)->val.u; break; + case N_OP_SHR: v.i = CAR(n)->val.u >> CDR(n)->val.u; break; + case N_CMP_EQL: v.type.t = T_BOOL; v.i = CAR(n)->val.i == CDR(n)->val.i; break; + case N_CMP_NEQ: v.type.t = T_BOOL; v.i = CAR(n)->val.i != CDR(n)->val.i; break; + case N_CMP_LES: v.type.t = T_BOOL; v.i = CAR(n)->val.i < CDR(n)->val.i; break; + case N_CMP_GTR: v.type.t = T_BOOL; v.i = CAR(n)->val.i > CDR(n)->val.i; break; + case N_CMP_LTE: v.type.t = T_BOOL; v.i = CAR(n)->val.i <= CDR(n)->val.i; break; + case N_CMP_GTE: v.type.t = T_BOOL; v.i = CAR(n)->val.i >= CDR(n)->val.i; break; default: return n->val; } return v; } else if (lit_type.t == T_BOOL) { switch (n->type) { - case N_OP_NOT: v.i = !in[0]->val.i; break; - case N_CMP_EQL: v.i = in[0]->val.i == in[1]->val.i; break; - case N_CMP_NEQ: v.i = in[0]->val.i != in[1]->val.i; break; - case N_OP_AND: v.i = in[0]->val.i && in[1]->val.i; break; - case N_OP_OR: v.i = in[0]->val.i || in[1]->val.i; break; - case N_OP_XOR: v.i = in[0]->val.i ^ in[1]->val.i; break; + case N_OP_NOT: v.i = !CAR(n)->val.i; break; + case N_CMP_EQL: v.i = CAR(n)->val.i == CDR(n)->val.i; break; + case N_CMP_NEQ: v.i = CAR(n)->val.i != CDR(n)->val.i; break; + case N_OP_AND: v.i = CAR(n)->val.i && CDR(n)->val.i; break; + case N_OP_OR: v.i = CAR(n)->val.i || CDR(n)->val.i; break; + case N_OP_XOR: v.i = CAR(n)->val.i ^ CDR(n)->val.i; break; default: return n->val; } return v; @@ -389,7 +397,7 @@ Value node_compute(Node *n, Lexer *l) { #include -#define NODE(...) node_peephole(node_new(p, __VA_ARGS__), p, l) +#define NODE(t, ...) node_peephole(node_new(p, t, CTRL(n), __VA_ARGS__), p, l) #define OP(...) NODE(n->type, __VA_ARGS__) static inline int node_eql_i64(Node *n, int64_t i) { @@ -498,7 +506,7 @@ Node *node_idealize(Node *n, Proc *p, Lexer *l) { if (v.type.lvl == T_CONST) { Node *t = node_dedup_lit(p, v); if (t) return t; - Node *r = node_new(p, N_LIT, p->start); + Node *r = node_new(p, N_LIT, NULL, p->start); r->val = v; r->src_pos = n->src_pos; return r; @@ -517,8 +525,8 @@ Node *node_idealize(Node *n, Proc *p, Lexer *l) { } } - if (n->in.len > 1 && same && !same_ptr) { - Node *r = node_new_empty(p, n->type); + if (n->in.len > 2 && same && !same_ptr) { + Node *r = node_new(p, n->type, NULL); for (int i = 0; i < n->in.len; i++) { node_add(p, CAR(n), r); } @@ -691,6 +699,27 @@ zero_no_effect: if (node_eql_i64(CAR(n), 0)) return CDR(n); case N_CMP_GTE: if (same) return node_new_lit_bool(p, 1); break; + + case N_IF_ELSE: + if (T(CAR(n), N_LIT)) { + if (CAR(n)->val.i) { + n->val.tuple.data[1].type.lvl = T_XCTRL; + } else { + n->val.tuple.data[0].type.lvl = T_XCTRL; + } + } + break; + + case N_PHI: + if (same) return CAR(n); + if (IN(CTRL(n), 0)->val.type.lvl == T_XCTRL) { + return CDR(n); + } + if (IN(CTRL(n), 1)->val.type.lvl == T_XCTRL) { + return CAR(n); + } + break; + default: break; } @@ -747,15 +776,15 @@ Node *node_peephole(Node *n, Proc *p, Lexer *l) { void proc_init(Proc *proc, Str name) { memset(proc, 0, sizeof(Proc)); - proc->start = node_new_empty(proc, N_START); + proc->start = node_new(proc, N_START, NULL); proc->start->val.type = (Type) { .lvl = T_BOT, .t = T_TUPLE, .next = NULL }; - proc->stop = node_new_empty(proc, N_STOP); + proc->stop = node_new(proc, N_STOP, NULL); proc->ctrl = proc->start; - proc->keepalive = node_new_empty(proc, N_KEEPALIVE); + proc->keepalive = node_new(proc, N_KEEPALIVE, NULL); proc->name = name; } @@ -838,8 +867,14 @@ NameBinding *scope_update(Scope *scope, Str name, Node *to, Proc *proc) { 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_out(proc, b->node, proc->keepalive); + 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); + } +} -- cgit v1.2.3