[Bug ipa/60243] New: IPA is slow on large cgraph tree

[Bug ipa/60243] New: IPA is slow on large cgraph tree

[rguenth at gcc dot gnu.org]

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

            Bug ID: 60243
           Summary: IPA is slow on large cgraph tree
           Product: gcc
           Version: 4.9.0
            Status: UNCONFIRMED
          Keywords: compile-time-hog
          Severity: normal
          Priority: P3
         Component: ipa
          Assignee: unassigned at gcc dot gnu.org
          Reporter: rguenth at gcc dot gnu.org

I've built that testcase to show quadraticness in ipa_modify_call_arguments
calls to update_ssa:

#!/bin/sh

for i in `seq $1`; do
    echo "static void test$i (int);"
done

for i in `seq $1`; do
    echo "void test$i (int i) {"
    echo "asm (\"\":::\"memory\");"
    for j in `seq $i $1`; do
        if ! test $i == $j; then
            echo "test$j (i);"
        fi
    done
    echo "}"
done

echo "int main() { test1 (5); return 0; }"

but curiously I see (for 1000 and using 4.8):

 ipa inlining heuristics :   2.78 ( 6%) usr   0.02 ( 0%) sys   2.80 ( 5%) wall 
  1546 kB ( 0%) ggc
 ipa profile             :  14.34 (29%) usr   0.01 ( 0%) sys  14.35 (25%) wall 
     0 kB ( 0%) ggc
 ipa SRA                 :   2.32 ( 5%) usr   2.09 (34%) sys   4.49 ( 8%) wall 
281101 kB (32%) ggc
 tree SSA rewrite        :   0.54 ( 1%) usr   0.68 (11%) sys   1.99 ( 4%) wall 
 87933 kB (10%) ggc
 tree SSA incremental    :   0.02 ( 0%) usr   0.02 ( 0%) sys   0.07 ( 0%) wall 
     0 kB ( 0%) ggc
 TOTAL                 :  49.83             6.10            56.55            
883870 kB

that's because all affected bodies are not yet in SSA form ... heh.  So
that part may not be a real issue.

But the IPA profile part?  At -O2?

[Bug ipa/60243] IPA is slow on large cgraph tree

[rguenth at gcc dot gnu.org]

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

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

[Bug ipa/60243] IPA is slow on large cgraph tree

[jakub at gcc dot gnu.org]

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

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

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

