[PATCH v2] match.pd: fold the rounded average idiom, the dual of the floor rule

The floor rule added by g:b59ff31043a turns

  ((x >> 1) + (y >> 1)) + (x & y & 1)   into   (x & y) + ((x ^ y) >> 1)

using x + y == 2 * (x & y) + (x ^ y).  The rounded-up average has the same
shape through the dual identity x + y == 2 * (x | y) - (x ^ y), so

  ((x >> 1) + (y >> 1)) + ((x | y) & 1) into   (x | y) - ((x ^ y) >> 1)

is the matching four-operation form.  This is the spelling used by the
rounding motion-compensation averages in media codecs.

For vector types this is the scalar counterpart of the .AVG_CEIL matcher
added by g:72f0b446d2c: that matcher already recognises both the
six-operation source form and exactly this minus form, so on targets with
the averaging instruction the late vector pattern still gets its
IFN_AVG_CEIL whichever spelling reaches it, and on targets without one a
vector drops from six elementwise operations to four.

The identity was checked exhaustively over every pair of 16-bit values, for
both the unsigned and the signed (arithmetic shift) case: no mismatches.

On arm the six-operation form went from five instructions to three; five
near-miss shapes (a mask of 2 rather than 1, a shift of 2, an xor in place
of the ior, a third operand, mismatched shift counts) are all left alone.

Bootstrapped on x86_64-pc-linux-gnu at trunk 95dd5ea480d with the
stage2/stage3 comparison successful, and regtested there with gcc.dg/dg.exp
and gcc.dg/tree-ssa/tree-ssa.exp: no unexpected results.  With the fold
reverted and the tests kept, the first test's shift, xor and mask scans
fail (the ior count is the same in either form); the second test is an
execution check of the identity at the extremes of both ranges and passes
either way.

Assisted-by: Claude Opus 5 (Anthropic)

gcc/ChangeLog:

	* match.pd (((x >> 1) + (y >> 1)) + ((x | y) & 1)): New pattern.

gcc/testsuite/ChangeLog:

	* gcc.dg/tree-ssa/avg-ceil-1.c: New test.
	* gcc.dg/tree-ssa/avg-ceil-2.c: New test.
	* gcc.target/aarch64/sve/pr89007-1.c: Expect the four-operation
	form of the rounded average.

Signed-off-by: Dominic P <[email protected]>
---
v2: adjust gcc.target/aarch64/sve/pr89007-1.c, whose check-function-bodies
pins the six-operation emulation of the rounded average that this fold
improves: on SVE (no URHADD before SVE2) the vectorised loop body is now
orr, eor, lsr and sub -- four operations instead of six, still with no
unpacking, which is what PR89007 is about.  pr89007-2.c (the floor form)
is byte-for-byte unchanged.

The gcov-39.c prime-paths report from the same CI run is not caused by
this patch: the .gcno files it emits for that test differ from an
unpatched compiler's at the same revision only in the four-byte stamp
field, so the number of prime paths cannot have changed; the test also
contains no rounded-average idiom.  The identical failure was reported
against an unrelated series of mine last week with the same signature.

Retested at the CI's baseline (9d59dcff40a) with an aarch64 cross: the
updated test's four checks pass, as do avg-ceil-1.c's five.

 gcc/match.pd                                  | 10 ++++
 gcc/testsuite/gcc.dg/tree-ssa/avg-ceil-1.c    | 25 +++++++++
 gcc/testsuite/gcc.dg/tree-ssa/avg-ceil-2.c    | 53 +++++++++++++++++++
 .../gcc.target/aarch64/sve/pr89007-1.c        | 11 ++--
 4 files changed, 94 insertions(+), 5 deletions(-)
 create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/avg-ceil-1.c
 create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/avg-ceil-2.c

diff --git a/gcc/match.pd b/gcc/match.pd
index 665e8eede7f..718c1f1333c 100644
--- a/gcc/match.pd
+++ b/gcc/match.pd
@@ -2069,6 +2069,16 @@ DEFINE_INT_AND_FLOAT_ROUND_FN (RINT)
 	 (bit_and (bit_and:c@3 @0 @1) integer_onep))
  (plus @3 (rshift (bit_xor @0 @1) @2)))
 
