match: fold the sum of a min/max pair
Checks
| Context |
Check |
Description |
| linaro-tcwg-bot/tcwg_simplebootstrap_build--master-arm-bootstrap |
success
|
Build passed
|
| linaro-tcwg-bot/tcwg_simplebootstrap_build--master-aarch64-bootstrap |
success
|
Build passed
|
| linaro-tcwg-bot/tcwg_gcc_build--master-aarch64 |
success
|
Build passed
|
| linaro-tcwg-bot/tcwg_gcc_build--master-arm |
success
|
Build passed
|
Commit Message
From: Kyrylo Tkachov <ktkachov@nvidia.com>
The minimum and the maximum of two values add up to the sum of those
values, so subtracting one of them from the sum yields the other one.
That identity holds in modular arithmetic, so it needs only the guards
the neighbouring (x + y) - (x | y) rule uses.
int f (int a, int b) { int mn = a < b ? a : b; return (a + b) - mn; }
aarch64 -O2:
before after
cmp w1, w0 cmp w1, w0
add w2, w1, w0 csel w0, w1, w0, ge
csel w0, w1, w0, le
sub w0, w2, w0
Bootstrapped and tested on aarch64-none-linux-gnu.
Ok for trunk?
Thanks,
Kyrill
gcc/ChangeLog:
* match.pd ((x + y) - minmax (x, y)): New simplification.
gcc/testsuite/ChangeLog:
* gcc.dg/tree-ssa/minmax-sum-1.c: New test.
Signed-off-by: Kyrylo Tkachov <ktkachov@nvidia.com>
---
gcc/match.pd | 11 +++++++++++
gcc/testsuite/gcc.dg/tree-ssa/minmax-sum-1.c | 18 ++++++++++++++++++
2 files changed, 29 insertions(+)
create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/minmax-sum-1.c
Comments
On Tue, Aug 4, 2026 at 3:15 AM <ktkachov@nvidia.com> wrote:
>
> From: Kyrylo Tkachov <ktkachov@nvidia.com>
>
> The minimum and the maximum of two values add up to the sum of those
> values, so subtracting one of them from the sum yields the other one.
> That identity holds in modular arithmetic, so it needs only the guards
> the neighbouring (x + y) - (x | y) rule uses.
It holds even in non-modular (infinite) arithmetic too. That is it
will either be min == y: `x+y - y` (x) or min==x: `x+y-x` (y). So what
was min will turn into max.
>
> int f (int a, int b) { int mn = a < b ? a : b; return (a + b) - mn; }
>
> aarch64 -O2:
>
> before after
> cmp w1, w0 cmp w1, w0
> add w2, w1, w0 csel w0, w1, w0, ge
> csel w0, w1, w0, le
> sub w0, w2, w0
>
> Bootstrapped and tested on aarch64-none-linux-gnu.
> Ok for trunk?
> Thanks,
> Kyrill
>
> gcc/ChangeLog:
>
> * match.pd ((x + y) - minmax (x, y)): New simplification.
>
> gcc/testsuite/ChangeLog:
>
> * gcc.dg/tree-ssa/minmax-sum-1.c: New test.
>
> Signed-off-by: Kyrylo Tkachov <ktkachov@nvidia.com>
> ---
> gcc/match.pd | 11 +++++++++++
> gcc/testsuite/gcc.dg/tree-ssa/minmax-sum-1.c | 18 ++++++++++++++++++
> 2 files changed, 29 insertions(+)
> create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/minmax-sum-1.c
>
> diff --git a/gcc/match.pd b/gcc/match.pd
> index 72169a7a666..3c789e41493 100644
> --- a/gcc/match.pd
> +++ b/gcc/match.pd
> @@ -2048,6 +2048,17 @@ DEFINE_INT_AND_FLOAT_ROUND_FN (RINT)
> && !TYPE_SATURATING (type))
> (res @0 @1))))
>
> +/* (x + y) - min (x, y) -> max (x, y)
> + (x + y) - max (x, y) -> min (x, y)
> + The sum of the minimum and the maximum is the sum of the operands. */
> +(for minmax (min max)
> + maxmin (max min)
> + (simplify
> + (minus (plus @0 @1) (minmax:c @0 @1))
:c is not needed here since the order should be the same for both plus
and min/max.
> + (if (ANY_INTEGRAL_TYPE_P (type)
> + && !TYPE_OVERFLOW_SANITIZED (type) && !TYPE_OVERFLOW_TRAPS (type))
Since you use ANY_INTEGRAL_TYPE_P, can you add a few vector testcases?
Also should this work for fp with -ffast-math too?
> + (maxmin @0 @1))))
> +
> /* (x | y) - y -> (x & ~y) */
> (simplify
> (minus (bit_ior:cs @0 @1) @1)
> diff --git a/gcc/testsuite/gcc.dg/tree-ssa/minmax-sum-1.c b/gcc/testsuite/gcc.dg/tree-ssa/minmax-sum-1.c
> new file mode 100644
> index 00000000000..47a78abd0fa
> --- /dev/null
> +++ b/gcc/testsuite/gcc.dg/tree-ssa/minmax-sum-1.c
> @@ -0,0 +1,18 @@
> +/* { dg-do compile } */
> +/* { dg-options "-O2 -fdump-tree-optimized" } */
> +
> +/* The sum of the minimum and the maximum is the sum of the operands. */
> +
> +int f1 (int a, int b) { int mn = a < b ? a : b; return (a + b) - mn; }
> +int f2 (int a, int b) { int mx = a < b ? b : a; return (a + b) - mx; }
> +unsigned int f3 (unsigned int a, unsigned int b)
> +{
> + unsigned int mn = a < b ? a : b;
> + return (a + b) - mn;
> +}
> +long f4 (long a, long b) { long mx = a < b ? b : a; return (b + a) - mx; }
> +
> +/* { dg-final { scan-tree-dump-times "MAX_EXPR" 2 "optimized" } } */
> +/* { dg-final { scan-tree-dump-times "MIN_EXPR" 2 "optimized" } } */
> +/* { dg-final { scan-tree-dump-not " \\+ " "optimized" } } */
> +/* { dg-final { scan-tree-dump-not " - " "optimized" } } */
> --
> 2.50.1 (Apple Git-155)
>
@@ -2048,6 +2048,17 @@ DEFINE_INT_AND_FLOAT_ROUND_FN (RINT)
&& !TYPE_SATURATING (type))
(res @0 @1))))
+/* (x + y) - min (x, y) -> max (x, y)
+ (x + y) - max (x, y) -> min (x, y)
+ The sum of the minimum and the maximum is the sum of the operands. */
+(for minmax (min max)
+ maxmin (max min)
+ (simplify
+ (minus (plus @0 @1) (minmax:c @0 @1))
+ (if (ANY_INTEGRAL_TYPE_P (type)
+ && !TYPE_OVERFLOW_SANITIZED (type) && !TYPE_OVERFLOW_TRAPS (type))
+ (maxmin @0 @1))))
+
/* (x | y) - y -> (x & ~y) */
(simplify
(minus (bit_ior:cs @0 @1) @1)
new file mode 100644
@@ -0,0 +1,18 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-optimized" } */
+
+/* The sum of the minimum and the maximum is the sum of the operands. */
+
+int f1 (int a, int b) { int mn = a < b ? a : b; return (a + b) - mn; }
+int f2 (int a, int b) { int mx = a < b ? b : a; return (a + b) - mx; }
+unsigned int f3 (unsigned int a, unsigned int b)
+{
+ unsigned int mn = a < b ? a : b;
+ return (a + b) - mn;
+}
+long f4 (long a, long b) { long mx = a < b ? b : a; return (b + a) - mx; }
+
+/* { dg-final { scan-tree-dump-times "MAX_EXPR" 2 "optimized" } } */
+/* { dg-final { scan-tree-dump-times "MIN_EXPR" 2 "optimized" } } */
+/* { dg-final { scan-tree-dump-not " \\+ " "optimized" } } */
+/* { dg-final { scan-tree-dump-not " - " "optimized" } } */