Re: [patch v3]middle-end: Teach ranger about POLY_INT_CST ranges for VRP.

Sorry for the slow reply.

Tamar Christina <[email protected]> writes:
> A an area where LLVM generates much better code than GCC today is in
> optimization of VLA branches guarded by VLA constants.
>
> Normally in GIMPLE POLY_INT_CSTs have no upport and lower bound because well,
> they're poly.  However SVE has defined minimum and maximum vector sizes in
> the architecture[1] and so for us we do have bounds on these constants.
>
> [1] https://developer.arm.com/documentation/102476/0101/Introducing-SVE
>
> Today LLVM optimizes these simple expressions
>
> #include <arm_sve.h>
>
> int g (void)
> {
>   unsigned int vl = svcntb ();
>   return vl < 257;
> }
>
> int h (void)
> {
>   return svcntw () <= 64;
> }
>
> away to
>
> g():
>         mov     w0, #1
>         ret
>
> h():
>         mov     w0, #1
>         ret
>
> which is right because both are always true for any SVE vector length.
>
> while GCC generates:
>
> g():
>         cntb    x0
>         cmp     w0, 257
>         cset    w0, cc
>         ret
> h():
>         cntw    x0
>         cmp     x0, 65
>         cset    w0, cc
>         ret
>
> This patch extends ranger with a target hook poly_int_indeterminate_bound which
> is different from the current costing only hooks used in the vectorizer because
> those hooks can't be relied upon for correctness.
>
> This new hook allows us specify the minimum and maximum bounds of a POLY_INT_CST
> and have ranger use it in range_query::get_tree_range though specifying the
> indeterminate bound of a POLY target.
>
> This gets GCC to fold away many known true or known false comparisons in
> codegen today and we generate much simpler loop pre-headers.
>
> I have kept the AArch64 parts in this patch to get some extra eyes on it, but
> will split them out on commit.
>
> Bootstrapped Regtested on aarch64-none-linux-gnu,
> arm-none-linux-gnueabihf, x86_64-pc-linux-gnu
> -m32, -m64 and no issues.
>
> Ok for master?
>
> Thanks,
> Tamar
>
> gcc/ChangeLog:
>
> 	* config/aarch64/aarch64.cc (aarch64_poly_int_indeterminate_bound): New.
> 	(TARGET_POLY_INT_INDETERMINATE_BOUND ): Implement hook using it.
> 	* target.def (poly_int_indeterminate_bound): New.
> 	* doc/tm.texi.in: Document it.
> 	* doc/tm.texi: Regenerate.
> 	* value-query.cc (range_query::get_tree_range): Use it.
>
> gcc/testsuite/ChangeLog:
>
> 	* gcc.target/aarch64/sve/slp_12.c: Update testcases
> 	* gcc.target/aarch64/sve/cnt_fold_7.c: New test.
> 	* gcc.target/aarch64/sve/cnt_fold_7_run.c: New test.

This mostly LGTM, but some comments about the wide_int usage below.

