summaryrefslogtreecommitdiff
path: root/opt
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 /opt
parent150431ba47ff455aa3fb65525ccb44ec02a95774 (diff)
downloadmc-d4f8f2a57a2d1b7adf6d9f45a1d3661cfd3d3d48.tar.gz
Rename 'opt' to 'mi'.
It's not just for opts anymore.
Diffstat (limited to 'opt')
-rw-r--r--opt/Makefile9
-rw-r--r--opt/cfg.c167
-rw-r--r--opt/df.c19
-rw-r--r--opt/fold.c132
-rw-r--r--opt/opt.h32
5 files changed, 0 insertions, 359 deletions
diff --git a/opt/Makefile b/opt/Makefile
deleted file mode 100644
index 3dacc1d..0000000
--- a/opt/Makefile
+++ /dev/null
@@ -1,9 +0,0 @@
-LIB=libopt.a
-OBJ=cfg.o \
- fold.o \
- df.o \
-
-DEPS=../parse/libparse.a
-
-include ../mk/lexyacc.mk
-include ../mk/c.mk
diff --git a/opt/cfg.c b/opt/cfg.c
deleted file mode 100644
index 3387014..0000000
--- a/opt/cfg.c
+++ /dev/null
@@ -1,167 +0,0 @@
-#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");
- }
-}
diff --git a/opt/df.c b/opt/df.c
deleted file mode 100644
index 01185cd..0000000
--- a/opt/df.c
+++ /dev/null
@@ -1,19 +0,0 @@
-#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"
-
-void flow(Cfg *cfg)
-{
-}
-
diff --git a/opt/fold.c b/opt/fold.c
deleted file mode 100644
index 5a4eba0..0000000
--- a/opt/fold.c
+++ /dev/null
@@ -1,132 +0,0 @@
-#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 int islit(Node *n, vlong *v)
-{
- Node *l;
-
- if (exprop(n) != Olit)
- return 0;
- l = n->expr.args[0];
- if (l->lit.littype != Lint)
- return 0;
- *v = l->lit.intval;
- return 1;
-}
-
-static int isval(Node *n, vlong val)
-{
- vlong v;
-
- if (!islit(n, &v))
- return 0;
- return v == val;
-}
-
-static Node *val(int line, vlong val, Type *t)
-{
- Node *n;
-
- n = mkint(line, val);
- n = mkexpr(line, Olit, n, NULL);
- n->expr.type = t;
- return n;
-}
-
-Node *fold(Node *n)
-{
- Node **args, *r;
- vlong a, b;
- size_t i;
-
- if (!n)
- return NULL;
- if (n->type != Nexpr)
- return n;
-
- r = NULL;
- args = n->expr.args;
- for (i = 0; i < n->expr.nargs; i++)
- args[i] = fold(args[i]);
- switch (exprop(n)) {
- case Ovar:
- /* FIXME: chase small consts */
- break;
- case Oadd:
- /* x + 0 = 0 */
- if (isval(args[0], 0))
- r = args[1];
- if (isval(args[1], 0))
- r = args[0];
- if (islit(args[0], &a) && islit(args[1], &b))
- r = val(n->line, a + b, exprtype(n));
- break;
- case Osub:
- /* x - 0 = 0 */
- if (isval(args[1], 0))
- r = args[0];
- if (islit(args[0], &a) && islit(args[1], &b))
- r = val(n->line, a - b, exprtype(n));
- break;
- case Omul:
- /* 1 * x = x */
- if (isval(args[0], 1))
- r = args[1];
- if (isval(args[1], 1))
- r = args[0];
- /* 0 * x = 0 */
- if (isval(args[0], 0))
- r = args[0];
- if (isval(args[1], 0))
- r = args[1];
- if (islit(args[0], &a) && islit(args[1], &b))
- r = val(n->line, a * b, exprtype(n));
- break;
- case Odiv:
- /* x/1 = x */
- if (isval(args[1], 1))
- r = args[0];
- /* 0/x = 0 */
- if (isval(args[1], 0))
- r = args[1];
- if (islit(args[0], &a) && islit(args[1], &b))
- r = val(n->line, a / b, exprtype(n));
- break;
- case Omod:
- /* x%1 = x */
- if (isval(args[1], 0))
- r = args[0];
- if (islit(args[0], &a) && islit(args[1], &b))
- r = val(n->line, a % b, exprtype(n));
- break;
- case Oneg:
- if (islit(args[0], &a))
- r = val(n->line, -a, exprtype(n));
- break;
- case Ocast:
- /* FIXME: we currentl assume that the bits of the
- * val are close enough. */
- r = args[0];
- r->expr.type = exprtype(n);
- break;
- default:
- break;
- }
-
- if (r)
- return r;
- else
- return n;
-}
diff --git a/opt/opt.h b/opt/opt.h
deleted file mode 100644
index dcdfc62..0000000
--- a/opt/opt.h
+++ /dev/null
@@ -1,32 +0,0 @@
-typedef struct Cfg Cfg;
-typedef struct Bb Bb;
-
-struct Cfg {
- Bb **bb;
- size_t nbb;
-
- /* for building bb */
- int nextbbid;
- Htab *lblmap; /* label => Bb mapping */
- 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 *pred;
- Bitset *succ;
-};
-
-/* expression folding */
-Node *fold(Node *n);
-/* Takes a reduced block, and returns a flow graph. */
-Cfg *mkcfg(Node **nl, size_t nn);
-void dumpcfg(Cfg *c, FILE *fd);
-void flow(Cfg *cfg);