[gcc] GCC 4.5.0=>4.5.1

gcc/gcc/tree-ssa-loop-ivcanon.c

Index: gcc/gcc/tree-ssa-loop-ivcanon.c
diff --git a/gcc/gcc/tree-ssa-loop-ivcanon.c b/gcc/gcc/tree-ssa-loop-ivcanon.c
index e278c55b08bbd3f0387bf8f03a968f13fd1e9441..2b0988d1e52a827bcdf160d8192017b670eebb47 100644
--- a/gcc/gcc/tree-ssa-loop-ivcanon.c
+++ b/gcc/gcc/tree-ssa-loop-ivcanon.c
@@ -1,24 +1,25 @@
 /* Induction variable canonicalization.
-   Copyright (C) 2004, 2005, 2007, 2008 Free Software Foundation, Inc.
-   
+   Copyright (C) 2004, 2005, 2007, 2008, 2010
+   Free Software Foundation, Inc.
+
 This file is part of GCC.
-   
+
 GCC is free software; you can redistribute it and/or modify it
 under the terms of the GNU General Public License as published by the
 Free Software Foundation; either version 3, or (at your option) any
 later version.
-   
+
 GCC is distributed in the hope that it will be useful, but WITHOUT
 ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
 FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
 for more details.
-   
+
 You should have received a copy of the GNU General Public License
 along with GCC; see the file COPYING3.  If not see
 <http://www.gnu.org/licenses/>.  */
 
 /* This pass detects the loops that iterate a constant number of times,
-   adds a canonical induction variable (step -1, tested against 0) 
+   adds a canonical induction variable (step -1, tested against 0)
    and replaces the exit test.  This enables the less powerful rtl
    level analysis to use this information.
 
@@ -53,6 +54,7 @@ along with GCC; see the file COPYING3.  If not see
 #include "params.h"
 #include "flags.h"
 #include "tree-inline.h"
+#include "target.h"
 
 /* Specifies types of loops that may be unrolled.  */
 
@@ -118,7 +120,7 @@ tree_num_loop_insns (struct loop *loop, eni_weights *weights)
 {
   basic_block *body = get_loop_body (loop);
   gimple_stmt_iterator gsi;
-  unsigned size = 1, i;
+  unsigned size = 0, i;
 
   for (i = 0; i < loop->num_nodes; i++)
     for (gsi = gsi_start_bb (body[i]); !gsi_end_p (gsi); gsi_next (&gsi))
@@ -128,34 +130,201 @@ tree_num_loop_insns (struct loop *loop, eni_weights *weights)
   return size;
 }
 
-/* Estimate number of insns of completely unrolled loop.  We assume
-   that the size of the unrolled loop is decreased in the
-   following way (the numbers of insns are based on what
-   estimate_num_insns returns for appropriate statements):
+/* Describe size of loop as detected by tree_estimate_loop_size.  */
+struct loop_size
+{
+  /* Number of instructions in the loop.  */
+  int overall;
+
+  /* Number of instructions that will be likely optimized out in
+     peeled iterations of loop  (i.e. computation based on induction
+     variable where induction variable starts at known constant.)  */
+  int eliminated_by_peeling;
+
+  /* Same statistics for last iteration of loop: it is smaller because
+     instructions after exit are not executed.  */
+  int last_iteration;
+  int last_iteration_eliminated_by_peeling;
+};
+
+/* Return true if OP in STMT will be constant after peeling LOOP.  */
+
+static bool
+constant_after_peeling (tree op, gimple stmt, struct loop *loop)
+{
+  affine_iv iv;
+
+  if (is_gimple_min_invariant (op))
+    return true;
 
-   1) exit condition gets removed (2 insns)
-   2) increment of the control variable gets removed (2 insns)
-   3) All remaining statements are likely to get simplified
-      due to constant propagation.  Hard to estimate; just
-      as a heuristics we decrease the rest by 1/3.
+  /* We can still fold accesses to constant arrays when index is known.  */
+  if (TREE_CODE (op) != SSA_NAME)
+    {
+      tree base = op;
+
+      /* First make fast look if we see constant array inside.  */
+      while (handled_component_p (base))
+	base = TREE_OPERAND (base, 0);
+      if ((DECL_P (base)
+      	   && TREE_STATIC (base)
+	   && TREE_READONLY (base)
+           && (DECL_INITIAL (base)
+	       || (!DECL_EXTERNAL (base)
+		   && targetm.binds_local_p (base))))
+	  || CONSTANT_CLASS_P (base))
+	{
+	  /* If so, see if we understand all the indices.  */
+	  base = op;
+	  while (handled_component_p (base))
+	    {
+	      if (TREE_CODE (base) == ARRAY_REF
+		  && !constant_after_peeling (TREE_OPERAND (base, 1), stmt, loop))
+		return false;
+	      base = TREE_OPERAND (base, 0);
+	    }
+	  return true;
+	}
+      return false;
+    }
 
