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