[PATCH] match: fold two comparisons of a masked value

From: Kyrylo Tkachov <[email protected]>

  ((X + C1) & LOWMASK) ==/!= C2 -> (X & LOWMASK) ==/!= C2 - C1
  (X & HIGHMASK) >/<= C -> X >/<= (C | ~HIGHMASK)

Only the low bits of the addition survive the first mask, so the constant
moves to the other side of the comparison and the addition goes away.  A
comparison constant that does not fit the mask makes the result fixed.

Clearing the low bits rounds the value down, and a rounded value passes a
relational comparison exactly when the value itself passes it against the
constant with those bits set, so the second mask goes away too.  The
other two predicates are already canonicalised into these.

  int f (int x) { return (x & -8) > 16; }

aarch64 -O2:

  before                          after
    and   w0, w0, -8                cmp   w0, 23
    cmp   w0, 16                    cset  w0, gt
    cset  w0, gt

Two existing tests observe shapes this rewrite now folds.  bic-bitmask-19.c
scans for "> 1" and the loop guard (n & -16) > 0 becomes n > 15, which the
regex also matches, so it is anchored on the statement end.  pr68217.c
relies on the comparison keeping the masked value live, so the value is
returned instead.

Keep signed additions that trap or carry sanitizer instrumentation.
Also accept high-mask constants whose discarded low bits are already set.

Bootstrapped and tested on aarch64-none-linux-gnu.
Ok for trunk?
Thanks,
Kyrill

gcc/ChangeLog:

	* match.pd (((X + C1) & LOWMASK) ==/!= C2): New simplification.
	((X & HIGHMASK) >/<= C): Likewise.

gcc/testsuite/ChangeLog:

	* gcc.dg/tree-ssa/maskcmp-1.c: New test.
	* gcc.dg/bic-bitmask-19.c: Anchor the comparison scan.
	* gcc.dg/pr68217.c: Return the masked value.
	* gcc.dg/tree-ssa/maskcmp-overflow-1.c: New test.
	* gcc.dg/tree-ssa/maskcmp-overflow-2.c: New test.

Signed-off-by: Kyrylo Tkachov <[email protected]>
---
 gcc/match.pd                                  | 28 +++++++++++++++++++
 gcc/testsuite/gcc.dg/bic-bitmask-19.c         |  4 ++-
 gcc/testsuite/gcc.dg/pr68217.c                | 12 ++++++--
 gcc/testsuite/gcc.dg/tree-ssa/maskcmp-1.c     | 23 +++++++++++++++
 .../gcc.dg/tree-ssa/maskcmp-overflow-1.c      | 10 +++++++
 .../gcc.dg/tree-ssa/maskcmp-overflow-2.c      | 10 +++++++
 6 files changed, 83 insertions(+), 4 deletions(-)
 create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/maskcmp-1.c
 create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/maskcmp-overflow-1.c
 create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/maskcmp-overflow-2.c

diff --git a/gcc/match.pd b/gcc/match.pd
index 9924f95c4cc..b27d9a0bad0 100644
--- a/gcc/match.pd
+++ b/gcc/match.pd
@@ -5354,6 +5354,34 @@ DEFINE_INT_AND_FLOAT_ROUND_FN (RINT)
 	 && wi::lshift (wi::to_wide (@0), cand) == wi::to_wide (@2))
      (cmp @1 { build_int_cst (TREE_TYPE (@1), cand); }))))))
 
