PR tree-optimization/19401

	* tree-flow.h (tree_unroll_loops_completely): Declaration changed.
	* tree-ssa-loop-ivcanon.c (enum unroll_level): New.
	(estimated_unrolled_size): New function.
	(try_unroll_loop_completely, canonicalize_loop_induction_variables,
	tree_unroll_loops_completely): Always unroll loops if the code size
	does not increase.
	* tree-ssa-loop.c (tree_complete_unroll): Indicate whether all
	loops should be unrolled completely.
	(gate_tree_complete_unroll): Run complete unrolling unconditionally.


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

4 files changed, 94 insertions, 19 deletions

diff --git a/gcc/ChangeLog b/gcc/ChangeLog
index e579c1de342..9a94371ef13 100644
--- a/gcc/ChangeLog
+++ b/gcc/ChangeLog
@@ -1,5 +1,18 @@
 2005-05-06  Zdenek Dvorak  <dvorakz@suse.cz>
 
+	PR tree-optimization/19401
+	* tree-flow.h (tree_unroll_loops_completely): Declaration changed.
+	* tree-ssa-loop-ivcanon.c (enum unroll_level): New.
+	(estimated_unrolled_size): New function.
+	(try_unroll_loop_completely, canonicalize_loop_induction_variables,
+	tree_unroll_loops_completely): Always unroll loops if the code size
+	does not increase.
+	* tree-ssa-loop.c (tree_complete_unroll): Indicate whether all
+	loops should be unrolled completely.
+	(gate_tree_complete_unroll): Run complete unrolling unconditionally.
+
+2005-05-06  Zdenek Dvorak  <dvorakz@suse.cz>
+
 	PR rtl-optimization/21254
 	* loop-iv.c (iv_number_of_iterations): Simplify infiniteness
 	assumptions for loops that otherwise do not roll.
diff --git a/gcc/tree-flow.h b/gcc/tree-flow.h
index d71238cd388..fc1456488d2 100644
--- a/gcc/tree-flow.h
+++ b/gcc/tree-flow.h
@@ -693,7 +693,7 @@ bool empty_block_p (basic_block);
 void tree_ssa_lim (struct loops *);
 void tree_ssa_unswitch_loops (struct loops *);
 void canonicalize_induction_variables (struct loops *);
-void tree_unroll_loops_completely (struct loops *);
+void tree_unroll_loops_completely (struct loops *, bool);
 void tree_ssa_iv_optimize (struct loops *);
 
 bool number_of_iterations_exit (struct loop *, edge,
diff --git a/gcc/tree-ssa-loop-ivcanon.c b/gcc/tree-ssa-loop-ivcanon.c
index f2898b5c781..c4e64b2635a 100644
--- a/gcc/tree-ssa-loop-ivcanon.c
+++ b/gcc/tree-ssa-loop-ivcanon.c
@@ -55,6 +55,17 @@ Software Foundation, 59 Temple Place - Suite 330, Boston, MA
 #include "flags.h"
 #include "tree-inline.h"
 
+/* Specifies types of loops that may be unrolled.  */
+
+enum unroll_level
+{
+  UL_SINGLE_ITER,	/* Only loops that exit immediatelly in the first
+			   iteration.  */
+  UL_NO_GROWTH,		/* Only loops whose unrolling will not cause increase
+			   of code size.  */
+  UL_ALL		/* All suitable loops.  */
+};
+
 /* Adds a canonical induction variable to LOOP iterating NITER times.  EXIT
    is the exit edge whose condition is replaced.  */
 
@@ -117,18 +128,43 @@ tree_num_loop_insns (struct loop *loop)
   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):