--- Comment #2 from Jakub Jelinek <jakub at gcc dot gnu.org> ---
So:
#define A(n) static void test##n (int);
#define B(n) A(n##0) A(n##1) A(n##2) A(n##3) A(n##4) A(n##5) A(n##6) A(n##7)
A(n##8) A(n##9)
#define C(n) B(n##0) B(n##1) B(n##2) B(n##3) B(n##4) B(n##5) B(n##6) B(n##7)
B(n##8) B(n##9)
#define D(n) C(n##0) C(n##1) C(n##2) C(n##3) C(n##4) C(n##5) C(n##6) C(n##7)
C(n##8) C(n##9)
D(1)
#undef A
#define E(m, n) if (n > m) test##n (i);
#define F(m, n) E(m, n##0) E(m, n##1) E(m, n##2) E(m, n##3) E(m, n##4) E(m,
n##5) E(m, n##6) E(m, n##7) E(m, n##8) E(m, n##9)
#define G(m, n) F(m, n##0) F(m, n##1) F(m, n##2) F(m, n##3) F(m, n##4) F(m,
n##5) F(m, n##6) F(m, n##7) F(m, n##8) F(m, n##9)
#define H(m, n) G(m, n##0) G(m, n##1) G(m, n##2) G(m, n##3) G(m, n##4) G(m,
n##5) G(m, n##6) G(m, n##7) G(m, n##8) G(m, n##9)
#define A(n) \
static void test##n (int i)\
{\
  asm ("" : : : "memory");\
  H(n, 1)\
}
D(1)

int
main ()
{
  test1000 (5);
  return 0;
}

so that we have something for the testsuite?

[Bug ipa/60243] IPA is slow on large cgraph tree

[rguenth at gcc dot gnu.org]

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

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

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

--- Comment #3 from Richard Biener <rguenth at gcc dot gnu.org> ---
estimate_calls_size_and_time is quite high on the profile - called via
do_estimate_edge_size it walks callgraph edges O(n^2).  It seems that
the idea of having a cache is worse than devising an algorithm to
compute sizes and times for the whole cgraph at once?

The next high thing on the profile is ipa_propagate_frequency_1 called
from do_estimate_growth (same thing, walks over all call edges again).

The ipa-profile slowness is the same - ipa_propagate_frequency.

The testcase has N cgraph nodes and N^2/2 call edges, so it's quite unusual
of course.

[Bug ipa/60243] IPA is slow on large cgraph tree

[rguenth at gcc dot gnu.org]

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

--- Comment #4 from Richard Biener <rguenth at gcc dot gnu.org> ---
Oh, and ipa_profile_generate_summary is dominated by symtab_get_node ()
hashtable lookup ...

[Bug ipa/60243] IPA is slow on large cgraph tree

[rguenth at gcc dot gnu.org]

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

--- Comment #5 from Richard Biener <rguenth at gcc dot gnu.org> ---
(In reply to Richard Biener from comment #4)
> Oh, and ipa_profile_generate_summary is dominated by symtab_get_node ()
> hashtable lookup ...

here:

int
estimate_num_insns (gimple stmt, eni_weights *weights)
{
        /* Do not special case builtins where we see the body.
           This just confuse inliner.  */
...
        else if (!(decl = gimple_call_fndecl (stmt))
                 || !(node = cgraph_get_node (decl))
                 || node->definition)
          ;

a simple re-org will fix that.  I'll do that.

[Bug ipa/60243] IPA is slow on large cgraph tree

[rguenth at gcc dot gnu.org]

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

--- Comment #7 from Richard Biener <rguenth at gcc dot gnu.org> ---
Created attachment 32163
  --> http://gcc.gnu.org/bugzilla/attachment.cgi?id=32163&action=edit
patch 2

[Bug ipa/60243] IPA is slow on large cgraph tree

[rguenth at gcc dot gnu.org]

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

--- Comment #6 from Richard Biener <rguenth at gcc dot gnu.org> ---
Created attachment 32162
  --> http://gcc.gnu.org/bugzilla/attachment.cgi?id=32162&action=edit
patch 1

[Bug ipa/60243] IPA is slow on large cgraph tree

[rguenth at gcc dot gnu.org]

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

--- Comment #8 from Richard Biener <rguenth at gcc dot gnu.org> ---
Author: rguenth
Date: Wed Feb 19 09:29:34 2014
New Revision: 207879

URL: http://gcc.gnu.org/viewcvs?rev=207879&root=gcc&view=rev
Log:
2014-02-19  Richard Biener  <rguenther@suse.de>

    PR ipa/60243
    * ipa-prop.c: Include stringpool.h and tree-ssanames.h.
    (ipa_modify_call_arguments): Emit an argument load explicitely and
    preserve virtual SSA form there and for the replacement call.
    Do not update SSA form nor free dominance info.

Modified:
    trunk/gcc/ChangeLog
    trunk/gcc/ipa-prop.c

[Bug ipa/60243] IPA is slow on large cgraph tree

[rguenth at gcc dot gnu.org]

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

--- Comment #9 from Richard Biener <rguenth at gcc dot gnu.org> ---
Author: rguenth
Date: Wed Feb 19 14:25:47 2014
New Revision: 207899

URL: http://gcc.gnu.org/viewcvs?rev=207899&root=gcc&view=rev
Log:
2014-02-19  Richard Biener  <rguenther@suse.de>

    PR ipa/60243
    * tree-inline.c (estimate_num_insns): Avoid calling cgraph_get_node
    for all calls.

Modified:
    trunk/gcc/ChangeLog
    trunk/gcc/tree-inline.c

[Bug ipa/60243] IPA is slow on large cgraph tree

[hubicka at ucw dot cz]

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

--- Comment #10 from Jan Hubicka <hubicka at ucw dot cz> ---
> --- Comment #3 from Richard Biener <rguenth at gcc dot gnu.org> ---
> estimate_calls_size_and_time is quite high on the profile - called via
> do_estimate_edge_size it walks callgraph edges O(n^2).  It seems that
> the idea of having a cache is worse than devising an algorithm to
> compute sizes and times for the whole cgraph at once?

Yep, the problem is that they are changing as the inlining progresses, since
we propagate predicates on them on each inline.  I will check the testcase.

[Bug ipa/60243] IPA is slow on large cgraph tree

[hubicka at gcc dot gnu.org]

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

--- Comment #11 from Jan Hubicka <hubicka at gcc dot gnu.org> ---
Created attachment 32244
  --> http://gcc.gnu.org/bugzilla/attachment.cgi?id=32244&action=edit
WIP patch

this patch cuts some redundant work on estimating size of functions that will
be too large to be inlined anyway. Currently inliner spends a lot of time
compuing properties of these functions (since small and inlinable functions are
also fast to estimate)

The patch doesn't really save much time building libreoffice/firefox. I will
experiment with it a bit more.

[Bug ipa/60243] IPA is slow on large cgraph tree

[rguenther at suse dot de]

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

--- Comment #12 from rguenther at suse dot de <rguenther at suse dot de> ---
On Sun, 2 Mar 2014, hubicka at gcc dot gnu.org wrote:

> http://gcc.gnu.org/bugzilla/show_bug.cgi?id=60243
> 
> --- Comment #11 from Jan Hubicka <hubicka at gcc dot gnu.org> ---
> Created attachment 32244
>   --> http://gcc.gnu.org/bugzilla/attachment.cgi?id=32244&action=edit
> WIP patch
> 
> this patch cuts some redundant work on estimating size of functions that will
> be too large to be inlined anyway. Currently inliner spends a lot of time
> compuing properties of these functions (since small and inlinable functions are
> also fast to estimate)
> 
> The patch doesn't really save much time building libreoffice/firefox. I will
> experiment with it a bit more.

Does it help PR60315?  That one is even more an excessive example.

[Bug ipa/60243] IPA is slow on large cgraph tree

[hubicka at gcc dot gnu.org]

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

--- Comment #13 from Jan Hubicka <hubicka at gcc dot gnu.org> ---
BTW, compiled with C++ FE we seem to have important bottleneck in 
linemap_macro_map_lookup

[Bug ipa/60243] IPA is slow on large cgraph tree

[hubicka at gcc dot gnu.org]

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

--- Comment #14 from Jan Hubicka <hubicka at gcc dot gnu.org> ---
Author: hubicka
Date: Fri Mar 28 19:50:28 2014
New Revision: 208916

URL: http://gcc.gnu.org/viewcvs?rev=208916&root=gcc&view=rev
Log:
    PR ipa/60243
    * ipa-inline.c (want_inline_small_function_p): Short circuit large
    functions; reorganize to make cheap checks first.
    (inline_small_functions): Do not estimate growth when dumping;
    it is expensive.
    * ipa-inline.h (inline_summary): Add min_size.
    (growth_likely_positive): New function.
    * ipa-inline-analysis.c (dump_inline_summary): Add min_size.
    (set_cond_stmt_execution_predicate): Cleanup.
    (estimate_edge_size_and_time): Compute min_size.
    (estimate_calls_size_and_time): Likewise.
    (estimate_node_size_and_time): Likewise.
    (inline_update_overall_summary): Update min_size.
    (do_estimate_edge_time): Likewise.
    (do_estimate_edge_size): Update.
    (do_estimate_edge_hints): Update.
    (growth_likely_positive): New function.

Modified:
    trunk/gcc/ChangeLog
    trunk/gcc/ipa-inline-analysis.c
    trunk/gcc/ipa-inline.c
    trunk/gcc/ipa-inline.h

[Bug ipa/60243] IPA is slow on large cgraph tree

[rguenth at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=60243
Bug 60243 depends on bug 60315, which changed state.

Bug 60315 Summary: [4.8 Regression] template constructor switch optimization
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=60315

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

[Bug ipa/60243] IPA is slow on large cgraph tree

[rguenth at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
   Last reconfirmed|2018-11-19 00:00:00         |2024-2-19

--- Comment #28 from Richard Biener <rguenth at gcc dot gnu.org> ---
Original testcase at -O2:

 callgraph functions expansion      :  11.94 ( 51%)   2.19 ( 42%)  14.14 ( 49%)
  570M ( 40%)
 callgraph ipa passes               :  10.00 ( 43%)   0.70 ( 13%)  10.70 ( 37%)
  601M ( 42%)
 ipa profile                        :   4.68 ( 20%)   0.00 (  0%)   4.68 ( 16%)
    0  (  0%)
 TOTAL                              :  23.36          5.22         28.60       
 1430M
23.36user 5.27system 0:28.65elapsed 99%CPU (0avgtext+0avgdata
1152100maxresident)k
0inputs+0outputs (0major+315833minor)pagefaults 0swaps

Jakubs testcase at -O2:

 callgraph functions expansion      :  12.66 ( 30%)   2.21 ( 16%)  14.87 ( 27%)
  505M ( 15%)
 callgraph ipa passes               :  18.28 ( 44%)   0.65 (  5%)  18.94 ( 34%)
  601M ( 18%)
 ipa profile                        :   4.20 ( 10%)   0.00 (  0%)   4.20 (  8%)
    0  (  0%)
 preprocessing                      :   1.47 (  4%)   3.27 ( 24%)   4.81 (  9%)
  417M ( 12%)
 lexical analysis                   :   2.24 (  5%)   4.08 ( 30%)   6.34 ( 11%)
    0  (  0%)
 early inlining heuristics          :   2.83 (  7%)   0.04 (  0%)   2.97 (  5%)
 1658k (  0%)
 inline parameters                  :   3.01 (  7%)   0.21 (  2%)   3.16 (  6%)
   29M (  1%)
 tree CFG construction              :   3.44 (  8%)   0.15 (  1%)   3.52 (  6%)
  599M ( 18%)
 tree operand scan                  :   4.47 ( 11%)   0.26 (  2%)   4.80 (  9%)
   93M (  3%)
 TOTAL                              :  41.73         13.57         55.32       
 3422M
41.73user 13.67system 0:55.42elapsed 99%CPU (0avgtext+0avgdata
2374596maxresident)k
0inputs+0outputs (0major+536990minor)pagefaults 0swaps

so besides a faster machine still like Honza said in the last comment.