ref: e34aa646c03869642a8d9b699356f5036cdd2c48
parent: 6b823d1993cb4bf0b01fca63cb926f8979580ce2
author: Ori Bernstein <[email protected]>
date: Fri Sep 5 06:53:28 EDT 2014
Move 'mi/' directory to 'opt/'.
This is to free the 'mi/' name for machine independent code
generation bits. Eg: debug information, register allocation,
and other common stuff.
--- a/6/Makefile
+++ b/6/Makefile
@@ -5,7 +5,7 @@
ra.o \
simp.o \
-DEPS=../parse/libparse.a ../mi/libmi.a
+DEPS=../parse/libparse.a ../opt/libmi.a
include ../config.mk
include ../mk/c.mk
--- a/Makefile
+++ b/Makefile
@@ -1,5 +1,5 @@
SUB = parse \
- mi \
+ opt \
6 \
muse \
myrbuild \
--- a/mi/Makefile
+++ /dev/null
@@ -1,8 +1,0 @@
-LIB=libmi.a
-OBJ=cfg.o \
- fold.o \
- df.o \
-
-DEPS=../parse/libparse.a
-
-include ../mk/c.mk
--- a/mi/cfg.c
+++ /dev/null
@@ -1,196 +1,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 char *lblstr(Node *n)
-{- assert(exprop(n) == Olit);
- assert(n->expr.args[0]->type == Nlit);
- assert(n->expr.args[0]->lit.littype == Llbl);
- return n->expr.args[0]->lit.lblval;
-}
-
-static void label(Cfg *cfg, Node *lbl, Bb *bb)
-{- htput(cfg->lblmap, lblstr(lbl), bb);
- lappend(&bb->lbls, &bb->nlbls, lblstr(lbl));
-}
-
-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;
-}
-
-static int islabel(Node *n)
-{- Node *l;
- if (n->type != Nexpr)
- return 0;
- if (exprop(n) != Olit)
- return 0;
- l = n->expr.args[0];
- if (l->type != Nlit)
- return 0;
- if (l->lit.littype != Llbl)
- return 0;
- return 1;
-}
-
-static Bb *addlabel(Cfg *cfg, Bb *bb, Node **nl, size_t i)
-{- /* 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, lblstr(nl[i])), NULL));
- }
- if (bb->nnl)
- bb = mkbb(cfg);
- label(cfg, nl[i], bb);
- return bb;
-}
-
-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 Nexpr:
- if (islabel(nl[i]))
- bb = addlabel(cfg, bb, nl, i);
- else if (addnode(cfg, bb, nl[i]))
- bb = mkbb(cfg);
- break;
- 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, lblstr(a));
- if (!targ)
- die("No bb with label \"%s\"", lblstr(a));- bsput(bb->succ, targ->id);
- bsput(targ->pred, bb->id);
- }
- if (b) {- targ = htget(cfg->lblmap, lblstr(b));
- if (!targ)
- die("No bb with label \"%s\"", lblstr(b));- 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");
- }
-}
--- a/mi/df.c
+++ /dev/null
@@ -1,40 +1,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 void nodeuse(Node *n, Bitset *bs)
-{-}
-
-static void nodedef(Node *n, Bitset *bs)
-{-}
-
-static void bbuse(Bb *bb, Bitset *bs)
-{-}
-
-static void bbdef(Bb *bb, Bitset *bs)
-{-}
-*/
-
-void flow(Cfg *cfg)
-{-}
-
-void checkret(Cfg *cfg)
-{-}
--- a/mi/fold.c
+++ /dev/null
@@ -1,215 +1,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;
-}
-
-static int issmallconst(Node *dcl)
-{- Type *t;
-
- if (!dcl->decl.isconst)
- return 0;
- if (!dcl->decl.init)
- return 0;
- t = tybase(exprtype(dcl->decl.init));
- if (t->type <= Tyfloat64)
- return 1;
- return 0;
-}
-
-static Node *foldcast(Node *n)
-{- Type *to, *from;
- Node *sub;
-
- sub = n->expr.args[0];
- to = exprtype(n);
- from = exprtype(sub);
-
- switch (tybase(to)->type) {- case Tybool:
- case Tyint8: case Tyint16: case Tyint32: case Tyint64:
- case Tyuint8: case Tyuint16: case Tyuint32: case Tyuint64:
- case Tyint: case Tyuint: case Tylong: case Tyulong:
- case Tychar: case Tybyte:
- case Typtr:
- switch (tybase(from)->type) {- case Tybool:
- case Tyint8: case Tyint16: case Tyint32: case Tyint64:
- case Tyuint8: case Tyuint16: case Tyuint32: case Tyuint64:
- case Tyint: case Tyuint: case Tylong: case Tyulong:
- case Tychar: case Tybyte:
- case Typtr:
- if (exprop(sub) == Olit || tybase(from)->type == tybase(to)->type) {- sub->expr.type = to;
- return sub;
- } else {- return n;
- }
- default:
- return n;
- }
- default:
- return n;
- }
- return n;
-}
-
-
-
-Node *fold(Node *n, int foldvar)
-{- Node **args, *r;
- Type *t;
- 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], foldvar);
- switch (exprop(n)) {- case Ovar:
- if (foldvar && issmallconst(decls[n->expr.did]))
- r = fold(decls[n->expr.did]->decl.init, foldvar);
- 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 Obsl:
- if (islit(args[0], &a) && islit(args[1], &b))
- r = val(n->line, a << b, exprtype(n));
- break;
- case Obsr:
- if (islit(args[0], &a) && islit(args[1], &b))
- r = val(n->line, a >> b, exprtype(n));
- break;
- case Obor:
- if (islit(args[0], &a) && islit(args[1], &b))
- r = val(n->line, a | b, exprtype(n));
- break;
- case Oband:
- if (islit(args[0], &a) && islit(args[1], &b))
- r = val(n->line, a & b, exprtype(n));
- break;
- case Obxor:
- if (islit(args[0], &a) && islit(args[1], &b))
- r = val(n->line, a ^ b, exprtype(n));
- break;
- case Omemb:
- t = tybase(exprtype(args[0]));
- /* we only fold lengths right now */
- if (t->type == Tyarray && !strcmp(namestr(args[1]), "len"))
- r = t->asize;
- break;
- case Ocast:
- r = foldcast(n);
- break;
- default:
- break;
- }
-
- if (r && n->expr.idx)
- r->expr.idx = n->expr.idx;
-
- if (r)
- return r;
- else
- return n;
-}
-
--- a/mi/opt.h
+++ /dev/null
@@ -1,34 +1,0 @@
-typedef struct Cfg Cfg;
-typedef struct Bb Bb;
-
-struct Cfg {- Bb **bb;
- Bb *start;
- Bb *end;
- 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, int foldvar);
-/* 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);
--- /dev/null
+++ b/opt/Makefile
@@ -1,0 +1,8 @@
+LIB=libmi.a
+OBJ=cfg.o \
+ fold.o \
+ df.o \
+
+DEPS=../parse/libparse.a
+
+include ../mk/c.mk
--- /dev/null
+++ b/opt/cfg.c
@@ -1,0 +1,196 @@
+#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 char *lblstr(Node *n)
+{+ assert(exprop(n) == Olit);
+ assert(n->expr.args[0]->type == Nlit);
+ assert(n->expr.args[0]->lit.littype == Llbl);
+ return n->expr.args[0]->lit.lblval;
+}
+
+static void label(Cfg *cfg, Node *lbl, Bb *bb)
+{+ htput(cfg->lblmap, lblstr(lbl), bb);
+ lappend(&bb->lbls, &bb->nlbls, lblstr(lbl));
+}
+
+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;
+}
+
+static int islabel(Node *n)
+{+ Node *l;
+ if (n->type != Nexpr)
+ return 0;
+ if (exprop(n) != Olit)
+ return 0;
+ l = n->expr.args[0];
+ if (l->type != Nlit)
+ return 0;
+ if (l->lit.littype != Llbl)
+ return 0;
+ return 1;
+}
+
+static Bb *addlabel(Cfg *cfg, Bb *bb, Node **nl, size_t i)
+{+ /* 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, lblstr(nl[i])), NULL));
+ }
+ if (bb->nnl)
+ bb = mkbb(cfg);
+ label(cfg, nl[i], bb);
+ return bb;
+}
+
+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 Nexpr:
+ if (islabel(nl[i]))
+ bb = addlabel(cfg, bb, nl, i);
+ else if (addnode(cfg, bb, nl[i]))
+ bb = mkbb(cfg);
+ break;
+ 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, lblstr(a));
+ if (!targ)
+ die("No bb with label \"%s\"", lblstr(a));+ bsput(bb->succ, targ->id);
+ bsput(targ->pred, bb->id);
+ }
+ if (b) {+ targ = htget(cfg->lblmap, lblstr(b));
+ if (!targ)
+ die("No bb with label \"%s\"", lblstr(b));+ 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");
+ }
+}
--- /dev/null
+++ b/opt/df.c
@@ -1,0 +1,40 @@
+#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 void nodeuse(Node *n, Bitset *bs)
+{+}
+
+static void nodedef(Node *n, Bitset *bs)
+{+}
+
+static void bbuse(Bb *bb, Bitset *bs)
+{+}
+
+static void bbdef(Bb *bb, Bitset *bs)
+{+}
+*/
+
+void flow(Cfg *cfg)
+{+}
+
+void checkret(Cfg *cfg)
+{+}
--- /dev/null
+++ b/opt/fold.c
@@ -1,0 +1,215 @@
+#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;
+}
+
+static int issmallconst(Node *dcl)
+{+ Type *t;
+
+ if (!dcl->decl.isconst)
+ return 0;
+ if (!dcl->decl.init)
+ return 0;
+ t = tybase(exprtype(dcl->decl.init));
+ if (t->type <= Tyfloat64)
+ return 1;
+ return 0;
+}
+
+static Node *foldcast(Node *n)
+{+ Type *to, *from;
+ Node *sub;
+
+ sub = n->expr.args[0];
+ to = exprtype(n);
+ from = exprtype(sub);
+
+ switch (tybase(to)->type) {+ case Tybool:
+ case Tyint8: case Tyint16: case Tyint32: case Tyint64:
+ case Tyuint8: case Tyuint16: case Tyuint32: case Tyuint64:
+ case Tyint: case Tyuint: case Tylong: case Tyulong:
+ case Tychar: case Tybyte:
+ case Typtr:
+ switch (tybase(from)->type) {+ case Tybool:
+ case Tyint8: case Tyint16: case Tyint32: case Tyint64:
+ case Tyuint8: case Tyuint16: case Tyuint32: case Tyuint64:
+ case Tyint: case Tyuint: case Tylong: case Tyulong:
+ case Tychar: case Tybyte:
+ case Typtr:
+ if (exprop(sub) == Olit || tybase(from)->type == tybase(to)->type) {+ sub->expr.type = to;
+ return sub;
+ } else {+ return n;
+ }
+ default:
+ return n;
+ }
+ default:
+ return n;
+ }
+ return n;
+}
+
+
+
+Node *fold(Node *n, int foldvar)
+{+ Node **args, *r;
+ Type *t;
+ 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], foldvar);
+ switch (exprop(n)) {+ case Ovar:
+ if (foldvar && issmallconst(decls[n->expr.did]))
+ r = fold(decls[n->expr.did]->decl.init, foldvar);
+ 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 Obsl:
+ if (islit(args[0], &a) && islit(args[1], &b))
+ r = val(n->line, a << b, exprtype(n));
+ break;
+ case Obsr:
+ if (islit(args[0], &a) && islit(args[1], &b))
+ r = val(n->line, a >> b, exprtype(n));
+ break;
+ case Obor:
+ if (islit(args[0], &a) && islit(args[1], &b))
+ r = val(n->line, a | b, exprtype(n));
+ break;
+ case Oband:
+ if (islit(args[0], &a) && islit(args[1], &b))
+ r = val(n->line, a & b, exprtype(n));
+ break;
+ case Obxor:
+ if (islit(args[0], &a) && islit(args[1], &b))
+ r = val(n->line, a ^ b, exprtype(n));
+ break;
+ case Omemb:
+ t = tybase(exprtype(args[0]));
+ /* we only fold lengths right now */
+ if (t->type == Tyarray && !strcmp(namestr(args[1]), "len"))
+ r = t->asize;
+ break;
+ case Ocast:
+ r = foldcast(n);
+ break;
+ default:
+ break;
+ }
+
+ if (r && n->expr.idx)
+ r->expr.idx = n->expr.idx;
+
+ if (r)
+ return r;
+ else
+ return n;
+}
+
--- /dev/null
+++ b/opt/opt.h
@@ -1,0 +1,34 @@
+typedef struct Cfg Cfg;
+typedef struct Bb Bb;
+
+struct Cfg {+ Bb **bb;
+ Bb *start;
+ Bb *end;
+ 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, int foldvar);
+/* 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);