[v2] match.pd: (A>>bool) == 0 -> (unsigned)A) <= bool [PR119420]

  From: Daniel Barboza <daniel.barboza@oss.qualcomm.com>

Note that we're not adding its counterpart:

"(A>>bool) != 0 -> (unsigned)A) > bool"

Because it will collide with patterns that handles builtin_clz (e.g.
clz-complement-int.c tree-ssa test).

Bootstrapped and regression tested in x86.

        PR tree-optimization/119420

gcc/ChangeLog:

	* match.pd(`(A>>bool) EQ 0 -> (unsigned)A) LE bool`): New
	pattern.

gcc/testsuite/ChangeLog:

        * gcc.dg/tree-ssa/pr119420.c: New test.
---

Changes from v1:
- fixed formatting of (with ...) block;
- added match.pd comment about the interaction with builtin_clz and why
  we're not adding the NE variation.
- v1 link: https://gcc.gnu.org/pipermail/gcc-patches/2026-March/709727.html

 gcc/match.pd                             | 11 +++++++++++
 gcc/testsuite/gcc.dg/tree-ssa/pr119420.c | 23 +++++++++++++++++++++++
 2 files changed, 34 insertions(+)
 create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/pr119420.c
  

On Tue, Apr 7, 2026 at 2:20 PM Daniel Henrique Barboza
<daniel.barboza@oss.qualcomm.com> wrote:
>
> From: Daniel Barboza <daniel.barboza@oss.qualcomm.com>
>
> Note that we're not adding its counterpart:
>
> "(A>>bool) != 0 -> (unsigned)A) > bool"
>
> Because it will collide with patterns that handles builtin_clz (e.g.
> clz-complement-int.c tree-ssa test).

I think this can be done for any constant shift (and not just for bool value).
From combine.cc:
  /* If we have (compare (xshiftrt FOO N) (const_int C)) and
     the low order N bits of FOO are known to be zero, we can do this
     by comparing FOO with C shifted left N bits so long as no
     overflow occurs.  Even if the low order N bits of FOO aren't known
     to be zero, if the comparison is >= or < we can use the same
     optimization and for > or <= by setting all the low
     order N bits in the comparison constant.  */

Handling more than just bool would also fix PR 124808. But maybe that
should be handled separately since this case is for the non-constant
bool case.

Thanks,
Andrew

