https://gcc.gnu.org/g:9785d99e281d829b1b97110859ee3b73dffa3b51
commit r16-5684-g9785d99e281d829b1b97110859ee3b73dffa3b51 Author: Jakub Jelinek <[email protected]> Date: Fri Nov 28 10:04:53 2025 +0100 match.pd: Re-add (y << x) {<,<=,>,>=} x simplifications [PR122733] Here is my attempt to implement what has been reverted in r16-5648 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. And gimple_match_range_of_expr now includes in itself undefined_p check and returns false even for that, so that many of the callers don't need to check that. 2025-11-28 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. Diff: --- gcc/gimple-match-head.cc | 8 ++++-- gcc/match.pd | 42 +++++++++++++++++++++------- gcc/testsuite/gcc.dg/match-shift-cmp-4.c | 47 ++++++++++++++++++++++++++++++++ gcc/testsuite/gcc.dg/match-shift-cmp-5.c | 47 ++++++++++++++++++++++++++++++++ 4 files changed, 131 insertions(+), 13 deletions(-) diff --git a/gcc/gimple-match-head.cc b/gcc/gimple-match-head.cc index f8d0acf81462..895d390455d3 100644 --- a/gcc/gimple-match-head.cc +++ b/gcc/gimple-match-head.cc @@ -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 (); } diff --git a/gcc/match.pd b/gcc/match.pd index 4ebf394d4a4a..f164ec591008 100644 --- a/gcc/match.pd +++ b/gcc/match.pd @@ -662,7 +662,7 @@ DEFINE_INT_AND_FLOAT_ROUND_FN (RINT) 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_INT_AND_FLOAT_ROUND_FN (RINT) 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_INT_AND_FLOAT_ROUND_FN (RINT) /* "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_INT_AND_FLOAT_ROUND_FN (RINT) /* "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_INT_AND_FLOAT_ROUND_FN (RINT) /* (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_INT_AND_FLOAT_ROUND_FN (RINT) 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_INT_AND_FLOAT_ROUND_FN (RINT) || 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 (); diff --git a/gcc/testsuite/gcc.dg/match-shift-cmp-4.c b/gcc/testsuite/gcc.dg/match-shift-cmp-4.c new file mode 100644 index 000000000000..c2458d995156 --- /dev/null +++ b/gcc/testsuite/gcc.dg/match-shift-cmp-4.c @@ -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; +} diff --git a/gcc/testsuite/gcc.dg/match-shift-cmp-5.c b/gcc/testsuite/gcc.dg/match-shift-cmp-5.c new file mode 100644 index 000000000000..7768f5911501 --- /dev/null +++ b/gcc/testsuite/gcc.dg/match-shift-cmp-5.c @@ -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; +}
