[PATCH][v2] match.pd: drop an operand discarded by a shift

From: Kyrylo Tkachov <[email protected]>

Neither an inclusive nor an exclusive or can carry, so an operand whose set
bits all lie below the shift count contributes nothing to the result:

  int f (int a, int b) { return (a ^ (b & 1)) >> 1; }

aarch64 -O2 before:

	and	w1, w1, 1
	eor	w0, w1, w0
	asr	w0, w0, 1

after:

	asr	w0, w0, 1

The set bits are read from tree_nonzero_bits, so the rule also fires when
the operand is a boolean, a narrow value or anything else whose range the
middle end already knows.  Found by mining the optimized dumps of real code,
where the shape comes from flag bits packed into the low bits of a word.

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

gcc/ChangeLog:

	* match.pd ((X | Y) >> C, (X ^ Y) >> C): New simplification.

gcc/testsuite/ChangeLog:

	* gcc.dg/tree-ssa/shift-drops-bitop-1.c: New test.

Signed-off-by: Kyrylo Tkachov <[email protected]>
---
 gcc/match.pd                                  | 15 +++++++++++
 .../gcc.dg/tree-ssa/shift-drops-bitop-1.c     | 26 +++++++++++++++++++
 2 files changed, 41 insertions(+)
 create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/shift-drops-bitop-1.c

diff --git a/gcc/match.pd b/gcc/match.pd
index 076e62a79c8..1174026b691 100644
--- a/gcc/match.pd
+++ b/gcc/match.pd
@@ -5021,6 +5021,21 @@ DEFINE_INT_AND_FLOAT_ROUND_FN (RINT)
 			- TYPE_PRECISION (TREE_TYPE (@2)))))
   (bit_and (convert @0) (lshift { build_minus_one_cst (type); } @1))))
 
+/* (X op Y) >> C -> X >> C when every set bit of Y lies below bit C.
+   Neither an inclusive nor an exclusive or can carry into the bits the
+   shift keeps, so Y contributes nothing to the result.  */
+(for op (bit_ior bit_xor)
+ (simplify
+  (rshift (op @0 @1) INTEGER_CST@2)
+  (if (INTEGRAL_TYPE_P (type)
+       && tree_fits_uhwi_p (@2)
+       && tree_to_uhwi (@2) < TYPE_PRECISION (type))
+   (with { wide_int mask = wi::mask (tree_to_uhwi (@2), true,
+				     TYPE_PRECISION (type)); }
+    (if ((tree_nonzero_bits (@1) & mask) == 0)
+     (rshift @0 @2)
+     (if ((tree_nonzero_bits (@0) & mask) == 0)
+      (rshift @1 @2)))))))
 #if GIMPLE
 /* (X >> C1) << (C1 + C2) -> X << C2 if the low C1 bits of X are zero.  */
 (simplify
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/shift-drops-bitop-1.c b/gcc/testsuite/gcc.dg/tree-ssa/shift-drops-bitop-1.c
new file mode 100644
index 00000000000..50d547c6c18
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/shift-drops-bitop-1.c
@@ -0,0 +1,26 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-original -fdump-tree-optimized" } */
+
+/* Neither an inclusive nor an exclusive or can carry, so an operand whose
+   set bits all lie below the shift count contributes nothing.  */
+
+int f1 (int a, int b) { return (a ^ (b & 1)) >> 1; }
+unsigned f2 (unsigned a, unsigned b) { return (a | (b & 7)) >> 3; }
+long f3 (long a, int c) { return (a ^ (long) (c != 0)) >> 1; }
+
+/* GENERIC folding must preserve evaluation of the discarded operand.  */
+int side;
+int f4 (int a, int b) { return (a ^ ((side++, b) & 1)) >> 1; }
+unsigned f5 (unsigned a, unsigned b)
+{
+  return ((a * 3) ^ ((side++, b) & 1)) >> 1;
+}
+
+/* Bit 1 of the mask survives the shift, so the exclusive or stays.  */
+int keep (int a, int b) { return (a ^ (b & 3)) >> 1; }
+
+/* { dg-final { scan-tree-dump-times " \\^ " 1 "optimized" } } */
+/* { dg-final { scan-tree-dump-not " \\| " "optimized" } } */
+/* { dg-final { scan-tree-dump-times " \\^ " 2 "original" } } */
+/* { dg-final { scan-tree-dump-not " \\| " "original" } } */
+/* { dg-final { scan-tree-dump-times "side\\+\\+" 2 "original" } } */
-- 
2.50.1 (Apple Git-155)