summaryrefslogtreecommitdiff
path: root/mi/cfg.c
diff options
context:
space:
mode:
authorOri Bernstein <orib@google.com>2012-09-17 15:21:40 -0400
committerOri Bernstein <orib@google.com>2012-09-17 15:21:40 -0400
commitd4f8f2a57a2d1b7adf6d9f45a1d3661cfd3d3d48 (patch)
tree69b6acd823d5a98a1b035877dbf9c25fbcb51db5 /mi/cfg.c
parent150431ba47ff455aa3fb65525ccb44ec02a95774 (diff)
downloadmc-d4f8f2a57a2d1b7adf6d9f45a1d3661cfd3d3d48.tar.gz
Rename 'opt' to 'mi'.
It's not just for opts anymore.
Diffstat (limited to 'mi/cfg.c')
-rw-r--r--mi/cfg.c167
1 files changed, 167 insertions, 0 deletions
diff --git a/mi/cfg.c b/mi/cfg.c
new file mode 100644
index 0000000..3387014
--- /dev/null
+++ b/mi/cfg.c
@@ -0,0 +1,167 @@
+#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"
+
+
+static Bb *mkbb(Cfg *cfg)
+{
+ Bb *bb;
+
+ bb = zalloc(sizeof(Bb));
+ bb->id = cfg->nextbbid++;
+ bb->pred = mkbs();
+ bb->succ = mkbs();
+ lappend(&cfg->bb, &cfg->nbb, bb);
+ return bb;
+}
+
+static void label(Cfg *cfg, Node *lbl, Bb *bb)
+{
+ htput(cfg->lblmap, lbl->lbl.name, bb);
+ lappend(&bb->lbls, &bb->nlbls, lbl->lbl.name);
+}
+
+static 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, bb);
+ return 1;
+ break;
+ default:
+ lappend(&bb->nl, &bb->nnl, n);
+ break;
+ }
+ return 0;
+}
+
+Cfg *mkcfg(Node **nl, size_t nn)
+{
+ Cfg *cfg;
+ Bb *pre, *post;
+ Bb *bb, *targ;
+ Node *a, *b;
+ size_t i;
+
+ cfg = zalloc(sizeof(Cfg));
+ cfg->lblmap = mkht(strhash, streq);
+ pre = mkbb(cfg);
+ bb = mkbb(cfg);
+ for (i = 0; i < nn; i++) {
+ switch (nl[i]->type) {
+ case Nlbl:
+ /* if the current block assumes fall-through, insert an explicit jump */
+ if (i > 0 && nl[i - 1]->type == Nexpr) {
+ if (exprop(nl[i - 1]) != Ocjmp && exprop(nl[i - 1]) != Ojmp)
+ addnode(cfg, bb, mkexpr(-1, Ojmp, mklbl(-1, nl[i]->lbl.name), NULL));
+ }
+ if (bb->nnl)
+ bb = mkbb(cfg);
+ label(cfg, nl[i], bb);
+ 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));
+ }
+ }
+ post = mkbb(cfg);
+ bsput(pre->succ, cfg->bb[1]->id);
+ bsput(cfg->bb[1]->pred, pre->id);
+ bsput(cfg->bb[cfg->nbb - 2]->succ, post->id);
+ bsput(post->pred, cfg->bb[cfg->nbb - 2]->id);
+ 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[1];
+ b = cfg->fixjmp[i]->expr.args[2];
+ 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->succ, targ->id);
+ bsput(targ->pred, bb->id);
+ }
+ if (b) {
+ targ = htget(cfg->lblmap, b->lbl.name);
+ if (!targ)
+ die("No bb with label %s", b->lbl.name);
+ bsput(bb->succ, targ->id);
+ bsput(targ->pred, bb->id);
+ }
+ }
+ return cfg;
+}
+
+void dumpcfg(Cfg *cfg, FILE *fd)
+{
+ size_t i, j;
+ Bb *bb;
+ char *sep;
+
+ for (j = 0; j < cfg->nbb; j++) {
+ bb = cfg->bb[j];
+ fprintf(fd, "\n");
+ fprintf(fd, "Bb: %d labels=(", bb->id);
+ sep = "";
+ for (i = 0; i < bb->nlbls; i++) {;
+ fprintf(fd, "%s%s", bb->lbls[i], sep);
+ sep = ",";
+ }
+ fprintf(fd, ")\n");
+
+ /* in edges */
+ fprintf(fd, "Pred: ");
+ sep = "";
+ for (i = 0; i < bsmax(bb->pred); i++) {
+ if (bshas(bb->pred, i)) {
+ fprintf(fd, "%s%zd", sep, i);
+ sep = ",";
+ }
+ }
+ fprintf(fd, "\n");
+
+ /* out edges */
+ fprintf(fd, "Succ: ");
+ sep = "";
+ for (i = 0; i < bsmax(bb->succ); i++) {
+ if (bshas(bb->succ, i)) {
+ fprintf(fd, "%s%zd", sep, i);
+ sep = ",";
+ }
+ }
+ fprintf(fd, "\n");
+
+ for (i = 0; i < bb->nnl; i++)
+ dump(bb->nl[i], fd);
+ fprintf(fd, "\n");
+ }
+}