shithub: mc

Info  •  Files  •  Log  •  Branches

Only add registers from the actual initial set.

    While using all registers as the initial set is correct,
    it leads to a lot of spurious zero-degree nodes in the graphs
    and worklists.

    This makes things hard to debug, as well as slower.

--- a/6/asm.h

+++ b/6/asm.h

@@ -123,11 +123,12 @@

     /* 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 */

     Bitset **gadj;      /* igraph adj set repr */

     int *degree;        /* degree of nodes */

-    Loc **aliasmap;   /* mapping of aliases */

+    Loc **aliasmap;     /* mapping of aliases */

     Loc  **selstk;

     size_t nselstk;

--- a/6/ra.c

+++ b/6/ra.c

@@ -306,7 +306,6 @@

 {

     if (u == v || gbhasedge(s, u, v))

         return;

-    printf("edge %zd -- %zd\n", u, v);

     gbputedge(s, u, v);

     gbputedge(s, v, u);

     if (!bshas(s->prepainted, u)) {

@@ -350,7 +349,7 @@

     s->nrmoves = zalloc(maxregid * sizeof(size_t));

     for (i = 0; i < maxregid; i++)

-        if (locmap[i]->reg.colour)

+        if (bshas(s->prepainted, i))

             s->degree[i] = 1<<16;

 }

@@ -377,6 +376,12 @@

             nu = uses(insn, u);

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

+

             /* moves get special treatment, since we don't want spurious

              * edges between the src and dest */

             if (ismove(insn)) {

@@ -461,9 +466,8 @@

 {

     size_t i;

-    for (i = 0; i < maxregid; i++) {

+    for (i = 0; bsiter(s->initial, &i); i++) {

         if (bshas(s->prepainted, i)) {

-            printf("Prepainted %zd\n", i);

             continue;

         }

         else if (s->degree[i] >= K)

@@ -500,7 +504,6 @@

     assert(n < maxregid);

     d = s->degree[n];

     s->degree[n]--;

-    printf("decdegree %zd (deg = %d)\n", n, d);

     if (d == K) {

         enablemove(s, n);

@@ -517,7 +520,6 @@

     check(s);

     l = lpop(&s->wlsimp, &s->nwlsimp);

     lappend(&s->selstk, &s->nselstk, l);

-    printf("simp %zd\n", l->reg.id);

     for (m = 0; adjiter(s, l->reg.id, &m); m++) {

         decdegree(s, m);

     }

@@ -537,6 +539,7 @@

 static void wladd(Isel *s, regid u)

 {

     size_t i;

+    size_t x;

     if (bshas(s->prepainted, u))

         return;

@@ -546,6 +549,12 @@

         return;

     check(s);

+    if (wlhas(s->wlsimp, s->nwlfreeze, u, &x)) printf("%zd on simp\n", i);

+    if (wlhas(s->wlfreeze, s->nwlfreeze, u, &x)) printf("%zd on freeze\n", i);

+    if (wlhas(s->wlspill, s->nwlspill, u, &x)) printf("%zd on spill\n", i);

+    if (wlhas(s->selstk, s->nselstk, u, &x)) printf("%zd selecst stack\n", i);

+    if (bshas(s->coalesced, u)) printf("%zd coalesced\n", i);

+    if (bshas(s->spilled, u)) printf("%zd on stack\n", i);

     assert(wlhas(s->wlfreeze, s->nwlfreeze, u, &i));

     ldel(&s->wlfreeze, &s->nwlfreeze, i);

     lappend(&s->wlsimp, &s->nwlsimp, locmap[u]);

@@ -661,17 +670,14 @@

     }

     if (u == v) {

-        printf("same\n");

         lappend(&s->mcoalesced, &s->nmcoalesced, m);

         wladd(s, u);

         wladd(s, v);

     } else if (bshas(s->prepainted, v) || gbhasedge(s, u, v)) {

-        printf("prepaint\n");

         lappend(&s->mconstrained, &s->nmconstrained, m);

         wladd(s, u);

         wladd(s, v);

     } else if (combinable(s, u, v)) {

-        printf("combine\n");

         lappend(&s->mcoalesced, &s->nmcoalesced, m);

         combine(s, u, v);

         check(s);

@@ -1033,6 +1039,7 @@

     s->shouldspill = mkbs();

     s->neverspill = mkbs();

+    s->initial = mkbs();

     for (i = 0; i < Nsaved; i++)

         bsput(s->shouldspill, s->calleesave[i]->reg.id);

     spilled = 0;

@@ -1206,7 +1213,7 @@

     size_t idx;

     char foo[5];

-    for (i = 0; i < maxregid; i++) {

+    for (i = 0; bsiter(s->initial, &i); i++) {

         /* check worklists are disjoint */

         n = 0;

         if (bshas(s->prepainted, i)) {