--- a/gcc/tree-scalar-evolution.c	Tue May 25 18:58:51 2010 +0900
+++ b/gcc/tree-scalar-evolution.c	Tue Mar 22 17:18:12 2011 +0900
@@ -257,21 +257,12 @@
 #include "config.h"
 #include "system.h"
 #include "coretypes.h"
-#include "tm.h"
-#include "ggc.h"
-#include "tree.h"
-#include "basic-block.h"
-#include "diagnostic.h"
-#include "tree-pretty-print.h"
 #include "gimple-pretty-print.h"
 #include "tree-flow.h"
-#include "tree-dump.h"
-#include "timevar.h"
 #include "cfgloop.h"
 #include "tree-chrec.h"
 #include "tree-scalar-evolution.h"
 #include "tree-pass.h"
-#include "flags.h"
 #include "params.h"
 
 static tree analyze_scalar_evolution_1 (struct loop *, tree, tree);
@@ -315,7 +306,7 @@
 {
   struct scev_info_str *res;
 
-  res = GGC_NEW (struct scev_info_str);
+  res = ggc_alloc_scev_info_str ();
   res->var = var;
   res->chrec = chrec_not_analyzed_yet;
   res->instantiated_below = instantiated_below;
@@ -386,19 +377,17 @@
   if (is_gimple_min_invariant (chrec))
     return false;
 
-  if (TREE_CODE (chrec) == VAR_DECL
-      || TREE_CODE (chrec) == PARM_DECL
-      || TREE_CODE (chrec) == FUNCTION_DECL
-      || TREE_CODE (chrec) == LABEL_DECL
-      || TREE_CODE (chrec) == RESULT_DECL
-      || TREE_CODE (chrec) == FIELD_DECL)
-    return true;
-
   if (TREE_CODE (chrec) == SSA_NAME)
     {
-      gimple def = SSA_NAME_DEF_STMT (chrec);
-      struct loop *def_loop = loop_containing_stmt (def);
-      struct loop *loop = get_loop (loop_nb);
+      gimple def;
+      loop_p def_loop, loop;
+
+      if (SSA_NAME_IS_DEFAULT_DEF (chrec))
+	return false;
+
+      def = SSA_NAME_DEF_STMT (chrec);
+      def_loop = loop_containing_stmt (def);
+      loop = get_loop (loop_nb);
 
       if (def_loop == NULL)
 	return false;
@@ -900,23 +889,6 @@
   return res;
 }
 
-/* Helper function.  */
-
-static inline tree
-set_nb_iterations_in_loop (struct loop *loop,
-			   tree res)
-{
-  if (dump_file && (dump_flags & TDF_DETAILS))
-    {
-      fprintf (dump_file, "  (set_nb_iterations_in_loop = ");
-      print_generic_expr (dump_file, res, 0);
-      fprintf (dump_file, "))\n");
-    }
-
-  loop->nb_iterations = res;
-  return res;
-}
-
 
 
 /* This section selects the loops that will be good candidates for the
@@ -1188,6 +1160,24 @@
 				    halting_phi, evolution_of_loop, limit);
       break;
 
+    case ADDR_EXPR:
+      /* Handle &MEM[ptr + CST] which is equivalent to POINTER_PLUS_EXPR.  */
+      if (TREE_CODE (TREE_OPERAND (expr, 0)) == MEM_REF)
+	{
+	  expr = TREE_OPERAND (expr, 0);
+	  rhs0 = TREE_OPERAND (expr, 0);
+	  rhs1 = TREE_OPERAND (expr, 1);
+	  type = TREE_TYPE (rhs0);
+	  STRIP_USELESS_TYPE_CONVERSION (rhs0);
+	  STRIP_USELESS_TYPE_CONVERSION (rhs1);
+	  res = follow_ssa_edge_binary (loop, at_stmt, type,
+					rhs0, POINTER_PLUS_EXPR, rhs1,
+					halting_phi, evolution_of_loop, limit);
+	}
+      else
+	res = t_false;
+      break;
+
     case ASSERT_EXPR:
       /* This assignment is of the form: "a_1 = ASSERT_EXPR <a_2, ...>"
 	 It must be handled as a copy assignment of the form a_1 = a_2.  */
@@ -1409,7 +1399,7 @@
     return t_false;
 
   /* Give up if the path is longer than the MAX that we allow.  */
-  if (limit > PARAM_VALUE (PARAM_SCEV_MAX_EXPR_SIZE))
+  if (limit > PARAM_VALUE (PARAM_SCEV_MAX_EXPR_COMPLEXITY))
     return t_dont_know;
 
   def_loop = loop_containing_stmt (def);
@@ -1717,12 +1707,22 @@
 	  return chrec_convert (type, analyze_scalar_evolution (loop, rhs1),
 				at_stmt);
 	}
