https://gcc.gnu.org/g:875a6c6192a68f75ad213f2a1b3804e7724073e7
commit r17-2307-g875a6c6192a68f75ad213f2a1b3804e7724073e7 Author: Daniel Barboza <[email protected]> Date: Thu Apr 9 08:40:11 2026 -0300 match.pd: right shift compare canonicalization [PR124808] Canonicalize right shift non-equality comparisons with constants by turn them into a comparison with a left shifted constant. Assuming the generic format: (A >> CST1) CMP CST2 For CMP (<, >=) we'll compare A with CST2 left shifted by CST1: - (A >> CST1) < CST2 -> A < (CST2 << CST1) - (A >> CST1) >= CST2 -> A >= (CST2 << CST1) And for CMP (<=, >) we need to IOR the lower CST1 bits from the left shift: - (A >> CST1) <= CST2 -> A <= (CST2 << CST1) | mask - (A >> CST1) > CST2 -> A > (CST2 << CST1) | mask Given that the right hand side changes involves just constants, in the end we'll replace a rshift + cmp with just a cmp. Bootstrapped and regression tested in x86, aarch64 and RISC-V. PR tree-optimization/124808 gcc/ChangeLog: * match.pd(`(A >> CST1) CMP CST2`): New pattern. gcc/testsuite/ChangeLog: * gcc.dg/tree-ssa/pr124808-2.c: New test. * gcc.dg/tree-ssa/pr124808.c: New test. Diff: --- gcc/match.pd | 62 ++++++++++++++++++++++++ gcc/testsuite/gcc.dg/tree-ssa/pr124808-2.c | 44 +++++++++++++++++ gcc/testsuite/gcc.dg/tree-ssa/pr124808.c | 78 ++++++++++++++++++++++++++++++ 3 files changed, 184 insertions(+) diff --git a/gcc/match.pd b/gcc/match.pd index cf03333fdc6b..39328818f0e7 100644 --- a/gcc/match.pd +++ b/gcc/match.pd @@ -5118,6 +5118,68 @@ DEFINE_INT_AND_FLOAT_ROUND_FN (RINT) && TYPE_UNSIGNED (TREE_TYPE (@1))) (cmp @0 @1)))) +/* PR124808: (A >> CST1) CMP CST2 -> A CMP (CST2 << CST1) + Canonicalize non-equality comparisons between a right + shift and a constant, turning it into a comparison + with a constant that is left shifted. If we view A as: + + A: "|--- CST2 ----|--CST1--|" + + A >> CST1 will be equal to CST2 for all A values in the + range CST2 << CST1 to (CST2 << CST1) | 1s_mask (CST1). + + Therefore: + - (A >> CST1) < CST2 -> A < (CST2 << CST1), A must + be smaller than all values from the range; + - (A >> CST1) <= CST2 -> A <= (CST2 << CST1) | mask, + A must be smaller or equal than the range end; + - (A >> CST1) > CST2 -> A > (CST2 << CST1) | mask, + A must be greater than all values from the range; + - (A >> CST1) >= CST2 -> A >= (CST2 << CST1), A must + be greater or equal than the range start. + + We're also using "single_use" and wrapping around "if GIMPLE" + because (1) this class "VA1 LSHIFT/RSHIFT VAL2 CMP VAL3" of + optimizations tend to match CTZ|CLZ builtin patterns and we + don't want to trip on them and (2) we will get in the way of + certain optimizations (see ARM's sat-1.c test) that are done + using GENERIC due to how forwprop currently works. */ +#if GIMPLE +(for cmp (le lt ge gt) + (simplify + (cmp (rshift@3 @0 INTEGER_CST@1) INTEGER_CST@2) + (if (INTEGRAL_TYPE_P (TREE_TYPE (@0)) + && single_use (@3) + && tree_fits_uhwi_p (@1) + && tree_to_uhwi (@1) < TYPE_PRECISION (TREE_TYPE (@0)) + && tree_int_cst_sgn (@2) >= 0 + && tree_to_uhwi (@1) < TYPE_PRECISION (TREE_TYPE (@2)) + && (wi::to_wide (@2) == 0 + /* If @2 is nonzero, verify if we'll overflow when + doing @2 << @1 by checking if the shift amount + can start throwing 1s away if type_unsigned, or + if the shift amount can reach the sign bit. */ + || (TYPE_UNSIGNED (TREE_TYPE (@2)) + && wi::leu_p (wi::to_wide (@1), wi::clz (wi::to_wide (@2)))) + || (!TYPE_UNSIGNED (TREE_TYPE (@2)) + && wi::ltu_p (wi::to_wide (@1), wi::clz (wi::to_wide (@2)))))) + + /* No need to set the lower @1 bits of the resulting + lshift for "<" and ">=" comparisons. */ + (if (cmp == LT_EXPR || cmp == GE_EXPR) + (cmp @0 (lshift @2 @1)) + + /* For "<=" and ">" set the lower @1 lshift bits. */ + (with { + tree type2 = TREE_TYPE (@2); + unsigned prec = TYPE_PRECISION (type2); + unsigned mask_len = tree_to_uhwi (@1); + wide_int cst1_mask = wi::mask (mask_len, false, prec); + } + (cmp @0 (bit_ior (lshift @2 @1) + { wide_int_to_tree (type2, cst1_mask); }))))))) +#endif + /* Rewrite an LROTATE_EXPR by a constant into an RROTATE_EXPR by a new constant. */ (simplify diff --git a/gcc/testsuite/gcc.dg/tree-ssa/pr124808-2.c b/gcc/testsuite/gcc.dg/tree-ssa/pr124808-2.c new file mode 100644 index 000000000000..bfab8109ce6e --- /dev/null +++ b/gcc/testsuite/gcc.dg/tree-ssa/pr124808-2.c @@ -0,0 +1,44 @@ +/* { dg-additional-options -O2 } */ +/* { dg-additional-options -fdump-tree-forwprop1 } */ + +long* SetupPrecalculatedData1 (long* a) { + long b = 1; + int i; + for (i = 0; i < 64; i++) { + if(i>>3 < 7) + a[i] += (b<<(i+8)); + } + return a; +} + +long* SetupPrecalculatedData2 (long* a) { + long b = 1; + int i; + for (i = 0; i <= 64; i++) { + if(i>>3 < 7) + a[i] += (b<<(i+8)); + } + return a; +} + +long* SetupPrecalculatedData3 (long* a) { + long b = 1; + int i; + for (i = 0; i < 64; i++) { + if(i>>3 > 7) + a[i] += (b<<(i+8)); + } + return a; +} + +long* SetupPrecalculatedData4 (long* a) { + long b = 1; + int i; + for (i = 0; i < 64; i++) { + if(i>>3 >= 7) + a[i] += (b<<(i+8)); + } + return a; +} + +/* { dg-final { scan-tree-dump-times ">> 3" 0 forwprop1 } } */ diff --git a/gcc/testsuite/gcc.dg/tree-ssa/pr124808.c b/gcc/testsuite/gcc.dg/tree-ssa/pr124808.c new file mode 100644 index 000000000000..5f3c1f0a8c41 --- /dev/null +++ b/gcc/testsuite/gcc.dg/tree-ssa/pr124808.c @@ -0,0 +1,78 @@ +/* { dg-do run } */ +/* { dg-options "-O2" } */ + +void abort(void); + +/* Macro adapted from builtin-object-size-common.h */ +#define FAIL() \ + do { \ + __builtin_printf ("Failure at line: %d\n", __LINE__); \ + abort(); \ + } while (0) + +#define SHIFTVAL 3 +#define CMPVAL 1 + +long setValue1 (long in) +{ + if (in >> SHIFTVAL < CMPVAL) + return in += SHIFTVAL; + return -1; +} + +long setValue2 (long in) +{ + if (in >> SHIFTVAL <= CMPVAL) + return in += SHIFTVAL; + return -1; +} + +long setValue3 (long in) +{ + if (in >> SHIFTVAL > CMPVAL) + return in += SHIFTVAL; + return -1; +} + +long setValue4 (long in) +{ + if (in >> SHIFTVAL >= CMPVAL) + return in += SHIFTVAL; + return -1; +} + +int main (void) { + /* setValue1: in << 3 < 1; */ + if (setValue1 (7) != 10) + FAIL (); + if (setValue1 (8) != -1) + FAIL (); + + /* setValue2: in << 3 <= 1; */ + if (setValue2 (7) != 10) + FAIL (); + if (setValue2 (8) != 11) + FAIL (); + if (setValue2 (15) != 18) + FAIL (); + if (setValue2 (16) != -1) + FAIL (); + + /* setValue3: in << 3 > 1; */ + if (setValue3 (15) != -1) + FAIL (); + if (setValue3 (16) != 19) + FAIL (); + + /* setValue4: in << 3 >= 1; */ + if (setValue4 (7) != -1) + FAIL (); + if (setValue4 (8) != 11) + FAIL (); + if (setValue4 (15) != 18) + FAIL (); + if (setValue4 (16) != 19) + FAIL (); + + return 0; +}
