[Bug c/107127] New: [Regression 11/12] Long compile times on code with C complex

[Bug c/107127] New: [Regression 11/12] Long compile times on code with C complex

[inform at tiker dot net]

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

            Bug ID: 107127
           Summary: [Regression 11/12] Long compile times on code with C
                    complex
           Product: gcc
           Version: 12.2.0
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: c
          Assignee: unassigned at gcc dot gnu.org
          Reporter: inform at tiker dot net
  Target Milestone: ---

A generated code using C-style complex arithmetic that compiled nearly
instantaneously with gcc 10.4 takes >=30s with gcc 11.3.0 and 12.2.0.

How to reproduce:

git clone https://gist.github.com/inducer/802e227e86e3ff4fd95aa0fefae462fe.git 
cd 802e227e86e3ff4fd95aa0fefae462fe
git checkout 9eb600e
$ time gcc-10 -c post-110.c
gcc-10 -c post-110.c  0,05s user 0,02s system 45% cpu 0,155 total
$ time gcc-11 -c post-110.c
^C
gcc-11 -c post-110.c  0,00s user 0,00s system 0% cpu 23,757 total
$ time gcc-12 -c post-110.c
^C
gcc-12 -c post-110.c  0,00s user 0,00s system 0% cpu 31,574 total

This does not seem to be very sensitive to headers, so I'm not including
preprocessed source to start. Happy to supply it if needed.

Target: x86_64-linux-gnu
Precise versions:

gcc version 10.4.0 (Debian 10.4.0-5)
gcc version 11.3.0 (Debian 11.3.0-5)
gcc version 12.2.0 (Debian 12.2.0-3)

x-ref: https://github.com/inducer/loopy/issues/686

[Bug c/107127] [11/12/13 Regression] Long compile times on code with C complex since r11-3299-gcba079f354a55363

[marxin at gcc dot gnu.org]

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

Martin Liška <marxin at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|UNCONFIRMED                 |NEW
     Ever confirmed|0                           |1
            Summary|[Regression 11/12] Long     |[11/12/13 Regression] Long
                   |compile times on code with  |compile times on code with
                   |C complex                   |C complex since
                   |                            |r11-3299-gcba079f354a55363
                 CC|                            |marxin at gcc dot gnu.org,
                   |                            |sandra at codesourcery dot com
   Last reconfirmed|                            |2022-10-03

--- Comment #1 from Martin Liška <marxin at gcc dot gnu.org> ---
Started with r11-3299-gcba079f354a55363.
Thanks for the bug report.

[Bug c/107127] [11/12/13 Regression] Long compile times on code with C complex since r11-3299-gcba079f354a55363

[marxin at gcc dot gnu.org]

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

--- Comment #2 from Martin Liška <marxin at gcc dot gnu.org> ---
Reduced test-case:

$ cat x.i
int *loopy_kernel_expr9;

void loopy_kernel() {
  _Complex var_e9_11;
  double var_e9_15;
  ;
  ;
  double var_e9_6;
  ;
  loopy_kernel_expr9[0] /
      ((((var_e9_6 *
              (0 - 0 / var_e9_11 + 699.0 + 7.050460596289373 - 286.0 -
               +-4.659839407494593 + 1.5759632377305621 + 0) *
              0 -
          3.287790705257411 + 4.226175928534705 + 0)) *
            var_e9_15 +
        5.065182909294865) *
           1.2325048646197416 * 0 * 0 -
       8.459732847790127 + 0 + 88.0 + 6.967677749063906 + 867.0 +
       9.104465770830789 - 7.042039895022722 * -1.0);
}

$ time gcc-7 x.i -c

real    0m0.028s
user    0m0.007s
sys     0m0.021s

$ time gcc-12 x.i -c

real    0m1.675s
user    0m1.656s
sys     0m0.018s

[Bug c/107127] [11/12/13 Regression] Long compile times on code with C complex since r11-3299-gcba079f354a55363

