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

---
 peephole.c | 559 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 559 insertions(+)
 create mode 100644 peephole.c

(limited to 'peephole.c')

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 <stdarg.h>
+#include <assert.h>
+
+#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 <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;
+}
-- 
cgit v1.2.3