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

login
register
mail settings
Submitter Jan Hubicka
Date Oct. 20, 2012, 2:43 p.m.
Message ID <20121020144331.GA29352@kam.mff.cuni.cz>
Download mbox | patch
Permalink /patch/192919/
State New
Headers show

Comments

Jan Hubicka - Oct. 20, 2012, 2:43 p.m.
> > > > 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.

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