1 /* Inlining decision heuristics.
2 Copyright (C) 2003-2014 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"
97 #include "trans-mem.h"
99 #include "tree-inline.h"
100 #include "langhooks.h"
102 #include "diagnostic.h"
103 #include "gimple-pretty-print.h"
107 #include "tree-pass.h"
108 #include "coverage.h"
111 #include "basic-block.h"
112 #include "tree-ssa-alias.h"
113 #include "internal-fn.h"
114 #include "gimple-expr.h"
117 #include "gimple-ssa.h"
118 #include "ipa-prop.h"
121 #include "ipa-inline.h"
122 #include "ipa-utils.h"
125 #include "builtins.h"
127 /* Statistics we collect about inlining algorithm. */
128 static int overall_size
;
129 static gcov_type max_count
;
130 static sreal max_count_real
, max_relbenefit_real
, half_int_min_real
;
131 static gcov_type spec_rem
;
133 /* Return false when inlining edge E would lead to violating
134 limits on function unit growth or stack usage growth.
136 The relative function body growth limit is present generally
137 to avoid problems with non-linear behavior of the compiler.
138 To allow inlining huge functions into tiny wrapper, the limit
139 is always based on the bigger of the two functions considered.
141 For stack growth limits we always base the growth in stack usage
142 of the callers. We want to prevent applications from segfaulting
143 on stack overflow when functions with huge stack frames gets
147 caller_growth_limits (struct cgraph_edge
*e
)
149 struct cgraph_node
*to
= e
->caller
;
150 struct cgraph_node
*what
= cgraph_function_or_thunk_node (e
->callee
, NULL
);
153 HOST_WIDE_INT stack_size_limit
= 0, inlined_stack
;
154 struct inline_summary
*info
, *what_info
, *outer_info
= inline_summary (to
);
156 /* Look for function e->caller is inlined to. While doing
157 so work out the largest function body on the way. As
158 described above, we want to base our function growth
159 limits based on that. Not on the self size of the
160 outer function, not on the self size of inline code
161 we immediately inline to. This is the most relaxed
162 interpretation of the rule "do not grow large functions
163 too much in order to prevent compiler from exploding". */
166 info
= inline_summary (to
);
167 if (limit
< info
->self_size
)
168 limit
= info
->self_size
;
169 if (stack_size_limit
< info
->estimated_self_stack_size
)
170 stack_size_limit
= info
->estimated_self_stack_size
;
171 if (to
->global
.inlined_to
)
172 to
= to
->callers
->caller
;
177 what_info
= inline_summary (what
);
179 if (limit
< what_info
->self_size
)
180 limit
= what_info
->self_size
;
182 limit
+= limit
* PARAM_VALUE (PARAM_LARGE_FUNCTION_GROWTH
) / 100;
184 /* Check the size after inlining against the function limits. But allow
185 the function to shrink if it went over the limits by forced inlining. */
186 newsize
= estimate_size_after_inlining (to
, e
);
187 if (newsize
>= info
->size
188 && newsize
> PARAM_VALUE (PARAM_LARGE_FUNCTION_INSNS
)
191 e
->inline_failed
= CIF_LARGE_FUNCTION_GROWTH_LIMIT
;
195 if (!what_info
->estimated_stack_size
)
198 /* FIXME: Stack size limit often prevents inlining in Fortran programs
199 due to large i/o datastructures used by the Fortran front-end.
200 We ought to ignore this limit when we know that the edge is executed
201 on every invocation of the caller (i.e. its call statement dominates
202 exit block). We do not track this information, yet. */
203 stack_size_limit
+= ((gcov_type
)stack_size_limit
204 * PARAM_VALUE (PARAM_STACK_FRAME_GROWTH
) / 100);
206 inlined_stack
= (outer_info
->stack_frame_offset
207 + outer_info
->estimated_self_stack_size
208 + what_info
->estimated_stack_size
);
209 /* Check new stack consumption with stack consumption at the place
211 if (inlined_stack
> stack_size_limit
212 /* If function already has large stack usage from sibling
213 inline call, we can inline, too.
214 This bit overoptimistically assume that we are good at stack
216 && inlined_stack
> info
->estimated_stack_size
217 && inlined_stack
> PARAM_VALUE (PARAM_LARGE_STACK_FRAME
))
219 e
->inline_failed
= CIF_LARGE_STACK_FRAME_GROWTH_LIMIT
;
225 /* Dump info about why inlining has failed. */
228 report_inline_failed_reason (struct cgraph_edge
*e
)
232 fprintf (dump_file
, " not inlinable: %s/%i -> %s/%i, %s\n",
233 xstrdup (e
->caller
->name ()), e
->caller
->order
,
234 xstrdup (e
->callee
->name ()), e
->callee
->order
,
235 cgraph_inline_failed_string (e
->inline_failed
));
239 /* Decide whether sanitizer-related attributes allow inlining. */
242 sanitize_attrs_match_for_inline_p (const_tree caller
, const_tree callee
)
244 /* Don't care if sanitizer is disabled */
245 if (!(flag_sanitize
& SANITIZE_ADDRESS
))
248 if (!caller
|| !callee
)
251 return !!lookup_attribute ("no_sanitize_address",
252 DECL_ATTRIBUTES (caller
)) ==
253 !!lookup_attribute ("no_sanitize_address",
254 DECL_ATTRIBUTES (callee
));
257 /* Decide if we can inline the edge and possibly update
258 inline_failed reason.
259 We check whether inlining is possible at all and whether
260 caller growth limits allow doing so.
262 if REPORT is true, output reason to the dump file.
264 if DISREGARD_LIMITS is true, ignore size limits.*/
267 can_inline_edge_p (struct cgraph_edge
*e
, bool report
,
268 bool disregard_limits
= false)
270 bool inlinable
= true;
271 enum availability avail
;
272 struct cgraph_node
*callee
273 = cgraph_function_or_thunk_node (e
->callee
, &avail
);
274 tree caller_tree
= DECL_FUNCTION_SPECIFIC_OPTIMIZATION (e
->caller
->decl
);
276 = callee
? DECL_FUNCTION_SPECIFIC_OPTIMIZATION (callee
->decl
) : NULL
;
277 struct function
*caller_cfun
= DECL_STRUCT_FUNCTION (e
->caller
->decl
);
278 struct function
*callee_cfun
279 = callee
? DECL_STRUCT_FUNCTION (callee
->decl
) : NULL
;
281 if (!caller_cfun
&& e
->caller
->clone_of
)
282 caller_cfun
= DECL_STRUCT_FUNCTION (e
->caller
->clone_of
->decl
);
284 if (!callee_cfun
&& callee
&& callee
->clone_of
)
285 callee_cfun
= DECL_STRUCT_FUNCTION (callee
->clone_of
->decl
);
287 gcc_assert (e
->inline_failed
);
289 if (!callee
|| !callee
->definition
)
291 e
->inline_failed
= CIF_BODY_NOT_AVAILABLE
;
294 else if (callee
->calls_comdat_local
)
296 e
->inline_failed
= CIF_USES_COMDAT_LOCAL
;
299 else if (!inline_summary (callee
)->inlinable
300 || (caller_cfun
&& fn_contains_cilk_spawn_p (caller_cfun
)))
302 e
->inline_failed
= CIF_FUNCTION_NOT_INLINABLE
;
305 else if (avail
<= AVAIL_OVERWRITABLE
)
307 e
->inline_failed
= CIF_OVERWRITABLE
;
310 else if (e
->call_stmt_cannot_inline_p
)
312 if (e
->inline_failed
!= CIF_FUNCTION_NOT_OPTIMIZED
)
313 e
->inline_failed
= CIF_MISMATCHED_ARGUMENTS
;
316 /* Don't inline if the functions have different EH personalities. */
317 else if (DECL_FUNCTION_PERSONALITY (e
->caller
->decl
)
318 && DECL_FUNCTION_PERSONALITY (callee
->decl
)
319 && (DECL_FUNCTION_PERSONALITY (e
->caller
->decl
)
320 != DECL_FUNCTION_PERSONALITY (callee
->decl
)))
322 e
->inline_failed
= CIF_EH_PERSONALITY
;
325 /* TM pure functions should not be inlined into non-TM_pure
327 else if (is_tm_pure (callee
->decl
)
328 && !is_tm_pure (e
->caller
->decl
))
330 e
->inline_failed
= CIF_UNSPECIFIED
;
333 /* Don't inline if the callee can throw non-call exceptions but the
335 FIXME: this is obviously wrong for LTO where STRUCT_FUNCTION is missing.
336 Move the flag into cgraph node or mirror it in the inline summary. */
337 else if (callee_cfun
&& callee_cfun
->can_throw_non_call_exceptions
338 && !(caller_cfun
&& caller_cfun
->can_throw_non_call_exceptions
))
340 e
->inline_failed
= CIF_NON_CALL_EXCEPTIONS
;
343 /* Check compatibility of target optimization options. */
344 else if (!targetm
.target_option
.can_inline_p (e
->caller
->decl
,
347 e
->inline_failed
= CIF_TARGET_OPTION_MISMATCH
;
350 /* Don't inline a function with mismatched sanitization attributes. */
351 else if (!sanitize_attrs_match_for_inline_p (e
->caller
->decl
, callee
->decl
))
353 e
->inline_failed
= CIF_ATTRIBUTE_MISMATCH
;
356 /* Check if caller growth allows the inlining. */
357 else if (!DECL_DISREGARD_INLINE_LIMITS (callee
->decl
)
359 && !lookup_attribute ("flatten",
361 (e
->caller
->global
.inlined_to
362 ? e
->caller
->global
.inlined_to
->decl
364 && !caller_growth_limits (e
))
366 /* Don't inline a function with a higher optimization level than the
367 caller. FIXME: this is really just tip of iceberg of handling
368 optimization attribute. */
369 else if (caller_tree
!= callee_tree
)
371 struct cl_optimization
*caller_opt
372 = TREE_OPTIMIZATION ((caller_tree
)
374 : optimization_default_node
);
376 struct cl_optimization
*callee_opt
377 = TREE_OPTIMIZATION ((callee_tree
)
379 : optimization_default_node
);
381 if (((caller_opt
->x_optimize
> callee_opt
->x_optimize
)
382 || (caller_opt
->x_optimize_size
!= callee_opt
->x_optimize_size
))
383 /* gcc.dg/pr43564.c. Look at forced inline even in -O0. */
384 && !DECL_DISREGARD_INLINE_LIMITS (e
->callee
->decl
))
386 e
->inline_failed
= CIF_OPTIMIZATION_MISMATCH
;
391 if (!inlinable
&& report
)
392 report_inline_failed_reason (e
);
397 /* Return true if the edge E is inlinable during early inlining. */
400 can_early_inline_edge_p (struct cgraph_edge
*e
)
402 struct cgraph_node
*callee
= cgraph_function_or_thunk_node (e
->callee
,
404 /* Early inliner might get called at WPA stage when IPA pass adds new
405 function. In this case we can not really do any of early inlining
406 because function bodies are missing. */
407 if (!gimple_has_body_p (callee
->decl
))
409 e
->inline_failed
= CIF_BODY_NOT_AVAILABLE
;
412 /* In early inliner some of callees may not be in SSA form yet
413 (i.e. the callgraph is cyclic and we did not process
414 the callee by early inliner, yet). We don't have CIF code for this
415 case; later we will re-do the decision in the real inliner. */
416 if (!gimple_in_ssa_p (DECL_STRUCT_FUNCTION (e
->caller
->decl
))
417 || !gimple_in_ssa_p (DECL_STRUCT_FUNCTION (callee
->decl
)))
420 fprintf (dump_file
, " edge not inlinable: not in SSA form\n");
423 if (!can_inline_edge_p (e
, true))
429 /* Return number of calls in N. Ignore cheap builtins. */
432 num_calls (struct cgraph_node
*n
)
434 struct cgraph_edge
*e
;
437 for (e
= n
->callees
; e
; e
= e
->next_callee
)
438 if (!is_inexpensive_builtin (e
->callee
->decl
))
444 /* Return true if we are interested in inlining small function. */
447 want_early_inline_function_p (struct cgraph_edge
*e
)
449 bool want_inline
= true;
450 struct cgraph_node
*callee
= cgraph_function_or_thunk_node (e
->callee
, NULL
);
452 if (DECL_DISREGARD_INLINE_LIMITS (callee
->decl
))
454 else if (!DECL_DECLARED_INLINE_P (callee
->decl
)
455 && !flag_inline_small_functions
)
457 e
->inline_failed
= CIF_FUNCTION_NOT_INLINE_CANDIDATE
;
458 report_inline_failed_reason (e
);
463 int growth
= estimate_edge_growth (e
);
468 else if (!cgraph_maybe_hot_edge_p (e
)
472 fprintf (dump_file
, " will not early inline: %s/%i->%s/%i, "
473 "call is cold and code would grow by %i\n",
474 xstrdup (e
->caller
->name ()),
476 xstrdup (callee
->name ()), callee
->order
,
480 else if (growth
> PARAM_VALUE (PARAM_EARLY_INLINING_INSNS
))
483 fprintf (dump_file
, " will not early inline: %s/%i->%s/%i, "
484 "growth %i exceeds --param early-inlining-insns\n",
485 xstrdup (e
->caller
->name ()),
487 xstrdup (callee
->name ()), callee
->order
,
491 else if ((n
= num_calls (callee
)) != 0
492 && growth
* (n
+ 1) > PARAM_VALUE (PARAM_EARLY_INLINING_INSNS
))
495 fprintf (dump_file
, " will not early inline: %s/%i->%s/%i, "
496 "growth %i exceeds --param early-inlining-insns "
497 "divided by number of calls\n",
498 xstrdup (e
->caller
->name ()),
500 xstrdup (callee
->name ()), callee
->order
,
508 /* Compute time of the edge->caller + edge->callee execution when inlining
512 compute_uninlined_call_time (struct inline_summary
*callee_info
,
513 struct cgraph_edge
*edge
)
515 gcov_type uninlined_call_time
=
516 RDIV ((gcov_type
)callee_info
->time
* MAX (edge
->frequency
, 1),
518 gcov_type caller_time
= inline_summary (edge
->caller
->global
.inlined_to
519 ? edge
->caller
->global
.inlined_to
520 : edge
->caller
)->time
;
521 return uninlined_call_time
+ caller_time
;
524 /* Same as compute_uinlined_call_time but compute time when inlining
528 compute_inlined_call_time (struct cgraph_edge
*edge
,
531 gcov_type caller_time
= inline_summary (edge
->caller
->global
.inlined_to
532 ? edge
->caller
->global
.inlined_to
533 : edge
->caller
)->time
;
534 gcov_type time
= (caller_time
535 + RDIV (((gcov_type
) edge_time
536 - inline_edge_summary (edge
)->call_stmt_time
)
537 * MAX (edge
->frequency
, 1), CGRAPH_FREQ_BASE
));
538 /* Possible one roundoff error, but watch for overflows. */
539 gcc_checking_assert (time
>= INT_MIN
/ 2);
545 /* Return true if the speedup for inlining E is bigger than
546 PARAM_MAX_INLINE_MIN_SPEEDUP. */
549 big_speedup_p (struct cgraph_edge
*e
)
551 gcov_type time
= compute_uninlined_call_time (inline_summary (e
->callee
),
553 gcov_type inlined_time
= compute_inlined_call_time (e
,
554 estimate_edge_time (e
));
555 if (time
- inlined_time
556 > RDIV (time
* PARAM_VALUE (PARAM_INLINE_MIN_SPEEDUP
), 100))
561 /* Return true if we are interested in inlining small function.
562 When REPORT is true, report reason to dump file. */
565 want_inline_small_function_p (struct cgraph_edge
*e
, bool report
)
567 bool want_inline
= true;
568 struct cgraph_node
*callee
= cgraph_function_or_thunk_node (e
->callee
, NULL
);
570 if (DECL_DISREGARD_INLINE_LIMITS (callee
->decl
))
572 else if (!DECL_DECLARED_INLINE_P (callee
->decl
)
573 && !flag_inline_small_functions
)
575 e
->inline_failed
= CIF_FUNCTION_NOT_INLINE_CANDIDATE
;
578 /* Do fast and conservative check if the function can be good
579 inline cnadidate. At themoment we allow inline hints to
580 promote non-inline function to inline and we increase
581 MAX_INLINE_INSNS_SINGLE 16fold for inline functions. */
582 else if ((!DECL_DECLARED_INLINE_P (callee
->decl
)
583 && (!e
->count
|| !cgraph_maybe_hot_edge_p (e
)))
584 && inline_summary (callee
)->min_size
- inline_edge_summary (e
)->call_stmt_size
585 > MAX (MAX_INLINE_INSNS_SINGLE
, MAX_INLINE_INSNS_AUTO
))
587 e
->inline_failed
= CIF_MAX_INLINE_INSNS_AUTO_LIMIT
;
590 else if ((DECL_DECLARED_INLINE_P (callee
->decl
) || e
->count
)
591 && inline_summary (callee
)->min_size
- inline_edge_summary (e
)->call_stmt_size
592 > 16 * MAX_INLINE_INSNS_SINGLE
)
594 e
->inline_failed
= (DECL_DECLARED_INLINE_P (callee
->decl
)
595 ? CIF_MAX_INLINE_INSNS_SINGLE_LIMIT
596 : CIF_MAX_INLINE_INSNS_AUTO_LIMIT
);
601 int growth
= estimate_edge_growth (e
);
602 inline_hints hints
= estimate_edge_hints (e
);
603 bool big_speedup
= big_speedup_p (e
);
607 /* Apply MAX_INLINE_INSNS_SINGLE limit. Do not do so when
608 hints suggests that inlining given function is very profitable. */
609 else if (DECL_DECLARED_INLINE_P (callee
->decl
)
610 && growth
>= MAX_INLINE_INSNS_SINGLE
612 && !(hints
& (INLINE_HINT_indirect_call
613 | INLINE_HINT_known_hot
614 | INLINE_HINT_loop_iterations
615 | INLINE_HINT_array_index
616 | INLINE_HINT_loop_stride
)))
617 || growth
>= MAX_INLINE_INSNS_SINGLE
* 16))
619 e
->inline_failed
= CIF_MAX_INLINE_INSNS_SINGLE_LIMIT
;
622 else if (!DECL_DECLARED_INLINE_P (callee
->decl
)
623 && !flag_inline_functions
)
625 /* growth_likely_positive is expensive, always test it last. */
626 if (growth
>= MAX_INLINE_INSNS_SINGLE
627 || growth_likely_positive (callee
, growth
))
629 e
->inline_failed
= CIF_NOT_DECLARED_INLINED
;
633 /* Apply MAX_INLINE_INSNS_AUTO limit for functions not declared inline
634 Upgrade it to MAX_INLINE_INSNS_SINGLE when hints suggests that
635 inlining given function is very profitable. */
636 else if (!DECL_DECLARED_INLINE_P (callee
->decl
)
638 && !(hints
& INLINE_HINT_known_hot
)
639 && growth
>= ((hints
& (INLINE_HINT_indirect_call
640 | INLINE_HINT_loop_iterations
641 | INLINE_HINT_array_index
642 | INLINE_HINT_loop_stride
))
643 ? MAX (MAX_INLINE_INSNS_AUTO
,
644 MAX_INLINE_INSNS_SINGLE
)
645 : MAX_INLINE_INSNS_AUTO
))
647 /* growth_likely_positive is expensive, always test it last. */
648 if (growth
>= MAX_INLINE_INSNS_SINGLE
649 || growth_likely_positive (callee
, growth
))
651 e
->inline_failed
= CIF_MAX_INLINE_INSNS_AUTO_LIMIT
;
655 /* If call is cold, do not inline when function body would grow. */
656 else if (!cgraph_maybe_hot_edge_p (e
)
657 && (growth
>= MAX_INLINE_INSNS_SINGLE
658 || growth_likely_positive (callee
, growth
)))
660 e
->inline_failed
= CIF_UNLIKELY_CALL
;
664 if (!want_inline
&& report
)
665 report_inline_failed_reason (e
);
669 /* EDGE is self recursive edge.
670 We hand two cases - when function A is inlining into itself
671 or when function A is being inlined into another inliner copy of function
674 In first case OUTER_NODE points to the toplevel copy of A, while
675 in the second case OUTER_NODE points to the outermost copy of A in B.
677 In both cases we want to be extra selective since
678 inlining the call will just introduce new recursive calls to appear. */
681 want_inline_self_recursive_call_p (struct cgraph_edge
*edge
,
682 struct cgraph_node
*outer_node
,
686 char const *reason
= NULL
;
687 bool want_inline
= true;
688 int caller_freq
= CGRAPH_FREQ_BASE
;
689 int max_depth
= PARAM_VALUE (PARAM_MAX_INLINE_RECURSIVE_DEPTH_AUTO
);
691 if (DECL_DECLARED_INLINE_P (edge
->caller
->decl
))
692 max_depth
= PARAM_VALUE (PARAM_MAX_INLINE_RECURSIVE_DEPTH
);
694 if (!cgraph_maybe_hot_edge_p (edge
))
696 reason
= "recursive call is cold";
699 else if (max_count
&& !outer_node
->count
)
701 reason
= "not executed in profile";
704 else if (depth
> max_depth
)
706 reason
= "--param max-inline-recursive-depth exceeded.";
710 if (outer_node
->global
.inlined_to
)
711 caller_freq
= outer_node
->callers
->frequency
;
715 reason
= "function is inlined and unlikely";
721 /* Inlining of self recursive function into copy of itself within other function
722 is transformation similar to loop peeling.
724 Peeling is profitable if we can inline enough copies to make probability
725 of actual call to the self recursive function very small. Be sure that
726 the probability of recursion is small.
728 We ensure that the frequency of recursing is at most 1 - (1/max_depth).
729 This way the expected number of recision is at most max_depth. */
732 int max_prob
= CGRAPH_FREQ_BASE
- ((CGRAPH_FREQ_BASE
+ max_depth
- 1)
735 for (i
= 1; i
< depth
; i
++)
736 max_prob
= max_prob
* max_prob
/ CGRAPH_FREQ_BASE
;
738 && (edge
->count
* CGRAPH_FREQ_BASE
/ outer_node
->count
741 reason
= "profile of recursive call is too large";
745 && (edge
->frequency
* CGRAPH_FREQ_BASE
/ caller_freq
748 reason
= "frequency of recursive call is too large";
752 /* Recursive inlining, i.e. equivalent of unrolling, is profitable if recursion
753 depth is large. We reduce function call overhead and increase chances that
754 things fit in hardware return predictor.
756 Recursive inlining might however increase cost of stack frame setup
757 actually slowing down functions whose recursion tree is wide rather than
760 Deciding reliably on when to do recursive inlining without profile feedback
761 is tricky. For now we disable recursive inlining when probability of self
764 Recursive inlining of self recursive call within loop also results in large loop
765 depths that generally optimize badly. We may want to throttle down inlining
766 in those cases. In particular this seems to happen in one of libstdc++ rb tree
771 && (edge
->count
* 100 / outer_node
->count
772 <= PARAM_VALUE (PARAM_MIN_INLINE_RECURSIVE_PROBABILITY
)))
774 reason
= "profile of recursive call is too small";
778 && (edge
->frequency
* 100 / caller_freq
779 <= PARAM_VALUE (PARAM_MIN_INLINE_RECURSIVE_PROBABILITY
)))
781 reason
= "frequency of recursive call is too small";
785 if (!want_inline
&& dump_file
)
786 fprintf (dump_file
, " not inlining recursively: %s\n", reason
);
790 /* Return true when NODE has uninlinable caller;
791 set HAS_HOT_CALL if it has hot call.
792 Worker for cgraph_for_node_and_aliases. */
795 check_callers (struct cgraph_node
*node
, void *has_hot_call
)
797 struct cgraph_edge
*e
;
798 for (e
= node
->callers
; e
; e
= e
->next_caller
)
800 if (!can_inline_edge_p (e
, true))
802 if (!(*(bool *)has_hot_call
) && cgraph_maybe_hot_edge_p (e
))
803 *(bool *)has_hot_call
= true;
808 /* If NODE has a caller, return true. */
811 has_caller_p (struct cgraph_node
*node
, void *data ATTRIBUTE_UNUSED
)
818 /* Decide if inlining NODE would reduce unit size by eliminating
819 the offline copy of function.
820 When COLD is true the cold calls are considered, too. */
823 want_inline_function_to_all_callers_p (struct cgraph_node
*node
, bool cold
)
825 struct cgraph_node
*function
= cgraph_function_or_thunk_node (node
, NULL
);
826 bool has_hot_call
= false;
828 /* Does it have callers? */
829 if (!cgraph_for_node_and_aliases (node
, has_caller_p
, NULL
, true))
831 /* Already inlined? */
832 if (function
->global
.inlined_to
)
834 if (cgraph_function_or_thunk_node (node
, NULL
) != node
)
836 /* Inlining into all callers would increase size? */
837 if (estimate_growth (node
) > 0)
839 /* All inlines must be possible. */
840 if (cgraph_for_node_and_aliases (node
, check_callers
, &has_hot_call
, true))
842 if (!cold
&& !has_hot_call
)
847 #define RELATIVE_TIME_BENEFIT_RANGE (INT_MAX / 64)
849 /* Return relative time improvement for inlining EDGE in range
850 1...RELATIVE_TIME_BENEFIT_RANGE */
853 relative_time_benefit (struct inline_summary
*callee_info
,
854 struct cgraph_edge
*edge
,
857 gcov_type relbenefit
;
858 gcov_type uninlined_call_time
= compute_uninlined_call_time (callee_info
, edge
);
859 gcov_type inlined_call_time
= compute_inlined_call_time (edge
, edge_time
);
861 /* Inlining into extern inline function is not a win. */
862 if (DECL_EXTERNAL (edge
->caller
->global
.inlined_to
863 ? edge
->caller
->global
.inlined_to
->decl
864 : edge
->caller
->decl
))
867 /* Watch overflows. */
868 gcc_checking_assert (uninlined_call_time
>= 0);
869 gcc_checking_assert (inlined_call_time
>= 0);
870 gcc_checking_assert (uninlined_call_time
>= inlined_call_time
);
872 /* Compute relative time benefit, i.e. how much the call becomes faster.
873 ??? perhaps computing how much the caller+calle together become faster
874 would lead to more realistic results. */
875 if (!uninlined_call_time
)
876 uninlined_call_time
= 1;
878 RDIV (((gcov_type
)uninlined_call_time
- inlined_call_time
) * RELATIVE_TIME_BENEFIT_RANGE
,
879 uninlined_call_time
);
880 relbenefit
= MIN (relbenefit
, RELATIVE_TIME_BENEFIT_RANGE
);
881 gcc_checking_assert (relbenefit
>= 0);
882 relbenefit
= MAX (relbenefit
, 1);
887 /* A cost model driving the inlining heuristics in a way so the edges with
888 smallest badness are inlined first. After each inlining is performed
889 the costs of all caller edges of nodes affected are recomputed so the
890 metrics may accurately depend on values such as number of inlinable callers
891 of the function or function body size. */
894 edge_badness (struct cgraph_edge
*edge
, bool dump
)
897 int growth
, edge_time
;
898 struct cgraph_node
*callee
= cgraph_function_or_thunk_node (edge
->callee
,
900 struct inline_summary
*callee_info
= inline_summary (callee
);
903 if (DECL_DISREGARD_INLINE_LIMITS (callee
->decl
))
906 growth
= estimate_edge_growth (edge
);
907 edge_time
= estimate_edge_time (edge
);
908 hints
= estimate_edge_hints (edge
);
909 gcc_checking_assert (edge_time
>= 0);
910 gcc_checking_assert (edge_time
<= callee_info
->time
);
911 gcc_checking_assert (growth
<= callee_info
->size
);
915 fprintf (dump_file
, " Badness calculation for %s/%i -> %s/%i\n",
916 xstrdup (edge
->caller
->name ()),
918 xstrdup (callee
->name ()),
919 edge
->callee
->order
);
920 fprintf (dump_file
, " size growth %i, time %i ",
923 dump_inline_hints (dump_file
, hints
);
924 if (big_speedup_p (edge
))
925 fprintf (dump_file
, " big_speedup");
926 fprintf (dump_file
, "\n");
929 /* Always prefer inlining saving code size. */
932 badness
= INT_MIN
/ 2 + growth
;
934 fprintf (dump_file
, " %i: Growth %i <= 0\n", (int) badness
,
938 /* When profiling is available, compute badness as:
940 relative_edge_count * relative_time_benefit
941 goodness = -------------------------------------------
945 The fraction is upside down, because on edge counts and time beneits
946 the bounds are known. Edge growth is essentially unlimited. */
950 sreal tmp
, relbenefit_real
, growth_real
;
951 int relbenefit
= relative_time_benefit (callee_info
, edge
, edge_time
);
952 /* Capping edge->count to max_count. edge->count can be larger than
953 max_count if an inline adds new edges which increase max_count
954 after max_count is computed. */
955 gcov_type edge_count
= edge
->count
> max_count
? max_count
: edge
->count
;
957 sreal_init (&relbenefit_real
, relbenefit
, 0);
958 sreal_init (&growth_real
, growth
, 0);
960 /* relative_edge_count. */
961 sreal_init (&tmp
, edge_count
, 0);
962 sreal_div (&tmp
, &tmp
, &max_count_real
);
964 /* relative_time_benefit. */
965 sreal_mul (&tmp
, &tmp
, &relbenefit_real
);
966 sreal_div (&tmp
, &tmp
, &max_relbenefit_real
);
968 /* growth_f_caller. */
969 sreal_mul (&tmp
, &tmp
, &half_int_min_real
);
970 sreal_div (&tmp
, &tmp
, &growth_real
);
972 badness
= -1 * sreal_to_int (&tmp
);
977 " %i (relative %f): profile info. Relative count %f%s"
978 " * Relative benefit %f\n",
979 (int) badness
, (double) badness
/ INT_MIN
,
980 (double) edge_count
/ max_count
,
981 edge
->count
> max_count
? " (capped to max_count)" : "",
982 relbenefit
* 100.0 / RELATIVE_TIME_BENEFIT_RANGE
);
986 /* When function local profile is available. Compute badness as:
988 relative_time_benefit
989 goodness = ---------------------------------
990 growth_of_caller * overall_growth
994 compensated by the inline hints.
996 else if (flag_guess_branch_prob
)
998 badness
= (relative_time_benefit (callee_info
, edge
, edge_time
)
999 * (INT_MIN
/ 16 / RELATIVE_TIME_BENEFIT_RANGE
));
1000 badness
/= (MIN (65536/2, growth
) * MIN (65536/2, MAX (1, callee_info
->growth
)));
1001 gcc_checking_assert (badness
<=0 && badness
>= INT_MIN
/ 16);
1002 if ((hints
& (INLINE_HINT_indirect_call
1003 | INLINE_HINT_loop_iterations
1004 | INLINE_HINT_array_index
1005 | INLINE_HINT_loop_stride
))
1006 || callee_info
->growth
<= 0)
1008 if (hints
& (INLINE_HINT_same_scc
))
1010 else if (hints
& (INLINE_HINT_in_scc
))
1012 else if (hints
& (INLINE_HINT_cross_module
))
1014 gcc_checking_assert (badness
<= 0 && badness
>= INT_MIN
/ 2);
1015 if ((hints
& INLINE_HINT_declared_inline
) && badness
>= INT_MIN
/ 32)
1020 " %i: guessed profile. frequency %f,"
1021 " benefit %f%%, time w/o inlining %i, time w inlining %i"
1022 " overall growth %i (current) %i (original)\n",
1023 (int) badness
, (double)edge
->frequency
/ CGRAPH_FREQ_BASE
,
1024 relative_time_benefit (callee_info
, edge
, edge_time
) * 100.0
1025 / RELATIVE_TIME_BENEFIT_RANGE
,
1026 (int)compute_uninlined_call_time (callee_info
, edge
),
1027 (int)compute_inlined_call_time (edge
, edge_time
),
1028 estimate_growth (callee
),
1029 callee_info
->growth
);
1032 /* When function local profile is not available or it does not give
1033 useful information (ie frequency is zero), base the cost on
1034 loop nest and overall size growth, so we optimize for overall number
1035 of functions fully inlined in program. */
1038 int nest
= MIN (inline_edge_summary (edge
)->loop_depth
, 8);
1039 badness
= growth
* 256;
1041 /* Decrease badness if call is nested. */
1049 fprintf (dump_file
, " %i: no profile. nest %i\n", (int) badness
,
1053 /* Ensure that we did not overflow in all the fixed point math above. */
1054 gcc_assert (badness
>= INT_MIN
);
1055 gcc_assert (badness
<= INT_MAX
- 1);
1056 /* Make recursive inlining happen always after other inlining is done. */
1057 if (cgraph_edge_recursive_p (edge
))
1063 /* Recompute badness of EDGE and update its key in HEAP if needed. */
1065 update_edge_key (fibheap_t heap
, struct cgraph_edge
*edge
)
1067 int badness
= edge_badness (edge
, false);
1070 fibnode_t n
= (fibnode_t
) edge
->aux
;
1071 gcc_checking_assert (n
->data
== edge
);
1073 /* fibheap_replace_key only decrease the keys.
1074 When we increase the key we do not update heap
1075 and instead re-insert the element once it becomes
1076 a minimum of heap. */
1077 if (badness
< n
->key
)
1079 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1082 " decreasing badness %s/%i -> %s/%i, %i to %i\n",
1083 xstrdup (edge
->caller
->name ()),
1084 edge
->caller
->order
,
1085 xstrdup (edge
->callee
->name ()),
1086 edge
->callee
->order
,
1090 fibheap_replace_key (heap
, n
, badness
);
1091 gcc_checking_assert (n
->key
== badness
);
1096 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1099 " enqueuing call %s/%i -> %s/%i, badness %i\n",
1100 xstrdup (edge
->caller
->name ()),
1101 edge
->caller
->order
,
1102 xstrdup (edge
->callee
->name ()),
1103 edge
->callee
->order
,
1106 edge
->aux
= fibheap_insert (heap
, badness
, edge
);
1111 /* NODE was inlined.
1112 All caller edges needs to be resetted because
1113 size estimates change. Similarly callees needs reset
1114 because better context may be known. */
1117 reset_edge_caches (struct cgraph_node
*node
)
1119 struct cgraph_edge
*edge
;
1120 struct cgraph_edge
*e
= node
->callees
;
1121 struct cgraph_node
*where
= node
;
1123 struct ipa_ref
*ref
= NULL
;
1125 if (where
->global
.inlined_to
)
1126 where
= where
->global
.inlined_to
;
1128 /* WHERE body size has changed, the cached growth is invalid. */
1129 reset_node_growth_cache (where
);
1131 for (edge
= where
->callers
; edge
; edge
= edge
->next_caller
)
1132 if (edge
->inline_failed
)
1133 reset_edge_growth_cache (edge
);
1134 for (i
= 0; where
->iterate_referring (i
, ref
); i
++)
1135 if (ref
->use
== IPA_REF_ALIAS
)
1136 reset_edge_caches (dyn_cast
<cgraph_node
*> (ref
->referring
));
1142 if (!e
->inline_failed
&& e
->callee
->callees
)
1143 e
= e
->callee
->callees
;
1146 if (e
->inline_failed
)
1147 reset_edge_growth_cache (e
);
1154 if (e
->caller
== node
)
1156 e
= e
->caller
->callers
;
1158 while (!e
->next_callee
);
1164 /* Recompute HEAP nodes for each of caller of NODE.
1165 UPDATED_NODES track nodes we already visited, to avoid redundant work.
1166 When CHECK_INLINABLITY_FOR is set, re-check for specified edge that
1167 it is inlinable. Otherwise check all edges. */
1170 update_caller_keys (fibheap_t heap
, struct cgraph_node
*node
,
1171 bitmap updated_nodes
,
1172 struct cgraph_edge
*check_inlinablity_for
)
1174 struct cgraph_edge
*edge
;
1176 struct ipa_ref
*ref
= NULL
;
1178 if ((!node
->alias
&& !inline_summary (node
)->inlinable
)
1179 || node
->global
.inlined_to
)
1181 if (!bitmap_set_bit (updated_nodes
, node
->uid
))
1184 for (i
= 0; node
->iterate_referring (i
, ref
); i
++)
1185 if (ref
->use
== IPA_REF_ALIAS
)
1187 struct cgraph_node
*alias
= dyn_cast
<cgraph_node
*> (ref
->referring
);
1188 update_caller_keys (heap
, alias
, updated_nodes
, check_inlinablity_for
);
1191 for (edge
= node
->callers
; edge
; edge
= edge
->next_caller
)
1192 if (edge
->inline_failed
)
1194 if (!check_inlinablity_for
1195 || check_inlinablity_for
== edge
)
1197 if (can_inline_edge_p (edge
, false)
1198 && want_inline_small_function_p (edge
, false))
1199 update_edge_key (heap
, edge
);
1202 report_inline_failed_reason (edge
);
1203 fibheap_delete_node (heap
, (fibnode_t
) edge
->aux
);
1208 update_edge_key (heap
, edge
);
1212 /* Recompute HEAP nodes for each uninlined call in NODE.
1213 This is used when we know that edge badnesses are going only to increase
1214 (we introduced new call site) and thus all we need is to insert newly
1215 created edges into heap. */
1218 update_callee_keys (fibheap_t heap
, struct cgraph_node
*node
,
1219 bitmap updated_nodes
)
1221 struct cgraph_edge
*e
= node
->callees
;
1226 if (!e
->inline_failed
&& e
->callee
->callees
)
1227 e
= e
->callee
->callees
;
1230 enum availability avail
;
1231 struct cgraph_node
*callee
;
1232 /* We do not reset callee growth cache here. Since we added a new call,
1233 growth chould have just increased and consequentely badness metric
1234 don't need updating. */
1235 if (e
->inline_failed
1236 && (callee
= cgraph_function_or_thunk_node (e
->callee
, &avail
))
1237 && inline_summary (callee
)->inlinable
1238 && avail
>= AVAIL_AVAILABLE
1239 && !bitmap_bit_p (updated_nodes
, callee
->uid
))
1241 if (can_inline_edge_p (e
, false)
1242 && want_inline_small_function_p (e
, false))
1243 update_edge_key (heap
, e
);
1246 report_inline_failed_reason (e
);
1247 fibheap_delete_node (heap
, (fibnode_t
) e
->aux
);
1257 if (e
->caller
== node
)
1259 e
= e
->caller
->callers
;
1261 while (!e
->next_callee
);
1267 /* Enqueue all recursive calls from NODE into priority queue depending on
1268 how likely we want to recursively inline the call. */
1271 lookup_recursive_calls (struct cgraph_node
*node
, struct cgraph_node
*where
,
1274 struct cgraph_edge
*e
;
1275 enum availability avail
;
1277 for (e
= where
->callees
; e
; e
= e
->next_callee
)
1278 if (e
->callee
== node
1279 || (cgraph_function_or_thunk_node (e
->callee
, &avail
) == node
1280 && avail
> AVAIL_OVERWRITABLE
))
1282 /* When profile feedback is available, prioritize by expected number
1284 fibheap_insert (heap
,
1285 !max_count
? -e
->frequency
1286 : -(e
->count
/ ((max_count
+ (1<<24) - 1) / (1<<24))),
1289 for (e
= where
->callees
; e
; e
= e
->next_callee
)
1290 if (!e
->inline_failed
)
1291 lookup_recursive_calls (node
, e
->callee
, heap
);
1294 /* Decide on recursive inlining: in the case function has recursive calls,
1295 inline until body size reaches given argument. If any new indirect edges
1296 are discovered in the process, add them to *NEW_EDGES, unless NEW_EDGES
1300 recursive_inlining (struct cgraph_edge
*edge
,
1301 vec
<cgraph_edge_p
> *new_edges
)
1303 int limit
= PARAM_VALUE (PARAM_MAX_INLINE_INSNS_RECURSIVE_AUTO
);
1305 struct cgraph_node
*node
;
1306 struct cgraph_edge
*e
;
1307 struct cgraph_node
*master_clone
= NULL
, *next
;
1311 node
= edge
->caller
;
1312 if (node
->global
.inlined_to
)
1313 node
= node
->global
.inlined_to
;
1315 if (DECL_DECLARED_INLINE_P (node
->decl
))
1316 limit
= PARAM_VALUE (PARAM_MAX_INLINE_INSNS_RECURSIVE
);
1318 /* Make sure that function is small enough to be considered for inlining. */
1319 if (estimate_size_after_inlining (node
, edge
) >= limit
)
1321 heap
= fibheap_new ();
1322 lookup_recursive_calls (node
, node
, heap
);
1323 if (fibheap_empty (heap
))
1325 fibheap_delete (heap
);
1331 " Performing recursive inlining on %s\n",
1334 /* Do the inlining and update list of recursive call during process. */
1335 while (!fibheap_empty (heap
))
1337 struct cgraph_edge
*curr
1338 = (struct cgraph_edge
*) fibheap_extract_min (heap
);
1339 struct cgraph_node
*cnode
, *dest
= curr
->callee
;
1341 if (!can_inline_edge_p (curr
, true))
1344 /* MASTER_CLONE is produced in the case we already started modified
1345 the function. Be sure to redirect edge to the original body before
1346 estimating growths otherwise we will be seeing growths after inlining
1347 the already modified body. */
1350 cgraph_redirect_edge_callee (curr
, master_clone
);
1351 reset_edge_growth_cache (curr
);
1354 if (estimate_size_after_inlining (node
, curr
) > limit
)
1356 cgraph_redirect_edge_callee (curr
, dest
);
1357 reset_edge_growth_cache (curr
);
1362 for (cnode
= curr
->caller
;
1363 cnode
->global
.inlined_to
; cnode
= cnode
->callers
->caller
)
1365 == cgraph_function_or_thunk_node (curr
->callee
, NULL
)->decl
)
1368 if (!want_inline_self_recursive_call_p (curr
, node
, false, depth
))
1370 cgraph_redirect_edge_callee (curr
, dest
);
1371 reset_edge_growth_cache (curr
);
1378 " Inlining call of depth %i", depth
);
1381 fprintf (dump_file
, " called approx. %.2f times per call",
1382 (double)curr
->count
/ node
->count
);
1384 fprintf (dump_file
, "\n");
1388 /* We need original clone to copy around. */
1389 master_clone
= cgraph_clone_node (node
, node
->decl
,
1390 node
->count
, CGRAPH_FREQ_BASE
,
1391 false, vNULL
, true, NULL
, NULL
);
1392 for (e
= master_clone
->callees
; e
; e
= e
->next_callee
)
1393 if (!e
->inline_failed
)
1394 clone_inlined_nodes (e
, true, false, NULL
, CGRAPH_FREQ_BASE
);
1395 cgraph_redirect_edge_callee (curr
, master_clone
);
1396 reset_edge_growth_cache (curr
);
1399 inline_call (curr
, false, new_edges
, &overall_size
, true);
1400 lookup_recursive_calls (node
, curr
->callee
, heap
);
1404 if (!fibheap_empty (heap
) && dump_file
)
1405 fprintf (dump_file
, " Recursive inlining growth limit met.\n");
1406 fibheap_delete (heap
);
1413 "\n Inlined %i times, "
1414 "body grown from size %i to %i, time %i to %i\n", n
,
1415 inline_summary (master_clone
)->size
, inline_summary (node
)->size
,
1416 inline_summary (master_clone
)->time
, inline_summary (node
)->time
);
1418 /* Remove master clone we used for inlining. We rely that clones inlined
1419 into master clone gets queued just before master clone so we don't
1421 for (node
= cgraph_first_function (); node
!= master_clone
;
1424 next
= cgraph_next_function (node
);
1425 if (node
->global
.inlined_to
== master_clone
)
1426 cgraph_remove_node (node
);
1428 cgraph_remove_node (master_clone
);
1433 /* Given whole compilation unit estimate of INSNS, compute how large we can
1434 allow the unit to grow. */
1437 compute_max_insns (int insns
)
1439 int max_insns
= insns
;
1440 if (max_insns
< PARAM_VALUE (PARAM_LARGE_UNIT_INSNS
))
1441 max_insns
= PARAM_VALUE (PARAM_LARGE_UNIT_INSNS
);
1443 return ((int64_t) max_insns
1444 * (100 + PARAM_VALUE (PARAM_INLINE_UNIT_GROWTH
)) / 100);
1448 /* Compute badness of all edges in NEW_EDGES and add them to the HEAP. */
1451 add_new_edges_to_heap (fibheap_t heap
, vec
<cgraph_edge_p
> new_edges
)
1453 while (new_edges
.length () > 0)
1455 struct cgraph_edge
*edge
= new_edges
.pop ();
1457 gcc_assert (!edge
->aux
);
1458 if (edge
->inline_failed
1459 && can_inline_edge_p (edge
, true)
1460 && want_inline_small_function_p (edge
, true))
1461 edge
->aux
= fibheap_insert (heap
, edge_badness (edge
, false), edge
);
1465 /* Remove EDGE from the fibheap. */
1468 heap_edge_removal_hook (struct cgraph_edge
*e
, void *data
)
1471 reset_node_growth_cache (e
->callee
);
1474 fibheap_delete_node ((fibheap_t
)data
, (fibnode_t
)e
->aux
);
1479 /* Return true if speculation of edge E seems useful.
1480 If ANTICIPATE_INLINING is true, be conservative and hope that E
1484 speculation_useful_p (struct cgraph_edge
*e
, bool anticipate_inlining
)
1486 enum availability avail
;
1487 struct cgraph_node
*target
= cgraph_function_or_thunk_node (e
->callee
, &avail
);
1488 struct cgraph_edge
*direct
, *indirect
;
1489 struct ipa_ref
*ref
;
1491 gcc_assert (e
->speculative
&& !e
->indirect_unknown_callee
);
1493 if (!cgraph_maybe_hot_edge_p (e
))
1496 /* See if IP optimizations found something potentially useful about the
1497 function. For now we look only for CONST/PURE flags. Almost everything
1498 else we propagate is useless. */
1499 if (avail
>= AVAIL_AVAILABLE
)
1501 int ecf_flags
= flags_from_decl_or_type (target
->decl
);
1502 if (ecf_flags
& ECF_CONST
)
1504 cgraph_speculative_call_info (e
, direct
, indirect
, ref
);
1505 if (!(indirect
->indirect_info
->ecf_flags
& ECF_CONST
))
1508 else if (ecf_flags
& ECF_PURE
)
1510 cgraph_speculative_call_info (e
, direct
, indirect
, ref
);
1511 if (!(indirect
->indirect_info
->ecf_flags
& ECF_PURE
))
1515 /* If we did not managed to inline the function nor redirect
1516 to an ipa-cp clone (that are seen by having local flag set),
1517 it is probably pointless to inline it unless hardware is missing
1518 indirect call predictor. */
1519 if (!anticipate_inlining
&& e
->inline_failed
&& !target
->local
.local
)
1521 /* For overwritable targets there is not much to do. */
1522 if (e
->inline_failed
&& !can_inline_edge_p (e
, false, true))
1524 /* OK, speculation seems interesting. */
1528 /* We know that EDGE is not going to be inlined.
1529 See if we can remove speculation. */
1532 resolve_noninline_speculation (fibheap_t edge_heap
, struct cgraph_edge
*edge
)
1534 if (edge
->speculative
&& !speculation_useful_p (edge
, false))
1536 struct cgraph_node
*node
= edge
->caller
;
1537 struct cgraph_node
*where
= node
->global
.inlined_to
1538 ? node
->global
.inlined_to
: node
;
1539 bitmap updated_nodes
= BITMAP_ALLOC (NULL
);
1541 spec_rem
+= edge
->count
;
1542 cgraph_resolve_speculation (edge
, NULL
);
1543 reset_edge_caches (where
);
1544 inline_update_overall_summary (where
);
1545 update_caller_keys (edge_heap
, where
,
1546 updated_nodes
, NULL
);
1547 update_callee_keys (edge_heap
, where
,
1549 BITMAP_FREE (updated_nodes
);
1553 /* We use greedy algorithm for inlining of small functions:
1554 All inline candidates are put into prioritized heap ordered in
1557 The inlining of small functions is bounded by unit growth parameters. */
1560 inline_small_functions (void)
1562 struct cgraph_node
*node
;
1563 struct cgraph_edge
*edge
;
1564 fibheap_t edge_heap
= fibheap_new ();
1565 bitmap updated_nodes
= BITMAP_ALLOC (NULL
);
1566 int min_size
, max_size
;
1567 auto_vec
<cgraph_edge_p
> new_indirect_edges
;
1568 int initial_size
= 0;
1569 struct cgraph_node
**order
= XCNEWVEC (struct cgraph_node
*, cgraph_n_nodes
);
1570 struct cgraph_edge_hook_list
*edge_removal_hook_holder
;
1572 if (flag_indirect_inlining
)
1573 new_indirect_edges
.create (8);
1575 edge_removal_hook_holder
1576 = cgraph_add_edge_removal_hook (&heap_edge_removal_hook
, edge_heap
);
1578 /* Compute overall unit size and other global parameters used by badness
1582 ipa_reduced_postorder (order
, true, true, NULL
);
1585 FOR_EACH_DEFINED_FUNCTION (node
)
1586 if (!node
->global
.inlined_to
)
1588 if (cgraph_function_with_gimple_body_p (node
)
1589 || node
->thunk
.thunk_p
)
1591 struct inline_summary
*info
= inline_summary (node
);
1592 struct ipa_dfs_info
*dfs
= (struct ipa_dfs_info
*) node
->aux
;
1594 /* Do not account external functions, they will be optimized out
1595 if not inlined. Also only count the non-cold portion of program. */
1596 if (!DECL_EXTERNAL (node
->decl
)
1597 && node
->frequency
!= NODE_FREQUENCY_UNLIKELY_EXECUTED
)
1598 initial_size
+= info
->size
;
1599 info
->growth
= estimate_growth (node
);
1600 if (dfs
&& dfs
->next_cycle
)
1602 struct cgraph_node
*n2
;
1603 int id
= dfs
->scc_no
+ 1;
1605 n2
= ((struct ipa_dfs_info
*) node
->aux
)->next_cycle
)
1607 struct inline_summary
*info2
= inline_summary (n2
);
1615 for (edge
= node
->callers
; edge
; edge
= edge
->next_caller
)
1616 if (max_count
< edge
->count
)
1617 max_count
= edge
->count
;
1619 sreal_init (&max_count_real
, max_count
, 0);
1620 sreal_init (&max_relbenefit_real
, RELATIVE_TIME_BENEFIT_RANGE
, 0);
1621 sreal_init (&half_int_min_real
, INT_MAX
/ 2, 0);
1622 ipa_free_postorder_info ();
1623 initialize_growth_caches ();
1627 "\nDeciding on inlining of small functions. Starting with size %i.\n",
1630 overall_size
= initial_size
;
1631 max_size
= compute_max_insns (overall_size
);
1632 min_size
= overall_size
;
1634 /* Populate the heap with all edges we might inline. */
1636 FOR_EACH_DEFINED_FUNCTION (node
)
1638 bool update
= false;
1639 struct cgraph_edge
*next
;
1642 fprintf (dump_file
, "Enqueueing calls in %s/%i.\n",
1643 node
->name (), node
->order
);
1645 for (edge
= node
->callees
; edge
; edge
= next
)
1647 next
= edge
->next_callee
;
1648 if (edge
->inline_failed
1650 && can_inline_edge_p (edge
, true)
1651 && want_inline_small_function_p (edge
, true)
1652 && edge
->inline_failed
)
1654 gcc_assert (!edge
->aux
);
1655 update_edge_key (edge_heap
, edge
);
1657 if (edge
->speculative
&& !speculation_useful_p (edge
, edge
->aux
!= NULL
))
1659 cgraph_resolve_speculation (edge
, NULL
);
1665 struct cgraph_node
*where
= node
->global
.inlined_to
1666 ? node
->global
.inlined_to
: node
;
1667 inline_update_overall_summary (where
);
1668 reset_node_growth_cache (where
);
1669 reset_edge_caches (where
);
1670 update_caller_keys (edge_heap
, where
,
1671 updated_nodes
, NULL
);
1672 bitmap_clear (updated_nodes
);
1676 gcc_assert (in_lto_p
1678 || (profile_info
&& flag_branch_probabilities
));
1680 while (!fibheap_empty (edge_heap
))
1682 int old_size
= overall_size
;
1683 struct cgraph_node
*where
, *callee
;
1684 int badness
= fibheap_min_key (edge_heap
);
1685 int current_badness
;
1689 edge
= (struct cgraph_edge
*) fibheap_extract_min (edge_heap
);
1690 gcc_assert (edge
->aux
);
1692 if (!edge
->inline_failed
|| !edge
->callee
->analyzed
)
1695 /* Be sure that caches are maintained consistent.
1696 We can not make this ENABLE_CHECKING only because it cause different
1697 updates of the fibheap queue. */
1698 cached_badness
= edge_badness (edge
, false);
1699 reset_edge_growth_cache (edge
);
1700 reset_node_growth_cache (edge
->callee
);
1702 /* When updating the edge costs, we only decrease badness in the keys.
1703 Increases of badness are handled lazilly; when we see key with out
1704 of date value on it, we re-insert it now. */
1705 current_badness
= edge_badness (edge
, false);
1706 gcc_assert (cached_badness
== current_badness
);
1707 gcc_assert (current_badness
>= badness
);
1708 if (current_badness
!= badness
)
1710 edge
->aux
= fibheap_insert (edge_heap
, current_badness
, edge
);
1714 if (!can_inline_edge_p (edge
, true))
1716 resolve_noninline_speculation (edge_heap
, edge
);
1720 callee
= cgraph_function_or_thunk_node (edge
->callee
, NULL
);
1721 growth
= estimate_edge_growth (edge
);
1725 "\nConsidering %s/%i with %i size\n",
1726 callee
->name (), callee
->order
,
1727 inline_summary (callee
)->size
);
1729 " to be inlined into %s/%i in %s:%i\n"
1730 " Estimated badness is %i, frequency %.2f.\n",
1731 edge
->caller
->name (), edge
->caller
->order
,
1732 flag_wpa
? "unknown"
1733 : gimple_filename ((const_gimple
) edge
->call_stmt
),
1735 : gimple_lineno ((const_gimple
) edge
->call_stmt
),
1737 edge
->frequency
/ (double)CGRAPH_FREQ_BASE
);
1739 fprintf (dump_file
," Called %"PRId64
"x\n",
1741 if (dump_flags
& TDF_DETAILS
)
1742 edge_badness (edge
, true);
1745 if (overall_size
+ growth
> max_size
1746 && !DECL_DISREGARD_INLINE_LIMITS (callee
->decl
))
1748 edge
->inline_failed
= CIF_INLINE_UNIT_GROWTH_LIMIT
;
1749 report_inline_failed_reason (edge
);
1750 resolve_noninline_speculation (edge_heap
, edge
);
1754 if (!want_inline_small_function_p (edge
, true))
1756 resolve_noninline_speculation (edge_heap
, edge
);
1760 /* Heuristics for inlining small functions work poorly for
1761 recursive calls where we do effects similar to loop unrolling.
1762 When inlining such edge seems profitable, leave decision on
1763 specific inliner. */
1764 if (cgraph_edge_recursive_p (edge
))
1766 where
= edge
->caller
;
1767 if (where
->global
.inlined_to
)
1768 where
= where
->global
.inlined_to
;
1769 if (!recursive_inlining (edge
,
1770 flag_indirect_inlining
1771 ? &new_indirect_edges
: NULL
))
1773 edge
->inline_failed
= CIF_RECURSIVE_INLINING
;
1774 resolve_noninline_speculation (edge_heap
, edge
);
1777 reset_edge_caches (where
);
1778 /* Recursive inliner inlines all recursive calls of the function
1779 at once. Consequently we need to update all callee keys. */
1780 if (flag_indirect_inlining
)
1781 add_new_edges_to_heap (edge_heap
, new_indirect_edges
);
1782 update_callee_keys (edge_heap
, where
, updated_nodes
);
1783 bitmap_clear (updated_nodes
);
1787 struct cgraph_node
*outer_node
= NULL
;
1790 /* Consider the case where self recursive function A is inlined
1791 into B. This is desired optimization in some cases, since it
1792 leads to effect similar of loop peeling and we might completely
1793 optimize out the recursive call. However we must be extra
1796 where
= edge
->caller
;
1797 while (where
->global
.inlined_to
)
1799 if (where
->decl
== callee
->decl
)
1800 outer_node
= where
, depth
++;
1801 where
= where
->callers
->caller
;
1804 && !want_inline_self_recursive_call_p (edge
, outer_node
,
1808 = (DECL_DISREGARD_INLINE_LIMITS (edge
->callee
->decl
)
1809 ? CIF_RECURSIVE_INLINING
: CIF_UNSPECIFIED
);
1810 resolve_noninline_speculation (edge_heap
, edge
);
1813 else if (depth
&& dump_file
)
1814 fprintf (dump_file
, " Peeling recursion with depth %i\n", depth
);
1816 gcc_checking_assert (!callee
->global
.inlined_to
);
1817 inline_call (edge
, true, &new_indirect_edges
, &overall_size
, true);
1818 if (flag_indirect_inlining
)
1819 add_new_edges_to_heap (edge_heap
, new_indirect_edges
);
1821 reset_edge_caches (edge
->callee
);
1822 reset_node_growth_cache (callee
);
1824 update_callee_keys (edge_heap
, where
, updated_nodes
);
1826 where
= edge
->caller
;
1827 if (where
->global
.inlined_to
)
1828 where
= where
->global
.inlined_to
;
1830 /* Our profitability metric can depend on local properties
1831 such as number of inlinable calls and size of the function body.
1832 After inlining these properties might change for the function we
1833 inlined into (since it's body size changed) and for the functions
1834 called by function we inlined (since number of it inlinable callers
1836 update_caller_keys (edge_heap
, where
, updated_nodes
, NULL
);
1837 bitmap_clear (updated_nodes
);
1842 " Inlined into %s which now has time %i and size %i,"
1843 "net change of %+i.\n",
1844 edge
->caller
->name (),
1845 inline_summary (edge
->caller
)->time
,
1846 inline_summary (edge
->caller
)->size
,
1847 overall_size
- old_size
);
1849 if (min_size
> overall_size
)
1851 min_size
= overall_size
;
1852 max_size
= compute_max_insns (min_size
);
1855 fprintf (dump_file
, "New minimal size reached: %i\n", min_size
);
1859 free_growth_caches ();
1860 fibheap_delete (edge_heap
);
1863 "Unit growth for small function inlining: %i->%i (%i%%)\n",
1864 initial_size
, overall_size
,
1865 initial_size
? overall_size
* 100 / (initial_size
) - 100: 0);
1866 BITMAP_FREE (updated_nodes
);
1867 cgraph_remove_edge_removal_hook (edge_removal_hook_holder
);
1870 /* Flatten NODE. Performed both during early inlining and
1871 at IPA inlining time. */
1874 flatten_function (struct cgraph_node
*node
, bool early
)
1876 struct cgraph_edge
*e
;
1878 /* We shouldn't be called recursively when we are being processed. */
1879 gcc_assert (node
->aux
== NULL
);
1881 node
->aux
= (void *) node
;
1883 for (e
= node
->callees
; e
; e
= e
->next_callee
)
1885 struct cgraph_node
*orig_callee
;
1886 struct cgraph_node
*callee
= cgraph_function_or_thunk_node (e
->callee
, NULL
);
1888 /* We've hit cycle? It is time to give up. */
1893 "Not inlining %s into %s to avoid cycle.\n",
1894 xstrdup (callee
->name ()),
1895 xstrdup (e
->caller
->name ()));
1896 e
->inline_failed
= CIF_RECURSIVE_INLINING
;
1900 /* When the edge is already inlined, we just need to recurse into
1901 it in order to fully flatten the leaves. */
1902 if (!e
->inline_failed
)
1904 flatten_function (callee
, early
);
1908 /* Flatten attribute needs to be processed during late inlining. For
1909 extra code quality we however do flattening during early optimization,
1912 ? !can_inline_edge_p (e
, true)
1913 : !can_early_inline_edge_p (e
))
1916 if (cgraph_edge_recursive_p (e
))
1919 fprintf (dump_file
, "Not inlining: recursive call.\n");
1923 if (gimple_in_ssa_p (DECL_STRUCT_FUNCTION (node
->decl
))
1924 != gimple_in_ssa_p (DECL_STRUCT_FUNCTION (callee
->decl
)))
1927 fprintf (dump_file
, "Not inlining: SSA form does not match.\n");
1931 /* Inline the edge and flatten the inline clone. Avoid
1932 recursing through the original node if the node was cloned. */
1934 fprintf (dump_file
, " Inlining %s into %s.\n",
1935 xstrdup (callee
->name ()),
1936 xstrdup (e
->caller
->name ()));
1937 orig_callee
= callee
;
1938 inline_call (e
, true, NULL
, NULL
, false);
1939 if (e
->callee
!= orig_callee
)
1940 orig_callee
->aux
= (void *) node
;
1941 flatten_function (e
->callee
, early
);
1942 if (e
->callee
!= orig_callee
)
1943 orig_callee
->aux
= NULL
;
1947 if (!node
->global
.inlined_to
)
1948 inline_update_overall_summary (node
);
1951 /* Count number of callers of NODE and store it into DATA (that
1952 points to int. Worker for cgraph_for_node_and_aliases. */
1955 sum_callers (struct cgraph_node
*node
, void *data
)
1957 struct cgraph_edge
*e
;
1958 int *num_calls
= (int *)data
;
1960 for (e
= node
->callers
; e
; e
= e
->next_caller
)
1965 /* Inline NODE to all callers. Worker for cgraph_for_node_and_aliases.
1966 DATA points to number of calls originally found so we avoid infinite
1970 inline_to_all_callers (struct cgraph_node
*node
, void *data
)
1972 int *num_calls
= (int *)data
;
1973 bool callee_removed
= false;
1975 while (node
->callers
&& !node
->global
.inlined_to
)
1977 struct cgraph_node
*caller
= node
->callers
->caller
;
1982 "\nInlining %s size %i.\n",
1984 inline_summary (node
)->size
);
1986 " Called once from %s %i insns.\n",
1987 node
->callers
->caller
->name (),
1988 inline_summary (node
->callers
->caller
)->size
);
1991 inline_call (node
->callers
, true, NULL
, NULL
, true, &callee_removed
);
1994 " Inlined into %s which now has %i size\n",
1996 inline_summary (caller
)->size
);
1997 if (!(*num_calls
)--)
2000 fprintf (dump_file
, "New calls found; giving up.\n");
2001 return callee_removed
;
2009 /* Output overall time estimate. */
2011 dump_overall_stats (void)
2013 int64_t sum_weighted
= 0, sum
= 0;
2014 struct cgraph_node
*node
;
2016 FOR_EACH_DEFINED_FUNCTION (node
)
2017 if (!node
->global
.inlined_to
2020 int time
= inline_summary (node
)->time
;
2022 sum_weighted
+= time
* node
->count
;
2024 fprintf (dump_file
, "Overall time estimate: "
2025 "%"PRId64
" weighted by profile: "
2026 "%"PRId64
"\n", sum
, sum_weighted
);
2029 /* Output some useful stats about inlining. */
2032 dump_inline_stats (void)
2034 int64_t inlined_cnt
= 0, inlined_indir_cnt
= 0;
2035 int64_t inlined_virt_cnt
= 0, inlined_virt_indir_cnt
= 0;
2036 int64_t noninlined_cnt
= 0, noninlined_indir_cnt
= 0;
2037 int64_t noninlined_virt_cnt
= 0, noninlined_virt_indir_cnt
= 0;
2038 int64_t inlined_speculative
= 0, inlined_speculative_ply
= 0;
2039 int64_t indirect_poly_cnt
= 0, indirect_cnt
= 0;
2040 int64_t reason
[CIF_N_REASONS
][3];
2042 struct cgraph_node
*node
;
2044 memset (reason
, 0, sizeof (reason
));
2045 FOR_EACH_DEFINED_FUNCTION (node
)
2047 struct cgraph_edge
*e
;
2048 for (e
= node
->callees
; e
; e
= e
->next_callee
)
2050 if (e
->inline_failed
)
2052 reason
[(int) e
->inline_failed
][0] += e
->count
;
2053 reason
[(int) e
->inline_failed
][1] += e
->frequency
;
2054 reason
[(int) e
->inline_failed
][2] ++;
2055 if (DECL_VIRTUAL_P (e
->callee
->decl
))
2057 if (e
->indirect_inlining_edge
)
2058 noninlined_virt_indir_cnt
+= e
->count
;
2060 noninlined_virt_cnt
+= e
->count
;
2064 if (e
->indirect_inlining_edge
)
2065 noninlined_indir_cnt
+= e
->count
;
2067 noninlined_cnt
+= e
->count
;
2074 if (DECL_VIRTUAL_P (e
->callee
->decl
))
2075 inlined_speculative_ply
+= e
->count
;
2077 inlined_speculative
+= e
->count
;
2079 else if (DECL_VIRTUAL_P (e
->callee
->decl
))
2081 if (e
->indirect_inlining_edge
)
2082 inlined_virt_indir_cnt
+= e
->count
;
2084 inlined_virt_cnt
+= e
->count
;
2088 if (e
->indirect_inlining_edge
)
2089 inlined_indir_cnt
+= e
->count
;
2091 inlined_cnt
+= e
->count
;
2095 for (e
= node
->indirect_calls
; e
; e
= e
->next_callee
)
2096 if (e
->indirect_info
->polymorphic
)
2097 indirect_poly_cnt
+= e
->count
;
2099 indirect_cnt
+= e
->count
;
2104 "Inlined %"PRId64
" + speculative "
2105 "%"PRId64
" + speculative polymorphic "
2106 "%"PRId64
" + previously indirect "
2107 "%"PRId64
" + virtual "
2108 "%"PRId64
" + virtual and previously indirect "
2109 "%"PRId64
"\n" "Not inlined "
2110 "%"PRId64
" + previously indirect "
2111 "%"PRId64
" + virtual "
2112 "%"PRId64
" + virtual and previously indirect "
2113 "%"PRId64
" + stil indirect "
2114 "%"PRId64
" + still indirect polymorphic "
2115 "%"PRId64
"\n", inlined_cnt
,
2116 inlined_speculative
, inlined_speculative_ply
,
2117 inlined_indir_cnt
, inlined_virt_cnt
, inlined_virt_indir_cnt
,
2118 noninlined_cnt
, noninlined_indir_cnt
, noninlined_virt_cnt
,
2119 noninlined_virt_indir_cnt
, indirect_cnt
, indirect_poly_cnt
);
2121 "Removed speculations %"PRId64
"\n",
2124 dump_overall_stats ();
2125 fprintf (dump_file
, "\nWhy inlining failed?\n");
2126 for (i
= 0; i
< CIF_N_REASONS
; i
++)
2128 fprintf (dump_file
, "%-50s: %8i calls, %8i freq, %"PRId64
" count\n",
2129 cgraph_inline_failed_string ((cgraph_inline_failed_t
) i
),
2130 (int) reason
[i
][2], (int) reason
[i
][1], reason
[i
][0]);
2133 /* Decide on the inlining. We do so in the topological order to avoid
2134 expenses on updating data structures. */
2139 struct cgraph_node
*node
;
2141 struct cgraph_node
**order
;
2144 bool remove_functions
= false;
2149 order
= XCNEWVEC (struct cgraph_node
*, cgraph_n_nodes
);
2151 if (in_lto_p
&& optimize
)
2152 ipa_update_after_lto_read ();
2155 dump_inline_summaries (dump_file
);
2157 nnodes
= ipa_reverse_postorder (order
);
2159 FOR_EACH_FUNCTION (node
)
2163 fprintf (dump_file
, "\nFlattening functions:\n");
2165 /* In the first pass handle functions to be flattened. Do this with
2166 a priority so none of our later choices will make this impossible. */
2167 for (i
= nnodes
- 1; i
>= 0; i
--)
2171 /* Handle nodes to be flattened.
2172 Ideally when processing callees we stop inlining at the
2173 entry of cycles, possibly cloning that entry point and
2174 try to flatten itself turning it into a self-recursive
2176 if (lookup_attribute ("flatten",
2177 DECL_ATTRIBUTES (node
->decl
)) != NULL
)
2181 "Flattening %s\n", node
->name ());
2182 flatten_function (node
, false);
2186 dump_overall_stats ();
2188 inline_small_functions ();
2190 /* Do first after-inlining removal. We want to remove all "stale" extern inline
2191 functions and virtual functions so we really know what is called once. */
2192 symtab_remove_unreachable_nodes (false, dump_file
);
2195 /* Inline functions with a property that after inlining into all callers the
2196 code size will shrink because the out-of-line copy is eliminated.
2197 We do this regardless on the callee size as long as function growth limits
2201 "\nDeciding on functions to be inlined into all callers and removing useless speculations:\n");
2203 /* Inlining one function called once has good chance of preventing
2204 inlining other function into the same callee. Ideally we should
2205 work in priority order, but probably inlining hot functions first
2206 is good cut without the extra pain of maintaining the queue.
2208 ??? this is not really fitting the bill perfectly: inlining function
2209 into callee often leads to better optimization of callee due to
2210 increased context for optimization.
2211 For example if main() function calls a function that outputs help
2212 and then function that does the main optmization, we should inline
2213 the second with priority even if both calls are cold by themselves.
2215 We probably want to implement new predicate replacing our use of
2216 maybe_hot_edge interpreted as maybe_hot_edge || callee is known
2218 for (cold
= 0; cold
<= 1; cold
++)
2220 FOR_EACH_DEFINED_FUNCTION (node
)
2222 struct cgraph_edge
*edge
, *next
;
2225 for (edge
= node
->callees
; edge
; edge
= next
)
2227 next
= edge
->next_callee
;
2228 if (edge
->speculative
&& !speculation_useful_p (edge
, false))
2230 cgraph_resolve_speculation (edge
, NULL
);
2231 spec_rem
+= edge
->count
;
2233 remove_functions
= true;
2238 struct cgraph_node
*where
= node
->global
.inlined_to
2239 ? node
->global
.inlined_to
: node
;
2240 reset_node_growth_cache (where
);
2241 reset_edge_caches (where
);
2242 inline_update_overall_summary (where
);
2244 if (flag_inline_functions_called_once
2245 && want_inline_function_to_all_callers_p (node
, cold
))
2248 cgraph_for_node_and_aliases (node
, sum_callers
,
2250 while (cgraph_for_node_and_aliases (node
, inline_to_all_callers
,
2253 remove_functions
= true;
2258 /* Free ipa-prop structures if they are no longer needed. */
2260 ipa_free_all_structures_after_iinln ();
2265 "\nInlined %i calls, eliminated %i functions\n\n",
2266 ncalls_inlined
, nfunctions_inlined
);
2267 dump_inline_stats ();
2271 dump_inline_summaries (dump_file
);
2272 /* In WPA we use inline summaries for partitioning process. */
2274 inline_free_summary ();
2275 return remove_functions
? TODO_remove_functions
: 0;
2278 /* Inline always-inline function calls in NODE. */
2281 inline_always_inline_functions (struct cgraph_node
*node
)
2283 struct cgraph_edge
*e
;
2284 bool inlined
= false;
2286 for (e
= node
->callees
; e
; e
= e
->next_callee
)
2288 struct cgraph_node
*callee
= cgraph_function_or_thunk_node (e
->callee
, NULL
);
2289 if (!DECL_DISREGARD_INLINE_LIMITS (callee
->decl
))
2292 if (cgraph_edge_recursive_p (e
))
2295 fprintf (dump_file
, " Not inlining recursive call to %s.\n",
2296 e
->callee
->name ());
2297 e
->inline_failed
= CIF_RECURSIVE_INLINING
;
2301 if (!can_early_inline_edge_p (e
))
2303 /* Set inlined to true if the callee is marked "always_inline" but
2304 is not inlinable. This will allow flagging an error later in
2305 expand_call_inline in tree-inline.c. */
2306 if (lookup_attribute ("always_inline",
2307 DECL_ATTRIBUTES (callee
->decl
)) != NULL
)
2313 fprintf (dump_file
, " Inlining %s into %s (always_inline).\n",
2314 xstrdup (e
->callee
->name ()),
2315 xstrdup (e
->caller
->name ()));
2316 inline_call (e
, true, NULL
, NULL
, false);
2320 inline_update_overall_summary (node
);
2325 /* Decide on the inlining. We do so in the topological order to avoid
2326 expenses on updating data structures. */
2329 early_inline_small_functions (struct cgraph_node
*node
)
2331 struct cgraph_edge
*e
;
2332 bool inlined
= false;
2334 for (e
= node
->callees
; e
; e
= e
->next_callee
)
2336 struct cgraph_node
*callee
= cgraph_function_or_thunk_node (e
->callee
, NULL
);
2337 if (!inline_summary (callee
)->inlinable
2338 || !e
->inline_failed
)
2341 /* Do not consider functions not declared inline. */
2342 if (!DECL_DECLARED_INLINE_P (callee
->decl
)
2343 && !flag_inline_small_functions
2344 && !flag_inline_functions
)
2348 fprintf (dump_file
, "Considering inline candidate %s.\n",
2351 if (!can_early_inline_edge_p (e
))
2354 if (cgraph_edge_recursive_p (e
))
2357 fprintf (dump_file
, " Not inlining: recursive call.\n");
2361 if (!want_early_inline_function_p (e
))
2365 fprintf (dump_file
, " Inlining %s into %s.\n",
2366 xstrdup (callee
->name ()),
2367 xstrdup (e
->caller
->name ()));
2368 inline_call (e
, true, NULL
, NULL
, true);
2375 /* Do inlining of small functions. Doing so early helps profiling and other
2376 passes to be somewhat more effective and avoids some code duplication in
2377 later real inlining pass for testcases with very many function calls. */
2381 const pass_data pass_data_early_inline
=
2383 GIMPLE_PASS
, /* type */
2384 "einline", /* name */
2385 OPTGROUP_INLINE
, /* optinfo_flags */
2386 true, /* has_execute */
2387 TV_EARLY_INLINING
, /* tv_id */
2388 PROP_ssa
, /* properties_required */
2389 0, /* properties_provided */
2390 0, /* properties_destroyed */
2391 0, /* todo_flags_start */
2392 0, /* todo_flags_finish */
2395 class pass_early_inline
: public gimple_opt_pass
2398 pass_early_inline (gcc::context
*ctxt
)
2399 : gimple_opt_pass (pass_data_early_inline
, ctxt
)
2402 /* opt_pass methods: */
2403 virtual unsigned int execute (function
*);
2405 }; // class pass_early_inline
2408 pass_early_inline::execute (function
*fun
)
2410 struct cgraph_node
*node
= cgraph_get_node (current_function_decl
);
2411 struct cgraph_edge
*edge
;
2412 unsigned int todo
= 0;
2414 bool inlined
= false;
2419 /* Do nothing if datastructures for ipa-inliner are already computed. This
2420 happens when some pass decides to construct new function and
2421 cgraph_add_new_function calls lowering passes and early optimization on
2422 it. This may confuse ourself when early inliner decide to inline call to
2423 function clone, because function clones don't have parameter list in
2424 ipa-prop matching their signature. */
2425 if (ipa_node_params_vector
.exists ())
2428 #ifdef ENABLE_CHECKING
2429 verify_cgraph_node (node
);
2431 node
->remove_all_references ();
2433 /* Even when not optimizing or not inlining inline always-inline
2435 inlined
= inline_always_inline_functions (node
);
2439 || !flag_early_inlining
2440 /* Never inline regular functions into always-inline functions
2441 during incremental inlining. This sucks as functions calling
2442 always inline functions will get less optimized, but at the
2443 same time inlining of functions calling always inline
2444 function into an always inline function might introduce
2445 cycles of edges to be always inlined in the callgraph.
2447 We might want to be smarter and just avoid this type of inlining. */
2448 || DECL_DISREGARD_INLINE_LIMITS (node
->decl
))
2450 else if (lookup_attribute ("flatten",
2451 DECL_ATTRIBUTES (node
->decl
)) != NULL
)
2453 /* When the function is marked to be flattened, recursively inline
2457 "Flattening %s\n", node
->name ());
2458 flatten_function (node
, true);
2463 /* We iterate incremental inlining to get trivial cases of indirect
2465 while (iterations
< PARAM_VALUE (PARAM_EARLY_INLINER_MAX_ITERATIONS
)
2466 && early_inline_small_functions (node
))
2468 timevar_push (TV_INTEGRATION
);
2469 todo
|= optimize_inline_calls (current_function_decl
);
2471 /* Technically we ought to recompute inline parameters so the new
2472 iteration of early inliner works as expected. We however have
2473 values approximately right and thus we only need to update edge
2474 info that might be cleared out for newly discovered edges. */
2475 for (edge
= node
->callees
; edge
; edge
= edge
->next_callee
)
2477 struct inline_edge_summary
*es
= inline_edge_summary (edge
);
2479 = estimate_num_insns (edge
->call_stmt
, &eni_size_weights
);
2481 = estimate_num_insns (edge
->call_stmt
, &eni_time_weights
);
2482 if (edge
->callee
->decl
2483 && !gimple_check_call_matching_types (
2484 edge
->call_stmt
, edge
->callee
->decl
, false))
2485 edge
->call_stmt_cannot_inline_p
= true;
2487 if (iterations
< PARAM_VALUE (PARAM_EARLY_INLINER_MAX_ITERATIONS
) - 1)
2488 inline_update_overall_summary (node
);
2489 timevar_pop (TV_INTEGRATION
);
2494 fprintf (dump_file
, "Iterations: %i\n", iterations
);
2499 timevar_push (TV_INTEGRATION
);
2500 todo
|= optimize_inline_calls (current_function_decl
);
2501 timevar_pop (TV_INTEGRATION
);
2504 fun
->always_inline_functions_inlined
= true;
2512 make_pass_early_inline (gcc::context
*ctxt
)
2514 return new pass_early_inline (ctxt
);
2519 const pass_data pass_data_ipa_inline
=
2521 IPA_PASS
, /* type */
2522 "inline", /* name */
2523 OPTGROUP_INLINE
, /* optinfo_flags */
2524 true, /* has_execute */
2525 TV_IPA_INLINING
, /* tv_id */
2526 0, /* properties_required */
2527 0, /* properties_provided */
2528 0, /* properties_destroyed */
2529 TODO_remove_functions
, /* todo_flags_start */
2530 ( TODO_dump_symtab
), /* todo_flags_finish */
2533 class pass_ipa_inline
: public ipa_opt_pass_d
2536 pass_ipa_inline (gcc::context
*ctxt
)
2537 : ipa_opt_pass_d (pass_data_ipa_inline
, ctxt
,
2538 inline_generate_summary
, /* generate_summary */
2539 inline_write_summary
, /* write_summary */
2540 inline_read_summary
, /* read_summary */
2541 NULL
, /* write_optimization_summary */
2542 NULL
, /* read_optimization_summary */
2543 NULL
, /* stmt_fixup */
2544 0, /* function_transform_todo_flags_start */
2545 inline_transform
, /* function_transform */
2546 NULL
) /* variable_transform */
2549 /* opt_pass methods: */
2550 virtual unsigned int execute (function
*) { return ipa_inline (); }
2552 }; // class pass_ipa_inline
2557 make_pass_ipa_inline (gcc::context
*ctxt
)
2559 return new pass_ipa_inline (ctxt
);