* Makefile.in (tree-data-ref.o): Add langhooks.h dependency.

	* tree-ssa-loop-niter.c (derive_constant_upper_bound):  Follow
	ud-chains.  Handle AND_EXPR.
	(record_estimate): Record whether the estimate is realistic
	and whether it is derived from a loop exit.
	(record_nonwrapping_iv, idx_infer_loop_bounds, infer_loop_bounds_from_ref,
	infer_loop_bounds_from_array, infer_loop_bounds_from_signedness): New
	functions.
	(compute_estimated_nb_iterations): Take only realistic bounds into
	account.  Set estimate_state.  Use double_ints.
	(infer_loop_bounds_from_undefined): Call infer_loop_bounds_from_array
	and infer_loop_bounds_from_signedness.  Do not consider basic blocks
	that do not have to be always executed.
	(estimate_numbers_of_iterations_loop): Set estimate_state, and use it
	to determine whether to call infer_loop_bounds_from_undefined
	and compute_estimated_nb_iterations.
	(n_of_executions_at_most): Use double_ints.
	(free_numbers_of_iterations_estimates_loop): Set estimate_state.
	(substitute_in_loop_info): Do not replace in estimated_nb_iterations.
	* double-int.c (double_int_to_tree): Improve comment.
	(double_int_fits_to_tree_p): New function.
	* double-int.h (double_int_fits_to_tree_p): Declare.
	* tree-data-ref.c: Include langhooks.h.
	(estimate_niter_from_size_of_data, estimate_iters_using_array): Removed.
	(analyze_array_indexes): Do not call estimate_niter_from_size_of_data.
	(analyze_array): Do not pass estimate_only argument to
	analyze_array_indexes.
	(get_number_of_iters_for_loop): Build tree from the stored double_int
	value.
	(get_references_in_stmt, find_data_references_in_stmt): New functions.
	(find_data_references_in_loop): Use find_data_references_in_stmt.
	* tree-data-ref.h (struct data_ref_loc_d): New.
	(get_references_in_stmt): Declare.
	(estimate_iters_using_array): Declaration removed.
	* cfgloop.h (struct nb_iter_bound): Change type of bound to
	double_int.  Improve comments.  Add is_exit and realistic
	fields.
	(struct loop): Changed type of estimated_nb_iterations to double_int.
	Added estimate_state field.
	(record_estimate): Declaration removed.



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

8 files changed, 579 insertions, 338 deletions

diff --git a/gcc/ChangeLog b/gcc/ChangeLog
index d3363d17169..845e2353ef5 100644
--- a/gcc/ChangeLog
+++ b/gcc/ChangeLog
@@ -1,5 +1,48 @@
 2006-11-12  Zdenek Dvorak <dvorakz@suse.cz>
 
+	* Makefile.in (tree-data-ref.o): Add langhooks.h dependency.
+	* tree-ssa-loop-niter.c (derive_constant_upper_bound):  Follow
+	ud-chains.  Handle AND_EXPR.
+	(record_estimate): Record whether the estimate is realistic
+	and whether it is derived from a loop exit.
+	(record_nonwrapping_iv, idx_infer_loop_bounds, infer_loop_bounds_from_ref,
+	infer_loop_bounds_from_array, infer_loop_bounds_from_signedness): New
+	functions.
+	(compute_estimated_nb_iterations): Take only realistic bounds into
+	account.  Set estimate_state.  Use double_ints.
+	(infer_loop_bounds_from_undefined): Call infer_loop_bounds_from_array
+	and infer_loop_bounds_from_signedness.  Do not consider basic blocks
+	that do not have to be always executed.
+	(estimate_numbers_of_iterations_loop): Set estimate_state, and use it
+	to determine whether to call infer_loop_bounds_from_undefined
+	and compute_estimated_nb_iterations.
+	(n_of_executions_at_most): Use double_ints.
+	(free_numbers_of_iterations_estimates_loop): Set estimate_state.
+	(substitute_in_loop_info): Do not replace in estimated_nb_iterations.
+	* double-int.c (double_int_to_tree): Improve comment.
+	(double_int_fits_to_tree_p): New function.
+	* double-int.h (double_int_fits_to_tree_p): Declare.
+	* tree-data-ref.c: Include langhooks.h.
+	(estimate_niter_from_size_of_data, estimate_iters_using_array): Removed.
+	(analyze_array_indexes): Do not call estimate_niter_from_size_of_data.
+	(analyze_array): Do not pass estimate_only argument to
+	analyze_array_indexes.
+	(get_number_of_iters_for_loop): Build tree from the stored double_int
+	value.
+	(get_references_in_stmt, find_data_references_in_stmt): New functions.
+	(find_data_references_in_loop): Use find_data_references_in_stmt.
+	* tree-data-ref.h (struct data_ref_loc_d): New.
+	(get_references_in_stmt): Declare.
+	(estimate_iters_using_array): Declaration removed.
+	* cfgloop.h (struct nb_iter_bound): Change type of bound to
+	double_int.  Improve comments.  Add is_exit and realistic
+	fields.
+	(struct loop): Changed type of estimated_nb_iterations to double_int.
+	Added estimate_state field.
+	(record_estimate): Declaration removed.
+
+2006-11-12  Zdenek Dvorak <dvorakz@suse.cz>
+
 	* params.c (set_param_value): Initialize the "set" field.
 	* params.h (struct param_info): Add "set" field.
 	(PARAM_SET_P): New macro.
diff --git a/gcc/Makefile.in b/gcc/Makefile.in
index 59be2fe09c6..7e4c16a5e6a 100644
--- a/gcc/Makefile.in
+++ b/gcc/Makefile.in
@@ -2080,7 +2080,7 @@ tree-scalar-evolution.o: tree-scalar-evolution.c $(CONFIG_H) $(SYSTEM_H) \
 tree-data-ref.o: tree-data-ref.c $(CONFIG_H) $(SYSTEM_H) coretypes.h $(TM_H) \
    $(GGC_H) $(TREE_H) $(RTL_H) $(BASIC_BLOCK_H) $(DIAGNOSTIC_H) \
    $(TREE_FLOW_H) $(TREE_DUMP_H) $(TIMEVAR_H) $(CFGLOOP_H) \
-   $(TREE_DATA_REF_H) $(SCEV_H) tree-pass.h tree-chrec.h
+   $(TREE_DATA_REF_H) $(SCEV_H) tree-pass.h tree-chrec.h langhooks.h
 tree-vect-analyze.o: tree-vect-analyze.c $(CONFIG_H) $(SYSTEM_H) coretypes.h \
    $(TM_H) $(GGC_H) $(OPTABS_H) $(TREE_H) $(BASIC_BLOCK_H) \
    $(DIAGNOSTIC_H) $(TREE_FLOW_H) $(TREE_DUMP_H) $(TIMEVAR_H) $(CFGLOOP_H) \
