[PATCH] [tree-optimization] Optimize max/min pattern with comparison

[PATCH] [tree-optimization] Optimize max/min pattern with comparison

[Eugene Rozenfeld]

[-- Attachment #1: Type: text/plain, Size: 495 bytes --]

Make the following simplifications:
    X <= MAX(X, Y) -> true
    X > MAX(X, Y) -> false
    X >= MIN(X, Y) -> true
    X < MIN(X, Y) -> false
    
This fixes PR96708.
    
Tested on x86_64-pc-linux-gnu.

bool f(int a, int b)
{
    int tmp = (a < b) ? b : a;
    return tmp >= a;
}

Code without the patch:

vmovd  xmm0,edi
vmovd  xmm1,esi
vpmaxsd xmm0,xmm0,xmm1
vmovd  eax,xmm0
cmp    eax,edi
setge  al
ret    

Code with the patch:

mov    eax,0x1
ret

Eugene

[-- Attachment #2: 0001-Optimize-max-pattern-with-comparison.patch --]
[-- Type: application/octet-stream, Size: 1272 bytes --]

From f6391c197b670b516238ac7707512c1358336520 Mon Sep 17 00:00:00 2001
From: Eugene Rozenfeld <erozen@microsoft.com>
Date: Sat, 21 Nov 2020 01:08:50 -0800
Subject: [PATCH] Optimize max pattern with comparison

Make the following simplifications:
X <= MAX(X, Y) -> true
X > MAX(X, Y) -> false
X >= MIN(X, Y) -> true
X < MIN(X, Y) -> false

This fixes PR96708.

gcc/
* match.pd : New patterns.
---
 gcc/match.pd | 10 ++++++++++
 1 file changed, 10 insertions(+)

diff --git a/gcc/match.pd b/gcc/match.pd
index cbb4bf0b32d..75237741946 100644
--- a/gcc/match.pd
+++ b/gcc/match.pd
@@ -2851,6 +2851,16 @@ DEFINE_INT_AND_FLOAT_ROUND_FN (RINT)
   (cmp (minmax @0 INTEGER_CST@1) INTEGER_CST@2)
   (comb (cmp @0 @2) (cmp @1 @2))))
 
+/* X <= MAX(X, Y) -> true
+   X > MAX(X, Y) -> false 
+   X >= MIN(X, Y) -> true
+   X < MIN(X, Y) -> false */
+(for minmax (min     min     max     max     )
+     cmp    (ge      lt      le      gt      )
+ (simplify
+  (cmp @0 (minmax:c @0 @1))
+  { constant_boolean_node (cmp == GE_EXPR || cmp == LE_EXPR, type); } ))
+
 /* Undo fancy way of writing max/min or other ?: expressions,
    like a - ((a - b) & -(a < b)), in this case into (a < b) ? b : a.
    People normally use ?: and that is what we actually try to optimize.  */
-- 
2.17.1

Re: [PATCH] [tree-optimization] Optimize max/min pattern with comparison

[Jeff Law]

On 11/25/20 3:04 PM, Eugene Rozenfeld via Gcc-patches wrote:
> Make the following simplifications:
>     X <= MAX(X, Y) -> true
>     X > MAX(X, Y) -> false
>     X >= MIN(X, Y) -> true
>     X < MIN(X, Y) -> false
>     
> This fixes PR96708.
>     
> Tested on x86_64-pc-linux-gnu.
>
> bool f(int a, int b)
> {
>     int tmp = (a < b) ? b : a;
>     return tmp >= a;
> }
>
> Code without the patch:
>
> vmovd  xmm0,edi
> vmovd  xmm1,esi
> vpmaxsd xmm0,xmm0,xmm1
> vmovd  eax,xmm0
> cmp    eax,edi
> setge  al
> ret    
>
> Code with the patch:
>
> mov    eax,0x1
> ret
>
> Eugene
>
> 0001-Optimize-max-pattern-with-comparison.patch
>
> From f6391c197b670b516238ac7707512c1358336520 Mon Sep 17 00:00:00 2001
> From: Eugene Rozenfeld <erozen@microsoft.com>
> Date: Sat, 21 Nov 2020 01:08:50 -0800
> Subject: [PATCH] Optimize max pattern with comparison
>
> Make the following simplifications:
> X <= MAX(X, Y) -> true
> X > MAX(X, Y) -> false
> X >= MIN(X, Y) -> true
> X < MIN(X, Y) -> false
>
> This fixes PR96708.
>
> gcc/
> * match.pd : New patterns.
> ---
>  gcc/match.pd | 10 ++++++++++
>  1 file changed, 10 insertions(+)
>
> diff --git a/gcc/match.pd b/gcc/match.pd
> index cbb4bf0b32d..75237741946 100644
> --- a/gcc/match.pd
> +++ b/gcc/match.pd
> @@ -2851,6 +2851,16 @@ DEFINE_INT_AND_FLOAT_ROUND_FN (RINT)
>    (cmp (minmax @0 INTEGER_CST@1) INTEGER_CST@2)
>    (comb (cmp @0 @2) (cmp @1 @2))))
>  
> +/* X <= MAX(X, Y) -> true
> +   X > MAX(X, Y) -> false 
> +   X >= MIN(X, Y) -> true
> +   X < MIN(X, Y) -> false */
> +(for minmax (min     min     max     max     )
> +     cmp    (ge      lt      le      gt      )
> + (simplify
> +  (cmp @0 (minmax:c @0 @1))
> +  { constant_boolean_node (cmp == GE_EXPR || cmp == LE_EXPR, type); } ))
Don't you need to look at the opcode (MIN vs MAX) vs CMP to know the
result?  I'd really like to see some tests for the testsuite.    In
particular I'd like to see positive tests where we should apply the
optimization and negative tests when we should not apply the optimization.

