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

Commit Message

Luc Van Oostenryck Dec. 4, 2020, 5:16 p.m. UTC

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 <[e-mail]>
---
 flowgraph.c | 15 +++++++++++++++
 flowgraph.h |  4 ++++
 2 files changed, 19 insertions(+)

Patch

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