Fix array bound niter estimate (PR middle-end/54937)

Fix array bound niter estimate (PR middle-end/54937)

[Jan Hubicka]

Hi,
this patch fixes off-by-one error in the testcase attached.  The problem is that
dominance based test used by record_estimate to check whether the given statement
must be executed at last iteration of the loop is wrong ignoring the side effect
of other statements that may terminate the program.
It also does not work for mulitple exits as excercised by cunroll-2.c testcase.

This patch makes simple approach of computing set of all statements that must
by executed last iteration first time record_estimate is executed this way.
The set is computed conservatively walking header BB and its signle successors
(possibly diving into nested loop) stopping on first BB with multiple exits.

Better result can be computed by
1) estimating what loops are known to be finite
2) inserting fake edges for all infinite loop and all statements with side effect
   that may terminate the execution
3) using the post dominance info.
But that seems too expensive for something that is executed several times per
function compilation. In fact I am thinking about making recrod-estimate to happen
at ivcanon time only and then making the loop_max_iterations and loop_estimated_iterations
to simply return the bound instead of trying to recompute it all the time.

Still I do not see us to care about very precise bound for loops having complex
control flow since we do not really want to completely unroll them and elsewhere
the off-by-one error in conservative direction for iteration estimate is not big
deal.

Bootstrapped/regtested x86_64-linux, seems sane?

Honza

	PR middle-end/54937
	* tree-ssa-loop-niter.c (compute_stmts_executed_last_iteration): New
	function.
	(record_estimate): Use it; remove confused dominance test.
	(estimate_numbers_of_iterations_loop): Free stmts_executed_last_iteration.
	* gcc.c-torture/execute/pr54937.c: Ne wtestcase.
	* testsuite/gcc.dg/tree-ssa/cunroll-2.c: Tighten.
Index: tree-ssa-loop-niter.c
===================================================================
*** tree-ssa-loop-niter.c	(revision 192537)
--- tree-ssa-loop-niter.c	(working copy)
*************** record_niter_bound (struct loop *loop, d
*** 2523,2528 ****
--- 2523,2580 ----
      loop->nb_iterations_estimate = loop->nb_iterations_upper_bound;
  }
  
+ /* Compute pointer set of statements in currently analyzed loop that are known
+    to be executed at last iteration and store it into AUX.  
+    We do very simple job of recording statements in the superblock
+    starsting in loop header until reaching first statement with side effect.
+ 
+    We can compute post-dominance after inserting fake edges to CFG
+    for all statements possibly terminating CFG and for all possibly
+    infinite subloops, but we really care about precise estimates
+    of simple loops with little control flow in it.  */
+ static void
+ compute_stmts_executed_last_iteration (struct loop *loop)
+ {
+   basic_block bb = loop->header;
+   pointer_set_t *visited = NULL;
+   gimple_stmt_iterator gsi;
+   pointer_set_t *stmts_executed_last_iteration;
+ 
+   loop->aux = stmts_executed_last_iteration = pointer_set_create ();
+   while (true)
+     {
+       for (gsi = gsi_start_bb (loop->header); !gsi_end_p (gsi); gsi_next (&gsi))
+ 	{
+ 	  if (gimple_has_side_effects (gsi_stmt (gsi)))
+ 	    {
+ 	      if (visited)
+ 	        pointer_set_destroy (visited);
+ 	      return;
+ 	    }
+ 	  pointer_set_insert (stmts_executed_last_iteration, gsi_stmt (gsi));
+ 	}
+       if (single_succ_p (bb))
+ 	{
+ 	  /* Deal with the rare case that there is an infintie loop inside the
+ 	     loop examined.  */
+ 	  if (!visited)
+ 	    {
+               visited = pointer_set_create ();
+               pointer_set_insert (visited, bb);
+ 	    }
+ 	  bb = single_succ_edge (bb)->dest;
+           if (pointer_set_insert (visited, bb))
+ 	    break;
+ 	}
+       else
+ 	break;
+     }
+   if (visited)
+     pointer_set_destroy (visited);
+   return;
+ }
+ 
+ 
  /* Records that AT_STMT is executed at most BOUND + 1 times in LOOP.  IS_EXIT
     is true if the loop is exited immediately after STMT, and this exit
     is taken at last when the STMT is executed BOUND + 1 times.
*************** record_estimate (struct loop *loop, tree
*** 2535,2541 ****
  		 gimple at_stmt, bool is_exit, bool realistic, bool upper)
  {
    double_int delta;
-   edge exit;
  
    if (dump_file && (dump_flags & TDF_DETAILS))
      {
--- 2587,2592 ----
*************** record_estimate (struct loop *loop, tree
*** 2573,2586 ****
       If at_stmt is an exit or dominates the single exit from the loop,
       then the loop latch is executed at most BOUND times, otherwise
       it can be executed BOUND + 1 times.  */
!   exit = single_exit (loop);
!   if (is_exit
!       || (exit != NULL
! 	  && dominated_by_p (CDI_DOMINATORS,
! 			     exit->src, gimple_bb (at_stmt))))
      delta = double_int_zero;
    else
!     delta = double_int_one;
    i_bound += delta;
  
    /* If an overflow occurred, ignore the result.  */
--- 2624,2641 ----
       If at_stmt is an exit or dominates the single exit from the loop,
       then the loop latch is executed at most BOUND times, otherwise
       it can be executed BOUND + 1 times.  */
!   if (is_exit)
      delta = double_int_zero;
    else
!     {
!       if (!loop->aux)
! 	compute_stmts_executed_last_iteration (loop);
!       if (pointer_set_contains ((pointer_set_t *)loop->aux,
! 				at_stmt))
!         delta = double_int_zero;
!       else
!         delta = double_int_one;
!     }
    i_bound += delta;
  
    /* If an overflow occurred, ignore the result.  */
*************** estimate_numbers_of_iterations_loop (str
*** 2971,2976 ****
--- 3026,3033 ----
    if (loop->estimate_state != EST_NOT_COMPUTED)
      return;
  
+   gcc_assert (!loop->aux);
+ 
    loop->estimate_state = EST_AVAILABLE;
    /* Force estimate compuation but leave any existing upper bound in place.  */
    loop->any_estimate = false;
*************** estimate_numbers_of_iterations_loop (str
*** 3004,3009 ****
--- 3061,3071 ----
        bound = gcov_type_to_double_int (nit);
        record_niter_bound (loop, bound, true, false);
      }
+   if (loop->aux)
+     {
+       pointer_set_destroy ((pointer_set_t *)loop->aux);
+       loop->aux = NULL;
+     }
  }
  
  /* Sets NIT to the estimated number of executions of the latch of the
Index: testsuite/gcc.c-torture/execute/pr54937.c
===================================================================
--- testsuite/gcc.c-torture/execute/pr54937.c	(revision 0)
+++ testsuite/gcc.c-torture/execute/pr54937.c	(revision 0)
@@ -0,0 +1,22 @@
+
+void exit (int);
+void abort (void);
+int a[1];
+void (*terminate_me)(int);
+
+__attribute__((noinline,noclone))
+t(int c)
+{ int i;
+  for (i=0;i<c;i++)
+    {
+      if (i)
+       terminate_me(0);
+      a[i]=0;
+    }
+}
+main()
+{
+  terminate_me = exit;
+  t(100);
+  abort();
+}
Index: testsuite/gcc.dg/tree-ssa/cunroll-2.c
===================================================================
--- testsuite/gcc.dg/tree-ssa/cunroll-2.c	(revision 192608)
+++ testsuite/gcc.dg/tree-ssa/cunroll-2.c	(working copy)
@@ -12,5 +12,5 @@ test(int c)
     }
 }
 /* We are not able to get rid of the final conditional because the loop has two exits.  */
