aboutsummaryrefslogtreecommitdiff
path: root/src
diff options
context:
space:
mode:
Diffstat (limited to 'src')
-rw-r--r--src/abi.c14
-rw-r--r--src/asm.c241
-rw-r--r--src/nodes.c8
-rw-r--r--src/regalloc.c337
-rw-r--r--src/ssa.c4
-rw-r--r--src/vec.c13
6 files changed, 439 insertions, 178 deletions
diff --git a/src/abi.c b/src/abi.c
index cb92190..80f34e4 100644
--- a/src/abi.c
+++ b/src/abi.c
@@ -19,7 +19,7 @@ static struct insn rewrite_param(struct insn n)
assert(n.in[1].class == IMM);
int64_t nth_param = n.in[1].v;
assert(nth_param >= 0 && nth_param < 25
- && "stack argument passing not yet supported");
+ && "stack argument passing not yet supported");
return insn_create(MOVE, I27, n.out, nth_ar(nth_param), noclass());
}
@@ -41,9 +41,11 @@ static struct insn rewrite_arg(struct insn n)
assert(nth_arg >= 0 && nth_arg < 25);
if (n.in[0].class == TMP || n.in[0].class == REG)
- return insn_create(MOVE, I27, nth_ar(nth_arg), n.in[0], noclass());
+ return insn_create(MOVE, I27, nth_ar(nth_arg), n.in[0],
+ noclass());
else if (n.in[0].class == IMM || n.in[0].class == REF)
- return insn_create(COPY, I27, nth_ar(nth_arg), n.in[0], noclass());
+ return insn_create(COPY, I27, nth_ar(nth_arg), n.in[0],
+ noclass());
assert("illegal arg type");
abort();
@@ -57,9 +59,11 @@ static struct insn rewrite_retarg(struct insn n)
assert(nth_arg >= 0 && nth_arg < 25);
if (n.in[0].class == TMP || n.in[0].class == REG)
- return insn_create(MOVE, I27, nth_ar(nth_arg), n.in[0], noclass());
+ return insn_create(MOVE, I27, nth_ar(nth_arg), n.in[0],
+ noclass());
else if (n.in[0].class == IMM || n.in[0].class == REF)
- return insn_create(COPY, I27, nth_ar(nth_arg), n.in[0], noclass());
+ return insn_create(COPY, I27, nth_ar(nth_arg), n.in[0],
+ noclass());
assert("illegal retval type");
abort();
diff --git a/src/asm.c b/src/asm.c
index e177c4e..fd4d68a 100644
--- a/src/asm.c
+++ b/src/asm.c
@@ -8,87 +8,87 @@ static const char *rname(struct val v)
assert(v.class == REG);
/** @todo use ABI names? */
switch (v.r) {
- case RX0: return "x0";
- case RX1: return "x1";
- case RX2: return "x2";
- case RX3: return "x3";
- case RX4: return "x4";
- case RX5: return "x5";
- case RX6: return "x6";
- case RX7: return "x7";
- case RX8: return "x8";
- case RX9: return "x9";
- case RX10: return "x10";
- case RX11: return "x11";
- case RX12: return "x12";
- case RX13: return "x13";
- case RX14: return "x14";
- case RX15: return "x15";
- case RX16: return "x16";
- case RX17: return "x17";
- case RX18: return "x18";
- case RX19: return "x19";
- case RX20: return "x20";
- case RX21: return "x21";
- case RX22: return "x22";
- case RX23: return "x23";
- case RX24: return "x24";
- case RX25: return "x25";
- case RX26: return "x26";
- case RX27: return "x27";
- case RX28: return "x28";
- case RX29: return "x29";
- case RX30: return "x30";
- case RX31: return "x31";
- case RX32: return "x32";
- case RX33: return "x33";
- case RX34: return "x34";
- case RX35: return "x35";
- case RX36: return "x36";
- case RX37: return "x37";
- case RX38: return "x38";
- case RX39: return "x39";
- case RX40: return "x40";
- case RX41: return "x41";
- case RX42: return "x42";
- case RX43: return "x43";
- case RX44: return "x44";
- case RX45: return "x45";
- case RX46: return "x46";
- case RX47: return "x47";
- case RX48: return "x48";
- case RX49: return "x49";
- case RX50: return "x50";
- case RX51: return "x51";
- case RX52: return "x52";
- case RX53: return "x53";
- case RX54: return "x54";
- case RX55: return "x55";
- case RX56: return "x56";
- case RX57: return "x57";
- case RX58: return "x58";
- case RX59: return "x59";
- case RX60: return "x60";
- case RX61: return "x61";
- case RX62: return "x62";
- case RX63: return "x63";
- case RX64: return "x64";
- case RX65: return "x65";
- case RX66: return "x66";
- case RX67: return "x67";
- case RX68: return "x68";
- case RX69: return "x69";
- case RX70: return "x70";
- case RX71: return "x71";
- case RX72: return "x72";
- case RX73: return "x73";
- case RX74: return "x74";
- case RX75: return "x75";
- case RX76: return "x76";
- case RX77: return "x77";
- case RX78: return "x78";
- case RX79: return "x79";
- case RX80: return "x80";
+ case RX0: return "x0";
+ case RX1: return "x1";
+ case RX2: return "x2";
+ case RX3: return "x3";
+ case RX4: return "x4";
+ case RX5: return "x5";
+ case RX6: return "x6";
+ case RX7: return "x7";
+ case RX8: return "x8";
+ case RX9: return "x9";
+ case RX10: return "x10";
+ case RX11: return "x11";
+ case RX12: return "x12";
+ case RX13: return "x13";
+ case RX14: return "x14";
+ case RX15: return "x15";
+ case RX16: return "x16";
+ case RX17: return "x17";
+ case RX18: return "x18";
+ case RX19: return "x19";
+ case RX20: return "x20";
+ case RX21: return "x21";
+ case RX22: return "x22";
+ case RX23: return "x23";
+ case RX24: return "x24";
+ case RX25: return "x25";
+ case RX26: return "x26";
+ case RX27: return "x27";
+ case RX28: return "x28";
+ case RX29: return "x29";
+ case RX30: return "x30";
+ case RX31: return "x31";
+ case RX32: return "x32";
+ case RX33: return "x33";
+ case RX34: return "x34";
+ case RX35: return "x35";
+ case RX36: return "x36";
+ case RX37: return "x37";
+ case RX38: return "x38";
+ case RX39: return "x39";
+ case RX40: return "x40";
+ case RX41: return "x41";
+ case RX42: return "x42";
+ case RX43: return "x43";
+ case RX44: return "x44";
+ case RX45: return "x45";
+ case RX46: return "x46";
+ case RX47: return "x47";
+ case RX48: return "x48";
+ case RX49: return "x49";
+ case RX50: return "x50";
+ case RX51: return "x51";
+ case RX52: return "x52";
+ case RX53: return "x53";
+ case RX54: return "x54";
+ case RX55: return "x55";
+ case RX56: return "x56";
+ case RX57: return "x57";
+ case RX58: return "x58";
+ case RX59: return "x59";
+ case RX60: return "x60";
+ case RX61: return "x61";
+ case RX62: return "x62";
+ case RX63: return "x63";
+ case RX64: return "x64";
+ case RX65: return "x65";
+ case RX66: return "x66";
+ case RX67: return "x67";
+ case RX68: return "x68";
+ case RX69: return "x69";
+ case RX70: return "x70";
+ case RX71: return "x71";
+ case RX72: return "x72";
+ case RX73: return "x73";
+ case RX74: return "x74";
+ case RX75: return "x75";
+ case RX76: return "x76";
+ case RX77: return "x77";
+ case RX78: return "x78";
+ case RX79: return "x79";
+ case RX80: return "x80";
}
assert(0 && "illegal register");
@@ -114,7 +114,7 @@ static void save_state(struct fn *f, FILE *o)
for (size_t i = 0; i < f->max_callee_save; ++i) {
fprintf(o, "st w s%zi, -%zi(fp)\n",
- i, 3 * i + 9);
+ i, 3 * i + 9);
}
}
@@ -122,7 +122,7 @@ static void restore_state(struct fn *f, FILE *o)
{
for (size_t i = 0; i < f->max_callee_save; ++i) {
fprintf(o, "ld w s%zi, -%zi(fp)\n",
- i, 3 * i + 9);
+ i, 3 * i + 9);
}
if (f->has_calls)
@@ -134,22 +134,23 @@ static void restore_state(struct fn *f, FILE *o)
static void output_move(struct insn n, FILE *o)
{
- fprintf(o, "mv %s, %s\n",
- rname(n.out), rname(n.in[0]));
+ if (!same_val(n.out, n.in[0]))
+ fprintf(o, "mv %s, %s\n",
+ rname(n.out), rname(n.in[0]));
}
static void output_add(struct insn n, FILE *o)
{
if (n.in[1].class == REG) {
fprintf(o, "add %s, %s, %s\n",
- rname(n.out), rname(n.in[0]), rname(n.in[1]));
+ rname(n.out), rname(n.in[0]), rname(n.in[1]));
return;
}
else if (n.in[1].class == IMM) {
/** @todo fix for values larger than what addi allows, mark one
* temporary register reserved for the compiler? */
fprintf(o, "addi %s, %s, %lli\n",
- rname(n.out), rname(n.in[0]), (long long int)n.in[1].v);
+ rname(n.out), rname(n.in[0]), (long long int)n.in[1].v);
return;
}
@@ -161,16 +162,18 @@ static void output_sub(struct insn n, FILE *o)
{
if (n.in[1].class == REG) {
fprintf(o, "sub %s, %s, %s\n",
- rname(n.out), rname(n.in[0]), rname(n.in[1]));
+ rname(n.out), rname(n.in[0]), rname(n.in[1]));
return;
}
else if (n.in[1].class == IMM) {
if (n.in[1].v >= 0)
fprintf(o, "addi %s, %s, -%lli\n",
- rname(n.out), rname(n.in[0]), (long long int)n.in[1].v);
+ rname(n.out), rname(n.in[0]),
+ (long long int)n.in[1].v);
else /* double negative */
fprintf(o, "addi %s, %s, %lli\n",
- rname(n.out), rname(n.in[0]), (long long int)n.in[1].v);
+ rname(n.out), rname(n.in[0]),
+ (long long int)n.in[1].v);
return;
}
@@ -181,7 +184,7 @@ static void output_sub(struct insn n, FILE *o)
static void output_copy(struct insn n, FILE *o)
{
fprintf(o, "li %s, %lli\n",
- rname(n.out), (long long int)n.in[0].v);
+ rname(n.out), (long long int)n.in[0].v);
}
static void output_call(struct insn n, FILE *o)
@@ -205,13 +208,13 @@ static void output_insn(struct insn n, FILE *o)
* we may be missing out on certain optimizations by not using some kind
* of matching here but good enough for now */
switch (n.type) {
- case MOVE: output_move(n, o); break;
- case ADD: output_add(n, o); break;
- case SUB: output_sub(n, o); break;
- case COPY: output_copy(n, o); break;
- case CALL: output_call(n, o); break;
- default: fprintf(stderr, "unimplemented insn: %s\n", op_str(n.type));
- abort();
+ case MOVE: output_move(n, o); break;
+ case ADD: output_add(n, o); break;
+ case SUB: output_sub(n, o); break;
+ case COPY: output_copy(n, o); break;
+ case CALL: output_call(n, o); break;
+ default: fprintf(stderr, "unimplemented insn: %s\n", op_str(n.type));
+ abort();
}
}
@@ -219,16 +222,16 @@ static void output_blt(struct blk *b, struct fn *f, FILE *o)
{
assert(b->s2);
fprintf(o, "blt %s, %s, .%s.%lli\n",
- rname(b->cmp[0]), rname(b->cmp[1]),
- f->name, (long long int)b->s2->id);
+ rname(b->cmp[0]), rname(b->cmp[1]),
+ f->name, (long long int)b->s2->id);
}
static void output_ble(struct blk *b, struct fn *f, FILE *o)
{
assert(b->s2);
fprintf(o, "ble %s, %s, .%s.%lli\n",
- rname(b->cmp[0]), rname(b->cmp[1]),
- f->name, (long long int)b->s2->id);
+ rname(b->cmp[0]), rname(b->cmp[1]),
+ f->name, (long long int)b->s2->id);
}
static void output_ret(struct fn *f, FILE *o)
@@ -249,12 +252,25 @@ static void output_j(struct blk *b, struct fn *f, FILE *o)
static void output_branch(struct blk *b, struct fn *f, FILE *o)
{
switch (b->btype) {
- case RET: output_ret(f, o); break;
- case J: output_j(b, f, o); break;
- case BLT: output_blt(b, f, o); break;
- case BLE: output_ble(b, f, o); break;
- default: fprintf(stderr, "unimplemented branch: %s\n", op_str(b->btype));
- abort();
+ case RET: output_ret(f, o); break;
+ case J: output_j(b, f, o); break;
+ case BLT: output_blt(b, f, o); break;
+ case BLE: output_ble(b, f, o); break;
+ default: fprintf(stderr, "unimplemented branch: %s\n",
+ op_str(b->btype));
+ abort();
+ }
+}
+
+static void output_moves(struct vec *params, struct vec *args, FILE *o)
+{
+ /* move arguments to parameters */
+ assert(vec_len(params) == vec_len(args));
+ foreach_blk_param(pi, *params) {
+ struct val p = blk_param_at(*params, pi);
+ struct val a = blk_param_at(*args, pi);
+ struct insn i = insn_create(MOVE, NOTYPE, p, a, noclass());
+ output_move(i, o);
}
}
@@ -265,13 +281,20 @@ void output(struct fn *f, FILE *o)
foreach_blk(bi, f->blks) {
struct blk *b = blk_at(f->blks, bi);
fprintf(o, ".%s.%lli:\n",
- f->name, (long long int)b->id);
+ f->name, (long long int)b->id);
foreach_insn(i, b->insns) {
struct insn n = insn_at(b->insns, i);
output_insn(n, o);
}
+ if (b->s2)
+ output_moves(&b->s2->params, &b->args2, o);
+
output_branch(b, f, o);
+
+ /* J is again the special case */
+ if (b->s1 && b->btype != J)
+ output_moves(&b->s1->params, &b->args1, o);
}
}
diff --git a/src/nodes.c b/src/nodes.c
index a6ff0b8..05f96fe 100644
--- a/src/nodes.c
+++ b/src/nodes.c
@@ -6,7 +6,8 @@
#include <qbt/debug.h>
#include <qbt/vec.h>
-void insadd(struct blk *b, enum insn_type o, enum val_type t, struct val r, struct val a0, struct val a1)
+void insadd(struct blk *b, enum insn_type o, enum val_type t, struct val r,
+ struct val a0, struct val a1)
{
struct insn i = insn_create(o, t, r, a0, a1);
vec_append(&b->insns, &i);
@@ -35,7 +36,8 @@ int64_t idmatch(struct fn *f, const char *id)
return -1;
}
-void finish_block(struct blk *b, enum insn_type cmp, struct val a0, struct val a1, const char *label)
+void finish_block(struct blk *b, enum insn_type cmp, struct val a0,
+ struct val a1, const char *label)
{
assert(cmp >= BEQ && cmp <= RET && "illegal comparison type for block");
b->btype = cmp;
@@ -198,7 +200,7 @@ void dump_block(struct blk *b)
{
printf("//\t/*** block %lld ", (long long)b->id);
if (b->name) printf("\"%s\" ", b->name);
-
+
printf("(");
foreach_blk_param(pi, b->params) {
struct val v = blk_param_at(b->params, pi);
diff --git a/src/regalloc.c b/src/regalloc.c
index 474e5a4..68e68a2 100644
--- a/src/regalloc.c
+++ b/src/regalloc.c
@@ -1,90 +1,317 @@
#include <assert.h>
+#include <stdlib.h>
#include <qbt/regalloc.h>
#include <qbt/vec.h>
#include <qbt/abi.h>
+/* first try to use temporaries, then callee-save, then finally args.
+ * Idea is that callee-save cost is paid once at the start of the function call,
+ * after that they're free. Argument registers are generally important to keep
+ * free to make sure function calls in loops etc. don't have to shuffle
+ * registers around as much */
static const int64_t tr_map[] = {
+ RT0, RT1, RT2, RT3, RT4, RT5, RT6, RT7, RT8, RT9,
+ RT10, RT11, RT12, RT13, RT14, RT15, RT16, RT17, RT18, RT19,
+ RT20, RT21, RT22, RT23,
+
RS0, RS1, RS2, RS3, RS4, RS5, RS6, RS7, RS8, RS9,
RS10, RS11, RS12, RS13, RS14, RS15, RS16, RS17, RS18, RS19,
- RS20, RS21, RS22, RS23, RS24
+ RS20, RS21, RS22, RS23,
+
+ RA0, RA1, RA2, RA3, RA4, RA5, RA6, RA7, RA8, RA9,
+ RA10, RA11, RA12, RA13, RA14, RA15, RA16, RA17, RA18, RA19,
+ RA20, RA21, RA22, RA23,
};
-#define reg_at(v, i)\
- vect_at(int64_t, v, i)
+#define reg_at(v, i) \
+ vect_at(struct val, v, i)
-static struct val rewrite_tmp(struct vec rmap, struct val t)
+static bool has_rewrite_rule(struct vec *rmap, struct val t)
{
- assert(t.class == TMP);
- assert(t.r < (int64_t)vec_len(&rmap));
- int64_t r = reg_at(rmap, t.r);
- assert(r);
- return reg_val(r);
+ if (t.r >= (int64_t)vec_len(rmap))
+ return false;
+
+ struct val r = reg_at(*rmap, t.r);
+ return r.class != NOCLASS;
}
-static size_t cur_reg = 0;
-static void add_rewrite_rule(struct vec *rmap, struct val t)
+static struct val rewrite_tmp(struct vec *rmap, struct val t)
{
assert(t.class == TMP);
- assert(cur_reg < 25
- && "ran out of temp registers, time to implement proper regalloc!");
+ assert(t.r < (int64_t)vec_len(rmap));
+ struct val r = reg_at(*rmap, t.r);
+ assert(r.class != NOCLASS);
+ return r;
+}
+
+static void add_rewrite_rule(struct vec *rmap, struct val from, struct val to)
+{
+ assert(from.class == TMP);
+ assert(to.class == REG);
/* note <=, we go one 'beyond' just to make sure that 0 fits */
- while ((int64_t)vec_len(rmap) <= t.r) {
- int64_t zero = 0;
- vec_append(rmap, &zero);
+ while ((int64_t)vec_len(rmap) <= from.r) {
+ struct val no = noclass();
+ vec_append(rmap, &no);
}
- if (reg_at(*rmap, t.r) == 0)
- reg_at(*rmap, t.r) = tr_map[cur_reg++];
+ reg_at(*rmap, from.r) = to;
}
-void regalloc(struct fn *f)
+static void add_hint(struct vec *hints, struct val from, struct val to)
{
- /* very ugly, fix once we get the proper regalloc implemented */
- cur_reg = 0;
- struct vec rmap = vec_create(sizeof(int64_t));
+ /* kind of a hack */
+ add_rewrite_rule(hints, from, to);
+}
- /* here we would ideally do some kind of lifetime checking, to start
- * with we only assign to different temporary registers, we have enough
- * of them to work for some smaller test functions */
- /* lifetime info would probably also be useful for saving callee-save
- * registers during calls, so that should probably also be done during
- * register allocation? maybe? */
- foreach_blk(bi, f->blks) {
- struct blk *b = blk_at(f->blks, bi);
- foreach_insn(i, b->insns) {
- struct insn n = insn_at(b->insns, i);
- if (n.in[0].class == TMP) {
- n.in[0] = rewrite_tmp(rmap, n.in[0]);
- }
+static struct val get_hint(struct vec *hints, struct val from)
+{
+ if ((int64_t)vec_len(hints) <= from.r)
+ return noclass();
- if (n.in[1].class == TMP) {
- n.in[1] = rewrite_tmp(rmap, n.in[1]);
- }
+ return rewrite_tmp(hints, from);
+}
- if (n.out.class == TMP) {
- add_rewrite_rule(&rmap, n.out);
- n.out = rewrite_tmp(rmap, n.out);
- }
+struct lifetime {
+ struct val v;
+ size_t start;
+ size_t end;
+ size_t used;
+};
+
+#define lifetime_at(lifetimes, i) \
+ vect_at(struct lifetime, lifetimes, i)
+
+#define foreach_lifetime(iter, lifetimes) \
+ foreach_vec(iter, lifetimes)
+
+static void add_def(struct vec *lifetimes, struct val v, size_t i)
+{
+ while ((int64_t)vec_len(lifetimes) <= v.r) {
+ vec_append(lifetimes, &(struct lifetime){noclass(), 0, 0, 0});
+ }
+
+ /* I guess a def isn't techincally a 'use' but good enough, we assume
+ * that unused variables have already been removed by some earlier stage
+ * (not currently true but that's the intention) */
+ lifetime_at(*lifetimes, v.r) = (struct lifetime){v, i, 0, 1};
+}
- /* write back changes */
- insn_at(b->insns, i) = n;
+static void add_use(struct vec *lifetimes, struct val v, size_t i)
+{
+ assert((int64_t)vec_len(lifetimes) > v.r);
+ struct lifetime l = lifetime_at(*lifetimes, v.r);
+ assert(l.used);
+ l.used++;
+ l.end = i;
+ lifetime_at(*lifetimes, v.r) = l;
+}
+
+static void collect_lifetimes(struct blk *b, struct vec *hints,
+ struct vec *lifetimes)
+{
+ foreach_blk_param(pi, b->params) {
+ struct val v = blk_param_at(b->params, pi);
+ add_def(lifetimes, v, 0);
+ }
+
+ size_t pos = 1;
+ foreach_insn(ii, b->insns) {
+ struct insn i = insn_at(b->insns, ii);
+ if (i.in[0].class == TMP)
+ add_use(lifetimes, i.in[0], pos);
- /* do this here since the register allocation is the
- * last stage before actually lowering to assembly, so
- * no possibility of dead code elimination or stuff like
- * that */
- if (n.type == CALL)
- f->has_calls = true;
+ if (i.in[1].class == TMP)
+ add_use(lifetimes, i.in[1], pos);
+
+ if (i.out.class == TMP)
+ add_def(lifetimes, i.out, pos);
+
+ /* collect some early hints */
+ if (i.type == MOVE) {
+ /* input arguments, retvals */
+ if (i.out.class == TMP && i.in[0].class == REG)
+ add_hint(hints, i.out, i.in[0]);
+
+ if (i.out.class == REG && i.in[0].class == TMP)
+ add_hint(hints, i.in[0], i.out);
}
- if (b->cmp[0].class == TMP)
- b->cmp[0] = rewrite_tmp(rmap, b->cmp[0]);
+ pos++;
+ }
+
+ if (b->cmp[0].class == TMP)
+ add_use(lifetimes, b->cmp[0], pos);
+
+ if (b->cmp[1].class == TMP)
+ add_use(lifetimes, b->cmp[1], pos);
+
+ foreach_blk_param(pi, b->args1) {
+ struct val v = blk_param_at(b->args1, pi);
+ add_use(lifetimes, v, pos);
+ }
+
+ foreach_blk_param(pi, b->args2) {
+ struct val v = blk_param_at(b->args2, pi);
+ add_use(lifetimes, v, pos);
+ }
+}
+
+static void build_active(struct vec *active, struct vec *lifetimes, size_t i)
+{
+ struct lifetime ref = lifetime_at(*lifetimes, i);
+ foreach_lifetime(li, *lifetimes) {
+ struct lifetime l = lifetime_at(*lifetimes, li);
+ if (l.used == 0)
+ continue;
+
+ if (l.end < ref.start)
+ continue;
+
+ if (l.start > ref.end)
+ continue;
+
+ vec_append(active, &l);
+ }
+}
- if (b->cmp[1].class == TMP)
- b->cmp[1] = rewrite_tmp(rmap, b->cmp[1]);
+static void build_reserved(struct vec *reserved, struct vec *active,
+ struct vec *rmap)
+{
+ foreach_lifetime(li, *active) {
+ struct lifetime l = lifetime_at(*active, li);
+ if (l.used == 0)
+ continue;
+
+ if (has_rewrite_rule(rmap, l.v)) {
+ struct val act = rewrite_tmp(rmap, l.v);
+ vec_append(reserved, &act);
+ }
+ }
+}
+
+static bool reg_free(struct vec *reserved, struct val f)
+{
+ assert(f.class == REG);
+ /* not the fastest way in the world, but good enough for now */
+ foreach_val(ri, *reserved) {
+ struct val r = val_at(*reserved, ri);
+ if (same_val(r, f))
+ return false;
+ }
+
+ return true;
+}
+
+static struct val find_free_reg(struct vec *reserved)
+{
+ for (size_t i = 0; i < sizeof(tr_map) / sizeof(tr_map[0]); ++i) {
+ struct val r = reg_val(tr_map[i]);
+ if (reg_free(reserved, r))
+ return r;
+ }
+
+ /* handle spill case later */
+ assert(0 &&
+ "ran out of registers, time to implement proper spill handling");
+ abort();
+}
+
+static void build_rmap(struct vec *hints, struct vec *lifetimes,
+ struct vec *rmap)
+{
+ struct vec active = vec_create(sizeof(struct lifetime));
+ struct vec reserved = vec_create(sizeof(struct val));
+
+ foreach_lifetime(li, *lifetimes) {
+ struct lifetime l = lifetime_at(*lifetimes, li);
+ if (l.used == 0)
+ continue;
+
+ vec_reset(&active);
+ build_active(&active, lifetimes, li);
+ build_reserved(&reserved, &active, rmap);
+
+ struct val h = get_hint(hints, l.v);
+ if (h.class != NOCLASS) {
+ if (reg_free(&reserved, h)) {
+ add_rewrite_rule(rmap, l.v, h);
+ continue;
+ }
+ }
+
+ /* eventually we should select the spill register only for the
+ * least used register, but that's a bit more complicated than
+ * just this linear scan */
+ struct val f = find_free_reg(&reserved);
+ add_rewrite_rule(rmap, l.v, f);
+ }
+}
+
+/* has_calls is kind of in an iffy place but I guess it's fine */
+static void do_rewrites(struct blk *b, struct vec *rmap, struct fn *f)
+{
+ foreach_blk_param(pi, b->params) {
+ struct val p = blk_param_at(b->params, pi);
+ blk_param_at(b->params, pi) = rewrite_tmp(rmap, p);
+ }
+
+ foreach_insn(ii, b->insns) {
+ struct insn i = insn_at(b->insns, ii);
+ if (i.in[0].class == TMP)
+ i.in[0] = rewrite_tmp(rmap, i.in[0]);
+
+ if (i.in[1].class == TMP)
+ i.in[1] = rewrite_tmp(rmap, i.in[1]);
+
+ if (i.out.class == TMP)
+ i.out = rewrite_tmp(rmap, i.out);
+
+ /** @todo save caller-save at callsites here */
+ if (i.type == CALL)
+ f->has_calls = true;
+
+ /* write back changes, christ I forget this a lot */
+ insn_at(b->insns, ii) = i;
+ }
+
+ if (b->cmp[0].class == TMP)
+ b->cmp[0] = rewrite_tmp(rmap, b->cmp[0]);
+
+ if (b->cmp[1].class == TMP)
+ b->cmp[1] = rewrite_tmp(rmap, b->cmp[1]);
+
+ foreach_blk_param(pi, b->args1) {
+ struct val p = blk_param_at(b->args1, pi);
+ blk_param_at(b->args1, pi) = rewrite_tmp(rmap, p);
+ }
+
+ foreach_blk_param(pi, b->args2) {
+ struct val p = blk_param_at(b->args2, pi);
+ blk_param_at(b->args2, pi) = rewrite_tmp(rmap, p);
+ }
+}
+
+/* assumes ssa form */
+void regalloc(struct fn *f)
+{
+ struct vec hints = vec_create(sizeof(struct val));
+ struct vec lifetimes = vec_create(sizeof(struct lifetime));
+ struct vec rmap = vec_create(sizeof(struct val));
+
+ /* here it would probably make sense to iterate through lifetimes in
+ * order of priority, like loop nesting/count etc */
+ foreach_blk(bi, f->blks) {
+ struct blk *b = blk_at(f->blks, bi);
+ vec_reset(&lifetimes);
+ /** @todo collect hints from args/params */
+ collect_lifetimes(b, &hints, &lifetimes);
+ build_rmap(&hints, &lifetimes, &rmap);
+ do_rewrites(b, &rmap, f);
+ /** @todo forward_hints(b, &hints, &rmap) */
}
- f->max_callee_save = cur_reg;
+ vec_destroy(&hints);
+ vec_destroy(&lifetimes);
vec_destroy(&rmap);
}
diff --git a/src/ssa.c b/src/ssa.c
index 59e7254..96d1eb1 100644
--- a/src/ssa.c
+++ b/src/ssa.c
@@ -78,7 +78,7 @@ static void build_params(struct blk *b, int visited)
struct val in2 = i.in[1];
if (in2.class == TMP && !has_val(&generated, in2))
add_val(&required, in2);
-
+
struct val out = i.out;
if (out.class == TMP) {
add_val(&generated, out);
@@ -147,7 +147,7 @@ static void collect_params(struct blk *b, int visited)
}
}
-#define tmpval_at(rmap, i)\
+#define tmpval_at(rmap, i) \
vect_at(struct val, rmap, i)
static void add_rewrite_rule(struct vec *rmap, struct val from, struct val to)
diff --git a/src/vec.c b/src/vec.c
index 4ba92fb..e487162 100644
--- a/src/vec.c
+++ b/src/vec.c
@@ -7,13 +7,18 @@
struct vec vec_create(size_t ns)
{
return (struct vec) {
- .n = 0,
- .s = 1,
- .ns = ns,
- .buf = malloc(ns),
+ .n = 0,
+ .s = 1,
+ .ns = ns,
+ .buf = malloc(ns),
};
}
+void vec_reset(struct vec *v)
+{
+ v->n = 0;
+}
+
size_t vec_len(struct vec *v)
{
return v->n;
generated by cgit v1.3 (git 2.53.0) at 2026-08-27 01:44:38 +0000