-   NINSNS is the number of insns in the loop before unrolling.
-   NUNROLL is the number of times the loop is unrolled.  */
+  /* Induction variables are constants.  */
+  if (!simple_iv (loop, loop_containing_stmt (stmt), op, &iv, false))
+    return false;
+  if (!is_gimple_min_invariant (iv.base))
+    return false;
+  if (!is_gimple_min_invariant (iv.step))
+    return false;
+  return true;
+}
+
+/* Computes an estimated number of insns in LOOP, weighted by WEIGHTS.
+   Return results in SIZE, estimate benefits for complete unrolling exiting by EXIT.  */
+
+static void
+tree_estimate_loop_size (struct loop *loop, edge exit, struct loop_size *size)
+{
+  basic_block *body = get_loop_body (loop);
+  gimple_stmt_iterator gsi;
+  unsigned int i;
+  bool after_exit;
+
+  size->overall = 0;
+  size->eliminated_by_peeling = 0;
+  size->last_iteration = 0;
+  size->last_iteration_eliminated_by_peeling = 0;
+
+  if (dump_file && (dump_flags & TDF_DETAILS))
+    fprintf (dump_file, "Estimating sizes for loop %i\n", loop->num);
+  for (i = 0; i < loop->num_nodes; i++)
+    {
+      if (exit && body[i] != exit->src
+	  && dominated_by_p (CDI_DOMINATORS, body[i], exit->src))
+	after_exit = true;
+      else
+	after_exit = false;
+      if (dump_file && (dump_flags & TDF_DETAILS))
+	fprintf (dump_file, " BB: %i, after_exit: %i\n", body[i]->index, after_exit);
+
+      for (gsi = gsi_start_bb (body[i]); !gsi_end_p (gsi); gsi_next (&gsi))
+	{
+	  gimple stmt = gsi_stmt (gsi);
+	  int num = estimate_num_insns (stmt, &eni_size_weights);
+	  bool likely_eliminated = false;
+
+	  if (dump_file && (dump_flags & TDF_DETAILS))
+	    {
+	      fprintf (dump_file, "  size: %3i ", num);
+	      print_gimple_stmt (dump_file, gsi_stmt (gsi), 0, 0);
+	    }
+
+	  /* Look for reasons why we might optimize this stmt away. */
+
+	  /* Exit conditional.  */
+	  if (body[i] == exit->src && stmt == last_stmt (exit->src))
+	    {
+	      if (dump_file && (dump_flags & TDF_DETAILS))
+	        fprintf (dump_file, "   Exit condition will be eliminated.\n");
+	      likely_eliminated = true;
+	    }
+	  /* Sets of IV variables  */
+	  else if (gimple_code (stmt) == GIMPLE_ASSIGN
+	      && constant_after_peeling (gimple_assign_lhs (stmt), stmt, loop))
+	    {
+	      if (dump_file && (dump_flags & TDF_DETAILS))
+	        fprintf (dump_file, "   Induction variable computation will"
+			 " be folded away.\n");
+	      likely_eliminated = true;
+	    }
+	  /* Assignments of IV variables.  */
+	  else if (gimple_code (stmt) == GIMPLE_ASSIGN
+		   && TREE_CODE (gimple_assign_lhs (stmt)) == SSA_NAME
+		   && constant_after_peeling (gimple_assign_rhs1 (stmt), stmt,loop)
+		   && (gimple_assign_rhs_class (stmt) != GIMPLE_BINARY_RHS
+		       || constant_after_peeling (gimple_assign_rhs2 (stmt),
+		       				  stmt, loop)))
+	    {
+	      if (dump_file && (dump_flags & TDF_DETAILS))
+	        fprintf (dump_file, "   Constant expression will be folded away.\n");
+	      likely_eliminated = true;
+	    }
+	  /* Conditionals.  */
+	  else if (gimple_code (stmt) == GIMPLE_COND
+		   && constant_after_peeling (gimple_cond_lhs (stmt), stmt, loop)
+		   && constant_after_peeling (gimple_cond_rhs (stmt), stmt, loop))
+	    {
+	      if (dump_file && (dump_flags & TDF_DETAILS))
+	        fprintf (dump_file, "   Constant conditional.\n");
+	      likely_eliminated = true;
+	    }
+
+	  size->overall += num;
+	  if (likely_eliminated)
+	    size->eliminated_by_peeling += num;
+	  if (!after_exit)
+	    {
+	      size->last_iteration += num;
+	      if (likely_eliminated)
+		size->last_iteration_eliminated_by_peeling += num;
+	    }
+	}
+    }
+  if (dump_file && (dump_flags & TDF_DETAILS))
+    fprintf (dump_file, "size: %i-%i, last_iteration: %i-%i\n", size->overall,
+    	     size->eliminated_by_peeling, size->last_iteration,
+	     size->last_iteration_eliminated_by_peeling);
+
+  free (body);
+}
+
+/* Estimate number of insns of completely unrolled loop.
+   It is (NUNROLL + 1) * size of loop body with taking into account
+   the fact that in last copy everything after exit conditional
+   is dead and that some instructions will be eliminated after
+   peeling.
+
+   Loop body is likely going to simplify futher, this is difficult
+   to guess, we just decrease the result by 1/3.  */
 
 static unsigned HOST_WIDE_INT
