[Bug c/111554] New: Timeout with with "-O3 -fno-dse -fno-inline -fno-store-merging -fno-toplevel-reorder -fno-tree-dce -fno-tree-dse"

[Bug c/111554] New: Timeout with with "-O3 -fno-dse -fno-inline -fno-store-merging -fno-toplevel-reorder -fno-tree-dce -fno-tree-dse"

[19373742 at buaa dot edu.cn]

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

            Bug ID: 111554
           Summary: Timeout with with "-O3 -fno-dse -fno-inline
                    -fno-store-merging -fno-toplevel-reorder -fno-tree-dce
                    -fno-tree-dse"
           Product: gcc
           Version: 14.0
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: c
          Assignee: unassigned at gcc dot gnu.org
          Reporter: 19373742 at buaa dot edu.cn
  Target Milestone: ---

Created attachment 55974
  --> https://gcc.gnu.org/bugzilla/attachment.cgi?id=55974&action=edit
The preprocessed file

*******************************************************************************
OS and Platform:
Ubuntu 20.04.4 LTS
*******************************************************************************
gcc version:
$ gcc -v
Using built-in specs.
COLLECT_GCC=/home/cuisk/ctc/gcc-releases/gcc-14/bin/gcc
COLLECT_LTO_WRAPPER=/home/cuisk/ctc/gcc-releases/gcc-14/libexec/gcc/x86_64-pc-linux-gnu/14.0.0/lto-wrapper
Target: x86_64-pc-linux-gnu
Configured with: ./configure --prefix=/home/cuisk/ctc/gcc-releases/gcc-14
--disable-multilib --enable-language=c,c++
Thread model: posix
Supported LTO compression algorithms: zlib
gcc version 14.0.0 20230917 (experimental) (GCC)
*******************************************************************************
Command Lines:
$ (ulimit -t 60; gcc -I /home/csmith/include/csmith-2.3.0 -O3 -fno-dse
-fno-inline -fno-store-merging -fno-toplevel-reorder -fno-tree-dce
-fno-tree-dse a.c -o tle.o)

gcc: fatal error: Killed signal terminated program cc1
compilation terminated.

$ (ulimit -t 60; /home/cuisk/ctc/gcc-releases/gcc-14/bin/gcc -I
/home/cuisk/ctc/csmith/include/csmith-2.3.0 -save-temps /home/cuisk/gcc/tmp/a.c
-o tle2.o 2>tle.out)
$./tle2.o
checksum = 0

[Bug c/111554] Timeout with with "-O3 -fno-dse -fno-inline -fno-store-merging -fno-toplevel-reorder -fno-tree-dce -fno-tree-dse"

[19373742 at buaa dot edu.cn]

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

--- Comment #1 from CTC <19373742 at buaa dot edu.cn> ---
Created attachment 55975
  --> https://gcc.gnu.org/bugzilla/attachment.cgi?id=55975&action=edit
The compiler output

[Bug rtl-optimization/111554] Timeout with with "-O3 -fno-dse -fno-inline -fno-store-merging -fno-toplevel-reorder -fno-tree-dce -fno-tree-dse"

