diff options
Diffstat (limited to 'spill.c')
| -rw-r--r-- | spill.c | 507 |
1 files changed, 507 insertions, 0 deletions
@@ -0,0 +1,507 @@ +#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); + } +} |