On Fri, 8 Jun 2012, William J. Schmidt wrote: > This patch adds a heuristic to the vectorizer when estimating the > minimum profitable number of iterations. The heuristic is > target-dependent, and is currently disabled for all targets except > PowerPC. However, the intent is to make it general enough to be useful > for other targets that want to opt in. > > A previous patch addressed some PowerPC SPEC degradations by modifying > the vector cost model values for vec_perm and vec_promote_demote. The > values were set a little higher than their natural values because the > natural values were not sufficient to prevent a poor vectorization > choice. However, this is not the right long-term solution, since it can > unnecessarily constrain other vectorization choices involving permute > instructions. > > Analysis of the badly vectorized loop (in sphinx3) showed that the > problem was overcommitment of vector resources -- too many vector > instructions issued without enough non-vector instructions available to > cover the delays. The vector cost model assumes that instructions > always have a constant cost, and doesn't have a way of judging this kind > of "density" of vector instructions. > > The present patch adds a heuristic to recognize when a loop is likely to > overcommit resources, and adds a small penalty to the inside-loop cost > to account for the expected stalls. The heuristic is parameterized with > three target-specific values: > > * Density threshold: The heuristic will apply only when the > percentage of inside-loop cost attributable to vectorized > instructions exceeds this value. > > * Size threshold: The heuristic will apply only when the > inside-loop cost exceeds this value. > > * Penalty: The inside-loop cost will be increased by this > percentage value when the heuristic applies. > > Thus only reasonably large loop bodies that are mostly vectorized > instructions will be affected. > > By applying only a small percentage bump to the inside-loop cost, the > heuristic will only turn off vectorization for loops that were > considered "barely profitable" to begin with (such as the sphinx3 loop). > So the heuristic is quite conservative and should not affect the vast > majority of vectorization decisions. > > Together with the new heuristic, this patch reduces the vec_perm and > vec_promote_demote costs for PowerPC to their natural values. > > I've regstrapped this with no regressions on powerpc64-unknown-linux-gnu > and verified that no performance regressions occur on SPEC cpu2006. Is > this ok for trunk?
Hmm. I don't like this patch or its general idea too much. Instead I'd like us to move more of the cost model detail to the target, giving it a chance to look at the whole loop before deciding on a cost. ISTR posting the overall idea at some point, but let me repeat it here instead of trying to find that e-mail. The basic interface of the cost model should be, in targetm.vectorize /* Tell the target to start cost analysis of a loop or a basic-block (if the loop argument is NULL). Returns an opaque pointer to target-private data. */ void *init_cost (struct loop *loop); /* Add cost for N vectorized-stmt-kind statements in vector_mode. */ void add_stmt_cost (void *data, unsigned n, vectorized-stmt-kind, enum machine_mode vector_mode); /* Tell the target to compute and return the cost of the accumulated statements and free any target-private data. */ unsigned finish_cost (void *data); with eventually slightly different signatures for add_stmt_cost (like pass in the original scalar stmt?). It allows the target, at finish_cost time, to evaluate things like register pressure and resource utilization. Thanks, Richard. > Thanks, > Bill > > > 2012-06-08 Bill Schmidt <wschm...@linux.ibm.com> > > * doc/tm.texi.in: Add vectorization density hooks. > * doc/tm.texi: Regenerate. > * targhooks.c (default_density_pct_threshold): New. > (default_density_size_threshold): New. > (default_density_penalty): New. > * targhooks.h: New decls for new targhooks.c functions. > * target.def (density_pct_threshold): New DEF_HOOK. > (density_size_threshold): Likewise. > (density_penalty): Likewise. > * tree-vect-loop.c (accum_stmt_cost): New. > (vect_estimate_min_profitable_iters): Perform density test. > * config/rs6000/rs6000.c (TARGET_VECTORIZE_DENSITY_PCT_THRESHOLD): > New macro definition. > (TARGET_VECTORIZE_DENSITY_SIZE_THRESHOLD): Likewise. > (TARGET_VECTORIZE_DENSITY_PENALTY): Likewise. > (rs6000_builtin_vectorization_cost): Reduce costs of vec_perm and > vec_promote_demote to correct values. > (rs6000_density_pct_threshold): New. > (rs6000_density_size_threshold): New. > (rs6000_density_penalty): New. > > > Index: gcc/doc/tm.texi > =================================================================== > --- gcc/doc/tm.texi (revision 188305) > +++ gcc/doc/tm.texi (working copy) > @@ -5798,6 +5798,27 @@ The default is @code{NULL_TREE} which means to not > loads. > @end deftypefn > > +@deftypefn {Target Hook} int TARGET_VECTORIZE_DENSITY_PCT_THRESHOLD (void) > +This hook should return the maximum density, expressed in percent, for > +which autovectorization of loops with large bodies should be constrained. > +See also @code{TARGET_VECTORIZE_DENSITY_SIZE_THRESHOLD}. The default > +is to return 100, which disables the density test. > +@end deftypefn > + > +@deftypefn {Target Hook} int TARGET_VECTORIZE_DENSITY_SIZE_THRESHOLD (void) > +This hook should return the minimum estimated size of a vectorized > +loop body for which the density test should apply. See also > +@code{TARGET_VECTORIZE_DENSITY_PCT_THRESHOLD}. The default is set > +to the unreasonable value of 1000000, which effectively disables > +the density test. > +@end deftypefn > + > +@deftypefn {Target Hook} int TARGET_VECTORIZE_DENSITY_PENALTY (void) > +This hook should return the penalty, expressed in percent, to be applied > +to the inside-of-loop vectorization costs for a loop failing the density > +test. The default is 10. > +@end deftypefn > + > @node Anchored Addresses > @section Anchored Addresses > @cindex anchored addresses > Index: gcc/doc/tm.texi.in > =================================================================== > --- gcc/doc/tm.texi.in (revision 188305) > +++ gcc/doc/tm.texi.in (working copy) > @@ -5730,6 +5730,27 @@ The default is @code{NULL_TREE} which means to not > loads. > @end deftypefn > > +@hook TARGET_VECTORIZE_DENSITY_PCT_THRESHOLD > +This hook should return the maximum density, expressed in percent, for > +which autovectorization of loops with large bodies should be constrained. > +See also @code{TARGET_VECTORIZE_DENSITY_SIZE_THRESHOLD}. The default > +is to return 100, which disables the density test. > +@end deftypefn > + > +@hook TARGET_VECTORIZE_DENSITY_SIZE_THRESHOLD > +This hook should return the minimum estimated size of a vectorized > +loop body for which the density test should apply. See also > +@code{TARGET_VECTORIZE_DENSITY_PCT_THRESHOLD}. The default is set > +to the unreasonable value of 1000000, which effectively disables > +the density test. > +@end deftypefn > + > +@hook TARGET_VECTORIZE_DENSITY_PENALTY > +This hook should return the penalty, expressed in percent, to be applied > +to the inside-of-loop vectorization costs for a loop failing the density > +test. The default is 10. > +@end deftypefn > + > @node Anchored Addresses > @section Anchored Addresses > @cindex anchored addresses > Index: gcc/targhooks.c > =================================================================== > --- gcc/targhooks.c (revision 188305) > +++ gcc/targhooks.c (working copy) > @@ -990,6 +990,33 @@ default_autovectorize_vector_sizes (void) > return 0; > } > > +/* By default, the density test for autovectorization is disabled by > + setting the minimum percentage to 100. */ > + > +int > +default_density_pct_threshold (void) > +{ > + return 100; > +} > + > +/* By default, the density size threshold for autovectorization is > + meaningless since the density test is disabled. An unreasonably > + large number is used to further inhibit the density test. */ > + > +int > +default_density_size_threshold (void) > +{ > + return 1000000; > +} > + > +/* By default, the density penalty for autovectorization is set to 10%. */ > + > +int > +default_density_penalty (void) > +{ > + return 10; > +} > + > /* Determine whether or not a pointer mode is valid. Assume defaults > of ptr_mode or Pmode - can be overridden. */ > bool > Index: gcc/targhooks.h > =================================================================== > --- gcc/targhooks.h (revision 188305) > +++ gcc/targhooks.h (working copy) > @@ -90,6 +90,9 @@ default_builtin_support_vector_misalignment (enum > int, bool); > extern enum machine_mode default_preferred_simd_mode (enum machine_mode > mode); > extern unsigned int default_autovectorize_vector_sizes (void); > +extern int default_density_pct_threshold (void); > +extern int default_density_size_threshold (void); > +extern int default_density_penalty (void); > > /* These are here, and not in hooks.[ch], because not all users of > hooks.h include tm.h, and thus we don't have CUMULATIVE_ARGS. */ > Index: gcc/target.def > =================================================================== > --- gcc/target.def (revision 188305) > +++ gcc/target.def (working copy) > @@ -1054,6 +1054,32 @@ DEFHOOK > (const_tree mem_vectype, const_tree index_type, int scale), > NULL) > > +/* Return the maximum density in percent for loop vectorization. */ > +DEFHOOK > +(density_pct_threshold, > +"", > +int, > +(void), > +default_density_pct_threshold) > + > +/* Return the minimum size of a loop iteration for applying the density > + test for loop vectorization. */ > +DEFHOOK > +(density_size_threshold, > +"", > +int, > +(void), > +default_density_size_threshold) > + > +/* Return the penalty in percent for vectorizing a loop failing the > + density test. */ > +DEFHOOK > +(density_penalty, > +"", > +int, > +(void), > +default_density_penalty) > + > HOOK_VECTOR_END (vectorize) > > #undef HOOK_PREFIX > Index: gcc/tree-vect-loop.c > =================================================================== > --- gcc/tree-vect-loop.c (revision 188305) > +++ gcc/tree-vect-loop.c (working copy) > @@ -2485,6 +2485,58 @@ vect_get_known_peeling_cost (loop_vec_info loop_vi > + peel_guard_costs; > } > > +/* Add the inside-loop cost of STMT to either *REL_COST or *IRREL_COST, > + depending on whether or not STMT will be vectorized. For vectorized > + statements, the inside-loop cost is as already computed. For other > + statements, assume a cost of one. */ > + > +static void > +accum_stmt_cost (gimple stmt, int *rel_cost, int *irrel_cost) > +{ > + stmt_vec_info stmt_info = vinfo_for_stmt (stmt); > + gimple pattern_stmt = STMT_VINFO_RELATED_STMT (stmt_info); > + gimple_seq pattern_def_seq; > + > + /* If the statement is irrelevant, but it has a related pattern > + statement that is relevant, process just the related statement. > + If the statement is relevant and it has a related pattern > + statement that is also relevant, process them both. */ > + if (!STMT_VINFO_RELEVANT_P (stmt_info) > + && !STMT_VINFO_LIVE_P (stmt_info)) > + { > + if (STMT_VINFO_IN_PATTERN_P (stmt_info) > + && pattern_stmt > + && (STMT_VINFO_RELEVANT_P (vinfo_for_stmt (pattern_stmt)) > + || STMT_VINFO_LIVE_P (vinfo_for_stmt (pattern_stmt)))) > + accum_stmt_cost (pattern_stmt, rel_cost, irrel_cost); > + else > + (*irrel_cost)++; > + } > + else if (STMT_VINFO_IN_PATTERN_P (stmt_info) > + && pattern_stmt > + && (STMT_VINFO_RELEVANT_P (vinfo_for_stmt (pattern_stmt)) > + || STMT_VINFO_LIVE_P (vinfo_for_stmt (pattern_stmt)))) > + accum_stmt_cost (pattern_stmt, rel_cost, irrel_cost); > + > + /* If we're looking at a pattern that has additional statements, > + count them as well. */ > + if (is_pattern_stmt_p (stmt_info) > + && (pattern_def_seq = STMT_VINFO_PATTERN_DEF_SEQ (stmt_info))) > + { > + gimple_stmt_iterator gsi; > + for (gsi = gsi_start (pattern_def_seq); !gsi_end_p (gsi); gsi_next > (&gsi)) > + { > + gimple pattern_def_stmt = gsi_stmt (gsi); > + if (STMT_VINFO_RELEVANT_P (vinfo_for_stmt (pattern_def_stmt)) > + || STMT_VINFO_LIVE_P (vinfo_for_stmt (pattern_def_stmt))) > + accum_stmt_cost (pattern_def_stmt, rel_cost, irrel_cost); > + } > + } > + > + /* Accumulate the inside-loop cost of this vectorizable statement. */ > + *rel_cost += STMT_VINFO_INSIDE_OF_LOOP_COST (stmt_info); > +} > + > /* Function vect_estimate_min_profitable_iters > > Return the number of iterations required for the vector version of the > @@ -2743,6 +2795,45 @@ vect_estimate_min_profitable_iters (loop_vec_info > vec_inside_cost += SLP_INSTANCE_INSIDE_OF_LOOP_COST (instance); > } > > + /* Test for likely overcommitment of vector hardware resources. If a > + loop iteration is relatively large, and too large a percentage of > + instructions in the loop are vectorized, the cost model may not > + adequately reflect delays from unavailable vector resources. > + Penalize vec_inside_cost for this case, using target-specific > + parameters. */ > + if (targetm.vectorize.density_pct_threshold () < 100) > + { > + int rel_cost = 0, irrel_cost = 0; > + int density_pct; > + > + for (i = 0; i < nbbs; i++) > + { > + basic_block bb = bbs[i]; > + gimple_stmt_iterator gsi; > + > + for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi)) > + { > + gimple stmt = gsi_stmt (gsi); > + accum_stmt_cost (stmt, &rel_cost, &irrel_cost); > + } > + } > + > + density_pct = (rel_cost * 100) / (rel_cost + irrel_cost); > + > + if (density_pct > targetm.vectorize.density_pct_threshold () > + && (rel_cost + irrel_cost > + > targetm.vectorize.density_size_threshold ())) > + { > + int penalty = targetm.vectorize.density_penalty (); > + vec_inside_cost = vec_inside_cost * (100 + penalty) / 100; > + if (vect_print_dump_info (REPORT_DETAILS)) > + fprintf (vect_dump, > + "density %d%%, cost %d exceeds threshold" > + ", penalizing inside-loop cost by %d%%.", > + density_pct, rel_cost + irrel_cost, penalty); > + } > + } > + > /* Calculate number of iterations required to make the vector version > profitable, relative to the loop bodies only. The following condition > must hold true: > Index: gcc/config/rs6000/rs6000.c > =================================================================== > --- gcc/config/rs6000/rs6000.c (revision 188305) > +++ gcc/config/rs6000/rs6000.c (working copy) > @@ -1289,6 +1289,15 @@ static const struct attribute_spec rs6000_attribut > #undef TARGET_VECTORIZE_PREFERRED_SIMD_MODE > #define TARGET_VECTORIZE_PREFERRED_SIMD_MODE \ > rs6000_preferred_simd_mode > +#undef TARGET_VECTORIZE_DENSITY_PCT_THRESHOLD > +#define TARGET_VECTORIZE_DENSITY_PCT_THRESHOLD \ > + rs6000_density_pct_threshold > +#undef TARGET_VECTORIZE_DENSITY_SIZE_THRESHOLD > +#define TARGET_VECTORIZE_DENSITY_SIZE_THRESHOLD \ > + rs6000_density_size_threshold > +#undef TARGET_VECTORIZE_DENSITY_PENALTY > +#define TARGET_VECTORIZE_DENSITY_PENALTY \ > + rs6000_density_penalty > > #undef TARGET_INIT_BUILTINS > #define TARGET_INIT_BUILTINS rs6000_init_builtins > @@ -3421,13 +3430,13 @@ rs6000_builtin_vectorization_cost (enum vect_cost_ > > case vec_perm: > if (TARGET_VSX) > - return 4; > + return 3; > else > return 1; > > case vec_promote_demote: > if (TARGET_VSX) > - return 5; > + return 4; > else > return 1; > > @@ -3551,6 +3560,30 @@ rs6000_preferred_simd_mode (enum machine_mode mode > return word_mode; > } > > +/* Implement targetm.vectorize.density_pct_threshold. */ > + > +static int > +rs6000_density_pct_threshold (void) > +{ > + return 85; > +} > + > +/* Implement targetm.vectorize.density_size_threshold. */ > + > +static int > +rs6000_density_size_threshold (void) > +{ > + return 70; > +} > + > +/* Implement targetm.vectorize.density_penalty. */ > + > +static int > +rs6000_density_penalty (void) > +{ > + return 10; > +} > + > /* Handler for the Mathematical Acceleration Subsystem (mass) interface to a > library with vectorized intrinsics. */ > > > > -- Richard Guenther <rguent...@suse.de> SUSE / SUSE Labs SUSE LINUX Products GmbH - Nuernberg - AG Nuernberg - HRB 16746 GF: Jeff Hawn, Jennifer Guild, Felix Imendörffer