commit 12f9d16c7b000030ce332778fa4d51d455ae819f
parent 2380b5786a515af7149f7648d9e9c22a663e3a9c
Author: Quentin Carbonneaux <quentin.carbonneaux@yale.edu>
Date: Mon, 5 Dec 2016 02:09:48 -0500
create cfg.c for cfg-related functions
Diffstat:
| M | Makefile | | | 2 | +- |
| M | all.h | | | 12 | ++++++++++-- |
| A | cfg.c | | | 230 | +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ |
| M | ssa.c | | | 187 | ------------------------------------------------------------------------------- |
| M | util.c | | | 41 | ----------------------------------------- |
5 files changed, 241 insertions(+), 231 deletions(-)
diff --git a/Makefile b/Makefile
@@ -4,7 +4,7 @@ ABI = sysv
V = @
OBJDIR = obj
-SRC = main.c util.c parse.c mem.c ssa.c copy.c fold.c live.c $(ABI).c isel.c spill.c rega.c emit.c
+SRC = main.c util.c parse.c cfg.c mem.c ssa.c copy.c fold.c live.c $(ABI).c isel.c spill.c rega.c emit.c
OBJ = $(SRC:%.c=$(OBJDIR)/%.o)
CFLAGS += -Wall -Wextra -std=c99 -g -pedantic
diff --git a/all.h b/all.h
@@ -481,8 +481,6 @@ void die_(char *, char *, ...) __attribute__((noreturn));
void *emalloc(size_t);
void *alloc(size_t);
void freeall(void);
-Blk *blknew(void);
-void blkdel(Blk *);
void emit(int, int, Ref, Ref, Ref);
void emiti(Ins);
void idup(Ins **, Ins *, ulong);
@@ -523,6 +521,16 @@ void printfn(Fn *, FILE *);
void printref(Ref, Fn *, FILE *);
void err(char *, ...) __attribute__((noreturn));
+/* cfg.c */
+Blk *blknew(void);
+void blkdel(Blk *);
+void fillpreds(Fn *);
+void fillrpo(Fn *);
+void filldom(Fn *);
+int sdom(Blk *, Blk *);
+int dom(Blk *, Blk *);
+void fillfron(Fn *);
+
/* mem.c */
void memopt(Fn *);
diff --git a/cfg.c 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);
+ }
+}
diff --git a/ssa.c b/ssa.c
@@ -87,193 +87,6 @@ filluse(Fn *fn)
}
}
-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;
-}
-
-static 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;
- }
-}
-
-static 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;
-}
-
-static 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;
-}
-
-static 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);
- }
-}
-
static Ref
refindex(int t, Fn *fn)
{
diff --git a/util.c b/util.c
@@ -87,47 +87,6 @@ freeall()
nptr = 1;
}
-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));
- }
- }
-}
-
void
emit(int op, int k, Ref to, Ref arg0, Ref arg1)
{
