shithub: mc

Info  •  Files  •  Log  •  Branches

Optimize nodemoves()

    Maintain sets for the instruction, so that we don't
    have to do lots of O(n) lookups. Those are slow.

--- a/6/asm.h

+++ b/6/asm.h

@@ -84,6 +84,7 @@

 };

 struct Insn {

+    size_t uid;

     AsmOp op;

     Loc *args[Maxarg];

     size_t nargs;

@@ -156,11 +157,13 @@

     Insn **mfrozen;

     size_t nmfrozen;

+    Bitset *mactiveset;

     Insn **mactive;

     size_t nmactive;

     /* worklists */

+    Bitset *wlmoveset;

     Insn **wlmove;

     size_t nwlmove;

--- a/6/isel.c

+++ b/6/isel.c

@@ -145,10 +145,12 @@

     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;

--- a/6/ra.c

+++ b/6/ra.c

@@ -410,6 +410,8 @@

     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 @@

                 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 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,22 +522,10 @@

     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;

 }

@@ -541,7 +532,15 @@

 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 @@

             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 @@

     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 @@

         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 @@

         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);