diff mbox

[v1,05/18] dom: add support for dominance queries

Message ID 20180320005256.53284-6-luc.vanoostenryck@gmail.com (mailing list archive)
State Mainlined, archived
Headers show

Commit Message

Luc Van Oostenryck March 20, 2018, 12:52 a.m. UTC 
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@gmail.com>
---
 flowgraph.c | 24 ++++++++++++++++++++++++
 flowgraph.h |  4 ++++
 2 files changed, 28 insertions(+)
diff mbox

Patch

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