Re: [RFC] Make vectorizer to skip loops with small iteration estimate

[Richard Guenther <rguenther at suse dot de>]

On Sun, 30 Sep 2012, Jan Hubicka wrote:

> Hi,
> the point of the following patch is to make vectorizer to not vectorize the
> following testcase with profile feedback:
> 
> int a[10000];
> int i=500000000;
> int k=2;
> int val;
> __attribute__ ((noinline,noclone))
> test()
> {
>   int j;
>   for(j=0;j<k;j++)
>     a[j]=val;
> }
> main()
> {
>   while (i)
>     {
>       test ();
>       i--;
>     }
> }
> 
> Here the compiler should work out that the second loop iterates 2 times at the
> average and thus it is not good candidate for vectorizing.
> 
> In my first attempt I added the following:
> @@ -1474,6 +1478,18 @@ vect_analyze_loop_operations (loop_vec_i
>        return false;
>      }
>  
> +  if ((estimated_niter = estimated_stmt_executions_int (loop)) != -1
> +      && (unsigned HOST_WIDE_INT) estimated_niter <= th)
> +    {
> +      if (vect_print_dump_info (REPORT_UNVECTORIZED_LOCATIONS))
> +        fprintf (vect_dump, "not vectorized: estimated iteration count too small.");
> +      if (vect_print_dump_info (REPORT_DETAILS))
> +        fprintf (vect_dump, "not vectorized: estimated iteration count smaller than "
> +                 "user specified loop bound parameter or minimum "
> +                 "profitable iterations (whichever is more conservative).");
> +      return false;
> +    }
> +
> 
> But to my surprise it does not help.  There are two things:
> 
> 1) the value of TH is bit low.  In a way the cost model works is that
>    it finds minimal niters where vectorized loop with all the setup costs
>    is cheaper than the vector loop with all the setup costs.  I.e.
> 
>   /* 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    (A)
>      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.  */
> 
>     This value is used for both
>     1) decision if number of iterations is too low (max iterations is known)
>     2) decision on runtime whether we want to take the vectorized path
>     or the scalar path.
> 
>     The vectoried loop looks like:
>       k.1_10 = k;
>       if (k.1_10 > 0)
> 	{
> 	  pretmp_2 = val;
> 	  niters.8_4 = (unsigned int) k.1_10;
> 	  bnd.9_13 = niters.8_4 >> 2;
> 	  ratio_mult_vf.10_1 = bnd.9_13 << 2;
> 	  _18 = niters.8_4 <= 3;
> 	  _19 = ratio_mult_vf.10_1 == 0;
> 	  _20 = _19 | _18;
> 	  if (_20 != 0)
> 	    scalar loop
> 	  else
> 	    vector prologue
> 	}
> 
>      So the unvectorized cost is
>      SIC * niters
> 
>      The vectorized path is
>      SOC + VIC * ((niters-PL_ITERS-EP_ITERS)/VF) + VOC
>      The scalar path of vectorizer loop is
>      SIC * niters + SOC

Note that 'th' is used for the runtime profitability check which is
done at the time the setup cost has already been taken (yes, we
probably should make it more conservative but then guard the whole
set of loops by the check, not only the vectorized path).
See PR53355 for the general issue.

>    It makes sense to vectorize if
>    SIC * niters > SOC + VIC * ((niters-PL_ITERS-EP_ITERS)/VF) + VOC   (B)
>    That is in the optimal cse where we actually vectorize the overall
>    speed of vectorized loop including the runtime check is better.
> 
>    It makes sense to take the vector loop if
>    SIC * niters > VIC * ((niters-PL_ITERS-EP_ITERS)/VF) + VOC         (C)
>    Because the scalar loop is taken.
> 
>    The attached patch implements the formula (C) and uses it to deterine the
>    decision based on number of iterations estimate (that is usually provided by
>    the feedback)
> 
>    As a reality check, I tried my testcase.
> 
>    9: Cost model analysis:
>      Vector inside of loop cost: 1
>      Vector prologue cost: 7
>      Vector epilogue cost: 2
>      Scalar iteration cost: 1
>      Scalar outside cost: 6
>      Vector outside cost: 9
>      prologue iterations: 0
>      epilogue iterations: 2
>      Calculated minimum iters for profitability: 4
> 
>    9:   Profitability threshold = 3
> 
>    9:   Profitability estimated iterations threshold = 20
> 
>    This is overrated. The loop starts to be benefical at about 4 iterations in
>    reality.  I guess the values are kind of wrong.
> 
>    Vector inside of loop cost and Scalar iteration cost seems to ignore the
>    fact that the loops do contain some control flow that should account at least
>    one extra cycle.
> 
>    Vector prologue cost seems bit overrated for one pack operation.
> 
>    Of course this is very simple benchmark, in reality the vectorizatoin can be
>    a lot more harmful by complicating more complex control flows.
>
>    So I guess we have two options
>     1) go with the new formula and try to make cost model a bit more realistic.
>     2) stay with original formula that is quite close to reality, but I think
>        more by an accident.

