improve register allocation

+ Still linear, but orders regs by some kind of priority
+ Use all registers available, not just callee-save

1 files changed, 65 insertions, 10 deletions

diff --git a/src/ejit.c b/src/ejit.c
index 34526b8..b0a0d51 100644
--- a/src/ejit.c
+++ b/src/ejit.c
@@ -6,20 +6,48 @@
 
 #include "common.h"
 
-static size_t max(size_t a, size_t b)
+static struct gpr_stat zero_gpr_stat()
 {
-	return a > b ? a : b;
+	return (struct gpr_stat){
+		.r = EJIT_GPR(0),
+		.prio = 0,
+		.rno = 0
+	};
+}
+
+static struct fpr_stat zero_fpr_stat()
+{
+	return (struct fpr_stat){
+		.f = EJIT_FPR(0),
+		.prio = 0,
+		.fno = 0
+	};
 }
 
 static void update_gpr(struct ejit_func *f, struct ejit_gpr r0)
 {
-	/* +1 because we want to look at count, not index */
-	f->gpr = max(f->gpr, r0.r + 1);
+	while (gpr_stats_len(&f->gpr) <= r0.r)
+		gpr_stats_append(&f->gpr, zero_gpr_stat());
+
+	struct gpr_stat *gpr = gpr_stats_at(&f->gpr, r0.r);
+	/* presumably first time we see this gpr */
+	/** @todo are branches faster than a memory write? */
+	if (gpr->prio == 0)
+		gpr->r = r0;
+
+	gpr->prio += f->prio;
 }
 
 static void update_fpr(struct ejit_func *f, struct ejit_fpr f0)
 {
-	f->fpr = max(f->fpr, f0.f + 1);
+	while (fpr_stats_len(&f->fpr) <= f0.f)
+		fpr_stats_append(&f->fpr, zero_fpr_stat());
+
+	struct fpr_stat *fpr = fpr_stats_at(&f->fpr, f0.f);
+	if (fpr->prio == 0)
+		fpr->f = f0;
+
+	fpr->prio += f->prio;
 }
 
 static void update_64(struct ejit_func *f, int64_t o)
@@ -288,11 +316,12 @@ struct ejit_func *ejit_create_func(enum ejit_type rtype, size_t argc,
 
 	f->insns = insns_create();
 	f->labels = labels_create();
+	f->gpr = gpr_stats_create();
+	f->fpr = fpr_stats_create();
 	f->arena = NULL;
 	f->direct_call = NULL;
 	f->size = 0;
-	f->gpr = 0;
-	f->fpr = 0;
+	f->prio = 1;
 	f->use_64 = false;
 
 	for (size_t i = 0; i < argc; ++i) {
@@ -318,7 +347,11 @@ struct ejit_func *ejit_create_func(enum ejit_type rtype, size_t argc,
 
 void ejit_compile_func(struct ejit_func *f)
 {
-	ejit_select_compile_func(f, f->gpr, f->fpr, f->use_64, true);
+	ejit_select_compile_func(f,
+			gpr_stats_len(&f->gpr),
+			fpr_stats_len(&f->fpr),
+			f->use_64,
+			true);
 }
 
 void ejit_select_compile_func(struct ejit_func *f, size_t gpr, size_t fpr,
@@ -328,8 +361,8 @@ void ejit_select_compile_func(struct ejit_func *f, size_t gpr, size_t fpr,
 	emit_insn_o(f, END);
 
 	/* user can get some sanity checking done by passing these explicitly */
-	assert(gpr >= f->gpr);
-	assert(fpr >= f->fpr);
+	assert(gpr >= gpr_stats_len(&f->gpr));
+	assert(fpr >= fpr_stats_len(&f->fpr));
 	assert(!f->use_64 || (use_64 == f->use_64));
 
 	/* try to jit compile if possible */
@@ -364,6 +397,8 @@ void ejit_destroy_func(struct ejit_func *f)
 
 	insns_destroy(&f->insns);
 	labels_destroy(&f->labels);
+	gpr_stats_destroy(&f->gpr);
+	fpr_stats_destroy(&f->fpr);
 	free(f);
 }
 
@@ -1570,3 +1605,23 @@ double ejit_run_func_f(struct ejit_func *f, size_t argc,
 	destroy_interp_state(state);
 	return r;
 }
+
+size_t ejit_get_prio(struct ejit_func *s)
+{
+	return s->prio;
+}
+
+void ejit_set_prio(struct ejit_func *s, size_t prio)
+{
+	s->prio = prio;
+}
+
+void ejit_inc_prio(struct ejit_func *s, size_t prio)
+{
+	s->prio += prio;
+}
+
+void ejit_dec_prio(struct ejit_func *s, size_t prio)
+{
+	s->prio -= prio;
+}