path: root/peephole.c

#include <stdarg.h>
#include <assert.h>
#include <stdio.h>

#include "peephole.h"
#include "strio.h"

extern int no_opt;

#define NM_COMMUTATIVE (NM_OP_ADD | NM_OP_MUL | NM_OP_AND | NM_OP_XOR | NM_OP_OR | NM_CMP_EQL | NM_CMP_NEQ)
#define NM_ASSOCIATIVE (NM_OP_ADD | NM_OP_MUL | NM_OP_AND | NM_OP_XOR | NM_OP_OR)
#define NM_COMPARISON (NM_CMP_EQL | NM_CMP_NEQ | NM_CMP_LES | NM_CMP_GTR | NM_CMP_LTE | NM_CMP_GTE)
#define NM_IDEMPOTENT (NM_OP_AND | NM_OP_OR)

#define C(a, b) type_base_eql(&(a)->type, &(b)->type)
#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)

/* 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 },
		{ N_CMP_LES, N_CMP_EQL },
		{ N_CMP_GTR, N_CMP_EQL },
	};
	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 (u32 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;
}

#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;
}

/* TODO:
 *
 * Implement something like
 * int node_is(Node *a, Relation r, Node *b);
 * so you can do node_is(a, LES, b).
 *
 * In theory, there are six different relations nodes can have:
 * - a = b
 * - a <> b
 * - a < b
 * - a > b
 * - a <= b
 * - a >= b
 *
 * To identify any of them is necessarily kinda recursive --- we need to walk
 * the tree of known relations.  First check to see if `a < b` is stored as an
 * axiomatically true thing in the knowledge table -- if not, we need to scan
 * through their relations, looking to see if there's any value x where a < x
 * < b --- or a < x < y < b, or a < x < y < z < b, and so on.
 *
 * Because there are six node-relations, they can be packed into a single byte.
 * They can also all be reordered (a < b = b > a), so we don't need to store a
 * different flags byte for each node --- the order of which node should be on
 * what side of the comparison is determined by their ID, low to high.
 *
 * The simplest way to store them is a 2d array, NxN where N is the number of
 * nodes.  But this quickly gets expensive:  with 1024 nodes we're already up
 * to a megabyte of space.  So instead it's probably gonna be a hash table or
 * trie, with both 32-bit node IDs mixed into one 64-bit key.  One problem,
 * though:  how do we efficiently _scan_ that space, to find those recursive
 * values?  We need to track, for each node, a list of other nodes it has
 * known-relations with.
 */

/* 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);

/* TODO: separate out equivalence as in complete identity vs. just same value */
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;
	for (u32 i = 1; i < a->in.len; i++) {
		if (!node_equiv(IN(a, i), IN(b, i))) 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) {
	if (node_cmp_incompat(a->op, b->op) && node_equiv_input(a, b)) return 1;
	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 (((NMASK(a->op) | NMASK(b->op)) & NM_COMMUTATIVE)
			&& ((node_equiv(CDR(a), CAR(b)) && node_equiv(CAR(a), CDR(b)))
			|| (node_equiv(CAR(a), CDR(b)) && node_equiv(CDR(a), CAR(b))))) {
		/* assuming input count is 2 */
		fprintf(stderr, "equiv\n");
		return 1;
	}
	for (u32 i = 1; i < a->in.len; i++) {
		if (!node_equiv(IN(a, i), IN(b, i))) return 0;
	}
	return 1;
}

Node *node_new_zero(Graph *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, Graph *p, Lexer *l) {
	type_check(n, l);

	/* stuff that needs to happen even if optimizations are disabled */

	/*switch (n->op) {
	case N_PHI:
		for (int i = 0; i < n->in.len; i++) {
			if (IN(n,i) && IN(n,i)->op == N_UNINIT) {
				Node *r = node_new(p, N_UNINIT, p->start);
				r->type = n->type;
				return r;
			}
		}
	default:
		break;
	}*/

	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 (u32 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 (u32 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 */

	if (NMASK(n->op) & NM_COMMUTATIVE) {
		/* 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));
		}

		/* op(phi(C, A, B), phi(C, B, A)) -> op(A, B) */
		if (T(CAR(n), N_PHI) && T(CDR(n), N_PHI) && CTRL(CAR(n)) == CTRL(CDR(n))
				&& (node_equiv(CADR(n), CDAR(n)) && node_equiv(CAAR(n), CDDR(n)))) {
			return OP(CAAR(n), CADR(n));
		}
	}

	if (NMASK(n->op) & NM_ASSOCIATIVE) {
		/* 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(Y,X), X) -> op(op(X, X), Y) */
		if (T(CAR(n), n->op)) {
			int leq = node_equiv(CAAR(n), CDR(n));
			int req = node_equiv(CADR(n), CDR(n));
			if (leq && !req) return OP(OP(CDR(n), CDR(n)), CADR(n));
			if (req && !leq) return OP(OP(CDR(n), CDR(n)), CAAR(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));
		}
	}

	if (NMASK(n->op) & NM_IDEMPOTENT) {
		/* op(X, X) -> X */
		if (node_equiv(CAR(n), CDR(n))) return CAR(n);

		/* op(op(X, Y), X | Y) -> op(X, Y) */
		if (T(CAR(n), n->op) && (node_equiv(CDR(n), CAAR(n)) || node_equiv(CDR(n), CADR(n)))) {
			return CAR(n);
		}

		/* op(op(X, Y), op(X, Y)) -> op(X, Y) */
		if (T(CAR(n), n->op) && T(CDR(n), n->op) && node_equiv_input(CAR(n), CDR(n))) {
			return CAR(n);
		}

		/* op(phi(C, A, B), op(A, B)) -> op(A, B) */
		if (T(CAR(n), N_PHI) && T(CDR(n), n->op) && node_equiv_input(CAR(n), CDR(n))) {
			return CDR(n);
		}
		if (T(CDR(n), N_PHI) && T(CAR(n), n->op) && node_equiv_input(CAR(n), CDR(n))) {
			return CAR(n);
		}
	}

	/* optimize based on situations where the input is partly known (e.g.
	 * one constant input and one not, or identical inputs) */

	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"));
		}
		{
			// TODO: this only holds true for _unsigned_ integers
			/*
			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 (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 (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);
		if (((T(CAR(n), N_CMP_LTE) && T(CDR(n), N_CMP_GTE)) || (T(CAR(n), N_CMP_GTE) && T(CDR(n), N_CMP_LTE)))
				&& node_equiv_input(CAR(n), CDR(n))) {
			return NODE(N_CMP_EQL, CAAR(n), CADR(n));
		}
		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) {
			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 (u32 i = 0; i < n->in.len; i++) {
			if (IN(n, i)->type.lvl != T_XCTRL) live_in++;
		}
		if (live_in == 1) {
			for (u32 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;

	case N_OP_SHL:
	case N_OP_SHR:
		/* a (<< | >>) 0 -> a */
		/* 0 (<< | >>) a -> 0 */
		if (node_eql_i64(CDR(n), 0) || node_eql_i64(CAR(n), 0)) return CAR(n);
		break;

	default:
		break;
	}

	if (NMASK(n->op) & NM_COMPARISON) {
		/* 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 ((NMASK(CAR(n)->op) & NM_ASSOCIATIVE) && 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, Graph *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;
}