Start working on dataflow analysis.

    This adds a first cut at breaking things into BBs.

3 files changed, 108 insertions, 0 deletions

diff --git a/opt/Makefile b/opt/Makefile
new file mode 100644
index 0000000..5092981
--- /dev/null
+++ b/opt/Makefile
@@ -0,0 +1,9 @@
+LIB=libopt.a
+OBJ=df.o \
+
+CFLAGS+=-I../parse
+LDFLAGS+=-L../parse -lparse
+EXTRADEP=../parse/libparse.a
+
+include ../mk/lexyacc.mk
+include ../mk/c.mk
diff --git a/opt/df.c b/opt/df.c
new file mode 100644
index 0000000..c19059d
--- /dev/null
+++ b/opt/df.c
@@ -0,0 +1,72 @@
+#include <stdlib.h>
+#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 "parse.h"
+#include "opt.h"
+
+
+Bb *mkbb(Cfg *cfg)
+{
+    static int nextbbid = 0;
+    Bb *bb;
+
+    bb = zalloc(sizeof(Bb));
+    bb->id = nextbbid++;
+    bb->in = mkbs();
+    bb->out = mkbs();
+    lappend(&cfg->bb, &cfg->nbb, bb);
+    return bb;
+}
+
+int addnode(Cfg *cfg, Bb *bb, Node *n)
+{
+    switch (exprop(n)) {
+        case Ojmp:
+        case Ocjmp:
+            lappend(&bb->nl, &bb->nnl, n);
+            lappend(&cfg->fixjmp, &cfg->nfixjmp, n);
+            lappend(&cfg->fixblk, &cfg->nfixblk, n);
+            return 1;
+            break;
+        default:
+            lappend(&bb->nl, &bb->nnl, n);
+            break;
+    }
+    return 0;
+}
+
+Cfg *mkcfg(Node **nl, int nn)
+{
+    Cfg *cfg;
+    Bb *bb;
+    int i;
+    
+    cfg = zalloc(sizeof(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);
+                break;
+            case Nexpr:
+                if (addnode(cfg, bb, nl[i]))
+                    bb = mkbb(cfg);
+                break;
+            case Ndecl:
+                break;
+            default:
+                die("Invalid node type %s in mkcfg", nodestr(nl[i]->type));
+        }
+    }
+    return cfg;
+}
diff --git a/opt/opt.h b/opt/opt.h
new file mode 100644
index 0000000..cbdd63e
--- /dev/null
+++ b/opt/opt.h
@@ -0,0 +1,27 @@
+typedef struct Cfg Cfg;
+typedef struct Bb Bb;
+
+struct  Cfg {
+    Bb **bb;
+    size_t nbb;
+
+    /* for building bb */
+    Node **fixjmp;
+    size_t nfixjmp;
+    Bb **fixblk;
+    size_t nfixblk;
+};
+
+struct Bb {
+    int id;
+    char **lbls;
+    size_t nlbls;
+    Node **nl;
+    size_t nnl;
+    Bitset *in;
+    Bitset *out;
+};
+
+/* Takes a reduced block, and returns a flow graph. */
+Cfg *mkcfg(Node **nl, int nn);
+void flow(Cfg *cfg);