* [PATCH] tree-optimization/103514 Missing XOR-EQ-AND Optimization
@ 2021-12-03 7:01 Navid Rahimi
0 siblings, 0 replies; 4+ messages in thread
From: Navid Rahimi @ 2021-12-03 7:01 UTC (permalink / raw)
To: Navid Rahimi via Gcc-patches
[-- 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
^ permalink raw reply [flat|nested] 4+ messages in thread
* Re: [PATCH] tree-optimization/103514 Missing XOR-EQ-AND Optimization
@ 2021-12-04 21:22 Marc Glisse
0 siblings, 0 replies; 4+ messages in thread
From: Marc Glisse @ 2021-12-04 21:22 UTC (permalink / raw)
To: gcc-patches
+/* (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
^ permalink raw reply [flat|nested] 4+ messages in thread
* [PATCH] tree-optimization/103514 Missing XOR-EQ-AND Optimization
@ 2022-01-05 20:12 Navid Rahimi
2022-01-28 22:14 ` Jeff Law
0 siblings, 1 reply; 4+ messages in thread
From: Navid Rahimi @ 2022-01-05 20:12 UTC (permalink / raw)
To: gcc-patches
[-- 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
^ permalink raw reply [flat|nested] 4+ messages in thread
* Re: [PATCH] tree-optimization/103514 Missing XOR-EQ-AND Optimization
2022-01-05 20:12 Navid Rahimi
@ 2022-01-28 22:14 ` Jeff Law
0 siblings, 0 replies; 4+ messages in thread
From: Jeff Law @ 2022-01-28 22:14 UTC (permalink / raw)
To: Navid Rahimi, gcc-patches
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
^ permalink raw reply [flat|nested] 4+ messages in thread
end of thread, other threads:[~2022-01-28 22:14 UTC | newest]
Thread overview: 4+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2021-12-03 7:01 [PATCH] tree-optimization/103514 Missing XOR-EQ-AND Optimization Navid Rahimi
2021-12-04 21:22 Marc Glisse
2022-01-05 20:12 Navid Rahimi
2022-01-28 22:14 ` Jeff Law
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).