[Bug middle-end/54146] Very slow compile with attribute((flatten))

["hubicka at gcc dot gnu.org" <gcc-bugzilla at gcc dot gnu dot org>]

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

--- Comment #40 from Jan Hubicka <hubicka at gcc dot gnu.org> 2012-08-10 04:34:54 UTC ---
OK,
my simple ^C profiling shows:
#14 0x000000000091f17f in estimate_edge_size_and_time (e=0x7fffb7192d68,
size=<optimized out>, time=0x7fffc04110b0, prob=10000) at
../../gcc/ipa-inline-analysis.c:2183
#15 0x000000000091f23a in estimate_calls_size_and_time (node=0x7fffb7193af8,
size=0x7fffc04110b4, time=0x7fffc04110b0, possible_truths=4294967294,
known_vals=0x0, 
    known_binfos=0x0) at ../../gcc/ipa-inline-analysis.c:2274
#16 0x000000000091f2d1 in estimate_calls_size_and_time (node=0x7fffb71939c0,
size=0x7fffc04110b4, time=0x7fffc04110b0, possible_truths=4294967294,
known_vals=0x0, 
    known_binfos=0x0) at ../../gcc/ipa-inline-analysis.c:2277
#17 0x000000000091f2d1 in estimate_calls_size_and_time (node=0x7fffb7193888,
size=0x7fffc04110b4, time=0x7fffc04110b0, possible_truths=4294967294,
known_vals=0x0, 
    known_binfos=0x0) at ../../gcc/ipa-inline-analysis.c:2277
#18 0x000000000091f2d1 in estimate_calls_size_and_time (node=0x7fffb7191c30,
size=0x7fffc04110b4, time=0x7fffc04110b0, possible_truths=4294967294,
known_vals=0x0, 
    known_binfos=0x0) at ../../gcc/ipa-inline-analysis.c:2277
#19 0x000000000091f2d1 in estimate_calls_size_and_time (node=0x7fffb7180c30,
size=0x7fffc04110b4, time=0x7fffc04110b0, possible_truths=4294967294,
known_vals=0x0, 
    known_binfos=0x0) at ../../gcc/ipa-inline-analysis.c:2277
#20 0x000000000091f2d1 in estimate_calls_size_and_time (node=0x7fffb7147d68,
size=0x7fffc04110b4, time=0x7fffc04110b0, possible_truths=4294967294,
known_vals=0x0, 
    known_binfos=0x0) at ../../gcc/ipa-inline-analysis.c:2277
#21 0x000000000091f2d1 in estimate_calls_size_and_time (node=0x7fffcbb039c0,
size=0x7fffc04110b4, time=0x7fffc04110b0, possible_truths=4294967294,
known_vals=0x0, 
    known_binfos=0x0) at ../../gcc/ipa-inline-analysis.c:2277
#22 0x00000000009232a1 in inline_merge_summary (edge=0x7fffb6fba068) at
../../gcc/ipa-inline-analysis.c:2687
#23 0x0000000000ed0cdf in inline_call (e=0x7fffb6fba068,
update_original=<optimized out>, new_edges=0x0, overall_size=0x0) at
../../gcc/ipa-inline-transform.c:246
#24 0x0000000000ece3a9 in flatten_function (node=0x7fffb6fb9ea0, early=1
'\001') at ../../gcc/ipa-inline.c:1605
#25 0x0000000000ece3bf in flatten_function (node=0x7fffb6fb4c30, early=1
'\001') at ../../gcc/ipa-inline.c:1608
#26 0x0000000000ece3bf in flatten_function (node=0x7fffb6f87270, early=1
'\001') at ../../gcc/ipa-inline.c:1608
#27 0x0000000000ece3bf in flatten_function (node=0x7fffcbb039c0, early=1
'\001') at ../../gcc/ipa-inline.c:1608
#28 0x0000000000ece616 in early_inliner () at ../../gcc/ipa-inline.c:1881

so the time is actually not spent in the predicate merging logic, but in
computing overall size/time of the function after inline operation is
performed. This is because of following call in inline_merge_summary:

  estimate_calls_size_and_time (to, &info->size, &info->time,
                                ~(clause_t)(1 << predicate_false_condition),
                                NULL, NULL);

Here we simply recompute the size/time by walking all callees of the function
and since this involve recursive walk of the inlined callees that are many we
hit quadratic time complexity.
Ugly.  One (particularly ugly) workaround would be to make inline_merge_summary
to skip updating after each step of flattening because flattening do not care,
but that is quite a kludge (similar to Steven's patch but with one extra update
on the very end).

Other solution is to work hard enough to update everything incrementally, but
it is not 100% trivial (that is why I simply recompute). 
I actually tought of this case and concluded that if we do so deep inline trees
we will blow up somewhere else.  Quite an achivement that Steven managed to
chase out all the other cases.

Honza