[Bug c/96729] New: hang on x86_64-linux-gnu with `-g -O3`

[Bug c/96729] New: hang on x86_64-linux-gnu with `-g -O3`

[cnsun at uwaterloo dot ca]

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

            Bug ID: 96729
           Summary: hang on x86_64-linux-gnu with `-g -O3`
           Product: gcc
           Version: unknown
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: c
          Assignee: unassigned at gcc dot gnu.org
          Reporter: cnsun at uwaterloo dot ca
  Target Milestone: ---

$ timeout -s 9 60 gcc-trunk -g -O3 t.c 
Killed
$ 
$ cat t.c
int a, b, d, e;
int c[9][4];
int main() {
  for (;;) {
    long g;
    if (e)
      continue;
    d = 3;
    for (; d < 22; d++) {
      a = 0;
      for (; a < 55; a = a + 6) {
        b = 0;
        for (; b < 9; b++) {
          g = 0;
          c[b][g] = 3;
        }
      }
    }
  }
}
$ 
$ gcc-trunk -v
Using built-in specs.
COLLECT_GCC=gcc-trunk
COLLECT_LTO_WRAPPER=/scratch/software/gcc-trunk/libexec/gcc/x86_64-pc-linux-gnu/11.0.0/lto-wrapper
Target: x86_64-pc-linux-gnu
Configured with: /tmp/tmp.uva1EAuUpA-gcc-builder/gcc/configure
--enable-languages=c,c++,lto --enable-multiarch
--prefix=/scratch/software/gcc-trunk --disable-bootstrap
Thread model: posix
Supported LTO compression algorithms: zlib
gcc version 11.0.0 20200820 (experimental) [master revision
:01cb32abf:04e23a4051fb3c049f85b9e6e2fc58f937337aff] (GCC) 
$ 
$ gcc-trunk -g -O2 t.c
$ 
$

[Bug tree-optimization/96729] [11 Regression] hang on x86_64-linux-gnu with `-g -O3` since r11-39-gf9e1ea10e657af9f

