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 true when N is leaf function. Accept cheap builtins
384 in leaf functions. */
387 leaf_node_p (struct cgraph_node
*n
)
389 struct cgraph_edge
*e
;
390 for (e
= n
->callees
; e
; e
= e
->next_callee
)
391 if (!is_inexpensive_builtin (e
->callee
->symbol
.decl
))
397 /* Return true if we are interested in inlining small function. */
400 want_early_inline_function_p (struct cgraph_edge
*e
)
402 bool want_inline
= true;
403 struct cgraph_node
*callee
= cgraph_function_or_thunk_node (e
->callee
, NULL
);
405 if (DECL_DISREGARD_INLINE_LIMITS (callee
->symbol
.decl
))
407 else if (!DECL_DECLARED_INLINE_P (callee
->symbol
.decl
)
408 && !flag_inline_small_functions
)
410 e
->inline_failed
= CIF_FUNCTION_NOT_INLINE_CANDIDATE
;
411 report_inline_failed_reason (e
);
416 int growth
= estimate_edge_growth (e
);
419 else if (!cgraph_maybe_hot_edge_p (e
)
423 fprintf (dump_file
, " will not early inline: %s/%i->%s/%i, "
424 "call is cold and code would grow by %i\n",
425 xstrdup (cgraph_node_name (e
->caller
)), e
->caller
->uid
,
426 xstrdup (cgraph_node_name (callee
)), callee
->uid
,
430 else if (!leaf_node_p (callee
)
434 fprintf (dump_file
, " will not early inline: %s/%i->%s/%i, "
435 "callee is not leaf and code would grow by %i\n",
436 xstrdup (cgraph_node_name (e
->caller
)), e
->caller
->uid
,
437 xstrdup (cgraph_node_name (callee
)), callee
->uid
,
441 else if (growth
> PARAM_VALUE (PARAM_EARLY_INLINING_INSNS
))
444 fprintf (dump_file
, " will not early inline: %s/%i->%s/%i, "
445 "growth %i exceeds --param early-inlining-insns\n",
446 xstrdup (cgraph_node_name (e
->caller
)), e
->caller
->uid
,
447 xstrdup (cgraph_node_name (callee
)), callee
->uid
,
455 /* Return true if we are interested in inlining small function.
456 When REPORT is true, report reason to dump file. */
459 want_inline_small_function_p (struct cgraph_edge
*e
, bool report
)
461 bool want_inline
= true;
462 struct cgraph_node
*callee
= cgraph_function_or_thunk_node (e
->callee
, NULL
);
464 if (DECL_DISREGARD_INLINE_LIMITS (callee
->symbol
.decl
))
466 else if (!DECL_DECLARED_INLINE_P (callee
->symbol
.decl
)
467 && !flag_inline_small_functions
)
469 e
->inline_failed
= CIF_FUNCTION_NOT_INLINE_CANDIDATE
;
474 int growth
= estimate_edge_growth (e
);
475 inline_hints hints
= estimate_edge_hints (e
);
479 /* Apply MAX_INLINE_INSNS_SINGLE limit. Do not do so when
480 hints suggests that inlining given function is very profitable. */
481 else if (DECL_DECLARED_INLINE_P (callee
->symbol
.decl
)
482 && growth
>= MAX_INLINE_INSNS_SINGLE
483 && !(hints
& (INLINE_HINT_indirect_call
484 | INLINE_HINT_loop_iterations
)))
486 e
->inline_failed
= CIF_MAX_INLINE_INSNS_SINGLE_LIMIT
;
489 /* Before giving up based on fact that caller size will grow, allow
490 functions that are called few times and eliminating the offline
491 copy will lead to overall code size reduction.
492 Not all of these will be handled by subsequent inlining of functions
493 called once: in particular weak functions are not handled or funcitons
494 that inline to multiple calls but a lot of bodies is optimized out.
495 Finally we want to inline earlier to allow inlining of callbacks.
497 This is slightly wrong on aggressive side: it is entirely possible
498 that function is called many times with a context where inlining
499 reduces code size and few times with a context where inlining increase
500 code size. Resoluting growth estimate will be negative even if it
501 would make more sense to keep offline copy and do not inline into the
502 call sites that makes the code size grow.
504 When badness orders the calls in a way that code reducing calls come
505 first, this situation is not a problem at all: after inlining all
506 "good" calls, we will realize that keeping the function around is
508 else if (growth
<= MAX_INLINE_INSNS_SINGLE
509 /* Unlike for functions called once, we play unsafe with
510 COMDATs. We can allow that since we know functions
511 in consideration are small (and thus risk is small) and
512 moreover grow estimates already accounts that COMDAT
513 functions may or may not disappear when eliminated from
514 current unit. With good probability making aggressive
515 choice in all units is going to make overall program
518 Consequently we ask cgraph_can_remove_if_no_direct_calls_p
520 cgraph_will_be_removed_from_program_if_no_direct_calls */
521 && !DECL_EXTERNAL (callee
->symbol
.decl
)
522 && cgraph_can_remove_if_no_direct_calls_p (callee
)
523 && estimate_growth (callee
) <= 0)
525 else if (!DECL_DECLARED_INLINE_P (callee
->symbol
.decl
)
526 && !flag_inline_functions
)
528 e
->inline_failed
= CIF_NOT_DECLARED_INLINED
;
531 /* Apply MAX_INLINE_INSNS_AUTO limit for functions not declared inline
532 Upgrade it to MAX_INLINE_INSNS_SINGLE when hints suggests that
533 inlining given function is very profitable. */
534 else if (!DECL_DECLARED_INLINE_P (callee
->symbol
.decl
)
535 && growth
>= ((hints
& INLINE_HINT_indirect_call
)
536 ? MAX (MAX_INLINE_INSNS_AUTO
,
537 MAX_INLINE_INSNS_SINGLE
)
538 : MAX_INLINE_INSNS_AUTO
))
540 e
->inline_failed
= CIF_MAX_INLINE_INSNS_AUTO_LIMIT
;
543 /* If call is cold, do not inline when function body would grow. */
544 else if (!cgraph_maybe_hot_edge_p (e
))
546 e
->inline_failed
= CIF_UNLIKELY_CALL
;
550 if (!want_inline
&& report
)
551 report_inline_failed_reason (e
);
555 /* EDGE is self recursive edge.
556 We hand two cases - when function A is inlining into itself
557 or when function A is being inlined into another inliner copy of function
560 In first case OUTER_NODE points to the toplevel copy of A, while
561 in the second case OUTER_NODE points to the outermost copy of A in B.
563 In both cases we want to be extra selective since
564 inlining the call will just introduce new recursive calls to appear. */
567 want_inline_self_recursive_call_p (struct cgraph_edge
*edge
,
568 struct cgraph_node
*outer_node
,
572 char const *reason
= NULL
;
573 bool want_inline
= true;
574 int caller_freq
= CGRAPH_FREQ_BASE
;
575 int max_depth
= PARAM_VALUE (PARAM_MAX_INLINE_RECURSIVE_DEPTH_AUTO
);
577 if (DECL_DECLARED_INLINE_P (edge
->caller
->symbol
.decl
))
578 max_depth
= PARAM_VALUE (PARAM_MAX_INLINE_RECURSIVE_DEPTH
);
580 if (!cgraph_maybe_hot_edge_p (edge
))
582 reason
= "recursive call is cold";
585 else if (max_count
&& !outer_node
->count
)
587 reason
= "not executed in profile";
590 else if (depth
> max_depth
)
592 reason
= "--param max-inline-recursive-depth exceeded.";
596 if (outer_node
->global
.inlined_to
)
597 caller_freq
= outer_node
->callers
->frequency
;
601 /* Inlining of self recursive function into copy of itself within other function
602 is transformation similar to loop peeling.
604 Peeling is profitable if we can inline enough copies to make probability
605 of actual call to the self recursive function very small. Be sure that
606 the probability of recursion is small.
608 We ensure that the frequency of recursing is at most 1 - (1/max_depth).
609 This way the expected number of recision is at most max_depth. */
612 int max_prob
= CGRAPH_FREQ_BASE
- ((CGRAPH_FREQ_BASE
+ max_depth
- 1)
615 for (i
= 1; i
< depth
; i
++)
616 max_prob
= max_prob
* max_prob
/ CGRAPH_FREQ_BASE
;
618 && (edge
->count
* CGRAPH_FREQ_BASE
/ outer_node
->count
621 reason
= "profile of recursive call is too large";
625 && (edge
->frequency
* CGRAPH_FREQ_BASE
/ caller_freq
628 reason
= "frequency of recursive call is too large";
632 /* Recursive inlining, i.e. equivalent of unrolling, is profitable if recursion
633 depth is large. We reduce function call overhead and increase chances that
634 things fit in hardware return predictor.
636 Recursive inlining might however increase cost of stack frame setup
637 actually slowing down functions whose recursion tree is wide rather than
640 Deciding reliably on when to do recursive inlining without profile feedback
641 is tricky. For now we disable recursive inlining when probability of self
644 Recursive inlining of self recursive call within loop also results in large loop
645 depths that generally optimize badly. We may want to throttle down inlining
646 in those cases. In particular this seems to happen in one of libstdc++ rb tree
651 && (edge
->count
* 100 / outer_node
->count
652 <= PARAM_VALUE (PARAM_MIN_INLINE_RECURSIVE_PROBABILITY
)))
654 reason
= "profile of recursive call is too small";
658 && (edge
->frequency
* 100 / caller_freq
659 <= PARAM_VALUE (PARAM_MIN_INLINE_RECURSIVE_PROBABILITY
)))
661 reason
= "frequency of recursive call is too small";
665 if (!want_inline
&& dump_file
)
666 fprintf (dump_file
, " not inlining recursively: %s\n", reason
);
670 /* Return true when NODE has caller other than EDGE.
671 Worker for cgraph_for_node_and_aliases. */
674 check_caller_edge (struct cgraph_node
*node
, void *edge
)
676 return (node
->callers
677 && node
->callers
!= edge
);
681 /* Decide if NODE is called once inlining it would eliminate need
682 for the offline copy of function. */
685 want_inline_function_called_once_p (struct cgraph_node
*node
)
687 struct cgraph_node
*function
= cgraph_function_or_thunk_node (node
, NULL
);
688 /* Already inlined? */
689 if (function
->global
.inlined_to
)
691 /* Zero or more then one callers? */
693 || node
->callers
->next_caller
)
695 /* Maybe other aliases has more direct calls. */
696 if (cgraph_for_node_and_aliases (node
, check_caller_edge
, node
->callers
, true))
698 /* Recursive call makes no sense to inline. */
699 if (cgraph_edge_recursive_p (node
->callers
))
701 /* External functions are not really in the unit, so inlining
702 them when called once would just increase the program size. */
703 if (DECL_EXTERNAL (function
->symbol
.decl
))
705 /* Offline body must be optimized out. */
706 if (!cgraph_will_be_removed_from_program_if_no_direct_calls (function
))
708 if (!can_inline_edge_p (node
->callers
, true))
714 /* Return relative time improvement for inlining EDGE in range
718 relative_time_benefit (struct inline_summary
*callee_info
,
719 struct cgraph_edge
*edge
,
723 gcov_type uninlined_call_time
;
725 uninlined_call_time
=
728 + inline_edge_summary (edge
)->call_stmt_time
) * edge
->frequency
729 + CGRAPH_FREQ_BASE
/ 2) / CGRAPH_FREQ_BASE
;
730 /* Compute relative time benefit, i.e. how much the call becomes faster.
731 ??? perhaps computing how much the caller+calle together become faster
732 would lead to more realistic results. */
733 if (!uninlined_call_time
)
734 uninlined_call_time
= 1;
736 (uninlined_call_time
- time_growth
) * 256 / (uninlined_call_time
);
737 relbenefit
= MIN (relbenefit
, 512);
738 relbenefit
= MAX (relbenefit
, 1);
743 /* A cost model driving the inlining heuristics in a way so the edges with
744 smallest badness are inlined first. After each inlining is performed
745 the costs of all caller edges of nodes affected are recomputed so the
746 metrics may accurately depend on values such as number of inlinable callers
747 of the function or function body size. */
750 edge_badness (struct cgraph_edge
*edge
, bool dump
)
753 int growth
, time_growth
;
754 struct cgraph_node
*callee
= cgraph_function_or_thunk_node (edge
->callee
,
756 struct inline_summary
*callee_info
= inline_summary (callee
);
759 if (DECL_DISREGARD_INLINE_LIMITS (callee
->symbol
.decl
))
762 growth
= estimate_edge_growth (edge
);
763 time_growth
= estimate_edge_time (edge
);
764 hints
= estimate_edge_hints (edge
);
768 fprintf (dump_file
, " Badness calculation for %s -> %s\n",
769 xstrdup (cgraph_node_name (edge
->caller
)),
770 xstrdup (cgraph_node_name (callee
)));
771 fprintf (dump_file
, " size growth %i, time growth %i ",
774 dump_inline_hints (dump_file
, hints
);
775 fprintf (dump_file
, "\n");
778 /* Always prefer inlining saving code size. */
781 badness
= INT_MIN
/ 2 + growth
;
783 fprintf (dump_file
, " %i: Growth %i <= 0\n", (int) badness
,
787 /* When profiling is available, compute badness as:
789 relative_edge_count * relative_time_benefit
790 goodness = -------------------------------------------
794 The fraction is upside down, because on edge counts and time beneits
795 the bounds are known. Edge growth is essentially unlimited. */
799 int relbenefit
= relative_time_benefit (callee_info
, edge
, time_growth
);
802 ((double) edge
->count
* INT_MIN
/ 2 / max_count
/ 512) *
803 relative_time_benefit (callee_info
, edge
, time_growth
)) / growth
;
805 /* Be sure that insanity of the profile won't lead to increasing counts
806 in the scalling and thus to overflow in the computation above. */
807 gcc_assert (max_count
>= edge
->count
);
811 " %i (relative %f): profile info. Relative count %f"
812 " * Relative benefit %f\n",
813 (int) badness
, (double) badness
/ INT_MIN
,
814 (double) edge
->count
/ max_count
,
815 relbenefit
* 100 / 256.0);
819 /* When function local profile is available. Compute badness as:
823 badness = -------------------------------------- + growth_for-all
824 relative_time_benefit * edge_frequency
827 else if (flag_guess_branch_prob
)
829 int div
= edge
->frequency
* (1<<10) / CGRAPH_FREQ_MAX
;
832 gcc_checking_assert (edge
->frequency
<= CGRAPH_FREQ_MAX
);
833 div
*= relative_time_benefit (callee_info
, edge
, time_growth
);
835 /* frequency is normalized in range 1...2^10.
836 relbenefit in range 1...2^9
837 DIV should be in range 1....2^19. */
838 gcc_checking_assert (div
>= 1 && div
<= (1<<19));
840 /* Result must be integer in range 0...INT_MAX.
841 Set the base of fixed point calculation so we don't lose much of
842 precision for small bandesses (those are interesting) yet we don't
843 overflow for growths that are still in interesting range.
845 Fixed point arithmetic with point at 8th bit. */
846 badness
= ((gcov_type
)growth
) * (1<<(19+8));
847 badness
= (badness
+ div
/ 2) / div
;
849 /* Overall growth of inlining all calls of function matters: we want to
850 inline so offline copy of function is no longer needed.
852 Additionally functions that can be fully inlined without much of
853 effort are better inline candidates than functions that can be fully
854 inlined only after noticeable overall unit growths. The latter
855 are better in a sense compressing of code size by factoring out common
856 code into separate function shared by multiple code paths.
858 We might mix the valud into the fraction by taking into account
859 relative growth of the unit, but for now just add the number
860 into resulting fraction. */
861 if (badness
> INT_MAX
/ 2)
863 badness
= INT_MAX
/ 2;
865 fprintf (dump_file
, "Badness overflow\n");
867 if (hints
& (INLINE_HINT_indirect_call
868 | INLINE_HINT_loop_iterations
))
873 " %i: guessed profile. frequency %f,"
874 " benefit %f%%, divisor %i\n",
875 (int) badness
, (double)edge
->frequency
/ CGRAPH_FREQ_BASE
,
876 relative_time_benefit (callee_info
, edge
, time_growth
) * 100 / 256.0, div
);
879 /* When function local profile is not available or it does not give
880 useful information (ie frequency is zero), base the cost on
881 loop nest and overall size growth, so we optimize for overall number
882 of functions fully inlined in program. */
885 int nest
= MIN (inline_edge_summary (edge
)->loop_depth
, 8);
886 badness
= growth
* 256;
888 /* Decrease badness if call is nested. */
896 fprintf (dump_file
, " %i: no profile. nest %i\n", (int) badness
,
900 /* Ensure that we did not overflow in all the fixed point math above. */
901 gcc_assert (badness
>= INT_MIN
);
902 gcc_assert (badness
<= INT_MAX
- 1);
903 /* Make recursive inlining happen always after other inlining is done. */
904 if (cgraph_edge_recursive_p (edge
))
910 /* Recompute badness of EDGE and update its key in HEAP if needed. */
912 update_edge_key (fibheap_t heap
, struct cgraph_edge
*edge
)
914 int badness
= edge_badness (edge
, false);
917 fibnode_t n
= (fibnode_t
) edge
->aux
;
918 gcc_checking_assert (n
->data
== edge
);
920 /* fibheap_replace_key only decrease the keys.
921 When we increase the key we do not update heap
922 and instead re-insert the element once it becomes
923 a minimum of heap. */
924 if (badness
< n
->key
)
926 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
929 " decreasing badness %s/%i -> %s/%i, %i to %i\n",
930 xstrdup (cgraph_node_name (edge
->caller
)),
932 xstrdup (cgraph_node_name (edge
->callee
)),
937 fibheap_replace_key (heap
, n
, badness
);
938 gcc_checking_assert (n
->key
== badness
);
943 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
946 " enqueuing call %s/%i -> %s/%i, badness %i\n",
947 xstrdup (cgraph_node_name (edge
->caller
)),
949 xstrdup (cgraph_node_name (edge
->callee
)),
953 edge
->aux
= fibheap_insert (heap
, badness
, edge
);
959 All caller edges needs to be resetted because
960 size estimates change. Similarly callees needs reset
961 because better context may be known. */
964 reset_edge_caches (struct cgraph_node
*node
)
966 struct cgraph_edge
*edge
;
967 struct cgraph_edge
*e
= node
->callees
;
968 struct cgraph_node
*where
= node
;
972 if (where
->global
.inlined_to
)
973 where
= where
->global
.inlined_to
;
975 /* WHERE body size has changed, the cached growth is invalid. */
976 reset_node_growth_cache (where
);
978 for (edge
= where
->callers
; edge
; edge
= edge
->next_caller
)
979 if (edge
->inline_failed
)
980 reset_edge_growth_cache (edge
);
981 for (i
= 0; ipa_ref_list_referring_iterate (&where
->symbol
.ref_list
,
983 if (ref
->use
== IPA_REF_ALIAS
)
984 reset_edge_caches (ipa_ref_referring_node (ref
));
990 if (!e
->inline_failed
&& e
->callee
->callees
)
991 e
= e
->callee
->callees
;
994 if (e
->inline_failed
)
995 reset_edge_growth_cache (e
);
1002 if (e
->caller
== node
)
1004 e
= e
->caller
->callers
;
1006 while (!e
->next_callee
);
1012 /* Recompute HEAP nodes for each of caller of NODE.
1013 UPDATED_NODES track nodes we already visited, to avoid redundant work.
1014 When CHECK_INLINABLITY_FOR is set, re-check for specified edge that
1015 it is inlinable. Otherwise check all edges. */
1018 update_caller_keys (fibheap_t heap
, struct cgraph_node
*node
,
1019 bitmap updated_nodes
,
1020 struct cgraph_edge
*check_inlinablity_for
)
1022 struct cgraph_edge
*edge
;
1024 struct ipa_ref
*ref
;
1026 if ((!node
->alias
&& !inline_summary (node
)->inlinable
)
1027 || cgraph_function_body_availability (node
) <= AVAIL_OVERWRITABLE
1028 || node
->global
.inlined_to
)
1030 if (!bitmap_set_bit (updated_nodes
, node
->uid
))
1033 for (i
= 0; ipa_ref_list_referring_iterate (&node
->symbol
.ref_list
,
1035 if (ref
->use
== IPA_REF_ALIAS
)
1037 struct cgraph_node
*alias
= ipa_ref_referring_node (ref
);
1038 update_caller_keys (heap
, alias
, updated_nodes
, check_inlinablity_for
);
1041 for (edge
= node
->callers
; edge
; edge
= edge
->next_caller
)
1042 if (edge
->inline_failed
)
1044 if (!check_inlinablity_for
1045 || check_inlinablity_for
== edge
)
1047 if (can_inline_edge_p (edge
, false)
1048 && want_inline_small_function_p (edge
, false))
1049 update_edge_key (heap
, edge
);
1052 report_inline_failed_reason (edge
);
1053 fibheap_delete_node (heap
, (fibnode_t
) edge
->aux
);
1058 update_edge_key (heap
, edge
);
1062 /* Recompute HEAP nodes for each uninlined call in NODE.
1063 This is used when we know that edge badnesses are going only to increase
1064 (we introduced new call site) and thus all we need is to insert newly
1065 created edges into heap. */
1068 update_callee_keys (fibheap_t heap
, struct cgraph_node
*node
,
1069 bitmap updated_nodes
)
1071 struct cgraph_edge
*e
= node
->callees
;
1076 if (!e
->inline_failed
&& e
->callee
->callees
)
1077 e
= e
->callee
->callees
;
1080 enum availability avail
;
1081 struct cgraph_node
*callee
;
1082 /* We do not reset callee growth cache here. Since we added a new call,
1083 growth chould have just increased and consequentely badness metric
1084 don't need updating. */
1085 if (e
->inline_failed
1086 && (callee
= cgraph_function_or_thunk_node (e
->callee
, &avail
))
1087 && inline_summary (callee
)->inlinable
1088 && cgraph_function_body_availability (callee
) >= AVAIL_AVAILABLE
1089 && !bitmap_bit_p (updated_nodes
, callee
->uid
))
1091 if (can_inline_edge_p (e
, false)
1092 && want_inline_small_function_p (e
, false))
1093 update_edge_key (heap
, e
);
1096 report_inline_failed_reason (e
);
1097 fibheap_delete_node (heap
, (fibnode_t
) e
->aux
);
1107 if (e
->caller
== node
)
1109 e
= e
->caller
->callers
;
1111 while (!e
->next_callee
);
1117 /* Enqueue all recursive calls from NODE into priority queue depending on
1118 how likely we want to recursively inline the call. */
1121 lookup_recursive_calls (struct cgraph_node
*node
, struct cgraph_node
*where
,
1124 struct cgraph_edge
*e
;
1125 enum availability avail
;
1127 for (e
= where
->callees
; e
; e
= e
->next_callee
)
1128 if (e
->callee
== node
1129 || (cgraph_function_or_thunk_node (e
->callee
, &avail
) == node
1130 && avail
> AVAIL_OVERWRITABLE
))
1132 /* When profile feedback is available, prioritize by expected number
1134 fibheap_insert (heap
,
1135 !max_count
? -e
->frequency
1136 : -(e
->count
/ ((max_count
+ (1<<24) - 1) / (1<<24))),
1139 for (e
= where
->callees
; e
; e
= e
->next_callee
)
1140 if (!e
->inline_failed
)
1141 lookup_recursive_calls (node
, e
->callee
, heap
);
1144 /* Decide on recursive inlining: in the case function has recursive calls,
1145 inline until body size reaches given argument. If any new indirect edges
1146 are discovered in the process, add them to *NEW_EDGES, unless NEW_EDGES
1150 recursive_inlining (struct cgraph_edge
*edge
,
1151 VEC (cgraph_edge_p
, heap
) **new_edges
)
1153 int limit
= PARAM_VALUE (PARAM_MAX_INLINE_INSNS_RECURSIVE_AUTO
);
1155 struct cgraph_node
*node
;
1156 struct cgraph_edge
*e
;
1157 struct cgraph_node
*master_clone
= NULL
, *next
;
1161 node
= edge
->caller
;
1162 if (node
->global
.inlined_to
)
1163 node
= node
->global
.inlined_to
;
1165 if (DECL_DECLARED_INLINE_P (node
->symbol
.decl
))
1166 limit
= PARAM_VALUE (PARAM_MAX_INLINE_INSNS_RECURSIVE
);
1168 /* Make sure that function is small enough to be considered for inlining. */
1169 if (estimate_size_after_inlining (node
, edge
) >= limit
)
1171 heap
= fibheap_new ();
1172 lookup_recursive_calls (node
, node
, heap
);
1173 if (fibheap_empty (heap
))
1175 fibheap_delete (heap
);
1181 " Performing recursive inlining on %s\n",
1182 cgraph_node_name (node
));
1184 /* Do the inlining and update list of recursive call during process. */
1185 while (!fibheap_empty (heap
))
1187 struct cgraph_edge
*curr
1188 = (struct cgraph_edge
*) fibheap_extract_min (heap
);
1189 struct cgraph_node
*cnode
;
1191 if (estimate_size_after_inlining (node
, curr
) > limit
)
1194 if (!can_inline_edge_p (curr
, true))
1198 for (cnode
= curr
->caller
;
1199 cnode
->global
.inlined_to
; cnode
= cnode
->callers
->caller
)
1200 if (node
->symbol
.decl
1201 == cgraph_function_or_thunk_node (curr
->callee
, NULL
)->symbol
.decl
)
1204 if (!want_inline_self_recursive_call_p (curr
, node
, false, depth
))
1210 " Inlining call of depth %i", depth
);
1213 fprintf (dump_file
, " called approx. %.2f times per call",
1214 (double)curr
->count
/ node
->count
);
1216 fprintf (dump_file
, "\n");
1220 /* We need original clone to copy around. */
1221 master_clone
= cgraph_clone_node (node
, node
->symbol
.decl
,
1222 node
->count
, CGRAPH_FREQ_BASE
,
1224 for (e
= master_clone
->callees
; e
; e
= e
->next_callee
)
1225 if (!e
->inline_failed
)
1226 clone_inlined_nodes (e
, true, false, NULL
);
1229 cgraph_redirect_edge_callee (curr
, master_clone
);
1230 inline_call (curr
, false, new_edges
, &overall_size
, true);
1231 lookup_recursive_calls (node
, curr
->callee
, heap
);
1235 if (!fibheap_empty (heap
) && dump_file
)
1236 fprintf (dump_file
, " Recursive inlining growth limit met.\n");
1237 fibheap_delete (heap
);
1244 "\n Inlined %i times, "
1245 "body grown from size %i to %i, time %i to %i\n", n
,
1246 inline_summary (master_clone
)->size
, inline_summary (node
)->size
,
1247 inline_summary (master_clone
)->time
, inline_summary (node
)->time
);
1249 /* Remove master clone we used for inlining. We rely that clones inlined
1250 into master clone gets queued just before master clone so we don't
1252 for (node
= cgraph_first_function (); node
!= master_clone
;
1255 next
= cgraph_next_function (node
);
1256 if (node
->global
.inlined_to
== master_clone
)
1257 cgraph_remove_node (node
);
1259 cgraph_remove_node (master_clone
);
1264 /* Given whole compilation unit estimate of INSNS, compute how large we can
1265 allow the unit to grow. */
1268 compute_max_insns (int insns
)
1270 int max_insns
= insns
;
1271 if (max_insns
< PARAM_VALUE (PARAM_LARGE_UNIT_INSNS
))
1272 max_insns
= PARAM_VALUE (PARAM_LARGE_UNIT_INSNS
);
1274 return ((HOST_WIDEST_INT
) max_insns
1275 * (100 + PARAM_VALUE (PARAM_INLINE_UNIT_GROWTH
)) / 100);
1279 /* Compute badness of all edges in NEW_EDGES and add them to the HEAP. */
1282 add_new_edges_to_heap (fibheap_t heap
, VEC (cgraph_edge_p
, heap
) *new_edges
)
1284 while (VEC_length (cgraph_edge_p
, new_edges
) > 0)
1286 struct cgraph_edge
*edge
= VEC_pop (cgraph_edge_p
, new_edges
);
1288 gcc_assert (!edge
->aux
);
1289 if (edge
->inline_failed
1290 && can_inline_edge_p (edge
, true)
1291 && want_inline_small_function_p (edge
, true))
1292 edge
->aux
= fibheap_insert (heap
, edge_badness (edge
, false), edge
);
1297 /* We use greedy algorithm for inlining of small functions:
1298 All inline candidates are put into prioritized heap ordered in
1301 The inlining of small functions is bounded by unit growth parameters. */
1304 inline_small_functions (void)
1306 struct cgraph_node
*node
;
1307 struct cgraph_edge
*edge
;
1308 fibheap_t edge_heap
= fibheap_new ();
1309 bitmap updated_nodes
= BITMAP_ALLOC (NULL
);
1310 int min_size
, max_size
;
1311 VEC (cgraph_edge_p
, heap
) *new_indirect_edges
= NULL
;
1312 int initial_size
= 0;
1314 if (flag_indirect_inlining
)
1315 new_indirect_edges
= VEC_alloc (cgraph_edge_p
, heap
, 8);
1319 "\nDeciding on inlining of small functions. Starting with size %i.\n",
1322 /* Compute overall unit size and other global parameters used by badness
1326 initialize_growth_caches ();
1328 FOR_EACH_DEFINED_FUNCTION (node
)
1329 if (!node
->global
.inlined_to
)
1331 if (cgraph_function_with_gimple_body_p (node
)
1332 || node
->thunk
.thunk_p
)
1334 struct inline_summary
*info
= inline_summary (node
);
1336 if (!DECL_EXTERNAL (node
->symbol
.decl
))
1337 initial_size
+= info
->size
;
1340 for (edge
= node
->callers
; edge
; edge
= edge
->next_caller
)
1341 if (max_count
< edge
->count
)
1342 max_count
= edge
->count
;
1345 overall_size
= initial_size
;
1346 max_size
= compute_max_insns (overall_size
);
1347 min_size
= overall_size
;
1349 /* Populate the heeap with all edges we might inline. */
1351 FOR_EACH_DEFINED_FUNCTION (node
)
1352 if (!node
->global
.inlined_to
)
1355 fprintf (dump_file
, "Enqueueing calls of %s/%i.\n",
1356 cgraph_node_name (node
), node
->uid
);
1358 for (edge
= node
->callers
; edge
; edge
= edge
->next_caller
)
1359 if (edge
->inline_failed
1360 && can_inline_edge_p (edge
, true)
1361 && want_inline_small_function_p (edge
, true)
1362 && edge
->inline_failed
)
1364 gcc_assert (!edge
->aux
);
1365 update_edge_key (edge_heap
, edge
);
1369 gcc_assert (in_lto_p
1371 || (profile_info
&& flag_branch_probabilities
));
1373 while (!fibheap_empty (edge_heap
))
1375 int old_size
= overall_size
;
1376 struct cgraph_node
*where
, *callee
;
1377 int badness
= fibheap_min_key (edge_heap
);
1378 int current_badness
;
1382 edge
= (struct cgraph_edge
*) fibheap_extract_min (edge_heap
);
1383 gcc_assert (edge
->aux
);
1385 if (!edge
->inline_failed
)
1388 /* Be sure that caches are maintained consistent.
1389 We can not make this ENABLE_CHECKING only because it cause different
1390 updates of the fibheap queue. */
1391 cached_badness
= edge_badness (edge
, false);
1392 reset_edge_growth_cache (edge
);
1393 reset_node_growth_cache (edge
->callee
);
1395 /* When updating the edge costs, we only decrease badness in the keys.
1396 Increases of badness are handled lazilly; when we see key with out
1397 of date value on it, we re-insert it now. */
1398 current_badness
= edge_badness (edge
, false);
1399 gcc_assert (cached_badness
== current_badness
);
1400 gcc_assert (current_badness
>= badness
);
1401 if (current_badness
!= badness
)
1403 edge
->aux
= fibheap_insert (edge_heap
, current_badness
, edge
);
1407 if (!can_inline_edge_p (edge
, true))
1410 callee
= cgraph_function_or_thunk_node (edge
->callee
, NULL
);
1411 growth
= estimate_edge_growth (edge
);
1415 "\nConsidering %s with %i size\n",
1416 cgraph_node_name (callee
),
1417 inline_summary (callee
)->size
);
1419 " to be inlined into %s in %s:%i\n"
1420 " Estimated growth after inlined into all is %+i insns.\n"
1421 " Estimated badness is %i, frequency %.2f.\n",
1422 cgraph_node_name (edge
->caller
),
1423 flag_wpa
? "unknown"
1424 : gimple_filename ((const_gimple
) edge
->call_stmt
),
1426 : gimple_lineno ((const_gimple
) edge
->call_stmt
),
1427 estimate_growth (callee
),
1429 edge
->frequency
/ (double)CGRAPH_FREQ_BASE
);
1431 fprintf (dump_file
," Called "HOST_WIDEST_INT_PRINT_DEC
"x\n",
1433 if (dump_flags
& TDF_DETAILS
)
1434 edge_badness (edge
, true);
1437 if (overall_size
+ growth
> max_size
1438 && !DECL_DISREGARD_INLINE_LIMITS (callee
->symbol
.decl
))
1440 edge
->inline_failed
= CIF_INLINE_UNIT_GROWTH_LIMIT
;
1441 report_inline_failed_reason (edge
);
1445 if (!want_inline_small_function_p (edge
, true))
1448 /* Heuristics for inlining small functions works poorly for
1449 recursive calls where we do efect similar to loop unrolling.
1450 When inliing such edge seems profitable, leave decision on
1451 specific inliner. */
1452 if (cgraph_edge_recursive_p (edge
))
1454 where
= edge
->caller
;
1455 if (where
->global
.inlined_to
)
1456 where
= where
->global
.inlined_to
;
1457 if (!recursive_inlining (edge
,
1458 flag_indirect_inlining
1459 ? &new_indirect_edges
: NULL
))
1461 edge
->inline_failed
= CIF_RECURSIVE_INLINING
;
1464 reset_edge_caches (where
);
1465 /* Recursive inliner inlines all recursive calls of the function
1466 at once. Consequently we need to update all callee keys. */
1467 if (flag_indirect_inlining
)
1468 add_new_edges_to_heap (edge_heap
, new_indirect_edges
);
1469 update_callee_keys (edge_heap
, where
, updated_nodes
);
1473 struct cgraph_node
*outer_node
= NULL
;
1476 /* Consider the case where self recursive function A is inlined into B.
1477 This is desired optimization in some cases, since it leads to effect
1478 similar of loop peeling and we might completely optimize out the
1479 recursive call. However we must be extra selective. */
1481 where
= edge
->caller
;
1482 while (where
->global
.inlined_to
)
1484 if (where
->symbol
.decl
== callee
->symbol
.decl
)
1485 outer_node
= where
, depth
++;
1486 where
= where
->callers
->caller
;
1489 && !want_inline_self_recursive_call_p (edge
, outer_node
,
1493 = (DECL_DISREGARD_INLINE_LIMITS (edge
->callee
->symbol
.decl
)
1494 ? CIF_RECURSIVE_INLINING
: CIF_UNSPECIFIED
);
1497 else if (depth
&& dump_file
)
1498 fprintf (dump_file
, " Peeling recursion with depth %i\n", depth
);
1500 gcc_checking_assert (!callee
->global
.inlined_to
);
1501 inline_call (edge
, true, &new_indirect_edges
, &overall_size
, true);
1502 if (flag_indirect_inlining
)
1503 add_new_edges_to_heap (edge_heap
, new_indirect_edges
);
1505 reset_edge_caches (edge
->callee
);
1506 reset_node_growth_cache (callee
);
1508 update_callee_keys (edge_heap
, edge
->callee
, updated_nodes
);
1510 where
= edge
->caller
;
1511 if (where
->global
.inlined_to
)
1512 where
= where
->global
.inlined_to
;
1514 /* Our profitability metric can depend on local properties
1515 such as number of inlinable calls and size of the function body.
1516 After inlining these properties might change for the function we
1517 inlined into (since it's body size changed) and for the functions
1518 called by function we inlined (since number of it inlinable callers
1520 update_caller_keys (edge_heap
, where
, updated_nodes
, NULL
);
1521 bitmap_clear (updated_nodes
);
1526 " Inlined into %s which now has time %i and size %i,"
1527 "net change of %+i.\n",
1528 cgraph_node_name (edge
->caller
),
1529 inline_summary (edge
->caller
)->time
,
1530 inline_summary (edge
->caller
)->size
,
1531 overall_size
- old_size
);
1533 if (min_size
> overall_size
)
1535 min_size
= overall_size
;
1536 max_size
= compute_max_insns (min_size
);
1539 fprintf (dump_file
, "New minimal size reached: %i\n", min_size
);
1543 free_growth_caches ();
1544 if (new_indirect_edges
)
1545 VEC_free (cgraph_edge_p
, heap
, new_indirect_edges
);
1546 fibheap_delete (edge_heap
);
1549 "Unit growth for small function inlining: %i->%i (%i%%)\n",
1550 initial_size
, overall_size
,
1551 initial_size
? overall_size
* 100 / (initial_size
) - 100: 0);
1552 BITMAP_FREE (updated_nodes
);
1555 /* Flatten NODE. Performed both during early inlining and
1556 at IPA inlining time. */
1559 flatten_function (struct cgraph_node
*node
, bool early
)
1561 struct cgraph_edge
*e
;
1563 /* We shouldn't be called recursively when we are being processed. */
1564 gcc_assert (node
->symbol
.aux
== NULL
);
1566 node
->symbol
.aux
= (void *) node
;
1568 for (e
= node
->callees
; e
; e
= e
->next_callee
)
1570 struct cgraph_node
*orig_callee
;
1571 struct cgraph_node
*callee
= cgraph_function_or_thunk_node (e
->callee
, NULL
);
1573 /* We've hit cycle? It is time to give up. */
1574 if (callee
->symbol
.aux
)
1578 "Not inlining %s into %s to avoid cycle.\n",
1579 xstrdup (cgraph_node_name (callee
)),
1580 xstrdup (cgraph_node_name (e
->caller
)));
1581 e
->inline_failed
= CIF_RECURSIVE_INLINING
;
1585 /* When the edge is already inlined, we just need to recurse into
1586 it in order to fully flatten the leaves. */
1587 if (!e
->inline_failed
)
1589 flatten_function (callee
, early
);
1593 /* Flatten attribute needs to be processed during late inlining. For
1594 extra code quality we however do flattening during early optimization,
1597 ? !can_inline_edge_p (e
, true)
1598 : !can_early_inline_edge_p (e
))
1601 if (cgraph_edge_recursive_p (e
))
1604 fprintf (dump_file
, "Not inlining: recursive call.\n");
1608 if (gimple_in_ssa_p (DECL_STRUCT_FUNCTION (node
->symbol
.decl
))
1609 != gimple_in_ssa_p (DECL_STRUCT_FUNCTION (callee
->symbol
.decl
)))
1612 fprintf (dump_file
, "Not inlining: SSA form does not match.\n");
1616 /* Inline the edge and flatten the inline clone. Avoid
1617 recursing through the original node if the node was cloned. */
1619 fprintf (dump_file
, " Inlining %s into %s.\n",
1620 xstrdup (cgraph_node_name (callee
)),
1621 xstrdup (cgraph_node_name (e
->caller
)));
1622 orig_callee
= callee
;
1623 inline_call (e
, true, NULL
, NULL
, false);
1624 if (e
->callee
!= orig_callee
)
1625 orig_callee
->symbol
.aux
= (void *) node
;
1626 flatten_function (e
->callee
, early
);
1627 if (e
->callee
!= orig_callee
)
1628 orig_callee
->symbol
.aux
= NULL
;
1631 node
->symbol
.aux
= NULL
;
1632 if (!node
->global
.inlined_to
)
1633 inline_update_overall_summary (node
);
1636 /* Decide on the inlining. We do so in the topological order to avoid
1637 expenses on updating data structures. */
1642 struct cgraph_node
*node
;
1644 struct cgraph_node
**order
=
1645 XCNEWVEC (struct cgraph_node
*, cgraph_n_nodes
);
1648 if (in_lto_p
&& optimize
)
1649 ipa_update_after_lto_read ();
1652 dump_inline_summaries (dump_file
);
1654 nnodes
= ipa_reverse_postorder (order
);
1656 FOR_EACH_FUNCTION (node
)
1657 node
->symbol
.aux
= 0;
1660 fprintf (dump_file
, "\nFlattening functions:\n");
1662 /* In the first pass handle functions to be flattened. Do this with
1663 a priority so none of our later choices will make this impossible. */
1664 for (i
= nnodes
- 1; i
>= 0; i
--)
1668 /* Handle nodes to be flattened.
1669 Ideally when processing callees we stop inlining at the
1670 entry of cycles, possibly cloning that entry point and
1671 try to flatten itself turning it into a self-recursive
1673 if (lookup_attribute ("flatten",
1674 DECL_ATTRIBUTES (node
->symbol
.decl
)) != NULL
)
1678 "Flattening %s\n", cgraph_node_name (node
));
1679 flatten_function (node
, false);
1683 inline_small_functions ();
1684 symtab_remove_unreachable_nodes (true, dump_file
);
1687 /* We already perform some inlining of functions called once during
1688 inlining small functions above. After unreachable nodes are removed,
1689 we still might do a quick check that nothing new is found. */
1690 if (flag_inline_functions_called_once
)
1694 fprintf (dump_file
, "\nDeciding on functions called once:\n");
1696 /* Inlining one function called once has good chance of preventing
1697 inlining other function into the same callee. Ideally we should
1698 work in priority order, but probably inlining hot functions first
1699 is good cut without the extra pain of maintaining the queue.
1701 ??? this is not really fitting the bill perfectly: inlining function
1702 into callee often leads to better optimization of callee due to
1703 increased context for optimization.
1704 For example if main() function calls a function that outputs help
1705 and then function that does the main optmization, we should inline
1706 the second with priority even if both calls are cold by themselves.
1708 We probably want to implement new predicate replacing our use of
1709 maybe_hot_edge interpreted as maybe_hot_edge || callee is known
1711 for (cold
= 0; cold
<= 1; cold
++)
1713 FOR_EACH_DEFINED_FUNCTION (node
)
1715 if (want_inline_function_called_once_p (node
)
1717 || cgraph_maybe_hot_edge_p (node
->callers
)))
1719 struct cgraph_node
*caller
= node
->callers
->caller
;
1724 "\nInlining %s size %i.\n",
1725 cgraph_node_name (node
),
1726 inline_summary (node
)->size
);
1728 " Called once from %s %i insns.\n",
1729 cgraph_node_name (node
->callers
->caller
),
1730 inline_summary (node
->callers
->caller
)->size
);
1733 inline_call (node
->callers
, true, NULL
, NULL
, true);
1736 " Inlined into %s which now has %i size\n",
1737 cgraph_node_name (caller
),
1738 inline_summary (caller
)->size
);
1744 /* Free ipa-prop structures if they are no longer needed. */
1746 ipa_free_all_structures_after_iinln ();
1750 "\nInlined %i calls, eliminated %i functions\n\n",
1751 ncalls_inlined
, nfunctions_inlined
);
1754 dump_inline_summaries (dump_file
);
1755 /* In WPA we use inline summaries for partitioning process. */
1757 inline_free_summary ();
1761 /* Inline always-inline function calls in NODE. */
1764 inline_always_inline_functions (struct cgraph_node
*node
)
1766 struct cgraph_edge
*e
;
1767 bool inlined
= false;
1769 for (e
= node
->callees
; e
; e
= e
->next_callee
)
1771 struct cgraph_node
*callee
= cgraph_function_or_thunk_node (e
->callee
, NULL
);
1772 if (!DECL_DISREGARD_INLINE_LIMITS (callee
->symbol
.decl
))
1775 if (cgraph_edge_recursive_p (e
))
1778 fprintf (dump_file
, " Not inlining recursive call to %s.\n",
1779 cgraph_node_name (e
->callee
));
1780 e
->inline_failed
= CIF_RECURSIVE_INLINING
;
1784 if (!can_early_inline_edge_p (e
))
1788 fprintf (dump_file
, " Inlining %s into %s (always_inline).\n",
1789 xstrdup (cgraph_node_name (e
->callee
)),
1790 xstrdup (cgraph_node_name (e
->caller
)));
1791 inline_call (e
, true, NULL
, NULL
, false);
1795 inline_update_overall_summary (node
);
1800 /* Decide on the inlining. We do so in the topological order to avoid
1801 expenses on updating data structures. */
1804 early_inline_small_functions (struct cgraph_node
*node
)
1806 struct cgraph_edge
*e
;
1807 bool inlined
= false;
1809 for (e
= node
->callees
; e
; e
= e
->next_callee
)
1811 struct cgraph_node
*callee
= cgraph_function_or_thunk_node (e
->callee
, NULL
);
1812 if (!inline_summary (callee
)->inlinable
1813 || !e
->inline_failed
)
1816 /* Do not consider functions not declared inline. */
1817 if (!DECL_DECLARED_INLINE_P (callee
->symbol
.decl
)
1818 && !flag_inline_small_functions
1819 && !flag_inline_functions
)
1823 fprintf (dump_file
, "Considering inline candidate %s.\n",
1824 cgraph_node_name (callee
));
1826 if (!can_early_inline_edge_p (e
))
1829 if (cgraph_edge_recursive_p (e
))
1832 fprintf (dump_file
, " Not inlining: recursive call.\n");
1836 if (!want_early_inline_function_p (e
))
1840 fprintf (dump_file
, " Inlining %s into %s.\n",
1841 xstrdup (cgraph_node_name (callee
)),
1842 xstrdup (cgraph_node_name (e
->caller
)));
1843 inline_call (e
, true, NULL
, NULL
, true);
1850 /* Do inlining of small functions. Doing so early helps profiling and other
1851 passes to be somewhat more effective and avoids some code duplication in
1852 later real inlining pass for testcases with very many function calls. */
1854 early_inliner (void)
1856 struct cgraph_node
*node
= cgraph_get_node (current_function_decl
);
1857 struct cgraph_edge
*edge
;
1858 unsigned int todo
= 0;
1860 bool inlined
= false;
1865 /* Do nothing if datastructures for ipa-inliner are already computed. This
1866 happens when some pass decides to construct new function and
1867 cgraph_add_new_function calls lowering passes and early optimization on
1868 it. This may confuse ourself when early inliner decide to inline call to
1869 function clone, because function clones don't have parameter list in
1870 ipa-prop matching their signature. */
1871 if (ipa_node_params_vector
)
1874 #ifdef ENABLE_CHECKING
1875 verify_cgraph_node (node
);
1878 /* Even when not optimizing or not inlining inline always-inline
1880 inlined
= inline_always_inline_functions (node
);
1884 || !flag_early_inlining
1885 /* Never inline regular functions into always-inline functions
1886 during incremental inlining. This sucks as functions calling
1887 always inline functions will get less optimized, but at the
1888 same time inlining of functions calling always inline
1889 function into an always inline function might introduce
1890 cycles of edges to be always inlined in the callgraph.
1892 We might want to be smarter and just avoid this type of inlining. */
1893 || DECL_DISREGARD_INLINE_LIMITS (node
->symbol
.decl
))
1895 else if (lookup_attribute ("flatten",
1896 DECL_ATTRIBUTES (node
->symbol
.decl
)) != NULL
)
1898 /* When the function is marked to be flattened, recursively inline
1902 "Flattening %s\n", cgraph_node_name (node
));
1903 flatten_function (node
, true);
1908 /* We iterate incremental inlining to get trivial cases of indirect
1910 while (iterations
< PARAM_VALUE (PARAM_EARLY_INLINER_MAX_ITERATIONS
)
1911 && early_inline_small_functions (node
))
1913 timevar_push (TV_INTEGRATION
);
1914 todo
|= optimize_inline_calls (current_function_decl
);
1916 /* Technically we ought to recompute inline parameters so the new
1917 iteration of early inliner works as expected. We however have
1918 values approximately right and thus we only need to update edge
1919 info that might be cleared out for newly discovered edges. */
1920 for (edge
= node
->callees
; edge
; edge
= edge
->next_callee
)
1922 struct inline_edge_summary
*es
= inline_edge_summary (edge
);
1924 = estimate_num_insns (edge
->call_stmt
, &eni_size_weights
);
1926 = estimate_num_insns (edge
->call_stmt
, &eni_time_weights
);
1927 if (edge
->callee
->symbol
.decl
1928 && !gimple_check_call_matching_types (edge
->call_stmt
,
1929 edge
->callee
->symbol
.decl
))
1930 edge
->call_stmt_cannot_inline_p
= true;
1932 timevar_pop (TV_INTEGRATION
);
1937 fprintf (dump_file
, "Iterations: %i\n", iterations
);
1942 timevar_push (TV_INTEGRATION
);
1943 todo
|= optimize_inline_calls (current_function_decl
);
1944 timevar_pop (TV_INTEGRATION
);
1947 cfun
->always_inline_functions_inlined
= true;
1952 struct gimple_opt_pass pass_early_inline
=
1956 "einline", /* name */
1958 early_inliner
, /* execute */
1961 0, /* static_pass_number */
1962 TV_EARLY_INLINING
, /* tv_id */
1963 PROP_ssa
, /* properties_required */
1964 0, /* properties_provided */
1965 0, /* properties_destroyed */
1966 0, /* todo_flags_start */
1967 0 /* todo_flags_finish */
1972 /* When to run IPA inlining. Inlining of always-inline functions
1973 happens during early inlining.
1975 Enable inlining unconditoinally at -flto. We need size estimates to
1976 drive partitioning. */
1979 gate_ipa_inline (void)
1981 return optimize
|| flag_lto
|| flag_wpa
;
1984 struct ipa_opt_pass_d pass_ipa_inline
=
1988 "inline", /* name */
1989 gate_ipa_inline
, /* gate */
1990 ipa_inline
, /* execute */
1993 0, /* static_pass_number */
1994 TV_IPA_INLINING
, /* tv_id */
1995 0, /* properties_required */
1996 0, /* properties_provided */
1997 0, /* properties_destroyed */
1998 TODO_remove_functions
, /* todo_flags_finish */
2000 | TODO_remove_functions
| TODO_ggc_collect
/* todo_flags_finish */
2002 inline_generate_summary
, /* generate_summary */
2003 inline_write_summary
, /* write_summary */
2004 inline_read_summary
, /* read_summary */
2005 NULL
, /* write_optimization_summary */
2006 NULL
, /* read_optimization_summary */
2007 NULL
, /* stmt_fixup */
2009 inline_transform
, /* function_transform */
2010 NULL
, /* variable_transform */