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 ()
+ && 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
