[PATCH] MATCH: Simplify `(X &| B) CMP X` if possible [PR 101590]

[Andrew Pinski <pinskia@gmail.com>]

From: Andrew Pinski <apinski@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