re PR tree-optimization/60841 (gcc: internal compiler error: Killed (program cc1) out of memory)

2014-04-17   Richard Biener  <rguenther@suse.de>

	PR tree-optimization/60841
	* tree-vect-data-refs.c (vect_analyze_data_refs): Count stmts.
	* tree-vect-loop.c (vect_analyze_loop_2): Pass down number
	of stmts to SLP build.
	* tree-vect-slp.c (vect_slp_analyze_bb_1): Likewise.
	(vect_analyze_slp): Likewise.
	(vect_analyze_slp_instance): Likewise.
	(vect_build_slp_tree): Limit overall SLP tree growth.
	* tree-vectorizer.h (vect_analyze_data_refs,
	vect_analyze_slp): Adjust prototypes.

	* gcc.dg/vect/pr60841.c: New testcase.

From-SVN: r209467

7 files changed, 244 insertions, 17 deletions

diff --git a/gcc/ChangeLog b/gcc/ChangeLog
index 320e15a..a8664ea 100644
--- a/gcc/ChangeLog
+++ b/gcc/ChangeLog
@@ -1,3 +1,16 @@
+2014-04-17   Richard Biener  <rguenther@suse.de>
+
+	PR tree-optimization/60841
+	* tree-vect-data-refs.c (vect_analyze_data_refs): Count stmts.
+	* tree-vect-loop.c (vect_analyze_loop_2): Pass down number
+	of stmts to SLP build.
+	* tree-vect-slp.c (vect_slp_analyze_bb_1): Likewise.
+	(vect_analyze_slp): Likewise.
+	(vect_analyze_slp_instance): Likewise.
+	(vect_build_slp_tree): Limit overall SLP tree growth.
+	* tree-vectorizer.h (vect_analyze_data_refs,
+	vect_analyze_slp): Adjust prototypes.
+
 2014-04-17  Evgeny Stupachenko  <evstupac@gmail.com>
 
 	* config/i386/i386.c (x86_add_stmt_cost): Fix vector cost model for
diff --git a/gcc/testsuite/ChangeLog b/gcc/testsuite/ChangeLog
index b8d40b7..7e9b599 100644
--- a/gcc/testsuite/ChangeLog
+++ b/gcc/testsuite/ChangeLog
@@ -1,3 +1,8 @@
+2014-04-17   Richard Biener  <rguenther@suse.de>
+
+	PR tree-optimization/60841
+	* gcc.dg/vect/pr60841.c: New testcase.
+
 2014-04-16  Jan Hubicka  <hubicka@ucw.cz>
 
 	* g++.dg/ipa/devirt-31.C: New testcase.