> @@ -404,8 +406,98 @@ range_query::get_tree_range (vrange &r, tree expr, gimple *stmt,
>        if (POLY_INT_CST_P (expr))
>  	{
>  	  unsigned int precision = TYPE_PRECISION (type);
> -	  r.set_varying (type);
> -	  r.update_bitmask ({ wi::zero (precision), get_nonzero_bits (expr) });
> +	  signop sign = TYPE_SIGN (type);
> +	  bool have_poly_bound = targetm.poly_int_indeterminate_bound;
> +	  poly_uint64 indeterminate_bound;
> +
> +	  if (have_poly_bound)
> +	    indeterminate_bound = targetm.poly_int_indeterminate_bound ();
> +
> +	  poly_wide_int val = wi::to_poly_wide (expr);
> +	  wide_int type_min = wi::to_wide (TYPE_MIN_VALUE (type));
> +	  wide_int type_max = wi::to_wide (TYPE_MAX_VALUE (type));

Variables should usually only be declared as "wide_int" if they specifically
need to be written to later.  Otherwise it's best to use "auto".  The types
returned by wi::to_wide and the like are more efficient than temporary
wide_ints.

One of the requirements for wide_int being accepted was that using trees
and rtxes as "wide_int-like" should have low overhead.  We tend to lose
that in practice by using wide_int temporaries where they aren't needed.

I know this isn't exactly hot code, but I'm going to make this point
whenever I review wide_int stuff, since the idiom might be copied
elsewhere.

> +
> +	  /* Start with the invariant part of the poly-int, then account
> +	     for each coefficient below.
> +
> +	     The target hook gives a per-coefficient upper bound for the
> +	     indeterminate.  Since those indeterminates are unsigned and
> +	     nonnegative, a positive coefficient can only increase the upper
> +	     bound and a negative coefficient can only decrease the lower
> +	     bound.  The opposite bound is unaffected by that coefficient:
> +
> +		[A, +C] with C >= 0  => max += C * bound
> +		[A, -C] with C >= 0  => min -= C * bound.  */
> +	  wide_int bounds[2]
> +	    = { wide_int::from (val.coeffs[0], precision, sign),
> +		wide_int::from (val.coeffs[0], precision, sign) };

These wide_int::froms seem unnecessary.  val.coeffs[0] is already a
wide_int of the right precision.

> +	  bool ovf[2] = { false, false };
> +
> +	  for (unsigned int i = 1; i < NUM_POLY_INT_COEFFS; ++i)
> +	    {
> +	      wide_int coeff = wide_int::from (val.coeffs[i], precision, sign);

Similarly here.

> +	      if (wi::eq_p (coeff, 0))
> +		continue;
> +
> +	      /* Select the only bound affected by this coefficient.  A
> +		 negative coefficient contributes to the minimum and a positive
> +		 coefficient contributes to the maximum.  */
> +	      bool coeff_neg = wi::neg_p (coeff, sign);
> +	      wide_int &bound = bounds[coeff_neg ? 0 : 1];
> +	      bool &bound_ovf = ovf[coeff_neg ? 0 : 1];
> +
> +	      if (bound_ovf)
> +		continue;
> +
> +	      /* A missing hook, or a -1 bound for this coefficient, means the
> +		 indeterminate has no finite target-specific limit.  Treat that
> +		 like an overflow of the affected bound.  */
> +	      if (!have_poly_bound
> +		  || indeterminate_bound.coeffs[i] == HOST_WIDE_INT_M1U)
> +		bound_ovf = true;
> +	      else
> +		{
> +		  wide_int indeterminate
> +		    = wi::uhwi (indeterminate_bound.coeffs[i], precision);

Similarly here about not using wide_int.

> +		  wi::overflow_type mul_ovf = wi::OVF_NONE;
> +		  wide_int term = wi::mul (coeff, indeterminate, sign,
> +					   &mul_ovf);
> +		  wi::overflow_type add_ovf = wi::OVF_NONE;
> +		  bound = wi::add (bound, term, sign, &add_ovf);
> +		  bound_ovf = (mul_ovf != wi::OVF_NONE
> +			       || add_ovf != wi::OVF_NONE);
> +		}
> +
> +	      if (TYPE_OVERFLOW_WRAPS (type) && bound_ovf)
> +		{
> +		  r.set_varying (type);
> +		  return true;
> +		}
> +
> +	      if (bound_ovf)
> +		{
> +		  if (coeff_neg)
> +		    bounds[0] = type_min;
> +		  else
> +		    bounds[1] = type_max;
> +		}
> +	    }

I've attached the comments above in patch form since I wanted to check
that they worked.  It's trivial stuff, so doesn't count as co-authorship.

> +
> +	  if (!wi::le_p (bounds[0], bounds[1], sign))
> +	    {
> +	      r.set_varying (type);
> +	      return true;
> +	    }

Is this possible after the above?  I would hope that we could either drop
this or turn it into an assert.  Either way is ok with me.

OK with those changes, thanks.  I think the patch has been around long
enough that more active folks would have commented by now if they wanted to.
But please say if you think the above le_p is still needed.

Richard

> +
> +	  irange &ir = as_a <irange> (r);
> +	  ir.set (type, bounds[0], bounds[1]);
> +
> +	  /* Preserve alignment/step information that is not visible in the
> +	     intervals.  For example, a poly-int like [8, 8] can
> +	     only produce multiples of 8, but the interval range might be
> +	     [8, 136], which also contains values with low bits set.  */
> +	  ir.update_bitmask (irange_bitmask (wi::zero (precision),
> +					     get_nonzero_bits (expr)));
>  	  return true;
>  	}
>        break;


diff --git a/gcc/value-query.cc b/gcc/value-query.cc
index 53728addefc..da93aea4a14 100644
--- a/gcc/value-query.cc
+++ b/gcc/value-query.cc
@@ -413,9 +413,9 @@ range_query::get_tree_range (vrange &r, tree expr, gimple *stmt,
 	  if (have_poly_bound)
 	    indeterminate_bound = targetm.poly_int_indeterminate_bound ();
 
-	  poly_wide_int val = wi::to_poly_wide (expr);
-	  wide_int type_min = wi::to_wide (TYPE_MIN_VALUE (type));
-	  wide_int type_max = wi::to_wide (TYPE_MAX_VALUE (type));
+	  auto val = wi::to_poly_wide (expr);
+	  auto type_min = wi::to_wide (TYPE_MIN_VALUE (type));
+	  auto type_max = wi::to_wide (TYPE_MAX_VALUE (type));
 
 	  /* Start with the invariant part of the poly-int, then account
 	     for each coefficient below.
@@ -428,14 +428,12 @@ range_query::get_tree_range (vrange &r, tree expr, gimple *stmt,
 
 		[A, +C] with C >= 0  => max += C * bound
 		[A, -C] with C >= 0  => min -= C * bound.  */
-	  wide_int bounds[2]
-	    = { wide_int::from (val.coeffs[0], precision, sign),
-		wide_int::from (val.coeffs[0], precision, sign) };
+	  wide_int bounds[2] = { val.coeffs[0], val.coeffs[0] };
 	  bool ovf[2] = { false, false };
 
 	  for (unsigned int i = 1; i < NUM_POLY_INT_COEFFS; ++i)
 	    {
-	      wide_int coeff = wide_int::from (val.coeffs[i], precision, sign);
+	      const auto &coeff = val.coeffs[i];
 	      if (wi::eq_p (coeff, 0))
 		continue;
 
@@ -457,11 +455,10 @@ range_query::get_tree_range (vrange &r, tree expr, gimple *stmt,
 		bound_ovf = true;
 	      else
 		{
-		  wide_int indeterminate
+		  auto indeterminate
 		    = wi::uhwi (indeterminate_bound.coeffs[i], precision);
 		  wi::overflow_type mul_ovf = wi::OVF_NONE;
-		  wide_int term = wi::mul (coeff, indeterminate, sign,
-					   &mul_ovf);
+		  auto term = wi::mul (coeff, indeterminate, sign, &mul_ovf);
 		  wi::overflow_type add_ovf = wi::OVF_NONE;
 		  bound = wi::add (bound, term, sign, &add_ovf);
 		  bound_ovf = (mul_ovf != wi::OVF_NONE