factor out node stuff into ir.c & ir.h

1 files changed, 8 insertions, 368 deletions

diff --git a/main.c b/main.c
index 95b8422..05c639c 100644
--- a/main.c
+++ b/main.c
@@ -9,89 +9,10 @@
 #include "lex.h"
 #include "arena.h"
 #include "dynarr.h"
+#include "ir.h"
 
 int no_opt = 1;
 
-/* node graph */
-
-typedef enum {
-	N_START,
-	N_RETURN,
-	N_KEEPALIVE,
-	N_LIT,
-	N_OP_ADD, N_OP_SUB, N_OP_MUL, N_OP_DIV,
-	N_OP_AND, N_OP_OR, N_OP_XOR,
-	N_OP_SHL, N_OP_SHR,
-	N_OP_NEG, N_OP_NOT,
-	N_VALUE
-} NodeType;
-
-const char *node_type_name[] = {
-	"start",
-	"return",
-	"keepalive",
-	"literal",
-	"add", "sub", "mul", "div",
-	"and", "or", "xor",
-	"lshift", "rshift",
-	"neg", "not",
-	"value"
-};
-
-typedef enum {
-	T_BOT,
-	T_TOP,
-	T_CONST,
-	T_INT
-} Type;
-
-typedef struct {
-	Type type;
-	union {
-		int64_t i;
-		uint64_t u;
-	};
-} Value;
-
-typedef struct Node {
-	union {
-		struct Node *prev_free;
-		struct {
-			int id, refs;
-			int walked;
-			NodeType type;
-			LexSpan src_pos;
-			DYNARR(struct Node *) in, out;
-			Value val;
-		};
-	};
-} Node;
-
-typedef struct NameBinding {
-	struct NameBinding *prev;
-	LexSpan src_pos;
-	Str name;
-	Node *node;
-} NameBinding;
-
-typedef struct ScopeFrame {
-	struct ScopeFrame *prev;
-	NameBinding *latest;
-} ScopeFrame;
-
-typedef struct {
-	ScopeFrame *tail, *free_scope;
-	NameBinding *free_bind;
-} Scope;
-
-typedef struct {
-	Arena arena;
-	Str name;
-	Node *start, *stop, *keepalive;
-	Node *free_list;
-	Scope scope;
-} Proc;
-
 typedef struct {
 	DYNARR(Proc) procs;
 } Unit;
@@ -100,111 +21,18 @@ void unit_init(Unit *u) {
 	(void)u;
 }
 
