diff options
| -rw-r--r-- | ir.c | 225 | ||||
| -rw-r--r-- | ir.h | 88 | ||||
| -rw-r--r-- | main.c | 92 | ||||
| -rw-r--r-- | test.lang | 14 |
4 files changed, 253 insertions, 166 deletions
@@ -6,28 +6,11 @@ extern int no_opt; -/* convenience macros (lisp-inspired lol) */ - -#define IN(n, i) ((n)->in.data[i]) -#define OUT(n, i) ((n)->out.data[i]) - -#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)) -#define CDDR(n) CDR(CDR(n)) -#define CAAAR(n) CAR(CAAR(n)) -#define CAADR(n) CDR(CAAR(n)) -#define CADAR(n) CAR(CADR(n)) -#define CADDR(n) CDR(CADR(n)) -#define CDAAR(n) CAR(CDAR(n)) -#define CDADR(n) CDR(CDAR(n)) -#define CDDAR(n) CAR(CDDR(n)) -#define CDDDR(n) CDR(CDDR(n)) -#define T(a,b) ((a)->type == b) -#define T2(a,b,t) ((a)->type == t && (b)->type == t) +/* TODO: + * + * Separate normal graph manipulation from peephole optimization code. + * + */ /* types */ @@ -69,45 +52,45 @@ 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)->val.type, &l->arena), &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->type), s)); + 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->type) { + switch (n->op) { case N_PHI: - n->val.type = (Type) { .lvl = T_TOP, .t = IN(n, 1)->val.type.t }; + 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)->val.type, &n->val.type)) { + if (!type_base_eql(&IN(n, i)->type, &n->type)) { return 0; } } return 1; case N_OP_NEG: - n->val.type = (Type) { .lvl = T_TOP, .t = T_INT }; - return CAR(n)->val.type.t == T_INT; + n->type = (Type) { .lvl = T_TOP, .t = T_INT }; + return CAR(n)->type.t == T_INT; case N_OP_NOT: - n->val.type = (Type) { .lvl = T_TOP, .t = CAR(n)->val.type.t }; - return CAR(n)->val.type.t == T_INT || CAR(n)->val.type.t == T_BOOL; + 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->val.type = (Type) { .lvl = T_TOP, .t = CAR(n)->val.type.t }; - return (CAR(n)->val.type.t == T_INT && CDR(n)->val.type.t == T_INT) - || (CAR(n)->val.type.t == T_BOOL && CDR(n)->val.type.t == T_BOOL); + 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->val.type = (Type) { .lvl = T_TOP, .t = T_INT }; - return CAR(n)->val.type.t == T_INT && CDR(n)->val.type.t == T_INT; + 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->val.type = (Type) { .lvl = T_TOP, .t = T_BOOL }; - return CAR(n)->val.type.t == T_INT && CDR(n)->val.type.t == T_INT; + 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->val.type = (Type) { .lvl = T_TOP, .t = T_BOOL }; - return type_base_eql(&CAR(n)->val.type, &CDR(n)->val.type); - /* (CAR(n)->val.type.t == T_INT && CDR(n)->val.type.t == T_INT) - || (CAR(n)->val.type.t == T_BOOL && CDR(n)->val.type.t == T_BOOL); */ + 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; } @@ -133,7 +116,6 @@ const char *node_type_name(NodeType t) { "greater", "less-or-equal", "greater-or-equal", - "value" }; return names[t]; } @@ -222,7 +204,7 @@ Node *node_new_empty(Proc *p, NodeType t) { } else { n = new(&p->arena, Node); } - n->type = t; + n->op = t; n->id = global_node_count++; return n; } @@ -248,7 +230,7 @@ Node *node_dedup_lit(Proc *p, Value v) { * how many literals even usually occur in a procedure? */ for (int i = 0; i < p->start->out.len; i++) { Node *t = p->start->out.data[i]; - if (t->type == N_LIT && type_eql(&t->val.type, &v.type) && t->val.i == v.i) { + if (t->op == N_LIT && type_eql(&t->type, &v.type) && t->val.i == v.i) { return t; } } @@ -272,41 +254,43 @@ Node *node_new_lit_bool(Proc *p, int b) { } static inline int node_op_communative(NodeType t) { - NodeType ops[] = { N_OP_ADD, N_OP_MUL, N_OP_AND, N_OP_XOR, N_OP_OR, N_CMP_EQL, N_CMP_NEQ }; + 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; + 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 }; + /*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 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 }; + /*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 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) { - struct { NodeType l, r; } pairs[] = { - { N_CMP_EQL, N_CMP_NEQ }, - { N_CMP_LES, N_CMP_GTE }, - { N_CMP_GTR, N_CMP_LTE }, - }; - for (unsigned i = 0; i < sizeof pairs / sizeof *pairs; i++) { - if (pairs[i].l == a) return pairs[i].r; - if (pairs[i].r == a) return pairs[i].l; + 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; } - return N_NONE; } static inline NodeType node_cmp_flip_sign(NodeType a) { @@ -339,13 +323,13 @@ 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->val.type.lvl != T_CONST) { + if (p->type.lvl != T_CONST) { lit_type.lvl = T_BOT; break; } - if (!type_eql(&p->val.type, &lit_type)) { + if (!type_eql(&p->type, &lit_type)) { if (lit_type.lvl == T_BOT) { - lit_type = p->val.type; + lit_type = p->type; } else { lit_type.lvl = T_BOT; break; @@ -358,7 +342,7 @@ Value node_compute(Node *n, Lexer *l) { Value v = { .type = lit_type }; if (lit_type.t == T_INT) { - switch (n->type) { + 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; @@ -385,7 +369,7 @@ Value node_compute(Node *n, Lexer *l) { } return v; } else if (lit_type.t == T_BOOL) { - switch (n->type) { + 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; @@ -403,10 +387,10 @@ Value node_compute(Node *n, Lexer *l) { #include <stdio.h> #define NODE(t, ...) node_peephole(node_new(p, t, CTRL(n), __VA_ARGS__), p, l) -#define OP(...) NODE(n->type, __VA_ARGS__) +#define OP(...) NODE(n->op, __VA_ARGS__) static inline int node_eql_i64(Node *n, int64_t i) { - return n->type == N_LIT && n->val.type.t == T_INT && n->val.i == 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) { @@ -430,7 +414,7 @@ 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->val.type.t == b->val.type.t) && b->val.i == -a->val.i) 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; } @@ -445,7 +429,7 @@ 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->type != b->type) return 0; + 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; @@ -455,9 +439,9 @@ static int node_equiv(Node *a, Node *b) { /* TODO: figure out a more thorough way of comparing node graphs */ static inline int node_known_not_equiv_ord(Node *a, Node *b) { - if ((T(b, N_OP_ADD) || T(b, N_OP_SUB)) && node_equiv(a, CAR(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 (T(a, N_OP_SUB) && T(b, N_OP_ADD) && node_sub_add_equiv(a, b)) 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) { @@ -469,7 +453,7 @@ static int node_equiv_input(Node *a, Node *b) { 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->type) || node_op_communative(b->type)) + 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 */ @@ -485,7 +469,7 @@ Node *node_new_zero(Proc *p, Node *n) { Value v = { .type = { .lvl = T_CONST, - .t = n->val.type.t, + .t = n->type.t, }, .i = 0 }; @@ -494,7 +478,7 @@ Node *node_new_zero(Proc *p, Node *n) { } static inline int is_zero(Node *n) { - return n->val.type.lvl == T_CONST && (n->val.type.t == T_INT || n->val.type.t == T_BOOL) && !n->val.i; + return n->type.lvl == T_CONST && (n->type.t == T_INT || n->type.t == T_BOOL) && !n->val.i; } /* needs lexer for error reporting */ @@ -507,7 +491,7 @@ Node *node_idealize(Node *n, Proc *p, Lexer *l) { /* try to compute a literal value */ - if (n->type != N_LIT) { + if (n->op != N_LIT) { Value v = node_compute(n, l); if (v.type.lvl == T_CONST) { Node *t = node_dedup_lit(p, v); @@ -532,7 +516,7 @@ Node *node_idealize(Node *n, Proc *p, Lexer *l) { } if (n->in.len > 2 && same && !same_ptr) { - Node *r = node_new(p, n->type, NULL); + Node *r = node_new(p, n->op, NULL); for (int i = 0; i < n->in.len; i++) { node_add(p, CAR(n), r); } @@ -543,15 +527,15 @@ Node *node_idealize(Node *n, Proc *p, Lexer *l) { /* the overall trend is to move them rightwards */ /* need to check for type compatibility */ - #define C(a, b) type_eql(&(a)->val.type, &(b)->val.type) - if (node_op_communative(n->type)) { + #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->type, CDR(n), CAR(n)); + 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)) @@ -561,26 +545,26 @@ Node *node_idealize(Node *n, Proc *p, Lexer *l) { } } - if (node_op_associative(n->type)) { + if (node_op_associative(n->op)) { /* op(X, op(Y,Z)) -> op(op(Y,Z), X) */ - /*if (!T(CAR(n), n->type) && T(CDR(n), n->type) - && C(CAR(n), CDAR(n))) return OP(CDR(n), CAR(n));*/ + 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->type) && T(CDDR(n), N_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->type) + 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->type) && !T(CAAR(n), N_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)); @@ -590,22 +574,22 @@ Node *node_idealize(Node *n, Proc *p, Lexer *l) { /* 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)->val.type.lvl == T_CONST && (n)->val.type.t == T_INT && (n)->val.i == v) -#define BOOL_EQ(n, v) ((n)->val.type.lvl == T_CONST && (n)->val.type.t == T_BOOL && (n)->val.i == v) +#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->type) { + switch (n->op) { case N_OP_NOT: { - NodeType op = node_cmp_opposite(CAR(n)->type); + 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->type)) return CAAR(n); + 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)->val.type.t == T_INT) { + 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)); @@ -627,7 +611,7 @@ Node *node_idealize(Node *n, Proc *p, Lexer *l) { if (node_eql_i64(CDR(n), 1)) return CAR(n); { int po2; - if (T(CDR(n), N_LIT) && CDR(n)->val.type.t == T_INT && (po2 = u64_power_of_2(CDR(n)->val.u))) {; + 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)); } } @@ -638,7 +622,7 @@ Node *node_idealize(Node *n, Proc *p, Lexer *l) { } { int po2; - if (T(CDR(n), N_LIT) && CDR(n)->val.type.t == T_INT && (po2 = u64_power_of_2(CDR(n)->val.u))) {; + 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)); } } @@ -647,7 +631,7 @@ Node *node_idealize(Node *n, Proc *p, Lexer *l) { 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)->type == node_cmp_opposite(CAR(n)->type) && node_equiv_input(CAR(n), 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))) { @@ -668,20 +652,20 @@ Node *node_idealize(Node *n, Proc *p, Lexer *l) { 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)->type, CDR(n)->type) && node_equiv_input(CAR(n), 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)->type == node_cmp_opposite(CAR(n)->type) && node_equiv_input(CAR(n), 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); } /* ~bool ^ bool = 1 */ /* ~i64 ^ i64 = -1 */ if (T(CAR(n), N_OP_NOT) && node_equiv(CAAR(n), CDR(n))) { - if (CDR(n)->val.type.t == T_INT) return node_new_lit_i64(p, -1); - if (CDR(n)->val.type.t == T_BOOL) return node_new_lit_bool(p, 1); + 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); @@ -723,11 +707,11 @@ zero_no_effect: if (node_eql_i64(CAR(n), 0)) return CDR(n); break; case N_RETURN: - if (CTRL(n)->val.type.lvl == T_XCTRL) return CTRL(n); + if (CTRL(n)->type.lvl == T_XCTRL) return CTRL(n); break; case N_PROJ: - if (T(CTRL(n), N_IF_ELSE) && CTRL(n)->val.type.t == T_TUPLE) { + 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 } @@ -741,19 +725,24 @@ zero_no_effect: if (node_eql_i64(CAR(n), 0)) return CDR(n); case N_PHI: if (same) return CAR(n); - if (IN(CTRL(n), 1)->val.type.lvl == T_XCTRL) return CAR(n); - if (IN(CTRL(n), 0)->val.type.lvl == T_XCTRL) return CDR(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: { int live_in = 0; for (int i = 0; i < n->in.len; i++) { - if (IN(n, i)->val.type.lvl != T_XCTRL) live_in++; + 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)->val.type.lvl != T_XCTRL) { + if (IN(n, i)->type.lvl != T_XCTRL) { return IN(n, i); } } @@ -770,36 +759,36 @@ zero_no_effect: if (node_eql_i64(CAR(n), 0)) return CDR(n); break; } - if (node_op_comparison(n->type)) { + 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->type, CAAR(n), CDDR(n)); - if (node_equiv(CAAR(n), CDDR(n))) return NODE(n->type, CAAR(n), CDAR(n)); + 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->type, CDAR(n), CADR(n)); - if (node_equiv(CDAR(n), CADR(n))) return NODE(n->type, CDAR(n), CAAR(n)); + 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)->type) && T(CAR(n), CDR(n)->type)) { - if (node_equiv(CAAR(n), CDAR(n))) return NODE(n->type, CADR(n), CDDR(n)); - if (node_equiv(CADR(n), CDAR(n))) return NODE(n->type, CAAR(n), CDDR(n)); - if (node_equiv(CAAR(n), CDDR(n))) return NODE(n->type, CADR(n), CDAR(n)); - if (node_equiv(CADR(n), CDDR(n))) return NODE(n->type, CAAR(n), CDAR(n)); + 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->type, CAAR(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->type), CADR(n), CDDR(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->type), CAAR(n), CDAR(n)); + return NODE(node_cmp_flip_sign(n->op), CAAR(n), CDAR(n)); } } @@ -823,7 +812,7 @@ 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(proc, N_START, NULL); - proc->start->val.type = (Type) { + proc->start->type = (Type) { .lvl = T_BOT, .t = T_TUPLE, .next = NULL @@ -22,11 +22,11 @@ typedef enum { T_BOOL, T_INT, T_PTR -} BaseType; +} TypeKind; typedef struct Type { TypeLevel lvl; - BaseType t; + TypeKind t; struct Type *next; } Type; @@ -49,21 +49,49 @@ void type_err(struct Node *n, Lexer *l); /* nodes */ +#define NODE_TYPE_LIST\ + X(NONE, "invalid node")\ + X(START, "start")\ + X(IF_ELSE, "if-else")\ + X(REGION, "region")\ + X(PHI, "phi")\ + X(STOP, "stop")\ + X(PROJ, "projection")\ + X(RETURN, "return")\ + X(KEEPALIVE, "keepalive")\ + X(LIT, "literal")\ + X(OP_ADD, "add")\ + X(OP_SUB, "sub")\ + X(OP_MUL, "mul")\ + X(OP_DIV, "div")\ + X(OP_AND, "and")\ + X(OP_OR, "or")\ + X(OP_XOR, "xor")\ + X(OP_SHL, "shl")\ + X(OP_SHR, "shr")\ + X(OP_NEG, "neg")\ + X(OP_NOT, "not")\ + X(CMP_EQL, "equal")\ + X(CMP_NEQ, "not-equal")\ + X(CMP_LES, "less-than")\ + X(CMP_GTR, "greater-than")\ + X(CMP_LTE, "less-or-equal")\ + X(CMP_GTE, "greater-or-equal") + typedef enum { - N_NONE, - N_START, N_IF_ELSE, N_REGION, N_PHI, N_STOP, - N_PROJ, - N_RETURN, - N_KEEPALIVE, - N_LIT, - N_OP_ADD, N_OP_SUB, N_OP_MUL, N_OP_DIV, - N_OP_AND, N_OP_OR, N_OP_XOR, - N_OP_SHL, N_OP_SHR, - N_OP_NEG, N_OP_NOT, - N_CMP_EQL, N_CMP_NEQ, N_CMP_LES, N_CMP_GTR, N_CMP_LTE, N_CMP_GTE, - N_VALUE +#define X(n, name) N_##n, + NODE_TYPE_LIST +#undef X + N_MAX } NodeType; +#define NMASK(n) (1L << n) +typedef enum { +#define X(n, name) NM_##n = NMASK(N_##n), + NODE_TYPE_LIST +#undef X +} NodeMask; + const char *node_type_name(NodeType t); typedef DYNARR(struct Node *) NodeList; @@ -75,15 +103,43 @@ typedef struct Node { struct Node *prev_free; struct { int walked; - NodeType type; + NodeType op; LexSpan src_pos; NodeInputs in; /* note: index 0 used for control flow */ NodeOutputs out; - Value val; + union { + Type type; + Value val; + }; }; }; } Node; +/* convenience macros (lisp-inspired lol) */ + +#define IN(n, i) ((n)->in.data[i]) +#define OUT(n, i) ((n)->out.data[i]) + +#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)) +#define CDDR(n) CDR(CDR(n)) +#define CAAAR(n) CAR(CAAR(n)) +#define CAADR(n) CDR(CAAR(n)) +#define CADAR(n) CAR(CADR(n)) +#define CADDR(n) CDR(CADR(n)) +#define CDAAR(n) CAR(CDAR(n)) +#define CDADR(n) CDR(CDAR(n)) +#define CDDAR(n) CAR(CDDR(n)) +#define CDDDR(n) CDR(CDDR(n)) +#define T(a,b) ((a)->op == b) +#define T2(a,b,t) ((a)->op == t && (b)->op == t) + + + /* procedure graph */ typedef struct NameBinding { @@ -47,9 +47,6 @@ Node *ctrl(Proc *p, Node *n) { }); return NULL; } - if (p->ctrl->val.type.lvl == T_XCTRL) { - return NULL; - } p->ctrl = n; return n; } @@ -61,16 +58,16 @@ void parse_return(Lexer *l, Proc *p) { n = node_new(p, N_RETURN, p->ctrl); } else { Node *e = parse_expr(l, p); - if (!type_base_eql(&e->val.type, &p->ret_type)) { + if (!type_base_eql(&e->type, &p->ret_type)) { lex_error_at(l, e->src_pos, LE_ERROR, str_fmt(&p->arena, "incorrect return type (expected %S, got %S)", type_desc(&p->ret_type, &p->arena), - type_desc(&e->val.type, &p->arena))); + type_desc(&e->type, &p->arena))); } n = node_new(p, N_RETURN, p->ctrl, e); } n = node_peephole(n, p, l); - if (n->val.type.lvl != T_XCTRL) { + if (n->type.lvl != T_XCTRL) { node_add(p, n, p->stop); } ctrl(p, n); @@ -121,17 +118,49 @@ void parse_assign(Lexer *l, Proc *p) { lex_error_at(l, pos, LE_ERROR, S("undeclared identifier")); } Node *e = parse_expr(l, p); - if (!type_base_eql(&e->val.type, &b->node->val.type)) { + if (!type_base_eql(&e->type, &b->node->type)) { lex_error_at(l, pos, LE_ERROR, str_fmt(&p->arena, "tried to assign value of type %S to variable of type %S", - type_desc(&e->val.type, &p->arena), - type_desc(&b->node->val.type, &p->arena))); + type_desc(&e->type, &p->arena), + type_desc(&b->node->type, &p->arena))); } scope_update(b, e, p); } -void merge_scope(Lexer *l, Proc *p, ScopeNameList *before, ScopeNameList *ntrue, ScopeNameList *nfalse) { - node_add(p, p->ctrl, p->keepalive); +/* TODO: Implement a better system for this. + * + * Something like: + * + * ScopeChangeList chg_true = {0}, chg_false = {0}; + * scope_track_changes(&p->scope, &chg_true, p, scratch); + * parse_block(l, p); + * scope_rewind_changes(&p->scope, &chg_true, p); + * scope_track_changes(&p->scope, &chg_false, p, scratch); + * parse_block(l, p); + * scope_merge_changes(&p->scope, &chg_true, &chg_false, region, p); + * + * We put a flag in Scope somewhere that marks where it's tracking changes to, + * then have scope_update() look up the name binding being changed in the change + * list; if present, update value to the new node. If not, create it with + * orig set to the previous value of the name binding, and value to the new node. + * Since we're only tracking _changes_, there should be some way to make sure that + * newly created let-bindings after tracking starts aren't stored in the list. + * Maybe give NameBindings an index, note the index of the latest binding at the + * time scope_track_changes() is called, ignore any larger than it. + * + * Take care with making sure changes remain attached to keepalive --- rewind + * doesn't remove the new values, since it's just to revert temporarily. + * + * Also, probably should have a scratch arena for this sort of throwaway parsing + * data, instead of putting stuff in the procedure graph arena. It can be reset + * after each statement. + * + * Also also, switch scopes from a linked list to something a bit faster, like + * a simple arena-backed hash trie. + * + */ + +void merge_scope(Lexer *l, Proc *p, Node *region, ScopeNameList *before, ScopeNameList *ntrue, ScopeNameList *nfalse) { for (int i = 0; i < before->len; i++) { int j, k; ScopeName *b4 = &before->data[i]; @@ -143,21 +172,20 @@ void merge_scope(Lexer *l, Proc *p, ScopeNameList *before, ScopeNameList *ntrue, Node *phi; if (!no) { if (yes->node == b4->node) continue; - phi = node_new(p, N_PHI, p->ctrl, yes->node, b4->node); + phi = node_new(p, N_PHI, region, yes->node, b4->node); } else if (!yes) { if (no->node == b4->node) continue; - phi = node_new(p, N_PHI, p->ctrl, b4->node, no->node); + phi = node_new(p, N_PHI, region, b4->node, no->node); } else { if (yes->node == b4->node && no->node == b4->node) continue; - phi = node_new(p, N_PHI, p->ctrl, yes->node, no->node); + phi = node_new(p, N_PHI, region, yes->node, no->node); } - //fprintf(stderr, "phi('%.*s', %d, %d)\n", (int)b4->name.n, b4->name.s, phi->in.data[1]->id, phi->in.data[2]->id); + fprintf(stderr, "phi('%.*s', %d, %d)\n", (int)b4->name.n, b4->name.s, phi->in.data[1]->id, phi->in.data[2]->id); phi = node_peephole(phi, p, l); NameBinding *b = scope_find(&p->scope, b4->name); assert(b); scope_update(b, phi, p); } - node_remove(p, p->ctrl, p->keepalive); } /* TODO: find out a way to encode known relations between nodes, based on the @@ -206,9 +234,9 @@ void parse_if(Lexer *l, Proc *p) { node_add(p, if_false, p->keepalive); ScopeNameList scope_before = { 0 }, scope_true = { 0 }, scope_false = { 0 }; scope_collect(&p->scope, p, &scope_before, &p->arena); - if (cond->val.type.lvl == T_CONST) { - if (cond->val.i) if_false->val.type.lvl = T_XCTRL; - else if_true->val.type.lvl = T_XCTRL; + 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); //assert(if_true->in.len > 0); @@ -233,6 +261,8 @@ void parse_if(Lexer *l, Proc *p) { if (ctrl_else) { //assert(ctrl_if->in.len > 0); //assert(ctrl_else->in.len > 0); + 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); @@ -240,6 +270,8 @@ void parse_if(Lexer *l, Proc *p) { } else { //assert(ctrl_if->in.len > 0); //assert(if_false->in.len > 0); + 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); @@ -251,12 +283,14 @@ void parse_if(Lexer *l, Proc *p) { node_remove(p, if_false, p->keepalive); //p->ctrl = node_peephole(node_new(p, N_REGION, if_true, if_false), p, l); assert(p->ctrl->in.len > 0); - merge_scope(l, p, &scope_before, &scope_true, &scope_false); + 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); - assert(p->ctrl == region); + //assert(p->ctrl == region); /* make sure we're not orphaning any phi nodes*/ if (p->ctrl->out.len < 1) { ctrl(p, node_peephole(p->ctrl, p, l)); @@ -334,7 +368,7 @@ void parse_args_list(Lexer *l, Proc *proc) { lex_expected(l, TM_RPAREN | TM_COMMA); for (int j = 0; j < id; j++) { Node *proj = node_new(proc, N_PROJ, proc->start); - proj->val.type = v.type; + proj->type = v.type; proj->val.i = i++; ZDA_PUSH(&proc->arena, &start->val.tuple, v); scope_bind(&proc->scope, idbuf[j].name, proj, idbuf[j].pos, proc); @@ -498,7 +532,7 @@ void parse_unit(Lexer *l) { void node_print(Node *n, Proc *p) { if (n->walked) return; - if (n->type == N_START) { + if (n->op == N_START) { Str s = S(""); int c = n->val.tuple.len; Value *v = n->val.tuple.data; @@ -507,8 +541,8 @@ void node_print(Node *n, Proc *p) { str_cat(&s, type_desc(&v[i].type, &p->arena), &p->arena); } printf("\t%d [label=\"start(%.*s)\"]", n->id, (int)s.n, s.s); - } else if (n->type == N_LIT) { - switch (n->val.type.t) { + } else if (n->op == N_LIT) { + switch (n->type.t) { case T_INT: printf("\t%d [label=\"%ld\"]", n->id, n->val.i); break; @@ -516,7 +550,7 @@ void node_print(Node *n, Proc *p) { printf("\t%d [label=\"%s\"]", n->id, n->val.i ? "true" : "false"); break; case T_NONE: - if (n->val.type.lvl == T_XCTRL) { + if (n->type.lvl == T_XCTRL) { printf("\t%d [label=\"~ctrl\"]", n->id); break; } @@ -525,17 +559,17 @@ void node_print(Node *n, Proc *p) { printf("\t%d [label=\"literal %d\"]", n->id, n->id); break; } - } else if (n->type == N_PROJ) { + } else if (n->op == N_PROJ) { Str d = type_desc(&n->in.data[0]->val.tuple.data[n->val.i].type, &p->arena); printf("\t%d [label=\"%.*s(%ld)\", shape=record]", n->id, (int)d.n, d.s, n->val.i); } else { - printf("\t%d [label=\"%s\", shape=record]", n->id, node_type_name(n->type)); + 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->type == N_LIT) { + if (o->op == N_LIT) { printf("\t%d -> %d [style=dashed]\n", n->id, o->id); } else { int j; @@ -1,9 +1,17 @@ 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 */ - return a + b + if a < b { + return 237 + a + 812734 + b + 81753 + 2389 + } else { + return 1 + a + 7 + 123897 + } } |