[pinskia at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
   Target Milestone|---                         |11.4

[Bug c/107127] [11/12/13 Regression] Long compile times on code with C complex since r11-3299-gcba079f354a55363

[pinskia at gcc dot gnu.org]

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

--- Comment #3 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
If anything it is the walk of the tree in c_genericize (c-gimplify.c)
Which is causing the issue.

+      walk_tree (&DECL_SAVED_TREE (fndecl), c_genericize_control_r,
+                NULL, NULL);

I suspect walk_tree_without_duplicates might fix this rather than using
walk_tree here.

[Bug c/107127] [11/12/13 Regression] Long compile times on code with C complex since r11-3299-gcba079f354a55363

[rguenth at gcc dot gnu.org]

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

Richard Biener <rguenth at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
           Priority|P3                          |P2

--- Comment #4 from Richard Biener <rguenth at gcc dot gnu.org> ---
Mind testing a patch then...?

[Bug c/107127] [11/12/13 Regression] Long compile times on code with C complex since r11-3299-gcba079f354a55363

[jakub at gcc dot gnu.org]

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

Jakub Jelinek <jakub at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|NEW                         |ASSIGNED
           Assignee|unassigned at gcc dot gnu.org      |jakub at gcc dot gnu.org
                 CC|                            |jakub at gcc dot gnu.org

--- Comment #5 from Jakub Jelinek <jakub at gcc dot gnu.org> ---
Created attachment 53941
  --> https://gcc.gnu.org/bugzilla/attachment.cgi?id=53941&action=edit
gcc13-pr107127.patch

I'll do it.  Testcase extended so that it takes ~ 5 minutes on a fast machine
without the patch and so that it will often time out.

[Bug c/107127] [11/12/13 Regression] Long compile times on code with C complex since r11-3299-gcba079f354a55363

[cvs-commit at gcc dot gnu.org]

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

--- Comment #6 from CVS Commits <cvs-commit at gcc dot gnu.org> ---
The master branch has been updated by Jakub Jelinek <jakub@gcc.gnu.org>:

https://gcc.gnu.org/g:8a0fce6a51915c29584427fd376b40073c328090

commit r13-4268-g8a0fce6a51915c29584427fd376b40073c328090
Author: Jakub Jelinek <jakub@redhat.com>
Date:   Wed Nov 23 19:09:31 2022 +0100

    c: Fix compile time hog in c_genericize [PR107127]

    The complex multiplications result in deeply nested set of many SAVE_EXPRs,
    which takes even on fast machines over 5 minutes to walk.
    This patch fixes that by using walk_tree_without_duplicates where it is
    instant.

    2022-11-23  Andrew Pinski  <apinski@marvell.com>
                Jakub Jelinek  <jakub@redhat.com>

            PR c/107127
            * c-gimplify.cc (c_genericize): Use walk_tree_without_duplicates
            instead of walk_tree for c_genericize_control_r.

            * gcc.dg/pr107127.c: New test.

[Bug c/107127] [11/12 Regression] Long compile times on code with C complex since r11-3299-gcba079f354a55363

[jakub at gcc dot gnu.org]

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

Jakub Jelinek <jakub at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
            Summary|[11/12/13 Regression] Long  |[11/12 Regression] Long
                   |compile times on code with  |compile times on code with
                   |C complex since             |C complex since
                   |r11-3299-gcba079f354a55363  |r11-3299-gcba079f354a55363

--- Comment #7 from Jakub Jelinek <jakub at gcc dot gnu.org> ---
Fixed on the trunk so far.

[Bug c/107127] [11/12 Regression] Long compile times on code with C complex since r11-3299-gcba079f354a55363

[cvs-commit at gcc dot gnu.org]

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

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

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

commit r13-4283-gadd0f941be18cdf962a0f300019acacbf2325d41
Author: Jakub Jelinek <jakub@redhat.com>
Date:   Thu Nov 24 10:33:00 2022 +0100

    testsuite: Fix up broken testcase [PR107127]

    I've added { dg-options "" } line manually in the patch but
    forgot to adjust the number of added lines.

    2022-11-24  Jakub Jelinek  <jakub@redhat.com>

            PR c/107127
            * gcc.dg/pr107127.c (foo): Add missing closing }.

[Bug c/107127] [11/12 Regression] Long compile times on code with C complex since r11-3299-gcba079f354a55363

[cvs-commit at gcc dot gnu.org]

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

--- Comment #9 from CVS Commits <cvs-commit at gcc dot gnu.org> ---
The releases/gcc-12 branch has been updated by Jakub Jelinek
<jakub@gcc.gnu.org>:

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

commit r12-9120-gb585bd941ea2e5c1cca52e40210483b556ce2ed7
Author: Jakub Jelinek <jakub@redhat.com>
Date:   Wed Nov 23 19:09:31 2022 +0100

    c: Fix compile time hog in c_genericize [PR107127]

    The complex multiplications result in deeply nested set of many SAVE_EXPRs,
    which takes even on fast machines over 5 minutes to walk.
    This patch fixes that by using walk_tree_without_duplicates where it is
    instant.

    2022-11-23  Andrew Pinski  <apinski@marvell.com>
                Jakub Jelinek  <jakub@redhat.com>

            PR c/107127
            * c-gimplify.cc (c_genericize): Use walk_tree_without_duplicates
            instead of walk_tree for c_genericize_control_r.

            * gcc.dg/pr107127.c: New test.

    (cherry picked from commit 8a0fce6a51915c29584427fd376b40073c328090)