[pinskia at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
          Component|middle-end                  |rtl-optimization

--- Comment #2 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
#0  sd_find_dep_between_no_cache (pro=pro@entry=0x7ffff77bb080,
con=con@entry=0x7ffff6a00c40, resolved_p=resolved_p@entry=false,
sd_it_ptr=sd_it_ptr@entry=0x7fffffffd680) at
/home/apinski/src/upstream-gcc-git/gcc/gcc/sched-deps.cc:867
#1  0x0000000001e89a43 in add_or_update_dep_1 (new_dep=0x7fffffffd6e0,
resolved_p=<optimized out>, mem1=0x0, mem2=0x0) at
/home/apinski/src/upstream-gcc-git/gcc/gcc/sched-deps.cc:1260
#2  0x0000000001e89e1a in haifa_note_dep (elem=<optimized out>, ds=<optimized
out>) at /home/apinski/src/upstream-gcc-git/gcc/gcc/sched-deps.cc:1867
#3  0x0000000001e80cd3 in note_dep (ds=<optimized out>, e=<optimized out>) at
/home/apinski/src/upstream-gcc-git/gcc/gcc/sched-deps.cc:1902
#4  add_dependence_1 (insn=<optimized out>, elem=<optimized out>,
dep_type=<optimized out>) at
/home/apinski/src/upstream-gcc-git/gcc/gcc/sched-deps.cc:4294
#5  0x0000000001e82e2f in find_inc (mii=0x7fffffffd850, backwards=true) at
/home/apinski/src/upstream-gcc-git/gcc/gcc/sched-deps.cc:4844
#6  0x0000000001e830c2 in find_mem (mii=0x7fffffffd850, address_of_x=<optimized
out>) at /home/apinski/src/upstream-gcc-git/gcc/gcc/sched-deps.cc:4911
#7  0x0000000001e82ffe in find_mem (mii=0x7fffffffd850, address_of_x=<optimized
out>) at /home/apinski/src/upstream-gcc-git/gcc/gcc/sched-deps.cc:4928
#8  0x0000000001e8a22f in find_modifiable_mems (head=<optimized out>,
tail=<optimized out>) at /home/apinski/src/upstream-gcc-git/gcc/gcc/rtl.h:1511
#9  0x0000000001dc55f9 in schedule_block
(target_bb=target_bb@entry=0x7fffffffd9b8, init_state=0x31cf3c0) at
/home/apinski/src/upstream-gcc-git/gcc/gcc/haifa-sched.cc:6498
#10 0x0000000000faf84b in schedule_region (rgn=0) at
/home/apinski/src/upstream-gcc-git/gcc/gcc/sched-rgn.cc:3205
#11 schedule_insns () at
/home/apinski/src/upstream-gcc-git/gcc/gcc/sched-rgn.cc:3532
#12 0x0000000000fafb4e in schedule_insns () at
/home/apinski/src/upstream-gcc-git/gcc/gcc/sched-rgn.cc:3518
#13 rest_of_handle_sched2 () at
/home/apinski/src/upstream-gcc-git/gcc/gcc/sched-rgn.cc:3756
#14 (anonymous namespace)::pass_sched2::execute (this=<optimized out>) at
/home/apinski/src/upstream-gcc-git/gcc/gcc/sched-rgn.cc:3895

[Bug rtl-optimization/111554] [12/13/14 regression] Timeout with with "-O3 -fno-dse -fno-inline -fno-store-merging -fno-toplevel-reorder -fno-tree-dce -fno-tree-dse"

[sjames at gcc dot gnu.org]

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

Sam James <sjames at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |sjames at gcc dot gnu.org
            Summary|Timeout with with "-O3      |[12/13/14 regression]
                   |-fno-dse -fno-inline        |Timeout with with "-O3
                   |-fno-store-merging          |-fno-dse -fno-inline
                   |-fno-toplevel-reorder       |-fno-store-merging
                   |-fno-tree-dce               |-fno-toplevel-reorder
                   |-fno-tree-dse"              |-fno-tree-dce
                   |                            |-fno-tree-dse"

--- Comment #3 from Sam James <sjames at gcc dot gnu.org> ---
10/11 are both pretty fast for me with -O2, then 12/13/14 are all stuck with
-O2 or -O3

[Bug rtl-optimization/111554] [12/13/14 regression] Timeout with with "-O3 -fno-dse -fno-inline -fno-store-merging -fno-toplevel-reorder -fno-tree-dce -fno-tree-dse"

