1 /* Inlining decision heuristics.
2 Copyright (C) 2003, 2004, 2007, 2008, 2009, 2010, 2011
3 Free Software Foundation, Inc.
4 Contributed by Jan Hubicka
6 This file is part of GCC.
8 GCC is free software; you can redistribute it and/or modify it under
9 the terms of the GNU General Public License as published by the Free
10 Software Foundation; either version 3, or (at your option) any later
13 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
14 WARRANTY; without even the implied warranty of MERCHANTABILITY or
15 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
18 You should have received a copy of the GNU General Public License
19 along with GCC; see the file COPYING3. If not see
20 <http://www.gnu.org/licenses/>. */
22 /* Inlining decision heuristics
24 The implementation of inliner is organized as follows:
26 inlining heuristics limits
28 can_inline_edge_p allow to check that particular inlining is allowed
29 by the limits specified by user (allowed function growth, growth and so
32 Functions are inlined when it is obvious the result is profitable (such
33 as functions called once or when inlining reduce code size).
34 In addition to that we perform inlining of small functions and recursive
39 The inliner itself is split into two passes:
43 Simple local inlining pass inlining callees into current function.
44 This pass makes no use of whole unit analysis and thus it can do only
45 very simple decisions based on local properties.
47 The strength of the pass is that it is run in topological order
48 (reverse postorder) on the callgraph. Functions are converted into SSA
49 form just before this pass and optimized subsequently. As a result, the
50 callees of the function seen by the early inliner was already optimized
51 and results of early inlining adds a lot of optimization opportunities
52 for the local optimization.
54 The pass handle the obvious inlining decisions within the compilation
55 unit - inlining auto inline functions, inlining for size and
58 main strength of the pass is the ability to eliminate abstraction
59 penalty in C++ code (via combination of inlining and early
60 optimization) and thus improve quality of analysis done by real IPA
63 Because of lack of whole unit knowledge, the pass can not really make
64 good code size/performance tradeoffs. It however does very simple
65 speculative inlining allowing code size to grow by
66 EARLY_INLINING_INSNS when callee is leaf function. In this case the
67 optimizations performed later are very likely to eliminate the cost.
71 This is the real inliner able to handle inlining with whole program
72 knowledge. It performs following steps:
74 1) inlining of small functions. This is implemented by greedy
75 algorithm ordering all inlinable cgraph edges by their badness and
76 inlining them in this order as long as inline limits allows doing so.
78 This heuristics is not very good on inlining recursive calls. Recursive
79 calls can be inlined with results similar to loop unrolling. To do so,
80 special purpose recursive inliner is executed on function when
81 recursive edge is met as viable candidate.
83 2) Unreachable functions are removed from callgraph. Inlining leads
84 to devirtualization and other modification of callgraph so functions
85 may become unreachable during the process. Also functions declared as
86 extern inline or virtual functions are removed, since after inlining
87 we no longer need the offline bodies.
89 3) Functions called once and not exported from the unit are inlined.
90 This should almost always lead to reduction of code size by eliminating
91 the need for offline copy of the function. */
95 #include "coretypes.h"
98 #include "tree-inline.h"
99 #include "langhooks.h"
102 #include "diagnostic.h"
103 #include "gimple-pretty-print.h"
107 #include "tree-pass.h"
108 #include "coverage.h"
111 #include "tree-flow.h"
112 #include "ipa-prop.h"
115 #include "ipa-inline.h"
116 #include "ipa-utils.h"
118 /* Statistics we collect about inlining algorithm. */
119 static int overall_size
;
120 static gcov_type max_count
;
122 /* Return false when inlining edge E would lead to violating
123 limits on function unit growth or stack usage growth.
125 The relative function body growth limit is present generally
126 to avoid problems with non-linear behavior of the compiler.
127 To allow inlining huge functions into tiny wrapper, the limit
128 is always based on the bigger of the two functions considered.
130 For stack growth limits we always base the growth in stack usage
131 of the callers. We want to prevent applications from segfaulting
132 on stack overflow when functions with huge stack frames gets
136 caller_growth_limits (struct cgraph_edge
*e
)
138 struct cgraph_node
*to
= e
->caller
;
139 struct cgraph_node
*what
= cgraph_function_or_thunk_node (e
->callee
, NULL
);
142 HOST_WIDE_INT stack_size_limit
= 0, inlined_stack
;
143 struct inline_summary
*info
, *what_info
, *outer_info
= inline_summary (to
);
145 /* Look for function e->caller is inlined to. While doing
146 so work out the largest function body on the way. As
147 described above, we want to base our function growth
148 limits based on that. Not on the self size of the
149 outer function, not on the self size of inline code
150 we immediately inline to. This is the most relaxed
151 interpretation of the rule "do not grow large functions
152 too much in order to prevent compiler from exploding". */
155 info
= inline_summary (to
);
156 if (limit
< info
->self_size
)
157 limit
= info
->self_size
;
158 if (stack_size_limit
< info
->estimated_self_stack_size
)
159 stack_size_limit
= info
->estimated_self_stack_size
;
160 if (to
->global
.inlined_to
)
161 to
= to
->callers
->caller
;
166 what_info
= inline_summary (what
);
168 if (limit
< what_info
->self_size
)
169 limit
= what_info
->self_size
;
171 limit
+= limit
* PARAM_VALUE (PARAM_LARGE_FUNCTION_GROWTH
) / 100;
173 /* Check the size after inlining against the function limits. But allow
174 the function to shrink if it went over the limits by forced inlining. */
175 newsize
= estimate_size_after_inlining (to
, e
);
176 if (newsize
>= info
->size
177 && newsize
> PARAM_VALUE (PARAM_LARGE_FUNCTION_INSNS
)
180 e
->inline_failed
= CIF_LARGE_FUNCTION_GROWTH_LIMIT
;
184 if (!what_info
->estimated_stack_size
)
187 /* FIXME: Stack size limit often prevents inlining in Fortran programs
188 due to large i/o datastructures used by the Fortran front-end.
189 We ought to ignore this limit when we know that the edge is executed
190 on every invocation of the caller (i.e. its call statement dominates
191 exit block). We do not track this information, yet. */
192 stack_size_limit
+= ((gcov_type
)stack_size_limit
193 * PARAM_VALUE (PARAM_STACK_FRAME_GROWTH
) / 100);
195 inlined_stack
= (outer_info
->stack_frame_offset
196 + outer_info
->estimated_self_stack_size
197 + what_info
->estimated_stack_size
);
198 /* Check new stack consumption with stack consumption at the place
200 if (inlined_stack
> stack_size_limit
201 /* If function already has large stack usage from sibling
202 inline call, we can inline, too.
203 This bit overoptimistically assume that we are good at stack
205 && inlined_stack
> info
->estimated_stack_size
206 && inlined_stack
> PARAM_VALUE (PARAM_LARGE_STACK_FRAME
))
208 e
->inline_failed
= CIF_LARGE_STACK_FRAME_GROWTH_LIMIT
;
214 /* Dump info about why inlining has failed. */
217 report_inline_failed_reason (struct cgraph_edge
*e
)
221 fprintf (dump_file
, " not inlinable: %s/%i -> %s/%i, %s\n",
222 xstrdup (cgraph_node_name (e
->caller
)), e
->caller
->uid
,
223 xstrdup (cgraph_node_name (e
->callee
)), e
->callee
->uid
,
224 cgraph_inline_failed_string (e
->inline_failed
));
228 /* Decide if we can inline the edge and possibly update
229 inline_failed reason.
230 We check whether inlining is possible at all and whether
231 caller growth limits allow doing so.
233 if REPORT is true, output reason to the dump file. */
236 can_inline_edge_p (struct cgraph_edge
*e
, bool report
)
238 bool inlinable
= true;
239 enum availability avail
;
240 struct cgraph_node
*callee
241 = cgraph_function_or_thunk_node (e
->callee
, &avail
);
242 tree caller_tree
= DECL_FUNCTION_SPECIFIC_OPTIMIZATION (e
->caller
->symbol
.decl
);
244 = callee
? DECL_FUNCTION_SPECIFIC_OPTIMIZATION (callee
->symbol
.decl
) : NULL
;
245 struct function
*caller_cfun
= DECL_STRUCT_FUNCTION (e
->caller
->symbol
.decl
);
246 struct function
*callee_cfun
247 = callee
? DECL_STRUCT_FUNCTION (callee
->symbol
.decl
) : NULL
;
249 if (!caller_cfun
&& e
->caller
->clone_of
)
250 caller_cfun
= DECL_STRUCT_FUNCTION (e
->caller
->clone_of
->symbol
.decl
);
252 if (!callee_cfun
&& callee
&& callee
->clone_of
)
253 callee_cfun
= DECL_STRUCT_FUNCTION (callee
->clone_of
->symbol
.decl
);
255 gcc_assert (e
->inline_failed
);
257 if (!callee
|| !callee
->analyzed
)
259 e
->inline_failed
= CIF_BODY_NOT_AVAILABLE
;
262 else if (!inline_summary (callee
)->inlinable
)
264 e
->inline_failed
= CIF_FUNCTION_NOT_INLINABLE
;
267 else if (avail
<= AVAIL_OVERWRITABLE
)
269 e
->inline_failed
= CIF_OVERWRITABLE
;
272 else if (e
->call_stmt_cannot_inline_p
)
274 e
->inline_failed
= CIF_MISMATCHED_ARGUMENTS
;
277 /* Don't inline if the functions have different EH personalities. */
278 else if (DECL_FUNCTION_PERSONALITY (e
->caller
->symbol
.decl
)
279 && DECL_FUNCTION_PERSONALITY (callee
->symbol
.decl
)
280 && (DECL_FUNCTION_PERSONALITY (e
->caller
->symbol
.decl
)
281 != DECL_FUNCTION_PERSONALITY (callee
->symbol
.decl
)))
283 e
->inline_failed
= CIF_EH_PERSONALITY
;
286 /* TM pure functions should not be inlined into non-TM_pure
288 else if (is_tm_pure (callee
->symbol
.decl
)
289 && !is_tm_pure (e
->caller
->symbol
.decl
))
291 e
->inline_failed
= CIF_UNSPECIFIED
;
294 /* Don't inline if the callee can throw non-call exceptions but the
296 FIXME: this is obviously wrong for LTO where STRUCT_FUNCTION is missing.
297 Move the flag into cgraph node or mirror it in the inline summary. */
298 else if (callee_cfun
&& callee_cfun
->can_throw_non_call_exceptions
299 && !(caller_cfun
&& caller_cfun
->can_throw_non_call_exceptions
))
301 e
->inline_failed
= CIF_NON_CALL_EXCEPTIONS
;
304 /* Check compatibility of target optimization options. */
305 else if (!targetm
.target_option
.can_inline_p (e
->caller
->symbol
.decl
,
306 callee
->symbol
.decl
))
308 e
->inline_failed
= CIF_TARGET_OPTION_MISMATCH
;
311 /* Check if caller growth allows the inlining. */
312 else if (!DECL_DISREGARD_INLINE_LIMITS (callee
->symbol
.decl
)
313 && !lookup_attribute ("flatten",
315 (e
->caller
->global
.inlined_to
316 ? e
->caller
->global
.inlined_to
->symbol
.decl
317 : e
->caller
->symbol
.decl
))
318 && !caller_growth_limits (e
))
320 /* Don't inline a function with a higher optimization level than the
321 caller. FIXME: this is really just tip of iceberg of handling
322 optimization attribute. */
323 else if (caller_tree
!= callee_tree
)
325 struct cl_optimization
*caller_opt
326 = TREE_OPTIMIZATION ((caller_tree
)
328 : optimization_default_node
);
330 struct cl_optimization
*callee_opt
331 = TREE_OPTIMIZATION ((callee_tree
)
333 : optimization_default_node
);
335 if (((caller_opt
->x_optimize
> callee_opt
->x_optimize
)
336 || (caller_opt
->x_optimize_size
!= callee_opt
->x_optimize_size
))
337 /* gcc.dg/pr43564.c. Look at forced inline even in -O0. */
338 && !DECL_DISREGARD_INLINE_LIMITS (e
->callee
->symbol
.decl
))
340 e
->inline_failed
= CIF_OPTIMIZATION_MISMATCH
;
345 if (!inlinable
&& report
)
346 report_inline_failed_reason (e
);
351 /* Return true if the edge E is inlinable during early inlining. */
354 can_early_inline_edge_p (struct cgraph_edge
*e
)
356 struct cgraph_node
*callee
= cgraph_function_or_thunk_node (e
->callee
,
358 /* Early inliner might get called at WPA stage when IPA pass adds new
359 function. In this case we can not really do any of early inlining
360 because function bodies are missing. */
361 if (!gimple_has_body_p (callee
->symbol
.decl
))
363 e
->inline_failed
= CIF_BODY_NOT_AVAILABLE
;
366 /* In early inliner some of callees may not be in SSA form yet
367 (i.e. the callgraph is cyclic and we did not process
368 the callee by early inliner, yet). We don't have CIF code for this
369 case; later we will re-do the decision in the real inliner. */
370 if (!gimple_in_ssa_p (DECL_STRUCT_FUNCTION (e
->caller
->symbol
.decl
))
371 || !gimple_in_ssa_p (DECL_STRUCT_FUNCTION (callee
->symbol
.decl
)))
374 fprintf (dump_file
, " edge not inlinable: not in SSA form\n");
377 if (!can_inline_edge_p (e
, true))
383 /* Return number of calls in N. Ignore cheap builtins. */
386 num_calls (struct cgraph_node
*n
)
388 struct cgraph_edge
*e
;
391 for (e
= n
->callees
; e
; e
= e
->next_callee
)
392 if (!is_inexpensive_builtin (e
->callee
->symbol
.decl
))
398 /* Return true if we are interested in inlining small function. */
401 want_early_inline_function_p (struct cgraph_edge
*e
)
403 bool want_inline
= true;
404 struct cgraph_node
*callee
= cgraph_function_or_thunk_node (e
->callee
, NULL
);
406 if (DECL_DISREGARD_INLINE_LIMITS (callee
->symbol
.decl
))
408 else if (!DECL_DECLARED_INLINE_P (callee
->symbol
.decl
)
409 && !flag_inline_small_functions
)
411 e
->inline_failed
= CIF_FUNCTION_NOT_INLINE_CANDIDATE
;
412 report_inline_failed_reason (e
);
417 int growth
= estimate_edge_growth (e
);
422 else if (!cgraph_maybe_hot_edge_p (e
)
426 fprintf (dump_file
, " will not early inline: %s/%i->%s/%i, "
427 "call is cold and code would grow by %i\n",
428 xstrdup (cgraph_node_name (e
->caller
)), e
->caller
->uid
,
429 xstrdup (cgraph_node_name (callee
)), callee
->uid
,
433 else if (growth
> PARAM_VALUE (PARAM_EARLY_INLINING_INSNS
))
436 fprintf (dump_file
, " will not early inline: %s/%i->%s/%i, "
437 "growth %i exceeds --param early-inlining-insns\n",
438 xstrdup (cgraph_node_name (e
->caller
)), e
->caller
->uid
,
439 xstrdup (cgraph_node_name (callee
)), callee
->uid
,
443 else if ((n
= num_calls (callee
)) != 0
444 && growth
* (n
+ 1) > PARAM_VALUE (PARAM_EARLY_INLINING_INSNS
))
447 fprintf (dump_file
, " will not early inline: %s/%i->%s/%i, "
448 "growth %i exceeds --param early-inlining-insns "
449 "divided by number of calls\n",
450 xstrdup (cgraph_node_name (e
->caller
)), e
->caller
->uid
,
451 xstrdup (cgraph_node_name (callee
)), callee
->uid
,
459 /* Compute time of the edge->caller + edge->callee execution when inlining
463 compute_uninlined_call_time (struct inline_summary
*callee_info
,
464 struct cgraph_edge
*edge
)
466 gcov_type uninlined_call_time
=
467 RDIV ((gcov_type
)callee_info
->time
* MAX (edge
->frequency
, 1),
469 gcov_type caller_time
= inline_summary (edge
->caller
->global
.inlined_to
470 ? edge
->caller
->global
.inlined_to
471 : edge
->caller
)->time
;
472 return uninlined_call_time
+ caller_time
;
475 /* Same as compute_uinlined_call_time but compute time when inlining
479 compute_inlined_call_time (struct cgraph_edge
*edge
,
482 gcov_type caller_time
= inline_summary (edge
->caller
->global
.inlined_to
483 ? edge
->caller
->global
.inlined_to
484 : edge
->caller
)->time
;
485 gcov_type time
= (caller_time
486 + RDIV (((gcov_type
) edge_time
487 - inline_edge_summary (edge
)->call_stmt_time
)
488 * MAX (edge
->frequency
, 1), CGRAPH_FREQ_BASE
));
489 /* Possible one roundoff error, but watch for overflows. */
490 gcc_checking_assert (time
>= INT_MIN
/ 2);
496 /* Return true if the speedup for inlining E is bigger than
497 PARAM_MAX_INLINE_MIN_SPEEDUP. */
500 big_speedup_p (struct cgraph_edge
*e
)
502 gcov_type time
= compute_uninlined_call_time (inline_summary (e
->callee
),
504 gcov_type inlined_time
= compute_inlined_call_time (e
,
505 estimate_edge_time (e
));
506 if (time
- inlined_time
507 > RDIV (time
* PARAM_VALUE (PARAM_INLINE_MIN_SPEEDUP
), 100))
512 /* Return true if we are interested in inlining small function.
513 When REPORT is true, report reason to dump file. */
516 want_inline_small_function_p (struct cgraph_edge
*e
, bool report
)
518 bool want_inline
= true;
519 struct cgraph_node
*callee
= cgraph_function_or_thunk_node (e
->callee
, NULL
);
521 if (DECL_DISREGARD_INLINE_LIMITS (callee
->symbol
.decl
))
523 else if (!DECL_DECLARED_INLINE_P (callee
->symbol
.decl
)
524 && !flag_inline_small_functions
)
526 e
->inline_failed
= CIF_FUNCTION_NOT_INLINE_CANDIDATE
;
531 int growth
= estimate_edge_growth (e
);
532 inline_hints hints
= estimate_edge_hints (e
);
533 bool big_speedup
= big_speedup_p (e
);
537 /* Apply MAX_INLINE_INSNS_SINGLE limit. Do not do so when
538 hints suggests that inlining given function is very profitable. */
539 else if (DECL_DECLARED_INLINE_P (callee
->symbol
.decl
)
540 && growth
>= MAX_INLINE_INSNS_SINGLE
542 && !(hints
& (INLINE_HINT_indirect_call
543 | INLINE_HINT_loop_iterations
544 | INLINE_HINT_loop_stride
)))
546 e
->inline_failed
= CIF_MAX_INLINE_INSNS_SINGLE_LIMIT
;
549 /* Before giving up based on fact that caller size will grow, allow
550 functions that are called few times and eliminating the offline
551 copy will lead to overall code size reduction.
552 Not all of these will be handled by subsequent inlining of functions
553 called once: in particular weak functions are not handled or funcitons
554 that inline to multiple calls but a lot of bodies is optimized out.
555 Finally we want to inline earlier to allow inlining of callbacks.
557 This is slightly wrong on aggressive side: it is entirely possible
558 that function is called many times with a context where inlining
559 reduces code size and few times with a context where inlining increase
560 code size. Resoluting growth estimate will be negative even if it
561 would make more sense to keep offline copy and do not inline into the
562 call sites that makes the code size grow.
564 When badness orders the calls in a way that code reducing calls come
565 first, this situation is not a problem at all: after inlining all
566 "good" calls, we will realize that keeping the function around is
568 else if (growth
<= MAX_INLINE_INSNS_SINGLE
569 /* Unlike for functions called once, we play unsafe with
570 COMDATs. We can allow that since we know functions
571 in consideration are small (and thus risk is small) and
572 moreover grow estimates already accounts that COMDAT
573 functions may or may not disappear when eliminated from
574 current unit. With good probability making aggressive
575 choice in all units is going to make overall program
578 Consequently we ask cgraph_can_remove_if_no_direct_calls_p
580 cgraph_will_be_removed_from_program_if_no_direct_calls */
581 && !DECL_EXTERNAL (callee
->symbol
.decl
)
582 && cgraph_can_remove_if_no_direct_calls_p (callee
)
583 && estimate_growth (callee
) <= 0)
585 else if (!DECL_DECLARED_INLINE_P (callee
->symbol
.decl
)
586 && !flag_inline_functions
)
588 e
->inline_failed
= CIF_NOT_DECLARED_INLINED
;
591 /* Apply MAX_INLINE_INSNS_AUTO limit for functions not declared inline
592 Upgrade it to MAX_INLINE_INSNS_SINGLE when hints suggests that
593 inlining given function is very profitable. */
594 else if (!DECL_DECLARED_INLINE_P (callee
->symbol
.decl
)
596 && growth
>= ((hints
& (INLINE_HINT_indirect_call
597 | INLINE_HINT_loop_iterations
598 | INLINE_HINT_loop_stride
))
599 ? MAX (MAX_INLINE_INSNS_AUTO
,
600 MAX_INLINE_INSNS_SINGLE
)
601 : MAX_INLINE_INSNS_AUTO
))
603 e
->inline_failed
= CIF_MAX_INLINE_INSNS_AUTO_LIMIT
;
606 /* If call is cold, do not inline when function body would grow. */
607 else if (!cgraph_maybe_hot_edge_p (e
))
609 e
->inline_failed
= CIF_UNLIKELY_CALL
;
613 if (!want_inline
&& report
)
614 report_inline_failed_reason (e
);
618 /* EDGE is self recursive edge.
619 We hand two cases - when function A is inlining into itself
620 or when function A is being inlined into another inliner copy of function
623 In first case OUTER_NODE points to the toplevel copy of A, while
624 in the second case OUTER_NODE points to the outermost copy of A in B.
626 In both cases we want to be extra selective since
627 inlining the call will just introduce new recursive calls to appear. */
630 want_inline_self_recursive_call_p (struct cgraph_edge
*edge
,
631 struct cgraph_node
*outer_node
,
635 char const *reason
= NULL
;
636 bool want_inline
= true;
637 int caller_freq
= CGRAPH_FREQ_BASE
;
638 int max_depth
= PARAM_VALUE (PARAM_MAX_INLINE_RECURSIVE_DEPTH_AUTO
);
640 if (DECL_DECLARED_INLINE_P (edge
->caller
->symbol
.decl
))
641 max_depth
= PARAM_VALUE (PARAM_MAX_INLINE_RECURSIVE_DEPTH
);
643 if (!cgraph_maybe_hot_edge_p (edge
))
645 reason
= "recursive call is cold";
648 else if (max_count
&& !outer_node
->count
)
650 reason
= "not executed in profile";
653 else if (depth
> max_depth
)
655 reason
= "--param max-inline-recursive-depth exceeded.";
659 if (outer_node
->global
.inlined_to
)
660 caller_freq
= outer_node
->callers
->frequency
;
664 /* Inlining of self recursive function into copy of itself within other function
665 is transformation similar to loop peeling.
667 Peeling is profitable if we can inline enough copies to make probability
668 of actual call to the self recursive function very small. Be sure that
669 the probability of recursion is small.
671 We ensure that the frequency of recursing is at most 1 - (1/max_depth).
672 This way the expected number of recision is at most max_depth. */
675 int max_prob
= CGRAPH_FREQ_BASE
- ((CGRAPH_FREQ_BASE
+ max_depth
- 1)
678 for (i
= 1; i
< depth
; i
++)
679 max_prob
= max_prob
* max_prob
/ CGRAPH_FREQ_BASE
;
681 && (edge
->count
* CGRAPH_FREQ_BASE
/ outer_node
->count
684 reason
= "profile of recursive call is too large";
688 && (edge
->frequency
* CGRAPH_FREQ_BASE
/ caller_freq
691 reason
= "frequency of recursive call is too large";
695 /* Recursive inlining, i.e. equivalent of unrolling, is profitable if recursion
696 depth is large. We reduce function call overhead and increase chances that
697 things fit in hardware return predictor.
699 Recursive inlining might however increase cost of stack frame setup
700 actually slowing down functions whose recursion tree is wide rather than
703 Deciding reliably on when to do recursive inlining without profile feedback
704 is tricky. For now we disable recursive inlining when probability of self
707 Recursive inlining of self recursive call within loop also results in large loop
708 depths that generally optimize badly. We may want to throttle down inlining
709 in those cases. In particular this seems to happen in one of libstdc++ rb tree
714 && (edge
->count
* 100 / outer_node
->count
715 <= PARAM_VALUE (PARAM_MIN_INLINE_RECURSIVE_PROBABILITY
)))
717 reason
= "profile of recursive call is too small";
721 && (edge
->frequency
* 100 / caller_freq
722 <= PARAM_VALUE (PARAM_MIN_INLINE_RECURSIVE_PROBABILITY
)))
724 reason
= "frequency of recursive call is too small";
728 if (!want_inline
&& dump_file
)
729 fprintf (dump_file
, " not inlining recursively: %s\n", reason
);
733 /* Return true when NODE has caller other than EDGE.
734 Worker for cgraph_for_node_and_aliases. */
737 check_caller_edge (struct cgraph_node
*node
, void *edge
)
739 return (node
->callers
740 && node
->callers
!= edge
);
744 /* Decide if inlining NODE would reduce unit size by eliminating
745 the offline copy of function.
746 When COLD is true the cold calls are considered, too. */
749 want_inline_function_to_all_callers_p (struct cgraph_node
*node
, bool cold
)
751 struct cgraph_node
*function
= cgraph_function_or_thunk_node (node
, NULL
);
752 struct cgraph_edge
*e
;
753 bool has_hot_call
= false;
755 /* Does it have callers? */
758 /* Already inlined? */
759 if (function
->global
.inlined_to
)
761 if (cgraph_function_or_thunk_node (node
, NULL
) != node
)
763 /* Inlining into all callers would increase size? */
764 if (estimate_growth (node
) > 0)
766 /* Maybe other aliases has more direct calls. */
767 if (cgraph_for_node_and_aliases (node
, check_caller_edge
, node
->callers
, true))
769 /* All inlines must be possible. */
770 for (e
= node
->callers
; e
; e
= e
->next_caller
)
772 if (!can_inline_edge_p (e
, true))
774 if (!has_hot_call
&& cgraph_maybe_hot_edge_p (e
))
778 if (!cold
&& !has_hot_call
)
783 #define RELATIVE_TIME_BENEFIT_RANGE (INT_MAX / 64)
785 /* Return relative time improvement for inlining EDGE in range
786 1...RELATIVE_TIME_BENEFIT_RANGE */
789 relative_time_benefit (struct inline_summary
*callee_info
,
790 struct cgraph_edge
*edge
,
793 gcov_type relbenefit
;
794 gcov_type uninlined_call_time
= compute_uninlined_call_time (callee_info
, edge
);
795 gcov_type inlined_call_time
= compute_inlined_call_time (edge
, edge_time
);
797 /* Inlining into extern inline function is not a win. */
798 if (DECL_EXTERNAL (edge
->caller
->global
.inlined_to
799 ? edge
->caller
->global
.inlined_to
->symbol
.decl
800 : edge
->caller
->symbol
.decl
))
803 /* Watch overflows. */
804 gcc_checking_assert (uninlined_call_time
>= 0);
805 gcc_checking_assert (inlined_call_time
>= 0);
806 gcc_checking_assert (uninlined_call_time
>= inlined_call_time
);
808 /* Compute relative time benefit, i.e. how much the call becomes faster.
809 ??? perhaps computing how much the caller+calle together become faster
810 would lead to more realistic results. */
811 if (!uninlined_call_time
)
812 uninlined_call_time
= 1;
814 RDIV (((gcov_type
)uninlined_call_time
- inlined_call_time
) * RELATIVE_TIME_BENEFIT_RANGE
,
815 uninlined_call_time
);
816 relbenefit
= MIN (relbenefit
, RELATIVE_TIME_BENEFIT_RANGE
);
817 gcc_checking_assert (relbenefit
>= 0);
818 relbenefit
= MAX (relbenefit
, 1);
823 /* A cost model driving the inlining heuristics in a way so the edges with
824 smallest badness are inlined first. After each inlining is performed
825 the costs of all caller edges of nodes affected are recomputed so the
826 metrics may accurately depend on values such as number of inlinable callers
827 of the function or function body size. */
830 edge_badness (struct cgraph_edge
*edge
, bool dump
)
833 int growth
, edge_time
;
834 struct cgraph_node
*callee
= cgraph_function_or_thunk_node (edge
->callee
,
836 struct inline_summary
*callee_info
= inline_summary (callee
);
839 if (DECL_DISREGARD_INLINE_LIMITS (callee
->symbol
.decl
))
842 growth
= estimate_edge_growth (edge
);
843 edge_time
= estimate_edge_time (edge
);
844 hints
= estimate_edge_hints (edge
);
845 gcc_checking_assert (edge_time
>= 0);
846 gcc_checking_assert (edge_time
<= callee_info
->time
);
847 gcc_checking_assert (growth
<= callee_info
->size
);
851 fprintf (dump_file
, " Badness calculation for %s -> %s\n",
852 xstrdup (cgraph_node_name (edge
->caller
)),
853 xstrdup (cgraph_node_name (callee
)));
854 fprintf (dump_file
, " size growth %i, time %i ",
857 dump_inline_hints (dump_file
, hints
);
858 if (big_speedup_p (edge
))
859 fprintf (dump_file
, " big_speedup");
860 fprintf (dump_file
, "\n");
863 /* Always prefer inlining saving code size. */
866 badness
= INT_MIN
/ 2 + growth
;
868 fprintf (dump_file
, " %i: Growth %i <= 0\n", (int) badness
,
872 /* When profiling is available, compute badness as:
874 relative_edge_count * relative_time_benefit
875 goodness = -------------------------------------------
879 The fraction is upside down, because on edge counts and time beneits
880 the bounds are known. Edge growth is essentially unlimited. */
884 int relbenefit
= relative_time_benefit (callee_info
, edge
, edge_time
);
887 ((double) edge
->count
* INT_MIN
/ 2 / max_count
/ RELATIVE_TIME_BENEFIT_RANGE
) *
888 relbenefit
) / growth
;
890 /* Be sure that insanity of the profile won't lead to increasing counts
891 in the scalling and thus to overflow in the computation above. */
892 gcc_assert (max_count
>= edge
->count
);
896 " %i (relative %f): profile info. Relative count %f"
897 " * Relative benefit %f\n",
898 (int) badness
, (double) badness
/ INT_MIN
,
899 (double) edge
->count
/ max_count
,
900 relbenefit
* 100.0 / RELATIVE_TIME_BENEFIT_RANGE
);
904 /* When function local profile is available. Compute badness as:
906 relative_time_benefit
907 goodness = ---------------------------------
908 growth_of_caller * overall_growth
912 compensated by the inline hints.
914 else if (flag_guess_branch_prob
)
916 badness
= (relative_time_benefit (callee_info
, edge
, edge_time
)
917 * (INT_MIN
/ 16 / RELATIVE_TIME_BENEFIT_RANGE
));
918 badness
/= (growth
* MAX (1, callee_info
->growth
));
919 gcc_checking_assert (badness
<=0 && badness
>= INT_MIN
/ 16);
920 if ((hints
& (INLINE_HINT_indirect_call
921 | INLINE_HINT_loop_iterations
922 | INLINE_HINT_loop_stride
))
923 || callee_info
->growth
<= 0)
925 if (hints
& (INLINE_HINT_same_scc
))
927 else if (hints
& (INLINE_HINT_in_scc
))
929 else if (hints
& (INLINE_HINT_cross_module
))
931 gcc_checking_assert (badness
<= 0 && badness
>= INT_MIN
/ 2);
932 if ((hints
& INLINE_HINT_declared_inline
) && badness
>= INT_MIN
/ 32)
937 " %i: guessed profile. frequency %f,"
938 " benefit %f%%, time w/o inlining %i, time w inlining %i"
939 " overall growth %i (current) %i (original)\n",
940 (int) badness
, (double)edge
->frequency
/ CGRAPH_FREQ_BASE
,
941 relative_time_benefit (callee_info
, edge
, edge_time
) * 100.0
942 / RELATIVE_TIME_BENEFIT_RANGE
,
943 (int)compute_uninlined_call_time (callee_info
, edge
),
944 (int)compute_inlined_call_time (edge
, edge_time
),
945 estimate_growth (callee
),
946 callee_info
->growth
);
949 /* When function local profile is not available or it does not give
950 useful information (ie frequency is zero), base the cost on
951 loop nest and overall size growth, so we optimize for overall number
952 of functions fully inlined in program. */
955 int nest
= MIN (inline_edge_summary (edge
)->loop_depth
, 8);
956 badness
= growth
* 256;
958 /* Decrease badness if call is nested. */
966 fprintf (dump_file
, " %i: no profile. nest %i\n", (int) badness
,
970 /* Ensure that we did not overflow in all the fixed point math above. */
971 gcc_assert (badness
>= INT_MIN
);
972 gcc_assert (badness
<= INT_MAX
- 1);
973 /* Make recursive inlining happen always after other inlining is done. */
974 if (cgraph_edge_recursive_p (edge
))
980 /* Recompute badness of EDGE and update its key in HEAP if needed. */
982 update_edge_key (fibheap_t heap
, struct cgraph_edge
*edge
)
984 int badness
= edge_badness (edge
, false);
987 fibnode_t n
= (fibnode_t
) edge
->aux
;
988 gcc_checking_assert (n
->data
== edge
);
990 /* fibheap_replace_key only decrease the keys.
991 When we increase the key we do not update heap
992 and instead re-insert the element once it becomes
993 a minimum of heap. */
994 if (badness
< n
->key
)
996 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
999 " decreasing badness %s/%i -> %s/%i, %i to %i\n",
1000 xstrdup (cgraph_node_name (edge
->caller
)),
1002 xstrdup (cgraph_node_name (edge
->callee
)),
1007 fibheap_replace_key (heap
, n
, badness
);
1008 gcc_checking_assert (n
->key
== badness
);
1013 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1016 " enqueuing call %s/%i -> %s/%i, badness %i\n",
1017 xstrdup (cgraph_node_name (edge
->caller
)),
1019 xstrdup (cgraph_node_name (edge
->callee
)),
1023 edge
->aux
= fibheap_insert (heap
, badness
, edge
);
1028 /* NODE was inlined.
1029 All caller edges needs to be resetted because
1030 size estimates change. Similarly callees needs reset
1031 because better context may be known. */
1034 reset_edge_caches (struct cgraph_node
*node
)
1036 struct cgraph_edge
*edge
;
1037 struct cgraph_edge
*e
= node
->callees
;
1038 struct cgraph_node
*where
= node
;
1040 struct ipa_ref
*ref
;
1042 if (where
->global
.inlined_to
)
1043 where
= where
->global
.inlined_to
;
1045 /* WHERE body size has changed, the cached growth is invalid. */
1046 reset_node_growth_cache (where
);
1048 for (edge
= where
->callers
; edge
; edge
= edge
->next_caller
)
1049 if (edge
->inline_failed
)
1050 reset_edge_growth_cache (edge
);
1051 for (i
= 0; ipa_ref_list_referring_iterate (&where
->symbol
.ref_list
,
1053 if (ref
->use
== IPA_REF_ALIAS
)
1054 reset_edge_caches (ipa_ref_referring_node (ref
));
1060 if (!e
->inline_failed
&& e
->callee
->callees
)
1061 e
= e
->callee
->callees
;
1064 if (e
->inline_failed
)
1065 reset_edge_growth_cache (e
);
1072 if (e
->caller
== node
)
1074 e
= e
->caller
->callers
;
1076 while (!e
->next_callee
);
1082 /* Recompute HEAP nodes for each of caller of NODE.
1083 UPDATED_NODES track nodes we already visited, to avoid redundant work.
1084 When CHECK_INLINABLITY_FOR is set, re-check for specified edge that
1085 it is inlinable. Otherwise check all edges. */
1088 update_caller_keys (fibheap_t heap
, struct cgraph_node
*node
,
1089 bitmap updated_nodes
,
1090 struct cgraph_edge
*check_inlinablity_for
)
1092 struct cgraph_edge
*edge
;
1094 struct ipa_ref
*ref
;
1096 if ((!node
->alias
&& !inline_summary (node
)->inlinable
)
1097 || cgraph_function_body_availability (node
) <= AVAIL_OVERWRITABLE
1098 || node
->global
.inlined_to
)
1100 if (!bitmap_set_bit (updated_nodes
, node
->uid
))
1103 for (i
= 0; ipa_ref_list_referring_iterate (&node
->symbol
.ref_list
,
1105 if (ref
->use
== IPA_REF_ALIAS
)
1107 struct cgraph_node
*alias
= ipa_ref_referring_node (ref
);
1108 update_caller_keys (heap
, alias
, updated_nodes
, check_inlinablity_for
);
1111 for (edge
= node
->callers
; edge
; edge
= edge
->next_caller
)
1112 if (edge
->inline_failed
)
1114 if (!check_inlinablity_for
1115 || check_inlinablity_for
== edge
)
1117 if (can_inline_edge_p (edge
, false)
1118 && want_inline_small_function_p (edge
, false))
1119 update_edge_key (heap
, edge
);
1122 report_inline_failed_reason (edge
);
1123 fibheap_delete_node (heap
, (fibnode_t
) edge
->aux
);
1128 update_edge_key (heap
, edge
);
1132 /* Recompute HEAP nodes for each uninlined call in NODE.
1133 This is used when we know that edge badnesses are going only to increase
1134 (we introduced new call site) and thus all we need is to insert newly
1135 created edges into heap. */
1138 update_callee_keys (fibheap_t heap
, struct cgraph_node
*node
,
1139 bitmap updated_nodes
)
1141 struct cgraph_edge
*e
= node
->callees
;
1146 if (!e
->inline_failed
&& e
->callee
->callees
)
1147 e
= e
->callee
->callees
;
1150 enum availability avail
;
1151 struct cgraph_node
*callee
;
1152 /* We do not reset callee growth cache here. Since we added a new call,
1153 growth chould have just increased and consequentely badness metric
1154 don't need updating. */
1155 if (e
->inline_failed
1156 && (callee
= cgraph_function_or_thunk_node (e
->callee
, &avail
))
1157 && inline_summary (callee
)->inlinable
1158 && cgraph_function_body_availability (callee
) >= AVAIL_AVAILABLE
1159 && !bitmap_bit_p (updated_nodes
, callee
->uid
))
1161 if (can_inline_edge_p (e
, false)
1162 && want_inline_small_function_p (e
, false))
1163 update_edge_key (heap
, e
);
1166 report_inline_failed_reason (e
);
1167 fibheap_delete_node (heap
, (fibnode_t
) e
->aux
);
1177 if (e
->caller
== node
)
1179 e
= e
->caller
->callers
;
1181 while (!e
->next_callee
);
1187 /* Enqueue all recursive calls from NODE into priority queue depending on
1188 how likely we want to recursively inline the call. */
1191 lookup_recursive_calls (struct cgraph_node
*node
, struct cgraph_node
*where
,
1194 struct cgraph_edge
*e
;
1195 enum availability avail
;
1197 for (e
= where
->callees
; e
; e
= e
->next_callee
)
1198 if (e
->callee
== node
1199 || (cgraph_function_or_thunk_node (e
->callee
, &avail
) == node
1200 && avail
> AVAIL_OVERWRITABLE
))
1202 /* When profile feedback is available, prioritize by expected number
1204 fibheap_insert (heap
,
1205 !max_count
? -e
->frequency
1206 : -(e
->count
/ ((max_count
+ (1<<24) - 1) / (1<<24))),
1209 for (e
= where
->callees
; e
; e
= e
->next_callee
)
1210 if (!e
->inline_failed
)
1211 lookup_recursive_calls (node
, e
->callee
, heap
);
1214 /* Decide on recursive inlining: in the case function has recursive calls,
1215 inline until body size reaches given argument. If any new indirect edges
1216 are discovered in the process, add them to *NEW_EDGES, unless NEW_EDGES
1220 recursive_inlining (struct cgraph_edge
*edge
,
1221 VEC (cgraph_edge_p
, heap
) **new_edges
)
1223 int limit
= PARAM_VALUE (PARAM_MAX_INLINE_INSNS_RECURSIVE_AUTO
);
1225 struct cgraph_node
*node
;
1226 struct cgraph_edge
*e
;
1227 struct cgraph_node
*master_clone
= NULL
, *next
;
1231 node
= edge
->caller
;
1232 if (node
->global
.inlined_to
)
1233 node
= node
->global
.inlined_to
;
1235 if (DECL_DECLARED_INLINE_P (node
->symbol
.decl
))
1236 limit
= PARAM_VALUE (PARAM_MAX_INLINE_INSNS_RECURSIVE
);
1238 /* Make sure that function is small enough to be considered for inlining. */
1239 if (estimate_size_after_inlining (node
, edge
) >= limit
)
1241 heap
= fibheap_new ();
1242 lookup_recursive_calls (node
, node
, heap
);
1243 if (fibheap_empty (heap
))
1245 fibheap_delete (heap
);
1251 " Performing recursive inlining on %s\n",
1252 cgraph_node_name (node
));
1254 /* Do the inlining and update list of recursive call during process. */
1255 while (!fibheap_empty (heap
))
1257 struct cgraph_edge
*curr
1258 = (struct cgraph_edge
*) fibheap_extract_min (heap
);
1259 struct cgraph_node
*cnode
, *dest
= curr
->callee
;
1261 if (!can_inline_edge_p (curr
, true))
1264 /* MASTER_CLONE is produced in the case we already started modified
1265 the function. Be sure to redirect edge to the original body before
1266 estimating growths otherwise we will be seeing growths after inlining
1267 the already modified body. */
1270 cgraph_redirect_edge_callee (curr
, master_clone
);
1271 reset_edge_growth_cache (curr
);
1274 if (estimate_size_after_inlining (node
, curr
) > limit
)
1276 cgraph_redirect_edge_callee (curr
, dest
);
1277 reset_edge_growth_cache (curr
);
1282 for (cnode
= curr
->caller
;
1283 cnode
->global
.inlined_to
; cnode
= cnode
->callers
->caller
)
1284 if (node
->symbol
.decl
1285 == cgraph_function_or_thunk_node (curr
->callee
, NULL
)->symbol
.decl
)
1288 if (!want_inline_self_recursive_call_p (curr
, node
, false, depth
))
1290 cgraph_redirect_edge_callee (curr
, dest
);
1291 reset_edge_growth_cache (curr
);
1298 " Inlining call of depth %i", depth
);
1301 fprintf (dump_file
, " called approx. %.2f times per call",
1302 (double)curr
->count
/ node
->count
);
1304 fprintf (dump_file
, "\n");
1308 /* We need original clone to copy around. */
1309 master_clone
= cgraph_clone_node (node
, node
->symbol
.decl
,
1310 node
->count
, CGRAPH_FREQ_BASE
,
1312 for (e
= master_clone
->callees
; e
; e
= e
->next_callee
)
1313 if (!e
->inline_failed
)
1314 clone_inlined_nodes (e
, true, false, NULL
);
1315 cgraph_redirect_edge_callee (curr
, master_clone
);
1316 reset_edge_growth_cache (curr
);
1319 inline_call (curr
, false, new_edges
, &overall_size
, true);
1320 lookup_recursive_calls (node
, curr
->callee
, heap
);
1324 if (!fibheap_empty (heap
) && dump_file
)
1325 fprintf (dump_file
, " Recursive inlining growth limit met.\n");
1326 fibheap_delete (heap
);
1333 "\n Inlined %i times, "
1334 "body grown from size %i to %i, time %i to %i\n", n
,
1335 inline_summary (master_clone
)->size
, inline_summary (node
)->size
,
1336 inline_summary (master_clone
)->time
, inline_summary (node
)->time
);
1338 /* Remove master clone we used for inlining. We rely that clones inlined
1339 into master clone gets queued just before master clone so we don't
1341 for (node
= cgraph_first_function (); node
!= master_clone
;
1344 next
= cgraph_next_function (node
);
1345 if (node
->global
.inlined_to
== master_clone
)
1346 cgraph_remove_node (node
);
1348 cgraph_remove_node (master_clone
);
1353 /* Given whole compilation unit estimate of INSNS, compute how large we can
1354 allow the unit to grow. */
1357 compute_max_insns (int insns
)
1359 int max_insns
= insns
;
1360 if (max_insns
< PARAM_VALUE (PARAM_LARGE_UNIT_INSNS
))
1361 max_insns
= PARAM_VALUE (PARAM_LARGE_UNIT_INSNS
);
1363 return ((HOST_WIDEST_INT
) max_insns
1364 * (100 + PARAM_VALUE (PARAM_INLINE_UNIT_GROWTH
)) / 100);
1368 /* Compute badness of all edges in NEW_EDGES and add them to the HEAP. */
1371 add_new_edges_to_heap (fibheap_t heap
, VEC (cgraph_edge_p
, heap
) *new_edges
)
1373 while (VEC_length (cgraph_edge_p
, new_edges
) > 0)
1375 struct cgraph_edge
*edge
= VEC_pop (cgraph_edge_p
, new_edges
);
1377 gcc_assert (!edge
->aux
);
1378 if (edge
->inline_failed
1379 && can_inline_edge_p (edge
, true)
1380 && want_inline_small_function_p (edge
, true))
1381 edge
->aux
= fibheap_insert (heap
, edge_badness (edge
, false), edge
);
1386 /* We use greedy algorithm for inlining of small functions:
1387 All inline candidates are put into prioritized heap ordered in
1390 The inlining of small functions is bounded by unit growth parameters. */
1393 inline_small_functions (void)
1395 struct cgraph_node
*node
;
1396 struct cgraph_edge
*edge
;
1397 fibheap_t edge_heap
= fibheap_new ();
1398 bitmap updated_nodes
= BITMAP_ALLOC (NULL
);
1399 int min_size
, max_size
;
1400 VEC (cgraph_edge_p
, heap
) *new_indirect_edges
= NULL
;
1401 int initial_size
= 0;
1402 struct cgraph_node
**order
= XCNEWVEC (struct cgraph_node
*, cgraph_n_nodes
);
1404 if (flag_indirect_inlining
)
1405 new_indirect_edges
= VEC_alloc (cgraph_edge_p
, heap
, 8);
1407 /* Compute overall unit size and other global parameters used by badness
1411 ipa_reduced_postorder (order
, true, true, NULL
);
1414 FOR_EACH_DEFINED_FUNCTION (node
)
1415 if (!node
->global
.inlined_to
)
1417 if (cgraph_function_with_gimple_body_p (node
)
1418 || node
->thunk
.thunk_p
)
1420 struct inline_summary
*info
= inline_summary (node
);
1421 struct ipa_dfs_info
*dfs
= (struct ipa_dfs_info
*) node
->symbol
.aux
;
1423 if (!DECL_EXTERNAL (node
->symbol
.decl
))
1424 initial_size
+= info
->size
;
1425 info
->growth
= estimate_growth (node
);
1426 if (dfs
&& dfs
->next_cycle
)
1428 struct cgraph_node
*n2
;
1429 int id
= dfs
->scc_no
+ 1;
1431 n2
= ((struct ipa_dfs_info
*) node
->symbol
.aux
)->next_cycle
)
1433 struct inline_summary
*info2
= inline_summary (n2
);
1441 for (edge
= node
->callers
; edge
; edge
= edge
->next_caller
)
1442 if (max_count
< edge
->count
)
1443 max_count
= edge
->count
;
1445 ipa_free_postorder_info ();
1446 initialize_growth_caches ();
1450 "\nDeciding on inlining of small functions. Starting with size %i.\n",
1453 overall_size
= initial_size
;
1454 max_size
= compute_max_insns (overall_size
);
1455 min_size
= overall_size
;
1457 /* Populate the heeap with all edges we might inline. */
1459 FOR_EACH_DEFINED_FUNCTION (node
)
1460 if (!node
->global
.inlined_to
)
1463 fprintf (dump_file
, "Enqueueing calls of %s/%i.\n",
1464 cgraph_node_name (node
), node
->uid
);
1466 for (edge
= node
->callers
; edge
; edge
= edge
->next_caller
)
1467 if (edge
->inline_failed
1468 && can_inline_edge_p (edge
, true)
1469 && want_inline_small_function_p (edge
, true)
1470 && edge
->inline_failed
)
1472 gcc_assert (!edge
->aux
);
1473 update_edge_key (edge_heap
, edge
);
1477 gcc_assert (in_lto_p
1479 || (profile_info
&& flag_branch_probabilities
));
1481 while (!fibheap_empty (edge_heap
))
1483 int old_size
= overall_size
;
1484 struct cgraph_node
*where
, *callee
;
1485 int badness
= fibheap_min_key (edge_heap
);
1486 int current_badness
;
1490 edge
= (struct cgraph_edge
*) fibheap_extract_min (edge_heap
);
1491 gcc_assert (edge
->aux
);
1493 if (!edge
->inline_failed
)
1496 /* Be sure that caches are maintained consistent.
1497 We can not make this ENABLE_CHECKING only because it cause different
1498 updates of the fibheap queue. */
1499 cached_badness
= edge_badness (edge
, false);
1500 reset_edge_growth_cache (edge
);
1501 reset_node_growth_cache (edge
->callee
);
1503 /* When updating the edge costs, we only decrease badness in the keys.
1504 Increases of badness are handled lazilly; when we see key with out
1505 of date value on it, we re-insert it now. */
1506 current_badness
= edge_badness (edge
, false);
1507 gcc_assert (cached_badness
== current_badness
);
1508 gcc_assert (current_badness
>= badness
);
1509 if (current_badness
!= badness
)
1511 edge
->aux
= fibheap_insert (edge_heap
, current_badness
, edge
);
1515 if (!can_inline_edge_p (edge
, true))
1518 callee
= cgraph_function_or_thunk_node (edge
->callee
, NULL
);
1519 growth
= estimate_edge_growth (edge
);
1523 "\nConsidering %s with %i size\n",
1524 cgraph_node_name (callee
),
1525 inline_summary (callee
)->size
);
1527 " to be inlined into %s in %s:%i\n"
1528 " Estimated growth after inlined into all is %+i insns.\n"
1529 " Estimated badness is %i, frequency %.2f.\n",
1530 cgraph_node_name (edge
->caller
),
1531 flag_wpa
? "unknown"
1532 : gimple_filename ((const_gimple
) edge
->call_stmt
),
1534 : gimple_lineno ((const_gimple
) edge
->call_stmt
),
1535 estimate_growth (callee
),
1537 edge
->frequency
/ (double)CGRAPH_FREQ_BASE
);
1539 fprintf (dump_file
," Called "HOST_WIDEST_INT_PRINT_DEC
"x\n",
1541 if (dump_flags
& TDF_DETAILS
)
1542 edge_badness (edge
, true);
1545 if (overall_size
+ growth
> max_size
1546 && !DECL_DISREGARD_INLINE_LIMITS (callee
->symbol
.decl
))
1548 edge
->inline_failed
= CIF_INLINE_UNIT_GROWTH_LIMIT
;
1549 report_inline_failed_reason (edge
);
1553 if (!want_inline_small_function_p (edge
, true))
1556 /* Heuristics for inlining small functions works poorly for
1557 recursive calls where we do efect similar to loop unrolling.
1558 When inliing such edge seems profitable, leave decision on
1559 specific inliner. */
1560 if (cgraph_edge_recursive_p (edge
))
1562 where
= edge
->caller
;
1563 if (where
->global
.inlined_to
)
1564 where
= where
->global
.inlined_to
;
1565 if (!recursive_inlining (edge
,
1566 flag_indirect_inlining
1567 ? &new_indirect_edges
: NULL
))
1569 edge
->inline_failed
= CIF_RECURSIVE_INLINING
;
1572 reset_edge_caches (where
);
1573 /* Recursive inliner inlines all recursive calls of the function
1574 at once. Consequently we need to update all callee keys. */
1575 if (flag_indirect_inlining
)
1576 add_new_edges_to_heap (edge_heap
, new_indirect_edges
);
1577 update_callee_keys (edge_heap
, where
, updated_nodes
);
1581 struct cgraph_node
*outer_node
= NULL
;
1584 /* Consider the case where self recursive function A is inlined into B.
1585 This is desired optimization in some cases, since it leads to effect
1586 similar of loop peeling and we might completely optimize out the
1587 recursive call. However we must be extra selective. */
1589 where
= edge
->caller
;
1590 while (where
->global
.inlined_to
)
1592 if (where
->symbol
.decl
== callee
->symbol
.decl
)
1593 outer_node
= where
, depth
++;
1594 where
= where
->callers
->caller
;
1597 && !want_inline_self_recursive_call_p (edge
, outer_node
,
1601 = (DECL_DISREGARD_INLINE_LIMITS (edge
->callee
->symbol
.decl
)
1602 ? CIF_RECURSIVE_INLINING
: CIF_UNSPECIFIED
);
1605 else if (depth
&& dump_file
)
1606 fprintf (dump_file
, " Peeling recursion with depth %i\n", depth
);
1608 gcc_checking_assert (!callee
->global
.inlined_to
);
1609 inline_call (edge
, true, &new_indirect_edges
, &overall_size
, true);
1610 if (flag_indirect_inlining
)
1611 add_new_edges_to_heap (edge_heap
, new_indirect_edges
);
1613 reset_edge_caches (edge
->callee
);
1614 reset_node_growth_cache (callee
);
1616 update_callee_keys (edge_heap
, where
, updated_nodes
);
1618 where
= edge
->caller
;
1619 if (where
->global
.inlined_to
)
1620 where
= where
->global
.inlined_to
;
1622 /* Our profitability metric can depend on local properties
1623 such as number of inlinable calls and size of the function body.
1624 After inlining these properties might change for the function we
1625 inlined into (since it's body size changed) and for the functions
1626 called by function we inlined (since number of it inlinable callers
1628 update_caller_keys (edge_heap
, where
, updated_nodes
, NULL
);
1629 bitmap_clear (updated_nodes
);
1634 " Inlined into %s which now has time %i and size %i,"
1635 "net change of %+i.\n",
1636 cgraph_node_name (edge
->caller
),
1637 inline_summary (edge
->caller
)->time
,
1638 inline_summary (edge
->caller
)->size
,
1639 overall_size
- old_size
);
1641 if (min_size
> overall_size
)
1643 min_size
= overall_size
;
1644 max_size
= compute_max_insns (min_size
);
1647 fprintf (dump_file
, "New minimal size reached: %i\n", min_size
);
1651 free_growth_caches ();
1652 if (new_indirect_edges
)
1653 VEC_free (cgraph_edge_p
, heap
, new_indirect_edges
);
1654 fibheap_delete (edge_heap
);
1657 "Unit growth for small function inlining: %i->%i (%i%%)\n",
1658 initial_size
, overall_size
,
1659 initial_size
? overall_size
* 100 / (initial_size
) - 100: 0);
1660 BITMAP_FREE (updated_nodes
);
1663 /* Flatten NODE. Performed both during early inlining and
1664 at IPA inlining time. */
1667 flatten_function (struct cgraph_node
*node
, bool early
)
1669 struct cgraph_edge
*e
;
1671 /* We shouldn't be called recursively when we are being processed. */
1672 gcc_assert (node
->symbol
.aux
== NULL
);
1674 node
->symbol
.aux
= (void *) node
;
1676 for (e
= node
->callees
; e
; e
= e
->next_callee
)
1678 struct cgraph_node
*orig_callee
;
1679 struct cgraph_node
*callee
= cgraph_function_or_thunk_node (e
->callee
, NULL
);
1681 /* We've hit cycle? It is time to give up. */
1682 if (callee
->symbol
.aux
)
1686 "Not inlining %s into %s to avoid cycle.\n",
1687 xstrdup (cgraph_node_name (callee
)),
1688 xstrdup (cgraph_node_name (e
->caller
)));
1689 e
->inline_failed
= CIF_RECURSIVE_INLINING
;
1693 /* When the edge is already inlined, we just need to recurse into
1694 it in order to fully flatten the leaves. */
1695 if (!e
->inline_failed
)
1697 flatten_function (callee
, early
);
1701 /* Flatten attribute needs to be processed during late inlining. For
1702 extra code quality we however do flattening during early optimization,
1705 ? !can_inline_edge_p (e
, true)
1706 : !can_early_inline_edge_p (e
))
1709 if (cgraph_edge_recursive_p (e
))
1712 fprintf (dump_file
, "Not inlining: recursive call.\n");
1716 if (gimple_in_ssa_p (DECL_STRUCT_FUNCTION (node
->symbol
.decl
))
1717 != gimple_in_ssa_p (DECL_STRUCT_FUNCTION (callee
->symbol
.decl
)))
1720 fprintf (dump_file
, "Not inlining: SSA form does not match.\n");
1724 /* Inline the edge and flatten the inline clone. Avoid
1725 recursing through the original node if the node was cloned. */
1727 fprintf (dump_file
, " Inlining %s into %s.\n",
1728 xstrdup (cgraph_node_name (callee
)),
1729 xstrdup (cgraph_node_name (e
->caller
)));
1730 orig_callee
= callee
;
1731 inline_call (e
, true, NULL
, NULL
, false);
1732 if (e
->callee
!= orig_callee
)
1733 orig_callee
->symbol
.aux
= (void *) node
;
1734 flatten_function (e
->callee
, early
);
1735 if (e
->callee
!= orig_callee
)
1736 orig_callee
->symbol
.aux
= NULL
;
1739 node
->symbol
.aux
= NULL
;
1740 if (!node
->global
.inlined_to
)
1741 inline_update_overall_summary (node
);
1744 /* Decide on the inlining. We do so in the topological order to avoid
1745 expenses on updating data structures. */
1750 struct cgraph_node
*node
;
1752 struct cgraph_node
**order
=
1753 XCNEWVEC (struct cgraph_node
*, cgraph_n_nodes
);
1756 if (in_lto_p
&& optimize
)
1757 ipa_update_after_lto_read ();
1760 dump_inline_summaries (dump_file
);
1762 nnodes
= ipa_reverse_postorder (order
);
1764 FOR_EACH_FUNCTION (node
)
1765 node
->symbol
.aux
= 0;
1768 fprintf (dump_file
, "\nFlattening functions:\n");
1770 /* In the first pass handle functions to be flattened. Do this with
1771 a priority so none of our later choices will make this impossible. */
1772 for (i
= nnodes
- 1; i
>= 0; i
--)
1776 /* Handle nodes to be flattened.
1777 Ideally when processing callees we stop inlining at the
1778 entry of cycles, possibly cloning that entry point and
1779 try to flatten itself turning it into a self-recursive
1781 if (lookup_attribute ("flatten",
1782 DECL_ATTRIBUTES (node
->symbol
.decl
)) != NULL
)
1786 "Flattening %s\n", cgraph_node_name (node
));
1787 flatten_function (node
, false);
1791 inline_small_functions ();
1792 symtab_remove_unreachable_nodes (true, dump_file
);
1795 /* Inline functions with a property that after inlining into all callers the
1796 code size will shrink because the out-of-line copy is eliminated.
1797 We do this regardless on the callee size as long as function growth limits
1799 if (flag_inline_functions_called_once
)
1804 "\nDeciding on functions to be inlined into all callers:\n");
1806 /* Inlining one function called once has good chance of preventing
1807 inlining other function into the same callee. Ideally we should
1808 work in priority order, but probably inlining hot functions first
1809 is good cut without the extra pain of maintaining the queue.
1811 ??? this is not really fitting the bill perfectly: inlining function
1812 into callee often leads to better optimization of callee due to
1813 increased context for optimization.
1814 For example if main() function calls a function that outputs help
1815 and then function that does the main optmization, we should inline
1816 the second with priority even if both calls are cold by themselves.
1818 We probably want to implement new predicate replacing our use of
1819 maybe_hot_edge interpreted as maybe_hot_edge || callee is known
1821 for (cold
= 0; cold
<= 1; cold
++)
1823 FOR_EACH_DEFINED_FUNCTION (node
)
1825 if (want_inline_function_to_all_callers_p (node
, cold
))
1828 struct cgraph_edge
*e
;
1829 for (e
= node
->callers
; e
; e
= e
->next_caller
)
1831 while (node
->callers
&& !node
->global
.inlined_to
)
1833 struct cgraph_node
*caller
= node
->callers
->caller
;
1838 "\nInlining %s size %i.\n",
1839 cgraph_node_name (node
),
1840 inline_summary (node
)->size
);
1842 " Called once from %s %i insns.\n",
1843 cgraph_node_name (node
->callers
->caller
),
1844 inline_summary (node
->callers
->caller
)->size
);
1847 inline_call (node
->callers
, true, NULL
, NULL
, true);
1850 " Inlined into %s which now has %i size\n",
1851 cgraph_node_name (caller
),
1852 inline_summary (caller
)->size
);
1856 fprintf (dump_file
, "New calls found; giving up.\n");
1865 /* Free ipa-prop structures if they are no longer needed. */
1867 ipa_free_all_structures_after_iinln ();
1871 "\nInlined %i calls, eliminated %i functions\n\n",
1872 ncalls_inlined
, nfunctions_inlined
);
1875 dump_inline_summaries (dump_file
);
1876 /* In WPA we use inline summaries for partitioning process. */
1878 inline_free_summary ();
1882 /* Inline always-inline function calls in NODE. */
1885 inline_always_inline_functions (struct cgraph_node
*node
)
1887 struct cgraph_edge
*e
;
1888 bool inlined
= false;
1890 for (e
= node
->callees
; e
; e
= e
->next_callee
)
1892 struct cgraph_node
*callee
= cgraph_function_or_thunk_node (e
->callee
, NULL
);
1893 if (!DECL_DISREGARD_INLINE_LIMITS (callee
->symbol
.decl
))
1896 if (cgraph_edge_recursive_p (e
))
1899 fprintf (dump_file
, " Not inlining recursive call to %s.\n",
1900 cgraph_node_name (e
->callee
));
1901 e
->inline_failed
= CIF_RECURSIVE_INLINING
;
1905 if (!can_early_inline_edge_p (e
))
1909 fprintf (dump_file
, " Inlining %s into %s (always_inline).\n",
1910 xstrdup (cgraph_node_name (e
->callee
)),
1911 xstrdup (cgraph_node_name (e
->caller
)));
1912 inline_call (e
, true, NULL
, NULL
, false);
1916 inline_update_overall_summary (node
);
1921 /* Decide on the inlining. We do so in the topological order to avoid
1922 expenses on updating data structures. */
1925 early_inline_small_functions (struct cgraph_node
*node
)
1927 struct cgraph_edge
*e
;
1928 bool inlined
= false;
1930 for (e
= node
->callees
; e
; e
= e
->next_callee
)
1932 struct cgraph_node
*callee
= cgraph_function_or_thunk_node (e
->callee
, NULL
);
1933 if (!inline_summary (callee
)->inlinable
1934 || !e
->inline_failed
)
1937 /* Do not consider functions not declared inline. */
1938 if (!DECL_DECLARED_INLINE_P (callee
->symbol
.decl
)
1939 && !flag_inline_small_functions
1940 && !flag_inline_functions
)
1944 fprintf (dump_file
, "Considering inline candidate %s.\n",
1945 cgraph_node_name (callee
));
1947 if (!can_early_inline_edge_p (e
))
1950 if (cgraph_edge_recursive_p (e
))
1953 fprintf (dump_file
, " Not inlining: recursive call.\n");
1957 if (!want_early_inline_function_p (e
))
1961 fprintf (dump_file
, " Inlining %s into %s.\n",
1962 xstrdup (cgraph_node_name (callee
)),
1963 xstrdup (cgraph_node_name (e
->caller
)));
1964 inline_call (e
, true, NULL
, NULL
, true);
1971 /* Do inlining of small functions. Doing so early helps profiling and other
1972 passes to be somewhat more effective and avoids some code duplication in
1973 later real inlining pass for testcases with very many function calls. */
1975 early_inliner (void)
1977 struct cgraph_node
*node
= cgraph_get_node (current_function_decl
);
1978 struct cgraph_edge
*edge
;
1979 unsigned int todo
= 0;
1981 bool inlined
= false;
1986 /* Do nothing if datastructures for ipa-inliner are already computed. This
1987 happens when some pass decides to construct new function and
1988 cgraph_add_new_function calls lowering passes and early optimization on
1989 it. This may confuse ourself when early inliner decide to inline call to
1990 function clone, because function clones don't have parameter list in
1991 ipa-prop matching their signature. */
1992 if (ipa_node_params_vector
)
1995 #ifdef ENABLE_CHECKING
1996 verify_cgraph_node (node
);
1999 /* Even when not optimizing or not inlining inline always-inline
2001 inlined
= inline_always_inline_functions (node
);
2005 || !flag_early_inlining
2006 /* Never inline regular functions into always-inline functions
2007 during incremental inlining. This sucks as functions calling
2008 always inline functions will get less optimized, but at the
2009 same time inlining of functions calling always inline
2010 function into an always inline function might introduce
2011 cycles of edges to be always inlined in the callgraph.
2013 We might want to be smarter and just avoid this type of inlining. */
2014 || DECL_DISREGARD_INLINE_LIMITS (node
->symbol
.decl
))
2016 else if (lookup_attribute ("flatten",
2017 DECL_ATTRIBUTES (node
->symbol
.decl
)) != NULL
)
2019 /* When the function is marked to be flattened, recursively inline
2023 "Flattening %s\n", cgraph_node_name (node
));
2024 flatten_function (node
, true);
2029 /* We iterate incremental inlining to get trivial cases of indirect
2031 while (iterations
< PARAM_VALUE (PARAM_EARLY_INLINER_MAX_ITERATIONS
)
2032 && early_inline_small_functions (node
))
2034 timevar_push (TV_INTEGRATION
);
2035 todo
|= optimize_inline_calls (current_function_decl
);
2037 /* Technically we ought to recompute inline parameters so the new
2038 iteration of early inliner works as expected. We however have
2039 values approximately right and thus we only need to update edge
2040 info that might be cleared out for newly discovered edges. */
2041 for (edge
= node
->callees
; edge
; edge
= edge
->next_callee
)
2043 struct inline_edge_summary
*es
= inline_edge_summary (edge
);
2045 = estimate_num_insns (edge
->call_stmt
, &eni_size_weights
);
2047 = estimate_num_insns (edge
->call_stmt
, &eni_time_weights
);
2048 if (edge
->callee
->symbol
.decl
2049 && !gimple_check_call_matching_types (edge
->call_stmt
,
2050 edge
->callee
->symbol
.decl
))
2051 edge
->call_stmt_cannot_inline_p
= true;
2053 timevar_pop (TV_INTEGRATION
);
2058 fprintf (dump_file
, "Iterations: %i\n", iterations
);
2063 timevar_push (TV_INTEGRATION
);
2064 todo
|= optimize_inline_calls (current_function_decl
);
2065 timevar_pop (TV_INTEGRATION
);
2068 cfun
->always_inline_functions_inlined
= true;
2073 struct gimple_opt_pass pass_early_inline
=
2077 "einline", /* name */
2078 OPTGROUP_INLINE
, /* optinfo_flags */
2080 early_inliner
, /* execute */
2083 0, /* static_pass_number */
2084 TV_EARLY_INLINING
, /* tv_id */
2085 PROP_ssa
, /* properties_required */
2086 0, /* properties_provided */
2087 0, /* properties_destroyed */
2088 0, /* todo_flags_start */
2089 0 /* todo_flags_finish */
2094 /* When to run IPA inlining. Inlining of always-inline functions
2095 happens during early inlining.
2097 Enable inlining unconditoinally at -flto. We need size estimates to
2098 drive partitioning. */
2101 gate_ipa_inline (void)
2103 return optimize
|| flag_lto
|| flag_wpa
;
2106 struct ipa_opt_pass_d pass_ipa_inline
=
2110 "inline", /* name */
2111 OPTGROUP_INLINE
, /* optinfo_flags */
2112 gate_ipa_inline
, /* gate */
2113 ipa_inline
, /* execute */
2116 0, /* static_pass_number */
2117 TV_IPA_INLINING
, /* tv_id */
2118 0, /* properties_required */
2119 0, /* properties_provided */
2120 0, /* properties_destroyed */
2121 TODO_remove_functions
, /* todo_flags_finish */
2123 | TODO_remove_functions
| TODO_ggc_collect
/* todo_flags_finish */
2125 inline_generate_summary
, /* generate_summary */
2126 inline_write_summary
, /* write_summary */
2127 inline_read_summary
, /* read_summary */
2128 NULL
, /* write_optimization_summary */
2129 NULL
, /* read_optimization_summary */
2130 NULL
, /* stmt_fixup */
2132 inline_transform
, /* function_transform */
2133 NULL
, /* variable_transform */