diff --git a/gcc/cfgloop.h b/gcc/cfgloop.h
index 6838677011e..311c43ea922 100644
--- a/gcc/cfgloop.h
+++ b/gcc/cfgloop.h
@@ -47,12 +47,31 @@ struct lpt_decision
 
 struct nb_iter_bound
 {
-  tree bound;		/* The constant expression whose value is an upper
-			   bound on the number of executions of ...  */
-  tree at_stmt;		/* ... this statement during one execution of
-			   a loop.  */
+  /* The statement STMT is executed at most ...  */
+  tree stmt;
+
+  /* ... BOUND + 1 times (BOUND must be an unsigned constant).
+     The + 1 is added for the following reasons:
+
+     a) 0 would otherwise be unused, while we would need to care more about
+        overflows (as MAX + 1 is sometimes produced as the estimate on number
+	of executions of STMT).
+     b) it is consistent with the result of number_of_iterations_exit.  */
+  double_int bound;
+
+  /* True if the statement will cause the loop to be leaved the (at most) 
+     BOUND + 1-st time it is executed, that is, all the statements after it
+     are executed at most BOUND times.  */
+  bool is_exit;
+
+  /* True if the bound is "realistic" -- i.e., most likely the loop really has
+     number of iterations close to the bound.  Exact bounds (if the number of
+     iterations of a loop is a constant) and bounds derived from the size of
+     data accessed in the loop are considered realistic.  */
+  bool realistic;
+
+  /* The next bound in the list.  */
   struct nb_iter_bound *next;
-			/* The next bound in a list.  */
 };
 
 /* Structure to hold information for each natural loop.  */
@@ -111,9 +130,18 @@ struct loop
      information in this field.  */
   tree nb_iterations;
 
-  /* An INTEGER_CST estimation of the number of iterations.  NULL_TREE
-     if there is no estimation.  */
-  tree estimated_nb_iterations;
+  /* An integer estimation of the number of iterations.  Estimate_state
+     describes what is the state of the estimation.  */
+  enum
+    {
+      /* Estimate was not computed yet.  */
+      EST_NOT_COMPUTED,
+      /* Estimate was computed, but we could derive no useful bound.  */
+      EST_NOT_AVAILABLE,
+      /* Estimate is ready.  */
+      EST_AVAILABLE
+    } estimate_state;
+  double_int estimated_nb_iterations;
 
   /* Upper bound on number of iterations of a loop.  */
   struct nb_iter_bound *bounds;
@@ -398,6 +426,5 @@ enum
 extern void unroll_and_peel_loops (struct loops *, int);
 extern void doloop_optimize_loops (struct loops *);
 extern void move_loop_invariants (struct loops *);
-extern void record_estimate (struct loop *, tree, tree, tree);
 
 #endif /* GCC_CFGLOOP_H */
diff --git a/gcc/double-int.c b/gcc/double-int.c
index 3be0abf4f3a..f1824da8ff4 100644
--- a/gcc/double-int.c
+++ b/gcc/double-int.c
@@ -290,7 +290,8 @@ double_int_umod (double_int a, double_int b, unsigned code)
   return double_int_mod (a, b, true, code);
 }
 
-/* Constructs tree in type TYPE from with value given by CST.  */
+/* Constructs tree in type TYPE from with value given by CST.  Signedness of CST
+   is assumed to be the same as the signedness of TYPE.  */
 
 tree
 double_int_to_tree (tree type, double_int cst)
@@ -300,6 +301,19 @@ double_int_to_tree (tree type, double_int cst)
   return build_int_cst_wide (type, cst.low, cst.high);
 }
 
+/* Returns true if CST fits into range of TYPE.  Signedness of CST is assumed
+   to be the same as the signedness of TYPE.  */
+
+bool
+double_int_fits_to_tree_p (tree type, double_int cst)
+{
+  double_int ext = double_int_ext (cst,
+				   TYPE_PRECISION (type),
+				   TYPE_UNSIGNED (type));
+
+  return double_int_equal_p (cst, ext);
+}
+
 /* Returns true if CST is negative.  Of course, CST is considered to
    be signed.  */
 
diff --git a/gcc/double-int.h b/gcc/double-int.h
index eddd7b7e2fe..6ecfa48f787 100644
--- a/gcc/double-int.h
+++ b/gcc/double-int.h
@@ -58,7 +58,8 @@ union tree_node;
 /* Constructors and conversions.  */
 
 union tree_node *double_int_to_tree (union tree_node *, double_int);
-double_int tree_to_double_int (union tree_node *tree);
+bool double_int_fits_to_tree_p (union tree_node *, double_int);
+double_int tree_to_double_int (union tree_node *);
 
 /* Constructs double_int from integer CST.  The bits over the precision of
    HOST_WIDE_INT are filled with the sign bit.  */
diff --git a/gcc/tree-data-ref.c b/gcc/tree-data-ref.c
index 2e47a25ac90..3734058bbbf 100644
--- a/gcc/tree-data-ref.c
+++ b/gcc/tree-data-ref.c
@@ -93,6 +93,7 @@ Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA
 #include "tree-data-ref.h"
 #include "tree-scalar-evolution.h"
 #include "tree-pass.h"
