From 26d66f28fdb9bea6e05c2c9f9df7870f9d9f76b2 Mon Sep 17 00:00:00 2001 From: Richard Biener Date: Tue, 8 Aug 2017 12:49:39 +0000 Subject: re PR tree-optimization/81723 (fortran build doesn't terminate on 64bit targets) 2017-08-08 Richard Biener PR tree-optimization/81723 * tree-vect-slp.c (struct bst_traits): New hash traits. (bst_fail): New global. (vect_build_slp_tree_2): New worker, split out from ... (vect_build_slp_tree): ... this now wrapping it with using bst_fail set to cache SLP tree build fails. Properly handle max_tree_size. (vect_analyze_slp_instance): Allocate and free bst_fail. * gfortran.dg/pr81723.f: New testcase. From-SVN: r250953 --- gcc/tree-vect-slp.c | 87 +++++++++++++++++++++++++++++++++++++++++++++++++---- 1 file changed, 81 insertions(+), 6 deletions(-) (limited to 'gcc/tree-vect-slp.c') diff --git a/gcc/tree-vect-slp.c b/gcc/tree-vect-slp.c index 1334df3..04ecaab 100644 --- a/gcc/tree-vect-slp.c +++ b/gcc/tree-vect-slp.c @@ -908,12 +908,49 @@ vect_build_slp_tree_1 (vec_info *vinfo, unsigned char *swap, return true; } -/* Recursively build an SLP tree starting from NODE. - Fail (and return a value not equal to zero) if def-stmts are not - isomorphic, require data permutation or are of unsupported types of - operation. Otherwise, return 0. - The value returned is the depth in the SLP tree where a mismatch - was found. */ +/* Traits for the hash_set to record failed SLP builds for a stmt set. + Note we never remove apart from at destruction time so we do not + need a special value for deleted that differs from empty. */ +struct bst_traits +{ + typedef vec value_type; + typedef vec compare_type; + static inline hashval_t hash (value_type); + static inline bool equal (value_type existing, value_type candidate); + static inline bool is_empty (value_type x) { return !x.exists (); } + static inline bool is_deleted (value_type x) { return !x.exists (); } + static inline void mark_empty (value_type &x) { x.release (); } + static inline void mark_deleted (value_type &x) { x.release (); } + static inline void remove (value_type &x) { x.release (); } +}; +inline hashval_t +bst_traits::hash (value_type x) +{ + inchash::hash h; + for (unsigned i = 0; i < x.length (); ++i) + h.add_int (gimple_uid (x[i])); + return h.end (); +} +inline bool +bst_traits::equal (value_type existing, value_type candidate) +{ + if (existing.length () != candidate.length ()) + return false; + for (unsigned i = 0; i < existing.length (); ++i) + if (existing[i] != candidate[i]) + return false; + return true; +} + +static hash_set , bst_traits> *bst_fail; + +static slp_tree +vect_build_slp_tree_2 (vec_info *vinfo, + vec stmts, unsigned int group_size, + unsigned int *max_nunits, + vec *loads, + bool *matches, unsigned *npermutes, unsigned *tree_size, + unsigned max_tree_size); static slp_tree vect_build_slp_tree (vec_info *vinfo, @@ -923,6 +960,39 @@ vect_build_slp_tree (vec_info *vinfo, bool *matches, unsigned *npermutes, unsigned *tree_size, unsigned max_tree_size) { + if (bst_fail->contains (stmts)) + return NULL; + slp_tree res = vect_build_slp_tree_2 (vinfo, stmts, group_size, max_nunits, + loads, matches, npermutes, tree_size, + max_tree_size); + /* When SLP build fails for stmts record this, otherwise SLP build + can be exponential in time when we allow to construct parts from + scalars, see PR81723. */ + if (! res) + { + vec x; + x.create (stmts.length ()); + x.splice (stmts); + bst_fail->add (x); + } + return res; +} + +/* Recursively build an SLP tree starting from NODE. + Fail (and return a value not equal to zero) if def-stmts are not + isomorphic, require data permutation or are of unsupported types of + operation. Otherwise, return 0. + The value returned is the depth in the SLP tree where a mismatch + was found. */ + +static slp_tree +vect_build_slp_tree_2 (vec_info *vinfo, + vec stmts, unsigned int group_size, + unsigned int *max_nunits, + vec *loads, + bool *matches, unsigned *npermutes, unsigned *tree_size, + unsigned max_tree_size) +{ unsigned nops, i, this_tree_size = 0, this_max_nunits = *max_nunits; gimple *stmt; slp_tree node; @@ -1014,6 +1084,9 @@ vect_build_slp_tree (vec_info *vinfo, stmt = stmts[0]; + if (tree_size) + max_tree_size -= *tree_size; + /* Create SLP_TREE nodes for the definition node/s. */ FOR_EACH_VEC_ELT (oprnds_info, i, oprnd_info) { @@ -1933,9 +2006,11 @@ vect_analyze_slp_instance (vec_info *vinfo, /* Build the tree for the SLP instance. */ bool *matches = XALLOCAVEC (bool, group_size); unsigned npermutes = 0; + bst_fail = new hash_set , bst_traits> (); node = vect_build_slp_tree (vinfo, scalar_stmts, group_size, &max_nunits, &loads, matches, &npermutes, NULL, max_tree_size); + delete bst_fail; if (node != NULL) { /* Calculate the unrolling factor based on the smallest type. */ -- cgit v1.1