From 2676caa4209d1a81fbb4076d87da699f681d14e2 Mon Sep 17 00:00:00 2001 From: lemon Date: Sat, 13 Sep 2025 23:33:52 +0200 Subject: regalloc improvements --- common.h | 1 + mem.c | 6 +++++ regalloc.c | 83 +++++++++++++++++++++++++++++++++++++------------------------- 3 files changed, 57 insertions(+), 33 deletions(-) diff --git a/common.h b/common.h index 0079163..6c2e1e9 100644 --- a/common.h +++ b/common.h @@ -377,6 +377,7 @@ xbgrow_(void **p, size_t n) struct arena *newarena(uint chunksiz); void *alloc(struct arena **, uint siz, uint align); +void *allocz(struct arena **, uint siz, uint align); static inline void * alloccopy(struct arena **arena, const void *src, uint siz, uint align) { diff --git a/mem.c b/mem.c index cf65087..b673986 100644 --- a/mem.c +++ b/mem.c @@ -117,6 +117,12 @@ alloc(struct arena **par, uint siz, uint align) return new->mem; } +void * +allocz(struct arena **par, uint siz, uint align) +{ + return memset(alloc(par, siz, align), 0, siz); +} + void freearena(struct arena *ar) { diff --git a/regalloc.c b/regalloc.c index 63d9d7c..6f737e6 100644 --- a/regalloc.c +++ b/regalloc.c @@ -315,11 +315,10 @@ fixcssa(struct function *fn) } while ((blk = blk->lnext) != fn->entry); } -static bool +static inline bool rangeoverlap(struct range a, struct range b) { - return (a.from < b.from && b.from < a.to) - || (b.from < a.from && a.from < b.to); + return a.from < b.to && b.from < a.to; } static bool @@ -343,6 +342,18 @@ pushrange(struct interval *lv, struct range r) } #define itrange(lv, i) ((lv)->nrange <= 2 ? (lv)->_inl : (lv)->_dyn)[i] +static bool +intervaloverlap(struct interval *a, struct interval *b) +{ + for (int i = 0, j = 0; i < a->nrange && j < b->nrange; ) { + struct range r1 = itrange(a, i), r2 = itrange(b, 2); + if (rangeoverlap(r1, r2)) return 1; + if (r1.to <= r2.from) ++i; + else ++j; + } + return 0; +} + static void addrange0(struct interval *it, struct range new) { @@ -459,10 +470,10 @@ buildintervals(struct rega *ra) { extern int ninstr; struct block *blk, *last; - struct bitset **livein = xcalloc(ra->fn->nblk * sizeof *livein); + struct bitset **livein = alloc(&ra->arena, ra->fn->nblk * sizeof *livein, 0); for (int i = 0; i < ra->fn->nblk; ++i) - livein[i] = xcalloc(BSSIZE(ninstr) * sizeof *livein[i]); + livein[i] = allocz(&ra->arena, BSSIZE(ninstr) * sizeof *livein[i], 0); numberinstrs(ra->fn); /* visit blocks in reverse, to build lifetime intervals */ @@ -541,24 +552,18 @@ buildintervals(struct rega *ra) defreg(ra, reg, pos); } } - for (int j = 0; j < call->narg; ++j) { - int reg = call->abiarg[j].reg; - if (reg >= 0) { - rclob = rsclr(rclob, reg); - usereg(ra, reg, blk, pos); - } - } if (rclob) { struct fixinterval *fxit = alloc(&ra->arena, sizeof *fxit, 0); fxit->next = ra->intervals.fixed; fxit->range = (struct range) {pos, pos}; fxit->rs = rclob; ra->intervals.fixed = fxit; - /*DBG("CLOBBER @%d:%d {", blk->id, curi); - for (int reg = 0; rsiter(®, rclob); ++reg) { - DBG("%s,",mctarg->rnames[reg]); + } + for (int j = call->narg - 1; j >= 0; --j) { + int reg = call->abiarg[j].reg; + if (reg >= 0) { + usereg(ra, reg, blk, pos); } - DBG("}\n");*/ } } @@ -622,24 +627,21 @@ buildintervals(struct rega *ra) // DBG("live out: "), priliveset(live, bssize); } while ((blk = blk->lprev) != last); - for (int i = 0; i < ra->fn->nblk; ++i) free(livein[i]); - free(livein); - int var; struct interval *lv; imap_each(&ra->intervals.temps, var, lv) { - DBG("lifetime of %%%d: [ ", var); + DBG("lifetime of %%%d: ", var); for (int i = 0; i < lv->nrange; ++i) { struct range r = itrange(lv, i); - DBG("%d-%d, ", r.from, r.to); + DBG("[%d,%d)%s", r.from, r.to, i < lv->nrange-1 ? ", " : ""); } - DBG("]\n"); + DBG("\n"); } for (struct fixinterval *fx = ra->intervals.fixed; fx; fx = fx->next) { DBG("fixed {"); for (int r = 0; rsiter(&r, fx->rs); ++r) DBG("%s,", mctarg->rnames[r]); - DBG("}: [%d-%d]\n", fx->range.from, fx->range.to); + DBG("}: [%d,%d)\n", fx->range.from, fx->range.to); } } @@ -717,7 +719,7 @@ linearscan(struct rega *ra) inactive = it; if (it->alloc.t == AREG) { ra->free |= 1<alloc.a; - //DBG(" unblock %s\n", mctarg->rnames[it->reg]); + DBG(" >> %%%d unblock %s\n", ra->intervals.temps.mb.k[it-ra->intervals.temps.v], mctarg->rnames[it->alloc.a]); } } else lnk = &it->next; } @@ -741,7 +743,7 @@ linearscan(struct rega *ra) if (it->alloc.t == AREG) { assert(rstest(ra->free, it->alloc.a)); ra->free &= ~(1<alloc.a); - //DBG("reblock %s\n", mctarg->rnames[it->reg]); + DBG(" << %%%d reblock %s\n", ra->intervals.temps.mb.k[it-ra->intervals.temps.v], mctarg->rnames[it->alloc.a]); } } else lnk = &it->next; } @@ -753,19 +755,29 @@ linearscan(struct rega *ra) struct instr *ins = &instrtab[this]; int reg = 0; int end = itrange(current, current->nrange-1).to; - // XXX check regs in inactive intervals dont overlap with current + + /* exclude regs from overlapping fixed intervals */ for (struct fixinterval *fxit = intervals->fixed; fxit; fxit = fxit->next) { if (fxit->range.to <= pos) { intervals->fixed = fxit->next; continue; - } else if (fxit->range.from >= end) + } else if (fxit->range.from >= end) { break; -// if (rangeoverlap(it->range, (struct range) {pos, itrange(current, current->n-1).to})) { - // if (fxit->range.to >= pos && fxit->range.to < itrange(current, current->n-1).from) { - if (rangeoverlap(fxit->range, (struct range) {pos, end}) && fxit->range.from != end) { - free = rsminus(free, fxit->rs); + } + + for (int i = 0; i < current->nrange; ++i) { + if (rangeoverlap(fxit->range, itrange(current, i))) { + free = rsminus(free, fxit->rs); + } + } + } + /* exclude regs from overlapping inactive intervals */ + for (struct interval *it = inactive; it; it = it->next) { + if (it->alloc.t == AREG && intervaloverlap(it, current)) { + free = rsclr(free, it->alloc.a); } } + /* for 2-address instrs, exclude reg from 2nd arg */ if (ins->inplace && opnarg[ins->op] == 2) { int xreg; if (ins->r.t == RREG) free = rsclr(free, ins->r.i); @@ -783,6 +795,7 @@ linearscan(struct rega *ra) continue; } + /* have free regs, try to use hint */ if (current->rhint >= 0) DBG("have hint %s for %%%d\n", mctarg->rnames[current->rhint], intervals->temps.mb.k[current - intervals->temps.v]); @@ -809,6 +822,10 @@ linearscan(struct rega *ra) goto GotReg; } } + + /* prefer caller-saved registers */ + if (rsminus(free, mctarg->rcallee) != 0) free = rsminus(free, mctarg->rcallee); + for (reg = 0; !rstest(free, reg); ++reg); } GotReg: @@ -834,7 +851,7 @@ regalloc(struct function *fn) struct rega ra = {fn, .arena = (void *)amem.m}; struct block *blk, *last; memset(ra.arena, 0, sizeof *ra.arena); - ra.arena->cap = sizeof amem.m; + ra.arena->cap = sizeof amem.m - sizeof(struct arena); /* setup */ if (!fpregset || !gpregset) { @@ -1157,7 +1174,7 @@ fixlive(struct function *fn) struct bitset definedbuf[4] = {0}; struct bitset *defined = definedbuf; - if (ninstr >= sizeof(definedbuf)*8) + if (BSSIZE(ninstr) >= sizeof(definedbuf)) defined = xcalloc(sizeof *defined * BSSIZE(ninstr)); npendingphi = 0; -- cgit v1.2.3