summaryrefslogtreecommitdiff
path: root/mi/reaching.c
diff options
context:
space:
mode:
Diffstat (limited to 'mi/reaching.c')
-rw-r--r--mi/reaching.c233
1 files changed, 109 insertions, 124 deletions
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;
}