+
+   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.
+
+   NINSNS is the number of insns in the loop before unrolling.
+   NUNROLL is the number of times the loop is unrolled.  */
+
+static unsigned HOST_WIDE_INT
+estimated_unrolled_size (unsigned HOST_WIDE_INT ninsns,
+			 unsigned HOST_WIDE_INT nunroll)
+{
+  HOST_WIDE_INT unr_insns = 2 * ((HOST_WIDE_INT) ninsns - 4) / 3;
+  if (unr_insns <= 0)
+    unr_insns = 1;
+  unr_insns *= (nunroll + 1);
+
+  return unr_insns;
+}
+
 /* Tries to unroll LOOP completely, i.e. NITER times.  LOOPS is the
-   loop tree.  COMPLETELY_UNROLL is true if we should unroll the loop
-   even if it may cause code growth.  EXIT is the exit of the loop
-   that should be eliminated.  */
+   loop tree.  UL determines which loops we are allowed to unroll. 
+   EXIT is the exit of the loop that should be eliminated.  */
 
 static bool
 try_unroll_loop_completely (struct loops *loops ATTRIBUTE_UNUSED,
 			    struct loop *loop,
 			    edge exit, tree niter,
-			    bool completely_unroll)
+			    enum unroll_level ul)
 {
-  unsigned HOST_WIDE_INT n_unroll, ninsns, max_unroll;
+  unsigned HOST_WIDE_INT n_unroll, ninsns, max_unroll, unr_insns;
   tree old_cond, cond, dont_exit, do_exit;
 
   if (loop->inner)
@@ -144,7 +180,7 @@ try_unroll_loop_completely (struct loops *loops ATTRIBUTE_UNUSED,
 
   if (n_unroll)
     {
-      if (!completely_unroll)
+      if (ul == UL_SINGLE_ITER)
 	return false;
 
       ninsns = tree_num_loop_insns (loop);
@@ -152,6 +188,25 @@ try_unroll_loop_completely (struct loops *loops ATTRIBUTE_UNUSED,
       if (n_unroll * ninsns
 	  > (unsigned) PARAM_VALUE (PARAM_MAX_COMPLETELY_PEELED_INSNS))
 	return false;
+
+      if (ul == UL_NO_GROWTH)
+	{
+	  unr_insns = estimated_unrolled_size (ninsns, n_unroll);
+	  
+	  if (dump_file && (dump_flags & TDF_DETAILS))
+	    {
+	      fprintf (dump_file, "  Loop size: %d\n", (int) ninsns);
+	      fprintf (dump_file, "  Estimated size after unrolling: %d\n",
+		       (int) unr_insns);
+	    }
+	  
+	  if (unr_insns > ninsns)
+	    {
+	      if (dump_file && (dump_flags & TDF_DETAILS))
+		fprintf (dump_file, "Not unrolling loop %d:\n", loop->num);
+	      return false;
+	    }
+	}
     }
 
   if (exit->flags & EDGE_TRUE_VALUE)
@@ -194,14 +249,14 @@ try_unroll_loop_completely (struct loops *loops ATTRIBUTE_UNUSED,
 }
 
 /* Adds a canonical induction variable to LOOP if suitable.  LOOPS is the loops
-   tree.  CREATE_IV is true if we may create a new iv.  COMPLETELY_UNROLL is
-   true if we should do complete unrolling even if it may cause the code
-   growth.  If TRY_EVAL is true, we try to determine the number of iterations
-   of a loop by direct evaluation.  Returns true if cfg is changed.  */
+   tree.  CREATE_IV is true if we may create a new iv.  UL determines what
+   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. 
+   Returns true if cfg is changed.  */
 
 static bool
 canonicalize_loop_induction_variables (struct loops *loops, struct loop *loop,
-				       bool create_iv, bool completely_unroll,
+				       bool create_iv, enum unroll_level ul,
 				       bool try_eval)
 {
   edge exit = NULL;
@@ -245,7 +300,7 @@ canonicalize_loop_induction_variables (struct loops *loops, struct loop *loop,
       fprintf (dump_file, " times.\n");
     }
 
-  if (try_unroll_loop_completely (loops, loop, exit, niter, completely_unroll))
+  if (try_unroll_loop_completely (loops, loop, exit, niter, ul))
     return true;
 
   if (create_iv)
@@ -270,7 +325,8 @@ canonicalize_induction_variables (struct loops *loops)
 
       if (loop)
 	changed |= canonicalize_loop_induction_variables (loops, loop,
-							  true, false, true);
+							  true, UL_SINGLE_ITER,
+							  true);
     }
 
   /* Clean up the information about numbers of iterations, since brute force
@@ -281,14 +337,17 @@ canonicalize_induction_variables (struct loops *loops)
     cleanup_tree_cfg_loop ();
 }
 
-/* Unroll LOOPS completely if they iterate just few times.  */
+/* Unroll LOOPS completely if they iterate just few times.  Unless
+   MAY_INCREASE_SIZE is true, perform the unrolling only if the
+   size of the code does not increase.  */
 
 void
-tree_unroll_loops_completely (struct loops *loops)
+tree_unroll_loops_completely (struct loops *loops, bool may_increase_size)
 {
   unsigned i;
   struct loop *loop;
   bool changed = false;
+  enum unroll_level ul = may_increase_size ? UL_ALL : UL_NO_GROWTH;
 
   for (i = 1; i < loops->num; i++)
     {
@@ -298,7 +357,7 @@ tree_unroll_loops_completely (struct loops *loops)
 	continue;
 
       changed |= canonicalize_loop_induction_variables (loops, loop,
-							false, true,
+							false, ul,
 							!flag_tree_loop_ivcanon);
     }
 
diff --git a/gcc/tree-ssa-loop.c b/gcc/tree-ssa-loop.c
index b86820ecfa4..f7a96fb2aa7 100644
--- a/gcc/tree-ssa-loop.c
+++ b/gcc/tree-ssa-loop.c
@@ -323,13 +323,16 @@ tree_complete_unroll (void)
   if (!current_loops)
     return;
 
-  tree_unroll_loops_completely (current_loops);
+  tree_unroll_loops_completely (current_loops,
+				flag_unroll_loops
+				|| flag_peel_loops
+				|| optimize >= 3);
 }
 
 static bool
 gate_tree_complete_unroll (void)
 {
-  return flag_peel_loops || flag_unroll_loops;
+  return true;
 }
 
 struct tree_opt_pass pass_complete_unroll =