diff mbox series

split-path: Improve ifcvt heurstic for split path [PR112402]

Message ID 20240903175031.2682032-1-quic_apinski@quicinc.com
State New
Headers show
Series split-path: Improve ifcvt heurstic for split path [PR112402] | expand

Commit Message

Andrew Pinski Sept. 3, 2024, 5:50 p.m. UTC 
This simplifies the heurstic for split path to see if the join
bb is a ifcvt candidate.
For the predecessors bbs need either to be empty or only have one
statement in them which could be a decent ifcvt candidate.
The previous heurstics would miss that:
```
if (a) goto B else goto C;
B:  goto C;
C:
c = PHI<d,e>
```

Would be a decent ifcvt candidate. And would also miss:
```
if (a) goto B else goto C;
B: d = f + 1;  goto C;
C:
c = PHI<d,e>
```

Also since currently the max number of cmovs being able to produced is 3, we
should only assume `<= 3` phis can be ifcvt candidates.

The testcase changes for split-path-6.c is that lookharder function
is a true ifcvt case where we would get cmov as expected; it looks like it
was not a candidate when the heurstic was added but became one later on.
pr88797.C is now rejected via it being an ifcvt candidate rather than being about
DCE/const prop.

The rest of the testsuite changes are just slight change in the dump,
removing the "*diamnond" part as it was removed from the print.

Bootstrapped and tested on x86_64.

	PR tree-optimization/112402

gcc/ChangeLog:

	* gimple-ssa-split-paths.cc (poor_ifcvt_pred): New function.
	(is_feasible_trace): Remove old heurstics for ifcvt cases.
	For num_stmts <=1 for both pred check poor_ifcvt_pred on both
	pred.

gcc/testsuite/ChangeLog:

	* gcc.dg/tree-ssa/split-path-11.c: Update scan.
	* gcc.dg/tree-ssa/split-path-2.c: Update scan.
	* gcc.dg/tree-ssa/split-path-5.c: Update scan.
	* gcc.dg/tree-ssa/split-path-6.c: Update scan.
	* g++.dg/tree-ssa/pr88797.C: Update scan.
	* gcc.dg/tree-ssa/split-path-13.c: New test.

Signed-off-by: Andrew Pinski <quic_apinski@quicinc.com>
---
 gcc/gimple-ssa-split-paths.cc                 | 172 ++++++------------
 gcc/testsuite/g++.dg/tree-ssa/pr88797.C       |   2 +-
 gcc/testsuite/gcc.dg/tree-ssa/split-path-11.c |   2 +-
 gcc/testsuite/gcc.dg/tree-ssa/split-path-13.c |  26 +++
 gcc/testsuite/gcc.dg/tree-ssa/split-path-2.c  |   2 +-
 gcc/testsuite/gcc.dg/tree-ssa/split-path-5.c  |   2 +-
 gcc/testsuite/gcc.dg/tree-ssa/split-path-6.c  |   4 +-
 7 files changed, 88 insertions(+), 122 deletions(-)
 create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/split-path-13.c
diff mbox series

Patch

diff --git a/gcc/gimple-ssa-split-paths.cc b/gcc/gimple-ssa-split-paths.cc
index 81a5d1dee5b..32b5c445760 100644
--- a/gcc/gimple-ssa-split-paths.cc
+++ b/gcc/gimple-ssa-split-paths.cc
@@ -35,6 +35,7 @@  along with GCC; see the file COPYING3.  If not see
 #include "tree-phinodes.h"
 #include "ssa-iterators.h"
 #include "fold-const.h"
