shithub: mc

Download patch

ref: 4c168baca830ab272ab88c41e07fecf4b98fe79b
parent: 538f78b722586f02734d53e8a90d3227c9ad22ed
author: Ori Bernstein <[email protected]>
date: Sat May 24 22:12:46 EDT 2014 

Make things slightly less O(maxreg)ish

   Use a dense vector for the adjacency list. This is slightly
   less stupid than using a sparse bit set.


--- a/6/asm.h
+++ b/6/asm.h
@@ -137,7 +137,7 @@
     Bitset *initial;    /* initial set of locations used by this fn */
 
     size_t *gbits;      /* igraph matrix repr */
-    regid **_gadj;      /* igraph adj set repr */
+    regid **gadj;      /* igraph adj set repr */
     size_t *ngadj;
     int *degree;        /* degree of nodes */
     Loc **aliasmap;     /* mapping of aliases */
--- a/6/ra.c
+++ b/6/ra.c
@@ -352,8 +352,8 @@
 static void alputedge(Isel *s, regid u, regid v)
 {
     s->ngadj[u]++;
-    s->_gadj[u] = xrealloc(s->_gadj[u], s->ngadj[u]*sizeof(regid));
-    s->_gadj[u][s->ngadj[u] - 1] = v;
+    s->gadj[u] = xrealloc(s->gadj[u], s->ngadj[u]*sizeof(regid));
+    s->gadj[u][s->ngadj[u] - 1] = v;
 }
 
 static void addedge(Isel *s, regid u, regid v)
@@ -386,9 +386,9 @@
     gchunks = (maxregid*maxregid)/Sizetbits + 1;
     s->gbits = zalloc(gchunks*sizeof(size_t));
     /* fresh adj list repr. */
-    free(s->_gadj);
+    free(s->gadj);
     free(s->ngadj);
-    s->_gadj = zalloc(maxregid * sizeof(regid*));
+    s->gadj = zalloc(maxregid * sizeof(regid*));
     s->ngadj = zalloc(maxregid * sizeof(size_t));
 
     s->spilled = bsclear(s->spilled);
@@ -573,7 +573,7 @@
     if (before != after) {
         enablemove(s, m);
         for (i = 0; i < s->ngadj[m]; i++) {
-            n = s->_gadj[m][i];
+            n = s->gadj[m][i];
             if (adjavail(s, n))
                 enablemove(s, n);
         }
@@ -615,7 +615,7 @@
     l = lpop(&s->wlsimp, &s->nwlsimp);
     lappend(&s->selstk, &s->nselstk, l);
     for (i = 0; i < s->ngadj[l->reg.id]; i++) {
-        m = s->_gadj[l->reg.id][i];
+        m = s->gadj[l->reg.id][i];
         if (adjavail(s, m))
             decdegree(s, m);
     }
@@ -655,12 +655,12 @@
 
     k = 0;
     for (i = 0; i < s->ngadj[u]; i++) {
-        n = s->_gadj[u][i];
+        n = s->gadj[u][i];
         if (adjavail(s, n) && !istrivial(s, n))
             k++;
     }
     for (i = 0; i < s->ngadj[v]; i++) {
-        n = s->_gadj[v][i];
+        n = s->gadj[v][i];
         if (adjavail(s, n) && !istrivial(s, n))
             k++;
     }
@@ -689,7 +689,7 @@
 
     /* if it is, are the adjacent nodes ok to combine with this? */
     for (i = 0; i < s->ngadj[v]; i++) {
-        t = s->_gadj[v][i];
+        t = s->gadj[v][i];
         if (adjavail(s, t) && !ok(s, t, u))
             return 0;
     }
@@ -727,7 +727,7 @@
     }
 
     for (i = 0; i < s->ngadj[v]; i++) {
-        t = s->_gadj[v][i];
+        t = s->gadj[v][i];
         if (!adjavail(s, t))
             continue;
         if (debugopt['r'] > 2)
@@ -875,7 +875,7 @@
         n = lpop(&s->selstk, &s->nselstk);
 
         for (j = 0; j < s->ngadj[n->reg.id];j++) {
-            l = s->_gadj[n->reg.id][j];
+            l = s->gadj[n->reg.id][j];
             if (debugopt['r'] > 1)
                 printedge(stdout, "paint-edge:", n->reg.id, l);
             w = locmap[getalias(s, l)];