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" } } */

Reply via email to