On Sun, Sep 6, 2026 at 1:55 AM Shivam Gupta <[email protected]> wrote:
>
> If the argument to popcount is known to fit in unsigned int, convert
> it to unsigned int before applying the popcount operation. This allows
> the target to use a narrower popcount operation when appropriate.
>
> PR tree-optimization/125221
>
> gcc/ChangeLog:
>
> * gimple-match-head.cc: Include vr-values.h.
> * match.pd (POPCOUNT): Narrow the argument when its value range
> fits in unsigned int.
>
> gcc/testsuite/ChangeLog:
>
> * gcc.dg/popcountll-narrow.c: New test.
>
> Bootstrapped and tested on x86_64-pc-linux-gnu.
>
> Signed-off-by: Shivam Gupta <[email protected]>
> ---
> gcc/gimple-match-head.cc | 1 +
> gcc/match.pd | 15 ++++++
> gcc/testsuite/gcc.dg/popcountll-narrow.c | 60 ++++++++++++++++++++++++
> 3 files changed, 76 insertions(+)
> create mode 100644 gcc/testsuite/gcc.dg/popcountll-narrow.c
>
> diff --git a/gcc/gimple-match-head.cc b/gcc/gimple-match-head.cc
> index 757e324cb..9cf6e3160 100644
> --- a/gcc/gimple-match-head.cc
> +++ b/gcc/gimple-match-head.cc
> @@ -51,6 +51,7 @@ along with GCC; see the file COPYING3. If not see
> #include "langhooks.h"
> #include "attribs.h"
> #include "asan.h"
> +#include "vr-values.h"
>
> tree do_valueize (tree, tree (*)(tree), bool &);
> tree do_valueize (tree (*)(tree), tree);
> diff --git a/gcc/match.pd b/gcc/match.pd
> index 54cad1cd2..ad032092e 100644
> --- a/gcc/match.pd
> +++ b/gcc/match.pd
> @@ -11228,6 +11228,21 @@ DEFINE_INT_AND_FLOAT_ROUND_FN (RINT)
> #endif
>
> /* POPCOUNT simplifications. */
> +#if GIMPLE
> +/* If the value passed to popcount is known to fit in unsigned int,
> + use the narrower popcount operation. */
> +(simplify
> + (POPCOUNT @0)
> + (if (TYPE_PRECISION (TREE_TYPE (@0)) > TYPE_PRECISION (unsigned_type_node))
> + (with { int_range_max vr0; }
> + (if (gimple_match_range_of_expr (vr0, @0)
> + && range_fits_type_p (&vr0,
> + TYPE_PRECISION (unsigned_type_node),
> + TYPE_SIGN (unsigned_type_node)))
> + (with { tree utype = unsigned_type_node; }
> + (POPCOUNT (convert:utype @0)))))))
This will incorrectly produce a popcountll with a `unsigned int` as
the argument which is incorrect. Instead you should look at how it is
currently handled here:
```
/* popcount(zext(X)) == popcount(X). */
(simplify
(POPCOUNT (convert@1 @0))
(if (INTEGRAL_TYPE_P (TREE_TYPE (@1))
&& INTEGRAL_TYPE_P (TREE_TYPE (@0))
&& TYPE_UNSIGNED (TREE_TYPE (@0))
&& TYPE_PRECISION (TREE_TYPE (@1)) > TYPE_PRECISION (TREE_TYPE (@0)))
(with { combined_fn cfn = CFN_LAST;
tree type0 = TREE_TYPE (@0);
if (BITINT_TYPE_P (type0))
{
if (TYPE_PRECISION (type0) > MAX_FIXED_MODE_SIZE)
cfn = CFN_POPCOUNT;
else
type0
= build_nonstandard_integer_type (TYPE_PRECISION (type0),
1);
}
if (cfn == CFN_LAST
&& direct_internal_fn_supported_p (IFN_POPCOUNT, type0,
OPTIMIZE_FOR_BOTH))
cfn = CFN_POPCOUNT;
if (cfn == CFN_LAST
&& TYPE_PRECISION (TREE_TYPE (@1)) > BITS_PER_WORD
&& !direct_internal_fn_supported_p (IFN_POPCOUNT,
TREE_TYPE (@1),
OPTIMIZE_FOR_BOTH))
{
if (TYPE_PRECISION (type0)
== TYPE_PRECISION (unsigned_type_node))
cfn = CFN_BUILT_IN_POPCOUNT;
else if (TYPE_PRECISION (type0)
== TYPE_PRECISION (long_long_unsigned_type_node))
cfn = CFN_BUILT_IN_POPCOUNTLL;
} }
(if (cfn == CFN_POPCOUNT)
(IFN_POPCOUNT (convert:type0 @0))
(if (cfn == CFN_BUILT_IN_POPCOUNT)
(BUILT_IN_POPCOUNT (convert:type0 @0))
(if (cfn == CFN_BUILT_IN_POPCOUNTLL)
(BUILT_IN_POPCOUNTLL (convert:type0 @0))))))))
```
Even for BitInt case, you could see if it fits in
`MAX_FIXED_MODE_SIZE` and see if that exists as a popcount.
For an example aarch64 has a 128bit (TImode) popcount optab (when CSSC
is not enabled). Well and 128bit TImode popcount can be done by
splitting the popcount into 2 too.
> +#endif
> +
> /* popcount(X) + popcount(Y) is popcount(X|Y) when X&Y must be zero. */
> (simplify
> (plus (POPCOUNT:s @0) (POPCOUNT:s @1))
> diff --git a/gcc/testsuite/gcc.dg/popcountll-narrow.c
> b/gcc/testsuite/gcc.dg/popcountll-narrow.c
> new file mode 100644
> index 000000000..4c5a7db78
> --- /dev/null
> +++ b/gcc/testsuite/gcc.dg/popcountll-narrow.c
> @@ -0,0 +1,60 @@
> +/* { dg-do compile } */
> +/* { dg-options "-Os -fdump-tree-optimized" } */
> +
> +int func1(unsigned long long x) {
> + return __builtin_popcountll(x & 0x87878787);
> +}
> +int func2(unsigned long long x) {
> + return __builtin_popcountll(x >> 32);
> +}
> +int func2b(unsigned long long x) {
> + return __builtin_popcountll((x >> 32) & 0xFFFFFFFF);
> +}
> +int func3(unsigned char x) {
> + if (x >= 64) {
> + __builtin_unreachable();
> + }
> + return __builtin_popcountll(0x87878787ULL >> x);
> +}
> +int func3b(unsigned char x) {
> + if (x >= 64) {
> + __builtin_unreachable();
> + }
> + return __builtin_popcountll((0x87878787ULL >> x) & 0xFFFFFFFF);
> +}
> +int func4(unsigned long long x) {
> + return __builtin_popcountll(x % 4294967291U);
> +}
> +int func4b(unsigned long long x) {
> + return __builtin_popcountll((x % 4294967291U) & 0xFFFFFFFF);
> +}
> +int func5(unsigned long long x) {
> + return __builtin_popcountll(x / 4294967311U);
> +}
> +int func5b(unsigned long long x) {
> + return __builtin_popcountll((x / 4294967311U) & 0xFFFFFFFF);
> +}
> +int func6(unsigned long long x) {
> + if (x > 0xFFFFFFFFULL) {
> + __builtin_unreachable();
> + }
> + return __builtin_popcountll(x);
> +}
> +int func6b(unsigned long long x) {
> + if (x > 0xFFFFFFFFULL) {
> + __builtin_unreachable();
> + }
> + return __builtin_popcountll(x & 0xFFFFFFFF);
> +}
> +
> +/* Negative test case */
> +int func7(unsigned long long x) {
> + return __builtin_popcountll(x);
> +}
> +
> +/* Verify that all(f1-f6) popcount arguments have been narrowed to unsigned
> int
> + temporaries. */
> +/* { dg-final { scan-tree-dump-times {__builtin_popcountll \(_[0-9]+\)} 11
> "optimized" } } */
> +
> +/* Verify that an argument whose range is not known to fit is unchanged. */
> +/* { dg-final { scan-tree-dump-times {__builtin_popcountll \(x_} 1
> "optimized" } } */
> --
> 2.43.0
>