-void unit_fini(Unit *u) {
-	free(u->procs.data);
-}
-
-void node_kill(Node *n, Proc *p);
-
-void node_die(Node *n, Proc *p) {
-	/*n->prev_free = p->free_list;
-	p->free_list = n;*/
-}
-
-void node_del_out(Node *n, Node *p) {
-	for (int i = 0; i < n->out.len; i++) {
-		if (n->out.data[i] == p) {
-			p->refs--;
-			if (i + 1 < n->out.len) {
-				memmove(&n->out.data[i], &n->out.data[i + 1], sizeof(Node*) * (n->out.len - i - 1));
-			}
-			n->out.len--;
-			i--;
-		}
-	}
-}
-
-void node_del_in(Node *n, Node *p) {
-	for (int i = 0; i < n->in.len; i++) {
-		if (n->in.data[i] == p) {
-			p->refs--;
-			if (i + 1 < n->in.len) {
-				memmove(&n->in.data[i], &n->in.data[i + 1], sizeof(Node*) * (n->in.len - i - 1));
-			}
-			n->in.len--;
-			i--;
-		}
-	}
-}
-
-void node_kill(Node *n, Proc *p) {
-	for (int i = 0; i < n->in.len; i++) {
-		node_del_out(n->in.data[i], n);
-		n->in.data[i]->refs--;
-		if (n->in.data[i]->out.len < 1) node_kill(n->in.data[i], p);
-	}
-	for (int i = 0; i < n->out.len; i++) {
-		node_del_in(n->out.data[i], n);
-		n->out.data[i]->refs--;
-		if (n->out.data[i]->refs < 1) node_die(n->out.data[i], p);
-	}
-	n->in.len = 0;
-	n->out.len = 0;
-	node_die(n, p);
-}
-
-void node_add(Proc *p, Node *src, Node *dest) {
-	ZDA_PUSH(&src->out, dest, &p->arena);
-	ZDA_PUSH(&dest->in, src, &p->arena);
-	src->refs++;
-	dest->refs++;
-	if (dest->src_pos.n == 0) dest->src_pos = src->src_pos;
-}
-
-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->refs < 1) node_die(src, p);
-	else 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;
-}
-
-Node *node_new(Proc *p, NodeType t, ...) {
-	Node *node = node_new_empty(p, t);
-	va_list ap;
-	va_start(ap, t);
-	for (;;) {
-		Node *n = va_arg(ap, Node *);
-		if (!n) break;
-		node_add(p, n, node);
+void unit_free(Unit *u) {
+	for (int i = 0; i < u->procs.len; i++) {
+		proc_free(&u->procs.data[i]);
 	}
-	va_end(ap);
-	return node;
+	free(u->procs.data);
 }
 
-#define node_new(...) node_new(__VA_ARGS__, NULL)
-
 void node_print(Node *n) {
 	if (n->type == N_LIT) {
 		printf("\t%d [label=\"%ld\"]\n", n->id, n->val.i);
 	} else {
-		printf("\t%d [label=\"%s\", shape=record]\n", n->id, node_type_name[n->type]);
+		printf("\t%d [label=\"%s\", shape=record]\n", n->id, node_type_name(n->type));
 	}
 	if (n->walked) {
 		return;
@@ -244,191 +72,6 @@ void unit_print(Unit *u) {
 	puts("}");
 }
 
-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 && t->val.type == v.type && t->val.i == v.i) {
-			fprintf(stderr, "deduplicated a node\n");
-			return t;
-		}
-	}
-	return NULL;
-}
-
-Node *node_new_lit_i64(Proc *p, int64_t i) {
-	Value v = (Value) { T_INT, { .i = i } };
-	Node *t = node_dedup_lit(p, v);
-	if (t) return t;
-	Node *n = node_new(p, N_LIT, p->start);
-	n->val = v;
-	return n;
-}
-
-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 };
-	for (unsigned i = 0; i < sizeof ops / sizeof *ops; i++) {
-		if (ops[i] == t) return 1;
-	}
-	return 0;
-}
-
-Value node_compute(Node *n, Lexer *l) {
-	Type lit_type = T_BOT;
-	Node **in = n->in.data;
-	for (int i = 0; i < n->in.len; i++) {
-		Node *p = in[i];
-		if (p->type != N_LIT) break;
-		if (p->val.type != lit_type) {
-			if (lit_type == T_BOT) {
-				lit_type = p->val.type;
-			} else {
-				lit_type = T_BOT;
-				break;
-			}
-		}
-	}
-	if (lit_type == T_INT) {
-		Value v = { .type = lit_type };
-		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_DIV:
-			       if (in[1]->val.i == 0) {
-				       lex_error_at(l, in[1]->src_pos, LE_ERROR, S("divisor always evaluates to zero"));
-			       }
-			       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_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;
-		default: return n->val;
-		}
-		return v;
-	}
-	return n->val;
-}
-
-/* needs lexer for error reporting */
-Node *node_peephole(Node *n, Proc *p, Lexer *l) {
-	if (no_opt) return n;
-
-	if (n->type != N_LIT) {
-		Value v = node_compute(n, l);
-		if (v.type > T_CONST) {
-			node_kill(n, p);
-			Node *t = node_dedup_lit(p, v);
-			if (t) return t;
-			Node *r = node_new(p, N_LIT, p->start);
-			r->val = v;
-			r->src_pos = n->src_pos;
-			return r;
-		}
-	}
-
-	Node **in = n->in.data;
-	/* TODO: figure out to do peepholes recursively, without fucking up the graph or having to clone everything */
-	if (node_op_communative(n->type)) {
-		/* transformations to help encourage constant folding */
-		/* the overall trend is to move them rightwards */
-		if (in[0]->type == N_LIT
-				&& in[1]->type == n->type
-				&& in[1]->in.data[0]->type != N_LIT
-				&& in[1]->in.data[1]->type == N_LIT) {
-			/* op(lit, op(X, lit)) -> op(X, op(lit, lit)) */
-			Node *tmp = in[1]->in.data[0];
-			in[1]->in.data[0] = in[0];
-			in[0] = tmp;
-			/* TODO: ...would it break anything at all to just do in[1] = node_peephole(in[1], p, l)?
-			 * probably not, right? */
-		} else if (in[0]->type == n->type
-				&& in[0]->in.data[0]->type != N_LIT
-				&& in[0]->in.data[1]->type == N_LIT
-				&& in[1]->type != N_LIT) {
-			/* op(op(X, lit), Y) -> op(op(X, Y), lit) */
-			Node *tmp = in[0]->in.data[1];
-			in[0]->in.data[1] = in[1];
-			in[1] = tmp;
-		} else if (in[0]->type == N_LIT && in[1]->type != N_LIT) {
-			/* op(lit, X) -> op(X, lit) */
-			Node *tmp = in[0];
-			in[0] = in[1];
-			in[1] = tmp;
-		}
-	}
-
-	return n;
-}
-
-/* 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;
-}
-
 /* parsing */
 
 Node *parse_expr(Lexer *l, Proc *p);
@@ -491,11 +134,8 @@ void parse_stmt(Lexer *l, Proc *p) {
 Proc *parse_proc(Lexer *l, Unit *u) {
 	DA_FIT(&u->procs, u->procs.len + 1);
 	Proc *proc = &u->procs.data[u->procs.len++];
-	memset(proc, 0, sizeof(Proc));
-	proc->start = node_new_empty(proc, N_START);
-	proc->keepalive = node_new_empty(proc, N_KEEPALIVE);
 	lex_expect(l, TM_IDENT);
-	proc->name = l->ident;
+	proc_init(proc, l->ident);
 	lex_expect(l, TM_LBRACE);
 	lex_next(l);
 	scope_push(&proc->scope, proc);
@@ -600,7 +240,7 @@ void parse_unit(Lexer *l) {
 		parse_toplevel(l, &u);
 	}
 	unit_print(&u);
-	unit_fini(&u);
+	unit_free(&u);
 }
 
 int main(int argc, const char **argv) {