diff options
author | Ori Bernstein <ori@eigenstate.org> | 2015-11-17 20:53:32 -0800 |
---|---|---|
committer | Ori Bernstein <ori@eigenstate.org> | 2015-11-17 20:53:32 -0800 |
commit | 8531896f8d21ba1e727262aaf5cd96043590b480 (patch) | |
tree | 7c01441755f56ab66d33c37d3ac41642ddc46c0b /mi | |
parent | c20862cda53c711fe476f6c7d0f6631af47a4933 (diff) | |
download | mc-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.c | 456 | ||||
-rw-r--r-- | mi/dfcheck.c | 184 | ||||
-rw-r--r-- | mi/fold.c | 390 | ||||
-rw-r--r-- | mi/match.c | 1288 | ||||
-rw-r--r-- | mi/mi.h | 48 | ||||
-rw-r--r-- | mi/reaching.c | 233 |
6 files changed, 1292 insertions, 1307 deletions
@@ -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); } @@ -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; } @@ -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); } @@ -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; } |