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

login
register
mail settings
Submitter Jan Hubicka
Date Oct. 22, 2012, 3:22 p.m.
Message ID <20121022152240.GA13310@kam.mff.cuni.cz>
Download mbox | patch
Permalink /patch/193176/
State New
Headers show

Comments

Jan Hubicka - Oct. 22, 2012, 3:22 p.m.
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.
Richard Guenther - Oct. 23, 2012, 9:30 a.m.
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" } } */
> 
>

Patch

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" } } */