[PATCH] match.pd: fold the overflow-free average idiom

From: Kyrylo Tkachov <[email protected]>

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 is three operations instead of five.  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 five-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 that do
have a halving add are unaffected: IFN_AVG_FLOOR is recognised on the
scalar form before this rule can see anything, so NEON and SVE2 keep
their uhadd.

Do not commute the identical inner shift forms.  Reuse the matched
conjunction in the result.

Bootstrapped and tested on aarch64-none-linux-gnu.
Ok for trunk?
Thanks,
Kyrill

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]>
---
 gcc/match.pd                                  |  9 +++++++
 gcc/testsuite/gcc.dg/tree-ssa/avg-1.c         | 27 +++++++++++++++++++
 .../gcc.target/aarch64/sve/pr89007-2.c        | 10 +++----
 3 files changed, 40 insertions(+), 6 deletions(-)
 create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/avg-1.c

diff --git a/gcc/match.pd b/gcc/match.pd
index 0d58ff2c115..45811d10341 100644
--- a/gcc/match.pd
+++ b/gcc/match.pd
@@ -2181,6 +2181,15 @@ DEFINE_INT_AND_FLOAT_ROUND_FN (RINT)
       && wi::to_widest (@2) == 1)
   (plus @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 three
+   operations instead of five.  */
+(simplify
+ (plus:c (plus (rshift @0 integer_onep@2) (rshift @1 @2))
+	 (bit_and:c (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 00000000000..d1fde110a74
--- /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 1de44df96c9..26f00dc2258 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
-- 
2.50.1 (Apple Git-155)