diff options
Diffstat (limited to 'ir.c')
| -rw-r--r-- | ir.c | 726 |
1 files changed, 84 insertions, 642 deletions
@@ -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 <stdio.h> - -#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; + } +} |