Re: [PATCH] [tree-optimization] Optimize two patterns with three xors.

Re: [PATCH] [tree-optimization] Optimize two patterns with three xors.

[Eugene Rozenfeld]

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

Thank you for the review Richard!

I re-worked the patch based on your suggestions (attached).
I made the change to reuse the first bit_xor in both patterns and I added :s to the last xor in the first pattern.
For the second pattern I didn't add :s because I think the simplification is beneficial even if the second or third bit_xor has more than one use since we are simplifying them to just a single operand (@2). If that is incorrect, please explain why.

Eugene

-----Original Message-----
From: Richard Biener <richard.guenther@gmail.com> 
Sent: Monday, November 16, 2020 4:11 AM
To: Eugene Rozenfeld <Eugene.Rozenfeld@microsoft.com>
Cc: gcc-patches@gcc.gnu.org
Subject: Re: [PATCH] [tree-optimization] Optimize two patterns with three xors.

On Thu, Nov 12, 2020 at 2:53 AM Eugene Rozenfeld via Gcc-patches <gcc-patches@gcc.gnu.org> wrote:
>
> Simplify (a ^ b) & ((b ^ c) ^ a) --> (a ^ b) & ~c.
>
> int f(int a, int b, int c)
> {
>     return (a ^ b) & ((b ^ c) ^ a);
> }
>
> Code without the patch:
> mov    eax,edx
> xor    eax,esi
> xor    eax,edi
> xor    edi,esi
> and    eax,edi
> ret
>
> Code with the patch:
> xor    edi,esi
> andn   eax,edx,edi
> ret
>
> Simplify (a ^ b) | ((b ^ c) ^ a) --> (a ^ b) | c.
> int g(int a, int b, int c)
> {
>     return (a ^ b) | ((b ^ c) ^ a);
> }
>
> Code without the patch:
> mov    eax,edx
> xor    eax,esi
> xor    eax,edi
> xor    edi,esi
> or     eax,edi
> ret
>
> Code with the patch:
> xor    edi,esi
> mov    eax,edi
> or     eax,edx
> ret
>
> This fixes PR96671.

+/* (a ^ b) & ((b ^ c) ^ a) --> (a ^ b) & ~c */ (simplify  (bit_and:c 
+(bit_xor:c @0 @1) (bit_xor:cs (bit_xor:c @1 @2) @0))  (bit_and (bit_xor 
+@0 @1) (bit_not @2)))

you should be able to re-use the first bit_xor by doing

+/* (a ^ b) & ((b ^ c) ^ a) --> (a ^ b) & ~c */ (simplify  (bit_and:c 
+(bit_xor:c@3 @0 @1) (bit_xor:cs (bit_xor:c @1 @2) @0))  (bit_and @3 
+(bit_not @2)))

For completeness the last (bit_xor:c @1 @2) should also have a :s

+/* (a ^ b) | ((b ^ c) ^ a) --> (a ^ b) | c */ (simplify  (bit_ior:c 
+(bit_xor:c @0 @1) (bit_xor:c (bit_xor:c @1 @2) @0))  (bit_ior (bit_xor 
+@0 @1) @2))

completely misses :s here and the same comment about the re-use of the existing xor applies.

Otherwise looks OK to me, sorry for the delay.

Thanks,
Richard.

> Tested on x86_64-pc-linux-gnu.
>

[-- Attachment #2: 0001-Optimize-two-patterns-with-three-xors.patch --]
[-- Type: application/octet-stream, Size: 1106 bytes --]

From 8769f7e720219457d7e708d04981231c0d4501f5 Mon Sep 17 00:00:00 2001
From: Eugene Rozenfeld <erozen@microsoft.com>
Date: Wed, 11 Nov 2020 17:24:48 -0800
Subject: [PATCH] Optimize two patterns with three xors.

Simplify (a ^ b) & ((b ^ c) ^ a) to (a ^ b) & ~c.
Simplify (a ^ b) | ((b ^ c) ^ a) to (a ^ b) | c.
This fixes PR96671.

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

diff --git a/gcc/match.pd b/gcc/match.pd
index 349eab61d6b..1dd05c4c2a3 100644
--- a/gcc/match.pd
+++ b/gcc/match.pd
@@ -901,6 +901,16 @@ DEFINE_INT_AND_FLOAT_ROUND_FN (RINT)
  (bit_not (bit_ior:cs (bit_not @0) @1))
  (bit_and @0 (bit_not @1)))
 
