https://gcc.gnu.org/g:56efa4a739786bb1c1c6dcdab0ad81cb1c55b970
commit r17-4693-g56efa4a739786bb1c1c6dcdab0ad81cb1c55b970 Author: Samarth Tandale <[email protected]> Date: Sun Sep 27 09:34:59 2026 -0600 [PATCH v1] match.pd: Fold (a != 0) | (popcount(a) == n) and related patterns [PR112094] 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]> Diff: --- 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(+) diff --git a/gcc/match.pd b/gcc/match.pd index 305c672e78c2..c70a8e6d6d27 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 000000000000..3f6666e228c6 --- /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 000000000000..4b6e32a83c54 --- /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" } } */