-/* { dg-final { scan-tree-dump "Unrolled loop 1 completely .duplicated 2 times.." "cunroll"} } */
+/* { dg-final { scan-tree-dump "Unrolled loop 1 completely .duplicated 1 times.." "cunroll"} } */
 /* { dg-final { cleanup-tree-dump "cunroll" } } */

Re: Fix array bound niter estimate (PR middle-end/54937)

[Richard Biener]

On Fri, 19 Oct 2012, Jan Hubicka wrote:

> Hi,
> this patch fixes off-by-one error in the testcase attached.  The problem is that
> dominance based test used by record_estimate to check whether the given statement
> must be executed at last iteration of the loop is wrong ignoring the side effect
> of other statements that may terminate the program.
> It also does not work for mulitple exits as excercised by cunroll-2.c testcase.
> 
> This patch makes simple approach of computing set of all statements that must
> by executed last iteration first time record_estimate is executed this way.
> The set is computed conservatively walking header BB and its signle successors
> (possibly diving into nested loop) stopping on first BB with multiple exits.
> 
> Better result can be computed by
> 1) estimating what loops are known to be finite
> 2) inserting fake edges for all infinite loop and all statements with side effect
>    that may terminate the execution
> 3) using the post dominance info.

would using post-dom info even work?  That only says that _if_ the
dominated stmt executed then it came through the dominator.  It
doesn't deal with functions that may not return.

> But that seems too expensive for something that is executed several times per
> function compilation. In fact I am thinking about making recrod-estimate to happen
> at ivcanon time only and then making the loop_max_iterations and loop_estimated_iterations
> to simply return the bound instead of trying to recompute it all the time.
> 
> Still I do not see us to care about very precise bound for loops having complex
> control flow since we do not really want to completely unroll them and elsewhere
> the off-by-one error in conservative direction for iteration estimate is not big
> deal.
> 
> Bootstrapped/regtested x86_64-linux, seems sane?
> 
> Honza
> 
> 	PR middle-end/54937
> 	* tree-ssa-loop-niter.c (compute_stmts_executed_last_iteration): New
> 	function.
> 	(record_estimate): Use it; remove confused dominance test.
> 	(estimate_numbers_of_iterations_loop): Free stmts_executed_last_iteration.
> 	* gcc.c-torture/execute/pr54937.c: Ne wtestcase.
> 	* testsuite/gcc.dg/tree-ssa/cunroll-2.c: Tighten.
> Index: tree-ssa-loop-niter.c
> ===================================================================
> *** tree-ssa-loop-niter.c	(revision 192537)
> --- tree-ssa-loop-niter.c	(working copy)
> *************** record_niter_bound (struct loop *loop, d
> *** 2523,2528 ****
> --- 2523,2580 ----
>       loop->nb_iterations_estimate = loop->nb_iterations_upper_bound;
>   }
>   
> + /* Compute pointer set of statements in currently analyzed loop that are known
> +    to be executed at last iteration and store it into AUX.  
> +    We do very simple job of recording statements in the superblock
> +    starsting in loop header until reaching first statement with side effect.
> + 
> +    We can compute post-dominance after inserting fake edges to CFG
> +    for all statements possibly terminating CFG and for all possibly
> +    infinite subloops, but we really care about precise estimates
> +    of simple loops with little control flow in it.  */
> + static void
> + compute_stmts_executed_last_iteration (struct loop *loop)
> + {
> +   basic_block bb = loop->header;
> +   pointer_set_t *visited = NULL;
> +   gimple_stmt_iterator gsi;
> +   pointer_set_t *stmts_executed_last_iteration;
> + 
> +   loop->aux = stmts_executed_last_iteration = pointer_set_create ();
> +   while (true)
> +     {
> +       for (gsi = gsi_start_bb (loop->header); !gsi_end_p (gsi); gsi_next (&gsi))
> + 	{
> + 	  if (gimple_has_side_effects (gsi_stmt (gsi)))
> + 	    {
> + 	      if (visited)
> + 	        pointer_set_destroy (visited);
> + 	      return;
> + 	    }
> + 	  pointer_set_insert (stmts_executed_last_iteration, gsi_stmt (gsi));
> + 	}
> +       if (single_succ_p (bb))
> + 	{
> + 	  /* Deal with the rare case that there is an infintie loop inside the
> + 	     loop examined.  */
> + 	  if (!visited)
> + 	    {
> +               visited = pointer_set_create ();
> +               pointer_set_insert (visited, bb);
> + 	    }
> + 	  bb = single_succ_edge (bb)->dest;
> +           if (pointer_set_insert (visited, bb))
> + 	    break;
> + 	}
> +       else
> + 	break;
> +     }
> +   if (visited)
> +     pointer_set_destroy (visited);
> +   return;
> + }
> + 
> + 
>   /* Records that AT_STMT is executed at most BOUND + 1 times in LOOP.  IS_EXIT
>      is true if the loop is exited immediately after STMT, and this exit
>      is taken at last when the STMT is executed BOUND + 1 times.
> *************** record_estimate (struct loop *loop, tree
> *** 2535,2541 ****
>   		 gimple at_stmt, bool is_exit, bool realistic, bool upper)
>   {
>     double_int delta;
> -   edge exit;
>   
>     if (dump_file && (dump_flags & TDF_DETAILS))
>       {
> --- 2587,2592 ----
> *************** record_estimate (struct loop *loop, tree
> *** 2573,2586 ****
>        If at_stmt is an exit or dominates the single exit from the loop,
>        then the loop latch is executed at most BOUND times, otherwise
>        it can be executed BOUND + 1 times.  */
> !   exit = single_exit (loop);
> !   if (is_exit
> !       || (exit != NULL
> ! 	  && dominated_by_p (CDI_DOMINATORS,
> ! 			     exit->src, gimple_bb (at_stmt))))
>       delta = double_int_zero;
>     else
> !     delta = double_int_one;
>     i_bound += delta;
>   
>     /* If an overflow occurred, ignore the result.  */
> --- 2624,2641 ----
>        If at_stmt is an exit or dominates the single exit from the loop,
>        then the loop latch is executed at most BOUND times, otherwise
>        it can be executed BOUND + 1 times.  */
> !   if (is_exit)
>       delta = double_int_zero;
>     else
> !     {
> !       if (!loop->aux)
> ! 	compute_stmts_executed_last_iteration (loop);
> !       if (pointer_set_contains ((pointer_set_t *)loop->aux,
> ! 				at_stmt))
> !         delta = double_int_zero;
> !       else
> !         delta = double_int_one;
> !     }

What about the conservative variant of simply

      else
        delta = double_int_one;

?  I don't like all the code you add, nor the use of ->aux.

>     i_bound += delta;

Another alternative would be to not use i_bound for the
strong upper bound but only the estimate (thus conservatively
use i_bound + 1 for the upper bound if !is_exit).

Richard.

