https://gcc.gnu.org/g:06c476d192702a07dc6a8431b7f1a54d7526d3a5
commit r17-5988-g06c476d192702a07dc6a8431b7f1a54d7526d3a5 Author: Naveen <[email protected]> Date: Thu Nov 5 20:22:06 2026 -0800 tree-optimization: simplify popcount of bitwise NOT Recognize popcount (~x) and rewrite it as the operand’s precision minus popcount (x). This removes the bitwise complement and enables further simplifications such as folding popcount (~x) + popcount (x) to a constant. gcc/ChangeLog: * match.pd (popcount (bit_not @0)): Simplify to precision minus popcount. gcc/testsuite/ChangeLog: * gcc.dg/fold-popcount-bitnot-arith.c: New test. * gcc.dg/tree-ssa/popcount-bitnot-arith.c: New test. Signed-off-by: Naveen <[email protected]> Diff: --- gcc/match.pd | 11 ++++ gcc/testsuite/gcc.dg/fold-popcount-bitnot-arith.c | 67 ++++++++++++++++++++++ .../gcc.dg/tree-ssa/popcount-bitnot-arith.c | 20 +++++++ 3 files changed, 98 insertions(+) diff --git a/gcc/match.pd b/gcc/match.pd index 9be30877f441..3e206704fc6c 100644 --- a/gcc/match.pd +++ b/gcc/match.pd @@ -11749,6 +11749,17 @@ DEFINE_INT_AND_FLOAT_ROUND_FN (RINT) (if (prec0 == prec1 || (prec0 > prec1 && TYPE_UNSIGNED (type1))) (popcount (convert:type0 @2)))))))) +/* popcount (~X) --> PREC - popcount (X). + The identity popcount (~x) == PREC - popcount (x) holds for all + PREC-bit integers in two's-complement arithmetic. */ +(for popcount (POPCOUNT) + (simplify + (popcount (nop_convert?:s (bit_not:s @0))) + (with { unsigned int prec = TYPE_PRECISION (TREE_TYPE (@0)); } + (if (INTEGRAL_TYPE_P (TREE_TYPE (@0))) + (minus { build_int_cst (type, prec); } + (popcount:type @0)))))) + /* Canonicalize POPCOUNT(x)&1 as PARITY(X). */ (simplify (bit_and (POPCOUNT @0) integer_onep) diff --git a/gcc/testsuite/gcc.dg/fold-popcount-bitnot-arith.c b/gcc/testsuite/gcc.dg/fold-popcount-bitnot-arith.c new file mode 100644 index 000000000000..b0b5ade0c742 --- /dev/null +++ b/gcc/testsuite/gcc.dg/fold-popcount-bitnot-arith.c @@ -0,0 +1,67 @@ +/* { dg-do run } */ +/* { dg-options "-O2" } */ + +/* Correctness test: popcount(~X) == PREC - popcount(X). + Checks unsigned int, signed int, and unsigned long long, including + boundary cases with all-zeros and all-ones. */ + +#include <stdlib.h> +#include <limits.h> + +int f_uint (unsigned int x) { return __builtin_popcount (~x); } +int f_int (int x) { return __builtin_popcount (~x); } +int f_ull (unsigned long long x) { return __builtin_popcountll (~x); } + +#define PREC_UINT ((int)(sizeof (unsigned int) * CHAR_BIT)) +#define PREC_ULL ((int)(sizeof (unsigned long long) * CHAR_BIT)) + +int +main (void) +{ + /* unsigned int test vectors. */ + static const unsigned int uv[] = { + 0U, + 1U, + 0x12345678U, + 0x07FFFFFFU, /* popcount = 27, popcount(~) = 5 */ + 0xFFFFFFFFU, /* all-ones: popcount(~) = 0 */ + }; + for (unsigned i = 0; i < sizeof uv / sizeof *uv; i++) + { + int expected = PREC_UINT - __builtin_popcount (uv[i]); + if (f_uint (uv[i]) != expected) + abort (); + } + + /* signed int test vectors, including negative values. */ + static const int iv[] = { + 0, + 1, + -1, + 0x12345678, + 0x07FFFFFF, + }; + for (unsigned i = 0; i < sizeof iv / sizeof *iv; i++) + { + int expected = PREC_UINT + - __builtin_popcount ((unsigned int) iv[i]); + if (f_int (iv[i]) != expected) + abort (); + } + + /* unsigned long long test vectors. */ + static const unsigned long long ullv[] = { + 0ULL, + 1ULL, + 0x123456789ABCDEF0ULL, + 0x3FFFFFFFFFFFFFFFULL, /* 2 bits clear: popcount(~) = 2 */ + ~0ULL, /* all-ones: popcount(~) = 0 */ + }; + for (unsigned i = 0; i < sizeof ullv / sizeof *ullv; i++) + { + int expected = PREC_ULL - __builtin_popcountll (ullv[i]); + if (f_ull (ullv[i]) != expected) + abort (); + } + return 0; +} diff --git a/gcc/testsuite/gcc.dg/tree-ssa/popcount-bitnot-arith.c b/gcc/testsuite/gcc.dg/tree-ssa/popcount-bitnot-arith.c new file mode 100644 index 000000000000..9a2b823d13c2 --- /dev/null +++ b/gcc/testsuite/gcc.dg/tree-ssa/popcount-bitnot-arith.c @@ -0,0 +1,20 @@ +/* Verify that popcount(~X) is folded to PREC - popcount(X), + eliminating the BIT_NOT_EXPR for unsigned and signed input. */ +/* { dg-do compile } */ +/* { dg-options "-O2 -fdump-tree-optimized" } */ + +/* unsigned int: PREC == 32. */ +int f_uint (unsigned int x) { return __builtin_popcount (~x); } + +/* signed int: the builtin argument conversion is a no-op conversion. */ +int f_int (int x) { return __builtin_popcount (~x); } + +/* unsigned long long: PREC == 64. */ +int f_ull (unsigned long long x) { return __builtin_popcountll (~x); } + +/* popcount(~x) + popcount(x) == PREC: verify the sum constant-folds. */ +int f_chain (unsigned int x) { return __builtin_popcount (~x) + __builtin_popcount (x); } + +/* The BIT_NOT_EXPR must be gone; the sum in f_chain must fold to 32. */ +/* { dg-final { scan-tree-dump-not "~" "optimized" } } */ +/* { dg-final { scan-tree-dump "return 32" "optimized" } } */