I also wonder if there's value in handling this in Ranger and/or DOM. 
Though I'd probably wait to see if fixing in match.pd is sufficient to
cover the cases I'm thinking of in Ranger & DOM.

Jeff

Re: [PATCH] [tree-optimization] Optimize max/min pattern with comparison

[Marc Glisse]

On Tue, 1 Dec 2020, Eugene Rozenfeld via Gcc-patches wrote:

> Thank you for the review Jeff.
>
> I don't need to look at the opcode to know the result. The pattern will be matched only in these 4 cases:
>
> X <= MAX(X, Y) -> true
> X > MAX(X, Y) -> false
> X >= MIN(X, Y) -> true
> X < MIN(X, Y) -> false
>
> So, the result will be true for GE_EXPR and LE_EXPR and false otherwise.

Is that true even if X is NaN?

It may be hard to hit a situation where this matters though, if we honor 
NaN, we don't build MAX_EXPR (which is unspecified).

-- 
Marc Glisse

Re: [PATCH] [tree-optimization] Optimize max/min pattern with comparison

[Jeff Law]

On 11/30/20 7:00 PM, Eugene Rozenfeld wrote:
> Thank you for the review Jeff.
>
> I don't need to look at the opcode to know the result. The pattern will be matched only in these 4 cases:
>
> X <= MAX(X, Y) -> true
> X > MAX(X, Y) -> false
> X >= MIN(X, Y) -> true
> X < MIN(X, Y) -> false
>
> So, the result will be true for GE_EXPR and LE_EXPR and false otherwise.
>
> I added two test files: one for positive cases and one for negative cases. The updated patch is attached.
Thanks.  Installed.

jeff

Re: [PATCH] [tree-optimization] Optimize max/min pattern with comparison

[Jeff Law]

On 11/30/20 7:00 PM, Eugene Rozenfeld wrote:
> Thank you for the review Jeff.
>
> I don't need to look at the opcode to know the result. The pattern will be matched only in these 4 cases:
>
> X <= MAX(X, Y) -> true
> X > MAX(X, Y) -> false
> X >= MIN(X, Y) -> true
> X < MIN(X, Y) -> false
>
> So, the result will be true for GE_EXPR and LE_EXPR and false otherwise.
>
> I added two test files: one for positive cases and one for negative cases. The updated patch is attached.
Nuts, they weren't nested FORs, sorry for mis-reading.  I'll take
another close look tomorrow.

jeff

Re: [PATCH] [tree-optimization] Optimize max/min pattern with comparison

[Eugene Rozenfeld]

