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 <luc.vanoostenryck@xxxxxxxxx>
---
flowgraph.c | 103 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
flowgraph.h | 1 +
linearize.h | 4 +++
3 files changed, 108 insertions(+)
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);
--
2.16.2
--
To unsubscribe from this list: send the line "unsubscribe linux-sparse" in
the body of a message to majordomo@xxxxxxxxxxxxxxx
More majordomo info at http://vger.kernel.org/majordomo-info.html
