shithub: mc

--- a/8/asm.h

+++ b/8/asm.h

@@ -101,7 +101,7 @@

 /* instruction selection state */

 struct Isel {

-    Cfg  *cfg;

+    Cfg  *cfg;          /* cfg built with nodes */

     Asmbb **bb;         /* 1:1 mappings with the Node bbs in the CFG */

     size_t nbb;

@@ -116,10 +116,11 @@

     /* register allocator state */

     Insn ***moves;

-    Bitset *prepainted; /* locations that need to be a specific colour */

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

-    Bitset **igraph;    /* adjacency set for igraph */

     int *degree;        /* degree of nodes */

     /* worklists */

@@ -167,4 +168,4 @@

 /* useful functions */

 size_t size(Node *n);

 void breakhere();

-void dumpasm(Asmbb **bbs, size_t nbb, FILE *fd);

+void dumpasm(Isel *s, FILE *fd);

--- a/8/ra.c

+++ b/8/ra.c

@@ -2,18 +2,16 @@

 #include <stdio.h>

 #include <stdint.h>

 #include <stdarg.h>

-#include <ctype.h>

-#include <string.h>

 #include <assert.h>

-#include <sys/types.h>

-#include <sys/stat.h>

-#include <fcntl.h>

-#include <unistd.h>

+#include <limits.h>

+#include <string.h>

 #include "parse.h"

 #include "opt.h"

 #include "asm.h"

+#define Sizetbits (CHAR_BIT*sizeof(size_t)) /* used in graph reprs */

 typedef struct Usage Usage;

 struct Usage {

     int l[Maxarg + 1];

@@ -164,36 +162,80 @@

     return i->op == Imov;

+static void gbputedge(size_t *g, int u, int v)

+{

+    size_t i, j;

+    i = (maxregid * v) + u;

+    j = (maxregid * u) + v;

+    g[i/Sizetbits] |= 1 << (i % Sizetbits);

+    g[j/Sizetbits] |= 1 << (j % Sizetbits);

+}

+/* static */ int gbhasedge(size_t *g, int u, int v)

+{

+    size_t i;

+    i = (maxregid * v) + u;

+    return g[i/Sizetbits] & (1 << (i % Sizetbits));

+}

 static void addedge(Isel *s, int u, int v)

     if (u == v)

 	return;

-    locprint(stdout, locmap[u]);

-    fprintf(stdout, " -- ");

-    locprint(stdout, locmap[v]);

-    fprintf(stdout, "\n");

+    gbputedge(s->gbits, u, v);

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

+	bsput(s->gadj[u], v);

+	s->degree[u]++;

+    }

+    if (!bshas(s->prepainted, v)) {

+	bsput(s->gadj[v], u);

+	s->degree[v]++;

+    }

+void setup(Isel *s)

+{

+    Bitset **gadj;

+    size_t gchunks;

+    size_t i;

+    free(s->gbits);

+    gchunks = (maxregid*maxregid)/Sizetbits + 1;

+    s->gbits = zalloc(gchunks*sizeof(size_t));

+    /* fresh adj list repr. try to avoid reallocating all the bitsets */

+    gadj = zalloc(maxregid * sizeof(Bitset*));

+    if (s->gadj)

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

+	    gadj[i] = bsclear(s->gadj[i]);

+    else

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

+	    gadj[i] = mkbs();

+    free(s->gadj);

+    s->gadj = gadj;

+    s->prepainted = bsclear(s->prepainted);

+    s->degree = xalloc(maxregid * sizeof(int));

+    s->moves = zalloc(maxregid * sizeof(Loc **));

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

+}

 static void build(Isel *s)

-    /* uses/defs */

     long u[2*Maxarg], d[2*Maxarg];

     size_t nu, nd;

-    /* indexes */

     size_t i, k;

     ssize_t j;

-    /* liveness */

     Bitset *live;

-    /* convenience vars */

     Asmbb **bb;

     size_t nbb;

     Insn *insn;

     size_t l;

+    setup(s);

+    /* set up convenience vars */

     bb = s->bb;

     nbb = s->nbb;

-    s->moves = zalloc(maxregid * sizeof(Loc **));

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

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

     for (i = 0; i < nbb; i++) {

 	live = bsdup(bb[i]->liveout);

@@ -252,7 +294,7 @@

     liveness(s);

     if (debug)

-	dumpasm(s->bb, s->nbb, stdout);

+	dumpasm(s, stdout);

     build(s);

     //mkworklist(s);

@@ -288,7 +330,7 @@

     fprintf(fd, "\n");

-void dumpasm(Asmbb **bbs, size_t nbb, FILE *fd)

+void dumpasm(Isel *s, FILE *fd)

     size_t i, j;

     char *sep;

@@ -295,8 +337,8 @@

     Asmbb *bb;

     fprintf(fd, "ASM -------- \n");

-    for (j = 0; j < nbb; j++) {

-        bb = bbs[j];

+    for (j = 0; j < s->nbb; j++) {

+        bb = s->bb[j];

         fprintf(fd, "\n");

         fprintf(fd, "Bb: %d labels=(", bb->id);

         sep = "";

--- a/parse/bitset.c

+++ b/parse/bitset.c

@@ -7,7 +7,7 @@

 #include "parse.h"

-#define Uintbits (CHAR_BIT*sizeof(int))

+#define Sizetbits (CHAR_BIT*sizeof(size_t)) /* used in graph reprs */

 static void eqsz(Bitset *a, Bitset *b)

@@ -62,7 +62,7 @@

     n = 0;

     for (i = 0; i < bs->nchunks; i++)

         for (j = 1; j < sizeof(size_t)*CHAR_BIT; j++)

-            if (bs->chunks[i] & 1 << j)

+            if (bs->chunks[i] & 1ULL << j)

                 n++;

     return n;

@@ -85,7 +85,7 @@

  * is a bit slow. This is mostly an aid to iterate over it. */

 size_t bsmax(Bitset *bs)

-    return bs->nchunks*sizeof(size_t)*CHAR_BIT;

+    return bs->nchunks*Sizetbits;

 void delbs(Bitset *bs)

@@ -97,27 +97,26 @@

 void bsput(Bitset *bs, size_t elt)

     size_t sz;

-    assert(elt < 100);

-    if (elt >= bs->nchunks*Uintbits) {

-        sz = (elt/Uintbits)+1;

+    if (elt >= bs->nchunks*Sizetbits) {

+        sz = (elt/Sizetbits)+1;

         bs->chunks = zrealloc(bs->chunks, bs->nchunks*sizeof(size_t), sz*sizeof(size_t));

         bs->nchunks = sz;

-    bs->chunks[elt/Uintbits] |= 1 << (elt % Uintbits);

+    bs->chunks[elt/Sizetbits] |= 1ULL << (elt % Sizetbits);

 void bsdel(Bitset *bs, size_t elt)

-    if (elt < bs->nchunks*Uintbits)

-        bs->chunks[elt/Uintbits] &= ~(1 << (elt % Uintbits));

+    if (elt < bs->nchunks*Sizetbits)

+        bs->chunks[elt/Sizetbits] &= ~(1ULL << (elt % Sizetbits));

 int bshas(Bitset *bs, size_t elt)

-    if (elt >= bs->nchunks*Uintbits)

+    if (elt >= bs->nchunks*Sizetbits)

         return 0;

     else

-        return bs->chunks[elt/Uintbits] & (1 << (elt % Uintbits));

+        return bs->chunks[elt/Sizetbits] & (1ULL << (elt % Sizetbits));

 void bsunion(Bitset *a, Bitset *b)

--- a/parse/parse.h

+++ b/parse/parse.h

@@ -54,7 +54,7 @@

 struct Bitset {

     size_t nchunks;

-    uint *chunks;

+    size_t *chunks;

};

 struct Htab {