This is the mail archive of the
gcc-patches@gcc.gnu.org
mailing list for the GCC project.
[PATCH] Fix PR60841
- From: Richard Biener <rguenther at suse dot de>
- To: gcc-patches at gcc dot gnu dot org
- Date: Thu, 17 Apr 2014 10:03:03 +0200 (CEST)
- Subject: [PATCH] Fix PR60841
- Authentication-results: sourceware.org; auth=none
This fixes running into the exponential value-graph -> SLP tree
expansion by artificially limiting the overall SLP tree size.
Bootstrapped and tested on x86_64-unknown-linux-gnu, applied to trunk.
Richard.
2014-04-16 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.
Index: gcc/tree-vect-data-refs.c
===================================================================
--- gcc/tree-vect-data-refs.c (revision 209423)
+++ gcc/tree-vect-data-refs.c (working copy)
@@ -3172,7 +3213,7 @@ vect_check_gather (gimple stmt, loop_vec
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 +3248,9 @@ vect_analyze_data_refs (loop_vec_info lo
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 +3304,9 @@ vect_analyze_data_refs (loop_vec_info lo
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)))
{
Index: gcc/tree-vect-loop.c
===================================================================
--- gcc/tree-vect-loop.c (revision 209423)
+++ gcc/tree-vect-loop.c (working copy)
@@ -1629,6 +1629,7 @@ vect_analyze_loop_2 (loop_vec_info loop_
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_
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_
}
/* 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. */
Index: gcc/tree-vect-slp.c
===================================================================
--- gcc/tree-vect-slp.c (revision 209423)
+++ gcc/tree-vect-slp.c (working copy)
@@ -849,9 +849,10 @@ vect_build_slp_tree (loop_vec_info loop_
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_
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_
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_
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_
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 loo
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
/* 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
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_vin
/* 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_vin
{
/* 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_vin
/* 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,
Index: gcc/tree-vectorizer.h
===================================================================
--- gcc/tree-vectorizer.h (revision 209423)
+++ gcc/tree-vectorizer.h (working copy)
@@ -1057,7 +1057,8 @@ extern bool vect_analyze_data_ref_access
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_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,
Index: gcc/testsuite/gcc.dg/vect/pr60841.c
===================================================================
--- gcc/testsuite/gcc.dg/vect/pr60841.c (revision 0)
+++ gcc/testsuite/gcc.dg/vect/pr60841.c (working copy)
@@ -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" } } */