shithub: mc

Download patch

ref: 75cf80b3680ec08c42145aa0f52d7c65dad33766
parent: e8c3f0ca6d64fc775d7a1578a84118b05829715a
author: Ori Bernstein <[email protected]>
date: Thu Jun 14 19:16:02 EDT 2012 

Fix use of ull in igraph.


--- a/8/asm.h
+++ b/8/asm.h
@@ -115,11 +115,18 @@
     Loc *stksz;
 
     /* register allocator state */
-    Insn ***moves;
-    size_t *nmoves;
     Bitset *prepainted; /* locations that need to be a specific colour */
+
     size_t *gbits;      /* igraph matrix repr */
     Bitset **gadj;      /* igraph adj set repr */
+
+    Insn ***moves;
+    size_t *nmoves;
+    Insn **activemoves;
+    size_t nactivemoves;
+
+    Bitset *selstk;
+    Bitset *coalesced;
 
     int *degree;        /* degree of nodes */
 
--- a/8/ra.c
+++ b/8/ra.c
@@ -162,23 +162,24 @@
     return i->op == Imov;
 }
 
-static void gbputedge(size_t *g, int u, int v)
+/* static */ int gbhasedge(size_t *g, size_t u, size_t v)
 {
-    size_t i, j;
+    size_t i;
     i = (maxregid * v) + u;
-    j = (maxregid * u) + v;
-    g[i/Sizetbits] |= 1 << (i % Sizetbits);
-    g[j/Sizetbits] |= 1 << (j % Sizetbits);
+    return g[i/Sizetbits] & (1ULL <<(i % Sizetbits));
 }
 
-/* static */ int gbhasedge(size_t *g, int u, int v)
+static void gbputedge(size_t *g, size_t u, size_t v)
 {
-    size_t i;
+    size_t i, j;
     i = (maxregid * v) + u;
-    return g[i/Sizetbits] & (1 << (i % Sizetbits));
+    j = (maxregid * u) + v;
+    g[i/Sizetbits] |= 1ULL <<(i % Sizetbits);
+    g[j/Sizetbits] |= 1ULL <<(j % Sizetbits);
+    assert(!gbhasedge(g, 5, 5));
 }
 
-static void addedge(Isel *s, int u, int v)
+static void addedge(Isel *s, size_t u, size_t v)
 {
     if (u == v)
 	return;
@@ -214,7 +215,7 @@
     s->gadj = gadj;
 
     s->prepainted = bsclear(s->prepainted);
-    s->degree = xalloc(maxregid * sizeof(int));
+    s->degree = zalloc(maxregid * sizeof(int));
     s->moves = zalloc(maxregid * sizeof(Loc **));
     s->nmoves = zalloc(maxregid * sizeof(size_t));
 }
@@ -264,26 +265,55 @@
     }
 }
 
-static int degree(int id)
+Bitset *adjacent(Isel *s, size_t n)
 {
-    die("Unimplemented");
-    return 42;
+    Bitset *r;
+
+    r = bsdup(s->gadj[n]);
+    bsdiff(r, s->selstk);
+    bsdiff(r, s->coalesced);
+    return r;
 }
 
-static int moverelated(int id)
+size_t nodemoves(Isel *s, size_t nid, Insn ***pil)
 {
-    die("blah");
-    return 42;
+    size_t i, j;
+    size_t n;
+
+    /* FIXME: inefficient. Do I care? */
+    n = 0;
+    for (i = 0; i < s->nmoves[nid]; i++) {
+	for (j = 0; j < s->nactivemoves; j++) {
+	    if (s->activemoves[j] == s->moves[nid][i]) {
+		if (pil)
+		    lappend(pil, &n, s->moves[nid][i]);
+		continue;
+	    }
+	}
+	for (j = 0; j < s->nwlmove; j++) {
+	    if (s->wlmove[j] == s->moves[nid][i]) {
+		if (pil)
+		    lappend(pil, &n, s->moves[nid][i]);
+		continue;
+	    }
+	}
+    }
+    return n;
 }
 
+static int moverelated(Isel *s, size_t n)
+{
+    return nodemoves(s, n, NULL) != 0;
+}
+
 /* static */ void mkworklist(Isel *s)
 {
     size_t i;
 
     for (i = 0; i < maxregid; i++) {
-	if (degree(locmap[i]->reg.id) >= K)
+	if (s->degree[i] >= K)
 	    lappend(&s->wlspill, &s->nwlspill, locmap[i]);
-	else if (moverelated(locmap[i]->reg.id))
+	else if (moverelated(s, i))
 	    lappend(&s->wlfreeze, &s->nwlfreeze, locmap[i]);
 	else
 	    lappend(&s->wlsimp, &s->nwlsimp, locmap[i]);
@@ -290,13 +320,40 @@
     }
 }
 
+void simp(Isel *s)
+{
+}
+
+void coalesce(Isel *s)
+{
+}
+
+void freeze(Isel *s)
+{
+}
+
+void spill(Isel *s)
+{
+}
+
 void regalloc(Isel *s)
 {
     liveness(s);
+    build(s);
     if (debug)
 	dumpasm(s, stdout);
-    build(s);
-    //mkworklist(s);
+    do {
+	if (s->nwlsimp)
+	    simp(s);
+	else if (s->nwlmove)
+	    coalesce(s);
+	else if (s->nwlfreeze)
+	    freeze(s);
+	else if (s->nwlspill)
+	    spill(s);
+	break;
+    } while (s->nwlsimp || s->nwlmove || s->nwlfreeze || s->nwlspill);
+    mkworklist(s);
 }
 
 static void setprint(FILE *fd, Bitset *s)
@@ -336,6 +393,17 @@
     char *sep;
     Asmbb *bb;
 
+    fprintf(fd, "IGRAPH ----- \n");
+    for (i = 0; i < maxregid; i++) {
+	for (j = i; j < maxregid; j++) {
+	    if (gbhasedge(s->gbits, i, j)) {
+		locprint(fd, locmap[i]);
+		fprintf(fd, " -- ");
+		locprint(fd, locmap[j]);
+		fprintf(fd, "\n");
+	    }
+	}
+    }
     fprintf(fd, "ASM -------- \n");
     for (j = 0; j < s->nbb; j++) {
         bb = s->bb[j];