shithub: mc

Download patch

ref: a340b8b9e6b3645eccb5ee3e00cb92c974029c68
parent: 6007029a7fcb1184f5f3d698ed55f96fa4812ac1
author: Ori Bernstein <[email protected]>
date: Tue Jun 3 20:09:37 EDT 2014 

Optimize the register allocator.

    We don't need to iterate through lists to figure out which
    node a list is on. Store it in the node.


--- a/6/asm.h
+++ b/6/asm.h
@@ -59,6 +59,7 @@
 struct Loc {
     Loctype type; /* the type of loc */
     Mode mode;    /* the mode of this location */
+    void *list;
     union {
         char *lbl;  /* for Loclbl, Loclitl */
         struct {    /* for Locreg */
@@ -113,7 +114,6 @@
     Bitset *liveout;  /* variables live on exit from BB */
 };
 
-
 /* instruction selection state */
 struct Isel {
     Cfg  *cfg;          /* cfg built with nodes */
@@ -133,8 +133,6 @@
     Loc *calleesave[Nsaved];
 
     /* register allocator state */
-    Bitset *prepainted; /* locations that need to be a specific colour */
-    Bitset *initial;    /* initial set of locations used by this fn */
 
     size_t *gbits;      /* igraph matrix repr */
     regid **gadj;      /* igraph adj set repr */
@@ -142,11 +140,6 @@
     int *degree;        /* degree of nodes */
     Loc **aliasmap;     /* mapping of aliases */
 
-    Loc  **selstk;
-    size_t nselstk;
-
-    Bitset *coalesced;
-    Bitset *spilled;
     Bitset *shouldspill;        /* the first registers we should try to spill */
     Bitset *neverspill;        /* registers we should never spill */
 
@@ -179,6 +172,14 @@
 
     Loc **wlsimp;
     size_t nwlsimp;
+
+    Loc  **selstk;
+    size_t nselstk;
+
+    Bitset *coalesced;
+    Bitset *spilled;
+    Bitset *prepainted; /* locations that need to be a specific colour */
+    Bitset *initial;    /* initial set of locations used by this fn */
 };
 
 /* entry points */
--- a/6/ra.c
+++ b/6/ra.c
@@ -306,7 +306,7 @@
     assert(gbhasedge(s, u, v) && gbhasedge(s, v, u));
 }
 
-static int wlhas(Loc **wl, size_t nwl, regid v, size_t *idx)
+static int wlfind(Loc **wl, size_t nwl, regid v, size_t *idx)
 {
     size_t i;
 
@@ -356,6 +356,19 @@
     s->gadj[u][s->ngadj[u] - 1] = v;
 }
 
+static void wlput(Loc ***wl, size_t *nwl, Loc *l)
+{
+    lappend(wl, nwl, l);
+    l->list = wl;
+}
+
+static void wlputset(Bitset *bs, regid r)
+{
+    bsput(bs, r);
+    locmap[r]->list = bs;
+}
+
+
 static void addedge(Isel *s, regid u, regid v)
 {
     if (u == v || gbhasedge(s, u, v))
@@ -435,10 +448,14 @@
             nd = defs(insn, d);
 
             /* add these to the initial set */
-            for (k = 0; k < nu; k++)
-                bsput(s->initial, u[k]);
-            for (k = 0; k < nd; k++)
-                bsput(s->initial, d[k]);
+            for (k = 0; k < nu; k++) {
+                if (!bshas(s->prepainted, u[k]))
+                    wlputset(s->initial, u[k]);
+            }
+            for (k = 0; k < nd; k++) {
+                if (!bshas(s->prepainted, d[k]))
+                    wlputset(s->initial, d[k]);
+            }
 
             /* moves get special treatment, since we don't want spurious
              * edges between the src and dest */
@@ -479,13 +496,10 @@
 
 static int adjavail(Isel *s, regid r)
 {
-    size_t i;
-
     if (bshas(s->coalesced, r))
         return 0;
-    for (i = 0; i < s->nselstk; i++)
-        if (r == s->selstk[i]->reg.id)
-            return 0;
+    if (locmap[r]->list == &s->selstk)
+        return 0;
     return 1;
 }
 
@@ -532,11 +546,11 @@
         if (bshas(s->prepainted, i))
             continue;
         else if (!istrivial(s, i))
-            lappend(&s->wlspill, &s->nwlspill, locmap[i]);
+            wlput(&s->wlspill, &s->nwlspill, locmap[i]);
         else if (moverelated(s, i))
-            lappend(&s->wlfreeze, &s->nwlfreeze, locmap[i]);
+            wlput(&s->wlfreeze, &s->nwlfreeze, locmap[i]);
         else
-            lappend(&s->wlsimp, &s->nwlsimp, locmap[i]);
+            wlput(&s->wlsimp, &s->nwlsimp, locmap[i]);
         locmap[i]->reg.colour = 0;
     }
 }
@@ -589,19 +603,19 @@
          * that the node is already on the list that we'd be
          * moving it to.
          */
