[PATCH] 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.

Signed-off-by: Dominic P <[email protected]>
---
 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 ++++++++++++++++++++++
 3 files changed, 88 insertions(+)
 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 02684d8a302..99084158e1f 100644
--- a/gcc/match.pd
+++ b/gcc/match.pd
@@ -2049,6 +2049,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;
+}
-- 
2.55.0