From 85e28cfad0260ebf206a1249f153942ccea9673d Mon Sep 17 00:00:00 2001 From: WormHeamer Date: Sun, 10 Aug 2025 01:27:32 -0400 Subject: separate peephole optimization out --- ir.c | 726 +++++++------------------------------------------------------ ir.h | 2 - main.c | 1 + peephole.c | 559 +++++++++++++++++++++++++++++++++++++++++++++++ peephole.h | 9 + 5 files changed, 653 insertions(+), 644 deletions(-) create mode 100644 peephole.c create mode 100644 peephole.h diff --git a/ir.c b/ir.c index 42691ee..6e91faa 100644 --- a/ir.c +++ b/ir.c @@ -6,96 +6,6 @@ extern int no_opt; -/* TODO: - * - * Separate normal graph manipulation from peephole optimization code. - * - */ - -/* types */ - -int type_eql(Type *a, Type *b) { - if (a->t != b->t) return 0; - if (a->lvl != b->lvl) return 0; - if (a->next != b->next) return 0; - return a->next ? type_eql(a->next, b->next) : 1; -} - -int type_base_eql(Type *a, Type *b) { - if (a->t != b->t) return 0; - if (a->next != b->next) return 0; - return a->next ? type_base_eql(a->next, b->next) : 1; -} - -int value_eql(Value *a, Value *b) { - if (!type_eql(&a->type, &b->type)) return 0; - return a->i == b->i; -} - -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"); - case T_INT: return S("i64"); - case T_PTR: return str_fmt(arena, "^%S", type_desc(t->next, arena)); - default: return S("N/A"); - } -} - -void type_err(Node *n, Lexer *l) { - Str s = S(""); - for (int i = 0; i < n->in.len; i++) { - if (i > 0) str_cat(&s, S(", "), &l->arena); - str_cat(&s, type_desc(&IN(n, i)->type, &l->arena), &l->arena); - } - lex_error_at(l, n->src_pos, LE_ERROR, str_fmt(&l->arena, "type error %s (%S)", node_type_name(n->op), s)); -} - -int type_check(Node *n) { - switch (n->op) { - case N_PHI: - n->type = (Type) { .lvl = T_TOP, .t = IN(n, 1)->type.t }; - for (int i = 2; i < n->in.len; i++) { - if (!type_base_eql(&IN(n, i)->type, &n->type)) { - return 0; - } - } - return 1; - case N_OP_NEG: - n->type = (Type) { .lvl = T_TOP, .t = T_INT }; - return CAR(n)->type.t == T_INT; - case N_OP_NOT: - n->type = (Type) { .lvl = T_TOP, .t = CAR(n)->type.t }; - return CAR(n)->type.t == T_INT || CAR(n)->type.t == T_BOOL; - case N_OP_AND: case N_OP_OR: case N_OP_XOR: - n->type = (Type) { .lvl = T_TOP, .t = CAR(n)->type.t }; - return (CAR(n)->type.t == T_INT && CDR(n)->type.t == T_INT) - || (CAR(n)->type.t == T_BOOL && CDR(n)->type.t == T_BOOL); - case N_OP_ADD: case N_OP_SUB: case N_OP_MUL: case N_OP_DIV: - case N_OP_SHL: case N_OP_SHR: - n->type = (Type) { .lvl = T_TOP, .t = T_INT }; - return CAR(n)->type.t == T_INT && CDR(n)->type.t == T_INT; - case N_CMP_LES: case N_CMP_GTR: - case N_CMP_LTE: case N_CMP_GTE: - n->type = (Type) { .lvl = T_TOP, .t = T_BOOL }; - return CAR(n)->type.t == T_INT && CDR(n)->type.t == T_INT; - case N_CMP_EQL: - case N_CMP_NEQ: - n->type = (Type) { .lvl = T_TOP, .t = T_BOOL }; - return type_base_eql(&CAR(n)->type, &CDR(n)->type); - /* (CAR(n)->type.t == T_INT && CDR(n)->type.t == T_INT) - || (CAR(n)->type.t == T_BOOL && CDR(n)->type.t == T_BOOL); */ - default: - return 1; - } -} - /* nodes */ const char *node_type_name(NodeType t) { @@ -256,558 +166,6 @@ Node *node_new_lit_bool(Proc *p, int b) { return node_new_lit(p, (Value) { { .lvl = T_CONST, .t = T_BOOL }, { .i = b } }); } -static inline int node_op_communative(NodeType t) { - return NMASK(t) & (NM_OP_ADD | NM_OP_MUL | NM_OP_AND | NM_OP_XOR | NM_OP_OR | NM_CMP_EQL | NM_CMP_NEQ); - /*NodeType ops[] = { N_OP_ADD, N_OP_MUL, N_OP_AND, N_OP_XOR, N_OP_OR, N_CMP_EQL, N_CMP_NEQ }; - for (unsigned i = 0; i < sizeof ops / sizeof *ops; i++) { - if (ops[i] == t) return 1; - } - return 0;*/ -} - -static inline int node_op_associative(NodeType t) { - /*NodeType ops[] = { N_OP_ADD, N_OP_MUL, N_OP_AND, N_OP_XOR, N_OP_OR }; - for (unsigned i = 0; i < sizeof ops / sizeof *ops; i++) { - if (ops[i] == t) return 1; - } - return 0;*/ - return NMASK(t) & (NM_OP_ADD | NM_OP_MUL | NM_OP_AND | NM_OP_XOR | NM_OP_OR); -} - -static inline int node_op_comparison(NodeType t) { - /*NodeType ops[] = { N_CMP_EQL, N_CMP_NEQ, N_CMP_LES, N_CMP_GTR, N_CMP_LTE, N_CMP_GTE }; - for (unsigned i = 0; i < sizeof ops / sizeof *ops; i++) { - if (ops[i] == t) return 1; - } - return 0;*/ - return NMASK(t) & (NM_CMP_EQL | NM_CMP_NEQ | NM_CMP_LES | NM_CMP_GTR | NM_CMP_LTE | NM_CMP_GTE); -} - -/* when applied to the same input, at least one must be true */ -static inline NodeType node_cmp_opposite(NodeType a) { - switch (a) { - case N_CMP_EQL: return N_CMP_NEQ; - case N_CMP_NEQ: return N_CMP_EQL; - case N_CMP_LES: return N_CMP_GTE; - case N_CMP_GTE: return N_CMP_LES; - case N_CMP_GTR: return N_CMP_LTE; - case N_CMP_LTE: return N_CMP_GTR; - default: return N_NONE; - } -} - -static inline NodeType node_cmp_flip_sign(NodeType a) { - switch (a) { - case N_CMP_LES: return N_CMP_GTR; - case N_CMP_LTE: return N_CMP_GTE; - case N_CMP_GTR: return N_CMP_LES; - case N_CMP_GTE: return N_CMP_LTE; - default: return a; - } -} - -/* when applied to the same input, at least one must be false */ -static inline int node_cmp_incompat(NodeType a, NodeType b) { - struct { NodeType l, r; } pairs[] = { - { N_CMP_EQL, N_CMP_NEQ }, - { N_CMP_LES, N_CMP_GTE }, - { N_CMP_GTR, N_CMP_LTE }, - { N_CMP_LES, N_CMP_GTR }, - }; - for (unsigned i = 0; i < sizeof pairs / sizeof *pairs; i++) { - if ((pairs[i].l == a && pairs[i].r == b) || (pairs[i].l == b && pairs[i].r == a)) { - return 1; - } - } - return 0; -} - -Value node_compute(Node *n, Lexer *l) { - Type lit_type = { .lvl = T_BOT }; - for (int i = 1; i < n->in.len; i++) { - Node *p = IN(n, i); - if (p->type.lvl != T_CONST) { - lit_type.lvl = T_BOT; - break; - } - if (!type_eql(&p->type, &lit_type)) { - if (lit_type.lvl == T_BOT) { - lit_type = p->type; - } else { - lit_type.lvl = T_BOT; - break; - } - } - } - - if (lit_type.lvl != T_CONST) return n->val; - - Value v = { .type = lit_type }; - - if (lit_type.t == T_INT) { - switch (n->op) { - 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 (CDR(n)->val.i == 0) { - lex_error_at(l, CDR(n)->src_pos, LE_ERROR, S("divisor always evaluates to zero")); - } - 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; - 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->op) { - 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; - } - - return n->val; -} - -#include - -#define NODE(t, ...) node_peephole(node_new(p, t, CTRL(n), __VA_ARGS__), p, l) -#define OP(...) NODE(n->op, __VA_ARGS__) - -static inline int node_eql_i64(Node *n, int64_t i) { - return n->op == N_LIT && n->type.t == T_INT && n->val.i == i; -} - -static inline int u64_power_of_2(uint64_t x) { - int ldz = 0, tlz = 0; - for (int i = 0; i < 64; i++) { - if ((x >> i) & 1) break; - else tlz++; - } - for (int i = 0; i < 64; i++) { - if ((x << i) & (1UL << 63)) break; - else ldz++; - } - if (ldz + tlz != 63) return 0; - return tlz; -} - -/* functions to query the compile-time equivalence of nodes */ -/* fairly conservative of necessity */ - -static int node_equiv(Node *a, Node *b); -static int node_known_neg_of(Node *a, Node *b) { - if (T(b, N_OP_NEG) && node_equiv(a, CAR(b))) return 1; - if (T(a, N_OP_NEG) && node_equiv(CAR(a), b)) return 1; - if (T(a, N_LIT) && T(b, N_LIT) && (a->type.t == b->type.t) && b->val.i == -a->val.i) return 1; - return 0; -} - -static inline int node_sub_add_equiv(Node *a, Node *b) { - if (node_equiv(CAR(a), CAR(b)) && !node_known_neg_of(CDR(a), CDR(b))) return 1; - if (node_equiv(CAR(a), CDR(b)) && !node_known_neg_of(CDR(a), CAR(b))) return 1; - return 0; -} - -static int node_equiv_input(Node *a, Node *b); - -static int node_equiv(Node *a, Node *b) { - /* will doing this recursively be too slow? */ - if (a == b) return 1; - if (a->op != b->op) return 0; - if (a->in.len != b->in.len) return 0; - if (!value_eql(&a->val, &b->val)) return 0; - if (!node_equiv_input(a, b)) return 0; - return 1; -} - -/* TODO: figure out a more thorough way of comparing node graphs */ - -static inline int node_known_not_equiv_ord(Node *a, Node *b) { - if ((b->op & (NM_OP_ADD | NM_OP_SUB)) && node_equiv(a, CAR(b)) - && T(CDR(b), N_LIT) && !node_eql_i64(CDR(b), 0)) return 1; - if ((a->op & (NM_OP_ADD | NM_OP_SUB)) && node_sub_add_equiv(a, b)) return 1; - return 0; -} -static inline int node_known_not_equiv(Node *a, Node *b) { - return node_known_not_equiv_ord(a, b) || node_known_not_equiv_ord(b, a); -} - -static int node_equiv_input(Node *a, Node *b) { - if (a->in.len != b->in.len) return 0; - if (CTRL(a) != CTRL(b)) return 0; - /* note that this means the order of inputs isn't guaranteed, so be - * careful what you use this procedure for */ - if ((node_op_communative(a->op) || node_op_communative(b->op)) - && node_equiv(CDR(a), CAR(b)) - && node_equiv(CAR(a), CDR(b))) { - /* assuming input count is 2 */ - return 1; - } - for (int i = 1; i < a->in.len; i++) { - if (!node_equiv(IN(a, i), IN(b, i))) return 0; - } - return 1; -} - -Node *node_new_zero(Proc *p, Node *n) { - Value v = { - .type = { - .lvl = T_CONST, - .t = n->type.t, - }, - .i = 0 - }; - Node *r = node_new_lit(p, v); - return r; -} - -static inline int is_zero(Node *n) { - return n->type.lvl == T_CONST && (n->type.t == T_INT || n->type.t == T_BOOL) && !n->val.i; -} - -/* needs lexer for error reporting */ -Node *node_idealize(Node *n, Proc *p, Lexer *l) { - if (!type_check(n)) { - type_err(n, l); - } - - if (no_opt) return NULL; - - /* try to compute a literal value */ - - if (n->op != N_LIT) { - Value v = node_compute(n, 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, NULL, p->start); - r->val = v; - r->src_pos = n->src_pos; - return r; - } - } - - /* try to trim duplicate inputs from the graph */ - - int same = 1, same_ptr = 1; - for (int i = 1; i < n->in.len; i++) { - if (IN(n, i) == CAR(n)) continue; - same_ptr = 0; - if (!node_equiv(IN(n, i), CAR(n))) { - same = 0; - break; - } - } - - if (n->in.len > 2 && same && !same_ptr) { - Node *r = node_new(p, n->op, NULL); - for (int i = 0; i < n->in.len; i++) { - node_add(p, CAR(n), r); - } - return node_peephole(r, p, l); - } - - /* transformations to help encourage constant folding */ - /* the overall trend is to move them rightwards */ - - /* need to check for type compatibility */ - #define C(a, b) type_base_eql(&(a)->type, &(b)->type) - if (node_op_communative(n->op)) { - /* op(lit, X) -> op(X, lit) */ - if (T(CAR(n), N_LIT) && !T(CDR(n), N_LIT)) return OP(CDR(n), CAR(n)); - - /* op(X, not(Y)) -> op(not(Y), X) */ - /* shuffle not left to avoid conflict w/ literals */ - if (T(CDR(n), N_OP_NOT) && !T(CAR(n), N_OP_NOT)) { - return NODE(n->op, CDR(n), CAR(n)); - } - - if (T(CAR(n), N_PHI) && T(CDR(n), N_PHI) && CTRL(CAR(n)) == CTRL(CDR(n)) - && ((node_equiv(CAAR(n), CDAR(n)) && node_equiv(CADR(n), CDDR(n))) - || (node_equiv(CADR(n), CDAR(n)) && node_equiv(CAAR(n), CDDR(n))))) { - return OP(CAAR(n), CDAR(n)); - } - } - - if (node_op_associative(n->op)) { - /* op(X, op(Y,Z)) -> op(op(Y,Z), X) */ - if (!T(CAR(n), n->op) && T(CDR(n), n->op) - && C(CAR(n), CDAR(n))) return OP(CDR(n), CAR(n)); - - /* op(op(X,Y), op(Z, lit)) -> op(op(X, op(Y, Z)), lit) */ - if (T2(CAR(n), CDR(n), n->op) && T(CDDR(n), N_LIT) - && C(CAAR(n), CDAR(n)) && C(CAR(n), CDR(n))) { - return OP(OP(CAAR(n), OP(CADR(n), CDAR(n))), CDDR(n)); - } - - /* op(op(X, lit), lit) -> op(X, op(lit, lit)) */ - if (T(CDR(n), N_LIT) && T(CAR(n), n->op) - && !T(CAAR(n), N_LIT) && T(CADR(n), N_LIT) - && C(CADR(n), CDR(n))) { - return OP(CAAR(n), OP(CADR(n), CDR(n))); - } - - /* op(op(X, lit), Y) -> op(op(X, Y), lit) */ - if (T(CAR(n), n->op) && !T(CAAR(n), N_LIT) - && T(CADR(n), N_LIT) && !T(CDR(n), N_LIT) - && C(CADR(n), CDR(n))) { - return OP(OP(CAAR(n), CDR(n)), CADR(n)); - } - } - - /* optimize based on situations where the input is partly known (e.g. - * one constant input and one not, or identical inputs) */ - -#define INT_EQ(n, v) ((n)->type.lvl == T_CONST && (n)->type.t == T_INT && (n)->val.i == v) -#define BOOL_EQ(n, v) ((n)->type.lvl == T_CONST && (n)->type.t == T_BOOL && (n)->val.i == v) - - switch (n->op) { - case N_OP_NOT: - { - NodeType op = node_cmp_opposite(CAR(n)->op); - if (op != N_NONE) return NODE(op, CAAR(n), CADR(n)); - } - /* fallthrough */ - case N_OP_NEG: - if (T(CAR(n), n->op)) return CAAR(n); - break; - case N_OP_ADD: - if (same) return NODE(N_OP_MUL, CAR(n), node_new_lit_i64(p, 2)); - if (CAR(n)->type.t == T_INT) { - /* a + ~a = -1 */ - if (T(CAR(n), N_OP_NOT) && node_equiv(CAAR(n), CDR(n))) return node_new_lit_i64(p, -1); - if (T(CDR(n), N_LIT) && CDR(n)->val.i < 0) return NODE(N_OP_SUB, CAR(n), node_new_lit_i64(p, -CDR(n)->val.i)); - } - if (T(CAR(n), N_OP_NEG)) return NODE(N_OP_SUB, CDR(n), CAAR(n)); - if (T(CDR(n), N_OP_NEG)) return NODE(N_OP_SUB, CAR(n), CDAR(n)); - if (T(CAR(n), N_OP_SUB) && T(CDR(n), N_OP_SUB) - && node_equiv(CAAR(n), CDDR(n)) && node_equiv(CADR(n), CDAR(n))) { - return node_new_lit_i64(p, 0); - } - goto zero_no_effect; - case N_OP_SUB: - if (same) return node_new_lit_i64(p, 0); - if (node_eql_i64(CAR(n), 0)) return NODE(N_OP_NEG, CDR(n)); - if (node_eql_i64(CDR(n), 0)) return CAR(n); - break; - case N_OP_MUL: - if (node_eql_i64(CDR(n), 0)) return CDR(n); - if (node_eql_i64(CDR(n), 1)) return CAR(n); - { - int po2; - if (T(CDR(n), N_LIT) && CDR(n)->type.t == T_INT && (po2 = u64_power_of_2(CDR(n)->val.u))) {; - return NODE(N_OP_SHL, CAR(n), node_new_lit_i64(p, po2)); - } - } - break; - case N_OP_DIV: - if (node_eql_i64(CDR(n), 0)) { - lex_error_at(l, CDR(n)->src_pos, LE_ERROR, S("divisor always evaluates to zero")); - } - { - int po2; - if (T(CDR(n), N_LIT) && CDR(n)->type.t == T_INT && (po2 = u64_power_of_2(CDR(n)->val.u))) {; - return NODE(N_OP_SHR, CAR(n), node_new_lit_i64(p, po2)); - } - } - break; - case N_OP_OR: - if (same) return CAR(n); - if (is_zero(CDR(n))) return CAR(n); - if (BOOL_EQ(CDR(n), 1)) return CDR(n); - if (CDR(n)->op == node_cmp_opposite(CAR(n)->op) && node_equiv_input(CAR(n), CDR(n))) { - return node_new_lit_bool(p, 1); - } - if (T(CAR(n), N_CMP_LES) && T(CDR(n), N_CMP_EQL) && node_equiv_input(CAR(n), CDR(n))) { - return NODE(N_CMP_LTE, CAAR(n), CADR(n)); - } - if (T(CAR(n), N_CMP_EQL) && T(CDR(n), N_CMP_LES) && node_equiv_input(CAR(n), CDR(n))) { - return NODE(N_CMP_LTE, CDAR(n), CDDR(n)); - } - if (T(CAR(n), N_CMP_GTR) && T(CDR(n), N_CMP_EQL) && node_equiv_input(CAR(n), CDR(n))) { - return NODE(N_CMP_GTE, CAAR(n), CADR(n)); - } - if (T(CAR(n), N_CMP_EQL) && T(CDR(n), N_CMP_GTR) && node_equiv_input(CAR(n), CDR(n))) { - return NODE(N_CMP_GTE, CDAR(n), CDDR(n)); - } - goto zero_no_effect; - case N_OP_AND: - if (same) return CAR(n); - if (BOOL_EQ(CDR(n), 1)) return CAR(n); - if (is_zero(CDR(n))) return node_new_zero(p, CDR(n)); - if (T(CAR(n), N_OP_NOT) && node_equiv(CAAR(n), CDR(n))) return node_new_zero(p, CDR(n)); - if (node_cmp_incompat(CAR(n)->op, CDR(n)->op) && node_equiv_input(CAR(n), CDR(n))) { - return node_new_lit_bool(p, 0); - } - break; - case N_OP_XOR: - if (same) return node_new_zero(p, CAR(n)); - if (CDR(n)->op == node_cmp_opposite(CAR(n)->op) && node_equiv_input(CAR(n), CDR(n))) { - return node_new_lit_bool(p, 1); - } - /* ~bool ^ bool = 1 */ - /* ~i64 ^ i64 = -1 */ - if (T(CAR(n), N_OP_NOT) && node_equiv(CAAR(n), CDR(n))) { - if (CDR(n)->type.t == T_INT) return node_new_lit_i64(p, -1); - if (CDR(n)->type.t == T_BOOL) return node_new_lit_bool(p, 1); - } -zero_no_effect: if (node_eql_i64(CAR(n), 0)) return CDR(n); - if (node_eql_i64(CDR(n), 0)) return CAR(n); - break; - case N_CMP_EQL: - if (same) return node_new_lit_bool(p, 1); - if (node_known_not_equiv(CAR(n), CDR(n))) return node_new_lit_bool(p, 0); - if (BOOL_EQ(CDR(n), 1)) return CAR(n); - if (BOOL_EQ(CDR(n), 0)) return NODE(N_OP_NOT, CAR(n)); - if (T(CAR(n), N_OP_NOT) && node_equiv(CDR(n), CAAR(n))) return node_new_lit_bool(p, 0); - break; - case N_CMP_NEQ: - if (same) return node_new_lit_bool(p, 0); - if (node_known_not_equiv(CAR(n), CDR(n))) return node_new_lit_bool(p, 1); - if (BOOL_EQ(CDR(n), 0)) return CAR(n); - if (BOOL_EQ(CDR(n), 1)) return NODE(N_OP_NOT, CAR(n)); - break; - case N_CMP_LES: - if (same) return node_new_lit_bool(p, 0); - break; - case N_CMP_GTR: - if (same) return node_new_lit_bool(p, 0); - break; - case N_CMP_LTE: - if (same) return node_new_lit_bool(p, 1); - break; - 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_RETURN: - if (CTRL(n)->type.lvl == T_XCTRL) return CTRL(n); - break; - - 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) { - 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)); - } - } - break; - - case N_PHI: - if (same) return CAR(n); - if (CTRL(n)->in.len == 2) { - fprintf(stderr, "ctrl: %s\n", node_type_name(CTRL(n)->op)); - fprintf(stderr, "left: %p\n", (void*)IN(CTRL(n), 0)); - fprintf(stderr, "right: %p\n", (void*)IN(CTRL(n), 1)); - if (IN(CTRL(n), 1)->type.lvl == T_XCTRL) return CAR(n); - if (IN(CTRL(n), 0)->type.lvl == T_XCTRL) return CDR(n); - } - break; - - 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) { - return IN(n, i); - } - } - } - if (live_in == 0) { - return node_new_lit(p, (Value) { - .type = { .lvl = T_XCTRL, .t = T_NONE } - }); - } - } break; - - default: - break; - } - - if (node_op_comparison(n->op)) { - /* cmp(2a, a + b) -> cmp(a, b) */ - if (T(CAR(n), N_OP_SHL) && T(CDR(n), N_OP_ADD) && node_eql_i64(CADR(n), 1)) { - if (node_equiv(CAAR(n), CDAR(n))) return NODE(n->op, CAAR(n), CDDR(n)); - if (node_equiv(CAAR(n), CDDR(n))) return NODE(n->op, CAAR(n), CDAR(n)); - } - if (T(CDR(n), N_OP_SHL) && T(CAR(n), N_OP_ADD) && node_eql_i64(CDDR(n), 1)) { - if (node_equiv(CDAR(n), CAAR(n))) return NODE(n->op, CDAR(n), CADR(n)); - if (node_equiv(CDAR(n), CADR(n))) return NODE(n->op, CDAR(n), CAAR(n)); - } - /* cmp(a + b, a + c) -> cmp(b, c) */ - if (node_op_associative(CAR(n)->op) && T(CAR(n), CDR(n)->op)) { - if (node_equiv(CAAR(n), CDAR(n))) return NODE(n->op, CADR(n), CDDR(n)); - if (node_equiv(CADR(n), CDAR(n))) return NODE(n->op, CAAR(n), CDDR(n)); - if (node_equiv(CAAR(n), CDDR(n))) return NODE(n->op, CADR(n), CDAR(n)); - if (node_equiv(CADR(n), CDDR(n))) return NODE(n->op, CAAR(n), CDAR(n)); - } - if (T2(CAR(n), CDR(n), N_OP_SUB)) { - /* cmp(a - b, b - a) -> cmp(a, b) */ - if (node_equiv(CAAR(n), CDDR(n)) && node_equiv(CADR(n), CDAR(n))) { - return NODE(n->op, CAAR(n), CDAR(n)); - } - /* cmp(a - b, c - b) -> flipcmp(a, c) */ - if (node_equiv(CAAR(n), CDAR(n))) { - return NODE(node_cmp_flip_sign(n->op), CADR(n), CDDR(n)); - } - } - /* cmp(-a, -b) -> flipcmp(a, b) */ - if (T2(CAR(n), CDR(n), N_OP_NEG)) { - return NODE(node_cmp_flip_sign(n->op), CAAR(n), CDAR(n)); - } - } - - return NULL; -} - -Node *node_peephole(Node *n, Proc *p, Lexer *l) { - assert(n->refs > 0); - Node *r = node_idealize(n, p, l); - if (r) { - r->src_pos = n->src_pos; - NODE_KEEP(p, r, node_kill(n, p)); - return r; - } - /* FIXME: figure out why this shows the wrong position when in an assignment */ - return n; -} - /* procedures */ void proc_init(Proc *proc, Str name) { @@ -913,3 +271,87 @@ void scope_uncollect(Scope *scope, Proc *proc, ScopeNameList *nl) { node_remove(proc, nl->data[i].node, proc->keepalive); } } + +/* types */ + +int type_eql(Type *a, Type *b) { + if (a->t != b->t) return 0; + if (a->lvl != b->lvl) return 0; + if (a->next != b->next) return 0; + return a->next ? type_eql(a->next, b->next) : 1; +} + +int type_base_eql(Type *a, Type *b) { + if (a->t != b->t) return 0; + if (a->next != b->next) return 0; + return a->next ? type_base_eql(a->next, b->next) : 1; +} + +int value_eql(Value *a, Value *b) { + if (!type_eql(&a->type, &b->type)) return 0; + return a->i == b->i; +} + +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"); + case T_INT: return S("i64"); + case T_PTR: return str_fmt(arena, "^%S", type_desc(t->next, arena)); + default: return S("N/A"); + } +} + +void type_err(Node *n, Lexer *l) { + Str s = S(""); + for (int i = 0; i < n->in.len; i++) { + if (i > 0) str_cat(&s, S(", "), &l->arena); + str_cat(&s, type_desc(&IN(n, i)->type, &l->arena), &l->arena); + } + lex_error_at(l, n->src_pos, LE_ERROR, str_fmt(&l->arena, "type error %s (%S)", node_type_name(n->op), s)); +} + +int type_check(Node *n) { + switch (n->op) { + case N_PHI: + n->type = (Type) { .lvl = T_TOP, .t = IN(n, 1)->type.t }; + for (int i = 2; i < n->in.len; i++) { + if (!type_base_eql(&IN(n, i)->type, &n->type)) { + return 0; + } + } + return 1; + case N_OP_NEG: + n->type = (Type) { .lvl = T_TOP, .t = T_INT }; + return CAR(n)->type.t == T_INT; + case N_OP_NOT: + n->type = (Type) { .lvl = T_TOP, .t = CAR(n)->type.t }; + return CAR(n)->type.t == T_INT || CAR(n)->type.t == T_BOOL; + case N_OP_AND: case N_OP_OR: case N_OP_XOR: + n->type = (Type) { .lvl = T_TOP, .t = CAR(n)->type.t }; + return (CAR(n)->type.t == T_INT && CDR(n)->type.t == T_INT) + || (CAR(n)->type.t == T_BOOL && CDR(n)->type.t == T_BOOL); + case N_OP_ADD: case N_OP_SUB: case N_OP_MUL: case N_OP_DIV: + case N_OP_SHL: case N_OP_SHR: + n->type = (Type) { .lvl = T_TOP, .t = T_INT }; + return CAR(n)->type.t == T_INT && CDR(n)->type.t == T_INT; + case N_CMP_LES: case N_CMP_GTR: + case N_CMP_LTE: case N_CMP_GTE: + n->type = (Type) { .lvl = T_TOP, .t = T_BOOL }; + return CAR(n)->type.t == T_INT && CDR(n)->type.t == T_INT; + case N_CMP_EQL: + case N_CMP_NEQ: + n->type = (Type) { .lvl = T_TOP, .t = T_BOOL }; + return type_base_eql(&CAR(n)->type, &CDR(n)->type); + /* (CAR(n)->type.t == T_INT && CDR(n)->type.t == T_INT) + || (CAR(n)->type.t == T_BOOL && CDR(n)->type.t == T_BOOL); */ + default: + return 1; + } +} diff --git a/ir.h b/ir.h index 9c6fc0b..ca3e8b4 100644 --- a/ir.h +++ b/ir.h @@ -196,8 +196,6 @@ 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); -Value node_compute(Node *n, Lexer *l); -Node *node_peephole(Node *n, Proc *p, Lexer *l); Node *node_new_lit(Proc *p, Value v); Node *node_new_lit_bool(Proc *p, int b); diff --git a/main.c b/main.c index 26f9534..89d1f3a 100644 --- a/main.c +++ b/main.c @@ -11,6 +11,7 @@ #include "dynarr.h" #include "strio.h" #include "ir.h" +#include "peephole.h" int no_opt = 0; diff --git a/peephole.c b/peephole.c new file mode 100644 index 0000000..42e77ee --- /dev/null +++ b/peephole.c @@ -0,0 +1,559 @@ +#include +#include + +#include "peephole.h" +#include "strio.h" + +extern int no_opt; + +static inline int node_op_communative(NodeType t) { + return NMASK(t) & (NM_OP_ADD | NM_OP_MUL | NM_OP_AND | NM_OP_XOR | NM_OP_OR | NM_CMP_EQL | NM_CMP_NEQ); + /*NodeType ops[] = { N_OP_ADD, N_OP_MUL, N_OP_AND, N_OP_XOR, N_OP_OR, N_CMP_EQL, N_CMP_NEQ }; + for (unsigned i = 0; i < sizeof ops / sizeof *ops; i++) { + if (ops[i] == t) return 1; + } + return 0;*/ +} + +static inline int node_op_associative(NodeType t) { + /*NodeType ops[] = { N_OP_ADD, N_OP_MUL, N_OP_AND, N_OP_XOR, N_OP_OR }; + for (unsigned i = 0; i < sizeof ops / sizeof *ops; i++) { + if (ops[i] == t) return 1; + } + return 0;*/ + return NMASK(t) & (NM_OP_ADD | NM_OP_MUL | NM_OP_AND | NM_OP_XOR | NM_OP_OR); +} + +static inline int node_op_comparison(NodeType t) { + /*NodeType ops[] = { N_CMP_EQL, N_CMP_NEQ, N_CMP_LES, N_CMP_GTR, N_CMP_LTE, N_CMP_GTE }; + for (unsigned i = 0; i < sizeof ops / sizeof *ops; i++) { + if (ops[i] == t) return 1; + } + return 0;*/ + return NMASK(t) & (NM_CMP_EQL | NM_CMP_NEQ | NM_CMP_LES | NM_CMP_GTR | NM_CMP_LTE | NM_CMP_GTE); +} + +/* when applied to the same input, at least one must be true */ +static inline NodeType node_cmp_opposite(NodeType a) { + switch (a) { + case N_CMP_EQL: return N_CMP_NEQ; + case N_CMP_NEQ: return N_CMP_EQL; + case N_CMP_LES: return N_CMP_GTE; + case N_CMP_GTE: return N_CMP_LES; + case N_CMP_GTR: return N_CMP_LTE; + case N_CMP_LTE: return N_CMP_GTR; + default: return N_NONE; + } +} + +static inline NodeType node_cmp_flip_sign(NodeType a) { + switch (a) { + case N_CMP_LES: return N_CMP_GTR; + case N_CMP_LTE: return N_CMP_GTE; + case N_CMP_GTR: return N_CMP_LES; + case N_CMP_GTE: return N_CMP_LTE; + default: return a; + } +} + +/* when applied to the same input, at least one must be false */ +static inline int node_cmp_incompat(NodeType a, NodeType b) { + struct { NodeType l, r; } pairs[] = { + { N_CMP_EQL, N_CMP_NEQ }, + { N_CMP_LES, N_CMP_GTE }, + { N_CMP_GTR, N_CMP_LTE }, + { N_CMP_LES, N_CMP_GTR }, + }; + for (unsigned i = 0; i < sizeof pairs / sizeof *pairs; i++) { + if ((pairs[i].l == a && pairs[i].r == b) || (pairs[i].l == b && pairs[i].r == a)) { + return 1; + } + } + return 0; +} + +Value node_compute(Node *n, Lexer *l) { + Type lit_type = { .lvl = T_BOT }; + for (int i = 1; i < n->in.len; i++) { + Node *p = IN(n, i); + if (p->type.lvl != T_CONST) { + lit_type.lvl = T_BOT; + break; + } + if (!type_eql(&p->type, &lit_type)) { + if (lit_type.lvl == T_BOT) { + lit_type = p->type; + } else { + lit_type.lvl = T_BOT; + break; + } + } + } + + if (lit_type.lvl != T_CONST) return n->val; + + Value v = { .type = lit_type }; + + if (lit_type.t == T_INT) { + switch (n->op) { + 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 (CDR(n)->val.i == 0) { + lex_error_at(l, CDR(n)->src_pos, LE_ERROR, S("divisor always evaluates to zero")); + } + 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; + 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->op) { + 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; + } + + return n->val; +} + +#include + +#define NODE(t, ...) node_peephole(node_new(p, t, CTRL(n), __VA_ARGS__), p, l) +#define OP(...) NODE(n->op, __VA_ARGS__) + +static inline int node_eql_i64(Node *n, int64_t i) { + return n->op == N_LIT && n->type.t == T_INT && n->val.i == i; +} + +static inline int u64_power_of_2(uint64_t x) { + int ldz = 0, tlz = 0; + for (int i = 0; i < 64; i++) { + if ((x >> i) & 1) break; + else tlz++; + } + for (int i = 0; i < 64; i++) { + if ((x << i) & (1UL << 63)) break; + else ldz++; + } + if (ldz + tlz != 63) return 0; + return tlz; +} + +/* functions to query the compile-time equivalence of nodes */ +/* fairly conservative of necessity */ + +static int node_equiv(Node *a, Node *b); +static int node_known_neg_of(Node *a, Node *b) { + if (T(b, N_OP_NEG) && node_equiv(a, CAR(b))) return 1; + if (T(a, N_OP_NEG) && node_equiv(CAR(a), b)) return 1; + if (T(a, N_LIT) && T(b, N_LIT) && (a->type.t == b->type.t) && b->val.i == -a->val.i) return 1; + return 0; +} + +static inline int node_sub_add_equiv(Node *a, Node *b) { + if (node_equiv(CAR(a), CAR(b)) && !node_known_neg_of(CDR(a), CDR(b))) return 1; + if (node_equiv(CAR(a), CDR(b)) && !node_known_neg_of(CDR(a), CAR(b))) return 1; + return 0; +} + +static int node_equiv_input(Node *a, Node *b); + +static int node_equiv(Node *a, Node *b) { + /* will doing this recursively be too slow? */ + if (a == b) return 1; + if (a->op != b->op) return 0; + if (a->in.len != b->in.len) return 0; + if (!value_eql(&a->val, &b->val)) return 0; + if (!node_equiv_input(a, b)) return 0; + return 1; +} + +/* TODO: figure out a more thorough way of comparing node graphs */ + +static inline int node_known_not_equiv_ord(Node *a, Node *b) { + if ((b->op & (NM_OP_ADD | NM_OP_SUB)) && node_equiv(a, CAR(b)) + && T(CDR(b), N_LIT) && !node_eql_i64(CDR(b), 0)) return 1; + if ((a->op & (NM_OP_ADD | NM_OP_SUB)) && node_sub_add_equiv(a, b)) return 1; + return 0; +} +static inline int node_known_not_equiv(Node *a, Node *b) { + return node_known_not_equiv_ord(a, b) || node_known_not_equiv_ord(b, a); +} + +static int node_equiv_input(Node *a, Node *b) { + if (a->in.len != b->in.len) return 0; + if (CTRL(a) != CTRL(b)) return 0; + /* note that this means the order of inputs isn't guaranteed, so be + * careful what you use this procedure for */ + if ((node_op_communative(a->op) || node_op_communative(b->op)) + && node_equiv(CDR(a), CAR(b)) + && node_equiv(CAR(a), CDR(b))) { + /* assuming input count is 2 */ + return 1; + } + for (int i = 1; i < a->in.len; i++) { + if (!node_equiv(IN(a, i), IN(b, i))) return 0; + } + return 1; +} + +Node *node_new_zero(Proc *p, Node *n) { + Value v = { + .type = { + .lvl = T_CONST, + .t = n->type.t, + }, + .i = 0 + }; + Node *r = node_new_lit(p, v); + return r; +} + +static inline int is_zero(Node *n) { + return n->type.lvl == T_CONST && (n->type.t == T_INT || n->type.t == T_BOOL) && !n->val.i; +} + +/* needs lexer for error reporting */ +Node *node_idealize(Node *n, Proc *p, Lexer *l) { + if (!type_check(n)) { + type_err(n, l); + } + + if (no_opt) return NULL; + + /* try to compute a literal value */ + + if (n->op != N_LIT) { + Value v = node_compute(n, 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, NULL, p->start); + r->val = v; + r->src_pos = n->src_pos; + return r; + } + } + + /* try to trim duplicate inputs from the graph */ + + int same = 1, same_ptr = 1; + for (int i = 1; i < n->in.len; i++) { + if (IN(n, i) == CAR(n)) continue; + same_ptr = 0; + if (!node_equiv(IN(n, i), CAR(n))) { + same = 0; + break; + } + } + + if (n->in.len > 2 && same && !same_ptr) { + Node *r = node_new(p, n->op, NULL); + for (int i = 0; i < n->in.len; i++) { + node_add(p, CAR(n), r); + } + return node_peephole(r, p, l); + } + + /* transformations to help encourage constant folding */ + /* the overall trend is to move them rightwards */ + + /* need to check for type compatibility */ + #define C(a, b) type_base_eql(&(a)->type, &(b)->type) + if (node_op_communative(n->op)) { + /* op(lit, X) -> op(X, lit) */ + if (T(CAR(n), N_LIT) && !T(CDR(n), N_LIT)) return OP(CDR(n), CAR(n)); + + /* op(X, not(Y)) -> op(not(Y), X) */ + /* shuffle not left to avoid conflict w/ literals */ + if (T(CDR(n), N_OP_NOT) && !T(CAR(n), N_OP_NOT)) { + return NODE(n->op, CDR(n), CAR(n)); + } + + if (T(CAR(n), N_PHI) && T(CDR(n), N_PHI) && CTRL(CAR(n)) == CTRL(CDR(n)) + && ((node_equiv(CAAR(n), CDAR(n)) && node_equiv(CADR(n), CDDR(n))) + || (node_equiv(CADR(n), CDAR(n)) && node_equiv(CAAR(n), CDDR(n))))) { + return OP(CAAR(n), CDAR(n)); + } + } + + if (node_op_associative(n->op)) { + /* op(X, op(Y,Z)) -> op(op(Y,Z), X) */ + if (!T(CAR(n), n->op) && T(CDR(n), n->op) + && C(CAR(n), CDAR(n))) return OP(CDR(n), CAR(n)); + + /* op(op(X,Y), op(Z, lit)) -> op(op(X, op(Y, Z)), lit) */ + if (T2(CAR(n), CDR(n), n->op) && T(CDDR(n), N_LIT) + && C(CAAR(n), CDAR(n)) && C(CAR(n), CDR(n))) { + return OP(OP(CAAR(n), OP(CADR(n), CDAR(n))), CDDR(n)); + } + + /* op(op(X, lit), lit) -> op(X, op(lit, lit)) */ + if (T(CDR(n), N_LIT) && T(CAR(n), n->op) + && !T(CAAR(n), N_LIT) && T(CADR(n), N_LIT) + && C(CADR(n), CDR(n))) { + return OP(CAAR(n), OP(CADR(n), CDR(n))); + } + + /* op(op(X, lit), Y) -> op(op(X, Y), lit) */ + if (T(CAR(n), n->op) && !T(CAAR(n), N_LIT) + && T(CADR(n), N_LIT) && !T(CDR(n), N_LIT) + && C(CADR(n), CDR(n))) { + return OP(OP(CAAR(n), CDR(n)), CADR(n)); + } + } + + /* optimize based on situations where the input is partly known (e.g. + * one constant input and one not, or identical inputs) */ + +#define INT_EQ(n, v) ((n)->type.lvl == T_CONST && (n)->type.t == T_INT && (n)->val.i == v) +#define BOOL_EQ(n, v) ((n)->type.lvl == T_CONST && (n)->type.t == T_BOOL && (n)->val.i == v) + + switch (n->op) { + case N_OP_NOT: + { + NodeType op = node_cmp_opposite(CAR(n)->op); + if (op != N_NONE) return NODE(op, CAAR(n), CADR(n)); + } + /* fallthrough */ + case N_OP_NEG: + if (T(CAR(n), n->op)) return CAAR(n); + break; + case N_OP_ADD: + if (same) return NODE(N_OP_MUL, CAR(n), node_new_lit_i64(p, 2)); + if (CAR(n)->type.t == T_INT) { + /* a + ~a = -1 */ + if (T(CAR(n), N_OP_NOT) && node_equiv(CAAR(n), CDR(n))) return node_new_lit_i64(p, -1); + if (T(CDR(n), N_LIT) && CDR(n)->val.i < 0) return NODE(N_OP_SUB, CAR(n), node_new_lit_i64(p, -CDR(n)->val.i)); + } + if (T(CAR(n), N_OP_NEG)) return NODE(N_OP_SUB, CDR(n), CAAR(n)); + if (T(CDR(n), N_OP_NEG)) return NODE(N_OP_SUB, CAR(n), CDAR(n)); + if (T(CAR(n), N_OP_SUB) && T(CDR(n), N_OP_SUB) + && node_equiv(CAAR(n), CDDR(n)) && node_equiv(CADR(n), CDAR(n))) { + return node_new_lit_i64(p, 0); + } + goto zero_no_effect; + case N_OP_SUB: + if (same) return node_new_lit_i64(p, 0); + if (node_eql_i64(CAR(n), 0)) return NODE(N_OP_NEG, CDR(n)); + if (node_eql_i64(CDR(n), 0)) return CAR(n); + break; + case N_OP_MUL: + if (node_eql_i64(CDR(n), 0)) return CDR(n); + if (node_eql_i64(CDR(n), 1)) return CAR(n); + { + int po2; + if (T(CDR(n), N_LIT) && CDR(n)->type.t == T_INT && (po2 = u64_power_of_2(CDR(n)->val.u))) {; + return NODE(N_OP_SHL, CAR(n), node_new_lit_i64(p, po2)); + } + } + break; + case N_OP_DIV: + if (node_eql_i64(CDR(n), 0)) { + lex_error_at(l, CDR(n)->src_pos, LE_ERROR, S("divisor always evaluates to zero")); + } + { + int po2; + if (T(CDR(n), N_LIT) && CDR(n)->type.t == T_INT && (po2 = u64_power_of_2(CDR(n)->val.u))) {; + return NODE(N_OP_SHR, CAR(n), node_new_lit_i64(p, po2)); + } + } + break; + case N_OP_OR: + if (same) return CAR(n); + if (is_zero(CDR(n))) return CAR(n); + if (BOOL_EQ(CDR(n), 1)) return CDR(n); + if (CDR(n)->op == node_cmp_opposite(CAR(n)->op) && node_equiv_input(CAR(n), CDR(n))) { + return node_new_lit_bool(p, 1); + } + if (T(CAR(n), N_CMP_LES) && T(CDR(n), N_CMP_EQL) && node_equiv_input(CAR(n), CDR(n))) { + return NODE(N_CMP_LTE, CAAR(n), CADR(n)); + } + if (T(CAR(n), N_CMP_EQL) && T(CDR(n), N_CMP_LES) && node_equiv_input(CAR(n), CDR(n))) { + return NODE(N_CMP_LTE, CDAR(n), CDDR(n)); + } + if (T(CAR(n), N_CMP_GTR) && T(CDR(n), N_CMP_EQL) && node_equiv_input(CAR(n), CDR(n))) { + return NODE(N_CMP_GTE, CAAR(n), CADR(n)); + } + if (T(CAR(n), N_CMP_EQL) && T(CDR(n), N_CMP_GTR) && node_equiv_input(CAR(n), CDR(n))) { + return NODE(N_CMP_GTE, CDAR(n), CDDR(n)); + } + goto zero_no_effect; + case N_OP_AND: + if (same) return CAR(n); + if (BOOL_EQ(CDR(n), 1)) return CAR(n); + if (is_zero(CDR(n))) return node_new_zero(p, CDR(n)); + if (T(CAR(n), N_OP_NOT) && node_equiv(CAAR(n), CDR(n))) return node_new_zero(p, CDR(n)); + if (node_cmp_incompat(CAR(n)->op, CDR(n)->op) && node_equiv_input(CAR(n), CDR(n))) { + return node_new_lit_bool(p, 0); + } + break; + case N_OP_XOR: + if (same) return node_new_zero(p, CAR(n)); + if (CDR(n)->op == node_cmp_opposite(CAR(n)->op) && node_equiv_input(CAR(n), CDR(n))) { + return node_new_lit_bool(p, 1); + } + /* ~bool ^ bool = 1 */ + /* ~i64 ^ i64 = -1 */ + if (T(CAR(n), N_OP_NOT) && node_equiv(CAAR(n), CDR(n))) { + if (CDR(n)->type.t == T_INT) return node_new_lit_i64(p, -1); + if (CDR(n)->type.t == T_BOOL) return node_new_lit_bool(p, 1); + } +zero_no_effect: if (node_eql_i64(CAR(n), 0)) return CDR(n); + if (node_eql_i64(CDR(n), 0)) return CAR(n); + break; + case N_CMP_EQL: + if (same) return node_new_lit_bool(p, 1); + if (node_known_not_equiv(CAR(n), CDR(n))) return node_new_lit_bool(p, 0); + if (BOOL_EQ(CDR(n), 1)) return CAR(n); + if (BOOL_EQ(CDR(n), 0)) return NODE(N_OP_NOT, CAR(n)); + if (T(CAR(n), N_OP_NOT) && node_equiv(CDR(n), CAAR(n))) return node_new_lit_bool(p, 0); + break; + case N_CMP_NEQ: + if (same) return node_new_lit_bool(p, 0); + if (node_known_not_equiv(CAR(n), CDR(n))) return node_new_lit_bool(p, 1); + if (BOOL_EQ(CDR(n), 0)) return CAR(n); + if (BOOL_EQ(CDR(n), 1)) return NODE(N_OP_NOT, CAR(n)); + break; + case N_CMP_LES: + if (same) return node_new_lit_bool(p, 0); + break; + case N_CMP_GTR: + if (same) return node_new_lit_bool(p, 0); + break; + case N_CMP_LTE: + if (same) return node_new_lit_bool(p, 1); + break; + 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_RETURN: + if (CTRL(n)->type.lvl == T_XCTRL) return CTRL(n); + break; + + 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) { + 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)); + } + } + break; + + case N_PHI: + if (same) return CAR(n); + if (CTRL(n)->in.len == 2) { + fprintf(stderr, "ctrl: %s\n", node_type_name(CTRL(n)->op)); + fprintf(stderr, "left: %p\n", (void*)IN(CTRL(n), 0)); + fprintf(stderr, "right: %p\n", (void*)IN(CTRL(n), 1)); + if (IN(CTRL(n), 1)->type.lvl == T_XCTRL) return CAR(n); + if (IN(CTRL(n), 0)->type.lvl == T_XCTRL) return CDR(n); + } + break; + + 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) { + return IN(n, i); + } + } + } + if (live_in == 0) { + return node_new_lit(p, (Value) { + .type = { .lvl = T_XCTRL, .t = T_NONE } + }); + } + } break; + + default: + break; + } + + if (node_op_comparison(n->op)) { + /* cmp(2a, a + b) -> cmp(a, b) */ + if (T(CAR(n), N_OP_SHL) && T(CDR(n), N_OP_ADD) && node_eql_i64(CADR(n), 1)) { + if (node_equiv(CAAR(n), CDAR(n))) return NODE(n->op, CAAR(n), CDDR(n)); + if (node_equiv(CAAR(n), CDDR(n))) return NODE(n->op, CAAR(n), CDAR(n)); + } + if (T(CDR(n), N_OP_SHL) && T(CAR(n), N_OP_ADD) && node_eql_i64(CDDR(n), 1)) { + if (node_equiv(CDAR(n), CAAR(n))) return NODE(n->op, CDAR(n), CADR(n)); + if (node_equiv(CDAR(n), CADR(n))) return NODE(n->op, CDAR(n), CAAR(n)); + } + /* cmp(a + b, a + c) -> cmp(b, c) */ + if (node_op_associative(CAR(n)->op) && T(CAR(n), CDR(n)->op)) { + if (node_equiv(CAAR(n), CDAR(n))) return NODE(n->op, CADR(n), CDDR(n)); + if (node_equiv(CADR(n), CDAR(n))) return NODE(n->op, CAAR(n), CDDR(n)); + if (node_equiv(CAAR(n), CDDR(n))) return NODE(n->op, CADR(n), CDAR(n)); + if (node_equiv(CADR(n), CDDR(n))) return NODE(n->op, CAAR(n), CDAR(n)); + } + if (T2(CAR(n), CDR(n), N_OP_SUB)) { + /* cmp(a - b, b - a) -> cmp(a, b) */ + if (node_equiv(CAAR(n), CDDR(n)) && node_equiv(CADR(n), CDAR(n))) { + return NODE(n->op, CAAR(n), CDAR(n)); + } + /* cmp(a - b, c - b) -> flipcmp(a, c) */ + if (node_equiv(CAAR(n), CDAR(n))) { + return NODE(node_cmp_flip_sign(n->op), CADR(n), CDDR(n)); + } + } + /* cmp(-a, -b) -> flipcmp(a, b) */ + if (T2(CAR(n), CDR(n), N_OP_NEG)) { + return NODE(node_cmp_flip_sign(n->op), CAAR(n), CDAR(n)); + } + } + + return NULL; +} + +Node *node_peephole(Node *n, Proc *p, Lexer *l) { + assert(n->refs > 0); + Node *r = node_idealize(n, p, l); + if (r) { + r->src_pos = n->src_pos; + NODE_KEEP(p, r, node_kill(n, p)); + return r; + } + /* FIXME: figure out why this shows the wrong position when in an assignment */ + return n; +} diff --git a/peephole.h b/peephole.h new file mode 100644 index 0000000..e9a2cab --- /dev/null +++ b/peephole.h @@ -0,0 +1,9 @@ +#ifndef PEEPHOLE_H +#define PEEPHOLE_H + +#include "ir.h" + +Value node_compute(Node *n, Lexer *l); +Node *node_peephole(Node *n, Proc *p, Lexer *l); + +#endif -- cgit v1.2.3