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
, bool update_original
)
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
, update_original
);
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
, update_original
);
149 /* Mark edge E as inlined and update callgraph accordingly.
150 UPDATE_ORIGINAL specify whether profile of original function should be
154 cgraph_mark_inline_edge (struct cgraph_edge
*e
, bool update_original
)
156 int old_insns
= 0, new_insns
= 0;
157 struct cgraph_node
*to
= NULL
, *what
;
159 gcc_assert (e
->inline_failed
);
160 e
->inline_failed
= NULL
;
162 if (!e
->callee
->global
.inlined
&& flag_unit_at_a_time
)
163 DECL_POSSIBLY_INLINED (e
->callee
->decl
) = true;
164 e
->callee
->global
.inlined
= true;
166 cgraph_clone_inlined_nodes (e
, true, update_original
);
170 /* Now update size of caller and all functions caller is inlined into. */
171 for (;e
&& !e
->inline_failed
; e
= e
->caller
->callers
)
173 old_insns
= e
->caller
->global
.insns
;
174 new_insns
= cgraph_estimate_size_after_inlining (1, e
->caller
,
176 gcc_assert (new_insns
>= 0);
178 to
->global
.insns
= new_insns
;
180 gcc_assert (what
->global
.inlined_to
== to
);
181 if (new_insns
> old_insns
)
182 overall_insns
+= new_insns
- old_insns
;
186 /* Mark all calls of EDGE->CALLEE inlined into EDGE->CALLER.
187 Return following unredirected edge in the list of callers
190 static struct cgraph_edge
*
191 cgraph_mark_inline (struct cgraph_edge
*edge
)
193 struct cgraph_node
*to
= edge
->caller
;
194 struct cgraph_node
*what
= edge
->callee
;
195 struct cgraph_edge
*e
, *next
;
198 /* Look for all calls, mark them inline and clone recursively
199 all inlined functions. */
200 for (e
= what
->callers
; e
; e
= next
)
202 next
= e
->next_caller
;
203 if (e
->caller
== to
&& e
->inline_failed
)
205 cgraph_mark_inline_edge (e
, true);
215 /* Estimate the growth caused by inlining NODE into all callees. */
218 cgraph_estimate_growth (struct cgraph_node
*node
)
221 struct cgraph_edge
*e
;
222 if (node
->global
.estimated_growth
!= INT_MIN
)
223 return node
->global
.estimated_growth
;
225 for (e
= node
->callers
; e
; e
= e
->next_caller
)
226 if (e
->inline_failed
)
227 growth
+= (cgraph_estimate_size_after_inlining (1, e
->caller
, node
)
228 - e
->caller
->global
.insns
);
230 /* ??? Wrong for self recursive functions or cases where we decide to not
231 inline for different reasons, but it is not big deal as in that case
232 we will keep the body around, but we will also avoid some inlining. */
233 if (!node
->needed
&& !DECL_EXTERNAL (node
->decl
))
234 growth
-= node
->global
.insns
;
236 node
->global
.estimated_growth
= growth
;
240 /* Return false when inlining WHAT into TO is not good idea
241 as it would cause too large growth of function bodies. */
244 cgraph_check_inline_limits (struct cgraph_node
*to
, struct cgraph_node
*what
,
248 struct cgraph_edge
*e
;
252 if (to
->global
.inlined_to
)
253 to
= to
->global
.inlined_to
;
255 for (e
= to
->callees
; e
; e
= e
->next_callee
)
256 if (e
->callee
== what
)
259 /* When inlining large function body called once into small function,
260 take the inlined function as base for limiting the growth. */
261 if (to
->local
.self_insns
> what
->local
.self_insns
)
262 limit
= to
->local
.self_insns
;
264 limit
= what
->local
.self_insns
;
266 limit
+= limit
* PARAM_VALUE (PARAM_LARGE_FUNCTION_GROWTH
) / 100;
268 newsize
= cgraph_estimate_size_after_inlining (times
, to
, what
);
269 if (newsize
> PARAM_VALUE (PARAM_LARGE_FUNCTION_INSNS
)
273 *reason
= N_("--param large-function-growth limit reached");
279 /* Return true when function N is small enough to be inlined. */
282 cgraph_default_inline_p (struct cgraph_node
*n
, const char **reason
)
284 if (!DECL_INLINE (n
->decl
))
287 *reason
= N_("function not inlinable");
291 if (!DECL_SAVED_TREE (n
->decl
))
294 *reason
= N_("function body not available");
298 if (DECL_DECLARED_INLINE_P (n
->decl
))
300 if (n
->global
.insns
>= MAX_INLINE_INSNS_SINGLE
)
303 *reason
= N_("--param max-inline-insns-single limit reached");
309 if (n
->global
.insns
>= MAX_INLINE_INSNS_AUTO
)
312 *reason
= N_("--param max-inline-insns-auto limit reached");
320 /* Return true when inlining WHAT would create recursive inlining.
321 We call recursive inlining all cases where same function appears more than
322 once in the single recursion nest path in the inline graph. */
325 cgraph_recursive_inlining_p (struct cgraph_node
*to
,
326 struct cgraph_node
*what
,
330 if (to
->global
.inlined_to
)
331 recursive
= what
->decl
== to
->global
.inlined_to
->decl
;
333 recursive
= what
->decl
== to
->decl
;
334 /* Marking recursive function inline has sane semantic and thus we should
336 if (recursive
&& reason
)
337 *reason
= (what
->local
.disregard_inline_limits
338 ? N_("recursive inlining") : "");
342 /* Return true if the call can be hot. */
344 cgraph_maybe_hot_edge_p (struct cgraph_edge
*edge
)
346 if (profile_info
&& flag_branch_probabilities
348 <= profile_info
->sum_max
/ PARAM_VALUE (HOT_BB_COUNT_FRACTION
)))
353 /* A cost model driving the inlining heuristics in a way so the edges with
354 smallest badness are inlined first. After each inlining is performed
355 the costs of all caller edges of nodes affected are recomputed so the
356 metrics may accurately depend on values such as number of inlinable callers
357 of the function or function body size.
359 With profiling we use number of executions of each edge to drive the cost.
360 We also should distinguish hot and cold calls where the cold calls are
361 inlined into only when code size is overall improved.
365 cgraph_edge_badness (struct cgraph_edge
*edge
)
370 cgraph_estimate_size_after_inlining (1, edge
->caller
, edge
->callee
);
371 growth
-= edge
->caller
->global
.insns
;
373 /* Always prefer inlining saving code size. */
375 return INT_MIN
- growth
;
376 return ((int)((double)edge
->count
* INT_MIN
/ max_count
)) / growth
;
380 int nest
= MIN (edge
->loop_nest
, 8);
381 int badness
= cgraph_estimate_growth (edge
->callee
) * 256;
383 /* Decrease badness if call is nested. */
389 /* Make recursive inlining happen always after other inlining is done. */
390 if (cgraph_recursive_inlining_p (edge
->caller
, edge
->callee
, NULL
))
397 /* Recompute heap nodes for each of caller edge. */
400 update_caller_keys (fibheap_t heap
, struct cgraph_node
*node
,
401 bitmap updated_nodes
)
403 struct cgraph_edge
*edge
;
405 if (!node
->local
.inlinable
|| node
->local
.disregard_inline_limits
406 || node
->global
.inlined_to
)
408 if (bitmap_bit_p (updated_nodes
, node
->uid
))
410 bitmap_set_bit (updated_nodes
, node
->uid
);
411 node
->global
.estimated_growth
= INT_MIN
;
413 for (edge
= node
->callers
; edge
; edge
= edge
->next_caller
)
414 if (edge
->inline_failed
)
416 int badness
= cgraph_edge_badness (edge
);
419 fibnode_t n
= edge
->aux
;
420 gcc_assert (n
->data
== edge
);
421 if (n
->key
== badness
)
424 /* fibheap_replace_key only increase the keys. */
425 if (fibheap_replace_key (heap
, n
, badness
))
427 fibheap_delete_node (heap
, edge
->aux
);
429 edge
->aux
= fibheap_insert (heap
, badness
, edge
);
433 /* Recompute heap nodes for each of caller edges of each of callees. */
436 update_callee_keys (fibheap_t heap
, struct cgraph_node
*node
,
437 bitmap updated_nodes
)
439 struct cgraph_edge
*e
;
440 node
->global
.estimated_growth
= INT_MIN
;
442 for (e
= node
->callees
; e
; e
= e
->next_callee
)
443 if (e
->inline_failed
)
444 update_caller_keys (heap
, e
->callee
, updated_nodes
);
445 else if (!e
->inline_failed
)
446 update_callee_keys (heap
, e
->callee
, updated_nodes
);
449 /* Enqueue all recursive calls from NODE into priority queue depending on
450 how likely we want to recursively inline the call. */
453 lookup_recursive_calls (struct cgraph_node
*node
, struct cgraph_node
*where
,
457 struct cgraph_edge
*e
;
458 for (e
= where
->callees
; e
; e
= e
->next_callee
)
459 if (e
->callee
== node
)
461 /* When profile feedback is available, prioritize by expected number
462 of calls. Without profile feedback we maintain simple queue
463 to order candidates via recursive depths. */
464 fibheap_insert (heap
,
465 !max_count
? priority
++
466 : -(e
->count
/ ((max_count
+ (1<<24) - 1) / (1<<24))),
469 for (e
= where
->callees
; e
; e
= e
->next_callee
)
470 if (!e
->inline_failed
)
471 lookup_recursive_calls (node
, e
->callee
, heap
);
474 /* Find callgraph nodes closing a circle in the graph. The
475 resulting hashtab can be used to avoid walking the circles.
476 Uses the cgraph nodes ->aux field which needs to be zero
477 before and will be zero after operation. */
480 cgraph_find_cycles (struct cgraph_node
*node
, htab_t cycles
)
482 struct cgraph_edge
*e
;
487 slot
= htab_find_slot (cycles
, node
, INSERT
);
491 fprintf (dump_file
, "Cycle contains %s\n", cgraph_node_name (node
));
498 for (e
= node
->callees
; e
; e
= e
->next_callee
)
499 cgraph_find_cycles (e
->callee
, cycles
);
503 /* Leafify the cgraph node. We have to be careful in recursing
504 as to not run endlessly in circles of the callgraph.
505 We do so by using a hashtab of cycle entering nodes as generated
506 by cgraph_find_cycles. */
509 cgraph_flatten_node (struct cgraph_node
*node
, htab_t cycles
)
511 struct cgraph_edge
*e
;
513 for (e
= node
->callees
; e
; e
= e
->next_callee
)
515 /* Inline call, if possible, and recurse. Be sure we are not
516 entering callgraph circles here. */
518 && e
->callee
->local
.inlinable
519 && !cgraph_recursive_inlining_p (node
, e
->callee
,
521 && !htab_find (cycles
, e
->callee
))
524 fprintf (dump_file
, " inlining %s", cgraph_node_name (e
->callee
));
525 cgraph_mark_inline_edge (e
, true);
526 cgraph_flatten_node (e
->callee
, cycles
);
529 fprintf (dump_file
, " !inlining %s", cgraph_node_name (e
->callee
));
533 /* Decide on recursive inlining: in the case function has recursive calls,
534 inline until body size reaches given argument. */
537 cgraph_decide_recursive_inlining (struct cgraph_node
*node
)
539 int limit
= PARAM_VALUE (PARAM_MAX_INLINE_INSNS_RECURSIVE_AUTO
);
540 int max_depth
= PARAM_VALUE (PARAM_MAX_INLINE_RECURSIVE_DEPTH_AUTO
);
541 int probability
= PARAM_VALUE (PARAM_MIN_INLINE_RECURSIVE_PROBABILITY
);
543 struct cgraph_edge
*e
;
544 struct cgraph_node
*master_clone
;
548 if (DECL_DECLARED_INLINE_P (node
->decl
))
550 limit
= PARAM_VALUE (PARAM_MAX_INLINE_INSNS_RECURSIVE
);
551 max_depth
= PARAM_VALUE (PARAM_MAX_INLINE_RECURSIVE_DEPTH
);
554 /* Make sure that function is small enough to be considered for inlining. */
556 || cgraph_estimate_size_after_inlining (1, node
, node
) >= limit
)
558 heap
= fibheap_new ();
559 lookup_recursive_calls (node
, node
, heap
);
560 if (fibheap_empty (heap
))
562 fibheap_delete (heap
);
568 " Performing recursive inlining on %s\n",
569 cgraph_node_name (node
));
571 /* We need original clone to copy around. */
572 master_clone
= cgraph_clone_node (node
, node
->count
, 1, false);
573 master_clone
->needed
= true;
574 for (e
= master_clone
->callees
; e
; e
= e
->next_callee
)
575 if (!e
->inline_failed
)
576 cgraph_clone_inlined_nodes (e
, true, false);
578 /* Do the inlining and update list of recursive call during process. */
579 while (!fibheap_empty (heap
)
580 && (cgraph_estimate_size_after_inlining (1, node
, master_clone
)
583 struct cgraph_edge
*curr
= fibheap_extract_min (heap
);
584 struct cgraph_node
*cnode
;
587 for (cnode
= curr
->caller
;
588 cnode
->global
.inlined_to
; cnode
= cnode
->callers
->caller
)
589 if (node
->decl
== curr
->callee
->decl
)
591 if (depth
> max_depth
)
595 " maxmal depth reached\n");
601 if (!cgraph_maybe_hot_edge_p (curr
))
604 fprintf (dump_file
, " Not inlining cold call\n");
607 if (curr
->count
* 100 / node
->count
< probability
)
611 " Probability of edge is too small\n");
619 " Inlining call of depth %i", depth
);
622 fprintf (dump_file
, " called approx. %.2f times per call",
623 (double)curr
->count
/ node
->count
);
625 fprintf (dump_file
, "\n");
627 cgraph_redirect_edge_callee (curr
, master_clone
);
628 cgraph_mark_inline_edge (curr
, false);
629 lookup_recursive_calls (node
, curr
->callee
, heap
);
632 if (!fibheap_empty (heap
) && dump_file
)
633 fprintf (dump_file
, " Recursive inlining growth limit met.\n");
635 fibheap_delete (heap
);
638 "\n Inlined %i times, body grown from %i to %i insns\n", n
,
639 master_clone
->global
.insns
, node
->global
.insns
);
641 /* Remove master clone we used for inlining. We rely that clones inlined
642 into master clone gets queued just before master clone so we don't
644 for (node
= cgraph_nodes
; node
!= master_clone
;
646 if (node
->global
.inlined_to
== master_clone
)
647 cgraph_remove_node (node
);
648 cgraph_remove_node (master_clone
);
649 /* FIXME: Recursive inlining actually reduces number of calls of the
650 function. At this place we should probably walk the function and
651 inline clones and compensate the counts accordingly. This probably
652 doesn't matter much in practice. */
656 /* Set inline_failed for all callers of given function to REASON. */
659 cgraph_set_inline_failed (struct cgraph_node
*node
, const char *reason
)
661 struct cgraph_edge
*e
;
664 fprintf (dump_file
, "Inlining failed: %s\n", reason
);
665 for (e
= node
->callers
; e
; e
= e
->next_caller
)
666 if (e
->inline_failed
)
667 e
->inline_failed
= reason
;
670 /* We use greedy algorithm for inlining of small functions:
671 All inline candidates are put into prioritized heap based on estimated
672 growth of the overall number of instructions and then update the estimates.
674 INLINED and INLINED_CALEES are just pointers to arrays large enough
675 to be passed to cgraph_inlined_into and cgraph_inlined_callees. */
678 cgraph_decide_inlining_of_small_functions (void)
680 struct cgraph_node
*node
;
681 struct cgraph_edge
*edge
;
682 const char *failed_reason
;
683 fibheap_t heap
= fibheap_new ();
684 bitmap updated_nodes
= BITMAP_ALLOC (NULL
);
687 fprintf (dump_file
, "\nDeciding on smaller functions:\n");
689 /* Put all inline candidates into the heap. */
691 for (node
= cgraph_nodes
; node
; node
= node
->next
)
693 if (!node
->local
.inlinable
|| !node
->callers
694 || node
->local
.disregard_inline_limits
)
697 fprintf (dump_file
, "Considering inline candidate %s.\n", cgraph_node_name (node
));
699 node
->global
.estimated_growth
= INT_MIN
;
700 if (!cgraph_default_inline_p (node
, &failed_reason
))
702 cgraph_set_inline_failed (node
, failed_reason
);
706 for (edge
= node
->callers
; edge
; edge
= edge
->next_caller
)
707 if (edge
->inline_failed
)
709 gcc_assert (!edge
->aux
);
710 edge
->aux
= fibheap_insert (heap
, cgraph_edge_badness (edge
), edge
);
713 while (overall_insns
<= max_insns
&& (edge
= fibheap_extract_min (heap
)))
715 int old_insns
= overall_insns
;
716 struct cgraph_node
*where
;
718 cgraph_estimate_size_after_inlining (1, edge
->caller
, edge
->callee
);
720 growth
-= edge
->caller
->global
.insns
;
725 "\nConsidering %s with %i insns\n",
726 cgraph_node_name (edge
->callee
),
727 edge
->callee
->global
.insns
);
729 " to be inlined into %s\n"
730 " Estimated growth after inlined into all callees is %+i insns.\n"
731 " Estimated badness is %i.\n",
732 cgraph_node_name (edge
->caller
),
733 cgraph_estimate_growth (edge
->callee
),
734 cgraph_edge_badness (edge
));
736 fprintf (dump_file
," Called "HOST_WIDEST_INT_PRINT_DEC
"x\n", edge
->count
);
738 gcc_assert (edge
->aux
);
740 if (!edge
->inline_failed
)
743 /* When not having profile info ready we don't weight by any way the
744 position of call in procedure itself. This means if call of
745 function A from function B seems profitable to inline, the recursive
746 call of function A in inline copy of A in B will look profitable too
747 and we end up inlining until reaching maximal function growth. This
748 is not good idea so prohibit the recursive inlining.
750 ??? When the frequencies are taken into account we might not need this
754 where
= edge
->caller
;
755 while (where
->global
.inlined_to
)
757 if (where
->decl
== edge
->callee
->decl
)
759 where
= where
->callers
->caller
;
761 if (where
->global
.inlined_to
)
764 = (edge
->callee
->local
.disregard_inline_limits
? N_("recursive inlining") : "");
766 fprintf (dump_file
, " inline_failed:Recursive inlining performed only for function itself.\n");
771 if (!cgraph_maybe_hot_edge_p (edge
) && growth
> 0)
773 if (!cgraph_recursive_inlining_p (edge
->caller
, edge
->callee
,
774 &edge
->inline_failed
))
776 edge
->inline_failed
=
777 N_("call is unlikely");
779 fprintf (dump_file
, " inline_failed:%s.\n", edge
->inline_failed
);
783 if (!cgraph_default_inline_p (edge
->callee
, &edge
->inline_failed
))
785 if (!cgraph_recursive_inlining_p (edge
->caller
, edge
->callee
,
786 &edge
->inline_failed
))
789 fprintf (dump_file
, " inline_failed:%s.\n", edge
->inline_failed
);
793 if (cgraph_recursive_inlining_p (edge
->caller
, edge
->callee
,
794 &edge
->inline_failed
))
796 where
= edge
->caller
;
797 if (where
->global
.inlined_to
)
798 where
= where
->global
.inlined_to
;
799 if (!cgraph_decide_recursive_inlining (where
))
801 update_callee_keys (heap
, where
, updated_nodes
);
805 struct cgraph_node
*callee
;
806 if (!cgraph_check_inline_limits (edge
->caller
, edge
->callee
,
807 &edge
->inline_failed
))
810 fprintf (dump_file
, " Not inlining into %s:%s.\n",
811 cgraph_node_name (edge
->caller
), edge
->inline_failed
);
814 callee
= edge
->callee
;
815 cgraph_mark_inline_edge (edge
, true);
816 update_callee_keys (heap
, callee
, updated_nodes
);
818 where
= edge
->caller
;
819 if (where
->global
.inlined_to
)
820 where
= where
->global
.inlined_to
;
822 /* Our profitability metric can depend on local properties
823 such as number of inlinable calls and size of the function body.
824 After inlining these properties might change for the function we
825 inlined into (since it's body size changed) and for the functions
826 called by function we inlined (since number of it inlinable callers
828 update_caller_keys (heap
, where
, updated_nodes
);
829 bitmap_clear (updated_nodes
);
834 " Inlined into %s which now has %i insns,"
835 "net change of %+i insns.\n",
836 cgraph_node_name (edge
->caller
),
837 edge
->caller
->global
.insns
,
838 overall_insns
- old_insns
);
841 while ((edge
= fibheap_extract_min (heap
)) != NULL
)
843 gcc_assert (edge
->aux
);
845 if (!edge
->callee
->local
.disregard_inline_limits
&& edge
->inline_failed
846 && !cgraph_recursive_inlining_p (edge
->caller
, edge
->callee
,
847 &edge
->inline_failed
))
848 edge
->inline_failed
= N_("--param inline-unit-growth limit reached");
850 fibheap_delete (heap
);
851 BITMAP_FREE (updated_nodes
);
854 /* Decide on the inlining. We do so in the topological order to avoid
855 expenses on updating data structures. */
858 cgraph_decide_inlining (void)
860 struct cgraph_node
*node
;
862 struct cgraph_node
**order
=
863 xcalloc (cgraph_n_nodes
, sizeof (struct cgraph_node
*));
867 timevar_push (TV_INLINE_HEURISTICS
);
869 for (node
= cgraph_nodes
; node
; node
= node
->next
)
871 struct cgraph_edge
*e
;
872 initial_insns
+= node
->local
.self_insns
;
873 for (e
= node
->callees
; e
; e
= e
->next_callee
)
874 if (max_count
< e
->count
)
875 max_count
= e
->count
;
877 overall_insns
= initial_insns
;
878 gcc_assert (!max_count
|| (profile_info
&& flag_branch_probabilities
));
880 max_insns
= ((HOST_WIDEST_INT
) overall_insns
881 * (100 + PARAM_VALUE (PARAM_INLINE_UNIT_GROWTH
)) / 100);
883 nnodes
= cgraph_postorder (order
);
887 "\nDeciding on inlining. Starting with %i insns.\n",
890 for (node
= cgraph_nodes
; node
; node
= node
->next
)
894 fprintf (dump_file
, "\nInlining always_inline functions:\n");
896 /* In the first pass mark all always_inline edges. Do this with a priority
897 so none of our later choices will make this impossible. */
898 for (i
= nnodes
- 1; i
>= 0; i
--)
900 struct cgraph_edge
*e
, *next
;
904 /* Handle nodes to be flattened, but don't update overall unit size. */
905 if (lookup_attribute ("flatten", DECL_ATTRIBUTES (node
->decl
)) != NULL
)
907 int old_overall_insns
= overall_insns
;
911 "Leafifying %s\n", cgraph_node_name (node
));
912 cycles
= htab_create (7, htab_hash_pointer
, htab_eq_pointer
, NULL
);
913 cgraph_find_cycles (node
, cycles
);
914 cgraph_flatten_node (node
, cycles
);
915 htab_delete (cycles
);
916 overall_insns
= old_overall_insns
;
917 /* We don't need to consider always_inline functions inside the flattened
922 if (!node
->local
.disregard_inline_limits
)
926 "\nConsidering %s %i insns (always inline)\n",
927 cgraph_node_name (node
), node
->global
.insns
);
928 old_insns
= overall_insns
;
929 for (e
= node
->callers
; e
; e
= next
)
931 next
= e
->next_caller
;
932 if (!e
->inline_failed
)
934 if (cgraph_recursive_inlining_p (e
->caller
, e
->callee
,
937 cgraph_mark_inline_edge (e
, true);
940 " Inlined into %s which now has %i insns.\n",
941 cgraph_node_name (e
->caller
),
942 e
->caller
->global
.insns
);
946 " Inlined for a net change of %+i insns.\n",
947 overall_insns
- old_insns
);
950 if (!flag_really_no_inline
)
951 cgraph_decide_inlining_of_small_functions ();
953 if (!flag_really_no_inline
954 && flag_inline_functions_called_once
)
957 fprintf (dump_file
, "\nDeciding on functions called once:\n");
959 /* And finally decide what functions are called once. */
961 for (i
= nnodes
- 1; i
>= 0; i
--)
965 if (node
->callers
&& !node
->callers
->next_caller
&& !node
->needed
966 && node
->local
.inlinable
&& node
->callers
->inline_failed
967 && !DECL_EXTERNAL (node
->decl
) && !DECL_COMDAT (node
->decl
))
970 struct cgraph_node
*node1
;
972 /* Verify that we won't duplicate the caller. */
973 for (node1
= node
->callers
->caller
;
974 node1
->callers
&& !node1
->callers
->inline_failed
975 && ok
; node1
= node1
->callers
->caller
)
976 if (node1
->callers
->next_caller
|| node1
->needed
)
983 "\nConsidering %s %i insns.\n",
984 cgraph_node_name (node
), node
->global
.insns
);
986 " Called once from %s %i insns.\n",
987 cgraph_node_name (node
->callers
->caller
),
988 node
->callers
->caller
->global
.insns
);
991 old_insns
= overall_insns
;
993 if (cgraph_check_inline_limits (node
->callers
->caller
, node
,
996 cgraph_mark_inline (node
->callers
);
999 " Inlined into %s which now has %i insns"
1000 " for a net change of %+i insns.\n",
1001 cgraph_node_name (node
->callers
->caller
),
1002 node
->callers
->caller
->global
.insns
,
1003 overall_insns
- old_insns
);
1009 " Inline limit reached, not inlined.\n");
1018 "\nInlined %i calls, eliminated %i functions, "
1019 "%i insns turned to %i insns.\n\n",
1020 ncalls_inlined
, nfunctions_inlined
, initial_insns
,
1023 timevar_pop (TV_INLINE_HEURISTICS
);
1026 /* Decide on the inlining. We do so in the topological order to avoid
1027 expenses on updating data structures. */
1030 cgraph_decide_inlining_incrementally (struct cgraph_node
*node
, bool early
)
1032 struct cgraph_edge
*e
;
1033 bool inlined
= false;
1034 const char *failed_reason
;
1036 /* First of all look for always inline functions. */
1037 for (e
= node
->callees
; e
; e
= e
->next_callee
)
1038 if (e
->callee
->local
.disregard_inline_limits
1040 && !cgraph_recursive_inlining_p (node
, e
->callee
, &e
->inline_failed
)
1041 /* ??? It is possible that renaming variable removed the function body
1042 in duplicate_decls. See gcc.c-torture/compile/20011119-2.c */
1043 && DECL_SAVED_TREE (e
->callee
->decl
))
1045 if (dump_file
&& early
)
1047 fprintf (dump_file
, " Early inlining %s",
1048 cgraph_node_name (e
->callee
));
1049 fprintf (dump_file
, " into %s\n", cgraph_node_name (node
));
1051 cgraph_mark_inline (e
);
1055 /* Now do the automatic inlining. */
1056 if (!flag_really_no_inline
)
1057 for (e
= node
->callees
; e
; e
= e
->next_callee
)
1058 if (e
->callee
->local
.inlinable
1060 && !e
->callee
->local
.disregard_inline_limits
1061 && !cgraph_recursive_inlining_p (node
, e
->callee
, &e
->inline_failed
)
1063 || (cgraph_estimate_size_after_inlining (1, e
->caller
, node
)
1064 <= e
->caller
->global
.insns
))
1065 && cgraph_check_inline_limits (node
, e
->callee
, &e
->inline_failed
)
1066 && DECL_SAVED_TREE (e
->callee
->decl
))
1068 if (cgraph_default_inline_p (e
->callee
, &failed_reason
))
1070 if (dump_file
&& early
)
1072 fprintf (dump_file
, " Early inlining %s",
1073 cgraph_node_name (e
->callee
));
1074 fprintf (dump_file
, " into %s\n", cgraph_node_name (node
));
1076 cgraph_mark_inline (e
);
1080 e
->inline_failed
= failed_reason
;
1082 if (early
&& inlined
)
1084 push_cfun (DECL_STRUCT_FUNCTION (node
->decl
));
1085 tree_register_cfg_hooks ();
1086 current_function_decl
= node
->decl
;
1087 optimize_inline_calls (current_function_decl
);
1088 node
->local
.self_insns
= node
->global
.insns
;
1089 current_function_decl
= NULL
;
1095 /* When inlining shall be performed. */
1097 cgraph_gate_inlining (void)
1099 return flag_inline_trees
;
1102 struct tree_opt_pass pass_ipa_inline
=
1104 "inline", /* name */
1105 cgraph_gate_inlining
, /* gate */
1106 cgraph_decide_inlining
, /* execute */
1109 0, /* static_pass_number */
1110 TV_INTEGRATION
, /* tv_id */
1111 0, /* properties_required */
1112 PROP_cfg
, /* properties_provided */
1113 0, /* properties_destroyed */
1114 0, /* todo_flags_start */
1115 TODO_dump_cgraph
| TODO_dump_func
, /* todo_flags_finish */
1119 /* Do inlining of small functions. Doing so early helps profiling and other
1120 passes to be somewhat more effective and avoids some code duplication in
1121 later real inlining pass for testcases with very many function calls. */
1123 cgraph_early_inlining (void)
1125 struct cgraph_node
*node
;
1127 struct cgraph_node
**order
=
1128 xcalloc (cgraph_n_nodes
, sizeof (struct cgraph_node
*));
1131 if (sorrycount
|| errorcount
)
1133 #ifdef ENABLE_CHECKING
1134 for (node
= cgraph_nodes
; node
; node
= node
->next
)
1135 gcc_assert (!node
->aux
);
1138 nnodes
= cgraph_postorder (order
);
1139 for (i
= nnodes
- 1; i
>= 0; i
--)
1142 if (node
->analyzed
&& node
->local
.inlinable
1143 && (node
->needed
|| node
->reachable
)
1145 cgraph_decide_inlining_incrementally (node
, true);
1147 cgraph_remove_unreachable_nodes (true, dump_file
);
1148 #ifdef ENABLE_CHECKING
1149 for (node
= cgraph_nodes
; node
; node
= node
->next
)
1150 gcc_assert (!node
->global
.inlined_to
);
1155 /* When inlining shall be performed. */
1157 cgraph_gate_early_inlining (void)
1159 return flag_inline_trees
&& flag_early_inlining
;
1162 struct tree_opt_pass pass_early_ipa_inline
=
1164 "einline", /* name */
1165 cgraph_gate_early_inlining
, /* gate */
1166 cgraph_early_inlining
, /* execute */
1169 0, /* static_pass_number */
1170 TV_INTEGRATION
, /* tv_id */
1171 0, /* properties_required */
1172 PROP_cfg
, /* properties_provided */
1173 0, /* properties_destroyed */
1174 0, /* todo_flags_start */
1175 TODO_dump_cgraph
| TODO_dump_func
, /* todo_flags_finish */