https://gcc.gnu.org/g:c4ca512358be7cb1c8523f148fa84a57cbbf0060
commit r16-5161-gc4ca512358be7cb1c8523f148fa84a57cbbf0060 Author: Dhruv Chawla <[email protected]> Date: Thu Aug 21 02:06:07 2025 -0700 match.pd: Fold (y << x) <rel op> x -> 0 or 1 - (y << x) == x -> 0 when y != 0 - (y << x) {<,<=} x -> 0 when y > 0. - (y << x) != x -> 1 when y != 0. - (y << x) {>,>=} x -> 1 when y > 0. Bootstrapped and regtested on aarch64-linux-gnu. Signed-off-by: Dhruv Chawla <[email protected]> gcc/ChangeLog: * match.pd: New patterns. gcc/testsuite/ChangeLog: * gcc.dg/match-shift-cmp-1.c: New test. * gcc.dg/match-shift-cmp-2.c: Likewise. * gcc.dg/match-shift-cmp-3.c: Likewise. * gcc.dg/match-shift-cmp-4.c: Likewise. Diff: --- gcc/match.pd | 32 +++++++++++++++++ gcc/testsuite/gcc.dg/match-shift-cmp-1.c | 50 ++++++++++++++++++++++++++ gcc/testsuite/gcc.dg/match-shift-cmp-2.c | 62 ++++++++++++++++++++++++++++++++ gcc/testsuite/gcc.dg/match-shift-cmp-3.c | 44 +++++++++++++++++++++++ gcc/testsuite/gcc.dg/match-shift-cmp-4.c | 51 ++++++++++++++++++++++++++ 5 files changed, 239 insertions(+) diff --git a/gcc/match.pd b/gcc/match.pd index 3cd9ab1e9b04..63d56b081925 100644 --- a/gcc/match.pd +++ b/gcc/match.pd @@ -1339,6 +1339,38 @@ DEFINE_INT_AND_FLOAT_ROUND_FN (RINT) (if (INTEGRAL_TYPE_P (type)) (rshift (op @0 @2) @1)))) +/* (y << x) == x -> 0 when y != 0. */ +(simplify + (eq:c (nop_convert1? (lshift @0 @1)) (nop_convert2? @1)) + (if (INTEGRAL_TYPE_P (TREE_TYPE (@1)) + && tree_expr_nonzero_p (@0)) + { build_zero_cst (type); })) + +/* (y << x) {<,<=} x -> 0 when y > 0. */ +(for cmp (lt le) + (simplify + (cmp:c (nop_convert1? (lshift @0 @1)) (nop_convert2? @1)) + (if (INTEGRAL_TYPE_P (TREE_TYPE (@1)) + && tree_expr_nonzero_p (@0) + && tree_expr_nonnegative_p (@0)) + { build_zero_cst (type); }))) + +/* (y << x) != x -> 1 when y != 0. */ +(simplify + (ne:c (nop_convert1? (lshift @0 @1)) (nop_convert2? @1)) + (if (INTEGRAL_TYPE_P (TREE_TYPE (@1)) + && tree_expr_nonzero_p (@0)) + { build_one_cst (type); })) + +/* (y << x) {>,>=} x -> 1 when y > 0. */ +(for cmp (gt ge) + (simplify + (cmp:c (nop_convert1? (lshift @0 @1)) (nop_convert2? @1)) + (if (INTEGRAL_TYPE_P (TREE_TYPE (@1)) + && tree_expr_nonzero_p (@0) + && tree_expr_nonnegative_p (@0)) + { build_one_cst (type); }))) + /* Fold (1 << (C - x)) where C = precision(type) - 1 into ((1 << C) >> x). */ (simplify diff --git a/gcc/testsuite/gcc.dg/match-shift-cmp-1.c b/gcc/testsuite/gcc.dg/match-shift-cmp-1.c new file mode 100644 index 000000000000..b22d57d370f1 --- /dev/null +++ b/gcc/testsuite/gcc.dg/match-shift-cmp-1.c @@ -0,0 +1,50 @@ +/* { dg-do compile } */ +/* { dg-options "-O2 -fdump-tree-optimized" } */ + +#define TEST_ONE_CST(n, op, type, cst) \ + bool lshift_cst_##type##_##n (type x) { return (cst << x) op x; } + +#define TEST_OP_CST(n, op, cst) \ + TEST_ONE_CST (n, op, unsigned, cst) \ + TEST_ONE_CST (n, op, int, cst) \ + TEST_ONE_CST (n, op, bool, cst) \ + TEST_ONE_CST (n, op, test_enum, cst) + +#define TEST_ONE(n, op, type) \ + bool lshift_##type##_##n (type x, type y) \ + { \ + if (y <= 0) \ + __builtin_unreachable (); \ + return (y << x) op x; \ + } + +#define TEST_OP(n, op) \ + TEST_ONE (n, op, unsigned) \ + TEST_ONE (n, op, int) \ + TEST_ONE (n, op, bool) \ + TEST_ONE (n, op, test_enum) + +typedef enum +{ + MONE = -1, + ZERO = 0, + ONE = 1, + TWO = 2 +} test_enum; + +TEST_OP_CST (eq, ==, 1) +TEST_OP_CST (ne, !=, 2) +TEST_OP_CST (lt, <, 3) +TEST_OP_CST (gt, >, 4) +TEST_OP_CST (le, <=, 5) +TEST_OP_CST (ge, >=, 6) + +TEST_OP (eq, ==) +TEST_OP (ne, !=) +TEST_OP (lt, <) +TEST_OP (gt, >) +TEST_OP (le, <=) +TEST_OP (ge, >=) + +/* FIXME: The lt, le, gt and ge cases for int and enum don't get optimized. */ +/* { dg-final { scan-tree-dump-times "<<" 8 optimized } } */ diff --git a/gcc/testsuite/gcc.dg/match-shift-cmp-2.c b/gcc/testsuite/gcc.dg/match-shift-cmp-2.c new file mode 100644 index 000000000000..96a2fd954f63 --- /dev/null +++ b/gcc/testsuite/gcc.dg/match-shift-cmp-2.c @@ -0,0 +1,62 @@ +/* { dg-do compile } */ +/* { dg-options "-O2 -fdump-tree-optimized" } */ + +/* The fold (y << x) <op> x -> 0|1 shouldn't trigger when y is 0. */ + +#define TEST_ONE_CST(n, op, type, cst) \ + bool lshift_cst_##type##_##n (type x) { return (cst << x) op x; } + +#define TEST_OP_CST(n, op, cst) \ + TEST_ONE_CST (n, op, unsigned, cst) \ + TEST_ONE_CST (n, op, int, cst) \ + TEST_ONE_CST (n, op, bool, cst) \ + TEST_ONE_CST (n, op, test_enum, cst) + +#define TEST_ONE(n, op, type) \ + bool lshift_##type##_##n (type x, type y) \ + { \ + if (y != 0) \ + __builtin_unreachable (); \ + return (y << x) op x; \ + } + +#define TEST_OP(n, op) \ + TEST_ONE (n, op, unsigned) \ + TEST_ONE (n, op, int) \ + TEST_ONE (n, op, bool) \ + TEST_ONE (n, op, test_enum) + +typedef enum +{ + MONE = -1, + ZERO = 0, + ONE = 1, + TWO = 2 +} test_enum; + +TEST_OP_CST (eq, ==, 0) +TEST_OP_CST (ne, !=, 0) +TEST_OP_CST (lt, <, 0) +TEST_OP_CST (gt, >, 0) +TEST_OP_CST (le, <=, 0) +TEST_OP_CST (ge, >=, 0) + +TEST_OP (eq, ==) +TEST_OP (ne, !=) +TEST_OP (lt, <) +TEST_OP (gt, >) +TEST_OP (le, <=) +TEST_OP (ge, >=) + +/* These end up getting folded by other patterns. */ +/* { dg-final { scan-tree-dump-times "x_\\d\\(D\\) == 0" 8 optimized } } */ +/* { dg-final { scan-tree-dump-times "x_\\d\\(D\\) != 0" 8 optimized } } */ +/* { dg-final { scan-tree-dump-times "x_\\d\\(D\\) > 0" 4 optimized } } */ +/* { dg-final { scan-tree-dump-times "x_\\d\\(D\\) < 0" 4 optimized } } */ +/* { dg-final { scan-tree-dump-times "x_\\d\\(D\\) >= 0" 4 optimized } } */ +/* { dg-final { scan-tree-dump-times "x_\\d\\(D\\) <= 0" 4 optimized } } */ +/* { dg-final { scan-tree-dump-times "~x_\\d\\(D\\)" 4 optimized } } */ +/* { dg-final { scan-tree-dump-times "return x_\\d\\(D\\);" 4 optimized } } */ +/* { dg-final { scan-tree-dump-times "return 0;" 4 optimized } } */ +/* { dg-final { scan-tree-dump-times "return 1;" 4 optimized } } */ +/* Total: 48. */ diff --git a/gcc/testsuite/gcc.dg/match-shift-cmp-3.c b/gcc/testsuite/gcc.dg/match-shift-cmp-3.c new file mode 100644 index 000000000000..34380cfeb969 --- /dev/null +++ b/gcc/testsuite/gcc.dg/match-shift-cmp-3.c @@ -0,0 +1,44 @@ +/* { dg-do compile } */ +/* { dg-options "-O2 -fdump-tree-optimized" } */ + +/* The fold (y << x) <op> x -> 0|1 shouldn't trigger when y is negative or + zero unsigned (except for == and !=). */ + +#define TEST_ONE_CST(n, op, type, cst) \ + bool lshift_cst_##type##_##n (type x) { return ((cst << x) op x); } + +#define TEST_OP_CST(n, op, cst) \ + TEST_ONE_CST (n, op, int, cst) \ + TEST_ONE_CST (n, op, test_enum, cst) + +#define TEST_ONE(n, op, type) \ + bool lshift_##type##_##n (type x, type y) \ + { \ + if (y > 0) \ + __builtin_unreachable (); \ + return ((y << x) op x); \ + } + +#define TEST_OP(n, op) \ + TEST_ONE (n, op, int) \ + TEST_ONE (n, op, test_enum) + +typedef enum +{ + MONE = -1, + ZERO = 0, + ONE = 1, + TWO = 2 +} test_enum; + +TEST_OP_CST (lt, <, -1) +TEST_OP_CST (gt, >, -2) +TEST_OP_CST (le, <=, -3) +TEST_OP_CST (ge, >=, -4) + +TEST_OP (lt, <) +TEST_OP (gt, >) +TEST_OP (le, <=) +TEST_OP (ge, >=) + +/* { dg-final { scan-tree-dump-times "<<" 16 optimized } } */ 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..629e2a376d11 --- /dev/null +++ b/gcc/testsuite/gcc.dg/match-shift-cmp-4.c @@ -0,0 +1,51 @@ +/* { dg-do compile } */ +/* { dg-options "-O2 -fdump-tree-optimized" } */ + +/* The fold (y << x) <op> x -> 0|1 should trigger when y is negative + unsigned. */ + +#define TEST_ONE_CST(n, op, type, cst) \ + bool lshift_cst_##type##_##n (type x) { return ((unsigned) (cst) << x) op x; } + +#define TEST_OP_CST(n, op, cst) \ + TEST_ONE_CST (n, op, unsigned, cst) \ + TEST_ONE_CST (n, op, int, cst) \ + TEST_ONE_CST (n, op, test_enum, cst) + +#define TEST_ONE(n, op, type) \ + bool lshift_##type##_##n (type x, type y) \ + { \ + if ((int) y <= 0) \ + __builtin_unreachable (); \ + return ((unsigned) (y) << x) op x; \ + } + +#define TEST_OP(n, op) \ + TEST_ONE (n, op, unsigned) \ + TEST_ONE (n, op, int) \ + TEST_ONE (n, op, test_enum) + +typedef enum +{ + MONE = -1, + ZERO = 0, + ONE = 1, + TWO = 2 +} test_enum; + +TEST_OP_CST (eq, ==, -1) +TEST_OP_CST (ne, !=, -2) +TEST_OP_CST (lt, <, -3) +TEST_OP_CST (gt, >, -4) +TEST_OP_CST (le, <=, -5) +TEST_OP_CST (ge, >=, -6) + +TEST_OP (eq, ==) +TEST_OP (ne, !=) +TEST_OP (lt, <) +TEST_OP (gt, >) +TEST_OP (le, <=) +TEST_OP (ge, >=) + +/* { dg-final { scan-tree-dump-times "return 0;" 18 optimized } } */ +/* { dg-final { scan-tree-dump-times "return 1;" 18 optimized } } */