+#include "cfghooks.h"
 
 /* Given LATCH, the latch block in a loop, see if the shape of the
    path reaching LATCH is suitable for being split by duplication.
@@ -141,6 +142,40 @@  poor_ifcvt_candidate_code (enum tree_code code)
 	  || code == CALL_EXPR);
 }
 
+/* Return TRUE if PRED of BB is an poor ifcvt candidate. */
+static bool
+poor_ifcvt_pred (basic_block pred, basic_block bb)
+{
+  /* If the edge count of the pred is not 1, then
+     this is the predecessor from the if rather
+     than middle one. */
+  if (EDGE_COUNT (pred->succs) != 1)
+    return false;
+
+  /* Empty middle bb are never a poor ifcvt candidate. */
+  if (empty_block_p (pred))
+    return false;
+  /* If BB's predecessors are single statement blocks where
+     the output of that statement feed the same PHI in BB,
+     it an ifcvt candidate. */
+  gimple *stmt = last_and_only_stmt (pred);
+  if (!stmt || gimple_code (stmt) != GIMPLE_ASSIGN)
+    return true;
+  tree_code code = gimple_assign_rhs_code (stmt);
+  if (poor_ifcvt_candidate_code (code))
+    return true;
+  tree lhs = gimple_assign_lhs (stmt);
+  gimple_stmt_iterator gsi;
+  for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi))
+    {
+      gimple *phi = gsi_stmt (gsi);
+      if (gimple_phi_arg_def (phi, 0) == lhs
+	  || gimple_phi_arg_def (phi, 1) == lhs)
+	return false;
+    }
+  return true;
+}
+
 /* Return TRUE if BB is a reasonable block to duplicate by examining
    its size, false otherwise.  BB will always be a loop latch block.
 
@@ -181,127 +216,30 @@  is_feasible_trace (basic_block bb)
     }
 
   /* This is meant to catch cases that are likely opportunities for
-     if-conversion.  Essentially we look for the case where
-     BB's predecessors are both single statement blocks where
-     the output of that statement feed the same PHI in BB.  */
-  if (num_stmts_in_pred1 == 1 && num_stmts_in_pred2 == 1)
-    {
-      gimple *stmt1 = last_and_only_stmt (pred1);
-      gimple *stmt2 = last_and_only_stmt (pred2);
-
-      if (stmt1 && stmt2
-	  && gimple_code (stmt1) == GIMPLE_ASSIGN
-	  && gimple_code (stmt2) == GIMPLE_ASSIGN)
-	{
-	  enum tree_code code1 = gimple_assign_rhs_code (stmt1);
-	  enum tree_code code2 = gimple_assign_rhs_code (stmt2);
-
-	  if (!poor_ifcvt_candidate_code (code1)
-	      && !poor_ifcvt_candidate_code (code2))
-	    {
-	      tree lhs1 = gimple_assign_lhs (stmt1);
-	      tree lhs2 = gimple_assign_lhs (stmt2);
-	      gimple_stmt_iterator gsi;
-	      for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi))
-		{
-		  gimple *phi = gsi_stmt (gsi);
-		  if ((gimple_phi_arg_def (phi, 0) == lhs1
-		       && gimple_phi_arg_def (phi, 1) == lhs2)
-		      || (gimple_phi_arg_def (phi, 1) == lhs1
-			  && gimple_phi_arg_def (phi, 0) == lhs2))
-		    {
-		      if (dump_file && (dump_flags & TDF_DETAILS))
-			fprintf (dump_file,
-				 "Block %d appears to be a join point for "
-				 "if-convertable diamond.\n",
-				 bb->index);
-		      return false;
-		    }
-		}
-	    }
-	}
-    }
-
-  /* Canonicalize the form.  */
-  if (num_stmts_in_pred1 == 0 && num_stmts_in_pred2 == 1)
-    {
-      std::swap (pred1, pred2);
-      std::swap (num_stmts_in_pred1, num_stmts_in_pred2);
-    }
-
-  /* Another variant.  This one is half-diamond.  */
-  if (num_stmts_in_pred1 == 1 && num_stmts_in_pred2 == 0
-      && dominated_by_p (CDI_DOMINATORS, pred1, pred2))
+     if-conversion.  */
+  if (num_stmts_in_pred1 <= 1 && num_stmts_in_pred2 <= 1)
     {
-      gimple *stmt1 = last_and_only_stmt (pred1);
-
-      /* The only statement in PRED1 must be an assignment that is
-	 not a good candidate for if-conversion.   This may need some
-	 generalization.  */
-      if (stmt1 && gimple_code (stmt1) == GIMPLE_ASSIGN)
+      int num_phis = 0;
+      /* The max number of PHIs that should be considered for an ifcvt
+	 candidate.  */
+      const int max_num_phis = 3;
+      for (gphi_iterator si = gsi_start_phis (bb); ! gsi_end_p (si);
+	  gsi_next (&si))
 	{
-	  enum tree_code code1 = gimple_assign_rhs_code (stmt1);
-
-	  if (!poor_ifcvt_candidate_code (code1))
-	    {
-	      tree lhs1 = gimple_assign_lhs (stmt1);
-	      tree rhs1 = gimple_assign_rhs1 (stmt1);
-
-	      gimple_stmt_iterator gsi;
-	      for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi))
-		{
-		  gimple *phi = gsi_stmt (gsi);
-		  if ((gimple_phi_arg_def (phi, 0) == lhs1
-		       && gimple_phi_arg_def (phi, 1) == rhs1)
-		      || (gimple_phi_arg_def (phi, 1) == lhs1
-			  && gimple_phi_arg_def (phi, 0) == rhs1))
-		    {
-		      if (dump_file && (dump_flags & TDF_DETAILS))
-			fprintf (dump_file,
-				 "Block %d appears to be a join point for "
-				 "if-convertable half-diamond.\n",
-				 bb->index);
-		      return false;
-		    }
-		}
-	    }
+	  num_phis++;
+	  if (num_phis > max_num_phis)
+	    break;
 	}