>
> Bootstrapped and regression tested in x86.
>
>         PR tree-optimization/119420
>
> gcc/ChangeLog:
>
>         * match.pd(`(A>>bool) EQ 0 -> (unsigned)A) LE bool`): New
>         pattern.
>
> gcc/testsuite/ChangeLog:
>
>         * gcc.dg/tree-ssa/pr119420.c: New test.
> ---
>
> Changes from v1:
> - fixed formatting of (with ...) block;
> - added match.pd comment about the interaction with builtin_clz and why
>   we're not adding the NE variation.
> - v1 link: https://gcc.gnu.org/pipermail/gcc-patches/2026-March/709727.html
>
>  gcc/match.pd                             | 11 +++++++++++
>  gcc/testsuite/gcc.dg/tree-ssa/pr119420.c | 23 +++++++++++++++++++++++
>  2 files changed, 34 insertions(+)
>  create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/pr119420.c
>
> diff --git a/gcc/match.pd b/gcc/match.pd
> index 7f16fd4e081..b7a8ce420b4 100644
> --- a/gcc/match.pd
> +++ b/gcc/match.pd
> @@ -5367,6 +5367,17 @@ DEFINE_INT_AND_FLOAT_ROUND_FN (RINT)
>        @0)))))
>  #endif
>
> +/* PR119420: (A >> bool) == 0 -> (unsigned)a <= (unsigned)bool
> +
> +   We're not adding its NE counterpart:
> +   "(A>>bool) != 0 -> (unsigned)A) > bool"
> +   Because it collides with patterns that handles builtin_clz, as
> +   shown in clz-complement-int.c tree-ssa test.  */
> +(simplify
> + (eq (rshift @0 zero_one_valued_p@1) integer_zerop)
> + (with { tree utype = unsigned_type_for (TREE_TYPE (@0)); }
> +  (le (convert:utype @0) (convert:utype @1))))
> +
>  /* Rewrite an LROTATE_EXPR by a constant into an
>     RROTATE_EXPR by a new constant.  */
>  (simplify
> diff --git a/gcc/testsuite/gcc.dg/tree-ssa/pr119420.c b/gcc/testsuite/gcc.dg/tree-ssa/pr119420.c
> new file mode 100644
> index 00000000000..3169650fe66
> --- /dev/null
> +++ b/gcc/testsuite/gcc.dg/tree-ssa/pr119420.c
> @@ -0,0 +1,23 @@
> +/* { dg-additional-options -O2 } */
> +/* { dg-additional-options -fdump-tree-optimized } */
> +
> +int ll (signed a)
> +{
> +  int d = a >> 1;
> +  return d == 0;
> +}
> +
> +int ll1 (signed a)
> +{
> +  int d = a & ~1;
> +  return d == 0;
> +}
> +
> +int ll2 (signed a)
> +{
> +  unsigned aa = a;
> +  return aa <= 1;
> +}
> +
> +/* { dg-final { scan-tree-dump-times " >> " 0 optimized } } */
> +/* { dg-final { scan-tree-dump-times " <= " 3 optimized } } */
> --
> 2.43.0
>
  

On 4/8/2026 2:26 AM, Andrew Pinski wrote:
> On Tue, Apr 7, 2026 at 2:20 PM Daniel Henrique Barboza
> <daniel.barboza@oss.qualcomm.com> wrote:
>>
>> From: Daniel Barboza <daniel.barboza@oss.qualcomm.com>
>>
>> Note that we're not adding its counterpart:
>>
>> "(A>>bool) != 0 -> (unsigned)A) > bool"
>>
>> Because it will collide with patterns that handles builtin_clz (e.g.
>> clz-complement-int.c tree-ssa test).
> 
> I think this can be done for any constant shift (and not just for bool value).
>  From combine.cc:
>    /* If we have (compare (xshiftrt FOO N) (const_int C)) and
>       the low order N bits of FOO are known to be zero, we can do this
>       by comparing FOO with C shifted left N bits so long as no
>       overflow occurs.  Even if the low order N bits of FOO aren't known
>       to be zero, if the comparison is >= or < we can use the same
>       optimization and for > or <= by setting all the low
>       order N bits in the comparison constant.  */
> 
> Handling more than just bool would also fix PR 124808. But maybe that
> should be handled separately since this case is for the non-constant
> bool case.

I'll make changes to handle constant shifts and maybe we can help alleviate
124808.  That PR might require additional work anyway but at least progress
was made.


Thanks,
Daniel

> 
> Thanks,
> Andrew
> 
>>
>> Bootstrapped and regression tested in x86.
>>
>>          PR tree-optimization/119420
>>
>> gcc/ChangeLog:
>>
>>          * match.pd(`(A>>bool) EQ 0 -> (unsigned)A) LE bool`): New
>>          pattern.
>>
>> gcc/testsuite/ChangeLog:
>>
>>          * gcc.dg/tree-ssa/pr119420.c: New test.
>> ---
>>
>> Changes from v1:
>> - fixed formatting of (with ...) block;
>> - added match.pd comment about the interaction with builtin_clz and why
>>    we're not adding the NE variation.
>> - v1 link: https://gcc.gnu.org/pipermail/gcc-patches/2026-March/709727.html
>>
>>   gcc/match.pd                             | 11 +++++++++++
>>   gcc/testsuite/gcc.dg/tree-ssa/pr119420.c | 23 +++++++++++++++++++++++
>>   2 files changed, 34 insertions(+)
>>   create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/pr119420.c
>>
>> diff --git a/gcc/match.pd b/gcc/match.pd
>> index 7f16fd4e081..b7a8ce420b4 100644
>> --- a/gcc/match.pd
>> +++ b/gcc/match.pd
>> @@ -5367,6 +5367,17 @@ DEFINE_INT_AND_FLOAT_ROUND_FN (RINT)
>>         @0)))))
>>   #endif
>>
>> +/* PR119420: (A >> bool) == 0 -> (unsigned)a <= (unsigned)bool
>> +
>> +   We're not adding its NE counterpart:
>> +   "(A>>bool) != 0 -> (unsigned)A) > bool"
>> +   Because it collides with patterns that handles builtin_clz, as
>> +   shown in clz-complement-int.c tree-ssa test.  */
>> +(simplify
>> + (eq (rshift @0 zero_one_valued_p@1) integer_zerop)
>> + (with { tree utype = unsigned_type_for (TREE_TYPE (@0)); }
>> +  (le (convert:utype @0) (convert:utype @1))))
>> +
>>   /* Rewrite an LROTATE_EXPR by a constant into an
>>      RROTATE_EXPR by a new constant.  */
>>   (simplify
>> diff --git a/gcc/testsuite/gcc.dg/tree-ssa/pr119420.c b/gcc/testsuite/gcc.dg/tree-ssa/pr119420.c
>> new file mode 100644
>> index 00000000000..3169650fe66
>> --- /dev/null
>> +++ b/gcc/testsuite/gcc.dg/tree-ssa/pr119420.c
>> @@ -0,0 +1,23 @@
>> +/* { dg-additional-options -O2 } */
>> +/* { dg-additional-options -fdump-tree-optimized } */
>> +
>> +int ll (signed a)
>> +{
>> +  int d = a >> 1;
>> +  return d == 0;
>> +}
>> +
>> +int ll1 (signed a)
>> +{
>> +  int d = a & ~1;
>> +  return d == 0;
>> +}
>> +
>> +int ll2 (signed a)
>> +{
>> +  unsigned aa = a;
>> +  return aa <= 1;
>> +}
>> +
>> +/* { dg-final { scan-tree-dump-times " >> " 0 optimized } } */
>> +/* { dg-final { scan-tree-dump-times " <= " 3 optimized } } */
>> --
>> 2.43.0
>>
  

On 4/8/2026 2:26 AM, Andrew Pinski wrote:
> On Tue, Apr 7, 2026 at 2:20 PM Daniel Henrique Barboza
> <daniel.barboza@oss.qualcomm.com> wrote:
>>
>> From: Daniel Barboza <daniel.barboza@oss.qualcomm.com>
>>
>> Note that we're not adding its counterpart:
>>
>> "(A>>bool) != 0 -> (unsigned)A) > bool"
>>
>> Because it will collide with patterns that handles builtin_clz (e.g.
>> clz-complement-int.c tree-ssa test).
> 
> I think this can be done for any constant shift (and not just for bool value).
>  From combine.cc:
>    /* If we have (compare (xshiftrt FOO N) (const_int C)) and
>       the low order N bits of FOO are known to be zero, we can do this
>       by comparing FOO with C shifted left N bits so long as no
>       overflow occurs.  Even if the low order N bits of FOO aren't known
>       to be zero, if the comparison is >= or < we can use the same
>       optimization and for > or <= by setting all the low
>       order N bits in the comparison constant.  */
> 
> Handling more than just bool would also fix PR 124808. But maybe that
> should be handled separately since this case is for the non-constant
> bool case.

After trying to fit in the logic in this same patch I figured you're right.
PR124808 is too complex to be added as a side case of this pattern.

I'll create a separated patch for it.  Let's keep this one as is.


Thanks,
Daniel

> 
> Thanks,
> Andrew
> 
>>
>> Bootstrapped and regression tested in x86.
>>
>>          PR tree-optimization/119420
>>
>> gcc/ChangeLog:
>>
>>          * match.pd(`(A>>bool) EQ 0 -> (unsigned)A) LE bool`): New
>>          pattern.
>>
>> gcc/testsuite/ChangeLog:
>>
>>          * gcc.dg/tree-ssa/pr119420.c: New test.
>> ---
>>
>> Changes from v1:
>> - fixed formatting of (with ...) block;
>> - added match.pd comment about the interaction with builtin_clz and why
>>    we're not adding the NE variation.
>> - v1 link: https://gcc.gnu.org/pipermail/gcc-patches/2026-March/709727.html
>>
>>   gcc/match.pd                             | 11 +++++++++++
>>   gcc/testsuite/gcc.dg/tree-ssa/pr119420.c | 23 +++++++++++++++++++++++
>>   2 files changed, 34 insertions(+)
>>   create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/pr119420.c
>>
>> diff --git a/gcc/match.pd b/gcc/match.pd
>> index 7f16fd4e081..b7a8ce420b4 100644
>> --- a/gcc/match.pd
>> +++ b/gcc/match.pd
>> @@ -5367,6 +5367,17 @@ DEFINE_INT_AND_FLOAT_ROUND_FN (RINT)
>>         @0)))))
>>   #endif
>>
>> +/* PR119420: (A >> bool) == 0 -> (unsigned)a <= (unsigned)bool
>> +
>> +   We're not adding its NE counterpart:
>> +   "(A>>bool) != 0 -> (unsigned)A) > bool"
>> +   Because it collides with patterns that handles builtin_clz, as
>> +   shown in clz-complement-int.c tree-ssa test.  */
>> +(simplify
>> + (eq (rshift @0 zero_one_valued_p@1) integer_zerop)
>> + (with { tree utype = unsigned_type_for (TREE_TYPE (@0)); }
>> +  (le (convert:utype @0) (convert:utype @1))))
>> +
>>   /* Rewrite an LROTATE_EXPR by a constant into an
>>      RROTATE_EXPR by a new constant.  */
>>   (simplify
>> diff --git a/gcc/testsuite/gcc.dg/tree-ssa/pr119420.c b/gcc/testsuite/gcc.dg/tree-ssa/pr119420.c
>> new file mode 100644
>> index 00000000000..3169650fe66
>> --- /dev/null
>> +++ b/gcc/testsuite/gcc.dg/tree-ssa/pr119420.c
>> @@ -0,0 +1,23 @@
>> +/* { dg-additional-options -O2 } */
>> +/* { dg-additional-options -fdump-tree-optimized } */
>> +
>> +int ll (signed a)
>> +{
>> +  int d = a >> 1;
>> +  return d == 0;
>> +}
>> +
>> +int ll1 (signed a)
>> +{
>> +  int d = a & ~1;
>> +  return d == 0;
>> +}
>> +
>> +int ll2 (signed a)
>> +{
>> +  unsigned aa = a;
>> +  return aa <= 1;
>> +}
>> +
>> +/* { dg-final { scan-tree-dump-times " >> " 0 optimized } } */
>> +/* { dg-final { scan-tree-dump-times " <= " 3 optimized } } */
>> --
>> 2.43.0
>>
  

On Tue, Apr 7, 2026 at 2:20 PM Daniel Henrique Barboza
<daniel.barboza@oss.qualcomm.com> wrote:
>
> From: Daniel Barboza <daniel.barboza@oss.qualcomm.com>
>
> Note that we're not adding its counterpart:
>
> "(A>>bool) != 0 -> (unsigned)A) > bool"
>
> Because it will collide with patterns that handles builtin_clz (e.g.
> clz-complement-int.c tree-ssa test).
>
> Bootstrapped and regression tested in x86.
>
>         PR tree-optimization/119420
>
> gcc/ChangeLog:
>
>         * match.pd(`(A>>bool) EQ 0 -> (unsigned)A) LE bool`): New
>         pattern.
>
> gcc/testsuite/ChangeLog:
>
>         * gcc.dg/tree-ssa/pr119420.c: New test.
> ---
>
> Changes from v1:
> - fixed formatting of (with ...) block;
> - added match.pd comment about the interaction with builtin_clz and why
>   we're not adding the NE variation.
> - v1 link: https://gcc.gnu.org/pipermail/gcc-patches/2026-March/709727.html
>
>  gcc/match.pd                             | 11 +++++++++++
>  gcc/testsuite/gcc.dg/tree-ssa/pr119420.c | 23 +++++++++++++++++++++++
>  2 files changed, 34 insertions(+)
>  create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/pr119420.c
>
> diff --git a/gcc/match.pd b/gcc/match.pd
> index 7f16fd4e081..b7a8ce420b4 100644
> --- a/gcc/match.pd
> +++ b/gcc/match.pd
> @@ -5367,6 +5367,17 @@ DEFINE_INT_AND_FLOAT_ROUND_FN (RINT)
>        @0)))))
>  #endif
>
> +/* PR119420: (A >> bool) == 0 -> (unsigned)a <= (unsigned)bool
> +
> +   We're not adding its NE counterpart:
> +   "(A>>bool) != 0 -> (unsigned)A) > bool"
> +   Because it collides with patterns that handles builtin_clz, as
> +   shown in clz-complement-int.c tree-ssa test.  */
> +(simplify
> + (eq (rshift @0 zero_one_valued_p@1) integer_zerop)
> + (with { tree utype = unsigned_type_for (TREE_TYPE (@0)); }
> +  (le (convert:utype @0) (convert:utype @1))))

