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

On Tue, Aug 4, 2026 at 4:07=E2=80=AFAM <[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 simplificat=
ion
>         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 bo=
dy.
>
> 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) =3D=3D 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 thre=
e
> +   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/tests=
uite/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)
>