[PATCH] 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.

There is deliberately no single use restriction.  Most real instances keep
the exclusive or alive for another use and still save the shift's operand
being computed on this path.

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                                  | 11 ++++++++++
 .../gcc.dg/tree-ssa/shift-drops-bitop-1.c     | 22 +++++++++++++++++++
 2 files changed, 33 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 b27d9a0bad0..21bcfd069d4 100644
--- a/gcc/match.pd
+++ b/gcc/match.pd
@@ -5032,6 +5032,17 @@ 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:c @0 @1) INTEGER_CST@2)
+  (if (INTEGRAL_TYPE_P (type)
+       && wi::ltu_p (wi::to_wide (@2), element_precision (type))
+       && (tree_nonzero_bits (@1)
+	   & wi::mask (tree_to_uhwi (@2), true, element_precision (type))) == 0)
+   (rshift @0 @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..fe9cca34b4d
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/shift-drops-bitop-1.c
@@ -0,0 +1,22 @@
+/* { 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; }
+
+/* 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\\+\\+" 1 "original" } } */
-- 
2.50.1 (Apple Git-155)