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"
142 /* Mode incremental inliner operate on:
144 In ALWAYS_INLINE only functions marked
145 always_inline are inlined. This mode is used after detecting cycle during
148 In SIZE mode, only functions that reduce function body size after inlining
149 are inlined, this is used during early inlining.
151 in ALL mode, everything is inlined. This is used during flattening. */
154 INLINE_ALWAYS_INLINE
,
155 INLINE_SIZE_NORECURSIVE
,
160 cgraph_decide_inlining_incrementally (struct cgraph_node
*, enum inlining_mode
,
164 /* Statistics we collect about inlining algorithm. */
165 static int ncalls_inlined
;
166 static int nfunctions_inlined
;
167 static int overall_insns
;
168 static gcov_type max_count
;
170 /* Holders of ipa cgraph hooks: */
171 static struct cgraph_node_hook_list
*function_insertion_hook_holder
;
173 static inline struct inline_summary
*
174 inline_summary (struct cgraph_node
*node
)
176 return &node
->local
.inline_summary
;
179 /* Estimate size of the function after inlining WHAT into TO. */
182 cgraph_estimate_size_after_inlining (int times
, struct cgraph_node
*to
,
183 struct cgraph_node
*what
)
186 tree fndecl
= what
->decl
, arg
;
187 int call_insns
= PARAM_VALUE (PARAM_INLINE_CALL_COST
);
189 for (arg
= DECL_ARGUMENTS (fndecl
); arg
; arg
= TREE_CHAIN (arg
))
190 call_insns
+= estimate_move_cost (TREE_TYPE (arg
));
191 size
= (what
->global
.insns
- call_insns
) * times
+ to
->global
.insns
;
192 gcc_assert (size
>= 0);
196 /* E is expected to be an edge being inlined. Clone destination node of
197 the edge and redirect it to the new clone.
198 DUPLICATE is used for bookkeeping on whether we are actually creating new
199 clones or re-using node originally representing out-of-line function call.
202 cgraph_clone_inlined_nodes (struct cgraph_edge
*e
, bool duplicate
,
203 bool update_original
)
209 /* We may eliminate the need for out-of-line copy to be output.
210 In that case just go ahead and re-use it. */
211 if (!e
->callee
->callers
->next_caller
212 && !e
->callee
->needed
213 && !cgraph_new_nodes
)
215 gcc_assert (!e
->callee
->global
.inlined_to
);
216 if (e
->callee
->analyzed
)
217 overall_insns
-= e
->callee
->global
.insns
, nfunctions_inlined
++;
222 struct cgraph_node
*n
;
223 n
= cgraph_clone_node (e
->callee
, e
->count
, e
->frequency
, e
->loop_nest
,
225 cgraph_redirect_edge_callee (e
, n
);
229 if (e
->caller
->global
.inlined_to
)
230 e
->callee
->global
.inlined_to
= e
->caller
->global
.inlined_to
;
232 e
->callee
->global
.inlined_to
= e
->caller
;
233 e
->callee
->global
.stack_frame_offset
234 = e
->caller
->global
.stack_frame_offset
235 + inline_summary (e
->caller
)->estimated_self_stack_size
;
236 peak
= e
->callee
->global
.stack_frame_offset
237 + inline_summary (e
->callee
)->estimated_self_stack_size
;
238 if (e
->callee
->global
.inlined_to
->global
.estimated_stack_size
< peak
)
239 e
->callee
->global
.inlined_to
->global
.estimated_stack_size
= peak
;
241 /* Recursively clone all bodies. */
242 for (e
= e
->callee
->callees
; e
; e
= e
->next_callee
)
243 if (!e
->inline_failed
)
244 cgraph_clone_inlined_nodes (e
, duplicate
, update_original
);
247 /* Mark edge E as inlined and update callgraph accordingly. UPDATE_ORIGINAL
248 specify whether profile of original function should be updated. If any new
249 indirect edges are discovered in the process, add them to NEW_EDGES, unless
250 it is NULL. Return true iff any new callgraph edges were discovered as a
251 result of inlining. */
254 cgraph_mark_inline_edge (struct cgraph_edge
*e
, bool update_original
,
255 VEC (cgraph_edge_p
, heap
) **new_edges
)
257 int old_insns
= 0, new_insns
= 0;
258 struct cgraph_node
*to
= NULL
, *what
;
259 struct cgraph_edge
*curr
= e
;
261 if (e
->callee
->inline_decl
)
262 cgraph_redirect_edge_callee (e
, cgraph_node (e
->callee
->inline_decl
));
264 gcc_assert (e
->inline_failed
);
265 e
->inline_failed
= CIF_OK
;
267 if (!e
->callee
->global
.inlined
)
268 DECL_POSSIBLY_INLINED (e
->callee
->decl
) = true;
269 e
->callee
->global
.inlined
= true;
271 cgraph_clone_inlined_nodes (e
, true, update_original
);
275 /* Now update size of caller and all functions caller is inlined into. */
276 for (;e
&& !e
->inline_failed
; e
= e
->caller
->callers
)
278 old_insns
= e
->caller
->global
.insns
;
279 new_insns
= cgraph_estimate_size_after_inlining (1, e
->caller
,
281 gcc_assert (new_insns
>= 0);
283 to
->global
.insns
= new_insns
;
285 gcc_assert (what
->global
.inlined_to
== to
);
286 if (new_insns
> old_insns
)
287 overall_insns
+= new_insns
- old_insns
;
290 if (flag_indirect_inlining
)
291 return ipa_propagate_indirect_call_infos (curr
, new_edges
);
296 /* Mark all calls of EDGE->CALLEE inlined into EDGE->CALLER.
297 Return following unredirected edge in the list of callers
300 static struct cgraph_edge
*
301 cgraph_mark_inline (struct cgraph_edge
*edge
)
303 struct cgraph_node
*to
= edge
->caller
;
304 struct cgraph_node
*what
= edge
->callee
;
305 struct cgraph_edge
*e
, *next
;
307 gcc_assert (!gimple_call_cannot_inline_p (edge
->call_stmt
));
308 /* Look for all calls, mark them inline and clone recursively
309 all inlined functions. */
310 for (e
= what
->callers
; e
; e
= next
)
312 next
= e
->next_caller
;
313 if (e
->caller
== to
&& e
->inline_failed
)
315 cgraph_mark_inline_edge (e
, true, NULL
);
324 /* Estimate the growth caused by inlining NODE into all callees. */
327 cgraph_estimate_growth (struct cgraph_node
*node
)
330 struct cgraph_edge
*e
;
331 bool self_recursive
= false;
333 if (node
->global
.estimated_growth
!= INT_MIN
)
334 return node
->global
.estimated_growth
;
336 for (e
= node
->callers
; e
; e
= e
->next_caller
)
338 if (e
->caller
== node
)
339 self_recursive
= true;
340 if (e
->inline_failed
)
341 growth
+= (cgraph_estimate_size_after_inlining (1, e
->caller
, node
)
342 - e
->caller
->global
.insns
);
345 /* ??? Wrong for non-trivially self recursive functions or cases where
346 we decide to not inline for different reasons, but it is not big deal
347 as in that case we will keep the body around, but we will also avoid
349 if (!node
->needed
&& !DECL_EXTERNAL (node
->decl
) && !self_recursive
)
350 growth
-= node
->global
.insns
;
352 node
->global
.estimated_growth
= growth
;
356 /* Return false when inlining WHAT into TO is not good idea
357 as it would cause too large growth of function bodies.
358 When ONE_ONLY is true, assume that only one call site is going
359 to be inlined, otherwise figure out how many call sites in
360 TO calls WHAT and verify that all can be inlined.
364 cgraph_check_inline_limits (struct cgraph_node
*to
, struct cgraph_node
*what
,
365 cgraph_inline_failed_t
*reason
, bool one_only
)
368 struct cgraph_edge
*e
;
371 HOST_WIDE_INT stack_size_limit
, inlined_stack
;
376 for (e
= to
->callees
; e
; e
= e
->next_callee
)
377 if (e
->callee
== what
)
380 if (to
->global
.inlined_to
)
381 to
= to
->global
.inlined_to
;
383 /* When inlining large function body called once into small function,
384 take the inlined function as base for limiting the growth. */
385 if (inline_summary (to
)->self_insns
> inline_summary(what
)->self_insns
)
386 limit
= inline_summary (to
)->self_insns
;
388 limit
= inline_summary (what
)->self_insns
;
390 limit
+= limit
* PARAM_VALUE (PARAM_LARGE_FUNCTION_GROWTH
) / 100;
392 /* Check the size after inlining against the function limits. But allow
393 the function to shrink if it went over the limits by forced inlining. */
394 newsize
= cgraph_estimate_size_after_inlining (times
, to
, what
);
395 if (newsize
>= to
->global
.insns
396 && newsize
> PARAM_VALUE (PARAM_LARGE_FUNCTION_INSNS
)
400 *reason
= CIF_LARGE_FUNCTION_GROWTH_LIMIT
;
404 stack_size_limit
= inline_summary (to
)->estimated_self_stack_size
;
406 stack_size_limit
+= stack_size_limit
* PARAM_VALUE (PARAM_STACK_FRAME_GROWTH
) / 100;
408 inlined_stack
= (to
->global
.stack_frame_offset
409 + inline_summary (to
)->estimated_self_stack_size
410 + what
->global
.estimated_stack_size
);
411 if (inlined_stack
> stack_size_limit
412 && inlined_stack
> PARAM_VALUE (PARAM_LARGE_STACK_FRAME
))
415 *reason
= CIF_LARGE_STACK_FRAME_GROWTH_LIMIT
;
421 /* Return true when function N is small enough to be inlined. */
424 cgraph_default_inline_p (struct cgraph_node
*n
, cgraph_inline_failed_t
*reason
)
429 decl
= n
->inline_decl
;
430 if (!flag_inline_small_functions
&& !DECL_DECLARED_INLINE_P (decl
))
433 *reason
= CIF_FUNCTION_NOT_INLINE_CANDIDATE
;
440 *reason
= CIF_BODY_NOT_AVAILABLE
;
444 if (DECL_DECLARED_INLINE_P (decl
))
446 if (n
->global
.insns
>= MAX_INLINE_INSNS_SINGLE
)
449 *reason
= CIF_MAX_INLINE_INSNS_SINGLE_LIMIT
;
455 if (n
->global
.insns
>= MAX_INLINE_INSNS_AUTO
)
458 *reason
= CIF_MAX_INLINE_INSNS_AUTO_LIMIT
;
466 /* Return true when inlining WHAT would create recursive inlining.
467 We call recursive inlining all cases where same function appears more than
468 once in the single recursion nest path in the inline graph. */
471 cgraph_recursive_inlining_p (struct cgraph_node
*to
,
472 struct cgraph_node
*what
,
473 cgraph_inline_failed_t
*reason
)
476 if (to
->global
.inlined_to
)
477 recursive
= what
->decl
== to
->global
.inlined_to
->decl
;
479 recursive
= what
->decl
== to
->decl
;
480 /* Marking recursive function inline has sane semantic and thus we should
482 if (recursive
&& reason
)
483 *reason
= (what
->local
.disregard_inline_limits
484 ? CIF_RECURSIVE_INLINING
: CIF_UNSPECIFIED
);
488 /* A cost model driving the inlining heuristics in a way so the edges with
489 smallest badness are inlined first. After each inlining is performed
490 the costs of all caller edges of nodes affected are recomputed so the
491 metrics may accurately depend on values such as number of inlinable callers
492 of the function or function body size. */
495 cgraph_edge_badness (struct cgraph_edge
*edge
)
499 cgraph_estimate_size_after_inlining (1, edge
->caller
, edge
->callee
);
501 growth
-= edge
->caller
->global
.insns
;
503 /* Always prefer inlining saving code size. */
505 badness
= INT_MIN
- growth
;
507 /* When profiling is available, base priorities -(#calls / growth).
508 So we optimize for overall number of "executed" inlined calls. */
510 badness
= ((int)((double)edge
->count
* INT_MIN
/ max_count
)) / growth
;
512 /* When function local profile is available, base priorities on
513 growth / frequency, so we optimize for overall frequency of inlined
514 calls. This is not too accurate since while the call might be frequent
515 within function, the function itself is infrequent.
517 Other objective to optimize for is number of different calls inlined.
518 We add the estimated growth after inlining all functions to bias the
519 priorities slightly in this direction (so fewer times called functions
520 of the same size gets priority). */
521 else if (flag_guess_branch_prob
)
523 int div
= edge
->frequency
* 100 / CGRAPH_FREQ_BASE
;
525 cgraph_estimate_size_after_inlining (1, edge
->caller
, edge
->callee
);
526 growth
-= edge
->caller
->global
.insns
;
527 badness
= growth
* 256;
529 /* Decrease badness if call is nested. */
530 /* Compress the range so we don't overflow. */
532 div
= 256 + ceil_log2 (div
) - 8;
537 badness
+= cgraph_estimate_growth (edge
->callee
);
539 /* When function local profile is not available or it does not give
540 useful information (ie frequency is zero), base the cost on
541 loop nest and overall size growth, so we optimize for overall number
542 of functions fully inlined in program. */
545 int nest
= MIN (edge
->loop_nest
, 8);
546 badness
= cgraph_estimate_growth (edge
->callee
) * 256;
548 /* Decrease badness if call is nested. */
556 /* Make recursive inlining happen always after other inlining is done. */
557 if (cgraph_recursive_inlining_p (edge
->caller
, edge
->callee
, NULL
))
563 /* Recompute heap nodes for each of caller edge. */
566 update_caller_keys (fibheap_t heap
, struct cgraph_node
*node
,
567 bitmap updated_nodes
)
569 struct cgraph_edge
*edge
;
570 cgraph_inline_failed_t failed_reason
;
572 if (!node
->local
.inlinable
|| node
->local
.disregard_inline_limits
573 || node
->global
.inlined_to
)
575 if (bitmap_bit_p (updated_nodes
, node
->uid
))
577 bitmap_set_bit (updated_nodes
, node
->uid
);
578 node
->global
.estimated_growth
= INT_MIN
;
580 if (!node
->local
.inlinable
)
582 /* Prune out edges we won't inline into anymore. */
583 if (!cgraph_default_inline_p (node
, &failed_reason
))
585 for (edge
= node
->callers
; edge
; edge
= edge
->next_caller
)
588 fibheap_delete_node (heap
, (fibnode_t
) edge
->aux
);
590 if (edge
->inline_failed
)
591 edge
->inline_failed
= failed_reason
;
596 for (edge
= node
->callers
; edge
; edge
= edge
->next_caller
)
597 if (edge
->inline_failed
)
599 int badness
= cgraph_edge_badness (edge
);
602 fibnode_t n
= (fibnode_t
) edge
->aux
;
603 gcc_assert (n
->data
== edge
);
604 if (n
->key
== badness
)
607 /* fibheap_replace_key only increase the keys. */
608 if (fibheap_replace_key (heap
, n
, badness
))
610 fibheap_delete_node (heap
, (fibnode_t
) edge
->aux
);
612 edge
->aux
= fibheap_insert (heap
, badness
, edge
);
616 /* Recompute heap nodes for each of caller edges of each of callees. */
619 update_callee_keys (fibheap_t heap
, struct cgraph_node
*node
,
620 bitmap updated_nodes
)
622 struct cgraph_edge
*e
;
623 node
->global
.estimated_growth
= INT_MIN
;
625 for (e
= node
->callees
; e
; e
= e
->next_callee
)
626 if (e
->inline_failed
)
627 update_caller_keys (heap
, e
->callee
, updated_nodes
);
628 else if (!e
->inline_failed
)
629 update_callee_keys (heap
, e
->callee
, updated_nodes
);
632 /* Enqueue all recursive calls from NODE into priority queue depending on
633 how likely we want to recursively inline the call. */
636 lookup_recursive_calls (struct cgraph_node
*node
, struct cgraph_node
*where
,
640 struct cgraph_edge
*e
;
641 for (e
= where
->callees
; e
; e
= e
->next_callee
)
642 if (e
->callee
== node
)
644 /* When profile feedback is available, prioritize by expected number
645 of calls. Without profile feedback we maintain simple queue
646 to order candidates via recursive depths. */
647 fibheap_insert (heap
,
648 !max_count
? priority
++
649 : -(e
->count
/ ((max_count
+ (1<<24) - 1) / (1<<24))),
652 for (e
= where
->callees
; e
; e
= e
->next_callee
)
653 if (!e
->inline_failed
)
654 lookup_recursive_calls (node
, e
->callee
, heap
);
657 /* Decide on recursive inlining: in the case function has recursive calls,
658 inline until body size reaches given argument. If any new indirect edges
659 are discovered in the process, add them to *NEW_EDGES, unless NEW_EDGES
663 cgraph_decide_recursive_inlining (struct cgraph_node
*node
,
664 VEC (cgraph_edge_p
, heap
) **new_edges
)
666 int limit
= PARAM_VALUE (PARAM_MAX_INLINE_INSNS_RECURSIVE_AUTO
);
667 int max_depth
= PARAM_VALUE (PARAM_MAX_INLINE_RECURSIVE_DEPTH_AUTO
);
668 int probability
= PARAM_VALUE (PARAM_MIN_INLINE_RECURSIVE_PROBABILITY
);
670 struct cgraph_edge
*e
;
671 struct cgraph_node
*master_clone
, *next
;
675 if (optimize_function_for_size_p (DECL_STRUCT_FUNCTION (node
->decl
))
676 || (!flag_inline_functions
&& !DECL_DECLARED_INLINE_P (node
->decl
)))
679 if (DECL_DECLARED_INLINE_P (node
->decl
))
681 limit
= PARAM_VALUE (PARAM_MAX_INLINE_INSNS_RECURSIVE
);
682 max_depth
= PARAM_VALUE (PARAM_MAX_INLINE_RECURSIVE_DEPTH
);
685 /* Make sure that function is small enough to be considered for inlining. */
687 || cgraph_estimate_size_after_inlining (1, node
, node
) >= limit
)
689 heap
= fibheap_new ();
690 lookup_recursive_calls (node
, node
, heap
);
691 if (fibheap_empty (heap
))
693 fibheap_delete (heap
);
699 " Performing recursive inlining on %s\n",
700 cgraph_node_name (node
));
702 /* We need original clone to copy around. */
703 master_clone
= cgraph_clone_node (node
, node
->count
, CGRAPH_FREQ_BASE
, 1, false);
704 master_clone
->needed
= true;
705 for (e
= master_clone
->callees
; e
; e
= e
->next_callee
)
706 if (!e
->inline_failed
)
707 cgraph_clone_inlined_nodes (e
, true, false);
709 /* Do the inlining and update list of recursive call during process. */
710 while (!fibheap_empty (heap
)
711 && (cgraph_estimate_size_after_inlining (1, node
, master_clone
)
714 struct cgraph_edge
*curr
715 = (struct cgraph_edge
*) fibheap_extract_min (heap
);
716 struct cgraph_node
*cnode
;
719 for (cnode
= curr
->caller
;
720 cnode
->global
.inlined_to
; cnode
= cnode
->callers
->caller
)
721 if (node
->decl
== curr
->callee
->decl
)
723 if (depth
> max_depth
)
727 " maximal depth reached\n");
733 if (!cgraph_maybe_hot_edge_p (curr
))
736 fprintf (dump_file
, " Not inlining cold call\n");
739 if (curr
->count
* 100 / node
->count
< probability
)
743 " Probability of edge is too small\n");
751 " Inlining call of depth %i", depth
);
754 fprintf (dump_file
, " called approx. %.2f times per call",
755 (double)curr
->count
/ node
->count
);
757 fprintf (dump_file
, "\n");
759 cgraph_redirect_edge_callee (curr
, master_clone
);
760 cgraph_mark_inline_edge (curr
, false, new_edges
);
761 lookup_recursive_calls (node
, curr
->callee
, heap
);
764 if (!fibheap_empty (heap
) && dump_file
)
765 fprintf (dump_file
, " Recursive inlining growth limit met.\n");
767 fibheap_delete (heap
);
770 "\n Inlined %i times, body grown from %i to %i insns\n", n
,
771 master_clone
->global
.insns
, node
->global
.insns
);
773 /* Remove master clone we used for inlining. We rely that clones inlined
774 into master clone gets queued just before master clone so we don't
776 for (node
= cgraph_nodes
; node
!= master_clone
;
780 if (node
->global
.inlined_to
== master_clone
)
781 cgraph_remove_node (node
);
783 cgraph_remove_node (master_clone
);
784 /* FIXME: Recursive inlining actually reduces number of calls of the
785 function. At this place we should probably walk the function and
786 inline clones and compensate the counts accordingly. This probably
787 doesn't matter much in practice. */
791 /* Set inline_failed for all callers of given function to REASON. */
794 cgraph_set_inline_failed (struct cgraph_node
*node
,
795 cgraph_inline_failed_t reason
)
797 struct cgraph_edge
*e
;
800 fprintf (dump_file
, "Inlining failed: %s\n",
801 cgraph_inline_failed_string (reason
));
802 for (e
= node
->callers
; e
; e
= e
->next_caller
)
803 if (e
->inline_failed
)
804 e
->inline_failed
= reason
;
807 /* Given whole compilation unit estimate of INSNS, compute how large we can
808 allow the unit to grow. */
810 compute_max_insns (int insns
)
812 int max_insns
= insns
;
813 if (max_insns
< PARAM_VALUE (PARAM_LARGE_UNIT_INSNS
))
814 max_insns
= PARAM_VALUE (PARAM_LARGE_UNIT_INSNS
);
816 return ((HOST_WIDEST_INT
) max_insns
817 * (100 + PARAM_VALUE (PARAM_INLINE_UNIT_GROWTH
)) / 100);
820 /* Compute badness of all edges in NEW_EDGES and add them to the HEAP. */
822 add_new_edges_to_heap (fibheap_t heap
, VEC (cgraph_edge_p
, heap
) *new_edges
)
824 while (VEC_length (cgraph_edge_p
, new_edges
) > 0)
826 struct cgraph_edge
*edge
= VEC_pop (cgraph_edge_p
, new_edges
);
828 gcc_assert (!edge
->aux
);
829 edge
->aux
= fibheap_insert (heap
, cgraph_edge_badness (edge
), edge
);
834 /* We use greedy algorithm for inlining of small functions:
835 All inline candidates are put into prioritized heap based on estimated
836 growth of the overall number of instructions and then update the estimates.
838 INLINED and INLINED_CALEES are just pointers to arrays large enough
839 to be passed to cgraph_inlined_into and cgraph_inlined_callees. */
842 cgraph_decide_inlining_of_small_functions (void)
844 struct cgraph_node
*node
;
845 struct cgraph_edge
*edge
;
846 cgraph_inline_failed_t failed_reason
;
847 fibheap_t heap
= fibheap_new ();
848 bitmap updated_nodes
= BITMAP_ALLOC (NULL
);
849 int min_insns
, max_insns
;
850 VEC (cgraph_edge_p
, heap
) *new_indirect_edges
= NULL
;
852 if (flag_indirect_inlining
)
853 new_indirect_edges
= VEC_alloc (cgraph_edge_p
, heap
, 8);
856 fprintf (dump_file
, "\nDeciding on smaller functions:\n");
858 /* Put all inline candidates into the heap. */
860 for (node
= cgraph_nodes
; node
; node
= node
->next
)
862 if (!node
->local
.inlinable
|| !node
->callers
863 || node
->local
.disregard_inline_limits
)
866 fprintf (dump_file
, "Considering inline candidate %s.\n", cgraph_node_name (node
));
868 node
->global
.estimated_growth
= INT_MIN
;
869 if (!cgraph_default_inline_p (node
, &failed_reason
))
871 cgraph_set_inline_failed (node
, failed_reason
);
875 for (edge
= node
->callers
; edge
; edge
= edge
->next_caller
)
876 if (edge
->inline_failed
)
878 gcc_assert (!edge
->aux
);
879 edge
->aux
= fibheap_insert (heap
, cgraph_edge_badness (edge
), edge
);
883 max_insns
= compute_max_insns (overall_insns
);
884 min_insns
= overall_insns
;
886 while (overall_insns
<= max_insns
887 && (edge
= (struct cgraph_edge
*) fibheap_extract_min (heap
)))
889 int old_insns
= overall_insns
;
890 struct cgraph_node
*where
;
892 cgraph_estimate_size_after_inlining (1, edge
->caller
, edge
->callee
);
893 cgraph_inline_failed_t not_good
= CIF_OK
;
895 growth
-= edge
->caller
->global
.insns
;
900 "\nConsidering %s with %i insns\n",
901 cgraph_node_name (edge
->callee
),
902 edge
->callee
->global
.insns
);
904 " to be inlined into %s in %s:%i\n"
905 " Estimated growth after inlined into all callees is %+i insns.\n"
906 " Estimated badness is %i, frequency %.2f.\n",
907 cgraph_node_name (edge
->caller
),
908 gimple_filename ((const_gimple
) edge
->call_stmt
),
909 gimple_lineno ((const_gimple
) edge
->call_stmt
),
910 cgraph_estimate_growth (edge
->callee
),
911 cgraph_edge_badness (edge
),
912 edge
->frequency
/ (double)CGRAPH_FREQ_BASE
);
914 fprintf (dump_file
," Called "HOST_WIDEST_INT_PRINT_DEC
"x\n", edge
->count
);
916 gcc_assert (edge
->aux
);
918 if (!edge
->inline_failed
)
921 /* When not having profile info ready we don't weight by any way the
922 position of call in procedure itself. This means if call of
923 function A from function B seems profitable to inline, the recursive
924 call of function A in inline copy of A in B will look profitable too
925 and we end up inlining until reaching maximal function growth. This
926 is not good idea so prohibit the recursive inlining.
928 ??? When the frequencies are taken into account we might not need this
931 We need to be cureful here, in some testcases, e.g. directivec.c in
932 libcpp, we can estimate self recursive function to have negative growth
933 for inlining completely.
937 where
= edge
->caller
;
938 while (where
->global
.inlined_to
)
940 if (where
->decl
== edge
->callee
->decl
)
942 where
= where
->callers
->caller
;
944 if (where
->global
.inlined_to
)
947 = (edge
->callee
->local
.disregard_inline_limits
948 ? CIF_RECURSIVE_INLINING
: CIF_UNSPECIFIED
);
950 fprintf (dump_file
, " inline_failed:Recursive inlining performed only for function itself.\n");
955 if (!cgraph_maybe_hot_edge_p (edge
))
956 not_good
= CIF_UNLIKELY_CALL
;
957 if (!flag_inline_functions
958 && !DECL_DECLARED_INLINE_P (edge
->callee
->decl
))
959 not_good
= CIF_NOT_DECLARED_INLINED
;
960 if (optimize_function_for_size_p (DECL_STRUCT_FUNCTION(edge
->caller
->decl
)))
961 not_good
= CIF_OPTIMIZING_FOR_SIZE
;
962 if (not_good
&& growth
> 0 && cgraph_estimate_growth (edge
->callee
) > 0)
964 if (!cgraph_recursive_inlining_p (edge
->caller
, edge
->callee
,
965 &edge
->inline_failed
))
967 edge
->inline_failed
= not_good
;
969 fprintf (dump_file
, " inline_failed:%s.\n",
970 cgraph_inline_failed_string (edge
->inline_failed
));
974 if (!cgraph_default_inline_p (edge
->callee
, &edge
->inline_failed
))
976 if (!cgraph_recursive_inlining_p (edge
->caller
, edge
->callee
,
977 &edge
->inline_failed
))
980 fprintf (dump_file
, " inline_failed:%s.\n",
981 cgraph_inline_failed_string (edge
->inline_failed
));
985 if (!tree_can_inline_p (edge
->caller
->decl
, edge
->callee
->decl
))
987 gimple_call_set_cannot_inline (edge
->call_stmt
, true);
988 edge
->inline_failed
= CIF_TARGET_OPTION_MISMATCH
;
990 fprintf (dump_file
, " inline_failed:%s.\n",
991 cgraph_inline_failed_string (edge
->inline_failed
));
994 if (cgraph_recursive_inlining_p (edge
->caller
, edge
->callee
,
995 &edge
->inline_failed
))
997 where
= edge
->caller
;
998 if (where
->global
.inlined_to
)
999 where
= where
->global
.inlined_to
;
1000 if (!cgraph_decide_recursive_inlining (where
,
1001 flag_indirect_inlining
1002 ? &new_indirect_edges
: NULL
))
1004 if (flag_indirect_inlining
)
1005 add_new_edges_to_heap (heap
, new_indirect_edges
);
1006 update_callee_keys (heap
, where
, updated_nodes
);
1010 struct cgraph_node
*callee
;
1011 if (gimple_call_cannot_inline_p (edge
->call_stmt
)
1012 || !cgraph_check_inline_limits (edge
->caller
, edge
->callee
,
1013 &edge
->inline_failed
, true))
1016 fprintf (dump_file
, " Not inlining into %s:%s.\n",
1017 cgraph_node_name (edge
->caller
),
1018 cgraph_inline_failed_string (edge
->inline_failed
));
1021 callee
= edge
->callee
;
1022 cgraph_mark_inline_edge (edge
, true, &new_indirect_edges
);
1023 if (flag_indirect_inlining
)
1024 add_new_edges_to_heap (heap
, new_indirect_edges
);
1026 update_callee_keys (heap
, callee
, updated_nodes
);
1028 where
= edge
->caller
;
1029 if (where
->global
.inlined_to
)
1030 where
= where
->global
.inlined_to
;
1032 /* Our profitability metric can depend on local properties
1033 such as number of inlinable calls and size of the function body.
1034 After inlining these properties might change for the function we
1035 inlined into (since it's body size changed) and for the functions
1036 called by function we inlined (since number of it inlinable callers
1038 update_caller_keys (heap
, where
, updated_nodes
);
1039 bitmap_clear (updated_nodes
);
1044 " Inlined into %s which now has %i insns,"
1045 "net change of %+i insns.\n",
1046 cgraph_node_name (edge
->caller
),
1047 edge
->caller
->global
.insns
,
1048 overall_insns
- old_insns
);
1050 if (min_insns
> overall_insns
)
1052 min_insns
= overall_insns
;
1053 max_insns
= compute_max_insns (min_insns
);
1056 fprintf (dump_file
, "New minimal insns reached: %i\n", min_insns
);
1059 while ((edge
= (struct cgraph_edge
*) fibheap_extract_min (heap
)) != NULL
)
1061 gcc_assert (edge
->aux
);
1063 if (!edge
->callee
->local
.disregard_inline_limits
&& edge
->inline_failed
1064 && !cgraph_recursive_inlining_p (edge
->caller
, edge
->callee
,
1065 &edge
->inline_failed
))
1066 edge
->inline_failed
= CIF_INLINE_UNIT_GROWTH_LIMIT
;
1069 if (new_indirect_edges
)
1070 VEC_free (cgraph_edge_p
, heap
, new_indirect_edges
);
1071 fibheap_delete (heap
);
1072 BITMAP_FREE (updated_nodes
);
1075 /* Decide on the inlining. We do so in the topological order to avoid
1076 expenses on updating data structures. */
1079 cgraph_decide_inlining (void)
1081 struct cgraph_node
*node
;
1083 struct cgraph_node
**order
=
1084 XCNEWVEC (struct cgraph_node
*, cgraph_n_nodes
);
1087 int initial_insns
= 0;
1088 bool redo_always_inline
= true;
1090 cgraph_remove_function_insertion_hook (function_insertion_hook_holder
);
1093 for (node
= cgraph_nodes
; node
; node
= node
->next
)
1094 if (node
->analyzed
&& (node
->needed
|| node
->reachable
))
1096 struct cgraph_edge
*e
;
1098 initial_insns
+= inline_summary (node
)->self_insns
;
1099 gcc_assert (inline_summary (node
)->self_insns
== node
->global
.insns
);
1100 for (e
= node
->callees
; e
; e
= e
->next_callee
)
1101 if (max_count
< e
->count
)
1102 max_count
= e
->count
;
1104 overall_insns
= initial_insns
;
1105 gcc_assert (!max_count
|| (profile_info
&& flag_branch_probabilities
));
1107 nnodes
= cgraph_postorder (order
);
1111 "\nDeciding on inlining. Starting with %i insns.\n",
1114 for (node
= cgraph_nodes
; node
; node
= node
->next
)
1118 fprintf (dump_file
, "\nInlining always_inline functions:\n");
1120 /* In the first pass mark all always_inline edges. Do this with a priority
1121 so none of our later choices will make this impossible. */
1122 while (redo_always_inline
)
1124 redo_always_inline
= false;
1125 for (i
= nnodes
- 1; i
>= 0; i
--)
1127 struct cgraph_edge
*e
, *next
;
1131 /* Handle nodes to be flattened, but don't update overall unit
1133 if (lookup_attribute ("flatten",
1134 DECL_ATTRIBUTES (node
->decl
)) != NULL
)
1138 "Flattening %s\n", cgraph_node_name (node
));
1139 cgraph_decide_inlining_incrementally (node
, INLINE_ALL
, 0);
1142 if (!node
->local
.disregard_inline_limits
)
1146 "\nConsidering %s %i insns (always inline)\n",
1147 cgraph_node_name (node
), node
->global
.insns
);
1148 old_insns
= overall_insns
;
1149 for (e
= node
->callers
; e
; e
= next
)
1151 next
= e
->next_caller
;
1152 if (!e
->inline_failed
1153 || gimple_call_cannot_inline_p (e
->call_stmt
))
1155 if (cgraph_recursive_inlining_p (e
->caller
, e
->callee
,
1158 if (!tree_can_inline_p (e
->caller
->decl
, e
->callee
->decl
))
1160 gimple_call_set_cannot_inline (e
->call_stmt
, true);
1163 if (cgraph_mark_inline_edge (e
, true, NULL
))
1164 redo_always_inline
= true;
1167 " Inlined into %s which now has %i insns.\n",
1168 cgraph_node_name (e
->caller
),
1169 e
->caller
->global
.insns
);
1171 /* Inlining self recursive function might introduce new calls to
1172 themselves we didn't see in the loop above. Fill in the proper
1173 reason why inline failed. */
1174 for (e
= node
->callers
; e
; e
= e
->next_caller
)
1175 if (e
->inline_failed
)
1176 e
->inline_failed
= CIF_RECURSIVE_INLINING
;
1179 " Inlined for a net change of %+i insns.\n",
1180 overall_insns
- old_insns
);
1184 cgraph_decide_inlining_of_small_functions ();
1186 if (flag_inline_functions_called_once
)
1189 fprintf (dump_file
, "\nDeciding on functions called once:\n");
1191 /* And finally decide what functions are called once. */
1192 for (i
= nnodes
- 1; i
>= 0; i
--)
1197 && !node
->callers
->next_caller
1199 && node
->local
.inlinable
1200 && node
->callers
->inline_failed
1201 && !gimple_call_cannot_inline_p (node
->callers
->call_stmt
)
1202 && !DECL_EXTERNAL (node
->decl
)
1203 && !DECL_COMDAT (node
->decl
))
1208 "\nConsidering %s %i insns.\n",
1209 cgraph_node_name (node
), node
->global
.insns
);
1211 " Called once from %s %i insns.\n",
1212 cgraph_node_name (node
->callers
->caller
),
1213 node
->callers
->caller
->global
.insns
);
1216 old_insns
= overall_insns
;
1218 if (cgraph_check_inline_limits (node
->callers
->caller
, node
,
1221 cgraph_mark_inline (node
->callers
);
1224 " Inlined into %s which now has %i insns"
1225 " for a net change of %+i insns.\n",
1226 cgraph_node_name (node
->callers
->caller
),
1227 node
->callers
->caller
->global
.insns
,
1228 overall_insns
- old_insns
);
1234 " Inline limit reached, not inlined.\n");
1240 /* Free ipa-prop structures if they are no longer needed. */
1241 if (flag_indirect_inlining
)
1242 free_all_ipa_structures_after_iinln ();
1246 "\nInlined %i calls, eliminated %i functions, "
1247 "%i insns turned to %i insns.\n\n",
1248 ncalls_inlined
, nfunctions_inlined
, initial_insns
,
1254 /* Try to inline edge E from incremental inliner. MODE specifies mode
1257 We are detecting cycles by storing mode of inliner into cgraph_node last
1258 time we visited it in the recursion. In general when mode is set, we have
1259 recursive inlining, but as an special case, we want to try harder inline
1260 ALWAYS_INLINE functions: consider callgraph a->b->c->b, with a being
1261 flatten, b being always inline. Flattening 'a' will collapse
1262 a->b->c before hitting cycle. To accommodate always inline, we however
1263 need to inline a->b->c->b.
1265 So after hitting cycle first time, we switch into ALWAYS_INLINE mode and
1266 stop inlining only after hitting ALWAYS_INLINE in ALWAY_INLINE mode. */
1268 try_inline (struct cgraph_edge
*e
, enum inlining_mode mode
, int depth
)
1270 struct cgraph_node
*callee
= e
->callee
;
1271 enum inlining_mode callee_mode
= (enum inlining_mode
) (size_t) callee
->aux
;
1272 bool always_inline
= e
->callee
->local
.disregard_inline_limits
;
1273 bool inlined
= false;
1275 /* We've hit cycle? */
1278 /* It is first time we see it and we are not in ALWAY_INLINE only
1279 mode yet. and the function in question is always_inline. */
1280 if (always_inline
&& mode
!= INLINE_ALWAYS_INLINE
)
1284 indent_to (dump_file
, depth
);
1286 "Hit cycle in %s, switching to always inline only.\n",
1287 cgraph_node_name (callee
));
1289 mode
= INLINE_ALWAYS_INLINE
;
1291 /* Otherwise it is time to give up. */
1296 indent_to (dump_file
, depth
);
1298 "Not inlining %s into %s to avoid cycle.\n",
1299 cgraph_node_name (callee
),
1300 cgraph_node_name (e
->caller
));
1302 e
->inline_failed
= (e
->callee
->local
.disregard_inline_limits
1303 ? CIF_RECURSIVE_INLINING
: CIF_UNSPECIFIED
);
1308 callee
->aux
= (void *)(size_t) mode
;
1311 indent_to (dump_file
, depth
);
1312 fprintf (dump_file
, " Inlining %s into %s.\n",
1313 cgraph_node_name (e
->callee
),
1314 cgraph_node_name (e
->caller
));
1316 if (e
->inline_failed
)
1318 cgraph_mark_inline (e
);
1320 /* In order to fully inline always_inline functions, we need to
1321 recurse here, since the inlined functions might not be processed by
1322 incremental inlining at all yet.
1324 Also flattening needs to be done recursively. */
1326 if (mode
== INLINE_ALL
|| always_inline
)
1327 cgraph_decide_inlining_incrementally (e
->callee
, mode
, depth
+ 1);
1330 callee
->aux
= (void *)(size_t) callee_mode
;
1334 /* Decide on the inlining. We do so in the topological order to avoid
1335 expenses on updating data structures.
1336 DEPTH is depth of recursion, used only for debug output. */
1339 cgraph_decide_inlining_incrementally (struct cgraph_node
*node
,
1340 enum inlining_mode mode
,
1343 struct cgraph_edge
*e
;
1344 bool inlined
= false;
1345 cgraph_inline_failed_t failed_reason
;
1346 enum inlining_mode old_mode
;
1348 #ifdef ENABLE_CHECKING
1349 verify_cgraph_node (node
);
1352 old_mode
= (enum inlining_mode
) (size_t)node
->aux
;
1354 if (mode
!= INLINE_ALWAYS_INLINE
&& mode
!= INLINE_SIZE_NORECURSIVE
1355 && lookup_attribute ("flatten", DECL_ATTRIBUTES (node
->decl
)) != NULL
)
1359 indent_to (dump_file
, depth
);
1360 fprintf (dump_file
, "Flattening %s\n", cgraph_node_name (node
));
1365 node
->aux
= (void *)(size_t) mode
;
1367 /* First of all look for always inline functions. */
1368 if (mode
!= INLINE_SIZE_NORECURSIVE
)
1369 for (e
= node
->callees
; e
; e
= e
->next_callee
)
1371 if (!e
->callee
->local
.disregard_inline_limits
1372 && (mode
!= INLINE_ALL
|| !e
->callee
->local
.inlinable
))
1374 if (gimple_call_cannot_inline_p (e
->call_stmt
))
1376 /* When the edge is already inlined, we just need to recurse into
1377 it in order to fully flatten the leaves. */
1378 if (!e
->inline_failed
&& mode
== INLINE_ALL
)
1380 inlined
|= try_inline (e
, mode
, depth
);
1385 indent_to (dump_file
, depth
);
1387 "Considering to always inline inline candidate %s.\n",
1388 cgraph_node_name (e
->callee
));
1390 if (cgraph_recursive_inlining_p (node
, e
->callee
, &e
->inline_failed
))
1394 indent_to (dump_file
, depth
);
1395 fprintf (dump_file
, "Not inlining: recursive call.\n");
1399 if (!tree_can_inline_p (node
->decl
, e
->callee
->decl
))
1401 gimple_call_set_cannot_inline (e
->call_stmt
, true);
1404 indent_to (dump_file
, depth
);
1406 "Not inlining: Target specific option mismatch.\n");
1410 if (gimple_in_ssa_p (DECL_STRUCT_FUNCTION (node
->decl
))
1411 != gimple_in_ssa_p (DECL_STRUCT_FUNCTION (e
->callee
->decl
)))
1415 indent_to (dump_file
, depth
);
1416 fprintf (dump_file
, "Not inlining: SSA form does not match.\n");
1420 if (!e
->callee
->analyzed
&& !e
->callee
->inline_decl
)
1424 indent_to (dump_file
, depth
);
1426 "Not inlining: Function body no longer available.\n");
1430 inlined
|= try_inline (e
, mode
, depth
);
1433 /* Now do the automatic inlining. */
1434 if (mode
!= INLINE_ALL
&& mode
!= INLINE_ALWAYS_INLINE
)
1435 for (e
= node
->callees
; e
; e
= e
->next_callee
)
1437 if (!e
->callee
->local
.inlinable
1438 || !e
->inline_failed
1439 || e
->callee
->local
.disregard_inline_limits
)
1442 fprintf (dump_file
, "Considering inline candidate %s.\n",
1443 cgraph_node_name (e
->callee
));
1444 if (cgraph_recursive_inlining_p (node
, e
->callee
, &e
->inline_failed
))
1448 indent_to (dump_file
, depth
);
1449 fprintf (dump_file
, "Not inlining: recursive call.\n");
1453 if (gimple_in_ssa_p (DECL_STRUCT_FUNCTION (node
->decl
))
1454 != gimple_in_ssa_p (DECL_STRUCT_FUNCTION (e
->callee
->decl
)))
1458 indent_to (dump_file
, depth
);
1459 fprintf (dump_file
, "Not inlining: SSA form does not match.\n");
1463 /* When the function body would grow and inlining the function won't
1464 eliminate the need for offline copy of the function, don't inline.
1466 if (((mode
== INLINE_SIZE
|| mode
== INLINE_SIZE_NORECURSIVE
)
1467 || (!flag_inline_functions
1468 && !DECL_DECLARED_INLINE_P (e
->callee
->decl
)))
1469 && (cgraph_estimate_size_after_inlining (1, e
->caller
, e
->callee
)
1470 > e
->caller
->global
.insns
)
1471 && cgraph_estimate_growth (e
->callee
) > 0)
1475 indent_to (dump_file
, depth
);
1477 "Not inlining: code size would grow by %i insns.\n",
1478 cgraph_estimate_size_after_inlining (1, e
->caller
,
1480 - e
->caller
->global
.insns
);
1484 if (!cgraph_check_inline_limits (node
, e
->callee
, &e
->inline_failed
,
1486 || gimple_call_cannot_inline_p (e
->call_stmt
))
1490 indent_to (dump_file
, depth
);
1491 fprintf (dump_file
, "Not inlining: %s.\n",
1492 cgraph_inline_failed_string (e
->inline_failed
));
1496 if (!e
->callee
->analyzed
&& !e
->callee
->inline_decl
)
1500 indent_to (dump_file
, depth
);
1502 "Not inlining: Function body no longer available.\n");
1506 if (!tree_can_inline_p (node
->decl
, e
->callee
->decl
))
1508 gimple_call_set_cannot_inline (e
->call_stmt
, true);
1511 indent_to (dump_file
, depth
);
1513 "Not inlining: Target specific option mismatch.\n");
1517 if (cgraph_default_inline_p (e
->callee
, &failed_reason
))
1518 inlined
|= try_inline (e
, mode
, depth
);
1520 node
->aux
= (void *)(size_t) old_mode
;
1524 /* Because inlining might remove no-longer reachable nodes, we need to
1525 keep the array visible to garbage collector to avoid reading collected
1528 static GTY ((length ("nnodes"))) struct cgraph_node
**order
;
1530 /* Do inlining of small functions. Doing so early helps profiling and other
1531 passes to be somewhat more effective and avoids some code duplication in
1532 later real inlining pass for testcases with very many function calls. */
1534 cgraph_early_inlining (void)
1536 struct cgraph_node
*node
= cgraph_node (current_function_decl
);
1537 unsigned int todo
= 0;
1540 if (sorrycount
|| errorcount
)
1542 while (cgraph_decide_inlining_incrementally (node
,
1544 ? INLINE_SIZE_NORECURSIVE
: INLINE_SIZE
, 0)
1545 && iterations
< PARAM_VALUE (PARAM_EARLY_INLINER_MAX_ITERATIONS
))
1547 timevar_push (TV_INTEGRATION
);
1548 todo
|= optimize_inline_calls (current_function_decl
);
1550 timevar_pop (TV_INTEGRATION
);
1553 fprintf (dump_file
, "Iterations: %i\n", iterations
);
1554 cfun
->always_inline_functions_inlined
= true;
1558 /* When inlining shall be performed. */
1560 cgraph_gate_early_inlining (void)
1562 return flag_early_inlining
;
1565 struct gimple_opt_pass pass_early_inline
=
1569 "einline", /* name */
1570 cgraph_gate_early_inlining
, /* gate */
1571 cgraph_early_inlining
, /* execute */
1574 0, /* static_pass_number */
1575 TV_INLINE_HEURISTICS
, /* tv_id */
1576 0, /* properties_required */
1577 0, /* properties_provided */
1578 0, /* properties_destroyed */
1579 0, /* todo_flags_start */
1580 TODO_dump_func
/* todo_flags_finish */
1584 /* When inlining shall be performed. */
1586 cgraph_gate_ipa_early_inlining (void)
1588 return (flag_early_inlining
1589 && (flag_branch_probabilities
|| flag_test_coverage
1590 || profile_arc_flag
));
1593 /* IPA pass wrapper for early inlining pass. We need to run early inlining
1594 before tree profiling so we have stand alone IPA pass for doing so. */
1595 struct simple_ipa_opt_pass pass_ipa_early_inline
=
1599 "einline_ipa", /* name */
1600 cgraph_gate_ipa_early_inlining
, /* gate */
1604 0, /* static_pass_number */
1605 TV_INLINE_HEURISTICS
, /* tv_id */
1606 0, /* properties_required */
1607 0, /* properties_provided */
1608 0, /* properties_destroyed */
1609 0, /* todo_flags_start */
1610 TODO_dump_cgraph
/* todo_flags_finish */
1614 /* Compute parameters of functions used by inliner. */
1616 compute_inline_parameters (struct cgraph_node
*node
)
1618 HOST_WIDE_INT self_stack_size
;
1620 gcc_assert (!node
->global
.inlined_to
);
1622 /* Estimate the stack size for the function. But not at -O0
1623 because estimated_stack_frame_size is a quadratic problem. */
1624 self_stack_size
= optimize
? estimated_stack_frame_size () : 0;
1625 inline_summary (node
)->estimated_self_stack_size
= self_stack_size
;
1626 node
->global
.estimated_stack_size
= self_stack_size
;
1627 node
->global
.stack_frame_offset
= 0;
1629 /* Can this function be inlined at all? */
1630 node
->local
.inlinable
= tree_inlinable_function_p (current_function_decl
);
1632 /* Estimate the number of instructions for this function.
1633 ??? At -O0 we don't use this information except for the dumps, and
1634 even then only for always_inline functions. But disabling this
1635 causes ICEs in the inline heuristics... */
1636 inline_summary (node
)->self_insns
1637 = estimate_num_insns_fn (current_function_decl
, &eni_inlining_weights
);
1638 if (node
->local
.inlinable
&& !node
->local
.disregard_inline_limits
)
1639 node
->local
.disregard_inline_limits
1640 = DECL_DISREGARD_INLINE_LIMITS (current_function_decl
);
1642 /* Inlining characteristics are maintained by the cgraph_mark_inline. */
1643 node
->global
.insns
= inline_summary (node
)->self_insns
;
1648 /* Compute parameters of functions used by inliner using
1649 current_function_decl. */
1651 compute_inline_parameters_for_current (void)
1653 compute_inline_parameters (cgraph_node (current_function_decl
));
1657 struct gimple_opt_pass pass_inline_parameters
=
1663 compute_inline_parameters_for_current
,/* execute */
1666 0, /* static_pass_number */
1667 TV_INLINE_HEURISTICS
, /* tv_id */
1668 0, /* properties_required */
1669 0, /* properties_provided */
1670 0, /* properties_destroyed */
1671 0, /* todo_flags_start */
1672 0 /* todo_flags_finish */
1676 /* This function performs intraprocedural analyzis in NODE that is required to
1677 inline indirect calls. */
1679 inline_indirect_intraprocedural_analysis (struct cgraph_node
*node
)
1681 struct cgraph_edge
*cs
;
1685 ipa_initialize_node_params (node
);
1686 ipa_detect_param_modifications (node
);
1688 ipa_analyze_params_uses (node
);
1691 for (cs
= node
->callees
; cs
; cs
= cs
->next_callee
)
1693 ipa_count_arguments (cs
);
1694 ipa_compute_jump_functions (cs
);
1699 ipa_print_node_params (dump_file
, node
);
1700 ipa_print_node_jump_functions (dump_file
, node
);
1704 /* Note function body size. */
1706 analyze_function (struct cgraph_node
*node
)
1708 push_cfun (DECL_STRUCT_FUNCTION (node
->decl
));
1709 current_function_decl
= node
->decl
;
1711 compute_inline_parameters (node
);
1712 if (flag_indirect_inlining
)
1713 inline_indirect_intraprocedural_analysis (node
);
1715 current_function_decl
= NULL
;
1719 /* Called when new function is inserted to callgraph late. */
1721 add_new_function (struct cgraph_node
*node
, void *data ATTRIBUTE_UNUSED
)
1723 analyze_function (node
);
1726 /* Note function body size. */
1728 inline_generate_summary (void)
1730 struct cgraph_node
*node
;
1732 function_insertion_hook_holder
=
1733 cgraph_add_function_insertion_hook (&add_new_function
, NULL
);
1735 if (flag_indirect_inlining
)
1737 ipa_register_cgraph_hooks ();
1738 ipa_check_create_node_params ();
1739 ipa_check_create_edge_args ();
1742 for (node
= cgraph_nodes
; node
; node
= node
->next
)
1744 analyze_function (node
);
1749 /* Apply inline plan to function. */
1751 inline_transform (struct cgraph_node
*node
)
1753 unsigned int todo
= 0;
1754 struct cgraph_edge
*e
;
1756 /* We might need the body of this function so that we can expand
1757 it inline somewhere else. */
1758 if (cgraph_preserve_function_body_p (node
->decl
))
1759 save_inline_function_body (node
);
1761 for (e
= node
->callees
; e
; e
= e
->next_callee
)
1762 if (!e
->inline_failed
|| warn_inline
)
1767 timevar_push (TV_INTEGRATION
);
1768 todo
= optimize_inline_calls (current_function_decl
);
1769 timevar_pop (TV_INTEGRATION
);
1771 cfun
->always_inline_functions_inlined
= true;
1772 cfun
->after_inlining
= true;
1773 return todo
| execute_fixup_cfg ();
1776 struct ipa_opt_pass_d pass_ipa_inline
=
1780 "inline", /* name */
1782 cgraph_decide_inlining
, /* execute */
1785 0, /* static_pass_number */
1786 TV_INLINE_HEURISTICS
, /* tv_id */
1787 0, /* properties_required */
1788 0, /* properties_provided */
1789 0, /* properties_destroyed */
1790 TODO_remove_functions
, /* todo_flags_finish */
1791 TODO_dump_cgraph
| TODO_dump_func
1792 | TODO_remove_functions
/* todo_flags_finish */
1794 inline_generate_summary
, /* generate_summary */
1795 NULL
, /* write_summary */
1796 NULL
, /* read_summary */
1797 NULL
, /* function_read_summary */
1799 inline_transform
, /* function_transform */
1800 NULL
, /* variable_transform */
1804 #include "gt-ipa-inline.h"