commit 987b3def3394583321fee4543df9db76b9299bc6
parent 3e104e532b49038f94ec9770bbe3e765472cf613
Author: Quentin Carbonneaux <quentin.carbonneaux@yale.edu>
Date: Thu, 25 Feb 2016 15:20:27 -0500
start conversion to dynamic bitsets
Diffstat:
4 files changed, 85 insertions(+), 63 deletions(-)
diff --git 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
@@ -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
@@ -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
@@ -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;
