1 /* Inlining decision heuristics.
2 Copyright (C) 2003-2024 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 cannot 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"
109 #include "symbol-summary.h"
110 #include "tree-vrp.h"
113 #include "ipa-prop.h"
114 #include "ipa-fnsummary.h"
115 #include "ipa-inline.h"
116 #include "ipa-utils.h"
117 #include "auto-profile.h"
118 #include "builtins.h"
119 #include "fibonacci_heap.h"
120 #include "stringpool.h"
123 #include "ipa-strub.h"
125 /* Inliner uses greedy algorithm to inline calls in a priority order.
126 Badness is used as the key in a Fibonacci heap which roughly corresponds
127 to negation of benefit to cost ratios.
128 In case multiple calls has same priority we want to stabilize the outcomes
129 for which we use ids. */
136 : badness (sreal::min ()), uid (0)
139 inline_badness (cgraph_edge
*e
, sreal b
)
140 : badness (b
), uid (e
->get_uid ())
143 bool operator<= (const inline_badness
&other
)
145 if (badness
!= other
.badness
)
146 return badness
<= other
.badness
;
147 return uid
<= other
.uid
;
149 bool operator== (const inline_badness
&other
)
151 return badness
== other
.badness
&& uid
== other
.uid
;
153 bool operator!= (const inline_badness
&other
)
155 return badness
!= other
.badness
|| uid
!= other
.uid
;
157 bool operator< (const inline_badness
&other
)
159 if (badness
!= other
.badness
)
160 return badness
< other
.badness
;
161 return uid
< other
.uid
;
163 bool operator> (const inline_badness
&other
)
165 if (badness
!= other
.badness
)
166 return badness
> other
.badness
;
167 return uid
> other
.uid
;
171 typedef fibonacci_heap
<inline_badness
, cgraph_edge
> edge_heap_t
;
172 typedef fibonacci_node
<inline_badness
, cgraph_edge
> edge_heap_node_t
;
174 /* Statistics we collect about inlining algorithm. */
175 static int overall_size
;
176 static profile_count max_count
;
177 static profile_count spec_rem
;
179 /* Return false when inlining edge E would lead to violating
180 limits on function unit growth or stack usage growth.
182 The relative function body growth limit is present generally
183 to avoid problems with non-linear behavior of the compiler.
184 To allow inlining huge functions into tiny wrapper, the limit
185 is always based on the bigger of the two functions considered.
187 For stack growth limits we always base the growth in stack usage
188 of the callers. We want to prevent applications from segfaulting
189 on stack overflow when functions with huge stack frames gets
193 caller_growth_limits (struct cgraph_edge
*e
)
195 struct cgraph_node
*to
= e
->caller
;
196 struct cgraph_node
*what
= e
->callee
->ultimate_alias_target ();
199 HOST_WIDE_INT stack_size_limit
= 0, inlined_stack
;
200 ipa_size_summary
*outer_info
= ipa_size_summaries
->get (to
);
202 /* Look for function e->caller is inlined to. While doing
203 so work out the largest function body on the way. As
204 described above, we want to base our function growth
205 limits based on that. Not on the self size of the
206 outer function, not on the self size of inline code
207 we immediately inline to. This is the most relaxed
208 interpretation of the rule "do not grow large functions
209 too much in order to prevent compiler from exploding". */
212 ipa_size_summary
*size_info
= ipa_size_summaries
->get (to
);
213 if (limit
< size_info
->self_size
)
214 limit
= size_info
->self_size
;
215 if (stack_size_limit
< size_info
->estimated_self_stack_size
)
216 stack_size_limit
= size_info
->estimated_self_stack_size
;
218 to
= to
->callers
->caller
;
223 ipa_fn_summary
*what_info
= ipa_fn_summaries
->get (what
);
224 ipa_size_summary
*what_size_info
= ipa_size_summaries
->get (what
);
226 if (limit
< what_size_info
->self_size
)
227 limit
= what_size_info
->self_size
;
229 limit
+= limit
* opt_for_fn (to
->decl
, param_large_function_growth
) / 100;
231 /* Check the size after inlining against the function limits. But allow
232 the function to shrink if it went over the limits by forced inlining. */
233 newsize
= estimate_size_after_inlining (to
, e
);
234 if (newsize
>= ipa_size_summaries
->get (what
)->size
235 && newsize
> opt_for_fn (to
->decl
, param_large_function_insns
)
238 e
->inline_failed
= CIF_LARGE_FUNCTION_GROWTH_LIMIT
;
242 if (!what_info
->estimated_stack_size
)
245 /* FIXME: Stack size limit often prevents inlining in Fortran programs
246 due to large i/o datastructures used by the Fortran front-end.
247 We ought to ignore this limit when we know that the edge is executed
248 on every invocation of the caller (i.e. its call statement dominates
249 exit block). We do not track this information, yet. */
250 stack_size_limit
+= ((gcov_type
)stack_size_limit
251 * opt_for_fn (to
->decl
, param_stack_frame_growth
)
254 inlined_stack
= (ipa_get_stack_frame_offset (to
)
255 + outer_info
->estimated_self_stack_size
256 + what_info
->estimated_stack_size
);
257 /* Check new stack consumption with stack consumption at the place
259 if (inlined_stack
> stack_size_limit
260 /* If function already has large stack usage from sibling
261 inline call, we can inline, too.
262 This bit overoptimistically assume that we are good at stack
264 && inlined_stack
> ipa_fn_summaries
->get (to
)->estimated_stack_size
265 && inlined_stack
> opt_for_fn (to
->decl
, param_large_stack_frame
))
267 e
->inline_failed
= CIF_LARGE_STACK_FRAME_GROWTH_LIMIT
;
273 /* Dump info about why inlining has failed. */
276 report_inline_failed_reason (struct cgraph_edge
*e
)
278 if (dump_enabled_p ())
280 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, e
->call_stmt
,
281 " not inlinable: %C -> %C, %s\n",
282 e
->caller
, e
->callee
,
283 cgraph_inline_failed_string (e
->inline_failed
));
284 if ((e
->inline_failed
== CIF_TARGET_OPTION_MISMATCH
285 || e
->inline_failed
== CIF_OPTIMIZATION_MISMATCH
)
286 && e
->caller
->lto_file_data
287 && e
->callee
->ultimate_alias_target ()->lto_file_data
)
289 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, e
->call_stmt
,
290 " LTO objects: %s, %s\n",
291 e
->caller
->lto_file_data
->file_name
,
292 e
->callee
->ultimate_alias_target ()->lto_file_data
->file_name
);
294 if (e
->inline_failed
== CIF_TARGET_OPTION_MISMATCH
)
296 cl_target_option_print_diff
297 (dump_file
, 2, target_opts_for_fn (e
->caller
->decl
),
298 target_opts_for_fn (e
->callee
->ultimate_alias_target ()->decl
));
299 if (e
->inline_failed
== CIF_OPTIMIZATION_MISMATCH
)
301 cl_optimization_print_diff
302 (dump_file
, 2, opts_for_fn (e
->caller
->decl
),
303 opts_for_fn (e
->callee
->ultimate_alias_target ()->decl
));
307 /* Decide whether sanitizer-related attributes allow inlining. */
310 sanitize_attrs_match_for_inline_p (const_tree caller
, const_tree callee
)
312 if (!caller
|| !callee
)
315 /* Follow clang and allow inlining for always_inline functions. */
316 if (lookup_attribute ("always_inline", DECL_ATTRIBUTES (callee
)))
319 const sanitize_code codes
[] =
324 SANITIZE_UNDEFINED_NONDEFAULT
,
325 SANITIZE_POINTER_COMPARE
,
326 SANITIZE_POINTER_SUBTRACT
329 for (unsigned i
= 0; i
< ARRAY_SIZE (codes
); i
++)
330 if (sanitize_flags_p (codes
[i
], caller
)
331 != sanitize_flags_p (codes
[i
], callee
))
334 if (sanitize_coverage_p (caller
) != sanitize_coverage_p (callee
))
340 /* Used for flags where it is safe to inline when caller's value is
341 grater than callee's. */
342 #define check_maybe_up(flag) \
343 (opts_for_fn (caller->decl)->x_##flag \
344 != opts_for_fn (callee->decl)->x_##flag \
346 || opts_for_fn (caller->decl)->x_##flag \
347 < opts_for_fn (callee->decl)->x_##flag))
348 /* Used for flags where it is safe to inline when caller's value is
349 smaller than callee's. */
350 #define check_maybe_down(flag) \
351 (opts_for_fn (caller->decl)->x_##flag \
352 != opts_for_fn (callee->decl)->x_##flag \
354 || opts_for_fn (caller->decl)->x_##flag \
355 > opts_for_fn (callee->decl)->x_##flag))
356 /* Used for flags where exact match is needed for correctness. */
357 #define check_match(flag) \
358 (opts_for_fn (caller->decl)->x_##flag \
359 != opts_for_fn (callee->decl)->x_##flag)
361 /* Decide if we can inline the edge and possibly update
362 inline_failed reason.
363 We check whether inlining is possible at all and whether
364 caller growth limits allow doing so.
366 if REPORT is true, output reason to the dump file. */
369 can_inline_edge_p (struct cgraph_edge
*e
, bool report
,
372 gcc_checking_assert (e
->inline_failed
);
374 if (cgraph_inline_failed_type (e
->inline_failed
) == CIF_FINAL_ERROR
)
377 report_inline_failed_reason (e
);
381 bool inlinable
= true;
382 enum availability avail
;
383 cgraph_node
*caller
= (e
->caller
->inlined_to
384 ? e
->caller
->inlined_to
: e
->caller
);
385 cgraph_node
*callee
= e
->callee
->ultimate_alias_target (&avail
, caller
);
387 if (!callee
->definition
)
389 e
->inline_failed
= CIF_BODY_NOT_AVAILABLE
;
392 if (!early
&& (!opt_for_fn (callee
->decl
, optimize
)
393 || !opt_for_fn (caller
->decl
, optimize
)))
395 e
->inline_failed
= CIF_FUNCTION_NOT_OPTIMIZED
;
398 else if (callee
->calls_comdat_local
)
400 e
->inline_failed
= CIF_USES_COMDAT_LOCAL
;
403 else if (avail
<= AVAIL_INTERPOSABLE
)
405 e
->inline_failed
= CIF_OVERWRITABLE
;
408 /* All edges with call_stmt_cannot_inline_p should have inline_failed
409 initialized to one of FINAL_ERROR reasons. */
410 else if (e
->call_stmt_cannot_inline_p
)
412 /* Don't inline if the functions have different EH personalities. */
413 else if (DECL_FUNCTION_PERSONALITY (caller
->decl
)
414 && DECL_FUNCTION_PERSONALITY (callee
->decl
)
415 && (DECL_FUNCTION_PERSONALITY (caller
->decl
)
416 != DECL_FUNCTION_PERSONALITY (callee
->decl
)))
418 e
->inline_failed
= CIF_EH_PERSONALITY
;
421 /* TM pure functions should not be inlined into non-TM_pure
423 else if (is_tm_pure (callee
->decl
) && !is_tm_pure (caller
->decl
))
425 e
->inline_failed
= CIF_UNSPECIFIED
;
428 /* Check compatibility of target optimization options. */
429 else if (!targetm
.target_option
.can_inline_p (caller
->decl
,
432 e
->inline_failed
= CIF_TARGET_OPTION_MISMATCH
;
435 else if (ipa_fn_summaries
->get (callee
) == NULL
436 || !ipa_fn_summaries
->get (callee
)->inlinable
)
438 e
->inline_failed
= CIF_FUNCTION_NOT_INLINABLE
;
441 /* Don't inline a function with mismatched sanitization attributes. */
442 else if (!sanitize_attrs_match_for_inline_p (caller
->decl
, callee
->decl
))
444 e
->inline_failed
= CIF_SANITIZE_ATTRIBUTE_MISMATCH
;
448 if (inlinable
&& !strub_inlinable_to_p (callee
, caller
))
450 e
->inline_failed
= CIF_UNSPECIFIED
;
453 if (!inlinable
&& report
)
454 report_inline_failed_reason (e
);
458 /* Return inlining_insns_single limit for function N. If HINT or HINT2 is true
459 scale up the bound. */
462 inline_insns_single (cgraph_node
*n
, bool hint
, bool hint2
)
466 int64_t spd
= opt_for_fn (n
->decl
, param_inline_heuristics_hint_percent
);
470 return opt_for_fn (n
->decl
, param_max_inline_insns_single
) * spd
/ 100;
473 return opt_for_fn (n
->decl
, param_max_inline_insns_single
)
474 * opt_for_fn (n
->decl
, param_inline_heuristics_hint_percent
) / 100;
475 return opt_for_fn (n
->decl
, param_max_inline_insns_single
);
478 /* Return inlining_insns_auto limit for function N. If HINT or HINT2 is true
479 scale up the bound. */
482 inline_insns_auto (cgraph_node
*n
, bool hint
, bool hint2
)
484 int max_inline_insns_auto
= opt_for_fn (n
->decl
, param_max_inline_insns_auto
);
487 int64_t spd
= opt_for_fn (n
->decl
, param_inline_heuristics_hint_percent
);
491 return max_inline_insns_auto
* spd
/ 100;
494 return max_inline_insns_auto
495 * opt_for_fn (n
->decl
, param_inline_heuristics_hint_percent
) / 100;
496 return max_inline_insns_auto
;
499 /* Decide if we can inline the edge and possibly update
500 inline_failed reason.
501 We check whether inlining is possible at all and whether
502 caller growth limits allow doing so.
504 if REPORT is true, output reason to the dump file.
506 if DISREGARD_LIMITS is true, ignore size limits. */
509 can_inline_edge_by_limits_p (struct cgraph_edge
*e
, bool report
,
510 bool disregard_limits
= false, bool early
= false)
512 gcc_checking_assert (e
->inline_failed
);
514 if (cgraph_inline_failed_type (e
->inline_failed
) == CIF_FINAL_ERROR
)
517 report_inline_failed_reason (e
);
521 bool inlinable
= true;
522 enum availability avail
;
523 cgraph_node
*caller
= (e
->caller
->inlined_to
524 ? e
->caller
->inlined_to
: e
->caller
);
525 cgraph_node
*callee
= e
->callee
->ultimate_alias_target (&avail
, caller
);
526 tree caller_tree
= DECL_FUNCTION_SPECIFIC_OPTIMIZATION (caller
->decl
);
528 = callee
? DECL_FUNCTION_SPECIFIC_OPTIMIZATION (callee
->decl
) : NULL
;
529 /* Check if caller growth allows the inlining. */
530 if (!DECL_DISREGARD_INLINE_LIMITS (callee
->decl
)
532 && !lookup_attribute ("flatten",
533 DECL_ATTRIBUTES (caller
->decl
))
534 && !caller_growth_limits (e
))
536 else if (callee
->externally_visible
537 && !DECL_DISREGARD_INLINE_LIMITS (callee
->decl
)
538 && flag_live_patching
== LIVE_PATCHING_INLINE_ONLY_STATIC
)
540 e
->inline_failed
= CIF_EXTERN_LIVE_ONLY_STATIC
;
543 /* Don't inline a function with a higher optimization level than the
544 caller. FIXME: this is really just tip of iceberg of handling
545 optimization attribute. */
546 else if (caller_tree
!= callee_tree
)
549 (DECL_DISREGARD_INLINE_LIMITS (callee
->decl
)
550 && lookup_attribute ("always_inline",
551 DECL_ATTRIBUTES (callee
->decl
)));
552 ipa_fn_summary
*caller_info
= ipa_fn_summaries
->get (caller
);
553 ipa_fn_summary
*callee_info
= ipa_fn_summaries
->get (callee
);
555 /* Until GCC 4.9 we did not check the semantics-altering flags
556 below and inlined across optimization boundaries.
557 Enabling checks below breaks several packages by refusing
558 to inline library always_inline functions. See PR65873.
559 Disable the check for early inlining for now until better solution
561 if (always_inline
&& early
)
563 /* There are some options that change IL semantics which means
564 we cannot inline in these cases for correctness reason.
565 Not even for always_inline declared functions. */
566 else if (check_match (flag_wrapv
)
567 || check_match (flag_trapv
)
568 || check_match (flag_pcc_struct_return
)
569 || check_maybe_down (optimize_debug
)
570 /* When caller or callee does FP math, be sure FP codegen flags
572 || ((caller_info
->fp_expressions
&& callee_info
->fp_expressions
)
573 && (check_maybe_up (flag_rounding_math
)
574 || check_maybe_up (flag_trapping_math
)
575 || check_maybe_down (flag_unsafe_math_optimizations
)
576 || check_maybe_down (flag_finite_math_only
)
577 || check_maybe_up (flag_signaling_nans
)
578 || check_maybe_down (flag_cx_limited_range
)
579 || check_maybe_up (flag_signed_zeros
)
580 || check_maybe_down (flag_associative_math
)
581 || check_maybe_down (flag_reciprocal_math
)
582 || check_maybe_down (flag_fp_int_builtin_inexact
)
583 /* Strictly speaking only when the callee contains function
584 calls that may end up setting errno. */
585 || check_maybe_up (flag_errno_math
)))
586 /* We do not want to make code compiled with exceptions to be
587 brought into a non-EH function unless we know that the callee
589 This is tracked by DECL_FUNCTION_PERSONALITY. */
590 || (check_maybe_up (flag_non_call_exceptions
)
591 && DECL_FUNCTION_PERSONALITY (callee
->decl
))
592 || (check_maybe_up (flag_exceptions
)
593 && DECL_FUNCTION_PERSONALITY (callee
->decl
))
594 /* When devirtualization is disabled for callee, it is not safe
595 to inline it as we possibly mangled the type info.
596 Allow early inlining of always inlines. */
597 || (!early
&& check_maybe_down (flag_devirtualize
)))
599 e
->inline_failed
= CIF_OPTIMIZATION_MISMATCH
;
602 /* gcc.dg/pr43564.c. Apply user-forced inline even at -O0. */
603 else if (always_inline
)
605 /* When user added an attribute to the callee honor it. */
606 else if (lookup_attribute ("optimize", DECL_ATTRIBUTES (callee
->decl
))
607 && opts_for_fn (caller
->decl
) != opts_for_fn (callee
->decl
))
609 e
->inline_failed
= CIF_OPTIMIZATION_MISMATCH
;
612 /* If explicit optimize attribute are not used, the mismatch is caused
613 by different command line options used to build different units.
614 Do not care about COMDAT functions - those are intended to be
615 optimized with the optimization flags of module they are used in.
616 Also do not care about mixing up size/speed optimization when
617 DECL_DISREGARD_INLINE_LIMITS is set. */
618 else if ((callee
->merged_comdat
619 && !lookup_attribute ("optimize",
620 DECL_ATTRIBUTES (caller
->decl
)))
621 || DECL_DISREGARD_INLINE_LIMITS (callee
->decl
))
623 /* If mismatch is caused by merging two LTO units with different
624 optimization flags we want to be bit nicer. However never inline
625 if one of functions is not optimized at all. */
626 else if (!opt_for_fn (callee
->decl
, optimize
)
627 || !opt_for_fn (caller
->decl
, optimize
))
629 e
->inline_failed
= CIF_OPTIMIZATION_MISMATCH
;
632 /* If callee is optimized for size and caller is not, allow inlining if
633 code shrinks or we are in param_max_inline_insns_single limit and
634 callee is inline (and thus likely an unified comdat).
635 This will allow caller to run faster. */
636 else if (opt_for_fn (callee
->decl
, optimize_size
)
637 > opt_for_fn (caller
->decl
, optimize_size
))
639 int growth
= estimate_edge_growth (e
);
640 if (growth
> opt_for_fn (caller
->decl
, param_max_inline_insns_size
)
641 && (!DECL_DECLARED_INLINE_P (callee
->decl
)
642 && growth
>= MAX (inline_insns_single (caller
, false, false),
643 inline_insns_auto (caller
, false, false))))
645 e
->inline_failed
= CIF_OPTIMIZATION_MISMATCH
;
649 /* If callee is more aggressively optimized for performance than caller,
650 we generally want to inline only cheap (runtime wise) functions. */
651 else if (opt_for_fn (callee
->decl
, optimize_size
)
652 < opt_for_fn (caller
->decl
, optimize_size
)
653 || (opt_for_fn (callee
->decl
, optimize
)
654 > opt_for_fn (caller
->decl
, optimize
)))
656 if (estimate_edge_time (e
)
657 >= 20 + ipa_call_summaries
->get (e
)->call_stmt_time
)
659 e
->inline_failed
= CIF_OPTIMIZATION_MISMATCH
;
666 if (!inlinable
&& report
)
667 report_inline_failed_reason (e
);
672 /* Return true if the edge E is inlinable during early inlining. */
675 can_early_inline_edge_p (struct cgraph_edge
*e
)
677 cgraph_node
*caller
= (e
->caller
->inlined_to
678 ? e
->caller
->inlined_to
: e
->caller
);
679 struct cgraph_node
*callee
= e
->callee
->ultimate_alias_target ();
680 /* Early inliner might get called at WPA stage when IPA pass adds new
681 function. In this case we cannot really do any of early inlining
682 because function bodies are missing. */
683 if (cgraph_inline_failed_type (e
->inline_failed
) == CIF_FINAL_ERROR
)
685 if (!gimple_has_body_p (callee
->decl
))
687 e
->inline_failed
= CIF_BODY_NOT_AVAILABLE
;
690 gcc_assert (gimple_in_ssa_p (DECL_STRUCT_FUNCTION (e
->caller
->decl
))
691 && gimple_in_ssa_p (DECL_STRUCT_FUNCTION (callee
->decl
)));
693 && ((lookup_attribute ("no_profile_instrument_function",
694 DECL_ATTRIBUTES (caller
->decl
)) == NULL_TREE
)
695 != (lookup_attribute ("no_profile_instrument_function",
696 DECL_ATTRIBUTES (callee
->decl
)) == NULL_TREE
)))
699 if (!can_inline_edge_p (e
, true, true)
700 || !can_inline_edge_by_limits_p (e
, true, false, true))
702 /* When inlining regular functions into always-inline functions
703 during early inlining watch for possible inline cycles. */
704 if (DECL_DISREGARD_INLINE_LIMITS (caller
->decl
)
705 && lookup_attribute ("always_inline", DECL_ATTRIBUTES (caller
->decl
))
706 && (!DECL_DISREGARD_INLINE_LIMITS (callee
->decl
)
707 || !lookup_attribute ("always_inline", DECL_ATTRIBUTES (callee
->decl
))))
709 /* If there are indirect calls, inlining may produce direct call.
710 TODO: We may lift this restriction if we avoid errors on formely
711 indirect calls to always_inline functions. Taking address
712 of always_inline function is generally bad idea and should
713 have been declared as undefined, but sadly we allow this. */
714 if (caller
->indirect_calls
|| e
->callee
->indirect_calls
)
716 ipa_fn_summary
*callee_info
= ipa_fn_summaries
->get (callee
);
717 if (callee_info
->safe_to_inline_to_always_inline
)
718 return callee_info
->safe_to_inline_to_always_inline
- 1;
719 for (cgraph_edge
*e2
= callee
->callees
; e2
; e2
= e2
->next_callee
)
721 struct cgraph_node
*callee2
= e2
->callee
->ultimate_alias_target ();
722 /* As early inliner runs in RPO order, we will see uninlined
723 always_inline calls only in the case of cyclic graphs. */
724 if (DECL_DISREGARD_INLINE_LIMITS (callee2
->decl
)
725 || lookup_attribute ("always_inline", DECL_ATTRIBUTES (callee2
->decl
)))
727 callee_info
->safe_to_inline_to_always_inline
= 1;
730 /* With LTO watch for case where function is later replaced
731 by always_inline definition.
732 TODO: We may either stop treating noninlined cross-module always
733 inlines as errors, or we can extend decl merging to produce
734 syntacic alias and honor always inline only in units it has
735 been declared as such. */
736 if (flag_lto
&& callee2
->externally_visible
)
738 callee_info
->safe_to_inline_to_always_inline
= 1;
742 callee_info
->safe_to_inline_to_always_inline
= 2;
748 /* Return number of calls in N. Ignore cheap builtins. */
751 num_calls (struct cgraph_node
*n
)
753 struct cgraph_edge
*e
;
756 for (e
= n
->callees
; e
; e
= e
->next_callee
)
757 if (!is_inexpensive_builtin (e
->callee
->decl
))
763 /* Return true if we are interested in inlining small function. */
766 want_early_inline_function_p (struct cgraph_edge
*e
)
768 bool want_inline
= true;
769 struct cgraph_node
*callee
= e
->callee
->ultimate_alias_target ();
771 if (DECL_DISREGARD_INLINE_LIMITS (callee
->decl
))
773 /* For AutoFDO, we need to make sure that before profile summary, all
774 hot paths' IR look exactly the same as profiled binary. As a result,
775 in einliner, we will disregard size limit and inline those callsites
777 * inlined in the profiled binary, and
778 * the cloned callee has enough samples to be considered "hot". */
779 else if (flag_auto_profile
&& afdo_callsite_hot_enough_for_early_inline (e
))
781 else if (!DECL_DECLARED_INLINE_P (callee
->decl
)
782 && !opt_for_fn (e
->caller
->decl
, flag_inline_small_functions
))
784 e
->inline_failed
= CIF_FUNCTION_NOT_INLINE_CANDIDATE
;
785 report_inline_failed_reason (e
);
790 /* First take care of very large functions. */
791 int min_growth
= estimate_min_edge_growth (e
), growth
= 0;
793 int early_inlining_insns
= param_early_inlining_insns
;
795 if (min_growth
> early_inlining_insns
)
797 if (dump_enabled_p ())
798 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, e
->call_stmt
,
799 " will not early inline: %C->%C, "
800 "call is cold and code would grow "
807 growth
= estimate_edge_growth (e
);
810 if (!want_inline
|| growth
<= param_max_inline_insns_size
)
812 else if (!e
->maybe_hot_p ())
814 if (dump_enabled_p ())
815 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, e
->call_stmt
,
816 " will not early inline: %C->%C, "
817 "call is cold and code would grow by %i\n",
822 else if (growth
> early_inlining_insns
)
824 if (dump_enabled_p ())
825 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, e
->call_stmt
,
826 " will not early inline: %C->%C, "
827 "growth %i exceeds --param early-inlining-insns\n",
828 e
->caller
, callee
, growth
);
831 else if ((n
= num_calls (callee
)) != 0
832 && growth
* (n
+ 1) > early_inlining_insns
)
834 if (dump_enabled_p ())
835 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, e
->call_stmt
,
836 " will not early inline: %C->%C, "
837 "growth %i exceeds --param early-inlining-insns "
838 "divided by number of calls\n",
839 e
->caller
, callee
, growth
);
846 /* Compute time of the edge->caller + edge->callee execution when inlining
850 compute_uninlined_call_time (struct cgraph_edge
*edge
,
851 sreal uninlined_call_time
,
854 cgraph_node
*caller
= (edge
->caller
->inlined_to
855 ? edge
->caller
->inlined_to
859 uninlined_call_time
*= freq
;
861 uninlined_call_time
= uninlined_call_time
>> 11;
863 sreal caller_time
= ipa_fn_summaries
->get (caller
)->time
;
864 return uninlined_call_time
+ caller_time
;
867 /* Same as compute_uinlined_call_time but compute time when inlining
871 compute_inlined_call_time (struct cgraph_edge
*edge
,
875 cgraph_node
*caller
= (edge
->caller
->inlined_to
876 ? edge
->caller
->inlined_to
878 sreal caller_time
= ipa_fn_summaries
->get (caller
)->time
;
885 /* This calculation should match one in ipa-inline-analysis.cc
886 (estimate_edge_size_and_time). */
887 time
-= (sreal
)ipa_call_summaries
->get (edge
)->call_stmt_time
* freq
;
890 time
= ((sreal
) 1) >> 8;
891 gcc_checking_assert (time
>= 0);
895 /* Determine time saved by inlining EDGE of frequency FREQ
896 where callee's runtime w/o inlining is UNINLINED_TYPE
897 and with inlined is INLINED_TYPE. */
900 inlining_speedup (struct cgraph_edge
*edge
,
902 sreal uninlined_time
,
905 sreal speedup
= uninlined_time
- inlined_time
;
906 /* Handling of call_time should match one in ipa-inline-fnsummary.c
907 (estimate_edge_size_and_time). */
908 sreal call_time
= ipa_call_summaries
->get (edge
)->call_stmt_time
;
912 speedup
= (speedup
+ call_time
);
914 speedup
= speedup
* freq
;
917 speedup
= speedup
>> 11;
918 gcc_checking_assert (speedup
>= 0);
922 /* Return true if the speedup for inlining E is bigger than
923 param_inline_min_speedup. */
926 big_speedup_p (struct cgraph_edge
*e
)
929 sreal spec_time
= estimate_edge_time (e
, &unspec_time
);
930 sreal freq
= e
->sreal_frequency ();
931 sreal time
= compute_uninlined_call_time (e
, unspec_time
, freq
);
932 sreal inlined_time
= compute_inlined_call_time (e
, spec_time
, freq
);
933 cgraph_node
*caller
= (e
->caller
->inlined_to
934 ? e
->caller
->inlined_to
936 int limit
= opt_for_fn (caller
->decl
, param_inline_min_speedup
);
938 if ((time
- inlined_time
) * 100 > time
* limit
)
943 /* Return true if we are interested in inlining small function.
944 When REPORT is true, report reason to dump file. */
947 want_inline_small_function_p (struct cgraph_edge
*e
, bool report
)
949 bool want_inline
= true;
950 struct cgraph_node
*callee
= e
->callee
->ultimate_alias_target ();
951 cgraph_node
*to
= (e
->caller
->inlined_to
952 ? e
->caller
->inlined_to
: e
->caller
);
954 /* Allow this function to be called before can_inline_edge_p,
955 since it's usually cheaper. */
956 if (cgraph_inline_failed_type (e
->inline_failed
) == CIF_FINAL_ERROR
)
958 else if (DECL_DISREGARD_INLINE_LIMITS (callee
->decl
))
960 else if (!DECL_DECLARED_INLINE_P (callee
->decl
)
961 && !opt_for_fn (e
->caller
->decl
, flag_inline_small_functions
))
963 e
->inline_failed
= CIF_FUNCTION_NOT_INLINE_CANDIDATE
;
966 /* Do fast and conservative check if the function can be good
968 else if ((!DECL_DECLARED_INLINE_P (callee
->decl
)
969 && (!e
->count
.ipa ().initialized_p () || !e
->maybe_hot_p ()))
970 && ipa_fn_summaries
->get (callee
)->min_size
971 - ipa_call_summaries
->get (e
)->call_stmt_size
972 > inline_insns_auto (e
->caller
, true, true))
974 e
->inline_failed
= CIF_MAX_INLINE_INSNS_AUTO_LIMIT
;
977 else if ((DECL_DECLARED_INLINE_P (callee
->decl
)
978 || e
->count
.ipa ().nonzero_p ())
979 && ipa_fn_summaries
->get (callee
)->min_size
980 - ipa_call_summaries
->get (e
)->call_stmt_size
981 > inline_insns_single (e
->caller
, true, true))
983 e
->inline_failed
= (DECL_DECLARED_INLINE_P (callee
->decl
)
984 ? CIF_MAX_INLINE_INSNS_SINGLE_LIMIT
985 : CIF_MAX_INLINE_INSNS_AUTO_LIMIT
);
990 int growth
= estimate_edge_growth (e
);
991 ipa_hints hints
= estimate_edge_hints (e
);
992 /* We have two independent groups of hints. If one matches in each
993 of groups the limits are inreased. If both groups matches, limit
994 is increased even more. */
995 bool apply_hints
= (hints
& (INLINE_HINT_indirect_call
996 | INLINE_HINT_known_hot
997 | INLINE_HINT_loop_iterations
998 | INLINE_HINT_loop_stride
));
999 bool apply_hints2
= (hints
& INLINE_HINT_builtin_constant_p
);
1001 if (growth
<= opt_for_fn (to
->decl
,
1002 param_max_inline_insns_size
))
1004 /* Apply param_max_inline_insns_single limit. Do not do so when
1005 hints suggests that inlining given function is very profitable.
1006 Avoid computation of big_speedup_p when not necessary to change
1007 outcome of decision. */
1008 else if (DECL_DECLARED_INLINE_P (callee
->decl
)
1009 && growth
>= inline_insns_single (e
->caller
, apply_hints
,
1011 && (apply_hints
|| apply_hints2
1012 || growth
>= inline_insns_single (e
->caller
, true,
1014 || !big_speedup_p (e
)))
1016 e
->inline_failed
= CIF_MAX_INLINE_INSNS_SINGLE_LIMIT
;
1017 want_inline
= false;
1019 else if (!DECL_DECLARED_INLINE_P (callee
->decl
)
1020 && !opt_for_fn (e
->caller
->decl
, flag_inline_functions
)
1021 && growth
>= opt_for_fn (to
->decl
,
1022 param_max_inline_insns_small
))
1024 /* growth_positive_p is expensive, always test it last. */
1025 if (growth
>= inline_insns_single (e
->caller
, false, false)
1026 || growth_positive_p (callee
, e
, growth
))
1028 e
->inline_failed
= CIF_NOT_DECLARED_INLINED
;
1029 want_inline
= false;
1032 /* Apply param_max_inline_insns_auto limit for functions not declared
1033 inline. Bypass the limit when speedup seems big. */
1034 else if (!DECL_DECLARED_INLINE_P (callee
->decl
)
1035 && growth
>= inline_insns_auto (e
->caller
, apply_hints
,
1037 && (apply_hints
|| apply_hints2
1038 || growth
>= inline_insns_auto (e
->caller
, true,
1040 || !big_speedup_p (e
)))
1042 /* growth_positive_p is expensive, always test it last. */
1043 if (growth
>= inline_insns_single (e
->caller
, false, false)
1044 || growth_positive_p (callee
, e
, growth
))
1046 e
->inline_failed
= CIF_MAX_INLINE_INSNS_AUTO_LIMIT
;
1047 want_inline
= false;
1050 /* If call is cold, do not inline when function body would grow. */
1051 else if (!e
->maybe_hot_p ()
1052 && (growth
>= inline_insns_single (e
->caller
, false, false)
1053 || growth_positive_p (callee
, e
, growth
)))
1055 e
->inline_failed
= CIF_UNLIKELY_CALL
;
1056 want_inline
= false;
1059 if (!want_inline
&& report
)
1060 report_inline_failed_reason (e
);
1064 /* EDGE is self recursive edge.
1065 We handle two cases - when function A is inlining into itself
1066 or when function A is being inlined into another inliner copy of function
1067 A within function B.
1069 In first case OUTER_NODE points to the toplevel copy of A, while
1070 in the second case OUTER_NODE points to the outermost copy of A in B.
1072 In both cases we want to be extra selective since
1073 inlining the call will just introduce new recursive calls to appear. */
1076 want_inline_self_recursive_call_p (struct cgraph_edge
*edge
,
1077 struct cgraph_node
*outer_node
,
1081 char const *reason
= NULL
;
1082 bool want_inline
= true;
1083 sreal caller_freq
= 1;
1084 int max_depth
= opt_for_fn (outer_node
->decl
,
1085 param_max_inline_recursive_depth_auto
);
1087 if (DECL_DECLARED_INLINE_P (edge
->caller
->decl
))
1088 max_depth
= opt_for_fn (outer_node
->decl
,
1089 param_max_inline_recursive_depth
);
1091 if (!edge
->maybe_hot_p ())
1093 reason
= "recursive call is cold";
1094 want_inline
= false;
1096 else if (depth
> max_depth
)
1098 reason
= "--param max-inline-recursive-depth exceeded.";
1099 want_inline
= false;
1101 else if (outer_node
->inlined_to
1102 && (caller_freq
= outer_node
->callers
->sreal_frequency ()) == 0)
1104 reason
= "caller frequency is 0";
1105 want_inline
= false;
1110 /* Inlining of self recursive function into copy of itself within other
1111 function is transformation similar to loop peeling.
1113 Peeling is profitable if we can inline enough copies to make probability
1114 of actual call to the self recursive function very small. Be sure that
1115 the probability of recursion is small.
1117 We ensure that the frequency of recursing is at most 1 - (1/max_depth).
1118 This way the expected number of recursion is at most max_depth. */
1121 sreal max_prob
= (sreal
)1 - ((sreal
)1 / (sreal
)max_depth
);
1123 for (i
= 1; i
< depth
; i
++)
1124 max_prob
= max_prob
* max_prob
;
1125 if (edge
->sreal_frequency () >= max_prob
* caller_freq
)
1127 reason
= "frequency of recursive call is too large";
1128 want_inline
= false;
1131 /* Recursive inlining, i.e. equivalent of unrolling, is profitable if
1132 recursion depth is large. We reduce function call overhead and increase
1133 chances that things fit in hardware return predictor.
1135 Recursive inlining might however increase cost of stack frame setup
1136 actually slowing down functions whose recursion tree is wide rather than
1139 Deciding reliably on when to do recursive inlining without profile feedback
1140 is tricky. For now we disable recursive inlining when probability of self
1143 Recursive inlining of self recursive call within loop also results in
1144 large loop depths that generally optimize badly. We may want to throttle
1145 down inlining in those cases. In particular this seems to happen in one
1146 of libstdc++ rb tree methods. */
1149 if (edge
->sreal_frequency () * 100
1151 * opt_for_fn (outer_node
->decl
,
1152 param_min_inline_recursive_probability
))
1154 reason
= "frequency of recursive call is too small";
1155 want_inline
= false;
1158 if (!want_inline
&& dump_enabled_p ())
1159 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, edge
->call_stmt
,
1160 " not inlining recursively: %s\n", reason
);
1164 /* Return true when NODE has uninlinable caller;
1165 set HAS_HOT_CALL if it has hot call.
1166 Worker for cgraph_for_node_and_aliases. */
1169 check_callers (struct cgraph_node
*node
, void *has_hot_call
)
1171 struct cgraph_edge
*e
;
1172 for (e
= node
->callers
; e
; e
= e
->next_caller
)
1174 if (!opt_for_fn (e
->caller
->decl
, flag_inline_functions_called_once
)
1175 || !opt_for_fn (e
->caller
->decl
, optimize
))
1177 if (!can_inline_edge_p (e
, true))
1179 if (e
->recursive_p ())
1181 if (!can_inline_edge_by_limits_p (e
, true))
1183 /* Inlining large functions to large loop depth is often harmful because
1184 of register pressure it implies. */
1185 if ((int)ipa_call_summaries
->get (e
)->loop_depth
1186 > param_inline_functions_called_once_loop_depth
)
1188 /* Do not produce gigantic functions. */
1189 if (estimate_size_after_inlining (e
->caller
->inlined_to
?
1190 e
->caller
->inlined_to
: e
->caller
, e
)
1191 > param_inline_functions_called_once_insns
)
1193 if (!(*(bool *)has_hot_call
) && e
->maybe_hot_p ())
1194 *(bool *)has_hot_call
= true;
1199 /* If NODE has a caller, return true. */
1202 has_caller_p (struct cgraph_node
*node
, void *data ATTRIBUTE_UNUSED
)
1209 /* Decide if inlining NODE would reduce unit size by eliminating
1210 the offline copy of function.
1211 When COLD is true the cold calls are considered, too. */
1214 want_inline_function_to_all_callers_p (struct cgraph_node
*node
, bool cold
)
1216 bool has_hot_call
= false;
1218 /* Aliases gets inlined along with the function they alias. */
1221 /* Already inlined? */
1222 if (node
->inlined_to
)
1224 /* Does it have callers? */
1225 if (!node
->call_for_symbol_and_aliases (has_caller_p
, NULL
, true))
1227 /* Inlining into all callers would increase size? */
1228 if (growth_positive_p (node
, NULL
, INT_MIN
) > 0)
1230 /* All inlines must be possible. */
1231 if (node
->call_for_symbol_and_aliases (check_callers
, &has_hot_call
,
1234 if (!cold
&& !has_hot_call
)
1239 /* Return true if WHERE of SIZE is a possible candidate for wrapper heuristics
1240 in estimate_edge_badness. */
1243 wrapper_heuristics_may_apply (struct cgraph_node
*where
, int size
)
1245 return size
< (DECL_DECLARED_INLINE_P (where
->decl
)
1246 ? inline_insns_single (where
, false, false)
1247 : inline_insns_auto (where
, false, false));
1250 /* A cost model driving the inlining heuristics in a way so the edges with
1251 smallest badness are inlined first. After each inlining is performed
1252 the costs of all caller edges of nodes affected are recomputed so the
1253 metrics may accurately depend on values such as number of inlinable callers
1254 of the function or function body size. */
1257 edge_badness (struct cgraph_edge
*edge
, bool dump
)
1261 sreal edge_time
, unspec_edge_time
;
1262 struct cgraph_node
*callee
= edge
->callee
->ultimate_alias_target ();
1263 class ipa_fn_summary
*callee_info
= ipa_fn_summaries
->get (callee
);
1265 cgraph_node
*caller
= (edge
->caller
->inlined_to
1266 ? edge
->caller
->inlined_to
1269 growth
= estimate_edge_growth (edge
);
1270 edge_time
= estimate_edge_time (edge
, &unspec_edge_time
);
1271 hints
= estimate_edge_hints (edge
);
1272 gcc_checking_assert (edge_time
>= 0);
1273 /* Check that inlined time is better, but tolerate some roundoff issues.
1274 FIXME: When callee profile drops to 0 we account calls more. This
1275 should be fixed by never doing that. */
1276 gcc_checking_assert ((edge_time
* 100
1277 - callee_info
->time
* 101).to_int () <= 0
1278 || callee
->count
.ipa ().initialized_p ());
1279 gcc_checking_assert (growth
<= ipa_size_summaries
->get (callee
)->size
);
1283 fprintf (dump_file
, " Badness calculation for %s -> %s\n",
1284 edge
->caller
->dump_name (),
1285 edge
->callee
->dump_name ());
1286 fprintf (dump_file
, " size growth %i, time %f unspec %f ",
1288 edge_time
.to_double (),
1289 unspec_edge_time
.to_double ());
1290 ipa_dump_hints (dump_file
, hints
);
1291 if (big_speedup_p (edge
))
1292 fprintf (dump_file
, " big_speedup");
1293 fprintf (dump_file
, "\n");
1296 /* Always prefer inlining saving code size. */
1299 badness
= (sreal
) (-SREAL_MIN_SIG
+ growth
) << (SREAL_MAX_EXP
/ 256);
1301 fprintf (dump_file
, " %f: Growth %d <= 0\n", badness
.to_double (),
1304 /* Inlining into EXTERNAL functions is not going to change anything unless
1305 they are themselves inlined. */
1306 else if (DECL_EXTERNAL (caller
->decl
))
1309 fprintf (dump_file
, " max: function is external\n");
1310 return sreal::max ();
1312 /* When profile is available. Compute badness as:
1314 time_saved * caller_count
1315 goodness = -------------------------------------------------
1316 growth_of_caller * overall_growth * combined_size
1318 badness = - goodness
1320 Again use negative value to make calls with profile appear hotter
1323 else if (opt_for_fn (caller
->decl
, flag_guess_branch_prob
)
1324 || caller
->count
.ipa ().nonzero_p ())
1326 sreal numerator
, denominator
;
1328 sreal freq
= edge
->sreal_frequency ();
1330 numerator
= inlining_speedup (edge
, freq
, unspec_edge_time
, edge_time
);
1332 numerator
= ((sreal
) 1 >> 8);
1333 if (caller
->count
.ipa ().nonzero_p ())
1334 numerator
*= caller
->count
.ipa ().to_gcov_type ();
1335 else if (caller
->count
.ipa ().initialized_p ())
1336 numerator
= numerator
>> 11;
1337 denominator
= growth
;
1339 overall_growth
= callee_info
->growth
;
1341 /* Look for inliner wrappers of the form:
1347 noninline_callee ();
1349 Without penalizing this case, we usually inline noninline_callee
1350 into the inline_caller because overall_growth is small preventing
1351 further inlining of inline_caller.
1353 Penalize only callgraph edges to functions with small overall
1356 if (growth
> overall_growth
1357 /* ... and having only one caller which is not inlined ... */
1358 && callee_info
->single_caller
1359 && !edge
->caller
->inlined_to
1360 /* ... and edges executed only conditionally ... */
1362 /* ... consider case where callee is not inline but caller is ... */
1363 && ((!DECL_DECLARED_INLINE_P (edge
->callee
->decl
)
1364 && DECL_DECLARED_INLINE_P (caller
->decl
))
1365 /* ... or when early optimizers decided to split and edge
1366 frequency still indicates splitting is a win ... */
1367 || (callee
->split_part
&& !caller
->split_part
1369 < opt_for_fn (caller
->decl
,
1370 param_partial_inlining_entry_probability
)
1371 /* ... and do not overwrite user specified hints. */
1372 && (!DECL_DECLARED_INLINE_P (edge
->callee
->decl
)
1373 || DECL_DECLARED_INLINE_P (caller
->decl
)))))
1375 ipa_fn_summary
*caller_info
= ipa_fn_summaries
->get (caller
);
1376 int caller_growth
= caller_info
->growth
;
1378 /* Only apply the penalty when caller looks like inline candidate,
1379 and it is not called once. */
1380 if (!caller_info
->single_caller
&& overall_growth
< caller_growth
1381 && caller_info
->inlinable
1382 && wrapper_heuristics_may_apply
1383 (caller
, ipa_size_summaries
->get (caller
)->size
))
1387 " Wrapper penalty. Increasing growth %i to %i\n",
1388 overall_growth
, caller_growth
);
1389 overall_growth
= caller_growth
;
1392 if (overall_growth
> 0)
1394 /* Strongly prefer functions with few callers that can be inlined
1395 fully. The square root here leads to smaller binaries at average.
1396 Watch however for extreme cases and return to linear function
1397 when growth is large. */
1398 if (overall_growth
< 256)
1399 overall_growth
*= overall_growth
;
1401 overall_growth
+= 256 * 256 - 256;
1402 denominator
*= overall_growth
;
1404 denominator
*= ipa_size_summaries
->get (caller
)->size
+ growth
;
1406 badness
= - numerator
/ denominator
;
1411 " %f: guessed profile. frequency %f, count %" PRId64
1412 " caller count %" PRId64
1414 " overall growth %i (current) %i (original)"
1415 " %i (compensated)\n",
1416 badness
.to_double (),
1418 edge
->count
.ipa ().initialized_p ()
1419 ? edge
->count
.ipa ().to_gcov_type () : -1,
1420 caller
->count
.ipa ().initialized_p ()
1421 ? caller
->count
.ipa ().to_gcov_type () : -1,
1422 inlining_speedup (edge
, freq
, unspec_edge_time
,
1423 edge_time
).to_double (),
1424 estimate_growth (callee
),
1425 callee_info
->growth
, overall_growth
);
1428 /* When function local profile is not available or it does not give
1429 useful information (i.e. frequency is zero), base the cost on
1430 loop nest and overall size growth, so we optimize for overall number
1431 of functions fully inlined in program. */
1434 int nest
= MIN (ipa_call_summaries
->get (edge
)->loop_depth
, 8);
1437 /* Decrease badness if call is nested. */
1439 badness
= badness
>> nest
;
1441 badness
= badness
<< nest
;
1443 fprintf (dump_file
, " %f: no profile. nest %i\n",
1444 badness
.to_double (), nest
);
1446 gcc_checking_assert (badness
!= 0);
1448 if (edge
->recursive_p ())
1449 badness
= badness
.shift (badness
> 0 ? 4 : -4);
1450 if ((hints
& (INLINE_HINT_indirect_call
1451 | INLINE_HINT_loop_iterations
1452 | INLINE_HINT_loop_stride
))
1453 || callee_info
->growth
<= 0)
1454 badness
= badness
.shift (badness
> 0 ? -2 : 2);
1455 if (hints
& INLINE_HINT_builtin_constant_p
)
1456 badness
= badness
.shift (badness
> 0 ? -4 : 4);
1457 if (hints
& (INLINE_HINT_same_scc
))
1458 badness
= badness
.shift (badness
> 0 ? 3 : -3);
1459 else if (hints
& (INLINE_HINT_in_scc
))
1460 badness
= badness
.shift (badness
> 0 ? 2 : -2);
1461 else if (hints
& (INLINE_HINT_cross_module
))
1462 badness
= badness
.shift (badness
> 0 ? 1 : -1);
1463 if (DECL_DISREGARD_INLINE_LIMITS (callee
->decl
))
1464 badness
= badness
.shift (badness
> 0 ? -4 : 4);
1465 else if ((hints
& INLINE_HINT_declared_inline
))
1466 badness
= badness
.shift (badness
> 0 ? -3 : 3);
1468 fprintf (dump_file
, " Adjusted by hints %f\n", badness
.to_double ());
1472 /* Recompute badness of EDGE and update its key in HEAP if needed. */
1474 update_edge_key (edge_heap_t
*heap
, struct cgraph_edge
*edge
)
1476 sreal badness
= edge_badness (edge
, false);
1479 edge_heap_node_t
*n
= (edge_heap_node_t
*) edge
->aux
;
1480 gcc_checking_assert (n
->get_data () == edge
);
1482 /* fibonacci_heap::replace_key does busy updating of the
1483 heap that is unnecessarily expensive.
1484 We do lazy increases: after extracting minimum if the key
1485 turns out to be out of date, it is re-inserted into heap
1486 with correct value. */
1487 if (badness
< n
->get_key ().badness
)
1489 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1492 " decreasing badness %s -> %s, %f to %f\n",
1493 edge
->caller
->dump_name (),
1494 edge
->callee
->dump_name (),
1495 n
->get_key ().badness
.to_double (),
1496 badness
.to_double ());
1498 inline_badness
b (edge
, badness
);
1499 heap
->decrease_key (n
, b
);
1504 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1507 " enqueuing call %s -> %s, badness %f\n",
1508 edge
->caller
->dump_name (),
1509 edge
->callee
->dump_name (),
1510 badness
.to_double ());
1512 inline_badness
b (edge
, badness
);
1513 edge
->aux
= heap
->insert (b
, edge
);
1518 /* NODE was inlined.
1519 All caller edges needs to be reset because
1520 size estimates change. Similarly callees needs reset
1521 because better context may be known. */
1524 reset_edge_caches (struct cgraph_node
*node
)
1526 struct cgraph_edge
*edge
;
1527 struct cgraph_edge
*e
= node
->callees
;
1528 struct cgraph_node
*where
= node
;
1529 struct ipa_ref
*ref
;
1531 if (where
->inlined_to
)
1532 where
= where
->inlined_to
;
1534 reset_node_cache (where
);
1536 if (edge_growth_cache
!= NULL
)
1537 for (edge
= where
->callers
; edge
; edge
= edge
->next_caller
)
1538 if (edge
->inline_failed
)
1539 edge_growth_cache
->remove (edge
);
1541 FOR_EACH_ALIAS (where
, ref
)
1542 reset_edge_caches (dyn_cast
<cgraph_node
*> (ref
->referring
));
1548 if (!e
->inline_failed
&& e
->callee
->callees
)
1549 e
= e
->callee
->callees
;
1552 if (edge_growth_cache
!= NULL
&& e
->inline_failed
)
1553 edge_growth_cache
->remove (e
);
1560 if (e
->caller
== node
)
1562 e
= e
->caller
->callers
;
1564 while (!e
->next_callee
);
1570 /* Recompute HEAP nodes for each of caller of NODE.
1571 UPDATED_NODES track nodes we already visited, to avoid redundant work.
1572 When CHECK_INLINABLITY_FOR is set, re-check for specified edge that
1573 it is inlinable. Otherwise check all edges. */
1576 update_caller_keys (edge_heap_t
*heap
, struct cgraph_node
*node
,
1577 bitmap updated_nodes
,
1578 struct cgraph_edge
*check_inlinablity_for
)
1580 struct cgraph_edge
*edge
;
1581 struct ipa_ref
*ref
;
1583 if ((!node
->alias
&& !ipa_fn_summaries
->get (node
)->inlinable
)
1584 || node
->inlined_to
)
1586 if (!bitmap_set_bit (updated_nodes
, node
->get_uid ()))
1589 FOR_EACH_ALIAS (node
, ref
)
1591 struct cgraph_node
*alias
= dyn_cast
<cgraph_node
*> (ref
->referring
);
1592 update_caller_keys (heap
, alias
, updated_nodes
, check_inlinablity_for
);
1595 for (edge
= node
->callers
; edge
; edge
= edge
->next_caller
)
1596 if (edge
->inline_failed
)
1598 if (!check_inlinablity_for
1599 || check_inlinablity_for
== edge
)
1601 if (can_inline_edge_p (edge
, false)
1602 && want_inline_small_function_p (edge
, false)
1603 && can_inline_edge_by_limits_p (edge
, false))
1604 update_edge_key (heap
, edge
);
1607 report_inline_failed_reason (edge
);
1608 heap
->delete_node ((edge_heap_node_t
*) edge
->aux
);
1613 update_edge_key (heap
, edge
);
1617 /* Recompute HEAP nodes for each uninlined call in NODE
1618 If UPDATE_SINCE is non-NULL check if edges called within that function
1619 are inlinable (typically UPDATE_SINCE is the inline clone we introduced
1620 where all edges have new context).
1622 This is used when we know that edge badnesses are going only to increase
1623 (we introduced new call site) and thus all we need is to insert newly
1624 created edges into heap. */
1627 update_callee_keys (edge_heap_t
*heap
, struct cgraph_node
*node
,
1628 struct cgraph_node
*update_since
,
1629 bitmap updated_nodes
)
1631 struct cgraph_edge
*e
= node
->callees
;
1632 bool check_inlinability
= update_since
== node
;
1637 if (!e
->inline_failed
&& e
->callee
->callees
)
1639 if (e
->callee
== update_since
)
1640 check_inlinability
= true;
1641 e
= e
->callee
->callees
;
1645 enum availability avail
;
1646 struct cgraph_node
*callee
;
1647 if (!check_inlinability
)
1650 && !bitmap_bit_p (updated_nodes
,
1651 e
->callee
->ultimate_alias_target
1652 (&avail
, e
->caller
)->get_uid ()))
1653 update_edge_key (heap
, e
);
1655 /* We do not reset callee growth cache here. Since we added a new call,
1656 growth should have just increased and consequently badness metric
1657 don't need updating. */
1658 else if (e
->inline_failed
1659 && (callee
= e
->callee
->ultimate_alias_target (&avail
,
1661 && avail
>= AVAIL_AVAILABLE
1662 && ipa_fn_summaries
->get (callee
) != NULL
1663 && ipa_fn_summaries
->get (callee
)->inlinable
1664 && !bitmap_bit_p (updated_nodes
, callee
->get_uid ()))
1666 if (can_inline_edge_p (e
, false)
1667 && want_inline_small_function_p (e
, false)
1668 && can_inline_edge_by_limits_p (e
, false))
1670 gcc_checking_assert (check_inlinability
|| can_inline_edge_p (e
, false));
1671 gcc_checking_assert (check_inlinability
|| e
->aux
);
1672 update_edge_key (heap
, e
);
1676 report_inline_failed_reason (e
);
1677 heap
->delete_node ((edge_heap_node_t
*) e
->aux
);
1681 /* In case we redirected to unreachable node we only need to remove the
1685 heap
->delete_node ((edge_heap_node_t
*) e
->aux
);
1694 if (e
->caller
== node
)
1696 if (e
->caller
== update_since
)
1697 check_inlinability
= false;
1698 e
= e
->caller
->callers
;
1700 while (!e
->next_callee
);
1706 /* Enqueue all recursive calls from NODE into priority queue depending on
1707 how likely we want to recursively inline the call. */
1710 lookup_recursive_calls (struct cgraph_node
*node
, struct cgraph_node
*where
,
1713 struct cgraph_edge
*e
;
1714 enum availability avail
;
1716 for (e
= where
->callees
; e
; e
= e
->next_callee
)
1717 if (e
->callee
== node
1718 || (e
->callee
->ultimate_alias_target (&avail
, e
->caller
) == node
1719 && avail
> AVAIL_INTERPOSABLE
))
1721 inline_badness
b (e
, -e
->sreal_frequency ());
1722 heap
->insert (b
, e
);
1724 for (e
= where
->callees
; e
; e
= e
->next_callee
)
1725 if (!e
->inline_failed
)
1726 lookup_recursive_calls (node
, e
->callee
, heap
);
1729 /* Decide on recursive inlining: in the case function has recursive calls,
1730 inline until body size reaches given argument. If any new indirect edges
1731 are discovered in the process, add them to *NEW_EDGES, unless NEW_EDGES
1735 recursive_inlining (struct cgraph_edge
*edge
,
1736 vec
<cgraph_edge
*> *new_edges
)
1738 cgraph_node
*to
= (edge
->caller
->inlined_to
1739 ? edge
->caller
->inlined_to
: edge
->caller
);
1740 int limit
= opt_for_fn (to
->decl
,
1741 param_max_inline_insns_recursive_auto
);
1742 inline_badness
b (edge
, sreal::min ());
1743 edge_heap_t
heap (b
);
1744 struct cgraph_node
*node
;
1745 struct cgraph_edge
*e
;
1746 struct cgraph_node
*master_clone
= NULL
, *next
;
1750 node
= edge
->caller
;
1751 if (node
->inlined_to
)
1752 node
= node
->inlined_to
;
1754 if (DECL_DECLARED_INLINE_P (node
->decl
))
1755 limit
= opt_for_fn (to
->decl
, param_max_inline_insns_recursive
);
1757 /* Make sure that function is small enough to be considered for inlining. */
1758 if (estimate_size_after_inlining (node
, edge
) >= limit
)
1760 lookup_recursive_calls (node
, node
, &heap
);
1766 " Performing recursive inlining on %s\n", node
->dump_name ());
1768 /* Do the inlining and update list of recursive call during process. */
1769 while (!heap
.empty ())
1771 struct cgraph_edge
*curr
= heap
.extract_min ();
1772 struct cgraph_node
*cnode
, *dest
= curr
->callee
;
1774 if (!can_inline_edge_p (curr
, true)
1775 || !can_inline_edge_by_limits_p (curr
, true))
1778 /* MASTER_CLONE is produced in the case we already started modified
1779 the function. Be sure to redirect edge to the original body before
1780 estimating growths otherwise we will be seeing growths after inlining
1781 the already modified body. */
1784 curr
->redirect_callee (master_clone
);
1785 if (edge_growth_cache
!= NULL
)
1786 edge_growth_cache
->remove (curr
);
1789 if (estimate_size_after_inlining (node
, curr
) > limit
)
1791 curr
->redirect_callee (dest
);
1792 if (edge_growth_cache
!= NULL
)
1793 edge_growth_cache
->remove (curr
);
1798 for (cnode
= curr
->caller
;
1799 cnode
->inlined_to
; cnode
= cnode
->callers
->caller
)
1801 == curr
->callee
->ultimate_alias_target ()->decl
)
1804 if (!want_inline_self_recursive_call_p (curr
, node
, false, depth
))
1806 curr
->redirect_callee (dest
);
1807 if (edge_growth_cache
!= NULL
)
1808 edge_growth_cache
->remove (curr
);
1815 " Inlining call of depth %i", depth
);
1816 if (node
->count
.nonzero_p () && curr
->count
.initialized_p ())
1818 fprintf (dump_file
, " called approx. %.2f times per call",
1819 (double)curr
->count
.to_gcov_type ()
1820 / node
->count
.to_gcov_type ());
1822 fprintf (dump_file
, "\n");
1826 /* We need original clone to copy around. */
1827 master_clone
= node
->create_clone (node
->decl
, node
->count
,
1828 false, vNULL
, true, NULL
, NULL
);
1829 for (e
= master_clone
->callees
; e
; e
= e
->next_callee
)
1830 if (!e
->inline_failed
)
1831 clone_inlined_nodes (e
, true, false, NULL
);
1832 curr
->redirect_callee (master_clone
);
1833 if (edge_growth_cache
!= NULL
)
1834 edge_growth_cache
->remove (curr
);
1837 inline_call (curr
, false, new_edges
, &overall_size
, true);
1838 reset_node_cache (node
);
1839 lookup_recursive_calls (node
, curr
->callee
, &heap
);
1843 if (!heap
.empty () && dump_file
)
1844 fprintf (dump_file
, " Recursive inlining growth limit met.\n");
1849 if (dump_enabled_p ())
1850 dump_printf_loc (MSG_NOTE
, edge
->call_stmt
,
1851 "\n Inlined %i times, "
1852 "body grown from size %i to %i, time %f to %f\n", n
,
1853 ipa_size_summaries
->get (master_clone
)->size
,
1854 ipa_size_summaries
->get (node
)->size
,
1855 ipa_fn_summaries
->get (master_clone
)->time
.to_double (),
1856 ipa_fn_summaries
->get (node
)->time
.to_double ());
1858 /* Remove master clone we used for inlining. We rely that clones inlined
1859 into master clone gets queued just before master clone so we don't
1861 for (node
= symtab
->first_function (); node
!= master_clone
;
1864 next
= symtab
->next_function (node
);
1865 if (node
->inlined_to
== master_clone
)
1868 master_clone
->remove ();
1873 /* Given whole compilation unit estimate of INSNS, compute how large we can
1874 allow the unit to grow. */
1877 compute_max_insns (cgraph_node
*node
, int insns
)
1879 int max_insns
= insns
;
1880 if (max_insns
< opt_for_fn (node
->decl
, param_large_unit_insns
))
1881 max_insns
= opt_for_fn (node
->decl
, param_large_unit_insns
);
1883 return ((int64_t) max_insns
1884 * (100 + opt_for_fn (node
->decl
, param_inline_unit_growth
)) / 100);
1888 /* Compute badness of all edges in NEW_EDGES and add them to the HEAP. */
1891 add_new_edges_to_heap (edge_heap_t
*heap
, vec
<cgraph_edge
*> &new_edges
)
1893 while (new_edges
.length () > 0)
1895 struct cgraph_edge
*edge
= new_edges
.pop ();
1897 gcc_assert (!edge
->aux
);
1898 gcc_assert (edge
->callee
);
1899 if (edge
->inline_failed
1900 && can_inline_edge_p (edge
, true)
1901 && want_inline_small_function_p (edge
, true)
1902 && can_inline_edge_by_limits_p (edge
, true))
1904 inline_badness
b (edge
, edge_badness (edge
, false));
1905 edge
->aux
= heap
->insert (b
, edge
);
1910 /* Remove EDGE from the fibheap. */
1913 heap_edge_removal_hook (struct cgraph_edge
*e
, void *data
)
1917 ((edge_heap_t
*)data
)->delete_node ((edge_heap_node_t
*)e
->aux
);
1922 /* Return true if speculation of edge E seems useful.
1923 If ANTICIPATE_INLINING is true, be conservative and hope that E
1927 speculation_useful_p (struct cgraph_edge
*e
, bool anticipate_inlining
)
1929 /* If we have already decided to inline the edge, it seems useful. */
1930 if (!e
->inline_failed
)
1933 enum availability avail
;
1934 struct cgraph_node
*target
= e
->callee
->ultimate_alias_target (&avail
,
1937 gcc_assert (e
->speculative
&& !e
->indirect_unknown_callee
);
1939 if (!e
->maybe_hot_p ())
1942 /* See if IP optimizations found something potentially useful about the
1943 function. For now we look only for CONST/PURE flags. Almost everything
1944 else we propagate is useless. */
1945 if (avail
>= AVAIL_AVAILABLE
)
1947 int ecf_flags
= flags_from_decl_or_type (target
->decl
);
1948 if (ecf_flags
& ECF_CONST
)
1950 if (!(e
->speculative_call_indirect_edge ()->indirect_info
1951 ->ecf_flags
& ECF_CONST
))
1954 else if (ecf_flags
& ECF_PURE
)
1956 if (!(e
->speculative_call_indirect_edge ()->indirect_info
1957 ->ecf_flags
& ECF_PURE
))
1961 /* If we did not managed to inline the function nor redirect
1962 to an ipa-cp clone (that are seen by having local flag set),
1963 it is probably pointless to inline it unless hardware is missing
1964 indirect call predictor. */
1965 if (!anticipate_inlining
&& !target
->local
)
1967 /* For overwritable targets there is not much to do. */
1968 if (!can_inline_edge_p (e
, false)
1969 || !can_inline_edge_by_limits_p (e
, false, true))
1971 /* OK, speculation seems interesting. */
1975 /* We know that EDGE is not going to be inlined.
1976 See if we can remove speculation. */
1979 resolve_noninline_speculation (edge_heap_t
*edge_heap
, struct cgraph_edge
*edge
)
1981 if (edge
->speculative
&& !speculation_useful_p (edge
, false))
1983 struct cgraph_node
*node
= edge
->caller
;
1984 struct cgraph_node
*where
= node
->inlined_to
1985 ? node
->inlined_to
: node
;
1986 auto_bitmap updated_nodes
;
1988 if (edge
->count
.ipa ().initialized_p ())
1989 spec_rem
+= edge
->count
.ipa ();
1990 cgraph_edge::resolve_speculation (edge
);
1991 reset_edge_caches (where
);
1992 ipa_update_overall_fn_summary (where
);
1993 update_caller_keys (edge_heap
, where
,
1994 updated_nodes
, NULL
);
1995 update_callee_keys (edge_heap
, where
, NULL
,
2000 /* Return true if NODE should be accounted for overall size estimate.
2001 Skip all nodes optimized for size so we can measure the growth of hot
2002 part of program no matter of the padding. */
2005 inline_account_function_p (struct cgraph_node
*node
)
2007 return (!DECL_EXTERNAL (node
->decl
)
2008 && !opt_for_fn (node
->decl
, optimize_size
)
2009 && node
->frequency
!= NODE_FREQUENCY_UNLIKELY_EXECUTED
);
2012 /* Count number of callers of NODE and store it into DATA (that
2013 points to int. Worker for cgraph_for_node_and_aliases. */
2016 sum_callers (struct cgraph_node
*node
, void *data
)
2018 struct cgraph_edge
*e
;
2019 int *num_calls
= (int *)data
;
2021 for (e
= node
->callers
; e
; e
= e
->next_caller
)
2026 /* We only propagate across edges with non-interposable callee. */
2029 ignore_edge_p (struct cgraph_edge
*e
)
2031 enum availability avail
;
2032 e
->callee
->function_or_virtual_thunk_symbol (&avail
, e
->caller
);
2033 return (avail
<= AVAIL_INTERPOSABLE
);
2036 /* We use greedy algorithm for inlining of small functions:
2037 All inline candidates are put into prioritized heap ordered in
2040 The inlining of small functions is bounded by unit growth parameters. */
2043 inline_small_functions (void)
2045 struct cgraph_node
*node
;
2046 struct cgraph_edge
*edge
;
2048 edge_heap_t
edge_heap (b
);
2049 auto_bitmap updated_nodes
;
2051 auto_vec
<cgraph_edge
*> new_indirect_edges
;
2052 int initial_size
= 0;
2053 struct cgraph_node
**order
= XCNEWVEC (cgraph_node
*, symtab
->cgraph_count
);
2054 struct cgraph_edge_hook_list
*edge_removal_hook_holder
;
2055 new_indirect_edges
.create (8);
2057 edge_removal_hook_holder
2058 = symtab
->add_edge_removal_hook (&heap_edge_removal_hook
, &edge_heap
);
2060 /* Compute overall unit size and other global parameters used by badness
2063 max_count
= profile_count::uninitialized ();
2064 ipa_reduced_postorder (order
, true, ignore_edge_p
);
2067 FOR_EACH_DEFINED_FUNCTION (node
)
2068 if (!node
->inlined_to
)
2070 if (!node
->alias
&& node
->analyzed
2071 && (node
->has_gimple_body_p () || node
->thunk
)
2072 && opt_for_fn (node
->decl
, optimize
))
2074 class ipa_fn_summary
*info
= ipa_fn_summaries
->get (node
);
2075 struct ipa_dfs_info
*dfs
= (struct ipa_dfs_info
*) node
->aux
;
2077 /* Do not account external functions, they will be optimized out
2078 if not inlined. Also only count the non-cold portion of program. */
2079 if (inline_account_function_p (node
))
2080 initial_size
+= ipa_size_summaries
->get (node
)->size
;
2081 info
->growth
= estimate_growth (node
);
2084 node
->call_for_symbol_and_aliases (sum_callers
, &num_calls
,
2087 info
->single_caller
= true;
2088 if (dfs
&& dfs
->next_cycle
)
2090 struct cgraph_node
*n2
;
2091 int id
= dfs
->scc_no
+ 1;
2093 n2
= ((struct ipa_dfs_info
*) n2
->aux
)->next_cycle
)
2094 if (opt_for_fn (n2
->decl
, optimize
))
2096 ipa_fn_summary
*info2
= ipa_fn_summaries
->get
2097 (n2
->inlined_to
? n2
->inlined_to
: n2
);
2105 for (edge
= node
->callers
; edge
; edge
= edge
->next_caller
)
2106 max_count
= max_count
.max (edge
->count
.ipa ());
2108 ipa_free_postorder_info ();
2109 initialize_growth_caches ();
2113 "\nDeciding on inlining of small functions. Starting with size %i.\n",
2116 overall_size
= initial_size
;
2117 min_size
= overall_size
;
2119 /* Populate the heap with all edges we might inline. */
2121 FOR_EACH_DEFINED_FUNCTION (node
)
2123 bool update
= false;
2124 struct cgraph_edge
*next
= NULL
;
2125 bool has_speculative
= false;
2127 if (!opt_for_fn (node
->decl
, optimize
)
2128 /* With -Og we do not want to perform IPA inlining of small
2129 functions since there are no scalar cleanups after it
2130 that would realize the anticipated win. All abstraction
2131 is removed during early inlining. */
2132 || opt_for_fn (node
->decl
, optimize_debug
))
2136 fprintf (dump_file
, "Enqueueing calls in %s.\n", node
->dump_name ());
2138 for (edge
= node
->callees
; edge
; edge
= edge
->next_callee
)
2140 if (edge
->inline_failed
2142 && can_inline_edge_p (edge
, true)
2143 && want_inline_small_function_p (edge
, true)
2144 && can_inline_edge_by_limits_p (edge
, true)
2145 && edge
->inline_failed
)
2147 gcc_assert (!edge
->aux
);
2148 update_edge_key (&edge_heap
, edge
);
2150 if (edge
->speculative
)
2151 has_speculative
= true;
2153 if (has_speculative
)
2154 for (edge
= node
->callees
; edge
; edge
= next
)
2156 next
= edge
->next_callee
;
2157 if (edge
->speculative
2158 && !speculation_useful_p (edge
, edge
->aux
!= NULL
))
2160 cgraph_edge::resolve_speculation (edge
);
2166 struct cgraph_node
*where
= node
->inlined_to
2167 ? node
->inlined_to
: node
;
2168 ipa_update_overall_fn_summary (where
);
2169 reset_edge_caches (where
);
2170 update_caller_keys (&edge_heap
, where
,
2171 updated_nodes
, NULL
);
2172 update_callee_keys (&edge_heap
, where
, NULL
,
2174 bitmap_clear (updated_nodes
);
2178 gcc_assert (in_lto_p
2180 || (profile_info
&& flag_branch_probabilities
));
2182 while (!edge_heap
.empty ())
2184 int old_size
= overall_size
;
2185 struct cgraph_node
*where
, *callee
;
2186 sreal badness
= edge_heap
.min_key ().badness
;
2187 sreal current_badness
;
2190 edge
= edge_heap
.extract_min ();
2191 gcc_assert (edge
->aux
);
2193 if (!edge
->inline_failed
|| !edge
->callee
->analyzed
)
2196 /* Be sure that caches are maintained consistent.
2197 This check is affected by scaling roundoff errors when compiling for
2198 IPA this we skip it in that case. */
2199 if (flag_checking
&& !edge
->callee
->count
.ipa_p ()
2200 && (!max_count
.initialized_p () || !max_count
.nonzero_p ()))
2202 sreal cached_badness
= edge_badness (edge
, false);
2204 int old_size_est
= estimate_edge_size (edge
);
2205 sreal old_time_est
= estimate_edge_time (edge
);
2206 int old_hints_est
= estimate_edge_hints (edge
);
2208 if (edge_growth_cache
!= NULL
)
2209 edge_growth_cache
->remove (edge
);
2210 reset_node_cache (edge
->caller
->inlined_to
2211 ? edge
->caller
->inlined_to
2213 gcc_assert (old_size_est
== estimate_edge_size (edge
));
2214 gcc_assert (old_time_est
== estimate_edge_time (edge
));
2217 gcc_assert (old_hints_est == estimate_edge_hints (edge));
2219 fails with profile feedback because some hints depends on
2220 maybe_hot_edge_p predicate and because callee gets inlined to other
2221 calls, the edge may become cold.
2222 This ought to be fixed by computing relative probabilities
2223 for given invocation but that will be better done once whole
2224 code is converted to sreals. Disable for now and revert to "wrong"
2225 value so enable/disable checking paths agree. */
2226 edge_growth_cache
->get (edge
)->hints
= old_hints_est
+ 1;
2228 /* When updating the edge costs, we only decrease badness in the keys.
2229 Increases of badness are handled lazily; when we see key with out
2230 of date value on it, we re-insert it now. */
2231 current_badness
= edge_badness (edge
, false);
2232 gcc_assert (cached_badness
== current_badness
);
2233 gcc_assert (current_badness
>= badness
);
2236 current_badness
= edge_badness (edge
, false);
2237 if (current_badness
!= badness
)
2239 if (edge_heap
.min () && current_badness
> edge_heap
.min_key ().badness
)
2241 inline_badness
b (edge
, current_badness
);
2242 edge
->aux
= edge_heap
.insert (b
, edge
);
2246 badness
= current_badness
;
2249 if (!can_inline_edge_p (edge
, true)
2250 || !can_inline_edge_by_limits_p (edge
, true))
2252 resolve_noninline_speculation (&edge_heap
, edge
);
2256 callee
= edge
->callee
->ultimate_alias_target ();
2257 growth
= estimate_edge_growth (edge
);
2261 "\nConsidering %s with %i size\n",
2262 callee
->dump_name (),
2263 ipa_size_summaries
->get (callee
)->size
);
2265 " to be inlined into %s in %s:%i\n"
2266 " Estimated badness is %f, frequency %.2f.\n",
2267 edge
->caller
->dump_name (),
2269 && (LOCATION_LOCUS (gimple_location ((const gimple
*)
2271 > BUILTINS_LOCATION
)
2272 ? gimple_filename ((const gimple
*) edge
->call_stmt
)
2275 ? gimple_lineno ((const gimple
*) edge
->call_stmt
)
2277 badness
.to_double (),
2278 edge
->sreal_frequency ().to_double ());
2279 if (edge
->count
.ipa ().initialized_p ())
2281 fprintf (dump_file
, " Called ");
2282 edge
->count
.ipa ().dump (dump_file
);
2283 fprintf (dump_file
, " times\n");
2285 if (dump_flags
& TDF_DETAILS
)
2286 edge_badness (edge
, true);
2289 where
= edge
->caller
;
2291 if (overall_size
+ growth
> compute_max_insns (where
, min_size
)
2292 && !DECL_DISREGARD_INLINE_LIMITS (callee
->decl
))
2294 edge
->inline_failed
= CIF_INLINE_UNIT_GROWTH_LIMIT
;
2295 report_inline_failed_reason (edge
);
2296 resolve_noninline_speculation (&edge_heap
, edge
);
2300 if (!want_inline_small_function_p (edge
, true))
2302 resolve_noninline_speculation (&edge_heap
, edge
);
2306 profile_count old_count
= callee
->count
;
2308 /* Heuristics for inlining small functions work poorly for
2309 recursive calls where we do effects similar to loop unrolling.
2310 When inlining such edge seems profitable, leave decision on
2311 specific inliner. */
2312 if (edge
->recursive_p ())
2314 if (where
->inlined_to
)
2315 where
= where
->inlined_to
;
2316 if (!recursive_inlining (edge
,
2317 opt_for_fn (edge
->caller
->decl
,
2318 flag_indirect_inlining
)
2319 ? &new_indirect_edges
: NULL
))
2321 edge
->inline_failed
= CIF_RECURSIVE_INLINING
;
2322 resolve_noninline_speculation (&edge_heap
, edge
);
2325 reset_edge_caches (where
);
2326 /* Recursive inliner inlines all recursive calls of the function
2327 at once. Consequently we need to update all callee keys. */
2328 if (opt_for_fn (edge
->caller
->decl
, flag_indirect_inlining
))
2329 add_new_edges_to_heap (&edge_heap
, new_indirect_edges
);
2330 update_callee_keys (&edge_heap
, where
, where
, updated_nodes
);
2331 bitmap_clear (updated_nodes
);
2335 struct cgraph_node
*outer_node
= NULL
;
2338 /* Consider the case where self recursive function A is inlined
2339 into B. This is desired optimization in some cases, since it
2340 leads to effect similar of loop peeling and we might completely
2341 optimize out the recursive call. However we must be extra
2344 where
= edge
->caller
;
2345 while (where
->inlined_to
)
2347 if (where
->decl
== callee
->decl
)
2348 outer_node
= where
, depth
++;
2349 where
= where
->callers
->caller
;
2352 && !want_inline_self_recursive_call_p (edge
, outer_node
,
2356 = (DECL_DISREGARD_INLINE_LIMITS (edge
->callee
->decl
)
2357 ? CIF_RECURSIVE_INLINING
: CIF_UNSPECIFIED
);
2358 resolve_noninline_speculation (&edge_heap
, edge
);
2361 else if (depth
&& dump_file
)
2362 fprintf (dump_file
, " Peeling recursion with depth %i\n", depth
);
2364 gcc_checking_assert (!callee
->inlined_to
);
2366 int old_size
= ipa_size_summaries
->get (where
)->size
;
2367 sreal old_time
= ipa_fn_summaries
->get (where
)->time
;
2369 inline_call (edge
, true, &new_indirect_edges
, &overall_size
, true);
2370 reset_edge_caches (edge
->callee
);
2371 add_new_edges_to_heap (&edge_heap
, new_indirect_edges
);
2373 /* If caller's size and time increased we do not need to update
2374 all edges because badness is not going to decrease. */
2375 if (old_size
<= ipa_size_summaries
->get (where
)->size
2376 && old_time
<= ipa_fn_summaries
->get (where
)->time
2377 /* Wrapper penalty may be non-monotonous in this respect.
2378 Fortunately it only affects small functions. */
2379 && !wrapper_heuristics_may_apply (where
, old_size
))
2380 update_callee_keys (&edge_heap
, edge
->callee
, edge
->callee
,
2383 update_callee_keys (&edge_heap
, where
,
2387 where
= edge
->caller
;
2388 if (where
->inlined_to
)
2389 where
= where
->inlined_to
;
2391 /* Our profitability metric can depend on local properties
2392 such as number of inlinable calls and size of the function body.
2393 After inlining these properties might change for the function we
2394 inlined into (since it's body size changed) and for the functions
2395 called by function we inlined (since number of it inlinable callers
2397 update_caller_keys (&edge_heap
, where
, updated_nodes
, NULL
);
2398 /* Offline copy count has possibly changed, recompute if profile is
2400 struct cgraph_node
*n
2401 = cgraph_node::get (edge
->callee
->decl
)->ultimate_alias_target ();
2402 if (n
!= edge
->callee
&& n
->analyzed
&& !(n
->count
== old_count
)
2403 && n
->count
.ipa_p ())
2404 update_callee_keys (&edge_heap
, n
, NULL
, updated_nodes
);
2405 bitmap_clear (updated_nodes
);
2407 if (dump_enabled_p ())
2409 ipa_fn_summary
*s
= ipa_fn_summaries
->get (where
);
2411 /* dump_printf can't handle %+i. */
2412 char buf_net_change
[100];
2413 snprintf (buf_net_change
, sizeof buf_net_change
, "%+i",
2414 overall_size
- old_size
);
2416 dump_printf_loc (MSG_OPTIMIZED_LOCATIONS
, edge
->call_stmt
,
2417 " Inlined %C into %C which now has time %f and "
2418 "size %i, net change of %s%s.\n",
2419 edge
->callee
, edge
->caller
,
2420 s
->time
.to_double (),
2421 ipa_size_summaries
->get (edge
->caller
)->size
,
2423 cross_module_call_p (edge
) ? " (cross module)":"");
2425 if (min_size
> overall_size
)
2427 min_size
= overall_size
;
2430 fprintf (dump_file
, "New minimal size reached: %i\n", min_size
);
2434 free_growth_caches ();
2435 if (dump_enabled_p ())
2436 dump_printf (MSG_NOTE
,
2437 "Unit growth for small function inlining: %i->%i (%i%%)\n",
2438 initial_size
, overall_size
,
2439 initial_size
? overall_size
* 100 / (initial_size
) - 100: 0);
2440 symtab
->remove_edge_removal_hook (edge_removal_hook_holder
);
2443 /* Flatten NODE. Performed both during early inlining and
2444 at IPA inlining time. */
2447 flatten_function (struct cgraph_node
*node
, bool early
, bool update
)
2449 struct cgraph_edge
*e
;
2451 /* We shouldn't be called recursively when we are being processed. */
2452 gcc_assert (node
->aux
== NULL
);
2454 node
->aux
= (void *) node
;
2456 for (e
= node
->callees
; e
; e
= e
->next_callee
)
2458 struct cgraph_node
*orig_callee
;
2459 struct cgraph_node
*callee
= e
->callee
->ultimate_alias_target ();
2461 /* We've hit cycle? It is time to give up. */
2464 if (dump_enabled_p ())
2465 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, e
->call_stmt
,
2466 "Not inlining %C into %C to avoid cycle.\n",
2468 if (cgraph_inline_failed_type (e
->inline_failed
) != CIF_FINAL_ERROR
)
2469 e
->inline_failed
= CIF_RECURSIVE_INLINING
;
2473 /* When the edge is already inlined, we just need to recurse into
2474 it in order to fully flatten the leaves. */
2475 if (!e
->inline_failed
)
2477 flatten_function (callee
, early
, false);
2481 /* Flatten attribute needs to be processed during late inlining. For
2482 extra code quality we however do flattening during early optimization,
2485 ? !can_inline_edge_p (e
, true)
2486 && !can_inline_edge_by_limits_p (e
, true)
2487 : !can_early_inline_edge_p (e
))
2490 if (e
->recursive_p ())
2492 if (dump_enabled_p ())
2493 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, e
->call_stmt
,
2494 "Not inlining: recursive call.\n");
2498 if (gimple_in_ssa_p (DECL_STRUCT_FUNCTION (node
->decl
))
2499 != gimple_in_ssa_p (DECL_STRUCT_FUNCTION (callee
->decl
)))
2501 if (dump_enabled_p ())
2502 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, e
->call_stmt
,
2503 "Not inlining: SSA form does not match.\n");
2507 /* Inline the edge and flatten the inline clone. Avoid
2508 recursing through the original node if the node was cloned. */
2509 if (dump_enabled_p ())
2510 dump_printf_loc (MSG_OPTIMIZED_LOCATIONS
, e
->call_stmt
,
2511 " Inlining %C into %C.\n",
2513 orig_callee
= callee
;
2514 inline_call (e
, true, NULL
, NULL
, false);
2515 if (e
->callee
!= orig_callee
)
2516 orig_callee
->aux
= (void *) node
;
2517 flatten_function (e
->callee
, early
, false);
2518 if (e
->callee
!= orig_callee
)
2519 orig_callee
->aux
= NULL
;
2523 cgraph_node
*where
= node
->inlined_to
? node
->inlined_to
: node
;
2524 if (update
&& opt_for_fn (where
->decl
, optimize
))
2525 ipa_update_overall_fn_summary (where
);
2528 /* Inline NODE to all callers. Worker for cgraph_for_node_and_aliases.
2529 DATA points to number of calls originally found so we avoid infinite
2533 inline_to_all_callers_1 (struct cgraph_node
*node
, void *data
,
2534 hash_set
<cgraph_node
*> *callers
)
2536 int *num_calls
= (int *)data
;
2537 bool callee_removed
= false;
2539 while (node
->callers
&& !node
->inlined_to
)
2541 struct cgraph_node
*caller
= node
->callers
->caller
;
2543 if (!can_inline_edge_p (node
->callers
, true)
2544 || !can_inline_edge_by_limits_p (node
->callers
, true)
2545 || node
->callers
->recursive_p ())
2548 fprintf (dump_file
, "Uninlinable call found; giving up.\n");
2555 cgraph_node
*ultimate
= node
->ultimate_alias_target ();
2557 "\nInlining %s size %i.\n",
2558 ultimate
->dump_name (),
2559 ipa_size_summaries
->get (ultimate
)->size
);
2561 " Called once from %s %i insns.\n",
2562 node
->callers
->caller
->dump_name (),
2563 ipa_size_summaries
->get (node
->callers
->caller
)->size
);
2566 /* Remember which callers we inlined to, delaying updating the
2568 callers
->add (node
->callers
->caller
);
2569 inline_call (node
->callers
, true, NULL
, NULL
, false, &callee_removed
);
2572 " Inlined into %s which now has %i size\n",
2573 caller
->dump_name (),
2574 ipa_size_summaries
->get (caller
)->size
);
2575 if (!(*num_calls
)--)
2578 fprintf (dump_file
, "New calls found; giving up.\n");
2579 return callee_removed
;
2587 /* Wrapper around inline_to_all_callers_1 doing delayed overall summary
2591 inline_to_all_callers (struct cgraph_node
*node
, void *data
)
2593 hash_set
<cgraph_node
*> callers
;
2594 bool res
= inline_to_all_callers_1 (node
, data
, &callers
);
2595 /* Perform the delayed update of the overall summary of all callers
2596 processed. This avoids quadratic behavior in the cases where
2597 we have a lot of calls to the same function. */
2598 for (hash_set
<cgraph_node
*>::iterator i
= callers
.begin ();
2599 i
!= callers
.end (); ++i
)
2600 ipa_update_overall_fn_summary ((*i
)->inlined_to
? (*i
)->inlined_to
: *i
);
2604 /* Output overall time estimate. */
2606 dump_overall_stats (void)
2608 sreal sum_weighted
= 0, sum
= 0;
2609 struct cgraph_node
*node
;
2611 FOR_EACH_DEFINED_FUNCTION (node
)
2612 if (!node
->inlined_to
2615 ipa_fn_summary
*s
= ipa_fn_summaries
->get (node
);
2619 if (node
->count
.ipa ().initialized_p ())
2620 sum_weighted
+= s
->time
* node
->count
.ipa ().to_gcov_type ();
2623 fprintf (dump_file
, "Overall time estimate: "
2624 "%f weighted by profile: "
2625 "%f\n", sum
.to_double (), sum_weighted
.to_double ());
2628 /* Output some useful stats about inlining. */
2631 dump_inline_stats (void)
2633 int64_t inlined_cnt
= 0, inlined_indir_cnt
= 0;
2634 int64_t inlined_virt_cnt
= 0, inlined_virt_indir_cnt
= 0;
2635 int64_t noninlined_cnt
= 0, noninlined_indir_cnt
= 0;
2636 int64_t noninlined_virt_cnt
= 0, noninlined_virt_indir_cnt
= 0;
2637 int64_t inlined_speculative
= 0, inlined_speculative_ply
= 0;
2638 int64_t indirect_poly_cnt
= 0, indirect_cnt
= 0;
2639 int64_t reason
[CIF_N_REASONS
][2];
2640 sreal reason_freq
[CIF_N_REASONS
];
2642 struct cgraph_node
*node
;
2644 memset (reason
, 0, sizeof (reason
));
2645 for (i
=0; i
< CIF_N_REASONS
; i
++)
2647 FOR_EACH_DEFINED_FUNCTION (node
)
2649 struct cgraph_edge
*e
;
2650 for (e
= node
->callees
; e
; e
= e
->next_callee
)
2652 if (e
->inline_failed
)
2654 if (e
->count
.ipa ().initialized_p ())
2655 reason
[(int) e
->inline_failed
][0] += e
->count
.ipa ().to_gcov_type ();
2656 reason_freq
[(int) e
->inline_failed
] += e
->sreal_frequency ();
2657 reason
[(int) e
->inline_failed
][1] ++;
2658 if (DECL_VIRTUAL_P (e
->callee
->decl
)
2659 && e
->count
.ipa ().initialized_p ())
2661 if (e
->indirect_inlining_edge
)
2662 noninlined_virt_indir_cnt
+= e
->count
.ipa ().to_gcov_type ();
2664 noninlined_virt_cnt
+= e
->count
.ipa ().to_gcov_type ();
2666 else if (e
->count
.ipa ().initialized_p ())
2668 if (e
->indirect_inlining_edge
)
2669 noninlined_indir_cnt
+= e
->count
.ipa ().to_gcov_type ();
2671 noninlined_cnt
+= e
->count
.ipa ().to_gcov_type ();
2674 else if (e
->count
.ipa ().initialized_p ())
2678 if (DECL_VIRTUAL_P (e
->callee
->decl
))
2679 inlined_speculative_ply
+= e
->count
.ipa ().to_gcov_type ();
2681 inlined_speculative
+= e
->count
.ipa ().to_gcov_type ();
2683 else if (DECL_VIRTUAL_P (e
->callee
->decl
))
2685 if (e
->indirect_inlining_edge
)
2686 inlined_virt_indir_cnt
+= e
->count
.ipa ().to_gcov_type ();
2688 inlined_virt_cnt
+= e
->count
.ipa ().to_gcov_type ();
2692 if (e
->indirect_inlining_edge
)
2693 inlined_indir_cnt
+= e
->count
.ipa ().to_gcov_type ();
2695 inlined_cnt
+= e
->count
.ipa ().to_gcov_type ();
2699 for (e
= node
->indirect_calls
; e
; e
= e
->next_callee
)
2700 if (e
->indirect_info
->polymorphic
2701 & e
->count
.ipa ().initialized_p ())
2702 indirect_poly_cnt
+= e
->count
.ipa ().to_gcov_type ();
2703 else if (e
->count
.ipa ().initialized_p ())
2704 indirect_cnt
+= e
->count
.ipa ().to_gcov_type ();
2706 if (max_count
.initialized_p ())
2709 "Inlined %" PRId64
" + speculative "
2710 "%" PRId64
" + speculative polymorphic "
2711 "%" PRId64
" + previously indirect "
2712 "%" PRId64
" + virtual "
2713 "%" PRId64
" + virtual and previously indirect "
2714 "%" PRId64
"\n" "Not inlined "
2715 "%" PRId64
" + previously indirect "
2716 "%" PRId64
" + virtual "
2717 "%" PRId64
" + virtual and previously indirect "
2718 "%" PRId64
" + still indirect "
2719 "%" PRId64
" + still indirect polymorphic "
2720 "%" PRId64
"\n", inlined_cnt
,
2721 inlined_speculative
, inlined_speculative_ply
,
2722 inlined_indir_cnt
, inlined_virt_cnt
, inlined_virt_indir_cnt
,
2723 noninlined_cnt
, noninlined_indir_cnt
, noninlined_virt_cnt
,
2724 noninlined_virt_indir_cnt
, indirect_cnt
, indirect_poly_cnt
);
2725 fprintf (dump_file
, "Removed speculations ");
2726 spec_rem
.dump (dump_file
);
2727 fprintf (dump_file
, "\n");
2729 dump_overall_stats ();
2730 fprintf (dump_file
, "\nWhy inlining failed?\n");
2731 for (i
= 0; i
< CIF_N_REASONS
; i
++)
2733 fprintf (dump_file
, "%-50s: %8i calls, %8f freq, %" PRId64
" count\n",
2734 cgraph_inline_failed_string ((cgraph_inline_failed_t
) i
),
2735 (int) reason
[i
][1], reason_freq
[i
].to_double (), reason
[i
][0]);
2738 /* Called when node is removed. */
2741 flatten_remove_node_hook (struct cgraph_node
*node
, void *data
)
2743 if (lookup_attribute ("flatten", DECL_ATTRIBUTES (node
->decl
)) == NULL
)
2746 hash_set
<struct cgraph_node
*> *removed
2747 = (hash_set
<struct cgraph_node
*> *) data
;
2748 removed
->add (node
);
2751 /* Decide on the inlining. We do so in the topological order to avoid
2752 expenses on updating data structures. */
2757 struct cgraph_node
*node
;
2759 struct cgraph_node
**order
;
2762 bool remove_functions
= false;
2764 order
= XCNEWVEC (struct cgraph_node
*, symtab
->cgraph_count
);
2767 ipa_dump_fn_summaries (dump_file
);
2769 nnodes
= ipa_reverse_postorder (order
);
2770 spec_rem
= profile_count::zero ();
2772 FOR_EACH_FUNCTION (node
)
2776 /* Recompute the default reasons for inlining because they may have
2777 changed during merging. */
2780 for (cgraph_edge
*e
= node
->callees
; e
; e
= e
->next_callee
)
2782 gcc_assert (e
->inline_failed
);
2783 initialize_inline_failed (e
);
2785 for (cgraph_edge
*e
= node
->indirect_calls
; e
; e
= e
->next_callee
)
2786 initialize_inline_failed (e
);
2791 fprintf (dump_file
, "\nFlattening functions:\n");
2793 /* First shrink order array, so that it only contains nodes with
2794 flatten attribute. */
2795 for (i
= nnodes
- 1, j
= i
; i
>= 0; i
--)
2798 if (node
->definition
2799 /* Do not try to flatten aliases. These may happen for example when
2800 creating local aliases. */
2802 && lookup_attribute ("flatten",
2803 DECL_ATTRIBUTES (node
->decl
)) != NULL
)
2804 order
[j
--] = order
[i
];
2807 /* After the above loop, order[j + 1] ... order[nnodes - 1] contain
2808 nodes with flatten attribute. If there is more than one such
2809 node, we need to register a node removal hook, as flatten_function
2810 could remove other nodes with flatten attribute. See PR82801. */
2811 struct cgraph_node_hook_list
*node_removal_hook_holder
= NULL
;
2812 hash_set
<struct cgraph_node
*> *flatten_removed_nodes
= NULL
;
2815 flatten_removed_nodes
= new hash_set
<struct cgraph_node
*>;
2816 node_removal_hook_holder
2817 = symtab
->add_cgraph_removal_hook (&flatten_remove_node_hook
,
2818 flatten_removed_nodes
);
2821 /* In the first pass handle functions to be flattened. Do this with
2822 a priority so none of our later choices will make this impossible. */
2823 for (i
= nnodes
- 1; i
> j
; i
--)
2826 if (flatten_removed_nodes
2827 && flatten_removed_nodes
->contains (node
))
2830 /* Handle nodes to be flattened.
2831 Ideally when processing callees we stop inlining at the
2832 entry of cycles, possibly cloning that entry point and
2833 try to flatten itself turning it into a self-recursive
2836 fprintf (dump_file
, "Flattening %s\n", node
->dump_name ());
2837 flatten_function (node
, false, true);
2842 symtab
->remove_cgraph_removal_hook (node_removal_hook_holder
);
2843 delete flatten_removed_nodes
;
2848 dump_overall_stats ();
2850 inline_small_functions ();
2852 gcc_assert (symtab
->state
== IPA_SSA
);
2853 symtab
->state
= IPA_SSA_AFTER_INLINING
;
2854 /* Do first after-inlining removal. We want to remove all "stale" extern
2855 inline functions and virtual functions so we really know what is called
2857 symtab
->remove_unreachable_nodes (dump_file
);
2859 /* Inline functions with a property that after inlining into all callers the
2860 code size will shrink because the out-of-line copy is eliminated.
2861 We do this regardless on the callee size as long as function growth limits
2865 "\nDeciding on functions to be inlined into all callers and "
2866 "removing useless speculations:\n");
2868 /* Inlining one function called once has good chance of preventing
2869 inlining other function into the same callee. Ideally we should
2870 work in priority order, but probably inlining hot functions first
2871 is good cut without the extra pain of maintaining the queue.
2873 ??? this is not really fitting the bill perfectly: inlining function
2874 into callee often leads to better optimization of callee due to
2875 increased context for optimization.
2876 For example if main() function calls a function that outputs help
2877 and then function that does the main optimization, we should inline
2878 the second with priority even if both calls are cold by themselves.
2880 We probably want to implement new predicate replacing our use of
2881 maybe_hot_edge interpreted as maybe_hot_edge || callee is known
2883 for (cold
= 0; cold
<= 1; cold
++)
2885 FOR_EACH_DEFINED_FUNCTION (node
)
2887 struct cgraph_edge
*edge
, *next
;
2890 if (!opt_for_fn (node
->decl
, optimize
)
2891 || !opt_for_fn (node
->decl
, flag_inline_functions_called_once
))
2894 for (edge
= node
->callees
; edge
; edge
= next
)
2896 next
= edge
->next_callee
;
2897 if (edge
->speculative
&& !speculation_useful_p (edge
, false))
2899 if (edge
->count
.ipa ().initialized_p ())
2900 spec_rem
+= edge
->count
.ipa ();
2901 cgraph_edge::resolve_speculation (edge
);
2903 remove_functions
= true;
2908 struct cgraph_node
*where
= node
->inlined_to
2909 ? node
->inlined_to
: node
;
2910 reset_edge_caches (where
);
2911 ipa_update_overall_fn_summary (where
);
2913 if (want_inline_function_to_all_callers_p (node
, cold
))
2916 node
->call_for_symbol_and_aliases (sum_callers
, &num_calls
,
2918 while (node
->call_for_symbol_and_aliases
2919 (inline_to_all_callers
, &num_calls
, true))
2921 remove_functions
= true;
2926 if (dump_enabled_p ())
2927 dump_printf (MSG_NOTE
,
2928 "\nInlined %i calls, eliminated %i functions\n\n",
2929 ncalls_inlined
, nfunctions_inlined
);
2931 dump_inline_stats ();
2934 ipa_dump_fn_summaries (dump_file
);
2935 return remove_functions
? TODO_remove_functions
: 0;
2938 /* Inline always-inline function calls in NODE
2939 (which itself is possibly inline). */
2942 inline_always_inline_functions (struct cgraph_node
*node
)
2944 struct cgraph_edge
*e
;
2945 bool inlined
= false;
2947 for (e
= node
->callees
; e
; e
= e
->next_callee
)
2949 struct cgraph_node
*callee
= e
->callee
->ultimate_alias_target ();
2950 gcc_checking_assert (!callee
->aux
|| callee
->aux
== (void *)(size_t)1);
2951 if (!DECL_DISREGARD_INLINE_LIMITS (callee
->decl
)
2952 /* Watch for self-recursive cycles. */
2956 if (e
->recursive_p ())
2958 if (dump_enabled_p ())
2959 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, e
->call_stmt
,
2960 " Not inlining recursive call to %C.\n",
2962 e
->inline_failed
= CIF_RECURSIVE_INLINING
;
2965 if (callee
->definition
2966 && !ipa_fn_summaries
->get (callee
))
2967 compute_fn_summary (callee
, true);
2969 if (!can_early_inline_edge_p (e
))
2971 /* Set inlined to true if the callee is marked "always_inline" but
2972 is not inlinable. This will allow flagging an error later in
2973 expand_call_inline in tree-inline.cc. */
2974 if (lookup_attribute ("always_inline",
2975 DECL_ATTRIBUTES (callee
->decl
)) != NULL
)
2980 if (dump_enabled_p ())
2981 dump_printf_loc (MSG_OPTIMIZED_LOCATIONS
, e
->call_stmt
,
2982 " Inlining %C into %C (always_inline).\n",
2983 e
->callee
, e
->caller
);
2984 inline_call (e
, true, NULL
, NULL
, false);
2985 callee
->aux
= (void *)(size_t)1;
2986 /* Inline recursively to handle the case where always_inline function was
2987 not optimized yet since it is a part of a cycle in callgraph. */
2988 inline_always_inline_functions (e
->callee
);
2995 /* Decide on the inlining. We do so in the topological order to avoid
2996 expenses on updating data structures. */
2999 early_inline_small_functions (struct cgraph_node
*node
)
3001 struct cgraph_edge
*e
;
3002 bool inlined
= false;
3004 for (e
= node
->callees
; e
; e
= e
->next_callee
)
3006 struct cgraph_node
*callee
= e
->callee
->ultimate_alias_target ();
3008 /* We can encounter not-yet-analyzed function during
3009 early inlining on callgraphs with strongly
3010 connected components. */
3011 ipa_fn_summary
*s
= ipa_fn_summaries
->get (callee
);
3012 if (s
== NULL
|| !s
->inlinable
|| !e
->inline_failed
)
3015 /* Do not consider functions not declared inline. */
3016 if (!DECL_DECLARED_INLINE_P (callee
->decl
)
3017 && !opt_for_fn (node
->decl
, flag_inline_small_functions
)
3018 && !opt_for_fn (node
->decl
, flag_inline_functions
))
3021 if (dump_enabled_p ())
3022 dump_printf_loc (MSG_NOTE
, e
->call_stmt
,
3023 "Considering inline candidate %C.\n",
3026 if (!can_early_inline_edge_p (e
))
3029 if (e
->recursive_p ())
3031 if (dump_enabled_p ())
3032 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, e
->call_stmt
,
3033 " Not inlining: recursive call.\n");
3037 if (!want_early_inline_function_p (e
))
3040 if (dump_enabled_p ())
3041 dump_printf_loc (MSG_OPTIMIZED_LOCATIONS
, e
->call_stmt
,
3042 " Inlining %C into %C.\n",
3044 inline_call (e
, true, NULL
, NULL
, false);
3049 ipa_update_overall_fn_summary (node
);
3055 early_inliner (function
*fun
)
3057 struct cgraph_node
*node
= cgraph_node::get (current_function_decl
);
3058 struct cgraph_edge
*edge
;
3059 unsigned int todo
= 0;
3061 bool inlined
= false;
3066 /* Do nothing if datastructures for ipa-inliner are already computed. This
3067 happens when some pass decides to construct new function and
3068 cgraph_add_new_function calls lowering passes and early optimization on
3069 it. This may confuse ourself when early inliner decide to inline call to
3070 function clone, because function clones don't have parameter list in
3071 ipa-prop matching their signature. */
3072 if (ipa_node_params_sum
)
3077 node
->remove_all_references ();
3079 /* Even when not optimizing or not inlining inline always-inline
3081 inlined
= inline_always_inline_functions (node
);
3085 || !flag_early_inlining
)
3087 else if (lookup_attribute ("flatten",
3088 DECL_ATTRIBUTES (node
->decl
)) != NULL
)
3090 /* When the function is marked to be flattened, recursively inline
3092 if (dump_enabled_p ())
3093 dump_printf (MSG_OPTIMIZED_LOCATIONS
,
3094 "Flattening %C\n", node
);
3095 flatten_function (node
, true, true);
3100 /* If some always_inline functions was inlined, apply the changes.
3101 This way we will not account always inline into growth limits and
3102 moreover we will inline calls from always inlines that we skipped
3103 previously because of conditional in can_early_inline_edge_p
3104 which prevents some inlining to always_inline. */
3107 timevar_push (TV_INTEGRATION
);
3108 todo
|= optimize_inline_calls (current_function_decl
);
3109 /* optimize_inline_calls call above might have introduced new
3110 statements that don't have inline parameters computed. */
3111 for (edge
= node
->callees
; edge
; edge
= edge
->next_callee
)
3113 /* We can enounter not-yet-analyzed function during
3114 early inlining on callgraphs with strongly
3115 connected components. */
3116 ipa_call_summary
*es
= ipa_call_summaries
->get_create (edge
);
3118 = estimate_num_insns (edge
->call_stmt
, &eni_size_weights
);
3120 = estimate_num_insns (edge
->call_stmt
, &eni_time_weights
);
3122 ipa_update_overall_fn_summary (node
);
3124 timevar_pop (TV_INTEGRATION
);
3126 /* We iterate incremental inlining to get trivial cases of indirect
3128 while (iterations
< opt_for_fn (node
->decl
,
3129 param_early_inliner_max_iterations
)
3130 && early_inline_small_functions (node
))
3132 timevar_push (TV_INTEGRATION
);
3133 todo
|= optimize_inline_calls (current_function_decl
);
3135 /* Technically we ought to recompute inline parameters so the new
3136 iteration of early inliner works as expected. We however have
3137 values approximately right and thus we only need to update edge
3138 info that might be cleared out for newly discovered edges. */
3139 for (edge
= node
->callees
; edge
; edge
= edge
->next_callee
)
3141 /* We have no summary for new bound store calls yet. */
3142 ipa_call_summary
*es
= ipa_call_summaries
->get_create (edge
);
3144 = estimate_num_insns (edge
->call_stmt
, &eni_size_weights
);
3146 = estimate_num_insns (edge
->call_stmt
, &eni_time_weights
);
3148 if (iterations
< opt_for_fn (node
->decl
,
3149 param_early_inliner_max_iterations
) - 1)
3150 ipa_update_overall_fn_summary (node
);
3151 timevar_pop (TV_INTEGRATION
);
3156 fprintf (dump_file
, "Iterations: %i\n", iterations
);
3161 timevar_push (TV_INTEGRATION
);
3162 todo
|= optimize_inline_calls (current_function_decl
);
3163 timevar_pop (TV_INTEGRATION
);
3166 fun
->always_inline_functions_inlined
= true;
3171 /* Do inlining of small functions. Doing so early helps profiling and other
3172 passes to be somewhat more effective and avoids some code duplication in
3173 later real inlining pass for testcases with very many function calls. */
3177 const pass_data pass_data_early_inline
=
3179 GIMPLE_PASS
, /* type */
3180 "einline", /* name */
3181 OPTGROUP_INLINE
, /* optinfo_flags */
3182 TV_EARLY_INLINING
, /* tv_id */
3183 PROP_ssa
, /* properties_required */
3184 0, /* properties_provided */
3185 0, /* properties_destroyed */
3186 0, /* todo_flags_start */
3187 0, /* todo_flags_finish */
3190 class pass_early_inline
: public gimple_opt_pass
3193 pass_early_inline (gcc::context
*ctxt
)
3194 : gimple_opt_pass (pass_data_early_inline
, ctxt
)
3197 /* opt_pass methods: */
3198 unsigned int execute (function
*) final override
;
3200 }; // class pass_early_inline
3203 pass_early_inline::execute (function
*fun
)
3205 return early_inliner (fun
);
3211 make_pass_early_inline (gcc::context
*ctxt
)
3213 return new pass_early_inline (ctxt
);
3218 const pass_data pass_data_ipa_inline
=
3220 IPA_PASS
, /* type */
3221 "inline", /* name */
3222 OPTGROUP_INLINE
, /* optinfo_flags */
3223 TV_IPA_INLINING
, /* tv_id */
3224 0, /* properties_required */
3225 0, /* properties_provided */
3226 0, /* properties_destroyed */
3227 0, /* todo_flags_start */
3228 ( TODO_dump_symtab
), /* todo_flags_finish */
3231 class pass_ipa_inline
: public ipa_opt_pass_d
3234 pass_ipa_inline (gcc::context
*ctxt
)
3235 : ipa_opt_pass_d (pass_data_ipa_inline
, ctxt
,
3236 NULL
, /* generate_summary */
3237 NULL
, /* write_summary */
3238 NULL
, /* read_summary */
3239 NULL
, /* write_optimization_summary */
3240 NULL
, /* read_optimization_summary */
3241 NULL
, /* stmt_fixup */
3242 0, /* function_transform_todo_flags_start */
3243 inline_transform
, /* function_transform */
3244 NULL
) /* variable_transform */
3247 /* opt_pass methods: */
3248 unsigned int execute (function
*) final override
{ return ipa_inline (); }
3250 }; // class pass_ipa_inline
3255 make_pass_ipa_inline (gcc::context
*ctxt
)
3257 return new pass_ipa_inline (ctxt
);