1 /* Inlining decision heuristics.
2 Copyright (C) 2003, 2004, 2007, 2008, 2009 Free Software Foundation, Inc.
3 Contributed by Jan Hubicka
5 This file is part of GCC.
7 GCC is free software; you can redistribute it and/or modify it under
8 the terms of the GNU General Public License as published by the Free
9 Software Foundation; either version 3, or (at your option) any later
12 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
13 WARRANTY; without even the implied warranty of MERCHANTABILITY or
14 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
17 You should have received a copy of the GNU General Public License
18 along with GCC; see the file COPYING3. If not see
19 <http://www.gnu.org/licenses/>. */
21 /* Inlining decision heuristics
23 We separate inlining decisions from the inliner itself and store it
24 inside callgraph as so called inline plan. Refer to cgraph.c
25 documentation about particular representation of inline plans in the
28 There are three major parts of this file:
30 cgraph_mark_inline implementation
32 This function allows to mark given call inline and performs necessary
33 modifications of cgraph (production of the clones and updating overall
36 inlining heuristics limits
38 These functions allow to check that particular inlining is allowed
39 by the limits specified by user (allowed function growth, overall unit
44 This is implementation of IPA pass aiming to get as much of benefit
45 from inlining obeying the limits checked above.
47 The implementation of particular heuristics is separated from
48 the rest of code to make it easier to replace it with more complicated
49 implementation in the future. The rest of inlining code acts as a
50 library aimed to modify the callgraph and verify that the parameters
51 on code size growth fits.
53 To mark given call inline, use cgraph_mark_inline function, the
54 verification is performed by cgraph_default_inline_p and
55 cgraph_check_inline_limits.
57 The heuristics implements simple knapsack style algorithm ordering
58 all functions by their "profitability" (estimated by code size growth)
59 and inlining them in priority order.
61 cgraph_decide_inlining implements heuristics taking whole callgraph
62 into account, while cgraph_decide_inlining_incrementally considers
63 only one function at a time and is used by early inliner.
65 The inliner itself is split into several passes:
67 pass_inline_parameters
69 This pass computes local properties of functions that are used by inliner:
70 estimated function body size, whether function is inlinable at all and
71 stack frame consumption.
73 Before executing any of inliner passes, this local pass has to be applied
74 to each function in the callgraph (ie run as subpass of some earlier
75 IPA pass). The results are made out of date by any optimization applied
80 Simple local inlining pass inlining callees into current function. This
81 pass makes no global whole compilation unit analysis and this when allowed
82 to do inlining expanding code size it might result in unbounded growth of
85 The pass is run during conversion into SSA form. Only functions already
86 converted into SSA form are inlined, so the conversion must happen in
87 topological order on the callgraph (that is maintained by pass manager).
88 The functions after inlining are early optimized so the early inliner sees
89 unoptimized function itself, but all considered callees are already
90 optimized allowing it to unfold abstraction penalty on C++ effectively and
93 pass_ipa_early_inlining
95 With profiling, the early inlining is also necessary to reduce
96 instrumentation costs on program with high abstraction penalty (doing
97 many redundant calls). This can't happen in parallel with early
98 optimization and profile instrumentation, because we would end up
99 re-instrumenting already instrumented function bodies we brought in via
102 To avoid this, this pass is executed as IPA pass before profiling. It is
103 simple wrapper to pass_early_inlining and ensures first inlining.
107 This is the main pass implementing simple greedy algorithm to do inlining
108 of small functions that results in overall growth of compilation unit and
109 inlining of functions called once. The pass compute just so called inline
110 plan (representation of inlining to be done in callgraph) and unlike early
111 inlining it is not performing the inlining itself.
115 This pass performs actual inlining according to pass_ipa_inline on given
116 function. Possible the function body before inlining is saved when it is
117 needed for further inlining later.
122 #include "coretypes.h"
125 #include "tree-inline.h"
126 #include "langhooks.h"
129 #include "diagnostic.h"
134 #include "tree-pass.h"
136 #include "coverage.h"
138 #include "tree-flow.h"
140 #include "ipa-prop.h"
143 #define MAX_TIME 1000000000
145 /* Mode incremental inliner operate on:
147 In ALWAYS_INLINE only functions marked
148 always_inline are inlined. This mode is used after detecting cycle during
151 In SIZE mode, only functions that reduce function body size after inlining
152 are inlined, this is used during early inlining.
154 in ALL mode, everything is inlined. This is used during flattening. */
157 INLINE_ALWAYS_INLINE
,
158 INLINE_SIZE_NORECURSIVE
,
163 cgraph_decide_inlining_incrementally (struct cgraph_node
*, enum inlining_mode
,
167 /* Statistics we collect about inlining algorithm. */
168 static int ncalls_inlined
;
169 static int nfunctions_inlined
;
170 static int overall_size
;
171 static gcov_type max_count
, max_benefit
;
173 /* Holders of ipa cgraph hooks: */
174 static struct cgraph_node_hook_list
*function_insertion_hook_holder
;
176 static inline struct inline_summary
*
177 inline_summary (struct cgraph_node
*node
)
179 return &node
->local
.inline_summary
;
182 /* Estimate self time of the function after inlining WHAT into TO. */
185 cgraph_estimate_time_after_inlining (int frequency
, struct cgraph_node
*to
,
186 struct cgraph_node
*what
)
188 gcov_type time
= (((gcov_type
)what
->global
.time
189 - inline_summary (what
)->time_inlining_benefit
)
190 * frequency
+ CGRAPH_FREQ_BASE
/ 2) / CGRAPH_FREQ_BASE
199 /* Estimate self time of the function after inlining WHAT into TO. */
202 cgraph_estimate_size_after_inlining (int times
, struct cgraph_node
*to
,
203 struct cgraph_node
*what
)
205 int size
= (what
->global
.size
- inline_summary (what
)->size_inlining_benefit
) * times
+ to
->global
.size
;
206 gcc_assert (size
>= 0);
210 /* E is expected to be an edge being inlined. Clone destination node of
211 the edge and redirect it to the new clone.
212 DUPLICATE is used for bookkeeping on whether we are actually creating new
213 clones or re-using node originally representing out-of-line function call.
216 cgraph_clone_inlined_nodes (struct cgraph_edge
*e
, bool duplicate
,
217 bool update_original
)
223 /* We may eliminate the need for out-of-line copy to be output.
224 In that case just go ahead and re-use it. */
225 if (!e
->callee
->callers
->next_caller
226 && cgraph_can_remove_if_no_direct_calls_p (e
->callee
)
227 && !cgraph_new_nodes
)
229 gcc_assert (!e
->callee
->global
.inlined_to
);
230 if (e
->callee
->analyzed
)
232 overall_size
-= e
->callee
->global
.size
;
233 nfunctions_inlined
++;
236 e
->callee
->local
.externally_visible
= false;
240 struct cgraph_node
*n
;
241 n
= cgraph_clone_node (e
->callee
, e
->count
, e
->frequency
, e
->loop_nest
,
242 update_original
, NULL
);
243 cgraph_redirect_edge_callee (e
, n
);
247 if (e
->caller
->global
.inlined_to
)
248 e
->callee
->global
.inlined_to
= e
->caller
->global
.inlined_to
;
250 e
->callee
->global
.inlined_to
= e
->caller
;
251 e
->callee
->global
.stack_frame_offset
252 = e
->caller
->global
.stack_frame_offset
253 + inline_summary (e
->caller
)->estimated_self_stack_size
;
254 peak
= e
->callee
->global
.stack_frame_offset
255 + inline_summary (e
->callee
)->estimated_self_stack_size
;
256 if (e
->callee
->global
.inlined_to
->global
.estimated_stack_size
< peak
)
257 e
->callee
->global
.inlined_to
->global
.estimated_stack_size
= peak
;
259 /* Recursively clone all bodies. */
260 for (e
= e
->callee
->callees
; e
; e
= e
->next_callee
)
261 if (!e
->inline_failed
)
262 cgraph_clone_inlined_nodes (e
, duplicate
, update_original
);
265 /* Mark edge E as inlined and update callgraph accordingly. UPDATE_ORIGINAL
266 specify whether profile of original function should be updated. If any new
267 indirect edges are discovered in the process, add them to NEW_EDGES, unless
268 it is NULL. Return true iff any new callgraph edges were discovered as a
269 result of inlining. */
272 cgraph_mark_inline_edge (struct cgraph_edge
*e
, bool update_original
,
273 VEC (cgraph_edge_p
, heap
) **new_edges
)
275 int old_size
= 0, new_size
= 0;
276 struct cgraph_node
*to
= NULL
, *what
;
277 struct cgraph_edge
*curr
= e
;
279 bool duplicate
= false;
280 int orig_size
= e
->callee
->global
.size
;
282 gcc_assert (e
->inline_failed
);
283 e
->inline_failed
= CIF_OK
;
285 if (!e
->callee
->global
.inlined
)
286 DECL_POSSIBLY_INLINED (e
->callee
->decl
) = true;
287 e
->callee
->global
.inlined
= true;
289 if (e
->callee
->callers
->next_caller
290 || !cgraph_can_remove_if_no_direct_calls_p (e
->callee
))
292 cgraph_clone_inlined_nodes (e
, true, update_original
);
297 /* Now update size of caller and all functions caller is inlined into. */
298 for (;e
&& !e
->inline_failed
; e
= e
->caller
->callers
)
301 old_size
= e
->caller
->global
.size
;
302 new_size
= cgraph_estimate_size_after_inlining (1, to
, what
);
303 to
->global
.size
= new_size
;
304 to
->global
.time
= cgraph_estimate_time_after_inlining (freq
, to
, what
);
306 gcc_assert (what
->global
.inlined_to
== to
);
307 if (new_size
> old_size
)
308 overall_size
+= new_size
- old_size
;
310 overall_size
-= orig_size
;
313 if (flag_indirect_inlining
)
314 return ipa_propagate_indirect_call_infos (curr
, new_edges
);
319 /* Mark all calls of EDGE->CALLEE inlined into EDGE->CALLER.
320 Return following unredirected edge in the list of callers
323 static struct cgraph_edge
*
324 cgraph_mark_inline (struct cgraph_edge
*edge
)
326 struct cgraph_node
*to
= edge
->caller
;
327 struct cgraph_node
*what
= edge
->callee
;
328 struct cgraph_edge
*e
, *next
;
330 gcc_assert (!edge
->call_stmt_cannot_inline_p
);
331 /* Look for all calls, mark them inline and clone recursively
332 all inlined functions. */
333 for (e
= what
->callers
; e
; e
= next
)
335 next
= e
->next_caller
;
336 if (e
->caller
== to
&& e
->inline_failed
)
338 cgraph_mark_inline_edge (e
, true, NULL
);
347 /* Estimate the growth caused by inlining NODE into all callees. */
350 cgraph_estimate_growth (struct cgraph_node
*node
)
353 struct cgraph_edge
*e
;
354 bool self_recursive
= false;
356 if (node
->global
.estimated_growth
!= INT_MIN
)
357 return node
->global
.estimated_growth
;
359 for (e
= node
->callers
; e
; e
= e
->next_caller
)
361 if (e
->caller
== node
)
362 self_recursive
= true;
363 if (e
->inline_failed
)
364 growth
+= (cgraph_estimate_size_after_inlining (1, e
->caller
, node
)
365 - e
->caller
->global
.size
);
368 /* ??? Wrong for non-trivially self recursive functions or cases where
369 we decide to not inline for different reasons, but it is not big deal
370 as in that case we will keep the body around, but we will also avoid
372 if (cgraph_only_called_directly_p (node
)
373 && !DECL_EXTERNAL (node
->decl
) && !self_recursive
)
374 growth
-= node
->global
.size
;
376 node
->global
.estimated_growth
= growth
;
380 /* Return false when inlining WHAT into TO is not good idea
381 as it would cause too large growth of function bodies.
382 When ONE_ONLY is true, assume that only one call site is going
383 to be inlined, otherwise figure out how many call sites in
384 TO calls WHAT and verify that all can be inlined.
388 cgraph_check_inline_limits (struct cgraph_node
*to
, struct cgraph_node
*what
,
389 cgraph_inline_failed_t
*reason
, bool one_only
)
392 struct cgraph_edge
*e
;
395 HOST_WIDE_INT stack_size_limit
, inlined_stack
;
400 for (e
= to
->callees
; e
; e
= e
->next_callee
)
401 if (e
->callee
== what
)
404 if (to
->global
.inlined_to
)
405 to
= to
->global
.inlined_to
;
407 /* When inlining large function body called once into small function,
408 take the inlined function as base for limiting the growth. */
409 if (inline_summary (to
)->self_size
> inline_summary(what
)->self_size
)
410 limit
= inline_summary (to
)->self_size
;
412 limit
= inline_summary (what
)->self_size
;
414 limit
+= limit
* PARAM_VALUE (PARAM_LARGE_FUNCTION_GROWTH
) / 100;
416 /* Check the size after inlining against the function limits. But allow
417 the function to shrink if it went over the limits by forced inlining. */
418 newsize
= cgraph_estimate_size_after_inlining (times
, to
, what
);
419 if (newsize
>= to
->global
.size
420 && newsize
> PARAM_VALUE (PARAM_LARGE_FUNCTION_INSNS
)
424 *reason
= CIF_LARGE_FUNCTION_GROWTH_LIMIT
;
428 stack_size_limit
= inline_summary (to
)->estimated_self_stack_size
;
430 stack_size_limit
+= stack_size_limit
* PARAM_VALUE (PARAM_STACK_FRAME_GROWTH
) / 100;
432 inlined_stack
= (to
->global
.stack_frame_offset
433 + inline_summary (to
)->estimated_self_stack_size
434 + what
->global
.estimated_stack_size
);
435 if (inlined_stack
> stack_size_limit
436 && inlined_stack
> PARAM_VALUE (PARAM_LARGE_STACK_FRAME
))
439 *reason
= CIF_LARGE_STACK_FRAME_GROWTH_LIMIT
;
445 /* Return true when function N is small enough to be inlined. */
448 cgraph_default_inline_p (struct cgraph_node
*n
, cgraph_inline_failed_t
*reason
)
452 if (!flag_inline_small_functions
&& !DECL_DECLARED_INLINE_P (decl
))
455 *reason
= CIF_FUNCTION_NOT_INLINE_CANDIDATE
;
462 *reason
= CIF_BODY_NOT_AVAILABLE
;
466 if (DECL_DECLARED_INLINE_P (decl
))
468 if (n
->global
.size
>= MAX_INLINE_INSNS_SINGLE
)
471 *reason
= CIF_MAX_INLINE_INSNS_SINGLE_LIMIT
;
477 if (n
->global
.size
>= MAX_INLINE_INSNS_AUTO
)
480 *reason
= CIF_MAX_INLINE_INSNS_AUTO_LIMIT
;
488 /* Return true when inlining WHAT would create recursive inlining.
489 We call recursive inlining all cases where same function appears more than
490 once in the single recursion nest path in the inline graph. */
493 cgraph_recursive_inlining_p (struct cgraph_node
*to
,
494 struct cgraph_node
*what
,
495 cgraph_inline_failed_t
*reason
)
498 if (to
->global
.inlined_to
)
499 recursive
= what
->decl
== to
->global
.inlined_to
->decl
;
501 recursive
= what
->decl
== to
->decl
;
502 /* Marking recursive function inline has sane semantic and thus we should
504 if (recursive
&& reason
)
505 *reason
= (what
->local
.disregard_inline_limits
506 ? CIF_RECURSIVE_INLINING
: CIF_UNSPECIFIED
);
510 /* A cost model driving the inlining heuristics in a way so the edges with
511 smallest badness are inlined first. After each inlining is performed
512 the costs of all caller edges of nodes affected are recomputed so the
513 metrics may accurately depend on values such as number of inlinable callers
514 of the function or function body size. */
517 cgraph_edge_badness (struct cgraph_edge
*edge
)
521 cgraph_estimate_size_after_inlining (1, edge
->caller
, edge
->callee
);
523 growth
-= edge
->caller
->global
.size
;
525 /* Always prefer inlining saving code size. */
527 badness
= INT_MIN
- growth
;
529 /* When profiling is available, base priorities -(#calls / growth).
530 So we optimize for overall number of "executed" inlined calls. */
532 badness
= ((int)((double)edge
->count
* INT_MIN
/ max_count
/ (max_benefit
+ 1))
533 * (inline_summary (edge
->callee
)->time_inlining_benefit
+ 1)) / growth
;
535 /* When function local profile is available, base priorities on
536 growth / frequency, so we optimize for overall frequency of inlined
537 calls. This is not too accurate since while the call might be frequent
538 within function, the function itself is infrequent.
540 Other objective to optimize for is number of different calls inlined.
541 We add the estimated growth after inlining all functions to bias the
542 priorities slightly in this direction (so fewer times called functions
543 of the same size gets priority). */
544 else if (flag_guess_branch_prob
)
546 int div
= edge
->frequency
* 100 / CGRAPH_FREQ_BASE
+ 1;
547 badness
= growth
* 10000;
548 div
*= MIN (100 * inline_summary (edge
->callee
)->time_inlining_benefit
549 / (edge
->callee
->global
.time
+ 1) + 1, 100);
552 /* Decrease badness if call is nested. */
553 /* Compress the range so we don't overflow. */
555 div
= 10000 + ceil_log2 (div
) - 8;
560 badness
+= cgraph_estimate_growth (edge
->callee
);
561 if (badness
> INT_MAX
)
564 /* When function local profile is not available or it does not give
565 useful information (ie frequency is zero), base the cost on
566 loop nest and overall size growth, so we optimize for overall number
567 of functions fully inlined in program. */
570 int nest
= MIN (edge
->loop_nest
, 8);
571 badness
= cgraph_estimate_growth (edge
->callee
) * 256;
573 /* Decrease badness if call is nested. */
581 /* Make recursive inlining happen always after other inlining is done. */
582 if (cgraph_recursive_inlining_p (edge
->caller
, edge
->callee
, NULL
))
588 /* Recompute heap nodes for each of caller edge. */
591 update_caller_keys (fibheap_t heap
, struct cgraph_node
*node
,
592 bitmap updated_nodes
)
594 struct cgraph_edge
*edge
;
595 cgraph_inline_failed_t failed_reason
;
597 if (!node
->local
.inlinable
|| node
->local
.disregard_inline_limits
598 || node
->global
.inlined_to
)
600 if (bitmap_bit_p (updated_nodes
, node
->uid
))
602 bitmap_set_bit (updated_nodes
, node
->uid
);
603 node
->global
.estimated_growth
= INT_MIN
;
605 if (!node
->local
.inlinable
)
607 /* Prune out edges we won't inline into anymore. */
608 if (!cgraph_default_inline_p (node
, &failed_reason
))
610 for (edge
= node
->callers
; edge
; edge
= edge
->next_caller
)
613 fibheap_delete_node (heap
, (fibnode_t
) edge
->aux
);
615 if (edge
->inline_failed
)
616 edge
->inline_failed
= failed_reason
;
621 for (edge
= node
->callers
; edge
; edge
= edge
->next_caller
)
622 if (edge
->inline_failed
)
624 int badness
= cgraph_edge_badness (edge
);
627 fibnode_t n
= (fibnode_t
) edge
->aux
;
628 gcc_assert (n
->data
== edge
);
629 if (n
->key
== badness
)
632 /* fibheap_replace_key only increase the keys. */
633 if (fibheap_replace_key (heap
, n
, badness
))
635 fibheap_delete_node (heap
, (fibnode_t
) edge
->aux
);
637 edge
->aux
= fibheap_insert (heap
, badness
, edge
);
641 /* Recompute heap nodes for each of caller edges of each of callees. */
644 update_callee_keys (fibheap_t heap
, struct cgraph_node
*node
,
645 bitmap updated_nodes
)
647 struct cgraph_edge
*e
;
648 node
->global
.estimated_growth
= INT_MIN
;
650 for (e
= node
->callees
; e
; e
= e
->next_callee
)
651 if (e
->inline_failed
)
652 update_caller_keys (heap
, e
->callee
, updated_nodes
);
653 else if (!e
->inline_failed
)
654 update_callee_keys (heap
, e
->callee
, updated_nodes
);
657 /* Enqueue all recursive calls from NODE into priority queue depending on
658 how likely we want to recursively inline the call. */
661 lookup_recursive_calls (struct cgraph_node
*node
, struct cgraph_node
*where
,
665 struct cgraph_edge
*e
;
666 for (e
= where
->callees
; e
; e
= e
->next_callee
)
667 if (e
->callee
== node
)
669 /* When profile feedback is available, prioritize by expected number
670 of calls. Without profile feedback we maintain simple queue
671 to order candidates via recursive depths. */
672 fibheap_insert (heap
,
673 !max_count
? priority
++
674 : -(e
->count
/ ((max_count
+ (1<<24) - 1) / (1<<24))),
677 for (e
= where
->callees
; e
; e
= e
->next_callee
)
678 if (!e
->inline_failed
)
679 lookup_recursive_calls (node
, e
->callee
, heap
);
682 /* Decide on recursive inlining: in the case function has recursive calls,
683 inline until body size reaches given argument. If any new indirect edges
684 are discovered in the process, add them to *NEW_EDGES, unless NEW_EDGES
688 cgraph_decide_recursive_inlining (struct cgraph_node
*node
,
689 VEC (cgraph_edge_p
, heap
) **new_edges
)
691 int limit
= PARAM_VALUE (PARAM_MAX_INLINE_INSNS_RECURSIVE_AUTO
);
692 int max_depth
= PARAM_VALUE (PARAM_MAX_INLINE_RECURSIVE_DEPTH_AUTO
);
693 int probability
= PARAM_VALUE (PARAM_MIN_INLINE_RECURSIVE_PROBABILITY
);
695 struct cgraph_edge
*e
;
696 struct cgraph_node
*master_clone
, *next
;
700 if (optimize_function_for_size_p (DECL_STRUCT_FUNCTION (node
->decl
))
701 || (!flag_inline_functions
&& !DECL_DECLARED_INLINE_P (node
->decl
)))
704 if (DECL_DECLARED_INLINE_P (node
->decl
))
706 limit
= PARAM_VALUE (PARAM_MAX_INLINE_INSNS_RECURSIVE
);
707 max_depth
= PARAM_VALUE (PARAM_MAX_INLINE_RECURSIVE_DEPTH
);
710 /* Make sure that function is small enough to be considered for inlining. */
712 || cgraph_estimate_size_after_inlining (1, node
, node
) >= limit
)
714 heap
= fibheap_new ();
715 lookup_recursive_calls (node
, node
, heap
);
716 if (fibheap_empty (heap
))
718 fibheap_delete (heap
);
724 " Performing recursive inlining on %s\n",
725 cgraph_node_name (node
));
727 /* We need original clone to copy around. */
728 master_clone
= cgraph_clone_node (node
, node
->count
, CGRAPH_FREQ_BASE
, 1,
730 master_clone
->needed
= true;
731 for (e
= master_clone
->callees
; e
; e
= e
->next_callee
)
732 if (!e
->inline_failed
)
733 cgraph_clone_inlined_nodes (e
, true, false);
735 /* Do the inlining and update list of recursive call during process. */
736 while (!fibheap_empty (heap
)
737 && (cgraph_estimate_size_after_inlining (1, node
, master_clone
)
740 struct cgraph_edge
*curr
741 = (struct cgraph_edge
*) fibheap_extract_min (heap
);
742 struct cgraph_node
*cnode
;
745 for (cnode
= curr
->caller
;
746 cnode
->global
.inlined_to
; cnode
= cnode
->callers
->caller
)
747 if (node
->decl
== curr
->callee
->decl
)
749 if (depth
> max_depth
)
753 " maximal depth reached\n");
759 if (!cgraph_maybe_hot_edge_p (curr
))
762 fprintf (dump_file
, " Not inlining cold call\n");
765 if (curr
->count
* 100 / node
->count
< probability
)
769 " Probability of edge is too small\n");
777 " Inlining call of depth %i", depth
);
780 fprintf (dump_file
, " called approx. %.2f times per call",
781 (double)curr
->count
/ node
->count
);
783 fprintf (dump_file
, "\n");
785 cgraph_redirect_edge_callee (curr
, master_clone
);
786 cgraph_mark_inline_edge (curr
, false, new_edges
);
787 lookup_recursive_calls (node
, curr
->callee
, heap
);
790 if (!fibheap_empty (heap
) && dump_file
)
791 fprintf (dump_file
, " Recursive inlining growth limit met.\n");
793 fibheap_delete (heap
);
796 "\n Inlined %i times, body grown from size %i to %i, time %i to %i\n", n
,
797 master_clone
->global
.size
, node
->global
.size
,
798 master_clone
->global
.time
, node
->global
.time
);
800 /* Remove master clone we used for inlining. We rely that clones inlined
801 into master clone gets queued just before master clone so we don't
803 for (node
= cgraph_nodes
; node
!= master_clone
;
807 if (node
->global
.inlined_to
== master_clone
)
808 cgraph_remove_node (node
);
810 cgraph_remove_node (master_clone
);
811 /* FIXME: Recursive inlining actually reduces number of calls of the
812 function. At this place we should probably walk the function and
813 inline clones and compensate the counts accordingly. This probably
814 doesn't matter much in practice. */
818 /* Set inline_failed for all callers of given function to REASON. */
821 cgraph_set_inline_failed (struct cgraph_node
*node
,
822 cgraph_inline_failed_t reason
)
824 struct cgraph_edge
*e
;
827 fprintf (dump_file
, "Inlining failed: %s\n",
828 cgraph_inline_failed_string (reason
));
829 for (e
= node
->callers
; e
; e
= e
->next_caller
)
830 if (e
->inline_failed
)
831 e
->inline_failed
= reason
;
834 /* Given whole compilation unit estimate of INSNS, compute how large we can
835 allow the unit to grow. */
837 compute_max_insns (int insns
)
839 int max_insns
= insns
;
840 if (max_insns
< PARAM_VALUE (PARAM_LARGE_UNIT_INSNS
))
841 max_insns
= PARAM_VALUE (PARAM_LARGE_UNIT_INSNS
);
843 return ((HOST_WIDEST_INT
) max_insns
844 * (100 + PARAM_VALUE (PARAM_INLINE_UNIT_GROWTH
)) / 100);
847 /* Compute badness of all edges in NEW_EDGES and add them to the HEAP. */
849 add_new_edges_to_heap (fibheap_t heap
, VEC (cgraph_edge_p
, heap
) *new_edges
)
851 while (VEC_length (cgraph_edge_p
, new_edges
) > 0)
853 struct cgraph_edge
*edge
= VEC_pop (cgraph_edge_p
, new_edges
);
855 gcc_assert (!edge
->aux
);
856 edge
->aux
= fibheap_insert (heap
, cgraph_edge_badness (edge
), edge
);
861 /* We use greedy algorithm for inlining of small functions:
862 All inline candidates are put into prioritized heap based on estimated
863 growth of the overall number of instructions and then update the estimates.
865 INLINED and INLINED_CALEES are just pointers to arrays large enough
866 to be passed to cgraph_inlined_into and cgraph_inlined_callees. */
869 cgraph_decide_inlining_of_small_functions (void)
871 struct cgraph_node
*node
;
872 struct cgraph_edge
*edge
;
873 cgraph_inline_failed_t failed_reason
;
874 fibheap_t heap
= fibheap_new ();
875 bitmap updated_nodes
= BITMAP_ALLOC (NULL
);
876 int min_size
, max_size
;
877 VEC (cgraph_edge_p
, heap
) *new_indirect_edges
= NULL
;
879 if (flag_indirect_inlining
)
880 new_indirect_edges
= VEC_alloc (cgraph_edge_p
, heap
, 8);
883 fprintf (dump_file
, "\nDeciding on smaller functions:\n");
885 /* Put all inline candidates into the heap. */
887 for (node
= cgraph_nodes
; node
; node
= node
->next
)
889 if (!node
->local
.inlinable
|| !node
->callers
890 || node
->local
.disregard_inline_limits
)
893 fprintf (dump_file
, "Considering inline candidate %s.\n", cgraph_node_name (node
));
895 node
->global
.estimated_growth
= INT_MIN
;
896 if (!cgraph_default_inline_p (node
, &failed_reason
))
898 cgraph_set_inline_failed (node
, failed_reason
);
902 for (edge
= node
->callers
; edge
; edge
= edge
->next_caller
)
903 if (edge
->inline_failed
)
905 gcc_assert (!edge
->aux
);
906 edge
->aux
= fibheap_insert (heap
, cgraph_edge_badness (edge
), edge
);
910 max_size
= compute_max_insns (overall_size
);
911 min_size
= overall_size
;
913 while (overall_size
<= max_size
914 && (edge
= (struct cgraph_edge
*) fibheap_extract_min (heap
)))
916 int old_size
= overall_size
;
917 struct cgraph_node
*where
;
919 cgraph_estimate_size_after_inlining (1, edge
->caller
, edge
->callee
);
920 cgraph_inline_failed_t not_good
= CIF_OK
;
922 growth
-= edge
->caller
->global
.size
;
927 "\nConsidering %s with %i size\n",
928 cgraph_node_name (edge
->callee
),
929 edge
->callee
->global
.size
);
931 " to be inlined into %s in %s:%i\n"
932 " Estimated growth after inlined into all callees is %+i insns.\n"
933 " Estimated badness is %i, frequency %.2f.\n",
934 cgraph_node_name (edge
->caller
),
935 gimple_filename ((const_gimple
) edge
->call_stmt
),
936 gimple_lineno ((const_gimple
) edge
->call_stmt
),
937 cgraph_estimate_growth (edge
->callee
),
938 cgraph_edge_badness (edge
),
939 edge
->frequency
/ (double)CGRAPH_FREQ_BASE
);
941 fprintf (dump_file
," Called "HOST_WIDEST_INT_PRINT_DEC
"x\n", edge
->count
);
943 gcc_assert (edge
->aux
);
945 if (!edge
->inline_failed
)
948 /* When not having profile info ready we don't weight by any way the
949 position of call in procedure itself. This means if call of
950 function A from function B seems profitable to inline, the recursive
951 call of function A in inline copy of A in B will look profitable too
952 and we end up inlining until reaching maximal function growth. This
953 is not good idea so prohibit the recursive inlining.
955 ??? When the frequencies are taken into account we might not need this
958 We need to be cureful here, in some testcases, e.g. directivec.c in
959 libcpp, we can estimate self recursive function to have negative growth
960 for inlining completely.
964 where
= edge
->caller
;
965 while (where
->global
.inlined_to
)
967 if (where
->decl
== edge
->callee
->decl
)
969 where
= where
->callers
->caller
;
971 if (where
->global
.inlined_to
)
974 = (edge
->callee
->local
.disregard_inline_limits
975 ? CIF_RECURSIVE_INLINING
: CIF_UNSPECIFIED
);
977 fprintf (dump_file
, " inline_failed:Recursive inlining performed only for function itself.\n");
982 if (!cgraph_maybe_hot_edge_p (edge
))
983 not_good
= CIF_UNLIKELY_CALL
;
984 if (!flag_inline_functions
985 && !DECL_DECLARED_INLINE_P (edge
->callee
->decl
))
986 not_good
= CIF_NOT_DECLARED_INLINED
;
987 if (optimize_function_for_size_p (DECL_STRUCT_FUNCTION(edge
->caller
->decl
)))
988 not_good
= CIF_OPTIMIZING_FOR_SIZE
;
989 if (not_good
&& growth
> 0 && cgraph_estimate_growth (edge
->callee
) > 0)
991 if (!cgraph_recursive_inlining_p (edge
->caller
, edge
->callee
,
992 &edge
->inline_failed
))
994 edge
->inline_failed
= not_good
;
996 fprintf (dump_file
, " inline_failed:%s.\n",
997 cgraph_inline_failed_string (edge
->inline_failed
));
1001 if (!cgraph_default_inline_p (edge
->callee
, &edge
->inline_failed
))
1003 if (!cgraph_recursive_inlining_p (edge
->caller
, edge
->callee
,
1004 &edge
->inline_failed
))
1007 fprintf (dump_file
, " inline_failed:%s.\n",
1008 cgraph_inline_failed_string (edge
->inline_failed
));
1012 if (!tree_can_inline_p (edge
))
1015 fprintf (dump_file
, " inline_failed:%s.\n",
1016 cgraph_inline_failed_string (edge
->inline_failed
));
1019 if (cgraph_recursive_inlining_p (edge
->caller
, edge
->callee
,
1020 &edge
->inline_failed
))
1022 where
= edge
->caller
;
1023 if (where
->global
.inlined_to
)
1024 where
= where
->global
.inlined_to
;
1025 if (!cgraph_decide_recursive_inlining (where
,
1026 flag_indirect_inlining
1027 ? &new_indirect_edges
: NULL
))
1029 if (flag_indirect_inlining
)
1030 add_new_edges_to_heap (heap
, new_indirect_edges
);
1031 update_callee_keys (heap
, where
, updated_nodes
);
1035 struct cgraph_node
*callee
;
1036 if (edge
->call_stmt_cannot_inline_p
1037 || !cgraph_check_inline_limits (edge
->caller
, edge
->callee
,
1038 &edge
->inline_failed
, true))
1041 fprintf (dump_file
, " Not inlining into %s:%s.\n",
1042 cgraph_node_name (edge
->caller
),
1043 cgraph_inline_failed_string (edge
->inline_failed
));
1046 callee
= edge
->callee
;
1047 cgraph_mark_inline_edge (edge
, true, &new_indirect_edges
);
1048 if (flag_indirect_inlining
)
1049 add_new_edges_to_heap (heap
, new_indirect_edges
);
1051 update_callee_keys (heap
, callee
, updated_nodes
);
1053 where
= edge
->caller
;
1054 if (where
->global
.inlined_to
)
1055 where
= where
->global
.inlined_to
;
1057 /* Our profitability metric can depend on local properties
1058 such as number of inlinable calls and size of the function body.
1059 After inlining these properties might change for the function we
1060 inlined into (since it's body size changed) and for the functions
1061 called by function we inlined (since number of it inlinable callers
1063 update_caller_keys (heap
, where
, updated_nodes
);
1064 bitmap_clear (updated_nodes
);
1069 " Inlined into %s which now has size %i and self time %i,"
1070 "net change of %+i.\n",
1071 cgraph_node_name (edge
->caller
),
1072 edge
->caller
->global
.time
,
1073 edge
->caller
->global
.size
,
1074 overall_size
- old_size
);
1076 if (min_size
> overall_size
)
1078 min_size
= overall_size
;
1079 max_size
= compute_max_insns (min_size
);
1082 fprintf (dump_file
, "New minimal size reached: %i\n", min_size
);
1085 while ((edge
= (struct cgraph_edge
*) fibheap_extract_min (heap
)) != NULL
)
1087 gcc_assert (edge
->aux
);
1089 if (!edge
->callee
->local
.disregard_inline_limits
&& edge
->inline_failed
1090 && !cgraph_recursive_inlining_p (edge
->caller
, edge
->callee
,
1091 &edge
->inline_failed
))
1092 edge
->inline_failed
= CIF_INLINE_UNIT_GROWTH_LIMIT
;
1095 if (new_indirect_edges
)
1096 VEC_free (cgraph_edge_p
, heap
, new_indirect_edges
);
1097 fibheap_delete (heap
);
1098 BITMAP_FREE (updated_nodes
);
1101 /* Decide on the inlining. We do so in the topological order to avoid
1102 expenses on updating data structures. */
1105 cgraph_decide_inlining (void)
1107 struct cgraph_node
*node
;
1109 struct cgraph_node
**order
=
1110 XCNEWVEC (struct cgraph_node
*, cgraph_n_nodes
);
1113 bool redo_always_inline
= true;
1114 int initial_size
= 0;
1116 /* FIXME lto. We need to rethink how to coordinate different passes. */
1120 /* FIXME lto. We need to re-think about how the passes get invoked. */
1122 cgraph_remove_function_insertion_hook (function_insertion_hook_holder
);
1126 for (node
= cgraph_nodes
; node
; node
= node
->next
)
1129 struct cgraph_edge
*e
;
1131 gcc_assert (inline_summary (node
)->self_size
== node
->global
.size
);
1132 initial_size
+= node
->global
.size
;
1133 for (e
= node
->callees
; e
; e
= e
->next_callee
)
1134 if (max_count
< e
->count
)
1135 max_count
= e
->count
;
1136 if (max_benefit
< inline_summary (node
)->time_inlining_benefit
)
1137 max_benefit
= inline_summary (node
)->time_inlining_benefit
;
1139 gcc_assert (in_lto_p
1141 || (profile_info
&& flag_branch_probabilities
));
1142 overall_size
= initial_size
;
1144 nnodes
= cgraph_postorder (order
);
1148 "\nDeciding on inlining. Starting with size %i.\n",
1151 for (node
= cgraph_nodes
; node
; node
= node
->next
)
1155 fprintf (dump_file
, "\nInlining always_inline functions:\n");
1157 /* In the first pass mark all always_inline edges. Do this with a priority
1158 so none of our later choices will make this impossible. */
1159 while (redo_always_inline
)
1161 redo_always_inline
= false;
1162 for (i
= nnodes
- 1; i
>= 0; i
--)
1164 struct cgraph_edge
*e
, *next
;
1168 /* Handle nodes to be flattened, but don't update overall unit
1170 if (lookup_attribute ("flatten",
1171 DECL_ATTRIBUTES (node
->decl
)) != NULL
)
1175 "Flattening %s\n", cgraph_node_name (node
));
1176 cgraph_decide_inlining_incrementally (node
, INLINE_ALL
, 0);
1179 if (!node
->local
.disregard_inline_limits
)
1183 "\nConsidering %s size:%i (always inline)\n",
1184 cgraph_node_name (node
), node
->global
.size
);
1185 old_size
= overall_size
;
1186 for (e
= node
->callers
; e
; e
= next
)
1188 next
= e
->next_caller
;
1189 if (!e
->inline_failed
|| e
->call_stmt_cannot_inline_p
)
1191 if (cgraph_recursive_inlining_p (e
->caller
, e
->callee
,
1194 if (!tree_can_inline_p (e
))
1196 if (cgraph_mark_inline_edge (e
, true, NULL
))
1197 redo_always_inline
= true;
1200 " Inlined into %s which now has size %i.\n",
1201 cgraph_node_name (e
->caller
),
1202 e
->caller
->global
.size
);
1204 /* Inlining self recursive function might introduce new calls to
1205 themselves we didn't see in the loop above. Fill in the proper
1206 reason why inline failed. */
1207 for (e
= node
->callers
; e
; e
= e
->next_caller
)
1208 if (e
->inline_failed
)
1209 e
->inline_failed
= CIF_RECURSIVE_INLINING
;
1212 " Inlined for a net change of %+i size.\n",
1213 overall_size
- old_size
);
1217 cgraph_decide_inlining_of_small_functions ();
1219 if (flag_inline_functions_called_once
)
1222 fprintf (dump_file
, "\nDeciding on functions called once:\n");
1224 /* And finally decide what functions are called once. */
1225 for (i
= nnodes
- 1; i
>= 0; i
--)
1230 && !node
->callers
->next_caller
1231 && cgraph_only_called_directly_p (node
)
1232 && node
->local
.inlinable
1233 && node
->callers
->inline_failed
1234 && node
->callers
->caller
!= node
1235 && node
->callers
->caller
->global
.inlined_to
!= node
1236 && !node
->callers
->call_stmt_cannot_inline_p
1237 && !DECL_EXTERNAL (node
->decl
)
1238 && !DECL_COMDAT (node
->decl
))
1240 old_size
= overall_size
;
1244 "\nConsidering %s size %i.\n",
1245 cgraph_node_name (node
), node
->global
.size
);
1247 " Called once from %s %i insns.\n",
1248 cgraph_node_name (node
->callers
->caller
),
1249 node
->callers
->caller
->global
.size
);
1252 if (cgraph_check_inline_limits (node
->callers
->caller
, node
,
1255 cgraph_mark_inline (node
->callers
);
1258 " Inlined into %s which now has %i size"
1259 " for a net change of %+i size.\n",
1260 cgraph_node_name (node
->callers
->caller
),
1261 node
->callers
->caller
->global
.size
,
1262 overall_size
- old_size
);
1268 " Inline limit reached, not inlined.\n");
1274 /* Free ipa-prop structures if they are no longer needed. */
1275 if (flag_indirect_inlining
)
1276 free_all_ipa_structures_after_iinln ();
1280 "\nInlined %i calls, eliminated %i functions, "
1281 "size %i turned to %i size.\n\n",
1282 ncalls_inlined
, nfunctions_inlined
, initial_size
,
1288 /* Try to inline edge E from incremental inliner. MODE specifies mode
1291 We are detecting cycles by storing mode of inliner into cgraph_node last
1292 time we visited it in the recursion. In general when mode is set, we have
1293 recursive inlining, but as an special case, we want to try harder inline
1294 ALWAYS_INLINE functions: consider callgraph a->b->c->b, with a being
1295 flatten, b being always inline. Flattening 'a' will collapse
1296 a->b->c before hitting cycle. To accommodate always inline, we however
1297 need to inline a->b->c->b.
1299 So after hitting cycle first time, we switch into ALWAYS_INLINE mode and
1300 stop inlining only after hitting ALWAYS_INLINE in ALWAY_INLINE mode. */
1302 try_inline (struct cgraph_edge
*e
, enum inlining_mode mode
, int depth
)
1304 struct cgraph_node
*callee
= e
->callee
;
1305 enum inlining_mode callee_mode
= (enum inlining_mode
) (size_t) callee
->aux
;
1306 bool always_inline
= e
->callee
->local
.disregard_inline_limits
;
1307 bool inlined
= false;
1309 /* We've hit cycle? */
1312 /* It is first time we see it and we are not in ALWAY_INLINE only
1313 mode yet. and the function in question is always_inline. */
1314 if (always_inline
&& mode
!= INLINE_ALWAYS_INLINE
)
1318 indent_to (dump_file
, depth
);
1320 "Hit cycle in %s, switching to always inline only.\n",
1321 cgraph_node_name (callee
));
1323 mode
= INLINE_ALWAYS_INLINE
;
1325 /* Otherwise it is time to give up. */
1330 indent_to (dump_file
, depth
);
1332 "Not inlining %s into %s to avoid cycle.\n",
1333 cgraph_node_name (callee
),
1334 cgraph_node_name (e
->caller
));
1336 e
->inline_failed
= (e
->callee
->local
.disregard_inline_limits
1337 ? CIF_RECURSIVE_INLINING
: CIF_UNSPECIFIED
);
1342 callee
->aux
= (void *)(size_t) mode
;
1345 indent_to (dump_file
, depth
);
1346 fprintf (dump_file
, " Inlining %s into %s.\n",
1347 cgraph_node_name (e
->callee
),
1348 cgraph_node_name (e
->caller
));
1350 if (e
->inline_failed
)
1352 cgraph_mark_inline (e
);
1354 /* In order to fully inline always_inline functions, we need to
1355 recurse here, since the inlined functions might not be processed by
1356 incremental inlining at all yet.
1358 Also flattening needs to be done recursively. */
1360 if (mode
== INLINE_ALL
|| always_inline
)
1361 cgraph_decide_inlining_incrementally (e
->callee
, mode
, depth
+ 1);
1364 callee
->aux
= (void *)(size_t) callee_mode
;
1368 /* Return true when N is leaf function. Accept cheap (pure&const) builtins
1369 in leaf functions. */
1371 leaf_node_p (struct cgraph_node
*n
)
1373 struct cgraph_edge
*e
;
1374 for (e
= n
->callees
; e
; e
= e
->next_callee
)
1375 if (!DECL_BUILT_IN (e
->callee
->decl
)
1376 || (!TREE_READONLY (e
->callee
->decl
)
1377 || DECL_PURE_P (e
->callee
->decl
)))
1382 /* Decide on the inlining. We do so in the topological order to avoid
1383 expenses on updating data structures.
1384 DEPTH is depth of recursion, used only for debug output. */
1387 cgraph_decide_inlining_incrementally (struct cgraph_node
*node
,
1388 enum inlining_mode mode
,
1391 struct cgraph_edge
*e
;
1392 bool inlined
= false;
1393 cgraph_inline_failed_t failed_reason
;
1394 enum inlining_mode old_mode
;
1396 #ifdef ENABLE_CHECKING
1397 verify_cgraph_node (node
);
1400 old_mode
= (enum inlining_mode
) (size_t)node
->aux
;
1402 if (mode
!= INLINE_ALWAYS_INLINE
&& mode
!= INLINE_SIZE_NORECURSIVE
1403 && lookup_attribute ("flatten", DECL_ATTRIBUTES (node
->decl
)) != NULL
)
1407 indent_to (dump_file
, depth
);
1408 fprintf (dump_file
, "Flattening %s\n", cgraph_node_name (node
));
1413 node
->aux
= (void *)(size_t) mode
;
1415 /* First of all look for always inline functions. */
1416 if (mode
!= INLINE_SIZE_NORECURSIVE
)
1417 for (e
= node
->callees
; e
; e
= e
->next_callee
)
1419 if (!e
->callee
->local
.disregard_inline_limits
1420 && (mode
!= INLINE_ALL
|| !e
->callee
->local
.inlinable
))
1422 if (e
->call_stmt_cannot_inline_p
)
1424 /* When the edge is already inlined, we just need to recurse into
1425 it in order to fully flatten the leaves. */
1426 if (!e
->inline_failed
&& mode
== INLINE_ALL
)
1428 inlined
|= try_inline (e
, mode
, depth
);
1433 indent_to (dump_file
, depth
);
1435 "Considering to always inline inline candidate %s.\n",
1436 cgraph_node_name (e
->callee
));
1438 if (cgraph_recursive_inlining_p (node
, e
->callee
, &e
->inline_failed
))
1442 indent_to (dump_file
, depth
);
1443 fprintf (dump_file
, "Not inlining: recursive call.\n");
1447 if (!tree_can_inline_p (e
))
1451 indent_to (dump_file
, depth
);
1454 cgraph_inline_failed_string (e
->inline_failed
));
1458 if (gimple_in_ssa_p (DECL_STRUCT_FUNCTION (node
->decl
))
1459 != gimple_in_ssa_p (DECL_STRUCT_FUNCTION (e
->callee
->decl
)))
1463 indent_to (dump_file
, depth
);
1464 fprintf (dump_file
, "Not inlining: SSA form does not match.\n");
1468 if (!e
->callee
->analyzed
)
1472 indent_to (dump_file
, depth
);
1474 "Not inlining: Function body no longer available.\n");
1478 inlined
|= try_inline (e
, mode
, depth
);
1481 /* Now do the automatic inlining. */
1482 if (mode
!= INLINE_ALL
&& mode
!= INLINE_ALWAYS_INLINE
)
1483 for (e
= node
->callees
; e
; e
= e
->next_callee
)
1485 int allowed_growth
= 0;
1486 if (!e
->callee
->local
.inlinable
1487 || !e
->inline_failed
1488 || e
->callee
->local
.disregard_inline_limits
)
1491 fprintf (dump_file
, "Considering inline candidate %s.\n",
1492 cgraph_node_name (e
->callee
));
1493 if (cgraph_recursive_inlining_p (node
, e
->callee
, &e
->inline_failed
))
1497 indent_to (dump_file
, depth
);
1498 fprintf (dump_file
, "Not inlining: recursive call.\n");
1502 if (gimple_in_ssa_p (DECL_STRUCT_FUNCTION (node
->decl
))
1503 != gimple_in_ssa_p (DECL_STRUCT_FUNCTION (e
->callee
->decl
)))
1507 indent_to (dump_file
, depth
);
1508 fprintf (dump_file
, "Not inlining: SSA form does not match.\n");
1513 if (cgraph_maybe_hot_edge_p (e
) && leaf_node_p (e
->callee
)
1514 && optimize_function_for_speed_p (cfun
))
1515 allowed_growth
= PARAM_VALUE (PARAM_EARLY_INLINING_INSNS
);
1517 /* When the function body would grow and inlining the function won't
1518 eliminate the need for offline copy of the function, don't inline.
1520 if (((mode
== INLINE_SIZE
|| mode
== INLINE_SIZE_NORECURSIVE
)
1521 || (!flag_inline_functions
1522 && !DECL_DECLARED_INLINE_P (e
->callee
->decl
)))
1523 && (cgraph_estimate_size_after_inlining (1, e
->caller
, e
->callee
)
1524 > e
->caller
->global
.size
+ allowed_growth
)
1525 && cgraph_estimate_growth (e
->callee
) > allowed_growth
)
1529 indent_to (dump_file
, depth
);
1531 "Not inlining: code size would grow by %i.\n",
1532 cgraph_estimate_size_after_inlining (1, e
->caller
,
1534 - e
->caller
->global
.size
);
1538 if (!cgraph_check_inline_limits (node
, e
->callee
, &e
->inline_failed
,
1540 || e
->call_stmt_cannot_inline_p
)
1544 indent_to (dump_file
, depth
);
1545 fprintf (dump_file
, "Not inlining: %s.\n",
1546 cgraph_inline_failed_string (e
->inline_failed
));
1550 if (!e
->callee
->analyzed
)
1554 indent_to (dump_file
, depth
);
1556 "Not inlining: Function body no longer available.\n");
1560 if (!tree_can_inline_p (e
))
1564 indent_to (dump_file
, depth
);
1566 "Not inlining: %s.",
1567 cgraph_inline_failed_string (e
->inline_failed
));
1571 if (cgraph_default_inline_p (e
->callee
, &failed_reason
))
1572 inlined
|= try_inline (e
, mode
, depth
);
1574 node
->aux
= (void *)(size_t) old_mode
;
1578 /* Because inlining might remove no-longer reachable nodes, we need to
1579 keep the array visible to garbage collector to avoid reading collected
1582 static GTY ((length ("nnodes"))) struct cgraph_node
**order
;
1584 /* Do inlining of small functions. Doing so early helps profiling and other
1585 passes to be somewhat more effective and avoids some code duplication in
1586 later real inlining pass for testcases with very many function calls. */
1588 cgraph_early_inlining (void)
1590 struct cgraph_node
*node
= cgraph_node (current_function_decl
);
1591 unsigned int todo
= 0;
1594 if (sorrycount
|| errorcount
)
1596 while (cgraph_decide_inlining_incrementally (node
,
1598 ? INLINE_SIZE_NORECURSIVE
: INLINE_SIZE
, 0)
1599 && iterations
< PARAM_VALUE (PARAM_EARLY_INLINER_MAX_ITERATIONS
))
1601 timevar_push (TV_INTEGRATION
);
1602 todo
|= optimize_inline_calls (current_function_decl
);
1604 timevar_pop (TV_INTEGRATION
);
1607 fprintf (dump_file
, "Iterations: %i\n", iterations
);
1608 cfun
->always_inline_functions_inlined
= true;
1612 /* When inlining shall be performed. */
1614 cgraph_gate_early_inlining (void)
1616 return flag_early_inlining
;
1619 struct gimple_opt_pass pass_early_inline
=
1623 "einline", /* name */
1624 cgraph_gate_early_inlining
, /* gate */
1625 cgraph_early_inlining
, /* execute */
1628 0, /* static_pass_number */
1629 TV_INLINE_HEURISTICS
, /* tv_id */
1630 0, /* properties_required */
1631 0, /* properties_provided */
1632 0, /* properties_destroyed */
1633 0, /* todo_flags_start */
1634 TODO_dump_func
/* todo_flags_finish */
1638 /* When inlining shall be performed. */
1640 cgraph_gate_ipa_early_inlining (void)
1642 return (flag_early_inlining
1644 && (flag_branch_probabilities
|| flag_test_coverage
1645 || profile_arc_flag
));
1648 /* IPA pass wrapper for early inlining pass. We need to run early inlining
1649 before tree profiling so we have stand alone IPA pass for doing so. */
1650 struct simple_ipa_opt_pass pass_ipa_early_inline
=
1654 "einline_ipa", /* name */
1655 cgraph_gate_ipa_early_inlining
, /* gate */
1659 0, /* static_pass_number */
1660 TV_INLINE_HEURISTICS
, /* tv_id */
1661 0, /* properties_required */
1662 0, /* properties_provided */
1663 0, /* properties_destroyed */
1664 0, /* todo_flags_start */
1665 TODO_dump_cgraph
/* todo_flags_finish */
1669 /* See if statement might disappear after inlining. We are not terribly
1670 sophisficated, basically looking for simple abstraction penalty wrappers. */
1673 likely_eliminated_by_inlining_p (gimple stmt
)
1675 enum gimple_code code
= gimple_code (stmt
);
1681 if (gimple_num_ops (stmt
) != 2)
1684 /* Casts of parameters, loads from parameters passed by reference
1685 and stores to return value or parameters are probably free after
1687 if (gimple_assign_rhs_code (stmt
) == CONVERT_EXPR
1688 || gimple_assign_rhs_code (stmt
) == NOP_EXPR
1689 || gimple_assign_rhs_code (stmt
) == VIEW_CONVERT_EXPR
1690 || gimple_assign_rhs_class (stmt
) == GIMPLE_SINGLE_RHS
)
1692 tree rhs
= gimple_assign_rhs1 (stmt
);
1693 tree lhs
= gimple_assign_lhs (stmt
);
1694 tree inner_rhs
= rhs
;
1695 tree inner_lhs
= lhs
;
1696 bool rhs_free
= false;
1697 bool lhs_free
= false;
1699 while (handled_component_p (inner_lhs
) || TREE_CODE (inner_lhs
) == INDIRECT_REF
)
1700 inner_lhs
= TREE_OPERAND (inner_lhs
, 0);
1701 while (handled_component_p (inner_rhs
)
1702 || TREE_CODE (inner_rhs
) == ADDR_EXPR
|| TREE_CODE (inner_rhs
) == INDIRECT_REF
)
1703 inner_rhs
= TREE_OPERAND (inner_rhs
, 0);
1706 if (TREE_CODE (inner_rhs
) == PARM_DECL
1707 || (TREE_CODE (inner_rhs
) == SSA_NAME
1708 && SSA_NAME_IS_DEFAULT_DEF (inner_rhs
)
1709 && TREE_CODE (SSA_NAME_VAR (inner_rhs
)) == PARM_DECL
))
1711 if (rhs_free
&& is_gimple_reg (lhs
))
1713 if (((TREE_CODE (inner_lhs
) == PARM_DECL
1714 || (TREE_CODE (inner_lhs
) == SSA_NAME
1715 && SSA_NAME_IS_DEFAULT_DEF (inner_lhs
)
1716 && TREE_CODE (SSA_NAME_VAR (inner_lhs
)) == PARM_DECL
))
1717 && inner_lhs
!= lhs
)
1718 || TREE_CODE (inner_lhs
) == RESULT_DECL
1719 || (TREE_CODE (inner_lhs
) == SSA_NAME
1720 && TREE_CODE (SSA_NAME_VAR (inner_lhs
)) == RESULT_DECL
))
1722 if (lhs_free
&& (is_gimple_reg (rhs
) || is_gimple_min_invariant (rhs
)))
1724 if (lhs_free
&& rhs_free
)
1733 /* Compute function body size parameters for NODE. */
1736 estimate_function_body_sizes (struct cgraph_node
*node
)
1739 gcov_type time_inlining_benefit
= 0;
1741 int size_inlining_benefit
= 0;
1743 gimple_stmt_iterator bsi
;
1744 struct function
*my_function
= DECL_STRUCT_FUNCTION (node
->decl
);
1747 tree funtype
= TREE_TYPE (node
->decl
);
1750 fprintf (dump_file
, "Analyzing function body size: %s\n",
1751 cgraph_node_name (node
));
1753 gcc_assert (my_function
&& my_function
->cfg
);
1754 FOR_EACH_BB_FN (bb
, my_function
)
1756 freq
= compute_call_stmt_bb_frequency (node
->decl
, bb
);
1757 for (bsi
= gsi_start_bb (bb
); !gsi_end_p (bsi
); gsi_next (&bsi
))
1759 gimple stmt
= gsi_stmt (bsi
);
1760 int this_size
= estimate_num_insns (stmt
, &eni_size_weights
);
1761 int this_time
= estimate_num_insns (stmt
, &eni_time_weights
);
1763 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1765 fprintf (dump_file
, " freq:%6i size:%3i time:%3i ",
1766 freq
, this_size
, this_time
);
1767 print_gimple_stmt (dump_file
, stmt
, 0, 0);
1772 if (likely_eliminated_by_inlining_p (stmt
))
1774 size_inlining_benefit
+= this_size
;
1775 time_inlining_benefit
+= this_time
;
1776 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1777 fprintf (dump_file
, " Likely eliminated\n");
1779 gcc_assert (time
>= 0);
1780 gcc_assert (size
>= 0);
1783 time
= (time
+ CGRAPH_FREQ_BASE
/ 2) / CGRAPH_FREQ_BASE
;
1784 time_inlining_benefit
= ((time_inlining_benefit
+ CGRAPH_FREQ_BASE
/ 2)
1785 / CGRAPH_FREQ_BASE
);
1787 fprintf (dump_file
, "Overall function body time: %i-%i size: %i-%i\n",
1788 (int)time
, (int)time_inlining_benefit
,
1789 size
, size_inlining_benefit
);
1790 time_inlining_benefit
+= eni_time_weights
.call_cost
;
1791 size_inlining_benefit
+= eni_size_weights
.call_cost
;
1792 if (!VOID_TYPE_P (TREE_TYPE (funtype
)))
1794 int cost
= estimate_move_cost (TREE_TYPE (funtype
));
1795 time_inlining_benefit
+= cost
;
1796 size_inlining_benefit
+= cost
;
1798 for (arg
= DECL_ARGUMENTS (node
->decl
); arg
; arg
= TREE_CHAIN (arg
))
1799 if (!VOID_TYPE_P (TREE_TYPE (arg
)))
1801 int cost
= estimate_move_cost (TREE_TYPE (arg
));
1802 time_inlining_benefit
+= cost
;
1803 size_inlining_benefit
+= cost
;
1805 if (time_inlining_benefit
> MAX_TIME
)
1806 time_inlining_benefit
= MAX_TIME
;
1807 if (time
> MAX_TIME
)
1809 inline_summary (node
)->self_time
= time
;
1810 inline_summary (node
)->self_size
= size
;
1812 fprintf (dump_file
, "With function call overhead time: %i-%i size: %i-%i\n",
1813 (int)time
, (int)time_inlining_benefit
,
1814 size
, size_inlining_benefit
);
1815 inline_summary (node
)->time_inlining_benefit
= time_inlining_benefit
;
1816 inline_summary (node
)->size_inlining_benefit
= size_inlining_benefit
;
1819 /* Compute parameters of functions used by inliner. */
1821 compute_inline_parameters (struct cgraph_node
*node
)
1823 HOST_WIDE_INT self_stack_size
;
1825 gcc_assert (!node
->global
.inlined_to
);
1827 /* Estimate the stack size for the function. But not at -O0
1828 because estimated_stack_frame_size is a quadratic problem. */
1829 self_stack_size
= optimize
? estimated_stack_frame_size () : 0;
1830 inline_summary (node
)->estimated_self_stack_size
= self_stack_size
;
1831 node
->global
.estimated_stack_size
= self_stack_size
;
1832 node
->global
.stack_frame_offset
= 0;
1834 /* Can this function be inlined at all? */
1835 node
->local
.inlinable
= tree_inlinable_function_p (current_function_decl
);
1836 if (node
->local
.inlinable
&& !node
->local
.disregard_inline_limits
)
1837 node
->local
.disregard_inline_limits
1838 = DECL_DISREGARD_INLINE_LIMITS (current_function_decl
);
1839 estimate_function_body_sizes (node
);
1840 /* Inlining characteristics are maintained by the cgraph_mark_inline. */
1841 node
->global
.time
= inline_summary (node
)->self_time
;
1842 node
->global
.size
= inline_summary (node
)->self_size
;
1847 /* Compute parameters of functions used by inliner using
1848 current_function_decl. */
1850 compute_inline_parameters_for_current (void)
1852 compute_inline_parameters (cgraph_node (current_function_decl
));
1856 struct gimple_opt_pass pass_inline_parameters
=
1860 "inline_param", /* name */
1862 compute_inline_parameters_for_current
,/* execute */
1865 0, /* static_pass_number */
1866 TV_INLINE_HEURISTICS
, /* tv_id */
1867 0, /* properties_required */
1868 0, /* properties_provided */
1869 0, /* properties_destroyed */
1870 0, /* todo_flags_start */
1871 0 /* todo_flags_finish */
1875 /* This function performs intraprocedural analyzis in NODE that is required to
1876 inline indirect calls. */
1878 inline_indirect_intraprocedural_analysis (struct cgraph_node
*node
)
1880 struct cgraph_edge
*cs
;
1884 ipa_initialize_node_params (node
);
1885 ipa_detect_param_modifications (node
);
1887 ipa_analyze_params_uses (node
);
1890 for (cs
= node
->callees
; cs
; cs
= cs
->next_callee
)
1892 ipa_count_arguments (cs
);
1893 ipa_compute_jump_functions (cs
);
1898 ipa_print_node_params (dump_file
, node
);
1899 ipa_print_node_jump_functions (dump_file
, node
);
1903 /* Note function body size. */
1905 analyze_function (struct cgraph_node
*node
)
1907 push_cfun (DECL_STRUCT_FUNCTION (node
->decl
));
1908 current_function_decl
= node
->decl
;
1910 compute_inline_parameters (node
);
1911 if (flag_indirect_inlining
)
1912 inline_indirect_intraprocedural_analysis (node
);
1914 current_function_decl
= NULL
;
1918 /* Called when new function is inserted to callgraph late. */
1920 add_new_function (struct cgraph_node
*node
, void *data ATTRIBUTE_UNUSED
)
1922 analyze_function (node
);
1925 /* Note function body size. */
1927 inline_generate_summary (void)
1929 struct cgraph_node
*node
;
1931 /* FIXME lto. We should not run any IPA-summary pass in LTRANS mode. */
1935 function_insertion_hook_holder
=
1936 cgraph_add_function_insertion_hook (&add_new_function
, NULL
);
1938 if (flag_indirect_inlining
)
1940 ipa_register_cgraph_hooks ();
1941 ipa_check_create_node_params ();
1942 ipa_check_create_edge_args ();
1945 for (node
= cgraph_nodes
; node
; node
= node
->next
)
1947 analyze_function (node
);
1952 /* Apply inline plan to function. */
1954 inline_transform (struct cgraph_node
*node
)
1956 unsigned int todo
= 0;
1957 struct cgraph_edge
*e
;
1959 /* We might need the body of this function so that we can expand
1960 it inline somewhere else. */
1961 if (cgraph_preserve_function_body_p (node
->decl
))
1962 save_inline_function_body (node
);
1964 for (e
= node
->callees
; e
; e
= e
->next_callee
)
1965 if (!e
->inline_failed
|| warn_inline
)
1970 timevar_push (TV_INTEGRATION
);
1971 todo
= optimize_inline_calls (current_function_decl
);
1972 timevar_pop (TV_INTEGRATION
);
1974 cfun
->always_inline_functions_inlined
= true;
1975 cfun
->after_inlining
= true;
1976 return todo
| execute_fixup_cfg ();
1979 struct ipa_opt_pass_d pass_ipa_inline
=
1983 "inline", /* name */
1985 cgraph_decide_inlining
, /* execute */
1988 0, /* static_pass_number */
1989 TV_INLINE_HEURISTICS
, /* tv_id */
1990 0, /* properties_required */
1991 0, /* properties_provided */
1992 0, /* properties_destroyed */
1993 TODO_remove_functions
, /* todo_flags_finish */
1994 TODO_dump_cgraph
| TODO_dump_func
1995 | TODO_remove_functions
/* todo_flags_finish */
1997 inline_generate_summary
, /* generate_summary */
1998 NULL
, /* write_summary */
1999 NULL
, /* read_summary */
2000 NULL
, /* function_read_summary */
2002 inline_transform
, /* function_transform */
2003 NULL
, /* variable_transform */
2007 #include "gt-ipa-inline.h"