1 /* Inlining decision heuristics.
2 Copyright (C) 2003-2016 Free Software Foundation, Inc.
3 Contributed by Jan Hubicka
5 This file is part of GCC.
7 GCC is free software; you can redistribute it and/or modify it under
8 the terms of the GNU General Public License as published by the Free
9 Software Foundation; either version 3, or (at your option) any later
12 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
13 WARRANTY; without even the implied warranty of MERCHANTABILITY or
14 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
17 You should have received a copy of the GNU General Public License
18 along with GCC; see the file COPYING3. If not see
19 <http://www.gnu.org/licenses/>. */
21 /* Inlining decision heuristics
23 The implementation of inliner is organized as follows:
25 inlining heuristics limits
27 can_inline_edge_p allow to check that particular inlining is allowed
28 by the limits specified by user (allowed function growth, growth and so
31 Functions are inlined when it is obvious the result is profitable (such
32 as functions called once or when inlining reduce code size).
33 In addition to that we perform inlining of small functions and recursive
38 The inliner itself is split into two passes:
42 Simple local inlining pass inlining callees into current function.
43 This pass makes no use of whole unit analysis and thus it can do only
44 very simple decisions based on local properties.
46 The strength of the pass is that it is run in topological order
47 (reverse postorder) on the callgraph. Functions are converted into SSA
48 form just before this pass and optimized subsequently. As a result, the
49 callees of the function seen by the early inliner was already optimized
50 and results of early inlining adds a lot of optimization opportunities
51 for the local optimization.
53 The pass handle the obvious inlining decisions within the compilation
54 unit - inlining auto inline functions, inlining for size and
57 main strength of the pass is the ability to eliminate abstraction
58 penalty in C++ code (via combination of inlining and early
59 optimization) and thus improve quality of analysis done by real IPA
62 Because of lack of whole unit knowledge, the pass can not really make
63 good code size/performance tradeoffs. It however does very simple
64 speculative inlining allowing code size to grow by
65 EARLY_INLINING_INSNS when callee is leaf function. In this case the
66 optimizations performed later are very likely to eliminate the cost.
70 This is the real inliner able to handle inlining with whole program
71 knowledge. It performs following steps:
73 1) inlining of small functions. This is implemented by greedy
74 algorithm ordering all inlinable cgraph edges by their badness and
75 inlining them in this order as long as inline limits allows doing so.
77 This heuristics is not very good on inlining recursive calls. Recursive
78 calls can be inlined with results similar to loop unrolling. To do so,
79 special purpose recursive inliner is executed on function when
80 recursive edge is met as viable candidate.
82 2) Unreachable functions are removed from callgraph. Inlining leads
83 to devirtualization and other modification of callgraph so functions
84 may become unreachable during the process. Also functions declared as
85 extern inline or virtual functions are removed, since after inlining
86 we no longer need the offline bodies.
88 3) Functions called once and not exported from the unit are inlined.
89 This should almost always lead to reduction of code size by eliminating
90 the need for offline copy of the function. */
94 #include "coretypes.h"
100 #include "alloc-pool.h"
101 #include "tree-pass.h"
102 #include "gimple-ssa.h"
104 #include "lto-streamer.h"
105 #include "trans-mem.h"
107 #include "tree-inline.h"
110 #include "symbol-summary.h"
111 #include "ipa-prop.h"
112 #include "ipa-inline.h"
113 #include "ipa-utils.h"
115 #include "auto-profile.h"
116 #include "builtins.h"
117 #include "fibonacci_heap.h"
119 typedef fibonacci_heap
<sreal
, cgraph_edge
> edge_heap_t
;
120 typedef fibonacci_node
<sreal
, cgraph_edge
> edge_heap_node_t
;
122 /* Statistics we collect about inlining algorithm. */
123 static int overall_size
;
124 static gcov_type max_count
;
125 static gcov_type spec_rem
;
127 /* Pre-computed constants 1/CGRAPH_FREQ_BASE and 1/100. */
128 static sreal cgraph_freq_base_rec
, percent_rec
;
130 /* Return false when inlining edge E would lead to violating
131 limits on function unit growth or stack usage growth.
133 The relative function body growth limit is present generally
134 to avoid problems with non-linear behavior of the compiler.
135 To allow inlining huge functions into tiny wrapper, the limit
136 is always based on the bigger of the two functions considered.
138 For stack growth limits we always base the growth in stack usage
139 of the callers. We want to prevent applications from segfaulting
140 on stack overflow when functions with huge stack frames gets
144 caller_growth_limits (struct cgraph_edge
*e
)
146 struct cgraph_node
*to
= e
->caller
;
147 struct cgraph_node
*what
= e
->callee
->ultimate_alias_target ();
150 HOST_WIDE_INT stack_size_limit
= 0, inlined_stack
;
151 inline_summary
*info
, *what_info
, *outer_info
= inline_summaries
->get (to
);
153 /* Look for function e->caller is inlined to. While doing
154 so work out the largest function body on the way. As
155 described above, we want to base our function growth
156 limits based on that. Not on the self size of the
157 outer function, not on the self size of inline code
158 we immediately inline to. This is the most relaxed
159 interpretation of the rule "do not grow large functions
160 too much in order to prevent compiler from exploding". */
163 info
= inline_summaries
->get (to
);
164 if (limit
< info
->self_size
)
165 limit
= info
->self_size
;
166 if (stack_size_limit
< info
->estimated_self_stack_size
)
167 stack_size_limit
= info
->estimated_self_stack_size
;
168 if (to
->global
.inlined_to
)
169 to
= to
->callers
->caller
;
174 what_info
= inline_summaries
->get (what
);
176 if (limit
< what_info
->self_size
)
177 limit
= what_info
->self_size
;
179 limit
+= limit
* PARAM_VALUE (PARAM_LARGE_FUNCTION_GROWTH
) / 100;
181 /* Check the size after inlining against the function limits. But allow
182 the function to shrink if it went over the limits by forced inlining. */
183 newsize
= estimate_size_after_inlining (to
, e
);
184 if (newsize
>= info
->size
185 && newsize
> PARAM_VALUE (PARAM_LARGE_FUNCTION_INSNS
)
188 e
->inline_failed
= CIF_LARGE_FUNCTION_GROWTH_LIMIT
;
192 if (!what_info
->estimated_stack_size
)
195 /* FIXME: Stack size limit often prevents inlining in Fortran programs
196 due to large i/o datastructures used by the Fortran front-end.
197 We ought to ignore this limit when we know that the edge is executed
198 on every invocation of the caller (i.e. its call statement dominates
199 exit block). We do not track this information, yet. */
200 stack_size_limit
+= ((gcov_type
)stack_size_limit
201 * PARAM_VALUE (PARAM_STACK_FRAME_GROWTH
) / 100);
203 inlined_stack
= (outer_info
->stack_frame_offset
204 + outer_info
->estimated_self_stack_size
205 + what_info
->estimated_stack_size
);
206 /* Check new stack consumption with stack consumption at the place
208 if (inlined_stack
> stack_size_limit
209 /* If function already has large stack usage from sibling
210 inline call, we can inline, too.
211 This bit overoptimistically assume that we are good at stack
213 && inlined_stack
> info
->estimated_stack_size
214 && inlined_stack
> PARAM_VALUE (PARAM_LARGE_STACK_FRAME
))
216 e
->inline_failed
= CIF_LARGE_STACK_FRAME_GROWTH_LIMIT
;
222 /* Dump info about why inlining has failed. */
225 report_inline_failed_reason (struct cgraph_edge
*e
)
229 fprintf (dump_file
, " not inlinable: %s/%i -> %s/%i, %s\n",
230 xstrdup_for_dump (e
->caller
->name ()), e
->caller
->order
,
231 xstrdup_for_dump (e
->callee
->name ()), e
->callee
->order
,
232 cgraph_inline_failed_string (e
->inline_failed
));
233 if ((e
->inline_failed
== CIF_TARGET_OPTION_MISMATCH
234 || e
->inline_failed
== CIF_OPTIMIZATION_MISMATCH
)
235 && e
->caller
->lto_file_data
236 && e
->callee
->function_symbol ()->lto_file_data
)
238 fprintf (dump_file
, " LTO objects: %s, %s\n",
239 e
->caller
->lto_file_data
->file_name
,
240 e
->callee
->function_symbol ()->lto_file_data
->file_name
);
242 if (e
->inline_failed
== CIF_TARGET_OPTION_MISMATCH
)
243 cl_target_option_print_diff
244 (dump_file
, 2, target_opts_for_fn (e
->caller
->decl
),
245 target_opts_for_fn (e
->callee
->ultimate_alias_target ()->decl
));
246 if (e
->inline_failed
== CIF_OPTIMIZATION_MISMATCH
)
247 cl_optimization_print_diff
248 (dump_file
, 2, opts_for_fn (e
->caller
->decl
),
249 opts_for_fn (e
->callee
->ultimate_alias_target ()->decl
));
253 /* Decide whether sanitizer-related attributes allow inlining. */
256 sanitize_attrs_match_for_inline_p (const_tree caller
, const_tree callee
)
258 /* Don't care if sanitizer is disabled */
259 if (!(flag_sanitize
& SANITIZE_ADDRESS
))
262 if (!caller
|| !callee
)
265 return !!lookup_attribute ("no_sanitize_address",
266 DECL_ATTRIBUTES (caller
)) ==
267 !!lookup_attribute ("no_sanitize_address",
268 DECL_ATTRIBUTES (callee
));
271 /* Used for flags where it is safe to inline when caller's value is
272 grater than callee's. */
273 #define check_maybe_up(flag) \
274 (opts_for_fn (caller->decl)->x_##flag \
275 != opts_for_fn (callee->decl)->x_##flag \
277 || opts_for_fn (caller->decl)->x_##flag \
278 < opts_for_fn (callee->decl)->x_##flag))
279 /* Used for flags where it is safe to inline when caller's value is
280 smaller than callee's. */
281 #define check_maybe_down(flag) \
282 (opts_for_fn (caller->decl)->x_##flag \
283 != opts_for_fn (callee->decl)->x_##flag \
285 || opts_for_fn (caller->decl)->x_##flag \
286 > opts_for_fn (callee->decl)->x_##flag))
287 /* Used for flags where exact match is needed for correctness. */
288 #define check_match(flag) \
289 (opts_for_fn (caller->decl)->x_##flag \
290 != opts_for_fn (callee->decl)->x_##flag)
292 /* Decide if we can inline the edge and possibly update
293 inline_failed reason.
294 We check whether inlining is possible at all and whether
295 caller growth limits allow doing so.
297 if REPORT is true, output reason to the dump file.
299 if DISREGARD_LIMITS is true, ignore size limits.*/
302 can_inline_edge_p (struct cgraph_edge
*e
, bool report
,
303 bool disregard_limits
= false, bool early
= false)
305 gcc_checking_assert (e
->inline_failed
);
307 if (cgraph_inline_failed_type (e
->inline_failed
) == CIF_FINAL_ERROR
)
310 report_inline_failed_reason (e
);
314 bool inlinable
= true;
315 enum availability avail
;
316 cgraph_node
*caller
= e
->caller
->global
.inlined_to
317 ? e
->caller
->global
.inlined_to
: e
->caller
;
318 cgraph_node
*callee
= e
->callee
->ultimate_alias_target (&avail
, caller
);
319 tree caller_tree
= DECL_FUNCTION_SPECIFIC_OPTIMIZATION (caller
->decl
);
321 = callee
? DECL_FUNCTION_SPECIFIC_OPTIMIZATION (callee
->decl
) : NULL
;
323 if (!callee
->definition
)
325 e
->inline_failed
= CIF_BODY_NOT_AVAILABLE
;
328 else if (callee
->calls_comdat_local
)
330 e
->inline_failed
= CIF_USES_COMDAT_LOCAL
;
333 else if (avail
<= AVAIL_INTERPOSABLE
)
335 e
->inline_failed
= CIF_OVERWRITABLE
;
338 else if (e
->call_stmt_cannot_inline_p
)
340 if (e
->inline_failed
!= CIF_FUNCTION_NOT_OPTIMIZED
)
341 e
->inline_failed
= CIF_MISMATCHED_ARGUMENTS
;
344 /* Don't inline if the functions have different EH personalities. */
345 else if (DECL_FUNCTION_PERSONALITY (caller
->decl
)
346 && DECL_FUNCTION_PERSONALITY (callee
->decl
)
347 && (DECL_FUNCTION_PERSONALITY (caller
->decl
)
348 != DECL_FUNCTION_PERSONALITY (callee
->decl
)))
350 e
->inline_failed
= CIF_EH_PERSONALITY
;
353 /* TM pure functions should not be inlined into non-TM_pure
355 else if (is_tm_pure (callee
->decl
) && !is_tm_pure (caller
->decl
))
357 e
->inline_failed
= CIF_UNSPECIFIED
;
360 /* Check compatibility of target optimization options. */
361 else if (!targetm
.target_option
.can_inline_p (caller
->decl
,
364 e
->inline_failed
= CIF_TARGET_OPTION_MISMATCH
;
367 else if (!inline_summaries
->get (callee
)->inlinable
)
369 e
->inline_failed
= CIF_FUNCTION_NOT_INLINABLE
;
372 else if (inline_summaries
->get (caller
)->contains_cilk_spawn
)
374 e
->inline_failed
= CIF_CILK_SPAWN
;
377 /* Don't inline a function with mismatched sanitization attributes. */
378 else if (!sanitize_attrs_match_for_inline_p (caller
->decl
, callee
->decl
))
380 e
->inline_failed
= CIF_ATTRIBUTE_MISMATCH
;
383 /* Check if caller growth allows the inlining. */
384 else if (!DECL_DISREGARD_INLINE_LIMITS (callee
->decl
)
386 && !lookup_attribute ("flatten",
387 DECL_ATTRIBUTES (caller
->decl
))
388 && !caller_growth_limits (e
))
390 /* Don't inline a function with a higher optimization level than the
391 caller. FIXME: this is really just tip of iceberg of handling
392 optimization attribute. */
393 else if (caller_tree
!= callee_tree
)
396 (DECL_DISREGARD_INLINE_LIMITS (callee
->decl
)
397 && lookup_attribute ("always_inline",
398 DECL_ATTRIBUTES (callee
->decl
)));
400 /* Until GCC 4.9 we did not check the semantics alterning flags
401 bellow and inline across optimization boundry.
402 Enabling checks bellow breaks several packages by refusing
403 to inline library always_inline functions. See PR65873.
404 Disable the check for early inlining for now until better solution
406 if (always_inline
&& early
)
408 /* There are some options that change IL semantics which means
409 we cannot inline in these cases for correctness reason.
410 Not even for always_inline declared functions. */
411 /* Strictly speaking only when the callee contains signed integer
412 math where overflow is undefined. */
413 else if ((check_maybe_up (flag_strict_overflow
)
414 /* this flag is set by optimize. Allow inlining across
415 optimize boundary. */
416 && (!opt_for_fn (caller
->decl
, optimize
)
417 == !opt_for_fn (callee
->decl
, optimize
) || !always_inline
))
418 || check_match (flag_wrapv
)
419 || check_match (flag_trapv
)
420 /* Strictly speaking only when the callee uses FP math. */
421 || check_maybe_up (flag_rounding_math
)
422 || check_maybe_up (flag_trapping_math
)
423 || check_maybe_down (flag_unsafe_math_optimizations
)
424 || check_maybe_down (flag_finite_math_only
)
425 || check_maybe_up (flag_signaling_nans
)
426 || check_maybe_down (flag_cx_limited_range
)
427 || check_maybe_up (flag_signed_zeros
)
428 || check_maybe_down (flag_associative_math
)
429 || check_maybe_down (flag_reciprocal_math
)
430 /* We do not want to make code compiled with exceptions to be
431 brought into a non-EH function unless we know that the callee
433 This is tracked by DECL_FUNCTION_PERSONALITY. */
434 || (check_maybe_up (flag_non_call_exceptions
)
435 && DECL_FUNCTION_PERSONALITY (callee
->decl
))
436 || (check_maybe_up (flag_exceptions
)
437 && DECL_FUNCTION_PERSONALITY (callee
->decl
))
438 /* Strictly speaking only when the callee contains function
439 calls that may end up setting errno. */
440 || check_maybe_up (flag_errno_math
)
441 /* When devirtualization is diabled for callee, it is not safe
442 to inline it as we possibly mangled the type info.
443 Allow early inlining of always inlines. */
444 || (!early
&& check_maybe_down (flag_devirtualize
)))
446 e
->inline_failed
= CIF_OPTIMIZATION_MISMATCH
;
449 /* gcc.dg/pr43564.c. Apply user-forced inline even at -O0. */
450 else if (always_inline
)
452 /* When user added an attribute to the callee honor it. */
453 else if (lookup_attribute ("optimize", DECL_ATTRIBUTES (callee
->decl
))
454 && opts_for_fn (caller
->decl
) != opts_for_fn (callee
->decl
))
456 e
->inline_failed
= CIF_OPTIMIZATION_MISMATCH
;
459 /* If explicit optimize attribute are not used, the mismatch is caused
460 by different command line options used to build different units.
461 Do not care about COMDAT functions - those are intended to be
462 optimized with the optimization flags of module they are used in.
463 Also do not care about mixing up size/speed optimization when
464 DECL_DISREGARD_INLINE_LIMITS is set. */
465 else if ((callee
->merged_comdat
466 && !lookup_attribute ("optimize",
467 DECL_ATTRIBUTES (caller
->decl
)))
468 || DECL_DISREGARD_INLINE_LIMITS (callee
->decl
))
470 /* If mismatch is caused by merging two LTO units with different
471 optimizationflags we want to be bit nicer. However never inline
472 if one of functions is not optimized at all. */
473 else if (!opt_for_fn (callee
->decl
, optimize
)
474 || !opt_for_fn (caller
->decl
, optimize
))
476 e
->inline_failed
= CIF_OPTIMIZATION_MISMATCH
;
479 /* If callee is optimized for size and caller is not, allow inlining if
480 code shrinks or we are in MAX_INLINE_INSNS_SINGLE limit and callee
481 is inline (and thus likely an unified comdat). This will allow caller
483 else if (opt_for_fn (callee
->decl
, optimize_size
)
484 > opt_for_fn (caller
->decl
, optimize_size
))
486 int growth
= estimate_edge_growth (e
);
488 && (!DECL_DECLARED_INLINE_P (callee
->decl
)
489 && growth
>= MAX (MAX_INLINE_INSNS_SINGLE
,
490 MAX_INLINE_INSNS_AUTO
)))
492 e
->inline_failed
= CIF_OPTIMIZATION_MISMATCH
;
496 /* If callee is more aggressively optimized for performance than caller,
497 we generally want to inline only cheap (runtime wise) functions. */
498 else if (opt_for_fn (callee
->decl
, optimize_size
)
499 < opt_for_fn (caller
->decl
, optimize_size
)
500 || (opt_for_fn (callee
->decl
, optimize
)
501 > opt_for_fn (caller
->decl
, optimize
)))
503 if (estimate_edge_time (e
)
504 >= 20 + inline_edge_summary (e
)->call_stmt_time
)
506 e
->inline_failed
= CIF_OPTIMIZATION_MISMATCH
;
513 if (!inlinable
&& report
)
514 report_inline_failed_reason (e
);
519 /* Return true if the edge E is inlinable during early inlining. */
522 can_early_inline_edge_p (struct cgraph_edge
*e
)
524 struct cgraph_node
*callee
= e
->callee
->ultimate_alias_target ();
525 /* Early inliner might get called at WPA stage when IPA pass adds new
526 function. In this case we can not really do any of early inlining
527 because function bodies are missing. */
528 if (!gimple_has_body_p (callee
->decl
))
530 e
->inline_failed
= CIF_BODY_NOT_AVAILABLE
;
533 /* In early inliner some of callees may not be in SSA form yet
534 (i.e. the callgraph is cyclic and we did not process
535 the callee by early inliner, yet). We don't have CIF code for this
536 case; later we will re-do the decision in the real inliner. */
537 if (!gimple_in_ssa_p (DECL_STRUCT_FUNCTION (e
->caller
->decl
))
538 || !gimple_in_ssa_p (DECL_STRUCT_FUNCTION (callee
->decl
)))
541 fprintf (dump_file
, " edge not inlinable: not in SSA form\n");
544 if (!can_inline_edge_p (e
, true, false, true))
550 /* Return number of calls in N. Ignore cheap builtins. */
553 num_calls (struct cgraph_node
*n
)
555 struct cgraph_edge
*e
;
558 for (e
= n
->callees
; e
; e
= e
->next_callee
)
559 if (!is_inexpensive_builtin (e
->callee
->decl
))
565 /* Return true if we are interested in inlining small function. */
568 want_early_inline_function_p (struct cgraph_edge
*e
)
570 bool want_inline
= true;
571 struct cgraph_node
*callee
= e
->callee
->ultimate_alias_target ();
573 if (DECL_DISREGARD_INLINE_LIMITS (callee
->decl
))
575 /* For AutoFDO, we need to make sure that before profile summary, all
576 hot paths' IR look exactly the same as profiled binary. As a result,
577 in einliner, we will disregard size limit and inline those callsites
579 * inlined in the profiled binary, and
580 * the cloned callee has enough samples to be considered "hot". */
581 else if (flag_auto_profile
&& afdo_callsite_hot_enough_for_early_inline (e
))
583 else if (!DECL_DECLARED_INLINE_P (callee
->decl
)
584 && !opt_for_fn (e
->caller
->decl
, flag_inline_small_functions
))
586 e
->inline_failed
= CIF_FUNCTION_NOT_INLINE_CANDIDATE
;
587 report_inline_failed_reason (e
);
592 int growth
= estimate_edge_growth (e
);
597 else if (!e
->maybe_hot_p ()
601 fprintf (dump_file
, " will not early inline: %s/%i->%s/%i, "
602 "call is cold and code would grow by %i\n",
603 xstrdup_for_dump (e
->caller
->name ()),
605 xstrdup_for_dump (callee
->name ()), callee
->order
,
609 else if (growth
> PARAM_VALUE (PARAM_EARLY_INLINING_INSNS
))
612 fprintf (dump_file
, " will not early inline: %s/%i->%s/%i, "
613 "growth %i exceeds --param early-inlining-insns\n",
614 xstrdup_for_dump (e
->caller
->name ()),
616 xstrdup_for_dump (callee
->name ()), callee
->order
,
620 else if ((n
= num_calls (callee
)) != 0
621 && growth
* (n
+ 1) > PARAM_VALUE (PARAM_EARLY_INLINING_INSNS
))
624 fprintf (dump_file
, " will not early inline: %s/%i->%s/%i, "
625 "growth %i exceeds --param early-inlining-insns "
626 "divided by number of calls\n",
627 xstrdup_for_dump (e
->caller
->name ()),
629 xstrdup_for_dump (callee
->name ()), callee
->order
,
637 /* Compute time of the edge->caller + edge->callee execution when inlining
641 compute_uninlined_call_time (struct inline_summary
*callee_info
,
642 struct cgraph_edge
*edge
)
644 sreal uninlined_call_time
= (sreal
)callee_info
->time
;
645 cgraph_node
*caller
= (edge
->caller
->global
.inlined_to
646 ? edge
->caller
->global
.inlined_to
649 if (edge
->count
&& caller
->count
)
650 uninlined_call_time
*= (sreal
)edge
->count
/ caller
->count
;
652 uninlined_call_time
*= cgraph_freq_base_rec
* edge
->frequency
;
654 uninlined_call_time
= uninlined_call_time
>> 11;
656 int caller_time
= inline_summaries
->get (caller
)->time
;
657 return uninlined_call_time
+ caller_time
;
660 /* Same as compute_uinlined_call_time but compute time when inlining
664 compute_inlined_call_time (struct cgraph_edge
*edge
,
667 cgraph_node
*caller
= (edge
->caller
->global
.inlined_to
668 ? edge
->caller
->global
.inlined_to
670 int caller_time
= inline_summaries
->get (caller
)->time
;
671 sreal time
= edge_time
;
673 if (edge
->count
&& caller
->count
)
674 time
*= (sreal
)edge
->count
/ caller
->count
;
676 time
*= cgraph_freq_base_rec
* edge
->frequency
;
680 /* This calculation should match one in ipa-inline-analysis.
681 FIXME: Once ipa-inline-analysis is converted to sreal this can be
683 time
-= (sreal
) ((gcov_type
) edge
->frequency
684 * inline_edge_summary (edge
)->call_stmt_time
685 * (INLINE_TIME_SCALE
/ CGRAPH_FREQ_BASE
)) / INLINE_TIME_SCALE
;
688 time
= ((sreal
) 1) >> 8;
689 gcc_checking_assert (time
>= 0);
693 /* Return true if the speedup for inlining E is bigger than
694 PARAM_MAX_INLINE_MIN_SPEEDUP. */
697 big_speedup_p (struct cgraph_edge
*e
)
699 sreal time
= compute_uninlined_call_time (inline_summaries
->get (e
->callee
),
701 sreal inlined_time
= compute_inlined_call_time (e
, estimate_edge_time (e
));
703 if (time
- inlined_time
704 > (sreal
) time
* PARAM_VALUE (PARAM_INLINE_MIN_SPEEDUP
)
710 /* Return true if we are interested in inlining small function.
711 When REPORT is true, report reason to dump file. */
714 want_inline_small_function_p (struct cgraph_edge
*e
, bool report
)
716 bool want_inline
= true;
717 struct cgraph_node
*callee
= e
->callee
->ultimate_alias_target ();
719 if (DECL_DISREGARD_INLINE_LIMITS (callee
->decl
))
721 else if (!DECL_DECLARED_INLINE_P (callee
->decl
)
722 && !opt_for_fn (e
->caller
->decl
, flag_inline_small_functions
))
724 e
->inline_failed
= CIF_FUNCTION_NOT_INLINE_CANDIDATE
;
727 /* Do fast and conservative check if the function can be good
728 inline candidate. At the moment we allow inline hints to
729 promote non-inline functions to inline and we increase
730 MAX_INLINE_INSNS_SINGLE 16-fold for inline functions. */
731 else if ((!DECL_DECLARED_INLINE_P (callee
->decl
)
732 && (!e
->count
|| !e
->maybe_hot_p ()))
733 && inline_summaries
->get (callee
)->min_size
734 - inline_edge_summary (e
)->call_stmt_size
735 > MAX (MAX_INLINE_INSNS_SINGLE
, MAX_INLINE_INSNS_AUTO
))
737 e
->inline_failed
= CIF_MAX_INLINE_INSNS_AUTO_LIMIT
;
740 else if ((DECL_DECLARED_INLINE_P (callee
->decl
) || e
->count
)
741 && inline_summaries
->get (callee
)->min_size
742 - inline_edge_summary (e
)->call_stmt_size
743 > 16 * MAX_INLINE_INSNS_SINGLE
)
745 e
->inline_failed
= (DECL_DECLARED_INLINE_P (callee
->decl
)
746 ? CIF_MAX_INLINE_INSNS_SINGLE_LIMIT
747 : CIF_MAX_INLINE_INSNS_AUTO_LIMIT
);
752 int growth
= estimate_edge_growth (e
);
753 inline_hints hints
= estimate_edge_hints (e
);
754 bool big_speedup
= big_speedup_p (e
);
758 /* Apply MAX_INLINE_INSNS_SINGLE limit. Do not do so when
759 hints suggests that inlining given function is very profitable. */
760 else if (DECL_DECLARED_INLINE_P (callee
->decl
)
761 && growth
>= MAX_INLINE_INSNS_SINGLE
763 && !(hints
& (INLINE_HINT_indirect_call
764 | INLINE_HINT_known_hot
765 | INLINE_HINT_loop_iterations
766 | INLINE_HINT_array_index
767 | INLINE_HINT_loop_stride
)))
768 || growth
>= MAX_INLINE_INSNS_SINGLE
* 16))
770 e
->inline_failed
= CIF_MAX_INLINE_INSNS_SINGLE_LIMIT
;
773 else if (!DECL_DECLARED_INLINE_P (callee
->decl
)
774 && !opt_for_fn (e
->caller
->decl
, flag_inline_functions
))
776 /* growth_likely_positive is expensive, always test it last. */
777 if (growth
>= MAX_INLINE_INSNS_SINGLE
778 || growth_likely_positive (callee
, growth
))
780 e
->inline_failed
= CIF_NOT_DECLARED_INLINED
;
784 /* Apply MAX_INLINE_INSNS_AUTO limit for functions not declared inline
785 Upgrade it to MAX_INLINE_INSNS_SINGLE when hints suggests that
786 inlining given function is very profitable. */
787 else if (!DECL_DECLARED_INLINE_P (callee
->decl
)
789 && !(hints
& INLINE_HINT_known_hot
)
790 && growth
>= ((hints
& (INLINE_HINT_indirect_call
791 | INLINE_HINT_loop_iterations
792 | INLINE_HINT_array_index
793 | INLINE_HINT_loop_stride
))
794 ? MAX (MAX_INLINE_INSNS_AUTO
,
795 MAX_INLINE_INSNS_SINGLE
)
796 : MAX_INLINE_INSNS_AUTO
))
798 /* growth_likely_positive is expensive, always test it last. */
799 if (growth
>= MAX_INLINE_INSNS_SINGLE
800 || growth_likely_positive (callee
, growth
))
802 e
->inline_failed
= CIF_MAX_INLINE_INSNS_AUTO_LIMIT
;
806 /* If call is cold, do not inline when function body would grow. */
807 else if (!e
->maybe_hot_p ()
808 && (growth
>= MAX_INLINE_INSNS_SINGLE
809 || growth_likely_positive (callee
, growth
)))
811 e
->inline_failed
= CIF_UNLIKELY_CALL
;
815 if (!want_inline
&& report
)
816 report_inline_failed_reason (e
);
820 /* EDGE is self recursive edge.
821 We hand two cases - when function A is inlining into itself
822 or when function A is being inlined into another inliner copy of function
825 In first case OUTER_NODE points to the toplevel copy of A, while
826 in the second case OUTER_NODE points to the outermost copy of A in B.
828 In both cases we want to be extra selective since
829 inlining the call will just introduce new recursive calls to appear. */
832 want_inline_self_recursive_call_p (struct cgraph_edge
*edge
,
833 struct cgraph_node
*outer_node
,
837 char const *reason
= NULL
;
838 bool want_inline
= true;
839 int caller_freq
= CGRAPH_FREQ_BASE
;
840 int max_depth
= PARAM_VALUE (PARAM_MAX_INLINE_RECURSIVE_DEPTH_AUTO
);
842 if (DECL_DECLARED_INLINE_P (edge
->caller
->decl
))
843 max_depth
= PARAM_VALUE (PARAM_MAX_INLINE_RECURSIVE_DEPTH
);
845 if (!edge
->maybe_hot_p ())
847 reason
= "recursive call is cold";
850 else if (max_count
&& !outer_node
->count
)
852 reason
= "not executed in profile";
855 else if (depth
> max_depth
)
857 reason
= "--param max-inline-recursive-depth exceeded.";
861 if (outer_node
->global
.inlined_to
)
862 caller_freq
= outer_node
->callers
->frequency
;
866 reason
= "function is inlined and unlikely";
872 /* Inlining of self recursive function into copy of itself within other function
873 is transformation similar to loop peeling.
875 Peeling is profitable if we can inline enough copies to make probability
876 of actual call to the self recursive function very small. Be sure that
877 the probability of recursion is small.
879 We ensure that the frequency of recursing is at most 1 - (1/max_depth).
880 This way the expected number of recision is at most max_depth. */
883 int max_prob
= CGRAPH_FREQ_BASE
- ((CGRAPH_FREQ_BASE
+ max_depth
- 1)
886 for (i
= 1; i
< depth
; i
++)
887 max_prob
= max_prob
* max_prob
/ CGRAPH_FREQ_BASE
;
889 && (edge
->count
* CGRAPH_FREQ_BASE
/ outer_node
->count
892 reason
= "profile of recursive call is too large";
896 && (edge
->frequency
* CGRAPH_FREQ_BASE
/ caller_freq
899 reason
= "frequency of recursive call is too large";
903 /* Recursive inlining, i.e. equivalent of unrolling, is profitable if recursion
904 depth is large. We reduce function call overhead and increase chances that
905 things fit in hardware return predictor.
907 Recursive inlining might however increase cost of stack frame setup
908 actually slowing down functions whose recursion tree is wide rather than
911 Deciding reliably on when to do recursive inlining without profile feedback
912 is tricky. For now we disable recursive inlining when probability of self
915 Recursive inlining of self recursive call within loop also results in large loop
916 depths that generally optimize badly. We may want to throttle down inlining
917 in those cases. In particular this seems to happen in one of libstdc++ rb tree
922 && (edge
->count
* 100 / outer_node
->count
923 <= PARAM_VALUE (PARAM_MIN_INLINE_RECURSIVE_PROBABILITY
)))
925 reason
= "profile of recursive call is too small";
929 && (edge
->frequency
* 100 / caller_freq
930 <= PARAM_VALUE (PARAM_MIN_INLINE_RECURSIVE_PROBABILITY
)))
932 reason
= "frequency of recursive call is too small";
936 if (!want_inline
&& dump_file
)
937 fprintf (dump_file
, " not inlining recursively: %s\n", reason
);
941 /* Return true when NODE has uninlinable caller;
942 set HAS_HOT_CALL if it has hot call.
943 Worker for cgraph_for_node_and_aliases. */
946 check_callers (struct cgraph_node
*node
, void *has_hot_call
)
948 struct cgraph_edge
*e
;
949 for (e
= node
->callers
; e
; e
= e
->next_caller
)
951 if (!opt_for_fn (e
->caller
->decl
, flag_inline_functions_called_once
))
953 if (!can_inline_edge_p (e
, true))
955 if (e
->recursive_p ())
957 if (!(*(bool *)has_hot_call
) && e
->maybe_hot_p ())
958 *(bool *)has_hot_call
= true;
963 /* If NODE has a caller, return true. */
966 has_caller_p (struct cgraph_node
*node
, void *data ATTRIBUTE_UNUSED
)
973 /* Decide if inlining NODE would reduce unit size by eliminating
974 the offline copy of function.
975 When COLD is true the cold calls are considered, too. */
978 want_inline_function_to_all_callers_p (struct cgraph_node
*node
, bool cold
)
980 bool has_hot_call
= false;
982 /* Aliases gets inlined along with the function they alias. */
985 /* Already inlined? */
986 if (node
->global
.inlined_to
)
988 /* Does it have callers? */
989 if (!node
->call_for_symbol_and_aliases (has_caller_p
, NULL
, true))
991 /* Inlining into all callers would increase size? */
992 if (estimate_growth (node
) > 0)
994 /* All inlines must be possible. */
995 if (node
->call_for_symbol_and_aliases (check_callers
, &has_hot_call
,
998 if (!cold
&& !has_hot_call
)
1003 /* A cost model driving the inlining heuristics in a way so the edges with
1004 smallest badness are inlined first. After each inlining is performed
1005 the costs of all caller edges of nodes affected are recomputed so the
1006 metrics may accurately depend on values such as number of inlinable callers
1007 of the function or function body size. */
1010 edge_badness (struct cgraph_edge
*edge
, bool dump
)
1013 int growth
, edge_time
;
1014 struct cgraph_node
*callee
= edge
->callee
->ultimate_alias_target ();
1015 struct inline_summary
*callee_info
= inline_summaries
->get (callee
);
1017 cgraph_node
*caller
= (edge
->caller
->global
.inlined_to
1018 ? edge
->caller
->global
.inlined_to
1021 growth
= estimate_edge_growth (edge
);
1022 edge_time
= estimate_edge_time (edge
);
1023 hints
= estimate_edge_hints (edge
);
1024 gcc_checking_assert (edge_time
>= 0);
1025 gcc_checking_assert (edge_time
<= callee_info
->time
);
1026 gcc_checking_assert (growth
<= callee_info
->size
);
1030 fprintf (dump_file
, " Badness calculation for %s/%i -> %s/%i\n",
1031 xstrdup_for_dump (edge
->caller
->name ()),
1032 edge
->caller
->order
,
1033 xstrdup_for_dump (callee
->name ()),
1034 edge
->callee
->order
);
1035 fprintf (dump_file
, " size growth %i, time %i ",
1038 dump_inline_hints (dump_file
, hints
);
1039 if (big_speedup_p (edge
))
1040 fprintf (dump_file
, " big_speedup");
1041 fprintf (dump_file
, "\n");
1044 /* Always prefer inlining saving code size. */
1047 badness
= (sreal
) (-SREAL_MIN_SIG
+ growth
) << (SREAL_MAX_EXP
/ 256);
1049 fprintf (dump_file
, " %f: Growth %d <= 0\n", badness
.to_double (),
1052 /* Inlining into EXTERNAL functions is not going to change anything unless
1053 they are themselves inlined. */
1054 else if (DECL_EXTERNAL (caller
->decl
))
1057 fprintf (dump_file
, " max: function is external\n");
1058 return sreal::max ();
1060 /* When profile is available. Compute badness as:
1062 time_saved * caller_count
1063 goodness = -------------------------------------------------
1064 growth_of_caller * overall_growth * combined_size
1066 badness = - goodness
1068 Again use negative value to make calls with profile appear hotter
1071 else if (opt_for_fn (caller
->decl
, flag_guess_branch_prob
) || caller
->count
)
1073 sreal numerator
, denominator
;
1076 numerator
= (compute_uninlined_call_time (callee_info
, edge
)
1077 - compute_inlined_call_time (edge
, edge_time
));
1079 numerator
= ((sreal
) 1 >> 8);
1081 numerator
*= caller
->count
;
1082 else if (opt_for_fn (caller
->decl
, flag_branch_probabilities
))
1083 numerator
= numerator
>> 11;
1084 denominator
= growth
;
1086 overall_growth
= callee_info
->growth
;
1088 /* Look for inliner wrappers of the form:
1094 noninline_callee ();
1096 Withhout panilizing this case, we usually inline noninline_callee
1097 into the inline_caller because overall_growth is small preventing
1098 further inlining of inline_caller.
1100 Penalize only callgraph edges to functions with small overall
1103 if (growth
> overall_growth
1104 /* ... and having only one caller which is not inlined ... */
1105 && callee_info
->single_caller
1106 && !edge
->caller
->global
.inlined_to
1107 /* ... and edges executed only conditionally ... */
1108 && edge
->frequency
< CGRAPH_FREQ_BASE
1109 /* ... consider case where callee is not inline but caller is ... */
1110 && ((!DECL_DECLARED_INLINE_P (edge
->callee
->decl
)
1111 && DECL_DECLARED_INLINE_P (caller
->decl
))
1112 /* ... or when early optimizers decided to split and edge
1113 frequency still indicates splitting is a win ... */
1114 || (callee
->split_part
&& !caller
->split_part
1118 (PARAM_PARTIAL_INLINING_ENTRY_PROBABILITY
) / 100
1119 /* ... and do not overwrite user specified hints. */
1120 && (!DECL_DECLARED_INLINE_P (edge
->callee
->decl
)
1121 || DECL_DECLARED_INLINE_P (caller
->decl
)))))
1123 struct inline_summary
*caller_info
= inline_summaries
->get (caller
);
1124 int caller_growth
= caller_info
->growth
;
1126 /* Only apply the penalty when caller looks like inline candidate,
1127 and it is not called once and. */
1128 if (!caller_info
->single_caller
&& overall_growth
< caller_growth
1129 && caller_info
->inlinable
1130 && caller_info
->size
1131 < (DECL_DECLARED_INLINE_P (caller
->decl
)
1132 ? MAX_INLINE_INSNS_SINGLE
: MAX_INLINE_INSNS_AUTO
))
1136 " Wrapper penalty. Increasing growth %i to %i\n",
1137 overall_growth
, caller_growth
);
1138 overall_growth
= caller_growth
;
1141 if (overall_growth
> 0)
1143 /* Strongly preffer functions with few callers that can be inlined
1144 fully. The square root here leads to smaller binaries at average.
1145 Watch however for extreme cases and return to linear function
1146 when growth is large. */
1147 if (overall_growth
< 256)
1148 overall_growth
*= overall_growth
;
1150 overall_growth
+= 256 * 256 - 256;
1151 denominator
*= overall_growth
;
1153 denominator
*= inline_summaries
->get (caller
)->self_size
+ growth
;
1155 badness
= - numerator
/ denominator
;
1160 " %f: guessed profile. frequency %f, count %" PRId64
1161 " caller count %" PRId64
1162 " time w/o inlining %f, time w inlining %f"
1163 " overall growth %i (current) %i (original)"
1164 " %i (compensated)\n",
1165 badness
.to_double (),
1166 (double)edge
->frequency
/ CGRAPH_FREQ_BASE
,
1167 edge
->count
, caller
->count
,
1168 compute_uninlined_call_time (callee_info
, edge
).to_double (),
1169 compute_inlined_call_time (edge
, edge_time
).to_double (),
1170 estimate_growth (callee
),
1171 callee_info
->growth
, overall_growth
);
1174 /* When function local profile is not available or it does not give
1175 useful information (ie frequency is zero), base the cost on
1176 loop nest and overall size growth, so we optimize for overall number
1177 of functions fully inlined in program. */
1180 int nest
= MIN (inline_edge_summary (edge
)->loop_depth
, 8);
1183 /* Decrease badness if call is nested. */
1185 badness
= badness
>> nest
;
1187 badness
= badness
<< nest
;
1189 fprintf (dump_file
, " %f: no profile. nest %i\n",
1190 badness
.to_double (), nest
);
1192 gcc_checking_assert (badness
!= 0);
1194 if (edge
->recursive_p ())
1195 badness
= badness
.shift (badness
> 0 ? 4 : -4);
1196 if ((hints
& (INLINE_HINT_indirect_call
1197 | INLINE_HINT_loop_iterations
1198 | INLINE_HINT_array_index
1199 | INLINE_HINT_loop_stride
))
1200 || callee_info
->growth
<= 0)
1201 badness
= badness
.shift (badness
> 0 ? -2 : 2);
1202 if (hints
& (INLINE_HINT_same_scc
))
1203 badness
= badness
.shift (badness
> 0 ? 3 : -3);
1204 else if (hints
& (INLINE_HINT_in_scc
))
1205 badness
= badness
.shift (badness
> 0 ? 2 : -2);
1206 else if (hints
& (INLINE_HINT_cross_module
))
1207 badness
= badness
.shift (badness
> 0 ? 1 : -1);
1208 if (DECL_DISREGARD_INLINE_LIMITS (callee
->decl
))
1209 badness
= badness
.shift (badness
> 0 ? -4 : 4);
1210 else if ((hints
& INLINE_HINT_declared_inline
))
1211 badness
= badness
.shift (badness
> 0 ? -3 : 3);
1213 fprintf (dump_file
, " Adjusted by hints %f\n", badness
.to_double ());
1217 /* Recompute badness of EDGE and update its key in HEAP if needed. */
1219 update_edge_key (edge_heap_t
*heap
, struct cgraph_edge
*edge
)
1221 sreal badness
= edge_badness (edge
, false);
1224 edge_heap_node_t
*n
= (edge_heap_node_t
*) edge
->aux
;
1225 gcc_checking_assert (n
->get_data () == edge
);
1227 /* fibonacci_heap::replace_key does busy updating of the
1228 heap that is unnecesarily expensive.
1229 We do lazy increases: after extracting minimum if the key
1230 turns out to be out of date, it is re-inserted into heap
1231 with correct value. */
1232 if (badness
< n
->get_key ())
1234 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1237 " decreasing badness %s/%i -> %s/%i, %f"
1239 xstrdup_for_dump (edge
->caller
->name ()),
1240 edge
->caller
->order
,
1241 xstrdup_for_dump (edge
->callee
->name ()),
1242 edge
->callee
->order
,
1243 n
->get_key ().to_double (),
1244 badness
.to_double ());
1246 heap
->decrease_key (n
, badness
);
1251 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1254 " enqueuing call %s/%i -> %s/%i, badness %f\n",
1255 xstrdup_for_dump (edge
->caller
->name ()),
1256 edge
->caller
->order
,
1257 xstrdup_for_dump (edge
->callee
->name ()),
1258 edge
->callee
->order
,
1259 badness
.to_double ());
1261 edge
->aux
= heap
->insert (badness
, edge
);
1266 /* NODE was inlined.
1267 All caller edges needs to be resetted because
1268 size estimates change. Similarly callees needs reset
1269 because better context may be known. */
1272 reset_edge_caches (struct cgraph_node
*node
)
1274 struct cgraph_edge
*edge
;
1275 struct cgraph_edge
*e
= node
->callees
;
1276 struct cgraph_node
*where
= node
;
1277 struct ipa_ref
*ref
;
1279 if (where
->global
.inlined_to
)
1280 where
= where
->global
.inlined_to
;
1282 for (edge
= where
->callers
; edge
; edge
= edge
->next_caller
)
1283 if (edge
->inline_failed
)
1284 reset_edge_growth_cache (edge
);
1286 FOR_EACH_ALIAS (where
, ref
)
1287 reset_edge_caches (dyn_cast
<cgraph_node
*> (ref
->referring
));
1293 if (!e
->inline_failed
&& e
->callee
->callees
)
1294 e
= e
->callee
->callees
;
1297 if (e
->inline_failed
)
1298 reset_edge_growth_cache (e
);
1305 if (e
->caller
== node
)
1307 e
= e
->caller
->callers
;
1309 while (!e
->next_callee
);
1315 /* Recompute HEAP nodes for each of caller of NODE.
1316 UPDATED_NODES track nodes we already visited, to avoid redundant work.
1317 When CHECK_INLINABLITY_FOR is set, re-check for specified edge that
1318 it is inlinable. Otherwise check all edges. */
1321 update_caller_keys (edge_heap_t
*heap
, struct cgraph_node
*node
,
1322 bitmap updated_nodes
,
1323 struct cgraph_edge
*check_inlinablity_for
)
1325 struct cgraph_edge
*edge
;
1326 struct ipa_ref
*ref
;
1328 if ((!node
->alias
&& !inline_summaries
->get (node
)->inlinable
)
1329 || node
->global
.inlined_to
)
1331 if (!bitmap_set_bit (updated_nodes
, node
->uid
))
1334 FOR_EACH_ALIAS (node
, ref
)
1336 struct cgraph_node
*alias
= dyn_cast
<cgraph_node
*> (ref
->referring
);
1337 update_caller_keys (heap
, alias
, updated_nodes
, check_inlinablity_for
);
1340 for (edge
= node
->callers
; edge
; edge
= edge
->next_caller
)
1341 if (edge
->inline_failed
)
1343 if (!check_inlinablity_for
1344 || check_inlinablity_for
== edge
)
1346 if (can_inline_edge_p (edge
, false)
1347 && want_inline_small_function_p (edge
, false))
1348 update_edge_key (heap
, edge
);
1351 report_inline_failed_reason (edge
);
1352 heap
->delete_node ((edge_heap_node_t
*) edge
->aux
);
1357 update_edge_key (heap
, edge
);
1361 /* Recompute HEAP nodes for each uninlined call in NODE.
1362 This is used when we know that edge badnesses are going only to increase
1363 (we introduced new call site) and thus all we need is to insert newly
1364 created edges into heap. */
1367 update_callee_keys (edge_heap_t
*heap
, struct cgraph_node
*node
,
1368 bitmap updated_nodes
)
1370 struct cgraph_edge
*e
= node
->callees
;
1375 if (!e
->inline_failed
&& e
->callee
->callees
)
1376 e
= e
->callee
->callees
;
1379 enum availability avail
;
1380 struct cgraph_node
*callee
;
1381 /* We do not reset callee growth cache here. Since we added a new call,
1382 growth chould have just increased and consequentely badness metric
1383 don't need updating. */
1384 if (e
->inline_failed
1385 && (callee
= e
->callee
->ultimate_alias_target (&avail
, e
->caller
))
1386 && inline_summaries
->get (callee
)->inlinable
1387 && avail
>= AVAIL_AVAILABLE
1388 && !bitmap_bit_p (updated_nodes
, callee
->uid
))
1390 if (can_inline_edge_p (e
, false)
1391 && want_inline_small_function_p (e
, false))
1392 update_edge_key (heap
, e
);
1395 report_inline_failed_reason (e
);
1396 heap
->delete_node ((edge_heap_node_t
*) e
->aux
);
1406 if (e
->caller
== node
)
1408 e
= e
->caller
->callers
;
1410 while (!e
->next_callee
);
1416 /* Enqueue all recursive calls from NODE into priority queue depending on
1417 how likely we want to recursively inline the call. */
1420 lookup_recursive_calls (struct cgraph_node
*node
, struct cgraph_node
*where
,
1423 struct cgraph_edge
*e
;
1424 enum availability avail
;
1426 for (e
= where
->callees
; e
; e
= e
->next_callee
)
1427 if (e
->callee
== node
1428 || (e
->callee
->ultimate_alias_target (&avail
, e
->caller
) == node
1429 && avail
> AVAIL_INTERPOSABLE
))
1431 /* When profile feedback is available, prioritize by expected number
1433 heap
->insert (!max_count
? -e
->frequency
1434 : -(e
->count
/ ((max_count
+ (1<<24) - 1) / (1<<24))),
1437 for (e
= where
->callees
; e
; e
= e
->next_callee
)
1438 if (!e
->inline_failed
)
1439 lookup_recursive_calls (node
, e
->callee
, heap
);
1442 /* Decide on recursive inlining: in the case function has recursive calls,
1443 inline until body size reaches given argument. If any new indirect edges
1444 are discovered in the process, add them to *NEW_EDGES, unless NEW_EDGES
1448 recursive_inlining (struct cgraph_edge
*edge
,
1449 vec
<cgraph_edge
*> *new_edges
)
1451 int limit
= PARAM_VALUE (PARAM_MAX_INLINE_INSNS_RECURSIVE_AUTO
);
1452 edge_heap_t
heap (sreal::min ());
1453 struct cgraph_node
*node
;
1454 struct cgraph_edge
*e
;
1455 struct cgraph_node
*master_clone
= NULL
, *next
;
1459 node
= edge
->caller
;
1460 if (node
->global
.inlined_to
)
1461 node
= node
->global
.inlined_to
;
1463 if (DECL_DECLARED_INLINE_P (node
->decl
))
1464 limit
= PARAM_VALUE (PARAM_MAX_INLINE_INSNS_RECURSIVE
);
1466 /* Make sure that function is small enough to be considered for inlining. */
1467 if (estimate_size_after_inlining (node
, edge
) >= limit
)
1469 lookup_recursive_calls (node
, node
, &heap
);
1475 " Performing recursive inlining on %s\n",
1478 /* Do the inlining and update list of recursive call during process. */
1479 while (!heap
.empty ())
1481 struct cgraph_edge
*curr
= heap
.extract_min ();
1482 struct cgraph_node
*cnode
, *dest
= curr
->callee
;
1484 if (!can_inline_edge_p (curr
, true))
1487 /* MASTER_CLONE is produced in the case we already started modified
1488 the function. Be sure to redirect edge to the original body before
1489 estimating growths otherwise we will be seeing growths after inlining
1490 the already modified body. */
1493 curr
->redirect_callee (master_clone
);
1494 reset_edge_growth_cache (curr
);
1497 if (estimate_size_after_inlining (node
, curr
) > limit
)
1499 curr
->redirect_callee (dest
);
1500 reset_edge_growth_cache (curr
);
1505 for (cnode
= curr
->caller
;
1506 cnode
->global
.inlined_to
; cnode
= cnode
->callers
->caller
)
1508 == curr
->callee
->ultimate_alias_target ()->decl
)
1511 if (!want_inline_self_recursive_call_p (curr
, node
, false, depth
))
1513 curr
->redirect_callee (dest
);
1514 reset_edge_growth_cache (curr
);
1521 " Inlining call of depth %i", depth
);
1524 fprintf (dump_file
, " called approx. %.2f times per call",
1525 (double)curr
->count
/ node
->count
);
1527 fprintf (dump_file
, "\n");
1531 /* We need original clone to copy around. */
1532 master_clone
= node
->create_clone (node
->decl
, node
->count
,
1533 CGRAPH_FREQ_BASE
, false, vNULL
,
1535 for (e
= master_clone
->callees
; e
; e
= e
->next_callee
)
1536 if (!e
->inline_failed
)
1537 clone_inlined_nodes (e
, true, false, NULL
, CGRAPH_FREQ_BASE
);
1538 curr
->redirect_callee (master_clone
);
1539 reset_edge_growth_cache (curr
);
1542 inline_call (curr
, false, new_edges
, &overall_size
, true);
1543 lookup_recursive_calls (node
, curr
->callee
, &heap
);
1547 if (!heap
.empty () && dump_file
)
1548 fprintf (dump_file
, " Recursive inlining growth limit met.\n");
1555 "\n Inlined %i times, "
1556 "body grown from size %i to %i, time %i to %i\n", n
,
1557 inline_summaries
->get (master_clone
)->size
, inline_summaries
->get (node
)->size
,
1558 inline_summaries
->get (master_clone
)->time
, inline_summaries
->get (node
)->time
);
1560 /* Remove master clone we used for inlining. We rely that clones inlined
1561 into master clone gets queued just before master clone so we don't
1563 for (node
= symtab
->first_function (); node
!= master_clone
;
1566 next
= symtab
->next_function (node
);
1567 if (node
->global
.inlined_to
== master_clone
)
1570 master_clone
->remove ();
1575 /* Given whole compilation unit estimate of INSNS, compute how large we can
1576 allow the unit to grow. */
1579 compute_max_insns (int insns
)
1581 int max_insns
= insns
;
1582 if (max_insns
< PARAM_VALUE (PARAM_LARGE_UNIT_INSNS
))
1583 max_insns
= PARAM_VALUE (PARAM_LARGE_UNIT_INSNS
);
1585 return ((int64_t) max_insns
1586 * (100 + PARAM_VALUE (PARAM_INLINE_UNIT_GROWTH
)) / 100);
1590 /* Compute badness of all edges in NEW_EDGES and add them to the HEAP. */
1593 add_new_edges_to_heap (edge_heap_t
*heap
, vec
<cgraph_edge
*> new_edges
)
1595 while (new_edges
.length () > 0)
1597 struct cgraph_edge
*edge
= new_edges
.pop ();
1599 gcc_assert (!edge
->aux
);
1600 if (edge
->inline_failed
1601 && can_inline_edge_p (edge
, true)
1602 && want_inline_small_function_p (edge
, true))
1603 edge
->aux
= heap
->insert (edge_badness (edge
, false), edge
);
1607 /* Remove EDGE from the fibheap. */
1610 heap_edge_removal_hook (struct cgraph_edge
*e
, void *data
)
1614 ((edge_heap_t
*)data
)->delete_node ((edge_heap_node_t
*)e
->aux
);
1619 /* Return true if speculation of edge E seems useful.
1620 If ANTICIPATE_INLINING is true, be conservative and hope that E
1624 speculation_useful_p (struct cgraph_edge
*e
, bool anticipate_inlining
)
1626 enum availability avail
;
1627 struct cgraph_node
*target
= e
->callee
->ultimate_alias_target (&avail
,
1629 struct cgraph_edge
*direct
, *indirect
;
1630 struct ipa_ref
*ref
;
1632 gcc_assert (e
->speculative
&& !e
->indirect_unknown_callee
);
1634 if (!e
->maybe_hot_p ())
1637 /* See if IP optimizations found something potentially useful about the
1638 function. For now we look only for CONST/PURE flags. Almost everything
1639 else we propagate is useless. */
1640 if (avail
>= AVAIL_AVAILABLE
)
1642 int ecf_flags
= flags_from_decl_or_type (target
->decl
);
1643 if (ecf_flags
& ECF_CONST
)
1645 e
->speculative_call_info (direct
, indirect
, ref
);
1646 if (!(indirect
->indirect_info
->ecf_flags
& ECF_CONST
))
1649 else if (ecf_flags
& ECF_PURE
)
1651 e
->speculative_call_info (direct
, indirect
, ref
);
1652 if (!(indirect
->indirect_info
->ecf_flags
& ECF_PURE
))
1656 /* If we did not managed to inline the function nor redirect
1657 to an ipa-cp clone (that are seen by having local flag set),
1658 it is probably pointless to inline it unless hardware is missing
1659 indirect call predictor. */
1660 if (!anticipate_inlining
&& e
->inline_failed
&& !target
->local
.local
)
1662 /* For overwritable targets there is not much to do. */
1663 if (e
->inline_failed
&& !can_inline_edge_p (e
, false, true))
1665 /* OK, speculation seems interesting. */
1669 /* We know that EDGE is not going to be inlined.
1670 See if we can remove speculation. */
1673 resolve_noninline_speculation (edge_heap_t
*edge_heap
, struct cgraph_edge
*edge
)
1675 if (edge
->speculative
&& !speculation_useful_p (edge
, false))
1677 struct cgraph_node
*node
= edge
->caller
;
1678 struct cgraph_node
*where
= node
->global
.inlined_to
1679 ? node
->global
.inlined_to
: node
;
1680 bitmap updated_nodes
= BITMAP_ALLOC (NULL
);
1682 spec_rem
+= edge
->count
;
1683 edge
->resolve_speculation ();
1684 reset_edge_caches (where
);
1685 inline_update_overall_summary (where
);
1686 update_caller_keys (edge_heap
, where
,
1687 updated_nodes
, NULL
);
1688 update_callee_keys (edge_heap
, where
,
1690 BITMAP_FREE (updated_nodes
);
1694 /* Return true if NODE should be accounted for overall size estimate.
1695 Skip all nodes optimized for size so we can measure the growth of hot
1696 part of program no matter of the padding. */
1699 inline_account_function_p (struct cgraph_node
*node
)
1701 return (!DECL_EXTERNAL (node
->decl
)
1702 && !opt_for_fn (node
->decl
, optimize_size
)
1703 && node
->frequency
!= NODE_FREQUENCY_UNLIKELY_EXECUTED
);
1706 /* Count number of callers of NODE and store it into DATA (that
1707 points to int. Worker for cgraph_for_node_and_aliases. */
1710 sum_callers (struct cgraph_node
*node
, void *data
)
1712 struct cgraph_edge
*e
;
1713 int *num_calls
= (int *)data
;
1715 for (e
= node
->callers
; e
; e
= e
->next_caller
)
1720 /* We use greedy algorithm for inlining of small functions:
1721 All inline candidates are put into prioritized heap ordered in
1724 The inlining of small functions is bounded by unit growth parameters. */
1727 inline_small_functions (void)
1729 struct cgraph_node
*node
;
1730 struct cgraph_edge
*edge
;
1731 edge_heap_t
edge_heap (sreal::min ());
1732 bitmap updated_nodes
= BITMAP_ALLOC (NULL
);
1733 int min_size
, max_size
;
1734 auto_vec
<cgraph_edge
*> new_indirect_edges
;
1735 int initial_size
= 0;
1736 struct cgraph_node
**order
= XCNEWVEC (cgraph_node
*, symtab
->cgraph_count
);
1737 struct cgraph_edge_hook_list
*edge_removal_hook_holder
;
1738 new_indirect_edges
.create (8);
1740 edge_removal_hook_holder
1741 = symtab
->add_edge_removal_hook (&heap_edge_removal_hook
, &edge_heap
);
1743 /* Compute overall unit size and other global parameters used by badness
1747 ipa_reduced_postorder (order
, true, true, NULL
);
1750 FOR_EACH_DEFINED_FUNCTION (node
)
1751 if (!node
->global
.inlined_to
)
1753 if (!node
->alias
&& node
->analyzed
1754 && (node
->has_gimple_body_p () || node
->thunk
.thunk_p
))
1756 struct inline_summary
*info
= inline_summaries
->get (node
);
1757 struct ipa_dfs_info
*dfs
= (struct ipa_dfs_info
*) node
->aux
;
1759 /* Do not account external functions, they will be optimized out
1760 if not inlined. Also only count the non-cold portion of program. */
1761 if (inline_account_function_p (node
))
1762 initial_size
+= info
->size
;
1763 info
->growth
= estimate_growth (node
);
1766 node
->call_for_symbol_and_aliases (sum_callers
, &num_calls
,
1769 info
->single_caller
= true;
1770 if (dfs
&& dfs
->next_cycle
)
1772 struct cgraph_node
*n2
;
1773 int id
= dfs
->scc_no
+ 1;
1775 n2
= ((struct ipa_dfs_info
*) node
->aux
)->next_cycle
)
1777 struct inline_summary
*info2
= inline_summaries
->get (n2
);
1785 for (edge
= node
->callers
; edge
; edge
= edge
->next_caller
)
1786 if (max_count
< edge
->count
)
1787 max_count
= edge
->count
;
1789 ipa_free_postorder_info ();
1790 initialize_growth_caches ();
1794 "\nDeciding on inlining of small functions. Starting with size %i.\n",
1797 overall_size
= initial_size
;
1798 max_size
= compute_max_insns (overall_size
);
1799 min_size
= overall_size
;
1801 /* Populate the heap with all edges we might inline. */
1803 FOR_EACH_DEFINED_FUNCTION (node
)
1805 bool update
= false;
1806 struct cgraph_edge
*next
= NULL
;
1807 bool has_speculative
= false;
1810 fprintf (dump_file
, "Enqueueing calls in %s/%i.\n",
1811 node
->name (), node
->order
);
1813 for (edge
= node
->callees
; edge
; edge
= next
)
1815 next
= edge
->next_callee
;
1816 if (edge
->inline_failed
1818 && can_inline_edge_p (edge
, true)
1819 && want_inline_small_function_p (edge
, true)
1820 && edge
->inline_failed
)
1822 gcc_assert (!edge
->aux
);
1823 update_edge_key (&edge_heap
, edge
);
1825 if (edge
->speculative
)
1826 has_speculative
= true;
1828 if (has_speculative
)
1829 for (edge
= node
->callees
; edge
; edge
= next
)
1830 if (edge
->speculative
&& !speculation_useful_p (edge
,
1833 edge
->resolve_speculation ();
1838 struct cgraph_node
*where
= node
->global
.inlined_to
1839 ? node
->global
.inlined_to
: node
;
1840 inline_update_overall_summary (where
);
1841 reset_edge_caches (where
);
1842 update_caller_keys (&edge_heap
, where
,
1843 updated_nodes
, NULL
);
1844 update_callee_keys (&edge_heap
, where
,
1846 bitmap_clear (updated_nodes
);
1850 gcc_assert (in_lto_p
1852 || (profile_info
&& flag_branch_probabilities
));
1854 while (!edge_heap
.empty ())
1856 int old_size
= overall_size
;
1857 struct cgraph_node
*where
, *callee
;
1858 sreal badness
= edge_heap
.min_key ();
1859 sreal current_badness
;
1862 edge
= edge_heap
.extract_min ();
1863 gcc_assert (edge
->aux
);
1865 if (!edge
->inline_failed
|| !edge
->callee
->analyzed
)
1869 /* Be sure that caches are maintained consistent. */
1870 sreal cached_badness
= edge_badness (edge
, false);
1872 int old_size_est
= estimate_edge_size (edge
);
1873 int old_time_est
= estimate_edge_time (edge
);
1874 int old_hints_est
= estimate_edge_hints (edge
);
1876 reset_edge_growth_cache (edge
);
1877 gcc_assert (old_size_est
== estimate_edge_size (edge
));
1878 gcc_assert (old_time_est
== estimate_edge_time (edge
));
1881 gcc_assert (old_hints_est == estimate_edge_hints (edge));
1883 fails with profile feedback because some hints depends on
1884 maybe_hot_edge_p predicate and because callee gets inlined to other
1885 calls, the edge may become cold.
1886 This ought to be fixed by computing relative probabilities
1887 for given invocation but that will be better done once whole
1888 code is converted to sreals. Disable for now and revert to "wrong"
1889 value so enable/disable checking paths agree. */
1890 edge_growth_cache
[edge
->uid
].hints
= old_hints_est
+ 1;
1892 /* When updating the edge costs, we only decrease badness in the keys.
1893 Increases of badness are handled lazilly; when we see key with out
1894 of date value on it, we re-insert it now. */
1895 current_badness
= edge_badness (edge
, false);
1896 /* Disable checking for profile because roundoff errors may cause slight
1897 deviations in the order. */
1898 gcc_assert (max_count
|| cached_badness
== current_badness
);
1899 gcc_assert (current_badness
>= badness
);
1901 current_badness
= edge_badness (edge
, false);
1903 if (current_badness
!= badness
)
1905 if (edge_heap
.min () && current_badness
> edge_heap
.min_key ())
1907 edge
->aux
= edge_heap
.insert (current_badness
, edge
);
1911 badness
= current_badness
;
1914 if (!can_inline_edge_p (edge
, true))
1916 resolve_noninline_speculation (&edge_heap
, edge
);
1920 callee
= edge
->callee
->ultimate_alias_target ();
1921 growth
= estimate_edge_growth (edge
);
1925 "\nConsidering %s/%i with %i size\n",
1926 callee
->name (), callee
->order
,
1927 inline_summaries
->get (callee
)->size
);
1929 " to be inlined into %s/%i in %s:%i\n"
1930 " Estimated badness is %f, frequency %.2f.\n",
1931 edge
->caller
->name (), edge
->caller
->order
,
1933 && (LOCATION_LOCUS (gimple_location ((const gimple
*)
1935 > BUILTINS_LOCATION
)
1936 ? gimple_filename ((const gimple
*) edge
->call_stmt
)
1939 ? gimple_lineno ((const gimple
*) edge
->call_stmt
)
1941 badness
.to_double (),
1942 edge
->frequency
/ (double)CGRAPH_FREQ_BASE
);
1944 fprintf (dump_file
," Called %" PRId64
"x\n",
1946 if (dump_flags
& TDF_DETAILS
)
1947 edge_badness (edge
, true);
1950 if (overall_size
+ growth
> max_size
1951 && !DECL_DISREGARD_INLINE_LIMITS (callee
->decl
))
1953 edge
->inline_failed
= CIF_INLINE_UNIT_GROWTH_LIMIT
;
1954 report_inline_failed_reason (edge
);
1955 resolve_noninline_speculation (&edge_heap
, edge
);
1959 if (!want_inline_small_function_p (edge
, true))
1961 resolve_noninline_speculation (&edge_heap
, edge
);
1965 /* Heuristics for inlining small functions work poorly for
1966 recursive calls where we do effects similar to loop unrolling.
1967 When inlining such edge seems profitable, leave decision on
1968 specific inliner. */
1969 if (edge
->recursive_p ())
1971 where
= edge
->caller
;
1972 if (where
->global
.inlined_to
)
1973 where
= where
->global
.inlined_to
;
1974 if (!recursive_inlining (edge
,
1975 opt_for_fn (edge
->caller
->decl
,
1976 flag_indirect_inlining
)
1977 ? &new_indirect_edges
: NULL
))
1979 edge
->inline_failed
= CIF_RECURSIVE_INLINING
;
1980 resolve_noninline_speculation (&edge_heap
, edge
);
1983 reset_edge_caches (where
);
1984 /* Recursive inliner inlines all recursive calls of the function
1985 at once. Consequently we need to update all callee keys. */
1986 if (opt_for_fn (edge
->caller
->decl
, flag_indirect_inlining
))
1987 add_new_edges_to_heap (&edge_heap
, new_indirect_edges
);
1988 update_callee_keys (&edge_heap
, where
, updated_nodes
);
1989 bitmap_clear (updated_nodes
);
1993 struct cgraph_node
*outer_node
= NULL
;
1996 /* Consider the case where self recursive function A is inlined
1997 into B. This is desired optimization in some cases, since it
1998 leads to effect similar of loop peeling and we might completely
1999 optimize out the recursive call. However we must be extra
2002 where
= edge
->caller
;
2003 while (where
->global
.inlined_to
)
2005 if (where
->decl
== callee
->decl
)
2006 outer_node
= where
, depth
++;
2007 where
= where
->callers
->caller
;
2010 && !want_inline_self_recursive_call_p (edge
, outer_node
,
2014 = (DECL_DISREGARD_INLINE_LIMITS (edge
->callee
->decl
)
2015 ? CIF_RECURSIVE_INLINING
: CIF_UNSPECIFIED
);
2016 resolve_noninline_speculation (&edge_heap
, edge
);
2019 else if (depth
&& dump_file
)
2020 fprintf (dump_file
, " Peeling recursion with depth %i\n", depth
);
2022 gcc_checking_assert (!callee
->global
.inlined_to
);
2023 inline_call (edge
, true, &new_indirect_edges
, &overall_size
, true);
2024 add_new_edges_to_heap (&edge_heap
, new_indirect_edges
);
2026 reset_edge_caches (edge
->callee
->function_symbol ());
2028 update_callee_keys (&edge_heap
, where
, updated_nodes
);
2030 where
= edge
->caller
;
2031 if (where
->global
.inlined_to
)
2032 where
= where
->global
.inlined_to
;
2034 /* Our profitability metric can depend on local properties
2035 such as number of inlinable calls and size of the function body.
2036 After inlining these properties might change for the function we
2037 inlined into (since it's body size changed) and for the functions
2038 called by function we inlined (since number of it inlinable callers
2040 update_caller_keys (&edge_heap
, where
, updated_nodes
, NULL
);
2041 /* Offline copy count has possibly changed, recompute if profile is
2045 struct cgraph_node
*n
= cgraph_node::get (edge
->callee
->decl
);
2046 if (n
!= edge
->callee
&& n
->analyzed
)
2047 update_callee_keys (&edge_heap
, n
, updated_nodes
);
2049 bitmap_clear (updated_nodes
);
2054 " Inlined into %s which now has time %i and size %i,"
2055 "net change of %+i.\n",
2056 edge
->caller
->name (),
2057 inline_summaries
->get (edge
->caller
)->time
,
2058 inline_summaries
->get (edge
->caller
)->size
,
2059 overall_size
- old_size
);
2061 if (min_size
> overall_size
)
2063 min_size
= overall_size
;
2064 max_size
= compute_max_insns (min_size
);
2067 fprintf (dump_file
, "New minimal size reached: %i\n", min_size
);
2071 free_growth_caches ();
2074 "Unit growth for small function inlining: %i->%i (%i%%)\n",
2075 initial_size
, overall_size
,
2076 initial_size
? overall_size
* 100 / (initial_size
) - 100: 0);
2077 BITMAP_FREE (updated_nodes
);
2078 symtab
->remove_edge_removal_hook (edge_removal_hook_holder
);
2081 /* Flatten NODE. Performed both during early inlining and
2082 at IPA inlining time. */
2085 flatten_function (struct cgraph_node
*node
, bool early
)
2087 struct cgraph_edge
*e
;
2089 /* We shouldn't be called recursively when we are being processed. */
2090 gcc_assert (node
->aux
== NULL
);
2092 node
->aux
= (void *) node
;
2094 for (e
= node
->callees
; e
; e
= e
->next_callee
)
2096 struct cgraph_node
*orig_callee
;
2097 struct cgraph_node
*callee
= e
->callee
->ultimate_alias_target ();
2099 /* We've hit cycle? It is time to give up. */
2104 "Not inlining %s into %s to avoid cycle.\n",
2105 xstrdup_for_dump (callee
->name ()),
2106 xstrdup_for_dump (e
->caller
->name ()));
2107 e
->inline_failed
= CIF_RECURSIVE_INLINING
;
2111 /* When the edge is already inlined, we just need to recurse into
2112 it in order to fully flatten the leaves. */
2113 if (!e
->inline_failed
)
2115 flatten_function (callee
, early
);
2119 /* Flatten attribute needs to be processed during late inlining. For
2120 extra code quality we however do flattening during early optimization,
2123 ? !can_inline_edge_p (e
, true)
2124 : !can_early_inline_edge_p (e
))
2127 if (e
->recursive_p ())
2130 fprintf (dump_file
, "Not inlining: recursive call.\n");
2134 if (gimple_in_ssa_p (DECL_STRUCT_FUNCTION (node
->decl
))
2135 != gimple_in_ssa_p (DECL_STRUCT_FUNCTION (callee
->decl
)))
2138 fprintf (dump_file
, "Not inlining: SSA form does not match.\n");
2142 /* Inline the edge and flatten the inline clone. Avoid
2143 recursing through the original node if the node was cloned. */
2145 fprintf (dump_file
, " Inlining %s into %s.\n",
2146 xstrdup_for_dump (callee
->name ()),
2147 xstrdup_for_dump (e
->caller
->name ()));
2148 orig_callee
= callee
;
2149 inline_call (e
, true, NULL
, NULL
, false);
2150 if (e
->callee
!= orig_callee
)
2151 orig_callee
->aux
= (void *) node
;
2152 flatten_function (e
->callee
, early
);
2153 if (e
->callee
!= orig_callee
)
2154 orig_callee
->aux
= NULL
;
2158 if (!node
->global
.inlined_to
)
2159 inline_update_overall_summary (node
);
2162 /* Inline NODE to all callers. Worker for cgraph_for_node_and_aliases.
2163 DATA points to number of calls originally found so we avoid infinite
2167 inline_to_all_callers_1 (struct cgraph_node
*node
, void *data
,
2168 hash_set
<cgraph_node
*> *callers
)
2170 int *num_calls
= (int *)data
;
2171 bool callee_removed
= false;
2173 while (node
->callers
&& !node
->global
.inlined_to
)
2175 struct cgraph_node
*caller
= node
->callers
->caller
;
2177 if (!can_inline_edge_p (node
->callers
, true)
2178 || node
->callers
->recursive_p ())
2181 fprintf (dump_file
, "Uninlinable call found; giving up.\n");
2189 "\nInlining %s size %i.\n",
2191 inline_summaries
->get (node
)->size
);
2193 " Called once from %s %i insns.\n",
2194 node
->callers
->caller
->name (),
2195 inline_summaries
->get (node
->callers
->caller
)->size
);
2198 /* Remember which callers we inlined to, delaying updating the
2200 callers
->add (node
->callers
->caller
);
2201 inline_call (node
->callers
, true, NULL
, NULL
, false, &callee_removed
);
2204 " Inlined into %s which now has %i size\n",
2206 inline_summaries
->get (caller
)->size
);
2207 if (!(*num_calls
)--)
2210 fprintf (dump_file
, "New calls found; giving up.\n");
2211 return callee_removed
;
2219 /* Wrapper around inline_to_all_callers_1 doing delayed overall summary
2223 inline_to_all_callers (struct cgraph_node
*node
, void *data
)
2225 hash_set
<cgraph_node
*> callers
;
2226 bool res
= inline_to_all_callers_1 (node
, data
, &callers
);
2227 /* Perform the delayed update of the overall summary of all callers
2228 processed. This avoids quadratic behavior in the cases where
2229 we have a lot of calls to the same function. */
2230 for (hash_set
<cgraph_node
*>::iterator i
= callers
.begin ();
2231 i
!= callers
.end (); ++i
)
2232 inline_update_overall_summary (*i
);
2236 /* Output overall time estimate. */
2238 dump_overall_stats (void)
2240 int64_t sum_weighted
= 0, sum
= 0;
2241 struct cgraph_node
*node
;
2243 FOR_EACH_DEFINED_FUNCTION (node
)
2244 if (!node
->global
.inlined_to
2247 int time
= inline_summaries
->get (node
)->time
;
2249 sum_weighted
+= time
* node
->count
;
2251 fprintf (dump_file
, "Overall time estimate: "
2252 "%" PRId64
" weighted by profile: "
2253 "%" PRId64
"\n", sum
, sum_weighted
);
2256 /* Output some useful stats about inlining. */
2259 dump_inline_stats (void)
2261 int64_t inlined_cnt
= 0, inlined_indir_cnt
= 0;
2262 int64_t inlined_virt_cnt
= 0, inlined_virt_indir_cnt
= 0;
2263 int64_t noninlined_cnt
= 0, noninlined_indir_cnt
= 0;
2264 int64_t noninlined_virt_cnt
= 0, noninlined_virt_indir_cnt
= 0;
2265 int64_t inlined_speculative
= 0, inlined_speculative_ply
= 0;
2266 int64_t indirect_poly_cnt
= 0, indirect_cnt
= 0;
2267 int64_t reason
[CIF_N_REASONS
][3];
2269 struct cgraph_node
*node
;
2271 memset (reason
, 0, sizeof (reason
));
2272 FOR_EACH_DEFINED_FUNCTION (node
)
2274 struct cgraph_edge
*e
;
2275 for (e
= node
->callees
; e
; e
= e
->next_callee
)
2277 if (e
->inline_failed
)
2279 reason
[(int) e
->inline_failed
][0] += e
->count
;
2280 reason
[(int) e
->inline_failed
][1] += e
->frequency
;
2281 reason
[(int) e
->inline_failed
][2] ++;
2282 if (DECL_VIRTUAL_P (e
->callee
->decl
))
2284 if (e
->indirect_inlining_edge
)
2285 noninlined_virt_indir_cnt
+= e
->count
;
2287 noninlined_virt_cnt
+= e
->count
;
2291 if (e
->indirect_inlining_edge
)
2292 noninlined_indir_cnt
+= e
->count
;
2294 noninlined_cnt
+= e
->count
;
2301 if (DECL_VIRTUAL_P (e
->callee
->decl
))
2302 inlined_speculative_ply
+= e
->count
;
2304 inlined_speculative
+= e
->count
;
2306 else if (DECL_VIRTUAL_P (e
->callee
->decl
))
2308 if (e
->indirect_inlining_edge
)
2309 inlined_virt_indir_cnt
+= e
->count
;
2311 inlined_virt_cnt
+= e
->count
;
2315 if (e
->indirect_inlining_edge
)
2316 inlined_indir_cnt
+= e
->count
;
2318 inlined_cnt
+= e
->count
;
2322 for (e
= node
->indirect_calls
; e
; e
= e
->next_callee
)
2323 if (e
->indirect_info
->polymorphic
)
2324 indirect_poly_cnt
+= e
->count
;
2326 indirect_cnt
+= e
->count
;
2331 "Inlined %" PRId64
" + speculative "
2332 "%" PRId64
" + speculative polymorphic "
2333 "%" PRId64
" + previously indirect "
2334 "%" PRId64
" + virtual "
2335 "%" PRId64
" + virtual and previously indirect "
2336 "%" PRId64
"\n" "Not inlined "
2337 "%" PRId64
" + previously indirect "
2338 "%" PRId64
" + virtual "
2339 "%" PRId64
" + virtual and previously indirect "
2340 "%" PRId64
" + stil indirect "
2341 "%" PRId64
" + still indirect polymorphic "
2342 "%" PRId64
"\n", inlined_cnt
,
2343 inlined_speculative
, inlined_speculative_ply
,
2344 inlined_indir_cnt
, inlined_virt_cnt
, inlined_virt_indir_cnt
,
2345 noninlined_cnt
, noninlined_indir_cnt
, noninlined_virt_cnt
,
2346 noninlined_virt_indir_cnt
, indirect_cnt
, indirect_poly_cnt
);
2348 "Removed speculations %" PRId64
"\n",
2351 dump_overall_stats ();
2352 fprintf (dump_file
, "\nWhy inlining failed?\n");
2353 for (i
= 0; i
< CIF_N_REASONS
; i
++)
2355 fprintf (dump_file
, "%-50s: %8i calls, %8i freq, %" PRId64
" count\n",
2356 cgraph_inline_failed_string ((cgraph_inline_failed_t
) i
),
2357 (int) reason
[i
][2], (int) reason
[i
][1], reason
[i
][0]);
2360 /* Decide on the inlining. We do so in the topological order to avoid
2361 expenses on updating data structures. */
2366 struct cgraph_node
*node
;
2368 struct cgraph_node
**order
;
2371 bool remove_functions
= false;
2376 cgraph_freq_base_rec
= (sreal
) 1 / (sreal
) CGRAPH_FREQ_BASE
;
2377 percent_rec
= (sreal
) 1 / (sreal
) 100;
2379 order
= XCNEWVEC (struct cgraph_node
*, symtab
->cgraph_count
);
2381 if (in_lto_p
&& optimize
)
2382 ipa_update_after_lto_read ();
2385 dump_inline_summaries (dump_file
);
2387 nnodes
= ipa_reverse_postorder (order
);
2389 FOR_EACH_FUNCTION (node
)
2393 /* Recompute the default reasons for inlining because they may have
2394 changed during merging. */
2397 for (cgraph_edge
*e
= node
->callees
; e
; e
= e
->next_callee
)
2399 gcc_assert (e
->inline_failed
);
2400 initialize_inline_failed (e
);
2402 for (cgraph_edge
*e
= node
->indirect_calls
; e
; e
= e
->next_callee
)
2403 initialize_inline_failed (e
);
2408 fprintf (dump_file
, "\nFlattening functions:\n");
2410 /* In the first pass handle functions to be flattened. Do this with
2411 a priority so none of our later choices will make this impossible. */
2412 for (i
= nnodes
- 1; i
>= 0; i
--)
2416 /* Handle nodes to be flattened.
2417 Ideally when processing callees we stop inlining at the
2418 entry of cycles, possibly cloning that entry point and
2419 try to flatten itself turning it into a self-recursive
2421 if (lookup_attribute ("flatten",
2422 DECL_ATTRIBUTES (node
->decl
)) != NULL
)
2426 "Flattening %s\n", node
->name ());
2427 flatten_function (node
, false);
2431 dump_overall_stats ();
2433 inline_small_functions ();
2435 gcc_assert (symtab
->state
== IPA_SSA
);
2436 symtab
->state
= IPA_SSA_AFTER_INLINING
;
2437 /* Do first after-inlining removal. We want to remove all "stale" extern
2438 inline functions and virtual functions so we really know what is called
2440 symtab
->remove_unreachable_nodes (dump_file
);
2443 /* Inline functions with a property that after inlining into all callers the
2444 code size will shrink because the out-of-line copy is eliminated.
2445 We do this regardless on the callee size as long as function growth limits
2449 "\nDeciding on functions to be inlined into all callers and "
2450 "removing useless speculations:\n");
2452 /* Inlining one function called once has good chance of preventing
2453 inlining other function into the same callee. Ideally we should
2454 work in priority order, but probably inlining hot functions first
2455 is good cut without the extra pain of maintaining the queue.
2457 ??? this is not really fitting the bill perfectly: inlining function
2458 into callee often leads to better optimization of callee due to
2459 increased context for optimization.
2460 For example if main() function calls a function that outputs help
2461 and then function that does the main optmization, we should inline
2462 the second with priority even if both calls are cold by themselves.
2464 We probably want to implement new predicate replacing our use of
2465 maybe_hot_edge interpreted as maybe_hot_edge || callee is known
2467 for (cold
= 0; cold
<= 1; cold
++)
2469 FOR_EACH_DEFINED_FUNCTION (node
)
2471 struct cgraph_edge
*edge
, *next
;
2474 for (edge
= node
->callees
; edge
; edge
= next
)
2476 next
= edge
->next_callee
;
2477 if (edge
->speculative
&& !speculation_useful_p (edge
, false))
2479 edge
->resolve_speculation ();
2480 spec_rem
+= edge
->count
;
2482 remove_functions
= true;
2487 struct cgraph_node
*where
= node
->global
.inlined_to
2488 ? node
->global
.inlined_to
: node
;
2489 reset_edge_caches (where
);
2490 inline_update_overall_summary (where
);
2492 if (want_inline_function_to_all_callers_p (node
, cold
))
2495 node
->call_for_symbol_and_aliases (sum_callers
, &num_calls
,
2497 while (node
->call_for_symbol_and_aliases
2498 (inline_to_all_callers
, &num_calls
, true))
2500 remove_functions
= true;
2505 /* Free ipa-prop structures if they are no longer needed. */
2507 ipa_free_all_structures_after_iinln ();
2512 "\nInlined %i calls, eliminated %i functions\n\n",
2513 ncalls_inlined
, nfunctions_inlined
);
2514 dump_inline_stats ();
2518 dump_inline_summaries (dump_file
);
2519 /* In WPA we use inline summaries for partitioning process. */
2521 inline_free_summary ();
2522 return remove_functions
? TODO_remove_functions
: 0;
2525 /* Inline always-inline function calls in NODE. */
2528 inline_always_inline_functions (struct cgraph_node
*node
)
2530 struct cgraph_edge
*e
;
2531 bool inlined
= false;
2533 for (e
= node
->callees
; e
; e
= e
->next_callee
)
2535 struct cgraph_node
*callee
= e
->callee
->ultimate_alias_target ();
2536 if (!DECL_DISREGARD_INLINE_LIMITS (callee
->decl
))
2539 if (e
->recursive_p ())
2542 fprintf (dump_file
, " Not inlining recursive call to %s.\n",
2543 e
->callee
->name ());
2544 e
->inline_failed
= CIF_RECURSIVE_INLINING
;
2548 if (!can_early_inline_edge_p (e
))
2550 /* Set inlined to true if the callee is marked "always_inline" but
2551 is not inlinable. This will allow flagging an error later in
2552 expand_call_inline in tree-inline.c. */
2553 if (lookup_attribute ("always_inline",
2554 DECL_ATTRIBUTES (callee
->decl
)) != NULL
)
2560 fprintf (dump_file
, " Inlining %s into %s (always_inline).\n",
2561 xstrdup_for_dump (e
->callee
->name ()),
2562 xstrdup_for_dump (e
->caller
->name ()));
2563 inline_call (e
, true, NULL
, NULL
, false);
2567 inline_update_overall_summary (node
);
2572 /* Decide on the inlining. We do so in the topological order to avoid
2573 expenses on updating data structures. */
2576 early_inline_small_functions (struct cgraph_node
*node
)
2578 struct cgraph_edge
*e
;
2579 bool inlined
= false;
2581 for (e
= node
->callees
; e
; e
= e
->next_callee
)
2583 struct cgraph_node
*callee
= e
->callee
->ultimate_alias_target ();
2584 if (!inline_summaries
->get (callee
)->inlinable
2585 || !e
->inline_failed
)
2588 /* Do not consider functions not declared inline. */
2589 if (!DECL_DECLARED_INLINE_P (callee
->decl
)
2590 && !opt_for_fn (node
->decl
, flag_inline_small_functions
)
2591 && !opt_for_fn (node
->decl
, flag_inline_functions
))
2595 fprintf (dump_file
, "Considering inline candidate %s.\n",
2598 if (!can_early_inline_edge_p (e
))
2601 if (e
->recursive_p ())
2604 fprintf (dump_file
, " Not inlining: recursive call.\n");
2608 if (!want_early_inline_function_p (e
))
2612 fprintf (dump_file
, " Inlining %s into %s.\n",
2613 xstrdup_for_dump (callee
->name ()),
2614 xstrdup_for_dump (e
->caller
->name ()));
2615 inline_call (e
, true, NULL
, NULL
, false);
2620 inline_update_overall_summary (node
);
2626 early_inliner (function
*fun
)
2628 struct cgraph_node
*node
= cgraph_node::get (current_function_decl
);
2629 struct cgraph_edge
*edge
;
2630 unsigned int todo
= 0;
2632 bool inlined
= false;
2637 /* Do nothing if datastructures for ipa-inliner are already computed. This
2638 happens when some pass decides to construct new function and
2639 cgraph_add_new_function calls lowering passes and early optimization on
2640 it. This may confuse ourself when early inliner decide to inline call to
2641 function clone, because function clones don't have parameter list in
2642 ipa-prop matching their signature. */
2643 if (ipa_node_params_sum
)
2648 node
->remove_all_references ();
2650 /* Rebuild this reference because it dosn't depend on
2651 function's body and it's required to pass cgraph_node
2653 if (node
->instrumented_version
2654 && !node
->instrumentation_clone
)
2655 node
->create_reference (node
->instrumented_version
, IPA_REF_CHKP
, NULL
);
2657 /* Even when not optimizing or not inlining inline always-inline
2659 inlined
= inline_always_inline_functions (node
);
2663 || !flag_early_inlining
2664 /* Never inline regular functions into always-inline functions
2665 during incremental inlining. This sucks as functions calling
2666 always inline functions will get less optimized, but at the
2667 same time inlining of functions calling always inline
2668 function into an always inline function might introduce
2669 cycles of edges to be always inlined in the callgraph.
2671 We might want to be smarter and just avoid this type of inlining. */
2672 || (DECL_DISREGARD_INLINE_LIMITS (node
->decl
)
2673 && lookup_attribute ("always_inline",
2674 DECL_ATTRIBUTES (node
->decl
))))
2676 else if (lookup_attribute ("flatten",
2677 DECL_ATTRIBUTES (node
->decl
)) != NULL
)
2679 /* When the function is marked to be flattened, recursively inline
2683 "Flattening %s\n", node
->name ());
2684 flatten_function (node
, true);
2689 /* If some always_inline functions was inlined, apply the changes.
2690 This way we will not account always inline into growth limits and
2691 moreover we will inline calls from always inlines that we skipped
2692 previously because of conditional above. */
2695 timevar_push (TV_INTEGRATION
);
2696 todo
|= optimize_inline_calls (current_function_decl
);
2697 /* optimize_inline_calls call above might have introduced new
2698 statements that don't have inline parameters computed. */
2699 for (edge
= node
->callees
; edge
; edge
= edge
->next_callee
)
2701 if (inline_edge_summary_vec
.length () > (unsigned) edge
->uid
)
2703 struct inline_edge_summary
*es
= inline_edge_summary (edge
);
2705 = estimate_num_insns (edge
->call_stmt
, &eni_size_weights
);
2707 = estimate_num_insns (edge
->call_stmt
, &eni_time_weights
);
2710 inline_update_overall_summary (node
);
2712 timevar_pop (TV_INTEGRATION
);
2714 /* We iterate incremental inlining to get trivial cases of indirect
2716 while (iterations
< PARAM_VALUE (PARAM_EARLY_INLINER_MAX_ITERATIONS
)
2717 && early_inline_small_functions (node
))
2719 timevar_push (TV_INTEGRATION
);
2720 todo
|= optimize_inline_calls (current_function_decl
);
2722 /* Technically we ought to recompute inline parameters so the new
2723 iteration of early inliner works as expected. We however have
2724 values approximately right and thus we only need to update edge
2725 info that might be cleared out for newly discovered edges. */
2726 for (edge
= node
->callees
; edge
; edge
= edge
->next_callee
)
2728 /* We have no summary for new bound store calls yet. */
2729 if (inline_edge_summary_vec
.length () > (unsigned)edge
->uid
)
2731 struct inline_edge_summary
*es
= inline_edge_summary (edge
);
2733 = estimate_num_insns (edge
->call_stmt
, &eni_size_weights
);
2735 = estimate_num_insns (edge
->call_stmt
, &eni_time_weights
);
2737 if (edge
->callee
->decl
2738 && !gimple_check_call_matching_types (
2739 edge
->call_stmt
, edge
->callee
->decl
, false))
2740 edge
->call_stmt_cannot_inline_p
= true;
2742 if (iterations
< PARAM_VALUE (PARAM_EARLY_INLINER_MAX_ITERATIONS
) - 1)
2743 inline_update_overall_summary (node
);
2744 timevar_pop (TV_INTEGRATION
);
2749 fprintf (dump_file
, "Iterations: %i\n", iterations
);
2754 timevar_push (TV_INTEGRATION
);
2755 todo
|= optimize_inline_calls (current_function_decl
);
2756 timevar_pop (TV_INTEGRATION
);
2759 fun
->always_inline_functions_inlined
= true;
2764 /* Do inlining of small functions. Doing so early helps profiling and other
2765 passes to be somewhat more effective and avoids some code duplication in
2766 later real inlining pass for testcases with very many function calls. */
2770 const pass_data pass_data_early_inline
=
2772 GIMPLE_PASS
, /* type */
2773 "einline", /* name */
2774 OPTGROUP_INLINE
, /* optinfo_flags */
2775 TV_EARLY_INLINING
, /* tv_id */
2776 PROP_ssa
, /* properties_required */
2777 0, /* properties_provided */
2778 0, /* properties_destroyed */
2779 0, /* todo_flags_start */
2780 0, /* todo_flags_finish */
2783 class pass_early_inline
: public gimple_opt_pass
2786 pass_early_inline (gcc::context
*ctxt
)
2787 : gimple_opt_pass (pass_data_early_inline
, ctxt
)
2790 /* opt_pass methods: */
2791 virtual unsigned int execute (function
*);
2793 }; // class pass_early_inline
2796 pass_early_inline::execute (function
*fun
)
2798 return early_inliner (fun
);
2804 make_pass_early_inline (gcc::context
*ctxt
)
2806 return new pass_early_inline (ctxt
);
2811 const pass_data pass_data_ipa_inline
=
2813 IPA_PASS
, /* type */
2814 "inline", /* name */
2815 OPTGROUP_INLINE
, /* optinfo_flags */
2816 TV_IPA_INLINING
, /* tv_id */
2817 0, /* properties_required */
2818 0, /* properties_provided */
2819 0, /* properties_destroyed */
2820 0, /* todo_flags_start */
2821 ( TODO_dump_symtab
), /* todo_flags_finish */
2824 class pass_ipa_inline
: public ipa_opt_pass_d
2827 pass_ipa_inline (gcc::context
*ctxt
)
2828 : ipa_opt_pass_d (pass_data_ipa_inline
, ctxt
,
2829 inline_generate_summary
, /* generate_summary */
2830 inline_write_summary
, /* write_summary */
2831 inline_read_summary
, /* read_summary */
2832 NULL
, /* write_optimization_summary */
2833 NULL
, /* read_optimization_summary */
2834 NULL
, /* stmt_fixup */
2835 0, /* function_transform_todo_flags_start */
2836 inline_transform
, /* function_transform */
2837 NULL
) /* variable_transform */
2840 /* opt_pass methods: */
2841 virtual unsigned int execute (function
*) { return ipa_inline (); }
2843 }; // class pass_ipa_inline
2848 make_pass_ipa_inline (gcc::context
*ctxt
)
2850 return new pass_ipa_inline (ctxt
);