1 /* Inlining decision heuristics.
2 Copyright (C) 2003, 2004 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 2, 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 COPYING. If not, write to the Free
19 Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA
22 /* Inlining decision heuristics
24 We separate inlining decisions from the inliner itself and store it
25 inside callgraph as so called inline plan. Refer to cgraph.c
26 documentation about particular representation of inline plans in the
29 There are three major parts of this file:
31 cgraph_mark_inline implementation
33 This function allows to mark given call inline and performs necessary
34 modifications of cgraph (production of the clones and updating overall
37 inlining heuristics limits
39 These functions allow to check that particular inlining is allowed
40 by the limits specified by user (allowed function growth, overall unit
45 This is implementation of IPA pass aiming to get as much of benefit
46 from inlining obeying the limits checked above.
48 The implementation of particular heuristics is separated from
49 the rest of code to make it easier to replace it with more complicated
50 implementation in the future. The rest of inlining code acts as a
51 library aimed to modify the callgraph and verify that the parameters
52 on code size growth fits.
54 To mark given call inline, use cgraph_mark_inline function, the
55 verification is performed by cgraph_default_inline_p and
56 cgraph_check_inline_limits.
58 The heuristics implements simple knapsack style algorithm ordering
59 all functions by their "profitability" (estimated by code size growth)
60 and inlining them in priority order.
62 cgraph_decide_inlining implements heuristics taking whole callgraph
63 into account, while cgraph_decide_inlining_incrementally considers
64 only one function at a time and is used in non-unit-at-a-time mode. */
68 #include "coretypes.h"
71 #include "tree-inline.h"
72 #include "langhooks.h"
75 #include "diagnostic.h"
80 #include "tree-pass.h"
85 /* Statistics we collect about inlining algorithm. */
86 static int ncalls_inlined
;
87 static int nfunctions_inlined
;
88 static int initial_insns
;
89 static int overall_insns
;
91 static gcov_type max_count
;
93 /* Estimate size of the function after inlining WHAT into TO. */
96 cgraph_estimate_size_after_inlining (int times
, struct cgraph_node
*to
,
97 struct cgraph_node
*what
)
100 tree fndecl
= what
->decl
, arg
;
101 int call_insns
= PARAM_VALUE (PARAM_INLINE_CALL_COST
);
103 for (arg
= DECL_ARGUMENTS (fndecl
); arg
; arg
= TREE_CHAIN (arg
))
104 call_insns
+= estimate_move_cost (TREE_TYPE (arg
));
105 size
= (what
->global
.insns
- call_insns
) * times
+ to
->global
.insns
;
106 gcc_assert (size
>= 0);
110 /* E is expected to be an edge being inlined. Clone destination node of
111 the edge and redirect it to the new clone.
112 DUPLICATE is used for bookkeeping on whether we are actually creating new
113 clones or re-using node originally representing out-of-line function call.
116 cgraph_clone_inlined_nodes (struct cgraph_edge
*e
, bool duplicate
)
118 struct cgraph_node
*n
;
120 /* We may eliminate the need for out-of-line copy to be output. In that
121 case just go ahead and re-use it. */
122 if (!e
->callee
->callers
->next_caller
123 && (!e
->callee
->needed
|| DECL_EXTERNAL (e
->callee
->decl
))
125 && flag_unit_at_a_time
)
127 gcc_assert (!e
->callee
->global
.inlined_to
);
128 if (!DECL_EXTERNAL (e
->callee
->decl
))
129 overall_insns
-= e
->callee
->global
.insns
, nfunctions_inlined
++;
134 n
= cgraph_clone_node (e
->callee
, e
->count
, e
->loop_nest
, true);
135 cgraph_redirect_edge_callee (e
, n
);
138 if (e
->caller
->global
.inlined_to
)
139 e
->callee
->global
.inlined_to
= e
->caller
->global
.inlined_to
;
141 e
->callee
->global
.inlined_to
= e
->caller
;
143 /* Recursively clone all bodies. */
144 for (e
= e
->callee
->callees
; e
; e
= e
->next_callee
)
145 if (!e
->inline_failed
)
146 cgraph_clone_inlined_nodes (e
, duplicate
);
149 /* Mark edge E as inlined and update callgraph accordingly. */
152 cgraph_mark_inline_edge (struct cgraph_edge
*e
)
154 int old_insns
= 0, new_insns
= 0;
155 struct cgraph_node
*to
= NULL
, *what
;
157 gcc_assert (e
->inline_failed
);
158 e
->inline_failed
= NULL
;
160 if (!e
->callee
->global
.inlined
&& flag_unit_at_a_time
)
161 DECL_POSSIBLY_INLINED (e
->callee
->decl
) = true;
162 e
->callee
->global
.inlined
= true;
164 cgraph_clone_inlined_nodes (e
, true);
168 /* Now update size of caller and all functions caller is inlined into. */
169 for (;e
&& !e
->inline_failed
; e
= e
->caller
->callers
)
171 old_insns
= e
->caller
->global
.insns
;
172 new_insns
= cgraph_estimate_size_after_inlining (1, e
->caller
,
174 gcc_assert (new_insns
>= 0);
176 to
->global
.insns
= new_insns
;
178 gcc_assert (what
->global
.inlined_to
== to
);
179 if (new_insns
> old_insns
)
180 overall_insns
+= new_insns
- old_insns
;
184 /* Mark all calls of EDGE->CALLEE inlined into EDGE->CALLER.
185 Return following unredirected edge in the list of callers
188 static struct cgraph_edge
*
189 cgraph_mark_inline (struct cgraph_edge
*edge
)
191 struct cgraph_node
*to
= edge
->caller
;
192 struct cgraph_node
*what
= edge
->callee
;
193 struct cgraph_edge
*e
, *next
;
196 /* Look for all calls, mark them inline and clone recursively
197 all inlined functions. */
198 for (e
= what
->callers
; e
; e
= next
)
200 next
= e
->next_caller
;
201 if (e
->caller
== to
&& e
->inline_failed
)
203 cgraph_mark_inline_edge (e
);
213 /* Estimate the growth caused by inlining NODE into all callees. */
216 cgraph_estimate_growth (struct cgraph_node
*node
)
219 struct cgraph_edge
*e
;
220 if (node
->global
.estimated_growth
!= INT_MIN
)
221 return node
->global
.estimated_growth
;
223 for (e
= node
->callers
; e
; e
= e
->next_caller
)
224 if (e
->inline_failed
)
225 growth
+= (cgraph_estimate_size_after_inlining (1, e
->caller
, node
)
226 - e
->caller
->global
.insns
);
228 /* ??? Wrong for self recursive functions or cases where we decide to not
229 inline for different reasons, but it is not big deal as in that case
230 we will keep the body around, but we will also avoid some inlining. */
231 if (!node
->needed
&& !DECL_EXTERNAL (node
->decl
))
232 growth
-= node
->global
.insns
;
234 node
->global
.estimated_growth
= growth
;
238 /* Return false when inlining WHAT into TO is not good idea
239 as it would cause too large growth of function bodies. */
242 cgraph_check_inline_limits (struct cgraph_node
*to
, struct cgraph_node
*what
,
246 struct cgraph_edge
*e
;
250 if (to
->global
.inlined_to
)
251 to
= to
->global
.inlined_to
;
253 for (e
= to
->callees
; e
; e
= e
->next_callee
)
254 if (e
->callee
== what
)
257 /* When inlining large function body called once into small function,
258 take the inlined function as base for limiting the growth. */
259 if (to
->local
.self_insns
> what
->local
.self_insns
)
260 limit
= to
->local
.self_insns
;
262 limit
= what
->local
.self_insns
;
264 limit
+= limit
* PARAM_VALUE (PARAM_LARGE_FUNCTION_GROWTH
) / 100;
266 newsize
= cgraph_estimate_size_after_inlining (times
, to
, what
);
267 if (newsize
> PARAM_VALUE (PARAM_LARGE_FUNCTION_INSNS
)
271 *reason
= N_("--param large-function-growth limit reached");
277 /* Return true when function N is small enough to be inlined. */
280 cgraph_default_inline_p (struct cgraph_node
*n
, const char **reason
)
282 if (!DECL_INLINE (n
->decl
))
285 *reason
= N_("function not inlinable");
289 if (!DECL_SAVED_TREE (n
->decl
))
292 *reason
= N_("function body not available");
296 if (DECL_DECLARED_INLINE_P (n
->decl
))
298 if (n
->global
.insns
>= MAX_INLINE_INSNS_SINGLE
)
301 *reason
= N_("--param max-inline-insns-single limit reached");
307 if (n
->global
.insns
>= MAX_INLINE_INSNS_AUTO
)
310 *reason
= N_("--param max-inline-insns-auto limit reached");
318 /* Return true when inlining WHAT would create recursive inlining.
319 We call recursive inlining all cases where same function appears more than
320 once in the single recursion nest path in the inline graph. */
323 cgraph_recursive_inlining_p (struct cgraph_node
*to
,
324 struct cgraph_node
*what
,
328 if (to
->global
.inlined_to
)
329 recursive
= what
->decl
== to
->global
.inlined_to
->decl
;
331 recursive
= what
->decl
== to
->decl
;
332 /* Marking recursive function inline has sane semantic and thus we should
334 if (recursive
&& reason
)
335 *reason
= (what
->local
.disregard_inline_limits
336 ? N_("recursive inlining") : "");
340 /* Return true if the call can be hot. */
342 cgraph_maybe_hot_edge_p (struct cgraph_edge
*edge
)
344 if (profile_info
&& flag_branch_probabilities
346 <= profile_info
->sum_max
/ PARAM_VALUE (HOT_BB_COUNT_FRACTION
)))
351 /* A cost model driving the inlining heuristics in a way so the edges with
352 smallest badness are inlined first. After each inlining is performed
353 the costs of all caller edges of nodes affected are recomputed so the
354 metrics may accurately depend on values such as number of inlinable callers
355 of the function or function body size.
357 With profiling we use number of executions of each edge to drive the cost.
358 We also should distinguish hot and cold calls where the cold calls are
359 inlined into only when code size is overall improved.
363 cgraph_edge_badness (struct cgraph_edge
*edge
)
368 cgraph_estimate_size_after_inlining (1, edge
->caller
, edge
->callee
);
369 growth
-= edge
->caller
->global
.insns
;
371 /* Always prefer inlining saving code size. */
373 return INT_MIN
- growth
;
374 return ((int)((double)edge
->count
* INT_MIN
/ max_count
)) / growth
;
378 int nest
= MIN (edge
->loop_nest
, 8);
379 int badness
= cgraph_estimate_growth (edge
->callee
) * 256;
381 /* Decrease badness if call is nested. */
387 /* Make recursive inlining happen always after other inlining is done. */
388 if (cgraph_recursive_inlining_p (edge
->caller
, edge
->callee
, NULL
))
395 /* Recompute heap nodes for each of caller edge. */
398 update_caller_keys (fibheap_t heap
, struct cgraph_node
*node
,
399 bitmap updated_nodes
)
401 struct cgraph_edge
*edge
;
403 if (!node
->local
.inlinable
|| node
->local
.disregard_inline_limits
404 || node
->global
.inlined_to
)
406 if (bitmap_bit_p (updated_nodes
, node
->uid
))
408 bitmap_set_bit (updated_nodes
, node
->uid
);
409 node
->global
.estimated_growth
= INT_MIN
;
411 for (edge
= node
->callers
; edge
; edge
= edge
->next_caller
)
412 if (edge
->inline_failed
)
414 int badness
= cgraph_edge_badness (edge
);
417 fibnode_t n
= edge
->aux
;
418 gcc_assert (n
->data
== edge
);
419 if (n
->key
== badness
)
422 /* fibheap_replace_key only increase the keys. */
423 if (fibheap_replace_key (heap
, n
, badness
))
425 fibheap_delete_node (heap
, edge
->aux
);
427 edge
->aux
= fibheap_insert (heap
, badness
, edge
);
431 /* Recompute heap nodes for each of caller edges of each of callees. */
434 update_callee_keys (fibheap_t heap
, struct cgraph_node
*node
,
435 bitmap updated_nodes
)
437 struct cgraph_edge
*e
;
438 node
->global
.estimated_growth
= INT_MIN
;
440 for (e
= node
->callees
; e
; e
= e
->next_callee
)
441 if (e
->inline_failed
)
442 update_caller_keys (heap
, e
->callee
, updated_nodes
);
443 else if (!e
->inline_failed
)
444 update_callee_keys (heap
, e
->callee
, updated_nodes
);
447 /* Enqueue all recursive calls from NODE into priority queue depending on
448 how likely we want to recursively inline the call. */
451 lookup_recursive_calls (struct cgraph_node
*node
, struct cgraph_node
*where
,
455 struct cgraph_edge
*e
;
456 for (e
= where
->callees
; e
; e
= e
->next_callee
)
457 if (e
->callee
== node
)
459 /* When profile feedback is available, prioritize by expected number
460 of calls. Without profile feedback we maintain simple queue
461 to order candidates via recursive depths. */
462 fibheap_insert (heap
,
463 !max_count
? priority
++
464 : -(e
->count
/ ((max_count
+ (1<<24) - 1) / (1<<24))),
467 for (e
= where
->callees
; e
; e
= e
->next_callee
)
468 if (!e
->inline_failed
)
469 lookup_recursive_calls (node
, e
->callee
, heap
);
472 /* Find callgraph nodes closing a circle in the graph. The
473 resulting hashtab can be used to avoid walking the circles.
474 Uses the cgraph nodes ->aux field which needs to be zero
475 before and will be zero after operation. */
478 cgraph_find_cycles (struct cgraph_node
*node
, htab_t cycles
)
480 struct cgraph_edge
*e
;
485 slot
= htab_find_slot (cycles
, node
, INSERT
);
489 fprintf (dump_file
, "Cycle contains %s\n", cgraph_node_name (node
));
496 for (e
= node
->callees
; e
; e
= e
->next_callee
)
497 cgraph_find_cycles (e
->callee
, cycles
);
501 /* Leafify the cgraph node. We have to be careful in recursing
502 as to not run endlessly in circles of the callgraph.
503 We do so by using a hashtab of cycle entering nodes as generated
504 by cgraph_find_cycles. */
507 cgraph_flatten_node (struct cgraph_node
*node
, htab_t cycles
)
509 struct cgraph_edge
*e
;
511 for (e
= node
->callees
; e
; e
= e
->next_callee
)
513 /* Inline call, if possible, and recurse. Be sure we are not
514 entering callgraph circles here. */
516 && e
->callee
->local
.inlinable
517 && !cgraph_recursive_inlining_p (node
, e
->callee
,
519 && !htab_find (cycles
, e
->callee
))
522 fprintf (dump_file
, " inlining %s", cgraph_node_name (e
->callee
));
523 cgraph_mark_inline_edge (e
);
524 cgraph_flatten_node (e
->callee
, cycles
);
527 fprintf (dump_file
, " !inlining %s", cgraph_node_name (e
->callee
));
531 /* Decide on recursive inlining: in the case function has recursive calls,
532 inline until body size reaches given argument. */
535 cgraph_decide_recursive_inlining (struct cgraph_node
*node
)
537 int limit
= PARAM_VALUE (PARAM_MAX_INLINE_INSNS_RECURSIVE_AUTO
);
538 int max_depth
= PARAM_VALUE (PARAM_MAX_INLINE_RECURSIVE_DEPTH_AUTO
);
539 int probability
= PARAM_VALUE (PARAM_MIN_INLINE_RECURSIVE_PROBABILITY
);
541 struct cgraph_edge
*e
;
542 struct cgraph_node
*master_clone
;
546 if (DECL_DECLARED_INLINE_P (node
->decl
))
548 limit
= PARAM_VALUE (PARAM_MAX_INLINE_INSNS_RECURSIVE
);
549 max_depth
= PARAM_VALUE (PARAM_MAX_INLINE_RECURSIVE_DEPTH
);
552 /* Make sure that function is small enough to be considered for inlining. */
554 || cgraph_estimate_size_after_inlining (1, node
, node
) >= limit
)
556 heap
= fibheap_new ();
557 lookup_recursive_calls (node
, node
, heap
);
558 if (fibheap_empty (heap
))
560 fibheap_delete (heap
);
566 " Performing recursive inlining on %s\n",
567 cgraph_node_name (node
));
569 /* We need original clone to copy around. */
570 master_clone
= cgraph_clone_node (node
, node
->count
, 1, false);
571 master_clone
->needed
= true;
572 for (e
= master_clone
->callees
; e
; e
= e
->next_callee
)
573 if (!e
->inline_failed
)
574 cgraph_clone_inlined_nodes (e
, true);
576 /* Do the inlining and update list of recursive call during process. */
577 while (!fibheap_empty (heap
)
578 && (cgraph_estimate_size_after_inlining (1, node
, master_clone
)
581 struct cgraph_edge
*curr
= fibheap_extract_min (heap
);
582 struct cgraph_node
*cnode
;
585 for (cnode
= curr
->caller
;
586 cnode
->global
.inlined_to
; cnode
= cnode
->callers
->caller
)
587 if (node
->decl
== curr
->callee
->decl
)
589 if (depth
> max_depth
)
593 " maxmal depth reached\n");
599 if (!cgraph_maybe_hot_edge_p (curr
))
602 fprintf (dump_file
, " Not inlining cold call\n");
605 if (curr
->count
* 100 / node
->count
< probability
)
609 " Probability of edge is too small\n");
617 " Inlining call of depth %i", depth
);
620 fprintf (dump_file
, " called approx. %.2f times per call",
621 (double)curr
->count
/ node
->count
);
623 fprintf (dump_file
, "\n");
625 cgraph_redirect_edge_callee (curr
, master_clone
);
626 cgraph_mark_inline_edge (curr
);
627 lookup_recursive_calls (node
, curr
->callee
, heap
);
630 if (!fibheap_empty (heap
) && dump_file
)
631 fprintf (dump_file
, " Recursive inlining growth limit met.\n");
633 fibheap_delete (heap
);
636 "\n Inlined %i times, body grown from %i to %i insns\n", n
,
637 master_clone
->global
.insns
, node
->global
.insns
);
639 /* Remove master clone we used for inlining. We rely that clones inlined
640 into master clone gets queued just before master clone so we don't
642 for (node
= cgraph_nodes
; node
!= master_clone
;
644 if (node
->global
.inlined_to
== master_clone
)
645 cgraph_remove_node (node
);
646 cgraph_remove_node (master_clone
);
647 /* FIXME: Recursive inlining actually reduces number of calls of the
648 function. At this place we should probably walk the function and
649 inline clones and compensate the counts accordingly. This probably
650 doesn't matter much in practice. */
654 /* Set inline_failed for all callers of given function to REASON. */
657 cgraph_set_inline_failed (struct cgraph_node
*node
, const char *reason
)
659 struct cgraph_edge
*e
;
662 fprintf (dump_file
, "Inlining failed: %s\n", reason
);
663 for (e
= node
->callers
; e
; e
= e
->next_caller
)
664 if (e
->inline_failed
)
665 e
->inline_failed
= reason
;
668 /* We use greedy algorithm for inlining of small functions:
669 All inline candidates are put into prioritized heap based on estimated
670 growth of the overall number of instructions and then update the estimates.
672 INLINED and INLINED_CALEES are just pointers to arrays large enough
673 to be passed to cgraph_inlined_into and cgraph_inlined_callees. */
676 cgraph_decide_inlining_of_small_functions (void)
678 struct cgraph_node
*node
;
679 struct cgraph_edge
*edge
;
680 const char *failed_reason
;
681 fibheap_t heap
= fibheap_new ();
682 bitmap updated_nodes
= BITMAP_ALLOC (NULL
);
685 fprintf (dump_file
, "\nDeciding on smaller functions:\n");
687 /* Put all inline candidates into the heap. */
689 for (node
= cgraph_nodes
; node
; node
= node
->next
)
691 if (!node
->local
.inlinable
|| !node
->callers
692 || node
->local
.disregard_inline_limits
)
695 fprintf (dump_file
, "Considering inline candidate %s.\n", cgraph_node_name (node
));
697 node
->global
.estimated_growth
= INT_MIN
;
698 if (!cgraph_default_inline_p (node
, &failed_reason
))
700 cgraph_set_inline_failed (node
, failed_reason
);
704 for (edge
= node
->callers
; edge
; edge
= edge
->next_caller
)
705 if (edge
->inline_failed
)
707 gcc_assert (!edge
->aux
);
708 edge
->aux
= fibheap_insert (heap
, cgraph_edge_badness (edge
), edge
);
711 while (overall_insns
<= max_insns
&& (edge
= fibheap_extract_min (heap
)))
713 int old_insns
= overall_insns
;
714 struct cgraph_node
*where
;
716 cgraph_estimate_size_after_inlining (1, edge
->caller
, edge
->callee
);
718 growth
-= edge
->caller
->global
.insns
;
723 "\nConsidering %s with %i insns to be inlined into %s\n"
724 " Estimated growth after inlined into all callees is %+i insns.\n"
725 " Estimated badness is %i.\n",
726 cgraph_node_name (edge
->callee
),
727 edge
->callee
->global
.insns
,
728 cgraph_node_name (edge
->caller
),
729 cgraph_estimate_growth (edge
->callee
),
730 cgraph_edge_badness (edge
));
732 fprintf (dump_file
," Called "HOST_WIDEST_INT_PRINT_DEC
"x\n", edge
->count
);
734 gcc_assert (edge
->aux
);
736 if (!edge
->inline_failed
)
739 /* When not having profile info ready we don't weight by any way the
740 position of call in procedure itself. This means if call of
741 function A from function B seems profitable to inline, the recursive
742 call of function A in inline copy of A in B will look profitable too
743 and we end up inlining until reaching maximal function growth. This
744 is not good idea so prohibit the recursive inlining.
746 ??? When the frequencies are taken into account we might not need this
750 where
= edge
->caller
;
751 while (where
->global
.inlined_to
)
753 if (where
->decl
== edge
->callee
->decl
)
755 where
= where
->callers
->caller
;
757 if (where
->global
.inlined_to
)
760 = (edge
->callee
->local
.disregard_inline_limits
? N_("recursive inlining") : "");
762 fprintf (dump_file
, " inline_failed:Recursive inlining performed only for function itself.\n");
767 if (!cgraph_maybe_hot_edge_p (edge
) && growth
> 0)
769 if (!cgraph_recursive_inlining_p (edge
->caller
, edge
->callee
,
770 &edge
->inline_failed
))
772 edge
->inline_failed
=
773 N_("call is unlikely");
775 fprintf (dump_file
, " inline_failed:%s.\n", edge
->inline_failed
);
779 if (!cgraph_default_inline_p (edge
->callee
, &edge
->inline_failed
))
781 if (!cgraph_recursive_inlining_p (edge
->caller
, edge
->callee
,
782 &edge
->inline_failed
))
785 fprintf (dump_file
, " inline_failed:%s.\n", edge
->inline_failed
);
789 if (cgraph_recursive_inlining_p (edge
->caller
, edge
->callee
,
790 &edge
->inline_failed
))
792 where
= edge
->caller
;
793 if (where
->global
.inlined_to
)
794 where
= where
->global
.inlined_to
;
795 if (!cgraph_decide_recursive_inlining (where
))
797 update_callee_keys (heap
, where
, updated_nodes
);
801 struct cgraph_node
*callee
;
802 if (!cgraph_check_inline_limits (edge
->caller
, edge
->callee
,
803 &edge
->inline_failed
))
806 fprintf (dump_file
, " Not inlining into %s:%s.\n",
807 cgraph_node_name (edge
->caller
), edge
->inline_failed
);
810 callee
= edge
->callee
;
811 cgraph_mark_inline_edge (edge
);
812 update_callee_keys (heap
, callee
, updated_nodes
);
814 where
= edge
->caller
;
815 if (where
->global
.inlined_to
)
816 where
= where
->global
.inlined_to
;
818 /* Our profitability metric can depend on local properties
819 such as number of inlinable calls and size of the function body.
820 After inlining these properties might change for the function we
821 inlined into (since it's body size changed) and for the functions
822 called by function we inlined (since number of it inlinable callers
824 update_caller_keys (heap
, where
, updated_nodes
);
825 bitmap_clear (updated_nodes
);
829 " Inlined into %s which now has %i insns.\n",
830 cgraph_node_name (edge
->caller
),
831 edge
->caller
->global
.insns
);
834 " Inlined for a net change of %+i insns.\n",
835 overall_insns
- old_insns
);
837 while ((edge
= fibheap_extract_min (heap
)) != NULL
)
839 gcc_assert (edge
->aux
);
841 if (!edge
->callee
->local
.disregard_inline_limits
&& edge
->inline_failed
842 && !cgraph_recursive_inlining_p (edge
->caller
, edge
->callee
,
843 &edge
->inline_failed
))
844 edge
->inline_failed
= N_("--param inline-unit-growth limit reached");
846 fibheap_delete (heap
);
847 BITMAP_FREE (updated_nodes
);
850 /* Decide on the inlining. We do so in the topological order to avoid
851 expenses on updating data structures. */
854 cgraph_decide_inlining (void)
856 struct cgraph_node
*node
;
858 struct cgraph_node
**order
=
859 xcalloc (cgraph_n_nodes
, sizeof (struct cgraph_node
*));
863 timevar_push (TV_INLINE_HEURISTICS
);
865 for (node
= cgraph_nodes
; node
; node
= node
->next
)
867 struct cgraph_edge
*e
;
868 initial_insns
+= node
->local
.self_insns
;
869 for (e
= node
->callees
; e
; e
= e
->next_callee
)
870 if (max_count
< e
->count
)
871 max_count
= e
->count
;
873 overall_insns
= initial_insns
;
874 gcc_assert (!max_count
|| (profile_info
&& flag_branch_probabilities
));
876 max_insns
= ((HOST_WIDEST_INT
) overall_insns
877 * (100 + PARAM_VALUE (PARAM_INLINE_UNIT_GROWTH
)) / 100);
879 nnodes
= cgraph_postorder (order
);
883 "\nDeciding on inlining. Starting with %i insns.\n",
886 for (node
= cgraph_nodes
; node
; node
= node
->next
)
890 fprintf (dump_file
, "\nInlining always_inline functions:\n");
892 /* In the first pass mark all always_inline edges. Do this with a priority
893 so none of our later choices will make this impossible. */
894 for (i
= nnodes
- 1; i
>= 0; i
--)
896 struct cgraph_edge
*e
, *next
;
900 /* Handle nodes to be flattened, but don't update overall unit size. */
901 if (lookup_attribute ("flatten", DECL_ATTRIBUTES (node
->decl
)) != NULL
)
903 int old_overall_insns
= overall_insns
;
907 "Leafifying %s\n", cgraph_node_name (node
));
908 cycles
= htab_create (7, htab_hash_pointer
, htab_eq_pointer
, NULL
);
909 cgraph_find_cycles (node
, cycles
);
910 cgraph_flatten_node (node
, cycles
);
911 htab_delete (cycles
);
912 overall_insns
= old_overall_insns
;
913 /* We don't need to consider always_inline functions inside the flattened
918 if (!node
->local
.disregard_inline_limits
)
922 "\nConsidering %s %i insns (always inline)\n",
923 cgraph_node_name (node
), node
->global
.insns
);
924 old_insns
= overall_insns
;
925 for (e
= node
->callers
; e
; e
= next
)
927 next
= e
->next_caller
;
928 if (!e
->inline_failed
)
930 if (cgraph_recursive_inlining_p (e
->caller
, e
->callee
,
933 cgraph_mark_inline_edge (e
);
936 " Inlined into %s which now has %i insns.\n",
937 cgraph_node_name (e
->caller
),
938 e
->caller
->global
.insns
);
942 " Inlined for a net change of %+i insns.\n",
943 overall_insns
- old_insns
);
946 if (!flag_really_no_inline
)
948 cgraph_decide_inlining_of_small_functions ();
951 fprintf (dump_file
, "\nDeciding on functions called once:\n");
953 /* And finally decide what functions are called once. */
955 for (i
= nnodes
- 1; i
>= 0; i
--)
959 if (node
->callers
&& !node
->callers
->next_caller
&& !node
->needed
960 && node
->local
.inlinable
&& node
->callers
->inline_failed
961 && !DECL_EXTERNAL (node
->decl
) && !DECL_COMDAT (node
->decl
))
964 struct cgraph_node
*node1
;
966 /* Verify that we won't duplicate the caller. */
967 for (node1
= node
->callers
->caller
;
968 node1
->callers
&& !node1
->callers
->inline_failed
969 && ok
; node1
= node1
->callers
->caller
)
970 if (node1
->callers
->next_caller
|| node1
->needed
)
976 "\nConsidering %s %i insns.\n"
977 " Called once from %s %i insns.\n",
978 cgraph_node_name (node
), node
->global
.insns
,
979 cgraph_node_name (node
->callers
->caller
),
980 node
->callers
->caller
->global
.insns
);
982 old_insns
= overall_insns
;
984 if (cgraph_check_inline_limits (node
->callers
->caller
, node
,
987 cgraph_mark_inline (node
->callers
);
990 " Inlined into %s which now has %i insns"
991 " for a net change of %+i insns.\n",
992 cgraph_node_name (node
->callers
->caller
),
993 node
->callers
->caller
->global
.insns
,
994 overall_insns
- old_insns
);
1000 " Inline limit reached, not inlined.\n");
1009 "\nInlined %i calls, eliminated %i functions, "
1010 "%i insns turned to %i insns.\n\n",
1011 ncalls_inlined
, nfunctions_inlined
, initial_insns
,
1014 timevar_pop (TV_INLINE_HEURISTICS
);
1017 /* Decide on the inlining. We do so in the topological order to avoid
1018 expenses on updating data structures. */
1021 cgraph_decide_inlining_incrementally (struct cgraph_node
*node
, bool early
)
1023 struct cgraph_edge
*e
;
1024 bool inlined
= false;
1025 const char *failed_reason
;
1027 /* First of all look for always inline functions. */
1028 for (e
= node
->callees
; e
; e
= e
->next_callee
)
1029 if (e
->callee
->local
.disregard_inline_limits
1031 && !cgraph_recursive_inlining_p (node
, e
->callee
, &e
->inline_failed
)
1032 /* ??? It is possible that renaming variable removed the function body
1033 in duplicate_decls. See gcc.c-torture/compile/20011119-2.c */
1034 && DECL_SAVED_TREE (e
->callee
->decl
))
1036 if (dump_file
&& early
)
1037 fprintf (dump_file
, " Early inlining %s into %s\n",
1038 cgraph_node_name (e
->callee
), cgraph_node_name (node
));
1039 cgraph_mark_inline (e
);
1043 /* Now do the automatic inlining. */
1044 if (!flag_really_no_inline
)
1045 for (e
= node
->callees
; e
; e
= e
->next_callee
)
1046 if (e
->callee
->local
.inlinable
1048 && !e
->callee
->local
.disregard_inline_limits
1049 && !cgraph_recursive_inlining_p (node
, e
->callee
, &e
->inline_failed
)
1051 || (cgraph_estimate_size_after_inlining (1, e
->caller
, node
)
1052 <= e
->caller
->global
.insns
))
1053 && cgraph_check_inline_limits (node
, e
->callee
, &e
->inline_failed
)
1054 && DECL_SAVED_TREE (e
->callee
->decl
))
1056 if (cgraph_default_inline_p (e
->callee
, &failed_reason
))
1058 if (dump_file
&& early
)
1059 fprintf (dump_file
, " Early inlining %s into %s\n",
1060 cgraph_node_name (e
->callee
), cgraph_node_name (node
));
1061 cgraph_mark_inline (e
);
1065 e
->inline_failed
= failed_reason
;
1067 if (early
&& inlined
)
1069 push_cfun (DECL_STRUCT_FUNCTION (node
->decl
));
1070 tree_register_cfg_hooks ();
1071 current_function_decl
= node
->decl
;
1072 optimize_inline_calls (current_function_decl
);
1073 node
->local
.self_insns
= node
->global
.insns
;
1074 current_function_decl
= NULL
;
1080 /* When inlining shall be performed. */
1082 cgraph_gate_inlining (void)
1084 return flag_inline_trees
;
1087 struct tree_opt_pass pass_ipa_inline
=
1089 "inline", /* name */
1090 cgraph_gate_inlining
, /* gate */
1091 cgraph_decide_inlining
, /* execute */
1094 0, /* static_pass_number */
1095 TV_INTEGRATION
, /* tv_id */
1096 0, /* properties_required */
1097 PROP_cfg
, /* properties_provided */
1098 0, /* properties_destroyed */
1099 0, /* todo_flags_start */
1100 TODO_dump_cgraph
| TODO_dump_func
, /* todo_flags_finish */
1104 /* Do inlining of small functions. Doing so early helps profiling and other
1105 passes to be somewhat more effective and avoids some code duplication in
1106 later real inlining pass for testcases with very many function calls. */
1108 cgraph_early_inlining (void)
1110 struct cgraph_node
*node
;
1112 struct cgraph_node
**order
=
1113 xcalloc (cgraph_n_nodes
, sizeof (struct cgraph_node
*));
1116 if (sorrycount
|| errorcount
)
1118 #ifdef ENABLE_CHECKING
1119 for (node
= cgraph_nodes
; node
; node
= node
->next
)
1120 gcc_assert (!node
->aux
);
1123 nnodes
= cgraph_postorder (order
);
1124 for (i
= nnodes
- 1; i
>= 0; i
--)
1127 if (node
->analyzed
&& node
->local
.inlinable
1128 && (node
->needed
|| node
->reachable
)
1130 cgraph_decide_inlining_incrementally (node
, true);
1132 cgraph_remove_unreachable_nodes (true, dump_file
);
1133 #ifdef ENABLE_CHECKING
1134 for (node
= cgraph_nodes
; node
; node
= node
->next
)
1135 gcc_assert (!node
->global
.inlined_to
);
1140 /* When inlining shall be performed. */
1142 cgraph_gate_early_inlining (void)
1144 return flag_inline_trees
&& flag_early_inlining
;
1147 struct tree_opt_pass pass_early_ipa_inline
=
1149 "einline", /* name */
1150 cgraph_gate_early_inlining
, /* gate */
1151 cgraph_early_inlining
, /* execute */
1154 0, /* static_pass_number */
1155 TV_INTEGRATION
, /* tv_id */
1156 0, /* properties_required */
1157 PROP_cfg
, /* properties_provided */
1158 0, /* properties_destroyed */
1159 0, /* todo_flags_start */
1160 TODO_dump_cgraph
| TODO_dump_func
, /* todo_flags_finish */