Re: [PATCH] match.pd: drop an operand discarded by a shift

On Tue, Aug 4, 2026 at 2:47=E2=80=AFAM <[email protected]> wrote:
>
> From: Kyrylo Tkachov <[email protected]>
>
> Neither an inclusive nor an exclusive or can carry, so an operand whose s=
et
> bits all lie below the shift count contributes nothing to the result:
>
>   int f (int a, int b) { return (a ^ (b & 1)) >> 1; }
>
> aarch64 -O2 before:
>
>         and     w1, w1, 1
>         eor     w0, w1, w0
>         asr     w0, w0, 1
>
> after:
>
>         asr     w0, w0, 1
>
> The set bits are read from tree_nonzero_bits, so the rule also fires when
> the operand is a boolean, a narrow value or anything else whose range the
> middle end already knows.  Found by mining the optimized dumps of real co=
de,
> where the shape comes from flag bits packed into the low bits of a word.
>
> There is deliberately no single use restriction.  Most real instances kee=
p
> the exclusive or alive for another use and still save the shift's operand
> being computed on this path.
>
> Bootstrapped and tested on aarch64-none-linux-gnu.
> Ok for trunk?
> Thanks,
> Kyrill
>
> gcc/ChangeLog:
>
>         * match.pd ((X | Y) >> C, (X ^ Y) >> C): New simplification.
>
> gcc/testsuite/ChangeLog:
>
>         * gcc.dg/tree-ssa/shift-drops-bitop-1.c: New test.
>
> Signed-off-by: Kyrylo Tkachov <[email protected]>
> ---
>  gcc/match.pd                                  | 11 ++++++++++
>  .../gcc.dg/tree-ssa/shift-drops-bitop-1.c     | 22 +++++++++++++++++++
>  2 files changed, 33 insertions(+)
>  create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/shift-drops-bitop-1.c
>
> diff --git a/gcc/match.pd b/gcc/match.pd
> index b27d9a0bad0..21bcfd069d4 100644
> --- a/gcc/match.pd
> +++ b/gcc/match.pd
> @@ -5032,6 +5032,17 @@ DEFINE_INT_AND_FLOAT_ROUND_FN (RINT)
>                         - TYPE_PRECISION (TREE_TYPE (@2)))))
>    (bit_and (convert @0) (lshift { build_minus_one_cst (type); } @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.  */
> +(for op (bit_ior bit_xor)
> + (simplify
> +  (rshift (op:c @0 @1) INTEGER_CST@2)
Remove the `:c` (and see below).

> +  (if (INTEGRAL_TYPE_P (type)
> +       && wi::ltu_p (wi::to_wide (@2), element_precision (type))

tree_fits_uhwi_p (@2)
         && tree_to_uhwi (@2) < TYPE_PRECISION (type)


> +       && (tree_nonzero_bits (@1)
> +          & wi::mask (tree_to_uhwi (@2), true, element_precision (type))=
) =3D=3D 0)
> +   (rshift @0 @2))))

You can use TREE_PRECISION instead of element_precision here since you
already test if it is a scalar type.

So this should just be:
(if (INTEGRAL_TYPE_P (type)
    && tree_fits_uhwi_p (@2)
    && tree_to_uhwi (@2) < TYPE_PRECISION (type))
 (with { auto mask =3D wi::mask (tree_to_uhwi (@2), true, TYPE_PRECISION (t=
ype); }
  (if ((tree_nonzero_bits (@1) & mask)) =3D=3D 0)
    (rshift @0 @2)
     (if ((tree_nonzero_bits (@2) & mask)) =3D=3D 0)
      (rshift @0 @1))

This simplifies the generated code slightly and should speed up the
matching so won't need to go through the first part to be only
canceled out by the second part.

>  #if GIMPLE
>  /* (X >> C1) << (C1 + C2) -> X << C2 if the low C1 bits of X are zero.  =
*/
>  (simplify
> diff --git a/gcc/testsuite/gcc.dg/tree-ssa/shift-drops-bitop-1.c b/gcc/te=
stsuite/gcc.dg/tree-ssa/shift-drops-bitop-1.c
> new file mode 100644
> index 00000000000..fe9cca34b4d
> --- /dev/null
> +++ b/gcc/testsuite/gcc.dg/tree-ssa/shift-drops-bitop-1.c
> @@ -0,0 +1,22 @@
> +/* { dg-do compile } */
> +/* { dg-options "-O2 -fdump-tree-original -fdump-tree-optimized" } */
> +
> +/* Neither an inclusive nor an exclusive or can carry, so an operand who=
se
> +   set bits all lie below the shift count contributes nothing.  */
> +
> +int f1 (int a, int b) { return (a ^ (b & 1)) >> 1; }
> +unsigned f2 (unsigned a, unsigned b) { return (a | (b & 7)) >> 3; }
> +long f3 (long a, int c) { return (a ^ (long) (c !=3D 0)) >> 1; }
> +
> +/* GENERIC folding must preserve evaluation of the discarded operand.  *=
/
> +int side;
> +int f4 (int a, int b) { return (a ^ ((side++, b) & 1)) >> 1; }
> +
> +/* Bit 1 of the mask survives the shift, so the exclusive or stays.  */
> +int keep (int a, int b) { return (a ^ (b & 3)) >> 1; }
> +
> +/* { dg-final { scan-tree-dump-times " \\^ " 1 "optimized" } } */
> +/* { dg-final { scan-tree-dump-not " \\| " "optimized" } } */
> +/* { dg-final { scan-tree-dump-times " \\^ " 2 "original" } } */
> +/* { dg-final { scan-tree-dump-not " \\| " "original" } } */
> +/* { dg-final { scan-tree-dump-times "side\\+\\+" 1 "original" } } */
> --
> 2.50.1 (Apple Git-155)
>