[PATCH] Fix PR88533

[PATCH] Fix PR88533

[Richard Biener]

With the patch for PR85275 I throttled loop-header copying too much.
The following reverts that patch and instead adds heuristics to
should_duplicate_loop_header_p as to _not_ copy exit tests that
are based on non-IV/invariant tests.  Since CH runs before any
LIM we have to keep track of what is invariant ourselves.  Then
it's also easy enough to see what tests are based on IVs without
resorting to SCEV which would be limited in some cases as well.

Bootstrapped and tested on x86_64-unknown-linux-gnu, applied to trunk.

Richard.

2018-12-19  Richard Biener  <rguenther@suse.de>

	PR tree-optimization/88533
	Revert
	2018-04-30  Richard Biener  <rguenther@suse.de>

	PR tree-optimization/28364
	PR tree-optimization/85275
	* tree-ssa-loop-ch.c (ch_base::copy_headers): Stop after
	copying first exit test.

	* gcc.dg/tree-ssa/ssa-dom-thread-7.c: Adjust.

	* tree-ssa-loop-ch.c: Include tree-phinodes.h and
	ssa-iterators.h.
	(should_duplicate_loop_header_p): Track whether stmt compute
	loop invariants or values based on IVs.  Apart from the
	original loop header only duplicate blocks with exit tests
	that are based on IVs or invariants.

	* gcc.dg/tree-ssa/copy-headers-6.c: New testcase.
	* gcc.dg/tree-ssa/copy-headers-7.c: Likewise.
	* gcc.dg/tree-ssa/ivopt_mult_1.c: Un-XFAIL.
	* gcc.dg/tree-ssa/ivopt_mult_2.c: Likewise.

Index: gcc/testsuite/gcc.dg/tree-ssa/copy-headers-6.c
===================================================================
--- gcc/testsuite/gcc.dg/tree-ssa/copy-headers-6.c	(nonexistent)
+++ gcc/testsuite/gcc.dg/tree-ssa/copy-headers-6.c	(working copy)
@@ -0,0 +1,16 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-ch2-details" } */
+
+int is_sorted(int *a, int n)
+{
+  for (int i = 0; i < n - 1; i++)
+    if (a[i] > 0)
+      return 0;
+  return 1;
+}
+
+/* Verify we apply loop header copying but only copy the IV test and
+   not the alternate exit test.  */
+
+/* { dg-final { scan-tree-dump "is now do-while loop" "ch2" } } */
+/* { dg-final { scan-tree-dump-times "  if " 3 "ch2" } } */
Index: gcc/testsuite/gcc.dg/tree-ssa/copy-headers-7.c
===================================================================
--- gcc/testsuite/gcc.dg/tree-ssa/copy-headers-7.c	(nonexistent)
+++ gcc/testsuite/gcc.dg/tree-ssa/copy-headers-7.c	(working copy)
@@ -0,0 +1,16 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-ch2-details --param logical-op-non-short-circuit=0" } */
+
+int is_sorted(int *a, int n, int m, int k)
+{
+  for (int i = 0; i < n - 1 && m && k > i; i++)
+    if (a[i] > a[i + 1])
+      return 0;
+  return 1;
+}
+
+/* Verify we apply loop header copying but only copy the IV tests and
+   the invariant test, not the alternate exit test.  */
+
+/* { dg-final { scan-tree-dump "is now do-while loop" "ch2" } } */
+/* { dg-final { scan-tree-dump-times "Will duplicate bb" 3 "ch2" } } */
Index: gcc/testsuite/gcc.dg/tree-ssa/ivopt_mult_1.c
===================================================================
--- gcc/testsuite/gcc.dg/tree-ssa/ivopt_mult_1.c	(revision 267232)
+++ gcc/testsuite/gcc.dg/tree-ssa/ivopt_mult_1.c	(working copy)
@@ -20,4 +20,4 @@ long foo(long* p, long* p2, int N1, int
   return s;
 }
 
-/* { dg-final { scan-tree-dump-times "Replacing" 1 "ivopts" { xfail *-*-* } } } */
+/* { dg-final { scan-tree-dump-times "Replacing" 1 "ivopts" } } */
Index: gcc/testsuite/gcc.dg/tree-ssa/ivopt_mult_2.c
===================================================================
--- gcc/testsuite/gcc.dg/tree-ssa/ivopt_mult_2.c	(revision 267232)
+++ gcc/testsuite/gcc.dg/tree-ssa/ivopt_mult_2.c	(working copy)
@@ -21,4 +21,4 @@ long foo(long* p, long* p2, int N1, int
   return s;
 }
 
-/* { dg-final { scan-tree-dump-times "Replacing" 2 "ivopts" { xfail *-*-* } } } */
+/* { dg-final { scan-tree-dump-times "Replacing" 2 "ivopts" } } */
Index: gcc/testsuite/gcc.dg/tree-ssa/ssa-dom-thread-7.c
===================================================================
--- gcc/testsuite/gcc.dg/tree-ssa/ssa-dom-thread-7.c	(revision 267232)
+++ gcc/testsuite/gcc.dg/tree-ssa/ssa-dom-thread-7.c	(working copy)
@@ -2,7 +2,7 @@
 /* { dg-options "-O2 -fdump-tree-thread1-stats -fdump-tree-thread2-stats -fdump-tree-dom2-stats -fdump-tree-thread3-stats -fdump-tree-dom3-stats -fdump-tree-vrp2-stats -fno-guess-branch-probability" } */
 /* { dg-final { scan-tree-dump "Jumps threaded: 16"  "thread1" } } */
 /* { dg-final { scan-tree-dump "Jumps threaded: 9" "thread2" } } */
