1 /* Inlining decision heuristics.
2 Copyright (C) 2003-2017 Free Software Foundation, Inc.
3 Contributed by Jan Hubicka
5 This file is part of GCC.
7 GCC is free software; you can redistribute it and/or modify it under
8 the terms of the GNU General Public License as published by the Free
9 Software Foundation; either version 3, or (at your option) any later
12 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
13 WARRANTY; without even the implied warranty of MERCHANTABILITY or
14 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
17 You should have received a copy of the GNU General Public License
18 along with GCC; see the file COPYING3. If not see
19 <http://www.gnu.org/licenses/>. */
21 /* Inlining decision heuristics
23 The implementation of inliner is organized as follows:
25 inlining heuristics limits
27 can_inline_edge_p allow to check that particular inlining is allowed
28 by the limits specified by user (allowed function growth, growth and so
31 Functions are inlined when it is obvious the result is profitable (such
32 as functions called once or when inlining reduce code size).
33 In addition to that we perform inlining of small functions and recursive
38 The inliner itself is split into two passes:
42 Simple local inlining pass inlining callees into current function.
43 This pass makes no use of whole unit analysis and thus it can do only
44 very simple decisions based on local properties.
46 The strength of the pass is that it is run in topological order
47 (reverse postorder) on the callgraph. Functions are converted into SSA
48 form just before this pass and optimized subsequently. As a result, the
49 callees of the function seen by the early inliner was already optimized
50 and results of early inlining adds a lot of optimization opportunities
51 for the local optimization.
53 The pass handle the obvious inlining decisions within the compilation
54 unit - inlining auto inline functions, inlining for size and
57 main strength of the pass is the ability to eliminate abstraction
58 penalty in C++ code (via combination of inlining and early
59 optimization) and thus improve quality of analysis done by real IPA
62 Because of lack of whole unit knowledge, the pass can not really make
63 good code size/performance tradeoffs. It however does very simple
64 speculative inlining allowing code size to grow by
65 EARLY_INLINING_INSNS when callee is leaf function. In this case the
66 optimizations performed later are very likely to eliminate the cost.
70 This is the real inliner able to handle inlining with whole program
71 knowledge. It performs following steps:
73 1) inlining of small functions. This is implemented by greedy
74 algorithm ordering all inlinable cgraph edges by their badness and
75 inlining them in this order as long as inline limits allows doing so.
77 This heuristics is not very good on inlining recursive calls. Recursive
78 calls can be inlined with results similar to loop unrolling. To do so,
79 special purpose recursive inliner is executed on function when
80 recursive edge is met as viable candidate.
82 2) Unreachable functions are removed from callgraph. Inlining leads
83 to devirtualization and other modification of callgraph so functions
84 may become unreachable during the process. Also functions declared as
85 extern inline or virtual functions are removed, since after inlining
86 we no longer need the offline bodies.
88 3) Functions called once and not exported from the unit are inlined.
89 This should almost always lead to reduction of code size by eliminating
90 the need for offline copy of the function. */
94 #include "coretypes.h"
100 #include "alloc-pool.h"
101 #include "tree-pass.h"
102 #include "gimple-ssa.h"
104 #include "lto-streamer.h"
105 #include "trans-mem.h"
107 #include "tree-inline.h"
110 #include "symbol-summary.h"
111 #include "tree-vrp.h"
112 #include "ipa-prop.h"
113 #include "ipa-fnsummary.h"
114 #include "ipa-inline.h"
115 #include "ipa-utils.h"
117 #include "auto-profile.h"
118 #include "builtins.h"
119 #include "fibonacci_heap.h"
120 #include "stringpool.h"
124 typedef fibonacci_heap
<sreal
, cgraph_edge
> edge_heap_t
;
125 typedef fibonacci_node
<sreal
, cgraph_edge
> edge_heap_node_t
;
127 /* Statistics we collect about inlining algorithm. */
128 static int overall_size
;
129 static profile_count max_count
;
130 static profile_count spec_rem
;
132 /* Return false when inlining edge E would lead to violating
133 limits on function unit growth or stack usage growth.
135 The relative function body growth limit is present generally
136 to avoid problems with non-linear behavior of the compiler.
137 To allow inlining huge functions into tiny wrapper, the limit
138 is always based on the bigger of the two functions considered.
140 For stack growth limits we always base the growth in stack usage
141 of the callers. We want to prevent applications from segfaulting
142 on stack overflow when functions with huge stack frames gets
146 caller_growth_limits (struct cgraph_edge
*e
)
148 struct cgraph_node
*to
= e
->caller
;
149 struct cgraph_node
*what
= e
->callee
->ultimate_alias_target ();
152 HOST_WIDE_INT stack_size_limit
= 0, inlined_stack
;
153 ipa_fn_summary
*info
, *what_info
, *outer_info
= ipa_fn_summaries
->get (to
);
155 /* Look for function e->caller is inlined to. While doing
156 so work out the largest function body on the way. As
157 described above, we want to base our function growth
158 limits based on that. Not on the self size of the
159 outer function, not on the self size of inline code
160 we immediately inline to. This is the most relaxed
161 interpretation of the rule "do not grow large functions
162 too much in order to prevent compiler from exploding". */
165 info
= ipa_fn_summaries
->get (to
);
166 if (limit
< info
->self_size
)
167 limit
= info
->self_size
;
168 if (stack_size_limit
< info
->estimated_self_stack_size
)
169 stack_size_limit
= info
->estimated_self_stack_size
;
170 if (to
->global
.inlined_to
)
171 to
= to
->callers
->caller
;
176 what_info
= ipa_fn_summaries
->get (what
);
178 if (limit
< what_info
->self_size
)
179 limit
= what_info
->self_size
;
181 limit
+= limit
* PARAM_VALUE (PARAM_LARGE_FUNCTION_GROWTH
) / 100;
183 /* Check the size after inlining against the function limits. But allow
184 the function to shrink if it went over the limits by forced inlining. */
185 newsize
= estimate_size_after_inlining (to
, e
);
186 if (newsize
>= info
->size
187 && newsize
> PARAM_VALUE (PARAM_LARGE_FUNCTION_INSNS
)
190 e
->inline_failed
= CIF_LARGE_FUNCTION_GROWTH_LIMIT
;
194 if (!what_info
->estimated_stack_size
)
197 /* FIXME: Stack size limit often prevents inlining in Fortran programs
198 due to large i/o datastructures used by the Fortran front-end.
199 We ought to ignore this limit when we know that the edge is executed
200 on every invocation of the caller (i.e. its call statement dominates
201 exit block). We do not track this information, yet. */
202 stack_size_limit
+= ((gcov_type
)stack_size_limit
203 * PARAM_VALUE (PARAM_STACK_FRAME_GROWTH
) / 100);
205 inlined_stack
= (outer_info
->stack_frame_offset
206 + outer_info
->estimated_self_stack_size
207 + what_info
->estimated_stack_size
);
208 /* Check new stack consumption with stack consumption at the place
210 if (inlined_stack
> stack_size_limit
211 /* If function already has large stack usage from sibling
212 inline call, we can inline, too.
213 This bit overoptimistically assume that we are good at stack
215 && inlined_stack
> info
->estimated_stack_size
216 && inlined_stack
> PARAM_VALUE (PARAM_LARGE_STACK_FRAME
))
218 e
->inline_failed
= CIF_LARGE_STACK_FRAME_GROWTH_LIMIT
;
224 /* Dump info about why inlining has failed. */
227 report_inline_failed_reason (struct cgraph_edge
*e
)
231 fprintf (dump_file
, " not inlinable: %s -> %s, %s\n",
232 e
->caller
->dump_name (),
233 e
->callee
->dump_name (),
234 cgraph_inline_failed_string (e
->inline_failed
));
235 if ((e
->inline_failed
== CIF_TARGET_OPTION_MISMATCH
236 || e
->inline_failed
== CIF_OPTIMIZATION_MISMATCH
)
237 && e
->caller
->lto_file_data
238 && e
->callee
->ultimate_alias_target ()->lto_file_data
)
240 fprintf (dump_file
, " LTO objects: %s, %s\n",
241 e
->caller
->lto_file_data
->file_name
,
242 e
->callee
->ultimate_alias_target ()->lto_file_data
->file_name
);
244 if (e
->inline_failed
== CIF_TARGET_OPTION_MISMATCH
)
245 cl_target_option_print_diff
246 (dump_file
, 2, target_opts_for_fn (e
->caller
->decl
),
247 target_opts_for_fn (e
->callee
->ultimate_alias_target ()->decl
));
248 if (e
->inline_failed
== CIF_OPTIMIZATION_MISMATCH
)
249 cl_optimization_print_diff
250 (dump_file
, 2, opts_for_fn (e
->caller
->decl
),
251 opts_for_fn (e
->callee
->ultimate_alias_target ()->decl
));
255 /* Decide whether sanitizer-related attributes allow inlining. */
258 sanitize_attrs_match_for_inline_p (const_tree caller
, const_tree callee
)
260 if (!caller
|| !callee
)
263 return sanitize_flags_p (SANITIZE_ADDRESS
, caller
)
264 == sanitize_flags_p (SANITIZE_ADDRESS
, callee
);
267 /* Used for flags where it is safe to inline when caller's value is
268 grater than callee's. */
269 #define check_maybe_up(flag) \
270 (opts_for_fn (caller->decl)->x_##flag \
271 != opts_for_fn (callee->decl)->x_##flag \
273 || opts_for_fn (caller->decl)->x_##flag \
274 < opts_for_fn (callee->decl)->x_##flag))
275 /* Used for flags where it is safe to inline when caller's value is
276 smaller than callee's. */
277 #define check_maybe_down(flag) \
278 (opts_for_fn (caller->decl)->x_##flag \
279 != opts_for_fn (callee->decl)->x_##flag \
281 || opts_for_fn (caller->decl)->x_##flag \
282 > opts_for_fn (callee->decl)->x_##flag))
283 /* Used for flags where exact match is needed for correctness. */
284 #define check_match(flag) \
285 (opts_for_fn (caller->decl)->x_##flag \
286 != opts_for_fn (callee->decl)->x_##flag)
288 /* Decide if we can inline the edge and possibly update
289 inline_failed reason.
290 We check whether inlining is possible at all and whether
291 caller growth limits allow doing so.
293 if REPORT is true, output reason to the dump file.
295 if DISREGARD_LIMITS is true, ignore size limits.*/
298 can_inline_edge_p (struct cgraph_edge
*e
, bool report
,
299 bool disregard_limits
= false, bool early
= false)
301 gcc_checking_assert (e
->inline_failed
);
303 if (cgraph_inline_failed_type (e
->inline_failed
) == CIF_FINAL_ERROR
)
306 report_inline_failed_reason (e
);
310 bool inlinable
= true;
311 enum availability avail
;
312 cgraph_node
*caller
= e
->caller
->global
.inlined_to
313 ? e
->caller
->global
.inlined_to
: e
->caller
;
314 cgraph_node
*callee
= e
->callee
->ultimate_alias_target (&avail
, caller
);
315 tree caller_tree
= DECL_FUNCTION_SPECIFIC_OPTIMIZATION (caller
->decl
);
317 = callee
? DECL_FUNCTION_SPECIFIC_OPTIMIZATION (callee
->decl
) : NULL
;
319 if (!callee
->definition
)
321 e
->inline_failed
= CIF_BODY_NOT_AVAILABLE
;
324 if (!early
&& (!opt_for_fn (callee
->decl
, optimize
)
325 || !opt_for_fn (caller
->decl
, optimize
)))
327 e
->inline_failed
= CIF_FUNCTION_NOT_OPTIMIZED
;
330 else if (callee
->calls_comdat_local
)
332 e
->inline_failed
= CIF_USES_COMDAT_LOCAL
;
335 else if (avail
<= AVAIL_INTERPOSABLE
)
337 e
->inline_failed
= CIF_OVERWRITABLE
;
340 /* All edges with call_stmt_cannot_inline_p should have inline_failed
341 initialized to one of FINAL_ERROR reasons. */
342 else if (e
->call_stmt_cannot_inline_p
)
344 /* Don't inline if the functions have different EH personalities. */
345 else if (DECL_FUNCTION_PERSONALITY (caller
->decl
)
346 && DECL_FUNCTION_PERSONALITY (callee
->decl
)
347 && (DECL_FUNCTION_PERSONALITY (caller
->decl
)
348 != DECL_FUNCTION_PERSONALITY (callee
->decl
)))
350 e
->inline_failed
= CIF_EH_PERSONALITY
;
353 /* TM pure functions should not be inlined into non-TM_pure
355 else if (is_tm_pure (callee
->decl
) && !is_tm_pure (caller
->decl
))
357 e
->inline_failed
= CIF_UNSPECIFIED
;
360 /* Check compatibility of target optimization options. */
361 else if (!targetm
.target_option
.can_inline_p (caller
->decl
,
364 e
->inline_failed
= CIF_TARGET_OPTION_MISMATCH
;
367 else if (!ipa_fn_summaries
->get (callee
)->inlinable
)
369 e
->inline_failed
= CIF_FUNCTION_NOT_INLINABLE
;
372 /* Don't inline a function with mismatched sanitization attributes. */
373 else if (!sanitize_attrs_match_for_inline_p (caller
->decl
, callee
->decl
))
375 e
->inline_failed
= CIF_ATTRIBUTE_MISMATCH
;
378 /* Check if caller growth allows the inlining. */
379 else if (!DECL_DISREGARD_INLINE_LIMITS (callee
->decl
)
381 && !lookup_attribute ("flatten",
382 DECL_ATTRIBUTES (caller
->decl
))
383 && !caller_growth_limits (e
))
385 /* Don't inline a function with a higher optimization level than the
386 caller. FIXME: this is really just tip of iceberg of handling
387 optimization attribute. */
388 else if (caller_tree
!= callee_tree
)
391 (DECL_DISREGARD_INLINE_LIMITS (callee
->decl
)
392 && lookup_attribute ("always_inline",
393 DECL_ATTRIBUTES (callee
->decl
)));
394 ipa_fn_summary
*caller_info
= ipa_fn_summaries
->get (caller
);
395 ipa_fn_summary
*callee_info
= ipa_fn_summaries
->get (callee
);
397 /* Until GCC 4.9 we did not check the semantics alterning flags
398 bellow and inline across optimization boundry.
399 Enabling checks bellow breaks several packages by refusing
400 to inline library always_inline functions. See PR65873.
401 Disable the check for early inlining for now until better solution
403 if (always_inline
&& early
)
405 /* There are some options that change IL semantics which means
406 we cannot inline in these cases for correctness reason.
407 Not even for always_inline declared functions. */
408 else if (check_match (flag_wrapv
)
409 || check_match (flag_trapv
)
410 || check_match (flag_pcc_struct_return
)
411 /* When caller or callee does FP math, be sure FP codegen flags
413 || ((caller_info
->fp_expressions
&& callee_info
->fp_expressions
)
414 && (check_maybe_up (flag_rounding_math
)
415 || check_maybe_up (flag_trapping_math
)
416 || check_maybe_down (flag_unsafe_math_optimizations
)
417 || check_maybe_down (flag_finite_math_only
)
418 || check_maybe_up (flag_signaling_nans
)
419 || check_maybe_down (flag_cx_limited_range
)
420 || check_maybe_up (flag_signed_zeros
)
421 || check_maybe_down (flag_associative_math
)
422 || check_maybe_down (flag_reciprocal_math
)
423 || check_maybe_down (flag_fp_int_builtin_inexact
)
424 /* Strictly speaking only when the callee contains function
425 calls that may end up setting errno. */
426 || check_maybe_up (flag_errno_math
)))
427 /* We do not want to make code compiled with exceptions to be
428 brought into a non-EH function unless we know that the callee
430 This is tracked by DECL_FUNCTION_PERSONALITY. */
431 || (check_maybe_up (flag_non_call_exceptions
)
432 && DECL_FUNCTION_PERSONALITY (callee
->decl
))
433 || (check_maybe_up (flag_exceptions
)
434 && DECL_FUNCTION_PERSONALITY (callee
->decl
))
435 /* When devirtualization is diabled for callee, it is not safe
436 to inline it as we possibly mangled the type info.
437 Allow early inlining of always inlines. */
438 || (!early
&& check_maybe_down (flag_devirtualize
)))
440 e
->inline_failed
= CIF_OPTIMIZATION_MISMATCH
;
443 /* gcc.dg/pr43564.c. Apply user-forced inline even at -O0. */
444 else if (always_inline
)
446 /* When user added an attribute to the callee honor it. */
447 else if (lookup_attribute ("optimize", DECL_ATTRIBUTES (callee
->decl
))
448 && opts_for_fn (caller
->decl
) != opts_for_fn (callee
->decl
))
450 e
->inline_failed
= CIF_OPTIMIZATION_MISMATCH
;
453 /* If explicit optimize attribute are not used, the mismatch is caused
454 by different command line options used to build different units.
455 Do not care about COMDAT functions - those are intended to be
456 optimized with the optimization flags of module they are used in.
457 Also do not care about mixing up size/speed optimization when
458 DECL_DISREGARD_INLINE_LIMITS is set. */
459 else if ((callee
->merged_comdat
460 && !lookup_attribute ("optimize",
461 DECL_ATTRIBUTES (caller
->decl
)))
462 || DECL_DISREGARD_INLINE_LIMITS (callee
->decl
))
464 /* If mismatch is caused by merging two LTO units with different
465 optimizationflags we want to be bit nicer. However never inline
466 if one of functions is not optimized at all. */
467 else if (!opt_for_fn (callee
->decl
, optimize
)
468 || !opt_for_fn (caller
->decl
, optimize
))
470 e
->inline_failed
= CIF_OPTIMIZATION_MISMATCH
;
473 /* If callee is optimized for size and caller is not, allow inlining if
474 code shrinks or we are in MAX_INLINE_INSNS_SINGLE limit and callee
475 is inline (and thus likely an unified comdat). This will allow caller
477 else if (opt_for_fn (callee
->decl
, optimize_size
)
478 > opt_for_fn (caller
->decl
, optimize_size
))
480 int growth
= estimate_edge_growth (e
);
482 && (!DECL_DECLARED_INLINE_P (callee
->decl
)
483 && growth
>= MAX (MAX_INLINE_INSNS_SINGLE
,
484 MAX_INLINE_INSNS_AUTO
)))
486 e
->inline_failed
= CIF_OPTIMIZATION_MISMATCH
;
490 /* If callee is more aggressively optimized for performance than caller,
491 we generally want to inline only cheap (runtime wise) functions. */
492 else if (opt_for_fn (callee
->decl
, optimize_size
)
493 < opt_for_fn (caller
->decl
, optimize_size
)
494 || (opt_for_fn (callee
->decl
, optimize
)
495 > opt_for_fn (caller
->decl
, optimize
)))
497 if (estimate_edge_time (e
)
498 >= 20 + ipa_call_summaries
->get (e
)->call_stmt_time
)
500 e
->inline_failed
= CIF_OPTIMIZATION_MISMATCH
;
507 if (!inlinable
&& report
)
508 report_inline_failed_reason (e
);
513 /* Return true if the edge E is inlinable during early inlining. */
516 can_early_inline_edge_p (struct cgraph_edge
*e
)
518 struct cgraph_node
*callee
= e
->callee
->ultimate_alias_target ();
519 /* Early inliner might get called at WPA stage when IPA pass adds new
520 function. In this case we can not really do any of early inlining
521 because function bodies are missing. */
522 if (cgraph_inline_failed_type (e
->inline_failed
) == CIF_FINAL_ERROR
)
524 if (!gimple_has_body_p (callee
->decl
))
526 e
->inline_failed
= CIF_BODY_NOT_AVAILABLE
;
529 /* In early inliner some of callees may not be in SSA form yet
530 (i.e. the callgraph is cyclic and we did not process
531 the callee by early inliner, yet). We don't have CIF code for this
532 case; later we will re-do the decision in the real inliner. */
533 if (!gimple_in_ssa_p (DECL_STRUCT_FUNCTION (e
->caller
->decl
))
534 || !gimple_in_ssa_p (DECL_STRUCT_FUNCTION (callee
->decl
)))
537 fprintf (dump_file
, " edge not inlinable: not in SSA form\n");
540 if (!can_inline_edge_p (e
, true, false, true))
546 /* Return number of calls in N. Ignore cheap builtins. */
549 num_calls (struct cgraph_node
*n
)
551 struct cgraph_edge
*e
;
554 for (e
= n
->callees
; e
; e
= e
->next_callee
)
555 if (!is_inexpensive_builtin (e
->callee
->decl
))
561 /* Return true if we are interested in inlining small function. */
564 want_early_inline_function_p (struct cgraph_edge
*e
)
566 bool want_inline
= true;
567 struct cgraph_node
*callee
= e
->callee
->ultimate_alias_target ();
569 if (DECL_DISREGARD_INLINE_LIMITS (callee
->decl
))
571 /* For AutoFDO, we need to make sure that before profile summary, all
572 hot paths' IR look exactly the same as profiled binary. As a result,
573 in einliner, we will disregard size limit and inline those callsites
575 * inlined in the profiled binary, and
576 * the cloned callee has enough samples to be considered "hot". */
577 else if (flag_auto_profile
&& afdo_callsite_hot_enough_for_early_inline (e
))
579 else if (!DECL_DECLARED_INLINE_P (callee
->decl
)
580 && !opt_for_fn (e
->caller
->decl
, flag_inline_small_functions
))
582 e
->inline_failed
= CIF_FUNCTION_NOT_INLINE_CANDIDATE
;
583 report_inline_failed_reason (e
);
588 int growth
= estimate_edge_growth (e
);
593 else if (!e
->maybe_hot_p ()
597 fprintf (dump_file
, " will not early inline: %s->%s, "
598 "call is cold and code would grow by %i\n",
599 e
->caller
->dump_name (),
600 callee
->dump_name (),
604 else if (growth
> PARAM_VALUE (PARAM_EARLY_INLINING_INSNS
))
607 fprintf (dump_file
, " will not early inline: %s->%s, "
608 "growth %i exceeds --param early-inlining-insns\n",
609 e
->caller
->dump_name (),
610 callee
->dump_name (),
614 else if ((n
= num_calls (callee
)) != 0
615 && growth
* (n
+ 1) > PARAM_VALUE (PARAM_EARLY_INLINING_INSNS
))
618 fprintf (dump_file
, " will not early inline: %s->%s, "
619 "growth %i exceeds --param early-inlining-insns "
620 "divided by number of calls\n",
621 e
->caller
->dump_name (),
622 callee
->dump_name (),
630 /* Compute time of the edge->caller + edge->callee execution when inlining
634 compute_uninlined_call_time (struct cgraph_edge
*edge
,
635 sreal uninlined_call_time
)
637 cgraph_node
*caller
= (edge
->caller
->global
.inlined_to
638 ? edge
->caller
->global
.inlined_to
641 sreal freq
= edge
->sreal_frequency ();
643 uninlined_call_time
*= freq
;
645 uninlined_call_time
= uninlined_call_time
>> 11;
647 sreal caller_time
= ipa_fn_summaries
->get (caller
)->time
;
648 return uninlined_call_time
+ caller_time
;
651 /* Same as compute_uinlined_call_time but compute time when inlining
655 compute_inlined_call_time (struct cgraph_edge
*edge
,
658 cgraph_node
*caller
= (edge
->caller
->global
.inlined_to
659 ? edge
->caller
->global
.inlined_to
661 sreal caller_time
= ipa_fn_summaries
->get (caller
)->time
;
663 sreal freq
= edge
->sreal_frequency ();
669 /* This calculation should match one in ipa-inline-analysis.c
670 (estimate_edge_size_and_time). */
671 time
-= (sreal
)ipa_call_summaries
->get (edge
)->call_stmt_time
* freq
;
674 time
= ((sreal
) 1) >> 8;
675 gcc_checking_assert (time
>= 0);
679 /* Return true if the speedup for inlining E is bigger than
680 PARAM_MAX_INLINE_MIN_SPEEDUP. */
683 big_speedup_p (struct cgraph_edge
*e
)
686 sreal spec_time
= estimate_edge_time (e
, &unspec_time
);
687 sreal time
= compute_uninlined_call_time (e
, unspec_time
);
688 sreal inlined_time
= compute_inlined_call_time (e
, spec_time
);
690 if (time
- inlined_time
* 100
691 > (sreal
) (time
* PARAM_VALUE (PARAM_INLINE_MIN_SPEEDUP
)))
696 /* Return true if we are interested in inlining small function.
697 When REPORT is true, report reason to dump file. */
700 want_inline_small_function_p (struct cgraph_edge
*e
, bool report
)
702 bool want_inline
= true;
703 struct cgraph_node
*callee
= e
->callee
->ultimate_alias_target ();
705 if (DECL_DISREGARD_INLINE_LIMITS (callee
->decl
))
707 else if (!DECL_DECLARED_INLINE_P (callee
->decl
)
708 && !opt_for_fn (e
->caller
->decl
, flag_inline_small_functions
))
710 e
->inline_failed
= CIF_FUNCTION_NOT_INLINE_CANDIDATE
;
713 /* Do fast and conservative check if the function can be good
714 inline candidate. At the moment we allow inline hints to
715 promote non-inline functions to inline and we increase
716 MAX_INLINE_INSNS_SINGLE 16-fold for inline functions. */
717 else if ((!DECL_DECLARED_INLINE_P (callee
->decl
)
718 && (!e
->count
.ipa ().initialized_p () || !e
->maybe_hot_p ()))
719 && ipa_fn_summaries
->get (callee
)->min_size
720 - ipa_call_summaries
->get (e
)->call_stmt_size
721 > MAX (MAX_INLINE_INSNS_SINGLE
, MAX_INLINE_INSNS_AUTO
))
723 e
->inline_failed
= CIF_MAX_INLINE_INSNS_AUTO_LIMIT
;
726 else if ((DECL_DECLARED_INLINE_P (callee
->decl
)
727 || e
->count
.ipa ().nonzero_p ())
728 && ipa_fn_summaries
->get (callee
)->min_size
729 - ipa_call_summaries
->get (e
)->call_stmt_size
730 > 16 * MAX_INLINE_INSNS_SINGLE
)
732 e
->inline_failed
= (DECL_DECLARED_INLINE_P (callee
->decl
)
733 ? CIF_MAX_INLINE_INSNS_SINGLE_LIMIT
734 : CIF_MAX_INLINE_INSNS_AUTO_LIMIT
);
739 int growth
= estimate_edge_growth (e
);
740 ipa_hints hints
= estimate_edge_hints (e
);
741 bool big_speedup
= big_speedup_p (e
);
745 /* Apply MAX_INLINE_INSNS_SINGLE limit. Do not do so when
746 hints suggests that inlining given function is very profitable. */
747 else if (DECL_DECLARED_INLINE_P (callee
->decl
)
748 && growth
>= MAX_INLINE_INSNS_SINGLE
750 && !(hints
& (INLINE_HINT_indirect_call
751 | INLINE_HINT_known_hot
752 | INLINE_HINT_loop_iterations
753 | INLINE_HINT_array_index
754 | INLINE_HINT_loop_stride
)))
755 || growth
>= MAX_INLINE_INSNS_SINGLE
* 16))
757 e
->inline_failed
= CIF_MAX_INLINE_INSNS_SINGLE_LIMIT
;
760 else if (!DECL_DECLARED_INLINE_P (callee
->decl
)
761 && !opt_for_fn (e
->caller
->decl
, flag_inline_functions
))
763 /* growth_likely_positive is expensive, always test it last. */
764 if (growth
>= MAX_INLINE_INSNS_SINGLE
765 || growth_likely_positive (callee
, growth
))
767 e
->inline_failed
= CIF_NOT_DECLARED_INLINED
;
771 /* Apply MAX_INLINE_INSNS_AUTO limit for functions not declared inline
772 Upgrade it to MAX_INLINE_INSNS_SINGLE when hints suggests that
773 inlining given function is very profitable. */
774 else if (!DECL_DECLARED_INLINE_P (callee
->decl
)
776 && !(hints
& INLINE_HINT_known_hot
)
777 && growth
>= ((hints
& (INLINE_HINT_indirect_call
778 | INLINE_HINT_loop_iterations
779 | INLINE_HINT_array_index
780 | INLINE_HINT_loop_stride
))
781 ? MAX (MAX_INLINE_INSNS_AUTO
,
782 MAX_INLINE_INSNS_SINGLE
)
783 : MAX_INLINE_INSNS_AUTO
))
785 /* growth_likely_positive is expensive, always test it last. */
786 if (growth
>= MAX_INLINE_INSNS_SINGLE
787 || growth_likely_positive (callee
, growth
))
789 e
->inline_failed
= CIF_MAX_INLINE_INSNS_AUTO_LIMIT
;
793 /* If call is cold, do not inline when function body would grow. */
794 else if (!e
->maybe_hot_p ()
795 && (growth
>= MAX_INLINE_INSNS_SINGLE
796 || growth_likely_positive (callee
, growth
)))
798 e
->inline_failed
= CIF_UNLIKELY_CALL
;
802 if (!want_inline
&& report
)
803 report_inline_failed_reason (e
);
807 /* EDGE is self recursive edge.
808 We hand two cases - when function A is inlining into itself
809 or when function A is being inlined into another inliner copy of function
812 In first case OUTER_NODE points to the toplevel copy of A, while
813 in the second case OUTER_NODE points to the outermost copy of A in B.
815 In both cases we want to be extra selective since
816 inlining the call will just introduce new recursive calls to appear. */
819 want_inline_self_recursive_call_p (struct cgraph_edge
*edge
,
820 struct cgraph_node
*outer_node
,
824 char const *reason
= NULL
;
825 bool want_inline
= true;
826 sreal caller_freq
= 1;
827 int max_depth
= PARAM_VALUE (PARAM_MAX_INLINE_RECURSIVE_DEPTH_AUTO
);
829 if (DECL_DECLARED_INLINE_P (edge
->caller
->decl
))
830 max_depth
= PARAM_VALUE (PARAM_MAX_INLINE_RECURSIVE_DEPTH
);
832 if (!edge
->maybe_hot_p ())
834 reason
= "recursive call is cold";
837 else if (depth
> max_depth
)
839 reason
= "--param max-inline-recursive-depth exceeded.";
842 else if (outer_node
->global
.inlined_to
843 && (caller_freq
= outer_node
->callers
->sreal_frequency ()) == 0)
845 reason
= "caller frequency is 0";
851 /* Inlining of self recursive function into copy of itself within other
852 function is transformation similar to loop peeling.
854 Peeling is profitable if we can inline enough copies to make probability
855 of actual call to the self recursive function very small. Be sure that
856 the probability of recursion is small.
858 We ensure that the frequency of recursing is at most 1 - (1/max_depth).
859 This way the expected number of recursion is at most max_depth. */
862 sreal max_prob
= (sreal
)1 - ((sreal
)1 / (sreal
)max_depth
);
864 for (i
= 1; i
< depth
; i
++)
865 max_prob
= max_prob
* max_prob
;
866 if (edge
->sreal_frequency () >= max_prob
* caller_freq
)
868 reason
= "frequency of recursive call is too large";
872 /* Recursive inlining, i.e. equivalent of unrolling, is profitable if
873 recursion depth is large. We reduce function call overhead and increase
874 chances that things fit in hardware return predictor.
876 Recursive inlining might however increase cost of stack frame setup
877 actually slowing down functions whose recursion tree is wide rather than
880 Deciding reliably on when to do recursive inlining without profile feedback
881 is tricky. For now we disable recursive inlining when probability of self
884 Recursive inlining of self recursive call within loop also results in
885 large loop depths that generally optimize badly. We may want to throttle
886 down inlining in those cases. In particular this seems to happen in one
887 of libstdc++ rb tree methods. */
890 if (edge
->sreal_frequency () * 100
892 * PARAM_VALUE (PARAM_MIN_INLINE_RECURSIVE_PROBABILITY
))
894 reason
= "frequency of recursive call is too small";
898 if (!want_inline
&& dump_file
)
899 fprintf (dump_file
, " not inlining recursively: %s\n", reason
);
903 /* Return true when NODE has uninlinable caller;
904 set HAS_HOT_CALL if it has hot call.
905 Worker for cgraph_for_node_and_aliases. */
908 check_callers (struct cgraph_node
*node
, void *has_hot_call
)
910 struct cgraph_edge
*e
;
911 for (e
= node
->callers
; e
; e
= e
->next_caller
)
913 if (!opt_for_fn (e
->caller
->decl
, flag_inline_functions_called_once
)
914 || !opt_for_fn (e
->caller
->decl
, optimize
))
916 if (!can_inline_edge_p (e
, true))
918 if (e
->recursive_p ())
920 if (!(*(bool *)has_hot_call
) && e
->maybe_hot_p ())
921 *(bool *)has_hot_call
= true;
926 /* If NODE has a caller, return true. */
929 has_caller_p (struct cgraph_node
*node
, void *data ATTRIBUTE_UNUSED
)
936 /* Decide if inlining NODE would reduce unit size by eliminating
937 the offline copy of function.
938 When COLD is true the cold calls are considered, too. */
941 want_inline_function_to_all_callers_p (struct cgraph_node
*node
, bool cold
)
943 bool has_hot_call
= false;
945 /* Aliases gets inlined along with the function they alias. */
948 /* Already inlined? */
949 if (node
->global
.inlined_to
)
951 /* Does it have callers? */
952 if (!node
->call_for_symbol_and_aliases (has_caller_p
, NULL
, true))
954 /* Inlining into all callers would increase size? */
955 if (estimate_growth (node
) > 0)
957 /* All inlines must be possible. */
958 if (node
->call_for_symbol_and_aliases (check_callers
, &has_hot_call
,
961 if (!cold
&& !has_hot_call
)
966 /* A cost model driving the inlining heuristics in a way so the edges with
967 smallest badness are inlined first. After each inlining is performed
968 the costs of all caller edges of nodes affected are recomputed so the
969 metrics may accurately depend on values such as number of inlinable callers
970 of the function or function body size. */
973 edge_badness (struct cgraph_edge
*edge
, bool dump
)
977 sreal edge_time
, unspec_edge_time
;
978 struct cgraph_node
*callee
= edge
->callee
->ultimate_alias_target ();
979 struct ipa_fn_summary
*callee_info
= ipa_fn_summaries
->get (callee
);
981 cgraph_node
*caller
= (edge
->caller
->global
.inlined_to
982 ? edge
->caller
->global
.inlined_to
985 growth
= estimate_edge_growth (edge
);
986 edge_time
= estimate_edge_time (edge
, &unspec_edge_time
);
987 hints
= estimate_edge_hints (edge
);
988 gcc_checking_assert (edge_time
>= 0);
989 /* Check that inlined time is better, but tolerate some roundoff issues.
990 FIXME: When callee profile drops to 0 we account calls more. This
991 should be fixed by never doing that. */
992 gcc_checking_assert ((edge_time
- callee_info
->time
).to_int () <= 0
993 || callee
->count
.ipa ().initialized_p ());
994 gcc_checking_assert (growth
<= callee_info
->size
);
998 fprintf (dump_file
, " Badness calculation for %s -> %s\n",
999 edge
->caller
->dump_name (),
1000 edge
->callee
->dump_name ());
1001 fprintf (dump_file
, " size growth %i, time %f unspec %f ",
1003 edge_time
.to_double (),
1004 unspec_edge_time
.to_double ());
1005 ipa_dump_hints (dump_file
, hints
);
1006 if (big_speedup_p (edge
))
1007 fprintf (dump_file
, " big_speedup");
1008 fprintf (dump_file
, "\n");
1011 /* Always prefer inlining saving code size. */
1014 badness
= (sreal
) (-SREAL_MIN_SIG
+ growth
) << (SREAL_MAX_EXP
/ 256);
1016 fprintf (dump_file
, " %f: Growth %d <= 0\n", badness
.to_double (),
1019 /* Inlining into EXTERNAL functions is not going to change anything unless
1020 they are themselves inlined. */
1021 else if (DECL_EXTERNAL (caller
->decl
))
1024 fprintf (dump_file
, " max: function is external\n");
1025 return sreal::max ();
1027 /* When profile is available. Compute badness as:
1029 time_saved * caller_count
1030 goodness = -------------------------------------------------
1031 growth_of_caller * overall_growth * combined_size
1033 badness = - goodness
1035 Again use negative value to make calls with profile appear hotter
1038 else if (opt_for_fn (caller
->decl
, flag_guess_branch_prob
)
1039 || caller
->count
.ipa ().nonzero_p ())
1041 sreal numerator
, denominator
;
1043 sreal inlined_time
= compute_inlined_call_time (edge
, edge_time
);
1045 numerator
= (compute_uninlined_call_time (edge
, unspec_edge_time
)
1048 numerator
= ((sreal
) 1 >> 8);
1049 if (caller
->count
.ipa ().nonzero_p ())
1050 numerator
*= caller
->count
.ipa ().to_gcov_type ();
1051 else if (caller
->count
.ipa ().initialized_p ())
1052 numerator
= numerator
>> 11;
1053 denominator
= growth
;
1055 overall_growth
= callee_info
->growth
;
1057 /* Look for inliner wrappers of the form:
1063 noninline_callee ();
1065 Withhout panilizing this case, we usually inline noninline_callee
1066 into the inline_caller because overall_growth is small preventing
1067 further inlining of inline_caller.
1069 Penalize only callgraph edges to functions with small overall
1072 if (growth
> overall_growth
1073 /* ... and having only one caller which is not inlined ... */
1074 && callee_info
->single_caller
1075 && !edge
->caller
->global
.inlined_to
1076 /* ... and edges executed only conditionally ... */
1077 && edge
->sreal_frequency () < 1
1078 /* ... consider case where callee is not inline but caller is ... */
1079 && ((!DECL_DECLARED_INLINE_P (edge
->callee
->decl
)
1080 && DECL_DECLARED_INLINE_P (caller
->decl
))
1081 /* ... or when early optimizers decided to split and edge
1082 frequency still indicates splitting is a win ... */
1083 || (callee
->split_part
&& !caller
->split_part
1084 && edge
->sreal_frequency () * 100
1086 (PARAM_PARTIAL_INLINING_ENTRY_PROBABILITY
)
1087 /* ... and do not overwrite user specified hints. */
1088 && (!DECL_DECLARED_INLINE_P (edge
->callee
->decl
)
1089 || DECL_DECLARED_INLINE_P (caller
->decl
)))))
1091 struct ipa_fn_summary
*caller_info
= ipa_fn_summaries
->get (caller
);
1092 int caller_growth
= caller_info
->growth
;
1094 /* Only apply the penalty when caller looks like inline candidate,
1095 and it is not called once and. */
1096 if (!caller_info
->single_caller
&& overall_growth
< caller_growth
1097 && caller_info
->inlinable
1098 && caller_info
->size
1099 < (DECL_DECLARED_INLINE_P (caller
->decl
)
1100 ? MAX_INLINE_INSNS_SINGLE
: MAX_INLINE_INSNS_AUTO
))
1104 " Wrapper penalty. Increasing growth %i to %i\n",
1105 overall_growth
, caller_growth
);
1106 overall_growth
= caller_growth
;
1109 if (overall_growth
> 0)
1111 /* Strongly preffer functions with few callers that can be inlined
1112 fully. The square root here leads to smaller binaries at average.
1113 Watch however for extreme cases and return to linear function
1114 when growth is large. */
1115 if (overall_growth
< 256)
1116 overall_growth
*= overall_growth
;
1118 overall_growth
+= 256 * 256 - 256;
1119 denominator
*= overall_growth
;
1121 /*denominator *= inlined_time;*/
1123 badness
= - numerator
/ denominator
;
1128 " %f: guessed profile. frequency %f, count %" PRId64
1129 " caller count %" PRId64
1130 " time w/o inlining %f, time with inlining %f"
1131 " overall growth %i (current) %i (original)"
1132 " %i (compensated)\n",
1133 badness
.to_double (),
1134 edge
->sreal_frequency ().to_double (),
1135 edge
->count
.ipa ().initialized_p () ? edge
->count
.ipa ().to_gcov_type () : -1,
1136 caller
->count
.ipa ().initialized_p () ? caller
->count
.ipa ().to_gcov_type () : -1,
1137 compute_uninlined_call_time (edge
,
1138 unspec_edge_time
).to_double (),
1139 inlined_time
.to_double (),
1140 estimate_growth (callee
),
1141 callee_info
->growth
, overall_growth
);
1144 /* When function local profile is not available or it does not give
1145 useful information (ie frequency is zero), base the cost on
1146 loop nest and overall size growth, so we optimize for overall number
1147 of functions fully inlined in program. */
1150 int nest
= MIN (ipa_call_summaries
->get (edge
)->loop_depth
, 8);
1153 /* Decrease badness if call is nested. */
1155 badness
= badness
>> nest
;
1157 badness
= badness
<< nest
;
1159 fprintf (dump_file
, " %f: no profile. nest %i\n",
1160 badness
.to_double (), nest
);
1162 gcc_checking_assert (badness
!= 0);
1164 if (edge
->recursive_p ())
1165 badness
= badness
.shift (badness
> 0 ? 4 : -4);
1166 if ((hints
& (INLINE_HINT_indirect_call
1167 | INLINE_HINT_loop_iterations
1168 | INLINE_HINT_array_index
1169 | INLINE_HINT_loop_stride
))
1170 || callee_info
->growth
<= 0)
1171 badness
= badness
.shift (badness
> 0 ? -2 : 2);
1172 if (hints
& (INLINE_HINT_same_scc
))
1173 badness
= badness
.shift (badness
> 0 ? 3 : -3);
1174 else if (hints
& (INLINE_HINT_in_scc
))
1175 badness
= badness
.shift (badness
> 0 ? 2 : -2);
1176 else if (hints
& (INLINE_HINT_cross_module
))
1177 badness
= badness
.shift (badness
> 0 ? 1 : -1);
1178 if (DECL_DISREGARD_INLINE_LIMITS (callee
->decl
))
1179 badness
= badness
.shift (badness
> 0 ? -4 : 4);
1180 else if ((hints
& INLINE_HINT_declared_inline
))
1181 badness
= badness
.shift (badness
> 0 ? -3 : 3);
1183 fprintf (dump_file
, " Adjusted by hints %f\n", badness
.to_double ());
1187 /* Recompute badness of EDGE and update its key in HEAP if needed. */
1189 update_edge_key (edge_heap_t
*heap
, struct cgraph_edge
*edge
)
1191 sreal badness
= edge_badness (edge
, false);
1194 edge_heap_node_t
*n
= (edge_heap_node_t
*) edge
->aux
;
1195 gcc_checking_assert (n
->get_data () == edge
);
1197 /* fibonacci_heap::replace_key does busy updating of the
1198 heap that is unnecesarily expensive.
1199 We do lazy increases: after extracting minimum if the key
1200 turns out to be out of date, it is re-inserted into heap
1201 with correct value. */
1202 if (badness
< n
->get_key ())
1204 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1207 " decreasing badness %s -> %s, %f to %f\n",
1208 edge
->caller
->dump_name (),
1209 edge
->callee
->dump_name (),
1210 n
->get_key ().to_double (),
1211 badness
.to_double ());
1213 heap
->decrease_key (n
, badness
);
1218 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1221 " enqueuing call %s -> %s, badness %f\n",
1222 edge
->caller
->dump_name (),
1223 edge
->callee
->dump_name (),
1224 badness
.to_double ());
1226 edge
->aux
= heap
->insert (badness
, edge
);
1231 /* NODE was inlined.
1232 All caller edges needs to be resetted because
1233 size estimates change. Similarly callees needs reset
1234 because better context may be known. */
1237 reset_edge_caches (struct cgraph_node
*node
)
1239 struct cgraph_edge
*edge
;
1240 struct cgraph_edge
*e
= node
->callees
;
1241 struct cgraph_node
*where
= node
;
1242 struct ipa_ref
*ref
;
1244 if (where
->global
.inlined_to
)
1245 where
= where
->global
.inlined_to
;
1247 for (edge
= where
->callers
; edge
; edge
= edge
->next_caller
)
1248 if (edge
->inline_failed
)
1249 reset_edge_growth_cache (edge
);
1251 FOR_EACH_ALIAS (where
, ref
)
1252 reset_edge_caches (dyn_cast
<cgraph_node
*> (ref
->referring
));
1258 if (!e
->inline_failed
&& e
->callee
->callees
)
1259 e
= e
->callee
->callees
;
1262 if (e
->inline_failed
)
1263 reset_edge_growth_cache (e
);
1270 if (e
->caller
== node
)
1272 e
= e
->caller
->callers
;
1274 while (!e
->next_callee
);
1280 /* Recompute HEAP nodes for each of caller of NODE.
1281 UPDATED_NODES track nodes we already visited, to avoid redundant work.
1282 When CHECK_INLINABLITY_FOR is set, re-check for specified edge that
1283 it is inlinable. Otherwise check all edges. */
1286 update_caller_keys (edge_heap_t
*heap
, struct cgraph_node
*node
,
1287 bitmap updated_nodes
,
1288 struct cgraph_edge
*check_inlinablity_for
)
1290 struct cgraph_edge
*edge
;
1291 struct ipa_ref
*ref
;
1293 if ((!node
->alias
&& !ipa_fn_summaries
->get (node
)->inlinable
)
1294 || node
->global
.inlined_to
)
1296 if (!bitmap_set_bit (updated_nodes
, node
->uid
))
1299 FOR_EACH_ALIAS (node
, ref
)
1301 struct cgraph_node
*alias
= dyn_cast
<cgraph_node
*> (ref
->referring
);
1302 update_caller_keys (heap
, alias
, updated_nodes
, check_inlinablity_for
);
1305 for (edge
= node
->callers
; edge
; edge
= edge
->next_caller
)
1306 if (edge
->inline_failed
)
1308 if (!check_inlinablity_for
1309 || check_inlinablity_for
== edge
)
1311 if (can_inline_edge_p (edge
, false)
1312 && want_inline_small_function_p (edge
, false))
1313 update_edge_key (heap
, edge
);
1316 report_inline_failed_reason (edge
);
1317 heap
->delete_node ((edge_heap_node_t
*) edge
->aux
);
1322 update_edge_key (heap
, edge
);
1326 /* Recompute HEAP nodes for each uninlined call in NODE.
1327 This is used when we know that edge badnesses are going only to increase
1328 (we introduced new call site) and thus all we need is to insert newly
1329 created edges into heap. */
1332 update_callee_keys (edge_heap_t
*heap
, struct cgraph_node
*node
,
1333 bitmap updated_nodes
)
1335 struct cgraph_edge
*e
= node
->callees
;
1340 if (!e
->inline_failed
&& e
->callee
->callees
)
1341 e
= e
->callee
->callees
;
1344 enum availability avail
;
1345 struct cgraph_node
*callee
;
1346 /* We do not reset callee growth cache here. Since we added a new call,
1347 growth chould have just increased and consequentely badness metric
1348 don't need updating. */
1349 if (e
->inline_failed
1350 && (callee
= e
->callee
->ultimate_alias_target (&avail
, e
->caller
))
1351 && ipa_fn_summaries
->get (callee
)->inlinable
1352 && avail
>= AVAIL_AVAILABLE
1353 && !bitmap_bit_p (updated_nodes
, callee
->uid
))
1355 if (can_inline_edge_p (e
, false)
1356 && want_inline_small_function_p (e
, false))
1357 update_edge_key (heap
, e
);
1360 report_inline_failed_reason (e
);
1361 heap
->delete_node ((edge_heap_node_t
*) e
->aux
);
1371 if (e
->caller
== node
)
1373 e
= e
->caller
->callers
;
1375 while (!e
->next_callee
);
1381 /* Enqueue all recursive calls from NODE into priority queue depending on
1382 how likely we want to recursively inline the call. */
1385 lookup_recursive_calls (struct cgraph_node
*node
, struct cgraph_node
*where
,
1388 struct cgraph_edge
*e
;
1389 enum availability avail
;
1391 for (e
= where
->callees
; e
; e
= e
->next_callee
)
1392 if (e
->callee
== node
1393 || (e
->callee
->ultimate_alias_target (&avail
, e
->caller
) == node
1394 && avail
> AVAIL_INTERPOSABLE
))
1395 heap
->insert (-e
->sreal_frequency (), e
);
1396 for (e
= where
->callees
; e
; e
= e
->next_callee
)
1397 if (!e
->inline_failed
)
1398 lookup_recursive_calls (node
, e
->callee
, heap
);
1401 /* Decide on recursive inlining: in the case function has recursive calls,
1402 inline until body size reaches given argument. If any new indirect edges
1403 are discovered in the process, add them to *NEW_EDGES, unless NEW_EDGES
1407 recursive_inlining (struct cgraph_edge
*edge
,
1408 vec
<cgraph_edge
*> *new_edges
)
1410 int limit
= PARAM_VALUE (PARAM_MAX_INLINE_INSNS_RECURSIVE_AUTO
);
1411 edge_heap_t
heap (sreal::min ());
1412 struct cgraph_node
*node
;
1413 struct cgraph_edge
*e
;
1414 struct cgraph_node
*master_clone
= NULL
, *next
;
1418 node
= edge
->caller
;
1419 if (node
->global
.inlined_to
)
1420 node
= node
->global
.inlined_to
;
1422 if (DECL_DECLARED_INLINE_P (node
->decl
))
1423 limit
= PARAM_VALUE (PARAM_MAX_INLINE_INSNS_RECURSIVE
);
1425 /* Make sure that function is small enough to be considered for inlining. */
1426 if (estimate_size_after_inlining (node
, edge
) >= limit
)
1428 lookup_recursive_calls (node
, node
, &heap
);
1434 " Performing recursive inlining on %s\n",
1437 /* Do the inlining and update list of recursive call during process. */
1438 while (!heap
.empty ())
1440 struct cgraph_edge
*curr
= heap
.extract_min ();
1441 struct cgraph_node
*cnode
, *dest
= curr
->callee
;
1443 if (!can_inline_edge_p (curr
, true))
1446 /* MASTER_CLONE is produced in the case we already started modified
1447 the function. Be sure to redirect edge to the original body before
1448 estimating growths otherwise we will be seeing growths after inlining
1449 the already modified body. */
1452 curr
->redirect_callee (master_clone
);
1453 reset_edge_growth_cache (curr
);
1456 if (estimate_size_after_inlining (node
, curr
) > limit
)
1458 curr
->redirect_callee (dest
);
1459 reset_edge_growth_cache (curr
);
1464 for (cnode
= curr
->caller
;
1465 cnode
->global
.inlined_to
; cnode
= cnode
->callers
->caller
)
1467 == curr
->callee
->ultimate_alias_target ()->decl
)
1470 if (!want_inline_self_recursive_call_p (curr
, node
, false, depth
))
1472 curr
->redirect_callee (dest
);
1473 reset_edge_growth_cache (curr
);
1480 " Inlining call of depth %i", depth
);
1481 if (node
->count
.nonzero_p ())
1483 fprintf (dump_file
, " called approx. %.2f times per call",
1484 (double)curr
->count
.to_gcov_type ()
1485 / node
->count
.to_gcov_type ());
1487 fprintf (dump_file
, "\n");
1491 /* We need original clone to copy around. */
1492 master_clone
= node
->create_clone (node
->decl
, node
->count
,
1493 false, vNULL
, true, NULL
, NULL
);
1494 for (e
= master_clone
->callees
; e
; e
= e
->next_callee
)
1495 if (!e
->inline_failed
)
1496 clone_inlined_nodes (e
, true, false, NULL
);
1497 curr
->redirect_callee (master_clone
);
1498 reset_edge_growth_cache (curr
);
1501 inline_call (curr
, false, new_edges
, &overall_size
, true);
1502 lookup_recursive_calls (node
, curr
->callee
, &heap
);
1506 if (!heap
.empty () && dump_file
)
1507 fprintf (dump_file
, " Recursive inlining growth limit met.\n");
1514 "\n Inlined %i times, "
1515 "body grown from size %i to %i, time %f to %f\n", n
,
1516 ipa_fn_summaries
->get (master_clone
)->size
,
1517 ipa_fn_summaries
->get (node
)->size
,
1518 ipa_fn_summaries
->get (master_clone
)->time
.to_double (),
1519 ipa_fn_summaries
->get (node
)->time
.to_double ());
1521 /* Remove master clone we used for inlining. We rely that clones inlined
1522 into master clone gets queued just before master clone so we don't
1524 for (node
= symtab
->first_function (); node
!= master_clone
;
1527 next
= symtab
->next_function (node
);
1528 if (node
->global
.inlined_to
== master_clone
)
1531 master_clone
->remove ();
1536 /* Given whole compilation unit estimate of INSNS, compute how large we can
1537 allow the unit to grow. */
1540 compute_max_insns (int insns
)
1542 int max_insns
= insns
;
1543 if (max_insns
< PARAM_VALUE (PARAM_LARGE_UNIT_INSNS
))
1544 max_insns
= PARAM_VALUE (PARAM_LARGE_UNIT_INSNS
);
1546 return ((int64_t) max_insns
1547 * (100 + PARAM_VALUE (PARAM_INLINE_UNIT_GROWTH
)) / 100);
1551 /* Compute badness of all edges in NEW_EDGES and add them to the HEAP. */
1554 add_new_edges_to_heap (edge_heap_t
*heap
, vec
<cgraph_edge
*> new_edges
)
1556 while (new_edges
.length () > 0)
1558 struct cgraph_edge
*edge
= new_edges
.pop ();
1560 gcc_assert (!edge
->aux
);
1561 if (edge
->inline_failed
1562 && can_inline_edge_p (edge
, true)
1563 && want_inline_small_function_p (edge
, true))
1564 edge
->aux
= heap
->insert (edge_badness (edge
, false), edge
);
1568 /* Remove EDGE from the fibheap. */
1571 heap_edge_removal_hook (struct cgraph_edge
*e
, void *data
)
1575 ((edge_heap_t
*)data
)->delete_node ((edge_heap_node_t
*)e
->aux
);
1580 /* Return true if speculation of edge E seems useful.
1581 If ANTICIPATE_INLINING is true, be conservative and hope that E
1585 speculation_useful_p (struct cgraph_edge
*e
, bool anticipate_inlining
)
1587 enum availability avail
;
1588 struct cgraph_node
*target
= e
->callee
->ultimate_alias_target (&avail
,
1590 struct cgraph_edge
*direct
, *indirect
;
1591 struct ipa_ref
*ref
;
1593 gcc_assert (e
->speculative
&& !e
->indirect_unknown_callee
);
1595 if (!e
->maybe_hot_p ())
1598 /* See if IP optimizations found something potentially useful about the
1599 function. For now we look only for CONST/PURE flags. Almost everything
1600 else we propagate is useless. */
1601 if (avail
>= AVAIL_AVAILABLE
)
1603 int ecf_flags
= flags_from_decl_or_type (target
->decl
);
1604 if (ecf_flags
& ECF_CONST
)
1606 e
->speculative_call_info (direct
, indirect
, ref
);
1607 if (!(indirect
->indirect_info
->ecf_flags
& ECF_CONST
))
1610 else if (ecf_flags
& ECF_PURE
)
1612 e
->speculative_call_info (direct
, indirect
, ref
);
1613 if (!(indirect
->indirect_info
->ecf_flags
& ECF_PURE
))
1617 /* If we did not managed to inline the function nor redirect
1618 to an ipa-cp clone (that are seen by having local flag set),
1619 it is probably pointless to inline it unless hardware is missing
1620 indirect call predictor. */
1621 if (!anticipate_inlining
&& e
->inline_failed
&& !target
->local
.local
)
1623 /* For overwritable targets there is not much to do. */
1624 if (e
->inline_failed
&& !can_inline_edge_p (e
, false, true))
1626 /* OK, speculation seems interesting. */
1630 /* We know that EDGE is not going to be inlined.
1631 See if we can remove speculation. */
1634 resolve_noninline_speculation (edge_heap_t
*edge_heap
, struct cgraph_edge
*edge
)
1636 if (edge
->speculative
&& !speculation_useful_p (edge
, false))
1638 struct cgraph_node
*node
= edge
->caller
;
1639 struct cgraph_node
*where
= node
->global
.inlined_to
1640 ? node
->global
.inlined_to
: node
;
1641 auto_bitmap updated_nodes
;
1643 if (edge
->count
.ipa ().initialized_p ())
1644 spec_rem
+= edge
->count
.ipa ();
1645 edge
->resolve_speculation ();
1646 reset_edge_caches (where
);
1647 ipa_update_overall_fn_summary (where
);
1648 update_caller_keys (edge_heap
, where
,
1649 updated_nodes
, NULL
);
1650 update_callee_keys (edge_heap
, where
,
1655 /* Return true if NODE should be accounted for overall size estimate.
1656 Skip all nodes optimized for size so we can measure the growth of hot
1657 part of program no matter of the padding. */
1660 inline_account_function_p (struct cgraph_node
*node
)
1662 return (!DECL_EXTERNAL (node
->decl
)
1663 && !opt_for_fn (node
->decl
, optimize_size
)
1664 && node
->frequency
!= NODE_FREQUENCY_UNLIKELY_EXECUTED
);
1667 /* Count number of callers of NODE and store it into DATA (that
1668 points to int. Worker for cgraph_for_node_and_aliases. */
1671 sum_callers (struct cgraph_node
*node
, void *data
)
1673 struct cgraph_edge
*e
;
1674 int *num_calls
= (int *)data
;
1676 for (e
= node
->callers
; e
; e
= e
->next_caller
)
1681 /* We use greedy algorithm for inlining of small functions:
1682 All inline candidates are put into prioritized heap ordered in
1685 The inlining of small functions is bounded by unit growth parameters. */
1688 inline_small_functions (void)
1690 struct cgraph_node
*node
;
1691 struct cgraph_edge
*edge
;
1692 edge_heap_t
edge_heap (sreal::min ());
1693 auto_bitmap updated_nodes
;
1694 int min_size
, max_size
;
1695 auto_vec
<cgraph_edge
*> new_indirect_edges
;
1696 int initial_size
= 0;
1697 struct cgraph_node
**order
= XCNEWVEC (cgraph_node
*, symtab
->cgraph_count
);
1698 struct cgraph_edge_hook_list
*edge_removal_hook_holder
;
1699 new_indirect_edges
.create (8);
1701 edge_removal_hook_holder
1702 = symtab
->add_edge_removal_hook (&heap_edge_removal_hook
, &edge_heap
);
1704 /* Compute overall unit size and other global parameters used by badness
1707 max_count
= profile_count::uninitialized ();
1708 ipa_reduced_postorder (order
, true, true, NULL
);
1711 FOR_EACH_DEFINED_FUNCTION (node
)
1712 if (!node
->global
.inlined_to
)
1714 if (!node
->alias
&& node
->analyzed
1715 && (node
->has_gimple_body_p () || node
->thunk
.thunk_p
)
1716 && opt_for_fn (node
->decl
, optimize
))
1718 struct ipa_fn_summary
*info
= ipa_fn_summaries
->get (node
);
1719 struct ipa_dfs_info
*dfs
= (struct ipa_dfs_info
*) node
->aux
;
1721 /* Do not account external functions, they will be optimized out
1722 if not inlined. Also only count the non-cold portion of program. */
1723 if (inline_account_function_p (node
))
1724 initial_size
+= info
->size
;
1725 info
->growth
= estimate_growth (node
);
1728 node
->call_for_symbol_and_aliases (sum_callers
, &num_calls
,
1731 info
->single_caller
= true;
1732 if (dfs
&& dfs
->next_cycle
)
1734 struct cgraph_node
*n2
;
1735 int id
= dfs
->scc_no
+ 1;
1737 n2
= ((struct ipa_dfs_info
*) node
->aux
)->next_cycle
)
1738 if (opt_for_fn (n2
->decl
, optimize
))
1740 struct ipa_fn_summary
*info2
= ipa_fn_summaries
->get (n2
);
1748 for (edge
= node
->callers
; edge
; edge
= edge
->next_caller
)
1749 max_count
= max_count
.max (edge
->count
.ipa ());
1751 ipa_free_postorder_info ();
1752 initialize_growth_caches ();
1756 "\nDeciding on inlining of small functions. Starting with size %i.\n",
1759 overall_size
= initial_size
;
1760 max_size
= compute_max_insns (overall_size
);
1761 min_size
= overall_size
;
1763 /* Populate the heap with all edges we might inline. */
1765 FOR_EACH_DEFINED_FUNCTION (node
)
1767 bool update
= false;
1768 struct cgraph_edge
*next
= NULL
;
1769 bool has_speculative
= false;
1771 if (!opt_for_fn (node
->decl
, optimize
))
1775 fprintf (dump_file
, "Enqueueing calls in %s.\n", node
->dump_name ());
1777 for (edge
= node
->callees
; edge
; edge
= next
)
1779 next
= edge
->next_callee
;
1780 if (edge
->inline_failed
1782 && can_inline_edge_p (edge
, true)
1783 && want_inline_small_function_p (edge
, true)
1784 && edge
->inline_failed
)
1786 gcc_assert (!edge
->aux
);
1787 update_edge_key (&edge_heap
, edge
);
1789 if (edge
->speculative
)
1790 has_speculative
= true;
1792 if (has_speculative
)
1793 for (edge
= node
->callees
; edge
; edge
= next
)
1794 if (edge
->speculative
&& !speculation_useful_p (edge
,
1797 edge
->resolve_speculation ();
1802 struct cgraph_node
*where
= node
->global
.inlined_to
1803 ? node
->global
.inlined_to
: node
;
1804 ipa_update_overall_fn_summary (where
);
1805 reset_edge_caches (where
);
1806 update_caller_keys (&edge_heap
, where
,
1807 updated_nodes
, NULL
);
1808 update_callee_keys (&edge_heap
, where
,
1810 bitmap_clear (updated_nodes
);
1814 gcc_assert (in_lto_p
1816 || (profile_info
&& flag_branch_probabilities
));
1818 while (!edge_heap
.empty ())
1820 int old_size
= overall_size
;
1821 struct cgraph_node
*where
, *callee
;
1822 sreal badness
= edge_heap
.min_key ();
1823 sreal current_badness
;
1826 edge
= edge_heap
.extract_min ();
1827 gcc_assert (edge
->aux
);
1829 if (!edge
->inline_failed
|| !edge
->callee
->analyzed
)
1833 /* Be sure that caches are maintained consistent.
1834 This check is affected by scaling roundoff errors when compiling for
1835 IPA this we skip it in that case. */
1836 if (!edge
->callee
->count
.ipa_p ()
1837 && (!max_count
.initialized_p () || !max_count
.nonzero_p ()))
1839 sreal cached_badness
= edge_badness (edge
, false);
1841 int old_size_est
= estimate_edge_size (edge
);
1842 sreal old_time_est
= estimate_edge_time (edge
);
1843 int old_hints_est
= estimate_edge_hints (edge
);
1845 reset_edge_growth_cache (edge
);
1846 gcc_assert (old_size_est
== estimate_edge_size (edge
));
1847 gcc_assert (old_time_est
== estimate_edge_time (edge
));
1850 gcc_assert (old_hints_est == estimate_edge_hints (edge));
1852 fails with profile feedback because some hints depends on
1853 maybe_hot_edge_p predicate and because callee gets inlined to other
1854 calls, the edge may become cold.
1855 This ought to be fixed by computing relative probabilities
1856 for given invocation but that will be better done once whole
1857 code is converted to sreals. Disable for now and revert to "wrong"
1858 value so enable/disable checking paths agree. */
1859 edge_growth_cache
[edge
->uid
].hints
= old_hints_est
+ 1;
1861 /* When updating the edge costs, we only decrease badness in the keys.
1862 Increases of badness are handled lazilly; when we see key with out
1863 of date value on it, we re-insert it now. */
1864 current_badness
= edge_badness (edge
, false);
1865 gcc_assert (cached_badness
== current_badness
);
1866 gcc_assert (current_badness
>= badness
);
1869 current_badness
= edge_badness (edge
, false);
1871 current_badness
= edge_badness (edge
, false);
1873 if (current_badness
!= badness
)
1875 if (edge_heap
.min () && current_badness
> edge_heap
.min_key ())
1877 edge
->aux
= edge_heap
.insert (current_badness
, edge
);
1881 badness
= current_badness
;
1884 if (!can_inline_edge_p (edge
, true))
1886 resolve_noninline_speculation (&edge_heap
, edge
);
1890 callee
= edge
->callee
->ultimate_alias_target ();
1891 growth
= estimate_edge_growth (edge
);
1895 "\nConsidering %s with %i size\n",
1896 callee
->dump_name (),
1897 ipa_fn_summaries
->get (callee
)->size
);
1899 " to be inlined into %s in %s:%i\n"
1900 " Estimated badness is %f, frequency %.2f.\n",
1901 edge
->caller
->dump_name (),
1903 && (LOCATION_LOCUS (gimple_location ((const gimple
*)
1905 > BUILTINS_LOCATION
)
1906 ? gimple_filename ((const gimple
*) edge
->call_stmt
)
1909 ? gimple_lineno ((const gimple
*) edge
->call_stmt
)
1911 badness
.to_double (),
1912 edge
->sreal_frequency ().to_double ());
1913 if (edge
->count
.ipa ().initialized_p ())
1915 fprintf (dump_file
, " Called ");
1916 edge
->count
.ipa ().dump (dump_file
);
1917 fprintf (dump_file
, " times\n");
1919 if (dump_flags
& TDF_DETAILS
)
1920 edge_badness (edge
, true);
1923 if (overall_size
+ growth
> max_size
1924 && !DECL_DISREGARD_INLINE_LIMITS (callee
->decl
))
1926 edge
->inline_failed
= CIF_INLINE_UNIT_GROWTH_LIMIT
;
1927 report_inline_failed_reason (edge
);
1928 resolve_noninline_speculation (&edge_heap
, edge
);
1932 if (!want_inline_small_function_p (edge
, true))
1934 resolve_noninline_speculation (&edge_heap
, edge
);
1938 /* Heuristics for inlining small functions work poorly for
1939 recursive calls where we do effects similar to loop unrolling.
1940 When inlining such edge seems profitable, leave decision on
1941 specific inliner. */
1942 if (edge
->recursive_p ())
1944 where
= edge
->caller
;
1945 if (where
->global
.inlined_to
)
1946 where
= where
->global
.inlined_to
;
1947 if (!recursive_inlining (edge
,
1948 opt_for_fn (edge
->caller
->decl
,
1949 flag_indirect_inlining
)
1950 ? &new_indirect_edges
: NULL
))
1952 edge
->inline_failed
= CIF_RECURSIVE_INLINING
;
1953 resolve_noninline_speculation (&edge_heap
, edge
);
1956 reset_edge_caches (where
);
1957 /* Recursive inliner inlines all recursive calls of the function
1958 at once. Consequently we need to update all callee keys. */
1959 if (opt_for_fn (edge
->caller
->decl
, flag_indirect_inlining
))
1960 add_new_edges_to_heap (&edge_heap
, new_indirect_edges
);
1961 update_callee_keys (&edge_heap
, where
, updated_nodes
);
1962 bitmap_clear (updated_nodes
);
1966 struct cgraph_node
*outer_node
= NULL
;
1969 /* Consider the case where self recursive function A is inlined
1970 into B. This is desired optimization in some cases, since it
1971 leads to effect similar of loop peeling and we might completely
1972 optimize out the recursive call. However we must be extra
1975 where
= edge
->caller
;
1976 while (where
->global
.inlined_to
)
1978 if (where
->decl
== callee
->decl
)
1979 outer_node
= where
, depth
++;
1980 where
= where
->callers
->caller
;
1983 && !want_inline_self_recursive_call_p (edge
, outer_node
,
1987 = (DECL_DISREGARD_INLINE_LIMITS (edge
->callee
->decl
)
1988 ? CIF_RECURSIVE_INLINING
: CIF_UNSPECIFIED
);
1989 resolve_noninline_speculation (&edge_heap
, edge
);
1992 else if (depth
&& dump_file
)
1993 fprintf (dump_file
, " Peeling recursion with depth %i\n", depth
);
1995 gcc_checking_assert (!callee
->global
.inlined_to
);
1996 inline_call (edge
, true, &new_indirect_edges
, &overall_size
, true);
1997 add_new_edges_to_heap (&edge_heap
, new_indirect_edges
);
1999 reset_edge_caches (edge
->callee
);
2001 update_callee_keys (&edge_heap
, where
, updated_nodes
);
2003 where
= edge
->caller
;
2004 if (where
->global
.inlined_to
)
2005 where
= where
->global
.inlined_to
;
2007 /* Our profitability metric can depend on local properties
2008 such as number of inlinable calls and size of the function body.
2009 After inlining these properties might change for the function we
2010 inlined into (since it's body size changed) and for the functions
2011 called by function we inlined (since number of it inlinable callers
2013 update_caller_keys (&edge_heap
, where
, updated_nodes
, NULL
);
2014 /* Offline copy count has possibly changed, recompute if profile is
2016 struct cgraph_node
*n
= cgraph_node::get (edge
->callee
->decl
);
2017 if (n
!= edge
->callee
&& n
->analyzed
&& n
->count
.ipa ().initialized_p ())
2018 update_callee_keys (&edge_heap
, n
, updated_nodes
);
2019 bitmap_clear (updated_nodes
);
2024 " Inlined %s into %s which now has time %f and size %i, "
2025 "net change of %+i.\n",
2026 xstrdup_for_dump (edge
->callee
->name ()),
2027 xstrdup_for_dump (edge
->caller
->name ()),
2028 ipa_fn_summaries
->get (edge
->caller
)->time
.to_double (),
2029 ipa_fn_summaries
->get (edge
->caller
)->size
,
2030 overall_size
- old_size
);
2032 if (min_size
> overall_size
)
2034 min_size
= overall_size
;
2035 max_size
= compute_max_insns (min_size
);
2038 fprintf (dump_file
, "New minimal size reached: %i\n", min_size
);
2042 free_growth_caches ();
2045 "Unit growth for small function inlining: %i->%i (%i%%)\n",
2046 initial_size
, overall_size
,
2047 initial_size
? overall_size
* 100 / (initial_size
) - 100: 0);
2048 symtab
->remove_edge_removal_hook (edge_removal_hook_holder
);
2051 /* Flatten NODE. Performed both during early inlining and
2052 at IPA inlining time. */
2055 flatten_function (struct cgraph_node
*node
, bool early
)
2057 struct cgraph_edge
*e
;
2059 /* We shouldn't be called recursively when we are being processed. */
2060 gcc_assert (node
->aux
== NULL
);
2062 node
->aux
= (void *) node
;
2064 for (e
= node
->callees
; e
; e
= e
->next_callee
)
2066 struct cgraph_node
*orig_callee
;
2067 struct cgraph_node
*callee
= e
->callee
->ultimate_alias_target ();
2069 /* We've hit cycle? It is time to give up. */
2074 "Not inlining %s into %s to avoid cycle.\n",
2075 xstrdup_for_dump (callee
->name ()),
2076 xstrdup_for_dump (e
->caller
->name ()));
2077 e
->inline_failed
= CIF_RECURSIVE_INLINING
;
2081 /* When the edge is already inlined, we just need to recurse into
2082 it in order to fully flatten the leaves. */
2083 if (!e
->inline_failed
)
2085 flatten_function (callee
, early
);
2089 /* Flatten attribute needs to be processed during late inlining. For
2090 extra code quality we however do flattening during early optimization,
2093 ? !can_inline_edge_p (e
, true)
2094 : !can_early_inline_edge_p (e
))
2097 if (e
->recursive_p ())
2100 fprintf (dump_file
, "Not inlining: recursive call.\n");
2104 if (gimple_in_ssa_p (DECL_STRUCT_FUNCTION (node
->decl
))
2105 != gimple_in_ssa_p (DECL_STRUCT_FUNCTION (callee
->decl
)))
2108 fprintf (dump_file
, "Not inlining: SSA form does not match.\n");
2112 /* Inline the edge and flatten the inline clone. Avoid
2113 recursing through the original node if the node was cloned. */
2115 fprintf (dump_file
, " Inlining %s into %s.\n",
2116 xstrdup_for_dump (callee
->name ()),
2117 xstrdup_for_dump (e
->caller
->name ()));
2118 orig_callee
= callee
;
2119 inline_call (e
, true, NULL
, NULL
, false);
2120 if (e
->callee
!= orig_callee
)
2121 orig_callee
->aux
= (void *) node
;
2122 flatten_function (e
->callee
, early
);
2123 if (e
->callee
!= orig_callee
)
2124 orig_callee
->aux
= NULL
;
2128 if (!node
->global
.inlined_to
)
2129 ipa_update_overall_fn_summary (node
);
2132 /* Inline NODE to all callers. Worker for cgraph_for_node_and_aliases.
2133 DATA points to number of calls originally found so we avoid infinite
2137 inline_to_all_callers_1 (struct cgraph_node
*node
, void *data
,
2138 hash_set
<cgraph_node
*> *callers
)
2140 int *num_calls
= (int *)data
;
2141 bool callee_removed
= false;
2143 while (node
->callers
&& !node
->global
.inlined_to
)
2145 struct cgraph_node
*caller
= node
->callers
->caller
;
2147 if (!can_inline_edge_p (node
->callers
, true)
2148 || node
->callers
->recursive_p ())
2151 fprintf (dump_file
, "Uninlinable call found; giving up.\n");
2159 "\nInlining %s size %i.\n",
2161 ipa_fn_summaries
->get (node
)->size
);
2163 " Called once from %s %i insns.\n",
2164 node
->callers
->caller
->name (),
2165 ipa_fn_summaries
->get (node
->callers
->caller
)->size
);
2168 /* Remember which callers we inlined to, delaying updating the
2170 callers
->add (node
->callers
->caller
);
2171 inline_call (node
->callers
, true, NULL
, NULL
, false, &callee_removed
);
2174 " Inlined into %s which now has %i size\n",
2176 ipa_fn_summaries
->get (caller
)->size
);
2177 if (!(*num_calls
)--)
2180 fprintf (dump_file
, "New calls found; giving up.\n");
2181 return callee_removed
;
2189 /* Wrapper around inline_to_all_callers_1 doing delayed overall summary
2193 inline_to_all_callers (struct cgraph_node
*node
, void *data
)
2195 hash_set
<cgraph_node
*> callers
;
2196 bool res
= inline_to_all_callers_1 (node
, data
, &callers
);
2197 /* Perform the delayed update of the overall summary of all callers
2198 processed. This avoids quadratic behavior in the cases where
2199 we have a lot of calls to the same function. */
2200 for (hash_set
<cgraph_node
*>::iterator i
= callers
.begin ();
2201 i
!= callers
.end (); ++i
)
2202 ipa_update_overall_fn_summary (*i
);
2206 /* Output overall time estimate. */
2208 dump_overall_stats (void)
2210 sreal sum_weighted
= 0, sum
= 0;
2211 struct cgraph_node
*node
;
2213 FOR_EACH_DEFINED_FUNCTION (node
)
2214 if (!node
->global
.inlined_to
2217 sreal time
= ipa_fn_summaries
->get (node
)->time
;
2219 if (node
->count
.ipa ().initialized_p ())
2220 sum_weighted
+= time
* node
->count
.ipa ().to_gcov_type ();
2222 fprintf (dump_file
, "Overall time estimate: "
2223 "%f weighted by profile: "
2224 "%f\n", sum
.to_double (), sum_weighted
.to_double ());
2227 /* Output some useful stats about inlining. */
2230 dump_inline_stats (void)
2232 int64_t inlined_cnt
= 0, inlined_indir_cnt
= 0;
2233 int64_t inlined_virt_cnt
= 0, inlined_virt_indir_cnt
= 0;
2234 int64_t noninlined_cnt
= 0, noninlined_indir_cnt
= 0;
2235 int64_t noninlined_virt_cnt
= 0, noninlined_virt_indir_cnt
= 0;
2236 int64_t inlined_speculative
= 0, inlined_speculative_ply
= 0;
2237 int64_t indirect_poly_cnt
= 0, indirect_cnt
= 0;
2238 int64_t reason
[CIF_N_REASONS
][2];
2239 sreal reason_freq
[CIF_N_REASONS
];
2241 struct cgraph_node
*node
;
2243 memset (reason
, 0, sizeof (reason
));
2244 for (i
=0; i
< CIF_N_REASONS
; i
++)
2246 FOR_EACH_DEFINED_FUNCTION (node
)
2248 struct cgraph_edge
*e
;
2249 for (e
= node
->callees
; e
; e
= e
->next_callee
)
2251 if (e
->inline_failed
)
2253 if (e
->count
.ipa ().initialized_p ())
2254 reason
[(int) e
->inline_failed
][0] += e
->count
.ipa ().to_gcov_type ();
2255 reason_freq
[(int) e
->inline_failed
] += e
->sreal_frequency ();
2256 reason
[(int) e
->inline_failed
][1] ++;
2257 if (DECL_VIRTUAL_P (e
->callee
->decl
)
2258 && e
->count
.ipa ().initialized_p ())
2260 if (e
->indirect_inlining_edge
)
2261 noninlined_virt_indir_cnt
+= e
->count
.ipa ().to_gcov_type ();
2263 noninlined_virt_cnt
+= e
->count
.ipa ().to_gcov_type ();
2265 else if (e
->count
.ipa ().initialized_p ())
2267 if (e
->indirect_inlining_edge
)
2268 noninlined_indir_cnt
+= e
->count
.ipa ().to_gcov_type ();
2270 noninlined_cnt
+= e
->count
.ipa ().to_gcov_type ();
2273 else if (e
->count
.ipa ().initialized_p ())
2277 if (DECL_VIRTUAL_P (e
->callee
->decl
))
2278 inlined_speculative_ply
+= e
->count
.ipa ().to_gcov_type ();
2280 inlined_speculative
+= e
->count
.ipa ().to_gcov_type ();
2282 else if (DECL_VIRTUAL_P (e
->callee
->decl
))
2284 if (e
->indirect_inlining_edge
)
2285 inlined_virt_indir_cnt
+= e
->count
.ipa ().to_gcov_type ();
2287 inlined_virt_cnt
+= e
->count
.ipa ().to_gcov_type ();
2291 if (e
->indirect_inlining_edge
)
2292 inlined_indir_cnt
+= e
->count
.ipa ().to_gcov_type ();
2294 inlined_cnt
+= e
->count
.ipa ().to_gcov_type ();
2298 for (e
= node
->indirect_calls
; e
; e
= e
->next_callee
)
2299 if (e
->indirect_info
->polymorphic
2300 & e
->count
.ipa ().initialized_p ())
2301 indirect_poly_cnt
+= e
->count
.ipa ().to_gcov_type ();
2302 else if (e
->count
.ipa ().initialized_p ())
2303 indirect_cnt
+= e
->count
.ipa ().to_gcov_type ();
2305 if (max_count
.initialized_p ())
2308 "Inlined %" PRId64
" + speculative "
2309 "%" PRId64
" + speculative polymorphic "
2310 "%" PRId64
" + previously indirect "
2311 "%" PRId64
" + virtual "
2312 "%" PRId64
" + virtual and previously indirect "
2313 "%" PRId64
"\n" "Not inlined "
2314 "%" PRId64
" + previously indirect "
2315 "%" PRId64
" + virtual "
2316 "%" PRId64
" + virtual and previously indirect "
2317 "%" PRId64
" + stil indirect "
2318 "%" PRId64
" + still indirect polymorphic "
2319 "%" PRId64
"\n", inlined_cnt
,
2320 inlined_speculative
, inlined_speculative_ply
,
2321 inlined_indir_cnt
, inlined_virt_cnt
, inlined_virt_indir_cnt
,
2322 noninlined_cnt
, noninlined_indir_cnt
, noninlined_virt_cnt
,
2323 noninlined_virt_indir_cnt
, indirect_cnt
, indirect_poly_cnt
);
2324 fprintf (dump_file
, "Removed speculations ");
2325 spec_rem
.dump (dump_file
);
2326 fprintf (dump_file
, "\n");
2328 dump_overall_stats ();
2329 fprintf (dump_file
, "\nWhy inlining failed?\n");
2330 for (i
= 0; i
< CIF_N_REASONS
; i
++)
2332 fprintf (dump_file
, "%-50s: %8i calls, %8f freq, %" PRId64
" count\n",
2333 cgraph_inline_failed_string ((cgraph_inline_failed_t
) i
),
2334 (int) reason
[i
][1], reason_freq
[i
].to_double (), reason
[i
][0]);
2337 /* Decide on the inlining. We do so in the topological order to avoid
2338 expenses on updating data structures. */
2343 struct cgraph_node
*node
;
2345 struct cgraph_node
**order
;
2348 bool remove_functions
= false;
2350 order
= XCNEWVEC (struct cgraph_node
*, symtab
->cgraph_count
);
2353 ipa_dump_fn_summaries (dump_file
);
2355 nnodes
= ipa_reverse_postorder (order
);
2356 spec_rem
= profile_count::zero ();
2358 FOR_EACH_FUNCTION (node
)
2362 /* Recompute the default reasons for inlining because they may have
2363 changed during merging. */
2366 for (cgraph_edge
*e
= node
->callees
; e
; e
= e
->next_callee
)
2368 gcc_assert (e
->inline_failed
);
2369 initialize_inline_failed (e
);
2371 for (cgraph_edge
*e
= node
->indirect_calls
; e
; e
= e
->next_callee
)
2372 initialize_inline_failed (e
);
2377 fprintf (dump_file
, "\nFlattening functions:\n");
2379 /* In the first pass handle functions to be flattened. Do this with
2380 a priority so none of our later choices will make this impossible. */
2381 for (i
= nnodes
- 1; i
>= 0; i
--)
2385 /* Handle nodes to be flattened.
2386 Ideally when processing callees we stop inlining at the
2387 entry of cycles, possibly cloning that entry point and
2388 try to flatten itself turning it into a self-recursive
2390 if (lookup_attribute ("flatten",
2391 DECL_ATTRIBUTES (node
->decl
)) != NULL
)
2395 "Flattening %s\n", node
->name ());
2396 flatten_function (node
, false);
2400 dump_overall_stats ();
2402 inline_small_functions ();
2404 gcc_assert (symtab
->state
== IPA_SSA
);
2405 symtab
->state
= IPA_SSA_AFTER_INLINING
;
2406 /* Do first after-inlining removal. We want to remove all "stale" extern
2407 inline functions and virtual functions so we really know what is called
2409 symtab
->remove_unreachable_nodes (dump_file
);
2412 /* Inline functions with a property that after inlining into all callers the
2413 code size will shrink because the out-of-line copy is eliminated.
2414 We do this regardless on the callee size as long as function growth limits
2418 "\nDeciding on functions to be inlined into all callers and "
2419 "removing useless speculations:\n");
2421 /* Inlining one function called once has good chance of preventing
2422 inlining other function into the same callee. Ideally we should
2423 work in priority order, but probably inlining hot functions first
2424 is good cut without the extra pain of maintaining the queue.
2426 ??? this is not really fitting the bill perfectly: inlining function
2427 into callee often leads to better optimization of callee due to
2428 increased context for optimization.
2429 For example if main() function calls a function that outputs help
2430 and then function that does the main optmization, we should inline
2431 the second with priority even if both calls are cold by themselves.
2433 We probably want to implement new predicate replacing our use of
2434 maybe_hot_edge interpreted as maybe_hot_edge || callee is known
2436 for (cold
= 0; cold
<= 1; cold
++)
2438 FOR_EACH_DEFINED_FUNCTION (node
)
2440 struct cgraph_edge
*edge
, *next
;
2443 if (!opt_for_fn (node
->decl
, optimize
)
2444 || !opt_for_fn (node
->decl
, flag_inline_functions_called_once
))
2447 for (edge
= node
->callees
; edge
; edge
= next
)
2449 next
= edge
->next_callee
;
2450 if (edge
->speculative
&& !speculation_useful_p (edge
, false))
2452 if (edge
->count
.ipa ().initialized_p ())
2453 spec_rem
+= edge
->count
.ipa ();
2454 edge
->resolve_speculation ();
2456 remove_functions
= true;
2461 struct cgraph_node
*where
= node
->global
.inlined_to
2462 ? node
->global
.inlined_to
: node
;
2463 reset_edge_caches (where
);
2464 ipa_update_overall_fn_summary (where
);
2466 if (want_inline_function_to_all_callers_p (node
, cold
))
2469 node
->call_for_symbol_and_aliases (sum_callers
, &num_calls
,
2471 while (node
->call_for_symbol_and_aliases
2472 (inline_to_all_callers
, &num_calls
, true))
2474 remove_functions
= true;
2479 /* Free ipa-prop structures if they are no longer needed. */
2480 ipa_free_all_structures_after_iinln ();
2485 "\nInlined %i calls, eliminated %i functions\n\n",
2486 ncalls_inlined
, nfunctions_inlined
);
2487 dump_inline_stats ();
2491 ipa_dump_fn_summaries (dump_file
);
2492 return remove_functions
? TODO_remove_functions
: 0;
2495 /* Inline always-inline function calls in NODE. */
2498 inline_always_inline_functions (struct cgraph_node
*node
)
2500 struct cgraph_edge
*e
;
2501 bool inlined
= false;
2503 for (e
= node
->callees
; e
; e
= e
->next_callee
)
2505 struct cgraph_node
*callee
= e
->callee
->ultimate_alias_target ();
2506 if (!DECL_DISREGARD_INLINE_LIMITS (callee
->decl
))
2509 if (e
->recursive_p ())
2512 fprintf (dump_file
, " Not inlining recursive call to %s.\n",
2513 e
->callee
->name ());
2514 e
->inline_failed
= CIF_RECURSIVE_INLINING
;
2518 if (!can_early_inline_edge_p (e
))
2520 /* Set inlined to true if the callee is marked "always_inline" but
2521 is not inlinable. This will allow flagging an error later in
2522 expand_call_inline in tree-inline.c. */
2523 if (lookup_attribute ("always_inline",
2524 DECL_ATTRIBUTES (callee
->decl
)) != NULL
)
2530 fprintf (dump_file
, " Inlining %s into %s (always_inline).\n",
2531 xstrdup_for_dump (e
->callee
->name ()),
2532 xstrdup_for_dump (e
->caller
->name ()));
2533 inline_call (e
, true, NULL
, NULL
, false);
2537 ipa_update_overall_fn_summary (node
);
2542 /* Decide on the inlining. We do so in the topological order to avoid
2543 expenses on updating data structures. */
2546 early_inline_small_functions (struct cgraph_node
*node
)
2548 struct cgraph_edge
*e
;
2549 bool inlined
= false;
2551 for (e
= node
->callees
; e
; e
= e
->next_callee
)
2553 struct cgraph_node
*callee
= e
->callee
->ultimate_alias_target ();
2554 if (!ipa_fn_summaries
->get (callee
)->inlinable
2555 || !e
->inline_failed
)
2558 /* Do not consider functions not declared inline. */
2559 if (!DECL_DECLARED_INLINE_P (callee
->decl
)
2560 && !opt_for_fn (node
->decl
, flag_inline_small_functions
)
2561 && !opt_for_fn (node
->decl
, flag_inline_functions
))
2565 fprintf (dump_file
, "Considering inline candidate %s.\n",
2568 if (!can_early_inline_edge_p (e
))
2571 if (e
->recursive_p ())
2574 fprintf (dump_file
, " Not inlining: recursive call.\n");
2578 if (!want_early_inline_function_p (e
))
2582 fprintf (dump_file
, " Inlining %s into %s.\n",
2583 xstrdup_for_dump (callee
->name ()),
2584 xstrdup_for_dump (e
->caller
->name ()));
2585 inline_call (e
, true, NULL
, NULL
, false);
2590 ipa_update_overall_fn_summary (node
);
2596 early_inliner (function
*fun
)
2598 struct cgraph_node
*node
= cgraph_node::get (current_function_decl
);
2599 struct cgraph_edge
*edge
;
2600 unsigned int todo
= 0;
2602 bool inlined
= false;
2607 /* Do nothing if datastructures for ipa-inliner are already computed. This
2608 happens when some pass decides to construct new function and
2609 cgraph_add_new_function calls lowering passes and early optimization on
2610 it. This may confuse ourself when early inliner decide to inline call to
2611 function clone, because function clones don't have parameter list in
2612 ipa-prop matching their signature. */
2613 if (ipa_node_params_sum
)
2618 node
->remove_all_references ();
2620 /* Rebuild this reference because it dosn't depend on
2621 function's body and it's required to pass cgraph_node
2623 if (node
->instrumented_version
2624 && !node
->instrumentation_clone
)
2625 node
->create_reference (node
->instrumented_version
, IPA_REF_CHKP
, NULL
);
2627 /* Even when not optimizing or not inlining inline always-inline
2629 inlined
= inline_always_inline_functions (node
);
2633 || !flag_early_inlining
2634 /* Never inline regular functions into always-inline functions
2635 during incremental inlining. This sucks as functions calling
2636 always inline functions will get less optimized, but at the
2637 same time inlining of functions calling always inline
2638 function into an always inline function might introduce
2639 cycles of edges to be always inlined in the callgraph.
2641 We might want to be smarter and just avoid this type of inlining. */
2642 || (DECL_DISREGARD_INLINE_LIMITS (node
->decl
)
2643 && lookup_attribute ("always_inline",
2644 DECL_ATTRIBUTES (node
->decl
))))
2646 else if (lookup_attribute ("flatten",
2647 DECL_ATTRIBUTES (node
->decl
)) != NULL
)
2649 /* When the function is marked to be flattened, recursively inline
2653 "Flattening %s\n", node
->name ());
2654 flatten_function (node
, true);
2659 /* If some always_inline functions was inlined, apply the changes.
2660 This way we will not account always inline into growth limits and
2661 moreover we will inline calls from always inlines that we skipped
2662 previously because of conditional above. */
2665 timevar_push (TV_INTEGRATION
);
2666 todo
|= optimize_inline_calls (current_function_decl
);
2667 /* optimize_inline_calls call above might have introduced new
2668 statements that don't have inline parameters computed. */
2669 for (edge
= node
->callees
; edge
; edge
= edge
->next_callee
)
2671 struct ipa_call_summary
*es
= ipa_call_summaries
->get (edge
);
2673 = estimate_num_insns (edge
->call_stmt
, &eni_size_weights
);
2675 = estimate_num_insns (edge
->call_stmt
, &eni_time_weights
);
2677 ipa_update_overall_fn_summary (node
);
2679 timevar_pop (TV_INTEGRATION
);
2681 /* We iterate incremental inlining to get trivial cases of indirect
2683 while (iterations
< PARAM_VALUE (PARAM_EARLY_INLINER_MAX_ITERATIONS
)
2684 && early_inline_small_functions (node
))
2686 timevar_push (TV_INTEGRATION
);
2687 todo
|= optimize_inline_calls (current_function_decl
);
2689 /* Technically we ought to recompute inline parameters so the new
2690 iteration of early inliner works as expected. We however have
2691 values approximately right and thus we only need to update edge
2692 info that might be cleared out for newly discovered edges. */
2693 for (edge
= node
->callees
; edge
; edge
= edge
->next_callee
)
2695 /* We have no summary for new bound store calls yet. */
2696 struct ipa_call_summary
*es
= ipa_call_summaries
->get (edge
);
2698 = estimate_num_insns (edge
->call_stmt
, &eni_size_weights
);
2700 = estimate_num_insns (edge
->call_stmt
, &eni_time_weights
);
2702 if (edge
->callee
->decl
2703 && !gimple_check_call_matching_types (
2704 edge
->call_stmt
, edge
->callee
->decl
, false))
2706 edge
->inline_failed
= CIF_MISMATCHED_ARGUMENTS
;
2707 edge
->call_stmt_cannot_inline_p
= true;
2710 if (iterations
< PARAM_VALUE (PARAM_EARLY_INLINER_MAX_ITERATIONS
) - 1)
2711 ipa_update_overall_fn_summary (node
);
2712 timevar_pop (TV_INTEGRATION
);
2717 fprintf (dump_file
, "Iterations: %i\n", iterations
);
2722 timevar_push (TV_INTEGRATION
);
2723 todo
|= optimize_inline_calls (current_function_decl
);
2724 timevar_pop (TV_INTEGRATION
);
2727 fun
->always_inline_functions_inlined
= true;
2732 /* Do inlining of small functions. Doing so early helps profiling and other
2733 passes to be somewhat more effective and avoids some code duplication in
2734 later real inlining pass for testcases with very many function calls. */
2738 const pass_data pass_data_early_inline
=
2740 GIMPLE_PASS
, /* type */
2741 "einline", /* name */
2742 OPTGROUP_INLINE
, /* optinfo_flags */
2743 TV_EARLY_INLINING
, /* tv_id */
2744 PROP_ssa
, /* properties_required */
2745 0, /* properties_provided */
2746 0, /* properties_destroyed */
2747 0, /* todo_flags_start */
2748 0, /* todo_flags_finish */
2751 class pass_early_inline
: public gimple_opt_pass
2754 pass_early_inline (gcc::context
*ctxt
)
2755 : gimple_opt_pass (pass_data_early_inline
, ctxt
)
2758 /* opt_pass methods: */
2759 virtual unsigned int execute (function
*);
2761 }; // class pass_early_inline
2764 pass_early_inline::execute (function
*fun
)
2766 return early_inliner (fun
);
2772 make_pass_early_inline (gcc::context
*ctxt
)
2774 return new pass_early_inline (ctxt
);
2779 const pass_data pass_data_ipa_inline
=
2781 IPA_PASS
, /* type */
2782 "inline", /* name */
2783 OPTGROUP_INLINE
, /* optinfo_flags */
2784 TV_IPA_INLINING
, /* tv_id */
2785 0, /* properties_required */
2786 0, /* properties_provided */
2787 0, /* properties_destroyed */
2788 0, /* todo_flags_start */
2789 ( TODO_dump_symtab
), /* todo_flags_finish */
2792 class pass_ipa_inline
: public ipa_opt_pass_d
2795 pass_ipa_inline (gcc::context
*ctxt
)
2796 : ipa_opt_pass_d (pass_data_ipa_inline
, ctxt
,
2797 NULL
, /* generate_summary */
2798 NULL
, /* write_summary */
2799 NULL
, /* read_summary */
2800 NULL
, /* write_optimization_summary */
2801 NULL
, /* read_optimization_summary */
2802 NULL
, /* stmt_fixup */
2803 0, /* function_transform_todo_flags_start */
2804 inline_transform
, /* function_transform */
2805 NULL
) /* variable_transform */
2808 /* opt_pass methods: */
2809 virtual unsigned int execute (function
*) { return ipa_inline (); }
2811 }; // class pass_ipa_inline
2816 make_pass_ipa_inline (gcc::context
*ctxt
)
2818 return new pass_ipa_inline (ctxt
);