summary refs log tree commit diff
diff options
context:
space:
mode:
Diffstat
-rw-r--r--Makefile2
-rw-r--r--all.h12
-rw-r--r--cfg.c230
-rw-r--r--ssa.c187
-rw-r--r--util.c41
5 files changed, 241 insertions, 231 deletions
diff --git a/Makefile b/Makefile
index 9528f45..64531ea 100644
--- 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
index e303a87..6b1951d 100644
--- 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
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);
+	}
+}
diff --git a/ssa.c b/ssa.c
index 4b78fe3..a040484 100644
--- 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
index 63a1202..5c54c12 100644
--- 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)
 {
generated by cgit-pink 1.4.1 (git 2.36.1) at 2024-11-26 09:18:22 +0000