>     /* If an overflow occurred, ignore the result.  */
> *************** estimate_numbers_of_iterations_loop (str
> *** 2971,2976 ****
> --- 3026,3033 ----
>     if (loop->estimate_state != EST_NOT_COMPUTED)
>       return;
>   
> +   gcc_assert (!loop->aux);
> + 
>     loop->estimate_state = EST_AVAILABLE;
>     /* Force estimate compuation but leave any existing upper bound in place.  */
>     loop->any_estimate = false;
> *************** estimate_numbers_of_iterations_loop (str
> *** 3004,3009 ****
> --- 3061,3071 ----
>         bound = gcov_type_to_double_int (nit);
>         record_niter_bound (loop, bound, true, false);
>       }
> +   if (loop->aux)
> +     {
> +       pointer_set_destroy ((pointer_set_t *)loop->aux);
> +       loop->aux = NULL;
> +     }
>   }
>   
>   /* Sets NIT to the estimated number of executions of the latch of the
> Index: testsuite/gcc.c-torture/execute/pr54937.c
> ===================================================================
> --- testsuite/gcc.c-torture/execute/pr54937.c	(revision 0)
> +++ testsuite/gcc.c-torture/execute/pr54937.c	(revision 0)
> @@ -0,0 +1,22 @@
> +
> +void exit (int);
> +void abort (void);
> +int a[1];
> +void (*terminate_me)(int);
> +
> +__attribute__((noinline,noclone))
> +t(int c)
> +{ int i;
> +  for (i=0;i<c;i++)
> +    {
> +      if (i)
> +       terminate_me(0);
> +      a[i]=0;
> +    }
> +}
> +main()
> +{
> +  terminate_me = exit;
> +  t(100);
> +  abort();
> +}
> Index: testsuite/gcc.dg/tree-ssa/cunroll-2.c
> ===================================================================
> --- testsuite/gcc.dg/tree-ssa/cunroll-2.c	(revision 192608)
> +++ testsuite/gcc.dg/tree-ssa/cunroll-2.c	(working copy)
> @@ -12,5 +12,5 @@ test(int c)
>      }
>  }
>  /* We are not able to get rid of the final conditional because the loop has two exits.  */
> -/* { dg-final { scan-tree-dump "Unrolled loop 1 completely .duplicated 2 times.." "cunroll"} } */
> +/* { dg-final { scan-tree-dump "Unrolled loop 1 completely .duplicated 1 times.." "cunroll"} } */
>  /* { dg-final { cleanup-tree-dump "cunroll" } } */
> 
> 

-- 
Richard Biener <rguenther@suse.de>
SUSE / SUSE Labs
SUSE LINUX Products GmbH - Nuernberg - AG Nuernberg - HRB 16746
GF: Jeff Hawn, Jennifer Guild, Felix Imend

Re: Fix array bound niter estimate (PR middle-end/54937)

[Jan Hubicka]

> On Fri, 19 Oct 2012, Jan Hubicka wrote:
> 
> > Hi,
> > this patch fixes off-by-one error in the testcase attached.  The problem is that
> > dominance based test used by record_estimate to check whether the given statement
> > must be executed at last iteration of the loop is wrong ignoring the side effect
> > of other statements that may terminate the program.
> > It also does not work for mulitple exits as excercised by cunroll-2.c testcase.
> > 
> > This patch makes simple approach of computing set of all statements that must
> > by executed last iteration first time record_estimate is executed this way.
> > The set is computed conservatively walking header BB and its signle successors
> > (possibly diving into nested loop) stopping on first BB with multiple exits.
> > 
> > Better result can be computed by
> > 1) estimating what loops are known to be finite
> > 2) inserting fake edges for all infinite loop and all statements with side effect
> >    that may terminate the execution
> > 3) using the post dominance info.
> 
> would using post-dom info even work?  That only says that _if_ the
> dominated stmt executed then it came through the dominator.  It
> doesn't deal with functions that may not return.

With fake edges inserted it will. We do have code for that used in profiling that
also needs this stronger definition of CFG.
> 
> What about the conservative variant of simply
> 
>       else
>         delta = double_int_one;

I think it would be bad idea: it makes us to completely unroll one interation
too many that bloats code for no benefit. No optimization cancels the path in
CFG because of undefined effect and thus the code will be output (unless someone
smarter, like VRP, cleans up later, but it is more an exception than rule.)
> 
> ?  I don't like all the code you add, nor the use of ->aux.

Neither I really do, but what are the alternatives?

My first implementation simply checked that stmt is in the loop header and
walked up to the beggining of basic blocks looking for side effects.  Then I
become worried about possibility of gigantic basic blocks with many array
stores within the loop, so I decided to record the reachable statements instead
of repeating the walk.
Loop count estimation is recursive (i.e. it dives into inner loops), thus I
ended up with using AUX.  I can for sure put this separately or add extra
reference argument passed over the whole call stack, but there are quite many
functions that can leads to record_estimate. (I have nothing against that
alternative however if AUX looks ugly)
> 
> >     i_bound += delta;
> 
> Another alternative would be to not use i_bound for the
> strong upper bound but only the estimate (thus conservatively
> use i_bound + 1 for the upper bound if !is_exit).

We can not derrive realistic estimate based on this: the loop may exit much earlier.
We can only lower the estimate if it is already there and greater than this bound.
This can probably happen with profile feedback and I can implement it later,
I do not think it is terribly important though.

Honza

Re: Fix array bound niter estimate (PR middle-end/54937)

[Jan Hubicka]

> > What about the conservative variant of simply
> > 
> >       else
> >         delta = double_int_one;
> 
> I think it would be bad idea: it makes us to completely unroll one interation
> too many that bloats code for no benefit. No optimization cancels the path in
> CFG because of undefined effect and thus the code will be output (unless someone
> smarter, like VRP, cleans up later, but it is more an exception than rule.)

OK, on deper tought I guess I can add double_int_one always at that spot and
once we are done with everything I can walk nb_iter_bound for all statements
known to not be executed on last iteration and record them to pointer set.

Finally I can walk from header in DFS stopping on loop exits, side effects and
those stateemnts.  If I visit no loop exit or side effect I know I can lower
iteration count by 1 (in estimate_numbers_of_iterations_loop).

This will give accurate answer and requires just little extra bookkeeping.

I will give this a try.
Honza

Re: Fix array bound niter estimate (PR middle-end/54937)

[Jan Hubicka]

> > > What about the conservative variant of simply
> > > 
> > >       else
> > >         delta = double_int_one;
> > 
> > I think it would be bad idea: it makes us to completely unroll one interation
> > too many that bloats code for no benefit. No optimization cancels the path in
> > CFG because of undefined effect and thus the code will be output (unless someone
> > smarter, like VRP, cleans up later, but it is more an exception than rule.)
> 
> OK, on deper tought I guess I can add double_int_one always at that spot and
> once we are done with everything I can walk nb_iter_bound for all statements
> known to not be executed on last iteration and record them to pointer set.
> 
> Finally I can walk from header in DFS stopping on loop exits, side effects and
> those stateemnts.  If I visit no loop exit or side effect I know I can lower
> iteration count by 1 (in estimate_numbers_of_iterations_loop).
> 
> This will give accurate answer and requires just little extra bookkeeping.
> 
> I will give this a try.

Here is updated patch.  It solves the testcase and gives better estimates than before.

Here is obvious improvements: record_estimate can put all statements to the list not only
those that dominates loop latch and maybe_lower_iteration_bound can track lowest estimate
it finds on its walk.  This will need bit more work and I am thus sending the bugfix
separately, because I think it should go to 4.7, too.

Honza

	* tree-ssa-loop-niter.c (record_estimate): Remove confused
	dominators check.
	(maybe_lower_iteration_bound): New function.
	(estimate_numbers_of_iterations_loop): Use it.
