Re: [PATCH v5] match.pd: Simplify (~A & 1) == (~B & 1) at -O1 [PR112533]

On Mon, 17 Aug 2026 at 6:36 PM, Richard Biener <[email protected]>
wrote:

> On Sat, Aug 15, 2026 at 8:38 AM Shivam Gupta <[email protected]>
> wrote:
> >
> > At -O1, GCC lowers (~a & 1) == (~b & 1) into two different GIMPLE
> > forms depending on whether the boolean values come from a function
> > return boundary or an inline expression:
> >
> >   1. Via function return (e.g. inlined is_even), GCC preserves the
> >      eq/ne form because the function boundary hides the internal
> >      structure from the gimplifier:
> >        ((a&1)==0) == ((b&1)==0)   outer node is eq/ne
> >
> >   2. Via inline expression (directly written), GCC sees the full
> >      boolean expression tree at once and folds to bit_xor during
> >      gimplification:
> >        ((a&1)!=0) ^ ((b&1)==0)   outer node is bit_xor
> >
> > Add a generalized match.pd rule handling:
> >   1. ((x & c) == 0) OP ((y & c) == 0)
> >   2. ((x & c) != 0) OP ((y & c) == 0)
> >
> > for OP in { ==, !=, ^ } and pow2 masks.
> >
> > Fold these directly into the canonical xor-mask form:
> >   ((x ^ y) & c) == 0
> >   ((x ^ y) & c) != 0
> >
> > Bootstrapped and tested on aarch64-linux-gnu with
> > RUNTESTFLAGS="tree-ssa.exp".
>
> This looks OK now.  I'll note you're required to run the full testsuite,
> not only the tree-ssa.exp part.  I'll do that this time and will push
> after that succeeded.
>

Thanks a lot!

Shivam.