+/* Fold ((X + C1) & LOWMASK) ==/!= C2 into (X & LOWMASK) ==/!= C2 - C1.
+   Only the low bits of the addition survive the mask, so the constant can
+   move to the other side of the comparison and the addition goes away.  */
+(for cmp (eq ne)
+ (simplify
+  (cmp (bit_and:s (plus:s @0 INTEGER_CST@1) INTEGER_CST@2) INTEGER_CST@3)
+  (if (INTEGRAL_TYPE_P (TREE_TYPE (@0))
+       && !TYPE_OVERFLOW_TRAPS (TREE_TYPE (@0))
+       && !TYPE_OVERFLOW_SANITIZED (TREE_TYPE (@0))
+       && wi::popcount (wi::to_wide (@2) + 1) == 1)
+   (with { wide_int mask = wi::to_wide (@2);
+	   wide_int rhs = (wi::to_wide (@3) - wi::to_wide (@1)) & mask; }
+    (if ((wi::to_wide (@3) & ~mask) == 0)
+     (cmp (bit_and @0 @2)
+	  { wide_int_to_tree (TREE_TYPE (@0), rhs); })
+     { constant_boolean_node (cmp == NE_EXPR, type); })))))
+
+/* Fold (X & HIGHMASK) >/<= C into X >/<= (C | ~HIGHMASK).  Clearing the
+   low bits of X rounds it down, and a rounded value passes the comparison
+   exactly when X passes it against the constant with those bits set.  */
+(for cmp (gt le)
+ (simplify
+  (cmp (bit_and:s @0 INTEGER_CST@1) INTEGER_CST@2)
+  (if (INTEGRAL_TYPE_P (TREE_TYPE (@0))
+       && bitmask_inv_cst_vector_p (@1))
+   (with { wide_int c = wi::to_wide (@2) | wi::bit_not (wi::to_wide (@1)); }
+    (cmp @0 { wide_int_to_tree (TREE_TYPE (@0), c); })))))
+
 /* Fold ((X << C1) & C2) cmp C3 into (X & (C2 >> C1)) cmp (C3 >> C1)
 	((X >> C1) & C2) cmp C3 into (X & (C2 << C1)) cmp (C3 << C1).  */
 (for cmp (ne eq)
diff --git a/gcc/testsuite/gcc.dg/bic-bitmask-19.c b/gcc/testsuite/gcc.dg/bic-bitmask-19.c
index aa139da5c1e..d1574fbff80 100644
--- a/gcc/testsuite/gcc.dg/bic-bitmask-19.c
+++ b/gcc/testsuite/gcc.dg/bic-bitmask-19.c
@@ -19,6 +19,8 @@ void fun2(uint32_t *x, int n)
 
 #include "bic-bitmask.h"
 
-/* { dg-final { scan-tree-dump-times {>\s* 1} 1 dce7 { target vect_int } } } */
+/* The loop guard (n & -16) > 0 now folds to n > 15, so anchor the scan on
+   the statement end to keep it matching only the comparison under test.  */
+/* { dg-final { scan-tree-dump-times {>\s* 1;} 1 dce7 { target vect_int } } } */
 /* { dg-final { scan-tree-dump-not {&\s* 4294967294} dce7 { target vect_int } } } */
 
diff --git a/gcc/testsuite/gcc.dg/pr68217.c b/gcc/testsuite/gcc.dg/pr68217.c
index 60c80106760..279fedd86f4 100644
--- a/gcc/testsuite/gcc.dg/pr68217.c
+++ b/gcc/testsuite/gcc.dg/pr68217.c
@@ -1,13 +1,19 @@
 /* { dg-do compile } */
 /* { dg-options "-O2 -fdisable-tree-evrp -fdump-tree-vrp1 -fno-tree-ccp" } */
 
-int foo (void)
+#include <limits.h>
+
+/* Return x so that its range is still exported after the comparison folds
+   away.  (x & LLONG_MIN) < 1 is true for both values x can take, so the
+   test of it no longer keeps x live by itself.  */
+
+long long foo (void)
 {
     volatile int a = -1;
-    long long b = (1LL << (sizeof (b) * 8 - 1)); // LLONG_MIN
+    long long b = LLONG_MIN;
     long long x = (a & b); // x == 0x8000000000000000
     if (x < 1LL) { ; } else { __builtin_abort(); }
-    return 0;
+    return x;
 }
 
 /* { dg-final { scan-tree-dump "\\\[-INF, -INF\\\]\\\[0, 0\\\]" "vrp1" } } */
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/maskcmp-1.c b/gcc/testsuite/gcc.dg/tree-ssa/maskcmp-1.c
new file mode 100644
index 00000000000..97025c45b1d
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/maskcmp-1.c
@@ -0,0 +1,23 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-optimized" } */
+
+/* Only the low bits of the addition survive the mask, so the constant
+   moves to the other side of the comparison.  */
+int f1 (unsigned int x) { return ((x + 3u) & 7u) == 5u; }
+int f2 (unsigned int x) { return ((x + 300u) & 255u) != 7u; }
+
+/* The comparison constant does not fit the mask, the result is fixed.  */
+int f3 (unsigned int x) { return ((x + 3u) & 7u) == 9u; }
+
+/* Clearing the low bits rounds down, so the comparison constant can absorb
+   them and the mask goes away.  */
+int f4 (int x) { return (x & -8) > 16; }
+int f5 (int x) { return (x & -8) <= -16; }
+int f6 (unsigned int x) { return (x & 0xfffffff0u) > 100u; }
+
+/* { dg-final { scan-tree-dump-not " \\+ " "optimized" } } */
+/* { dg-final { scan-tree-dump-times " & 7;" 1 "optimized" } } */
+/* { dg-final { scan-tree-dump-times " & 255" 1 "optimized" } } */
+/* { dg-final { scan-tree-dump-times " > 23" 1 "optimized" } } */
+/* { dg-final { scan-tree-dump-times " < -8" 1 "optimized" } } */
+/* { dg-final { scan-tree-dump-times " > 111" 1 "optimized" } } */
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/maskcmp-overflow-1.c b/gcc/testsuite/gcc.dg/tree-ssa/maskcmp-overflow-1.c
new file mode 100644
index 00000000000..02e6d04bfff
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/maskcmp-overflow-1.c
@@ -0,0 +1,10 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -ftrapv -fdump-tree-optimized" } */
+
+int
+f (int x)
+{
+  return ((x + 1) & 7) == 0;
+}
+
+/* { dg-final { scan-tree-dump "\\+ 1" "optimized" } } */
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/maskcmp-overflow-2.c b/gcc/testsuite/gcc.dg/tree-ssa/maskcmp-overflow-2.c
new file mode 100644
index 00000000000..bacec863f28
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/maskcmp-overflow-2.c
@@ -0,0 +1,10 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -fsanitize=signed-integer-overflow -fdump-tree-optimized" } */
+
+int
+f (int x)
+{
+  return ((x + 1) & 7) == 0;
+}
+
+/* { dg-final { scan-tree-dump "UBSAN_CHECK_ADD" "optimized" } } */
-- 
2.50.1 (Apple Git-155)