On Thu, 27 Nov 2025, Jakub Jelinek wrote:
> On Fri, Nov 21, 2025 at 11:29:38AM +0100, Jakub Jelinek wrote:
> > On Thu, Nov 20, 2025 at 09:33:50AM +0530, Dhruv Chawla wrote:
> > > Thanks, I have attached the updated patch.
> >
> > > PR tree-optimization/122733
> > >
> > > gcc/ChangeLog:
> > >
> > > * match.pd ((y << x) {<,<=,>,>=} x): Remove.
> > > ((y << x) {==,!=} x): Call constant_boolean_node instead of
> > > build_one_cst/build_zero_cst and combine into one pattern.
> > >
> > > gcc/testsuite/ChangeLog:
> > >
> > > * gcc.dg/match-shift-cmp-1.c: Update test to only check
> > > equality.
> > > * gcc.dg/match-shift-cmp-2.c: Likewise.
> > > * gcc.dg/match-shift-cmp-3.c: Likewise.
> > > * gcc.dg/match-shift-cmp-4.c: Removed.
> >
> > LGTM.
>
> I've committed your patch now.
>
> On top of that, here is my attempt to implement it using ranger.
> Note also the changes to the equality pattern, first of all, there
> could be e.g. vector << scalar shifts, although they'll likely
> fail on the nop_convert vs. nop_convert, but also it would never
> match for say unsigned long long @0 and unsigned int @1 etc., pretty
> common cases.
>
> The new simplifier asks the ranger about ranges and bitmasks, verifies
> @0 is non-zero and that clz of the @0 nonzero bits bitmask (i.e. the minimum
> clz of all possible values of @0) is greater than (or greater than or equal
> to) maximum shift count. Which one of those depends on if the actual
> non-equality comparison is signed or unsigned.
>
> 2025-11-27 Jakub Jelinek <[email protected]>
>
> PR tree-optimization/122733
> * match.pd ((y << x) == x, (y << x) != x): Use convert2?
> instead of nop_convert2? and test INTEGRAL_TYPE_P on TREE_TYPE (@0)
> rather than TREE_TYPE (@1).
> ((y << x) {<,<=,>,>=} x): New simplification.
>
> * gcc.dg/match-shift-cmp-4.c: New test.
> * gcc.dg/match-shift-cmp-5.c: New test.
>
> --- gcc/match.pd.jj 2025-11-27 12:08:34.887423204 +0100
> +++ gcc/match.pd 2025-11-27 13:06:35.494902478 +0100
> @@ -1343,11 +1343,39 @@ (define_operator_list SYNC_FETCH_AND_AND
> /* (y << x) == x -> false and (y << x) != x -> true when y != 0. */
> (for cmp (eq ne)
> (simplify
> - (cmp:c (nop_convert1? (lshift @0 @1)) (nop_convert2? @1))
> - (if (INTEGRAL_TYPE_P (TREE_TYPE (@1))
> + (cmp:c (nop_convert1? (lshift @0 @1)) (convert2? @1))
> + (if (INTEGRAL_TYPE_P (TREE_TYPE (@0))
> && tree_expr_nonzero_p (@0))
> { constant_boolean_node (cmp != EQ_EXPR, type); })))
>
> +#if GIMPLE
> +/* (y << x) {<,<=} x -> false and (y << x) {>,>=} x -> true when y != 0
> + and (y << x) >> x == y and for signed comparison (y << x) >= 0. */
> +(for cmp (gt ge lt le)
> + (simplify
> + (cmp:c (nop_convert1?@3 (lshift@2 @0 @1)) (convert2? @1))
> + (if (INTEGRAL_TYPE_P (TREE_TYPE (@0)))
> + (with { bool ok = false;
> + int_range_max vr0, vr1;
> + if (gimple_match_range_of_expr (vr0, @0, @2)
> + && !vr0.varying_p ()
> + && !vr0.undefined_p ()
I guess the varying and undefined checks could be put into
gimple_match_range_of_expr as well?
Otherwise looks good.
> + && gimple_match_range_of_expr (vr1, @1, @2)
> + && !vr1.varying_p ()
> + && !vr1.undefined_p ()
> + && !vr0.contains_p (wi::zero (TYPE_PRECISION (TREE_TYPE (@0)))))
> + {
> + unsigned lz = wi::clz (vr0.get_nonzero_bits ());
> + if (!wi::neg_p (vr1.upper_bound (), TYPE_SIGN (TREE_TYPE (@1)))
> + && wi::ltu_p (vr1.upper_bound (),
> + wi::uhwi (lz + TYPE_UNSIGNED (TREE_TYPE (@3)),
> + TYPE_PRECISION (TREE_TYPE (@1)))))
> + ok = true;
> + } }
> + (if (ok)
> + { constant_boolean_node (cmp == GT_EXPR || cmp == GE_EXPR, type); })))))
> +#endif
> +
> /* Fold (1 << (C - x)) where C = precision(type) - 1
> into ((1 << C) >> x). */
> (simplify
> --- gcc/testsuite/gcc.dg/match-shift-cmp-4.c.jj 2025-11-27
> 13:28:04.848516222 +0100
> +++ gcc/testsuite/gcc.dg/match-shift-cmp-4.c 2025-11-27 13:29:37.676904590
> +0100
> @@ -0,0 +1,47 @@
> +/* { dg-do compile } */
> +/* { dg-options "-O2 -fdump-tree-optimized" } */
> +/* { dg-final { scan-tree-dump-times "return 0;" 4 "optimized" { target
> bitint575 } } } */
> +/* { dg-final { scan-tree-dump-times "return 0;" 2 "optimized" { target { !
> bitint575 } } } } */
> +/* { dg-final { scan-tree-dump-not " << " "optimized" } } */
> +
> +bool
> +foo (unsigned long long x, unsigned y)
> +{
> + if (x >= 64 || x == 0)
> + __builtin_unreachable ();
> + if (y > sizeof (unsigned long long) * __CHAR_BIT__ - 6)
> + __builtin_unreachable ();
> + return (x << y) <= y;
> +}
> +
> +#if __BITINT_MAXWIDTH__ >= 575
> +bool
> +bar (unsigned _BitInt(575) x, unsigned y)
> +{
> + if (x >= 1361129467683753853853498429727072845823uwb || x == 0)
> + __builtin_unreachable ();
> + if (y > 575 - 130)
> + __builtin_unreachable ();
> + return (x << y) < y;
> +}
> +
> +bool
> +baz (unsigned _BitInt(575) x, unsigned y)
> +{
> + if (x >= 1361129467683753853853498429727072845823uwb || x == 0)
> + __builtin_unreachable ();
> + if (y >= 575 - 130)
> + __builtin_unreachable ();
> + return ((signed _BitInt(575)) (x << y)) < y;
> +}
> +#endif
> +
> +bool
> +qux (int x, int y)
> +{
> + if (x >= 128 || x <= 0)
> + __builtin_unreachable ();
> + if (y >= sizeof (int) * __CHAR_BIT__ - 7)
> + __builtin_unreachable ();
> + return (x << y) <= y;
> +}
> --- gcc/testsuite/gcc.dg/match-shift-cmp-5.c.jj 2025-11-27
> 13:28:13.585364537 +0100
> +++ gcc/testsuite/gcc.dg/match-shift-cmp-5.c 2025-11-27 13:34:15.448082029
> +0100
> @@ -0,0 +1,47 @@
> +/* { dg-do compile } */
> +/* { dg-options "-O2 -fdump-tree-optimized" } */
> +/* { dg-final { scan-tree-dump-times "return 1;" 4 "optimized" { target
> bitint575 } } } */
> +/* { dg-final { scan-tree-dump-times "return 1;" 2 "optimized" { target { !
> bitint575 } } } } */
> +/* { dg-final { scan-tree-dump-not " << " "optimized" } } */
> +
> +bool
> +foo (unsigned long long x, unsigned y)
> +{
> + if (x >= 64 || x == 0)
> + __builtin_unreachable ();
> + if (y > sizeof (unsigned long long) * __CHAR_BIT__ - 6)
> + __builtin_unreachable ();
> + return (x << y) >= y;
> +}
> +
> +#if __BITINT_MAXWIDTH__ >= 575
> +bool
> +bar (unsigned _BitInt(575) x, unsigned y)
> +{
> + if (x >= 1361129467683753853853498429727072845823uwb || x == 0)
> + __builtin_unreachable ();
> + if (y > 575 - 130)
> + __builtin_unreachable ();
> + return (x << y) > y;
> +}
> +
> +bool
> +baz (unsigned _BitInt(575) x, unsigned y)
> +{
> + if (x >= 1361129467683753853853498429727072845823uwb || x == 0)
> + __builtin_unreachable ();
> + if (y >= 575 - 130)
> + __builtin_unreachable ();
> + return ((signed _BitInt(575)) (x << y)) > y;
> +}
> +#endif
> +
> +bool
> +qux (int x, int y)
> +{
> + if (x >= 128 || x <= 0)
> + __builtin_unreachable ();
> + if (y >= sizeof (int) * __CHAR_BIT__ - 7)
> + __builtin_unreachable ();
> + return (x << y) >= y;
> +}
>
>
> Jakub
>
>
--
Richard Biener <[email protected]>
SUSE Software Solutions Germany GmbH,
Frankenstrasse 146, 90461 Nuernberg, Germany;
GF: Jochen Jaser, Andrew McDonald, Werner Knoblich; (HRB 36809, AG Nuernberg)
