https://gcc.gnu.org/g:b59ff31043ae6b1a5ce8582dd375e2ef9a938d79
commit r17-3054-gb59ff31043ae6b1a5ce8582dd375e2ef9a938d79 Author: Kyrylo Tkachov <[email protected]> Date: Fri Aug 7 07:36:58 2026 +0200 match.pd: fold the overflow-free average idiom The average of two integers is often written so that it cannot overflow: ((x >> 1) + (y >> 1)) + (x & y & 1) Since x + y is 2 * (x & y) + (x ^ y), the same value is (x & y) + ((x ^ y) >> 1), which uses four operations instead of six. Both forms are exact for signed and unsigned types, and neither can overflow, because the result is always between the two inputs. int f (int a, int b) { return ((a >> 1) + (b >> 1)) + (a & b & 1); } aarch64 -O2 before: lsr w2, w1, 1 add w2, w2, w0, lsr 1 and w0, w0, w1 and w0, w0, 1 add w0, w2, w0 after: eor w2, w0, w1 and w0, w0, w1 add w0, w0, w2, lsr 1 The vectoriser emits the six-operation form itself when the target has no halving add, so the same reduction applies there. On SVE without SVE2 the loop body of pr89007-2.c goes from six vector operations to four, and that test is updated to the shorter sequence. Targets where IFN_AVG_FLOOR is recognised on the scalar form before this rule are unaffected, so NEON and SVE2 keep their uhadd. RISC-V also keeps its vector vaadd and vaaddu instructions for the pixel_avg case. Do not commute the identical inner shift forms. Reuse the matched conjunction in the result. Bootstrapped and tested on aarch64-none-linux-gnu. gcc/ChangeLog: * match.pd (((x >> 1) + (y >> 1)) + (x & y & 1)): New simplification to (x & y) + ((x ^ y) >> 1). gcc/testsuite/ChangeLog: * gcc.dg/tree-ssa/avg-1.c: New test. * gcc.target/aarch64/sve/pr89007-2.c: Update the expected loop body. Signed-off-by: Kyrylo Tkachov <[email protected]> Diff: --- gcc/match.pd | 9 ++++++++ gcc/testsuite/gcc.dg/tree-ssa/avg-1.c | 27 ++++++++++++++++++++++++ gcc/testsuite/gcc.target/aarch64/sve/pr89007-2.c | 10 ++++----- 3 files changed, 40 insertions(+), 6 deletions(-) diff --git a/gcc/match.pd b/gcc/match.pd index 62cc01380bcc..a2a48e1b4753 100644 --- a/gcc/match.pd +++ b/gcc/match.pd @@ -1986,6 +1986,15 @@ DEFINE_INT_AND_FLOAT_ROUND_FN (RINT) (op:c (bit_and @0 @1) (bit_xor @0 @1)) (bit_ior @0 @1))) +/* ((x >> 1) + (y >> 1)) + (x & y & 1) -> (x & y) + ((x ^ y) >> 1). + Both are the average of x and y computed without overflowing, since + x + y is 2 * (x & y) + (x ^ y), but the second form needs four + operations instead of six. */ +(simplify + (plus:c (plus (rshift @0 integer_onep@2) (rshift @1 @2)) + (bit_and (bit_and:c@3 @0 @1) integer_onep)) + (plus @3 (rshift (bit_xor @0 @1) @2))) + /* (x & y) + (x | y) -> x + y */ (simplify (plus:c (bit_and @0 @1) (bit_ior @0 @1)) diff --git a/gcc/testsuite/gcc.dg/tree-ssa/avg-1.c b/gcc/testsuite/gcc.dg/tree-ssa/avg-1.c new file mode 100644 index 000000000000..d1fde110a746 --- /dev/null +++ b/gcc/testsuite/gcc.dg/tree-ssa/avg-1.c @@ -0,0 +1,27 @@ +/* { dg-do compile } */ +/* { dg-options "-O2 -fdump-tree-optimized" } */ + +/* ((x >> 1) + (y >> 1)) + (x & y & 1) is the average of x and y without + overflow. It must fold to (x & y) + ((x ^ y) >> 1), which needs three + operations instead of five. */ + +int +f (int a, int b) +{ + return ((a >> 1) + (b >> 1)) + (a & b & 1); +} + +unsigned +g (unsigned a, unsigned b) +{ + return (a & b & 1) + ((a >> 1) + (b >> 1)); +} + +long +h (long a, long b) +{ + return ((a >> 1) + (b >> 1)) + (1 & b & a); +} + +/* { dg-final { scan-tree-dump-times " \\^ " 3 "optimized" } } */ +/* { dg-final { scan-tree-dump-not " & 1;" "optimized" } } */ diff --git a/gcc/testsuite/gcc.target/aarch64/sve/pr89007-2.c b/gcc/testsuite/gcc.target/aarch64/sve/pr89007-2.c index 1de44df96c92..26f00dc2258b 100644 --- a/gcc/testsuite/gcc.target/aarch64/sve/pr89007-2.c +++ b/gcc/testsuite/gcc.target/aarch64/sve/pr89007-2.c @@ -10,12 +10,10 @@ unsigned char in2[N]; /* ** foo: ** ... -** lsr (z[0-9]+\.b), z[0-9]+\.b, #1 -** lsr (z[0-9]+\.b), z[0-9]+\.b, #1 -** add (z[0-9]+\.b), (\1, \2|\2, \1) -** and (z[0-9]+)\.d, z[0-9]+\.d, z[0-9]+\.d -** and (z[0-9]+\.b), \5\.b, #0x1 -** add z[0-9]+\.b, (\3, \6|\6, \3) +** eor z[0-9]+\.d, z[0-9]+\.d, z[0-9]+\.d +** lsr z[0-9]+\.b, z[0-9]+\.b, #1 +** and z[0-9]+\.d, z[0-9]+\.d, z[0-9]+\.d +** add z[0-9]+\.b, z[0-9]+\.b, z[0-9]+\.b ** ... */ void
