[Bug other/105028] New: gcc.dg/long_branch.c compilation time increases by 10x on BE system after r11-5648

[Bug other/105028] New: gcc.dg/long_branch.c compilation time increases by 10x on BE system after r11-5648

[seurer at gcc dot gnu.org]

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

            Bug ID: 105028
           Summary: gcc.dg/long_branch.c compilation time increases by 10x
                    on BE system after r11-5648
           Product: gcc
           Version: 11.2.1
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: other
          Assignee: unassigned at gcc dot gnu.org
          Reporter: seurer at gcc dot gnu.org
  Target Milestone: ---

Starting back in gcc 11 there were a couple of test case compilations that
started to time out on our older BE systems.  The most common one was
gcc.dg/long_branch.c.  It happened so rarely I never got back to investigating
if it was always this way or there was some recent change.

I finally tracked it down to r11-5648.  Note it also happens in trunk.  Before
the change on a power 7 long_branch.c takes about 4s to compile with -m32 and
5.5s with -m64 (varies a bit between runs).  With r11-5648 that changes to 50+s
and 9s respectively.  On a busy system that 50s can stretch out long enough to
hit the 300 second ulimit set for test case compilations and thus they time
out. The time change increases are similar on a power 8 BE machine, too, but as
they are faster they never hit the timeout.

I see no difference in compilation time on an LE system.

I looked using -ftime-report at what was taking more time and saw these:

g:337d6362458ab033d3bfe287dda37f9da5577406, r11-5647:
 phase opt and generate             :   3.89 ( 97%)   0.04 ( 44%)   3.92 ( 95%)
   43M ( 91%)
 callgraph functions expansion      :   3.23 ( 80%)   0.02 ( 22%)   3.25 ( 79%)
   32M ( 68%)
 integrated RA                      :   0.23 (  6%)   0.00 (  0%)   0.23 (  6%)
   12M ( 26%)

g:037fe26ee1ac18581bf0ad646d48591c97d10bd3, r11-5648:
 phase opt and generate             :  32.86 (100%)   0.16 ( 73%)  33.02 ( 99%)
  205M ( 98%)
 callgraph functions expansion      :  32.28 ( 98%)   0.14 ( 64%)  32.42 ( 98%)
  194M ( 93%)
 integrated RA                      :  20.70 ( 63%)   0.08 ( 36%)  20.79 ( 63%)
   50M ( 24%)

The latter run had a few more phases that ran, too.

So, is this a real problem or a "just live with it" thing?


commit 037fe26ee1ac18581bf0ad646d48591c97d10bd3
Author: Jakub Jelinek <jakub@redhat.com>
Date:   Wed Dec 2 11:32:19 2020 +0100

    expansion: Further improve double-word modulo, division and divmod
[PR97459]

[Bug middle-end/105028] [11/12 Regression] gcc.dg/long_branch.c compilation time increases by 10x on BE system after r11-5648

