PR 55875 (IV wrapping issue)

[Jan Hubicka <hubicka at ucw dot cz>]

Hi,
My patch to add bounds that are not dominating loop latch caused problem in
scev_probably_wraps_p that is trying to prove that given IV at given STMT is
not wrapping based on loop bounds.  When I was extending loop bounds to contain
not only statements that dominate the loop latch, I verified the users that
they are valid after the change.  In this case it is however not true. What I
missed is that it does two things

1) it tries to prove that STMT is bounded by given bound based on fact that
bound's STMT dominate the statement
2) it tries to prove the bound based on number of iterations of loop that it
derrives from the bounds

I saw the dominance test in there and was happy. Obviously however 2) needs to
be updated.  It seems to me best to simply drop 2) that anyway is just
determining a bound on number of iterations and use the bound recorded in the
structure.

While doing that I also noticed older problem in the postdominance
test - we need to verify that loop is not terminated by a call or other side
ffect as demonstrated by the new C testcase I constructed.  This testcase
probably fails in 4.7 and earlier releases.

Boostrapped/regtested x86_64-linux

Honza

	* gcc.c-torture/execute/pr55875.c: New testcase.
	* g++.dg/torture/pr55875.C: New testcase.

	* tree-ssa-loop-niter.c (n_of_executions_at_most): Simplify
	to only test for cases where statement is dominated by the
	particular bound; handle correctly the "postdominance"
	test.
	(scev_probably_wraps_p): Use max loop iterations info
	as a global bound first.