Maybe for the ne case you could add a :s on the rshift for now. I
filed https://gcc.gnu.org/bugzilla/show_bug.cgi?id=124833 for the non
single use case.
That seems like what LLVM does. I think the above also would need the
:s on the rshift for the same reason.


Thanks,
Andrew Pinski

> +
>  /* Rewrite an LROTATE_EXPR by a constant into an
>     RROTATE_EXPR by a new constant.  */
>  (simplify
> diff --git a/gcc/testsuite/gcc.dg/tree-ssa/pr119420.c b/gcc/testsuite/gcc.dg/tree-ssa/pr119420.c
> new file mode 100644
> index 00000000000..3169650fe66
> --- /dev/null
> +++ b/gcc/testsuite/gcc.dg/tree-ssa/pr119420.c
> @@ -0,0 +1,23 @@
> +/* { dg-additional-options -O2 } */
> +/* { dg-additional-options -fdump-tree-optimized } */
> +
> +int ll (signed a)
> +{
> +  int d = a >> 1;
> +  return d == 0;
> +}
> +
> +int ll1 (signed a)
> +{
> +  int d = a & ~1;
> +  return d == 0;
> +}
> +
> +int ll2 (signed a)
> +{
> +  unsigned aa = a;
> +  return aa <= 1;
> +}
> +
> +/* { dg-final { scan-tree-dump-times " >> " 0 optimized } } */
> +/* { dg-final { scan-tree-dump-times " <= " 3 optimized } } */
> --
> 2.43.0
>
  

On 4/9/2026 3:10 PM, Andrew Pinski wrote:
> On Tue, Apr 7, 2026 at 2:20 PM Daniel Henrique Barboza
> <daniel.barboza@oss.qualcomm.com> wrote:
>>
>> From: Daniel Barboza <daniel.barboza@oss.qualcomm.com>
>>
>> Note that we're not adding its counterpart:
>>
>> "(A>>bool) != 0 -> (unsigned)A) > bool"
>>
>> Because it will collide with patterns that handles builtin_clz (e.g.
>> clz-complement-int.c tree-ssa test).
>>
>> Bootstrapped and regression tested in x86.
>>
>>          PR tree-optimization/119420
>>
>> gcc/ChangeLog:
>>
>>          * match.pd(`(A>>bool) EQ 0 -> (unsigned)A) LE bool`): New
>>          pattern.
>>
>> gcc/testsuite/ChangeLog:
>>
>>          * gcc.dg/tree-ssa/pr119420.c: New test.
>> ---
>>
>> Changes from v1:
>> - fixed formatting of (with ...) block;
>> - added match.pd comment about the interaction with builtin_clz and why
>>    we're not adding the NE variation.
>> - v1 link: https://gcc.gnu.org/pipermail/gcc-patches/2026-March/709727.html
>>
>>   gcc/match.pd                             | 11 +++++++++++
>>   gcc/testsuite/gcc.dg/tree-ssa/pr119420.c | 23 +++++++++++++++++++++++
>>   2 files changed, 34 insertions(+)
>>   create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/pr119420.c
>>
>> diff --git a/gcc/match.pd b/gcc/match.pd
>> index 7f16fd4e081..b7a8ce420b4 100644
>> --- a/gcc/match.pd
>> +++ b/gcc/match.pd
>> @@ -5367,6 +5367,17 @@ DEFINE_INT_AND_FLOAT_ROUND_FN (RINT)
>>         @0)))))
>>   #endif
>>
>> +/* PR119420: (A >> bool) == 0 -> (unsigned)a <= (unsigned)bool
>> +
>> +   We're not adding its NE counterpart:
>> +   "(A>>bool) != 0 -> (unsigned)A) > bool"
>> +   Because it collides with patterns that handles builtin_clz, as
>> +   shown in clz-complement-int.c tree-ssa test.  */
>> +(simplify
>> + (eq (rshift @0 zero_one_valued_p@1) integer_zerop)
>> + (with { tree utype = unsigned_type_for (TREE_TYPE (@0)); }
>> +  (le (convert:utype @0) (convert:utype @1))))
> 
> Maybe for the ne case you could add a :s on the rshift for now. I
> filed https://gcc.gnu.org/bugzilla/show_bug.cgi?id=124833 for the non
> single use case.
> That seems like what LLVM does. I think the above also would need the
> :s on the rshift for the same reason.

