[PATCH][v2] match: fold the sum of a min/max pair

From: Kyrylo Tkachov <[email protected]>

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.  It also holds for floating
point when reassociation is enabled and signed zeros and traps are not
honoured.

  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.
	* gcc.dg/tree-ssa/minmax-sum-fp-1.c: Likewise.
	* gcc.dg/tree-ssa/minmax-sum-fp-2.c: Likewise.
	* g++.target/aarch64/minmax-sum-1.C: Likewise.

Signed-off-by: Kyrylo Tkachov <[email protected]>
---
 gcc/match.pd                                   | 15 +++++++++++++++
 .../g++.target/aarch64/minmax-sum-1.C          | 17 +++++++++++++++++
 gcc/testsuite/gcc.dg/tree-ssa/minmax-sum-1.c   | 18 ++++++++++++++++++
 .../gcc.dg/tree-ssa/minmax-sum-fp-1.c          | 15 +++++++++++++++
 .../gcc.dg/tree-ssa/minmax-sum-fp-2.c          | 10 ++++++++++
 5 files changed, 75 insertions(+)
 create mode 100644 gcc/testsuite/g++.target/aarch64/minmax-sum-1.C
 create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/minmax-sum-1.c
 create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/minmax-sum-fp-1.c
 create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/minmax-sum-fp-2.c

diff --git a/gcc/match.pd b/gcc/match.pd
index 728fa8a8d63..35cc995ebf9 100644
--- a/gcc/match.pd
+++ b/gcc/match.pd
@@ -2051,6 +2051,21 @@ 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 @0 @1))
+  (if ((ANY_INTEGRAL_TYPE_P (type)
+	&& !TYPE_OVERFLOW_SANITIZED (type) && !TYPE_OVERFLOW_TRAPS (type))
+	|| (FLOAT_TYPE_P (type)
+	    && flag_associative_math
+	    && !HONOR_SIGNED_ZEROS (type)
+	    && !flag_trapping_math))
+   (maxmin @0 @1))))
+
 /* (x | y) - y -> (x & ~y) */
 (simplify
  (minus (bit_ior:cs @0 @1) @1)
diff --git a/gcc/testsuite/g++.target/aarch64/minmax-sum-1.C b/gcc/testsuite/g++.target/aarch64/minmax-sum-1.C
new file mode 100644
index 00000000000..d3df15e4693
--- /dev/null
+++ b/gcc/testsuite/g++.target/aarch64/minmax-sum-1.C
@@ -0,0 +1,17 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-optimized" } */
+
+/* Integer vector forms use the same simplification as scalar integers.  */
+
+typedef int v4si __attribute__((vector_size (16)));
+typedef unsigned int v4ui __attribute__((vector_size (16)));
+
+v4si f1 (v4si a, v4si b) { v4si m = a < b ? a : b; return (a + b) - m; }
+v4si f2 (v4si a, v4si b) { v4si m = a < b ? b : a; return (a + b) - m; }
+v4ui f3 (v4ui a, v4ui b) { v4ui m = a < b ? a : b; return (a + b) - m; }
+v4ui f4 (v4ui a, v4ui b) { v4ui m = a < b ? b : a; return (a + b) - m; }
+
+/* { 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" } } */
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" } } */
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/minmax-sum-fp-1.c b/gcc/testsuite/gcc.dg/tree-ssa/minmax-sum-fp-1.c
new file mode 100644
index 00000000000..42a5ff7ce25
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/minmax-sum-fp-1.c
@@ -0,0 +1,15 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -fassociative-math -fno-signed-zeros -fno-trapping-math -ffinite-math-only -fdump-tree-optimized" } */
+
+/* Reassociation permits the sum and subtraction to cancel for floating
+   point MIN_EXPR and MAX_EXPR.  */
+
+float f1 (float a, float b) { float m = a < b ? a : b; return (a + b) - m; }
+float f2 (float a, float b) { float m = a < b ? b : a; return (a + b) - m; }
+double f3 (double a, double b) { double m = a < b ? a : b; return (a + b) - m; }
+double f4 (double a, double b) { double m = a < b ? b : a; return (a + b) - m; }
+
+/* { 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" } } */
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/minmax-sum-fp-2.c b/gcc/testsuite/gcc.dg/tree-ssa/minmax-sum-fp-2.c
new file mode 100644
index 00000000000..58e92a049d5
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/minmax-sum-fp-2.c
@@ -0,0 +1,10 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-optimized" } */
+
+/* Strict floating-point arithmetic does not permit reassociation.  */
+
+float f1 (float a, float b) { float m = a < b ? a : b; return (a + b) - m; }
+double f2 (double a, double b) { double m = a < b ? b : a; return (a + b) - m; }
+
+/* { dg-final { scan-tree-dump-times " \\+ " 2 "optimized" } } */
+/* { dg-final { scan-tree-dump-times " - " 2 "optimized" } } */
-- 
2.50.1 (Apple Git-155)