Index: tree-ssa-loop-niter.c
===================================================================
--- tree-ssa-loop-niter.c	(revision 192537)
+++ tree-ssa-loop-niter.c	(working copy)
@@ -2535,7 +2541,6 @@ record_estimate (struct loop *loop, tree
 		 gimple at_stmt, bool is_exit, bool realistic, bool upper)
 {
   double_int delta;
-  edge exit;
 
   if (dump_file && (dump_flags & TDF_DETAILS))
     {
@@ -2570,14 +2577,10 @@ record_estimate (struct loop *loop, tree
     }
 
   /* Update the number of iteration estimates according to the bound.
-     If at_stmt is an exit or dominates the single exit from the loop,
-     then the loop latch is executed at most BOUND times, otherwise
-     it can be executed BOUND + 1 times.  */
-  exit = single_exit (loop);
-  if (is_exit
-      || (exit != NULL
-	  && dominated_by_p (CDI_DOMINATORS,
-			     exit->src, gimple_bb (at_stmt))))
+     If at_stmt is an exit then the loop latch is executed at most BOUND times,
+     otherwise it can be executed BOUND + 1 times.  We will lower the estimate
+     later if such statement must be executed on last iteration  */
+  if (is_exit)
     delta = double_int_zero;
   else
     delta = double_int_one;
@@ -2953,6 +2956,87 @@ gcov_type_to_double_int (gcov_type val)
   return ret;
 }
 
+/* See if every path cross the loop goes through a statement that is known
+   to not execute at the last iteration. In that case we can decrese iteration
+   count by 1.  */
+
+static void
+maybe_lower_iteration_bound (struct loop *loop)
+{
+  pointer_set_t *not_executed_last_iteration = pointer_set_create ();
+  pointer_set_t *visited;
+  struct nb_iter_bound *elt;
+  bool found = false;
+  VEC (basic_block, heap) *queue = NULL;
+
+  for (elt = loop->bounds; elt; elt = elt->next)
+    {
+      if (!elt->is_exit
+	  && elt->bound.ult (loop->nb_iterations_upper_bound))
+	{
+	  found = true;
+	  pointer_set_insert (not_executed_last_iteration, elt->stmt);
+	}
+    }
+  if (!found)
+    {
+      pointer_set_destroy (not_executed_last_iteration);
+      return;
+    }
+  visited = pointer_set_create ();
+  VEC_safe_push (basic_block, heap, queue, loop->header);
+  pointer_set_insert (visited, loop->header);
+  found = false;
+
+  while (VEC_length (basic_block, queue) && !found)
+    {
+      basic_block bb = VEC_pop (basic_block, queue);
+      gimple_stmt_iterator gsi;
+      bool stmt_found = false;
+
+      for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
+	{
+	  gimple stmt = gsi_stmt (gsi);
+	  if (pointer_set_contains (not_executed_last_iteration, stmt))
+	    {
+	      stmt_found = true;
+	      break;
+	    }
+	  if (gimple_has_side_effects (stmt))
+	    {
+	      found = true;
+	      break;
+	    }
+	}
+      if (!stmt_found && !found)
+	{
+          edge e;
+          edge_iterator ei;
+
+          FOR_EACH_EDGE (e, ei, bb->succs)
+	    {
+	      if (loop_exit_edge_p (loop, e))
+		{
+		  found = true;
+		  break;
+		}
+	      if (!pointer_set_insert (visited, e->dest))
+		VEC_safe_push (basic_block, heap, queue, e->dest);
+	    }
+	}
+    }
+  if (!found)
+    {
+      if (dump_file && (dump_flags & TDF_DETAILS))
+	fprintf (dump_file, "Reducing loop iteration estimate by 1; "
+		 "undefined statement must be executed at last iteration.");
+      record_niter_bound (loop, loop->nb_iterations_upper_bound - double_int_one,
+			  false, true);
+    }
+  pointer_set_destroy (visited);
+  VEC_free (basic_block, heap, queue);
+}
+
 /* Records estimates on numbers of iterations of LOOP.  If USE_UNDEFINED_P
    is true also use estimates derived from undefined behavior.  */
 
@@ -2996,6 +3080,9 @@ estimate_numbers_of_iterations_loop (str
 
   infer_loop_bounds_from_undefined (loop);
 
+  if (loop->any_upper_bound)
+    maybe_lower_iteration_bound (loop);
+
   /* If we have a measured profile, use it to estimate the number of
      iterations.  */
   if (loop->header->count != 0)

Re: Fix array bound niter estimate (PR middle-end/54937)

[Jan Hubicka]

> > > > What about the conservative variant of simply
> > > > 
> > > >       else
> > > >         delta = double_int_one;
> > > 
> > > I think it would be bad idea: it makes us to completely unroll one interation
> > > too many that bloats code for no benefit. No optimization cancels the path in
> > > CFG because of undefined effect and thus the code will be output (unless someone
> > > smarter, like VRP, cleans up later, but it is more an exception than rule.)
> > 
> > OK, on deper tought I guess I can add double_int_one always at that spot and
> > once we are done with everything I can walk nb_iter_bound for all statements
> > known to not be executed on last iteration and record them to pointer set.
> > 
> > Finally I can walk from header in DFS stopping on loop exits, side effects and
> > those stateemnts.  If I visit no loop exit or side effect I know I can lower
> > iteration count by 1 (in estimate_numbers_of_iterations_loop).
> > 
> > This will give accurate answer and requires just little extra bookkeeping.
> > 
> > I will give this a try.
> 
> Here is updated patch.  It solves the testcase and gives better estimates than before.
> 
> Here is obvious improvements: record_estimate can put all statements to the list not only
> those that dominates loop latch and maybe_lower_iteration_bound can track lowest estimate
> it finds on its walk.  This will need bit more work and I am thus sending the bugfix
> separately, because I think it should go to 4.7, too.

This patch fixes a trivial bug that solves one regression in fortran testsuite.  There are
two left:
gfortran.dg/bounds_check_9.f90 and gfortran.dg/bounds_check_fail_2.f90

I am quite convinced the code makes correct decision here and I put request to the original
PR http://gcc.gnu.org/bugzilla/show_bug.cgi?id=31119

We was overly conservative here just because we did not handle multipl exit
loops, so the testcase passed by accident rather than by decision.  Perhaps
this is actually bug in -fbounds-check implementation?

Honza
> 
> Honza
> 
> 	* tree-ssa-loop-niter.c (record_estimate): Remove confused
> 	dominators check.
> 	(maybe_lower_iteration_bound): New function.
> 	(estimate_numbers_of_iterations_loop): Use it.

Index: tree-ssa-loop-niter.c
===================================================================
--- tree-ssa-loop-niter.c	(revision 192632)
+++ tree-ssa-loop-niter.c	(working copy)
@@ -2535,7 +2541,6 @@ record_estimate (struct loop *loop, tree
 		 gimple at_stmt, bool is_exit, bool realistic, bool upper)
 {
   double_int delta;
-  edge exit;
 
   if (dump_file && (dump_flags & TDF_DETAILS))
     {
@@ -2570,14 +2577,10 @@ record_estimate (struct loop *loop, tree
     }
 
   /* Update the number of iteration estimates according to the bound.
-     If at_stmt is an exit or dominates the single exit from the loop,
-     then the loop latch is executed at most BOUND times, otherwise
-     it can be executed BOUND + 1 times.  */
-  exit = single_exit (loop);
-  if (is_exit
-      || (exit != NULL
-	  && dominated_by_p (CDI_DOMINATORS,
-			     exit->src, gimple_bb (at_stmt))))
+     If at_stmt is an exit then the loop latch is executed at most BOUND times,
+     otherwise it can be executed BOUND + 1 times.  We will lower the estimate
+     later if such statement must be executed on last iteration  */
+  if (is_exit)
     delta = double_int_zero;
   else
     delta = double_int_one;
@@ -2953,6 +2956,88 @@ gcov_type_to_double_int (gcov_type val)
   return ret;
 }
 
+/* See if every path cross the loop goes through a statement that is known
+   to not execute at the last iteration. In that case we can decrese iteration
+   count by 1.  */
+
+static void
+maybe_lower_iteration_bound (struct loop *loop)
+{
+  pointer_set_t *not_executed_last_iteration = pointer_set_create ();
+  pointer_set_t *visited;
+  struct nb_iter_bound *elt;
+  bool found = false;
+  VEC (basic_block, heap) *queue = NULL;
+
+  for (elt = loop->bounds; elt; elt = elt->next)
+    {
+      if (!elt->is_exit
+	  && elt->bound.ult (loop->nb_iterations_upper_bound))
+	{
+	  found = true;
+	  pointer_set_insert (not_executed_last_iteration, elt->stmt);
+	}
+    }
+  if (!found)
+    {
+      pointer_set_destroy (not_executed_last_iteration);
+      return;
+    }
+  visited = pointer_set_create ();
+  VEC_safe_push (basic_block, heap, queue, loop->header);
+  pointer_set_insert (visited, loop->header);
+  found = false;
+
+  while (VEC_length (basic_block, queue) && !found)
+    {
+      basic_block bb = VEC_pop (basic_block, queue);
+      gimple_stmt_iterator gsi;
+      bool stmt_found = false;
+
+      for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
+	{
+	  gimple stmt = gsi_stmt (gsi);
+	  if (pointer_set_contains (not_executed_last_iteration, stmt))
+	    {
+	      stmt_found = true;
+	      break;
+	    }
+	  if (gimple_has_side_effects (stmt))
+	    {
+	      found = true;
+	      break;
+	    }
+	}
+      if (!stmt_found && !found)
+	{
+          edge e;
+          edge_iterator ei;
+
+          FOR_EACH_EDGE (e, ei, bb->succs)
+	    {
+	      if (loop_exit_edge_p (loop, e)
+		  || e == loop_latch_edge (loop))
+		{
+		  found = true;
+		  break;
+		}
+	      if (!pointer_set_insert (visited, e->dest))
+		VEC_safe_push (basic_block, heap, queue, e->dest);
+	    }
+	}
+    }
+  if (!found)
+    {
+      if (dump_file && (dump_flags & TDF_DETAILS))
+	fprintf (dump_file, "Reducing loop iteration estimate by 1; "
+		 "undefined statement must be executed at the last iteration.\n");
+      record_niter_bound (loop, loop->nb_iterations_upper_bound - double_int_one,
+			  false, true);
+    }
+  pointer_set_destroy (visited);
+  VEC_free (basic_block, heap, queue);
+}
+
 /* Records estimates on numbers of iterations of LOOP.  If USE_UNDEFINED_P
    is true also use estimates derived from undefined behavior.  */
 
@@ -2996,6 +3081,8 @@ estimate_numbers_of_iterations_loop (str
 
   infer_loop_bounds_from_undefined (loop);
 
+  maybe_lower_iteration_bound (loop);
+
   /* If we have a measured profile, use it to estimate the number of
      iterations.  */
   if (loop->header->count != 0)

Re: Fix array bound niter estimate (PR middle-end/54937)

[Richard Biener]

On Fri, 19 Oct 2012, Jan Hubicka wrote:

> > > > What about the conservative variant of simply
> > > > 
> > > >       else
> > > >         delta = double_int_one;
> > > 
> > > I think it would be bad idea: it makes us to completely unroll one interation
> > > too many that bloats code for no benefit. No optimization cancels the path in
> > > CFG because of undefined effect and thus the code will be output (unless someone
> > > smarter, like VRP, cleans up later, but it is more an exception than rule.)
> > 
> > OK, on deper tought I guess I can add double_int_one always at that spot and
> > once we are done with everything I can walk nb_iter_bound for all statements
> > known to not be executed on last iteration and record them to pointer set.
> > 
> > Finally I can walk from header in DFS stopping on loop exits, side effects and
> > those stateemnts.  If I visit no loop exit or side effect I know I can lower
> > iteration count by 1 (in estimate_numbers_of_iterations_loop).
> > 
> > This will give accurate answer and requires just little extra bookkeeping.
> > 
> > I will give this a try.
> 
> Here is updated patch.  It solves the testcase and gives better estimates than before.
> 
> Here is obvious improvements: record_estimate can put all statements to the list not only
> those that dominates loop latch and maybe_lower_iteration_bound can track lowest estimate
> it finds on its walk.  This will need bit more work and I am thus sending the bugfix
> separately, because I think it should go to 4.7, too.
> 
> Honza
> 
> 	* tree-ssa-loop-niter.c (record_estimate): Remove confused
> 	dominators check.
> 	(maybe_lower_iteration_bound): New function.
> 	(estimate_numbers_of_iterations_loop): Use it.
> Index: tree-ssa-loop-niter.c
> ===================================================================
> --- tree-ssa-loop-niter.c	(revision 192537)
> +++ tree-ssa-loop-niter.c	(working copy)
> @@ -2535,7 +2541,6 @@ record_estimate (struct loop *loop, tree
>  		 gimple at_stmt, bool is_exit, bool realistic, bool upper)
>  {
>    double_int delta;
> -  edge exit;
>  
>    if (dump_file && (dump_flags & TDF_DETAILS))
>      {
> @@ -2570,14 +2577,10 @@ record_estimate (struct loop *loop, tree
>      }
>  
>    /* Update the number of iteration estimates according to the bound.
> -     If at_stmt is an exit or dominates the single exit from the loop,
> -     then the loop latch is executed at most BOUND times, otherwise
> -     it can be executed BOUND + 1 times.  */
> -  exit = single_exit (loop);
> -  if (is_exit
> -      || (exit != NULL
> -	  && dominated_by_p (CDI_DOMINATORS,
> -			     exit->src, gimple_bb (at_stmt))))
> +     If at_stmt is an exit then the loop latch is executed at most BOUND times,
> +     otherwise it can be executed BOUND + 1 times.  We will lower the estimate
> +     later if such statement must be executed on last iteration  */
> +  if (is_exit)
>      delta = double_int_zero;
>    else
>      delta = double_int_one;
> @@ -2953,6 +2956,87 @@ gcov_type_to_double_int (gcov_type val)
>    return ret;
>  }
>  
> +/* See if every path cross the loop goes through a statement that is known
> +   to not execute at the last iteration. In that case we can decrese iteration
> +   count by 1.  */
> +
> +static void
> +maybe_lower_iteration_bound (struct loop *loop)
> +{
> +  pointer_set_t *not_executed_last_iteration = pointer_set_create ();
> +  pointer_set_t *visited;
> +  struct nb_iter_bound *elt;
> +  bool found = false;
> +  VEC (basic_block, heap) *queue = NULL;
> +
> +  for (elt = loop->bounds; elt; elt = elt->next)
> +    {
> +      if (!elt->is_exit
> +	  && elt->bound.ult (loop->nb_iterations_upper_bound))
> +	{
> +	  found = true;
> +	  pointer_set_insert (not_executed_last_iteration, elt->stmt);
> +	}
> +    }

So you are looking for all stmts a bound was derived from.

> +  if (!found)
> +    {
> +      pointer_set_destroy (not_executed_last_iteration);

create this on-demand in the above loop?

> +      return;
> +    }
> +  visited = pointer_set_create ();
> +  VEC_safe_push (basic_block, heap, queue, loop->header);
> +  pointer_set_insert (visited, loop->header);

pointer-set for BB visited?  In most other places we use a
[s]bitmap with block numbers.

> +  found = false;
> +
> +  while (VEC_length (basic_block, queue) && !found)

looks like a do-while loop should be possible with a !VEC_empty ()
guard at the end.

> +    {
> +      basic_block bb = VEC_pop (basic_block, queue);
> +      gimple_stmt_iterator gsi;
> +      bool stmt_found = false;
> +
> +      for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
> +	{
> +	  gimple stmt = gsi_stmt (gsi);
> +	  if (pointer_set_contains (not_executed_last_iteration, stmt))
> +	    {
> +	      stmt_found = true;

we found one.

> +	      break;
> +	    }
> +	  if (gimple_has_side_effects (stmt))
> +	    {
> +	      found = true;

we found sth else?

> +	      break;
> +	    }
> +	}
> +      if (!stmt_found && !found)
> +	{

if we found neither walk more blocks.

> +          edge e;
> +          edge_iterator ei;
> +
> +          FOR_EACH_EDGE (e, ei, bb->succs)
> +	    {
> +	      if (loop_exit_edge_p (loop, e))
> +		{
> +		  found = true;

we reach a (possible) exit.  maybe rename found to
found_exit?

> +		  break;
> +		}
> +	      if (!pointer_set_insert (visited, e->dest))
> +		VEC_safe_push (basic_block, heap, queue, e->dest);
> +	    }
> +	}
> +    }
> +  if (!found)

if we didn't find an exit we reduce count.  double_int_one looks magic
here, but with the assertion that each queued 'stmt_found' upper
bound was less than loop->nb_iterations_upper_bound, subtracting one
is certainly conservative.  But why not use the maximum estimate from 
all stmts_found?

Thus, please add some comments, use a bitmap for visited and
rename variables to be more descriptive.

Overall I like this version a lot more ;)

Thanks,
Richard.

> +    {
> +      if (dump_file && (dump_flags & TDF_DETAILS))
> +	fprintf (dump_file, "Reducing loop iteration estimate by 1; "
> +		 "undefined statement must be executed at last iteration.");
> +      record_niter_bound (loop, loop->nb_iterations_upper_bound - double_int_one,
> +			  false, true);
> +    }
> +  pointer_set_destroy (visited);
> +  VEC_free (basic_block, heap, queue);
> +}
> +
>  /* Records estimates on numbers of iterations of LOOP.  If USE_UNDEFINED_P
>     is true also use estimates derived from undefined behavior.  */
>  
> @@ -2996,6 +3080,9 @@ estimate_numbers_of_iterations_loop (str
>  
>    infer_loop_bounds_from_undefined (loop);
>  
> +  if (loop->any_upper_bound)
> +    maybe_lower_iteration_bound (loop);
> +
>    /* If we have a measured profile, use it to estimate the number of
>       iterations.  */
>    if (loop->header->count != 0)
> 
> 

-- 
Richard Biener <rguenther@suse.de>
SUSE / SUSE Labs
SUSE LINUX Products GmbH - Nuernberg - AG Nuernberg - HRB 16746
GF: Jeff Hawn, Jennifer Guild, Felix Imend

Re: Fix array bound niter estimate (PR middle-end/54937)

[Jan Hubicka]

> > +static void
> > +maybe_lower_iteration_bound (struct loop *loop)
> > +{
> > +  pointer_set_t *not_executed_last_iteration = pointer_set_create ();
> > +  pointer_set_t *visited;
> > +  struct nb_iter_bound *elt;
> > +  bool found = false;
> > +  VEC (basic_block, heap) *queue = NULL;
> > +
> > +  for (elt = loop->bounds; elt; elt = elt->next)
> > +    {
> > +      if (!elt->is_exit
> > +	  && elt->bound.ult (loop->nb_iterations_upper_bound))
> > +	{
> > +	  found = true;
> > +	  pointer_set_insert (not_executed_last_iteration, elt->stmt);
> > +	}
> > +    }
> 
> So you are looking for all stmts a bound was derived from.

Yes, with bound smaller than the current estimate.
> 
> > +  if (!found)
> > +    {
> > +      pointer_set_destroy (not_executed_last_iteration);
> 
> create this on-demand in the above loop?

Will do. 
> 
> > +      return;
> > +    }
> > +  visited = pointer_set_create ();
> > +  VEC_safe_push (basic_block, heap, queue, loop->header);
> > +  pointer_set_insert (visited, loop->header);
> 
> pointer-set for BB visited?  In most other places we use a
> [s]bitmap with block numbers.

Will switch to bitmap though I think it is mostly because this tradition was
invented before pointer-set. bitmap has liner walk in it, pointer-set should
scale better.
> 
> if we didn't find an exit we reduce count.  double_int_one looks magic
> here, but with the assertion that each queued 'stmt_found' upper
> bound was less than loop->nb_iterations_upper_bound, subtracting one
> is certainly conservative.  But why not use the maximum estimate from 
> all stmts_found?

Because it is always nb_iterations_upper_bound-1, see logic in record_estimate.
I plan to change this - basically we can change record_esitmate to record all
statements, not only those dominating exit and do Dijkstra's algorithm in this
walk looking for largest upper bound we can reach loopback with.

But as I wrote in the email, I would like to do this incrementally - fix the
bug first (possibly for 4.7, too - the bug is there I am not sure if it can
lead to wrong code) and change this next.  It means some further changes
thorough niter.c, but little challenge to implement Dijkstra with double-int
based queue.
> 
> Thus, please add some comments, use a bitmap for visited and
> rename variables to be more descriptive.

Will do, and need to analyze the bounds fortran failures :)

Thanks,
Honza

Re: Fix array bound niter estimate (PR middle-end/54937)

[Jan Hubicka]

Hi,
here is updated patch with the comments.  The fortran failures turned out to be
funny interaction in between this patch and my other change that hoped that
loop closed SSA is closed on VOPs, but it is not.

Regtested x86_64-linux, bootstrap in progress, OK?

Honza

	* tree-ssa-loop-niter.c (record_estimate): Do not try to lower
	the bound of non-is_exit statements.
	(maybe_lower_iteration_bound): Do it here.
	(estimate_numbers_of_iterations_loop): Call it.
	
	* gcc.c-torture/execute/pr54937.c: New testcase.
	* gcc.dg/tree-ssa/cunroll-2.c: Update.
Index: tree-ssa-loop-niter.c
===================================================================
--- tree-ssa-loop-niter.c	(revision 192632)
+++ tree-ssa-loop-niter.c	(working copy)
@@ -2535,7 +2541,6 @@ record_estimate (struct loop *loop, tree
 		 gimple at_stmt, bool is_exit, bool realistic, bool upper)
 {
   double_int delta;
-  edge exit;
 
   if (dump_file && (dump_flags & TDF_DETAILS))
     {
@@ -2570,14 +2577,10 @@ record_estimate (struct loop *loop, tree
     }
 
   /* Update the number of iteration estimates according to the bound.
-     If at_stmt is an exit or dominates the single exit from the loop,
-     then the loop latch is executed at most BOUND times, otherwise
-     it can be executed BOUND + 1 times.  */
-  exit = single_exit (loop);
-  if (is_exit
-      || (exit != NULL
-	  && dominated_by_p (CDI_DOMINATORS,
-			     exit->src, gimple_bb (at_stmt))))
+     If at_stmt is an exit then the loop latch is executed at most BOUND times,
+     otherwise it can be executed BOUND + 1 times.  We will lower the estimate
+     later if such statement must be executed on last iteration  */
+  if (is_exit)
     delta = double_int_zero;
   else
     delta = double_int_one;
@@ -2953,6 +2956,110 @@ gcov_type_to_double_int (gcov_type val)
   return ret;
 }
 
+/* See if every path cross the loop goes through a statement that is known
+   to not execute at the last iteration. In that case we can decrese iteration
+   count by 1.  */
+
+static void
+maybe_lower_iteration_bound (struct loop *loop)
+{
+  pointer_set_t *not_executed_last_iteration = pointer_set_create ();
+  struct nb_iter_bound *elt;
+  bool found_exit = false;
+  VEC (basic_block, heap) *queue = NULL;
+  bitmap visited;
+
+  /* Collect all statements with interesting (i.e. lower than
+     nb_iterations_upper_bound) bound on them. 
+
+     TODO: Due to the way record_estimate choose estimates to store, the bounds
+     will be always nb_iterations_upper_bound-1.  We can change this to record
+     also statements not dominating the loop latch and update the walk bellow
+     to the shortest path algorthm.  */
+  for (elt = loop->bounds; elt; elt = elt->next)
+    {
+      if (!elt->is_exit
+	  && elt->bound.ult (loop->nb_iterations_upper_bound))
+	{
+	  if (!not_executed_last_iteration)
+	    not_executed_last_iteration = pointer_set_create ();
+	  pointer_set_insert (not_executed_last_iteration, elt->stmt);
+	}
+    }
+  if (!not_executed_last_iteration)
+    return;
+
+  /* Start DFS walk in the loop header and see if we can reach the
+     loop latch or any of the exits (including statements with side
+     effects that may terminate the loop otherwise) without visiting
+     any of the statements known to have undefined effect on the last
+     iteration.  */
+  VEC_safe_push (basic_block, heap, queue, loop->header);
+  visited = BITMAP_ALLOC (NULL);
+  bitmap_set_bit (visited, loop->header->index);
+  found_exit = false;
+
+  do
+    {
+      basic_block bb = VEC_pop (basic_block, queue);
+      gimple_stmt_iterator gsi;
+      bool stmt_found = false;
+
+      /* Loop for possible exits and statements bounding the execution.  */
+      for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
+	{
+	  gimple stmt = gsi_stmt (gsi);
+	  if (pointer_set_contains (not_executed_last_iteration, stmt))
+	    {
+	      stmt_found = true;
+	      break;
+	    }
+	  if (gimple_has_side_effects (stmt))
+	    {
+	      found_exit = true;
+	      break;
+	    }
+	}
+      if (found_exit)
+	break;
+
+      /* If no bounding statement is found, continue the walk.  */
+      if (!stmt_found)
+	{
+          edge e;
+          edge_iterator ei;
+
+          FOR_EACH_EDGE (e, ei, bb->succs)
+	    {
+	      if (loop_exit_edge_p (loop, e)
+		  || e == loop_latch_edge (loop))
+		{
+		  found_exit = true;
+		  break;
+		}
+	      if (bitmap_set_bit (visited, e->dest->index))
+		VEC_safe_push (basic_block, heap, queue, e->dest);
+	    }
+	}
+    }
+  while (VEC_length (basic_block, queue) && !found_exit);
+
+  /* If every path through the loop reach bounding statement before exit,
+     then we know the last iteration of the loop will have undefined effect
+     and we can decrease number of iterations.  */
+    
+  if (!found_exit)
+    {
+      if (dump_file && (dump_flags & TDF_DETAILS))
+	fprintf (dump_file, "Reducing loop iteration estimate by 1; "
+		 "undefined statement must be executed at the last iteration.\n");
+      record_niter_bound (loop, loop->nb_iterations_upper_bound - double_int_one,
+			  false, true);
+    }
+  BITMAP_FREE (visited);
+  VEC_free (basic_block, heap, queue);
+}
+
 /* Records estimates on numbers of iterations of LOOP.  If USE_UNDEFINED_P
    is true also use estimates derived from undefined behavior.  */
 
@@ -2996,6 +3103,8 @@ estimate_numbers_of_iterations_loop (str
 
   infer_loop_bounds_from_undefined (loop);
 
+  maybe_lower_iteration_bound (loop);
+
   /* If we have a measured profile, use it to estimate the number of
      iterations.  */
   if (loop->header->count != 0)
Index: testsuite/gcc.c-torture/execute/pr54937.c
===================================================================
--- testsuite/gcc.c-torture/execute/pr54937.c	(revision 0)
+++ testsuite/gcc.c-torture/execute/pr54937.c	(revision 0)
@@ -0,0 +1,22 @@
+
+void exit (int);
+void abort (void);
+int a[1];
+void (*terminate_me)(int);
+
+__attribute__((noinline,noclone))
+t(int c)
+{ int i;
+  for (i=0;i<c;i++)
+    {
+      if (i)
+       terminate_me(0);
+      a[i]=0;
+    }
+}
+main()
+{
+  terminate_me = exit;
+  t(100);
+  abort();
+}
Index: testsuite/gcc.dg/tree-ssa/cunroll-2.c
===================================================================
--- testsuite/gcc.dg/tree-ssa/cunroll-2.c	(revision 192632)
+++ testsuite/gcc.dg/tree-ssa/cunroll-2.c	(working copy)
@@ -12,5 +12,5 @@ test(int c)
     }
 }
 /* We are not able to get rid of the final conditional because the loop has two exits.  */
-/* { dg-final { scan-tree-dump "Unrolled loop 1 completely .duplicated 2 times.." "cunroll"} } */
+/* { dg-final { scan-tree-dump "Unrolled loop 1 completely .duplicated 1 times.." "cunroll"} } */
 /* { dg-final { cleanup-tree-dump "cunroll" } } */

Re: Fix array bound niter estimate (PR middle-end/54937)

[Richard Biener]

On Mon, 22 Oct 2012, Jan Hubicka wrote:

> Hi,
> here is updated patch with the comments.  The fortran failures turned out to be
> funny interaction in between this patch and my other change that hoped that
> loop closed SSA is closed on VOPs, but it is not.
> 
> Regtested x86_64-linux, bootstrap in progress, OK?

Ok for trunk.

Thanks,
Richard.

> Honza
> 
> 	* tree-ssa-loop-niter.c (record_estimate): Do not try to lower
> 	the bound of non-is_exit statements.
> 	(maybe_lower_iteration_bound): Do it here.
> 	(estimate_numbers_of_iterations_loop): Call it.
> 	
> 	* gcc.c-torture/execute/pr54937.c: New testcase.
> 	* gcc.dg/tree-ssa/cunroll-2.c: Update.
> Index: tree-ssa-loop-niter.c
> ===================================================================
> --- tree-ssa-loop-niter.c	(revision 192632)
> +++ tree-ssa-loop-niter.c	(working copy)
> @@ -2535,7 +2541,6 @@ record_estimate (struct loop *loop, tree
>  		 gimple at_stmt, bool is_exit, bool realistic, bool upper)
>  {
>    double_int delta;
> -  edge exit;
>  
>    if (dump_file && (dump_flags & TDF_DETAILS))
>      {
> @@ -2570,14 +2577,10 @@ record_estimate (struct loop *loop, tree
>      }
>  
>    /* Update the number of iteration estimates according to the bound.
> -     If at_stmt is an exit or dominates the single exit from the loop,
> -     then the loop latch is executed at most BOUND times, otherwise
> -     it can be executed BOUND + 1 times.  */
> -  exit = single_exit (loop);
> -  if (is_exit
> -      || (exit != NULL
> -	  && dominated_by_p (CDI_DOMINATORS,
> -			     exit->src, gimple_bb (at_stmt))))
> +     If at_stmt is an exit then the loop latch is executed at most BOUND times,
> +     otherwise it can be executed BOUND + 1 times.  We will lower the estimate
> +     later if such statement must be executed on last iteration  */
> +  if (is_exit)
>      delta = double_int_zero;
>    else
>      delta = double_int_one;
> @@ -2953,6 +2956,110 @@ gcov_type_to_double_int (gcov_type val)
>    return ret;
>  }
>  
> +/* See if every path cross the loop goes through a statement that is known
> +   to not execute at the last iteration. In that case we can decrese iteration
> +   count by 1.  */
> +
> +static void
> +maybe_lower_iteration_bound (struct loop *loop)
> +{
> +  pointer_set_t *not_executed_last_iteration = pointer_set_create ();
> +  struct nb_iter_bound *elt;
> +  bool found_exit = false;
> +  VEC (basic_block, heap) *queue = NULL;
> +  bitmap visited;
> +
> +  /* Collect all statements with interesting (i.e. lower than
> +     nb_iterations_upper_bound) bound on them. 
> +
> +     TODO: Due to the way record_estimate choose estimates to store, the bounds
> +     will be always nb_iterations_upper_bound-1.  We can change this to record
> +     also statements not dominating the loop latch and update the walk bellow
> +     to the shortest path algorthm.  */
> +  for (elt = loop->bounds; elt; elt = elt->next)
> +    {
> +      if (!elt->is_exit
> +	  && elt->bound.ult (loop->nb_iterations_upper_bound))
> +	{
> +	  if (!not_executed_last_iteration)
> +	    not_executed_last_iteration = pointer_set_create ();
> +	  pointer_set_insert (not_executed_last_iteration, elt->stmt);
> +	}
> +    }
> +  if (!not_executed_last_iteration)
> +    return;
> +
> +  /* Start DFS walk in the loop header and see if we can reach the
> +     loop latch or any of the exits (including statements with side
> +     effects that may terminate the loop otherwise) without visiting
> +     any of the statements known to have undefined effect on the last
> +     iteration.  */
> +  VEC_safe_push (basic_block, heap, queue, loop->header);
> +  visited = BITMAP_ALLOC (NULL);
> +  bitmap_set_bit (visited, loop->header->index);
> +  found_exit = false;
> +
> +  do
> +    {
> +      basic_block bb = VEC_pop (basic_block, queue);
> +      gimple_stmt_iterator gsi;
> +      bool stmt_found = false;
> +
> +      /* Loop for possible exits and statements bounding the execution.  */
> +      for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
> +	{
> +	  gimple stmt = gsi_stmt (gsi);
> +	  if (pointer_set_contains (not_executed_last_iteration, stmt))
> +	    {
> +	      stmt_found = true;
> +	      break;
> +	    }
> +	  if (gimple_has_side_effects (stmt))
> +	    {
> +	      found_exit = true;
> +	      break;
> +	    }
> +	}
> +      if (found_exit)
> +	break;
> +
> +      /* If no bounding statement is found, continue the walk.  */
> +      if (!stmt_found)
> +	{
> +          edge e;
> +          edge_iterator ei;
> +
> +          FOR_EACH_EDGE (e, ei, bb->succs)
> +	    {
> +	      if (loop_exit_edge_p (loop, e)
> +		  || e == loop_latch_edge (loop))
> +		{
> +		  found_exit = true;
> +		  break;
> +		}
> +	      if (bitmap_set_bit (visited, e->dest->index))
> +		VEC_safe_push (basic_block, heap, queue, e->dest);
> +	    }
> +	}
> +    }
> +  while (VEC_length (basic_block, queue) && !found_exit);
> +
> +  /* If every path through the loop reach bounding statement before exit,
> +     then we know the last iteration of the loop will have undefined effect
> +     and we can decrease number of iterations.  */
> +    
> +  if (!found_exit)
> +    {
> +      if (dump_file && (dump_flags & TDF_DETAILS))
> +	fprintf (dump_file, "Reducing loop iteration estimate by 1; "
> +		 "undefined statement must be executed at the last iteration.\n");
> +      record_niter_bound (loop, loop->nb_iterations_upper_bound - double_int_one,
> +			  false, true);
> +    }
> +  BITMAP_FREE (visited);
> +  VEC_free (basic_block, heap, queue);
> +}
> +
>  /* Records estimates on numbers of iterations of LOOP.  If USE_UNDEFINED_P
>     is true also use estimates derived from undefined behavior.  */
>  
> @@ -2996,6 +3103,8 @@ estimate_numbers_of_iterations_loop (str
>  
>    infer_loop_bounds_from_undefined (loop);
>  
> +  maybe_lower_iteration_bound (loop);
> +
>    /* If we have a measured profile, use it to estimate the number of
>       iterations.  */
>    if (loop->header->count != 0)
> Index: testsuite/gcc.c-torture/execute/pr54937.c
> ===================================================================
> --- testsuite/gcc.c-torture/execute/pr54937.c	(revision 0)
> +++ testsuite/gcc.c-torture/execute/pr54937.c	(revision 0)
> @@ -0,0 +1,22 @@
> +
> +void exit (int);
> +void abort (void);
> +int a[1];
> +void (*terminate_me)(int);
> +
> +__attribute__((noinline,noclone))
> +t(int c)
> +{ int i;
> +  for (i=0;i<c;i++)
> +    {
> +      if (i)
> +       terminate_me(0);
> +      a[i]=0;
> +    }
> +}
> +main()
> +{
> +  terminate_me = exit;
> +  t(100);
> +  abort();
> +}
> Index: testsuite/gcc.dg/tree-ssa/cunroll-2.c
> ===================================================================
> --- testsuite/gcc.dg/tree-ssa/cunroll-2.c	(revision 192632)
> +++ testsuite/gcc.dg/tree-ssa/cunroll-2.c	(working copy)
> @@ -12,5 +12,5 @@ test(int c)
>      }
>  }
>  /* We are not able to get rid of the final conditional because the loop has two exits.  */
> -/* { dg-final { scan-tree-dump "Unrolled loop 1 completely .duplicated 2 times.." "cunroll"} } */
> +/* { dg-final { scan-tree-dump "Unrolled loop 1 completely .duplicated 1 times.." "cunroll"} } */
>  /* { dg-final { cleanup-tree-dump "cunroll" } } */
> 
> 

-- 
Richard Biener <rguenther@suse.de>
SUSE / SUSE Labs
SUSE LINUX Products GmbH - Nuernberg - AG Nuernberg - HRB 16746
GF: Jeff Hawn, Jennifer Guild, Felix Imend

Re: Fix array bound niter estimate (PR middle-end/54937)

[Richard Biener]

On Fri, 19 Oct 2012, Jan Hubicka wrote:

> > On Fri, 19 Oct 2012, Jan Hubicka wrote:
> > 
> > > Hi,
> > > this patch fixes off-by-one error in the testcase attached.  The problem is that
> > > dominance based test used by record_estimate to check whether the given statement
> > > must be executed at last iteration of the loop is wrong ignoring the side effect
> > > of other statements that may terminate the program.
> > > It also does not work for mulitple exits as excercised by cunroll-2.c testcase.
> > > 
> > > This patch makes simple approach of computing set of all statements that must
> > > by executed last iteration first time record_estimate is executed this way.
> > > The set is computed conservatively walking header BB and its signle successors
> > > (possibly diving into nested loop) stopping on first BB with multiple exits.
> > > 
> > > Better result can be computed by
> > > 1) estimating what loops are known to be finite
> > > 2) inserting fake edges for all infinite loop and all statements with side effect
> > >    that may terminate the execution
> > > 3) using the post dominance info.
> > 
> > would using post-dom info even work?  That only says that _if_ the
> > dominated stmt executed then it came through the dominator.  It
> > doesn't deal with functions that may not return.
> 
> With fake edges inserted it will. We do have code for that used in profiling that
> also needs this stronger definition of CFG.

Huh, but then we will need to split blocks.  I don't think that's viable.

> > 
> > What about the conservative variant of simply
> > 
> >       else
> >         delta = double_int_one;
> 
> I think it would be bad idea: it makes us to completely unroll one interation
> too many that bloats code for no benefit. No optimization cancels the path in
> CFG because of undefined effect and thus the code will be output (unless someone
> smarter, like VRP, cleans up later, but it is more an exception than rule.)
> > 
> > ?  I don't like all the code you add, nor the use of ->aux.
> 
> Neither I really do, but what are the alternatives?

See above ;)

> My first implementation simply checked that stmt is in the loop header and
> walked up to the beggining of basic blocks looking for side effects.  Then I
> become worried about possibility of gigantic basic blocks with many array
> stores within the loop, so I decided to record the reachable statements instead
> of repeating the walk.
> Loop count estimation is recursive (i.e. it dives into inner loops), thus I
> ended up with using AUX.  I can for sure put this separately or add extra
> reference argument passed over the whole call stack, but there are quite many
> functions that can leads to record_estimate. (I have nothing against that
> alternative however if AUX looks ugly)

I am worried about passes trying to use AUX.  We should at least document
that it is for internal use only.

> > 
> > >     i_bound += delta;
> > 
> > Another alternative would be to not use i_bound for the
> > strong upper bound but only the estimate (thus conservatively
> > use i_bound + 1 for the upper bound if !is_exit).
> 
> We can not derrive realistic estimate based on this: the loop may exit much earlier.
> We can only lower the estimate if it is already there and greater than this bound.
> This can probably happen with profile feedback and I can implement it later,
> I do not think it is terribly important though.
> 
> Honza
> 
> 

-- 
Richard Biener <rguenther@suse.de>
SUSE / SUSE Labs
SUSE LINUX Products GmbH - Nuernberg - AG Nuernberg - HRB 16746
GF: Jeff Hawn, Jennifer Guild, Felix Imend