>
> Richard.
>
> > Changes since v1:
> > * v5: Add :s to the inner comparisons and bit_and expressions.
> >       Simplify the innersame check to compare icmp0 and icmp1
> >       directly.
> >
> > * v4: Removed the ((x & c) == 0) OP (y & c) simplify rule and
> >       mark the corresponding test case as XFAIL.
> >
> > * v3: Collapse both previous simplify rules into one generalized
> >       matcher covering all combinations of outer {eq, ne, bit_xor}
> >       and inner {eq, ne} comparisons.
> >       Add missing mixed-polarity test cases.
> >
> > * v2: Generalize mask from integer_onep to integer_pow2p.
> >       Combine both patterns into single one.
> >       Split test into bool-eq-evenness.c, bool-eq-bitxor.c,
> >       bool-eq-pow2.c.
> >
> >         PR tree-optimization/112533
> >
> > gcc/ChangeLog:
> >         * match.pd: Canonicalize boolean comparisons of masked pow2
> >         bits into xor-mask tests.
> >
> > gcc/testsuite/ChangeLog:
> >         * gcc.dg/tree-ssa/bool-eq-bitxor.c: New test.
> >         * gcc.dg/tree-ssa/bool-eq-evenness.c: New test.
> >         * gcc.dg/tree-ssa/bool-eq-pow2.c: New test.
> >
> > Signed-off-by: Shivam Gupta <[email protected]>
> > ---
> >  gcc/match.pd                                  | 20 +++++
> >  .../gcc.dg/tree-ssa/bool-eq-bitxor.c          | 42 +++++++++
> >  .../gcc.dg/tree-ssa/bool-eq-evenness.c        | 43 +++++++++
> >  gcc/testsuite/gcc.dg/tree-ssa/bool-eq-pow2.c  | 89 +++++++++++++++++++
> >  4 files changed, 194 insertions(+)
> >  create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/bool-eq-bitxor.c
> >  create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/bool-eq-evenness.c
> >  create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/bool-eq-pow2.c
> >
> > diff --git a/gcc/match.pd b/gcc/match.pd
> > index 02684d8a3..7a052365b 100644
> > --- a/gcc/match.pd
> > +++ b/gcc/match.pd
> > @@ -1564,6 +1564,26 @@ DEFINE_INT_AND_FLOAT_ROUND_FN (RINT)
> >    (if (TYPE_UNSIGNED (type))
> >      (bit_and @0 (bit_not (lshift { build_all_ones_cst (type); } @1)))))
> >
> > +/* PR112533: Canonicalize boolean comparisons of masked pow2 bits into
> > +   xor-mask tests.
> > +   ((x & c) == 0) == ((y & c) == 0) -> (((x ^ y) & c) == 0)
> > +   ((x & c) == 0) != ((y & c) == 0) -> (((x ^ y) & c) != 0)
> > +   and equivalent xor forms.  */
> > +(for masked_ocmp (eq ne bit_xor)
> > + (for icmp0 (eq eq ne ne)
> > +      icmp1 (eq ne eq ne)
> > +  (simplify
> > +   (masked_ocmp
> > +    (icmp0:s (bit_and:s @0 integer_pow2p@1) integer_zerop@3)
> > +    (icmp1:s (bit_and:s @2 @1) @3))
> > +   (if (types_match (@0, @2))
> > +    (with {
> > +      bool innersame = icmp0 == icmp1;
> > +    }
> > +     (if (innersame == (masked_ocmp == EQ_EXPR))
> > +      (eq (bit_and (bit_xor @0 @2) @1) @3)
> > +      (ne (bit_and (bit_xor @0 @2) @1) @3)))))))
> > +
> >  (for bitop (bit_and bit_ior)
> >       cmp (eq ne)
> >   /* PR35691: Transform
> > diff --git a/gcc/testsuite/gcc.dg/tree-ssa/bool-eq-bitxor.c
> b/gcc/testsuite/gcc.dg/tree-ssa/bool-eq-bitxor.c
> > new file mode 100644
> > index 000000000..bc263e809
> > --- /dev/null
> > +++ b/gcc/testsuite/gcc.dg/tree-ssa/bool-eq-bitxor.c
> > @@ -0,0 +1,42 @@
> > +/* { dg-do compile } */
> > +/* { dg-options "-O1 -fdump-tree-optimized" } */
> > +
> > +typedef unsigned int u32;
> > +
> > +_Bool
> > +xor_ne_eq (u32 a, u32 b)
> > +{
> > +  u32 t1 = a & 1;
> > +  u32 t2 = b & 1;
> > +  return (t1 != 0) ^ (t2 == 0);
> > +}
> > +
> > +_Bool
> > +xor_eq_eq (u32 a, u32 b)
> > +{
> > +  u32 t1 = a & 1;
> > +  u32 t2 = b & 1;
> > +  return (t1 == 0) ^ (t2 == 0);
> > +}
> > +
> > +_Bool
> > +xor_eq_ne (u32 a, u32 b)
> > +{
> > +  u32 t1 = a & 1;
> > +  u32 t2 = b & 1;
> > +  return (t1 == 0) ^ (t2 != 0);
> > +}
> > +
> > +_Bool
> > +xor_ne_ne (u32 a, u32 b)
> > +{
> > +  u32 t1 = a & 1;
> > +  u32 t2 = b & 1;
> > +  return (t1 != 0) ^ (t2 != 0);
> > +}
> > +
> > +/* Verify all functions canonicalize to xor-mask tests.  */
> > +/* { dg-final { scan-tree-dump-times "a_\[0-9\]+\\(D\\) \\^
> b_\[0-9\]+\\(D\\)" 3 "optimized" } } */
> > +
> > +/* xor_eq_ne not optimized yet due to zero_one_valued_p
> canonicalization.  */
> > +/* { dg-final { scan-tree-dump-times "& 1" 2 "optimized" { xfail *-*-*
> } } } */
> > diff --git a/gcc/testsuite/gcc.dg/tree-ssa/bool-eq-evenness.c
> b/gcc/testsuite/gcc.dg/tree-ssa/bool-eq-evenness.c
> > new file mode 100644
> > index 000000000..75df70dc6
> > --- /dev/null
> > +++ b/gcc/testsuite/gcc.dg/tree-ssa/bool-eq-evenness.c
> > @@ -0,0 +1,43 @@
> > +/* { dg-do compile } */
> > +/* { dg-options "-O1 -fdump-tree-optimized" } */
> > +
> > +/* Verify the GIMPLE-level fix for PR112533. */
> > +
> > +typedef unsigned int u32;
> > +
> > +static _Bool
> > +is_even (u32 a)
> > +{
> > +  return a % 2 == 0;
> > +}
> > +
> > +_Bool
> > +same_evenness (u32 a, u32 b)
> > +{
> > +  return is_even (a) == is_even (b);
> > +}
> > +
> > +_Bool
> > +diff_evenness (u32 a, u32 b)
> > +{
> > +  return is_even (a) != is_even (b);
> > +}
> > +
> > +_Bool
> > +same_evenness_cmp_zero (u32 a, u32 b)
> > +{
> > +  u32 t1 = a & 1;
> > +  u32 t2 = b & 1;
> > +  return (t1 == 0) == (t2 == 0);
> > +}
> > +
> > +_Bool
> > +diff_evenness_cmp_zero (u32 a, u32 b)
> > +{
> > +  u32 t1 = a & 1;
> > +  u32 t2 = b & 1;
> > +  return (t1 == 0) != (t2 == 0);
> > +}
> > +
> > +/* Verify all functions canonicalize to xor forms.  */
> > +/* { dg-final { scan-tree-dump-times "\\^" 4 "optimized" } } */
> > diff --git a/gcc/testsuite/gcc.dg/tree-ssa/bool-eq-pow2.c
> b/gcc/testsuite/gcc.dg/tree-ssa/bool-eq-pow2.c
> > new file mode 100644
> > index 000000000..109c5f036
> > --- /dev/null
> > +++ b/gcc/testsuite/gcc.dg/tree-ssa/bool-eq-pow2.c
> > @@ -0,0 +1,89 @@
> > +/* { dg-do compile } */
> > +/* { dg-options "-O1 -fdump-tree-optimized" } */
> > +
> > +typedef unsigned int u32;
> > +
> > +_Bool
> > +eq_eq_outer_eq_mask2 (u32 a, u32 b)
> > +{
> > +  u32 t1 = a & 2;
> > +  u32 t2 = b & 2;
> > +  return (t1 == 0) == (t2 == 0);
> > +}
> > +
> > +_Bool
> > +eq_eq_outer_eq_mask4 (u32 a, u32 b)
> > +{
> > +  u32 t1 = a & 4;
> > +  u32 t2 = b & 4;
> > +  return (t1 == 0) == (t2 == 0);
> > +}
> > +
> > +_Bool
> > +eq_eq_outer_ne (u32 a, u32 b)
> > +{
> > +  u32 t1 = a & 1;
> > +  u32 t2 = b & 1;
> > +  return (t1 == 0) != (t2 == 0);
> > +}
> > +
> > +_Bool
> > +ne_eq_outer_eq (u32 a, u32 b)
> > +{
> > +  u32 t1 = a & 1;
> > +  u32 t2 = b & 1;
> > +  return (t1 != 0) == (t2 == 0);
> > +}
> > +
> > +_Bool
> > +ne_eq_outer_ne (u32 a, u32 b)
> > +{
> > +  u32 t1 = a & 1;
> > +  u32 t2 = b & 1;
> > +  return (t1 != 0) != (t2 == 0);
> > +}
> > +
> > +_Bool
> > +eq_ne_outer_eq (u32 a, u32 b)
> > +{
> > +  u32 t1 = a & 1;
> > +  u32 t2 = b & 1;
> > +  return (t1 == 0) == (t2 != 0);
> > +}
> > +
> > +_Bool
> > +eq_ne_outer_ne (u32 a, u32 b)
> > +{
> > +  u32 t1 = a & 1;
> > +  u32 t2 = b & 1;
> > +  return (t1 == 0) != (t2 != 0);
> > +}
> > +
> > +_Bool
> > +ne_ne_outer_eq (u32 a, u32 b)
> > +{
> > +  u32 t1 = a & 1;
> > +  u32 t2 = b & 1;
> > +  return (t1 != 0) == (t2 != 0);
> > +}
> > +
> > +_Bool
> > +ne_ne_outer_ne (u32 a, u32 b)
> > +{
> > +  u32 t1 = a & 1;
> > +  u32 t2 = b & 1;
> > +  return (t1 != 0) != (t2 != 0);
> > +}
> > +
> > +/* Non-power-of-2: should not be simplified.  */
> > +_Bool
> > +eq_eq_outer_eq_nonpow2 (u32 a, u32 b)
> > +{
> > +  u32 t1 = a & 3;
> > +  u32 t2 = b & 3;
> > +  return (t1 == 0) == (t2 == 0);
> > +}
> > +
> > +/* Verify power-of-2 masks are simplified, non-power-of-2 masks are
> not.  */
> > +/* { dg-final { scan-tree-dump-times "a_\[0-9\]+\\(D\\) \\^
> b_\[0-9\]+\\(D\\)" 9 "optimized" } } */
> > +/* { dg-final { scan-tree-dump-times "& 3" 2 "optimized" } } */
> > --
> > 2.43.0
> >
>