summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorOri Bernstein <ori@eigenstate.org>2012-06-11 13:07:43 -0400
committerOri Bernstein <ori@eigenstate.org>2012-06-11 13:07:43 -0400
commitd298d45a63953323dfe03879a0ed1960387d320b (patch)
treeccc7cedb55d44ea1aa5e8ab00c4d84b35a38f5bb
parent1cb13e8ab55619e5063bebc5a2ca7a5a813a4e13 (diff)
downloadmc-d298d45a63953323dfe03879a0ed1960387d320b.tar.gz
More work towards getting dataflow going.
This commit temporarily breaks things.
-rw-r--r--8/Makefile6
-rw-r--r--8/main.c1
-rw-r--r--8/reduce.c5
-rw-r--r--Makefile1
-rw-r--r--opt/df.c77
-rw-r--r--opt/opt.h2
-rw-r--r--parse/bitset.c8
-rw-r--r--parse/parse.h1
8 files changed, 96 insertions, 5 deletions
diff --git a/8/Makefile b/8/Makefile
index fe4707d..6996650 100644
--- a/8/Makefile
+++ b/8/Makefile
@@ -4,9 +4,9 @@ OBJ=isel.o \
reduce.o \
regalloc.o \
-CFLAGS+=-I../parse
-LDFLAGS+=-L../parse -lparse
-EXTRADEP=../parse/libparse.a
+CFLAGS+=-I../parse -I../opt
+LDFLAGS+=-L../parse -lparse -L../opt -lopt
+EXTRADEP=../parse/libparse.a ../opt/libopt.a
include ../mk/lexyacc.mk
include ../mk/c.mk
diff --git a/8/main.c b/8/main.c
index 972f309..d55fd9e 100644
--- a/8/main.c
+++ b/8/main.c
@@ -11,6 +11,7 @@
#include "parse.h"
#include "asm.h"
+#include "opt.h"
Node *file;
static char *outfile;
diff --git a/8/reduce.c b/8/reduce.c
index 4588f17..f0acd38 100644
--- a/8/reduce.c
+++ b/8/reduce.c
@@ -11,6 +11,7 @@
#include "parse.h"
#include "asm.h"
+#include "opt.h"
#include "platform.h" /* HACK. We need some platform specific code gen behavior. *sigh.* */
@@ -607,6 +608,7 @@ static void lowerfn(char *name, Node *n, Htab *globls, FILE *fd)
int i;
Simp s = {0,};
Func fn;
+ Cfg *cfg;
if(debug)
printf("\n\nfunction %s\n", name);
@@ -622,6 +624,9 @@ static void lowerfn(char *name, Node *n, Htab *globls, FILE *fd)
if (debug)
for (i = 0; i < s.nstmts; i++)
dump(s.stmts[i], stdout);
+ cfg = mkcfg(s.stmts, s.nstmts);
+ if (debug)
+ dumpcfg(cfg, stdout);
fn.name = name;
fn.isglobl = 1; /* FIXME: we should actually use the visibility of the sym... */
diff --git a/Makefile b/Makefile
index 44083ab..a730d96 100644
--- a/Makefile
+++ b/Makefile
@@ -1,4 +1,5 @@
SUB = parse \
+ opt \
8
-include config.mk
diff --git a/opt/df.c b/opt/df.c
index c19059d..08b864c 100644
--- a/opt/df.c
+++ b/opt/df.c
@@ -27,6 +27,12 @@ Bb *mkbb(Cfg *cfg)
return bb;
}
+void label(Cfg *cfg, Node *lbl, Bb *bb)
+{
+ htput(cfg->lblmap, lbl->lbl.name, bb);
+ lappend(&bb->lbls, &bb->nlbls, lbl->lbl.name);
+}
+
int addnode(Cfg *cfg, Bb *bb, Node *n)
{
switch (exprop(n)) {
@@ -47,16 +53,19 @@ int addnode(Cfg *cfg, Bb *bb, Node *n)
Cfg *mkcfg(Node **nl, int nn)
{
Cfg *cfg;
- Bb *bb;
+ Bb *bb, *targ;
+ Node *a, *b;
int i;
cfg = zalloc(sizeof(Cfg));
+ cfg->lblmap = mkht(strhash, streq);
+ bb = mkbb(cfg);
for (i = 0; i < nn; i++) {
switch (nl[i]->type) {
case Nlbl:
if (bb->nnl)
bb = mkbb(cfg);
- lappend(&bb->lbls, &bb->nlbls, nl[i]->lbl.name);
+ label(cfg, nl[i], bb);
break;
case Nexpr:
if (addnode(cfg, bb, nl[i]))
@@ -68,5 +77,69 @@ Cfg *mkcfg(Node **nl, int nn)
die("Invalid node type %s in mkcfg", nodestr(nl[i]->type));
}
}
+ for (i = 0; i < cfg->nfixjmp; i++) {
+ bb = cfg->fixblk[i];
+ switch (exprop(cfg->fixjmp[i])) {
+ case Ojmp:
+ a = cfg->fixjmp[i]->expr.args[0];
+ b = NULL;
+ break;
+ case Ocjmp:
+ a = cfg->fixjmp[i]->expr.args[0];
+ b = cfg->fixjmp[i]->expr.args[1];
+ break;
+ default:
+ die("Bad jump fix thingy");
+ break;
+ }
+ if (a) {
+ targ = htget(cfg->lblmap, a->lbl.name);
+ if (!targ)
+ die("No bb with label %s", a->lbl.name);
+ bsput(bb->out, targ->id);
+ bsput(targ->in, bb->id);
+ }
+ if (b) {
+ targ = htget(cfg->lblmap, b->lbl.name);
+ if (!targ)
+ die("No bb with label %s", b->lbl.name);
+ bsput(bb->out, targ->id);
+ bsput(targ->in, bb->id);
+ }
+ }
return cfg;
}
+void dumpcfg(Cfg *cfg, FILE *fd)
+{
+ int i, j;
+ Bb *bb;
+ char *sep;
+
+ for (j = 0; j < cfg->nbb; j++) {
+ bb = cfg->bb[j];
+ fprintf(fd, "Bb: %d\n", bb->id);
+
+ /* in edges */
+ fprintf(fd, "In: ");
+ sep = "";
+ for (i = 0; i < bsmax(bb->in); i++) {
+ if (bshas(bb->in, i))
+ fprintf(fd, "%d%s", i, sep);
+ sep = ",";
+ }
+ fprintf(fd, "\n");
+
+ /* out edges */
+ fprintf(fd, "Out: ");
+ sep = "";
+ for (i = 0; i < bsmax(bb->out); i++) {
+ if (bshas(bb->in, i))
+ fprintf(fd, "%d%s", i, sep);
+ sep = ",";
+ }
+ fprintf(fd, "\n");
+
+ for (i = 0; i < bb->nnl; i++)
+ dump(bb->nl[i], fd);
+ }
+}
diff --git a/opt/opt.h b/opt/opt.h
index cbdd63e..dbf7dce 100644
--- a/opt/opt.h
+++ b/opt/opt.h
@@ -6,6 +6,7 @@ struct Cfg {
size_t nbb;
/* for building bb */
+ Htab *lblmap; /* label => Bb mapping */
Node **fixjmp;
size_t nfixjmp;
Bb **fixblk;
@@ -24,4 +25,5 @@ struct Bb {
/* Takes a reduced block, and returns a flow graph. */
Cfg *mkcfg(Node **nl, int nn);
+void dumpcfg(Cfg *c, FILE *fd);
void flow(Cfg *cfg);
diff --git a/parse/bitset.c b/parse/bitset.c
index 9bdfda9..153b602 100644
--- a/parse/bitset.c
+++ b/parse/bitset.c
@@ -56,6 +56,14 @@ int bscount(Bitset *bs)
return n;
}
+/* 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. */
+int bsmax(Bitset *bs)
+{
+ return bs->nchunks*sizeof(uint)*CHAR_BIT;
+}
+
void delbs(Bitset *bs)
{
free(bs->chunks);
diff --git a/parse/parse.h b/parse/parse.h
index 27c01c6..b44c197 100644
--- a/parse/parse.h
+++ b/parse/parse.h
@@ -233,6 +233,7 @@ void bsunion(Bitset *a, Bitset *b);
void bsintersect(Bitset *a, Bitset *b);
void bsdiff(Bitset *a, Bitset *b);
int bscount(Bitset *bs);
+int bsmax(Bitset *bs);
int bsissubset(Bitset *set, Bitset *sub);
Htab *mkht(ulong (*hash)(void *key), int (*cmp)(void *k1, void *k2));