diff options
| -rw-r--r-- | lisc/lisc.h | 4 | ||||
| -rw-r--r-- | lisc/live.c | 77 | ||||
| -rw-r--r-- | lisc/main.c | 5 |
3 files changed, 49 insertions, 37 deletions
diff --git a/lisc/lisc.h b/lisc/lisc.h index 84022a0..f44a0ab 100644 --- a/lisc/lisc.h +++ b/lisc/lisc.h @@ -130,7 +130,8 @@ struct Blk { Blk **pred; uint npred; - Bits in, out; + Bits in, out, gen; + int nlive; int loop; char name[NString]; int id; @@ -175,5 +176,6 @@ void filllive(Fn *); void isel(Fn *); /* spill.c */ +int bcnt(Bits *); void fillcost(Fn *); void spill(Fn *); diff --git a/lisc/live.c b/lisc/live.c index 4569db9..dd544c1 100644 --- a/lisc/live.c +++ b/lisc/live.c @@ -1,10 +1,14 @@ #include "lisc.h" -static inline void -bset(Bits *b, Ref r) +static void +bset(Ref r, Blk *b, int *nlv) { if (rtype(r) == RSym) - BSET(*b, r.val); + if (!BGET(b->in, r.val)) { + ++*nlv; + BSET(b->in, r.val); + BSET(b->gen, r.val); + } } /* liveness analysis @@ -16,51 +20,56 @@ filllive(Fn *f) Blk *b; Ins *i; Phi *p; - int z, n, chg; + int z, n, chg, nlv; uint a; - Bits *kill, *use, *k, *u, bt; + Bits tb; assert(f->ntmp <= NBit*BITS); - kill = alloc(f->nblk * sizeof kill[0]); - use = alloc(f->nblk * sizeof use[0]); - for (b=f->start; b; b=b->link) { - memset(&b->in, 0, sizeof(Bits)); - memset(&b->out, 0, sizeof(Bits)); - } for (b=f->start; b; b=b->link) { - k = &kill[b->id]; - u = &use[b->id]; - for (p=b->phi; p; p=p->link) { - for (a=0; a<p->narg; a++) - bset(&p->blk[a]->out, p->arg[a]); - bset(k, p->to); - } - for (i=b->ins; i-b->ins < b->nins; i++) { - bset(k, i->to); - bset(u, i->arg[0]); - bset(u, i->arg[1]); - } - bset(u, b->jmp.arg); + b->in = (Bits){{0}}; + b->out = (Bits){{0}}; + b->gen = (Bits){{0}}; + b->nlive = 0; } -Again: - chg = 0; + chg = 1; + if (0) + Again: + chg = 0; for (n=f->nblk-1; n>=0; n--) { b = f->rpo[n]; - bt = b->out; + + tb = b->out; if (b->s1) for (z=0; z<BITS; z++) b->out.t[z] |= b->s1->in.t[z]; if (b->s2) for (z=0; z<BITS; z++) b->out.t[z] |= b->s2->in.t[z]; - chg |= memcmp(&b->out, &bt, sizeof(Bits)) != 0; - k = &kill[n]; - u = &use[n]; - for (z=0; z<BITS; z++) - b->in.t[z] = (b->out.t[z]|u->t[z]) & ~k->t[z]; + chg |= memcmp(&b->out, &tb, sizeof(Bits)) != 0; + + b->in = b->out; + nlv = bcnt(&b->in); + bset(b->jmp.arg, b, &nlv); + b->nlive = nlv; + for (i=&b->ins[b->nins]; i!=b->ins;) { + i--; + if (!req(i->to, R)) { + nlv -= BGET(b->in, i->to.val); + BCLR(b->in, i->to.val); + } + bset(i->arg[0], b, &nlv); + bset(i->arg[1], b, &nlv); + if (nlv > b->nlive) + b->nlive = nlv; + } + + for (p=b->phi; p; p=p->link) { + BCLR(b->in, p->to.val); + for (a=0; a<p->narg; a++) + if (rtype(p->arg[a]) == RSym) + BSET(p->blk[a]->out, p->arg[a].val); + } } if (chg) goto Again; - free(kill); - free(use); } diff --git a/lisc/main.c b/lisc/main.c index bab3276..c0c147b 100644 --- a/lisc/main.c +++ b/lisc/main.c @@ -59,12 +59,13 @@ main(int ac, char *av[]) filllive(fn); for (b=fn->start; b; b=b->link) { printf("> Block %s\n", b->name); - printf("\t in: ["); + printf("\t in: ["); dumprset(&b->in, fn); printf(" ]\n"); - printf("\tout: ["); + printf("\tout: ["); dumprset(&b->out, fn); printf(" ]\n"); + printf("\tnlive: %d\n", b->nlive); } pr = 0; break; |