path: root/ir.c

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

#include "ir.h"
#include "strio.h"

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)

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

int type_check(Node *n) {
	switch (n->type) {
	case N_PHI:
		n->val.type = (Type) { .lvl = T_TOP, .t = IN(n, 1)->val.type.t };
		for (int i = 2; i < n->in.len; i++) {
			if (!type_base_eql(&IN(n, i)->val.type, &n->val.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;
	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;
	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);
	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;
	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;
	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); */
	default:
		return 1;
	}
}

/* nodes */

const char *node_type_name(NodeType t) {
	const char *names[] = {
		"N/A",
		"start", "if-else", "region", "phi", "stop",
		"projection",
		"return",
		"keepalive",
		"literal",
		"add", "sub", "mul", "div",
		"and", "or", "xor",
		"lshift", "rshift",
		"neg", "not",
		"equal",
		"not-equal",
		"less",
		"greater",
		"less-or-equal",
		"greater-or-equal",
		"value"
	};
	return names[t];
}

void node_die(Node *n, Proc *p) {
	assert(n->refs == 0);
	n->prev_free = p->free_list;
	p->free_list = n;
}

void node_del_out(Node *n, Node *p) {
	for (int i = n->out.len - 1; i >= 0; i--) {
		if (n->out.data[i] == p) {
			if (p) p->refs--;
			n->out.len--;
			if (i < n->out.len) {
				n->out.data[i] = n->out.data[n->out.len];
			}
			break;
		}
	}
}

void node_del_in(Node *n, Node *p) {
	for (int i = n->in.len - 1; i >= 0; i--) {
		if (n->in.data[i] == p) {
			if (p) p->refs--;
			n->in.len--;
			if (i < n->in.len) {
				memmove(&n->in.data[i], &n->in.data[i + 1], sizeof(Node*) * (n->in.len - i));
			}
			break;
		}
	}
}

void node_kill(Node *n, Proc *p) {
	if (p->ctrl == n) {
		/* probably this is fine */
		p->ctrl = CTRL(n);
	}
	while (n->refs > 0 && n->in.len > 0) node_remove(p, n->in.data[0], n);
	while (n->refs > 0 && n->out.len > 0) node_remove(p, n, n->out.data[0]);
	assert(n->refs == 0);
}

void node_add_out(Proc *p, Node *a, Node *b) {
	ZDA_PUSH(&p->arena, &a->out, b);
	if (b) b->refs++;
}

void node_add_in(Proc *p, Node *a, Node *b) {
	ZDA_PUSH(&p->arena, &a->in, b);
	if (b) b->refs++;
}

void node_add(Proc *p, Node *src, Node *dest) {
	node_add_in(p, dest, src);
	if (!src) return;
	node_add_out(p, src, dest);
	if (dest->src_pos.n == 0) dest->src_pos = src->src_pos;
	else if (src->src_pos.n != 0) {
		int lo = dest->src_pos.ofs < src->src_pos.ofs ? dest->src_pos.ofs : src->src_pos.ofs;
		int hi = dest->src_pos.ofs + dest->src_pos.n > src->src_pos.ofs + src->src_pos.n ? dest->src_pos.ofs + dest->src_pos.n : src->src_pos.ofs + src->src_pos.n;
		dest->src_pos = (LexSpan) { lo, hi - lo };
	}
}

void node_remove(Proc *p, Node *src, Node *dest) {
	node_del_in(dest, src);
	if (dest->refs < 1) node_die(dest, p);
	if (src) {
		node_del_out(src, dest);
		if (src->out.len < 1) node_kill(src, p);
	}
}

static int global_node_count = 0;

Node *node_new_empty(Proc *p, NodeType t) {
	Node *n;
	if (p->free_list) {
		n = p->free_list;
		p->free_list = n->prev_free;
		memset(n, 0, sizeof(Node));
	} else {
		n = new(&p->arena, Node);
	}
	n->type = t;
	n->id = global_node_count++;
	return n;
}

int type_check(Node *);
Node *node_newv(Proc *p, NodeType t, Node *ctrl, ...) {
	Node *node = node_new_empty(p, t);
	va_list ap;
	va_start(ap, ctrl);
	node_add(p, ctrl, node);
	for (;;) {
		Node *n = va_arg(ap, Node *);
		if (!n) break;
		node_add(p, n, node);
	}
	va_end(ap);
	return node;
}

Node *node_dedup_lit(Proc *p, Value v) {
	/* TODO: this is probably real inefficient for large procedure graphs,
	 * but does it matter? how many nodes are direct children of the start node?
	 * 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) {
			return t;
		}
	}
	return NULL;
}

Node *node_new_lit(Proc *p, Value v) {
	Node *t = node_dedup_lit(p, v);
	if (t) return t;
	Node *n = node_new(p, N_LIT, NULL, p->start);
	n->val = v;
	return n;
}

Node *node_new_lit_i64(Proc *p, int64_t i) {
	return node_new_lit(p, (Value) { { .lvl = T_CONST, .t = T_INT }, { .i = i } });
}

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) {
	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;
}

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

/* 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;
	}
	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->val.type.lvl != T_CONST) {
			lit_type.lvl = T_BOT;
			break;
		}
		if (!type_eql(&p->val.type, &lit_type)) {
			if (lit_type.lvl == T_BOT) {
				lit_type = p->val.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->type) {
		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->type) {
		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->type, __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;
}

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->val.type.t == b->val.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->type != b->type) 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 ((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;
}
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->type) || node_op_communative(b->type))
			&& 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->val.type.t,
		},
		.i = 0
	};
	Node *r = node_new_lit(p, v);
	return r;
}

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

/* 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->type != 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->type, 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_eql(&(a)->val.type, &(b)->val.type)
	if (node_op_communative(n->type)) {
		/* 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));
		}

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

		/* 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)
				&& 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)
				&& !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)
				&& 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)->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)

	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;
	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) {
			/* 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)->val.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)->val.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)->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);
		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))) {
			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))) {
			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);
		}
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_PROJ:
		if (T(CTRL(n), N_IF_ELSE) && CTRL(n)->val.type.t == T_TUPLE) {
			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 (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);
		break;

	default:
		break;
	}

	if (node_op_comparison(n->type)) {
		/* 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 (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));
		}
		/* 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 (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));
			}
			/* 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));
			}
		}
		/* 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 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) {
	memset(proc, 0, sizeof(Proc));
	proc->start = node_new(proc, N_START, NULL);
	proc->start->val.type = (Type) {
		.lvl = T_BOT,
		.t = T_TUPLE,
		.next = NULL
	};
	proc->stop = node_new(proc, N_STOP, NULL);
	proc->ctrl = proc->start;
	proc->keepalive = node_new(proc, N_KEEPALIVE, NULL);
	proc->name = name;
}

void proc_free(Proc *proc) {
	arena_free(&proc->arena);
}

/* scope */

NameBinding *scope_find(Scope *scope, Str name) {
	for (ScopeFrame *f = scope->tail; f; f = f->prev) {
		for (NameBinding *b = f->latest; b; b = b->prev) {
			if (str_eql(b->name, name)) {
				return b;
			}
		}
	}
	return NULL;
}

ScopeFrame *scope_push(Scope *scope, Proc *proc) {
	ScopeFrame *f;
	if (scope->free_scope) {
		f = scope->free_scope;
		*f = (ScopeFrame) { 0 };
		scope->free_scope = f->prev;
	} else {
		f = new(&proc->arena, ScopeFrame);
	}
	f->prev = scope->tail;
	scope->tail = f;
	return f;
}

ScopeFrame *scope_pop(Scope *scope, Proc *proc) {
	ScopeFrame *f = scope->tail;
	scope->tail = f->prev;
	f->prev = scope->free_scope;
	scope->free_scope = f;
	for (NameBinding *b = f->latest; b; ) {
		NameBinding *p = b->prev;
		b->prev = scope->free_bind;
		scope->free_bind = b;
		node_remove(proc, b->node, proc->keepalive);
		b = p;
	}
	return scope->tail;
}

/* returns previous value */
NameBinding *scope_bind(Scope *scope, Str name, Node *value, LexSpan pos, Proc *proc) {
	NameBinding *prev = scope_find(scope, name);
	NameBinding *b;
	if (scope->free_bind) {
		b = scope->free_bind;
		*b = (NameBinding) { 0 };
		scope->free_bind = b->prev;
	} else {
		b = new(&proc->arena, NameBinding);
	}
	b->name = name;
	b->prev = scope->tail->latest;
	scope->tail->latest = b;
	b->node = value;
	b->src_pos = pos;
	node_add(proc, value, proc->keepalive);
	return prev;
}

NameBinding *scope_update(NameBinding *b, Node *to, Proc *proc) {
	Node *n = b->node;
	node_add(proc, to, proc->keepalive);
	b->node = to;
	node_remove(proc, n, proc->keepalive);
	return b;
}

/* adds to keepalive so these aren't invalidated */
void scope_collect(Scope *scope, Proc *proc, ScopeNameList *nl, Arena *arena) {
	for (ScopeFrame *f = scope->tail; f; f = f->prev) {
		for (NameBinding *b = f->latest; b; b = b->prev) {
			node_add(proc, b->node, proc->keepalive);
			ZDA_PUSH(arena, nl, (ScopeName) { b->name, b->node });
		}
	}
}

void scope_uncollect(Scope *scope, Proc *proc, ScopeNameList *nl) {
	for (int i = 0; i < nl->len; i++) {
		node_remove(proc, nl->data[i].node, proc->keepalive);
	}
}