1 /* Inlining decision heuristics.
2 Copyright (C) 2003, 2004, 2007, 2008 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 in non-unit-at-a-time mode.
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 This is the main inlining pass in non-unit-at-a-time.
87 With unit-at-a-time the pass is run during conversion into SSA form.
88 Only functions already converted into SSA form are inlined, so the
89 conversion must happen in topological order on the callgraph (that is
90 maintained by pass manager). The functions after inlining are early
91 optimized so the early inliner sees unoptimized function itself, but
92 all considered callees are already optimized allowing it to unfold
93 abstraction penalty on C++ effectively and cheaply.
95 pass_ipa_early_inlining
97 With profiling, the early inlining is also necessary to reduce
98 instrumentation costs on program with high abstraction penalty (doing
99 many redundant calls). This can't happen in parallel with early
100 optimization and profile instrumentation, because we would end up
101 re-instrumenting already instrumented function bodies we brought in via
104 To avoid this, this pass is executed as IPA pass before profiling. It is
105 simple wrapper to pass_early_inlining and ensures first inlining.
109 This is the main pass implementing simple greedy algorithm to do inlining
110 of small functions that results in overall growth of compilation unit and
111 inlining of functions called once. The pass compute just so called inline
112 plan (representation of inlining to be done in callgraph) and unlike early
113 inlining it is not performing the inlining itself.
117 This pass performs actual inlining according to pass_ipa_inline on given
118 function. Possible the function body before inlining is saved when it is
119 needed for further inlining later.
124 #include "coretypes.h"
127 #include "tree-inline.h"
128 #include "langhooks.h"
131 #include "diagnostic.h"
136 #include "tree-pass.h"
138 #include "coverage.h"
140 #include "tree-flow.h"
142 #include "ipa-prop.h"
144 /* Mode incremental inliner operate on:
146 In ALWAYS_INLINE only functions marked
147 always_inline are inlined. This mode is used after detecting cycle during
150 In SIZE mode, only functions that reduce function body size after inlining
151 are inlined, this is used during early inlining.
153 In SPEED mode, all small functions are inlined. This might result in
154 unbounded growth of compilation unit and is used only in non-unit-at-a-time
157 in ALL mode, everything is inlined. This is used during flattening. */
160 INLINE_ALWAYS_INLINE
,
166 cgraph_decide_inlining_incrementally (struct cgraph_node
*, enum inlining_mode
,
170 /* Statistics we collect about inlining algorithm. */
171 static int ncalls_inlined
;
172 static int nfunctions_inlined
;
173 static int overall_insns
;
174 static gcov_type max_count
;
176 static inline struct inline_summary
*
177 inline_summary (struct cgraph_node
*node
)
179 return &node
->local
.inline_summary
;
182 /* Estimate size of the function after inlining WHAT into TO. */
185 cgraph_estimate_size_after_inlining (int times
, struct cgraph_node
*to
,
186 struct cgraph_node
*what
)
189 tree fndecl
= what
->decl
, arg
;
190 int call_insns
= PARAM_VALUE (PARAM_INLINE_CALL_COST
);
192 for (arg
= DECL_ARGUMENTS (fndecl
); arg
; arg
= TREE_CHAIN (arg
))
193 call_insns
+= estimate_move_cost (TREE_TYPE (arg
));
194 size
= (what
->global
.insns
- call_insns
) * times
+ to
->global
.insns
;
195 gcc_assert (size
>= 0);
199 /* E is expected to be an edge being inlined. Clone destination node of
200 the edge and redirect it to the new clone.
201 DUPLICATE is used for bookkeeping on whether we are actually creating new
202 clones or re-using node originally representing out-of-line function call.
205 cgraph_clone_inlined_nodes (struct cgraph_edge
*e
, bool duplicate
, bool update_original
)
210 /* We may eliminate the need for out-of-line copy to be output.
211 In that case just go ahead and re-use it. */
212 if (!e
->callee
->callers
->next_caller
213 && !e
->callee
->needed
215 && flag_unit_at_a_time
)
217 gcc_assert (!e
->callee
->global
.inlined_to
);
218 if (DECL_SAVED_TREE (e
->callee
->decl
))
219 overall_insns
-= e
->callee
->global
.insns
, nfunctions_inlined
++;
224 struct cgraph_node
*n
;
225 n
= cgraph_clone_node (e
->callee
, e
->count
, e
->frequency
, e
->loop_nest
,
227 cgraph_redirect_edge_callee (e
, n
);
231 if (e
->caller
->global
.inlined_to
)
232 e
->callee
->global
.inlined_to
= e
->caller
->global
.inlined_to
;
234 e
->callee
->global
.inlined_to
= e
->caller
;
235 e
->callee
->global
.stack_frame_offset
236 = e
->caller
->global
.stack_frame_offset
237 + inline_summary (e
->caller
)->estimated_self_stack_size
;
238 peak
= e
->callee
->global
.stack_frame_offset
239 + inline_summary (e
->callee
)->estimated_self_stack_size
;
240 if (e
->callee
->global
.inlined_to
->global
.estimated_stack_size
< peak
)
241 e
->callee
->global
.inlined_to
->global
.estimated_stack_size
= peak
;
243 /* Recursively clone all bodies. */
244 for (e
= e
->callee
->callees
; e
; e
= e
->next_callee
)
245 if (!e
->inline_failed
)
246 cgraph_clone_inlined_nodes (e
, duplicate
, update_original
);
249 /* Mark edge E as inlined and update callgraph accordingly.
250 UPDATE_ORIGINAL specify whether profile of original function should be
254 cgraph_mark_inline_edge (struct cgraph_edge
*e
, bool update_original
)
256 int old_insns
= 0, new_insns
= 0;
257 struct cgraph_node
*to
= NULL
, *what
;
259 if (e
->callee
->inline_decl
)
260 cgraph_redirect_edge_callee (e
, cgraph_node (e
->callee
->inline_decl
));
262 gcc_assert (e
->inline_failed
);
263 e
->inline_failed
= NULL
;
265 if (!e
->callee
->global
.inlined
&& flag_unit_at_a_time
)
266 DECL_POSSIBLY_INLINED (e
->callee
->decl
) = true;
267 e
->callee
->global
.inlined
= true;
269 cgraph_clone_inlined_nodes (e
, true, update_original
);
273 /* Now update size of caller and all functions caller is inlined into. */
274 for (;e
&& !e
->inline_failed
; e
= e
->caller
->callers
)
276 old_insns
= e
->caller
->global
.insns
;
277 new_insns
= cgraph_estimate_size_after_inlining (1, e
->caller
,
279 gcc_assert (new_insns
>= 0);
281 to
->global
.insns
= new_insns
;
283 gcc_assert (what
->global
.inlined_to
== to
);
284 if (new_insns
> old_insns
)
285 overall_insns
+= new_insns
- old_insns
;
289 /* Mark all calls of EDGE->CALLEE inlined into EDGE->CALLER.
290 Return following unredirected edge in the list of callers
293 static struct cgraph_edge
*
294 cgraph_mark_inline (struct cgraph_edge
*edge
)
296 struct cgraph_node
*to
= edge
->caller
;
297 struct cgraph_node
*what
= edge
->callee
;
298 struct cgraph_edge
*e
, *next
;
300 gcc_assert (!CALL_STMT_CANNOT_INLINE_P (edge
->call_stmt
));
301 /* Look for all calls, mark them inline and clone recursively
302 all inlined functions. */
303 for (e
= what
->callers
; e
; e
= next
)
305 next
= e
->next_caller
;
306 if (e
->caller
== to
&& e
->inline_failed
)
308 cgraph_mark_inline_edge (e
, true);
317 /* Estimate the growth caused by inlining NODE into all callees. */
320 cgraph_estimate_growth (struct cgraph_node
*node
)
323 struct cgraph_edge
*e
;
324 if (node
->global
.estimated_growth
!= INT_MIN
)
325 return node
->global
.estimated_growth
;
327 for (e
= node
->callers
; e
; e
= e
->next_caller
)
328 if (e
->inline_failed
)
329 growth
+= (cgraph_estimate_size_after_inlining (1, e
->caller
, node
)
330 - e
->caller
->global
.insns
);
332 /* ??? Wrong for self recursive functions or cases where we decide to not
333 inline for different reasons, but it is not big deal as in that case
334 we will keep the body around, but we will also avoid some inlining. */
335 if (!node
->needed
&& !DECL_EXTERNAL (node
->decl
))
336 growth
-= node
->global
.insns
;
338 node
->global
.estimated_growth
= growth
;
342 /* Return false when inlining WHAT into TO is not good idea
343 as it would cause too large growth of function bodies.
344 When ONE_ONLY is true, assume that only one call site is going
345 to be inlined, otherwise figure out how many call sites in
346 TO calls WHAT and verify that all can be inlined.
350 cgraph_check_inline_limits (struct cgraph_node
*to
, struct cgraph_node
*what
,
351 const char **reason
, bool one_only
)
354 struct cgraph_edge
*e
;
357 HOST_WIDE_INT stack_size_limit
, inlined_stack
;
362 for (e
= to
->callees
; e
; e
= e
->next_callee
)
363 if (e
->callee
== what
)
366 if (to
->global
.inlined_to
)
367 to
= to
->global
.inlined_to
;
369 /* When inlining large function body called once into small function,
370 take the inlined function as base for limiting the growth. */
371 if (inline_summary (to
)->self_insns
> inline_summary(what
)->self_insns
)
372 limit
= inline_summary (to
)->self_insns
;
374 limit
= inline_summary (what
)->self_insns
;
376 limit
+= limit
* PARAM_VALUE (PARAM_LARGE_FUNCTION_GROWTH
) / 100;
378 /* Check the size after inlining against the function limits. But allow
379 the function to shrink if it went over the limits by forced inlining. */
380 newsize
= cgraph_estimate_size_after_inlining (times
, to
, what
);
381 if (newsize
>= to
->global
.insns
382 && newsize
> PARAM_VALUE (PARAM_LARGE_FUNCTION_INSNS
)
386 *reason
= N_("--param large-function-growth limit reached");
390 stack_size_limit
= inline_summary (to
)->estimated_self_stack_size
;
392 stack_size_limit
+= stack_size_limit
* PARAM_VALUE (PARAM_STACK_FRAME_GROWTH
) / 100;
394 inlined_stack
= (to
->global
.stack_frame_offset
395 + inline_summary (to
)->estimated_self_stack_size
396 + what
->global
.estimated_stack_size
);
397 if (inlined_stack
> stack_size_limit
398 && inlined_stack
> PARAM_VALUE (PARAM_LARGE_STACK_FRAME
))
401 *reason
= N_("--param large-stack-frame-growth limit reached");
407 /* Return true when function N is small enough to be inlined. */
410 cgraph_default_inline_p (struct cgraph_node
*n
, const char **reason
)
415 decl
= n
->inline_decl
;
416 if (!flag_inline_small_functions
&& !DECL_DECLARED_INLINE_P (decl
))
419 *reason
= N_("function not inline candidate");
423 if (!DECL_STRUCT_FUNCTION (decl
)->cfg
)
426 *reason
= N_("function body not available");
430 if (DECL_DECLARED_INLINE_P (decl
))
432 if (n
->global
.insns
>= MAX_INLINE_INSNS_SINGLE
)
435 *reason
= N_("--param max-inline-insns-single limit reached");
441 if (n
->global
.insns
>= MAX_INLINE_INSNS_AUTO
)
444 *reason
= N_("--param max-inline-insns-auto limit reached");
452 /* Return true when inlining WHAT would create recursive inlining.
453 We call recursive inlining all cases where same function appears more than
454 once in the single recursion nest path in the inline graph. */
457 cgraph_recursive_inlining_p (struct cgraph_node
*to
,
458 struct cgraph_node
*what
,
462 if (to
->global
.inlined_to
)
463 recursive
= what
->decl
== to
->global
.inlined_to
->decl
;
465 recursive
= what
->decl
== to
->decl
;
466 /* Marking recursive function inline has sane semantic and thus we should
468 if (recursive
&& reason
)
469 *reason
= (what
->local
.disregard_inline_limits
470 ? N_("recursive inlining") : "");
474 /* Return true if the call can be hot. */
476 cgraph_maybe_hot_edge_p (struct cgraph_edge
*edge
)
478 if (profile_info
&& flag_branch_probabilities
480 <= profile_info
->sum_max
/ PARAM_VALUE (HOT_BB_COUNT_FRACTION
)))
482 if (lookup_attribute ("cold", DECL_ATTRIBUTES (edge
->callee
->decl
))
483 || lookup_attribute ("cold", DECL_ATTRIBUTES (edge
->caller
->decl
)))
485 if (lookup_attribute ("hot", DECL_ATTRIBUTES (edge
->caller
->decl
)))
487 if (flag_guess_branch_prob
488 && edge
->frequency
< (CGRAPH_FREQ_MAX
489 / PARAM_VALUE (HOT_BB_FREQUENCY_FRACTION
)))
494 /* A cost model driving the inlining heuristics in a way so the edges with
495 smallest badness are inlined first. After each inlining is performed
496 the costs of all caller edges of nodes affected are recomputed so the
497 metrics may accurately depend on values such as number of inlinable callers
498 of the function or function body size. */
501 cgraph_edge_badness (struct cgraph_edge
*edge
)
505 cgraph_estimate_size_after_inlining (1, edge
->caller
, edge
->callee
);
507 growth
-= edge
->caller
->global
.insns
;
509 /* Always prefer inlining saving code size. */
511 badness
= INT_MIN
- growth
;
513 /* When profiling is available, base priorities -(#calls / growth).
514 So we optimize for overall number of "executed" inlined calls. */
516 badness
= ((int)((double)edge
->count
* INT_MIN
/ max_count
)) / growth
;
518 /* When function local profile is available, base priorities on
519 growth / frequency, so we optimize for overall frequency of inlined
520 calls. This is not too accurate since while the call might be frequent
521 within function, the function itself is infrequent.
523 Other objective to optimize for is number of different calls inlined.
524 We add the estimated growth after inlining all functions to bias the
525 priorities slightly in this direction (so fewer times called functions
526 of the same size gets priority). */
527 else if (flag_guess_branch_prob
)
529 int div
= edge
->frequency
* 100 / CGRAPH_FREQ_BASE
;
531 cgraph_estimate_size_after_inlining (1, edge
->caller
, edge
->callee
);
532 growth
-= edge
->caller
->global
.insns
;
533 badness
= growth
* 256;
535 /* Decrease badness if call is nested. */
536 /* Compress the range so we don't overflow. */
538 div
= 256 + ceil_log2 (div
) - 8;
543 badness
+= cgraph_estimate_growth (edge
->callee
);
545 /* When function local profile is not available or it does not give
546 useful information (ie frequency is zero), base the cost on
547 loop nest and overall size growth, so we optimize for overall number
548 of functions fully inlined in program. */
551 int nest
= MIN (edge
->loop_nest
, 8);
552 badness
= cgraph_estimate_growth (edge
->callee
) * 256;
554 /* Decrease badness if call is nested. */
562 /* Make recursive inlining happen always after other inlining is done. */
563 if (cgraph_recursive_inlining_p (edge
->caller
, edge
->callee
, NULL
))
569 /* Recompute heap nodes for each of caller edge. */
572 update_caller_keys (fibheap_t heap
, struct cgraph_node
*node
,
573 bitmap updated_nodes
)
575 struct cgraph_edge
*edge
;
576 const char *failed_reason
;
578 if (!node
->local
.inlinable
|| node
->local
.disregard_inline_limits
579 || node
->global
.inlined_to
)
581 if (bitmap_bit_p (updated_nodes
, node
->uid
))
583 bitmap_set_bit (updated_nodes
, node
->uid
);
584 node
->global
.estimated_growth
= INT_MIN
;
586 if (!node
->local
.inlinable
)
588 /* Prune out edges we won't inline into anymore. */
589 if (!cgraph_default_inline_p (node
, &failed_reason
))
591 for (edge
= node
->callers
; edge
; edge
= edge
->next_caller
)
594 fibheap_delete_node (heap
, (fibnode_t
) edge
->aux
);
596 if (edge
->inline_failed
)
597 edge
->inline_failed
= failed_reason
;
602 for (edge
= node
->callers
; edge
; edge
= edge
->next_caller
)
603 if (edge
->inline_failed
)
605 int badness
= cgraph_edge_badness (edge
);
608 fibnode_t n
= (fibnode_t
) edge
->aux
;
609 gcc_assert (n
->data
== edge
);
610 if (n
->key
== badness
)
613 /* fibheap_replace_key only increase the keys. */
614 if (fibheap_replace_key (heap
, n
, badness
))
616 fibheap_delete_node (heap
, (fibnode_t
) edge
->aux
);
618 edge
->aux
= fibheap_insert (heap
, badness
, edge
);
622 /* Recompute heap nodes for each of caller edges of each of callees. */
625 update_callee_keys (fibheap_t heap
, struct cgraph_node
*node
,
626 bitmap updated_nodes
)
628 struct cgraph_edge
*e
;
629 node
->global
.estimated_growth
= INT_MIN
;
631 for (e
= node
->callees
; e
; e
= e
->next_callee
)
632 if (e
->inline_failed
)
633 update_caller_keys (heap
, e
->callee
, updated_nodes
);
634 else if (!e
->inline_failed
)
635 update_callee_keys (heap
, e
->callee
, updated_nodes
);
638 /* Enqueue all recursive calls from NODE into priority queue depending on
639 how likely we want to recursively inline the call. */
642 lookup_recursive_calls (struct cgraph_node
*node
, struct cgraph_node
*where
,
646 struct cgraph_edge
*e
;
647 for (e
= where
->callees
; e
; e
= e
->next_callee
)
648 if (e
->callee
== node
)
650 /* When profile feedback is available, prioritize by expected number
651 of calls. Without profile feedback we maintain simple queue
652 to order candidates via recursive depths. */
653 fibheap_insert (heap
,
654 !max_count
? priority
++
655 : -(e
->count
/ ((max_count
+ (1<<24) - 1) / (1<<24))),
658 for (e
= where
->callees
; e
; e
= e
->next_callee
)
659 if (!e
->inline_failed
)
660 lookup_recursive_calls (node
, e
->callee
, heap
);
663 /* Decide on recursive inlining: in the case function has recursive calls,
664 inline until body size reaches given argument. If any new indirect edges
665 are discovered in the process, add them to NEW_EDGES, unless it is NULL. */
668 cgraph_decide_recursive_inlining (struct cgraph_node
*node
,
669 VEC (cgraph_edge_p
, heap
) *new_edges
)
671 int limit
= PARAM_VALUE (PARAM_MAX_INLINE_INSNS_RECURSIVE_AUTO
);
672 int max_depth
= PARAM_VALUE (PARAM_MAX_INLINE_RECURSIVE_DEPTH_AUTO
);
673 int probability
= PARAM_VALUE (PARAM_MIN_INLINE_RECURSIVE_PROBABILITY
);
675 struct cgraph_edge
*e
;
676 struct cgraph_node
*master_clone
, *next
;
681 || (!flag_inline_functions
&& !DECL_DECLARED_INLINE_P (node
->decl
)))
684 if (DECL_DECLARED_INLINE_P (node
->decl
))
686 limit
= PARAM_VALUE (PARAM_MAX_INLINE_INSNS_RECURSIVE
);
687 max_depth
= PARAM_VALUE (PARAM_MAX_INLINE_RECURSIVE_DEPTH
);
690 /* Make sure that function is small enough to be considered for inlining. */
692 || cgraph_estimate_size_after_inlining (1, node
, node
) >= limit
)
694 heap
= fibheap_new ();
695 lookup_recursive_calls (node
, node
, heap
);
696 if (fibheap_empty (heap
))
698 fibheap_delete (heap
);
704 " Performing recursive inlining on %s\n",
705 cgraph_node_name (node
));
707 /* We need original clone to copy around. */
708 master_clone
= cgraph_clone_node (node
, node
->count
, CGRAPH_FREQ_BASE
, 1, false);
709 master_clone
->needed
= true;
710 for (e
= master_clone
->callees
; e
; e
= e
->next_callee
)
711 if (!e
->inline_failed
)
712 cgraph_clone_inlined_nodes (e
, true, false);
714 /* Do the inlining and update list of recursive call during process. */
715 while (!fibheap_empty (heap
)
716 && (cgraph_estimate_size_after_inlining (1, node
, master_clone
)
719 struct cgraph_edge
*curr
720 = (struct cgraph_edge
*) fibheap_extract_min (heap
);
721 struct cgraph_node
*cnode
;
724 for (cnode
= curr
->caller
;
725 cnode
->global
.inlined_to
; cnode
= cnode
->callers
->caller
)
726 if (node
->decl
== curr
->callee
->decl
)
728 if (depth
> max_depth
)
732 " maximal depth reached\n");
738 if (!cgraph_maybe_hot_edge_p (curr
))
741 fprintf (dump_file
, " Not inlining cold call\n");
744 if (curr
->count
* 100 / node
->count
< probability
)
748 " Probability of edge is too small\n");
756 " Inlining call of depth %i", depth
);
759 fprintf (dump_file
, " called approx. %.2f times per call",
760 (double)curr
->count
/ node
->count
);
762 fprintf (dump_file
, "\n");
764 cgraph_redirect_edge_callee (curr
, master_clone
);
765 cgraph_mark_inline_edge (curr
, false);
766 if (flag_indirect_inlining
)
767 ipa_propagate_indirect_call_infos (curr
, new_edges
);
768 lookup_recursive_calls (node
, curr
->callee
, heap
);
771 if (!fibheap_empty (heap
) && dump_file
)
772 fprintf (dump_file
, " Recursive inlining growth limit met.\n");
774 fibheap_delete (heap
);
777 "\n Inlined %i times, body grown from %i to %i insns\n", n
,
778 master_clone
->global
.insns
, node
->global
.insns
);
780 /* Remove master clone we used for inlining. We rely that clones inlined
781 into master clone gets queued just before master clone so we don't
783 for (node
= cgraph_nodes
; node
!= master_clone
;
787 if (node
->global
.inlined_to
== master_clone
)
788 cgraph_remove_node (node
);
790 cgraph_remove_node (master_clone
);
791 /* FIXME: Recursive inlining actually reduces number of calls of the
792 function. At this place we should probably walk the function and
793 inline clones and compensate the counts accordingly. This probably
794 doesn't matter much in practice. */
798 /* Set inline_failed for all callers of given function to REASON. */
801 cgraph_set_inline_failed (struct cgraph_node
*node
, const char *reason
)
803 struct cgraph_edge
*e
;
806 fprintf (dump_file
, "Inlining failed: %s\n", reason
);
807 for (e
= node
->callers
; e
; e
= e
->next_caller
)
808 if (e
->inline_failed
)
809 e
->inline_failed
= reason
;
812 /* Given whole compilation unit estimate of INSNS, compute how large we can
813 allow the unit to grow. */
815 compute_max_insns (int insns
)
817 int max_insns
= insns
;
818 if (max_insns
< PARAM_VALUE (PARAM_LARGE_UNIT_INSNS
))
819 max_insns
= PARAM_VALUE (PARAM_LARGE_UNIT_INSNS
);
821 return ((HOST_WIDEST_INT
) max_insns
822 * (100 + PARAM_VALUE (PARAM_INLINE_UNIT_GROWTH
)) / 100);
825 /* Compute badness of all edges in NEW_EDGES and add them to the HEAP. */
827 add_new_edges_to_heap (fibheap_t heap
, VEC (cgraph_edge_p
, heap
) *new_edges
)
829 while (VEC_length (cgraph_edge_p
, new_edges
) > 0)
831 struct cgraph_edge
*edge
= VEC_pop (cgraph_edge_p
, new_edges
);
833 gcc_assert (!edge
->aux
);
834 edge
->aux
= fibheap_insert (heap
, cgraph_edge_badness (edge
), edge
);
839 /* We use greedy algorithm for inlining of small functions:
840 All inline candidates are put into prioritized heap based on estimated
841 growth of the overall number of instructions and then update the estimates.
843 INLINED and INLINED_CALEES are just pointers to arrays large enough
844 to be passed to cgraph_inlined_into and cgraph_inlined_callees. */
847 cgraph_decide_inlining_of_small_functions (void)
849 struct cgraph_node
*node
;
850 struct cgraph_edge
*edge
;
851 const char *failed_reason
;
852 fibheap_t heap
= fibheap_new ();
853 bitmap updated_nodes
= BITMAP_ALLOC (NULL
);
854 int min_insns
, max_insns
;
855 VEC (cgraph_edge_p
, heap
) *new_indirect_edges
= NULL
;
857 if (flag_indirect_inlining
)
858 new_indirect_edges
= VEC_alloc (cgraph_edge_p
, heap
, 8);
861 fprintf (dump_file
, "\nDeciding on smaller functions:\n");
863 /* Put all inline candidates into the heap. */
865 for (node
= cgraph_nodes
; node
; node
= node
->next
)
867 if (!node
->local
.inlinable
|| !node
->callers
868 || node
->local
.disregard_inline_limits
)
871 fprintf (dump_file
, "Considering inline candidate %s.\n", cgraph_node_name (node
));
873 node
->global
.estimated_growth
= INT_MIN
;
874 if (!cgraph_default_inline_p (node
, &failed_reason
))
876 cgraph_set_inline_failed (node
, failed_reason
);
880 for (edge
= node
->callers
; edge
; edge
= edge
->next_caller
)
881 if (edge
->inline_failed
)
883 gcc_assert (!edge
->aux
);
884 edge
->aux
= fibheap_insert (heap
, cgraph_edge_badness (edge
), edge
);
888 max_insns
= compute_max_insns (overall_insns
);
889 min_insns
= overall_insns
;
891 while (overall_insns
<= max_insns
892 && (edge
= (struct cgraph_edge
*) fibheap_extract_min (heap
)))
894 int old_insns
= overall_insns
;
895 struct cgraph_node
*where
;
897 cgraph_estimate_size_after_inlining (1, edge
->caller
, edge
->callee
);
898 const char *not_good
= NULL
;
900 growth
-= edge
->caller
->global
.insns
;
905 "\nConsidering %s with %i insns\n",
906 cgraph_node_name (edge
->callee
),
907 edge
->callee
->global
.insns
);
909 " to be inlined into %s\n"
910 " Estimated growth after inlined into all callees is %+i insns.\n"
911 " Estimated badness is %i, frequency %.2f.\n",
912 cgraph_node_name (edge
->caller
),
913 cgraph_estimate_growth (edge
->callee
),
914 cgraph_edge_badness (edge
),
915 edge
->frequency
/ (double)CGRAPH_FREQ_BASE
);
917 fprintf (dump_file
," Called "HOST_WIDEST_INT_PRINT_DEC
"x\n", edge
->count
);
919 gcc_assert (edge
->aux
);
921 if (!edge
->inline_failed
)
924 /* When not having profile info ready we don't weight by any way the
925 position of call in procedure itself. This means if call of
926 function A from function B seems profitable to inline, the recursive
927 call of function A in inline copy of A in B will look profitable too
928 and we end up inlining until reaching maximal function growth. This
929 is not good idea so prohibit the recursive inlining.
931 ??? When the frequencies are taken into account we might not need this
935 where
= edge
->caller
;
936 while (where
->global
.inlined_to
)
938 if (where
->decl
== edge
->callee
->decl
)
940 where
= where
->callers
->caller
;
942 if (where
->global
.inlined_to
)
945 = (edge
->callee
->local
.disregard_inline_limits
? N_("recursive inlining") : "");
947 fprintf (dump_file
, " inline_failed:Recursive inlining performed only for function itself.\n");
952 if (!cgraph_maybe_hot_edge_p (edge
))
953 not_good
= N_("call is unlikely and code size would grow");
954 if (!flag_inline_functions
955 && !DECL_DECLARED_INLINE_P (edge
->callee
->decl
))
956 not_good
= N_("function not declared inline and code size would grow");
958 not_good
= N_("optimizing for size and code size would grow");
959 if (not_good
&& growth
> 0 && cgraph_estimate_growth (edge
->callee
) > 0)
961 if (!cgraph_recursive_inlining_p (edge
->caller
, edge
->callee
,
962 &edge
->inline_failed
))
964 edge
->inline_failed
= not_good
;
966 fprintf (dump_file
, " inline_failed:%s.\n", edge
->inline_failed
);
970 if (!cgraph_default_inline_p (edge
->callee
, &edge
->inline_failed
))
972 if (!cgraph_recursive_inlining_p (edge
->caller
, edge
->callee
,
973 &edge
->inline_failed
))
976 fprintf (dump_file
, " inline_failed:%s.\n", edge
->inline_failed
);
980 if (!tree_can_inline_p (edge
->caller
->decl
, edge
->callee
->decl
))
982 CALL_STMT_CANNOT_INLINE_P (edge
->call_stmt
) = true;
983 edge
->inline_failed
= N_("target specific option mismatch");
985 fprintf (dump_file
, " inline_failed:%s.\n", edge
->inline_failed
);
988 if (cgraph_recursive_inlining_p (edge
->caller
, edge
->callee
,
989 &edge
->inline_failed
))
991 where
= edge
->caller
;
992 if (where
->global
.inlined_to
)
993 where
= where
->global
.inlined_to
;
994 if (!cgraph_decide_recursive_inlining (where
, new_indirect_edges
))
996 if (flag_indirect_inlining
)
997 add_new_edges_to_heap (heap
, new_indirect_edges
);
998 update_callee_keys (heap
, where
, updated_nodes
);
1002 struct cgraph_node
*callee
;
1003 if (CALL_STMT_CANNOT_INLINE_P (edge
->call_stmt
)
1004 || !cgraph_check_inline_limits (edge
->caller
, edge
->callee
,
1005 &edge
->inline_failed
, true))
1008 fprintf (dump_file
, " Not inlining into %s:%s.\n",
1009 cgraph_node_name (edge
->caller
), edge
->inline_failed
);
1012 callee
= edge
->callee
;
1013 cgraph_mark_inline_edge (edge
, true);
1014 if (flag_indirect_inlining
)
1016 ipa_propagate_indirect_call_infos (edge
, new_indirect_edges
);
1017 add_new_edges_to_heap (heap
, new_indirect_edges
);
1019 update_callee_keys (heap
, callee
, updated_nodes
);
1021 where
= edge
->caller
;
1022 if (where
->global
.inlined_to
)
1023 where
= where
->global
.inlined_to
;
1025 /* Our profitability metric can depend on local properties
1026 such as number of inlinable calls and size of the function body.
1027 After inlining these properties might change for the function we
1028 inlined into (since it's body size changed) and for the functions
1029 called by function we inlined (since number of it inlinable callers
1031 update_caller_keys (heap
, where
, updated_nodes
);
1032 bitmap_clear (updated_nodes
);
1037 " Inlined into %s which now has %i insns,"
1038 "net change of %+i insns.\n",
1039 cgraph_node_name (edge
->caller
),
1040 edge
->caller
->global
.insns
,
1041 overall_insns
- old_insns
);
1043 if (min_insns
> overall_insns
)
1045 min_insns
= overall_insns
;
1046 max_insns
= compute_max_insns (min_insns
);
1049 fprintf (dump_file
, "New minimal insns reached: %i\n", min_insns
);
1052 while ((edge
= (struct cgraph_edge
*) fibheap_extract_min (heap
)) != NULL
)
1054 gcc_assert (edge
->aux
);
1056 if (!edge
->callee
->local
.disregard_inline_limits
&& edge
->inline_failed
1057 && !cgraph_recursive_inlining_p (edge
->caller
, edge
->callee
,
1058 &edge
->inline_failed
))
1059 edge
->inline_failed
= N_("--param inline-unit-growth limit reached");
1062 if (new_indirect_edges
)
1063 VEC_free (cgraph_edge_p
, heap
, new_indirect_edges
);
1064 fibheap_delete (heap
);
1065 BITMAP_FREE (updated_nodes
);
1068 /* Decide on the inlining. We do so in the topological order to avoid
1069 expenses on updating data structures. */
1072 cgraph_decide_inlining (void)
1074 struct cgraph_node
*node
;
1076 struct cgraph_node
**order
=
1077 XCNEWVEC (struct cgraph_node
*, cgraph_n_nodes
);
1080 int initial_insns
= 0;
1083 for (node
= cgraph_nodes
; node
; node
= node
->next
)
1084 if (node
->analyzed
&& (node
->needed
|| node
->reachable
))
1086 struct cgraph_edge
*e
;
1088 initial_insns
+= inline_summary (node
)->self_insns
;
1089 gcc_assert (inline_summary (node
)->self_insns
== node
->global
.insns
);
1090 for (e
= node
->callees
; e
; e
= e
->next_callee
)
1091 if (max_count
< e
->count
)
1092 max_count
= e
->count
;
1094 overall_insns
= initial_insns
;
1095 gcc_assert (!max_count
|| (profile_info
&& flag_branch_probabilities
));
1097 nnodes
= cgraph_postorder (order
);
1101 "\nDeciding on inlining. Starting with %i insns.\n",
1104 for (node
= cgraph_nodes
; node
; node
= node
->next
)
1108 fprintf (dump_file
, "\nInlining always_inline functions:\n");
1110 /* In the first pass mark all always_inline edges. Do this with a priority
1111 so none of our later choices will make this impossible. */
1112 for (i
= nnodes
- 1; i
>= 0; i
--)
1114 struct cgraph_edge
*e
, *next
;
1118 /* Handle nodes to be flattened, but don't update overall unit size. */
1119 if (lookup_attribute ("flatten", DECL_ATTRIBUTES (node
->decl
)) != NULL
)
1123 "Flattening %s\n", cgraph_node_name (node
));
1124 cgraph_decide_inlining_incrementally (node
, INLINE_ALL
, 0);
1127 if (!node
->local
.disregard_inline_limits
)
1131 "\nConsidering %s %i insns (always inline)\n",
1132 cgraph_node_name (node
), node
->global
.insns
);
1133 old_insns
= overall_insns
;
1134 for (e
= node
->callers
; e
; e
= next
)
1136 next
= e
->next_caller
;
1137 if (!e
->inline_failed
|| CALL_STMT_CANNOT_INLINE_P (e
->call_stmt
))
1139 if (cgraph_recursive_inlining_p (e
->caller
, e
->callee
,
1142 if (!tree_can_inline_p (e
->caller
->decl
, e
->callee
->decl
))
1144 CALL_STMT_CANNOT_INLINE_P (e
->call_stmt
) = true;
1147 cgraph_mark_inline_edge (e
, true);
1148 if (flag_indirect_inlining
)
1149 ipa_propagate_indirect_call_infos (e
, NULL
);
1152 " Inlined into %s which now has %i insns.\n",
1153 cgraph_node_name (e
->caller
),
1154 e
->caller
->global
.insns
);
1156 /* Inlining self recursive function might introduce new calls to
1157 themselves we didn't see in the loop above. Fill in the proper
1158 reason why inline failed. */
1159 for (e
= node
->callers
; e
; e
= e
->next_caller
)
1160 if (e
->inline_failed
)
1161 e
->inline_failed
= N_("recursive inlining");
1164 " Inlined for a net change of %+i insns.\n",
1165 overall_insns
- old_insns
);
1168 if (!flag_really_no_inline
)
1169 cgraph_decide_inlining_of_small_functions ();
1171 /* After this point, any edge discovery performed by indirect inlining is no
1172 good so let's give up. */
1173 if (flag_indirect_inlining
)
1174 free_all_ipa_structures_after_iinln ();
1176 if (!flag_really_no_inline
1177 && flag_inline_functions_called_once
)
1180 fprintf (dump_file
, "\nDeciding on functions called once:\n");
1182 /* And finally decide what functions are called once. */
1184 for (i
= nnodes
- 1; i
>= 0; i
--)
1188 if (node
->callers
&& !node
->callers
->next_caller
&& !node
->needed
1189 && node
->local
.inlinable
&& node
->callers
->inline_failed
1190 && !CALL_STMT_CANNOT_INLINE_P (node
->callers
->call_stmt
)
1191 && !DECL_EXTERNAL (node
->decl
) && !DECL_COMDAT (node
->decl
))
1196 "\nConsidering %s %i insns.\n",
1197 cgraph_node_name (node
), node
->global
.insns
);
1199 " Called once from %s %i insns.\n",
1200 cgraph_node_name (node
->callers
->caller
),
1201 node
->callers
->caller
->global
.insns
);
1204 old_insns
= overall_insns
;
1206 if (cgraph_check_inline_limits (node
->callers
->caller
, node
,
1209 cgraph_mark_inline (node
->callers
);
1212 " Inlined into %s which now has %i insns"
1213 " for a net change of %+i insns.\n",
1214 cgraph_node_name (node
->callers
->caller
),
1215 node
->callers
->caller
->global
.insns
,
1216 overall_insns
- old_insns
);
1222 " Inline limit reached, not inlined.\n");
1230 "\nInlined %i calls, eliminated %i functions, "
1231 "%i insns turned to %i insns.\n\n",
1232 ncalls_inlined
, nfunctions_inlined
, initial_insns
,
1238 /* Try to inline edge E from incremental inliner. MODE specifies mode
1241 We are detecting cycles by storing mode of inliner into cgraph_node last
1242 time we visited it in the recursion. In general when mode is set, we have
1243 recursive inlining, but as an special case, we want to try harder inline
1244 ALWAYS_INLINE functions: consider callgraph a->b->c->b, with a being
1245 flatten, b being always inline. Flattening 'a' will collapse
1246 a->b->c before hitting cycle. To accommodate always inline, we however
1247 need to inline a->b->c->b.
1249 So after hitting cycle first time, we switch into ALWAYS_INLINE mode and
1250 stop inlining only after hitting ALWAYS_INLINE in ALWAY_INLINE mode. */
1252 try_inline (struct cgraph_edge
*e
, enum inlining_mode mode
, int depth
)
1254 struct cgraph_node
*callee
= e
->callee
;
1255 enum inlining_mode callee_mode
= (enum inlining_mode
) (size_t) callee
->aux
;
1256 bool always_inline
= e
->callee
->local
.disregard_inline_limits
;
1258 /* We've hit cycle? */
1261 /* It is first time we see it and we are not in ALWAY_INLINE only
1262 mode yet. and the function in question is always_inline. */
1263 if (always_inline
&& mode
!= INLINE_ALWAYS_INLINE
)
1267 indent_to (dump_file
, depth
);
1269 "Hit cycle in %s, switching to always inline only.\n",
1270 cgraph_node_name (callee
));
1272 mode
= INLINE_ALWAYS_INLINE
;
1274 /* Otherwise it is time to give up. */
1279 indent_to (dump_file
, depth
);
1281 "Not inlining %s into %s to avoid cycle.\n",
1282 cgraph_node_name (callee
),
1283 cgraph_node_name (e
->caller
));
1285 e
->inline_failed
= (e
->callee
->local
.disregard_inline_limits
1286 ? N_("recursive inlining") : "");
1291 callee
->aux
= (void *)(size_t) mode
;
1294 indent_to (dump_file
, depth
);
1295 fprintf (dump_file
, " Inlining %s into %s.\n",
1296 cgraph_node_name (e
->callee
),
1297 cgraph_node_name (e
->caller
));
1299 if (e
->inline_failed
)
1300 cgraph_mark_inline (e
);
1302 /* In order to fully inline always_inline functions at -O0, we need to
1303 recurse here, since the inlined functions might not be processed by
1304 incremental inlining at all yet.
1306 Also flattening needs to be done recursively. */
1308 if (!flag_unit_at_a_time
|| mode
== INLINE_ALL
|| always_inline
)
1309 cgraph_decide_inlining_incrementally (e
->callee
, mode
, depth
+ 1);
1310 callee
->aux
= (void *)(size_t) callee_mode
;
1314 /* Decide on the inlining. We do so in the topological order to avoid
1315 expenses on updating data structures.
1316 DEPTH is depth of recursion, used only for debug output. */
1319 cgraph_decide_inlining_incrementally (struct cgraph_node
*node
,
1320 enum inlining_mode mode
,
1323 struct cgraph_edge
*e
;
1324 bool inlined
= false;
1325 const char *failed_reason
;
1326 enum inlining_mode old_mode
;
1328 #ifdef ENABLE_CHECKING
1329 verify_cgraph_node (node
);
1332 old_mode
= (enum inlining_mode
) (size_t)node
->aux
;
1334 if (mode
!= INLINE_ALWAYS_INLINE
1335 && lookup_attribute ("flatten", DECL_ATTRIBUTES (node
->decl
)) != NULL
)
1339 indent_to (dump_file
, depth
);
1340 fprintf (dump_file
, "Flattening %s\n", cgraph_node_name (node
));
1345 node
->aux
= (void *)(size_t) mode
;
1347 /* First of all look for always inline functions. */
1348 for (e
= node
->callees
; e
; e
= e
->next_callee
)
1350 if (!e
->callee
->local
.disregard_inline_limits
1351 && (mode
!= INLINE_ALL
|| !e
->callee
->local
.inlinable
))
1353 if (CALL_STMT_CANNOT_INLINE_P (e
->call_stmt
))
1355 /* When the edge is already inlined, we just need to recurse into
1356 it in order to fully flatten the leaves. */
1357 if (!e
->inline_failed
&& mode
== INLINE_ALL
)
1359 inlined
|= try_inline (e
, mode
, depth
);
1364 indent_to (dump_file
, depth
);
1366 "Considering to always inline inline candidate %s.\n",
1367 cgraph_node_name (e
->callee
));
1369 if (cgraph_recursive_inlining_p (node
, e
->callee
, &e
->inline_failed
))
1373 indent_to (dump_file
, depth
);
1374 fprintf (dump_file
, "Not inlining: recursive call.\n");
1378 if (!tree_can_inline_p (node
->decl
, e
->callee
->decl
))
1380 CALL_STMT_CANNOT_INLINE_P (e
->call_stmt
) = true;
1383 indent_to (dump_file
, depth
);
1385 "Not inlining: Target specific option mismatch.\n");
1389 if (gimple_in_ssa_p (DECL_STRUCT_FUNCTION (node
->decl
))
1390 != gimple_in_ssa_p (DECL_STRUCT_FUNCTION (e
->callee
->decl
)))
1394 indent_to (dump_file
, depth
);
1395 fprintf (dump_file
, "Not inlining: SSA form does not match.\n");
1399 if (!DECL_SAVED_TREE (e
->callee
->decl
) && !e
->callee
->inline_decl
)
1403 indent_to (dump_file
, depth
);
1405 "Not inlining: Function body no longer available.\n");
1409 inlined
|= try_inline (e
, mode
, depth
);
1412 /* Now do the automatic inlining. */
1413 if (!flag_really_no_inline
&& mode
!= INLINE_ALL
1414 && mode
!= INLINE_ALWAYS_INLINE
)
1415 for (e
= node
->callees
; e
; e
= e
->next_callee
)
1417 if (!e
->callee
->local
.inlinable
1418 || !e
->inline_failed
1419 || e
->callee
->local
.disregard_inline_limits
)
1422 fprintf (dump_file
, "Considering inline candidate %s.\n",
1423 cgraph_node_name (e
->callee
));
1424 if (cgraph_recursive_inlining_p (node
, e
->callee
, &e
->inline_failed
))
1428 indent_to (dump_file
, depth
);
1429 fprintf (dump_file
, "Not inlining: recursive call.\n");
1433 if (gimple_in_ssa_p (DECL_STRUCT_FUNCTION (node
->decl
))
1434 != gimple_in_ssa_p (DECL_STRUCT_FUNCTION (e
->callee
->decl
)))
1438 indent_to (dump_file
, depth
);
1439 fprintf (dump_file
, "Not inlining: SSA form does not match.\n");
1443 /* When the function body would grow and inlining the function won't
1444 eliminate the need for offline copy of the function, don't inline.
1446 if ((mode
== INLINE_SIZE
1447 || (!flag_inline_functions
1448 && !DECL_DECLARED_INLINE_P (e
->callee
->decl
)))
1449 && (cgraph_estimate_size_after_inlining (1, e
->caller
, e
->callee
)
1450 > e
->caller
->global
.insns
)
1451 && cgraph_estimate_growth (e
->callee
) > 0)
1455 indent_to (dump_file
, depth
);
1457 "Not inlining: code size would grow by %i insns.\n",
1458 cgraph_estimate_size_after_inlining (1, e
->caller
,
1460 - e
->caller
->global
.insns
);
1464 if (!cgraph_check_inline_limits (node
, e
->callee
, &e
->inline_failed
,
1466 || CALL_STMT_CANNOT_INLINE_P (e
->call_stmt
))
1470 indent_to (dump_file
, depth
);
1471 fprintf (dump_file
, "Not inlining: %s.\n", e
->inline_failed
);
1475 if (!DECL_SAVED_TREE (e
->callee
->decl
) && !e
->callee
->inline_decl
)
1479 indent_to (dump_file
, depth
);
1481 "Not inlining: Function body no longer available.\n");
1485 if (!tree_can_inline_p (node
->decl
, e
->callee
->decl
))
1487 CALL_STMT_CANNOT_INLINE_P (e
->call_stmt
) = true;
1490 indent_to (dump_file
, depth
);
1492 "Not inlining: Target specific option mismatch.\n");
1496 if (cgraph_default_inline_p (e
->callee
, &failed_reason
))
1497 inlined
|= try_inline (e
, mode
, depth
);
1498 else if (!flag_unit_at_a_time
)
1499 e
->inline_failed
= failed_reason
;
1501 node
->aux
= (void *)(size_t) old_mode
;
1505 /* When inlining shall be performed. */
1507 cgraph_gate_inlining (void)
1509 return flag_inline_trees
;
1512 /* Because inlining might remove no-longer reachable nodes, we need to
1513 keep the array visible to garbage collector to avoid reading collected
1516 static GTY ((length ("nnodes"))) struct cgraph_node
**order
;
1518 /* Do inlining of small functions. Doing so early helps profiling and other
1519 passes to be somewhat more effective and avoids some code duplication in
1520 later real inlining pass for testcases with very many function calls. */
1522 cgraph_early_inlining (void)
1524 struct cgraph_node
*node
= cgraph_node (current_function_decl
);
1525 unsigned int todo
= 0;
1527 if (sorrycount
|| errorcount
)
1529 if (cgraph_decide_inlining_incrementally (node
,
1530 flag_unit_at_a_time
|| optimize_size
1531 ? INLINE_SIZE
: INLINE_SPEED
, 0))
1533 timevar_push (TV_INTEGRATION
);
1534 todo
= optimize_inline_calls (current_function_decl
);
1535 timevar_pop (TV_INTEGRATION
);
1540 /* When inlining shall be performed. */
1542 cgraph_gate_early_inlining (void)
1544 return flag_inline_trees
&& flag_early_inlining
;
1547 struct gimple_opt_pass pass_early_inline
=
1551 "einline", /* name */
1552 cgraph_gate_early_inlining
, /* gate */
1553 cgraph_early_inlining
, /* execute */
1556 0, /* static_pass_number */
1557 TV_INLINE_HEURISTICS
, /* tv_id */
1558 0, /* properties_required */
1559 PROP_cfg
, /* properties_provided */
1560 0, /* properties_destroyed */
1561 0, /* todo_flags_start */
1562 TODO_dump_func
/* todo_flags_finish */
1566 /* When inlining shall be performed. */
1568 cgraph_gate_ipa_early_inlining (void)
1570 return (flag_inline_trees
&& flag_early_inlining
1571 && (flag_branch_probabilities
|| flag_test_coverage
1572 || profile_arc_flag
));
1575 /* IPA pass wrapper for early inlining pass. We need to run early inlining
1576 before tree profiling so we have stand alone IPA pass for doing so. */
1577 struct simple_ipa_opt_pass pass_ipa_early_inline
=
1581 "einline_ipa", /* name */
1582 cgraph_gate_ipa_early_inlining
, /* gate */
1586 0, /* static_pass_number */
1587 TV_INLINE_HEURISTICS
, /* tv_id */
1588 0, /* properties_required */
1589 PROP_cfg
, /* properties_provided */
1590 0, /* properties_destroyed */
1591 0, /* todo_flags_start */
1592 TODO_dump_cgraph
/* todo_flags_finish */
1596 /* Compute parameters of functions used by inliner. */
1598 compute_inline_parameters (struct cgraph_node
*node
)
1600 gcc_assert (!node
->global
.inlined_to
);
1601 inline_summary (node
)->estimated_self_stack_size
1602 = estimated_stack_frame_size ();
1603 node
->global
.estimated_stack_size
1604 = inline_summary (node
)->estimated_self_stack_size
;
1605 node
->global
.stack_frame_offset
= 0;
1606 node
->local
.inlinable
= tree_inlinable_function_p (current_function_decl
);
1607 inline_summary (node
)->self_insns
= estimate_num_insns (current_function_decl
,
1608 &eni_inlining_weights
);
1609 if (node
->local
.inlinable
&& !node
->local
.disregard_inline_limits
)
1610 node
->local
.disregard_inline_limits
1611 = DECL_DISREGARD_INLINE_LIMITS (current_function_decl
);
1612 if (flag_really_no_inline
&& !node
->local
.disregard_inline_limits
)
1613 node
->local
.inlinable
= 0;
1614 /* Inlining characteristics are maintained by the cgraph_mark_inline. */
1615 node
->global
.insns
= inline_summary (node
)->self_insns
;
1620 /* Compute parameters of functions used by inliner using
1621 current_function_decl. */
1623 compute_inline_parameters_for_current (void)
1625 compute_inline_parameters (cgraph_node (current_function_decl
));
1629 /* When inlining shall be performed. */
1631 gate_inline_passes (void)
1633 return flag_inline_trees
;
1636 struct gimple_opt_pass pass_inline_parameters
=
1641 gate_inline_passes
, /* gate */
1642 compute_inline_parameters_for_current
,/* execute */
1645 0, /* static_pass_number */
1646 TV_INLINE_HEURISTICS
, /* tv_id */
1647 0, /* properties_required */
1648 PROP_cfg
, /* properties_provided */
1649 0, /* properties_destroyed */
1650 0, /* todo_flags_start */
1651 0 /* todo_flags_finish */
1655 /* This function performs intraprocedural analyzis in NODE that is required to
1656 inline indirect calls. */
1658 inline_indirect_intraprocedural_analysis (struct cgraph_node
*node
)
1660 struct cgraph_edge
*cs
;
1662 ipa_count_formal_params (node
);
1663 ipa_create_param_decls_array (node
);
1664 ipa_detect_param_modifications (node
);
1665 ipa_analyze_params_uses (node
);
1668 ipa_print_node_param_flags (dump_file
, node
);
1670 for (cs
= node
->callees
; cs
; cs
= cs
->next_callee
)
1672 ipa_count_arguments (cs
);
1673 ipa_compute_jump_functions (cs
);
1677 ipa_print_node_jump_functions (dump_file
, node
);
1680 /* Note function body size. */
1682 inline_generate_summary (void)
1684 struct cgraph_node
**order
=
1685 XCNEWVEC (struct cgraph_node
*, cgraph_n_nodes
);
1686 int nnodes
= cgraph_postorder (order
);
1689 if (flag_indirect_inlining
)
1691 ipa_register_cgraph_hooks ();
1692 ipa_check_create_node_params ();
1693 ipa_check_create_edge_args ();
1696 for (i
= nnodes
- 1; i
>= 0; i
--)
1698 struct cgraph_node
*node
= order
[i
];
1700 /* Allow possibly removed nodes to be garbage collected. */
1702 if (node
->analyzed
&& (node
->needed
|| node
->reachable
))
1704 push_cfun (DECL_STRUCT_FUNCTION (node
->decl
));
1705 current_function_decl
= node
->decl
;
1706 compute_inline_parameters (node
);
1708 if (flag_indirect_inlining
)
1709 inline_indirect_intraprocedural_analysis (node
);
1715 current_function_decl
= NULL
;
1720 /* Apply inline plan to function. */
1722 inline_transform (struct cgraph_node
*node
)
1724 unsigned int todo
= 0;
1725 struct cgraph_edge
*e
;
1727 /* We might need the body of this function so that we can expand
1728 it inline somewhere else. */
1729 if (cgraph_preserve_function_body_p (current_function_decl
))
1730 save_inline_function_body (node
);
1732 for (e
= node
->callees
; e
; e
= e
->next_callee
)
1733 if (!e
->inline_failed
|| warn_inline
)
1737 timevar_push (TV_INTEGRATION
);
1738 todo
= optimize_inline_calls (current_function_decl
);
1739 timevar_pop (TV_INTEGRATION
);
1741 return todo
| execute_fixup_cfg ();
1744 struct ipa_opt_pass pass_ipa_inline
=
1748 "inline", /* name */
1749 cgraph_gate_inlining
, /* gate */
1750 cgraph_decide_inlining
, /* execute */
1753 0, /* static_pass_number */
1754 TV_INLINE_HEURISTICS
, /* tv_id */
1755 0, /* properties_required */
1756 PROP_cfg
, /* properties_provided */
1757 0, /* properties_destroyed */
1758 TODO_remove_functions
, /* todo_flags_finish */
1759 TODO_dump_cgraph
| TODO_dump_func
1760 | TODO_remove_functions
/* todo_flags_finish */
1762 inline_generate_summary
, /* generate_summary */
1763 NULL
, /* write_summary */
1764 NULL
, /* read_summary */
1765 NULL
, /* function_read_summary */
1767 inline_transform
, /* function_transform */
1768 NULL
, /* variable_transform */
1772 /* When inlining shall be performed. */
1774 cgraph_gate_O0_always_inline (void)
1776 return !flag_unit_at_a_time
|| !flag_inline_trees
;
1780 cgraph_O0_always_inline (void)
1782 struct cgraph_node
*node
= cgraph_node (current_function_decl
);
1783 unsigned int todo
= 0;
1786 if (sorrycount
|| errorcount
)
1788 inlined
= cgraph_decide_inlining_incrementally (node
, INLINE_SPEED
, 0);
1789 /* We might need the body of this function so that we can expand
1790 it inline somewhere else. */
1791 if (cgraph_preserve_function_body_p (current_function_decl
))
1792 save_inline_function_body (node
);
1793 if (inlined
|| warn_inline
)
1795 timevar_push (TV_INTEGRATION
);
1796 todo
= optimize_inline_calls (current_function_decl
);
1797 timevar_pop (TV_INTEGRATION
);
1799 /* In non-unit-at-a-time we must mark all referenced functions as needed. */
1800 if (!flag_unit_at_a_time
)
1802 struct cgraph_edge
*e
;
1803 for (e
= node
->callees
; e
; e
= e
->next_callee
)
1804 if (e
->callee
->analyzed
)
1805 cgraph_mark_needed_node (e
->callee
);
1807 return todo
| execute_fixup_cfg ();
1810 struct gimple_opt_pass pass_O0_always_inline
=
1814 "always_inline", /* name */
1815 cgraph_gate_O0_always_inline
, /* gate */
1816 cgraph_O0_always_inline
, /* execute */
1819 0, /* static_pass_number */
1820 TV_INLINE_HEURISTICS
, /* tv_id */
1821 0, /* properties_required */
1822 PROP_cfg
, /* properties_provided */
1823 0, /* properties_destroyed */
1824 0, /* todo_flags_start */
1825 TODO_dump_func
| TODO_verify_flow
1826 | TODO_verify_stmts
/* todo_flags_finish */
1830 #include "gt-ipa-inline.h"