I think we need to improve it as whole, thus I'd prefer 2).

> 2) Even when loop iterates 2 times, it is estimated to 4 iterations by
>    estimated_stmt_executions_int with the profile feedback.
>    The reason is loop_ch pass.  Given a rolled loop with exit probability
>    30%, proceeds by duplicating the header with original probabilities.
>    This makes the loop to be executed with 60% probability.  Because the
>    loop body counts remain the same (and they should), the expected number
>    of iterations increase by the decrease of entry edge to the header.
> 
>    I wonder what to do about this.  Obviously without path profiling
>    loop_ch can not really do a good job.  We can artifically make
>    header to suceed more likely, that is the reality, but that requires
>    non-trivial loop profile updating.
> 
>    We can also simply record the iteration bound into loop structure 
>    and ignore that the profile is not realistic

But we don't preserve loop structure from header copying ...

>    Finally we can duplicate loop headers before profilng.  I implemented
>    that via early_ch pass executed only with profile generation or feedback.
>    I guess it makes sense to do, even if it breaks the assumption that
>    we should do strictly -Os generation on paths where

Well, there are CH cases that do not increase code size and I doubt
that loop header copying is generally bad for -Os ... we are not
good at handling non-copied loop headers.

Btw, I added a "similar" check in vect_analyze_loop_operations:

  if ((LOOP_VINFO_NITERS_KNOWN_P (loop_vinfo)
       && (LOOP_VINFO_INT_NITERS (loop_vinfo) < vectorization_factor))
      || ((max_niter = max_stmt_executions_int (loop)) != -1
          && (unsigned HOST_WIDE_INT) max_niter < vectorization_factor))
    {
      if (dump_kind_p (MSG_MISSED_OPTIMIZATION))
        dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
                         "not vectorized: iteration count too small.");
      if (dump_kind_p (MSG_MISSED_OPTIMIZATION))
        dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
                         "not vectorized: iteration count smaller than "
                         "vectorization factor.");
      return false;
    }

maybe you simply need to update that to also consider the profile?


