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->callee->decl,
272 e->count, e->frequency, e->loop_nest,
273 update_original, NULL);
274 cgraph_redirect_edge_callee (e, n);
278 if (e->caller->global.inlined_to)
279 e->callee->global.inlined_to = e->caller->global.inlined_to;
281 e->callee->global.inlined_to = e->caller;
282 e->callee->global.stack_frame_offset
283 = e->caller->global.stack_frame_offset
284 + inline_summary (e->caller)->estimated_self_stack_size;
285 peak = e->callee->global.stack_frame_offset
286 + inline_summary (e->callee)->estimated_self_stack_size;
287 if (e->callee->global.inlined_to->global.estimated_stack_size < peak)
288 e->callee->global.inlined_to->global.estimated_stack_size = peak;
289 cgraph_propagate_frequency (e->callee);
291 /* Recursively clone all bodies. */
292 for (e = e->callee->callees; e; e = e->next_callee)
293 if (!e->inline_failed)
294 cgraph_clone_inlined_nodes (e, duplicate, update_original);
297 /* Mark edge E as inlined and update callgraph accordingly. UPDATE_ORIGINAL
298 specify whether profile of original function should be updated. If any new
299 indirect edges are discovered in the process, add them to NEW_EDGES, unless
300 it is NULL. Return true iff any new callgraph edges were discovered as a
301 result of inlining. */
304 cgraph_mark_inline_edge (struct cgraph_edge *e, bool update_original,
305 VEC (cgraph_edge_p, heap) **new_edges)
307 int old_size = 0, new_size = 0;
308 struct cgraph_node *to = NULL, *what;
309 struct cgraph_edge *curr = e;
312 gcc_assert (e->inline_failed);
313 e->inline_failed = CIF_OK;
314 DECL_POSSIBLY_INLINED (e->callee->decl) = true;
316 cgraph_clone_inlined_nodes (e, true, update_original);
321 /* Now update size of caller and all functions caller is inlined into. */
322 for (;e && !e->inline_failed; e = e->caller->callers)
325 old_size = e->caller->global.size;
326 new_size = cgraph_estimate_size_after_inlining (1, to, what);
327 to->global.size = new_size;
328 to->global.time = cgraph_estimate_time_after_inlining (freq, to, what);
330 gcc_assert (what->global.inlined_to == to);
331 if (new_size > old_size)
332 overall_size += new_size - old_size;
335 if (flag_indirect_inlining)
336 return ipa_propagate_indirect_call_infos (curr, new_edges);
341 /* Mark all calls of EDGE->CALLEE inlined into EDGE->CALLER. */
344 cgraph_mark_inline (struct cgraph_edge *edge)
346 struct cgraph_node *to = edge->caller;
347 struct cgraph_node *what = edge->callee;
348 struct cgraph_edge *e, *next;
350 gcc_assert (!edge->call_stmt_cannot_inline_p);
351 /* Look for all calls, mark them inline and clone recursively
352 all inlined functions. */
353 for (e = what->callers; e; e = next)
355 next = e->next_caller;
356 if (e->caller == to && e->inline_failed)
358 cgraph_mark_inline_edge (e, true, NULL);
365 /* Estimate the growth caused by inlining NODE into all callees. */
368 cgraph_estimate_growth (struct cgraph_node *node)
371 struct cgraph_edge *e;
372 bool self_recursive = false;
374 if (node->global.estimated_growth != INT_MIN)
375 return node->global.estimated_growth;
377 for (e = node->callers; e; e = e->next_caller)
379 if (e->caller == node)
380 self_recursive = true;
381 if (e->inline_failed)
382 growth += (cgraph_estimate_size_after_inlining (1, e->caller, node)
383 - e->caller->global.size);
386 /* ??? Wrong for non-trivially self recursive functions or cases where
387 we decide to not inline for different reasons, but it is not big deal
388 as in that case we will keep the body around, but we will also avoid
390 if (cgraph_only_called_directly_p (node)
391 && !DECL_EXTERNAL (node->decl) && !self_recursive)
392 growth -= node->global.size;
394 node->global.estimated_growth = growth;
398 /* Return false when inlining WHAT into TO is not good idea
399 as it would cause too large growth of function bodies.
400 When ONE_ONLY is true, assume that only one call site is going
401 to be inlined, otherwise figure out how many call sites in
402 TO calls WHAT and verify that all can be inlined.
406 cgraph_check_inline_limits (struct cgraph_node *to, struct cgraph_node *what,
407 cgraph_inline_failed_t *reason, bool one_only)
410 struct cgraph_edge *e;
413 HOST_WIDE_INT stack_size_limit, inlined_stack;
418 for (e = to->callees; e; e = e->next_callee)
419 if (e->callee == what)
422 if (to->global.inlined_to)
423 to = to->global.inlined_to;
425 /* When inlining large function body called once into small function,
426 take the inlined function as base for limiting the growth. */
427 if (inline_summary (to)->self_size > inline_summary(what)->self_size)
428 limit = inline_summary (to)->self_size;
430 limit = inline_summary (what)->self_size;
432 limit += limit * PARAM_VALUE (PARAM_LARGE_FUNCTION_GROWTH) / 100;
434 /* Check the size after inlining against the function limits. But allow
435 the function to shrink if it went over the limits by forced inlining. */
436 newsize = cgraph_estimate_size_after_inlining (times, to, what);
437 if (newsize >= to->global.size
438 && newsize > PARAM_VALUE (PARAM_LARGE_FUNCTION_INSNS)
442 *reason = CIF_LARGE_FUNCTION_GROWTH_LIMIT;
446 stack_size_limit = inline_summary (to)->estimated_self_stack_size;
448 stack_size_limit += stack_size_limit * PARAM_VALUE (PARAM_STACK_FRAME_GROWTH) / 100;
450 inlined_stack = (to->global.stack_frame_offset
451 + inline_summary (to)->estimated_self_stack_size
452 + what->global.estimated_stack_size);
453 if (inlined_stack > stack_size_limit
454 && inlined_stack > PARAM_VALUE (PARAM_LARGE_STACK_FRAME))
457 *reason = CIF_LARGE_STACK_FRAME_GROWTH_LIMIT;
463 /* Return true when function N is small enough to be inlined. */
466 cgraph_default_inline_p (struct cgraph_node *n, cgraph_inline_failed_t *reason)
470 if (n->local.disregard_inline_limits)
473 if (!flag_inline_small_functions && !DECL_DECLARED_INLINE_P (decl))
476 *reason = CIF_FUNCTION_NOT_INLINE_CANDIDATE;
483 *reason = CIF_BODY_NOT_AVAILABLE;
487 if (DECL_DECLARED_INLINE_P (decl))
489 if (n->global.size >= MAX_INLINE_INSNS_SINGLE)
492 *reason = CIF_MAX_INLINE_INSNS_SINGLE_LIMIT;
498 if (n->global.size >= MAX_INLINE_INSNS_AUTO)
501 *reason = CIF_MAX_INLINE_INSNS_AUTO_LIMIT;
509 /* Return true when inlining WHAT would create recursive inlining.
510 We call recursive inlining all cases where same function appears more than
511 once in the single recursion nest path in the inline graph. */
514 cgraph_recursive_inlining_p (struct cgraph_node *to,
515 struct cgraph_node *what,
516 cgraph_inline_failed_t *reason)
519 if (to->global.inlined_to)
520 recursive = what->decl == to->global.inlined_to->decl;
522 recursive = what->decl == to->decl;
523 /* Marking recursive function inline has sane semantic and thus we should
525 if (recursive && reason)
526 *reason = (what->local.disregard_inline_limits
527 ? CIF_RECURSIVE_INLINING : CIF_UNSPECIFIED);
531 /* A cost model driving the inlining heuristics in a way so the edges with
532 smallest badness are inlined first. After each inlining is performed
533 the costs of all caller edges of nodes affected are recomputed so the
534 metrics may accurately depend on values such as number of inlinable callers
535 of the function or function body size. */
538 cgraph_edge_badness (struct cgraph_edge *edge, bool dump)
542 (cgraph_estimate_size_after_inlining (1, edge->caller, edge->callee)
543 - edge->caller->global.size);
545 if (edge->callee->local.disregard_inline_limits)
550 fprintf (dump_file, " Badness calculcation for %s -> %s\n",
551 cgraph_node_name (edge->caller),
552 cgraph_node_name (edge->callee));
553 fprintf (dump_file, " growth %i, time %i-%i, size %i-%i\n",
555 edge->callee->global.time,
556 inline_summary (edge->callee)->time_inlining_benefit,
557 edge->callee->global.size,
558 inline_summary (edge->callee)->size_inlining_benefit);
561 /* Always prefer inlining saving code size. */
564 badness = INT_MIN - growth;
566 fprintf (dump_file, " %i: Growth %i < 0\n", (int) badness,
570 /* When profiling is available, base priorities -(#calls / growth).
571 So we optimize for overall number of "executed" inlined calls. */
576 ((double) edge->count * INT_MIN / max_count / (max_benefit + 1)) *
577 (inline_summary (edge->callee)->time_inlining_benefit + 1)) / growth;
581 " %i (relative %f): profile info. Relative count %f"
582 " * Relative benefit %f\n",
583 (int) badness, (double) badness / INT_MIN,
584 (double) edge->count / max_count,
585 (double) (inline_summary (edge->callee)->
586 time_inlining_benefit + 1) / (max_benefit + 1));
590 /* When function local profile is available, base priorities on
591 growth / frequency, so we optimize for overall frequency of inlined
592 calls. This is not too accurate since while the call might be frequent
593 within function, the function itself is infrequent.
595 Other objective to optimize for is number of different calls inlined.
596 We add the estimated growth after inlining all functions to bias the
597 priorities slightly in this direction (so fewer times called functions
598 of the same size gets priority). */
599 else if (flag_guess_branch_prob)
601 int div = edge->frequency * 100 / CGRAPH_FREQ_BASE + 1;
604 badness = growth * 10000;
606 MIN (100 * inline_summary (edge->callee)->time_inlining_benefit /
607 (edge->callee->global.time + 1) +1, 100);
611 /* Decrease badness if call is nested. */
612 /* Compress the range so we don't overflow. */
614 div = 10000 + ceil_log2 (div) - 8;
619 growth_for_all = cgraph_estimate_growth (edge->callee);
620 badness += growth_for_all;
621 if (badness > INT_MAX)
626 " %i: guessed profile. frequency %i, overall growth %i,"
627 " benefit %i%%, divisor %i\n",
628 (int) badness, edge->frequency, growth_for_all, benefitperc, div);
631 /* When function local profile is not available or it does not give
632 useful information (ie frequency is zero), base the cost on
633 loop nest and overall size growth, so we optimize for overall number
634 of functions fully inlined in program. */
637 int nest = MIN (edge->loop_nest, 8);
638 badness = cgraph_estimate_growth (edge->callee) * 256;
640 /* Decrease badness if call is nested. */
648 fprintf (dump_file, " %i: no profile. nest %i\n", (int) badness,
652 /* Ensure that we did not overflow in all the fixed point math above. */
653 gcc_assert (badness >= INT_MIN);
654 gcc_assert (badness <= INT_MAX - 1);
655 /* Make recursive inlining happen always after other inlining is done. */
656 if (cgraph_recursive_inlining_p (edge->caller, edge->callee, NULL))
662 /* Recompute heap nodes for each of caller edge. */
665 update_caller_keys (fibheap_t heap, struct cgraph_node *node,
666 bitmap updated_nodes)
668 struct cgraph_edge *edge;
669 cgraph_inline_failed_t failed_reason;
671 if (!node->local.inlinable
672 || node->global.inlined_to)
674 if (bitmap_bit_p (updated_nodes, node->uid))
676 bitmap_set_bit (updated_nodes, node->uid);
677 node->global.estimated_growth = INT_MIN;
679 if (!node->local.inlinable)
681 /* Prune out edges we won't inline into anymore. */
682 if (!cgraph_default_inline_p (node, &failed_reason))
684 for (edge = node->callers; edge; edge = edge->next_caller)
687 fibheap_delete_node (heap, (fibnode_t) edge->aux);
689 if (edge->inline_failed)
690 edge->inline_failed = failed_reason;
695 for (edge = node->callers; edge; edge = edge->next_caller)
696 if (edge->inline_failed)
698 int badness = cgraph_edge_badness (edge, false);
701 fibnode_t n = (fibnode_t) edge->aux;
702 gcc_assert (n->data == edge);
703 if (n->key == badness)
706 /* fibheap_replace_key only increase the keys. */
707 if (badness < n->key)
709 fibheap_replace_key (heap, n, badness);
710 gcc_assert (n->key == badness);
713 fibheap_delete_node (heap, (fibnode_t) edge->aux);
715 edge->aux = fibheap_insert (heap, badness, edge);
719 /* Recompute heap nodes for each of caller edges of each of callees. */
722 update_callee_keys (fibheap_t heap, struct cgraph_node *node,
723 bitmap updated_nodes)
725 struct cgraph_edge *e;
726 node->global.estimated_growth = INT_MIN;
728 for (e = node->callees; e; e = e->next_callee)
729 if (e->inline_failed)
730 update_caller_keys (heap, e->callee, updated_nodes);
731 else if (!e->inline_failed)
732 update_callee_keys (heap, e->callee, updated_nodes);
735 /* Enqueue all recursive calls from NODE into priority queue depending on
736 how likely we want to recursively inline the call. */
739 lookup_recursive_calls (struct cgraph_node *node, struct cgraph_node *where,
743 struct cgraph_edge *e;
744 for (e = where->callees; e; e = e->next_callee)
745 if (e->callee == node)
747 /* When profile feedback is available, prioritize by expected number
748 of calls. Without profile feedback we maintain simple queue
749 to order candidates via recursive depths. */
750 fibheap_insert (heap,
751 !max_count ? priority++
752 : -(e->count / ((max_count + (1<<24) - 1) / (1<<24))),
755 for (e = where->callees; e; e = e->next_callee)
756 if (!e->inline_failed)
757 lookup_recursive_calls (node, e->callee, heap);
760 /* Decide on recursive inlining: in the case function has recursive calls,
761 inline until body size reaches given argument. If any new indirect edges
762 are discovered in the process, add them to *NEW_EDGES, unless NEW_EDGES
766 cgraph_decide_recursive_inlining (struct cgraph_node *node,
767 VEC (cgraph_edge_p, heap) **new_edges)
769 int limit = PARAM_VALUE (PARAM_MAX_INLINE_INSNS_RECURSIVE_AUTO);
770 int max_depth = PARAM_VALUE (PARAM_MAX_INLINE_RECURSIVE_DEPTH_AUTO);
771 int probability = PARAM_VALUE (PARAM_MIN_INLINE_RECURSIVE_PROBABILITY);
773 struct cgraph_edge *e;
774 struct cgraph_node *master_clone, *next;
778 /* It does not make sense to recursively inline always-inline functions
779 as we are going to sorry() on the remaining calls anyway. */
780 if (node->local.disregard_inline_limits
781 && lookup_attribute ("always_inline", DECL_ATTRIBUTES (node->decl)))
784 if (optimize_function_for_size_p (DECL_STRUCT_FUNCTION (node->decl))
785 || (!flag_inline_functions && !DECL_DECLARED_INLINE_P (node->decl)))
788 if (DECL_DECLARED_INLINE_P (node->decl))
790 limit = PARAM_VALUE (PARAM_MAX_INLINE_INSNS_RECURSIVE);
791 max_depth = PARAM_VALUE (PARAM_MAX_INLINE_RECURSIVE_DEPTH);
794 /* Make sure that function is small enough to be considered for inlining. */
796 || cgraph_estimate_size_after_inlining (1, node, node) >= limit)
798 heap = fibheap_new ();
799 lookup_recursive_calls (node, node, heap);
800 if (fibheap_empty (heap))
802 fibheap_delete (heap);
808 " Performing recursive inlining on %s\n",
809 cgraph_node_name (node));
811 /* We need original clone to copy around. */
812 master_clone = cgraph_clone_node (node, node->decl,
813 node->count, CGRAPH_FREQ_BASE, 1,
815 master_clone->needed = true;
816 for (e = master_clone->callees; e; e = e->next_callee)
817 if (!e->inline_failed)
818 cgraph_clone_inlined_nodes (e, true, false);
820 /* Do the inlining and update list of recursive call during process. */
821 while (!fibheap_empty (heap)
822 && (cgraph_estimate_size_after_inlining (1, node, master_clone)
825 struct cgraph_edge *curr
826 = (struct cgraph_edge *) fibheap_extract_min (heap);
827 struct cgraph_node *cnode;
830 for (cnode = curr->caller;
831 cnode->global.inlined_to; cnode = cnode->callers->caller)
832 if (node->decl == curr->callee->decl)
834 if (depth > max_depth)
838 " maximal depth reached\n");
844 if (!cgraph_maybe_hot_edge_p (curr))
847 fprintf (dump_file, " Not inlining cold call\n");
850 if (curr->count * 100 / node->count < probability)
854 " Probability of edge is too small\n");
862 " Inlining call of depth %i", depth);
865 fprintf (dump_file, " called approx. %.2f times per call",
866 (double)curr->count / node->count);
868 fprintf (dump_file, "\n");
870 cgraph_redirect_edge_callee (curr, master_clone);
871 cgraph_mark_inline_edge (curr, false, new_edges);
872 lookup_recursive_calls (node, curr->callee, heap);
875 if (!fibheap_empty (heap) && dump_file)
876 fprintf (dump_file, " Recursive inlining growth limit met.\n");
878 fibheap_delete (heap);
881 "\n Inlined %i times, body grown from size %i to %i, time %i to %i\n", n,
882 master_clone->global.size, node->global.size,
883 master_clone->global.time, node->global.time);
885 /* Remove master clone we used for inlining. We rely that clones inlined
886 into master clone gets queued just before master clone so we don't
888 for (node = cgraph_nodes; node != master_clone;
892 if (node->global.inlined_to == master_clone)
893 cgraph_remove_node (node);
895 cgraph_remove_node (master_clone);
896 /* FIXME: Recursive inlining actually reduces number of calls of the
897 function. At this place we should probably walk the function and
898 inline clones and compensate the counts accordingly. This probably
899 doesn't matter much in practice. */
903 /* Set inline_failed for all callers of given function to REASON. */
906 cgraph_set_inline_failed (struct cgraph_node *node,
907 cgraph_inline_failed_t reason)
909 struct cgraph_edge *e;
912 fprintf (dump_file, "Inlining failed: %s\n",
913 cgraph_inline_failed_string (reason));
914 for (e = node->callers; e; e = e->next_caller)
915 if (e->inline_failed)
916 e->inline_failed = reason;
919 /* Given whole compilation unit estimate of INSNS, compute how large we can
920 allow the unit to grow. */
922 compute_max_insns (int insns)
924 int max_insns = insns;
925 if (max_insns < PARAM_VALUE (PARAM_LARGE_UNIT_INSNS))
926 max_insns = PARAM_VALUE (PARAM_LARGE_UNIT_INSNS);
928 return ((HOST_WIDEST_INT) max_insns
929 * (100 + PARAM_VALUE (PARAM_INLINE_UNIT_GROWTH)) / 100);
932 /* Compute badness of all edges in NEW_EDGES and add them to the HEAP. */
934 add_new_edges_to_heap (fibheap_t heap, VEC (cgraph_edge_p, heap) *new_edges)
936 while (VEC_length (cgraph_edge_p, new_edges) > 0)
938 struct cgraph_edge *edge = VEC_pop (cgraph_edge_p, new_edges);
940 gcc_assert (!edge->aux);
941 edge->aux = fibheap_insert (heap, cgraph_edge_badness (edge, false), edge);
946 /* We use greedy algorithm for inlining of small functions:
947 All inline candidates are put into prioritized heap based on estimated
948 growth of the overall number of instructions and then update the estimates.
950 INLINED and INLINED_CALEES are just pointers to arrays large enough
951 to be passed to cgraph_inlined_into and cgraph_inlined_callees. */
954 cgraph_decide_inlining_of_small_functions (void)
956 struct cgraph_node *node;
957 struct cgraph_edge *edge;
958 cgraph_inline_failed_t failed_reason;
959 fibheap_t heap = fibheap_new ();
960 bitmap updated_nodes = BITMAP_ALLOC (NULL);
961 int min_size, max_size;
962 VEC (cgraph_edge_p, heap) *new_indirect_edges = NULL;
964 if (flag_indirect_inlining)
965 new_indirect_edges = VEC_alloc (cgraph_edge_p, heap, 8);
968 fprintf (dump_file, "\nDeciding on smaller functions:\n");
970 /* Put all inline candidates into the heap. */
972 for (node = cgraph_nodes; node; node = node->next)
974 if (!node->local.inlinable || !node->callers)
977 fprintf (dump_file, "Considering inline candidate %s.\n", cgraph_node_name (node));
979 node->global.estimated_growth = INT_MIN;
980 if (!cgraph_default_inline_p (node, &failed_reason))
982 cgraph_set_inline_failed (node, failed_reason);
986 for (edge = node->callers; edge; edge = edge->next_caller)
987 if (edge->inline_failed)
989 gcc_assert (!edge->aux);
990 edge->aux = fibheap_insert (heap, cgraph_edge_badness (edge, false), edge);
994 max_size = compute_max_insns (overall_size);
995 min_size = overall_size;
997 while (overall_size <= max_size
998 && !fibheap_empty (heap))
1000 int old_size = overall_size;
1001 struct cgraph_node *where, *callee;
1002 int badness = fibheap_min_key (heap);
1004 cgraph_inline_failed_t not_good = CIF_OK;
1006 edge = (struct cgraph_edge *) fibheap_extract_min (heap);
1007 gcc_assert (edge->aux);
1009 if (!edge->inline_failed)
1011 #ifdef ENABLE_CHECKING
1012 gcc_assert (cgraph_edge_badness (edge, false) == badness);
1014 callee = edge->callee;
1016 growth = (cgraph_estimate_size_after_inlining (1, edge->caller, edge->callee)
1017 - edge->caller->global.size);
1022 "\nConsidering %s with %i size\n",
1023 cgraph_node_name (edge->callee),
1024 edge->callee->global.size);
1026 " to be inlined into %s in %s:%i\n"
1027 " Estimated growth after inlined into all callees is %+i insns.\n"
1028 " Estimated badness is %i, frequency %.2f.\n",
1029 cgraph_node_name (edge->caller),
1030 flag_wpa ? "unknown"
1031 : gimple_filename ((const_gimple) edge->call_stmt),
1032 flag_wpa ? -1 : gimple_lineno ((const_gimple) edge->call_stmt),
1033 cgraph_estimate_growth (edge->callee),
1035 edge->frequency / (double)CGRAPH_FREQ_BASE);
1037 fprintf (dump_file," Called "HOST_WIDEST_INT_PRINT_DEC"x\n", edge->count);
1038 if (dump_flags & TDF_DETAILS)
1039 cgraph_edge_badness (edge, true);
1042 /* When not having profile info ready we don't weight by any way the
1043 position of call in procedure itself. This means if call of
1044 function A from function B seems profitable to inline, the recursive
1045 call of function A in inline copy of A in B will look profitable too
1046 and we end up inlining until reaching maximal function growth. This
1047 is not good idea so prohibit the recursive inlining.
1049 ??? When the frequencies are taken into account we might not need this
1052 We need to be cureful here, in some testcases, e.g. directivec.c in
1053 libcpp, we can estimate self recursive function to have negative growth
1054 for inlining completely.
1058 where = edge->caller;
1059 while (where->global.inlined_to)
1061 if (where->decl == edge->callee->decl)
1063 where = where->callers->caller;
1065 if (where->global.inlined_to)
1068 = (edge->callee->local.disregard_inline_limits
1069 ? CIF_RECURSIVE_INLINING : CIF_UNSPECIFIED);
1071 fprintf (dump_file, " inline_failed:Recursive inlining performed only for function itself.\n");
1076 if (edge->callee->local.disregard_inline_limits)
1078 else if (!cgraph_maybe_hot_edge_p (edge))
1079 not_good = CIF_UNLIKELY_CALL;
1080 else if (!flag_inline_functions
1081 && !DECL_DECLARED_INLINE_P (edge->callee->decl))
1082 not_good = CIF_NOT_DECLARED_INLINED;
1083 else if (optimize_function_for_size_p (DECL_STRUCT_FUNCTION(edge->caller->decl)))
1084 not_good = CIF_OPTIMIZING_FOR_SIZE;
1085 if (not_good && growth > 0 && cgraph_estimate_growth (edge->callee) > 0)
1087 if (!cgraph_recursive_inlining_p (edge->caller, edge->callee,
1088 &edge->inline_failed))
1090 edge->inline_failed = not_good;
1092 fprintf (dump_file, " inline_failed:%s.\n",
1093 cgraph_inline_failed_string (edge->inline_failed));
1097 if (!cgraph_default_inline_p (edge->callee, &edge->inline_failed))
1099 if (!cgraph_recursive_inlining_p (edge->caller, edge->callee,
1100 &edge->inline_failed))
1103 fprintf (dump_file, " inline_failed:%s.\n",
1104 cgraph_inline_failed_string (edge->inline_failed));
1108 if (!tree_can_inline_p (edge))
1111 fprintf (dump_file, " inline_failed:%s.\n",
1112 cgraph_inline_failed_string (edge->inline_failed));
1115 if (cgraph_recursive_inlining_p (edge->caller, edge->callee,
1116 &edge->inline_failed))
1118 where = edge->caller;
1119 if (where->global.inlined_to)
1120 where = where->global.inlined_to;
1121 if (!cgraph_decide_recursive_inlining (where,
1122 flag_indirect_inlining
1123 ? &new_indirect_edges : NULL))
1125 if (flag_indirect_inlining)
1126 add_new_edges_to_heap (heap, new_indirect_edges);
1127 update_callee_keys (heap, where, updated_nodes);
1131 struct cgraph_node *callee;
1132 if (edge->call_stmt_cannot_inline_p
1133 || !cgraph_check_inline_limits (edge->caller, edge->callee,
1134 &edge->inline_failed, true))
1137 fprintf (dump_file, " Not inlining into %s:%s.\n",
1138 cgraph_node_name (edge->caller),
1139 cgraph_inline_failed_string (edge->inline_failed));
1142 callee = edge->callee;
1143 cgraph_mark_inline_edge (edge, true, &new_indirect_edges);
1144 if (flag_indirect_inlining)
1145 add_new_edges_to_heap (heap, new_indirect_edges);
1147 update_callee_keys (heap, callee, updated_nodes);
1149 where = edge->caller;
1150 if (where->global.inlined_to)
1151 where = where->global.inlined_to;
1153 /* Our profitability metric can depend on local properties
1154 such as number of inlinable calls and size of the function body.
1155 After inlining these properties might change for the function we
1156 inlined into (since it's body size changed) and for the functions
1157 called by function we inlined (since number of it inlinable callers
1159 update_caller_keys (heap, where, updated_nodes);
1161 /* We removed one call of the function we just inlined. If offline
1162 copy is still needed, be sure to update the keys. */
1163 if (callee != where && !callee->global.inlined_to)
1164 update_caller_keys (heap, callee, updated_nodes);
1165 bitmap_clear (updated_nodes);
1170 " Inlined into %s which now has size %i and self time %i,"
1171 "net change of %+i.\n",
1172 cgraph_node_name (edge->caller),
1173 edge->caller->global.time,
1174 edge->caller->global.size,
1175 overall_size - old_size);
1177 if (min_size > overall_size)
1179 min_size = overall_size;
1180 max_size = compute_max_insns (min_size);
1183 fprintf (dump_file, "New minimal size reached: %i\n", min_size);
1186 while (!fibheap_empty (heap))
1188 int badness = fibheap_min_key (heap);
1190 edge = (struct cgraph_edge *) fibheap_extract_min (heap);
1191 gcc_assert (edge->aux);
1193 if (!edge->inline_failed)
1195 #ifdef ENABLE_CHECKING
1196 gcc_assert (cgraph_edge_badness (edge, false) == badness);
1201 "\nSkipping %s with %i size\n",
1202 cgraph_node_name (edge->callee),
1203 edge->callee->global.size);
1205 " called by %s in %s:%i\n"
1206 " Estimated growth after inlined into all callees is %+i insns.\n"
1207 " Estimated badness is %i, frequency %.2f.\n",
1208 cgraph_node_name (edge->caller),
1209 flag_wpa ? "unknown"
1210 : gimple_filename ((const_gimple) edge->call_stmt),
1211 flag_wpa ? -1 : gimple_lineno ((const_gimple) edge->call_stmt),
1212 cgraph_estimate_growth (edge->callee),
1214 edge->frequency / (double)CGRAPH_FREQ_BASE);
1216 fprintf (dump_file," Called "HOST_WIDEST_INT_PRINT_DEC"x\n", edge->count);
1217 if (dump_flags & TDF_DETAILS)
1218 cgraph_edge_badness (edge, true);
1220 if (!edge->callee->local.disregard_inline_limits && edge->inline_failed
1221 && !cgraph_recursive_inlining_p (edge->caller, edge->callee,
1222 &edge->inline_failed))
1223 edge->inline_failed = CIF_INLINE_UNIT_GROWTH_LIMIT;
1226 if (new_indirect_edges)
1227 VEC_free (cgraph_edge_p, heap, new_indirect_edges);
1228 fibheap_delete (heap);
1229 BITMAP_FREE (updated_nodes);
1232 /* Flatten NODE from the IPA inliner. */
1235 cgraph_flatten (struct cgraph_node *node)
1237 struct cgraph_edge *e;
1239 /* We shouldn't be called recursively when we are being processed. */
1240 gcc_assert (node->aux == NULL);
1242 node->aux = (void *)(size_t) INLINE_ALL;
1244 for (e = node->callees; e; e = e->next_callee)
1246 struct cgraph_node *orig_callee;
1248 if (e->call_stmt_cannot_inline_p)
1251 if (!e->callee->analyzed)
1255 "Not inlining: Function body not available.\n");
1259 /* We've hit cycle? It is time to give up. */
1264 "Not inlining %s into %s to avoid cycle.\n",
1265 cgraph_node_name (e->callee),
1266 cgraph_node_name (e->caller));
1267 e->inline_failed = CIF_RECURSIVE_INLINING;
1271 /* When the edge is already inlined, we just need to recurse into
1272 it in order to fully flatten the leaves. */
1273 if (!e->inline_failed)
1275 cgraph_flatten (e->callee);
1279 if (cgraph_recursive_inlining_p (node, e->callee, &e->inline_failed))
1282 fprintf (dump_file, "Not inlining: recursive call.\n");
1286 if (!tree_can_inline_p (e))
1289 fprintf (dump_file, "Not inlining: %s",
1290 cgraph_inline_failed_string (e->inline_failed));
1294 /* Inline the edge and flatten the inline clone. Avoid
1295 recursing through the original node if the node was cloned. */
1297 fprintf (dump_file, " Inlining %s into %s.\n",
1298 cgraph_node_name (e->callee),
1299 cgraph_node_name (e->caller));
1300 orig_callee = e->callee;
1301 cgraph_mark_inline_edge (e, true, NULL);
1302 if (e->callee != orig_callee)
1303 orig_callee->aux = (void *)(size_t) INLINE_ALL;
1304 cgraph_flatten (e->callee);
1305 if (e->callee != orig_callee)
1306 orig_callee->aux = NULL;
1312 /* Decide on the inlining. We do so in the topological order to avoid
1313 expenses on updating data structures. */
1316 cgraph_decide_inlining (void)
1318 struct cgraph_node *node;
1320 struct cgraph_node **order =
1321 XCNEWVEC (struct cgraph_node *, cgraph_n_nodes);
1324 int initial_size = 0;
1326 cgraph_remove_function_insertion_hook (function_insertion_hook_holder);
1327 if (in_lto_p && flag_indirect_inlining)
1328 ipa_update_after_lto_read ();
1329 if (flag_indirect_inlining)
1330 ipa_create_all_structures_for_iinln ();
1334 for (node = cgraph_nodes; node; node = node->next)
1337 struct cgraph_edge *e;
1339 gcc_assert (inline_summary (node)->self_size == node->global.size);
1340 initial_size += node->global.size;
1341 for (e = node->callees; e; e = e->next_callee)
1342 if (max_count < e->count)
1343 max_count = e->count;
1344 if (max_benefit < inline_summary (node)->time_inlining_benefit)
1345 max_benefit = inline_summary (node)->time_inlining_benefit;
1347 gcc_assert (in_lto_p
1349 || (profile_info && flag_branch_probabilities));
1350 overall_size = initial_size;
1352 nnodes = cgraph_postorder (order);
1356 "\nDeciding on inlining. Starting with size %i.\n",
1359 for (node = cgraph_nodes; node; node = node->next)
1363 fprintf (dump_file, "\nFlattening functions:\n");
1365 /* In the first pass handle functions to be flattened. Do this with
1366 a priority so none of our later choices will make this impossible. */
1367 for (i = nnodes - 1; i >= 0; i--)
1371 /* Handle nodes to be flattened, but don't update overall unit
1372 size. Calling the incremental inliner here is lame,
1373 a simple worklist should be enough. What should be left
1374 here from the early inliner (if it runs) is cyclic cases.
1375 Ideally when processing callees we stop inlining at the
1376 entry of cycles, possibly cloning that entry point and
1377 try to flatten itself turning it into a self-recursive
1379 if (lookup_attribute ("flatten",
1380 DECL_ATTRIBUTES (node->decl)) != NULL)
1384 "Flattening %s\n", cgraph_node_name (node));
1385 cgraph_flatten (node);
1389 cgraph_decide_inlining_of_small_functions ();
1391 if (flag_inline_functions_called_once)
1394 fprintf (dump_file, "\nDeciding on functions called once:\n");
1396 /* And finally decide what functions are called once. */
1397 for (i = nnodes - 1; i >= 0; i--)
1402 && !node->callers->next_caller
1403 && cgraph_only_called_directly_p (node)
1404 && node->local.inlinable
1405 && node->callers->inline_failed
1406 && node->callers->caller != node
1407 && node->callers->caller->global.inlined_to != node
1408 && !node->callers->call_stmt_cannot_inline_p
1409 && !DECL_EXTERNAL (node->decl)
1410 && !DECL_COMDAT (node->decl))
1412 cgraph_inline_failed_t reason;
1413 old_size = overall_size;
1417 "\nConsidering %s size %i.\n",
1418 cgraph_node_name (node), node->global.size);
1420 " Called once from %s %i insns.\n",
1421 cgraph_node_name (node->callers->caller),
1422 node->callers->caller->global.size);
1425 if (cgraph_check_inline_limits (node->callers->caller, node,
1428 struct cgraph_node *caller = node->callers->caller;
1429 cgraph_mark_inline (node->callers);
1432 " Inlined into %s which now has %i size"
1433 " for a net change of %+i size.\n",
1434 cgraph_node_name (caller),
1435 caller->global.size,
1436 overall_size - old_size);
1442 " Not inlining: %s.\n",
1443 cgraph_inline_failed_string (reason));
1449 /* Free ipa-prop structures if they are no longer needed. */
1450 if (flag_indirect_inlining)
1451 ipa_free_all_structures_after_iinln ();
1455 "\nInlined %i calls, eliminated %i functions, "
1456 "size %i turned to %i size.\n\n",
1457 ncalls_inlined, nfunctions_inlined, initial_size,
1463 /* Return true when N is leaf function. Accept cheap (pure&const) builtins
1464 in leaf functions. */
1466 leaf_node_p (struct cgraph_node *n)
1468 struct cgraph_edge *e;
1469 for (e = n->callees; e; e = e->next_callee)
1470 if (!DECL_BUILT_IN (e->callee->decl)
1471 || (!TREE_READONLY (e->callee->decl)
1472 || DECL_PURE_P (e->callee->decl)))
1477 /* Decide on the inlining. We do so in the topological order to avoid
1478 expenses on updating data structures. */
1481 cgraph_decide_inlining_incrementally (struct cgraph_node *node,
1482 enum inlining_mode mode)
1484 struct cgraph_edge *e;
1485 bool inlined = false;
1486 cgraph_inline_failed_t failed_reason;
1488 #ifdef ENABLE_CHECKING
1489 verify_cgraph_node (node);
1492 if (mode != INLINE_ALWAYS_INLINE && mode != INLINE_SIZE_NORECURSIVE
1493 && lookup_attribute ("flatten", DECL_ATTRIBUTES (node->decl)) != NULL)
1496 fprintf (dump_file, "Incrementally flattening %s\n",
1497 cgraph_node_name (node));
1501 /* First of all look for always inline functions. */
1502 if (mode != INLINE_SIZE_NORECURSIVE)
1503 for (e = node->callees; e; e = e->next_callee)
1505 if (!e->callee->local.disregard_inline_limits
1506 && (mode != INLINE_ALL || !e->callee->local.inlinable))
1508 if (e->call_stmt_cannot_inline_p)
1512 "Considering to always inline inline candidate %s.\n",
1513 cgraph_node_name (e->callee));
1514 if (cgraph_recursive_inlining_p (node, e->callee, &e->inline_failed))
1517 fprintf (dump_file, "Not inlining: recursive call.\n");
1520 if (!tree_can_inline_p (e))
1525 cgraph_inline_failed_string (e->inline_failed));
1528 if (gimple_in_ssa_p (DECL_STRUCT_FUNCTION (node->decl))
1529 != gimple_in_ssa_p (DECL_STRUCT_FUNCTION (e->callee->decl)))
1532 fprintf (dump_file, "Not inlining: SSA form does not match.\n");
1535 if (!e->callee->analyzed)
1539 "Not inlining: Function body no longer available.\n");
1544 fprintf (dump_file, " Inlining %s into %s.\n",
1545 cgraph_node_name (e->callee),
1546 cgraph_node_name (e->caller));
1547 cgraph_mark_inline (e);
1551 /* Now do the automatic inlining. */
1552 if (mode != INLINE_ALL && mode != INLINE_ALWAYS_INLINE
1553 /* Never inline regular functions into always-inline functions
1554 during incremental inlining. */
1555 && !node->local.disregard_inline_limits)
1557 bitmap visited = BITMAP_ALLOC (NULL);
1558 for (e = node->callees; e; e = e->next_callee)
1560 int allowed_growth = 0;
1561 if (!e->callee->local.inlinable
1562 || !e->inline_failed
1563 || e->callee->local.disregard_inline_limits)
1565 /* We are inlining a function to all call-sites in node
1566 or to none. So visit each candidate only once. */
1567 if (!bitmap_set_bit (visited, e->callee->uid))
1570 fprintf (dump_file, "Considering inline candidate %s.\n",
1571 cgraph_node_name (e->callee));
1572 if (cgraph_recursive_inlining_p (node, e->callee, &e->inline_failed))
1575 fprintf (dump_file, "Not inlining: recursive call.\n");
1578 if (gimple_in_ssa_p (DECL_STRUCT_FUNCTION (node->decl))
1579 != gimple_in_ssa_p (DECL_STRUCT_FUNCTION (e->callee->decl)))
1583 "Not inlining: SSA form does not match.\n");
1587 if (cgraph_maybe_hot_edge_p (e) && leaf_node_p (e->callee)
1588 && optimize_function_for_speed_p (cfun))
1589 allowed_growth = PARAM_VALUE (PARAM_EARLY_INLINING_INSNS);
1591 /* When the function body would grow and inlining the function
1592 won't eliminate the need for offline copy of the function,
1594 if (((mode == INLINE_SIZE || mode == INLINE_SIZE_NORECURSIVE)
1595 || (!flag_inline_functions
1596 && !DECL_DECLARED_INLINE_P (e->callee->decl)))
1597 && (cgraph_estimate_size_after_inlining (1, e->caller, e->callee)
1598 > e->caller->global.size + allowed_growth)
1599 && cgraph_estimate_growth (e->callee) > allowed_growth)
1603 "Not inlining: code size would grow by %i.\n",
1604 cgraph_estimate_size_after_inlining (1, e->caller,
1606 - e->caller->global.size);
1609 if (!cgraph_check_inline_limits (node, e->callee, &e->inline_failed,
1611 || e->call_stmt_cannot_inline_p)
1614 fprintf (dump_file, "Not inlining: %s.\n",
1615 cgraph_inline_failed_string (e->inline_failed));
1618 if (!e->callee->analyzed)
1622 "Not inlining: Function body no longer available.\n");
1625 if (!tree_can_inline_p (e))
1629 "Not inlining: %s.",
1630 cgraph_inline_failed_string (e->inline_failed));
1633 if (cgraph_default_inline_p (e->callee, &failed_reason))
1636 fprintf (dump_file, " Inlining %s into %s.\n",
1637 cgraph_node_name (e->callee),
1638 cgraph_node_name (e->caller));
1639 cgraph_mark_inline (e);
1643 BITMAP_FREE (visited);
1648 /* Because inlining might remove no-longer reachable nodes, we need to
1649 keep the array visible to garbage collector to avoid reading collected
1652 static GTY ((length ("nnodes"))) struct cgraph_node **order;
1654 /* Do inlining of small functions. Doing so early helps profiling and other
1655 passes to be somewhat more effective and avoids some code duplication in
1656 later real inlining pass for testcases with very many function calls. */
1658 cgraph_early_inlining (void)
1660 struct cgraph_node *node = cgraph_node (current_function_decl);
1661 unsigned int todo = 0;
1664 if (sorrycount || errorcount)
1669 || !flag_early_inlining)
1671 /* When not optimizing or not inlining inline only always-inline
1673 cgraph_decide_inlining_incrementally (node, INLINE_ALWAYS_INLINE);
1674 timevar_push (TV_INTEGRATION);
1675 todo |= optimize_inline_calls (current_function_decl);
1676 timevar_pop (TV_INTEGRATION);
1680 if (lookup_attribute ("flatten",
1681 DECL_ATTRIBUTES (node->decl)) != NULL)
1685 "Flattening %s\n", cgraph_node_name (node));
1686 cgraph_flatten (node);
1687 timevar_push (TV_INTEGRATION);
1688 todo |= optimize_inline_calls (current_function_decl);
1689 timevar_pop (TV_INTEGRATION);
1691 /* We iterate incremental inlining to get trivial cases of indirect
1693 while (iterations < PARAM_VALUE (PARAM_EARLY_INLINER_MAX_ITERATIONS)
1694 && cgraph_decide_inlining_incrementally (node,
1696 ? INLINE_SIZE_NORECURSIVE
1699 timevar_push (TV_INTEGRATION);
1700 todo |= optimize_inline_calls (current_function_decl);
1702 timevar_pop (TV_INTEGRATION);
1705 fprintf (dump_file, "Iterations: %i\n", iterations);
1708 cfun->always_inline_functions_inlined = true;
1713 struct gimple_opt_pass pass_early_inline =
1717 "einline", /* name */
1719 cgraph_early_inlining, /* execute */
1722 0, /* static_pass_number */
1723 TV_INLINE_HEURISTICS, /* tv_id */
1724 0, /* properties_required */
1725 0, /* properties_provided */
1726 0, /* properties_destroyed */
1727 0, /* todo_flags_start */
1728 TODO_dump_func /* todo_flags_finish */
1732 /* When inlining shall be performed. */
1734 cgraph_gate_ipa_early_inlining (void)
1736 return (flag_early_inlining
1738 && (flag_branch_probabilities || flag_test_coverage
1739 || profile_arc_flag));
1742 /* IPA pass wrapper for early inlining pass. We need to run early inlining
1743 before tree profiling so we have stand alone IPA pass for doing so. */
1744 struct simple_ipa_opt_pass pass_ipa_early_inline =
1748 "einline_ipa", /* name */
1749 cgraph_gate_ipa_early_inlining, /* gate */
1753 0, /* static_pass_number */
1754 TV_INLINE_HEURISTICS, /* tv_id */
1755 0, /* properties_required */
1756 0, /* properties_provided */
1757 0, /* properties_destroyed */
1758 0, /* todo_flags_start */
1759 TODO_dump_cgraph /* todo_flags_finish */
1763 /* See if statement might disappear after inlining. We are not terribly
1764 sophisficated, basically looking for simple abstraction penalty wrappers. */
1767 likely_eliminated_by_inlining_p (gimple stmt)
1769 enum gimple_code code = gimple_code (stmt);
1775 if (gimple_num_ops (stmt) != 2)
1778 /* Casts of parameters, loads from parameters passed by reference
1779 and stores to return value or parameters are probably free after
1781 if (gimple_assign_rhs_code (stmt) == CONVERT_EXPR
1782 || gimple_assign_rhs_code (stmt) == NOP_EXPR
1783 || gimple_assign_rhs_code (stmt) == VIEW_CONVERT_EXPR
1784 || gimple_assign_rhs_class (stmt) == GIMPLE_SINGLE_RHS)
1786 tree rhs = gimple_assign_rhs1 (stmt);
1787 tree lhs = gimple_assign_lhs (stmt);
1788 tree inner_rhs = rhs;
1789 tree inner_lhs = lhs;
1790 bool rhs_free = false;
1791 bool lhs_free = false;
1793 while (handled_component_p (inner_lhs) || TREE_CODE (inner_lhs) == INDIRECT_REF)
1794 inner_lhs = TREE_OPERAND (inner_lhs, 0);
1795 while (handled_component_p (inner_rhs)
1796 || TREE_CODE (inner_rhs) == ADDR_EXPR || TREE_CODE (inner_rhs) == INDIRECT_REF)
1797 inner_rhs = TREE_OPERAND (inner_rhs, 0);
1800 if (TREE_CODE (inner_rhs) == PARM_DECL
1801 || (TREE_CODE (inner_rhs) == SSA_NAME
1802 && SSA_NAME_IS_DEFAULT_DEF (inner_rhs)
1803 && TREE_CODE (SSA_NAME_VAR (inner_rhs)) == PARM_DECL))
1805 if (rhs_free && is_gimple_reg (lhs))
1807 if (((TREE_CODE (inner_lhs) == PARM_DECL
1808 || (TREE_CODE (inner_lhs) == SSA_NAME
1809 && SSA_NAME_IS_DEFAULT_DEF (inner_lhs)
1810 && TREE_CODE (SSA_NAME_VAR (inner_lhs)) == PARM_DECL))
1811 && inner_lhs != lhs)
1812 || TREE_CODE (inner_lhs) == RESULT_DECL
1813 || (TREE_CODE (inner_lhs) == SSA_NAME
1814 && TREE_CODE (SSA_NAME_VAR (inner_lhs)) == RESULT_DECL))
1816 if (lhs_free && (is_gimple_reg (rhs) || is_gimple_min_invariant (rhs)))
1818 if (lhs_free && rhs_free)
1827 /* Compute function body size parameters for NODE. */
1830 estimate_function_body_sizes (struct cgraph_node *node)
1833 gcov_type time_inlining_benefit = 0;
1835 int size_inlining_benefit = 0;
1837 gimple_stmt_iterator bsi;
1838 struct function *my_function = DECL_STRUCT_FUNCTION (node->decl);
1841 tree funtype = TREE_TYPE (node->decl);
1844 fprintf (dump_file, "Analyzing function body size: %s\n",
1845 cgraph_node_name (node));
1847 gcc_assert (my_function && my_function->cfg);
1848 FOR_EACH_BB_FN (bb, my_function)
1850 freq = compute_call_stmt_bb_frequency (node->decl, bb);
1851 for (bsi = gsi_start_bb (bb); !gsi_end_p (bsi); gsi_next (&bsi))
1853 gimple stmt = gsi_stmt (bsi);
1854 int this_size = estimate_num_insns (stmt, &eni_size_weights);
1855 int this_time = estimate_num_insns (stmt, &eni_time_weights);
1857 if (dump_file && (dump_flags & TDF_DETAILS))
1859 fprintf (dump_file, " freq:%6i size:%3i time:%3i ",
1860 freq, this_size, this_time);
1861 print_gimple_stmt (dump_file, stmt, 0, 0);
1866 if (likely_eliminated_by_inlining_p (stmt))
1868 size_inlining_benefit += this_size;
1869 time_inlining_benefit += this_time;
1870 if (dump_file && (dump_flags & TDF_DETAILS))
1871 fprintf (dump_file, " Likely eliminated\n");
1873 gcc_assert (time >= 0);
1874 gcc_assert (size >= 0);
1877 time = (time + CGRAPH_FREQ_BASE / 2) / CGRAPH_FREQ_BASE;
1878 time_inlining_benefit = ((time_inlining_benefit + CGRAPH_FREQ_BASE / 2)
1879 / CGRAPH_FREQ_BASE);
1881 fprintf (dump_file, "Overall function body time: %i-%i size: %i-%i\n",
1882 (int)time, (int)time_inlining_benefit,
1883 size, size_inlining_benefit);
1884 time_inlining_benefit += eni_time_weights.call_cost;
1885 size_inlining_benefit += eni_size_weights.call_cost;
1886 if (!VOID_TYPE_P (TREE_TYPE (funtype)))
1888 int cost = estimate_move_cost (TREE_TYPE (funtype));
1889 time_inlining_benefit += cost;
1890 size_inlining_benefit += cost;
1892 for (arg = DECL_ARGUMENTS (node->decl); arg; arg = TREE_CHAIN (arg))
1893 if (!VOID_TYPE_P (TREE_TYPE (arg)))
1895 int cost = estimate_move_cost (TREE_TYPE (arg));
1896 time_inlining_benefit += cost;
1897 size_inlining_benefit += cost;
1899 if (time_inlining_benefit > MAX_TIME)
1900 time_inlining_benefit = MAX_TIME;
1901 if (time > MAX_TIME)
1903 inline_summary (node)->self_time = time;
1904 inline_summary (node)->self_size = size;
1906 fprintf (dump_file, "With function call overhead time: %i-%i size: %i-%i\n",
1907 (int)time, (int)time_inlining_benefit,
1908 size, size_inlining_benefit);
1909 inline_summary (node)->time_inlining_benefit = time_inlining_benefit;
1910 inline_summary (node)->size_inlining_benefit = size_inlining_benefit;
1913 /* Compute parameters of functions used by inliner. */
1915 compute_inline_parameters (struct cgraph_node *node)
1917 HOST_WIDE_INT self_stack_size;
1919 gcc_assert (!node->global.inlined_to);
1921 /* Estimate the stack size for the function. But not at -O0
1922 because estimated_stack_frame_size is a quadratic problem. */
1923 self_stack_size = optimize ? estimated_stack_frame_size () : 0;
1924 inline_summary (node)->estimated_self_stack_size = self_stack_size;
1925 node->global.estimated_stack_size = self_stack_size;
1926 node->global.stack_frame_offset = 0;
1928 /* Can this function be inlined at all? */
1929 node->local.inlinable = tree_inlinable_function_p (node->decl);
1930 if (node->local.inlinable && !node->local.disregard_inline_limits)
1931 node->local.disregard_inline_limits
1932 = DECL_DISREGARD_INLINE_LIMITS (node->decl);
1933 estimate_function_body_sizes (node);
1934 /* Inlining characteristics are maintained by the cgraph_mark_inline. */
1935 node->global.time = inline_summary (node)->self_time;
1936 node->global.size = inline_summary (node)->self_size;
1941 /* Compute parameters of functions used by inliner using
1942 current_function_decl. */
1944 compute_inline_parameters_for_current (void)
1946 compute_inline_parameters (cgraph_node (current_function_decl));
1950 struct gimple_opt_pass pass_inline_parameters =
1954 "inline_param", /* name */
1956 compute_inline_parameters_for_current,/* execute */
1959 0, /* static_pass_number */
1960 TV_INLINE_HEURISTICS, /* tv_id */
1961 0, /* properties_required */
1962 0, /* properties_provided */
1963 0, /* properties_destroyed */
1964 0, /* todo_flags_start */
1965 0 /* todo_flags_finish */
1969 /* This function performs intraprocedural analyzis in NODE that is required to
1970 inline indirect calls. */
1972 inline_indirect_intraprocedural_analysis (struct cgraph_node *node)
1974 struct cgraph_edge *cs;
1978 ipa_initialize_node_params (node);
1979 ipa_detect_param_modifications (node);
1981 ipa_analyze_params_uses (node);
1984 for (cs = node->callees; cs; cs = cs->next_callee)
1986 ipa_count_arguments (cs);
1987 ipa_compute_jump_functions (cs);
1992 ipa_print_node_params (dump_file, node);
1993 ipa_print_node_jump_functions (dump_file, node);
1997 /* Note function body size. */
1999 analyze_function (struct cgraph_node *node)
2001 push_cfun (DECL_STRUCT_FUNCTION (node->decl));
2002 current_function_decl = node->decl;
2004 compute_inline_parameters (node);
2005 if (flag_indirect_inlining)
2006 inline_indirect_intraprocedural_analysis (node);
2008 current_function_decl = NULL;
2012 /* Called when new function is inserted to callgraph late. */
2014 add_new_function (struct cgraph_node *node, void *data ATTRIBUTE_UNUSED)
2016 analyze_function (node);
2019 /* Note function body size. */
2021 inline_generate_summary (void)
2023 struct cgraph_node *node;
2025 function_insertion_hook_holder =
2026 cgraph_add_function_insertion_hook (&add_new_function, NULL);
2028 if (flag_indirect_inlining)
2030 ipa_register_cgraph_hooks ();
2031 ipa_check_create_node_params ();
2032 ipa_check_create_edge_args ();
2035 for (node = cgraph_nodes; node; node = node->next)
2037 analyze_function (node);
2042 /* Apply inline plan to function. */
2044 inline_transform (struct cgraph_node *node)
2046 unsigned int todo = 0;
2047 struct cgraph_edge *e;
2049 /* FIXME: Currently the passmanager is adding inline transform more than once to some
2050 clones. This needs revisiting after WPA cleanups. */
2051 if (cfun->after_inlining)
2054 /* We might need the body of this function so that we can expand
2055 it inline somewhere else. */
2056 if (cgraph_preserve_function_body_p (node->decl))
2057 save_inline_function_body (node);
2059 for (e = node->callees; e; e = e->next_callee)
2060 if (!e->inline_failed || warn_inline)
2065 timevar_push (TV_INTEGRATION);
2066 todo = optimize_inline_calls (current_function_decl);
2067 timevar_pop (TV_INTEGRATION);
2069 cfun->always_inline_functions_inlined = true;
2070 cfun->after_inlining = true;
2071 return todo | execute_fixup_cfg ();
2074 /* Read inline summary. Jump functions are shared among ipa-cp
2075 and inliner, so when ipa-cp is active, we don't need to write them
2079 inline_read_summary (void)
2081 if (flag_indirect_inlining)
2083 ipa_register_cgraph_hooks ();
2085 ipa_prop_read_jump_functions ();
2087 function_insertion_hook_holder =
2088 cgraph_add_function_insertion_hook (&add_new_function, NULL);
2091 /* Write inline summary for node in SET.
2092 Jump functions are shared among ipa-cp and inliner, so when ipa-cp is
2093 active, we don't need to write them twice. */
2096 inline_write_summary (cgraph_node_set set,
2097 varpool_node_set vset ATTRIBUTE_UNUSED)
2099 if (flag_indirect_inlining && !flag_ipa_cp)
2100 ipa_prop_write_jump_functions (set);
2103 /* When to run IPA inlining. Inlining of always-inline functions
2104 happens during early inlining. */
2107 gate_cgraph_decide_inlining (void)
2109 /* ??? We'd like to skip this if not optimizing or not inlining as
2110 all always-inline functions have been processed by early
2111 inlining already. But this at least breaks EH with C++ as
2112 we need to unconditionally run fixup_cfg even at -O0.
2113 So leave it on unconditionally for now. */
2117 struct ipa_opt_pass_d pass_ipa_inline =
2121 "inline", /* name */
2122 gate_cgraph_decide_inlining, /* gate */
2123 cgraph_decide_inlining, /* execute */
2126 0, /* static_pass_number */
2127 TV_INLINE_HEURISTICS, /* tv_id */
2128 0, /* properties_required */
2129 0, /* properties_provided */
2130 0, /* properties_destroyed */
2131 TODO_remove_functions, /* todo_flags_finish */
2132 TODO_dump_cgraph | TODO_dump_func
2133 | TODO_remove_functions | TODO_ggc_collect /* todo_flags_finish */
2135 inline_generate_summary, /* generate_summary */
2136 inline_write_summary, /* write_summary */
2137 inline_read_summary, /* read_summary */
2138 NULL, /* write_optimization_summary */
2139 NULL, /* read_optimization_summary */
2140 NULL, /* stmt_fixup */
2142 inline_transform, /* function_transform */
2143 NULL, /* variable_transform */
2147 #include "gt-ipa-inline.h"