https://gcc.gnu.org/g:ef09fd77d46188ec20ae2205dbf9258730668933
commit r17-3176-gef09fd77d46188ec20ae2205dbf9258730668933 Author: Kyrylo Tkachov <[email protected]> Date: Thu Jul 30 18:13:13 2026 +0200 match.pd: drop an operand discarded by a shift 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. tree_nonzero_bits also handles GENERIC expressions, and genmatch preserves the side effects of a discarded operand. Generate this rule for both GENERIC and GIMPLE. Bootstrapped and tested on aarch64-none-linux-gnu. 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. * gcc.dg/tree-ssa/shift-drops-bitop-2.c: Likewise. Signed-off-by: Kyrylo Tkachov <[email protected]> Diff: --- gcc/match.pd | 15 ++++++++++++++ .../gcc.dg/tree-ssa/shift-drops-bitop-1.c | 23 ++++++++++++++++++++++ .../gcc.dg/tree-ssa/shift-drops-bitop-2.c | 7 +++++++ 3 files changed, 45 insertions(+) diff --git a/gcc/match.pd b/gcc/match.pd index cccb607a622c..0ba97b32cb13 100644 --- a/gcc/match.pd +++ b/gcc/match.pd @@ -5106,6 +5106,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 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 000000000000..6282fa848f50 --- /dev/null +++ b/gcc/testsuite/gcc.dg/tree-ssa/shift-drops-bitop-1.c @@ -0,0 +1,23 @@ +/* { 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; +} + +/* { dg-final { scan-tree-dump-not " \\^ " "optimized" } } */ +/* { dg-final { scan-tree-dump-not " \\| " "optimized" } } */ +/* { dg-final { scan-tree-dump-times " \\^ " 1 "original" } } */ +/* { dg-final { scan-tree-dump-not " \\| " "original" } } */ +/* { dg-final { scan-tree-dump-times "side\\+\\+" 2 "original" } } */ diff --git a/gcc/testsuite/gcc.dg/tree-ssa/shift-drops-bitop-2.c b/gcc/testsuite/gcc.dg/tree-ssa/shift-drops-bitop-2.c new file mode 100644 index 000000000000..a795416a7156 --- /dev/null +++ b/gcc/testsuite/gcc.dg/tree-ssa/shift-drops-bitop-2.c @@ -0,0 +1,7 @@ +/* { dg-do compile } */ +/* { dg-options "-O2 -fdump-tree-optimized" } */ + +/* 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" } } */
