* loop-unswitch.c (unswitch_single_loop): Use

	estimated_loop_iterations_int to prevent unswitching when loop
	is known to not roll.
	* tree-ssa-loop-niter.c (estimated_loop_iterations): Do not segfault
	when SCEV is not initialized.
	(max_loop_iterations): Likewise.
	* tree-ssa-loop-unswitch.c (tree_ssa_unswitch_loops): Use
	estimated_loop_iterations_int to prevent unswithcing when
	loop is known to not roll.
	* tree-scalar-evolution.c (scev_initialized_p): New function.
	* tree-scalar-evolution.h (scev_initialized_p): Likewise.
	* loop-unroll.c (decide_peel_once_rolling): Use
	max_loop_iterations_int.
	(unroll_loop_constant_iterations): Update
	nb_iterations_upper_bound and nb_iterations_estimate.
	(decide_unroll_runtime_iterations): Use
	estimated_loop_iterations or max_loop_iterations;
	(unroll_loop_runtime_iterations): fix profile updating.
	(decide_peel_simple): Use estimated_loop_iterations
	and max_loop_iterations.
	(decide_unroll_stupid): Use estimated_loop_iterations
	ad max_loop_iterations.
	* loop-doloop.c (doloop_modify): Use max_loop_iterations_int.
	(doloop_optimize): Likewise.
	* loop-iv.c (iv_number_of_iterations): Use record_niter_bound.
	(find_simple_exit): Likewise.
	* cfgloop.h (struct niter_desc): Remove niter_max.


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

10 files changed, 173 insertions, 46 deletions

diff --git a/gcc/ChangeLog b/gcc/ChangeLog
index b7e0a64be80..ba74c1bbc1f 100644
--- a/gcc/ChangeLog
+++ b/gcc/ChangeLog
@@ -1,3 +1,33 @@
+2012-10-08  Jan Hubicka  <jh@suse.cz>
+
+	* loop-unswitch.c (unswitch_single_loop): Use
+	estimated_loop_iterations_int to prevent unswitching when loop
+	is known to not roll.
+	* tree-ssa-loop-niter.c (estimated_loop_iterations): Do not segfault
+	when SCEV is not initialized.
+	(max_loop_iterations): Likewise.
+	* tree-ssa-loop-unswitch.c (tree_ssa_unswitch_loops): Use
+	estimated_loop_iterations_int to prevent unswithcing when
+	loop is known to not roll.
+	* tree-scalar-evolution.c (scev_initialized_p): New function.
+	* tree-scalar-evolution.h (scev_initialized_p): Likewise.
+	* loop-unroll.c (decide_peel_once_rolling): Use
+	max_loop_iterations_int.
+	(unroll_loop_constant_iterations): Update
+	nb_iterations_upper_bound and nb_iterations_estimate.
+	(decide_unroll_runtime_iterations): Use
+	estimated_loop_iterations or max_loop_iterations;
+	(unroll_loop_runtime_iterations): fix profile updating.
+	(decide_peel_simple): Use estimated_loop_iterations
+	and max_loop_iterations.
+	(decide_unroll_stupid): Use estimated_loop_iterations
+	ad max_loop_iterations.
+	* loop-doloop.c (doloop_modify): Use max_loop_iterations_int.
+	(doloop_optimize): Likewise.
+	* loop-iv.c (iv_number_of_iterations): Use record_niter_bound.
+	(find_simple_exit): Likewise.
+	* cfgloop.h (struct niter_desc): Remove niter_max.
+
 2012-10-08  Marek Polacek  <polacek@redhat.com>
 
 	PR debug/54831
diff --git a/gcc/cfgloop.h b/gcc/cfgloop.h
index e0a370f32bf..9d7b784174d 100644
--- a/gcc/cfgloop.h
+++ b/gcc/cfgloop.h
@@ -386,9 +386,6 @@ struct niter_desc
   /* Number of iterations if constant.  */
   unsigned HOST_WIDEST_INT niter;
 
-  /* Upper bound on the number of iterations.  */
-  unsigned HOST_WIDEST_INT niter_max;
-
   /* Assumptions under that the rest of the information is valid.  */
   rtx assumptions;
 
