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"
108 #include "tree-pass.h"
109 #include "coverage.h"
112 #include "tree-flow.h"
113 #include "ipa-prop.h"
116 #include "ipa-inline.h"
117 #include "ipa-utils.h"
119 /* Statistics we collect about inlining algorithm. */
120 static int overall_size;
121 static gcov_type max_count;
123 /* Return false when inlining edge E would lead to violating
124 limits on function unit growth or stack usage growth.
126 The relative function body growth limit is present generally
127 to avoid problems with non-linear behavior of the compiler.
128 To allow inlining huge functions into tiny wrapper, the limit
129 is always based on the bigger of the two functions considered.
131 For stack growth limits we always base the growth in stack usage
132 of the callers. We want to prevent applications from segfaulting
133 on stack overflow when functions with huge stack frames gets
137 caller_growth_limits (struct cgraph_edge *e)
139 struct cgraph_node *to = e->caller;
140 struct cgraph_node *what = cgraph_function_or_thunk_node (e->callee, NULL);
143 HOST_WIDE_INT stack_size_limit = 0, inlined_stack;
144 struct inline_summary *info, *what_info, *outer_info = inline_summary (to);
146 /* Look for function e->caller is inlined to. While doing
147 so work out the largest function body on the way. As
148 described above, we want to base our function growth
149 limits based on that. Not on the self size of the
150 outer function, not on the self size of inline code
151 we immediately inline to. This is the most relaxed
152 interpretation of the rule "do not grow large functions
153 too much in order to prevent compiler from exploding". */
156 info = inline_summary (to);
157 if (limit < info->self_size)
158 limit = info->self_size;
159 if (stack_size_limit < info->estimated_self_stack_size)
160 stack_size_limit = info->estimated_self_stack_size;
161 if (to->global.inlined_to)
162 to = to->callers->caller;
167 what_info = inline_summary (what);
169 if (limit < what_info->self_size)
170 limit = what_info->self_size;
172 limit += limit * PARAM_VALUE (PARAM_LARGE_FUNCTION_GROWTH) / 100;
174 /* Check the size after inlining against the function limits. But allow
175 the function to shrink if it went over the limits by forced inlining. */
176 newsize = estimate_size_after_inlining (to, e);
177 if (newsize >= info->size
178 && newsize > PARAM_VALUE (PARAM_LARGE_FUNCTION_INSNS)
181 e->inline_failed = CIF_LARGE_FUNCTION_GROWTH_LIMIT;
185 if (!what_info->estimated_stack_size)
188 /* FIXME: Stack size limit often prevents inlining in Fortran programs
189 due to large i/o datastructures used by the Fortran front-end.
190 We ought to ignore this limit when we know that the edge is executed
191 on every invocation of the caller (i.e. its call statement dominates
192 exit block). We do not track this information, yet. */
193 stack_size_limit += ((gcov_type)stack_size_limit
194 * PARAM_VALUE (PARAM_STACK_FRAME_GROWTH) / 100);
196 inlined_stack = (outer_info->stack_frame_offset
197 + outer_info->estimated_self_stack_size
198 + what_info->estimated_stack_size);
199 /* Check new stack consumption with stack consumption at the place
201 if (inlined_stack > stack_size_limit
202 /* If function already has large stack usage from sibling
203 inline call, we can inline, too.
204 This bit overoptimistically assume that we are good at stack
206 && inlined_stack > info->estimated_stack_size
207 && inlined_stack > PARAM_VALUE (PARAM_LARGE_STACK_FRAME))
209 e->inline_failed = CIF_LARGE_STACK_FRAME_GROWTH_LIMIT;
215 /* Dump info about why inlining has failed. */
218 report_inline_failed_reason (struct cgraph_edge *e)
222 fprintf (dump_file, " not inlinable: %s/%i -> %s/%i, %s\n",
223 cgraph_node_name (e->caller), e->caller->uid,
224 cgraph_node_name (e->callee), e->callee->uid,
225 cgraph_inline_failed_string (e->inline_failed));
229 /* Decide if we can inline the edge and possibly update
230 inline_failed reason.
231 We check whether inlining is possible at all and whether
232 caller growth limits allow doing so.
234 if REPORT is true, output reason to the dump file. */
237 can_inline_edge_p (struct cgraph_edge *e, bool report)
239 bool inlinable = true;
240 enum availability avail;
241 struct cgraph_node *callee
242 = cgraph_function_or_thunk_node (e->callee, &avail);
243 tree caller_tree = DECL_FUNCTION_SPECIFIC_OPTIMIZATION (e->caller->decl);
245 = callee ? DECL_FUNCTION_SPECIFIC_OPTIMIZATION (callee->decl) : NULL;
246 struct function *caller_cfun = DECL_STRUCT_FUNCTION (e->caller->decl);
247 struct function *callee_cfun
248 = callee ? DECL_STRUCT_FUNCTION (callee->decl) : NULL;
250 if (!caller_cfun && e->caller->clone_of)
251 caller_cfun = DECL_STRUCT_FUNCTION (e->caller->clone_of->decl);
253 if (!callee_cfun && callee && callee->clone_of)
254 callee_cfun = DECL_STRUCT_FUNCTION (callee->clone_of->decl);
256 gcc_assert (e->inline_failed);
258 if (!callee || !callee->analyzed)
260 e->inline_failed = CIF_BODY_NOT_AVAILABLE;
263 else if (!inline_summary (callee)->inlinable)
265 e->inline_failed = CIF_FUNCTION_NOT_INLINABLE;
268 else if (avail <= AVAIL_OVERWRITABLE)
270 e->inline_failed = CIF_OVERWRITABLE;
273 else if (e->call_stmt_cannot_inline_p)
275 e->inline_failed = CIF_MISMATCHED_ARGUMENTS;
278 /* Don't inline if the functions have different EH personalities. */
279 else if (DECL_FUNCTION_PERSONALITY (e->caller->decl)
280 && DECL_FUNCTION_PERSONALITY (callee->decl)
281 && (DECL_FUNCTION_PERSONALITY (e->caller->decl)
282 != DECL_FUNCTION_PERSONALITY (callee->decl)))
284 e->inline_failed = CIF_EH_PERSONALITY;
287 /* Don't inline if the callee can throw non-call exceptions but the
289 FIXME: this is obviously wrong for LTO where STRUCT_FUNCTION is missing.
290 Move the flag into cgraph node or mirror it in the inline summary. */
291 else if (callee_cfun && callee_cfun->can_throw_non_call_exceptions
292 && !(caller_cfun && caller_cfun->can_throw_non_call_exceptions))
294 e->inline_failed = CIF_NON_CALL_EXCEPTIONS;
297 /* Check compatibility of target optimization options. */
298 else if (!targetm.target_option.can_inline_p (e->caller->decl,
301 e->inline_failed = CIF_TARGET_OPTION_MISMATCH;
304 /* Check if caller growth allows the inlining. */
305 else if (!DECL_DISREGARD_INLINE_LIMITS (callee->decl)
306 && !lookup_attribute ("flatten",
308 (e->caller->global.inlined_to
309 ? e->caller->global.inlined_to->decl
311 && !caller_growth_limits (e))
313 /* Don't inline a function with a higher optimization level than the
314 caller. FIXME: this is really just tip of iceberg of handling
315 optimization attribute. */
316 else if (caller_tree != callee_tree)
318 struct cl_optimization *caller_opt
319 = TREE_OPTIMIZATION ((caller_tree)
321 : optimization_default_node);
323 struct cl_optimization *callee_opt
324 = TREE_OPTIMIZATION ((callee_tree)
326 : optimization_default_node);
328 if (((caller_opt->x_optimize > callee_opt->x_optimize)
329 || (caller_opt->x_optimize_size != callee_opt->x_optimize_size))
330 /* gcc.dg/pr43564.c. Look at forced inline even in -O0. */
331 && !DECL_DISREGARD_INLINE_LIMITS (e->callee->decl))
333 e->inline_failed = CIF_OPTIMIZATION_MISMATCH;
338 /* Be sure that the cannot_inline_p flag is up to date. */
339 gcc_checking_assert (!e->call_stmt
340 || (gimple_call_cannot_inline_p (e->call_stmt)
341 == e->call_stmt_cannot_inline_p)
342 /* In -flto-partition=none mode we really keep things out of
343 sync because call_stmt_cannot_inline_p is set at cgraph
344 merging when function bodies are not there yet. */
345 || (in_lto_p && !gimple_call_cannot_inline_p (e->call_stmt)));
346 if (!inlinable && report)
347 report_inline_failed_reason (e);
352 /* Return true if the edge E is inlinable during early inlining. */
355 can_early_inline_edge_p (struct cgraph_edge *e)
357 struct cgraph_node *callee = cgraph_function_or_thunk_node (e->callee,
359 /* Early inliner might get called at WPA stage when IPA pass adds new
360 function. In this case we can not really do any of early inlining
361 because function bodies are missing. */
362 if (!gimple_has_body_p (callee->decl))
364 e->inline_failed = CIF_BODY_NOT_AVAILABLE;
367 /* In early inliner some of callees may not be in SSA form yet
368 (i.e. the callgraph is cyclic and we did not process
369 the callee by early inliner, yet). We don't have CIF code for this
370 case; later we will re-do the decision in the real inliner. */
371 if (!gimple_in_ssa_p (DECL_STRUCT_FUNCTION (e->caller->decl))
372 || !gimple_in_ssa_p (DECL_STRUCT_FUNCTION (callee->decl)))
375 fprintf (dump_file, " edge not inlinable: not in SSA form\n");
378 if (!can_inline_edge_p (e, true))
384 /* Return true when N is leaf function. Accept cheap builtins
385 in leaf functions. */
388 leaf_node_p (struct cgraph_node *n)
390 struct cgraph_edge *e;
391 for (e = n->callees; e; e = e->next_callee)
392 if (!is_inexpensive_builtin (e->callee->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->decl))
408 else if (!DECL_DECLARED_INLINE_P (callee->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);
420 else if (!cgraph_maybe_hot_edge_p (e)
424 fprintf (dump_file, " will not early inline: %s/%i->%s/%i, "
425 "call is cold and code would grow by %i\n",
426 cgraph_node_name (e->caller), e->caller->uid,
427 cgraph_node_name (callee), callee->uid,
431 else if (!leaf_node_p (callee)
435 fprintf (dump_file, " will not early inline: %s/%i->%s/%i, "
436 "callee is not leaf and code would grow by %i\n",
437 cgraph_node_name (e->caller), e->caller->uid,
438 cgraph_node_name (callee), callee->uid,
442 else if (growth > PARAM_VALUE (PARAM_EARLY_INLINING_INSNS))
445 fprintf (dump_file, " will not early inline: %s/%i->%s/%i, "
446 "growth %i exceeds --param early-inlining-insns\n",
447 cgraph_node_name (e->caller), e->caller->uid,
448 cgraph_node_name (callee), callee->uid,
456 /* Return true if we are interested in inlining small function.
457 When REPORT is true, report reason to dump file. */
460 want_inline_small_function_p (struct cgraph_edge *e, bool report)
462 bool want_inline = true;
463 struct cgraph_node *callee = cgraph_function_or_thunk_node (e->callee, NULL);
465 if (DECL_DISREGARD_INLINE_LIMITS (callee->decl))
467 else if (!DECL_DECLARED_INLINE_P (callee->decl)
468 && !flag_inline_small_functions)
470 e->inline_failed = CIF_FUNCTION_NOT_INLINE_CANDIDATE;
475 int growth = estimate_edge_growth (e);
479 else if (DECL_DECLARED_INLINE_P (callee->decl)
480 && growth >= MAX_INLINE_INSNS_SINGLE)
482 e->inline_failed = CIF_MAX_INLINE_INSNS_SINGLE_LIMIT;
485 else if (!DECL_DECLARED_INLINE_P (callee->decl)
486 && !flag_inline_functions)
488 e->inline_failed = CIF_NOT_DECLARED_INLINED;
491 else if (!DECL_DECLARED_INLINE_P (callee->decl)
492 && growth >= MAX_INLINE_INSNS_AUTO)
494 e->inline_failed = CIF_MAX_INLINE_INSNS_AUTO_LIMIT;
497 /* If call is cold, do not inline when function body would grow.
498 Still inline when the overall unit size will shrink because the offline
499 copy of function being eliminated.
501 This is slightly wrong on aggressive side: it is entirely possible
502 that function is called many times with a context where inlining
503 reduces code size and few times with a context where inlining increase
504 code size. Resoluting growth estimate will be negative even if it
505 would make more sense to keep offline copy and do not inline into the
506 call sites that makes the code size grow.
508 When badness orders the calls in a way that code reducing calls come
509 first, this situation is not a problem at all: after inlining all
510 "good" calls, we will realize that keeping the function around is
512 else if (!cgraph_maybe_hot_edge_p (e)
513 && (DECL_EXTERNAL (callee->decl)
515 /* Unlike for functions called once, we play unsafe with
516 COMDATs. We can allow that since we know functions
517 in consideration are small (and thus risk is small) and
518 moreover grow estimates already accounts that COMDAT
519 functions may or may not disappear when eliminated from
520 current unit. With good probability making aggressive
521 choice in all units is going to make overall program
524 Consequently we ask cgraph_can_remove_if_no_direct_calls_p
526 cgraph_will_be_removed_from_program_if_no_direct_calls */
528 || !cgraph_can_remove_if_no_direct_calls_p (callee)
529 || estimate_growth (callee) > 0))
531 e->inline_failed = CIF_UNLIKELY_CALL;
535 if (!want_inline && report)
536 report_inline_failed_reason (e);
540 /* EDGE is self recursive edge.
541 We hand two cases - when function A is inlining into itself
542 or when function A is being inlined into another inliner copy of function
545 In first case OUTER_NODE points to the toplevel copy of A, while
546 in the second case OUTER_NODE points to the outermost copy of A in B.
548 In both cases we want to be extra selective since
549 inlining the call will just introduce new recursive calls to appear. */
552 want_inline_self_recursive_call_p (struct cgraph_edge *edge,
553 struct cgraph_node *outer_node,
557 char const *reason = NULL;
558 bool want_inline = true;
559 int caller_freq = CGRAPH_FREQ_BASE;
560 int max_depth = PARAM_VALUE (PARAM_MAX_INLINE_RECURSIVE_DEPTH_AUTO);
562 if (DECL_DECLARED_INLINE_P (edge->caller->decl))
563 max_depth = PARAM_VALUE (PARAM_MAX_INLINE_RECURSIVE_DEPTH);
565 if (!cgraph_maybe_hot_edge_p (edge))
567 reason = "recursive call is cold";
570 else if (max_count && !outer_node->count)
572 reason = "not executed in profile";
575 else if (depth > max_depth)
577 reason = "--param max-inline-recursive-depth exceeded.";
581 if (outer_node->global.inlined_to)
582 caller_freq = outer_node->callers->frequency;
586 /* Inlining of self recursive function into copy of itself within other function
587 is transformation similar to loop peeling.
589 Peeling is profitable if we can inline enough copies to make probability
590 of actual call to the self recursive function very small. Be sure that
591 the probability of recursion is small.
593 We ensure that the frequency of recursing is at most 1 - (1/max_depth).
594 This way the expected number of recision is at most max_depth. */
597 int max_prob = CGRAPH_FREQ_BASE - ((CGRAPH_FREQ_BASE + max_depth - 1)
600 for (i = 1; i < depth; i++)
601 max_prob = max_prob * max_prob / CGRAPH_FREQ_BASE;
603 && (edge->count * CGRAPH_FREQ_BASE / outer_node->count
606 reason = "profile of recursive call is too large";
610 && (edge->frequency * CGRAPH_FREQ_BASE / caller_freq
613 reason = "frequency of recursive call is too large";
617 /* Recursive inlining, i.e. equivalent of unrolling, is profitable if recursion
618 depth is large. We reduce function call overhead and increase chances that
619 things fit in hardware return predictor.
621 Recursive inlining might however increase cost of stack frame setup
622 actually slowing down functions whose recursion tree is wide rather than
625 Deciding reliably on when to do recursive inlining without profile feedback
626 is tricky. For now we disable recursive inlining when probability of self
629 Recursive inlining of self recursive call within loop also results in large loop
630 depths that generally optimize badly. We may want to throttle down inlining
631 in those cases. In particular this seems to happen in one of libstdc++ rb tree
636 && (edge->count * 100 / outer_node->count
637 <= PARAM_VALUE (PARAM_MIN_INLINE_RECURSIVE_PROBABILITY)))
639 reason = "profile of recursive call is too small";
643 && (edge->frequency * 100 / caller_freq
644 <= PARAM_VALUE (PARAM_MIN_INLINE_RECURSIVE_PROBABILITY)))
646 reason = "frequency of recursive call is too small";
650 if (!want_inline && dump_file)
651 fprintf (dump_file, " not inlining recursively: %s\n", reason);
655 /* Return true when NODE has caller other than EDGE.
656 Worker for cgraph_for_node_and_aliases. */
659 check_caller_edge (struct cgraph_node *node, void *edge)
661 return (node->callers
662 && node->callers != edge);
666 /* Decide if NODE is called once inlining it would eliminate need
667 for the offline copy of function. */
670 want_inline_function_called_once_p (struct cgraph_node *node)
672 struct cgraph_node *function = cgraph_function_or_thunk_node (node, NULL);
673 /* Already inlined? */
674 if (function->global.inlined_to)
676 /* Zero or more then one callers? */
678 || node->callers->next_caller)
680 /* Maybe other aliases has more direct calls. */
681 if (cgraph_for_node_and_aliases (node, check_caller_edge, node->callers, true))
683 /* Recursive call makes no sense to inline. */
684 if (cgraph_edge_recursive_p (node->callers))
686 /* External functions are not really in the unit, so inlining
687 them when called once would just increase the program size. */
688 if (DECL_EXTERNAL (function->decl))
690 /* Offline body must be optimized out. */
691 if (!cgraph_will_be_removed_from_program_if_no_direct_calls (function))
693 if (!can_inline_edge_p (node->callers, true))
699 /* Return relative time improvement for inlining EDGE in range
703 relative_time_benefit (struct inline_summary *callee_info,
704 struct cgraph_edge *edge,
708 gcov_type uninlined_call_time;
710 uninlined_call_time =
713 + inline_edge_summary (edge)->call_stmt_time
714 + CGRAPH_FREQ_BASE / 2) * edge->frequency
716 /* Compute relative time benefit, i.e. how much the call becomes faster.
717 ??? perhaps computing how much the caller+calle together become faster
718 would lead to more realistic results. */
719 if (!uninlined_call_time)
720 uninlined_call_time = 1;
722 (uninlined_call_time - time_growth) * 256 / (uninlined_call_time);
723 relbenefit = MIN (relbenefit, 512);
724 relbenefit = MAX (relbenefit, 1);
729 /* A cost model driving the inlining heuristics in a way so the edges with
730 smallest badness are inlined first. After each inlining is performed
731 the costs of all caller edges of nodes affected are recomputed so the
732 metrics may accurately depend on values such as number of inlinable callers
733 of the function or function body size. */
736 edge_badness (struct cgraph_edge *edge, bool dump)
739 int growth, time_growth;
740 struct cgraph_node *callee = cgraph_function_or_thunk_node (edge->callee,
742 struct inline_summary *callee_info = inline_summary (callee);
744 if (DECL_DISREGARD_INLINE_LIMITS (callee->decl))
747 growth = estimate_edge_growth (edge);
748 time_growth = estimate_edge_time (edge);
752 fprintf (dump_file, " Badness calculation for %s -> %s\n",
753 cgraph_node_name (edge->caller),
754 cgraph_node_name (callee));
755 fprintf (dump_file, " size growth %i, time growth %i\n",
760 /* Always prefer inlining saving code size. */
763 badness = INT_MIN / 2 + growth;
765 fprintf (dump_file, " %i: Growth %i <= 0\n", (int) badness,
769 /* When profiling is available, compute badness as:
771 relative_edge_count * relative_time_benefit
772 goodness = -------------------------------------------
776 The fraction is upside down, becuase on edge counts and time beneits
777 the bounds are known. Edge growth is essentially unlimited. */
781 int relbenefit = relative_time_benefit (callee_info, edge, time_growth);
784 ((double) edge->count * INT_MIN / 2 / max_count / 512) *
785 relative_time_benefit (callee_info, edge, time_growth)) / growth;
787 /* Be sure that insanity of the profile won't lead to increasing counts
788 in the scalling and thus to overflow in the computation above. */
789 gcc_assert (max_count >= edge->count);
793 " %i (relative %f): profile info. Relative count %f"
794 " * Relative benefit %f\n",
795 (int) badness, (double) badness / INT_MIN,
796 (double) edge->count / max_count,
797 relbenefit * 100 / 256.0);
801 /* When function local profile is available. Compute badness as:
805 badness = -------------------------------------- + growth_for-all
806 relative_time_benefit * edge_frequency
809 else if (flag_guess_branch_prob)
811 int div = edge->frequency * (1<<10) / CGRAPH_FREQ_MAX;
815 gcc_checking_assert (edge->frequency <= CGRAPH_FREQ_MAX);
816 div *= relative_time_benefit (callee_info, edge, time_growth);
818 /* frequency is normalized in range 1...2^10.
819 relbenefit in range 1...2^9
820 DIV should be in range 1....2^19. */
821 gcc_checking_assert (div >= 1 && div <= (1<<19));
823 /* Result must be integer in range 0...INT_MAX.
824 Set the base of fixed point calculation so we don't lose much of
825 precision for small bandesses (those are interesting) yet we don't
826 overflow for growths that are still in interesting range. */
827 badness = ((gcov_type)growth) * (1<<18);
828 badness = (badness + div / 2) / div;
830 /* Overall growth of inlining all calls of function matters: we want to
831 inline so offline copy of function is no longer needed.
833 Additionally functions that can be fully inlined without much of
834 effort are better inline candidates than functions that can be fully
835 inlined only after noticeable overall unit growths. The latter
836 are better in a sense compressing of code size by factoring out common
837 code into separate function shared by multiple code paths.
839 We might mix the valud into the fraction by taking into account
840 relative growth of the unit, but for now just add the number
841 into resulting fraction. */
842 growth_for_all = estimate_growth (callee);
843 badness += growth_for_all;
844 if (badness > INT_MAX - 1)
845 badness = INT_MAX - 1;
849 " %i: guessed profile. frequency %f, overall growth %i,"
850 " benefit %f%%, divisor %i\n",
851 (int) badness, (double)edge->frequency / CGRAPH_FREQ_BASE, growth_for_all,
852 relative_time_benefit (callee_info, edge, time_growth) * 100 / 256.0, div);
855 /* When function local profile is not available or it does not give
856 useful information (ie frequency is zero), base the cost on
857 loop nest and overall size growth, so we optimize for overall number
858 of functions fully inlined in program. */
861 int nest = MIN (inline_edge_summary (edge)->loop_depth, 8);
862 badness = estimate_growth (callee) * 256;
864 /* Decrease badness if call is nested. */
872 fprintf (dump_file, " %i: no profile. nest %i\n", (int) badness,
876 /* Ensure that we did not overflow in all the fixed point math above. */
877 gcc_assert (badness >= INT_MIN);
878 gcc_assert (badness <= INT_MAX - 1);
879 /* Make recursive inlining happen always after other inlining is done. */
880 if (cgraph_edge_recursive_p (edge))
886 /* Recompute badness of EDGE and update its key in HEAP if needed. */
888 update_edge_key (fibheap_t heap, struct cgraph_edge *edge)
890 int badness = edge_badness (edge, false);
893 fibnode_t n = (fibnode_t) edge->aux;
894 gcc_checking_assert (n->data == edge);
896 /* fibheap_replace_key only decrease the keys.
897 When we increase the key we do not update heap
898 and instead re-insert the element once it becomes
899 a minimum of heap. */
900 if (badness < n->key)
902 if (dump_file && (dump_flags & TDF_DETAILS))
905 " decreasing badness %s/%i -> %s/%i, %i to %i\n",
906 cgraph_node_name (edge->caller), edge->caller->uid,
907 cgraph_node_name (edge->callee), edge->callee->uid,
911 fibheap_replace_key (heap, n, badness);
912 gcc_checking_assert (n->key == badness);
917 if (dump_file && (dump_flags & TDF_DETAILS))
920 " enqueuing call %s/%i -> %s/%i, badness %i\n",
921 cgraph_node_name (edge->caller), edge->caller->uid,
922 cgraph_node_name (edge->callee), edge->callee->uid,
925 edge->aux = fibheap_insert (heap, badness, edge);
931 All caller edges needs to be resetted because
932 size estimates change. Similarly callees needs reset
933 because better context may be known. */
936 reset_edge_caches (struct cgraph_node *node)
938 struct cgraph_edge *edge;
939 struct cgraph_edge *e = node->callees;
940 struct cgraph_node *where = node;
944 if (where->global.inlined_to)
945 where = where->global.inlined_to;
947 /* WHERE body size has changed, the cached growth is invalid. */
948 reset_node_growth_cache (where);
950 for (edge = where->callers; edge; edge = edge->next_caller)
951 if (edge->inline_failed)
952 reset_edge_growth_cache (edge);
953 for (i = 0; ipa_ref_list_refering_iterate (&where->ref_list, i, ref); i++)
954 if (ref->use == IPA_REF_ALIAS)
955 reset_edge_caches (ipa_ref_refering_node (ref));
961 if (!e->inline_failed && e->callee->callees)
962 e = e->callee->callees;
965 if (e->inline_failed)
966 reset_edge_growth_cache (e);
973 if (e->caller == node)
975 e = e->caller->callers;
977 while (!e->next_callee);
983 /* Recompute HEAP nodes for each of caller of NODE.
984 UPDATED_NODES track nodes we already visited, to avoid redundant work.
985 When CHECK_INLINABLITY_FOR is set, re-check for specified edge that
986 it is inlinable. Otherwise check all edges. */
989 update_caller_keys (fibheap_t heap, struct cgraph_node *node,
990 bitmap updated_nodes,
991 struct cgraph_edge *check_inlinablity_for)
993 struct cgraph_edge *edge;
997 if ((!node->alias && !inline_summary (node)->inlinable)
998 || cgraph_function_body_availability (node) <= AVAIL_OVERWRITABLE
999 || node->global.inlined_to)
1001 if (!bitmap_set_bit (updated_nodes, node->uid))
1004 for (i = 0; ipa_ref_list_refering_iterate (&node->ref_list, i, ref); i++)
1005 if (ref->use == IPA_REF_ALIAS)
1007 struct cgraph_node *alias = ipa_ref_refering_node (ref);
1008 update_caller_keys (heap, alias, updated_nodes, check_inlinablity_for);
1011 for (edge = node->callers; edge; edge = edge->next_caller)
1012 if (edge->inline_failed)
1014 if (!check_inlinablity_for
1015 || check_inlinablity_for == edge)
1017 if (can_inline_edge_p (edge, false)
1018 && want_inline_small_function_p (edge, false))
1019 update_edge_key (heap, edge);
1022 report_inline_failed_reason (edge);
1023 fibheap_delete_node (heap, (fibnode_t) edge->aux);
1028 update_edge_key (heap, edge);
1032 /* Recompute HEAP nodes for each uninlined call in NODE.
1033 This is used when we know that edge badnesses are going only to increase
1034 (we introduced new call site) and thus all we need is to insert newly
1035 created edges into heap. */
1038 update_callee_keys (fibheap_t heap, struct cgraph_node *node,
1039 bitmap updated_nodes)
1041 struct cgraph_edge *e = node->callees;
1046 if (!e->inline_failed && e->callee->callees)
1047 e = e->callee->callees;
1050 enum availability avail;
1051 struct cgraph_node *callee;
1052 /* We do not reset callee growth cache here. Since we added a new call,
1053 growth chould have just increased and consequentely badness metric
1054 don't need updating. */
1055 if (e->inline_failed
1056 && (callee = cgraph_function_or_thunk_node (e->callee, &avail))
1057 && inline_summary (callee)->inlinable
1058 && cgraph_function_body_availability (callee) >= AVAIL_AVAILABLE
1059 && !bitmap_bit_p (updated_nodes, callee->uid))
1061 if (can_inline_edge_p (e, false)
1062 && want_inline_small_function_p (e, false))
1063 update_edge_key (heap, e);
1066 report_inline_failed_reason (e);
1067 fibheap_delete_node (heap, (fibnode_t) e->aux);
1077 if (e->caller == node)
1079 e = e->caller->callers;
1081 while (!e->next_callee);
1087 /* Recompute heap nodes for each of caller edges of each of callees.
1088 Walk recursively into all inline clones. */
1091 update_all_callee_keys (fibheap_t heap, struct cgraph_node *node,
1092 bitmap updated_nodes)
1094 struct cgraph_edge *e = node->callees;
1098 if (!e->inline_failed && e->callee->callees)
1099 e = e->callee->callees;
1102 struct cgraph_node *callee = cgraph_function_or_thunk_node (e->callee,
1105 /* We inlined and thus callees might have different number of calls.
1106 Reset their caches */
1107 reset_node_growth_cache (callee);
1108 if (e->inline_failed)
1109 update_caller_keys (heap, callee, updated_nodes, e);
1116 if (e->caller == node)
1118 e = e->caller->callers;
1120 while (!e->next_callee);
1126 /* Enqueue all recursive calls from NODE into priority queue depending on
1127 how likely we want to recursively inline the call. */
1130 lookup_recursive_calls (struct cgraph_node *node, struct cgraph_node *where,
1133 struct cgraph_edge *e;
1134 enum availability avail;
1136 for (e = where->callees; e; e = e->next_callee)
1137 if (e->callee == node
1138 || (cgraph_function_or_thunk_node (e->callee, &avail) == node
1139 && avail > AVAIL_OVERWRITABLE))
1141 /* When profile feedback is available, prioritize by expected number
1143 fibheap_insert (heap,
1144 !max_count ? -e->frequency
1145 : -(e->count / ((max_count + (1<<24) - 1) / (1<<24))),
1148 for (e = where->callees; e; e = e->next_callee)
1149 if (!e->inline_failed)
1150 lookup_recursive_calls (node, e->callee, heap);
1153 /* Decide on recursive inlining: in the case function has recursive calls,
1154 inline until body size reaches given argument. If any new indirect edges
1155 are discovered in the process, add them to *NEW_EDGES, unless NEW_EDGES
1159 recursive_inlining (struct cgraph_edge *edge,
1160 VEC (cgraph_edge_p, heap) **new_edges)
1162 int limit = PARAM_VALUE (PARAM_MAX_INLINE_INSNS_RECURSIVE_AUTO);
1164 struct cgraph_node *node;
1165 struct cgraph_edge *e;
1166 struct cgraph_node *master_clone = NULL, *next;
1170 node = edge->caller;
1171 if (node->global.inlined_to)
1172 node = node->global.inlined_to;
1174 if (DECL_DECLARED_INLINE_P (node->decl))
1175 limit = PARAM_VALUE (PARAM_MAX_INLINE_INSNS_RECURSIVE);
1177 /* Make sure that function is small enough to be considered for inlining. */
1178 if (estimate_size_after_inlining (node, edge) >= limit)
1180 heap = fibheap_new ();
1181 lookup_recursive_calls (node, node, heap);
1182 if (fibheap_empty (heap))
1184 fibheap_delete (heap);
1190 " Performing recursive inlining on %s\n",
1191 cgraph_node_name (node));
1193 /* Do the inlining and update list of recursive call during process. */
1194 while (!fibheap_empty (heap))
1196 struct cgraph_edge *curr
1197 = (struct cgraph_edge *) fibheap_extract_min (heap);
1198 struct cgraph_node *cnode;
1200 if (estimate_size_after_inlining (node, curr) > limit)
1203 if (!can_inline_edge_p (curr, true))
1207 for (cnode = curr->caller;
1208 cnode->global.inlined_to; cnode = cnode->callers->caller)
1209 if (node->decl == curr->callee->decl)
1212 if (!want_inline_self_recursive_call_p (curr, node, false, depth))
1218 " Inlining call of depth %i", depth);
1221 fprintf (dump_file, " called approx. %.2f times per call",
1222 (double)curr->count / node->count);
1224 fprintf (dump_file, "\n");
1228 /* We need original clone to copy around. */
1229 master_clone = cgraph_clone_node (node, node->decl,
1230 node->count, CGRAPH_FREQ_BASE,
1232 for (e = master_clone->callees; e; e = e->next_callee)
1233 if (!e->inline_failed)
1234 clone_inlined_nodes (e, true, false, NULL);
1237 cgraph_redirect_edge_callee (curr, master_clone);
1238 inline_call (curr, false, new_edges, &overall_size);
1239 lookup_recursive_calls (node, curr->callee, heap);
1243 if (!fibheap_empty (heap) && dump_file)
1244 fprintf (dump_file, " Recursive inlining growth limit met.\n");
1245 fibheap_delete (heap);
1252 "\n Inlined %i times, "
1253 "body grown from size %i to %i, time %i to %i\n", n,
1254 inline_summary (master_clone)->size, inline_summary (node)->size,
1255 inline_summary (master_clone)->time, inline_summary (node)->time);
1257 /* Remove master clone we used for inlining. We rely that clones inlined
1258 into master clone gets queued just before master clone so we don't
1260 for (node = cgraph_nodes; node != master_clone;
1264 if (node->global.inlined_to == master_clone)
1265 cgraph_remove_node (node);
1267 cgraph_remove_node (master_clone);
1272 /* Given whole compilation unit estimate of INSNS, compute how large we can
1273 allow the unit to grow. */
1276 compute_max_insns (int insns)
1278 int max_insns = insns;
1279 if (max_insns < PARAM_VALUE (PARAM_LARGE_UNIT_INSNS))
1280 max_insns = PARAM_VALUE (PARAM_LARGE_UNIT_INSNS);
1282 return ((HOST_WIDEST_INT) max_insns
1283 * (100 + PARAM_VALUE (PARAM_INLINE_UNIT_GROWTH)) / 100);
1287 /* Compute badness of all edges in NEW_EDGES and add them to the HEAP. */
1290 add_new_edges_to_heap (fibheap_t heap, VEC (cgraph_edge_p, heap) *new_edges)
1292 while (VEC_length (cgraph_edge_p, new_edges) > 0)
1294 struct cgraph_edge *edge = VEC_pop (cgraph_edge_p, new_edges);
1296 gcc_assert (!edge->aux);
1297 if (edge->inline_failed
1298 && can_inline_edge_p (edge, true)
1299 && want_inline_small_function_p (edge, true))
1300 edge->aux = fibheap_insert (heap, edge_badness (edge, false), edge);
1305 /* We use greedy algorithm for inlining of small functions:
1306 All inline candidates are put into prioritized heap ordered in
1309 The inlining of small functions is bounded by unit growth parameters. */
1312 inline_small_functions (void)
1314 struct cgraph_node *node;
1315 struct cgraph_edge *edge;
1316 fibheap_t heap = fibheap_new ();
1317 bitmap updated_nodes = BITMAP_ALLOC (NULL);
1318 int min_size, max_size;
1319 VEC (cgraph_edge_p, heap) *new_indirect_edges = NULL;
1320 int initial_size = 0;
1322 if (flag_indirect_inlining)
1323 new_indirect_edges = VEC_alloc (cgraph_edge_p, heap, 8);
1327 "\nDeciding on inlining of small functions. Starting with size %i.\n",
1330 /* Compute overall unit size and other global parameters used by badness
1334 initialize_growth_caches ();
1336 FOR_EACH_DEFINED_FUNCTION (node)
1337 if (!node->global.inlined_to)
1339 if (cgraph_function_with_gimple_body_p (node)
1340 || node->thunk.thunk_p)
1342 struct inline_summary *info = inline_summary (node);
1344 if (!DECL_EXTERNAL (node->decl))
1345 initial_size += info->size;
1348 for (edge = node->callers; edge; edge = edge->next_caller)
1349 if (max_count < edge->count)
1350 max_count = edge->count;
1353 overall_size = initial_size;
1354 max_size = compute_max_insns (overall_size);
1355 min_size = overall_size;
1357 /* Populate the heeap with all edges we might inline. */
1359 FOR_EACH_DEFINED_FUNCTION (node)
1360 if (!node->global.inlined_to)
1363 fprintf (dump_file, "Enqueueing calls of %s/%i.\n",
1364 cgraph_node_name (node), node->uid);
1366 for (edge = node->callers; edge; edge = edge->next_caller)
1367 if (edge->inline_failed
1368 && can_inline_edge_p (edge, true)
1369 && want_inline_small_function_p (edge, true)
1370 && edge->inline_failed)
1372 gcc_assert (!edge->aux);
1373 update_edge_key (heap, edge);
1377 gcc_assert (in_lto_p
1379 || (profile_info && flag_branch_probabilities));
1381 while (!fibheap_empty (heap))
1383 int old_size = overall_size;
1384 struct cgraph_node *where, *callee;
1385 int badness = fibheap_min_key (heap);
1386 int current_badness;
1389 edge = (struct cgraph_edge *) fibheap_extract_min (heap);
1390 gcc_assert (edge->aux);
1392 if (!edge->inline_failed)
1395 /* Be sure that caches are maintained consistent. */
1396 #ifdef ENABLE_CHECKING
1397 reset_edge_growth_cache (edge);
1398 reset_node_growth_cache (edge->callee);
1401 /* When updating the edge costs, we only decrease badness in the keys.
1402 Increases of badness are handled lazilly; when we see key with out
1403 of date value on it, we re-insert it now. */
1404 current_badness = edge_badness (edge, false);
1405 gcc_assert (current_badness >= badness);
1406 if (current_badness != badness)
1408 edge->aux = fibheap_insert (heap, current_badness, edge);
1412 if (!can_inline_edge_p (edge, true))
1415 callee = cgraph_function_or_thunk_node (edge->callee, NULL);
1416 growth = estimate_edge_growth (edge);
1420 "\nConsidering %s with %i size\n",
1421 cgraph_node_name (callee),
1422 inline_summary (callee)->size);
1424 " to be inlined into %s in %s:%i\n"
1425 " Estimated growth after inlined into all is %+i insns.\n"
1426 " Estimated badness is %i, frequency %.2f.\n",
1427 cgraph_node_name (edge->caller),
1428 flag_wpa ? "unknown"
1429 : gimple_filename ((const_gimple) edge->call_stmt),
1431 : gimple_lineno ((const_gimple) edge->call_stmt),
1432 estimate_growth (callee),
1434 edge->frequency / (double)CGRAPH_FREQ_BASE);
1436 fprintf (dump_file," Called "HOST_WIDEST_INT_PRINT_DEC"x\n",
1438 if (dump_flags & TDF_DETAILS)
1439 edge_badness (edge, true);
1442 if (overall_size + growth > max_size
1443 && !DECL_DISREGARD_INLINE_LIMITS (callee->decl))
1445 edge->inline_failed = CIF_INLINE_UNIT_GROWTH_LIMIT;
1446 report_inline_failed_reason (edge);
1450 if (!want_inline_small_function_p (edge, true))
1453 /* Heuristics for inlining small functions works poorly for
1454 recursive calls where we do efect similar to loop unrolling.
1455 When inliing such edge seems profitable, leave decision on
1456 specific inliner. */
1457 if (cgraph_edge_recursive_p (edge))
1459 where = edge->caller;
1460 if (where->global.inlined_to)
1461 where = where->global.inlined_to;
1462 if (!recursive_inlining (edge,
1463 flag_indirect_inlining
1464 ? &new_indirect_edges : NULL))
1466 edge->inline_failed = CIF_RECURSIVE_INLINING;
1469 reset_edge_caches (where);
1470 /* Recursive inliner inlines all recursive calls of the function
1471 at once. Consequently we need to update all callee keys. */
1472 if (flag_indirect_inlining)
1473 add_new_edges_to_heap (heap, new_indirect_edges);
1474 update_all_callee_keys (heap, where, updated_nodes);
1478 struct cgraph_node *outer_node = NULL;
1481 /* Consider the case where self recursive function A is inlined into B.
1482 This is desired optimization in some cases, since it leads to effect
1483 similar of loop peeling and we might completely optimize out the
1484 recursive call. However we must be extra selective. */
1486 where = edge->caller;
1487 while (where->global.inlined_to)
1489 if (where->decl == callee->decl)
1490 outer_node = where, depth++;
1491 where = where->callers->caller;
1494 && !want_inline_self_recursive_call_p (edge, outer_node,
1498 = (DECL_DISREGARD_INLINE_LIMITS (edge->callee->decl)
1499 ? CIF_RECURSIVE_INLINING : CIF_UNSPECIFIED);
1502 else if (depth && dump_file)
1503 fprintf (dump_file, " Peeling recursion with depth %i\n", depth);
1505 gcc_checking_assert (!callee->global.inlined_to);
1506 inline_call (edge, true, &new_indirect_edges, &overall_size);
1507 if (flag_indirect_inlining)
1508 add_new_edges_to_heap (heap, new_indirect_edges);
1510 reset_edge_caches (edge->callee);
1511 reset_node_growth_cache (callee);
1513 /* We inlined last offline copy to the body. This might lead
1514 to callees of function having fewer call sites and thus they
1515 may need updating. */
1516 if (callee->global.inlined_to)
1517 update_all_callee_keys (heap, callee, updated_nodes);
1519 update_callee_keys (heap, edge->callee, updated_nodes);
1521 where = edge->caller;
1522 if (where->global.inlined_to)
1523 where = where->global.inlined_to;
1525 /* Our profitability metric can depend on local properties
1526 such as number of inlinable calls and size of the function body.
1527 After inlining these properties might change for the function we
1528 inlined into (since it's body size changed) and for the functions
1529 called by function we inlined (since number of it inlinable callers
1531 update_caller_keys (heap, where, updated_nodes, NULL);
1533 /* We removed one call of the function we just inlined. If offline
1534 copy is still needed, be sure to update the keys. */
1535 if (callee != where && !callee->global.inlined_to)
1536 update_caller_keys (heap, callee, updated_nodes, NULL);
1537 bitmap_clear (updated_nodes);
1542 " Inlined into %s which now has time %i and size %i,"
1543 "net change of %+i.\n",
1544 cgraph_node_name (edge->caller),
1545 inline_summary (edge->caller)->time,
1546 inline_summary (edge->caller)->size,
1547 overall_size - old_size);
1549 if (min_size > overall_size)
1551 min_size = overall_size;
1552 max_size = compute_max_insns (min_size);
1555 fprintf (dump_file, "New minimal size reached: %i\n", min_size);
1559 free_growth_caches ();
1560 if (new_indirect_edges)
1561 VEC_free (cgraph_edge_p, heap, new_indirect_edges);
1562 fibheap_delete (heap);
1565 "Unit growth for small function inlining: %i->%i (%i%%)\n",
1566 initial_size, overall_size,
1567 initial_size ? overall_size * 100 / (initial_size) - 100: 0);
1568 BITMAP_FREE (updated_nodes);
1571 /* Flatten NODE. Performed both during early inlining and
1572 at IPA inlining time. */
1575 flatten_function (struct cgraph_node *node, bool early)
1577 struct cgraph_edge *e;
1579 /* We shouldn't be called recursively when we are being processed. */
1580 gcc_assert (node->aux == NULL);
1582 node->aux = (void *) node;
1584 for (e = node->callees; e; e = e->next_callee)
1586 struct cgraph_node *orig_callee;
1587 struct cgraph_node *callee = cgraph_function_or_thunk_node (e->callee, NULL);
1589 /* We've hit cycle? It is time to give up. */
1594 "Not inlining %s into %s to avoid cycle.\n",
1595 cgraph_node_name (callee),
1596 cgraph_node_name (e->caller));
1597 e->inline_failed = CIF_RECURSIVE_INLINING;
1601 /* When the edge is already inlined, we just need to recurse into
1602 it in order to fully flatten the leaves. */
1603 if (!e->inline_failed)
1605 flatten_function (callee, early);
1609 /* Flatten attribute needs to be processed during late inlining. For
1610 extra code quality we however do flattening during early optimization,
1613 ? !can_inline_edge_p (e, true)
1614 : !can_early_inline_edge_p (e))
1617 if (cgraph_edge_recursive_p (e))
1620 fprintf (dump_file, "Not inlining: recursive call.\n");
1624 if (gimple_in_ssa_p (DECL_STRUCT_FUNCTION (node->decl))
1625 != gimple_in_ssa_p (DECL_STRUCT_FUNCTION (callee->decl)))
1628 fprintf (dump_file, "Not inlining: SSA form does not match.\n");
1632 /* Inline the edge and flatten the inline clone. Avoid
1633 recursing through the original node if the node was cloned. */
1635 fprintf (dump_file, " Inlining %s into %s.\n",
1636 cgraph_node_name (callee),
1637 cgraph_node_name (e->caller));
1638 orig_callee = callee;
1639 inline_call (e, true, NULL, NULL);
1640 if (e->callee != orig_callee)
1641 orig_callee->aux = (void *) node;
1642 flatten_function (e->callee, early);
1643 if (e->callee != orig_callee)
1644 orig_callee->aux = NULL;
1650 /* Decide on the inlining. We do so in the topological order to avoid
1651 expenses on updating data structures. */
1656 struct cgraph_node *node;
1658 struct cgraph_node **order =
1659 XCNEWVEC (struct cgraph_node *, cgraph_n_nodes);
1662 if (in_lto_p && flag_indirect_inlining)
1663 ipa_update_after_lto_read ();
1664 if (flag_indirect_inlining)
1665 ipa_create_all_structures_for_iinln ();
1668 dump_inline_summaries (dump_file);
1670 nnodes = ipa_reverse_postorder (order);
1672 for (node = cgraph_nodes; node; node = node->next)
1676 fprintf (dump_file, "\nFlattening functions:\n");
1678 /* In the first pass handle functions to be flattened. Do this with
1679 a priority so none of our later choices will make this impossible. */
1680 for (i = nnodes - 1; i >= 0; i--)
1684 /* Handle nodes to be flattened.
1685 Ideally when processing callees we stop inlining at the
1686 entry of cycles, possibly cloning that entry point and
1687 try to flatten itself turning it into a self-recursive
1689 if (lookup_attribute ("flatten",
1690 DECL_ATTRIBUTES (node->decl)) != NULL)
1694 "Flattening %s\n", cgraph_node_name (node));
1695 flatten_function (node, false);
1699 inline_small_functions ();
1700 cgraph_remove_unreachable_nodes (true, dump_file);
1703 /* We already perform some inlining of functions called once during
1704 inlining small functions above. After unreachable nodes are removed,
1705 we still might do a quick check that nothing new is found. */
1706 if (flag_inline_functions_called_once)
1710 fprintf (dump_file, "\nDeciding on functions called once:\n");
1712 /* Inlining one function called once has good chance of preventing
1713 inlining other function into the same callee. Ideally we should
1714 work in priority order, but probably inlining hot functions first
1715 is good cut without the extra pain of maintaining the queue.
1717 ??? this is not really fitting the bill perfectly: inlining function
1718 into callee often leads to better optimization of callee due to
1719 increased context for optimization.
1720 For example if main() function calls a function that outputs help
1721 and then function that does the main optmization, we should inline
1722 the second with priority even if both calls are cold by themselves.
1724 We probably want to implement new predicate replacing our use of
1725 maybe_hot_edge interpreted as maybe_hot_edge || callee is known
1727 for (cold = 0; cold <= 1; cold ++)
1729 for (node = cgraph_nodes; node; node = node->next)
1731 if (want_inline_function_called_once_p (node)
1733 || cgraph_maybe_hot_edge_p (node->callers)))
1735 struct cgraph_node *caller = node->callers->caller;
1740 "\nInlining %s size %i.\n",
1741 cgraph_node_name (node), inline_summary (node)->size);
1743 " Called once from %s %i insns.\n",
1744 cgraph_node_name (node->callers->caller),
1745 inline_summary (node->callers->caller)->size);
1748 inline_call (node->callers, true, NULL, NULL);
1751 " Inlined into %s which now has %i size\n",
1752 cgraph_node_name (caller),
1753 inline_summary (caller)->size);
1759 /* Free ipa-prop structures if they are no longer needed. */
1760 if (flag_indirect_inlining)
1761 ipa_free_all_structures_after_iinln ();
1765 "\nInlined %i calls, eliminated %i functions\n\n",
1766 ncalls_inlined, nfunctions_inlined);
1769 dump_inline_summaries (dump_file);
1770 /* In WPA we use inline summaries for partitioning process. */
1772 inline_free_summary ();
1776 /* Inline always-inline function calls in NODE. */
1779 inline_always_inline_functions (struct cgraph_node *node)
1781 struct cgraph_edge *e;
1782 bool inlined = false;
1784 for (e = node->callees; e; e = e->next_callee)
1786 struct cgraph_node *callee = cgraph_function_or_thunk_node (e->callee, NULL);
1787 if (!DECL_DISREGARD_INLINE_LIMITS (callee->decl))
1790 if (cgraph_edge_recursive_p (e))
1793 fprintf (dump_file, " Not inlining recursive call to %s.\n",
1794 cgraph_node_name (e->callee));
1795 e->inline_failed = CIF_RECURSIVE_INLINING;
1799 if (!can_early_inline_edge_p (e))
1803 fprintf (dump_file, " Inlining %s into %s (always_inline).\n",
1804 cgraph_node_name (e->callee),
1805 cgraph_node_name (e->caller));
1806 inline_call (e, true, NULL, NULL);
1813 /* Decide on the inlining. We do so in the topological order to avoid
1814 expenses on updating data structures. */
1817 early_inline_small_functions (struct cgraph_node *node)
1819 struct cgraph_edge *e;
1820 bool inlined = false;
1822 for (e = node->callees; e; e = e->next_callee)
1824 struct cgraph_node *callee = cgraph_function_or_thunk_node (e->callee, NULL);
1825 if (!inline_summary (callee)->inlinable
1826 || !e->inline_failed)
1829 /* Do not consider functions not declared inline. */
1830 if (!DECL_DECLARED_INLINE_P (callee->decl)
1831 && !flag_inline_small_functions
1832 && !flag_inline_functions)
1836 fprintf (dump_file, "Considering inline candidate %s.\n",
1837 cgraph_node_name (callee));
1839 if (!can_early_inline_edge_p (e))
1842 if (cgraph_edge_recursive_p (e))
1845 fprintf (dump_file, " Not inlining: recursive call.\n");
1849 if (!want_early_inline_function_p (e))
1853 fprintf (dump_file, " Inlining %s into %s.\n",
1854 cgraph_node_name (callee),
1855 cgraph_node_name (e->caller));
1856 inline_call (e, true, NULL, NULL);
1863 /* Do inlining of small functions. Doing so early helps profiling and other
1864 passes to be somewhat more effective and avoids some code duplication in
1865 later real inlining pass for testcases with very many function calls. */
1867 early_inliner (void)
1869 struct cgraph_node *node = cgraph_get_node (current_function_decl);
1870 struct cgraph_edge *edge;
1871 unsigned int todo = 0;
1873 bool inlined = false;
1878 /* Do nothing if datastructures for ipa-inliner are already computed. This
1879 happens when some pass decides to construct new function and
1880 cgraph_add_new_function calls lowering passes and early optimization on
1881 it. This may confuse ourself when early inliner decide to inline call to
1882 function clone, because function clones don't have parameter list in
1883 ipa-prop matching their signature. */
1884 if (ipa_node_params_vector)
1887 #ifdef ENABLE_CHECKING
1888 verify_cgraph_node (node);
1891 /* Even when not optimizing or not inlining inline always-inline
1893 inlined = inline_always_inline_functions (node);
1897 || !flag_early_inlining
1898 /* Never inline regular functions into always-inline functions
1899 during incremental inlining. This sucks as functions calling
1900 always inline functions will get less optimized, but at the
1901 same time inlining of functions calling always inline
1902 function into an always inline function might introduce
1903 cycles of edges to be always inlined in the callgraph.
1905 We might want to be smarter and just avoid this type of inlining. */
1906 || DECL_DISREGARD_INLINE_LIMITS (node->decl))
1908 else if (lookup_attribute ("flatten",
1909 DECL_ATTRIBUTES (node->decl)) != NULL)
1911 /* When the function is marked to be flattened, recursively inline
1915 "Flattening %s\n", cgraph_node_name (node));
1916 flatten_function (node, true);
1921 /* We iterate incremental inlining to get trivial cases of indirect
1923 while (iterations < PARAM_VALUE (PARAM_EARLY_INLINER_MAX_ITERATIONS)
1924 && early_inline_small_functions (node))
1926 timevar_push (TV_INTEGRATION);
1927 todo |= optimize_inline_calls (current_function_decl);
1929 /* Technically we ought to recompute inline parameters so the new
1930 iteration of early inliner works as expected. We however have
1931 values approximately right and thus we only need to update edge
1932 info that might be cleared out for newly discovered edges. */
1933 for (edge = node->callees; edge; edge = edge->next_callee)
1935 struct inline_edge_summary *es = inline_edge_summary (edge);
1937 = estimate_num_insns (edge->call_stmt, &eni_size_weights);
1939 = estimate_num_insns (edge->call_stmt, &eni_time_weights);
1941 timevar_pop (TV_INTEGRATION);
1946 fprintf (dump_file, "Iterations: %i\n", iterations);
1951 timevar_push (TV_INTEGRATION);
1952 todo |= optimize_inline_calls (current_function_decl);
1953 timevar_pop (TV_INTEGRATION);
1956 cfun->always_inline_functions_inlined = true;
1961 struct gimple_opt_pass pass_early_inline =
1965 "einline", /* name */
1967 early_inliner, /* execute */
1970 0, /* static_pass_number */
1971 TV_INLINE_HEURISTICS, /* tv_id */
1972 PROP_ssa, /* properties_required */
1973 0, /* properties_provided */
1974 0, /* properties_destroyed */
1975 0, /* todo_flags_start */
1976 0 /* todo_flags_finish */
1981 /* When to run IPA inlining. Inlining of always-inline functions
1982 happens during early inlining.
1984 Enable inlining unconditoinally at -flto. We need size estimates to
1985 drive partitioning. */
1988 gate_ipa_inline (void)
1990 return optimize || flag_lto || flag_wpa;
1993 struct ipa_opt_pass_d pass_ipa_inline =
1997 "inline", /* name */
1998 gate_ipa_inline, /* gate */
1999 ipa_inline, /* execute */
2002 0, /* static_pass_number */
2003 TV_INLINE_HEURISTICS, /* tv_id */
2004 0, /* properties_required */
2005 0, /* properties_provided */
2006 0, /* properties_destroyed */
2007 TODO_remove_functions, /* todo_flags_finish */
2009 | TODO_remove_functions | TODO_ggc_collect /* todo_flags_finish */
2011 inline_generate_summary, /* generate_summary */
2012 inline_write_summary, /* write_summary */
2013 inline_read_summary, /* read_summary */
2014 NULL, /* write_optimization_summary */
2015 NULL, /* read_optimization_summary */
2016 NULL, /* stmt_fixup */
2018 inline_transform, /* function_transform */
2019 NULL, /* variable_transform */