[v1,03/18] dom: calculate the dominance tree

Commit Message

Luc Van Oostenryck March 20, 2018, 12:52 a.m. UTC

Build the CFG's dominance tree and for each BB record:
- the immediate dominator as bb->idom (is null for entry BB).
- the list of immediately dominated BB as bb->doms.

Signed-off-by: Luc Van Oostenryck <[e-mail]>
---
 flowgraph.c | 103 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
 flowgraph.h |   1 +
 linearize.h |   4 +++
 3 files changed, 108 insertions(+)

Patch

diff --git a/flowgraph.c b/flowgraph.c
index 40a75e825..d5551908e 100644
--- a/flowgraph.c
+++ b/flowgraph.c
@@ -8,7 +8,9 @@ 
 #include "flowgraph.h"
 #include "linearize.h"
 #include "flow.h"			// for bb_generation
+#include <assert.h>
 #include <stdio.h>
+#include <stdlib.h>
 
 
 struct cfg_info {
@@ -76,3 +78,104 @@  int cfg_postorder(struct entrypoint *ep)
 		debug_postorder(ep);
 	return info.nr;
 }
+
+//
+// Calculate the dominance tree following:
+//	"A simple, fast dominance algorithm"
+//	by K. D. Cooper, T. J. Harvey, and K. Kennedy.
+//	cfr. http://www.cs.rice.edu/∼keith/EMBED/dom.pdf
+//
+static struct basic_block *intersect_dom(struct basic_block *doms[],
+		struct basic_block *b1, struct basic_block *b2)
+{
+	int f1 = b1->postorder_nr, f2 = b2->postorder_nr;
+	while (f1 != f2) {
+		while (f1 < f2) {
+			b1 = doms[f1];
+			f1 = b1->postorder_nr;
+		}
+		while (f2 < f1) {
+			b2 = doms[f2];
+			f2 = b2->postorder_nr;
+		}
+	}
+	return b1;
+}
+
+void domtree_build(struct entrypoint *ep)
+{
+	struct basic_block *entry = ep->entry->bb;
+	struct basic_block **doms;
+	struct basic_block *bb;
+	unsigned int size;
+	int max_level = 0;
+	int changed;
+
+	// First calculate the (reverse) postorder.
+	// This will give use us:
+	//	- the links to do a reverse postorder traversal
+	//	- the order number for each block
+	size = cfg_postorder(ep);
+
+	// initialize the dominators array
+	doms = calloc(size, sizeof(*doms));
+	assert(entry->postorder_nr == size-1);
+	doms[size-1] = entry;
+
+	do {
+		struct basic_block *b;
+
+		changed = 0;
+		FOR_EACH_PTR(ep->bbs, b) {
+			struct basic_block *p;
+			int bnr = b->postorder_nr;
+			struct basic_block *new_idom = NULL;
+
+			if (b == entry)
+				continue;	// ignore entry node
+
+			FOR_EACH_PTR(b->parents, p) {
+				unsigned int pnr = p->postorder_nr;
+				if (!doms[pnr])
+					continue;
+				if (!new_idom) {
+					new_idom = p;
+					continue;
+				}
+
+				new_idom = intersect_dom(doms, p, new_idom);
+			} END_FOR_EACH_PTR(p);
+
+			assert(new_idom);
+			if (doms[bnr] != new_idom) {
+				doms[bnr] = new_idom;
+				changed = 1;
+			}
+		} END_FOR_EACH_PTR(b);
+	} while (changed);
+
+	// set the idom links
+	FOR_EACH_PTR(ep->bbs, bb) {
+		struct basic_block *idom = doms[bb->postorder_nr];
+
+		if (bb == entry)
+			continue;	// ignore entry node
+
+		bb->idom = idom;
+		add_bb(&idom->doms, bb);
+	} END_FOR_EACH_PTR(bb);
+	entry->idom = NULL;
+
+	// set the dominance levels
+	FOR_EACH_PTR(ep->bbs, bb) {
+		struct basic_block *idom = bb->idom;
+		int level = idom ? idom->dom_level + 1 : 0;
+
+		bb->dom_level = level;
+		if (max_level < level)
+			max_level = level;
+	} END_FOR_EACH_PTR(bb);
+	ep->dom_levels = max_level + 1;
+
+	free(doms);
+}
diff --git a/flowgraph.h b/flowgraph.h
index 676c5b2d8..8e42f865d 100644
--- a/flowgraph.h
+++ b/flowgraph.h
@@ -4,5 +4,6 @@ 
 struct entrypoint;
 
 int cfg_postorder(struct entrypoint *ep);
+void domtree_build(struct entrypoint *ep);
 
 #endif
diff --git a/linearize.h b/linearize.h
index 50738a9d8..486cf5979 100644
--- a/linearize.h
+++ b/linearize.h
@@ -260,11 +260,14 @@  struct basic_block {
 	union {
 		int context;
 		int postorder_nr;	/* postorder number */
+		int dom_level;		/* level in the dominance tree */
 	};
 	struct entrypoint *ep;
 	struct basic_block_list *parents; /* sources */
 	struct basic_block_list *children; /* destinations */
 	struct instruction_list *insns;	/* Linear list of instructions */
+	struct basic_block *idom;	/* link to the immediate dominator */
+	struct basic_block_list *doms;	/* list of BB idominated by this one */
 	struct pseudo_list *needs, *defines;
 	union {
 		unsigned int nr;	/* unique id for label's names */
@@ -366,6 +369,7 @@  struct entrypoint {
 	struct basic_block_list *bbs;
 	struct basic_block *active;
 	struct instruction *entry;
+	unsigned int dom_levels;	/* max levels in the dom tree */
 };
 
 extern void insert_select(struct basic_block *bb, struct instruction *br, struct instruction *phi, pseudo_t if_true, pseudo_t if_false);