1 /* Inlining decision heuristics.
2 Copyright (C) 2003, 2004, 2007, 2008, 2009, 2010
3 Free Software Foundation, Inc.
4 Contributed by Jan Hubicka
6 This file is part of GCC.
8 GCC is free software; you can redistribute it and/or modify it under
9 the terms of the GNU General Public License as published by the Free
10 Software Foundation; either version 3, or (at your option) any later
13 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
14 WARRANTY; without even the implied warranty of MERCHANTABILITY or
15 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
18 You should have received a copy of the GNU General Public License
19 along with GCC; see the file COPYING3. If not see
20 <http://www.gnu.org/licenses/>. */
22 /* Inlining decision heuristics
24 We separate inlining decisions from the inliner itself and store it
25 inside callgraph as so called inline plan. Refer to cgraph.c
26 documentation about particular representation of inline plans in the
29 There are three major parts of this file:
31 cgraph_mark_inline implementation
33 This function allows to mark given call inline and performs necessary
34 modifications of cgraph (production of the clones and updating overall
37 inlining heuristics limits
39 These functions allow to check that particular inlining is allowed
40 by the limits specified by user (allowed function growth, overall unit
45 This is implementation of IPA pass aiming to get as much of benefit
46 from inlining obeying the limits checked above.
48 The implementation of particular heuristics is separated from
49 the rest of code to make it easier to replace it with more complicated
50 implementation in the future. The rest of inlining code acts as a
51 library aimed to modify the callgraph and verify that the parameters
52 on code size growth fits.
54 To mark given call inline, use cgraph_mark_inline function, the
55 verification is performed by cgraph_default_inline_p and
56 cgraph_check_inline_limits.
58 The heuristics implements simple knapsack style algorithm ordering
59 all functions by their "profitability" (estimated by code size growth)
60 and inlining them in priority order.
62 cgraph_decide_inlining implements heuristics taking whole callgraph
63 into account, while cgraph_decide_inlining_incrementally considers
64 only one function at a time and is used by early inliner.
66 The inliner itself is split into several passes:
68 pass_inline_parameters
70 This pass computes local properties of functions that are used by inliner:
71 estimated function body size, whether function is inlinable at all and
72 stack frame consumption.
74 Before executing any of inliner passes, this local pass has to be applied
75 to each function in the callgraph (ie run as subpass of some earlier
76 IPA pass). The results are made out of date by any optimization applied
81 Simple local inlining pass inlining callees into current function. This
82 pass makes no global whole compilation unit analysis and this when allowed
83 to do inlining expanding code size it might result in unbounded growth of
86 The pass is run during conversion into SSA form. Only functions already
87 converted into SSA form are inlined, so the conversion must happen in
88 topological order on the callgraph (that is maintained by pass manager).
89 The functions after inlining are early optimized so the early inliner sees
90 unoptimized function itself, but all considered callees are already
91 optimized allowing it to unfold abstraction penalty on C++ effectively and
94 pass_ipa_early_inlining
96 With profiling, the early inlining is also necessary to reduce
97 instrumentation costs on program with high abstraction penalty (doing
98 many redundant calls). This can't happen in parallel with early
99 optimization and profile instrumentation, because we would end up
100 re-instrumenting already instrumented function bodies we brought in via
103 To avoid this, this pass is executed as IPA pass before profiling. It is
104 simple wrapper to pass_early_inlining and ensures first inlining.
108 This is the main pass implementing simple greedy algorithm to do inlining
109 of small functions that results in overall growth of compilation unit and
110 inlining of functions called once. The pass compute just so called inline
111 plan (representation of inlining to be done in callgraph) and unlike early
112 inlining it is not performing the inlining itself.
116 This pass performs actual inlining according to pass_ipa_inline on given
117 function. Possible the function body before inlining is saved when it is
118 needed for further inlining later.
123 #include "coretypes.h"
126 #include "tree-inline.h"
127 #include "langhooks.h"
130 #include "diagnostic.h"
135 #include "tree-pass.h"
137 #include "coverage.h"
139 #include "tree-flow.h"
141 #include "ipa-prop.h"
144 #define MAX_TIME 1000000000
146 /* Mode incremental inliner operate on:
148 In ALWAYS_INLINE only functions marked
149 always_inline are inlined. This mode is used after detecting cycle during
152 In SIZE mode, only functions that reduce function body size after inlining
153 are inlined, this is used during early inlining.
155 in ALL mode, everything is inlined. This is used during flattening. */
158 INLINE_ALWAYS_INLINE,
159 INLINE_SIZE_NORECURSIVE,
165 cgraph_decide_inlining_incrementally (struct cgraph_node *, enum inlining_mode);
166 static void cgraph_flatten (struct cgraph_node *node);
169 /* Statistics we collect about inlining algorithm. */
170 static int ncalls_inlined;
171 static int nfunctions_inlined;
172 static int overall_size;
173 static gcov_type max_count, max_benefit;
175 /* Holders of ipa cgraph hooks: */
176 static struct cgraph_node_hook_list *function_insertion_hook_holder;
178 static inline struct inline_summary *
179 inline_summary (struct cgraph_node *node)
181 return &node->local.inline_summary;
184 /* Estimate self time of the function after inlining WHAT into TO. */
187 cgraph_estimate_time_after_inlining (int frequency, struct cgraph_node *to,
188 struct cgraph_node *what)
190 gcov_type time = (((gcov_type)what->global.time
191 - inline_summary (what)->time_inlining_benefit)
192 * frequency + CGRAPH_FREQ_BASE / 2) / CGRAPH_FREQ_BASE
201 /* Estimate self time of the function after inlining WHAT into TO. */
204 cgraph_estimate_size_after_inlining (int times, struct cgraph_node *to,
205 struct cgraph_node *what)
207 int size = (what->global.size - inline_summary (what)->size_inlining_benefit) * times + to->global.size;
208 gcc_assert (size >= 0);
212 /* Scale frequency of NODE edges by FREQ_SCALE and increase loop nest
216 update_noncloned_frequencies (struct cgraph_node *node,
217 int freq_scale, int nest)
219 struct cgraph_edge *e;
221 /* We do not want to ignore high loop nest after freq drops to 0. */
224 for (e = node->callees; e; e = e->next_callee)
226 e->loop_nest += nest;
227 e->frequency = e->frequency * (gcov_type) freq_scale / CGRAPH_FREQ_BASE;
228 if (e->frequency > CGRAPH_FREQ_MAX)
229 e->frequency = CGRAPH_FREQ_MAX;
230 if (!e->inline_failed)
231 update_noncloned_frequencies (e->callee, freq_scale, nest);
235 /* E is expected to be an edge being inlined. Clone destination node of
236 the edge and redirect it to the new clone.
237 DUPLICATE is used for bookkeeping on whether we are actually creating new
238 clones or re-using node originally representing out-of-line function call.
241 cgraph_clone_inlined_nodes (struct cgraph_edge *e, bool duplicate,
242 bool update_original)
248 /* We may eliminate the need for out-of-line copy to be output.
249 In that case just go ahead and re-use it. */
250 if (!e->callee->callers->next_caller
251 && cgraph_can_remove_if_no_direct_calls_p (e->callee)
252 /* Don't reuse if more than one function shares a comdat group.
253 If the other function(s) are needed, we need to emit even
254 this function out of line. */
255 && !e->callee->same_comdat_group
256 && !cgraph_new_nodes)
258 gcc_assert (!e->callee->global.inlined_to);
259 if (e->callee->analyzed)
261 overall_size -= e->callee->global.size;
262 nfunctions_inlined++;
265 e->callee->local.externally_visible = false;
266 update_noncloned_frequencies (e->callee, e->frequency, e->loop_nest);
270 struct cgraph_node *n;
271 n = cgraph_clone_node (e->callee, e->count, e->frequency, e->loop_nest,
272 update_original, NULL);
273 cgraph_redirect_edge_callee (e, n);
277 if (e->caller->global.inlined_to)
278 e->callee->global.inlined_to = e->caller->global.inlined_to;
280 e->callee->global.inlined_to = e->caller;
281 e->callee->global.stack_frame_offset
282 = e->caller->global.stack_frame_offset
283 + inline_summary (e->caller)->estimated_self_stack_size;
284 peak = e->callee->global.stack_frame_offset
285 + inline_summary (e->callee)->estimated_self_stack_size;
286 if (e->callee->global.inlined_to->global.estimated_stack_size < peak)
287 e->callee->global.inlined_to->global.estimated_stack_size = peak;
289 /* Recursively clone all bodies. */
290 for (e = e->callee->callees; e; e = e->next_callee)
291 if (!e->inline_failed)
292 cgraph_clone_inlined_nodes (e, duplicate, update_original);
295 /* Mark edge E as inlined and update callgraph accordingly. UPDATE_ORIGINAL
296 specify whether profile of original function should be updated. If any new
297 indirect edges are discovered in the process, add them to NEW_EDGES, unless
298 it is NULL. Return true iff any new callgraph edges were discovered as a
299 result of inlining. */
302 cgraph_mark_inline_edge (struct cgraph_edge *e, bool update_original,
303 VEC (cgraph_edge_p, heap) **new_edges)
305 int old_size = 0, new_size = 0;
306 struct cgraph_node *to = NULL, *what;
307 struct cgraph_edge *curr = e;
309 bool duplicate = false;
310 int orig_size = e->callee->global.size;
312 gcc_assert (e->inline_failed);
313 e->inline_failed = CIF_OK;
315 if (!e->callee->global.inlined)
316 DECL_POSSIBLY_INLINED (e->callee->decl) = true;
317 e->callee->global.inlined = true;
319 if (e->callee->callers->next_caller
320 || !cgraph_can_remove_if_no_direct_calls_p (e->callee)
321 || e->callee->same_comdat_group)
323 cgraph_clone_inlined_nodes (e, true, update_original);
328 /* Now update size of caller and all functions caller is inlined into. */
329 for (;e && !e->inline_failed; e = e->caller->callers)
332 old_size = e->caller->global.size;
333 new_size = cgraph_estimate_size_after_inlining (1, to, what);
334 to->global.size = new_size;
335 to->global.time = cgraph_estimate_time_after_inlining (freq, to, what);
337 gcc_assert (what->global.inlined_to == to);
338 if (new_size > old_size)
339 overall_size += new_size - old_size;
341 overall_size -= orig_size;
344 if (flag_indirect_inlining)
345 return ipa_propagate_indirect_call_infos (curr, new_edges);
350 /* Mark all calls of EDGE->CALLEE inlined into EDGE->CALLER. */
353 cgraph_mark_inline (struct cgraph_edge *edge)
355 struct cgraph_node *to = edge->caller;
356 struct cgraph_node *what = edge->callee;
357 struct cgraph_edge *e, *next;
359 gcc_assert (!edge->call_stmt_cannot_inline_p);
360 /* Look for all calls, mark them inline and clone recursively
361 all inlined functions. */
362 for (e = what->callers; e; e = next)
364 next = e->next_caller;
365 if (e->caller == to && e->inline_failed)
367 cgraph_mark_inline_edge (e, true, NULL);
374 /* Estimate the growth caused by inlining NODE into all callees. */
377 cgraph_estimate_growth (struct cgraph_node *node)
380 struct cgraph_edge *e;
381 bool self_recursive = false;
383 if (node->global.estimated_growth != INT_MIN)
384 return node->global.estimated_growth;
386 for (e = node->callers; e; e = e->next_caller)
388 if (e->caller == node)
389 self_recursive = true;
390 if (e->inline_failed)
391 growth += (cgraph_estimate_size_after_inlining (1, e->caller, node)
392 - e->caller->global.size);
395 /* ??? Wrong for non-trivially self recursive functions or cases where
396 we decide to not inline for different reasons, but it is not big deal
397 as in that case we will keep the body around, but we will also avoid
399 if (cgraph_only_called_directly_p (node)
400 && !DECL_EXTERNAL (node->decl) && !self_recursive)
401 growth -= node->global.size;
403 node->global.estimated_growth = growth;
407 /* Return false when inlining WHAT into TO is not good idea
408 as it would cause too large growth of function bodies.
409 When ONE_ONLY is true, assume that only one call site is going
410 to be inlined, otherwise figure out how many call sites in
411 TO calls WHAT and verify that all can be inlined.
415 cgraph_check_inline_limits (struct cgraph_node *to, struct cgraph_node *what,
416 cgraph_inline_failed_t *reason, bool one_only)
419 struct cgraph_edge *e;
422 HOST_WIDE_INT stack_size_limit, inlined_stack;
427 for (e = to->callees; e; e = e->next_callee)
428 if (e->callee == what)
431 if (to->global.inlined_to)
432 to = to->global.inlined_to;
434 /* When inlining large function body called once into small function,
435 take the inlined function as base for limiting the growth. */
436 if (inline_summary (to)->self_size > inline_summary(what)->self_size)
437 limit = inline_summary (to)->self_size;
439 limit = inline_summary (what)->self_size;
441 limit += limit * PARAM_VALUE (PARAM_LARGE_FUNCTION_GROWTH) / 100;
443 /* Check the size after inlining against the function limits. But allow
444 the function to shrink if it went over the limits by forced inlining. */
445 newsize = cgraph_estimate_size_after_inlining (times, to, what);
446 if (newsize >= to->global.size
447 && newsize > PARAM_VALUE (PARAM_LARGE_FUNCTION_INSNS)
451 *reason = CIF_LARGE_FUNCTION_GROWTH_LIMIT;
455 stack_size_limit = inline_summary (to)->estimated_self_stack_size;
457 stack_size_limit += stack_size_limit * PARAM_VALUE (PARAM_STACK_FRAME_GROWTH) / 100;
459 inlined_stack = (to->global.stack_frame_offset
460 + inline_summary (to)->estimated_self_stack_size
461 + what->global.estimated_stack_size);
462 if (inlined_stack > stack_size_limit
463 && inlined_stack > PARAM_VALUE (PARAM_LARGE_STACK_FRAME))
466 *reason = CIF_LARGE_STACK_FRAME_GROWTH_LIMIT;
472 /* Return true when function N is small enough to be inlined. */
475 cgraph_default_inline_p (struct cgraph_node *n, cgraph_inline_failed_t *reason)
479 if (n->local.disregard_inline_limits)
482 if (!flag_inline_small_functions && !DECL_DECLARED_INLINE_P (decl))
485 *reason = CIF_FUNCTION_NOT_INLINE_CANDIDATE;
492 *reason = CIF_BODY_NOT_AVAILABLE;
496 if (DECL_DECLARED_INLINE_P (decl))
498 if (n->global.size >= MAX_INLINE_INSNS_SINGLE)
501 *reason = CIF_MAX_INLINE_INSNS_SINGLE_LIMIT;
507 if (n->global.size >= MAX_INLINE_INSNS_AUTO)
510 *reason = CIF_MAX_INLINE_INSNS_AUTO_LIMIT;
518 /* Return true when inlining WHAT would create recursive inlining.
519 We call recursive inlining all cases where same function appears more than
520 once in the single recursion nest path in the inline graph. */
523 cgraph_recursive_inlining_p (struct cgraph_node *to,
524 struct cgraph_node *what,
525 cgraph_inline_failed_t *reason)
528 if (to->global.inlined_to)
529 recursive = what->decl == to->global.inlined_to->decl;
531 recursive = what->decl == to->decl;
532 /* Marking recursive function inline has sane semantic and thus we should
534 if (recursive && reason)
535 *reason = (what->local.disregard_inline_limits
536 ? CIF_RECURSIVE_INLINING : CIF_UNSPECIFIED);
540 /* A cost model driving the inlining heuristics in a way so the edges with
541 smallest badness are inlined first. After each inlining is performed
542 the costs of all caller edges of nodes affected are recomputed so the
543 metrics may accurately depend on values such as number of inlinable callers
544 of the function or function body size. */
547 cgraph_edge_badness (struct cgraph_edge *edge)
551 cgraph_estimate_size_after_inlining (1, edge->caller, edge->callee);
553 growth -= edge->caller->global.size;
555 /* Always prefer inlining saving code size. */
557 badness = INT_MIN - growth;
559 /* When profiling is available, base priorities -(#calls / growth).
560 So we optimize for overall number of "executed" inlined calls. */
562 badness = ((int)((double)edge->count * INT_MIN / max_count / (max_benefit + 1))
563 * (inline_summary (edge->callee)->time_inlining_benefit + 1)) / growth;
565 /* When function local profile is available, base priorities on
566 growth / frequency, so we optimize for overall frequency of inlined
567 calls. This is not too accurate since while the call might be frequent
568 within function, the function itself is infrequent.
570 Other objective to optimize for is number of different calls inlined.
571 We add the estimated growth after inlining all functions to bias the
572 priorities slightly in this direction (so fewer times called functions
573 of the same size gets priority). */
574 else if (flag_guess_branch_prob)
576 int div = edge->frequency * 100 / CGRAPH_FREQ_BASE + 1;
577 badness = growth * 10000;
578 div *= MIN (100 * inline_summary (edge->callee)->time_inlining_benefit
579 / (edge->callee->global.time + 1) + 1, 100);
582 /* Decrease badness if call is nested. */
583 /* Compress the range so we don't overflow. */
585 div = 10000 + ceil_log2 (div) - 8;
590 badness += cgraph_estimate_growth (edge->callee);
591 if (badness > INT_MAX)
594 /* When function local profile is not available or it does not give
595 useful information (ie frequency is zero), base the cost on
596 loop nest and overall size growth, so we optimize for overall number
597 of functions fully inlined in program. */
600 int nest = MIN (edge->loop_nest, 8);
601 badness = cgraph_estimate_growth (edge->callee) * 256;
603 /* Decrease badness if call is nested. */
611 /* Make recursive inlining happen always after other inlining is done. */
612 if (cgraph_recursive_inlining_p (edge->caller, edge->callee, NULL))
618 /* Recompute heap nodes for each of caller edge. */
621 update_caller_keys (fibheap_t heap, struct cgraph_node *node,
622 bitmap updated_nodes)
624 struct cgraph_edge *edge;
625 cgraph_inline_failed_t failed_reason;
627 if (!node->local.inlinable || node->local.disregard_inline_limits
628 || node->global.inlined_to)
630 if (bitmap_bit_p (updated_nodes, node->uid))
632 bitmap_set_bit (updated_nodes, node->uid);
633 node->global.estimated_growth = INT_MIN;
635 if (!node->local.inlinable)
637 /* Prune out edges we won't inline into anymore. */
638 if (!cgraph_default_inline_p (node, &failed_reason))
640 for (edge = node->callers; edge; edge = edge->next_caller)
643 fibheap_delete_node (heap, (fibnode_t) edge->aux);
645 if (edge->inline_failed)
646 edge->inline_failed = failed_reason;
651 for (edge = node->callers; edge; edge = edge->next_caller)
652 if (edge->inline_failed)
654 int badness = cgraph_edge_badness (edge);
657 fibnode_t n = (fibnode_t) edge->aux;
658 gcc_assert (n->data == edge);
659 if (n->key == badness)
662 /* fibheap_replace_key only increase the keys. */
663 if (fibheap_replace_key (heap, n, badness))
665 fibheap_delete_node (heap, (fibnode_t) edge->aux);
667 edge->aux = fibheap_insert (heap, badness, edge);
671 /* Recompute heap nodes for each of caller edges of each of callees. */
674 update_callee_keys (fibheap_t heap, struct cgraph_node *node,
675 bitmap updated_nodes)
677 struct cgraph_edge *e;
678 node->global.estimated_growth = INT_MIN;
680 for (e = node->callees; e; e = e->next_callee)
681 if (e->inline_failed)
682 update_caller_keys (heap, e->callee, updated_nodes);
683 else if (!e->inline_failed)
684 update_callee_keys (heap, e->callee, updated_nodes);
687 /* Enqueue all recursive calls from NODE into priority queue depending on
688 how likely we want to recursively inline the call. */
691 lookup_recursive_calls (struct cgraph_node *node, struct cgraph_node *where,
695 struct cgraph_edge *e;
696 for (e = where->callees; e; e = e->next_callee)
697 if (e->callee == node)
699 /* When profile feedback is available, prioritize by expected number
700 of calls. Without profile feedback we maintain simple queue
701 to order candidates via recursive depths. */
702 fibheap_insert (heap,
703 !max_count ? priority++
704 : -(e->count / ((max_count + (1<<24) - 1) / (1<<24))),
707 for (e = where->callees; e; e = e->next_callee)
708 if (!e->inline_failed)
709 lookup_recursive_calls (node, e->callee, heap);
712 /* Decide on recursive inlining: in the case function has recursive calls,
713 inline until body size reaches given argument. If any new indirect edges
714 are discovered in the process, add them to *NEW_EDGES, unless NEW_EDGES
718 cgraph_decide_recursive_inlining (struct cgraph_node *node,
719 VEC (cgraph_edge_p, heap) **new_edges)
721 int limit = PARAM_VALUE (PARAM_MAX_INLINE_INSNS_RECURSIVE_AUTO);
722 int max_depth = PARAM_VALUE (PARAM_MAX_INLINE_RECURSIVE_DEPTH_AUTO);
723 int probability = PARAM_VALUE (PARAM_MIN_INLINE_RECURSIVE_PROBABILITY);
725 struct cgraph_edge *e;
726 struct cgraph_node *master_clone, *next;
730 /* It does not make sense to recursively inline always-inline functions
731 as we are going to sorry() on the remaining calls anyway. */
732 if (node->local.disregard_inline_limits
733 && lookup_attribute ("always_inline", DECL_ATTRIBUTES (node->decl)))
736 if (optimize_function_for_size_p (DECL_STRUCT_FUNCTION (node->decl))
737 || (!flag_inline_functions && !DECL_DECLARED_INLINE_P (node->decl)))
740 if (DECL_DECLARED_INLINE_P (node->decl))
742 limit = PARAM_VALUE (PARAM_MAX_INLINE_INSNS_RECURSIVE);
743 max_depth = PARAM_VALUE (PARAM_MAX_INLINE_RECURSIVE_DEPTH);
746 /* Make sure that function is small enough to be considered for inlining. */
748 || cgraph_estimate_size_after_inlining (1, node, node) >= limit)
750 heap = fibheap_new ();
751 lookup_recursive_calls (node, node, heap);
752 if (fibheap_empty (heap))
754 fibheap_delete (heap);
760 " Performing recursive inlining on %s\n",
761 cgraph_node_name (node));
763 /* We need original clone to copy around. */
764 master_clone = cgraph_clone_node (node, node->count, CGRAPH_FREQ_BASE, 1,
766 master_clone->needed = true;
767 for (e = master_clone->callees; e; e = e->next_callee)
768 if (!e->inline_failed)
769 cgraph_clone_inlined_nodes (e, true, false);
771 /* Do the inlining and update list of recursive call during process. */
772 while (!fibheap_empty (heap)
773 && (cgraph_estimate_size_after_inlining (1, node, master_clone)
776 struct cgraph_edge *curr
777 = (struct cgraph_edge *) fibheap_extract_min (heap);
778 struct cgraph_node *cnode;
781 for (cnode = curr->caller;
782 cnode->global.inlined_to; cnode = cnode->callers->caller)
783 if (node->decl == curr->callee->decl)
785 if (depth > max_depth)
789 " maximal depth reached\n");
795 if (!cgraph_maybe_hot_edge_p (curr))
798 fprintf (dump_file, " Not inlining cold call\n");
801 if (curr->count * 100 / node->count < probability)
805 " Probability of edge is too small\n");
813 " Inlining call of depth %i", depth);
816 fprintf (dump_file, " called approx. %.2f times per call",
817 (double)curr->count / node->count);
819 fprintf (dump_file, "\n");
821 cgraph_redirect_edge_callee (curr, master_clone);
822 cgraph_mark_inline_edge (curr, false, new_edges);
823 lookup_recursive_calls (node, curr->callee, heap);
826 if (!fibheap_empty (heap) && dump_file)
827 fprintf (dump_file, " Recursive inlining growth limit met.\n");
829 fibheap_delete (heap);
832 "\n Inlined %i times, body grown from size %i to %i, time %i to %i\n", n,
833 master_clone->global.size, node->global.size,
834 master_clone->global.time, node->global.time);
836 /* Remove master clone we used for inlining. We rely that clones inlined
837 into master clone gets queued just before master clone so we don't
839 for (node = cgraph_nodes; node != master_clone;
843 if (node->global.inlined_to == master_clone)
844 cgraph_remove_node (node);
846 cgraph_remove_node (master_clone);
847 /* FIXME: Recursive inlining actually reduces number of calls of the
848 function. At this place we should probably walk the function and
849 inline clones and compensate the counts accordingly. This probably
850 doesn't matter much in practice. */
854 /* Set inline_failed for all callers of given function to REASON. */
857 cgraph_set_inline_failed (struct cgraph_node *node,
858 cgraph_inline_failed_t reason)
860 struct cgraph_edge *e;
863 fprintf (dump_file, "Inlining failed: %s\n",
864 cgraph_inline_failed_string (reason));
865 for (e = node->callers; e; e = e->next_caller)
866 if (e->inline_failed)
867 e->inline_failed = reason;
870 /* Given whole compilation unit estimate of INSNS, compute how large we can
871 allow the unit to grow. */
873 compute_max_insns (int insns)
875 int max_insns = insns;
876 if (max_insns < PARAM_VALUE (PARAM_LARGE_UNIT_INSNS))
877 max_insns = PARAM_VALUE (PARAM_LARGE_UNIT_INSNS);
879 return ((HOST_WIDEST_INT) max_insns
880 * (100 + PARAM_VALUE (PARAM_INLINE_UNIT_GROWTH)) / 100);
883 /* Compute badness of all edges in NEW_EDGES and add them to the HEAP. */
885 add_new_edges_to_heap (fibheap_t heap, VEC (cgraph_edge_p, heap) *new_edges)
887 while (VEC_length (cgraph_edge_p, new_edges) > 0)
889 struct cgraph_edge *edge = VEC_pop (cgraph_edge_p, new_edges);
891 gcc_assert (!edge->aux);
892 edge->aux = fibheap_insert (heap, cgraph_edge_badness (edge), edge);
897 /* We use greedy algorithm for inlining of small functions:
898 All inline candidates are put into prioritized heap based on estimated
899 growth of the overall number of instructions and then update the estimates.
901 INLINED and INLINED_CALEES are just pointers to arrays large enough
902 to be passed to cgraph_inlined_into and cgraph_inlined_callees. */
905 cgraph_decide_inlining_of_small_functions (void)
907 struct cgraph_node *node;
908 struct cgraph_edge *edge;
909 cgraph_inline_failed_t failed_reason;
910 fibheap_t heap = fibheap_new ();
911 bitmap updated_nodes = BITMAP_ALLOC (NULL);
912 int min_size, max_size;
913 VEC (cgraph_edge_p, heap) *new_indirect_edges = NULL;
915 if (flag_indirect_inlining)
916 new_indirect_edges = VEC_alloc (cgraph_edge_p, heap, 8);
919 fprintf (dump_file, "\nDeciding on smaller functions:\n");
921 /* Put all inline candidates into the heap. */
923 for (node = cgraph_nodes; node; node = node->next)
925 if (!node->local.inlinable || !node->callers)
928 fprintf (dump_file, "Considering inline candidate %s.\n", cgraph_node_name (node));
930 node->global.estimated_growth = INT_MIN;
931 if (!cgraph_default_inline_p (node, &failed_reason))
933 cgraph_set_inline_failed (node, failed_reason);
937 for (edge = node->callers; edge; edge = edge->next_caller)
938 if (edge->inline_failed)
940 gcc_assert (!edge->aux);
941 edge->aux = fibheap_insert (heap, cgraph_edge_badness (edge), edge);
945 max_size = compute_max_insns (overall_size);
946 min_size = overall_size;
948 while (overall_size <= max_size
949 && (edge = (struct cgraph_edge *) fibheap_extract_min (heap)))
951 int old_size = overall_size;
952 struct cgraph_node *where;
954 cgraph_estimate_size_after_inlining (1, edge->caller, edge->callee);
955 cgraph_inline_failed_t not_good = CIF_OK;
957 growth -= edge->caller->global.size;
962 "\nConsidering %s with %i size\n",
963 cgraph_node_name (edge->callee),
964 edge->callee->global.size);
966 " to be inlined into %s in %s:%i\n"
967 " Estimated growth after inlined into all callees is %+i insns.\n"
968 " Estimated badness is %i, frequency %.2f.\n",
969 cgraph_node_name (edge->caller),
970 gimple_filename ((const_gimple) edge->call_stmt),
971 gimple_lineno ((const_gimple) edge->call_stmt),
972 cgraph_estimate_growth (edge->callee),
973 cgraph_edge_badness (edge),
974 edge->frequency / (double)CGRAPH_FREQ_BASE);
976 fprintf (dump_file," Called "HOST_WIDEST_INT_PRINT_DEC"x\n", edge->count);
978 gcc_assert (edge->aux);
980 if (!edge->inline_failed)
983 /* When not having profile info ready we don't weight by any way the
984 position of call in procedure itself. This means if call of
985 function A from function B seems profitable to inline, the recursive
986 call of function A in inline copy of A in B will look profitable too
987 and we end up inlining until reaching maximal function growth. This
988 is not good idea so prohibit the recursive inlining.
990 ??? When the frequencies are taken into account we might not need this
993 We need to be cureful here, in some testcases, e.g. directivec.c in
994 libcpp, we can estimate self recursive function to have negative growth
995 for inlining completely.
999 where = edge->caller;
1000 while (where->global.inlined_to)
1002 if (where->decl == edge->callee->decl)
1004 where = where->callers->caller;
1006 if (where->global.inlined_to)
1009 = (edge->callee->local.disregard_inline_limits
1010 ? CIF_RECURSIVE_INLINING : CIF_UNSPECIFIED);
1012 fprintf (dump_file, " inline_failed:Recursive inlining performed only for function itself.\n");
1017 if (!cgraph_maybe_hot_edge_p (edge))
1018 not_good = CIF_UNLIKELY_CALL;
1019 if (!flag_inline_functions
1020 && !DECL_DECLARED_INLINE_P (edge->callee->decl))
1021 not_good = CIF_NOT_DECLARED_INLINED;
1022 if (optimize_function_for_size_p (DECL_STRUCT_FUNCTION(edge->caller->decl)))
1023 not_good = CIF_OPTIMIZING_FOR_SIZE;
1024 if (not_good && growth > 0 && cgraph_estimate_growth (edge->callee) > 0)
1026 if (!cgraph_recursive_inlining_p (edge->caller, edge->callee,
1027 &edge->inline_failed))
1029 edge->inline_failed = not_good;
1031 fprintf (dump_file, " inline_failed:%s.\n",
1032 cgraph_inline_failed_string (edge->inline_failed));
1036 if (!cgraph_default_inline_p (edge->callee, &edge->inline_failed))
1038 if (!cgraph_recursive_inlining_p (edge->caller, edge->callee,
1039 &edge->inline_failed))
1042 fprintf (dump_file, " inline_failed:%s.\n",
1043 cgraph_inline_failed_string (edge->inline_failed));
1047 if (!tree_can_inline_p (edge))
1050 fprintf (dump_file, " inline_failed:%s.\n",
1051 cgraph_inline_failed_string (edge->inline_failed));
1054 if (cgraph_recursive_inlining_p (edge->caller, edge->callee,
1055 &edge->inline_failed))
1057 where = edge->caller;
1058 if (where->global.inlined_to)
1059 where = where->global.inlined_to;
1060 if (!cgraph_decide_recursive_inlining (where,
1061 flag_indirect_inlining
1062 ? &new_indirect_edges : NULL))
1064 if (flag_indirect_inlining)
1065 add_new_edges_to_heap (heap, new_indirect_edges);
1066 update_callee_keys (heap, where, updated_nodes);
1070 struct cgraph_node *callee;
1071 if (edge->call_stmt_cannot_inline_p
1072 || !cgraph_check_inline_limits (edge->caller, edge->callee,
1073 &edge->inline_failed, true))
1076 fprintf (dump_file, " Not inlining into %s:%s.\n",
1077 cgraph_node_name (edge->caller),
1078 cgraph_inline_failed_string (edge->inline_failed));
1081 callee = edge->callee;
1082 cgraph_mark_inline_edge (edge, true, &new_indirect_edges);
1083 if (flag_indirect_inlining)
1084 add_new_edges_to_heap (heap, new_indirect_edges);
1086 update_callee_keys (heap, callee, updated_nodes);
1088 where = edge->caller;
1089 if (where->global.inlined_to)
1090 where = where->global.inlined_to;
1092 /* Our profitability metric can depend on local properties
1093 such as number of inlinable calls and size of the function body.
1094 After inlining these properties might change for the function we
1095 inlined into (since it's body size changed) and for the functions
1096 called by function we inlined (since number of it inlinable callers
1098 update_caller_keys (heap, where, updated_nodes);
1099 bitmap_clear (updated_nodes);
1104 " Inlined into %s which now has size %i and self time %i,"
1105 "net change of %+i.\n",
1106 cgraph_node_name (edge->caller),
1107 edge->caller->global.time,
1108 edge->caller->global.size,
1109 overall_size - old_size);
1111 if (min_size > overall_size)
1113 min_size = overall_size;
1114 max_size = compute_max_insns (min_size);
1117 fprintf (dump_file, "New minimal size reached: %i\n", min_size);
1120 while ((edge = (struct cgraph_edge *) fibheap_extract_min (heap)) != NULL)
1122 gcc_assert (edge->aux);
1124 if (!edge->callee->local.disregard_inline_limits && edge->inline_failed
1125 && !cgraph_recursive_inlining_p (edge->caller, edge->callee,
1126 &edge->inline_failed))
1127 edge->inline_failed = CIF_INLINE_UNIT_GROWTH_LIMIT;
1130 if (new_indirect_edges)
1131 VEC_free (cgraph_edge_p, heap, new_indirect_edges);
1132 fibheap_delete (heap);
1133 BITMAP_FREE (updated_nodes);
1136 /* Flatten NODE from the IPA inliner. */
1139 cgraph_flatten (struct cgraph_node *node)
1141 struct cgraph_edge *e;
1143 /* We shouldn't be called recursively when we are being processed. */
1144 gcc_assert (node->aux == NULL);
1146 node->aux = (void *)(size_t) INLINE_ALL;
1148 for (e = node->callees; e; e = e->next_callee)
1150 struct cgraph_node *orig_callee;
1152 if (e->call_stmt_cannot_inline_p)
1155 if (!e->callee->analyzed)
1159 "Not inlining: Function body not available.\n");
1163 /* We've hit cycle? It is time to give up. */
1168 "Not inlining %s into %s to avoid cycle.\n",
1169 cgraph_node_name (e->callee),
1170 cgraph_node_name (e->caller));
1171 e->inline_failed = CIF_RECURSIVE_INLINING;
1175 /* When the edge is already inlined, we just need to recurse into
1176 it in order to fully flatten the leaves. */
1177 if (!e->inline_failed)
1179 cgraph_flatten (e->callee);
1183 if (cgraph_recursive_inlining_p (node, e->callee, &e->inline_failed))
1186 fprintf (dump_file, "Not inlining: recursive call.\n");
1190 if (!tree_can_inline_p (e))
1193 fprintf (dump_file, "Not inlining: %s",
1194 cgraph_inline_failed_string (e->inline_failed));
1198 /* Inline the edge and flatten the inline clone. Avoid
1199 recursing through the original node if the node was cloned. */
1201 fprintf (dump_file, " Inlining %s into %s.\n",
1202 cgraph_node_name (e->callee),
1203 cgraph_node_name (e->caller));
1204 orig_callee = e->callee;
1205 cgraph_mark_inline_edge (e, true, NULL);
1206 if (e->callee != orig_callee)
1207 orig_callee->aux = (void *)(size_t) INLINE_ALL;
1208 cgraph_flatten (e->callee);
1209 if (e->callee != orig_callee)
1210 orig_callee->aux = NULL;
1216 /* Decide on the inlining. We do so in the topological order to avoid
1217 expenses on updating data structures. */
1220 cgraph_decide_inlining (void)
1222 struct cgraph_node *node;
1224 struct cgraph_node **order =
1225 XCNEWVEC (struct cgraph_node *, cgraph_n_nodes);
1228 int initial_size = 0;
1230 cgraph_remove_function_insertion_hook (function_insertion_hook_holder);
1231 if (in_lto_p && flag_indirect_inlining)
1232 ipa_update_after_lto_read ();
1236 for (node = cgraph_nodes; node; node = node->next)
1239 struct cgraph_edge *e;
1241 gcc_assert (inline_summary (node)->self_size == node->global.size);
1242 initial_size += node->global.size;
1243 for (e = node->callees; e; e = e->next_callee)
1244 if (max_count < e->count)
1245 max_count = e->count;
1246 if (max_benefit < inline_summary (node)->time_inlining_benefit)
1247 max_benefit = inline_summary (node)->time_inlining_benefit;
1249 gcc_assert (in_lto_p
1251 || (profile_info && flag_branch_probabilities));
1252 overall_size = initial_size;
1254 nnodes = cgraph_postorder (order);
1258 "\nDeciding on inlining. Starting with size %i.\n",
1261 for (node = cgraph_nodes; node; node = node->next)
1265 fprintf (dump_file, "\nFlattening functions:\n");
1267 /* In the first pass handle functions to be flattened. Do this with
1268 a priority so none of our later choices will make this impossible. */
1269 for (i = nnodes - 1; i >= 0; i--)
1273 /* Handle nodes to be flattened, but don't update overall unit
1274 size. Calling the incremental inliner here is lame,
1275 a simple worklist should be enough. What should be left
1276 here from the early inliner (if it runs) is cyclic cases.
1277 Ideally when processing callees we stop inlining at the
1278 entry of cycles, possibly cloning that entry point and
1279 try to flatten itself turning it into a self-recursive
1281 if (lookup_attribute ("flatten",
1282 DECL_ATTRIBUTES (node->decl)) != NULL)
1286 "Flattening %s\n", cgraph_node_name (node));
1287 cgraph_flatten (node);
1291 cgraph_decide_inlining_of_small_functions ();
1293 if (flag_inline_functions_called_once)
1296 fprintf (dump_file, "\nDeciding on functions called once:\n");
1298 /* And finally decide what functions are called once. */
1299 for (i = nnodes - 1; i >= 0; i--)
1304 && !node->callers->next_caller
1305 && cgraph_only_called_directly_p (node)
1306 && node->local.inlinable
1307 && node->callers->inline_failed
1308 && node->callers->caller != node
1309 && node->callers->caller->global.inlined_to != node
1310 && !node->callers->call_stmt_cannot_inline_p
1311 && !DECL_EXTERNAL (node->decl)
1312 && !DECL_COMDAT (node->decl))
1314 cgraph_inline_failed_t reason;
1315 old_size = overall_size;
1319 "\nConsidering %s size %i.\n",
1320 cgraph_node_name (node), node->global.size);
1322 " Called once from %s %i insns.\n",
1323 cgraph_node_name (node->callers->caller),
1324 node->callers->caller->global.size);
1327 if (cgraph_check_inline_limits (node->callers->caller, node,
1330 cgraph_mark_inline (node->callers);
1333 " Inlined into %s which now has %i size"
1334 " for a net change of %+i size.\n",
1335 cgraph_node_name (node->callers->caller),
1336 node->callers->caller->global.size,
1337 overall_size - old_size);
1343 " Not inlining: %s.\n",
1344 cgraph_inline_failed_string (reason));
1350 /* Free ipa-prop structures if they are no longer needed. */
1351 if (flag_indirect_inlining)
1352 free_all_ipa_structures_after_iinln ();
1356 "\nInlined %i calls, eliminated %i functions, "
1357 "size %i turned to %i size.\n\n",
1358 ncalls_inlined, nfunctions_inlined, initial_size,
1364 /* Return true when N is leaf function. Accept cheap (pure&const) builtins
1365 in leaf functions. */
1367 leaf_node_p (struct cgraph_node *n)
1369 struct cgraph_edge *e;
1370 for (e = n->callees; e; e = e->next_callee)
1371 if (!DECL_BUILT_IN (e->callee->decl)
1372 || (!TREE_READONLY (e->callee->decl)
1373 || DECL_PURE_P (e->callee->decl)))
1378 /* Decide on the inlining. We do so in the topological order to avoid
1379 expenses on updating data structures. */
1382 cgraph_decide_inlining_incrementally (struct cgraph_node *node,
1383 enum inlining_mode mode)
1385 struct cgraph_edge *e;
1386 bool inlined = false;
1387 cgraph_inline_failed_t failed_reason;
1389 #ifdef ENABLE_CHECKING
1390 verify_cgraph_node (node);
1393 if (mode != INLINE_ALWAYS_INLINE && mode != INLINE_SIZE_NORECURSIVE
1394 && lookup_attribute ("flatten", DECL_ATTRIBUTES (node->decl)) != NULL)
1397 fprintf (dump_file, "Incrementally flattening %s\n",
1398 cgraph_node_name (node));
1402 /* First of all look for always inline functions. */
1403 if (mode != INLINE_SIZE_NORECURSIVE)
1404 for (e = node->callees; e; e = e->next_callee)
1406 if (!e->callee->local.disregard_inline_limits
1407 && (mode != INLINE_ALL || !e->callee->local.inlinable))
1409 if (e->call_stmt_cannot_inline_p)
1413 "Considering to always inline inline candidate %s.\n",
1414 cgraph_node_name (e->callee));
1415 if (cgraph_recursive_inlining_p (node, e->callee, &e->inline_failed))
1418 fprintf (dump_file, "Not inlining: recursive call.\n");
1421 if (!tree_can_inline_p (e))
1426 cgraph_inline_failed_string (e->inline_failed));
1429 if (gimple_in_ssa_p (DECL_STRUCT_FUNCTION (node->decl))
1430 != gimple_in_ssa_p (DECL_STRUCT_FUNCTION (e->callee->decl)))
1433 fprintf (dump_file, "Not inlining: SSA form does not match.\n");
1436 if (!e->callee->analyzed)
1440 "Not inlining: Function body no longer available.\n");
1445 fprintf (dump_file, " Inlining %s into %s.\n",
1446 cgraph_node_name (e->callee),
1447 cgraph_node_name (e->caller));
1448 cgraph_mark_inline (e);
1452 /* Now do the automatic inlining. */
1453 if (mode != INLINE_ALL && mode != INLINE_ALWAYS_INLINE
1454 /* Never inline regular functions into always-inline functions
1455 during incremental inlining. */
1456 && !node->local.disregard_inline_limits)
1458 bitmap visited = BITMAP_ALLOC (NULL);
1459 for (e = node->callees; e; e = e->next_callee)
1461 int allowed_growth = 0;
1462 if (!e->callee->local.inlinable
1463 || !e->inline_failed
1464 || e->callee->local.disregard_inline_limits)
1466 /* We are inlining a function to all call-sites in node
1467 or to none. So visit each candidate only once. */
1468 if (!bitmap_set_bit (visited, e->callee->uid))
1471 fprintf (dump_file, "Considering inline candidate %s.\n",
1472 cgraph_node_name (e->callee));
1473 if (cgraph_recursive_inlining_p (node, e->callee, &e->inline_failed))
1476 fprintf (dump_file, "Not inlining: recursive call.\n");
1479 if (gimple_in_ssa_p (DECL_STRUCT_FUNCTION (node->decl))
1480 != gimple_in_ssa_p (DECL_STRUCT_FUNCTION (e->callee->decl)))
1484 "Not inlining: SSA form does not match.\n");
1488 if (cgraph_maybe_hot_edge_p (e) && leaf_node_p (e->callee)
1489 && optimize_function_for_speed_p (cfun))
1490 allowed_growth = PARAM_VALUE (PARAM_EARLY_INLINING_INSNS);
1492 /* When the function body would grow and inlining the function
1493 won't eliminate the need for offline copy of the function,
1495 if (((mode == INLINE_SIZE || mode == INLINE_SIZE_NORECURSIVE)
1496 || (!flag_inline_functions
1497 && !DECL_DECLARED_INLINE_P (e->callee->decl)))
1498 && (cgraph_estimate_size_after_inlining (1, e->caller, e->callee)
1499 > e->caller->global.size + allowed_growth)
1500 && cgraph_estimate_growth (e->callee) > allowed_growth)
1504 "Not inlining: code size would grow by %i.\n",
1505 cgraph_estimate_size_after_inlining (1, e->caller,
1507 - e->caller->global.size);
1510 if (!cgraph_check_inline_limits (node, e->callee, &e->inline_failed,
1512 || e->call_stmt_cannot_inline_p)
1515 fprintf (dump_file, "Not inlining: %s.\n",
1516 cgraph_inline_failed_string (e->inline_failed));
1519 if (!e->callee->analyzed)
1523 "Not inlining: Function body no longer available.\n");
1526 if (!tree_can_inline_p (e))
1530 "Not inlining: %s.",
1531 cgraph_inline_failed_string (e->inline_failed));
1534 if (cgraph_default_inline_p (e->callee, &failed_reason))
1537 fprintf (dump_file, " Inlining %s into %s.\n",
1538 cgraph_node_name (e->callee),
1539 cgraph_node_name (e->caller));
1540 cgraph_mark_inline (e);
1544 BITMAP_FREE (visited);
1549 /* Because inlining might remove no-longer reachable nodes, we need to
1550 keep the array visible to garbage collector to avoid reading collected
1553 static GTY ((length ("nnodes"))) struct cgraph_node **order;
1555 /* Do inlining of small functions. Doing so early helps profiling and other
1556 passes to be somewhat more effective and avoids some code duplication in
1557 later real inlining pass for testcases with very many function calls. */
1559 cgraph_early_inlining (void)
1561 struct cgraph_node *node = cgraph_node (current_function_decl);
1562 unsigned int todo = 0;
1565 if (sorrycount || errorcount)
1570 || !flag_early_inlining)
1572 /* When not optimizing or not inlining inline only always-inline
1574 cgraph_decide_inlining_incrementally (node, INLINE_ALWAYS_INLINE);
1575 timevar_push (TV_INTEGRATION);
1576 todo |= optimize_inline_calls (current_function_decl);
1577 timevar_pop (TV_INTEGRATION);
1581 /* We iterate incremental inlining to get trivial cases of indirect
1583 while (iterations < PARAM_VALUE (PARAM_EARLY_INLINER_MAX_ITERATIONS)
1584 && cgraph_decide_inlining_incrementally (node,
1586 ? INLINE_SIZE_NORECURSIVE
1589 timevar_push (TV_INTEGRATION);
1590 todo |= optimize_inline_calls (current_function_decl);
1592 timevar_pop (TV_INTEGRATION);
1595 fprintf (dump_file, "Iterations: %i\n", iterations);
1598 cfun->always_inline_functions_inlined = true;
1603 struct gimple_opt_pass pass_early_inline =
1607 "einline", /* name */
1609 cgraph_early_inlining, /* execute */
1612 0, /* static_pass_number */
1613 TV_INLINE_HEURISTICS, /* tv_id */
1614 0, /* properties_required */
1615 0, /* properties_provided */
1616 0, /* properties_destroyed */
1617 0, /* todo_flags_start */
1618 TODO_dump_func /* todo_flags_finish */
1622 /* When inlining shall be performed. */
1624 cgraph_gate_ipa_early_inlining (void)
1626 return (flag_early_inlining
1628 && (flag_branch_probabilities || flag_test_coverage
1629 || profile_arc_flag));
1632 /* IPA pass wrapper for early inlining pass. We need to run early inlining
1633 before tree profiling so we have stand alone IPA pass for doing so. */
1634 struct simple_ipa_opt_pass pass_ipa_early_inline =
1638 "einline_ipa", /* name */
1639 cgraph_gate_ipa_early_inlining, /* gate */
1643 0, /* static_pass_number */
1644 TV_INLINE_HEURISTICS, /* tv_id */
1645 0, /* properties_required */
1646 0, /* properties_provided */
1647 0, /* properties_destroyed */
1648 0, /* todo_flags_start */
1649 TODO_dump_cgraph /* todo_flags_finish */
1653 /* See if statement might disappear after inlining. We are not terribly
1654 sophisficated, basically looking for simple abstraction penalty wrappers. */
1657 likely_eliminated_by_inlining_p (gimple stmt)
1659 enum gimple_code code = gimple_code (stmt);
1665 if (gimple_num_ops (stmt) != 2)
1668 /* Casts of parameters, loads from parameters passed by reference
1669 and stores to return value or parameters are probably free after
1671 if (gimple_assign_rhs_code (stmt) == CONVERT_EXPR
1672 || gimple_assign_rhs_code (stmt) == NOP_EXPR
1673 || gimple_assign_rhs_code (stmt) == VIEW_CONVERT_EXPR
1674 || gimple_assign_rhs_class (stmt) == GIMPLE_SINGLE_RHS)
1676 tree rhs = gimple_assign_rhs1 (stmt);
1677 tree lhs = gimple_assign_lhs (stmt);
1678 tree inner_rhs = rhs;
1679 tree inner_lhs = lhs;
1680 bool rhs_free = false;
1681 bool lhs_free = false;
1683 while (handled_component_p (inner_lhs) || TREE_CODE (inner_lhs) == INDIRECT_REF)
1684 inner_lhs = TREE_OPERAND (inner_lhs, 0);
1685 while (handled_component_p (inner_rhs)
1686 || TREE_CODE (inner_rhs) == ADDR_EXPR || TREE_CODE (inner_rhs) == INDIRECT_REF)
1687 inner_rhs = TREE_OPERAND (inner_rhs, 0);
1690 if (TREE_CODE (inner_rhs) == PARM_DECL
1691 || (TREE_CODE (inner_rhs) == SSA_NAME
1692 && SSA_NAME_IS_DEFAULT_DEF (inner_rhs)
1693 && TREE_CODE (SSA_NAME_VAR (inner_rhs)) == PARM_DECL))
1695 if (rhs_free && is_gimple_reg (lhs))
1697 if (((TREE_CODE (inner_lhs) == PARM_DECL
1698 || (TREE_CODE (inner_lhs) == SSA_NAME
1699 && SSA_NAME_IS_DEFAULT_DEF (inner_lhs)
1700 && TREE_CODE (SSA_NAME_VAR (inner_lhs)) == PARM_DECL))
1701 && inner_lhs != lhs)
1702 || TREE_CODE (inner_lhs) == RESULT_DECL
1703 || (TREE_CODE (inner_lhs) == SSA_NAME
1704 && TREE_CODE (SSA_NAME_VAR (inner_lhs)) == RESULT_DECL))
1706 if (lhs_free && (is_gimple_reg (rhs) || is_gimple_min_invariant (rhs)))
1708 if (lhs_free && rhs_free)
1717 /* Compute function body size parameters for NODE. */
1720 estimate_function_body_sizes (struct cgraph_node *node)
1723 gcov_type time_inlining_benefit = 0;
1725 int size_inlining_benefit = 0;
1727 gimple_stmt_iterator bsi;
1728 struct function *my_function = DECL_STRUCT_FUNCTION (node->decl);
1731 tree funtype = TREE_TYPE (node->decl);
1733 if (node->local.disregard_inline_limits)
1735 inline_summary (node)->self_time = 0;
1736 inline_summary (node)->self_size = 0;
1737 inline_summary (node)->time_inlining_benefit = 0;
1738 inline_summary (node)->size_inlining_benefit = 0;
1742 fprintf (dump_file, "Analyzing function body size: %s\n",
1743 cgraph_node_name (node));
1745 gcc_assert (my_function && my_function->cfg);
1746 FOR_EACH_BB_FN (bb, my_function)
1748 freq = compute_call_stmt_bb_frequency (node->decl, bb);
1749 for (bsi = gsi_start_bb (bb); !gsi_end_p (bsi); gsi_next (&bsi))
1751 gimple stmt = gsi_stmt (bsi);
1752 int this_size = estimate_num_insns (stmt, &eni_size_weights);
1753 int this_time = estimate_num_insns (stmt, &eni_time_weights);
1755 if (dump_file && (dump_flags & TDF_DETAILS))
1757 fprintf (dump_file, " freq:%6i size:%3i time:%3i ",
1758 freq, this_size, this_time);
1759 print_gimple_stmt (dump_file, stmt, 0, 0);
1764 if (likely_eliminated_by_inlining_p (stmt))
1766 size_inlining_benefit += this_size;
1767 time_inlining_benefit += this_time;
1768 if (dump_file && (dump_flags & TDF_DETAILS))
1769 fprintf (dump_file, " Likely eliminated\n");
1771 gcc_assert (time >= 0);
1772 gcc_assert (size >= 0);
1775 time = (time + CGRAPH_FREQ_BASE / 2) / CGRAPH_FREQ_BASE;
1776 time_inlining_benefit = ((time_inlining_benefit + CGRAPH_FREQ_BASE / 2)
1777 / CGRAPH_FREQ_BASE);
1779 fprintf (dump_file, "Overall function body time: %i-%i size: %i-%i\n",
1780 (int)time, (int)time_inlining_benefit,
1781 size, size_inlining_benefit);
1782 time_inlining_benefit += eni_time_weights.call_cost;
1783 size_inlining_benefit += eni_size_weights.call_cost;
1784 if (!VOID_TYPE_P (TREE_TYPE (funtype)))
1786 int cost = estimate_move_cost (TREE_TYPE (funtype));
1787 time_inlining_benefit += cost;
1788 size_inlining_benefit += cost;
1790 for (arg = DECL_ARGUMENTS (node->decl); arg; arg = TREE_CHAIN (arg))
1791 if (!VOID_TYPE_P (TREE_TYPE (arg)))
1793 int cost = estimate_move_cost (TREE_TYPE (arg));
1794 time_inlining_benefit += cost;
1795 size_inlining_benefit += cost;
1797 if (time_inlining_benefit > MAX_TIME)
1798 time_inlining_benefit = MAX_TIME;
1799 if (time > MAX_TIME)
1801 inline_summary (node)->self_time = time;
1802 inline_summary (node)->self_size = size;
1804 fprintf (dump_file, "With function call overhead time: %i-%i size: %i-%i\n",
1805 (int)time, (int)time_inlining_benefit,
1806 size, size_inlining_benefit);
1807 inline_summary (node)->time_inlining_benefit = time_inlining_benefit;
1808 inline_summary (node)->size_inlining_benefit = size_inlining_benefit;
1811 /* Compute parameters of functions used by inliner. */
1813 compute_inline_parameters (struct cgraph_node *node)
1815 HOST_WIDE_INT self_stack_size;
1817 gcc_assert (!node->global.inlined_to);
1819 /* Estimate the stack size for the function. But not at -O0
1820 because estimated_stack_frame_size is a quadratic problem. */
1821 self_stack_size = optimize ? estimated_stack_frame_size () : 0;
1822 inline_summary (node)->estimated_self_stack_size = self_stack_size;
1823 node->global.estimated_stack_size = self_stack_size;
1824 node->global.stack_frame_offset = 0;
1826 /* Can this function be inlined at all? */
1827 node->local.inlinable = tree_inlinable_function_p (node->decl);
1828 if (node->local.inlinable && !node->local.disregard_inline_limits)
1829 node->local.disregard_inline_limits
1830 = DECL_DISREGARD_INLINE_LIMITS (node->decl);
1831 estimate_function_body_sizes (node);
1832 /* Inlining characteristics are maintained by the cgraph_mark_inline. */
1833 node->global.time = inline_summary (node)->self_time;
1834 node->global.size = inline_summary (node)->self_size;
1839 /* Compute parameters of functions used by inliner using
1840 current_function_decl. */
1842 compute_inline_parameters_for_current (void)
1844 compute_inline_parameters (cgraph_node (current_function_decl));
1848 struct gimple_opt_pass pass_inline_parameters =
1852 "inline_param", /* name */
1854 compute_inline_parameters_for_current,/* execute */
1857 0, /* static_pass_number */
1858 TV_INLINE_HEURISTICS, /* tv_id */
1859 0, /* properties_required */
1860 0, /* properties_provided */
1861 0, /* properties_destroyed */
1862 0, /* todo_flags_start */
1863 0 /* todo_flags_finish */
1867 /* This function performs intraprocedural analyzis in NODE that is required to
1868 inline indirect calls. */
1870 inline_indirect_intraprocedural_analysis (struct cgraph_node *node)
1872 struct cgraph_edge *cs;
1876 ipa_initialize_node_params (node);
1877 ipa_detect_param_modifications (node);
1879 ipa_analyze_params_uses (node);
1882 for (cs = node->callees; cs; cs = cs->next_callee)
1884 ipa_count_arguments (cs);
1885 ipa_compute_jump_functions (cs);
1890 ipa_print_node_params (dump_file, node);
1891 ipa_print_node_jump_functions (dump_file, node);
1895 /* Note function body size. */
1897 analyze_function (struct cgraph_node *node)
1899 push_cfun (DECL_STRUCT_FUNCTION (node->decl));
1900 current_function_decl = node->decl;
1902 compute_inline_parameters (node);
1903 if (flag_indirect_inlining)
1904 inline_indirect_intraprocedural_analysis (node);
1906 current_function_decl = NULL;
1910 /* Called when new function is inserted to callgraph late. */
1912 add_new_function (struct cgraph_node *node, void *data ATTRIBUTE_UNUSED)
1914 analyze_function (node);
1917 /* Note function body size. */
1919 inline_generate_summary (void)
1921 struct cgraph_node *node;
1923 function_insertion_hook_holder =
1924 cgraph_add_function_insertion_hook (&add_new_function, NULL);
1926 if (flag_indirect_inlining)
1928 ipa_register_cgraph_hooks ();
1929 ipa_check_create_node_params ();
1930 ipa_check_create_edge_args ();
1933 for (node = cgraph_nodes; node; node = node->next)
1935 analyze_function (node);
1940 /* Apply inline plan to function. */
1942 inline_transform (struct cgraph_node *node)
1944 unsigned int todo = 0;
1945 struct cgraph_edge *e;
1947 /* FIXME: Currently the passmanager is adding inline transform more than once to some
1948 clones. This needs revisiting after WPA cleanups. */
1949 if (cfun->after_inlining)
1952 /* We might need the body of this function so that we can expand
1953 it inline somewhere else. */
1954 if (cgraph_preserve_function_body_p (node->decl))
1955 save_inline_function_body (node);
1957 for (e = node->callees; e; e = e->next_callee)
1958 if (!e->inline_failed || warn_inline)
1963 timevar_push (TV_INTEGRATION);
1964 todo = optimize_inline_calls (current_function_decl);
1965 timevar_pop (TV_INTEGRATION);
1967 cfun->always_inline_functions_inlined = true;
1968 cfun->after_inlining = true;
1969 return todo | execute_fixup_cfg ();
1972 /* Read inline summary. Jump functions are shared among ipa-cp
1973 and inliner, so when ipa-cp is active, we don't need to write them
1977 inline_read_summary (void)
1979 if (flag_indirect_inlining)
1981 ipa_register_cgraph_hooks ();
1983 ipa_prop_read_jump_functions ();
1985 function_insertion_hook_holder =
1986 cgraph_add_function_insertion_hook (&add_new_function, NULL);
1989 /* Write inline summary for node in SET.
1990 Jump functions are shared among ipa-cp and inliner, so when ipa-cp is
1991 active, we don't need to write them twice. */
1994 inline_write_summary (cgraph_node_set set)
1996 if (flag_indirect_inlining && !flag_ipa_cp)
1997 ipa_prop_write_jump_functions (set);
2000 /* When to run IPA inlining. Inlining of always-inline functions
2001 happens during early inlining. */
2004 gate_cgraph_decide_inlining (void)
2006 /* ??? We'd like to skip this if not optimizing or not inlining as
2007 all always-inline functions have been processed by early
2008 inlining already. But this at least breaks EH with C++ as
2009 we need to unconditionally run fixup_cfg even at -O0.
2010 So leave it on unconditionally for now. */
2014 struct ipa_opt_pass_d pass_ipa_inline =
2018 "inline", /* name */
2019 gate_cgraph_decide_inlining, /* gate */
2020 cgraph_decide_inlining, /* execute */
2023 0, /* static_pass_number */
2024 TV_INLINE_HEURISTICS, /* tv_id */
2025 0, /* properties_required */
2026 0, /* properties_provided */
2027 0, /* properties_destroyed */
2028 TODO_remove_functions, /* todo_flags_finish */
2029 TODO_dump_cgraph | TODO_dump_func
2030 | TODO_remove_functions /* todo_flags_finish */
2032 inline_generate_summary, /* generate_summary */
2033 inline_write_summary, /* write_summary */
2034 inline_read_summary, /* read_summary */
2035 NULL, /* function_read_summary */
2036 lto_ipa_fixup_call_notes, /* stmt_fixup */
2038 inline_transform, /* function_transform */
2039 NULL, /* variable_transform */
2043 #include "gt-ipa-inline.h"