[Bug ipa/62016] New: very slow compilation at -O3 on x86_64-linux-gnu

[Bug ipa/62016] New: very slow compilation at -O3 on x86_64-linux-gnu

[su at cs dot ucdavis.edu]

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

            Bug ID: 62016
           Summary: very slow compilation at -O3 on x86_64-linux-gnu
           Product: gcc
           Version: 4.10.0
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: ipa
          Assignee: unassigned at gcc dot gnu.org
          Reporter: su at cs dot ucdavis.edu

The following test case takes the current gcc trunk much longer to compile at
-O3 on x86_64-linux (in both 32-bit and 64-bit modes). 

It also affects gcc 4.8.x and 4.9.x, and is a regression from 4.7.x. 

This is likely due to the inliner as the code compiles fine with -fno-inline.  

$ gcc-trunk -v
Using built-in specs.
COLLECT_GCC=gcc-trunk
COLLECT_LTO_WRAPPER=/usr/local/gcc-trunk/libexec/gcc/x86_64-unknown-linux-gnu/4.10.0/lto-wrapper
Target: x86_64-unknown-linux-gnu
Configured with: ../gcc-trunk/configure --prefix=/usr/local/gcc-trunk
--enable-languages=c,c++ --disable-werror --enable-multilib
Thread model: posix
gcc version 4.10.0 20140804 (experimental) [trunk revision 213529] (GCC) 
$ 
$ time gcc-trunk -O2 small.c    
0.02user 0.01system 0:00.28elapsed 15%CPU (0avgtext+0avgdata 50912maxresident)k
0inputs+32outputs (1major+6643minor)pagefaults 0swaps
$ time gcc-4.7 -O3 small.c
0.11user 0.02system 0:00.71elapsed 19%CPU (0avgtext+0avgdata 65344maxresident)k
0inputs+32outputs (1major+7683minor)pagefaults 0swaps
$ 
$ time gcc-trunk -O3 -fno-inline small.c
0.04user 0.01system 0:00.47elapsed 12%CPU (0avgtext+0avgdata 51776maxresident)k
0inputs+32outputs (1major+6709minor)pagefaults 0swaps
$ 
$ time gcc-trunk -O3 small.c
8.43user 0.28system 0:34.83elapsed 25%CPU (0avgtext+0avgdata
1622880maxresident)k
0inputs+32outputs (1major+106347minor)pagefaults 0swaps
$ 


----------------------------------


#include <assert.h>

int a, b, c, d, e, f, g, h, i, j;

void
fn1 (int *p1, int *p2)
{
  for (; a; a++)
    {
      assert (p1 == 0);
      fn1 (0, p2);
      fn1 (&i, &b);
      fn1 (&f, 0);
    }
}

void
fn2 ()
{
  fn1 (&c, 0);
  fn1 (&d, 0);
  fn1 (&e, 0);
  fn1 (&g, 0);
  fn1 (&h, 0);
  fn1 (&j, 0);
}

int 
main ()
{
  fn2 (); 
  return 0; 
}

[Bug ipa/62016] [4.8/4.9/4.10 Regression] very slow compilation at -O3 on x86_64-linux-gnu

