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
;
288 cgraph_propagate_frequency (e
->callee
);
290 /* Recursively clone all bodies. */
291 for (e
= e
->callee
->callees
; e
; e
= e
->next_callee
)
292 if (!e
->inline_failed
)
293 cgraph_clone_inlined_nodes (e
, duplicate
, update_original
);
296 /* Mark edge E as inlined and update callgraph accordingly. UPDATE_ORIGINAL
297 specify whether profile of original function should be updated. If any new
298 indirect edges are discovered in the process, add them to NEW_EDGES, unless
299 it is NULL. Return true iff any new callgraph edges were discovered as a
300 result of inlining. */
303 cgraph_mark_inline_edge (struct cgraph_edge
*e
, bool update_original
,
304 VEC (cgraph_edge_p
, heap
) **new_edges
)
306 int old_size
= 0, new_size
= 0;
307 struct cgraph_node
*to
= NULL
, *what
;
308 struct cgraph_edge
*curr
= e
;
311 gcc_assert (e
->inline_failed
);
312 e
->inline_failed
= CIF_OK
;
314 if (!e
->callee
->global
.inlined
)
315 DECL_POSSIBLY_INLINED (e
->callee
->decl
) = true;
316 e
->callee
->global
.inlined
= true;
318 cgraph_clone_inlined_nodes (e
, true, update_original
);
323 /* Now update size of caller and all functions caller is inlined into. */
324 for (;e
&& !e
->inline_failed
; e
= e
->caller
->callers
)
327 old_size
= e
->caller
->global
.size
;
328 new_size
= cgraph_estimate_size_after_inlining (1, to
, what
);
329 to
->global
.size
= new_size
;
330 to
->global
.time
= cgraph_estimate_time_after_inlining (freq
, to
, what
);
332 gcc_assert (what
->global
.inlined_to
== to
);
333 if (new_size
> old_size
)
334 overall_size
+= new_size
- old_size
;
337 if (flag_indirect_inlining
)
338 return ipa_propagate_indirect_call_infos (curr
, new_edges
);
343 /* Mark all calls of EDGE->CALLEE inlined into EDGE->CALLER. */
346 cgraph_mark_inline (struct cgraph_edge
*edge
)
348 struct cgraph_node
*to
= edge
->caller
;
349 struct cgraph_node
*what
= edge
->callee
;
350 struct cgraph_edge
*e
, *next
;
352 gcc_assert (!edge
->call_stmt_cannot_inline_p
);
353 /* Look for all calls, mark them inline and clone recursively
354 all inlined functions. */
355 for (e
= what
->callers
; e
; e
= next
)
357 next
= e
->next_caller
;
358 if (e
->caller
== to
&& e
->inline_failed
)
360 cgraph_mark_inline_edge (e
, true, NULL
);
367 /* Estimate the growth caused by inlining NODE into all callees. */
370 cgraph_estimate_growth (struct cgraph_node
*node
)
373 struct cgraph_edge
*e
;
374 bool self_recursive
= false;
376 if (node
->global
.estimated_growth
!= INT_MIN
)
377 return node
->global
.estimated_growth
;
379 for (e
= node
->callers
; e
; e
= e
->next_caller
)
381 if (e
->caller
== node
)
382 self_recursive
= true;
383 if (e
->inline_failed
)
384 growth
+= (cgraph_estimate_size_after_inlining (1, e
->caller
, node
)
385 - e
->caller
->global
.size
);
388 /* ??? Wrong for non-trivially self recursive functions or cases where
389 we decide to not inline for different reasons, but it is not big deal
390 as in that case we will keep the body around, but we will also avoid
392 if (cgraph_only_called_directly_p (node
)
393 && !DECL_EXTERNAL (node
->decl
) && !self_recursive
)
394 growth
-= node
->global
.size
;
396 node
->global
.estimated_growth
= growth
;
400 /* Return false when inlining WHAT into TO is not good idea
401 as it would cause too large growth of function bodies.
402 When ONE_ONLY is true, assume that only one call site is going
403 to be inlined, otherwise figure out how many call sites in
404 TO calls WHAT and verify that all can be inlined.
408 cgraph_check_inline_limits (struct cgraph_node
*to
, struct cgraph_node
*what
,
409 cgraph_inline_failed_t
*reason
, bool one_only
)
412 struct cgraph_edge
*e
;
415 HOST_WIDE_INT stack_size_limit
, inlined_stack
;
420 for (e
= to
->callees
; e
; e
= e
->next_callee
)
421 if (e
->callee
== what
)
424 if (to
->global
.inlined_to
)
425 to
= to
->global
.inlined_to
;
427 /* When inlining large function body called once into small function,
428 take the inlined function as base for limiting the growth. */
429 if (inline_summary (to
)->self_size
> inline_summary(what
)->self_size
)
430 limit
= inline_summary (to
)->self_size
;
432 limit
= inline_summary (what
)->self_size
;
434 limit
+= limit
* PARAM_VALUE (PARAM_LARGE_FUNCTION_GROWTH
) / 100;
436 /* Check the size after inlining against the function limits. But allow
437 the function to shrink if it went over the limits by forced inlining. */
438 newsize
= cgraph_estimate_size_after_inlining (times
, to
, what
);
439 if (newsize
>= to
->global
.size
440 && newsize
> PARAM_VALUE (PARAM_LARGE_FUNCTION_INSNS
)
444 *reason
= CIF_LARGE_FUNCTION_GROWTH_LIMIT
;
448 stack_size_limit
= inline_summary (to
)->estimated_self_stack_size
;
450 stack_size_limit
+= stack_size_limit
* PARAM_VALUE (PARAM_STACK_FRAME_GROWTH
) / 100;
452 inlined_stack
= (to
->global
.stack_frame_offset
453 + inline_summary (to
)->estimated_self_stack_size
454 + what
->global
.estimated_stack_size
);
455 if (inlined_stack
> stack_size_limit
456 && inlined_stack
> PARAM_VALUE (PARAM_LARGE_STACK_FRAME
))
459 *reason
= CIF_LARGE_STACK_FRAME_GROWTH_LIMIT
;
465 /* Return true when function N is small enough to be inlined. */
468 cgraph_default_inline_p (struct cgraph_node
*n
, cgraph_inline_failed_t
*reason
)
472 if (n
->local
.disregard_inline_limits
)
475 if (!flag_inline_small_functions
&& !DECL_DECLARED_INLINE_P (decl
))
478 *reason
= CIF_FUNCTION_NOT_INLINE_CANDIDATE
;
485 *reason
= CIF_BODY_NOT_AVAILABLE
;
489 if (DECL_DECLARED_INLINE_P (decl
))
491 if (n
->global
.size
>= MAX_INLINE_INSNS_SINGLE
)
494 *reason
= CIF_MAX_INLINE_INSNS_SINGLE_LIMIT
;
500 if (n
->global
.size
>= MAX_INLINE_INSNS_AUTO
)
503 *reason
= CIF_MAX_INLINE_INSNS_AUTO_LIMIT
;
511 /* Return true when inlining WHAT would create recursive inlining.
512 We call recursive inlining all cases where same function appears more than
513 once in the single recursion nest path in the inline graph. */
516 cgraph_recursive_inlining_p (struct cgraph_node
*to
,
517 struct cgraph_node
*what
,
518 cgraph_inline_failed_t
*reason
)
521 if (to
->global
.inlined_to
)
522 recursive
= what
->decl
== to
->global
.inlined_to
->decl
;
524 recursive
= what
->decl
== to
->decl
;
525 /* Marking recursive function inline has sane semantic and thus we should
527 if (recursive
&& reason
)
528 *reason
= (what
->local
.disregard_inline_limits
529 ? CIF_RECURSIVE_INLINING
: CIF_UNSPECIFIED
);
533 /* A cost model driving the inlining heuristics in a way so the edges with
534 smallest badness are inlined first. After each inlining is performed
535 the costs of all caller edges of nodes affected are recomputed so the
536 metrics may accurately depend on values such as number of inlinable callers
537 of the function or function body size. */
540 cgraph_edge_badness (struct cgraph_edge
*edge
, bool dump
)
544 (cgraph_estimate_size_after_inlining (1, edge
->caller
, edge
->callee
)
545 - edge
->caller
->global
.size
);
549 fprintf (dump_file
, " Badness calculcation for %s -> %s\n",
550 cgraph_node_name (edge
->caller
),
551 cgraph_node_name (edge
->callee
));
552 fprintf (dump_file
, " growth %i, time %i-%i, size %i-%i\n",
554 edge
->callee
->global
.time
,
555 inline_summary (edge
->callee
)->time_inlining_benefit
,
556 edge
->callee
->global
.size
,
557 inline_summary (edge
->callee
)->size_inlining_benefit
);
560 /* Always prefer inlining saving code size. */
563 badness
= INT_MIN
- growth
;
565 fprintf (dump_file
, " %i: Growth %i < 0\n", (int) badness
,
569 /* When profiling is available, base priorities -(#calls / growth).
570 So we optimize for overall number of "executed" inlined calls. */
575 ((double) edge
->count
* INT_MIN
/ max_count
/ (max_benefit
+ 1)) *
576 (inline_summary (edge
->callee
)->time_inlining_benefit
+ 1)) / growth
;
580 " %i (relative %f): profile info. Relative count %f"
581 " * Relative benefit %f\n",
582 (int) badness
, (double) badness
/ INT_MIN
,
583 (double) edge
->count
/ max_count
,
584 (double) (inline_summary (edge
->callee
)->
585 time_inlining_benefit
+ 1) / (max_benefit
+ 1));
589 /* When function local profile is available, base priorities on
590 growth / frequency, so we optimize for overall frequency of inlined
591 calls. This is not too accurate since while the call might be frequent
592 within function, the function itself is infrequent.
594 Other objective to optimize for is number of different calls inlined.
595 We add the estimated growth after inlining all functions to bias the
596 priorities slightly in this direction (so fewer times called functions
597 of the same size gets priority). */
598 else if (flag_guess_branch_prob
)
600 int div
= edge
->frequency
* 100 / CGRAPH_FREQ_BASE
+ 1;
603 badness
= growth
* 10000;
605 MIN (100 * inline_summary (edge
->callee
)->time_inlining_benefit
/
606 (edge
->callee
->global
.time
+ 1) +1, 100);
610 /* Decrease badness if call is nested. */
611 /* Compress the range so we don't overflow. */
613 div
= 10000 + ceil_log2 (div
) - 8;
618 growth_for_all
= cgraph_estimate_growth (edge
->callee
);
619 badness
+= growth_for_all
;
620 if (badness
> INT_MAX
)
625 " %i: guessed profile. frequency %i, overall growth %i,"
626 " benefit %i%%, divisor %i\n",
627 (int) badness
, edge
->frequency
, growth_for_all
, benefitperc
, div
);
630 /* When function local profile is not available or it does not give
631 useful information (ie frequency is zero), base the cost on
632 loop nest and overall size growth, so we optimize for overall number
633 of functions fully inlined in program. */
636 int nest
= MIN (edge
->loop_nest
, 8);
637 badness
= cgraph_estimate_growth (edge
->callee
) * 256;
639 /* Decrease badness if call is nested. */
647 fprintf (dump_file
, " %i: no profile. nest %i\n", (int) badness
,
651 /* Ensure that we did not overflow in all the fixed point math above. */
652 gcc_assert (badness
>= INT_MIN
);
653 gcc_assert (badness
<= INT_MAX
- 1);
654 /* Make recursive inlining happen always after other inlining is done. */
655 if (cgraph_recursive_inlining_p (edge
->caller
, edge
->callee
, NULL
))
661 /* Recompute heap nodes for each of caller edge. */
664 update_caller_keys (fibheap_t heap
, struct cgraph_node
*node
,
665 bitmap updated_nodes
)
667 struct cgraph_edge
*edge
;
668 cgraph_inline_failed_t failed_reason
;
670 if (!node
->local
.inlinable
|| node
->local
.disregard_inline_limits
671 || node
->global
.inlined_to
)
673 if (bitmap_bit_p (updated_nodes
, node
->uid
))
675 bitmap_set_bit (updated_nodes
, node
->uid
);
676 node
->global
.estimated_growth
= INT_MIN
;
678 if (!node
->local
.inlinable
)
680 /* Prune out edges we won't inline into anymore. */
681 if (!cgraph_default_inline_p (node
, &failed_reason
))
683 for (edge
= node
->callers
; edge
; edge
= edge
->next_caller
)
686 fibheap_delete_node (heap
, (fibnode_t
) edge
->aux
);
688 if (edge
->inline_failed
)
689 edge
->inline_failed
= failed_reason
;
694 for (edge
= node
->callers
; edge
; edge
= edge
->next_caller
)
695 if (edge
->inline_failed
)
697 int badness
= cgraph_edge_badness (edge
, false);
700 fibnode_t n
= (fibnode_t
) edge
->aux
;
701 gcc_assert (n
->data
== edge
);
702 if (n
->key
== badness
)
705 /* fibheap_replace_key only increase the keys. */
706 if (badness
< n
->key
)
708 fibheap_replace_key (heap
, n
, badness
);
709 gcc_assert (n
->key
== badness
);
712 fibheap_delete_node (heap
, (fibnode_t
) edge
->aux
);
714 edge
->aux
= fibheap_insert (heap
, badness
, edge
);
718 /* Recompute heap nodes for each of caller edges of each of callees. */
721 update_callee_keys (fibheap_t heap
, struct cgraph_node
*node
,
722 bitmap updated_nodes
)
724 struct cgraph_edge
*e
;
725 node
->global
.estimated_growth
= INT_MIN
;
727 for (e
= node
->callees
; e
; e
= e
->next_callee
)
728 if (e
->inline_failed
)
729 update_caller_keys (heap
, e
->callee
, updated_nodes
);
730 else if (!e
->inline_failed
)
731 update_callee_keys (heap
, e
->callee
, updated_nodes
);
734 /* Enqueue all recursive calls from NODE into priority queue depending on
735 how likely we want to recursively inline the call. */
738 lookup_recursive_calls (struct cgraph_node
*node
, struct cgraph_node
*where
,
742 struct cgraph_edge
*e
;
743 for (e
= where
->callees
; e
; e
= e
->next_callee
)
744 if (e
->callee
== node
)
746 /* When profile feedback is available, prioritize by expected number
747 of calls. Without profile feedback we maintain simple queue
748 to order candidates via recursive depths. */
749 fibheap_insert (heap
,
750 !max_count
? priority
++
751 : -(e
->count
/ ((max_count
+ (1<<24) - 1) / (1<<24))),
754 for (e
= where
->callees
; e
; e
= e
->next_callee
)
755 if (!e
->inline_failed
)
756 lookup_recursive_calls (node
, e
->callee
, heap
);
759 /* Decide on recursive inlining: in the case function has recursive calls,
760 inline until body size reaches given argument. If any new indirect edges
761 are discovered in the process, add them to *NEW_EDGES, unless NEW_EDGES
765 cgraph_decide_recursive_inlining (struct cgraph_node
*node
,
766 VEC (cgraph_edge_p
, heap
) **new_edges
)
768 int limit
= PARAM_VALUE (PARAM_MAX_INLINE_INSNS_RECURSIVE_AUTO
);
769 int max_depth
= PARAM_VALUE (PARAM_MAX_INLINE_RECURSIVE_DEPTH_AUTO
);
770 int probability
= PARAM_VALUE (PARAM_MIN_INLINE_RECURSIVE_PROBABILITY
);
772 struct cgraph_edge
*e
;
773 struct cgraph_node
*master_clone
, *next
;
777 /* It does not make sense to recursively inline always-inline functions
778 as we are going to sorry() on the remaining calls anyway. */
779 if (node
->local
.disregard_inline_limits
780 && lookup_attribute ("always_inline", DECL_ATTRIBUTES (node
->decl
)))
783 if (optimize_function_for_size_p (DECL_STRUCT_FUNCTION (node
->decl
))
784 || (!flag_inline_functions
&& !DECL_DECLARED_INLINE_P (node
->decl
)))
787 if (DECL_DECLARED_INLINE_P (node
->decl
))
789 limit
= PARAM_VALUE (PARAM_MAX_INLINE_INSNS_RECURSIVE
);
790 max_depth
= PARAM_VALUE (PARAM_MAX_INLINE_RECURSIVE_DEPTH
);
793 /* Make sure that function is small enough to be considered for inlining. */
795 || cgraph_estimate_size_after_inlining (1, node
, node
) >= limit
)
797 heap
= fibheap_new ();
798 lookup_recursive_calls (node
, node
, heap
);
799 if (fibheap_empty (heap
))
801 fibheap_delete (heap
);
807 " Performing recursive inlining on %s\n",
808 cgraph_node_name (node
));
810 /* We need original clone to copy around. */
811 master_clone
= cgraph_clone_node (node
, node
->count
, CGRAPH_FREQ_BASE
, 1,
813 master_clone
->needed
= true;
814 for (e
= master_clone
->callees
; e
; e
= e
->next_callee
)
815 if (!e
->inline_failed
)
816 cgraph_clone_inlined_nodes (e
, true, false);
818 /* Do the inlining and update list of recursive call during process. */
819 while (!fibheap_empty (heap
)
820 && (cgraph_estimate_size_after_inlining (1, node
, master_clone
)
823 struct cgraph_edge
*curr
824 = (struct cgraph_edge
*) fibheap_extract_min (heap
);
825 struct cgraph_node
*cnode
;
828 for (cnode
= curr
->caller
;
829 cnode
->global
.inlined_to
; cnode
= cnode
->callers
->caller
)
830 if (node
->decl
== curr
->callee
->decl
)
832 if (depth
> max_depth
)
836 " maximal depth reached\n");
842 if (!cgraph_maybe_hot_edge_p (curr
))
845 fprintf (dump_file
, " Not inlining cold call\n");
848 if (curr
->count
* 100 / node
->count
< probability
)
852 " Probability of edge is too small\n");
860 " Inlining call of depth %i", depth
);
863 fprintf (dump_file
, " called approx. %.2f times per call",
864 (double)curr
->count
/ node
->count
);
866 fprintf (dump_file
, "\n");
868 cgraph_redirect_edge_callee (curr
, master_clone
);
869 cgraph_mark_inline_edge (curr
, false, new_edges
);
870 lookup_recursive_calls (node
, curr
->callee
, heap
);
873 if (!fibheap_empty (heap
) && dump_file
)
874 fprintf (dump_file
, " Recursive inlining growth limit met.\n");
876 fibheap_delete (heap
);
879 "\n Inlined %i times, body grown from size %i to %i, time %i to %i\n", n
,
880 master_clone
->global
.size
, node
->global
.size
,
881 master_clone
->global
.time
, node
->global
.time
);
883 /* Remove master clone we used for inlining. We rely that clones inlined
884 into master clone gets queued just before master clone so we don't
886 for (node
= cgraph_nodes
; node
!= master_clone
;
890 if (node
->global
.inlined_to
== master_clone
)
891 cgraph_remove_node (node
);
893 cgraph_remove_node (master_clone
);
894 /* FIXME: Recursive inlining actually reduces number of calls of the
895 function. At this place we should probably walk the function and
896 inline clones and compensate the counts accordingly. This probably
897 doesn't matter much in practice. */
901 /* Set inline_failed for all callers of given function to REASON. */
904 cgraph_set_inline_failed (struct cgraph_node
*node
,
905 cgraph_inline_failed_t reason
)
907 struct cgraph_edge
*e
;
910 fprintf (dump_file
, "Inlining failed: %s\n",
911 cgraph_inline_failed_string (reason
));
912 for (e
= node
->callers
; e
; e
= e
->next_caller
)
913 if (e
->inline_failed
)
914 e
->inline_failed
= reason
;
917 /* Given whole compilation unit estimate of INSNS, compute how large we can
918 allow the unit to grow. */
920 compute_max_insns (int insns
)
922 int max_insns
= insns
;
923 if (max_insns
< PARAM_VALUE (PARAM_LARGE_UNIT_INSNS
))
924 max_insns
= PARAM_VALUE (PARAM_LARGE_UNIT_INSNS
);
926 return ((HOST_WIDEST_INT
) max_insns
927 * (100 + PARAM_VALUE (PARAM_INLINE_UNIT_GROWTH
)) / 100);
930 /* Compute badness of all edges in NEW_EDGES and add them to the HEAP. */
932 add_new_edges_to_heap (fibheap_t heap
, VEC (cgraph_edge_p
, heap
) *new_edges
)
934 while (VEC_length (cgraph_edge_p
, new_edges
) > 0)
936 struct cgraph_edge
*edge
= VEC_pop (cgraph_edge_p
, new_edges
);
938 gcc_assert (!edge
->aux
);
939 edge
->aux
= fibheap_insert (heap
, cgraph_edge_badness (edge
, false), edge
);
944 /* We use greedy algorithm for inlining of small functions:
945 All inline candidates are put into prioritized heap based on estimated
946 growth of the overall number of instructions and then update the estimates.
948 INLINED and INLINED_CALEES are just pointers to arrays large enough
949 to be passed to cgraph_inlined_into and cgraph_inlined_callees. */
952 cgraph_decide_inlining_of_small_functions (void)
954 struct cgraph_node
*node
;
955 struct cgraph_edge
*edge
;
956 cgraph_inline_failed_t failed_reason
;
957 fibheap_t heap
= fibheap_new ();
958 bitmap updated_nodes
= BITMAP_ALLOC (NULL
);
959 int min_size
, max_size
;
960 VEC (cgraph_edge_p
, heap
) *new_indirect_edges
= NULL
;
962 if (flag_indirect_inlining
)
963 new_indirect_edges
= VEC_alloc (cgraph_edge_p
, heap
, 8);
966 fprintf (dump_file
, "\nDeciding on smaller functions:\n");
968 /* Put all inline candidates into the heap. */
970 for (node
= cgraph_nodes
; node
; node
= node
->next
)
972 if (!node
->local
.inlinable
|| !node
->callers
)
975 fprintf (dump_file
, "Considering inline candidate %s.\n", cgraph_node_name (node
));
977 node
->global
.estimated_growth
= INT_MIN
;
978 if (!cgraph_default_inline_p (node
, &failed_reason
))
980 cgraph_set_inline_failed (node
, failed_reason
);
984 for (edge
= node
->callers
; edge
; edge
= edge
->next_caller
)
985 if (edge
->inline_failed
)
987 gcc_assert (!edge
->aux
);
988 edge
->aux
= fibheap_insert (heap
, cgraph_edge_badness (edge
, false), edge
);
992 max_size
= compute_max_insns (overall_size
);
993 min_size
= overall_size
;
995 while (overall_size
<= max_size
996 && !fibheap_empty (heap
))
998 int old_size
= overall_size
;
999 struct cgraph_node
*where
, *callee
;
1000 int badness
= fibheap_min_key (heap
);
1002 cgraph_inline_failed_t not_good
= CIF_OK
;
1004 edge
= (struct cgraph_edge
*) fibheap_extract_min (heap
);
1005 gcc_assert (edge
->aux
);
1007 if (!edge
->inline_failed
)
1009 #ifdef ENABLE_CHECKING
1010 gcc_assert (cgraph_edge_badness (edge
, false) == badness
);
1012 callee
= edge
->callee
;
1014 growth
= (cgraph_estimate_size_after_inlining (1, edge
->caller
, edge
->callee
)
1015 - edge
->caller
->global
.size
);
1020 "\nConsidering %s with %i size\n",
1021 cgraph_node_name (edge
->callee
),
1022 edge
->callee
->global
.size
);
1024 " to be inlined into %s in %s:%i\n"
1025 " Estimated growth after inlined into all callees is %+i insns.\n"
1026 " Estimated badness is %i, frequency %.2f.\n",
1027 cgraph_node_name (edge
->caller
),
1028 flag_wpa
? "unknown"
1029 : gimple_filename ((const_gimple
) edge
->call_stmt
),
1030 flag_wpa
? -1 : gimple_lineno ((const_gimple
) edge
->call_stmt
),
1031 cgraph_estimate_growth (edge
->callee
),
1033 edge
->frequency
/ (double)CGRAPH_FREQ_BASE
);
1035 fprintf (dump_file
," Called "HOST_WIDEST_INT_PRINT_DEC
"x\n", edge
->count
);
1036 if (dump_flags
& TDF_DETAILS
)
1037 cgraph_edge_badness (edge
, true);
1040 /* When not having profile info ready we don't weight by any way the
1041 position of call in procedure itself. This means if call of
1042 function A from function B seems profitable to inline, the recursive
1043 call of function A in inline copy of A in B will look profitable too
1044 and we end up inlining until reaching maximal function growth. This
1045 is not good idea so prohibit the recursive inlining.
1047 ??? When the frequencies are taken into account we might not need this
1050 We need to be cureful here, in some testcases, e.g. directivec.c in
1051 libcpp, we can estimate self recursive function to have negative growth
1052 for inlining completely.
1056 where
= edge
->caller
;
1057 while (where
->global
.inlined_to
)
1059 if (where
->decl
== edge
->callee
->decl
)
1061 where
= where
->callers
->caller
;
1063 if (where
->global
.inlined_to
)
1066 = (edge
->callee
->local
.disregard_inline_limits
1067 ? CIF_RECURSIVE_INLINING
: CIF_UNSPECIFIED
);
1069 fprintf (dump_file
, " inline_failed:Recursive inlining performed only for function itself.\n");
1074 if (!cgraph_maybe_hot_edge_p (edge
))
1075 not_good
= CIF_UNLIKELY_CALL
;
1076 if (!flag_inline_functions
1077 && !DECL_DECLARED_INLINE_P (edge
->callee
->decl
))
1078 not_good
= CIF_NOT_DECLARED_INLINED
;
1079 if (optimize_function_for_size_p (DECL_STRUCT_FUNCTION(edge
->caller
->decl
)))
1080 not_good
= CIF_OPTIMIZING_FOR_SIZE
;
1081 if (not_good
&& growth
> 0 && cgraph_estimate_growth (edge
->callee
) > 0)
1083 if (!cgraph_recursive_inlining_p (edge
->caller
, edge
->callee
,
1084 &edge
->inline_failed
))
1086 edge
->inline_failed
= not_good
;
1088 fprintf (dump_file
, " inline_failed:%s.\n",
1089 cgraph_inline_failed_string (edge
->inline_failed
));
1093 if (!cgraph_default_inline_p (edge
->callee
, &edge
->inline_failed
))
1095 if (!cgraph_recursive_inlining_p (edge
->caller
, edge
->callee
,
1096 &edge
->inline_failed
))
1099 fprintf (dump_file
, " inline_failed:%s.\n",
1100 cgraph_inline_failed_string (edge
->inline_failed
));
1104 if (!tree_can_inline_p (edge
))
1107 fprintf (dump_file
, " inline_failed:%s.\n",
1108 cgraph_inline_failed_string (edge
->inline_failed
));
1111 if (cgraph_recursive_inlining_p (edge
->caller
, edge
->callee
,
1112 &edge
->inline_failed
))
1114 where
= edge
->caller
;
1115 if (where
->global
.inlined_to
)
1116 where
= where
->global
.inlined_to
;
1117 if (!cgraph_decide_recursive_inlining (where
,
1118 flag_indirect_inlining
1119 ? &new_indirect_edges
: NULL
))
1121 if (flag_indirect_inlining
)
1122 add_new_edges_to_heap (heap
, new_indirect_edges
);
1123 update_callee_keys (heap
, where
, updated_nodes
);
1127 struct cgraph_node
*callee
;
1128 if (edge
->call_stmt_cannot_inline_p
1129 || !cgraph_check_inline_limits (edge
->caller
, edge
->callee
,
1130 &edge
->inline_failed
, true))
1133 fprintf (dump_file
, " Not inlining into %s:%s.\n",
1134 cgraph_node_name (edge
->caller
),
1135 cgraph_inline_failed_string (edge
->inline_failed
));
1138 callee
= edge
->callee
;
1139 cgraph_mark_inline_edge (edge
, true, &new_indirect_edges
);
1140 if (flag_indirect_inlining
)
1141 add_new_edges_to_heap (heap
, new_indirect_edges
);
1143 update_callee_keys (heap
, callee
, updated_nodes
);
1145 where
= edge
->caller
;
1146 if (where
->global
.inlined_to
)
1147 where
= where
->global
.inlined_to
;
1149 /* Our profitability metric can depend on local properties
1150 such as number of inlinable calls and size of the function body.
1151 After inlining these properties might change for the function we
1152 inlined into (since it's body size changed) and for the functions
1153 called by function we inlined (since number of it inlinable callers
1155 update_caller_keys (heap
, where
, updated_nodes
);
1157 /* We removed one call of the function we just inlined. If offline
1158 copy is still needed, be sure to update the keys. */
1159 if (callee
!= where
&& !callee
->global
.inlined_to
)
1160 update_caller_keys (heap
, callee
, updated_nodes
);
1161 bitmap_clear (updated_nodes
);
1166 " Inlined into %s which now has size %i and self time %i,"
1167 "net change of %+i.\n",
1168 cgraph_node_name (edge
->caller
),
1169 edge
->caller
->global
.time
,
1170 edge
->caller
->global
.size
,
1171 overall_size
- old_size
);
1173 if (min_size
> overall_size
)
1175 min_size
= overall_size
;
1176 max_size
= compute_max_insns (min_size
);
1179 fprintf (dump_file
, "New minimal size reached: %i\n", min_size
);
1182 while (!fibheap_empty (heap
))
1184 int badness
= fibheap_min_key (heap
);
1186 edge
= (struct cgraph_edge
*) fibheap_extract_min (heap
);
1187 gcc_assert (edge
->aux
);
1189 if (!edge
->inline_failed
)
1191 #ifdef ENABLE_CHECKING
1192 gcc_assert (cgraph_edge_badness (edge
, false) == badness
);
1197 "\nSkipping %s with %i size\n",
1198 cgraph_node_name (edge
->callee
),
1199 edge
->callee
->global
.size
);
1201 " called by %s in %s:%i\n"
1202 " Estimated growth after inlined into all callees is %+i insns.\n"
1203 " Estimated badness is %i, frequency %.2f.\n",
1204 cgraph_node_name (edge
->caller
),
1205 flag_wpa
? "unknown"
1206 : gimple_filename ((const_gimple
) edge
->call_stmt
),
1207 flag_wpa
? -1 : gimple_lineno ((const_gimple
) edge
->call_stmt
),
1208 cgraph_estimate_growth (edge
->callee
),
1210 edge
->frequency
/ (double)CGRAPH_FREQ_BASE
);
1212 fprintf (dump_file
," Called "HOST_WIDEST_INT_PRINT_DEC
"x\n", edge
->count
);
1213 if (dump_flags
& TDF_DETAILS
)
1214 cgraph_edge_badness (edge
, true);
1216 if (!edge
->callee
->local
.disregard_inline_limits
&& edge
->inline_failed
1217 && !cgraph_recursive_inlining_p (edge
->caller
, edge
->callee
,
1218 &edge
->inline_failed
))
1219 edge
->inline_failed
= CIF_INLINE_UNIT_GROWTH_LIMIT
;
1222 if (new_indirect_edges
)
1223 VEC_free (cgraph_edge_p
, heap
, new_indirect_edges
);
1224 fibheap_delete (heap
);
1225 BITMAP_FREE (updated_nodes
);
1228 /* Flatten NODE from the IPA inliner. */
1231 cgraph_flatten (struct cgraph_node
*node
)
1233 struct cgraph_edge
*e
;
1235 /* We shouldn't be called recursively when we are being processed. */
1236 gcc_assert (node
->aux
== NULL
);
1238 node
->aux
= (void *)(size_t) INLINE_ALL
;
1240 for (e
= node
->callees
; e
; e
= e
->next_callee
)
1242 struct cgraph_node
*orig_callee
;
1244 if (e
->call_stmt_cannot_inline_p
)
1247 if (!e
->callee
->analyzed
)
1251 "Not inlining: Function body not available.\n");
1255 /* We've hit cycle? It is time to give up. */
1260 "Not inlining %s into %s to avoid cycle.\n",
1261 cgraph_node_name (e
->callee
),
1262 cgraph_node_name (e
->caller
));
1263 e
->inline_failed
= CIF_RECURSIVE_INLINING
;
1267 /* When the edge is already inlined, we just need to recurse into
1268 it in order to fully flatten the leaves. */
1269 if (!e
->inline_failed
)
1271 cgraph_flatten (e
->callee
);
1275 if (cgraph_recursive_inlining_p (node
, e
->callee
, &e
->inline_failed
))
1278 fprintf (dump_file
, "Not inlining: recursive call.\n");
1282 if (!tree_can_inline_p (e
))
1285 fprintf (dump_file
, "Not inlining: %s",
1286 cgraph_inline_failed_string (e
->inline_failed
));
1290 /* Inline the edge and flatten the inline clone. Avoid
1291 recursing through the original node if the node was cloned. */
1293 fprintf (dump_file
, " Inlining %s into %s.\n",
1294 cgraph_node_name (e
->callee
),
1295 cgraph_node_name (e
->caller
));
1296 orig_callee
= e
->callee
;
1297 cgraph_mark_inline_edge (e
, true, NULL
);
1298 if (e
->callee
!= orig_callee
)
1299 orig_callee
->aux
= (void *)(size_t) INLINE_ALL
;
1300 cgraph_flatten (e
->callee
);
1301 if (e
->callee
!= orig_callee
)
1302 orig_callee
->aux
= NULL
;
1308 /* Decide on the inlining. We do so in the topological order to avoid
1309 expenses on updating data structures. */
1312 cgraph_decide_inlining (void)
1314 struct cgraph_node
*node
;
1316 struct cgraph_node
**order
=
1317 XCNEWVEC (struct cgraph_node
*, cgraph_n_nodes
);
1320 int initial_size
= 0;
1322 cgraph_remove_function_insertion_hook (function_insertion_hook_holder
);
1323 if (in_lto_p
&& flag_indirect_inlining
)
1324 ipa_update_after_lto_read ();
1328 for (node
= cgraph_nodes
; node
; node
= node
->next
)
1331 struct cgraph_edge
*e
;
1333 gcc_assert (inline_summary (node
)->self_size
== node
->global
.size
);
1334 initial_size
+= node
->global
.size
;
1335 for (e
= node
->callees
; e
; e
= e
->next_callee
)
1336 if (max_count
< e
->count
)
1337 max_count
= e
->count
;
1338 if (max_benefit
< inline_summary (node
)->time_inlining_benefit
)
1339 max_benefit
= inline_summary (node
)->time_inlining_benefit
;
1341 gcc_assert (in_lto_p
1343 || (profile_info
&& flag_branch_probabilities
));
1344 overall_size
= initial_size
;
1346 nnodes
= cgraph_postorder (order
);
1350 "\nDeciding on inlining. Starting with size %i.\n",
1353 for (node
= cgraph_nodes
; node
; node
= node
->next
)
1357 fprintf (dump_file
, "\nFlattening functions:\n");
1359 /* In the first pass handle functions to be flattened. Do this with
1360 a priority so none of our later choices will make this impossible. */
1361 for (i
= nnodes
- 1; i
>= 0; i
--)
1365 /* Handle nodes to be flattened, but don't update overall unit
1366 size. Calling the incremental inliner here is lame,
1367 a simple worklist should be enough. What should be left
1368 here from the early inliner (if it runs) is cyclic cases.
1369 Ideally when processing callees we stop inlining at the
1370 entry of cycles, possibly cloning that entry point and
1371 try to flatten itself turning it into a self-recursive
1373 if (lookup_attribute ("flatten",
1374 DECL_ATTRIBUTES (node
->decl
)) != NULL
)
1378 "Flattening %s\n", cgraph_node_name (node
));
1379 cgraph_flatten (node
);
1383 cgraph_decide_inlining_of_small_functions ();
1385 if (flag_inline_functions_called_once
)
1388 fprintf (dump_file
, "\nDeciding on functions called once:\n");
1390 /* And finally decide what functions are called once. */
1391 for (i
= nnodes
- 1; i
>= 0; i
--)
1396 && !node
->callers
->next_caller
1397 && cgraph_only_called_directly_p (node
)
1398 && node
->local
.inlinable
1399 && node
->callers
->inline_failed
1400 && node
->callers
->caller
!= node
1401 && node
->callers
->caller
->global
.inlined_to
!= node
1402 && !node
->callers
->call_stmt_cannot_inline_p
1403 && !DECL_EXTERNAL (node
->decl
)
1404 && !DECL_COMDAT (node
->decl
))
1406 cgraph_inline_failed_t reason
;
1407 old_size
= overall_size
;
1411 "\nConsidering %s size %i.\n",
1412 cgraph_node_name (node
), node
->global
.size
);
1414 " Called once from %s %i insns.\n",
1415 cgraph_node_name (node
->callers
->caller
),
1416 node
->callers
->caller
->global
.size
);
1419 if (cgraph_check_inline_limits (node
->callers
->caller
, node
,
1422 struct cgraph_node
*caller
= node
->callers
->caller
;
1423 cgraph_mark_inline (node
->callers
);
1426 " Inlined into %s which now has %i size"
1427 " for a net change of %+i size.\n",
1428 cgraph_node_name (caller
),
1429 caller
->global
.size
,
1430 overall_size
- old_size
);
1436 " Not inlining: %s.\n",
1437 cgraph_inline_failed_string (reason
));
1443 /* Free ipa-prop structures if they are no longer needed. */
1444 if (flag_indirect_inlining
)
1445 free_all_ipa_structures_after_iinln ();
1449 "\nInlined %i calls, eliminated %i functions, "
1450 "size %i turned to %i size.\n\n",
1451 ncalls_inlined
, nfunctions_inlined
, initial_size
,
1457 /* Return true when N is leaf function. Accept cheap (pure&const) builtins
1458 in leaf functions. */
1460 leaf_node_p (struct cgraph_node
*n
)
1462 struct cgraph_edge
*e
;
1463 for (e
= n
->callees
; e
; e
= e
->next_callee
)
1464 if (!DECL_BUILT_IN (e
->callee
->decl
)
1465 || (!TREE_READONLY (e
->callee
->decl
)
1466 || DECL_PURE_P (e
->callee
->decl
)))
1471 /* Decide on the inlining. We do so in the topological order to avoid
1472 expenses on updating data structures. */
1475 cgraph_decide_inlining_incrementally (struct cgraph_node
*node
,
1476 enum inlining_mode mode
)
1478 struct cgraph_edge
*e
;
1479 bool inlined
= false;
1480 cgraph_inline_failed_t failed_reason
;
1482 #ifdef ENABLE_CHECKING
1483 verify_cgraph_node (node
);
1486 if (mode
!= INLINE_ALWAYS_INLINE
&& mode
!= INLINE_SIZE_NORECURSIVE
1487 && lookup_attribute ("flatten", DECL_ATTRIBUTES (node
->decl
)) != NULL
)
1490 fprintf (dump_file
, "Incrementally flattening %s\n",
1491 cgraph_node_name (node
));
1495 /* First of all look for always inline functions. */
1496 if (mode
!= INLINE_SIZE_NORECURSIVE
)
1497 for (e
= node
->callees
; e
; e
= e
->next_callee
)
1499 if (!e
->callee
->local
.disregard_inline_limits
1500 && (mode
!= INLINE_ALL
|| !e
->callee
->local
.inlinable
))
1502 if (e
->call_stmt_cannot_inline_p
)
1506 "Considering to always inline inline candidate %s.\n",
1507 cgraph_node_name (e
->callee
));
1508 if (cgraph_recursive_inlining_p (node
, e
->callee
, &e
->inline_failed
))
1511 fprintf (dump_file
, "Not inlining: recursive call.\n");
1514 if (!tree_can_inline_p (e
))
1519 cgraph_inline_failed_string (e
->inline_failed
));
1522 if (gimple_in_ssa_p (DECL_STRUCT_FUNCTION (node
->decl
))
1523 != gimple_in_ssa_p (DECL_STRUCT_FUNCTION (e
->callee
->decl
)))
1526 fprintf (dump_file
, "Not inlining: SSA form does not match.\n");
1529 if (!e
->callee
->analyzed
)
1533 "Not inlining: Function body no longer available.\n");
1538 fprintf (dump_file
, " Inlining %s into %s.\n",
1539 cgraph_node_name (e
->callee
),
1540 cgraph_node_name (e
->caller
));
1541 cgraph_mark_inline (e
);
1545 /* Now do the automatic inlining. */
1546 if (mode
!= INLINE_ALL
&& mode
!= INLINE_ALWAYS_INLINE
1547 /* Never inline regular functions into always-inline functions
1548 during incremental inlining. */
1549 && !node
->local
.disregard_inline_limits
)
1551 bitmap visited
= BITMAP_ALLOC (NULL
);
1552 for (e
= node
->callees
; e
; e
= e
->next_callee
)
1554 int allowed_growth
= 0;
1555 if (!e
->callee
->local
.inlinable
1556 || !e
->inline_failed
1557 || e
->callee
->local
.disregard_inline_limits
)
1559 /* We are inlining a function to all call-sites in node
1560 or to none. So visit each candidate only once. */
1561 if (!bitmap_set_bit (visited
, e
->callee
->uid
))
1564 fprintf (dump_file
, "Considering inline candidate %s.\n",
1565 cgraph_node_name (e
->callee
));
1566 if (cgraph_recursive_inlining_p (node
, e
->callee
, &e
->inline_failed
))
1569 fprintf (dump_file
, "Not inlining: recursive call.\n");
1572 if (gimple_in_ssa_p (DECL_STRUCT_FUNCTION (node
->decl
))
1573 != gimple_in_ssa_p (DECL_STRUCT_FUNCTION (e
->callee
->decl
)))
1577 "Not inlining: SSA form does not match.\n");
1581 if (cgraph_maybe_hot_edge_p (e
) && leaf_node_p (e
->callee
)
1582 && optimize_function_for_speed_p (cfun
))
1583 allowed_growth
= PARAM_VALUE (PARAM_EARLY_INLINING_INSNS
);
1585 /* When the function body would grow and inlining the function
1586 won't eliminate the need for offline copy of the function,
1588 if (((mode
== INLINE_SIZE
|| mode
== INLINE_SIZE_NORECURSIVE
)
1589 || (!flag_inline_functions
1590 && !DECL_DECLARED_INLINE_P (e
->callee
->decl
)))
1591 && (cgraph_estimate_size_after_inlining (1, e
->caller
, e
->callee
)
1592 > e
->caller
->global
.size
+ allowed_growth
)
1593 && cgraph_estimate_growth (e
->callee
) > allowed_growth
)
1597 "Not inlining: code size would grow by %i.\n",
1598 cgraph_estimate_size_after_inlining (1, e
->caller
,
1600 - e
->caller
->global
.size
);
1603 if (!cgraph_check_inline_limits (node
, e
->callee
, &e
->inline_failed
,
1605 || e
->call_stmt_cannot_inline_p
)
1608 fprintf (dump_file
, "Not inlining: %s.\n",
1609 cgraph_inline_failed_string (e
->inline_failed
));
1612 if (!e
->callee
->analyzed
)
1616 "Not inlining: Function body no longer available.\n");
1619 if (!tree_can_inline_p (e
))
1623 "Not inlining: %s.",
1624 cgraph_inline_failed_string (e
->inline_failed
));
1627 if (cgraph_default_inline_p (e
->callee
, &failed_reason
))
1630 fprintf (dump_file
, " Inlining %s into %s.\n",
1631 cgraph_node_name (e
->callee
),
1632 cgraph_node_name (e
->caller
));
1633 cgraph_mark_inline (e
);
1637 BITMAP_FREE (visited
);
1642 /* Because inlining might remove no-longer reachable nodes, we need to
1643 keep the array visible to garbage collector to avoid reading collected
1646 static GTY ((length ("nnodes"))) struct cgraph_node
**order
;
1648 /* Do inlining of small functions. Doing so early helps profiling and other
1649 passes to be somewhat more effective and avoids some code duplication in
1650 later real inlining pass for testcases with very many function calls. */
1652 cgraph_early_inlining (void)
1654 struct cgraph_node
*node
= cgraph_node (current_function_decl
);
1655 unsigned int todo
= 0;
1658 if (sorrycount
|| errorcount
)
1663 || !flag_early_inlining
)
1665 /* When not optimizing or not inlining inline only always-inline
1667 cgraph_decide_inlining_incrementally (node
, INLINE_ALWAYS_INLINE
);
1668 timevar_push (TV_INTEGRATION
);
1669 todo
|= optimize_inline_calls (current_function_decl
);
1670 timevar_pop (TV_INTEGRATION
);
1674 if (lookup_attribute ("flatten",
1675 DECL_ATTRIBUTES (node
->decl
)) != NULL
)
1679 "Flattening %s\n", cgraph_node_name (node
));
1680 cgraph_flatten (node
);
1681 timevar_push (TV_INTEGRATION
);
1682 todo
|= optimize_inline_calls (current_function_decl
);
1683 timevar_pop (TV_INTEGRATION
);
1685 /* We iterate incremental inlining to get trivial cases of indirect
1687 while (iterations
< PARAM_VALUE (PARAM_EARLY_INLINER_MAX_ITERATIONS
)
1688 && cgraph_decide_inlining_incrementally (node
,
1690 ? INLINE_SIZE_NORECURSIVE
1693 timevar_push (TV_INTEGRATION
);
1694 todo
|= optimize_inline_calls (current_function_decl
);
1696 timevar_pop (TV_INTEGRATION
);
1699 fprintf (dump_file
, "Iterations: %i\n", iterations
);
1702 cfun
->always_inline_functions_inlined
= true;
1707 struct gimple_opt_pass pass_early_inline
=
1711 "einline", /* name */
1713 cgraph_early_inlining
, /* execute */
1716 0, /* static_pass_number */
1717 TV_INLINE_HEURISTICS
, /* tv_id */
1718 0, /* properties_required */
1719 0, /* properties_provided */
1720 0, /* properties_destroyed */
1721 0, /* todo_flags_start */
1722 TODO_dump_func
/* todo_flags_finish */
1726 /* When inlining shall be performed. */
1728 cgraph_gate_ipa_early_inlining (void)
1730 return (flag_early_inlining
1732 && (flag_branch_probabilities
|| flag_test_coverage
1733 || profile_arc_flag
));
1736 /* IPA pass wrapper for early inlining pass. We need to run early inlining
1737 before tree profiling so we have stand alone IPA pass for doing so. */
1738 struct simple_ipa_opt_pass pass_ipa_early_inline
=
1742 "einline_ipa", /* name */
1743 cgraph_gate_ipa_early_inlining
, /* gate */
1747 0, /* static_pass_number */
1748 TV_INLINE_HEURISTICS
, /* tv_id */
1749 0, /* properties_required */
1750 0, /* properties_provided */
1751 0, /* properties_destroyed */
1752 0, /* todo_flags_start */
1753 TODO_dump_cgraph
/* todo_flags_finish */
1757 /* See if statement might disappear after inlining. We are not terribly
1758 sophisficated, basically looking for simple abstraction penalty wrappers. */
1761 likely_eliminated_by_inlining_p (gimple stmt
)
1763 enum gimple_code code
= gimple_code (stmt
);
1769 if (gimple_num_ops (stmt
) != 2)
1772 /* Casts of parameters, loads from parameters passed by reference
1773 and stores to return value or parameters are probably free after
1775 if (gimple_assign_rhs_code (stmt
) == CONVERT_EXPR
1776 || gimple_assign_rhs_code (stmt
) == NOP_EXPR
1777 || gimple_assign_rhs_code (stmt
) == VIEW_CONVERT_EXPR
1778 || gimple_assign_rhs_class (stmt
) == GIMPLE_SINGLE_RHS
)
1780 tree rhs
= gimple_assign_rhs1 (stmt
);
1781 tree lhs
= gimple_assign_lhs (stmt
);
1782 tree inner_rhs
= rhs
;
1783 tree inner_lhs
= lhs
;
1784 bool rhs_free
= false;
1785 bool lhs_free
= false;
1787 while (handled_component_p (inner_lhs
) || TREE_CODE (inner_lhs
) == INDIRECT_REF
)
1788 inner_lhs
= TREE_OPERAND (inner_lhs
, 0);
1789 while (handled_component_p (inner_rhs
)
1790 || TREE_CODE (inner_rhs
) == ADDR_EXPR
|| TREE_CODE (inner_rhs
) == INDIRECT_REF
)
1791 inner_rhs
= TREE_OPERAND (inner_rhs
, 0);
1794 if (TREE_CODE (inner_rhs
) == PARM_DECL
1795 || (TREE_CODE (inner_rhs
) == SSA_NAME
1796 && SSA_NAME_IS_DEFAULT_DEF (inner_rhs
)
1797 && TREE_CODE (SSA_NAME_VAR (inner_rhs
)) == PARM_DECL
))
1799 if (rhs_free
&& is_gimple_reg (lhs
))
1801 if (((TREE_CODE (inner_lhs
) == PARM_DECL
1802 || (TREE_CODE (inner_lhs
) == SSA_NAME
1803 && SSA_NAME_IS_DEFAULT_DEF (inner_lhs
)
1804 && TREE_CODE (SSA_NAME_VAR (inner_lhs
)) == PARM_DECL
))
1805 && inner_lhs
!= lhs
)
1806 || TREE_CODE (inner_lhs
) == RESULT_DECL
1807 || (TREE_CODE (inner_lhs
) == SSA_NAME
1808 && TREE_CODE (SSA_NAME_VAR (inner_lhs
)) == RESULT_DECL
))
1810 if (lhs_free
&& (is_gimple_reg (rhs
) || is_gimple_min_invariant (rhs
)))
1812 if (lhs_free
&& rhs_free
)
1821 /* Compute function body size parameters for NODE. */
1824 estimate_function_body_sizes (struct cgraph_node
*node
)
1827 gcov_type time_inlining_benefit
= 0;
1829 int size_inlining_benefit
= 0;
1831 gimple_stmt_iterator bsi
;
1832 struct function
*my_function
= DECL_STRUCT_FUNCTION (node
->decl
);
1835 tree funtype
= TREE_TYPE (node
->decl
);
1837 if (node
->local
.disregard_inline_limits
)
1839 inline_summary (node
)->self_time
= 0;
1840 inline_summary (node
)->self_size
= 0;
1841 inline_summary (node
)->time_inlining_benefit
= 0;
1842 inline_summary (node
)->size_inlining_benefit
= 0;
1846 fprintf (dump_file
, "Analyzing function body size: %s\n",
1847 cgraph_node_name (node
));
1849 gcc_assert (my_function
&& my_function
->cfg
);
1850 FOR_EACH_BB_FN (bb
, my_function
)
1852 freq
= compute_call_stmt_bb_frequency (node
->decl
, bb
);
1853 for (bsi
= gsi_start_bb (bb
); !gsi_end_p (bsi
); gsi_next (&bsi
))
1855 gimple stmt
= gsi_stmt (bsi
);
1856 int this_size
= estimate_num_insns (stmt
, &eni_size_weights
);
1857 int this_time
= estimate_num_insns (stmt
, &eni_time_weights
);
1859 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1861 fprintf (dump_file
, " freq:%6i size:%3i time:%3i ",
1862 freq
, this_size
, this_time
);
1863 print_gimple_stmt (dump_file
, stmt
, 0, 0);
1868 if (likely_eliminated_by_inlining_p (stmt
))
1870 size_inlining_benefit
+= this_size
;
1871 time_inlining_benefit
+= this_time
;
1872 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1873 fprintf (dump_file
, " Likely eliminated\n");
1875 gcc_assert (time
>= 0);
1876 gcc_assert (size
>= 0);
1879 time
= (time
+ CGRAPH_FREQ_BASE
/ 2) / CGRAPH_FREQ_BASE
;
1880 time_inlining_benefit
= ((time_inlining_benefit
+ CGRAPH_FREQ_BASE
/ 2)
1881 / CGRAPH_FREQ_BASE
);
1883 fprintf (dump_file
, "Overall function body time: %i-%i size: %i-%i\n",
1884 (int)time
, (int)time_inlining_benefit
,
1885 size
, size_inlining_benefit
);
1886 time_inlining_benefit
+= eni_time_weights
.call_cost
;
1887 size_inlining_benefit
+= eni_size_weights
.call_cost
;
1888 if (!VOID_TYPE_P (TREE_TYPE (funtype
)))
1890 int cost
= estimate_move_cost (TREE_TYPE (funtype
));
1891 time_inlining_benefit
+= cost
;
1892 size_inlining_benefit
+= cost
;
1894 for (arg
= DECL_ARGUMENTS (node
->decl
); arg
; arg
= TREE_CHAIN (arg
))
1895 if (!VOID_TYPE_P (TREE_TYPE (arg
)))
1897 int cost
= estimate_move_cost (TREE_TYPE (arg
));
1898 time_inlining_benefit
+= cost
;
1899 size_inlining_benefit
+= cost
;
1901 if (time_inlining_benefit
> MAX_TIME
)
1902 time_inlining_benefit
= MAX_TIME
;
1903 if (time
> MAX_TIME
)
1905 inline_summary (node
)->self_time
= time
;
1906 inline_summary (node
)->self_size
= size
;
1908 fprintf (dump_file
, "With function call overhead time: %i-%i size: %i-%i\n",
1909 (int)time
, (int)time_inlining_benefit
,
1910 size
, size_inlining_benefit
);
1911 inline_summary (node
)->time_inlining_benefit
= time_inlining_benefit
;
1912 inline_summary (node
)->size_inlining_benefit
= size_inlining_benefit
;
1915 /* Compute parameters of functions used by inliner. */
1917 compute_inline_parameters (struct cgraph_node
*node
)
1919 HOST_WIDE_INT self_stack_size
;
1921 gcc_assert (!node
->global
.inlined_to
);
1923 /* Estimate the stack size for the function. But not at -O0
1924 because estimated_stack_frame_size is a quadratic problem. */
1925 self_stack_size
= optimize
? estimated_stack_frame_size () : 0;
1926 inline_summary (node
)->estimated_self_stack_size
= self_stack_size
;
1927 node
->global
.estimated_stack_size
= self_stack_size
;
1928 node
->global
.stack_frame_offset
= 0;
1930 /* Can this function be inlined at all? */
1931 node
->local
.inlinable
= tree_inlinable_function_p (node
->decl
);
1932 if (node
->local
.inlinable
&& !node
->local
.disregard_inline_limits
)
1933 node
->local
.disregard_inline_limits
1934 = DECL_DISREGARD_INLINE_LIMITS (node
->decl
);
1935 estimate_function_body_sizes (node
);
1936 /* Inlining characteristics are maintained by the cgraph_mark_inline. */
1937 node
->global
.time
= inline_summary (node
)->self_time
;
1938 node
->global
.size
= inline_summary (node
)->self_size
;
1943 /* Compute parameters of functions used by inliner using
1944 current_function_decl. */
1946 compute_inline_parameters_for_current (void)
1948 compute_inline_parameters (cgraph_node (current_function_decl
));
1952 struct gimple_opt_pass pass_inline_parameters
=
1956 "inline_param", /* name */
1958 compute_inline_parameters_for_current
,/* execute */
1961 0, /* static_pass_number */
1962 TV_INLINE_HEURISTICS
, /* tv_id */
1963 0, /* properties_required */
1964 0, /* properties_provided */
1965 0, /* properties_destroyed */
1966 0, /* todo_flags_start */
1967 0 /* todo_flags_finish */
1971 /* This function performs intraprocedural analyzis in NODE that is required to
1972 inline indirect calls. */
1974 inline_indirect_intraprocedural_analysis (struct cgraph_node
*node
)
1976 struct cgraph_edge
*cs
;
1980 ipa_initialize_node_params (node
);
1981 ipa_detect_param_modifications (node
);
1983 ipa_analyze_params_uses (node
);
1986 for (cs
= node
->callees
; cs
; cs
= cs
->next_callee
)
1988 ipa_count_arguments (cs
);
1989 ipa_compute_jump_functions (cs
);
1994 ipa_print_node_params (dump_file
, node
);
1995 ipa_print_node_jump_functions (dump_file
, node
);
1999 /* Note function body size. */
2001 analyze_function (struct cgraph_node
*node
)
2003 push_cfun (DECL_STRUCT_FUNCTION (node
->decl
));
2004 current_function_decl
= node
->decl
;
2006 compute_inline_parameters (node
);
2007 if (flag_indirect_inlining
)
2008 inline_indirect_intraprocedural_analysis (node
);
2010 current_function_decl
= NULL
;
2014 /* Called when new function is inserted to callgraph late. */
2016 add_new_function (struct cgraph_node
*node
, void *data ATTRIBUTE_UNUSED
)
2018 analyze_function (node
);
2021 /* Note function body size. */
2023 inline_generate_summary (void)
2025 struct cgraph_node
*node
;
2027 function_insertion_hook_holder
=
2028 cgraph_add_function_insertion_hook (&add_new_function
, NULL
);
2030 if (flag_indirect_inlining
)
2032 ipa_register_cgraph_hooks ();
2033 ipa_check_create_node_params ();
2034 ipa_check_create_edge_args ();
2037 for (node
= cgraph_nodes
; node
; node
= node
->next
)
2039 analyze_function (node
);
2044 /* Apply inline plan to function. */
2046 inline_transform (struct cgraph_node
*node
)
2048 unsigned int todo
= 0;
2049 struct cgraph_edge
*e
;
2051 /* FIXME: Currently the passmanager is adding inline transform more than once to some
2052 clones. This needs revisiting after WPA cleanups. */
2053 if (cfun
->after_inlining
)
2056 /* We might need the body of this function so that we can expand
2057 it inline somewhere else. */
2058 if (cgraph_preserve_function_body_p (node
->decl
))
2059 save_inline_function_body (node
);
2061 for (e
= node
->callees
; e
; e
= e
->next_callee
)
2062 if (!e
->inline_failed
|| warn_inline
)
2067 timevar_push (TV_INTEGRATION
);
2068 todo
= optimize_inline_calls (current_function_decl
);
2069 timevar_pop (TV_INTEGRATION
);
2071 cfun
->always_inline_functions_inlined
= true;
2072 cfun
->after_inlining
= true;
2073 return todo
| execute_fixup_cfg ();
2076 /* Read inline summary. Jump functions are shared among ipa-cp
2077 and inliner, so when ipa-cp is active, we don't need to write them
2081 inline_read_summary (void)
2083 if (flag_indirect_inlining
)
2085 ipa_register_cgraph_hooks ();
2087 ipa_prop_read_jump_functions ();
2089 function_insertion_hook_holder
=
2090 cgraph_add_function_insertion_hook (&add_new_function
, NULL
);
2093 /* Write inline summary for node in SET.
2094 Jump functions are shared among ipa-cp and inliner, so when ipa-cp is
2095 active, we don't need to write them twice. */
2098 inline_write_summary (cgraph_node_set set
)
2100 if (flag_indirect_inlining
&& !flag_ipa_cp
)
2101 ipa_prop_write_jump_functions (set
);
2104 /* When to run IPA inlining. Inlining of always-inline functions
2105 happens during early inlining. */
2108 gate_cgraph_decide_inlining (void)
2110 /* ??? We'd like to skip this if not optimizing or not inlining as
2111 all always-inline functions have been processed by early
2112 inlining already. But this at least breaks EH with C++ as
2113 we need to unconditionally run fixup_cfg even at -O0.
2114 So leave it on unconditionally for now. */
2118 struct ipa_opt_pass_d pass_ipa_inline
=
2122 "inline", /* name */
2123 gate_cgraph_decide_inlining
, /* gate */
2124 cgraph_decide_inlining
, /* execute */
2127 0, /* static_pass_number */
2128 TV_INLINE_HEURISTICS
, /* tv_id */
2129 0, /* properties_required */
2130 0, /* properties_provided */
2131 0, /* properties_destroyed */
2132 TODO_remove_functions
, /* todo_flags_finish */
2133 TODO_dump_cgraph
| TODO_dump_func
2134 | TODO_remove_functions
/* todo_flags_finish */
2136 inline_generate_summary
, /* generate_summary */
2137 inline_write_summary
, /* write_summary */
2138 inline_read_summary
, /* read_summary */
2139 NULL
, /* write_optimization_summary */
2140 NULL
, /* read_optimization_summary */
2141 lto_ipa_fixup_call_notes
, /* stmt_fixup */
2143 inline_transform
, /* function_transform */
2144 NULL
, /* variable_transform */
2148 #include "gt-ipa-inline.h"