The dominance tree is useless as such, what's matter
is to be able to make queries, to ask if such BB dominates
this other BB.
This patch add an API (domtree_dominates()) to do this.
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@xxxxxxxxx>
---
flowgraph.c | 24 ++++++++++++++++++++++++
flowgraph.h | 4 ++++
2 files changed, 28 insertions(+)
diff --git a/flowgraph.c b/flowgraph.c
index b2d95893c..8fc22dcfd 100644
--- a/flowgraph.c
+++ b/flowgraph.c
@@ -193,3 +193,27 @@ void domtree_build(struct entrypoint *ep)
if (dbg_domtree)
debug_domtree(ep);
}
+
+// dt_dominates - does BB a dominates BB b?
+bool domtree_dominates(struct basic_block *a, struct basic_block *b)
+{
+ if (a == b) // dominance is reflexive
+ return true;
+ if (a == b->idom)
+ return true;
+ if (b == a->idom)
+ return false;
+
+ // can't dominate if deeper in the DT
+ if (a->dom_level >= b->dom_level)
+ return false;
+
+ // FIXME: can be faster if we have the DFS in-out numbers
+
+ // walk up the dominator tree
+ for (b = b->idom; b; b = b->idom) {
+ if (b == a)
+ return true;
+ }
+ return false;
+}
diff --git a/flowgraph.h b/flowgraph.h
index 8e42f865d..7226c55f0 100644
--- a/flowgraph.h
+++ b/flowgraph.h
@@ -1,9 +1,13 @@
#ifndef FLOWGRAPH_H
#define FLOWGRAPH_H
+#include <stdbool.h>
+
struct entrypoint;
+struct basic_block;
int cfg_postorder(struct entrypoint *ep);
void domtree_build(struct entrypoint *ep);
+bool domtree_dominates(struct basic_block *a, struct basic_block *b);
#endif
--
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