-estimated_unrolled_size (unsigned HOST_WIDE_INT ninsns,
+estimated_unrolled_size (struct loop_size *size,
 			 unsigned HOST_WIDE_INT nunroll)
 {
-  HOST_WIDE_INT unr_insns = 2 * ((HOST_WIDE_INT) ninsns - 4) / 3;
+  HOST_WIDE_INT unr_insns = ((nunroll)
+  			     * (HOST_WIDE_INT) (size->overall
+			     			- size->eliminated_by_peeling));
+  if (!nunroll)
+    unr_insns = 0;
+  unr_insns += size->last_iteration - size->last_iteration_eliminated_by_peeling;
+
+  unr_insns = unr_insns * 2 / 3;
   if (unr_insns <= 0)
     unr_insns = 1;
-  unr_insns *= (nunroll + 1);
 
   return unr_insns;
 }
 
 /* Tries to unroll LOOP completely, i.e. NITER times.
-   UL determines which loops we are allowed to unroll. 
+   UL determines which loops we are allowed to unroll.
    EXIT is the exit of the loop that should be eliminated.  */
 
 static bool
@@ -165,6 +334,7 @@ try_unroll_loop_completely (struct loop *loop,
 {
   unsigned HOST_WIDE_INT n_unroll, ninsns, max_unroll, unr_insns;
   gimple cond;
+  struct loop_size size;
 
   if (loop->inner)
     return false;
@@ -182,9 +352,10 @@ try_unroll_loop_completely (struct loop *loop,
       if (ul == UL_SINGLE_ITER)
 	return false;
 
-      ninsns = tree_num_loop_insns (loop, &eni_size_weights);
+      tree_estimate_loop_size (loop, exit, &size);
+      ninsns = size.overall;
 
-      unr_insns = estimated_unrolled_size (ninsns, n_unroll);
+      unr_insns = estimated_unrolled_size (&size, n_unroll);
       if (dump_file && (dump_flags & TDF_DETAILS))
 	{
 	  fprintf (dump_file, "  Loop size: %d\n", (int) ninsns);
@@ -261,9 +432,9 @@ try_unroll_loop_completely (struct loop *loop,
 }
 
 /* Adds a canonical induction variable to LOOP if suitable.
-   CREATE_IV is true if we may create a new iv.  UL determines 
+   CREATE_IV is true if we may create a new iv.  UL determines
    which loops we are allowed to completely unroll.  If TRY_EVAL is true, we try
-   to determine the number of iterations of a loop by direct evaluation. 
+   to determine the number of iterations of a loop by direct evaluation.
    Returns true if cfg is changed.  */
 
 static bool
@@ -324,7 +495,7 @@ canonicalize_induction_variables (void)
   loop_iterator li;
   struct loop *loop;
   bool changed = false;
-  
+
   FOR_EACH_LOOP (li, loop, 0)
     {
       changed |= canonicalize_loop_induction_variables (loop,
@@ -352,6 +523,7 @@ tree_unroll_loops_completely (bool may_increase_size, bool unroll_outer)
   struct loop *loop;
   bool changed;
   enum unroll_level ul;
+  int iteration = 0;
 
   do
     {
@@ -384,192 +556,8 @@ tree_unroll_loops_completely (bool may_increase_size, bool unroll_outer)
 	  scev_reset ();
 	}
     }
-  while (changed);
-
-  return 0;
-}
-
-/* Checks whether LOOP is empty.  */
-
-static bool
-empty_loop_p (struct loop *loop)
-{
-  edge exit;
-  struct tree_niter_desc niter;
-  basic_block *body;
-  gimple_stmt_iterator gsi;
-  unsigned i;
-
-  /* If the loop has multiple exits, it is too hard for us to handle.
-     Similarly, if the exit is not dominating, we cannot determine
-     whether the loop is not infinite.  */
-  exit = single_dom_exit (loop);
-  if (!exit)
-    return false;
-
-  /* The loop must be finite.  */
-  if (!number_of_iterations_exit (loop, exit, &niter, false))
-    return false;
-
-  /* Values of all loop exit phi nodes must be invariants.  */
-  for (gsi = gsi_start(phi_nodes (exit->dest)); !gsi_end_p (gsi); gsi_next (&gsi))
-    {
-      gimple phi = gsi_stmt (gsi);
-      tree def;
-
-      if (!is_gimple_reg (PHI_RESULT (phi)))
-	continue;
-
-      def = PHI_ARG_DEF_FROM_EDGE (phi, exit);
-
-      if (!expr_invariant_in_loop_p (loop, def))
-	return false;
-    }
-
-  /* And there should be no memory modifying or from other reasons
-     unremovable statements.  */
-  body = get_loop_body (loop);
-  for (i = 0; i < loop->num_nodes; i++)
-    {
-      /* Irreducible region might be infinite.  */
-      if (body[i]->flags & BB_IRREDUCIBLE_LOOP)
-	{
-	  free (body);
-	  return false;
-	}
-	
-      for (gsi = gsi_start_bb (body[i]); !gsi_end_p (gsi); gsi_next (&gsi))
-	{
-	  gimple stmt = gsi_stmt (gsi);
-
-	  if (!ZERO_SSA_OPERANDS (stmt, SSA_OP_VIRTUAL_DEFS)
-	      || gimple_has_volatile_ops (stmt))
-	    {
-	      free (body);
-	      return false;
-	    }
-
-	  /* Also, asm statements and calls may have side effects and we
-	     cannot change the number of times they are executed.  */
-	  switch (gimple_code (stmt))
-	    {
-	    case GIMPLE_CALL:
-	      if (gimple_has_side_effects (stmt))
-		{
-		  free (body);
-		  return false;
-		}
-	      break;
-
-	    case GIMPLE_ASM:
-	      /* We cannot remove volatile assembler.  */
-	      if (gimple_asm_volatile_p (stmt))
-		{
-		  free (body);
-		  return false;
-		}
-	      break;
-
-	    default:
-	      break;
-	    }
-	}
-      }
-  free (body);
-
-  return true;
-}
-
-/* Remove LOOP by making it exit in the first iteration.  */
-
-static void
-remove_empty_loop (struct loop *loop)
-{
-  edge exit = single_dom_exit (loop), non_exit;
-  gimple cond_stmt = last_stmt (exit->src);
-  basic_block *body;
-  unsigned n_before, freq_in, freq_h;
-  gcov_type exit_count = exit->count;
-
-  if (dump_file)
-    fprintf (dump_file, "Removing empty loop %d\n", loop->num);
-
-  non_exit = EDGE_SUCC (exit->src, 0);
-  if (non_exit == exit)
-    non_exit = EDGE_SUCC (exit->src, 1);
-
-  if (exit->flags & EDGE_TRUE_VALUE)
-    gimple_cond_make_true (cond_stmt);
-  else
-    gimple_cond_make_false (cond_stmt);
-  update_stmt (cond_stmt);
-
-  /* Let us set the probabilities of the edges coming from the exit block.  */
-  exit->probability = REG_BR_PROB_BASE;
-  non_exit->probability = 0;
-  non_exit->count = 0;
-
-  /* Update frequencies and counts.  Everything before
-     the exit needs to be scaled FREQ_IN/FREQ_H times,
-     where FREQ_IN is the frequency of the entry edge
-     and FREQ_H is the frequency of the loop header.
-     Everything after the exit has zero frequency.  */
-  freq_h = loop->header->frequency;
-  freq_in = EDGE_FREQUENCY (loop_preheader_edge (loop));
-  if (freq_h != 0)
-    {
-      body = get_loop_body_in_dom_order (loop);
-      for (n_before = 1; n_before <= loop->num_nodes; n_before++)
-	if (body[n_before - 1] == exit->src)
-	  break;
-      scale_bbs_frequencies_int (body, n_before, freq_in, freq_h);
-      scale_bbs_frequencies_int (body + n_before, loop->num_nodes - n_before,
-				 0, 1);
-      free (body);
-    }
-
-  /* Number of executions of exit is not changed, thus we need to restore
-     the original value.  */
-  exit->count = exit_count;
-}
-
-/* Removes LOOP if it is empty.  Returns true if LOOP is removed.  CHANGED
-   is set to true if LOOP or any of its subloops is removed.  */
-
-static bool
-try_remove_empty_loop (struct loop *loop, bool *changed)
-{
-  bool nonempty_subloop = false;
-  struct loop *sub;
+  while (changed
+	 && ++iteration <= PARAM_VALUE (PARAM_MAX_UNROLL_ITERATIONS));
 
-  /* First, all subloops must be removed.  */
-  for (sub = loop->inner; sub; sub = sub->next)
-    nonempty_subloop |= !try_remove_empty_loop (sub, changed);
-
-  if (nonempty_subloop || !empty_loop_p (loop))
-    return false;
-
-  remove_empty_loop (loop);
-  *changed = true;
-  return true;
-}
-
-/* Remove the empty loops.  */
-
-unsigned int
-remove_empty_loops (void)
-{
-  bool changed = false;
-  struct loop *loop;
-
-  for (loop = current_loops->tree_root->inner; loop; loop = loop->next)
-    try_remove_empty_loop (loop, &changed);
-
-  if (changed)
-    {
-      scev_reset ();
-      return TODO_cleanup_cfg;
-    }
   return 0;
 }
-