ref: 720ffc701948aa87040d5d57a8028063f949bec7
parent: ce58af0c3497db7f716dc1912009c8b9da55b0a5
author: Ori Bernstein <[email protected]>
date: Thu Jun 14 15:43:27 EDT 2012
Add in igraph build() function.
--- a/8/asm.h
+++ b/8/asm.h
@@ -1,4 +1,5 @@
#define Maxarg 4
+#define K 4 /* 4 general purpose regs with all modes available */
typedef struct Insn Insn;
typedef struct Loc Loc;
@@ -101,21 +102,38 @@
/* instruction selection state */
struct Isel {Cfg *cfg;
- Asmbb **bb;
+
+ Asmbb **bb; /* 1:1 mappings with the Node bbs in the CFG */
size_t nbb;
Asmbb *curbb;
- Node *ret;
- Htab *locs; /* decl id => int stkoff */
- Htab *globls; /* decl id => char *globlname */
+ Node *ret; /* we store the return into here */
+ Htab *locs; /* decl id => int stkoff */
+ Htab *globls; /* decl id => char *globlname */
+
/* increased when we spill */
Loc *stksz;
/* register allocator state */
Insn ***moves;
+ Bitset *prepainted; /* locations that need to be a specific colour */
size_t *nmoves;
+
+ Bitset **igraph; /* adjacency set for igraph */
+ int *degree; /* degree of nodes */
+
+ /* worklists */
Insn **wlmove;
size_t nwlmove;
+
+ Loc **wlspill;
+ size_t nwlspill;
+
+ Loc **wlfreeze;
+ size_t nwlfreeze;
+
+ Loc **wlsimp;
+ size_t nwlsimp;
};
/* entry points */
@@ -123,8 +141,8 @@
void gen(Node *file, char *out);
/* location generation */
-extern int maxregid;
-extern Loc **loctab; /* mapping from reg id => Loc * */
+extern size_t maxregid;
+extern Loc **locmap; /* mapping from reg id => Loc * */
Loc *loclbl(Node *lbl);
Loc *locstrlbl(char *lbl);
@@ -144,8 +162,6 @@
extern Mode regmodes[]; /* mode table */
void regalloc(Isel *s);
-size_t uses(Insn *i, long *uses);
-size_t defs(Insn *i, long *defs);
/* useful functions */
--- a/8/ra.c
+++ b/8/ra.c
@@ -36,7 +36,7 @@
#undef Def
};
-size_t uses(Insn *insn, long *u)
+static size_t uses(Insn *insn, long *u)
{size_t i, j;
int k;
@@ -75,7 +75,7 @@
return j;
}
-size_t defs(Insn *insn, long *d)
+static size_t defs(Insn *insn, long *d)
{size_t i, j;
int k;
@@ -102,7 +102,7 @@
return j;
}
-void usedef(Asmbb *bb)
+static void udcalc(Asmbb *bb)
{/* up to 2 registers per memloc, so
* 2*Maxarg is the maximum number of
@@ -124,7 +124,7 @@
}
}
-void liveness(Isel *s)
+static void liveness(Isel *s)
{Bitset *old;
Asmbb **bb;
@@ -135,7 +135,7 @@
bb = s->bb;
nbb = s->nbb;
for (i = 0; i < nbb; i++) {- usedef(s->bb[i]);
+ udcalc(s->bb[i]);
bb[i]->livein = bsclear(bb[i]->livein);
bb[i]->liveout = bsclear(bb[i]->liveout);
}
@@ -146,16 +146,13 @@
for (i = 0; i < nbb; i++) {old = bsdup(bb[i]->liveout);
/* liveout[b] = U(s in succ) livein[s] */
- for (j = 0; j < bsmax(bb[i]->succ); j++) {- if (!bshas(bb[i]->succ, j))
- continue;
+ for (j = 0; bsiter(bb[i]->succ, &j); j++)
bsunion(bb[i]->liveout, bb[j]->livein);
- }
/* livein[b] = use[b] U (out[b] \ def[b]) */
bb[i]->livein = bsclear(bb[i]->livein);
bsunion(bb[i]->livein, bb[i]->liveout);
- bsdiff(bb[i]->liveout, bb[i]->def);
- bsunion(bb[i]->liveout, bb[i]->use);
+ bsdiff(bb[i]->livein, bb[i]->def);
+ bsunion(bb[i]->livein, bb[i]->use);
if (!changed)
changed = !bseq(old, bb[i]->liveout);
}
@@ -162,16 +159,22 @@
}
}
-int ismove(Insn *i)
+static int ismove(Insn *i)
{return i->op == Imov;
}
-void addedge(Isel *s, int u, int v)
+static void addedge(Isel *s, int u, int v)
{+ if (u == v)
+ return;
+ locprint(stdout, locmap[u]);
+ fprintf(stdout, " -- ");
+ locprint(stdout, locmap[v]);
+ fprintf(stdout, "\n");
}
-void build(Isel *s)
+static void build(Isel *s)
{/* uses/defs */
long u[2*Maxarg], d[2*Maxarg];
@@ -185,12 +188,13 @@
Asmbb **bb;
size_t nbb;
Insn *insn;
- uint l;
+ size_t l;
bb = s->bb;
nbb = s->nbb;
s->moves = zalloc(maxregid * sizeof(Loc **));
s->nmoves = zalloc(maxregid * sizeof(size_t));
+ //s->graph = zalloc(maxregid * sizeof(size_t));
for (i = 0; i < nbb; i++) {live = bsdup(bb[i]->liveout);
for (j = bb[i]->ni - 1; j >= 0; j--) {@@ -216,9 +220,34 @@
addedge(s, d[k], l);
}
}
+}
+static int degree(int id)
+{+ die("Unimplemented");+ return 42;
}
+static int moverelated(int id)
+{+ die("blah");+ return 42;
+}
+
+/* static */ void mkworklist(Isel *s)
+{+ size_t i;
+
+ for (i = 0; i < maxregid; i++) {+ if (degree(locmap[i]->reg.id) >= K)
+ lappend(&s->wlspill, &s->nwlspill, locmap[i]);
+ else if (moverelated(locmap[i]->reg.id))
+ lappend(&s->wlfreeze, &s->nwlfreeze, locmap[i]);
+ else
+ lappend(&s->wlsimp, &s->nwlsimp, locmap[i]);
+ }
+}
+
void regalloc(Isel *s)
{liveness(s);
@@ -225,9 +254,10 @@
if (debug)
dumpasm(s->bb, s->nbb, stdout);
build(s);
+ //mkworklist(s);
}
-void setprint(FILE *fd, Bitset *s)
+static void setprint(FILE *fd, Bitset *s)
{char *sep;
size_t i;
@@ -242,7 +272,7 @@
fprintf(fd, "\n");
}
-void locsetprint(FILE *fd, Bitset *s)
+static void locsetprint(FILE *fd, Bitset *s)
{char *sep;
size_t i;
@@ -251,7 +281,7 @@
for (i = 0; i < bsmax(s); i++) { if (bshas(s, i)) {fprintf(fd, "%s", sep);
- locprint(fd, loctab[i]);
+ locprint(fd, locmap[i]);
sep = ",";
}
}
--- a/8/regalloc.c
+++ b/8/regalloc.c
@@ -70,8 +70,8 @@
return locstrlbl(lbl->lbl.name);
}
-Loc **loctab = NULL;
-int maxregid = 0;
+Loc **locmap = NULL;
+size_t maxregid = 0;
Loc *locreg(Mode m)
{@@ -81,8 +81,8 @@
l->type = Locreg;
l->mode = m;
l->reg.id = maxregid++;
- loctab = xrealloc(loctab, maxregid * sizeof(Loc*));
- loctab[l->reg.id] = l;
+ locmap = xrealloc(locmap, maxregid * sizeof(Loc*));
+ locmap[l->reg.id] = l;
return l;
}
--- a/parse/bitset.c
+++ b/parse/bitset.c
@@ -17,9 +17,9 @@
sz = a->nchunks;
else
sz = b->nchunks;
- a->chunks = zrealloc(a->chunks, a->nchunks*sizeof(uint), sz*sizeof(uint));
+ a->chunks = zrealloc(a->chunks, a->nchunks*sizeof(size_t), sz*sizeof(size_t));
a->nchunks = sz;
- b->chunks = zrealloc(b->chunks, a->nchunks*sizeof(uint), sz*sizeof(uint));
+ b->chunks = zrealloc(b->chunks, a->nchunks*sizeof(size_t), sz*sizeof(size_t));
b->nchunks = sz;
}
@@ -29,7 +29,7 @@
bs = xalloc(sizeof(Bitset));
bs->nchunks = 1;
- bs->chunks = zalloc(1*sizeof(uint));
+ bs->chunks = zalloc(1*sizeof(size_t));
return bs;
}
@@ -39,8 +39,8 @@
bs = xalloc(sizeof(Bitset));
bs->nchunks = a->nchunks;
- bs->chunks = xalloc(a->nchunks*sizeof(uint));
- memcpy(bs->chunks, a->chunks, a->nchunks*sizeof(uint));
+ bs->chunks = xalloc(a->nchunks*sizeof(size_t));
+ memcpy(bs->chunks, a->chunks, a->nchunks*sizeof(size_t));
return bs;
}
@@ -61,15 +61,15 @@
n = 0;
for (i = 0; i < bs->nchunks; i++)
- for (j = 1; j < sizeof(uint)*CHAR_BIT; j++)
+ for (j = 1; j < sizeof(size_t)*CHAR_BIT; j++)
if (bs->chunks[i] & 1 << j)
n++;
return n;
}
-int bsiter(Bitset *bs, uint *elt)
+int bsiter(Bitset *bs, size_t *elt)
{- uint i;
+ size_t i;
for (i = *elt; i < bsmax(bs); i++) { if (bshas(bs, i)) {@@ -85,7 +85,7 @@
* is a bit slow. This is mostly an aid to iterate over it. */
size_t bsmax(Bitset *bs)
{- return bs->nchunks*sizeof(uint)*CHAR_BIT;
+ return bs->nchunks*sizeof(size_t)*CHAR_BIT;
}
void delbs(Bitset *bs)
@@ -94,24 +94,25 @@
free(bs);
}
-void bsput(Bitset *bs, uint elt)
+void bsput(Bitset *bs, size_t elt)
{size_t sz;
+ assert(elt < 100);
if (elt >= bs->nchunks*Uintbits) {sz = (elt/Uintbits)+1;
- bs->chunks = zrealloc(bs->chunks, bs->nchunks*sizeof(uint), sz*sizeof(uint));
+ bs->chunks = zrealloc(bs->chunks, bs->nchunks*sizeof(size_t), sz*sizeof(size_t));
bs->nchunks = sz;
}
bs->chunks[elt/Uintbits] |= 1 << (elt % Uintbits);
}
-void bsdel(Bitset *bs, uint elt)
+void bsdel(Bitset *bs, size_t elt)
{if (elt < bs->nchunks*Uintbits)
bs->chunks[elt/Uintbits] &= ~(1 << (elt % Uintbits));
}
-int bshas(Bitset *bs, uint elt)
+int bshas(Bitset *bs, size_t elt)
{if (elt >= bs->nchunks*Uintbits)
return 0;
--- a/parse/parse.h
+++ b/parse/parse.h
@@ -227,15 +227,15 @@
Bitset *bsdup(Bitset *bs);
Bitset *bsclear(Bitset *bs);
void delbs(Bitset *bs);
-void bsput(Bitset *bs, uint elt);
-void bsdel(Bitset *bs, uint elt);
+void bsput(Bitset *bs, size_t elt);
+void bsdel(Bitset *bs, size_t elt);
void bsunion(Bitset *a, Bitset *b);
void bsintersect(Bitset *a, Bitset *b);
void bsdiff(Bitset *a, Bitset *b);
-int bshas(Bitset *bs, uint elt);
+int bshas(Bitset *bs, size_t elt);
int bseq(Bitset *a, Bitset *b);
int bsissubset(Bitset *set, Bitset *sub);
-int bsiter(Bitset *bs, uint *elt);
+int bsiter(Bitset *bs, size_t *elt);
size_t bsmax(Bitset *bs);
size_t bscount(Bitset *bs);