-
-      return chrec_dont_know;
     }
 
   switch (code)
     {
+    case ADDR_EXPR:
+      /* Handle &MEM[ptr + CST] which is equivalent to POINTER_PLUS_EXPR.  */
+      if (TREE_CODE (TREE_OPERAND (rhs1, 0)) != MEM_REF)
+	{
+	  res = chrec_dont_know;
+	  break;
+	}
+
+      rhs2 = TREE_OPERAND (TREE_OPERAND (rhs1, 0), 1);
+      rhs1 = TREE_OPERAND (TREE_OPERAND (rhs1, 0), 0);
+      /* Fall through.  */
+
     case POINTER_PLUS_EXPR:
       chrec1 = analyze_scalar_evolution (loop, rhs1);
       chrec2 = analyze_scalar_evolution (loop, rhs2);
@@ -1834,13 +1834,18 @@
 				  struct loop *def_loop,
 				  tree ev)
 {
+  bool val;
   tree res;
+
   if (def_loop == wrto_loop)
     return ev;
 
   def_loop = superloop_at_depth (def_loop, loop_depth (wrto_loop) + 1);
   res = compute_overall_effect_of_inner_loop (def_loop, ev);
 
+  if (no_evolution_in_loop_p (res, wrto_loop->num, &val) && val)
+    return res;
+
   return analyze_scalar_evolution_1 (wrto_loop, res, chrec_not_analyzed_yet);
 }
 
@@ -2179,20 +2184,34 @@
      result again.  */
   res = analyze_scalar_evolution (def_loop, chrec);
 
-  /* Don't instantiate loop-closed-ssa phi nodes.  */
+  /* Don't instantiate default definitions.  */
   if (TREE_CODE (res) == SSA_NAME
-      && (loop_containing_stmt (SSA_NAME_DEF_STMT (res)) == NULL
-	  || (loop_depth (loop_containing_stmt (SSA_NAME_DEF_STMT (res)))
-	      > loop_depth (def_loop))))
+      && SSA_NAME_IS_DEFAULT_DEF (res))
+    ;
+
+  /* Don't instantiate loop-closed-ssa phi nodes.  */
+  else if (TREE_CODE (res) == SSA_NAME
+	   && loop_depth (loop_containing_stmt (SSA_NAME_DEF_STMT (res)))
+	   > loop_depth (def_loop))
     {
       if (res == chrec)
 	res = loop_closed_phi_def (chrec);
       else
 	res = chrec;
 
-      if (res == NULL_TREE
-	  || !dominated_by_p (CDI_DOMINATORS, instantiate_below,
-			      gimple_bb (SSA_NAME_DEF_STMT (res))))
+      /* When there is no loop_closed_phi_def, it means that the
+	 variable is not used after the loop: try to still compute the
+	 value of the variable when exiting the loop.  */
+      if (res == NULL_TREE)
+	{
+	  loop_p loop = loop_containing_stmt (SSA_NAME_DEF_STMT (chrec));
+	  res = analyze_scalar_evolution (loop, chrec);
+	  res = compute_overall_effect_of_inner_loop (loop, res);
+	  res = instantiate_scev_r (instantiate_below, evolution_loop, res,
+				    fold_conversions, cache, size_expr);
+	}
+      else if (!dominated_by_p (CDI_DOMINATORS, instantiate_below,
+				gimple_bb (SSA_NAME_DEF_STMT (res))))
 	res = chrec_dont_know;
     }
 
@@ -2203,7 +2222,6 @@
   /* Store the correct value to the cache.  */
   set_instantiated_value (cache, instantiate_below, chrec, res);
   return res;
