On 8/4/2026 5:06 AM, [email protected] wrote:
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]>
So you mention that this should not affect targets with averaging. It
may not be that simple. If we consider RISC-V, it does not have a
scalar averaging instruction. So I suspect this pattern would fire.
But RISC-V does have a vector averaging instruction. We definitely
want to continue to support vaadd[u], so the question is whether or not
this pattern might inhibit discovery of a vector averaging. IIRC it
shows up in pixel_avg (big surprise). I did extract pixel_avg and tried
it on RISC-V with your patch. It's still using the vaadd[u]
instruction, so at least the most compelling case from spec2017 is still
doing the right thing.
---
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)))
+
So I count the original sequence as 6 operations. 2 right shifts, 2
logical ands and 2 plus operations. The optimized forms I count as 4
operations (logical and, logical xor, shift, plus). So you may need a
comment update.
So update the comment if necessary. OK for the trunk.
jeff
