diff options
Diffstat (limited to 'cfg.c')
| -rw-r--r-- | cfg.c | 230 |
1 files changed, 230 insertions, 0 deletions
diff --git a/cfg.c b/cfg.c new file mode 100644 index 0000000..ae54deb --- /dev/null +++ b/cfg.c @@ -0,0 +1,230 @@ +#include "all.h" + +Blk * +blknew() +{ + static Blk z; + Blk *b; + + b = alloc(sizeof *b); + *b = z; + return b; +} + +void +blkdel(Blk *b) +{ + Blk *s, **ps, *succ[3]; + Phi *p; + uint a; + + succ[0] = b->s1; + succ[1] = b->s2 == b->s1 ? 0 : b->s2; + succ[2] = 0; + for (ps=succ; (s=*ps); ps++) { + for (p=s->phi; p; p=p->link) { + for (a=0; p->blk[a]!=b; a++) + assert(a+1<p->narg); + p->narg--; + memmove(&p->blk[a], &p->blk[a+1], + sizeof p->blk[0] * (p->narg-a)); + memmove(&p->arg[a], &p->arg[a+1], + sizeof p->arg[0] * (p->narg-a)); + } + if (s->npred != 0) { + for (a=0; s->pred[a]!=b; a++) + assert(a+1<s->npred); + s->npred--; + memmove(&s->pred[a], &s->pred[a+1], + sizeof s->pred[0] * (s->npred-a)); + } + } +} + +static void +addpred(Blk *bp, Blk *bc) +{ + if (!bc->pred) { + bc->pred = alloc(bc->npred * sizeof bc->pred[0]); + bc->visit = 0; + } + bc->pred[bc->visit++] = bp; +} + +/* fill predecessors information in blocks */ +void +fillpreds(Fn *f) +{ + Blk *b; + + for (b=f->start; b; b=b->link) { + b->npred = 0; + b->pred = 0; + } + for (b=f->start; b; b=b->link) { + if (b->s1) + b->s1->npred++; + if (b->s2 && b->s2 != b->s1) + b->s2->npred++; + } + for (b=f->start; b; b=b->link) { + if (b->s1) + addpred(b, b->s1); + if (b->s2 && b->s2 != b->s1) + addpred(b, b->s2); + } +} + +static int +rporec(Blk *b, int x) +{ + Blk *s1, *s2; + + if (!b || b->id >= 0) + return x; + b->id = 1; + s1 = b->s1; + s2 = b->s2; + if (s1 && s2 && s1->loop > s2->loop) { + s1 = b->s2; + s2 = b->s1; + } + x = rporec(s1, x); + x = rporec(s2, x); + b->id = x; + assert(x >= 0); + return x - 1; +} + +/* fill the rpo information */ +void +fillrpo(Fn *f) +{ + int n; + Blk *b, **p; + + for (b=f->start; b; b=b->link) + b->id = -1; + n = 1 + rporec(f->start, f->nblk-1); + f->nblk -= n; + f->rpo = alloc(f->nblk * sizeof f->rpo[0]); + for (p=&f->start; (b=*p);) { + if (b->id == -1) { + blkdel(b); + *p = b->link; + } else { + b->id -= n; + f->rpo[b->id] = b; + p = &b->link; + } + } +} + +/* for dominators computation, read + * "A Simple, Fast Dominance Algorithm" + * by K. Cooper, T. Harvey, and K. Kennedy. + */ + +static Blk * +inter(Blk *b1, Blk *b2) +{ + Blk *bt; + + if (b1 == 0) + return b2; + while (b1 != b2) { + if (b1->id < b2->id) { + bt = b1; + b1 = b2; + b2 = bt; + } + while (b1->id > b2->id) { + b1 = b1->idom; + assert(b1); + } + } + return b1; +} + +void +filldom(Fn *fn) +{ + Blk *b, *d; + int ch, n; + uint p; + + for (b=fn->start; b; b=b->link) { + b->idom = 0; + b->dom = 0; + b->dlink = 0; + } + do { + ch = 0; + for (n=1; n<fn->nblk; n++) { + b = fn->rpo[n]; + d = 0; + for (p=0; p<b->npred; p++) + if (b->pred[p]->idom + || b->pred[p] == fn->start) + d = inter(d, b->pred[p]); + if (d != b->idom) { + ch++; + b->idom = d; + } + } + } while (ch); + for (b=fn->start; b; b=b->link) + if ((d=b->idom)) { + assert(d != b); + b->dlink = d->dom; + d->dom = b; + } +} + +int +sdom(Blk *b1, Blk *b2) +{ + assert(b1 && b2); + if (b1 == b2) + return 0; + while (b2->id > b1->id) + b2 = b2->idom; + return b1 == b2; +} + +int +dom(Blk *b1, Blk *b2) +{ + return b1 == b2 || sdom(b1, b2); +} + +static void +addfron(Blk *a, Blk *b) +{ + int n; + + for (n=0; n<a->nfron; n++) + if (a->fron[n] == b) + return; + if (!a->nfron) + a->fron = vnew(++a->nfron, sizeof a->fron[0], alloc); + else + vgrow(&a->fron, ++a->nfron); + a->fron[a->nfron-1] = b; +} + +/* fill the dominance frontier */ +void +fillfron(Fn *fn) +{ + Blk *a, *b; + + for (b=fn->start; b; b=b->link) { + if (b->s1) + for (a=b; !sdom(a, b->s1); a=a->idom) + addfron(a, b->s1); + if (b->s2) + for (a=b; !sdom(a, b->s2); a=a->idom) + addfron(a, b->s2); + } +} |