better node_equiv for associative ops; not(cmp(a,b)) -> oppcmp(a,b)

1 files changed, 38 insertions, 12 deletions

diff --git a/ir.c b/ir.c
index e52e0b9..6bd1313 100644
--- a/ir.c
+++ b/ir.c
@@ -98,6 +98,7 @@ int type_check(Node *n) {
 
 const char *node_type_name(NodeType t) {
 	const char *names[] = {
+		"N/A",
 		"start",
 		"projection",
 		"return",
@@ -261,18 +262,17 @@ static inline int node_op_associative(NodeType t) {
 }
 
 /* when applied to the same input, at least one must be true */
-static inline int node_cmp_opposite(NodeType a, NodeType b) {
+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 && pairs[i].r == b) || (pairs[i].l == b && pairs[i].r == a)) {
-			return 1;
-		}
+		if (pairs[i].l == a) return pairs[i].r;
+		if (pairs[i].r == a) return pairs[i].l;
 	}
-	return 0;
+	return N_NONE;
 }
 
 /* when applied to the same input, at least one must be false */
@@ -397,22 +397,23 @@ static inline int node_sub_add_equiv(Node *a, Node *b) {
 	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->type != b->type) return 0;
 	if (a->in.len != b->in.len) return 0;
 	if (!value_eql(&a->val, &b->val)) return 0;
-	for (int i = 0; i < a->in.len; i++) {
-		if (!node_equiv(a->in.data[i], b->in.data[i])) 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 ((T(b, N_OP_ADD) || T(b, N_OP_SUB)) && node_equiv(a, CAR(b)) && !node_eql_i64(CDR(b), 0)) return 1;
+	if ((T(b, N_OP_ADD) || T(b, N_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;
 	return 0;
 }
@@ -420,8 +421,16 @@ 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 inline int node_equiv_input(Node *a, Node *b) {
+static int node_equiv_input(Node *a, Node *b) {
 	if (a->in.len != b->in.len) 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))
+			&& node_equiv(a->in.data[1], b->in.data[0])
+			&& node_equiv(a->in.data[0], b->in.data[1])) {
+		/* assuming input count is 2 */
+		return 1;
+	}
 	for (int i = 0; i < a->in.len; i++) {
 		if (!node_equiv(a->in.data[i], b->in.data[i])) return 0;
 	}
@@ -536,6 +545,11 @@ Node *node_idealize(Node *n, Proc *p, Lexer *l) {
 
 	switch (n->type) {
 	case N_OP_NOT:
+		{
+			NodeType op = node_cmp_opposite(CAR(n)->type);
+			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);
 		break;
@@ -579,9 +593,21 @@ 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 (node_cmp_opposite(CAR(n)->type, CDR(n)->type) && node_equiv_input(CAR(n), CDR(n))) {
+		if (CDR(n)->type == node_cmp_opposite(CAR(n)->type) && 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);
@@ -594,7 +620,7 @@ Node *node_idealize(Node *n, Proc *p, Lexer *l) {
 		break;
 	case N_OP_XOR:
 		if (same) return node_new_zero(p, CAR(n));
-		if (node_cmp_opposite(CAR(n)->type, CDR(n)->type) && node_equiv_input(CAR(n), CDR(n))) {
+		if (CDR(n)->type == node_cmp_opposite(CAR(n)->type) && node_equiv_input(CAR(n), CDR(n))) {
 			return node_new_lit_bool(p, 1);
 		}
 		/* ~bool ^ bool = 1 */