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

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