diff options
| -rw-r--r-- | lisc/Makefile | 2 | ||||
| -rw-r--r-- | lisc/lisc.h | 23 | ||||
| -rw-r--r-- | lisc/live.c | 81 | ||||
| -rw-r--r-- | lisc/util.c | 42 |
4 files changed, 85 insertions, 63 deletions
diff --git a/lisc/Makefile b/lisc/Makefile index 560fd4f..d293227 100644 --- a/lisc/Makefile +++ b/lisc/Makefile @@ -1,5 +1,5 @@ BIN = lisc -OBJ = main.o util.o parse.o mem.o ssa.o copy.o live.o isel.o spill.o rega.o emit.o +OBJ = main.o util.o parse.o live.o # mem.o ssa.o copy.o live.o isel.o spill.o rega.o emit.o CFLAGS = -Wall -Wextra -std=c99 -g -pedantic diff --git a/lisc/lisc.h b/lisc/lisc.h index 19cc639..441f2cb 100644 --- a/lisc/lisc.h +++ b/lisc/lisc.h @@ -9,7 +9,7 @@ typedef unsigned short ushort; typedef unsigned long ulong; typedef struct Bits Bits; -typedef struct Bitset BSet; +typedef struct BSet BSet; typedef struct Ref Ref; typedef struct OpDesc OpDesc; typedef struct Ins Ins; @@ -85,6 +85,11 @@ enum { NBit = 64, }; +struct BSet { + uint nt; + ulong *t; +}; + struct Bits { ulong t[BITS]; }; @@ -336,7 +341,7 @@ struct Blk { Blk **pred; uint npred; - Bits in, out, gen; + BSet in[1], out[1], gen[1]; int nlive[2]; int loop; char name[NString]; @@ -468,6 +473,18 @@ Ref newtmp(char *, Fn *); Ref getcon(int64_t, Fn *); void addcon(Con *, Con *); +void bsinit(BSet *, uint); +void bszero(BSet *); +uint bscount(BSet *); +int bshas(BSet *, uint); +void bsset(BSet *, uint); +void bsclr(BSet *, uint); +void bscopy(BSet *, BSet *); +void bsunion(BSet *, BSet *); +void bsinter(BSet *, BSet *); +void bsdiff(BSet *, BSet *); +int bsiter(BSet *, uint *); + /* parse.c */ extern OpDesc opdesc[NOp]; void parse(FILE *, void (Dat *), void (Fn *)); @@ -487,7 +504,7 @@ void ssa(Fn *); void copy(Fn *); /* live.c */ -Bits liveon(Blk *, Blk *); +void liveon(BSet *, Blk *, Blk *); void filllive(Fn *); /* isel.c */ diff --git a/lisc/live.c b/lisc/live.c index 3718642..dceb7e2 100644 --- a/lisc/live.c +++ b/lisc/live.c @@ -1,12 +1,22 @@ #include "lisc.h" -Bits -liveon(Blk *b, Blk *s) +void +liveon(BSet *v, Blk *b, Blk *s) { - Bits v; Phi *p; uint a; + bsunion(v, s->in); + for (p=s->phi; p; p=p->link) { + bsclr(v, p->to.val); + for (a=0; a<p->narg; a++) + if (p->blk[a] == b) + if (rtype(p->arg[a]) == RTmp) + bsset(v, p->arg[a].val); + } + return; + + /* v = s->in; for (p=s->phi; p; p=p->link) { BCLR(v, p->to.val); @@ -16,6 +26,7 @@ liveon(Blk *b, Blk *s) BSET(v, p->arg[a].val); } return v; + */ } static int @@ -56,11 +67,11 @@ bset(Ref r, Blk *b, int *nlv, short *phi, Tmp *tmp) if (rtype(r) != RTmp) return; - BSET(b->gen, r.val); + bsset(b->gen, r.val); phifix(r.val, phi, tmp); - if (!BGET(b->in, r.val)) { + if (!bshas(b->in, r.val)) { nlv[KBASE(tmp[r.val].cls)]++; - BSET(b->in, r.val); + bsset(b->in, r.val); } } @@ -72,41 +83,40 @@ filllive(Fn *f) { Blk *b; Ins *i; - int k, t, z, m[2], n, chg, nlv[2]; + int k, t, m[2], n, chg, nlv[2]; short *phi; - Bits u, v; + BSet u[1], v[1]; Mem *ma; - assert(f->ntmp <= NBit*BITS); + bsinit(u, f->ntmp); /* todo, free those */ + bsinit(v, f->ntmp); phi = emalloc(f->ntmp * sizeof phi[0]); for (b=f->start; b; b=b->link) { - BZERO(b->in); - BZERO(b->out); - BZERO(b->gen); + bsinit(b->in, f->ntmp); + bsinit(b->out, f->ntmp); + bsinit(b->gen, f->ntmp); } chg = 1; Again: for (n=f->nblk-1; n>=0; n--) { b = f->rpo[n]; - u = b->out; - if (b->s1) { - v = liveon(b, b->s1); - for (z=0; z<BITS; z++) - b->out.t[z] |= v.t[z]; - } - if (b->s2) { - v = liveon(b, b->s2); - for (z=0; z<BITS; z++) - b->out.t[z] |= v.t[z]; - } - chg |= memcmp(&b->out, &u, sizeof(Bits)); + bscopy(u, b->out); + if (b->s1) + liveon(b->out, b, b->s1); + if (b->s2) + liveon(b->out, b, b->s2); + + if (bsequal(b->out, u)) + continue; + else + chg = 1; memset(phi, 0, f->ntmp * sizeof phi[0]); memset(nlv, 0, sizeof nlv); - b->in = b->out; + bscopy(b->in, b->out); for (t=0; t<f->ntmp; t++) - if (BGET(b->in, t)) { + if (bshas(b->in, t)) { phifix(t, phi, f->tmp); nlv[KBASE(f->tmp[t].cls)]++; } @@ -114,26 +124,25 @@ Again: for (k=0; k<2; k++) b->nlive[k] = nlv[k]; for (i=&b->ins[b->nins]; i!=b->ins;) { - if ((--i)->op == OCall - && rtype(i->arg[1]) == RACall) { - b->in.t[0] &= ~calldef(*i, m); + if ((--i)->op == OCall && rtype(i->arg[1]) == RACall) { + b->in->t[0] &= ~calldef(*i, m); for (k=0; k<2; k++) nlv[k] -= m[k]; if (nlv[0] + NISave > b->nlive[0]) b->nlive[0] = nlv[0] + NISave; if (nlv[1] + NFSave > b->nlive[1]) b->nlive[1] = nlv[1] + NFSave; - b->in.t[0] |= calluse(*i, m); + b->in->t[0] |= calluse(*i, m); for (k=0; k<2; k++) nlv[k] += m[k]; } if (!req(i->to, R)) { assert(rtype(i->to) == RTmp); t = i->to.val; - if (BGET(b->in, i->to.val)) + if (bshas(b->in, i->to.val)) nlv[KBASE(f->tmp[t].cls)]--; - BSET(b->gen, t); - BCLR(b->in, t); + bsset(b->gen, t); + bsclr(b->in, t); phi[phitmp(t, f->tmp)] = 0; } for (k=0; k<2; k++) @@ -162,11 +171,11 @@ Again: fprintf(stderr, "\n> Liveness analysis:\n"); for (b=f->start; b; b=b->link) { fprintf(stderr, "\t%-10sin: ", b->name); - dumpts(&b->in, f->tmp, stderr); + dumpts(b->in, f->tmp, stderr); fprintf(stderr, "\t out: "); - dumpts(&b->out, f->tmp, stderr); + dumpts(b->out, f->tmp, stderr); fprintf(stderr, "\t gen: "); - dumpts(&b->gen, f->tmp, stderr); + dumpts(b->gen, f->tmp, stderr); fprintf(stderr, "\t live: "); fprintf(stderr, "%d %d\n", b->nlive[0], b->nlive[1]); } diff --git a/lisc/util.c b/lisc/util.c index bfddbff..4f0298c 100644 --- a/lisc/util.c +++ b/lisc/util.c @@ -3,11 +3,6 @@ typedef struct Bitset Bitset; typedef struct Vec Vec; -struct Bitset { - uint nchunk; - ulong *chunk; -}; - struct Vec { ulong mag; size_t esz; @@ -244,8 +239,8 @@ void bsinit(BSet *bs, uint n) { n = (n + NBit-1) / NBit; - bs->nchunk = n; - bs->chunk = alloc(n * sizeof bs->chunk[0]); + bs->nt = n; + bs->t = alloc(n * sizeof bs->t[0]); } uint @@ -254,9 +249,9 @@ bscount(BSet *bs) uint i, j, n; n = 0; - for (i=0; i<bs->nchunk; i++) + for (i=0; i<bs->nt; i++) for (j=0; j<NBit; j++) - if (bs->chunk[i] & BIT(j)) + if (bs->t[i] & BIT(j)) n++; return n; } @@ -264,41 +259,42 @@ bscount(BSet *bs) static inline uint bsmax(BSet *bs) { - return bs->nchunk * NBit; + return bs->nt * NBit; } int bshas(BSet *bs, uint elt) { assert(elt < bsmax(bs)); - return (bs->chunk[elt/NBit] & BIT(elt%NBit)) != 0; + return (bs->t[elt/NBit] & BIT(elt%NBit)) != 0; } void bsset(BSet *bs, uint elt) { assert(elt < bsmax(bs)); - bs->chunk[elt/NBit] |= BIT(elt%NBit); + bs->t[elt/NBit] |= BIT(elt%NBit); } void bsclr(BSet *bs, uint elt) { assert(elt < bsmax(bs)); - bs->chunk[elt/NBit] &= ~BIT(elt%NBit); + bs->t[elt/NBit] &= ~BIT(elt%NBit); } -#define BSOP(f, op) \ - void \ - f(BSet *a, BSet *b) \ - { \ - uint i; \ - \ - assert(a->nchunk == b->nchunk); \ - for (i=0; i<a->nchunk; i++) \ - a->chunk[i] op b->chunk[i]; \ +#define BSOP(f, op) \ + void \ + f(BSet *a, BSet *b) \ + { \ + uint i; \ + \ + assert(a->nt == b->nt); \ + for (i=0; i<a->nt; i++) \ + a->t[i] op b->t[i]; \ } +BSOP(bscopy, =) BSOP(bsunion, |=) BSOP(bsinter, &=) BSOP(bsdiff, &= ~) @@ -321,7 +317,7 @@ bsiter(BSet *bs, uint *elt) uint i; for (i = *elt; i < bsmax(bs); i++) { - while (i < bsmax(bs) && !bs->chunk[i/NBit]) + while (i < bsmax(bs) && !bs->t[i/NBit]) i = (i + NBit) & -NBit; if (bshas(bs, i)) { *elt = i; |