match.pd: fold the overflow-free average idiom
Checks
Commit Message
From: Kyrylo Tkachov <ktkachov@nvidia.com>
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 <ktkachov@nvidia.com>
---
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
Comments
On Tue, Aug 4, 2026 at 4:07 AM <ktkachov@nvidia.com> wrote:
>
> From: Kyrylo Tkachov <ktkachov@nvidia.com>
>
> 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 <ktkachov@nvidia.com>
> ---
> 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)
>
On 8/4/2026 5:06 AM, ktkachov@nvidia.com wrote:
> From: Kyrylo Tkachov <ktkachov@nvidia.com>
>
> 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 <ktkachov@nvidia.com>
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
@@ -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)))
+
/* (x & y) + (x | y) -> x + y */
(simplify
(plus:c (bit_and @0 @1) (bit_ior @0 @1))
new file mode 100644
@@ -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" } } */
@@ -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