[PATCH] match: move a mask across a following right shift

From: Kyrylo Tkachov <[email protected]>

This is a respin of https://gcc.gnu.org/pipermail/gcc-patches/2026-August/726305.html
with a subject change as this is more general now after Andrea's feedback.

For an unsigned type,

  (X & (A << Y)) >> Y

is equal to

  (X >> Y) & A.

The same identity holds for a signed type when X is known nonnegative or
when the possible high bits of A cannot affect the sign-extension bits.  An
all-ones A is a special case in which the mask disappears completely.

  unsigned f (unsigned x, int y) { return (x & (~0u << y)) >> y; }

aarch64 -O2:

  before                          after
    mov   w2, -1                    lsr   w0, w0, w1
    lsl   w2, w2, w1
    and   w0, w2, w0
    lsr   w0, w0, w1

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

gcc/ChangeLog:

	* match.pd ((X & (A << Y)) >> Y): New simplification.

gcc/testsuite/ChangeLog:

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

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

diff --git a/gcc/match.pd b/gcc/match.pd
index 44ee449b61f..2e16ed0f7dc 100644
--- a/gcc/match.pd
+++ b/gcc/match.pd
@@ -5234,6 +5234,23 @@ DEFINE_INT_AND_FLOAT_ROUND_FN (RINT)
 			- TYPE_PRECISION (TREE_TYPE (@2)))))
   (bit_and (convert @0) (lshift { build_minus_one_cst (type); } @1))))
 
+/* Move a mask across a right shift when this does not change the sign bits.
+   An all-ones mask only clears bits that the shift discards.  */
+(simplify
+ (rshift (bit_and:cs @0 (lshift @2 @1)) @1)
+ (if (integer_all_onesp (@2))
+  (rshift @0 @1)
+  (if (ANY_INTEGRAL_TYPE_P (type)
+       && (TYPE_UNSIGNED (type)
+	   || tree_expr_nonnegative_p (@0)
+	   || (INTEGRAL_TYPE_P (type)
+	       && tree_fits_uhwi_p (@1)
+	       && tree_to_uhwi (@1) < TYPE_PRECISION (type)
+	       && (tree_nonzero_bits (@2)
+		   & wi::mask (TYPE_PRECISION (type)
+			       - tree_to_uhwi (@1) - 1,
+			       true, TYPE_PRECISION (type))) == 0)))
+   (bit_and (rshift @0 @1) @2))))
 /* (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.  */
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/shift-mask-1.c b/gcc/testsuite/gcc.dg/tree-ssa/shift-mask-1.c
new file mode 100644
index 00000000000..d98d9ed870b
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/shift-mask-1.c
@@ -0,0 +1,21 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-optimized" } */
+
+/* Masking off the bits that the following right shift discards is a no-op.  */
+
+unsigned int f1 (unsigned int x, int y) { return (x & (~0u << y)) >> y; }
+int f2 (int x, int y) { return (x & (~0 << y)) >> y; }
+unsigned long f3 (unsigned long x, int y) { return (x & (~0ul << y)) >> y; }
+unsigned int f4 (unsigned int x, int y) { return ((~0u << y) & x) >> y; }
+
+unsigned int g1 (unsigned int x, int y, unsigned int a)
+{ return (x & (a << y)) >> y; }
+int g2 (unsigned short x, int y, int a) { return (x & (a << y)) >> y; }
+int g3 (int x, unsigned short a) { return (x & (a << 3)) >> 3; }
+
+/* A variable signed value and mask can change the sign-extension bits.  */
+int keep (int x, int y, int a) { return (x & (a << y)) >> y; }
+
+/* { dg-final { scan-tree-dump-times " & " 4 "optimized" } } */
+/* { dg-final { scan-tree-dump-times " << " 1 "optimized" } } */
+/* { dg-final { scan-tree-dump-times " >> " 8 "optimized" } } */
-- 
2.50.1 (Apple Git-155)