public inbox for gcc-bugs@sourceware.org
help / color / mirror / Atom feed
* [Bug tree-optimization/102232] New: Missed arithmetic fold
@ 2021-09-07 15:22 llvm at rifkin dot dev
  2021-09-07 15:24 ` [Bug tree-optimization/102232] " llvm at rifkin dot dev
                   ` (9 more replies)
  0 siblings, 10 replies; 11+ messages in thread
From: llvm at rifkin dot dev @ 2021-09-07 15:22 UTC (permalink / raw)
  To: gcc-bugs

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=102232

            Bug ID: 102232
           Summary: Missed arithmetic fold
           Product: gcc
           Version: 12.0
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: tree-optimization
          Assignee: unassigned at gcc dot gnu.org
          Reporter: llvm at rifkin dot dev
  Target Milestone: ---

LLVM optimizes bar into tgt here but not foo.

https://godbolt.org/z/nhEjaoanx

int foo(int a, int b) {
    return b * (1 + a / b) - a;
}
int bar(int a, int b) {
    return b * (a / b) + b - a;
}
int tgt(int a, int b) {
    return b - a % b;
}

LLVM appears to miss this too.

^ permalink raw reply	[flat|nested] 11+ messages in thread

* [Bug tree-optimization/102232] Missed arithmetic fold
  2021-09-07 15:22 [Bug tree-optimization/102232] New: Missed arithmetic fold llvm at rifkin dot dev
@ 2021-09-07 15:24 ` llvm at rifkin dot dev
  2021-09-07 18:34 ` pinskia at gcc dot gnu.org
                   ` (8 subsequent siblings)
  9 siblings, 0 replies; 11+ messages in thread
From: llvm at rifkin dot dev @ 2021-09-07 15:24 UTC (permalink / raw)
  To: gcc-bugs

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=102232

--- Comment #1 from Jeremy R. <llvm at rifkin dot dev> ---
Correction on first line: *GCC optimizes bar into tgt here but not foo.
Pardon my sloppy copy-paste from my bug report over on LLVM's bugzilla!

^ permalink raw reply	[flat|nested] 11+ messages in thread

* [Bug tree-optimization/102232] Missed arithmetic fold
  2021-09-07 15:22 [Bug tree-optimization/102232] New: Missed arithmetic fold llvm at rifkin dot dev
  2021-09-07 15:24 ` [Bug tree-optimization/102232] " llvm at rifkin dot dev
@ 2021-09-07 18:34 ` pinskia at gcc dot gnu.org
  2021-09-07 18:43 ` pinskia at gcc dot gnu.org
                   ` (7 subsequent siblings)
  9 siblings, 0 replies; 11+ messages in thread
From: pinskia at gcc dot gnu.org @ 2021-09-07 18:34 UTC (permalink / raw)
  To: gcc-bugs

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=102232

Andrew Pinski <pinskia at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
           Keywords|                            |missed-optimization
           Severity|normal                      |enhancement

^ permalink raw reply	[flat|nested] 11+ messages in thread

* [Bug tree-optimization/102232] Missed arithmetic fold
  2021-09-07 15:22 [Bug tree-optimization/102232] New: Missed arithmetic fold llvm at rifkin dot dev
  2021-09-07 15:24 ` [Bug tree-optimization/102232] " llvm at rifkin dot dev
  2021-09-07 18:34 ` pinskia at gcc dot gnu.org
@ 2021-09-07 18:43 ` pinskia at gcc dot gnu.org
  2021-11-09  4:30 ` navidrahimi at microsoft dot com
                   ` (6 subsequent siblings)
  9 siblings, 0 replies; 11+ messages in thread
From: pinskia at gcc dot gnu.org @ 2021-09-07 18:43 UTC (permalink / raw)
  To: gcc-bugs

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=102232

Andrew Pinski <pinskia at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
           Keywords|                            |TREE
             Status|UNCONFIRMED                 |NEW
   Last reconfirmed|                            |2021-09-07
     Ever confirmed|0                           |1

--- Comment #2 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
So on aarch64, the code for all three functions are almost the same:

foo(int, int):
        sdiv    w2, w0, w1
        madd    w1, w2, w1, w1
        sub     w0, w1, w0
        ret

bar(int, int):
        sdiv    w2, w0, w1
        madd    w1, w2, w1, w1
        sub     w0, w1, w0
        ret

