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
