preliminary peephole optimization of if statements

1 files changed, 84 insertions, 49 deletions

diff --git a/ir.c b/ir.c
index dd8b66c..bd3354b 100644
--- a/ir.c
+++ b/ir.c
@@ -11,8 +11,9 @@ extern int no_opt;
 #define IN(n, i) ((n)->in.data[i])
 #define OUT(n, i) ((n)->out.data[i])
 
-#define CAR(n) IN(n, 0)
-#define CDR(n) IN(n, 1)
+#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))
@@ -50,6 +51,11 @@ int value_eql(Value *a, Value *b) {
 
 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");
@@ -140,7 +146,7 @@ void node_die(Node *n, Proc *p) {
 void node_del_out(Node *n, Node *p) {
 	for (int i = n->out.len - 1; i >= 0; i--) {
 		if (n->out.data[i] == p) {
-			p->refs--;
+			if (p) p->refs--;
 			n->out.len--;
 			if (i < n->out.len) {
 				n->out.data[i] = n->out.data[n->out.len];
@@ -153,7 +159,7 @@ void node_del_out(Node *n, Node *p) {
 void node_del_in(Node *n, Node *p) {
 	for (int i = n->in.len - 1; i >= 0; i--) {
 		if (n->in.data[i] == p) {
-			p->refs--;
+			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));
@@ -164,7 +170,6 @@ void node_del_in(Node *n, Node *p) {
 }
 
 void node_kill(Node *n, Proc *p) {
-	assert(n->refs > 0);
 	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);
@@ -172,17 +177,18 @@ void node_kill(Node *n, Proc *p) {
 
 void node_add_out(Proc *p, Node *a, Node *b) {
 	ZDA_PUSH(&p->arena, &a->out, b);
-	b->refs++;
+	if (b) b->refs++;
 }
 
 void node_add_in(Proc *p, Node *a, Node *b) {
 	ZDA_PUSH(&p->arena, &a->in, b);
-	b->refs++;
+	if (b) b->refs++;
 }
 
 void node_add(Proc *p, Node *src, Node *dest) {
-	node_add_out(p, src, 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;
@@ -192,10 +198,12 @@ void node_add(Proc *p, Node *src, Node *dest) {
 }
 
 void node_remove(Proc *p, Node *src, Node *dest) {
-	node_del_out(src, dest);
 	node_del_in(dest, src);
 	if (dest->refs < 1) node_die(dest, p);
-	if (src->out.len < 1) node_kill(src, p);
+	if (src) {
+		node_del_out(src, dest);
+		if (src->out.len < 1) node_kill(src, p);
+	}
 }
 
 static int global_node_count = 0;
@@ -215,10 +223,11 @@ Node *node_new_empty(Proc *p, NodeType t) {
 }
 
 int type_check(Node *);
-Node *node_newv(Proc *p, NodeType t, ...) {
+Node *node_newv(Proc *p, NodeType t, Node *ctrl, ...) {
 	Node *node = node_new_empty(p, t);
 	va_list ap;
-	va_start(ap, t);
+	va_start(ap, ctrl);
+	node_add(p, ctrl, node);
 	for (;;) {
 		Node *n = va_arg(ap, Node *);
 		if (!n) break;
@@ -244,7 +253,7 @@ Node *node_dedup_lit(Proc *p, Value v) {
 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, p->start);
+	Node *n = node_new(p, N_LIT, NULL, p->start);
 	n->val = v;
 	return n;
 }
@@ -323,9 +332,8 @@ static inline int node_cmp_incompat(NodeType a, NodeType b) {
 
 Value node_compute(Node *n, Lexer *l) {
 	Type lit_type = { .lvl = T_BOT };
-	Node **in = n->in.data;
-	for (int i = 0; i < n->in.len; i++) {
-		Node *p = in[i];
+	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;
@@ -346,39 +354,39 @@ Value node_compute(Node *n, Lexer *l) {
 
 	if (lit_type.t == T_INT) {
 		switch (n->type) {
-		case N_OP_NEG: v.i = -in[0]->val.i; break;
-		case N_OP_NOT: v.i = ~in[0]->val.i; break;
-		case N_OP_ADD: v.i = in[0]->val.i + in[1]->val.i; break;
-		case N_OP_SUB: v.i = in[0]->val.i - in[1]->val.i; break;
-		case N_OP_MUL: v.i = in[0]->val.i * in[1]->val.i; break;
+		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 (in[1]->val.i == 0) {
-			       lex_error_at(l, in[1]->src_pos, LE_ERROR, S("divisor always evaluates to zero"));
+		       if (CDR(n)->val.i == 0) {
+			       lex_error_at(l, CDR(n)->src_pos, LE_ERROR, S("divisor always evaluates to zero"));
 		       }
-		       v.i = in[0]->val.i / in[1]->val.i;
+		       v.i = CAR(n)->val.i / CDR(n)->val.i;
 		       break;
-		case N_OP_AND: v.i = in[0]->val.i & in[1]->val.i; break;
-		case N_OP_OR: v.i = in[0]->val.i | in[1]->val.i; break;
-		case N_OP_XOR: v.i = in[0]->val.i ^ in[1]->val.i; break;
-		case N_OP_SHL: v.i = in[0]->val.u << in[1]->val.u; break;
-		case N_OP_SHR: v.i = in[0]->val.u >> in[1]->val.u; break;
-		case N_CMP_EQL: v.type.t = T_BOOL; v.i = in[0]->val.i == in[1]->val.i; break;
-		case N_CMP_NEQ: v.type.t = T_BOOL; v.i = in[0]->val.i != in[1]->val.i; break;
-		case N_CMP_LES: v.type.t = T_BOOL; v.i = in[0]->val.i < in[1]->val.i; break;
-		case N_CMP_GTR: v.type.t = T_BOOL; v.i = in[0]->val.i > in[1]->val.i; break;
-		case N_CMP_LTE: v.type.t = T_BOOL; v.i = in[0]->val.i <= in[1]->val.i; break;
-		case N_CMP_GTE: v.type.t = T_BOOL; v.i = in[0]->val.i >= in[1]->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 = !in[0]->val.i; break;
-		case N_CMP_EQL: v.i = in[0]->val.i == in[1]->val.i; break;
-		case N_CMP_NEQ: v.i = in[0]->val.i != in[1]->val.i; break;
-		case N_OP_AND: v.i = in[0]->val.i && in[1]->val.i; break;
-		case N_OP_OR: v.i = in[0]->val.i || in[1]->val.i; break;
-		case N_OP_XOR: v.i = in[0]->val.i ^ in[1]->val.i; break;
+		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;
@@ -389,7 +397,7 @@ Value node_compute(Node *n, Lexer *l) {
 
 #include <stdio.h>
 
-#define NODE(...) node_peephole(node_new(p, __VA_ARGS__), p, l)
+#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) {
@@ -498,7 +506,7 @@ Node *node_idealize(Node *n, Proc *p, Lexer *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, p->start);
+			Node *r = node_new(p, N_LIT, NULL, p->start);
 			r->val = v;
 			r->src_pos = n->src_pos;
 			return r;
@@ -517,8 +525,8 @@ Node *node_idealize(Node *n, Proc *p, Lexer *l) {
 		}
 	}
 
-	if (n->in.len > 1 && same && !same_ptr) {
-		Node *r = node_new_empty(p, n->type);
+	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);
 		}
@@ -691,6 +699,27 @@ zero_no_effect:	if (node_eql_i64(CAR(n), 0)) return CDR(n);
 	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_PHI:
+		if (same) return CAR(n);
+		if (IN(CTRL(n), 0)->val.type.lvl == T_XCTRL) {
+			return CDR(n);
+		}
+		if (IN(CTRL(n), 1)->val.type.lvl == T_XCTRL) {
+			return CAR(n);
+		}
+		break;
+
 	default:
 		break;
 	}
@@ -747,15 +776,15 @@ 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_empty(proc, N_START);
+	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_empty(proc, N_STOP);
+	proc->stop = node_new(proc, N_STOP, NULL);
 	proc->ctrl = proc->start;
-	proc->keepalive = node_new_empty(proc, N_KEEPALIVE);
+	proc->keepalive = node_new(proc, N_KEEPALIVE, NULL);
 	proc->name = name;
 }
 
@@ -838,8 +867,14 @@ NameBinding *scope_update(Scope *scope, Str name, Node *to, Proc *proc) {
 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_out(proc, b->node, proc->keepalive);
+			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);
+	}
+}