[Bug tree-optimization/103514] Missing XOR-EQ-AND Optimization
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=103514 --- Comment #2 from Navid Rahimi --- Exactly. Actually in my final version I had it with single loop, but didn't know I can remove the condition too. Thanks Andrew.
[Bug tree-optimization/103514] New: Missing XOR-EQ-AND Optimization
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=103514
Bug ID: 103514
Summary: Missing XOR-EQ-AND Optimization
Product: gcc
Version: unknown
Status: UNCONFIRMED
Severity: normal
Priority: P3
Component: tree-optimization
Assignee: unassigned at gcc dot gnu.org
Reporter: navidrahimi at microsoft dot com
Target Milestone: ---
We are not optimizing &&-^-== combination, LLVM does it [1]:
// Proof of correctness https://alive2.llvm.org/ce/z/a4tuWF
bool
src (bool a, bool b)
{
return (a && b) == (a ^ b);
}
bool
tgt (bool a, bool b)
{
return !(a || b);
}
// Proof of correctness https://alive2.llvm.org/ce/z/w-iotd
bool
src (bool a, bool b)
{
return (a && b) ^ (a == b);
}
bool
tgt (bool a, bool b)
{
return !(a || b);
}
I will be sending a patch for this. This will solve it, I have to run the
testsuite and write a few tests:
/* (a && b) first_op (a second_op b) -> !(a || b) */
(for first_op (bit_xor eq)
(for second_op (bit_xor eq)
(simplify
(first_op:c (bit_and:c truth_valued_p@0 truth_valued_p@1) (second_op:c @0
@1))
(if (first_op != second_op)
(bit_not (bit_ior @0 @1))
1) https://compiler-explorer.com/z/WqTxYhG3s
[Bug tree-optimization/103509] ((-1u >> t) & b) != 0 is not optimized to b != 0
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=103509 Navid Rahimi changed: What|Removed |Added CC||navidrahimi at microsoft dot com --- Comment #1 from Navid Rahimi --- Thanks Andrew. How about we close [1] in favor of this, to make sure we have only single place to track this issue. Previous discussion about this was here [2]. 1) https://gcc.gnu.org/bugzilla/show_bug.cgi?id=98956 2) https://gcc.gnu.org/pipermail/gcc-patches/2021-November/585783.html
[Bug tree-optimization/98956] Failure to optimize out boolean left shift
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=98956 Navid Rahimi changed: What|Removed |Added CC||navidrahimi at microsoft dot com --- Comment #3 from Navid Rahimi --- I am sending a patch for this: /* cmp : ==, != */ /* ((B0 << CST) cmp 0) -> B0 cmp 0 */ (for cmp (eq ne) (simplify (cmp (lshift (convert @0) INTEGER_CST@1) integer_zerop@2) (if (TREE_CODE (TREE_TYPE (@0)) == BOOLEAN_TYPE) (cmp @0 @2 This does not apply to other arithmetic operations (at least it is not verifiable). and for cases that it does apply to other arithmetic operators, GCC already produces optimized code. You can play with the codegen I link below: Codegen: https://compiler-explorer.com/z/nj4PTrecW Proof: https://alive2.llvm.org/ce/z/jyJAoS
[Bug tree-optimization/86136] Modular multiplication optimization
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=86136 Navid Rahimi changed: What|Removed |Added CC||navidrahimi at microsoft dot com --- Comment #4 from Navid Rahimi --- We can close this bug. Transformation doesn't verify! Codegen: https://compiler-explorer.com/z/Waoz4qaz6 Proof: https://alive2.llvm.org/ce/z/5H9ahK
[Bug tree-optimization/102929] [missed optimization] two ways to rounddown-to-next-multiple
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=102929 Navid Rahimi changed: What|Removed |Added CC||navidrahimi at microsoft dot com --- Comment #2 from Navid Rahimi --- https://compiler-explorer.com/z/rMKnddh3G Seems the patch has been landed. We can close this bug.
[Bug tree-optimization/93150] (A&N) == CST1 &( ((A&M)==CST2) | ((A&O)==CST3) ) is not simplified
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=93150 --- Comment #4 from Navid Rahimi --- Although I wrote a small code to just test this optimization. But I am not able to verify this transformation [1]. https://alive2.llvm.org/ce/z/THP27D The code can be something like this but if I were able to verify the optimization, I don't see any reason why N, M, O should be constant too. /* ((x & N) == CST1) bitop1 (((x & M) == CST2) bitop2 ((x & O) == CST3)) -> ((x & (N | M)) == (CST1 | CST2)) bitopt2 ((x & (N | O)) == (CST1 | CST3)) */ (for bitop1 (bit_and bit_or) bitop2 (bit_or bit_and) (for cmp (eq ne) (simplify (bitop1:c (cmp (bit_and @0 INTEGER_CST@N) INTEGER_CST@CST1) (bitop2 (cmp (bit_and @0 INTEGER_CST@N) INTEGER_CST@CST2) (cmp (bit_and @0 INTEGER_CST@N) INTEGER_CST@CST3))) (bitop2:c (cmp (bit_and:c @0 (bit_or INTEGER_CST@N INTEGER_CST@M)) (bit_or INTEGER_CST@CST1 INTEGER_CST@CST2)) (cmp (bit_and:c @0 (bit_or INTEGER_CST@N INTEGER_CST@O)) (bit_or INTEGER_CST@CST1 INTEGER_CST@CST3))
[Bug tree-optimization/93150] (A&N) == CST1 &( ((A&M)==CST2) | ((A&O)==CST3) ) is not simplified
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=93150 --- Comment #3 from Navid Rahimi --- Thanks Dávid, that does make sense. I forgot about constant elimination. I will send a patch for this.
[Bug middle-end/101955] (signed<<
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=101955
navidrahimi changed:
What|Removed |Added
CC||navidrahimi at microsoft dot
com
--- Comment #5 from navidrahimi ---
I think rather than just
int f(int b)
{
return (((b)<<31)>>31);
}
We should optimize long too:
int f(int b)
{
return (((b)<<63)>>63);
}
1) https://compiler-explorer.com/z/dnrr54v4r
[Bug tree-optimization/96779] Failure to optimize comparison of negative version of self
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=96779 --- Comment #5 from navidrahimi --- And this is the behavior of different compilers for this optimization: https://compiler-explorer.com/z/ahdEzxxTv
[Bug tree-optimization/96779] Failure to optimize comparison of negative version of self
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=96779
navidrahimi changed:
What|Removed |Added
CC||navidrahimi at microsoft dot
com
--- Comment #4 from navidrahimi ---
Hi Andrew,
I just used your code and added a check to check whether the type is wrapping
type:
(for cmp (eq ne)
(simplify
(cmp:c @0 (negate @0))
(if (ANY_INTEGRAL_TYPE_P (TREE_TYPE (@0))
&& !TYPE_OVERFLOW_WRAPS (type))
(cmp:c @0 { build_zero_cst (TREE_TYPE(@0)); })
This should work.
[Bug tree-optimization/93150] (A&N) == CST1 &( ((A&M)==CST2) | ((A&O)==CST3) ) is not simplified
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=93150 navidrahimi changed: What|Removed |Added CC||navidrahimi at microsoft dot com --- Comment #1 from navidrahimi --- I was just checking this bug and I don't see how this can be a win though: Expression: (x&N) == CST1 & ( ((x&M)==CST2) | ((x&O)==CST3)) Number of operations: &:4 |:1 ==:3 Expression: ((x&(N|M)) == (CST1|CST2)) | ((x&(N|O)==(CST1|CST3)) Number of operations: &:2 |:5 ==:2 P.S. I might be missing something here though.
[Bug tree-optimization/102232] Missed arithmetic fold
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=102232 --- Comment #7 from navidrahimi --- The new version of the patch I attached to this bug has been approved by Richard Biener in this thread [1]. 1) https://gcc.gnu.org/pipermail/gcc-patches/2021-November/583935.html
[Bug tree-optimization/102232] Missed arithmetic fold
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=102232 --- Comment #6 from navidrahimi --- Created attachment 51760 --> https://gcc.gnu.org/bugzilla/attachment.cgi?id=51760&action=edit [PATCH] PR tree-optimization/102232 Adding a missing pattern to match.pd
[Bug tree-optimization/102232] Missed arithmetic fold
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=102232
navidrahimi changed:
What|Removed |Added
Attachment #51752|0 |1
is obsolete||
--- Comment #5 from navidrahimi ---
Comment on attachment 51752
--> https://gcc.gnu.org/bugzilla/attachment.cgi?id=51752
[PATCH] PR tree-optimization/102232
>From 7c2abb0eab05766ab879066b000c13de827e3b3d Mon Sep 17 00:00:00 2001
>From: Navid Rahimi
>Date: Mon, 8 Nov 2021 13:57:19 -0800
>Subject: [PATCH] PR tree-optimization/102232
>
> * match.pd (x * (1 + y / x) - y) -> (x - y % x): New optimization.
> * gcc.dg/tree-ssa/pr102232.c: testcase for this optimization.
>---
> gcc/match.pd | 7
> gcc/testsuite/gcc.dg/tree-ssa/pr102232.c | 52
> 2 files changed, 59 insertions(+)
> create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/pr102232.c
>
>diff --git a/gcc/match.pd b/gcc/match.pd
>index 71cf6f9df0a..37c01e79d97 100644
>--- a/gcc/match.pd
>+++ b/gcc/match.pd
>@@ -1295,6 +1295,13 @@ DEFINE_INT_AND_FLOAT_ROUND_FN (RINT)
> (bit_xor (bit_ior:c (bit_not @0) @1) (bit_ior:c @0 (bit_not @1)))
> (bit_xor @0 @1))
>
>+/* x * (1 + y / x) - y -> x - y % x */
>+(simplify
>+ (minus (mult:cs @0 (plus:cs integer_onep (trunc_div:s @1 @0))) @1)
>+ (if (INTEGRAL_TYPE_P (TREE_TYPE (@0))
>+ && types_match (@0, @1))
>+ (minus @0 (trunc_mod @1 @0
>+
> /* ((x & y) - (x | y)) - 1 -> ~(x ^ y) */
> (simplify
> (plus (nop_convert1? (minus@2 (nop_convert2? (bit_and:c @0 @1))
>diff --git a/gcc/testsuite/gcc.dg/tree-ssa/pr102232.c
>b/gcc/testsuite/gcc.dg/tree-ssa/pr102232.c
>new file mode 100644
>index 000..e7485cf24e9
>--- /dev/null
>+++ b/gcc/testsuite/gcc.dg/tree-ssa/pr102232.c
>@@ -0,0 +1,52 @@
>+/* PR tree-optimization/102232 */
>+/* { dg-do run } */
>+/* { dg-options "-O3 -fdump-tree-optimized" } */
>+
>+int __attribute__ ((noipa)) foo (int a, int b)
>+{
>+ return b * (1 + a / b) - a;
>+}
>+
>+int
>+main (void)
>+{
>+ // few randomly generated test cases
>+ if (foo (71856034, 238) != 212)
>+{
>+ return 1;
>+}
>+ if (foo (71856034, 10909) != 1549)
>+{
>+ return 1;
>+}
>+ if (foo (20350, 1744) != 578)
>+{
>+ return 1;
>+}
>+ if (foo (444813, 88563) != 86565)
>+{
>+ return 1;
>+}
>+ if (foo (112237, 63004) != 13771)
>+{
>+ return 1;
>+}
>+ if (foo (68268386, 787116) != 210706)
>+{
>+ return 1;
>+}
>+ if (foo (-444813, 88563) != 90561)
>+{
>+ return 1;
>+}
>+ if (foo (-68268386, 787116) != 1363526)
>+{
>+ return 1;
>+}
>+
>+ return 0;
>+}
>+
>+/* Verify that multiplication and division has been removed. */
>+/* { dg-final { scan-tree-dump-not " \\* " "optimized" } } */
>+/* { dg-final { scan-tree-dump-not " / " "optimized" } } */
>\ No newline at end of file
>--
>2.25.1
>
[Bug tree-optimization/102232] Missed arithmetic fold
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=102232 --- Comment #4 from navidrahimi --- This patch I attached will fix this problem and does include the test [1]. You can follow the discussion in GCC-Patches here [1]. Although it seems I still have problem to fix with MIME type of the patch in mailing list. 1) https://gcc.gnu.org/pipermail/gcc-patches/2021-November/583737.html
[Bug tree-optimization/102232] Missed arithmetic fold
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=102232 navidrahimi changed: What|Removed |Added CC||navidrahimi at microsoft dot com --- Comment #3 from navidrahimi --- Created attachment 51752 --> https://gcc.gnu.org/bugzilla/attachment.cgi?id=51752&action=edit Adding this pattern to match.pd