diff --git a/gcc/loop-doloop.c b/gcc/loop-doloop.c
index 39e6ca92734..8dcfea5bba8 100644
--- a/gcc/loop-doloop.c
+++ b/gcc/loop-doloop.c
@@ -410,6 +410,7 @@ doloop_modify (struct loop *loop, struct niter_desc *desc,
   basic_block loop_end = desc->out_edge->src;
   enum machine_mode mode;
   rtx true_prob_val;
+  double_int iterations;
 
   jump_insn = BB_END (loop_end);
 
@@ -460,9 +461,10 @@ doloop_modify (struct loop *loop, struct niter_desc *desc,
 
       /* Determine if the iteration counter will be non-negative.
 	 Note that the maximum value loaded is iterations_max - 1.  */
-      if (desc->niter_max
-	  <= ((unsigned HOST_WIDEST_INT) 1
-	      << (GET_MODE_PRECISION (mode) - 1)))
+      if (max_loop_iterations (loop, &iterations)
+	  && (iterations.ule (double_int_one.llshift
+			       (GET_MODE_PRECISION (mode) - 1,
+				GET_MODE_PRECISION (mode)))))
 	nonneg = 1;
       break;
 
@@ -548,9 +550,17 @@ doloop_modify (struct loop *loop, struct niter_desc *desc,
   {
     rtx init;
     unsigned level = get_loop_level (loop) + 1;
+    double_int iter;
+    rtx iter_rtx;
+
+    if (!max_loop_iterations (loop, &iter)
+	|| !iter.fits_shwi ())
+      iter_rtx = const0_rtx;
+    else
+      iter_rtx = GEN_INT (iter.to_shwi());
     init = gen_doloop_begin (counter_reg,
 			     desc->const_iter ? desc->niter_expr : const0_rtx,
-			     GEN_INT (desc->niter_max),
+			     iter_rtx,
 			     GEN_INT (level));
     if (init)
       {
@@ -608,6 +618,7 @@ doloop_optimize (struct loop *loop)
   struct niter_desc *desc;
   unsigned word_mode_size;
   unsigned HOST_WIDE_INT word_mode_max;
+  double_int iter;
 
   if (dump_file)
     fprintf (dump_file, "Doloop: Processing loop %d.\n", loop->num);
@@ -658,7 +669,11 @@ doloop_optimize (struct loop *loop)
 
   count = copy_rtx (desc->niter_expr);
   iterations = desc->const_iter ? desc->niter_expr : const0_rtx;
-  iterations_max = GEN_INT (desc->niter_max);
+  if (!max_loop_iterations (loop, &iter)
+      || !iter.fits_shwi ())
+    iterations_max = const0_rtx;
+  else
+    iterations_max = GEN_INT (iter.to_shwi());
   level = get_loop_level (loop) + 1;
 
   /* Generate looping insn.  If the pattern FAILs then give up trying
@@ -678,7 +693,7 @@ doloop_optimize (struct loop *loop)
 	 computed, we must be sure that the number of iterations fits into
 	 the new mode.  */
       && (word_mode_size >= GET_MODE_PRECISION (mode)
-	  || desc->niter_max <= word_mode_max))
+	  || iter.ule (double_int::from_shwi (word_mode_max))))
     {
       if (word_mode_size > GET_MODE_PRECISION (mode))
 	{
diff --git a/gcc/loop-iv.c b/gcc/loop-iv.c
index e5c72596a32..658f20360f7 100644
--- a/gcc/loop-iv.c
+++ b/gcc/loop-iv.c
@@ -2294,10 +2294,6 @@ iv_number_of_iterations (struct loop *loop, rtx insn, rtx condition,
 
   desc->const_iter = false;
   desc->niter_expr = NULL_RTX;
-  desc->niter_max = 0;
-  if (loop->any_upper_bound
-      && loop->nb_iterations_upper_bound.fits_uhwi ())
-    desc->niter_max = loop->nb_iterations_upper_bound.low;
 
   cond = GET_CODE (condition);
   gcc_assert (COMPARISON_P (condition));
@@ -2567,9 +2563,8 @@ iv_number_of_iterations (struct loop *loop, rtx insn, rtx condition,
 			 ? iv0.base
 			 : mode_mmin);
 	  max = (up - down) / inc + 1;
-	  if (!desc->niter_max
-	      || max < desc->niter_max)
-	    desc->niter_max = max;
+	  record_niter_bound (loop, double_int::from_shwi (max),
+			      false, true);
 
 	  if (iv0.step == const0_rtx)
 	    {
@@ -2780,14 +2775,16 @@ iv_number_of_iterations (struct loop *loop, rtx insn, rtx condition,
       unsigned HOST_WIDEST_INT val = INTVAL (desc->niter_expr);
 
       desc->const_iter = true;
-      desc->niter_max = desc->niter = val & GET_MODE_MASK (desc->mode);
+      desc->niter = val & GET_MODE_MASK (desc->mode);
+      record_niter_bound (loop, double_int::from_shwi (desc->niter),
+			  false, true);
     }
   else
     {
       max = determine_max_iter (loop, desc, old_niter);
-      if (!desc->niter_max
-	  || max < desc->niter_max)
-	desc->niter_max = max;
+      gcc_assert (max);
+      record_niter_bound (loop, double_int::from_shwi (max),
+			  false, true);
 
       /* simplify_using_initial_values does a copy propagation on the registers
 	 in the expression for the number of iterations.  This prolongs life
@@ -2812,7 +2809,8 @@ zero_iter_simplify:
 zero_iter:
   desc->const_iter = true;
   desc->niter = 0;
-  desc->niter_max = 0;
+  record_niter_bound (loop, double_int_zero,
+		      true, true);
   desc->noloop_assumptions = NULL_RTX;
   desc->niter_expr = const0_rtx;
   return;
@@ -2946,9 +2944,10 @@ find_simple_exit (struct loop *loop, struct niter_desc *desc)
 	  print_rtl (dump_file, desc->niter_expr);
       	  fprintf (dump_file, "\n");
 
-	  fprintf (dump_file, "  upper bound: ");
-	  fprintf (dump_file, HOST_WIDEST_INT_PRINT_DEC, desc->niter_max);
-      	  fprintf (dump_file, "\n");
+	  fprintf (dump_file, "  upper bound: %li\n",
+		   (long)max_loop_iterations_int (loop));
+	  fprintf (dump_file, "  realistic bound: %li\n",
+		   (long)estimated_loop_iterations_int (loop));
 	}
       else
 	fprintf (dump_file, "Loop %d is not simple.\n", loop->num);
diff --git a/gcc/loop-unroll.c b/gcc/loop-unroll.c
index a09192597dd..b9ac22b8255 100644
--- a/gcc/loop-unroll.c
+++ b/gcc/loop-unroll.c
@@ -341,7 +341,8 @@ decide_peel_once_rolling (struct loop *loop, int flags ATTRIBUTE_UNUSED)
       || desc->assumptions
       || desc->infinite
       || !desc->const_iter
-      || desc->niter != 0)
+      || (desc->niter != 0
+	  && max_loop_iterations_int (loop) != 0))
     {
       if (dump_file)
 	fprintf (dump_file,
@@ -695,7 +696,13 @@ unroll_loop_constant_iterations (struct loop *loop)
 
 	  desc->noloop_assumptions = NULL_RTX;
 	  desc->niter -= exit_mod;
-	  desc->niter_max -= exit_mod;
+	  loop->nb_iterations_upper_bound -= double_int::from_uhwi (exit_mod);
+	  if (loop->any_estimate
+	      && double_int::from_uhwi (exit_mod).ule
+	           (loop->nb_iterations_estimate))
+	    loop->nb_iterations_estimate -= double_int::from_uhwi (exit_mod);
+	  else
+	    loop->any_estimate = false;
 	}
 
       SET_BIT (wont_exit, 1);
@@ -733,7 +740,12 @@ unroll_loop_constant_iterations (struct loop *loop)
   	    apply_opt_in_copies (opt_info, exit_mod + 1, false, false);
 
 	  desc->niter -= exit_mod + 1;
-	  desc->niter_max -= exit_mod + 1;
+	  if (loop->any_estimate
+	      && double_int::from_uhwi (exit_mod + 1).ule
+	           (loop->nb_iterations_estimate))
+	    loop->nb_iterations_estimate -= double_int::from_uhwi (exit_mod + 1);
+	  else
+	    loop->any_estimate = false;
 	  desc->noloop_assumptions = NULL_RTX;
 
 	  SET_BIT (wont_exit, 0);
@@ -782,7 +794,15 @@ unroll_loop_constant_iterations (struct loop *loop)
     }
 
   desc->niter /= max_unroll + 1;
-  desc->niter_max /= max_unroll + 1;
+  loop->nb_iterations_upper_bound
+    = loop->nb_iterations_upper_bound.udiv (double_int::from_uhwi (exit_mod
+								   + 1),
+					    FLOOR_DIV_EXPR);
+  if (loop->any_estimate)
+    loop->nb_iterations_estimate
+      = loop->nb_iterations_estimate.udiv (double_int::from_uhwi (exit_mod
+							          + 1),
+				           FLOOR_DIV_EXPR);
   desc->niter_expr = GEN_INT (desc->niter);
 
   /* Remove the edges.  */
@@ -803,6 +823,7 @@ decide_unroll_runtime_iterations (struct loop *loop, int flags)
 {
   unsigned nunroll, nunroll_by_av, i;
   struct niter_desc *desc;
+  double_int iterations;
 
   if (!(flags & UAP_UNROLL))
     {
@@ -856,9 +877,10 @@ decide_unroll_runtime_iterations (struct loop *loop, int flags)
     }
 
   /* If we have profile feedback, check whether the loop rolls.  */
-  if ((loop->header->count
-       && expected_loop_iterations (loop) < 2 * nunroll)
-      || desc->niter_max < 2 * nunroll)
+  if ((estimated_loop_iterations (loop, &iterations)
+       || max_loop_iterations (loop, &iterations))
+      && iterations.fits_shwi ()
+      && iterations.to_shwi () <= 2 * nunroll)
     {
       if (dump_file)
 	fprintf (dump_file, ";; Not unrolling loop, doesn't roll\n");
@@ -1092,6 +1114,7 @@ unroll_loop_runtime_iterations (struct loop *loop)
       single_pred_edge (swtch)->probability = REG_BR_PROB_BASE - p;
       e = make_edge (swtch, preheader,
 		     single_succ_edge (swtch)->flags & EDGE_IRREDUCIBLE_LOOP);
+      e->count = RDIV (preheader->count * REG_BR_PROB_BASE, p);
       e->probability = p;
     }
 
@@ -1111,6 +1134,7 @@ unroll_loop_runtime_iterations (struct loop *loop)
       single_succ_edge (swtch)->probability = REG_BR_PROB_BASE - p;
       e = make_edge (swtch, preheader,
 		     single_succ_edge (swtch)->flags & EDGE_IRREDUCIBLE_LOOP);
+      e->count = RDIV (preheader->count * REG_BR_PROB_BASE, p);
       e->probability = p;
     }
 
@@ -1172,13 +1196,26 @@ unroll_loop_runtime_iterations (struct loop *loop)
   desc->niter_expr =
     simplify_gen_binary (UDIV, desc->mode, old_niter,
 			 GEN_INT (max_unroll + 1));
-  desc->niter_max /= max_unroll + 1;
+  loop->nb_iterations_upper_bound
+    = loop->nb_iterations_upper_bound.udiv (double_int::from_uhwi (max_unroll
+								   + 1),
+					    FLOOR_DIV_EXPR);
+  if (loop->any_estimate)
+    loop->nb_iterations_estimate
+      = loop->nb_iterations_estimate.udiv (double_int::from_uhwi (max_unroll
+							          + 1),
+				           FLOOR_DIV_EXPR);
   if (exit_at_end)
     {
       desc->niter_expr =
 	simplify_gen_binary (MINUS, desc->mode, desc->niter_expr, const1_rtx);
       desc->noloop_assumptions = NULL_RTX;
-      desc->niter_max--;
+      --loop->nb_iterations_upper_bound;
+      if (loop->any_estimate
+	  && loop->nb_iterations_estimate != double_int_zero)
+	--loop->nb_iterations_estimate;
+      else
+	loop->any_estimate = false;
     }
 
   if (dump_file)
@@ -1196,6 +1233,7 @@ decide_peel_simple (struct loop *loop, int flags)
 {
   unsigned npeel;
   struct niter_desc *desc;
+  double_int iterations;
 
   if (!(flags & UAP_PEEL))
     {
@@ -1239,23 +1277,30 @@ decide_peel_simple (struct loop *loop, int flags)
       return;
     }
 
-  if (loop->header->count)
+  /* If we have realistic estimate on number of iterations, use it.  */
+  if (estimated_loop_iterations (loop, &iterations))
     {
-      unsigned niter = expected_loop_iterations (loop);
-      if (niter + 1 > npeel)
+      if (!iterations.fits_shwi ()
+	  || iterations.to_shwi () + 1 > npeel)
 	{
 	  if (dump_file)
 	    {
 	      fprintf (dump_file, ";; Not peeling loop, rolls too much (");
 	      fprintf (dump_file, HOST_WIDEST_INT_PRINT_DEC,
-		       (HOST_WIDEST_INT) (niter + 1));
+		       (HOST_WIDEST_INT) (iterations.to_shwi () + 1));
 	      fprintf (dump_file, " iterations > %d [maximum peelings])\n",
 		       npeel);
 	    }
 	  return;
 	}
-      npeel = niter + 1;
-    }
+      npeel = iterations.to_shwi () + 1;
+    }
+  /* If we have small enough bound on iterations, we can still peel (completely
+     unroll).  */
+  else if (max_loop_iterations (loop, &iterations)
+           && iterations.fits_shwi ()
+           && iterations.to_shwi () + 1 <= npeel)
+    npeel = iterations.to_shwi () + 1;
   else
     {
       /* For now we have no good heuristics to decide whether loop peeling
@@ -1349,6 +1394,7 @@ decide_unroll_stupid (struct loop *loop, int flags)
 {
   unsigned nunroll, nunroll_by_av, i;
   struct niter_desc *desc;
+  double_int iterations;
 
   if (!(flags & UAP_UNROLL_ALL))
     {
@@ -1401,9 +1447,10 @@ decide_unroll_stupid (struct loop *loop, int flags)
     }
 
   /* If we have profile feedback, check whether the loop rolls.  */
-  if ((loop->header->count
-       && expected_loop_iterations (loop) < 2 * nunroll)
-      || desc->niter_max < 2 * nunroll)
+  if ((estimated_loop_iterations (loop, &iterations)
+       || max_loop_iterations (loop, &iterations))
+      && iterations.fits_shwi ()
+      && iterations.to_shwi () <= 2 * nunroll)
     {
       if (dump_file)
 	fprintf (dump_file, ";; Not unrolling loop, doesn't roll\n");
diff --git a/gcc/loop-unswitch.c b/gcc/loop-unswitch.c
index a9089a66cdf..4107048de01 100644
--- a/gcc/loop-unswitch.c
+++ b/gcc/loop-unswitch.c
@@ -257,6 +257,7 @@ unswitch_single_loop (struct loop *loop, rtx cond_checked, int num)
   rtx cond, rcond = NULL_RTX, conds, rconds, acond, cinsn;
   int repeat;
   edge e;
+  HOST_WIDE_INT iterations;
 
   /* Do not unswitch too much.  */
   if (num > PARAM_VALUE (PARAM_MAX_UNSWITCH_LEVEL))
@@ -299,7 +300,8 @@ unswitch_single_loop (struct loop *loop, rtx cond_checked, int num)
     }
 
   /* Nor if the loop usually does not roll.  */
-  if (expected_loop_iterations (loop) < 1)
+  iterations = estimated_loop_iterations_int (loop);
+  if (iterations >= 0 && iterations <= 1)
     {
       if (dump_file)
 	fprintf (dump_file, ";; Not unswitching, loop iterations < 1\n");
diff --git a/gcc/tree-scalar-evolution.c b/gcc/tree-scalar-evolution.c
index d88bb1aa861..325654bac1b 100644
--- a/gcc/tree-scalar-evolution.c
+++ b/gcc/tree-scalar-evolution.c
@@ -3124,6 +3124,14 @@ scev_initialize (void)
     }
 }
 
+/* Return true if SCEV is initialized.  */
+
+bool
+scev_initialized_p (void)
+{
+  return scalar_evolution_info != NULL;
+}
+
 /* Cleans up the information cached by the scalar evolutions analysis
    in the hash table.  */
 
diff --git a/gcc/tree-scalar-evolution.h b/gcc/tree-scalar-evolution.h
index dd1bdfc3404..3e52c57e393 100644
--- a/gcc/tree-scalar-evolution.h
+++ b/gcc/tree-scalar-evolution.h
@@ -27,6 +27,7 @@ extern tree number_of_exit_cond_executions (struct loop *);
 extern gimple get_loop_exit_condition (const struct loop *);
 
 extern void scev_initialize (void);
+extern bool scev_initialized_p (void);
 extern void scev_reset (void);
 extern void scev_reset_htab (void);
 extern void scev_finalize (void);
diff --git a/gcc/tree-ssa-loop-niter.c b/gcc/tree-ssa-loop-niter.c
index 84ae6104490..cdcdb5c5ad8 100644
--- a/gcc/tree-ssa-loop-niter.c
+++ b/gcc/tree-ssa-loop-niter.c
@@ -3012,9 +3012,23 @@ estimate_numbers_of_iterations_loop (struct loop *loop)
 bool
 estimated_loop_iterations (struct loop *loop, double_int *nit)
 {
-  estimate_numbers_of_iterations_loop (loop);
+  /* When SCEV information is available, try to update loop iterations
+     estimate.  Otherwise just return whatever we recorded earlier.  */
+  if (scev_initialized_p ())
+    estimate_numbers_of_iterations_loop (loop);
+
+  /* Even if the bound is not recorded, possibly we can derrive one from
+     profile.  */
   if (!loop->any_estimate)
-    return false;
+    {
+      if (loop->header->count)
+	{
+          *nit = gcov_type_to_double_int
+		   (expected_loop_iterations_unbounded (loop) + 1);
+	  return true;
+	}
+      return false;
+    }
 
   *nit = loop->nb_iterations_estimate;
   return true;
@@ -3027,7 +3041,10 @@ estimated_loop_iterations (struct loop *loop, double_int *nit)
 bool
 max_loop_iterations (struct loop *loop, double_int *nit)
 {
-  estimate_numbers_of_iterations_loop (loop);
+  /* When SCEV information is available, try to update loop iterations
+     estimate.  Otherwise just return whatever we recorded earlier.  */
+  if (scev_initialized_p ())
+    estimate_numbers_of_iterations_loop (loop);
   if (!loop->any_upper_bound)
     return false;
 
diff --git a/gcc/tree-ssa-loop-unswitch.c b/gcc/tree-ssa-loop-unswitch.c
index eaf41e7d6ce..b24f3d74dce 100644
--- a/gcc/tree-ssa-loop-unswitch.c
+++ b/gcc/tree-ssa-loop-unswitch.c
@@ -78,6 +78,7 @@ tree_ssa_unswitch_loops (void)
   loop_iterator li;
   struct loop *loop;
   bool changed = false;
+  HOST_WIDE_INT iterations;
 
   /* Go through inner loops (only original ones).  */
   FOR_EACH_LOOP (li, loop, LI_ONLY_INNERMOST)
@@ -102,6 +103,16 @@ tree_ssa_unswitch_loops (void)
           continue;
         }
 
+      /* If the loop is not expected to iterate, there is no need
+	 for unswitching.  */
+      iterations = estimated_loop_iterations_int (loop);
+      if (iterations >= 0 && iterations <= 1)
+	{
+          if (dump_file && (dump_flags & TDF_DETAILS))
+            fprintf (dump_file, ";; Not unswitching, loop is not expected to iterate\n");
+          continue;
+	}
+
       changed |= tree_unswitch_single_loop (loop, 0);
     }