diff --git a/gcc/testsuite/gcc.dg/vect/pr60841.c b/gcc/testsuite/gcc.dg/vect/pr60841.c
new file mode 100644
index 0000000..44b5d01
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/vect/pr60841.c
@@ -0,0 +1,183 @@
+/* { dg-do compile } */
+/* { dg-additional-options "-ffast-math" } */
+
+/* This testcase shouldn't consume much memory or produce a 1GB vectorizer
+   dump file due to SLP tree explosion.  */
+
+struct S { int f1, f2, f3, f4; } a;
+struct T { short f3, f2, f1, f4; };
+int b, c, d, e, f, g;
+unsigned long z;
+
+void
+foo (struct T *p, struct T *q, int x, int w)
+{
+  for (; x; x++)
+    {
+      struct S h;
+      int i;
+      struct T j;
+      struct T *r;
+      h = a;
+      g = 0;
+      r = p + 2 * (c + 4) + 1;
+      j = *r;
+      r = p;
+      f = r->f1 - 1;
+      b = +1.0 + f * f;
+      i = (r->f2 + j.f2) / 2;
+      f = r->f3 - 1;
+      b += 1.0 - i * f * f;
+      f = r->f4 - 1;
+      if (b)
+	b += -1.0 - i * f;
+      if (b / w)
+	{
+	  h.f1 += 8.0 * r->f1;
+	  h.f2 += 8.0 * r->f2;
+	  h.f3 += 8.0 * r->f3;
+	  h.f4 += 8.0 * r->f4;
+	  g = 1;
+	}
+      r++;
+      f = r->f1;
+      i = (r->f2 + j.f2) / 2;
+      f = r->f3 - 1;
+      b += 1.0 - i * f * f;
+      i = (r->f4);
+      if (b * 65535UL / w)
+	{
+	  h.f1 += 10.0 * r->f1;
+	  h.f2 += 10.0 * r->f2;
+	  h.f3 += 10.0 * r->f3;
+	  h.f4 += 10.0 * r->f4;
+	  g += 10.0;
+	}
+      r++;
+      f = r->f1;
+      z = 5UL * i;
+      f = r->f2;
+      i = (r->f3 + j.f3) / 2;
+      b = -i * f * f;
+      i = (r->f4 + j.f4) / 2;
+      if (b * 65535UL / 25.0f)
+	{
+	  h.f1 += 8.0 * r->f1;
+	  h.f2 += 8.0 * r->f2;
+	  h.f3 += 8.0 * r->f3;
+	  h.f4 += 8.0 * r->f4;
+	  g += 8.0;
+	}
+      r++;
+      f = r->f1 - j.f1;
+      b = 1 * 2.0 * i * f * f;
+      f = r->f2;
+      b += 4.0 * f;
+      i = r->f3 / 2;
+      f = r->f4 - 1;
+      if (b * 1)
+	{
+	  h.f1 += 8.0 * r->f1;
+	  h.f2 += 8.0 * r->f2;
+	  h.f3 += 8.0 * r->f3;
+	  h.f4 += 8.0 * r->f4;
+	  g += 8.0;
+	}
+      b = 4.0 * 1 * f;
+      if (b * 65535UL / 25.0f)
+	{
+	  h.f1 += 20.0 * r->f1;
+	  h.f2 += 20.0 * r->f2;
+	  h.f3 += 20.0 * r->f3;
+	  h.f4 += 20.0 * r->f4;
+	  g += 20.0;
+	}
+      b = 5 * (0.0 - i);
+      if (b < 0)
+	{
+	  h.f1 += 8.0 * r->f1;
+	  h.f2 += 8.0 * r->f2;
+	  h.f3 += 8.0 * r->f3;
+	  h.f4 += 8.0 * r->f4;
+	  g += 8.0;
+	}
+      r = p + 2 * (c + 4);
+      i = (r->f1 + j.f1);
+      b = 1 * 2.0 * i * 1;
+      f = r->f2 - 1;
+      i = (r->f3 + j.f3) / 2;
+      b = 5 * (0.0 - i) * f * f;
+      i = (r->f4 + j.f4) / 2;
+      if (b * 65535UL / 25.0f)
+	{
+	  h.f1 += 10.0 * r->f1;
+	  h.f2 += 10.0 * r->f2;
+	  h.f3 += 10.0 * r->f3;
+	  h.f4 += 10.0 * r->f4;
+	  g += 10.0;
+	}
+      r++;
+      f = r->f1;
+      b = 5UL * i * f;
+      i = (r->f2 + j.f2) / 2;
+      f = r->f3 - 1;
+      b = 5 * (0.0 - i) * f * f;
+      f = r->f4 - 1;
+      if (b * 65535UL / 25.0f)
+	{
+	  h.f1 += 40.0 * r->f1;
+	  h.f2 += 40.0 * r->f2;
+	  h.f3 += 40.0 * r->f3;
+	  h.f4 += 40.0 * r->f4;
+	  g += 40.0;
+	}
+      r++;
+      i = (r->f1 + j.f1);
+      b = 5 * i * f;
+      f = r->f2;
+      b = 4.0 * f * f;
+      f = r->f3;
+      i = (r->f4 + j.f4) / 2;
+      b = 5 * (0.0 - i) * f * f;
+      if (b * 25.0f)
+	{
+	  h.f1 += 8.0 * r->f1;
+	  h.f2 += 8.0 * r->f2;
+	  h.f3 += 8.0 * r->f3;
+	  h.f4 += 8.0 * r->f4;
+	  g += 8.0;
+	}
+      r = p + 4 * (c + 4);
+      i = r->f1 / 2;
+      b = 5 * (1.0 + i);
+      i = r->f2 + j.f2;
+      f = r->f3 - 1;
+      b = 5 * (0.0 - i) * f * f;
+      i = (r->f4 + j.f4) / 2;
+      if (b * 65535UL / 25.0f)
+	{
+	  h.f1 += 5.0 * r->f1;
+	  h.f2 += 5.0 * r->f2;
+	  h.f3 += 5.0 * r->f3;
+	  h.f4 += 5.0 * r->f4;
+	  g += 5.0;
+	}
+      b = 5 * (1.0 + i);
+      if (b < 0)
+	{
+	  h.f1 += 5.0 * r->f1;
+	  h.f2 += 5.0 * r->f2;
+	  h.f3 += 5.0 * r->f3;
+	  h.f4 += 5.0 * r->f4;
+	  g += 5.0;
+	}
+      q->f1 = (h.f1 + g / 2 - 1) / g;
+      q->f2 = (h.f2 + g / 2 - 1) / g;
+      q->f3 = (h.f3 + g / 2 - 1) / g;
+      q->f4 = (h.f4 + g / 2 - 1) / g;
+      p++;
+      q++;
+    }
+}
+
+/* { dg-final { cleanup-tree-dump "vect" } } */
diff --git a/gcc/tree-vect-data-refs.c b/gcc/tree-vect-data-refs.c
index fbc35a3..274cdbd 100644
--- a/gcc/tree-vect-data-refs.c
+++ b/gcc/tree-vect-data-refs.c
@@ -3172,7 +3172,7 @@ vect_check_gather (gimple stmt, loop_vec_info loop_vinfo, tree *basep,
 bool
 vect_analyze_data_refs (loop_vec_info loop_vinfo,
 			bb_vec_info bb_vinfo,
-			int *min_vf)
+			int *min_vf, unsigned *n_stmts)
 {
   struct loop *loop = NULL;
   basic_block bb = NULL;
@@ -3207,6 +3207,9 @@ vect_analyze_data_refs (loop_vec_info loop_vinfo,
 	  for (gsi = gsi_start_bb (bbs[i]); !gsi_end_p (gsi); gsi_next (&gsi))
 	    {
 	      gimple stmt = gsi_stmt (gsi);
+	      if (is_gimple_debug (stmt))
+		continue;
+	      ++*n_stmts;
 	      if (!find_data_references_in_stmt (loop, stmt, &datarefs))
 		{
 		  if (is_gimple_call (stmt) && loop->safelen)
@@ -3260,6 +3263,9 @@ vect_analyze_data_refs (loop_vec_info loop_vinfo,
       for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
 	{
 	  gimple stmt = gsi_stmt (gsi);
+	  if (is_gimple_debug (stmt))
+	    continue;
+	  ++*n_stmts;
 	  if (!find_data_references_in_stmt (NULL, stmt,
 					     &BB_VINFO_DATAREFS (bb_vinfo)))
 	    {
diff --git a/gcc/tree-vect-loop.c b/gcc/tree-vect-loop.c
index def3bc4..7ec079a 100644
--- a/gcc/tree-vect-loop.c
+++ b/gcc/tree-vect-loop.c
@@ -1629,6 +1629,7 @@ vect_analyze_loop_2 (loop_vec_info loop_vinfo)
   int max_vf = MAX_VECTORIZATION_FACTOR;
   int min_vf = 2;
   unsigned int th;
+  unsigned int n_stmts = 0;
 
   /* Find all data references in the loop (which correspond to vdefs/vuses)
      and analyze their evolution in the loop.  Also adjust the minimal
@@ -1637,7 +1638,7 @@ vect_analyze_loop_2 (loop_vec_info loop_vinfo)
      FORNOW: Handle only simple, array references, which
      alignment can be forced, and aligned pointer-references.  */
 
-  ok = vect_analyze_data_refs (loop_vinfo, NULL, &min_vf);
+  ok = vect_analyze_data_refs (loop_vinfo, NULL, &min_vf, &n_stmts);
   if (!ok)
     {
       if (dump_enabled_p ())
@@ -1747,7 +1748,7 @@ vect_analyze_loop_2 (loop_vec_info loop_vinfo)
     }
 
   /* Check the SLP opportunities in the loop, analyze and build SLP trees.  */
-  ok = vect_analyze_slp (loop_vinfo, NULL);
+  ok = vect_analyze_slp (loop_vinfo, NULL, n_stmts);
   if (ok)
     {
       /* Decide which possible SLP instances to SLP.  */
diff --git a/gcc/tree-vect-slp.c b/gcc/tree-vect-slp.c
index 65f8b02..0ab267f 100644
--- a/gcc/tree-vect-slp.c
+++ b/gcc/tree-vect-slp.c
@@ -849,9 +849,10 @@ vect_build_slp_tree (loop_vec_info loop_vinfo, bb_vec_info bb_vinfo,
                      unsigned int *max_nunits,
                      vec<slp_tree> *loads,
                      unsigned int vectorization_factor,
-		     bool *matches, unsigned *npermutes)
+		     bool *matches, unsigned *npermutes, unsigned *tree_size,
+		     unsigned max_tree_size)
 {
-  unsigned nops, i, this_npermutes = 0;
+  unsigned nops, i, this_npermutes = 0, this_tree_size = 0;
   gimple stmt;
 
   if (!matches)
@@ -911,6 +912,12 @@ vect_build_slp_tree (loop_vec_info loop_vinfo, bb_vec_info bb_vinfo,
       if (oprnd_info->first_dt != vect_internal_def)
         continue;
 
+      if (++this_tree_size > max_tree_size)
+	{
+	  vect_free_oprnd_info (oprnds_info);
+	  return false;
+	}
+
       child = vect_create_new_slp_node (oprnd_info->def_stmts);
       if (!child)
 	{
@@ -921,7 +928,8 @@ vect_build_slp_tree (loop_vec_info loop_vinfo, bb_vec_info bb_vinfo,
       bool *matches = XALLOCAVEC (bool, group_size);
       if (vect_build_slp_tree (loop_vinfo, bb_vinfo, &child,
 			       group_size, max_nunits, loads,
-			       vectorization_factor, matches, npermutes))
+			       vectorization_factor, matches,
+			       npermutes, &this_tree_size, max_tree_size))
 	{
 	  oprnd_info->def_stmts = vNULL;
 	  SLP_TREE_CHILDREN (*node).quick_push (child);
@@ -961,7 +969,8 @@ vect_build_slp_tree (loop_vec_info loop_vinfo, bb_vec_info bb_vinfo,
 	  if (vect_build_slp_tree (loop_vinfo, bb_vinfo, &child,
 				   group_size, max_nunits, loads,
 				   vectorization_factor,
-				   matches, npermutes))
+				   matches, npermutes, &this_tree_size,
+				   max_tree_size))
 	    {
 	      oprnd_info->def_stmts = vNULL;
 	      SLP_TREE_CHILDREN (*node).quick_push (child);
@@ -977,6 +986,9 @@ vect_build_slp_tree (loop_vec_info loop_vinfo, bb_vec_info bb_vinfo,
       return false;
     }
 
+  if (tree_size)
+    *tree_size += this_tree_size;
+
   vect_free_oprnd_info (oprnds_info);
   return true;
 }
@@ -1436,7 +1448,7 @@ vect_analyze_slp_cost (loop_vec_info loop_vinfo, bb_vec_info bb_vinfo,
 
 static bool
 vect_analyze_slp_instance (loop_vec_info loop_vinfo, bb_vec_info bb_vinfo,
-                           gimple stmt)
+                           gimple stmt, unsigned max_tree_size)
 {
   slp_instance new_instance;
   slp_tree node;
@@ -1536,7 +1548,8 @@ vect_analyze_slp_instance (loop_vec_info loop_vinfo, bb_vec_info bb_vinfo,
   /* Build the tree for the SLP instance.  */
   if (vect_build_slp_tree (loop_vinfo, bb_vinfo, &node, group_size,
 			   &max_nunits, &loads,
-			   vectorization_factor, NULL, NULL))
+			   vectorization_factor, NULL, NULL, NULL,
+			   max_tree_size))
     {
       /* Calculate the unrolling factor based on the smallest type.  */
       if (max_nunits > nunits)
@@ -1641,7 +1654,8 @@ vect_analyze_slp_instance (loop_vec_info loop_vinfo, bb_vec_info bb_vinfo,
    trees of packed scalar stmts if SLP is possible.  */
 
 bool
-vect_analyze_slp (loop_vec_info loop_vinfo, bb_vec_info bb_vinfo)
+vect_analyze_slp (loop_vec_info loop_vinfo, bb_vec_info bb_vinfo,
+		  unsigned max_tree_size)
 {
   unsigned int i;
   vec<gimple> grouped_stores;
@@ -1664,7 +1678,8 @@ vect_analyze_slp (loop_vec_info loop_vinfo, bb_vec_info bb_vinfo)
 
   /* Find SLP sequences starting from groups of grouped stores.  */
   FOR_EACH_VEC_ELT (grouped_stores, i, first_element)
-    if (vect_analyze_slp_instance (loop_vinfo, bb_vinfo, first_element))
+    if (vect_analyze_slp_instance (loop_vinfo, bb_vinfo, first_element,
+				   max_tree_size))
       ok = true;
 
   if (bb_vinfo && !ok)
@@ -1681,7 +1696,8 @@ vect_analyze_slp (loop_vec_info loop_vinfo, bb_vec_info bb_vinfo)
     {
       /* Find SLP sequences starting from reduction chains.  */
       FOR_EACH_VEC_ELT (reduc_chains, i, first_element)
-        if (vect_analyze_slp_instance (loop_vinfo, bb_vinfo, first_element))
+        if (vect_analyze_slp_instance (loop_vinfo, bb_vinfo, first_element,
+				       max_tree_size))
           ok = true;
         else
           return false;
@@ -1693,7 +1709,8 @@ vect_analyze_slp (loop_vec_info loop_vinfo, bb_vec_info bb_vinfo)
 
   /* Find SLP sequences starting from groups of reductions.  */
   if (loop_vinfo && LOOP_VINFO_REDUCTIONS (loop_vinfo).length () > 1
-      && vect_analyze_slp_instance (loop_vinfo, bb_vinfo, reductions[0]))
+      && vect_analyze_slp_instance (loop_vinfo, bb_vinfo, reductions[0],
+				    max_tree_size))
     ok = true;
 
   return true;
@@ -2071,12 +2088,13 @@ vect_slp_analyze_bb_1 (basic_block bb)
   slp_instance instance;
   int i;
   int min_vf = 2;
+  unsigned n_stmts = 0;
 
   bb_vinfo = new_bb_vec_info (bb);
   if (!bb_vinfo)
     return NULL;
 
-  if (!vect_analyze_data_refs (NULL, bb_vinfo, &min_vf))
+  if (!vect_analyze_data_refs (NULL, bb_vinfo, &min_vf, &n_stmts))
     {
       if (dump_enabled_p ())
         dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
@@ -2124,7 +2142,7 @@ vect_slp_analyze_bb_1 (basic_block bb)
 
   /* Check the SLP opportunities in the basic block, analyze and build SLP
      trees.  */
-  if (!vect_analyze_slp (NULL, bb_vinfo))
+  if (!vect_analyze_slp (NULL, bb_vinfo, n_stmts))
     {
       if (dump_enabled_p ())
         dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location, 
diff --git a/gcc/tree-vectorizer.h b/gcc/tree-vectorizer.h
index 035d654..c5cb037 100644
--- a/gcc/tree-vectorizer.h
+++ b/gcc/tree-vectorizer.h
@@ -1057,7 +1057,8 @@ extern bool vect_analyze_data_ref_accesses (loop_vec_info, bb_vec_info);
 extern bool vect_prune_runtime_alias_test_list (loop_vec_info);
 extern tree vect_check_gather (gimple, loop_vec_info, tree *, tree *,
 			       int *);
-extern bool vect_analyze_data_refs (loop_vec_info, bb_vec_info, int *);
+extern bool vect_analyze_data_refs (loop_vec_info, bb_vec_info, int *,
+				    unsigned *);
 extern tree vect_create_data_ref_ptr (gimple, tree, struct loop *, tree,
 				      tree *, gimple_stmt_iterator *,
 				      gimple *, bool, bool *);
@@ -1107,7 +1108,7 @@ extern bool vect_transform_slp_perm_load (slp_tree, vec<tree> ,
                                           slp_instance, bool);
 extern bool vect_schedule_slp (loop_vec_info, bb_vec_info);
 extern void vect_update_slp_costs_according_to_vf (loop_vec_info);
-extern bool vect_analyze_slp (loop_vec_info, bb_vec_info);
+extern bool vect_analyze_slp (loop_vec_info, bb_vec_info, unsigned);
 extern bool vect_make_slp_decision (loop_vec_info);
 extern void vect_detect_hybrid_slp (loop_vec_info);
 extern void vect_get_slp_defs (vec<tree> , slp_tree,