[marxin at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
            Summary|hang on x86_64-linux-gnu    |[11 Regression] hang on
                   |with `-g -O3`               |x86_64-linux-gnu with `-g
                   |                            |-O3` since
                   |                            |r11-39-gf9e1ea10e657af9f
                 CC|                            |marxin at gcc dot gnu.org,
                   |                            |rguenth at gcc dot gnu.org
      Known to fail|                            |11.0
             Status|UNCONFIRMED                 |NEW
           Priority|P3                          |P1
     Ever confirmed|0                           |1
      Known to work|                            |10.2.0
   Last reconfirmed|                            |2020-08-24

--- Comment #1 from Martin Liška <marxin at gcc dot gnu.org> ---
Confirmed, started with Richi's r11-39-gf9e1ea10e657af9f.

[Bug tree-optimization/96729] [11 Regression] hang on x86_64-linux-gnu with `-g -O3` since r11-39-gf9e1ea10e657af9f

[rguenth at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|NEW                         |ASSIGNED
   Target Milestone|---                         |11.0
           Assignee|unassigned at gcc dot gnu.org      |rguenth at gcc dot gnu.org
            Version|unknown                     |11.0

--- Comment #2 from Richard Biener <rguenth at gcc dot gnu.org> ---
Mine.

[Bug tree-optimization/96729] [11 Regression] hang on x86_64-linux-gnu with `-g -O3` since r11-39-gf9e1ea10e657af9f

[rguenth at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |aoliva at gcc dot gnu.org,
                   |                            |jakub at gcc dot gnu.org

--- Comment #3 from Richard Biener <rguenth at gcc dot gnu.org> ---
I can't reproduce this.  Well, -O3 -g takes way longer but that's because
we elide the stores to a, b, d and e since the loop is endless and then
we unroll it all ending up with a basic-block with just ~20000 useless
debug stmts.

So we now optimize as expected.

-gno-statement-frontiers makes it also compiled fast.

Now the question is whether we may want to do anything about a BB like

  <bb 10> [local count: 1804255]:
  [t.c:4:3] # DEBUG BEGIN_STMT
  [t.c:5:5] # DEBUG BEGIN_STMT
  [t.c:6:5] # DEBUG BEGIN_STMT
  [t.c:10:7] # DEBUG BEGIN_STMT
  [t.c:11:7] # DEBUG BEGIN_STMT
  [t.c:11:14] # DEBUG BEGIN_STMT
  [t.c:12:9] # DEBUG BEGIN_STMT
  [t.c:13:9] # DEBUG BEGIN_STMT
  [t.c:13:16] # DEBUG BEGIN_STMT
  [t.c:14:13] # DEBUG g => NULL
  [t.c:14:11] # DEBUG BEGIN_STMT
  [t.c:14:13] # DEBUG g => 0
  [t.c:15:11] # DEBUG BEGIN_STMT
  [t.c:15:19] [t.c:15:15] [t.c:15:12] c[0][0] = 3;
  [t.c:13:23] # DEBUG BEGIN_STMT
  [t.c:13:16] # DEBUG BEGIN_STMT
  [t.c:11:22] # DEBUG BEGIN_STMT
  [t.c:11:14] # DEBUG BEGIN_STMT
  [t.c:12:9] # DEBUG BEGIN_STMT
  [t.c:13:9] # DEBUG BEGIN_STMT
  [t.c:13:16] # DEBUG BEGIN_STMT
  [t.c:14:13] # DEBUG g => NULL
  [t.c:14:11] # DEBUG BEGIN_STMT
  [t.c:14:13] # DEBUG g => 0
  [t.c:15:11] # DEBUG BEGIN_STMT
  [t.c:13:23] # DEBUG BEGIN_STMT
  [t.c:13:16] # DEBUG BEGIN_STMT
  [t.c:11:22] # DEBUG BEGIN_STMT
  [t.c:11:14] # DEBUG BEGIN_STMT
  [t.c:12:9] # DEBUG BEGIN_STMT
  [t.c:13:9] # DEBUG BEGIN_STMT
  [t.c:13:16] # DEBUG BEGIN_STMT
  [t.c:14:13] # DEBUG g => NULL
  [t.c:14:11] # DEBUG BEGIN_STMT
  [t.c:14:13] # DEBUG g => 0
  [t.c:15:11] # DEBUG BEGIN_STMT
  [t.c:13:23] # DEBUG BEGIN_STMT
  [t.c:13:16] # DEBUG BEGIN_STMT
  [t.c:11:22] # DEBUG BEGIN_STMT
  [t.c:11:14] # DEBUG BEGIN_STMT
  [t.c:12:9] # DEBUG BEGIN_STMT
  [t.c:13:9] # DEBUG BEGIN_STMT
  [t.c:13:16] # DEBUG BEGIN_STMT
  [t.c:14:13] # DEBUG g => NULL
  [t.c:14:11] # DEBUG BEGIN_STMT
  [t.c:14:13] # DEBUG g => 0
...
  [t.c:15:11] # DEBUG BEGIN_STMT
  [t.c:15:19] [t.c:15:15] [t.c:15:12] c[1][0] = 3;
  [t.c:13:23] # DEBUG BEGIN_STMT
  [t.c:13:16] # DEBUG BEGIN_STMT
  [t.c:11:22] # DEBUG BEGIN_STMT
  [t.c:11:14] # DEBUG BEGIN_STMT
...

I understand that it is not as simple as simply killing adjacent
DEBUG BEGIN_STMT stmts, keeping only the last?

[Bug tree-optimization/96729] [11 Regression] hang on x86_64-linux-gnu with `-g -O3` since r11-39-gf9e1ea10e657af9f

[rguenth at gcc dot gnu.org]

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

--- Comment #4 from Richard Biener <rguenth at gcc dot gnu.org> ---
Samples: 7K of event 'cycles:u', Event count (approx.): 7668407627              
Overhead  Command  Shared Object     Symbol                                     
  26.63%  cc1      cc1               [.] dwarf2out_next_real_insn
   9.81%  cc1      cc1               [.] is_a_helper<rtx_insn*>::test<rtx_def>

guess there's some quadraticness here, walking the insn stream more times
than necessary.

[Bug tree-optimization/96729] [11 Regression] slow compile with `-g -O3` since r11-39-gf9e1ea10e657af9f

[jakub at gcc dot gnu.org]

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

--- Comment #5 from Jakub Jelinek <jakub at gcc dot gnu.org> ---
(In reply to Richard Biener from comment #4)
> Samples: 7K of event 'cycles:u', Event count (approx.): 7668407627          
> 
> Overhead  Command  Shared Object     Symbol                                 
> 
>   26.63%  cc1      cc1               [.] dwarf2out_next_real_insn
>    9.81%  cc1      cc1               [.]
> is_a_helper<rtx_insn*>::test<rtx_def>
> 
> guess there's some quadraticness here, walking the insn stream more times
> than necessary.

For the thousands of consecutive NOTE_INSN_VAR_LOCATION notes case
dwarf2out_var_location has a cache that avoids calling dwarf2out_next_real_insn
for each and thus the quadratic behavior.
Unfortunately the addition of NOTE_INSN_BEGIN_STMT and/or
NOTE_INSN_INLINE_ENTRY broke how this cache works, because
dwarf2out_var_location isn't called in those cases.

[Bug debug/96729] [11 Regression] slow compile with `-g -O3` since r11-39-gf9e1ea10e657af9f

[jakub at gcc dot gnu.org]

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

--- Comment #6 from Jakub Jelinek <jakub at gcc dot gnu.org> ---
Created attachment 49121
  --> https://gcc.gnu.org/bugzilla/attachment.cgi?id=49121&action=edit
gcc11-pr96729.patch

Untested fix for the next real insn caching.
$ time ./cc1.vanilla -quiet -g -O3 pr96729.c -dA

real 0m2.756s
user 0m2.728s
sys 0m0.022s
$ time ./cc1 -quiet -g -O3 pr96729.c -dA

real 0m1.040s
user 0m1.018s
sys 0m0.020s

and the generated assembly is identical.  The times are with -O0 built
debugging cc1, so I really can't reproduce spending 60s on that, that would
need extremely slow machine.

[Bug debug/96729] [11 Regression] slow compile with `-g -O3` since r11-39-gf9e1ea10e657af9f

[rguenth at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
           Assignee|rguenth at gcc dot gnu.org         |jakub at gcc dot gnu.org

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

[Bug debug/96729] [11 Regression] slow compile with `-g -O3` since r11-39-gf9e1ea10e657af9f

[cvs-commit at gcc dot gnu.org]

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

--- 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:ca1afa261d03c9343dff1208325f87d9ba69ec7a

commit r11-2872-gca1afa261d03c9343dff1208325f87d9ba69ec7a
Author: Jakub Jelinek <jakub@redhat.com>
Date:   Wed Aug 26 10:30:15 2020 +0200

    dwarf2out: Fix up dwarf2out_next_real_insn caching [PR96729]

    The addition of NOTE_INSN_BEGIN_STMT and NOTE_INSN_INLINE_ENTRY notes
    reintroduced quadratic behavior into dwarf2out_var_location.
    This function needs to know the next real instruction to which the var
    location note applies, but the way final_scan_insn is called outside of
    final.c main loop doesn't make it easy to look up the next real insn in
    there (and for non-dwarf it is even useless).  Usually next real insn is
    only a few notes away, but we can have hundreds of thousands of consecutive
    notes only followed by a real insn.  dwarf2out_var_location to avoid the
    quadratic behavior contains a cache, it remembers the next note and when it
    is called again on that loc_note, it can use the previously computed
    dwarf2out_next_real_insn result, rather than walking the insn chain once
    again.  But, for NOTE_INSN_{BEGIN_STMT,INLINE_ENTRY} dwarf2out_var_location
    is not called while the code puts into the cache those notes, which means
if
    we have e.g. in the worst case NOTE_INSN_VAR_LOCATION and
    NOTE_INSN_BEGIN_STMT notes alternating, the cache is not really used.

    The following patch fixes it by looking up the next NOTE_INSN_VAR_LOCATION
    if any.  While the lookup could be perhaps done together with looking for
    the next real insn once (e.g. in dwarf2out_next_real_insn or its copy),
    there are other dwarf2out_next_real_insn callers which don't need/want that
    behavior and if there are more than two NOTE_INSN_VAR_LOCATION notes
    followed by the same real insn, we need to do that "find next
    NOTE_INSN_VAR_LOCATION" walk anyway.

    On the testcase from the PR this patch speeds it 2.8times, from 0m0.674s
    to 0m0.236s (why it takes for the reporter more than 60s is unknown).

    2020-08-26  Jakub Jelinek  <jakub@redhat.com>

            PR debug/96729
            * dwarf2out.c (dwarf2out_next_real_insn): Adjust function comment.
            (dwarf2out_var_location): Look for next_note only if next_real is
            non-NULL, in that case look for the first non-deleted
            NOTE_INSN_VAR_LOCATION between loc_note and next_real, if any.

[Bug debug/96729] [11 Regression] slow compile with `-g -O3` since r11-39-gf9e1ea10e657af9f

[cvs-commit at gcc dot gnu.org]

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

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

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

commit r10-8728-gede01bd9adf55f43598036d21d5db3d95dfd24a3
Author: Jakub Jelinek <jakub@redhat.com>
Date:   Wed Aug 26 10:30:15 2020 +0200

    dwarf2out: Fix up dwarf2out_next_real_insn caching [PR96729]

    The addition of NOTE_INSN_BEGIN_STMT and NOTE_INSN_INLINE_ENTRY notes
    reintroduced quadratic behavior into dwarf2out_var_location.
    This function needs to know the next real instruction to which the var
    location note applies, but the way final_scan_insn is called outside of
    final.c main loop doesn't make it easy to look up the next real insn in
    there (and for non-dwarf it is even useless).  Usually next real insn is
    only a few notes away, but we can have hundreds of thousands of consecutive
    notes only followed by a real insn.  dwarf2out_var_location to avoid the
    quadratic behavior contains a cache, it remembers the next note and when it
    is called again on that loc_note, it can use the previously computed
    dwarf2out_next_real_insn result, rather than walking the insn chain once
    again.  But, for NOTE_INSN_{BEGIN_STMT,INLINE_ENTRY} dwarf2out_var_location
    is not called while the code puts into the cache those notes, which means
if
    we have e.g. in the worst case NOTE_INSN_VAR_LOCATION and
    NOTE_INSN_BEGIN_STMT notes alternating, the cache is not really used.

    The following patch fixes it by looking up the next NOTE_INSN_VAR_LOCATION
    if any.  While the lookup could be perhaps done together with looking for
    the next real insn once (e.g. in dwarf2out_next_real_insn or its copy),
    there are other dwarf2out_next_real_insn callers which don't need/want that
    behavior and if there are more than two NOTE_INSN_VAR_LOCATION notes
    followed by the same real insn, we need to do that "find next
    NOTE_INSN_VAR_LOCATION" walk anyway.

    On the testcase from the PR this patch speeds it 2.8times, from 0m0.674s
    to 0m0.236s (why it takes for the reporter more than 60s is unknown).

    2020-08-26  Jakub Jelinek  <jakub@redhat.com>

            PR debug/96729
            * dwarf2out.c (dwarf2out_next_real_insn): Adjust function comment.
            (dwarf2out_var_location): Look for next_note only if next_real is
            non-NULL, in that case look for the first non-deleted
            NOTE_INSN_VAR_LOCATION between loc_note and next_real, if any.

    (cherry picked from commit ca1afa261d03c9343dff1208325f87d9ba69ec7a)

[Bug debug/96729] [11 Regression] slow compile with `-g -O3` since r11-39-gf9e1ea10e657af9f

[cvs-commit at gcc dot gnu.org]

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

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

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

commit r9-8911-gace10c37de7c2f9f2d419337dc1f173c01f7ec7d
Author: Jakub Jelinek <jakub@redhat.com>
Date:   Wed Aug 26 10:30:15 2020 +0200

    dwarf2out: Fix up dwarf2out_next_real_insn caching [PR96729]

    The addition of NOTE_INSN_BEGIN_STMT and NOTE_INSN_INLINE_ENTRY notes
    reintroduced quadratic behavior into dwarf2out_var_location.
    This function needs to know the next real instruction to which the var
    location note applies, but the way final_scan_insn is called outside of
    final.c main loop doesn't make it easy to look up the next real insn in
    there (and for non-dwarf it is even useless).  Usually next real insn is
    only a few notes away, but we can have hundreds of thousands of consecutive
    notes only followed by a real insn.  dwarf2out_var_location to avoid the
    quadratic behavior contains a cache, it remembers the next note and when it
    is called again on that loc_note, it can use the previously computed
    dwarf2out_next_real_insn result, rather than walking the insn chain once
    again.  But, for NOTE_INSN_{BEGIN_STMT,INLINE_ENTRY} dwarf2out_var_location
    is not called while the code puts into the cache those notes, which means
if
    we have e.g. in the worst case NOTE_INSN_VAR_LOCATION and
    NOTE_INSN_BEGIN_STMT notes alternating, the cache is not really used.

    The following patch fixes it by looking up the next NOTE_INSN_VAR_LOCATION
    if any.  While the lookup could be perhaps done together with looking for
    the next real insn once (e.g. in dwarf2out_next_real_insn or its copy),
    there are other dwarf2out_next_real_insn callers which don't need/want that
    behavior and if there are more than two NOTE_INSN_VAR_LOCATION notes
    followed by the same real insn, we need to do that "find next
    NOTE_INSN_VAR_LOCATION" walk anyway.

    On the testcase from the PR this patch speeds it 2.8times, from 0m0.674s
    to 0m0.236s (why it takes for the reporter more than 60s is unknown).

    2020-08-26  Jakub Jelinek  <jakub@redhat.com>

            PR debug/96729
            * dwarf2out.c (dwarf2out_next_real_insn): Adjust function comment.
            (dwarf2out_var_location): Look for next_note only if next_real is
            non-NULL, in that case look for the first non-deleted
            NOTE_INSN_VAR_LOCATION between loc_note and next_real, if any.

    (cherry picked from commit ca1afa261d03c9343dff1208325f87d9ba69ec7a)

[Bug debug/96729] [11 Regression] slow compile with `-g -O3` since r11-39-gf9e1ea10e657af9f

[jakub at gcc dot gnu.org]

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

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

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

--- Comment #11 from Jakub Jelinek <jakub at gcc dot gnu.org> ---
Caching reenabled for 8.5 in r8-10514-g36290fcee3b6f1bb71dad0aaba7a68e71d825b74
and for 9.4+, 10.3+ and 11.1+ by the above commits.