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 && edge->inline_failed
1035 && cgraph_default_inline_p (edge->callee, &edge->inline_failed))
1036 edge->aux = fibheap_insert (heap, cgraph_edge_badness (edge, false), edge);
1041 /* We use greedy algorithm for inlining of small functions:
1042 All inline candidates are put into prioritized heap based on estimated
1043 growth of the overall number of instructions and then update the estimates.
1045 INLINED and INLINED_CALEES are just pointers to arrays large enough
1046 to be passed to cgraph_inlined_into and cgraph_inlined_callees. */
1049 cgraph_decide_inlining_of_small_functions (void)
1051 struct cgraph_node *node;
1052 struct cgraph_edge *edge;
1053 cgraph_inline_failed_t failed_reason;
1054 fibheap_t heap = fibheap_new ();
1055 bitmap updated_nodes = BITMAP_ALLOC (NULL);
1056 int min_size, max_size;
1057 VEC (cgraph_edge_p, heap) *new_indirect_edges = NULL;
1059 if (flag_indirect_inlining)
1060 new_indirect_edges = VEC_alloc (cgraph_edge_p, heap, 8);
1063 fprintf (dump_file, "\nDeciding on smaller functions:\n");
1065 /* Put all inline candidates into the heap. */
1067 for (node = cgraph_nodes; node; node = node->next)
1069 if (!node->local.inlinable || !node->callers)
1072 fprintf (dump_file, "Considering inline candidate %s.\n", cgraph_node_name (node));
1074 node->global.estimated_growth = INT_MIN;
1075 if (!cgraph_default_inline_p (node, &failed_reason))
1077 cgraph_set_inline_failed (node, failed_reason);
1081 for (edge = node->callers; edge; edge = edge->next_caller)
1082 if (edge->inline_failed)
1084 gcc_assert (!edge->aux);
1085 edge->aux = fibheap_insert (heap, cgraph_edge_badness (edge, false), edge);
1089 max_size = compute_max_insns (overall_size);
1090 min_size = overall_size;
1092 while (overall_size <= max_size
1093 && !fibheap_empty (heap))
1095 int old_size = overall_size;
1096 struct cgraph_node *where, *callee;
1097 int badness = fibheap_min_key (heap);
1098 int current_badness;
1100 cgraph_inline_failed_t not_good = CIF_OK;
1102 edge = (struct cgraph_edge *) fibheap_extract_min (heap);
1103 gcc_assert (edge->aux);
1105 if (!edge->inline_failed)
1108 /* When updating the edge costs, we only decrease badness in the keys.
1109 When the badness increase, we keep the heap as it is and re-insert
1111 current_badness = cgraph_edge_badness (edge, false);
1112 gcc_assert (current_badness >= badness);
1113 if (current_badness != badness)
1115 edge->aux = fibheap_insert (heap, current_badness, edge);
1119 callee = edge->callee;
1121 growth = (cgraph_estimate_size_after_inlining (1, edge->caller, edge->callee)
1122 - edge->caller->global.size);
1127 "\nConsidering %s with %i size\n",
1128 cgraph_node_name (edge->callee),
1129 edge->callee->global.size);
1131 " to be inlined into %s in %s:%i\n"
1132 " Estimated growth after inlined into all callees is %+i insns.\n"
1133 " Estimated badness is %i, frequency %.2f.\n",
1134 cgraph_node_name (edge->caller),
1135 flag_wpa ? "unknown"
1136 : gimple_filename ((const_gimple) edge->call_stmt),
1137 flag_wpa ? -1 : gimple_lineno ((const_gimple) edge->call_stmt),
1138 cgraph_estimate_growth (edge->callee),
1140 edge->frequency / (double)CGRAPH_FREQ_BASE);
1142 fprintf (dump_file," Called "HOST_WIDEST_INT_PRINT_DEC"x\n", edge->count);
1143 if (dump_flags & TDF_DETAILS)
1144 cgraph_edge_badness (edge, true);
1147 /* When not having profile info ready we don't weight by any way the
1148 position of call in procedure itself. This means if call of
1149 function A from function B seems profitable to inline, the recursive
1150 call of function A in inline copy of A in B will look profitable too
1151 and we end up inlining until reaching maximal function growth. This
1152 is not good idea so prohibit the recursive inlining.
1154 ??? When the frequencies are taken into account we might not need this
1157 We need to be cureful here, in some testcases, e.g. directivec.c in
1158 libcpp, we can estimate self recursive function to have negative growth
1159 for inlining completely.
1163 where = edge->caller;
1164 while (where->global.inlined_to)
1166 if (where->decl == edge->callee->decl)
1168 where = where->callers->caller;
1170 if (where->global.inlined_to)
1173 = (edge->callee->local.disregard_inline_limits
1174 ? CIF_RECURSIVE_INLINING : CIF_UNSPECIFIED);
1176 fprintf (dump_file, " inline_failed:Recursive inlining performed only for function itself.\n");
1181 if (edge->callee->local.disregard_inline_limits)
1183 else if (!cgraph_maybe_hot_edge_p (edge))
1184 not_good = CIF_UNLIKELY_CALL;
1185 else if (!flag_inline_functions
1186 && !DECL_DECLARED_INLINE_P (edge->callee->decl))
1187 not_good = CIF_NOT_DECLARED_INLINED;
1188 else if (optimize_function_for_size_p (DECL_STRUCT_FUNCTION(edge->caller->decl)))
1189 not_good = CIF_OPTIMIZING_FOR_SIZE;
1190 if (not_good && growth > 0 && cgraph_estimate_growth (edge->callee) > 0)
1192 if (!cgraph_recursive_inlining_p (edge->caller, edge->callee,
1193 &edge->inline_failed))
1195 edge->inline_failed = not_good;
1197 fprintf (dump_file, " inline_failed:%s.\n",
1198 cgraph_inline_failed_string (edge->inline_failed));
1202 if (!cgraph_default_inline_p (edge->callee, &edge->inline_failed))
1204 if (!cgraph_recursive_inlining_p (edge->caller, edge->callee,
1205 &edge->inline_failed))
1208 fprintf (dump_file, " inline_failed:%s.\n",
1209 cgraph_inline_failed_string (edge->inline_failed));
1213 if (!tree_can_inline_p (edge))
1216 fprintf (dump_file, " inline_failed:%s.\n",
1217 cgraph_inline_failed_string (edge->inline_failed));
1220 if (cgraph_recursive_inlining_p (edge->caller, edge->callee,
1221 &edge->inline_failed))
1223 where = edge->caller;
1224 if (where->global.inlined_to)
1225 where = where->global.inlined_to;
1226 if (!cgraph_decide_recursive_inlining (where,
1227 flag_indirect_inlining
1228 ? &new_indirect_edges : NULL))
1230 if (flag_indirect_inlining)
1231 add_new_edges_to_heap (heap, new_indirect_edges);
1232 update_all_callee_keys (heap, where, updated_nodes);
1236 struct cgraph_node *callee;
1237 if (edge->call_stmt_cannot_inline_p
1238 || !cgraph_check_inline_limits (edge->caller, edge->callee,
1239 &edge->inline_failed, true))
1242 fprintf (dump_file, " Not inlining into %s:%s.\n",
1243 cgraph_node_name (edge->caller),
1244 cgraph_inline_failed_string (edge->inline_failed));
1247 callee = edge->callee;
1248 gcc_checking_assert (!callee->global.inlined_to);
1249 cgraph_mark_inline_edge (edge, true, &new_indirect_edges);
1250 if (flag_indirect_inlining)
1251 add_new_edges_to_heap (heap, new_indirect_edges);
1253 /* We inlined last offline copy to the body. This might lead
1254 to callees of function having fewer call sites and thus they
1255 may need updating. */
1256 if (callee->global.inlined_to)
1257 update_all_callee_keys (heap, callee, updated_nodes);
1259 update_callee_keys (heap, edge->callee, updated_nodes);
1261 where = edge->caller;
1262 if (where->global.inlined_to)
1263 where = where->global.inlined_to;
1265 /* Our profitability metric can depend on local properties
1266 such as number of inlinable calls and size of the function body.
1267 After inlining these properties might change for the function we
1268 inlined into (since it's body size changed) and for the functions
1269 called by function we inlined (since number of it inlinable callers
1271 update_caller_keys (heap, where, updated_nodes);
1273 /* We removed one call of the function we just inlined. If offline
1274 copy is still needed, be sure to update the keys. */
1275 if (callee != where && !callee->global.inlined_to)
1276 update_caller_keys (heap, callee, updated_nodes);
1277 bitmap_clear (updated_nodes);
1282 " Inlined into %s which now has size %i and self time %i,"
1283 "net change of %+i.\n",
1284 cgraph_node_name (edge->caller),
1285 edge->caller->global.time,
1286 edge->caller->global.size,
1287 overall_size - old_size);
1289 if (min_size > overall_size)
1291 min_size = overall_size;
1292 max_size = compute_max_insns (min_size);
1295 fprintf (dump_file, "New minimal size reached: %i\n", min_size);
1298 while (!fibheap_empty (heap))
1300 int badness = fibheap_min_key (heap);
1302 edge = (struct cgraph_edge *) fibheap_extract_min (heap);
1303 gcc_assert (edge->aux);
1305 if (!edge->inline_failed)
1307 #ifdef ENABLE_CHECKING
1308 gcc_assert (cgraph_edge_badness (edge, false) >= badness);
1313 "\nSkipping %s with %i size\n",
1314 cgraph_node_name (edge->callee),
1315 edge->callee->global.size);
1317 " called by %s in %s:%i\n"
1318 " Estimated growth after inlined into all callees is %+i insns.\n"
1319 " Estimated badness is %i, frequency %.2f.\n",
1320 cgraph_node_name (edge->caller),
1321 flag_wpa ? "unknown"
1322 : gimple_filename ((const_gimple) edge->call_stmt),
1323 flag_wpa ? -1 : gimple_lineno ((const_gimple) edge->call_stmt),
1324 cgraph_estimate_growth (edge->callee),
1326 edge->frequency / (double)CGRAPH_FREQ_BASE);
1328 fprintf (dump_file," Called "HOST_WIDEST_INT_PRINT_DEC"x\n", edge->count);
1329 if (dump_flags & TDF_DETAILS)
1330 cgraph_edge_badness (edge, true);
1332 if (!edge->callee->local.disregard_inline_limits && edge->inline_failed
1333 && !cgraph_recursive_inlining_p (edge->caller, edge->callee,
1334 &edge->inline_failed))
1335 edge->inline_failed = CIF_INLINE_UNIT_GROWTH_LIMIT;
1338 if (new_indirect_edges)
1339 VEC_free (cgraph_edge_p, heap, new_indirect_edges);
1340 fibheap_delete (heap);
1341 BITMAP_FREE (updated_nodes);
1344 /* Flatten NODE from the IPA inliner. */
1347 cgraph_flatten (struct cgraph_node *node)
1349 struct cgraph_edge *e;
1351 /* We shouldn't be called recursively when we are being processed. */
1352 gcc_assert (node->aux == NULL);
1354 node->aux = (void *)(size_t) INLINE_ALL;
1356 for (e = node->callees; e; e = e->next_callee)
1358 struct cgraph_node *orig_callee;
1360 if (e->call_stmt_cannot_inline_p)
1363 if (!e->callee->analyzed)
1367 "Not inlining: Function body not available.\n");
1371 /* We've hit cycle? It is time to give up. */
1376 "Not inlining %s into %s to avoid cycle.\n",
1377 cgraph_node_name (e->callee),
1378 cgraph_node_name (e->caller));
1379 e->inline_failed = CIF_RECURSIVE_INLINING;
1383 /* When the edge is already inlined, we just need to recurse into
1384 it in order to fully flatten the leaves. */
1385 if (!e->inline_failed)
1387 cgraph_flatten (e->callee);
1391 if (cgraph_recursive_inlining_p (node, e->callee, &e->inline_failed))
1394 fprintf (dump_file, "Not inlining: recursive call.\n");
1398 if (!tree_can_inline_p (e))
1401 fprintf (dump_file, "Not inlining: %s",
1402 cgraph_inline_failed_string (e->inline_failed));
1406 /* Inline the edge and flatten the inline clone. Avoid
1407 recursing through the original node if the node was cloned. */
1409 fprintf (dump_file, " Inlining %s into %s.\n",
1410 cgraph_node_name (e->callee),
1411 cgraph_node_name (e->caller));
1412 orig_callee = e->callee;
1413 cgraph_mark_inline_edge (e, true, NULL);
1414 if (e->callee != orig_callee)
1415 orig_callee->aux = (void *)(size_t) INLINE_ALL;
1416 cgraph_flatten (e->callee);
1417 if (e->callee != orig_callee)
1418 orig_callee->aux = NULL;
1424 /* Decide on the inlining. We do so in the topological order to avoid
1425 expenses on updating data structures. */
1428 cgraph_decide_inlining (void)
1430 struct cgraph_node *node;
1432 struct cgraph_node **order =
1433 XCNEWVEC (struct cgraph_node *, cgraph_n_nodes);
1436 int initial_size = 0;
1438 cgraph_remove_function_insertion_hook (function_insertion_hook_holder);
1439 if (in_lto_p && flag_indirect_inlining)
1440 ipa_update_after_lto_read ();
1441 if (flag_indirect_inlining)
1442 ipa_create_all_structures_for_iinln ();
1446 for (node = cgraph_nodes; node; node = node->next)
1449 struct cgraph_edge *e;
1451 gcc_assert (inline_summary (node)->self_size == node->global.size);
1452 initial_size += node->global.size;
1453 for (e = node->callees; e; e = e->next_callee)
1454 if (max_count < e->count)
1455 max_count = e->count;
1456 if (max_benefit < inline_summary (node)->time_inlining_benefit)
1457 max_benefit = inline_summary (node)->time_inlining_benefit;
1459 gcc_assert (in_lto_p
1461 || (profile_info && flag_branch_probabilities));
1462 overall_size = initial_size;
1464 nnodes = cgraph_postorder (order);
1468 "\nDeciding on inlining. Starting with size %i.\n",
1471 for (node = cgraph_nodes; node; node = node->next)
1475 fprintf (dump_file, "\nFlattening functions:\n");
1477 /* In the first pass handle functions to be flattened. Do this with
1478 a priority so none of our later choices will make this impossible. */
1479 for (i = nnodes - 1; i >= 0; i--)
1483 /* Handle nodes to be flattened, but don't update overall unit
1484 size. Calling the incremental inliner here is lame,
1485 a simple worklist should be enough. What should be left
1486 here from the early inliner (if it runs) is cyclic cases.
1487 Ideally when processing callees we stop inlining at the
1488 entry of cycles, possibly cloning that entry point and
1489 try to flatten itself turning it into a self-recursive
1491 if (lookup_attribute ("flatten",
1492 DECL_ATTRIBUTES (node->decl)) != NULL)
1496 "Flattening %s\n", cgraph_node_name (node));
1497 cgraph_flatten (node);
1501 cgraph_decide_inlining_of_small_functions ();
1503 if (flag_inline_functions_called_once)
1506 fprintf (dump_file, "\nDeciding on functions called once:\n");
1508 /* And finally decide what functions are called once. */
1509 for (i = nnodes - 1; i >= 0; i--)
1514 && !node->callers->next_caller
1515 && cgraph_will_be_removed_from_program_if_no_direct_calls (node)
1516 && node->local.inlinable
1517 && cgraph_function_body_availability (node) >= AVAIL_AVAILABLE
1518 && node->callers->inline_failed
1519 && node->callers->caller != node
1520 && node->callers->caller->global.inlined_to != node
1521 && !node->callers->call_stmt_cannot_inline_p
1522 && !DECL_EXTERNAL (node->decl))
1524 cgraph_inline_failed_t reason;
1525 old_size = overall_size;
1529 "\nConsidering %s size %i.\n",
1530 cgraph_node_name (node), node->global.size);
1532 " Called once from %s %i insns.\n",
1533 cgraph_node_name (node->callers->caller),
1534 node->callers->caller->global.size);
1537 if (cgraph_check_inline_limits (node->callers->caller, node,
1540 struct cgraph_node *caller = node->callers->caller;
1541 cgraph_mark_inline (node->callers);
1544 " Inlined into %s which now has %i size"
1545 " for a net change of %+i size.\n",
1546 cgraph_node_name (caller),
1547 caller->global.size,
1548 overall_size - old_size);
1554 " Not inlining: %s.\n",
1555 cgraph_inline_failed_string (reason));
1561 /* Free ipa-prop structures if they are no longer needed. */
1562 if (flag_indirect_inlining)
1563 ipa_free_all_structures_after_iinln ();
1567 "\nInlined %i calls, eliminated %i functions, "
1568 "size %i turned to %i size.\n\n",
1569 ncalls_inlined, nfunctions_inlined, initial_size,
1575 /* Return true when N is leaf function. Accept cheap (pure&const) builtins
1576 in leaf functions. */
1578 leaf_node_p (struct cgraph_node *n)
1580 struct cgraph_edge *e;
1581 for (e = n->callees; e; e = e->next_callee)
1582 if (!DECL_BUILT_IN (e->callee->decl)
1583 || (!TREE_READONLY (e->callee->decl)
1584 || DECL_PURE_P (e->callee->decl)))
1589 /* Decide on the inlining. We do so in the topological order to avoid
1590 expenses on updating data structures. */
1593 cgraph_decide_inlining_incrementally (struct cgraph_node *node,
1594 enum inlining_mode mode)
1596 struct cgraph_edge *e;
1597 bool inlined = false;
1598 cgraph_inline_failed_t failed_reason;
1600 #ifdef ENABLE_CHECKING
1601 verify_cgraph_node (node);
1604 if (mode != INLINE_ALWAYS_INLINE && mode != INLINE_SIZE_NORECURSIVE
1605 && lookup_attribute ("flatten", DECL_ATTRIBUTES (node->decl)) != NULL)
1608 fprintf (dump_file, "Incrementally flattening %s\n",
1609 cgraph_node_name (node));
1613 /* First of all look for always inline functions. */
1614 if (mode != INLINE_SIZE_NORECURSIVE)
1615 for (e = node->callees; e; e = e->next_callee)
1617 if (!e->callee->local.disregard_inline_limits
1618 && (mode != INLINE_ALL || !e->callee->local.inlinable))
1620 if (e->call_stmt_cannot_inline_p)
1624 "Considering to always inline inline candidate %s.\n",
1625 cgraph_node_name (e->callee));
1626 if (cgraph_recursive_inlining_p (node, e->callee, &e->inline_failed))
1629 fprintf (dump_file, "Not inlining: recursive call.\n");
1632 if (!tree_can_inline_p (e))
1637 cgraph_inline_failed_string (e->inline_failed));
1640 if (gimple_in_ssa_p (DECL_STRUCT_FUNCTION (node->decl))
1641 != gimple_in_ssa_p (DECL_STRUCT_FUNCTION (e->callee->decl)))
1644 fprintf (dump_file, "Not inlining: SSA form does not match.\n");
1647 if (!e->callee->analyzed)
1651 "Not inlining: Function body no longer available.\n");
1656 fprintf (dump_file, " Inlining %s into %s.\n",
1657 cgraph_node_name (e->callee),
1658 cgraph_node_name (e->caller));
1659 cgraph_mark_inline (e);
1663 /* Now do the automatic inlining. */
1664 if (mode != INLINE_ALL && mode != INLINE_ALWAYS_INLINE
1665 /* Never inline regular functions into always-inline functions
1666 during incremental inlining. */
1667 && !node->local.disregard_inline_limits)
1669 bitmap visited = BITMAP_ALLOC (NULL);
1670 for (e = node->callees; e; e = e->next_callee)
1672 int allowed_growth = 0;
1673 if (!e->callee->local.inlinable
1674 || !e->inline_failed
1675 || e->callee->local.disregard_inline_limits)
1677 /* We are inlining a function to all call-sites in node
1678 or to none. So visit each candidate only once. */
1679 if (!bitmap_set_bit (visited, e->callee->uid))
1682 fprintf (dump_file, "Considering inline candidate %s.\n",
1683 cgraph_node_name (e->callee));
1684 if (cgraph_recursive_inlining_p (node, e->callee, &e->inline_failed))
1687 fprintf (dump_file, "Not inlining: recursive call.\n");
1690 if (gimple_in_ssa_p (DECL_STRUCT_FUNCTION (node->decl))
1691 != gimple_in_ssa_p (DECL_STRUCT_FUNCTION (e->callee->decl)))
1695 "Not inlining: SSA form does not match.\n");
1699 if (cgraph_maybe_hot_edge_p (e) && leaf_node_p (e->callee)
1700 && optimize_function_for_speed_p (cfun))
1701 allowed_growth = PARAM_VALUE (PARAM_EARLY_INLINING_INSNS);
1703 /* When the function body would grow and inlining the function
1704 won't eliminate the need for offline copy of the function,
1706 if (((mode == INLINE_SIZE || mode == INLINE_SIZE_NORECURSIVE)
1707 || (!flag_inline_functions
1708 && !DECL_DECLARED_INLINE_P (e->callee->decl)))
1709 && (cgraph_estimate_size_after_inlining (1, e->caller, e->callee)
1710 > e->caller->global.size + allowed_growth)
1711 && cgraph_estimate_growth (e->callee) > allowed_growth)
1715 "Not inlining: code size would grow by %i.\n",
1716 cgraph_estimate_size_after_inlining (1, e->caller,
1718 - e->caller->global.size);
1721 if (!cgraph_check_inline_limits (node, e->callee, &e->inline_failed,
1723 || e->call_stmt_cannot_inline_p)
1726 fprintf (dump_file, "Not inlining: %s.\n",
1727 cgraph_inline_failed_string (e->inline_failed));
1730 if (!e->callee->analyzed)
1734 "Not inlining: Function body no longer available.\n");
1737 if (!tree_can_inline_p (e))
1741 "Not inlining: %s.",
1742 cgraph_inline_failed_string (e->inline_failed));
1745 if (cgraph_default_inline_p (e->callee, &failed_reason))
1748 fprintf (dump_file, " Inlining %s into %s.\n",
1749 cgraph_node_name (e->callee),
1750 cgraph_node_name (e->caller));
1751 cgraph_mark_inline (e);
1755 BITMAP_FREE (visited);
1760 /* Because inlining might remove no-longer reachable nodes, we need to
1761 keep the array visible to garbage collector to avoid reading collected
1764 static GTY ((length ("nnodes"))) struct cgraph_node **order;
1766 /* Do inlining of small functions. Doing so early helps profiling and other
1767 passes to be somewhat more effective and avoids some code duplication in
1768 later real inlining pass for testcases with very many function calls. */
1770 cgraph_early_inlining (void)
1772 struct cgraph_node *node = cgraph_node (current_function_decl);
1773 unsigned int todo = 0;
1781 || !flag_early_inlining)
1783 /* When not optimizing or not inlining inline only always-inline
1785 cgraph_decide_inlining_incrementally (node, INLINE_ALWAYS_INLINE);
1786 timevar_push (TV_INTEGRATION);
1787 todo |= optimize_inline_calls (current_function_decl);
1788 timevar_pop (TV_INTEGRATION);
1792 if (lookup_attribute ("flatten",
1793 DECL_ATTRIBUTES (node->decl)) != NULL)
1797 "Flattening %s\n", cgraph_node_name (node));
1798 cgraph_flatten (node);
1799 timevar_push (TV_INTEGRATION);
1800 todo |= optimize_inline_calls (current_function_decl);
1801 timevar_pop (TV_INTEGRATION);
1803 /* We iterate incremental inlining to get trivial cases of indirect
1805 while (iterations < PARAM_VALUE (PARAM_EARLY_INLINER_MAX_ITERATIONS)
1806 && cgraph_decide_inlining_incrementally (node,
1808 ? INLINE_SIZE_NORECURSIVE
1811 timevar_push (TV_INTEGRATION);
1812 todo |= optimize_inline_calls (current_function_decl);
1814 timevar_pop (TV_INTEGRATION);
1817 fprintf (dump_file, "Iterations: %i\n", iterations);
1820 cfun->always_inline_functions_inlined = true;
1825 struct gimple_opt_pass pass_early_inline =
1829 "einline", /* name */
1831 cgraph_early_inlining, /* execute */
1834 0, /* static_pass_number */
1835 TV_INLINE_HEURISTICS, /* tv_id */
1836 0, /* properties_required */
1837 0, /* properties_provided */
1838 0, /* properties_destroyed */
1839 0, /* todo_flags_start */
1840 TODO_dump_func /* todo_flags_finish */
1844 /* When inlining shall be performed. */
1846 cgraph_gate_ipa_early_inlining (void)
1848 return (flag_early_inlining
1850 && (flag_branch_probabilities || flag_test_coverage
1851 || profile_arc_flag));
1854 /* IPA pass wrapper for early inlining pass. We need to run early inlining
1855 before tree profiling so we have stand alone IPA pass for doing so. */
1856 struct simple_ipa_opt_pass pass_ipa_early_inline =
1860 "einline_ipa", /* name */
1861 cgraph_gate_ipa_early_inlining, /* gate */
1865 0, /* static_pass_number */
1866 TV_INLINE_HEURISTICS, /* tv_id */
1867 0, /* properties_required */
1868 0, /* properties_provided */
1869 0, /* properties_destroyed */
1870 0, /* todo_flags_start */
1871 TODO_dump_cgraph /* todo_flags_finish */
1875 /* See if statement might disappear after inlining. We are not terribly
1876 sophisficated, basically looking for simple abstraction penalty wrappers. */
1879 likely_eliminated_by_inlining_p (gimple stmt)
1881 enum gimple_code code = gimple_code (stmt);
1887 if (gimple_num_ops (stmt) != 2)
1890 /* Casts of parameters, loads from parameters passed by reference
1891 and stores to return value or parameters are probably free after
1893 if (gimple_assign_rhs_code (stmt) == CONVERT_EXPR
1894 || gimple_assign_rhs_code (stmt) == NOP_EXPR
1895 || gimple_assign_rhs_code (stmt) == VIEW_CONVERT_EXPR
1896 || gimple_assign_rhs_class (stmt) == GIMPLE_SINGLE_RHS)
1898 tree rhs = gimple_assign_rhs1 (stmt);
1899 tree lhs = gimple_assign_lhs (stmt);
1900 tree inner_rhs = rhs;
1901 tree inner_lhs = lhs;
1902 bool rhs_free = false;
1903 bool lhs_free = false;
1905 while (handled_component_p (inner_lhs)
1906 || TREE_CODE (inner_lhs) == MEM_REF)
1907 inner_lhs = TREE_OPERAND (inner_lhs, 0);
1908 while (handled_component_p (inner_rhs)
1909 || TREE_CODE (inner_rhs) == ADDR_EXPR
1910 || TREE_CODE (inner_rhs) == MEM_REF)
1911 inner_rhs = TREE_OPERAND (inner_rhs, 0);
1914 if (TREE_CODE (inner_rhs) == PARM_DECL
1915 || (TREE_CODE (inner_rhs) == SSA_NAME
1916 && SSA_NAME_IS_DEFAULT_DEF (inner_rhs)
1917 && TREE_CODE (SSA_NAME_VAR (inner_rhs)) == PARM_DECL))
1919 if (rhs_free && is_gimple_reg (lhs))
1921 if (((TREE_CODE (inner_lhs) == PARM_DECL
1922 || (TREE_CODE (inner_lhs) == SSA_NAME
1923 && SSA_NAME_IS_DEFAULT_DEF (inner_lhs)
1924 && TREE_CODE (SSA_NAME_VAR (inner_lhs)) == PARM_DECL))
1925 && inner_lhs != lhs)
1926 || TREE_CODE (inner_lhs) == RESULT_DECL
1927 || (TREE_CODE (inner_lhs) == SSA_NAME
1928 && TREE_CODE (SSA_NAME_VAR (inner_lhs)) == RESULT_DECL))
1931 && (is_gimple_reg (rhs) || is_gimple_min_invariant (rhs)))
1933 if (lhs_free && rhs_free)
1942 /* Compute function body size parameters for NODE. */
1945 estimate_function_body_sizes (struct cgraph_node *node)
1948 gcov_type time_inlining_benefit = 0;
1950 int size_inlining_benefit = 0;
1952 gimple_stmt_iterator bsi;
1953 struct function *my_function = DECL_STRUCT_FUNCTION (node->decl);
1956 tree funtype = TREE_TYPE (node->decl);
1959 fprintf (dump_file, "Analyzing function body size: %s\n",
1960 cgraph_node_name (node));
1962 gcc_assert (my_function && my_function->cfg);
1963 FOR_EACH_BB_FN (bb, my_function)
1965 freq = compute_call_stmt_bb_frequency (node->decl, bb);
1966 for (bsi = gsi_start_bb (bb); !gsi_end_p (bsi); gsi_next (&bsi))
1968 gimple stmt = gsi_stmt (bsi);
1969 int this_size = estimate_num_insns (stmt, &eni_size_weights);
1970 int this_time = estimate_num_insns (stmt, &eni_time_weights);
1972 if (dump_file && (dump_flags & TDF_DETAILS))
1974 fprintf (dump_file, " freq:%6i size:%3i time:%3i ",
1975 freq, this_size, this_time);
1976 print_gimple_stmt (dump_file, stmt, 0, 0);
1981 if (likely_eliminated_by_inlining_p (stmt))
1983 size_inlining_benefit += this_size;
1984 time_inlining_benefit += this_time;
1985 if (dump_file && (dump_flags & TDF_DETAILS))
1986 fprintf (dump_file, " Likely eliminated\n");
1988 gcc_assert (time >= 0);
1989 gcc_assert (size >= 0);
1992 time = (time + CGRAPH_FREQ_BASE / 2) / CGRAPH_FREQ_BASE;
1993 time_inlining_benefit = ((time_inlining_benefit + CGRAPH_FREQ_BASE / 2)
1994 / CGRAPH_FREQ_BASE);
1996 fprintf (dump_file, "Overall function body time: %i-%i size: %i-%i\n",
1997 (int)time, (int)time_inlining_benefit,
1998 size, size_inlining_benefit);
1999 time_inlining_benefit += eni_time_weights.call_cost;
2000 size_inlining_benefit += eni_size_weights.call_cost;
2001 if (!VOID_TYPE_P (TREE_TYPE (funtype)))
2003 int cost = estimate_move_cost (TREE_TYPE (funtype));
2004 time_inlining_benefit += cost;
2005 size_inlining_benefit += cost;
2007 for (arg = DECL_ARGUMENTS (node->decl); arg; arg = DECL_CHAIN (arg))
2008 if (!VOID_TYPE_P (TREE_TYPE (arg)))
2010 int cost = estimate_move_cost (TREE_TYPE (arg));
2011 time_inlining_benefit += cost;
2012 size_inlining_benefit += cost;
2014 if (time_inlining_benefit > MAX_TIME)
2015 time_inlining_benefit = MAX_TIME;
2016 if (time > MAX_TIME)
2018 inline_summary (node)->self_time = time;
2019 inline_summary (node)->self_size = size;
2021 fprintf (dump_file, "With function call overhead time: %i-%i size: %i-%i\n",
2022 (int)time, (int)time_inlining_benefit,
2023 size, size_inlining_benefit);
2024 inline_summary (node)->time_inlining_benefit = time_inlining_benefit;
2025 inline_summary (node)->size_inlining_benefit = size_inlining_benefit;
2028 /* Compute parameters of functions used by inliner. */
2030 compute_inline_parameters (struct cgraph_node *node)
2032 HOST_WIDE_INT self_stack_size;
2034 gcc_assert (!node->global.inlined_to);
2036 /* Estimate the stack size for the function. But not at -O0
2037 because estimated_stack_frame_size is a quadratic problem. */
2038 self_stack_size = optimize ? estimated_stack_frame_size (node->decl) : 0;
2039 inline_summary (node)->estimated_self_stack_size = self_stack_size;
2040 node->global.estimated_stack_size = self_stack_size;
2041 node->global.stack_frame_offset = 0;
2043 /* Can this function be inlined at all? */
2044 node->local.inlinable = tree_inlinable_function_p (node->decl);
2045 if (node->local.inlinable && !node->local.disregard_inline_limits)
2046 node->local.disregard_inline_limits
2047 = DECL_DISREGARD_INLINE_LIMITS (node->decl);
2048 estimate_function_body_sizes (node);
2049 /* Inlining characteristics are maintained by the cgraph_mark_inline. */
2050 node->global.time = inline_summary (node)->self_time;
2051 node->global.size = inline_summary (node)->self_size;
2056 /* Compute parameters of functions used by inliner using
2057 current_function_decl. */
2059 compute_inline_parameters_for_current (void)
2061 compute_inline_parameters (cgraph_node (current_function_decl));
2065 struct gimple_opt_pass pass_inline_parameters =
2069 "inline_param", /* name */
2071 compute_inline_parameters_for_current,/* execute */
2074 0, /* static_pass_number */
2075 TV_INLINE_HEURISTICS, /* tv_id */
2076 0, /* properties_required */
2077 0, /* properties_provided */
2078 0, /* properties_destroyed */
2079 0, /* todo_flags_start */
2080 0 /* todo_flags_finish */
2084 /* This function performs intraprocedural analyzis in NODE that is required to
2085 inline indirect calls. */
2087 inline_indirect_intraprocedural_analysis (struct cgraph_node *node)
2089 ipa_analyze_node (node);
2090 if (dump_file && (dump_flags & TDF_DETAILS))
2092 ipa_print_node_params (dump_file, node);
2093 ipa_print_node_jump_functions (dump_file, node);
2097 /* Note function body size. */
2099 analyze_function (struct cgraph_node *node)
2101 push_cfun (DECL_STRUCT_FUNCTION (node->decl));
2102 current_function_decl = node->decl;
2104 compute_inline_parameters (node);
2105 /* FIXME: We should remove the optimize check after we ensure we never run
2106 IPA passes when not optimizng. */
2107 if (flag_indirect_inlining && optimize)
2108 inline_indirect_intraprocedural_analysis (node);
2110 current_function_decl = NULL;
2114 /* Called when new function is inserted to callgraph late. */
2116 add_new_function (struct cgraph_node *node, void *data ATTRIBUTE_UNUSED)
2118 analyze_function (node);
2121 /* Note function body size. */
2123 inline_generate_summary (void)
2125 struct cgraph_node *node;
2127 function_insertion_hook_holder =
2128 cgraph_add_function_insertion_hook (&add_new_function, NULL);
2130 if (flag_indirect_inlining)
2132 ipa_register_cgraph_hooks ();
2133 ipa_check_create_node_params ();
2134 ipa_check_create_edge_args ();
2137 for (node = cgraph_nodes; node; node = node->next)
2139 analyze_function (node);
2144 /* Apply inline plan to function. */
2146 inline_transform (struct cgraph_node *node)
2148 unsigned int todo = 0;
2149 struct cgraph_edge *e;
2150 bool inline_p = false;
2152 /* FIXME: Currently the passmanager is adding inline transform more than once to some
2153 clones. This needs revisiting after WPA cleanups. */
2154 if (cfun->after_inlining)
2157 /* We might need the body of this function so that we can expand
2158 it inline somewhere else. */
2159 if (cgraph_preserve_function_body_p (node->decl))
2160 save_inline_function_body (node);
2162 for (e = node->callees; e; e = e->next_callee)
2164 cgraph_redirect_edge_call_stmt_to_callee (e);
2165 if (!e->inline_failed || warn_inline)
2171 timevar_push (TV_INTEGRATION);
2172 todo = optimize_inline_calls (current_function_decl);
2173 timevar_pop (TV_INTEGRATION);
2175 cfun->always_inline_functions_inlined = true;
2176 cfun->after_inlining = true;
2177 return todo | execute_fixup_cfg ();
2180 /* Read inline summary. Jump functions are shared among ipa-cp
2181 and inliner, so when ipa-cp is active, we don't need to write them
2185 inline_read_summary (void)
2187 if (flag_indirect_inlining)
2189 ipa_register_cgraph_hooks ();
2191 ipa_prop_read_jump_functions ();
2193 function_insertion_hook_holder =
2194 cgraph_add_function_insertion_hook (&add_new_function, NULL);
2197 /* Write inline summary for node in SET.
2198 Jump functions are shared among ipa-cp and inliner, so when ipa-cp is
2199 active, we don't need to write them twice. */
2202 inline_write_summary (cgraph_node_set set,
2203 varpool_node_set vset ATTRIBUTE_UNUSED)
2205 if (flag_indirect_inlining && !flag_ipa_cp)
2206 ipa_prop_write_jump_functions (set);
2209 /* When to run IPA inlining. Inlining of always-inline functions
2210 happens during early inlining. */
2213 gate_cgraph_decide_inlining (void)
2215 /* ??? We'd like to skip this if not optimizing or not inlining as
2216 all always-inline functions have been processed by early
2217 inlining already. But this at least breaks EH with C++ as
2218 we need to unconditionally run fixup_cfg even at -O0.
2219 So leave it on unconditionally for now. */
2223 struct ipa_opt_pass_d pass_ipa_inline =
2227 "inline", /* name */
2228 gate_cgraph_decide_inlining, /* gate */
2229 cgraph_decide_inlining, /* execute */
2232 0, /* static_pass_number */
2233 TV_INLINE_HEURISTICS, /* tv_id */
2234 0, /* properties_required */
2235 0, /* properties_provided */
2236 0, /* properties_destroyed */
2237 TODO_remove_functions, /* todo_flags_finish */
2238 TODO_dump_cgraph | TODO_dump_func
2239 | TODO_remove_functions | TODO_ggc_collect /* todo_flags_finish */
2241 inline_generate_summary, /* generate_summary */
2242 inline_write_summary, /* write_summary */
2243 inline_read_summary, /* read_summary */
2244 NULL, /* write_optimization_summary */
2245 NULL, /* read_optimization_summary */
2246 NULL, /* stmt_fixup */
2248 inline_transform, /* function_transform */
2249 NULL, /* variable_transform */
2253 #include "gt-ipa-inline.h"