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

On Wed, Aug 5, 2026 at 4:59 AM <[email protected]> wrote:
>
> 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)))

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)
>