match.pd: drop an operand discarded by a shift
Checks
| Context |
Check |
Description |
| linaro-tcwg-bot/tcwg_simplebootstrap_build--master-arm-bootstrap |
success
|
Build passed
|
| linaro-tcwg-bot/tcwg_simplebootstrap_build--master-aarch64-bootstrap |
success
|
Build passed
|
Commit Message
From: Kyrylo Tkachov <ktkachov@nvidia.com>
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 <ktkachov@nvidia.com>
---
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
Comments
On Tue, Aug 4, 2026 at 2:47 AM <ktkachov@nvidia.com> wrote:
>
> From: Kyrylo Tkachov <ktkachov@nvidia.com>
>
> 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 <ktkachov@nvidia.com>
> ---
> 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)
>
@@ -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)
+ (if (INTEGRAL_TYPE_P (type)
+ && wi::ltu_p (wi::to_wide (@2), element_precision (type))
+ && (tree_nonzero_bits (@1)
+ & wi::mask (tree_to_uhwi (@2), true, element_precision (type))) == 0)
+ (rshift @0 @2))))
#if GIMPLE
/* (X >> C1) << (C1 + C2) -> X << C2 if the low C1 bits of X are zero. */
(simplify
new file mode 100644
@@ -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" } } */