That brings me back to a patch that is pending a review/redo:

"Re: [PATCH v2] match.pd: simplify lshift const cmp using bit_and [PR124019]"

Jeff mentioned that this patch breaks a CRIS test, and adding ":s" would be
a solution, and the pattern handled there:

"A << CST1 EQ|NE CST2 -> (A & CSTmask) EQ|NE (CST2 >> CST1); "

it is also a pattern that happens to collide with the builtin_ctz call with
CST1 = 1 (which is not handled in that patch).

And the pattern you suggested for PR124808 is also similar to these 2 (by the
way your idea improves that loop):

(A >> CST1) cmp CST2  ->  A cmp (CST2 << CST1)


My point here is that maybe there's an overall design/pattern in all these
optimizations with this overall format "A lshift|rshift CST1 cmp CST2" due
to how they match these CTZ/CLZ builtins, and maybe we should default to
use ":s" in all related patterns.  Does that make sense?


Daniel

> 
> 
> Thanks,
> Andrew Pinski
> 
>> +
>>   /* Rewrite an LROTATE_EXPR by a constant into an
>>      RROTATE_EXPR by a new constant.  */
>>   (simplify
>> diff --git a/gcc/testsuite/gcc.dg/tree-ssa/pr119420.c b/gcc/testsuite/gcc.dg/tree-ssa/pr119420.c
>> new file mode 100644
>> index 00000000000..3169650fe66
>> --- /dev/null
>> +++ b/gcc/testsuite/gcc.dg/tree-ssa/pr119420.c
>> @@ -0,0 +1,23 @@
>> +/* { dg-additional-options -O2 } */
>> +/* { dg-additional-options -fdump-tree-optimized } */
>> +
>> +int ll (signed a)
>> +{
>> +  int d = a >> 1;
>> +  return d == 0;
>> +}
>> +
>> +int ll1 (signed a)
>> +{
>> +  int d = a & ~1;
>> +  return d == 0;
>> +}
>> +
>> +int ll2 (signed a)
>> +{
>> +  unsigned aa = a;
>> +  return aa <= 1;
>> +}
>> +
>> +/* { dg-final { scan-tree-dump-times " >> " 0 optimized } } */
>> +/* { dg-final { scan-tree-dump-times " <= " 3 optimized } } */
>> --
>> 2.43.0
>>
  

On Thu, Apr 9, 2026 at 11:50 AM Daniel Henrique Barboza
<daniel.barboza@oss.qualcomm.com> wrote:
>
>
>
> On 4/9/2026 3:10 PM, Andrew Pinski wrote:
> > On Tue, Apr 7, 2026 at 2:20 PM Daniel Henrique Barboza
> > <daniel.barboza@oss.qualcomm.com> wrote:
> >>
> >> From: Daniel Barboza <daniel.barboza@oss.qualcomm.com>
> >>
> >> Note that we're not adding its counterpart:
> >>
> >> "(A>>bool) != 0 -> (unsigned)A) > bool"
> >>
> >> Because it will collide with patterns that handles builtin_clz (e.g.
> >> clz-complement-int.c tree-ssa test).
> >>
> >> Bootstrapped and regression tested in x86.
> >>
> >>          PR tree-optimization/119420
> >>
> >> gcc/ChangeLog:
> >>
> >>          * match.pd(`(A>>bool) EQ 0 -> (unsigned)A) LE bool`): New
> >>          pattern.
> >>
> >> gcc/testsuite/ChangeLog:
> >>
> >>          * gcc.dg/tree-ssa/pr119420.c: New test.
> >> ---
> >>
> >> Changes from v1:
> >> - fixed formatting of (with ...) block;
> >> - added match.pd comment about the interaction with builtin_clz and why
> >>    we're not adding the NE variation.
> >> - v1 link: https://gcc.gnu.org/pipermail/gcc-patches/2026-March/709727.html
> >>
> >>   gcc/match.pd                             | 11 +++++++++++
> >>   gcc/testsuite/gcc.dg/tree-ssa/pr119420.c | 23 +++++++++++++++++++++++
> >>   2 files changed, 34 insertions(+)
> >>   create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/pr119420.c
> >>
> >> diff --git a/gcc/match.pd b/gcc/match.pd
> >> index 7f16fd4e081..b7a8ce420b4 100644
> >> --- a/gcc/match.pd
> >> +++ b/gcc/match.pd
> >> @@ -5367,6 +5367,17 @@ DEFINE_INT_AND_FLOAT_ROUND_FN (RINT)
> >>         @0)))))
> >>   #endif
> >>
> >> +/* PR119420: (A >> bool) == 0 -> (unsigned)a <= (unsigned)bool
> >> +
> >> +   We're not adding its NE counterpart:
> >> +   "(A>>bool) != 0 -> (unsigned)A) > bool"
> >> +   Because it collides with patterns that handles builtin_clz, as
> >> +   shown in clz-complement-int.c tree-ssa test.  */
> >> +(simplify
> >> + (eq (rshift @0 zero_one_valued_p@1) integer_zerop)
> >> + (with { tree utype = unsigned_type_for (TREE_TYPE (@0)); }
> >> +  (le (convert:utype @0) (convert:utype @1))))
> >
> > Maybe for the ne case you could add a :s on the rshift for now. I
> > filed https://gcc.gnu.org/bugzilla/show_bug.cgi?id=124833 for the non
> > single use case.
> > That seems like what LLVM does. I think the above also would need the
> > :s on the rshift for the same reason.
>
> That brings me back to a patch that is pending a review/redo:
>
> "Re: [PATCH v2] match.pd: simplify lshift const cmp using bit_and [PR124019]"
>
> Jeff mentioned that this patch breaks a CRIS test, and adding ":s" would be
> a solution, and the pattern handled there:
>
> "A << CST1 EQ|NE CST2 -> (A & CSTmask) EQ|NE (CST2 >> CST1); "
>
> it is also a pattern that happens to collide with the builtin_ctz call with
> CST1 = 1 (which is not handled in that patch).
>
> And the pattern you suggested for PR124808 is also similar to these 2 (by the
> way your idea improves that loop):
>
> (A >> CST1) cmp CST2  ->  A cmp (CST2 << CST1)
>
>
> My point here is that maybe there's an overall design/pattern in all these
> optimizations with this overall format "A lshift|rshift CST1 cmp CST2" due
> to how they match these CTZ/CLZ builtins, and maybe we should default to
> use ":s" in all related patterns.  Does that make sense?

