On Thu, Nov 27, 2025 at 02:44:56PM +0100, Jakub Jelinek wrote:
> On Thu, Nov 27, 2025 at 02:32:42PM +0100, Richard Biener wrote:
> > > +#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?
>
> Agreed about the undefined_p stuff, for varying_p I'd defer to the callers,
> sometimes they are ok even with VARYING, depends on what exactly they use it
> for. Checking !vrN.varying_p () here isn't really necessary, just that
> if it is varying, testing the rest is a waste of compile time, it will
> vr0 surely contain zero in that case and lz will be 0, and for the shift
> count it will not be smaller than lz + uns.
Now in patch form:
2025-11-27 Jakub Jelinek <[email protected]>
PR tree-optimization/122733
* gimple-match-head.cc (gimple_match_range_of_expr): Return false
even when range_of_expr returns true, but the range is undefined_p.
* match.pd ((mult (plus:s@5 (mult:s@4 @0 @1) @2) @3)): Remove
vr0.undefined_p () check.
((plus (mult:s@5 (plus:s@4 @0 @1) @2) @3)): Likewise.
((X + M*N) / N -> X / N + M): Remove vr4.undefined_p () check.
((X - M*N) / N -> X / N - M): Likewise.
((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.
(((T)(A)) + CST -> (T)(A + CST)): Remove vr.undefined_p () check.
(x_5 == cstN ? cst4 : cst3): Remove r.undefined_p () check.
* gcc.dg/match-shift-cmp-4.c: New test.
* gcc.dg/match-shift-cmp-5.c: New test.
--- gcc/gimple-match-head.cc.jj 2025-11-27 11:59:26.739943819 +0100
+++ gcc/gimple-match-head.cc 2025-11-27 15:10:36.979762117 +0100
@@ -529,7 +529,9 @@ gimple_match_ctx (tree op)
static inline bool
gimple_match_range_of_expr (vrange &r, tree op, tree ctx = NULL_TREE)
{
- return get_range_query (cfun)->range_of_expr (r, op,
- ctx ? gimple_match_ctx (ctx)
- : NULL);
+ if (!get_range_query (cfun)->range_of_expr (r, op,
+ ctx ? gimple_match_ctx (ctx)
+ : NULL))
+ return false;
+ return !r.undefined_p ();
}
--- gcc/match.pd.jj 2025-11-27 13:51:55.586675608 +0100
+++ gcc/match.pd 2025-11-27 15:09:52.747530952 +0100
@@ -662,7 +662,7 @@ (define_operator_list SYNC_FETCH_AND_AND
int_range_max vr0;
if (ovf1 == wi::OVF_NONE && ovf2 == wi::OVF_NONE
&& gimple_match_range_of_expr (vr0, @4, @5)
- && !vr0.varying_p () && !vr0.undefined_p ())
+ && !vr0.varying_p ())
{
wide_int wmin0 = vr0.lower_bound ();
wide_int wmax0 = vr0.upper_bound ();
@@ -703,7 +703,7 @@ (define_operator_list SYNC_FETCH_AND_AND
int_range_max vr0;
if (ovf1 == wi::OVF_NONE && ovf2 == wi::OVF_NONE
&& gimple_match_range_of_expr (vr0, @0, @4)
- && !vr0.varying_p () && !vr0.undefined_p ())
+ && !vr0.varying_p ())
{
wide_int wmin0 = vr0.lower_bound ();
wide_int wmax0 = vr0.upper_bound ();
@@ -1079,7 +1079,6 @@ (define_operator_list SYNC_FETCH_AND_AND
/* "X+(N*M)" doesn't overflow. */
&& range_op_handler (PLUS_EXPR).overflow_free_p (vr0, vr3)
&& gimple_match_range_of_expr (vr4, @4)
- && !vr4.undefined_p ()
/* "X+N*M" is not with opposite sign as "X". */
&& (TYPE_UNSIGNED (type)
|| (vr0.nonnegative_p () && vr4.nonnegative_p ())
@@ -1100,7 +1099,6 @@ (define_operator_list SYNC_FETCH_AND_AND
/* "X - (N*M)" doesn't overflow. */
&& range_op_handler (MINUS_EXPR).overflow_free_p (vr0, vr3)
&& gimple_match_range_of_expr (vr4, @4)
- && !vr4.undefined_p ()
/* "X-N*M" is not with opposite sign as "X". */
&& (TYPE_UNSIGNED (type)
|| (vr0.nonnegative_p () && vr4.nonnegative_p ())
@@ -1343,11 +1341,37 @@ (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 ()
+ && gimple_match_range_of_expr (vr1, @1, @2)
+ && !vr1.varying_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
@@ -4446,8 +4470,7 @@ (define_operator_list SYNC_FETCH_AND_AND
TYPE_SIGN (inner_type));
int_range_max vr;
- if (gimple_match_range_of_expr (vr, @0, @2)
- && !vr.varying_p () && !vr.undefined_p ())
+ if (gimple_match_range_of_expr (vr, @0, @2) && !vr.varying_p ())
{
wide_int wmin0 = vr.lower_bound ();
wide_int wmax0 = vr.upper_bound ();
@@ -6531,8 +6554,7 @@ (define_operator_list SYNC_FETCH_AND_AND
|| wi::to_widest (@2) == wi::to_widest (@3) + 1))
(with {
int_range_max r;
- if (!gimple_match_range_of_expr (r, @0, @4)
- || r.undefined_p ())
+ if (!gimple_match_range_of_expr (r, @0, @4))
r.set_varying (TREE_TYPE (@0));
wide_int min = r.lower_bound ();
--- gcc/testsuite/gcc.dg/match-shift-cmp-4.c.jj 2025-11-27 15:07:01.640022895
+0100
+++ gcc/testsuite/gcc.dg/match-shift-cmp-4.c 2025-11-27 15:07:01.640022895
+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 15:07:01.640112754
+0100
+++ gcc/testsuite/gcc.dg/match-shift-cmp-5.c 2025-11-27 15:07:01.640112754
+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
