PR 55875 (IV wrapping issue)

Hi,
I actually attached not completely final version of the patch.  This one has
the extra loop looking for side effect that cures the first testcase.

Sorry for the confussion.
Honza

	PR tree-optimize/55875
	* 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.

On Tue, Jan 08, 2013 at 05:49:28PM +0100, Jan Hubicka wrote:
> --- testsuite/gcc.c-torture/execute/pr55875.c	(revision 0)
> +++ testsuite/gcc.c-torture/execute/pr55875.c	(revision 0)
> @@ -0,0 +1,17 @@

Please add
/* PR tree-optimization/55875 */
here.

> +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)

And

// PR tree-optimization/55875
// { dg-do run }

here, dg-do compile is the default.

> @@ -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;

There should be tabs on the 4 above lines, just bugzilla ate it.

	Jakub

Hi,
here is even more updated patch, this time really fixing the testcase, I hope ;)
It turns out there is one extra problem in tree-ssa-loop-niter.c triggered by
that code.  Some bounds, like one based on inequality test or with wrapping
IVs are bounds only when they are executed every iteration.

Boostrapped/regtested x86_64-linux.

Honza

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

	* tree-ssa-loop-niter.c (number_of_iterations_cond): Add
	EVERY_ITERATION parameter.
	(number_of_iterations_exit): Check if exit is executed every
	iteration.
	(idx_infer_loop_bounds): Similarly here.
	(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: tree-ssa-loop-niter.c
===================================================================
*** tree-ssa-loop-niter.c	(revision 194918)
--- tree-ssa-loop-niter.c	(working copy)
*************** dump_affine_iv (FILE *file, affine_iv *i
*** 1208,1213 ****
--- 1208,1215 ----
     -- in this case we can use the information whether the control induction
     variables can overflow or not in a more efficient way.
  
+    if EVERY_ITERATION is true, we know the test is executed on every iteration.
+ 
     The results (number of iterations and assumptions as described in
     comments at struct tree_niter_desc in tree-flow.h) are stored to NITER.
     Returns false if it fails to determine number of iterations, true if it
*************** static bool
*** 1217,1227 ****
  number_of_iterations_cond (struct loop *loop,
  			   tree type, affine_iv *iv0, enum tree_code code,
  			   affine_iv *iv1, struct tree_niter_desc *niter,
! 			   bool only_exit)
  {
    bool exit_must_be_taken = false, ret;
    bounds bnds;
  
    /* The meaning of these assumptions is this:
       if !assumptions
         then the rest of information does not have to be valid
--- 1219,1239 ----
  number_of_iterations_cond (struct loop *loop,
  			   tree type, affine_iv *iv0, enum tree_code code,
  			   affine_iv *iv1, struct tree_niter_desc *niter,
! 			   bool only_exit, bool every_iteration)
  {
    bool exit_must_be_taken = false, ret;
    bounds bnds;
  
+   /* If the test is not executed every iteration, wrapping may make the test
+      to pass again. 
+      TODO: the overflow case can be still used as unreliable estimate of upper
+      bound.  But we have no API to pass it down to number of iterations code
+      and, at present, it will not use it anyway.  */
+   if (!every_iteration
+       && (!iv0->no_overflow || !iv1->no_overflow
+ 	  || code == NE_EXPR || code == EQ_EXPR))
+     return false;
+ 
    /* The meaning of these assumptions is this:
       if !assumptions
         then the rest of information does not have to be valid
*************** number_of_iterations_exit (struct loop *
*** 1807,1815 ****
    tree op0, op1;
    enum tree_code code;
    affine_iv iv0, iv1;
  
!   if (every_iteration
!       && !dominated_by_p (CDI_DOMINATORS, loop->latch, exit->src))
      return false;
  
    niter->assumptions = boolean_false_node;
--- 1819,1829 ----
    tree op0, op1;
    enum tree_code code;
    affine_iv iv0, iv1;
+   bool safe;
  
!   safe = dominated_by_p (CDI_DOMINATORS, loop->latch, exit->src);
! 
!   if (every_iteration && !safe)
      return false;
  
    niter->assumptions = boolean_false_node;
*************** number_of_iterations_exit (struct loop *
*** 1855,1861 ****
    iv0.base = expand_simple_operations (iv0.base);
    iv1.base = expand_simple_operations (iv1.base);
    if (!number_of_iterations_cond (loop, type, &iv0, code, &iv1, niter,
! 				  loop_only_exit_p (loop, exit)))
      {
        fold_undefer_and_ignore_overflow_warnings ();
        return false;
--- 1869,1875 ----
    iv0.base = expand_simple_operations (iv0.base);
    iv1.base = expand_simple_operations (iv1.base);
    if (!number_of_iterations_cond (loop, type, &iv0, code, &iv1, niter,
! 				  loop_only_exit_p (loop, exit), safe))
      {
        fold_undefer_and_ignore_overflow_warnings ();
        return false;
*************** idx_infer_loop_bounds (tree base, tree *
*** 2657,2662 ****
--- 2671,2677 ----
    tree low, high, type, next;
    bool sign, upper = true, at_end = false;
    struct loop *loop = data->loop;
+   bool reliable = true;
  
    if (TREE_CODE (base) != ARRAY_REF)
      return true;
*************** idx_infer_loop_bounds (tree base, tree *
*** 2728,2734 ****
        && tree_int_cst_compare (next, high) <= 0)
      return true;
  
!   record_nonwrapping_iv (loop, init, step, data->stmt, low, high, true, upper);
    return true;
  }
  
--- 2743,2756 ----
        && tree_int_cst_compare (next, high) <= 0)
      return true;
  
!   /* If access is not executed on every iteration, we must ensure that overlow may
!      not make the access valid later.  */
!   if (!dominated_by_p (CDI_DOMINATORS, loop->latch, gimple_bb (data->stmt))
!       && scev_probably_wraps_p (initial_condition_in_loop_num (ev, loop->num),
! 				step, data->stmt, loop, true))
!     reliable = false;
! 
!   record_nonwrapping_iv (loop, init, step, data->stmt, low, high, reliable, upper);
    return true;
  }
  
*************** stmt_dominates_stmt_p (gimple s1, gimple
*** 3549,3556 ****
  /* 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.  */
  
  static bool
  n_of_executions_at_most (gimple stmt,
--- 3571,3585 ----
  /* 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 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,
*************** n_of_executions_at_most (gimple stmt,
*** 3571,3602 ****
    /* 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 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.  */
  
    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;
      }
    else
      {
!       if (!stmt
! 	  || (gimple_bb (stmt) != gimple_bb (niter_bound->stmt)
! 	      && !stmt_dominates_stmt_p (niter_bound->stmt, stmt)))
  	{
  	  bound += double_int_one;
  	  if (bound.is_zero ()
  	      || !double_int_fits_to_tree_p (nit_type, bound))
--- 3600,3642 ----
    /* 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 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 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 == niter_bound->stmt
! 	  || !stmt_dominates_stmt_p (niter_bound->stmt, stmt))
! 	return false;
!       cmp = GE_EXPR;
      }
    else
      {
!       if (!stmt_dominates_stmt_p (niter_bound->stmt, stmt))
  	{
+           gimple_stmt_iterator bsi;
+ 	  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.  Still need to test that the loop
+ 	     can not be terinated by a side effect in between.  */
+ 	  for (bsi = gsi_for_stmt (stmt); gsi_stmt (bsi) != niter_bound->stmt;
+ 	       gsi_next (&bsi))
+ 	    if (gimple_has_side_effects (gsi_stmt (bsi)))
+ 	       return false;
  	  bound += double_int_one;
  	  if (bound.is_zero ()
  	      || !double_int_fits_to_tree_p (nit_type, bound))
*************** scev_probably_wraps_p (tree base, tree s
*** 3640,3649 ****
  		       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);
  
    /* FIXME: We really need something like
       http://gcc.gnu.org/ml/gcc-patches/2005-06/msg02025.html.
--- 3680,3691 ----
  		       gimple at_stmt, struct loop *loop,
  		       bool use_overflow_semantics)
  {
    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.
*************** scev_probably_wraps_p (tree base, tree s
*** 3706,3719 ****
    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 (n_of_executions_at_most (at_stmt, bound, valid_niter))
! 	{
! 	  fold_undefer_and_ignore_overflow_warnings ();
! 	  return false;
! 	}
      }
  
    fold_undefer_and_ignore_overflow_warnings ();
  
--- 3748,3773 ----
    valid_niter = fold_build2 (FLOOR_DIV_EXPR, unsigned_type, delta, step_abs);
  
    estimate_numbers_of_iterations_loop (loop);
! 
!   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))
      {
!       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 ();
  
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 ****
--- 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/20070621-1.C
===================================================================
*** testsuite/g++.dg/torture/20070621-1.C	(revision 195032)
--- testsuite/g++.dg/torture/20070621-1.C	(working copy)
***************
*** 1,3 ****
--- 1,4 ----
+ // { dg-do compile }
  /* Reduced from libstdc++-v3/testsuite/25_algorithms/equal/1.cc
  
  1.2.ii: In function 'void test1()':
Index: testsuite/g++.dg/torture/pr55875.C
===================================================================
*** testsuite/g++.dg/torture/pr55875.C	(revision 0)
--- testsuite/g++.dg/torture/pr55875.C	(revision 0)
***************
*** 0 ****
--- 1,55 ----
+ // { dg-do run }
+ 
+ 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;
+ }
+

On Tue, 8 Jan 2013, Jan Hubicka wrote:

> Hi,
> here is even more updated patch, this time really fixing the testcase, I hope ;)
> It turns out there is one extra problem in tree-ssa-loop-niter.c triggered by
> that code.  Some bounds, like one based on inequality test or with wrapping
> IVs are bounds only when they are executed every iteration.
> 
> Boostrapped/regtested x86_64-linux.
> 
> Honza
> 
> 	PR tree-optimiation/55875
> 	* gcc.c-torture/execute/pr55875.c: New testcase.
> 	* g++.dg/torture/pr55875.C: New testcase.
> 
> 	* tree-ssa-loop-niter.c (number_of_iterations_cond): Add
> 	EVERY_ITERATION parameter.
> 	(number_of_iterations_exit): Check if exit is executed every
> 	iteration.
> 	(idx_infer_loop_bounds): Similarly here.
> 	(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: tree-ssa-loop-niter.c
> ===================================================================
> *** tree-ssa-loop-niter.c	(revision 194918)
> --- tree-ssa-loop-niter.c	(working copy)
> *************** dump_affine_iv (FILE *file, affine_iv *i
> *** 1208,1213 ****
> --- 1208,1215 ----
>      -- in this case we can use the information whether the control induction
>      variables can overflow or not in a more efficient way.
>   
> +    if EVERY_ITERATION is true, we know the test is executed on every iteration.
> + 
>      The results (number of iterations and assumptions as described in
>      comments at struct tree_niter_desc in tree-flow.h) are stored to NITER.
>      Returns false if it fails to determine number of iterations, true if it
> *************** static bool
> *** 1217,1227 ****
>   number_of_iterations_cond (struct loop *loop,
>   			   tree type, affine_iv *iv0, enum tree_code code,
>   			   affine_iv *iv1, struct tree_niter_desc *niter,
> ! 			   bool only_exit)
>   {
>     bool exit_must_be_taken = false, ret;
>     bounds bnds;
>   
>     /* The meaning of these assumptions is this:
>        if !assumptions
>          then the rest of information does not have to be valid
> --- 1219,1239 ----
>   number_of_iterations_cond (struct loop *loop,
>   			   tree type, affine_iv *iv0, enum tree_code code,
>   			   affine_iv *iv1, struct tree_niter_desc *niter,
> ! 			   bool only_exit, bool every_iteration)
>   {
>     bool exit_must_be_taken = false, ret;
>     bounds bnds;
>   
> +   /* If the test is not executed every iteration, wrapping may make the test
> +      to pass again. 
> +      TODO: the overflow case can be still used as unreliable estimate of upper
> +      bound.  But we have no API to pass it down to number of iterations code
> +      and, at present, it will not use it anyway.  */
> +   if (!every_iteration
> +       && (!iv0->no_overflow || !iv1->no_overflow
> + 	  || code == NE_EXPR || code == EQ_EXPR))
> +     return false;
> + 
>     /* The meaning of these assumptions is this:
>        if !assumptions
>          then the rest of information does not have to be valid
> *************** number_of_iterations_exit (struct loop *
> *** 1807,1815 ****
>     tree op0, op1;
>     enum tree_code code;
>     affine_iv iv0, iv1;
>   
> !   if (every_iteration
> !       && !dominated_by_p (CDI_DOMINATORS, loop->latch, exit->src))
>       return false;
>   
>     niter->assumptions = boolean_false_node;
> --- 1819,1829 ----
>     tree op0, op1;
>     enum tree_code code;
>     affine_iv iv0, iv1;
> +   bool safe;
>   
> !   safe = dominated_by_p (CDI_DOMINATORS, loop->latch, exit->src);
> ! 
> !   if (every_iteration && !safe)
>       return false;
>   
>     niter->assumptions = boolean_false_node;
> *************** number_of_iterations_exit (struct loop *
> *** 1855,1861 ****
>     iv0.base = expand_simple_operations (iv0.base);
>     iv1.base = expand_simple_operations (iv1.base);
>     if (!number_of_iterations_cond (loop, type, &iv0, code, &iv1, niter,
> ! 				  loop_only_exit_p (loop, exit)))
>       {
>         fold_undefer_and_ignore_overflow_warnings ();
>         return false;
> --- 1869,1875 ----
>     iv0.base = expand_simple_operations (iv0.base);
>     iv1.base = expand_simple_operations (iv1.base);
>     if (!number_of_iterations_cond (loop, type, &iv0, code, &iv1, niter,
> ! 				  loop_only_exit_p (loop, exit), safe))
>       {
>         fold_undefer_and_ignore_overflow_warnings ();
>         return false;
> *************** idx_infer_loop_bounds (tree base, tree *
> *** 2657,2662 ****
> --- 2671,2677 ----
>     tree low, high, type, next;
>     bool sign, upper = true, at_end = false;
>     struct loop *loop = data->loop;
> +   bool reliable = true;
>   
>     if (TREE_CODE (base) != ARRAY_REF)
>       return true;
> *************** idx_infer_loop_bounds (tree base, tree *
> *** 2728,2734 ****
>         && tree_int_cst_compare (next, high) <= 0)
>       return true;
>   
> !   record_nonwrapping_iv (loop, init, step, data->stmt, low, high, true, upper);
>     return true;
>   }
>   
> --- 2743,2756 ----
>         && tree_int_cst_compare (next, high) <= 0)
>       return true;
>   
> !   /* If access is not executed on every iteration, we must ensure that overlow may
> !      not make the access valid later.  */
> !   if (!dominated_by_p (CDI_DOMINATORS, loop->latch, gimple_bb (data->stmt))
> !       && scev_probably_wraps_p (initial_condition_in_loop_num (ev, loop->num),
> ! 				step, data->stmt, loop, true))
> !     reliable = false;
> ! 
> !   record_nonwrapping_iv (loop, init, step, data->stmt, low, high, reliable, upper);
>     return true;
>   }
>   
> *************** stmt_dominates_stmt_p (gimple s1, gimple
> *** 3549,3556 ****
>   /* 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.  */
>   
>   static bool
>   n_of_executions_at_most (gimple stmt,
> --- 3571,3585 ----
>   /* 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 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,
> *************** n_of_executions_at_most (gimple stmt,
> *** 3571,3602 ****
>     /* 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 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.  */
>   
>     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;
>       }
>     else
>       {
> !       if (!stmt
> ! 	  || (gimple_bb (stmt) != gimple_bb (niter_bound->stmt)
> ! 	      && !stmt_dominates_stmt_p (niter_bound->stmt, stmt)))
>   	{
>   	  bound += double_int_one;
>   	  if (bound.is_zero ()
>   	      || !double_int_fits_to_tree_p (nit_type, bound))
> --- 3600,3642 ----
>     /* 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 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 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 == niter_bound->stmt
> ! 	  || !stmt_dominates_stmt_p (niter_bound->stmt, stmt))
> ! 	return false;
> !       cmp = GE_EXPR;
>       }
>     else
>       {
> !       if (!stmt_dominates_stmt_p (niter_bound->stmt, stmt))
>   	{
> +           gimple_stmt_iterator bsi;
> + 	  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.  Still need to test that the loop
> + 	     can not be terinated by a side effect in between.  */
> + 	  for (bsi = gsi_for_stmt (stmt); gsi_stmt (bsi) != niter_bound->stmt;
> + 	       gsi_next (&bsi))
> + 	    if (gimple_has_side_effects (gsi_stmt (bsi)))
> + 	       return false;

Ugh.  Both to stmt_dominates_stmt_p and to this (both use loops).
For stmt_dominates_stmt_p you'd simply use GIMPLE uids as other
passes do (and compute them, of course), for the above you'd
alongside of the UID store a sequence number that increments
at each stmt with side-effect.  UID is 32bits, so you could
even store (stmt-number-in-bb << 8) | side-effect-nr in UID
(with the issue that if there are exactly 256 side-effect stmts
inbetween the two stmts you'd miss that fact ...).

Well.  At least those loops are a real issue IMHO.  Adding a
second doesn't make complexity worse I understand - still ...
I expected better from you ;)

Patch is ok, but think about this for a minute - eventually
you can come up with sth very clever.

Thanks,
Richard.

>   	  bound += double_int_one;
>   	  if (bound.is_zero ()
>   	      || !double_int_fits_to_tree_p (nit_type, bound))
> *************** scev_probably_wraps_p (tree base, tree s
> *** 3640,3649 ****
>   		       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);
>   
>     /* FIXME: We really need something like
>        http://gcc.gnu.org/ml/gcc-patches/2005-06/msg02025.html.
> --- 3680,3691 ----
>   		       gimple at_stmt, struct loop *loop,
>   		       bool use_overflow_semantics)
>   {
>     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.
> *************** scev_probably_wraps_p (tree base, tree s
> *** 3706,3719 ****
>     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 (n_of_executions_at_most (at_stmt, bound, valid_niter))
> ! 	{
> ! 	  fold_undefer_and_ignore_overflow_warnings ();
> ! 	  return false;
> ! 	}
>       }
>   
>     fold_undefer_and_ignore_overflow_warnings ();
>   
> --- 3748,3773 ----
>     valid_niter = fold_build2 (FLOOR_DIV_EXPR, unsigned_type, delta, step_abs);
>   
>     estimate_numbers_of_iterations_loop (loop);
> ! 
> !   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))
>       {
> !       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 ();
>   
> 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 ****
> --- 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/20070621-1.C
> ===================================================================
> *** testsuite/g++.dg/torture/20070621-1.C	(revision 195032)
> --- testsuite/g++.dg/torture/20070621-1.C	(working copy)
> ***************
> *** 1,3 ****
> --- 1,4 ----
> + // { dg-do compile }
>   /* Reduced from libstdc++-v3/testsuite/25_algorithms/equal/1.cc
>   
>   1.2.ii: In function 'void test1()':
> Index: testsuite/g++.dg/torture/pr55875.C
> ===================================================================
> *** testsuite/g++.dg/torture/pr55875.C	(revision 0)
> --- testsuite/g++.dg/torture/pr55875.C	(revision 0)
> ***************
> *** 0 ****
> --- 1,55 ----
> + // { dg-do run }
> + 
> + 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;
> + }
> + 
> 
>

> 
> Ugh.  Both to stmt_dominates_stmt_p and to this (both use loops).
> For stmt_dominates_stmt_p you'd simply use GIMPLE uids as other
> passes do (and compute them, of course), for the above you'd
> alongside of the UID store a sequence number that increments
> at each stmt with side-effect.  UID is 32bits, so you could
> even store (stmt-number-in-bb << 8) | side-effect-nr in UID
> (with the issue that if there are exactly 256 side-effect stmts
> inbetween the two stmts you'd miss that fact ...).
> 
> Well.  At least those loops are a real issue IMHO.  Adding a
> second doesn't make complexity worse I understand - still ...
> I expected better from you ;)
> 
> Patch is ok, but think about this for a minute - eventually
> you can come up with sth very clever.

As I wrote in the comment above, I think it is best to precompute
the bounds in number of iterations in basic blocks by same
algorithm as discover_iteration_bound_by_body_walk.
We will then have O(nstmts+nbounds) algorithm.
The challenge is where to attach the data and how to keep it up to date.

The non-wrappingness is tested on random uses of SCEV across the compiler when
the loop body can be somewhat modified already (so thus also UIDs will run out
of sync). Moreover the non-wrappingness is used by niter logic itself when
bounds are being inserted (giving conservatively wrong answers)
So I think it is more of 4.9 material.

I would expect us to be actually slightly faster than before the patch,
because we skip the bound walk when iterations already give the info.

With constant time gsi_for_stmt the loop in stmt_dominates_stmt_p can probably
be changed to start walk on one statement and look for the second.

Honza