[Bug c++/54052] New: Segmentation Fault

[Bug c++/54052] New: Segmentation Fault

[baxter at about dot org]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=54052

             Bug #: 54052
           Summary: Segmentation Fault
    Classification: Unclassified
           Product: gcc
           Version: 4.5.3
            Status: UNCONFIRMED
          Severity: blocker
          Priority: P3
         Component: c++
        AssignedTo: unassigned@gcc.gnu.org
        ReportedBy: baxter@about.org


Command line: g++ -Wno-system-headers -Wall -Wextra -ansi -pedantic -O6   -c -o
test08.o test08.cpp -save-temps

Version: g++ -v
Utilisation des specs internes.
COLLECT_GCC=g++
COLLECT_LTO_WRAPPER=/usr/lib/gcc/i686-pc-cygwin/4.5.3/lto-wrapper.exe
Target: i686-pc-cygwin
Configuré avec:
/gnu/gcc/releases/respins/4.5.3-3/gcc4-4.5.3-3/src/gcc-4.5.3/configure
--srcdir=/gnu/gcc/releases/respins/4.5.3-3/gc
c4-4.5.3-3/src/gcc-4.5.3 --prefix=/usr --exec-prefix=/usr --bindir=/usr/bin
--sbindir=/usr/sbin --libexecdir=/usr/lib --datadir=/usr
/share --localstatedir=/var --sysconfdir=/etc --datarootdir=/usr/share
--docdir=/usr/share/doc/gcc4 -C --datadir=/usr/share --infodi
r=/usr/share/info --mandir=/usr/share/man -v --with-gmp=/usr --with-mpfr=/usr
--enable-bootstrap --enable-version-specific-runtime-l
ibs --libexecdir=/usr/lib --enable-static --enable-shared
--enable-shared-libgcc --disable-__cxa_atexit --with-gnu-ld --with-gnu-as
--with-dwarf2 --disable-sjlj-exceptions
--enable-languages=ada,c,c++,fortran,java,lto,objc,obj-c++ --enable-graphite
--enable-lto --
enable-java-awt=gtk --disable-symvers --enable-libjava --program-suffix=-4
--enable-libgomp --enable-libssp --enable-libada --enable
-threads=posix --with-arch=i686 --with-tune=generic --enable-libgcj-sublibs
CC=gcc-4 CXX=g++-4 CC_FOR_TARGET=gcc-4 CXX_FOR_TARGET=g+
+-4 GNATMAKE_FOR_TARGET=gnatmake GNATBIND_FOR_TARGET=gnatbind
--with-ecj-jar=/usr/share/java/ecj.jar
Modèle de thread: posix
gcc version 4.5.3 (GCC)

Same bug seen with g++ 4.6.3 on ubuntu

Output:
test08.cpp: In function 'int main()':
test08.cpp:2467:2: erreur interne du compilateur: Segmentation fault
Veuillez soumettre un rapport complet d'anomalies,
avec le source pré-traité si nécessaire.
Consultez <http://gcc.gnu.org/bugs.html> pour plus de détail.
<builtin>: recipe for target `test08.o' failed

[Bug c++/54052] Segmentation Fault

[baxter at about dot org]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=54052

Christophe DUVERGER <baxter at about dot org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Target|i686-pc-cygwin              |i686-linux-gnu

--- Comment #1 from Christophe DUVERGER <baxter at about dot org> 2012-07-24 16:04:16 UTC ---
With g++ 4.6.3:

Output:
g++ -Wno-system-headers -Wall -Wextra -ansi -pedantic -O6   -c -o test08.o
test08.cpp

cc1plus: out of memory allocating 408 bytes after a total of 917585920 bytes

Version:
Utilisation des specs internes.
COLLECT_GCC=g++
COLLECT_LTO_WRAPPER=/usr/lib/gcc/i686-linux-gnu/4.6/lto-wrapper
Target: i686-linux-gnu
Configuré avec: ../src/configure -v --with-pkgversion='Ubuntu/Linaro
4.6.3-1ubuntu5' --with-bugurl=file:///usr/share/doc/gcc-4.6/README.Bugs
--enable-languages=c,c++,fortran,objc,obj-c++ --prefix=/usr
--program-suffix=-4.6 --enable-shared --enable-linker-build-id
--with-system-zlib --libexecdir=/usr/lib --without-included-gettext
--enable-threads=posix --with-gxx-include-dir=/usr/include/c++/4.6
--libdir=/usr/lib --enable-nls --with-sysroot=/ --enable-clocale=gnu
--enable-libstdcxx-debug --enable-libstdcxx-time=yes --enable-gnu-unique-object
--enable-plugin --enable-objc-gc --enable-targets=all --disable-werror
--with-arch-32=i686 --with-tune=generic --enable-checking=release
--build=i686-linux-gnu --host=i686-linux-gnu --target=i686-linux-gnu
Modèle de thread: posix
gcc version 4.6.3 (Ubuntu/Linaro 4.6.3-1ubuntu5)

[Bug c++/54052] Segmentation Fault

[redi at gcc dot gnu.org]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=54052

Jonathan Wakely <redi at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|UNCONFIRMED                 |WAITING
   Last reconfirmed|                            |2012-07-24
     Ever Confirmed|0                           |1
           Severity|blocker                     |normal

--- Comment #2 from Jonathan Wakely <redi at gcc dot gnu.org> 2012-07-24 16:19:19 UTC ---
You probably ran out of memory, but unless you do as requested then noone will
ever know:

Veuillez soumettre un rapport complet d'anomalies,
avec le source pré-traité si nécessaire.
Consultez <http://gcc.gnu.org/bugs.html> pour plus de détail.
<builtin>: recipe for target `test08.o' failed

