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
, bool update_original
)
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
, update_original
);
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
, update_original
);
149 /* Mark edge E as inlined and update callgraph accordingly.
150 UPDATE_ORIGINAL specify whether profile of original function should be
154 cgraph_mark_inline_edge (struct cgraph_edge
*e
, bool update_original
)
156 int old_insns
= 0, new_insns
= 0;
157 struct cgraph_node
*to
= NULL
, *what
;
159 if (e
->callee
->inline_decl
)
160 cgraph_redirect_edge_callee (e
, cgraph_node (e
->callee
->inline_decl
));
162 gcc_assert (e
->inline_failed
);
163 e
->inline_failed
= NULL
;
165 if (!e
->callee
->global
.inlined
&& flag_unit_at_a_time
)
166 DECL_POSSIBLY_INLINED (e
->callee
->decl
) = true;
167 e
->callee
->global
.inlined
= true;
169 cgraph_clone_inlined_nodes (e
, true, update_original
);
173 /* Now update size of caller and all functions caller is inlined into. */
174 for (;e
&& !e
->inline_failed
; e
= e
->caller
->callers
)
176 old_insns
= e
->caller
->global
.insns
;
177 new_insns
= cgraph_estimate_size_after_inlining (1, e
->caller
,
179 gcc_assert (new_insns
>= 0);
181 to
->global
.insns
= new_insns
;
183 gcc_assert (what
->global
.inlined_to
== to
);
184 if (new_insns
> old_insns
)
185 overall_insns
+= new_insns
- old_insns
;
189 /* Mark all calls of EDGE->CALLEE inlined into EDGE->CALLER.
190 Return following unredirected edge in the list of callers
193 static struct cgraph_edge
*
194 cgraph_mark_inline (struct cgraph_edge
*edge
)
196 struct cgraph_node
*to
= edge
->caller
;
197 struct cgraph_node
*what
= edge
->callee
;
198 struct cgraph_edge
*e
, *next
;
201 /* Look for all calls, mark them inline and clone recursively
202 all inlined functions. */
203 for (e
= what
->callers
; e
; e
= next
)
205 next
= e
->next_caller
;
206 if (e
->caller
== to
&& e
->inline_failed
)
208 cgraph_mark_inline_edge (e
, true);
218 /* Estimate the growth caused by inlining NODE into all callees. */
221 cgraph_estimate_growth (struct cgraph_node
*node
)
224 struct cgraph_edge
*e
;
225 if (node
->global
.estimated_growth
!= INT_MIN
)
226 return node
->global
.estimated_growth
;
228 for (e
= node
->callers
; e
; e
= e
->next_caller
)
229 if (e
->inline_failed
)
230 growth
+= (cgraph_estimate_size_after_inlining (1, e
->caller
, node
)
231 - e
->caller
->global
.insns
);
233 /* ??? Wrong for self recursive functions or cases where we decide to not
234 inline for different reasons, but it is not big deal as in that case
235 we will keep the body around, but we will also avoid some inlining. */
236 if (!node
->needed
&& !DECL_EXTERNAL (node
->decl
))
237 growth
-= node
->global
.insns
;
239 node
->global
.estimated_growth
= growth
;
243 /* Return false when inlining WHAT into TO is not good idea
244 as it would cause too large growth of function bodies. */
247 cgraph_check_inline_limits (struct cgraph_node
*to
, struct cgraph_node
*what
,
251 struct cgraph_edge
*e
;
255 if (to
->global
.inlined_to
)
256 to
= to
->global
.inlined_to
;
258 for (e
= to
->callees
; e
; e
= e
->next_callee
)
259 if (e
->callee
== what
)
262 /* When inlining large function body called once into small function,
263 take the inlined function as base for limiting the growth. */
264 if (to
->local
.self_insns
> what
->local
.self_insns
)
265 limit
= to
->local
.self_insns
;
267 limit
= what
->local
.self_insns
;
269 limit
+= limit
* PARAM_VALUE (PARAM_LARGE_FUNCTION_GROWTH
) / 100;
271 newsize
= cgraph_estimate_size_after_inlining (times
, to
, what
);
272 if (newsize
> PARAM_VALUE (PARAM_LARGE_FUNCTION_INSNS
)
276 *reason
= N_("--param large-function-growth limit reached");
282 /* Return true when function N is small enough to be inlined. */
285 cgraph_default_inline_p (struct cgraph_node
*n
, const char **reason
)
290 decl
= n
->inline_decl
;
291 if (!DECL_INLINE (decl
))
294 *reason
= N_("function not inlinable");
298 if (!DECL_STRUCT_FUNCTION (decl
)->cfg
)
301 *reason
= N_("function body not available");
305 if (DECL_DECLARED_INLINE_P (decl
))
307 if (n
->global
.insns
>= MAX_INLINE_INSNS_SINGLE
)
310 *reason
= N_("--param max-inline-insns-single limit reached");
316 if (n
->global
.insns
>= MAX_INLINE_INSNS_AUTO
)
319 *reason
= N_("--param max-inline-insns-auto limit reached");
327 /* Return true when inlining WHAT would create recursive inlining.
328 We call recursive inlining all cases where same function appears more than
329 once in the single recursion nest path in the inline graph. */
332 cgraph_recursive_inlining_p (struct cgraph_node
*to
,
333 struct cgraph_node
*what
,
337 if (to
->global
.inlined_to
)
338 recursive
= what
->decl
== to
->global
.inlined_to
->decl
;
340 recursive
= what
->decl
== to
->decl
;
341 /* Marking recursive function inline has sane semantic and thus we should
343 if (recursive
&& reason
)
344 *reason
= (what
->local
.disregard_inline_limits
345 ? N_("recursive inlining") : "");
349 /* Return true if the call can be hot. */
351 cgraph_maybe_hot_edge_p (struct cgraph_edge
*edge
)
353 if (profile_info
&& flag_branch_probabilities
355 <= profile_info
->sum_max
/ PARAM_VALUE (HOT_BB_COUNT_FRACTION
)))
360 /* A cost model driving the inlining heuristics in a way so the edges with
361 smallest badness are inlined first. After each inlining is performed
362 the costs of all caller edges of nodes affected are recomputed so the
363 metrics may accurately depend on values such as number of inlinable callers
364 of the function or function body size.
366 With profiling we use number of executions of each edge to drive the cost.
367 We also should distinguish hot and cold calls where the cold calls are
368 inlined into only when code size is overall improved.
372 cgraph_edge_badness (struct cgraph_edge
*edge
)
377 cgraph_estimate_size_after_inlining (1, edge
->caller
, edge
->callee
);
378 growth
-= edge
->caller
->global
.insns
;
380 /* Always prefer inlining saving code size. */
382 return INT_MIN
- growth
;
383 return ((int)((double)edge
->count
* INT_MIN
/ max_count
)) / growth
;
387 int nest
= MIN (edge
->loop_nest
, 8);
388 int badness
= cgraph_estimate_growth (edge
->callee
) * 256;
390 /* Decrease badness if call is nested. */
396 /* Make recursive inlining happen always after other inlining is done. */
397 if (cgraph_recursive_inlining_p (edge
->caller
, edge
->callee
, NULL
))
404 /* Recompute heap nodes for each of caller edge. */
407 update_caller_keys (fibheap_t heap
, struct cgraph_node
*node
,
408 bitmap updated_nodes
)
410 struct cgraph_edge
*edge
;
412 if (!node
->local
.inlinable
|| node
->local
.disregard_inline_limits
413 || node
->global
.inlined_to
)
415 if (bitmap_bit_p (updated_nodes
, node
->uid
))
417 bitmap_set_bit (updated_nodes
, node
->uid
);
418 node
->global
.estimated_growth
= INT_MIN
;
420 for (edge
= node
->callers
; edge
; edge
= edge
->next_caller
)
421 if (edge
->inline_failed
)
423 int badness
= cgraph_edge_badness (edge
);
426 fibnode_t n
= edge
->aux
;
427 gcc_assert (n
->data
== edge
);
428 if (n
->key
== badness
)
431 /* fibheap_replace_key only increase the keys. */
432 if (fibheap_replace_key (heap
, n
, badness
))
434 fibheap_delete_node (heap
, edge
->aux
);
436 edge
->aux
= fibheap_insert (heap
, badness
, edge
);
440 /* Recompute heap nodes for each of caller edges of each of callees. */
443 update_callee_keys (fibheap_t heap
, struct cgraph_node
*node
,
444 bitmap updated_nodes
)
446 struct cgraph_edge
*e
;
447 node
->global
.estimated_growth
= INT_MIN
;
449 for (e
= node
->callees
; e
; e
= e
->next_callee
)
450 if (e
->inline_failed
)
451 update_caller_keys (heap
, e
->callee
, updated_nodes
);
452 else if (!e
->inline_failed
)
453 update_callee_keys (heap
, e
->callee
, updated_nodes
);
456 /* Enqueue all recursive calls from NODE into priority queue depending on
457 how likely we want to recursively inline the call. */
460 lookup_recursive_calls (struct cgraph_node
*node
, struct cgraph_node
*where
,
464 struct cgraph_edge
*e
;
465 for (e
= where
->callees
; e
; e
= e
->next_callee
)
466 if (e
->callee
== node
)
468 /* When profile feedback is available, prioritize by expected number
469 of calls. Without profile feedback we maintain simple queue
470 to order candidates via recursive depths. */
471 fibheap_insert (heap
,
472 !max_count
? priority
++
473 : -(e
->count
/ ((max_count
+ (1<<24) - 1) / (1<<24))),
476 for (e
= where
->callees
; e
; e
= e
->next_callee
)
477 if (!e
->inline_failed
)
478 lookup_recursive_calls (node
, e
->callee
, heap
);
481 /* Find callgraph nodes closing a circle in the graph. The
482 resulting hashtab can be used to avoid walking the circles.
483 Uses the cgraph nodes ->aux field which needs to be zero
484 before and will be zero after operation. */
487 cgraph_find_cycles (struct cgraph_node
*node
, htab_t cycles
)
489 struct cgraph_edge
*e
;
494 slot
= htab_find_slot (cycles
, node
, INSERT
);
498 fprintf (dump_file
, "Cycle contains %s\n", cgraph_node_name (node
));
505 for (e
= node
->callees
; e
; e
= e
->next_callee
)
506 cgraph_find_cycles (e
->callee
, cycles
);
512 cgraph_apply_inline_plan (void)
514 struct cgraph_node
*node
;
515 struct cgraph_node
**order
=
516 xcalloc (cgraph_n_nodes
, sizeof (struct cgraph_node
*));
517 int order_pos
= 0, new_order_pos
= 0;
520 timevar_push (TV_INTEGRATION
);
521 order_pos
= cgraph_postorder (order
);
522 gcc_assert (order_pos
== cgraph_n_nodes
);
524 /* Garbage collector may remove inline clones we eliminate during
525 optimization. So we must be sure to not reference them. */
526 for (i
= 0; i
< order_pos
; i
++)
527 if (!order
[i
]->global
.inlined_to
)
528 order
[new_order_pos
++] = order
[i
];
530 /* Initialize the default bitmap obstack. */
531 bitmap_obstack_initialize (NULL
);
534 for (i
= 0; i
< new_order_pos
; i
++)
536 struct cgraph_edge
*e
;
539 for (e
= node
->callees
; e
; e
= e
->next_callee
)
540 if (!e
->inline_failed
|| warn_inline
)
544 if (cgraph_preserve_function_body_p (node
->decl
, true))
545 save_inline_function_body (node
);
546 push_cfun (DECL_STRUCT_FUNCTION (node
->decl
));
547 tree_register_cfg_hooks ();
548 current_function_decl
= node
->decl
;
549 optimize_inline_calls (node
->decl
, false);
550 free_dominance_info (CDI_DOMINATORS
);
551 free_dominance_info (CDI_POST_DOMINATORS
);
552 node
->local
.self_insns
= node
->global
.insns
;
558 timevar_pop (TV_INTEGRATION
);
561 /* Leafify the cgraph node. We have to be careful in recursing
562 as to not run endlessly in circles of the callgraph.
563 We do so by using a hashtab of cycle entering nodes as generated
564 by cgraph_find_cycles. */
567 cgraph_flatten_node (struct cgraph_node
*node
, htab_t cycles
)
569 struct cgraph_edge
*e
;
571 for (e
= node
->callees
; e
; e
= e
->next_callee
)
573 /* Inline call, if possible, and recurse. Be sure we are not
574 entering callgraph circles here. */
576 && e
->callee
->local
.inlinable
577 && !cgraph_recursive_inlining_p (node
, e
->callee
,
579 && !htab_find (cycles
, e
->callee
))
582 fprintf (dump_file
, " inlining %s", cgraph_node_name (e
->callee
));
583 cgraph_mark_inline_edge (e
, true);
584 cgraph_flatten_node (e
->callee
, cycles
);
587 fprintf (dump_file
, " !inlining %s", cgraph_node_name (e
->callee
));
591 /* Decide on recursive inlining: in the case function has recursive calls,
592 inline until body size reaches given argument. */
595 cgraph_decide_recursive_inlining (struct cgraph_node
*node
)
597 int limit
= PARAM_VALUE (PARAM_MAX_INLINE_INSNS_RECURSIVE_AUTO
);
598 int max_depth
= PARAM_VALUE (PARAM_MAX_INLINE_RECURSIVE_DEPTH_AUTO
);
599 int probability
= PARAM_VALUE (PARAM_MIN_INLINE_RECURSIVE_PROBABILITY
);
601 struct cgraph_edge
*e
;
602 struct cgraph_node
*master_clone
;
606 if (DECL_DECLARED_INLINE_P (node
->decl
))
608 limit
= PARAM_VALUE (PARAM_MAX_INLINE_INSNS_RECURSIVE
);
609 max_depth
= PARAM_VALUE (PARAM_MAX_INLINE_RECURSIVE_DEPTH
);
612 /* Make sure that function is small enough to be considered for inlining. */
614 || cgraph_estimate_size_after_inlining (1, node
, node
) >= limit
)
616 heap
= fibheap_new ();
617 lookup_recursive_calls (node
, node
, heap
);
618 if (fibheap_empty (heap
))
620 fibheap_delete (heap
);
626 " Performing recursive inlining on %s\n",
627 cgraph_node_name (node
));
629 /* We need original clone to copy around. */
630 master_clone
= cgraph_clone_node (node
, node
->count
, 1, false);
631 master_clone
->needed
= true;
632 for (e
= master_clone
->callees
; e
; e
= e
->next_callee
)
633 if (!e
->inline_failed
)
634 cgraph_clone_inlined_nodes (e
, true, false);
636 /* Do the inlining and update list of recursive call during process. */
637 while (!fibheap_empty (heap
)
638 && (cgraph_estimate_size_after_inlining (1, node
, master_clone
)
641 struct cgraph_edge
*curr
= fibheap_extract_min (heap
);
642 struct cgraph_node
*cnode
;
645 for (cnode
= curr
->caller
;
646 cnode
->global
.inlined_to
; cnode
= cnode
->callers
->caller
)
647 if (node
->decl
== curr
->callee
->decl
)
649 if (depth
> max_depth
)
653 " maxmal depth reached\n");
659 if (!cgraph_maybe_hot_edge_p (curr
))
662 fprintf (dump_file
, " Not inlining cold call\n");
665 if (curr
->count
* 100 / node
->count
< probability
)
669 " Probability of edge is too small\n");
677 " Inlining call of depth %i", depth
);
680 fprintf (dump_file
, " called approx. %.2f times per call",
681 (double)curr
->count
/ node
->count
);
683 fprintf (dump_file
, "\n");
685 cgraph_redirect_edge_callee (curr
, master_clone
);
686 cgraph_mark_inline_edge (curr
, false);
687 lookup_recursive_calls (node
, curr
->callee
, heap
);
690 if (!fibheap_empty (heap
) && dump_file
)
691 fprintf (dump_file
, " Recursive inlining growth limit met.\n");
693 fibheap_delete (heap
);
696 "\n Inlined %i times, body grown from %i to %i insns\n", n
,
697 master_clone
->global
.insns
, node
->global
.insns
);
699 /* Remove master clone we used for inlining. We rely that clones inlined
700 into master clone gets queued just before master clone so we don't
702 for (node
= cgraph_nodes
; node
!= master_clone
;
704 if (node
->global
.inlined_to
== master_clone
)
705 cgraph_remove_node (node
);
706 cgraph_remove_node (master_clone
);
707 /* FIXME: Recursive inlining actually reduces number of calls of the
708 function. At this place we should probably walk the function and
709 inline clones and compensate the counts accordingly. This probably
710 doesn't matter much in practice. */
714 /* Set inline_failed for all callers of given function to REASON. */
717 cgraph_set_inline_failed (struct cgraph_node
*node
, const char *reason
)
719 struct cgraph_edge
*e
;
722 fprintf (dump_file
, "Inlining failed: %s\n", reason
);
723 for (e
= node
->callers
; e
; e
= e
->next_caller
)
724 if (e
->inline_failed
)
725 e
->inline_failed
= reason
;
728 /* We use greedy algorithm for inlining of small functions:
729 All inline candidates are put into prioritized heap based on estimated
730 growth of the overall number of instructions and then update the estimates.
732 INLINED and INLINED_CALEES are just pointers to arrays large enough
733 to be passed to cgraph_inlined_into and cgraph_inlined_callees. */
736 cgraph_decide_inlining_of_small_functions (void)
738 struct cgraph_node
*node
;
739 struct cgraph_edge
*edge
;
740 const char *failed_reason
;
741 fibheap_t heap
= fibheap_new ();
742 bitmap updated_nodes
= BITMAP_ALLOC (NULL
);
745 fprintf (dump_file
, "\nDeciding on smaller functions:\n");
747 /* Put all inline candidates into the heap. */
749 for (node
= cgraph_nodes
; node
; node
= node
->next
)
751 if (!node
->local
.inlinable
|| !node
->callers
752 || node
->local
.disregard_inline_limits
)
755 fprintf (dump_file
, "Considering inline candidate %s.\n", cgraph_node_name (node
));
757 node
->global
.estimated_growth
= INT_MIN
;
758 if (!cgraph_default_inline_p (node
, &failed_reason
))
760 cgraph_set_inline_failed (node
, failed_reason
);
764 for (edge
= node
->callers
; edge
; edge
= edge
->next_caller
)
765 if (edge
->inline_failed
)
767 gcc_assert (!edge
->aux
);
768 edge
->aux
= fibheap_insert (heap
, cgraph_edge_badness (edge
), edge
);
771 while (overall_insns
<= max_insns
&& (edge
= fibheap_extract_min (heap
)))
773 int old_insns
= overall_insns
;
774 struct cgraph_node
*where
;
776 cgraph_estimate_size_after_inlining (1, edge
->caller
, edge
->callee
);
778 growth
-= edge
->caller
->global
.insns
;
783 "\nConsidering %s with %i insns\n",
784 cgraph_node_name (edge
->callee
),
785 edge
->callee
->global
.insns
);
787 " to be inlined into %s\n"
788 " Estimated growth after inlined into all callees is %+i insns.\n"
789 " Estimated badness is %i.\n",
790 cgraph_node_name (edge
->caller
),
791 cgraph_estimate_growth (edge
->callee
),
792 cgraph_edge_badness (edge
));
794 fprintf (dump_file
," Called "HOST_WIDEST_INT_PRINT_DEC
"x\n", edge
->count
);
796 gcc_assert (edge
->aux
);
798 if (!edge
->inline_failed
)
801 /* When not having profile info ready we don't weight by any way the
802 position of call in procedure itself. This means if call of
803 function A from function B seems profitable to inline, the recursive
804 call of function A in inline copy of A in B will look profitable too
805 and we end up inlining until reaching maximal function growth. This
806 is not good idea so prohibit the recursive inlining.
808 ??? When the frequencies are taken into account we might not need this
812 where
= edge
->caller
;
813 while (where
->global
.inlined_to
)
815 if (where
->decl
== edge
->callee
->decl
)
817 where
= where
->callers
->caller
;
819 if (where
->global
.inlined_to
)
822 = (edge
->callee
->local
.disregard_inline_limits
? N_("recursive inlining") : "");
824 fprintf (dump_file
, " inline_failed:Recursive inlining performed only for function itself.\n");
829 if (!cgraph_maybe_hot_edge_p (edge
) && growth
> 0)
831 if (!cgraph_recursive_inlining_p (edge
->caller
, edge
->callee
,
832 &edge
->inline_failed
))
834 edge
->inline_failed
=
835 N_("call is unlikely");
837 fprintf (dump_file
, " inline_failed:%s.\n", edge
->inline_failed
);
841 if (!cgraph_default_inline_p (edge
->callee
, &edge
->inline_failed
))
843 if (!cgraph_recursive_inlining_p (edge
->caller
, edge
->callee
,
844 &edge
->inline_failed
))
847 fprintf (dump_file
, " inline_failed:%s.\n", edge
->inline_failed
);
851 if (cgraph_recursive_inlining_p (edge
->caller
, edge
->callee
,
852 &edge
->inline_failed
))
854 where
= edge
->caller
;
855 if (where
->global
.inlined_to
)
856 where
= where
->global
.inlined_to
;
857 if (!cgraph_decide_recursive_inlining (where
))
859 update_callee_keys (heap
, where
, updated_nodes
);
863 struct cgraph_node
*callee
;
864 if (!cgraph_check_inline_limits (edge
->caller
, edge
->callee
,
865 &edge
->inline_failed
))
868 fprintf (dump_file
, " Not inlining into %s:%s.\n",
869 cgraph_node_name (edge
->caller
), edge
->inline_failed
);
872 callee
= edge
->callee
;
873 cgraph_mark_inline_edge (edge
, true);
874 update_callee_keys (heap
, callee
, updated_nodes
);
876 where
= edge
->caller
;
877 if (where
->global
.inlined_to
)
878 where
= where
->global
.inlined_to
;
880 /* Our profitability metric can depend on local properties
881 such as number of inlinable calls and size of the function body.
882 After inlining these properties might change for the function we
883 inlined into (since it's body size changed) and for the functions
884 called by function we inlined (since number of it inlinable callers
886 update_caller_keys (heap
, where
, updated_nodes
);
887 bitmap_clear (updated_nodes
);
892 " Inlined into %s which now has %i insns,"
893 "net change of %+i insns.\n",
894 cgraph_node_name (edge
->caller
),
895 edge
->caller
->global
.insns
,
896 overall_insns
- old_insns
);
899 while ((edge
= fibheap_extract_min (heap
)) != NULL
)
901 gcc_assert (edge
->aux
);
903 if (!edge
->callee
->local
.disregard_inline_limits
&& edge
->inline_failed
904 && !cgraph_recursive_inlining_p (edge
->caller
, edge
->callee
,
905 &edge
->inline_failed
))
906 edge
->inline_failed
= N_("--param inline-unit-growth limit reached");
908 fibheap_delete (heap
);
909 BITMAP_FREE (updated_nodes
);
912 /* Decide on the inlining. We do so in the topological order to avoid
913 expenses on updating data structures. */
916 cgraph_decide_inlining (void)
918 struct cgraph_node
*node
;
920 struct cgraph_node
**order
=
921 xcalloc (cgraph_n_nodes
, sizeof (struct cgraph_node
*));
925 timevar_push (TV_INLINE_HEURISTICS
);
927 for (node
= cgraph_nodes
; node
; node
= node
->next
)
929 struct cgraph_edge
*e
;
930 initial_insns
+= node
->local
.self_insns
;
931 for (e
= node
->callees
; e
; e
= e
->next_callee
)
932 if (max_count
< e
->count
)
933 max_count
= e
->count
;
935 overall_insns
= initial_insns
;
936 gcc_assert (!max_count
|| (profile_info
&& flag_branch_probabilities
));
938 max_insns
= overall_insns
;
939 if (max_insns
< PARAM_VALUE (PARAM_LARGE_UNIT_INSNS
))
940 max_insns
= PARAM_VALUE (PARAM_LARGE_UNIT_INSNS
);
942 max_insns
= ((HOST_WIDEST_INT
) max_insns
943 * (100 + PARAM_VALUE (PARAM_INLINE_UNIT_GROWTH
)) / 100);
945 nnodes
= cgraph_postorder (order
);
949 "\nDeciding on inlining. Starting with %i insns.\n",
952 for (node
= cgraph_nodes
; node
; node
= node
->next
)
956 fprintf (dump_file
, "\nInlining always_inline functions:\n");
958 /* In the first pass mark all always_inline edges. Do this with a priority
959 so none of our later choices will make this impossible. */
960 for (i
= nnodes
- 1; i
>= 0; i
--)
962 struct cgraph_edge
*e
, *next
;
966 /* Handle nodes to be flattened, but don't update overall unit size. */
967 if (lookup_attribute ("flatten", DECL_ATTRIBUTES (node
->decl
)) != NULL
)
969 int old_overall_insns
= overall_insns
;
973 "Leafifying %s\n", cgraph_node_name (node
));
974 cycles
= htab_create (7, htab_hash_pointer
, htab_eq_pointer
, NULL
);
975 cgraph_find_cycles (node
, cycles
);
976 cgraph_flatten_node (node
, cycles
);
977 htab_delete (cycles
);
978 overall_insns
= old_overall_insns
;
979 /* We don't need to consider always_inline functions inside the flattened
984 if (!node
->local
.disregard_inline_limits
)
988 "\nConsidering %s %i insns (always inline)\n",
989 cgraph_node_name (node
), node
->global
.insns
);
990 old_insns
= overall_insns
;
991 for (e
= node
->callers
; e
; e
= next
)
993 next
= e
->next_caller
;
994 if (!e
->inline_failed
)
996 if (cgraph_recursive_inlining_p (e
->caller
, e
->callee
,
999 cgraph_mark_inline_edge (e
, true);
1002 " Inlined into %s which now has %i insns.\n",
1003 cgraph_node_name (e
->caller
),
1004 e
->caller
->global
.insns
);
1008 " Inlined for a net change of %+i insns.\n",
1009 overall_insns
- old_insns
);
1012 if (!flag_really_no_inline
)
1013 cgraph_decide_inlining_of_small_functions ();
1015 if (!flag_really_no_inline
1016 && flag_inline_functions_called_once
)
1019 fprintf (dump_file
, "\nDeciding on functions called once:\n");
1021 /* And finally decide what functions are called once. */
1023 for (i
= nnodes
- 1; i
>= 0; i
--)
1027 if (node
->callers
&& !node
->callers
->next_caller
&& !node
->needed
1028 && node
->local
.inlinable
&& node
->callers
->inline_failed
1029 && !DECL_EXTERNAL (node
->decl
) && !DECL_COMDAT (node
->decl
))
1032 struct cgraph_node
*node1
;
1034 /* Verify that we won't duplicate the caller. */
1035 for (node1
= node
->callers
->caller
;
1036 node1
->callers
&& !node1
->callers
->inline_failed
1037 && ok
; node1
= node1
->callers
->caller
)
1038 if (node1
->callers
->next_caller
|| node1
->needed
)
1045 "\nConsidering %s %i insns.\n",
1046 cgraph_node_name (node
), node
->global
.insns
);
1048 " Called once from %s %i insns.\n",
1049 cgraph_node_name (node
->callers
->caller
),
1050 node
->callers
->caller
->global
.insns
);
1053 old_insns
= overall_insns
;
1055 if (cgraph_check_inline_limits (node
->callers
->caller
, node
,
1058 cgraph_mark_inline (node
->callers
);
1061 " Inlined into %s which now has %i insns"
1062 " for a net change of %+i insns.\n",
1063 cgraph_node_name (node
->callers
->caller
),
1064 node
->callers
->caller
->global
.insns
,
1065 overall_insns
- old_insns
);
1071 " Inline limit reached, not inlined.\n");
1078 cgraph_remove_unreachable_nodes (false, dump_file
);
1079 cgraph_apply_inline_plan ();
1080 cgraph_remove_unreachable_nodes (false, dump_file
);
1084 "\nInlined %i calls, eliminated %i functions, "
1085 "%i insns turned to %i insns.\n\n",
1086 ncalls_inlined
, nfunctions_inlined
, initial_insns
,
1089 timevar_pop (TV_INLINE_HEURISTICS
);
1092 /* Decide on the inlining. We do so in the topological order to avoid
1093 expenses on updating data structures. */
1096 cgraph_decide_inlining_incrementally (struct cgraph_node
*node
, bool early
)
1098 struct cgraph_edge
*e
;
1099 bool inlined
= false;
1100 const char *failed_reason
;
1102 /* First of all look for always inline functions. */
1103 for (e
= node
->callees
; e
; e
= e
->next_callee
)
1104 if (e
->callee
->local
.disregard_inline_limits
1106 && !cgraph_recursive_inlining_p (node
, e
->callee
, &e
->inline_failed
)
1107 /* ??? It is possible that renaming variable removed the function body
1108 in duplicate_decls. See gcc.c-torture/compile/20011119-2.c */
1109 && (DECL_SAVED_TREE (e
->callee
->decl
) || e
->callee
->inline_decl
))
1111 if (dump_file
&& early
)
1113 fprintf (dump_file
, " Early inlining %s",
1114 cgraph_node_name (e
->callee
));
1115 fprintf (dump_file
, " into %s\n", cgraph_node_name (node
));
1117 cgraph_mark_inline (e
);
1121 /* Now do the automatic inlining. */
1122 if (!flag_really_no_inline
)
1123 for (e
= node
->callees
; e
; e
= e
->next_callee
)
1124 if (e
->callee
->local
.inlinable
1126 && !e
->callee
->local
.disregard_inline_limits
1127 && !cgraph_recursive_inlining_p (node
, e
->callee
, &e
->inline_failed
)
1129 || (cgraph_estimate_size_after_inlining (1, e
->caller
, node
)
1130 <= e
->caller
->global
.insns
))
1131 && cgraph_check_inline_limits (node
, e
->callee
, &e
->inline_failed
)
1132 && (DECL_SAVED_TREE (e
->callee
->decl
) || e
->callee
->inline_decl
))
1134 if (cgraph_default_inline_p (e
->callee
, &failed_reason
))
1136 if (dump_file
&& early
)
1138 fprintf (dump_file
, " Early inlining %s",
1139 cgraph_node_name (e
->callee
));
1140 fprintf (dump_file
, " into %s\n", cgraph_node_name (node
));
1142 cgraph_mark_inline (e
);
1146 e
->inline_failed
= failed_reason
;
1148 if (inlined
|| (warn_inline
&& !early
))
1150 /* Initialize the default bitmap obstack. */
1151 bitmap_obstack_initialize (NULL
);
1152 push_cfun (DECL_STRUCT_FUNCTION (node
->decl
));
1153 tree_register_cfg_hooks ();
1154 current_function_decl
= node
->decl
;
1155 optimize_inline_calls (current_function_decl
, early
);
1156 free_dominance_info (CDI_DOMINATORS
);
1157 free_dominance_info (CDI_POST_DOMINATORS
);
1158 node
->local
.self_insns
= node
->global
.insns
;
1159 current_function_decl
= NULL
;
1165 /* When inlining shall be performed. */
1167 cgraph_gate_inlining (void)
1169 return flag_inline_trees
/*&& 0*/;
1172 struct tree_opt_pass pass_ipa_inline
=
1174 "inline", /* name */
1175 cgraph_gate_inlining
, /* gate */
1176 cgraph_decide_inlining
, /* execute */
1179 0, /* static_pass_number */
1180 TV_INTEGRATION
, /* tv_id */
1181 0, /* properties_required */
1182 PROP_cfg
, /* properties_provided */
1183 0, /* properties_destroyed */
1184 0, /* todo_flags_start */
1185 TODO_dump_cgraph
| TODO_dump_func
, /* todo_flags_finish */
1189 /* Do inlining of small functions. Doing so early helps profiling and other
1190 passes to be somewhat more effective and avoids some code duplication in
1191 later real inlining pass for testcases with very many function calls. */
1193 cgraph_early_inlining (void)
1195 struct cgraph_node
*node
;
1197 struct cgraph_node
**order
=
1198 xcalloc (cgraph_n_nodes
, sizeof (struct cgraph_node
*));
1201 if (sorrycount
|| errorcount
)
1203 #ifdef ENABLE_CHECKING
1204 for (node
= cgraph_nodes
; node
; node
= node
->next
)
1205 gcc_assert (!node
->aux
);
1208 nnodes
= cgraph_postorder (order
);
1209 for (i
= nnodes
- 1; i
>= 0; i
--)
1212 if (node
->analyzed
&& node
->local
.inlinable
1213 && (node
->needed
|| node
->reachable
)
1215 cgraph_decide_inlining_incrementally (node
, true);
1217 cgraph_remove_unreachable_nodes (true, dump_file
);
1218 #ifdef ENABLE_CHECKING
1219 for (node
= cgraph_nodes
; node
; node
= node
->next
)
1220 gcc_assert (!node
->global
.inlined_to
);
1225 /* When inlining shall be performed. */
1227 cgraph_gate_early_inlining (void)
1229 return flag_inline_trees
&& flag_early_inlining
;
1232 struct tree_opt_pass pass_early_ipa_inline
=
1234 "einline", /* name */
1235 cgraph_gate_early_inlining
, /* gate */
1236 cgraph_early_inlining
, /* execute */
1239 0, /* static_pass_number */
1240 TV_INTEGRATION
, /* tv_id */
1241 0, /* properties_required */
1242 PROP_cfg
, /* properties_provided */
1243 0, /* properties_destroyed */
1244 0, /* todo_flags_start */
1245 TODO_dump_cgraph
| TODO_dump_func
, /* todo_flags_finish */