[-- Attachment #1: Type: text/plain, Size: 3040 bytes --]

Thank you for the review Jeff.

I don't need to look at the opcode to know the result. The pattern will be matched only in these 4 cases:

X <= MAX(X, Y) -> true
X > MAX(X, Y) -> false
X >= MIN(X, Y) -> true
X < MIN(X, Y) -> false

So, the result will be true for GE_EXPR and LE_EXPR and false otherwise.

I added two test files: one for positive cases and one for negative cases. The updated patch is attached.

Thanks,

Eugene

-----Original Message-----
From: Jeff Law <law@redhat.com> 
Sent: Monday, November 30, 2020 9:51 AM
To: Eugene Rozenfeld <Eugene.Rozenfeld@microsoft.com>; gcc-patches@gcc.gnu.org
Subject: Re: [PATCH] [tree-optimization] Optimize max/min pattern with comparison



On 11/25/20 3:04 PM, Eugene Rozenfeld via Gcc-patches wrote:
> Make the following simplifications:
>     X <= MAX(X, Y) -> true
>     X > MAX(X, Y) -> false
>     X >= MIN(X, Y) -> true
>     X < MIN(X, Y) -> false
>     
> This fixes PR96708.
>     
> Tested on x86_64-pc-linux-gnu.
>
> bool f(int a, int b)
> {
>     int tmp = (a < b) ? b : a;
>     return tmp >= a;
> }
>
> Code without the patch:
>
> vmovd  xmm0,edi
> vmovd  xmm1,esi
> vpmaxsd xmm0,xmm0,xmm1
> vmovd  eax,xmm0
> cmp    eax,edi
> setge  al
> ret    
>
> Code with the patch:
>
> mov    eax,0x1
> ret
>
> Eugene
>
> 0001-Optimize-max-pattern-with-comparison.patch
>
> From f6391c197b670b516238ac7707512c1358336520 Mon Sep 17 00:00:00 2001
> From: Eugene Rozenfeld <erozen@microsoft.com>
> Date: Sat, 21 Nov 2020 01:08:50 -0800
> Subject: [PATCH] Optimize max pattern with comparison
>
> Make the following simplifications:
> X <= MAX(X, Y) -> true
> X > MAX(X, Y) -> false
> X >= MIN(X, Y) -> true
> X < MIN(X, Y) -> false
>
> This fixes PR96708.
>
> gcc/
> * match.pd : New patterns.
> ---
>  gcc/match.pd | 10 ++++++++++
>  1 file changed, 10 insertions(+)
>
> diff --git a/gcc/match.pd b/gcc/match.pd index 
> cbb4bf0b32d..75237741946 100644
> --- a/gcc/match.pd
> +++ b/gcc/match.pd
> @@ -2851,6 +2851,16 @@ DEFINE_INT_AND_FLOAT_ROUND_FN (RINT)
>    (cmp (minmax @0 INTEGER_CST@1) INTEGER_CST@2)
>    (comb (cmp @0 @2) (cmp @1 @2))))
>  
> +/* X <= MAX(X, Y) -> true
> +   X > MAX(X, Y) -> false 
> +   X >= MIN(X, Y) -> true
> +   X < MIN(X, Y) -> false */
> +(for minmax (min     min     max     max     )
> +     cmp    (ge      lt      le      gt      )
> + (simplify
> +  (cmp @0 (minmax:c @0 @1))
> +  { constant_boolean_node (cmp == GE_EXPR || cmp == LE_EXPR, type); } 
> +))
Don't you need to look at the opcode (MIN vs MAX) vs CMP to know the result?  I'd really like to see some tests for the testsuite.    In particular I'd like to see positive tests where we should apply the optimization and negative tests when we should not apply the optimization.

I also wonder if there's value in handling this in Ranger and/or DOM. Though I'd probably wait to see if fixing in match.pd is sufficient to cover the cases I'm thinking of in Ranger & DOM.

Jeff



[-- Attachment #2: 0001-Optimize-min-and-max-patterns-with-comparison.patch --]
[-- Type: application/octet-stream, Size: 4403 bytes --]

From 406a5133fbbd7bc7edde123397b895bb85b82342 Mon Sep 17 00:00:00 2001
From: Eugene Rozenfeld <erozen@microsoft.com>
Date: Sat, 21 Nov 2020 01:08:50 -0800
Subject: [PATCH] Optimize min and max patterns with comparison

Make the following simplifications:
X <= MAX(X, Y) -> true
X > MAX(X, Y) -> false
X >= MIN(X, Y) -> true
X < MIN(X, Y) -> false

This fixes PR96708.

gcc/
* match.pd : New patterns for comparing X with MAX(X, Y) or MIN(X, Y)

gcc/testsuite/
* gcc.dg/pr96708-positive.c: Tests for cases when the new patterns are applied
* gcc.dg/pr96708-negative.c: Tests for cases when the new patterns are not applied
---
 gcc/match.pd                            | 10 ++++++
 gcc/testsuite/gcc.dg/pr96708-negative.c | 48 +++++++++++++++++++++++++
 gcc/testsuite/gcc.dg/pr96708-positive.c | 48 +++++++++++++++++++++++++
 3 files changed, 106 insertions(+)
 create mode 100644 gcc/testsuite/gcc.dg/pr96708-negative.c
 create mode 100644 gcc/testsuite/gcc.dg/pr96708-positive.c

diff --git a/gcc/match.pd b/gcc/match.pd
index cbb4bf0b32d..75237741946 100644
--- a/gcc/match.pd
+++ b/gcc/match.pd
@@ -2851,6 +2851,16 @@ DEFINE_INT_AND_FLOAT_ROUND_FN (RINT)
   (cmp (minmax @0 INTEGER_CST@1) INTEGER_CST@2)
   (comb (cmp @0 @2) (cmp @1 @2))))
 
