1 /* Inlining decision heuristics.
2 Copyright (C) 2003, 2004 Free Software Foundation, Inc.
3 Contributed by Jan Hubicka
5 This file is part of GCC.
7 GCC is free software; you can redistribute it and/or modify it under
8 the terms of the GNU General Public License as published by the Free
9 Software Foundation; either version 2, or (at your option) any later
12 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
13 WARRANTY; without even the implied warranty of MERCHANTABILITY or
14 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
17 You should have received a copy of the GNU General Public License
18 along with GCC; see the file COPYING. If not, write to the Free
19 Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA
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 in non-unit-at-a-time mode. */
68 #include "coretypes.h"
71 #include "tree-inline.h"
72 #include "langhooks.h"
75 #include "diagnostic.h"
80 #include "tree-pass.h"
85 /* Statistics we collect about inlining algorithm. */
86 static int ncalls_inlined;
87 static int nfunctions_inlined;
88 static int initial_insns;
89 static int overall_insns;
91 static gcov_type max_count;
93 /* Estimate size of the function after inlining WHAT into TO. */
96 cgraph_estimate_size_after_inlining (int times, struct cgraph_node *to,
97 struct cgraph_node *what)
100 tree fndecl = what->decl, arg;
101 int call_insns = PARAM_VALUE (PARAM_INLINE_CALL_COST);
103 for (arg = DECL_ARGUMENTS (fndecl); arg; arg = TREE_CHAIN (arg))
104 call_insns += estimate_move_cost (TREE_TYPE (arg));
105 size = (what->global.insns - call_insns) * times + to->global.insns;
106 gcc_assert (size >= 0);
110 /* E is expected to be an edge being inlined. Clone destination node of
111 the edge and redirect it to the new clone.
112 DUPLICATE is used for bookkeeping on whether we are actually creating new
113 clones or re-using node originally representing out-of-line function call.
116 cgraph_clone_inlined_nodes (struct cgraph_edge *e, bool duplicate)
118 struct cgraph_node *n;
120 /* We may eliminate the need for out-of-line copy to be output. In that
121 case just go ahead and re-use it. */
122 if (!e->callee->callers->next_caller
123 && (!e->callee->needed || DECL_EXTERNAL (e->callee->decl))
125 && flag_unit_at_a_time)
127 gcc_assert (!e->callee->global.inlined_to);
128 if (!DECL_EXTERNAL (e->callee->decl))
129 overall_insns -= e->callee->global.insns, nfunctions_inlined++;
134 n = cgraph_clone_node (e->callee, e->count, e->loop_nest);
135 cgraph_redirect_edge_callee (e, n);
138 if (e->caller->global.inlined_to)
139 e->callee->global.inlined_to = e->caller->global.inlined_to;
141 e->callee->global.inlined_to = e->caller;
143 /* Recursively clone all bodies. */
144 for (e = e->callee->callees; e; e = e->next_callee)
145 if (!e->inline_failed)
146 cgraph_clone_inlined_nodes (e, duplicate);
149 /* Mark edge E as inlined and update callgraph accordingly. */
152 cgraph_mark_inline_edge (struct cgraph_edge *e)
154 int old_insns = 0, new_insns = 0;
155 struct cgraph_node *to = NULL, *what;
157 gcc_assert (e->inline_failed);
158 e->inline_failed = NULL;
160 if (!e->callee->global.inlined && flag_unit_at_a_time)
161 DECL_POSSIBLY_INLINED (e->callee->decl) = true;
162 e->callee->global.inlined = true;
164 cgraph_clone_inlined_nodes (e, true);
168 /* Now update size of caller and all functions caller is inlined into. */
169 for (;e && !e->inline_failed; e = e->caller->callers)
171 old_insns = e->caller->global.insns;
172 new_insns = cgraph_estimate_size_after_inlining (1, e->caller,
174 gcc_assert (new_insns >= 0);
176 to->global.insns = new_insns;
178 gcc_assert (what->global.inlined_to == to);
179 if (new_insns > old_insns)
180 overall_insns += new_insns - old_insns;
184 /* Mark all calls of EDGE->CALLEE inlined into EDGE->CALLER.
185 Return following unredirected edge in the list of callers
188 static struct cgraph_edge *
189 cgraph_mark_inline (struct cgraph_edge *edge)
191 struct cgraph_node *to = edge->caller;
192 struct cgraph_node *what = edge->callee;
193 struct cgraph_edge *e, *next;
196 /* Look for all calls, mark them inline and clone recursively
197 all inlined functions. */
198 for (e = what->callers; e; e = next)
200 next = e->next_caller;
201 if (e->caller == to && e->inline_failed)
203 cgraph_mark_inline_edge (e);
213 /* Estimate the growth caused by inlining NODE into all callees. */
216 cgraph_estimate_growth (struct cgraph_node *node)
219 struct cgraph_edge *e;
220 if (node->global.estimated_growth != INT_MIN)
221 return node->global.estimated_growth;
223 for (e = node->callers; e; e = e->next_caller)
224 if (e->inline_failed)
225 growth += (cgraph_estimate_size_after_inlining (1, e->caller, node)
226 - e->caller->global.insns);
228 /* ??? Wrong for self recursive functions or cases where we decide to not
229 inline for different reasons, but it is not big deal as in that case
230 we will keep the body around, but we will also avoid some inlining. */
231 if (!node->needed && !DECL_EXTERNAL (node->decl))
232 growth -= node->global.insns;
234 node->global.estimated_growth = growth;
238 /* Return false when inlining WHAT into TO is not good idea
239 as it would cause too large growth of function bodies. */
242 cgraph_check_inline_limits (struct cgraph_node *to, struct cgraph_node *what,
246 struct cgraph_edge *e;
250 if (to->global.inlined_to)
251 to = to->global.inlined_to;
253 for (e = to->callees; e; e = e->next_callee)
254 if (e->callee == what)
257 /* When inlining large function body called once into small function,
258 take the inlined function as base for limiting the growth. */
259 if (to->local.self_insns > what->local.self_insns)
260 limit = to->local.self_insns;
262 limit = what->local.self_insns;
264 limit += limit * PARAM_VALUE (PARAM_LARGE_FUNCTION_GROWTH) / 100;
266 newsize = cgraph_estimate_size_after_inlining (times, to, what);
267 if (newsize > PARAM_VALUE (PARAM_LARGE_FUNCTION_INSNS)
271 *reason = N_("--param large-function-growth limit reached");
277 /* Return true when function N is small enough to be inlined. */
280 cgraph_default_inline_p (struct cgraph_node *n, const char **reason)
282 if (!DECL_INLINE (n->decl))
285 *reason = N_("function not inlinable");
289 if (!DECL_SAVED_TREE (n->decl))
292 *reason = N_("function body not available");
296 if (DECL_DECLARED_INLINE_P (n->decl))
298 if (n->global.insns >= MAX_INLINE_INSNS_SINGLE)
301 *reason = N_("--param max-inline-insns-single limit reached");
307 if (n->global.insns >= MAX_INLINE_INSNS_AUTO)
310 *reason = N_("--param max-inline-insns-auto limit reached");
318 /* Return true when inlining WHAT would create recursive inlining.
319 We call recursive inlining all cases where same function appears more than
320 once in the single recursion nest path in the inline graph. */
323 cgraph_recursive_inlining_p (struct cgraph_node *to,
324 struct cgraph_node *what,
328 if (to->global.inlined_to)
329 recursive = what->decl == to->global.inlined_to->decl;
331 recursive = what->decl == to->decl;
332 /* Marking recursive function inline has sane semantic and thus we should
334 if (recursive && reason)
335 *reason = (what->local.disregard_inline_limits
336 ? N_("recursive inlining") : "");
340 /* Return true if the call can be hot. */
342 cgraph_maybe_hot_edge_p (struct cgraph_edge *edge)
344 if (profile_info && flag_branch_probabilities
346 <= profile_info->sum_max / PARAM_VALUE (HOT_BB_COUNT_FRACTION)))
351 /* A cost model driving the inlining heuristics in a way so the edges with
352 smallest badness are inlined first. After each inlining is performed
353 the costs of all caller edges of nodes affected are recomputed so the
354 metrics may accurately depend on values such as number of inlinable callers
355 of the function or function body size.
357 With profiling we use number of executions of each edge to drive the cost.
358 We also should distinguish hot and cold calls where the cold calls are
359 inlined into only when code size is overall improved.
363 cgraph_edge_badness (struct cgraph_edge *edge)
368 cgraph_estimate_size_after_inlining (1, edge->caller, edge->callee);
369 growth -= edge->caller->global.insns;
371 /* Always prefer inlining saving code size. */
373 return INT_MIN - growth;
374 return ((int)((double)edge->count * INT_MIN / max_count)) / growth;
378 int nest = MIN (edge->loop_nest, 8);
379 int badness = cgraph_estimate_growth (edge->callee) * 256;
381 /* Decrease badness if call is nested. */
387 /* Make recursive inlining happen always after other inlining is done. */
388 if (cgraph_recursive_inlining_p (edge->caller, edge->callee, NULL))
395 /* Recompute heap nodes for each of caller edge. */
398 update_caller_keys (fibheap_t heap, struct cgraph_node *node,
399 bitmap updated_nodes)
401 struct cgraph_edge *edge;
403 if (!node->local.inlinable || node->local.disregard_inline_limits
404 || node->global.inlined_to)
406 if (bitmap_bit_p (updated_nodes, node->uid))
408 bitmap_set_bit (updated_nodes, node->uid);
409 node->global.estimated_growth = INT_MIN;
411 for (edge = node->callers; edge; edge = edge->next_caller)
412 if (edge->inline_failed)
414 int badness = cgraph_edge_badness (edge);
417 fibnode_t n = edge->aux;
418 gcc_assert (n->data == edge);
419 if (n->key == badness)
422 /* fibheap_replace_key only increase the keys. */
423 if (fibheap_replace_key (heap, n, badness))
425 fibheap_delete_node (heap, edge->aux);
427 edge->aux = fibheap_insert (heap, badness, edge);
431 /* Recompute heap nodes for each of caller edges of each of callees. */
434 update_callee_keys (fibheap_t heap, struct cgraph_node *node,
435 bitmap updated_nodes)
437 struct cgraph_edge *e;
438 node->global.estimated_growth = INT_MIN;
440 for (e = node->callees; e; e = e->next_callee)
441 if (e->inline_failed)
442 update_caller_keys (heap, e->callee, updated_nodes);
443 else if (!e->inline_failed)
444 update_callee_keys (heap, e->callee, updated_nodes);
447 /* Enqueue all recursive calls from NODE into priority queue depending on
448 how likely we want to recursively inline the call. */
451 lookup_recursive_calls (struct cgraph_node *node, struct cgraph_node *where,
455 struct cgraph_edge *e;
456 for (e = where->callees; e; e = e->next_callee)
457 if (e->callee == node)
459 /* FIXME: Once counts and frequencies are available we should drive the
460 order by these. For now force the order to be simple queue since
461 we get order dependent on recursion depth for free by this. */
462 fibheap_insert (heap, priority++, e);
464 for (e = where->callees; e; e = e->next_callee)
465 if (!e->inline_failed)
466 lookup_recursive_calls (node, e->callee, heap);
469 /* Find callgraph nodes closing a circle in the graph. The
470 resulting hashtab can be used to avoid walking the circles.
471 Uses the cgraph nodes ->aux field which needs to be zero
472 before and will be zero after operation. */
475 cgraph_find_cycles (struct cgraph_node *node, htab_t cycles)
477 struct cgraph_edge *e;
482 slot = htab_find_slot (cycles, node, INSERT);
486 fprintf (dump_file, "Cycle contains %s\n", cgraph_node_name (node));
493 for (e = node->callees; e; e = e->next_callee)
494 cgraph_find_cycles (e->callee, cycles);
498 /* Leafify the cgraph node. We have to be careful in recursing
499 as to not run endlessly in circles of the callgraph.
500 We do so by using a hashtab of cycle entering nodes as generated
501 by cgraph_find_cycles. */
504 cgraph_flatten_node (struct cgraph_node *node, htab_t cycles)
506 struct cgraph_edge *e;
508 for (e = node->callees; e; e = e->next_callee)
510 /* Inline call, if possible, and recurse. Be sure we are not
511 entering callgraph circles here. */
513 && e->callee->local.inlinable
514 && !cgraph_recursive_inlining_p (node, e->callee,
516 && !htab_find (cycles, e->callee))
519 fprintf (dump_file, " inlining %s", cgraph_node_name (e->callee));
520 cgraph_mark_inline_edge (e);
521 cgraph_flatten_node (e->callee, cycles);
524 fprintf (dump_file, " !inlining %s", cgraph_node_name (e->callee));
528 /* Decide on recursive inlining: in the case function has recursive calls,
529 inline until body size reaches given argument. */
532 cgraph_decide_recursive_inlining (struct cgraph_node *node)
534 int limit = PARAM_VALUE (PARAM_MAX_INLINE_INSNS_RECURSIVE_AUTO);
535 int max_depth = PARAM_VALUE (PARAM_MAX_INLINE_RECURSIVE_DEPTH_AUTO);
537 struct cgraph_edge *e;
538 struct cgraph_node *master_clone;
542 if (DECL_DECLARED_INLINE_P (node->decl))
544 limit = PARAM_VALUE (PARAM_MAX_INLINE_INSNS_RECURSIVE);
545 max_depth = PARAM_VALUE (PARAM_MAX_INLINE_RECURSIVE_DEPTH);
548 /* Make sure that function is small enough to be considered for inlining. */
550 || cgraph_estimate_size_after_inlining (1, node, node) >= limit)
552 heap = fibheap_new ();
553 lookup_recursive_calls (node, node, heap);
554 if (fibheap_empty (heap))
556 fibheap_delete (heap);
562 " Performing recursive inlining on %s\n",
563 cgraph_node_name (node));
565 /* We need original clone to copy around. */
566 master_clone = cgraph_clone_node (node, 0, 1);
567 master_clone->needed = true;
568 for (e = master_clone->callees; e; e = e->next_callee)
569 if (!e->inline_failed)
570 cgraph_clone_inlined_nodes (e, true);
572 /* Do the inlining and update list of recursive call during process. */
573 while (!fibheap_empty (heap)
574 && cgraph_estimate_size_after_inlining (1, node, master_clone) <= limit)
576 struct cgraph_edge *curr = fibheap_extract_min (heap);
577 struct cgraph_node *node;
580 for (node = curr->caller;
581 node; node = node->global.inlined_to)
582 if (node->decl == curr->callee->decl)
584 if (depth > max_depth)
589 " Inlining call of depth %i\n", depth);
590 cgraph_redirect_edge_callee (curr, master_clone);
591 cgraph_mark_inline_edge (curr);
592 lookup_recursive_calls (node, curr->callee, heap);
596 fibheap_delete (heap);
599 "\n Inlined %i times, body grown from %i to %i insns\n", n,
600 master_clone->global.insns, node->global.insns);
602 /* Remove master clone we used for inlining. We rely that clones inlined
603 into master clone gets queued just before master clone so we don't
605 for (node = cgraph_nodes; node != master_clone;
607 if (node->global.inlined_to == master_clone)
608 cgraph_remove_node (node);
609 cgraph_remove_node (master_clone);
613 /* Set inline_failed for all callers of given function to REASON. */
616 cgraph_set_inline_failed (struct cgraph_node *node, const char *reason)
618 struct cgraph_edge *e;
621 fprintf (dump_file, "Inlining failed: %s\n", reason);
622 for (e = node->callers; e; e = e->next_caller)
623 if (e->inline_failed)
624 e->inline_failed = reason;
627 /* We use greedy algorithm for inlining of small functions:
628 All inline candidates are put into prioritized heap based on estimated
629 growth of the overall number of instructions and then update the estimates.
631 INLINED and INLINED_CALEES are just pointers to arrays large enough
632 to be passed to cgraph_inlined_into and cgraph_inlined_callees. */
635 cgraph_decide_inlining_of_small_functions (void)
637 struct cgraph_node *node;
638 struct cgraph_edge *edge;
639 const char *failed_reason;
640 fibheap_t heap = fibheap_new ();
641 bitmap updated_nodes = BITMAP_ALLOC (NULL);
644 fprintf (dump_file, "\nDeciding on smaller functions:\n");
646 /* Put all inline candidates into the heap. */
648 for (node = cgraph_nodes; node; node = node->next)
650 if (!node->local.inlinable || !node->callers
651 || node->local.disregard_inline_limits)
654 fprintf (dump_file, "Considering inline candidate %s.\n", cgraph_node_name (node));
656 node->global.estimated_growth = INT_MIN;
657 if (!cgraph_default_inline_p (node, &failed_reason))
659 cgraph_set_inline_failed (node, failed_reason);
663 for (edge = node->callers; edge; edge = edge->next_caller)
664 if (edge->inline_failed)
666 gcc_assert (!edge->aux);
667 edge->aux = fibheap_insert (heap, cgraph_edge_badness (edge), edge);
670 while (overall_insns <= max_insns && (edge = fibheap_extract_min (heap)))
672 int old_insns = overall_insns;
673 struct cgraph_node *where;
675 cgraph_estimate_size_after_inlining (1, edge->caller, edge->callee);
677 growth -= edge->caller->global.insns;
682 "\nConsidering %s with %i insns to be inlined into %s\n"
683 " Estimated growth after inlined into all callees is %+i insns.\n"
684 " Estimated badness is %i.\n",
685 cgraph_node_name (edge->callee),
686 edge->callee->global.insns,
687 cgraph_node_name (edge->caller),
688 cgraph_estimate_growth (edge->callee),
689 cgraph_edge_badness (edge));
691 fprintf (dump_file," Called "HOST_WIDEST_INT_PRINT_DEC"x\n", edge->count);
693 gcc_assert (edge->aux);
695 if (!edge->inline_failed)
698 /* When not having profile info ready we don't weight by any way the
699 position of call in procedure itself. This means if call of
700 function A from function B seems profitable to inline, the recursive
701 call of function A in inline copy of A in B will look profitable too
702 and we end up inlining until reaching maximal function growth. This
703 is not good idea so prohibit the recursive inlining.
705 ??? When the frequencies are taken into account we might not need this
709 where = edge->caller;
710 while (where->global.inlined_to)
712 if (where->decl == edge->callee->decl)
714 where = where->callers->caller;
716 if (where->global.inlined_to)
719 = (edge->callee->local.disregard_inline_limits ? N_("recursive inlining") : "");
721 fprintf (dump_file, " inline_failed:Recursive inlining performed only for function itself.\n");
726 if (!cgraph_maybe_hot_edge_p (edge) && growth > 0)
728 if (!cgraph_recursive_inlining_p (edge->caller, edge->callee,
729 &edge->inline_failed))
731 edge->inline_failed =
732 N_("call is unlikely");
734 fprintf (dump_file, " inline_failed:%s.\n", edge->inline_failed);
738 if (!cgraph_default_inline_p (edge->callee, &edge->inline_failed))
740 if (!cgraph_recursive_inlining_p (edge->caller, edge->callee,
741 &edge->inline_failed))
744 fprintf (dump_file, " inline_failed:%s.\n", edge->inline_failed);
748 if (cgraph_recursive_inlining_p (edge->caller, edge->callee,
749 &edge->inline_failed))
751 where = edge->caller;
752 if (where->global.inlined_to)
753 where = where->global.inlined_to;
754 if (!cgraph_decide_recursive_inlining (where))
756 update_callee_keys (heap, where, updated_nodes);
760 struct cgraph_node *callee;
761 if (!cgraph_check_inline_limits (edge->caller, edge->callee,
762 &edge->inline_failed))
765 fprintf (dump_file, " Not inlining into %s:%s.\n",
766 cgraph_node_name (edge->caller), edge->inline_failed);
769 callee = edge->callee;
770 cgraph_mark_inline_edge (edge);
771 update_callee_keys (heap, callee, updated_nodes);
773 where = edge->caller;
774 if (where->global.inlined_to)
775 where = where->global.inlined_to;
777 /* Our profitability metric can depend on local properties
778 such as number of inlinable calls and size of the function body.
779 After inlining these properties might change for the function we
780 inlined into (since it's body size changed) and for the functions
781 called by function we inlined (since number of it inlinable callers
783 update_caller_keys (heap, where, updated_nodes);
784 bitmap_clear (updated_nodes);
788 " Inlined into %s which now has %i insns.\n",
789 cgraph_node_name (edge->caller),
790 edge->caller->global.insns);
793 " Inlined for a net change of %+i insns.\n",
794 overall_insns - old_insns);
796 while ((edge = fibheap_extract_min (heap)) != NULL)
798 gcc_assert (edge->aux);
800 if (!edge->callee->local.disregard_inline_limits && edge->inline_failed
801 && !cgraph_recursive_inlining_p (edge->caller, edge->callee,
802 &edge->inline_failed))
803 edge->inline_failed = N_("--param inline-unit-growth limit reached");
805 fibheap_delete (heap);
806 BITMAP_FREE (updated_nodes);
809 /* Decide on the inlining. We do so in the topological order to avoid
810 expenses on updating data structures. */
813 cgraph_decide_inlining (void)
815 struct cgraph_node *node;
817 struct cgraph_node **order =
818 xcalloc (cgraph_n_nodes, sizeof (struct cgraph_node *));
822 timevar_push (TV_INLINE_HEURISTICS);
824 for (node = cgraph_nodes; node; node = node->next)
826 struct cgraph_edge *e;
827 initial_insns += node->local.self_insns;
828 for (e = node->callees; e; e = e->next_callee)
829 if (max_count < e->count)
830 max_count = e->count;
832 overall_insns = initial_insns;
833 gcc_assert (!max_count || (profile_info && flag_branch_probabilities));
835 max_insns = ((HOST_WIDEST_INT) overall_insns
836 * (100 + PARAM_VALUE (PARAM_INLINE_UNIT_GROWTH)) / 100);
838 nnodes = cgraph_postorder (order);
842 "\nDeciding on inlining. Starting with %i insns.\n",
845 for (node = cgraph_nodes; node; node = node->next)
849 fprintf (dump_file, "\nInlining always_inline functions:\n");
851 /* In the first pass mark all always_inline edges. Do this with a priority
852 so none of our later choices will make this impossible. */
853 for (i = nnodes - 1; i >= 0; i--)
855 struct cgraph_edge *e, *next;
859 /* Handle nodes to be flattened, but don't update overall unit size. */
860 if (lookup_attribute ("flatten", DECL_ATTRIBUTES (node->decl)) != NULL)
862 int old_overall_insns = overall_insns;
866 "Leafifying %s\n", cgraph_node_name (node));
867 cycles = htab_create (7, htab_hash_pointer, htab_eq_pointer, NULL);
868 cgraph_find_cycles (node, cycles);
869 cgraph_flatten_node (node, cycles);
870 htab_delete (cycles);
871 overall_insns = old_overall_insns;
872 /* We don't need to consider always_inline functions inside the flattened
877 if (!node->local.disregard_inline_limits)
881 "\nConsidering %s %i insns (always inline)\n",
882 cgraph_node_name (node), node->global.insns);
883 old_insns = overall_insns;
884 for (e = node->callers; e; e = next)
886 next = e->next_caller;
887 if (!e->inline_failed)
889 if (cgraph_recursive_inlining_p (e->caller, e->callee,
892 cgraph_mark_inline_edge (e);
895 " Inlined into %s which now has %i insns.\n",
896 cgraph_node_name (e->caller),
897 e->caller->global.insns);
901 " Inlined for a net change of %+i insns.\n",
902 overall_insns - old_insns);
905 if (!flag_really_no_inline)
907 cgraph_decide_inlining_of_small_functions ();
910 fprintf (dump_file, "\nDeciding on functions called once:\n");
912 /* And finally decide what functions are called once. */
914 for (i = nnodes - 1; i >= 0; i--)
918 if (node->callers && !node->callers->next_caller && !node->needed
919 && node->local.inlinable && node->callers->inline_failed
920 && !DECL_EXTERNAL (node->decl) && !DECL_COMDAT (node->decl))
923 struct cgraph_node *node1;
925 /* Verify that we won't duplicate the caller. */
926 for (node1 = node->callers->caller;
927 node1->callers && !node1->callers->inline_failed
928 && ok; node1 = node1->callers->caller)
929 if (node1->callers->next_caller || node1->needed)
935 "\nConsidering %s %i insns.\n"
936 " Called once from %s %i insns.\n",
937 cgraph_node_name (node), node->global.insns,
938 cgraph_node_name (node->callers->caller),
939 node->callers->caller->global.insns);
941 old_insns = overall_insns;
943 if (cgraph_check_inline_limits (node->callers->caller, node,
946 cgraph_mark_inline (node->callers);
949 " Inlined into %s which now has %i insns"
950 " for a net change of %+i insns.\n",
951 cgraph_node_name (node->callers->caller),
952 node->callers->caller->global.insns,
953 overall_insns - old_insns);
959 " Inline limit reached, not inlined.\n");
968 "\nInlined %i calls, eliminated %i functions, "
969 "%i insns turned to %i insns.\n\n",
970 ncalls_inlined, nfunctions_inlined, initial_insns,
973 timevar_pop (TV_INLINE_HEURISTICS);
976 /* Decide on the inlining. We do so in the topological order to avoid
977 expenses on updating data structures. */
980 cgraph_decide_inlining_incrementally (struct cgraph_node *node, bool early)
982 struct cgraph_edge *e;
983 bool inlined = false;
984 const char *failed_reason;
986 /* First of all look for always inline functions. */
987 for (e = node->callees; e; e = e->next_callee)
988 if (e->callee->local.disregard_inline_limits
990 && !cgraph_recursive_inlining_p (node, e->callee, &e->inline_failed)
991 /* ??? It is possible that renaming variable removed the function body
992 in duplicate_decls. See gcc.c-torture/compile/20011119-2.c */
993 && DECL_SAVED_TREE (e->callee->decl))
995 if (dump_file && early)
996 fprintf (dump_file, " Early inlining %s into %s\n",
997 cgraph_node_name (e->callee), cgraph_node_name (node));
998 cgraph_mark_inline (e);
1002 /* Now do the automatic inlining. */
1003 if (!flag_really_no_inline)
1004 for (e = node->callees; e; e = e->next_callee)
1005 if (e->callee->local.inlinable
1007 && !e->callee->local.disregard_inline_limits
1008 && !cgraph_recursive_inlining_p (node, e->callee, &e->inline_failed)
1010 || (cgraph_estimate_size_after_inlining (1, e->caller, node)
1011 <= e->caller->global.insns))
1012 && cgraph_check_inline_limits (node, e->callee, &e->inline_failed)
1013 && DECL_SAVED_TREE (e->callee->decl))
1015 if (cgraph_default_inline_p (e->callee, &failed_reason))
1017 if (dump_file && early)
1018 fprintf (dump_file, " Early inlining %s into %s\n",
1019 cgraph_node_name (e->callee), cgraph_node_name (node));
1020 cgraph_mark_inline (e);
1024 e->inline_failed = failed_reason;
1026 if (early && inlined)
1028 push_cfun (DECL_STRUCT_FUNCTION (node->decl));
1029 tree_register_cfg_hooks ();
1030 current_function_decl = node->decl;
1031 optimize_inline_calls (current_function_decl);
1032 node->local.self_insns = node->global.insns;
1033 current_function_decl = NULL;
1040 /* When inlining shall be performed. */
1042 cgraph_gate_inlining (void)
1044 return flag_inline_trees;
1047 struct tree_opt_pass pass_ipa_inline =
1049 "inline", /* name */
1050 cgraph_gate_inlining, /* gate */
1051 cgraph_decide_inlining, /* execute */
1054 0, /* static_pass_number */
1055 TV_INTEGRATION, /* tv_id */
1056 0, /* properties_required */
1057 PROP_cfg, /* properties_provided */
1058 0, /* properties_destroyed */
1059 0, /* todo_flags_start */
1060 TODO_dump_cgraph | TODO_dump_func, /* todo_flags_finish */
1064 /* Do inlining of small functions. Doing so early helps profiling and other
1065 passes to be somewhat more effective and avoids some code duplication in
1066 later real inlining pass for testcases with very many function calls. */
1068 cgraph_early_inlining (void)
1070 struct cgraph_node *node;
1072 struct cgraph_node **order =
1073 xcalloc (cgraph_n_nodes, sizeof (struct cgraph_node *));
1076 if (sorrycount || errorcount)
1078 #ifdef ENABLE_CHECKING
1079 for (node = cgraph_nodes; node; node = node->next)
1080 gcc_assert (!node->aux);
1083 nnodes = cgraph_postorder (order);
1084 for (i = nnodes - 1; i >= 0; i--)
1087 if (node->analyzed && node->local.inlinable
1088 && (node->needed || node->reachable)
1090 cgraph_decide_inlining_incrementally (node, true);
1092 cgraph_remove_unreachable_nodes (true, dump_file);
1093 #ifdef ENABLE_CHECKING
1094 for (node = cgraph_nodes; node; node = node->next)
1095 gcc_assert (!node->global.inlined_to);
1100 /* When inlining shall be performed. */
1102 cgraph_gate_early_inlining (void)
1104 return flag_inline_trees && flag_early_inlining;
1107 struct tree_opt_pass pass_early_ipa_inline =
1109 "einline", /* name */
1110 cgraph_gate_early_inlining, /* gate */
1111 cgraph_early_inlining, /* execute */
1114 0, /* static_pass_number */
1115 TV_INTEGRATION, /* tv_id */
1116 0, /* properties_required */
1117 PROP_cfg, /* properties_provided */
1118 0, /* properties_destroyed */
1119 0, /* todo_flags_start */
1120 TODO_dump_cgraph | TODO_dump_func, /* todo_flags_finish */