[Bug c/107127] [11/12 Regression] Long compile times on code with C complex since r11-3299-gcba079f354a55363

[cvs-commit at gcc dot gnu.org]

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

--- Comment #10 from CVS Commits <cvs-commit at gcc dot gnu.org> ---
The releases/gcc-12 branch has been updated by Jakub Jelinek
<jakub@gcc.gnu.org>:

https://gcc.gnu.org/g:80010acd052ca7fe544740144756cf9fc2fad629

commit r12-9121-g80010acd052ca7fe544740144756cf9fc2fad629
Author: Jakub Jelinek <jakub@redhat.com>
Date:   Thu Nov 24 10:33:00 2022 +0100

    testsuite: Fix up broken testcase [PR107127]

    I've added { dg-options "" } line manually in the patch but
    forgot to adjust the number of added lines.

    2022-11-24  Jakub Jelinek  <jakub@redhat.com>

            PR c/107127
            * gcc.dg/pr107127.c (foo): Add missing closing }.

    (cherry picked from commit add0f941be18cdf962a0f300019acacbf2325d41)

[Bug c/107127] [11 Regression] Long compile times on code with C complex since r11-3299-gcba079f354a55363

[jakub at gcc dot gnu.org]

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

Jakub Jelinek <jakub at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
            Summary|[11/12 Regression] Long     |[11 Regression] Long
                   |compile times on code with  |compile times on code with
                   |C complex since             |C complex since
                   |r11-3299-gcba079f354a55363  |r11-3299-gcba079f354a55363

--- Comment #11 from Jakub Jelinek <jakub at gcc dot gnu.org> ---
Fixed for gcc 12.3 too.

[Bug c/107127] [11 Regression] Long compile times on code with C complex since r11-3299-gcba079f354a55363

[cvs-commit at gcc dot gnu.org]

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

--- Comment #12 from CVS Commits <cvs-commit at gcc dot gnu.org> ---
The releases/gcc-11 branch has been updated by Jakub Jelinek
<jakub@gcc.gnu.org>:

https://gcc.gnu.org/g:21d09955d2b7755db7d5ba3cd4a314930b470da7

commit r11-10682-g21d09955d2b7755db7d5ba3cd4a314930b470da7
Author: Jakub Jelinek <jakub@redhat.com>
Date:   Wed Nov 23 19:09:31 2022 +0100

    c: Fix compile time hog in c_genericize [PR107127]

    The complex multiplications result in deeply nested set of many SAVE_EXPRs,
    which takes even on fast machines over 5 minutes to walk.
    This patch fixes that by using walk_tree_without_duplicates where it is
    instant.

    2022-11-23  Andrew Pinski  <apinski@marvell.com>
                Jakub Jelinek  <jakub@redhat.com>

            PR c/107127
            * c-gimplify.c (c_genericize): Use walk_tree_without_duplicates
            instead of walk_tree for c_genericize_control_r.

            * gcc.dg/pr107127.c: New test.

    (cherry picked from commit 8a0fce6a51915c29584427fd376b40073c328090)

[Bug c/107127] [11 Regression] Long compile times on code with C complex since r11-3299-gcba079f354a55363

[cvs-commit at gcc dot gnu.org]

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

--- Comment #13 from CVS Commits <cvs-commit at gcc dot gnu.org> ---
The releases/gcc-11 branch has been updated by Jakub Jelinek
<jakub@gcc.gnu.org>:

https://gcc.gnu.org/g:21ffe7bc50422bbf2fc844f4e69a16d7e8d35698

commit r11-10683-g21ffe7bc50422bbf2fc844f4e69a16d7e8d35698
Author: Jakub Jelinek <jakub@redhat.com>
Date:   Thu Nov 24 10:33:00 2022 +0100

    testsuite: Fix up broken testcase [PR107127]

    I've added { dg-options "" } line manually in the patch but
    forgot to adjust the number of added lines.

    2022-11-24  Jakub Jelinek  <jakub@redhat.com>

            PR c/107127
            * gcc.dg/pr107127.c (foo): Add missing closing }.

    (cherry picked from commit add0f941be18cdf962a0f300019acacbf2325d41)

[Bug c/107127] [11 Regression] Long compile times on code with C complex since r11-3299-gcba079f354a55363

[jakub at gcc dot gnu.org]

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

Jakub Jelinek <jakub at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|ASSIGNED                    |RESOLVED
         Resolution|---                         |FIXED

--- Comment #14 from Jakub Jelinek <jakub at gcc dot gnu.org> ---
Fixed for 11.4 as well.