1 /* Inlining decision heuristics.
2 Copyright (C) 2003, 2004, 2007, 2008, 2009, 2010
3 Free Software Foundation, Inc.
4 Contributed by Jan Hubicka
6 This file is part of GCC.
8 GCC is free software; you can redistribute it and/or modify it under
9 the terms of the GNU General Public License as published by the Free
10 Software Foundation; either version 3, or (at your option) any later
13 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
14 WARRANTY; without even the implied warranty of MERCHANTABILITY or
15 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
18 You should have received a copy of the GNU General Public License
19 along with GCC; see the file COPYING3. If not see
20 <http://www.gnu.org/licenses/>. */
22 /* Inlining decision heuristics
24 We separate inlining decisions from the inliner itself and store it
25 inside callgraph as so called inline plan. Refer to cgraph.c
26 documentation about particular representation of inline plans in the
29 There are three major parts of this file:
31 cgraph_mark_inline implementation
33 This function allows to mark given call inline and performs necessary
34 modifications of cgraph (production of the clones and updating overall
37 inlining heuristics limits
39 These functions allow to check that particular inlining is allowed
40 by the limits specified by user (allowed function growth, overall unit
45 This is implementation of IPA pass aiming to get as much of benefit
46 from inlining obeying the limits checked above.
48 The implementation of particular heuristics is separated from
49 the rest of code to make it easier to replace it with more complicated
50 implementation in the future. The rest of inlining code acts as a
51 library aimed to modify the callgraph and verify that the parameters
52 on code size growth fits.
54 To mark given call inline, use cgraph_mark_inline function, the
55 verification is performed by cgraph_default_inline_p and
56 cgraph_check_inline_limits.
58 The heuristics implements simple knapsack style algorithm ordering
59 all functions by their "profitability" (estimated by code size growth)
60 and inlining them in priority order.
62 cgraph_decide_inlining implements heuristics taking whole callgraph
63 into account, while cgraph_decide_inlining_incrementally considers
64 only one function at a time and is used by early inliner.
66 The inliner itself is split into several passes:
68 pass_inline_parameters
70 This pass computes local properties of functions that are used by inliner:
71 estimated function body size, whether function is inlinable at all and
72 stack frame consumption.
74 Before executing any of inliner passes, this local pass has to be applied
75 to each function in the callgraph (ie run as subpass of some earlier
76 IPA pass). The results are made out of date by any optimization applied
81 Simple local inlining pass inlining callees into current function. This
82 pass makes no global whole compilation unit analysis and this when allowed
83 to do inlining expanding code size it might result in unbounded growth of
86 The pass is run during conversion into SSA form. Only functions already
87 converted into SSA form are inlined, so the conversion must happen in
88 topological order on the callgraph (that is maintained by pass manager).
89 The functions after inlining are early optimized so the early inliner sees
90 unoptimized function itself, but all considered callees are already
91 optimized allowing it to unfold abstraction penalty on C++ effectively and
94 pass_ipa_early_inlining
96 With profiling, the early inlining is also necessary to reduce
97 instrumentation costs on program with high abstraction penalty (doing
98 many redundant calls). This can't happen in parallel with early
99 optimization and profile instrumentation, because we would end up
100 re-instrumenting already instrumented function bodies we brought in via
103 To avoid this, this pass is executed as IPA pass before profiling. It is
104 simple wrapper to pass_early_inlining and ensures first inlining.
108 This is the main pass implementing simple greedy algorithm to do inlining
109 of small functions that results in overall growth of compilation unit and
110 inlining of functions called once. The pass compute just so called inline
111 plan (representation of inlining to be done in callgraph) and unlike early
112 inlining it is not performing the inlining itself.
116 This pass performs actual inlining according to pass_ipa_inline on given
117 function. Possible the function body before inlining is saved when it is
118 needed for further inlining later.
123 #include "coretypes.h"
126 #include "tree-inline.h"
127 #include "langhooks.h"
130 #include "diagnostic.h"
135 #include "tree-pass.h"
137 #include "coverage.h"
139 #include "tree-flow.h"
141 #include "ipa-prop.h"
144 #define MAX_TIME 1000000000
146 /* Mode incremental inliner operate on:
148 In ALWAYS_INLINE only functions marked
149 always_inline are inlined. This mode is used after detecting cycle during
152 In SIZE mode, only functions that reduce function body size after inlining
153 are inlined, this is used during early inlining.
155 in ALL mode, everything is inlined. This is used during flattening. */
158 INLINE_ALWAYS_INLINE
,
159 INLINE_SIZE_NORECURSIVE
,
165 cgraph_decide_inlining_incrementally (struct cgraph_node
*, enum inlining_mode
);
166 static void cgraph_flatten (struct cgraph_node
*node
);
169 /* Statistics we collect about inlining algorithm. */
170 static int ncalls_inlined
;
171 static int nfunctions_inlined
;
172 static int overall_size
;
173 static gcov_type max_count
, max_benefit
;
175 /* Holders of ipa cgraph hooks: */
176 static struct cgraph_node_hook_list
*function_insertion_hook_holder
;
178 static inline struct inline_summary
*
179 inline_summary (struct cgraph_node
*node
)
181 return &node
->local
.inline_summary
;
184 /* Estimate self time of the function after inlining WHAT into TO. */
187 cgraph_estimate_time_after_inlining (int frequency
, struct cgraph_node
*to
,
188 struct cgraph_node
*what
)
190 gcov_type time
= (((gcov_type
)what
->global
.time
191 - inline_summary (what
)->time_inlining_benefit
)
192 * frequency
+ CGRAPH_FREQ_BASE
/ 2) / CGRAPH_FREQ_BASE
201 /* Estimate self time of the function after inlining WHAT into TO. */
204 cgraph_estimate_size_after_inlining (int times
, struct cgraph_node
*to
,
205 struct cgraph_node
*what
)
207 int size
= (what
->global
.size
- inline_summary (what
)->size_inlining_benefit
) * times
+ to
->global
.size
;
208 gcc_assert (size
>= 0);
212 /* Scale frequency of NODE edges by FREQ_SCALE and increase loop nest
216 update_noncloned_frequencies (struct cgraph_node
*node
,
217 int freq_scale
, int nest
)
219 struct cgraph_edge
*e
;
221 /* We do not want to ignore high loop nest after freq drops to 0. */
224 for (e
= node
->callees
; e
; e
= e
->next_callee
)
226 e
->loop_nest
+= nest
;
227 e
->frequency
= e
->frequency
* (gcov_type
) freq_scale
/ CGRAPH_FREQ_BASE
;
228 if (e
->frequency
> CGRAPH_FREQ_MAX
)
229 e
->frequency
= CGRAPH_FREQ_MAX
;
230 if (!e
->inline_failed
)
231 update_noncloned_frequencies (e
->callee
, freq_scale
, nest
);
235 /* E is expected to be an edge being inlined. Clone destination node of
236 the edge and redirect it to the new clone.
237 DUPLICATE is used for bookkeeping on whether we are actually creating new
238 clones or re-using node originally representing out-of-line function call.
241 cgraph_clone_inlined_nodes (struct cgraph_edge
*e
, bool duplicate
,
242 bool update_original
)
248 /* We may eliminate the need for out-of-line copy to be output.
249 In that case just go ahead and re-use it. */
250 if (!e
->callee
->callers
->next_caller
251 && cgraph_can_remove_if_no_direct_calls_p (e
->callee
)
252 /* Don't reuse if more than one function shares a comdat group.
253 If the other function(s) are needed, we need to emit even
254 this function out of line. */
255 && !e
->callee
->same_comdat_group
256 && !cgraph_new_nodes
)
258 gcc_assert (!e
->callee
->global
.inlined_to
);
259 if (e
->callee
->analyzed
)
261 overall_size
-= e
->callee
->global
.size
;
262 nfunctions_inlined
++;
265 e
->callee
->local
.externally_visible
= false;
266 update_noncloned_frequencies (e
->callee
, e
->frequency
, e
->loop_nest
);
270 struct cgraph_node
*n
;
271 n
= cgraph_clone_node (e
->callee
, e
->count
, e
->frequency
, e
->loop_nest
,
272 update_original
, NULL
);
273 cgraph_redirect_edge_callee (e
, n
);
277 if (e
->caller
->global
.inlined_to
)
278 e
->callee
->global
.inlined_to
= e
->caller
->global
.inlined_to
;
280 e
->callee
->global
.inlined_to
= e
->caller
;
281 e
->callee
->global
.stack_frame_offset
282 = e
->caller
->global
.stack_frame_offset
283 + inline_summary (e
->caller
)->estimated_self_stack_size
;
284 peak
= e
->callee
->global
.stack_frame_offset
285 + inline_summary (e
->callee
)->estimated_self_stack_size
;
286 if (e
->callee
->global
.inlined_to
->global
.estimated_stack_size
< peak
)
287 e
->callee
->global
.inlined_to
->global
.estimated_stack_size
= peak
;
289 /* Recursively clone all bodies. */
290 for (e
= e
->callee
->callees
; e
; e
= e
->next_callee
)
291 if (!e
->inline_failed
)
292 cgraph_clone_inlined_nodes (e
, duplicate
, update_original
);
295 /* Mark edge E as inlined and update callgraph accordingly. UPDATE_ORIGINAL
296 specify whether profile of original function should be updated. If any new
297 indirect edges are discovered in the process, add them to NEW_EDGES, unless
298 it is NULL. Return true iff any new callgraph edges were discovered as a
299 result of inlining. */
302 cgraph_mark_inline_edge (struct cgraph_edge
*e
, bool update_original
,
303 VEC (cgraph_edge_p
, heap
) **new_edges
)
305 int old_size
= 0, new_size
= 0;
306 struct cgraph_node
*to
= NULL
, *what
;
307 struct cgraph_edge
*curr
= e
;
310 gcc_assert (e
->inline_failed
);
311 e
->inline_failed
= CIF_OK
;
313 if (!e
->callee
->global
.inlined
)
314 DECL_POSSIBLY_INLINED (e
->callee
->decl
) = true;
315 e
->callee
->global
.inlined
= true;
317 cgraph_clone_inlined_nodes (e
, true, update_original
);
322 /* Now update size of caller and all functions caller is inlined into. */
323 for (;e
&& !e
->inline_failed
; e
= e
->caller
->callers
)
326 old_size
= e
->caller
->global
.size
;
327 new_size
= cgraph_estimate_size_after_inlining (1, to
, what
);
328 to
->global
.size
= new_size
;
329 to
->global
.time
= cgraph_estimate_time_after_inlining (freq
, to
, what
);
331 gcc_assert (what
->global
.inlined_to
== to
);
332 if (new_size
> old_size
)
333 overall_size
+= new_size
- old_size
;
336 if (flag_indirect_inlining
)
337 return ipa_propagate_indirect_call_infos (curr
, new_edges
);
342 /* Mark all calls of EDGE->CALLEE inlined into EDGE->CALLER. */
345 cgraph_mark_inline (struct cgraph_edge
*edge
)
347 struct cgraph_node
*to
= edge
->caller
;
348 struct cgraph_node
*what
= edge
->callee
;
349 struct cgraph_edge
*e
, *next
;
351 gcc_assert (!edge
->call_stmt_cannot_inline_p
);
352 /* Look for all calls, mark them inline and clone recursively
353 all inlined functions. */
354 for (e
= what
->callers
; e
; e
= next
)
356 next
= e
->next_caller
;
357 if (e
->caller
== to
&& e
->inline_failed
)
359 cgraph_mark_inline_edge (e
, true, NULL
);
366 /* Estimate the growth caused by inlining NODE into all callees. */
369 cgraph_estimate_growth (struct cgraph_node
*node
)
372 struct cgraph_edge
*e
;
373 bool self_recursive
= false;
375 if (node
->global
.estimated_growth
!= INT_MIN
)
376 return node
->global
.estimated_growth
;
378 for (e
= node
->callers
; e
; e
= e
->next_caller
)
380 if (e
->caller
== node
)
381 self_recursive
= true;
382 if (e
->inline_failed
)
383 growth
+= (cgraph_estimate_size_after_inlining (1, e
->caller
, node
)
384 - e
->caller
->global
.size
);
387 /* ??? Wrong for non-trivially self recursive functions or cases where
388 we decide to not inline for different reasons, but it is not big deal
389 as in that case we will keep the body around, but we will also avoid
391 if (cgraph_only_called_directly_p (node
)
392 && !DECL_EXTERNAL (node
->decl
) && !self_recursive
)
393 growth
-= node
->global
.size
;
395 node
->global
.estimated_growth
= growth
;
399 /* Return false when inlining WHAT into TO is not good idea
400 as it would cause too large growth of function bodies.
401 When ONE_ONLY is true, assume that only one call site is going
402 to be inlined, otherwise figure out how many call sites in
403 TO calls WHAT and verify that all can be inlined.
407 cgraph_check_inline_limits (struct cgraph_node
*to
, struct cgraph_node
*what
,
408 cgraph_inline_failed_t
*reason
, bool one_only
)
411 struct cgraph_edge
*e
;
414 HOST_WIDE_INT stack_size_limit
, inlined_stack
;
419 for (e
= to
->callees
; e
; e
= e
->next_callee
)
420 if (e
->callee
== what
)
423 if (to
->global
.inlined_to
)
424 to
= to
->global
.inlined_to
;
426 /* When inlining large function body called once into small function,
427 take the inlined function as base for limiting the growth. */
428 if (inline_summary (to
)->self_size
> inline_summary(what
)->self_size
)
429 limit
= inline_summary (to
)->self_size
;
431 limit
= inline_summary (what
)->self_size
;
433 limit
+= limit
* PARAM_VALUE (PARAM_LARGE_FUNCTION_GROWTH
) / 100;
435 /* Check the size after inlining against the function limits. But allow
436 the function to shrink if it went over the limits by forced inlining. */
437 newsize
= cgraph_estimate_size_after_inlining (times
, to
, what
);
438 if (newsize
>= to
->global
.size
439 && newsize
> PARAM_VALUE (PARAM_LARGE_FUNCTION_INSNS
)
443 *reason
= CIF_LARGE_FUNCTION_GROWTH_LIMIT
;
447 stack_size_limit
= inline_summary (to
)->estimated_self_stack_size
;
449 stack_size_limit
+= stack_size_limit
* PARAM_VALUE (PARAM_STACK_FRAME_GROWTH
) / 100;
451 inlined_stack
= (to
->global
.stack_frame_offset
452 + inline_summary (to
)->estimated_self_stack_size
453 + what
->global
.estimated_stack_size
);
454 if (inlined_stack
> stack_size_limit
455 && inlined_stack
> PARAM_VALUE (PARAM_LARGE_STACK_FRAME
))
458 *reason
= CIF_LARGE_STACK_FRAME_GROWTH_LIMIT
;
464 /* Return true when function N is small enough to be inlined. */
467 cgraph_default_inline_p (struct cgraph_node
*n
, cgraph_inline_failed_t
*reason
)
471 if (n
->local
.disregard_inline_limits
)
474 if (!flag_inline_small_functions
&& !DECL_DECLARED_INLINE_P (decl
))
477 *reason
= CIF_FUNCTION_NOT_INLINE_CANDIDATE
;
484 *reason
= CIF_BODY_NOT_AVAILABLE
;
488 if (DECL_DECLARED_INLINE_P (decl
))
490 if (n
->global
.size
>= MAX_INLINE_INSNS_SINGLE
)
493 *reason
= CIF_MAX_INLINE_INSNS_SINGLE_LIMIT
;
499 if (n
->global
.size
>= MAX_INLINE_INSNS_AUTO
)
502 *reason
= CIF_MAX_INLINE_INSNS_AUTO_LIMIT
;
510 /* Return true when inlining WHAT would create recursive inlining.
511 We call recursive inlining all cases where same function appears more than
512 once in the single recursion nest path in the inline graph. */
515 cgraph_recursive_inlining_p (struct cgraph_node
*to
,
516 struct cgraph_node
*what
,
517 cgraph_inline_failed_t
*reason
)
520 if (to
->global
.inlined_to
)
521 recursive
= what
->decl
== to
->global
.inlined_to
->decl
;
523 recursive
= what
->decl
== to
->decl
;
524 /* Marking recursive function inline has sane semantic and thus we should
526 if (recursive
&& reason
)
527 *reason
= (what
->local
.disregard_inline_limits
528 ? CIF_RECURSIVE_INLINING
: CIF_UNSPECIFIED
);
532 /* A cost model driving the inlining heuristics in a way so the edges with
533 smallest badness are inlined first. After each inlining is performed
534 the costs of all caller edges of nodes affected are recomputed so the
535 metrics may accurately depend on values such as number of inlinable callers
536 of the function or function body size. */
539 cgraph_edge_badness (struct cgraph_edge
*edge
, bool dump
)
543 (cgraph_estimate_size_after_inlining (1, edge
->caller
, edge
->callee
)
544 - edge
->caller
->global
.size
);
548 fprintf (dump_file
, " Badness calculcation for %s -> %s\n",
549 cgraph_node_name (edge
->caller
),
550 cgraph_node_name (edge
->callee
));
551 fprintf (dump_file
, " growth %i, time %i-%i, size %i-%i\n",
553 edge
->callee
->global
.time
,
554 inline_summary (edge
->callee
)->time_inlining_benefit
,
555 edge
->callee
->global
.size
,
556 inline_summary (edge
->callee
)->size_inlining_benefit
);
559 /* Always prefer inlining saving code size. */
562 badness
= INT_MIN
- growth
;
564 fprintf (dump_file
, " %i: Growth %i < 0\n", (int) badness
,
568 /* When profiling is available, base priorities -(#calls / growth).
569 So we optimize for overall number of "executed" inlined calls. */
574 ((double) edge
->count
* INT_MIN
/ max_count
/ (max_benefit
+ 1)) *
575 (inline_summary (edge
->callee
)->time_inlining_benefit
+ 1)) / growth
;
579 " %i (relative %f): profile info. Relative count %f"
580 " * Relative benefit %f\n",
581 (int) badness
, (double) badness
/ INT_MIN
,
582 (double) edge
->count
/ max_count
,
583 (double) (inline_summary (edge
->callee
)->
584 time_inlining_benefit
+ 1) / (max_benefit
+ 1));
588 /* When function local profile is available, base priorities on
589 growth / frequency, so we optimize for overall frequency of inlined
590 calls. This is not too accurate since while the call might be frequent
591 within function, the function itself is infrequent.
593 Other objective to optimize for is number of different calls inlined.
594 We add the estimated growth after inlining all functions to bias the
595 priorities slightly in this direction (so fewer times called functions
596 of the same size gets priority). */
597 else if (flag_guess_branch_prob
)
599 int div
= edge
->frequency
* 100 / CGRAPH_FREQ_BASE
+ 1;
602 badness
= growth
* 10000;
604 MIN (100 * inline_summary (edge
->callee
)->time_inlining_benefit
/
605 (edge
->callee
->global
.time
+ 1) +1, 100);
609 /* Decrease badness if call is nested. */
610 /* Compress the range so we don't overflow. */
612 div
= 10000 + ceil_log2 (div
) - 8;
617 growth_for_all
= cgraph_estimate_growth (edge
->callee
);
618 badness
+= growth_for_all
;
619 if (badness
> INT_MAX
)
624 " %i: guessed profile. frequency %i, overall growth %i,"
625 " benefit %i%%, divisor %i\n",
626 (int) badness
, edge
->frequency
, growth_for_all
, benefitperc
, div
);
629 /* When function local profile is not available or it does not give
630 useful information (ie frequency is zero), base the cost on
631 loop nest and overall size growth, so we optimize for overall number
632 of functions fully inlined in program. */
635 int nest
= MIN (edge
->loop_nest
, 8);
636 badness
= cgraph_estimate_growth (edge
->callee
) * 256;
638 /* Decrease badness if call is nested. */
646 fprintf (dump_file
, " %i: no profile. nest %i\n", (int) badness
,
650 /* Ensure that we did not overflow in all the fixed point math above. */
651 gcc_assert (badness
>= INT_MIN
);
652 gcc_assert (badness
<= INT_MAX
- 1);
653 /* Make recursive inlining happen always after other inlining is done. */
654 if (cgraph_recursive_inlining_p (edge
->caller
, edge
->callee
, NULL
))
660 /* Recompute heap nodes for each of caller edge. */
663 update_caller_keys (fibheap_t heap
, struct cgraph_node
*node
,
664 bitmap updated_nodes
)
666 struct cgraph_edge
*edge
;
667 cgraph_inline_failed_t failed_reason
;
669 if (!node
->local
.inlinable
|| node
->local
.disregard_inline_limits
670 || node
->global
.inlined_to
)
672 if (bitmap_bit_p (updated_nodes
, node
->uid
))
674 bitmap_set_bit (updated_nodes
, node
->uid
);
675 node
->global
.estimated_growth
= INT_MIN
;
677 if (!node
->local
.inlinable
)
679 /* Prune out edges we won't inline into anymore. */
680 if (!cgraph_default_inline_p (node
, &failed_reason
))
682 for (edge
= node
->callers
; edge
; edge
= edge
->next_caller
)
685 fibheap_delete_node (heap
, (fibnode_t
) edge
->aux
);
687 if (edge
->inline_failed
)
688 edge
->inline_failed
= failed_reason
;
693 for (edge
= node
->callers
; edge
; edge
= edge
->next_caller
)
694 if (edge
->inline_failed
)
696 int badness
= cgraph_edge_badness (edge
, false);
699 fibnode_t n
= (fibnode_t
) edge
->aux
;
700 gcc_assert (n
->data
== edge
);
701 if (n
->key
== badness
)
704 /* fibheap_replace_key only increase the keys. */
705 if (badness
< n
->key
)
707 fibheap_replace_key (heap
, n
, badness
);
708 gcc_assert (n
->key
== badness
);
711 fibheap_delete_node (heap
, (fibnode_t
) edge
->aux
);
713 edge
->aux
= fibheap_insert (heap
, badness
, edge
);
717 /* Recompute heap nodes for each of caller edges of each of callees. */
720 update_callee_keys (fibheap_t heap
, struct cgraph_node
*node
,
721 bitmap updated_nodes
)
723 struct cgraph_edge
*e
;
724 node
->global
.estimated_growth
= INT_MIN
;
726 for (e
= node
->callees
; e
; e
= e
->next_callee
)
727 if (e
->inline_failed
)
728 update_caller_keys (heap
, e
->callee
, updated_nodes
);
729 else if (!e
->inline_failed
)
730 update_callee_keys (heap
, e
->callee
, updated_nodes
);
733 /* Enqueue all recursive calls from NODE into priority queue depending on
734 how likely we want to recursively inline the call. */
737 lookup_recursive_calls (struct cgraph_node
*node
, struct cgraph_node
*where
,
741 struct cgraph_edge
*e
;
742 for (e
= where
->callees
; e
; e
= e
->next_callee
)
743 if (e
->callee
== node
)
745 /* When profile feedback is available, prioritize by expected number
746 of calls. Without profile feedback we maintain simple queue
747 to order candidates via recursive depths. */
748 fibheap_insert (heap
,
749 !max_count
? priority
++
750 : -(e
->count
/ ((max_count
+ (1<<24) - 1) / (1<<24))),
753 for (e
= where
->callees
; e
; e
= e
->next_callee
)
754 if (!e
->inline_failed
)
755 lookup_recursive_calls (node
, e
->callee
, heap
);
758 /* Decide on recursive inlining: in the case function has recursive calls,
759 inline until body size reaches given argument. If any new indirect edges
760 are discovered in the process, add them to *NEW_EDGES, unless NEW_EDGES
764 cgraph_decide_recursive_inlining (struct cgraph_node
*node
,
765 VEC (cgraph_edge_p
, heap
) **new_edges
)
767 int limit
= PARAM_VALUE (PARAM_MAX_INLINE_INSNS_RECURSIVE_AUTO
);
768 int max_depth
= PARAM_VALUE (PARAM_MAX_INLINE_RECURSIVE_DEPTH_AUTO
);
769 int probability
= PARAM_VALUE (PARAM_MIN_INLINE_RECURSIVE_PROBABILITY
);
771 struct cgraph_edge
*e
;
772 struct cgraph_node
*master_clone
, *next
;
776 /* It does not make sense to recursively inline always-inline functions
777 as we are going to sorry() on the remaining calls anyway. */
778 if (node
->local
.disregard_inline_limits
779 && lookup_attribute ("always_inline", DECL_ATTRIBUTES (node
->decl
)))
782 if (optimize_function_for_size_p (DECL_STRUCT_FUNCTION (node
->decl
))
783 || (!flag_inline_functions
&& !DECL_DECLARED_INLINE_P (node
->decl
)))
786 if (DECL_DECLARED_INLINE_P (node
->decl
))
788 limit
= PARAM_VALUE (PARAM_MAX_INLINE_INSNS_RECURSIVE
);
789 max_depth
= PARAM_VALUE (PARAM_MAX_INLINE_RECURSIVE_DEPTH
);
792 /* Make sure that function is small enough to be considered for inlining. */
794 || cgraph_estimate_size_after_inlining (1, node
, node
) >= limit
)
796 heap
= fibheap_new ();
797 lookup_recursive_calls (node
, node
, heap
);
798 if (fibheap_empty (heap
))
800 fibheap_delete (heap
);
806 " Performing recursive inlining on %s\n",
807 cgraph_node_name (node
));
809 /* We need original clone to copy around. */
810 master_clone
= cgraph_clone_node (node
, node
->count
, CGRAPH_FREQ_BASE
, 1,
812 master_clone
->needed
= true;
813 for (e
= master_clone
->callees
; e
; e
= e
->next_callee
)
814 if (!e
->inline_failed
)
815 cgraph_clone_inlined_nodes (e
, true, false);
817 /* Do the inlining and update list of recursive call during process. */
818 while (!fibheap_empty (heap
)
819 && (cgraph_estimate_size_after_inlining (1, node
, master_clone
)
822 struct cgraph_edge
*curr
823 = (struct cgraph_edge
*) fibheap_extract_min (heap
);
824 struct cgraph_node
*cnode
;
827 for (cnode
= curr
->caller
;
828 cnode
->global
.inlined_to
; cnode
= cnode
->callers
->caller
)
829 if (node
->decl
== curr
->callee
->decl
)
831 if (depth
> max_depth
)
835 " maximal depth reached\n");
841 if (!cgraph_maybe_hot_edge_p (curr
))
844 fprintf (dump_file
, " Not inlining cold call\n");
847 if (curr
->count
* 100 / node
->count
< probability
)
851 " Probability of edge is too small\n");
859 " Inlining call of depth %i", depth
);
862 fprintf (dump_file
, " called approx. %.2f times per call",
863 (double)curr
->count
/ node
->count
);
865 fprintf (dump_file
, "\n");
867 cgraph_redirect_edge_callee (curr
, master_clone
);
868 cgraph_mark_inline_edge (curr
, false, new_edges
);
869 lookup_recursive_calls (node
, curr
->callee
, heap
);
872 if (!fibheap_empty (heap
) && dump_file
)
873 fprintf (dump_file
, " Recursive inlining growth limit met.\n");
875 fibheap_delete (heap
);
878 "\n Inlined %i times, body grown from size %i to %i, time %i to %i\n", n
,
879 master_clone
->global
.size
, node
->global
.size
,
880 master_clone
->global
.time
, node
->global
.time
);
882 /* Remove master clone we used for inlining. We rely that clones inlined
883 into master clone gets queued just before master clone so we don't
885 for (node
= cgraph_nodes
; node
!= master_clone
;
889 if (node
->global
.inlined_to
== master_clone
)
890 cgraph_remove_node (node
);
892 cgraph_remove_node (master_clone
);
893 /* FIXME: Recursive inlining actually reduces number of calls of the
894 function. At this place we should probably walk the function and
895 inline clones and compensate the counts accordingly. This probably
896 doesn't matter much in practice. */
900 /* Set inline_failed for all callers of given function to REASON. */
903 cgraph_set_inline_failed (struct cgraph_node
*node
,
904 cgraph_inline_failed_t reason
)
906 struct cgraph_edge
*e
;
909 fprintf (dump_file
, "Inlining failed: %s\n",
910 cgraph_inline_failed_string (reason
));
911 for (e
= node
->callers
; e
; e
= e
->next_caller
)
912 if (e
->inline_failed
)
913 e
->inline_failed
= reason
;
916 /* Given whole compilation unit estimate of INSNS, compute how large we can
917 allow the unit to grow. */
919 compute_max_insns (int insns
)
921 int max_insns
= insns
;
922 if (max_insns
< PARAM_VALUE (PARAM_LARGE_UNIT_INSNS
))
923 max_insns
= PARAM_VALUE (PARAM_LARGE_UNIT_INSNS
);
925 return ((HOST_WIDEST_INT
) max_insns
926 * (100 + PARAM_VALUE (PARAM_INLINE_UNIT_GROWTH
)) / 100);
929 /* Compute badness of all edges in NEW_EDGES and add them to the HEAP. */
931 add_new_edges_to_heap (fibheap_t heap
, VEC (cgraph_edge_p
, heap
) *new_edges
)
933 while (VEC_length (cgraph_edge_p
, new_edges
) > 0)
935 struct cgraph_edge
*edge
= VEC_pop (cgraph_edge_p
, new_edges
);
937 gcc_assert (!edge
->aux
);
938 edge
->aux
= fibheap_insert (heap
, cgraph_edge_badness (edge
, false), edge
);
943 /* We use greedy algorithm for inlining of small functions:
944 All inline candidates are put into prioritized heap based on estimated
945 growth of the overall number of instructions and then update the estimates.
947 INLINED and INLINED_CALEES are just pointers to arrays large enough
948 to be passed to cgraph_inlined_into and cgraph_inlined_callees. */
951 cgraph_decide_inlining_of_small_functions (void)
953 struct cgraph_node
*node
;
954 struct cgraph_edge
*edge
;
955 cgraph_inline_failed_t failed_reason
;
956 fibheap_t heap
= fibheap_new ();
957 bitmap updated_nodes
= BITMAP_ALLOC (NULL
);
958 int min_size
, max_size
;
959 VEC (cgraph_edge_p
, heap
) *new_indirect_edges
= NULL
;
961 if (flag_indirect_inlining
)
962 new_indirect_edges
= VEC_alloc (cgraph_edge_p
, heap
, 8);
965 fprintf (dump_file
, "\nDeciding on smaller functions:\n");
967 /* Put all inline candidates into the heap. */
969 for (node
= cgraph_nodes
; node
; node
= node
->next
)
971 if (!node
->local
.inlinable
|| !node
->callers
)
974 fprintf (dump_file
, "Considering inline candidate %s.\n", cgraph_node_name (node
));
976 node
->global
.estimated_growth
= INT_MIN
;
977 if (!cgraph_default_inline_p (node
, &failed_reason
))
979 cgraph_set_inline_failed (node
, failed_reason
);
983 for (edge
= node
->callers
; edge
; edge
= edge
->next_caller
)
984 if (edge
->inline_failed
)
986 gcc_assert (!edge
->aux
);
987 edge
->aux
= fibheap_insert (heap
, cgraph_edge_badness (edge
, false), edge
);
991 max_size
= compute_max_insns (overall_size
);
992 min_size
= overall_size
;
994 while (overall_size
<= max_size
995 && !fibheap_empty (heap
))
997 int old_size
= overall_size
;
998 struct cgraph_node
*where
, *callee
;
999 int badness
= fibheap_min_key (heap
);
1001 cgraph_inline_failed_t not_good
= CIF_OK
;
1003 edge
= (struct cgraph_edge
*) fibheap_extract_min (heap
);
1004 gcc_assert (edge
->aux
);
1006 if (!edge
->inline_failed
)
1008 #ifdef ENABLE_CHECKING
1009 gcc_assert (cgraph_edge_badness (edge
, false) == badness
);
1011 callee
= edge
->callee
;
1013 growth
= (cgraph_estimate_size_after_inlining (1, edge
->caller
, edge
->callee
)
1014 - edge
->caller
->global
.size
);
1019 "\nConsidering %s with %i size\n",
1020 cgraph_node_name (edge
->callee
),
1021 edge
->callee
->global
.size
);
1023 " to be inlined into %s in %s:%i\n"
1024 " Estimated growth after inlined into all callees is %+i insns.\n"
1025 " Estimated badness is %i, frequency %.2f.\n",
1026 cgraph_node_name (edge
->caller
),
1027 gimple_filename ((const_gimple
) edge
->call_stmt
),
1028 gimple_lineno ((const_gimple
) edge
->call_stmt
),
1029 cgraph_estimate_growth (edge
->callee
),
1031 edge
->frequency
/ (double)CGRAPH_FREQ_BASE
);
1033 fprintf (dump_file
," Called "HOST_WIDEST_INT_PRINT_DEC
"x\n", edge
->count
);
1034 if (dump_flags
& TDF_DETAILS
)
1035 cgraph_edge_badness (edge
, true);
1038 /* When not having profile info ready we don't weight by any way the
1039 position of call in procedure itself. This means if call of
1040 function A from function B seems profitable to inline, the recursive
1041 call of function A in inline copy of A in B will look profitable too
1042 and we end up inlining until reaching maximal function growth. This
1043 is not good idea so prohibit the recursive inlining.
1045 ??? When the frequencies are taken into account we might not need this
1048 We need to be cureful here, in some testcases, e.g. directivec.c in
1049 libcpp, we can estimate self recursive function to have negative growth
1050 for inlining completely.
1054 where
= edge
->caller
;
1055 while (where
->global
.inlined_to
)
1057 if (where
->decl
== edge
->callee
->decl
)
1059 where
= where
->callers
->caller
;
1061 if (where
->global
.inlined_to
)
1064 = (edge
->callee
->local
.disregard_inline_limits
1065 ? CIF_RECURSIVE_INLINING
: CIF_UNSPECIFIED
);
1067 fprintf (dump_file
, " inline_failed:Recursive inlining performed only for function itself.\n");
1072 if (!cgraph_maybe_hot_edge_p (edge
))
1073 not_good
= CIF_UNLIKELY_CALL
;
1074 if (!flag_inline_functions
1075 && !DECL_DECLARED_INLINE_P (edge
->callee
->decl
))
1076 not_good
= CIF_NOT_DECLARED_INLINED
;
1077 if (optimize_function_for_size_p (DECL_STRUCT_FUNCTION(edge
->caller
->decl
)))
1078 not_good
= CIF_OPTIMIZING_FOR_SIZE
;
1079 if (not_good
&& growth
> 0 && cgraph_estimate_growth (edge
->callee
) > 0)
1081 if (!cgraph_recursive_inlining_p (edge
->caller
, edge
->callee
,
1082 &edge
->inline_failed
))
1084 edge
->inline_failed
= not_good
;
1086 fprintf (dump_file
, " inline_failed:%s.\n",
1087 cgraph_inline_failed_string (edge
->inline_failed
));
1091 if (!cgraph_default_inline_p (edge
->callee
, &edge
->inline_failed
))
1093 if (!cgraph_recursive_inlining_p (edge
->caller
, edge
->callee
,
1094 &edge
->inline_failed
))
1097 fprintf (dump_file
, " inline_failed:%s.\n",
1098 cgraph_inline_failed_string (edge
->inline_failed
));
1102 if (!tree_can_inline_p (edge
))
1105 fprintf (dump_file
, " inline_failed:%s.\n",
1106 cgraph_inline_failed_string (edge
->inline_failed
));
1109 if (cgraph_recursive_inlining_p (edge
->caller
, edge
->callee
,
1110 &edge
->inline_failed
))
1112 where
= edge
->caller
;
1113 if (where
->global
.inlined_to
)
1114 where
= where
->global
.inlined_to
;
1115 if (!cgraph_decide_recursive_inlining (where
,
1116 flag_indirect_inlining
1117 ? &new_indirect_edges
: NULL
))
1119 if (flag_indirect_inlining
)
1120 add_new_edges_to_heap (heap
, new_indirect_edges
);
1121 update_callee_keys (heap
, where
, updated_nodes
);
1125 struct cgraph_node
*callee
;
1126 if (edge
->call_stmt_cannot_inline_p
1127 || !cgraph_check_inline_limits (edge
->caller
, edge
->callee
,
1128 &edge
->inline_failed
, true))
1131 fprintf (dump_file
, " Not inlining into %s:%s.\n",
1132 cgraph_node_name (edge
->caller
),
1133 cgraph_inline_failed_string (edge
->inline_failed
));
1136 callee
= edge
->callee
;
1137 cgraph_mark_inline_edge (edge
, true, &new_indirect_edges
);
1138 if (flag_indirect_inlining
)
1139 add_new_edges_to_heap (heap
, new_indirect_edges
);
1141 update_callee_keys (heap
, callee
, updated_nodes
);
1143 where
= edge
->caller
;
1144 if (where
->global
.inlined_to
)
1145 where
= where
->global
.inlined_to
;
1147 /* Our profitability metric can depend on local properties
1148 such as number of inlinable calls and size of the function body.
1149 After inlining these properties might change for the function we
1150 inlined into (since it's body size changed) and for the functions
1151 called by function we inlined (since number of it inlinable callers
1153 update_caller_keys (heap
, where
, updated_nodes
);
1155 /* We removed one call of the function we just inlined. If offline
1156 copy is still needed, be sure to update the keys. */
1157 if (callee
!= where
&& !callee
->global
.inlined_to
)
1158 update_caller_keys (heap
, callee
, updated_nodes
);
1159 bitmap_clear (updated_nodes
);
1164 " Inlined into %s which now has size %i and self time %i,"
1165 "net change of %+i.\n",
1166 cgraph_node_name (edge
->caller
),
1167 edge
->caller
->global
.time
,
1168 edge
->caller
->global
.size
,
1169 overall_size
- old_size
);
1171 if (min_size
> overall_size
)
1173 min_size
= overall_size
;
1174 max_size
= compute_max_insns (min_size
);
1177 fprintf (dump_file
, "New minimal size reached: %i\n", min_size
);
1180 while (!fibheap_empty (heap
))
1182 int badness
= fibheap_min_key (heap
);
1184 edge
= (struct cgraph_edge
*) fibheap_extract_min (heap
);
1185 gcc_assert (edge
->aux
);
1187 if (!edge
->inline_failed
)
1189 #ifdef ENABLE_CHECKING
1190 gcc_assert (cgraph_edge_badness (edge
, false) == badness
);
1195 "\nSkipping %s with %i size\n",
1196 cgraph_node_name (edge
->callee
),
1197 edge
->callee
->global
.size
);
1199 " called by %s in %s:%i\n"
1200 " Estimated growth after inlined into all callees is %+i insns.\n"
1201 " Estimated badness is %i, frequency %.2f.\n",
1202 cgraph_node_name (edge
->caller
),
1203 gimple_filename ((const_gimple
) edge
->call_stmt
),
1204 gimple_lineno ((const_gimple
) edge
->call_stmt
),
1205 cgraph_estimate_growth (edge
->callee
),
1207 edge
->frequency
/ (double)CGRAPH_FREQ_BASE
);
1209 fprintf (dump_file
," Called "HOST_WIDEST_INT_PRINT_DEC
"x\n", edge
->count
);
1210 if (dump_flags
& TDF_DETAILS
)
1211 cgraph_edge_badness (edge
, true);
1213 if (!edge
->callee
->local
.disregard_inline_limits
&& edge
->inline_failed
1214 && !cgraph_recursive_inlining_p (edge
->caller
, edge
->callee
,
1215 &edge
->inline_failed
))
1216 edge
->inline_failed
= CIF_INLINE_UNIT_GROWTH_LIMIT
;
1219 if (new_indirect_edges
)
1220 VEC_free (cgraph_edge_p
, heap
, new_indirect_edges
);
1221 fibheap_delete (heap
);
1222 BITMAP_FREE (updated_nodes
);
1225 /* Flatten NODE from the IPA inliner. */
1228 cgraph_flatten (struct cgraph_node
*node
)
1230 struct cgraph_edge
*e
;
1232 /* We shouldn't be called recursively when we are being processed. */
1233 gcc_assert (node
->aux
== NULL
);
1235 node
->aux
= (void *)(size_t) INLINE_ALL
;
1237 for (e
= node
->callees
; e
; e
= e
->next_callee
)
1239 struct cgraph_node
*orig_callee
;
1241 if (e
->call_stmt_cannot_inline_p
)
1244 if (!e
->callee
->analyzed
)
1248 "Not inlining: Function body not available.\n");
1252 /* We've hit cycle? It is time to give up. */
1257 "Not inlining %s into %s to avoid cycle.\n",
1258 cgraph_node_name (e
->callee
),
1259 cgraph_node_name (e
->caller
));
1260 e
->inline_failed
= CIF_RECURSIVE_INLINING
;
1264 /* When the edge is already inlined, we just need to recurse into
1265 it in order to fully flatten the leaves. */
1266 if (!e
->inline_failed
)
1268 cgraph_flatten (e
->callee
);
1272 if (cgraph_recursive_inlining_p (node
, e
->callee
, &e
->inline_failed
))
1275 fprintf (dump_file
, "Not inlining: recursive call.\n");
1279 if (!tree_can_inline_p (e
))
1282 fprintf (dump_file
, "Not inlining: %s",
1283 cgraph_inline_failed_string (e
->inline_failed
));
1287 /* Inline the edge and flatten the inline clone. Avoid
1288 recursing through the original node if the node was cloned. */
1290 fprintf (dump_file
, " Inlining %s into %s.\n",
1291 cgraph_node_name (e
->callee
),
1292 cgraph_node_name (e
->caller
));
1293 orig_callee
= e
->callee
;
1294 cgraph_mark_inline_edge (e
, true, NULL
);
1295 if (e
->callee
!= orig_callee
)
1296 orig_callee
->aux
= (void *)(size_t) INLINE_ALL
;
1297 cgraph_flatten (e
->callee
);
1298 if (e
->callee
!= orig_callee
)
1299 orig_callee
->aux
= NULL
;
1305 /* Decide on the inlining. We do so in the topological order to avoid
1306 expenses on updating data structures. */
1309 cgraph_decide_inlining (void)
1311 struct cgraph_node
*node
;
1313 struct cgraph_node
**order
=
1314 XCNEWVEC (struct cgraph_node
*, cgraph_n_nodes
);
1317 int initial_size
= 0;
1319 cgraph_remove_function_insertion_hook (function_insertion_hook_holder
);
1320 if (in_lto_p
&& flag_indirect_inlining
)
1321 ipa_update_after_lto_read ();
1325 for (node
= cgraph_nodes
; node
; node
= node
->next
)
1328 struct cgraph_edge
*e
;
1330 gcc_assert (inline_summary (node
)->self_size
== node
->global
.size
);
1331 initial_size
+= node
->global
.size
;
1332 for (e
= node
->callees
; e
; e
= e
->next_callee
)
1333 if (max_count
< e
->count
)
1334 max_count
= e
->count
;
1335 if (max_benefit
< inline_summary (node
)->time_inlining_benefit
)
1336 max_benefit
= inline_summary (node
)->time_inlining_benefit
;
1338 gcc_assert (in_lto_p
1340 || (profile_info
&& flag_branch_probabilities
));
1341 overall_size
= initial_size
;
1343 nnodes
= cgraph_postorder (order
);
1347 "\nDeciding on inlining. Starting with size %i.\n",
1350 for (node
= cgraph_nodes
; node
; node
= node
->next
)
1354 fprintf (dump_file
, "\nFlattening functions:\n");
1356 /* In the first pass handle functions to be flattened. Do this with
1357 a priority so none of our later choices will make this impossible. */
1358 for (i
= nnodes
- 1; i
>= 0; i
--)
1362 /* Handle nodes to be flattened, but don't update overall unit
1363 size. Calling the incremental inliner here is lame,
1364 a simple worklist should be enough. What should be left
1365 here from the early inliner (if it runs) is cyclic cases.
1366 Ideally when processing callees we stop inlining at the
1367 entry of cycles, possibly cloning that entry point and
1368 try to flatten itself turning it into a self-recursive
1370 if (lookup_attribute ("flatten",
1371 DECL_ATTRIBUTES (node
->decl
)) != NULL
)
1375 "Flattening %s\n", cgraph_node_name (node
));
1376 cgraph_flatten (node
);
1380 cgraph_decide_inlining_of_small_functions ();
1382 if (flag_inline_functions_called_once
)
1385 fprintf (dump_file
, "\nDeciding on functions called once:\n");
1387 /* And finally decide what functions are called once. */
1388 for (i
= nnodes
- 1; i
>= 0; i
--)
1393 && !node
->callers
->next_caller
1394 && cgraph_only_called_directly_p (node
)
1395 && node
->local
.inlinable
1396 && node
->callers
->inline_failed
1397 && node
->callers
->caller
!= node
1398 && node
->callers
->caller
->global
.inlined_to
!= node
1399 && !node
->callers
->call_stmt_cannot_inline_p
1400 && !DECL_EXTERNAL (node
->decl
)
1401 && !DECL_COMDAT (node
->decl
))
1403 cgraph_inline_failed_t reason
;
1404 old_size
= overall_size
;
1408 "\nConsidering %s size %i.\n",
1409 cgraph_node_name (node
), node
->global
.size
);
1411 " Called once from %s %i insns.\n",
1412 cgraph_node_name (node
->callers
->caller
),
1413 node
->callers
->caller
->global
.size
);
1416 if (cgraph_check_inline_limits (node
->callers
->caller
, node
,
1419 cgraph_mark_inline (node
->callers
);
1422 " Inlined into %s which now has %i size"
1423 " for a net change of %+i size.\n",
1424 cgraph_node_name (node
->callers
->caller
),
1425 node
->callers
->caller
->global
.size
,
1426 overall_size
- old_size
);
1432 " Not inlining: %s.\n",
1433 cgraph_inline_failed_string (reason
));
1439 /* Free ipa-prop structures if they are no longer needed. */
1440 if (flag_indirect_inlining
)
1441 free_all_ipa_structures_after_iinln ();
1445 "\nInlined %i calls, eliminated %i functions, "
1446 "size %i turned to %i size.\n\n",
1447 ncalls_inlined
, nfunctions_inlined
, initial_size
,
1453 /* Return true when N is leaf function. Accept cheap (pure&const) builtins
1454 in leaf functions. */
1456 leaf_node_p (struct cgraph_node
*n
)
1458 struct cgraph_edge
*e
;
1459 for (e
= n
->callees
; e
; e
= e
->next_callee
)
1460 if (!DECL_BUILT_IN (e
->callee
->decl
)
1461 || (!TREE_READONLY (e
->callee
->decl
)
1462 || DECL_PURE_P (e
->callee
->decl
)))
1467 /* Decide on the inlining. We do so in the topological order to avoid
1468 expenses on updating data structures. */
1471 cgraph_decide_inlining_incrementally (struct cgraph_node
*node
,
1472 enum inlining_mode mode
)
1474 struct cgraph_edge
*e
;
1475 bool inlined
= false;
1476 cgraph_inline_failed_t failed_reason
;
1478 #ifdef ENABLE_CHECKING
1479 verify_cgraph_node (node
);
1482 if (mode
!= INLINE_ALWAYS_INLINE
&& mode
!= INLINE_SIZE_NORECURSIVE
1483 && lookup_attribute ("flatten", DECL_ATTRIBUTES (node
->decl
)) != NULL
)
1486 fprintf (dump_file
, "Incrementally flattening %s\n",
1487 cgraph_node_name (node
));
1491 /* First of all look for always inline functions. */
1492 if (mode
!= INLINE_SIZE_NORECURSIVE
)
1493 for (e
= node
->callees
; e
; e
= e
->next_callee
)
1495 if (!e
->callee
->local
.disregard_inline_limits
1496 && (mode
!= INLINE_ALL
|| !e
->callee
->local
.inlinable
))
1498 if (e
->call_stmt_cannot_inline_p
)
1502 "Considering to always inline inline candidate %s.\n",
1503 cgraph_node_name (e
->callee
));
1504 if (cgraph_recursive_inlining_p (node
, e
->callee
, &e
->inline_failed
))
1507 fprintf (dump_file
, "Not inlining: recursive call.\n");
1510 if (!tree_can_inline_p (e
))
1515 cgraph_inline_failed_string (e
->inline_failed
));
1518 if (gimple_in_ssa_p (DECL_STRUCT_FUNCTION (node
->decl
))
1519 != gimple_in_ssa_p (DECL_STRUCT_FUNCTION (e
->callee
->decl
)))
1522 fprintf (dump_file
, "Not inlining: SSA form does not match.\n");
1525 if (!e
->callee
->analyzed
)
1529 "Not inlining: Function body no longer available.\n");
1534 fprintf (dump_file
, " Inlining %s into %s.\n",
1535 cgraph_node_name (e
->callee
),
1536 cgraph_node_name (e
->caller
));
1537 cgraph_mark_inline (e
);
1541 /* Now do the automatic inlining. */
1542 if (mode
!= INLINE_ALL
&& mode
!= INLINE_ALWAYS_INLINE
1543 /* Never inline regular functions into always-inline functions
1544 during incremental inlining. */
1545 && !node
->local
.disregard_inline_limits
)
1547 bitmap visited
= BITMAP_ALLOC (NULL
);
1548 for (e
= node
->callees
; e
; e
= e
->next_callee
)
1550 int allowed_growth
= 0;
1551 if (!e
->callee
->local
.inlinable
1552 || !e
->inline_failed
1553 || e
->callee
->local
.disregard_inline_limits
)
1555 /* We are inlining a function to all call-sites in node
1556 or to none. So visit each candidate only once. */
1557 if (!bitmap_set_bit (visited
, e
->callee
->uid
))
1560 fprintf (dump_file
, "Considering inline candidate %s.\n",
1561 cgraph_node_name (e
->callee
));
1562 if (cgraph_recursive_inlining_p (node
, e
->callee
, &e
->inline_failed
))
1565 fprintf (dump_file
, "Not inlining: recursive call.\n");
1568 if (gimple_in_ssa_p (DECL_STRUCT_FUNCTION (node
->decl
))
1569 != gimple_in_ssa_p (DECL_STRUCT_FUNCTION (e
->callee
->decl
)))
1573 "Not inlining: SSA form does not match.\n");
1577 if (cgraph_maybe_hot_edge_p (e
) && leaf_node_p (e
->callee
)
1578 && optimize_function_for_speed_p (cfun
))
1579 allowed_growth
= PARAM_VALUE (PARAM_EARLY_INLINING_INSNS
);
1581 /* When the function body would grow and inlining the function
1582 won't eliminate the need for offline copy of the function,
1584 if (((mode
== INLINE_SIZE
|| mode
== INLINE_SIZE_NORECURSIVE
)
1585 || (!flag_inline_functions
1586 && !DECL_DECLARED_INLINE_P (e
->callee
->decl
)))
1587 && (cgraph_estimate_size_after_inlining (1, e
->caller
, e
->callee
)
1588 > e
->caller
->global
.size
+ allowed_growth
)
1589 && cgraph_estimate_growth (e
->callee
) > allowed_growth
)
1593 "Not inlining: code size would grow by %i.\n",
1594 cgraph_estimate_size_after_inlining (1, e
->caller
,
1596 - e
->caller
->global
.size
);
1599 if (!cgraph_check_inline_limits (node
, e
->callee
, &e
->inline_failed
,
1601 || e
->call_stmt_cannot_inline_p
)
1604 fprintf (dump_file
, "Not inlining: %s.\n",
1605 cgraph_inline_failed_string (e
->inline_failed
));
1608 if (!e
->callee
->analyzed
)
1612 "Not inlining: Function body no longer available.\n");
1615 if (!tree_can_inline_p (e
))
1619 "Not inlining: %s.",
1620 cgraph_inline_failed_string (e
->inline_failed
));
1623 if (cgraph_default_inline_p (e
->callee
, &failed_reason
))
1626 fprintf (dump_file
, " Inlining %s into %s.\n",
1627 cgraph_node_name (e
->callee
),
1628 cgraph_node_name (e
->caller
));
1629 cgraph_mark_inline (e
);
1633 BITMAP_FREE (visited
);
1638 /* Because inlining might remove no-longer reachable nodes, we need to
1639 keep the array visible to garbage collector to avoid reading collected
1642 static GTY ((length ("nnodes"))) struct cgraph_node
**order
;
1644 /* Do inlining of small functions. Doing so early helps profiling and other
1645 passes to be somewhat more effective and avoids some code duplication in
1646 later real inlining pass for testcases with very many function calls. */
1648 cgraph_early_inlining (void)
1650 struct cgraph_node
*node
= cgraph_node (current_function_decl
);
1651 unsigned int todo
= 0;
1654 if (sorrycount
|| errorcount
)
1659 || !flag_early_inlining
)
1661 /* When not optimizing or not inlining inline only always-inline
1663 cgraph_decide_inlining_incrementally (node
, INLINE_ALWAYS_INLINE
);
1664 timevar_push (TV_INTEGRATION
);
1665 todo
|= optimize_inline_calls (current_function_decl
);
1666 timevar_pop (TV_INTEGRATION
);
1670 /* We iterate incremental inlining to get trivial cases of indirect
1672 while (iterations
< PARAM_VALUE (PARAM_EARLY_INLINER_MAX_ITERATIONS
)
1673 && cgraph_decide_inlining_incrementally (node
,
1675 ? INLINE_SIZE_NORECURSIVE
1678 timevar_push (TV_INTEGRATION
);
1679 todo
|= optimize_inline_calls (current_function_decl
);
1681 timevar_pop (TV_INTEGRATION
);
1684 fprintf (dump_file
, "Iterations: %i\n", iterations
);
1687 cfun
->always_inline_functions_inlined
= true;
1692 struct gimple_opt_pass pass_early_inline
=
1696 "einline", /* name */
1698 cgraph_early_inlining
, /* execute */
1701 0, /* static_pass_number */
1702 TV_INLINE_HEURISTICS
, /* tv_id */
1703 0, /* properties_required */
1704 0, /* properties_provided */
1705 0, /* properties_destroyed */
1706 0, /* todo_flags_start */
1707 TODO_dump_func
/* todo_flags_finish */
1711 /* When inlining shall be performed. */
1713 cgraph_gate_ipa_early_inlining (void)
1715 return (flag_early_inlining
1717 && (flag_branch_probabilities
|| flag_test_coverage
1718 || profile_arc_flag
));
1721 /* IPA pass wrapper for early inlining pass. We need to run early inlining
1722 before tree profiling so we have stand alone IPA pass for doing so. */
1723 struct simple_ipa_opt_pass pass_ipa_early_inline
=
1727 "einline_ipa", /* name */
1728 cgraph_gate_ipa_early_inlining
, /* gate */
1732 0, /* static_pass_number */
1733 TV_INLINE_HEURISTICS
, /* tv_id */
1734 0, /* properties_required */
1735 0, /* properties_provided */
1736 0, /* properties_destroyed */
1737 0, /* todo_flags_start */
1738 TODO_dump_cgraph
/* todo_flags_finish */
1742 /* See if statement might disappear after inlining. We are not terribly
1743 sophisficated, basically looking for simple abstraction penalty wrappers. */
1746 likely_eliminated_by_inlining_p (gimple stmt
)
1748 enum gimple_code code
= gimple_code (stmt
);
1754 if (gimple_num_ops (stmt
) != 2)
1757 /* Casts of parameters, loads from parameters passed by reference
1758 and stores to return value or parameters are probably free after
1760 if (gimple_assign_rhs_code (stmt
) == CONVERT_EXPR
1761 || gimple_assign_rhs_code (stmt
) == NOP_EXPR
1762 || gimple_assign_rhs_code (stmt
) == VIEW_CONVERT_EXPR
1763 || gimple_assign_rhs_class (stmt
) == GIMPLE_SINGLE_RHS
)
1765 tree rhs
= gimple_assign_rhs1 (stmt
);
1766 tree lhs
= gimple_assign_lhs (stmt
);
1767 tree inner_rhs
= rhs
;
1768 tree inner_lhs
= lhs
;
1769 bool rhs_free
= false;
1770 bool lhs_free
= false;
1772 while (handled_component_p (inner_lhs
) || TREE_CODE (inner_lhs
) == INDIRECT_REF
)
1773 inner_lhs
= TREE_OPERAND (inner_lhs
, 0);
1774 while (handled_component_p (inner_rhs
)
1775 || TREE_CODE (inner_rhs
) == ADDR_EXPR
|| TREE_CODE (inner_rhs
) == INDIRECT_REF
)
1776 inner_rhs
= TREE_OPERAND (inner_rhs
, 0);
1779 if (TREE_CODE (inner_rhs
) == PARM_DECL
1780 || (TREE_CODE (inner_rhs
) == SSA_NAME
1781 && SSA_NAME_IS_DEFAULT_DEF (inner_rhs
)
1782 && TREE_CODE (SSA_NAME_VAR (inner_rhs
)) == PARM_DECL
))
1784 if (rhs_free
&& is_gimple_reg (lhs
))
1786 if (((TREE_CODE (inner_lhs
) == PARM_DECL
1787 || (TREE_CODE (inner_lhs
) == SSA_NAME
1788 && SSA_NAME_IS_DEFAULT_DEF (inner_lhs
)
1789 && TREE_CODE (SSA_NAME_VAR (inner_lhs
)) == PARM_DECL
))
1790 && inner_lhs
!= lhs
)
1791 || TREE_CODE (inner_lhs
) == RESULT_DECL
1792 || (TREE_CODE (inner_lhs
) == SSA_NAME
1793 && TREE_CODE (SSA_NAME_VAR (inner_lhs
)) == RESULT_DECL
))
1795 if (lhs_free
&& (is_gimple_reg (rhs
) || is_gimple_min_invariant (rhs
)))
1797 if (lhs_free
&& rhs_free
)
1806 /* Compute function body size parameters for NODE. */
1809 estimate_function_body_sizes (struct cgraph_node
*node
)
1812 gcov_type time_inlining_benefit
= 0;
1814 int size_inlining_benefit
= 0;
1816 gimple_stmt_iterator bsi
;
1817 struct function
*my_function
= DECL_STRUCT_FUNCTION (node
->decl
);
1820 tree funtype
= TREE_TYPE (node
->decl
);
1822 if (node
->local
.disregard_inline_limits
)
1824 inline_summary (node
)->self_time
= 0;
1825 inline_summary (node
)->self_size
= 0;
1826 inline_summary (node
)->time_inlining_benefit
= 0;
1827 inline_summary (node
)->size_inlining_benefit
= 0;
1831 fprintf (dump_file
, "Analyzing function body size: %s\n",
1832 cgraph_node_name (node
));
1834 gcc_assert (my_function
&& my_function
->cfg
);
1835 FOR_EACH_BB_FN (bb
, my_function
)
1837 freq
= compute_call_stmt_bb_frequency (node
->decl
, bb
);
1838 for (bsi
= gsi_start_bb (bb
); !gsi_end_p (bsi
); gsi_next (&bsi
))
1840 gimple stmt
= gsi_stmt (bsi
);
1841 int this_size
= estimate_num_insns (stmt
, &eni_size_weights
);
1842 int this_time
= estimate_num_insns (stmt
, &eni_time_weights
);
1844 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1846 fprintf (dump_file
, " freq:%6i size:%3i time:%3i ",
1847 freq
, this_size
, this_time
);
1848 print_gimple_stmt (dump_file
, stmt
, 0, 0);
1853 if (likely_eliminated_by_inlining_p (stmt
))
1855 size_inlining_benefit
+= this_size
;
1856 time_inlining_benefit
+= this_time
;
1857 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1858 fprintf (dump_file
, " Likely eliminated\n");
1860 gcc_assert (time
>= 0);
1861 gcc_assert (size
>= 0);
1864 time
= (time
+ CGRAPH_FREQ_BASE
/ 2) / CGRAPH_FREQ_BASE
;
1865 time_inlining_benefit
= ((time_inlining_benefit
+ CGRAPH_FREQ_BASE
/ 2)
1866 / CGRAPH_FREQ_BASE
);
1868 fprintf (dump_file
, "Overall function body time: %i-%i size: %i-%i\n",
1869 (int)time
, (int)time_inlining_benefit
,
1870 size
, size_inlining_benefit
);
1871 time_inlining_benefit
+= eni_time_weights
.call_cost
;
1872 size_inlining_benefit
+= eni_size_weights
.call_cost
;
1873 if (!VOID_TYPE_P (TREE_TYPE (funtype
)))
1875 int cost
= estimate_move_cost (TREE_TYPE (funtype
));
1876 time_inlining_benefit
+= cost
;
1877 size_inlining_benefit
+= cost
;
1879 for (arg
= DECL_ARGUMENTS (node
->decl
); arg
; arg
= TREE_CHAIN (arg
))
1880 if (!VOID_TYPE_P (TREE_TYPE (arg
)))
1882 int cost
= estimate_move_cost (TREE_TYPE (arg
));
1883 time_inlining_benefit
+= cost
;
1884 size_inlining_benefit
+= cost
;
1886 if (time_inlining_benefit
> MAX_TIME
)
1887 time_inlining_benefit
= MAX_TIME
;
1888 if (time
> MAX_TIME
)
1890 inline_summary (node
)->self_time
= time
;
1891 inline_summary (node
)->self_size
= size
;
1893 fprintf (dump_file
, "With function call overhead time: %i-%i size: %i-%i\n",
1894 (int)time
, (int)time_inlining_benefit
,
1895 size
, size_inlining_benefit
);
1896 inline_summary (node
)->time_inlining_benefit
= time_inlining_benefit
;
1897 inline_summary (node
)->size_inlining_benefit
= size_inlining_benefit
;
1900 /* Compute parameters of functions used by inliner. */
1902 compute_inline_parameters (struct cgraph_node
*node
)
1904 HOST_WIDE_INT self_stack_size
;
1906 gcc_assert (!node
->global
.inlined_to
);
1908 /* Estimate the stack size for the function. But not at -O0
1909 because estimated_stack_frame_size is a quadratic problem. */
1910 self_stack_size
= optimize
? estimated_stack_frame_size () : 0;
1911 inline_summary (node
)->estimated_self_stack_size
= self_stack_size
;
1912 node
->global
.estimated_stack_size
= self_stack_size
;
1913 node
->global
.stack_frame_offset
= 0;
1915 /* Can this function be inlined at all? */
1916 node
->local
.inlinable
= tree_inlinable_function_p (node
->decl
);
1917 if (node
->local
.inlinable
&& !node
->local
.disregard_inline_limits
)
1918 node
->local
.disregard_inline_limits
1919 = DECL_DISREGARD_INLINE_LIMITS (node
->decl
);
1920 estimate_function_body_sizes (node
);
1921 /* Inlining characteristics are maintained by the cgraph_mark_inline. */
1922 node
->global
.time
= inline_summary (node
)->self_time
;
1923 node
->global
.size
= inline_summary (node
)->self_size
;
1928 /* Compute parameters of functions used by inliner using
1929 current_function_decl. */
1931 compute_inline_parameters_for_current (void)
1933 compute_inline_parameters (cgraph_node (current_function_decl
));
1937 struct gimple_opt_pass pass_inline_parameters
=
1941 "inline_param", /* name */
1943 compute_inline_parameters_for_current
,/* execute */
1946 0, /* static_pass_number */
1947 TV_INLINE_HEURISTICS
, /* tv_id */
1948 0, /* properties_required */
1949 0, /* properties_provided */
1950 0, /* properties_destroyed */
1951 0, /* todo_flags_start */
1952 0 /* todo_flags_finish */
1956 /* This function performs intraprocedural analyzis in NODE that is required to
1957 inline indirect calls. */
1959 inline_indirect_intraprocedural_analysis (struct cgraph_node
*node
)
1961 struct cgraph_edge
*cs
;
1965 ipa_initialize_node_params (node
);
1966 ipa_detect_param_modifications (node
);
1968 ipa_analyze_params_uses (node
);
1971 for (cs
= node
->callees
; cs
; cs
= cs
->next_callee
)
1973 ipa_count_arguments (cs
);
1974 ipa_compute_jump_functions (cs
);
1979 ipa_print_node_params (dump_file
, node
);
1980 ipa_print_node_jump_functions (dump_file
, node
);
1984 /* Note function body size. */
1986 analyze_function (struct cgraph_node
*node
)
1988 push_cfun (DECL_STRUCT_FUNCTION (node
->decl
));
1989 current_function_decl
= node
->decl
;
1991 compute_inline_parameters (node
);
1992 if (flag_indirect_inlining
)
1993 inline_indirect_intraprocedural_analysis (node
);
1995 current_function_decl
= NULL
;
1999 /* Called when new function is inserted to callgraph late. */
2001 add_new_function (struct cgraph_node
*node
, void *data ATTRIBUTE_UNUSED
)
2003 analyze_function (node
);
2006 /* Note function body size. */
2008 inline_generate_summary (void)
2010 struct cgraph_node
*node
;
2012 function_insertion_hook_holder
=
2013 cgraph_add_function_insertion_hook (&add_new_function
, NULL
);
2015 if (flag_indirect_inlining
)
2017 ipa_register_cgraph_hooks ();
2018 ipa_check_create_node_params ();
2019 ipa_check_create_edge_args ();
2022 for (node
= cgraph_nodes
; node
; node
= node
->next
)
2024 analyze_function (node
);
2029 /* Apply inline plan to function. */
2031 inline_transform (struct cgraph_node
*node
)
2033 unsigned int todo
= 0;
2034 struct cgraph_edge
*e
;
2036 /* FIXME: Currently the passmanager is adding inline transform more than once to some
2037 clones. This needs revisiting after WPA cleanups. */
2038 if (cfun
->after_inlining
)
2041 /* We might need the body of this function so that we can expand
2042 it inline somewhere else. */
2043 if (cgraph_preserve_function_body_p (node
->decl
))
2044 save_inline_function_body (node
);
2046 for (e
= node
->callees
; e
; e
= e
->next_callee
)
2047 if (!e
->inline_failed
|| warn_inline
)
2052 timevar_push (TV_INTEGRATION
);
2053 todo
= optimize_inline_calls (current_function_decl
);
2054 timevar_pop (TV_INTEGRATION
);
2056 cfun
->always_inline_functions_inlined
= true;
2057 cfun
->after_inlining
= true;
2058 return todo
| execute_fixup_cfg ();
2061 /* Read inline summary. Jump functions are shared among ipa-cp
2062 and inliner, so when ipa-cp is active, we don't need to write them
2066 inline_read_summary (void)
2068 if (flag_indirect_inlining
)
2070 ipa_register_cgraph_hooks ();
2072 ipa_prop_read_jump_functions ();
2074 function_insertion_hook_holder
=
2075 cgraph_add_function_insertion_hook (&add_new_function
, NULL
);
2078 /* Write inline summary for node in SET.
2079 Jump functions are shared among ipa-cp and inliner, so when ipa-cp is
2080 active, we don't need to write them twice. */
2083 inline_write_summary (cgraph_node_set set
)
2085 if (flag_indirect_inlining
&& !flag_ipa_cp
)
2086 ipa_prop_write_jump_functions (set
);
2089 /* When to run IPA inlining. Inlining of always-inline functions
2090 happens during early inlining. */
2093 gate_cgraph_decide_inlining (void)
2095 /* ??? We'd like to skip this if not optimizing or not inlining as
2096 all always-inline functions have been processed by early
2097 inlining already. But this at least breaks EH with C++ as
2098 we need to unconditionally run fixup_cfg even at -O0.
2099 So leave it on unconditionally for now. */
2103 struct ipa_opt_pass_d pass_ipa_inline
=
2107 "inline", /* name */
2108 gate_cgraph_decide_inlining
, /* gate */
2109 cgraph_decide_inlining
, /* execute */
2112 0, /* static_pass_number */
2113 TV_INLINE_HEURISTICS
, /* tv_id */
2114 0, /* properties_required */
2115 0, /* properties_provided */
2116 0, /* properties_destroyed */
2117 TODO_remove_functions
, /* todo_flags_finish */
2118 TODO_dump_cgraph
| TODO_dump_func
2119 | TODO_remove_functions
/* todo_flags_finish */
2121 inline_generate_summary
, /* generate_summary */
2122 inline_write_summary
, /* write_summary */
2123 inline_read_summary
, /* read_summary */
2124 NULL
, /* function_read_summary */
2125 lto_ipa_fixup_call_notes
, /* stmt_fixup */
2127 inline_transform
, /* function_transform */
2128 NULL
, /* variable_transform */
2132 #include "gt-ipa-inline.h"