shithub: mc

Info  •  Files  •  Log  •  Branches

Fix build function.

    We should now try to build a correct interference graph, modulo
    actually building the graph.

--- a/8/asm.h

+++ b/8/asm.h

@@ -110,6 +110,12 @@

     /* increased when we spill */

     Loc *stksz;

+

+    /* register allocator state */

+    Insn ***moves;

+    size_t *nmoves;

+    Insn **wlmove;

+    size_t nwlmove;

 };

 /* entry points */

@@ -117,6 +123,9 @@

 void gen(Node *file, char *out);

 /* location generation */

+extern int maxregid;

+extern Loc **loctab; /* mapping from reg id => Loc * */

+

 Loc *loclbl(Node *lbl);

 Loc *locstrlbl(char *lbl);

 Loc *locreg(Mode m);

@@ -131,12 +140,12 @@

 void iprintf(FILE *fd, Insn *insn);

 /* register allocation */

+extern char *regnames[]; /* name table */

+extern Mode regmodes[];  /* mode table */

+

 void regalloc(Isel *s);

 size_t uses(Insn *i, long *uses);

 size_t defs(Insn *i, long *defs);

-extern char *regnames[];

-extern Mode regmodes[];

-extern Loc **loctab;

 /* useful functions */

--- a/8/insns.def

+++ b/8/insns.def

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

 Insn(Iadd,      "\tadd%t %r,%x\n",              Use(.l={1,2}),			Def(.l={2}))

 Insn(Isub,      "\tsub%t %r,%x\n",              Use(.l={1,2}),			Def(.l={2}))

 Insn(Imul,      "\tmul%t %r\n",              	Use(.l={1},.r={Reax}),		Def(.r={Reax,Redx}))

-Insn(Idiv,      "\tdiv%t %r\n",              	Use(.l={1},.r={Reax,Redx}),	Def(.l={Reax,Redx}))

+Insn(Idiv,      "\tdiv%t %r\n",              	Use(.l={1},.r={Reax,Redx}),	Def(.r={Reax,Redx}))

 Insn(Ineg,      "\tneg%t %r\n",              	Use(.l={1}),			Def(.l={1}))

 Insn(Iand,      "\tand%t %r,%x\n",              Use(.l={1,2}),			Def(.l={2}))

 Insn(Ior,       "\tor%t %r,%x\n",               Use(.l={1,2}),			Def(.l={2}))

--- a/8/ra.c

+++ b/8/ra.c

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

     int k;

     j = 0;

-    /* Add all the registers dsed and defined. Ddplicates

+    /* Add all the registers dsed and defined. Duplicates

      * in this list are fine, since they're being added to

      * a set anyways */

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

@@ -162,6 +162,71 @@

     }

 }

+int ismove(Insn *i)

+{

+    return i->op == Imov;

+}

+

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

+{

+}

+

+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;

+    uint l;

+

+    bb = s->bb;

+    nbb = s->nbb;

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

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

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

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

+	for (j = bb[i]->ni - 1; j >= 0; j--) {

+	    insn = bb[i]->il[j];

+	    nu = uses(insn, u);

+	    nd = defs(insn, d);

+	    if (ismove(insn)) {

+		/* live \= uses(i) */

+		for (k = 0; k < nu; k++)

+		    bsdel(live, u[k]);

+

+		for (k = 0; k < nu; k++)

+		    lappend(&s->moves[u[k]], &s->nmoves[u[k]], insn);

+		for (k = 0; k < nd; k++)

+		    lappend(&s->moves[d[k]], &s->nmoves[d[k]], insn);

+		lappend(&s->wlmove, &s->nwlmove, insn);

+	    }

+	    for (k = 0; k < nd; k++)

+		bsput(live, d[k]);

+

+	    for (k = 0; k < nd; k++)

+		for (l = 0; bsiter(live, &l); l++)

+		    addedge(s, d[k], l);

+	}

+    }

+

+}

+

+void regalloc(Isel *s)

+{

+    liveness(s);

+    if (debug)

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

+    build(s);

+}

+

 void setprint(FILE *fd, Bitset *s)

 {

     char *sep;

@@ -230,9 +295,3 @@

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

 }

-void regalloc(Isel *s)

-{

-    liveness(s);

-    if (debug)

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

-}

--- a/8/regalloc.c

+++ b/8/regalloc.c

@@ -71,16 +71,17 @@

 }

 Loc **loctab = NULL;

+int maxregid = 0;

+

 Loc *locreg(Mode m)

 {

     Loc *l;

-    static long nextid = 0;

     l = zalloc(sizeof(Loc));

     l->type = Locreg;

     l->mode = m;

-    l->reg.id = nextid++;

-    loctab = xrealloc(loctab, nextid * sizeof(Loc*));

+    l->reg.id = maxregid++;

+    loctab = xrealloc(loctab, maxregid * sizeof(Loc*));

     loctab[l->reg.id] = l;

     return l;

 }

--- a/parse/bitset.c

+++ b/parse/bitset.c

@@ -67,6 +67,19 @@

     return n;

 }

+int bsiter(Bitset *bs, uint *elt)

+{

+    uint i;

+

+    for (i = *elt; i < bsmax(bs); i++) {

+	if (bshas(bs, i)) {

+	    *elt = i;

+	    return 1;

+	}

+    }

+    return 0;

+}

+

 /* Returns the largest value that the bitset can possibly

  * hold. It's conservative, but scanning the entire bitset

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

--- a/parse/parse.h

+++ b/parse/parse.h

@@ -235,8 +235,9 @@

 int  bshas(Bitset *bs, uint elt);

 int  bseq(Bitset *a, Bitset *b);

 int  bsissubset(Bitset *set, Bitset *sub);

-size_t bscount(Bitset *bs);

+int  bsiter(Bitset *bs, uint *elt);

 size_t bsmax(Bitset *bs);

+size_t bscount(Bitset *bs);

 Htab *mkht(ulong (*hash)(void *key), int (*cmp)(void *k1, void *k2));

 int htput(Htab *ht, void *k, void *v);