1 /* Inlining decision heuristics.
2 Copyright (C) 2003, 2004, 2007, 2008, 2009, 2010
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 We separate inlining decisions from the inliner itself and store it
25 inside callgraph as so called inline plan. Refer to cgraph.c
26 documentation about particular representation of inline plans in the
29 There are three major parts of this file:
31 cgraph_mark_inline implementation
33 This function allows to mark given call inline and performs necessary
34 modifications of cgraph (production of the clones and updating overall
37 inlining heuristics limits
39 These functions allow to check that particular inlining is allowed
40 by the limits specified by user (allowed function growth, overall unit
45 This is implementation of IPA pass aiming to get as much of benefit
46 from inlining obeying the limits checked above.
48 The implementation of particular heuristics is separated from
49 the rest of code to make it easier to replace it with more complicated
50 implementation in the future. The rest of inlining code acts as a
51 library aimed to modify the callgraph and verify that the parameters
52 on code size growth fits.
54 To mark given call inline, use cgraph_mark_inline function, the
55 verification is performed by cgraph_default_inline_p and
56 cgraph_check_inline_limits.
58 The heuristics implements simple knapsack style algorithm ordering
59 all functions by their "profitability" (estimated by code size growth)
60 and inlining them in priority order.
62 cgraph_decide_inlining implements heuristics taking whole callgraph
63 into account, while cgraph_decide_inlining_incrementally considers
64 only one function at a time and is used by early inliner.
66 The inliner itself is split into several passes:
68 pass_inline_parameters
70 This pass computes local properties of functions that are used by inliner:
71 estimated function body size, whether function is inlinable at all and
72 stack frame consumption.
74 Before executing any of inliner passes, this local pass has to be applied
75 to each function in the callgraph (ie run as subpass of some earlier
76 IPA pass). The results are made out of date by any optimization applied
81 Simple local inlining pass inlining callees into current function. This
82 pass makes no global whole compilation unit analysis and this when allowed
83 to do inlining expanding code size it might result in unbounded growth of
86 The pass is run during conversion into SSA form. Only functions already
87 converted into SSA form are inlined, so the conversion must happen in
88 topological order on the callgraph (that is maintained by pass manager).
89 The functions after inlining are early optimized so the early inliner sees
90 unoptimized function itself, but all considered callees are already
91 optimized allowing it to unfold abstraction penalty on C++ effectively and
94 pass_ipa_early_inlining
96 With profiling, the early inlining is also necessary to reduce
97 instrumentation costs on program with high abstraction penalty (doing
98 many redundant calls). This can't happen in parallel with early
99 optimization and profile instrumentation, because we would end up
100 re-instrumenting already instrumented function bodies we brought in via
103 To avoid this, this pass is executed as IPA pass before profiling. It is
104 simple wrapper to pass_early_inlining and ensures first inlining.
108 This is the main pass implementing simple greedy algorithm to do inlining
109 of small functions that results in overall growth of compilation unit and
110 inlining of functions called once. The pass compute just so called inline
111 plan (representation of inlining to be done in callgraph) and unlike early
112 inlining it is not performing the inlining itself.
116 This pass performs actual inlining according to pass_ipa_inline on given
117 function. Possible the function body before inlining is saved when it is
118 needed for further inlining later.
123 #include "coretypes.h"
126 #include "tree-inline.h"
127 #include "langhooks.h"
130 #include "diagnostic.h"
131 #include "gimple-pretty-print.h"
136 #include "tree-pass.h"
138 #include "coverage.h"
140 #include "tree-flow.h"
142 #include "ipa-prop.h"
145 #define MAX_TIME 1000000000
147 /* Mode incremental inliner operate on:
149 In ALWAYS_INLINE only functions marked
150 always_inline are inlined. This mode is used after detecting cycle during
153 In SIZE mode, only functions that reduce function body size after inlining
154 are inlined, this is used during early inlining.
156 in ALL mode, everything is inlined. This is used during flattening. */
159 INLINE_ALWAYS_INLINE,
160 INLINE_SIZE_NORECURSIVE,
166 cgraph_decide_inlining_incrementally (struct cgraph_node *, enum inlining_mode);
167 static void cgraph_flatten (struct cgraph_node *node);
170 /* Statistics we collect about inlining algorithm. */
171 static int ncalls_inlined;
172 static int nfunctions_inlined;
173 static int overall_size;
174 static gcov_type max_count, max_benefit;
176 /* Holders of ipa cgraph hooks: */
177 static struct cgraph_node_hook_list *function_insertion_hook_holder;
179 static inline struct inline_summary *
180 inline_summary (struct cgraph_node *node)
182 return &node->local.inline_summary;
185 /* Estimate self time of the function after inlining WHAT into TO. */
188 cgraph_estimate_time_after_inlining (int frequency, struct cgraph_node *to,
189 struct cgraph_node *what)
191 gcov_type time = (((gcov_type)what->global.time
192 - inline_summary (what)->time_inlining_benefit)
193 * frequency + CGRAPH_FREQ_BASE / 2) / CGRAPH_FREQ_BASE
202 /* Estimate self time of the function after inlining WHAT into TO. */
205 cgraph_estimate_size_after_inlining (int times, struct cgraph_node *to,
206 struct cgraph_node *what)
208 int size = ((what->global.size - inline_summary (what)->size_inlining_benefit)
209 * times + to->global.size);
210 gcc_assert (size >= 0);
214 /* Scale frequency of NODE edges by FREQ_SCALE and increase loop nest
218 update_noncloned_frequencies (struct cgraph_node *node,
219 int freq_scale, int nest)
221 struct cgraph_edge *e;
223 /* We do not want to ignore high loop nest after freq drops to 0. */
226 for (e = node->callees; e; e = e->next_callee)
228 e->loop_nest += nest;
229 e->frequency = e->frequency * (gcov_type) freq_scale / CGRAPH_FREQ_BASE;
230 if (e->frequency > CGRAPH_FREQ_MAX)
231 e->frequency = CGRAPH_FREQ_MAX;
232 if (!e->inline_failed)
233 update_noncloned_frequencies (e->callee, freq_scale, nest);
237 /* E is expected to be an edge being inlined. Clone destination node of
238 the edge and redirect it to the new clone.
239 DUPLICATE is used for bookkeeping on whether we are actually creating new
240 clones or re-using node originally representing out-of-line function call.
243 cgraph_clone_inlined_nodes (struct cgraph_edge *e, bool duplicate,
244 bool update_original)
250 /* We may eliminate the need for out-of-line copy to be output.
251 In that case just go ahead and re-use it. */
252 if (!e->callee->callers->next_caller
253 && cgraph_can_remove_if_no_direct_calls_p (e->callee)
254 /* Inlining might enable more devirtualizing, so we want to remove
255 those only after all devirtualizable virtual calls are processed.
256 Lacking may edges in callgraph we just preserve them post
258 && (!DECL_VIRTUAL_P (e->callee->decl)
259 || (!DECL_COMDAT (e->callee->decl) && !DECL_EXTERNAL (e->callee->decl)))
260 /* Don't reuse if more than one function shares a comdat group.
261 If the other function(s) are needed, we need to emit even
262 this function out of line. */
263 && !e->callee->same_comdat_group
264 && !cgraph_new_nodes)
266 gcc_assert (!e->callee->global.inlined_to);
267 if (e->callee->analyzed)
269 overall_size -= e->callee->global.size;
270 nfunctions_inlined++;
273 e->callee->local.externally_visible = false;
274 update_noncloned_frequencies (e->callee, e->frequency, e->loop_nest);
278 struct cgraph_node *n;
279 n = cgraph_clone_node (e->callee, e->callee->decl,
280 e->count, e->frequency, e->loop_nest,
281 update_original, NULL);
282 cgraph_redirect_edge_callee (e, n);
286 if (e->caller->global.inlined_to)
287 e->callee->global.inlined_to = e->caller->global.inlined_to;
289 e->callee->global.inlined_to = e->caller;
290 e->callee->global.stack_frame_offset
291 = e->caller->global.stack_frame_offset
292 + inline_summary (e->caller)->estimated_self_stack_size;
293 peak = e->callee->global.stack_frame_offset
294 + inline_summary (e->callee)->estimated_self_stack_size;
295 if (e->callee->global.inlined_to->global.estimated_stack_size < peak)
296 e->callee->global.inlined_to->global.estimated_stack_size = peak;
297 cgraph_propagate_frequency (e->callee);
299 /* Recursively clone all bodies. */
300 for (e = e->callee->callees; e; e = e->next_callee)
301 if (!e->inline_failed)
302 cgraph_clone_inlined_nodes (e, duplicate, update_original);
305 /* Mark edge E as inlined and update callgraph accordingly. UPDATE_ORIGINAL
306 specify whether profile of original function should be updated. If any new
307 indirect edges are discovered in the process, add them to NEW_EDGES, unless
308 it is NULL. Return true iff any new callgraph edges were discovered as a
309 result of inlining. */
312 cgraph_mark_inline_edge (struct cgraph_edge *e, bool update_original,
313 VEC (cgraph_edge_p, heap) **new_edges)
315 int old_size = 0, new_size = 0;
316 struct cgraph_node *to = NULL, *what;
317 struct cgraph_edge *curr = e;
320 gcc_assert (e->inline_failed);
321 e->inline_failed = CIF_OK;
322 DECL_POSSIBLY_INLINED (e->callee->decl) = true;
324 cgraph_clone_inlined_nodes (e, true, update_original);
329 /* Now update size of caller and all functions caller is inlined into. */
330 for (;e && !e->inline_failed; e = e->caller->callers)
333 old_size = e->caller->global.size;
334 new_size = cgraph_estimate_size_after_inlining (1, to, what);
335 to->global.size = new_size;
336 to->global.time = cgraph_estimate_time_after_inlining (freq, to, what);
338 gcc_assert (what->global.inlined_to == to);
339 if (new_size > old_size)
340 overall_size += new_size - old_size;
343 /* FIXME: We should remove the optimize check after we ensure we never run
344 IPA passes when not optimizng. */
345 if (flag_indirect_inlining && optimize)
346 return ipa_propagate_indirect_call_infos (curr, new_edges);
351 /* Mark all calls of EDGE->CALLEE inlined into EDGE->CALLER. */
354 cgraph_mark_inline (struct cgraph_edge *edge)
356 struct cgraph_node *to = edge->caller;
357 struct cgraph_node *what = edge->callee;
358 struct cgraph_edge *e, *next;
360 gcc_assert (!edge->call_stmt_cannot_inline_p);
361 /* Look for all calls, mark them inline and clone recursively
362 all inlined functions. */
363 for (e = what->callers; e; e = next)
365 next = e->next_caller;
366 if (e->caller == to && e->inline_failed)
368 cgraph_mark_inline_edge (e, true, NULL);
375 /* Estimate the growth caused by inlining NODE into all callees. */
378 cgraph_estimate_growth (struct cgraph_node *node)
381 struct cgraph_edge *e;
382 bool self_recursive = false;
384 if (node->global.estimated_growth != INT_MIN)
385 return node->global.estimated_growth;
387 for (e = node->callers; e; e = e->next_caller)
389 if (e->caller == node)
390 self_recursive = true;
391 if (e->inline_failed)
392 growth += (cgraph_estimate_size_after_inlining (1, e->caller, node)
393 - e->caller->global.size);
396 /* ??? Wrong for non-trivially self recursive functions or cases where
397 we decide to not inline for different reasons, but it is not big deal
398 as in that case we will keep the body around, but we will also avoid
400 if (cgraph_will_be_removed_from_program_if_no_direct_calls (node)
401 && !DECL_EXTERNAL (node->decl) && !self_recursive)
402 growth -= node->global.size;
404 node->global.estimated_growth = growth;
408 /* Return false when inlining WHAT into TO is not good idea
409 as it would cause too large growth of function bodies.
410 When ONE_ONLY is true, assume that only one call site is going
411 to be inlined, otherwise figure out how many call sites in
412 TO calls WHAT and verify that all can be inlined.
416 cgraph_check_inline_limits (struct cgraph_node *to, struct cgraph_node *what,
417 cgraph_inline_failed_t *reason, bool one_only)
420 struct cgraph_edge *e;
423 HOST_WIDE_INT stack_size_limit, inlined_stack;
428 for (e = to->callees; e; e = e->next_callee)
429 if (e->callee == what)
432 if (to->global.inlined_to)
433 to = to->global.inlined_to;
435 /* When inlining large function body called once into small function,
436 take the inlined function as base for limiting the growth. */
437 if (inline_summary (to)->self_size > inline_summary(what)->self_size)
438 limit = inline_summary (to)->self_size;
440 limit = inline_summary (what)->self_size;
442 limit += limit * PARAM_VALUE (PARAM_LARGE_FUNCTION_GROWTH) / 100;
444 /* Check the size after inlining against the function limits. But allow
445 the function to shrink if it went over the limits by forced inlining. */
446 newsize = cgraph_estimate_size_after_inlining (times, to, what);
447 if (newsize >= to->global.size
448 && newsize > PARAM_VALUE (PARAM_LARGE_FUNCTION_INSNS)
452 *reason = CIF_LARGE_FUNCTION_GROWTH_LIMIT;
456 stack_size_limit = inline_summary (to)->estimated_self_stack_size;
458 stack_size_limit += stack_size_limit * PARAM_VALUE (PARAM_STACK_FRAME_GROWTH) / 100;
460 inlined_stack = (to->global.stack_frame_offset
461 + inline_summary (to)->estimated_self_stack_size
462 + what->global.estimated_stack_size);
463 if (inlined_stack > stack_size_limit
464 && inlined_stack > PARAM_VALUE (PARAM_LARGE_STACK_FRAME))
467 *reason = CIF_LARGE_STACK_FRAME_GROWTH_LIMIT;
473 /* Return true when function N is small enough to be inlined. */
476 cgraph_default_inline_p (struct cgraph_node *n, cgraph_inline_failed_t *reason)
480 if (n->local.disregard_inline_limits)
483 if (!flag_inline_small_functions && !DECL_DECLARED_INLINE_P (decl))
486 *reason = CIF_FUNCTION_NOT_INLINE_CANDIDATE;
492 *reason = CIF_BODY_NOT_AVAILABLE;
495 if (cgraph_function_body_availability (n) <= AVAIL_OVERWRITABLE)
498 *reason = CIF_OVERWRITABLE;
503 if (DECL_DECLARED_INLINE_P (decl))
505 if (n->global.size >= MAX_INLINE_INSNS_SINGLE)
508 *reason = CIF_MAX_INLINE_INSNS_SINGLE_LIMIT;
514 if (n->global.size >= MAX_INLINE_INSNS_AUTO)
517 *reason = CIF_MAX_INLINE_INSNS_AUTO_LIMIT;
525 /* Return true when inlining WHAT would create recursive inlining.
526 We call recursive inlining all cases where same function appears more than
527 once in the single recursion nest path in the inline graph. */
530 cgraph_recursive_inlining_p (struct cgraph_node *to,
531 struct cgraph_node *what,
532 cgraph_inline_failed_t *reason)
535 if (to->global.inlined_to)
536 recursive = what->decl == to->global.inlined_to->decl;
538 recursive = what->decl == to->decl;
539 /* Marking recursive function inline has sane semantic and thus we should
541 if (recursive && reason)
542 *reason = (what->local.disregard_inline_limits
543 ? CIF_RECURSIVE_INLINING : CIF_UNSPECIFIED);
547 /* A cost model driving the inlining heuristics in a way so the edges with
548 smallest badness are inlined first. After each inlining is performed
549 the costs of all caller edges of nodes affected are recomputed so the
550 metrics may accurately depend on values such as number of inlinable callers
551 of the function or function body size. */
554 cgraph_edge_badness (struct cgraph_edge *edge, bool dump)
558 (cgraph_estimate_size_after_inlining (1, edge->caller, edge->callee)
559 - edge->caller->global.size);
561 if (edge->callee->local.disregard_inline_limits)
566 fprintf (dump_file, " Badness calculcation for %s -> %s\n",
567 cgraph_node_name (edge->caller),
568 cgraph_node_name (edge->callee));
569 fprintf (dump_file, " growth %i, time %i-%i, size %i-%i\n",
571 edge->callee->global.time,
572 inline_summary (edge->callee)->time_inlining_benefit,
573 edge->callee->global.size,
574 inline_summary (edge->callee)->size_inlining_benefit);
577 /* Always prefer inlining saving code size. */
580 badness = INT_MIN - growth;
582 fprintf (dump_file, " %i: Growth %i < 0\n", (int) badness,
586 /* When profiling is available, base priorities -(#calls / growth).
587 So we optimize for overall number of "executed" inlined calls. */
592 ((double) edge->count * INT_MIN / max_count / (max_benefit + 1)) *
593 (inline_summary (edge->callee)->time_inlining_benefit + 1)) / growth;
597 " %i (relative %f): profile info. Relative count %f"
598 " * Relative benefit %f\n",
599 (int) badness, (double) badness / INT_MIN,
600 (double) edge->count / max_count,
601 (double) (inline_summary (edge->callee)->
602 time_inlining_benefit + 1) / (max_benefit + 1));
606 /* When function local profile is available, base priorities on
607 growth / frequency, so we optimize for overall frequency of inlined
608 calls. This is not too accurate since while the call might be frequent
609 within function, the function itself is infrequent.
611 Other objective to optimize for is number of different calls inlined.
612 We add the estimated growth after inlining all functions to bias the
613 priorities slightly in this direction (so fewer times called functions
614 of the same size gets priority). */
615 else if (flag_guess_branch_prob)
617 int div = edge->frequency * 100 / CGRAPH_FREQ_BASE + 1;
620 badness = growth * 10000;
622 MIN (100 * inline_summary (edge->callee)->time_inlining_benefit /
623 (edge->callee->global.time + 1) +1, 100);
627 /* Decrease badness if call is nested. */
628 /* Compress the range so we don't overflow. */
630 div = 10000 + ceil_log2 (div) - 8;
635 growth_for_all = cgraph_estimate_growth (edge->callee);
636 badness += growth_for_all;
637 if (badness > INT_MAX)
642 " %i: guessed profile. frequency %i, overall growth %i,"
643 " benefit %i%%, divisor %i\n",
644 (int) badness, edge->frequency, growth_for_all, benefitperc, div);
647 /* When function local profile is not available or it does not give
648 useful information (ie frequency is zero), base the cost on
649 loop nest and overall size growth, so we optimize for overall number
650 of functions fully inlined in program. */
653 int nest = MIN (edge->loop_nest, 8);
654 badness = cgraph_estimate_growth (edge->callee) * 256;
656 /* Decrease badness if call is nested. */
664 fprintf (dump_file, " %i: no profile. nest %i\n", (int) badness,
668 /* Ensure that we did not overflow in all the fixed point math above. */
669 gcc_assert (badness >= INT_MIN);
670 gcc_assert (badness <= INT_MAX - 1);
671 /* Make recursive inlining happen always after other inlining is done. */
672 if (cgraph_recursive_inlining_p (edge->caller, edge->callee, NULL))
678 /* Recompute badness of EDGE and update its key in HEAP if needed. */
680 update_edge_key (fibheap_t heap, struct cgraph_edge *edge)
682 int badness = cgraph_edge_badness (edge, false);
685 fibnode_t n = (fibnode_t) edge->aux;
686 gcc_checking_assert (n->data == edge);
688 /* fibheap_replace_key only decrease the keys.
689 When we increase the key we do not update heap
690 and instead re-insert the element once it becomes
692 if (badness < n->key)
694 fibheap_replace_key (heap, n, badness);
695 gcc_checking_assert (n->key == badness);
699 edge->aux = fibheap_insert (heap, badness, edge);
702 /* Recompute heap nodes for each of caller edge. */
705 update_caller_keys (fibheap_t heap, struct cgraph_node *node,
706 bitmap updated_nodes)
708 struct cgraph_edge *edge;
709 cgraph_inline_failed_t failed_reason;
711 if (!node->local.inlinable
712 || cgraph_function_body_availability (node) <= AVAIL_OVERWRITABLE
713 || node->global.inlined_to)
715 if (!bitmap_set_bit (updated_nodes, node->uid))
717 node->global.estimated_growth = INT_MIN;
719 /* See if there is something to do. */
720 for (edge = node->callers; edge; edge = edge->next_caller)
721 if (edge->inline_failed)
725 /* Prune out edges we won't inline into anymore. */
726 if (!cgraph_default_inline_p (node, &failed_reason))
728 for (; edge; edge = edge->next_caller)
731 fibheap_delete_node (heap, (fibnode_t) edge->aux);
733 if (edge->inline_failed)
734 edge->inline_failed = failed_reason;
739 for (; edge; edge = edge->next_caller)
740 if (edge->inline_failed)
741 update_edge_key (heap, edge);
744 /* Recompute heap nodes for each uninlined call.
745 This is used when we know that edge badnesses are going only to increase
746 (we introduced new call site) and thus all we need is to insert newly
747 created edges into heap. */
750 update_callee_keys (fibheap_t heap, struct cgraph_node *node,
751 bitmap updated_nodes)
753 struct cgraph_edge *e = node->callees;
754 node->global.estimated_growth = INT_MIN;
759 if (!e->inline_failed && e->callee->callees)
760 e = e->callee->callees;
764 && e->callee->local.inlinable
765 && cgraph_function_body_availability (e->callee) >= AVAIL_AVAILABLE
766 && !bitmap_bit_p (updated_nodes, e->callee->uid))
768 node->global.estimated_growth = INT_MIN;
769 /* If function becomes uninlinable, we need to remove it from the heap. */
770 if (!cgraph_default_inline_p (e->callee, &e->inline_failed))
771 update_caller_keys (heap, e->callee, updated_nodes);
773 /* Otherwise update just edge E. */
774 update_edge_key (heap, e);
782 if (e->caller == node)
784 e = e->caller->callers;
786 while (!e->next_callee);
792 /* Recompute heap nodes for each of caller edges of each of callees.
793 Walk recursively into all inline clones. */
796 update_all_callee_keys (fibheap_t heap, struct cgraph_node *node,
797 bitmap updated_nodes)
799 struct cgraph_edge *e = node->callees;
800 node->global.estimated_growth = INT_MIN;
805 if (!e->inline_failed && e->callee->callees)
806 e = e->callee->callees;
809 if (e->inline_failed)
810 update_caller_keys (heap, e->callee, updated_nodes);
817 if (e->caller == node)
819 e = e->caller->callers;
821 while (!e->next_callee);
827 /* Enqueue all recursive calls from NODE into priority queue depending on
828 how likely we want to recursively inline the call. */
831 lookup_recursive_calls (struct cgraph_node *node, struct cgraph_node *where,
835 struct cgraph_edge *e;
836 for (e = where->callees; e; e = e->next_callee)
837 if (e->callee == node)
839 /* When profile feedback is available, prioritize by expected number
840 of calls. Without profile feedback we maintain simple queue
841 to order candidates via recursive depths. */
842 fibheap_insert (heap,
843 !max_count ? priority++
844 : -(e->count / ((max_count + (1<<24) - 1) / (1<<24))),
847 for (e = where->callees; e; e = e->next_callee)
848 if (!e->inline_failed)
849 lookup_recursive_calls (node, e->callee, heap);
852 /* Decide on recursive inlining: in the case function has recursive calls,
853 inline until body size reaches given argument. If any new indirect edges
854 are discovered in the process, add them to *NEW_EDGES, unless NEW_EDGES
858 cgraph_decide_recursive_inlining (struct cgraph_node *node,
859 VEC (cgraph_edge_p, heap) **new_edges)
861 int limit = PARAM_VALUE (PARAM_MAX_INLINE_INSNS_RECURSIVE_AUTO);
862 int max_depth = PARAM_VALUE (PARAM_MAX_INLINE_RECURSIVE_DEPTH_AUTO);
863 int probability = PARAM_VALUE (PARAM_MIN_INLINE_RECURSIVE_PROBABILITY);
865 struct cgraph_edge *e;
866 struct cgraph_node *master_clone, *next;
870 /* It does not make sense to recursively inline always-inline functions
871 as we are going to sorry() on the remaining calls anyway. */
872 if (node->local.disregard_inline_limits
873 && lookup_attribute ("always_inline", DECL_ATTRIBUTES (node->decl)))
876 if (optimize_function_for_size_p (DECL_STRUCT_FUNCTION (node->decl))
877 || (!flag_inline_functions && !DECL_DECLARED_INLINE_P (node->decl)))
880 if (DECL_DECLARED_INLINE_P (node->decl))
882 limit = PARAM_VALUE (PARAM_MAX_INLINE_INSNS_RECURSIVE);
883 max_depth = PARAM_VALUE (PARAM_MAX_INLINE_RECURSIVE_DEPTH);
886 /* Make sure that function is small enough to be considered for inlining. */
888 || cgraph_estimate_size_after_inlining (1, node, node) >= limit)
890 heap = fibheap_new ();
891 lookup_recursive_calls (node, node, heap);
892 if (fibheap_empty (heap))
894 fibheap_delete (heap);
900 " Performing recursive inlining on %s\n",
901 cgraph_node_name (node));
903 /* We need original clone to copy around. */
904 master_clone = cgraph_clone_node (node, node->decl,
905 node->count, CGRAPH_FREQ_BASE, 1,
907 master_clone->needed = true;
908 for (e = master_clone->callees; e; e = e->next_callee)
909 if (!e->inline_failed)
910 cgraph_clone_inlined_nodes (e, true, false);
912 /* Do the inlining and update list of recursive call during process. */
913 while (!fibheap_empty (heap)
914 && (cgraph_estimate_size_after_inlining (1, node, master_clone)
917 struct cgraph_edge *curr
918 = (struct cgraph_edge *) fibheap_extract_min (heap);
919 struct cgraph_node *cnode;
922 for (cnode = curr->caller;
923 cnode->global.inlined_to; cnode = cnode->callers->caller)
924 if (node->decl == curr->callee->decl)
926 if (depth > max_depth)
930 " maximal depth reached\n");
936 if (!cgraph_maybe_hot_edge_p (curr))
939 fprintf (dump_file, " Not inlining cold call\n");
942 if (curr->count * 100 / node->count < probability)
946 " Probability of edge is too small\n");
954 " Inlining call of depth %i", depth);
957 fprintf (dump_file, " called approx. %.2f times per call",
958 (double)curr->count / node->count);
960 fprintf (dump_file, "\n");
962 cgraph_redirect_edge_callee (curr, master_clone);
963 cgraph_mark_inline_edge (curr, false, new_edges);
964 lookup_recursive_calls (node, curr->callee, heap);
967 if (!fibheap_empty (heap) && dump_file)
968 fprintf (dump_file, " Recursive inlining growth limit met.\n");
970 fibheap_delete (heap);
973 "\n Inlined %i times, body grown from size %i to %i, time %i to %i\n", n,
974 master_clone->global.size, node->global.size,
975 master_clone->global.time, node->global.time);
977 /* Remove master clone we used for inlining. We rely that clones inlined
978 into master clone gets queued just before master clone so we don't
980 for (node = cgraph_nodes; node != master_clone;
984 if (node->global.inlined_to == master_clone)
985 cgraph_remove_node (node);
987 cgraph_remove_node (master_clone);
988 /* FIXME: Recursive inlining actually reduces number of calls of the
989 function. At this place we should probably walk the function and
990 inline clones and compensate the counts accordingly. This probably
991 doesn't matter much in practice. */
995 /* Set inline_failed for all callers of given function to REASON. */
998 cgraph_set_inline_failed (struct cgraph_node *node,
999 cgraph_inline_failed_t reason)
1001 struct cgraph_edge *e;
1004 fprintf (dump_file, "Inlining failed: %s\n",
1005 cgraph_inline_failed_string (reason));
1006 for (e = node->callers; e; e = e->next_caller)
1007 if (e->inline_failed)
1008 e->inline_failed = reason;
1011 /* Given whole compilation unit estimate of INSNS, compute how large we can
1012 allow the unit to grow. */
1014 compute_max_insns (int insns)
1016 int max_insns = insns;
1017 if (max_insns < PARAM_VALUE (PARAM_LARGE_UNIT_INSNS))
1018 max_insns = PARAM_VALUE (PARAM_LARGE_UNIT_INSNS);
1020 return ((HOST_WIDEST_INT) max_insns
1021 * (100 + PARAM_VALUE (PARAM_INLINE_UNIT_GROWTH)) / 100);
1024 /* Compute badness of all edges in NEW_EDGES and add them to the HEAP. */
1026 add_new_edges_to_heap (fibheap_t heap, VEC (cgraph_edge_p, heap) *new_edges)
1028 while (VEC_length (cgraph_edge_p, new_edges) > 0)
1030 struct cgraph_edge *edge = VEC_pop (cgraph_edge_p, new_edges);
1032 gcc_assert (!edge->aux);
1033 if (edge->callee->local.inlinable
1034 && cgraph_default_inline_p (edge->callee, &edge->inline_failed))
1035 edge->aux = fibheap_insert (heap, cgraph_edge_badness (edge, false), edge);
1040 /* We use greedy algorithm for inlining of small functions:
1041 All inline candidates are put into prioritized heap based on estimated
1042 growth of the overall number of instructions and then update the estimates.
1044 INLINED and INLINED_CALEES are just pointers to arrays large enough
1045 to be passed to cgraph_inlined_into and cgraph_inlined_callees. */
1048 cgraph_decide_inlining_of_small_functions (void)
1050 struct cgraph_node *node;
1051 struct cgraph_edge *edge;
1052 cgraph_inline_failed_t failed_reason;
1053 fibheap_t heap = fibheap_new ();
1054 bitmap updated_nodes = BITMAP_ALLOC (NULL);
1055 int min_size, max_size;
1056 VEC (cgraph_edge_p, heap) *new_indirect_edges = NULL;
1058 if (flag_indirect_inlining)
1059 new_indirect_edges = VEC_alloc (cgraph_edge_p, heap, 8);
1062 fprintf (dump_file, "\nDeciding on smaller functions:\n");
1064 /* Put all inline candidates into the heap. */
1066 for (node = cgraph_nodes; node; node = node->next)
1068 if (!node->local.inlinable || !node->callers)
1071 fprintf (dump_file, "Considering inline candidate %s.\n", cgraph_node_name (node));
1073 node->global.estimated_growth = INT_MIN;
1074 if (!cgraph_default_inline_p (node, &failed_reason))
1076 cgraph_set_inline_failed (node, failed_reason);
1080 for (edge = node->callers; edge; edge = edge->next_caller)
1081 if (edge->inline_failed)
1083 gcc_assert (!edge->aux);
1084 edge->aux = fibheap_insert (heap, cgraph_edge_badness (edge, false), edge);
1088 max_size = compute_max_insns (overall_size);
1089 min_size = overall_size;
1091 while (overall_size <= max_size
1092 && !fibheap_empty (heap))
1094 int old_size = overall_size;
1095 struct cgraph_node *where, *callee;
1096 int badness = fibheap_min_key (heap);
1097 int current_badness;
1099 cgraph_inline_failed_t not_good = CIF_OK;
1101 edge = (struct cgraph_edge *) fibheap_extract_min (heap);
1102 gcc_assert (edge->aux);
1104 if (!edge->inline_failed)
1107 /* When updating the edge costs, we only decrease badness in the keys.
1108 When the badness increase, we keep the heap as it is and re-insert
1110 current_badness = cgraph_edge_badness (edge, false);
1111 gcc_assert (current_badness >= badness);
1112 if (current_badness != badness)
1114 edge->aux = fibheap_insert (heap, current_badness, edge);
1118 callee = edge->callee;
1120 growth = (cgraph_estimate_size_after_inlining (1, edge->caller, edge->callee)
1121 - edge->caller->global.size);
1126 "\nConsidering %s with %i size\n",
1127 cgraph_node_name (edge->callee),
1128 edge->callee->global.size);
1130 " to be inlined into %s in %s:%i\n"
1131 " Estimated growth after inlined into all callees is %+i insns.\n"
1132 " Estimated badness is %i, frequency %.2f.\n",
1133 cgraph_node_name (edge->caller),
1134 flag_wpa ? "unknown"
1135 : gimple_filename ((const_gimple) edge->call_stmt),
1136 flag_wpa ? -1 : gimple_lineno ((const_gimple) edge->call_stmt),
1137 cgraph_estimate_growth (edge->callee),
1139 edge->frequency / (double)CGRAPH_FREQ_BASE);
1141 fprintf (dump_file," Called "HOST_WIDEST_INT_PRINT_DEC"x\n", edge->count);
1142 if (dump_flags & TDF_DETAILS)
1143 cgraph_edge_badness (edge, true);
1146 /* When not having profile info ready we don't weight by any way the
1147 position of call in procedure itself. This means if call of
1148 function A from function B seems profitable to inline, the recursive
1149 call of function A in inline copy of A in B will look profitable too
1150 and we end up inlining until reaching maximal function growth. This
1151 is not good idea so prohibit the recursive inlining.
1153 ??? When the frequencies are taken into account we might not need this
1156 We need to be cureful here, in some testcases, e.g. directivec.c in
1157 libcpp, we can estimate self recursive function to have negative growth
1158 for inlining completely.
1162 where = edge->caller;
1163 while (where->global.inlined_to)
1165 if (where->decl == edge->callee->decl)
1167 where = where->callers->caller;
1169 if (where->global.inlined_to)
1172 = (edge->callee->local.disregard_inline_limits
1173 ? CIF_RECURSIVE_INLINING : CIF_UNSPECIFIED);
1175 fprintf (dump_file, " inline_failed:Recursive inlining performed only for function itself.\n");
1180 if (edge->callee->local.disregard_inline_limits)
1182 else if (!cgraph_maybe_hot_edge_p (edge))
1183 not_good = CIF_UNLIKELY_CALL;
1184 else if (!flag_inline_functions
1185 && !DECL_DECLARED_INLINE_P (edge->callee->decl))
1186 not_good = CIF_NOT_DECLARED_INLINED;
1187 else if (optimize_function_for_size_p (DECL_STRUCT_FUNCTION(edge->caller->decl)))
1188 not_good = CIF_OPTIMIZING_FOR_SIZE;
1189 if (not_good && growth > 0 && cgraph_estimate_growth (edge->callee) > 0)
1191 if (!cgraph_recursive_inlining_p (edge->caller, edge->callee,
1192 &edge->inline_failed))
1194 edge->inline_failed = not_good;
1196 fprintf (dump_file, " inline_failed:%s.\n",
1197 cgraph_inline_failed_string (edge->inline_failed));
1201 if (!cgraph_default_inline_p (edge->callee, &edge->inline_failed))
1203 if (!cgraph_recursive_inlining_p (edge->caller, edge->callee,
1204 &edge->inline_failed))
1207 fprintf (dump_file, " inline_failed:%s.\n",
1208 cgraph_inline_failed_string (edge->inline_failed));
1212 if (!tree_can_inline_p (edge))
1215 fprintf (dump_file, " inline_failed:%s.\n",
1216 cgraph_inline_failed_string (edge->inline_failed));
1219 if (cgraph_recursive_inlining_p (edge->caller, edge->callee,
1220 &edge->inline_failed))
1222 where = edge->caller;
1223 if (where->global.inlined_to)
1224 where = where->global.inlined_to;
1225 if (!cgraph_decide_recursive_inlining (where,
1226 flag_indirect_inlining
1227 ? &new_indirect_edges : NULL))
1229 if (flag_indirect_inlining)
1230 add_new_edges_to_heap (heap, new_indirect_edges);
1231 update_all_callee_keys (heap, where, updated_nodes);
1235 struct cgraph_node *callee;
1236 if (edge->call_stmt_cannot_inline_p
1237 || !cgraph_check_inline_limits (edge->caller, edge->callee,
1238 &edge->inline_failed, true))
1241 fprintf (dump_file, " Not inlining into %s:%s.\n",
1242 cgraph_node_name (edge->caller),
1243 cgraph_inline_failed_string (edge->inline_failed));
1246 callee = edge->callee;
1247 gcc_checking_assert (!callee->global.inlined_to);
1248 cgraph_mark_inline_edge (edge, true, &new_indirect_edges);
1249 if (flag_indirect_inlining)
1250 add_new_edges_to_heap (heap, new_indirect_edges);
1252 /* We inlined last offline copy to the body. This might lead
1253 to callees of function having fewer call sites and thus they
1254 may need updating. */
1255 if (callee->global.inlined_to)
1256 update_all_callee_keys (heap, callee, updated_nodes);
1258 update_callee_keys (heap, edge->callee, updated_nodes);
1260 where = edge->caller;
1261 if (where->global.inlined_to)
1262 where = where->global.inlined_to;
1264 /* Our profitability metric can depend on local properties
1265 such as number of inlinable calls and size of the function body.
1266 After inlining these properties might change for the function we
1267 inlined into (since it's body size changed) and for the functions
1268 called by function we inlined (since number of it inlinable callers
1270 update_caller_keys (heap, where, updated_nodes);
1272 /* We removed one call of the function we just inlined. If offline
1273 copy is still needed, be sure to update the keys. */
1274 if (callee != where && !callee->global.inlined_to)
1275 update_caller_keys (heap, callee, updated_nodes);
1276 bitmap_clear (updated_nodes);
1281 " Inlined into %s which now has size %i and self time %i,"
1282 "net change of %+i.\n",
1283 cgraph_node_name (edge->caller),
1284 edge->caller->global.time,
1285 edge->caller->global.size,
1286 overall_size - old_size);
1288 if (min_size > overall_size)
1290 min_size = overall_size;
1291 max_size = compute_max_insns (min_size);
1294 fprintf (dump_file, "New minimal size reached: %i\n", min_size);
1297 while (!fibheap_empty (heap))
1299 int badness = fibheap_min_key (heap);
1301 edge = (struct cgraph_edge *) fibheap_extract_min (heap);
1302 gcc_assert (edge->aux);
1304 if (!edge->inline_failed)
1306 #ifdef ENABLE_CHECKING
1307 gcc_assert (cgraph_edge_badness (edge, false) >= badness);
1312 "\nSkipping %s with %i size\n",
1313 cgraph_node_name (edge->callee),
1314 edge->callee->global.size);
1316 " called by %s in %s:%i\n"
1317 " Estimated growth after inlined into all callees is %+i insns.\n"
1318 " Estimated badness is %i, frequency %.2f.\n",
1319 cgraph_node_name (edge->caller),
1320 flag_wpa ? "unknown"
1321 : gimple_filename ((const_gimple) edge->call_stmt),
1322 flag_wpa ? -1 : gimple_lineno ((const_gimple) edge->call_stmt),
1323 cgraph_estimate_growth (edge->callee),
1325 edge->frequency / (double)CGRAPH_FREQ_BASE);
1327 fprintf (dump_file," Called "HOST_WIDEST_INT_PRINT_DEC"x\n", edge->count);
1328 if (dump_flags & TDF_DETAILS)
1329 cgraph_edge_badness (edge, true);
1331 if (!edge->callee->local.disregard_inline_limits && edge->inline_failed
1332 && !cgraph_recursive_inlining_p (edge->caller, edge->callee,
1333 &edge->inline_failed))
1334 edge->inline_failed = CIF_INLINE_UNIT_GROWTH_LIMIT;
1337 if (new_indirect_edges)
1338 VEC_free (cgraph_edge_p, heap, new_indirect_edges);
1339 fibheap_delete (heap);
1340 BITMAP_FREE (updated_nodes);
1343 /* Flatten NODE from the IPA inliner. */
1346 cgraph_flatten (struct cgraph_node *node)
1348 struct cgraph_edge *e;
1350 /* We shouldn't be called recursively when we are being processed. */
1351 gcc_assert (node->aux == NULL);
1353 node->aux = (void *)(size_t) INLINE_ALL;
1355 for (e = node->callees; e; e = e->next_callee)
1357 struct cgraph_node *orig_callee;
1359 if (e->call_stmt_cannot_inline_p)
1362 if (!e->callee->analyzed)
1366 "Not inlining: Function body not available.\n");
1370 /* We've hit cycle? It is time to give up. */
1375 "Not inlining %s into %s to avoid cycle.\n",
1376 cgraph_node_name (e->callee),
1377 cgraph_node_name (e->caller));
1378 e->inline_failed = CIF_RECURSIVE_INLINING;
1382 /* When the edge is already inlined, we just need to recurse into
1383 it in order to fully flatten the leaves. */
1384 if (!e->inline_failed)
1386 cgraph_flatten (e->callee);
1390 if (cgraph_recursive_inlining_p (node, e->callee, &e->inline_failed))
1393 fprintf (dump_file, "Not inlining: recursive call.\n");
1397 if (!tree_can_inline_p (e))
1400 fprintf (dump_file, "Not inlining: %s",
1401 cgraph_inline_failed_string (e->inline_failed));
1405 /* Inline the edge and flatten the inline clone. Avoid
1406 recursing through the original node if the node was cloned. */
1408 fprintf (dump_file, " Inlining %s into %s.\n",
1409 cgraph_node_name (e->callee),
1410 cgraph_node_name (e->caller));
1411 orig_callee = e->callee;
1412 cgraph_mark_inline_edge (e, true, NULL);
1413 if (e->callee != orig_callee)
1414 orig_callee->aux = (void *)(size_t) INLINE_ALL;
1415 cgraph_flatten (e->callee);
1416 if (e->callee != orig_callee)
1417 orig_callee->aux = NULL;
1423 /* Decide on the inlining. We do so in the topological order to avoid
1424 expenses on updating data structures. */
1427 cgraph_decide_inlining (void)
1429 struct cgraph_node *node;
1431 struct cgraph_node **order =
1432 XCNEWVEC (struct cgraph_node *, cgraph_n_nodes);
1435 int initial_size = 0;
1437 cgraph_remove_function_insertion_hook (function_insertion_hook_holder);
1438 if (in_lto_p && flag_indirect_inlining)
1439 ipa_update_after_lto_read ();
1440 if (flag_indirect_inlining)
1441 ipa_create_all_structures_for_iinln ();
1445 for (node = cgraph_nodes; node; node = node->next)
1448 struct cgraph_edge *e;
1450 gcc_assert (inline_summary (node)->self_size == node->global.size);
1451 initial_size += node->global.size;
1452 for (e = node->callees; e; e = e->next_callee)
1453 if (max_count < e->count)
1454 max_count = e->count;
1455 if (max_benefit < inline_summary (node)->time_inlining_benefit)
1456 max_benefit = inline_summary (node)->time_inlining_benefit;
1458 gcc_assert (in_lto_p
1460 || (profile_info && flag_branch_probabilities));
1461 overall_size = initial_size;
1463 nnodes = cgraph_postorder (order);
1467 "\nDeciding on inlining. Starting with size %i.\n",
1470 for (node = cgraph_nodes; node; node = node->next)
1474 fprintf (dump_file, "\nFlattening functions:\n");
1476 /* In the first pass handle functions to be flattened. Do this with
1477 a priority so none of our later choices will make this impossible. */
1478 for (i = nnodes - 1; i >= 0; i--)
1482 /* Handle nodes to be flattened, but don't update overall unit
1483 size. Calling the incremental inliner here is lame,
1484 a simple worklist should be enough. What should be left
1485 here from the early inliner (if it runs) is cyclic cases.
1486 Ideally when processing callees we stop inlining at the
1487 entry of cycles, possibly cloning that entry point and
1488 try to flatten itself turning it into a self-recursive
1490 if (lookup_attribute ("flatten",
1491 DECL_ATTRIBUTES (node->decl)) != NULL)
1495 "Flattening %s\n", cgraph_node_name (node));
1496 cgraph_flatten (node);
1500 cgraph_decide_inlining_of_small_functions ();
1502 if (flag_inline_functions_called_once)
1505 fprintf (dump_file, "\nDeciding on functions called once:\n");
1507 /* And finally decide what functions are called once. */
1508 for (i = nnodes - 1; i >= 0; i--)
1513 && !node->callers->next_caller
1514 && cgraph_will_be_removed_from_program_if_no_direct_calls (node)
1515 && node->local.inlinable
1516 && cgraph_function_body_availability (node) >= AVAIL_AVAILABLE
1517 && node->callers->inline_failed
1518 && node->callers->caller != node
1519 && node->callers->caller->global.inlined_to != node
1520 && !node->callers->call_stmt_cannot_inline_p
1521 && !DECL_EXTERNAL (node->decl))
1523 cgraph_inline_failed_t reason;
1524 old_size = overall_size;
1528 "\nConsidering %s size %i.\n",
1529 cgraph_node_name (node), node->global.size);
1531 " Called once from %s %i insns.\n",
1532 cgraph_node_name (node->callers->caller),
1533 node->callers->caller->global.size);
1536 if (cgraph_check_inline_limits (node->callers->caller, node,
1539 struct cgraph_node *caller = node->callers->caller;
1540 cgraph_mark_inline (node->callers);
1543 " Inlined into %s which now has %i size"
1544 " for a net change of %+i size.\n",
1545 cgraph_node_name (caller),
1546 caller->global.size,
1547 overall_size - old_size);
1553 " Not inlining: %s.\n",
1554 cgraph_inline_failed_string (reason));
1560 /* Free ipa-prop structures if they are no longer needed. */
1561 if (flag_indirect_inlining)
1562 ipa_free_all_structures_after_iinln ();
1566 "\nInlined %i calls, eliminated %i functions, "
1567 "size %i turned to %i size.\n\n",
1568 ncalls_inlined, nfunctions_inlined, initial_size,
1574 /* Return true when N is leaf function. Accept cheap (pure&const) builtins
1575 in leaf functions. */
1577 leaf_node_p (struct cgraph_node *n)
1579 struct cgraph_edge *e;
1580 for (e = n->callees; e; e = e->next_callee)
1581 if (!DECL_BUILT_IN (e->callee->decl)
1582 || (!TREE_READONLY (e->callee->decl)
1583 || DECL_PURE_P (e->callee->decl)))
1588 /* Decide on the inlining. We do so in the topological order to avoid
1589 expenses on updating data structures. */
1592 cgraph_decide_inlining_incrementally (struct cgraph_node *node,
1593 enum inlining_mode mode)
1595 struct cgraph_edge *e;
1596 bool inlined = false;
1597 cgraph_inline_failed_t failed_reason;
1599 #ifdef ENABLE_CHECKING
1600 verify_cgraph_node (node);
1603 if (mode != INLINE_ALWAYS_INLINE && mode != INLINE_SIZE_NORECURSIVE
1604 && lookup_attribute ("flatten", DECL_ATTRIBUTES (node->decl)) != NULL)
1607 fprintf (dump_file, "Incrementally flattening %s\n",
1608 cgraph_node_name (node));
1612 /* First of all look for always inline functions. */
1613 if (mode != INLINE_SIZE_NORECURSIVE)
1614 for (e = node->callees; e; e = e->next_callee)
1616 if (!e->callee->local.disregard_inline_limits
1617 && (mode != INLINE_ALL || !e->callee->local.inlinable))
1619 if (e->call_stmt_cannot_inline_p)
1623 "Considering to always inline inline candidate %s.\n",
1624 cgraph_node_name (e->callee));
1625 if (cgraph_recursive_inlining_p (node, e->callee, &e->inline_failed))
1628 fprintf (dump_file, "Not inlining: recursive call.\n");
1631 if (!tree_can_inline_p (e))
1636 cgraph_inline_failed_string (e->inline_failed));
1639 if (gimple_in_ssa_p (DECL_STRUCT_FUNCTION (node->decl))
1640 != gimple_in_ssa_p (DECL_STRUCT_FUNCTION (e->callee->decl)))
1643 fprintf (dump_file, "Not inlining: SSA form does not match.\n");
1646 if (!e->callee->analyzed)
1650 "Not inlining: Function body no longer available.\n");
1655 fprintf (dump_file, " Inlining %s into %s.\n",
1656 cgraph_node_name (e->callee),
1657 cgraph_node_name (e->caller));
1658 cgraph_mark_inline (e);
1662 /* Now do the automatic inlining. */
1663 if (mode != INLINE_ALL && mode != INLINE_ALWAYS_INLINE
1664 /* Never inline regular functions into always-inline functions
1665 during incremental inlining. */
1666 && !node->local.disregard_inline_limits)
1668 bitmap visited = BITMAP_ALLOC (NULL);
1669 for (e = node->callees; e; e = e->next_callee)
1671 int allowed_growth = 0;
1672 if (!e->callee->local.inlinable
1673 || !e->inline_failed
1674 || e->callee->local.disregard_inline_limits)
1676 /* We are inlining a function to all call-sites in node
1677 or to none. So visit each candidate only once. */
1678 if (!bitmap_set_bit (visited, e->callee->uid))
1681 fprintf (dump_file, "Considering inline candidate %s.\n",
1682 cgraph_node_name (e->callee));
1683 if (cgraph_recursive_inlining_p (node, e->callee, &e->inline_failed))
1686 fprintf (dump_file, "Not inlining: recursive call.\n");
1689 if (gimple_in_ssa_p (DECL_STRUCT_FUNCTION (node->decl))
1690 != gimple_in_ssa_p (DECL_STRUCT_FUNCTION (e->callee->decl)))
1694 "Not inlining: SSA form does not match.\n");
1698 if (cgraph_maybe_hot_edge_p (e) && leaf_node_p (e->callee)
1699 && optimize_function_for_speed_p (cfun))
1700 allowed_growth = PARAM_VALUE (PARAM_EARLY_INLINING_INSNS);
1702 /* When the function body would grow and inlining the function
1703 won't eliminate the need for offline copy of the function,
1705 if (((mode == INLINE_SIZE || mode == INLINE_SIZE_NORECURSIVE)
1706 || (!flag_inline_functions
1707 && !DECL_DECLARED_INLINE_P (e->callee->decl)))
1708 && (cgraph_estimate_size_after_inlining (1, e->caller, e->callee)
1709 > e->caller->global.size + allowed_growth)
1710 && cgraph_estimate_growth (e->callee) > allowed_growth)
1714 "Not inlining: code size would grow by %i.\n",
1715 cgraph_estimate_size_after_inlining (1, e->caller,
1717 - e->caller->global.size);
1720 if (!cgraph_check_inline_limits (node, e->callee, &e->inline_failed,
1722 || e->call_stmt_cannot_inline_p)
1725 fprintf (dump_file, "Not inlining: %s.\n",
1726 cgraph_inline_failed_string (e->inline_failed));
1729 if (!e->callee->analyzed)
1733 "Not inlining: Function body no longer available.\n");
1736 if (!tree_can_inline_p (e))
1740 "Not inlining: %s.",
1741 cgraph_inline_failed_string (e->inline_failed));
1744 if (cgraph_default_inline_p (e->callee, &failed_reason))
1747 fprintf (dump_file, " Inlining %s into %s.\n",
1748 cgraph_node_name (e->callee),
1749 cgraph_node_name (e->caller));
1750 cgraph_mark_inline (e);
1754 BITMAP_FREE (visited);
1759 /* Because inlining might remove no-longer reachable nodes, we need to
1760 keep the array visible to garbage collector to avoid reading collected
1763 static GTY ((length ("nnodes"))) struct cgraph_node **order;
1765 /* Do inlining of small functions. Doing so early helps profiling and other
1766 passes to be somewhat more effective and avoids some code duplication in
1767 later real inlining pass for testcases with very many function calls. */
1769 cgraph_early_inlining (void)
1771 struct cgraph_node *node = cgraph_node (current_function_decl);
1772 unsigned int todo = 0;
1780 || !flag_early_inlining)
1782 /* When not optimizing or not inlining inline only always-inline
1784 cgraph_decide_inlining_incrementally (node, INLINE_ALWAYS_INLINE);
1785 timevar_push (TV_INTEGRATION);
1786 todo |= optimize_inline_calls (current_function_decl);
1787 timevar_pop (TV_INTEGRATION);
1791 if (lookup_attribute ("flatten",
1792 DECL_ATTRIBUTES (node->decl)) != NULL)
1796 "Flattening %s\n", cgraph_node_name (node));
1797 cgraph_flatten (node);
1798 timevar_push (TV_INTEGRATION);
1799 todo |= optimize_inline_calls (current_function_decl);
1800 timevar_pop (TV_INTEGRATION);
1802 /* We iterate incremental inlining to get trivial cases of indirect
1804 while (iterations < PARAM_VALUE (PARAM_EARLY_INLINER_MAX_ITERATIONS)
1805 && cgraph_decide_inlining_incrementally (node,
1807 ? INLINE_SIZE_NORECURSIVE
1810 timevar_push (TV_INTEGRATION);
1811 todo |= optimize_inline_calls (current_function_decl);
1813 timevar_pop (TV_INTEGRATION);
1816 fprintf (dump_file, "Iterations: %i\n", iterations);
1819 cfun->always_inline_functions_inlined = true;
1824 struct gimple_opt_pass pass_early_inline =
1828 "einline", /* name */
1830 cgraph_early_inlining, /* execute */
1833 0, /* static_pass_number */
1834 TV_INLINE_HEURISTICS, /* tv_id */
1835 0, /* properties_required */
1836 0, /* properties_provided */
1837 0, /* properties_destroyed */
1838 0, /* todo_flags_start */
1839 TODO_dump_func /* todo_flags_finish */
1843 /* When inlining shall be performed. */
1845 cgraph_gate_ipa_early_inlining (void)
1847 return (flag_early_inlining
1849 && (flag_branch_probabilities || flag_test_coverage
1850 || profile_arc_flag));
1853 /* IPA pass wrapper for early inlining pass. We need to run early inlining
1854 before tree profiling so we have stand alone IPA pass for doing so. */
1855 struct simple_ipa_opt_pass pass_ipa_early_inline =
1859 "einline_ipa", /* name */
1860 cgraph_gate_ipa_early_inlining, /* gate */
1864 0, /* static_pass_number */
1865 TV_INLINE_HEURISTICS, /* tv_id */
1866 0, /* properties_required */
1867 0, /* properties_provided */
1868 0, /* properties_destroyed */
1869 0, /* todo_flags_start */
1870 TODO_dump_cgraph /* todo_flags_finish */
1874 /* See if statement might disappear after inlining. We are not terribly
1875 sophisficated, basically looking for simple abstraction penalty wrappers. */
1878 likely_eliminated_by_inlining_p (gimple stmt)
1880 enum gimple_code code = gimple_code (stmt);
1886 if (gimple_num_ops (stmt) != 2)
1889 /* Casts of parameters, loads from parameters passed by reference
1890 and stores to return value or parameters are probably free after
1892 if (gimple_assign_rhs_code (stmt) == CONVERT_EXPR
1893 || gimple_assign_rhs_code (stmt) == NOP_EXPR
1894 || gimple_assign_rhs_code (stmt) == VIEW_CONVERT_EXPR
1895 || gimple_assign_rhs_class (stmt) == GIMPLE_SINGLE_RHS)
1897 tree rhs = gimple_assign_rhs1 (stmt);
1898 tree lhs = gimple_assign_lhs (stmt);
1899 tree inner_rhs = rhs;
1900 tree inner_lhs = lhs;
1901 bool rhs_free = false;
1902 bool lhs_free = false;
1904 while (handled_component_p (inner_lhs)
1905 || TREE_CODE (inner_lhs) == MEM_REF)
1906 inner_lhs = TREE_OPERAND (inner_lhs, 0);
1907 while (handled_component_p (inner_rhs)
1908 || TREE_CODE (inner_rhs) == ADDR_EXPR
1909 || TREE_CODE (inner_rhs) == MEM_REF)
1910 inner_rhs = TREE_OPERAND (inner_rhs, 0);
1913 if (TREE_CODE (inner_rhs) == PARM_DECL
1914 || (TREE_CODE (inner_rhs) == SSA_NAME
1915 && SSA_NAME_IS_DEFAULT_DEF (inner_rhs)
1916 && TREE_CODE (SSA_NAME_VAR (inner_rhs)) == PARM_DECL))
1918 if (rhs_free && is_gimple_reg (lhs))
1920 if (((TREE_CODE (inner_lhs) == PARM_DECL
1921 || (TREE_CODE (inner_lhs) == SSA_NAME
1922 && SSA_NAME_IS_DEFAULT_DEF (inner_lhs)
1923 && TREE_CODE (SSA_NAME_VAR (inner_lhs)) == PARM_DECL))
1924 && inner_lhs != lhs)
1925 || TREE_CODE (inner_lhs) == RESULT_DECL
1926 || (TREE_CODE (inner_lhs) == SSA_NAME
1927 && TREE_CODE (SSA_NAME_VAR (inner_lhs)) == RESULT_DECL))
1930 && (is_gimple_reg (rhs) || is_gimple_min_invariant (rhs)))
1932 if (lhs_free && rhs_free)
1941 /* Compute function body size parameters for NODE. */
1944 estimate_function_body_sizes (struct cgraph_node *node)
1947 gcov_type time_inlining_benefit = 0;
1949 int size_inlining_benefit = 0;
1951 gimple_stmt_iterator bsi;
1952 struct function *my_function = DECL_STRUCT_FUNCTION (node->decl);
1955 tree funtype = TREE_TYPE (node->decl);
1958 fprintf (dump_file, "Analyzing function body size: %s\n",
1959 cgraph_node_name (node));
1961 gcc_assert (my_function && my_function->cfg);
1962 FOR_EACH_BB_FN (bb, my_function)
1964 freq = compute_call_stmt_bb_frequency (node->decl, bb);
1965 for (bsi = gsi_start_bb (bb); !gsi_end_p (bsi); gsi_next (&bsi))
1967 gimple stmt = gsi_stmt (bsi);
1968 int this_size = estimate_num_insns (stmt, &eni_size_weights);
1969 int this_time = estimate_num_insns (stmt, &eni_time_weights);
1971 if (dump_file && (dump_flags & TDF_DETAILS))
1973 fprintf (dump_file, " freq:%6i size:%3i time:%3i ",
1974 freq, this_size, this_time);
1975 print_gimple_stmt (dump_file, stmt, 0, 0);
1980 if (likely_eliminated_by_inlining_p (stmt))
1982 size_inlining_benefit += this_size;
1983 time_inlining_benefit += this_time;
1984 if (dump_file && (dump_flags & TDF_DETAILS))
1985 fprintf (dump_file, " Likely eliminated\n");
1987 gcc_assert (time >= 0);
1988 gcc_assert (size >= 0);
1991 time = (time + CGRAPH_FREQ_BASE / 2) / CGRAPH_FREQ_BASE;
1992 time_inlining_benefit = ((time_inlining_benefit + CGRAPH_FREQ_BASE / 2)
1993 / CGRAPH_FREQ_BASE);
1995 fprintf (dump_file, "Overall function body time: %i-%i size: %i-%i\n",
1996 (int)time, (int)time_inlining_benefit,
1997 size, size_inlining_benefit);
1998 time_inlining_benefit += eni_time_weights.call_cost;
1999 size_inlining_benefit += eni_size_weights.call_cost;
2000 if (!VOID_TYPE_P (TREE_TYPE (funtype)))
2002 int cost = estimate_move_cost (TREE_TYPE (funtype));
2003 time_inlining_benefit += cost;
2004 size_inlining_benefit += cost;
2006 for (arg = DECL_ARGUMENTS (node->decl); arg; arg = DECL_CHAIN (arg))
2007 if (!VOID_TYPE_P (TREE_TYPE (arg)))
2009 int cost = estimate_move_cost (TREE_TYPE (arg));
2010 time_inlining_benefit += cost;
2011 size_inlining_benefit += cost;
2013 if (time_inlining_benefit > MAX_TIME)
2014 time_inlining_benefit = MAX_TIME;
2015 if (time > MAX_TIME)
2017 inline_summary (node)->self_time = time;
2018 inline_summary (node)->self_size = size;
2020 fprintf (dump_file, "With function call overhead time: %i-%i size: %i-%i\n",
2021 (int)time, (int)time_inlining_benefit,
2022 size, size_inlining_benefit);
2023 inline_summary (node)->time_inlining_benefit = time_inlining_benefit;
2024 inline_summary (node)->size_inlining_benefit = size_inlining_benefit;
2027 /* Compute parameters of functions used by inliner. */
2029 compute_inline_parameters (struct cgraph_node *node)
2031 HOST_WIDE_INT self_stack_size;
2033 gcc_assert (!node->global.inlined_to);
2035 /* Estimate the stack size for the function. But not at -O0
2036 because estimated_stack_frame_size is a quadratic problem. */
2037 self_stack_size = optimize ? estimated_stack_frame_size (node->decl) : 0;
2038 inline_summary (node)->estimated_self_stack_size = self_stack_size;
2039 node->global.estimated_stack_size = self_stack_size;
2040 node->global.stack_frame_offset = 0;
2042 /* Can this function be inlined at all? */
2043 node->local.inlinable = tree_inlinable_function_p (node->decl);
2044 if (node->local.inlinable && !node->local.disregard_inline_limits)
2045 node->local.disregard_inline_limits
2046 = DECL_DISREGARD_INLINE_LIMITS (node->decl);
2047 estimate_function_body_sizes (node);
2048 /* Inlining characteristics are maintained by the cgraph_mark_inline. */
2049 node->global.time = inline_summary (node)->self_time;
2050 node->global.size = inline_summary (node)->self_size;
2055 /* Compute parameters of functions used by inliner using
2056 current_function_decl. */
2058 compute_inline_parameters_for_current (void)
2060 compute_inline_parameters (cgraph_node (current_function_decl));
2064 struct gimple_opt_pass pass_inline_parameters =
2068 "inline_param", /* name */
2070 compute_inline_parameters_for_current,/* execute */
2073 0, /* static_pass_number */
2074 TV_INLINE_HEURISTICS, /* tv_id */
2075 0, /* properties_required */
2076 0, /* properties_provided */
2077 0, /* properties_destroyed */
2078 0, /* todo_flags_start */
2079 0 /* todo_flags_finish */
2083 /* This function performs intraprocedural analyzis in NODE that is required to
2084 inline indirect calls. */
2086 inline_indirect_intraprocedural_analysis (struct cgraph_node *node)
2088 ipa_analyze_node (node);
2089 if (dump_file && (dump_flags & TDF_DETAILS))
2091 ipa_print_node_params (dump_file, node);
2092 ipa_print_node_jump_functions (dump_file, node);
2096 /* Note function body size. */
2098 analyze_function (struct cgraph_node *node)
2100 push_cfun (DECL_STRUCT_FUNCTION (node->decl));
2101 current_function_decl = node->decl;
2103 compute_inline_parameters (node);
2104 /* FIXME: We should remove the optimize check after we ensure we never run
2105 IPA passes when not optimizng. */
2106 if (flag_indirect_inlining && optimize)
2107 inline_indirect_intraprocedural_analysis (node);
2109 current_function_decl = NULL;
2113 /* Called when new function is inserted to callgraph late. */
2115 add_new_function (struct cgraph_node *node, void *data ATTRIBUTE_UNUSED)
2117 analyze_function (node);
2120 /* Note function body size. */
2122 inline_generate_summary (void)
2124 struct cgraph_node *node;
2126 function_insertion_hook_holder =
2127 cgraph_add_function_insertion_hook (&add_new_function, NULL);
2129 if (flag_indirect_inlining)
2131 ipa_register_cgraph_hooks ();
2132 ipa_check_create_node_params ();
2133 ipa_check_create_edge_args ();
2136 for (node = cgraph_nodes; node; node = node->next)
2138 analyze_function (node);
2143 /* Apply inline plan to function. */
2145 inline_transform (struct cgraph_node *node)
2147 unsigned int todo = 0;
2148 struct cgraph_edge *e;
2149 bool inline_p = false;
2151 /* FIXME: Currently the passmanager is adding inline transform more than once to some
2152 clones. This needs revisiting after WPA cleanups. */
2153 if (cfun->after_inlining)
2156 /* We might need the body of this function so that we can expand
2157 it inline somewhere else. */
2158 if (cgraph_preserve_function_body_p (node->decl))
2159 save_inline_function_body (node);
2161 for (e = node->callees; e; e = e->next_callee)
2163 cgraph_redirect_edge_call_stmt_to_callee (e);
2164 if (!e->inline_failed || warn_inline)
2170 timevar_push (TV_INTEGRATION);
2171 todo = optimize_inline_calls (current_function_decl);
2172 timevar_pop (TV_INTEGRATION);
2174 cfun->always_inline_functions_inlined = true;
2175 cfun->after_inlining = true;
2176 return todo | execute_fixup_cfg ();
2179 /* Read inline summary. Jump functions are shared among ipa-cp
2180 and inliner, so when ipa-cp is active, we don't need to write them
2184 inline_read_summary (void)
2186 if (flag_indirect_inlining)
2188 ipa_register_cgraph_hooks ();
2190 ipa_prop_read_jump_functions ();
2192 function_insertion_hook_holder =
2193 cgraph_add_function_insertion_hook (&add_new_function, NULL);
2196 /* Write inline summary for node in SET.
2197 Jump functions are shared among ipa-cp and inliner, so when ipa-cp is
2198 active, we don't need to write them twice. */
2201 inline_write_summary (cgraph_node_set set,
2202 varpool_node_set vset ATTRIBUTE_UNUSED)
2204 if (flag_indirect_inlining && !flag_ipa_cp)
2205 ipa_prop_write_jump_functions (set);
2208 /* When to run IPA inlining. Inlining of always-inline functions
2209 happens during early inlining. */
2212 gate_cgraph_decide_inlining (void)
2214 /* ??? We'd like to skip this if not optimizing or not inlining as
2215 all always-inline functions have been processed by early
2216 inlining already. But this at least breaks EH with C++ as
2217 we need to unconditionally run fixup_cfg even at -O0.
2218 So leave it on unconditionally for now. */
2222 struct ipa_opt_pass_d pass_ipa_inline =
2226 "inline", /* name */
2227 gate_cgraph_decide_inlining, /* gate */
2228 cgraph_decide_inlining, /* execute */
2231 0, /* static_pass_number */
2232 TV_INLINE_HEURISTICS, /* tv_id */
2233 0, /* properties_required */
2234 0, /* properties_provided */
2235 0, /* properties_destroyed */
2236 TODO_remove_functions, /* todo_flags_finish */
2237 TODO_dump_cgraph | TODO_dump_func
2238 | TODO_remove_functions | TODO_ggc_collect /* todo_flags_finish */
2240 inline_generate_summary, /* generate_summary */
2241 inline_write_summary, /* write_summary */
2242 inline_read_summary, /* read_summary */
2243 NULL, /* write_optimization_summary */
2244 NULL, /* read_optimization_summary */
2245 NULL, /* stmt_fixup */
2247 inline_transform, /* function_transform */
2248 NULL, /* variable_transform */
2252 #include "gt-ipa-inline.h"