diff options
Diffstat (limited to 'src/spill.c')
| -rw-r--r-- | src/spill.c | 507 |
1 files changed, 0 insertions, 507 deletions
diff --git a/src/spill.c b/src/spill.c deleted file mode 100644 index 72f8106..0000000 --- a/src/spill.c +++ /dev/null @@ -1,507 +0,0 @@ -#include "all.h" - -static void -loopmark(Blk *hd, Blk *b, Phi *p) -{ - int k, head; - uint n, a; - - head = hd->id; - if (b->id < head) - return; - for (; p; p=p->link) - for (a=0; a<p->narg; a++) - if (p->blk[a] == b) - if (rtype(p->arg[a]) == RTmp) - bsset(hd->gen, p->arg[a].val); - if (b->visit == head) - return; - b->visit = head; - b->loop *= 10; - /* aggregate looping information at - * loop headers */ - bsunion(hd->gen, b->gen); - for (k=0; k<2; k++) - if (b->nlive[k] > hd->nlive[k]) - hd->nlive[k] = b->nlive[k]; - for (n=0; n<b->npred; n++) - loopmark(hd, b->pred[n], b->phi); -} - -static void -tmpuse(Ref r, int use, int loop, Fn *fn) -{ - Mem *m; - Tmp *t; - - if (rtype(r) == RAMem) { - m = &fn->mem[r.val & AMask]; - tmpuse(m->base, 1, loop, fn); - tmpuse(m->index, 1, loop, fn); - } - else if (rtype(r) == RTmp && r.val >= Tmp0) { - t = &fn->tmp[r.val]; - t->nuse += use; - t->ndef += !use; - t->cost += loop; - } -} - -/* evaluate spill costs of temporaries, - * this also fills usage information - * requires rpo, preds - */ -void -fillcost(Fn *fn) -{ - int n, hd; - uint a; - Blk *b; - Ins *i; - Tmp *t; - Phi *p; - - for (b=fn->start; b; b=b->link) { - b->loop = 1; - b->visit = -1; - } - if (debug['S']) - fprintf(stderr, "\n> Loop information:\n"); - for (n=0; n<fn->nblk; n++) { - b = fn->rpo[n]; - hd = 0; - for (a=0; a<b->npred; a++) - if (b->pred[a]->id >= n) { - loopmark(b, b->pred[a], b->phi); - hd = 1; - } - if (hd && debug['S']) { - fprintf(stderr, "\t%-10s", b->name); - fprintf(stderr, " (% 3d ", b->nlive[0]); - fprintf(stderr, "% 3d) ", b->nlive[1]); - dumpts(b->gen, fn->tmp, stderr); - } - } - for (t=fn->tmp; t-fn->tmp < fn->ntmp; t++) { - t->cost = t-fn->tmp < Tmp0 ? 1e6 : 0; - t->nuse = 0; - t->ndef = 0; - } - for (b=fn->start; b; b=b->link) { - for (p=b->phi; p; p=p->link) { - /* todo, the cost computation - * for p->to is not great... */ - tmpuse(p->to, 0, 0, fn); - for (a=0; a<p->narg; a++) { - n = p->blk[a]->loop; - assert(b->npred==p->narg && - "wrong cfg"); - n /= b->npred; - tmpuse(p->arg[a], 1, n, fn); - } - } - n = b->loop; - for (i=b->ins; i-b->ins < b->nins; i++) { - tmpuse(i->to, 0, n, fn); - tmpuse(i->arg[0], 1, n, fn); - tmpuse(i->arg[1], 1, n, fn); - } - tmpuse(b->jmp.arg, 1, n, fn); - } - if (debug['S']) { - fprintf(stderr, "\n> Spill costs:\n"); - for (n=Tmp0; n<fn->ntmp; n++) - fprintf(stderr, "\t%-10s %d\n", - fn->tmp[n].name, - fn->tmp[n].cost); - fprintf(stderr, "\n"); - } -} - -static BSet *fst; /* temps to prioritize in registers (for tcmp1) */ -static Tmp *tmp; /* current temporaries (for tcmpX) */ -static int ntmp; /* current # of temps (for limit) */ -static int locs; /* stack size used by locals */ -static int slot4; /* next slot of 4 bytes */ -static int slot8; /* ditto, 8 bytes */ -static BSet mask[2][1]; /* class masks */ - -static int -tcmp0(const void *pa, const void *pb) -{ - return tmp[*(int *)pb].cost - tmp[*(int *)pa].cost; -} - -static int -tcmp1(const void *pa, const void *pb) -{ - int c; - - c = bshas(fst, *(int *)pb) - bshas(fst, *(int *)pa); - return c ? c : tcmp0(pa, pb); -} - -static Ref -slot(int t) -{ - int s; - - if (t < Tmp0) - diag("spill: cannot spill register"); - s = tmp[t].slot; - if (s == -1) { - assert(NAlign == 3); - /* nice logic to pack stack slots - * on demand, there can be only - * one hole and slot4 points to it - * - * invariant: slot4 <= slot8 - */ - if (KWIDE(tmp[t].cls)) { - s = slot8; - if (slot4 == slot8) - slot4 += 2; - slot8 += 2; - } else { - s = slot4; - if (slot4 == slot8) { - slot8 += 2; - slot4 += 1; - } else - slot4 = slot8; - } - s += locs; - tmp[t].slot = s; - } - return SLOT(s); -} - -static void -limit(BSet *b, int k, BSet *f) -{ - static int *tarr, maxt; - int i, nt; - uint t; - - nt = bscount(b); - if (nt <= k) - return; - if (nt > maxt) { - free(tarr); - tarr = emalloc(nt * sizeof tarr[0]); - maxt = nt; - } - for (i=0, t=0; bsiter(b, &t); t++) { - bsclr(b, t); - tarr[i++] = t; - } - if (!f) - qsort(tarr, nt, sizeof tarr[0], tcmp0); - else { - fst = f; - qsort(tarr, nt, sizeof tarr[0], tcmp1); - } - for (i=0; i<k && i<nt; i++) - bsset(b, tarr[i]); - for (; i<nt; i++) - slot(tarr[i]); -} - -static void -limit2(BSet *b1, int k1, int k2, BSet *fst) -{ - BSet b2[1]; - - bsinit(b2, ntmp); /* todo, free those */ - bscopy(b2, b1); - bsinter(b1, mask[0]); - bsinter(b2, mask[1]); - limit(b1, NIReg - k1, fst); - limit(b2, NFReg - k2, fst); - bsunion(b1, b2); -} - -static void -sethint(BSet *u, bits r) -{ - uint t; - - for (t=Tmp0; bsiter(u, &t); t++) - tmp[phicls(t, tmp)].hint.m |= r; -} - -static void -reloads(BSet *u, BSet *v) -{ - uint t; - - for (t=Tmp0; bsiter(u, &t); t++) - if (!bshas(v, t)) - emit(OLoad, tmp[t].cls, TMP(t), slot(t), R); -} - -static void -store(Ref r, int s) -{ - static int kstore[] = { - [Kw] = OStorew, [Kl] = OStorel, - [Ks] = OStores, [Kd] = OStored, - }; - - if (s != -1) - emit(kstore[tmp[r.val].cls], 0, R, r, SLOT(s)); -} - -static int -regcpy(Ins *i) -{ - return i->op == OCopy && isreg(i->arg[0]); -} - -static Ins * -dopm(Blk *b, Ins *i, BSet *v) -{ - int n, t; - BSet u[1]; - Ins *i1; - bits r; - - bsinit(u, ntmp); /* todo, free those */ - /* consecutive copies from - * registers need to be handled - * as one large instruction - * - * fixme: there is an assumption - * that calls are always followed - * by copy instructions here, this - * might not be true if previous - * passes change - */ - i1 = ++i; - do { - i--; - t = i->to.val; - if (!req(i->to, R)) - if (bshas(v, t)) { - bsclr(v, t); - store(i->to, tmp[t].slot); - } - bsset(v, i->arg[0].val); - } while (i != b->ins && regcpy(i-1)); - bscopy(u, v); - if (i != b->ins && (i-1)->op == OCall) { - v->t[0] &= ~retregs((i-1)->arg[1], 0); - limit2(v, NISave, NFSave, 0); - for (r=0, n=0; n<NRSave; n++) - r |= BIT(rsave[n]); - v->t[0] |= argregs((i-1)->arg[1], 0); - } else { - limit2(v, 0, 0, 0); - r = v->t[0]; - } - sethint(v, r); - reloads(u, v); - do - emiti(*--i1); - while (i1 != i); - return i; -} - -/* spill code insertion - * requires spill costs, rpo, liveness - * - * Note: this will replace liveness - * information (in, out) with temporaries - * that must be in registers at block - * borders - * - * Be careful with: - * - OCopy instructions to ensure register - * constraints - */ -void -spill(Fn *fn) -{ - Blk *b, *s1, *s2, *hd, **bp; - int j, n, l, t, k, lvarg[2]; - BSet u[1], v[1], w[1]; - Ins *i; - Phi *p; - Mem *m; - bits r; - - tmp = fn->tmp; - ntmp = fn->ntmp; - bsinit(u, ntmp); - bsinit(v, ntmp); - bsinit(w, ntmp); - bsinit(mask[0], ntmp); - bsinit(mask[1], ntmp); - locs = fn->slot; - slot4 = 0; - slot8 = 0; - for (t=0; t<ntmp; t++) { - k = 0; - if (t >= XMM0 && t < XMM0 + NFReg) - k = 1; - else if (t >= Tmp0) - k = KBASE(tmp[t].cls); - bsset(mask[k], t); - } - - for (bp=&fn->rpo[fn->nblk]; bp!=fn->rpo;) { - b = *--bp; - /* invariant: all bocks with bigger rpo got - * their in,out updated. */ - - /* 1. find temporaries in registers at - * the end of the block (put them in v) */ - curi = 0; - s1 = b->s1; - s2 = b->s2; - hd = 0; - if (s1 && s1->id <= n) - hd = s1; - if (s2 && s2->id <= n) - if (!hd || s2->id >= hd->id) - hd = s2; - r = 0; - bszero(v); - if (hd) { - /* back-edge */ - for (k=0; k<2; k++) { - n = k == 0 ? NIReg : NFReg; - bscopy(u, b->out); - bsinter(u, mask[k]); - bscopy(w, u); - bsinter(u, hd->gen); - bsdiff(w, hd->gen); - if ((int)bscount(u) < n) { /* fixme */ - j = bscount(w); /* live through */ - l = hd->nlive[k]; - limit(w, n - (l - j), 0); - bsunion(u, w); - } else - limit(u, n, 0); - bsunion(v, u); - } - } else if (s1) { - liveon(v, b, s1); - if (s2) { - liveon(u, b, s2); - bscopy(w, u); - bsinter(w, v); - bsunion(v, u); - } - limit2(v, 0, 0, w); - } else if (rtype(b->jmp.arg) == RACall) { - /* return */ - r = retregs(b->jmp.arg, 0); - v->t[0] |= r; - } - bscopy(b->out, v); - - /* 2. process the block instructions */ - curi = &insb[NIns]; - for (i=&b->ins[b->nins]; i!=b->ins;) { - i--; - if (regcpy(i)) { - i = dopm(b, i, v); - continue; - } - bszero(w); - if (!req(i->to, R)) { - assert(rtype(i->to) == RTmp); - t = i->to.val; - if (bshas(v, t)) - bsclr(v, t); - else { - /* make sure we have a reg - * for the result */ - bsset(v, t); - bsset(w, t); - } - } - j = opdesc[i->op].nmem; - for (n=0; n<2; n++) - if (rtype(i->arg[n]) == RAMem) - j--; - for (n=0; n<2; n++) - switch (rtype(i->arg[n])) { - case RAMem: - t = i->arg[n].val; - m = &fn->mem[t & AMask]; - if (rtype(m->base) == RTmp) { - bsset(v, m->base.val); - bsset(w, m->base.val); - } - if (rtype(m->index) == RTmp) { - bsset(v, m->index.val); - bsset(w, m->index.val); - } - break; - case RTmp: - t = i->arg[n].val; - lvarg[n] = bshas(v, t); - bsset(v, t); - if (j-- <= 0) - bsset(w, t); - break; - } - bscopy(u, v); - limit2(v, 0, 0, w); - for (n=0; n<2; n++) - if (rtype(i->arg[n]) == RTmp) { - t = i->arg[n].val; - if (!bshas(v, t)) { - /* do not reload if the - * the temporary was dead - */ - if (!lvarg[n]) - bsclr(u, t); - i->arg[n] = slot(t); - } - } - reloads(u, v); - if (!req(i->to, R)) { - t = i->to.val; - store(i->to, tmp[t].slot); - bsclr(v, t); - } - emiti(*i); - r = v->t[0] & (BIT(Tmp0)-1); - if (r) - sethint(v, r); - } - assert(!r || b==fn->start); - - for (p=b->phi; p; p=p->link) { - assert(rtype(p->to) == RTmp); - t = p->to.val; - if (bshas(v, t)) { - bsclr(v, t); - store(p->to, tmp[t].slot); - } else if (bshas(b->in, t)) - /* only if the phi is live */ - p->to = slot(p->to.val); - } - bscopy(b->in, v); - b->nins = &insb[NIns] - curi; - idup(&b->ins, curi, b->nins); - } - - /* align the locals to a 16 byte boundary */ - assert(NAlign == 3); - slot8 += slot8 & 3; - fn->slot += slot8; - - if (debug['S']) { - fprintf(stderr, "\n> Block information:\n"); - for (b=fn->start; b; b=b->link) { - printf("\t%-10s (% 5d) ", b->name, b->loop); - dumpts(b->out, fn->tmp, stdout); - } - fprintf(stderr, "\n> After spilling:\n"); - printfn(fn, stderr); - } -} |