[patch] Fix estimate number of iterations

[Sebastian Pop]

Hi,
here is a patch for restricting the computation of loop bounds to
arrays not contained in structs.

Another correction to the bound estimation is that we have to check
that the array is accessed without surrounding conditions: for
example, in the following case it is not possible to determine a bound
for the loop:

int A[10];
for (i = 0; i < some_param; i++)
  if (foo ())
    A[i] = ...

Bootstrapped and tested on {i686,x68_64}-linux.  Ok?

	* tree-cfg.c (already_visited_bb, bb_executed_unconditionally_1,
	bb_executed_unconditionally_p, stmt_executed_unconditionally_p): New.
	* tree-data-ref.c (analyze_array_indexes): Don't invoke
	estimate_niter_from_size_of_data on arrays in structs.
	* tree-flow.h (stmt_executed_unconditionally_p): Declared.
	* tree-ssa-loop-niter.c (compute_estimated_nb_iterations): Don't
	use loop bounds that are executed conditionally in the loop.

Index: tree-cfg.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-cfg.c,v
retrieving revision 2.221
diff -d -u -p -r2.221 tree-cfg.c
--- tree-cfg.c	13 Sep 2005 07:33:49 -0000	2.221
+++ tree-cfg.c	19 Sep 2005 19:51:36 -0000
@@ -4418,6 +4418,72 @@ tree_duplicate_sese_region (edge entry, 
   return true;
 }
 
+static bitmap already_visited_bb;
+
+/* Return true when BB is executed independently of any condition.  */
+
+static bool
+bb_executed_unconditionally_1 (struct loop *loop, basic_block bb)
+{
+  edge e;
+  edge_iterator ei;
+
+  if (bitmap_bit_p (already_visited_bb, bb->index))
+    return true;
+  else
+    bitmap_set_bit (already_visited_bb, bb->index);
+
+  /* Scan over predecessors.  */
+  FOR_EACH_EDGE (e, ei, bb->preds)
+    {
+      basic_block predecessor = e->src;
+      tree last;
+
+      /* When LOOP has a single exit, don't include the exit condition.  */
+      if ((loop->single_exit && predecessor == loop->single_exit->src)
+	  /* Stop at loop's header.  */
+	  || predecessor == loop->header
+	  /* Don't record conditions that don't belong to LOOP.  */
+	  || predecessor->loop_father != loop)
+	continue;
+
+      last = last_stmt (predecessor);
+      if (last && TREE_CODE (last) == COND_EXPR)
+	return false;
+
+      /* Scan predecessors of predecessor.  */
+      if (bb_executed_unconditionally_1 (loop, predecessor) == false)
+	return false;
+    }
+
+  return true;
+}
+
+/* Return true when BB is executed independently of any condition.  */
+
+static bool
+bb_executed_unconditionally_p (basic_block bb)
+{
+  bool res;
+
+  already_visited_bb = BITMAP_ALLOC (NULL);
+  res = bb_executed_unconditionally_1 (bb->loop_father, bb);
+  BITMAP_FREE (already_visited_bb);
+
+  return res;
+}
+
+/* Return true if STMT is executed independently of any condition.  */
+
+bool
+stmt_executed_unconditionally_p (tree stmt)
+{
+  /* Another less efficient implementation is:
+     return (stmt_executed_under_condition (stmt) == boolean_true_node);
+     that would construct the condition, whereas it is possible to cut
+     the search after finding the first condition.  */
+  return bb_executed_unconditionally_p (bb_for_stmt (stmt));
+}
 
 /* Dump FUNCTION_DECL FN to file FILE using FLAGS (see TDF_* in tree.h)  */
 
Index: tree-data-ref.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-data-ref.c,v
retrieving revision 2.42
diff -d -u -p -r2.42 tree-data-ref.c
--- tree-data-ref.c	15 Sep 2005 17:21:48 -0000	2.42
+++ tree-data-ref.c	19 Sep 2005 19:51:36 -0000
@@ -823,8 +823,13 @@ analyze_array_indexes (struct loop *loop
   access_fn = instantiate_parameters 
     (loop, analyze_scalar_evolution (loop, opnd1));
 
-  if (chrec_contains_undetermined (loop->estimated_nb_iterations))
-    estimate_niter_from_size_of_data (loop, opnd0, access_fn, stmt);
+  /* FIXME: see http://gcc.gnu.org/ml/gcc/2005-09/msg00597.html.
+     Estimation of loop bounds should be extended to also work on
+     arrays in structures once we have the infrastructure for
+     estimating the max size of structs.  */
+  if (TREE_CODE (opnd0) == VAR_DECL)
+    if (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);
Index: tree-flow.h
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-flow.h,v
retrieving revision 2.135
diff -d -u -p -r2.135 tree-flow.h
--- tree-flow.h	19 Sep 2005 09:02:23 -0000	2.135
+++ tree-flow.h	19 Sep 2005 19:51:36 -0000
@@ -559,6 +559,7 @@ extern void fold_cond_expr_cond (void);
 extern void replace_uses_by (tree, tree);
 extern void start_recording_case_labels (void);
 extern void end_recording_case_labels (void);
+extern bool stmt_executed_unconditionally_p (tree);
 
 /* In tree-cfgcleanup.c  */
 extern bool cleanup_tree_cfg (void);
Index: tree-ssa-loop-niter.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-ssa-loop-niter.c,v
retrieving revision 2.43
diff -d -u -p -r2.43 tree-ssa-loop-niter.c
--- tree-ssa-loop-niter.c	15 Sep 2005 17:21:48 -0000	2.43
+++ tree-ssa-loop-niter.c	19 Sep 2005 19:51:36 -0000
@@ -1391,9 +1391,11 @@ compute_estimated_nb_iterations (struct 
   
   for (bound = loop->bounds; bound; bound = bound->next)
     if (TREE_CODE (bound->bound) == INTEGER_CST
-	/* Update only when there is no previous estimation.  */
+	/* Update only when the current bound is executed unconditionally,  */
+	&& bound->at_stmt && stmt_executed_unconditionally_p (bound->at_stmt)
+	/* and when there is no previous estimation,  */
 	&& (chrec_contains_undetermined (loop->estimated_nb_iterations)
-	    /* Or when the current estimation is smaller.  */
+	    /* or when the current estimation is smaller.  */
 	    || tree_int_cst_lt (bound->bound, loop->estimated_nb_iterations)))
       loop->estimated_nb_iterations = bound->bound;
 }