From: Andrew Pinski <apin...@marvell.com> I noticed we were missing these simplifications so let's add them.
This adds the following simplifications: U & N <= U -> true U & N > U -> false When U is known to be as non-negative. When N is also known to be non-negative, this is also true: U | N < U -> false U | N >= U -> true When N is a negative integer, the result flips and we get: U | N < U -> true U | N >= U -> false We could extend this later on to be the case where we know N is nonconstant but is known to be negative. Bootstrapped and tested on x86_64-linux-gnu with no regressions. PR tree-optimization/101590 PR tree-optimization/94884 gcc/ChangeLog: * match.pd (`(X BIT_OP Y) CMP X`): New pattern. gcc/testsuite/ChangeLog: * gcc.dg/tree-ssa/bitcmp-1.c: New test. * gcc.dg/tree-ssa/bitcmp-2.c: New test. * gcc.dg/tree-ssa/bitcmp-3.c: New test. * gcc.dg/tree-ssa/bitcmp-4.c: New test. * gcc.dg/tree-ssa/bitcmp-5.c: New test. * gcc.dg/tree-ssa/bitcmp-6.c: New test. --- gcc/match.pd | 24 +++++++++++++ gcc/testsuite/gcc.dg/tree-ssa/bitcmp-1.c | 20 +++++++++++ gcc/testsuite/gcc.dg/tree-ssa/bitcmp-2.c | 20 +++++++++++ gcc/testsuite/gcc.dg/tree-ssa/bitcmp-3.c | 21 ++++++++++++ gcc/testsuite/gcc.dg/tree-ssa/bitcmp-4.c | 36 ++++++++++++++++++++ gcc/testsuite/gcc.dg/tree-ssa/bitcmp-5.c | 43 ++++++++++++++++++++++++ gcc/testsuite/gcc.dg/tree-ssa/bitcmp-6.c | 41 ++++++++++++++++++++++ 7 files changed, 205 insertions(+) create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/bitcmp-1.c create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/bitcmp-2.c create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/bitcmp-3.c create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/bitcmp-4.c create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/bitcmp-5.c create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/bitcmp-6.c diff --git a/gcc/match.pd b/gcc/match.pd index 5f6aeb07ac0..7d651a6582d 100644 --- a/gcc/match.pd +++ b/gcc/match.pd @@ -2707,6 +2707,30 @@ DEFINE_INT_AND_FLOAT_ROUND_FN (RINT) (if (TREE_INT_CST_LOW (@1) & 1) { constant_boolean_node (cmp == NE_EXPR, type); }))) +/* + U & N <= U -> true + U & N > U -> false + U needs to be non-negative. + + U | N < U -> false + U | N >= U -> true + U and N needs to be non-negative + + U | N < U -> true + U | N >= U -> false + U needs to be non-negative and N needs to be a negative constant. + */ +(for cmp (lt ge le gt ) + bitop (bit_ior bit_ior bit_and bit_and) + (simplify + (cmp:c (bitop:c tree_expr_nonnegative_p@0 @1) @0) + (if (INTEGRAL_TYPE_P (TREE_TYPE (@0))) + (if (bitop == BIT_AND_EXPR || tree_expr_nonnegative_p (@1)) + { constant_boolean_node (cmp == GE_EXPR || cmp == LE_EXPR, type); } + /* The sign is opposite now so the comparison is swapped around. */ + (if (TREE_CODE (@1) == INTEGER_CST && wi::neg_p (wi::to_wide (@1))) + { constant_boolean_node (cmp == LT_EXPR, type); }))))) + /* Arguments on which one can call get_nonzero_bits to get the bits possibly set. */ (match with_possible_nonzero_bits diff --git a/gcc/testsuite/gcc.dg/tree-ssa/bitcmp-1.c b/gcc/testsuite/gcc.dg/tree-ssa/bitcmp-1.c new file mode 100644 index 00000000000..f3d515bb2d6 --- /dev/null +++ b/gcc/testsuite/gcc.dg/tree-ssa/bitcmp-1.c @@ -0,0 +1,20 @@ +/* { dg-do compile } */ +/* { dg-options "-O2 -fdump-tree-optimized" } */ +/* PR tree-optimization/101590 */ + +int f_and_le(unsigned len) { + const unsigned N = 4; + unsigned newlen = len & -N; + return newlen <= len; // return 1 +} +int f_or_ge(unsigned len) { + const unsigned N = 4; + unsigned newlen = len | -N; + return newlen >= len; // return 1 +} + +/* { dg-final { scan-tree-dump-not " <= " "optimized" } } */ +/* { dg-final { scan-tree-dump-not " >= " "optimized" } } */ +/* { dg-final { scan-tree-dump-not " & " "optimized" } } */ +/* { dg-final { scan-tree-dump-not " \\\| " "optimized" } } */ +/* { dg-final { scan-tree-dump-times "return 1;" 2 "optimized" } } */ diff --git a/gcc/testsuite/gcc.dg/tree-ssa/bitcmp-2.c b/gcc/testsuite/gcc.dg/tree-ssa/bitcmp-2.c new file mode 100644 index 00000000000..d0031d9ecb8 --- /dev/null +++ b/gcc/testsuite/gcc.dg/tree-ssa/bitcmp-2.c @@ -0,0 +1,20 @@ +/* { dg-do compile } */ +/* { dg-options "-O2 -fdump-tree-optimized" } */ +/* PR tree-optimization/101590 */ + +int f_and_gt(unsigned len) { + const unsigned N = 4; + unsigned newlen = len & -N; + return newlen > len; // return 0 +} +int f_or_lt(unsigned len) { + const unsigned N = 4; + unsigned newlen = len | -N; + return newlen < len; // return 0 +} + +/* { dg-final { scan-tree-dump-not " > " "optimized" } } */ +/* { dg-final { scan-tree-dump-not " < " "optimized" } } */ +/* { dg-final { scan-tree-dump-not " & " "optimized" } } */ +/* { dg-final { scan-tree-dump-not " \\\| " "optimized" } } */ +/* { dg-final { scan-tree-dump-times "return 0;" 2 "optimized" } } */ \ No newline at end of file diff --git a/gcc/testsuite/gcc.dg/tree-ssa/bitcmp-3.c b/gcc/testsuite/gcc.dg/tree-ssa/bitcmp-3.c new file mode 100644 index 00000000000..5cfab7dc742 --- /dev/null +++ b/gcc/testsuite/gcc.dg/tree-ssa/bitcmp-3.c @@ -0,0 +1,21 @@ +/* { dg-do compile } */ +/* { dg-options "-O2 -fdump-tree-optimized" } */ +/* PR tree-optimization/94884 */ + +#define bool _Bool +bool decide() __attribute((const)); + +inline unsigned getXOrY(unsigned x, unsigned y) +{ + return decide() ? y : x; +} + +bool f(unsigned x, unsigned y) +{ + return (x | y) >= getXOrY(x, y); +} + + +/* { dg-final { scan-tree-dump-not " >= " "optimized" } } */ +/* { dg-final { scan-tree-dump-not " \\\| " "optimized" } } */ +/* { dg-final { scan-tree-dump-times "return 1;" 1 "optimized" } } */ \ No newline at end of file diff --git a/gcc/testsuite/gcc.dg/tree-ssa/bitcmp-4.c b/gcc/testsuite/gcc.dg/tree-ssa/bitcmp-4.c new file mode 100644 index 00000000000..701014b2d0e --- /dev/null +++ b/gcc/testsuite/gcc.dg/tree-ssa/bitcmp-4.c @@ -0,0 +1,36 @@ +/* { dg-do compile } */ +/* { dg-options "-O2 -fdump-tree-optimized" } */ +/* PR tree-optimization/101590 */ + +int f_and_le(int len) { + const int N = 4; + int newlen = len & -N; + return newlen <= len; +} +int f_or_ge(int len) { + const int N = 4; + int newlen = len | -N; + return newlen >= len; +} + +int f_and_gt(int len) { + const int N = 4; + int newlen = len & -N; + return newlen > len; +} +int f_or_lt(int len) { + const int N = 4; + int newlen = len | -N; + return newlen < len; +} + +/* These cannot be optimized since we don't know if the sign + can change or not. */ +/* { dg-final { scan-tree-dump-times " > " 1 "optimized" } } */ +/* { dg-final { scan-tree-dump-times " < " 1 "optimized" } } */ +/* { dg-final { scan-tree-dump-times " <= " 1 "optimized" } } */ +/* { dg-final { scan-tree-dump-times " >= " 1 "optimized" } } */ +/* { dg-final { scan-tree-dump-times " & " 2 "optimized" } } */ +/* { dg-final { scan-tree-dump-times " \\\| " 2 "optimized" } } */ +/* { dg-final { scan-tree-dump-not "return 1;" "optimized" } } */ +/* { dg-final { scan-tree-dump-not "return 0;" "optimized" } } */ diff --git a/gcc/testsuite/gcc.dg/tree-ssa/bitcmp-5.c b/gcc/testsuite/gcc.dg/tree-ssa/bitcmp-5.c new file mode 100644 index 00000000000..a6be14294b4 --- /dev/null +++ b/gcc/testsuite/gcc.dg/tree-ssa/bitcmp-5.c @@ -0,0 +1,43 @@ +/* { dg-do compile } */ +/* { dg-options "-O2 -fdump-tree-optimized" } */ +/* PR tree-optimization/101590 */ + +/* These are the signed integer versions + of `(a & b) CMP a` and `(a | b) CMP a` + which can be optimized to 1. */ + + +/* For `&`, the non-negativeness of b is not taken into account. */ +int f_and_le(int len) { + len &= 0xfffff; + const int N = 4; + int newlen = len & -N; + return newlen <= len; // return 1 +} +int f_and_le_(int len, int N) { + len &= 0xfffff; + int newlen = len & -N; + return newlen <= len; // return 1 +} + + +/* For `|`, to get a known value, b either needs to be non-negative + or a constant. For the negative constant case, we swap around the comparison. */ +int f_or_ge_(int len, int N) { + len &= 0xfffff; + N &= 0xffff; + int newlen = len | N; + return newlen >= len; // return 1 +} +int f_or_lt(int len) { + len &= 0xfffff; + const int N = 4; + int newlen = len | -N; + return newlen < len; // return 1 +} + +/* { dg-final { scan-tree-dump-not " <= " "optimized" } } */ +/* { dg-final { scan-tree-dump-not " >= " "optimized" } } */ +/* { dg-final { scan-tree-dump-not " & " "optimized" } } */ +/* { dg-final { scan-tree-dump-not " \\\| " "optimized" } } */ +/* { dg-final { scan-tree-dump-times "return 1;" 4 "optimized" } } */ diff --git a/gcc/testsuite/gcc.dg/tree-ssa/bitcmp-6.c b/gcc/testsuite/gcc.dg/tree-ssa/bitcmp-6.c new file mode 100644 index 00000000000..a86a19fbef2 --- /dev/null +++ b/gcc/testsuite/gcc.dg/tree-ssa/bitcmp-6.c @@ -0,0 +1,41 @@ +/* { dg-do compile } */ +/* { dg-options "-O2 -fdump-tree-optimized" } */ +/* PR tree-optimization/101590 */ + +/* These are the signed integer versions + of `(a & b) CMP a` and `(a | b) CMP a` + which can be optimized to 0. */ + +/* For `&`, the non-negativeness of b is not taken into account. */ +int f_and_gt(int len) { + len &= 0xfffff; + const int N = 4; + int newlen = len & -N; + return newlen > len; // return 0 +} +int f_and_gt_(int len, int N) { + len &= 0xfffff; + int newlen = len & -N; + return newlen > len; // return 0 +} + +/* For `|`, to get a known value, b either needs to be non-negative + or a constant. For the negative constant case, we swap around the comparison. */ +int f_or_lt_(int len, int N) { + len &= 0xfffff; + N &= 0xffff; + int newlen = len | N; + return newlen < len; // return 0 +} +int f_or_ge(int len) { + len &= 0xfffff; + const int N = 4; + int newlen = len | -N; + return newlen >= len; // return 0 +} + +/* { dg-final { scan-tree-dump-not " > " "optimized" } } */ +/* { dg-final { scan-tree-dump-not " < " "optimized" } } */ +/* { dg-final { scan-tree-dump-not " & " "optimized" } } */ +/* { dg-final { scan-tree-dump-not " \\\| " "optimized" } } */ +/* { dg-final { scan-tree-dump-times "return 0;" 4 "optimized" } } */ -- 2.39.3