[v2] match.pd: drop an operand discarded by a shift
Checks
| Context |
Check |
Description |
| linaro-tcwg-bot/tcwg_simplebootstrap_build--master-aarch64-bootstrap |
success
|
Build passed
|
| linaro-tcwg-bot/tcwg_gcc_build--master-aarch64 |
success
|
Build passed
|
| linaro-tcwg-bot/tcwg_simplebootstrap_build--master-arm-bootstrap |
success
|
Build passed
|
| linaro-tcwg-bot/tcwg_gcc_build--master-arm |
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.
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 | 15 +++++++++++
.../gcc.dg/tree-ssa/shift-drops-bitop-1.c | 26 +++++++++++++++++++
2 files changed, 41 insertions(+)
create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/shift-drops-bitop-1.c
Comments
On 8/5/2026 5:40 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.
>
> 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.
GIven this can fire for !GIMPLE and we totally drop the Y term, don't we
need to either verify Y has no side effects or guard the transformation
on GIMPLE?
Jeff
On Fri, Aug 7, 2026 at 9:52 AM Jeffrey Law <jeffrey.law@oss.qualcomm.com> wrote:
>
>
>
> On 8/5/2026 5:40 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.
> >
> > 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.
> GIven this can fire for !GIMPLE and we totally drop the Y term, don't we
> need to either verify Y has no side effects or guard the transformation
> on GIMPLE?
In the case of generic, genmatch already adds the needed code to deal
with the dropping and/or side effects.
The genmatch code which does this starts with the following comment:
```
/* Search for captures not used in the result expression and dependent
on TREE_SIDE_EFFECTS emit omit_one_operand. */
```
The only case where a match pattern needs to do something manual is if
you make a conditional expression unconditional; usually inside a
COND_EXPR (but might be also from THRUTH_*IF_EXPR too). There is
expr_no_side_effects_p for that check.
Yes there are some match patterns that check TREE_SIDE_EFFECTS
explicitly but that is not needed; I noticed the majority of them were
added by Roger so it might have been out of habit or not realizing
gnematch handles that case already.
Thanks,
Andrea
>
> Jeff
On 8/7/2026 11:16 AM, Andrea Pinski wrote:
> On Fri, Aug 7, 2026 at 9:52 AM Jeffrey Law <jeffrey.law@oss.qualcomm.com> wrote:
>>
>>
>> On 8/5/2026 5:40 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.
>>>
>>> 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.
>> GIven this can fire for !GIMPLE and we totally drop the Y term, don't we
>> need to either verify Y has no side effects or guard the transformation
>> on GIMPLE?
> In the case of generic, genmatch already adds the needed code to deal
> with the dropping and/or side effects.
>
> The genmatch code which does this starts with the following comment:
> ```
> /* Search for captures not used in the result expression and dependent
> on TREE_SIDE_EFFECTS emit omit_one_operand. */
> ```
>
> The only case where a match pattern needs to do something manual is if
> you make a conditional expression unconditional; usually inside a
> COND_EXPR (but might be also from THRUTH_*IF_EXPR too). There is
> expr_no_side_effects_p for that check.
> Yes there are some match patterns that check TREE_SIDE_EFFECTS
> explicitly but that is not needed; I noticed the majority of them were
> added by Roger so it might have been out of habit or not realizing
> gnematch handles that case already.
Thanks for the clarification. In that case, OK for the trunk.
jeff
@@ -5021,6 +5021,21 @@ 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 @0 @1) INTEGER_CST@2)
+ (if (INTEGRAL_TYPE_P (type)
+ && tree_fits_uhwi_p (@2)
+ && tree_to_uhwi (@2) < TYPE_PRECISION (type))
+ (with { wide_int 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 (@0) & mask) == 0)
+ (rshift @1 @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,26 @@
+/* { 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; }
+unsigned f5 (unsigned a, unsigned b)
+{
+ return ((a * 3) ^ ((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\\+\\+" 2 "original" } } */