-    }
-
-  /* Canonicalize the form.  */
-  if (single_pred_p (pred1) && single_pred (pred1) == pred2
-      && num_stmts_in_pred1 == 0)
-    std::swap (pred1, pred2);
-
-  /* This is meant to catch another kind of cases that are likely opportunities
-     for if-conversion.  After canonicalizing, PRED2 must be an empty block and
-     PRED1 must be the only predecessor of PRED2.  Moreover, PRED1 is supposed
-     to end with a cond_stmt which has the same args with the PHI in BB.  */
-  if (single_pred_p (pred2) && single_pred (pred2) == pred1
-      && num_stmts_in_pred2 == 0)
-    {
-      if (gcond *cond_stmt = dyn_cast <gcond *> (*gsi_last_bb (pred1)))
+      if (num_phis <= max_num_phis
+	  && !poor_ifcvt_pred (pred1, bb)
+	  && !poor_ifcvt_pred (pred2, bb))
 	{
-	  tree lhs = gimple_cond_lhs (cond_stmt);
-	  tree rhs = gimple_cond_rhs (cond_stmt);
-
-	  gimple_stmt_iterator gsi;
-	  for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi))
-	    {
-	      gimple *phi = gsi_stmt (gsi);
-	      if ((operand_equal_p (gimple_phi_arg_def (phi, 0), lhs)
-		   && operand_equal_p (gimple_phi_arg_def (phi, 1), rhs))
-		  || (operand_equal_p (gimple_phi_arg_def (phi, 0), rhs)
-		      && (operand_equal_p (gimple_phi_arg_def (phi, 1), lhs))))
-		{
-		  if (dump_file && (dump_flags & TDF_DETAILS))
-		    fprintf (dump_file,
-			     "Block %d appears to be optimized to a join "
-			     "point for if-convertable half-diamond.\n",
-			     bb->index);
-		  return false;
-		}
-	    }
+	  if (dump_file && (dump_flags & TDF_DETAILS))
+	    fprintf (dump_file,
+		     "Block %d appears to be a join point for "
+		     "if-convertable bbs.\n",
+		     bb->index);
+	  return false;
 	}
     }
 
diff --git a/gcc/testsuite/g++.dg/tree-ssa/pr88797.C b/gcc/testsuite/g++.dg/tree-ssa/pr88797.C
index 75391d6c049..df1df89fa67 100644
--- a/gcc/testsuite/g++.dg/tree-ssa/pr88797.C
+++ b/gcc/testsuite/g++.dg/tree-ssa/pr88797.C
@@ -12,5 +12,5 @@  void test_f(unsigned x, unsigned y) {
 }
 
 /* { dg-final { scan-tree-dump-not "Duplicating join block" "split-paths" } } */
