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"
84 /* Statistics we collect about inlining algorithm. */
85 static int ncalls_inlined
;
86 static int nfunctions_inlined
;
87 static int initial_insns
;
88 static int overall_insns
;
90 static gcov_type max_count
;
92 /* Estimate size of the function after inlining WHAT into TO. */
95 cgraph_estimate_size_after_inlining (int times
, struct cgraph_node
*to
,
96 struct cgraph_node
*what
)
99 tree fndecl
= what
->decl
, arg
;
100 int call_insns
= PARAM_VALUE (PARAM_INLINE_CALL_COST
);
102 for (arg
= DECL_ARGUMENTS (fndecl
); arg
; arg
= TREE_CHAIN (arg
))
103 call_insns
+= estimate_move_cost (TREE_TYPE (arg
));
104 size
= (what
->global
.insns
- call_insns
) * times
+ to
->global
.insns
;
105 gcc_assert (size
>= 0);
109 /* E is expected to be an edge being inlined. Clone destination node of
110 the edge and redirect it to the new clone.
111 DUPLICATE is used for bookkeeping on whether we are actually creating new
112 clones or re-using node originally representing out-of-line function call.
115 cgraph_clone_inlined_nodes (struct cgraph_edge
*e
, bool duplicate
)
117 struct cgraph_node
*n
;
119 /* We may eliminate the need for out-of-line copy to be output. In that
120 case just go ahead and re-use it. */
121 if (!e
->callee
->callers
->next_caller
122 && (!e
->callee
->needed
|| DECL_EXTERNAL (e
->callee
->decl
))
124 && (flag_unit_at_a_time
&& cgraph_global_info_ready
))
126 gcc_assert (!e
->callee
->global
.inlined_to
);
127 if (!DECL_EXTERNAL (e
->callee
->decl
))
128 overall_insns
-= e
->callee
->global
.insns
, nfunctions_inlined
++;
133 n
= cgraph_clone_node (e
->callee
, e
->count
, e
->loop_nest
);
134 cgraph_redirect_edge_callee (e
, n
);
137 if (e
->caller
->global
.inlined_to
)
138 e
->callee
->global
.inlined_to
= e
->caller
->global
.inlined_to
;
140 e
->callee
->global
.inlined_to
= e
->caller
;
142 /* Recursively clone all bodies. */
143 for (e
= e
->callee
->callees
; e
; e
= e
->next_callee
)
144 if (!e
->inline_failed
)
145 cgraph_clone_inlined_nodes (e
, duplicate
);
148 /* Mark edge E as inlined and update callgraph accordingly. */
151 cgraph_mark_inline_edge (struct cgraph_edge
*e
)
153 int old_insns
= 0, new_insns
= 0;
154 struct cgraph_node
*to
= NULL
, *what
;
156 gcc_assert (e
->inline_failed
);
157 e
->inline_failed
= NULL
;
159 if (!e
->callee
->global
.inlined
&& flag_unit_at_a_time
)
160 DECL_POSSIBLY_INLINED (e
->callee
->decl
) = true;
161 e
->callee
->global
.inlined
= true;
163 cgraph_clone_inlined_nodes (e
, true);
167 /* Now update size of caller and all functions caller is inlined into. */
168 for (;e
&& !e
->inline_failed
; e
= e
->caller
->callers
)
170 old_insns
= e
->caller
->global
.insns
;
171 new_insns
= cgraph_estimate_size_after_inlining (1, e
->caller
,
173 gcc_assert (new_insns
>= 0);
175 to
->global
.insns
= new_insns
;
177 gcc_assert (what
->global
.inlined_to
== to
);
178 if (new_insns
> old_insns
)
179 overall_insns
+= new_insns
- old_insns
;
183 /* Mark all calls of EDGE->CALLEE inlined into EDGE->CALLER.
184 Return following unredirected edge in the list of callers
187 static struct cgraph_edge
*
188 cgraph_mark_inline (struct cgraph_edge
*edge
)
190 struct cgraph_node
*to
= edge
->caller
;
191 struct cgraph_node
*what
= edge
->callee
;
192 struct cgraph_edge
*e
, *next
;
195 /* Look for all calls, mark them inline and clone recursively
196 all inlined functions. */
197 for (e
= what
->callers
; e
; e
= next
)
199 next
= e
->next_caller
;
200 if (e
->caller
== to
&& e
->inline_failed
)
202 cgraph_mark_inline_edge (e
);
212 /* Estimate the growth caused by inlining NODE into all callees. */
215 cgraph_estimate_growth (struct cgraph_node
*node
)
218 struct cgraph_edge
*e
;
219 if (node
->global
.estimated_growth
!= INT_MIN
)
220 return node
->global
.estimated_growth
;
222 for (e
= node
->callers
; e
; e
= e
->next_caller
)
223 if (e
->inline_failed
)
224 growth
+= (cgraph_estimate_size_after_inlining (1, e
->caller
, node
)
225 - e
->caller
->global
.insns
);
227 /* ??? Wrong for self recursive functions or cases where we decide to not
228 inline for different reasons, but it is not big deal as in that case
229 we will keep the body around, but we will also avoid some inlining. */
230 if (!node
->needed
&& !DECL_EXTERNAL (node
->decl
))
231 growth
-= node
->global
.insns
;
233 node
->global
.estimated_growth
= growth
;
237 /* Return false when inlining WHAT into TO is not good idea
238 as it would cause too large growth of function bodies. */
241 cgraph_check_inline_limits (struct cgraph_node
*to
, struct cgraph_node
*what
,
245 struct cgraph_edge
*e
;
249 if (to
->global
.inlined_to
)
250 to
= to
->global
.inlined_to
;
252 for (e
= to
->callees
; e
; e
= e
->next_callee
)
253 if (e
->callee
== what
)
256 /* When inlining large function body called once into small function,
257 take the inlined function as base for limiting the growth. */
258 if (to
->local
.self_insns
> what
->local
.self_insns
)
259 limit
= to
->local
.self_insns
;
261 limit
= what
->local
.self_insns
;
263 limit
+= limit
* PARAM_VALUE (PARAM_LARGE_FUNCTION_GROWTH
) / 100;
265 newsize
= cgraph_estimate_size_after_inlining (times
, to
, what
);
266 if (newsize
> PARAM_VALUE (PARAM_LARGE_FUNCTION_INSNS
)
270 *reason
= N_("--param large-function-growth limit reached");
276 /* Return true when function N is small enough to be inlined. */
279 cgraph_default_inline_p (struct cgraph_node
*n
)
281 if (!DECL_INLINE (n
->decl
) || !DECL_SAVED_TREE (n
->decl
))
283 if (DECL_DECLARED_INLINE_P (n
->decl
))
284 return n
->global
.insns
< MAX_INLINE_INSNS_SINGLE
;
286 return n
->global
.insns
< MAX_INLINE_INSNS_AUTO
;
289 /* Return true when inlining WHAT would create recursive inlining.
290 We call recursive inlining all cases where same function appears more than
291 once in the single recursion nest path in the inline graph. */
294 cgraph_recursive_inlining_p (struct cgraph_node
*to
,
295 struct cgraph_node
*what
,
299 if (to
->global
.inlined_to
)
300 recursive
= what
->decl
== to
->global
.inlined_to
->decl
;
302 recursive
= what
->decl
== to
->decl
;
303 /* Marking recursive function inline has sane semantic and thus we should
305 if (recursive
&& reason
)
306 *reason
= (what
->local
.disregard_inline_limits
307 ? N_("recursive inlining") : "");
311 /* Return true if the call can be hot. */
313 cgraph_maybe_hot_edge_p (struct cgraph_edge
*edge
)
315 if (profile_info
&& flag_branch_probabilities
317 <= profile_info
->sum_max
/ PARAM_VALUE (HOT_BB_COUNT_FRACTION
)))
322 /* A cost model driving the inlining heuristics in a way so the edges with
323 smallest badness are inlined first. After each inlining is performed
324 the costs of all caller edges of nodes affected are recomputed so the
325 metrics may accurately depend on values such as number of inlinable callers
326 of the function or function body size.
328 For the moment we use estimated growth caused by inlining callee into all
329 it's callers for driving the inlining but once we have loop depth or
330 frequency information readily available we should do better.
332 With profiling we use number of executions of each edge to drive the cost.
333 We also should distinguish hot and cold calls where the cold calls are
334 inlined into only when code size is overall improved.
336 Value INT_MAX can be returned to prevent function from being inlined.
340 cgraph_edge_badness (struct cgraph_edge
*edge
)
345 cgraph_estimate_size_after_inlining (1, edge
->caller
, edge
->callee
);
346 growth
-= edge
->caller
->global
.insns
;
348 /* Always prefer inlining saving code size. */
350 return INT_MIN
- growth
;
351 return ((int)((double)edge
->count
* INT_MIN
/ max_count
)) / growth
;
355 int nest
= MIN (edge
->loop_nest
, 8);
356 int badness
= cgraph_estimate_growth (edge
->callee
) * 256;
360 /* Make recursive inlining happen always after other inlining is done. */
361 if (cgraph_recursive_inlining_p (edge
->caller
, edge
->callee
, NULL
))
368 /* Recompute heap nodes for each of caller edge. */
371 update_caller_keys (fibheap_t heap
, struct cgraph_node
*node
,
372 bitmap updated_nodes
)
374 struct cgraph_edge
*edge
;
376 if (!node
->local
.inlinable
|| node
->local
.disregard_inline_limits
377 || node
->global
.inlined_to
)
379 if (bitmap_bit_p (updated_nodes
, node
->uid
))
381 bitmap_set_bit (updated_nodes
, node
->uid
);
383 for (edge
= node
->callers
; edge
; edge
= edge
->next_caller
)
384 if (edge
->inline_failed
)
386 int badness
= cgraph_edge_badness (edge
);
389 fibnode_t n
= edge
->aux
;
390 gcc_assert (n
->data
== edge
);
391 if (n
->key
== badness
)
394 /* fibheap_replace_key only increase the keys. */
395 if (fibheap_replace_key (heap
, n
, badness
))
397 fibheap_delete_node (heap
, edge
->aux
);
399 edge
->aux
= fibheap_insert (heap
, badness
, edge
);
403 /* Recompute heap nodes for each of caller edges of each of callees. */
406 update_callee_keys (fibheap_t heap
, struct cgraph_node
*node
,
407 bitmap updated_nodes
)
409 struct cgraph_edge
*e
;
410 node
->global
.estimated_growth
= INT_MIN
;
412 for (e
= node
->callees
; e
; e
= e
->next_callee
)
413 if (e
->inline_failed
)
414 update_caller_keys (heap
, e
->callee
, updated_nodes
);
415 else if (!e
->inline_failed
)
416 update_callee_keys (heap
, e
->callee
, updated_nodes
);
419 /* Enqueue all recursive calls from NODE into priority queue depending on
420 how likely we want to recursively inline the call. */
423 lookup_recursive_calls (struct cgraph_node
*node
, struct cgraph_node
*where
,
427 struct cgraph_edge
*e
;
428 for (e
= where
->callees
; e
; e
= e
->next_callee
)
429 if (e
->callee
== node
)
431 /* FIXME: Once counts and frequencies are available we should drive the
432 order by these. For now force the order to be simple queue since
433 we get order dependent on recursion depth for free by this. */
434 fibheap_insert (heap
, priority
++, e
);
436 for (e
= where
->callees
; e
; e
= e
->next_callee
)
437 if (!e
->inline_failed
)
438 lookup_recursive_calls (node
, e
->callee
, heap
);
441 /* Decide on recursive inlining: in the case function has recursive calls,
442 inline until body size reaches given argument. */
445 cgraph_decide_recursive_inlining (struct cgraph_node
*node
)
447 int limit
= PARAM_VALUE (PARAM_MAX_INLINE_INSNS_RECURSIVE_AUTO
);
448 int max_depth
= PARAM_VALUE (PARAM_MAX_INLINE_RECURSIVE_DEPTH_AUTO
);
450 struct cgraph_edge
*e
;
451 struct cgraph_node
*master_clone
;
455 if (DECL_DECLARED_INLINE_P (node
->decl
))
457 limit
= PARAM_VALUE (PARAM_MAX_INLINE_INSNS_RECURSIVE
);
458 max_depth
= PARAM_VALUE (PARAM_MAX_INLINE_RECURSIVE_DEPTH
);
461 /* Make sure that function is small enough to be considered for inlining. */
463 || cgraph_estimate_size_after_inlining (1, node
, node
) >= limit
)
465 heap
= fibheap_new ();
466 lookup_recursive_calls (node
, node
, heap
);
467 if (fibheap_empty (heap
))
469 fibheap_delete (heap
);
475 " Performing recursive inlining on %s\n",
476 cgraph_node_name (node
));
478 /* We need original clone to copy around. */
479 master_clone
= cgraph_clone_node (node
, 0, 1);
480 master_clone
->needed
= true;
481 for (e
= master_clone
->callees
; e
; e
= e
->next_callee
)
482 if (!e
->inline_failed
)
483 cgraph_clone_inlined_nodes (e
, true);
485 /* Do the inlining and update list of recursive call during process. */
486 while (!fibheap_empty (heap
)
487 && cgraph_estimate_size_after_inlining (1, node
, master_clone
) <= limit
)
489 struct cgraph_edge
*curr
= fibheap_extract_min (heap
);
490 struct cgraph_node
*node
;
493 for (node
= curr
->caller
;
494 node
; node
= node
->global
.inlined_to
)
495 if (node
->decl
== curr
->callee
->decl
)
497 if (depth
> max_depth
)
502 " Inlining call of depth %i\n", depth
);
503 cgraph_redirect_edge_callee (curr
, master_clone
);
504 cgraph_mark_inline_edge (curr
);
505 lookup_recursive_calls (node
, curr
->callee
, heap
);
509 fibheap_delete (heap
);
512 "\n Inlined %i times, body grown from %i to %i insns\n", n
,
513 master_clone
->global
.insns
, node
->global
.insns
);
515 /* Remove master clone we used for inlining. We rely that clones inlined
516 into master clone gets queued just before master clone so we don't
518 for (node
= cgraph_nodes
; node
!= master_clone
;
520 if (node
->global
.inlined_to
== master_clone
)
521 cgraph_remove_node (node
);
522 cgraph_remove_node (master_clone
);
526 /* Set inline_failed for all callers of given function to REASON. */
529 cgraph_set_inline_failed (struct cgraph_node
*node
, const char *reason
)
531 struct cgraph_edge
*e
;
534 fprintf (dump_file
, "Inlining failed: %s\n", reason
);
535 for (e
= node
->callers
; e
; e
= e
->next_caller
)
536 if (e
->inline_failed
)
537 e
->inline_failed
= reason
;
540 /* We use greedy algorithm for inlining of small functions:
541 All inline candidates are put into prioritized heap based on estimated
542 growth of the overall number of instructions and then update the estimates.
544 INLINED and INLINED_CALEES are just pointers to arrays large enough
545 to be passed to cgraph_inlined_into and cgraph_inlined_callees. */
548 cgraph_decide_inlining_of_small_functions (void)
550 struct cgraph_node
*node
;
551 struct cgraph_edge
*edge
;
552 fibheap_t heap
= fibheap_new ();
553 bitmap updated_nodes
= BITMAP_ALLOC (NULL
);
556 fprintf (dump_file
, "\nDeciding on smaller functions:\n");
558 /* Put all inline candidates into the heap. */
560 for (node
= cgraph_nodes
; node
; node
= node
->next
)
562 if (!node
->local
.inlinable
|| !node
->callers
563 || node
->local
.disregard_inline_limits
)
566 fprintf (dump_file
, "Considering inline candidate %s.\n", cgraph_node_name (node
));
568 node
->global
.estimated_growth
= INT_MIN
;
569 if (!cgraph_default_inline_p (node
))
571 cgraph_set_inline_failed (node
,
572 N_("--param max-inline-insns-single limit reached"));
576 for (edge
= node
->callers
; edge
; edge
= edge
->next_caller
)
577 if (edge
->inline_failed
)
579 gcc_assert (!edge
->aux
);
580 edge
->aux
= fibheap_insert (heap
, cgraph_edge_badness (edge
), edge
);
583 while (overall_insns
<= max_insns
&& (edge
= fibheap_extract_min (heap
)))
585 int old_insns
= overall_insns
;
586 struct cgraph_node
*where
;
588 cgraph_estimate_size_after_inlining (1, edge
->caller
, edge
->callee
);
590 growth
-= edge
->caller
->global
.insns
;
595 "\nConsidering %s with %i insns to be inlined into %s\n"
596 " Estimated growth after inlined into all callees is %+i insns.\n"
597 " Estimated badness is %i.\n",
598 cgraph_node_name (edge
->callee
),
599 edge
->callee
->global
.insns
,
600 cgraph_node_name (edge
->caller
),
601 cgraph_estimate_growth (edge
->callee
),
602 cgraph_edge_badness (edge
));
604 fprintf (dump_file
," Called "HOST_WIDEST_INT_PRINT_DEC
"x\n", edge
->count
);
606 gcc_assert (edge
->aux
);
608 if (!edge
->inline_failed
)
611 /* When not having profile info ready we don't weight by any way the
612 position of call in procedure itself. This means if call of
613 function A from function B seems profitable to inline, the recursive
614 call of function A in inline copy of A in B will look profitable too
615 and we end up inlining until reaching maximal function growth. This
616 is not good idea so prohibit the recursive inlining.
618 ??? When the frequencies are taken into account we might not need this
622 where
= edge
->caller
;
623 while (where
->global
.inlined_to
)
625 if (where
->decl
== edge
->callee
->decl
)
627 where
= where
->callers
->caller
;
629 if (where
->global
.inlined_to
)
632 = (edge
->callee
->local
.disregard_inline_limits
? N_("recursive inlining") : "");
634 fprintf (dump_file
, " inline_failed:Recursive inlining performed only for function itself.\n");
639 if (!cgraph_maybe_hot_edge_p (edge
) && growth
> 0)
641 if (!cgraph_recursive_inlining_p (edge
->caller
, edge
->callee
,
642 &edge
->inline_failed
))
644 edge
->inline_failed
=
645 N_("call is unlikely");
647 fprintf (dump_file
, " inline_failed:%s.\n", edge
->inline_failed
);
651 if (!cgraph_default_inline_p (edge
->callee
))
653 if (!cgraph_recursive_inlining_p (edge
->caller
, edge
->callee
,
654 &edge
->inline_failed
))
656 edge
->inline_failed
=
657 N_("--param max-inline-insns-single limit reached after inlining into the callee");
659 fprintf (dump_file
, " inline_failed:%s.\n", edge
->inline_failed
);
663 if (cgraph_recursive_inlining_p (edge
->caller
, edge
->callee
,
664 &edge
->inline_failed
))
666 where
= edge
->caller
;
667 if (where
->global
.inlined_to
)
668 where
= where
->global
.inlined_to
;
669 if (!cgraph_decide_recursive_inlining (where
))
671 update_callee_keys (heap
, where
, updated_nodes
);
675 if (!cgraph_check_inline_limits (edge
->caller
, edge
->callee
,
676 &edge
->inline_failed
))
679 fprintf (dump_file
, " Not inlining into %s:%s.\n",
680 cgraph_node_name (edge
->caller
), edge
->inline_failed
);
683 cgraph_mark_inline_edge (edge
);
684 update_callee_keys (heap
, edge
->callee
, updated_nodes
);
686 where
= edge
->caller
;
687 if (where
->global
.inlined_to
)
688 where
= where
->global
.inlined_to
;
690 /* Our profitability metric can depend on local properties
691 such as number of inlinable calls and size of the function body.
692 After inlining these properties might change for the function we
693 inlined into (since it's body size changed) and for the functions
694 called by function we inlined (since number of it inlinable callers
696 update_caller_keys (heap
, where
, updated_nodes
);
697 bitmap_clear (updated_nodes
);
701 " Inlined into %s which now has %i insns.\n",
702 cgraph_node_name (edge
->caller
),
703 edge
->caller
->global
.insns
);
706 " Inlined for a net change of %+i insns.\n",
707 overall_insns
- old_insns
);
709 while ((edge
= fibheap_extract_min (heap
)) != NULL
)
711 gcc_assert (edge
->aux
);
713 if (!edge
->callee
->local
.disregard_inline_limits
&& edge
->inline_failed
714 && !cgraph_recursive_inlining_p (edge
->caller
, edge
->callee
,
715 &edge
->inline_failed
))
716 edge
->inline_failed
= N_("--param inline-unit-growth limit reached");
718 fibheap_delete (heap
);
719 BITMAP_FREE (updated_nodes
);
722 /* Decide on the inlining. We do so in the topological order to avoid
723 expenses on updating data structures. */
726 cgraph_decide_inlining (void)
728 struct cgraph_node
*node
;
730 struct cgraph_node
**order
=
731 xcalloc (cgraph_n_nodes
, sizeof (struct cgraph_node
*));
735 timevar_push (TV_INLINE_HEURISTICS
);
737 for (node
= cgraph_nodes
; node
; node
= node
->next
)
739 struct cgraph_edge
*e
;
740 initial_insns
+= node
->local
.self_insns
;
741 for (e
= node
->callees
; e
; e
= e
->next_callee
)
742 if (max_count
< e
->count
)
743 max_count
= e
->count
;
745 overall_insns
= initial_insns
;
746 gcc_assert (!max_count
|| (profile_info
&& flag_branch_probabilities
));
748 max_insns
= ((HOST_WIDEST_INT
) overall_insns
749 * (100 + PARAM_VALUE (PARAM_INLINE_UNIT_GROWTH
)) / 100);
751 nnodes
= cgraph_postorder (order
);
755 "\nDeciding on inlining. Starting with %i insns.\n",
758 for (node
= cgraph_nodes
; node
; node
= node
->next
)
762 fprintf (dump_file
, "\nInlining always_inline functions:\n");
764 /* In the first pass mark all always_inline edges. Do this with a priority
765 so none of our later choices will make this impossible. */
766 for (i
= nnodes
- 1; i
>= 0; i
--)
768 struct cgraph_edge
*e
, *next
;
772 if (!node
->local
.disregard_inline_limits
)
776 "\nConsidering %s %i insns (always inline)\n",
777 cgraph_node_name (node
), node
->global
.insns
);
778 old_insns
= overall_insns
;
779 for (e
= node
->callers
; e
; e
= next
)
781 next
= e
->next_caller
;
782 if (!e
->inline_failed
)
784 if (cgraph_recursive_inlining_p (e
->caller
, e
->callee
,
787 cgraph_mark_inline_edge (e
);
790 " Inlined into %s which now has %i insns.\n",
791 cgraph_node_name (e
->caller
),
792 e
->caller
->global
.insns
);
796 " Inlined for a net change of %+i insns.\n",
797 overall_insns
- old_insns
);
800 if (!flag_really_no_inline
)
802 cgraph_decide_inlining_of_small_functions ();
805 fprintf (dump_file
, "\nDeciding on functions called once:\n");
807 /* And finally decide what functions are called once. */
809 for (i
= nnodes
- 1; i
>= 0; i
--)
813 if (node
->callers
&& !node
->callers
->next_caller
&& !node
->needed
814 && node
->local
.inlinable
&& node
->callers
->inline_failed
815 && !DECL_EXTERNAL (node
->decl
) && !DECL_COMDAT (node
->decl
))
818 struct cgraph_node
*node1
;
820 /* Verify that we won't duplicate the caller. */
821 for (node1
= node
->callers
->caller
;
822 node1
->callers
&& !node1
->callers
->inline_failed
823 && ok
; node1
= node1
->callers
->caller
)
824 if (node1
->callers
->next_caller
|| node1
->needed
)
830 "\nConsidering %s %i insns.\n"
831 " Called once from %s %i insns.\n",
832 cgraph_node_name (node
), node
->global
.insns
,
833 cgraph_node_name (node
->callers
->caller
),
834 node
->callers
->caller
->global
.insns
);
836 old_insns
= overall_insns
;
838 if (cgraph_check_inline_limits (node
->callers
->caller
, node
,
841 cgraph_mark_inline (node
->callers
);
844 " Inlined into %s which now has %i insns"
845 " for a net change of %+i insns.\n",
846 cgraph_node_name (node
->callers
->caller
),
847 node
->callers
->caller
->global
.insns
,
848 overall_insns
- old_insns
);
854 " Inline limit reached, not inlined.\n");
863 "\nInlined %i calls, eliminated %i functions, "
864 "%i insns turned to %i insns.\n\n",
865 ncalls_inlined
, nfunctions_inlined
, initial_insns
,
868 timevar_pop (TV_INLINE_HEURISTICS
);
871 /* Decide on the inlining. We do so in the topological order to avoid
872 expenses on updating data structures. */
875 cgraph_decide_inlining_incrementally (struct cgraph_node
*node
, bool early
)
877 struct cgraph_edge
*e
;
878 bool inlined
= false;
880 /* First of all look for always inline functions. */
881 for (e
= node
->callees
; e
; e
= e
->next_callee
)
882 if (e
->callee
->local
.disregard_inline_limits
884 && !cgraph_recursive_inlining_p (node
, e
->callee
, &e
->inline_failed
)
885 /* ??? It is possible that renaming variable removed the function body
886 in duplicate_decls. See gcc.c-torture/compile/20011119-2.c */
887 && DECL_SAVED_TREE (e
->callee
->decl
))
889 if (dump_file
&& early
)
890 fprintf (dump_file
, " Early inlining %s into %s\n",
891 cgraph_node_name (e
->callee
), cgraph_node_name (node
));
892 cgraph_mark_inline (e
);
896 /* Now do the automatic inlining. */
897 if (!flag_really_no_inline
)
898 for (e
= node
->callees
; e
; e
= e
->next_callee
)
899 if (e
->callee
->local
.inlinable
901 && !e
->callee
->local
.disregard_inline_limits
902 && !cgraph_recursive_inlining_p (node
, e
->callee
, &e
->inline_failed
)
904 || (cgraph_estimate_size_after_inlining (1, e
->caller
, node
)
905 <= e
->caller
->global
.insns
))
906 && cgraph_check_inline_limits (node
, e
->callee
, &e
->inline_failed
)
907 && DECL_SAVED_TREE (e
->callee
->decl
))
909 if (cgraph_default_inline_p (e
->callee
))
911 if (dump_file
&& early
)
912 fprintf (dump_file
, " Early inlining %s into %s\n",
913 cgraph_node_name (e
->callee
), cgraph_node_name (node
));
914 cgraph_mark_inline (e
);
919 = N_("--param max-inline-insns-single limit reached");
921 if (early
&& inlined
)
923 push_cfun (DECL_STRUCT_FUNCTION (node
->decl
));
924 tree_register_cfg_hooks ();
925 current_function_decl
= node
->decl
;
926 optimize_inline_calls (current_function_decl
);
927 node
->local
.self_insns
= node
->global
.insns
;
928 current_function_decl
= NULL
;
935 /* When inlining shall be performed. */
937 cgraph_gate_inlining (void)
939 return flag_inline_trees
;
942 struct tree_opt_pass pass_ipa_inline
=
945 cgraph_gate_inlining
, /* gate */
946 cgraph_decide_inlining
, /* execute */
949 0, /* static_pass_number */
950 TV_INTEGRATION
, /* tv_id */
951 0, /* properties_required */
952 PROP_cfg
, /* properties_provided */
953 0, /* properties_destroyed */
954 0, /* todo_flags_start */
955 TODO_dump_cgraph
| TODO_dump_func
, /* todo_flags_finish */
959 /* Do inlining of small functions. Doing so early helps profiling and other
960 passes to be somewhat more effective and avoids some code duplication in
961 later real inlining pass for testcases with very many function calls. */
963 cgraph_early_inlining (void)
965 struct cgraph_node
*node
;
967 struct cgraph_node
**order
=
968 xcalloc (cgraph_n_nodes
, sizeof (struct cgraph_node
*));
971 if (sorrycount
|| errorcount
)
973 #ifdef ENABLE_CHECKING
974 for (node
= cgraph_nodes
; node
; node
= node
->next
)
975 gcc_assert (!node
->aux
);
978 nnodes
= cgraph_postorder (order
);
979 for (i
= nnodes
- 1; i
>= 0; i
--)
982 if (node
->analyzed
&& node
->local
.inlinable
983 && (node
->needed
|| node
->reachable
)
985 cgraph_decide_inlining_incrementally (node
, true);
987 cgraph_remove_unreachable_nodes (true, dump_file
);
988 #ifdef ENABLE_CHECKING
989 for (node
= cgraph_nodes
; node
; node
= node
->next
)
990 gcc_assert (!node
->global
.inlined_to
);
995 /* When inlining shall be performed. */
997 cgraph_gate_early_inlining (void)
999 return flag_inline_trees
&& flag_early_inlining
;
1002 struct tree_opt_pass pass_early_ipa_inline
=
1004 "einline", /* name */
1005 cgraph_gate_early_inlining
, /* gate */
1006 cgraph_early_inlining
, /* execute */
1009 0, /* static_pass_number */
1010 TV_INTEGRATION
, /* tv_id */
1011 0, /* properties_required */
1012 PROP_cfg
, /* properties_provided */
1013 0, /* properties_destroyed */
1014 0, /* todo_flags_start */
1015 TODO_dump_cgraph
| TODO_dump_func
, /* todo_flags_finish */