1 /* Inlining decision heuristics.
2 Copyright (C) 2003-2015 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"
99 #include "double-int.h"
103 #include "wide-int.h"
106 #include "fold-const.h"
107 #include "trans-mem.h"
109 #include "tree-inline.h"
110 #include "langhooks.h"
112 #include "diagnostic.h"
113 #include "gimple-pretty-print.h"
116 #include "tree-pass.h"
117 #include "coverage.h"
122 #include "hard-reg-set.h"
124 #include "function.h"
125 #include "basic-block.h"
126 #include "tree-ssa-alias.h"
127 #include "internal-fn.h"
128 #include "gimple-expr.h"
131 #include "gimple-ssa.h"
132 #include "hash-map.h"
133 #include "plugin-api.h"
136 #include "alloc-pool.h"
137 #include "symbol-summary.h"
138 #include "ipa-prop.h"
141 #include "ipa-inline.h"
142 #include "ipa-utils.h"
144 #include "auto-profile.h"
146 #include "builtins.h"
147 #include "fibonacci_heap.h"
148 #include "lto-streamer.h"
150 typedef fibonacci_heap
<sreal
, cgraph_edge
> edge_heap_t
;
151 typedef fibonacci_node
<sreal
, cgraph_edge
> edge_heap_node_t
;
153 /* Statistics we collect about inlining algorithm. */
154 static int overall_size
;
155 static gcov_type max_count
;
156 static gcov_type spec_rem
;
158 /* Pre-computed constants 1/CGRAPH_FREQ_BASE and 1/100. */
159 static sreal cgraph_freq_base_rec
, percent_rec
;
161 /* Return false when inlining edge E would lead to violating
162 limits on function unit growth or stack usage growth.
164 The relative function body growth limit is present generally
165 to avoid problems with non-linear behavior of the compiler.
166 To allow inlining huge functions into tiny wrapper, the limit
167 is always based on the bigger of the two functions considered.
169 For stack growth limits we always base the growth in stack usage
170 of the callers. We want to prevent applications from segfaulting
171 on stack overflow when functions with huge stack frames gets
175 caller_growth_limits (struct cgraph_edge
*e
)
177 struct cgraph_node
*to
= e
->caller
;
178 struct cgraph_node
*what
= e
->callee
->ultimate_alias_target ();
181 HOST_WIDE_INT stack_size_limit
= 0, inlined_stack
;
182 inline_summary
*info
, *what_info
, *outer_info
= inline_summaries
->get (to
);
184 /* Look for function e->caller is inlined to. While doing
185 so work out the largest function body on the way. As
186 described above, we want to base our function growth
187 limits based on that. Not on the self size of the
188 outer function, not on the self size of inline code
189 we immediately inline to. This is the most relaxed
190 interpretation of the rule "do not grow large functions
191 too much in order to prevent compiler from exploding". */
194 info
= inline_summaries
->get (to
);
195 if (limit
< info
->self_size
)
196 limit
= info
->self_size
;
197 if (stack_size_limit
< info
->estimated_self_stack_size
)
198 stack_size_limit
= info
->estimated_self_stack_size
;
199 if (to
->global
.inlined_to
)
200 to
= to
->callers
->caller
;
205 what_info
= inline_summaries
->get (what
);
207 if (limit
< what_info
->self_size
)
208 limit
= what_info
->self_size
;
210 limit
+= limit
* PARAM_VALUE (PARAM_LARGE_FUNCTION_GROWTH
) / 100;
212 /* Check the size after inlining against the function limits. But allow
213 the function to shrink if it went over the limits by forced inlining. */
214 newsize
= estimate_size_after_inlining (to
, e
);
215 if (newsize
>= info
->size
216 && newsize
> PARAM_VALUE (PARAM_LARGE_FUNCTION_INSNS
)
219 e
->inline_failed
= CIF_LARGE_FUNCTION_GROWTH_LIMIT
;
223 if (!what_info
->estimated_stack_size
)
226 /* FIXME: Stack size limit often prevents inlining in Fortran programs
227 due to large i/o datastructures used by the Fortran front-end.
228 We ought to ignore this limit when we know that the edge is executed
229 on every invocation of the caller (i.e. its call statement dominates
230 exit block). We do not track this information, yet. */
231 stack_size_limit
+= ((gcov_type
)stack_size_limit
232 * PARAM_VALUE (PARAM_STACK_FRAME_GROWTH
) / 100);
234 inlined_stack
= (outer_info
->stack_frame_offset
235 + outer_info
->estimated_self_stack_size
236 + what_info
->estimated_stack_size
);
237 /* Check new stack consumption with stack consumption at the place
239 if (inlined_stack
> stack_size_limit
240 /* If function already has large stack usage from sibling
241 inline call, we can inline, too.
242 This bit overoptimistically assume that we are good at stack
244 && inlined_stack
> info
->estimated_stack_size
245 && inlined_stack
> PARAM_VALUE (PARAM_LARGE_STACK_FRAME
))
247 e
->inline_failed
= CIF_LARGE_STACK_FRAME_GROWTH_LIMIT
;
253 /* Dump info about why inlining has failed. */
256 report_inline_failed_reason (struct cgraph_edge
*e
)
260 fprintf (dump_file
, " not inlinable: %s/%i -> %s/%i, %s\n",
261 xstrdup_for_dump (e
->caller
->name ()), e
->caller
->order
,
262 xstrdup_for_dump (e
->callee
->name ()), e
->callee
->order
,
263 cgraph_inline_failed_string (e
->inline_failed
));
264 if ((e
->inline_failed
== CIF_TARGET_OPTION_MISMATCH
265 || e
->inline_failed
== CIF_OPTIMIZATION_MISMATCH
)
266 && e
->caller
->lto_file_data
267 && e
->callee
->function_symbol ()->lto_file_data
)
269 fprintf (dump_file
, " LTO objects: %s, %s\n",
270 e
->caller
->lto_file_data
->file_name
,
271 e
->callee
->function_symbol ()->lto_file_data
->file_name
);
273 if (e
->inline_failed
== CIF_TARGET_OPTION_MISMATCH
)
274 cl_target_option_print_diff
275 (dump_file
, 2, target_opts_for_fn (e
->caller
->decl
),
276 target_opts_for_fn (e
->callee
->ultimate_alias_target ()->decl
));
277 if (e
->inline_failed
== CIF_OPTIMIZATION_MISMATCH
)
278 cl_optimization_print_diff
279 (dump_file
, 2, opts_for_fn (e
->caller
->decl
),
280 opts_for_fn (e
->callee
->ultimate_alias_target ()->decl
));
284 /* Decide whether sanitizer-related attributes allow inlining. */
287 sanitize_attrs_match_for_inline_p (const_tree caller
, const_tree callee
)
289 /* Don't care if sanitizer is disabled */
290 if (!(flag_sanitize
& SANITIZE_ADDRESS
))
293 if (!caller
|| !callee
)
296 return !!lookup_attribute ("no_sanitize_address",
297 DECL_ATTRIBUTES (caller
)) ==
298 !!lookup_attribute ("no_sanitize_address",
299 DECL_ATTRIBUTES (callee
));
302 /* Decide if we can inline the edge and possibly update
303 inline_failed reason.
304 We check whether inlining is possible at all and whether
305 caller growth limits allow doing so.
307 if REPORT is true, output reason to the dump file.
309 if DISREGARD_LIMITS is true, ignore size limits.*/
312 can_inline_edge_p (struct cgraph_edge
*e
, bool report
,
313 bool disregard_limits
= false)
315 bool inlinable
= true;
316 enum availability avail
;
317 cgraph_node
*callee
= e
->callee
->ultimate_alias_target (&avail
);
318 cgraph_node
*caller
= e
->caller
->global
.inlined_to
319 ? e
->caller
->global
.inlined_to
: e
->caller
;
320 tree caller_tree
= DECL_FUNCTION_SPECIFIC_OPTIMIZATION (caller
->decl
);
322 = callee
? DECL_FUNCTION_SPECIFIC_OPTIMIZATION (callee
->decl
) : NULL
;
323 struct function
*caller_fun
= caller
->get_fun ();
324 struct function
*callee_fun
= callee
? callee
->get_fun () : NULL
;
326 gcc_assert (e
->inline_failed
);
328 if (!callee
|| !callee
->definition
)
330 e
->inline_failed
= CIF_BODY_NOT_AVAILABLE
;
333 else if (callee
->calls_comdat_local
)
335 e
->inline_failed
= CIF_USES_COMDAT_LOCAL
;
338 else if (!inline_summaries
->get (callee
)->inlinable
339 || (caller_fun
&& fn_contains_cilk_spawn_p (caller_fun
)))
341 e
->inline_failed
= CIF_FUNCTION_NOT_INLINABLE
;
344 else if (avail
<= AVAIL_INTERPOSABLE
)
346 e
->inline_failed
= CIF_OVERWRITABLE
;
349 else if (e
->call_stmt_cannot_inline_p
)
351 if (e
->inline_failed
!= CIF_FUNCTION_NOT_OPTIMIZED
)
352 e
->inline_failed
= CIF_MISMATCHED_ARGUMENTS
;
355 /* Don't inline if the functions have different EH personalities. */
356 else if (DECL_FUNCTION_PERSONALITY (caller
->decl
)
357 && DECL_FUNCTION_PERSONALITY (callee
->decl
)
358 && (DECL_FUNCTION_PERSONALITY (caller
->decl
)
359 != DECL_FUNCTION_PERSONALITY (callee
->decl
)))
361 e
->inline_failed
= CIF_EH_PERSONALITY
;
364 /* TM pure functions should not be inlined into non-TM_pure
366 else if (is_tm_pure (callee
->decl
)
367 && !is_tm_pure (caller
->decl
))
369 e
->inline_failed
= CIF_UNSPECIFIED
;
372 /* Don't inline if the callee can throw non-call exceptions but the
374 FIXME: this is obviously wrong for LTO where STRUCT_FUNCTION is missing.
375 Move the flag into cgraph node or mirror it in the inline summary. */
376 else if (callee_fun
&& callee_fun
->can_throw_non_call_exceptions
377 && !(caller_fun
&& caller_fun
->can_throw_non_call_exceptions
))
379 e
->inline_failed
= CIF_NON_CALL_EXCEPTIONS
;
382 /* Check compatibility of target optimization options. */
383 else if (!targetm
.target_option
.can_inline_p (caller
->decl
,
386 e
->inline_failed
= CIF_TARGET_OPTION_MISMATCH
;
389 /* Don't inline a function with mismatched sanitization attributes. */
390 else if (!sanitize_attrs_match_for_inline_p (caller
->decl
, callee
->decl
))
392 e
->inline_failed
= CIF_ATTRIBUTE_MISMATCH
;
395 /* Check if caller growth allows the inlining. */
396 else if (!DECL_DISREGARD_INLINE_LIMITS (callee
->decl
)
398 && !lookup_attribute ("flatten",
399 DECL_ATTRIBUTES (caller
->decl
))
400 && !caller_growth_limits (e
))
402 /* Don't inline a function with a higher optimization level than the
403 caller. FIXME: this is really just tip of iceberg of handling
404 optimization attribute. */
405 else if (caller_tree
!= callee_tree
)
407 /* There are some options that change IL semantics which means
408 we cannot inline in these cases for correctness reason.
409 Not even for always_inline declared functions. */
410 /* Strictly speaking only when the callee contains signed integer
411 math where overflow is undefined. */
412 if ((opt_for_fn (e
->caller
->decl
, flag_strict_overflow
)
413 != opt_for_fn (e
->caller
->decl
, flag_strict_overflow
))
414 || (opt_for_fn (e
->caller
->decl
, flag_wrapv
)
415 != opt_for_fn (e
->caller
->decl
, flag_wrapv
))
416 || (opt_for_fn (e
->caller
->decl
, flag_trapv
)
417 != opt_for_fn (e
->caller
->decl
, flag_trapv
))
418 /* Strictly speaking only when the callee contains memory
419 accesses that are not using alias-set zero anyway. */
420 || (opt_for_fn (e
->caller
->decl
, flag_strict_aliasing
)
421 != opt_for_fn (e
->caller
->decl
, flag_strict_aliasing
))
422 /* Strictly speaking only when the callee uses FP math. */
423 || (opt_for_fn (e
->caller
->decl
, flag_rounding_math
)
424 != opt_for_fn (e
->caller
->decl
, flag_rounding_math
))
425 || (opt_for_fn (e
->caller
->decl
, flag_trapping_math
)
426 != opt_for_fn (e
->caller
->decl
, flag_trapping_math
))
427 || (opt_for_fn (e
->caller
->decl
, flag_unsafe_math_optimizations
)
428 != opt_for_fn (e
->caller
->decl
, flag_unsafe_math_optimizations
))
429 || (opt_for_fn (e
->caller
->decl
, flag_finite_math_only
)
430 != opt_for_fn (e
->caller
->decl
, flag_finite_math_only
))
431 || (opt_for_fn (e
->caller
->decl
, flag_signaling_nans
)
432 != opt_for_fn (e
->caller
->decl
, flag_signaling_nans
))
433 || (opt_for_fn (e
->caller
->decl
, flag_cx_limited_range
)
434 != opt_for_fn (e
->caller
->decl
, flag_cx_limited_range
))
435 || (opt_for_fn (e
->caller
->decl
, flag_signed_zeros
)
436 != opt_for_fn (e
->caller
->decl
, flag_signed_zeros
))
437 || (opt_for_fn (e
->caller
->decl
, flag_associative_math
)
438 != opt_for_fn (e
->caller
->decl
, flag_associative_math
))
439 || (opt_for_fn (e
->caller
->decl
, flag_reciprocal_math
)
440 != opt_for_fn (e
->caller
->decl
, flag_reciprocal_math
))
441 /* Strictly speaking only when the callee contains function
442 calls that may end up setting errno. */
443 || (opt_for_fn (e
->caller
->decl
, flag_errno_math
)
444 != opt_for_fn (e
->caller
->decl
, flag_errno_math
)))
446 e
->inline_failed
= CIF_OPTIMIZATION_MISMATCH
;
449 /* gcc.dg/pr43564.c. Apply user-forced inline even at -O0. */
450 else if (DECL_DISREGARD_INLINE_LIMITS (callee
->decl
)
451 && lookup_attribute ("always_inline",
452 DECL_ATTRIBUTES (callee
->decl
)))
454 /* When user added an attribute to the callee honor it. */
455 else if (lookup_attribute ("optimize", DECL_ATTRIBUTES (callee
->decl
))
456 && opts_for_fn (caller
->decl
) != opts_for_fn (callee
->decl
))
458 e
->inline_failed
= CIF_OPTIMIZATION_MISMATCH
;
461 /* If mismatch is caused by merging two LTO units with different
462 optimizationflags we want to be bit nicer. However never inline
463 if one of functions is not optimized at all. */
464 else if (!opt_for_fn (callee
->decl
, optimize
)
465 || !opt_for_fn (caller
->decl
, optimize
))
467 e
->inline_failed
= CIF_OPTIMIZATION_MISMATCH
;
470 /* If callee is optimized for size and caller is not, allow inlining if
471 code shrinks or we are in MAX_INLINE_INSNS_SINGLE limit and callee
472 is inline (and thus likely an unified comdat). This will allow caller
474 else if (opt_for_fn (callee
->decl
, optimize_size
)
475 > opt_for_fn (caller
->decl
, optimize_size
))
477 int growth
= estimate_edge_growth (e
);
479 && (!DECL_DECLARED_INLINE_P (callee
->decl
)
480 && growth
>= MAX (MAX_INLINE_INSNS_SINGLE
,
481 MAX_INLINE_INSNS_AUTO
)))
483 e
->inline_failed
= CIF_OPTIMIZATION_MISMATCH
;
487 /* If callee is more aggressively optimized for performance than caller,
488 we generally want to inline only cheap (runtime wise) functions. */
489 else if (opt_for_fn (callee
->decl
, optimize_size
)
490 < opt_for_fn (caller
->decl
, optimize_size
)
491 || (opt_for_fn (callee
->decl
, optimize
)
492 >= opt_for_fn (caller
->decl
, optimize
)))
494 if (estimate_edge_time (e
)
495 >= 20 + inline_edge_summary (e
)->call_stmt_time
)
497 e
->inline_failed
= CIF_OPTIMIZATION_MISMATCH
;
504 if (!inlinable
&& report
)
505 report_inline_failed_reason (e
);
510 /* Return true if the edge E is inlinable during early inlining. */
513 can_early_inline_edge_p (struct cgraph_edge
*e
)
515 struct cgraph_node
*callee
= e
->callee
->ultimate_alias_target ();
516 /* Early inliner might get called at WPA stage when IPA pass adds new
517 function. In this case we can not really do any of early inlining
518 because function bodies are missing. */
519 if (!gimple_has_body_p (callee
->decl
))
521 e
->inline_failed
= CIF_BODY_NOT_AVAILABLE
;
524 /* In early inliner some of callees may not be in SSA form yet
525 (i.e. the callgraph is cyclic and we did not process
526 the callee by early inliner, yet). We don't have CIF code for this
527 case; later we will re-do the decision in the real inliner. */
528 if (!gimple_in_ssa_p (DECL_STRUCT_FUNCTION (e
->caller
->decl
))
529 || !gimple_in_ssa_p (DECL_STRUCT_FUNCTION (callee
->decl
)))
532 fprintf (dump_file
, " edge not inlinable: not in SSA form\n");
535 if (!can_inline_edge_p (e
, true))
541 /* Return number of calls in N. Ignore cheap builtins. */
544 num_calls (struct cgraph_node
*n
)
546 struct cgraph_edge
*e
;
549 for (e
= n
->callees
; e
; e
= e
->next_callee
)
550 if (!is_inexpensive_builtin (e
->callee
->decl
))
556 /* Return true if we are interested in inlining small function. */
559 want_early_inline_function_p (struct cgraph_edge
*e
)
561 bool want_inline
= true;
562 struct cgraph_node
*callee
= e
->callee
->ultimate_alias_target ();
564 if (DECL_DISREGARD_INLINE_LIMITS (callee
->decl
))
566 /* For AutoFDO, we need to make sure that before profile summary, all
567 hot paths' IR look exactly the same as profiled binary. As a result,
568 in einliner, we will disregard size limit and inline those callsites
570 * inlined in the profiled binary, and
571 * the cloned callee has enough samples to be considered "hot". */
572 else if (flag_auto_profile
&& afdo_callsite_hot_enough_for_early_inline (e
))
574 else if (!DECL_DECLARED_INLINE_P (callee
->decl
)
575 && !opt_for_fn (e
->caller
->decl
, flag_inline_small_functions
))
577 e
->inline_failed
= CIF_FUNCTION_NOT_INLINE_CANDIDATE
;
578 report_inline_failed_reason (e
);
583 int growth
= estimate_edge_growth (e
);
588 else if (!e
->maybe_hot_p ()
592 fprintf (dump_file
, " will not early inline: %s/%i->%s/%i, "
593 "call is cold and code would grow by %i\n",
594 xstrdup_for_dump (e
->caller
->name ()),
596 xstrdup_for_dump (callee
->name ()), callee
->order
,
600 else if (growth
> PARAM_VALUE (PARAM_EARLY_INLINING_INSNS
))
603 fprintf (dump_file
, " will not early inline: %s/%i->%s/%i, "
604 "growth %i exceeds --param early-inlining-insns\n",
605 xstrdup_for_dump (e
->caller
->name ()),
607 xstrdup_for_dump (callee
->name ()), callee
->order
,
611 else if ((n
= num_calls (callee
)) != 0
612 && growth
* (n
+ 1) > PARAM_VALUE (PARAM_EARLY_INLINING_INSNS
))
615 fprintf (dump_file
, " will not early inline: %s/%i->%s/%i, "
616 "growth %i exceeds --param early-inlining-insns "
617 "divided by number of calls\n",
618 xstrdup_for_dump (e
->caller
->name ()),
620 xstrdup_for_dump (callee
->name ()), callee
->order
,
628 /* Compute time of the edge->caller + edge->callee execution when inlining
632 compute_uninlined_call_time (struct inline_summary
*callee_info
,
633 struct cgraph_edge
*edge
)
635 sreal uninlined_call_time
= (sreal
)callee_info
->time
;
636 cgraph_node
*caller
= (edge
->caller
->global
.inlined_to
637 ? edge
->caller
->global
.inlined_to
640 if (edge
->count
&& caller
->count
)
641 uninlined_call_time
*= (sreal
)edge
->count
/ caller
->count
;
643 uninlined_call_time
*= cgraph_freq_base_rec
* edge
->frequency
;
645 uninlined_call_time
= uninlined_call_time
>> 11;
647 int caller_time
= inline_summaries
->get (caller
)->time
;
648 return uninlined_call_time
+ caller_time
;
651 /* Same as compute_uinlined_call_time but compute time when inlining
655 compute_inlined_call_time (struct cgraph_edge
*edge
,
658 cgraph_node
*caller
= (edge
->caller
->global
.inlined_to
659 ? edge
->caller
->global
.inlined_to
661 int caller_time
= inline_summaries
->get (caller
)->time
;
662 sreal time
= edge_time
;
664 if (edge
->count
&& caller
->count
)
665 time
*= (sreal
)edge
->count
/ caller
->count
;
667 time
*= cgraph_freq_base_rec
* edge
->frequency
;
671 /* This calculation should match one in ipa-inline-analysis.
672 FIXME: Once ipa-inline-analysis is converted to sreal this can be
674 time
-= (sreal
) ((gcov_type
) edge
->frequency
675 * inline_edge_summary (edge
)->call_stmt_time
676 * (INLINE_TIME_SCALE
/ CGRAPH_FREQ_BASE
)) / INLINE_TIME_SCALE
;
679 time
= ((sreal
) 1) >> 8;
680 gcc_checking_assert (time
>= 0);
684 /* Return true if the speedup for inlining E is bigger than
685 PARAM_MAX_INLINE_MIN_SPEEDUP. */
688 big_speedup_p (struct cgraph_edge
*e
)
690 sreal time
= compute_uninlined_call_time (inline_summaries
->get (e
->callee
),
692 sreal inlined_time
= compute_inlined_call_time (e
, estimate_edge_time (e
));
694 if (time
- inlined_time
695 > (sreal
) time
* PARAM_VALUE (PARAM_INLINE_MIN_SPEEDUP
)
701 /* Return true if we are interested in inlining small function.
702 When REPORT is true, report reason to dump file. */
705 want_inline_small_function_p (struct cgraph_edge
*e
, bool report
)
707 bool want_inline
= true;
708 struct cgraph_node
*callee
= e
->callee
->ultimate_alias_target ();
710 if (DECL_DISREGARD_INLINE_LIMITS (callee
->decl
))
712 else if (!DECL_DECLARED_INLINE_P (callee
->decl
)
713 && !opt_for_fn (e
->caller
->decl
, flag_inline_small_functions
))
715 e
->inline_failed
= CIF_FUNCTION_NOT_INLINE_CANDIDATE
;
718 /* Do fast and conservative check if the function can be good
719 inline candidate. At the moment we allow inline hints to
720 promote non-inline functions to inline and we increase
721 MAX_INLINE_INSNS_SINGLE 16-fold for inline functions. */
722 else if ((!DECL_DECLARED_INLINE_P (callee
->decl
)
723 && (!e
->count
|| !e
->maybe_hot_p ()))
724 && inline_summaries
->get (callee
)->min_size
725 - inline_edge_summary (e
)->call_stmt_size
726 > MAX (MAX_INLINE_INSNS_SINGLE
, MAX_INLINE_INSNS_AUTO
))
728 e
->inline_failed
= CIF_MAX_INLINE_INSNS_AUTO_LIMIT
;
731 else if ((DECL_DECLARED_INLINE_P (callee
->decl
) || e
->count
)
732 && inline_summaries
->get (callee
)->min_size
733 - inline_edge_summary (e
)->call_stmt_size
734 > 16 * MAX_INLINE_INSNS_SINGLE
)
736 e
->inline_failed
= (DECL_DECLARED_INLINE_P (callee
->decl
)
737 ? CIF_MAX_INLINE_INSNS_SINGLE_LIMIT
738 : CIF_MAX_INLINE_INSNS_AUTO_LIMIT
);
743 int growth
= estimate_edge_growth (e
);
744 inline_hints hints
= estimate_edge_hints (e
);
745 bool big_speedup
= big_speedup_p (e
);
749 /* Apply MAX_INLINE_INSNS_SINGLE limit. Do not do so when
750 hints suggests that inlining given function is very profitable. */
751 else if (DECL_DECLARED_INLINE_P (callee
->decl
)
752 && growth
>= MAX_INLINE_INSNS_SINGLE
754 && !(hints
& (INLINE_HINT_indirect_call
755 | INLINE_HINT_known_hot
756 | INLINE_HINT_loop_iterations
757 | INLINE_HINT_array_index
758 | INLINE_HINT_loop_stride
)))
759 || growth
>= MAX_INLINE_INSNS_SINGLE
* 16))
761 e
->inline_failed
= CIF_MAX_INLINE_INSNS_SINGLE_LIMIT
;
764 else if (!DECL_DECLARED_INLINE_P (callee
->decl
)
765 && !opt_for_fn (e
->caller
->decl
, flag_inline_functions
))
767 /* growth_likely_positive is expensive, always test it last. */
768 if (growth
>= MAX_INLINE_INSNS_SINGLE
769 || growth_likely_positive (callee
, growth
))
771 e
->inline_failed
= CIF_NOT_DECLARED_INLINED
;
775 /* Apply MAX_INLINE_INSNS_AUTO limit for functions not declared inline
776 Upgrade it to MAX_INLINE_INSNS_SINGLE when hints suggests that
777 inlining given function is very profitable. */
778 else if (!DECL_DECLARED_INLINE_P (callee
->decl
)
780 && !(hints
& INLINE_HINT_known_hot
)
781 && growth
>= ((hints
& (INLINE_HINT_indirect_call
782 | INLINE_HINT_loop_iterations
783 | INLINE_HINT_array_index
784 | INLINE_HINT_loop_stride
))
785 ? MAX (MAX_INLINE_INSNS_AUTO
,
786 MAX_INLINE_INSNS_SINGLE
)
787 : MAX_INLINE_INSNS_AUTO
))
789 /* growth_likely_positive is expensive, always test it last. */
790 if (growth
>= MAX_INLINE_INSNS_SINGLE
791 || growth_likely_positive (callee
, growth
))
793 e
->inline_failed
= CIF_MAX_INLINE_INSNS_AUTO_LIMIT
;
797 /* If call is cold, do not inline when function body would grow. */
798 else if (!e
->maybe_hot_p ()
799 && (growth
>= MAX_INLINE_INSNS_SINGLE
800 || growth_likely_positive (callee
, growth
)))
802 e
->inline_failed
= CIF_UNLIKELY_CALL
;
806 if (!want_inline
&& report
)
807 report_inline_failed_reason (e
);
811 /* EDGE is self recursive edge.
812 We hand two cases - when function A is inlining into itself
813 or when function A is being inlined into another inliner copy of function
816 In first case OUTER_NODE points to the toplevel copy of A, while
817 in the second case OUTER_NODE points to the outermost copy of A in B.
819 In both cases we want to be extra selective since
820 inlining the call will just introduce new recursive calls to appear. */
823 want_inline_self_recursive_call_p (struct cgraph_edge
*edge
,
824 struct cgraph_node
*outer_node
,
828 char const *reason
= NULL
;
829 bool want_inline
= true;
830 int caller_freq
= CGRAPH_FREQ_BASE
;
831 int max_depth
= PARAM_VALUE (PARAM_MAX_INLINE_RECURSIVE_DEPTH_AUTO
);
833 if (DECL_DECLARED_INLINE_P (edge
->caller
->decl
))
834 max_depth
= PARAM_VALUE (PARAM_MAX_INLINE_RECURSIVE_DEPTH
);
836 if (!edge
->maybe_hot_p ())
838 reason
= "recursive call is cold";
841 else if (max_count
&& !outer_node
->count
)
843 reason
= "not executed in profile";
846 else if (depth
> max_depth
)
848 reason
= "--param max-inline-recursive-depth exceeded.";
852 if (outer_node
->global
.inlined_to
)
853 caller_freq
= outer_node
->callers
->frequency
;
857 reason
= "function is inlined and unlikely";
863 /* Inlining of self recursive function into copy of itself within other function
864 is transformation similar to loop peeling.
866 Peeling is profitable if we can inline enough copies to make probability
867 of actual call to the self recursive function very small. Be sure that
868 the probability of recursion is small.
870 We ensure that the frequency of recursing is at most 1 - (1/max_depth).
871 This way the expected number of recision is at most max_depth. */
874 int max_prob
= CGRAPH_FREQ_BASE
- ((CGRAPH_FREQ_BASE
+ max_depth
- 1)
877 for (i
= 1; i
< depth
; i
++)
878 max_prob
= max_prob
* max_prob
/ CGRAPH_FREQ_BASE
;
880 && (edge
->count
* CGRAPH_FREQ_BASE
/ outer_node
->count
883 reason
= "profile of recursive call is too large";
887 && (edge
->frequency
* CGRAPH_FREQ_BASE
/ caller_freq
890 reason
= "frequency of recursive call is too large";
894 /* Recursive inlining, i.e. equivalent of unrolling, is profitable if recursion
895 depth is large. We reduce function call overhead and increase chances that
896 things fit in hardware return predictor.
898 Recursive inlining might however increase cost of stack frame setup
899 actually slowing down functions whose recursion tree is wide rather than
902 Deciding reliably on when to do recursive inlining without profile feedback
903 is tricky. For now we disable recursive inlining when probability of self
906 Recursive inlining of self recursive call within loop also results in large loop
907 depths that generally optimize badly. We may want to throttle down inlining
908 in those cases. In particular this seems to happen in one of libstdc++ rb tree
913 && (edge
->count
* 100 / outer_node
->count
914 <= PARAM_VALUE (PARAM_MIN_INLINE_RECURSIVE_PROBABILITY
)))
916 reason
= "profile of recursive call is too small";
920 && (edge
->frequency
* 100 / caller_freq
921 <= PARAM_VALUE (PARAM_MIN_INLINE_RECURSIVE_PROBABILITY
)))
923 reason
= "frequency of recursive call is too small";
927 if (!want_inline
&& dump_file
)
928 fprintf (dump_file
, " not inlining recursively: %s\n", reason
);
932 /* Return true when NODE has uninlinable caller;
933 set HAS_HOT_CALL if it has hot call.
934 Worker for cgraph_for_node_and_aliases. */
937 check_callers (struct cgraph_node
*node
, void *has_hot_call
)
939 struct cgraph_edge
*e
;
940 for (e
= node
->callers
; e
; e
= e
->next_caller
)
942 if (!opt_for_fn (e
->caller
->decl
, flag_inline_functions_called_once
))
944 if (!can_inline_edge_p (e
, true))
946 if (!(*(bool *)has_hot_call
) && e
->maybe_hot_p ())
947 *(bool *)has_hot_call
= true;
952 /* If NODE has a caller, return true. */
955 has_caller_p (struct cgraph_node
*node
, void *data ATTRIBUTE_UNUSED
)
962 /* Decide if inlining NODE would reduce unit size by eliminating
963 the offline copy of function.
964 When COLD is true the cold calls are considered, too. */
967 want_inline_function_to_all_callers_p (struct cgraph_node
*node
, bool cold
)
969 bool has_hot_call
= false;
971 /* Aliases gets inlined along with the function they alias. */
974 /* Already inlined? */
975 if (node
->global
.inlined_to
)
977 /* Does it have callers? */
978 if (!node
->call_for_symbol_thunks_and_aliases (has_caller_p
, NULL
, true))
980 /* Inlining into all callers would increase size? */
981 if (estimate_growth (node
) > 0)
983 /* All inlines must be possible. */
984 if (node
->call_for_symbol_thunks_and_aliases (check_callers
, &has_hot_call
,
987 if (!cold
&& !has_hot_call
)
992 /* A cost model driving the inlining heuristics in a way so the edges with
993 smallest badness are inlined first. After each inlining is performed
994 the costs of all caller edges of nodes affected are recomputed so the
995 metrics may accurately depend on values such as number of inlinable callers
996 of the function or function body size. */
999 edge_badness (struct cgraph_edge
*edge
, bool dump
)
1002 int growth
, edge_time
;
1003 struct cgraph_node
*callee
= edge
->callee
->ultimate_alias_target ();
1004 struct inline_summary
*callee_info
= inline_summaries
->get (callee
);
1006 cgraph_node
*caller
= (edge
->caller
->global
.inlined_to
1007 ? edge
->caller
->global
.inlined_to
1010 growth
= estimate_edge_growth (edge
);
1011 edge_time
= estimate_edge_time (edge
);
1012 hints
= estimate_edge_hints (edge
);
1013 gcc_checking_assert (edge_time
>= 0);
1014 gcc_checking_assert (edge_time
<= callee_info
->time
);
1015 gcc_checking_assert (growth
<= callee_info
->size
);
1019 fprintf (dump_file
, " Badness calculation for %s/%i -> %s/%i\n",
1020 xstrdup_for_dump (edge
->caller
->name ()),
1021 edge
->caller
->order
,
1022 xstrdup_for_dump (callee
->name ()),
1023 edge
->callee
->order
);
1024 fprintf (dump_file
, " size growth %i, time %i ",
1027 dump_inline_hints (dump_file
, hints
);
1028 if (big_speedup_p (edge
))
1029 fprintf (dump_file
, " big_speedup");
1030 fprintf (dump_file
, "\n");
1033 /* Always prefer inlining saving code size. */
1036 badness
= (sreal
) (-SREAL_MIN_SIG
+ growth
) << (SREAL_MAX_EXP
/ 256);
1038 fprintf (dump_file
, " %f: Growth %d <= 0\n", badness
.to_double (),
1041 /* Inlining into EXTERNAL functions is not going to change anything unless
1042 they are themselves inlined. */
1043 else if (DECL_EXTERNAL (caller
->decl
))
1046 fprintf (dump_file
, " max: function is external\n");
1047 return sreal::max ();
1049 /* When profile is available. Compute badness as:
1051 time_saved * caller_count
1052 goodness = ---------------------------------
1053 growth_of_caller * overall_growth
1055 badness = - goodness
1057 Again use negative value to make calls with profile appear hotter
1060 else if (opt_for_fn (caller
->decl
, flag_guess_branch_prob
) || caller
->count
)
1062 sreal numerator
, denominator
;
1064 numerator
= (compute_uninlined_call_time (callee_info
, edge
)
1065 - compute_inlined_call_time (edge
, edge_time
));
1067 numerator
= ((sreal
) 1 >> 8);
1069 numerator
*= caller
->count
;
1070 else if (opt_for_fn (caller
->decl
, flag_branch_probabilities
))
1071 numerator
= numerator
>> 11;
1072 denominator
= growth
;
1073 if (callee_info
->growth
> 0)
1074 denominator
*= callee_info
->growth
;
1076 badness
= - numerator
/ denominator
;
1081 " %f: guessed profile. frequency %f, count %"PRId64
1082 " caller count %"PRId64
1083 " time w/o inlining %f, time w inlining %f"
1084 " overall growth %i (current) %i (original)\n",
1085 badness
.to_double (), (double)edge
->frequency
/ CGRAPH_FREQ_BASE
,
1086 edge
->count
, caller
->count
,
1087 compute_uninlined_call_time (callee_info
, edge
).to_double (),
1088 compute_inlined_call_time (edge
, edge_time
).to_double (),
1089 estimate_growth (callee
),
1090 callee_info
->growth
);
1093 /* When function local profile is not available or it does not give
1094 useful information (ie frequency is zero), base the cost on
1095 loop nest and overall size growth, so we optimize for overall number
1096 of functions fully inlined in program. */
1099 int nest
= MIN (inline_edge_summary (edge
)->loop_depth
, 8);
1102 /* Decrease badness if call is nested. */
1104 badness
= badness
>> nest
;
1106 badness
= badness
<< nest
;
1108 fprintf (dump_file
, " %f: no profile. nest %i\n", badness
.to_double (),
1111 gcc_checking_assert (badness
!= 0);
1113 if (edge
->recursive_p ())
1114 badness
= badness
.shift (badness
> 0 ? 4 : -4);
1115 if ((hints
& (INLINE_HINT_indirect_call
1116 | INLINE_HINT_loop_iterations
1117 | INLINE_HINT_array_index
1118 | INLINE_HINT_loop_stride
))
1119 || callee_info
->growth
<= 0)
1120 badness
= badness
.shift (badness
> 0 ? -2 : 2);
1121 if (hints
& (INLINE_HINT_same_scc
))
1122 badness
= badness
.shift (badness
> 0 ? 3 : -3);
1123 else if (hints
& (INLINE_HINT_in_scc
))
1124 badness
= badness
.shift (badness
> 0 ? 2 : -2);
1125 else if (hints
& (INLINE_HINT_cross_module
))
1126 badness
= badness
.shift (badness
> 0 ? 1 : -1);
1127 if (DECL_DISREGARD_INLINE_LIMITS (callee
->decl
))
1128 badness
= badness
.shift (badness
> 0 ? -4 : 4);
1129 else if ((hints
& INLINE_HINT_declared_inline
))
1130 badness
= badness
.shift (badness
> 0 ? -3 : 3);
1132 fprintf (dump_file
, " Adjusted by hints %f\n", badness
.to_double ());
1136 /* Recompute badness of EDGE and update its key in HEAP if needed. */
1138 update_edge_key (edge_heap_t
*heap
, struct cgraph_edge
*edge
)
1140 sreal badness
= edge_badness (edge
, false);
1143 edge_heap_node_t
*n
= (edge_heap_node_t
*) edge
->aux
;
1144 gcc_checking_assert (n
->get_data () == edge
);
1146 /* fibonacci_heap::replace_key does busy updating of the
1147 heap that is unnecesarily expensive.
1148 We do lazy increases: after extracting minimum if the key
1149 turns out to be out of date, it is re-inserted into heap
1150 with correct value. */
1151 if (badness
< n
->get_key ())
1153 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1156 " decreasing badness %s/%i -> %s/%i, %f"
1158 xstrdup_for_dump (edge
->caller
->name ()),
1159 edge
->caller
->order
,
1160 xstrdup_for_dump (edge
->callee
->name ()),
1161 edge
->callee
->order
,
1162 n
->get_key ().to_double (),
1163 badness
.to_double ());
1165 heap
->decrease_key (n
, badness
);
1170 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1173 " enqueuing call %s/%i -> %s/%i, badness %f\n",
1174 xstrdup_for_dump (edge
->caller
->name ()),
1175 edge
->caller
->order
,
1176 xstrdup_for_dump (edge
->callee
->name ()),
1177 edge
->callee
->order
,
1178 badness
.to_double ());
1180 edge
->aux
= heap
->insert (badness
, edge
);
1185 /* NODE was inlined.
1186 All caller edges needs to be resetted because
1187 size estimates change. Similarly callees needs reset
1188 because better context may be known. */
1191 reset_edge_caches (struct cgraph_node
*node
)
1193 struct cgraph_edge
*edge
;
1194 struct cgraph_edge
*e
= node
->callees
;
1195 struct cgraph_node
*where
= node
;
1196 struct ipa_ref
*ref
;
1198 if (where
->global
.inlined_to
)
1199 where
= where
->global
.inlined_to
;
1201 for (edge
= where
->callers
; edge
; edge
= edge
->next_caller
)
1202 if (edge
->inline_failed
)
1203 reset_edge_growth_cache (edge
);
1205 FOR_EACH_ALIAS (where
, ref
)
1206 reset_edge_caches (dyn_cast
<cgraph_node
*> (ref
->referring
));
1212 if (!e
->inline_failed
&& e
->callee
->callees
)
1213 e
= e
->callee
->callees
;
1216 if (e
->inline_failed
)
1217 reset_edge_growth_cache (e
);
1224 if (e
->caller
== node
)
1226 e
= e
->caller
->callers
;
1228 while (!e
->next_callee
);
1234 /* Recompute HEAP nodes for each of caller of NODE.
1235 UPDATED_NODES track nodes we already visited, to avoid redundant work.
1236 When CHECK_INLINABLITY_FOR is set, re-check for specified edge that
1237 it is inlinable. Otherwise check all edges. */
1240 update_caller_keys (edge_heap_t
*heap
, struct cgraph_node
*node
,
1241 bitmap updated_nodes
,
1242 struct cgraph_edge
*check_inlinablity_for
)
1244 struct cgraph_edge
*edge
;
1245 struct ipa_ref
*ref
;
1247 if ((!node
->alias
&& !inline_summaries
->get (node
)->inlinable
)
1248 || node
->global
.inlined_to
)
1250 if (!bitmap_set_bit (updated_nodes
, node
->uid
))
1253 FOR_EACH_ALIAS (node
, ref
)
1255 struct cgraph_node
*alias
= dyn_cast
<cgraph_node
*> (ref
->referring
);
1256 update_caller_keys (heap
, alias
, updated_nodes
, check_inlinablity_for
);
1259 for (edge
= node
->callers
; edge
; edge
= edge
->next_caller
)
1260 if (edge
->inline_failed
)
1262 if (!check_inlinablity_for
1263 || check_inlinablity_for
== edge
)
1265 if (can_inline_edge_p (edge
, false)
1266 && want_inline_small_function_p (edge
, false))
1267 update_edge_key (heap
, edge
);
1270 report_inline_failed_reason (edge
);
1271 heap
->delete_node ((edge_heap_node_t
*) edge
->aux
);
1276 update_edge_key (heap
, edge
);
1280 /* Recompute HEAP nodes for each uninlined call in NODE.
1281 This is used when we know that edge badnesses are going only to increase
1282 (we introduced new call site) and thus all we need is to insert newly
1283 created edges into heap. */
1286 update_callee_keys (edge_heap_t
*heap
, struct cgraph_node
*node
,
1287 bitmap updated_nodes
)
1289 struct cgraph_edge
*e
= node
->callees
;
1294 if (!e
->inline_failed
&& e
->callee
->callees
)
1295 e
= e
->callee
->callees
;
1298 enum availability avail
;
1299 struct cgraph_node
*callee
;
1300 /* We do not reset callee growth cache here. Since we added a new call,
1301 growth chould have just increased and consequentely badness metric
1302 don't need updating. */
1303 if (e
->inline_failed
1304 && (callee
= e
->callee
->ultimate_alias_target (&avail
))
1305 && inline_summaries
->get (callee
)->inlinable
1306 && avail
>= AVAIL_AVAILABLE
1307 && !bitmap_bit_p (updated_nodes
, callee
->uid
))
1309 if (can_inline_edge_p (e
, false)
1310 && want_inline_small_function_p (e
, false))
1311 update_edge_key (heap
, e
);
1314 report_inline_failed_reason (e
);
1315 heap
->delete_node ((edge_heap_node_t
*) e
->aux
);
1325 if (e
->caller
== node
)
1327 e
= e
->caller
->callers
;
1329 while (!e
->next_callee
);
1335 /* Enqueue all recursive calls from NODE into priority queue depending on
1336 how likely we want to recursively inline the call. */
1339 lookup_recursive_calls (struct cgraph_node
*node
, struct cgraph_node
*where
,
1342 struct cgraph_edge
*e
;
1343 enum availability avail
;
1345 for (e
= where
->callees
; e
; e
= e
->next_callee
)
1346 if (e
->callee
== node
1347 || (e
->callee
->ultimate_alias_target (&avail
) == node
1348 && avail
> AVAIL_INTERPOSABLE
))
1350 /* When profile feedback is available, prioritize by expected number
1352 heap
->insert (!max_count
? -e
->frequency
1353 : -(e
->count
/ ((max_count
+ (1<<24) - 1) / (1<<24))),
1356 for (e
= where
->callees
; e
; e
= e
->next_callee
)
1357 if (!e
->inline_failed
)
1358 lookup_recursive_calls (node
, e
->callee
, heap
);
1361 /* Decide on recursive inlining: in the case function has recursive calls,
1362 inline until body size reaches given argument. If any new indirect edges
1363 are discovered in the process, add them to *NEW_EDGES, unless NEW_EDGES
1367 recursive_inlining (struct cgraph_edge
*edge
,
1368 vec
<cgraph_edge
*> *new_edges
)
1370 int limit
= PARAM_VALUE (PARAM_MAX_INLINE_INSNS_RECURSIVE_AUTO
);
1371 edge_heap_t
heap (sreal::min ());
1372 struct cgraph_node
*node
;
1373 struct cgraph_edge
*e
;
1374 struct cgraph_node
*master_clone
= NULL
, *next
;
1378 node
= edge
->caller
;
1379 if (node
->global
.inlined_to
)
1380 node
= node
->global
.inlined_to
;
1382 if (DECL_DECLARED_INLINE_P (node
->decl
))
1383 limit
= PARAM_VALUE (PARAM_MAX_INLINE_INSNS_RECURSIVE
);
1385 /* Make sure that function is small enough to be considered for inlining. */
1386 if (estimate_size_after_inlining (node
, edge
) >= limit
)
1388 lookup_recursive_calls (node
, node
, &heap
);
1394 " Performing recursive inlining on %s\n",
1397 /* Do the inlining and update list of recursive call during process. */
1398 while (!heap
.empty ())
1400 struct cgraph_edge
*curr
= heap
.extract_min ();
1401 struct cgraph_node
*cnode
, *dest
= curr
->callee
;
1403 if (!can_inline_edge_p (curr
, true))
1406 /* MASTER_CLONE is produced in the case we already started modified
1407 the function. Be sure to redirect edge to the original body before
1408 estimating growths otherwise we will be seeing growths after inlining
1409 the already modified body. */
1412 curr
->redirect_callee (master_clone
);
1413 reset_edge_growth_cache (curr
);
1416 if (estimate_size_after_inlining (node
, curr
) > limit
)
1418 curr
->redirect_callee (dest
);
1419 reset_edge_growth_cache (curr
);
1424 for (cnode
= curr
->caller
;
1425 cnode
->global
.inlined_to
; cnode
= cnode
->callers
->caller
)
1427 == curr
->callee
->ultimate_alias_target ()->decl
)
1430 if (!want_inline_self_recursive_call_p (curr
, node
, false, depth
))
1432 curr
->redirect_callee (dest
);
1433 reset_edge_growth_cache (curr
);
1440 " Inlining call of depth %i", depth
);
1443 fprintf (dump_file
, " called approx. %.2f times per call",
1444 (double)curr
->count
/ node
->count
);
1446 fprintf (dump_file
, "\n");
1450 /* We need original clone to copy around. */
1451 master_clone
= node
->create_clone (node
->decl
, node
->count
,
1452 CGRAPH_FREQ_BASE
, false, vNULL
,
1454 for (e
= master_clone
->callees
; e
; e
= e
->next_callee
)
1455 if (!e
->inline_failed
)
1456 clone_inlined_nodes (e
, true, false, NULL
, CGRAPH_FREQ_BASE
);
1457 curr
->redirect_callee (master_clone
);
1458 reset_edge_growth_cache (curr
);
1461 inline_call (curr
, false, new_edges
, &overall_size
, true);
1462 lookup_recursive_calls (node
, curr
->callee
, &heap
);
1466 if (!heap
.empty () && dump_file
)
1467 fprintf (dump_file
, " Recursive inlining growth limit met.\n");
1474 "\n Inlined %i times, "
1475 "body grown from size %i to %i, time %i to %i\n", n
,
1476 inline_summaries
->get (master_clone
)->size
, inline_summaries
->get (node
)->size
,
1477 inline_summaries
->get (master_clone
)->time
, inline_summaries
->get (node
)->time
);
1479 /* Remove master clone we used for inlining. We rely that clones inlined
1480 into master clone gets queued just before master clone so we don't
1482 for (node
= symtab
->first_function (); node
!= master_clone
;
1485 next
= symtab
->next_function (node
);
1486 if (node
->global
.inlined_to
== master_clone
)
1489 master_clone
->remove ();
1494 /* Given whole compilation unit estimate of INSNS, compute how large we can
1495 allow the unit to grow. */
1498 compute_max_insns (int insns
)
1500 int max_insns
= insns
;
1501 if (max_insns
< PARAM_VALUE (PARAM_LARGE_UNIT_INSNS
))
1502 max_insns
= PARAM_VALUE (PARAM_LARGE_UNIT_INSNS
);
1504 return ((int64_t) max_insns
1505 * (100 + PARAM_VALUE (PARAM_INLINE_UNIT_GROWTH
)) / 100);
1509 /* Compute badness of all edges in NEW_EDGES and add them to the HEAP. */
1512 add_new_edges_to_heap (edge_heap_t
*heap
, vec
<cgraph_edge
*> new_edges
)
1514 while (new_edges
.length () > 0)
1516 struct cgraph_edge
*edge
= new_edges
.pop ();
1518 gcc_assert (!edge
->aux
);
1519 if (edge
->inline_failed
1520 && can_inline_edge_p (edge
, true)
1521 && want_inline_small_function_p (edge
, true))
1522 edge
->aux
= heap
->insert (edge_badness (edge
, false), edge
);
1526 /* Remove EDGE from the fibheap. */
1529 heap_edge_removal_hook (struct cgraph_edge
*e
, void *data
)
1533 ((edge_heap_t
*)data
)->delete_node ((edge_heap_node_t
*)e
->aux
);
1538 /* Return true if speculation of edge E seems useful.
1539 If ANTICIPATE_INLINING is true, be conservative and hope that E
1543 speculation_useful_p (struct cgraph_edge
*e
, bool anticipate_inlining
)
1545 enum availability avail
;
1546 struct cgraph_node
*target
= e
->callee
->ultimate_alias_target (&avail
);
1547 struct cgraph_edge
*direct
, *indirect
;
1548 struct ipa_ref
*ref
;
1550 gcc_assert (e
->speculative
&& !e
->indirect_unknown_callee
);
1552 if (!e
->maybe_hot_p ())
1555 /* See if IP optimizations found something potentially useful about the
1556 function. For now we look only for CONST/PURE flags. Almost everything
1557 else we propagate is useless. */
1558 if (avail
>= AVAIL_AVAILABLE
)
1560 int ecf_flags
= flags_from_decl_or_type (target
->decl
);
1561 if (ecf_flags
& ECF_CONST
)
1563 e
->speculative_call_info (direct
, indirect
, ref
);
1564 if (!(indirect
->indirect_info
->ecf_flags
& ECF_CONST
))
1567 else if (ecf_flags
& ECF_PURE
)
1569 e
->speculative_call_info (direct
, indirect
, ref
);
1570 if (!(indirect
->indirect_info
->ecf_flags
& ECF_PURE
))
1574 /* If we did not managed to inline the function nor redirect
1575 to an ipa-cp clone (that are seen by having local flag set),
1576 it is probably pointless to inline it unless hardware is missing
1577 indirect call predictor. */
1578 if (!anticipate_inlining
&& e
->inline_failed
&& !target
->local
.local
)
1580 /* For overwritable targets there is not much to do. */
1581 if (e
->inline_failed
&& !can_inline_edge_p (e
, false, true))
1583 /* OK, speculation seems interesting. */
1587 /* We know that EDGE is not going to be inlined.
1588 See if we can remove speculation. */
1591 resolve_noninline_speculation (edge_heap_t
*edge_heap
, struct cgraph_edge
*edge
)
1593 if (edge
->speculative
&& !speculation_useful_p (edge
, false))
1595 struct cgraph_node
*node
= edge
->caller
;
1596 struct cgraph_node
*where
= node
->global
.inlined_to
1597 ? node
->global
.inlined_to
: node
;
1598 bitmap updated_nodes
= BITMAP_ALLOC (NULL
);
1600 spec_rem
+= edge
->count
;
1601 edge
->resolve_speculation ();
1602 reset_edge_caches (where
);
1603 inline_update_overall_summary (where
);
1604 update_caller_keys (edge_heap
, where
,
1605 updated_nodes
, NULL
);
1606 update_callee_keys (edge_heap
, where
,
1608 BITMAP_FREE (updated_nodes
);
1612 /* Return true if NODE should be accounted for overall size estimate.
1613 Skip all nodes optimized for size so we can measure the growth of hot
1614 part of program no matter of the padding. */
1617 inline_account_function_p (struct cgraph_node
*node
)
1619 return (!DECL_EXTERNAL (node
->decl
)
1620 && !opt_for_fn (node
->decl
, optimize_size
)
1621 && node
->frequency
!= NODE_FREQUENCY_UNLIKELY_EXECUTED
);
1624 /* We use greedy algorithm for inlining of small functions:
1625 All inline candidates are put into prioritized heap ordered in
1628 The inlining of small functions is bounded by unit growth parameters. */
1631 inline_small_functions (void)
1633 struct cgraph_node
*node
;
1634 struct cgraph_edge
*edge
;
1635 edge_heap_t
edge_heap (sreal::min ());
1636 bitmap updated_nodes
= BITMAP_ALLOC (NULL
);
1637 int min_size
, max_size
;
1638 auto_vec
<cgraph_edge
*> new_indirect_edges
;
1639 int initial_size
= 0;
1640 struct cgraph_node
**order
= XCNEWVEC (cgraph_node
*, symtab
->cgraph_count
);
1641 struct cgraph_edge_hook_list
*edge_removal_hook_holder
;
1642 new_indirect_edges
.create (8);
1644 edge_removal_hook_holder
1645 = symtab
->add_edge_removal_hook (&heap_edge_removal_hook
, &edge_heap
);
1647 /* Compute overall unit size and other global parameters used by badness
1651 ipa_reduced_postorder (order
, true, true, NULL
);
1654 FOR_EACH_DEFINED_FUNCTION (node
)
1655 if (!node
->global
.inlined_to
)
1657 if (!node
->alias
&& node
->analyzed
1658 && (node
->has_gimple_body_p () || node
->thunk
.thunk_p
))
1660 struct inline_summary
*info
= inline_summaries
->get (node
);
1661 struct ipa_dfs_info
*dfs
= (struct ipa_dfs_info
*) node
->aux
;
1663 /* Do not account external functions, they will be optimized out
1664 if not inlined. Also only count the non-cold portion of program. */
1665 if (inline_account_function_p (node
))
1666 initial_size
+= info
->size
;
1667 info
->growth
= estimate_growth (node
);
1668 if (dfs
&& dfs
->next_cycle
)
1670 struct cgraph_node
*n2
;
1671 int id
= dfs
->scc_no
+ 1;
1673 n2
= ((struct ipa_dfs_info
*) node
->aux
)->next_cycle
)
1675 struct inline_summary
*info2
= inline_summaries
->get (n2
);
1683 for (edge
= node
->callers
; edge
; edge
= edge
->next_caller
)
1684 if (max_count
< edge
->count
)
1685 max_count
= edge
->count
;
1687 ipa_free_postorder_info ();
1688 initialize_growth_caches ();
1692 "\nDeciding on inlining of small functions. Starting with size %i.\n",
1695 overall_size
= initial_size
;
1696 max_size
= compute_max_insns (overall_size
);
1697 min_size
= overall_size
;
1699 /* Populate the heap with all edges we might inline. */
1701 FOR_EACH_DEFINED_FUNCTION (node
)
1703 bool update
= false;
1704 struct cgraph_edge
*next
;
1707 fprintf (dump_file
, "Enqueueing calls in %s/%i.\n",
1708 node
->name (), node
->order
);
1710 for (edge
= node
->callees
; edge
; edge
= next
)
1712 next
= edge
->next_callee
;
1713 if (edge
->inline_failed
1715 && can_inline_edge_p (edge
, true)
1716 && want_inline_small_function_p (edge
, true)
1717 && edge
->inline_failed
)
1719 gcc_assert (!edge
->aux
);
1720 update_edge_key (&edge_heap
, edge
);
1722 if (edge
->speculative
&& !speculation_useful_p (edge
, edge
->aux
!= NULL
))
1724 edge
->resolve_speculation ();
1730 struct cgraph_node
*where
= node
->global
.inlined_to
1731 ? node
->global
.inlined_to
: node
;
1732 inline_update_overall_summary (where
);
1733 reset_edge_caches (where
);
1734 update_caller_keys (&edge_heap
, where
,
1735 updated_nodes
, NULL
);
1736 update_callee_keys (&edge_heap
, where
,
1738 bitmap_clear (updated_nodes
);
1742 gcc_assert (in_lto_p
1744 || (profile_info
&& flag_branch_probabilities
));
1746 while (!edge_heap
.empty ())
1748 int old_size
= overall_size
;
1749 struct cgraph_node
*where
, *callee
;
1750 sreal badness
= edge_heap
.min_key ();
1751 sreal current_badness
;
1754 edge
= edge_heap
.extract_min ();
1755 gcc_assert (edge
->aux
);
1757 if (!edge
->inline_failed
|| !edge
->callee
->analyzed
)
1760 #ifdef ENABLE_CHECKING
1761 /* Be sure that caches are maintained consistent. */
1762 sreal cached_badness
= edge_badness (edge
, false);
1764 int old_size_est
= estimate_edge_size (edge
);
1765 int old_time_est
= estimate_edge_time (edge
);
1766 int old_hints_est
= estimate_edge_hints (edge
);
1768 reset_edge_growth_cache (edge
);
1769 gcc_assert (old_size_est
== estimate_edge_size (edge
));
1770 gcc_assert (old_time_est
== estimate_edge_time (edge
));
1773 gcc_assert (old_hints_est == estimate_edge_hints (edge));
1775 fails with profile feedback because some hints depends on
1776 maybe_hot_edge_p predicate and because callee gets inlined to other
1777 calls, the edge may become cold.
1778 This ought to be fixed by computing relative probabilities
1779 for given invocation but that will be better done once whole
1780 code is converted to sreals. Disable for now and revert to "wrong"
1781 value so enable/disable checking paths agree. */
1782 edge_growth_cache
[edge
->uid
].hints
= old_hints_est
+ 1;
1784 /* When updating the edge costs, we only decrease badness in the keys.
1785 Increases of badness are handled lazilly; when we see key with out
1786 of date value on it, we re-insert it now. */
1787 current_badness
= edge_badness (edge
, false);
1788 /* Disable checking for profile because roundoff errors may cause slight
1789 deviations in the order. */
1790 gcc_assert (max_count
|| cached_badness
== current_badness
);
1791 gcc_assert (current_badness
>= badness
);
1793 current_badness
= edge_badness (edge
, false);
1795 if (current_badness
!= badness
)
1797 if (edge_heap
.min () && current_badness
> edge_heap
.min_key ())
1799 edge
->aux
= edge_heap
.insert (current_badness
, edge
);
1803 badness
= current_badness
;
1806 if (!can_inline_edge_p (edge
, true))
1808 resolve_noninline_speculation (&edge_heap
, edge
);
1812 callee
= edge
->callee
->ultimate_alias_target ();
1813 growth
= estimate_edge_growth (edge
);
1817 "\nConsidering %s/%i with %i size\n",
1818 callee
->name (), callee
->order
,
1819 inline_summaries
->get (callee
)->size
);
1821 " to be inlined into %s/%i in %s:%i\n"
1822 " Estimated badness is %f, frequency %.2f.\n",
1823 edge
->caller
->name (), edge
->caller
->order
,
1825 ? gimple_filename ((const_gimple
) edge
->call_stmt
)
1828 ? gimple_lineno ((const_gimple
) edge
->call_stmt
)
1830 badness
.to_double (),
1831 edge
->frequency
/ (double)CGRAPH_FREQ_BASE
);
1833 fprintf (dump_file
," Called %"PRId64
"x\n",
1835 if (dump_flags
& TDF_DETAILS
)
1836 edge_badness (edge
, true);
1839 if (overall_size
+ growth
> max_size
1840 && !DECL_DISREGARD_INLINE_LIMITS (callee
->decl
))
1842 edge
->inline_failed
= CIF_INLINE_UNIT_GROWTH_LIMIT
;
1843 report_inline_failed_reason (edge
);
1844 resolve_noninline_speculation (&edge_heap
, edge
);
1848 if (!want_inline_small_function_p (edge
, true))
1850 resolve_noninline_speculation (&edge_heap
, edge
);
1854 /* Heuristics for inlining small functions work poorly for
1855 recursive calls where we do effects similar to loop unrolling.
1856 When inlining such edge seems profitable, leave decision on
1857 specific inliner. */
1858 if (edge
->recursive_p ())
1860 where
= edge
->caller
;
1861 if (where
->global
.inlined_to
)
1862 where
= where
->global
.inlined_to
;
1863 if (!recursive_inlining (edge
,
1864 opt_for_fn (edge
->caller
->decl
,
1865 flag_indirect_inlining
)
1866 ? &new_indirect_edges
: NULL
))
1868 edge
->inline_failed
= CIF_RECURSIVE_INLINING
;
1869 resolve_noninline_speculation (&edge_heap
, edge
);
1872 reset_edge_caches (where
);
1873 /* Recursive inliner inlines all recursive calls of the function
1874 at once. Consequently we need to update all callee keys. */
1875 if (opt_for_fn (edge
->caller
->decl
, flag_indirect_inlining
))
1876 add_new_edges_to_heap (&edge_heap
, new_indirect_edges
);
1877 update_callee_keys (&edge_heap
, where
, updated_nodes
);
1878 bitmap_clear (updated_nodes
);
1882 struct cgraph_node
*outer_node
= NULL
;
1885 /* Consider the case where self recursive function A is inlined
1886 into B. This is desired optimization in some cases, since it
1887 leads to effect similar of loop peeling and we might completely
1888 optimize out the recursive call. However we must be extra
1891 where
= edge
->caller
;
1892 while (where
->global
.inlined_to
)
1894 if (where
->decl
== callee
->decl
)
1895 outer_node
= where
, depth
++;
1896 where
= where
->callers
->caller
;
1899 && !want_inline_self_recursive_call_p (edge
, outer_node
,
1903 = (DECL_DISREGARD_INLINE_LIMITS (edge
->callee
->decl
)
1904 ? CIF_RECURSIVE_INLINING
: CIF_UNSPECIFIED
);
1905 resolve_noninline_speculation (&edge_heap
, edge
);
1908 else if (depth
&& dump_file
)
1909 fprintf (dump_file
, " Peeling recursion with depth %i\n", depth
);
1911 gcc_checking_assert (!callee
->global
.inlined_to
);
1912 inline_call (edge
, true, &new_indirect_edges
, &overall_size
, true);
1913 add_new_edges_to_heap (&edge_heap
, new_indirect_edges
);
1915 reset_edge_caches (edge
->callee
->function_symbol ());
1917 update_callee_keys (&edge_heap
, where
, updated_nodes
);
1919 where
= edge
->caller
;
1920 if (where
->global
.inlined_to
)
1921 where
= where
->global
.inlined_to
;
1923 /* Our profitability metric can depend on local properties
1924 such as number of inlinable calls and size of the function body.
1925 After inlining these properties might change for the function we
1926 inlined into (since it's body size changed) and for the functions
1927 called by function we inlined (since number of it inlinable callers
1929 update_caller_keys (&edge_heap
, where
, updated_nodes
, NULL
);
1930 /* Offline copy count has possibly changed, recompute if profile is
1934 struct cgraph_node
*n
= cgraph_node::get (edge
->callee
->decl
);
1935 if (n
!= edge
->callee
&& n
->analyzed
)
1936 update_callee_keys (&edge_heap
, n
, updated_nodes
);
1938 bitmap_clear (updated_nodes
);
1943 " Inlined into %s which now has time %i and size %i,"
1944 "net change of %+i.\n",
1945 edge
->caller
->name (),
1946 inline_summaries
->get (edge
->caller
)->time
,
1947 inline_summaries
->get (edge
->caller
)->size
,
1948 overall_size
- old_size
);
1950 if (min_size
> overall_size
)
1952 min_size
= overall_size
;
1953 max_size
= compute_max_insns (min_size
);
1956 fprintf (dump_file
, "New minimal size reached: %i\n", min_size
);
1960 free_growth_caches ();
1963 "Unit growth for small function inlining: %i->%i (%i%%)\n",
1964 initial_size
, overall_size
,
1965 initial_size
? overall_size
* 100 / (initial_size
) - 100: 0);
1966 BITMAP_FREE (updated_nodes
);
1967 symtab
->remove_edge_removal_hook (edge_removal_hook_holder
);
1970 /* Flatten NODE. Performed both during early inlining and
1971 at IPA inlining time. */
1974 flatten_function (struct cgraph_node
*node
, bool early
)
1976 struct cgraph_edge
*e
;
1978 /* We shouldn't be called recursively when we are being processed. */
1979 gcc_assert (node
->aux
== NULL
);
1981 node
->aux
= (void *) node
;
1983 for (e
= node
->callees
; e
; e
= e
->next_callee
)
1985 struct cgraph_node
*orig_callee
;
1986 struct cgraph_node
*callee
= e
->callee
->ultimate_alias_target ();
1988 /* We've hit cycle? It is time to give up. */
1993 "Not inlining %s into %s to avoid cycle.\n",
1994 xstrdup_for_dump (callee
->name ()),
1995 xstrdup_for_dump (e
->caller
->name ()));
1996 e
->inline_failed
= CIF_RECURSIVE_INLINING
;
2000 /* When the edge is already inlined, we just need to recurse into
2001 it in order to fully flatten the leaves. */
2002 if (!e
->inline_failed
)
2004 flatten_function (callee
, early
);
2008 /* Flatten attribute needs to be processed during late inlining. For
2009 extra code quality we however do flattening during early optimization,
2012 ? !can_inline_edge_p (e
, true)
2013 : !can_early_inline_edge_p (e
))
2016 if (e
->recursive_p ())
2019 fprintf (dump_file
, "Not inlining: recursive call.\n");
2023 if (gimple_in_ssa_p (DECL_STRUCT_FUNCTION (node
->decl
))
2024 != gimple_in_ssa_p (DECL_STRUCT_FUNCTION (callee
->decl
)))
2027 fprintf (dump_file
, "Not inlining: SSA form does not match.\n");
2031 /* Inline the edge and flatten the inline clone. Avoid
2032 recursing through the original node if the node was cloned. */
2034 fprintf (dump_file
, " Inlining %s into %s.\n",
2035 xstrdup_for_dump (callee
->name ()),
2036 xstrdup_for_dump (e
->caller
->name ()));
2037 orig_callee
= callee
;
2038 inline_call (e
, true, NULL
, NULL
, false);
2039 if (e
->callee
!= orig_callee
)
2040 orig_callee
->aux
= (void *) node
;
2041 flatten_function (e
->callee
, early
);
2042 if (e
->callee
!= orig_callee
)
2043 orig_callee
->aux
= NULL
;
2047 if (!node
->global
.inlined_to
)
2048 inline_update_overall_summary (node
);
2051 /* Count number of callers of NODE and store it into DATA (that
2052 points to int. Worker for cgraph_for_node_and_aliases. */
2055 sum_callers (struct cgraph_node
*node
, void *data
)
2057 struct cgraph_edge
*e
;
2058 int *num_calls
= (int *)data
;
2060 for (e
= node
->callers
; e
; e
= e
->next_caller
)
2065 /* Inline NODE to all callers. Worker for cgraph_for_node_and_aliases.
2066 DATA points to number of calls originally found so we avoid infinite
2070 inline_to_all_callers (struct cgraph_node
*node
, void *data
)
2072 int *num_calls
= (int *)data
;
2073 bool callee_removed
= false;
2075 while (node
->callers
&& !node
->global
.inlined_to
)
2077 struct cgraph_node
*caller
= node
->callers
->caller
;
2082 "\nInlining %s size %i.\n",
2084 inline_summaries
->get (node
)->size
);
2086 " Called once from %s %i insns.\n",
2087 node
->callers
->caller
->name (),
2088 inline_summaries
->get (node
->callers
->caller
)->size
);
2091 inline_call (node
->callers
, true, NULL
, NULL
, true, &callee_removed
);
2094 " Inlined into %s which now has %i size\n",
2096 inline_summaries
->get (caller
)->size
);
2097 if (!(*num_calls
)--)
2100 fprintf (dump_file
, "New calls found; giving up.\n");
2101 return callee_removed
;
2109 /* Output overall time estimate. */
2111 dump_overall_stats (void)
2113 int64_t sum_weighted
= 0, sum
= 0;
2114 struct cgraph_node
*node
;
2116 FOR_EACH_DEFINED_FUNCTION (node
)
2117 if (!node
->global
.inlined_to
2120 int time
= inline_summaries
->get (node
)->time
;
2122 sum_weighted
+= time
* node
->count
;
2124 fprintf (dump_file
, "Overall time estimate: "
2125 "%"PRId64
" weighted by profile: "
2126 "%"PRId64
"\n", sum
, sum_weighted
);
2129 /* Output some useful stats about inlining. */
2132 dump_inline_stats (void)
2134 int64_t inlined_cnt
= 0, inlined_indir_cnt
= 0;
2135 int64_t inlined_virt_cnt
= 0, inlined_virt_indir_cnt
= 0;
2136 int64_t noninlined_cnt
= 0, noninlined_indir_cnt
= 0;
2137 int64_t noninlined_virt_cnt
= 0, noninlined_virt_indir_cnt
= 0;
2138 int64_t inlined_speculative
= 0, inlined_speculative_ply
= 0;
2139 int64_t indirect_poly_cnt
= 0, indirect_cnt
= 0;
2140 int64_t reason
[CIF_N_REASONS
][3];
2142 struct cgraph_node
*node
;
2144 memset (reason
, 0, sizeof (reason
));
2145 FOR_EACH_DEFINED_FUNCTION (node
)
2147 struct cgraph_edge
*e
;
2148 for (e
= node
->callees
; e
; e
= e
->next_callee
)
2150 if (e
->inline_failed
)
2152 reason
[(int) e
->inline_failed
][0] += e
->count
;
2153 reason
[(int) e
->inline_failed
][1] += e
->frequency
;
2154 reason
[(int) e
->inline_failed
][2] ++;
2155 if (DECL_VIRTUAL_P (e
->callee
->decl
))
2157 if (e
->indirect_inlining_edge
)
2158 noninlined_virt_indir_cnt
+= e
->count
;
2160 noninlined_virt_cnt
+= e
->count
;
2164 if (e
->indirect_inlining_edge
)
2165 noninlined_indir_cnt
+= e
->count
;
2167 noninlined_cnt
+= e
->count
;
2174 if (DECL_VIRTUAL_P (e
->callee
->decl
))
2175 inlined_speculative_ply
+= e
->count
;
2177 inlined_speculative
+= e
->count
;
2179 else if (DECL_VIRTUAL_P (e
->callee
->decl
))
2181 if (e
->indirect_inlining_edge
)
2182 inlined_virt_indir_cnt
+= e
->count
;
2184 inlined_virt_cnt
+= e
->count
;
2188 if (e
->indirect_inlining_edge
)
2189 inlined_indir_cnt
+= e
->count
;
2191 inlined_cnt
+= e
->count
;
2195 for (e
= node
->indirect_calls
; e
; e
= e
->next_callee
)
2196 if (e
->indirect_info
->polymorphic
)
2197 indirect_poly_cnt
+= e
->count
;
2199 indirect_cnt
+= e
->count
;
2204 "Inlined %"PRId64
" + speculative "
2205 "%"PRId64
" + speculative polymorphic "
2206 "%"PRId64
" + previously indirect "
2207 "%"PRId64
" + virtual "
2208 "%"PRId64
" + virtual and previously indirect "
2209 "%"PRId64
"\n" "Not inlined "
2210 "%"PRId64
" + previously indirect "
2211 "%"PRId64
" + virtual "
2212 "%"PRId64
" + virtual and previously indirect "
2213 "%"PRId64
" + stil indirect "
2214 "%"PRId64
" + still indirect polymorphic "
2215 "%"PRId64
"\n", inlined_cnt
,
2216 inlined_speculative
, inlined_speculative_ply
,
2217 inlined_indir_cnt
, inlined_virt_cnt
, inlined_virt_indir_cnt
,
2218 noninlined_cnt
, noninlined_indir_cnt
, noninlined_virt_cnt
,
2219 noninlined_virt_indir_cnt
, indirect_cnt
, indirect_poly_cnt
);
2221 "Removed speculations %"PRId64
"\n",
2224 dump_overall_stats ();
2225 fprintf (dump_file
, "\nWhy inlining failed?\n");
2226 for (i
= 0; i
< CIF_N_REASONS
; i
++)
2228 fprintf (dump_file
, "%-50s: %8i calls, %8i freq, %"PRId64
" count\n",
2229 cgraph_inline_failed_string ((cgraph_inline_failed_t
) i
),
2230 (int) reason
[i
][2], (int) reason
[i
][1], reason
[i
][0]);
2233 /* Decide on the inlining. We do so in the topological order to avoid
2234 expenses on updating data structures. */
2239 struct cgraph_node
*node
;
2241 struct cgraph_node
**order
;
2244 bool remove_functions
= false;
2249 cgraph_freq_base_rec
= (sreal
) 1 / (sreal
) CGRAPH_FREQ_BASE
;
2250 percent_rec
= (sreal
) 1 / (sreal
) 100;
2252 order
= XCNEWVEC (struct cgraph_node
*, symtab
->cgraph_count
);
2254 if (in_lto_p
&& optimize
)
2255 ipa_update_after_lto_read ();
2258 dump_inline_summaries (dump_file
);
2260 nnodes
= ipa_reverse_postorder (order
);
2262 FOR_EACH_FUNCTION (node
)
2266 fprintf (dump_file
, "\nFlattening functions:\n");
2268 /* In the first pass handle functions to be flattened. Do this with
2269 a priority so none of our later choices will make this impossible. */
2270 for (i
= nnodes
- 1; i
>= 0; i
--)
2274 /* Handle nodes to be flattened.
2275 Ideally when processing callees we stop inlining at the
2276 entry of cycles, possibly cloning that entry point and
2277 try to flatten itself turning it into a self-recursive
2279 if (lookup_attribute ("flatten",
2280 DECL_ATTRIBUTES (node
->decl
)) != NULL
)
2284 "Flattening %s\n", node
->name ());
2285 flatten_function (node
, false);
2289 dump_overall_stats ();
2291 inline_small_functions ();
2293 gcc_assert (symtab
->state
== IPA_SSA
);
2294 symtab
->state
= IPA_SSA_AFTER_INLINING
;
2295 /* Do first after-inlining removal. We want to remove all "stale" extern
2296 inline functions and virtual functions so we really know what is called
2298 symtab
->remove_unreachable_nodes (dump_file
);
2301 /* Inline functions with a property that after inlining into all callers the
2302 code size will shrink because the out-of-line copy is eliminated.
2303 We do this regardless on the callee size as long as function growth limits
2307 "\nDeciding on functions to be inlined into all callers and "
2308 "removing useless speculations:\n");
2310 /* Inlining one function called once has good chance of preventing
2311 inlining other function into the same callee. Ideally we should
2312 work in priority order, but probably inlining hot functions first
2313 is good cut without the extra pain of maintaining the queue.
2315 ??? this is not really fitting the bill perfectly: inlining function
2316 into callee often leads to better optimization of callee due to
2317 increased context for optimization.
2318 For example if main() function calls a function that outputs help
2319 and then function that does the main optmization, we should inline
2320 the second with priority even if both calls are cold by themselves.
2322 We probably want to implement new predicate replacing our use of
2323 maybe_hot_edge interpreted as maybe_hot_edge || callee is known
2325 for (cold
= 0; cold
<= 1; cold
++)
2327 FOR_EACH_DEFINED_FUNCTION (node
)
2329 struct cgraph_edge
*edge
, *next
;
2332 for (edge
= node
->callees
; edge
; edge
= next
)
2334 next
= edge
->next_callee
;
2335 if (edge
->speculative
&& !speculation_useful_p (edge
, false))
2337 edge
->resolve_speculation ();
2338 spec_rem
+= edge
->count
;
2340 remove_functions
= true;
2345 struct cgraph_node
*where
= node
->global
.inlined_to
2346 ? node
->global
.inlined_to
: node
;
2347 reset_edge_caches (where
);
2348 inline_update_overall_summary (where
);
2350 if (want_inline_function_to_all_callers_p (node
, cold
))
2353 node
->call_for_symbol_thunks_and_aliases (sum_callers
, &num_calls
,
2355 while (node
->call_for_symbol_thunks_and_aliases
2356 (inline_to_all_callers
, &num_calls
, true))
2358 remove_functions
= true;
2363 /* Free ipa-prop structures if they are no longer needed. */
2365 ipa_free_all_structures_after_iinln ();
2370 "\nInlined %i calls, eliminated %i functions\n\n",
2371 ncalls_inlined
, nfunctions_inlined
);
2372 dump_inline_stats ();
2376 dump_inline_summaries (dump_file
);
2377 /* In WPA we use inline summaries for partitioning process. */
2379 inline_free_summary ();
2380 return remove_functions
? TODO_remove_functions
: 0;
2383 /* Inline always-inline function calls in NODE. */
2386 inline_always_inline_functions (struct cgraph_node
*node
)
2388 struct cgraph_edge
*e
;
2389 bool inlined
= false;
2391 for (e
= node
->callees
; e
; e
= e
->next_callee
)
2393 struct cgraph_node
*callee
= e
->callee
->ultimate_alias_target ();
2394 if (!DECL_DISREGARD_INLINE_LIMITS (callee
->decl
))
2397 if (e
->recursive_p ())
2400 fprintf (dump_file
, " Not inlining recursive call to %s.\n",
2401 e
->callee
->name ());
2402 e
->inline_failed
= CIF_RECURSIVE_INLINING
;
2406 if (!can_early_inline_edge_p (e
))
2408 /* Set inlined to true if the callee is marked "always_inline" but
2409 is not inlinable. This will allow flagging an error later in
2410 expand_call_inline in tree-inline.c. */
2411 if (lookup_attribute ("always_inline",
2412 DECL_ATTRIBUTES (callee
->decl
)) != NULL
)
2418 fprintf (dump_file
, " Inlining %s into %s (always_inline).\n",
2419 xstrdup_for_dump (e
->callee
->name ()),
2420 xstrdup_for_dump (e
->caller
->name ()));
2421 inline_call (e
, true, NULL
, NULL
, false);
2425 inline_update_overall_summary (node
);
2430 /* Decide on the inlining. We do so in the topological order to avoid
2431 expenses on updating data structures. */
2434 early_inline_small_functions (struct cgraph_node
*node
)
2436 struct cgraph_edge
*e
;
2437 bool inlined
= false;
2439 for (e
= node
->callees
; e
; e
= e
->next_callee
)
2441 struct cgraph_node
*callee
= e
->callee
->ultimate_alias_target ();
2442 if (!inline_summaries
->get (callee
)->inlinable
2443 || !e
->inline_failed
)
2446 /* Do not consider functions not declared inline. */
2447 if (!DECL_DECLARED_INLINE_P (callee
->decl
)
2448 && !opt_for_fn (node
->decl
, flag_inline_small_functions
)
2449 && !opt_for_fn (node
->decl
, flag_inline_functions
))
2453 fprintf (dump_file
, "Considering inline candidate %s.\n",
2456 if (!can_early_inline_edge_p (e
))
2459 if (e
->recursive_p ())
2462 fprintf (dump_file
, " Not inlining: recursive call.\n");
2466 if (!want_early_inline_function_p (e
))
2470 fprintf (dump_file
, " Inlining %s into %s.\n",
2471 xstrdup_for_dump (callee
->name ()),
2472 xstrdup_for_dump (e
->caller
->name ()));
2473 inline_call (e
, true, NULL
, NULL
, true);
2481 early_inliner (function
*fun
)
2483 struct cgraph_node
*node
= cgraph_node::get (current_function_decl
);
2484 struct cgraph_edge
*edge
;
2485 unsigned int todo
= 0;
2487 bool inlined
= false;
2492 /* Do nothing if datastructures for ipa-inliner are already computed. This
2493 happens when some pass decides to construct new function and
2494 cgraph_add_new_function calls lowering passes and early optimization on
2495 it. This may confuse ourself when early inliner decide to inline call to
2496 function clone, because function clones don't have parameter list in
2497 ipa-prop matching their signature. */
2498 if (ipa_node_params_sum
)
2501 #ifdef ENABLE_CHECKING
2504 node
->remove_all_references ();
2506 /* Even when not optimizing or not inlining inline always-inline
2508 inlined
= inline_always_inline_functions (node
);
2512 || !flag_early_inlining
2513 /* Never inline regular functions into always-inline functions
2514 during incremental inlining. This sucks as functions calling
2515 always inline functions will get less optimized, but at the
2516 same time inlining of functions calling always inline
2517 function into an always inline function might introduce
2518 cycles of edges to be always inlined in the callgraph.
2520 We might want to be smarter and just avoid this type of inlining. */
2521 || DECL_DISREGARD_INLINE_LIMITS (node
->decl
))
2523 else if (lookup_attribute ("flatten",
2524 DECL_ATTRIBUTES (node
->decl
)) != NULL
)
2526 /* When the function is marked to be flattened, recursively inline
2530 "Flattening %s\n", node
->name ());
2531 flatten_function (node
, true);
2536 /* We iterate incremental inlining to get trivial cases of indirect
2538 while (iterations
< PARAM_VALUE (PARAM_EARLY_INLINER_MAX_ITERATIONS
)
2539 && early_inline_small_functions (node
))
2541 timevar_push (TV_INTEGRATION
);
2542 todo
|= optimize_inline_calls (current_function_decl
);
2544 /* Technically we ought to recompute inline parameters so the new
2545 iteration of early inliner works as expected. We however have
2546 values approximately right and thus we only need to update edge
2547 info that might be cleared out for newly discovered edges. */
2548 for (edge
= node
->callees
; edge
; edge
= edge
->next_callee
)
2550 /* We have no summary for new bound store calls yet. */
2551 if (inline_edge_summary_vec
.length () > (unsigned)edge
->uid
)
2553 struct inline_edge_summary
*es
= inline_edge_summary (edge
);
2555 = estimate_num_insns (edge
->call_stmt
, &eni_size_weights
);
2557 = estimate_num_insns (edge
->call_stmt
, &eni_time_weights
);
2559 if (edge
->callee
->decl
2560 && !gimple_check_call_matching_types (
2561 edge
->call_stmt
, edge
->callee
->decl
, false))
2562 edge
->call_stmt_cannot_inline_p
= true;
2564 if (iterations
< PARAM_VALUE (PARAM_EARLY_INLINER_MAX_ITERATIONS
) - 1)
2565 inline_update_overall_summary (node
);
2566 timevar_pop (TV_INTEGRATION
);
2571 fprintf (dump_file
, "Iterations: %i\n", iterations
);
2576 timevar_push (TV_INTEGRATION
);
2577 todo
|= optimize_inline_calls (current_function_decl
);
2578 timevar_pop (TV_INTEGRATION
);
2581 fun
->always_inline_functions_inlined
= true;
2586 /* Do inlining of small functions. Doing so early helps profiling and other
2587 passes to be somewhat more effective and avoids some code duplication in
2588 later real inlining pass for testcases with very many function calls. */
2592 const pass_data pass_data_early_inline
=
2594 GIMPLE_PASS
, /* type */
2595 "einline", /* name */
2596 OPTGROUP_INLINE
, /* optinfo_flags */
2597 TV_EARLY_INLINING
, /* tv_id */
2598 PROP_ssa
, /* properties_required */
2599 0, /* properties_provided */
2600 0, /* properties_destroyed */
2601 0, /* todo_flags_start */
2602 0, /* todo_flags_finish */
2605 class pass_early_inline
: public gimple_opt_pass
2608 pass_early_inline (gcc::context
*ctxt
)
2609 : gimple_opt_pass (pass_data_early_inline
, ctxt
)
2612 /* opt_pass methods: */
2613 virtual unsigned int execute (function
*);
2615 }; // class pass_early_inline
2618 pass_early_inline::execute (function
*fun
)
2620 return early_inliner (fun
);
2626 make_pass_early_inline (gcc::context
*ctxt
)
2628 return new pass_early_inline (ctxt
);
2633 const pass_data pass_data_ipa_inline
=
2635 IPA_PASS
, /* type */
2636 "inline", /* name */
2637 OPTGROUP_INLINE
, /* optinfo_flags */
2638 TV_IPA_INLINING
, /* tv_id */
2639 0, /* properties_required */
2640 0, /* properties_provided */
2641 0, /* properties_destroyed */
2642 0, /* todo_flags_start */
2643 ( TODO_dump_symtab
), /* todo_flags_finish */
2646 class pass_ipa_inline
: public ipa_opt_pass_d
2649 pass_ipa_inline (gcc::context
*ctxt
)
2650 : ipa_opt_pass_d (pass_data_ipa_inline
, ctxt
,
2651 inline_generate_summary
, /* generate_summary */
2652 inline_write_summary
, /* write_summary */
2653 inline_read_summary
, /* read_summary */
2654 NULL
, /* write_optimization_summary */
2655 NULL
, /* read_optimization_summary */
2656 NULL
, /* stmt_fixup */
2657 0, /* function_transform_todo_flags_start */
2658 inline_transform
, /* function_transform */
2659 NULL
) /* variable_transform */
2662 /* opt_pass methods: */
2663 virtual unsigned int execute (function
*) { return ipa_inline (); }
2665 }; // class pass_ipa_inline
2670 make_pass_ipa_inline (gcc::context
*ctxt
)
2672 return new pass_ipa_inline (ctxt
);