+#include "langhooks.h"
 
 static struct datadep_stats
 {
@@ -888,75 +889,16 @@ dump_ddrs (FILE *file, VEC (ddr_p, heap) *ddrs)
 
 
 
-/* Estimate the number of iterations from the size of the data and the
-   access functions.  */
-
-static void
-estimate_niter_from_size_of_data (struct loop *loop, 
-				  tree opnd0, 
-				  tree access_fn, 
-				  tree stmt)
-{
-  tree estimation = NULL_TREE;
-  tree array_size, data_size, element_size;
-  tree init, step;
-
-  init = initial_condition (access_fn);
-  step = evolution_part_in_loop_num (access_fn, loop->num);
-
-  array_size = TYPE_SIZE (TREE_TYPE (opnd0));
-  element_size = TYPE_SIZE (TREE_TYPE (TREE_TYPE (opnd0)));
-  if (array_size == NULL_TREE 
-      || TREE_CODE (array_size) != INTEGER_CST
-      || TREE_CODE (element_size) != INTEGER_CST)
-    return;
-
-  data_size = fold_build2 (EXACT_DIV_EXPR, integer_type_node,
-			   array_size, element_size);
-
-  if (init != NULL_TREE
-      && step != NULL_TREE
-      && TREE_CODE (init) == INTEGER_CST
-      && TREE_CODE (step) == INTEGER_CST)
-    {
-      tree i_plus_s = fold_build2 (PLUS_EXPR, integer_type_node, init, step);
-      tree sign = fold_binary (GT_EXPR, boolean_type_node, i_plus_s, init);
-
-      if (sign == boolean_true_node)
-	estimation = fold_build2 (CEIL_DIV_EXPR, integer_type_node,
-				  fold_build2 (MINUS_EXPR, integer_type_node,
-					       data_size, init), step);
-
-      /* When the step is negative, as in PR23386: (init = 3, step =
-	 0ffffffff, data_size = 100), we have to compute the
-	 estimation as ceil_div (init, 0 - step) + 1.  */
-      else if (sign == boolean_false_node)
-	estimation = 
-	  fold_build2 (PLUS_EXPR, integer_type_node,
-		       fold_build2 (CEIL_DIV_EXPR, integer_type_node,
-				    init,
-				    fold_build2 (MINUS_EXPR, unsigned_type_node,
-						 integer_zero_node, step)),
-		       integer_one_node);
-
-      if (estimation)
-	record_estimate (loop, estimation, boolean_true_node, stmt);
-    }
-}
-
 /* Given an ARRAY_REF node REF, records its access functions.
    Example: given A[i][3], record in ACCESS_FNS the opnd1 function,
    i.e. the constant "3", then recursively call the function on opnd0,
    i.e. the ARRAY_REF "A[i]".  
-   If ESTIMATE_ONLY is true, we just set the estimated number of loop
-   iterations, we don't store the access function.
    The function returns the base name: "A".  */
 
 static tree
 analyze_array_indexes (struct loop *loop,
 		       VEC(tree,heap) **access_fns, 
-		       tree ref, tree stmt,
-		       bool estimate_only)
+		       tree ref, tree stmt)
 {
   tree opnd0, opnd1;
   tree access_fn;
@@ -971,32 +913,17 @@ analyze_array_indexes (struct loop *loop,
   access_fn = instantiate_parameters
     (loop, analyze_scalar_evolution (loop, opnd1));
 
-  if (estimate_only 
-      && chrec_contains_undetermined (loop->estimated_nb_iterations))
-    estimate_niter_from_size_of_data (loop, opnd0, access_fn, stmt);
-
-  if (!estimate_only)
-    VEC_safe_push (tree, heap, *access_fns, access_fn);
+  VEC_safe_push (tree, heap, *access_fns, access_fn);
   
   /* Recursively record other array access functions.  */
   if (TREE_CODE (opnd0) == ARRAY_REF)
-    return analyze_array_indexes (loop, access_fns, opnd0, stmt, estimate_only);
+    return analyze_array_indexes (loop, access_fns, opnd0, stmt);
 
   /* Return the base name of the data access.  */
   else
     return opnd0;
 }
 
-/* For an array reference REF contained in STMT, attempt to bound the
-   number of iterations in the loop containing STMT  */
-
-void 
-estimate_iters_using_array (tree stmt, tree ref)
-{
-  analyze_array_indexes (loop_containing_stmt (stmt), NULL, ref, stmt, 
-			 true);
-}
-  
 /* For a data reference REF contained in the statement STMT, initialize
    a DATA_REFERENCE structure, and return it.  IS_READ flag has to be
    set to true when REF is in the right hand side of an
@@ -1022,7 +949,7 @@ analyze_array (tree stmt, tree ref, bool is_read)
   DR_REF (res) = ref;
   acc_fns = VEC_alloc (tree, heap, 3);
   DR_BASE_OBJECT (res) = analyze_array_indexes
-    (loop_containing_stmt (stmt), &acc_fns, ref, stmt, false);
+    (loop_containing_stmt (stmt), &acc_fns, ref, stmt);
   DR_TYPE (res) = ARRAY_REF_TYPE;
   DR_SET_ACCESS_FNS (res, acc_fns);
   DR_IS_READ (res) = is_read;
@@ -2377,13 +2304,20 @@ analyze_ziv_subscript (tree chrec_a,
 static tree
 get_number_of_iters_for_loop (int loopnum)
 {
-  tree numiter = number_of_iterations_in_loop (current_loops->parray[loopnum]);
+  struct loop *loop = current_loops->parray[loopnum];
+  tree numiter = number_of_iterations_in_loop (loop);
+
+  if (TREE_CODE (numiter) == INTEGER_CST)
+    return numiter;
 
-  if (TREE_CODE (numiter) != INTEGER_CST)
-    numiter = current_loops->parray[loopnum]->estimated_nb_iterations;
-  if (chrec_contains_undetermined (numiter))
-    return NULL_TREE;
-  return numiter;
+  if (loop->estimate_state == EST_AVAILABLE)
+    {
+      tree type = lang_hooks.types.type_for_size (INT_TYPE_SIZE, true);
+      if (double_int_fits_to_tree_p (type, loop->estimated_nb_iterations))
+	return double_int_to_tree (type, loop->estimated_nb_iterations);
+    }
+
+  return NULL_TREE;
 }
     
 /* Analyze a SIV (Single Index Variable) subscript where CHREC_A is a
@@ -4060,6 +3994,105 @@ compute_all_dependences (VEC (data_reference_p, heap) *datarefs,
       }
 }
 
+/* Stores the locations of memory references in STMT to REFERENCES.  Returns
+   true if STMT clobbers memory, false otherwise.  */
+
+bool
+get_references_in_stmt (tree stmt, VEC (data_ref_loc, heap) **references)
+{
+  bool clobbers_memory = false;
+  data_ref_loc *ref;
+  tree *op0, *op1, args, call;
+
+  *references = NULL;
+
+  /* ASM_EXPR and CALL_EXPR may embed arbitrary side effects.
+     Calls have side-effects, except those to const or pure
+     functions.  */
+  call = get_call_expr_in (stmt);
+  if ((call
+       && !(call_expr_flags (call) & (ECF_CONST | ECF_PURE)))
+      || (TREE_CODE (stmt) == ASM_EXPR
+	  && ASM_VOLATILE_P (stmt)))
+    clobbers_memory = true;
+
+  if (ZERO_SSA_OPERANDS (stmt, SSA_OP_ALL_VIRTUALS))
+    return clobbers_memory;
+
+  if (TREE_CODE (stmt) ==  MODIFY_EXPR)
+    {
+      op0 = &TREE_OPERAND (stmt, 0);
+      op1 = &TREE_OPERAND (stmt, 1);
+		
+      if (DECL_P (*op1)
+	  || REFERENCE_CLASS_P (*op1))
+	{
+	  ref = VEC_safe_push (data_ref_loc, heap, *references, NULL);
+	  ref->pos = op1;
+	  ref->is_read = true;
+	}
+
+      if (DECL_P (*op0)
+	  || REFERENCE_CLASS_P (*op0))
+	{
+	  ref = VEC_safe_push (data_ref_loc, heap, *references, NULL);
+	  ref->pos = op0;
+	  ref->is_read = false;
+	}
+    }
+
+  if (call)
+    {
+      for (args = TREE_OPERAND (call, 1); args; args = TREE_CHAIN (args))
+	{
+	  op0 = &TREE_VALUE (args);
+	  if (DECL_P (*op0)
+	      || REFERENCE_CLASS_P (*op0))
+	    {
+	      ref = VEC_safe_push (data_ref_loc, heap, *references, NULL);
+	      ref->pos = op0;
+	      ref->is_read = true;
+	    }
+	}
+    }
+
+  return clobbers_memory;
+}
+
+/* Stores the data references in STMT to DATAREFS.  If there is an unanalyzable
+   reference, returns false, otherwise returns true.  */
+
+static bool
+find_data_references_in_stmt (tree stmt,
+			      VEC (data_reference_p, heap) **datarefs)
+{
+  unsigned i;
+  VEC (data_ref_loc, heap) *references;
+  data_ref_loc *ref;
+  bool ret = true;
+  data_reference_p dr;
+
+  if (get_references_in_stmt (stmt, &references))
+    {
+      VEC_free (data_ref_loc, heap, references);
+      return false;
+    }
+
+  for (i = 0; VEC_iterate (data_ref_loc, references, i, ref); i++)
+    {
+      dr = create_data_ref (*ref->pos, stmt, ref->is_read);
+      if (dr)
+	VEC_safe_push (data_reference_p, heap, *datarefs, dr);
+      else
+	{
+	  ret = false;
+	  break;
+	}
+    }
+  VEC_free (data_ref_loc, heap, references);
+  return ret;
+}
+
 /* Search the data references in LOOP, and record the information into
    DATAREFS.  Returns chrec_dont_know when failing to analyze a
    difficult case, returns NULL_TREE otherwise.
@@ -4074,118 +4107,41 @@ find_data_references_in_loop (struct loop *loop,
   basic_block bb, *bbs;
   unsigned int i;
   block_stmt_iterator bsi;
-  struct data_reference *dr;
 
   bbs = get_loop_body (loop);
+  loop->parallel_p = true;
 
   for (i = 0; i < loop->num_nodes; i++)
     {
       bb = bbs[i];
 
       for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
-        {
+	{
 	  tree stmt = bsi_stmt (bsi);
 
-	  /* ASM_EXPR and CALL_EXPR may embed arbitrary side effects.
-	     Calls have side-effects, except those to const or pure
-	     functions.  */
-	  if ((TREE_CODE (stmt) == CALL_EXPR
-	       && !(call_expr_flags (stmt) & (ECF_CONST | ECF_PURE)))
-	      || (TREE_CODE (stmt) == ASM_EXPR
-		  && ASM_VOLATILE_P (stmt)))
-	    goto insert_dont_know_node;
-
-	  if (ZERO_SSA_OPERANDS (stmt, SSA_OP_ALL_VIRTUALS))
-	    continue;
-
-	  switch (TREE_CODE (stmt))
+	  if (!find_data_references_in_stmt (stmt, datarefs))
 	    {
-	    case MODIFY_EXPR:
-	      {
-		bool one_inserted = false;
-		tree opnd0 = TREE_OPERAND (stmt, 0);
-		tree opnd1 = TREE_OPERAND (stmt, 1);
-		
-		if (TREE_CODE (opnd0) == ARRAY_REF 
-		    || TREE_CODE (opnd0) == INDIRECT_REF
-                    || TREE_CODE (opnd0) == COMPONENT_REF)
-		  {
-		    dr = create_data_ref (opnd0, stmt, false);
-		    if (dr) 
-		      {
-			VEC_safe_push (data_reference_p, heap, *datarefs, dr);
-			one_inserted = true;
-		      }
-		  }
-
-		if (TREE_CODE (opnd1) == ARRAY_REF 
-		    || TREE_CODE (opnd1) == INDIRECT_REF
-		    || TREE_CODE (opnd1) == COMPONENT_REF)
-		  {
-		    dr = create_data_ref (opnd1, stmt, true);
-		    if (dr) 
-		      {
-			VEC_safe_push (data_reference_p, heap, *datarefs, dr);
-			one_inserted = true;
-		      }
-		  }
-
-		if (!one_inserted)
-		  goto insert_dont_know_node;
-
-		break;
-	      }
-
-	    case CALL_EXPR:
-	      {
-		tree args;
-		bool one_inserted = false;
-
-		for (args = TREE_OPERAND (stmt, 1); args; 
-		     args = TREE_CHAIN (args))
-		  if (TREE_CODE (TREE_VALUE (args)) == ARRAY_REF
-		      || TREE_CODE (TREE_VALUE (args)) == INDIRECT_REF
-		      || TREE_CODE (TREE_VALUE (args)) == COMPONENT_REF)
-		    {
-		      dr = create_data_ref (TREE_VALUE (args), stmt, true);
-		      if (dr)
-			{
-			  VEC_safe_push (data_reference_p, heap, *datarefs, dr);
-			  one_inserted = true;
-			}
-		    }
-
-		if (!one_inserted)
-		  goto insert_dont_know_node;
-
-		break;
-	      }
-
-	    default:
-		{
-		  struct data_reference *res;
-
-		insert_dont_know_node:;
-		  res = XNEW (struct data_reference);
-		  DR_STMT (res) = NULL_TREE;
-		  DR_REF (res) = NULL_TREE;
-		  DR_BASE_OBJECT (res) = NULL;
-		  DR_TYPE (res) = ARRAY_REF_TYPE;
-		  DR_SET_ACCESS_FNS (res, NULL);
-		  DR_BASE_OBJECT (res) = NULL;
-		  DR_IS_READ (res) = false;
-		  DR_BASE_ADDRESS (res) = NULL_TREE;
-		  DR_OFFSET (res) = NULL_TREE;
-		  DR_INIT (res) = NULL_TREE;
-		  DR_STEP (res) = NULL_TREE;
-		  DR_OFFSET_MISALIGNMENT (res) = NULL_TREE;
-		  DR_MEMTAG (res) = NULL_TREE;
-		  DR_PTR_INFO (res) = NULL;
-		  VEC_safe_push (data_reference_p, heap, *datarefs, res);
-
-		  free (bbs);
-		  return chrec_dont_know;
-		}
+	      struct data_reference *res;
+	      res = XNEW (struct data_reference);
+	      DR_STMT (res) = NULL_TREE;
+	      DR_REF (res) = NULL_TREE;
+	      DR_BASE_OBJECT (res) = NULL;
+	      DR_TYPE (res) = ARRAY_REF_TYPE;
+	      DR_SET_ACCESS_FNS (res, NULL);
+	      DR_BASE_OBJECT (res) = NULL;
+	      DR_IS_READ (res) = false;
+	      DR_BASE_ADDRESS (res) = NULL_TREE;
+	      DR_OFFSET (res) = NULL_TREE;
+	      DR_INIT (res) = NULL_TREE;
+	      DR_STEP (res) = NULL_TREE;
+	      DR_OFFSET_MISALIGNMENT (res) = NULL_TREE;
+	      DR_MEMTAG (res) = NULL_TREE;
+	      DR_PTR_INFO (res) = NULL;
+	      loop->parallel_p = false;
+	      VEC_safe_push (data_reference_p, heap, *datarefs, res);
+
+	      free (bbs);
+	      return chrec_dont_know;
 	    }
 
 	  /* When there are no defs in the loop, the loop is parallel.  */
@@ -4193,7 +4149,6 @@ find_data_references_in_loop (struct loop *loop,
 	    loop->parallel_p = false;
 	}
     }