+/* X <= MAX(X, Y) -> true
+   X > MAX(X, Y) -> false 
+   X >= MIN(X, Y) -> true
+   X < MIN(X, Y) -> false */
+(for minmax (min     min     max     max     )
+     cmp    (ge      lt      le      gt      )
+ (simplify
+  (cmp @0 (minmax:c @0 @1))
+  { constant_boolean_node (cmp == GE_EXPR || cmp == LE_EXPR, type); } ))
+
 /* Undo fancy way of writing max/min or other ?: expressions,
    like a - ((a - b) & -(a < b)), in this case into (a < b) ? b : a.
    People normally use ?: and that is what we actually try to optimize.  */
diff --git a/gcc/testsuite/gcc.dg/pr96708-negative.c b/gcc/testsuite/gcc.dg/pr96708-negative.c
new file mode 100644
index 00000000000..91964d3b971
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/pr96708-negative.c
@@ -0,0 +1,48 @@
+/* { dg-do run } */
+/* { dg-options "-O -fdump-tree-optimized" } */
+
+#include <stdbool.h>
+
+bool __attribute__ ((noinline))
+test1 (int a, int b)
+{
+    int tmp = (a < b) ? b : a;
+    return tmp <= a;
+}
+
+bool __attribute__ ((noinline))
+test2 (int a, int b)
+{
+    int tmp = (a < b) ? b : a;
+    return tmp > a;
+}
+
+bool __attribute__ ((noinline))
+test3 (int a, int b)
+{
+    int tmp = (a > b) ? b : a;
+    return tmp >= a;
+}
+
+bool __attribute__ ((noinline))
+test4 (int a, int b)
+{
+    int tmp = (a > b) ? b : a;
+    return tmp < a;
+}
+
+int main()
+{
+    if (test1 (1, 2) || !test1 (2, 1) || 
+        !test2 (1, 2) || test2 (2, 1) ||
+        !test3 (1, 2) || test3 (2, 1) ||
+        test4 (1, 2) || !test4 (2, 1)) {
+        __builtin_abort();	
+    }
+    return 0;
+}
+
+/* { 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-times "return 0;" 1 "optimized" } } */
+/* { dg-final { scan-tree-dump-not { "return 1;" } "optimized" } } */
diff --git a/gcc/testsuite/gcc.dg/pr96708-positive.c b/gcc/testsuite/gcc.dg/pr96708-positive.c
new file mode 100644
index 00000000000..65af85344b6
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/pr96708-positive.c
@@ -0,0 +1,48 @@
+/* { dg-do run } */
+/* { dg-options "-O -fdump-tree-optimized" } */
+
+#include <stdbool.h>
+
+bool __attribute__ ((noinline))
+test1(int a, int b)
+{
+    int tmp = (a < b) ? b : a;
+    return tmp >= a;
+}
+
+bool __attribute__ ((noinline))
+test2(int a, int b)
+{
+    int tmp = (a < b) ? b : a;
+    return tmp < a;
+}
+
+bool __attribute__ ((noinline))
+test3(int a, int b)
+{
+    int tmp = (a > b) ? b : a;
+    return tmp <= a;
+}
+
+bool __attribute__ ((noinline))
+test4(int a, int b)
+{
+    int tmp = (a > b) ? b : a;
+    return tmp > a;
+}
+
+int main()
+{
+    if (!test1 (1, 2) || !test1 (2, 1) || 
+        test2 (1, 2) || test2 (2, 1) ||
+        !test3 (1, 2) || !test3 (2, 1) ||
+        test4 (1, 2) || test4 (2, 1)) {
+        __builtin_abort();	
+    }
+    return 0;
+}
+
+/* { dg-final { scan-tree-dump-times "return 0;" 3 "optimized" } } */
+/* { dg-final { scan-tree-dump-times "return 1;" 2 "optimized" } } */
+/* { dg-final { scan-tree-dump-not { "MAX_EXPR" } "optimized" } } */
+/* { dg-final { scan-tree-dump-not { "MIN_EXPR" } "optimized" } } */
-- 
2.17.1