[RFC PATCH 0/2] cse: place common expressions in the Lowest Common Dominator

[RFC PATCH 0/2] cse: place common expressions in the Lowest Common Dominator

[Luc Van Oostenryck]

This series extend the current CSE by using the lowest common dominator
instead of the more limiting 'common single parent'.

It allows significantly more common expressions to be eliminated.
However, it has the annoying disadvantage of slightly making worse
the 'context imbalance' problem. As such, it's not intended to be
merged as-is.

Luc Van Oostenryck (2):
  flowgraph: add a function to calculate the Lowest Common Denominator
  cse: place common expressions in the Lowest Common Dominator

 cse.c       | 38 ++++++++++----------------------------
 flowgraph.c | 15 +++++++++++++++
 flowgraph.h |  4 ++++
 3 files changed, 29 insertions(+), 28 deletions(-)

-- 
2.29.2

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

[Luc Van Oostenryck]

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

[PATCH 2/2] cse: place common expressions in the Lowest Common Dominator

[Luc Van Oostenryck]

Currently, during CSE, common expressions are eliminated if either:
1) they belong to the same Basic Block;
2) one of the expressions dominates the other (so, one of the BB they
   belong dominates the other);
3) they have a single parent which is the same for both.

The third case can be extended to another suitable ancestor:
any common dominator would be OK, which is exactly what is done in
this patch.

Note: This patch is interesting because it allows significantly more
      common expressions to be eliminated. However, it has the annoying
      disadvantage of making the 'context imbalance' problem slightly
      worse. So, it's not intended to be merged as-is.

Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
---
 cse.c | 38 ++++++++++----------------------------
 1 file changed, 10 insertions(+), 28 deletions(-)

diff --git a/cse.c b/cse.c
index 1e58a973ecf6..c33babf2c6c8 100644
--- a/cse.c
+++ b/cse.c
@@ -279,20 +279,6 @@ static struct instruction * cse_one_instruction(struct instruction *insn, struct
 	return def;
 }
 
-static struct basic_block *trivial_common_parent(struct basic_block *bb1, struct basic_block *bb2)
-{
-	struct basic_block *parent;
-
-	if (bb_list_size(bb1->parents) != 1)
-		return NULL;
-	parent = first_basic_block(bb1->parents);
-	if (bb_list_size(bb2->parents) != 1)
-		return NULL;
-	if (first_basic_block(bb2->parents) != parent)
-		return NULL;
-	return parent;
-}
-
 static inline void remove_instruction(struct instruction_list **list, struct instruction *insn, int count)
 {
 	delete_ptr_list_entry((struct ptr_list **)list, insn, count);
@@ -318,7 +304,7 @@ static struct instruction * try_to_cse(struct entrypoint *ep, struct instruction
 	b2 = i2->bb;
 
 	/*
-	 * Currently we only handle the uninteresting degenerate case where
+	 * First try the uninteresting degenerate case where
 	 * the CSE is inside one basic-block.
 	 */
 	if (b1 == b2) {
@@ -332,22 +318,18 @@ static struct instruction * try_to_cse(struct entrypoint *ep, struct instruction
 		warning(b1->pos, "Whaa? unable to find CSE instructions");
 		return i1;
 	}
-	if (domtree_dominates(b1, b2))
-		return cse_one_instruction(i2, i1);
 
-	if (domtree_dominates(b2, b1))
+	/* Then try the case where one of the BB already dominate the other. */
+	common = bb_common_dominator(b1, b2);
+	if (common == b1)
+		return cse_one_instruction(i2, i1);
+	if (common == b2)
 		return cse_one_instruction(i1, i2);
 
-	/* No direct dominance - but we could try to find a common ancestor.. */
-	common = trivial_common_parent(b1, b2);
-	if (common) {
-		i1 = cse_one_instruction(i2, i1);
-		remove_instruction(&b1->insns, i1, 1);
-		add_instruction_to_end(i1, common);
-	} else {
-		i1 = i2;
-	}
-
+	/* No direct dominance - use the common dominator. */
+	cse_one_instruction(i2, i1);
+	remove_instruction(&b1->insns, i1, 1);
+	add_instruction_to_end(i1, common);
 	return i1;
 }
 
-- 
2.29.2