From 629257bcb81434117f1e9c68479032563176dc0c Mon Sep 17 00:00:00 2001
From: Richard Biener <rguenther@suse.de>
Date: Tue, 25 Jun 2024 14:04:31 +0200
Subject: [PATCH] tree-optimization/115629 - missed tail merging

The following fixes a missed tail-merging observed for the testcase
in PR115629.  The issue is that when deps_ok_for_redirect doesn't
compute both would be valid prevailing blocks it rejects the merge.
The following instead makes sure to record the working block as
prevailing.  Also stmt comparison fails for indirect references
and is not handling memory references thoroughly, failing to unify
array indices and pointers indirected.  The following attempts to
fix this.

	PR tree-optimization/115629
	* tree-ssa-tail-merge.cc (gimple_equal_p): Handle
	memory references better.
	(deps_ok_for_redirect): Handle the case not both blocks
	are considered a valid prevailing block.

	* gcc.dg/tree-ssa/tail-merge-1.c: New testcase.
---
 gcc/testsuite/gcc.dg/tree-ssa/tail-merge-1.c | 14 ++++
 gcc/tree-ssa-tail-merge.cc                   | 69 +++++++++++++++++---
 2 files changed, 75 insertions(+), 8 deletions(-)
 create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/tail-merge-1.c

diff --git a/gcc/testsuite/gcc.dg/tree-ssa/tail-merge-1.c b/gcc/testsuite/gcc.dg/tree-ssa/tail-merge-1.c
new file mode 100644
index 000000000000..e5670c33ba36
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/tail-merge-1.c
@@ -0,0 +1,14 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-dce4" } */
+
+void foo1 (int *restrict a, int *restrict b, int *restrict c,
+	   int *restrict d, int *restrict res, int n)
+{
+  for (int i = 0; i < n; i++)
+    res[i] = a[i] ? b[i] : (c[i] ? b[i] : d[i]);
+}
+
+/* After tail-merging (run during PRE) we should end up merging the two
+   blocks dereferencing 'b', ending up with two iftmp assigns and the
+   iftmp PHI def.  */
+/* { dg-final { scan-tree-dump-times "iftmp\[^\r\n\]* = " 3 "dce4" } } */
diff --git a/gcc/tree-ssa-tail-merge.cc b/gcc/tree-ssa-tail-merge.cc
index c8b4a79294d7..27e7c6a37b2a 100644
--- a/gcc/tree-ssa-tail-merge.cc
+++ b/gcc/tree-ssa-tail-merge.cc
@@ -1188,7 +1188,52 @@ gimple_equal_p (same_succ *same_succ, gimple *s1, gimple *s2)
 	{
 	  t1 = gimple_arg (s1, i);
 	  t2 = gimple_arg (s2, i);
-	  if (!gimple_operand_equal_value_p (t1, t2))
+	  while (handled_component_p (t1) && handled_component_p (t2))
+	    {
+	      if (TREE_CODE (t1) != TREE_CODE (t2)
+		  || TREE_THIS_VOLATILE (t1) != TREE_THIS_VOLATILE (t2))
+		return false;
+	      switch (TREE_CODE (t1))
+		{
+		case COMPONENT_REF:
+		  if (TREE_OPERAND (t1, 1) != TREE_OPERAND (t2, 1)
+		      || !gimple_operand_equal_value_p (TREE_OPERAND (t1, 2),
+							TREE_OPERAND (t2, 2)))
+		    return false;
+		  break;
+		case ARRAY_REF:
+		case ARRAY_RANGE_REF:
+		  if (!gimple_operand_equal_value_p (TREE_OPERAND (t1, 3),
+						     TREE_OPERAND (t2, 3)))
+		    return false;
+		  /* Fallthru.  */
+		case BIT_FIELD_REF:
+		  if (!gimple_operand_equal_value_p (TREE_OPERAND (t1, 1),
+						     TREE_OPERAND (t2, 1))
+		      || !gimple_operand_equal_value_p (TREE_OPERAND (t1, 2),
+							TREE_OPERAND (t2, 2)))
+		    return false;
+		  break;
+		case REALPART_EXPR:
+		case IMAGPART_EXPR:
+		case VIEW_CONVERT_EXPR:
+		  break;
+		default:
+		gcc_unreachable ();
+		}
+	      t1 = TREE_OPERAND (t1, 0);
+	      t2 = TREE_OPERAND (t2, 0);
+	    }
+	  if (TREE_CODE (t1) == MEM_REF && TREE_CODE (t2) == MEM_REF)
+	    {
+	      if (TREE_THIS_VOLATILE (t1) != TREE_THIS_VOLATILE (t2)
+		  || TYPE_ALIGN (TREE_TYPE (t1)) != TYPE_ALIGN (TREE_TYPE (t2))
+		  || !gimple_operand_equal_value_p (TREE_OPERAND (t1, 0),
+						    TREE_OPERAND (t2, 0))
+		  || TREE_OPERAND (t1, 1) != TREE_OPERAND (t2, 1))
+		return false;
+	    }
+	  else if (!gimple_operand_equal_value_p (t1, t2))
 	    return false;
 	}
       return true;
@@ -1462,16 +1507,24 @@ deps_ok_for_redirect_from_bb_to_bb (basic_block from, basic_block to)
    replacement are dominates by their defs.  */
 
 static bool
-deps_ok_for_redirect (basic_block bb1, basic_block bb2)
+deps_ok_for_redirect (basic_block &bb1, basic_block &bb2)
 {
-  if (BB_CLUSTER (bb1) != NULL)
-    bb1 = BB_CLUSTER (bb1)->rep_bb;
+  basic_block b1 = bb1;
+  basic_block b2 = bb2;
+  if (BB_CLUSTER (b1) != NULL)
+    b1 = BB_CLUSTER (b1)->rep_bb;
 
-  if (BB_CLUSTER (bb2) != NULL)
-    bb2 = BB_CLUSTER (bb2)->rep_bb;
+  if (BB_CLUSTER (b2) != NULL)
+    b2 = BB_CLUSTER (b2)->rep_bb;
 
-  return (deps_ok_for_redirect_from_bb_to_bb (bb1, bb2)
-	  && deps_ok_for_redirect_from_bb_to_bb (bb2, bb1));
+  if (deps_ok_for_redirect_from_bb_to_bb (b1, b2))
+    return true;
+  if (deps_ok_for_redirect_from_bb_to_bb (b2, b1))
+    {
+      std::swap (bb1, bb2);
+      return true;
+    }
+  return false;
 }
 
 /* Within SAME_SUCC->bbs, find clusters of bbs which can be merged.  */
-- 
2.47.2