-
   free (bbs);
 
   return NULL_TREE;
diff --git a/gcc/tree-data-ref.h b/gcc/tree-data-ref.h
index 8cf17ae8fb5..7d6f9f94cb4 100644
--- a/gcc/tree-data-ref.h
+++ b/gcc/tree-data-ref.h
@@ -269,6 +269,21 @@ DEF_VEC_ALLOC_P(ddr_p,heap);
 
 
 
+/* Describes a location of a memory reference.  */
+
+typedef struct data_ref_loc_d
+{
+  /* Position of the memory reference.  */
+  tree *pos;
+
+  /* True if the memory reference is read.  */
+  bool is_read;
+} data_ref_loc;
+
+DEF_VEC_O (data_ref_loc);
+DEF_VEC_ALLOC_O (data_ref_loc, heap);
+
+bool get_references_in_stmt (tree, VEC (data_ref_loc, heap) **);
 extern tree find_data_references_in_loop (struct loop *,
 					  VEC (data_reference_p, heap) **);
 extern void compute_data_dependences_for_loop (struct loop *, bool,
@@ -292,7 +307,6 @@ extern void free_dependence_relation (struct data_dependence_relation *);
 extern void free_dependence_relations (VEC (ddr_p, heap) *);
 extern void free_data_refs (VEC (data_reference_p, heap) *);
 extern struct data_reference *analyze_array (tree, tree, bool);
-extern void estimate_iters_using_array (tree, tree);
 
 
 /* Return the index of the variable VAR in the LOOP_NEST array.  */
diff --git a/gcc/tree-ssa-loop-niter.c b/gcc/tree-ssa-loop-niter.c
index e079dda2068..487a08d8dd6 100644
--- a/gcc/tree-ssa-loop-niter.c
+++ b/gcc/tree-ssa-loop-niter.c
@@ -1533,6 +1533,7 @@ derive_constant_upper_bound (tree val, tree additional)
   tree type = TREE_TYPE (val);
   tree op0, op1, subtype, maxt;
   double_int bnd, max, mmax, cst;
+  tree stmt;
 
   if (INTEGRAL_TYPE_P (type))
     maxt = TYPE_MAX_VALUE (type);
@@ -1647,39 +1648,113 @@ derive_constant_upper_bound (tree val, tree additional)
       bnd = derive_constant_upper_bound (op0, additional);
       return double_int_udiv (bnd, tree_to_double_int (op1), FLOOR_DIV_EXPR);
 
+    case BIT_AND_EXPR:
+      op1 = TREE_OPERAND (val, 1);
+      if (TREE_CODE (op1) != INTEGER_CST
+	  || tree_int_cst_sign_bit (op1))
+	return max;
+      return tree_to_double_int (op1);
+
+    case SSA_NAME:
+      stmt = SSA_NAME_DEF_STMT (val);
+      if (TREE_CODE (stmt) != MODIFY_EXPR
+	  || TREE_OPERAND (stmt, 0) != val)
+	return max;
+      return derive_constant_upper_bound (TREE_OPERAND (stmt, 1), additional);
+
     default: 
       return max;
     }
 }
 
