summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorOri Bernstein <ori@eigenstate.org>2014-06-18 10:52:29 -0400
committerOri Bernstein <ori@eigenstate.org>2014-06-18 10:52:29 -0400
commitd602a0b9372004e85db60153d4579938c1022f06 (patch)
tree72171d447806034f561f2c288cb311ff9d2dae41
parent05d7bc89b7b144997e91c764c9aa0bbdddc0dcac (diff)
downloadmc-d602a0b9372004e85db60153d4579938c1022f06.tar.gz
Optimize nodemoves()
Maintain sets for the instruction, so that we don't have to do lots of O(n) lookups. Those are slow.
-rw-r--r--6/asm.h3
-rw-r--r--6/isel.c2
-rw-r--r--6/ra.c59
3 files changed, 38 insertions, 26 deletions
diff --git a/6/asm.h b/6/asm.h
index e631ede..4c1d8a7 100644
--- a/6/asm.h
+++ b/6/asm.h
@@ -84,6 +84,7 @@ struct Loc {
};
struct Insn {
+ size_t uid;
AsmOp op;
Loc *args[Maxarg];
size_t nargs;
@@ -156,11 +157,13 @@ struct Isel {
Insn **mfrozen;
size_t nmfrozen;
+ Bitset *mactiveset;
Insn **mactive;
size_t nmactive;
/* worklists */
+ Bitset *wlmoveset;
Insn **wlmove;
size_t nwlmove;
diff --git a/6/isel.c b/6/isel.c
index 6e3f323..f4f3da3 100644
--- a/6/isel.c
+++ b/6/isel.c
@@ -145,10 +145,12 @@ static Insn *mkinsnv(AsmOp op, va_list ap)
Loc *l;
Insn *i;
int n;
+ static size_t insnid;
n = 0;
i = malloc(sizeof(Insn));
i->op = op;
+ i->uid = insnid++;
while ((l = va_arg(ap, Loc*)) != NULL)
i->args[n++] = l;
i->nargs = n;
diff --git a/6/ra.c b/6/ra.c
index 56e6119..c72329a 100644
--- a/6/ra.c
+++ b/6/ra.c
@@ -410,6 +410,8 @@ static void setup(Isel *s)
s->gadj = zalloc(maxregid * sizeof(regid*));
s->ngadj = zalloc(maxregid * sizeof(size_t));
+ s->mactiveset = bsclear(s->mactiveset);
+ s->wlmoveset = bsclear(s->wlmoveset);
s->spilled = bsclear(s->spilled);
s->coalesced = bsclear(s->coalesced);
lfree(&s->wlspill, &s->nwlspill);
@@ -483,6 +485,7 @@ static void build(Isel *s)
for (k = 0; k < nd; k++)
lappend(&s->rmoves[d[k]], &s->nrmoves[d[k]], insn);
lappend(&s->wlmove, &s->nwlmove, insn);
+ bsput(s->wlmoveset, insn->uid);
}
/* live = live U def(i) */
for (k = 0; k < nd; k++)
@@ -511,7 +514,7 @@ static int adjavail(Isel *s, regid r)
static size_t nodemoves(Isel *s, regid n, Insn ***pil)
{
- size_t i, j;
+ size_t i;
size_t count;
/* FIXME: inefficient. Do I care? */
@@ -519,29 +522,25 @@ static size_t nodemoves(Isel *s, regid n, Insn ***pil)
if (pil)
*pil = NULL;
for (i = 0; i < s->nrmoves[n]; i++) {
- for (j = 0; j < s->nmactive; j++) {
- if (s->mactive[j] == s->rmoves[n][i]) {
- if (pil)
- lappend(pil, &count, s->rmoves[n][i]);
- else
- count++;
- }
- }
- for (j = 0; j < s->nwlmove; j++) {
- if (s->wlmove[j] == s->rmoves[n][i]) {
- if (pil)
- lappend(pil, &count, s->rmoves[n][i]);
- else
- count++;
- }
- }
+ if (bshas(s->mactiveset, s->rmoves[n][i]->uid))
+ lappend(pil, &count, s->rmoves[n][i]);
+ if (bshas(s->wlmoveset, s->rmoves[n][i]->uid))
+ lappend(pil, &count, s->rmoves[n][i]);
}
return count;
}
static int moverelated(Isel *s, regid n)
{
- return nodemoves(s, n, NULL) != 0;
+ size_t i;
+
+ for (i = 0; i < s->nrmoves[n]; i++) {
+ if (bshas(s->mactiveset, s->rmoves[n][i]->uid))
+ return 1;
+ if (bshas(s->wlmoveset, s->rmoves[n][i]->uid))
+ return 1;
+ }
+ return 0;
}
static void mkworklist(Isel *s)
@@ -574,6 +573,8 @@ static void enablemove(Isel *s, regid n)
if (il[i] == s->mactive[j]) {
ldel(&s->mactive, &s->nmactive, j);
lappend(&s->wlmove, &s->nwlmove, il[i]);
+ bsdel(s->mactiveset, il[i]->uid);
+ bsput(s->wlmoveset, il[i]->uid);
}
}
}
@@ -782,6 +783,7 @@ static void coalesce(Isel *s)
regid u, v, tmp;
m = lpop(&s->wlmove, &s->nwlmove);
+ bsdel(s->wlmoveset, m->uid);
u = getalias(s, m->args[0]->reg.id);
v = getalias(s, m->args[1]->reg.id);
@@ -805,16 +807,20 @@ static void coalesce(Isel *s)
wladd(s, u);
} else {
lappend(&s->mactive, &s->nmactive, m);
+ bsput(s->mactiveset, m->uid);
}
}
-static int mldel(Insn ***ml, size_t *nml, Insn *m)
+static int mldel(Insn ***ml, size_t *nml, Bitset *bs, Insn *m)
{
size_t i;
- for (i = 0; i < *nml; i++) {
- if (m == (*ml)[i]) {
- ldel(ml, nml, i);
- return 1;
+ if (bshas(bs, m->uid)) {
+ bsdel(bs, m->uid);
+ for (i = 0; i < *nml; i++) {
+ if (m == (*ml)[i]) {
+ ldel(ml, nml, i);
+ return 1;
+ }
}
}
return 0;
@@ -837,10 +843,11 @@ static void freezemoves(Isel *s, Loc *u)
else
v = locmap[getalias(s, m->args[0]->reg.id)];
- if (!mldel(&s->mactive, &s->nmactive, m))
- mldel(&s->wlmove, &s->nwlmove, m);
+ if (!mldel(&s->mactive, &s->nmactive, s->mactiveset, m))
+ mldel(&s->wlmove, &s->nwlmove, s->wlmoveset, m);
+
lappend(&s->mfrozen, &s->nmfrozen, m);
- if (!nodemoves(s, v->reg.id, NULL) && istrivial(s, v->reg.id)) {
+ if (!moverelated(s, v->reg.id) && istrivial(s, v->reg.id)) {
if (!wlfind(s->wlfreeze, s->nwlfreeze, v->reg.id, &idx))
die("Reg %zd not in freeze wl\n", v->reg.id);
wldel(s, &s->wlfreeze, &s->nwlfreeze, idx);