Index: testsuite/gcc.c-torture/execute/pr55875.c
===================================================================
--- testsuite/gcc.c-torture/execute/pr55875.c	(revision 0)
+++ testsuite/gcc.c-torture/execute/pr55875.c	(revision 0)
@@ -0,0 +1,17 @@
+int a[250];
+__attribute__ ((noinline))
+t(int i)
+{
+  if (i==0)
+    exit(0);
+  if (i>255)
+    abort ();
+}
+main()
+{
+  unsigned int i;
+  for (i=0;;i++)
+    {
+      a[i]=t((unsigned char)(i+5));
+    }
+}
Index: testsuite/g++.dg/torture/pr55875.C
===================================================================
--- testsuite/g++.dg/torture/pr55875.C	(revision 0)
+++ testsuite/g++.dg/torture/pr55875.C	(revision 0)
@@ -0,0 +1,53 @@
+struct A
+{
+  short int a1;
+  unsigned char a2;
+  unsigned int a3;
+};
+
+struct B
+{
+  unsigned short b1;
+  const A *b2;
+};
+
+B b;
+
+__attribute__((noinline, noclone))
+int foo (unsigned x)
+{
+  __asm volatile ("" : "+r" (x) : : "memory");
+  return x;
+}
+
+inline void
+bar (const int &)
+{
+}
+
+__attribute__((noinline)) void
+baz ()
+{
+  const A *a = b.b2;
+  unsigned int i;
+  unsigned short n = b.b1;
+  for (i = 0; i < n; ++i)
+    if (a[i].a1 == 11)
+      {
+    if (i > 0 && (a[i - 1].a2 & 1))
+      continue;
+    bar (foo (2));
+    return;
+      }
+}
+
+int
+main ()
+{
+  A a[4] = { { 10, 0, 0 }, { 11, 1, 0 }, { 11, 1, 0 }, { 11, 1, 0 } };
+  b.b1 = 4;
+  b.b2 = a;
+  baz ();
+  return 0;
+}
+
Index: tree-ssa-loop-niter.c
===================================================================
--- tree-ssa-loop-niter.c	(revision 194918)
+++ tree-ssa-loop-niter.c	(working copy)
@@ -3549,8 +3549,15 @@ stmt_dominates_stmt_p (gimple s1, gimple
 /* Returns true when we can prove that the number of executions of
    STMT in the loop is at most NITER, according to the bound on
    the number of executions of the statement NITER_BOUND->stmt recorded in
-   NITER_BOUND.  If STMT is NULL, we must prove this bound for all
-   statements in the loop.  */
+   NITER_BOUND and fact that NITER_BOUND->stmt dominate STMT.
+
+   ??? This code can become quite a CPU hog - we can have many bounds,
+   and large basic block forcing stmt_dominates_stmt_p to be queried
+   many times on a large basic blocks, so the whole thing is O(n^2)
+   for scev_probably_wraps_p invocation (that can be done n times).
+
+   It would make more sense (and give better answers) to remember BB
+   bounds computed by discover_iteration_bound_by_body_walk.  */
 
 static bool
 n_of_executions_at_most (gimple stmt,
@@ -3571,32 +3578,37 @@ n_of_executions_at_most (gimple stmt,
   /* We know that NITER_BOUND->stmt is executed at most NITER_BOUND->bound + 1
      times.  This means that:
 
-     -- if NITER_BOUND->is_exit is true, then everything before
-        NITER_BOUND->stmt is executed at most NITER_BOUND->bound + 1
-	times, and everything after it at most NITER_BOUND->bound times.
+     -- if NITER_BOUND->is_exit is true, then everything after
+	it at most NITER_BOUND->bound times.
 
      -- If NITER_BOUND->is_exit is false, then if we can prove that when STMT
 	is executed, then NITER_BOUND->stmt is executed as well in the same
-	iteration (we conclude that if both statements belong to the same
-	basic block, or if STMT is after NITER_BOUND->stmt), then STMT
-	is executed at most NITER_BOUND->bound + 1 times.  Otherwise STMT is
-	executed at most NITER_BOUND->bound + 2 times.  */
+	iteration then STMT is executed at most NITER_BOUND->bound + 1 times. 
+
+	If we can determine that NITER_BOUND->stmt is always executed
+	after STMT, then STMT is executed at most NITER_BOUND->bound + 2 times.
+	We conclude that if both statements belong to the same
+	basic block and STMT is before NITER_BOUND->stmt and there are no
+	statements with side effects in between.  */
 
   if (niter_bound->is_exit)
     {
-      if (stmt
-	  && stmt != niter_bound->stmt
-	  && stmt_dominates_stmt_p (niter_bound->stmt, stmt))
-	cmp = GE_EXPR;
-      else
-	cmp = GT_EXPR;
+      if (stmt == niter_bound->stmt
+	  || !stmt_dominates_stmt_p (niter_bound->stmt, stmt))
+	return false;
+      cmp = GE_EXPR;
     }
   else
     {
-      if (!stmt
-	  || (gimple_bb (stmt) != gimple_bb (niter_bound->stmt)
-	      && !stmt_dominates_stmt_p (niter_bound->stmt, stmt)))
+      if (!stmt_dominates_stmt_p (niter_bound->stmt, stmt))
 	{
+	  if (gimple_bb (stmt) != gimple_bb (niter_bound->stmt)
+	      || gimple_code (stmt) == GIMPLE_PHI
+	      || gimple_code (niter_bound->stmt) == GIMPLE_PHI)
+	    return false;
+
+	  /* By stmt_dominates_stmt_p we already know that STMT appears
+	     before NITER_BOUND->STMT.  */
 	  bound += double_int_one;
 	  if (bound.is_zero ()
 	      || !double_int_fits_to_tree_p (nit_type, bound))
@@ -3640,10 +3652,12 @@ scev_probably_wraps_p (tree base, tree s
 		       gimple at_stmt, struct loop *loop,
 		       bool use_overflow_semantics)
 {
-  struct nb_iter_bound *bound;
   tree delta, step_abs;
   tree unsigned_type, valid_niter;
   tree type = TREE_TYPE (step);
+  tree e;
+  double_int niter;
+  struct nb_iter_bound *bound;
 
   /* FIXME: We really need something like
      http://gcc.gnu.org/ml/gcc-patches/2005-06/msg02025.html.
@@ -3706,14 +3720,26 @@ scev_probably_wraps_p (tree base, tree s
   valid_niter = fold_build2 (FLOOR_DIV_EXPR, unsigned_type, delta, step_abs);
 
   estimate_numbers_of_iterations_loop (loop);
-  for (bound = loop->bounds; bound; bound = bound->next)
+
+  if (max_loop_iterations (loop, &niter)
+      && double_int_fits_to_tree_p (TREE_TYPE (valid_niter), niter)
+      && (e = fold_binary (GT_EXPR, boolean_type_node, valid_niter,
+			   double_int_to_tree (TREE_TYPE (valid_niter),
+					       niter))) != NULL
+      && integer_nonzerop (e))
     {
-      if (n_of_executions_at_most (at_stmt, bound, valid_niter))
-	{
-	  fold_undefer_and_ignore_overflow_warnings ();
-	  return false;
-	}
+      fold_undefer_and_ignore_overflow_warnings ();
+      return false;
     }
+  if (at_stmt)
+    for (bound = loop->bounds; bound; bound = bound->next)
+      {
+	if (n_of_executions_at_most (at_stmt, bound, valid_niter))
+	  {
+	    fold_undefer_and_ignore_overflow_warnings ();
+	    return false;
+	  }
+      }
 
   fold_undefer_and_ignore_overflow_warnings ();