-        found = wlhas(s->wlspill, s->nwlspill, m, &idx);
+        found = wlfind(s->wlspill, s->nwlspill, m, &idx);
         if (found)
             ldel(&s->wlspill, &s->nwlspill, idx);
         if (moverelated(s, m)) {
             if (!found)
-                assert(wlhas(s->wlfreeze, s->nwlfreeze, m, &idx));
+                assert(wlfind(s->wlfreeze, s->nwlfreeze, m, &idx));
             else
-                lappend(&s->wlfreeze, &s->nwlfreeze, locmap[m]);
+                wlput(&s->wlfreeze, &s->nwlfreeze, locmap[m]);
         } else {
             if (!found)
-                assert(wlhas(s->wlsimp, s->nwlsimp, m, &idx));
+                assert(wlfind(s->wlsimp, s->nwlsimp, m, &idx));
             else
-                lappend(&s->wlsimp, &s->nwlsimp, locmap[m]);
+                wlput(&s->wlsimp, &s->nwlsimp, locmap[m]);
         }
     }
 }
@@ -613,7 +627,7 @@
     size_t i;
 
     l = lpop(&s->wlsimp, &s->nwlsimp);
-    lappend(&s->selstk, &s->nselstk, l);
+    wlput(&s->selstk, &s->nselstk, l);
     for (i = 0; i < s->ngadj[l->reg.id]; i++) {
         m = s->gadj[l->reg.id][i];
         if (adjavail(s, m))
@@ -642,9 +656,9 @@
     if (!istrivial(s, u))
         return;
 
-    assert(wlhas(s->wlfreeze, s->nwlfreeze, u, &i));
+    assert(wlfind(s->wlfreeze, s->nwlfreeze, u, &i));
     ldel(&s->wlfreeze, &s->nwlfreeze, i);
-    lappend(&s->wlsimp, &s->nwlsimp, locmap[u]);
+    wlput(&s->wlsimp, &s->nwlsimp, locmap[u]);
 }
 
 static int conservative(Isel *s, regid u, regid v)
@@ -705,12 +719,12 @@
 
     if (debugopt['r'] > 2)
         printedge(stdout, "combining:", u, v);
-    if (wlhas(s->wlfreeze, s->nwlfreeze, v, &idx))
+    if (wlfind(s->wlfreeze, s->nwlfreeze, v, &idx))
         ldel(&s->wlfreeze, &s->nwlfreeze, idx);
-    else if (wlhas(s->wlspill, s->nwlspill, v, &idx)) {
+    else if (wlfind(s->wlspill, s->nwlspill, v, &idx)) {
         ldel(&s->wlspill, &s->nwlspill, idx);
     }
-    bsput(s->coalesced, v);
+    wlputset(s->coalesced, v);
     s->aliasmap[v] = locmap[u];
 
     /* nodemoves[u] = nodemoves[u] U nodemoves[v] */
@@ -735,9 +749,9 @@
         addedge(s, t, u);
         decdegree(s, t);
     }
-    if (!istrivial(s, u) && wlhas(s->wlfreeze, s->nwlfreeze, u, &idx)) {
+    if (!istrivial(s, u) && wlfind(s->wlfreeze, s->nwlfreeze, u, &idx)) {
         ldel(&s->wlfreeze, &s->nwlfreeze, idx);
-        lappend(&s->wlspill, &s->nwlspill, locmap[u]);
+        wlput(&s->wlspill, &s->nwlspill, locmap[u]);
     }
 }
 
@@ -806,10 +820,10 @@
             mldel(&s->wlmove, &s->nwlmove, m);
         lappend(&s->mfrozen, &s->nmfrozen, m);
         if (!nodemoves(s, v->reg.id, NULL) && istrivial(s, v->reg.id)) {
-            if (!wlhas(s->wlfreeze, s->nwlfreeze, v->reg.id, &idx))
+            if (!wlfind(s->wlfreeze, s->nwlfreeze, v->reg.id, &idx))
                 die("Reg %zd not in freeze wl\n", v->reg.id);
             ldel(&s->wlfreeze, &s->nwlfreeze, idx);
-            lappend(&s->wlsimp, &s->nwlsimp, v);
+            wlput(&s->wlsimp, &s->nwlsimp, v);
         }
 
     }
@@ -821,7 +835,7 @@
     Loc *l;
 
     l = lpop(&s->wlfreeze, &s->nwlfreeze);
-    lappend(&s->wlsimp, &s->nwlsimp, l);
+    wlput(&s->wlsimp, &s->nwlsimp, l);
     freezemoves(s, l);
 }
 
@@ -852,7 +866,7 @@
         }
     }
     assert(m != NULL);
-    lappend(&s->wlsimp, &s->nwlsimp, m);
+    wlput(&s->wlsimp, &s->nwlsimp, m);
     freezemoves(s, m);
 }
 
@@ -898,7 +912,7 @@
         }
         if (!found) {
             spilled = 1;
-            bsput(s->spilled, n->reg.id);
+            wlputset(s->spilled, n->reg.id);
         }
     }
     for (l = 0; bsiter(s->coalesced, &l); l++) {