Re: [PATCH] tree-optimization/103514 Missing XOR-EQ-AND Optimization

Re: [PATCH] tree-optimization/103514 Missing XOR-EQ-AND Optimization

[Marc Glisse]

+/* (a & b) ^ (a == b) -> !(a | b) */
+/* (a & b) == (a ^ b) -> !(a | b) */
+(for first_op (bit_xor eq)
+     second_op (eq bit_xor)
+ (simplify
+  (first_op:c (bit_and:c @0 @1) (second_op:c @0 @1))
+   (if (INTEGRAL_TYPE_P (TREE_TYPE (@0))
+        && types_match (TREE_TYPE (@0), TREE_TYPE (@1)))
+    (convert (bit_not (bit_ior @0 @1))))))

I don't think you need types_match, if both are operands of bit_and, their 
types must already match.

It isn't clear what the INTEGRAL_TYPE_P test is for. Your 2 
transformations don't seem that similar to me. The first one requires that 
a and b have the same type as the result of ==, so they are boolean-like. 
The second one makes sense for more general integers, but then it looks 
like it should produce (a|b)==0.

It doesn't look like we have a canonical representation between a^b and 
a!=b for booleans :-(

(sorry for the broken thread, I was automatically unsubscribed because 
mailman doesn't like greylisting)

-- 
Marc Glisse

Re: [EXTERNAL] Re: [PATCH] tree-optimization/103514 Missing XOR-EQ-AND Optimization

[Navid Rahimi]

Hi Marc, thanks for clear explanation.

Actually I have to withdraw this patch. As you noticed there are some problems with this. I was testing it yesterday, and I did realize I made mistake combining different types in this pattern.

The same approach would work only and only if the types of every operand is boolean. But if there are any integer here, then this is not going to work.

For looking at example and link to proof in each case [1].

One actual example, with the input values is like this:

(a & b) ^ (a == b) -> !(a | b)

a = 2 and b = 2,
src :
(a == b) => true
(a & b) => 2
(a & b) ^ (a == b) => (2) ^ (true) => 3 (the compiler will consider true as 1) [2].

tgt:
(a | b) => 2
!(a | b) => !(2) => false.

Which means the transformation is incorrect for other types. (Same transformation does work for bool types, so I think in my next patch I will keep the approach and will restrict it to bool types only).

1) https://compiler-explorer.com/z/h7hcohY74
2) https://eel.is/c++draft/conv.prom#6

Best wishes,
Navid.

________________________________________
From: Marc Glisse <marc.glisse@inria.fr>
Sent: Saturday, December 4, 2021 13:22
To: gcc-patches@gcc.gnu.org
Cc: Navid Rahimi
Subject: [EXTERNAL] Re: [PATCH] tree-optimization/103514 Missing XOR-EQ-AND Optimization

