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"
122 typedef fibonacci_heap
<sreal
, cgraph_edge
> edge_heap_t
;
123 typedef fibonacci_node
<sreal
, cgraph_edge
> edge_heap_node_t
;
125 /* Statistics we collect about inlining algorithm. */
126 static int overall_size
;
127 static profile_count max_count
;
128 static profile_count spec_rem
;
130 /* Pre-computed constants 1/CGRAPH_FREQ_BASE and 1/100. */
131 static sreal cgraph_freq_base_rec
, percent_rec
;
133 /* Return false when inlining edge E would lead to violating
134 limits on function unit growth or stack usage growth.
136 The relative function body growth limit is present generally
137 to avoid problems with non-linear behavior of the compiler.
138 To allow inlining huge functions into tiny wrapper, the limit
139 is always based on the bigger of the two functions considered.
141 For stack growth limits we always base the growth in stack usage
142 of the callers. We want to prevent applications from segfaulting
143 on stack overflow when functions with huge stack frames gets
147 caller_growth_limits (struct cgraph_edge
*e
)
149 struct cgraph_node
*to
= e
->caller
;
150 struct cgraph_node
*what
= e
->callee
->ultimate_alias_target ();
153 HOST_WIDE_INT stack_size_limit
= 0, inlined_stack
;
154 ipa_fn_summary
*info
, *what_info
, *outer_info
= ipa_fn_summaries
->get (to
);
156 /* Look for function e->caller is inlined to. While doing
157 so work out the largest function body on the way. As
158 described above, we want to base our function growth
159 limits based on that. Not on the self size of the
160 outer function, not on the self size of inline code
161 we immediately inline to. This is the most relaxed
162 interpretation of the rule "do not grow large functions
163 too much in order to prevent compiler from exploding". */
166 info
= ipa_fn_summaries
->get (to
);
167 if (limit
< info
->self_size
)
168 limit
= info
->self_size
;
169 if (stack_size_limit
< info
->estimated_self_stack_size
)
170 stack_size_limit
= info
->estimated_self_stack_size
;
171 if (to
->global
.inlined_to
)
172 to
= to
->callers
->caller
;
177 what_info
= ipa_fn_summaries
->get (what
);
179 if (limit
< what_info
->self_size
)
180 limit
= what_info
->self_size
;
182 limit
+= limit
* PARAM_VALUE (PARAM_LARGE_FUNCTION_GROWTH
) / 100;
184 /* Check the size after inlining against the function limits. But allow
185 the function to shrink if it went over the limits by forced inlining. */
186 newsize
= estimate_size_after_inlining (to
, e
);
187 if (newsize
>= info
->size
188 && newsize
> PARAM_VALUE (PARAM_LARGE_FUNCTION_INSNS
)
191 e
->inline_failed
= CIF_LARGE_FUNCTION_GROWTH_LIMIT
;
195 if (!what_info
->estimated_stack_size
)
198 /* FIXME: Stack size limit often prevents inlining in Fortran programs
199 due to large i/o datastructures used by the Fortran front-end.
200 We ought to ignore this limit when we know that the edge is executed
201 on every invocation of the caller (i.e. its call statement dominates
202 exit block). We do not track this information, yet. */
203 stack_size_limit
+= ((gcov_type
)stack_size_limit
204 * PARAM_VALUE (PARAM_STACK_FRAME_GROWTH
) / 100);
206 inlined_stack
= (outer_info
->stack_frame_offset
207 + outer_info
->estimated_self_stack_size
208 + what_info
->estimated_stack_size
);
209 /* Check new stack consumption with stack consumption at the place
211 if (inlined_stack
> stack_size_limit
212 /* If function already has large stack usage from sibling
213 inline call, we can inline, too.
214 This bit overoptimistically assume that we are good at stack
216 && inlined_stack
> info
->estimated_stack_size
217 && inlined_stack
> PARAM_VALUE (PARAM_LARGE_STACK_FRAME
))
219 e
->inline_failed
= CIF_LARGE_STACK_FRAME_GROWTH_LIMIT
;
225 /* Dump info about why inlining has failed. */
228 report_inline_failed_reason (struct cgraph_edge
*e
)
232 fprintf (dump_file
, " not inlinable: %s -> %s, %s\n",
233 e
->caller
->dump_name (),
234 e
->callee
->dump_name (),
235 cgraph_inline_failed_string (e
->inline_failed
));
236 if ((e
->inline_failed
== CIF_TARGET_OPTION_MISMATCH
237 || e
->inline_failed
== CIF_OPTIMIZATION_MISMATCH
)
238 && e
->caller
->lto_file_data
239 && e
->callee
->ultimate_alias_target ()->lto_file_data
)
241 fprintf (dump_file
, " LTO objects: %s, %s\n",
242 e
->caller
->lto_file_data
->file_name
,
243 e
->callee
->ultimate_alias_target ()->lto_file_data
->file_name
);
245 if (e
->inline_failed
== CIF_TARGET_OPTION_MISMATCH
)
246 cl_target_option_print_diff
247 (dump_file
, 2, target_opts_for_fn (e
->caller
->decl
),
248 target_opts_for_fn (e
->callee
->ultimate_alias_target ()->decl
));
249 if (e
->inline_failed
== CIF_OPTIMIZATION_MISMATCH
)
250 cl_optimization_print_diff
251 (dump_file
, 2, opts_for_fn (e
->caller
->decl
),
252 opts_for_fn (e
->callee
->ultimate_alias_target ()->decl
));
256 /* Decide whether sanitizer-related attributes allow inlining. */
259 sanitize_attrs_match_for_inline_p (const_tree caller
, const_tree callee
)
261 if (!caller
|| !callee
)
264 return sanitize_flags_p (SANITIZE_ADDRESS
, caller
)
265 == sanitize_flags_p (SANITIZE_ADDRESS
, callee
);
268 /* Used for flags where it is safe to inline when caller's value is
269 grater than callee's. */
270 #define check_maybe_up(flag) \
271 (opts_for_fn (caller->decl)->x_##flag \
272 != opts_for_fn (callee->decl)->x_##flag \
274 || opts_for_fn (caller->decl)->x_##flag \
275 < opts_for_fn (callee->decl)->x_##flag))
276 /* Used for flags where it is safe to inline when caller's value is
277 smaller than callee's. */
278 #define check_maybe_down(flag) \
279 (opts_for_fn (caller->decl)->x_##flag \
280 != opts_for_fn (callee->decl)->x_##flag \
282 || opts_for_fn (caller->decl)->x_##flag \
283 > opts_for_fn (callee->decl)->x_##flag))
284 /* Used for flags where exact match is needed for correctness. */
285 #define check_match(flag) \
286 (opts_for_fn (caller->decl)->x_##flag \
287 != opts_for_fn (callee->decl)->x_##flag)
289 /* Decide if we can inline the edge and possibly update
290 inline_failed reason.
291 We check whether inlining is possible at all and whether
292 caller growth limits allow doing so.
294 if REPORT is true, output reason to the dump file.
296 if DISREGARD_LIMITS is true, ignore size limits.*/
299 can_inline_edge_p (struct cgraph_edge
*e
, bool report
,
300 bool disregard_limits
= false, bool early
= false)
302 gcc_checking_assert (e
->inline_failed
);
304 if (cgraph_inline_failed_type (e
->inline_failed
) == CIF_FINAL_ERROR
)
307 report_inline_failed_reason (e
);
311 bool inlinable
= true;
312 enum availability avail
;
313 cgraph_node
*caller
= e
->caller
->global
.inlined_to
314 ? e
->caller
->global
.inlined_to
: e
->caller
;
315 cgraph_node
*callee
= e
->callee
->ultimate_alias_target (&avail
, caller
);
316 tree caller_tree
= DECL_FUNCTION_SPECIFIC_OPTIMIZATION (caller
->decl
);
318 = callee
? DECL_FUNCTION_SPECIFIC_OPTIMIZATION (callee
->decl
) : NULL
;
320 if (!callee
->definition
)
322 e
->inline_failed
= CIF_BODY_NOT_AVAILABLE
;
325 if (!early
&& !opt_for_fn (callee
->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 if (edge
->count
> profile_count::zero ()
642 && caller
->count
> profile_count::zero ())
643 uninlined_call_time
*= (sreal
)edge
->count
.to_gcov_type ()
644 / caller
->count
.to_gcov_type ();
646 uninlined_call_time
*= cgraph_freq_base_rec
* edge
->frequency
;
648 uninlined_call_time
= uninlined_call_time
>> 11;
650 sreal caller_time
= ipa_fn_summaries
->get (caller
)->time
;
651 return uninlined_call_time
+ caller_time
;
654 /* Same as compute_uinlined_call_time but compute time when inlining
658 compute_inlined_call_time (struct cgraph_edge
*edge
,
661 cgraph_node
*caller
= (edge
->caller
->global
.inlined_to
662 ? edge
->caller
->global
.inlined_to
664 sreal caller_time
= ipa_fn_summaries
->get (caller
)->time
;
666 if (edge
->count
> profile_count::zero ()
667 && caller
->count
> profile_count::zero ())
668 time
*= (sreal
)edge
->count
.to_gcov_type () / caller
->count
.to_gcov_type ();
670 time
*= cgraph_freq_base_rec
* edge
->frequency
;
674 /* This calculation should match one in ipa-inline-analysis.c
675 (estimate_edge_size_and_time). */
676 time
-= (sreal
) edge
->frequency
677 * ipa_call_summaries
->get (edge
)->call_stmt_time
/ CGRAPH_FREQ_BASE
;
680 time
= ((sreal
) 1) >> 8;
681 gcc_checking_assert (time
>= 0);
685 /* Return true if the speedup for inlining E is bigger than
686 PARAM_MAX_INLINE_MIN_SPEEDUP. */
689 big_speedup_p (struct cgraph_edge
*e
)
692 sreal spec_time
= estimate_edge_time (e
, &unspec_time
);
693 sreal time
= compute_uninlined_call_time (e
, unspec_time
);
694 sreal inlined_time
= compute_inlined_call_time (e
, spec_time
);
696 if (time
- inlined_time
697 > (sreal
) (time
* PARAM_VALUE (PARAM_INLINE_MIN_SPEEDUP
))
703 /* Return true if we are interested in inlining small function.
704 When REPORT is true, report reason to dump file. */
707 want_inline_small_function_p (struct cgraph_edge
*e
, bool report
)
709 bool want_inline
= true;
710 struct cgraph_node
*callee
= e
->callee
->ultimate_alias_target ();
712 if (DECL_DISREGARD_INLINE_LIMITS (callee
->decl
))
714 else if (!DECL_DECLARED_INLINE_P (callee
->decl
)
715 && !opt_for_fn (e
->caller
->decl
, flag_inline_small_functions
))
717 e
->inline_failed
= CIF_FUNCTION_NOT_INLINE_CANDIDATE
;
720 /* Do fast and conservative check if the function can be good
721 inline candidate. At the moment we allow inline hints to
722 promote non-inline functions to inline and we increase
723 MAX_INLINE_INSNS_SINGLE 16-fold for inline functions. */
724 else if ((!DECL_DECLARED_INLINE_P (callee
->decl
)
725 && (!e
->count
.initialized_p () || !e
->maybe_hot_p ()))
726 && ipa_fn_summaries
->get (callee
)->min_size
727 - ipa_call_summaries
->get (e
)->call_stmt_size
728 > MAX (MAX_INLINE_INSNS_SINGLE
, MAX_INLINE_INSNS_AUTO
))
730 e
->inline_failed
= CIF_MAX_INLINE_INSNS_AUTO_LIMIT
;
733 else if ((DECL_DECLARED_INLINE_P (callee
->decl
)
734 || e
->count
> profile_count::zero ())
735 && ipa_fn_summaries
->get (callee
)->min_size
736 - ipa_call_summaries
->get (e
)->call_stmt_size
737 > 16 * MAX_INLINE_INSNS_SINGLE
)
739 e
->inline_failed
= (DECL_DECLARED_INLINE_P (callee
->decl
)
740 ? CIF_MAX_INLINE_INSNS_SINGLE_LIMIT
741 : CIF_MAX_INLINE_INSNS_AUTO_LIMIT
);
746 int growth
= estimate_edge_growth (e
);
747 ipa_hints hints
= estimate_edge_hints (e
);
748 bool big_speedup
= big_speedup_p (e
);
752 /* Apply MAX_INLINE_INSNS_SINGLE limit. Do not do so when
753 hints suggests that inlining given function is very profitable. */
754 else if (DECL_DECLARED_INLINE_P (callee
->decl
)
755 && growth
>= MAX_INLINE_INSNS_SINGLE
757 && !(hints
& (INLINE_HINT_indirect_call
758 | INLINE_HINT_known_hot
759 | INLINE_HINT_loop_iterations
760 | INLINE_HINT_array_index
761 | INLINE_HINT_loop_stride
)))
762 || growth
>= MAX_INLINE_INSNS_SINGLE
* 16))
764 e
->inline_failed
= CIF_MAX_INLINE_INSNS_SINGLE_LIMIT
;
767 else if (!DECL_DECLARED_INLINE_P (callee
->decl
)
768 && !opt_for_fn (e
->caller
->decl
, flag_inline_functions
))
770 /* growth_likely_positive is expensive, always test it last. */
771 if (growth
>= MAX_INLINE_INSNS_SINGLE
772 || growth_likely_positive (callee
, growth
))
774 e
->inline_failed
= CIF_NOT_DECLARED_INLINED
;
778 /* Apply MAX_INLINE_INSNS_AUTO limit for functions not declared inline
779 Upgrade it to MAX_INLINE_INSNS_SINGLE when hints suggests that
780 inlining given function is very profitable. */
781 else if (!DECL_DECLARED_INLINE_P (callee
->decl
)
783 && !(hints
& INLINE_HINT_known_hot
)
784 && growth
>= ((hints
& (INLINE_HINT_indirect_call
785 | INLINE_HINT_loop_iterations
786 | INLINE_HINT_array_index
787 | INLINE_HINT_loop_stride
))
788 ? MAX (MAX_INLINE_INSNS_AUTO
,
789 MAX_INLINE_INSNS_SINGLE
)
790 : MAX_INLINE_INSNS_AUTO
))
792 /* growth_likely_positive is expensive, always test it last. */
793 if (growth
>= MAX_INLINE_INSNS_SINGLE
794 || growth_likely_positive (callee
, growth
))
796 e
->inline_failed
= CIF_MAX_INLINE_INSNS_AUTO_LIMIT
;
800 /* If call is cold, do not inline when function body would grow. */
801 else if (!e
->maybe_hot_p ()
802 && (growth
>= MAX_INLINE_INSNS_SINGLE
803 || growth_likely_positive (callee
, growth
)))
805 e
->inline_failed
= CIF_UNLIKELY_CALL
;
809 if (!want_inline
&& report
)
810 report_inline_failed_reason (e
);
814 /* EDGE is self recursive edge.
815 We hand two cases - when function A is inlining into itself
816 or when function A is being inlined into another inliner copy of function
819 In first case OUTER_NODE points to the toplevel copy of A, while
820 in the second case OUTER_NODE points to the outermost copy of A in B.
822 In both cases we want to be extra selective since
823 inlining the call will just introduce new recursive calls to appear. */
826 want_inline_self_recursive_call_p (struct cgraph_edge
*edge
,
827 struct cgraph_node
*outer_node
,
831 char const *reason
= NULL
;
832 bool want_inline
= true;
833 int caller_freq
= CGRAPH_FREQ_BASE
;
834 int max_depth
= PARAM_VALUE (PARAM_MAX_INLINE_RECURSIVE_DEPTH_AUTO
);
836 if (DECL_DECLARED_INLINE_P (edge
->caller
->decl
))
837 max_depth
= PARAM_VALUE (PARAM_MAX_INLINE_RECURSIVE_DEPTH
);
839 if (!edge
->maybe_hot_p ())
841 reason
= "recursive call is cold";
844 else if (outer_node
->count
== profile_count::zero ())
846 reason
= "not executed in profile";
849 else if (depth
> max_depth
)
851 reason
= "--param max-inline-recursive-depth exceeded.";
855 if (outer_node
->global
.inlined_to
)
856 caller_freq
= outer_node
->callers
->frequency
;
860 reason
= "function is inlined and unlikely";
866 /* Inlining of self recursive function into copy of itself within other function
867 is transformation similar to loop peeling.
869 Peeling is profitable if we can inline enough copies to make probability
870 of actual call to the self recursive function very small. Be sure that
871 the probability of recursion is small.
873 We ensure that the frequency of recursing is at most 1 - (1/max_depth).
874 This way the expected number of recision is at most max_depth. */
877 int max_prob
= CGRAPH_FREQ_BASE
- ((CGRAPH_FREQ_BASE
+ max_depth
- 1)
880 for (i
= 1; i
< depth
; i
++)
881 max_prob
= max_prob
* max_prob
/ CGRAPH_FREQ_BASE
;
882 if (max_count
> profile_count::zero () && edge
->count
> profile_count::zero ()
883 && (edge
->count
.to_gcov_type () * CGRAPH_FREQ_BASE
884 / outer_node
->count
.to_gcov_type ()
887 reason
= "profile of recursive call is too large";
890 if (max_count
== profile_count::zero ()
891 && (edge
->frequency
* CGRAPH_FREQ_BASE
/ caller_freq
894 reason
= "frequency of recursive call is too large";
898 /* Recursive inlining, i.e. equivalent of unrolling, is profitable if recursion
899 depth is large. We reduce function call overhead and increase chances that
900 things fit in hardware return predictor.
902 Recursive inlining might however increase cost of stack frame setup
903 actually slowing down functions whose recursion tree is wide rather than
906 Deciding reliably on when to do recursive inlining without profile feedback
907 is tricky. For now we disable recursive inlining when probability of self
910 Recursive inlining of self recursive call within loop also results in large loop
911 depths that generally optimize badly. We may want to throttle down inlining
912 in those cases. In particular this seems to happen in one of libstdc++ rb tree
916 if (max_count
> profile_count::zero () && edge
->count
.initialized_p ()
917 && (edge
->count
.to_gcov_type () * 100
918 / outer_node
->count
.to_gcov_type ()
919 <= PARAM_VALUE (PARAM_MIN_INLINE_RECURSIVE_PROBABILITY
)))
921 reason
= "profile of recursive call is too small";
924 else if ((max_count
== profile_count::zero ()
925 || !edge
->count
.initialized_p ())
926 && (edge
->frequency
* 100 / caller_freq
927 <= PARAM_VALUE (PARAM_MIN_INLINE_RECURSIVE_PROBABILITY
)))
929 reason
= "frequency of recursive call is too small";
933 if (!want_inline
&& dump_file
)
934 fprintf (dump_file
, " not inlining recursively: %s\n", reason
);
938 /* Return true when NODE has uninlinable caller;
939 set HAS_HOT_CALL if it has hot call.
940 Worker for cgraph_for_node_and_aliases. */
943 check_callers (struct cgraph_node
*node
, void *has_hot_call
)
945 struct cgraph_edge
*e
;
946 for (e
= node
->callers
; e
; e
= e
->next_caller
)
948 if (!opt_for_fn (e
->caller
->decl
, flag_inline_functions_called_once
)
949 || !opt_for_fn (e
->caller
->decl
, optimize
))
951 if (!can_inline_edge_p (e
, true))
953 if (e
->recursive_p ())
955 if (!(*(bool *)has_hot_call
) && e
->maybe_hot_p ())
956 *(bool *)has_hot_call
= true;
961 /* If NODE has a caller, return true. */
964 has_caller_p (struct cgraph_node
*node
, void *data ATTRIBUTE_UNUSED
)
971 /* Decide if inlining NODE would reduce unit size by eliminating
972 the offline copy of function.
973 When COLD is true the cold calls are considered, too. */
976 want_inline_function_to_all_callers_p (struct cgraph_node
*node
, bool cold
)
978 bool has_hot_call
= false;
980 /* Aliases gets inlined along with the function they alias. */
983 /* Already inlined? */
984 if (node
->global
.inlined_to
)
986 /* Does it have callers? */
987 if (!node
->call_for_symbol_and_aliases (has_caller_p
, NULL
, true))
989 /* Inlining into all callers would increase size? */
990 if (estimate_growth (node
) > 0)
992 /* All inlines must be possible. */
993 if (node
->call_for_symbol_and_aliases (check_callers
, &has_hot_call
,
996 if (!cold
&& !has_hot_call
)
1001 /* A cost model driving the inlining heuristics in a way so the edges with
1002 smallest badness are inlined first. After each inlining is performed
1003 the costs of all caller edges of nodes affected are recomputed so the
1004 metrics may accurately depend on values such as number of inlinable callers
1005 of the function or function body size. */
1008 edge_badness (struct cgraph_edge
*edge
, bool dump
)
1012 sreal edge_time
, unspec_edge_time
;
1013 struct cgraph_node
*callee
= edge
->callee
->ultimate_alias_target ();
1014 struct ipa_fn_summary
*callee_info
= ipa_fn_summaries
->get (callee
);
1016 cgraph_node
*caller
= (edge
->caller
->global
.inlined_to
1017 ? edge
->caller
->global
.inlined_to
1020 growth
= estimate_edge_growth (edge
);
1021 edge_time
= estimate_edge_time (edge
, &unspec_edge_time
);
1022 hints
= estimate_edge_hints (edge
);
1023 gcc_checking_assert (edge_time
>= 0);
1024 /* Check that inlined time is better, but tolerate some roundoff issues. */
1025 gcc_checking_assert ((edge_time
- callee_info
->time
).to_int () <= 0);
1026 gcc_checking_assert (growth
<= callee_info
->size
);
1030 fprintf (dump_file
, " Badness calculation for %s -> %s\n",
1031 edge
->caller
->dump_name (),
1032 edge
->callee
->dump_name ());
1033 fprintf (dump_file
, " size growth %i, time %f unspec %f ",
1035 edge_time
.to_double (),
1036 unspec_edge_time
.to_double ());
1037 ipa_dump_hints (dump_file
, hints
);
1038 if (big_speedup_p (edge
))
1039 fprintf (dump_file
, " big_speedup");
1040 fprintf (dump_file
, "\n");
1043 /* Always prefer inlining saving code size. */
1046 badness
= (sreal
) (-SREAL_MIN_SIG
+ growth
) << (SREAL_MAX_EXP
/ 256);
1048 fprintf (dump_file
, " %f: Growth %d <= 0\n", badness
.to_double (),
1051 /* Inlining into EXTERNAL functions is not going to change anything unless
1052 they are themselves inlined. */
1053 else if (DECL_EXTERNAL (caller
->decl
))
1056 fprintf (dump_file
, " max: function is external\n");
1057 return sreal::max ();
1059 /* When profile is available. Compute badness as:
1061 time_saved * caller_count
1062 goodness = -------------------------------------------------
1063 growth_of_caller * overall_growth * combined_size
1065 badness = - goodness
1067 Again use negative value to make calls with profile appear hotter
1070 else if (opt_for_fn (caller
->decl
, flag_guess_branch_prob
)
1071 || caller
->count
> profile_count::zero ())
1073 sreal numerator
, denominator
;
1075 sreal inlined_time
= compute_inlined_call_time (edge
, edge_time
);
1077 numerator
= (compute_uninlined_call_time (edge
, unspec_edge_time
)
1080 numerator
= ((sreal
) 1 >> 8);
1081 if (caller
->count
> profile_count::zero ())
1082 numerator
*= caller
->count
.to_gcov_type ();
1083 else if (caller
->count
.initialized_p ())
1084 numerator
= numerator
>> 11;
1085 denominator
= growth
;
1087 overall_growth
= callee_info
->growth
;
1089 /* Look for inliner wrappers of the form:
1095 noninline_callee ();
1097 Withhout panilizing this case, we usually inline noninline_callee
1098 into the inline_caller because overall_growth is small preventing
1099 further inlining of inline_caller.
1101 Penalize only callgraph edges to functions with small overall
1104 if (growth
> overall_growth
1105 /* ... and having only one caller which is not inlined ... */
1106 && callee_info
->single_caller
1107 && !edge
->caller
->global
.inlined_to
1108 /* ... and edges executed only conditionally ... */
1109 && edge
->frequency
< CGRAPH_FREQ_BASE
1110 /* ... consider case where callee is not inline but caller is ... */
1111 && ((!DECL_DECLARED_INLINE_P (edge
->callee
->decl
)
1112 && DECL_DECLARED_INLINE_P (caller
->decl
))
1113 /* ... or when early optimizers decided to split and edge
1114 frequency still indicates splitting is a win ... */
1115 || (callee
->split_part
&& !caller
->split_part
1119 (PARAM_PARTIAL_INLINING_ENTRY_PROBABILITY
) / 100
1120 /* ... and do not overwrite user specified hints. */
1121 && (!DECL_DECLARED_INLINE_P (edge
->callee
->decl
)
1122 || DECL_DECLARED_INLINE_P (caller
->decl
)))))
1124 struct ipa_fn_summary
*caller_info
= ipa_fn_summaries
->get (caller
);
1125 int caller_growth
= caller_info
->growth
;
1127 /* Only apply the penalty when caller looks like inline candidate,
1128 and it is not called once and. */
1129 if (!caller_info
->single_caller
&& overall_growth
< caller_growth
1130 && caller_info
->inlinable
1131 && caller_info
->size
1132 < (DECL_DECLARED_INLINE_P (caller
->decl
)
1133 ? MAX_INLINE_INSNS_SINGLE
: MAX_INLINE_INSNS_AUTO
))
1137 " Wrapper penalty. Increasing growth %i to %i\n",
1138 overall_growth
, caller_growth
);
1139 overall_growth
= caller_growth
;
1142 if (overall_growth
> 0)
1144 /* Strongly preffer functions with few callers that can be inlined
1145 fully. The square root here leads to smaller binaries at average.
1146 Watch however for extreme cases and return to linear function
1147 when growth is large. */
1148 if (overall_growth
< 256)
1149 overall_growth
*= overall_growth
;
1151 overall_growth
+= 256 * 256 - 256;
1152 denominator
*= overall_growth
;
1154 denominator
*= inlined_time
;
1156 badness
= - numerator
/ denominator
;
1161 " %f: guessed profile. frequency %f, count %" PRId64
1162 " caller count %" PRId64
1163 " time w/o inlining %f, time with inlining %f"
1164 " overall growth %i (current) %i (original)"
1165 " %i (compensated)\n",
1166 badness
.to_double (),
1167 (double)edge
->frequency
/ CGRAPH_FREQ_BASE
,
1168 edge
->count
.initialized_p () ? edge
->count
.to_gcov_type () : -1,
1169 caller
->count
.initialized_p () ? caller
->count
.to_gcov_type () : -1,
1170 compute_uninlined_call_time (edge
,
1171 unspec_edge_time
).to_double (),
1172 compute_inlined_call_time (edge
, edge_time
).to_double (),
1173 estimate_growth (callee
),
1174 callee_info
->growth
, overall_growth
);
1177 /* When function local profile is not available or it does not give
1178 useful information (ie frequency is zero), base the cost on
1179 loop nest and overall size growth, so we optimize for overall number
1180 of functions fully inlined in program. */
1183 int nest
= MIN (ipa_call_summaries
->get (edge
)->loop_depth
, 8);
1186 /* Decrease badness if call is nested. */
1188 badness
= badness
>> nest
;
1190 badness
= badness
<< nest
;
1192 fprintf (dump_file
, " %f: no profile. nest %i\n",
1193 badness
.to_double (), nest
);
1195 gcc_checking_assert (badness
!= 0);
1197 if (edge
->recursive_p ())
1198 badness
= badness
.shift (badness
> 0 ? 4 : -4);
1199 if ((hints
& (INLINE_HINT_indirect_call
1200 | INLINE_HINT_loop_iterations
1201 | INLINE_HINT_array_index
1202 | INLINE_HINT_loop_stride
))
1203 || callee_info
->growth
<= 0)
1204 badness
= badness
.shift (badness
> 0 ? -2 : 2);
1205 if (hints
& (INLINE_HINT_same_scc
))
1206 badness
= badness
.shift (badness
> 0 ? 3 : -3);
1207 else if (hints
& (INLINE_HINT_in_scc
))
1208 badness
= badness
.shift (badness
> 0 ? 2 : -2);
1209 else if (hints
& (INLINE_HINT_cross_module
))
1210 badness
= badness
.shift (badness
> 0 ? 1 : -1);
1211 if (DECL_DISREGARD_INLINE_LIMITS (callee
->decl
))
1212 badness
= badness
.shift (badness
> 0 ? -4 : 4);
1213 else if ((hints
& INLINE_HINT_declared_inline
))
1214 badness
= badness
.shift (badness
> 0 ? -3 : 3);
1216 fprintf (dump_file
, " Adjusted by hints %f\n", badness
.to_double ());
1220 /* Recompute badness of EDGE and update its key in HEAP if needed. */
1222 update_edge_key (edge_heap_t
*heap
, struct cgraph_edge
*edge
)
1224 sreal badness
= edge_badness (edge
, false);
1227 edge_heap_node_t
*n
= (edge_heap_node_t
*) edge
->aux
;
1228 gcc_checking_assert (n
->get_data () == edge
);
1230 /* fibonacci_heap::replace_key does busy updating of the
1231 heap that is unnecesarily expensive.
1232 We do lazy increases: after extracting minimum if the key
1233 turns out to be out of date, it is re-inserted into heap
1234 with correct value. */
1235 if (badness
< n
->get_key ())
1237 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1240 " decreasing badness %s -> %s, %f to %f\n",
1241 edge
->caller
->dump_name (),
1242 edge
->callee
->dump_name (),
1243 n
->get_key ().to_double (),
1244 badness
.to_double ());
1246 heap
->decrease_key (n
, badness
);
1251 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1254 " enqueuing call %s -> %s, badness %f\n",
1255 edge
->caller
->dump_name (),
1256 edge
->callee
->dump_name (),
1257 badness
.to_double ());
1259 edge
->aux
= heap
->insert (badness
, edge
);
1264 /* NODE was inlined.
1265 All caller edges needs to be resetted because
1266 size estimates change. Similarly callees needs reset
1267 because better context may be known. */
1270 reset_edge_caches (struct cgraph_node
*node
)
1272 struct cgraph_edge
*edge
;
1273 struct cgraph_edge
*e
= node
->callees
;
1274 struct cgraph_node
*where
= node
;
1275 struct ipa_ref
*ref
;
1277 if (where
->global
.inlined_to
)
1278 where
= where
->global
.inlined_to
;
1280 for (edge
= where
->callers
; edge
; edge
= edge
->next_caller
)
1281 if (edge
->inline_failed
)
1282 reset_edge_growth_cache (edge
);
1284 FOR_EACH_ALIAS (where
, ref
)
1285 reset_edge_caches (dyn_cast
<cgraph_node
*> (ref
->referring
));
1291 if (!e
->inline_failed
&& e
->callee
->callees
)
1292 e
= e
->callee
->callees
;
1295 if (e
->inline_failed
)
1296 reset_edge_growth_cache (e
);
1303 if (e
->caller
== node
)
1305 e
= e
->caller
->callers
;
1307 while (!e
->next_callee
);
1313 /* Recompute HEAP nodes for each of caller of NODE.
1314 UPDATED_NODES track nodes we already visited, to avoid redundant work.
1315 When CHECK_INLINABLITY_FOR is set, re-check for specified edge that
1316 it is inlinable. Otherwise check all edges. */
1319 update_caller_keys (edge_heap_t
*heap
, struct cgraph_node
*node
,
1320 bitmap updated_nodes
,
1321 struct cgraph_edge
*check_inlinablity_for
)
1323 struct cgraph_edge
*edge
;
1324 struct ipa_ref
*ref
;
1326 if ((!node
->alias
&& !ipa_fn_summaries
->get (node
)->inlinable
)
1327 || node
->global
.inlined_to
)
1329 if (!bitmap_set_bit (updated_nodes
, node
->uid
))
1332 FOR_EACH_ALIAS (node
, ref
)
1334 struct cgraph_node
*alias
= dyn_cast
<cgraph_node
*> (ref
->referring
);
1335 update_caller_keys (heap
, alias
, updated_nodes
, check_inlinablity_for
);
1338 for (edge
= node
->callers
; edge
; edge
= edge
->next_caller
)
1339 if (edge
->inline_failed
)
1341 if (!check_inlinablity_for
1342 || check_inlinablity_for
== edge
)
1344 if (can_inline_edge_p (edge
, false)
1345 && want_inline_small_function_p (edge
, false))
1346 update_edge_key (heap
, edge
);
1349 report_inline_failed_reason (edge
);
1350 heap
->delete_node ((edge_heap_node_t
*) edge
->aux
);
1355 update_edge_key (heap
, edge
);
1359 /* Recompute HEAP nodes for each uninlined call in NODE.
1360 This is used when we know that edge badnesses are going only to increase
1361 (we introduced new call site) and thus all we need is to insert newly
1362 created edges into heap. */
1365 update_callee_keys (edge_heap_t
*heap
, struct cgraph_node
*node
,
1366 bitmap updated_nodes
)
1368 struct cgraph_edge
*e
= node
->callees
;
1373 if (!e
->inline_failed
&& e
->callee
->callees
)
1374 e
= e
->callee
->callees
;
1377 enum availability avail
;
1378 struct cgraph_node
*callee
;
1379 /* We do not reset callee growth cache here. Since we added a new call,
1380 growth chould have just increased and consequentely badness metric
1381 don't need updating. */
1382 if (e
->inline_failed
1383 && (callee
= e
->callee
->ultimate_alias_target (&avail
, e
->caller
))
1384 && ipa_fn_summaries
->get (callee
)->inlinable
1385 && avail
>= AVAIL_AVAILABLE
1386 && !bitmap_bit_p (updated_nodes
, callee
->uid
))
1388 if (can_inline_edge_p (e
, false)
1389 && want_inline_small_function_p (e
, false))
1390 update_edge_key (heap
, e
);
1393 report_inline_failed_reason (e
);
1394 heap
->delete_node ((edge_heap_node_t
*) e
->aux
);
1404 if (e
->caller
== node
)
1406 e
= e
->caller
->callers
;
1408 while (!e
->next_callee
);
1414 /* Enqueue all recursive calls from NODE into priority queue depending on
1415 how likely we want to recursively inline the call. */
1418 lookup_recursive_calls (struct cgraph_node
*node
, struct cgraph_node
*where
,
1421 struct cgraph_edge
*e
;
1422 enum availability avail
;
1424 for (e
= where
->callees
; e
; e
= e
->next_callee
)
1425 if (e
->callee
== node
1426 || (e
->callee
->ultimate_alias_target (&avail
, e
->caller
) == node
1427 && avail
> AVAIL_INTERPOSABLE
))
1429 /* When profile feedback is available, prioritize by expected number
1431 heap
->insert (!(max_count
> 0) || !e
->count
.initialized_p () ? -e
->frequency
1432 : -(e
->count
.to_gcov_type ()
1433 / ((max_count
.to_gcov_type () + (1<<24) - 1)
1437 for (e
= where
->callees
; e
; e
= e
->next_callee
)
1438 if (!e
->inline_failed
)
1439 lookup_recursive_calls (node
, e
->callee
, heap
);
1442 /* Decide on recursive inlining: in the case function has recursive calls,
1443 inline until body size reaches given argument. If any new indirect edges
1444 are discovered in the process, add them to *NEW_EDGES, unless NEW_EDGES
1448 recursive_inlining (struct cgraph_edge
*edge
,
1449 vec
<cgraph_edge
*> *new_edges
)
1451 int limit
= PARAM_VALUE (PARAM_MAX_INLINE_INSNS_RECURSIVE_AUTO
);
1452 edge_heap_t
heap (sreal::min ());
1453 struct cgraph_node
*node
;
1454 struct cgraph_edge
*e
;
1455 struct cgraph_node
*master_clone
= NULL
, *next
;
1459 node
= edge
->caller
;
1460 if (node
->global
.inlined_to
)
1461 node
= node
->global
.inlined_to
;
1463 if (DECL_DECLARED_INLINE_P (node
->decl
))
1464 limit
= PARAM_VALUE (PARAM_MAX_INLINE_INSNS_RECURSIVE
);
1466 /* Make sure that function is small enough to be considered for inlining. */
1467 if (estimate_size_after_inlining (node
, edge
) >= limit
)
1469 lookup_recursive_calls (node
, node
, &heap
);
1475 " Performing recursive inlining on %s\n",
1478 /* Do the inlining and update list of recursive call during process. */
1479 while (!heap
.empty ())
1481 struct cgraph_edge
*curr
= heap
.extract_min ();
1482 struct cgraph_node
*cnode
, *dest
= curr
->callee
;
1484 if (!can_inline_edge_p (curr
, true))
1487 /* MASTER_CLONE is produced in the case we already started modified
1488 the function. Be sure to redirect edge to the original body before
1489 estimating growths otherwise we will be seeing growths after inlining
1490 the already modified body. */
1493 curr
->redirect_callee (master_clone
);
1494 reset_edge_growth_cache (curr
);
1497 if (estimate_size_after_inlining (node
, curr
) > limit
)
1499 curr
->redirect_callee (dest
);
1500 reset_edge_growth_cache (curr
);
1505 for (cnode
= curr
->caller
;
1506 cnode
->global
.inlined_to
; cnode
= cnode
->callers
->caller
)
1508 == curr
->callee
->ultimate_alias_target ()->decl
)
1511 if (!want_inline_self_recursive_call_p (curr
, node
, false, depth
))
1513 curr
->redirect_callee (dest
);
1514 reset_edge_growth_cache (curr
);
1521 " Inlining call of depth %i", depth
);
1522 if (node
->count
> profile_count::zero ())
1524 fprintf (dump_file
, " called approx. %.2f times per call",
1525 (double)curr
->count
.to_gcov_type ()
1526 / node
->count
.to_gcov_type ());
1528 fprintf (dump_file
, "\n");
1532 /* We need original clone to copy around. */
1533 master_clone
= node
->create_clone (node
->decl
, node
->count
,
1534 CGRAPH_FREQ_BASE
, false, vNULL
,
1536 for (e
= master_clone
->callees
; e
; e
= e
->next_callee
)
1537 if (!e
->inline_failed
)
1538 clone_inlined_nodes (e
, true, false, NULL
, CGRAPH_FREQ_BASE
);
1539 curr
->redirect_callee (master_clone
);
1540 reset_edge_growth_cache (curr
);
1543 inline_call (curr
, false, new_edges
, &overall_size
, true);
1544 lookup_recursive_calls (node
, curr
->callee
, &heap
);
1548 if (!heap
.empty () && dump_file
)
1549 fprintf (dump_file
, " Recursive inlining growth limit met.\n");
1556 "\n Inlined %i times, "
1557 "body grown from size %i to %i, time %f to %f\n", n
,
1558 ipa_fn_summaries
->get (master_clone
)->size
,
1559 ipa_fn_summaries
->get (node
)->size
,
1560 ipa_fn_summaries
->get (master_clone
)->time
.to_double (),
1561 ipa_fn_summaries
->get (node
)->time
.to_double ());
1563 /* Remove master clone we used for inlining. We rely that clones inlined
1564 into master clone gets queued just before master clone so we don't
1566 for (node
= symtab
->first_function (); node
!= master_clone
;
1569 next
= symtab
->next_function (node
);
1570 if (node
->global
.inlined_to
== master_clone
)
1573 master_clone
->remove ();
1578 /* Given whole compilation unit estimate of INSNS, compute how large we can
1579 allow the unit to grow. */
1582 compute_max_insns (int insns
)
1584 int max_insns
= insns
;
1585 if (max_insns
< PARAM_VALUE (PARAM_LARGE_UNIT_INSNS
))
1586 max_insns
= PARAM_VALUE (PARAM_LARGE_UNIT_INSNS
);
1588 return ((int64_t) max_insns
1589 * (100 + PARAM_VALUE (PARAM_INLINE_UNIT_GROWTH
)) / 100);
1593 /* Compute badness of all edges in NEW_EDGES and add them to the HEAP. */
1596 add_new_edges_to_heap (edge_heap_t
*heap
, vec
<cgraph_edge
*> new_edges
)
1598 while (new_edges
.length () > 0)
1600 struct cgraph_edge
*edge
= new_edges
.pop ();
1602 gcc_assert (!edge
->aux
);
1603 if (edge
->inline_failed
1604 && can_inline_edge_p (edge
, true)
1605 && want_inline_small_function_p (edge
, true))
1606 edge
->aux
= heap
->insert (edge_badness (edge
, false), edge
);
1610 /* Remove EDGE from the fibheap. */
1613 heap_edge_removal_hook (struct cgraph_edge
*e
, void *data
)
1617 ((edge_heap_t
*)data
)->delete_node ((edge_heap_node_t
*)e
->aux
);
1622 /* Return true if speculation of edge E seems useful.
1623 If ANTICIPATE_INLINING is true, be conservative and hope that E
1627 speculation_useful_p (struct cgraph_edge
*e
, bool anticipate_inlining
)
1629 enum availability avail
;
1630 struct cgraph_node
*target
= e
->callee
->ultimate_alias_target (&avail
,
1632 struct cgraph_edge
*direct
, *indirect
;
1633 struct ipa_ref
*ref
;
1635 gcc_assert (e
->speculative
&& !e
->indirect_unknown_callee
);
1637 if (!e
->maybe_hot_p ())
1640 /* See if IP optimizations found something potentially useful about the
1641 function. For now we look only for CONST/PURE flags. Almost everything
1642 else we propagate is useless. */
1643 if (avail
>= AVAIL_AVAILABLE
)
1645 int ecf_flags
= flags_from_decl_or_type (target
->decl
);
1646 if (ecf_flags
& ECF_CONST
)
1648 e
->speculative_call_info (direct
, indirect
, ref
);
1649 if (!(indirect
->indirect_info
->ecf_flags
& ECF_CONST
))
1652 else if (ecf_flags
& ECF_PURE
)
1654 e
->speculative_call_info (direct
, indirect
, ref
);
1655 if (!(indirect
->indirect_info
->ecf_flags
& ECF_PURE
))
1659 /* If we did not managed to inline the function nor redirect
1660 to an ipa-cp clone (that are seen by having local flag set),
1661 it is probably pointless to inline it unless hardware is missing
1662 indirect call predictor. */
1663 if (!anticipate_inlining
&& e
->inline_failed
&& !target
->local
.local
)
1665 /* For overwritable targets there is not much to do. */
1666 if (e
->inline_failed
&& !can_inline_edge_p (e
, false, true))
1668 /* OK, speculation seems interesting. */
1672 /* We know that EDGE is not going to be inlined.
1673 See if we can remove speculation. */
1676 resolve_noninline_speculation (edge_heap_t
*edge_heap
, struct cgraph_edge
*edge
)
1678 if (edge
->speculative
&& !speculation_useful_p (edge
, false))
1680 struct cgraph_node
*node
= edge
->caller
;
1681 struct cgraph_node
*where
= node
->global
.inlined_to
1682 ? node
->global
.inlined_to
: node
;
1683 auto_bitmap updated_nodes
;
1685 spec_rem
+= edge
->count
;
1686 edge
->resolve_speculation ();
1687 reset_edge_caches (where
);
1688 ipa_update_overall_fn_summary (where
);
1689 update_caller_keys (edge_heap
, where
,
1690 updated_nodes
, NULL
);
1691 update_callee_keys (edge_heap
, where
,
1696 /* Return true if NODE should be accounted for overall size estimate.
1697 Skip all nodes optimized for size so we can measure the growth of hot
1698 part of program no matter of the padding. */
1701 inline_account_function_p (struct cgraph_node
*node
)
1703 return (!DECL_EXTERNAL (node
->decl
)
1704 && !opt_for_fn (node
->decl
, optimize_size
)
1705 && node
->frequency
!= NODE_FREQUENCY_UNLIKELY_EXECUTED
);
1708 /* Count number of callers of NODE and store it into DATA (that
1709 points to int. Worker for cgraph_for_node_and_aliases. */
1712 sum_callers (struct cgraph_node
*node
, void *data
)
1714 struct cgraph_edge
*e
;
1715 int *num_calls
= (int *)data
;
1717 for (e
= node
->callers
; e
; e
= e
->next_caller
)
1722 /* We use greedy algorithm for inlining of small functions:
1723 All inline candidates are put into prioritized heap ordered in
1726 The inlining of small functions is bounded by unit growth parameters. */
1729 inline_small_functions (void)
1731 struct cgraph_node
*node
;
1732 struct cgraph_edge
*edge
;
1733 edge_heap_t
edge_heap (sreal::min ());
1734 auto_bitmap updated_nodes
;
1735 int min_size
, max_size
;
1736 auto_vec
<cgraph_edge
*> new_indirect_edges
;
1737 int initial_size
= 0;
1738 struct cgraph_node
**order
= XCNEWVEC (cgraph_node
*, symtab
->cgraph_count
);
1739 struct cgraph_edge_hook_list
*edge_removal_hook_holder
;
1740 new_indirect_edges
.create (8);
1742 edge_removal_hook_holder
1743 = symtab
->add_edge_removal_hook (&heap_edge_removal_hook
, &edge_heap
);
1745 /* Compute overall unit size and other global parameters used by badness
1748 max_count
= profile_count::uninitialized ();
1749 ipa_reduced_postorder (order
, true, true, NULL
);
1752 FOR_EACH_DEFINED_FUNCTION (node
)
1753 if (!node
->global
.inlined_to
)
1755 if (!node
->alias
&& node
->analyzed
1756 && (node
->has_gimple_body_p () || node
->thunk
.thunk_p
)
1757 && opt_for_fn (node
->decl
, optimize
))
1759 struct ipa_fn_summary
*info
= ipa_fn_summaries
->get (node
);
1760 struct ipa_dfs_info
*dfs
= (struct ipa_dfs_info
*) node
->aux
;
1762 /* Do not account external functions, they will be optimized out
1763 if not inlined. Also only count the non-cold portion of program. */
1764 if (inline_account_function_p (node
))
1765 initial_size
+= info
->size
;
1766 info
->growth
= estimate_growth (node
);
1769 node
->call_for_symbol_and_aliases (sum_callers
, &num_calls
,
1772 info
->single_caller
= true;
1773 if (dfs
&& dfs
->next_cycle
)
1775 struct cgraph_node
*n2
;
1776 int id
= dfs
->scc_no
+ 1;
1778 n2
= ((struct ipa_dfs_info
*) node
->aux
)->next_cycle
)
1779 if (opt_for_fn (n2
->decl
, optimize
))
1781 struct ipa_fn_summary
*info2
= ipa_fn_summaries
->get (n2
);
1789 for (edge
= node
->callers
; edge
; edge
= edge
->next_caller
)
1790 if (!(max_count
>= edge
->count
))
1791 max_count
= edge
->count
;
1793 ipa_free_postorder_info ();
1794 initialize_growth_caches ();
1798 "\nDeciding on inlining of small functions. Starting with size %i.\n",
1801 overall_size
= initial_size
;
1802 max_size
= compute_max_insns (overall_size
);
1803 min_size
= overall_size
;
1805 /* Populate the heap with all edges we might inline. */
1807 FOR_EACH_DEFINED_FUNCTION (node
)
1809 bool update
= false;
1810 struct cgraph_edge
*next
= NULL
;
1811 bool has_speculative
= false;
1813 if (!opt_for_fn (node
->decl
, optimize
))
1817 fprintf (dump_file
, "Enqueueing calls in %s.\n", node
->dump_name ());
1819 for (edge
= node
->callees
; edge
; edge
= next
)
1821 next
= edge
->next_callee
;
1822 if (edge
->inline_failed
1824 && can_inline_edge_p (edge
, true)
1825 && want_inline_small_function_p (edge
, true)
1826 && edge
->inline_failed
)
1828 gcc_assert (!edge
->aux
);
1829 update_edge_key (&edge_heap
, edge
);
1831 if (edge
->speculative
)
1832 has_speculative
= true;
1834 if (has_speculative
)
1835 for (edge
= node
->callees
; edge
; edge
= next
)
1836 if (edge
->speculative
&& !speculation_useful_p (edge
,
1839 edge
->resolve_speculation ();
1844 struct cgraph_node
*where
= node
->global
.inlined_to
1845 ? node
->global
.inlined_to
: node
;
1846 ipa_update_overall_fn_summary (where
);
1847 reset_edge_caches (where
);
1848 update_caller_keys (&edge_heap
, where
,
1849 updated_nodes
, NULL
);
1850 update_callee_keys (&edge_heap
, where
,
1852 bitmap_clear (updated_nodes
);
1856 gcc_assert (in_lto_p
1858 || (profile_info
&& flag_branch_probabilities
));
1860 while (!edge_heap
.empty ())
1862 int old_size
= overall_size
;
1863 struct cgraph_node
*where
, *callee
;
1864 sreal badness
= edge_heap
.min_key ();
1865 sreal current_badness
;
1868 edge
= edge_heap
.extract_min ();
1869 gcc_assert (edge
->aux
);
1871 if (!edge
->inline_failed
|| !edge
->callee
->analyzed
)
1875 /* Be sure that caches are maintained consistent. */
1876 sreal cached_badness
= edge_badness (edge
, false);
1878 int old_size_est
= estimate_edge_size (edge
);
1879 sreal old_time_est
= estimate_edge_time (edge
);
1880 int old_hints_est
= estimate_edge_hints (edge
);
1882 reset_edge_growth_cache (edge
);
1883 gcc_assert (old_size_est
== estimate_edge_size (edge
));
1884 gcc_assert (old_time_est
== estimate_edge_time (edge
));
1887 gcc_assert (old_hints_est == estimate_edge_hints (edge));
1889 fails with profile feedback because some hints depends on
1890 maybe_hot_edge_p predicate and because callee gets inlined to other
1891 calls, the edge may become cold.
1892 This ought to be fixed by computing relative probabilities
1893 for given invocation but that will be better done once whole
1894 code is converted to sreals. Disable for now and revert to "wrong"
1895 value so enable/disable checking paths agree. */
1896 edge_growth_cache
[edge
->uid
].hints
= old_hints_est
+ 1;
1898 /* When updating the edge costs, we only decrease badness in the keys.
1899 Increases of badness are handled lazilly; when we see key with out
1900 of date value on it, we re-insert it now. */
1901 current_badness
= edge_badness (edge
, false);
1902 gcc_assert (cached_badness
== current_badness
);
1903 gcc_assert (current_badness
>= badness
);
1905 current_badness
= edge_badness (edge
, false);
1907 if (current_badness
!= badness
)
1909 if (edge_heap
.min () && current_badness
> edge_heap
.min_key ())
1911 edge
->aux
= edge_heap
.insert (current_badness
, edge
);
1915 badness
= current_badness
;
1918 if (!can_inline_edge_p (edge
, true))
1920 resolve_noninline_speculation (&edge_heap
, edge
);
1924 callee
= edge
->callee
->ultimate_alias_target ();
1925 growth
= estimate_edge_growth (edge
);
1929 "\nConsidering %s with %i size\n",
1930 callee
->dump_name (),
1931 ipa_fn_summaries
->get (callee
)->size
);
1933 " to be inlined into %s in %s:%i\n"
1934 " Estimated badness is %f, frequency %.2f.\n",
1935 edge
->caller
->dump_name (),
1937 && (LOCATION_LOCUS (gimple_location ((const gimple
*)
1939 > BUILTINS_LOCATION
)
1940 ? gimple_filename ((const gimple
*) edge
->call_stmt
)
1943 ? gimple_lineno ((const gimple
*) edge
->call_stmt
)
1945 badness
.to_double (),
1946 edge
->frequency
/ (double)CGRAPH_FREQ_BASE
);
1947 if (edge
->count
.initialized_p ())
1949 fprintf (dump_file
, " Called ");
1950 edge
->count
.dump (dump_file
);
1951 fprintf (dump_file
, "times\n");
1953 if (dump_flags
& TDF_DETAILS
)
1954 edge_badness (edge
, true);
1957 if (overall_size
+ growth
> max_size
1958 && !DECL_DISREGARD_INLINE_LIMITS (callee
->decl
))
1960 edge
->inline_failed
= CIF_INLINE_UNIT_GROWTH_LIMIT
;
1961 report_inline_failed_reason (edge
);
1962 resolve_noninline_speculation (&edge_heap
, edge
);
1966 if (!want_inline_small_function_p (edge
, true))
1968 resolve_noninline_speculation (&edge_heap
, edge
);
1972 /* Heuristics for inlining small functions work poorly for
1973 recursive calls where we do effects similar to loop unrolling.
1974 When inlining such edge seems profitable, leave decision on
1975 specific inliner. */
1976 if (edge
->recursive_p ())
1978 where
= edge
->caller
;
1979 if (where
->global
.inlined_to
)
1980 where
= where
->global
.inlined_to
;
1981 if (!recursive_inlining (edge
,
1982 opt_for_fn (edge
->caller
->decl
,
1983 flag_indirect_inlining
)
1984 ? &new_indirect_edges
: NULL
))
1986 edge
->inline_failed
= CIF_RECURSIVE_INLINING
;
1987 resolve_noninline_speculation (&edge_heap
, edge
);
1990 reset_edge_caches (where
);
1991 /* Recursive inliner inlines all recursive calls of the function
1992 at once. Consequently we need to update all callee keys. */
1993 if (opt_for_fn (edge
->caller
->decl
, flag_indirect_inlining
))
1994 add_new_edges_to_heap (&edge_heap
, new_indirect_edges
);
1995 update_callee_keys (&edge_heap
, where
, updated_nodes
);
1996 bitmap_clear (updated_nodes
);
2000 struct cgraph_node
*outer_node
= NULL
;
2003 /* Consider the case where self recursive function A is inlined
2004 into B. This is desired optimization in some cases, since it
2005 leads to effect similar of loop peeling and we might completely
2006 optimize out the recursive call. However we must be extra
2009 where
= edge
->caller
;
2010 while (where
->global
.inlined_to
)
2012 if (where
->decl
== callee
->decl
)
2013 outer_node
= where
, depth
++;
2014 where
= where
->callers
->caller
;
2017 && !want_inline_self_recursive_call_p (edge
, outer_node
,
2021 = (DECL_DISREGARD_INLINE_LIMITS (edge
->callee
->decl
)
2022 ? CIF_RECURSIVE_INLINING
: CIF_UNSPECIFIED
);
2023 resolve_noninline_speculation (&edge_heap
, edge
);
2026 else if (depth
&& dump_file
)
2027 fprintf (dump_file
, " Peeling recursion with depth %i\n", depth
);
2029 gcc_checking_assert (!callee
->global
.inlined_to
);
2030 inline_call (edge
, true, &new_indirect_edges
, &overall_size
, true);
2031 add_new_edges_to_heap (&edge_heap
, new_indirect_edges
);
2033 reset_edge_caches (edge
->callee
);
2035 update_callee_keys (&edge_heap
, where
, updated_nodes
);
2037 where
= edge
->caller
;
2038 if (where
->global
.inlined_to
)
2039 where
= where
->global
.inlined_to
;
2041 /* Our profitability metric can depend on local properties
2042 such as number of inlinable calls and size of the function body.
2043 After inlining these properties might change for the function we
2044 inlined into (since it's body size changed) and for the functions
2045 called by function we inlined (since number of it inlinable callers
2047 update_caller_keys (&edge_heap
, where
, updated_nodes
, NULL
);
2048 /* Offline copy count has possibly changed, recompute if profile is
2050 if (max_count
> profile_count::zero ())
2052 struct cgraph_node
*n
= cgraph_node::get (edge
->callee
->decl
);
2053 if (n
!= edge
->callee
&& n
->analyzed
)
2054 update_callee_keys (&edge_heap
, n
, updated_nodes
);
2056 bitmap_clear (updated_nodes
);
2061 " Inlined %s into %s which now has time %f and size %i, "
2062 "net change of %+i.\n",
2063 xstrdup_for_dump (edge
->callee
->name ()),
2064 xstrdup_for_dump (edge
->caller
->name ()),
2065 ipa_fn_summaries
->get (edge
->caller
)->time
.to_double (),
2066 ipa_fn_summaries
->get (edge
->caller
)->size
,
2067 overall_size
- old_size
);
2069 if (min_size
> overall_size
)
2071 min_size
= overall_size
;
2072 max_size
= compute_max_insns (min_size
);
2075 fprintf (dump_file
, "New minimal size reached: %i\n", min_size
);
2079 free_growth_caches ();
2082 "Unit growth for small function inlining: %i->%i (%i%%)\n",
2083 initial_size
, overall_size
,
2084 initial_size
? overall_size
* 100 / (initial_size
) - 100: 0);
2085 symtab
->remove_edge_removal_hook (edge_removal_hook_holder
);
2088 /* Flatten NODE. Performed both during early inlining and
2089 at IPA inlining time. */
2092 flatten_function (struct cgraph_node
*node
, bool early
)
2094 struct cgraph_edge
*e
;
2096 /* We shouldn't be called recursively when we are being processed. */
2097 gcc_assert (node
->aux
== NULL
);
2099 node
->aux
= (void *) node
;
2101 for (e
= node
->callees
; e
; e
= e
->next_callee
)
2103 struct cgraph_node
*orig_callee
;
2104 struct cgraph_node
*callee
= e
->callee
->ultimate_alias_target ();
2106 /* We've hit cycle? It is time to give up. */
2111 "Not inlining %s into %s to avoid cycle.\n",
2112 xstrdup_for_dump (callee
->name ()),
2113 xstrdup_for_dump (e
->caller
->name ()));
2114 e
->inline_failed
= CIF_RECURSIVE_INLINING
;
2118 /* When the edge is already inlined, we just need to recurse into
2119 it in order to fully flatten the leaves. */
2120 if (!e
->inline_failed
)
2122 flatten_function (callee
, early
);
2126 /* Flatten attribute needs to be processed during late inlining. For
2127 extra code quality we however do flattening during early optimization,
2130 ? !can_inline_edge_p (e
, true)
2131 : !can_early_inline_edge_p (e
))
2134 if (e
->recursive_p ())
2137 fprintf (dump_file
, "Not inlining: recursive call.\n");
2141 if (gimple_in_ssa_p (DECL_STRUCT_FUNCTION (node
->decl
))
2142 != gimple_in_ssa_p (DECL_STRUCT_FUNCTION (callee
->decl
)))
2145 fprintf (dump_file
, "Not inlining: SSA form does not match.\n");
2149 /* Inline the edge and flatten the inline clone. Avoid
2150 recursing through the original node if the node was cloned. */
2152 fprintf (dump_file
, " Inlining %s into %s.\n",
2153 xstrdup_for_dump (callee
->name ()),
2154 xstrdup_for_dump (e
->caller
->name ()));
2155 orig_callee
= callee
;
2156 inline_call (e
, true, NULL
, NULL
, false);
2157 if (e
->callee
!= orig_callee
)
2158 orig_callee
->aux
= (void *) node
;
2159 flatten_function (e
->callee
, early
);
2160 if (e
->callee
!= orig_callee
)
2161 orig_callee
->aux
= NULL
;
2165 if (!node
->global
.inlined_to
)
2166 ipa_update_overall_fn_summary (node
);
2169 /* Inline NODE to all callers. Worker for cgraph_for_node_and_aliases.
2170 DATA points to number of calls originally found so we avoid infinite
2174 inline_to_all_callers_1 (struct cgraph_node
*node
, void *data
,
2175 hash_set
<cgraph_node
*> *callers
)
2177 int *num_calls
= (int *)data
;
2178 bool callee_removed
= false;
2180 while (node
->callers
&& !node
->global
.inlined_to
)
2182 struct cgraph_node
*caller
= node
->callers
->caller
;
2184 if (!can_inline_edge_p (node
->callers
, true)
2185 || node
->callers
->recursive_p ())
2188 fprintf (dump_file
, "Uninlinable call found; giving up.\n");
2196 "\nInlining %s size %i.\n",
2198 ipa_fn_summaries
->get (node
)->size
);
2200 " Called once from %s %i insns.\n",
2201 node
->callers
->caller
->name (),
2202 ipa_fn_summaries
->get (node
->callers
->caller
)->size
);
2205 /* Remember which callers we inlined to, delaying updating the
2207 callers
->add (node
->callers
->caller
);
2208 inline_call (node
->callers
, true, NULL
, NULL
, false, &callee_removed
);
2211 " Inlined into %s which now has %i size\n",
2213 ipa_fn_summaries
->get (caller
)->size
);
2214 if (!(*num_calls
)--)
2217 fprintf (dump_file
, "New calls found; giving up.\n");
2218 return callee_removed
;
2226 /* Wrapper around inline_to_all_callers_1 doing delayed overall summary
2230 inline_to_all_callers (struct cgraph_node
*node
, void *data
)
2232 hash_set
<cgraph_node
*> callers
;
2233 bool res
= inline_to_all_callers_1 (node
, data
, &callers
);
2234 /* Perform the delayed update of the overall summary of all callers
2235 processed. This avoids quadratic behavior in the cases where
2236 we have a lot of calls to the same function. */
2237 for (hash_set
<cgraph_node
*>::iterator i
= callers
.begin ();
2238 i
!= callers
.end (); ++i
)
2239 ipa_update_overall_fn_summary (*i
);
2243 /* Output overall time estimate. */
2245 dump_overall_stats (void)
2247 sreal sum_weighted
= 0, sum
= 0;
2248 struct cgraph_node
*node
;
2250 FOR_EACH_DEFINED_FUNCTION (node
)
2251 if (!node
->global
.inlined_to
2254 sreal time
= ipa_fn_summaries
->get (node
)->time
;
2256 if (node
->count
.initialized_p ())
2257 sum_weighted
+= time
* node
->count
.to_gcov_type ();
2259 fprintf (dump_file
, "Overall time estimate: "
2260 "%f weighted by profile: "
2261 "%f\n", sum
.to_double (), sum_weighted
.to_double ());
2264 /* Output some useful stats about inlining. */
2267 dump_inline_stats (void)
2269 int64_t inlined_cnt
= 0, inlined_indir_cnt
= 0;
2270 int64_t inlined_virt_cnt
= 0, inlined_virt_indir_cnt
= 0;
2271 int64_t noninlined_cnt
= 0, noninlined_indir_cnt
= 0;
2272 int64_t noninlined_virt_cnt
= 0, noninlined_virt_indir_cnt
= 0;
2273 int64_t inlined_speculative
= 0, inlined_speculative_ply
= 0;
2274 int64_t indirect_poly_cnt
= 0, indirect_cnt
= 0;
2275 int64_t reason
[CIF_N_REASONS
][3];
2277 struct cgraph_node
*node
;
2279 memset (reason
, 0, sizeof (reason
));
2280 FOR_EACH_DEFINED_FUNCTION (node
)
2282 struct cgraph_edge
*e
;
2283 for (e
= node
->callees
; e
; e
= e
->next_callee
)
2285 if (e
->inline_failed
)
2287 if (e
->count
.initialized_p ())
2288 reason
[(int) e
->inline_failed
][0] += e
->count
.to_gcov_type ();
2289 reason
[(int) e
->inline_failed
][1] += e
->frequency
;
2290 reason
[(int) e
->inline_failed
][2] ++;
2291 if (DECL_VIRTUAL_P (e
->callee
->decl
)
2292 && e
->count
.initialized_p ())
2294 if (e
->indirect_inlining_edge
)
2295 noninlined_virt_indir_cnt
+= e
->count
.to_gcov_type ();
2297 noninlined_virt_cnt
+= e
->count
.to_gcov_type ();
2299 else if (e
->count
.initialized_p ())
2301 if (e
->indirect_inlining_edge
)
2302 noninlined_indir_cnt
+= e
->count
.to_gcov_type ();
2304 noninlined_cnt
+= e
->count
.to_gcov_type ();
2307 else if (e
->count
.initialized_p ())
2311 if (DECL_VIRTUAL_P (e
->callee
->decl
))
2312 inlined_speculative_ply
+= e
->count
.to_gcov_type ();
2314 inlined_speculative
+= e
->count
.to_gcov_type ();
2316 else if (DECL_VIRTUAL_P (e
->callee
->decl
))
2318 if (e
->indirect_inlining_edge
)
2319 inlined_virt_indir_cnt
+= e
->count
.to_gcov_type ();
2321 inlined_virt_cnt
+= e
->count
.to_gcov_type ();
2325 if (e
->indirect_inlining_edge
)
2326 inlined_indir_cnt
+= e
->count
.to_gcov_type ();
2328 inlined_cnt
+= e
->count
.to_gcov_type ();
2332 for (e
= node
->indirect_calls
; e
; e
= e
->next_callee
)
2333 if (e
->indirect_info
->polymorphic
2334 & e
->count
.initialized_p ())
2335 indirect_poly_cnt
+= e
->count
.to_gcov_type ();
2336 else if (e
->count
.initialized_p ())
2337 indirect_cnt
+= e
->count
.to_gcov_type ();
2339 if (max_count
.initialized_p ())
2342 "Inlined %" PRId64
" + speculative "
2343 "%" PRId64
" + speculative polymorphic "
2344 "%" PRId64
" + previously indirect "
2345 "%" PRId64
" + virtual "
2346 "%" PRId64
" + virtual and previously indirect "
2347 "%" PRId64
"\n" "Not inlined "
2348 "%" PRId64
" + previously indirect "
2349 "%" PRId64
" + virtual "
2350 "%" PRId64
" + virtual and previously indirect "
2351 "%" PRId64
" + stil indirect "
2352 "%" PRId64
" + still indirect polymorphic "
2353 "%" PRId64
"\n", inlined_cnt
,
2354 inlined_speculative
, inlined_speculative_ply
,
2355 inlined_indir_cnt
, inlined_virt_cnt
, inlined_virt_indir_cnt
,
2356 noninlined_cnt
, noninlined_indir_cnt
, noninlined_virt_cnt
,
2357 noninlined_virt_indir_cnt
, indirect_cnt
, indirect_poly_cnt
);
2358 fprintf (dump_file
, "Removed speculations ");
2359 spec_rem
.dump (dump_file
);
2360 fprintf (dump_file
, "\n");
2362 dump_overall_stats ();
2363 fprintf (dump_file
, "\nWhy inlining failed?\n");
2364 for (i
= 0; i
< CIF_N_REASONS
; i
++)
2366 fprintf (dump_file
, "%-50s: %8i calls, %8i freq, %" PRId64
" count\n",
2367 cgraph_inline_failed_string ((cgraph_inline_failed_t
) i
),
2368 (int) reason
[i
][2], (int) reason
[i
][1], reason
[i
][0]);
2371 /* Decide on the inlining. We do so in the topological order to avoid
2372 expenses on updating data structures. */
2377 struct cgraph_node
*node
;
2379 struct cgraph_node
**order
;
2382 bool remove_functions
= false;
2384 cgraph_freq_base_rec
= (sreal
) 1 / (sreal
) CGRAPH_FREQ_BASE
;
2385 percent_rec
= (sreal
) 1 / (sreal
) 100;
2387 order
= XCNEWVEC (struct cgraph_node
*, symtab
->cgraph_count
);
2390 ipa_dump_fn_summaries (dump_file
);
2392 nnodes
= ipa_reverse_postorder (order
);
2394 FOR_EACH_FUNCTION (node
)
2398 /* Recompute the default reasons for inlining because they may have
2399 changed during merging. */
2402 for (cgraph_edge
*e
= node
->callees
; e
; e
= e
->next_callee
)
2404 gcc_assert (e
->inline_failed
);
2405 initialize_inline_failed (e
);
2407 for (cgraph_edge
*e
= node
->indirect_calls
; e
; e
= e
->next_callee
)
2408 initialize_inline_failed (e
);
2413 fprintf (dump_file
, "\nFlattening functions:\n");
2415 /* In the first pass handle functions to be flattened. Do this with
2416 a priority so none of our later choices will make this impossible. */
2417 for (i
= nnodes
- 1; i
>= 0; i
--)
2421 /* Handle nodes to be flattened.
2422 Ideally when processing callees we stop inlining at the
2423 entry of cycles, possibly cloning that entry point and
2424 try to flatten itself turning it into a self-recursive
2426 if (lookup_attribute ("flatten",
2427 DECL_ATTRIBUTES (node
->decl
)) != NULL
)
2431 "Flattening %s\n", node
->name ());
2432 flatten_function (node
, false);
2436 dump_overall_stats ();
2438 inline_small_functions ();
2440 gcc_assert (symtab
->state
== IPA_SSA
);
2441 symtab
->state
= IPA_SSA_AFTER_INLINING
;
2442 /* Do first after-inlining removal. We want to remove all "stale" extern
2443 inline functions and virtual functions so we really know what is called
2445 symtab
->remove_unreachable_nodes (dump_file
);
2448 /* Inline functions with a property that after inlining into all callers the
2449 code size will shrink because the out-of-line copy is eliminated.
2450 We do this regardless on the callee size as long as function growth limits
2454 "\nDeciding on functions to be inlined into all callers and "
2455 "removing useless speculations:\n");
2457 /* Inlining one function called once has good chance of preventing
2458 inlining other function into the same callee. Ideally we should
2459 work in priority order, but probably inlining hot functions first
2460 is good cut without the extra pain of maintaining the queue.
2462 ??? this is not really fitting the bill perfectly: inlining function
2463 into callee often leads to better optimization of callee due to
2464 increased context for optimization.
2465 For example if main() function calls a function that outputs help
2466 and then function that does the main optmization, we should inline
2467 the second with priority even if both calls are cold by themselves.
2469 We probably want to implement new predicate replacing our use of
2470 maybe_hot_edge interpreted as maybe_hot_edge || callee is known
2472 for (cold
= 0; cold
<= 1; cold
++)
2474 FOR_EACH_DEFINED_FUNCTION (node
)
2476 struct cgraph_edge
*edge
, *next
;
2479 if (!opt_for_fn (node
->decl
, optimize
)
2480 || !opt_for_fn (node
->decl
, flag_inline_functions_called_once
))
2483 for (edge
= node
->callees
; edge
; edge
= next
)
2485 next
= edge
->next_callee
;
2486 if (edge
->speculative
&& !speculation_useful_p (edge
, false))
2488 edge
->resolve_speculation ();
2489 spec_rem
+= edge
->count
;
2491 remove_functions
= true;
2496 struct cgraph_node
*where
= node
->global
.inlined_to
2497 ? node
->global
.inlined_to
: node
;
2498 reset_edge_caches (where
);
2499 ipa_update_overall_fn_summary (where
);
2501 if (want_inline_function_to_all_callers_p (node
, cold
))
2504 node
->call_for_symbol_and_aliases (sum_callers
, &num_calls
,
2506 while (node
->call_for_symbol_and_aliases
2507 (inline_to_all_callers
, &num_calls
, true))
2509 remove_functions
= true;
2514 /* Free ipa-prop structures if they are no longer needed. */
2515 ipa_free_all_structures_after_iinln ();
2520 "\nInlined %i calls, eliminated %i functions\n\n",
2521 ncalls_inlined
, nfunctions_inlined
);
2522 dump_inline_stats ();
2526 ipa_dump_fn_summaries (dump_file
);
2527 /* In WPA we use inline summaries for partitioning process. */
2529 ipa_free_fn_summary ();
2530 return remove_functions
? TODO_remove_functions
: 0;
2533 /* Inline always-inline function calls in NODE. */
2536 inline_always_inline_functions (struct cgraph_node
*node
)
2538 struct cgraph_edge
*e
;
2539 bool inlined
= false;
2541 for (e
= node
->callees
; e
; e
= e
->next_callee
)
2543 struct cgraph_node
*callee
= e
->callee
->ultimate_alias_target ();
2544 if (!DECL_DISREGARD_INLINE_LIMITS (callee
->decl
))
2547 if (e
->recursive_p ())
2550 fprintf (dump_file
, " Not inlining recursive call to %s.\n",
2551 e
->callee
->name ());
2552 e
->inline_failed
= CIF_RECURSIVE_INLINING
;
2556 if (!can_early_inline_edge_p (e
))
2558 /* Set inlined to true if the callee is marked "always_inline" but
2559 is not inlinable. This will allow flagging an error later in
2560 expand_call_inline in tree-inline.c. */
2561 if (lookup_attribute ("always_inline",
2562 DECL_ATTRIBUTES (callee
->decl
)) != NULL
)
2568 fprintf (dump_file
, " Inlining %s into %s (always_inline).\n",
2569 xstrdup_for_dump (e
->callee
->name ()),
2570 xstrdup_for_dump (e
->caller
->name ()));
2571 inline_call (e
, true, NULL
, NULL
, false);
2575 ipa_update_overall_fn_summary (node
);
2580 /* Decide on the inlining. We do so in the topological order to avoid
2581 expenses on updating data structures. */
2584 early_inline_small_functions (struct cgraph_node
*node
)
2586 struct cgraph_edge
*e
;
2587 bool inlined
= false;
2589 for (e
= node
->callees
; e
; e
= e
->next_callee
)
2591 struct cgraph_node
*callee
= e
->callee
->ultimate_alias_target ();
2592 if (!ipa_fn_summaries
->get (callee
)->inlinable
2593 || !e
->inline_failed
)
2596 /* Do not consider functions not declared inline. */
2597 if (!DECL_DECLARED_INLINE_P (callee
->decl
)
2598 && !opt_for_fn (node
->decl
, flag_inline_small_functions
)
2599 && !opt_for_fn (node
->decl
, flag_inline_functions
))
2603 fprintf (dump_file
, "Considering inline candidate %s.\n",
2606 if (!can_early_inline_edge_p (e
))
2609 if (e
->recursive_p ())
2612 fprintf (dump_file
, " Not inlining: recursive call.\n");
2616 if (!want_early_inline_function_p (e
))
2620 fprintf (dump_file
, " Inlining %s into %s.\n",
2621 xstrdup_for_dump (callee
->name ()),
2622 xstrdup_for_dump (e
->caller
->name ()));
2623 inline_call (e
, true, NULL
, NULL
, false);
2628 ipa_update_overall_fn_summary (node
);
2634 early_inliner (function
*fun
)
2636 struct cgraph_node
*node
= cgraph_node::get (current_function_decl
);
2637 struct cgraph_edge
*edge
;
2638 unsigned int todo
= 0;
2640 bool inlined
= false;
2645 /* Do nothing if datastructures for ipa-inliner are already computed. This
2646 happens when some pass decides to construct new function and
2647 cgraph_add_new_function calls lowering passes and early optimization on
2648 it. This may confuse ourself when early inliner decide to inline call to
2649 function clone, because function clones don't have parameter list in
2650 ipa-prop matching their signature. */
2651 if (ipa_node_params_sum
)
2656 node
->remove_all_references ();
2658 /* Rebuild this reference because it dosn't depend on
2659 function's body and it's required to pass cgraph_node
2661 if (node
->instrumented_version
2662 && !node
->instrumentation_clone
)
2663 node
->create_reference (node
->instrumented_version
, IPA_REF_CHKP
, NULL
);
2665 /* Even when not optimizing or not inlining inline always-inline
2667 inlined
= inline_always_inline_functions (node
);
2671 || !flag_early_inlining
2672 /* Never inline regular functions into always-inline functions
2673 during incremental inlining. This sucks as functions calling
2674 always inline functions will get less optimized, but at the
2675 same time inlining of functions calling always inline
2676 function into an always inline function might introduce
2677 cycles of edges to be always inlined in the callgraph.
2679 We might want to be smarter and just avoid this type of inlining. */
2680 || (DECL_DISREGARD_INLINE_LIMITS (node
->decl
)
2681 && lookup_attribute ("always_inline",
2682 DECL_ATTRIBUTES (node
->decl
))))
2684 else if (lookup_attribute ("flatten",
2685 DECL_ATTRIBUTES (node
->decl
)) != NULL
)
2687 /* When the function is marked to be flattened, recursively inline
2691 "Flattening %s\n", node
->name ());
2692 flatten_function (node
, true);
2697 /* If some always_inline functions was inlined, apply the changes.
2698 This way we will not account always inline into growth limits and
2699 moreover we will inline calls from always inlines that we skipped
2700 previously because of conditional above. */
2703 timevar_push (TV_INTEGRATION
);
2704 todo
|= optimize_inline_calls (current_function_decl
);
2705 /* optimize_inline_calls call above might have introduced new
2706 statements that don't have inline parameters computed. */
2707 for (edge
= node
->callees
; edge
; edge
= edge
->next_callee
)
2709 struct ipa_call_summary
*es
= ipa_call_summaries
->get (edge
);
2711 = estimate_num_insns (edge
->call_stmt
, &eni_size_weights
);
2713 = estimate_num_insns (edge
->call_stmt
, &eni_time_weights
);
2715 ipa_update_overall_fn_summary (node
);
2717 timevar_pop (TV_INTEGRATION
);
2719 /* We iterate incremental inlining to get trivial cases of indirect
2721 while (iterations
< PARAM_VALUE (PARAM_EARLY_INLINER_MAX_ITERATIONS
)
2722 && early_inline_small_functions (node
))
2724 timevar_push (TV_INTEGRATION
);
2725 todo
|= optimize_inline_calls (current_function_decl
);
2727 /* Technically we ought to recompute inline parameters so the new
2728 iteration of early inliner works as expected. We however have
2729 values approximately right and thus we only need to update edge
2730 info that might be cleared out for newly discovered edges. */
2731 for (edge
= node
->callees
; edge
; edge
= edge
->next_callee
)
2733 /* We have no summary for new bound store calls yet. */
2734 struct ipa_call_summary
*es
= ipa_call_summaries
->get (edge
);
2736 = estimate_num_insns (edge
->call_stmt
, &eni_size_weights
);
2738 = estimate_num_insns (edge
->call_stmt
, &eni_time_weights
);
2740 if (edge
->callee
->decl
2741 && !gimple_check_call_matching_types (
2742 edge
->call_stmt
, edge
->callee
->decl
, false))
2744 edge
->inline_failed
= CIF_MISMATCHED_ARGUMENTS
;
2745 edge
->call_stmt_cannot_inline_p
= true;
2748 if (iterations
< PARAM_VALUE (PARAM_EARLY_INLINER_MAX_ITERATIONS
) - 1)
2749 ipa_update_overall_fn_summary (node
);
2750 timevar_pop (TV_INTEGRATION
);
2755 fprintf (dump_file
, "Iterations: %i\n", iterations
);
2760 timevar_push (TV_INTEGRATION
);
2761 todo
|= optimize_inline_calls (current_function_decl
);
2762 timevar_pop (TV_INTEGRATION
);
2765 fun
->always_inline_functions_inlined
= true;
2770 /* Do inlining of small functions. Doing so early helps profiling and other
2771 passes to be somewhat more effective and avoids some code duplication in
2772 later real inlining pass for testcases with very many function calls. */
2776 const pass_data pass_data_early_inline
=
2778 GIMPLE_PASS
, /* type */
2779 "einline", /* name */
2780 OPTGROUP_INLINE
, /* optinfo_flags */
2781 TV_EARLY_INLINING
, /* tv_id */
2782 PROP_ssa
, /* properties_required */
2783 0, /* properties_provided */
2784 0, /* properties_destroyed */
2785 0, /* todo_flags_start */
2786 0, /* todo_flags_finish */
2789 class pass_early_inline
: public gimple_opt_pass
2792 pass_early_inline (gcc::context
*ctxt
)
2793 : gimple_opt_pass (pass_data_early_inline
, ctxt
)
2796 /* opt_pass methods: */
2797 virtual unsigned int execute (function
*);
2799 }; // class pass_early_inline
2802 pass_early_inline::execute (function
*fun
)
2804 return early_inliner (fun
);
2810 make_pass_early_inline (gcc::context
*ctxt
)
2812 return new pass_early_inline (ctxt
);
2817 const pass_data pass_data_ipa_inline
=
2819 IPA_PASS
, /* type */
2820 "inline", /* name */
2821 OPTGROUP_INLINE
, /* optinfo_flags */
2822 TV_IPA_INLINING
, /* tv_id */
2823 0, /* properties_required */
2824 0, /* properties_provided */
2825 0, /* properties_destroyed */
2826 0, /* todo_flags_start */
2827 ( TODO_dump_symtab
), /* todo_flags_finish */
2830 class pass_ipa_inline
: public ipa_opt_pass_d
2833 pass_ipa_inline (gcc::context
*ctxt
)
2834 : ipa_opt_pass_d (pass_data_ipa_inline
, ctxt
,
2835 NULL
, /* generate_summary */
2836 NULL
, /* write_summary */
2837 NULL
, /* read_summary */
2838 NULL
, /* write_optimization_summary */
2839 NULL
, /* read_optimization_summary */
2840 NULL
, /* stmt_fixup */
2841 0, /* function_transform_todo_flags_start */
2842 inline_transform
, /* function_transform */
2843 NULL
) /* variable_transform */
2846 /* opt_pass methods: */
2847 virtual unsigned int execute (function
*) { return ipa_inline (); }
2849 }; // class pass_ipa_inline
2854 make_pass_ipa_inline (gcc::context
*ctxt
)
2856 return new pass_ipa_inline (ctxt
);