shift operators, deduplicate integer constant nodes

1 files changed, 33 insertions, 6 deletions

diff --git a/main.c b/main.c
index 8c6b837..95b8422 100644
--- a/main.c
+++ b/main.c
@@ -10,7 +10,7 @@
 #include "arena.h"
 #include "dynarr.h"
 
-int no_opt = 0;
+int no_opt = 1;
 
 /* node graph */
 
@@ -21,6 +21,7 @@ typedef enum {
 	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;
@@ -32,6 +33,7 @@ const char *node_type_name[] = {
 	"literal",
 	"add", "sub", "mul", "div",
 	"and", "or", "xor",
+	"lshift", "rshift",
 	"neg", "not",
 	"value"
 };
@@ -47,6 +49,7 @@ typedef struct {
 	Type type;
 	union {
 		int64_t i;
+		uint64_t u;
 	};
 } Value;
 
@@ -104,8 +107,8 @@ void unit_fini(Unit *u) {
 void node_kill(Node *n, Proc *p);
 
 void node_die(Node *n, Proc *p) {
-	n->prev_free = p->free_list;
-	p->free_list = n;
+	/*n->prev_free = p->free_list;
+	p->free_list = n;*/
 }
 
 void node_del_out(Node *n, Node *p) {
@@ -241,9 +244,26 @@ 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 = (Value) { T_INT, { .i = i } };
+	n->val = v;
 	return n;
 }
 
@@ -287,6 +307,8 @@ Value node_compute(Node *n, Lexer *l) {
 		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;
@@ -301,10 +323,12 @@ Node *node_peephole(Node *n, Proc *p, Lexer *l) {
 	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;
-			node_kill(n, p);
 			return r;
 		}
 	}
@@ -339,6 +363,7 @@ Node *node_peephole(Node *n, Proc *p, Lexer *l) {
 			in[1] = tmp;
 		}
 	}
+
 	return n;
 }
 
@@ -532,7 +557,7 @@ Node *parse_term(Lexer *l, Proc *p) {
 Node *parse_expr(Lexer *l, Proc *p) {
 	LexSpan pos = l->pos;
 	Node *lhs = parse_term(l, p);
-	if (TMASK(l->tok) & (TM_PLUS | TM_MINUS | TM_ASTERISK | TM_SLASH | TM_NOT | TM_AND | TM_XOR | TM_OR)) {
+	if (TMASK(l->tok) & (TM_PLUS | TM_MINUS | TM_ASTERISK | TM_SLASH | TM_NOT | TM_AND | TM_XOR | TM_OR | TM_SHL | TM_SHR)) {
 		Token t = l->tok;
 		lex_next(l);
 		Node *rhs = parse_expr(l, p);
@@ -546,6 +571,8 @@ Node *parse_expr(Lexer *l, Proc *p) {
 		case TOK_AND: nt = N_OP_AND; break;
 		case TOK_OR: nt = N_OP_OR; break;
 		case TOK_XOR: nt = N_OP_XOR; break;
+		case TOK_SHL: nt = N_OP_SHL; break;
+		case TOK_SHR: nt = N_OP_SHR; break;
 		default: break;
 		}
 		lhs = node_new(p, nt, lhs, rhs);