[Bug c++/54052] Segmentation Fault

[baxter at about dot org]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=54052

--- Comment #3 from Christophe DUVERGER <baxter at about dot org> 2012-07-24 18:29:00 UTC ---
I have added the source file test08.ii on the link URL
(http://dl.free.fr/qK5B6KvjM) because I can not attach the file to the bug
report (test08.ii is 1,5Mo)

[Bug c++/54052] Segmentation Fault

[redi at gcc dot gnu.org]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=54052

--- Comment #4 from Jonathan Wakely <redi at gcc dot gnu.org> 2012-07-24 18:37:18 UTC ---
Have you tried compressing it?

That URL is an HTML page on some unknown site, not a .ii file, so I can't
download it with wget and am not opening it in my browser.

[Bug c++/54052] Segmentation Fault

[baxter at about dot org]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=54052

--- Comment #5 from Christophe DUVERGER <baxter at about dot org> 2012-07-24 20:33:47 UTC ---
Created attachment 27868
  --> http://gcc.gnu.org/bugzilla/attachment.cgi?id=27868
test08.ii file

[Bug c++/54052] Segmentation Fault

[paolo.carlini at oracle dot com]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=54052

Paolo Carlini <paolo.carlini at oracle dot com> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|WAITING                     |UNCONFIRMED
                 CC|baxter at about dot org     |
     Ever Confirmed|1                           |0

[Bug c++/54052] [11/12/13/14 Regression] g++ takes excessive time in opt and generate phase; can lead to Segmentation Fault when not enough memory available

[rguenth at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |rguenth at gcc dot gnu.org,
                   |                            |rsandifo at gcc dot gnu.org
            Summary|g++ takes excessive time in |[11/12/13/14 Regression]
                   |opt and generate phase; can |g++ takes excessive time in
                   |lead to Segmentation Fault  |opt and generate phase; can
                   |when not enough memory      |lead to Segmentation Fault
                   |available                   |when not enough memory
                   |                            |available
   Last reconfirmed|2018-09-18 00:00:00         |2024-2-16
   Target Milestone|---                         |11.5

--- Comment #10 from Richard Biener <rguenth at gcc dot gnu.org> ---
GCC 14:

-O0  800MB in 10s
-O1  1.2GB in 30min (!)

SSA construction (rtl_ssa::function_info::place_phis) takes forever.

 forward prop                       :1669.98 ( 95%)
 combiner                           :  34.80 (  2%)
 TOTAL                              :1749.78

unsurprisingly -fno-forward-propagate helps a lot, compile-time down to 76s.

GCC 11 seems to be similarly slow, stopped after some minutes,
-fno-forward-propagate helps as well (63s).

GCC 10 (no RTL SSA):

-O1  1GB in 70s

 dominance frontiers                :  13.69 ( 19%)
 combiner                           :  36.62 ( 50%)

so there's at least a big regression from GCC 10 here.


The testcase might be a bit large to work with and I didn't profile but
for -O1 we need some "fix" here, even if it might be simply giving up
for some CFG + nregs characteristics that makes things blow up here.

[Bug middle-end/54052] [11/12/13/14 Regression] g++ takes excessive time in opt and generate phase; can lead to Segmentation Fault when not enough memory available

[rguenth at gcc dot gnu.org]

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

--- Comment #11 from Richard Biener <rguenth at gcc dot gnu.org> ---
Btw, just as expected:

Samples: 5M of event 'cycles:u', Event count (approx.): 8038399460939           
Overhead       Samples  Command  Shared Object       Symbol                     
  95.69%       5693007  cc1plus  cc1plus             [.] bitmap_ior_into
   0.62%         37954  cc1plus  cc1plus             [.]
get_last_value_validate
...

with

-   95.70%    95.67%       5717568  cc1plus  cc1plus             [.]
bitmap_ior_into                        #
     95.67% _start                                                             
                            #
        __libc_start_main                                                      
                            #
        main                                                                   
                            #
        toplev::main                                                           
                            #
        toplev::main                                                           
                            #
        compile_file                                                           
                            #
        symbol_table::finalize_compilation_unit                                
                            #
        symbol_table::compile (inlined)                                        
                            #
        symbol_table::compile                                                  
                            #
      - symbol_table::compile                                                  
                            #
         - 95.67% cgraph_node::expand                                          
                            #
              execute_pass_list                                                
                            #
            - execute_pass_list_1                                              
                            #
               - 95.67% execute_pass_list_1                                    
                            #
                  - 95.67% execute_one_pass                                    
                            #
                     - 95.66% fwprop                                           
                            #
                        - 95.66% fwprop_init (inlined)                         
                            #
                             rtl_ssa::function_info::function_info             
                            #
                           - rtl_ssa::function_info::process_all_blocks        
                            #
                              + 95.66% rtl_ssa::function_info::place_phis      
                            #

and it seems to be the

  // If block B1 defines R and if B2 is in the dominance frontier of B1,
  // queue a possible phi node for R in B2.
  auto_bitmap worklist;
  for (unsigned int b1 = 0; b1 < num_bb_indices; ++b1)
    {
      // Only access DF information for blocks that are known to exist.
      if (bitmap_empty_p (&frontiers[b1]))
        continue;

      bitmap b1_def = &DF_LR_BB_INFO (BASIC_BLOCK_FOR_FN (m_fn, b1))->def;
      bitmap_iterator bmi;
      unsigned int b2;
      EXECUTE_IF_SET_IN_BITMAP (&frontiers[b1], 0, b2, bmi)
        if (bitmap_ior_into (&unfiltered[b2], b1_def)
            && !bitmap_empty_p (&frontiers[b2]))
          // Propagate the (potential) new phi node definitions in B2.
          bitmap_set_bit (worklist, b2);
    }

loop.  This looks quadratic and I wonder if it is the best way to perform
PHI insertion ... possibly (since it seems to be some sort of propagation)
an improvement could be to work on RPO instead of BB index order, but
possibly this tries to compute the minimal set of PHIs required which
could be expensive - I don't remember GIMPLE SSA doing any sort of
"iteration" (but we do not compute all PHI insertions at the same time
but instead do it per variable).  The slowness (apart from the quadraticness)
might be as well because the working sets when processing all PHIs at the
same time is so large.

[Bug middle-end/54052] [11/12/13/14 Regression] g++ takes excessive time in opt and generate phase; can lead to Segmentation Fault when not enough memory available

[rguenth at gcc dot gnu.org]

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

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

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

--- Comment #12 from Richard Biener <rguenth at gcc dot gnu.org> ---
callgrind is of couse somewhat hopeless but after 20min we have seen
23229 blocks (over 17 invocations of the function) and sofar
155551845 invocations of bitmap_ior_into from that very place (line 652).

I wonder if we really need 'unfiltered' and could not "filter" it with
DF_LR_IN.  Because obviously computing all regs ever defined in any
dominated block requires quadratic memory?

Doing

diff --git a/gcc/rtl-ssa/blocks.cc b/gcc/rtl-ssa/blocks.cc
index 8996443e8d5..9d1cd1b0365 100644
--- a/gcc/rtl-ssa/blocks.cc
+++ b/gcc/rtl-ssa/blocks.cc
@@ -649,7 +649,8 @@ function_info::place_phis (build_info &bi)
       bitmap_iterator bmi;
       unsigned int b2;
       EXECUTE_IF_SET_IN_BITMAP (&frontiers[b1], 0, b2, bmi)
-       if (bitmap_ior_into (&unfiltered[b2], b1_def)
+       if (bitmap_ior_and_into (&unfiltered[b2], b1_def,
+                                DF_LR_IN (BASIC_BLOCK_FOR_FN (m_fn, b2)))
            && !bitmap_empty_p (&frontiers[b2]))
          // Propagate the (potential) new phi node definitions in B2.
          bitmap_set_bit (worklist, b2);

shrinks the compile-time of the testcase to 63s:

 forward prop                       :   3.02 (  5%)
 combiner                           :  30.01 ( 47%)
 TOTAL                              :  63.59
63.59user 0.84system 1:04.45elapsed 99%CPU (0avgtext+0avgdata
1127464maxresident)k
0inputs+25160outputs (0major+262276minor)pagefaults 0swaps

Untested, of course.  Testing now.

[Bug middle-end/54052] [11/12/13/14 Regression] g++ takes excessive time in opt and generate phase; can lead to Segmentation Fault when not enough memory available

[rguenth at gcc dot gnu.org]

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

--- Comment #13 from Richard Biener <rguenth at gcc dot gnu.org> ---
Btw, PR98863 was the last one triggering place_phis rewrite but I'm not sure
what actual testcase Richard used.  There's plenty of SPEC testers so the
original reported WRF case will show up again.

Unpatched on the same machine as last comment:

 forward prop                       :1359.71 ( 96%)
 combiner                           :  29.95 (  2%)
 TOTAL                              :1420.22          0.98       1421.51       
  596M
1420.22user 1.02system 23:41.57elapsed 99%CPU (0avgtext+0avgdata
1209924maxresident)k
0inputs+25096outputs (0major+355965minor)pagefaults 0swaps

interestingly peak memory usage is almost unchanged.

[Bug middle-end/54052] [11/12/13/14 Regression] g++ takes excessive time in opt and generate phase; can lead to Segmentation Fault when not enough memory available

[cvs-commit at gcc dot gnu.org]

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

--- Comment #14 from GCC 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:c7151283dc747769d4ac4f216d8f519bda2569b5

commit r14-9064-gc7151283dc747769d4ac4f216d8f519bda2569b5
Author: Richard Biener <rguenther@suse.de>
Date:   Mon Feb 19 11:10:50 2024 +0100

    rtl-optimization/54052 - RTL SSA PHI insertion compile-time hog

    The following tries to address the PHI insertion compile-time hog in
    RTL fwprop observed with the PR54052 testcase where the loop computing
    the "unfiltered" set of variables possibly needing PHI nodes for each
    block exhibits quadratic compile-time and memory-use.

    It does so by pruning the local DEFs with LR_OUT of the block, removing
    regs that can never be LR_IN (defined by this block) in the dominance
    frontier.

            PR rtl-optimization/54052
            * rtl-ssa/blocks.cc (function_info::place_phis): Filter
            local defs by LR_OUT.

[Bug middle-end/54052] [11/12/13 Regression] g++ takes excessive time in opt and generate phase; can lead to Segmentation Fault when not enough memory available

[rguenth at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
            Summary|[11/12/13/14 Regression]    |[11/12/13 Regression] g++
                   |g++ takes excessive time in |takes excessive time in opt
                   |opt and generate phase; can |and generate phase; can
                   |lead to Segmentation Fault  |lead to Segmentation Fault
                   |when not enough memory      |when not enough memory
                   |available                   |available

--- Comment #15 from Richard Biener <rguenth at gcc dot gnu.org> ---
We're back to GCC 10 performance on trunk now.

[Bug middle-end/54052] [11/12/13 Regression] g++ takes excessive time in opt and generate phase; can lead to Segmentation Fault when not enough memory available

[rguenth at gcc dot gnu.org]

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

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

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

[Bug middle-end/54052] [11/12/13 Regression] g++ takes excessive time in opt and generate phase; can lead to Segmentation Fault when not enough memory available

[cvs-commit at gcc dot gnu.org]

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

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

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

commit r13-8763-gd629308c699bb8fe90c2afeb7fa1acb12cb5526b
Author: Richard Biener <rguenther@suse.de>
Date:   Mon Feb 19 11:10:50 2024 +0100

    rtl-optimization/54052 - RTL SSA PHI insertion compile-time hog

    The following tries to address the PHI insertion compile-time hog in
    RTL fwprop observed with the PR54052 testcase where the loop computing
    the "unfiltered" set of variables possibly needing PHI nodes for each
    block exhibits quadratic compile-time and memory-use.

    It does so by pruning the local DEFs with LR_OUT of the block, removing
    regs that can never be LR_IN (defined by this block) in the dominance
    frontier.

            PR rtl-optimization/54052
            * rtl-ssa/blocks.cc (function_info::place_phis): Filter
            local defs by LR_OUT.

    (cherry picked from commit c7151283dc747769d4ac4f216d8f519bda2569b5)