On 18 March 2019 10:58:53 CET, Richard Sandiford <richard.sandif...@arm.com>
wrote:
>This patch fixes a case in which we vectorised something with a
>fully-predicated loop even after the cost model had rejected it.
>E.g. the loop in the testcase has the costs:
>
> Vector inside of loop cost: 27
> Vector prologue cost: 0
> Vector epilogue cost: 0
> Scalar iteration cost: 7
> Scalar outside cost: 6
> Vector outside cost: 0
> prologue iterations: 0
> epilogue iterations: 0
>
>and we can see that the loop executes at most three times, but we
>decided to vectorise it anyway.
>
>(The costs here are equal for three iterations, but the same thing
>happens even when the vector code is strictly more expensive.)
>
>The problem is the handling of "/VF" in:
>
> /* Calculate number of iterations required to make the vector version
> profitable, relative to the loop bodies only. The following condition
> must hold true:
> SIC * niters + SOC > VIC * ((niters-PL_ITERS-EP_ITERS)/VF) + VOC
> where
> SIC = scalar iteration cost, VIC = vector iteration cost,
> VOC = vector outside cost, VF = vectorization factor,
> PL_ITERS = prologue iterations, EP_ITERS= epilogue iterations
> SOC = scalar outside cost for run time cost model check. */
>
>We treat the "/VF" as truncating, but for fully-predicated loops, it's
>closer to a ceil division, since fractional iterations are handled by a
>full iteration with some predicate bits set to false.
>
>The easiest fix seemed to be to calculate the minimum number of vector
>iterations first, then use that to calculate the minimum number of
>scalar
>iterations.
>
>Calculating the minimum number of vector iterations might make sense
>for
>unpredicated loops too, since calculating the scalar niters directly
>doesn't take into account the fact that the VIC multiple has to be an
>integer. But the handling of PL_ITERS and EP_ITERS for unpredicated
>loops is a bit hand-wavy anyway, so maybe vagueness here cancels out
>vagueness there?
>
>Either way, changing this for unpredicated loops would be much too
>invasive for stage 4, so the patch keeps it specific to
>fully-predicated
>loops (i.e. SVE) for now. There's no functional change for other
>targets.
>
>Tested on aarch64-linux-gnu with and without SVE, and on
>x86_64-linux-gnu.
>This is a regression introduced by the original cost model patches for
>fully-predicated loops, so OK for GCC 9?
>
>Thanks,
>Richard
>
>
>2019-03-18 Richard Sandiford <richard.sandif...@arm.com>
>
>gcc/
> * tree-vect-loop.c (vect_estimate_min_profitable_iters): Fix the
> calculation of the minimum number of scalar iterations for
> fully-predicated loops.
>
>gcc/testsuite/
> * gcc.target/aarch64/sve/cost_model_1.c: New test.
>
>Index: gcc/tree-vect-loop.c
>===================================================================
>--- gcc/tree-vect-loop.c 2019-03-08 18:15:33.668751875 +0000
>+++ gcc/tree-vect-loop.c 2019-03-18 09:55:03.257194326 +0000
>@@ -3600,14 +3600,89 @@ vect_estimate_min_profitable_iters (loop
> /* Calculate number of iterations required to make the vector version
> profitable, relative to the loop bodies only. The following condition
> must hold true:
>- SIC * niters + SOC > VIC * ((niters-PL_ITERS-EP_ITERS)/VF) + VOC
>+ SIC * niters + SOC > VIC * ((niters - NPEEL) / VF) + VOC
> where
> SIC = scalar iteration cost, VIC = vector iteration cost,
> VOC = vector outside cost, VF = vectorization factor,
>- PL_ITERS = prologue iterations, EP_ITERS= epilogue iterations
>+ NPEEL = prologue iterations + epilogue iterations,
> SOC = scalar outside cost for run time cost model check. */
>
>- if ((scalar_single_iter_cost * assumed_vf) > (int) vec_inside_cost)
>+ int saving_per_viter = (scalar_single_iter_cost * assumed_vf
>+ - vec_inside_cost);
>+ if (saving_per_viter <= 0)
>+ {
>+ if (LOOP_VINFO_LOOP (loop_vinfo)->force_vectorize)
>+ warning_at (vect_location.get_location_t (), OPT_Wopenmp_simd,
>+ "vectorization did not happen for a simd loop");
>+
>+ if (dump_enabled_p ())
>+ dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
>+ "cost model: the vector iteration cost = %d "
>+ "divided by the scalar iteration cost = %d "
>+ "is greater or equal to the vectorization factor = %d"
>+ ".\n",
>+ vec_inside_cost, scalar_single_iter_cost, assumed_vf);
>+ *ret_min_profitable_niters = -1;
>+ *ret_min_profitable_estimate = -1;
>+ return;
>+ }
>+
>+ /* ??? The "if" arm is written to handle all cases; see below for
>what
>+ we would do for !LOOP_VINFO_FULLY_MASKED_P. */
>+ if (LOOP_VINFO_FULLY_MASKED_P (loop_vinfo))
>+ {
The condition above seems to contain...
>+ /* Rewriting the condition above in terms of the number of
>+ vector iterations (vniters) rather than the number of
>+ scalar iterations (niters) gives:
>+
>+ SIC * (vniters * VF + NPEEL) + SOC > VIC * vniters + VOC
>+
>+ <==> vniters * (SIC * VF - VIC) > VOC - SIC * NPEEL - SOC
>+
>+ For integer N, X and Y when X > 0:
>+
>+ N * X > Y <==> N >= (Y /[floor] X) + 1. */
>+ int outside_overhead = (vec_outside_cost
>+ - scalar_single_iter_cost * peel_iters_prologue
>+ - scalar_single_iter_cost * peel_iters_epilogue
>+ - scalar_outside_cost);
>+ /* We're only interested in cases that require at least one
>+ vector iteration. */
>+ int min_vec_niters = 1;
>+ if (outside_overhead > 0)
>+ min_vec_niters = outside_overhead / saving_per_viter + 1;
>+
>+ if (dump_enabled_p ())
>+ dump_printf (MSG_NOTE, " Minimum number of vector iterations: %d\n",
>+ min_vec_niters);
>+
>+ if (LOOP_VINFO_FULLY_MASKED_P (loop_vinfo))
>+ {
... this identical condition, AFAICS?
So this second conditions else arm should be dead, shouldn't it?
thanks,
>+ /* Now that we know the minimum number of vector iterations,
>+ find the minimum niters for which the scalar cost is larger:
>+
>+ SIC * niters > VIC * vniters + VOC - SOC
>+
>+ We know that the minimum niters is no more than
>+ vniters * VF + NPEEL, but it might be (and often is) less
>+ than that if a partial vector iteration is cheaper than the
>+ equivalent scalar code. */
>+ int threshold = (vec_inside_cost * min_vec_niters
>+ + vec_outside_cost
>+ - scalar_outside_cost);
>+ if (threshold <= 0)
>+ min_profitable_iters = 1;
>+ else
>+ min_profitable_iters = threshold / scalar_single_iter_cost + 1;
>+ }
>+ else
>+ /* Convert the number of vector iterations into a number of
>+ scalar iterations. */
>+ min_profitable_iters = (min_vec_niters * assumed_vf
>+ + peel_iters_prologue
>+ + peel_iters_epilogue);
>+ }
>+ else
> {
> min_profitable_iters = ((vec_outside_cost - scalar_outside_cost)
> * assumed_vf
>@@ -3617,8 +3692,7 @@ vect_estimate_min_profitable_iters (loop
> min_profitable_iters = 0;
> else
> {
>- min_profitable_iters /= ((scalar_single_iter_cost * assumed_vf)
>- - vec_inside_cost);
>+ min_profitable_iters /= saving_per_viter;
>
> if ((scalar_single_iter_cost * assumed_vf * min_profitable_iters)
> <= (((int) vec_inside_cost * min_profitable_iters)
>@@ -3627,24 +3701,6 @@ vect_estimate_min_profitable_iters (loop
> min_profitable_iters++;
> }
> }
>- /* vector version will never be profitable. */
>- else
>- {
>- if (LOOP_VINFO_LOOP (loop_vinfo)->force_vectorize)
>- warning_at (vect_location.get_location_t (), OPT_Wopenmp_simd,
>- "vectorization did not happen for a simd loop");
>-
>- if (dump_enabled_p ())
>- dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
>- "cost model: the vector iteration cost = %d "
>- "divided by the scalar iteration cost = %d "
>- "is greater or equal to the vectorization factor = %d"
>- ".\n",
>- vec_inside_cost, scalar_single_iter_cost, assumed_vf);
>- *ret_min_profitable_niters = -1;
>- *ret_min_profitable_estimate = -1;
>- return;
>- }
>
> if (dump_enabled_p ())
> dump_printf (MSG_NOTE,
>@@ -3668,10 +3724,34 @@ vect_estimate_min_profitable_iters (loop
>
> Non-vectorized variant is SIC * niters and it must win over vector
>variant on the expected loop trip count. The following condition must
>hold true:
>- SIC * niters > VIC * ((niters-PL_ITERS-EP_ITERS)/VF) + VOC + SOC
>*/
>+ SIC * niters > VIC * ((niters - NPEEL) / VF) + VOC + SOC */
>
> if (vec_outside_cost <= 0)
> min_profitable_estimate = 0;
>+ else if (LOOP_VINFO_FULLY_MASKED_P (loop_vinfo))
>+ {
>+ /* This is a repeat of the code above, but with + SOC rather
>+ than - SOC. */
>+ int outside_overhead = (vec_outside_cost
>+ - scalar_single_iter_cost * peel_iters_prologue
>+ - scalar_single_iter_cost * peel_iters_epilogue
>+ + scalar_outside_cost);
>+ int min_vec_niters = 1;
>+ if (outside_overhead > 0)
>+ min_vec_niters = outside_overhead / saving_per_viter + 1;
>+
>+ if (LOOP_VINFO_FULLY_MASKED_P (loop_vinfo))
>+ {
>+ int threshold = (vec_inside_cost * min_vec_niters
>+ + vec_outside_cost
>+ + scalar_outside_cost);
>+ min_profitable_estimate = threshold / scalar_single_iter_cost + 1;
>+ }
>+ else
>+ min_profitable_estimate = (min_vec_niters * assumed_vf
>+ + peel_iters_prologue
>+ + peel_iters_epilogue);
>+ }
> else
> {
> min_profitable_estimate = ((vec_outside_cost + scalar_outside_cost)
>Index: gcc/testsuite/gcc.target/aarch64/sve/cost_model_1.c
>===================================================================
>--- /dev/null 2019-03-08 11:40:14.606883727 +0000
>+++ gcc/testsuite/gcc.target/aarch64/sve/cost_model_1.c 2019-03-18
>09:55:03.257194326 +0000
>@@ -0,0 +1,12 @@
>+/* { dg-options "-O2 -ftree-vectorize -fdump-tree-vect-details" } */
>+
>+void
>+f (unsigned int *restrict x, unsigned int *restrict y,
>+ unsigned char *restrict z, unsigned int n)
>+{
>+ for (unsigned int i = 0; i < n % 4; ++i)
>+ x[i] = x[i] + y[i] + z[i];
>+}
>+
>+/* { dg-final { scan-tree-dump "not vectorized: estimated iteration
>count too small" vect } } */
>+/* { dg-final { scan-tree-dump "vectorized 0 loops" vect } } */