-/* { dg-final { scan-tree-dump "Jumps threaded: 1"  "dom2" } } */
+/* { dg-final { scan-tree-dump-not "Jumps threaded"  "dom2" } } */
 /* aarch64 has the highest CASE_VALUES_THRESHOLD in GCC.  It's high enough
    to change decisions in switch expansion which in turn can expose new
    jump threading opportunities.  Skip the later tests on aarch64.  */
Index: gcc/tree-ssa-loop-ch.c
===================================================================
--- gcc/tree-ssa-loop-ch.c	(revision 267232)
+++ gcc/tree-ssa-loop-ch.c	(working copy)
@@ -34,6 +34,8 @@ along with GCC; see the file COPYING3.
 #include "tree-ssa-scopedtables.h"
 #include "tree-ssa-threadedge.h"
 #include "tree-ssa-sccvn.h"
+#include "tree-phinodes.h"
+#include "ssa-iterators.h"
 #include "params.h"
 
 /* Duplicates headers of loops if they are small enough, so that the statements
@@ -50,7 +52,6 @@ should_duplicate_loop_header_p (basic_bl
 				int *limit)
 {
   gimple_stmt_iterator bsi;
-  gimple *last;
 
   gcc_assert (!header->aux);
 
@@ -99,8 +100,8 @@ should_duplicate_loop_header_p (basic_bl
       return false;
     }
 
-  last = last_stmt (header);
-  if (gimple_code (last) != GIMPLE_COND)
+  gcond *last = dyn_cast <gcond *> (last_stmt (header));
+  if (!last)
     {
       if (dump_file && (dump_flags & TDF_DETAILS))
 	fprintf (dump_file,
@@ -109,10 +110,24 @@ should_duplicate_loop_header_p (basic_bl
       return false;
     }
 
-  /* Count number of instructions and punt on calls.  */
+  for (gphi_iterator psi = gsi_start_phis (header); !gsi_end_p (psi);
+       gsi_next (&psi))
+    {
+      gphi *phi = psi.phi ();
+      tree res = gimple_phi_result (phi);
+      if (INTEGRAL_TYPE_P (TREE_TYPE (res))
+	  || POINTER_TYPE_P (TREE_TYPE (res)))
+	gimple_set_uid (phi, 1 /* IV */);
+      else
+	gimple_set_uid (phi, 0);
+    }
+
+  /* Count number of instructions and punt on calls.
+     Populate stmts INV/IV flag to later apply heuristics to the
+     kind of conditions we want to copy.  */
   for (bsi = gsi_start_bb (header); !gsi_end_p (bsi); gsi_next (&bsi))
     {
-      last = gsi_stmt (bsi);
+      gimple *last = gsi_stmt (bsi);
 
       if (gimple_code (last) == GIMPLE_LABEL)
 	continue;
@@ -142,7 +157,52 @@ should_duplicate_loop_header_p (basic_bl
 		     header->index);
 	  return false;
 	}
+
+      /* Classify the stmt based on whether its computation is based
+         on a IV or whether it is invariant in the loop.  */
+      gimple_set_uid (last, 0);
+      if (!gimple_vuse (last))
+	{
+	  bool inv = true;
+	  bool iv = false;
+	  ssa_op_iter i;
+	  tree op;
+	  FOR_EACH_SSA_TREE_OPERAND (op, last, i, SSA_OP_USE)
+	    if (!SSA_NAME_IS_DEFAULT_DEF (op)
+		&& flow_bb_inside_loop_p (loop,
+					  gimple_bb (SSA_NAME_DEF_STMT (op))))
+	      {
+		if (!(gimple_uid (SSA_NAME_DEF_STMT (op)) & 2 /* INV */))
+		  inv = false;
+		if (gimple_uid (SSA_NAME_DEF_STMT (op)) & 1 /* IV */)
+		  iv = true;
+	      }
+	  gimple_set_uid (last, (iv ? 1 : 0) | (inv ? 2 : 0));
+	}
     }
+
+  /* If the condition tests a non-IV loop variant we do not want to rotate
+     the loop further.  Unless this is the original loop header.  */
+  tree lhs = gimple_cond_lhs (last);
+  tree rhs = gimple_cond_rhs (last);
+  if (header != loop->header
+      && ((TREE_CODE (lhs) == SSA_NAME
+	   && !SSA_NAME_IS_DEFAULT_DEF (lhs)
+	   && flow_bb_inside_loop_p (loop, gimple_bb (SSA_NAME_DEF_STMT (lhs)))
+	   && gimple_uid (SSA_NAME_DEF_STMT (lhs)) == 0)
+	  || (TREE_CODE (rhs) == SSA_NAME
+	      && !SSA_NAME_IS_DEFAULT_DEF (rhs)
+	      && flow_bb_inside_loop_p (loop,
+					gimple_bb (SSA_NAME_DEF_STMT (rhs)))
+	      && gimple_uid (SSA_NAME_DEF_STMT (rhs)) == 0)))
+    {
+      if (dump_file && (dump_flags & TDF_DETAILS))
+	fprintf (dump_file,
+		 "  Not duplicating bb %i: condition based on non-IV loop"
+		 "variant.\n", header->index);
+      return false;
+    }
+
   if (dump_file && (dump_flags & TDF_DETAILS))
     fprintf (dump_file, "    Will duplicate bb %i\n", header->index); 
   return true;
@@ -343,11 +403,6 @@ ch_base::copy_headers (function *fun)
 	  bbs[n_bbs++] = header;
 	  gcc_assert (bbs_size > n_bbs);
 	  header = exit->dest;
-	  /* Make sure to stop copying after we copied the first exit test.
-	     Without further heuristics we do not want to rotate the loop
-	     any further.  */
-	  if (loop_exits_from_bb_p (loop, exit->src))
-	    break;
 	}
 
       if (!exit)