aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorAndrew Pinski <apinski@marvell.com>2023-09-12 18:24:22 -0700
committerAndrew Pinski <pinskia@gmail.com>2023-10-27 00:49:30 -0700
commita5e69e94591ae282857d59e868ff6cea7306c802 (patch)
tree14ce48bb0a1eeed23e5f131ce19c7099595e08d9
parent7eed861e8ca3f533e56dea6348573caa09f16f5e (diff)
downloadgcc-a5e69e94591ae282857d59e868ff6cea7306c802.zip
gcc-a5e69e94591ae282857d59e868ff6cea7306c802.tar.gz
gcc-a5e69e94591ae282857d59e868ff6cea7306c802.tar.bz2
MATCH: Simplify `(X &| B) CMP X` if possible [PR 101590]
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.
-rw-r--r--gcc/match.pd24
-rw-r--r--gcc/testsuite/gcc.dg/tree-ssa/bitcmp-1.c20
-rw-r--r--gcc/testsuite/gcc.dg/tree-ssa/bitcmp-2.c20
-rw-r--r--gcc/testsuite/gcc.dg/tree-ssa/bitcmp-3.c21
-rw-r--r--gcc/testsuite/gcc.dg/tree-ssa/bitcmp-4.c36
-rw-r--r--gcc/testsuite/gcc.dg/tree-ssa/bitcmp-5.c43
-rw-r--r--gcc/testsuite/gcc.dg/tree-ssa/bitcmp-6.c41
7 files changed, 205 insertions, 0 deletions
diff --git a/gcc/match.pd b/gcc/match.pd
index 5f6aeb0..7d651a6 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 0000000..f3d515b
--- /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 0000000..d0031d9
--- /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 0000000..5cfab7d
--- /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 0000000..701014b
--- /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 0000000..a6be142
--- /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 0000000..a86a19f
--- /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" } } */