-/* Records that AT_STMT is executed at most BOUND times in LOOP.  The
-   additional condition ADDITIONAL is recorded with the bound.  */
+/* Records that AT_STMT is executed at most BOUND + 1 times in LOOP.  The
+   additional condition ADDITIONAL is recorded with the bound.  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.
+   REALISTIC is true if the estimate comes from a reliable source
+   (number of iterations analysis, or size of data accessed in the loop).  */
 
-void
-record_estimate (struct loop *loop, tree bound, tree additional, tree at_stmt)
+static void
+record_estimate (struct loop *loop, tree bound, tree additional, tree at_stmt,
+		 bool is_exit, bool realistic)
 {
   struct nb_iter_bound *elt = xmalloc (sizeof (struct nb_iter_bound));
   double_int i_bound = derive_constant_upper_bound (bound, additional);
-  tree c_bound = double_int_to_tree (unsigned_type_for (TREE_TYPE (bound)),
-				     i_bound);
 
   if (dump_file && (dump_flags & TDF_DETAILS))
     {
-      fprintf (dump_file, "Statements after ");
+      fprintf (dump_file, "Statement %s", is_exit ? "(exit)" : "");
       print_generic_expr (dump_file, at_stmt, TDF_SLIM);
-      fprintf (dump_file, " are executed at most ");
+      fprintf (dump_file, " is executed at most ");
       print_generic_expr (dump_file, bound, TDF_SLIM);
       fprintf (dump_file, " (bounded by ");
-      print_generic_expr (dump_file, c_bound, TDF_SLIM);
-      fprintf (dump_file, ") times in loop %d.\n", loop->num);
+      dump_double_int (dump_file, i_bound, true);
+      fprintf (dump_file, ") + 1 times in loop %d.\n", loop->num);
     }
 
-  elt->bound = c_bound;
-  elt->at_stmt = at_stmt;
+  elt->bound = i_bound;
+  elt->stmt = at_stmt;
+  elt->is_exit = is_exit;
+  elt->realistic = realistic && TREE_CODE (bound) == INTEGER_CST;
   elt->next = loop->bounds;
   loop->bounds = elt;
 }
 
