match: move a mask across a following right shift
Checks
Commit Message
From: Kyrylo Tkachov <ktkachov@nvidia.com>
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 <ktkachov@nvidia.com>
---
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
Comments
On Wed, Aug 5, 2026 at 4:59 AM <ktkachov@nvidia.com> wrote:
>
> From: Kyrylo Tkachov <ktkachov@nvidia.com>
>
> 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 <ktkachov@nvidia.com>
> ---
> 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)))
First off this:
TYPE_UNSIGNED (type)
> + || tree_expr_nonnegative_p (@0)
You could just use tree_expr_nonnegative_p then.
> + (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" } } */
Please split up the testcases and add some correctness one to make
sure it is valid to do.
> --
> 2.50.1 (Apple Git-155)
>
@@ -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. */
new file mode 100644
@@ -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" } } */