[rguenth at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
           Keywords|                            |compile-time-hog
             Status|UNCONFIRMED                 |NEW
   Last reconfirmed|                            |2014-08-05
   Target Milestone|---                         |4.8.4
            Summary|very slow compilation at    |[4.8/4.9/4.10 Regression]
                   |-O3 on x86_64-linux-gnu     |very slow compilation at
                   |                            |-O3 on x86_64-linux-gnu
     Ever confirmed|0                           |1

--- Comment #1 from Richard Biener <rguenth at gcc dot gnu.org> ---
Confirmed.  4.8 is slowest (very very slow), 4.9 is a lot better but still
100x slower than 4.7.

4.7:

 TOTAL                 :   0.09             0.01             0.10              
6621 kB

4.8:

<not finished after 6min 30s>

4.9:

 ipa inlining heuristics :   2.99 (93%) usr   0.12 (92%) sys   3.11 (93%) wall 
406507 kB (99%) ggc

4.10 (take with grain of salt - unoptimized and with checking):

 ipa inlining heuristics :   6.81 (90%) usr   0.15 (94%) sys   6.95 (90%) wall 
426678 kB (99%) ggc

[Bug ipa/62016] [4.8/4.9/4.10 Regression] very slow compilation at -O3 on x86_64-linux-gnu

[rguenth at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |hubicka at gcc dot gnu.org,
                   |                            |rguenth at gcc dot gnu.org

--- Comment #2 from Richard Biener <rguenth at gcc dot gnu.org> ---
Would be nice to identify what improved 4.9 here and backport that to 4.8.  And
of course try to fix it for real for 4.10.

ISTR the predicate stuff was a major hog.

[Bug ipa/62016] [4.8/4.9/4.10 Regression] very slow compilation at -O3 on x86_64-linux-gnu

[trippels at gcc dot gnu.org]

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

Markus Trippelsdorf <trippels at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |trippels at gcc dot gnu.org

--- Comment #3 from Markus Trippelsdorf <trippels at gcc dot gnu.org> ---
estimate_calls_size_and_time is responsible:

callgrind shows during compilation:

PID 8134: /usr/libexec/gcc/x86_64-pc-linux-gnu/4.8.3/cc1 -quiet small.c -quiet
-dumpbase small.c -mtune=generic -march=x86-64 -auxbase small -O3 -o
/tmp/cc5Ji2sS.s
sending command status internal to pid 8134

  Totals:           Ir 
   Th 1  7,602,583,430 

  Frame:              Ir Backtrace for Thread 1
   [ 0]  198,528,310,004 estimate_calls_size_and_time(cgraph_node*, int*, int*,
int*, unsigned int, vec<tree_node*, va_heap, vl_ptr>, vec<tree_node*, va_heap,
vl_ptr>, vec<ipa_agg_jump_function*, va_heap, vl_ptr>) [clone
.isra.48.371314.34966] (58874971 x)
...
   [34]  198,528,323,290 estimate_calls_size_and_time(cgraph_node*, int*, int*,
int*, unsigned int, vec<tree_node*, va_heap, vl_ptr>, vec<tree_node*, va_heap,
vl_ptr>, vec<ipa_agg_jump_function*, va_heap, vl_ptr>) [clone
.isra.48.371314.34966] (58874971 x)
   [35]    7,299,677,321 estimate_calls_size_and_time(cgraph_node*, int*, int*,
int*, unsigned int, vec<tree_node*, va_heap, vl_ptr>, vec<tree_node*, va_heap,
vl_ptr>, vec<ipa_agg_jump_function*, va_heap, vl_ptr>) [clone
.isra.48.371314.34966] (68761 x)
   [36]    7,276,594,294 estimate_calls_size_and_time(cgraph_node*, int*, int*,
int*, unsigned int, vec<tree_node*, va_heap, vl_ptr>, vec<tree_node*, va_heap,
vl_ptr>, vec<ipa_agg_jump_function*, va_heap, vl_ptr>) [clone
.isra.48.371314.34966] (35608 x)
   [37]    7,286,199,223 estimate_node_size_and_time(cgraph_node*, unsigned
int, vec<tree_node*, va_heap, vl_ptr>, vec<tree_node*, va_heap, vl_ptr>,
vec<ipa_agg_jump_function*, va_heap, vl_ptr>, int*, int*, int*,
vec<inline_param_summary, va_heap, vl_ptr>) [clone .371325] (35570 x)
   [38]    7,382,517,284 do_estimate_edge_time(cgraph_edge*) (35570 x)
   [39]    7,376,457,586 do_estimate_edge_size(cgraph_edge*) (30094 x)
   [40]    7,375,282,471 estimate_edge_size(cgraph_edge*) [clone .371672.55874]
(64499 x)
   [41]    7,376,509,640 do_estimate_growth_1(cgraph_node*, void*) [clone
.371011] (78 x)
   [42]    7,376,511,655 cgraph_for_node_and_aliases(cgraph_node*, bool
(*)(cgraph_node*, void*), void*, bool) (78 x)
   [43]    7,376,515,292 do_estimate_growth(cgraph_node*) (78 x)

[Bug ipa/62016] [4.8/4.9/4.10 Regression] very slow compilation at -O3 on x86_64-linux-gnu

[hubicka at gcc dot gnu.org]

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

Jan Hubicka <hubicka at gcc dot gnu.org> changed:

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

--- Comment #4 from Jan Hubicka <hubicka at gcc dot gnu.org> ---
mine.

[Bug ipa/62016] [4.8/4.9/4.10 Regression] very slow compilation at -O3 on x86_64-linux-gnu

[jakub at gcc dot gnu.org]

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

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

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

--- Comment #5 from Jakub Jelinek <jakub at gcc dot gnu.org> ---
The regression in 4.8 started with r193161.

[Bug ipa/62016] [4.8/4.9/4.10 Regression] very slow compilation at -O3 on x86_64-linux-gnu

[jakub at gcc dot gnu.org]

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

--- Comment #6 from Jakub Jelinek <jakub at gcc dot gnu.org> ---
In 4.9/trunk I think the compile time improved with r208831 , though I was
testing tiny bit different testcase - if (p1 != 0) __builtin_abort ();
instead of assert (p1 == 0);, nevertheless, r208830 took at -O3 still over 13
minutes before I've killed it, r208831 only 3 minutes and something.

[Bug ipa/62016] [4.8/4.9/5 Regression] very slow compilation at -O3 on x86_64-linux-gnu

[rguenth at gcc dot gnu.org]

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

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

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

[Bug ipa/62016] [4.8/4.9/5 Regression] very slow compilation at -O3 on x86_64-linux-gnu

[jakub at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
   Target Milestone|4.8.4                       |4.8.5

--- Comment #7 from Jakub Jelinek <jakub at gcc dot gnu.org> ---
GCC 4.8.4 has been released.

[Bug ipa/62016] [4.8/4.9/5 Regression] very slow compilation at -O3 on x86_64-linux-gnu

[hubicka at gcc dot gnu.org]

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

--- Comment #8 from Jan Hubicka <hubicka at gcc dot gnu.org> ---
Hmm, backporting the code to turn unreachable calls to __builtin_unreachable to
4.7 is quite risky - nothin in 4.7 really cared about correctness of the
analysis. While I do recall only one recent bug in that area, I think it is
safer to leave it as it is.

With sreal changes I guess 5.0 can update costs incrementally. The expensive
part here is not really the evaulation of predicates. Just the fact that we
create function with incredibly many unreachable calls (that accounts as 0) and
we keep re-counting them each time we inline next call.

If we just keep incrementally updating the overall size/speed of the large
function, this problem will go away (and there is earlier Steven's inline bomb
exposing same behaviour)

[Bug ipa/62016] [4.8/4.9/5 Regression] very slow compilation at -O3 on x86_64-linux-gnu

[hubicka at gcc dot gnu.org]

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

--- Comment #9 from Jan Hubicka <hubicka at gcc dot gnu.org> ---
Seems to be fine with GCC 5:
[jh@gcc2-power8 gcc]$ ./xgcc -B ./ -O3 t.c -Q                     
 fn1 fn2 main
Analyzing compilation unit
Performing interprocedural optimizations
 <*free_lang_data> <visibility> <build_ssa_passes> <chkp_passes>
<opt_local_passes> <free-inline-summary> <increase_alignment> <whole-program>
<profile_estimate> <icf> <devirt> <cp> <inline> <pure-const> <static-var>
<single-use> <comdats>Assembling functions:
 fn1.part.0 fn1.constprop fn1 fn2 main
Execution times (seconds)
 phase setup             :   0.00 ( 0%) usr   0.00 ( 0%) sys   0.01 ( 4%) wall 
  1247 kB (48%) ggc
 phase parsing           :   0.01 ( 5%) usr   0.00 ( 0%) sys   0.00 ( 0%) wall 
   210 kB ( 8%) ggc
 phase opt and generate  :   0.21 (95%) usr   0.00 ( 0%) sys   0.22 (96%) wall 
  1127 kB (43%) ggc
 callgraph construction  :   0.00 ( 0%) usr   0.00 ( 0%) sys   0.01 ( 4%) wall 
    33 kB ( 1%) ggc
 callgraph optimization  :   0.03 (14%) usr   0.00 ( 0%) sys   0.00 ( 0%) wall 
     4 kB ( 0%) ggc
 ipa inlining heuristics :   0.00 ( 0%) usr   0.00 ( 0%) sys   0.01 ( 4%) wall 
   158 kB ( 6%) ggc
 CFG verifier            :   0.01 ( 5%) usr   0.00 ( 0%) sys   0.01 ( 4%) wall 
     0 kB ( 0%) ggc
 df reg dead/unused notes:   0.01 ( 5%) usr   0.00 ( 0%) sys   0.01 ( 4%) wall 
     2 kB ( 0%) ggc
 parser (global)         :   0.01 ( 5%) usr   0.00 ( 0%) sys   0.00 ( 0%) wall 
   139 kB ( 5%) ggc
 tree CFG cleanup        :   0.02 ( 9%) usr   0.00 ( 0%) sys   0.02 ( 9%) wall 
     3 kB ( 0%) ggc
 tree SSA incremental    :   0.00 ( 0%) usr   0.00 ( 0%) sys   0.01 ( 4%) wall 
    14 kB ( 1%) ggc
 tree operand scan       :   0.01 ( 5%) usr   0.00 ( 0%) sys   0.01 ( 4%) wall 
    37 kB ( 1%) ggc
 dominator optimization  :   0.01 ( 5%) usr   0.00 ( 0%) sys   0.01 ( 4%) wall 
    19 kB ( 1%) ggc
 tree CCP                :   0.01 ( 5%) usr   0.00 ( 0%) sys   0.01 ( 4%) wall 
     0 kB ( 0%) ggc
 tree SSA verifier       :   0.01 ( 5%) usr   0.00 ( 0%) sys   0.01 ( 4%) wall 
     0 kB ( 0%) ggc
 tree STMT verifier      :   0.03 (14%) usr   0.00 ( 0%) sys   0.03 (13%) wall 
     0 kB ( 0%) ggc
 callgraph verifier      :   0.00 ( 0%) usr   0.00 ( 0%) sys   0.01 ( 4%) wall 
     0 kB ( 0%) ggc
 loop init               :   0.01 ( 5%) usr   0.00 ( 0%) sys   0.01 ( 4%) wall 
    56 kB ( 2%) ggc
 loop invariant motion   :   0.01 ( 5%) usr   0.00 ( 0%) sys   0.01 ( 4%) wall 
     0 kB ( 0%) ggc
 reload                  :   0.01 ( 5%) usr   0.00 ( 0%) sys   0.01 ( 4%) wall 
     2 kB ( 0%) ggc
 hard reg cprop          :   0.01 ( 5%) usr   0.00 ( 0%) sys   0.01 ( 4%) wall 
     0 kB ( 0%) ggc
 rest of compilation     :   0.01 ( 5%) usr   0.00 ( 0%) sys   0.01 ( 4%) wall 
    40 kB ( 2%) ggc
 verify RTL sharing      :   0.02 ( 9%) usr   0.00 ( 0%) sys   0.02 ( 9%) wall 
     0 kB ( 0%) ggc
 TOTAL                 :   0.22             0.00             0.23              
2602 kB

[Bug ipa/62016] [4.8/4.9 Regression] very slow compilation at -O3 on x86_64-linux-gnu

[rguenth at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
      Known to work|                            |5.0
            Summary|[4.8/4.9/5 Regression] very |[4.8/4.9 Regression] very
                   |slow compilation at -O3 on  |slow compilation at -O3 on
                   |x86_64-linux-gnu            |x86_64-linux-gnu
      Known to fail|                            |4.8.3, 4.9.2

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

> /usr/bin/time gcc-4.7 t.c -O3
0.10user 0.02system 0:00.62elapsed 21%CPU (0avgtext+0avgdata 15704maxresident)k
26080inputs+48outputs (113major+9177minor)pagefaults 0swaps
> /usr/bin/time gcc-4.8 t.c -O3
^C
0.00user 0.00system 6:11.40elapsed 0%CPU (0avgtext+0avgdata 1136maxresident)k
1440inputs+0outputs (7major+331minor)pagefaults 0swaps
> /usr/bin/time gcc-4.9 t.c -O3
3.13user 0.18system 0:03.84elapsed 86%CPU (0avgtext+0avgdata
404088maxresident)k
28400inputs+48outputs (128major+137978minor)pagefaults 0swaps
> /usr/bin/time /space/rguenther/install/gcc-5.0/bin/gcc t.c -O3
0.04user 0.01system 0:00.28elapsed 20%CPU (0avgtext+0avgdata 13364maxresident)k
6376inputs+48outputs (17major+8570minor)pagefaults 0swaps

[Bug ipa/62016] [4.8/4.9 Regression] very slow compilation at -O3 on x86_64-linux-gnu

[rguenth at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
   Target Milestone|4.8.5                       |4.9.3

--- Comment #11 from Richard Biener <rguenth at gcc dot gnu.org> ---
The gcc-4_8-branch is being closed, re-targeting regressions to 4.9.3.

[Bug ipa/62016] [4.9 Regression] very slow compilation at -O3 on x86_64-linux-gnu

[jakub at gcc dot gnu.org]

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

--- Comment #12 from Jakub Jelinek <jakub at gcc dot gnu.org> ---
GCC 4.9.3 has been released.

[Bug ipa/62016] [4.9 Regression] very slow compilation at -O3 on x86_64-linux-gnu

[jakub at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
   Target Milestone|4.9.3                       |4.9.4