Yes, I think so. Though in some cases having `:s` there is worse.
Maybe the issue is forwprop needs to be limiting how it handles
conditionals for loop exits.
Currently forwprop calls fold_stmt and not limiting the valueization
here. But maybe for loop exits we should.
This would allow us to remove the single_use/`:s` on some more
patterns (e.g. https://gcc.gnu.org/bugzilla/show_bug.cgi?id=122186).
Let me think about this some more.

Thanks,
Andrew


>
>
> Daniel
>
> >
> >
> > Thanks,
> > Andrew Pinski
> >
> >> +
> >>   /* Rewrite an LROTATE_EXPR by a constant into an
> >>      RROTATE_EXPR by a new constant.  */
> >>   (simplify
> >> diff --git a/gcc/testsuite/gcc.dg/tree-ssa/pr119420.c b/gcc/testsuite/gcc.dg/tree-ssa/pr119420.c
> >> new file mode 100644
> >> index 00000000000..3169650fe66
> >> --- /dev/null
> >> +++ b/gcc/testsuite/gcc.dg/tree-ssa/pr119420.c
> >> @@ -0,0 +1,23 @@
> >> +/* { dg-additional-options -O2 } */
> >> +/* { dg-additional-options -fdump-tree-optimized } */
> >> +
> >> +int ll (signed a)
> >> +{
> >> +  int d = a >> 1;
> >> +  return d == 0;
> >> +}
> >> +
> >> +int ll1 (signed a)
> >> +{
> >> +  int d = a & ~1;
> >> +  return d == 0;
> >> +}
> >> +
> >> +int ll2 (signed a)
> >> +{
> >> +  unsigned aa = a;
> >> +  return aa <= 1;
> >> +}
> >> +
> >> +/* { dg-final { scan-tree-dump-times " >> " 0 optimized } } */
> >> +/* { dg-final { scan-tree-dump-times " <= " 3 optimized } } */
> >> --
> >> 2.43.0
> >>
>
  

On Thu, Apr 9, 2026 at 9:04 PM Andrew Pinski
<andrew.pinski@oss.qualcomm.com> wrote:
>
> On Thu, Apr 9, 2026 at 11:50 AM Daniel Henrique Barboza
> <daniel.barboza@oss.qualcomm.com> wrote:
> >
> >
> >
> > On 4/9/2026 3:10 PM, Andrew Pinski wrote:
> > > On Tue, Apr 7, 2026 at 2:20 PM Daniel Henrique Barboza
> > > <daniel.barboza@oss.qualcomm.com> wrote:
> > >>
> > >> From: Daniel Barboza <daniel.barboza@oss.qualcomm.com>
> > >>
> > >> Note that we're not adding its counterpart:
> > >>
> > >> "(A>>bool) != 0 -> (unsigned)A) > bool"
> > >>
> > >> Because it will collide with patterns that handles builtin_clz (e.g.
> > >> clz-complement-int.c tree-ssa test).
> > >>
> > >> Bootstrapped and regression tested in x86.
> > >>
> > >>          PR tree-optimization/119420
> > >>
> > >> gcc/ChangeLog:
> > >>
> > >>          * match.pd(`(A>>bool) EQ 0 -> (unsigned)A) LE bool`): New
> > >>          pattern.
> > >>
> > >> gcc/testsuite/ChangeLog:
> > >>
> > >>          * gcc.dg/tree-ssa/pr119420.c: New test.
> > >> ---
> > >>
> > >> Changes from v1:
> > >> - fixed formatting of (with ...) block;
> > >> - added match.pd comment about the interaction with builtin_clz and why
> > >>    we're not adding the NE variation.
> > >> - v1 link: https://gcc.gnu.org/pipermail/gcc-patches/2026-March/709727.html
> > >>
> > >>   gcc/match.pd                             | 11 +++++++++++
> > >>   gcc/testsuite/gcc.dg/tree-ssa/pr119420.c | 23 +++++++++++++++++++++++
> > >>   2 files changed, 34 insertions(+)
> > >>   create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/pr119420.c
> > >>
> > >> diff --git a/gcc/match.pd b/gcc/match.pd
> > >> index 7f16fd4e081..b7a8ce420b4 100644
> > >> --- a/gcc/match.pd
> > >> +++ b/gcc/match.pd
> > >> @@ -5367,6 +5367,17 @@ DEFINE_INT_AND_FLOAT_ROUND_FN (RINT)
> > >>         @0)))))
> > >>   #endif
> > >>
> > >> +/* PR119420: (A >> bool) == 0 -> (unsigned)a <= (unsigned)bool
> > >> +
> > >> +   We're not adding its NE counterpart:
> > >> +   "(A>>bool) != 0 -> (unsigned)A) > bool"
> > >> +   Because it collides with patterns that handles builtin_clz, as
> > >> +   shown in clz-complement-int.c tree-ssa test.  */
> > >> +(simplify
> > >> + (eq (rshift @0 zero_one_valued_p@1) integer_zerop)
> > >> + (with { tree utype = unsigned_type_for (TREE_TYPE (@0)); }
> > >> +  (le (convert:utype @0) (convert:utype @1))))
> > >
> > > Maybe for the ne case you could add a :s on the rshift for now. I
> > > filed https://gcc.gnu.org/bugzilla/show_bug.cgi?id=124833 for the non
> > > single use case.
> > > That seems like what LLVM does. I think the above also would need the
> > > :s on the rshift for the same reason.
> >
> > That brings me back to a patch that is pending a review/redo:
> >
> > "Re: [PATCH v2] match.pd: simplify lshift const cmp using bit_and [PR124019]"
> >
> > Jeff mentioned that this patch breaks a CRIS test, and adding ":s" would be
> > a solution, and the pattern handled there:
> >
> > "A << CST1 EQ|NE CST2 -> (A & CSTmask) EQ|NE (CST2 >> CST1); "
> >
> > it is also a pattern that happens to collide with the builtin_ctz call with
> > CST1 = 1 (which is not handled in that patch).
> >
> > And the pattern you suggested for PR124808 is also similar to these 2 (by the
> > way your idea improves that loop):
> >
> > (A >> CST1) cmp CST2  ->  A cmp (CST2 << CST1)
> >
> >
> > My point here is that maybe there's an overall design/pattern in all these
> > optimizations with this overall format "A lshift|rshift CST1 cmp CST2" due
> > to how they match these CTZ/CLZ builtins, and maybe we should default to
> > use ":s" in all related patterns.  Does that make sense?
>
> Yes, I think so. Though in some cases having `:s` there is worse.
> Maybe the issue is forwprop needs to be limiting how it handles
> conditionals for loop exits.
> Currently forwprop calls fold_stmt and not limiting the valueization
> here. But maybe for loop exits we should.
> This would allow us to remove the single_use/`:s` on some more
> patterns (e.g. https://gcc.gnu.org/bugzilla/show_bug.cgi?id=122186).
> Let me think about this some more.

It's also if you have two uses that can be folded in a similar way,
leading to CSE of the generated extra stmt that we cannot anticipate
(or even try).  At one point I thought that forwprop could do
:s ignoring folding, but with the ability to roll-back, and do some
form of costing after a local CSE on the result, costing before/after
for "connected components".  But I have never sat down to think
about how to actually reasonably implement such thing - it might
be interesting to get feedback from folding like "this would have
simplified, but did not because of multi-use of @1, @2 ...", and
then somehow gather possible multi-use folding roots, "unshare",
fold, try to CSE and cost the set of expressions.  But that does not
play well with the somewhat nice lattice setup we have in forwprop
right now.

Richard.

>
> Thanks,
> Andrew
>
>
> >
> >
> > Daniel
> >
> > >
> > >
> > > Thanks,
> > > Andrew Pinski
> > >
> > >> +
> > >>   /* Rewrite an LROTATE_EXPR by a constant into an
> > >>      RROTATE_EXPR by a new constant.  */
> > >>   (simplify
> > >> diff --git a/gcc/testsuite/gcc.dg/tree-ssa/pr119420.c b/gcc/testsuite/gcc.dg/tree-ssa/pr119420.c
> > >> new file mode 100644
> > >> index 00000000000..3169650fe66
> > >> --- /dev/null
> > >> +++ b/gcc/testsuite/gcc.dg/tree-ssa/pr119420.c
> > >> @@ -0,0 +1,23 @@
> > >> +/* { dg-additional-options -O2 } */
> > >> +/* { dg-additional-options -fdump-tree-optimized } */
> > >> +
> > >> +int ll (signed a)
> > >> +{
> > >> +  int d = a >> 1;
> > >> +  return d == 0;
> > >> +}
> > >> +
> > >> +int ll1 (signed a)
> > >> +{
> > >> +  int d = a & ~1;
> > >> +  return d == 0;
> > >> +}
> > >> +
> > >> +int ll2 (signed a)
> > >> +{
> > >> +  unsigned aa = a;
> > >> +  return aa <= 1;
> > >> +}
> > >> +
> > >> +/* { dg-final { scan-tree-dump-times " >> " 0 optimized } } */
> > >> +/* { dg-final { scan-tree-dump-times " <= " 3 optimized } } */
> > >> --
> > >> 2.43.0
> > >>
> >
  

On 4/9/2026 4:02 PM, Andrew Pinski wrote:
> On Thu, Apr 9, 2026 at 11:50 AM Daniel Henrique Barboza
> <daniel.barboza@oss.qualcomm.com> wrote:
>>
>>
>>
>> On 4/9/2026 3:10 PM, Andrew Pinski wrote:
>>> On Tue, Apr 7, 2026 at 2:20 PM Daniel Henrique Barboza
>>> <daniel.barboza@oss.qualcomm.com> wrote:
>>>>
>>>> From: Daniel Barboza <daniel.barboza@oss.qualcomm.com>
>>>>
>>>> Note that we're not adding its counterpart:
>>>>
>>>> "(A>>bool) != 0 -> (unsigned)A) > bool"
>>>>
>>>> Because it will collide with patterns that handles builtin_clz (e.g.
>>>> clz-complement-int.c tree-ssa test).
>>>>
>>>> Bootstrapped and regression tested in x86.
>>>>
>>>>           PR tree-optimization/119420
>>>>
>>>> gcc/ChangeLog:
>>>>
>>>>           * match.pd(`(A>>bool) EQ 0 -> (unsigned)A) LE bool`): New
>>>>           pattern.
>>>>
>>>> gcc/testsuite/ChangeLog:
>>>>
>>>>           * gcc.dg/tree-ssa/pr119420.c: New test.
>>>> ---
>>>>
>>>> Changes from v1:
>>>> - fixed formatting of (with ...) block;
>>>> - added match.pd comment about the interaction with builtin_clz and why
>>>>     we're not adding the NE variation.
>>>> - v1 link: https://gcc.gnu.org/pipermail/gcc-patches/2026-March/709727.html
>>>>
>>>>    gcc/match.pd                             | 11 +++++++++++
>>>>    gcc/testsuite/gcc.dg/tree-ssa/pr119420.c | 23 +++++++++++++++++++++++
>>>>    2 files changed, 34 insertions(+)
>>>>    create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/pr119420.c
>>>>
>>>> diff --git a/gcc/match.pd b/gcc/match.pd
>>>> index 7f16fd4e081..b7a8ce420b4 100644
>>>> --- a/gcc/match.pd
>>>> +++ b/gcc/match.pd
>>>> @@ -5367,6 +5367,17 @@ DEFINE_INT_AND_FLOAT_ROUND_FN (RINT)
>>>>          @0)))))
>>>>    #endif
>>>>
>>>> +/* PR119420: (A >> bool) == 0 -> (unsigned)a <= (unsigned)bool
>>>> +
>>>> +   We're not adding its NE counterpart:
>>>> +   "(A>>bool) != 0 -> (unsigned)A) > bool"
>>>> +   Because it collides with patterns that handles builtin_clz, as
>>>> +   shown in clz-complement-int.c tree-ssa test.  */
>>>> +(simplify
>>>> + (eq (rshift @0 zero_one_valued_p@1) integer_zerop)
>>>> + (with { tree utype = unsigned_type_for (TREE_TYPE (@0)); }
>>>> +  (le (convert:utype @0) (convert:utype @1))))
>>>
>>> Maybe for the ne case you could add a :s on the rshift for now. I
>>> filed https://gcc.gnu.org/bugzilla/show_bug.cgi?id=124833 for the non
>>> single use case.
>>> That seems like what LLVM does. I think the above also would need the
>>> :s on the rshift for the same reason.
>>
>> That brings me back to a patch that is pending a review/redo:
>>
>> "Re: [PATCH v2] match.pd: simplify lshift const cmp using bit_and [PR124019]"
>>
>> Jeff mentioned that this patch breaks a CRIS test, and adding ":s" would be
>> a solution, and the pattern handled there:
>>
>> "A << CST1 EQ|NE CST2 -> (A & CSTmask) EQ|NE (CST2 >> CST1);"
>>
>> it is also a pattern that happens to collide with the builtin_ctz call with
>> CST1 = 1 (which is not handled in that patch).
>>
>> And the pattern you suggested for PR124808 is also similar to these 2 (by the
>> way your idea improves that loop):
>>
>> (A >> CST1) cmp CST2  ->  A cmp (CST2 << CST1)
>>
>>
>> My point here is that maybe there's an overall design/pattern in all these
>> optimizations with this overall format "A lshift|rshift CST1 cmp CST2" due
>> to how they match these CTZ/CLZ builtins, and maybe we should default to
>> use ":s" in all related patterns.  Does that make sense?
> 
> Yes, I think so. Though in some cases having `:s` there is worse.
> Maybe the issue is forwprop needs to be limiting how it handles
> conditionals for loop exits.
> Currently forwprop calls fold_stmt and not limiting the valueization
> here. But maybe for loop exits we should.
> This would allow us to remove the single_use/`:s` on some more
> patterns (e.g. https://gcc.gnu.org/bugzilla/show_bug.cgi?id=122186).
> Let me think about this some more.

I have some things to add here:

- Jeff detected a regression on this patch with in cris/pr93372-4.c that he
reported by accident in another patch (124019).  That regression is fixed
by adding :s, so we will end up fixing that by trying to not trip these CTZ/CLZ
patterns;

- that cris related code got me thinking: regardless of how we're dealing with
CTZ/CLZ shouldn't we always treat these CMP canonicalizations as single_use?
Consider this code:

--------
cris/pr93372-4.c

int f(int a, int *b)
{
   /* As seen in powisf2, the result of a shift is checked for zeroness. */
   int c = a >> 1;
   *b = (c == 0);
   return c;
}
--------

With this patch applied the 'optimized' dump we have is:


;;   basic block 2
   # RANGE [irange] int [-1073741824, 1073741823]
   c_4 = a_3(D) >> 1;
   _8 = (unsigned int) a_3(D);
   _1 = _8 <= 1;
   # RANGE [irange] int [0, 1] MASK 0x1 VALUE 0x0
   _2 = (intD.7) _1;
   # .MEM_7 = VDEF <.MEM_5(D)>
   *b_6(D) = _2;
   # VUSE <.MEM_7>
   return c_4;


The right shift is being used as return so we can't get rid of it. Therefore
seems to me that there's no way around not using ':s' in the rshift - if
we need the rshift result for other purposes outside of the CMP, might as
well not touch the CMP at all.  Is this a fair statement?


- following what we've done in

[PATCH v3] match.pd: right shift compare canonicalization [PR124808]

We put that code inside an "if GIMPLE" block and used "single_use" directly.
Shouldn't we do the same here?  At very least we would be consistent in how
we're implementing these optimizations with xshift and CMPs.


Thanks,
Daniel


> 
> Thanks,
> Andrew
> 
> 
>>
>>
>> Daniel
>>
>>>
>>>
>>> Thanks,
>>> Andrew Pinski
>>>
>>>> +
>>>>    /* Rewrite an LROTATE_EXPR by a constant into an
>>>>       RROTATE_EXPR by a new constant.  */
>>>>    (simplify
>>>> diff --git a/gcc/testsuite/gcc.dg/tree-ssa/pr119420.c b/gcc/testsuite/gcc.dg/tree-ssa/pr119420.c
>>>> new file mode 100644
>>>> index 00000000000..3169650fe66
>>>> --- /dev/null
>>>> +++ b/gcc/testsuite/gcc.dg/tree-ssa/pr119420.c
>>>> @@ -0,0 +1,23 @@
>>>> +/* { dg-additional-options -O2 } */
>>>> +/* { dg-additional-options -fdump-tree-optimized } */
>>>> +
>>>> +int ll (signed a)
>>>> +{
>>>> +  int d = a >> 1;
>>>> +  return d == 0;
>>>> +}
>>>> +
>>>> +int ll1 (signed a)
>>>> +{
>>>> +  int d = a & ~1;
>>>> +  return d == 0;
>>>> +}
>>>> +
>>>> +int ll2 (signed a)
>>>> +{
>>>> +  unsigned aa = a;
>>>> +  return aa <= 1;
>>>> +}
>>>> +
>>>> +/* { dg-final { scan-tree-dump-times " >> " 0 optimized } } */
>>>> +/* { dg-final { scan-tree-dump-times " <= " 3 optimized } } */
>>>> --
>>>> 2.43.0
>>>>
>>
  

Quick follow-up on my last reply:

On 4/16/2026 5:11 PM, Daniel Henrique Barboza wrote:
> 
> 
> On 4/9/2026 4:02 PM, Andrew Pinski wrote:
>> On Thu, Apr 9, 2026 at 11:50 AM Daniel Henrique Barboza
>> <daniel.barboza@oss.qualcomm.com> wrote:
>>>
>>>
>>>
>>> On 4/9/2026 3:10 PM, Andrew Pinski wrote:
>>>> On Tue, Apr 7, 2026 at 2:20 PM Daniel Henrique Barboza
>>>> <daniel.barboza@oss.qualcomm.com> wrote:
>>>>>
>>>>> From: Daniel Barboza <daniel.barboza@oss.qualcomm.com>
>>>>>
>>>>> Note that we're not adding its counterpart:
>>>>>
>>>>> "(A>>bool) != 0 -> (unsigned)A) > bool"
>>>>>
>>>>> Because it will collide with patterns that handles builtin_clz (e.g.
>>>>> clz-complement-int.c tree-ssa test).


I added the NE variant back, and then dealt with clz-complement-int.c test ...


>>>>>
>>>>> Bootstrapped and regression tested in x86.
>>>>>
>>>>>           PR tree-optimization/119420

[...]

>>>>>
> 
> - following what we've done in
> 
> [PATCH v3] match.pd: right shift compare canonicalization [PR124808]
> 
> We put that code inside an "if GIMPLE" block and used "single_use" directly.
> Shouldn't we do the same here?  At very least we would be consistent in how
> we're implementing these optimizations with xshift and CMPs.


By doing the same thing we did in 124808, i.e. (1) wrap in #if GIMPLE and (2)
use single_use() in the rshift.  Using just ":s" won't work.

I suppose the explanation gave in 124808 reviews is valid here too, so

- w.r.t why we need "if GIMPLE":

---
The way forwardprop handles comparisons is a problem in general and
that might be the issue here. IIRC for comparisons forwprop tries to
build up a generic tree and then fold that.

So maybe the workaround here is to enable this pattern for GIMPLE only.
The other workaround is to use single_use directly instead of `:s`.


- w.r.t why we need "single_use" directly instead of ":s":

-----

  Oh yes because of the way `:s` works (I had to read genmatch to
remember how this thing works). It is trying to prevent doing 2->2 or
3->2 "combings"/simplifications.
But since here we are creating a simplified expression and not pushing
to the sequence, `:s` will not reject it so
you need the explicit single_use check.
---


I'll run the usual regression tests and send a v3.  I'll make sure to
check the 'cris-elf' target to ensure we don't trip on that same test
again.  And we can have the "NE" variant too, which is nice.


Thanks,
Daniel