1 /* Inlining decision heuristics.
2 Copyright (C) 2003, 2004, 2007, 2008, 2009, 2010, 2011
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_edge 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
96 This is the main pass implementing simple greedy algorithm to do inlining
97 of small functions that results in overall growth of compilation unit and
98 inlining of functions called once. The pass compute just so called inline
99 plan (representation of inlining to be done in callgraph) and unlike early
100 inlining it is not performing the inlining itself.
105 #include "coretypes.h"
108 #include "tree-inline.h"
109 #include "langhooks.h"
112 #include "diagnostic.h"
113 #include "gimple-pretty-print.h"
118 #include "tree-pass.h"
120 #include "coverage.h"
122 #include "tree-flow.h"
124 #include "ipa-prop.h"
127 #define MAX_TIME 1000000000
129 /* Mode incremental inliner operate on:
131 In ALWAYS_INLINE only functions marked
132 always_inline are inlined. This mode is used after detecting cycle during
135 In SIZE mode, only functions that reduce function body size after inlining
136 are inlined, this is used during early inlining.
138 in ALL mode, everything is inlined. This is used during flattening. */
141 INLINE_ALWAYS_INLINE,
142 INLINE_SIZE_NORECURSIVE,
148 cgraph_decide_inlining_incrementally (struct cgraph_node *, enum inlining_mode);
149 static void cgraph_flatten (struct cgraph_node *node);
152 /* Statistics we collect about inlining algorithm. */
153 static int ncalls_inlined;
154 static int nfunctions_inlined;
155 static int overall_size;
156 static gcov_type max_count, max_benefit;
158 /* Holders of ipa cgraph hooks: */
159 static struct cgraph_node_hook_list *function_insertion_hook_holder;
161 static inline struct inline_summary *
162 inline_summary (struct cgraph_node *node)
164 return &node->local.inline_summary;
167 /* Estimate self time of the function after inlining WHAT into TO. */
170 cgraph_estimate_time_after_inlining (int frequency, struct cgraph_node *to,
171 struct cgraph_node *what)
173 gcov_type time = (((gcov_type)what->global.time
174 - inline_summary (what)->time_inlining_benefit)
175 * frequency + CGRAPH_FREQ_BASE / 2) / CGRAPH_FREQ_BASE
184 /* Estimate self size of the function after inlining WHAT into TO. */
187 cgraph_estimate_size_after_inlining (struct cgraph_node *to,
188 struct cgraph_node *what)
190 int size = ((what->global.size - inline_summary (what)->size_inlining_benefit)
192 gcc_assert (size >= 0);
196 /* Scale frequency of NODE edges by FREQ_SCALE and increase loop nest
200 update_noncloned_frequencies (struct cgraph_node *node,
201 int freq_scale, int nest)
203 struct cgraph_edge *e;
205 /* We do not want to ignore high loop nest after freq drops to 0. */
208 for (e = node->callees; e; e = e->next_callee)
210 e->loop_nest += nest;
211 e->frequency = e->frequency * (gcov_type) freq_scale / CGRAPH_FREQ_BASE;
212 if (e->frequency > CGRAPH_FREQ_MAX)
213 e->frequency = CGRAPH_FREQ_MAX;
214 if (!e->inline_failed)
215 update_noncloned_frequencies (e->callee, freq_scale, nest);
219 /* E is expected to be an edge being inlined. Clone destination node of
220 the edge and redirect it to the new clone.
221 DUPLICATE is used for bookkeeping on whether we are actually creating new
222 clones or re-using node originally representing out-of-line function call.
225 cgraph_clone_inlined_nodes (struct cgraph_edge *e, bool duplicate,
226 bool update_original)
232 /* We may eliminate the need for out-of-line copy to be output.
233 In that case just go ahead and re-use it. */
234 if (!e->callee->callers->next_caller
235 /* Recursive inlining never wants the master clone to be overwritten. */
237 /* FIXME: When address is taken of DECL_EXTERNAL function we still can remove its
238 offline copy, but we would need to keep unanalyzed node in the callgraph so
239 references can point to it. */
240 && !e->callee->address_taken
241 && cgraph_can_remove_if_no_direct_calls_p (e->callee)
242 /* Inlining might enable more devirtualizing, so we want to remove
243 those only after all devirtualizable virtual calls are processed.
244 Lacking may edges in callgraph we just preserve them post
246 && !DECL_VIRTUAL_P (e->callee->decl)
247 /* Don't reuse if more than one function shares a comdat group.
248 If the other function(s) are needed, we need to emit even
249 this function out of line. */
250 && !e->callee->same_comdat_group
251 && !cgraph_new_nodes)
253 gcc_assert (!e->callee->global.inlined_to);
254 if (e->callee->analyzed && !DECL_EXTERNAL (e->callee->decl))
256 overall_size -= e->callee->global.size;
257 nfunctions_inlined++;
260 e->callee->local.externally_visible = false;
261 update_noncloned_frequencies (e->callee, e->frequency, e->loop_nest);
265 struct cgraph_node *n;
266 n = cgraph_clone_node (e->callee, e->callee->decl,
267 e->count, e->frequency, e->loop_nest,
268 update_original, NULL);
269 cgraph_redirect_edge_callee (e, n);
273 if (e->caller->global.inlined_to)
274 e->callee->global.inlined_to = e->caller->global.inlined_to;
276 e->callee->global.inlined_to = e->caller;
277 e->callee->global.stack_frame_offset
278 = e->caller->global.stack_frame_offset
279 + inline_summary (e->caller)->estimated_self_stack_size;
280 peak = e->callee->global.stack_frame_offset
281 + inline_summary (e->callee)->estimated_self_stack_size;
282 if (e->callee->global.inlined_to->global.estimated_stack_size < peak)
283 e->callee->global.inlined_to->global.estimated_stack_size = peak;
284 cgraph_propagate_frequency (e->callee);
286 /* Recursively clone all bodies. */
287 for (e = e->callee->callees; e; e = e->next_callee)
288 if (!e->inline_failed)
289 cgraph_clone_inlined_nodes (e, duplicate, update_original);
292 /* Mark edge E as inlined and update callgraph accordingly. UPDATE_ORIGINAL
293 specify whether profile of original function should be updated. If any new
294 indirect edges are discovered in the process, add them to NEW_EDGES, unless
295 it is NULL. Return true iff any new callgraph edges were discovered as a
296 result of inlining. */
299 cgraph_mark_inline_edge (struct cgraph_edge *e, bool update_original,
300 VEC (cgraph_edge_p, heap) **new_edges)
302 int old_size = 0, new_size = 0;
303 struct cgraph_node *to = NULL, *what;
304 struct cgraph_edge *curr = e;
307 /* Don't inline inlined edges. */
308 gcc_assert (e->inline_failed);
309 /* Don't even think of inlining inline clone. */
310 gcc_assert (!e->callee->global.inlined_to);
312 e->inline_failed = CIF_OK;
313 DECL_POSSIBLY_INLINED (e->callee->decl) = true;
315 cgraph_clone_inlined_nodes (e, true, update_original);
320 /* Now update size of caller and all functions caller is inlined into. */
321 for (;e && !e->inline_failed; e = e->caller->callers)
324 old_size = e->caller->global.size;
325 new_size = cgraph_estimate_size_after_inlining (to, what);
326 to->global.size = new_size;
327 to->global.time = cgraph_estimate_time_after_inlining (freq, to, what);
329 gcc_assert (what->global.inlined_to == to);
330 if (new_size > old_size)
331 overall_size += new_size - old_size;
334 /* FIXME: We should remove the optimize check after we ensure we never run
335 IPA passes when not optimizing. */
336 if (flag_indirect_inlining && optimize)
337 return ipa_propagate_indirect_call_infos (curr, new_edges);
342 /* Estimate the growth caused by inlining NODE into all callees. */
345 cgraph_estimate_growth (struct cgraph_node *node)
348 struct cgraph_edge *e;
349 bool self_recursive = false;
351 if (node->global.estimated_growth != INT_MIN)
352 return node->global.estimated_growth;
354 for (e = node->callers; e; e = e->next_caller)
356 if (e->caller == node)
357 self_recursive = true;
358 if (e->inline_failed)
359 growth += (cgraph_estimate_size_after_inlining (e->caller, node)
360 - e->caller->global.size);
363 /* ??? Wrong for non-trivially self recursive functions or cases where
364 we decide to not inline for different reasons, but it is not big deal
365 as in that case we will keep the body around, but we will also avoid
367 if (cgraph_will_be_removed_from_program_if_no_direct_calls (node)
368 && !DECL_EXTERNAL (node->decl) && !self_recursive)
369 growth -= node->global.size;
370 /* COMDAT functions are very often not shared across multiple units since they
371 come from various template instantiations. Take this into account. */
372 else if (DECL_COMDAT (node->decl) && !self_recursive
373 && cgraph_can_remove_if_no_direct_calls_p (node))
374 growth -= (node->global.size
375 * (100 - PARAM_VALUE (PARAM_COMDAT_SHARING_PROBABILITY)) + 50) / 100;
377 node->global.estimated_growth = growth;
381 /* Return false when inlining WHAT into TO is not good idea
382 as it would cause too large growth of function bodies.
383 When ONE_ONLY is true, assume that only one call site is going
384 to be inlined, otherwise figure out how many call sites in
385 TO calls WHAT and verify that all can be inlined.
389 cgraph_check_inline_limits (struct cgraph_node *to, struct cgraph_node *what,
390 cgraph_inline_failed_t *reason)
394 HOST_WIDE_INT stack_size_limit, inlined_stack;
396 if (to->global.inlined_to)
397 to = to->global.inlined_to;
399 /* When inlining large function body called once into small function,
400 take the inlined function as base for limiting the growth. */
401 if (inline_summary (to)->self_size > inline_summary(what)->self_size)
402 limit = inline_summary (to)->self_size;
404 limit = inline_summary (what)->self_size;
406 limit += limit * PARAM_VALUE (PARAM_LARGE_FUNCTION_GROWTH) / 100;
408 /* Check the size after inlining against the function limits. But allow
409 the function to shrink if it went over the limits by forced inlining. */
410 newsize = cgraph_estimate_size_after_inlining (to, what);
411 if (newsize >= to->global.size
412 && newsize > PARAM_VALUE (PARAM_LARGE_FUNCTION_INSNS)
416 *reason = CIF_LARGE_FUNCTION_GROWTH_LIMIT;
420 stack_size_limit = inline_summary (to)->estimated_self_stack_size;
422 stack_size_limit += stack_size_limit * PARAM_VALUE (PARAM_STACK_FRAME_GROWTH) / 100;
424 inlined_stack = (to->global.stack_frame_offset
425 + inline_summary (to)->estimated_self_stack_size
426 + what->global.estimated_stack_size);
427 if (inlined_stack > stack_size_limit
428 && inlined_stack > PARAM_VALUE (PARAM_LARGE_STACK_FRAME))
431 *reason = CIF_LARGE_STACK_FRAME_GROWTH_LIMIT;
437 /* Return true when function N is small enough to be inlined. */
440 cgraph_default_inline_p (struct cgraph_node *n, cgraph_inline_failed_t *reason)
444 if (n->local.disregard_inline_limits)
447 if (!flag_inline_small_functions && !DECL_DECLARED_INLINE_P (decl))
450 *reason = CIF_FUNCTION_NOT_INLINE_CANDIDATE;
456 *reason = CIF_BODY_NOT_AVAILABLE;
459 if (cgraph_function_body_availability (n) <= AVAIL_OVERWRITABLE)
462 *reason = CIF_OVERWRITABLE;
467 if (DECL_DECLARED_INLINE_P (decl))
469 if (n->global.size >= MAX_INLINE_INSNS_SINGLE)
472 *reason = CIF_MAX_INLINE_INSNS_SINGLE_LIMIT;
478 if (n->global.size >= MAX_INLINE_INSNS_AUTO)
481 *reason = CIF_MAX_INLINE_INSNS_AUTO_LIMIT;
489 /* Return true when inlining WHAT would create recursive inlining.
490 We call recursive inlining all cases where same function appears more than
491 once in the single recursion nest path in the inline graph. */
494 cgraph_recursive_inlining_p (struct cgraph_node *to,
495 struct cgraph_node *what,
496 cgraph_inline_failed_t *reason)
499 if (to->global.inlined_to)
500 recursive = what->decl == to->global.inlined_to->decl;
502 recursive = what->decl == to->decl;
503 /* Marking recursive function inline has sane semantic and thus we should
505 if (recursive && reason)
506 *reason = (what->local.disregard_inline_limits
507 ? CIF_RECURSIVE_INLINING : CIF_UNSPECIFIED);
511 /* A cost model driving the inlining heuristics in a way so the edges with
512 smallest badness are inlined first. After each inlining is performed
513 the costs of all caller edges of nodes affected are recomputed so the
514 metrics may accurately depend on values such as number of inlinable callers
515 of the function or function body size. */
518 cgraph_edge_badness (struct cgraph_edge *edge, bool dump)
522 (cgraph_estimate_size_after_inlining (edge->caller, edge->callee)
523 - edge->caller->global.size);
525 if (edge->callee->local.disregard_inline_limits)
530 fprintf (dump_file, " Badness calculation for %s -> %s\n",
531 cgraph_node_name (edge->caller),
532 cgraph_node_name (edge->callee));
533 fprintf (dump_file, " growth %i, time %i-%i, size %i-%i\n",
535 edge->callee->global.time,
536 inline_summary (edge->callee)->time_inlining_benefit,
537 edge->callee->global.size,
538 inline_summary (edge->callee)->size_inlining_benefit);
541 /* Always prefer inlining saving code size. */
544 badness = INT_MIN - growth;
546 fprintf (dump_file, " %i: Growth %i < 0\n", (int) badness,
550 /* When profiling is available, base priorities -(#calls / growth).
551 So we optimize for overall number of "executed" inlined calls. */
556 ((double) edge->count * INT_MIN / max_count / (max_benefit + 1)) *
557 (inline_summary (edge->callee)->time_inlining_benefit + 1)) / growth;
561 " %i (relative %f): profile info. Relative count %f"
562 " * Relative benefit %f\n",
563 (int) badness, (double) badness / INT_MIN,
564 (double) edge->count / max_count,
565 (double) (inline_summary (edge->callee)->
566 time_inlining_benefit + 1) / (max_benefit + 1));
570 /* When function local profile is available, base priorities on
571 growth / frequency, so we optimize for overall frequency of inlined
572 calls. This is not too accurate since while the call might be frequent
573 within function, the function itself is infrequent.
575 Other objective to optimize for is number of different calls inlined.
576 We add the estimated growth after inlining all functions to bias the
577 priorities slightly in this direction (so fewer times called functions
578 of the same size gets priority). */
579 else if (flag_guess_branch_prob)
581 int div = edge->frequency * 100 / CGRAPH_FREQ_BASE + 1;
584 badness = growth * 10000;
586 MIN (100 * inline_summary (edge->callee)->time_inlining_benefit /
587 (edge->callee->global.time + 1) +1, 100);
591 /* Decrease badness if call is nested. */
592 /* Compress the range so we don't overflow. */
594 div = 10000 + ceil_log2 (div) - 8;
599 growth_for_all = cgraph_estimate_growth (edge->callee);
600 badness += growth_for_all;
601 if (badness > INT_MAX)
606 " %i: guessed profile. frequency %i, overall growth %i,"
607 " benefit %i%%, divisor %i\n",
608 (int) badness, edge->frequency, growth_for_all, benefitperc, div);
611 /* When function local profile is not available or it does not give
612 useful information (ie frequency is zero), base the cost on
613 loop nest and overall size growth, so we optimize for overall number
614 of functions fully inlined in program. */
617 int nest = MIN (edge->loop_nest, 8);
618 badness = cgraph_estimate_growth (edge->callee) * 256;
620 /* Decrease badness if call is nested. */
628 fprintf (dump_file, " %i: no profile. nest %i\n", (int) badness,
632 /* Ensure that we did not overflow in all the fixed point math above. */
633 gcc_assert (badness >= INT_MIN);
634 gcc_assert (badness <= INT_MAX - 1);
635 /* Make recursive inlining happen always after other inlining is done. */
636 if (cgraph_recursive_inlining_p (edge->caller, edge->callee, NULL))
642 /* Recompute badness of EDGE and update its key in HEAP if needed. */
644 update_edge_key (fibheap_t heap, struct cgraph_edge *edge)
646 int badness = cgraph_edge_badness (edge, false);
649 fibnode_t n = (fibnode_t) edge->aux;
650 gcc_checking_assert (n->data == edge);
652 /* fibheap_replace_key only decrease the keys.
653 When we increase the key we do not update heap
654 and instead re-insert the element once it becomes
655 a minimum of heap. */
656 if (badness < n->key)
658 fibheap_replace_key (heap, n, badness);
659 gcc_checking_assert (n->key == badness);
663 edge->aux = fibheap_insert (heap, badness, edge);
666 /* Recompute heap nodes for each of caller edge. */
669 update_caller_keys (fibheap_t heap, struct cgraph_node *node,
670 bitmap updated_nodes)
672 struct cgraph_edge *edge;
673 cgraph_inline_failed_t failed_reason;
675 if (!node->local.inlinable
676 || cgraph_function_body_availability (node) <= AVAIL_OVERWRITABLE
677 || node->global.inlined_to)
679 if (!bitmap_set_bit (updated_nodes, node->uid))
681 node->global.estimated_growth = INT_MIN;
683 /* See if there is something to do. */
684 for (edge = node->callers; edge; edge = edge->next_caller)
685 if (edge->inline_failed)
689 /* Prune out edges we won't inline into anymore. */
690 if (!cgraph_default_inline_p (node, &failed_reason))
692 for (; edge; edge = edge->next_caller)
695 fibheap_delete_node (heap, (fibnode_t) edge->aux);
697 if (edge->inline_failed)
698 edge->inline_failed = failed_reason;
703 for (; edge; edge = edge->next_caller)
704 if (edge->inline_failed)
705 update_edge_key (heap, edge);
708 /* Recompute heap nodes for each uninlined call.
709 This is used when we know that edge badnesses are going only to increase
710 (we introduced new call site) and thus all we need is to insert newly
711 created edges into heap. */
714 update_callee_keys (fibheap_t heap, struct cgraph_node *node,
715 bitmap updated_nodes)
717 struct cgraph_edge *e = node->callees;
718 node->global.estimated_growth = INT_MIN;
723 if (!e->inline_failed && e->callee->callees)
724 e = e->callee->callees;
728 && e->callee->local.inlinable
729 && cgraph_function_body_availability (e->callee) >= AVAIL_AVAILABLE
730 && !bitmap_bit_p (updated_nodes, e->callee->uid))
732 node->global.estimated_growth = INT_MIN;
733 /* If function becomes uninlinable, we need to remove it from the heap. */
734 if (!cgraph_default_inline_p (e->callee, &e->inline_failed))
735 update_caller_keys (heap, e->callee, updated_nodes);
737 /* Otherwise update just edge E. */
738 update_edge_key (heap, e);
746 if (e->caller == node)
748 e = e->caller->callers;
750 while (!e->next_callee);
756 /* Recompute heap nodes for each of caller edges of each of callees.
757 Walk recursively into all inline clones. */
760 update_all_callee_keys (fibheap_t heap, struct cgraph_node *node,
761 bitmap updated_nodes)
763 struct cgraph_edge *e = node->callees;
764 node->global.estimated_growth = INT_MIN;
769 if (!e->inline_failed && e->callee->callees)
770 e = e->callee->callees;
773 if (e->inline_failed)
774 update_caller_keys (heap, e->callee, updated_nodes);
781 if (e->caller == node)
783 e = e->caller->callers;
785 while (!e->next_callee);
791 /* Enqueue all recursive calls from NODE into priority queue depending on
792 how likely we want to recursively inline the call. */
795 lookup_recursive_calls (struct cgraph_node *node, struct cgraph_node *where,
799 struct cgraph_edge *e;
800 for (e = where->callees; e; e = e->next_callee)
801 if (e->callee == node)
803 /* When profile feedback is available, prioritize by expected number
804 of calls. Without profile feedback we maintain simple queue
805 to order candidates via recursive depths. */
806 fibheap_insert (heap,
807 !max_count ? priority++
808 : -(e->count / ((max_count + (1<<24) - 1) / (1<<24))),
811 for (e = where->callees; e; e = e->next_callee)
812 if (!e->inline_failed)
813 lookup_recursive_calls (node, e->callee, heap);
816 /* Decide on recursive inlining: in the case function has recursive calls,
817 inline until body size reaches given argument. If any new indirect edges
818 are discovered in the process, add them to *NEW_EDGES, unless NEW_EDGES
822 cgraph_decide_recursive_inlining (struct cgraph_node *node,
823 VEC (cgraph_edge_p, heap) **new_edges)
825 int limit = PARAM_VALUE (PARAM_MAX_INLINE_INSNS_RECURSIVE_AUTO);
826 int max_depth = PARAM_VALUE (PARAM_MAX_INLINE_RECURSIVE_DEPTH_AUTO);
827 int probability = PARAM_VALUE (PARAM_MIN_INLINE_RECURSIVE_PROBABILITY);
829 struct cgraph_edge *e;
830 struct cgraph_node *master_clone, *next;
834 /* It does not make sense to recursively inline always-inline functions
835 as we are going to sorry() on the remaining calls anyway. */
836 if (node->local.disregard_inline_limits
837 && lookup_attribute ("always_inline", DECL_ATTRIBUTES (node->decl)))
840 if (optimize_function_for_size_p (DECL_STRUCT_FUNCTION (node->decl))
841 || (!flag_inline_functions && !DECL_DECLARED_INLINE_P (node->decl)))
844 if (DECL_DECLARED_INLINE_P (node->decl))
846 limit = PARAM_VALUE (PARAM_MAX_INLINE_INSNS_RECURSIVE);
847 max_depth = PARAM_VALUE (PARAM_MAX_INLINE_RECURSIVE_DEPTH);
850 /* Make sure that function is small enough to be considered for inlining. */
852 || cgraph_estimate_size_after_inlining (node, node) >= limit)
854 heap = fibheap_new ();
855 lookup_recursive_calls (node, node, heap);
856 if (fibheap_empty (heap))
858 fibheap_delete (heap);
864 " Performing recursive inlining on %s\n",
865 cgraph_node_name (node));
867 /* We need original clone to copy around. */
868 master_clone = cgraph_clone_node (node, node->decl,
869 node->count, CGRAPH_FREQ_BASE, 1,
871 for (e = master_clone->callees; e; e = e->next_callee)
872 if (!e->inline_failed)
873 cgraph_clone_inlined_nodes (e, true, false);
875 /* Do the inlining and update list of recursive call during process. */
876 while (!fibheap_empty (heap)
877 && (cgraph_estimate_size_after_inlining (node, master_clone)
880 struct cgraph_edge *curr
881 = (struct cgraph_edge *) fibheap_extract_min (heap);
882 struct cgraph_node *cnode;
885 for (cnode = curr->caller;
886 cnode->global.inlined_to; cnode = cnode->callers->caller)
887 if (node->decl == curr->callee->decl)
889 if (depth > max_depth)
893 " maximal depth reached\n");
897 if (max_count && node->count)
899 if (!cgraph_maybe_hot_edge_p (curr))
902 fprintf (dump_file, " Not inlining cold call\n");
905 if (curr->count * 100 / node->count < probability)
909 " Probability of edge is too small\n");
917 " Inlining call of depth %i", depth);
920 fprintf (dump_file, " called approx. %.2f times per call",
921 (double)curr->count / node->count);
923 fprintf (dump_file, "\n");
925 cgraph_redirect_edge_callee (curr, master_clone);
926 cgraph_mark_inline_edge (curr, false, new_edges);
927 lookup_recursive_calls (node, curr->callee, heap);
930 if (!fibheap_empty (heap) && dump_file)
931 fprintf (dump_file, " Recursive inlining growth limit met.\n");
933 fibheap_delete (heap);
936 "\n Inlined %i times, body grown from size %i to %i, time %i to %i\n", n,
937 master_clone->global.size, node->global.size,
938 master_clone->global.time, node->global.time);
940 /* Remove master clone we used for inlining. We rely that clones inlined
941 into master clone gets queued just before master clone so we don't
943 for (node = cgraph_nodes; node != master_clone;
947 if (node->global.inlined_to == master_clone)
948 cgraph_remove_node (node);
950 cgraph_remove_node (master_clone);
951 /* FIXME: Recursive inlining actually reduces number of calls of the
952 function. At this place we should probably walk the function and
953 inline clones and compensate the counts accordingly. This probably
954 doesn't matter much in practice. */
958 /* Set inline_failed for all callers of given function to REASON. */
961 cgraph_set_inline_failed (struct cgraph_node *node,
962 cgraph_inline_failed_t reason)
964 struct cgraph_edge *e;
967 fprintf (dump_file, "Inlining failed: %s\n",
968 cgraph_inline_failed_string (reason));
969 for (e = node->callers; e; e = e->next_caller)
970 if (e->inline_failed)
971 e->inline_failed = reason;
974 /* Given whole compilation unit estimate of INSNS, compute how large we can
975 allow the unit to grow. */
977 compute_max_insns (int insns)
979 int max_insns = insns;
980 if (max_insns < PARAM_VALUE (PARAM_LARGE_UNIT_INSNS))
981 max_insns = PARAM_VALUE (PARAM_LARGE_UNIT_INSNS);
983 return ((HOST_WIDEST_INT) max_insns
984 * (100 + PARAM_VALUE (PARAM_INLINE_UNIT_GROWTH)) / 100);
987 /* Compute badness of all edges in NEW_EDGES and add them to the HEAP. */
989 add_new_edges_to_heap (fibheap_t heap, VEC (cgraph_edge_p, heap) *new_edges)
991 while (VEC_length (cgraph_edge_p, new_edges) > 0)
993 struct cgraph_edge *edge = VEC_pop (cgraph_edge_p, new_edges);
995 gcc_assert (!edge->aux);
996 if (edge->callee->local.inlinable
997 && edge->inline_failed
998 && cgraph_default_inline_p (edge->callee, &edge->inline_failed))
999 edge->aux = fibheap_insert (heap, cgraph_edge_badness (edge, false), edge);
1004 /* We use greedy algorithm for inlining of small functions:
1005 All inline candidates are put into prioritized heap based on estimated
1006 growth of the overall number of instructions and then update the estimates.
1008 INLINED and INLINED_CALLEES are just pointers to arrays large enough
1009 to be passed to cgraph_inlined_into and cgraph_inlined_callees. */
1012 cgraph_decide_inlining_of_small_functions (void)
1014 struct cgraph_node *node;
1015 struct cgraph_edge *edge;
1016 cgraph_inline_failed_t failed_reason;
1017 fibheap_t heap = fibheap_new ();
1018 bitmap updated_nodes = BITMAP_ALLOC (NULL);
1019 int min_size, max_size;
1020 VEC (cgraph_edge_p, heap) *new_indirect_edges = NULL;
1022 if (flag_indirect_inlining)
1023 new_indirect_edges = VEC_alloc (cgraph_edge_p, heap, 8);
1026 fprintf (dump_file, "\nDeciding on smaller functions:\n");
1028 /* Put all inline candidates into the heap. */
1030 for (node = cgraph_nodes; node; node = node->next)
1032 if (!node->local.inlinable || !node->callers)
1035 fprintf (dump_file, "Considering inline candidate %s.\n", cgraph_node_name (node));
1037 node->global.estimated_growth = INT_MIN;
1038 if (!cgraph_default_inline_p (node, &failed_reason))
1040 cgraph_set_inline_failed (node, failed_reason);
1044 for (edge = node->callers; edge; edge = edge->next_caller)
1045 if (edge->inline_failed)
1047 gcc_assert (!edge->aux);
1048 edge->aux = fibheap_insert (heap, cgraph_edge_badness (edge, false), edge);
1052 max_size = compute_max_insns (overall_size);
1053 min_size = overall_size;
1055 while (overall_size <= max_size
1056 && !fibheap_empty (heap))
1058 int old_size = overall_size;
1059 struct cgraph_node *where, *callee;
1060 int badness = fibheap_min_key (heap);
1061 int current_badness;
1063 cgraph_inline_failed_t not_good = CIF_OK;
1065 edge = (struct cgraph_edge *) fibheap_extract_min (heap);
1066 gcc_assert (edge->aux);
1068 if (!edge->inline_failed)
1071 /* When updating the edge costs, we only decrease badness in the keys.
1072 When the badness increase, we keep the heap as it is and re-insert
1074 current_badness = cgraph_edge_badness (edge, false);
1075 gcc_assert (current_badness >= badness);
1076 if (current_badness != badness)
1078 edge->aux = fibheap_insert (heap, current_badness, edge);
1082 callee = edge->callee;
1084 growth = (cgraph_estimate_size_after_inlining (edge->caller, edge->callee)
1085 - edge->caller->global.size);
1090 "\nConsidering %s with %i size\n",
1091 cgraph_node_name (edge->callee),
1092 edge->callee->global.size);
1094 " to be inlined into %s in %s:%i\n"
1095 " Estimated growth after inlined into all callees is %+i insns.\n"
1096 " Estimated badness is %i, frequency %.2f.\n",
1097 cgraph_node_name (edge->caller),
1098 flag_wpa ? "unknown"
1099 : gimple_filename ((const_gimple) edge->call_stmt),
1100 flag_wpa ? -1 : gimple_lineno ((const_gimple) edge->call_stmt),
1101 cgraph_estimate_growth (edge->callee),
1103 edge->frequency / (double)CGRAPH_FREQ_BASE);
1105 fprintf (dump_file," Called "HOST_WIDEST_INT_PRINT_DEC"x\n", edge->count);
1106 if (dump_flags & TDF_DETAILS)
1107 cgraph_edge_badness (edge, true);
1110 /* When not having profile info ready we don't weight by any way the
1111 position of call in procedure itself. This means if call of
1112 function A from function B seems profitable to inline, the recursive
1113 call of function A in inline copy of A in B will look profitable too
1114 and we end up inlining until reaching maximal function growth. This
1115 is not good idea so prohibit the recursive inlining.
1117 ??? When the frequencies are taken into account we might not need this
1120 We need to be careful here, in some testcases, e.g. directives.c in
1121 libcpp, we can estimate self recursive function to have negative growth
1122 for inlining completely.
1126 where = edge->caller;
1127 while (where->global.inlined_to)
1129 if (where->decl == edge->callee->decl)
1131 where = where->callers->caller;
1133 if (where->global.inlined_to)
1136 = (edge->callee->local.disregard_inline_limits
1137 ? CIF_RECURSIVE_INLINING : CIF_UNSPECIFIED);
1139 fprintf (dump_file, " inline_failed:Recursive inlining performed only for function itself.\n");
1144 if (edge->callee->local.disregard_inline_limits)
1146 else if (!cgraph_maybe_hot_edge_p (edge))
1147 not_good = CIF_UNLIKELY_CALL;
1148 else if (!flag_inline_functions
1149 && !DECL_DECLARED_INLINE_P (edge->callee->decl))
1150 not_good = CIF_NOT_DECLARED_INLINED;
1151 else if (optimize_function_for_size_p (DECL_STRUCT_FUNCTION(edge->caller->decl)))
1152 not_good = CIF_OPTIMIZING_FOR_SIZE;
1153 if (not_good && growth > 0 && cgraph_estimate_growth (edge->callee) > 0)
1155 if (!cgraph_recursive_inlining_p (edge->caller, edge->callee,
1156 &edge->inline_failed))
1158 edge->inline_failed = not_good;
1160 fprintf (dump_file, " inline_failed:%s.\n",
1161 cgraph_inline_failed_string (edge->inline_failed));
1165 if (!cgraph_default_inline_p (edge->callee, &edge->inline_failed))
1167 if (!cgraph_recursive_inlining_p (edge->caller, edge->callee,
1168 &edge->inline_failed))
1171 fprintf (dump_file, " inline_failed:%s.\n",
1172 cgraph_inline_failed_string (edge->inline_failed));
1176 if (!tree_can_inline_p (edge)
1177 || edge->call_stmt_cannot_inline_p)
1180 fprintf (dump_file, " inline_failed:%s.\n",
1181 cgraph_inline_failed_string (edge->inline_failed));
1184 if (cgraph_recursive_inlining_p (edge->caller, edge->callee,
1185 &edge->inline_failed))
1187 where = edge->caller;
1188 if (where->global.inlined_to)
1189 where = where->global.inlined_to;
1190 if (!cgraph_decide_recursive_inlining (where,
1191 flag_indirect_inlining
1192 ? &new_indirect_edges : NULL))
1194 if (flag_indirect_inlining)
1195 add_new_edges_to_heap (heap, new_indirect_edges);
1196 update_all_callee_keys (heap, where, updated_nodes);
1200 struct cgraph_node *callee;
1201 if (!cgraph_check_inline_limits (edge->caller, edge->callee,
1202 &edge->inline_failed))
1205 fprintf (dump_file, " Not inlining into %s:%s.\n",
1206 cgraph_node_name (edge->caller),
1207 cgraph_inline_failed_string (edge->inline_failed));
1210 callee = edge->callee;
1211 gcc_checking_assert (!callee->global.inlined_to);
1212 cgraph_mark_inline_edge (edge, true, &new_indirect_edges);
1213 if (flag_indirect_inlining)
1214 add_new_edges_to_heap (heap, new_indirect_edges);
1216 /* We inlined last offline copy to the body. This might lead
1217 to callees of function having fewer call sites and thus they
1218 may need updating. */
1219 if (callee->global.inlined_to)
1220 update_all_callee_keys (heap, callee, updated_nodes);
1222 update_callee_keys (heap, edge->callee, updated_nodes);
1224 where = edge->caller;
1225 if (where->global.inlined_to)
1226 where = where->global.inlined_to;
1228 /* Our profitability metric can depend on local properties
1229 such as number of inlinable calls and size of the function body.
1230 After inlining these properties might change for the function we
1231 inlined into (since it's body size changed) and for the functions
1232 called by function we inlined (since number of it inlinable callers
1234 update_caller_keys (heap, where, updated_nodes);
1236 /* We removed one call of the function we just inlined. If offline
1237 copy is still needed, be sure to update the keys. */
1238 if (callee != where && !callee->global.inlined_to)
1239 update_caller_keys (heap, callee, updated_nodes);
1240 bitmap_clear (updated_nodes);
1245 " Inlined into %s which now has time %i and size %i,"
1246 "net change of %+i.\n",
1247 cgraph_node_name (edge->caller),
1248 edge->caller->global.time,
1249 edge->caller->global.size,
1250 overall_size - old_size);
1252 if (min_size > overall_size)
1254 min_size = overall_size;
1255 max_size = compute_max_insns (min_size);
1258 fprintf (dump_file, "New minimal size reached: %i\n", min_size);
1261 while (!fibheap_empty (heap))
1263 int badness = fibheap_min_key (heap);
1265 edge = (struct cgraph_edge *) fibheap_extract_min (heap);
1266 gcc_assert (edge->aux);
1268 if (!edge->inline_failed)
1270 #ifdef ENABLE_CHECKING
1271 gcc_assert (cgraph_edge_badness (edge, false) >= badness);
1276 "\nSkipping %s with %i size\n",
1277 cgraph_node_name (edge->callee),
1278 edge->callee->global.size);
1280 " called by %s in %s:%i\n"
1281 " Estimated growth after inlined into all callees is %+i insns.\n"
1282 " Estimated badness is %i, frequency %.2f.\n",
1283 cgraph_node_name (edge->caller),
1284 flag_wpa ? "unknown"
1285 : gimple_filename ((const_gimple) edge->call_stmt),
1286 flag_wpa ? -1 : gimple_lineno ((const_gimple) edge->call_stmt),
1287 cgraph_estimate_growth (edge->callee),
1289 edge->frequency / (double)CGRAPH_FREQ_BASE);
1291 fprintf (dump_file," Called "HOST_WIDEST_INT_PRINT_DEC"x\n", edge->count);
1292 if (dump_flags & TDF_DETAILS)
1293 cgraph_edge_badness (edge, true);
1295 if (!edge->callee->local.disregard_inline_limits && edge->inline_failed
1296 && !cgraph_recursive_inlining_p (edge->caller, edge->callee,
1297 &edge->inline_failed))
1298 edge->inline_failed = CIF_INLINE_UNIT_GROWTH_LIMIT;
1301 if (new_indirect_edges)
1302 VEC_free (cgraph_edge_p, heap, new_indirect_edges);
1303 fibheap_delete (heap);
1304 BITMAP_FREE (updated_nodes);
1307 /* Flatten NODE from the IPA inliner. */
1310 cgraph_flatten (struct cgraph_node *node)
1312 struct cgraph_edge *e;
1314 /* We shouldn't be called recursively when we are being processed. */
1315 gcc_assert (node->aux == NULL);
1317 node->aux = (void *)(size_t) INLINE_ALL;
1319 for (e = node->callees; e; e = e->next_callee)
1321 struct cgraph_node *orig_callee;
1323 if (e->call_stmt_cannot_inline_p)
1326 fprintf (dump_file, "Not inlining: %s",
1327 cgraph_inline_failed_string (e->inline_failed));
1331 if (!e->callee->analyzed)
1335 "Not inlining: Function body not available.\n");
1339 if (!e->callee->local.inlinable)
1342 /* We've hit cycle? It is time to give up. */
1347 "Not inlining %s into %s to avoid cycle.\n",
1348 cgraph_node_name (e->callee),
1349 cgraph_node_name (e->caller));
1350 e->inline_failed = CIF_RECURSIVE_INLINING;
1354 /* When the edge is already inlined, we just need to recurse into
1355 it in order to fully flatten the leaves. */
1356 if (!e->inline_failed)
1358 cgraph_flatten (e->callee);
1362 if (cgraph_recursive_inlining_p (node, e->callee, &e->inline_failed))
1365 fprintf (dump_file, "Not inlining: recursive call.\n");
1369 if (!tree_can_inline_p (e))
1372 fprintf (dump_file, "Not inlining: %s",
1373 cgraph_inline_failed_string (e->inline_failed));
1377 if (gimple_in_ssa_p (DECL_STRUCT_FUNCTION (node->decl))
1378 != gimple_in_ssa_p (DECL_STRUCT_FUNCTION (e->callee->decl)))
1381 fprintf (dump_file, "Not inlining: SSA form does not match.\n");
1385 /* Inline the edge and flatten the inline clone. Avoid
1386 recursing through the original node if the node was cloned. */
1388 fprintf (dump_file, " Inlining %s into %s.\n",
1389 cgraph_node_name (e->callee),
1390 cgraph_node_name (e->caller));
1391 orig_callee = e->callee;
1392 cgraph_mark_inline_edge (e, true, NULL);
1393 if (e->callee != orig_callee)
1394 orig_callee->aux = (void *)(size_t) INLINE_ALL;
1395 cgraph_flatten (e->callee);
1396 if (e->callee != orig_callee)
1397 orig_callee->aux = NULL;
1403 /* Decide on the inlining. We do so in the topological order to avoid
1404 expenses on updating data structures. */
1407 cgraph_decide_inlining (void)
1409 struct cgraph_node *node;
1411 struct cgraph_node **order =
1412 XCNEWVEC (struct cgraph_node *, cgraph_n_nodes);
1415 int initial_size = 0;
1417 cgraph_remove_function_insertion_hook (function_insertion_hook_holder);
1418 if (in_lto_p && flag_indirect_inlining)
1419 ipa_update_after_lto_read ();
1420 if (flag_indirect_inlining)
1421 ipa_create_all_structures_for_iinln ();
1425 for (node = cgraph_nodes; node; node = node->next)
1428 struct cgraph_edge *e;
1430 gcc_assert (inline_summary (node)->self_size == node->global.size);
1431 if (!DECL_EXTERNAL (node->decl))
1432 initial_size += node->global.size;
1433 for (e = node->callees; e; e = e->next_callee)
1434 if (max_count < e->count)
1435 max_count = e->count;
1436 if (max_benefit < inline_summary (node)->time_inlining_benefit)
1437 max_benefit = inline_summary (node)->time_inlining_benefit;
1439 gcc_assert (in_lto_p
1441 || (profile_info && flag_branch_probabilities));
1442 overall_size = initial_size;
1444 nnodes = cgraph_postorder (order);
1448 "\nDeciding on inlining. Starting with size %i.\n",
1451 for (node = cgraph_nodes; node; node = node->next)
1455 fprintf (dump_file, "\nFlattening functions:\n");
1457 /* In the first pass handle functions to be flattened. Do this with
1458 a priority so none of our later choices will make this impossible. */
1459 for (i = nnodes - 1; i >= 0; i--)
1463 /* Handle nodes to be flattened, but don't update overall unit
1464 size. Calling the incremental inliner here is lame,
1465 a simple worklist should be enough. What should be left
1466 here from the early inliner (if it runs) is cyclic cases.
1467 Ideally when processing callees we stop inlining at the
1468 entry of cycles, possibly cloning that entry point and
1469 try to flatten itself turning it into a self-recursive
1471 if (lookup_attribute ("flatten",
1472 DECL_ATTRIBUTES (node->decl)) != NULL)
1476 "Flattening %s\n", cgraph_node_name (node));
1477 cgraph_flatten (node);
1481 cgraph_decide_inlining_of_small_functions ();
1483 if (flag_inline_functions_called_once)
1486 fprintf (dump_file, "\nDeciding on functions called once:\n");
1488 /* And finally decide what functions are called once. */
1489 for (i = nnodes - 1; i >= 0; i--)
1494 && !node->callers->next_caller
1495 && !node->global.inlined_to
1496 && cgraph_will_be_removed_from_program_if_no_direct_calls (node)
1497 && node->local.inlinable
1498 && cgraph_function_body_availability (node) >= AVAIL_AVAILABLE
1499 && node->callers->inline_failed
1500 && node->callers->caller != node
1501 && node->callers->caller->global.inlined_to != node
1502 && !node->callers->call_stmt_cannot_inline_p
1503 && tree_can_inline_p (node->callers)
1504 && !DECL_EXTERNAL (node->decl))
1506 cgraph_inline_failed_t reason;
1507 old_size = overall_size;
1511 "\nConsidering %s size %i.\n",
1512 cgraph_node_name (node), node->global.size);
1514 " Called once from %s %i insns.\n",
1515 cgraph_node_name (node->callers->caller),
1516 node->callers->caller->global.size);
1519 if (cgraph_check_inline_limits (node->callers->caller, node,
1522 struct cgraph_node *caller = node->callers->caller;
1523 cgraph_mark_inline_edge (node->callers, true, NULL);
1526 " Inlined into %s which now has %i size"
1527 " for a net change of %+i size.\n",
1528 cgraph_node_name (caller),
1529 caller->global.size,
1530 overall_size - old_size);
1536 " Not inlining: %s.\n",
1537 cgraph_inline_failed_string (reason));
1543 /* Free ipa-prop structures if they are no longer needed. */
1544 if (flag_indirect_inlining)
1545 ipa_free_all_structures_after_iinln ();
1549 "\nInlined %i calls, eliminated %i functions, "
1550 "size %i turned to %i size.\n\n",
1551 ncalls_inlined, nfunctions_inlined, initial_size,
1557 /* Return true when N is leaf function. Accept cheap builtins
1558 in leaf functions. */
1561 leaf_node_p (struct cgraph_node *n)
1563 struct cgraph_edge *e;
1564 for (e = n->callees; e; e = e->next_callee)
1565 if (!is_inexpensive_builtin (e->callee->decl))
1570 /* Decide on the inlining. We do so in the topological order to avoid
1571 expenses on updating data structures. */
1574 cgraph_decide_inlining_incrementally (struct cgraph_node *node,
1575 enum inlining_mode mode)
1577 struct cgraph_edge *e;
1578 bool inlined = false;
1579 cgraph_inline_failed_t failed_reason;
1581 #ifdef ENABLE_CHECKING
1582 verify_cgraph_node (node);
1585 if (mode != INLINE_ALWAYS_INLINE && mode != INLINE_SIZE_NORECURSIVE
1586 && lookup_attribute ("flatten", DECL_ATTRIBUTES (node->decl)) != NULL)
1589 fprintf (dump_file, "Incrementally flattening %s\n",
1590 cgraph_node_name (node));
1594 /* First of all look for always inline functions. */
1595 if (mode != INLINE_SIZE_NORECURSIVE)
1596 for (e = node->callees; e; e = e->next_callee)
1598 if (!e->callee->local.disregard_inline_limits
1599 && (mode != INLINE_ALL || !e->callee->local.inlinable))
1603 "Considering to always inline inline candidate %s.\n",
1604 cgraph_node_name (e->callee));
1605 if (cgraph_recursive_inlining_p (node, e->callee, &e->inline_failed))
1608 fprintf (dump_file, "Not inlining: recursive call.\n");
1611 if (!tree_can_inline_p (e)
1612 || e->call_stmt_cannot_inline_p)
1617 cgraph_inline_failed_string (e->inline_failed));
1620 if (gimple_in_ssa_p (DECL_STRUCT_FUNCTION (node->decl))
1621 != gimple_in_ssa_p (DECL_STRUCT_FUNCTION (e->callee->decl)))
1624 fprintf (dump_file, "Not inlining: SSA form does not match.\n");
1627 if (!e->callee->analyzed)
1631 "Not inlining: Function body no longer available.\n");
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_edge (e, true, NULL);
1643 /* Now do the automatic inlining. */
1644 if (mode != INLINE_ALL && mode != INLINE_ALWAYS_INLINE
1645 /* Never inline regular functions into always-inline functions
1646 during incremental inlining. */
1647 && !node->local.disregard_inline_limits)
1649 for (e = node->callees; e; e = e->next_callee)
1651 int allowed_growth = 0;
1652 if (!e->callee->local.inlinable
1653 || !e->inline_failed
1654 || e->callee->local.disregard_inline_limits)
1657 fprintf (dump_file, "Considering inline candidate %s.\n",
1658 cgraph_node_name (e->callee));
1659 if (cgraph_recursive_inlining_p (node, e->callee, &e->inline_failed))
1662 fprintf (dump_file, "Not inlining: recursive call.\n");
1665 if (gimple_in_ssa_p (DECL_STRUCT_FUNCTION (node->decl))
1666 != gimple_in_ssa_p (DECL_STRUCT_FUNCTION (e->callee->decl)))
1670 "Not inlining: SSA form does not match.\n");
1674 if (cgraph_maybe_hot_edge_p (e) && leaf_node_p (e->callee)
1675 && optimize_function_for_speed_p (cfun))
1676 allowed_growth = PARAM_VALUE (PARAM_EARLY_INLINING_INSNS);
1678 /* When the function body would grow and inlining the function
1679 won't eliminate the need for offline copy of the function,
1681 if (((mode == INLINE_SIZE || mode == INLINE_SIZE_NORECURSIVE)
1682 || (!flag_inline_functions
1683 && !DECL_DECLARED_INLINE_P (e->callee->decl)))
1684 && (cgraph_estimate_size_after_inlining (e->caller, e->callee)
1685 > e->caller->global.size + allowed_growth)
1686 && cgraph_estimate_growth (e->callee) > allowed_growth)
1690 "Not inlining: code size would grow by %i.\n",
1691 cgraph_estimate_size_after_inlining (e->caller,
1693 - e->caller->global.size);
1696 if (e->call_stmt_cannot_inline_p
1697 || !tree_can_inline_p (e))
1701 "Not inlining: call site not inlinable.\n");
1704 if (!e->callee->analyzed)
1708 "Not inlining: Function body no longer available.\n");
1711 if (!cgraph_check_inline_limits (node, e->callee, &e->inline_failed))
1714 fprintf (dump_file, "Not inlining: %s.\n",
1715 cgraph_inline_failed_string (e->inline_failed));
1718 if (cgraph_default_inline_p (e->callee, &failed_reason))
1721 fprintf (dump_file, " Inlining %s into %s.\n",
1722 cgraph_node_name (e->callee),
1723 cgraph_node_name (e->caller));
1724 cgraph_mark_inline_edge (e, true, NULL);
1732 /* Because inlining might remove no-longer reachable nodes, we need to
1733 keep the array visible to garbage collector to avoid reading collected
1736 static GTY ((length ("nnodes"))) struct cgraph_node **order;
1738 /* Do inlining of small functions. Doing so early helps profiling and other
1739 passes to be somewhat more effective and avoids some code duplication in
1740 later real inlining pass for testcases with very many function calls. */
1742 cgraph_early_inlining (void)
1744 struct cgraph_node *node = cgraph_node (current_function_decl);
1745 unsigned int todo = 0;
1753 || !flag_early_inlining)
1755 /* When not optimizing or not inlining inline only always-inline
1757 cgraph_decide_inlining_incrementally (node, INLINE_ALWAYS_INLINE);
1758 timevar_push (TV_INTEGRATION);
1759 todo |= optimize_inline_calls (current_function_decl);
1760 timevar_pop (TV_INTEGRATION);
1764 if (lookup_attribute ("flatten",
1765 DECL_ATTRIBUTES (node->decl)) != NULL)
1769 "Flattening %s\n", cgraph_node_name (node));
1770 cgraph_flatten (node);
1771 timevar_push (TV_INTEGRATION);
1772 todo |= optimize_inline_calls (current_function_decl);
1773 timevar_pop (TV_INTEGRATION);
1775 /* We iterate incremental inlining to get trivial cases of indirect
1777 while (iterations < PARAM_VALUE (PARAM_EARLY_INLINER_MAX_ITERATIONS)
1778 && cgraph_decide_inlining_incrementally (node,
1780 ? INLINE_SIZE_NORECURSIVE
1783 timevar_push (TV_INTEGRATION);
1784 todo |= optimize_inline_calls (current_function_decl);
1786 timevar_pop (TV_INTEGRATION);
1789 fprintf (dump_file, "Iterations: %i\n", iterations);
1792 cfun->always_inline_functions_inlined = true;
1797 struct gimple_opt_pass pass_early_inline =
1801 "einline", /* name */
1803 cgraph_early_inlining, /* execute */
1806 0, /* static_pass_number */
1807 TV_INLINE_HEURISTICS, /* tv_id */
1808 0, /* properties_required */
1809 0, /* properties_provided */
1810 0, /* properties_destroyed */
1811 0, /* todo_flags_start */
1812 TODO_dump_func /* todo_flags_finish */
1817 /* See if statement might disappear after inlining.
1818 0 - means not eliminated
1819 1 - half of statements goes away
1820 2 - for sure it is eliminated.
1821 We are not terribly sophisticated, basically looking for simple abstraction
1822 penalty wrappers. */
1825 eliminated_by_inlining_prob (gimple stmt)
1827 enum gimple_code code = gimple_code (stmt);
1833 if (gimple_num_ops (stmt) != 2)
1836 /* Casts of parameters, loads from parameters passed by reference
1837 and stores to return value or parameters are often free after
1838 inlining dua to SRA and further combining.
1839 Assume that half of statements goes away. */
1840 if (gimple_assign_rhs_code (stmt) == CONVERT_EXPR
1841 || gimple_assign_rhs_code (stmt) == NOP_EXPR
1842 || gimple_assign_rhs_code (stmt) == VIEW_CONVERT_EXPR
1843 || gimple_assign_rhs_class (stmt) == GIMPLE_SINGLE_RHS)
1845 tree rhs = gimple_assign_rhs1 (stmt);
1846 tree lhs = gimple_assign_lhs (stmt);
1847 tree inner_rhs = rhs;
1848 tree inner_lhs = lhs;
1849 bool rhs_free = false;
1850 bool lhs_free = false;
1852 while (handled_component_p (inner_lhs)
1853 || TREE_CODE (inner_lhs) == MEM_REF)
1854 inner_lhs = TREE_OPERAND (inner_lhs, 0);
1855 while (handled_component_p (inner_rhs)
1856 || TREE_CODE (inner_rhs) == ADDR_EXPR
1857 || TREE_CODE (inner_rhs) == MEM_REF)
1858 inner_rhs = TREE_OPERAND (inner_rhs, 0);
1861 if (TREE_CODE (inner_rhs) == PARM_DECL
1862 || (TREE_CODE (inner_rhs) == SSA_NAME
1863 && SSA_NAME_IS_DEFAULT_DEF (inner_rhs)
1864 && TREE_CODE (SSA_NAME_VAR (inner_rhs)) == PARM_DECL))
1866 if (rhs_free && is_gimple_reg (lhs))
1868 if (((TREE_CODE (inner_lhs) == PARM_DECL
1869 || (TREE_CODE (inner_lhs) == SSA_NAME
1870 && SSA_NAME_IS_DEFAULT_DEF (inner_lhs)
1871 && TREE_CODE (SSA_NAME_VAR (inner_lhs)) == PARM_DECL))
1872 && inner_lhs != lhs)
1873 || TREE_CODE (inner_lhs) == RESULT_DECL
1874 || (TREE_CODE (inner_lhs) == SSA_NAME
1875 && TREE_CODE (SSA_NAME_VAR (inner_lhs)) == RESULT_DECL))
1878 && (is_gimple_reg (rhs) || is_gimple_min_invariant (rhs)))
1880 if (lhs_free && rhs_free)
1889 /* Compute function body size parameters for NODE. */
1892 estimate_function_body_sizes (struct cgraph_node *node)
1895 gcov_type time_inlining_benefit = 0;
1896 /* Estimate static overhead for function prologue/epilogue and alignment. */
1898 /* Benefits are scaled by probability of elimination that is in range
1900 int size_inlining_benefit = 2 * 2;
1902 gimple_stmt_iterator bsi;
1903 struct function *my_function = DECL_STRUCT_FUNCTION (node->decl);
1906 tree funtype = TREE_TYPE (node->decl);
1909 fprintf (dump_file, "Analyzing function body size: %s\n",
1910 cgraph_node_name (node));
1912 gcc_assert (my_function && my_function->cfg);
1913 FOR_EACH_BB_FN (bb, my_function)
1915 freq = compute_call_stmt_bb_frequency (node->decl, bb);
1916 for (bsi = gsi_start_bb (bb); !gsi_end_p (bsi); gsi_next (&bsi))
1918 gimple stmt = gsi_stmt (bsi);
1919 int this_size = estimate_num_insns (stmt, &eni_size_weights);
1920 int this_time = estimate_num_insns (stmt, &eni_time_weights);
1923 if (dump_file && (dump_flags & TDF_DETAILS))
1925 fprintf (dump_file, " freq:%6i size:%3i time:%3i ",
1926 freq, this_size, this_time);
1927 print_gimple_stmt (dump_file, stmt, 0, 0);
1932 prob = eliminated_by_inlining_prob (stmt);
1933 if (prob == 1 && dump_file && (dump_flags & TDF_DETAILS))
1934 fprintf (dump_file, " 50%% will be eliminated by inlining\n");
1935 if (prob == 2 && dump_file && (dump_flags & TDF_DETAILS))
1936 fprintf (dump_file, " will eliminated by inlining\n");
1937 size_inlining_benefit += this_size * prob;
1938 time_inlining_benefit += this_time * prob;
1939 gcc_assert (time >= 0);
1940 gcc_assert (size >= 0);
1943 time = (time + CGRAPH_FREQ_BASE / 2) / CGRAPH_FREQ_BASE;
1944 time_inlining_benefit = ((time_inlining_benefit + CGRAPH_FREQ_BASE)
1945 / (CGRAPH_FREQ_BASE * 2));
1946 size_inlining_benefit = (size_inlining_benefit + 1) / 2;
1948 fprintf (dump_file, "Overall function body time: %i-%i size: %i-%i\n",
1949 (int)time, (int)time_inlining_benefit,
1950 size, size_inlining_benefit);
1951 time_inlining_benefit += eni_time_weights.call_cost;
1952 size_inlining_benefit += eni_size_weights.call_cost;
1953 if (!VOID_TYPE_P (TREE_TYPE (funtype)))
1955 int cost = estimate_move_cost (TREE_TYPE (funtype));
1956 time_inlining_benefit += cost;
1957 size_inlining_benefit += cost;
1959 for (arg = DECL_ARGUMENTS (node->decl); arg; arg = DECL_CHAIN (arg))
1960 if (!VOID_TYPE_P (TREE_TYPE (arg)))
1962 int cost = estimate_move_cost (TREE_TYPE (arg));
1963 time_inlining_benefit += cost;
1964 size_inlining_benefit += cost;
1966 if (time_inlining_benefit > MAX_TIME)
1967 time_inlining_benefit = MAX_TIME;
1968 if (time > MAX_TIME)
1970 inline_summary (node)->self_time = time;
1971 inline_summary (node)->self_size = size;
1973 fprintf (dump_file, "With function call overhead time: %i-%i size: %i-%i\n",
1974 (int)time, (int)time_inlining_benefit,
1975 size, size_inlining_benefit);
1976 inline_summary (node)->time_inlining_benefit = time_inlining_benefit;
1977 inline_summary (node)->size_inlining_benefit = size_inlining_benefit;
1980 /* Compute parameters of functions used by inliner. */
1982 compute_inline_parameters (struct cgraph_node *node)
1984 HOST_WIDE_INT self_stack_size;
1986 gcc_assert (!node->global.inlined_to);
1988 /* Estimate the stack size for the function if we're optimizing. */
1989 self_stack_size = optimize ? estimated_stack_frame_size (node) : 0;
1990 inline_summary (node)->estimated_self_stack_size = self_stack_size;
1991 node->global.estimated_stack_size = self_stack_size;
1992 node->global.stack_frame_offset = 0;
1994 /* Can this function be inlined at all? */
1995 node->local.inlinable = tree_inlinable_function_p (node->decl);
1996 if (!node->local.inlinable)
1997 node->local.disregard_inline_limits = 0;
1999 /* Inlinable functions always can change signature. */
2000 if (node->local.inlinable)
2001 node->local.can_change_signature = true;
2004 struct cgraph_edge *e;
2006 /* Functions calling builtin_apply can not change signature. */
2007 for (e = node->callees; e; e = e->next_callee)
2008 if (DECL_BUILT_IN (e->callee->decl)
2009 && DECL_BUILT_IN_CLASS (e->callee->decl) == BUILT_IN_NORMAL
2010 && DECL_FUNCTION_CODE (e->callee->decl) == BUILT_IN_APPLY_ARGS)
2012 node->local.can_change_signature = !e;
2014 estimate_function_body_sizes (node);
2015 /* Inlining characteristics are maintained by the cgraph_mark_inline. */
2016 node->global.time = inline_summary (node)->self_time;
2017 node->global.size = inline_summary (node)->self_size;
2021 /* Compute parameters of functions used by inliner using
2022 current_function_decl. */
2024 compute_inline_parameters_for_current (void)
2026 compute_inline_parameters (cgraph_node (current_function_decl));
2030 struct gimple_opt_pass pass_inline_parameters =
2034 "inline_param", /* name */
2036 compute_inline_parameters_for_current,/* execute */
2039 0, /* static_pass_number */
2040 TV_INLINE_HEURISTICS, /* tv_id */
2041 0, /* properties_required */
2042 0, /* properties_provided */
2043 0, /* properties_destroyed */
2044 0, /* todo_flags_start */
2045 0 /* todo_flags_finish */
2049 /* This function performs intraprocedural analysis in NODE that is required to
2050 inline indirect calls. */
2052 inline_indirect_intraprocedural_analysis (struct cgraph_node *node)
2054 ipa_analyze_node (node);
2055 if (dump_file && (dump_flags & TDF_DETAILS))
2057 ipa_print_node_params (dump_file, node);
2058 ipa_print_node_jump_functions (dump_file, node);
2062 /* Note function body size. */
2064 analyze_function (struct cgraph_node *node)
2066 push_cfun (DECL_STRUCT_FUNCTION (node->decl));
2067 current_function_decl = node->decl;
2069 compute_inline_parameters (node);
2070 /* FIXME: We should remove the optimize check after we ensure we never run
2071 IPA passes when not optimizing. */
2072 if (flag_indirect_inlining && optimize)
2073 inline_indirect_intraprocedural_analysis (node);
2075 current_function_decl = NULL;
2079 /* Called when new function is inserted to callgraph late. */
2081 add_new_function (struct cgraph_node *node, void *data ATTRIBUTE_UNUSED)
2083 analyze_function (node);
2086 /* Note function body size. */
2088 inline_generate_summary (void)
2090 struct cgraph_node *node;
2092 function_insertion_hook_holder =
2093 cgraph_add_function_insertion_hook (&add_new_function, NULL);
2095 if (flag_indirect_inlining)
2096 ipa_register_cgraph_hooks ();
2098 for (node = cgraph_nodes; node; node = node->next)
2100 analyze_function (node);
2105 /* Apply inline plan to function. */
2107 inline_transform (struct cgraph_node *node)
2109 unsigned int todo = 0;
2110 struct cgraph_edge *e;
2111 bool inline_p = false;
2113 /* FIXME: Currently the pass manager is adding inline transform more than once to some
2114 clones. This needs revisiting after WPA cleanups. */
2115 if (cfun->after_inlining)
2118 /* We might need the body of this function so that we can expand
2119 it inline somewhere else. */
2120 if (cgraph_preserve_function_body_p (node->decl))
2121 save_inline_function_body (node);
2123 for (e = node->callees; e; e = e->next_callee)
2125 cgraph_redirect_edge_call_stmt_to_callee (e);
2126 if (!e->inline_failed || warn_inline)
2132 timevar_push (TV_INTEGRATION);
2133 todo = optimize_inline_calls (current_function_decl);
2134 timevar_pop (TV_INTEGRATION);
2136 cfun->always_inline_functions_inlined = true;
2137 cfun->after_inlining = true;
2138 return todo | execute_fixup_cfg ();
2141 /* Read inline summary. Jump functions are shared among ipa-cp
2142 and inliner, so when ipa-cp is active, we don't need to write them
2146 inline_read_summary (void)
2148 if (flag_indirect_inlining)
2150 ipa_register_cgraph_hooks ();
2152 ipa_prop_read_jump_functions ();
2154 function_insertion_hook_holder =
2155 cgraph_add_function_insertion_hook (&add_new_function, NULL);
2158 /* Write inline summary for node in SET.
2159 Jump functions are shared among ipa-cp and inliner, so when ipa-cp is
2160 active, we don't need to write them twice. */
2163 inline_write_summary (cgraph_node_set set,
2164 varpool_node_set vset ATTRIBUTE_UNUSED)
2166 if (flag_indirect_inlining && !flag_ipa_cp)
2167 ipa_prop_write_jump_functions (set);
2170 /* When to run IPA inlining. Inlining of always-inline functions
2171 happens during early inlining. */
2174 gate_cgraph_decide_inlining (void)
2176 /* ??? We'd like to skip this if not optimizing or not inlining as
2177 all always-inline functions have been processed by early
2178 inlining already. But this at least breaks EH with C++ as
2179 we need to unconditionally run fixup_cfg even at -O0.
2180 So leave it on unconditionally for now. */
2184 struct ipa_opt_pass_d pass_ipa_inline =
2188 "inline", /* name */
2189 gate_cgraph_decide_inlining, /* gate */
2190 cgraph_decide_inlining, /* execute */
2193 0, /* static_pass_number */
2194 TV_INLINE_HEURISTICS, /* tv_id */
2195 0, /* properties_required */
2196 0, /* properties_provided */
2197 0, /* properties_destroyed */
2198 TODO_remove_functions, /* todo_flags_finish */
2199 TODO_dump_cgraph | TODO_dump_func
2200 | TODO_remove_functions | TODO_ggc_collect /* todo_flags_finish */
2202 inline_generate_summary, /* generate_summary */
2203 inline_write_summary, /* write_summary */
2204 inline_read_summary, /* read_summary */
2205 NULL, /* write_optimization_summary */
2206 NULL, /* read_optimization_summary */
2207 NULL, /* stmt_fixup */
2209 inline_transform, /* function_transform */
2210 NULL, /* variable_transform */
2214 #include "gt-ipa-inline.h"