[gcc r17-3054] match.pd: fold the overflow-free average idiom

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