match: drop a mask that the following right shift discards
Checks
Commit Message
From: Kyrylo Tkachov <ktkachov@nvidia.com>
(X & (-1 << Y)) >> Y clears the low Y bits and then shifts them out, so
the mask is redundant. This drops three operations, and it turns up in
code that aligns a value down before scaling it.
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 & (-1 << 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 | 5 +++++
gcc/testsuite/gcc.dg/tree-ssa/shift-mask-1.c | 13 +++++++++++++
2 files changed, 18 insertions(+)
create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/shift-mask-1.c
Comments
On Tue, Aug 4, 2026 at 3:48 AM <ktkachov@nvidia.com> wrote:
>
> From: Kyrylo Tkachov <ktkachov@nvidia.com>
>
> (X & (-1 << Y)) >> Y clears the low Y bits and then shifts them out, so
> the mask is redundant. This drops three operations, and it turns up in
> code that aligns a value down before scaling it.
>
> unsigned f (unsigned x, int y) { return (x & (~0u << y)) >> y; }
We can do a generic version for this rather than depending on -1 or any value.
That is:
```
unsigned g0 (unsigned x, int y, unsigned a)
{
return (x & (a << y)) >> y;
}
```
can be convert into:
```
unsigned g (unsigned x, int y, unsigned a)
{
return (x >> y) & a;
}
```
When a and x are unsigned or a is all ones, this can be done.
For signed types, x needs to be non-negative, y needs to be constant
and a needs to have bit y not being set (that is (non_zero(a)>>y)&1 ==
0).
e.g.:
```
int h0 (int x, int y, unsigned short a)
{
return (x & (a << 3)) >> 3;
}
```
can be translated into:
```
int h1 (int x, int y, unsigned short a)
{
return (x) >> 3 & a;
}
```
>
> 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 & (-1 << 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 | 5 +++++
> gcc/testsuite/gcc.dg/tree-ssa/shift-mask-1.c | 13 +++++++++++++
> 2 files changed, 18 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 a97158bf062..ac35442f8ba 100644
> --- a/gcc/match.pd
> +++ b/gcc/match.pd
> @@ -5261,6 +5261,11 @@ DEFINE_INT_AND_FLOAT_ROUND_FN (RINT)
> - TYPE_PRECISION (TREE_TYPE (@2)))))
> (bit_and (convert @0) (lshift { build_minus_one_cst (type); } @1))))
>
> +/* (X & (-1 << Y)) >> Y -> X >> Y. The mask only clears bits that the
> + shift discards. */
> +(simplify
> + (rshift (bit_and:c @0 (lshift integer_all_onesp @1)) @1)
> + (rshift @0 @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. */
> 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..16d129d1f29
> --- /dev/null
> +++ b/gcc/testsuite/gcc.dg/tree-ssa/shift-mask-1.c
> @@ -0,0 +1,13 @@
> +/* { 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; }
> +
> +/* { dg-final { scan-tree-dump-not " & " "optimized" } } */
> +/* { dg-final { scan-tree-dump-not " << " "optimized" } } */
> +/* { dg-final { scan-tree-dump-times " >> " 4 "optimized" } } */
> --
> 2.50.1 (Apple Git-155)
>
@@ -5261,6 +5261,11 @@ DEFINE_INT_AND_FLOAT_ROUND_FN (RINT)
- TYPE_PRECISION (TREE_TYPE (@2)))))
(bit_and (convert @0) (lshift { build_minus_one_cst (type); } @1))))
+/* (X & (-1 << Y)) >> Y -> X >> Y. The mask only clears bits that the
+ shift discards. */
+(simplify
+ (rshift (bit_and:c @0 (lshift integer_all_onesp @1)) @1)
+ (rshift @0 @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. */
new file mode 100644
@@ -0,0 +1,13 @@
+/* { 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; }
+
+/* { dg-final { scan-tree-dump-not " & " "optimized" } } */
+/* { dg-final { scan-tree-dump-not " << " "optimized" } } */
+/* { dg-final { scan-tree-dump-times " >> " 4 "optimized" } } */