shithub: mc

Download patch

ref: 3c8b80689e43668ae45177cd22d042407757ab02
parent: 6497ac18c2db4fb60489a0b0fd9c2c035c75c343
author: Ori Bernstein <ori@eigenstate.org>
date: Mon Jun 11 07:13:50 EDT 2012

Start working on dataflow analysis.

    This adds a first cut at breaking things into BBs.

--- /dev/null
+++ b/opt/Makefile
@@ -1,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
--- /dev/null
+++ b/opt/df.c
@@ -1,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;
+}
--- /dev/null
+++ b/opt/opt.h
@@ -1,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);