[patch] Fix memory exhaustion during cunrolli

[Eric Botcazou <ebotcazou at adacore dot com>]

Hi,

the attached testcase triggers a memory exhaustion at -O2 during the cunrolli 
pass on the mainline and 4.7 branch.  The problem is that the size estimates 
disregard induction variable computations on the ground that they will be 
folded later.  But they aren't folded between the iterations of the loop so 
they can add up and exhaust the memory during SSA updating if stars are 
properly aligned.

The patch is a somewhat simple-minded fix...  Bootstrapped/regtested on x86_64-
suse-linux.  OK for mainline and 4.7 branch?


2012-09-13  Eric Botcazou  <ebotcazou@adacore.com>

	* tree-ssa-loop-ivcanon.c (propagate_constants_for_unrolling): New.
	(tree_unroll_loops_completely): Starting from the second iteration,
	propagate constants within the innermost loops.


2012-09-13  Eric Botcazou  <ebotcazou@adacore.com>

	* gnat.dg/loop_optimization12.ad[sb]: New test.


-- 
Eric Botcazou

Index: tree-ssa-loop-ivcanon.c
===================================================================
--- tree-ssa-loop-ivcanon.c	(revision 191198)
+++ tree-ssa-loop-ivcanon.c	(working copy)
@@ -503,6 +503,48 @@ canonicalize_induction_variables (void)
   return 0;
 }
 
+/* Propagate constant SSA_NAMEs defined in basic block BB.  */
+
+static void
+propagate_constants_for_unrolling (basic_block bb)
+{
+  gimple_stmt_iterator gsi;
+
+  for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); )
+    {
+      gimple stmt = gsi_stmt (gsi);
+      tree lhs;
+
+      /* Look for assignments to SSA names with constant RHS.  */
+      if (is_gimple_assign (stmt)
+	  && (lhs = gimple_assign_lhs (stmt), TREE_CODE (lhs) == SSA_NAME)
+	  && gimple_assign_rhs_code (stmt) == INTEGER_CST)
+	{
+	  imm_use_iterator iter;
+	  gimple use_stmt;
+
+	  /* Propagate the RHS into all the uses of the SSA name.  */
+	  FOR_EACH_IMM_USE_STMT (use_stmt, iter, lhs)
+	    {
+	      gimple_stmt_iterator use_stmt_gsi = gsi_for_stmt (use_stmt);
+	      use_operand_p use;
+
+	      FOR_EACH_IMM_USE_ON_STMT (use, iter)
+	        propagate_value (use, gimple_assign_rhs1 (stmt));
+
+	      fold_stmt_inplace (&use_stmt_gsi);
+	      update_stmt (use_stmt);
+	    }
+
+	  /* And get rid of the now unused SSA name.  */
+	  gsi_remove (&gsi, true);
+	  release_ssa_name (lhs);
+	}
+      else
+	gsi_next (&gsi);
+    }
+}
+
 /* 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.  */
@@ -522,6 +564,19 @@ tree_unroll_loops_completely (bool may_i
 
       FOR_EACH_LOOP (li, loop, LI_ONLY_INNERMOST)
 	{
+	  /* If we have already unrolled, we need to propagate constants
+	     within the new basic blocks to fold away induction variable
+	     computations; otherwise, the size might blow up before the
+	     iteration is complete and the IR eventually cleaned up.  */
+	  if (iteration > 0)
+	    {
+	      unsigned i;
+	      basic_block *body = get_loop_body_in_dom_order (loop);
+	      for (i = 0; i < loop->num_nodes; i++)
+		propagate_constants_for_unrolling (body[i]);
+	      free (body);
+	    }
+
 	  if (may_increase_size && optimize_loop_for_speed_p (loop)
 	      /* Unroll outermost loops only if asked to do so or they do
 		 not cause code growth.  */
@@ -530,6 +585,7 @@ tree_unroll_loops_completely (bool may_i
 	    ul = UL_ALL;
 	  else
 	    ul = UL_NO_GROWTH;
+
 	  changed |= canonicalize_loop_induction_variables
 		       (loop, false, ul, !flag_tree_loop_ivcanon);
 	}

-- { dg-do compile }
-- { dg-options "-O2" }

package body Loop_Optimization12 is

  procedure Reset (S : Rec_Ptr) is
  begin
    for I in Enum1 loop
      S.F (I).all := (others =>
                       (others =>
                         (others =>
                           (others =>
                             (others =>
                               (others =>
                                 (others =>
                                   (others =>
                                    (others =>
                                      (others => 0))))))))));
    end loop;
  end;

end Loop_Optimization12;

package Loop_Optimization12 is

  type Enum1 is (A, B, C, D, E, F, G, H, I, J);

  type Enum2 is (A, B, C);

  type Enum3 is (A, B, C, D, E, F);

  type Enum4 is (A, B, C, D);

  type Enum5 is (A, B, C, D, E);

  type Arr is array (Enum3, Enum4, Enum4, Enum5, Enum5, Enum3,
                     Enum2, Enum3, Enum5, Enum3) of Natural;

  type Arr_Ptr is access Arr;
  type Ext_Arr is array (Enum1) of Arr_Ptr;

  type Rec is record
    F : Ext_Arr;
  end record;

  type Rec_Ptr is access Rec;

  procedure Reset (S : Rec_Ptr);

end Loop_Optimization12;