+/* Record the estimate on number of iterations of LOOP based on the fact that
+   the induction variable BASE + STEP * i evaluated in STMT does not wrap and
+   its values belong to the range <LOW, HIGH>.  DATA_SIZE_BOUNDS_P is true if
+   LOW and HIGH are derived from the size of data.  */
+
+static void
+record_nonwrapping_iv (struct loop *loop, tree base, tree step, tree stmt,
+		       tree low, tree high, bool data_size_bounds_p)
+{
+  tree niter_bound, extreme, delta;
+  tree type = TREE_TYPE (base), unsigned_type;
+
+  if (TREE_CODE (step) != INTEGER_CST || zero_p (step))
+    return;
+
+  if (dump_file && (dump_flags & TDF_DETAILS))
+    {
+      fprintf (dump_file, "Induction variable (");
+      print_generic_expr (dump_file, TREE_TYPE (base), TDF_SLIM);
+      fprintf (dump_file, ") ");
+      print_generic_expr (dump_file, base, TDF_SLIM);
+      fprintf (dump_file, " + ");
+      print_generic_expr (dump_file, step, TDF_SLIM);
+      fprintf (dump_file, " * iteration does not wrap in statement ");
+      print_generic_expr (dump_file, stmt, TDF_SLIM);
+      fprintf (dump_file, " in loop %d.\n", loop->num);
+    }
+
+  unsigned_type = unsigned_type_for (type);
+  base = fold_convert (unsigned_type, base);
+  step = fold_convert (unsigned_type, step);
+
+  if (tree_int_cst_sign_bit (step))
+    {
+      extreme = fold_convert (unsigned_type, low);
+      if (TREE_CODE (base) != INTEGER_CST)
+	base = fold_convert (unsigned_type, high);
+      delta = fold_build2 (MINUS_EXPR, unsigned_type, base, extreme);
+      step = fold_build1 (NEGATE_EXPR, unsigned_type, step);
+    }
+  else
+    {
+      extreme = fold_convert (unsigned_type, high);
+      if (TREE_CODE (base) != INTEGER_CST)
+	base = fold_convert (unsigned_type, low);
+      delta = fold_build2 (MINUS_EXPR, unsigned_type, extreme, base);
+    }
+
+  /* STMT is executed at most NITER_BOUND + 1 times, since otherwise the value
+     would get out of the range.  */
+  niter_bound = fold_build2 (FLOOR_DIV_EXPR, unsigned_type, delta, step);
+  record_estimate (loop, niter_bound, boolean_true_node, stmt,
+		   false, data_size_bounds_p);
+}
+
 /* Initialize LOOP->ESTIMATED_NB_ITERATIONS with the lowest safe
    approximation of the number of iterations for LOOP.  */
 
@@ -1687,20 +1762,184 @@ static void
 compute_estimated_nb_iterations (struct loop *loop)
 {
   struct nb_iter_bound *bound;
-  
+ 
+  gcc_assert (loop->estimate_state == EST_NOT_AVAILABLE);
+
   for (bound = loop->bounds; bound; bound = bound->next)
     {
-      if (TREE_CODE (bound->bound) != INTEGER_CST)
+      if (!bound->realistic)
 	continue;
 
       /* Update only when there is no previous estimation, or when the current
 	 estimation is smaller.  */
-      if (chrec_contains_undetermined (loop->estimated_nb_iterations)
-	  || tree_int_cst_lt (bound->bound, loop->estimated_nb_iterations))
-	loop->estimated_nb_iterations = bound->bound;
+      if (loop->estimate_state == EST_NOT_AVAILABLE
+	  || double_int_ucmp (bound->bound, loop->estimated_nb_iterations) < 0)
+	{
+	  loop->estimate_state = EST_AVAILABLE;
+	  loop->estimated_nb_iterations = bound->bound;
+	}
     }
 }
 
