diff options
| -rw-r--r-- | Makefile | 2 | ||||
| -rw-r--r-- | all.h | 6 | ||||
| -rw-r--r-- | load.c | 408 |
3 files changed, 414 insertions, 2 deletions
diff --git a/Makefile b/Makefile index 19bf777..fc649f8 100644 --- a/Makefile +++ b/Makefile @@ -4,7 +4,7 @@ ABI = sysv V = @ OBJDIR = obj -SRC = main.c util.c parse.c cfg.c mem.c ssa.c alias.c copy.c fold.c live.c $(ABI).c isel.c spill.c rega.c emit.c +SRC = main.c util.c parse.c cfg.c mem.c ssa.c alias.c load.c copy.c fold.c live.c $(ABI).c isel.c spill.c rega.c emit.c OBJ = $(SRC:%.c=$(OBJDIR)/%.o) CFLAGS += -Wall -Wextra -std=c99 -g -pedantic diff --git a/all.h b/all.h index 943480a..5784d9a 100644 --- a/all.h +++ b/all.h @@ -530,7 +530,8 @@ void bsdiff(BSet *, BSet *); int bsequal(BSet *, BSet *); int bsiter(BSet *, int *); -static inline int bshas(BSet *bs, uint elt) +static inline int +bshas(BSet *bs, uint elt) { assert(elt < bs->nt * NBit); return (bs->t[elt/NBit] & BIT(elt%NBit)) != 0; @@ -561,6 +562,9 @@ void fillalias(Fn *); int alias(Ref, int, Ref, int, int *, Fn *); int escapes(Ref, Fn *); +/* load.c */ +void loadopt(Fn *); + /* ssa.c */ void filluse(Fn *); void fillpreds(Fn *); diff --git a/load.c b/load.c new file mode 100644 index 0000000..a6bd68e --- /dev/null +++ b/load.c @@ -0,0 +1,408 @@ +#include "all.h" + +#define MASK(w) (BIT(8*(w)-1)*2-1) /* must work when w==8 */ + +typedef struct Loc Loc; +typedef struct Slice Slice; +typedef struct Insert Insert; + + +struct Loc { + enum { + LRoot, /* right above the original load */ + LLoad, /* inserting a load is allowed */ + LNoLoad, /* only scalar operations allowed */ + } type; + uint off; + Blk *blk; +}; + +struct Slice { + Ref ref; + short sz; + short cls; /* load class */ +}; + +struct Insert { + uint isphi:1; + uint num:31; + int bid; + uint off; + union { + Ins ins; + struct { + Slice m; + Phi *p; + } phi; + } new; +}; + +static Fn *curf; +static uint inum; /* current insertion number */ +static Insert *ilog; /* global insertion log */ +static uint nlog; /* number of entries in the log */ + +static int +loadsz(Ins *l) +{ + switch (l->op) { + case Oloadsb: case Oloadub: return 1; + case Oloadsh: case Oloaduh: return 2; + case Oloadsw: case Oloaduw: return 4; + case Oload: return KWIDE(l->cls) ? 8 : 4; + } + die("unreachable"); +} + +static int +storesz(Ins *s) +{ + switch (s->op) { + case Ostoreb: return 1; + case Ostoreh: return 2; + case Ostorew: case Ostores: return 4; + case Ostorel: case Ostored: return 8; + } + die("unreachable"); +} + +static Ref +iins(int cls, int op, Ref a0, Ref a1, Loc *l) +{ + Insert *ist; + + vgrow(&ilog, ++nlog); + ist = &ilog[nlog-1]; + ist->isphi = 0; + ist->num = inum++; + ist->bid = l->blk->id; + ist->off = l->off; + ist->new.ins = (Ins){op, R, {a0, a1}, cls}; + return ist->new.ins.to = newtmp("ld", cls, curf); +} + +static void +cast(Ref *r, int cls, Loc *l) +{ + int cls0; + + if (rtype(*r) == RCon) + return; + assert(rtype(*r) == RTmp); + cls0 = curf->tmp[r->val].cls; + if (cls0 == cls || (cls == Kw && cls0 == Kl)) + return; + assert(!KWIDE(cls0) || KWIDE(cls)); + if (KWIDE(cls) == KWIDE(cls0)) + *r = iins(cls, Ocast, *r, R, l); + else { + assert(cls == Kl); + if (cls0 == Ks) + *r = iins(Kw, Ocast, *r, R, l); + *r = iins(Kl, Oextuw, *r, R, l); + } +} + +static inline void +mask(int cls, Ref *r, bits msk, Loc *l) +{ + cast(r, cls, l); + *r = iins(cls, Oand, *r, getcon(msk, curf), l); +} + +static Ref +load(Slice sl, bits msk, Loc *l) +{ + Ref r; + int ld, cls, all; + + ld = (int[]){ + [1] = Oloadub, + [2] = Oloaduh, + [4] = Oloaduw, + [8] = Oload + }[sl.sz]; + all = msk == MASK(sl.sz); + if (all) + cls = sl.cls; + else + cls = sl.sz > 4 ? Kl : Kw; + r = iins(cls, ld, sl.ref, R, l); + if (!all) + mask(cls, &r, msk, l); + return r; +} + +/* returns a ref containing the contents of the slice + * passed as argument, all the bits set to 0 in the + * mask argument are zeroed in the result; + * the returned ref has an integer class when the + * mask does not cover all the bits of the slice, + * otherwise, it has class sl.cls + * the procedure returns R when it fails */ +static Ref +def(Slice sl, bits msk, Blk *b, Ins *i, Loc *il) +{ + Blk *bp; + bits msk1, msks; + int off, cls, cls1, op, sz, ld; + uint np, oldl, oldt; + Ref r, r1; + Phi *p; + Insert *ist; + Loc l; + + /* invariants: + * -1- b dominates il->blk; so we can use + * temporaries of b in il->blk + * -2- if il->type != LNoLoad, then il->blk + * postdominates the original load; so it + * is safe to load in il->blk + * -3- if il->type != LNoLoad, then b + * postdominates il->blk (and by 2, the + * original load) + */ + assert(dom(b, il->blk)); + oldl = nlog; + oldt = curf->ntmp; + if (0) { + Load: + curf->ntmp = oldt; + nlog = oldl; + if (il->type != LLoad) + return R; + return load(sl, msk, il); + } + + if (!i) + i = &b->ins[b->nins]; + cls = sl.sz > 4 ? Kl : Kw; + msks = MASK(sl.sz); + + while (i > b->ins) { + --i; + if (req(i->to, sl.ref) + || (i->op == Ocall && escapes(sl.ref, curf))) + goto Load; + ld = isload(i->op); + if (ld) { + sz = loadsz(i); + r1 = i->arg[0]; + r = i->to; + } else if (isstore(i->op)) { + sz = storesz(i); + r1 = i->arg[1]; + r = i->arg[0]; + } else + continue; + switch (alias(sl.ref, sl.sz, r1, sz, &off, curf)) { + case MustAlias: + if (off < 0) { + off = -off; + msk1 = (MASK(sz) << 8*off) & msks; + op = Oshl; + } else { + msk1 = (MASK(sz) >> 8*off) & msks; + op = Oshr; + } + if ((msk1 & msk) == 0) + break; + if (off) { + cls1 = cls; + if (op == Oshr && off + sl.sz > 4) + cls1 = Kl; + cast(&r, cls1, il); + r1 = getcon(8*off, curf); + r = iins(cls1, op, r, r1, il); + } + if ((msk1 & msk) != msk1 || off + sz < sl.sz) + mask(cls, &r, msk1 & msk, il); + if ((msk & ~msk1) != 0) { + r1 = def(sl, msk & ~msk1, b, i, il); + if (req(r1, R)) + goto Load; + r = iins(cls, Oor, r, r1, il); + } + if (msk == msks) + cast(&r, sl.cls, il); + return r; + case MayAlias: + if (ld) + break; + else + goto Load; + case NoAlias: + break; + default: + die("unreachable"); + } + } + + for (ist=ilog; ist<&ilog[nlog]; ++ist) + if (ist->isphi && ist->bid == b->id) + if (req(ist->new.phi.m.ref, sl.ref)) + if (ist->new.phi.m.sz == sl.sz) { + r = ist->new.phi.p->to; + if (msk != msks) + mask(cls, &r, msk, il); + else + cast(&r, sl.cls, il); + return r; + } + + for (p=b->phi; p; p=p->link) + if (req(p->to, sl.ref)) + /* scanning predecessors in that + * case would be unsafe */ + goto Load; + + if (b->npred == 0) + goto Load; + if (b->npred == 1) { + bp = b->pred[0]; + assert(bp->loop == il->blk->loop); + l = *il; + if (bp->s2) + l.type = LNoLoad; + r1 = def(sl, msk, bp, 0, &l); + if (req(r1, R)) + goto Load; + return r1; + } + + r = newtmp("ld", sl.cls, curf); + p = alloc(sizeof *p); + vgrow(&ilog, ++nlog); + ist = &ilog[nlog-1]; + ist->isphi = 1; + ist->bid = b->id; + ist->new.phi.m = sl; + ist->new.phi.p = p; + p->to = r; + p->cls = sl.cls; + p->narg = b->npred; + for (np=0; np<b->npred; ++np) { + bp = b->pred[np]; + if (!bp->s2 + && il->type != LNoLoad + && bp->loop < il->blk->loop) + l.type = LLoad; + else + l.type = LNoLoad; + l.blk = bp; + l.off = bp->nins; + r1 = def(sl, msks, bp, 0, &l); + if (req(r1, R)) + goto Load; + p->arg[np] = r1; + p->blk[np] = bp; + } + if (msk != msks) + mask(cls, &r, msk, il); + return r; +} + +static int +icmp(const void *pa, const void *pb) +{ + Insert *a, *b; + int c; + + a = (Insert *)pa; + b = (Insert *)pb; + if ((c = a->bid - b->bid)) + return c; + if (a->isphi && b->isphi) + return 0; + if (a->isphi) + return -1; + if (b->isphi) + return +1; + if ((c = a->off - b->off)) + return c; + return a->num - b->num; +} + +/* require rpo ssa alias */ +void +loadopt(Fn *fn) +{ + Ins *i, *ib; + Blk *b; + int n, sz; + uint ni, ext, nt; + Insert *ist; + Slice sl; + Loc l; + + curf = fn; + ilog = vnew(0, sizeof ilog[0], emalloc); + nlog = 0; + inum = 0; + for (b=fn->start; b; b=b->link) + for (i=b->ins; i<&b->ins[b->nins]; ++i) { + if (!isload(i->op)) + continue; + sz = loadsz(i); + sl = (Slice){i->arg[0], sz, i->cls}; + l = (Loc){LRoot, i-b->ins, b}; + i->arg[1] = def(sl, MASK(sz), b, i, &l); + } + qsort(ilog, nlog, sizeof ilog[0], icmp); + vgrow(&ilog, nlog+1); + ilog[nlog].bid = fn->nblk; /* add a sentinel */ + ib = vnew(0, sizeof(Ins), emalloc); + for (ist=ilog, n=0; n<fn->nblk; ++n) { + b = fn->rpo[n]; + for (; ist->bid == n && ist->isphi; ++ist) { + ist->new.phi.p->link = b->phi; + b->phi = ist->new.phi.p; + } + ni = 0; + nt = 0; + for (;;) { + if (ist->bid == n && ist->off == ni) + i = &ist++->new.ins; + else { + if (ni == b->nins) + break; + i = &b->ins[ni++]; + if (isload(i->op) + && !req(i->arg[1], R)) { + ext = Oextsb + i->op - Oloadsb; + switch (i->op) { + default: + die("unreachable"); + case Oloadsb: + case Oloadub: + case Oloadsh: + case Oloaduh: + i->op = ext; + break; + case Oloadsw: + case Oloaduw: + if (i->cls == Kl) { + i->op = ext; + break; + } + case Oload: + i->op = Ocopy; + break; + } + i->arg[0] = i->arg[1]; + i->arg[1] = R; + } + } + vgrow(&ib, ++nt); + ib[nt-1] = *i; + } + b->nins = nt; + idup(&b->ins, ib, nt); + } + vfree(ib); + vfree(ilog); + if (debug['M']) { + fprintf(stderr, "\n> After load elimination:\n"); + printfn(fn, stderr); + } +} |