On Tue, Aug 4, 2026 at 4:07 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]>
> ---
> 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))
Note this is not a full review; just something I Noticed:
The outer bit_and does not need `:c` as constants are always in the
last operand.
> + (plus @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-1.c
> b/gcc/testsuite/gcc.dg/tree-ssa/avg-1.c
> new file mode 100644
> index 00000000000..d1fde110a74
> --- /dev/null
> +++ b/gcc/testsuite/gcc.dg/tree-ssa/avg-1.c
> @@ -0,0 +1,27 @@
> +/* { dg-do compile } */
> +/* { dg-options "-O2 -fdump-tree-optimized" } */
> +
> +/* ((x >> 1) + (y >> 1)) + (x & y & 1) is the average of x and y without
> + overflow. It must fold to (x & y) + ((x ^ y) >> 1), which needs three
> + operations instead of five. */
> +
> +int
> +f (int a, int b)
> +{
> + return ((a >> 1) + (b >> 1)) + (a & b & 1);
> +}
> +
> +unsigned
> +g (unsigned a, unsigned b)
> +{
> + return (a & b & 1) + ((a >> 1) + (b >> 1));
> +}
> +
> +long
> +h (long a, long b)
> +{
> + return ((a >> 1) + (b >> 1)) + (1 & b & a);
> +}
> +
> +/* { dg-final { scan-tree-dump-times " \\^ " 3 "optimized" } } */
> +/* { dg-final { scan-tree-dump-not " & 1;" "optimized" } } */
> diff --git a/gcc/testsuite/gcc.target/aarch64/sve/pr89007-2.c
> b/gcc/testsuite/gcc.target/aarch64/sve/pr89007-2.c
> index 1de44df96c9..26f00dc2258 100644
> --- a/gcc/testsuite/gcc.target/aarch64/sve/pr89007-2.c
> +++ b/gcc/testsuite/gcc.target/aarch64/sve/pr89007-2.c
> @@ -10,12 +10,10 @@ unsigned char in2[N];
> /*
> ** 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)
> -** and (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, z[0-9]+\.b, #1
> +** and z[0-9]+\.d, z[0-9]+\.d, z[0-9]+\.d
> +** add z[0-9]+\.b, z[0-9]+\.b, z[0-9]+\.b
> ** ...
> */
> void
> --
> 2.50.1 (Apple Git-155)
>