+/* (a ^ b) & ((b ^ c) ^ a) --> (a ^ b) & ~c */
+(simplify
+ (bit_and:c (bit_xor:c@3 @0 @1) (bit_xor:cs (bit_xor:cs @1 @2) @0))
+ (bit_and @3 (bit_not @2)))
+
+/* (a ^ b) | ((b ^ c) ^ a) --> (a ^ b) | c */
+(simplify
+ (bit_ior:c (bit_xor:c@3 @0 @1) (bit_xor:c (bit_xor:c @1 @2) @0))
+ (bit_ior @3 @2))
+
 /* Simplify (~X & Y) to X ^ Y if we know that (X & ~Y) is 0.  */
 #if GIMPLE
 (simplify
-- 
2.17.1

Re: [PATCH] [tree-optimization] Optimize two patterns with three xors.

[Richard Biener]

On Tue, Nov 17, 2020 at 3:19 AM Eugene Rozenfeld
<Eugene.Rozenfeld@microsoft.com> wrote:
>
> Thank you for the review Richard!
>
> I re-worked the patch based on your suggestions (attached).
> I made the change to reuse the first bit_xor in both patterns and I added :s to the last xor in the first pattern.
> For the second pattern I didn't add :s because I think the simplification is beneficial even if the second or third bit_xor has more than one use since we are simplifying them to just a single operand (@2). If that is incorrect, please explain why.

Ah, true, that's correct.

The patch is OK.

Thanks,
Richard.

> Eugene
>
> -----Original Message-----
> From: Richard Biener <richard.guenther@gmail.com>
> Sent: Monday, November 16, 2020 4:11 AM
> To: Eugene Rozenfeld <Eugene.Rozenfeld@microsoft.com>
> Cc: gcc-patches@gcc.gnu.org
> Subject: Re: [PATCH] [tree-optimization] Optimize two patterns with three xors.
>
> On Thu, Nov 12, 2020 at 2:53 AM Eugene Rozenfeld via Gcc-patches <gcc-patches@gcc.gnu.org> wrote:
> >
> > Simplify (a ^ b) & ((b ^ c) ^ a) --> (a ^ b) & ~c.
> >
> > int f(int a, int b, int c)
> > {
> >     return (a ^ b) & ((b ^ c) ^ a);
> > }
> >
> > Code without the patch:
> > mov    eax,edx
> > xor    eax,esi
> > xor    eax,edi
> > xor    edi,esi
> > and    eax,edi
> > ret
> >
> > Code with the patch:
> > xor    edi,esi
> > andn   eax,edx,edi
> > ret
> >
> > Simplify (a ^ b) | ((b ^ c) ^ a) --> (a ^ b) | c.
> > int g(int a, int b, int c)
> > {
> >     return (a ^ b) | ((b ^ c) ^ a);
> > }
> >
> > Code without the patch:
> > mov    eax,edx
> > xor    eax,esi
> > xor    eax,edi
> > xor    edi,esi
> > or     eax,edi
> > ret
> >
> > Code with the patch:
> > xor    edi,esi
> > mov    eax,edi
> > or     eax,edx
> > ret
> >
> > This fixes PR96671.
>
> +/* (a ^ b) & ((b ^ c) ^ a) --> (a ^ b) & ~c */ (simplify  (bit_and:c
> +(bit_xor:c @0 @1) (bit_xor:cs (bit_xor:c @1 @2) @0))  (bit_and (bit_xor
> +@0 @1) (bit_not @2)))
>
> you should be able to re-use the first bit_xor by doing
>
> +/* (a ^ b) & ((b ^ c) ^ a) --> (a ^ b) & ~c */ (simplify  (bit_and:c
> +(bit_xor:c@3 @0 @1) (bit_xor:cs (bit_xor:c @1 @2) @0))  (bit_and @3
> +(bit_not @2)))
>
> For completeness the last (bit_xor:c @1 @2) should also have a :s
>
> +/* (a ^ b) | ((b ^ c) ^ a) --> (a ^ b) | c */ (simplify  (bit_ior:c
> +(bit_xor:c @0 @1) (bit_xor:c (bit_xor:c @1 @2) @0))  (bit_ior (bit_xor
> +@0 @1) @2))
>
> completely misses :s here and the same comment about the re-use of the existing xor applies.
>
> Otherwise looks OK to me, sorry for the delay.
>
> Thanks,
> Richard.
>
> > Tested on x86_64-pc-linux-gnu.
> >

Re: [PATCH] [tree-optimization] Optimize two patterns with three xors.

[Jeff Law]

On 11/17/20 12:57 AM, Richard Biener via Gcc-patches wrote:
> On Tue, Nov 17, 2020 at 3:19 AM Eugene Rozenfeld
> <Eugene.Rozenfeld@microsoft.com> wrote:
>> Thank you for the review Richard!
>>
>> I re-worked the patch based on your suggestions (attached).
>> I made the change to reuse the first bit_xor in both patterns and I added :s to the last xor in the first pattern.
>> For the second pattern I didn't add :s because I think the simplification is beneficial even if the second or third bit_xor has more than one use since we are simplifying them to just a single operand (@2). If that is incorrect, please explain why.
> Ah, true, that's correct.
>
> The patch is OK.
I've installed this on the trunk.

Eugene, if you're going to contribute regularly you should probably go
ahead and get commit privs so that you can commit ACK's patches
yourself.   There should be a link to a form from this page:

https://gcc.gnu.org/gitwrite.html


Jeff

RE: [EXTERNAL] Re: [PATCH] [tree-optimization] Optimize two patterns with three xors.

[Eugene Rozenfeld]

Thank you for installing my patch Jeff!

Yes, I intend to contribute regularly. I'm working on getting copyright assignment/disclaimer paperwork approved by my employer. I'll apply for commit privs after that.

Eugene

-----Original Message-----
From: Jeff Law <law@redhat.com> 
Sent: Wednesday, November 18, 2020 11:33 AM
To: Richard Biener <richard.guenther@gmail.com>; Eugene Rozenfeld <Eugene.Rozenfeld@microsoft.com>
Cc: gcc-patches@gcc.gnu.org
Subject: [EXTERNAL] Re: [PATCH] [tree-optimization] Optimize two patterns with three xors.



On 11/17/20 12:57 AM, Richard Biener via Gcc-patches wrote:
> On Tue, Nov 17, 2020 at 3:19 AM Eugene Rozenfeld 
> <Eugene.Rozenfeld@microsoft.com> wrote:
>> Thank you for the review Richard!
>>
>> I re-worked the patch based on your suggestions (attached).
>> I made the change to reuse the first bit_xor in both patterns and I added :s to the last xor in the first pattern.
>> For the second pattern I didn't add :s because I think the simplification is beneficial even if the second or third bit_xor has more than one use since we are simplifying them to just a single operand (@2). If that is incorrect, please explain why.
> Ah, true, that's correct.
>
> The patch is OK.
I've installed this on the trunk.

Eugene, if you're going to contribute regularly you should probably go ahead and get commit privs so that you can commit ACK's patches yourself.   There should be a link to a form from this page:

https://nam06.safelinks.protection.outlook.com/?url=https%3A%2F%2Fgcc.gnu.org%2Fgitwrite.html&amp;data=04%7C01%7Ceugene.rozenfeld%40microsoft.com%7Ca31f5335968749cdfe1708d88bf8bfb2%7C72f988bf86f141af91ab2d7cd011db47%7C1%7C0%7C637413247775369684%7CUnknown%7CTWFpbGZsb3d8eyJWIjoiMC4wLjAwMDAiLCJQIjoiV2luMzIiLCJBTiI6Ik1haWwiLCJXVCI6Mn0%3D%7C1000&amp;sdata=BfQGAtU%2F8IJ8%2BRcvuNI8qKWgnC9oPFtWQhXo1RzlBTU%3D&amp;reserved=0


Jeff