From: Samarth Tandale <[email protected]>
Fold (a != 0) | (popcount(a) == n) into (a != 0) | (n == 0), and
(a == 0) & (popcount(a) != n) into (a == 0) & (n != 0).
This follows from x == 0 => popcount(x) == 0: when a == 0 the
popcount comparison reduces to a comparison against zero, and when
a != 0 the outer OR/AND already determines the result.
PR tree-optimization/112094
gcc/ChangeLog:
* match.pd: Add fold for (a != 0) | (popcount(a) == n) and
(a == 0) & (popcount(a) != n).
gcc/testsuite/ChangeLog:
* gcc.dg/fold-popcount-12.c: New test.
* gcc.dg/fold-popcount-13.c: New test.
Signed-off-by: Samarth Tandale <[email protected]>
---
Fold (a != 0) | (popcount(a) == n) into (a != 0) | (n == 0), and
(a == 0) & (popcount(a) != n) into (a == 0) & (n != 0).
This follows from x == 0 => popcount(x) == 0: when a == 0 the
popcount comparison reduces to a comparison against zero, and when
a != 0 the outer OR/AND already determines the result.
PR tree-optimization/112094
```
gcc/ChangeLog:
* match.pd: Add fold for (a != 0) | (popcount(a) == n) and
(a == 0) & (popcount(a) != n).
gcc/testsuite/ChangeLog:
* gcc.dg/fold-popcount-12.c: New test.
* gcc.dg/fold-popcount-13.c: New test.
```
Signed-off-by: Samarth Tandale <[email protected]>
This is a forge pull request published on the gcc-patches mailing list mailing
list
as requested by Samarth Tandale via Sourceware Forge
<[email protected]>.
Forge discussion: https://forge.sourceware.org/gcc/gcc/pulls/233
Get it locally using:
```
git fetch forge-upstream "+refs/versioned_pull/233/*:refs/versioned_pull/233/*"
git switch -c "pr-233-v1" "refs/versioned_pull/233/1/head"
```
Or, download the patch at: https://forge.sourceware.org/gcc/gcc/pulls/233.diff
Created on: 2026-09-24 11:25:25+00:00
Latest update: 2026-09-24 11:48:15+00:00
Changes: 3 changed files, 195 additions, 0 deletions
Head revision: sam-100/gcc ref pr112094-popcount commit
19af6b5f77682efdc05756d9e5ff39cd12d54434
Base revision: gcc/gcc ref trunk commit
b679fda6b4f2d41323e19f780b52805e7a06bfcc r17-4589-gb679fda6b4f2d4
Merge base: b679fda6b4f2d41323e19f780b52805e7a06bfcc
Requested Reviewers:
Changed files:
- A: gcc/testsuite/gcc.dg/fold-popcount-12.c
- A: gcc/testsuite/gcc.dg/fold-popcount-13.c
- M: gcc/match.pd
gcc/match.pd | 13 +++
gcc/testsuite/gcc.dg/fold-popcount-12.c | 149 ++++++++++++++++++++++++
gcc/testsuite/gcc.dg/fold-popcount-13.c | 33 ++++++
3 files changed, 195 insertions(+)
create mode 100644 gcc/testsuite/gcc.dg/fold-popcount-12.c
create mode 100644 gcc/testsuite/gcc.dg/fold-popcount-13.c
diff --git a/gcc/match.pd b/gcc/match.pd
index b6a9d4e79be21..c2a66c2606b71 100644
--- a/gcc/match.pd
+++ b/gcc/match.pd
@@ -11508,6 +11508,19 @@ DEFINE_INT_AND_FLOAT_ROUND_FN (RINT)
(cmp (popcount @0) integer_zerop)
(rep @0 { build_zero_cst (TREE_TYPE (@0)); }))))
+/* (a != 0) | (popcount (a) == n) -> (a != 0) | (n == 0)
+ (a == 0) & (popcount (a) != n) -> (a == 0) & (n != 0) */
+(for popcount (POPCOUNT)
+ (for bop (bit_ior bit_and)
+ popcmp (eq ne)
+ zerocmp (ne eq)
+ (simplify
+ (bop:c (zerocmp@2 @0 integer_zerop)
+ (popcmp:cs (popcount (convert?@3 @0)) @1))
+ (if (INTEGRAL_TYPE_P (TREE_TYPE (@0))
+ && INTEGRAL_TYPE_P (TREE_TYPE (@3)))
+ (bop @2 (popcmp @1 { build_zero_cst (TREE_TYPE (@1)); }))))))
+
/* popcount(bswap(x)) is popcount(x). */
(for popcount (POPCOUNT)
(for bswap (BSWAP BITREVERSE)
diff --git a/gcc/testsuite/gcc.dg/fold-popcount-12.c
b/gcc/testsuite/gcc.dg/fold-popcount-12.c
new file mode 100644
index 0000000000000..3f6666e228c67
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/fold-popcount-12.c
@@ -0,0 +1,149 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-optimized" } */
+/* PR tree-optimization/112094 */
+/* Test that
+ (a != 0) | (popcount(a) == n) -> (a != 0) | (n == 0)
+ (a == 0) & (popcount(a) != n) -> (a == 0) & (n != 0)
+ and their commuted forms are folded away. */
+
+/* OR cases. */
+int f (unsigned int a, int n)
+{
+ int t = __builtin_popcount (a);
+ return (a != 0) | (t == n);
+}
+
+int fl (unsigned long a, int n)
+{
+ int t = __builtin_popcountl (a);
+ return (a != 0) | (t == n);
+}
+
+int fll (unsigned long long a, int n)
+{
+ int t = __builtin_popcountll (a);
+ return (a != 0) | (t == n);
+}
+
+/* Signed-to-unsigned conversions inserted for popcount. */
+int f_signed (int a, int n)
+{
+ int t = __builtin_popcount (a);
+ return (a != 0) | (t == n);
+}
+
+int fl_signed (long a, int n)
+{
+ int t = __builtin_popcountl (a);
+ return (a != 0) | (t == n);
+}
+
+int fll_signed (long long a, int n)
+{
+ int t = __builtin_popcountll (a);
+ return (a != 0) | (t == n);
+}
+
+/* Integral conversions: promotion, widening, and narrowing. */
+int f_promoted (short a, int n)
+{
+ int t = __builtin_popcount (a);
+ return (a != 0) | (t == n);
+}
+
+int f_widened (int a, int n)
+{
+ int t = __builtin_popcountll (a);
+ return (a != 0) | (t == n);
+}
+
+int f_narrowed (long long a, int n)
+{
+ int t = __builtin_popcount (a);
+ return (a != 0) | (t == n);
+}
+
+/* Commuted operator and comparison operands. */
+int f_comm (unsigned int a, int n)
+{
+ int t = __builtin_popcount (a);
+ return (t == n) | (a != 0);
+}
+
+int f_comm2 (unsigned int a, int n)
+{
+ int t = __builtin_popcount (a);
+ return (a != 0) | (n == t);
+}
+
+int f_comm3 (unsigned int a, int n)
+{
+ int t = __builtin_popcount (a);
+ return (0 != a) | (t == n);
+}
+
+/* AND cases. */
+int g (unsigned int a, int n)
+{
+ int t = __builtin_popcount (a);
+ return (a == 0) & (t != n);
+}
+
+int gl (unsigned long a, int n)
+{
+ int t = __builtin_popcountl (a);
+ return (a == 0) & (t != n);
+}
+
+int gll (unsigned long long a, int n)
+{
+ int t = __builtin_popcountll (a);
+ return (a == 0) & (t != n);
+}
+
+/* Signed-to-unsigned conversions inserted for popcount. */
+int g_signed (int a, int n)
+{
+ int t = __builtin_popcount (a);
+ return (a == 0) & (t != n);
+}
+
+/* Integral conversions: promotion, widening, and narrowing. */
+int g_promoted (short a, int n)
+{
+ int t = __builtin_popcount (a);
+ return (a == 0) & (t != n);
+}
+
+int g_widened (int a, int n)
+{
+ int t = __builtin_popcountll (a);
+ return (a == 0) & (t != n);
+}
+
+int g_narrowed (long long a, int n)
+{
+ int t = __builtin_popcount (a);
+ return (a == 0) & (t != n);
+}
+
+/* Commuted operator and comparison operands. */
+int g_comm (unsigned int a, int n)
+{
+ int t = __builtin_popcount (a);
+ return (t != n) & (a == 0);
+}
+
+int g_comm2 (unsigned int a, int n)
+{
+ int t = __builtin_popcount (a);
+ return (a == 0) & (n != t);
+}
+
+int g_comm3 (unsigned int a, int n)
+{
+ int t = __builtin_popcount (a);
+ return (0 == a) & (t != n);
+}
+
+/* { dg-final { scan-tree-dump-not "popcount" "optimized" } } */
diff --git a/gcc/testsuite/gcc.dg/fold-popcount-13.c
b/gcc/testsuite/gcc.dg/fold-popcount-13.c
new file mode 100644
index 0000000000000..4b6e32a83c54d
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/fold-popcount-13.c
@@ -0,0 +1,33 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-optimized" } */
+/* PR tree-optimization/112094 */
+/* Verify that popcount comparisons are preserved when they cannot be
+ safely simplified. */
+
+/* The comparison result is used twice. */
+int f_multiuse (unsigned int a, int n, int *out)
+{
+ int c = __builtin_popcount (a) == n;
+ *out = c;
+ return (a != 0) | c;
+}
+
+extern int get_value (void);
+volatile unsigned int value;
+
+/* Both calls to get_value are observable and must be preserved. */
+int f_side_effect (int n)
+{
+ return (get_value () != 0)
+ | (__builtin_popcount (get_value ()) == n);
+}
+
+/* Both volatile reads are observable and must be preserved. */
+int f_volatile (int n)
+{
+ return (value != 0)
+ | (__builtin_popcount (value) == n);
+}
+
+/* One popcount remains for each negative case. */
+/* { dg-final { scan-tree-dump-times "popcount" 3 "optimized" } } */
--
2.54.0
