Re: [PATCH] match: drop a mask that the following right shift discards

On Tue, Aug 4, 2026 at 3:48=E2=80=AFAM <[email protected]> wrote:
>
> From: Kyrylo Tkachov <[email protected]>
>
> (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 val=
ue.
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 =3D=3D
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 <[email protected]>
> ---
>  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)
>