* tree-ssa-loop-niter.c (compute_estimated_nb_iterations): Fix

	off-by-one error.
	(array_at_struct_end_p): New function.
	(idx_infer_loop_bounds): Use it.
	(estimate_numbers_of_iterations_loop): Export.
	* predict.c (predict_loops): Use estimated_loop_iterations_int.
	Do not use PRED_LOOP_EXIT on exits predicted by # of iterations.
	(tree_estimate_probability): Call record_loop_exits.
	* tree-data-ref.c (get_number_of_iters_for_loop): Replaced by ...
	(estimated_loop_iterations, estimated_loop_iterations_int,
	estimated_loop_iterations_tree): New functions.
	(analyze_siv_subscript_cst_affine,
	compute_overlap_steps_for_affine_1_2,
	analyze_subscript_affine_affine): Use estimated_loop_iterations_int.
	(analyze_miv_subscript): Use estimated_loop_iterations_tree.
	* predict.def (PRED_LOOP_ITERATIONS): Update comment.
	(PRED_LOOP_ITERATIONS_GUESSED): New.
	* cfgloop.c (record_loop_exits): Do nothing if there are no loops.
	* cfgloop.h (estimate_numbers_of_iterations_loop,
	estimated_loop_iterations_int): Declare.



git-svn-id: svn+ssh://gcc.gnu.org/svn/gcc/trunk@122316 138bc75d-0d04-0410-961f-82ee72b054a4

1 files changed, 69 insertions, 4 deletions

diff --git a/gcc/tree-ssa-loop-niter.c b/gcc/tree-ssa-loop-niter.c
index 56ef2e90e8c..018e9a80529 100644
--- a/gcc/tree-ssa-loop-niter.c
+++ b/gcc/tree-ssa-loop-niter.c
@@ -1752,6 +1752,8 @@ static void
 compute_estimated_nb_iterations (struct loop *loop)
 {
   struct nb_iter_bound *bound;
+  double_int bnd_val, delta;
+  edge exit;
  
   gcc_assert (loop->estimate_state == EST_NOT_AVAILABLE);
 
@@ -1760,17 +1762,79 @@ compute_estimated_nb_iterations (struct loop *loop)
       if (!bound->realistic)
 	continue;
 
+      bnd_val = bound->bound;
+      /* If bound->stmt is an exit, then every statement in the loop is
+	 executed at most BND_VAL + 1 times.  If it is not an exit, then
+	 some of the statements before it could be executed BND_VAL + 2
+	 times, if an exit of LOOP is before stmt.  */
+      exit = single_exit (loop);
+
+      if (bound->is_exit
+	  || (exit != NULL
+	      && dominated_by_p (CDI_DOMINATORS,
+				 exit->src, bb_for_stmt (bound->stmt))))
+	delta = double_int_one;
+      else
+	delta = double_int_two;
+      bnd_val = double_int_add (bnd_val, delta);
+
+      /* If an overflow occured, ignore the result.  */
+      if (double_int_ucmp (bnd_val, delta) < 0)
+	continue;
+
       /* Update only when there is no previous estimation, or when the current
 	 estimation is smaller.  */
       if (loop->estimate_state == EST_NOT_AVAILABLE
-	  || double_int_ucmp (bound->bound, loop->estimated_nb_iterations) < 0)
+	  || double_int_ucmp (bnd_val, loop->estimated_nb_iterations) < 0)
 	{
 	  loop->estimate_state = EST_AVAILABLE;
-	  loop->estimated_nb_iterations = bound->bound;
+	  loop->estimated_nb_iterations = bnd_val;
 	}
     }
 }
 
+/* Returns true if REF is a reference to an array at the end of a dynamically
+   allocated structure.  If this is the case, the array may be allocated larger
+   than its upper bound implies.  */
+
+static bool
+array_at_struct_end_p (tree ref)
+{
+  tree base = get_base_address (ref);
+  tree parent, field;
+
+  /* Unless the reference is through a pointer, the size of the array matches
+     its declaration.  */
+  if (!base || !INDIRECT_REF_P (base))
+    return false;
+  
+  for (;handled_component_p (ref); ref = parent)
+    {
+      parent = TREE_OPERAND (ref, 0);
+
+      if (TREE_CODE (ref) == COMPONENT_REF)
+	{
+	  /* All fields of a union are at its end.  */
+	  if (TREE_CODE (TREE_TYPE (parent)) == UNION_TYPE)
+	    continue;
+
+	  /* Unless the field is at the end of the struct, we are done.  */
+	  field = TREE_OPERAND (ref, 1);
+	  if (TREE_CHAIN (field))
+	    return false;
+	}
+
+      /* The other options are ARRAY_REF, ARRAY_RANGE_REF, VIEW_CONVERT_EXPR.
+	 In all these cases, we might be accessing the last element, and
+	 although in practice this will probably never happen, it is legal for
+	 the indices of this last element to exceed the bounds of the array.
+	 Therefore, continue checking.  */
+    }
+
+  gcc_assert (INDIRECT_REF_P (ref));
+  return true;
+}
+
 /* Determine information about number of iterations a LOOP from the index
    IDX of a data reference accessed in STMT.  Callback for for_each_index.  */
 
@@ -1789,7 +1853,8 @@ idx_infer_loop_bounds (tree base, tree *idx, void *dta)
   bool sign;
   struct loop *loop = data->loop;
 
-  if (TREE_CODE (base) != ARRAY_REF)
+  if (TREE_CODE (base) != ARRAY_REF
+      || array_at_struct_end_p (base))
     return true;
 
   ev = instantiate_parameters (loop, analyze_scalar_evolution (loop, *idx));
@@ -1974,7 +2039,7 @@ infer_loop_bounds_from_undefined (struct loop *loop)
 
 /* Records estimates on numbers of iterations of LOOP.  */
 
-static void
+void
 estimate_numbers_of_iterations_loop (struct loop *loop)
 {
   VEC (edge, heap) *exits;