summaryrefslogtreecommitdiff
path: root/mi
diff options
context:
space:
mode:
authorOri Bernstein <ori@eigenstate.org>2015-11-17 20:53:32 -0800
committerOri Bernstein <ori@eigenstate.org>2015-11-17 20:53:32 -0800
commit8531896f8d21ba1e727262aaf5cd96043590b480 (patch)
tree7c01441755f56ab66d33c37d3ac41642ddc46c0b /mi
parentc20862cda53c711fe476f6c7d0f6631af47a4933 (diff)
downloadmc-8531896f8d21ba1e727262aaf5cd96043590b480.tar.gz
MEGAPATCH: Tabification.
Tabs > spaces. By 4 spaces, to be precise. Let's use them.
Diffstat (limited to 'mi')
-rw-r--r--mi/cfg.c456
-rw-r--r--mi/dfcheck.c184
-rw-r--r--mi/fold.c390
-rw-r--r--mi/match.c1288
-rw-r--r--mi/mi.h48
-rw-r--r--mi/reaching.c233
6 files changed, 1292 insertions, 1307 deletions
diff --git a/mi/cfg.c b/mi/cfg.c
index 39b59fe..f5c6961 100644
--- a/mi/cfg.c
+++ b/mi/cfg.c
@@ -16,298 +16,298 @@
static Bb *mkbb(Cfg *cfg)
{
- Bb *bb;
+ Bb *bb;
- bb = zalloc(sizeof(Bb));
- bb->id = cfg->nextbbid++;
- bb->pred = mkbs();
- bb->succ = mkbs();
- lappend(&cfg->bb, &cfg->nbb, bb);
- return 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 strlabel(Cfg *cfg, char *lbl, Bb *bb)
{
- htput(cfg->lblmap, lbl, bb);
- lappend(&bb->lbls, &bb->nlbls, lbl);
+ htput(cfg->lblmap, lbl, bb);
+ lappend(&bb->lbls, &bb->nlbls, lbl);
}
static void label(Cfg *cfg, Node *lbl, Bb *bb)
{
- strlabel(cfg, lblstr(lbl), bb);
+ strlabel(cfg, lblstr(lbl), bb);
}
static int isnonretcall(Node *fn)
{
- Node *dcl;
+ Node *dcl;
- if (exprop(fn) != Ovar)
- return 0;
- dcl = decls[fn->expr.did];
- return dcl->decl.isnoret;
+ if (exprop(fn) != Ovar)
+ return 0;
+ dcl = decls[fn->expr.did];
+ return dcl->decl.isnoret;
}
static int addnode(Cfg *cfg, Bb *bb, Node *n)
{
- switch (exprop(n)) {
- case Ojmp:
- case Ocjmp:
- case Oret:
- lappend(&bb->nl, &bb->nnl, n);
- lappend(&cfg->fixjmp, &cfg->nfixjmp, n);
- lappend(&cfg->fixblk, &cfg->nfixblk, bb);
- return 1;
- case Ocall:
- lappend(&bb->nl, &bb->nnl, n);
- return isnonretcall(n->expr.args[0]);
- case Odead:
- lappend(&bb->nl, &bb->nnl, n);
- return 1;
- default:
- lappend(&bb->nl, &bb->nnl, n);
- break;
- }
- return 0;
+ switch (exprop(n)) {
+ case Ojmp:
+ case Ocjmp:
+ case Oret:
+ lappend(&bb->nl, &bb->nnl, n);
+ lappend(&cfg->fixjmp, &cfg->nfixjmp, n);
+ lappend(&cfg->fixblk, &cfg->nfixblk, bb);
+ return 1;
+ case Ocall:
+ lappend(&bb->nl, &bb->nnl, n);
+ return isnonretcall(n->expr.args[0]);
+ case Odead:
+ lappend(&bb->nl, &bb->nnl, n);
+ return 1;
+ 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;
+ 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, Srcloc loc)
{
- /* 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(loc, Ojmp, mklbl(loc, lblstr(nl[i])), NULL));
- }
- if (bb->nnl)
- bb = mkbb(cfg);
- label(cfg, nl[i], bb);
- return bb;
+ /* 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(loc, Ojmp, mklbl(loc, lblstr(nl[i])), NULL));
+ }
+ if (bb->nnl)
+ bb = mkbb(cfg);
+ label(cfg, nl[i], bb);
+ return bb;
}
void delete(Cfg *cfg, Bb *bb)
{
- size_t i, j;
+ size_t i, j;
- if (bb == cfg->start || bb == cfg->end)
- return;
- for (i = 0; bsiter(bb->pred, &i); i++) {
- bsunion(cfg->bb[i]->succ, bb->succ);
- bsdel(cfg->bb[i]->succ, bb->id);
- }
- for (i = 0; bsiter(bb->succ, &i); i++) {
- bsunion(cfg->bb[i]->pred, bb->pred);
- bsdel(cfg->bb[i]->pred, bb->id);
- for (j = 0; j < bb->nlbls; j++)
- strlabel(cfg, bb->lbls[j], cfg->bb[i]);
- }
- cfg->bb[bb->id] = NULL;
+ if (bb == cfg->start || bb == cfg->end)
+ return;
+ for (i = 0; bsiter(bb->pred, &i); i++) {
+ bsunion(cfg->bb[i]->succ, bb->succ);
+ bsdel(cfg->bb[i]->succ, bb->id);
+ }
+ for (i = 0; bsiter(bb->succ, &i); i++) {
+ bsunion(cfg->bb[i]->pred, bb->pred);
+ bsdel(cfg->bb[i]->pred, bb->id);
+ for (j = 0; j < bb->nlbls; j++)
+ strlabel(cfg, bb->lbls[j], cfg->bb[i]);
+ }
+ cfg->bb[bb->id] = NULL;
}
void noexit(Cfg *cfg, Bb *bb)
{
- size_t i;
- for (i = 0; bsiter(bb->succ, &i); i++)
- bsdel(cfg->bb[i]->pred, bb->id);
- bsclear(bb->succ);
+ size_t i;
+ for (i = 0; bsiter(bb->succ, &i); i++)
+ bsdel(cfg->bb[i]->pred, bb->id);
+ bsclear(bb->succ);
}
void trimdead(Cfg *cfg, Bb *bb)
{
- size_t i;
+ size_t i;
- if (!bb)
- return;
- for (i = 0; i < bb->nnl; i++) {
- switch (exprop(bb->nl[i])) {
- /* if we're jumping, we can't keep going
- * within this BB */
- case Ojmp:
- case Ocjmp:
- case Oret:
- bb->nnl = i + 1;
- return;
- case Odead:
- noexit(cfg, bb);
- bb->nnl = i + 1;
- return;
- case Ocall:
- if (isnonretcall(bb->nl[i]->expr.args[0])) {
- noexit(cfg, bb);
- bb->nnl = i + 1;
- return;
- }
- break;
- default:
- /* nothing */
- break;
- }
- }
+ if (!bb)
+ return;
+ for (i = 0; i < bb->nnl; i++) {
+ switch (exprop(bb->nl[i])) {
+ /* if we're jumping, we can't keep going
+ * within this BB */
+ case Ojmp:
+ case Ocjmp:
+ case Oret:
+ bb->nnl = i + 1;
+ return;
+ case Odead:
+ noexit(cfg, bb);
+ bb->nnl = i + 1;
+ return;
+ case Ocall:
+ if (isnonretcall(bb->nl[i]->expr.args[0])) {
+ noexit(cfg, bb);
+ bb->nnl = i + 1;
+ return;
+ }
+ break;
+ default:
+ /* nothing */
+ break;
+ }
+ }
}
void trim(Cfg *cfg)
{
- Bb *bb;
- size_t i;
- int deleted;
+ Bb *bb;
+ size_t i;
+ int deleted;
- deleted = 1;
- while (deleted) {
- deleted = 0;
- for (i = 0; i < cfg->nbb; i++) {
- bb = cfg->bb[i];
- if (bb == cfg->start || bb == cfg->end)
- continue;
- trimdead(cfg, bb);
- if (bb && bsisempty(bb->pred)) {
- delete(cfg, bb);
- deleted = 1;
- }
- }
- }
+ deleted = 1;
+ while (deleted) {
+ deleted = 0;
+ for (i = 0; i < cfg->nbb; i++) {
+ bb = cfg->bb[i];
+ if (bb == cfg->start || bb == cfg->end)
+ continue;
+ trimdead(cfg, bb);
+ if (bb && bsisempty(bb->pred)) {
+ delete(cfg, bb);
+ deleted = 1;
+ }
+ }
+ }
}
Cfg *mkcfg(Node *fn, Node **nl, size_t nn)
{
- Cfg *cfg;
- Bb *pre, *post;
- Bb *bb, *targ;
- Node *a, *b;
- static int nextret;
- char buf[32];
- size_t i;
+ Cfg *cfg;
+ Bb *pre, *post;
+ Bb *bb, *targ;
+ Node *a, *b;
+ static int nextret;
+ char buf[32];
+ size_t i;
- cfg = zalloc(sizeof(Cfg));
- cfg->fn = fn;
- 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, nl[i]->loc);
- 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);
- bprintf(buf, sizeof buf, ".R%d", nextret++);
- label(cfg, mklbl(fn->loc, buf), post);
+ cfg = zalloc(sizeof(Cfg));
+ cfg->fn = fn;
+ 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, nl[i]->loc);
+ 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);
+ bprintf(buf, sizeof buf, ".R%d", nextret++);
+ label(cfg, mklbl(fn->loc, buf), post);
- cfg->start = pre;
- cfg->end = post;
- 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);
+ cfg->start = pre;
+ cfg->end = post;
+ 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;
- case Oret:
- a = mklbl(cfg->fixjmp[i]->loc, cfg->end->lbls[0]);
- b = NULL;
- 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);
- }
- }
- trim(cfg);
- return cfg;
+ 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;
+ case Oret:
+ a = mklbl(cfg->fixjmp[i]->loc, cfg->end->lbls[0]);
+ b = NULL;
+ 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);
+ }
+ }
+ trim(cfg);
+ return cfg;
}
void dumpbb(Bb *bb, FILE *fd)
{
- size_t i;
- char *sep;
+ size_t i;
+ char *sep;
- 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");
+ 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");
+ /* 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");
+ /* 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");
+ for (i = 0; i < bb->nnl; i++)
+ dump(bb->nl[i], fd);
+ fprintf(fd, "\n");
}
void dumpcfg(Cfg *cfg, FILE *fd)
{
- size_t i;
+ size_t i;
- for (i = 0; i < cfg->nbb; i++) {
- if (!cfg->bb[i])
- continue;
- fprintf(fd, "\n");
- dumpbb(cfg->bb[i], fd);
- }
+ for (i = 0; i < cfg->nbb; i++) {
+ if (!cfg->bb[i])
+ continue;
+ fprintf(fd, "\n");
+ dumpbb(cfg->bb[i], fd);
+ }
}
diff --git a/mi/dfcheck.c b/mi/dfcheck.c
index 316bf65..a83f1db 100644
--- a/mi/dfcheck.c
+++ b/mi/dfcheck.c
@@ -15,117 +15,117 @@
static void checkundef(Node *n, Reaching *r, Bitset *reach, Bitset *kill)
{
- size_t i, j, did;
- Node *def;
- Type *t;
+ size_t i, j, did;
+ Node *def;
+ Type *t;
- if (n->type != Nexpr)
- return;
- if (exprop(n) == Ovar) {
- did = n->expr.did;
- for (j = 0; j < r->ndefs[did]; j++) {
- t = tybase(exprtype(n));
- if (t->type == Tystruct || t->type == Tyunion || t->type == Tyarray || t->type == Tytuple)
- continue;
- if (bshas(kill, r->defs[did][j]))
- continue;
- if (!bshas(reach, r->defs[did][j]))
- continue;
- def = nodes[r->defs[did][j]];
- if (exprop(def) == Oundef)
- fatal(n, "%s used before definition", namestr(n->expr.args[0]));
- }
- } else {
- switch (exprop(n)) {
- case Oset:
- case Oasn:
- case Oblit:
- checkundef(n->expr.args[1], r, reach, kill);
- break;
- case Oaddr:
- case Oslice:
- /* these don't actually look at the of args[0], so they're ok. */
- for (i = 1; i < n->expr.nargs; i++)
- checkundef(n->expr.args[i], r, reach, kill);
- break;
- case Ocall:
- for (i = 1; i < n->expr.nargs; i++)
- if (exprop(n->expr.args[i]) != Oaddr)
- checkundef(n->expr.args[i], r, reach, kill);
- break;
- default:
- for (i = 0; i < n->expr.nargs; i++)
- checkundef(n->expr.args[i], r, reach, kill);
- break;
- }
- }
+ if (n->type != Nexpr)
+ return;
+ if (exprop(n) == Ovar) {
+ did = n->expr.did;
+ for (j = 0; j < r->ndefs[did]; j++) {
+ t = tybase(exprtype(n));
+ if (t->type == Tystruct || t->type == Tyunion || t->type == Tyarray || t->type == Tytuple)
+ continue;
+ if (bshas(kill, r->defs[did][j]))
+ continue;
+ if (!bshas(reach, r->defs[did][j]))
+ continue;
+ def = nodes[r->defs[did][j]];
+ if (exprop(def) == Oundef)
+ fatal(n, "%s used before definition", namestr(n->expr.args[0]));
+ }
+ } else {
+ switch (exprop(n)) {
+ case Oset:
+ case Oasn:
+ case Oblit:
+ checkundef(n->expr.args[1], r, reach, kill);
+ break;
+ case Oaddr:
+ case Oslice:
+ /* these don't actually look at the of args[0], so they're ok. */
+ for (i = 1; i < n->expr.nargs; i++)
+ checkundef(n->expr.args[i], r, reach, kill);
+ break;
+ case Ocall:
+ for (i = 1; i < n->expr.nargs; i++)
+ if (exprop(n->expr.args[i]) != Oaddr)
+ checkundef(n->expr.args[i], r, reach, kill);
+ break;
+ default:
+ for (i = 0; i < n->expr.nargs; i++)
+ checkundef(n->expr.args[i], r, reach, kill);
+ break;
+ }
+ }
}
static void checkreach(Cfg *cfg)
{
- Bitset *reach, *kill;
- size_t i, j, k;
- Reaching *r;
- Node *n, *m;
- Bb *bb;
+ Bitset *reach, *kill;
+ size_t i, j, k;
+ Reaching *r;
+ Node *n, *m;
+ Bb *bb;
- r = reaching(cfg);
- for (i = 0; i < cfg->nbb; i++) {
- bb = cfg->bb[i];
- if (!bb)
- continue;
- reach = bsdup(r->in[i]);
- kill = mkbs();
- for (j = 0; j < bb->nnl; j++) {
- n = bb->nl[j];
- if (exprop(n) == Oundef) {
- bsput(reach, n->nid);
- } else {
- m = assignee(n);
- if (m)
- for (k = 0; k < r->ndefs[m->expr.did]; k++)
- bsput(kill, r->defs[m->expr.did][k]);
- checkundef(n, r, reach, kill);
- }
- }
- bsfree(reach);
- bsfree(kill);
- }
+ r = reaching(cfg);
+ for (i = 0; i < cfg->nbb; i++) {
+ bb = cfg->bb[i];
+ if (!bb)
+ continue;
+ reach = bsdup(r->in[i]);
+ kill = mkbs();
+ for (j = 0; j < bb->nnl; j++) {
+ n = bb->nl[j];
+ if (exprop(n) == Oundef) {
+ bsput(reach, n->nid);
+ } else {
+ m = assignee(n);
+ if (m)
+ for (k = 0; k < r->ndefs[m->expr.did]; k++)
+ bsput(kill, r->defs[m->expr.did][k]);
+ checkundef(n, r, reach, kill);
+ }
+ }
+ bsfree(reach);
+ bsfree(kill);
+ }
}
static void checkpredret(Cfg *cfg, Bb *bb)
{
- Bb *pred;
- Op op;
- size_t i;
+ Bb *pred;
+ Op op;
+ size_t i;
- for (i = 0; bsiter(bb->pred, &i); i++) {
- pred = cfg->bb[i];
- if (pred->nnl == 0) {
- checkpredret(cfg, pred);
- } else {
- op = exprop(pred->nl[pred->nnl - 1]);
- if (op != Oret && op != Odead) {
- fatal(pred->nl[pred->nnl-1], "Reaches end of function without return\n");
- }
- }
- }
+ for (i = 0; bsiter(bb->pred, &i); i++) {
+ pred = cfg->bb[i];
+ if (pred->nnl == 0) {
+ checkpredret(cfg, pred);
+ } else {
+ op = exprop(pred->nl[pred->nnl - 1]);
+ if (op != Oret && op != Odead) {
+ fatal(pred->nl[pred->nnl-1], "Reaches end of function without return\n");
+ }
+ }
+ }
}
static void checkret(Cfg *cfg)
{
- Type *ft;
+ Type *ft;
- ft = tybase(decltype(cfg->fn));
- assert(ft->type == Tyfunc || ft->type == Tycode);
- if (ft->sub[0]->type == Tyvoid)
- return;
+ ft = tybase(decltype(cfg->fn));
+ assert(ft->type == Tyfunc || ft->type == Tycode);
+ if (ft->sub[0]->type == Tyvoid)
+ return;
- checkpredret(cfg, cfg->end);
+ checkpredret(cfg, cfg->end);
}
void check(Cfg *cfg)
{
- checkret(cfg);
- if(0) checkreach(cfg);
+ checkret(cfg);
+ if(0) checkreach(cfg);
}
diff --git a/mi/fold.c b/mi/fold.c
index 2658431..f62e440 100644
--- a/mi/fold.c
+++ b/mi/fold.c
@@ -15,226 +15,226 @@
static int getintlit(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;
+ 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 isintval(Node *n, vlong val)
{
- vlong v;
+ vlong v;
- if (!getintlit(n, &v))
- return 0;
- return v == val;
+ if (!getintlit(n, &v))
+ return 0;
+ return v == val;
}
static Node *val(Srcloc loc, vlong val, Type *t)
{
- Node *l, *n;
+ Node *l, *n;
- l = mkint(loc, val);
- n = mkexpr(loc, Olit, l, NULL);
- l->lit.type = t;
- n->expr.type = t;
- return n;
+ l = mkint(loc, val);
+ n = mkexpr(loc, Olit, l, NULL);
+ l->lit.type = t;
+ 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 <= Tyflt64)
- return 1;
- return 0;
+ Type *t;
+
+ if (!dcl->decl.isconst)
+ return 0;
+ if (!dcl->decl.init)
+ return 0;
+ t = tybase(exprtype(dcl->decl.init));
+ if (t->type <= Tyflt64)
+ 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 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 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;
+ 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 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 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;
}
int idxcmp(const void *pa, const void *pb)
{
- Node *a, *b;
- vlong av, bv;
-
- a = *(Node **)pa;
- b = *(Node **)pb;
-
- assert(getintlit(a->expr.idx, &av));
- assert(getintlit(b->expr.idx, &bv));
-
- /* don't trust overflow with int64 */
- if (av < bv)
- return -1;
- else if (av == bv)
- return 0;
- else
- return 1;
+ Node *a, *b;
+ vlong av, bv;
+
+ a = *(Node **)pa;
+ b = *(Node **)pb;
+
+ assert(getintlit(a->expr.idx, &av));
+ assert(getintlit(b->expr.idx, &bv));
+
+ /* don't trust overflow with int64 */
+ if (av < bv)
+ return -1;
+ else if (av == bv)
+ return 0;
+ else
+ return 1;
}
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;
- if (n->expr.idx)
- n->expr.idx = fold(n->expr.idx, foldvar);
- 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 (isintval(args[0], 0))
- r = args[1];
- if (isintval(args[1], 0))
- r = args[0];
- if (getintlit(args[0], &a) && getintlit(args[1], &b))
- r = val(n->loc, a + b, exprtype(n));
- break;
- case Osub:
- /* x - 0 = 0 */
- if (isintval(args[1], 0))
- r = args[0];
- if (getintlit(args[0], &a) && getintlit(args[1], &b))
- r = val(n->loc, a - b, exprtype(n));
- break;
- case Omul:
- /* 1 * x = x */
- if (isintval(args[0], 1))
- r = args[1];
- if (isintval(args[1], 1))
- r = args[0];
- /* 0 * x = 0 */
- if (isintval(args[0], 0))
- r = args[0];
- if (isintval(args[1], 0))
- r = args[1];
- if (getintlit(args[0], &a) && getintlit(args[1], &b))
- r = val(n->loc, a * b, exprtype(n));
- break;
- case Odiv:
- /* x/0 = error */
- if (isintval(args[1], 0))
- fatal(args[1], "division by zero");
- /* x/1 = x */
- if (isintval(args[1], 1))
- r = args[0];
- /* 0/x = 0 */
- if (isintval(args[1], 0))
- r = args[1];
- if (getintlit(args[0], &a) && getintlit(args[1], &b))
- r = val(n->loc, a / b, exprtype(n));
- break;
- case Omod:
- /* x%1 = x */
- if (isintval(args[1], 0))
- r = args[0];
- if (getintlit(args[0], &a) && getintlit(args[1], &b))
- r = val(n->loc, a % b, exprtype(n));
- break;
- case Oneg:
- if (getintlit(args[0], &a))
- r = val(n->loc, -a, exprtype(n));
- break;
- case Obsl:
- if (getintlit(args[0], &a) && getintlit(args[1], &b))
- r = val(n->loc, a << b, exprtype(n));
- break;
- case Obsr:
- if (getintlit(args[0], &a) && getintlit(args[1], &b))
- r = val(n->loc, a >> b, exprtype(n));
- break;
- case Obor:
- if (getintlit(args[0], &a) && getintlit(args[1], &b))
- r = val(n->loc, a | b, exprtype(n));
- break;
- case Oband:
- if (getintlit(args[0], &a) && getintlit(args[1], &b))
- r = val(n->loc, a & b, exprtype(n));
- break;
- case Obxor:
- if (getintlit(args[0], &a) && getintlit(args[1], &b))
- r = val(n->loc, 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 Oarr:
- qsort(n->expr.args, n->expr.nargs, sizeof(Node*), idxcmp);
- 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;
+ 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;
+ if (n->expr.idx)
+ n->expr.idx = fold(n->expr.idx, foldvar);
+ 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 (isintval(args[0], 0))
+ r = args[1];
+ if (isintval(args[1], 0))
+ r = args[0];
+ if (getintlit(args[0], &a) && getintlit(args[1], &b))
+ r = val(n->loc, a + b, exprtype(n));
+ break;
+ case Osub:
+ /* x - 0 = 0 */
+ if (isintval(args[1], 0))
+ r = args[0];
+ if (getintlit(args[0], &a) && getintlit(args[1], &b))
+ r = val(n->loc, a - b, exprtype(n));
+ break;
+ case Omul:
+ /* 1 * x = x */
+ if (isintval(args[0], 1))
+ r = args[1];
+ if (isintval(args[1], 1))
+ r = args[0];
+ /* 0 * x = 0 */
+ if (isintval(args[0], 0))
+ r = args[0];
+ if (isintval(args[1], 0))
+ r = args[1];
+ if (getintlit(args[0], &a) && getintlit(args[1], &b))
+ r = val(n->loc, a * b, exprtype(n));
+ break;
+ case Odiv:
+ /* x/0 = error */
+ if (isintval(args[1], 0))
+ fatal(args[1], "division by zero");
+ /* x/1 = x */
+ if (isintval(args[1], 1))
+ r = args[0];
+ /* 0/x = 0 */
+ if (isintval(args[1], 0))
+ r = args[1];
+ if (getintlit(args[0], &a) && getintlit(args[1], &b))
+ r = val(n->loc, a / b, exprtype(n));
+ break;
+ case Omod:
+ /* x%1 = x */
+ if (isintval(args[1], 0))
+ r = args[0];
+ if (getintlit(args[0], &a) && getintlit(args[1], &b))
+ r = val(n->loc, a % b, exprtype(n));
+ break;
+ case Oneg:
+ if (getintlit(args[0], &a))
+ r = val(n->loc, -a, exprtype(n));
+ break;
+ case Obsl:
+ if (getintlit(args[0], &a) && getintlit(args[1], &b))
+ r = val(n->loc, a << b, exprtype(n));
+ break;
+ case Obsr:
+ if (getintlit(args[0], &a) && getintlit(args[1], &b))
+ r = val(n->loc, a >> b, exprtype(n));
+ break;
+ case Obor:
+ if (getintlit(args[0], &a) && getintlit(args[1], &b))
+ r = val(n->loc, a | b, exprtype(n));
+ break;
+ case Oband:
+ if (getintlit(args[0], &a) && getintlit(args[1], &b))
+ r = val(n->loc, a & b, exprtype(n));
+ break;
+ case Obxor:
+ if (getintlit(args[0], &a) && getintlit(args[1], &b))
+ r = val(n->loc, 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 Oarr:
+ qsort(n->expr.args, n->expr.nargs, sizeof(Node*), idxcmp);
+ 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;
}
diff --git a/mi/match.c b/mi/match.c
index 2588f59..df335f8 100644
--- a/mi/match.c
+++ b/mi/match.c
@@ -14,26 +14,26 @@
typedef struct Dtree Dtree;
struct Dtree {
- int id;
- Srcloc loc;
-
- /* values for matching */
- Node *lbl;
- Node *load;
- size_t nconstructors;
- int accept;
- int emitted;
-
- /* the decision tree step */
- Node **pat;
- size_t npat;
- Dtree **next;
- size_t nnext;
- Dtree *any;
-
- /* captured variables and action */
- Node **cap;
- size_t ncap;
+ int id;
+ Srcloc loc;
+
+ /* values for matching */
+ Node *lbl;
+ Node *load;
+ size_t nconstructors;
+ int accept;
+ int emitted;
+
+ /* the decision tree step */
+ Node **pat;
+ size_t npat;
+ Dtree **next;
+ size_t nnext;
+ Dtree *any;
+
+ /* captured variables and action */
+ Node **cap;
+ size_t ncap;
};
@@ -44,752 +44,752 @@ void dtreedump(FILE *fd, Dtree *dt);
static Node *utag(Node *n)
{
- Node *tag;
+ Node *tag;
- tag = mkexpr(n->loc, Outag, n, NULL);
- tag->expr.type = mktype(n->loc, Tyint32);
- return tag;
+ tag = mkexpr(n->loc, Outag, n, NULL);
+ tag->expr.type = mktype(n->loc, Tyint32);
+ return tag;
}
static Node *uvalue(Node *n, Type *ty)
{
- Node *elt;
+ Node *elt;
- elt = mkexpr(n->loc, Oudata, n, NULL);
- elt->expr.type = ty;
- return elt;
+ elt = mkexpr(n->loc, Oudata, n, NULL);
+ elt->expr.type = ty;
+ return elt;
}
static Node *tupelt(Node *n, size_t i)
{
- Node *idx, *elt;
+ Node *idx, *elt;
- idx = mkintlit(n->loc, i);
- idx->expr.type = mktype(n->loc, Tyuint64);
- elt = mkexpr(n->loc, Otupget, n, idx, NULL);
- elt->expr.type = tybase(exprtype(n))->sub[i];
- return elt;
+ idx = mkintlit(n->loc, i);
+ idx->expr.type = mktype(n->loc, Tyuint64);
+ elt = mkexpr(n->loc, Otupget, n, idx, NULL);
+ elt->expr.type = tybase(exprtype(n))->sub[i];
+ return elt;
}
static Node *arrayelt(Node *n, size_t i)
{
- Node *idx, *elt;
+ Node *idx, *elt;
- idx = mkintlit(n->loc, i);
- idx->expr.type = mktype(n->loc, Tyuint64);
- elt = mkexpr(n->loc, Oidx, n, idx, NULL);
- elt->expr.type = tybase(exprtype(n))->sub[0];
- return elt;
+ idx = mkintlit(n->loc, i);
+ idx->expr.type = mktype(n->loc, Tyuint64);
+ elt = mkexpr(n->loc, Oidx, n, idx, NULL);
+ elt->expr.type = tybase(exprtype(n))->sub[0];
+ return elt;
}
static Node *findmemb(Node *pat, Node *name)
{
- Node *n;
- size_t i;
-
- for (i = 0; i < pat->expr.nargs; i++) {
- n = pat->expr.args[i];
- if (nameeq(n->expr.idx, name))
- return n;
- }
- return NULL;
+ Node *n;
+ size_t i;
+
+ for (i = 0; i < pat->expr.nargs; i++) {
+ n = pat->expr.args[i];
+ if (nameeq(n->expr.idx, name))
+ return n;
+ }
+ return NULL;
}
static Dtree *dtbytag(Dtree *t, Ucon *uc)
{
- uint32_t tagval;
- Node *taglit;
- size_t i;
-
- for (i = 0; i < t->npat; i++) {
- taglit = t->pat[i]->expr.args[0];
- tagval = taglit->lit.intval;
- if (tagval == uc->id) {
- return t->next[i];
- }
- }
- return NULL;
+ uint32_t tagval;
+ Node *taglit;
+ size_t i;
+
+ for (i = 0; i < t->npat; i++) {
+ taglit = t->pat[i]->expr.args[0];
+ tagval = taglit->lit.intval;
+ if (tagval == uc->id) {
+ return t->next[i];
+ }
+ }
+ return NULL;
}
static Node *structmemb(Node *n, Node *name, Type *ty)
{
- Node *elt;
+ Node *elt;
- elt = mkexpr(n->loc, Omemb, n, name, NULL);
- elt->expr.type = ty;
- return elt;
+ elt = mkexpr(n->loc, Omemb, n, name, NULL);
+ elt->expr.type = ty;
+ return elt;
}
static Node *addcapture(Node *n, Node **cap, size_t ncap)
{
- Node **blk;
- size_t nblk, i;
-
- nblk = 0;
- blk = NULL;
-
- for (i = 0; i < ncap; i++)
- lappend(&blk, &nblk, cap[i]);
- for (i = 0; i < n->block.nstmts; i++)
- lappend(&blk, &nblk, n->block.stmts[i]);
- lfree(&n->block.stmts, &n->block.nstmts);
- n->block.stmts = blk;
- n->block.nstmts = nblk;
- return n;
+ Node **blk;
+ size_t nblk, i;
+
+ nblk = 0;
+ blk = NULL;
+
+ for (i = 0; i < ncap; i++)
+ lappend(&blk, &nblk, cap[i]);
+ for (i = 0; i < n->block.nstmts; i++)
+ lappend(&blk, &nblk, n->block.stmts[i]);
+ lfree(&n->block.stmts, &n->block.nstmts);
+ n->block.stmts = blk;
+ n->block.nstmts = nblk;
+ return n;
}
static Dtree *mkdtree(Srcloc loc, Node *lbl)
{
- static int ndtree;
- Dtree *t;
-
- t = zalloc(sizeof(Dtree));
- t->lbl = lbl;
- t->loc = loc;
- t->id = ndtree++;
- return t;
+ static int ndtree;
+ Dtree *t;
+
+ t = zalloc(sizeof(Dtree));
+ t->lbl = lbl;
+ t->loc = loc;
+ t->id = ndtree++;
+ return t;
}
static Dtree *nextnode(Srcloc loc, size_t idx, size_t count, Dtree *accept)
{
- if (idx == count - 1)
- return accept;
- else
- return mkdtree(loc, genlbl(loc));
+ if (idx == count - 1)
+ return accept;
+ else
+ return mkdtree(loc, genlbl(loc));
}
static size_t nconstructors(Type *t)
{
- if (!t)
- return 0;
-
- t = tybase(t);
- switch (t->type) {
- case Tyvoid: return 0; break;
- case Tybool: return 2; break;
- case Tychar: return 0x10ffff; break;
-
- /* signed ints */
- case Tyint8: return 0x100; break;
- case Tyint16: return 0x10000; break;
- case Tyint32: return 0x100000000; break;
- case Tyint: return 0x100000000; break;
- case Tyint64: return ~0ull; break;
-
- /* unsigned ints */
- case Tybyte: return 0x100; break;
- case Tyuint8: return 0x100; break;
- case Tyuint16: return 0x10000; break;
- case Tyuint32: return 0x100000000; break;
- case Tyuint: return 0x100000000; break;
- case Tyuint64: return ~0ull; break;
-
- /* floats */
- case Tyflt32: return ~0ull; break;
- case Tyflt64: return ~0ull; break;
-
- /* complex types */
- case Typtr: return 1; break;
- case Tyarray: return 1; break;
- case Tytuple: return 1; break;
- case Tystruct: return 1;
- case Tyunion: return t->nmemb; break;
- case Tyslice: return ~0ULL; break;
-
- case Tyvar: case Typaram: case Tyunres: case Tyname:
- case Tybad: case Tyvalist: case Tygeneric: case Ntypes:
- case Tyfunc: case Tycode:
- die("Invalid constructor type %s in match", tystr(t));
- break;
- }
- return 0;
+ if (!t)
+ return 0;
+
+ t = tybase(t);
+ switch (t->type) {
+ case Tyvoid: return 0; break;
+ case Tybool: return 2; break;
+ case Tychar: return 0x10ffff; break;
+
+ /* signed ints */
+ case Tyint8: return 0x100; break;
+ case Tyint16: return 0x10000; break;
+ case Tyint32: return 0x100000000; break;
+ case Tyint: return 0x100000000; break;
+ case Tyint64: return ~0ull; break;
+
+ /* unsigned ints */
+ case Tybyte: return 0x100; break;
+ case Tyuint8: return 0x100; break;
+ case Tyuint16: return 0x10000; break;
+ case Tyuint32: return 0x100000000; break;
+ case Tyuint: return 0x100000000; break;
+ case Tyuint64: return ~0ull; break;
+
+ /* floats */
+ case Tyflt32: return ~0ull; break;
+ case Tyflt64: return ~0ull; break;
+
+ /* complex types */
+ case Typtr: return 1; break;
+ case Tyarray: return 1; break;
+ case Tytuple: return 1; break;
+ case Tystruct: return 1;
+ case Tyunion: return t->nmemb; break;
+ case Tyslice: return ~0ULL; break;
+
+ case Tyvar: case Typaram: case Tyunres: case Tyname:
+ case Tybad: case Tyvalist: case Tygeneric: case Ntypes:
+ case Tyfunc: case Tycode:
+ die("Invalid constructor type %s in match", tystr(t));
+ break;
+ }
+ return 0;
}
static int verifymatch(Dtree *t)
{
- size_t i;
- int ret;
-
- if (t->accept)
- return 1;
-
- ret = 0;
- if (t->nnext == t->nconstructors || t->any)
- ret = 1;
- for (i = 0; i < t->nnext; i++)
- if (!verifymatch(t->next[i]))
- ret = 0;
- return ret;
+ size_t i;
+ int ret;
+
+ if (t->accept)
+ return 1;
+
+ ret = 0;
+ if (t->nnext == t->nconstructors || t->any)
+ ret = 1;
+ for (i = 0; i < t->nnext; i++)
+ if (!verifymatch(t->next[i]))
+ ret = 0;
+ return ret;
}
static int acceptall(Dtree *t, Dtree *accept)
{
- size_t i;
- int ret;
-
- if (t->any == accept)
- return 0;
-
- ret = 0;
- if (t->any) {
- if (acceptall(t->any, accept))
- ret = 1;
- } else {
- t->any = accept;
- ret = 1;
- }
-
- for (i = 0; i < t->nnext; i++)
- if (acceptall(t->next[i], accept))
- ret = 1;
- return ret;
+ size_t i;
+ int ret;
+
+ if (t->any == accept)
+ return 0;
+
+ ret = 0;
+ if (t->any) {
+ if (acceptall(t->any, accept))
+ ret = 1;
+ } else {
+ t->any = accept;
+ ret = 1;
+ }
+
+ for (i = 0; i < t->nnext; i++)
+ if (acceptall(t->next[i], accept))
+ ret = 1;
+ return ret;
}
static int addwildrec(Srcloc loc, Type *ty, Dtree *start, Dtree *accept, Dtree ***end, size_t *nend)
{
- Dtree *next, **last, **tail;
- size_t i, j, nelt, nlast, ntail;
- Node *asize;
- Ucon *uc;
- int ret;
-
- tail = NULL;
- ntail = 0;
- ty = tybase(ty);
- if (istyprimitive(ty)) {
- for (i = 0; i < start->nnext; i++)
- lappend(end, nend, start->next[i]);
- if (start->any) {
- lappend(end, nend, start->any);
- return 0;
- } else {
- start->any = accept;
- lappend(end, nend, accept);
- return 1;
- }
- }
-
- ret = 0;
- last = NULL;
- nlast = 0;
- lappend(&last, &nlast, start);
- switch (ty->type) {
- case Tytuple:
- for (i = 0; i < ty->nsub; i++) {
- next = nextnode(loc, i, ty->nsub, accept);
- tail = NULL;
- ntail = 0;
- for (j = 0; j < nlast; j++)
- if (addwildrec(loc, ty->sub[i], last[j], next, &tail, &ntail))
- ret = 1;
- lfree(&last, &nlast);
- last = tail;
- nlast = ntail;
- }
- break;
- case Tyarray:
- asize = fold(ty->asize, 1);
- nelt = asize->expr.args[0]->lit.intval;
- for (i = 0; i < nelt; i++) {
- next = nextnode(loc, i, nelt, accept);
- tail = NULL;
- ntail = 0;
- for (j = 0; j < nlast; j++)
- if (addwildrec(loc, ty->sub[0], last[j], next, &tail, &ntail))
- ret = 1;
- lfree(&last, &nlast);
- last = tail;
- nlast = ntail;
- }
- break;
- case Tystruct:
- for (i = 0; i < ty->nmemb; i++) {
- next = nextnode(loc, i, ty->nmemb, accept);
- tail = NULL;
- ntail = 0;
- for (j = 0; j < nlast; j++)
- if (addwildrec(loc, decltype(ty->sdecls[i]), last[j], next, &tail, &ntail))
- ret = 1;
- lfree(&last, &nlast);
- last = tail;
- nlast = ntail;
- }
- break;
- case Tyunion:
- for (i = 0; i < ty->nmemb; i++) {
- uc = ty->udecls[i];
- next = dtbytag(start, uc);
- if (next) {
- if (uc->etype) {
- if (addwildrec(loc, uc->etype, next, accept, end, nend))
- ret = 1;
- } else {
- lappend(end, nend, next);
- }
- }
- }
- if (!start->any) {
- start->any = accept;
- ret = 1;
- }
- lappend(end, nend, start->any);
- break;
- case Tyslice:
- ret = acceptall(start, accept);
- lappend(&last, &nlast, accept);
- break;
- default:
- lappend(&last, &nlast, accept);
- break;
- }
- lcat(end, nend, last, nlast);
- lfree(&last, &nlast);
- return ret;
+ Dtree *next, **last, **tail;
+ size_t i, j, nelt, nlast, ntail;
+ Node *asize;
+ Ucon *uc;
+ int ret;
+
+ tail = NULL;
+ ntail = 0;
+ ty = tybase(ty);
+ if (istyprimitive(ty)) {
+ for (i = 0; i < start->nnext; i++)
+ lappend(end, nend, start->next[i]);
+ if (start->any) {
+ lappend(end, nend, start->any);
+ return 0;
+ } else {
+ start->any = accept;
+ lappend(end, nend, accept);
+ return 1;
+ }
+ }
+
+ ret = 0;
+ last = NULL;
+ nlast = 0;
+ lappend(&last, &nlast, start);
+ switch (ty->type) {
+ case Tytuple:
+ for (i = 0; i < ty->nsub; i++) {
+ next = nextnode(loc, i, ty->nsub, accept);
+ tail = NULL;
+ ntail = 0;
+ for (j = 0; j < nlast; j++)
+ if (addwildrec(loc, ty->sub[i], last[j], next, &tail, &ntail))
+ ret = 1;
+ lfree(&last, &nlast);
+ last = tail;
+ nlast = ntail;
+ }
+ break;
+ case Tyarray:
+ asize = fold(ty->asize, 1);
+ nelt = asize->expr.args[0]->lit.intval;
+ for (i = 0; i < nelt; i++) {
+ next = nextnode(loc, i, nelt, accept);
+ tail = NULL;
+ ntail = 0;
+ for (j = 0; j < nlast; j++)
+ if (addwildrec(loc, ty->sub[0], last[j], next, &tail, &ntail))
+ ret = 1;
+ lfree(&last, &nlast);
+ last = tail;
+ nlast = ntail;
+ }
+ break;
+ case Tystruct:
+ for (i = 0; i < ty->nmemb; i++) {
+ next = nextnode(loc, i, ty->nmemb, accept);
+ tail = NULL;
+ ntail = 0;
+ for (j = 0; j < nlast; j++)
+ if (addwildrec(loc, decltype(ty->sdecls[i]), last[j], next, &tail, &ntail))
+ ret = 1;
+ lfree(&last, &nlast);
+ last = tail;
+ nlast = ntail;
+ }
+ break;
+ case Tyunion:
+ for (i = 0; i < ty->nmemb; i++) {
+ uc = ty->udecls[i];
+ next = dtbytag(start, uc);
+ if (next) {
+ if (uc->etype) {
+ if (addwildrec(loc, uc->etype, next, accept, end, nend))
+ ret = 1;
+ } else {
+ lappend(end, nend, next);
+ }
+ }
+ }
+ if (!start->any) {
+ start->any = accept;
+ ret = 1;
+ }
+ lappend(end, nend, start->any);
+ break;
+ case Tyslice:
+ ret = acceptall(start, accept);
+ lappend(&last, &nlast, accept);
+ break;
+ default:
+ lappend(&last, &nlast, accept);
+ break;
+ }
+ lcat(end, nend, last, nlast);
+ lfree(&last, &nlast);
+ return ret;
}
static int addwild(Node *pat, Node *val, Dtree *start, Dtree *accept, Node ***cap, size_t *ncap, Dtree ***end, size_t *nend)
{
- Node *asn;
-
- asn = mkexpr(pat->loc, Oasn, pat, val, NULL);
- asn->expr.type = exprtype(pat);
- if (cap && ncap) {
- asn = mkexpr(pat->loc, Oasn, pat, val, NULL);
- asn->expr.type = exprtype(pat);
- lappend(cap, ncap, asn);
- }
- return addwildrec(pat->loc, exprtype(pat), start, accept, end, nend);
+ Node *asn;
+
+ asn = mkexpr(pat->loc, Oasn, pat, val, NULL);
+ asn->expr.type = exprtype(pat);
+ if (cap && ncap) {
+ asn = mkexpr(pat->loc, Oasn, pat, val, NULL);
+ asn->expr.type = exprtype(pat);
+ lappend(cap, ncap, asn);
+ }
+ return addwildrec(pat->loc, exprtype(pat), start, accept, end, nend);
}
static int addunion(Node *pat, Node *val, Dtree *start, Dtree *accept, Node ***cap, size_t *ncap, Dtree ***end, size_t *nend)
{
- Node *tagid;
- Dtree *next;
- Ucon *uc;
-
- if (start->any) {
- lappend(end, nend, start->any);
- return 0;
- }
-
- uc = finducon(tybase(exprtype(pat)), pat->expr.args[0]);
- next = dtbytag(start, uc);
- if (next) {
- if (!uc->etype) {
- lappend(end, nend, next);
- return 0;
- } else {
- return addpat(pat->expr.args[1], uvalue(val, uc->etype), next, accept, cap, ncap, end, nend);
- }
- }
-
- if (!start->load) {
- start->load = utag(val);
- start->nconstructors = nconstructors(tybase(exprtype(pat)));
- }
-
- tagid = mkintlit(pat->loc, uc->id);
- tagid->expr.type = mktype(pat->loc, Tyint32);
- lappend(&start->pat, &start->npat, tagid);
- if (uc->etype) {
- next = mkdtree(pat->loc, genlbl(pat->loc));
- lappend(&start->next, &start->nnext, next);
- addpat(pat->expr.args[1], uvalue(val, uc->etype), next, accept, cap, ncap, end, nend);
- } else {
- lappend(&start->next, &start->nnext, accept);
- lappend(end, nend, accept);
- }
- return 1;
+ Node *tagid;
+ Dtree *next;
+ Ucon *uc;
+
+ if (start->any) {
+ lappend(end, nend, start->any);
+ return 0;
+ }
+
+ uc = finducon(tybase(exprtype(pat)), pat->expr.args[0]);
+ next = dtbytag(start, uc);
+ if (next) {
+ if (!uc->etype) {
+ lappend(end, nend, next);
+ return 0;
+ } else {
+ return addpat(pat->expr.args[1], uvalue(val, uc->etype), next, accept, cap, ncap, end, nend);
+ }
+ }
+
+ if (!start->load) {
+ start->load = utag(val);
+ start->nconstructors = nconstructors(tybase(exprtype(pat)));
+ }
+
+ tagid = mkintlit(pat->loc, uc->id);
+ tagid->expr.type = mktype(pat->loc, Tyint32);
+ lappend(&start->pat, &start->npat, tagid);
+ if (uc->etype) {
+ next = mkdtree(pat->loc, genlbl(pat->loc));
+ lappend(&start->next, &start->nnext, next);
+ addpat(pat->expr.args[1], uvalue(val, uc->etype), next, accept, cap, ncap, end, nend);
+ } else {
+ lappend(&start->next, &start->nnext, accept);
+ lappend(end, nend, accept);
+ }
+ return 1;
}
static int addstr(Node *pat, Node *val, Dtree *start, Dtree *accept, Node ***cap, size_t *ncap, Dtree ***end, size_t *nend)
{
- Dtree **tail, **last, *next;
- size_t i, j, n, ntail, nlast;
- Node *p, *v, *lit;
- Type *ty;
- char *s;
- int ret;
-
- lit = pat->expr.args[0];
- n = lit->lit.strval.len;
- s = lit->lit.strval.buf;
-
- ty = mktype(pat->loc, Tyuint64);
- p = mkintlit(lit->loc, n);
- v = structmemb(val, mkname(pat->loc, "len"), ty);
- p->expr.type = ty;
-
- if (n == 0)
- next = accept;
- else
- next = mkdtree(pat->loc, genlbl(pat->loc));
-
- last = NULL;
- nlast = 0;
- if (addpat(p, v, start, next, cap, ncap, &last, &nlast))
- ret = 1;
-
- ty = mktype(pat->loc, Tybyte);
- for (i = 0; i < n; i++) {
- p = mkintlit(lit->loc, s[i]);
- p->expr.type = ty;
- v = arrayelt(val, i);
-
- tail = NULL;
- ntail = 0;
- next = nextnode(pat->loc, i, n, accept);
- for (j = 0; j < nlast; j++)
- if (addpat(p, v, last[j], next, NULL, NULL, &tail, &ntail))
- ret = 1;
- lfree(&last, &nlast);
- last = tail;
- nlast = ntail;
- }
- lcat(end, nend, last, nlast);
- lfree(&last, &nlast);
- return ret;
+ Dtree **tail, **last, *next;
+ size_t i, j, n, ntail, nlast;
+ Node *p, *v, *lit;
+ Type *ty;
+ char *s;
+ int ret;
+
+ lit = pat->expr.args[0];
+ n = lit->lit.strval.len;
+ s = lit->lit.strval.buf;
+
+ ty = mktype(pat->loc, Tyuint64);
+ p = mkintlit(lit->loc, n);
+ v = structmemb(val, mkname(pat->loc, "len"), ty);
+ p->expr.type = ty;
+
+ if (n == 0)
+ next = accept;
+ else
+ next = mkdtree(pat->loc, genlbl(pat->loc));
+
+ last = NULL;
+ nlast = 0;
+ if (addpat(p, v, start, next, cap, ncap, &last, &nlast))
+ ret = 1;
+
+ ty = mktype(pat->loc, Tybyte);
+ for (i = 0; i < n; i++) {
+ p = mkintlit(lit->loc, s[i]);
+ p->expr.type = ty;
+ v = arrayelt(val, i);
+
+ tail = NULL;
+ ntail = 0;
+ next = nextnode(pat->loc, i, n, accept);
+ for (j = 0; j < nlast; j++)
+ if (addpat(p, v, last[j], next, NULL, NULL, &tail, &ntail))
+ ret = 1;
+ lfree(&last, &nlast);
+ last = tail;
+ nlast = ntail;
+ }
+ lcat(end, nend, last, nlast);
+ lfree(&last, &nlast);
+ return ret;
}
static int addlit(Node *pat, Node *val, Dtree *start, Dtree *accept, Node ***cap, size_t *ncap, Dtree ***end, size_t *nend)
{
- size_t i;
-
- if (pat->expr.args[0]->lit.littype == Lstr) {
- return addstr(pat, val, start, accept, cap, ncap, end, nend);
- } else {
- /* if we already have a match, we're not adding a new node */
- if (start->any) {
- lappend(end, nend, start->any);
- return 0;
- }
-
- for (i = 0; i < start->npat; i++) {
- if (liteq(start->pat[i]->expr.args[0], pat->expr.args[0])) {
- lappend(end, nend, start->next[i]);
- return 0;
- }
- }
-
- /* wire up an edge from start to 'accept' */
- if (!start->load) {
- start->load = val;
- start->nconstructors = nconstructors(exprtype(pat));
- }
- lappend(&start->pat, &start->npat, pat);
- lappend(&start->next, &start->nnext, accept);
- lappend(end, nend, accept);
- return 1;
- }
+ size_t i;
+
+ if (pat->expr.args[0]->lit.littype == Lstr) {
+ return addstr(pat, val, start, accept, cap, ncap, end, nend);
+ } else {
+ /* if we already have a match, we're not adding a new node */
+ if (start->any) {
+ lappend(end, nend, start->any);
+ return 0;
+ }
+
+ for (i = 0; i < start->npat; i++) {
+ if (liteq(start->pat[i]->expr.args[0], pat->expr.args[0])) {
+ lappend(end, nend, start->next[i]);
+ return 0;
+ }
+ }
+
+ /* wire up an edge from start to 'accept' */
+ if (!start->load) {
+ start->load = val;
+ start->nconstructors = nconstructors(exprtype(pat));
+ }
+ lappend(&start->pat, &start->npat, pat);
+ lappend(&start->next, &start->nnext, accept);
+ lappend(end, nend, accept);
+ return 1;
+ }
}
static int addtup(Node *pat, Node *val, Dtree *start, Dtree *accept, Node ***cap, size_t *ncap, Dtree ***end, size_t *nend)
{
- size_t nargs, nlast, ntail, i, j;
- Dtree *next, **last, **tail;
- Node **args;
- int ret;
-
- args = pat->expr.args;
- nargs = pat->expr.nargs;
- last = NULL;
- nlast = 0;
- lappend(&last, &nlast, start);
- ret = 0;
-
- for (i = 0; i < nargs; i++) {
- next = nextnode(args[i]->loc, i, nargs, accept);
- tail = NULL;
- ntail = 0;
- for (j = 0; j < nlast; j++)
- if (addpat(pat->expr.args[i], tupelt(val, i), last[j], next, cap, ncap, &tail, &ntail))
- ret = 1;
- lfree(&last, &nlast);
- last = tail;
- nlast = ntail;
- }
- lcat(end, nend, last, nlast);
- lfree(&last, &nlast);
- return ret;
+ size_t nargs, nlast, ntail, i, j;
+ Dtree *next, **last, **tail;
+ Node **args;
+ int ret;
+
+ args = pat->expr.args;
+ nargs = pat->expr.nargs;
+ last = NULL;
+ nlast = 0;
+ lappend(&last, &nlast, start);
+ ret = 0;
+
+ for (i = 0; i < nargs; i++) {
+ next = nextnode(args[i]->loc, i, nargs, accept);
+ tail = NULL;
+ ntail = 0;
+ for (j = 0; j < nlast; j++)
+ if (addpat(pat->expr.args[i], tupelt(val, i), last[j], next, cap, ncap, &tail, &ntail))
+ ret = 1;
+ lfree(&last, &nlast);
+ last = tail;
+ nlast = ntail;
+ }
+ lcat(end, nend, last, nlast);
+ lfree(&last, &nlast);
+ return ret;
}
static int addarr(Node *pat, Node *val, Dtree *start, Dtree *accept, Node ***cap, size_t *ncap, Dtree ***end, size_t *nend)
{
- size_t nargs, nlast, ntail, i, j;
- Dtree *next, **last, **tail;
- Node **args;
- int ret;
-
- args = pat->expr.args;
- nargs = pat->expr.nargs;
- last = NULL;
- nlast = 0;
- lappend(&last, &nlast, start);
- ret = 0;
-
- for (i = 0; i < nargs; i++) {
- next = nextnode(args[i]->loc, i, nargs, accept);
- tail = NULL;
- ntail = 0;
- for (j = 0; j < nlast; j++)
- if (addpat(pat->expr.args[i], arrayelt(val, i), last[j], next, cap, ncap, &tail, &ntail))
- ret = 1;
- lfree(&last, &nlast);
- last = tail;
- nlast = ntail;
- }
- lcat(end, nend, last, nlast);
- lfree(&last, &nlast);
- return ret;
+ size_t nargs, nlast, ntail, i, j;
+ Dtree *next, **last, **tail;
+ Node **args;
+ int ret;
+
+ args = pat->expr.args;
+ nargs = pat->expr.nargs;
+ last = NULL;
+ nlast = 0;
+ lappend(&last, &nlast, start);
+ ret = 0;
+
+ for (i = 0; i < nargs; i++) {
+ next = nextnode(args[i]->loc, i, nargs, accept);
+ tail = NULL;
+ ntail = 0;
+ for (j = 0; j < nlast; j++)
+ if (addpat(pat->expr.args[i], arrayelt(val, i), last[j], next, cap, ncap, &tail, &ntail))
+ ret = 1;
+ lfree(&last, &nlast);
+ last = tail;
+ nlast = ntail;
+ }
+ lcat(end, nend, last, nlast);
+ lfree(&last, &nlast);
+ return ret;
}
static int addstruct(Node *pat, Node *val, Dtree *start, Dtree *accept, Node ***cap, size_t *ncap, Dtree ***end, size_t *nend)
{
- Dtree *next, **last, **tail;
- Node *memb, *name;
- Type *ty, *mty;
- size_t i, j, ntail, nlast;
- int ret;
-
- ret = 0;
- last = NULL;
- nlast = 0;
- lappend(&last, &nlast, start);
- ty = tybase(exprtype(pat));
-
- for (i = 0; i < ty->nmemb; i++) {
- mty = decltype(ty->sdecls[i]);
- name = ty->sdecls[i]->decl.name;
- memb = findmemb(pat, name);
- next = nextnode(pat->loc, i, ty->nmemb, accept);
- tail = NULL;
- ntail = 0;
-
- for (j = 0; j < nlast; j++) {
- /* add a _ capture if we don't specify the value */
- if (!memb) {
- if (addwild(memb, NULL, last[j], next, NULL, NULL, &tail, &ntail))
- ret = 1;
- } else {
- if (addpat(memb, structmemb(val, name, mty), last[j], next, cap, ncap, &tail, &ntail))
- ret = 1;
- }
- }
- lfree(&last, &nlast);
- last = tail;
- nlast = ntail;
- }
- lcat(end, nend, last, nlast);
- lfree(&last, &nlast);
- return ret;
+ Dtree *next, **last, **tail;
+ Node *memb, *name;
+ Type *ty, *mty;
+ size_t i, j, ntail, nlast;
+ int ret;
+
+ ret = 0;
+ last = NULL;
+ nlast = 0;
+ lappend(&last, &nlast, start);
+ ty = tybase(exprtype(pat));
+
+ for (i = 0; i < ty->nmemb; i++) {
+ mty = decltype(ty->sdecls[i]);
+ name = ty->sdecls[i]->decl.name;
+ memb = findmemb(pat, name);
+ next = nextnode(pat->loc, i, ty->nmemb, accept);
+ tail = NULL;
+ ntail = 0;
+
+ for (j = 0; j < nlast; j++) {
+ /* add a _ capture if we don't specify the value */
+ if (!memb) {
+ if (addwild(memb, NULL, last[j], next, NULL, NULL, &tail, &ntail))
+ ret = 1;
+ } else {
+ if (addpat(memb, structmemb(val, name, mty), last[j], next, cap, ncap, &tail, &ntail))
+ ret = 1;
+ }
+ }
+ lfree(&last, &nlast);
+ last = tail;
+ nlast = ntail;
+ }
+ lcat(end, nend, last, nlast);
+ lfree(&last, &nlast);
+ return ret;
}
static int addpat(Node *pat, Node *val, Dtree *start, Dtree *accept, Node ***cap, size_t *ncap, Dtree ***end, size_t *nend)
{
- int ret;
- Node *dcl;
-
- pat = fold(pat, 1);
- ret = 0;
- switch (exprop(pat)) {
- case Ovar:
- dcl = decls[pat->expr.did];
- if (dcl->decl.isconst)
- ret = addpat(dcl->decl.init, val, start, accept, cap, ncap, end, nend);
- else
- ret = addwild(pat, val, start, accept, cap, ncap, end, nend);
- break;
- case Oucon:
- ret = addunion(pat, val, start, accept, cap, ncap, end, nend);
- break;
- case Olit:
- ret = addlit(pat, val, start, accept, cap, ncap, end, nend);
- break;
- case Otup:
- ret = addtup(pat, val, start, accept, cap, ncap, end, nend);
- break;
- case Oarr:
- ret = addarr(pat, val, start, accept, cap, ncap, end, nend);
- break;
- case Ostruct:
- ret = addstruct(pat, val, start, accept, cap, ncap, end, nend);
- break;
- case Ogap:
- ret = addwild(pat, NULL, start, accept, NULL, NULL, end, nend);
- break;
- default:
- fatal(pat, "unsupported pattern %s of type %s", opstr[exprop(pat)], tystr(exprtype(pat)));
- break;
- }
- return ret;
+ int ret;
+ Node *dcl;
+
+ pat = fold(pat, 1);
+ ret = 0;
+ switch (exprop(pat)) {
+ case Ovar:
+ dcl = decls[pat->expr.did];
+ if (dcl->decl.isconst)
+ ret = addpat(dcl->decl.init, val, start, accept, cap, ncap, end, nend);
+ else
+ ret = addwild(pat, val, start, accept, cap, ncap, end, nend);
+ break;
+ case Oucon:
+ ret = addunion(pat, val, start, accept, cap, ncap, end, nend);
+ break;
+ case Olit:
+ ret = addlit(pat, val, start, accept, cap, ncap, end, nend);
+ break;
+ case Otup:
+ ret = addtup(pat, val, start, accept, cap, ncap, end, nend);
+ break;
+ case Oarr:
+ ret = addarr(pat, val, start, accept, cap, ncap, end, nend);
+ break;
+ case Ostruct:
+ ret = addstruct(pat, val, start, accept, cap, ncap, end, nend);
+ break;
+ case Ogap:
+ ret = addwild(pat, NULL, start, accept, NULL, NULL, end, nend);
+ break;
+ default:
+ fatal(pat, "unsupported pattern %s of type %s", opstr[exprop(pat)], tystr(exprtype(pat)));
+ break;
+ }
+ return ret;
}
/* val must be a pure, fully evaluated value */
Dtree *gendtree(Node *m, Node *val, Node **lbl, size_t nlbl)
{
- Dtree *start, *accept, **end;
- Node **pat, **cap;
- size_t npat, ncap, nend;
- size_t i;
-
- pat = m->matchstmt.matches;
- npat = m->matchstmt.nmatches;
-
- end = NULL;
- nend = 0;
- start = mkdtree(m->loc, genlbl(m->loc));
- for (i = 0; i < npat; i++) {
- cap = NULL;
- ncap = 0;
- accept = mkdtree(lbl[i]->loc, lbl[i]);
- accept->accept = 1;
-
- if (!addpat(pat[i]->match.pat, val, start, accept, &cap, &ncap, &end, &nend))
- fatal(pat[i], "pattern matched by earlier case");
- addcapture(pat[i]->match.block, cap, ncap);
- }
- if (!verifymatch(start))
- fatal(m, "nonexhaustive pattern set in match statement");
- return start;
+ Dtree *start, *accept, **end;
+ Node **pat, **cap;
+ size_t npat, ncap, nend;
+ size_t i;
+
+ pat = m->matchstmt.matches;
+ npat = m->matchstmt.nmatches;
+
+ end = NULL;
+ nend = 0;
+ start = mkdtree(m->loc, genlbl(m->loc));
+ for (i = 0; i < npat; i++) {
+ cap = NULL;
+ ncap = 0;
+ accept = mkdtree(lbl[i]->loc, lbl[i]);
+ accept->accept = 1;
+
+ if (!addpat(pat[i]->match.pat, val, start, accept, &cap, &ncap, &end, &nend))
+ fatal(pat[i], "pattern matched by earlier case");
+ addcapture(pat[i]->match.block, cap, ncap);
+ }
+ if (!verifymatch(start))
+ fatal(m, "nonexhaustive pattern set in match statement");
+ return start;
}
void genmatchcode(Dtree *dt, Node ***out, size_t *nout)
{
- Node *jmp, *eq, *fail;
- int emit;
- size_t i;
-
- if (dt->emitted)
- return;
- dt->emitted = 1;
-
- /* the we jump to the accept label when generating the parent */
- if (dt->accept) {
- jmp = mkexpr(dt->loc, Ojmp, dt->lbl, NULL);
- jmp->expr.type = mktype(dt->loc, Tyvoid);
- lappend(out, nout, jmp);
- return;
- }
-
- lappend(out, nout, dt->lbl);
- for (i = 0; i < dt->nnext; i++) {
- if (i == dt->nnext - 1 && dt->any) {
- fail = dt->any->lbl;
- emit = 0;
- } else {
- fail = genlbl(dt->loc);
- emit = 1;
- }
-
- eq = mkexpr(dt->loc, Oeq, dt->load, dt->pat[i], NULL);
- eq->expr.type = mktype(dt->loc, Tybool);
- jmp = mkexpr(dt->loc, Ocjmp, eq, dt->next[i]->lbl, fail, NULL);
- jmp->expr.type = mktype(dt->loc, Tyvoid);
- lappend(out, nout, jmp);
-
- genmatchcode(dt->next[i], out, nout);
- if (emit)
- lappend(out, nout, fail);
- }
- if (dt->any) {
- jmp = mkexpr(dt->loc, Ojmp, dt->any->lbl, NULL);
- jmp->expr.type = mktype(dt->loc, Tyvoid);
- lappend(out, nout, jmp);
- genmatchcode(dt->any, out, nout);
- }
+ Node *jmp, *eq, *fail;
+ int emit;
+ size_t i;
+
+ if (dt->emitted)
+ return;
+ dt->emitted = 1;
+
+ /* the we jump to the accept label when generating the parent */
+ if (dt->accept) {
+ jmp = mkexpr(dt->loc, Ojmp, dt->lbl, NULL);
+ jmp->expr.type = mktype(dt->loc, Tyvoid);
+ lappend(out, nout, jmp);
+ return;
+ }
+
+ lappend(out, nout, dt->lbl);
+ for (i = 0; i < dt->nnext; i++) {
+ if (i == dt->nnext - 1 && dt->any) {
+ fail = dt->any->lbl;
+ emit = 0;
+ } else {
+ fail = genlbl(dt->loc);
+ emit = 1;
+ }
+
+ eq = mkexpr(dt->loc, Oeq, dt->load, dt->pat[i], NULL);
+ eq->expr.type = mktype(dt->loc, Tybool);
+ jmp = mkexpr(dt->loc, Ocjmp, eq, dt->next[i]->lbl, fail, NULL);
+ jmp->expr.type = mktype(dt->loc, Tyvoid);
+ lappend(out, nout, jmp);
+
+ genmatchcode(dt->next[i], out, nout);
+ if (emit)
+ lappend(out, nout, fail);
+ }
+ if (dt->any) {
+ jmp = mkexpr(dt->loc, Ojmp, dt->any->lbl, NULL);
+ jmp->expr.type = mktype(dt->loc, Tyvoid);
+ lappend(out, nout, jmp);
+ genmatchcode(dt->any, out, nout);
+ }
}
void genonematch(Node *pat, Node *val, Node *iftrue, Node *iffalse, Node ***out, size_t *nout, Node ***cap, size_t *ncap)
{
- Dtree *start, *accept, *reject, **end;
- size_t nend;
+ Dtree *start, *accept, *reject, **end;
+ size_t nend;
- end = NULL;
- nend = 0;
+ end = NULL;
+ nend = 0;
- start = mkdtree(pat->loc, genlbl(pat->loc));
- accept = mkdtree(iftrue->loc, iftrue);
- accept->accept = 1;
- reject = mkdtree(iffalse->loc, iffalse);
- reject->accept = 1;
+ start = mkdtree(pat->loc, genlbl(pat->loc));
+ accept = mkdtree(iftrue->loc, iftrue);
+ accept->accept = 1;
+ reject = mkdtree(iffalse->loc, iffalse);
+ reject->accept = 1;
- assert(addpat(pat, val, start, accept, cap, ncap, &end, &nend));
- acceptall(start, reject);
- genmatchcode(start, out, nout);
+ assert(addpat(pat, val, start, accept, cap, ncap, &end, &nend));
+ acceptall(start, reject);
+ genmatchcode(start, out, nout);
}
void genmatch(Node *m, Node *val, Node ***out, size_t *nout)
{
- Node **pat, **lbl, *end, *endlbl;
- size_t npat, nlbl, i;
- Dtree *dt;
-
- lbl = NULL;
- nlbl = 0;
-
- pat = m->matchstmt.matches;
- npat = m->matchstmt.nmatches;
- for (i = 0; i < npat; i++)
- lappend(&lbl, &nlbl, genlbl(pat[i]->match.block->loc));
-
-
- endlbl = genlbl(m->loc);
- dt = gendtree(m, val, lbl, nlbl);
- genmatchcode(dt, out, nout);
-
- for (i = 0; i < npat; i++) {
- end = mkexpr(pat[i]->loc, Ojmp, endlbl, NULL);
- end->expr.type = mktype(end->loc, Tyvoid);
- lappend(out, nout, lbl[i]);
- lappend(out, nout, pat[i]->match.block);
- lappend(out, nout, end);
- }
- lappend(out, nout, endlbl);
-
- if (debugopt['m']) {
- dtreedump(stdout, dt);
- for (i = 0; i < *nout; i++)
- dump((*out)[i], stdout);
- }
+ Node **pat, **lbl, *end, *endlbl;
+ size_t npat, nlbl, i;
+ Dtree *dt;
+
+ lbl = NULL;
+ nlbl = 0;
+
+ pat = m->matchstmt.matches;
+ npat = m->matchstmt.nmatches;
+ for (i = 0; i < npat; i++)
+ lappend(&lbl, &nlbl, genlbl(pat[i]->match.block->loc));
+
+
+ endlbl = genlbl(m->loc);
+ dt = gendtree(m, val, lbl, nlbl);
+ genmatchcode(dt, out, nout);
+
+ for (i = 0; i < npat; i++) {
+ end = mkexpr(pat[i]->loc, Ojmp, endlbl, NULL);
+ end->expr.type = mktype(end->loc, Tyvoid);
+ lappend(out, nout, lbl[i]);
+ lappend(out, nout, pat[i]->match.block);
+ lappend(out, nout, end);
+ }
+ lappend(out, nout, endlbl);
+
+ if (debugopt['m']) {
+ dtreedump(stdout, dt);
+ for (i = 0; i < *nout; i++)
+ dump((*out)[i], stdout);
+ }
}
void dtreedumplit(FILE *fd, Dtree *dt, Node *n, size_t depth)
{
- char *s;
-
- s = lblstr(dt->lbl);
- switch (n->lit.littype) {
- case Lchr: findentf(fd, depth, "%s: Lchr %c\n", s, n->lit.chrval); break;
- case Lbool: findentf(fd, depth, "%s: Lbool %s\n", s, n->lit.boolval ? "true" : "false"); break;
- case Lint: findentf(fd, depth, "%s: Lint %llu\n", s, n->lit.intval); break;
- case Lflt: findentf(fd, depth, "%s: Lflt %lf\n", s, n->lit.fltval); break;
- case Lstr: findentf(fd, depth, "%s: Lstr %.*s\n", s, (int)n->lit.strval.len, n->lit.strval.buf); break;
- case Llbl: findentf(fd, depth, "%s: Llbl %s\n", s, n->lit.lblval); break;
- case Lfunc: findentf(fd, depth, "%s: Lfunc\n"); break;
- }
+ char *s;
+
+ s = lblstr(dt->lbl);
+ switch (n->lit.littype) {
+ case Lchr: findentf(fd, depth, "%s: Lchr %c\n", s, n->lit.chrval); break;
+ case Lbool: findentf(fd, depth, "%s: Lbool %s\n", s, n->lit.boolval ? "true" : "false"); break;
+ case Lint: findentf(fd, depth, "%s: Lint %llu\n", s, n->lit.intval); break;
+ case Lflt: findentf(fd, depth, "%s: Lflt %lf\n", s, n->lit.fltval); break;
+ case Lstr: findentf(fd, depth, "%s: Lstr %.*s\n", s, (int)n->lit.strval.len, n->lit.strval.buf); break;
+ case Llbl: findentf(fd, depth, "%s: Llbl %s\n", s, n->lit.lblval); break;
+ case Lfunc: findentf(fd, depth, "%s: Lfunc\n"); break;
+ }
}
void dtreedumpnode(FILE *fd, Dtree *dt, size_t depth)
{
- size_t i;
-
- if (dt->accept)
- findentf(fd, depth, "%s: accept\n", lblstr(dt->lbl));
-
- for (i = 0; i < dt->nnext; i++) {
- dtreedumplit(fd, dt, dt->pat[i]->expr.args[0], depth);
- dtreedumpnode(fd, dt->next[i], depth + 1);
- }
- if (dt->any) {
- findentf(fd, depth, "%s: wildcard\n", lblstr(dt->lbl));
- dtreedumpnode(fd, dt->any, depth + 1);
- }
+ size_t i;
+
+ if (dt->accept)
+ findentf(fd, depth, "%s: accept\n", lblstr(dt->lbl));
+
+ for (i = 0; i < dt->nnext; i++) {
+ dtreedumplit(fd, dt, dt->pat[i]->expr.args[0], depth);
+ dtreedumpnode(fd, dt->next[i], depth + 1);
+ }
+ if (dt->any) {
+ findentf(fd, depth, "%s: wildcard\n", lblstr(dt->lbl));
+ dtreedumpnode(fd, dt->any, depth + 1);
+ }
}
void dtreedump(FILE *fd, Dtree *dt)
{
- dtreedumpnode(fd, dt, 0);
+ dtreedumpnode(fd, dt, 0);
}
diff --git a/mi/mi.h b/mi/mi.h
index 0b9c8a8..021a3f7 100644
--- a/mi/mi.h
+++ b/mi/mi.h
@@ -3,36 +3,36 @@ typedef struct Bb Bb;
typedef struct Reaching Reaching;
struct Cfg {
- Node *fn;
- 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;
+ Node *fn;
+ 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;
+ int id;
+ char **lbls;
+ size_t nlbls;
+ Node **nl;
+ size_t nnl;
+ Bitset *pred;
+ Bitset *succ;
};
struct Reaching {
- Bitset **in;
- Bitset **out;
- size_t **defs;
- size_t *ndefs;
+ Bitset **in;
+ Bitset **out;
+ size_t **defs;
+ size_t *ndefs;
};
/* expression folding */
diff --git a/mi/reaching.c b/mi/reaching.c
index 01bd798..aaaaedc 100644
--- a/mi/reaching.c
+++ b/mi/reaching.c
@@ -15,153 +15,138 @@
Node *assignee(Node *n)
{
- Node *a;
+ Node *a;
- switch (exprop(n)) {
- case Oundef: case Odef:
- case Oset:
- case Oasn: case Oaddeq:
- case Osubeq: case Omuleq:
- case Odiveq: case Omodeq:
- case Oboreq: case Obandeq:
- case Obxoreq: case Obsleq:
- case Obsreq:
- return n->expr.args[0];
- break;
- case Oblit:
- case Oclear:
- a = n->expr.args[0];
- if (exprop(a) != Oaddr)
- break;
- a = a->expr.args[0];
- if (exprop(a) != Ovar)
- break;
- return a;
- default:
- break;
- }
- return NULL;
+ switch (exprop(n)) {
+ case Oundef: case Odef:
+ case Oset:
+ case Oasn: case Oaddeq:
+ case Osubeq: case Omuleq:
+ case Odiveq: case Omodeq:
+ case Oboreq: case Obandeq:
+ case Obxoreq: case Obsleq:
+ case Obsreq:
+ return n->expr.args[0];
+ break;
+ case Oblit:
+ case Oclear:
+ a = n->expr.args[0];
+ if (exprop(a) != Oaddr)
+ break;
+ a = a->expr.args[0];
+ if (exprop(a) != Ovar)
+ break;
+ return a;
+ default:
+ break;
+ }
+ return NULL;
}
static void collectdefs(Cfg *cfg, size_t **defs, size_t *ndefs)
{
- size_t i, j, did;
- Node *n;
- Bb *bb;
+ size_t i, j, did;
+ Node *n;
+ Bb *bb;
- for (i = 0; i < cfg->nbb; i++) {
- bb = cfg->bb[i];
- if (!bb)
- continue;
- for (j = 0; j < bb->nnl; j++) {
- n = assignee(bb->nl[j]);
- if (n && exprop(n) == Ovar) {
- did = n->expr.did;
- ndefs[did]++;
- defs[did] = xrealloc(defs[did], ndefs[did] * sizeof(size_t));
- defs[did][ndefs[did] - 1] = bb->nl[j]->nid;
- }
- }
- }
+ for (i = 0; i < cfg->nbb; i++) {
+ bb = cfg->bb[i];
+ if (!bb)
+ continue;
+ for (j = 0; j < bb->nnl; j++) {
+ n = assignee(bb->nl[j]);
+ if (n && exprop(n) == Ovar) {
+ did = n->expr.did;
+ ndefs[did]++;
+ defs[did] = xrealloc(defs[did], ndefs[did] * sizeof(size_t));
+ defs[did][ndefs[did] - 1] = bb->nl[j]->nid;
+ }
+ }
+ }
}
static void genkill(Bb *bb, size_t **defs, size_t *ndefs, Bitset *gen, Bitset *kill)
{
- size_t i, j, did;
- Node *n;
+ size_t i, j, did;
+ Node *n;
- for (i = 0; i < bb->nnl; i++) {
- n = assignee(bb->nl[i]);
- if (!n)
- continue;
- did = n->expr.did;
- for (j = 0; j < ndefs[did]; j++) {
- bsput(kill, defs[did][j]);
- bsdel(gen, defs[did][j]);
- }
- bsput(gen, bb->nl[i]->nid);
- bsdel(kill, bb->nl[i]->nid);
- }
+ for (i = 0; i < bb->nnl; i++) {
+ n = assignee(bb->nl[i]);
+ if (!n)
+ continue;
+ did = n->expr.did;
+ for (j = 0; j < ndefs[did]; j++) {
+ bsput(kill, defs[did][j]);
+ bsdel(gen, defs[did][j]);
+ }
+ bsput(gen, bb->nl[i]->nid);
+ bsdel(kill, bb->nl[i]->nid);
+ }
}
void bsdump(Bitset *bs)
{
- size_t i;
- for (i = 0; bsiter(bs, &i); i++)
- printf("%zd ", i);
- printf("\n");
+ size_t i;
+ for (i = 0; bsiter(bs, &i); i++)
+ printf("%zd ", i);
+ printf("\n");
}
Reaching *reaching(Cfg *cfg)
{
- Bitset **in, **out;
- Bitset **gen, **kill;
- Bitset *bbin, *bbout;
- Reaching *reaching;
- size_t **defs; /* mapping from did => [def,list] */
- size_t *ndefs;
- size_t i, j;
- int changed;
+ Bitset **in, **out;
+ Bitset **gen, **kill;
+ Bitset *bbin, *bbout;
+ Reaching *reaching;
+ size_t **defs; /* mapping from did => [def,list] */
+ size_t *ndefs;
+ size_t i, j;
+ int changed;
- in = zalloc(cfg->nbb * sizeof(Bb*));
- out = zalloc(cfg->nbb * sizeof(Bb*));
- gen = zalloc(cfg->nbb * sizeof(Bb*));
- kill = zalloc(cfg->nbb * sizeof(Bb*));
- defs = zalloc(ndecls * sizeof(size_t*));
- ndefs = zalloc(ndecls * sizeof(size_t));
+ in = zalloc(cfg->nbb * sizeof(Bb*));
+ out = zalloc(cfg->nbb * sizeof(Bb*));
+ gen = zalloc(cfg->nbb * sizeof(Bb*));
+ kill = zalloc(cfg->nbb * sizeof(Bb*));
+ defs = zalloc(ndecls * sizeof(size_t*));
+ ndefs = zalloc(ndecls * sizeof(size_t));
- collectdefs(cfg, defs, ndefs);
- for (i = 0; i < cfg->nbb; i++) {
- in[i] = mkbs();
- out[i] = mkbs();
- gen[i] = mkbs();
- kill[i] = mkbs();
- if (cfg->bb[i])
- genkill(cfg->bb[i], defs, ndefs, gen[i], kill[i]);
- }
+ collectdefs(cfg, defs, ndefs);
+ for (i = 0; i < cfg->nbb; i++) {
+ in[i] = mkbs();
+ out[i] = mkbs();
+ gen[i] = mkbs();
+ kill[i] = mkbs();
+ if (cfg->bb[i])
+ genkill(cfg->bb[i], defs, ndefs, gen[i], kill[i]);
+ }
- do {
- changed = 0;
- for (i = 0; i < cfg->nbb; i++) {
- if (!cfg->bb[i])
- continue;
- bbin = mkbs();
- for (j = 0; bsiter(cfg->bb[i]->pred, &j); j++)
- bsunion(bbin, out[j]);
- bbout = bsdup(bbin);
- bsdiff(bbout, kill[i]);
- bsunion(bbout, gen[i]);
+ do {
+ changed = 0;
+ for (i = 0; i < cfg->nbb; i++) {
+ if (!cfg->bb[i])
+ continue;
+ bbin = mkbs();
+ for (j = 0; bsiter(cfg->bb[i]->pred, &j); j++)
+ bsunion(bbin, out[j]);
+ bbout = bsdup(bbin);
+ bsdiff(bbout, kill[i]);
+ bsunion(bbout, gen[i]);
- if (!bseq(out[i], bbout) || !bseq(in[i], bbin)) {
- changed = 1;
- bsfree(in[i]);
- bsfree(out[i]);
- in[i] = bbin;
- out[i] = bbout;
- }
- }
- } while (changed);
+ if (!bseq(out[i], bbout) || !bseq(in[i], bbin)) {
+ changed = 1;
+ bsfree(in[i]);
+ bsfree(out[i]);
+ in[i] = bbin;
+ out[i] = bbout;
+ }
+ }
+ } while (changed);
-// for (i = 0; i < ndecls; i++) {
-// if (defs[i])
-// printf("\t%zd: ", i);
-// for (j = 0; j < ndefs[i]; j++)
-// printf("%zd ", defs[i][j]);
-// if (defs[i])
-// printf("\n");
-// }
-// for (i = 0; i < cfg->nbb; i++) {
-// printf("bb %zd\n", i);
-// printf("\tin: ");
-// bsdump(in[i]);
-// printf("\tout: ");
-// bsdump(out[i]);
-// }
- reaching = xalloc(sizeof(Reaching));
- reaching->in = in;
- reaching->out = out;
- reaching->defs = defs;
- reaching->ndefs = ndefs;
- return reaching;
+ reaching = xalloc(sizeof(Reaching));
+ reaching->in = in;
+ reaching->out = out;
+ reaching->defs = defs;
+ reaching->ndefs = ndefs;
+ return reaching;
}