1 /* Inlining decision heuristics.
2 Copyright (C) 2003-2017 Free Software Foundation, Inc.
3 Contributed by Jan Hubicka
5 This file is part of GCC.
7 GCC is free software; you can redistribute it and/or modify it under
8 the terms of the GNU General Public License as published by the Free
9 Software Foundation; either version 3, or (at your option) any later
12 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
13 WARRANTY; without even the implied warranty of MERCHANTABILITY or
14 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
17 You should have received a copy of the GNU General Public License
18 along with GCC; see the file COPYING3. If not see
19 <http://www.gnu.org/licenses/>. */
21 /* Inlining decision heuristics
23 The implementation of inliner is organized as follows:
25 inlining heuristics limits
27 can_inline_edge_p allow to check that particular inlining is allowed
28 by the limits specified by user (allowed function growth, growth and so
31 Functions are inlined when it is obvious the result is profitable (such
32 as functions called once or when inlining reduce code size).
33 In addition to that we perform inlining of small functions and recursive
38 The inliner itself is split into two passes:
42 Simple local inlining pass inlining callees into current function.
43 This pass makes no use of whole unit analysis and thus it can do only
44 very simple decisions based on local properties.
46 The strength of the pass is that it is run in topological order
47 (reverse postorder) on the callgraph. Functions are converted into SSA
48 form just before this pass and optimized subsequently. As a result, the
49 callees of the function seen by the early inliner was already optimized
50 and results of early inlining adds a lot of optimization opportunities
51 for the local optimization.
53 The pass handle the obvious inlining decisions within the compilation
54 unit - inlining auto inline functions, inlining for size and
57 main strength of the pass is the ability to eliminate abstraction
58 penalty in C++ code (via combination of inlining and early
59 optimization) and thus improve quality of analysis done by real IPA
62 Because of lack of whole unit knowledge, the pass can not really make
63 good code size/performance tradeoffs. It however does very simple
64 speculative inlining allowing code size to grow by
65 EARLY_INLINING_INSNS when callee is leaf function. In this case the
66 optimizations performed later are very likely to eliminate the cost.
70 This is the real inliner able to handle inlining with whole program
71 knowledge. It performs following steps:
73 1) inlining of small functions. This is implemented by greedy
74 algorithm ordering all inlinable cgraph edges by their badness and
75 inlining them in this order as long as inline limits allows doing so.
77 This heuristics is not very good on inlining recursive calls. Recursive
78 calls can be inlined with results similar to loop unrolling. To do so,
79 special purpose recursive inliner is executed on function when
80 recursive edge is met as viable candidate.
82 2) Unreachable functions are removed from callgraph. Inlining leads
83 to devirtualization and other modification of callgraph so functions
84 may become unreachable during the process. Also functions declared as
85 extern inline or virtual functions are removed, since after inlining
86 we no longer need the offline bodies.
88 3) Functions called once and not exported from the unit are inlined.
89 This should almost always lead to reduction of code size by eliminating
90 the need for offline copy of the function. */
94 #include "coretypes.h"
100 #include "alloc-pool.h"
101 #include "tree-pass.h"
102 #include "gimple-ssa.h"
104 #include "lto-streamer.h"
105 #include "trans-mem.h"
107 #include "tree-inline.h"
110 #include "symbol-summary.h"
111 #include "tree-vrp.h"
112 #include "ipa-prop.h"
113 #include "ipa-inline.h"
114 #include "ipa-utils.h"
116 #include "auto-profile.h"
117 #include "builtins.h"
118 #include "fibonacci_heap.h"
120 typedef fibonacci_heap
<sreal
, cgraph_edge
> edge_heap_t
;
121 typedef fibonacci_node
<sreal
, cgraph_edge
> edge_heap_node_t
;
123 /* Statistics we collect about inlining algorithm. */
124 static int overall_size
;
125 static gcov_type max_count
;
126 static gcov_type spec_rem
;
128 /* Pre-computed constants 1/CGRAPH_FREQ_BASE and 1/100. */
129 static sreal cgraph_freq_base_rec
, percent_rec
;
131 /* Return false when inlining edge E would lead to violating
132 limits on function unit growth or stack usage growth.
134 The relative function body growth limit is present generally
135 to avoid problems with non-linear behavior of the compiler.
136 To allow inlining huge functions into tiny wrapper, the limit
137 is always based on the bigger of the two functions considered.
139 For stack growth limits we always base the growth in stack usage
140 of the callers. We want to prevent applications from segfaulting
141 on stack overflow when functions with huge stack frames gets
145 caller_growth_limits (struct cgraph_edge
*e
)
147 struct cgraph_node
*to
= e
->caller
;
148 struct cgraph_node
*what
= e
->callee
->ultimate_alias_target ();
151 HOST_WIDE_INT stack_size_limit
= 0, inlined_stack
;
152 inline_summary
*info
, *what_info
, *outer_info
= inline_summaries
->get (to
);
154 /* Look for function e->caller is inlined to. While doing
155 so work out the largest function body on the way. As
156 described above, we want to base our function growth
157 limits based on that. Not on the self size of the
158 outer function, not on the self size of inline code
159 we immediately inline to. This is the most relaxed
160 interpretation of the rule "do not grow large functions
161 too much in order to prevent compiler from exploding". */
164 info
= inline_summaries
->get (to
);
165 if (limit
< info
->self_size
)
166 limit
= info
->self_size
;
167 if (stack_size_limit
< info
->estimated_self_stack_size
)
168 stack_size_limit
= info
->estimated_self_stack_size
;
169 if (to
->global
.inlined_to
)
170 to
= to
->callers
->caller
;
175 what_info
= inline_summaries
->get (what
);
177 if (limit
< what_info
->self_size
)
178 limit
= what_info
->self_size
;
180 limit
+= limit
* PARAM_VALUE (PARAM_LARGE_FUNCTION_GROWTH
) / 100;
182 /* Check the size after inlining against the function limits. But allow
183 the function to shrink if it went over the limits by forced inlining. */
184 newsize
= estimate_size_after_inlining (to
, e
);
185 if (newsize
>= info
->size
186 && newsize
> PARAM_VALUE (PARAM_LARGE_FUNCTION_INSNS
)
189 e
->inline_failed
= CIF_LARGE_FUNCTION_GROWTH_LIMIT
;
193 if (!what_info
->estimated_stack_size
)
196 /* FIXME: Stack size limit often prevents inlining in Fortran programs
197 due to large i/o datastructures used by the Fortran front-end.
198 We ought to ignore this limit when we know that the edge is executed
199 on every invocation of the caller (i.e. its call statement dominates
200 exit block). We do not track this information, yet. */
201 stack_size_limit
+= ((gcov_type
)stack_size_limit
202 * PARAM_VALUE (PARAM_STACK_FRAME_GROWTH
) / 100);
204 inlined_stack
= (outer_info
->stack_frame_offset
205 + outer_info
->estimated_self_stack_size
206 + what_info
->estimated_stack_size
);
207 /* Check new stack consumption with stack consumption at the place
209 if (inlined_stack
> stack_size_limit
210 /* If function already has large stack usage from sibling
211 inline call, we can inline, too.
212 This bit overoptimistically assume that we are good at stack
214 && inlined_stack
> info
->estimated_stack_size
215 && inlined_stack
> PARAM_VALUE (PARAM_LARGE_STACK_FRAME
))
217 e
->inline_failed
= CIF_LARGE_STACK_FRAME_GROWTH_LIMIT
;
223 /* Dump info about why inlining has failed. */
226 report_inline_failed_reason (struct cgraph_edge
*e
)
230 fprintf (dump_file
, " not inlinable: %s/%i -> %s/%i, %s\n",
231 xstrdup_for_dump (e
->caller
->name ()), e
->caller
->order
,
232 xstrdup_for_dump (e
->callee
->name ()), e
->callee
->order
,
233 cgraph_inline_failed_string (e
->inline_failed
));
234 if ((e
->inline_failed
== CIF_TARGET_OPTION_MISMATCH
235 || e
->inline_failed
== CIF_OPTIMIZATION_MISMATCH
)
236 && e
->caller
->lto_file_data
237 && e
->callee
->ultimate_alias_target ()->lto_file_data
)
239 fprintf (dump_file
, " LTO objects: %s, %s\n",
240 e
->caller
->lto_file_data
->file_name
,
241 e
->callee
->ultimate_alias_target ()->lto_file_data
->file_name
);
243 if (e
->inline_failed
== CIF_TARGET_OPTION_MISMATCH
)
244 cl_target_option_print_diff
245 (dump_file
, 2, target_opts_for_fn (e
->caller
->decl
),
246 target_opts_for_fn (e
->callee
->ultimate_alias_target ()->decl
));
247 if (e
->inline_failed
== CIF_OPTIMIZATION_MISMATCH
)
248 cl_optimization_print_diff
249 (dump_file
, 2, opts_for_fn (e
->caller
->decl
),
250 opts_for_fn (e
->callee
->ultimate_alias_target ()->decl
));
254 /* Decide whether sanitizer-related attributes allow inlining. */
257 sanitize_attrs_match_for_inline_p (const_tree caller
, const_tree callee
)
259 /* Don't care if sanitizer is disabled */
260 if (!(flag_sanitize
& SANITIZE_ADDRESS
))
263 if (!caller
|| !callee
)
266 return !!lookup_attribute ("no_sanitize_address",
267 DECL_ATTRIBUTES (caller
)) ==
268 !!lookup_attribute ("no_sanitize_address",
269 DECL_ATTRIBUTES (callee
));
272 /* Used for flags where it is safe to inline when caller's value is
273 grater than callee's. */
274 #define check_maybe_up(flag) \
275 (opts_for_fn (caller->decl)->x_##flag \
276 != opts_for_fn (callee->decl)->x_##flag \
278 || opts_for_fn (caller->decl)->x_##flag \
279 < opts_for_fn (callee->decl)->x_##flag))
280 /* Used for flags where it is safe to inline when caller's value is
281 smaller than callee's. */
282 #define check_maybe_down(flag) \
283 (opts_for_fn (caller->decl)->x_##flag \
284 != opts_for_fn (callee->decl)->x_##flag \
286 || opts_for_fn (caller->decl)->x_##flag \
287 > opts_for_fn (callee->decl)->x_##flag))
288 /* Used for flags where exact match is needed for correctness. */
289 #define check_match(flag) \
290 (opts_for_fn (caller->decl)->x_##flag \
291 != opts_for_fn (callee->decl)->x_##flag)
293 /* Decide if we can inline the edge and possibly update
294 inline_failed reason.
295 We check whether inlining is possible at all and whether
296 caller growth limits allow doing so.
298 if REPORT is true, output reason to the dump file.
300 if DISREGARD_LIMITS is true, ignore size limits.*/
303 can_inline_edge_p (struct cgraph_edge
*e
, bool report
,
304 bool disregard_limits
= false, bool early
= false)
306 gcc_checking_assert (e
->inline_failed
);
308 if (cgraph_inline_failed_type (e
->inline_failed
) == CIF_FINAL_ERROR
)
311 report_inline_failed_reason (e
);
315 bool inlinable
= true;
316 enum availability avail
;
317 cgraph_node
*caller
= e
->caller
->global
.inlined_to
318 ? e
->caller
->global
.inlined_to
: e
->caller
;
319 cgraph_node
*callee
= e
->callee
->ultimate_alias_target (&avail
, caller
);
320 tree caller_tree
= DECL_FUNCTION_SPECIFIC_OPTIMIZATION (caller
->decl
);
322 = callee
? DECL_FUNCTION_SPECIFIC_OPTIMIZATION (callee
->decl
) : NULL
;
324 if (!callee
->definition
)
326 e
->inline_failed
= CIF_BODY_NOT_AVAILABLE
;
329 else if (callee
->calls_comdat_local
)
331 e
->inline_failed
= CIF_USES_COMDAT_LOCAL
;
334 else if (avail
<= AVAIL_INTERPOSABLE
)
336 e
->inline_failed
= CIF_OVERWRITABLE
;
339 /* All edges with call_stmt_cannot_inline_p should have inline_failed
340 initialized to one of FINAL_ERROR reasons. */
341 else if (e
->call_stmt_cannot_inline_p
)
343 /* Don't inline if the functions have different EH personalities. */
344 else if (DECL_FUNCTION_PERSONALITY (caller
->decl
)
345 && DECL_FUNCTION_PERSONALITY (callee
->decl
)
346 && (DECL_FUNCTION_PERSONALITY (caller
->decl
)
347 != DECL_FUNCTION_PERSONALITY (callee
->decl
)))
349 e
->inline_failed
= CIF_EH_PERSONALITY
;
352 /* TM pure functions should not be inlined into non-TM_pure
354 else if (is_tm_pure (callee
->decl
) && !is_tm_pure (caller
->decl
))
356 e
->inline_failed
= CIF_UNSPECIFIED
;
359 /* Check compatibility of target optimization options. */
360 else if (!targetm
.target_option
.can_inline_p (caller
->decl
,
363 e
->inline_failed
= CIF_TARGET_OPTION_MISMATCH
;
366 else if (!inline_summaries
->get (callee
)->inlinable
)
368 e
->inline_failed
= CIF_FUNCTION_NOT_INLINABLE
;
371 /* Don't inline a function with mismatched sanitization attributes. */
372 else if (!sanitize_attrs_match_for_inline_p (caller
->decl
, callee
->decl
))
374 e
->inline_failed
= CIF_ATTRIBUTE_MISMATCH
;
377 /* Check if caller growth allows the inlining. */
378 else if (!DECL_DISREGARD_INLINE_LIMITS (callee
->decl
)
380 && !lookup_attribute ("flatten",
381 DECL_ATTRIBUTES (caller
->decl
))
382 && !caller_growth_limits (e
))
384 /* Don't inline a function with a higher optimization level than the
385 caller. FIXME: this is really just tip of iceberg of handling
386 optimization attribute. */
387 else if (caller_tree
!= callee_tree
)
390 (DECL_DISREGARD_INLINE_LIMITS (callee
->decl
)
391 && lookup_attribute ("always_inline",
392 DECL_ATTRIBUTES (callee
->decl
)));
393 inline_summary
*caller_info
= inline_summaries
->get (caller
);
394 inline_summary
*callee_info
= inline_summaries
->get (callee
);
396 /* Until GCC 4.9 we did not check the semantics alterning flags
397 bellow and inline across optimization boundry.
398 Enabling checks bellow breaks several packages by refusing
399 to inline library always_inline functions. See PR65873.
400 Disable the check for early inlining for now until better solution
402 if (always_inline
&& early
)
404 /* There are some options that change IL semantics which means
405 we cannot inline in these cases for correctness reason.
406 Not even for always_inline declared functions. */
407 /* Strictly speaking only when the callee contains signed integer
408 math where overflow is undefined. */
409 else if ((check_maybe_up (flag_strict_overflow
)
410 /* this flag is set by optimize. Allow inlining across
411 optimize boundary. */
412 && (!opt_for_fn (caller
->decl
, optimize
)
413 == !opt_for_fn (callee
->decl
, optimize
) || !always_inline
))
414 || check_match (flag_wrapv
)
415 || check_match (flag_trapv
)
416 /* When caller or callee does FP math, be sure FP codegen flags
418 || ((caller_info
->fp_expressions
&& callee_info
->fp_expressions
)
419 && (check_maybe_up (flag_rounding_math
)
420 || check_maybe_up (flag_trapping_math
)
421 || check_maybe_down (flag_unsafe_math_optimizations
)
422 || check_maybe_down (flag_finite_math_only
)
423 || check_maybe_up (flag_signaling_nans
)
424 || check_maybe_down (flag_cx_limited_range
)
425 || check_maybe_up (flag_signed_zeros
)
426 || check_maybe_down (flag_associative_math
)
427 || check_maybe_down (flag_reciprocal_math
)
428 || check_maybe_down (flag_fp_int_builtin_inexact
)
429 /* Strictly speaking only when the callee contains function
430 calls that may end up setting errno. */
431 || check_maybe_up (flag_errno_math
)))
432 /* We do not want to make code compiled with exceptions to be
433 brought into a non-EH function unless we know that the callee
435 This is tracked by DECL_FUNCTION_PERSONALITY. */
436 || (check_maybe_up (flag_non_call_exceptions
)
437 && DECL_FUNCTION_PERSONALITY (callee
->decl
))
438 || (check_maybe_up (flag_exceptions
)
439 && DECL_FUNCTION_PERSONALITY (callee
->decl
))
440 /* When devirtualization is diabled for callee, it is not safe
441 to inline it as we possibly mangled the type info.
442 Allow early inlining of always inlines. */
443 || (!early
&& check_maybe_down (flag_devirtualize
)))
445 e
->inline_failed
= CIF_OPTIMIZATION_MISMATCH
;
448 /* gcc.dg/pr43564.c. Apply user-forced inline even at -O0. */
449 else if (always_inline
)
451 /* When user added an attribute to the callee honor it. */
452 else if (lookup_attribute ("optimize", DECL_ATTRIBUTES (callee
->decl
))
453 && opts_for_fn (caller
->decl
) != opts_for_fn (callee
->decl
))
455 e
->inline_failed
= CIF_OPTIMIZATION_MISMATCH
;
458 /* If explicit optimize attribute are not used, the mismatch is caused
459 by different command line options used to build different units.
460 Do not care about COMDAT functions - those are intended to be
461 optimized with the optimization flags of module they are used in.
462 Also do not care about mixing up size/speed optimization when
463 DECL_DISREGARD_INLINE_LIMITS is set. */
464 else if ((callee
->merged_comdat
465 && !lookup_attribute ("optimize",
466 DECL_ATTRIBUTES (caller
->decl
)))
467 || DECL_DISREGARD_INLINE_LIMITS (callee
->decl
))
469 /* If mismatch is caused by merging two LTO units with different
470 optimizationflags we want to be bit nicer. However never inline
471 if one of functions is not optimized at all. */
472 else if (!opt_for_fn (callee
->decl
, optimize
)
473 || !opt_for_fn (caller
->decl
, optimize
))
475 e
->inline_failed
= CIF_OPTIMIZATION_MISMATCH
;
478 /* If callee is optimized for size and caller is not, allow inlining if
479 code shrinks or we are in MAX_INLINE_INSNS_SINGLE limit and callee
480 is inline (and thus likely an unified comdat). This will allow caller
482 else if (opt_for_fn (callee
->decl
, optimize_size
)
483 > opt_for_fn (caller
->decl
, optimize_size
))
485 int growth
= estimate_edge_growth (e
);
487 && (!DECL_DECLARED_INLINE_P (callee
->decl
)
488 && growth
>= MAX (MAX_INLINE_INSNS_SINGLE
,
489 MAX_INLINE_INSNS_AUTO
)))
491 e
->inline_failed
= CIF_OPTIMIZATION_MISMATCH
;
495 /* If callee is more aggressively optimized for performance than caller,
496 we generally want to inline only cheap (runtime wise) functions. */
497 else if (opt_for_fn (callee
->decl
, optimize_size
)
498 < opt_for_fn (caller
->decl
, optimize_size
)
499 || (opt_for_fn (callee
->decl
, optimize
)
500 > opt_for_fn (caller
->decl
, optimize
)))
502 if (estimate_edge_time (e
)
503 >= 20 + inline_edge_summary (e
)->call_stmt_time
)
505 e
->inline_failed
= CIF_OPTIMIZATION_MISMATCH
;
512 if (!inlinable
&& report
)
513 report_inline_failed_reason (e
);
518 /* Return true if the edge E is inlinable during early inlining. */
521 can_early_inline_edge_p (struct cgraph_edge
*e
)
523 struct cgraph_node
*callee
= e
->callee
->ultimate_alias_target ();
524 /* Early inliner might get called at WPA stage when IPA pass adds new
525 function. In this case we can not really do any of early inlining
526 because function bodies are missing. */
527 if (cgraph_inline_failed_type (e
->inline_failed
) == CIF_FINAL_ERROR
)
529 if (!gimple_has_body_p (callee
->decl
))
531 e
->inline_failed
= CIF_BODY_NOT_AVAILABLE
;
534 /* In early inliner some of callees may not be in SSA form yet
535 (i.e. the callgraph is cyclic and we did not process
536 the callee by early inliner, yet). We don't have CIF code for this
537 case; later we will re-do the decision in the real inliner. */
538 if (!gimple_in_ssa_p (DECL_STRUCT_FUNCTION (e
->caller
->decl
))
539 || !gimple_in_ssa_p (DECL_STRUCT_FUNCTION (callee
->decl
)))
542 fprintf (dump_file
, " edge not inlinable: not in SSA form\n");
545 if (!can_inline_edge_p (e
, true, false, true))
551 /* Return number of calls in N. Ignore cheap builtins. */
554 num_calls (struct cgraph_node
*n
)
556 struct cgraph_edge
*e
;
559 for (e
= n
->callees
; e
; e
= e
->next_callee
)
560 if (!is_inexpensive_builtin (e
->callee
->decl
))
566 /* Return true if we are interested in inlining small function. */
569 want_early_inline_function_p (struct cgraph_edge
*e
)
571 bool want_inline
= true;
572 struct cgraph_node
*callee
= e
->callee
->ultimate_alias_target ();
574 if (DECL_DISREGARD_INLINE_LIMITS (callee
->decl
))
576 /* For AutoFDO, we need to make sure that before profile summary, all
577 hot paths' IR look exactly the same as profiled binary. As a result,
578 in einliner, we will disregard size limit and inline those callsites
580 * inlined in the profiled binary, and
581 * the cloned callee has enough samples to be considered "hot". */
582 else if (flag_auto_profile
&& afdo_callsite_hot_enough_for_early_inline (e
))
584 else if (!DECL_DECLARED_INLINE_P (callee
->decl
)
585 && !opt_for_fn (e
->caller
->decl
, flag_inline_small_functions
))
587 e
->inline_failed
= CIF_FUNCTION_NOT_INLINE_CANDIDATE
;
588 report_inline_failed_reason (e
);
593 int growth
= estimate_edge_growth (e
);
598 else if (!e
->maybe_hot_p ()
602 fprintf (dump_file
, " will not early inline: %s/%i->%s/%i, "
603 "call is cold and code would grow by %i\n",
604 xstrdup_for_dump (e
->caller
->name ()),
606 xstrdup_for_dump (callee
->name ()), callee
->order
,
610 else if (growth
> PARAM_VALUE (PARAM_EARLY_INLINING_INSNS
))
613 fprintf (dump_file
, " will not early inline: %s/%i->%s/%i, "
614 "growth %i exceeds --param early-inlining-insns\n",
615 xstrdup_for_dump (e
->caller
->name ()),
617 xstrdup_for_dump (callee
->name ()), callee
->order
,
621 else if ((n
= num_calls (callee
)) != 0
622 && growth
* (n
+ 1) > PARAM_VALUE (PARAM_EARLY_INLINING_INSNS
))
625 fprintf (dump_file
, " will not early inline: %s/%i->%s/%i, "
626 "growth %i exceeds --param early-inlining-insns "
627 "divided by number of calls\n",
628 xstrdup_for_dump (e
->caller
->name ()),
630 xstrdup_for_dump (callee
->name ()), callee
->order
,
638 /* Compute time of the edge->caller + edge->callee execution when inlining
642 compute_uninlined_call_time (struct cgraph_edge
*edge
,
643 sreal uninlined_call_time
)
645 cgraph_node
*caller
= (edge
->caller
->global
.inlined_to
646 ? edge
->caller
->global
.inlined_to
649 if (edge
->count
&& caller
->count
)
650 uninlined_call_time
*= (sreal
)edge
->count
/ caller
->count
;
652 uninlined_call_time
*= cgraph_freq_base_rec
* edge
->frequency
;
654 uninlined_call_time
= uninlined_call_time
>> 11;
656 sreal caller_time
= inline_summaries
->get (caller
)->time
;
657 return uninlined_call_time
+ caller_time
;
660 /* Same as compute_uinlined_call_time but compute time when inlining
664 compute_inlined_call_time (struct cgraph_edge
*edge
,
667 cgraph_node
*caller
= (edge
->caller
->global
.inlined_to
668 ? edge
->caller
->global
.inlined_to
670 sreal caller_time
= inline_summaries
->get (caller
)->time
;
672 if (edge
->count
&& caller
->count
)
673 time
*= (sreal
)edge
->count
/ caller
->count
;
675 time
*= cgraph_freq_base_rec
* edge
->frequency
;
679 /* This calculation should match one in ipa-inline-analysis.c
680 (estimate_edge_size_and_time). */
681 time
-= (sreal
) edge
->frequency
682 * inline_edge_summary (edge
)->call_stmt_time
/ CGRAPH_FREQ_BASE
;
685 time
= ((sreal
) 1) >> 8;
686 gcc_checking_assert (time
>= 0);
690 /* Return true if the speedup for inlining E is bigger than
691 PARAM_MAX_INLINE_MIN_SPEEDUP. */
694 big_speedup_p (struct cgraph_edge
*e
)
697 sreal spec_time
= estimate_edge_time (e
, &unspec_time
);
698 sreal time
= compute_uninlined_call_time (e
, unspec_time
);
699 sreal inlined_time
= compute_inlined_call_time (e
, spec_time
);
701 if (time
- inlined_time
702 > (sreal
) (time
* PARAM_VALUE (PARAM_INLINE_MIN_SPEEDUP
))
708 /* Return true if we are interested in inlining small function.
709 When REPORT is true, report reason to dump file. */
712 want_inline_small_function_p (struct cgraph_edge
*e
, bool report
)
714 bool want_inline
= true;
715 struct cgraph_node
*callee
= e
->callee
->ultimate_alias_target ();
717 if (DECL_DISREGARD_INLINE_LIMITS (callee
->decl
))
719 else if (!DECL_DECLARED_INLINE_P (callee
->decl
)
720 && !opt_for_fn (e
->caller
->decl
, flag_inline_small_functions
))
722 e
->inline_failed
= CIF_FUNCTION_NOT_INLINE_CANDIDATE
;
725 /* Do fast and conservative check if the function can be good
726 inline candidate. At the moment we allow inline hints to
727 promote non-inline functions to inline and we increase
728 MAX_INLINE_INSNS_SINGLE 16-fold for inline functions. */
729 else if ((!DECL_DECLARED_INLINE_P (callee
->decl
)
730 && (!e
->count
|| !e
->maybe_hot_p ()))
731 && inline_summaries
->get (callee
)->min_size
732 - inline_edge_summary (e
)->call_stmt_size
733 > MAX (MAX_INLINE_INSNS_SINGLE
, MAX_INLINE_INSNS_AUTO
))
735 e
->inline_failed
= CIF_MAX_INLINE_INSNS_AUTO_LIMIT
;
738 else if ((DECL_DECLARED_INLINE_P (callee
->decl
) || e
->count
)
739 && inline_summaries
->get (callee
)->min_size
740 - inline_edge_summary (e
)->call_stmt_size
741 > 16 * MAX_INLINE_INSNS_SINGLE
)
743 e
->inline_failed
= (DECL_DECLARED_INLINE_P (callee
->decl
)
744 ? CIF_MAX_INLINE_INSNS_SINGLE_LIMIT
745 : CIF_MAX_INLINE_INSNS_AUTO_LIMIT
);
750 int growth
= estimate_edge_growth (e
);
751 inline_hints hints
= estimate_edge_hints (e
);
752 bool big_speedup
= big_speedup_p (e
);
756 /* Apply MAX_INLINE_INSNS_SINGLE limit. Do not do so when
757 hints suggests that inlining given function is very profitable. */
758 else if (DECL_DECLARED_INLINE_P (callee
->decl
)
759 && growth
>= MAX_INLINE_INSNS_SINGLE
761 && !(hints
& (INLINE_HINT_indirect_call
762 | INLINE_HINT_known_hot
763 | INLINE_HINT_loop_iterations
764 | INLINE_HINT_array_index
765 | INLINE_HINT_loop_stride
)))
766 || growth
>= MAX_INLINE_INSNS_SINGLE
* 16))
768 e
->inline_failed
= CIF_MAX_INLINE_INSNS_SINGLE_LIMIT
;
771 else if (!DECL_DECLARED_INLINE_P (callee
->decl
)
772 && !opt_for_fn (e
->caller
->decl
, flag_inline_functions
))
774 /* growth_likely_positive is expensive, always test it last. */
775 if (growth
>= MAX_INLINE_INSNS_SINGLE
776 || growth_likely_positive (callee
, growth
))
778 e
->inline_failed
= CIF_NOT_DECLARED_INLINED
;
782 /* Apply MAX_INLINE_INSNS_AUTO limit for functions not declared inline
783 Upgrade it to MAX_INLINE_INSNS_SINGLE when hints suggests that
784 inlining given function is very profitable. */
785 else if (!DECL_DECLARED_INLINE_P (callee
->decl
)
787 && !(hints
& INLINE_HINT_known_hot
)
788 && growth
>= ((hints
& (INLINE_HINT_indirect_call
789 | INLINE_HINT_loop_iterations
790 | INLINE_HINT_array_index
791 | INLINE_HINT_loop_stride
))
792 ? MAX (MAX_INLINE_INSNS_AUTO
,
793 MAX_INLINE_INSNS_SINGLE
)
794 : MAX_INLINE_INSNS_AUTO
))
796 /* growth_likely_positive is expensive, always test it last. */
797 if (growth
>= MAX_INLINE_INSNS_SINGLE
798 || growth_likely_positive (callee
, growth
))
800 e
->inline_failed
= CIF_MAX_INLINE_INSNS_AUTO_LIMIT
;
804 /* If call is cold, do not inline when function body would grow. */
805 else if (!e
->maybe_hot_p ()
806 && (growth
>= MAX_INLINE_INSNS_SINGLE
807 || growth_likely_positive (callee
, growth
)))
809 e
->inline_failed
= CIF_UNLIKELY_CALL
;
813 if (!want_inline
&& report
)
814 report_inline_failed_reason (e
);
818 /* EDGE is self recursive edge.
819 We hand two cases - when function A is inlining into itself
820 or when function A is being inlined into another inliner copy of function
823 In first case OUTER_NODE points to the toplevel copy of A, while
824 in the second case OUTER_NODE points to the outermost copy of A in B.
826 In both cases we want to be extra selective since
827 inlining the call will just introduce new recursive calls to appear. */
830 want_inline_self_recursive_call_p (struct cgraph_edge
*edge
,
831 struct cgraph_node
*outer_node
,
835 char const *reason
= NULL
;
836 bool want_inline
= true;
837 int caller_freq
= CGRAPH_FREQ_BASE
;
838 int max_depth
= PARAM_VALUE (PARAM_MAX_INLINE_RECURSIVE_DEPTH_AUTO
);
840 if (DECL_DECLARED_INLINE_P (edge
->caller
->decl
))
841 max_depth
= PARAM_VALUE (PARAM_MAX_INLINE_RECURSIVE_DEPTH
);
843 if (!edge
->maybe_hot_p ())
845 reason
= "recursive call is cold";
848 else if (max_count
&& !outer_node
->count
)
850 reason
= "not executed in profile";
853 else if (depth
> max_depth
)
855 reason
= "--param max-inline-recursive-depth exceeded.";
859 if (outer_node
->global
.inlined_to
)
860 caller_freq
= outer_node
->callers
->frequency
;
864 reason
= "function is inlined and unlikely";
870 /* Inlining of self recursive function into copy of itself within other function
871 is transformation similar to loop peeling.
873 Peeling is profitable if we can inline enough copies to make probability
874 of actual call to the self recursive function very small. Be sure that
875 the probability of recursion is small.
877 We ensure that the frequency of recursing is at most 1 - (1/max_depth).
878 This way the expected number of recision is at most max_depth. */
881 int max_prob
= CGRAPH_FREQ_BASE
- ((CGRAPH_FREQ_BASE
+ max_depth
- 1)
884 for (i
= 1; i
< depth
; i
++)
885 max_prob
= max_prob
* max_prob
/ CGRAPH_FREQ_BASE
;
887 && (edge
->count
* CGRAPH_FREQ_BASE
/ outer_node
->count
890 reason
= "profile of recursive call is too large";
894 && (edge
->frequency
* CGRAPH_FREQ_BASE
/ caller_freq
897 reason
= "frequency of recursive call is too large";
901 /* Recursive inlining, i.e. equivalent of unrolling, is profitable if recursion
902 depth is large. We reduce function call overhead and increase chances that
903 things fit in hardware return predictor.
905 Recursive inlining might however increase cost of stack frame setup
906 actually slowing down functions whose recursion tree is wide rather than
909 Deciding reliably on when to do recursive inlining without profile feedback
910 is tricky. For now we disable recursive inlining when probability of self
913 Recursive inlining of self recursive call within loop also results in large loop
914 depths that generally optimize badly. We may want to throttle down inlining
915 in those cases. In particular this seems to happen in one of libstdc++ rb tree
920 && (edge
->count
* 100 / outer_node
->count
921 <= PARAM_VALUE (PARAM_MIN_INLINE_RECURSIVE_PROBABILITY
)))
923 reason
= "profile of recursive call is too small";
927 && (edge
->frequency
* 100 / caller_freq
928 <= PARAM_VALUE (PARAM_MIN_INLINE_RECURSIVE_PROBABILITY
)))
930 reason
= "frequency of recursive call is too small";
934 if (!want_inline
&& dump_file
)
935 fprintf (dump_file
, " not inlining recursively: %s\n", reason
);
939 /* Return true when NODE has uninlinable caller;
940 set HAS_HOT_CALL if it has hot call.
941 Worker for cgraph_for_node_and_aliases. */
944 check_callers (struct cgraph_node
*node
, void *has_hot_call
)
946 struct cgraph_edge
*e
;
947 for (e
= node
->callers
; e
; e
= e
->next_caller
)
949 if (!opt_for_fn (e
->caller
->decl
, flag_inline_functions_called_once
))
951 if (!can_inline_edge_p (e
, true))
953 if (e
->recursive_p ())
955 if (!(*(bool *)has_hot_call
) && e
->maybe_hot_p ())
956 *(bool *)has_hot_call
= true;
961 /* If NODE has a caller, return true. */
964 has_caller_p (struct cgraph_node
*node
, void *data ATTRIBUTE_UNUSED
)
971 /* Decide if inlining NODE would reduce unit size by eliminating
972 the offline copy of function.
973 When COLD is true the cold calls are considered, too. */
976 want_inline_function_to_all_callers_p (struct cgraph_node
*node
, bool cold
)
978 bool has_hot_call
= false;
980 /* Aliases gets inlined along with the function they alias. */
983 /* Already inlined? */
984 if (node
->global
.inlined_to
)
986 /* Does it have callers? */
987 if (!node
->call_for_symbol_and_aliases (has_caller_p
, NULL
, true))
989 /* Inlining into all callers would increase size? */
990 if (estimate_growth (node
) > 0)
992 /* All inlines must be possible. */
993 if (node
->call_for_symbol_and_aliases (check_callers
, &has_hot_call
,
996 if (!cold
&& !has_hot_call
)
1001 /* A cost model driving the inlining heuristics in a way so the edges with
1002 smallest badness are inlined first. After each inlining is performed
1003 the costs of all caller edges of nodes affected are recomputed so the
1004 metrics may accurately depend on values such as number of inlinable callers
1005 of the function or function body size. */
1008 edge_badness (struct cgraph_edge
*edge
, bool dump
)
1012 sreal edge_time
, unspec_edge_time
;
1013 struct cgraph_node
*callee
= edge
->callee
->ultimate_alias_target ();
1014 struct inline_summary
*callee_info
= inline_summaries
->get (callee
);
1016 cgraph_node
*caller
= (edge
->caller
->global
.inlined_to
1017 ? edge
->caller
->global
.inlined_to
1020 growth
= estimate_edge_growth (edge
);
1021 edge_time
= estimate_edge_time (edge
, &unspec_edge_time
);
1022 hints
= estimate_edge_hints (edge
);
1023 gcc_checking_assert (edge_time
>= 0);
1024 /* Check that inlined time is better, but tolerate some roundoff issues. */
1025 gcc_checking_assert ((edge_time
- callee_info
->time
).to_int () <= 0);
1026 gcc_checking_assert (growth
<= callee_info
->size
);
1030 fprintf (dump_file
, " Badness calculation for %s/%i -> %s/%i\n",
1031 xstrdup_for_dump (edge
->caller
->name ()),
1032 edge
->caller
->order
,
1033 xstrdup_for_dump (callee
->name ()),
1034 edge
->callee
->order
);
1035 fprintf (dump_file
, " size growth %i, time %f unspec %f ",
1037 edge_time
.to_double (),
1038 unspec_edge_time
.to_double ());
1039 dump_inline_hints (dump_file
, hints
);
1040 if (big_speedup_p (edge
))
1041 fprintf (dump_file
, " big_speedup");
1042 fprintf (dump_file
, "\n");
1045 /* Always prefer inlining saving code size. */
1048 badness
= (sreal
) (-SREAL_MIN_SIG
+ growth
) << (SREAL_MAX_EXP
/ 256);
1050 fprintf (dump_file
, " %f: Growth %d <= 0\n", badness
.to_double (),
1053 /* Inlining into EXTERNAL functions is not going to change anything unless
1054 they are themselves inlined. */
1055 else if (DECL_EXTERNAL (caller
->decl
))
1058 fprintf (dump_file
, " max: function is external\n");
1059 return sreal::max ();
1061 /* When profile is available. Compute badness as:
1063 time_saved * caller_count
1064 goodness = -------------------------------------------------
1065 growth_of_caller * overall_growth * combined_size
1067 badness = - goodness
1069 Again use negative value to make calls with profile appear hotter
1072 else if (opt_for_fn (caller
->decl
, flag_guess_branch_prob
) || caller
->count
)
1074 sreal numerator
, denominator
;
1077 numerator
= (compute_uninlined_call_time (edge
, unspec_edge_time
)
1078 - compute_inlined_call_time (edge
, edge_time
));
1080 numerator
= ((sreal
) 1 >> 8);
1082 numerator
*= caller
->count
;
1083 else if (opt_for_fn (caller
->decl
, flag_branch_probabilities
))
1084 numerator
= numerator
>> 11;
1085 denominator
= growth
;
1087 overall_growth
= callee_info
->growth
;
1089 /* Look for inliner wrappers of the form:
1095 noninline_callee ();
1097 Withhout panilizing this case, we usually inline noninline_callee
1098 into the inline_caller because overall_growth is small preventing
1099 further inlining of inline_caller.
1101 Penalize only callgraph edges to functions with small overall
1104 if (growth
> overall_growth
1105 /* ... and having only one caller which is not inlined ... */
1106 && callee_info
->single_caller
1107 && !edge
->caller
->global
.inlined_to
1108 /* ... and edges executed only conditionally ... */
1109 && edge
->frequency
< CGRAPH_FREQ_BASE
1110 /* ... consider case where callee is not inline but caller is ... */
1111 && ((!DECL_DECLARED_INLINE_P (edge
->callee
->decl
)
1112 && DECL_DECLARED_INLINE_P (caller
->decl
))
1113 /* ... or when early optimizers decided to split and edge
1114 frequency still indicates splitting is a win ... */
1115 || (callee
->split_part
&& !caller
->split_part
1119 (PARAM_PARTIAL_INLINING_ENTRY_PROBABILITY
) / 100
1120 /* ... and do not overwrite user specified hints. */
1121 && (!DECL_DECLARED_INLINE_P (edge
->callee
->decl
)
1122 || DECL_DECLARED_INLINE_P (caller
->decl
)))))
1124 struct inline_summary
*caller_info
= inline_summaries
->get (caller
);
1125 int caller_growth
= caller_info
->growth
;
1127 /* Only apply the penalty when caller looks like inline candidate,
1128 and it is not called once and. */
1129 if (!caller_info
->single_caller
&& overall_growth
< caller_growth
1130 && caller_info
->inlinable
1131 && caller_info
->size
1132 < (DECL_DECLARED_INLINE_P (caller
->decl
)
1133 ? MAX_INLINE_INSNS_SINGLE
: MAX_INLINE_INSNS_AUTO
))
1137 " Wrapper penalty. Increasing growth %i to %i\n",
1138 overall_growth
, caller_growth
);
1139 overall_growth
= caller_growth
;
1142 if (overall_growth
> 0)
1144 /* Strongly preffer functions with few callers that can be inlined
1145 fully. The square root here leads to smaller binaries at average.
1146 Watch however for extreme cases and return to linear function
1147 when growth is large. */
1148 if (overall_growth
< 256)
1149 overall_growth
*= overall_growth
;
1151 overall_growth
+= 256 * 256 - 256;
1152 denominator
*= overall_growth
;
1154 denominator
*= inline_summaries
->get (caller
)->self_size
+ growth
;
1156 badness
= - numerator
/ denominator
;
1161 " %f: guessed profile. frequency %f, count %" PRId64
1162 " caller count %" PRId64
1163 " time w/o inlining %f, time with inlining %f"
1164 " overall growth %i (current) %i (original)"
1165 " %i (compensated)\n",
1166 badness
.to_double (),
1167 (double)edge
->frequency
/ CGRAPH_FREQ_BASE
,
1168 edge
->count
, caller
->count
,
1169 compute_uninlined_call_time (edge
,
1170 unspec_edge_time
).to_double (),
1171 compute_inlined_call_time (edge
, edge_time
).to_double (),
1172 estimate_growth (callee
),
1173 callee_info
->growth
, overall_growth
);
1176 /* When function local profile is not available or it does not give
1177 useful information (ie frequency is zero), base the cost on
1178 loop nest and overall size growth, so we optimize for overall number
1179 of functions fully inlined in program. */
1182 int nest
= MIN (inline_edge_summary (edge
)->loop_depth
, 8);
1185 /* Decrease badness if call is nested. */
1187 badness
= badness
>> nest
;
1189 badness
= badness
<< nest
;
1191 fprintf (dump_file
, " %f: no profile. nest %i\n",
1192 badness
.to_double (), nest
);
1194 gcc_checking_assert (badness
!= 0);
1196 if (edge
->recursive_p ())
1197 badness
= badness
.shift (badness
> 0 ? 4 : -4);
1198 if ((hints
& (INLINE_HINT_indirect_call
1199 | INLINE_HINT_loop_iterations
1200 | INLINE_HINT_array_index
1201 | INLINE_HINT_loop_stride
))
1202 || callee_info
->growth
<= 0)
1203 badness
= badness
.shift (badness
> 0 ? -2 : 2);
1204 if (hints
& (INLINE_HINT_same_scc
))
1205 badness
= badness
.shift (badness
> 0 ? 3 : -3);
1206 else if (hints
& (INLINE_HINT_in_scc
))
1207 badness
= badness
.shift (badness
> 0 ? 2 : -2);
1208 else if (hints
& (INLINE_HINT_cross_module
))
1209 badness
= badness
.shift (badness
> 0 ? 1 : -1);
1210 if (DECL_DISREGARD_INLINE_LIMITS (callee
->decl
))
1211 badness
= badness
.shift (badness
> 0 ? -4 : 4);
1212 else if ((hints
& INLINE_HINT_declared_inline
))
1213 badness
= badness
.shift (badness
> 0 ? -3 : 3);
1215 fprintf (dump_file
, " Adjusted by hints %f\n", badness
.to_double ());
1219 /* Recompute badness of EDGE and update its key in HEAP if needed. */
1221 update_edge_key (edge_heap_t
*heap
, struct cgraph_edge
*edge
)
1223 sreal badness
= edge_badness (edge
, false);
1226 edge_heap_node_t
*n
= (edge_heap_node_t
*) edge
->aux
;
1227 gcc_checking_assert (n
->get_data () == edge
);
1229 /* fibonacci_heap::replace_key does busy updating of the
1230 heap that is unnecesarily expensive.
1231 We do lazy increases: after extracting minimum if the key
1232 turns out to be out of date, it is re-inserted into heap
1233 with correct value. */
1234 if (badness
< n
->get_key ())
1236 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1239 " decreasing badness %s/%i -> %s/%i, %f"
1241 xstrdup_for_dump (edge
->caller
->name ()),
1242 edge
->caller
->order
,
1243 xstrdup_for_dump (edge
->callee
->name ()),
1244 edge
->callee
->order
,
1245 n
->get_key ().to_double (),
1246 badness
.to_double ());
1248 heap
->decrease_key (n
, badness
);
1253 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1256 " enqueuing call %s/%i -> %s/%i, badness %f\n",
1257 xstrdup_for_dump (edge
->caller
->name ()),
1258 edge
->caller
->order
,
1259 xstrdup_for_dump (edge
->callee
->name ()),
1260 edge
->callee
->order
,
1261 badness
.to_double ());
1263 edge
->aux
= heap
->insert (badness
, edge
);
1268 /* NODE was inlined.
1269 All caller edges needs to be resetted because
1270 size estimates change. Similarly callees needs reset
1271 because better context may be known. */
1274 reset_edge_caches (struct cgraph_node
*node
)
1276 struct cgraph_edge
*edge
;
1277 struct cgraph_edge
*e
= node
->callees
;
1278 struct cgraph_node
*where
= node
;
1279 struct ipa_ref
*ref
;
1281 if (where
->global
.inlined_to
)
1282 where
= where
->global
.inlined_to
;
1284 for (edge
= where
->callers
; edge
; edge
= edge
->next_caller
)
1285 if (edge
->inline_failed
)
1286 reset_edge_growth_cache (edge
);
1288 FOR_EACH_ALIAS (where
, ref
)
1289 reset_edge_caches (dyn_cast
<cgraph_node
*> (ref
->referring
));
1295 if (!e
->inline_failed
&& e
->callee
->callees
)
1296 e
= e
->callee
->callees
;
1299 if (e
->inline_failed
)
1300 reset_edge_growth_cache (e
);
1307 if (e
->caller
== node
)
1309 e
= e
->caller
->callers
;
1311 while (!e
->next_callee
);
1317 /* Recompute HEAP nodes for each of caller of NODE.
1318 UPDATED_NODES track nodes we already visited, to avoid redundant work.
1319 When CHECK_INLINABLITY_FOR is set, re-check for specified edge that
1320 it is inlinable. Otherwise check all edges. */
1323 update_caller_keys (edge_heap_t
*heap
, struct cgraph_node
*node
,
1324 bitmap updated_nodes
,
1325 struct cgraph_edge
*check_inlinablity_for
)
1327 struct cgraph_edge
*edge
;
1328 struct ipa_ref
*ref
;
1330 if ((!node
->alias
&& !inline_summaries
->get (node
)->inlinable
)
1331 || node
->global
.inlined_to
)
1333 if (!bitmap_set_bit (updated_nodes
, node
->uid
))
1336 FOR_EACH_ALIAS (node
, ref
)
1338 struct cgraph_node
*alias
= dyn_cast
<cgraph_node
*> (ref
->referring
);
1339 update_caller_keys (heap
, alias
, updated_nodes
, check_inlinablity_for
);
1342 for (edge
= node
->callers
; edge
; edge
= edge
->next_caller
)
1343 if (edge
->inline_failed
)
1345 if (!check_inlinablity_for
1346 || check_inlinablity_for
== edge
)
1348 if (can_inline_edge_p (edge
, false)
1349 && want_inline_small_function_p (edge
, false))
1350 update_edge_key (heap
, edge
);
1353 report_inline_failed_reason (edge
);
1354 heap
->delete_node ((edge_heap_node_t
*) edge
->aux
);
1359 update_edge_key (heap
, edge
);
1363 /* Recompute HEAP nodes for each uninlined call in NODE.
1364 This is used when we know that edge badnesses are going only to increase
1365 (we introduced new call site) and thus all we need is to insert newly
1366 created edges into heap. */
1369 update_callee_keys (edge_heap_t
*heap
, struct cgraph_node
*node
,
1370 bitmap updated_nodes
)
1372 struct cgraph_edge
*e
= node
->callees
;
1377 if (!e
->inline_failed
&& e
->callee
->callees
)
1378 e
= e
->callee
->callees
;
1381 enum availability avail
;
1382 struct cgraph_node
*callee
;
1383 /* We do not reset callee growth cache here. Since we added a new call,
1384 growth chould have just increased and consequentely badness metric
1385 don't need updating. */
1386 if (e
->inline_failed
1387 && (callee
= e
->callee
->ultimate_alias_target (&avail
, e
->caller
))
1388 && inline_summaries
->get (callee
)->inlinable
1389 && avail
>= AVAIL_AVAILABLE
1390 && !bitmap_bit_p (updated_nodes
, callee
->uid
))
1392 if (can_inline_edge_p (e
, false)
1393 && want_inline_small_function_p (e
, false))
1394 update_edge_key (heap
, e
);
1397 report_inline_failed_reason (e
);
1398 heap
->delete_node ((edge_heap_node_t
*) e
->aux
);
1408 if (e
->caller
== node
)
1410 e
= e
->caller
->callers
;
1412 while (!e
->next_callee
);
1418 /* Enqueue all recursive calls from NODE into priority queue depending on
1419 how likely we want to recursively inline the call. */
1422 lookup_recursive_calls (struct cgraph_node
*node
, struct cgraph_node
*where
,
1425 struct cgraph_edge
*e
;
1426 enum availability avail
;
1428 for (e
= where
->callees
; e
; e
= e
->next_callee
)
1429 if (e
->callee
== node
1430 || (e
->callee
->ultimate_alias_target (&avail
, e
->caller
) == node
1431 && avail
> AVAIL_INTERPOSABLE
))
1433 /* When profile feedback is available, prioritize by expected number
1435 heap
->insert (!max_count
? -e
->frequency
1436 : -(e
->count
/ ((max_count
+ (1<<24) - 1) / (1<<24))),
1439 for (e
= where
->callees
; e
; e
= e
->next_callee
)
1440 if (!e
->inline_failed
)
1441 lookup_recursive_calls (node
, e
->callee
, heap
);
1444 /* Decide on recursive inlining: in the case function has recursive calls,
1445 inline until body size reaches given argument. If any new indirect edges
1446 are discovered in the process, add them to *NEW_EDGES, unless NEW_EDGES
1450 recursive_inlining (struct cgraph_edge
*edge
,
1451 vec
<cgraph_edge
*> *new_edges
)
1453 int limit
= PARAM_VALUE (PARAM_MAX_INLINE_INSNS_RECURSIVE_AUTO
);
1454 edge_heap_t
heap (sreal::min ());
1455 struct cgraph_node
*node
;
1456 struct cgraph_edge
*e
;
1457 struct cgraph_node
*master_clone
= NULL
, *next
;
1461 node
= edge
->caller
;
1462 if (node
->global
.inlined_to
)
1463 node
= node
->global
.inlined_to
;
1465 if (DECL_DECLARED_INLINE_P (node
->decl
))
1466 limit
= PARAM_VALUE (PARAM_MAX_INLINE_INSNS_RECURSIVE
);
1468 /* Make sure that function is small enough to be considered for inlining. */
1469 if (estimate_size_after_inlining (node
, edge
) >= limit
)
1471 lookup_recursive_calls (node
, node
, &heap
);
1477 " Performing recursive inlining on %s\n",
1480 /* Do the inlining and update list of recursive call during process. */
1481 while (!heap
.empty ())
1483 struct cgraph_edge
*curr
= heap
.extract_min ();
1484 struct cgraph_node
*cnode
, *dest
= curr
->callee
;
1486 if (!can_inline_edge_p (curr
, true))
1489 /* MASTER_CLONE is produced in the case we already started modified
1490 the function. Be sure to redirect edge to the original body before
1491 estimating growths otherwise we will be seeing growths after inlining
1492 the already modified body. */
1495 curr
->redirect_callee (master_clone
);
1496 reset_edge_growth_cache (curr
);
1499 if (estimate_size_after_inlining (node
, curr
) > limit
)
1501 curr
->redirect_callee (dest
);
1502 reset_edge_growth_cache (curr
);
1507 for (cnode
= curr
->caller
;
1508 cnode
->global
.inlined_to
; cnode
= cnode
->callers
->caller
)
1510 == curr
->callee
->ultimate_alias_target ()->decl
)
1513 if (!want_inline_self_recursive_call_p (curr
, node
, false, depth
))
1515 curr
->redirect_callee (dest
);
1516 reset_edge_growth_cache (curr
);
1523 " Inlining call of depth %i", depth
);
1526 fprintf (dump_file
, " called approx. %.2f times per call",
1527 (double)curr
->count
/ node
->count
);
1529 fprintf (dump_file
, "\n");
1533 /* We need original clone to copy around. */
1534 master_clone
= node
->create_clone (node
->decl
, node
->count
,
1535 CGRAPH_FREQ_BASE
, false, vNULL
,
1537 for (e
= master_clone
->callees
; e
; e
= e
->next_callee
)
1538 if (!e
->inline_failed
)
1539 clone_inlined_nodes (e
, true, false, NULL
, CGRAPH_FREQ_BASE
);
1540 curr
->redirect_callee (master_clone
);
1541 reset_edge_growth_cache (curr
);
1544 inline_call (curr
, false, new_edges
, &overall_size
, true);
1545 lookup_recursive_calls (node
, curr
->callee
, &heap
);
1549 if (!heap
.empty () && dump_file
)
1550 fprintf (dump_file
, " Recursive inlining growth limit met.\n");
1557 "\n Inlined %i times, "
1558 "body grown from size %i to %i, time %f to %f\n", n
,
1559 inline_summaries
->get (master_clone
)->size
,
1560 inline_summaries
->get (node
)->size
,
1561 inline_summaries
->get (master_clone
)->time
.to_double (),
1562 inline_summaries
->get (node
)->time
.to_double ());
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 sreal 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 %s into %s which now has time %f and size %i, "
2059 "net change of %+i.\n",
2060 edge
->callee
->name (),
2061 edge
->caller
->name (),
2062 inline_summaries
->get (edge
->caller
)->time
.to_double (),
2063 inline_summaries
->get (edge
->caller
)->size
,
2064 overall_size
- old_size
);
2066 if (min_size
> overall_size
)
2068 min_size
= overall_size
;
2069 max_size
= compute_max_insns (min_size
);
2072 fprintf (dump_file
, "New minimal size reached: %i\n", min_size
);
2076 free_growth_caches ();
2079 "Unit growth for small function inlining: %i->%i (%i%%)\n",
2080 initial_size
, overall_size
,
2081 initial_size
? overall_size
* 100 / (initial_size
) - 100: 0);
2082 BITMAP_FREE (updated_nodes
);
2083 symtab
->remove_edge_removal_hook (edge_removal_hook_holder
);
2086 /* Flatten NODE. Performed both during early inlining and
2087 at IPA inlining time. */
2090 flatten_function (struct cgraph_node
*node
, bool early
)
2092 struct cgraph_edge
*e
;
2094 /* We shouldn't be called recursively when we are being processed. */
2095 gcc_assert (node
->aux
== NULL
);
2097 node
->aux
= (void *) node
;
2099 for (e
= node
->callees
; e
; e
= e
->next_callee
)
2101 struct cgraph_node
*orig_callee
;
2102 struct cgraph_node
*callee
= e
->callee
->ultimate_alias_target ();
2104 /* We've hit cycle? It is time to give up. */
2109 "Not inlining %s into %s to avoid cycle.\n",
2110 xstrdup_for_dump (callee
->name ()),
2111 xstrdup_for_dump (e
->caller
->name ()));
2112 e
->inline_failed
= CIF_RECURSIVE_INLINING
;
2116 /* When the edge is already inlined, we just need to recurse into
2117 it in order to fully flatten the leaves. */
2118 if (!e
->inline_failed
)
2120 flatten_function (callee
, early
);
2124 /* Flatten attribute needs to be processed during late inlining. For
2125 extra code quality we however do flattening during early optimization,
2128 ? !can_inline_edge_p (e
, true)
2129 : !can_early_inline_edge_p (e
))
2132 if (e
->recursive_p ())
2135 fprintf (dump_file
, "Not inlining: recursive call.\n");
2139 if (gimple_in_ssa_p (DECL_STRUCT_FUNCTION (node
->decl
))
2140 != gimple_in_ssa_p (DECL_STRUCT_FUNCTION (callee
->decl
)))
2143 fprintf (dump_file
, "Not inlining: SSA form does not match.\n");
2147 /* Inline the edge and flatten the inline clone. Avoid
2148 recursing through the original node if the node was cloned. */
2150 fprintf (dump_file
, " Inlining %s into %s.\n",
2151 xstrdup_for_dump (callee
->name ()),
2152 xstrdup_for_dump (e
->caller
->name ()));
2153 orig_callee
= callee
;
2154 inline_call (e
, true, NULL
, NULL
, false);
2155 if (e
->callee
!= orig_callee
)
2156 orig_callee
->aux
= (void *) node
;
2157 flatten_function (e
->callee
, early
);
2158 if (e
->callee
!= orig_callee
)
2159 orig_callee
->aux
= NULL
;
2163 if (!node
->global
.inlined_to
)
2164 inline_update_overall_summary (node
);
2167 /* Inline NODE to all callers. Worker for cgraph_for_node_and_aliases.
2168 DATA points to number of calls originally found so we avoid infinite
2172 inline_to_all_callers_1 (struct cgraph_node
*node
, void *data
,
2173 hash_set
<cgraph_node
*> *callers
)
2175 int *num_calls
= (int *)data
;
2176 bool callee_removed
= false;
2178 while (node
->callers
&& !node
->global
.inlined_to
)
2180 struct cgraph_node
*caller
= node
->callers
->caller
;
2182 if (!can_inline_edge_p (node
->callers
, true)
2183 || node
->callers
->recursive_p ())
2186 fprintf (dump_file
, "Uninlinable call found; giving up.\n");
2194 "\nInlining %s size %i.\n",
2196 inline_summaries
->get (node
)->size
);
2198 " Called once from %s %i insns.\n",
2199 node
->callers
->caller
->name (),
2200 inline_summaries
->get (node
->callers
->caller
)->size
);
2203 /* Remember which callers we inlined to, delaying updating the
2205 callers
->add (node
->callers
->caller
);
2206 inline_call (node
->callers
, true, NULL
, NULL
, false, &callee_removed
);
2209 " Inlined into %s which now has %i size\n",
2211 inline_summaries
->get (caller
)->size
);
2212 if (!(*num_calls
)--)
2215 fprintf (dump_file
, "New calls found; giving up.\n");
2216 return callee_removed
;
2224 /* Wrapper around inline_to_all_callers_1 doing delayed overall summary
2228 inline_to_all_callers (struct cgraph_node
*node
, void *data
)
2230 hash_set
<cgraph_node
*> callers
;
2231 bool res
= inline_to_all_callers_1 (node
, data
, &callers
);
2232 /* Perform the delayed update of the overall summary of all callers
2233 processed. This avoids quadratic behavior in the cases where
2234 we have a lot of calls to the same function. */
2235 for (hash_set
<cgraph_node
*>::iterator i
= callers
.begin ();
2236 i
!= callers
.end (); ++i
)
2237 inline_update_overall_summary (*i
);
2241 /* Output overall time estimate. */
2243 dump_overall_stats (void)
2245 sreal sum_weighted
= 0, sum
= 0;
2246 struct cgraph_node
*node
;
2248 FOR_EACH_DEFINED_FUNCTION (node
)
2249 if (!node
->global
.inlined_to
2252 sreal time
= inline_summaries
->get (node
)->time
;
2254 sum_weighted
+= time
* node
->count
;
2256 fprintf (dump_file
, "Overall time estimate: "
2257 "%f weighted by profile: "
2258 "%f\n", sum
.to_double (), sum_weighted
.to_double ());
2261 /* Output some useful stats about inlining. */
2264 dump_inline_stats (void)
2266 int64_t inlined_cnt
= 0, inlined_indir_cnt
= 0;
2267 int64_t inlined_virt_cnt
= 0, inlined_virt_indir_cnt
= 0;
2268 int64_t noninlined_cnt
= 0, noninlined_indir_cnt
= 0;
2269 int64_t noninlined_virt_cnt
= 0, noninlined_virt_indir_cnt
= 0;
2270 int64_t inlined_speculative
= 0, inlined_speculative_ply
= 0;
2271 int64_t indirect_poly_cnt
= 0, indirect_cnt
= 0;
2272 int64_t reason
[CIF_N_REASONS
][3];
2274 struct cgraph_node
*node
;
2276 memset (reason
, 0, sizeof (reason
));
2277 FOR_EACH_DEFINED_FUNCTION (node
)
2279 struct cgraph_edge
*e
;
2280 for (e
= node
->callees
; e
; e
= e
->next_callee
)
2282 if (e
->inline_failed
)
2284 reason
[(int) e
->inline_failed
][0] += e
->count
;
2285 reason
[(int) e
->inline_failed
][1] += e
->frequency
;
2286 reason
[(int) e
->inline_failed
][2] ++;
2287 if (DECL_VIRTUAL_P (e
->callee
->decl
))
2289 if (e
->indirect_inlining_edge
)
2290 noninlined_virt_indir_cnt
+= e
->count
;
2292 noninlined_virt_cnt
+= e
->count
;
2296 if (e
->indirect_inlining_edge
)
2297 noninlined_indir_cnt
+= e
->count
;
2299 noninlined_cnt
+= e
->count
;
2306 if (DECL_VIRTUAL_P (e
->callee
->decl
))
2307 inlined_speculative_ply
+= e
->count
;
2309 inlined_speculative
+= e
->count
;
2311 else if (DECL_VIRTUAL_P (e
->callee
->decl
))
2313 if (e
->indirect_inlining_edge
)
2314 inlined_virt_indir_cnt
+= e
->count
;
2316 inlined_virt_cnt
+= e
->count
;
2320 if (e
->indirect_inlining_edge
)
2321 inlined_indir_cnt
+= e
->count
;
2323 inlined_cnt
+= e
->count
;
2327 for (e
= node
->indirect_calls
; e
; e
= e
->next_callee
)
2328 if (e
->indirect_info
->polymorphic
)
2329 indirect_poly_cnt
+= e
->count
;
2331 indirect_cnt
+= e
->count
;
2336 "Inlined %" PRId64
" + speculative "
2337 "%" PRId64
" + speculative polymorphic "
2338 "%" PRId64
" + previously indirect "
2339 "%" PRId64
" + virtual "
2340 "%" PRId64
" + virtual and previously indirect "
2341 "%" PRId64
"\n" "Not inlined "
2342 "%" PRId64
" + previously indirect "
2343 "%" PRId64
" + virtual "
2344 "%" PRId64
" + virtual and previously indirect "
2345 "%" PRId64
" + stil indirect "
2346 "%" PRId64
" + still indirect polymorphic "
2347 "%" PRId64
"\n", inlined_cnt
,
2348 inlined_speculative
, inlined_speculative_ply
,
2349 inlined_indir_cnt
, inlined_virt_cnt
, inlined_virt_indir_cnt
,
2350 noninlined_cnt
, noninlined_indir_cnt
, noninlined_virt_cnt
,
2351 noninlined_virt_indir_cnt
, indirect_cnt
, indirect_poly_cnt
);
2353 "Removed speculations %" PRId64
"\n",
2356 dump_overall_stats ();
2357 fprintf (dump_file
, "\nWhy inlining failed?\n");
2358 for (i
= 0; i
< CIF_N_REASONS
; i
++)
2360 fprintf (dump_file
, "%-50s: %8i calls, %8i freq, %" PRId64
" count\n",
2361 cgraph_inline_failed_string ((cgraph_inline_failed_t
) i
),
2362 (int) reason
[i
][2], (int) reason
[i
][1], reason
[i
][0]);
2365 /* Decide on the inlining. We do so in the topological order to avoid
2366 expenses on updating data structures. */
2371 struct cgraph_node
*node
;
2373 struct cgraph_node
**order
;
2376 bool remove_functions
= false;
2381 cgraph_freq_base_rec
= (sreal
) 1 / (sreal
) CGRAPH_FREQ_BASE
;
2382 percent_rec
= (sreal
) 1 / (sreal
) 100;
2384 order
= XCNEWVEC (struct cgraph_node
*, symtab
->cgraph_count
);
2386 if (in_lto_p
&& optimize
)
2387 ipa_update_after_lto_read ();
2390 dump_inline_summaries (dump_file
);
2392 nnodes
= ipa_reverse_postorder (order
);
2394 FOR_EACH_FUNCTION (node
)
2398 /* Recompute the default reasons for inlining because they may have
2399 changed during merging. */
2402 for (cgraph_edge
*e
= node
->callees
; e
; e
= e
->next_callee
)
2404 gcc_assert (e
->inline_failed
);
2405 initialize_inline_failed (e
);
2407 for (cgraph_edge
*e
= node
->indirect_calls
; e
; e
= e
->next_callee
)
2408 initialize_inline_failed (e
);
2413 fprintf (dump_file
, "\nFlattening functions:\n");
2415 /* In the first pass handle functions to be flattened. Do this with
2416 a priority so none of our later choices will make this impossible. */
2417 for (i
= nnodes
- 1; i
>= 0; i
--)
2421 /* Handle nodes to be flattened.
2422 Ideally when processing callees we stop inlining at the
2423 entry of cycles, possibly cloning that entry point and
2424 try to flatten itself turning it into a self-recursive
2426 if (lookup_attribute ("flatten",
2427 DECL_ATTRIBUTES (node
->decl
)) != NULL
)
2431 "Flattening %s\n", node
->name ());
2432 flatten_function (node
, false);
2436 dump_overall_stats ();
2438 inline_small_functions ();
2440 gcc_assert (symtab
->state
== IPA_SSA
);
2441 symtab
->state
= IPA_SSA_AFTER_INLINING
;
2442 /* Do first after-inlining removal. We want to remove all "stale" extern
2443 inline functions and virtual functions so we really know what is called
2445 symtab
->remove_unreachable_nodes (dump_file
);
2448 /* Inline functions with a property that after inlining into all callers the
2449 code size will shrink because the out-of-line copy is eliminated.
2450 We do this regardless on the callee size as long as function growth limits
2454 "\nDeciding on functions to be inlined into all callers and "
2455 "removing useless speculations:\n");
2457 /* Inlining one function called once has good chance of preventing
2458 inlining other function into the same callee. Ideally we should
2459 work in priority order, but probably inlining hot functions first
2460 is good cut without the extra pain of maintaining the queue.
2462 ??? this is not really fitting the bill perfectly: inlining function
2463 into callee often leads to better optimization of callee due to
2464 increased context for optimization.
2465 For example if main() function calls a function that outputs help
2466 and then function that does the main optmization, we should inline
2467 the second with priority even if both calls are cold by themselves.
2469 We probably want to implement new predicate replacing our use of
2470 maybe_hot_edge interpreted as maybe_hot_edge || callee is known
2472 for (cold
= 0; cold
<= 1; cold
++)
2474 FOR_EACH_DEFINED_FUNCTION (node
)
2476 struct cgraph_edge
*edge
, *next
;
2479 for (edge
= node
->callees
; edge
; edge
= next
)
2481 next
= edge
->next_callee
;
2482 if (edge
->speculative
&& !speculation_useful_p (edge
, false))
2484 edge
->resolve_speculation ();
2485 spec_rem
+= edge
->count
;
2487 remove_functions
= true;
2492 struct cgraph_node
*where
= node
->global
.inlined_to
2493 ? node
->global
.inlined_to
: node
;
2494 reset_edge_caches (where
);
2495 inline_update_overall_summary (where
);
2497 if (want_inline_function_to_all_callers_p (node
, cold
))
2500 node
->call_for_symbol_and_aliases (sum_callers
, &num_calls
,
2502 while (node
->call_for_symbol_and_aliases
2503 (inline_to_all_callers
, &num_calls
, true))
2505 remove_functions
= true;
2510 /* Free ipa-prop structures if they are no longer needed. */
2512 ipa_free_all_structures_after_iinln ();
2517 "\nInlined %i calls, eliminated %i functions\n\n",
2518 ncalls_inlined
, nfunctions_inlined
);
2519 dump_inline_stats ();
2523 dump_inline_summaries (dump_file
);
2524 /* In WPA we use inline summaries for partitioning process. */
2526 inline_free_summary ();
2527 return remove_functions
? TODO_remove_functions
: 0;
2530 /* Inline always-inline function calls in NODE. */
2533 inline_always_inline_functions (struct cgraph_node
*node
)
2535 struct cgraph_edge
*e
;
2536 bool inlined
= false;
2538 for (e
= node
->callees
; e
; e
= e
->next_callee
)
2540 struct cgraph_node
*callee
= e
->callee
->ultimate_alias_target ();
2541 if (!DECL_DISREGARD_INLINE_LIMITS (callee
->decl
))
2544 if (e
->recursive_p ())
2547 fprintf (dump_file
, " Not inlining recursive call to %s.\n",
2548 e
->callee
->name ());
2549 e
->inline_failed
= CIF_RECURSIVE_INLINING
;
2553 if (!can_early_inline_edge_p (e
))
2555 /* Set inlined to true if the callee is marked "always_inline" but
2556 is not inlinable. This will allow flagging an error later in
2557 expand_call_inline in tree-inline.c. */
2558 if (lookup_attribute ("always_inline",
2559 DECL_ATTRIBUTES (callee
->decl
)) != NULL
)
2565 fprintf (dump_file
, " Inlining %s into %s (always_inline).\n",
2566 xstrdup_for_dump (e
->callee
->name ()),
2567 xstrdup_for_dump (e
->caller
->name ()));
2568 inline_call (e
, true, NULL
, NULL
, false);
2572 inline_update_overall_summary (node
);
2577 /* Decide on the inlining. We do so in the topological order to avoid
2578 expenses on updating data structures. */
2581 early_inline_small_functions (struct cgraph_node
*node
)
2583 struct cgraph_edge
*e
;
2584 bool inlined
= false;
2586 for (e
= node
->callees
; e
; e
= e
->next_callee
)
2588 struct cgraph_node
*callee
= e
->callee
->ultimate_alias_target ();
2589 if (!inline_summaries
->get (callee
)->inlinable
2590 || !e
->inline_failed
)
2593 /* Do not consider functions not declared inline. */
2594 if (!DECL_DECLARED_INLINE_P (callee
->decl
)
2595 && !opt_for_fn (node
->decl
, flag_inline_small_functions
)
2596 && !opt_for_fn (node
->decl
, flag_inline_functions
))
2600 fprintf (dump_file
, "Considering inline candidate %s.\n",
2603 if (!can_early_inline_edge_p (e
))
2606 if (e
->recursive_p ())
2609 fprintf (dump_file
, " Not inlining: recursive call.\n");
2613 if (!want_early_inline_function_p (e
))
2617 fprintf (dump_file
, " Inlining %s into %s.\n",
2618 xstrdup_for_dump (callee
->name ()),
2619 xstrdup_for_dump (e
->caller
->name ()));
2620 inline_call (e
, true, NULL
, NULL
, false);
2625 inline_update_overall_summary (node
);
2631 early_inliner (function
*fun
)
2633 struct cgraph_node
*node
= cgraph_node::get (current_function_decl
);
2634 struct cgraph_edge
*edge
;
2635 unsigned int todo
= 0;
2637 bool inlined
= false;
2642 /* Do nothing if datastructures for ipa-inliner are already computed. This
2643 happens when some pass decides to construct new function and
2644 cgraph_add_new_function calls lowering passes and early optimization on
2645 it. This may confuse ourself when early inliner decide to inline call to
2646 function clone, because function clones don't have parameter list in
2647 ipa-prop matching their signature. */
2648 if (ipa_node_params_sum
)
2653 node
->remove_all_references ();
2655 /* Rebuild this reference because it dosn't depend on
2656 function's body and it's required to pass cgraph_node
2658 if (node
->instrumented_version
2659 && !node
->instrumentation_clone
)
2660 node
->create_reference (node
->instrumented_version
, IPA_REF_CHKP
, NULL
);
2662 /* Even when not optimizing or not inlining inline always-inline
2664 inlined
= inline_always_inline_functions (node
);
2668 || !flag_early_inlining
2669 /* Never inline regular functions into always-inline functions
2670 during incremental inlining. This sucks as functions calling
2671 always inline functions will get less optimized, but at the
2672 same time inlining of functions calling always inline
2673 function into an always inline function might introduce
2674 cycles of edges to be always inlined in the callgraph.
2676 We might want to be smarter and just avoid this type of inlining. */
2677 || (DECL_DISREGARD_INLINE_LIMITS (node
->decl
)
2678 && lookup_attribute ("always_inline",
2679 DECL_ATTRIBUTES (node
->decl
))))
2681 else if (lookup_attribute ("flatten",
2682 DECL_ATTRIBUTES (node
->decl
)) != NULL
)
2684 /* When the function is marked to be flattened, recursively inline
2688 "Flattening %s\n", node
->name ());
2689 flatten_function (node
, true);
2694 /* If some always_inline functions was inlined, apply the changes.
2695 This way we will not account always inline into growth limits and
2696 moreover we will inline calls from always inlines that we skipped
2697 previously because of conditional above. */
2700 timevar_push (TV_INTEGRATION
);
2701 todo
|= optimize_inline_calls (current_function_decl
);
2702 /* optimize_inline_calls call above might have introduced new
2703 statements that don't have inline parameters computed. */
2704 for (edge
= node
->callees
; edge
; edge
= edge
->next_callee
)
2706 if (inline_edge_summary_vec
.length () > (unsigned) edge
->uid
)
2708 struct inline_edge_summary
*es
= inline_edge_summary (edge
);
2710 = estimate_num_insns (edge
->call_stmt
, &eni_size_weights
);
2712 = estimate_num_insns (edge
->call_stmt
, &eni_time_weights
);
2715 inline_update_overall_summary (node
);
2717 timevar_pop (TV_INTEGRATION
);
2719 /* We iterate incremental inlining to get trivial cases of indirect
2721 while (iterations
< PARAM_VALUE (PARAM_EARLY_INLINER_MAX_ITERATIONS
)
2722 && early_inline_small_functions (node
))
2724 timevar_push (TV_INTEGRATION
);
2725 todo
|= optimize_inline_calls (current_function_decl
);
2727 /* Technically we ought to recompute inline parameters so the new
2728 iteration of early inliner works as expected. We however have
2729 values approximately right and thus we only need to update edge
2730 info that might be cleared out for newly discovered edges. */
2731 for (edge
= node
->callees
; edge
; edge
= edge
->next_callee
)
2733 /* We have no summary for new bound store calls yet. */
2734 if (inline_edge_summary_vec
.length () > (unsigned)edge
->uid
)
2736 struct inline_edge_summary
*es
= inline_edge_summary (edge
);
2738 = estimate_num_insns (edge
->call_stmt
, &eni_size_weights
);
2740 = estimate_num_insns (edge
->call_stmt
, &eni_time_weights
);
2742 if (edge
->callee
->decl
2743 && !gimple_check_call_matching_types (
2744 edge
->call_stmt
, edge
->callee
->decl
, false))
2746 edge
->inline_failed
= CIF_MISMATCHED_ARGUMENTS
;
2747 edge
->call_stmt_cannot_inline_p
= true;
2750 if (iterations
< PARAM_VALUE (PARAM_EARLY_INLINER_MAX_ITERATIONS
) - 1)
2751 inline_update_overall_summary (node
);
2752 timevar_pop (TV_INTEGRATION
);
2757 fprintf (dump_file
, "Iterations: %i\n", iterations
);
2762 timevar_push (TV_INTEGRATION
);
2763 todo
|= optimize_inline_calls (current_function_decl
);
2764 timevar_pop (TV_INTEGRATION
);
2767 fun
->always_inline_functions_inlined
= true;
2772 /* Do inlining of small functions. Doing so early helps profiling and other
2773 passes to be somewhat more effective and avoids some code duplication in
2774 later real inlining pass for testcases with very many function calls. */
2778 const pass_data pass_data_early_inline
=
2780 GIMPLE_PASS
, /* type */
2781 "einline", /* name */
2782 OPTGROUP_INLINE
, /* optinfo_flags */
2783 TV_EARLY_INLINING
, /* tv_id */
2784 PROP_ssa
, /* properties_required */
2785 0, /* properties_provided */
2786 0, /* properties_destroyed */
2787 0, /* todo_flags_start */
2788 0, /* todo_flags_finish */
2791 class pass_early_inline
: public gimple_opt_pass
2794 pass_early_inline (gcc::context
*ctxt
)
2795 : gimple_opt_pass (pass_data_early_inline
, ctxt
)
2798 /* opt_pass methods: */
2799 virtual unsigned int execute (function
*);
2801 }; // class pass_early_inline
2804 pass_early_inline::execute (function
*fun
)
2806 return early_inliner (fun
);
2812 make_pass_early_inline (gcc::context
*ctxt
)
2814 return new pass_early_inline (ctxt
);
2819 const pass_data pass_data_ipa_inline
=
2821 IPA_PASS
, /* type */
2822 "inline", /* name */
2823 OPTGROUP_INLINE
, /* optinfo_flags */
2824 TV_IPA_INLINING
, /* tv_id */
2825 0, /* properties_required */
2826 0, /* properties_provided */
2827 0, /* properties_destroyed */
2828 0, /* todo_flags_start */
2829 ( TODO_dump_symtab
), /* todo_flags_finish */
2832 class pass_ipa_inline
: public ipa_opt_pass_d
2835 pass_ipa_inline (gcc::context
*ctxt
)
2836 : ipa_opt_pass_d (pass_data_ipa_inline
, ctxt
,
2837 inline_generate_summary
, /* generate_summary */
2838 inline_write_summary
, /* write_summary */
2839 inline_read_summary
, /* read_summary */
2840 NULL
, /* write_optimization_summary */
2841 NULL
, /* read_optimization_summary */
2842 NULL
, /* stmt_fixup */
2843 0, /* function_transform_todo_flags_start */
2844 inline_transform
, /* function_transform */
2845 NULL
) /* variable_transform */
2848 /* opt_pass methods: */
2849 virtual unsigned int execute (function
*) { return ipa_inline (); }
2851 }; // class pass_ipa_inline
2856 make_pass_ipa_inline (gcc::context
*ctxt
)
2858 return new pass_ipa_inline (ctxt
);