+/* Determine information about number of iterations a LOOP from the index
+   IDX of a data reference accessed in STMT.  Callback for for_each_index.  */
+
+struct ilb_data
+{
+  struct loop *loop;
+  tree stmt;
+};
+
+static bool
+idx_infer_loop_bounds (tree base, tree *idx, void *dta)
+{
+  struct ilb_data *data = dta;
+  tree ev, init, step;
+  tree low, high, type, next;
+  bool sign;
+  struct loop *loop = data->loop;
+
+  if (TREE_CODE (base) != ARRAY_REF)
+    return true;
+
+  ev = instantiate_parameters (loop, analyze_scalar_evolution (loop, *idx));
+  init = initial_condition (ev);
+  step = evolution_part_in_loop_num (ev, loop->num);
+
+  if (!init
+      || !step
+      || TREE_CODE (step) != INTEGER_CST
+      || zero_p (step)
+      || tree_contains_chrecs (init, NULL)
+      || chrec_contains_symbols_defined_in_loop (init, loop->num))
+    return true;
+
+  low = array_ref_low_bound (base);
+  high = array_ref_up_bound (base);
+  
+  /* The case of nonconstant bounds could be handled, but it would be
+     complicated.  */
+  if (TREE_CODE (low) != INTEGER_CST
+      || !high
+      || TREE_CODE (high) != INTEGER_CST)
+    return true;
+  sign = tree_int_cst_sign_bit (step);
+  type = TREE_TYPE (step);
+  
+  /* In case the relevant bound of the array does not fit in type, or
+     it does, but bound + step (in type) still belongs into the range of the
+     array, the index may wrap and still stay within the range of the array
+     (consider e.g. if the array is indexed by the full range of
+     unsigned char).
+
+     To make things simpler, we require both bounds to fit into type, although
+     there are cases where this would not be strightly necessary.  */
+  if (!int_fits_type_p (high, type)
+      || !int_fits_type_p (low, type))
+    return true;
+  low = fold_convert (type, low);
+  high = fold_convert (type, high);
+
+  if (sign)
+    next = fold_binary (PLUS_EXPR, type, low, step);
+  else
+    next = fold_binary (PLUS_EXPR, type, high, step);
+  
+  if (tree_int_cst_compare (low, next) <= 0
+      && tree_int_cst_compare (next, high) <= 0)
+    return true;
+
+  record_nonwrapping_iv (loop, init, step, data->stmt, low, high, true);
+  return true;
+}
+
+/* Determine information about number of iterations a LOOP from the bounds
+   of arrays in the data reference REF accessed in STMT.  */
+
+static void
+infer_loop_bounds_from_ref (struct loop *loop, tree stmt, tree ref)
+{
+  struct ilb_data data;
+
+  data.loop = loop;
+  data.stmt = stmt;
+  for_each_index (&ref, idx_infer_loop_bounds, &data);
+}
+
+/* Determine information about number of iterations of a LOOP from the way
+   arrays are used in STMT.  */
+
+static void
+infer_loop_bounds_from_array (struct loop *loop, tree stmt)
+{
+  tree call;
+
+  if (TREE_CODE (stmt) == MODIFY_EXPR)
+    {
+      tree op0 = TREE_OPERAND (stmt, 0);
+      tree op1 = TREE_OPERAND (stmt, 1);
+
+      /* For each memory access, analyze its access function
+	 and record a bound on the loop iteration domain.  */
+      if (REFERENCE_CLASS_P (op0))
+	infer_loop_bounds_from_ref (loop, stmt, op0);
+
+      if (REFERENCE_CLASS_P (op1))
+	infer_loop_bounds_from_ref (loop, stmt, op1);
+    }
+  
+  
+  call = get_call_expr_in (stmt);
+  if (call)
+    {
+      tree args;
+
+      for (args = TREE_OPERAND (call, 1); args; args = TREE_CHAIN (args))
+	if (REFERENCE_CLASS_P (TREE_VALUE (args)))
+	  infer_loop_bounds_from_ref (loop, stmt, TREE_VALUE (args));
+    }
+}
+
+/* Determine information about number of iterations of a LOOP from the fact
+   that signed arithmetics in STMT does not overflow.  */
+
+static void
+infer_loop_bounds_from_signedness (struct loop *loop, tree stmt)
+{
+  tree def, base, step, scev, type, low, high;
+
+  if (flag_wrapv || TREE_CODE (stmt) != MODIFY_EXPR)
+    return;
+
+  def = TREE_OPERAND (stmt, 0);
+
+  if (TREE_CODE (def) != SSA_NAME)
+    return;
+
+  type = TREE_TYPE (def);
+  if (!INTEGRAL_TYPE_P (type)
+      || TYPE_UNSIGNED (type))
+    return;
+
+  scev = instantiate_parameters (loop, analyze_scalar_evolution (loop, def));
+  if (chrec_contains_undetermined (scev))
+    return;
+
+  base = initial_condition_in_loop_num (scev, loop->num);
+  step = evolution_part_in_loop_num (scev, loop->num);
+
+  if (!base || !step
+      || TREE_CODE (step) != INTEGER_CST
+      || tree_contains_chrecs (base, NULL)
+      || chrec_contains_symbols_defined_in_loop (base, loop->num))
+    return;
+
+  low = lower_bound_in_type (type, type);
+  high = upper_bound_in_type (type, type);
+
+  record_nonwrapping_iv (loop, base, step, stmt, low, high, false);
+}
+
 /* The following analyzers are extracting informations on the bounds
    of LOOP from the following undefined behaviors:
 
@@ -1714,8 +1953,9 @@ static void
 infer_loop_bounds_from_undefined (struct loop *loop)
 {
   unsigned i;
-  basic_block bb, *bbs;
+  basic_block *bbs;
   block_stmt_iterator bsi;
+  basic_block bb;
   
   bbs = get_loop_body (loop);
 
@@ -1723,95 +1963,21 @@ infer_loop_bounds_from_undefined (struct loop *loop)
     {
       bb = bbs[i];
 
+      /* If BB is not executed in each iteration of the loop, we cannot
+	 use it to infer any information about # of iterations of the loop.  */
+      if (!dominated_by_p (CDI_DOMINATORS, loop->latch, bb))
+	continue;
+
       for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
-        {
+	{
 	  tree stmt = bsi_stmt (bsi);
 
-	  switch (TREE_CODE (stmt))
-	    {
-	    case MODIFY_EXPR:
-	      {
-		tree op0 = TREE_OPERAND (stmt, 0);
-		tree op1 = TREE_OPERAND (stmt, 1);
-
-		/* For each array access, analyze its access function
-		   and record a bound on the loop iteration domain.  */
-		if (TREE_CODE (op1) == ARRAY_REF 
-		    && !array_ref_contains_indirect_ref (op1))
-		  estimate_iters_using_array (stmt, op1);
-
-		if (TREE_CODE (op0) == ARRAY_REF 
-		    && !array_ref_contains_indirect_ref (op0))
-		  estimate_iters_using_array (stmt, op0);
-
-		/* For each signed type variable in LOOP, analyze its
-		   scalar evolution and record a bound of the loop
-		   based on the type's ranges.  */
-		else if (!flag_wrapv && TREE_CODE (op0) == SSA_NAME)
-		  {
-		    tree init, step, diff, estimation;
-		    tree scev = instantiate_parameters 
-		      (loop, analyze_scalar_evolution (loop, op0));
-		    tree type = chrec_type (scev);
-
-		    if (chrec_contains_undetermined (scev)
-			|| TYPE_UNSIGNED (type))
-		      break;
-
-		    init = initial_condition_in_loop_num (scev, loop->num);
-		    step = evolution_part_in_loop_num (scev, loop->num);
-
-		    if (init == NULL_TREE
-			|| step == NULL_TREE
-			|| TREE_CODE (init) != INTEGER_CST
-			|| TREE_CODE (step) != INTEGER_CST
-			|| TYPE_MIN_VALUE (type) == NULL_TREE
-			|| TYPE_MAX_VALUE (type) == NULL_TREE)
-		      break;
-
-		    if (integer_nonzerop (step))
-		      {
-			tree utype;
-
-			if (tree_int_cst_lt (step, integer_zero_node))
-			  diff = fold_build2 (MINUS_EXPR, type, init,
-					      TYPE_MIN_VALUE (type));
-			else
-			  diff = fold_build2 (MINUS_EXPR, type,
-					      TYPE_MAX_VALUE (type), init);
-
-			utype = unsigned_type_for (type);
-			estimation = fold_build2 (CEIL_DIV_EXPR, type, diff,
-						  step);
-			record_estimate (loop,
-					 fold_convert (utype, estimation),
-					 boolean_true_node, stmt);
-		      }
-		  }
-
-		break;
-	      }
-
-	    case CALL_EXPR:
-	      {
-		tree args;
-
-		for (args = TREE_OPERAND (stmt, 1); args;
-		     args = TREE_CHAIN (args))
-		  if (TREE_CODE (TREE_VALUE (args)) == ARRAY_REF
-		      && !array_ref_contains_indirect_ref (TREE_VALUE (args)))
-		    estimate_iters_using_array (stmt, TREE_VALUE (args));
-
-		break;
-	      }
-
-	    default:
-	      break;
-	    }
-	}
+	  infer_loop_bounds_from_array (loop, stmt);
+	  infer_loop_bounds_from_signedness (loop, stmt);
+  	}
+
     }
 