-/* { dg-final { scan-tree-dump-times "Block . is a join that does not expose" 1 "split-paths" } } */
+/* { dg-final { scan-tree-dump-times "appears to be a join point for if-convertable bbs." 1 "split-paths" } } */
 
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/split-path-11.c b/gcc/testsuite/gcc.dg/tree-ssa/split-path-11.c
index 66f57d92edb..6c15c16151b 100644
--- a/gcc/testsuite/gcc.dg/tree-ssa/split-path-11.c
+++ b/gcc/testsuite/gcc.dg/tree-ssa/split-path-11.c
@@ -11,4 +11,4 @@  void foo(unsigned long long *M)
     }
 }
 
-/* { dg-final { scan-tree-dump-times "join point for if-convertable half-diamond" 1 "split-paths" } } */
+/* { dg-final { scan-tree-dump-times "join point for if-convertable" 1 "split-paths" } } */
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/split-path-13.c b/gcc/testsuite/gcc.dg/tree-ssa/split-path-13.c
new file mode 100644
index 00000000000..8a24972d050
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/split-path-13.c
@@ -0,0 +1,26 @@ 
+/* { dg-do compile } */
+/* { dg-options "-O2 -fsplit-paths -fdump-tree-split-paths-details " } */
+/* PR tree-optimization/112402 */
+/* This is similar to split-path-2.c but instead of the add
+   being inside both sides, we have a constant. */
+
+int
+foo(signed char *p, int n)
+{
+  int s = 0;
+  int i;
+
+  for (i = 0; i < n; i++) {
+    int t;
+    if (p[i] >= 0)
+      t = 1;
+    else
+      t = -1;
+    s += t;
+  }
+
+  return s;
+}
+
+/* { dg-final { scan-tree-dump "appears to be a join point for if-convertable" "split-paths" } } */
+
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/split-path-2.c b/gcc/testsuite/gcc.dg/tree-ssa/split-path-2.c
index 8f503f236a6..73c21635388 100644
--- a/gcc/testsuite/gcc.dg/tree-ssa/split-path-2.c
+++ b/gcc/testsuite/gcc.dg/tree-ssa/split-path-2.c
@@ -17,5 +17,5 @@  foo(signed char *p, int n)
   return s;
 }
 
-/* { dg-final { scan-tree-dump "appears to be a join point for if-convertable diamond" "split-paths" } } */
+/* { dg-final { scan-tree-dump "appears to be a join point for if-convertable" "split-paths" } } */
 
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/split-path-5.c b/gcc/testsuite/gcc.dg/tree-ssa/split-path-5.c
index 88c3a55b968..317a55f158a 100644
--- a/gcc/testsuite/gcc.dg/tree-ssa/split-path-5.c
+++ b/gcc/testsuite/gcc.dg/tree-ssa/split-path-5.c
@@ -41,4 +41,4 @@  bmhi_init (const signed char *pattern)
     }
 }
 
-/* { dg-final { scan-tree-dump-times "join point for if-convertable half-diamond" 1 "split-paths" } } */
+/* { dg-final { scan-tree-dump-times "join point for if-convertable" 1 "split-paths" } } */
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/split-path-6.c b/gcc/testsuite/gcc.dg/tree-ssa/split-path-6.c
index 5f5dd157601..71e6362b10c 100644
--- a/gcc/testsuite/gcc.dg/tree-ssa/split-path-6.c
+++ b/gcc/testsuite/gcc.dg/tree-ssa/split-path-6.c
@@ -57,6 +57,8 @@  oof (void)
     }
 }
 
+
+/* lookharder becomes an ifcvt'd/cmov. */
 void
 lookharder (char *string)
 {
@@ -73,4 +75,4 @@  lookharder (char *string)
     }
 }
 
-/* { dg-final { scan-tree-dump-times "Duplicating join block" 3 "split-paths" } } */
+/* { dg-final { scan-tree-dump-times "Duplicating join block" 2 "split-paths" } } */