On Tue, Aug 4, 2026 at 2:47 AM <[email protected]> wrote:
>
> From: Kyrylo Tkachov <[email protected]>
>
> Neither an inclusive nor an exclusive or can carry, so an operand whose set
> 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 code,
> 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 keep
> 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))) ==
> 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 = wi::mask (tree_to_uhwi (@2), true, TYPE_PRECISION (type); }
(if ((tree_nonzero_bits (@1) & mask)) == 0)
(rshift @0 @2)
(if ((tree_nonzero_bits (@2) & mask)) == 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/testsuite/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 whose
> + 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 != 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)
>
