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 /* Pre-computed constant 1/100. */
133 static sreal percent_rec
;
135 /* Return false when inlining edge E would lead to violating
136 limits on function unit growth or stack usage growth.
138 The relative function body growth limit is present generally
139 to avoid problems with non-linear behavior of the compiler.
140 To allow inlining huge functions into tiny wrapper, the limit
141 is always based on the bigger of the two functions considered.
143 For stack growth limits we always base the growth in stack usage
144 of the callers. We want to prevent applications from segfaulting
145 on stack overflow when functions with huge stack frames gets
149 caller_growth_limits (struct cgraph_edge
*e
)
151 struct cgraph_node
*to
= e
->caller
;
152 struct cgraph_node
*what
= e
->callee
->ultimate_alias_target ();
155 HOST_WIDE_INT stack_size_limit
= 0, inlined_stack
;
156 ipa_fn_summary
*info
, *what_info
, *outer_info
= ipa_fn_summaries
->get (to
);
158 /* Look for function e->caller is inlined to. While doing
159 so work out the largest function body on the way. As
160 described above, we want to base our function growth
161 limits based on that. Not on the self size of the
162 outer function, not on the self size of inline code
163 we immediately inline to. This is the most relaxed
164 interpretation of the rule "do not grow large functions
165 too much in order to prevent compiler from exploding". */
168 info
= ipa_fn_summaries
->get (to
);
169 if (limit
< info
->self_size
)
170 limit
= info
->self_size
;
171 if (stack_size_limit
< info
->estimated_self_stack_size
)
172 stack_size_limit
= info
->estimated_self_stack_size
;
173 if (to
->global
.inlined_to
)
174 to
= to
->callers
->caller
;
179 what_info
= ipa_fn_summaries
->get (what
);
181 if (limit
< what_info
->self_size
)
182 limit
= what_info
->self_size
;
184 limit
+= limit
* PARAM_VALUE (PARAM_LARGE_FUNCTION_GROWTH
) / 100;
186 /* Check the size after inlining against the function limits. But allow
187 the function to shrink if it went over the limits by forced inlining. */
188 newsize
= estimate_size_after_inlining (to
, e
);
189 if (newsize
>= info
->size
190 && newsize
> PARAM_VALUE (PARAM_LARGE_FUNCTION_INSNS
)
193 e
->inline_failed
= CIF_LARGE_FUNCTION_GROWTH_LIMIT
;
197 if (!what_info
->estimated_stack_size
)
200 /* FIXME: Stack size limit often prevents inlining in Fortran programs
201 due to large i/o datastructures used by the Fortran front-end.
202 We ought to ignore this limit when we know that the edge is executed
203 on every invocation of the caller (i.e. its call statement dominates
204 exit block). We do not track this information, yet. */
205 stack_size_limit
+= ((gcov_type
)stack_size_limit
206 * PARAM_VALUE (PARAM_STACK_FRAME_GROWTH
) / 100);
208 inlined_stack
= (outer_info
->stack_frame_offset
209 + outer_info
->estimated_self_stack_size
210 + what_info
->estimated_stack_size
);
211 /* Check new stack consumption with stack consumption at the place
213 if (inlined_stack
> stack_size_limit
214 /* If function already has large stack usage from sibling
215 inline call, we can inline, too.
216 This bit overoptimistically assume that we are good at stack
218 && inlined_stack
> info
->estimated_stack_size
219 && inlined_stack
> PARAM_VALUE (PARAM_LARGE_STACK_FRAME
))
221 e
->inline_failed
= CIF_LARGE_STACK_FRAME_GROWTH_LIMIT
;
227 /* Dump info about why inlining has failed. */
230 report_inline_failed_reason (struct cgraph_edge
*e
)
234 fprintf (dump_file
, " not inlinable: %s -> %s, %s\n",
235 e
->caller
->dump_name (),
236 e
->callee
->dump_name (),
237 cgraph_inline_failed_string (e
->inline_failed
));
238 if ((e
->inline_failed
== CIF_TARGET_OPTION_MISMATCH
239 || e
->inline_failed
== CIF_OPTIMIZATION_MISMATCH
)
240 && e
->caller
->lto_file_data
241 && e
->callee
->ultimate_alias_target ()->lto_file_data
)
243 fprintf (dump_file
, " LTO objects: %s, %s\n",
244 e
->caller
->lto_file_data
->file_name
,
245 e
->callee
->ultimate_alias_target ()->lto_file_data
->file_name
);
247 if (e
->inline_failed
== CIF_TARGET_OPTION_MISMATCH
)
248 cl_target_option_print_diff
249 (dump_file
, 2, target_opts_for_fn (e
->caller
->decl
),
250 target_opts_for_fn (e
->callee
->ultimate_alias_target ()->decl
));
251 if (e
->inline_failed
== CIF_OPTIMIZATION_MISMATCH
)
252 cl_optimization_print_diff
253 (dump_file
, 2, opts_for_fn (e
->caller
->decl
),
254 opts_for_fn (e
->callee
->ultimate_alias_target ()->decl
));
258 /* Decide whether sanitizer-related attributes allow inlining. */
261 sanitize_attrs_match_for_inline_p (const_tree caller
, const_tree callee
)
263 if (!caller
|| !callee
)
266 return sanitize_flags_p (SANITIZE_ADDRESS
, caller
)
267 == sanitize_flags_p (SANITIZE_ADDRESS
, callee
);
270 /* Used for flags where it is safe to inline when caller's value is
271 grater than callee's. */
272 #define check_maybe_up(flag) \
273 (opts_for_fn (caller->decl)->x_##flag \
274 != opts_for_fn (callee->decl)->x_##flag \
276 || opts_for_fn (caller->decl)->x_##flag \
277 < opts_for_fn (callee->decl)->x_##flag))
278 /* Used for flags where it is safe to inline when caller's value is
279 smaller than callee's. */
280 #define check_maybe_down(flag) \
281 (opts_for_fn (caller->decl)->x_##flag \
282 != opts_for_fn (callee->decl)->x_##flag \
284 || opts_for_fn (caller->decl)->x_##flag \
285 > opts_for_fn (callee->decl)->x_##flag))
286 /* Used for flags where exact match is needed for correctness. */
287 #define check_match(flag) \
288 (opts_for_fn (caller->decl)->x_##flag \
289 != opts_for_fn (callee->decl)->x_##flag)
291 /* Decide if we can inline the edge and possibly update
292 inline_failed reason.
293 We check whether inlining is possible at all and whether
294 caller growth limits allow doing so.
296 if REPORT is true, output reason to the dump file.
298 if DISREGARD_LIMITS is true, ignore size limits.*/
301 can_inline_edge_p (struct cgraph_edge
*e
, bool report
,
302 bool disregard_limits
= false, bool early
= false)
304 gcc_checking_assert (e
->inline_failed
);
306 if (cgraph_inline_failed_type (e
->inline_failed
) == CIF_FINAL_ERROR
)
309 report_inline_failed_reason (e
);
313 bool inlinable
= true;
314 enum availability avail
;
315 cgraph_node
*caller
= e
->caller
->global
.inlined_to
316 ? e
->caller
->global
.inlined_to
: e
->caller
;
317 cgraph_node
*callee
= e
->callee
->ultimate_alias_target (&avail
, caller
);
318 tree caller_tree
= DECL_FUNCTION_SPECIFIC_OPTIMIZATION (caller
->decl
);
320 = callee
? DECL_FUNCTION_SPECIFIC_OPTIMIZATION (callee
->decl
) : NULL
;
322 if (!callee
->definition
)
324 e
->inline_failed
= CIF_BODY_NOT_AVAILABLE
;
327 if (!early
&& !opt_for_fn (callee
->decl
, optimize
))
329 e
->inline_failed
= CIF_FUNCTION_NOT_OPTIMIZED
;
332 else if (callee
->calls_comdat_local
)
334 e
->inline_failed
= CIF_USES_COMDAT_LOCAL
;
337 else if (avail
<= AVAIL_INTERPOSABLE
)
339 e
->inline_failed
= CIF_OVERWRITABLE
;
342 /* All edges with call_stmt_cannot_inline_p should have inline_failed
343 initialized to one of FINAL_ERROR reasons. */
344 else if (e
->call_stmt_cannot_inline_p
)
346 /* Don't inline if the functions have different EH personalities. */
347 else if (DECL_FUNCTION_PERSONALITY (caller
->decl
)
348 && DECL_FUNCTION_PERSONALITY (callee
->decl
)
349 && (DECL_FUNCTION_PERSONALITY (caller
->decl
)
350 != DECL_FUNCTION_PERSONALITY (callee
->decl
)))
352 e
->inline_failed
= CIF_EH_PERSONALITY
;
355 /* TM pure functions should not be inlined into non-TM_pure
357 else if (is_tm_pure (callee
->decl
) && !is_tm_pure (caller
->decl
))
359 e
->inline_failed
= CIF_UNSPECIFIED
;
362 /* Check compatibility of target optimization options. */
363 else if (!targetm
.target_option
.can_inline_p (caller
->decl
,
366 e
->inline_failed
= CIF_TARGET_OPTION_MISMATCH
;
369 else if (!ipa_fn_summaries
->get (callee
)->inlinable
)
371 e
->inline_failed
= CIF_FUNCTION_NOT_INLINABLE
;
374 /* Don't inline a function with mismatched sanitization attributes. */
375 else if (!sanitize_attrs_match_for_inline_p (caller
->decl
, callee
->decl
))
377 e
->inline_failed
= CIF_ATTRIBUTE_MISMATCH
;
380 /* Check if caller growth allows the inlining. */
381 else if (!DECL_DISREGARD_INLINE_LIMITS (callee
->decl
)
383 && !lookup_attribute ("flatten",
384 DECL_ATTRIBUTES (caller
->decl
))
385 && !caller_growth_limits (e
))
387 /* Don't inline a function with a higher optimization level than the
388 caller. FIXME: this is really just tip of iceberg of handling
389 optimization attribute. */
390 else if (caller_tree
!= callee_tree
)
393 (DECL_DISREGARD_INLINE_LIMITS (callee
->decl
)
394 && lookup_attribute ("always_inline",
395 DECL_ATTRIBUTES (callee
->decl
)));
396 ipa_fn_summary
*caller_info
= ipa_fn_summaries
->get (caller
);
397 ipa_fn_summary
*callee_info
= ipa_fn_summaries
->get (callee
);
399 /* Until GCC 4.9 we did not check the semantics alterning flags
400 bellow and inline across optimization boundry.
401 Enabling checks bellow breaks several packages by refusing
402 to inline library always_inline functions. See PR65873.
403 Disable the check for early inlining for now until better solution
405 if (always_inline
&& early
)
407 /* There are some options that change IL semantics which means
408 we cannot inline in these cases for correctness reason.
409 Not even for always_inline declared functions. */
410 else if (check_match (flag_wrapv
)
411 || check_match (flag_trapv
)
412 || check_match (flag_pcc_struct_return
)
413 /* When caller or callee does FP math, be sure FP codegen flags
415 || ((caller_info
->fp_expressions
&& callee_info
->fp_expressions
)
416 && (check_maybe_up (flag_rounding_math
)
417 || check_maybe_up (flag_trapping_math
)
418 || check_maybe_down (flag_unsafe_math_optimizations
)
419 || check_maybe_down (flag_finite_math_only
)
420 || check_maybe_up (flag_signaling_nans
)
421 || check_maybe_down (flag_cx_limited_range
)
422 || check_maybe_up (flag_signed_zeros
)
423 || check_maybe_down (flag_associative_math
)
424 || check_maybe_down (flag_reciprocal_math
)
425 || check_maybe_down (flag_fp_int_builtin_inexact
)
426 /* Strictly speaking only when the callee contains function
427 calls that may end up setting errno. */
428 || check_maybe_up (flag_errno_math
)))
429 /* We do not want to make code compiled with exceptions to be
430 brought into a non-EH function unless we know that the callee
432 This is tracked by DECL_FUNCTION_PERSONALITY. */
433 || (check_maybe_up (flag_non_call_exceptions
)
434 && DECL_FUNCTION_PERSONALITY (callee
->decl
))
435 || (check_maybe_up (flag_exceptions
)
436 && DECL_FUNCTION_PERSONALITY (callee
->decl
))
437 /* When devirtualization is diabled for callee, it is not safe
438 to inline it as we possibly mangled the type info.
439 Allow early inlining of always inlines. */
440 || (!early
&& check_maybe_down (flag_devirtualize
)))
442 e
->inline_failed
= CIF_OPTIMIZATION_MISMATCH
;
445 /* gcc.dg/pr43564.c. Apply user-forced inline even at -O0. */
446 else if (always_inline
)
448 /* When user added an attribute to the callee honor it. */
449 else if (lookup_attribute ("optimize", DECL_ATTRIBUTES (callee
->decl
))
450 && opts_for_fn (caller
->decl
) != opts_for_fn (callee
->decl
))
452 e
->inline_failed
= CIF_OPTIMIZATION_MISMATCH
;
455 /* If explicit optimize attribute are not used, the mismatch is caused
456 by different command line options used to build different units.
457 Do not care about COMDAT functions - those are intended to be
458 optimized with the optimization flags of module they are used in.
459 Also do not care about mixing up size/speed optimization when
460 DECL_DISREGARD_INLINE_LIMITS is set. */
461 else if ((callee
->merged_comdat
462 && !lookup_attribute ("optimize",
463 DECL_ATTRIBUTES (caller
->decl
)))
464 || DECL_DISREGARD_INLINE_LIMITS (callee
->decl
))
466 /* If mismatch is caused by merging two LTO units with different
467 optimizationflags we want to be bit nicer. However never inline
468 if one of functions is not optimized at all. */
469 else if (!opt_for_fn (callee
->decl
, optimize
)
470 || !opt_for_fn (caller
->decl
, optimize
))
472 e
->inline_failed
= CIF_OPTIMIZATION_MISMATCH
;
475 /* If callee is optimized for size and caller is not, allow inlining if
476 code shrinks or we are in MAX_INLINE_INSNS_SINGLE limit and callee
477 is inline (and thus likely an unified comdat). This will allow caller
479 else if (opt_for_fn (callee
->decl
, optimize_size
)
480 > opt_for_fn (caller
->decl
, optimize_size
))
482 int growth
= estimate_edge_growth (e
);
484 && (!DECL_DECLARED_INLINE_P (callee
->decl
)
485 && growth
>= MAX (MAX_INLINE_INSNS_SINGLE
,
486 MAX_INLINE_INSNS_AUTO
)))
488 e
->inline_failed
= CIF_OPTIMIZATION_MISMATCH
;
492 /* If callee is more aggressively optimized for performance than caller,
493 we generally want to inline only cheap (runtime wise) functions. */
494 else if (opt_for_fn (callee
->decl
, optimize_size
)
495 < opt_for_fn (caller
->decl
, optimize_size
)
496 || (opt_for_fn (callee
->decl
, optimize
)
497 > opt_for_fn (caller
->decl
, optimize
)))
499 if (estimate_edge_time (e
)
500 >= 20 + ipa_call_summaries
->get (e
)->call_stmt_time
)
502 e
->inline_failed
= CIF_OPTIMIZATION_MISMATCH
;
509 if (!inlinable
&& report
)
510 report_inline_failed_reason (e
);
515 /* Return true if the edge E is inlinable during early inlining. */
518 can_early_inline_edge_p (struct cgraph_edge
*e
)
520 struct cgraph_node
*callee
= e
->callee
->ultimate_alias_target ();
521 /* Early inliner might get called at WPA stage when IPA pass adds new
522 function. In this case we can not really do any of early inlining
523 because function bodies are missing. */
524 if (cgraph_inline_failed_type (e
->inline_failed
) == CIF_FINAL_ERROR
)
526 if (!gimple_has_body_p (callee
->decl
))
528 e
->inline_failed
= CIF_BODY_NOT_AVAILABLE
;
531 /* In early inliner some of callees may not be in SSA form yet
532 (i.e. the callgraph is cyclic and we did not process
533 the callee by early inliner, yet). We don't have CIF code for this
534 case; later we will re-do the decision in the real inliner. */
535 if (!gimple_in_ssa_p (DECL_STRUCT_FUNCTION (e
->caller
->decl
))
536 || !gimple_in_ssa_p (DECL_STRUCT_FUNCTION (callee
->decl
)))
539 fprintf (dump_file
, " edge not inlinable: not in SSA form\n");
542 if (!can_inline_edge_p (e
, true, false, true))
548 /* Return number of calls in N. Ignore cheap builtins. */
551 num_calls (struct cgraph_node
*n
)
553 struct cgraph_edge
*e
;
556 for (e
= n
->callees
; e
; e
= e
->next_callee
)
557 if (!is_inexpensive_builtin (e
->callee
->decl
))
563 /* Return true if we are interested in inlining small function. */
566 want_early_inline_function_p (struct cgraph_edge
*e
)
568 bool want_inline
= true;
569 struct cgraph_node
*callee
= e
->callee
->ultimate_alias_target ();
571 if (DECL_DISREGARD_INLINE_LIMITS (callee
->decl
))
573 /* For AutoFDO, we need to make sure that before profile summary, all
574 hot paths' IR look exactly the same as profiled binary. As a result,
575 in einliner, we will disregard size limit and inline those callsites
577 * inlined in the profiled binary, and
578 * the cloned callee has enough samples to be considered "hot". */
579 else if (flag_auto_profile
&& afdo_callsite_hot_enough_for_early_inline (e
))
581 else if (!DECL_DECLARED_INLINE_P (callee
->decl
)
582 && !opt_for_fn (e
->caller
->decl
, flag_inline_small_functions
))
584 e
->inline_failed
= CIF_FUNCTION_NOT_INLINE_CANDIDATE
;
585 report_inline_failed_reason (e
);
590 int growth
= estimate_edge_growth (e
);
595 else if (!e
->maybe_hot_p ()
599 fprintf (dump_file
, " will not early inline: %s->%s, "
600 "call is cold and code would grow by %i\n",
601 e
->caller
->dump_name (),
602 callee
->dump_name (),
606 else if (growth
> PARAM_VALUE (PARAM_EARLY_INLINING_INSNS
))
609 fprintf (dump_file
, " will not early inline: %s->%s, "
610 "growth %i exceeds --param early-inlining-insns\n",
611 e
->caller
->dump_name (),
612 callee
->dump_name (),
616 else if ((n
= num_calls (callee
)) != 0
617 && growth
* (n
+ 1) > PARAM_VALUE (PARAM_EARLY_INLINING_INSNS
))
620 fprintf (dump_file
, " will not early inline: %s->%s, "
621 "growth %i exceeds --param early-inlining-insns "
622 "divided by number of calls\n",
623 e
->caller
->dump_name (),
624 callee
->dump_name (),
632 /* Compute time of the edge->caller + edge->callee execution when inlining
636 compute_uninlined_call_time (struct cgraph_edge
*edge
,
637 sreal uninlined_call_time
)
639 cgraph_node
*caller
= (edge
->caller
->global
.inlined_to
640 ? edge
->caller
->global
.inlined_to
643 sreal freq
= edge
->sreal_frequency ();
645 uninlined_call_time
*= freq
;
647 uninlined_call_time
= uninlined_call_time
>> 11;
649 sreal caller_time
= ipa_fn_summaries
->get (caller
)->time
;
650 return uninlined_call_time
+ caller_time
;
653 /* Same as compute_uinlined_call_time but compute time when inlining
657 compute_inlined_call_time (struct cgraph_edge
*edge
,
660 cgraph_node
*caller
= (edge
->caller
->global
.inlined_to
661 ? edge
->caller
->global
.inlined_to
663 sreal caller_time
= ipa_fn_summaries
->get (caller
)->time
;
665 sreal freq
= edge
->sreal_frequency ();
671 /* This calculation should match one in ipa-inline-analysis.c
672 (estimate_edge_size_and_time). */
673 time
-= (sreal
)ipa_call_summaries
->get (edge
)->call_stmt_time
* freq
;
676 time
= ((sreal
) 1) >> 8;
677 gcc_checking_assert (time
>= 0);
681 /* Return true if the speedup for inlining E is bigger than
682 PARAM_MAX_INLINE_MIN_SPEEDUP. */
685 big_speedup_p (struct cgraph_edge
*e
)
688 sreal spec_time
= estimate_edge_time (e
, &unspec_time
);
689 sreal time
= compute_uninlined_call_time (e
, unspec_time
);
690 sreal inlined_time
= compute_inlined_call_time (e
, spec_time
);
692 if (time
- inlined_time
693 > (sreal
) (time
* PARAM_VALUE (PARAM_INLINE_MIN_SPEEDUP
))
699 /* Return true if we are interested in inlining small function.
700 When REPORT is true, report reason to dump file. */
703 want_inline_small_function_p (struct cgraph_edge
*e
, bool report
)
705 bool want_inline
= true;
706 struct cgraph_node
*callee
= e
->callee
->ultimate_alias_target ();
708 if (DECL_DISREGARD_INLINE_LIMITS (callee
->decl
))
710 else if (!DECL_DECLARED_INLINE_P (callee
->decl
)
711 && !opt_for_fn (e
->caller
->decl
, flag_inline_small_functions
))
713 e
->inline_failed
= CIF_FUNCTION_NOT_INLINE_CANDIDATE
;
716 /* Do fast and conservative check if the function can be good
717 inline candidate. At the moment we allow inline hints to
718 promote non-inline functions to inline and we increase
719 MAX_INLINE_INSNS_SINGLE 16-fold for inline functions. */
720 else if ((!DECL_DECLARED_INLINE_P (callee
->decl
)
721 && (!e
->count
.ipa ().initialized_p () || !e
->maybe_hot_p ()))
722 && ipa_fn_summaries
->get (callee
)->min_size
723 - ipa_call_summaries
->get (e
)->call_stmt_size
724 > MAX (MAX_INLINE_INSNS_SINGLE
, MAX_INLINE_INSNS_AUTO
))
726 e
->inline_failed
= CIF_MAX_INLINE_INSNS_AUTO_LIMIT
;
729 else if ((DECL_DECLARED_INLINE_P (callee
->decl
)
730 || e
->count
.ipa ().nonzero_p ())
731 && ipa_fn_summaries
->get (callee
)->min_size
732 - ipa_call_summaries
->get (e
)->call_stmt_size
733 > 16 * MAX_INLINE_INSNS_SINGLE
)
735 e
->inline_failed
= (DECL_DECLARED_INLINE_P (callee
->decl
)
736 ? CIF_MAX_INLINE_INSNS_SINGLE_LIMIT
737 : CIF_MAX_INLINE_INSNS_AUTO_LIMIT
);
742 int growth
= estimate_edge_growth (e
);
743 ipa_hints hints
= estimate_edge_hints (e
);
744 bool big_speedup
= big_speedup_p (e
);
748 /* Apply MAX_INLINE_INSNS_SINGLE limit. Do not do so when
749 hints suggests that inlining given function is very profitable. */
750 else if (DECL_DECLARED_INLINE_P (callee
->decl
)
751 && growth
>= MAX_INLINE_INSNS_SINGLE
753 && !(hints
& (INLINE_HINT_indirect_call
754 | INLINE_HINT_known_hot
755 | INLINE_HINT_loop_iterations
756 | INLINE_HINT_array_index
757 | INLINE_HINT_loop_stride
)))
758 || growth
>= MAX_INLINE_INSNS_SINGLE
* 16))
760 e
->inline_failed
= CIF_MAX_INLINE_INSNS_SINGLE_LIMIT
;
763 else if (!DECL_DECLARED_INLINE_P (callee
->decl
)
764 && !opt_for_fn (e
->caller
->decl
, flag_inline_functions
))
766 /* growth_likely_positive is expensive, always test it last. */
767 if (growth
>= MAX_INLINE_INSNS_SINGLE
768 || growth_likely_positive (callee
, growth
))
770 e
->inline_failed
= CIF_NOT_DECLARED_INLINED
;
774 /* Apply MAX_INLINE_INSNS_AUTO limit for functions not declared inline
775 Upgrade it to MAX_INLINE_INSNS_SINGLE when hints suggests that
776 inlining given function is very profitable. */
777 else if (!DECL_DECLARED_INLINE_P (callee
->decl
)
779 && !(hints
& INLINE_HINT_known_hot
)
780 && growth
>= ((hints
& (INLINE_HINT_indirect_call
781 | INLINE_HINT_loop_iterations
782 | INLINE_HINT_array_index
783 | INLINE_HINT_loop_stride
))
784 ? MAX (MAX_INLINE_INSNS_AUTO
,
785 MAX_INLINE_INSNS_SINGLE
)
786 : MAX_INLINE_INSNS_AUTO
))
788 /* growth_likely_positive is expensive, always test it last. */
789 if (growth
>= MAX_INLINE_INSNS_SINGLE
790 || growth_likely_positive (callee
, growth
))
792 e
->inline_failed
= CIF_MAX_INLINE_INSNS_AUTO_LIMIT
;
796 /* If call is cold, do not inline when function body would grow. */
797 else if (!e
->maybe_hot_p ()
798 && (growth
>= MAX_INLINE_INSNS_SINGLE
799 || growth_likely_positive (callee
, growth
)))
801 e
->inline_failed
= CIF_UNLIKELY_CALL
;
805 if (!want_inline
&& report
)
806 report_inline_failed_reason (e
);
810 /* EDGE is self recursive edge.
811 We hand two cases - when function A is inlining into itself
812 or when function A is being inlined into another inliner copy of function
815 In first case OUTER_NODE points to the toplevel copy of A, while
816 in the second case OUTER_NODE points to the outermost copy of A in B.
818 In both cases we want to be extra selective since
819 inlining the call will just introduce new recursive calls to appear. */
822 want_inline_self_recursive_call_p (struct cgraph_edge
*edge
,
823 struct cgraph_node
*outer_node
,
827 char const *reason
= NULL
;
828 bool want_inline
= true;
829 int caller_freq
= CGRAPH_FREQ_BASE
;
830 int max_depth
= PARAM_VALUE (PARAM_MAX_INLINE_RECURSIVE_DEPTH_AUTO
);
832 if (DECL_DECLARED_INLINE_P (edge
->caller
->decl
))
833 max_depth
= PARAM_VALUE (PARAM_MAX_INLINE_RECURSIVE_DEPTH
);
835 if (!edge
->maybe_hot_p ())
837 reason
= "recursive call is cold";
840 else if (!outer_node
->count
.ipa ().nonzero_p ())
842 reason
= "not executed in profile";
845 else if (depth
> max_depth
)
847 reason
= "--param max-inline-recursive-depth exceeded.";
851 if (outer_node
->global
.inlined_to
)
852 caller_freq
= outer_node
->callers
->frequency ();
856 reason
= "function is inlined and unlikely";
862 /* Inlining of self recursive function into copy of itself within other function
863 is transformation similar to loop peeling.
865 Peeling is profitable if we can inline enough copies to make probability
866 of actual call to the self recursive function very small. Be sure that
867 the probability of recursion is small.
869 We ensure that the frequency of recursing is at most 1 - (1/max_depth).
870 This way the expected number of recision is at most max_depth. */
873 int max_prob
= CGRAPH_FREQ_BASE
- ((CGRAPH_FREQ_BASE
+ max_depth
- 1)
876 for (i
= 1; i
< depth
; i
++)
877 max_prob
= max_prob
* max_prob
/ CGRAPH_FREQ_BASE
;
878 if (max_count
.nonzero_p () && edge
->count
.ipa ().nonzero_p ()
879 && (edge
->count
.ipa ().to_gcov_type () * CGRAPH_FREQ_BASE
880 / outer_node
->count
.ipa ().to_gcov_type ()
883 reason
= "profile of recursive call is too large";
886 if (!max_count
.nonzero_p ()
887 && (edge
->frequency () * CGRAPH_FREQ_BASE
/ caller_freq
890 reason
= "frequency of recursive call is too large";
894 /* Recursive inlining, i.e. equivalent of unrolling, is profitable if recursion
895 depth is large. We reduce function call overhead and increase chances that
896 things fit in hardware return predictor.
898 Recursive inlining might however increase cost of stack frame setup
899 actually slowing down functions whose recursion tree is wide rather than
902 Deciding reliably on when to do recursive inlining without profile feedback
903 is tricky. For now we disable recursive inlining when probability of self
906 Recursive inlining of self recursive call within loop also results in large loop
907 depths that generally optimize badly. We may want to throttle down inlining
908 in those cases. In particular this seems to happen in one of libstdc++ rb tree
912 if (max_count
.nonzero_p () && edge
->count
.ipa ().initialized_p ()
913 && (edge
->count
.ipa ().to_gcov_type () * 100
914 / outer_node
->count
.ipa ().to_gcov_type ()
915 <= PARAM_VALUE (PARAM_MIN_INLINE_RECURSIVE_PROBABILITY
)))
917 reason
= "profile of recursive call is too small";
920 else if ((!max_count
.nonzero_p ()
921 || !edge
->count
.ipa ().initialized_p ())
922 && (edge
->frequency () * 100 / caller_freq
923 <= PARAM_VALUE (PARAM_MIN_INLINE_RECURSIVE_PROBABILITY
)))
925 reason
= "frequency of recursive call is too small";
929 if (!want_inline
&& dump_file
)
930 fprintf (dump_file
, " not inlining recursively: %s\n", reason
);
934 /* Return true when NODE has uninlinable caller;
935 set HAS_HOT_CALL if it has hot call.
936 Worker for cgraph_for_node_and_aliases. */
939 check_callers (struct cgraph_node
*node
, void *has_hot_call
)
941 struct cgraph_edge
*e
;
942 for (e
= node
->callers
; e
; e
= e
->next_caller
)
944 if (!opt_for_fn (e
->caller
->decl
, flag_inline_functions_called_once
)
945 || !opt_for_fn (e
->caller
->decl
, optimize
))
947 if (!can_inline_edge_p (e
, true))
949 if (e
->recursive_p ())
951 if (!(*(bool *)has_hot_call
) && e
->maybe_hot_p ())
952 *(bool *)has_hot_call
= true;
957 /* If NODE has a caller, return true. */
960 has_caller_p (struct cgraph_node
*node
, void *data ATTRIBUTE_UNUSED
)
967 /* Decide if inlining NODE would reduce unit size by eliminating
968 the offline copy of function.
969 When COLD is true the cold calls are considered, too. */
972 want_inline_function_to_all_callers_p (struct cgraph_node
*node
, bool cold
)
974 bool has_hot_call
= false;
976 /* Aliases gets inlined along with the function they alias. */
979 /* Already inlined? */
980 if (node
->global
.inlined_to
)
982 /* Does it have callers? */
983 if (!node
->call_for_symbol_and_aliases (has_caller_p
, NULL
, true))
985 /* Inlining into all callers would increase size? */
986 if (estimate_growth (node
) > 0)
988 /* All inlines must be possible. */
989 if (node
->call_for_symbol_and_aliases (check_callers
, &has_hot_call
,
992 if (!cold
&& !has_hot_call
)
997 /* A cost model driving the inlining heuristics in a way so the edges with
998 smallest badness are inlined first. After each inlining is performed
999 the costs of all caller edges of nodes affected are recomputed so the
1000 metrics may accurately depend on values such as number of inlinable callers
1001 of the function or function body size. */
1004 edge_badness (struct cgraph_edge
*edge
, bool dump
)
1008 sreal edge_time
, unspec_edge_time
;
1009 struct cgraph_node
*callee
= edge
->callee
->ultimate_alias_target ();
1010 struct ipa_fn_summary
*callee_info
= ipa_fn_summaries
->get (callee
);
1012 cgraph_node
*caller
= (edge
->caller
->global
.inlined_to
1013 ? edge
->caller
->global
.inlined_to
1016 growth
= estimate_edge_growth (edge
);
1017 edge_time
= estimate_edge_time (edge
, &unspec_edge_time
);
1018 hints
= estimate_edge_hints (edge
);
1019 gcc_checking_assert (edge_time
>= 0);
1020 /* Check that inlined time is better, but tolerate some roundoff issues.
1021 FIXME: When callee profile drops to 0 we account calls more. This
1022 should be fixed by never doing that. */
1023 gcc_checking_assert ((edge_time
- callee_info
->time
).to_int () <= 0
1024 || callee
->count
.ipa ().initialized_p ());
1025 gcc_checking_assert (growth
<= callee_info
->size
);
1029 fprintf (dump_file
, " Badness calculation for %s -> %s\n",
1030 edge
->caller
->dump_name (),
1031 edge
->callee
->dump_name ());
1032 fprintf (dump_file
, " size growth %i, time %f unspec %f ",
1034 edge_time
.to_double (),
1035 unspec_edge_time
.to_double ());
1036 ipa_dump_hints (dump_file
, hints
);
1037 if (big_speedup_p (edge
))
1038 fprintf (dump_file
, " big_speedup");
1039 fprintf (dump_file
, "\n");
1042 /* Always prefer inlining saving code size. */
1045 badness
= (sreal
) (-SREAL_MIN_SIG
+ growth
) << (SREAL_MAX_EXP
/ 256);
1047 fprintf (dump_file
, " %f: Growth %d <= 0\n", badness
.to_double (),
1050 /* Inlining into EXTERNAL functions is not going to change anything unless
1051 they are themselves inlined. */
1052 else if (DECL_EXTERNAL (caller
->decl
))
1055 fprintf (dump_file
, " max: function is external\n");
1056 return sreal::max ();
1058 /* When profile is available. Compute badness as:
1060 time_saved * caller_count
1061 goodness = -------------------------------------------------
1062 growth_of_caller * overall_growth * combined_size
1064 badness = - goodness
1066 Again use negative value to make calls with profile appear hotter
1069 else if (opt_for_fn (caller
->decl
, flag_guess_branch_prob
)
1070 || caller
->count
.ipa ().nonzero_p ())
1072 sreal numerator
, denominator
;
1074 sreal inlined_time
= compute_inlined_call_time (edge
, edge_time
);
1076 numerator
= (compute_uninlined_call_time (edge
, unspec_edge_time
)
1079 numerator
= ((sreal
) 1 >> 8);
1080 if (caller
->count
.ipa ().nonzero_p ())
1081 numerator
*= caller
->count
.ipa ().to_gcov_type ();
1082 else if (caller
->count
.ipa ().initialized_p ())
1083 numerator
= numerator
>> 11;
1084 denominator
= growth
;
1086 overall_growth
= callee_info
->growth
;
1088 /* Look for inliner wrappers of the form:
1094 noninline_callee ();
1096 Withhout panilizing this case, we usually inline noninline_callee
1097 into the inline_caller because overall_growth is small preventing
1098 further inlining of inline_caller.
1100 Penalize only callgraph edges to functions with small overall
1103 if (growth
> overall_growth
1104 /* ... and having only one caller which is not inlined ... */
1105 && callee_info
->single_caller
1106 && !edge
->caller
->global
.inlined_to
1107 /* ... and edges executed only conditionally ... */
1108 && edge
->frequency () < CGRAPH_FREQ_BASE
1109 /* ... consider case where callee is not inline but caller is ... */
1110 && ((!DECL_DECLARED_INLINE_P (edge
->callee
->decl
)
1111 && DECL_DECLARED_INLINE_P (caller
->decl
))
1112 /* ... or when early optimizers decided to split and edge
1113 frequency still indicates splitting is a win ... */
1114 || (callee
->split_part
&& !caller
->split_part
1115 && edge
->frequency ()
1118 (PARAM_PARTIAL_INLINING_ENTRY_PROBABILITY
) / 100
1119 /* ... and do not overwrite user specified hints. */
1120 && (!DECL_DECLARED_INLINE_P (edge
->callee
->decl
)
1121 || DECL_DECLARED_INLINE_P (caller
->decl
)))))
1123 struct ipa_fn_summary
*caller_info
= ipa_fn_summaries
->get (caller
);
1124 int caller_growth
= caller_info
->growth
;
1126 /* Only apply the penalty when caller looks like inline candidate,
1127 and it is not called once and. */
1128 if (!caller_info
->single_caller
&& overall_growth
< caller_growth
1129 && caller_info
->inlinable
1130 && caller_info
->size
1131 < (DECL_DECLARED_INLINE_P (caller
->decl
)
1132 ? MAX_INLINE_INSNS_SINGLE
: MAX_INLINE_INSNS_AUTO
))
1136 " Wrapper penalty. Increasing growth %i to %i\n",
1137 overall_growth
, caller_growth
);
1138 overall_growth
= caller_growth
;
1141 if (overall_growth
> 0)
1143 /* Strongly preffer functions with few callers that can be inlined
1144 fully. The square root here leads to smaller binaries at average.
1145 Watch however for extreme cases and return to linear function
1146 when growth is large. */
1147 if (overall_growth
< 256)
1148 overall_growth
*= overall_growth
;
1150 overall_growth
+= 256 * 256 - 256;
1151 denominator
*= overall_growth
;
1153 denominator
*= inlined_time
;
1155 badness
= - numerator
/ denominator
;
1160 " %f: guessed profile. frequency %f, count %" PRId64
1161 " caller count %" PRId64
1162 " time w/o inlining %f, time with inlining %f"
1163 " overall growth %i (current) %i (original)"
1164 " %i (compensated)\n",
1165 badness
.to_double (),
1166 edge
->sreal_frequency ().to_double (),
1167 edge
->count
.ipa ().initialized_p () ? edge
->count
.ipa ().to_gcov_type () : -1,
1168 caller
->count
.ipa ().initialized_p () ? caller
->count
.ipa ().to_gcov_type () : -1,
1169 compute_uninlined_call_time (edge
,
1170 unspec_edge_time
).to_double (),
1171 compute_inlined_call_time (edge
, edge_time
).to_double (),
1172 estimate_growth (callee
),
1173 callee_info
->growth
, overall_growth
);
1176 /* When function local profile is not available or it does not give
1177 useful information (ie frequency is zero), base the cost on
1178 loop nest and overall size growth, so we optimize for overall number
1179 of functions fully inlined in program. */
1182 int nest
= MIN (ipa_call_summaries
->get (edge
)->loop_depth
, 8);
1185 /* Decrease badness if call is nested. */
1187 badness
= badness
>> nest
;
1189 badness
= badness
<< nest
;
1191 fprintf (dump_file
, " %f: no profile. nest %i\n",
1192 badness
.to_double (), nest
);
1194 gcc_checking_assert (badness
!= 0);
1196 if (edge
->recursive_p ())
1197 badness
= badness
.shift (badness
> 0 ? 4 : -4);
1198 if ((hints
& (INLINE_HINT_indirect_call
1199 | INLINE_HINT_loop_iterations
1200 | INLINE_HINT_array_index
1201 | INLINE_HINT_loop_stride
))
1202 || callee_info
->growth
<= 0)
1203 badness
= badness
.shift (badness
> 0 ? -2 : 2);
1204 if (hints
& (INLINE_HINT_same_scc
))
1205 badness
= badness
.shift (badness
> 0 ? 3 : -3);
1206 else if (hints
& (INLINE_HINT_in_scc
))
1207 badness
= badness
.shift (badness
> 0 ? 2 : -2);
1208 else if (hints
& (INLINE_HINT_cross_module
))
1209 badness
= badness
.shift (badness
> 0 ? 1 : -1);
1210 if (DECL_DISREGARD_INLINE_LIMITS (callee
->decl
))
1211 badness
= badness
.shift (badness
> 0 ? -4 : 4);
1212 else if ((hints
& INLINE_HINT_declared_inline
))
1213 badness
= badness
.shift (badness
> 0 ? -3 : 3);
1215 fprintf (dump_file
, " Adjusted by hints %f\n", badness
.to_double ());
1219 /* Recompute badness of EDGE and update its key in HEAP if needed. */
1221 update_edge_key (edge_heap_t
*heap
, struct cgraph_edge
*edge
)
1223 sreal badness
= edge_badness (edge
, false);
1226 edge_heap_node_t
*n
= (edge_heap_node_t
*) edge
->aux
;
1227 gcc_checking_assert (n
->get_data () == edge
);
1229 /* fibonacci_heap::replace_key does busy updating of the
1230 heap that is unnecesarily expensive.
1231 We do lazy increases: after extracting minimum if the key
1232 turns out to be out of date, it is re-inserted into heap
1233 with correct value. */
1234 if (badness
< n
->get_key ())
1236 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1239 " decreasing badness %s -> %s, %f to %f\n",
1240 edge
->caller
->dump_name (),
1241 edge
->callee
->dump_name (),
1242 n
->get_key ().to_double (),
1243 badness
.to_double ());
1245 heap
->decrease_key (n
, badness
);
1250 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1253 " enqueuing call %s -> %s, badness %f\n",
1254 edge
->caller
->dump_name (),
1255 edge
->callee
->dump_name (),
1256 badness
.to_double ());
1258 edge
->aux
= heap
->insert (badness
, edge
);
1263 /* NODE was inlined.
1264 All caller edges needs to be resetted because
1265 size estimates change. Similarly callees needs reset
1266 because better context may be known. */
1269 reset_edge_caches (struct cgraph_node
*node
)
1271 struct cgraph_edge
*edge
;
1272 struct cgraph_edge
*e
= node
->callees
;
1273 struct cgraph_node
*where
= node
;
1274 struct ipa_ref
*ref
;
1276 if (where
->global
.inlined_to
)
1277 where
= where
->global
.inlined_to
;
1279 for (edge
= where
->callers
; edge
; edge
= edge
->next_caller
)
1280 if (edge
->inline_failed
)
1281 reset_edge_growth_cache (edge
);
1283 FOR_EACH_ALIAS (where
, ref
)
1284 reset_edge_caches (dyn_cast
<cgraph_node
*> (ref
->referring
));
1290 if (!e
->inline_failed
&& e
->callee
->callees
)
1291 e
= e
->callee
->callees
;
1294 if (e
->inline_failed
)
1295 reset_edge_growth_cache (e
);
1302 if (e
->caller
== node
)
1304 e
= e
->caller
->callers
;
1306 while (!e
->next_callee
);
1312 /* Recompute HEAP nodes for each of caller of NODE.
1313 UPDATED_NODES track nodes we already visited, to avoid redundant work.
1314 When CHECK_INLINABLITY_FOR is set, re-check for specified edge that
1315 it is inlinable. Otherwise check all edges. */
1318 update_caller_keys (edge_heap_t
*heap
, struct cgraph_node
*node
,
1319 bitmap updated_nodes
,
1320 struct cgraph_edge
*check_inlinablity_for
)
1322 struct cgraph_edge
*edge
;
1323 struct ipa_ref
*ref
;
1325 if ((!node
->alias
&& !ipa_fn_summaries
->get (node
)->inlinable
)
1326 || node
->global
.inlined_to
)
1328 if (!bitmap_set_bit (updated_nodes
, node
->uid
))
1331 FOR_EACH_ALIAS (node
, ref
)
1333 struct cgraph_node
*alias
= dyn_cast
<cgraph_node
*> (ref
->referring
);
1334 update_caller_keys (heap
, alias
, updated_nodes
, check_inlinablity_for
);
1337 for (edge
= node
->callers
; edge
; edge
= edge
->next_caller
)
1338 if (edge
->inline_failed
)
1340 if (!check_inlinablity_for
1341 || check_inlinablity_for
== edge
)
1343 if (can_inline_edge_p (edge
, false)
1344 && want_inline_small_function_p (edge
, false))
1345 update_edge_key (heap
, edge
);
1348 report_inline_failed_reason (edge
);
1349 heap
->delete_node ((edge_heap_node_t
*) edge
->aux
);
1354 update_edge_key (heap
, edge
);
1358 /* Recompute HEAP nodes for each uninlined call in NODE.
1359 This is used when we know that edge badnesses are going only to increase
1360 (we introduced new call site) and thus all we need is to insert newly
1361 created edges into heap. */
1364 update_callee_keys (edge_heap_t
*heap
, struct cgraph_node
*node
,
1365 bitmap updated_nodes
)
1367 struct cgraph_edge
*e
= node
->callees
;
1372 if (!e
->inline_failed
&& e
->callee
->callees
)
1373 e
= e
->callee
->callees
;
1376 enum availability avail
;
1377 struct cgraph_node
*callee
;
1378 /* We do not reset callee growth cache here. Since we added a new call,
1379 growth chould have just increased and consequentely badness metric
1380 don't need updating. */
1381 if (e
->inline_failed
1382 && (callee
= e
->callee
->ultimate_alias_target (&avail
, e
->caller
))
1383 && ipa_fn_summaries
->get (callee
)->inlinable
1384 && avail
>= AVAIL_AVAILABLE
1385 && !bitmap_bit_p (updated_nodes
, callee
->uid
))
1387 if (can_inline_edge_p (e
, false)
1388 && want_inline_small_function_p (e
, false))
1389 update_edge_key (heap
, e
);
1392 report_inline_failed_reason (e
);
1393 heap
->delete_node ((edge_heap_node_t
*) e
->aux
);
1403 if (e
->caller
== node
)
1405 e
= e
->caller
->callers
;
1407 while (!e
->next_callee
);
1413 /* Enqueue all recursive calls from NODE into priority queue depending on
1414 how likely we want to recursively inline the call. */
1417 lookup_recursive_calls (struct cgraph_node
*node
, struct cgraph_node
*where
,
1420 struct cgraph_edge
*e
;
1421 enum availability avail
;
1423 for (e
= where
->callees
; e
; e
= e
->next_callee
)
1424 if (e
->callee
== node
1425 || (e
->callee
->ultimate_alias_target (&avail
, e
->caller
) == node
1426 && avail
> AVAIL_INTERPOSABLE
))
1428 /* When profile feedback is available, prioritize by expected number
1430 heap
->insert (!(max_count
> 0) || !e
->count
.ipa ().initialized_p () ? -e
->frequency ()
1431 : -(e
->count
.ipa ().to_gcov_type ()
1432 / ((max_count
.to_gcov_type () + (1<<24) - 1)
1436 for (e
= where
->callees
; e
; e
= e
->next_callee
)
1437 if (!e
->inline_failed
)
1438 lookup_recursive_calls (node
, e
->callee
, heap
);
1441 /* Decide on recursive inlining: in the case function has recursive calls,
1442 inline until body size reaches given argument. If any new indirect edges
1443 are discovered in the process, add them to *NEW_EDGES, unless NEW_EDGES
1447 recursive_inlining (struct cgraph_edge
*edge
,
1448 vec
<cgraph_edge
*> *new_edges
)
1450 int limit
= PARAM_VALUE (PARAM_MAX_INLINE_INSNS_RECURSIVE_AUTO
);
1451 edge_heap_t
heap (sreal::min ());
1452 struct cgraph_node
*node
;
1453 struct cgraph_edge
*e
;
1454 struct cgraph_node
*master_clone
= NULL
, *next
;
1458 node
= edge
->caller
;
1459 if (node
->global
.inlined_to
)
1460 node
= node
->global
.inlined_to
;
1462 if (DECL_DECLARED_INLINE_P (node
->decl
))
1463 limit
= PARAM_VALUE (PARAM_MAX_INLINE_INSNS_RECURSIVE
);
1465 /* Make sure that function is small enough to be considered for inlining. */
1466 if (estimate_size_after_inlining (node
, edge
) >= limit
)
1468 lookup_recursive_calls (node
, node
, &heap
);
1474 " Performing recursive inlining on %s\n",
1477 /* Do the inlining and update list of recursive call during process. */
1478 while (!heap
.empty ())
1480 struct cgraph_edge
*curr
= heap
.extract_min ();
1481 struct cgraph_node
*cnode
, *dest
= curr
->callee
;
1483 if (!can_inline_edge_p (curr
, true))
1486 /* MASTER_CLONE is produced in the case we already started modified
1487 the function. Be sure to redirect edge to the original body before
1488 estimating growths otherwise we will be seeing growths after inlining
1489 the already modified body. */
1492 curr
->redirect_callee (master_clone
);
1493 reset_edge_growth_cache (curr
);
1496 if (estimate_size_after_inlining (node
, curr
) > limit
)
1498 curr
->redirect_callee (dest
);
1499 reset_edge_growth_cache (curr
);
1504 for (cnode
= curr
->caller
;
1505 cnode
->global
.inlined_to
; cnode
= cnode
->callers
->caller
)
1507 == curr
->callee
->ultimate_alias_target ()->decl
)
1510 if (!want_inline_self_recursive_call_p (curr
, node
, false, depth
))
1512 curr
->redirect_callee (dest
);
1513 reset_edge_growth_cache (curr
);
1520 " Inlining call of depth %i", depth
);
1521 if (node
->count
.nonzero_p ())
1523 fprintf (dump_file
, " called approx. %.2f times per call",
1524 (double)curr
->count
.to_gcov_type ()
1525 / node
->count
.to_gcov_type ());
1527 fprintf (dump_file
, "\n");
1531 /* We need original clone to copy around. */
1532 master_clone
= node
->create_clone (node
->decl
, node
->count
,
1533 false, vNULL
, true, NULL
, NULL
);
1534 for (e
= master_clone
->callees
; e
; e
= e
->next_callee
)
1535 if (!e
->inline_failed
)
1536 clone_inlined_nodes (e
, true, false, NULL
);
1537 curr
->redirect_callee (master_clone
);
1538 reset_edge_growth_cache (curr
);
1541 inline_call (curr
, false, new_edges
, &overall_size
, true);
1542 lookup_recursive_calls (node
, curr
->callee
, &heap
);
1546 if (!heap
.empty () && dump_file
)
1547 fprintf (dump_file
, " Recursive inlining growth limit met.\n");
1554 "\n Inlined %i times, "
1555 "body grown from size %i to %i, time %f to %f\n", n
,
1556 ipa_fn_summaries
->get (master_clone
)->size
,
1557 ipa_fn_summaries
->get (node
)->size
,
1558 ipa_fn_summaries
->get (master_clone
)->time
.to_double (),
1559 ipa_fn_summaries
->get (node
)->time
.to_double ());
1561 /* Remove master clone we used for inlining. We rely that clones inlined
1562 into master clone gets queued just before master clone so we don't
1564 for (node
= symtab
->first_function (); node
!= master_clone
;
1567 next
= symtab
->next_function (node
);
1568 if (node
->global
.inlined_to
== master_clone
)
1571 master_clone
->remove ();
1576 /* Given whole compilation unit estimate of INSNS, compute how large we can
1577 allow the unit to grow. */
1580 compute_max_insns (int insns
)
1582 int max_insns
= insns
;
1583 if (max_insns
< PARAM_VALUE (PARAM_LARGE_UNIT_INSNS
))
1584 max_insns
= PARAM_VALUE (PARAM_LARGE_UNIT_INSNS
);
1586 return ((int64_t) max_insns
1587 * (100 + PARAM_VALUE (PARAM_INLINE_UNIT_GROWTH
)) / 100);
1591 /* Compute badness of all edges in NEW_EDGES and add them to the HEAP. */
1594 add_new_edges_to_heap (edge_heap_t
*heap
, vec
<cgraph_edge
*> new_edges
)
1596 while (new_edges
.length () > 0)
1598 struct cgraph_edge
*edge
= new_edges
.pop ();
1600 gcc_assert (!edge
->aux
);
1601 if (edge
->inline_failed
1602 && can_inline_edge_p (edge
, true)
1603 && want_inline_small_function_p (edge
, true))
1604 edge
->aux
= heap
->insert (edge_badness (edge
, false), edge
);
1608 /* Remove EDGE from the fibheap. */
1611 heap_edge_removal_hook (struct cgraph_edge
*e
, void *data
)
1615 ((edge_heap_t
*)data
)->delete_node ((edge_heap_node_t
*)e
->aux
);
1620 /* Return true if speculation of edge E seems useful.
1621 If ANTICIPATE_INLINING is true, be conservative and hope that E
1625 speculation_useful_p (struct cgraph_edge
*e
, bool anticipate_inlining
)
1627 enum availability avail
;
1628 struct cgraph_node
*target
= e
->callee
->ultimate_alias_target (&avail
,
1630 struct cgraph_edge
*direct
, *indirect
;
1631 struct ipa_ref
*ref
;
1633 gcc_assert (e
->speculative
&& !e
->indirect_unknown_callee
);
1635 if (!e
->maybe_hot_p ())
1638 /* See if IP optimizations found something potentially useful about the
1639 function. For now we look only for CONST/PURE flags. Almost everything
1640 else we propagate is useless. */
1641 if (avail
>= AVAIL_AVAILABLE
)
1643 int ecf_flags
= flags_from_decl_or_type (target
->decl
);
1644 if (ecf_flags
& ECF_CONST
)
1646 e
->speculative_call_info (direct
, indirect
, ref
);
1647 if (!(indirect
->indirect_info
->ecf_flags
& ECF_CONST
))
1650 else if (ecf_flags
& ECF_PURE
)
1652 e
->speculative_call_info (direct
, indirect
, ref
);
1653 if (!(indirect
->indirect_info
->ecf_flags
& ECF_PURE
))
1657 /* If we did not managed to inline the function nor redirect
1658 to an ipa-cp clone (that are seen by having local flag set),
1659 it is probably pointless to inline it unless hardware is missing
1660 indirect call predictor. */
1661 if (!anticipate_inlining
&& e
->inline_failed
&& !target
->local
.local
)
1663 /* For overwritable targets there is not much to do. */
1664 if (e
->inline_failed
&& !can_inline_edge_p (e
, false, true))
1666 /* OK, speculation seems interesting. */
1670 /* We know that EDGE is not going to be inlined.
1671 See if we can remove speculation. */
1674 resolve_noninline_speculation (edge_heap_t
*edge_heap
, struct cgraph_edge
*edge
)
1676 if (edge
->speculative
&& !speculation_useful_p (edge
, false))
1678 struct cgraph_node
*node
= edge
->caller
;
1679 struct cgraph_node
*where
= node
->global
.inlined_to
1680 ? node
->global
.inlined_to
: node
;
1681 auto_bitmap updated_nodes
;
1683 if (edge
->count
.ipa ().initialized_p ())
1684 spec_rem
+= edge
->count
.ipa ();
1685 edge
->resolve_speculation ();
1686 reset_edge_caches (where
);
1687 ipa_update_overall_fn_summary (where
);
1688 update_caller_keys (edge_heap
, where
,
1689 updated_nodes
, NULL
);
1690 update_callee_keys (edge_heap
, where
,
1695 /* Return true if NODE should be accounted for overall size estimate.
1696 Skip all nodes optimized for size so we can measure the growth of hot
1697 part of program no matter of the padding. */
1700 inline_account_function_p (struct cgraph_node
*node
)
1702 return (!DECL_EXTERNAL (node
->decl
)
1703 && !opt_for_fn (node
->decl
, optimize_size
)
1704 && node
->frequency
!= NODE_FREQUENCY_UNLIKELY_EXECUTED
);
1707 /* Count number of callers of NODE and store it into DATA (that
1708 points to int. Worker for cgraph_for_node_and_aliases. */
1711 sum_callers (struct cgraph_node
*node
, void *data
)
1713 struct cgraph_edge
*e
;
1714 int *num_calls
= (int *)data
;
1716 for (e
= node
->callers
; e
; e
= e
->next_caller
)
1721 /* We use greedy algorithm for inlining of small functions:
1722 All inline candidates are put into prioritized heap ordered in
1725 The inlining of small functions is bounded by unit growth parameters. */
1728 inline_small_functions (void)
1730 struct cgraph_node
*node
;
1731 struct cgraph_edge
*edge
;
1732 edge_heap_t
edge_heap (sreal::min ());
1733 auto_bitmap updated_nodes
;
1734 int min_size
, max_size
;
1735 auto_vec
<cgraph_edge
*> new_indirect_edges
;
1736 int initial_size
= 0;
1737 struct cgraph_node
**order
= XCNEWVEC (cgraph_node
*, symtab
->cgraph_count
);
1738 struct cgraph_edge_hook_list
*edge_removal_hook_holder
;
1739 new_indirect_edges
.create (8);
1741 edge_removal_hook_holder
1742 = symtab
->add_edge_removal_hook (&heap_edge_removal_hook
, &edge_heap
);
1744 /* Compute overall unit size and other global parameters used by badness
1747 max_count
= profile_count::uninitialized ();
1748 ipa_reduced_postorder (order
, true, true, NULL
);
1751 FOR_EACH_DEFINED_FUNCTION (node
)
1752 if (!node
->global
.inlined_to
)
1754 if (!node
->alias
&& node
->analyzed
1755 && (node
->has_gimple_body_p () || node
->thunk
.thunk_p
)
1756 && opt_for_fn (node
->decl
, optimize
))
1758 struct ipa_fn_summary
*info
= ipa_fn_summaries
->get (node
);
1759 struct ipa_dfs_info
*dfs
= (struct ipa_dfs_info
*) node
->aux
;
1761 /* Do not account external functions, they will be optimized out
1762 if not inlined. Also only count the non-cold portion of program. */
1763 if (inline_account_function_p (node
))
1764 initial_size
+= info
->size
;
1765 info
->growth
= estimate_growth (node
);
1768 node
->call_for_symbol_and_aliases (sum_callers
, &num_calls
,
1771 info
->single_caller
= true;
1772 if (dfs
&& dfs
->next_cycle
)
1774 struct cgraph_node
*n2
;
1775 int id
= dfs
->scc_no
+ 1;
1777 n2
= ((struct ipa_dfs_info
*) node
->aux
)->next_cycle
)
1778 if (opt_for_fn (n2
->decl
, optimize
))
1780 struct ipa_fn_summary
*info2
= ipa_fn_summaries
->get (n2
);
1788 for (edge
= node
->callers
; edge
; edge
= edge
->next_caller
)
1789 max_count
= max_count
.max (edge
->count
.ipa ());
1791 ipa_free_postorder_info ();
1792 initialize_growth_caches ();
1796 "\nDeciding on inlining of small functions. Starting with size %i.\n",
1799 overall_size
= initial_size
;
1800 max_size
= compute_max_insns (overall_size
);
1801 min_size
= overall_size
;
1803 /* Populate the heap with all edges we might inline. */
1805 FOR_EACH_DEFINED_FUNCTION (node
)
1807 bool update
= false;
1808 struct cgraph_edge
*next
= NULL
;
1809 bool has_speculative
= false;
1811 if (!opt_for_fn (node
->decl
, optimize
))
1815 fprintf (dump_file
, "Enqueueing calls in %s.\n", node
->dump_name ());
1817 for (edge
= node
->callees
; edge
; edge
= next
)
1819 next
= edge
->next_callee
;
1820 if (edge
->inline_failed
1822 && can_inline_edge_p (edge
, true)
1823 && want_inline_small_function_p (edge
, true)
1824 && edge
->inline_failed
)
1826 gcc_assert (!edge
->aux
);
1827 update_edge_key (&edge_heap
, edge
);
1829 if (edge
->speculative
)
1830 has_speculative
= true;
1832 if (has_speculative
)
1833 for (edge
= node
->callees
; edge
; edge
= next
)
1834 if (edge
->speculative
&& !speculation_useful_p (edge
,
1837 edge
->resolve_speculation ();
1842 struct cgraph_node
*where
= node
->global
.inlined_to
1843 ? node
->global
.inlined_to
: node
;
1844 ipa_update_overall_fn_summary (where
);
1845 reset_edge_caches (where
);
1846 update_caller_keys (&edge_heap
, where
,
1847 updated_nodes
, NULL
);
1848 update_callee_keys (&edge_heap
, where
,
1850 bitmap_clear (updated_nodes
);
1854 gcc_assert (in_lto_p
1856 || (profile_info
&& flag_branch_probabilities
));
1858 while (!edge_heap
.empty ())
1860 int old_size
= overall_size
;
1861 struct cgraph_node
*where
, *callee
;
1862 sreal badness
= edge_heap
.min_key ();
1863 sreal current_badness
;
1866 edge
= edge_heap
.extract_min ();
1867 gcc_assert (edge
->aux
);
1869 if (!edge
->inline_failed
|| !edge
->callee
->analyzed
)
1873 /* Be sure that caches are maintained consistent.
1874 This check is affected by scaling roundoff errors when compiling for
1875 IPA this we skip it in that case. */
1876 if (!edge
->callee
->count
.ipa_p ())
1878 sreal cached_badness
= edge_badness (edge
, false);
1880 int old_size_est
= estimate_edge_size (edge
);
1881 sreal old_time_est
= estimate_edge_time (edge
);
1882 int old_hints_est
= estimate_edge_hints (edge
);
1884 reset_edge_growth_cache (edge
);
1885 gcc_assert (old_size_est
== estimate_edge_size (edge
));
1886 gcc_assert (old_time_est
== estimate_edge_time (edge
));
1889 gcc_assert (old_hints_est == estimate_edge_hints (edge));
1891 fails with profile feedback because some hints depends on
1892 maybe_hot_edge_p predicate and because callee gets inlined to other
1893 calls, the edge may become cold.
1894 This ought to be fixed by computing relative probabilities
1895 for given invocation but that will be better done once whole
1896 code is converted to sreals. Disable for now and revert to "wrong"
1897 value so enable/disable checking paths agree. */
1898 edge_growth_cache
[edge
->uid
].hints
= old_hints_est
+ 1;
1900 /* When updating the edge costs, we only decrease badness in the keys.
1901 Increases of badness are handled lazilly; when we see key with out
1902 of date value on it, we re-insert it now. */
1903 current_badness
= edge_badness (edge
, false);
1904 gcc_assert (cached_badness
== current_badness
);
1905 gcc_assert (current_badness
>= badness
);
1908 current_badness
= edge_badness (edge
, false);
1910 if (current_badness
!= badness
)
1912 if (edge_heap
.min () && current_badness
> edge_heap
.min_key ())
1914 edge
->aux
= edge_heap
.insert (current_badness
, edge
);
1918 badness
= current_badness
;
1921 if (!can_inline_edge_p (edge
, true))
1923 resolve_noninline_speculation (&edge_heap
, edge
);
1927 callee
= edge
->callee
->ultimate_alias_target ();
1928 growth
= estimate_edge_growth (edge
);
1932 "\nConsidering %s with %i size\n",
1933 callee
->dump_name (),
1934 ipa_fn_summaries
->get (callee
)->size
);
1936 " to be inlined into %s in %s:%i\n"
1937 " Estimated badness is %f, frequency %.2f.\n",
1938 edge
->caller
->dump_name (),
1940 && (LOCATION_LOCUS (gimple_location ((const gimple
*)
1942 > BUILTINS_LOCATION
)
1943 ? gimple_filename ((const gimple
*) edge
->call_stmt
)
1946 ? gimple_lineno ((const gimple
*) edge
->call_stmt
)
1948 badness
.to_double (),
1949 edge
->sreal_frequency ().to_double ());
1950 if (edge
->count
.ipa ().initialized_p ())
1952 fprintf (dump_file
, " Called ");
1953 edge
->count
.ipa ().dump (dump_file
);
1954 fprintf (dump_file
, "times\n");
1956 if (dump_flags
& TDF_DETAILS
)
1957 edge_badness (edge
, true);
1960 if (overall_size
+ growth
> max_size
1961 && !DECL_DISREGARD_INLINE_LIMITS (callee
->decl
))
1963 edge
->inline_failed
= CIF_INLINE_UNIT_GROWTH_LIMIT
;
1964 report_inline_failed_reason (edge
);
1965 resolve_noninline_speculation (&edge_heap
, edge
);
1969 if (!want_inline_small_function_p (edge
, true))
1971 resolve_noninline_speculation (&edge_heap
, edge
);
1975 /* Heuristics for inlining small functions work poorly for
1976 recursive calls where we do effects similar to loop unrolling.
1977 When inlining such edge seems profitable, leave decision on
1978 specific inliner. */
1979 if (edge
->recursive_p ())
1981 where
= edge
->caller
;
1982 if (where
->global
.inlined_to
)
1983 where
= where
->global
.inlined_to
;
1984 if (!recursive_inlining (edge
,
1985 opt_for_fn (edge
->caller
->decl
,
1986 flag_indirect_inlining
)
1987 ? &new_indirect_edges
: NULL
))
1989 edge
->inline_failed
= CIF_RECURSIVE_INLINING
;
1990 resolve_noninline_speculation (&edge_heap
, edge
);
1993 reset_edge_caches (where
);
1994 /* Recursive inliner inlines all recursive calls of the function
1995 at once. Consequently we need to update all callee keys. */
1996 if (opt_for_fn (edge
->caller
->decl
, flag_indirect_inlining
))
1997 add_new_edges_to_heap (&edge_heap
, new_indirect_edges
);
1998 update_callee_keys (&edge_heap
, where
, updated_nodes
);
1999 bitmap_clear (updated_nodes
);
2003 struct cgraph_node
*outer_node
= NULL
;
2006 /* Consider the case where self recursive function A is inlined
2007 into B. This is desired optimization in some cases, since it
2008 leads to effect similar of loop peeling and we might completely
2009 optimize out the recursive call. However we must be extra
2012 where
= edge
->caller
;
2013 while (where
->global
.inlined_to
)
2015 if (where
->decl
== callee
->decl
)
2016 outer_node
= where
, depth
++;
2017 where
= where
->callers
->caller
;
2020 && !want_inline_self_recursive_call_p (edge
, outer_node
,
2024 = (DECL_DISREGARD_INLINE_LIMITS (edge
->callee
->decl
)
2025 ? CIF_RECURSIVE_INLINING
: CIF_UNSPECIFIED
);
2026 resolve_noninline_speculation (&edge_heap
, edge
);
2029 else if (depth
&& dump_file
)
2030 fprintf (dump_file
, " Peeling recursion with depth %i\n", depth
);
2032 gcc_checking_assert (!callee
->global
.inlined_to
);
2033 inline_call (edge
, true, &new_indirect_edges
, &overall_size
, true);
2034 add_new_edges_to_heap (&edge_heap
, new_indirect_edges
);
2036 reset_edge_caches (edge
->callee
);
2038 update_callee_keys (&edge_heap
, where
, updated_nodes
);
2040 where
= edge
->caller
;
2041 if (where
->global
.inlined_to
)
2042 where
= where
->global
.inlined_to
;
2044 /* Our profitability metric can depend on local properties
2045 such as number of inlinable calls and size of the function body.
2046 After inlining these properties might change for the function we
2047 inlined into (since it's body size changed) and for the functions
2048 called by function we inlined (since number of it inlinable callers
2050 update_caller_keys (&edge_heap
, where
, updated_nodes
, NULL
);
2051 /* Offline copy count has possibly changed, recompute if profile is
2053 if (max_count
.nonzero_p ())
2055 struct cgraph_node
*n
= cgraph_node::get (edge
->callee
->decl
);
2056 if (n
!= edge
->callee
&& n
->analyzed
)
2057 update_callee_keys (&edge_heap
, n
, updated_nodes
);
2059 bitmap_clear (updated_nodes
);
2064 " Inlined %s into %s which now has time %f and size %i, "
2065 "net change of %+i.\n",
2066 xstrdup_for_dump (edge
->callee
->name ()),
2067 xstrdup_for_dump (edge
->caller
->name ()),
2068 ipa_fn_summaries
->get (edge
->caller
)->time
.to_double (),
2069 ipa_fn_summaries
->get (edge
->caller
)->size
,
2070 overall_size
- old_size
);
2072 if (min_size
> overall_size
)
2074 min_size
= overall_size
;
2075 max_size
= compute_max_insns (min_size
);
2078 fprintf (dump_file
, "New minimal size reached: %i\n", min_size
);
2082 free_growth_caches ();
2085 "Unit growth for small function inlining: %i->%i (%i%%)\n",
2086 initial_size
, overall_size
,
2087 initial_size
? overall_size
* 100 / (initial_size
) - 100: 0);
2088 symtab
->remove_edge_removal_hook (edge_removal_hook_holder
);
2091 /* Flatten NODE. Performed both during early inlining and
2092 at IPA inlining time. */
2095 flatten_function (struct cgraph_node
*node
, bool early
)
2097 struct cgraph_edge
*e
;
2099 /* We shouldn't be called recursively when we are being processed. */
2100 gcc_assert (node
->aux
== NULL
);
2102 node
->aux
= (void *) node
;
2104 for (e
= node
->callees
; e
; e
= e
->next_callee
)
2106 struct cgraph_node
*orig_callee
;
2107 struct cgraph_node
*callee
= e
->callee
->ultimate_alias_target ();
2109 /* We've hit cycle? It is time to give up. */
2114 "Not inlining %s into %s to avoid cycle.\n",
2115 xstrdup_for_dump (callee
->name ()),
2116 xstrdup_for_dump (e
->caller
->name ()));
2117 e
->inline_failed
= CIF_RECURSIVE_INLINING
;
2121 /* When the edge is already inlined, we just need to recurse into
2122 it in order to fully flatten the leaves. */
2123 if (!e
->inline_failed
)
2125 flatten_function (callee
, early
);
2129 /* Flatten attribute needs to be processed during late inlining. For
2130 extra code quality we however do flattening during early optimization,
2133 ? !can_inline_edge_p (e
, true)
2134 : !can_early_inline_edge_p (e
))
2137 if (e
->recursive_p ())
2140 fprintf (dump_file
, "Not inlining: recursive call.\n");
2144 if (gimple_in_ssa_p (DECL_STRUCT_FUNCTION (node
->decl
))
2145 != gimple_in_ssa_p (DECL_STRUCT_FUNCTION (callee
->decl
)))
2148 fprintf (dump_file
, "Not inlining: SSA form does not match.\n");
2152 /* Inline the edge and flatten the inline clone. Avoid
2153 recursing through the original node if the node was cloned. */
2155 fprintf (dump_file
, " Inlining %s into %s.\n",
2156 xstrdup_for_dump (callee
->name ()),
2157 xstrdup_for_dump (e
->caller
->name ()));
2158 orig_callee
= callee
;
2159 inline_call (e
, true, NULL
, NULL
, false);
2160 if (e
->callee
!= orig_callee
)
2161 orig_callee
->aux
= (void *) node
;
2162 flatten_function (e
->callee
, early
);
2163 if (e
->callee
!= orig_callee
)
2164 orig_callee
->aux
= NULL
;
2168 if (!node
->global
.inlined_to
)
2169 ipa_update_overall_fn_summary (node
);
2172 /* Inline NODE to all callers. Worker for cgraph_for_node_and_aliases.
2173 DATA points to number of calls originally found so we avoid infinite
2177 inline_to_all_callers_1 (struct cgraph_node
*node
, void *data
,
2178 hash_set
<cgraph_node
*> *callers
)
2180 int *num_calls
= (int *)data
;
2181 bool callee_removed
= false;
2183 while (node
->callers
&& !node
->global
.inlined_to
)
2185 struct cgraph_node
*caller
= node
->callers
->caller
;
2187 if (!can_inline_edge_p (node
->callers
, true)
2188 || node
->callers
->recursive_p ())
2191 fprintf (dump_file
, "Uninlinable call found; giving up.\n");
2199 "\nInlining %s size %i.\n",
2201 ipa_fn_summaries
->get (node
)->size
);
2203 " Called once from %s %i insns.\n",
2204 node
->callers
->caller
->name (),
2205 ipa_fn_summaries
->get (node
->callers
->caller
)->size
);
2208 /* Remember which callers we inlined to, delaying updating the
2210 callers
->add (node
->callers
->caller
);
2211 inline_call (node
->callers
, true, NULL
, NULL
, false, &callee_removed
);
2214 " Inlined into %s which now has %i size\n",
2216 ipa_fn_summaries
->get (caller
)->size
);
2217 if (!(*num_calls
)--)
2220 fprintf (dump_file
, "New calls found; giving up.\n");
2221 return callee_removed
;
2229 /* Wrapper around inline_to_all_callers_1 doing delayed overall summary
2233 inline_to_all_callers (struct cgraph_node
*node
, void *data
)
2235 hash_set
<cgraph_node
*> callers
;
2236 bool res
= inline_to_all_callers_1 (node
, data
, &callers
);
2237 /* Perform the delayed update of the overall summary of all callers
2238 processed. This avoids quadratic behavior in the cases where
2239 we have a lot of calls to the same function. */
2240 for (hash_set
<cgraph_node
*>::iterator i
= callers
.begin ();
2241 i
!= callers
.end (); ++i
)
2242 ipa_update_overall_fn_summary (*i
);
2246 /* Output overall time estimate. */
2248 dump_overall_stats (void)
2250 sreal sum_weighted
= 0, sum
= 0;
2251 struct cgraph_node
*node
;
2253 FOR_EACH_DEFINED_FUNCTION (node
)
2254 if (!node
->global
.inlined_to
2257 sreal time
= ipa_fn_summaries
->get (node
)->time
;
2259 if (node
->count
.ipa ().initialized_p ())
2260 sum_weighted
+= time
* node
->count
.ipa ().to_gcov_type ();
2262 fprintf (dump_file
, "Overall time estimate: "
2263 "%f weighted by profile: "
2264 "%f\n", sum
.to_double (), sum_weighted
.to_double ());
2267 /* Output some useful stats about inlining. */
2270 dump_inline_stats (void)
2272 int64_t inlined_cnt
= 0, inlined_indir_cnt
= 0;
2273 int64_t inlined_virt_cnt
= 0, inlined_virt_indir_cnt
= 0;
2274 int64_t noninlined_cnt
= 0, noninlined_indir_cnt
= 0;
2275 int64_t noninlined_virt_cnt
= 0, noninlined_virt_indir_cnt
= 0;
2276 int64_t inlined_speculative
= 0, inlined_speculative_ply
= 0;
2277 int64_t indirect_poly_cnt
= 0, indirect_cnt
= 0;
2278 int64_t reason
[CIF_N_REASONS
][3];
2280 struct cgraph_node
*node
;
2282 memset (reason
, 0, sizeof (reason
));
2283 FOR_EACH_DEFINED_FUNCTION (node
)
2285 struct cgraph_edge
*e
;
2286 for (e
= node
->callees
; e
; e
= e
->next_callee
)
2288 if (e
->inline_failed
)
2290 if (e
->count
.ipa ().initialized_p ())
2291 reason
[(int) e
->inline_failed
][0] += e
->count
.ipa ().to_gcov_type ();
2292 reason
[(int) e
->inline_failed
][1] += e
->frequency ();
2293 reason
[(int) e
->inline_failed
][2] ++;
2294 if (DECL_VIRTUAL_P (e
->callee
->decl
)
2295 && e
->count
.ipa ().initialized_p ())
2297 if (e
->indirect_inlining_edge
)
2298 noninlined_virt_indir_cnt
+= e
->count
.ipa ().to_gcov_type ();
2300 noninlined_virt_cnt
+= e
->count
.ipa ().to_gcov_type ();
2302 else if (e
->count
.ipa ().initialized_p ())
2304 if (e
->indirect_inlining_edge
)
2305 noninlined_indir_cnt
+= e
->count
.ipa ().to_gcov_type ();
2307 noninlined_cnt
+= e
->count
.ipa ().to_gcov_type ();
2310 else if (e
->count
.ipa ().initialized_p ())
2314 if (DECL_VIRTUAL_P (e
->callee
->decl
))
2315 inlined_speculative_ply
+= e
->count
.ipa ().to_gcov_type ();
2317 inlined_speculative
+= e
->count
.ipa ().to_gcov_type ();
2319 else if (DECL_VIRTUAL_P (e
->callee
->decl
))
2321 if (e
->indirect_inlining_edge
)
2322 inlined_virt_indir_cnt
+= e
->count
.ipa ().to_gcov_type ();
2324 inlined_virt_cnt
+= e
->count
.ipa ().to_gcov_type ();
2328 if (e
->indirect_inlining_edge
)
2329 inlined_indir_cnt
+= e
->count
.ipa ().to_gcov_type ();
2331 inlined_cnt
+= e
->count
.ipa ().to_gcov_type ();
2335 for (e
= node
->indirect_calls
; e
; e
= e
->next_callee
)
2336 if (e
->indirect_info
->polymorphic
2337 & e
->count
.ipa ().initialized_p ())
2338 indirect_poly_cnt
+= e
->count
.ipa ().to_gcov_type ();
2339 else if (e
->count
.ipa ().initialized_p ())
2340 indirect_cnt
+= e
->count
.ipa ().to_gcov_type ();
2342 if (max_count
.initialized_p ())
2345 "Inlined %" PRId64
" + speculative "
2346 "%" PRId64
" + speculative polymorphic "
2347 "%" PRId64
" + previously indirect "
2348 "%" PRId64
" + virtual "
2349 "%" PRId64
" + virtual and previously indirect "
2350 "%" PRId64
"\n" "Not inlined "
2351 "%" PRId64
" + previously indirect "
2352 "%" PRId64
" + virtual "
2353 "%" PRId64
" + virtual and previously indirect "
2354 "%" PRId64
" + stil indirect "
2355 "%" PRId64
" + still indirect polymorphic "
2356 "%" PRId64
"\n", inlined_cnt
,
2357 inlined_speculative
, inlined_speculative_ply
,
2358 inlined_indir_cnt
, inlined_virt_cnt
, inlined_virt_indir_cnt
,
2359 noninlined_cnt
, noninlined_indir_cnt
, noninlined_virt_cnt
,
2360 noninlined_virt_indir_cnt
, indirect_cnt
, indirect_poly_cnt
);
2361 fprintf (dump_file
, "Removed speculations ");
2362 spec_rem
.dump (dump_file
);
2363 fprintf (dump_file
, "\n");
2365 dump_overall_stats ();
2366 fprintf (dump_file
, "\nWhy inlining failed?\n");
2367 for (i
= 0; i
< CIF_N_REASONS
; i
++)
2369 fprintf (dump_file
, "%-50s: %8i calls, %8i freq, %" PRId64
" count\n",
2370 cgraph_inline_failed_string ((cgraph_inline_failed_t
) i
),
2371 (int) reason
[i
][2], (int) reason
[i
][1], reason
[i
][0]);
2374 /* Decide on the inlining. We do so in the topological order to avoid
2375 expenses on updating data structures. */
2380 struct cgraph_node
*node
;
2382 struct cgraph_node
**order
;
2385 bool remove_functions
= false;
2387 percent_rec
= (sreal
) 1 / (sreal
) 100;
2389 order
= XCNEWVEC (struct cgraph_node
*, symtab
->cgraph_count
);
2392 ipa_dump_fn_summaries (dump_file
);
2394 nnodes
= ipa_reverse_postorder (order
);
2395 spec_rem
= profile_count::zero ();
2397 FOR_EACH_FUNCTION (node
)
2401 /* Recompute the default reasons for inlining because they may have
2402 changed during merging. */
2405 for (cgraph_edge
*e
= node
->callees
; e
; e
= e
->next_callee
)
2407 gcc_assert (e
->inline_failed
);
2408 initialize_inline_failed (e
);
2410 for (cgraph_edge
*e
= node
->indirect_calls
; e
; e
= e
->next_callee
)
2411 initialize_inline_failed (e
);
2416 fprintf (dump_file
, "\nFlattening functions:\n");
2418 /* In the first pass handle functions to be flattened. Do this with
2419 a priority so none of our later choices will make this impossible. */
2420 for (i
= nnodes
- 1; i
>= 0; i
--)
2424 /* Handle nodes to be flattened.
2425 Ideally when processing callees we stop inlining at the
2426 entry of cycles, possibly cloning that entry point and
2427 try to flatten itself turning it into a self-recursive
2429 if (lookup_attribute ("flatten",
2430 DECL_ATTRIBUTES (node
->decl
)) != NULL
)
2434 "Flattening %s\n", node
->name ());
2435 flatten_function (node
, false);
2439 dump_overall_stats ();
2441 inline_small_functions ();
2443 gcc_assert (symtab
->state
== IPA_SSA
);
2444 symtab
->state
= IPA_SSA_AFTER_INLINING
;
2445 /* Do first after-inlining removal. We want to remove all "stale" extern
2446 inline functions and virtual functions so we really know what is called
2448 symtab
->remove_unreachable_nodes (dump_file
);
2451 /* Inline functions with a property that after inlining into all callers the
2452 code size will shrink because the out-of-line copy is eliminated.
2453 We do this regardless on the callee size as long as function growth limits
2457 "\nDeciding on functions to be inlined into all callers and "
2458 "removing useless speculations:\n");
2460 /* Inlining one function called once has good chance of preventing
2461 inlining other function into the same callee. Ideally we should
2462 work in priority order, but probably inlining hot functions first
2463 is good cut without the extra pain of maintaining the queue.
2465 ??? this is not really fitting the bill perfectly: inlining function
2466 into callee often leads to better optimization of callee due to
2467 increased context for optimization.
2468 For example if main() function calls a function that outputs help
2469 and then function that does the main optmization, we should inline
2470 the second with priority even if both calls are cold by themselves.
2472 We probably want to implement new predicate replacing our use of
2473 maybe_hot_edge interpreted as maybe_hot_edge || callee is known
2475 for (cold
= 0; cold
<= 1; cold
++)
2477 FOR_EACH_DEFINED_FUNCTION (node
)
2479 struct cgraph_edge
*edge
, *next
;
2482 if (!opt_for_fn (node
->decl
, optimize
)
2483 || !opt_for_fn (node
->decl
, flag_inline_functions_called_once
))
2486 for (edge
= node
->callees
; edge
; edge
= next
)
2488 next
= edge
->next_callee
;
2489 if (edge
->speculative
&& !speculation_useful_p (edge
, false))
2491 if (edge
->count
.ipa ().initialized_p ())
2492 spec_rem
+= edge
->count
.ipa ();
2493 edge
->resolve_speculation ();
2495 remove_functions
= true;
2500 struct cgraph_node
*where
= node
->global
.inlined_to
2501 ? node
->global
.inlined_to
: node
;
2502 reset_edge_caches (where
);
2503 ipa_update_overall_fn_summary (where
);
2505 if (want_inline_function_to_all_callers_p (node
, cold
))
2508 node
->call_for_symbol_and_aliases (sum_callers
, &num_calls
,
2510 while (node
->call_for_symbol_and_aliases
2511 (inline_to_all_callers
, &num_calls
, true))
2513 remove_functions
= true;
2518 /* Free ipa-prop structures if they are no longer needed. */
2519 ipa_free_all_structures_after_iinln ();
2524 "\nInlined %i calls, eliminated %i functions\n\n",
2525 ncalls_inlined
, nfunctions_inlined
);
2526 dump_inline_stats ();
2530 ipa_dump_fn_summaries (dump_file
);
2531 return remove_functions
? TODO_remove_functions
: 0;
2534 /* Inline always-inline function calls in NODE. */
2537 inline_always_inline_functions (struct cgraph_node
*node
)
2539 struct cgraph_edge
*e
;
2540 bool inlined
= false;
2542 for (e
= node
->callees
; e
; e
= e
->next_callee
)
2544 struct cgraph_node
*callee
= e
->callee
->ultimate_alias_target ();
2545 if (!DECL_DISREGARD_INLINE_LIMITS (callee
->decl
))
2548 if (e
->recursive_p ())
2551 fprintf (dump_file
, " Not inlining recursive call to %s.\n",
2552 e
->callee
->name ());
2553 e
->inline_failed
= CIF_RECURSIVE_INLINING
;
2557 if (!can_early_inline_edge_p (e
))
2559 /* Set inlined to true if the callee is marked "always_inline" but
2560 is not inlinable. This will allow flagging an error later in
2561 expand_call_inline in tree-inline.c. */
2562 if (lookup_attribute ("always_inline",
2563 DECL_ATTRIBUTES (callee
->decl
)) != NULL
)
2569 fprintf (dump_file
, " Inlining %s into %s (always_inline).\n",
2570 xstrdup_for_dump (e
->callee
->name ()),
2571 xstrdup_for_dump (e
->caller
->name ()));
2572 inline_call (e
, true, NULL
, NULL
, false);
2576 ipa_update_overall_fn_summary (node
);
2581 /* Decide on the inlining. We do so in the topological order to avoid
2582 expenses on updating data structures. */
2585 early_inline_small_functions (struct cgraph_node
*node
)
2587 struct cgraph_edge
*e
;
2588 bool inlined
= false;
2590 for (e
= node
->callees
; e
; e
= e
->next_callee
)
2592 struct cgraph_node
*callee
= e
->callee
->ultimate_alias_target ();
2593 if (!ipa_fn_summaries
->get (callee
)->inlinable
2594 || !e
->inline_failed
)
2597 /* Do not consider functions not declared inline. */
2598 if (!DECL_DECLARED_INLINE_P (callee
->decl
)
2599 && !opt_for_fn (node
->decl
, flag_inline_small_functions
)
2600 && !opt_for_fn (node
->decl
, flag_inline_functions
))
2604 fprintf (dump_file
, "Considering inline candidate %s.\n",
2607 if (!can_early_inline_edge_p (e
))
2610 if (e
->recursive_p ())
2613 fprintf (dump_file
, " Not inlining: recursive call.\n");
2617 if (!want_early_inline_function_p (e
))
2621 fprintf (dump_file
, " Inlining %s into %s.\n",
2622 xstrdup_for_dump (callee
->name ()),
2623 xstrdup_for_dump (e
->caller
->name ()));
2624 inline_call (e
, true, NULL
, NULL
, false);
2629 ipa_update_overall_fn_summary (node
);
2635 early_inliner (function
*fun
)
2637 struct cgraph_node
*node
= cgraph_node::get (current_function_decl
);
2638 struct cgraph_edge
*edge
;
2639 unsigned int todo
= 0;
2641 bool inlined
= false;
2646 /* Do nothing if datastructures for ipa-inliner are already computed. This
2647 happens when some pass decides to construct new function and
2648 cgraph_add_new_function calls lowering passes and early optimization on
2649 it. This may confuse ourself when early inliner decide to inline call to
2650 function clone, because function clones don't have parameter list in
2651 ipa-prop matching their signature. */
2652 if (ipa_node_params_sum
)
2657 node
->remove_all_references ();
2659 /* Rebuild this reference because it dosn't depend on
2660 function's body and it's required to pass cgraph_node
2662 if (node
->instrumented_version
2663 && !node
->instrumentation_clone
)
2664 node
->create_reference (node
->instrumented_version
, IPA_REF_CHKP
, NULL
);
2666 /* Even when not optimizing or not inlining inline always-inline
2668 inlined
= inline_always_inline_functions (node
);
2672 || !flag_early_inlining
2673 /* Never inline regular functions into always-inline functions
2674 during incremental inlining. This sucks as functions calling
2675 always inline functions will get less optimized, but at the
2676 same time inlining of functions calling always inline
2677 function into an always inline function might introduce
2678 cycles of edges to be always inlined in the callgraph.
2680 We might want to be smarter and just avoid this type of inlining. */
2681 || (DECL_DISREGARD_INLINE_LIMITS (node
->decl
)
2682 && lookup_attribute ("always_inline",
2683 DECL_ATTRIBUTES (node
->decl
))))
2685 else if (lookup_attribute ("flatten",
2686 DECL_ATTRIBUTES (node
->decl
)) != NULL
)
2688 /* When the function is marked to be flattened, recursively inline
2692 "Flattening %s\n", node
->name ());
2693 flatten_function (node
, true);
2698 /* If some always_inline functions was inlined, apply the changes.
2699 This way we will not account always inline into growth limits and
2700 moreover we will inline calls from always inlines that we skipped
2701 previously because of conditional above. */
2704 timevar_push (TV_INTEGRATION
);
2705 todo
|= optimize_inline_calls (current_function_decl
);
2706 /* optimize_inline_calls call above might have introduced new
2707 statements that don't have inline parameters computed. */
2708 for (edge
= node
->callees
; edge
; edge
= edge
->next_callee
)
2710 struct ipa_call_summary
*es
= ipa_call_summaries
->get (edge
);
2712 = estimate_num_insns (edge
->call_stmt
, &eni_size_weights
);
2714 = estimate_num_insns (edge
->call_stmt
, &eni_time_weights
);
2716 ipa_update_overall_fn_summary (node
);
2718 timevar_pop (TV_INTEGRATION
);
2720 /* We iterate incremental inlining to get trivial cases of indirect
2722 while (iterations
< PARAM_VALUE (PARAM_EARLY_INLINER_MAX_ITERATIONS
)
2723 && early_inline_small_functions (node
))
2725 timevar_push (TV_INTEGRATION
);
2726 todo
|= optimize_inline_calls (current_function_decl
);
2728 /* Technically we ought to recompute inline parameters so the new
2729 iteration of early inliner works as expected. We however have
2730 values approximately right and thus we only need to update edge
2731 info that might be cleared out for newly discovered edges. */
2732 for (edge
= node
->callees
; edge
; edge
= edge
->next_callee
)
2734 /* We have no summary for new bound store calls yet. */
2735 struct ipa_call_summary
*es
= ipa_call_summaries
->get (edge
);
2737 = estimate_num_insns (edge
->call_stmt
, &eni_size_weights
);
2739 = estimate_num_insns (edge
->call_stmt
, &eni_time_weights
);
2741 if (edge
->callee
->decl
2742 && !gimple_check_call_matching_types (
2743 edge
->call_stmt
, edge
->callee
->decl
, false))
2745 edge
->inline_failed
= CIF_MISMATCHED_ARGUMENTS
;
2746 edge
->call_stmt_cannot_inline_p
= true;
2749 if (iterations
< PARAM_VALUE (PARAM_EARLY_INLINER_MAX_ITERATIONS
) - 1)
2750 ipa_update_overall_fn_summary (node
);
2751 timevar_pop (TV_INTEGRATION
);
2756 fprintf (dump_file
, "Iterations: %i\n", iterations
);
2761 timevar_push (TV_INTEGRATION
);
2762 todo
|= optimize_inline_calls (current_function_decl
);
2763 timevar_pop (TV_INTEGRATION
);
2766 fun
->always_inline_functions_inlined
= true;
2771 /* Do inlining of small functions. Doing so early helps profiling and other
2772 passes to be somewhat more effective and avoids some code duplication in
2773 later real inlining pass for testcases with very many function calls. */
2777 const pass_data pass_data_early_inline
=
2779 GIMPLE_PASS
, /* type */
2780 "einline", /* name */
2781 OPTGROUP_INLINE
, /* optinfo_flags */
2782 TV_EARLY_INLINING
, /* tv_id */
2783 PROP_ssa
, /* properties_required */
2784 0, /* properties_provided */
2785 0, /* properties_destroyed */
2786 0, /* todo_flags_start */
2787 0, /* todo_flags_finish */
2790 class pass_early_inline
: public gimple_opt_pass
2793 pass_early_inline (gcc::context
*ctxt
)
2794 : gimple_opt_pass (pass_data_early_inline
, ctxt
)
2797 /* opt_pass methods: */
2798 virtual unsigned int execute (function
*);
2800 }; // class pass_early_inline
2803 pass_early_inline::execute (function
*fun
)
2805 return early_inliner (fun
);
2811 make_pass_early_inline (gcc::context
*ctxt
)
2813 return new pass_early_inline (ctxt
);
2818 const pass_data pass_data_ipa_inline
=
2820 IPA_PASS
, /* type */
2821 "inline", /* name */
2822 OPTGROUP_INLINE
, /* optinfo_flags */
2823 TV_IPA_INLINING
, /* tv_id */
2824 0, /* properties_required */
2825 0, /* properties_provided */
2826 0, /* properties_destroyed */
2827 0, /* todo_flags_start */
2828 ( TODO_dump_symtab
), /* todo_flags_finish */
2831 class pass_ipa_inline
: public ipa_opt_pass_d
2834 pass_ipa_inline (gcc::context
*ctxt
)
2835 : ipa_opt_pass_d (pass_data_ipa_inline
, ctxt
,
2836 NULL
, /* generate_summary */
2837 NULL
, /* write_summary */
2838 NULL
, /* read_summary */
2839 NULL
, /* write_optimization_summary */
2840 NULL
, /* read_optimization_summary */
2841 NULL
, /* stmt_fixup */
2842 0, /* function_transform_todo_flags_start */
2843 inline_transform
, /* function_transform */
2844 NULL
) /* variable_transform */
2847 /* opt_pass methods: */
2848 virtual unsigned int execute (function
*) { return ipa_inline (); }
2850 }; // class pass_ipa_inline
2855 make_pass_ipa_inline (gcc::context
*ctxt
)
2857 return new pass_ipa_inline (ctxt
);