+/* ((x >> 1) + (y >> 1)) + ((x | y) & 1) -> (x | y) - ((x ^ y) >> 1).
+   The rounded-up dual of the rule above: x + y is 2 * (x | y) - (x ^ y), so
+   the average rounded towards +inf is (x | y) - ((x ^ y) >> 1), again four
+   operations instead of six.  This is the form used by the rounding
+   motion-compensation averages in media codecs.  */
+(simplify
+ (plus:c (plus (rshift @0 integer_onep@2) (rshift @1 @2))
+	 (bit_and (bit_ior:c@3 @0 @1) integer_onep))
+ (minus @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-ceil-1.c b/gcc/testsuite/gcc.dg/tree-ssa/avg-ceil-1.c
new file mode 100644
index 00000000000..bb66c4415d3
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/avg-ceil-1.c
@@ -0,0 +1,25 @@
+/* The six-operation rounded (ceiling) average should collapse to the
+   four-operation form, the dual of the floor rule:
+     ((x >> 1) + (y >> 1)) + ((x | y) & 1)  ->  (x | y) - ((x ^ y) >> 1)
+   x + y is 2 * (x | y) - (x ^ y), so halving the sum rounded up needs only
+   an ior, an xor, a shift and a subtract.  */
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-optimized" } */
+
+unsigned
+avg_ceil (unsigned x, unsigned y)
+{
+  return ((x >> 1) + (y >> 1)) + ((x | y) & 1u);
+}
+
+int
+avg_ceil_signed (int x, int y)
+{
+  return ((x >> 1) + (y >> 1)) + ((x | y) & 1);
+}
+
+/* Both shifts of the operands must be gone, leaving one shift of the xor.  */
+/* { dg-final { scan-tree-dump-times " >> 1;" 2 "optimized" } } */
+/* { dg-final { scan-tree-dump-times " \\^ " 2 "optimized" } } */
+/* { dg-final { scan-tree-dump-times " \\| " 2 "optimized" } } */
+/* { dg-final { scan-tree-dump-not " & 1;" "optimized" } } */
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/avg-ceil-2.c b/gcc/testsuite/gcc.dg/tree-ssa/avg-ceil-2.c
new file mode 100644
index 00000000000..f1ca20b49d0
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/avg-ceil-2.c
@@ -0,0 +1,53 @@
+/* Execution test for the rounded-average fold
+     ((x >> 1) + (y >> 1)) + ((x | y) & 1)  ->  (x | y) - ((x ^ y) >> 1)
+   at the extremes of the signed and unsigned ranges.  The subtraction in
+   the folded form cannot overflow: its result is the ceiling average,
+   which always lies between min (x, y) and max (x, y).  Compare against
+   the source expression evaluated in a wider type.  */
+/* { dg-do run } */
+/* { dg-options "-O2" } */
+/* { dg-require-effective-target int32plus } */
+
+#define INT_MIN (-__INT_MAX__ - 1)
+#define INT_MAX __INT_MAX__
+
+__attribute__ ((noipa)) int
+avg_ceil_signed (int x, int y)
+{
+  return ((x >> 1) + (y >> 1)) + ((x | y) & 1);
+}
+
+__attribute__ ((noipa)) unsigned
+avg_ceil_unsigned (unsigned x, unsigned y)
+{
+  return ((x >> 1) + (y >> 1)) + ((x | y) & 1u);
+}
+
+int
+main (void)
+{
+  static const int sv[] = { INT_MIN, INT_MIN + 1, -3, -2, -1, 0, 1, 2, 3,
+			    INT_MAX - 1, INT_MAX };
+  static const unsigned uv[] = { 0, 1, 2, 3, 0x7ffffffe, 0x7fffffff,
+				 0x80000000u, 0xfffffffeu, 0xffffffffu };
+  unsigned i, j;
+
+  for (i = 0; i < sizeof sv / sizeof sv[0]; i++)
+    for (j = 0; j < sizeof sv / sizeof sv[0]; j++)
+      {
+	long long x = sv[i], y = sv[j];
+	long long ref = ((x >> 1) + (y >> 1)) + ((x | y) & 1);
+	if (avg_ceil_signed (sv[i], sv[j]) != (int) ref)
+	  __builtin_abort ();
+      }
+
+  for (i = 0; i < sizeof uv / sizeof uv[0]; i++)
+    for (j = 0; j < sizeof uv / sizeof uv[0]; j++)
+      {
+	unsigned long long x = uv[i], y = uv[j];
+	unsigned long long ref = ((x >> 1) + (y >> 1)) + ((x | y) & 1);
+	if (avg_ceil_unsigned (uv[i], uv[j]) != (unsigned) ref)
+	  __builtin_abort ();
+      }
+  return 0;
+}
diff --git a/gcc/testsuite/gcc.target/aarch64/sve/pr89007-1.c b/gcc/testsuite/gcc.target/aarch64/sve/pr89007-1.c
index d65aa94a52a..c34c2b463af 100644
--- a/gcc/testsuite/gcc.target/aarch64/sve/pr89007-1.c
+++ b/gcc/testsuite/gcc.target/aarch64/sve/pr89007-1.c
@@ -7,15 +7,16 @@ unsigned char dst[N];
 unsigned char in1[N];
 unsigned char in2[N];
 
+/* The rounded average is computed through the four-operation identity
+   x + y = 2 * (x | y) - (x ^ y), so the loop body is an orr, an eor, a
+   shift and a subtract -- and still no widening.  */
 /*
 **  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)
 **	orr	(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), \2\.b, #1
+**	sub	z[0-9]+\.b, \1\.b, \3
 **	...
 */
 void
-- 
2.55.0