small size optimization on <= 1-node NodeList

4 files changed, 61 insertions, 19 deletions

diff --git a/ir.c b/ir.c
index 88676bc..b15e3a8 100644
--- a/ir.c
+++ b/ir.c
@@ -6,17 +6,41 @@
 
 /* node lists */
 
-void nodelist_push(NodeList *l, Node *p, Arena *a) {
-	ZDA_PUSH(a, l, p);
+void nodelist_fit(NodeList *l, uint32_t sz, Arena *a) {
+	if (l->cap) {
+		if (sz > l->cap) {
+			uint32_t c = l->cap;
+			while (sz > c) c <<= 1;
+			l->data = resize(a, l->data, l->cap, c);
+			l->cap = c;
+		}
+	} else {
+		if (sz > 1) {
+			uint32_t cap = 2;
+			while (cap < sz) cap <<= 1;
+			Node **data = new_arr(a, Node *, cap);
+			data[0] = l->sbo;
+			l->data = data;
+			l->cap = cap;
+		}
+	}
 }
 
-void nodelist_remove(NodeList *l, Node *p) {
-	for (int i = l->len - 1; i >= 0; i--) {
-		if (l->data[i] == p) {
-			if (p) p->refs--;
+void nodelist_push(NodeList *l, Node *n, Arena *a) {
+	nodelist_fit(l, l->len + 1, a);
+	Node **p = nodelist_nth(l, l->len++);
+	if (n) n->refs++;
+	*p = n;
+}
+
+void nodelist_remove(NodeList *l, Node *n) {
+	Node **data = nodelist_data(l);
+	for (unsigned i = 0; i < l->len; i++) {
+		if (data[i] == n) {
+			if (n) n->refs--;
 			l->len--;
 			if (i < l->len) {
-				memmove(&l->data[i], &l->data[i + 1], sizeof(Node*) * (l->len - i));
+				memmove(&data[i], &data[i+1], (l->len - i) * sizeof(Node *));
 			}
 			break;
 		}
@@ -24,12 +48,15 @@ void nodelist_remove(NodeList *l, Node *p) {
 }
 
 void nodelist_remove_unordered(NodeList *l, Node *p) {
-	for (int i = l->len - 1; i >= 0; i--) {
-		if (l->data[i] == p) {
+	Node **data = nodelist_data(l);
+	unsigned i = l->len;
+	while (i) {
+		i--;
+		if (data[i] == p) {
 			if (p) p->refs--;
 			l->len--;
 			if (i < l->len) {
-				l->data[i] = l->data[l->len];
+				data[i] = data[l->len];
 			}
 			break;
 		}
@@ -74,13 +101,13 @@ void node_kill(Node *n, Graph *p) {
 }
 
 void node_add_out(Graph *p, Node *a, Node *b) {
+	assert(b > 0xfffff || !b);
 	nodelist_push(&a->out, b, p->pool->arena);
-	if (b) b->refs++;
 }
 
 void node_add_in(Graph *p, Node *a, Node *b) {
+	assert(b > 0xfffff || !b);
 	nodelist_push(&a->in, b, p->pool->arena);
-	if (b) b->refs++;
 }
 
 void node_set_in(Graph *p, Node *n, int idx, Node *to) {
@@ -93,10 +120,10 @@ void node_set_in(Graph *p, Node *n, int idx, Node *to) {
 }
 
 void node_add(Graph *p, Node *src, Node *dest) {
-	if (src) assert(src->op != N_DEAD);
-	if (dest) assert(dest->op != N_DEAD);
+	assert(dest->op != N_DEAD);
 	node_add_in(p, dest, src);
 	if (!src) return;
+	assert(src->op != N_DEAD);
 	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) {
diff --git a/ir.h b/ir.h
index 8b963f7..b5992c8 100644
--- a/ir.h
+++ b/ir.h
@@ -100,7 +100,13 @@ typedef enum {
 
 const char *node_type_name(NodeType t);
 
-typedef DYNARR(struct Node *) NodeList;
+typedef struct {
+	unsigned len, cap;
+	union {
+		struct Node *sbo;
+		struct Node **data;
+	};
+} NodeList;
 
 typedef struct Node {
 	int id, refs;
@@ -122,8 +128,9 @@ typedef struct Node {
 
 /* convenience macros (lisp-inspired lol) */
 
-#define IN(n, i) ((n)->in.data[i])
-#define OUT(n, i) ((n)->out.data[i])
+#define Ni(nl, i) (*nodelist_nth(&(nl), i))
+#define IN(n, i) Ni(n->in, i)
+#define OUT(n, i) Ni(n->out, i)
 
 #define CTRL(n) IN(n, 0)
 #define CAR(n) IN(n, 1)
@@ -187,4 +194,12 @@ int node_maybe_uninit(Node *n);
 
 #define node_new(...) node_newv(__VA_ARGS__, NULL)
 
+static inline Node **nodelist_data(NodeList *l) {
+	return l->cap ? l->data : &l->sbo;
+}
+
+static inline Node **nodelist_nth(NodeList *l, uint32_t i) {
+	return nodelist_data(l) + i;
+}
+
 #endif
diff --git a/main.c b/main.c
index 1f1241d..9f807c1 100644
--- a/main.c
+++ b/main.c
@@ -679,6 +679,6 @@ int main(int argc, const char **argv) {
 	parse_unit(&l, &u);
 	unit_print(&u);
 	lex_free(&l);
-	fprintf(stderr, "%zu\n", sizeof(Node));
+	fprintf(stderr, "node size = %zu\n", sizeof(Node));
 	return 0;
 }
diff --git a/test.lang b/test.lang
index 8a000c7..e57f630 100644
--- a/test.lang
+++ b/test.lang
@@ -4,5 +4,5 @@ func main(a, b i64) i64 {
 		a := b
 		b := t
 	}
-	return a + b + 3
+	return (a + b + 3) xor b
 }