ref: 3b2a10f280a9c927bd678199a90a96f8cddab89c
parent: 6cf64ac765264c305b91b3062ef8e3525e83add5
author: Ori Bernstein <[email protected]>
date: Thu May 7 21:06:17 EDT 2015
Get closer to a working use-before-def check.
--- a/mi/Makefile
+++ b/mi/Makefile
@@ -1,8 +1,10 @@
LIB=libmi.a
OBJ=cfg.o \
+ dfcheck.o \
fold.o \
match.o \
- dfcheck.o \
+ reaching.o \
+
DEPS=../parse/libparse.a
--- a/mi/dfcheck.c
+++ b/mi/dfcheck.c
@@ -13,195 +13,64 @@
#include "parse.h"
#include "mi.h"
-static void nodevars(Node *n, Bitset *bs)
+static void checkundef(Node *n, Reaching *r, Bitset *reach, Bitset *kill)
{- size_t i;
+ size_t i, j, did;
+ Node *def;
- if (!n || n->type != Nexpr)
+ if (n->type != Nexpr)
return;
- switch (exprop(n)) {- case Ovar:
- bsput(bs, n->expr.did);
- break;
- default:
- nodevars(n->expr.idx, bs);
- for (i = 0; i < n->expr.nargs; i++)
- nodevars(n->expr.args[i], bs);
- break;
- }
-}
-void nodedef(Node *n, Bitset *bs)
-{- Node *p;
- size_t i;
-
- switch(exprop(n)) {- case Oset:
- case Oasn: case Oaddeq:
- case Osubeq: case Omuleq:
- case Odiveq: case Omodeq:
- case Oboreq: case Obandeq:
- case Obxoreq: case Obsleq:
- case Obsreq:
- nodevars(n->expr.args[0], bs);
- nodedef(n->expr.args[1], bs);
- break;
- /* for the sake of less noise: assume that f(&var) inits the var. */
- case Ocall:
- for (i = 1; i < n->expr.nargs; i++) {- p = n->expr.args[i];
- if (exprop(p) == Oaddr && exprop(p->expr.args[0]) == Ovar)
- nodevars(p, bs);
- }
- break;
- default:
- break;
- }
-}
-
-static void checkdefined(Node *n, Bitset *def)
-{- size_t i;
- Node *d;
-
- if (!n || n->type != Nexpr)
- return;
- switch (exprop(n)) {- case Ovar:
- d = decls[n->expr.did];
- if (!bshas(def, n->expr.did) && !d->decl.isglobl)
+ if (exprop(n) == Ovar) {+ did = n->expr.did;
+ for (j = 0; j < r->ndefs[did]; j++) {+ if (bshas(kill, r->defs[did][j]))
+ continue;
+ if (bshas(reach, r->defs[did][j]))
+ def = nodes[r->defs[did][j]];
+ if (exprop(def) == Oundef)
fatal(n, "%s used before definition", namestr(n->expr.args[0]));
- break;
- default:
- nodevars(n->expr.idx, def);
- for (i = 0; i < n->expr.nargs; i++)
- checkdefined(n->expr.args[i], def);
- break;
- }
-}
-
-static void checkuse(Bb *bb, Bitset *def)
-{- size_t i;
- Node *n;
-
- if (!bb)
- return;
- for (i = 0; i < bb->nnl; i++) {- n = bb->nl[i];
- /* Tradeoff.
- *
- * We could check after, and get slightly more accurate checking,
- * but then we error on things like:
- * init(&foo);
- *
- * We can check before, but then we don't error on things like:
- * x = f(x)
- *
- * Eventually we should check both ways. Right now, I want to get
- * something working.
- */
- nodedef(n, def);
- switch(exprop(n)) {- case Oset:
- case Oasn:
- checkdefined(n->expr.args[1], def);
- break;
- default:
- checkdefined(n, def);
}
+ } else {+ for (i = 0; i < n->expr.nargs; i++)
+ checkundef(n->expr.args[i], r, reach, kill);
}
}
-static void bbdef(Bb *bb, Bitset *bs)
+void bsdump(Bitset *bs)
{size_t i;
-
- if (!bb)
- return;
- for (i = 0; i < bb->nnl; i++)
- nodedef(bb->nl[i], bs);
+ for (i = 0; bsiter(bs, &i); i++)
+ printf("%zd ", i);+ printf("\n");}
-static Bitset *indef(Cfg *cfg, Bb *bb, Bitset **outdef)
-{- size_t j;
- Bitset *def;
-
- j = 0;
- if (!bb || !bsiter(bb->pred, &j))
- return mkbs();
- def = bsdup(outdef[j]);
- for (; bsiter(bb->pred, &j); j++)
- bsintersect(def, outdef[j]);
- return def;
-}
-
-static void addargs(Cfg *cfg, Bitset *def)
-{- Node *n;
- size_t i;
-
- n = cfg->fn;
- assert(n->type == Ndecl);
- n = n->decl.init;
- assert(n->type == Nexpr);
- n = n->expr.args[0];
- assert(n->type == Nlit);
- n = n->lit.fnval;
-
- for (i = 0; i < n->func.nargs; i++)
- bsput(def,n->func.args[i]->decl.did);
-}
-
static void checkreach(Cfg *cfg)
{- Bitset **outdef;
- Bitset *def;
- size_t i, j;
- int changed;
+ Bitset *reach, *kill;
+ size_t i, j, k;
+ Reaching *r;
+ Node *n, *m;
Bb *bb;
- outdef = xalloc(sizeof(Bitset*) * cfg->nbb);
-
- def = mkbs();
-
+ r = reaching(cfg);
for (i = 0; i < cfg->nbb; i++) {- outdef[i] = mkbs();
- bbdef(cfg->bb[i], outdef[i]);
- }
- addargs(cfg, outdef[cfg->start->id]);
-
- for (i = 0; i < cfg->nbb; i++)
- for (j= 0; bsiter(outdef[i], &j); j++)
- printf("bb %zd defines %s\n", i, declname(decls[j]));-
- do {- changed = 0;
- for (i = 0; i < cfg->nbb; i++) {- bb = cfg->bb[i];
-
- def = indef(cfg, bb, outdef);
- bsunion(def, outdef[i]);
-
- if (!bseq(outdef[i], def)) {- changed = 1;
- bsfree(outdef[i]);
- outdef[i] = def;
+ bb = cfg->bb[i];
+ 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);
}
-
}
- } while (changed);
-
-
-
- printf("---\n");- for (i = 0; i < cfg->nbb; i++) {- for (j= 0; bsiter(outdef[i], &j); j++)
- printf("bb %zd defines %s\n", i, declname(decls[j]));- def = indef(cfg, bb, outdef);
- checkuse(cfg->bb[i], def);
- bsfree(def);
+ bsfree(reach);
+ bsfree(kill);
}
}
@@ -239,6 +108,6 @@
void check(Cfg *cfg)
{checkret(cfg);
- if (0)
+ if(0)
checkreach(cfg);
}
--- a/mi/mi.h
+++ b/mi/mi.h
@@ -1,5 +1,6 @@
typedef struct Cfg Cfg;
typedef struct Bb Bb;
+typedef struct Reaching Reaching;
struct Cfg {Node *fn;
@@ -27,8 +28,20 @@
Bitset *succ;
};
+struct Reaching {+ Bitset **in;
+ Bitset **out;
+ size_t **defs;
+ size_t *ndefs;
+};
+
/* expression folding */
Node *fold(Node *n, int foldvar);
+
+/* dataflow analysis */
+Reaching *reaching(Cfg *cfg);
+Node *assignee(Node *n);
+
/* Takes a reduced block, and returns a flow graph. */
Cfg *mkcfg(Node *fn, Node **nl, size_t nn);
void dumpcfg(Cfg *c, FILE *fd);
--- /dev/null
+++ b/mi/reaching.c
@@ -1,0 +1,130 @@
+#include <stdlib.h>
+#include <stdio.h>
+#include <inttypes.h>
+#include <stdarg.h>
+#include <ctype.h>
+#include <string.h>
+#include <assert.h>
+#include <sys/types.h>
+#include <sys/stat.h>
+#include <fcntl.h>
+#include <unistd.h>
+
+#include "parse.h"
+#include "mi.h"
+
+Node *assignee(Node *n)
+{+ switch (exprop(n)) {+ case Oundef:
+ 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;
+ default:
+ break;
+ }
+ return NULL;
+}
+
+static void collectdefs(Cfg *cfg, size_t **defs, size_t *ndefs)
+{+ 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;
+ }
+ }
+ }
+}
+
+static void genkill(Bb *bb, size_t **defs, size_t *ndefs, Bitset *gen, Bitset *kill)
+{+ 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;
+ bsput(gen, bb->nl[i]->nid);
+ for (j = 0; j < ndefs[did]; j++)
+ bsput(kill, defs[did][j]);
+ }
+}
+
+
+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;
+
+ 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]);
+ }
+
+ do {+ changed = 0;
+ for (i = 0; i < cfg->nbb; i++) {+ if (!cfg->bb[i])
+ continue;
+ bbout = mkbs();
+ for (j = 0; bsiter(cfg->bb[i]->pred, &j); j++)
+ bsunion(bbout, in[j]);
+ bbin = bsdup(bbout);
+ bsdiff(bbin, kill[i]);
+ bsunion(bbin, 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);
+
+ reaching = xalloc(sizeof(Reaching));
+ reaching->in = in;
+ reaching->out = out;
+ reaching->defs = defs;
+ reaching->ndefs = ndefs;
+ return reaching;
+}
--- a/parse/node.c
+++ b/parse/node.c
@@ -12,7 +12,8 @@
#include "parse.h"
-size_t maxnid;
+Node **nodes;
+size_t nnodes;
Node **decls;
size_t ndecls;
@@ -49,9 +50,10 @@
Node *n;
n = zalloc(sizeof(Node));
- n->nid = maxnid++;
+ n->nid = nnodes;
n->type = nt;
n->loc = loc;
+ lappend(&nodes, &nnodes, n);
return n;
}
--- a/parse/parse.h
+++ b/parse/parse.h
@@ -375,10 +375,11 @@
extern Trait **traittab; /* int -> trait map */
extern size_t ntraittab;
extern Node **decls; /* decl id -> decl map */
+extern size_t nnodes;
+extern Node **nodes; /* node id -> node map */
extern size_t ndecls;
extern Node **exportimpls;
extern size_t nexportimpls;
-extern size_t maxnid; /* the maximum node id generated so far */
/* property tables */
extern int opispure[];