tgt(int, int):
        sdiv    w2, w0, w1
        msub    w0, w2, w1, w0
        sub     w0, w1, w0
        ret

MSVC can do the transformation.

^ permalink raw reply	[flat|nested] 11+ messages in thread

* [Bug tree-optimization/102232] Missed arithmetic fold
  2021-09-07 15:22 [Bug tree-optimization/102232] New: Missed arithmetic fold llvm at rifkin dot dev
                   ` (2 preceding siblings ...)
  2021-09-07 18:43 ` pinskia at gcc dot gnu.org
@ 2021-11-09  4:30 ` navidrahimi at microsoft dot com
  2021-11-09  4:34 ` navidrahimi at microsoft dot com
                   ` (5 subsequent siblings)
  9 siblings, 0 replies; 11+ messages in thread
From: navidrahimi at microsoft dot com @ 2021-11-09  4:30 UTC (permalink / raw)
  To: gcc-bugs

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=102232

navidrahimi <navidrahimi at microsoft dot com> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |navidrahimi at microsoft dot com

--- Comment #3 from navidrahimi <navidrahimi at microsoft dot com> ---
Created attachment 51752
  --> https://gcc.gnu.org/bugzilla/attachment.cgi?id=51752&action=edit
Adding this pattern to match.pd

^ permalink raw reply	[flat|nested] 11+ messages in thread

* [Bug tree-optimization/102232] Missed arithmetic fold
  2021-09-07 15:22 [Bug tree-optimization/102232] New: Missed arithmetic fold llvm at rifkin dot dev
                   ` (3 preceding siblings ...)
  2021-11-09  4:30 ` navidrahimi at microsoft dot com
@ 2021-11-09  4:34 ` navidrahimi at microsoft dot com
  2021-11-10 16:17 ` navidrahimi at microsoft dot com
                   ` (4 subsequent siblings)
  9 siblings, 0 replies; 11+ messages in thread
From: navidrahimi at microsoft dot com @ 2021-11-09  4:34 UTC (permalink / raw)
  To: gcc-bugs

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=102232

--- Comment #4 from navidrahimi <navidrahimi at microsoft dot com> ---
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

^ permalink raw reply	[flat|nested] 11+ messages in thread

* [Bug tree-optimization/102232] Missed arithmetic fold
  2021-09-07 15:22 [Bug tree-optimization/102232] New: Missed arithmetic fold llvm at rifkin dot dev
                   ` (4 preceding siblings ...)
  2021-11-09  4:34 ` navidrahimi at microsoft dot com
@ 2021-11-10 16:17 ` navidrahimi at microsoft dot com
  2021-11-10 16:19 ` navidrahimi at microsoft dot com
                   ` (3 subsequent siblings)
  9 siblings, 0 replies; 11+ messages in thread
From: navidrahimi at microsoft dot com @ 2021-11-10 16:17 UTC (permalink / raw)
  To: gcc-bugs

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=102232

navidrahimi <navidrahimi at microsoft dot com> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
  Attachment #51752|0                           |1
        is obsolete|                            |

--- Comment #5 from navidrahimi <navidrahimi at microsoft dot com> ---
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 <navidrahimi@microsoft.com>
>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 00000000000..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
>

^ permalink raw reply	[flat|nested] 11+ messages in thread

* [Bug tree-optimization/102232] Missed arithmetic fold
  2021-09-07 15:22 [Bug tree-optimization/102232] New: Missed arithmetic fold llvm at rifkin dot dev
                   ` (5 preceding siblings ...)
  2021-11-10 16:17 ` navidrahimi at microsoft dot com
@ 2021-11-10 16:19 ` navidrahimi at microsoft dot com
  2021-11-10 16:22 ` navidrahimi at microsoft dot com
                   ` (2 subsequent siblings)
  9 siblings, 0 replies; 11+ messages in thread
From: navidrahimi at microsoft dot com @ 2021-11-10 16:19 UTC (permalink / raw)
  To: gcc-bugs

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=102232

--- Comment #6 from navidrahimi <navidrahimi at microsoft dot com> ---
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

^ permalink raw reply	[flat|nested] 11+ messages in thread

* [Bug tree-optimization/102232] Missed arithmetic fold
  2021-09-07 15:22 [Bug tree-optimization/102232] New: Missed arithmetic fold llvm at rifkin dot dev
                   ` (6 preceding siblings ...)
  2021-11-10 16:19 ` navidrahimi at microsoft dot com
