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
