On Thu, 27 Nov 2025, Jakub Jelinek wrote:
> 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:
LGTM
> 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
>
>
--
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)
