diff options
Diffstat (limited to 'src')
| -rw-r--r-- | src/common.h | 4 | ||||
| -rw-r--r-- | src/compile/compile.c | 188 | ||||
| -rw-r--r-- | src/ejit.c | 10 |
3 files changed, 176 insertions, 26 deletions
diff --git a/src/common.h b/src/common.h index 493a89d..3e56a76 100644 --- a/src/common.h +++ b/src/common.h @@ -258,7 +258,7 @@ struct ejit_insn { struct fpr_stat { struct ejit_fpr f; - size_t prio, fno; + size_t prio, fno, start, end; }; #define VEC_NAME fpr_stats @@ -267,7 +267,7 @@ struct fpr_stat { struct gpr_stat { struct ejit_gpr r; - size_t prio, rno; + size_t prio, rno, start, end; }; #define VEC_NAME gpr_stats diff --git a/src/compile/compile.c b/src/compile/compile.c index 50f12dc..aba44a0 100644 --- a/src/compile/compile.c +++ b/src/compile/compile.c @@ -2203,7 +2203,7 @@ static size_t compile_fn_body(struct ejit_func *f, jit_state_t *j, void *arena, jit_operand_t type = jit_operand_imm(JIT_OPERAND_ABI_WORD, i.r1); jit_operand_t arg; - if (i.r2 < physfpr_count()) { + if (f2 < physfpr_count()) { /* regular register */ arg = jit_operand_fpr(jit_abi_from(i.r1), physfpr_at(f2)); @@ -2421,43 +2421,187 @@ calli: return size; } -/* highest prio first */ -static int gpr_sort_prio(struct gpr_stat *a, struct gpr_stat *b) +struct alive_slot { + long r; + size_t cost; + size_t idx; + size_t remap; +}; + +#define VEC_NAME alive +#define VEC_TYPE struct alive_slot +#include "../vec.h" + +static int spill_cost_sort(struct alive_slot *a, struct alive_slot *b) { - return (int)b->prio - (int)a->prio; + if (a->cost > b->cost) + return -1; + + return a->cost < b->cost; +} + +/* slightly more parameters than I would like but I guess it's fine */ +static void calculate_alive(struct alive *alive, size_t idx, + size_t prio, size_t start, size_t end, size_t *rno, + void *regs, int (*dead)(void *regs, size_t idx, size_t start)) +{ + /* single-shot */ + if (end <= start + 1) { + *rno = 0; + struct alive_slot *a = alive_at(alive, 0); + a->cost += prio; + return; + } + + long max_cost_idx = -1; + size_t max_cost = 0; + long counter = 0; + foreach_vec(ai, *alive) { + struct alive_slot *a = alive_at(alive, ai); + + /* skip reserved slot */ + if (idx == 0) { + counter++; + continue; + } + + if (a->r < 0 && a->cost > max_cost) { + max_cost = a->cost; + max_cost_idx = counter; + } + + counter++; + + /* skip gravestones */ + if (a->r < 0) + continue; + + if (dead(regs, a->r, start)) + a->r = -1; /* gravestone */ + } + + /* there's a suitable slot for us */ + if (max_cost_idx >= 0) { + *rno = max_cost_idx; + + struct alive_slot *a = alive_at(alive, max_cost_idx); + a->cost += prio; + a->r = idx; + return; + } + + *rno = alive_len(alive); + struct alive_slot a = { + .cost = prio, + .r = idx, + .idx = *rno + }; + alive_append(alive, a); } -static int fpr_sort_prio(struct fpr_stat *a, struct fpr_stat *b) +static int gpr_dead(void *regs, size_t idx, size_t start) { - return (int)b->prio - (int)a->prio; + struct gpr_stats *gprs = regs; + return gpr_stats_at(gprs, idx)->end < start; } -/* sort registers by highest priority first, then renumber registers in the - * given order. Higher priority is given a physical register first. - * - * Note that the `->r` field becomes 'meaningless' after sorting, and you should - * only use the `->rno` field after this point. Essentially, if you have a - * register EJIT_GPR(2), you should use `gpr_stats_at(2)->rno` for the 'actual' - * register number in `getloc` and the like. - * - * Can be a bit confusing, but this way we don't have to allocate any new - * arrays, which is cool. */ +static void linear_gpr_alloc(struct ejit_func *f) +{ + foreach_vec(gi, f->gpr) { + gpr_stats_at(&f->gpr, gi)->rno = gi; + } +} + +/* there's a fair bit of repetition between this and the gpr case, hmm */ static void assign_gprs(struct ejit_func *f) { - gpr_stats_sort(&f->gpr, (vec_comp_t)gpr_sort_prio); + /* everything fits into registers, no need to start optimizing */ + if (gpr_stats_len(&f->gpr) <= physgpr_count()) + return linear_gpr_alloc(f); + + struct alive alive = alive_create(gpr_stats_len(&f->gpr)); + + /* special oneshot register class */ + struct alive_slot a = {.r = 0, .cost = 0, .idx = 0}; + alive_append(&alive, a); + + foreach_vec(gi, f->gpr) { + struct gpr_stat *gpr = gpr_stats_at(&f->gpr, gi); + calculate_alive(&alive, gi, + gpr->prio, gpr->start, gpr->end, &gpr->rno, + &f->gpr, gpr_dead); + } + + /* sort so that the highest spill cost register classes are at the front and + * as such more likely to be placed in registers */ + alive_sort(&alive, (vec_comp_t)spill_cost_sort); + + /* update remapping info */ + for(size_t i = 0; i < alive_len(&alive); ++i) { + struct alive_slot *a = alive_at(&alive, i); + alive_at(&alive, a->idx)->remap = i; + } + + /* remap locations */ for (size_t i = 0; i < gpr_stats_len(&f->gpr); ++i) { - size_t rno = gpr_stats_at(&f->gpr, i)->r.r; - gpr_stats_at(&f->gpr, rno)->rno = i; + struct gpr_stat *gpr = gpr_stats_at(&f->gpr, i); + struct alive_slot *a = alive_at(&alive, gpr->rno); + gpr->rno = a->remap; + } + + alive_destroy(&alive); +} + +static int fpr_dead(void *regs, size_t idx, size_t start) +{ + struct fpr_stats *fprs = regs; + return fpr_stats_at(fprs, idx)->end < start; +} + +static void linear_fpr_alloc(struct ejit_func *f) +{ + foreach_vec(fi, f->fpr) { + fpr_stats_at(&f->fpr, fi)->fno = fi; } } static void assign_fprs(struct ejit_func *f) { - fpr_stats_sort(&f->fpr, (vec_comp_t)fpr_sort_prio); + /* everything fits into registers, no need to start optimizing */ + if (fpr_stats_len(&f->fpr) <= physfpr_count()) + return linear_fpr_alloc(f); + + struct alive alive = alive_create(fpr_stats_len(&f->fpr)); + + /* special oneshot register class */ + struct alive_slot a = {.r = 0, .cost = 0, .idx = 0}; + alive_append(&alive, a); + + foreach_vec(fi, f->fpr) { + struct fpr_stat *fpr = fpr_stats_at(&f->fpr, fi); + calculate_alive(&alive, fi, + fpr->prio, fpr->start, fpr->end, &fpr->fno, + &f->fpr, fpr_dead); + } + + /* sort so that the highest spill cost register classes are at the front and + * as such more likely to be placed in registers */ + alive_sort(&alive, (vec_comp_t)spill_cost_sort); + + /* update remapping info */ + for(size_t i = 0; i < alive_len(&alive); ++i) { + struct alive_slot *a = alive_at(&alive, i); + alive_at(&alive, a->idx)->remap = i; + } + + /* remap locations */ for (size_t i = 0; i < fpr_stats_len(&f->fpr); ++i) { - size_t rno = fpr_stats_at(&f->fpr, i)->f.f; - fpr_stats_at(&f->fpr, rno)->fno = i; + struct fpr_stat *fpr = fpr_stats_at(&f->fpr, i); + struct alive_slot *a = alive_at(&alive, fpr->fno); + fpr->fno = a->remap; } + + alive_destroy(&alive); } static size_t align_up(size_t a, size_t n) @@ -48,9 +48,12 @@ static void update_gpr(struct ejit_func *f, struct ejit_gpr r0) 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) + if (gpr->prio == 0) { + gpr->start = insns_len(&f->insns); gpr->r = r0; + } + gpr->end = insns_len(&f->insns); gpr->prio += f->prio; } @@ -60,9 +63,12 @@ static void update_fpr(struct ejit_func *f, struct ejit_fpr f0) fpr_stats_append(&f->fpr, zero_fpr_stat()); struct fpr_stat *fpr = fpr_stats_at(&f->fpr, f0.f); - if (fpr->prio == 0) + if (fpr->prio == 0) { + fpr->start = insns_len(&f->insns); fpr->f = f0; + } + fpr->end = insns_len(&f->insns); fpr->prio += f->prio; } |