[You don't often get email from marc.glisse@inria.fr. Learn why this is important at http://aka.ms/LearnAboutSenderIdentification.]

+/* (a & b) ^ (a == b) -> !(a | b) */
+/* (a & b) == (a ^ b) -> !(a | b) */
+(for first_op (bit_xor eq)
+     second_op (eq bit_xor)
+ (simplify
+  (first_op:c (bit_and:c @0 @1) (second_op:c @0 @1))
+   (if (INTEGRAL_TYPE_P (TREE_TYPE (@0))
+        && types_match (TREE_TYPE (@0), TREE_TYPE (@1)))
+    (convert (bit_not (bit_ior @0 @1))))))

I don't think you need types_match, if both are operands of bit_and, their
types must already match.

It isn't clear what the INTEGRAL_TYPE_P test is for. Your 2
transformations don't seem that similar to me. The first one requires that
a and b have the same type as the result of ==, so they are boolean-like.
The second one makes sense for more general integers, but then it looks
like it should produce (a|b)==0.

It doesn't look like we have a canonical representation between a^b and
a!=b for booleans :-(

(sorry for the broken thread, I was automatically unsubscribed because
mailman doesn't like greylisting)

--
Marc Glisse

Re: [PATCH] tree-optimization/103514 Missing XOR-EQ-AND Optimization

[Jeff Law]

On 1/5/2022 1:12 PM, Navid Rahimi via Gcc-patches wrote:
> Hi GCC community,
>
> This patch will add the missed pattern described in bug 103514 [1] to the match.pd. [1] includes proof of correctness for the patch too.
>
> PR tree-optimization/103514
> 	* match.pd (a & b) ^ (a == b) -> !(a | b): New optimization.
> 	* match.pd (a & b) == (a ^ b) -> !(a | b): New optimization.
> 	* gcc.dg/tree-ssa/pr103514.c: Testcase for this optimization.
>
> 1) https://gcc.gnu.org/bugzilla/show_bug.cgi?id=103514
Note the bug was filed an fixed during stage3, review just didn't happen 
in a reasonable timeframe.

I'm going to ACK this for the trunk and go ahead and commit it for you.

Thanks for your patience,
jeff

[PATCH] tree-optimization/103514 Missing XOR-EQ-AND Optimization

[Navid Rahimi]

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

Hi GCC community,

This patch will add the missed pattern described in bug 103514 [1] to the match.pd. [1] includes proof of correctness for the patch too. 

PR tree-optimization/103514
	* match.pd (a & b) ^ (a == b) -> !(a | b): New optimization.
	* match.pd (a & b) == (a ^ b) -> !(a | b): New optimization.
	* gcc.dg/tree-ssa/pr103514.c: Testcase for this optimization.

1) https://gcc.gnu.org/bugzilla/show_bug.cgi?id=103514

Best wishes,
Navid.

[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #2: 0001-tree-optimization-103514-Missing-XOR-EQ-AND-Opt-v4.patch --]
[-- Type: text/x-patch; name="0001-tree-optimization-103514-Missing-XOR-EQ-AND-Opt-v4.patch", Size: 2163 bytes --]

From 7bc34478cc3a494bb634625281b5f03e43f210a9 Mon Sep 17 00:00:00 2001
From: Navid Rahimi <navidrahimi@microsoft.com>
Date: Wed, 1 Dec 2021 00:00:54 -0800
Subject: [PATCH] tree-optimization/103514 Missing XOR-EQ-AND Optimization

	* match.pd (a & b) ^ (a == b) -> !(a | b): New optimization.
	* match.pd (a & b) == (a ^ b) -> !(a | b): New optimization.
	* gcc.dg/tree-ssa/pr103514.c: Testcase for this optimization.
---
 gcc/match.pd                             |  8 ++++++
 gcc/testsuite/gcc.dg/tree-ssa/pr103514.c | 33 ++++++++++++++++++++++++
 2 files changed, 41 insertions(+)
 create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/pr103514.c

diff --git a/gcc/match.pd b/gcc/match.pd
index 0d7b8dd1334..df55206d2ec 100644
--- a/gcc/match.pd
+++ b/gcc/match.pd
@@ -1768,6 +1768,14 @@ DEFINE_INT_AND_FLOAT_ROUND_FN (RINT)
  (negate (nop_convert? (bit_not @0)))
  (plus (view_convert @0) { build_each_one_cst (type); }))
 
+/* (a & b) ^ (a == b) -> !(a | b) */
+/* (a & b) == (a ^ b) -> !(a | b) */
+(for first_op (bit_xor eq)
+     second_op (eq bit_xor)
+ (simplify
+  (first_op:c (bit_and:c truth_valued_p@0 truth_valued_p@1) (second_op:c @0 @1))
+    (bit_not (bit_ior @0 @1))))
+
 /* Convert ~ (A - 1) or ~ (A + -1) to -A.  */
 (simplify
  (bit_not (convert? (minus @0 integer_each_onep)))
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/pr103514.c b/gcc/testsuite/gcc.dg/tree-ssa/pr103514.c
new file mode 100644
index 00000000000..5942ad37bf0
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/pr103514.c
@@ -0,0 +1,33 @@
+/* { dg-do compile } */
+/* { dg-options "-O -fdump-tree-optimized" } */
+#include <stdbool.h>
+
+bool
+i (bool a, bool b)
+{
+     return (a & b) ^ (a == b);
+}
+
+bool
+j (bool a, bool b)
+{
+     return (a & b) == (a ^ b);
+}
+
+bool
+g (bool a, bool b)
+{
+    return (a && b) == (a ^ b); 
+}
+
+bool
+h (bool a, bool b)
+{
+     return (a && b) ^ (a == b);
+}
+
+
+/* Make sure we have removed "==" and "^" and "&". */
+/* { dg-final { scan-tree-dump-not "&" "optimized"} } */
+/* { dg-final { scan-tree-dump-not "\\^"  "optimized"} } */
+/* { dg-final { scan-tree-dump-not "==" "optimized"} } */
\ No newline at end of file
-- 
2.25.1

[PATCH] tree-optimization/103514 Missing XOR-EQ-AND Optimization

[Navid Rahimi]

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

Hi GCC community,

This patch will add the missed pattern described in bug 103514 [1] to the match.pd. Tested on x86_64 Linux. 

tree-optimization/103514 Missing XOR-EQ-AND Optimization

        * match.pd (a & b) == (a ^ b) -> !(a | b): New optimization.
        * match.pd (a & b) ^ (a == b) -> !(a | b): New optimization.

        * gcc.dg/tree-ssa/pr102232.c: Testcase for this optimization.

1) https://gcc.gnu.org/bugzilla/show_bug.cgi?id=103514

Best wishes,
Navid.

[-- Attachment #2: 0001-tree-optimization-103514-Missing-XOR-EQ-AND-Opt-v3.patch --]
[-- Type: application/octet-stream, Size: 2587 bytes --]

From 8de3e8ee91dd3a31d5b71b4b001a1ca5ed4cd9bd Mon Sep 17 00:00:00 2001
From: Navid Rahimi <navidrahimi@microsoft.com>
Date: Wed, 1 Dec 2021 00:00:54 -0800
Subject: [PATCH] tree-optimization/103514 Missing XOR-EQ-AND Optimization

	* match.pd (a & b) == (a ^ b) -> !(a | b): New optimization.
	* match.pd (a & b) ^ (a == b) -> !(a | b): New optimization.

	* gcc.dg/tree-ssa/pr102232.c: Testcase for this optimization.
---
 gcc/match.pd                             | 10 +++++
 gcc/testsuite/gcc.dg/tree-ssa/pr103514.c | 56 ++++++++++++++++++++++++
 2 files changed, 66 insertions(+)
 create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/pr103514.c

diff --git a/gcc/match.pd b/gcc/match.pd
index d467a1c4e45..2e2958f608e 100644
--- a/gcc/match.pd
+++ b/gcc/match.pd
@@ -1768,6 +1768,16 @@ DEFINE_INT_AND_FLOAT_ROUND_FN (RINT)
  (negate (nop_convert? (bit_not @0)))
  (plus (view_convert @0) { build_each_one_cst (type); }))
 
+/* (a & b) ^ (a == b) -> !(a | b) */
+/* (a & b) == (a ^ b) -> !(a | b) */
+(for first_op (bit_xor eq)
+     second_op (eq bit_xor)
+ (simplify
+  (first_op:c (bit_and:c @0 @1) (second_op:c @0 @1))
+   (if (INTEGRAL_TYPE_P (TREE_TYPE (@0))
+        && types_match (TREE_TYPE (@0), TREE_TYPE (@1)))
+    (convert (bit_not (bit_ior @0 @1))))))
+
 /* Convert ~ (A - 1) or ~ (A + -1) to -A.  */
 (simplify
  (bit_not (convert? (minus @0 integer_each_onep)))
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/pr103514.c b/gcc/testsuite/gcc.dg/tree-ssa/pr103514.c
new file mode 100644
index 00000000000..b46d033a36c
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/pr103514.c
@@ -0,0 +1,56 @@
+/* { dg-do compile } */
+/* { dg-options "-O -fdump-tree-optimized" } */
+#include <stdbool.h>
+
+bool
+b (bool a, bool b)
+{
+    return (a && b) == (a ^ b);
+}
+
+bool
+b_reverse (bool a, bool b)
+{
+     return (a && b) ^ (a == b);
+}
+
+int
+i (int a, int b)
+{
+     return (a & b) ^ (a == b);
+}
+
+int
+i_reverse (int a, int b)
+{
+     return (a & b) == (a ^ b);
+}
+
+long
+l (long a, long b)
+{
+     return (a & b) ^ (a == b);
+}
+
+long
+l_reverse (long a, long b)
+{
+     return (a & b) == (a ^ b);
+}
+
+unsigned int
+ui (unsigned int a, unsigned int b)
+{
+     return (a & b) ^ (a == b);
+}
+
+unsigned int
+ui_reverse (unsigned int a, unsigned int b)
+{
+     return (a & b) == (a ^ b);
+}
+
+/* Make sure we have removed "==" and "^" and "&". */
+/* { dg-final { scan-tree-dump-not "&" "optimized"} } */
+/* { dg-final { scan-tree-dump-not "\\^"  "optimized"} } */
+/* { dg-final { scan-tree-dump-not "==" "optimized"} } */
\ No newline at end of file
-- 
2.25.1