@ 2021-11-10 16:22 ` navidrahimi at microsoft dot com
  2021-11-23  3:08 ` cvs-commit at gcc dot gnu.org
  2022-02-23 21:26 ` roger at nextmovesoftware dot com
  9 siblings, 0 replies; 11+ messages in thread
From: navidrahimi at microsoft dot com @ 2021-11-10 16:22 UTC (permalink / raw)
  To: gcc-bugs

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=102232

--- Comment #7 from navidrahimi <navidrahimi at microsoft dot com> ---
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

^ permalink raw reply	[flat|nested] 11+ messages in thread

* [Bug tree-optimization/102232] Missed arithmetic fold
  2021-09-07 15:22 [Bug tree-optimization/102232] New: Missed arithmetic fold llvm at rifkin dot dev
                   ` (7 preceding siblings ...)
  2021-11-10 16:22 ` navidrahimi at microsoft dot com
@ 2021-11-23  3:08 ` cvs-commit at gcc dot gnu.org
  2022-02-23 21:26 ` roger at nextmovesoftware dot com
  9 siblings, 0 replies; 11+ messages in thread
From: cvs-commit at gcc dot gnu.org @ 2021-11-23  3:08 UTC (permalink / raw)
  To: gcc-bugs

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=102232

--- Comment #8 from CVS Commits <cvs-commit at gcc dot gnu.org> ---
The master branch has been updated by Jeff Law <law@gcc.gnu.org>:

https://gcc.gnu.org/g:df1a0d526e2e4c75311345c0b73ce8483e243899

commit r12-5460-gdf1a0d526e2e4c75311345c0b73ce8483e243899
Author: Navid Rahimi <navidrahimi@microsoft.com>
Date:   Mon Nov 22 22:07:35 2021 -0500

    Re: [PATCH] PR tree-optimization/102232 Adding a missing pattern to
match.pd

            PR tree-optimization/102232

    gcc/
            * match.pd (x * (1 + y / x) - y) -> (x - y % x): New optimization.

    gcc/testsuite/

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

^ permalink raw reply	[flat|nested] 11+ messages in thread

* [Bug tree-optimization/102232] Missed arithmetic fold
  2021-09-07 15:22 [Bug tree-optimization/102232] New: Missed arithmetic fold llvm at rifkin dot dev
                   ` (8 preceding siblings ...)
  2021-11-23  3:08 ` cvs-commit at gcc dot gnu.org
@ 2022-02-23 21:26 ` roger at nextmovesoftware dot com
  9 siblings, 0 replies; 11+ messages in thread
From: roger at nextmovesoftware dot com @ 2022-02-23 21:26 UTC (permalink / raw)
  To: gcc-bugs

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=102232

Roger Sayle <roger at nextmovesoftware dot com> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|NEW                         |RESOLVED
         Resolution|---                         |FIXED
   Target Milestone|---                         |12.0
                 CC|                            |roger at nextmovesoftware dot com

--- Comment #9 from Roger Sayle <roger at nextmovesoftware dot com> ---
This is fixed on mainline; the godbolt link in comment #1 shows that GCC now
generates the same code for all three functions.

^ permalink raw reply	[flat|nested] 11+ messages in thread

end of thread, other threads:[~2022-02-23 21:26 UTC | newest]

Thread overview: 11+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2021-09-07 15:22 [Bug tree-optimization/102232] New: Missed arithmetic fold llvm at rifkin dot dev
2021-09-07 15:24 ` [Bug tree-optimization/102232] " llvm at rifkin dot dev
2021-09-07 18:34 ` pinskia at gcc dot gnu.org
2021-09-07 18:43 ` pinskia at gcc dot gnu.org
2021-11-09  4:30 ` navidrahimi at microsoft dot com
2021-11-09  4:34 ` navidrahimi at microsoft dot com
2021-11-10 16:17 ` navidrahimi at microsoft dot com
2021-11-10 16:19 ` navidrahimi at microsoft dot com
2021-11-10 16:22 ` navidrahimi at microsoft dot com
2021-11-23  3:08 ` cvs-commit at gcc dot gnu.org
2022-02-23 21:26 ` roger at nextmovesoftware dot com

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).