2012-07-26 Kazu Hirata <kazu@codesourcery.com>
[official-gcc.git] / gcc / ipa-inline.c
blob1a4594d746f7f536146e957586315c2c1a27c363
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
11 version.
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
16 for more details.
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
30 on).
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
35 inlining.
37 inlining heuristics
39 The inliner itself is split into two passes:
41 pass_early_inlining
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
56 flattening.
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
61 optimizers.
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.
69 pass_ipa_inline
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. */
93 #include "config.h"
94 #include "system.h"
95 #include "coretypes.h"
96 #include "tm.h"
97 #include "tree.h"
98 #include "tree-inline.h"
99 #include "langhooks.h"
100 #include "flags.h"
101 #include "cgraph.h"
102 #include "diagnostic.h"
103 #include "gimple-pretty-print.h"
104 #include "params.h"
105 #include "fibheap.h"
106 #include "intl.h"
107 #include "tree-pass.h"
108 #include "coverage.h"
109 #include "ggc.h"
110 #include "rtl.h"
111 #include "tree-flow.h"
112 #include "ipa-prop.h"
113 #include "except.h"
114 #include "target.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
133 inlined. */
135 static bool
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);
140 int newsize;
141 int limit = 0;
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". */
153 while (true)
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;
162 else
163 break;
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)
178 && newsize > limit)
180 e->inline_failed = CIF_LARGE_FUNCTION_GROWTH_LIMIT;
181 return false;
184 if (!what_info->estimated_stack_size)
185 return true;
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
199 stack is used. */
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
204 packing. */
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;
209 return false;
211 return true;
214 /* Dump info about why inlining has failed. */
216 static void
217 report_inline_failed_reason (struct cgraph_edge *e)
219 if (dump_file)
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. */
235 static bool
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);
243 tree callee_tree
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;
260 inlinable = false;
262 else if (!inline_summary (callee)->inlinable)
264 e->inline_failed = CIF_FUNCTION_NOT_INLINABLE;
265 inlinable = false;
267 else if (avail <= AVAIL_OVERWRITABLE)
269 e->inline_failed = CIF_OVERWRITABLE;
270 return false;
272 else if (e->call_stmt_cannot_inline_p)
274 e->inline_failed = CIF_MISMATCHED_ARGUMENTS;
275 inlinable = false;
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;
284 inlinable = false;
286 /* TM pure functions should not be inlined into non-TM_pure
287 functions. */
288 else if (is_tm_pure (callee->symbol.decl)
289 && !is_tm_pure (e->caller->symbol.decl))
291 e->inline_failed = CIF_UNSPECIFIED;
292 inlinable = false;
294 /* Don't inline if the callee can throw non-call exceptions but the
295 caller cannot.
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;
302 inlinable = false;
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;
309 inlinable = false;
311 /* Check if caller growth allows the inlining. */
312 else if (!DECL_DISREGARD_INLINE_LIMITS (callee->symbol.decl)
313 && !lookup_attribute ("flatten",
314 DECL_ATTRIBUTES
315 (e->caller->global.inlined_to
316 ? e->caller->global.inlined_to->symbol.decl
317 : e->caller->symbol.decl))
318 && !caller_growth_limits (e))
319 inlinable = false;
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)
327 ? caller_tree
328 : optimization_default_node);
330 struct cl_optimization *callee_opt
331 = TREE_OPTIMIZATION ((callee_tree)
332 ? 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;
341 inlinable = false;
345 if (!inlinable && report)
346 report_inline_failed_reason (e);
347 return inlinable;
351 /* Return true if the edge E is inlinable during early inlining. */
353 static bool
354 can_early_inline_edge_p (struct cgraph_edge *e)
356 struct cgraph_node *callee = cgraph_function_or_thunk_node (e->callee,
357 NULL);
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;
364 return false;
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)))
373 if (dump_file)
374 fprintf (dump_file, " edge not inlinable: not in SSA form\n");
375 return false;
377 if (!can_inline_edge_p (e, true))
378 return false;
379 return true;
383 /* Return true when N is leaf function. Accept cheap builtins
384 in leaf functions. */
386 static bool
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))
392 return false;
393 return true;
397 /* Return true if we are interested in inlining small function. */
399 static bool
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);
412 want_inline = false;
414 else
416 int growth = estimate_edge_growth (e);
417 if (growth <= 0)
419 else if (!cgraph_maybe_hot_edge_p (e)
420 && growth > 0)
422 if (dump_file)
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,
427 growth);
428 want_inline = false;
430 else if (!leaf_node_p (callee)
431 && growth > 0)
433 if (dump_file)
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,
438 growth);
439 want_inline = false;
441 else if (growth > PARAM_VALUE (PARAM_EARLY_INLINING_INSNS))
443 if (dump_file)
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,
448 growth);
449 want_inline = false;
452 return want_inline;
455 /* Return true if we are interested in inlining small function.
456 When REPORT is true, report reason to dump file. */
458 static bool
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;
470 want_inline = false;
472 else
474 int growth = estimate_edge_growth (e);
476 if (growth <= 0)
478 else if (DECL_DECLARED_INLINE_P (callee->symbol.decl)
479 && growth >= MAX_INLINE_INSNS_SINGLE)
481 e->inline_failed = CIF_MAX_INLINE_INSNS_SINGLE_LIMIT;
482 want_inline = false;
484 /* Before giving up based on fact that caller size will grow, allow
485 functions that are called few times and eliminating the offline
486 copy will lead to overall code size reduction.
487 Not all of these will be handled by subsequent inlining of functions
488 called once: in particular weak functions are not handled or funcitons
489 that inline to multiple calls but a lot of bodies is optimized out.
490 Finally we want to inline earlier to allow inlining of callbacks.
492 This is slightly wrong on aggressive side: it is entirely possible
493 that function is called many times with a context where inlining
494 reduces code size and few times with a context where inlining increase
495 code size. Resoluting growth estimate will be negative even if it
496 would make more sense to keep offline copy and do not inline into the
497 call sites that makes the code size grow.
499 When badness orders the calls in a way that code reducing calls come
500 first, this situation is not a problem at all: after inlining all
501 "good" calls, we will realize that keeping the function around is
502 better. */
503 else if (growth <= MAX_INLINE_INSNS_SINGLE
504 /* Unlike for functions called once, we play unsafe with
505 COMDATs. We can allow that since we know functions
506 in consideration are small (and thus risk is small) and
507 moreover grow estimates already accounts that COMDAT
508 functions may or may not disappear when eliminated from
509 current unit. With good probability making aggressive
510 choice in all units is going to make overall program
511 smaller.
513 Consequently we ask cgraph_can_remove_if_no_direct_calls_p
514 instead of
515 cgraph_will_be_removed_from_program_if_no_direct_calls */
516 && !DECL_EXTERNAL (callee->symbol.decl)
517 && cgraph_can_remove_if_no_direct_calls_p (callee)
518 && estimate_growth (callee) <= 0)
520 else if (!DECL_DECLARED_INLINE_P (callee->symbol.decl)
521 && !flag_inline_functions)
523 e->inline_failed = CIF_NOT_DECLARED_INLINED;
524 want_inline = false;
526 else if (!DECL_DECLARED_INLINE_P (callee->symbol.decl)
527 && growth >= MAX_INLINE_INSNS_AUTO)
529 e->inline_failed = CIF_MAX_INLINE_INSNS_AUTO_LIMIT;
530 want_inline = false;
532 /* If call is cold, do not inline when function body would grow. */
533 else if (!cgraph_maybe_hot_edge_p (e))
535 e->inline_failed = CIF_UNLIKELY_CALL;
536 want_inline = false;
539 if (!want_inline && report)
540 report_inline_failed_reason (e);
541 return want_inline;
544 /* EDGE is self recursive edge.
545 We hand two cases - when function A is inlining into itself
546 or when function A is being inlined into another inliner copy of function
547 A within function B.
549 In first case OUTER_NODE points to the toplevel copy of A, while
550 in the second case OUTER_NODE points to the outermost copy of A in B.
552 In both cases we want to be extra selective since
553 inlining the call will just introduce new recursive calls to appear. */
555 static bool
556 want_inline_self_recursive_call_p (struct cgraph_edge *edge,
557 struct cgraph_node *outer_node,
558 bool peeling,
559 int depth)
561 char const *reason = NULL;
562 bool want_inline = true;
563 int caller_freq = CGRAPH_FREQ_BASE;
564 int max_depth = PARAM_VALUE (PARAM_MAX_INLINE_RECURSIVE_DEPTH_AUTO);
566 if (DECL_DECLARED_INLINE_P (edge->caller->symbol.decl))
567 max_depth = PARAM_VALUE (PARAM_MAX_INLINE_RECURSIVE_DEPTH);
569 if (!cgraph_maybe_hot_edge_p (edge))
571 reason = "recursive call is cold";
572 want_inline = false;
574 else if (max_count && !outer_node->count)
576 reason = "not executed in profile";
577 want_inline = false;
579 else if (depth > max_depth)
581 reason = "--param max-inline-recursive-depth exceeded.";
582 want_inline = false;
585 if (outer_node->global.inlined_to)
586 caller_freq = outer_node->callers->frequency;
588 if (!want_inline)
590 /* Inlining of self recursive function into copy of itself within other function
591 is transformation similar to loop peeling.
593 Peeling is profitable if we can inline enough copies to make probability
594 of actual call to the self recursive function very small. Be sure that
595 the probability of recursion is small.
597 We ensure that the frequency of recursing is at most 1 - (1/max_depth).
598 This way the expected number of recision is at most max_depth. */
599 else if (peeling)
601 int max_prob = CGRAPH_FREQ_BASE - ((CGRAPH_FREQ_BASE + max_depth - 1)
602 / max_depth);
603 int i;
604 for (i = 1; i < depth; i++)
605 max_prob = max_prob * max_prob / CGRAPH_FREQ_BASE;
606 if (max_count
607 && (edge->count * CGRAPH_FREQ_BASE / outer_node->count
608 >= max_prob))
610 reason = "profile of recursive call is too large";
611 want_inline = false;
613 if (!max_count
614 && (edge->frequency * CGRAPH_FREQ_BASE / caller_freq
615 >= max_prob))
617 reason = "frequency of recursive call is too large";
618 want_inline = false;
621 /* Recursive inlining, i.e. equivalent of unrolling, is profitable if recursion
622 depth is large. We reduce function call overhead and increase chances that
623 things fit in hardware return predictor.
625 Recursive inlining might however increase cost of stack frame setup
626 actually slowing down functions whose recursion tree is wide rather than
627 deep.
629 Deciding reliably on when to do recursive inlining without profile feedback
630 is tricky. For now we disable recursive inlining when probability of self
631 recursion is low.
633 Recursive inlining of self recursive call within loop also results in large loop
634 depths that generally optimize badly. We may want to throttle down inlining
635 in those cases. In particular this seems to happen in one of libstdc++ rb tree
636 methods. */
637 else
639 if (max_count
640 && (edge->count * 100 / outer_node->count
641 <= PARAM_VALUE (PARAM_MIN_INLINE_RECURSIVE_PROBABILITY)))
643 reason = "profile of recursive call is too small";
644 want_inline = false;
646 else if (!max_count
647 && (edge->frequency * 100 / caller_freq
648 <= PARAM_VALUE (PARAM_MIN_INLINE_RECURSIVE_PROBABILITY)))
650 reason = "frequency of recursive call is too small";
651 want_inline = false;
654 if (!want_inline && dump_file)
655 fprintf (dump_file, " not inlining recursively: %s\n", reason);
656 return want_inline;
659 /* Return true when NODE has caller other than EDGE.
660 Worker for cgraph_for_node_and_aliases. */
662 static bool
663 check_caller_edge (struct cgraph_node *node, void *edge)
665 return (node->callers
666 && node->callers != edge);
670 /* Decide if NODE is called once inlining it would eliminate need
671 for the offline copy of function. */
673 static bool
674 want_inline_function_called_once_p (struct cgraph_node *node)
676 struct cgraph_node *function = cgraph_function_or_thunk_node (node, NULL);
677 /* Already inlined? */
678 if (function->global.inlined_to)
679 return false;
680 /* Zero or more then one callers? */
681 if (!node->callers
682 || node->callers->next_caller)
683 return false;
684 /* Maybe other aliases has more direct calls. */
685 if (cgraph_for_node_and_aliases (node, check_caller_edge, node->callers, true))
686 return false;
687 /* Recursive call makes no sense to inline. */
688 if (cgraph_edge_recursive_p (node->callers))
689 return false;
690 /* External functions are not really in the unit, so inlining
691 them when called once would just increase the program size. */
692 if (DECL_EXTERNAL (function->symbol.decl))
693 return false;
694 /* Offline body must be optimized out. */
695 if (!cgraph_will_be_removed_from_program_if_no_direct_calls (function))
696 return false;
697 if (!can_inline_edge_p (node->callers, true))
698 return false;
699 return true;
703 /* Return relative time improvement for inlining EDGE in range
704 1...2^9. */
706 static inline int
707 relative_time_benefit (struct inline_summary *callee_info,
708 struct cgraph_edge *edge,
709 int time_growth)
711 int relbenefit;
712 gcov_type uninlined_call_time;
714 uninlined_call_time =
715 ((gcov_type)
716 (callee_info->time
717 + inline_edge_summary (edge)->call_stmt_time) * edge->frequency
718 + CGRAPH_FREQ_BASE / 2) / CGRAPH_FREQ_BASE;
719 /* Compute relative time benefit, i.e. how much the call becomes faster.
720 ??? perhaps computing how much the caller+calle together become faster
721 would lead to more realistic results. */
722 if (!uninlined_call_time)
723 uninlined_call_time = 1;
724 relbenefit =
725 (uninlined_call_time - time_growth) * 256 / (uninlined_call_time);
726 relbenefit = MIN (relbenefit, 512);
727 relbenefit = MAX (relbenefit, 1);
728 return relbenefit;
732 /* A cost model driving the inlining heuristics in a way so the edges with
733 smallest badness are inlined first. After each inlining is performed
734 the costs of all caller edges of nodes affected are recomputed so the
735 metrics may accurately depend on values such as number of inlinable callers
736 of the function or function body size. */
738 static int
739 edge_badness (struct cgraph_edge *edge, bool dump)
741 gcov_type badness;
742 int growth, time_growth;
743 struct cgraph_node *callee = cgraph_function_or_thunk_node (edge->callee,
744 NULL);
745 struct inline_summary *callee_info = inline_summary (callee);
747 if (DECL_DISREGARD_INLINE_LIMITS (callee->symbol.decl))
748 return INT_MIN;
750 growth = estimate_edge_growth (edge);
751 time_growth = estimate_edge_time (edge);
753 if (dump)
755 fprintf (dump_file, " Badness calculation for %s -> %s\n",
756 xstrdup (cgraph_node_name (edge->caller)),
757 xstrdup (cgraph_node_name (callee)));
758 fprintf (dump_file, " size growth %i, time growth %i\n",
759 growth,
760 time_growth);
763 /* Always prefer inlining saving code size. */
764 if (growth <= 0)
766 badness = INT_MIN / 2 + growth;
767 if (dump)
768 fprintf (dump_file, " %i: Growth %i <= 0\n", (int) badness,
769 growth);
772 /* When profiling is available, compute badness as:
774 relative_edge_count * relative_time_benefit
775 goodness = -------------------------------------------
776 edge_growth
777 badness = -goodness
779 The fraction is upside down, because on edge counts and time beneits
780 the bounds are known. Edge growth is essentially unlimited. */
782 else if (max_count)
784 int relbenefit = relative_time_benefit (callee_info, edge, time_growth);
785 badness =
786 ((int)
787 ((double) edge->count * INT_MIN / 2 / max_count / 512) *
788 relative_time_benefit (callee_info, edge, time_growth)) / growth;
790 /* Be sure that insanity of the profile won't lead to increasing counts
791 in the scalling and thus to overflow in the computation above. */
792 gcc_assert (max_count >= edge->count);
793 if (dump)
795 fprintf (dump_file,
796 " %i (relative %f): profile info. Relative count %f"
797 " * Relative benefit %f\n",
798 (int) badness, (double) badness / INT_MIN,
799 (double) edge->count / max_count,
800 relbenefit * 100 / 256.0);
804 /* When function local profile is available. Compute badness as:
807 growth_of_callee
808 badness = -------------------------------------- + growth_for-all
809 relative_time_benefit * edge_frequency
812 else if (flag_guess_branch_prob)
814 int div = edge->frequency * (1<<10) / CGRAPH_FREQ_MAX;
816 div = MAX (div, 1);
817 gcc_checking_assert (edge->frequency <= CGRAPH_FREQ_MAX);
818 div *= relative_time_benefit (callee_info, edge, time_growth);
820 /* frequency is normalized in range 1...2^10.
821 relbenefit in range 1...2^9
822 DIV should be in range 1....2^19. */
823 gcc_checking_assert (div >= 1 && div <= (1<<19));
825 /* Result must be integer in range 0...INT_MAX.
826 Set the base of fixed point calculation so we don't lose much of
827 precision for small bandesses (those are interesting) yet we don't
828 overflow for growths that are still in interesting range.
830 Fixed point arithmetic with point at 8th bit. */
831 badness = ((gcov_type)growth) * (1<<(19+8));
832 badness = (badness + div / 2) / div;
834 /* Overall growth of inlining all calls of function matters: we want to
835 inline so offline copy of function is no longer needed.
837 Additionally functions that can be fully inlined without much of
838 effort are better inline candidates than functions that can be fully
839 inlined only after noticeable overall unit growths. The latter
840 are better in a sense compressing of code size by factoring out common
841 code into separate function shared by multiple code paths.
843 We might mix the valud into the fraction by taking into account
844 relative growth of the unit, but for now just add the number
845 into resulting fraction. */
846 if (badness > INT_MAX / 2)
848 badness = INT_MAX / 2;
849 if (dump)
850 fprintf (dump_file, "Badness overflow\n");
852 if (dump)
854 fprintf (dump_file,
855 " %i: guessed profile. frequency %f,"
856 " benefit %f%%, divisor %i\n",
857 (int) badness, (double)edge->frequency / CGRAPH_FREQ_BASE,
858 relative_time_benefit (callee_info, edge, time_growth) * 100 / 256.0, div);
861 /* When function local profile is not available or it does not give
862 useful information (ie frequency is zero), base the cost on
863 loop nest and overall size growth, so we optimize for overall number
864 of functions fully inlined in program. */
865 else
867 int nest = MIN (inline_edge_summary (edge)->loop_depth, 8);
868 badness = growth * 256;
870 /* Decrease badness if call is nested. */
871 if (badness > 0)
872 badness >>= nest;
873 else
875 badness <<= nest;
877 if (dump)
878 fprintf (dump_file, " %i: no profile. nest %i\n", (int) badness,
879 nest);
882 /* Ensure that we did not overflow in all the fixed point math above. */
883 gcc_assert (badness >= INT_MIN);
884 gcc_assert (badness <= INT_MAX - 1);
885 /* Make recursive inlining happen always after other inlining is done. */
886 if (cgraph_edge_recursive_p (edge))
887 return badness + 1;
888 else
889 return badness;
892 /* Recompute badness of EDGE and update its key in HEAP if needed. */
893 static inline void
894 update_edge_key (fibheap_t heap, struct cgraph_edge *edge)
896 int badness = edge_badness (edge, false);
897 if (edge->aux)
899 fibnode_t n = (fibnode_t) edge->aux;
900 gcc_checking_assert (n->data == edge);
902 /* fibheap_replace_key only decrease the keys.
903 When we increase the key we do not update heap
904 and instead re-insert the element once it becomes
905 a minimum of heap. */
906 if (badness < n->key)
908 if (dump_file && (dump_flags & TDF_DETAILS))
910 fprintf (dump_file,
911 " decreasing badness %s/%i -> %s/%i, %i to %i\n",
912 xstrdup (cgraph_node_name (edge->caller)),
913 edge->caller->uid,
914 xstrdup (cgraph_node_name (edge->callee)),
915 edge->callee->uid,
916 (int)n->key,
917 badness);
919 fibheap_replace_key (heap, n, badness);
920 gcc_checking_assert (n->key == badness);
923 else
925 if (dump_file && (dump_flags & TDF_DETAILS))
927 fprintf (dump_file,
928 " enqueuing call %s/%i -> %s/%i, badness %i\n",
929 xstrdup (cgraph_node_name (edge->caller)),
930 edge->caller->uid,
931 xstrdup (cgraph_node_name (edge->callee)),
932 edge->callee->uid,
933 badness);
935 edge->aux = fibheap_insert (heap, badness, edge);
940 /* NODE was inlined.
941 All caller edges needs to be resetted because
942 size estimates change. Similarly callees needs reset
943 because better context may be known. */
945 static void
946 reset_edge_caches (struct cgraph_node *node)
948 struct cgraph_edge *edge;
949 struct cgraph_edge *e = node->callees;
950 struct cgraph_node *where = node;
951 int i;
952 struct ipa_ref *ref;
954 if (where->global.inlined_to)
955 where = where->global.inlined_to;
957 /* WHERE body size has changed, the cached growth is invalid. */
958 reset_node_growth_cache (where);
960 for (edge = where->callers; edge; edge = edge->next_caller)
961 if (edge->inline_failed)
962 reset_edge_growth_cache (edge);
963 for (i = 0; ipa_ref_list_referring_iterate (&where->symbol.ref_list,
964 i, ref); i++)
965 if (ref->use == IPA_REF_ALIAS)
966 reset_edge_caches (ipa_ref_referring_node (ref));
968 if (!e)
969 return;
971 while (true)
972 if (!e->inline_failed && e->callee->callees)
973 e = e->callee->callees;
974 else
976 if (e->inline_failed)
977 reset_edge_growth_cache (e);
978 if (e->next_callee)
979 e = e->next_callee;
980 else
984 if (e->caller == node)
985 return;
986 e = e->caller->callers;
988 while (!e->next_callee);
989 e = e->next_callee;
994 /* Recompute HEAP nodes for each of caller of NODE.
995 UPDATED_NODES track nodes we already visited, to avoid redundant work.
996 When CHECK_INLINABLITY_FOR is set, re-check for specified edge that
997 it is inlinable. Otherwise check all edges. */
999 static void
1000 update_caller_keys (fibheap_t heap, struct cgraph_node *node,
1001 bitmap updated_nodes,
1002 struct cgraph_edge *check_inlinablity_for)
1004 struct cgraph_edge *edge;
1005 int i;
1006 struct ipa_ref *ref;
1008 if ((!node->alias && !inline_summary (node)->inlinable)
1009 || cgraph_function_body_availability (node) <= AVAIL_OVERWRITABLE
1010 || node->global.inlined_to)
1011 return;
1012 if (!bitmap_set_bit (updated_nodes, node->uid))
1013 return;
1015 for (i = 0; ipa_ref_list_referring_iterate (&node->symbol.ref_list,
1016 i, ref); i++)
1017 if (ref->use == IPA_REF_ALIAS)
1019 struct cgraph_node *alias = ipa_ref_referring_node (ref);
1020 update_caller_keys (heap, alias, updated_nodes, check_inlinablity_for);
1023 for (edge = node->callers; edge; edge = edge->next_caller)
1024 if (edge->inline_failed)
1026 if (!check_inlinablity_for
1027 || check_inlinablity_for == edge)
1029 if (can_inline_edge_p (edge, false)
1030 && want_inline_small_function_p (edge, false))
1031 update_edge_key (heap, edge);
1032 else if (edge->aux)
1034 report_inline_failed_reason (edge);
1035 fibheap_delete_node (heap, (fibnode_t) edge->aux);
1036 edge->aux = NULL;
1039 else if (edge->aux)
1040 update_edge_key (heap, edge);
1044 /* Recompute HEAP nodes for each uninlined call in NODE.
1045 This is used when we know that edge badnesses are going only to increase
1046 (we introduced new call site) and thus all we need is to insert newly
1047 created edges into heap. */
1049 static void
1050 update_callee_keys (fibheap_t heap, struct cgraph_node *node,
1051 bitmap updated_nodes)
1053 struct cgraph_edge *e = node->callees;
1055 if (!e)
1056 return;
1057 while (true)
1058 if (!e->inline_failed && e->callee->callees)
1059 e = e->callee->callees;
1060 else
1062 enum availability avail;
1063 struct cgraph_node *callee;
1064 /* We do not reset callee growth cache here. Since we added a new call,
1065 growth chould have just increased and consequentely badness metric
1066 don't need updating. */
1067 if (e->inline_failed
1068 && (callee = cgraph_function_or_thunk_node (e->callee, &avail))
1069 && inline_summary (callee)->inlinable
1070 && cgraph_function_body_availability (callee) >= AVAIL_AVAILABLE
1071 && !bitmap_bit_p (updated_nodes, callee->uid))
1073 if (can_inline_edge_p (e, false)
1074 && want_inline_small_function_p (e, false))
1075 update_edge_key (heap, e);
1076 else if (e->aux)
1078 report_inline_failed_reason (e);
1079 fibheap_delete_node (heap, (fibnode_t) e->aux);
1080 e->aux = NULL;
1083 if (e->next_callee)
1084 e = e->next_callee;
1085 else
1089 if (e->caller == node)
1090 return;
1091 e = e->caller->callers;
1093 while (!e->next_callee);
1094 e = e->next_callee;
1099 /* Enqueue all recursive calls from NODE into priority queue depending on
1100 how likely we want to recursively inline the call. */
1102 static void
1103 lookup_recursive_calls (struct cgraph_node *node, struct cgraph_node *where,
1104 fibheap_t heap)
1106 struct cgraph_edge *e;
1107 enum availability avail;
1109 for (e = where->callees; e; e = e->next_callee)
1110 if (e->callee == node
1111 || (cgraph_function_or_thunk_node (e->callee, &avail) == node
1112 && avail > AVAIL_OVERWRITABLE))
1114 /* When profile feedback is available, prioritize by expected number
1115 of calls. */
1116 fibheap_insert (heap,
1117 !max_count ? -e->frequency
1118 : -(e->count / ((max_count + (1<<24) - 1) / (1<<24))),
1121 for (e = where->callees; e; e = e->next_callee)
1122 if (!e->inline_failed)
1123 lookup_recursive_calls (node, e->callee, heap);
1126 /* Decide on recursive inlining: in the case function has recursive calls,
1127 inline until body size reaches given argument. If any new indirect edges
1128 are discovered in the process, add them to *NEW_EDGES, unless NEW_EDGES
1129 is NULL. */
1131 static bool
1132 recursive_inlining (struct cgraph_edge *edge,
1133 VEC (cgraph_edge_p, heap) **new_edges)
1135 int limit = PARAM_VALUE (PARAM_MAX_INLINE_INSNS_RECURSIVE_AUTO);
1136 fibheap_t heap;
1137 struct cgraph_node *node;
1138 struct cgraph_edge *e;
1139 struct cgraph_node *master_clone = NULL, *next;
1140 int depth = 0;
1141 int n = 0;
1143 node = edge->caller;
1144 if (node->global.inlined_to)
1145 node = node->global.inlined_to;
1147 if (DECL_DECLARED_INLINE_P (node->symbol.decl))
1148 limit = PARAM_VALUE (PARAM_MAX_INLINE_INSNS_RECURSIVE);
1150 /* Make sure that function is small enough to be considered for inlining. */
1151 if (estimate_size_after_inlining (node, edge) >= limit)
1152 return false;
1153 heap = fibheap_new ();
1154 lookup_recursive_calls (node, node, heap);
1155 if (fibheap_empty (heap))
1157 fibheap_delete (heap);
1158 return false;
1161 if (dump_file)
1162 fprintf (dump_file,
1163 " Performing recursive inlining on %s\n",
1164 cgraph_node_name (node));
1166 /* Do the inlining and update list of recursive call during process. */
1167 while (!fibheap_empty (heap))
1169 struct cgraph_edge *curr
1170 = (struct cgraph_edge *) fibheap_extract_min (heap);
1171 struct cgraph_node *cnode;
1173 if (estimate_size_after_inlining (node, curr) > limit)
1174 break;
1176 if (!can_inline_edge_p (curr, true))
1177 continue;
1179 depth = 1;
1180 for (cnode = curr->caller;
1181 cnode->global.inlined_to; cnode = cnode->callers->caller)
1182 if (node->symbol.decl
1183 == cgraph_function_or_thunk_node (curr->callee, NULL)->symbol.decl)
1184 depth++;
1186 if (!want_inline_self_recursive_call_p (curr, node, false, depth))
1187 continue;
1189 if (dump_file)
1191 fprintf (dump_file,
1192 " Inlining call of depth %i", depth);
1193 if (node->count)
1195 fprintf (dump_file, " called approx. %.2f times per call",
1196 (double)curr->count / node->count);
1198 fprintf (dump_file, "\n");
1200 if (!master_clone)
1202 /* We need original clone to copy around. */
1203 master_clone = cgraph_clone_node (node, node->symbol.decl,
1204 node->count, CGRAPH_FREQ_BASE,
1205 false, NULL, true);
1206 for (e = master_clone->callees; e; e = e->next_callee)
1207 if (!e->inline_failed)
1208 clone_inlined_nodes (e, true, false, NULL);
1211 cgraph_redirect_edge_callee (curr, master_clone);
1212 inline_call (curr, false, new_edges, &overall_size);
1213 lookup_recursive_calls (node, curr->callee, heap);
1214 n++;
1217 if (!fibheap_empty (heap) && dump_file)
1218 fprintf (dump_file, " Recursive inlining growth limit met.\n");
1219 fibheap_delete (heap);
1221 if (!master_clone)
1222 return false;
1224 if (dump_file)
1225 fprintf (dump_file,
1226 "\n Inlined %i times, "
1227 "body grown from size %i to %i, time %i to %i\n", n,
1228 inline_summary (master_clone)->size, inline_summary (node)->size,
1229 inline_summary (master_clone)->time, inline_summary (node)->time);
1231 /* Remove master clone we used for inlining. We rely that clones inlined
1232 into master clone gets queued just before master clone so we don't
1233 need recursion. */
1234 for (node = cgraph_first_function (); node != master_clone;
1235 node = next)
1237 next = cgraph_next_function (node);
1238 if (node->global.inlined_to == master_clone)
1239 cgraph_remove_node (node);
1241 cgraph_remove_node (master_clone);
1242 return true;
1246 /* Given whole compilation unit estimate of INSNS, compute how large we can
1247 allow the unit to grow. */
1249 static int
1250 compute_max_insns (int insns)
1252 int max_insns = insns;
1253 if (max_insns < PARAM_VALUE (PARAM_LARGE_UNIT_INSNS))
1254 max_insns = PARAM_VALUE (PARAM_LARGE_UNIT_INSNS);
1256 return ((HOST_WIDEST_INT) max_insns
1257 * (100 + PARAM_VALUE (PARAM_INLINE_UNIT_GROWTH)) / 100);
1261 /* Compute badness of all edges in NEW_EDGES and add them to the HEAP. */
1263 static void
1264 add_new_edges_to_heap (fibheap_t heap, VEC (cgraph_edge_p, heap) *new_edges)
1266 while (VEC_length (cgraph_edge_p, new_edges) > 0)
1268 struct cgraph_edge *edge = VEC_pop (cgraph_edge_p, new_edges);
1270 gcc_assert (!edge->aux);
1271 if (edge->inline_failed
1272 && can_inline_edge_p (edge, true)
1273 && want_inline_small_function_p (edge, true))
1274 edge->aux = fibheap_insert (heap, edge_badness (edge, false), edge);
1279 /* We use greedy algorithm for inlining of small functions:
1280 All inline candidates are put into prioritized heap ordered in
1281 increasing badness.
1283 The inlining of small functions is bounded by unit growth parameters. */
1285 static void
1286 inline_small_functions (void)
1288 struct cgraph_node *node;
1289 struct cgraph_edge *edge;
1290 fibheap_t heap = fibheap_new ();
1291 bitmap updated_nodes = BITMAP_ALLOC (NULL);
1292 int min_size, max_size;
1293 VEC (cgraph_edge_p, heap) *new_indirect_edges = NULL;
1294 int initial_size = 0;
1296 if (flag_indirect_inlining)
1297 new_indirect_edges = VEC_alloc (cgraph_edge_p, heap, 8);
1299 if (dump_file)
1300 fprintf (dump_file,
1301 "\nDeciding on inlining of small functions. Starting with size %i.\n",
1302 initial_size);
1304 /* Compute overall unit size and other global parameters used by badness
1305 metrics. */
1307 max_count = 0;
1308 initialize_growth_caches ();
1310 FOR_EACH_DEFINED_FUNCTION (node)
1311 if (!node->global.inlined_to)
1313 if (cgraph_function_with_gimple_body_p (node)
1314 || node->thunk.thunk_p)
1316 struct inline_summary *info = inline_summary (node);
1318 if (!DECL_EXTERNAL (node->symbol.decl))
1319 initial_size += info->size;
1322 for (edge = node->callers; edge; edge = edge->next_caller)
1323 if (max_count < edge->count)
1324 max_count = edge->count;
1327 overall_size = initial_size;
1328 max_size = compute_max_insns (overall_size);
1329 min_size = overall_size;
1331 /* Populate the heeap with all edges we might inline. */
1333 FOR_EACH_DEFINED_FUNCTION (node)
1334 if (!node->global.inlined_to)
1336 if (dump_file)
1337 fprintf (dump_file, "Enqueueing calls of %s/%i.\n",
1338 cgraph_node_name (node), node->uid);
1340 for (edge = node->callers; edge; edge = edge->next_caller)
1341 if (edge->inline_failed
1342 && can_inline_edge_p (edge, true)
1343 && want_inline_small_function_p (edge, true)
1344 && edge->inline_failed)
1346 gcc_assert (!edge->aux);
1347 update_edge_key (heap, edge);
1351 gcc_assert (in_lto_p
1352 || !max_count
1353 || (profile_info && flag_branch_probabilities));
1355 while (!fibheap_empty (heap))
1357 int old_size = overall_size;
1358 struct cgraph_node *where, *callee;
1359 int badness = fibheap_min_key (heap);
1360 int current_badness;
1361 int cached_badness;
1362 int growth;
1364 edge = (struct cgraph_edge *) fibheap_extract_min (heap);
1365 gcc_assert (edge->aux);
1366 edge->aux = NULL;
1367 if (!edge->inline_failed)
1368 continue;
1370 /* Be sure that caches are maintained consistent.
1371 We can not make this ENABLE_CHECKING only because it cause different
1372 updates of the fibheap queue. */
1373 cached_badness = edge_badness (edge, false);
1374 reset_edge_growth_cache (edge);
1375 reset_node_growth_cache (edge->callee);
1377 /* When updating the edge costs, we only decrease badness in the keys.
1378 Increases of badness are handled lazilly; when we see key with out
1379 of date value on it, we re-insert it now. */
1380 current_badness = edge_badness (edge, false);
1381 gcc_assert (cached_badness == current_badness);
1382 gcc_assert (current_badness >= badness);
1383 if (current_badness != badness)
1385 edge->aux = fibheap_insert (heap, current_badness, edge);
1386 continue;
1389 if (!can_inline_edge_p (edge, true))
1390 continue;
1392 callee = cgraph_function_or_thunk_node (edge->callee, NULL);
1393 growth = estimate_edge_growth (edge);
1394 if (dump_file)
1396 fprintf (dump_file,
1397 "\nConsidering %s with %i size\n",
1398 cgraph_node_name (callee),
1399 inline_summary (callee)->size);
1400 fprintf (dump_file,
1401 " to be inlined into %s in %s:%i\n"
1402 " Estimated growth after inlined into all is %+i insns.\n"
1403 " Estimated badness is %i, frequency %.2f.\n",
1404 cgraph_node_name (edge->caller),
1405 flag_wpa ? "unknown"
1406 : gimple_filename ((const_gimple) edge->call_stmt),
1407 flag_wpa ? -1
1408 : gimple_lineno ((const_gimple) edge->call_stmt),
1409 estimate_growth (callee),
1410 badness,
1411 edge->frequency / (double)CGRAPH_FREQ_BASE);
1412 if (edge->count)
1413 fprintf (dump_file," Called "HOST_WIDEST_INT_PRINT_DEC"x\n",
1414 edge->count);
1415 if (dump_flags & TDF_DETAILS)
1416 edge_badness (edge, true);
1419 if (overall_size + growth > max_size
1420 && !DECL_DISREGARD_INLINE_LIMITS (callee->symbol.decl))
1422 edge->inline_failed = CIF_INLINE_UNIT_GROWTH_LIMIT;
1423 report_inline_failed_reason (edge);
1424 continue;
1427 if (!want_inline_small_function_p (edge, true))
1428 continue;
1430 /* Heuristics for inlining small functions works poorly for
1431 recursive calls where we do efect similar to loop unrolling.
1432 When inliing such edge seems profitable, leave decision on
1433 specific inliner. */
1434 if (cgraph_edge_recursive_p (edge))
1436 where = edge->caller;
1437 if (where->global.inlined_to)
1438 where = where->global.inlined_to;
1439 if (!recursive_inlining (edge,
1440 flag_indirect_inlining
1441 ? &new_indirect_edges : NULL))
1443 edge->inline_failed = CIF_RECURSIVE_INLINING;
1444 continue;
1446 reset_edge_caches (where);
1447 /* Recursive inliner inlines all recursive calls of the function
1448 at once. Consequently we need to update all callee keys. */
1449 if (flag_indirect_inlining)
1450 add_new_edges_to_heap (heap, new_indirect_edges);
1451 update_callee_keys (heap, where, updated_nodes);
1453 else
1455 struct cgraph_node *outer_node = NULL;
1456 int depth = 0;
1458 /* Consider the case where self recursive function A is inlined into B.
1459 This is desired optimization in some cases, since it leads to effect
1460 similar of loop peeling and we might completely optimize out the
1461 recursive call. However we must be extra selective. */
1463 where = edge->caller;
1464 while (where->global.inlined_to)
1466 if (where->symbol.decl == callee->symbol.decl)
1467 outer_node = where, depth++;
1468 where = where->callers->caller;
1470 if (outer_node
1471 && !want_inline_self_recursive_call_p (edge, outer_node,
1472 true, depth))
1474 edge->inline_failed
1475 = (DECL_DISREGARD_INLINE_LIMITS (edge->callee->symbol.decl)
1476 ? CIF_RECURSIVE_INLINING : CIF_UNSPECIFIED);
1477 continue;
1479 else if (depth && dump_file)
1480 fprintf (dump_file, " Peeling recursion with depth %i\n", depth);
1482 gcc_checking_assert (!callee->global.inlined_to);
1483 inline_call (edge, true, &new_indirect_edges, &overall_size);
1484 if (flag_indirect_inlining)
1485 add_new_edges_to_heap (heap, new_indirect_edges);
1487 reset_edge_caches (edge->callee);
1488 reset_node_growth_cache (callee);
1490 update_callee_keys (heap, edge->callee, updated_nodes);
1492 where = edge->caller;
1493 if (where->global.inlined_to)
1494 where = where->global.inlined_to;
1496 /* Our profitability metric can depend on local properties
1497 such as number of inlinable calls and size of the function body.
1498 After inlining these properties might change for the function we
1499 inlined into (since it's body size changed) and for the functions
1500 called by function we inlined (since number of it inlinable callers
1501 might change). */
1502 update_caller_keys (heap, where, updated_nodes, NULL);
1503 bitmap_clear (updated_nodes);
1505 if (dump_file)
1507 fprintf (dump_file,
1508 " Inlined into %s which now has time %i and size %i,"
1509 "net change of %+i.\n",
1510 cgraph_node_name (edge->caller),
1511 inline_summary (edge->caller)->time,
1512 inline_summary (edge->caller)->size,
1513 overall_size - old_size);
1515 if (min_size > overall_size)
1517 min_size = overall_size;
1518 max_size = compute_max_insns (min_size);
1520 if (dump_file)
1521 fprintf (dump_file, "New minimal size reached: %i\n", min_size);
1525 free_growth_caches ();
1526 if (new_indirect_edges)
1527 VEC_free (cgraph_edge_p, heap, new_indirect_edges);
1528 fibheap_delete (heap);
1529 if (dump_file)
1530 fprintf (dump_file,
1531 "Unit growth for small function inlining: %i->%i (%i%%)\n",
1532 initial_size, overall_size,
1533 initial_size ? overall_size * 100 / (initial_size) - 100: 0);
1534 BITMAP_FREE (updated_nodes);
1537 /* Flatten NODE. Performed both during early inlining and
1538 at IPA inlining time. */
1540 static void
1541 flatten_function (struct cgraph_node *node, bool early)
1543 struct cgraph_edge *e;
1545 /* We shouldn't be called recursively when we are being processed. */
1546 gcc_assert (node->symbol.aux == NULL);
1548 node->symbol.aux = (void *) node;
1550 for (e = node->callees; e; e = e->next_callee)
1552 struct cgraph_node *orig_callee;
1553 struct cgraph_node *callee = cgraph_function_or_thunk_node (e->callee, NULL);
1555 /* We've hit cycle? It is time to give up. */
1556 if (callee->symbol.aux)
1558 if (dump_file)
1559 fprintf (dump_file,
1560 "Not inlining %s into %s to avoid cycle.\n",
1561 xstrdup (cgraph_node_name (callee)),
1562 xstrdup (cgraph_node_name (e->caller)));
1563 e->inline_failed = CIF_RECURSIVE_INLINING;
1564 continue;
1567 /* When the edge is already inlined, we just need to recurse into
1568 it in order to fully flatten the leaves. */
1569 if (!e->inline_failed)
1571 flatten_function (callee, early);
1572 continue;
1575 /* Flatten attribute needs to be processed during late inlining. For
1576 extra code quality we however do flattening during early optimization,
1577 too. */
1578 if (!early
1579 ? !can_inline_edge_p (e, true)
1580 : !can_early_inline_edge_p (e))
1581 continue;
1583 if (cgraph_edge_recursive_p (e))
1585 if (dump_file)
1586 fprintf (dump_file, "Not inlining: recursive call.\n");
1587 continue;
1590 if (gimple_in_ssa_p (DECL_STRUCT_FUNCTION (node->symbol.decl))
1591 != gimple_in_ssa_p (DECL_STRUCT_FUNCTION (callee->symbol.decl)))
1593 if (dump_file)
1594 fprintf (dump_file, "Not inlining: SSA form does not match.\n");
1595 continue;
1598 /* Inline the edge and flatten the inline clone. Avoid
1599 recursing through the original node if the node was cloned. */
1600 if (dump_file)
1601 fprintf (dump_file, " Inlining %s into %s.\n",
1602 xstrdup (cgraph_node_name (callee)),
1603 xstrdup (cgraph_node_name (e->caller)));
1604 orig_callee = callee;
1605 inline_call (e, true, NULL, NULL);
1606 if (e->callee != orig_callee)
1607 orig_callee->symbol.aux = (void *) node;
1608 flatten_function (e->callee, early);
1609 if (e->callee != orig_callee)
1610 orig_callee->symbol.aux = NULL;
1613 node->symbol.aux = NULL;
1616 /* Decide on the inlining. We do so in the topological order to avoid
1617 expenses on updating data structures. */
1619 static unsigned int
1620 ipa_inline (void)
1622 struct cgraph_node *node;
1623 int nnodes;
1624 struct cgraph_node **order =
1625 XCNEWVEC (struct cgraph_node *, cgraph_n_nodes);
1626 int i;
1628 if (in_lto_p && optimize)
1629 ipa_update_after_lto_read ();
1631 if (dump_file)
1632 dump_inline_summaries (dump_file);
1634 nnodes = ipa_reverse_postorder (order);
1636 FOR_EACH_FUNCTION (node)
1637 node->symbol.aux = 0;
1639 if (dump_file)
1640 fprintf (dump_file, "\nFlattening functions:\n");
1642 /* In the first pass handle functions to be flattened. Do this with
1643 a priority so none of our later choices will make this impossible. */
1644 for (i = nnodes - 1; i >= 0; i--)
1646 node = order[i];
1648 /* Handle nodes to be flattened.
1649 Ideally when processing callees we stop inlining at the
1650 entry of cycles, possibly cloning that entry point and
1651 try to flatten itself turning it into a self-recursive
1652 function. */
1653 if (lookup_attribute ("flatten",
1654 DECL_ATTRIBUTES (node->symbol.decl)) != NULL)
1656 if (dump_file)
1657 fprintf (dump_file,
1658 "Flattening %s\n", cgraph_node_name (node));
1659 flatten_function (node, false);
1663 inline_small_functions ();
1664 symtab_remove_unreachable_nodes (true, dump_file);
1665 free (order);
1667 /* We already perform some inlining of functions called once during
1668 inlining small functions above. After unreachable nodes are removed,
1669 we still might do a quick check that nothing new is found. */
1670 if (flag_inline_functions_called_once)
1672 int cold;
1673 if (dump_file)
1674 fprintf (dump_file, "\nDeciding on functions called once:\n");
1676 /* Inlining one function called once has good chance of preventing
1677 inlining other function into the same callee. Ideally we should
1678 work in priority order, but probably inlining hot functions first
1679 is good cut without the extra pain of maintaining the queue.
1681 ??? this is not really fitting the bill perfectly: inlining function
1682 into callee often leads to better optimization of callee due to
1683 increased context for optimization.
1684 For example if main() function calls a function that outputs help
1685 and then function that does the main optmization, we should inline
1686 the second with priority even if both calls are cold by themselves.
1688 We probably want to implement new predicate replacing our use of
1689 maybe_hot_edge interpreted as maybe_hot_edge || callee is known
1690 to be hot. */
1691 for (cold = 0; cold <= 1; cold ++)
1693 FOR_EACH_DEFINED_FUNCTION (node)
1695 if (want_inline_function_called_once_p (node)
1696 && (cold
1697 || cgraph_maybe_hot_edge_p (node->callers)))
1699 struct cgraph_node *caller = node->callers->caller;
1701 if (dump_file)
1703 fprintf (dump_file,
1704 "\nInlining %s size %i.\n",
1705 cgraph_node_name (node),
1706 inline_summary (node)->size);
1707 fprintf (dump_file,
1708 " Called once from %s %i insns.\n",
1709 cgraph_node_name (node->callers->caller),
1710 inline_summary (node->callers->caller)->size);
1713 inline_call (node->callers, true, NULL, NULL);
1714 if (dump_file)
1715 fprintf (dump_file,
1716 " Inlined into %s which now has %i size\n",
1717 cgraph_node_name (caller),
1718 inline_summary (caller)->size);
1724 /* Free ipa-prop structures if they are no longer needed. */
1725 if (optimize)
1726 ipa_free_all_structures_after_iinln ();
1728 if (dump_file)
1729 fprintf (dump_file,
1730 "\nInlined %i calls, eliminated %i functions\n\n",
1731 ncalls_inlined, nfunctions_inlined);
1733 if (dump_file)
1734 dump_inline_summaries (dump_file);
1735 /* In WPA we use inline summaries for partitioning process. */
1736 if (!flag_wpa)
1737 inline_free_summary ();
1738 return 0;
1741 /* Inline always-inline function calls in NODE. */
1743 static bool
1744 inline_always_inline_functions (struct cgraph_node *node)
1746 struct cgraph_edge *e;
1747 bool inlined = false;
1749 for (e = node->callees; e; e = e->next_callee)
1751 struct cgraph_node *callee = cgraph_function_or_thunk_node (e->callee, NULL);
1752 if (!DECL_DISREGARD_INLINE_LIMITS (callee->symbol.decl))
1753 continue;
1755 if (cgraph_edge_recursive_p (e))
1757 if (dump_file)
1758 fprintf (dump_file, " Not inlining recursive call to %s.\n",
1759 cgraph_node_name (e->callee));
1760 e->inline_failed = CIF_RECURSIVE_INLINING;
1761 continue;
1764 if (!can_early_inline_edge_p (e))
1765 continue;
1767 if (dump_file)
1768 fprintf (dump_file, " Inlining %s into %s (always_inline).\n",
1769 xstrdup (cgraph_node_name (e->callee)),
1770 xstrdup (cgraph_node_name (e->caller)));
1771 inline_call (e, true, NULL, NULL);
1772 inlined = true;
1775 return inlined;
1778 /* Decide on the inlining. We do so in the topological order to avoid
1779 expenses on updating data structures. */
1781 static bool
1782 early_inline_small_functions (struct cgraph_node *node)
1784 struct cgraph_edge *e;
1785 bool inlined = false;
1787 for (e = node->callees; e; e = e->next_callee)
1789 struct cgraph_node *callee = cgraph_function_or_thunk_node (e->callee, NULL);
1790 if (!inline_summary (callee)->inlinable
1791 || !e->inline_failed)
1792 continue;
1794 /* Do not consider functions not declared inline. */
1795 if (!DECL_DECLARED_INLINE_P (callee->symbol.decl)
1796 && !flag_inline_small_functions
1797 && !flag_inline_functions)
1798 continue;
1800 if (dump_file)
1801 fprintf (dump_file, "Considering inline candidate %s.\n",
1802 cgraph_node_name (callee));
1804 if (!can_early_inline_edge_p (e))
1805 continue;
1807 if (cgraph_edge_recursive_p (e))
1809 if (dump_file)
1810 fprintf (dump_file, " Not inlining: recursive call.\n");
1811 continue;
1814 if (!want_early_inline_function_p (e))
1815 continue;
1817 if (dump_file)
1818 fprintf (dump_file, " Inlining %s into %s.\n",
1819 xstrdup (cgraph_node_name (callee)),
1820 xstrdup (cgraph_node_name (e->caller)));
1821 inline_call (e, true, NULL, NULL);
1822 inlined = true;
1825 return inlined;
1828 /* Do inlining of small functions. Doing so early helps profiling and other
1829 passes to be somewhat more effective and avoids some code duplication in
1830 later real inlining pass for testcases with very many function calls. */
1831 static unsigned int
1832 early_inliner (void)
1834 struct cgraph_node *node = cgraph_get_node (current_function_decl);
1835 struct cgraph_edge *edge;
1836 unsigned int todo = 0;
1837 int iterations = 0;
1838 bool inlined = false;
1840 if (seen_error ())
1841 return 0;
1843 /* Do nothing if datastructures for ipa-inliner are already computed. This
1844 happens when some pass decides to construct new function and
1845 cgraph_add_new_function calls lowering passes and early optimization on
1846 it. This may confuse ourself when early inliner decide to inline call to
1847 function clone, because function clones don't have parameter list in
1848 ipa-prop matching their signature. */
1849 if (ipa_node_params_vector)
1850 return 0;
1852 #ifdef ENABLE_CHECKING
1853 verify_cgraph_node (node);
1854 #endif
1856 /* Even when not optimizing or not inlining inline always-inline
1857 functions. */
1858 inlined = inline_always_inline_functions (node);
1860 if (!optimize
1861 || flag_no_inline
1862 || !flag_early_inlining
1863 /* Never inline regular functions into always-inline functions
1864 during incremental inlining. This sucks as functions calling
1865 always inline functions will get less optimized, but at the
1866 same time inlining of functions calling always inline
1867 function into an always inline function might introduce
1868 cycles of edges to be always inlined in the callgraph.
1870 We might want to be smarter and just avoid this type of inlining. */
1871 || DECL_DISREGARD_INLINE_LIMITS (node->symbol.decl))
1873 else if (lookup_attribute ("flatten",
1874 DECL_ATTRIBUTES (node->symbol.decl)) != NULL)
1876 /* When the function is marked to be flattened, recursively inline
1877 all calls in it. */
1878 if (dump_file)
1879 fprintf (dump_file,
1880 "Flattening %s\n", cgraph_node_name (node));
1881 flatten_function (node, true);
1882 inlined = true;
1884 else
1886 /* We iterate incremental inlining to get trivial cases of indirect
1887 inlining. */
1888 while (iterations < PARAM_VALUE (PARAM_EARLY_INLINER_MAX_ITERATIONS)
1889 && early_inline_small_functions (node))
1891 timevar_push (TV_INTEGRATION);
1892 todo |= optimize_inline_calls (current_function_decl);
1894 /* Technically we ought to recompute inline parameters so the new
1895 iteration of early inliner works as expected. We however have
1896 values approximately right and thus we only need to update edge
1897 info that might be cleared out for newly discovered edges. */
1898 for (edge = node->callees; edge; edge = edge->next_callee)
1900 struct inline_edge_summary *es = inline_edge_summary (edge);
1901 es->call_stmt_size
1902 = estimate_num_insns (edge->call_stmt, &eni_size_weights);
1903 es->call_stmt_time
1904 = estimate_num_insns (edge->call_stmt, &eni_time_weights);
1905 if (edge->callee->symbol.decl
1906 && !gimple_check_call_matching_types (edge->call_stmt,
1907 edge->callee->symbol.decl))
1908 edge->call_stmt_cannot_inline_p = true;
1910 timevar_pop (TV_INTEGRATION);
1911 iterations++;
1912 inlined = false;
1914 if (dump_file)
1915 fprintf (dump_file, "Iterations: %i\n", iterations);
1918 if (inlined)
1920 timevar_push (TV_INTEGRATION);
1921 todo |= optimize_inline_calls (current_function_decl);
1922 timevar_pop (TV_INTEGRATION);
1925 cfun->always_inline_functions_inlined = true;
1927 return todo;
1930 struct gimple_opt_pass pass_early_inline =
1933 GIMPLE_PASS,
1934 "einline", /* name */
1935 NULL, /* gate */
1936 early_inliner, /* execute */
1937 NULL, /* sub */
1938 NULL, /* next */
1939 0, /* static_pass_number */
1940 TV_INLINE_HEURISTICS, /* tv_id */
1941 PROP_ssa, /* properties_required */
1942 0, /* properties_provided */
1943 0, /* properties_destroyed */
1944 0, /* todo_flags_start */
1945 0 /* todo_flags_finish */
1950 /* When to run IPA inlining. Inlining of always-inline functions
1951 happens during early inlining.
1953 Enable inlining unconditoinally at -flto. We need size estimates to
1954 drive partitioning. */
1956 static bool
1957 gate_ipa_inline (void)
1959 return optimize || flag_lto || flag_wpa;
1962 struct ipa_opt_pass_d pass_ipa_inline =
1965 IPA_PASS,
1966 "inline", /* name */
1967 gate_ipa_inline, /* gate */
1968 ipa_inline, /* execute */
1969 NULL, /* sub */
1970 NULL, /* next */
1971 0, /* static_pass_number */
1972 TV_INLINE_HEURISTICS, /* tv_id */
1973 0, /* properties_required */
1974 0, /* properties_provided */
1975 0, /* properties_destroyed */
1976 TODO_remove_functions, /* todo_flags_finish */
1977 TODO_dump_symtab
1978 | TODO_remove_functions | TODO_ggc_collect /* todo_flags_finish */
1980 inline_generate_summary, /* generate_summary */
1981 inline_write_summary, /* write_summary */
1982 inline_read_summary, /* read_summary */
1983 NULL, /* write_optimization_summary */
1984 NULL, /* read_optimization_summary */
1985 NULL, /* stmt_fixup */
1986 0, /* TODOs */
1987 inline_transform, /* function_transform */
1988 NULL, /* variable_transform */