The lowest dominator common to two given BBs is useful to know for
some optimizations like the placement of common sub-expressions.
So, add a function calculating it using the info from the dominator tree.
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@xxxxxxxxx>
---
flowgraph.c | 15 +++++++++++++++
flowgraph.h | 4 ++++
2 files changed, 19 insertions(+)
diff --git a/flowgraph.c b/flowgraph.c
index 73c29fc9f894..7db0290da31c 100644
--- a/flowgraph.c
+++ b/flowgraph.c
@@ -221,3 +221,18 @@ bool domtree_dominates(struct basic_block *a, struct basic_block *b)
}
return false;
}
+
+struct basic_block *bb_common_dominator(struct basic_block *a, struct basic_block *b)
+{
+ // walk op the domtree until the levels *and* the BBs match
+ while (a != b) {
+ int la = a->dom_level;
+ int lb = b->dom_level;
+
+ if (la >= lb)
+ a = a->idom;
+ if (lb >= la)
+ b = b->idom;
+ }
+ return a;
+}
diff --git a/flowgraph.h b/flowgraph.h
index 5a9c26073554..15f3156fdd4a 100644
--- a/flowgraph.h
+++ b/flowgraph.h
@@ -30,4 +30,8 @@ void domtree_build(struct entrypoint *ep);
// @return: ``true`` if @a dominates @b, ``false`` otherwise.
bool domtree_dominates(struct basic_block *a, struct basic_block *b);
+///
+// Find the lowest common dominator of two basic blocks.
+struct basic_block *bb_common_dominator(struct basic_block *a, struct basic_block *b);
+
#endif
--
2.29.2
