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"
135 #include "tree-pass.h"
137 #include "coverage.h"
139 #include "tree-flow.h"
141 #include "ipa-prop.h"
144 #define MAX_TIME 1000000000
146 /* Mode incremental inliner operate on:
148 In ALWAYS_INLINE only functions marked
149 always_inline are inlined. This mode is used after detecting cycle during
152 In SIZE mode, only functions that reduce function body size after inlining
153 are inlined, this is used during early inlining.
155 in ALL mode, everything is inlined. This is used during flattening. */
158 INLINE_ALWAYS_INLINE,
159 INLINE_SIZE_NORECURSIVE,
165 cgraph_decide_inlining_incrementally (struct cgraph_node *, enum inlining_mode);
166 static void cgraph_flatten (struct cgraph_node *node);
169 /* Statistics we collect about inlining algorithm. */
170 static int ncalls_inlined;
171 static int nfunctions_inlined;
172 static int overall_size;
173 static gcov_type max_count, max_benefit;
175 /* Holders of ipa cgraph hooks: */
176 static struct cgraph_node_hook_list *function_insertion_hook_holder;
178 static inline struct inline_summary *
179 inline_summary (struct cgraph_node *node)
181 return &node->local.inline_summary;
184 /* Estimate self time of the function after inlining WHAT into TO. */
187 cgraph_estimate_time_after_inlining (int frequency, struct cgraph_node *to,
188 struct cgraph_node *what)
190 gcov_type time = (((gcov_type)what->global.time
191 - inline_summary (what)->time_inlining_benefit)
192 * frequency + CGRAPH_FREQ_BASE / 2) / CGRAPH_FREQ_BASE
201 /* Estimate self time of the function after inlining WHAT into TO. */
204 cgraph_estimate_size_after_inlining (int times, struct cgraph_node *to,
205 struct cgraph_node *what)
207 int size = (what->global.size - inline_summary (what)->size_inlining_benefit) * times + to->global.size;
208 gcc_assert (size >= 0);
212 /* Scale frequency of NODE edges by FREQ_SCALE and increase loop nest
216 update_noncloned_frequencies (struct cgraph_node *node,
217 int freq_scale, int nest)
219 struct cgraph_edge *e;
221 /* We do not want to ignore high loop nest after freq drops to 0. */
224 for (e = node->callees; e; e = e->next_callee)
226 e->loop_nest += nest;
227 e->frequency = e->frequency * (gcov_type) freq_scale / CGRAPH_FREQ_BASE;
228 if (e->frequency > CGRAPH_FREQ_MAX)
229 e->frequency = CGRAPH_FREQ_MAX;
230 if (!e->inline_failed)
231 update_noncloned_frequencies (e->callee, freq_scale, nest);
235 /* E is expected to be an edge being inlined. Clone destination node of
236 the edge and redirect it to the new clone.
237 DUPLICATE is used for bookkeeping on whether we are actually creating new
238 clones or re-using node originally representing out-of-line function call.
241 cgraph_clone_inlined_nodes (struct cgraph_edge *e, bool duplicate,
242 bool update_original)
248 /* We may eliminate the need for out-of-line copy to be output.
249 In that case just go ahead and re-use it. */
250 if (!e->callee->callers->next_caller
251 && cgraph_can_remove_if_no_direct_calls_p (e->callee)
252 /* Don't reuse if more than one function shares a comdat group.
253 If the other function(s) are needed, we need to emit even
254 this function out of line. */
255 && !e->callee->same_comdat_group
256 && !cgraph_new_nodes)
258 gcc_assert (!e->callee->global.inlined_to);
259 if (e->callee->analyzed)
261 overall_size -= e->callee->global.size;
262 nfunctions_inlined++;
265 e->callee->local.externally_visible = false;
266 update_noncloned_frequencies (e->callee, e->frequency, e->loop_nest);
270 struct cgraph_node *n;
271 n = cgraph_clone_node (e->callee, e->count, e->frequency, e->loop_nest,
272 update_original, NULL);
273 cgraph_redirect_edge_callee (e, n);
277 if (e->caller->global.inlined_to)
278 e->callee->global.inlined_to = e->caller->global.inlined_to;
280 e->callee->global.inlined_to = e->caller;
281 e->callee->global.stack_frame_offset
282 = e->caller->global.stack_frame_offset
283 + inline_summary (e->caller)->estimated_self_stack_size;
284 peak = e->callee->global.stack_frame_offset
285 + inline_summary (e->callee)->estimated_self_stack_size;
286 if (e->callee->global.inlined_to->global.estimated_stack_size < peak)
287 e->callee->global.inlined_to->global.estimated_stack_size = peak;
288 cgraph_propagate_frequency (e->callee);
290 /* Recursively clone all bodies. */
291 for (e = e->callee->callees; e; e = e->next_callee)
292 if (!e->inline_failed)
293 cgraph_clone_inlined_nodes (e, duplicate, update_original);
296 /* Mark edge E as inlined and update callgraph accordingly. UPDATE_ORIGINAL
297 specify whether profile of original function should be updated. If any new
298 indirect edges are discovered in the process, add them to NEW_EDGES, unless
299 it is NULL. Return true iff any new callgraph edges were discovered as a
300 result of inlining. */
303 cgraph_mark_inline_edge (struct cgraph_edge *e, bool update_original,
304 VEC (cgraph_edge_p, heap) **new_edges)
306 int old_size = 0, new_size = 0;
307 struct cgraph_node *to = NULL, *what;
308 struct cgraph_edge *curr = e;
311 gcc_assert (e->inline_failed);
312 e->inline_failed = CIF_OK;
313 DECL_POSSIBLY_INLINED (e->callee->decl) = true;
315 cgraph_clone_inlined_nodes (e, true, update_original);
320 /* Now update size of caller and all functions caller is inlined into. */
321 for (;e && !e->inline_failed; e = e->caller->callers)
324 old_size = e->caller->global.size;
325 new_size = cgraph_estimate_size_after_inlining (1, to, what);
326 to->global.size = new_size;
327 to->global.time = cgraph_estimate_time_after_inlining (freq, to, what);
329 gcc_assert (what->global.inlined_to == to);
330 if (new_size > old_size)
331 overall_size += new_size - old_size;
334 if (flag_indirect_inlining)
335 return ipa_propagate_indirect_call_infos (curr, new_edges);
340 /* Mark all calls of EDGE->CALLEE inlined into EDGE->CALLER. */
343 cgraph_mark_inline (struct cgraph_edge *edge)
345 struct cgraph_node *to = edge->caller;
346 struct cgraph_node *what = edge->callee;
347 struct cgraph_edge *e, *next;
349 gcc_assert (!edge->call_stmt_cannot_inline_p);
350 /* Look for all calls, mark them inline and clone recursively
351 all inlined functions. */
352 for (e = what->callers; e; e = next)
354 next = e->next_caller;
355 if (e->caller == to && e->inline_failed)
357 cgraph_mark_inline_edge (e, true, NULL);
364 /* Estimate the growth caused by inlining NODE into all callees. */
367 cgraph_estimate_growth (struct cgraph_node *node)
370 struct cgraph_edge *e;
371 bool self_recursive = false;
373 if (node->global.estimated_growth != INT_MIN)
374 return node->global.estimated_growth;
376 for (e = node->callers; e; e = e->next_caller)
378 if (e->caller == node)
379 self_recursive = true;
380 if (e->inline_failed)
381 growth += (cgraph_estimate_size_after_inlining (1, e->caller, node)
382 - e->caller->global.size);
385 /* ??? Wrong for non-trivially self recursive functions or cases where
386 we decide to not inline for different reasons, but it is not big deal
387 as in that case we will keep the body around, but we will also avoid
389 if (cgraph_only_called_directly_p (node)
390 && !DECL_EXTERNAL (node->decl) && !self_recursive)
391 growth -= node->global.size;
393 node->global.estimated_growth = growth;
397 /* Return false when inlining WHAT into TO is not good idea
398 as it would cause too large growth of function bodies.
399 When ONE_ONLY is true, assume that only one call site is going
400 to be inlined, otherwise figure out how many call sites in
401 TO calls WHAT and verify that all can be inlined.
405 cgraph_check_inline_limits (struct cgraph_node *to, struct cgraph_node *what,
406 cgraph_inline_failed_t *reason, bool one_only)
409 struct cgraph_edge *e;
412 HOST_WIDE_INT stack_size_limit, inlined_stack;
417 for (e = to->callees; e; e = e->next_callee)
418 if (e->callee == what)
421 if (to->global.inlined_to)
422 to = to->global.inlined_to;
424 /* When inlining large function body called once into small function,
425 take the inlined function as base for limiting the growth. */
426 if (inline_summary (to)->self_size > inline_summary(what)->self_size)
427 limit = inline_summary (to)->self_size;
429 limit = inline_summary (what)->self_size;
431 limit += limit * PARAM_VALUE (PARAM_LARGE_FUNCTION_GROWTH) / 100;
433 /* Check the size after inlining against the function limits. But allow
434 the function to shrink if it went over the limits by forced inlining. */
435 newsize = cgraph_estimate_size_after_inlining (times, to, what);
436 if (newsize >= to->global.size
437 && newsize > PARAM_VALUE (PARAM_LARGE_FUNCTION_INSNS)
441 *reason = CIF_LARGE_FUNCTION_GROWTH_LIMIT;
445 stack_size_limit = inline_summary (to)->estimated_self_stack_size;
447 stack_size_limit += stack_size_limit * PARAM_VALUE (PARAM_STACK_FRAME_GROWTH) / 100;
449 inlined_stack = (to->global.stack_frame_offset
450 + inline_summary (to)->estimated_self_stack_size
451 + what->global.estimated_stack_size);
452 if (inlined_stack > stack_size_limit
453 && inlined_stack > PARAM_VALUE (PARAM_LARGE_STACK_FRAME))
456 *reason = CIF_LARGE_STACK_FRAME_GROWTH_LIMIT;
462 /* Return true when function N is small enough to be inlined. */
465 cgraph_default_inline_p (struct cgraph_node *n, cgraph_inline_failed_t *reason)
469 if (n->local.disregard_inline_limits)
472 if (!flag_inline_small_functions && !DECL_DECLARED_INLINE_P (decl))
475 *reason = CIF_FUNCTION_NOT_INLINE_CANDIDATE;
482 *reason = CIF_BODY_NOT_AVAILABLE;
486 if (DECL_DECLARED_INLINE_P (decl))
488 if (n->global.size >= MAX_INLINE_INSNS_SINGLE)
491 *reason = CIF_MAX_INLINE_INSNS_SINGLE_LIMIT;
497 if (n->global.size >= MAX_INLINE_INSNS_AUTO)
500 *reason = CIF_MAX_INLINE_INSNS_AUTO_LIMIT;
508 /* Return true when inlining WHAT would create recursive inlining.
509 We call recursive inlining all cases where same function appears more than
510 once in the single recursion nest path in the inline graph. */
513 cgraph_recursive_inlining_p (struct cgraph_node *to,
514 struct cgraph_node *what,
515 cgraph_inline_failed_t *reason)
518 if (to->global.inlined_to)
519 recursive = what->decl == to->global.inlined_to->decl;
521 recursive = what->decl == to->decl;
522 /* Marking recursive function inline has sane semantic and thus we should
524 if (recursive && reason)
525 *reason = (what->local.disregard_inline_limits
526 ? CIF_RECURSIVE_INLINING : CIF_UNSPECIFIED);
530 /* A cost model driving the inlining heuristics in a way so the edges with
531 smallest badness are inlined first. After each inlining is performed
532 the costs of all caller edges of nodes affected are recomputed so the
533 metrics may accurately depend on values such as number of inlinable callers
534 of the function or function body size. */
537 cgraph_edge_badness (struct cgraph_edge *edge, bool dump)
541 (cgraph_estimate_size_after_inlining (1, edge->caller, edge->callee)
542 - edge->caller->global.size);
544 if (edge->callee->local.disregard_inline_limits)
549 fprintf (dump_file, " Badness calculcation for %s -> %s\n",
550 cgraph_node_name (edge->caller),
551 cgraph_node_name (edge->callee));
552 fprintf (dump_file, " growth %i, time %i-%i, size %i-%i\n",
554 edge->callee->global.time,
555 inline_summary (edge->callee)->time_inlining_benefit,
556 edge->callee->global.size,
557 inline_summary (edge->callee)->size_inlining_benefit);
560 /* Always prefer inlining saving code size. */
563 badness = INT_MIN - growth;
565 fprintf (dump_file, " %i: Growth %i < 0\n", (int) badness,
569 /* When profiling is available, base priorities -(#calls / growth).
570 So we optimize for overall number of "executed" inlined calls. */
575 ((double) edge->count * INT_MIN / max_count / (max_benefit + 1)) *
576 (inline_summary (edge->callee)->time_inlining_benefit + 1)) / growth;
580 " %i (relative %f): profile info. Relative count %f"
581 " * Relative benefit %f\n",
582 (int) badness, (double) badness / INT_MIN,
583 (double) edge->count / max_count,
584 (double) (inline_summary (edge->callee)->
585 time_inlining_benefit + 1) / (max_benefit + 1));
589 /* When function local profile is available, base priorities on
590 growth / frequency, so we optimize for overall frequency of inlined
591 calls. This is not too accurate since while the call might be frequent
592 within function, the function itself is infrequent.
594 Other objective to optimize for is number of different calls inlined.
595 We add the estimated growth after inlining all functions to bias the
596 priorities slightly in this direction (so fewer times called functions
597 of the same size gets priority). */
598 else if (flag_guess_branch_prob)
600 int div = edge->frequency * 100 / CGRAPH_FREQ_BASE + 1;
603 badness = growth * 10000;
605 MIN (100 * inline_summary (edge->callee)->time_inlining_benefit /
606 (edge->callee->global.time + 1) +1, 100);
610 /* Decrease badness if call is nested. */
611 /* Compress the range so we don't overflow. */
613 div = 10000 + ceil_log2 (div) - 8;
618 growth_for_all = cgraph_estimate_growth (edge->callee);
619 badness += growth_for_all;
620 if (badness > INT_MAX)
625 " %i: guessed profile. frequency %i, overall growth %i,"
626 " benefit %i%%, divisor %i\n",
627 (int) badness, edge->frequency, growth_for_all, benefitperc, div);
630 /* When function local profile is not available or it does not give
631 useful information (ie frequency is zero), base the cost on
632 loop nest and overall size growth, so we optimize for overall number
633 of functions fully inlined in program. */
636 int nest = MIN (edge->loop_nest, 8);
637 badness = cgraph_estimate_growth (edge->callee) * 256;
639 /* Decrease badness if call is nested. */
647 fprintf (dump_file, " %i: no profile. nest %i\n", (int) badness,
651 /* Ensure that we did not overflow in all the fixed point math above. */
652 gcc_assert (badness >= INT_MIN);
653 gcc_assert (badness <= INT_MAX - 1);
654 /* Make recursive inlining happen always after other inlining is done. */
655 if (cgraph_recursive_inlining_p (edge->caller, edge->callee, NULL))
661 /* Recompute heap nodes for each of caller edge. */
664 update_caller_keys (fibheap_t heap, struct cgraph_node *node,
665 bitmap updated_nodes)
667 struct cgraph_edge *edge;
668 cgraph_inline_failed_t failed_reason;
670 if (!node->local.inlinable
671 || node->global.inlined_to)
673 if (bitmap_bit_p (updated_nodes, node->uid))
675 bitmap_set_bit (updated_nodes, node->uid);
676 node->global.estimated_growth = INT_MIN;
678 if (!node->local.inlinable)
680 /* Prune out edges we won't inline into anymore. */
681 if (!cgraph_default_inline_p (node, &failed_reason))
683 for (edge = node->callers; edge; edge = edge->next_caller)
686 fibheap_delete_node (heap, (fibnode_t) edge->aux);
688 if (edge->inline_failed)
689 edge->inline_failed = failed_reason;
694 for (edge = node->callers; edge; edge = edge->next_caller)
695 if (edge->inline_failed)
697 int badness = cgraph_edge_badness (edge, false);
700 fibnode_t n = (fibnode_t) edge->aux;
701 gcc_assert (n->data == edge);
702 if (n->key == badness)
705 /* fibheap_replace_key only increase the keys. */
706 if (badness < n->key)
708 fibheap_replace_key (heap, n, badness);
709 gcc_assert (n->key == badness);
712 fibheap_delete_node (heap, (fibnode_t) edge->aux);
714 edge->aux = fibheap_insert (heap, badness, edge);
718 /* Recompute heap nodes for each of caller edges of each of callees. */
721 update_callee_keys (fibheap_t heap, struct cgraph_node *node,
722 bitmap updated_nodes)
724 struct cgraph_edge *e;
725 node->global.estimated_growth = INT_MIN;
727 for (e = node->callees; e; e = e->next_callee)
728 if (e->inline_failed)
729 update_caller_keys (heap, e->callee, updated_nodes);
730 else if (!e->inline_failed)
731 update_callee_keys (heap, e->callee, updated_nodes);
734 /* Enqueue all recursive calls from NODE into priority queue depending on
735 how likely we want to recursively inline the call. */
738 lookup_recursive_calls (struct cgraph_node *node, struct cgraph_node *where,
742 struct cgraph_edge *e;
743 for (e = where->callees; e; e = e->next_callee)
744 if (e->callee == node)
746 /* When profile feedback is available, prioritize by expected number
747 of calls. Without profile feedback we maintain simple queue
748 to order candidates via recursive depths. */
749 fibheap_insert (heap,
750 !max_count ? priority++
751 : -(e->count / ((max_count + (1<<24) - 1) / (1<<24))),
754 for (e = where->callees; e; e = e->next_callee)
755 if (!e->inline_failed)
756 lookup_recursive_calls (node, e->callee, heap);
759 /* Decide on recursive inlining: in the case function has recursive calls,
760 inline until body size reaches given argument. If any new indirect edges
761 are discovered in the process, add them to *NEW_EDGES, unless NEW_EDGES
765 cgraph_decide_recursive_inlining (struct cgraph_node *node,
766 VEC (cgraph_edge_p, heap) **new_edges)
768 int limit = PARAM_VALUE (PARAM_MAX_INLINE_INSNS_RECURSIVE_AUTO);
769 int max_depth = PARAM_VALUE (PARAM_MAX_INLINE_RECURSIVE_DEPTH_AUTO);
770 int probability = PARAM_VALUE (PARAM_MIN_INLINE_RECURSIVE_PROBABILITY);
772 struct cgraph_edge *e;
773 struct cgraph_node *master_clone, *next;
777 /* It does not make sense to recursively inline always-inline functions
778 as we are going to sorry() on the remaining calls anyway. */
779 if (node->local.disregard_inline_limits
780 && lookup_attribute ("always_inline", DECL_ATTRIBUTES (node->decl)))
783 if (optimize_function_for_size_p (DECL_STRUCT_FUNCTION (node->decl))
784 || (!flag_inline_functions && !DECL_DECLARED_INLINE_P (node->decl)))
787 if (DECL_DECLARED_INLINE_P (node->decl))
789 limit = PARAM_VALUE (PARAM_MAX_INLINE_INSNS_RECURSIVE);
790 max_depth = PARAM_VALUE (PARAM_MAX_INLINE_RECURSIVE_DEPTH);
793 /* Make sure that function is small enough to be considered for inlining. */
795 || cgraph_estimate_size_after_inlining (1, node, node) >= limit)
797 heap = fibheap_new ();
798 lookup_recursive_calls (node, node, heap);
799 if (fibheap_empty (heap))
801 fibheap_delete (heap);
807 " Performing recursive inlining on %s\n",
808 cgraph_node_name (node));
810 /* We need original clone to copy around. */
811 master_clone = cgraph_clone_node (node, node->count, CGRAPH_FREQ_BASE, 1,
813 master_clone->needed = true;
814 for (e = master_clone->callees; e; e = e->next_callee)
815 if (!e->inline_failed)
816 cgraph_clone_inlined_nodes (e, true, false);
818 /* Do the inlining and update list of recursive call during process. */
819 while (!fibheap_empty (heap)
820 && (cgraph_estimate_size_after_inlining (1, node, master_clone)
823 struct cgraph_edge *curr
824 = (struct cgraph_edge *) fibheap_extract_min (heap);
825 struct cgraph_node *cnode;
828 for (cnode = curr->caller;
829 cnode->global.inlined_to; cnode = cnode->callers->caller)
830 if (node->decl == curr->callee->decl)
832 if (depth > max_depth)
836 " maximal depth reached\n");
842 if (!cgraph_maybe_hot_edge_p (curr))
845 fprintf (dump_file, " Not inlining cold call\n");
848 if (curr->count * 100 / node->count < probability)
852 " Probability of edge is too small\n");
860 " Inlining call of depth %i", depth);
863 fprintf (dump_file, " called approx. %.2f times per call",
864 (double)curr->count / node->count);
866 fprintf (dump_file, "\n");
868 cgraph_redirect_edge_callee (curr, master_clone);
869 cgraph_mark_inline_edge (curr, false, new_edges);
870 lookup_recursive_calls (node, curr->callee, heap);
873 if (!fibheap_empty (heap) && dump_file)
874 fprintf (dump_file, " Recursive inlining growth limit met.\n");
876 fibheap_delete (heap);
879 "\n Inlined %i times, body grown from size %i to %i, time %i to %i\n", n,
880 master_clone->global.size, node->global.size,
881 master_clone->global.time, node->global.time);
883 /* Remove master clone we used for inlining. We rely that clones inlined
884 into master clone gets queued just before master clone so we don't
886 for (node = cgraph_nodes; node != master_clone;
890 if (node->global.inlined_to == master_clone)
891 cgraph_remove_node (node);
893 cgraph_remove_node (master_clone);
894 /* FIXME: Recursive inlining actually reduces number of calls of the
895 function. At this place we should probably walk the function and
896 inline clones and compensate the counts accordingly. This probably
897 doesn't matter much in practice. */
901 /* Set inline_failed for all callers of given function to REASON. */
904 cgraph_set_inline_failed (struct cgraph_node *node,
905 cgraph_inline_failed_t reason)
907 struct cgraph_edge *e;
910 fprintf (dump_file, "Inlining failed: %s\n",
911 cgraph_inline_failed_string (reason));
912 for (e = node->callers; e; e = e->next_caller)
913 if (e->inline_failed)
914 e->inline_failed = reason;
917 /* Given whole compilation unit estimate of INSNS, compute how large we can
918 allow the unit to grow. */
920 compute_max_insns (int insns)
922 int max_insns = insns;
923 if (max_insns < PARAM_VALUE (PARAM_LARGE_UNIT_INSNS))
924 max_insns = PARAM_VALUE (PARAM_LARGE_UNIT_INSNS);
926 return ((HOST_WIDEST_INT) max_insns
927 * (100 + PARAM_VALUE (PARAM_INLINE_UNIT_GROWTH)) / 100);
930 /* Compute badness of all edges in NEW_EDGES and add them to the HEAP. */
932 add_new_edges_to_heap (fibheap_t heap, VEC (cgraph_edge_p, heap) *new_edges)
934 while (VEC_length (cgraph_edge_p, new_edges) > 0)
936 struct cgraph_edge *edge = VEC_pop (cgraph_edge_p, new_edges);
938 gcc_assert (!edge->aux);
939 edge->aux = fibheap_insert (heap, cgraph_edge_badness (edge, false), edge);
944 /* We use greedy algorithm for inlining of small functions:
945 All inline candidates are put into prioritized heap based on estimated
946 growth of the overall number of instructions and then update the estimates.
948 INLINED and INLINED_CALEES are just pointers to arrays large enough
949 to be passed to cgraph_inlined_into and cgraph_inlined_callees. */
952 cgraph_decide_inlining_of_small_functions (void)
954 struct cgraph_node *node;
955 struct cgraph_edge *edge;
956 cgraph_inline_failed_t failed_reason;
957 fibheap_t heap = fibheap_new ();
958 bitmap updated_nodes = BITMAP_ALLOC (NULL);
959 int min_size, max_size;
960 VEC (cgraph_edge_p, heap) *new_indirect_edges = NULL;
962 if (flag_indirect_inlining)
963 new_indirect_edges = VEC_alloc (cgraph_edge_p, heap, 8);
966 fprintf (dump_file, "\nDeciding on smaller functions:\n");
968 /* Put all inline candidates into the heap. */
970 for (node = cgraph_nodes; node; node = node->next)
972 if (!node->local.inlinable || !node->callers)
975 fprintf (dump_file, "Considering inline candidate %s.\n", cgraph_node_name (node));
977 node->global.estimated_growth = INT_MIN;
978 if (!cgraph_default_inline_p (node, &failed_reason))
980 cgraph_set_inline_failed (node, failed_reason);
984 for (edge = node->callers; edge; edge = edge->next_caller)
985 if (edge->inline_failed)
987 gcc_assert (!edge->aux);
988 edge->aux = fibheap_insert (heap, cgraph_edge_badness (edge, false), edge);
992 max_size = compute_max_insns (overall_size);
993 min_size = overall_size;
995 while (overall_size <= max_size
996 && !fibheap_empty (heap))
998 int old_size = overall_size;
999 struct cgraph_node *where, *callee;
1000 int badness = fibheap_min_key (heap);
1002 cgraph_inline_failed_t not_good = CIF_OK;
1004 edge = (struct cgraph_edge *) fibheap_extract_min (heap);
1005 gcc_assert (edge->aux);
1007 if (!edge->inline_failed)
1009 #ifdef ENABLE_CHECKING
1010 gcc_assert (cgraph_edge_badness (edge, false) == badness);
1012 callee = edge->callee;
1014 growth = (cgraph_estimate_size_after_inlining (1, edge->caller, edge->callee)
1015 - edge->caller->global.size);
1020 "\nConsidering %s with %i size\n",
1021 cgraph_node_name (edge->callee),
1022 edge->callee->global.size);
1024 " to be inlined into %s in %s:%i\n"
1025 " Estimated growth after inlined into all callees is %+i insns.\n"
1026 " Estimated badness is %i, frequency %.2f.\n",
1027 cgraph_node_name (edge->caller),
1028 flag_wpa ? "unknown"
1029 : gimple_filename ((const_gimple) edge->call_stmt),
1030 flag_wpa ? -1 : gimple_lineno ((const_gimple) edge->call_stmt),
1031 cgraph_estimate_growth (edge->callee),
1033 edge->frequency / (double)CGRAPH_FREQ_BASE);
1035 fprintf (dump_file," Called "HOST_WIDEST_INT_PRINT_DEC"x\n", edge->count);
1036 if (dump_flags & TDF_DETAILS)
1037 cgraph_edge_badness (edge, true);
1040 /* When not having profile info ready we don't weight by any way the
1041 position of call in procedure itself. This means if call of
1042 function A from function B seems profitable to inline, the recursive
1043 call of function A in inline copy of A in B will look profitable too
1044 and we end up inlining until reaching maximal function growth. This
1045 is not good idea so prohibit the recursive inlining.
1047 ??? When the frequencies are taken into account we might not need this
1050 We need to be cureful here, in some testcases, e.g. directivec.c in
1051 libcpp, we can estimate self recursive function to have negative growth
1052 for inlining completely.
1056 where = edge->caller;
1057 while (where->global.inlined_to)
1059 if (where->decl == edge->callee->decl)
1061 where = where->callers->caller;
1063 if (where->global.inlined_to)
1066 = (edge->callee->local.disregard_inline_limits
1067 ? CIF_RECURSIVE_INLINING : CIF_UNSPECIFIED);
1069 fprintf (dump_file, " inline_failed:Recursive inlining performed only for function itself.\n");
1074 if (edge->callee->local.disregard_inline_limits)
1076 else if (!cgraph_maybe_hot_edge_p (edge))
1077 not_good = CIF_UNLIKELY_CALL;
1078 else if (!flag_inline_functions
1079 && !DECL_DECLARED_INLINE_P (edge->callee->decl))
1080 not_good = CIF_NOT_DECLARED_INLINED;
1081 else if (optimize_function_for_size_p (DECL_STRUCT_FUNCTION(edge->caller->decl)))
1082 not_good = CIF_OPTIMIZING_FOR_SIZE;
1083 if (not_good && growth > 0 && cgraph_estimate_growth (edge->callee) > 0)
1085 if (!cgraph_recursive_inlining_p (edge->caller, edge->callee,
1086 &edge->inline_failed))
1088 edge->inline_failed = not_good;
1090 fprintf (dump_file, " inline_failed:%s.\n",
1091 cgraph_inline_failed_string (edge->inline_failed));
1095 if (!cgraph_default_inline_p (edge->callee, &edge->inline_failed))
1097 if (!cgraph_recursive_inlining_p (edge->caller, edge->callee,
1098 &edge->inline_failed))
1101 fprintf (dump_file, " inline_failed:%s.\n",
1102 cgraph_inline_failed_string (edge->inline_failed));
1106 if (!tree_can_inline_p (edge))
1109 fprintf (dump_file, " inline_failed:%s.\n",
1110 cgraph_inline_failed_string (edge->inline_failed));
1113 if (cgraph_recursive_inlining_p (edge->caller, edge->callee,
1114 &edge->inline_failed))
1116 where = edge->caller;
1117 if (where->global.inlined_to)
1118 where = where->global.inlined_to;
1119 if (!cgraph_decide_recursive_inlining (where,
1120 flag_indirect_inlining
1121 ? &new_indirect_edges : NULL))
1123 if (flag_indirect_inlining)
1124 add_new_edges_to_heap (heap, new_indirect_edges);
1125 update_callee_keys (heap, where, updated_nodes);
1129 struct cgraph_node *callee;
1130 if (edge->call_stmt_cannot_inline_p
1131 || !cgraph_check_inline_limits (edge->caller, edge->callee,
1132 &edge->inline_failed, true))
1135 fprintf (dump_file, " Not inlining into %s:%s.\n",
1136 cgraph_node_name (edge->caller),
1137 cgraph_inline_failed_string (edge->inline_failed));
1140 callee = edge->callee;
1141 cgraph_mark_inline_edge (edge, true, &new_indirect_edges);
1142 if (flag_indirect_inlining)
1143 add_new_edges_to_heap (heap, new_indirect_edges);
1145 update_callee_keys (heap, callee, updated_nodes);
1147 where = edge->caller;
1148 if (where->global.inlined_to)
1149 where = where->global.inlined_to;
1151 /* Our profitability metric can depend on local properties
1152 such as number of inlinable calls and size of the function body.
1153 After inlining these properties might change for the function we
1154 inlined into (since it's body size changed) and for the functions
1155 called by function we inlined (since number of it inlinable callers
1157 update_caller_keys (heap, where, updated_nodes);
1159 /* We removed one call of the function we just inlined. If offline
1160 copy is still needed, be sure to update the keys. */
1161 if (callee != where && !callee->global.inlined_to)
1162 update_caller_keys (heap, callee, updated_nodes);
1163 bitmap_clear (updated_nodes);
1168 " Inlined into %s which now has size %i and self time %i,"
1169 "net change of %+i.\n",
1170 cgraph_node_name (edge->caller),
1171 edge->caller->global.time,
1172 edge->caller->global.size,
1173 overall_size - old_size);
1175 if (min_size > overall_size)
1177 min_size = overall_size;
1178 max_size = compute_max_insns (min_size);
1181 fprintf (dump_file, "New minimal size reached: %i\n", min_size);
1184 while (!fibheap_empty (heap))
1186 int badness = fibheap_min_key (heap);
1188 edge = (struct cgraph_edge *) fibheap_extract_min (heap);
1189 gcc_assert (edge->aux);
1191 if (!edge->inline_failed)
1193 #ifdef ENABLE_CHECKING
1194 gcc_assert (cgraph_edge_badness (edge, false) == badness);
1199 "\nSkipping %s with %i size\n",
1200 cgraph_node_name (edge->callee),
1201 edge->callee->global.size);
1203 " called by %s in %s:%i\n"
1204 " Estimated growth after inlined into all callees is %+i insns.\n"
1205 " Estimated badness is %i, frequency %.2f.\n",
1206 cgraph_node_name (edge->caller),
1207 flag_wpa ? "unknown"
1208 : gimple_filename ((const_gimple) edge->call_stmt),
1209 flag_wpa ? -1 : gimple_lineno ((const_gimple) edge->call_stmt),
1210 cgraph_estimate_growth (edge->callee),
1212 edge->frequency / (double)CGRAPH_FREQ_BASE);
1214 fprintf (dump_file," Called "HOST_WIDEST_INT_PRINT_DEC"x\n", edge->count);
1215 if (dump_flags & TDF_DETAILS)
1216 cgraph_edge_badness (edge, true);
1218 if (!edge->callee->local.disregard_inline_limits && edge->inline_failed
1219 && !cgraph_recursive_inlining_p (edge->caller, edge->callee,
1220 &edge->inline_failed))
1221 edge->inline_failed = CIF_INLINE_UNIT_GROWTH_LIMIT;
1224 if (new_indirect_edges)
1225 VEC_free (cgraph_edge_p, heap, new_indirect_edges);
1226 fibheap_delete (heap);
1227 BITMAP_FREE (updated_nodes);
1230 /* Flatten NODE from the IPA inliner. */
1233 cgraph_flatten (struct cgraph_node *node)
1235 struct cgraph_edge *e;
1237 /* We shouldn't be called recursively when we are being processed. */
1238 gcc_assert (node->aux == NULL);
1240 node->aux = (void *)(size_t) INLINE_ALL;
1242 for (e = node->callees; e; e = e->next_callee)
1244 struct cgraph_node *orig_callee;
1246 if (e->call_stmt_cannot_inline_p)
1249 if (!e->callee->analyzed)
1253 "Not inlining: Function body not available.\n");
1257 /* We've hit cycle? It is time to give up. */
1262 "Not inlining %s into %s to avoid cycle.\n",
1263 cgraph_node_name (e->callee),
1264 cgraph_node_name (e->caller));
1265 e->inline_failed = CIF_RECURSIVE_INLINING;
1269 /* When the edge is already inlined, we just need to recurse into
1270 it in order to fully flatten the leaves. */
1271 if (!e->inline_failed)
1273 cgraph_flatten (e->callee);
1277 if (cgraph_recursive_inlining_p (node, e->callee, &e->inline_failed))
1280 fprintf (dump_file, "Not inlining: recursive call.\n");
1284 if (!tree_can_inline_p (e))
1287 fprintf (dump_file, "Not inlining: %s",
1288 cgraph_inline_failed_string (e->inline_failed));
1292 /* Inline the edge and flatten the inline clone. Avoid
1293 recursing through the original node if the node was cloned. */
1295 fprintf (dump_file, " Inlining %s into %s.\n",
1296 cgraph_node_name (e->callee),
1297 cgraph_node_name (e->caller));
1298 orig_callee = e->callee;
1299 cgraph_mark_inline_edge (e, true, NULL);
1300 if (e->callee != orig_callee)
1301 orig_callee->aux = (void *)(size_t) INLINE_ALL;
1302 cgraph_flatten (e->callee);
1303 if (e->callee != orig_callee)
1304 orig_callee->aux = NULL;
1310 /* Decide on the inlining. We do so in the topological order to avoid
1311 expenses on updating data structures. */
1314 cgraph_decide_inlining (void)
1316 struct cgraph_node *node;
1318 struct cgraph_node **order =
1319 XCNEWVEC (struct cgraph_node *, cgraph_n_nodes);
1322 int initial_size = 0;
1324 cgraph_remove_function_insertion_hook (function_insertion_hook_holder);
1325 if (in_lto_p && flag_indirect_inlining)
1326 ipa_update_after_lto_read ();
1327 if (flag_indirect_inlining)
1328 ipa_create_all_structures_for_iinln ();
1332 for (node = cgraph_nodes; node; node = node->next)
1335 struct cgraph_edge *e;
1337 gcc_assert (inline_summary (node)->self_size == node->global.size);
1338 initial_size += node->global.size;
1339 for (e = node->callees; e; e = e->next_callee)
1340 if (max_count < e->count)
1341 max_count = e->count;
1342 if (max_benefit < inline_summary (node)->time_inlining_benefit)
1343 max_benefit = inline_summary (node)->time_inlining_benefit;
1345 gcc_assert (in_lto_p
1347 || (profile_info && flag_branch_probabilities));
1348 overall_size = initial_size;
1350 nnodes = cgraph_postorder (order);
1354 "\nDeciding on inlining. Starting with size %i.\n",
1357 for (node = cgraph_nodes; node; node = node->next)
1361 fprintf (dump_file, "\nFlattening functions:\n");
1363 /* In the first pass handle functions to be flattened. Do this with
1364 a priority so none of our later choices will make this impossible. */
1365 for (i = nnodes - 1; i >= 0; i--)
1369 /* Handle nodes to be flattened, but don't update overall unit
1370 size. Calling the incremental inliner here is lame,
1371 a simple worklist should be enough. What should be left
1372 here from the early inliner (if it runs) is cyclic cases.
1373 Ideally when processing callees we stop inlining at the
1374 entry of cycles, possibly cloning that entry point and
1375 try to flatten itself turning it into a self-recursive
1377 if (lookup_attribute ("flatten",
1378 DECL_ATTRIBUTES (node->decl)) != NULL)
1382 "Flattening %s\n", cgraph_node_name (node));
1383 cgraph_flatten (node);
1387 cgraph_decide_inlining_of_small_functions ();
1389 if (flag_inline_functions_called_once)
1392 fprintf (dump_file, "\nDeciding on functions called once:\n");
1394 /* And finally decide what functions are called once. */
1395 for (i = nnodes - 1; i >= 0; i--)
1400 && !node->callers->next_caller
1401 && cgraph_only_called_directly_p (node)
1402 && node->local.inlinable
1403 && node->callers->inline_failed
1404 && node->callers->caller != node
1405 && node->callers->caller->global.inlined_to != node
1406 && !node->callers->call_stmt_cannot_inline_p
1407 && !DECL_EXTERNAL (node->decl)
1408 && !DECL_COMDAT (node->decl))
1410 cgraph_inline_failed_t reason;
1411 old_size = overall_size;
1415 "\nConsidering %s size %i.\n",
1416 cgraph_node_name (node), node->global.size);
1418 " Called once from %s %i insns.\n",
1419 cgraph_node_name (node->callers->caller),
1420 node->callers->caller->global.size);
1423 if (cgraph_check_inline_limits (node->callers->caller, node,
1426 struct cgraph_node *caller = node->callers->caller;
1427 cgraph_mark_inline (node->callers);
1430 " Inlined into %s which now has %i size"
1431 " for a net change of %+i size.\n",
1432 cgraph_node_name (caller),
1433 caller->global.size,
1434 overall_size - old_size);
1440 " Not inlining: %s.\n",
1441 cgraph_inline_failed_string (reason));
1447 /* Free ipa-prop structures if they are no longer needed. */
1448 if (flag_indirect_inlining)
1449 ipa_free_all_structures_after_iinln ();
1453 "\nInlined %i calls, eliminated %i functions, "
1454 "size %i turned to %i size.\n\n",
1455 ncalls_inlined, nfunctions_inlined, initial_size,
1461 /* Return true when N is leaf function. Accept cheap (pure&const) builtins
1462 in leaf functions. */
1464 leaf_node_p (struct cgraph_node *n)
1466 struct cgraph_edge *e;
1467 for (e = n->callees; e; e = e->next_callee)
1468 if (!DECL_BUILT_IN (e->callee->decl)
1469 || (!TREE_READONLY (e->callee->decl)
1470 || DECL_PURE_P (e->callee->decl)))
1475 /* Decide on the inlining. We do so in the topological order to avoid
1476 expenses on updating data structures. */
1479 cgraph_decide_inlining_incrementally (struct cgraph_node *node,
1480 enum inlining_mode mode)
1482 struct cgraph_edge *e;
1483 bool inlined = false;
1484 cgraph_inline_failed_t failed_reason;
1486 #ifdef ENABLE_CHECKING
1487 verify_cgraph_node (node);
1490 if (mode != INLINE_ALWAYS_INLINE && mode != INLINE_SIZE_NORECURSIVE
1491 && lookup_attribute ("flatten", DECL_ATTRIBUTES (node->decl)) != NULL)
1494 fprintf (dump_file, "Incrementally flattening %s\n",
1495 cgraph_node_name (node));
1499 /* First of all look for always inline functions. */
1500 if (mode != INLINE_SIZE_NORECURSIVE)
1501 for (e = node->callees; e; e = e->next_callee)
1503 if (!e->callee->local.disregard_inline_limits
1504 && (mode != INLINE_ALL || !e->callee->local.inlinable))
1506 if (e->call_stmt_cannot_inline_p)
1510 "Considering to always inline inline candidate %s.\n",
1511 cgraph_node_name (e->callee));
1512 if (cgraph_recursive_inlining_p (node, e->callee, &e->inline_failed))
1515 fprintf (dump_file, "Not inlining: recursive call.\n");
1518 if (!tree_can_inline_p (e))
1523 cgraph_inline_failed_string (e->inline_failed));
1526 if (gimple_in_ssa_p (DECL_STRUCT_FUNCTION (node->decl))
1527 != gimple_in_ssa_p (DECL_STRUCT_FUNCTION (e->callee->decl)))
1530 fprintf (dump_file, "Not inlining: SSA form does not match.\n");
1533 if (!e->callee->analyzed)
1537 "Not inlining: Function body no longer available.\n");
1542 fprintf (dump_file, " Inlining %s into %s.\n",
1543 cgraph_node_name (e->callee),
1544 cgraph_node_name (e->caller));
1545 cgraph_mark_inline (e);
1549 /* Now do the automatic inlining. */
1550 if (mode != INLINE_ALL && mode != INLINE_ALWAYS_INLINE
1551 /* Never inline regular functions into always-inline functions
1552 during incremental inlining. */
1553 && !node->local.disregard_inline_limits)
1555 bitmap visited = BITMAP_ALLOC (NULL);
1556 for (e = node->callees; e; e = e->next_callee)
1558 int allowed_growth = 0;
1559 if (!e->callee->local.inlinable
1560 || !e->inline_failed
1561 || e->callee->local.disregard_inline_limits)
1563 /* We are inlining a function to all call-sites in node
1564 or to none. So visit each candidate only once. */
1565 if (!bitmap_set_bit (visited, e->callee->uid))
1568 fprintf (dump_file, "Considering inline candidate %s.\n",
1569 cgraph_node_name (e->callee));
1570 if (cgraph_recursive_inlining_p (node, e->callee, &e->inline_failed))
1573 fprintf (dump_file, "Not inlining: recursive call.\n");
1576 if (gimple_in_ssa_p (DECL_STRUCT_FUNCTION (node->decl))
1577 != gimple_in_ssa_p (DECL_STRUCT_FUNCTION (e->callee->decl)))
1581 "Not inlining: SSA form does not match.\n");
1585 if (cgraph_maybe_hot_edge_p (e) && leaf_node_p (e->callee)
1586 && optimize_function_for_speed_p (cfun))
1587 allowed_growth = PARAM_VALUE (PARAM_EARLY_INLINING_INSNS);
1589 /* When the function body would grow and inlining the function
1590 won't eliminate the need for offline copy of the function,
1592 if (((mode == INLINE_SIZE || mode == INLINE_SIZE_NORECURSIVE)
1593 || (!flag_inline_functions
1594 && !DECL_DECLARED_INLINE_P (e->callee->decl)))
1595 && (cgraph_estimate_size_after_inlining (1, e->caller, e->callee)
1596 > e->caller->global.size + allowed_growth)
1597 && cgraph_estimate_growth (e->callee) > allowed_growth)
1601 "Not inlining: code size would grow by %i.\n",
1602 cgraph_estimate_size_after_inlining (1, e->caller,
1604 - e->caller->global.size);
1607 if (!cgraph_check_inline_limits (node, e->callee, &e->inline_failed,
1609 || e->call_stmt_cannot_inline_p)
1612 fprintf (dump_file, "Not inlining: %s.\n",
1613 cgraph_inline_failed_string (e->inline_failed));
1616 if (!e->callee->analyzed)
1620 "Not inlining: Function body no longer available.\n");
1623 if (!tree_can_inline_p (e))
1627 "Not inlining: %s.",
1628 cgraph_inline_failed_string (e->inline_failed));
1631 if (cgraph_default_inline_p (e->callee, &failed_reason))
1634 fprintf (dump_file, " Inlining %s into %s.\n",
1635 cgraph_node_name (e->callee),
1636 cgraph_node_name (e->caller));
1637 cgraph_mark_inline (e);
1641 BITMAP_FREE (visited);
1646 /* Because inlining might remove no-longer reachable nodes, we need to
1647 keep the array visible to garbage collector to avoid reading collected
1650 static GTY ((length ("nnodes"))) struct cgraph_node **order;
1652 /* Do inlining of small functions. Doing so early helps profiling and other
1653 passes to be somewhat more effective and avoids some code duplication in
1654 later real inlining pass for testcases with very many function calls. */
1656 cgraph_early_inlining (void)
1658 struct cgraph_node *node = cgraph_node (current_function_decl);
1659 unsigned int todo = 0;
1662 if (sorrycount || errorcount)
1667 || !flag_early_inlining)
1669 /* When not optimizing or not inlining inline only always-inline
1671 cgraph_decide_inlining_incrementally (node, INLINE_ALWAYS_INLINE);
1672 timevar_push (TV_INTEGRATION);
1673 todo |= optimize_inline_calls (current_function_decl);
1674 timevar_pop (TV_INTEGRATION);
1678 if (lookup_attribute ("flatten",
1679 DECL_ATTRIBUTES (node->decl)) != NULL)
1683 "Flattening %s\n", cgraph_node_name (node));
1684 cgraph_flatten (node);
1685 timevar_push (TV_INTEGRATION);
1686 todo |= optimize_inline_calls (current_function_decl);
1687 timevar_pop (TV_INTEGRATION);
1689 /* We iterate incremental inlining to get trivial cases of indirect
1691 while (iterations < PARAM_VALUE (PARAM_EARLY_INLINER_MAX_ITERATIONS)
1692 && cgraph_decide_inlining_incrementally (node,
1694 ? INLINE_SIZE_NORECURSIVE
1697 timevar_push (TV_INTEGRATION);
1698 todo |= optimize_inline_calls (current_function_decl);
1700 timevar_pop (TV_INTEGRATION);
1703 fprintf (dump_file, "Iterations: %i\n", iterations);
1706 cfun->always_inline_functions_inlined = true;
1711 struct gimple_opt_pass pass_early_inline =
1715 "einline", /* name */
1717 cgraph_early_inlining, /* execute */
1720 0, /* static_pass_number */
1721 TV_INLINE_HEURISTICS, /* tv_id */
1722 0, /* properties_required */
1723 0, /* properties_provided */
1724 0, /* properties_destroyed */
1725 0, /* todo_flags_start */
1726 TODO_dump_func /* todo_flags_finish */
1730 /* When inlining shall be performed. */
1732 cgraph_gate_ipa_early_inlining (void)
1734 return (flag_early_inlining
1736 && (flag_branch_probabilities || flag_test_coverage
1737 || profile_arc_flag));
1740 /* IPA pass wrapper for early inlining pass. We need to run early inlining
1741 before tree profiling so we have stand alone IPA pass for doing so. */
1742 struct simple_ipa_opt_pass pass_ipa_early_inline =
1746 "einline_ipa", /* name */
1747 cgraph_gate_ipa_early_inlining, /* gate */
1751 0, /* static_pass_number */
1752 TV_INLINE_HEURISTICS, /* tv_id */
1753 0, /* properties_required */
1754 0, /* properties_provided */
1755 0, /* properties_destroyed */
1756 0, /* todo_flags_start */
1757 TODO_dump_cgraph /* todo_flags_finish */
1761 /* See if statement might disappear after inlining. We are not terribly
1762 sophisficated, basically looking for simple abstraction penalty wrappers. */
1765 likely_eliminated_by_inlining_p (gimple stmt)
1767 enum gimple_code code = gimple_code (stmt);
1773 if (gimple_num_ops (stmt) != 2)
1776 /* Casts of parameters, loads from parameters passed by reference
1777 and stores to return value or parameters are probably free after
1779 if (gimple_assign_rhs_code (stmt) == CONVERT_EXPR
1780 || gimple_assign_rhs_code (stmt) == NOP_EXPR
1781 || gimple_assign_rhs_code (stmt) == VIEW_CONVERT_EXPR
1782 || gimple_assign_rhs_class (stmt) == GIMPLE_SINGLE_RHS)
1784 tree rhs = gimple_assign_rhs1 (stmt);
1785 tree lhs = gimple_assign_lhs (stmt);
1786 tree inner_rhs = rhs;
1787 tree inner_lhs = lhs;
1788 bool rhs_free = false;
1789 bool lhs_free = false;
1791 while (handled_component_p (inner_lhs) || TREE_CODE (inner_lhs) == INDIRECT_REF)
1792 inner_lhs = TREE_OPERAND (inner_lhs, 0);
1793 while (handled_component_p (inner_rhs)
1794 || TREE_CODE (inner_rhs) == ADDR_EXPR || TREE_CODE (inner_rhs) == INDIRECT_REF)
1795 inner_rhs = TREE_OPERAND (inner_rhs, 0);
1798 if (TREE_CODE (inner_rhs) == PARM_DECL
1799 || (TREE_CODE (inner_rhs) == SSA_NAME
1800 && SSA_NAME_IS_DEFAULT_DEF (inner_rhs)
1801 && TREE_CODE (SSA_NAME_VAR (inner_rhs)) == PARM_DECL))
1803 if (rhs_free && is_gimple_reg (lhs))
1805 if (((TREE_CODE (inner_lhs) == PARM_DECL
1806 || (TREE_CODE (inner_lhs) == SSA_NAME
1807 && SSA_NAME_IS_DEFAULT_DEF (inner_lhs)
1808 && TREE_CODE (SSA_NAME_VAR (inner_lhs)) == PARM_DECL))
1809 && inner_lhs != lhs)
1810 || TREE_CODE (inner_lhs) == RESULT_DECL
1811 || (TREE_CODE (inner_lhs) == SSA_NAME
1812 && TREE_CODE (SSA_NAME_VAR (inner_lhs)) == RESULT_DECL))
1814 if (lhs_free && (is_gimple_reg (rhs) || is_gimple_min_invariant (rhs)))
1816 if (lhs_free && rhs_free)
1825 /* Compute function body size parameters for NODE. */
1828 estimate_function_body_sizes (struct cgraph_node *node)
1831 gcov_type time_inlining_benefit = 0;
1833 int size_inlining_benefit = 0;
1835 gimple_stmt_iterator bsi;
1836 struct function *my_function = DECL_STRUCT_FUNCTION (node->decl);
1839 tree funtype = TREE_TYPE (node->decl);
1842 fprintf (dump_file, "Analyzing function body size: %s\n",
1843 cgraph_node_name (node));
1845 gcc_assert (my_function && my_function->cfg);
1846 FOR_EACH_BB_FN (bb, my_function)
1848 freq = compute_call_stmt_bb_frequency (node->decl, bb);
1849 for (bsi = gsi_start_bb (bb); !gsi_end_p (bsi); gsi_next (&bsi))
1851 gimple stmt = gsi_stmt (bsi);
1852 int this_size = estimate_num_insns (stmt, &eni_size_weights);
1853 int this_time = estimate_num_insns (stmt, &eni_time_weights);
1855 if (dump_file && (dump_flags & TDF_DETAILS))
1857 fprintf (dump_file, " freq:%6i size:%3i time:%3i ",
1858 freq, this_size, this_time);
1859 print_gimple_stmt (dump_file, stmt, 0, 0);
1864 if (likely_eliminated_by_inlining_p (stmt))
1866 size_inlining_benefit += this_size;
1867 time_inlining_benefit += this_time;
1868 if (dump_file && (dump_flags & TDF_DETAILS))
1869 fprintf (dump_file, " Likely eliminated\n");
1871 gcc_assert (time >= 0);
1872 gcc_assert (size >= 0);
1875 time = (time + CGRAPH_FREQ_BASE / 2) / CGRAPH_FREQ_BASE;
1876 time_inlining_benefit = ((time_inlining_benefit + CGRAPH_FREQ_BASE / 2)
1877 / CGRAPH_FREQ_BASE);
1879 fprintf (dump_file, "Overall function body time: %i-%i size: %i-%i\n",
1880 (int)time, (int)time_inlining_benefit,
1881 size, size_inlining_benefit);
1882 time_inlining_benefit += eni_time_weights.call_cost;
1883 size_inlining_benefit += eni_size_weights.call_cost;
1884 if (!VOID_TYPE_P (TREE_TYPE (funtype)))
1886 int cost = estimate_move_cost (TREE_TYPE (funtype));
1887 time_inlining_benefit += cost;
1888 size_inlining_benefit += cost;
1890 for (arg = DECL_ARGUMENTS (node->decl); arg; arg = TREE_CHAIN (arg))
1891 if (!VOID_TYPE_P (TREE_TYPE (arg)))
1893 int cost = estimate_move_cost (TREE_TYPE (arg));
1894 time_inlining_benefit += cost;
1895 size_inlining_benefit += cost;
1897 if (time_inlining_benefit > MAX_TIME)
1898 time_inlining_benefit = MAX_TIME;
1899 if (time > MAX_TIME)
1901 inline_summary (node)->self_time = time;
1902 inline_summary (node)->self_size = size;
1904 fprintf (dump_file, "With function call overhead time: %i-%i size: %i-%i\n",
1905 (int)time, (int)time_inlining_benefit,
1906 size, size_inlining_benefit);
1907 inline_summary (node)->time_inlining_benefit = time_inlining_benefit;
1908 inline_summary (node)->size_inlining_benefit = size_inlining_benefit;
1911 /* Compute parameters of functions used by inliner. */
1913 compute_inline_parameters (struct cgraph_node *node)
1915 HOST_WIDE_INT self_stack_size;
1917 gcc_assert (!node->global.inlined_to);
1919 /* Estimate the stack size for the function. But not at -O0
1920 because estimated_stack_frame_size is a quadratic problem. */
1921 self_stack_size = optimize ? estimated_stack_frame_size () : 0;
1922 inline_summary (node)->estimated_self_stack_size = self_stack_size;
1923 node->global.estimated_stack_size = self_stack_size;
1924 node->global.stack_frame_offset = 0;
1926 /* Can this function be inlined at all? */
1927 node->local.inlinable = tree_inlinable_function_p (node->decl);
1928 if (node->local.inlinable && !node->local.disregard_inline_limits)
1929 node->local.disregard_inline_limits
1930 = DECL_DISREGARD_INLINE_LIMITS (node->decl);
1931 estimate_function_body_sizes (node);
1932 /* Inlining characteristics are maintained by the cgraph_mark_inline. */
1933 node->global.time = inline_summary (node)->self_time;
1934 node->global.size = inline_summary (node)->self_size;
1939 /* Compute parameters of functions used by inliner using
1940 current_function_decl. */
1942 compute_inline_parameters_for_current (void)
1944 compute_inline_parameters (cgraph_node (current_function_decl));
1948 struct gimple_opt_pass pass_inline_parameters =
1952 "inline_param", /* name */
1954 compute_inline_parameters_for_current,/* execute */
1957 0, /* static_pass_number */
1958 TV_INLINE_HEURISTICS, /* tv_id */
1959 0, /* properties_required */
1960 0, /* properties_provided */
1961 0, /* properties_destroyed */
1962 0, /* todo_flags_start */
1963 0 /* todo_flags_finish */
1967 /* This function performs intraprocedural analyzis in NODE that is required to
1968 inline indirect calls. */
1970 inline_indirect_intraprocedural_analysis (struct cgraph_node *node)
1972 struct cgraph_edge *cs;
1976 ipa_initialize_node_params (node);
1977 ipa_detect_param_modifications (node);
1979 ipa_analyze_params_uses (node);
1982 for (cs = node->callees; cs; cs = cs->next_callee)
1984 ipa_count_arguments (cs);
1985 ipa_compute_jump_functions (cs);
1990 ipa_print_node_params (dump_file, node);
1991 ipa_print_node_jump_functions (dump_file, node);
1995 /* Note function body size. */
1997 analyze_function (struct cgraph_node *node)
1999 push_cfun (DECL_STRUCT_FUNCTION (node->decl));
2000 current_function_decl = node->decl;
2002 compute_inline_parameters (node);
2003 if (flag_indirect_inlining)
2004 inline_indirect_intraprocedural_analysis (node);
2006 current_function_decl = NULL;
2010 /* Called when new function is inserted to callgraph late. */
2012 add_new_function (struct cgraph_node *node, void *data ATTRIBUTE_UNUSED)
2014 analyze_function (node);
2017 /* Note function body size. */
2019 inline_generate_summary (void)
2021 struct cgraph_node *node;
2023 function_insertion_hook_holder =
2024 cgraph_add_function_insertion_hook (&add_new_function, NULL);
2026 if (flag_indirect_inlining)
2028 ipa_register_cgraph_hooks ();
2029 ipa_check_create_node_params ();
2030 ipa_check_create_edge_args ();
2033 for (node = cgraph_nodes; node; node = node->next)
2035 analyze_function (node);
2040 /* Apply inline plan to function. */
2042 inline_transform (struct cgraph_node *node)
2044 unsigned int todo = 0;
2045 struct cgraph_edge *e;
2047 /* FIXME: Currently the passmanager is adding inline transform more than once to some
2048 clones. This needs revisiting after WPA cleanups. */
2049 if (cfun->after_inlining)
2052 /* We might need the body of this function so that we can expand
2053 it inline somewhere else. */
2054 if (cgraph_preserve_function_body_p (node->decl))
2055 save_inline_function_body (node);
2057 for (e = node->callees; e; e = e->next_callee)
2058 if (!e->inline_failed || warn_inline)
2063 timevar_push (TV_INTEGRATION);
2064 todo = optimize_inline_calls (current_function_decl);
2065 timevar_pop (TV_INTEGRATION);
2067 cfun->always_inline_functions_inlined = true;
2068 cfun->after_inlining = true;
2069 return todo | execute_fixup_cfg ();
2072 /* Read inline summary. Jump functions are shared among ipa-cp
2073 and inliner, so when ipa-cp is active, we don't need to write them
2077 inline_read_summary (void)
2079 if (flag_indirect_inlining)
2081 ipa_register_cgraph_hooks ();
2083 ipa_prop_read_jump_functions ();
2085 function_insertion_hook_holder =
2086 cgraph_add_function_insertion_hook (&add_new_function, NULL);
2089 /* Write inline summary for node in SET.
2090 Jump functions are shared among ipa-cp and inliner, so when ipa-cp is
2091 active, we don't need to write them twice. */
2094 inline_write_summary (cgraph_node_set set,
2095 varpool_node_set vset ATTRIBUTE_UNUSED)
2097 if (flag_indirect_inlining && !flag_ipa_cp)
2098 ipa_prop_write_jump_functions (set);
2101 /* When to run IPA inlining. Inlining of always-inline functions
2102 happens during early inlining. */
2105 gate_cgraph_decide_inlining (void)
2107 /* ??? We'd like to skip this if not optimizing or not inlining as
2108 all always-inline functions have been processed by early
2109 inlining already. But this at least breaks EH with C++ as
2110 we need to unconditionally run fixup_cfg even at -O0.
2111 So leave it on unconditionally for now. */
2115 struct ipa_opt_pass_d pass_ipa_inline =
2119 "inline", /* name */
2120 gate_cgraph_decide_inlining, /* gate */
2121 cgraph_decide_inlining, /* execute */
2124 0, /* static_pass_number */
2125 TV_INLINE_HEURISTICS, /* tv_id */
2126 0, /* properties_required */
2127 0, /* properties_provided */
2128 0, /* properties_destroyed */
2129 TODO_remove_functions, /* todo_flags_finish */
2130 TODO_dump_cgraph | TODO_dump_func
2131 | TODO_remove_functions | TODO_ggc_collect /* todo_flags_finish */
2133 inline_generate_summary, /* generate_summary */
2134 inline_write_summary, /* write_summary */
2135 inline_read_summary, /* read_summary */
2136 NULL, /* write_optimization_summary */
2137 NULL, /* read_optimization_summary */
2138 NULL, /* stmt_fixup */
2140 inline_transform, /* function_transform */
2141 NULL, /* variable_transform */
2145 #include "gt-ipa-inline.h"