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
->ultimate_alias_target ()->lto_file_data
)
238 fprintf (dump_file
, " LTO objects: %s, %s\n",
239 e
->caller
->lto_file_data
->file_name
,
240 e
->callee
->ultimate_alias_target ()->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 /* All edges with call_stmt_cannot_inline_p should have inline_failed
339 initialized to one of FINAL_ERROR reasons. */
340 else if (e
->call_stmt_cannot_inline_p
)
342 /* Don't inline if the functions have different EH personalities. */
343 else if (DECL_FUNCTION_PERSONALITY (caller
->decl
)
344 && DECL_FUNCTION_PERSONALITY (callee
->decl
)
345 && (DECL_FUNCTION_PERSONALITY (caller
->decl
)
346 != DECL_FUNCTION_PERSONALITY (callee
->decl
)))
348 e
->inline_failed
= CIF_EH_PERSONALITY
;
351 /* TM pure functions should not be inlined into non-TM_pure
353 else if (is_tm_pure (callee
->decl
) && !is_tm_pure (caller
->decl
))
355 e
->inline_failed
= CIF_UNSPECIFIED
;
358 /* Check compatibility of target optimization options. */
359 else if (!targetm
.target_option
.can_inline_p (caller
->decl
,
362 e
->inline_failed
= CIF_TARGET_OPTION_MISMATCH
;
365 else if (!inline_summaries
->get (callee
)->inlinable
)
367 e
->inline_failed
= CIF_FUNCTION_NOT_INLINABLE
;
370 else if (inline_summaries
->get (caller
)->contains_cilk_spawn
)
372 e
->inline_failed
= CIF_CILK_SPAWN
;
375 /* Don't inline a function with mismatched sanitization attributes. */
376 else if (!sanitize_attrs_match_for_inline_p (caller
->decl
, callee
->decl
))
378 e
->inline_failed
= CIF_ATTRIBUTE_MISMATCH
;
381 /* Check if caller growth allows the inlining. */
382 else if (!DECL_DISREGARD_INLINE_LIMITS (callee
->decl
)
384 && !lookup_attribute ("flatten",
385 DECL_ATTRIBUTES (caller
->decl
))
386 && !caller_growth_limits (e
))
388 /* Don't inline a function with a higher optimization level than the
389 caller. FIXME: this is really just tip of iceberg of handling
390 optimization attribute. */
391 else if (caller_tree
!= callee_tree
)
394 (DECL_DISREGARD_INLINE_LIMITS (callee
->decl
)
395 && lookup_attribute ("always_inline",
396 DECL_ATTRIBUTES (callee
->decl
)));
397 inline_summary
*caller_info
= inline_summaries
->get (caller
);
398 inline_summary
*callee_info
= inline_summaries
->get (callee
);
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 /* When caller or callee does FP math, be sure FP codegen flags
422 || ((caller_info
->fp_expressions
&& callee_info
->fp_expressions
)
423 && (check_maybe_up (flag_rounding_math
)
424 || check_maybe_up (flag_trapping_math
)
425 || check_maybe_down (flag_unsafe_math_optimizations
)
426 || check_maybe_down (flag_finite_math_only
)
427 || check_maybe_up (flag_signaling_nans
)
428 || check_maybe_down (flag_cx_limited_range
)
429 || check_maybe_up (flag_signed_zeros
)
430 || check_maybe_down (flag_associative_math
)
431 || check_maybe_down (flag_reciprocal_math
)
432 /* Strictly speaking only when the callee contains function
433 calls that may end up setting errno. */
434 || check_maybe_up (flag_errno_math
)))
435 /* We do not want to make code compiled with exceptions to be
436 brought into a non-EH function unless we know that the callee
438 This is tracked by DECL_FUNCTION_PERSONALITY. */
439 || (check_maybe_up (flag_non_call_exceptions
)
440 && DECL_FUNCTION_PERSONALITY (callee
->decl
))
441 || (check_maybe_up (flag_exceptions
)
442 && DECL_FUNCTION_PERSONALITY (callee
->decl
))
443 /* When devirtualization is diabled for callee, it is not safe
444 to inline it as we possibly mangled the type info.
445 Allow early inlining of always inlines. */
446 || (!early
&& check_maybe_down (flag_devirtualize
)))
448 e
->inline_failed
= CIF_OPTIMIZATION_MISMATCH
;
451 /* gcc.dg/pr43564.c. Apply user-forced inline even at -O0. */
452 else if (always_inline
)
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 explicit optimize attribute are not used, the mismatch is caused
462 by different command line options used to build different units.
463 Do not care about COMDAT functions - those are intended to be
464 optimized with the optimization flags of module they are used in.
465 Also do not care about mixing up size/speed optimization when
466 DECL_DISREGARD_INLINE_LIMITS is set. */
467 else if ((callee
->merged_comdat
468 && !lookup_attribute ("optimize",
469 DECL_ATTRIBUTES (caller
->decl
)))
470 || DECL_DISREGARD_INLINE_LIMITS (callee
->decl
))
472 /* If mismatch is caused by merging two LTO units with different
473 optimizationflags we want to be bit nicer. However never inline
474 if one of functions is not optimized at all. */
475 else if (!opt_for_fn (callee
->decl
, optimize
)
476 || !opt_for_fn (caller
->decl
, optimize
))
478 e
->inline_failed
= CIF_OPTIMIZATION_MISMATCH
;
481 /* If callee is optimized for size and caller is not, allow inlining if
482 code shrinks or we are in MAX_INLINE_INSNS_SINGLE limit and callee
483 is inline (and thus likely an unified comdat). This will allow caller
485 else if (opt_for_fn (callee
->decl
, optimize_size
)
486 > opt_for_fn (caller
->decl
, optimize_size
))
488 int growth
= estimate_edge_growth (e
);
490 && (!DECL_DECLARED_INLINE_P (callee
->decl
)
491 && growth
>= MAX (MAX_INLINE_INSNS_SINGLE
,
492 MAX_INLINE_INSNS_AUTO
)))
494 e
->inline_failed
= CIF_OPTIMIZATION_MISMATCH
;
498 /* If callee is more aggressively optimized for performance than caller,
499 we generally want to inline only cheap (runtime wise) functions. */
500 else if (opt_for_fn (callee
->decl
, optimize_size
)
501 < opt_for_fn (caller
->decl
, optimize_size
)
502 || (opt_for_fn (callee
->decl
, optimize
)
503 > opt_for_fn (caller
->decl
, optimize
)))
505 if (estimate_edge_time (e
)
506 >= 20 + inline_edge_summary (e
)->call_stmt_time
)
508 e
->inline_failed
= CIF_OPTIMIZATION_MISMATCH
;
515 if (!inlinable
&& report
)
516 report_inline_failed_reason (e
);
521 /* Return true if the edge E is inlinable during early inlining. */
524 can_early_inline_edge_p (struct cgraph_edge
*e
)
526 struct cgraph_node
*callee
= e
->callee
->ultimate_alias_target ();
527 /* Early inliner might get called at WPA stage when IPA pass adds new
528 function. In this case we can not really do any of early inlining
529 because function bodies are missing. */
530 if (cgraph_inline_failed_type (e
->inline_failed
) == CIF_FINAL_ERROR
)
532 if (!gimple_has_body_p (callee
->decl
))
534 e
->inline_failed
= CIF_BODY_NOT_AVAILABLE
;
537 /* In early inliner some of callees may not be in SSA form yet
538 (i.e. the callgraph is cyclic and we did not process
539 the callee by early inliner, yet). We don't have CIF code for this
540 case; later we will re-do the decision in the real inliner. */
541 if (!gimple_in_ssa_p (DECL_STRUCT_FUNCTION (e
->caller
->decl
))
542 || !gimple_in_ssa_p (DECL_STRUCT_FUNCTION (callee
->decl
)))
545 fprintf (dump_file
, " edge not inlinable: not in SSA form\n");
548 if (!can_inline_edge_p (e
, true, false, true))
554 /* Return number of calls in N. Ignore cheap builtins. */
557 num_calls (struct cgraph_node
*n
)
559 struct cgraph_edge
*e
;
562 for (e
= n
->callees
; e
; e
= e
->next_callee
)
563 if (!is_inexpensive_builtin (e
->callee
->decl
))
569 /* Return true if we are interested in inlining small function. */
572 want_early_inline_function_p (struct cgraph_edge
*e
)
574 bool want_inline
= true;
575 struct cgraph_node
*callee
= e
->callee
->ultimate_alias_target ();
577 if (DECL_DISREGARD_INLINE_LIMITS (callee
->decl
))
579 /* For AutoFDO, we need to make sure that before profile summary, all
580 hot paths' IR look exactly the same as profiled binary. As a result,
581 in einliner, we will disregard size limit and inline those callsites
583 * inlined in the profiled binary, and
584 * the cloned callee has enough samples to be considered "hot". */
585 else if (flag_auto_profile
&& afdo_callsite_hot_enough_for_early_inline (e
))
587 else if (!DECL_DECLARED_INLINE_P (callee
->decl
)
588 && !opt_for_fn (e
->caller
->decl
, flag_inline_small_functions
))
590 e
->inline_failed
= CIF_FUNCTION_NOT_INLINE_CANDIDATE
;
591 report_inline_failed_reason (e
);
596 int growth
= estimate_edge_growth (e
);
601 else if (!e
->maybe_hot_p ()
605 fprintf (dump_file
, " will not early inline: %s/%i->%s/%i, "
606 "call is cold and code would grow by %i\n",
607 xstrdup_for_dump (e
->caller
->name ()),
609 xstrdup_for_dump (callee
->name ()), callee
->order
,
613 else if (growth
> PARAM_VALUE (PARAM_EARLY_INLINING_INSNS
))
616 fprintf (dump_file
, " will not early inline: %s/%i->%s/%i, "
617 "growth %i exceeds --param early-inlining-insns\n",
618 xstrdup_for_dump (e
->caller
->name ()),
620 xstrdup_for_dump (callee
->name ()), callee
->order
,
624 else if ((n
= num_calls (callee
)) != 0
625 && growth
* (n
+ 1) > PARAM_VALUE (PARAM_EARLY_INLINING_INSNS
))
628 fprintf (dump_file
, " will not early inline: %s/%i->%s/%i, "
629 "growth %i exceeds --param early-inlining-insns "
630 "divided by number of calls\n",
631 xstrdup_for_dump (e
->caller
->name ()),
633 xstrdup_for_dump (callee
->name ()), callee
->order
,
641 /* Compute time of the edge->caller + edge->callee execution when inlining
645 compute_uninlined_call_time (struct inline_summary
*callee_info
,
646 struct cgraph_edge
*edge
)
648 sreal uninlined_call_time
= (sreal
)callee_info
->time
;
649 cgraph_node
*caller
= (edge
->caller
->global
.inlined_to
650 ? edge
->caller
->global
.inlined_to
653 if (edge
->count
&& caller
->count
)
654 uninlined_call_time
*= (sreal
)edge
->count
/ caller
->count
;
656 uninlined_call_time
*= cgraph_freq_base_rec
* edge
->frequency
;
658 uninlined_call_time
= uninlined_call_time
>> 11;
660 int caller_time
= inline_summaries
->get (caller
)->time
;
661 return uninlined_call_time
+ caller_time
;
664 /* Same as compute_uinlined_call_time but compute time when inlining
668 compute_inlined_call_time (struct cgraph_edge
*edge
,
671 cgraph_node
*caller
= (edge
->caller
->global
.inlined_to
672 ? edge
->caller
->global
.inlined_to
674 int caller_time
= inline_summaries
->get (caller
)->time
;
675 sreal time
= edge_time
;
677 if (edge
->count
&& caller
->count
)
678 time
*= (sreal
)edge
->count
/ caller
->count
;
680 time
*= cgraph_freq_base_rec
* edge
->frequency
;
684 /* This calculation should match one in ipa-inline-analysis.
685 FIXME: Once ipa-inline-analysis is converted to sreal this can be
687 time
-= (sreal
) ((gcov_type
) edge
->frequency
688 * inline_edge_summary (edge
)->call_stmt_time
689 * (INLINE_TIME_SCALE
/ CGRAPH_FREQ_BASE
)) / INLINE_TIME_SCALE
;
692 time
= ((sreal
) 1) >> 8;
693 gcc_checking_assert (time
>= 0);
697 /* Return true if the speedup for inlining E is bigger than
698 PARAM_MAX_INLINE_MIN_SPEEDUP. */
701 big_speedup_p (struct cgraph_edge
*e
)
703 sreal time
= compute_uninlined_call_time (inline_summaries
->get (e
->callee
),
705 sreal inlined_time
= compute_inlined_call_time (e
, estimate_edge_time (e
));
707 if (time
- inlined_time
708 > (sreal
) time
* PARAM_VALUE (PARAM_INLINE_MIN_SPEEDUP
)
714 /* Return true if we are interested in inlining small function.
715 When REPORT is true, report reason to dump file. */
718 want_inline_small_function_p (struct cgraph_edge
*e
, bool report
)
720 bool want_inline
= true;
721 struct cgraph_node
*callee
= e
->callee
->ultimate_alias_target ();
723 if (DECL_DISREGARD_INLINE_LIMITS (callee
->decl
))
725 else if (!DECL_DECLARED_INLINE_P (callee
->decl
)
726 && !opt_for_fn (e
->caller
->decl
, flag_inline_small_functions
))
728 e
->inline_failed
= CIF_FUNCTION_NOT_INLINE_CANDIDATE
;
731 /* Do fast and conservative check if the function can be good
732 inline candidate. At the moment we allow inline hints to
733 promote non-inline functions to inline and we increase
734 MAX_INLINE_INSNS_SINGLE 16-fold for inline functions. */
735 else if ((!DECL_DECLARED_INLINE_P (callee
->decl
)
736 && (!e
->count
|| !e
->maybe_hot_p ()))
737 && inline_summaries
->get (callee
)->min_size
738 - inline_edge_summary (e
)->call_stmt_size
739 > MAX (MAX_INLINE_INSNS_SINGLE
, MAX_INLINE_INSNS_AUTO
))
741 e
->inline_failed
= CIF_MAX_INLINE_INSNS_AUTO_LIMIT
;
744 else if ((DECL_DECLARED_INLINE_P (callee
->decl
) || e
->count
)
745 && inline_summaries
->get (callee
)->min_size
746 - inline_edge_summary (e
)->call_stmt_size
747 > 16 * MAX_INLINE_INSNS_SINGLE
)
749 e
->inline_failed
= (DECL_DECLARED_INLINE_P (callee
->decl
)
750 ? CIF_MAX_INLINE_INSNS_SINGLE_LIMIT
751 : CIF_MAX_INLINE_INSNS_AUTO_LIMIT
);
756 int growth
= estimate_edge_growth (e
);
757 inline_hints hints
= estimate_edge_hints (e
);
758 bool big_speedup
= big_speedup_p (e
);
762 /* Apply MAX_INLINE_INSNS_SINGLE limit. Do not do so when
763 hints suggests that inlining given function is very profitable. */
764 else if (DECL_DECLARED_INLINE_P (callee
->decl
)
765 && growth
>= MAX_INLINE_INSNS_SINGLE
767 && !(hints
& (INLINE_HINT_indirect_call
768 | INLINE_HINT_known_hot
769 | INLINE_HINT_loop_iterations
770 | INLINE_HINT_array_index
771 | INLINE_HINT_loop_stride
)))
772 || growth
>= MAX_INLINE_INSNS_SINGLE
* 16))
774 e
->inline_failed
= CIF_MAX_INLINE_INSNS_SINGLE_LIMIT
;
777 else if (!DECL_DECLARED_INLINE_P (callee
->decl
)
778 && !opt_for_fn (e
->caller
->decl
, flag_inline_functions
))
780 /* growth_likely_positive is expensive, always test it last. */
781 if (growth
>= MAX_INLINE_INSNS_SINGLE
782 || growth_likely_positive (callee
, growth
))
784 e
->inline_failed
= CIF_NOT_DECLARED_INLINED
;
788 /* Apply MAX_INLINE_INSNS_AUTO limit for functions not declared inline
789 Upgrade it to MAX_INLINE_INSNS_SINGLE when hints suggests that
790 inlining given function is very profitable. */
791 else if (!DECL_DECLARED_INLINE_P (callee
->decl
)
793 && !(hints
& INLINE_HINT_known_hot
)
794 && growth
>= ((hints
& (INLINE_HINT_indirect_call
795 | INLINE_HINT_loop_iterations
796 | INLINE_HINT_array_index
797 | INLINE_HINT_loop_stride
))
798 ? MAX (MAX_INLINE_INSNS_AUTO
,
799 MAX_INLINE_INSNS_SINGLE
)
800 : MAX_INLINE_INSNS_AUTO
))
802 /* growth_likely_positive is expensive, always test it last. */
803 if (growth
>= MAX_INLINE_INSNS_SINGLE
804 || growth_likely_positive (callee
, growth
))
806 e
->inline_failed
= CIF_MAX_INLINE_INSNS_AUTO_LIMIT
;
810 /* If call is cold, do not inline when function body would grow. */
811 else if (!e
->maybe_hot_p ()
812 && (growth
>= MAX_INLINE_INSNS_SINGLE
813 || growth_likely_positive (callee
, growth
)))
815 e
->inline_failed
= CIF_UNLIKELY_CALL
;
819 if (!want_inline
&& report
)
820 report_inline_failed_reason (e
);
824 /* EDGE is self recursive edge.
825 We hand two cases - when function A is inlining into itself
826 or when function A is being inlined into another inliner copy of function
829 In first case OUTER_NODE points to the toplevel copy of A, while
830 in the second case OUTER_NODE points to the outermost copy of A in B.
832 In both cases we want to be extra selective since
833 inlining the call will just introduce new recursive calls to appear. */
836 want_inline_self_recursive_call_p (struct cgraph_edge
*edge
,
837 struct cgraph_node
*outer_node
,
841 char const *reason
= NULL
;
842 bool want_inline
= true;
843 int caller_freq
= CGRAPH_FREQ_BASE
;
844 int max_depth
= PARAM_VALUE (PARAM_MAX_INLINE_RECURSIVE_DEPTH_AUTO
);
846 if (DECL_DECLARED_INLINE_P (edge
->caller
->decl
))
847 max_depth
= PARAM_VALUE (PARAM_MAX_INLINE_RECURSIVE_DEPTH
);
849 if (!edge
->maybe_hot_p ())
851 reason
= "recursive call is cold";
854 else if (max_count
&& !outer_node
->count
)
856 reason
= "not executed in profile";
859 else if (depth
> max_depth
)
861 reason
= "--param max-inline-recursive-depth exceeded.";
865 if (outer_node
->global
.inlined_to
)
866 caller_freq
= outer_node
->callers
->frequency
;
870 reason
= "function is inlined and unlikely";
876 /* Inlining of self recursive function into copy of itself within other function
877 is transformation similar to loop peeling.
879 Peeling is profitable if we can inline enough copies to make probability
880 of actual call to the self recursive function very small. Be sure that
881 the probability of recursion is small.
883 We ensure that the frequency of recursing is at most 1 - (1/max_depth).
884 This way the expected number of recision is at most max_depth. */
887 int max_prob
= CGRAPH_FREQ_BASE
- ((CGRAPH_FREQ_BASE
+ max_depth
- 1)
890 for (i
= 1; i
< depth
; i
++)
891 max_prob
= max_prob
* max_prob
/ CGRAPH_FREQ_BASE
;
893 && (edge
->count
* CGRAPH_FREQ_BASE
/ outer_node
->count
896 reason
= "profile of recursive call is too large";
900 && (edge
->frequency
* CGRAPH_FREQ_BASE
/ caller_freq
903 reason
= "frequency of recursive call is too large";
907 /* Recursive inlining, i.e. equivalent of unrolling, is profitable if recursion
908 depth is large. We reduce function call overhead and increase chances that
909 things fit in hardware return predictor.
911 Recursive inlining might however increase cost of stack frame setup
912 actually slowing down functions whose recursion tree is wide rather than
915 Deciding reliably on when to do recursive inlining without profile feedback
916 is tricky. For now we disable recursive inlining when probability of self
919 Recursive inlining of self recursive call within loop also results in large loop
920 depths that generally optimize badly. We may want to throttle down inlining
921 in those cases. In particular this seems to happen in one of libstdc++ rb tree
926 && (edge
->count
* 100 / outer_node
->count
927 <= PARAM_VALUE (PARAM_MIN_INLINE_RECURSIVE_PROBABILITY
)))
929 reason
= "profile of recursive call is too small";
933 && (edge
->frequency
* 100 / caller_freq
934 <= PARAM_VALUE (PARAM_MIN_INLINE_RECURSIVE_PROBABILITY
)))
936 reason
= "frequency of recursive call is too small";
940 if (!want_inline
&& dump_file
)
941 fprintf (dump_file
, " not inlining recursively: %s\n", reason
);
945 /* Return true when NODE has uninlinable caller;
946 set HAS_HOT_CALL if it has hot call.
947 Worker for cgraph_for_node_and_aliases. */
950 check_callers (struct cgraph_node
*node
, void *has_hot_call
)
952 struct cgraph_edge
*e
;
953 for (e
= node
->callers
; e
; e
= e
->next_caller
)
955 if (!opt_for_fn (e
->caller
->decl
, flag_inline_functions_called_once
))
957 if (!can_inline_edge_p (e
, true))
959 if (e
->recursive_p ())
961 if (!(*(bool *)has_hot_call
) && e
->maybe_hot_p ())
962 *(bool *)has_hot_call
= true;
967 /* If NODE has a caller, return true. */
970 has_caller_p (struct cgraph_node
*node
, void *data ATTRIBUTE_UNUSED
)
977 /* Decide if inlining NODE would reduce unit size by eliminating
978 the offline copy of function.
979 When COLD is true the cold calls are considered, too. */
982 want_inline_function_to_all_callers_p (struct cgraph_node
*node
, bool cold
)
984 bool has_hot_call
= false;
986 /* Aliases gets inlined along with the function they alias. */
989 /* Already inlined? */
990 if (node
->global
.inlined_to
)
992 /* Does it have callers? */
993 if (!node
->call_for_symbol_and_aliases (has_caller_p
, NULL
, true))
995 /* Inlining into all callers would increase size? */
996 if (estimate_growth (node
) > 0)
998 /* All inlines must be possible. */
999 if (node
->call_for_symbol_and_aliases (check_callers
, &has_hot_call
,
1002 if (!cold
&& !has_hot_call
)
1007 /* A cost model driving the inlining heuristics in a way so the edges with
1008 smallest badness are inlined first. After each inlining is performed
1009 the costs of all caller edges of nodes affected are recomputed so the
1010 metrics may accurately depend on values such as number of inlinable callers
1011 of the function or function body size. */
1014 edge_badness (struct cgraph_edge
*edge
, bool dump
)
1017 int growth
, edge_time
;
1018 struct cgraph_node
*callee
= edge
->callee
->ultimate_alias_target ();
1019 struct inline_summary
*callee_info
= inline_summaries
->get (callee
);
1021 cgraph_node
*caller
= (edge
->caller
->global
.inlined_to
1022 ? edge
->caller
->global
.inlined_to
1025 growth
= estimate_edge_growth (edge
);
1026 edge_time
= estimate_edge_time (edge
);
1027 hints
= estimate_edge_hints (edge
);
1028 gcc_checking_assert (edge_time
>= 0);
1029 gcc_checking_assert (edge_time
<= callee_info
->time
);
1030 gcc_checking_assert (growth
<= callee_info
->size
);
1034 fprintf (dump_file
, " Badness calculation for %s/%i -> %s/%i\n",
1035 xstrdup_for_dump (edge
->caller
->name ()),
1036 edge
->caller
->order
,
1037 xstrdup_for_dump (callee
->name ()),
1038 edge
->callee
->order
);
1039 fprintf (dump_file
, " size growth %i, time %i ",
1042 dump_inline_hints (dump_file
, hints
);
1043 if (big_speedup_p (edge
))
1044 fprintf (dump_file
, " big_speedup");
1045 fprintf (dump_file
, "\n");
1048 /* Always prefer inlining saving code size. */
1051 badness
= (sreal
) (-SREAL_MIN_SIG
+ growth
) << (SREAL_MAX_EXP
/ 256);
1053 fprintf (dump_file
, " %f: Growth %d <= 0\n", badness
.to_double (),
1056 /* Inlining into EXTERNAL functions is not going to change anything unless
1057 they are themselves inlined. */
1058 else if (DECL_EXTERNAL (caller
->decl
))
1061 fprintf (dump_file
, " max: function is external\n");
1062 return sreal::max ();
1064 /* When profile is available. Compute badness as:
1066 time_saved * caller_count
1067 goodness = -------------------------------------------------
1068 growth_of_caller * overall_growth * combined_size
1070 badness = - goodness
1072 Again use negative value to make calls with profile appear hotter
1075 else if (opt_for_fn (caller
->decl
, flag_guess_branch_prob
) || caller
->count
)
1077 sreal numerator
, denominator
;
1080 numerator
= (compute_uninlined_call_time (callee_info
, edge
)
1081 - compute_inlined_call_time (edge
, edge_time
));
1083 numerator
= ((sreal
) 1 >> 8);
1085 numerator
*= caller
->count
;
1086 else if (opt_for_fn (caller
->decl
, flag_branch_probabilities
))
1087 numerator
= numerator
>> 11;
1088 denominator
= growth
;
1090 overall_growth
= callee_info
->growth
;
1092 /* Look for inliner wrappers of the form:
1098 noninline_callee ();
1100 Withhout panilizing this case, we usually inline noninline_callee
1101 into the inline_caller because overall_growth is small preventing
1102 further inlining of inline_caller.
1104 Penalize only callgraph edges to functions with small overall
1107 if (growth
> overall_growth
1108 /* ... and having only one caller which is not inlined ... */
1109 && callee_info
->single_caller
1110 && !edge
->caller
->global
.inlined_to
1111 /* ... and edges executed only conditionally ... */
1112 && edge
->frequency
< CGRAPH_FREQ_BASE
1113 /* ... consider case where callee is not inline but caller is ... */
1114 && ((!DECL_DECLARED_INLINE_P (edge
->callee
->decl
)
1115 && DECL_DECLARED_INLINE_P (caller
->decl
))
1116 /* ... or when early optimizers decided to split and edge
1117 frequency still indicates splitting is a win ... */
1118 || (callee
->split_part
&& !caller
->split_part
1122 (PARAM_PARTIAL_INLINING_ENTRY_PROBABILITY
) / 100
1123 /* ... and do not overwrite user specified hints. */
1124 && (!DECL_DECLARED_INLINE_P (edge
->callee
->decl
)
1125 || DECL_DECLARED_INLINE_P (caller
->decl
)))))
1127 struct inline_summary
*caller_info
= inline_summaries
->get (caller
);
1128 int caller_growth
= caller_info
->growth
;
1130 /* Only apply the penalty when caller looks like inline candidate,
1131 and it is not called once and. */
1132 if (!caller_info
->single_caller
&& overall_growth
< caller_growth
1133 && caller_info
->inlinable
1134 && caller_info
->size
1135 < (DECL_DECLARED_INLINE_P (caller
->decl
)
1136 ? MAX_INLINE_INSNS_SINGLE
: MAX_INLINE_INSNS_AUTO
))
1140 " Wrapper penalty. Increasing growth %i to %i\n",
1141 overall_growth
, caller_growth
);
1142 overall_growth
= caller_growth
;
1145 if (overall_growth
> 0)
1147 /* Strongly preffer functions with few callers that can be inlined
1148 fully. The square root here leads to smaller binaries at average.
1149 Watch however for extreme cases and return to linear function
1150 when growth is large. */
1151 if (overall_growth
< 256)
1152 overall_growth
*= overall_growth
;
1154 overall_growth
+= 256 * 256 - 256;
1155 denominator
*= overall_growth
;
1157 denominator
*= inline_summaries
->get (caller
)->self_size
+ growth
;
1159 badness
= - numerator
/ denominator
;
1164 " %f: guessed profile. frequency %f, count %" PRId64
1165 " caller count %" PRId64
1166 " time w/o inlining %f, time w/ inlining %f"
1167 " overall growth %i (current) %i (original)"
1168 " %i (compensated)\n",
1169 badness
.to_double (),
1170 (double)edge
->frequency
/ CGRAPH_FREQ_BASE
,
1171 edge
->count
, caller
->count
,
1172 compute_uninlined_call_time (callee_info
, edge
).to_double (),
1173 compute_inlined_call_time (edge
, edge_time
).to_double (),
1174 estimate_growth (callee
),
1175 callee_info
->growth
, overall_growth
);
1178 /* When function local profile is not available or it does not give
1179 useful information (ie frequency is zero), base the cost on
1180 loop nest and overall size growth, so we optimize for overall number
1181 of functions fully inlined in program. */
1184 int nest
= MIN (inline_edge_summary (edge
)->loop_depth
, 8);
1187 /* Decrease badness if call is nested. */
1189 badness
= badness
>> nest
;
1191 badness
= badness
<< nest
;
1193 fprintf (dump_file
, " %f: no profile. nest %i\n",
1194 badness
.to_double (), nest
);
1196 gcc_checking_assert (badness
!= 0);
1198 if (edge
->recursive_p ())
1199 badness
= badness
.shift (badness
> 0 ? 4 : -4);
1200 if ((hints
& (INLINE_HINT_indirect_call
1201 | INLINE_HINT_loop_iterations
1202 | INLINE_HINT_array_index
1203 | INLINE_HINT_loop_stride
))
1204 || callee_info
->growth
<= 0)
1205 badness
= badness
.shift (badness
> 0 ? -2 : 2);
1206 if (hints
& (INLINE_HINT_same_scc
))
1207 badness
= badness
.shift (badness
> 0 ? 3 : -3);
1208 else if (hints
& (INLINE_HINT_in_scc
))
1209 badness
= badness
.shift (badness
> 0 ? 2 : -2);
1210 else if (hints
& (INLINE_HINT_cross_module
))
1211 badness
= badness
.shift (badness
> 0 ? 1 : -1);
1212 if (DECL_DISREGARD_INLINE_LIMITS (callee
->decl
))
1213 badness
= badness
.shift (badness
> 0 ? -4 : 4);
1214 else if ((hints
& INLINE_HINT_declared_inline
))
1215 badness
= badness
.shift (badness
> 0 ? -3 : 3);
1217 fprintf (dump_file
, " Adjusted by hints %f\n", badness
.to_double ());
1221 /* Recompute badness of EDGE and update its key in HEAP if needed. */
1223 update_edge_key (edge_heap_t
*heap
, struct cgraph_edge
*edge
)
1225 sreal badness
= edge_badness (edge
, false);
1228 edge_heap_node_t
*n
= (edge_heap_node_t
*) edge
->aux
;
1229 gcc_checking_assert (n
->get_data () == edge
);
1231 /* fibonacci_heap::replace_key does busy updating of the
1232 heap that is unnecesarily expensive.
1233 We do lazy increases: after extracting minimum if the key
1234 turns out to be out of date, it is re-inserted into heap
1235 with correct value. */
1236 if (badness
< n
->get_key ())
1238 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1241 " decreasing badness %s/%i -> %s/%i, %f"
1243 xstrdup_for_dump (edge
->caller
->name ()),
1244 edge
->caller
->order
,
1245 xstrdup_for_dump (edge
->callee
->name ()),
1246 edge
->callee
->order
,
1247 n
->get_key ().to_double (),
1248 badness
.to_double ());
1250 heap
->decrease_key (n
, badness
);
1255 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1258 " enqueuing call %s/%i -> %s/%i, badness %f\n",
1259 xstrdup_for_dump (edge
->caller
->name ()),
1260 edge
->caller
->order
,
1261 xstrdup_for_dump (edge
->callee
->name ()),
1262 edge
->callee
->order
,
1263 badness
.to_double ());
1265 edge
->aux
= heap
->insert (badness
, edge
);
1270 /* NODE was inlined.
1271 All caller edges needs to be resetted because
1272 size estimates change. Similarly callees needs reset
1273 because better context may be known. */
1276 reset_edge_caches (struct cgraph_node
*node
)
1278 struct cgraph_edge
*edge
;
1279 struct cgraph_edge
*e
= node
->callees
;
1280 struct cgraph_node
*where
= node
;
1281 struct ipa_ref
*ref
;
1283 if (where
->global
.inlined_to
)
1284 where
= where
->global
.inlined_to
;
1286 for (edge
= where
->callers
; edge
; edge
= edge
->next_caller
)
1287 if (edge
->inline_failed
)
1288 reset_edge_growth_cache (edge
);
1290 FOR_EACH_ALIAS (where
, ref
)
1291 reset_edge_caches (dyn_cast
<cgraph_node
*> (ref
->referring
));
1297 if (!e
->inline_failed
&& e
->callee
->callees
)
1298 e
= e
->callee
->callees
;
1301 if (e
->inline_failed
)
1302 reset_edge_growth_cache (e
);
1309 if (e
->caller
== node
)
1311 e
= e
->caller
->callers
;
1313 while (!e
->next_callee
);
1319 /* Recompute HEAP nodes for each of caller of NODE.
1320 UPDATED_NODES track nodes we already visited, to avoid redundant work.
1321 When CHECK_INLINABLITY_FOR is set, re-check for specified edge that
1322 it is inlinable. Otherwise check all edges. */
1325 update_caller_keys (edge_heap_t
*heap
, struct cgraph_node
*node
,
1326 bitmap updated_nodes
,
1327 struct cgraph_edge
*check_inlinablity_for
)
1329 struct cgraph_edge
*edge
;
1330 struct ipa_ref
*ref
;
1332 if ((!node
->alias
&& !inline_summaries
->get (node
)->inlinable
)
1333 || node
->global
.inlined_to
)
1335 if (!bitmap_set_bit (updated_nodes
, node
->uid
))
1338 FOR_EACH_ALIAS (node
, ref
)
1340 struct cgraph_node
*alias
= dyn_cast
<cgraph_node
*> (ref
->referring
);
1341 update_caller_keys (heap
, alias
, updated_nodes
, check_inlinablity_for
);
1344 for (edge
= node
->callers
; edge
; edge
= edge
->next_caller
)
1345 if (edge
->inline_failed
)
1347 if (!check_inlinablity_for
1348 || check_inlinablity_for
== edge
)
1350 if (can_inline_edge_p (edge
, false)
1351 && want_inline_small_function_p (edge
, false))
1352 update_edge_key (heap
, edge
);
1355 report_inline_failed_reason (edge
);
1356 heap
->delete_node ((edge_heap_node_t
*) edge
->aux
);
1361 update_edge_key (heap
, edge
);
1365 /* Recompute HEAP nodes for each uninlined call in NODE.
1366 This is used when we know that edge badnesses are going only to increase
1367 (we introduced new call site) and thus all we need is to insert newly
1368 created edges into heap. */
1371 update_callee_keys (edge_heap_t
*heap
, struct cgraph_node
*node
,
1372 bitmap updated_nodes
)
1374 struct cgraph_edge
*e
= node
->callees
;
1379 if (!e
->inline_failed
&& e
->callee
->callees
)
1380 e
= e
->callee
->callees
;
1383 enum availability avail
;
1384 struct cgraph_node
*callee
;
1385 /* We do not reset callee growth cache here. Since we added a new call,
1386 growth chould have just increased and consequentely badness metric
1387 don't need updating. */
1388 if (e
->inline_failed
1389 && (callee
= e
->callee
->ultimate_alias_target (&avail
, e
->caller
))
1390 && inline_summaries
->get (callee
)->inlinable
1391 && avail
>= AVAIL_AVAILABLE
1392 && !bitmap_bit_p (updated_nodes
, callee
->uid
))
1394 if (can_inline_edge_p (e
, false)
1395 && want_inline_small_function_p (e
, false))
1396 update_edge_key (heap
, e
);
1399 report_inline_failed_reason (e
);
1400 heap
->delete_node ((edge_heap_node_t
*) e
->aux
);
1410 if (e
->caller
== node
)
1412 e
= e
->caller
->callers
;
1414 while (!e
->next_callee
);
1420 /* Enqueue all recursive calls from NODE into priority queue depending on
1421 how likely we want to recursively inline the call. */
1424 lookup_recursive_calls (struct cgraph_node
*node
, struct cgraph_node
*where
,
1427 struct cgraph_edge
*e
;
1428 enum availability avail
;
1430 for (e
= where
->callees
; e
; e
= e
->next_callee
)
1431 if (e
->callee
== node
1432 || (e
->callee
->ultimate_alias_target (&avail
, e
->caller
) == node
1433 && avail
> AVAIL_INTERPOSABLE
))
1435 /* When profile feedback is available, prioritize by expected number
1437 heap
->insert (!max_count
? -e
->frequency
1438 : -(e
->count
/ ((max_count
+ (1<<24) - 1) / (1<<24))),
1441 for (e
= where
->callees
; e
; e
= e
->next_callee
)
1442 if (!e
->inline_failed
)
1443 lookup_recursive_calls (node
, e
->callee
, heap
);
1446 /* Decide on recursive inlining: in the case function has recursive calls,
1447 inline until body size reaches given argument. If any new indirect edges
1448 are discovered in the process, add them to *NEW_EDGES, unless NEW_EDGES
1452 recursive_inlining (struct cgraph_edge
*edge
,
1453 vec
<cgraph_edge
*> *new_edges
)
1455 int limit
= PARAM_VALUE (PARAM_MAX_INLINE_INSNS_RECURSIVE_AUTO
);
1456 edge_heap_t
heap (sreal::min ());
1457 struct cgraph_node
*node
;
1458 struct cgraph_edge
*e
;
1459 struct cgraph_node
*master_clone
= NULL
, *next
;
1463 node
= edge
->caller
;
1464 if (node
->global
.inlined_to
)
1465 node
= node
->global
.inlined_to
;
1467 if (DECL_DECLARED_INLINE_P (node
->decl
))
1468 limit
= PARAM_VALUE (PARAM_MAX_INLINE_INSNS_RECURSIVE
);
1470 /* Make sure that function is small enough to be considered for inlining. */
1471 if (estimate_size_after_inlining (node
, edge
) >= limit
)
1473 lookup_recursive_calls (node
, node
, &heap
);
1479 " Performing recursive inlining on %s\n",
1482 /* Do the inlining and update list of recursive call during process. */
1483 while (!heap
.empty ())
1485 struct cgraph_edge
*curr
= heap
.extract_min ();
1486 struct cgraph_node
*cnode
, *dest
= curr
->callee
;
1488 if (!can_inline_edge_p (curr
, true))
1491 /* MASTER_CLONE is produced in the case we already started modified
1492 the function. Be sure to redirect edge to the original body before
1493 estimating growths otherwise we will be seeing growths after inlining
1494 the already modified body. */
1497 curr
->redirect_callee (master_clone
);
1498 reset_edge_growth_cache (curr
);
1501 if (estimate_size_after_inlining (node
, curr
) > limit
)
1503 curr
->redirect_callee (dest
);
1504 reset_edge_growth_cache (curr
);
1509 for (cnode
= curr
->caller
;
1510 cnode
->global
.inlined_to
; cnode
= cnode
->callers
->caller
)
1512 == curr
->callee
->ultimate_alias_target ()->decl
)
1515 if (!want_inline_self_recursive_call_p (curr
, node
, false, depth
))
1517 curr
->redirect_callee (dest
);
1518 reset_edge_growth_cache (curr
);
1525 " Inlining call of depth %i", depth
);
1528 fprintf (dump_file
, " called approx. %.2f times per call",
1529 (double)curr
->count
/ node
->count
);
1531 fprintf (dump_file
, "\n");
1535 /* We need original clone to copy around. */
1536 master_clone
= node
->create_clone (node
->decl
, node
->count
,
1537 CGRAPH_FREQ_BASE
, false, vNULL
,
1539 for (e
= master_clone
->callees
; e
; e
= e
->next_callee
)
1540 if (!e
->inline_failed
)
1541 clone_inlined_nodes (e
, true, false, NULL
, CGRAPH_FREQ_BASE
);
1542 curr
->redirect_callee (master_clone
);
1543 reset_edge_growth_cache (curr
);
1546 inline_call (curr
, false, new_edges
, &overall_size
, true);
1547 lookup_recursive_calls (node
, curr
->callee
, &heap
);
1551 if (!heap
.empty () && dump_file
)
1552 fprintf (dump_file
, " Recursive inlining growth limit met.\n");
1559 "\n Inlined %i times, "
1560 "body grown from size %i to %i, time %i to %i\n", n
,
1561 inline_summaries
->get (master_clone
)->size
, inline_summaries
->get (node
)->size
,
1562 inline_summaries
->get (master_clone
)->time
, inline_summaries
->get (node
)->time
);
1564 /* Remove master clone we used for inlining. We rely that clones inlined
1565 into master clone gets queued just before master clone so we don't
1567 for (node
= symtab
->first_function (); node
!= master_clone
;
1570 next
= symtab
->next_function (node
);
1571 if (node
->global
.inlined_to
== master_clone
)
1574 master_clone
->remove ();
1579 /* Given whole compilation unit estimate of INSNS, compute how large we can
1580 allow the unit to grow. */
1583 compute_max_insns (int insns
)
1585 int max_insns
= insns
;
1586 if (max_insns
< PARAM_VALUE (PARAM_LARGE_UNIT_INSNS
))
1587 max_insns
= PARAM_VALUE (PARAM_LARGE_UNIT_INSNS
);
1589 return ((int64_t) max_insns
1590 * (100 + PARAM_VALUE (PARAM_INLINE_UNIT_GROWTH
)) / 100);
1594 /* Compute badness of all edges in NEW_EDGES and add them to the HEAP. */
1597 add_new_edges_to_heap (edge_heap_t
*heap
, vec
<cgraph_edge
*> new_edges
)
1599 while (new_edges
.length () > 0)
1601 struct cgraph_edge
*edge
= new_edges
.pop ();
1603 gcc_assert (!edge
->aux
);
1604 if (edge
->inline_failed
1605 && can_inline_edge_p (edge
, true)
1606 && want_inline_small_function_p (edge
, true))
1607 edge
->aux
= heap
->insert (edge_badness (edge
, false), edge
);
1611 /* Remove EDGE from the fibheap. */
1614 heap_edge_removal_hook (struct cgraph_edge
*e
, void *data
)
1618 ((edge_heap_t
*)data
)->delete_node ((edge_heap_node_t
*)e
->aux
);
1623 /* Return true if speculation of edge E seems useful.
1624 If ANTICIPATE_INLINING is true, be conservative and hope that E
1628 speculation_useful_p (struct cgraph_edge
*e
, bool anticipate_inlining
)
1630 enum availability avail
;
1631 struct cgraph_node
*target
= e
->callee
->ultimate_alias_target (&avail
,
1633 struct cgraph_edge
*direct
, *indirect
;
1634 struct ipa_ref
*ref
;
1636 gcc_assert (e
->speculative
&& !e
->indirect_unknown_callee
);
1638 if (!e
->maybe_hot_p ())
1641 /* See if IP optimizations found something potentially useful about the
1642 function. For now we look only for CONST/PURE flags. Almost everything
1643 else we propagate is useless. */
1644 if (avail
>= AVAIL_AVAILABLE
)
1646 int ecf_flags
= flags_from_decl_or_type (target
->decl
);
1647 if (ecf_flags
& ECF_CONST
)
1649 e
->speculative_call_info (direct
, indirect
, ref
);
1650 if (!(indirect
->indirect_info
->ecf_flags
& ECF_CONST
))
1653 else if (ecf_flags
& ECF_PURE
)
1655 e
->speculative_call_info (direct
, indirect
, ref
);
1656 if (!(indirect
->indirect_info
->ecf_flags
& ECF_PURE
))
1660 /* If we did not managed to inline the function nor redirect
1661 to an ipa-cp clone (that are seen by having local flag set),
1662 it is probably pointless to inline it unless hardware is missing
1663 indirect call predictor. */
1664 if (!anticipate_inlining
&& e
->inline_failed
&& !target
->local
.local
)
1666 /* For overwritable targets there is not much to do. */
1667 if (e
->inline_failed
&& !can_inline_edge_p (e
, false, true))
1669 /* OK, speculation seems interesting. */
1673 /* We know that EDGE is not going to be inlined.
1674 See if we can remove speculation. */
1677 resolve_noninline_speculation (edge_heap_t
*edge_heap
, struct cgraph_edge
*edge
)
1679 if (edge
->speculative
&& !speculation_useful_p (edge
, false))
1681 struct cgraph_node
*node
= edge
->caller
;
1682 struct cgraph_node
*where
= node
->global
.inlined_to
1683 ? node
->global
.inlined_to
: node
;
1684 bitmap updated_nodes
= BITMAP_ALLOC (NULL
);
1686 spec_rem
+= edge
->count
;
1687 edge
->resolve_speculation ();
1688 reset_edge_caches (where
);
1689 inline_update_overall_summary (where
);
1690 update_caller_keys (edge_heap
, where
,
1691 updated_nodes
, NULL
);
1692 update_callee_keys (edge_heap
, where
,
1694 BITMAP_FREE (updated_nodes
);
1698 /* Return true if NODE should be accounted for overall size estimate.
1699 Skip all nodes optimized for size so we can measure the growth of hot
1700 part of program no matter of the padding. */
1703 inline_account_function_p (struct cgraph_node
*node
)
1705 return (!DECL_EXTERNAL (node
->decl
)
1706 && !opt_for_fn (node
->decl
, optimize_size
)
1707 && node
->frequency
!= NODE_FREQUENCY_UNLIKELY_EXECUTED
);
1710 /* Count number of callers of NODE and store it into DATA (that
1711 points to int. Worker for cgraph_for_node_and_aliases. */
1714 sum_callers (struct cgraph_node
*node
, void *data
)
1716 struct cgraph_edge
*e
;
1717 int *num_calls
= (int *)data
;
1719 for (e
= node
->callers
; e
; e
= e
->next_caller
)
1724 /* We use greedy algorithm for inlining of small functions:
1725 All inline candidates are put into prioritized heap ordered in
1728 The inlining of small functions is bounded by unit growth parameters. */
1731 inline_small_functions (void)
1733 struct cgraph_node
*node
;
1734 struct cgraph_edge
*edge
;
1735 edge_heap_t
edge_heap (sreal::min ());
1736 bitmap updated_nodes
= BITMAP_ALLOC (NULL
);
1737 int min_size
, max_size
;
1738 auto_vec
<cgraph_edge
*> new_indirect_edges
;
1739 int initial_size
= 0;
1740 struct cgraph_node
**order
= XCNEWVEC (cgraph_node
*, symtab
->cgraph_count
);
1741 struct cgraph_edge_hook_list
*edge_removal_hook_holder
;
1742 new_indirect_edges
.create (8);
1744 edge_removal_hook_holder
1745 = symtab
->add_edge_removal_hook (&heap_edge_removal_hook
, &edge_heap
);
1747 /* Compute overall unit size and other global parameters used by badness
1751 ipa_reduced_postorder (order
, true, true, NULL
);
1754 FOR_EACH_DEFINED_FUNCTION (node
)
1755 if (!node
->global
.inlined_to
)
1757 if (!node
->alias
&& node
->analyzed
1758 && (node
->has_gimple_body_p () || node
->thunk
.thunk_p
))
1760 struct inline_summary
*info
= inline_summaries
->get (node
);
1761 struct ipa_dfs_info
*dfs
= (struct ipa_dfs_info
*) node
->aux
;
1763 /* Do not account external functions, they will be optimized out
1764 if not inlined. Also only count the non-cold portion of program. */
1765 if (inline_account_function_p (node
))
1766 initial_size
+= info
->size
;
1767 info
->growth
= estimate_growth (node
);
1770 node
->call_for_symbol_and_aliases (sum_callers
, &num_calls
,
1773 info
->single_caller
= true;
1774 if (dfs
&& dfs
->next_cycle
)
1776 struct cgraph_node
*n2
;
1777 int id
= dfs
->scc_no
+ 1;
1779 n2
= ((struct ipa_dfs_info
*) node
->aux
)->next_cycle
)
1781 struct inline_summary
*info2
= inline_summaries
->get (n2
);
1789 for (edge
= node
->callers
; edge
; edge
= edge
->next_caller
)
1790 if (max_count
< edge
->count
)
1791 max_count
= edge
->count
;
1793 ipa_free_postorder_info ();
1794 initialize_growth_caches ();
1798 "\nDeciding on inlining of small functions. Starting with size %i.\n",
1801 overall_size
= initial_size
;
1802 max_size
= compute_max_insns (overall_size
);
1803 min_size
= overall_size
;
1805 /* Populate the heap with all edges we might inline. */
1807 FOR_EACH_DEFINED_FUNCTION (node
)
1809 bool update
= false;
1810 struct cgraph_edge
*next
= NULL
;
1811 bool has_speculative
= false;
1814 fprintf (dump_file
, "Enqueueing calls in %s/%i.\n",
1815 node
->name (), node
->order
);
1817 for (edge
= node
->callees
; edge
; edge
= next
)
1819 next
= edge
->next_callee
;
1820 if (edge
->inline_failed
1822 && can_inline_edge_p (edge
, true)
1823 && want_inline_small_function_p (edge
, true)
1824 && edge
->inline_failed
)
1826 gcc_assert (!edge
->aux
);
1827 update_edge_key (&edge_heap
, edge
);
1829 if (edge
->speculative
)
1830 has_speculative
= true;
1832 if (has_speculative
)
1833 for (edge
= node
->callees
; edge
; edge
= next
)
1834 if (edge
->speculative
&& !speculation_useful_p (edge
,
1837 edge
->resolve_speculation ();
1842 struct cgraph_node
*where
= node
->global
.inlined_to
1843 ? node
->global
.inlined_to
: node
;
1844 inline_update_overall_summary (where
);
1845 reset_edge_caches (where
);
1846 update_caller_keys (&edge_heap
, where
,
1847 updated_nodes
, NULL
);
1848 update_callee_keys (&edge_heap
, where
,
1850 bitmap_clear (updated_nodes
);
1854 gcc_assert (in_lto_p
1856 || (profile_info
&& flag_branch_probabilities
));
1858 while (!edge_heap
.empty ())
1860 int old_size
= overall_size
;
1861 struct cgraph_node
*where
, *callee
;
1862 sreal badness
= edge_heap
.min_key ();
1863 sreal current_badness
;
1866 edge
= edge_heap
.extract_min ();
1867 gcc_assert (edge
->aux
);
1869 if (!edge
->inline_failed
|| !edge
->callee
->analyzed
)
1873 /* Be sure that caches are maintained consistent. */
1874 sreal cached_badness
= edge_badness (edge
, false);
1876 int old_size_est
= estimate_edge_size (edge
);
1877 int old_time_est
= estimate_edge_time (edge
);
1878 int old_hints_est
= estimate_edge_hints (edge
);
1880 reset_edge_growth_cache (edge
);
1881 gcc_assert (old_size_est
== estimate_edge_size (edge
));
1882 gcc_assert (old_time_est
== estimate_edge_time (edge
));
1885 gcc_assert (old_hints_est == estimate_edge_hints (edge));
1887 fails with profile feedback because some hints depends on
1888 maybe_hot_edge_p predicate and because callee gets inlined to other
1889 calls, the edge may become cold.
1890 This ought to be fixed by computing relative probabilities
1891 for given invocation but that will be better done once whole
1892 code is converted to sreals. Disable for now and revert to "wrong"
1893 value so enable/disable checking paths agree. */
1894 edge_growth_cache
[edge
->uid
].hints
= old_hints_est
+ 1;
1896 /* When updating the edge costs, we only decrease badness in the keys.
1897 Increases of badness are handled lazilly; when we see key with out
1898 of date value on it, we re-insert it now. */
1899 current_badness
= edge_badness (edge
, false);
1900 /* Disable checking for profile because roundoff errors may cause slight
1901 deviations in the order. */
1902 gcc_assert (max_count
|| cached_badness
== current_badness
);
1903 gcc_assert (current_badness
>= badness
);
1905 current_badness
= edge_badness (edge
, false);
1907 if (current_badness
!= badness
)
1909 if (edge_heap
.min () && current_badness
> edge_heap
.min_key ())
1911 edge
->aux
= edge_heap
.insert (current_badness
, edge
);
1915 badness
= current_badness
;
1918 if (!can_inline_edge_p (edge
, true))
1920 resolve_noninline_speculation (&edge_heap
, edge
);
1924 callee
= edge
->callee
->ultimate_alias_target ();
1925 growth
= estimate_edge_growth (edge
);
1929 "\nConsidering %s/%i with %i size\n",
1930 callee
->name (), callee
->order
,
1931 inline_summaries
->get (callee
)->size
);
1933 " to be inlined into %s/%i in %s:%i\n"
1934 " Estimated badness is %f, frequency %.2f.\n",
1935 edge
->caller
->name (), edge
->caller
->order
,
1937 && (LOCATION_LOCUS (gimple_location ((const gimple
*)
1939 > BUILTINS_LOCATION
)
1940 ? gimple_filename ((const gimple
*) edge
->call_stmt
)
1943 ? gimple_lineno ((const gimple
*) edge
->call_stmt
)
1945 badness
.to_double (),
1946 edge
->frequency
/ (double)CGRAPH_FREQ_BASE
);
1948 fprintf (dump_file
," Called %" PRId64
"x\n",
1950 if (dump_flags
& TDF_DETAILS
)
1951 edge_badness (edge
, true);
1954 if (overall_size
+ growth
> max_size
1955 && !DECL_DISREGARD_INLINE_LIMITS (callee
->decl
))
1957 edge
->inline_failed
= CIF_INLINE_UNIT_GROWTH_LIMIT
;
1958 report_inline_failed_reason (edge
);
1959 resolve_noninline_speculation (&edge_heap
, edge
);
1963 if (!want_inline_small_function_p (edge
, true))
1965 resolve_noninline_speculation (&edge_heap
, edge
);
1969 /* Heuristics for inlining small functions work poorly for
1970 recursive calls where we do effects similar to loop unrolling.
1971 When inlining such edge seems profitable, leave decision on
1972 specific inliner. */
1973 if (edge
->recursive_p ())
1975 where
= edge
->caller
;
1976 if (where
->global
.inlined_to
)
1977 where
= where
->global
.inlined_to
;
1978 if (!recursive_inlining (edge
,
1979 opt_for_fn (edge
->caller
->decl
,
1980 flag_indirect_inlining
)
1981 ? &new_indirect_edges
: NULL
))
1983 edge
->inline_failed
= CIF_RECURSIVE_INLINING
;
1984 resolve_noninline_speculation (&edge_heap
, edge
);
1987 reset_edge_caches (where
);
1988 /* Recursive inliner inlines all recursive calls of the function
1989 at once. Consequently we need to update all callee keys. */
1990 if (opt_for_fn (edge
->caller
->decl
, flag_indirect_inlining
))
1991 add_new_edges_to_heap (&edge_heap
, new_indirect_edges
);
1992 update_callee_keys (&edge_heap
, where
, updated_nodes
);
1993 bitmap_clear (updated_nodes
);
1997 struct cgraph_node
*outer_node
= NULL
;
2000 /* Consider the case where self recursive function A is inlined
2001 into B. This is desired optimization in some cases, since it
2002 leads to effect similar of loop peeling and we might completely
2003 optimize out the recursive call. However we must be extra
2006 where
= edge
->caller
;
2007 while (where
->global
.inlined_to
)
2009 if (where
->decl
== callee
->decl
)
2010 outer_node
= where
, depth
++;
2011 where
= where
->callers
->caller
;
2014 && !want_inline_self_recursive_call_p (edge
, outer_node
,
2018 = (DECL_DISREGARD_INLINE_LIMITS (edge
->callee
->decl
)
2019 ? CIF_RECURSIVE_INLINING
: CIF_UNSPECIFIED
);
2020 resolve_noninline_speculation (&edge_heap
, edge
);
2023 else if (depth
&& dump_file
)
2024 fprintf (dump_file
, " Peeling recursion with depth %i\n", depth
);
2026 gcc_checking_assert (!callee
->global
.inlined_to
);
2027 inline_call (edge
, true, &new_indirect_edges
, &overall_size
, true);
2028 add_new_edges_to_heap (&edge_heap
, new_indirect_edges
);
2030 reset_edge_caches (edge
->callee
);
2032 update_callee_keys (&edge_heap
, where
, updated_nodes
);
2034 where
= edge
->caller
;
2035 if (where
->global
.inlined_to
)
2036 where
= where
->global
.inlined_to
;
2038 /* Our profitability metric can depend on local properties
2039 such as number of inlinable calls and size of the function body.
2040 After inlining these properties might change for the function we
2041 inlined into (since it's body size changed) and for the functions
2042 called by function we inlined (since number of it inlinable callers
2044 update_caller_keys (&edge_heap
, where
, updated_nodes
, NULL
);
2045 /* Offline copy count has possibly changed, recompute if profile is
2049 struct cgraph_node
*n
= cgraph_node::get (edge
->callee
->decl
);
2050 if (n
!= edge
->callee
&& n
->analyzed
)
2051 update_callee_keys (&edge_heap
, n
, updated_nodes
);
2053 bitmap_clear (updated_nodes
);
2058 " Inlined into %s which now has time %i and size %i,"
2059 "net change of %+i.\n",
2060 edge
->caller
->name (),
2061 inline_summaries
->get (edge
->caller
)->time
,
2062 inline_summaries
->get (edge
->caller
)->size
,
2063 overall_size
- old_size
);
2065 if (min_size
> overall_size
)
2067 min_size
= overall_size
;
2068 max_size
= compute_max_insns (min_size
);
2071 fprintf (dump_file
, "New minimal size reached: %i\n", min_size
);
2075 free_growth_caches ();
2078 "Unit growth for small function inlining: %i->%i (%i%%)\n",
2079 initial_size
, overall_size
,
2080 initial_size
? overall_size
* 100 / (initial_size
) - 100: 0);
2081 BITMAP_FREE (updated_nodes
);
2082 symtab
->remove_edge_removal_hook (edge_removal_hook_holder
);
2085 /* Flatten NODE. Performed both during early inlining and
2086 at IPA inlining time. */
2089 flatten_function (struct cgraph_node
*node
, bool early
)
2091 struct cgraph_edge
*e
;
2093 /* We shouldn't be called recursively when we are being processed. */
2094 gcc_assert (node
->aux
== NULL
);
2096 node
->aux
= (void *) node
;
2098 for (e
= node
->callees
; e
; e
= e
->next_callee
)
2100 struct cgraph_node
*orig_callee
;
2101 struct cgraph_node
*callee
= e
->callee
->ultimate_alias_target ();
2103 /* We've hit cycle? It is time to give up. */
2108 "Not inlining %s into %s to avoid cycle.\n",
2109 xstrdup_for_dump (callee
->name ()),
2110 xstrdup_for_dump (e
->caller
->name ()));
2111 e
->inline_failed
= CIF_RECURSIVE_INLINING
;
2115 /* When the edge is already inlined, we just need to recurse into
2116 it in order to fully flatten the leaves. */
2117 if (!e
->inline_failed
)
2119 flatten_function (callee
, early
);
2123 /* Flatten attribute needs to be processed during late inlining. For
2124 extra code quality we however do flattening during early optimization,
2127 ? !can_inline_edge_p (e
, true)
2128 : !can_early_inline_edge_p (e
))
2131 if (e
->recursive_p ())
2134 fprintf (dump_file
, "Not inlining: recursive call.\n");
2138 if (gimple_in_ssa_p (DECL_STRUCT_FUNCTION (node
->decl
))
2139 != gimple_in_ssa_p (DECL_STRUCT_FUNCTION (callee
->decl
)))
2142 fprintf (dump_file
, "Not inlining: SSA form does not match.\n");
2146 /* Inline the edge and flatten the inline clone. Avoid
2147 recursing through the original node if the node was cloned. */
2149 fprintf (dump_file
, " Inlining %s into %s.\n",
2150 xstrdup_for_dump (callee
->name ()),
2151 xstrdup_for_dump (e
->caller
->name ()));
2152 orig_callee
= callee
;
2153 inline_call (e
, true, NULL
, NULL
, false);
2154 if (e
->callee
!= orig_callee
)
2155 orig_callee
->aux
= (void *) node
;
2156 flatten_function (e
->callee
, early
);
2157 if (e
->callee
!= orig_callee
)
2158 orig_callee
->aux
= NULL
;
2162 if (!node
->global
.inlined_to
)
2163 inline_update_overall_summary (node
);
2166 /* Inline NODE to all callers. Worker for cgraph_for_node_and_aliases.
2167 DATA points to number of calls originally found so we avoid infinite
2171 inline_to_all_callers_1 (struct cgraph_node
*node
, void *data
,
2172 hash_set
<cgraph_node
*> *callers
)
2174 int *num_calls
= (int *)data
;
2175 bool callee_removed
= false;
2177 while (node
->callers
&& !node
->global
.inlined_to
)
2179 struct cgraph_node
*caller
= node
->callers
->caller
;
2181 if (!can_inline_edge_p (node
->callers
, true)
2182 || node
->callers
->recursive_p ())
2185 fprintf (dump_file
, "Uninlinable call found; giving up.\n");
2193 "\nInlining %s size %i.\n",
2195 inline_summaries
->get (node
)->size
);
2197 " Called once from %s %i insns.\n",
2198 node
->callers
->caller
->name (),
2199 inline_summaries
->get (node
->callers
->caller
)->size
);
2202 /* Remember which callers we inlined to, delaying updating the
2204 callers
->add (node
->callers
->caller
);
2205 inline_call (node
->callers
, true, NULL
, NULL
, false, &callee_removed
);
2208 " Inlined into %s which now has %i size\n",
2210 inline_summaries
->get (caller
)->size
);
2211 if (!(*num_calls
)--)
2214 fprintf (dump_file
, "New calls found; giving up.\n");
2215 return callee_removed
;
2223 /* Wrapper around inline_to_all_callers_1 doing delayed overall summary
2227 inline_to_all_callers (struct cgraph_node
*node
, void *data
)
2229 hash_set
<cgraph_node
*> callers
;
2230 bool res
= inline_to_all_callers_1 (node
, data
, &callers
);
2231 /* Perform the delayed update of the overall summary of all callers
2232 processed. This avoids quadratic behavior in the cases where
2233 we have a lot of calls to the same function. */
2234 for (hash_set
<cgraph_node
*>::iterator i
= callers
.begin ();
2235 i
!= callers
.end (); ++i
)
2236 inline_update_overall_summary (*i
);
2240 /* Output overall time estimate. */
2242 dump_overall_stats (void)
2244 int64_t sum_weighted
= 0, sum
= 0;
2245 struct cgraph_node
*node
;
2247 FOR_EACH_DEFINED_FUNCTION (node
)
2248 if (!node
->global
.inlined_to
2251 int time
= inline_summaries
->get (node
)->time
;
2253 sum_weighted
+= time
* node
->count
;
2255 fprintf (dump_file
, "Overall time estimate: "
2256 "%" PRId64
" weighted by profile: "
2257 "%" PRId64
"\n", sum
, sum_weighted
);
2260 /* Output some useful stats about inlining. */
2263 dump_inline_stats (void)
2265 int64_t inlined_cnt
= 0, inlined_indir_cnt
= 0;
2266 int64_t inlined_virt_cnt
= 0, inlined_virt_indir_cnt
= 0;
2267 int64_t noninlined_cnt
= 0, noninlined_indir_cnt
= 0;
2268 int64_t noninlined_virt_cnt
= 0, noninlined_virt_indir_cnt
= 0;
2269 int64_t inlined_speculative
= 0, inlined_speculative_ply
= 0;
2270 int64_t indirect_poly_cnt
= 0, indirect_cnt
= 0;
2271 int64_t reason
[CIF_N_REASONS
][3];
2273 struct cgraph_node
*node
;
2275 memset (reason
, 0, sizeof (reason
));
2276 FOR_EACH_DEFINED_FUNCTION (node
)
2278 struct cgraph_edge
*e
;
2279 for (e
= node
->callees
; e
; e
= e
->next_callee
)
2281 if (e
->inline_failed
)
2283 reason
[(int) e
->inline_failed
][0] += e
->count
;
2284 reason
[(int) e
->inline_failed
][1] += e
->frequency
;
2285 reason
[(int) e
->inline_failed
][2] ++;
2286 if (DECL_VIRTUAL_P (e
->callee
->decl
))
2288 if (e
->indirect_inlining_edge
)
2289 noninlined_virt_indir_cnt
+= e
->count
;
2291 noninlined_virt_cnt
+= e
->count
;
2295 if (e
->indirect_inlining_edge
)
2296 noninlined_indir_cnt
+= e
->count
;
2298 noninlined_cnt
+= e
->count
;
2305 if (DECL_VIRTUAL_P (e
->callee
->decl
))
2306 inlined_speculative_ply
+= e
->count
;
2308 inlined_speculative
+= e
->count
;
2310 else if (DECL_VIRTUAL_P (e
->callee
->decl
))
2312 if (e
->indirect_inlining_edge
)
2313 inlined_virt_indir_cnt
+= e
->count
;
2315 inlined_virt_cnt
+= e
->count
;
2319 if (e
->indirect_inlining_edge
)
2320 inlined_indir_cnt
+= e
->count
;
2322 inlined_cnt
+= e
->count
;
2326 for (e
= node
->indirect_calls
; e
; e
= e
->next_callee
)
2327 if (e
->indirect_info
->polymorphic
)
2328 indirect_poly_cnt
+= e
->count
;
2330 indirect_cnt
+= e
->count
;
2335 "Inlined %" PRId64
" + speculative "
2336 "%" PRId64
" + speculative polymorphic "
2337 "%" PRId64
" + previously indirect "
2338 "%" PRId64
" + virtual "
2339 "%" PRId64
" + virtual and previously indirect "
2340 "%" PRId64
"\n" "Not inlined "
2341 "%" PRId64
" + previously indirect "
2342 "%" PRId64
" + virtual "
2343 "%" PRId64
" + virtual and previously indirect "
2344 "%" PRId64
" + stil indirect "
2345 "%" PRId64
" + still indirect polymorphic "
2346 "%" PRId64
"\n", inlined_cnt
,
2347 inlined_speculative
, inlined_speculative_ply
,
2348 inlined_indir_cnt
, inlined_virt_cnt
, inlined_virt_indir_cnt
,
2349 noninlined_cnt
, noninlined_indir_cnt
, noninlined_virt_cnt
,
2350 noninlined_virt_indir_cnt
, indirect_cnt
, indirect_poly_cnt
);
2352 "Removed speculations %" PRId64
"\n",
2355 dump_overall_stats ();
2356 fprintf (dump_file
, "\nWhy inlining failed?\n");
2357 for (i
= 0; i
< CIF_N_REASONS
; i
++)
2359 fprintf (dump_file
, "%-50s: %8i calls, %8i freq, %" PRId64
" count\n",
2360 cgraph_inline_failed_string ((cgraph_inline_failed_t
) i
),
2361 (int) reason
[i
][2], (int) reason
[i
][1], reason
[i
][0]);
2364 /* Decide on the inlining. We do so in the topological order to avoid
2365 expenses on updating data structures. */
2370 struct cgraph_node
*node
;
2372 struct cgraph_node
**order
;
2375 bool remove_functions
= false;
2380 cgraph_freq_base_rec
= (sreal
) 1 / (sreal
) CGRAPH_FREQ_BASE
;
2381 percent_rec
= (sreal
) 1 / (sreal
) 100;
2383 order
= XCNEWVEC (struct cgraph_node
*, symtab
->cgraph_count
);
2385 if (in_lto_p
&& optimize
)
2386 ipa_update_after_lto_read ();
2389 dump_inline_summaries (dump_file
);
2391 nnodes
= ipa_reverse_postorder (order
);
2393 FOR_EACH_FUNCTION (node
)
2397 /* Recompute the default reasons for inlining because they may have
2398 changed during merging. */
2401 for (cgraph_edge
*e
= node
->callees
; e
; e
= e
->next_callee
)
2403 gcc_assert (e
->inline_failed
);
2404 initialize_inline_failed (e
);
2406 for (cgraph_edge
*e
= node
->indirect_calls
; e
; e
= e
->next_callee
)
2407 initialize_inline_failed (e
);
2412 fprintf (dump_file
, "\nFlattening functions:\n");
2414 /* In the first pass handle functions to be flattened. Do this with
2415 a priority so none of our later choices will make this impossible. */
2416 for (i
= nnodes
- 1; i
>= 0; i
--)
2420 /* Handle nodes to be flattened.
2421 Ideally when processing callees we stop inlining at the
2422 entry of cycles, possibly cloning that entry point and
2423 try to flatten itself turning it into a self-recursive
2425 if (lookup_attribute ("flatten",
2426 DECL_ATTRIBUTES (node
->decl
)) != NULL
)
2430 "Flattening %s\n", node
->name ());
2431 flatten_function (node
, false);
2435 dump_overall_stats ();
2437 inline_small_functions ();
2439 gcc_assert (symtab
->state
== IPA_SSA
);
2440 symtab
->state
= IPA_SSA_AFTER_INLINING
;
2441 /* Do first after-inlining removal. We want to remove all "stale" extern
2442 inline functions and virtual functions so we really know what is called
2444 symtab
->remove_unreachable_nodes (dump_file
);
2447 /* Inline functions with a property that after inlining into all callers the
2448 code size will shrink because the out-of-line copy is eliminated.
2449 We do this regardless on the callee size as long as function growth limits
2453 "\nDeciding on functions to be inlined into all callers and "
2454 "removing useless speculations:\n");
2456 /* Inlining one function called once has good chance of preventing
2457 inlining other function into the same callee. Ideally we should
2458 work in priority order, but probably inlining hot functions first
2459 is good cut without the extra pain of maintaining the queue.
2461 ??? this is not really fitting the bill perfectly: inlining function
2462 into callee often leads to better optimization of callee due to
2463 increased context for optimization.
2464 For example if main() function calls a function that outputs help
2465 and then function that does the main optmization, we should inline
2466 the second with priority even if both calls are cold by themselves.
2468 We probably want to implement new predicate replacing our use of
2469 maybe_hot_edge interpreted as maybe_hot_edge || callee is known
2471 for (cold
= 0; cold
<= 1; cold
++)
2473 FOR_EACH_DEFINED_FUNCTION (node
)
2475 struct cgraph_edge
*edge
, *next
;
2478 for (edge
= node
->callees
; edge
; edge
= next
)
2480 next
= edge
->next_callee
;
2481 if (edge
->speculative
&& !speculation_useful_p (edge
, false))
2483 edge
->resolve_speculation ();
2484 spec_rem
+= edge
->count
;
2486 remove_functions
= true;
2491 struct cgraph_node
*where
= node
->global
.inlined_to
2492 ? node
->global
.inlined_to
: node
;
2493 reset_edge_caches (where
);
2494 inline_update_overall_summary (where
);
2496 if (want_inline_function_to_all_callers_p (node
, cold
))
2499 node
->call_for_symbol_and_aliases (sum_callers
, &num_calls
,
2501 while (node
->call_for_symbol_and_aliases
2502 (inline_to_all_callers
, &num_calls
, true))
2504 remove_functions
= true;
2509 /* Free ipa-prop structures if they are no longer needed. */
2511 ipa_free_all_structures_after_iinln ();
2516 "\nInlined %i calls, eliminated %i functions\n\n",
2517 ncalls_inlined
, nfunctions_inlined
);
2518 dump_inline_stats ();
2522 dump_inline_summaries (dump_file
);
2523 /* In WPA we use inline summaries for partitioning process. */
2525 inline_free_summary ();
2526 return remove_functions
? TODO_remove_functions
: 0;
2529 /* Inline always-inline function calls in NODE. */
2532 inline_always_inline_functions (struct cgraph_node
*node
)
2534 struct cgraph_edge
*e
;
2535 bool inlined
= false;
2537 for (e
= node
->callees
; e
; e
= e
->next_callee
)
2539 struct cgraph_node
*callee
= e
->callee
->ultimate_alias_target ();
2540 if (!DECL_DISREGARD_INLINE_LIMITS (callee
->decl
))
2543 if (e
->recursive_p ())
2546 fprintf (dump_file
, " Not inlining recursive call to %s.\n",
2547 e
->callee
->name ());
2548 e
->inline_failed
= CIF_RECURSIVE_INLINING
;
2552 if (!can_early_inline_edge_p (e
))
2554 /* Set inlined to true if the callee is marked "always_inline" but
2555 is not inlinable. This will allow flagging an error later in
2556 expand_call_inline in tree-inline.c. */
2557 if (lookup_attribute ("always_inline",
2558 DECL_ATTRIBUTES (callee
->decl
)) != NULL
)
2564 fprintf (dump_file
, " Inlining %s into %s (always_inline).\n",
2565 xstrdup_for_dump (e
->callee
->name ()),
2566 xstrdup_for_dump (e
->caller
->name ()));
2567 inline_call (e
, true, NULL
, NULL
, false);
2571 inline_update_overall_summary (node
);
2576 /* Decide on the inlining. We do so in the topological order to avoid
2577 expenses on updating data structures. */
2580 early_inline_small_functions (struct cgraph_node
*node
)
2582 struct cgraph_edge
*e
;
2583 bool inlined
= false;
2585 for (e
= node
->callees
; e
; e
= e
->next_callee
)
2587 struct cgraph_node
*callee
= e
->callee
->ultimate_alias_target ();
2588 if (!inline_summaries
->get (callee
)->inlinable
2589 || !e
->inline_failed
)
2592 /* Do not consider functions not declared inline. */
2593 if (!DECL_DECLARED_INLINE_P (callee
->decl
)
2594 && !opt_for_fn (node
->decl
, flag_inline_small_functions
)
2595 && !opt_for_fn (node
->decl
, flag_inline_functions
))
2599 fprintf (dump_file
, "Considering inline candidate %s.\n",
2602 if (!can_early_inline_edge_p (e
))
2605 if (e
->recursive_p ())
2608 fprintf (dump_file
, " Not inlining: recursive call.\n");
2612 if (!want_early_inline_function_p (e
))
2616 fprintf (dump_file
, " Inlining %s into %s.\n",
2617 xstrdup_for_dump (callee
->name ()),
2618 xstrdup_for_dump (e
->caller
->name ()));
2619 inline_call (e
, true, NULL
, NULL
, false);
2624 inline_update_overall_summary (node
);
2630 early_inliner (function
*fun
)
2632 struct cgraph_node
*node
= cgraph_node::get (current_function_decl
);
2633 struct cgraph_edge
*edge
;
2634 unsigned int todo
= 0;
2636 bool inlined
= false;
2641 /* Do nothing if datastructures for ipa-inliner are already computed. This
2642 happens when some pass decides to construct new function and
2643 cgraph_add_new_function calls lowering passes and early optimization on
2644 it. This may confuse ourself when early inliner decide to inline call to
2645 function clone, because function clones don't have parameter list in
2646 ipa-prop matching their signature. */
2647 if (ipa_node_params_sum
)
2652 node
->remove_all_references ();
2654 /* Rebuild this reference because it dosn't depend on
2655 function's body and it's required to pass cgraph_node
2657 if (node
->instrumented_version
2658 && !node
->instrumentation_clone
)
2659 node
->create_reference (node
->instrumented_version
, IPA_REF_CHKP
, NULL
);
2661 /* Even when not optimizing or not inlining inline always-inline
2663 inlined
= inline_always_inline_functions (node
);
2667 || !flag_early_inlining
2668 /* Never inline regular functions into always-inline functions
2669 during incremental inlining. This sucks as functions calling
2670 always inline functions will get less optimized, but at the
2671 same time inlining of functions calling always inline
2672 function into an always inline function might introduce
2673 cycles of edges to be always inlined in the callgraph.
2675 We might want to be smarter and just avoid this type of inlining. */
2676 || (DECL_DISREGARD_INLINE_LIMITS (node
->decl
)
2677 && lookup_attribute ("always_inline",
2678 DECL_ATTRIBUTES (node
->decl
))))
2680 else if (lookup_attribute ("flatten",
2681 DECL_ATTRIBUTES (node
->decl
)) != NULL
)
2683 /* When the function is marked to be flattened, recursively inline
2687 "Flattening %s\n", node
->name ());
2688 flatten_function (node
, true);
2693 /* If some always_inline functions was inlined, apply the changes.
2694 This way we will not account always inline into growth limits and
2695 moreover we will inline calls from always inlines that we skipped
2696 previously because of conditional above. */
2699 timevar_push (TV_INTEGRATION
);
2700 todo
|= optimize_inline_calls (current_function_decl
);
2701 /* optimize_inline_calls call above might have introduced new
2702 statements that don't have inline parameters computed. */
2703 for (edge
= node
->callees
; edge
; edge
= edge
->next_callee
)
2705 if (inline_edge_summary_vec
.length () > (unsigned) edge
->uid
)
2707 struct inline_edge_summary
*es
= inline_edge_summary (edge
);
2709 = estimate_num_insns (edge
->call_stmt
, &eni_size_weights
);
2711 = estimate_num_insns (edge
->call_stmt
, &eni_time_weights
);
2714 inline_update_overall_summary (node
);
2716 timevar_pop (TV_INTEGRATION
);
2718 /* We iterate incremental inlining to get trivial cases of indirect
2720 while (iterations
< PARAM_VALUE (PARAM_EARLY_INLINER_MAX_ITERATIONS
)
2721 && early_inline_small_functions (node
))
2723 timevar_push (TV_INTEGRATION
);
2724 todo
|= optimize_inline_calls (current_function_decl
);
2726 /* Technically we ought to recompute inline parameters so the new
2727 iteration of early inliner works as expected. We however have
2728 values approximately right and thus we only need to update edge
2729 info that might be cleared out for newly discovered edges. */
2730 for (edge
= node
->callees
; edge
; edge
= edge
->next_callee
)
2732 /* We have no summary for new bound store calls yet. */
2733 if (inline_edge_summary_vec
.length () > (unsigned)edge
->uid
)
2735 struct inline_edge_summary
*es
= inline_edge_summary (edge
);
2737 = estimate_num_insns (edge
->call_stmt
, &eni_size_weights
);
2739 = estimate_num_insns (edge
->call_stmt
, &eni_time_weights
);
2741 if (edge
->callee
->decl
2742 && !gimple_check_call_matching_types (
2743 edge
->call_stmt
, edge
->callee
->decl
, false))
2745 edge
->inline_failed
= CIF_MISMATCHED_ARGUMENTS
;
2746 edge
->call_stmt_cannot_inline_p
= true;
2749 if (iterations
< PARAM_VALUE (PARAM_EARLY_INLINER_MAX_ITERATIONS
) - 1)
2750 inline_update_overall_summary (node
);
2751 timevar_pop (TV_INTEGRATION
);
2756 fprintf (dump_file
, "Iterations: %i\n", iterations
);
2761 timevar_push (TV_INTEGRATION
);
2762 todo
|= optimize_inline_calls (current_function_decl
);
2763 timevar_pop (TV_INTEGRATION
);
2766 fun
->always_inline_functions_inlined
= true;
2771 /* Do inlining of small functions. Doing so early helps profiling and other
2772 passes to be somewhat more effective and avoids some code duplication in
2773 later real inlining pass for testcases with very many function calls. */
2777 const pass_data pass_data_early_inline
=
2779 GIMPLE_PASS
, /* type */
2780 "einline", /* name */
2781 OPTGROUP_INLINE
, /* optinfo_flags */
2782 TV_EARLY_INLINING
, /* tv_id */
2783 PROP_ssa
, /* properties_required */
2784 0, /* properties_provided */
2785 0, /* properties_destroyed */
2786 0, /* todo_flags_start */
2787 0, /* todo_flags_finish */
2790 class pass_early_inline
: public gimple_opt_pass
2793 pass_early_inline (gcc::context
*ctxt
)
2794 : gimple_opt_pass (pass_data_early_inline
, ctxt
)
2797 /* opt_pass methods: */
2798 virtual unsigned int execute (function
*);
2800 }; // class pass_early_inline
2803 pass_early_inline::execute (function
*fun
)
2805 return early_inliner (fun
);
2811 make_pass_early_inline (gcc::context
*ctxt
)
2813 return new pass_early_inline (ctxt
);
2818 const pass_data pass_data_ipa_inline
=
2820 IPA_PASS
, /* type */
2821 "inline", /* name */
2822 OPTGROUP_INLINE
, /* optinfo_flags */
2823 TV_IPA_INLINING
, /* tv_id */
2824 0, /* properties_required */
2825 0, /* properties_provided */
2826 0, /* properties_destroyed */
2827 0, /* todo_flags_start */
2828 ( TODO_dump_symtab
), /* todo_flags_finish */
2831 class pass_ipa_inline
: public ipa_opt_pass_d
2834 pass_ipa_inline (gcc::context
*ctxt
)
2835 : ipa_opt_pass_d (pass_data_ipa_inline
, ctxt
,
2836 inline_generate_summary
, /* generate_summary */
2837 inline_write_summary
, /* write_summary */
2838 inline_read_summary
, /* read_summary */
2839 NULL
, /* write_optimization_summary */
2840 NULL
, /* read_optimization_summary */
2841 NULL
, /* stmt_fixup */
2842 0, /* function_transform_todo_flags_start */
2843 inline_transform
, /* function_transform */
2844 NULL
) /* variable_transform */
2847 /* opt_pass methods: */
2848 virtual unsigned int execute (function
*) { return ipa_inline (); }
2850 }; // class pass_ipa_inline
2855 make_pass_ipa_inline (gcc::context
*ctxt
)
2857 return new pass_ipa_inline (ctxt
);