1 /* Inlining decision heuristics.
2 Copyright (C) 2003, 2004, 2007, 2008, 2009, 2010
3 Free Software Foundation, Inc.
4 Contributed by Jan Hubicka
6 This file is part of GCC.
8 GCC is free software; you can redistribute it and/or modify it under
9 the terms of the GNU General Public License as published by the Free
10 Software Foundation; either version 3, or (at your option) any later
13 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
14 WARRANTY; without even the implied warranty of MERCHANTABILITY or
15 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
18 You should have received a copy of the GNU General Public License
19 along with GCC; see the file COPYING3. If not see
20 <http://www.gnu.org/licenses/>. */
22 /* Inlining decision heuristics
24 We separate inlining decisions from the inliner itself and store it
25 inside callgraph as so called inline plan. Refer to cgraph.c
26 documentation about particular representation of inline plans in the
29 There are three major parts of this file:
31 cgraph_mark_inline implementation
33 This function allows to mark given call inline and performs necessary
34 modifications of cgraph (production of the clones and updating overall
37 inlining heuristics limits
39 These functions allow to check that particular inlining is allowed
40 by the limits specified by user (allowed function growth, overall unit
45 This is implementation of IPA pass aiming to get as much of benefit
46 from inlining obeying the limits checked above.
48 The implementation of particular heuristics is separated from
49 the rest of code to make it easier to replace it with more complicated
50 implementation in the future. The rest of inlining code acts as a
51 library aimed to modify the callgraph and verify that the parameters
52 on code size growth fits.
54 To mark given call inline, use cgraph_mark_inline function, the
55 verification is performed by cgraph_default_inline_p and
56 cgraph_check_inline_limits.
58 The heuristics implements simple knapsack style algorithm ordering
59 all functions by their "profitability" (estimated by code size growth)
60 and inlining them in priority order.
62 cgraph_decide_inlining implements heuristics taking whole callgraph
63 into account, while cgraph_decide_inlining_incrementally considers
64 only one function at a time and is used by early inliner.
66 The inliner itself is split into several passes:
68 pass_inline_parameters
70 This pass computes local properties of functions that are used by inliner:
71 estimated function body size, whether function is inlinable at all and
72 stack frame consumption.
74 Before executing any of inliner passes, this local pass has to be applied
75 to each function in the callgraph (ie run as subpass of some earlier
76 IPA pass). The results are made out of date by any optimization applied
81 Simple local inlining pass inlining callees into current function. This
82 pass makes no global whole compilation unit analysis and this when allowed
83 to do inlining expanding code size it might result in unbounded growth of
86 The pass is run during conversion into SSA form. Only functions already
87 converted into SSA form are inlined, so the conversion must happen in
88 topological order on the callgraph (that is maintained by pass manager).
89 The functions after inlining are early optimized so the early inliner sees
90 unoptimized function itself, but all considered callees are already
91 optimized allowing it to unfold abstraction penalty on C++ effectively and
94 pass_ipa_early_inlining
96 With profiling, the early inlining is also necessary to reduce
97 instrumentation costs on program with high abstraction penalty (doing
98 many redundant calls). This can't happen in parallel with early
99 optimization and profile instrumentation, because we would end up
100 re-instrumenting already instrumented function bodies we brought in via
103 To avoid this, this pass is executed as IPA pass before profiling. It is
104 simple wrapper to pass_early_inlining and ensures first inlining.
108 This is the main pass implementing simple greedy algorithm to do inlining
109 of small functions that results in overall growth of compilation unit and
110 inlining of functions called once. The pass compute just so called inline
111 plan (representation of inlining to be done in callgraph) and unlike early
112 inlining it is not performing the inlining itself.
116 This pass performs actual inlining according to pass_ipa_inline on given
117 function. Possible the function body before inlining is saved when it is
118 needed for further inlining later.
123 #include "coretypes.h"
126 #include "tree-inline.h"
127 #include "langhooks.h"
130 #include "diagnostic.h"
131 #include "gimple-pretty-print.h"
136 #include "tree-pass.h"
138 #include "coverage.h"
140 #include "tree-flow.h"
142 #include "ipa-prop.h"
145 #define MAX_TIME 1000000000
147 /* Mode incremental inliner operate on:
149 In ALWAYS_INLINE only functions marked
150 always_inline are inlined. This mode is used after detecting cycle during
153 In SIZE mode, only functions that reduce function body size after inlining
154 are inlined, this is used during early inlining.
156 in ALL mode, everything is inlined. This is used during flattening. */
159 INLINE_ALWAYS_INLINE,
160 INLINE_SIZE_NORECURSIVE,
166 cgraph_decide_inlining_incrementally (struct cgraph_node *, enum inlining_mode);
167 static void cgraph_flatten (struct cgraph_node *node);
170 /* Statistics we collect about inlining algorithm. */
171 static int ncalls_inlined;
172 static int nfunctions_inlined;
173 static int overall_size;
174 static gcov_type max_count, max_benefit;
176 /* Holders of ipa cgraph hooks: */
177 static struct cgraph_node_hook_list *function_insertion_hook_holder;
179 static inline struct inline_summary *
180 inline_summary (struct cgraph_node *node)
182 return &node->local.inline_summary;
185 /* Estimate self time of the function after inlining WHAT into TO. */
188 cgraph_estimate_time_after_inlining (int frequency, struct cgraph_node *to,
189 struct cgraph_node *what)
191 gcov_type time = (((gcov_type)what->global.time
192 - inline_summary (what)->time_inlining_benefit)
193 * frequency + CGRAPH_FREQ_BASE / 2) / CGRAPH_FREQ_BASE
202 /* Estimate self time of the function after inlining WHAT into TO. */
205 cgraph_estimate_size_after_inlining (int times, struct cgraph_node *to,
206 struct cgraph_node *what)
208 int size = (what->global.size - inline_summary (what)->size_inlining_benefit) * times + to->global.size;
209 gcc_assert (size >= 0);
213 /* Scale frequency of NODE edges by FREQ_SCALE and increase loop nest
217 update_noncloned_frequencies (struct cgraph_node *node,
218 int freq_scale, int nest)
220 struct cgraph_edge *e;
222 /* We do not want to ignore high loop nest after freq drops to 0. */
225 for (e = node->callees; e; e = e->next_callee)
227 e->loop_nest += nest;
228 e->frequency = e->frequency * (gcov_type) freq_scale / CGRAPH_FREQ_BASE;
229 if (e->frequency > CGRAPH_FREQ_MAX)
230 e->frequency = CGRAPH_FREQ_MAX;
231 if (!e->inline_failed)
232 update_noncloned_frequencies (e->callee, freq_scale, nest);
236 /* E is expected to be an edge being inlined. Clone destination node of
237 the edge and redirect it to the new clone.
238 DUPLICATE is used for bookkeeping on whether we are actually creating new
239 clones or re-using node originally representing out-of-line function call.
242 cgraph_clone_inlined_nodes (struct cgraph_edge *e, bool duplicate,
243 bool update_original)
249 /* We may eliminate the need for out-of-line copy to be output.
250 In that case just go ahead and re-use it. */
251 if (!e->callee->callers->next_caller
252 && cgraph_can_remove_if_no_direct_calls_p (e->callee)
253 /* Don't reuse if more than one function shares a comdat group.
254 If the other function(s) are needed, we need to emit even
255 this function out of line. */
256 && !e->callee->same_comdat_group
257 && !cgraph_new_nodes)
259 gcc_assert (!e->callee->global.inlined_to);
260 if (e->callee->analyzed)
262 overall_size -= e->callee->global.size;
263 nfunctions_inlined++;
266 e->callee->local.externally_visible = false;
267 update_noncloned_frequencies (e->callee, e->frequency, e->loop_nest);
271 struct cgraph_node *n;
272 n = cgraph_clone_node (e->callee, e->callee->decl,
273 e->count, e->frequency, e->loop_nest,
274 update_original, NULL);
275 cgraph_redirect_edge_callee (e, n);
279 if (e->caller->global.inlined_to)
280 e->callee->global.inlined_to = e->caller->global.inlined_to;
282 e->callee->global.inlined_to = e->caller;
283 e->callee->global.stack_frame_offset
284 = e->caller->global.stack_frame_offset
285 + inline_summary (e->caller)->estimated_self_stack_size;
286 peak = e->callee->global.stack_frame_offset
287 + inline_summary (e->callee)->estimated_self_stack_size;
288 if (e->callee->global.inlined_to->global.estimated_stack_size < peak)
289 e->callee->global.inlined_to->global.estimated_stack_size = peak;
290 cgraph_propagate_frequency (e->callee);
292 /* Recursively clone all bodies. */
293 for (e = e->callee->callees; e; e = e->next_callee)
294 if (!e->inline_failed)
295 cgraph_clone_inlined_nodes (e, duplicate, update_original);
298 /* Mark edge E as inlined and update callgraph accordingly. UPDATE_ORIGINAL
299 specify whether profile of original function should be updated. If any new
300 indirect edges are discovered in the process, add them to NEW_EDGES, unless
301 it is NULL. Return true iff any new callgraph edges were discovered as a
302 result of inlining. */
305 cgraph_mark_inline_edge (struct cgraph_edge *e, bool update_original,
306 VEC (cgraph_edge_p, heap) **new_edges)
308 int old_size = 0, new_size = 0;
309 struct cgraph_node *to = NULL, *what;
310 struct cgraph_edge *curr = e;
313 gcc_assert (e->inline_failed);
314 e->inline_failed = CIF_OK;
315 DECL_POSSIBLY_INLINED (e->callee->decl) = true;
317 cgraph_clone_inlined_nodes (e, true, update_original);
322 /* Now update size of caller and all functions caller is inlined into. */
323 for (;e && !e->inline_failed; e = e->caller->callers)
326 old_size = e->caller->global.size;
327 new_size = cgraph_estimate_size_after_inlining (1, to, what);
328 to->global.size = new_size;
329 to->global.time = cgraph_estimate_time_after_inlining (freq, to, what);
331 gcc_assert (what->global.inlined_to == to);
332 if (new_size > old_size)
333 overall_size += new_size - old_size;
336 if (flag_indirect_inlining)
337 return ipa_propagate_indirect_call_infos (curr, new_edges);
342 /* Mark all calls of EDGE->CALLEE inlined into EDGE->CALLER. */
345 cgraph_mark_inline (struct cgraph_edge *edge)
347 struct cgraph_node *to = edge->caller;
348 struct cgraph_node *what = edge->callee;
349 struct cgraph_edge *e, *next;
351 gcc_assert (!edge->call_stmt_cannot_inline_p);
352 /* Look for all calls, mark them inline and clone recursively
353 all inlined functions. */
354 for (e = what->callers; e; e = next)
356 next = e->next_caller;
357 if (e->caller == to && e->inline_failed)
359 cgraph_mark_inline_edge (e, true, NULL);
366 /* Estimate the growth caused by inlining NODE into all callees. */
369 cgraph_estimate_growth (struct cgraph_node *node)
372 struct cgraph_edge *e;
373 bool self_recursive = false;
375 if (node->global.estimated_growth != INT_MIN)
376 return node->global.estimated_growth;
378 for (e = node->callers; e; e = e->next_caller)
380 if (e->caller == node)
381 self_recursive = true;
382 if (e->inline_failed)
383 growth += (cgraph_estimate_size_after_inlining (1, e->caller, node)
384 - e->caller->global.size);
387 /* ??? Wrong for non-trivially self recursive functions or cases where
388 we decide to not inline for different reasons, but it is not big deal
389 as in that case we will keep the body around, but we will also avoid
391 if (cgraph_only_called_directly_p (node)
392 && !DECL_EXTERNAL (node->decl) && !self_recursive)
393 growth -= node->global.size;
395 node->global.estimated_growth = growth;
399 /* Return false when inlining WHAT into TO is not good idea
400 as it would cause too large growth of function bodies.
401 When ONE_ONLY is true, assume that only one call site is going
402 to be inlined, otherwise figure out how many call sites in
403 TO calls WHAT and verify that all can be inlined.
407 cgraph_check_inline_limits (struct cgraph_node *to, struct cgraph_node *what,
408 cgraph_inline_failed_t *reason, bool one_only)
411 struct cgraph_edge *e;
414 HOST_WIDE_INT stack_size_limit, inlined_stack;
419 for (e = to->callees; e; e = e->next_callee)
420 if (e->callee == what)
423 if (to->global.inlined_to)
424 to = to->global.inlined_to;
426 /* When inlining large function body called once into small function,
427 take the inlined function as base for limiting the growth. */
428 if (inline_summary (to)->self_size > inline_summary(what)->self_size)
429 limit = inline_summary (to)->self_size;
431 limit = inline_summary (what)->self_size;
433 limit += limit * PARAM_VALUE (PARAM_LARGE_FUNCTION_GROWTH) / 100;
435 /* Check the size after inlining against the function limits. But allow
436 the function to shrink if it went over the limits by forced inlining. */
437 newsize = cgraph_estimate_size_after_inlining (times, to, what);
438 if (newsize >= to->global.size
439 && newsize > PARAM_VALUE (PARAM_LARGE_FUNCTION_INSNS)
443 *reason = CIF_LARGE_FUNCTION_GROWTH_LIMIT;
447 stack_size_limit = inline_summary (to)->estimated_self_stack_size;
449 stack_size_limit += stack_size_limit * PARAM_VALUE (PARAM_STACK_FRAME_GROWTH) / 100;
451 inlined_stack = (to->global.stack_frame_offset
452 + inline_summary (to)->estimated_self_stack_size
453 + what->global.estimated_stack_size);
454 if (inlined_stack > stack_size_limit
455 && inlined_stack > PARAM_VALUE (PARAM_LARGE_STACK_FRAME))
458 *reason = CIF_LARGE_STACK_FRAME_GROWTH_LIMIT;
464 /* Return true when function N is small enough to be inlined. */
467 cgraph_default_inline_p (struct cgraph_node *n, cgraph_inline_failed_t *reason)
471 if (n->local.disregard_inline_limits)
474 if (!flag_inline_small_functions && !DECL_DECLARED_INLINE_P (decl))
477 *reason = CIF_FUNCTION_NOT_INLINE_CANDIDATE;
484 *reason = CIF_BODY_NOT_AVAILABLE;
488 if (DECL_DECLARED_INLINE_P (decl))
490 if (n->global.size >= MAX_INLINE_INSNS_SINGLE)
493 *reason = CIF_MAX_INLINE_INSNS_SINGLE_LIMIT;
499 if (n->global.size >= MAX_INLINE_INSNS_AUTO)
502 *reason = CIF_MAX_INLINE_INSNS_AUTO_LIMIT;
510 /* Return true when inlining WHAT would create recursive inlining.
511 We call recursive inlining all cases where same function appears more than
512 once in the single recursion nest path in the inline graph. */
515 cgraph_recursive_inlining_p (struct cgraph_node *to,
516 struct cgraph_node *what,
517 cgraph_inline_failed_t *reason)
520 if (to->global.inlined_to)
521 recursive = what->decl == to->global.inlined_to->decl;
523 recursive = what->decl == to->decl;
524 /* Marking recursive function inline has sane semantic and thus we should
526 if (recursive && reason)
527 *reason = (what->local.disregard_inline_limits
528 ? CIF_RECURSIVE_INLINING : CIF_UNSPECIFIED);
532 /* A cost model driving the inlining heuristics in a way so the edges with
533 smallest badness are inlined first. After each inlining is performed
534 the costs of all caller edges of nodes affected are recomputed so the
535 metrics may accurately depend on values such as number of inlinable callers
536 of the function or function body size. */
539 cgraph_edge_badness (struct cgraph_edge *edge, bool dump)
543 (cgraph_estimate_size_after_inlining (1, edge->caller, edge->callee)
544 - edge->caller->global.size);
546 if (edge->callee->local.disregard_inline_limits)
551 fprintf (dump_file, " Badness calculcation for %s -> %s\n",
552 cgraph_node_name (edge->caller),
553 cgraph_node_name (edge->callee));
554 fprintf (dump_file, " growth %i, time %i-%i, size %i-%i\n",
556 edge->callee->global.time,
557 inline_summary (edge->callee)->time_inlining_benefit,
558 edge->callee->global.size,
559 inline_summary (edge->callee)->size_inlining_benefit);
562 /* Always prefer inlining saving code size. */
565 badness = INT_MIN - growth;
567 fprintf (dump_file, " %i: Growth %i < 0\n", (int) badness,
571 /* When profiling is available, base priorities -(#calls / growth).
572 So we optimize for overall number of "executed" inlined calls. */
577 ((double) edge->count * INT_MIN / max_count / (max_benefit + 1)) *
578 (inline_summary (edge->callee)->time_inlining_benefit + 1)) / growth;
582 " %i (relative %f): profile info. Relative count %f"
583 " * Relative benefit %f\n",
584 (int) badness, (double) badness / INT_MIN,
585 (double) edge->count / max_count,
586 (double) (inline_summary (edge->callee)->
587 time_inlining_benefit + 1) / (max_benefit + 1));
591 /* When function local profile is available, base priorities on
592 growth / frequency, so we optimize for overall frequency of inlined
593 calls. This is not too accurate since while the call might be frequent
594 within function, the function itself is infrequent.
596 Other objective to optimize for is number of different calls inlined.
597 We add the estimated growth after inlining all functions to bias the
598 priorities slightly in this direction (so fewer times called functions
599 of the same size gets priority). */
600 else if (flag_guess_branch_prob)
602 int div = edge->frequency * 100 / CGRAPH_FREQ_BASE + 1;
605 badness = growth * 10000;
607 MIN (100 * inline_summary (edge->callee)->time_inlining_benefit /
608 (edge->callee->global.time + 1) +1, 100);
612 /* Decrease badness if call is nested. */
613 /* Compress the range so we don't overflow. */
615 div = 10000 + ceil_log2 (div) - 8;
620 growth_for_all = cgraph_estimate_growth (edge->callee);
621 badness += growth_for_all;
622 if (badness > INT_MAX)
627 " %i: guessed profile. frequency %i, overall growth %i,"
628 " benefit %i%%, divisor %i\n",
629 (int) badness, edge->frequency, growth_for_all, benefitperc, div);
632 /* When function local profile is not available or it does not give
633 useful information (ie frequency is zero), base the cost on
634 loop nest and overall size growth, so we optimize for overall number
635 of functions fully inlined in program. */
638 int nest = MIN (edge->loop_nest, 8);
639 badness = cgraph_estimate_growth (edge->callee) * 256;
641 /* Decrease badness if call is nested. */
649 fprintf (dump_file, " %i: no profile. nest %i\n", (int) badness,
653 /* Ensure that we did not overflow in all the fixed point math above. */
654 gcc_assert (badness >= INT_MIN);
655 gcc_assert (badness <= INT_MAX - 1);
656 /* Make recursive inlining happen always after other inlining is done. */
657 if (cgraph_recursive_inlining_p (edge->caller, edge->callee, NULL))
663 /* Recompute heap nodes for each of caller edge. */
666 update_caller_keys (fibheap_t heap, struct cgraph_node *node,
667 bitmap updated_nodes)
669 struct cgraph_edge *edge;
670 cgraph_inline_failed_t failed_reason;
672 if (!node->local.inlinable
673 || node->global.inlined_to)
675 if (bitmap_bit_p (updated_nodes, node->uid))
677 bitmap_set_bit (updated_nodes, node->uid);
678 node->global.estimated_growth = INT_MIN;
680 if (!node->local.inlinable)
682 /* Prune out edges we won't inline into anymore. */
683 if (!cgraph_default_inline_p (node, &failed_reason))
685 for (edge = node->callers; edge; edge = edge->next_caller)
688 fibheap_delete_node (heap, (fibnode_t) edge->aux);
690 if (edge->inline_failed)
691 edge->inline_failed = failed_reason;
696 for (edge = node->callers; edge; edge = edge->next_caller)
697 if (edge->inline_failed)
699 int badness = cgraph_edge_badness (edge, false);
702 fibnode_t n = (fibnode_t) edge->aux;
703 gcc_assert (n->data == edge);
704 if (n->key == badness)
707 /* fibheap_replace_key only increase the keys. */
708 if (badness < n->key)
710 fibheap_replace_key (heap, n, badness);
711 gcc_assert (n->key == badness);
714 fibheap_delete_node (heap, (fibnode_t) edge->aux);
716 edge->aux = fibheap_insert (heap, badness, edge);
720 /* Recompute heap nodes for each of caller edges of each of callees. */
723 update_callee_keys (fibheap_t heap, struct cgraph_node *node,
724 bitmap updated_nodes)
726 struct cgraph_edge *e;
727 node->global.estimated_growth = INT_MIN;
729 for (e = node->callees; e; e = e->next_callee)
730 if (e->inline_failed)
731 update_caller_keys (heap, e->callee, updated_nodes);
732 else if (!e->inline_failed)
733 update_callee_keys (heap, e->callee, updated_nodes);
736 /* Enqueue all recursive calls from NODE into priority queue depending on
737 how likely we want to recursively inline the call. */
740 lookup_recursive_calls (struct cgraph_node *node, struct cgraph_node *where,
744 struct cgraph_edge *e;
745 for (e = where->callees; e; e = e->next_callee)
746 if (e->callee == node)
748 /* When profile feedback is available, prioritize by expected number
749 of calls. Without profile feedback we maintain simple queue
750 to order candidates via recursive depths. */
751 fibheap_insert (heap,
752 !max_count ? priority++
753 : -(e->count / ((max_count + (1<<24) - 1) / (1<<24))),
756 for (e = where->callees; e; e = e->next_callee)
757 if (!e->inline_failed)
758 lookup_recursive_calls (node, e->callee, heap);
761 /* Decide on recursive inlining: in the case function has recursive calls,
762 inline until body size reaches given argument. If any new indirect edges
763 are discovered in the process, add them to *NEW_EDGES, unless NEW_EDGES
767 cgraph_decide_recursive_inlining (struct cgraph_node *node,
768 VEC (cgraph_edge_p, heap) **new_edges)
770 int limit = PARAM_VALUE (PARAM_MAX_INLINE_INSNS_RECURSIVE_AUTO);
771 int max_depth = PARAM_VALUE (PARAM_MAX_INLINE_RECURSIVE_DEPTH_AUTO);
772 int probability = PARAM_VALUE (PARAM_MIN_INLINE_RECURSIVE_PROBABILITY);
774 struct cgraph_edge *e;
775 struct cgraph_node *master_clone, *next;
779 /* It does not make sense to recursively inline always-inline functions
780 as we are going to sorry() on the remaining calls anyway. */
781 if (node->local.disregard_inline_limits
782 && lookup_attribute ("always_inline", DECL_ATTRIBUTES (node->decl)))
785 if (optimize_function_for_size_p (DECL_STRUCT_FUNCTION (node->decl))
786 || (!flag_inline_functions && !DECL_DECLARED_INLINE_P (node->decl)))
789 if (DECL_DECLARED_INLINE_P (node->decl))
791 limit = PARAM_VALUE (PARAM_MAX_INLINE_INSNS_RECURSIVE);
792 max_depth = PARAM_VALUE (PARAM_MAX_INLINE_RECURSIVE_DEPTH);
795 /* Make sure that function is small enough to be considered for inlining. */
797 || cgraph_estimate_size_after_inlining (1, node, node) >= limit)
799 heap = fibheap_new ();
800 lookup_recursive_calls (node, node, heap);
801 if (fibheap_empty (heap))
803 fibheap_delete (heap);
809 " Performing recursive inlining on %s\n",
810 cgraph_node_name (node));
812 /* We need original clone to copy around. */
813 master_clone = cgraph_clone_node (node, node->decl,
814 node->count, CGRAPH_FREQ_BASE, 1,
816 master_clone->needed = true;
817 for (e = master_clone->callees; e; e = e->next_callee)
818 if (!e->inline_failed)
819 cgraph_clone_inlined_nodes (e, true, false);
821 /* Do the inlining and update list of recursive call during process. */
822 while (!fibheap_empty (heap)
823 && (cgraph_estimate_size_after_inlining (1, node, master_clone)
826 struct cgraph_edge *curr
827 = (struct cgraph_edge *) fibheap_extract_min (heap);
828 struct cgraph_node *cnode;
831 for (cnode = curr->caller;
832 cnode->global.inlined_to; cnode = cnode->callers->caller)
833 if (node->decl == curr->callee->decl)
835 if (depth > max_depth)
839 " maximal depth reached\n");
845 if (!cgraph_maybe_hot_edge_p (curr))
848 fprintf (dump_file, " Not inlining cold call\n");
851 if (curr->count * 100 / node->count < probability)
855 " Probability of edge is too small\n");
863 " Inlining call of depth %i", depth);
866 fprintf (dump_file, " called approx. %.2f times per call",
867 (double)curr->count / node->count);
869 fprintf (dump_file, "\n");
871 cgraph_redirect_edge_callee (curr, master_clone);
872 cgraph_mark_inline_edge (curr, false, new_edges);
873 lookup_recursive_calls (node, curr->callee, heap);
876 if (!fibheap_empty (heap) && dump_file)
877 fprintf (dump_file, " Recursive inlining growth limit met.\n");
879 fibheap_delete (heap);
882 "\n Inlined %i times, body grown from size %i to %i, time %i to %i\n", n,
883 master_clone->global.size, node->global.size,
884 master_clone->global.time, node->global.time);
886 /* Remove master clone we used for inlining. We rely that clones inlined
887 into master clone gets queued just before master clone so we don't
889 for (node = cgraph_nodes; node != master_clone;
893 if (node->global.inlined_to == master_clone)
894 cgraph_remove_node (node);
896 cgraph_remove_node (master_clone);
897 /* FIXME: Recursive inlining actually reduces number of calls of the
898 function. At this place we should probably walk the function and
899 inline clones and compensate the counts accordingly. This probably
900 doesn't matter much in practice. */
904 /* Set inline_failed for all callers of given function to REASON. */
907 cgraph_set_inline_failed (struct cgraph_node *node,
908 cgraph_inline_failed_t reason)
910 struct cgraph_edge *e;
913 fprintf (dump_file, "Inlining failed: %s\n",
914 cgraph_inline_failed_string (reason));
915 for (e = node->callers; e; e = e->next_caller)
916 if (e->inline_failed)
917 e->inline_failed = reason;
920 /* Given whole compilation unit estimate of INSNS, compute how large we can
921 allow the unit to grow. */
923 compute_max_insns (int insns)
925 int max_insns = insns;
926 if (max_insns < PARAM_VALUE (PARAM_LARGE_UNIT_INSNS))
927 max_insns = PARAM_VALUE (PARAM_LARGE_UNIT_INSNS);
929 return ((HOST_WIDEST_INT) max_insns
930 * (100 + PARAM_VALUE (PARAM_INLINE_UNIT_GROWTH)) / 100);
933 /* Compute badness of all edges in NEW_EDGES and add them to the HEAP. */
935 add_new_edges_to_heap (fibheap_t heap, VEC (cgraph_edge_p, heap) *new_edges)
937 while (VEC_length (cgraph_edge_p, new_edges) > 0)
939 struct cgraph_edge *edge = VEC_pop (cgraph_edge_p, new_edges);
941 gcc_assert (!edge->aux);
942 edge->aux = fibheap_insert (heap, cgraph_edge_badness (edge, false), edge);
947 /* We use greedy algorithm for inlining of small functions:
948 All inline candidates are put into prioritized heap based on estimated
949 growth of the overall number of instructions and then update the estimates.
951 INLINED and INLINED_CALEES are just pointers to arrays large enough
952 to be passed to cgraph_inlined_into and cgraph_inlined_callees. */
955 cgraph_decide_inlining_of_small_functions (void)
957 struct cgraph_node *node;
958 struct cgraph_edge *edge;
959 cgraph_inline_failed_t failed_reason;
960 fibheap_t heap = fibheap_new ();
961 bitmap updated_nodes = BITMAP_ALLOC (NULL);
962 int min_size, max_size;
963 VEC (cgraph_edge_p, heap) *new_indirect_edges = NULL;
965 if (flag_indirect_inlining)
966 new_indirect_edges = VEC_alloc (cgraph_edge_p, heap, 8);
969 fprintf (dump_file, "\nDeciding on smaller functions:\n");
971 /* Put all inline candidates into the heap. */
973 for (node = cgraph_nodes; node; node = node->next)
975 if (!node->local.inlinable || !node->callers)
978 fprintf (dump_file, "Considering inline candidate %s.\n", cgraph_node_name (node));
980 node->global.estimated_growth = INT_MIN;
981 if (!cgraph_default_inline_p (node, &failed_reason))
983 cgraph_set_inline_failed (node, failed_reason);
987 for (edge = node->callers; edge; edge = edge->next_caller)
988 if (edge->inline_failed)
990 gcc_assert (!edge->aux);
991 edge->aux = fibheap_insert (heap, cgraph_edge_badness (edge, false), edge);
995 max_size = compute_max_insns (overall_size);
996 min_size = overall_size;
998 while (overall_size <= max_size
999 && !fibheap_empty (heap))
1001 int old_size = overall_size;
1002 struct cgraph_node *where, *callee;
1003 int badness = fibheap_min_key (heap);
1005 cgraph_inline_failed_t not_good = CIF_OK;
1007 edge = (struct cgraph_edge *) fibheap_extract_min (heap);
1008 gcc_assert (edge->aux);
1010 if (!edge->inline_failed)
1012 #ifdef ENABLE_CHECKING
1013 gcc_assert (cgraph_edge_badness (edge, false) == badness);
1015 callee = edge->callee;
1017 growth = (cgraph_estimate_size_after_inlining (1, edge->caller, edge->callee)
1018 - edge->caller->global.size);
1023 "\nConsidering %s with %i size\n",
1024 cgraph_node_name (edge->callee),
1025 edge->callee->global.size);
1027 " to be inlined into %s in %s:%i\n"
1028 " Estimated growth after inlined into all callees is %+i insns.\n"
1029 " Estimated badness is %i, frequency %.2f.\n",
1030 cgraph_node_name (edge->caller),
1031 flag_wpa ? "unknown"
1032 : gimple_filename ((const_gimple) edge->call_stmt),
1033 flag_wpa ? -1 : gimple_lineno ((const_gimple) edge->call_stmt),
1034 cgraph_estimate_growth (edge->callee),
1036 edge->frequency / (double)CGRAPH_FREQ_BASE);
1038 fprintf (dump_file," Called "HOST_WIDEST_INT_PRINT_DEC"x\n", edge->count);
1039 if (dump_flags & TDF_DETAILS)
1040 cgraph_edge_badness (edge, true);
1043 /* When not having profile info ready we don't weight by any way the
1044 position of call in procedure itself. This means if call of
1045 function A from function B seems profitable to inline, the recursive
1046 call of function A in inline copy of A in B will look profitable too
1047 and we end up inlining until reaching maximal function growth. This
1048 is not good idea so prohibit the recursive inlining.
1050 ??? When the frequencies are taken into account we might not need this
1053 We need to be cureful here, in some testcases, e.g. directivec.c in
1054 libcpp, we can estimate self recursive function to have negative growth
1055 for inlining completely.
1059 where = edge->caller;
1060 while (where->global.inlined_to)
1062 if (where->decl == edge->callee->decl)
1064 where = where->callers->caller;
1066 if (where->global.inlined_to)
1069 = (edge->callee->local.disregard_inline_limits
1070 ? CIF_RECURSIVE_INLINING : CIF_UNSPECIFIED);
1072 fprintf (dump_file, " inline_failed:Recursive inlining performed only for function itself.\n");
1077 if (edge->callee->local.disregard_inline_limits)
1079 else if (!cgraph_maybe_hot_edge_p (edge))
1080 not_good = CIF_UNLIKELY_CALL;
1081 else if (!flag_inline_functions
1082 && !DECL_DECLARED_INLINE_P (edge->callee->decl))
1083 not_good = CIF_NOT_DECLARED_INLINED;
1084 else if (optimize_function_for_size_p (DECL_STRUCT_FUNCTION(edge->caller->decl)))
1085 not_good = CIF_OPTIMIZING_FOR_SIZE;
1086 if (not_good && growth > 0 && cgraph_estimate_growth (edge->callee) > 0)
1088 if (!cgraph_recursive_inlining_p (edge->caller, edge->callee,
1089 &edge->inline_failed))
1091 edge->inline_failed = not_good;
1093 fprintf (dump_file, " inline_failed:%s.\n",
1094 cgraph_inline_failed_string (edge->inline_failed));
1098 if (!cgraph_default_inline_p (edge->callee, &edge->inline_failed))
1100 if (!cgraph_recursive_inlining_p (edge->caller, edge->callee,
1101 &edge->inline_failed))
1104 fprintf (dump_file, " inline_failed:%s.\n",
1105 cgraph_inline_failed_string (edge->inline_failed));
1109 if (!tree_can_inline_p (edge))
1112 fprintf (dump_file, " inline_failed:%s.\n",
1113 cgraph_inline_failed_string (edge->inline_failed));
1116 if (cgraph_recursive_inlining_p (edge->caller, edge->callee,
1117 &edge->inline_failed))
1119 where = edge->caller;
1120 if (where->global.inlined_to)
1121 where = where->global.inlined_to;
1122 if (!cgraph_decide_recursive_inlining (where,
1123 flag_indirect_inlining
1124 ? &new_indirect_edges : NULL))
1126 if (flag_indirect_inlining)
1127 add_new_edges_to_heap (heap, new_indirect_edges);
1128 update_callee_keys (heap, where, updated_nodes);
1132 struct cgraph_node *callee;
1133 if (edge->call_stmt_cannot_inline_p
1134 || !cgraph_check_inline_limits (edge->caller, edge->callee,
1135 &edge->inline_failed, true))
1138 fprintf (dump_file, " Not inlining into %s:%s.\n",
1139 cgraph_node_name (edge->caller),
1140 cgraph_inline_failed_string (edge->inline_failed));
1143 callee = edge->callee;
1144 cgraph_mark_inline_edge (edge, true, &new_indirect_edges);
1145 if (flag_indirect_inlining)
1146 add_new_edges_to_heap (heap, new_indirect_edges);
1148 update_callee_keys (heap, callee, updated_nodes);
1150 where = edge->caller;
1151 if (where->global.inlined_to)
1152 where = where->global.inlined_to;
1154 /* Our profitability metric can depend on local properties
1155 such as number of inlinable calls and size of the function body.
1156 After inlining these properties might change for the function we
1157 inlined into (since it's body size changed) and for the functions
1158 called by function we inlined (since number of it inlinable callers
1160 update_caller_keys (heap, where, updated_nodes);
1162 /* We removed one call of the function we just inlined. If offline
1163 copy is still needed, be sure to update the keys. */
1164 if (callee != where && !callee->global.inlined_to)
1165 update_caller_keys (heap, callee, updated_nodes);
1166 bitmap_clear (updated_nodes);
1171 " Inlined into %s which now has size %i and self time %i,"
1172 "net change of %+i.\n",
1173 cgraph_node_name (edge->caller),
1174 edge->caller->global.time,
1175 edge->caller->global.size,
1176 overall_size - old_size);
1178 if (min_size > overall_size)
1180 min_size = overall_size;
1181 max_size = compute_max_insns (min_size);
1184 fprintf (dump_file, "New minimal size reached: %i\n", min_size);
1187 while (!fibheap_empty (heap))
1189 int badness = fibheap_min_key (heap);
1191 edge = (struct cgraph_edge *) fibheap_extract_min (heap);
1192 gcc_assert (edge->aux);
1194 if (!edge->inline_failed)
1196 #ifdef ENABLE_CHECKING
1197 gcc_assert (cgraph_edge_badness (edge, false) == badness);
1202 "\nSkipping %s with %i size\n",
1203 cgraph_node_name (edge->callee),
1204 edge->callee->global.size);
1206 " called by %s in %s:%i\n"
1207 " Estimated growth after inlined into all callees is %+i insns.\n"
1208 " Estimated badness is %i, frequency %.2f.\n",
1209 cgraph_node_name (edge->caller),
1210 flag_wpa ? "unknown"
1211 : gimple_filename ((const_gimple) edge->call_stmt),
1212 flag_wpa ? -1 : gimple_lineno ((const_gimple) edge->call_stmt),
1213 cgraph_estimate_growth (edge->callee),
1215 edge->frequency / (double)CGRAPH_FREQ_BASE);
1217 fprintf (dump_file," Called "HOST_WIDEST_INT_PRINT_DEC"x\n", edge->count);
1218 if (dump_flags & TDF_DETAILS)
1219 cgraph_edge_badness (edge, true);
1221 if (!edge->callee->local.disregard_inline_limits && edge->inline_failed
1222 && !cgraph_recursive_inlining_p (edge->caller, edge->callee,
1223 &edge->inline_failed))
1224 edge->inline_failed = CIF_INLINE_UNIT_GROWTH_LIMIT;
1227 if (new_indirect_edges)
1228 VEC_free (cgraph_edge_p, heap, new_indirect_edges);
1229 fibheap_delete (heap);
1230 BITMAP_FREE (updated_nodes);
1233 /* Flatten NODE from the IPA inliner. */
1236 cgraph_flatten (struct cgraph_node *node)
1238 struct cgraph_edge *e;
1240 /* We shouldn't be called recursively when we are being processed. */
1241 gcc_assert (node->aux == NULL);
1243 node->aux = (void *)(size_t) INLINE_ALL;
1245 for (e = node->callees; e; e = e->next_callee)
1247 struct cgraph_node *orig_callee;
1249 if (e->call_stmt_cannot_inline_p)
1252 if (!e->callee->analyzed)
1256 "Not inlining: Function body not available.\n");
1260 /* We've hit cycle? It is time to give up. */
1265 "Not inlining %s into %s to avoid cycle.\n",
1266 cgraph_node_name (e->callee),
1267 cgraph_node_name (e->caller));
1268 e->inline_failed = CIF_RECURSIVE_INLINING;
1272 /* When the edge is already inlined, we just need to recurse into
1273 it in order to fully flatten the leaves. */
1274 if (!e->inline_failed)
1276 cgraph_flatten (e->callee);
1280 if (cgraph_recursive_inlining_p (node, e->callee, &e->inline_failed))
1283 fprintf (dump_file, "Not inlining: recursive call.\n");
1287 if (!tree_can_inline_p (e))
1290 fprintf (dump_file, "Not inlining: %s",
1291 cgraph_inline_failed_string (e->inline_failed));
1295 /* Inline the edge and flatten the inline clone. Avoid
1296 recursing through the original node if the node was cloned. */
1298 fprintf (dump_file, " Inlining %s into %s.\n",
1299 cgraph_node_name (e->callee),
1300 cgraph_node_name (e->caller));
1301 orig_callee = e->callee;
1302 cgraph_mark_inline_edge (e, true, NULL);
1303 if (e->callee != orig_callee)
1304 orig_callee->aux = (void *)(size_t) INLINE_ALL;
1305 cgraph_flatten (e->callee);
1306 if (e->callee != orig_callee)
1307 orig_callee->aux = NULL;
1313 /* Decide on the inlining. We do so in the topological order to avoid
1314 expenses on updating data structures. */
1317 cgraph_decide_inlining (void)
1319 struct cgraph_node *node;
1321 struct cgraph_node **order =
1322 XCNEWVEC (struct cgraph_node *, cgraph_n_nodes);
1325 int initial_size = 0;
1327 cgraph_remove_function_insertion_hook (function_insertion_hook_holder);
1328 if (in_lto_p && flag_indirect_inlining)
1329 ipa_update_after_lto_read ();
1330 if (flag_indirect_inlining)
1331 ipa_create_all_structures_for_iinln ();
1335 for (node = cgraph_nodes; node; node = node->next)
1338 struct cgraph_edge *e;
1340 gcc_assert (inline_summary (node)->self_size == node->global.size);
1341 initial_size += node->global.size;
1342 for (e = node->callees; e; e = e->next_callee)
1343 if (max_count < e->count)
1344 max_count = e->count;
1345 if (max_benefit < inline_summary (node)->time_inlining_benefit)
1346 max_benefit = inline_summary (node)->time_inlining_benefit;
1348 gcc_assert (in_lto_p
1350 || (profile_info && flag_branch_probabilities));
1351 overall_size = initial_size;
1353 nnodes = cgraph_postorder (order);
1357 "\nDeciding on inlining. Starting with size %i.\n",
1360 for (node = cgraph_nodes; node; node = node->next)
1364 fprintf (dump_file, "\nFlattening functions:\n");
1366 /* In the first pass handle functions to be flattened. Do this with
1367 a priority so none of our later choices will make this impossible. */
1368 for (i = nnodes - 1; i >= 0; i--)
1372 /* Handle nodes to be flattened, but don't update overall unit
1373 size. Calling the incremental inliner here is lame,
1374 a simple worklist should be enough. What should be left
1375 here from the early inliner (if it runs) is cyclic cases.
1376 Ideally when processing callees we stop inlining at the
1377 entry of cycles, possibly cloning that entry point and
1378 try to flatten itself turning it into a self-recursive
1380 if (lookup_attribute ("flatten",
1381 DECL_ATTRIBUTES (node->decl)) != NULL)
1385 "Flattening %s\n", cgraph_node_name (node));
1386 cgraph_flatten (node);
1390 cgraph_decide_inlining_of_small_functions ();
1392 if (flag_inline_functions_called_once)
1395 fprintf (dump_file, "\nDeciding on functions called once:\n");
1397 /* And finally decide what functions are called once. */
1398 for (i = nnodes - 1; i >= 0; i--)
1403 && !node->callers->next_caller
1404 && cgraph_only_called_directly_p (node)
1405 && node->local.inlinable
1406 && node->callers->inline_failed
1407 && node->callers->caller != node
1408 && node->callers->caller->global.inlined_to != node
1409 && !node->callers->call_stmt_cannot_inline_p
1410 && !DECL_EXTERNAL (node->decl)
1411 && !DECL_COMDAT (node->decl))
1413 cgraph_inline_failed_t reason;
1414 old_size = overall_size;
1418 "\nConsidering %s size %i.\n",
1419 cgraph_node_name (node), node->global.size);
1421 " Called once from %s %i insns.\n",
1422 cgraph_node_name (node->callers->caller),
1423 node->callers->caller->global.size);
1426 if (cgraph_check_inline_limits (node->callers->caller, node,
1429 struct cgraph_node *caller = node->callers->caller;
1430 cgraph_mark_inline (node->callers);
1433 " Inlined into %s which now has %i size"
1434 " for a net change of %+i size.\n",
1435 cgraph_node_name (caller),
1436 caller->global.size,
1437 overall_size - old_size);
1443 " Not inlining: %s.\n",
1444 cgraph_inline_failed_string (reason));
1450 /* Free ipa-prop structures if they are no longer needed. */
1451 if (flag_indirect_inlining)
1452 ipa_free_all_structures_after_iinln ();
1456 "\nInlined %i calls, eliminated %i functions, "
1457 "size %i turned to %i size.\n\n",
1458 ncalls_inlined, nfunctions_inlined, initial_size,
1464 /* Return true when N is leaf function. Accept cheap (pure&const) builtins
1465 in leaf functions. */
1467 leaf_node_p (struct cgraph_node *n)
1469 struct cgraph_edge *e;
1470 for (e = n->callees; e; e = e->next_callee)
1471 if (!DECL_BUILT_IN (e->callee->decl)
1472 || (!TREE_READONLY (e->callee->decl)
1473 || DECL_PURE_P (e->callee->decl)))
1478 /* Decide on the inlining. We do so in the topological order to avoid
1479 expenses on updating data structures. */
1482 cgraph_decide_inlining_incrementally (struct cgraph_node *node,
1483 enum inlining_mode mode)
1485 struct cgraph_edge *e;
1486 bool inlined = false;
1487 cgraph_inline_failed_t failed_reason;
1489 #ifdef ENABLE_CHECKING
1490 verify_cgraph_node (node);
1493 if (mode != INLINE_ALWAYS_INLINE && mode != INLINE_SIZE_NORECURSIVE
1494 && lookup_attribute ("flatten", DECL_ATTRIBUTES (node->decl)) != NULL)
1497 fprintf (dump_file, "Incrementally flattening %s\n",
1498 cgraph_node_name (node));
1502 /* First of all look for always inline functions. */
1503 if (mode != INLINE_SIZE_NORECURSIVE)
1504 for (e = node->callees; e; e = e->next_callee)
1506 if (!e->callee->local.disregard_inline_limits
1507 && (mode != INLINE_ALL || !e->callee->local.inlinable))
1509 if (e->call_stmt_cannot_inline_p)
1513 "Considering to always inline inline candidate %s.\n",
1514 cgraph_node_name (e->callee));
1515 if (cgraph_recursive_inlining_p (node, e->callee, &e->inline_failed))
1518 fprintf (dump_file, "Not inlining: recursive call.\n");
1521 if (!tree_can_inline_p (e))
1526 cgraph_inline_failed_string (e->inline_failed));
1529 if (gimple_in_ssa_p (DECL_STRUCT_FUNCTION (node->decl))
1530 != gimple_in_ssa_p (DECL_STRUCT_FUNCTION (e->callee->decl)))
1533 fprintf (dump_file, "Not inlining: SSA form does not match.\n");
1536 if (!e->callee->analyzed)
1540 "Not inlining: Function body no longer available.\n");
1545 fprintf (dump_file, " Inlining %s into %s.\n",
1546 cgraph_node_name (e->callee),
1547 cgraph_node_name (e->caller));
1548 cgraph_mark_inline (e);
1552 /* Now do the automatic inlining. */
1553 if (mode != INLINE_ALL && mode != INLINE_ALWAYS_INLINE
1554 /* Never inline regular functions into always-inline functions
1555 during incremental inlining. */
1556 && !node->local.disregard_inline_limits)
1558 bitmap visited = BITMAP_ALLOC (NULL);
1559 for (e = node->callees; e; e = e->next_callee)
1561 int allowed_growth = 0;
1562 if (!e->callee->local.inlinable
1563 || !e->inline_failed
1564 || e->callee->local.disregard_inline_limits)
1566 /* We are inlining a function to all call-sites in node
1567 or to none. So visit each candidate only once. */
1568 if (!bitmap_set_bit (visited, e->callee->uid))
1571 fprintf (dump_file, "Considering inline candidate %s.\n",
1572 cgraph_node_name (e->callee));
1573 if (cgraph_recursive_inlining_p (node, e->callee, &e->inline_failed))
1576 fprintf (dump_file, "Not inlining: recursive call.\n");
1579 if (gimple_in_ssa_p (DECL_STRUCT_FUNCTION (node->decl))
1580 != gimple_in_ssa_p (DECL_STRUCT_FUNCTION (e->callee->decl)))
1584 "Not inlining: SSA form does not match.\n");
1588 if (cgraph_maybe_hot_edge_p (e) && leaf_node_p (e->callee)
1589 && optimize_function_for_speed_p (cfun))
1590 allowed_growth = PARAM_VALUE (PARAM_EARLY_INLINING_INSNS);
1592 /* When the function body would grow and inlining the function
1593 won't eliminate the need for offline copy of the function,
1595 if (((mode == INLINE_SIZE || mode == INLINE_SIZE_NORECURSIVE)
1596 || (!flag_inline_functions
1597 && !DECL_DECLARED_INLINE_P (e->callee->decl)))
1598 && (cgraph_estimate_size_after_inlining (1, e->caller, e->callee)
1599 > e->caller->global.size + allowed_growth)
1600 && cgraph_estimate_growth (e->callee) > allowed_growth)
1604 "Not inlining: code size would grow by %i.\n",
1605 cgraph_estimate_size_after_inlining (1, e->caller,
1607 - e->caller->global.size);
1610 if (!cgraph_check_inline_limits (node, e->callee, &e->inline_failed,
1612 || e->call_stmt_cannot_inline_p)
1615 fprintf (dump_file, "Not inlining: %s.\n",
1616 cgraph_inline_failed_string (e->inline_failed));
1619 if (!e->callee->analyzed)
1623 "Not inlining: Function body no longer available.\n");
1626 if (!tree_can_inline_p (e))
1630 "Not inlining: %s.",
1631 cgraph_inline_failed_string (e->inline_failed));
1634 if (cgraph_default_inline_p (e->callee, &failed_reason))
1637 fprintf (dump_file, " Inlining %s into %s.\n",
1638 cgraph_node_name (e->callee),
1639 cgraph_node_name (e->caller));
1640 cgraph_mark_inline (e);
1644 BITMAP_FREE (visited);
1649 /* Because inlining might remove no-longer reachable nodes, we need to
1650 keep the array visible to garbage collector to avoid reading collected
1653 static GTY ((length ("nnodes"))) struct cgraph_node **order;
1655 /* Do inlining of small functions. Doing so early helps profiling and other
1656 passes to be somewhat more effective and avoids some code duplication in
1657 later real inlining pass for testcases with very many function calls. */
1659 cgraph_early_inlining (void)
1661 struct cgraph_node *node = cgraph_node (current_function_decl);
1662 unsigned int todo = 0;
1665 if (sorrycount || errorcount)
1670 || !flag_early_inlining)
1672 /* When not optimizing or not inlining inline only always-inline
1674 cgraph_decide_inlining_incrementally (node, INLINE_ALWAYS_INLINE);
1675 timevar_push (TV_INTEGRATION);
1676 todo |= optimize_inline_calls (current_function_decl);
1677 timevar_pop (TV_INTEGRATION);
1681 if (lookup_attribute ("flatten",
1682 DECL_ATTRIBUTES (node->decl)) != NULL)
1686 "Flattening %s\n", cgraph_node_name (node));
1687 cgraph_flatten (node);
1688 timevar_push (TV_INTEGRATION);
1689 todo |= optimize_inline_calls (current_function_decl);
1690 timevar_pop (TV_INTEGRATION);
1692 /* We iterate incremental inlining to get trivial cases of indirect
1694 while (iterations < PARAM_VALUE (PARAM_EARLY_INLINER_MAX_ITERATIONS)
1695 && cgraph_decide_inlining_incrementally (node,
1697 ? INLINE_SIZE_NORECURSIVE
1700 timevar_push (TV_INTEGRATION);
1701 todo |= optimize_inline_calls (current_function_decl);
1703 timevar_pop (TV_INTEGRATION);
1706 fprintf (dump_file, "Iterations: %i\n", iterations);
1709 cfun->always_inline_functions_inlined = true;
1714 struct gimple_opt_pass pass_early_inline =
1718 "einline", /* name */
1720 cgraph_early_inlining, /* execute */
1723 0, /* static_pass_number */
1724 TV_INLINE_HEURISTICS, /* tv_id */
1725 0, /* properties_required */
1726 0, /* properties_provided */
1727 0, /* properties_destroyed */
1728 0, /* todo_flags_start */
1729 TODO_dump_func /* todo_flags_finish */
1733 /* When inlining shall be performed. */
1735 cgraph_gate_ipa_early_inlining (void)
1737 return (flag_early_inlining
1739 && (flag_branch_probabilities || flag_test_coverage
1740 || profile_arc_flag));
1743 /* IPA pass wrapper for early inlining pass. We need to run early inlining
1744 before tree profiling so we have stand alone IPA pass for doing so. */
1745 struct simple_ipa_opt_pass pass_ipa_early_inline =
1749 "einline_ipa", /* name */
1750 cgraph_gate_ipa_early_inlining, /* gate */
1754 0, /* static_pass_number */
1755 TV_INLINE_HEURISTICS, /* tv_id */
1756 0, /* properties_required */
1757 0, /* properties_provided */
1758 0, /* properties_destroyed */
1759 0, /* todo_flags_start */
1760 TODO_dump_cgraph /* todo_flags_finish */
1764 /* See if statement might disappear after inlining. We are not terribly
1765 sophisficated, basically looking for simple abstraction penalty wrappers. */
1768 likely_eliminated_by_inlining_p (gimple stmt)
1770 enum gimple_code code = gimple_code (stmt);
1776 if (gimple_num_ops (stmt) != 2)
1779 /* Casts of parameters, loads from parameters passed by reference
1780 and stores to return value or parameters are probably free after
1782 if (gimple_assign_rhs_code (stmt) == CONVERT_EXPR
1783 || gimple_assign_rhs_code (stmt) == NOP_EXPR
1784 || gimple_assign_rhs_code (stmt) == VIEW_CONVERT_EXPR
1785 || gimple_assign_rhs_class (stmt) == GIMPLE_SINGLE_RHS)
1787 tree rhs = gimple_assign_rhs1 (stmt);
1788 tree lhs = gimple_assign_lhs (stmt);
1789 tree inner_rhs = rhs;
1790 tree inner_lhs = lhs;
1791 bool rhs_free = false;
1792 bool lhs_free = false;
1794 while (handled_component_p (inner_lhs) || TREE_CODE (inner_lhs) == INDIRECT_REF)
1795 inner_lhs = TREE_OPERAND (inner_lhs, 0);
1796 while (handled_component_p (inner_rhs)
1797 || TREE_CODE (inner_rhs) == ADDR_EXPR || TREE_CODE (inner_rhs) == INDIRECT_REF)
1798 inner_rhs = TREE_OPERAND (inner_rhs, 0);
1801 if (TREE_CODE (inner_rhs) == PARM_DECL
1802 || (TREE_CODE (inner_rhs) == SSA_NAME
1803 && SSA_NAME_IS_DEFAULT_DEF (inner_rhs)
1804 && TREE_CODE (SSA_NAME_VAR (inner_rhs)) == PARM_DECL))
1806 if (rhs_free && is_gimple_reg (lhs))
1808 if (((TREE_CODE (inner_lhs) == PARM_DECL
1809 || (TREE_CODE (inner_lhs) == SSA_NAME
1810 && SSA_NAME_IS_DEFAULT_DEF (inner_lhs)
1811 && TREE_CODE (SSA_NAME_VAR (inner_lhs)) == PARM_DECL))
1812 && inner_lhs != lhs)
1813 || TREE_CODE (inner_lhs) == RESULT_DECL
1814 || (TREE_CODE (inner_lhs) == SSA_NAME
1815 && TREE_CODE (SSA_NAME_VAR (inner_lhs)) == RESULT_DECL))
1817 if (lhs_free && (is_gimple_reg (rhs) || is_gimple_min_invariant (rhs)))
1819 if (lhs_free && rhs_free)
1828 /* Compute function body size parameters for NODE. */
1831 estimate_function_body_sizes (struct cgraph_node *node)
1834 gcov_type time_inlining_benefit = 0;
1836 int size_inlining_benefit = 0;
1838 gimple_stmt_iterator bsi;
1839 struct function *my_function = DECL_STRUCT_FUNCTION (node->decl);
1842 tree funtype = TREE_TYPE (node->decl);
1845 fprintf (dump_file, "Analyzing function body size: %s\n",
1846 cgraph_node_name (node));
1848 gcc_assert (my_function && my_function->cfg);
1849 FOR_EACH_BB_FN (bb, my_function)
1851 freq = compute_call_stmt_bb_frequency (node->decl, bb);
1852 for (bsi = gsi_start_bb (bb); !gsi_end_p (bsi); gsi_next (&bsi))
1854 gimple stmt = gsi_stmt (bsi);
1855 int this_size = estimate_num_insns (stmt, &eni_size_weights);
1856 int this_time = estimate_num_insns (stmt, &eni_time_weights);
1858 if (dump_file && (dump_flags & TDF_DETAILS))
1860 fprintf (dump_file, " freq:%6i size:%3i time:%3i ",
1861 freq, this_size, this_time);
1862 print_gimple_stmt (dump_file, stmt, 0, 0);
1867 if (likely_eliminated_by_inlining_p (stmt))
1869 size_inlining_benefit += this_size;
1870 time_inlining_benefit += this_time;
1871 if (dump_file && (dump_flags & TDF_DETAILS))
1872 fprintf (dump_file, " Likely eliminated\n");
1874 gcc_assert (time >= 0);
1875 gcc_assert (size >= 0);
1878 time = (time + CGRAPH_FREQ_BASE / 2) / CGRAPH_FREQ_BASE;
1879 time_inlining_benefit = ((time_inlining_benefit + CGRAPH_FREQ_BASE / 2)
1880 / CGRAPH_FREQ_BASE);
1882 fprintf (dump_file, "Overall function body time: %i-%i size: %i-%i\n",
1883 (int)time, (int)time_inlining_benefit,
1884 size, size_inlining_benefit);
1885 time_inlining_benefit += eni_time_weights.call_cost;
1886 size_inlining_benefit += eni_size_weights.call_cost;
1887 if (!VOID_TYPE_P (TREE_TYPE (funtype)))
1889 int cost = estimate_move_cost (TREE_TYPE (funtype));
1890 time_inlining_benefit += cost;
1891 size_inlining_benefit += cost;
1893 for (arg = DECL_ARGUMENTS (node->decl); arg; arg = TREE_CHAIN (arg))
1894 if (!VOID_TYPE_P (TREE_TYPE (arg)))
1896 int cost = estimate_move_cost (TREE_TYPE (arg));
1897 time_inlining_benefit += cost;
1898 size_inlining_benefit += cost;
1900 if (time_inlining_benefit > MAX_TIME)
1901 time_inlining_benefit = MAX_TIME;
1902 if (time > MAX_TIME)
1904 inline_summary (node)->self_time = time;
1905 inline_summary (node)->self_size = size;
1907 fprintf (dump_file, "With function call overhead time: %i-%i size: %i-%i\n",
1908 (int)time, (int)time_inlining_benefit,
1909 size, size_inlining_benefit);
1910 inline_summary (node)->time_inlining_benefit = time_inlining_benefit;
1911 inline_summary (node)->size_inlining_benefit = size_inlining_benefit;
1914 /* Compute parameters of functions used by inliner. */
1916 compute_inline_parameters (struct cgraph_node *node)
1918 HOST_WIDE_INT self_stack_size;
1920 gcc_assert (!node->global.inlined_to);
1922 /* Estimate the stack size for the function. But not at -O0
1923 because estimated_stack_frame_size is a quadratic problem. */
1924 self_stack_size = optimize ? estimated_stack_frame_size () : 0;
1925 inline_summary (node)->estimated_self_stack_size = self_stack_size;
1926 node->global.estimated_stack_size = self_stack_size;
1927 node->global.stack_frame_offset = 0;
1929 /* Can this function be inlined at all? */
1930 node->local.inlinable = tree_inlinable_function_p (node->decl);
1931 if (node->local.inlinable && !node->local.disregard_inline_limits)
1932 node->local.disregard_inline_limits
1933 = DECL_DISREGARD_INLINE_LIMITS (node->decl);
1934 estimate_function_body_sizes (node);
1935 /* Inlining characteristics are maintained by the cgraph_mark_inline. */
1936 node->global.time = inline_summary (node)->self_time;
1937 node->global.size = inline_summary (node)->self_size;
1942 /* Compute parameters of functions used by inliner using
1943 current_function_decl. */
1945 compute_inline_parameters_for_current (void)
1947 compute_inline_parameters (cgraph_node (current_function_decl));
1951 struct gimple_opt_pass pass_inline_parameters =
1955 "inline_param", /* name */
1957 compute_inline_parameters_for_current,/* execute */
1960 0, /* static_pass_number */
1961 TV_INLINE_HEURISTICS, /* tv_id */
1962 0, /* properties_required */
1963 0, /* properties_provided */
1964 0, /* properties_destroyed */
1965 0, /* todo_flags_start */
1966 0 /* todo_flags_finish */
1970 /* This function performs intraprocedural analyzis in NODE that is required to
1971 inline indirect calls. */
1973 inline_indirect_intraprocedural_analysis (struct cgraph_node *node)
1975 ipa_initialize_node_params (node);
1976 ipa_detect_param_modifications (node);
1977 ipa_analyze_params_uses (node);
1978 ipa_compute_jump_functions (node);
1982 ipa_print_node_params (dump_file, node);
1983 ipa_print_node_jump_functions (dump_file, node);
1987 /* Note function body size. */
1989 analyze_function (struct cgraph_node *node)
1991 push_cfun (DECL_STRUCT_FUNCTION (node->decl));
1992 current_function_decl = node->decl;
1994 compute_inline_parameters (node);
1995 if (flag_indirect_inlining)
1996 inline_indirect_intraprocedural_analysis (node);
1998 current_function_decl = NULL;
2002 /* Called when new function is inserted to callgraph late. */
2004 add_new_function (struct cgraph_node *node, void *data ATTRIBUTE_UNUSED)
2006 analyze_function (node);
2009 /* Note function body size. */
2011 inline_generate_summary (void)
2013 struct cgraph_node *node;
2015 function_insertion_hook_holder =
2016 cgraph_add_function_insertion_hook (&add_new_function, NULL);
2018 if (flag_indirect_inlining)
2020 ipa_register_cgraph_hooks ();
2021 ipa_check_create_node_params ();
2022 ipa_check_create_edge_args ();
2025 for (node = cgraph_nodes; node; node = node->next)
2027 analyze_function (node);
2032 /* Apply inline plan to function. */
2034 inline_transform (struct cgraph_node *node)
2036 unsigned int todo = 0;
2037 struct cgraph_edge *e;
2039 /* FIXME: Currently the passmanager is adding inline transform more than once to some
2040 clones. This needs revisiting after WPA cleanups. */
2041 if (cfun->after_inlining)
2044 /* We might need the body of this function so that we can expand
2045 it inline somewhere else. */
2046 if (cgraph_preserve_function_body_p (node->decl))
2047 save_inline_function_body (node);
2049 for (e = node->callees; e; e = e->next_callee)
2050 if (!e->inline_failed || warn_inline)
2055 timevar_push (TV_INTEGRATION);
2056 todo = optimize_inline_calls (current_function_decl);
2057 timevar_pop (TV_INTEGRATION);
2059 cfun->always_inline_functions_inlined = true;
2060 cfun->after_inlining = true;
2061 return todo | execute_fixup_cfg ();
2064 /* Read inline summary. Jump functions are shared among ipa-cp
2065 and inliner, so when ipa-cp is active, we don't need to write them
2069 inline_read_summary (void)
2071 if (flag_indirect_inlining)
2073 ipa_register_cgraph_hooks ();
2075 ipa_prop_read_jump_functions ();
2077 function_insertion_hook_holder =
2078 cgraph_add_function_insertion_hook (&add_new_function, NULL);
2081 /* Write inline summary for node in SET.
2082 Jump functions are shared among ipa-cp and inliner, so when ipa-cp is
2083 active, we don't need to write them twice. */
2086 inline_write_summary (cgraph_node_set set,
2087 varpool_node_set vset ATTRIBUTE_UNUSED)
2089 if (flag_indirect_inlining && !flag_ipa_cp)
2090 ipa_prop_write_jump_functions (set);
2093 /* When to run IPA inlining. Inlining of always-inline functions
2094 happens during early inlining. */
2097 gate_cgraph_decide_inlining (void)
2099 /* ??? We'd like to skip this if not optimizing or not inlining as
2100 all always-inline functions have been processed by early
2101 inlining already. But this at least breaks EH with C++ as
2102 we need to unconditionally run fixup_cfg even at -O0.
2103 So leave it on unconditionally for now. */
2107 struct ipa_opt_pass_d pass_ipa_inline =
2111 "inline", /* name */
2112 gate_cgraph_decide_inlining, /* gate */
2113 cgraph_decide_inlining, /* execute */
2116 0, /* static_pass_number */
2117 TV_INLINE_HEURISTICS, /* tv_id */
2118 0, /* properties_required */
2119 0, /* properties_provided */
2120 0, /* properties_destroyed */
2121 TODO_remove_functions, /* todo_flags_finish */
2122 TODO_dump_cgraph | TODO_dump_func
2123 | TODO_remove_functions | TODO_ggc_collect /* todo_flags_finish */
2125 inline_generate_summary, /* generate_summary */
2126 inline_write_summary, /* write_summary */
2127 inline_read_summary, /* read_summary */
2128 NULL, /* write_optimization_summary */
2129 NULL, /* read_optimization_summary */
2130 NULL, /* stmt_fixup */
2132 inline_transform, /* function_transform */
2133 NULL, /* variable_transform */
2137 #include "gt-ipa-inline.h"