-  compute_estimated_nb_iterations (loop);
   free (bbs);
 }
 
@@ -1826,13 +1992,9 @@ estimate_numbers_of_iterations_loop (struct loop *loop)
   struct tree_niter_desc niter_desc;
 
   /* Give up if we already have tried to compute an estimation.  */
-  if (loop->estimated_nb_iterations == chrec_dont_know
-      /* Or when we already have an estimation.  */
-      || (loop->estimated_nb_iterations != NULL_TREE
-	  && TREE_CODE (loop->estimated_nb_iterations) == INTEGER_CST))
+  if (loop->estimate_state != EST_NOT_COMPUTED)
     return;
-  else
-    loop->estimated_nb_iterations = chrec_dont_know;
+  loop->estimate_state = EST_NOT_AVAILABLE;
 
   exits = get_loop_exit_edges (loop, &n_exits);
   for (i = 0; i < n_exits; i++)
@@ -1842,19 +2004,19 @@ estimate_numbers_of_iterations_loop (struct loop *loop)
 
       niter = niter_desc.niter;
       type = TREE_TYPE (niter);
-      if (!zero_p (niter_desc.may_be_zero)
-	  && !nonzero_p (niter_desc.may_be_zero))
+      if (TREE_CODE (niter_desc.may_be_zero) != INTEGER_CST)
 	niter = build3 (COND_EXPR, type, niter_desc.may_be_zero,
 			build_int_cst (type, 0),
 			niter);
       record_estimate (loop, niter,
 		       niter_desc.additional_info,
-		       last_stmt (exits[i]->src));
+		       last_stmt (exits[i]->src),
+		       true, true);
     }
   free (exits);
   
-  if (chrec_contains_undetermined (loop->estimated_nb_iterations))
-    infer_loop_bounds_from_undefined (loop);
+  infer_loop_bounds_from_undefined (loop);
+  compute_estimated_nb_iterations (loop);
 }
 
 /* Records estimates on numbers of iterations of LOOPS.  */
@@ -1899,40 +2061,67 @@ stmt_dominates_stmt_p (tree s1, tree s2)
 }
 
 /* Returns true when we can prove that the number of executions of
-   STMT in the loop is at most NITER, according to the fact
-   that the statement NITER_BOUND->at_stmt is executed at most
-   NITER_BOUND->bound times.  */
+   STMT in the loop is at most NITER, according to the bound on
+   the number of executions of the statement NITER_BOUND->stmt recorded in
+   NITER_BOUND.  If STMT is NULL, we must prove this bound for all
+   statements in the loop.  */
 
 static bool
 n_of_executions_at_most (tree stmt,
 			 struct nb_iter_bound *niter_bound, 
 			 tree niter)
 {
-  tree cond;
-  tree bound = niter_bound->bound;
-  tree bound_type = TREE_TYPE (bound);
+  double_int bound = niter_bound->bound;
   tree nit_type = TREE_TYPE (niter);
   enum tree_code cmp;
 
-  gcc_assert (TYPE_UNSIGNED (bound_type)
-	      && TYPE_UNSIGNED (nit_type)
-	      && is_gimple_min_invariant (bound));
-  if (TYPE_PRECISION (nit_type) > TYPE_PRECISION (bound_type))
-    bound = fold_convert (nit_type, bound);
-  else
-    niter = fold_convert (bound_type, niter);
-
-  /* After the statement niter_bound->at_stmt we know that anything is
-     executed at most BOUND times.  */
-  if (stmt && stmt_dominates_stmt_p (niter_bound->at_stmt, stmt))
-    cmp = GE_EXPR;
-  /* Before the statement niter_bound->at_stmt we know that anything
-     is executed at most BOUND + 1 times.  */
+  gcc_assert (TYPE_UNSIGNED (nit_type));
+
+  /* If the bound does not even fit into NIT_TYPE, it cannot tell us that
+     the number of iterations is small.  */
+  if (!double_int_fits_to_tree_p (nit_type, bound))
+    return false;
+
+  /* We know that NITER_BOUND->stmt is executed at most NITER_BOUND->bound + 1
+     times.  This means that:
+     
+     -- if NITER_BOUND->is_exit is true, then everything before
+        NITER_BOUND->stmt is executed at most NITER_BOUND->bound + 1
+	times, and everyting after it at most NITER_BOUND->bound times.
+
+     -- If NITER_BOUND->is_exit is false, then if we can prove that when STMT
+	is executed, then NITER_BOUND->stmt is executed as well in the same
+	iteration (we conclude that if both statements belong to the same
+	basic block, or if STMT is after NITER_BOUND->stmt), then STMT
+	is executed at most NITER_BOUND->bound + 1 times.  Otherwise STMT is
+	executed at most NITER_BOUND->bound + 2 times.  */
+
+  if (niter_bound->is_exit)
+    {
+      if (stmt
+	  && stmt != niter_bound->stmt
+	  && stmt_dominates_stmt_p (niter_bound->stmt, stmt))
+	cmp = GE_EXPR;
+      else
+	cmp = GT_EXPR;
+    }
   else
-    cmp = GT_EXPR;
+    {
+      if (!stmt
+	  || (bb_for_stmt (stmt) != bb_for_stmt (niter_bound->stmt)
+	      && !stmt_dominates_stmt_p (niter_bound->stmt, stmt)))
+	{
+	  bound = double_int_add (bound, double_int_one);
+	  if (double_int_zero_p (bound)
+	      || !double_int_fits_to_tree_p (nit_type, bound))
+	    return false;
+	}
+      cmp = GT_EXPR;
+    }
 
-  cond = fold_binary (cmp, boolean_type_node, niter, bound);
-  return nonzero_p (cond);
+  return nonzero_p (fold_binary (cmp, boolean_type_node,
+				 niter,
+				 double_int_to_tree (nit_type, bound)));
 }
 
 /* Returns true if the arithmetics in TYPE can be assumed not to wrap.  */
@@ -2042,7 +2231,7 @@ free_numbers_of_iterations_estimates_loop (struct loop *loop)
   struct nb_iter_bound *bound, *next;
 
   loop->nb_iterations = NULL;
-  loop->estimated_nb_iterations = NULL;
+  loop->estimate_state = EST_NOT_COMPUTED;
   for (bound = loop->bounds; bound; bound = next)
     {
       next = bound->next;
@@ -2075,6 +2264,4 @@ void
 substitute_in_loop_info (struct loop *loop, tree name, tree val)
 {
   loop->nb_iterations = simplify_replace_tree (loop->nb_iterations, name, val);
-  loop->estimated_nb_iterations
-	  = simplify_replace_tree (loop->estimated_nb_iterations, name, val);
 }