-
 }
 
 /* Analyze all the parameters of the chrec, between INSTANTIATE_BELOW
@@ -2321,6 +2339,41 @@
 /* Analyze all the parameters of the chrec, between INSTANTIATE_BELOW
    and EVOLUTION_LOOP, that were left under a symbolic form.
 
+   "CHREC" is an array reference to be instantiated.
+
+   CACHE is the cache of already instantiated values.
+
+   FOLD_CONVERSIONS should be set to true when the conversions that
+   may wrap in signed/pointer type are folded, as long as the value of
+   the chrec is preserved.
+
+   SIZE_EXPR is used for computing the size of the expression to be
+   instantiated, and to stop if it exceeds some limit.  */
+
+static tree
+instantiate_array_ref (basic_block instantiate_below,
+		       struct loop *evolution_loop, tree chrec,
+		       bool fold_conversions, htab_t cache, int size_expr)
+{
+  tree res;
+  tree index = TREE_OPERAND (chrec, 1);
+  tree op1 = instantiate_scev_r (instantiate_below, evolution_loop, index,
+				 fold_conversions, cache, size_expr);
+
+  if (op1 == chrec_dont_know)
+    return chrec_dont_know;
+
+  if (chrec && op1 == index)
+    return chrec;
+
+  res = unshare_expr (chrec);
+  TREE_OPERAND (res, 1) = op1;
+  return res;
+}
+
+/* Analyze all the parameters of the chrec, between INSTANTIATE_BELOW
+   and EVOLUTION_LOOP, that were left under a symbolic form.
+
    "CHREC" that stands for a convert expression "(TYPE) OP" is to be
    instantiated.
 
@@ -2555,7 +2608,8 @@
   if (size_expr++ > PARAM_VALUE (PARAM_SCEV_MAX_EXPR_SIZE))
     return chrec_dont_know;
 
-  if (automatically_generated_chrec_p (chrec)
+  if (chrec == NULL_TREE
+      || automatically_generated_chrec_p (chrec)
       || is_gimple_min_invariant (chrec))
     return chrec;
 
@@ -2597,6 +2651,10 @@
     case SCEV_KNOWN:
       return chrec_known;
 
+    case ARRAY_REF:
+      return instantiate_array_ref (instantiate_below, evolution_loop, chrec,
+				    fold_conversions, cache, size_expr);
+
     default:
       break;
     }
@@ -2685,8 +2743,11 @@
 /* Entry point for the analysis of the number of iterations pass.
    This function tries to safely approximate the number of iterations
    the loop will run.  When this property is not decidable at compile
-   time, the result is chrec_dont_know.  Otherwise the result is
-   a scalar or a symbolic parameter.
+   time, the result is chrec_dont_know.  Otherwise the result is a
+   scalar or a symbolic parameter.  When the number of iterations may
+   be equal to zero and the property cannot be determined at compile
+   time, the result is a COND_EXPR that represents in a symbolic form
+   the conditions under which the number of iterations is not zero.
 
    Example of analysis: suppose that the loop has an exit condition:
 
@@ -2705,37 +2766,53 @@
 tree
 number_of_latch_executions (struct loop *loop)
 {
-  tree res, type;
   edge exit;
   struct tree_niter_desc niter_desc;
-
-  /* Determine whether the number_of_iterations_in_loop has already
+  tree may_be_zero;
+  tree res;
+
+  /* Determine whether the number of iterations in loop has already
      been computed.  */
   res = loop->nb_iterations;
   if (res)
     return res;
-  res = chrec_dont_know;
+
+  may_be_zero = NULL_TREE;
 
   if (dump_file && (dump_flags & TDF_DETAILS))
-    fprintf (dump_file, "(number_of_iterations_in_loop\n");
-
+    fprintf (dump_file, "(number_of_iterations_in_loop = \n");
+
+  res = chrec_dont_know;
   exit = single_exit (loop);
-  if (!exit)
-    goto end;
-
-  if (!number_of_iterations_exit (loop, exit, &niter_desc, false))
-    goto end;
-
-  type = TREE_TYPE (niter_desc.niter);
-  if (integer_nonzerop (niter_desc.may_be_zero))
-    res = build_int_cst (type, 0);
-  else if (integer_zerop (niter_desc.may_be_zero))
-    res = niter_desc.niter;
+
+  if (exit && number_of_iterations_exit (loop, exit, &niter_desc, false))
+    {
+      may_be_zero = niter_desc.may_be_zero;
+      res = niter_desc.niter;
+    }
+
+  if (res == chrec_dont_know
+      || !may_be_zero
+      || integer_zerop (may_be_zero))
+    ;
+  else if (integer_nonzerop (may_be_zero))
+    res = build_int_cst (TREE_TYPE (res), 0);
+
+  else if (COMPARISON_CLASS_P (may_be_zero))
+    res = fold_build3 (COND_EXPR, TREE_TYPE (res), may_be_zero,
+		       build_int_cst (TREE_TYPE (res), 0), res);
   else
     res = chrec_dont_know;
 
-end:
-  return set_nb_iterations_in_loop (loop, res);
+  if (dump_file && (dump_flags & TDF_DETAILS))
+    {
+      fprintf (dump_file, "  (set_nb_iterations_in_loop = ");
+      print_generic_expr (dump_file, res, 0);
+      fprintf (dump_file, "))\n");
+    }
+
+  loop->nb_iterations = res;
+  return res;
 }
 
 /* Returns the number of executions of the exit condition of LOOP,
@@ -2777,7 +2854,7 @@
   unsigned nb_static_loops = 0;
   gimple cond;
 
-  for (i = 0; VEC_iterate (gimple, *exit_conditions, i, cond); i++)
+  FOR_EACH_VEC_ELT (gimple, *exit_conditions, i, cond)
     {
       tree res = number_of_latch_executions (loop_containing_stmt (cond));
       if (chrec_contains_undetermined (res))
@@ -2931,7 +3008,7 @@
 
   reset_chrecs_counters (&stats);
 
-  for (i = 0; VEC_iterate (gimple, *exit_conditions, i, cond); i++)
+  FOR_EACH_VEC_ELT (gimple, *exit_conditions, i, cond)
     {
       struct loop *loop;
       basic_block bb;
@@ -3016,12 +3093,9 @@
   loop_iterator li;
   struct loop *loop;
 
-  scalar_evolution_info = htab_create_alloc (100,
-					     hash_scev_info,
-					     eq_scev_info,
-					     del_scev_info,
-					     ggc_calloc,
-					     ggc_free);
+
+  scalar_evolution_info = htab_create_ggc (100, hash_scev_info, eq_scev_info,
+					   del_scev_info);
 
   initialize_scalar_evolutions_analyzer ();