From f4be2429f38faba0c54862055f808cb242a7eb49 Mon Sep 17 00:00:00 2001 From: Kimplul Date: Wed, 3 Apr 2024 18:36:21 +0300 Subject: make regalloc work with ssa form + Still not ideal register allocator, but can be improved with some heuristics and potentially completely replaced in the future if so desired with graph coloring or something. --- src/abi.c | 14 ++- src/asm.c | 241 +++++++++++++++++++++------------------- src/nodes.c | 8 +- src/regalloc.c | 339 +++++++++++++++++++++++++++++++++++++++++++++++---------- src/ssa.c | 4 +- src/vec.c | 13 ++- 6 files changed, 440 insertions(+), 179 deletions(-) (limited to 'src') 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 #include -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 +#include #include #include #include +/* 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)); - - /* 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]); - } + /* kind of a hack */ + add_rewrite_rule(hints, from, to); +} - if (n.in[1].class == TMP) { - n.in[1] = rewrite_tmp(rmap, n.in[1]); - } +static struct val get_hint(struct vec *hints, struct val from) +{ + if ((int64_t)vec_len(hints) <= from.r) + return noclass(); - if (n.out.class == TMP) { - add_rewrite_rule(&rmap, n.out); - n.out = rewrite_tmp(rmap, n.out); - } + return rewrite_tmp(hints, from); +} + +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}; +} + +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); + + 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); + } + + 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; - /* write back changes */ - insn_at(b->insns, i) = n; + if (l.end < ref.start) + continue; - /* 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 (l.start > ref.end) + continue; + + vec_append(active, &l); + } +} + +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; + } } - if (b->cmp[0].class == TMP) - b->cmp[0] = rewrite_tmp(rmap, b->cmp[0]); + /* 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)); - if (b->cmp[1].class == TMP) - b->cmp[1] = rewrite_tmp(rmap, b->cmp[1]); + /* 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; -- cgit v1.3