[PATCH 1/2] flowgraph: add a function to calculate the Lowest Common Denominator

[Luc Van Oostenryck <luc.vanoostenryck@gmail.com>]

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@gmail.com>
---
 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