diff options
Diffstat (limited to 'lisc/spill.c')
| -rw-r--r-- | lisc/spill.c | 145 |
1 files changed, 141 insertions, 4 deletions
diff --git a/lisc/spill.c b/lisc/spill.c index e9a6219..cd34931 100644 --- a/lisc/spill.c +++ b/lisc/spill.c @@ -172,6 +172,7 @@ slot(int t) { int s; + assert(sym[t].type == STmp); s = sym[t].spill; if (!s) { s = 1 + ns++; @@ -217,9 +218,11 @@ limit(Bits *b, int k, Bits *fst) res = (Bits){{0}}; for (i=0; i<k && i<nt; i++) BSET(res, tmp[i]); - if (curi) - for (; i<nt; i++) + for (; i<nt; i++) { + slot(tmp[i]); + if (curi) emit(OLoad, SYM(tmp[i]), slot(tmp[i]), R); + } return res; } @@ -251,6 +254,92 @@ setloc(Ref *pr, Bits *v, Bits *w) BSET(*w, t); } +static Blk *elist; /* edge list created by edge() */ +static int ne; /* length of elist */ + +static Blk * +edge(Blk *b, Blk **ps, Ins *ins, int nins) +{ + Blk *b1, *s; + Ins *ib; + Phi *p; + uint a; + + s = *ps; + /* first, try adding at the beginning + * or end of b or s + * + * todo, hey, is this overkill? + */ + if (b->s1 == s && !b->s2) { + ib = alloc((nins + b->nins) * sizeof(Ins)); + memcpy(ib, b->ins, b->nins * sizeof(Ins)); + memcpy(&ib[b->nins], ins, nins * sizeof(Ins)); + free(b->ins); + b->nins += nins; + b->ins = ib; + return 0; + } + if (s->npred == 1) { + ib = alloc((nins + s->nins) * sizeof(Ins)); + memcpy(ib, ins, nins * sizeof(Ins)); + memcpy(&ib[nins], s->ins, s->nins * sizeof(Ins)); + free(s->ins); + s->nins += nins; + s->ins = ib; + return 0; + } + /* last resort alloc a block */ + b1 = blocka(); + b1->link = elist; + elist = b1; + ne++; + sprintf(b1->name, "%s_%s", b->name, s->name); + ib = alloc(nins * sizeof(Ins)); + memcpy(ib, ins, nins * sizeof(Ins)); + b1->ins = ib; + b1->nins = nins; + b1->jmp.type = JJmp; + b1->s1 = s; + *ps = b1; + /* fix phis and predecessors */ + for (p=s->phi; p; p=p->link) + for (a=0; a<p->narg; a++) + if (p->blk[a] == b) + p->blk[a] = b1; + for (a=0; a<s->npred; a++) + if (s->pred[a] == b) + s->pred[a] = b1; + return b1; +} + +static void +reload(Blk *b, Blk **ps) +{ + Bits v; + Blk *s, *e; + int z, t; + Ref sr; + + s = *ps; + curi = insb; + v = s->in; + for (z=0; z<BITS; z++) + v.t[z] &= ~b->out.t[z]; + for (t=Tmp0; t<ntmp; t++) + if (BGET(v, t)) { + sr = SLOT(sym[t].spill); + assert(sr.val); + *curi++ = (Ins){OLoad, SYM(t), {sr, R}}; + } + if (curi != insb) { + e = edge(b, ps, insb, curi-insb); + if (e) { + e->loop = s->loop/s->npred; + e->out = v; + } + } +} /* spill code insertion * requires spill costs, rpo, liveness @@ -270,11 +359,14 @@ void spill(Fn *fn) { Blk *b, *s1, *s2, *hd; - int n, z, l; + int n, z, l, t; Bits v, w; Ins *i; int j, s; Phi *p; + Ref sr; + Ins *ib; + uint a; ns = 0; sym = fn->sym; @@ -378,7 +470,52 @@ spill(Fn *fn) memcpy(b->ins, curi, b->nins * sizeof(Ins)); for (p=b->phi; p; p=p->link) - BCLR(v, p->to.val); + if (BGET(v, p->to.val)) + BCLR(v, p->to.val); + else + p->to = slot(p->to.val); b->in = v; } + + /* 3. fix phi nodes and + * insert reload code between blocks */ + ne = 0; + elist = 0; + for (b=fn->start;; b=b->link) { + if (b->s1) + reload(b, &b->s1); + if (b->s2) + reload(b, &b->s2); + curi = insb; + for (p=b->phi; p; p=p->link) { + t = p->to.val; + sr = SLOT(sym[t].spill); + if (sr.val) + *curi++ = (Ins){OStore, R, {SYM(t), sr}}; + for (a=0; a<p->narg; a++) { + if (rtype(p->arg[a]) != RSym) + continue; + t = p->arg[a].val; + if (!BGET(p->blk[a]->out, t)) { + sr = SLOT(sym[t].spill); + assert(sr.val); + p->arg[a] = sr; + } + } + } + if (curi != insb) { + n = curi - insb; + ib = alloc((b->nins+n) * sizeof(Ins)); + memcpy(ib, insb, n * sizeof(Ins)); + memcpy(&ib[n], b->ins, b->nins * sizeof(Ins)); + free(b->ins); + b->nins += n; + b->ins = ib; + } + if (!b->link) { + b->link = elist; + fn->nblk += ne; + break; + } + } } |