> Index: tree-vect-loop.c
> ===================================================================
> --- tree-vect-loop.c	(revision 191852)
> +++ tree-vect-loop.c	(working copy)
> @@ -1243,6 +1243,8 @@ vect_analyze_loop_operations (loop_vec_i
>    unsigned int th;
>    bool only_slp_in_loop = true, ok;
>    HOST_WIDE_INT max_niter;
> +  HOST_WIDE_INT estimated_niter;
> +  int min_profitable_estimate;
>  
>    if (vect_print_dump_info (REPORT_DETAILS))
>      fprintf (vect_dump, "=== vect_analyze_loop_operations ===");
> @@ -1436,7 +1438,8 @@ vect_analyze_loop_operations (loop_vec_i
>       vector stmts depends on VF.  */
>    vect_update_slp_costs_according_to_vf (loop_vinfo);
>  
> -  min_profitable_iters = vect_estimate_min_profitable_iters (loop_vinfo);
> +  vect_estimate_min_profitable_iters (loop_vinfo, &min_profitable_iters,
> +				      &min_profitable_estimate);
>    LOOP_VINFO_COST_MODEL_MIN_ITERS (loop_vinfo) = min_profitable_iters;
>  
>    if (min_profitable_iters < 0)
> @@ -1452,6 +1455,7 @@ vect_analyze_loop_operations (loop_vec_i
>    min_scalar_loop_bound = ((PARAM_VALUE (PARAM_MIN_VECT_LOOP_BOUND)
>                              * vectorization_factor) - 1);
>  
> +
>    /* Use the cost model only if it is more conservative than user specified
>       threshold.  */
>  
> @@ -1474,6 +1478,18 @@ vect_analyze_loop_operations (loop_vec_i
>        return false;
>      }
>  
> +  if ((estimated_niter = estimated_stmt_executions_int (loop)) != -1
> +      && (unsigned HOST_WIDE_INT) estimated_niter <= MAX (th, min_profitable_estimate))
> +    {
> +      if (vect_print_dump_info (REPORT_UNVECTORIZED_LOCATIONS))
> +        fprintf (vect_dump, "not vectorized: estimated iteration count too small.");
> +      if (vect_print_dump_info (REPORT_DETAILS))
> +        fprintf (vect_dump, "not vectorized: estimated iteration count smaller than "
> +                 "user specified loop bound parameter or minimum "
> +                 "profitable iterations (whichever is more conservative).");
> +      return false;
> +    }
> +
>    if (!LOOP_VINFO_NITERS_KNOWN_P (loop_vinfo)
>        || LOOP_VINFO_INT_NITERS (loop_vinfo) % vectorization_factor != 0
>        || LOOP_PEELING_FOR_ALIGNMENT (loop_vinfo))
> @@ -2512,15 +2528,15 @@ vect_get_known_peeling_cost (loop_vec_in
>  
>     Return the number of iterations required for the vector version of the
>     loop to be profitable relative to the cost of the scalar version of the
> -   loop.
> +   loop.  */
>  
> -   TODO: Take profile info into account before making vectorization
> -   decisions, if available.  */
> -
> -int
> -vect_estimate_min_profitable_iters (loop_vec_info loop_vinfo)
> +void
> +vect_estimate_min_profitable_iters (loop_vec_info loop_vinfo,
> +				    int *ret_min_profitable_niters,
> +				    int *ret_min_profitable_estimate)
>  {
>    int min_profitable_iters;
> +  int min_profitable_estimate;
>    int peel_iters_prologue;
>    int peel_iters_epilogue;
>    unsigned vec_inside_cost = 0;
> @@ -2538,7 +2554,9 @@ vect_estimate_min_profitable_iters (loop
>      {
>        if (vect_print_dump_info (REPORT_COST))
>          fprintf (vect_dump, "cost model disabled.");
> -      return 0;
> +      *ret_min_profitable_niters = 0;
> +      *ret_min_profitable_estimate = 0;
> +      return;
>      }
>  
>    /* Requires loop versioning tests to handle misalignment.  */
> @@ -2774,7 +2792,9 @@ vect_estimate_min_profitable_iters (loop
>  		 "divided by the scalar iteration cost = %d "
>  		 "is greater or equal to the vectorization factor = %d.",
>                   vec_inside_cost, scalar_single_iter_cost, vf);
> -      return -1;
> +      *ret_min_profitable_niters = -1;
> +      *ret_min_profitable_estimate = -1;
> +      return;
>      }
>  
>    if (vect_print_dump_info (REPORT_COST))
> @@ -2789,6 +2809,7 @@ vect_estimate_min_profitable_iters (loop
>        fprintf (vect_dump, "  Scalar iteration cost: %d\n",
>  	       scalar_single_iter_cost);
>        fprintf (vect_dump, "  Scalar outside cost: %d\n", scalar_outside_cost);
> +      fprintf (vect_dump, "  Vector outside cost: %d\n", vec_outside_cost);
>        fprintf (vect_dump, "  prologue iterations: %d\n",
>                 peel_iters_prologue);
>        fprintf (vect_dump, "  epilogue iterations: %d\n",
> @@ -2809,7 +2830,34 @@ vect_estimate_min_profitable_iters (loop
>      fprintf (vect_dump, "  Profitability threshold = %d\n",
>  	     min_profitable_iters);
>  
> -  return min_profitable_iters;
> +  *ret_min_profitable_niters = min_profitable_iters;
> +  /* Calculate number of iterations required to make the vector version
> +     profitable, relative to the loop bodies only.
> +
> +     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  */
> +
> +  if ((scalar_single_iter_cost * vf) > (int) vec_inside_cost)
> +    {
> +      if (vec_outside_cost <= 0)
> +        min_profitable_estimate = 1;
> +      else
> +        {
> +          min_profitable_estimate = ((vec_outside_cost + scalar_outside_cost) * vf
> +				     - vec_inside_cost * peel_iters_prologue
> +                                     - vec_inside_cost * peel_iters_epilogue)
> +                                     / ((scalar_single_iter_cost * vf)
> +                                       - vec_inside_cost);
> +        }
> +    }
> +  min_profitable_estimate --;
> +  min_profitable_estimate = MAX (min_profitable_estimate, min_profitable_iters);
> +  if (vect_print_dump_info (REPORT_COST))
> +    fprintf (vect_dump, "  Profitability estimated iterations threshold = %d\n",
> +	     min_profitable_estimate);
> +
> +  *ret_min_profitable_estimate = min_profitable_estimate;
>  }
>  
>  
> 
> 

-- 
Richard Biener <rguenther@suse.de>
SUSE / SUSE Labs
SUSE LINUX Products GmbH - Nuernberg - AG Nuernberg - HRB 16746
GF: Jeff Hawn, Jennifer Guild, Felix Imend