[pinskia at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
   Target Milestone|---                         |11.3
           Keywords|                            |ra
            Summary|gcc.dg/long_branch.c        |[11/12 Regression]
                   |compilation time increases  |gcc.dg/long_branch.c
                   |by 10x on BE system after   |compilation time increases
                   |r11-5648                    |by 10x on BE system after
                   |                            |r11-5648

[Bug middle-end/105028] [11/12 Regression] gcc.dg/long_branch.c compilation time increases by 10x on BE system after r11-5648

[rguenth at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
     Ever confirmed|0                           |1
                 CC|                            |vmakarov at gcc dot gnu.org
   Last reconfirmed|                            |2022-03-23
             Status|UNCONFIRMED                 |NEW
           Priority|P3                          |P2

--- Comment #1 from Richard Biener <rguenth at gcc dot gnu.org> ---
Confirmed.

Samples: 42K of event 'cycles', Event count (approx.): 46707220159              
Overhead       Samples  Command  Shared Object     Symbol                       
  48.06%         20480  cc1      cc1               [.] form_threads_from_copies

and all the overhead is in the tail copying:

      /* Collect the rest of copies.  */
      for (n = 0; i < cp_num; i++)
        {
          cp = sorted_copies[i];
          if (ALLOCNO_COLOR_DATA (cp->first)->first_thread_allocno
              != ALLOCNO_COLOR_DATA (cp->second)->first_thread_allocno)
            sorted_copies[n++] = cp;
        }

for the slow case cp_num is 55100.

[Bug middle-end/105028] [11/12 Regression] gcc.dg/long_branch.c compilation time increases by 10x on BE system after r11-5648

[rguenth at gcc dot gnu.org]

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

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

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

--- Comment #2 from Richard Biener <rguenth at gcc dot gnu.org> ---
But the code is weird - I have no idea why we copy around fields at all instead
of just continuing to merge threads...

I'll test & post a patch which takes the function off the radar.

[Bug middle-end/105028] [11/12 Regression] gcc.dg/long_branch.c compilation time increases by 10x on BE system after r11-5648

[seurer at gcc dot gnu.org]

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

--- Comment #3 from seurer at gcc dot gnu.org ---
Thanks for looking at this.  It has been bugging me at a low level for months.

[Bug middle-end/105028] [11/12 Regression] gcc.dg/long_branch.c compilation time increases by 10x on BE system after r11-5648

[cvs-commit at gcc dot gnu.org]

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

--- Comment #4 from CVS Commits <cvs-commit at gcc dot gnu.org> ---
The master branch has been updated by Richard Biener <rguenth@gcc.gnu.org>:

https://gcc.gnu.org/g:1daa198aafd72925ca8dd8616385f523ff180d4a

commit r12-7785-g1daa198aafd72925ca8dd8616385f523ff180d4a
Author: Richard Biener <rguenther@suse.de>
Date:   Wed Mar 23 12:21:32 2022 +0100

    rtl-optimization/105028 - fix compile-time hog in form_threads_from_copies

    form_threads_from_copies processes a sorted array of copies, skipping
    those with the same thread and conflicting threads and merging the
    first non-conflicting ones.  After that it terminates the loop and
    gathers the remaining elements of the array, skipping same thread
    copies, re-starting the process.  For a large number of copies this
    gathering of the rest takes considerable time and it also appears
    pointless.  The following simply continues processing the array
    which should be equivalent as far as I can see.

    This takes form_threads_from_copies off the profile radar from
    previously taking ~50% of the compile-time.

    2022-03-23  Richard Biener  <rguenther@suse.de>

            PR rtl-optimization/105028
            * ira-color.cc (form_threads_from_copies): Remove unnecessary
            copying of the sorted_copies tail.

[Bug middle-end/105028] [11/12 Regression] gcc.dg/long_branch.c compilation time increases by 10x on BE system after r11-5648

[seurer at gcc dot gnu.org]

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

--- Comment #5 from seurer at gcc dot gnu.org ---
Thanks, that patch really improved things!

[Bug middle-end/105028] [11 Regression] gcc.dg/long_branch.c compilation time increases by 10x on BE system after r11-5648

[cvs-commit at gcc dot gnu.org]

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

--- Comment #6 from CVS Commits <cvs-commit at gcc dot gnu.org> ---
The releases/gcc-11 branch has been updated by Richard Biener
<rguenth@gcc.gnu.org>:

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

commit r11-9781-gb3eb889978c6a28961511bd70f3cc177df54fde7
Author: Richard Biener <rguenther@suse.de>
Date:   Wed Mar 23 12:21:32 2022 +0100

    rtl-optimization/105028 - fix compile-time hog in form_threads_from_copies

    form_threads_from_copies processes a sorted array of copies, skipping
    those with the same thread and conflicting threads and merging the
    first non-conflicting ones.  After that it terminates the loop and
    gathers the remaining elements of the array, skipping same thread
    copies, re-starting the process.  For a large number of copies this
    gathering of the rest takes considerable time and it also appears
    pointless.  The following simply continues processing the array
    which should be equivalent as far as I can see.

    This takes form_threads_from_copies off the profile radar from
    previously taking ~50% of the compile-time.

    2022-03-23  Richard Biener  <rguenther@suse.de>

            PR rtl-optimization/105028
            * ira-color.c (form_threads_from_copies): Remove unnecessary
            copying of the sorted_copies tail.

    (cherry picked from commit 1daa198aafd72925ca8dd8616385f523ff180d4a)

[Bug middle-end/105028] [11 Regression] gcc.dg/long_branch.c compilation time increases by 10x on BE system after r11-5648

[rguenth at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
      Known to fail|                            |11.2.0
         Resolution|---                         |FIXED
             Status|ASSIGNED                    |RESOLVED

--- Comment #7 from Richard Biener <rguenth at gcc dot gnu.org> ---
Fixed.