[pinskia at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
   Target Milestone|---                         |11.5

[Bug rtl-optimization/111554] [12/13/14 regression] Timeout with with "-O3 -fno-dse -fno-inline -fno-store-merging -fno-toplevel-reorder -fno-tree-dce -fno-tree-dse" since r12-2097-g9f34b780b0461e

[sjames at gcc dot gnu.org]

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

Sam James <sjames at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |rguenth at gcc dot gnu.org
            Summary|[12/13/14 regression]       |[12/13/14 regression]
                   |Timeout with with "-O3      |Timeout with with "-O3
                   |-fno-dse -fno-inline        |-fno-dse -fno-inline
                   |-fno-store-merging          |-fno-store-merging
                   |-fno-toplevel-reorder       |-fno-toplevel-reorder
                   |-fno-tree-dce               |-fno-tree-dce
                   |-fno-tree-dse"              |-fno-tree-dse" since
                   |                            |r12-2097-g9f34b780b0461e

--- Comment #4 from Sam James <sjames at gcc dot gnu.org> ---
Bisect says r12-2097-g9f34b780b0461e:

9f34b780b0461ec7b2b2defe96e44ab616ea2aa3 is the first bad commit
commit 9f34b780b0461ec7b2b2defe96e44ab616ea2aa3
Author: Richard Biener <rguenther@suse.de>
Date:   Wed Jul 7 11:41:03 2021 +0200

    tree-optimization/99728 - improve LIM for loops with aggregate copies

    This improves LIM by recording aggregate copies for disambiguation
    purposes instead of as UNANALYZABLE_MEM which will prevent any
    invariant or store motion across it.  This allows four of the six
    references in the loop of the testcase to be promoted.

    2021-07-07  Richard Biener  <rguenther@suse.de>

I'm not sure if that's right though. I can rerun it if it sounds dubious.

[Bug rtl-optimization/111554] [12/13/14 regression] Timeout with with "-O3 -fno-dse -fno-inline -fno-store-merging -fno-toplevel-reorder -fno-tree-dce -fno-tree-dse" since r12-2097-g9f34b780b0461e

[pinskia at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
   Target Milestone|11.5                        |12.4

[Bug rtl-optimization/111554] [12/13/14 regression] Timeout with with "-O3 -fno-dse -fno-inline -fno-store-merging -fno-toplevel-reorder -fno-tree-dce -fno-tree-dse" since r12-2097-g9f34b780b0461e

[pinskia at gcc dot gnu.org]

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

--- Comment #5 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
Reducing ...

[Bug rtl-optimization/111554] [12/13/14 regression] Timeout with with "-O3 -fno-dse -fno-inline -fno-store-merging -fno-toplevel-reorder -fno-tree-dce -fno-tree-dse" since r12-2097-g9f34b780b0461e

[pinskia at gcc dot gnu.org]

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

--- Comment #6 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
Created attachment 56172
  --> https://gcc.gnu.org/bugzilla/attachment.cgi?id=56172&action=edit
Testcase that takes ~8second

For this reduced testcase:
 scheduling 2                       :   7.66 ( 90%)   0.02 ( 50%)   7.69 ( 89%)
  134k (  1%)

[Bug rtl-optimization/111554] [12/13/14 regression] Timeout with with "-O3 -fno-dse -fno-inline -fno-store-merging -fno-toplevel-reorder -fno-tree-dce -fno-tree-dse" since r12-2097-g9f34b780b0461e

[pinskia at gcc dot gnu.org]

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

--- Comment #7 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
(In reply to Andrew Pinski from comment #6)
> Created attachment 56172 [details]
> Testcase that takes ~8second
> 
> For this reduced testcase:
>  scheduling 2                       :   7.66 ( 90%)   0.02 ( 50%)   7.69 (
> 89%)   134k (  1%)


This definitely shows some compile time issue as `-O3` without any other option
is very quick.

[Bug rtl-optimization/111554] [12/13/14 regression] Timeout with with "-O3 -fno-dse -fno-inline -fno-store-merging -fno-toplevel-reorder -fno-tree-dce -fno-tree-dse" since r12-2097-g9f34b780b0461e

[rguenth at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |mkuvyrkov at gcc dot gnu.org
             Status|UNCONFIRMED                 |NEW
   Last reconfirmed|                            |2023-10-23
     Ever confirmed|0                           |1

--- Comment #8 from Richard Biener <rguenth at gcc dot gnu.org> ---
Most definitely something like

      /* Find the dep_link with consumer CON in producer's forw_deps.  */
      FOR_EACH_DEP (pro, pro_list_type, sd_it, dep)
        if (DEP_CON (dep) == con)
          {
            found_p = true;
            break;
          }

is quite bad engineering.  The LIM change probably just triggered this to be
observable.

git puts the blame on Maxim, but he might just have refactored the code.  Still
he's the remaining scheduler expert, so ... ;)

[Bug rtl-optimization/111554] [12/13/14 regression] Timeout with with "-O3 -fno-dse -fno-inline -fno-store-merging -fno-toplevel-reorder -fno-tree-dce -fno-tree-dse" since r12-2097-g9f34b780b0461e

[mkuvyrkov at gcc dot gnu.org]

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

Maxim Kuvyrkov <mkuvyrkov at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
           Assignee|unassigned at gcc dot gnu.org      |mkuvyrkov at gcc dot gnu.org

--- Comment #9 from Maxim Kuvyrkov <mkuvyrkov at gcc dot gnu.org> ---
Taking.

[Bug rtl-optimization/111554] [12/13/14 regression] Timeout with with "-O3 -fno-dse -fno-inline -fno-store-merging -fno-toplevel-reorder -fno-tree-dce -fno-tree-dse" since r12-2097-g9f34b780b0461e

[mkuvyrkov at gcc dot gnu.org]

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

Maxim Kuvyrkov <mkuvyrkov at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|NEW                         |ASSIGNED

--- Comment #10 from Maxim Kuvyrkov <mkuvyrkov at gcc dot gnu.org> ---
This is, mostly, a dup of PR96388.
With the problem in PR96388 fixed, I'm seeing strange -ftime-report reporting
that [wrongly?] attributes a lot of time to alias analysis.

[Bug rtl-optimization/111554] [12/13/14 regression] Timeout with with "-O3 -fno-dse -fno-inline -fno-store-merging -fno-toplevel-reorder -fno-tree-dce -fno-tree-dse" since r12-2097-g9f34b780b0461e

[rguenth at gcc dot gnu.org]

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

--- Comment #11 from Richard Biener <rguenth at gcc dot gnu.org> ---
(In reply to Maxim Kuvyrkov from comment #10)
> This is, mostly, a dup of PR96388.
> With the problem in PR96388 fixed, I'm seeing strange -ftime-report
> reporting that [wrongly?] attributes a lot of time to alias analysis.

You can try -ftime-report -ftime-report-details (yeah, two options),
this lists "dependent" times in other timevars beyond the passes using them.

[Bug rtl-optimization/111554] [12/13/14 regression] Timeout with with "-O3 -fno-dse -fno-inline -fno-store-merging -fno-toplevel-reorder -fno-tree-dce -fno-tree-dse" since r12-2097-g9f34b780b0461e

[mkuvyrkov at gcc dot gnu.org]

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

--- Comment #12 from Maxim Kuvyrkov <mkuvyrkov at gcc dot gnu.org> ---
(In reply to Richard Biener from comment #11)
> (In reply to Maxim Kuvyrkov from comment #10)
> > This is, mostly, a dup of PR96388.
> > With the problem in PR96388 fixed, I'm seeing strange -ftime-report
> > reporting that [wrongly?] attributes a lot of time to alias analysis.
> 
> You can try -ftime-report -ftime-report-details (yeah, two options),
> this lists "dependent" times in other timevars beyond the passes using them.

Ack, thanks, Richard.

Posted patch in
https://gcc.gnu.org/pipermail/gcc-patches/2023-November/637419.html .

[Bug rtl-optimization/111554] [12/13/14 regression] Timeout with with "-O3 -fno-dse -fno-inline -fno-store-merging -fno-toplevel-reorder -fno-tree-dce -fno-tree-dse" since r12-2097-g9f34b780b0461e

[cvs-commit at gcc dot gnu.org]

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

--- Comment #13 from GCC Commits <cvs-commit at gcc dot gnu.org> ---
The master branch has been updated by Maxim Kuvyrkov <mkuvyrkov@gcc.gnu.org>:

https://gcc.gnu.org/g:0c42d1782e48d8ad578ace2065cce9b3615f97c0

commit r14-8174-g0c42d1782e48d8ad578ace2065cce9b3615f97c0
Author: Maxim Kuvyrkov <maxim.kuvyrkov@linaro.org>
Date:   Sun Nov 19 08:43:05 2023 +0000

    sched-deps.cc (find_modifiable_mems): Avoid exponential behavior [PR96388]

    This patch avoids sched-deps.cc:find_inc() creating exponential number
    of dependencies, which become memory and compilation time hogs.
    Consider example (simplified from PR96388) ...
    ===
    sp=sp-4 // sp_insnA
    mem_insnA1[sp+A1]
    ...
    mem_insnAN[sp+AN]
    sp=sp-4 // sp_insnB
    mem_insnB1[sp+B1]
    ...
    mem_insnBM[sp+BM]
    ===

    [For simplicity, let's assume find_inc(backwards==true)].
    In this example find_modifiable_mems() will arrange for mem_insnA*
    to be able to pass sp_insnA, and, while doing this, will create
    dependencies between all mem_insnA*s and sp_insnB -- because sp_insnB
    is a consumer of sp_insnA.  After this sp_insnB will have N new
    backward dependencies.
    Then find_modifiable_mems() gets to mem_insnB*s and starts to create
    N new dependencies for _every_ mem_insnB*.  This gets us N*M new
    dependencies.

    In PR96833's testcase N and M are 10k-15k, which causes RAM usage of
    30GB and compilation time of 30 minutes, with sched2 accounting for
    95% of both metrics.  After this patch the RAM usage is down to 1GB
    and compilation time is down to 3-4 minutes, with sched2 no longer
    standing out on -ftime-report or memory usage.

    gcc/ChangeLog:

            PR rtl-optimization/96388
            PR rtl-optimization/111554
            * sched-deps.cc (find_inc): Avoid exponential behavior.

[Bug rtl-optimization/111554] [12/13 regression] Timeout with with "-O3 -fno-dse -fno-inline -fno-store-merging -fno-toplevel-reorder -fno-tree-dce -fno-tree-dse" since r12-2097-g9f34b780b0461e

[rguenth at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
            Summary|[12/13/14 regression]       |[12/13 regression] Timeout
                   |Timeout with with "-O3      |with with "-O3 -fno-dse
                   |-fno-dse -fno-inline        |-fno-inline
                   |-fno-store-merging          |-fno-store-merging
                   |-fno-toplevel-reorder       |-fno-toplevel-reorder
                   |-fno-tree-dce               |-fno-tree-dce
                   |-fno-tree-dse" since        |-fno-tree-dse" since
                   |r12-2097-g9f34b780b0461e    |r12-2097-g9f34b780b0461e
           Priority|P3                          |P2
      Known to work|                            |14.0

--- Comment #14 from Richard Biener <rguenth at gcc dot gnu.org> ---
Fixed on trunk which now takes 1.4s on my machine.  There is the reported
'alias stmt walking' costs which is somewhat expected.

 tree FRE                           :   0.02 (  1%)   0.00 (  0%)   0.04 (  2%)
 1126k (  3%)
 `- alias stmt walking              :   0.52 ( 34%)   0.03 ( 18%)   0.52 ( 30%)
  248k (  1%)
 tree PRE                           :   0.02 (  1%)   0.00 (  0%)   0.02 (  1%)
  751k (  2%)
 `- alias stmt walking              :   0.17 ( 11%)   0.00 (  0%)   0.17 ( 10%)
   75k (  0%)

I don't think it's necessary to backport this unless we get to see a testcase
that doesn't require turning off so many passes.

[Bug rtl-optimization/111554] [12/13 regression] Timeout with with "-O3 -fno-dse -fno-inline -fno-store-merging -fno-toplevel-reorder -fno-tree-dce -fno-tree-dse" since r12-2097-g9f34b780b0461e

[mkuvyrkov at gcc dot gnu.org]

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

Maxim Kuvyrkov <mkuvyrkov at gcc dot gnu.org> changed:

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

--- Comment #15 from Maxim Kuvyrkov <mkuvyrkov at gcc dot gnu.org> ---
Richard,

Thanks for confirming.  I was about to do the same.

[Bug rtl-optimization/111554] [12/13 regression] Timeout with with "-O3 -fno-dse -fno-inline -fno-store-merging -fno-toplevel-reorder -fno-tree-dce -fno-tree-dse" since r12-2097-g9f34b780b0461e

[rguenth at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
   Target Milestone|12.4                        |14.0