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

[Jan Hubicka <hubicka at ucw dot cz>]

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