1 /* Callgraph based intraprocedural optimizations.
2 Copyright (C) 2003, 2004, 2005 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, 59 Temple Place - Suite 330, Boston, MA
22 /* This module implements main driver of compilation process as well as
23 few basic intraprocedural optimizers.
25 The main scope of this file is to act as an interface in between
26 tree based frontends and the backend (and middle end)
28 The front-end is supposed to use following functionality:
30 - cgraph_finalize_function
32 This function is called once front-end has parsed whole body of function
33 and it is certain that the function body nor the declaration will change.
35 (There is one exception needed for implementing GCC extern inline function.)
37 - cgraph_varpool_finalize_variable
39 This function has same behavior as the above but is used for static
42 - cgraph_finalize_compilation_unit
44 This function is called once compilation unit is finalized and it will
47 In the unit-at-a-time the call-graph construction and local function
48 analysis takes place here. Bodies of unreachable functions are released
49 to conserve memory usage.
51 ??? The compilation unit in this point of view should be compilation
52 unit as defined by the language - for instance C frontend allows multiple
53 compilation units to be parsed at once and it should call function each
54 time parsing is done so we save memory.
58 In this unit-at-a-time compilation the intra procedural analysis takes
59 place here. In particular the static functions whose address is never
60 taken are marked as local. Backend can then use this information to
61 modify calling conventions, do better inlining or similar optimizations.
63 - cgraph_assemble_pending_functions
64 - cgraph_varpool_assemble_pending_variables
66 In non-unit-at-a-time mode these functions can be used to force compilation
67 of functions or variables that are known to be needed at given stage
70 - cgraph_mark_needed_node
71 - cgraph_varpool_mark_needed_node
73 When function or variable is referenced by some hidden way (for instance
74 via assembly code and marked by attribute "used"), the call-graph data structure
75 must be updated accordingly by this function.
77 - analyze_expr callback
79 This function is responsible for lowering tree nodes not understood by
80 generic code into understandable ones or alternatively marking
81 callgraph and varpool nodes referenced by the as needed.
83 ??? On the tree-ssa genericizing should take place here and we will avoid
84 need for these hooks (replacing them by genericizing hook)
86 - expand_function callback
88 This function is used to expand function and pass it into RTL back-end.
89 Front-end should not make any assumptions about when this function can be
90 called. In particular cgraph_assemble_pending_functions,
91 cgraph_varpool_assemble_pending_variables, cgraph_finalize_function,
92 cgraph_varpool_finalize_function, cgraph_optimize can cause arbitrarily
93 previously finalized functions to be expanded.
95 We implement two compilation modes.
97 - unit-at-a-time: In this mode analyzing of all functions is deferred
98 to cgraph_finalize_compilation_unit and expansion into cgraph_optimize.
100 In cgraph_finalize_compilation_unit the reachable functions are
101 analyzed. During analysis the call-graph edges from reachable
102 functions are constructed and their destinations are marked as
103 reachable. References to functions and variables are discovered too
104 and variables found to be needed output to the assembly file. Via
105 mark_referenced call in assemble_variable functions referenced by
106 static variables are noticed too.
108 The intra-procedural information is produced and its existence
109 indicated by global_info_ready. Once this flag is set it is impossible
110 to change function from !reachable to reachable and thus
111 assemble_variable no longer call mark_referenced.
113 Finally the call-graph is topologically sorted and all reachable functions
114 that has not been completely inlined or are not external are output.
116 ??? It is possible that reference to function or variable is optimized
117 out. We can not deal with this nicely because topological order is not
118 suitable for it. For tree-ssa we may consider another pass doing
119 optimization and re-discovering reachable functions.
121 ??? Reorganize code so variables are output very last and only if they
122 really has been referenced by produced code, so we catch more cases
123 where reference has been optimized out.
127 All functions are variables are output as early as possible to conserve
128 memory consumption. This may or may not result in less memory used but
129 it is still needed for some legacy code that rely on particular ordering
130 of things output from the compiler.
132 Varpool data structures are not used and variables are output directly.
134 Functions are output early using call of
135 cgraph_assemble_pending_function from cgraph_finalize_function. The
136 decision on whether function is needed is made more conservative so
137 uninlininable static functions are needed too. During the call-graph
138 construction the edge destinations are not marked as reachable and it
139 is completely relied upn assemble_variable to mark them.
141 Inlining decision heuristics
142 ??? Move this to separate file after tree-ssa merge.
144 We separate inlining decisions from the inliner itself and store it
145 inside callgraph as so called inline plan. Refer to cgraph.c
146 documentation about particular representation of inline plans in the
149 The implementation of particular heuristics is separated from
150 the rest of code to make it easier to replace it with more complicated
151 implementation in the future. The rest of inlining code acts as a
152 library aimed to modify the callgraph and verify that the parameters
153 on code size growth fits.
155 To mark given call inline, use cgraph_mark_inline function, the
156 verification is performed by cgraph_default_inline_p and
157 cgraph_check_inline_limits.
159 The heuristics implements simple knapsack style algorithm ordering
160 all functions by their "profitability" (estimated by code size growth)
161 and inlining them in priority order.
163 cgraph_decide_inlining implements heuristics taking whole callgraph
164 into account, while cgraph_decide_inlining_incrementally considers
165 only one function at a time and is used in non-unit-at-a-time mode. */
170 #include "coretypes.h"
174 #include "tree-flow.h"
175 #include "tree-inline.h"
176 #include "langhooks.h"
177 #include "pointer-set.h"
184 #include "diagnostic.h"
188 #include "c-common.h"
190 #include "function.h"
191 #include "tree-gimple.h"
193 #define INSNS_PER_CALL 10
195 static void cgraph_expand_all_functions (void);
196 static void cgraph_mark_functions_to_output (void);
197 static void cgraph_expand_function (struct cgraph_node
*);
198 static tree
record_call_1 (tree
*, int *, void *);
199 static void cgraph_mark_local_functions (void);
200 static bool cgraph_default_inline_p (struct cgraph_node
*n
);
201 static void cgraph_analyze_function (struct cgraph_node
*node
);
202 static void cgraph_decide_inlining_incrementally (struct cgraph_node
*);
204 /* Statistics we collect about inlining algorithm. */
205 static int ncalls_inlined
;
206 static int nfunctions_inlined
;
207 static int initial_insns
;
208 static int overall_insns
;
210 /* Records tree nodes seen in cgraph_create_edges. Simply using
211 walk_tree_without_duplicates doesn't guarantee each node is visited
212 once because it gets a new htab upon each recursive call from
214 static struct pointer_set_t
*visited_nodes
;
216 static FILE *cgraph_dump_file
;
218 /* Determine if function DECL is needed. That is, visible to something
219 either outside this translation unit, something magic in the system
220 configury, or (if not doing unit-at-a-time) to something we havn't
224 decide_is_function_needed (struct cgraph_node
*node
, tree decl
)
228 /* If we decided it was needed before, but at the time we didn't have
229 the body of the function available, then it's still needed. We have
230 to go back and re-check its dependencies now. */
234 /* Externally visible functions must be output. The exception is
235 COMDAT functions that must be output only when they are needed. */
236 if (TREE_PUBLIC (decl
) && !DECL_COMDAT (decl
) && !DECL_EXTERNAL (decl
))
239 /* Constructors and destructors are reachable from the runtime by
241 if (DECL_STATIC_CONSTRUCTOR (decl
) || DECL_STATIC_DESTRUCTOR (decl
))
244 /* If the user told us it is used, then it must be so. */
245 if (lookup_attribute ("used", DECL_ATTRIBUTES (decl
)))
248 /* ??? If the assembler name is set by hand, it is possible to assemble
249 the name later after finalizing the function and the fact is noticed
250 in assemble_name then. This is arguably a bug. */
251 if (DECL_ASSEMBLER_NAME_SET_P (decl
)
252 && TREE_SYMBOL_REFERENCED (DECL_ASSEMBLER_NAME (decl
)))
255 if (flag_unit_at_a_time
)
258 /* If not doing unit at a time, then we'll only defer this function
259 if its marked for inlining. Otherwise we want to emit it now. */
261 /* "extern inline" functions are never output locally. */
262 if (DECL_EXTERNAL (decl
))
264 /* Nested functions of extern inline function shall not be emit unless
265 we inlined the origin. */
266 for (origin
= decl_function_context (decl
); origin
;
267 origin
= decl_function_context (origin
))
268 if (DECL_EXTERNAL (origin
))
270 /* We want to emit COMDAT functions only when absolutely necessary. */
271 if (DECL_COMDAT (decl
))
273 if (!DECL_INLINE (decl
)
274 || (!node
->local
.disregard_inline_limits
275 /* When declared inline, defer even the uninlinable functions.
276 This allows them to be eliminated when unused. */
277 && !DECL_DECLARED_INLINE_P (decl
)
278 && (!node
->local
.inlinable
|| !cgraph_default_inline_p (node
))))
286 /* When not doing unit-at-a-time, output all functions enqueued.
287 Return true when such a functions were found. */
290 cgraph_assemble_pending_functions (void)
294 if (flag_unit_at_a_time
)
297 while (cgraph_nodes_queue
)
299 struct cgraph_node
*n
= cgraph_nodes_queue
;
301 cgraph_nodes_queue
= cgraph_nodes_queue
->next_needed
;
302 n
->next_needed
= NULL
;
303 if (!n
->global
.inlined_to
305 && !DECL_EXTERNAL (n
->decl
))
307 cgraph_expand_function (n
);
315 /* DECL has been parsed. Take it, queue it, compile it at the whim of the
316 logic in effect. If NESTED is true, then our caller cannot stand to have
317 the garbage collector run at the moment. We would need to either create
318 a new GC context, or just not compile right now. */
321 cgraph_finalize_function (tree decl
, bool nested
)
323 struct cgraph_node
*node
= cgraph_node (decl
);
325 if (node
->local
.finalized
)
327 /* As an GCC extension we allow redefinition of the function. The
328 semantics when both copies of bodies differ is not well defined.
329 We replace the old body with new body so in unit at a time mode
330 we always use new body, while in normal mode we may end up with
331 old body inlined into some functions and new body expanded and
334 ??? It may make more sense to use one body for inlining and other
335 body for expanding the function but this is difficult to do. */
337 /* If node->output is set, then this is a unit-at-a-time compilation
338 and we have already begun whole-unit analysis. This is *not*
339 testing for whether we've already emitted the function. That
340 case can be sort-of legitimately seen with real function
341 redefinition errors. I would argue that the front end should
342 never present us with such a case, but don't enforce that for now. */
343 gcc_assert (!node
->output
);
345 /* Reset our data structures so we can analyze the function again. */
346 memset (&node
->local
, 0, sizeof (node
->local
));
347 memset (&node
->global
, 0, sizeof (node
->global
));
348 memset (&node
->rtl
, 0, sizeof (node
->rtl
));
349 node
->analyzed
= false;
350 node
->local
.redefined_extern_inline
= true;
352 if (!flag_unit_at_a_time
)
354 struct cgraph_node
*n
;
356 for (n
= cgraph_nodes
; n
; n
= n
->next
)
357 if (n
->global
.inlined_to
== node
)
358 cgraph_remove_node (n
);
361 cgraph_node_remove_callees (node
);
363 /* We may need to re-queue the node for assembling in case
364 we already proceeded it and ignored as not needed. */
365 if (node
->reachable
&& !flag_unit_at_a_time
)
367 struct cgraph_node
*n
;
369 for (n
= cgraph_nodes_queue
; n
; n
= n
->next_needed
)
377 notice_global_symbol (decl
);
379 node
->local
.finalized
= true;
381 lower_nested_functions (decl
);
382 gcc_assert (!node
->nested
);
384 /* If not unit at a time, then we need to create the call graph
385 now, so that called functions can be queued and emitted now. */
386 if (!flag_unit_at_a_time
)
388 cgraph_analyze_function (node
);
389 cgraph_decide_inlining_incrementally (node
);
392 if (decide_is_function_needed (node
, decl
))
393 cgraph_mark_needed_node (node
);
395 /* If not unit at a time, go ahead and emit everything we've found
396 to be reachable at this time. */
399 if (!cgraph_assemble_pending_functions ())
403 /* If we've not yet emitted decl, tell the debug info about it. */
404 if (!TREE_ASM_WRITTEN (decl
))
405 (*debug_hooks
->deferred_inline_function
) (decl
);
407 /* Possibly warn about unused parameters. */
408 if (warn_unused_parameter
)
409 do_warn_unused_parameter (decl
);
412 /* Walk tree and record all calls. Called via walk_tree. */
414 record_call_1 (tree
*tp
, int *walk_subtrees
, void *data
)
418 switch (TREE_CODE (t
))
421 /* ??? Really, we should mark this decl as *potentially* referenced
422 by this function and re-examine whether the decl is actually used
423 after rtl has been generated. */
426 cgraph_varpool_mark_needed_node (cgraph_varpool_node (t
));
427 if (lang_hooks
.callgraph
.analyze_expr
)
428 return lang_hooks
.callgraph
.analyze_expr (tp
, walk_subtrees
,
434 if (flag_unit_at_a_time
)
436 /* Record dereferences to the functions. This makes the
437 functions reachable unconditionally. */
438 tree decl
= TREE_OPERAND (*tp
, 0);
439 if (TREE_CODE (decl
) == FUNCTION_DECL
)
440 cgraph_mark_needed_node (cgraph_node (decl
));
446 tree decl
= get_callee_fndecl (*tp
);
447 if (decl
&& TREE_CODE (decl
) == FUNCTION_DECL
)
449 cgraph_create_edge (data
, cgraph_node (decl
), *tp
);
451 /* When we see a function call, we don't want to look at the
452 function reference in the ADDR_EXPR that is hanging from
453 the CALL_EXPR we're examining here, because we would
454 conclude incorrectly that the function's address could be
455 taken by something that is not a function call. So only
456 walk the function parameter list, skip the other subtrees. */
458 walk_tree (&TREE_OPERAND (*tp
, 1), record_call_1
, data
,
466 /* Save some cycles by not walking types and declaration as we
467 won't find anything useful there anyway. */
468 if (IS_TYPE_OR_DECL_P (*tp
))
474 if ((unsigned int) TREE_CODE (t
) >= LAST_AND_UNUSED_TREE_CODE
)
475 return lang_hooks
.callgraph
.analyze_expr (tp
, walk_subtrees
, data
);
482 /* Create cgraph edges for function calls inside BODY from NODE. */
485 cgraph_create_edges (struct cgraph_node
*node
, tree body
)
487 /* The nodes we're interested in are never shared, so walk
488 the tree ignoring duplicates. */
489 visited_nodes
= pointer_set_create ();
490 walk_tree (&body
, record_call_1
, node
, visited_nodes
);
491 pointer_set_destroy (visited_nodes
);
492 visited_nodes
= NULL
;
495 static bool error_found
;
497 /* Callback of verify_cgraph_node. Check that all call_exprs have
501 verify_cgraph_node_1 (tree
*tp
, int *walk_subtrees
, void *data
)
506 if (TREE_CODE (t
) == CALL_EXPR
&& (decl
= get_callee_fndecl (t
)))
508 struct cgraph_edge
*e
= cgraph_edge (data
, t
);
513 error ("Shared call_expr:");
517 if (e
->callee
->decl
!= cgraph_node (decl
)->decl
)
519 error ("Edge points to wrong declaration:");
520 debug_tree (e
->callee
->decl
);
521 fprintf (stderr
," Instead of:");
528 error ("Missing callgraph edge for call expr:");
534 /* Save some cycles by not walking types and declaration as we
535 won't find anything useful there anyway. */
536 if (IS_TYPE_OR_DECL_P (*tp
))
542 /* Verify cgraph nodes of given cgraph node. */
544 verify_cgraph_node (struct cgraph_node
*node
)
546 struct cgraph_edge
*e
;
547 struct cgraph_node
*main_clone
;
549 timevar_push (TV_CGRAPH_VERIFY
);
551 for (e
= node
->callees
; e
; e
= e
->next_callee
)
554 error ("Aux field set for edge %s->%s",
555 cgraph_node_name (e
->caller
), cgraph_node_name (e
->callee
));
558 for (e
= node
->callers
; e
; e
= e
->next_caller
)
560 if (!e
->inline_failed
)
562 if (node
->global
.inlined_to
563 != (e
->caller
->global
.inlined_to
564 ? e
->caller
->global
.inlined_to
: e
->caller
))
566 error ("Inlined_to pointer is wrong");
569 if (node
->callers
->next_caller
)
571 error ("Multiple inline callers");
576 if (node
->global
.inlined_to
)
578 error ("Inlined_to pointer set for noninline callers");
582 if (!node
->callers
&& node
->global
.inlined_to
)
584 error ("Inlined_to pointer is set but no predecesors found");
587 if (node
->global
.inlined_to
== node
)
589 error ("Inlined_to pointer reffers to itself");
593 for (main_clone
= cgraph_node (node
->decl
); main_clone
;
594 main_clone
= main_clone
->next_clone
)
595 if (main_clone
== node
)
599 error ("Node not found in DECL_ASSEMBLER_NAME hash");
604 && DECL_SAVED_TREE (node
->decl
) && !TREE_ASM_WRITTEN (node
->decl
)
605 && (!DECL_EXTERNAL (node
->decl
) || node
->global
.inlined_to
))
607 walk_tree_without_duplicates (&DECL_SAVED_TREE (node
->decl
),
608 verify_cgraph_node_1
, node
);
609 for (e
= node
->callees
; e
; e
= e
->next_callee
)
613 error ("Edge %s->%s has no corresponding call_expr",
614 cgraph_node_name (e
->caller
),
615 cgraph_node_name (e
->callee
));
623 dump_cgraph_node (stderr
, node
);
624 internal_error ("verify_cgraph_node failed.");
626 timevar_pop (TV_CGRAPH_VERIFY
);
629 /* Verify whole cgraph structure. */
633 struct cgraph_node
*node
;
635 if (sorrycount
|| errorcount
)
638 for (node
= cgraph_nodes
; node
; node
= node
->next
)
639 verify_cgraph_node (node
);
642 /* Analyze the function scheduled to be output. */
644 cgraph_analyze_function (struct cgraph_node
*node
)
646 tree decl
= node
->decl
;
647 struct cgraph_edge
*e
;
649 current_function_decl
= decl
;
651 /* First kill forward declaration so reverse inlining works properly. */
652 cgraph_create_edges (node
, DECL_SAVED_TREE (decl
));
654 node
->local
.inlinable
= tree_inlinable_function_p (decl
);
655 node
->local
.self_insns
= estimate_num_insns (DECL_SAVED_TREE (decl
));
656 if (node
->local
.inlinable
)
657 node
->local
.disregard_inline_limits
658 = lang_hooks
.tree_inlining
.disregard_inline_limits (decl
);
659 for (e
= node
->callers
; e
; e
= e
->next_caller
)
661 if (node
->local
.redefined_extern_inline
)
662 e
->inline_failed
= N_("redefined extern inline functions are not "
663 "considered for inlining");
664 else if (!node
->local
.inlinable
)
665 e
->inline_failed
= N_("function not inlinable");
667 e
->inline_failed
= N_("function not considered for inlining");
669 if (flag_really_no_inline
&& !node
->local
.disregard_inline_limits
)
670 node
->local
.inlinable
= 0;
671 /* Inlining characteristics are maintained by the cgraph_mark_inline. */
672 node
->global
.insns
= node
->local
.self_insns
;
674 node
->analyzed
= true;
675 current_function_decl
= NULL
;
678 /* Analyze the whole compilation unit once it is parsed completely. */
681 cgraph_finalize_compilation_unit (void)
683 struct cgraph_node
*node
;
685 if (errorcount
|| sorrycount
)
690 if (!flag_unit_at_a_time
)
692 cgraph_assemble_pending_functions ();
696 cgraph_varpool_assemble_pending_decls ();
698 fprintf (stderr
, "\nAnalyzing compilation unit\n");
700 timevar_push (TV_CGRAPH
);
701 if (cgraph_dump_file
)
703 fprintf (cgraph_dump_file
, "Initial entry points:");
704 for (node
= cgraph_nodes
; node
; node
= node
->next
)
705 if (node
->needed
&& DECL_SAVED_TREE (node
->decl
))
706 fprintf (cgraph_dump_file
, " %s", cgraph_node_name (node
));
707 fprintf (cgraph_dump_file
, "\n");
710 /* Propagate reachability flag and lower representation of all reachable
711 functions. In the future, lowering will introduce new functions and
712 new entry points on the way (by template instantiation and virtual
713 method table generation for instance). */
714 while (cgraph_nodes_queue
)
716 struct cgraph_edge
*edge
;
717 tree decl
= cgraph_nodes_queue
->decl
;
719 node
= cgraph_nodes_queue
;
720 cgraph_nodes_queue
= cgraph_nodes_queue
->next_needed
;
721 node
->next_needed
= NULL
;
723 /* ??? It is possible to create extern inline function and later using
724 weak alas attribute to kill its body. See
725 gcc.c-torture/compile/20011119-1.c */
726 if (!DECL_SAVED_TREE (decl
))
729 gcc_assert (!node
->analyzed
&& node
->reachable
);
730 gcc_assert (DECL_SAVED_TREE (decl
));
732 cgraph_analyze_function (node
);
734 for (edge
= node
->callees
; edge
; edge
= edge
->next_callee
)
735 if (!edge
->callee
->reachable
)
736 cgraph_mark_reachable_node (edge
->callee
);
738 cgraph_varpool_assemble_pending_decls ();
741 /* Collect entry points to the unit. */
743 if (cgraph_dump_file
)
745 fprintf (cgraph_dump_file
, "Unit entry points:");
746 for (node
= cgraph_nodes
; node
; node
= node
->next
)
747 if (node
->needed
&& DECL_SAVED_TREE (node
->decl
))
748 fprintf (cgraph_dump_file
, " %s", cgraph_node_name (node
));
749 fprintf (cgraph_dump_file
, "\n\nInitial ");
750 dump_cgraph (cgraph_dump_file
);
753 if (cgraph_dump_file
)
754 fprintf (cgraph_dump_file
, "\nReclaiming functions:");
756 for (node
= cgraph_nodes
; node
; node
= node
->next
)
758 tree decl
= node
->decl
;
760 if (!node
->reachable
&& DECL_SAVED_TREE (decl
))
762 if (cgraph_dump_file
)
763 fprintf (cgraph_dump_file
, " %s", cgraph_node_name (node
));
764 cgraph_remove_node (node
);
767 node
->next_needed
= NULL
;
769 if (cgraph_dump_file
)
771 fprintf (cgraph_dump_file
, "\n\nReclaimed ");
772 dump_cgraph (cgraph_dump_file
);
775 timevar_pop (TV_CGRAPH
);
777 /* Figure out what functions we want to assemble. */
780 cgraph_mark_functions_to_output (void)
782 struct cgraph_node
*node
;
784 for (node
= cgraph_nodes
; node
; node
= node
->next
)
786 tree decl
= node
->decl
;
787 struct cgraph_edge
*e
;
789 gcc_assert (!node
->output
);
791 for (e
= node
->callers
; e
; e
= e
->next_caller
)
792 if (e
->inline_failed
)
795 /* We need to output all local functions that are used and not
796 always inlined, as well as those that are reachable from
797 outside the current compilation unit. */
798 if (DECL_SAVED_TREE (decl
)
799 && !node
->global
.inlined_to
801 || (e
&& node
->reachable
))
802 && !TREE_ASM_WRITTEN (decl
)
803 && !DECL_EXTERNAL (decl
))
807 /* We should've reclaimed all functions that are not needed. */
808 #ifdef ENABLE_CHECKING
809 if (!node
->global
.inlined_to
&& DECL_SAVED_TREE (decl
)
810 && !DECL_EXTERNAL (decl
))
812 dump_cgraph_node (stderr
, node
);
813 internal_error ("failed to reclaim unneeded function");
816 gcc_assert (node
->global
.inlined_to
|| !DECL_SAVED_TREE (decl
)
817 || DECL_EXTERNAL (decl
));
824 /* Expand function specified by NODE. */
827 cgraph_expand_function (struct cgraph_node
*node
)
829 tree decl
= node
->decl
;
831 /* We ought to not compile any inline clones. */
832 gcc_assert (!node
->global
.inlined_to
);
834 if (flag_unit_at_a_time
)
835 announce_function (decl
);
837 /* Generate RTL for the body of DECL. */
838 lang_hooks
.callgraph
.expand_function (decl
);
840 /* Make sure that BE didn't give up on compiling. */
841 /* ??? Can happen with nested function of extern inline. */
842 gcc_assert (TREE_ASM_WRITTEN (node
->decl
));
844 current_function_decl
= NULL
;
845 if (!cgraph_preserve_function_body_p (node
->decl
))
847 DECL_SAVED_TREE (node
->decl
) = NULL
;
848 DECL_STRUCT_FUNCTION (node
->decl
) = NULL
;
849 DECL_INITIAL (node
->decl
) = error_mark_node
;
850 /* Eliminate all call edges. This is important so the call_expr no longer
851 points to the dead function body. */
852 cgraph_node_remove_callees (node
);
856 /* Fill array order with all nodes with output flag set in the reverse
857 topological order. */
860 cgraph_postorder (struct cgraph_node
**order
)
862 struct cgraph_node
*node
, *node2
;
865 struct cgraph_edge
*edge
, last
;
867 struct cgraph_node
**stack
=
868 xcalloc (cgraph_n_nodes
, sizeof (struct cgraph_node
*));
870 /* We have to deal with cycles nicely, so use a depth first traversal
871 output algorithm. Ignore the fact that some functions won't need
872 to be output and put them into order as well, so we get dependencies
873 right through intline functions. */
874 for (node
= cgraph_nodes
; node
; node
= node
->next
)
876 for (node
= cgraph_nodes
; node
; node
= node
->next
)
883 node
->aux
= node
->callers
;
886 while (node2
->aux
!= &last
)
889 if (edge
->next_caller
)
890 node2
->aux
= edge
->next_caller
;
893 if (!edge
->caller
->aux
)
895 if (!edge
->caller
->callers
)
896 edge
->caller
->aux
= &last
;
898 edge
->caller
->aux
= edge
->caller
->callers
;
899 stack
[stack_size
++] = node2
;
900 node2
= edge
->caller
;
904 if (node2
->aux
== &last
)
906 order
[order_pos
++] = node2
;
908 node2
= stack
[--stack_size
];
919 /* Perform reachability analysis and reclaim all unreachable nodes.
920 This function also remove unneeded bodies of extern inline functions
921 and thus needs to be done only after inlining decisions has been made. */
923 cgraph_remove_unreachable_nodes (void)
925 struct cgraph_node
*first
= (void *) 1;
926 struct cgraph_node
*node
;
927 bool changed
= false;
930 #ifdef ENABLE_CHECKING
933 if (cgraph_dump_file
)
934 fprintf (cgraph_dump_file
, "\nReclaiming functions:");
935 #ifdef ENABLE_CHECKING
936 for (node
= cgraph_nodes
; node
; node
= node
->next
)
937 gcc_assert (!node
->aux
);
939 for (node
= cgraph_nodes
; node
; node
= node
->next
)
940 if (node
->needed
&& !node
->global
.inlined_to
941 && (!DECL_EXTERNAL (node
->decl
) || !node
->analyzed
))
947 gcc_assert (!node
->aux
);
949 /* Perform reachability analysis. As a special case do not consider
950 extern inline functions not inlined as live because we won't output
952 while (first
!= (void *) 1)
954 struct cgraph_edge
*e
;
958 for (e
= node
->callees
; e
; e
= e
->next_callee
)
961 && (!e
->inline_failed
|| !e
->callee
->analyzed
962 || !DECL_EXTERNAL (e
->callee
->decl
)))
964 e
->callee
->aux
= first
;
969 /* Remove unreachable nodes. Extern inline functions need special care;
970 Unreachable extern inline functions shall be removed.
971 Reachable extern inline functions we never inlined shall get their bodies
973 Reachable extern inline functions we sometimes inlined will be turned into
974 unanalyzed nodes so they look like for true extern functions to the rest
975 of code. Body of such functions is released via remove_node once the
976 inline clones are eliminated. */
977 for (node
= cgraph_nodes
; node
; node
= node
->next
)
982 tree decl
= node
->decl
;
984 node
->global
.inlined_to
= NULL
;
985 if (DECL_STRUCT_FUNCTION (decl
))
986 local_insns
= node
->local
.self_insns
;
989 if (cgraph_dump_file
)
990 fprintf (cgraph_dump_file
, " %s", cgraph_node_name (node
));
991 if (!node
->analyzed
|| !DECL_EXTERNAL (node
->decl
))
992 cgraph_remove_node (node
);
995 struct cgraph_edge
*e
;
997 for (e
= node
->callers
; e
; e
= e
->next_caller
)
1000 if (e
|| node
->needed
)
1002 struct cgraph_node
*clone
;
1004 for (clone
= node
->next_clone
; clone
;
1005 clone
= clone
->next_clone
)
1010 DECL_SAVED_TREE (node
->decl
) = NULL
;
1011 DECL_STRUCT_FUNCTION (node
->decl
) = NULL
;
1012 DECL_INITIAL (node
->decl
) = error_mark_node
;
1014 cgraph_node_remove_callees (node
);
1015 node
->analyzed
= false;
1018 cgraph_remove_node (node
);
1020 if (!DECL_SAVED_TREE (decl
))
1021 insns
+= local_insns
;
1025 for (node
= cgraph_nodes
; node
; node
= node
->next
)
1027 if (cgraph_dump_file
)
1028 fprintf (cgraph_dump_file
, "\nReclaimed %i insns", insns
);
1032 /* Estimate size of the function after inlining WHAT into TO. */
1035 cgraph_estimate_size_after_inlining (int times
, struct cgraph_node
*to
,
1036 struct cgraph_node
*what
)
1038 tree fndecl
= what
->decl
;
1040 int call_insns
= PARAM_VALUE (PARAM_INLINE_CALL_COST
);
1041 for (arg
= DECL_ARGUMENTS (fndecl
); arg
; arg
= TREE_CHAIN (arg
))
1042 call_insns
+= estimate_move_cost (TREE_TYPE (arg
));
1043 return (what
->global
.insns
- call_insns
) * times
+ to
->global
.insns
;
1046 /* Estimate the growth caused by inlining NODE into all callees. */
1049 cgraph_estimate_growth (struct cgraph_node
*node
)
1052 struct cgraph_edge
*e
;
1054 for (e
= node
->callers
; e
; e
= e
->next_caller
)
1055 if (e
->inline_failed
)
1056 growth
+= (cgraph_estimate_size_after_inlining (1, e
->caller
, node
)
1057 - e
->caller
->global
.insns
);
1059 /* ??? Wrong for self recursive functions or cases where we decide to not
1060 inline for different reasons, but it is not big deal as in that case
1061 we will keep the body around, but we will also avoid some inlining. */
1062 if (!node
->needed
&& !DECL_EXTERNAL (node
->decl
))
1063 growth
-= node
->global
.insns
;
1068 /* E is expected to be an edge being inlined. Clone destination node of
1069 the edge and redirect it to the new clone.
1070 DUPLICATE is used for bookkeeping on whether we are actually creating new
1071 clones or re-using node originally representing out-of-line function call.
1074 cgraph_clone_inlined_nodes (struct cgraph_edge
*e
, bool duplicate
)
1076 struct cgraph_node
*n
;
1078 /* We may eliminate the need for out-of-line copy to be output. In that
1079 case just go ahead and re-use it. */
1080 if (!e
->callee
->callers
->next_caller
1081 && (!e
->callee
->needed
|| DECL_EXTERNAL (e
->callee
->decl
))
1083 && flag_unit_at_a_time
)
1085 gcc_assert (!e
->callee
->global
.inlined_to
);
1086 if (!DECL_EXTERNAL (e
->callee
->decl
))
1087 overall_insns
-= e
->callee
->global
.insns
, nfunctions_inlined
++;
1092 n
= cgraph_clone_node (e
->callee
);
1093 cgraph_redirect_edge_callee (e
, n
);
1096 if (e
->caller
->global
.inlined_to
)
1097 e
->callee
->global
.inlined_to
= e
->caller
->global
.inlined_to
;
1099 e
->callee
->global
.inlined_to
= e
->caller
;
1101 /* Recursively clone all bodies. */
1102 for (e
= e
->callee
->callees
; e
; e
= e
->next_callee
)
1103 if (!e
->inline_failed
)
1104 cgraph_clone_inlined_nodes (e
, duplicate
);
1107 /* Mark edge E as inlined and update callgraph accordingly. */
1110 cgraph_mark_inline_edge (struct cgraph_edge
*e
)
1112 int old_insns
= 0, new_insns
= 0;
1113 struct cgraph_node
*to
= NULL
, *what
;
1115 gcc_assert (e
->inline_failed
);
1116 e
->inline_failed
= NULL
;
1118 if (!e
->callee
->global
.inlined
&& flag_unit_at_a_time
)
1119 DECL_POSSIBLY_INLINED (e
->callee
->decl
) = true;
1120 e
->callee
->global
.inlined
= true;
1122 cgraph_clone_inlined_nodes (e
, true);
1126 /* Now update size of caller and all functions caller is inlined into. */
1127 for (;e
&& !e
->inline_failed
; e
= e
->caller
->callers
)
1129 old_insns
= e
->caller
->global
.insns
;
1130 new_insns
= cgraph_estimate_size_after_inlining (1, e
->caller
,
1132 gcc_assert (new_insns
>= 0);
1134 to
->global
.insns
= new_insns
;
1136 gcc_assert (what
->global
.inlined_to
== to
);
1137 if (new_insns
> old_insns
)
1138 overall_insns
+= new_insns
- old_insns
;
1142 /* Mark all calls of EDGE->CALLEE inlined into EDGE->CALLER.
1143 Return following unredirected edge in the list of callers
1146 static struct cgraph_edge
*
1147 cgraph_mark_inline (struct cgraph_edge
*edge
)
1149 struct cgraph_node
*to
= edge
->caller
;
1150 struct cgraph_node
*what
= edge
->callee
;
1151 struct cgraph_edge
*e
, *next
;
1154 /* Look for all calls, mark them inline and clone recursively
1155 all inlined functions. */
1156 for (e
= what
->callers
; e
; e
= next
)
1158 next
= e
->next_caller
;
1159 if (e
->caller
== to
&& e
->inline_failed
)
1161 cgraph_mark_inline_edge (e
);
1171 /* Return false when inlining WHAT into TO is not good idea
1172 as it would cause too large growth of function bodies. */
1175 cgraph_check_inline_limits (struct cgraph_node
*to
, struct cgraph_node
*what
,
1176 const char **reason
)
1179 struct cgraph_edge
*e
;
1183 if (to
->global
.inlined_to
)
1184 to
= to
->global
.inlined_to
;
1186 for (e
= to
->callees
; e
; e
= e
->next_callee
)
1187 if (e
->callee
== what
)
1190 /* When inlining large function body called once into small function,
1191 take the inlined function as base for limiting the growth. */
1192 if (to
->local
.self_insns
> what
->local
.self_insns
)
1193 limit
= to
->local
.self_insns
;
1195 limit
= what
->local
.self_insns
;
1197 limit
+= limit
* PARAM_VALUE (PARAM_LARGE_FUNCTION_GROWTH
) / 100;
1199 newsize
= cgraph_estimate_size_after_inlining (times
, to
, what
);
1200 if (newsize
> PARAM_VALUE (PARAM_LARGE_FUNCTION_INSNS
)
1204 *reason
= N_("--param large-function-growth limit reached");
1210 /* Return true when function N is small enough to be inlined. */
1213 cgraph_default_inline_p (struct cgraph_node
*n
)
1215 if (!DECL_INLINE (n
->decl
) || !DECL_SAVED_TREE (n
->decl
))
1217 if (DECL_DECLARED_INLINE_P (n
->decl
))
1218 return n
->global
.insns
< MAX_INLINE_INSNS_SINGLE
;
1220 return n
->global
.insns
< MAX_INLINE_INSNS_AUTO
;
1223 /* Return true when inlining WHAT would create recursive inlining.
1224 We call recursive inlining all cases where same function appears more than
1225 once in the single recursion nest path in the inline graph. */
1228 cgraph_recursive_inlining_p (struct cgraph_node
*to
,
1229 struct cgraph_node
*what
,
1230 const char **reason
)
1233 if (to
->global
.inlined_to
)
1234 recursive
= what
->decl
== to
->global
.inlined_to
->decl
;
1236 recursive
= what
->decl
== to
->decl
;
1237 /* Marking recursive function inline has sane semantic and thus we should
1239 if (recursive
&& reason
)
1240 *reason
= (what
->local
.disregard_inline_limits
1241 ? N_("recursive inlining") : "");
1245 /* Recompute heap nodes for each of callees. */
1247 update_callee_keys (fibheap_t heap
, struct fibnode
**heap_node
,
1248 struct cgraph_node
*node
)
1250 struct cgraph_edge
*e
;
1252 for (e
= node
->callees
; e
; e
= e
->next_callee
)
1253 if (e
->inline_failed
&& heap_node
[e
->callee
->uid
])
1254 fibheap_replace_key (heap
, heap_node
[e
->callee
->uid
],
1255 cgraph_estimate_growth (e
->callee
));
1256 else if (!e
->inline_failed
)
1257 update_callee_keys (heap
, heap_node
, e
->callee
);
1260 /* Enqueue all recursive calls from NODE into queue linked via aux pointers
1261 in between FIRST and LAST. WHERE is used for bookkeeping while looking
1262 int calls inlined within NODE. */
1264 lookup_recursive_calls (struct cgraph_node
*node
, struct cgraph_node
*where
,
1265 struct cgraph_edge
**first
, struct cgraph_edge
**last
)
1267 struct cgraph_edge
*e
;
1268 for (e
= where
->callees
; e
; e
= e
->next_callee
)
1269 if (e
->callee
== node
)
1277 for (e
= where
->callees
; e
; e
= e
->next_callee
)
1278 if (!e
->inline_failed
)
1279 lookup_recursive_calls (node
, e
->callee
, first
, last
);
1282 /* Decide on recursive inlining: in the case function has recursive calls,
1283 inline until body size reaches given argument. */
1285 cgraph_decide_recursive_inlining (struct cgraph_node
*node
)
1287 int limit
= PARAM_VALUE (PARAM_MAX_INLINE_INSNS_RECURSIVE_AUTO
);
1288 int max_depth
= PARAM_VALUE (PARAM_MAX_INLINE_RECURSIVE_DEPTH_AUTO
);
1289 struct cgraph_edge
*first_call
= NULL
, *last_call
= NULL
;
1290 struct cgraph_edge
*last_in_current_depth
;
1291 struct cgraph_edge
*e
;
1292 struct cgraph_node
*master_clone
;
1296 if (DECL_DECLARED_INLINE_P (node
->decl
))
1298 limit
= PARAM_VALUE (PARAM_MAX_INLINE_INSNS_RECURSIVE
);
1299 max_depth
= PARAM_VALUE (PARAM_MAX_INLINE_RECURSIVE_DEPTH
);
1302 /* Make sure that function is small enough to be considered for inlining. */
1304 || cgraph_estimate_size_after_inlining (1, node
, node
) >= limit
)
1306 lookup_recursive_calls (node
, node
, &first_call
, &last_call
);
1310 if (cgraph_dump_file
)
1311 fprintf (cgraph_dump_file
,
1312 "\nPerforming recursive inlining on %s\n",
1313 cgraph_node_name (node
));
1315 /* We need original clone to copy around. */
1316 master_clone
= cgraph_clone_node (node
);
1317 master_clone
->needed
= true;
1318 for (e
= master_clone
->callees
; e
; e
= e
->next_callee
)
1319 if (!e
->inline_failed
)
1320 cgraph_clone_inlined_nodes (e
, true);
1322 /* Do the inlining and update list of recursive call during process. */
1323 last_in_current_depth
= last_call
;
1325 && cgraph_estimate_size_after_inlining (1, node
, master_clone
) <= limit
)
1327 struct cgraph_edge
*curr
= first_call
;
1329 first_call
= first_call
->aux
;
1332 cgraph_redirect_edge_callee (curr
, master_clone
);
1333 cgraph_mark_inline_edge (curr
);
1334 lookup_recursive_calls (node
, curr
->callee
, &first_call
, &last_call
);
1336 if (last_in_current_depth
1337 && ++depth
>= max_depth
)
1342 /* Cleanup queue pointers. */
1345 struct cgraph_edge
*next
= first_call
->aux
;
1346 first_call
->aux
= NULL
;
1349 if (cgraph_dump_file
)
1350 fprintf (cgraph_dump_file
,
1351 "\n Inlined %i times, body grown from %i to %i insns\n", n
,
1352 master_clone
->global
.insns
, node
->global
.insns
);
1354 /* Remove master clone we used for inlining. We rely that clones inlined
1355 into master clone gets queued just before master clone so we don't
1357 for (node
= cgraph_nodes
; node
!= master_clone
;
1359 if (node
->global
.inlined_to
== master_clone
)
1360 cgraph_remove_node (node
);
1361 cgraph_remove_node (master_clone
);
1364 /* Set inline_failed for all callers of given function to REASON. */
1367 cgraph_set_inline_failed (struct cgraph_node
*node
, const char *reason
)
1369 struct cgraph_edge
*e
;
1371 if (cgraph_dump_file
)
1372 fprintf (cgraph_dump_file
, "Inlining failed: %s\n", reason
);
1373 for (e
= node
->callers
; e
; e
= e
->next_caller
)
1374 if (e
->inline_failed
)
1375 e
->inline_failed
= reason
;
1378 /* We use greedy algorithm for inlining of small functions:
1379 All inline candidates are put into prioritized heap based on estimated
1380 growth of the overall number of instructions and then update the estimates.
1382 INLINED and INLINED_CALEES are just pointers to arrays large enough
1383 to be passed to cgraph_inlined_into and cgraph_inlined_callees. */
1386 cgraph_decide_inlining_of_small_functions (void)
1388 struct cgraph_node
*node
;
1389 fibheap_t heap
= fibheap_new ();
1390 struct fibnode
**heap_node
=
1391 xcalloc (cgraph_max_uid
, sizeof (struct fibnode
*));
1392 int max_insns
= ((HOST_WIDEST_INT
) initial_insns
1393 * (100 + PARAM_VALUE (PARAM_INLINE_UNIT_GROWTH
)) / 100);
1395 /* Put all inline candidates into the heap. */
1397 for (node
= cgraph_nodes
; node
; node
= node
->next
)
1399 if (!node
->local
.inlinable
|| !node
->callers
1400 || node
->local
.disregard_inline_limits
)
1403 if (!cgraph_default_inline_p (node
))
1405 cgraph_set_inline_failed (node
,
1406 N_("--param max-inline-insns-single limit reached"));
1409 heap_node
[node
->uid
] =
1410 fibheap_insert (heap
, cgraph_estimate_growth (node
), node
);
1413 if (cgraph_dump_file
)
1414 fprintf (cgraph_dump_file
, "\nDeciding on smaller functions:\n");
1415 while (overall_insns
<= max_insns
&& (node
= fibheap_extract_min (heap
)))
1417 struct cgraph_edge
*e
, *next
;
1418 int old_insns
= overall_insns
;
1420 heap_node
[node
->uid
] = NULL
;
1421 if (cgraph_dump_file
)
1422 fprintf (cgraph_dump_file
,
1423 "\nConsidering %s with %i insns\n"
1424 " Estimated growth is %+i insns.\n",
1425 cgraph_node_name (node
), node
->global
.insns
,
1426 cgraph_estimate_growth (node
));
1427 if (!cgraph_default_inline_p (node
))
1429 cgraph_set_inline_failed (node
,
1430 N_("--param max-inline-insns-single limit reached after inlining into the callee"));
1433 for (e
= node
->callers
; e
; e
= next
)
1435 next
= e
->next_caller
;
1436 if (e
->inline_failed
)
1438 struct cgraph_node
*where
;
1440 if (cgraph_recursive_inlining_p (e
->caller
, e
->callee
,
1442 || !cgraph_check_inline_limits (e
->caller
, e
->callee
,
1445 if (cgraph_dump_file
)
1446 fprintf (cgraph_dump_file
, " Not inlining into %s:%s.\n",
1447 cgraph_node_name (e
->caller
), e
->inline_failed
);
1450 next
= cgraph_mark_inline (e
);
1452 if (where
->global
.inlined_to
)
1453 where
= where
->global
.inlined_to
;
1455 if (heap_node
[where
->uid
])
1456 fibheap_replace_key (heap
, heap_node
[where
->uid
],
1457 cgraph_estimate_growth (where
));
1459 if (cgraph_dump_file
)
1460 fprintf (cgraph_dump_file
,
1461 " Inlined into %s which now has %i insns.\n",
1462 cgraph_node_name (e
->caller
),
1463 e
->caller
->global
.insns
);
1467 cgraph_decide_recursive_inlining (node
);
1469 /* Similarly all functions called by the function we just inlined
1470 are now called more times; update keys. */
1471 update_callee_keys (heap
, heap_node
, node
);
1473 if (cgraph_dump_file
)
1474 fprintf (cgraph_dump_file
,
1475 " Inlined for a net change of %+i insns.\n",
1476 overall_insns
- old_insns
);
1478 while ((node
= fibheap_extract_min (heap
)) != NULL
)
1479 if (!node
->local
.disregard_inline_limits
)
1480 cgraph_set_inline_failed (node
, N_("--param inline-unit-growth limit reached"));
1481 fibheap_delete (heap
);
1485 /* Decide on the inlining. We do so in the topological order to avoid
1486 expenses on updating data structures. */
1489 cgraph_decide_inlining (void)
1491 struct cgraph_node
*node
;
1493 struct cgraph_node
**order
=
1494 xcalloc (cgraph_n_nodes
, sizeof (struct cgraph_node
*));
1498 for (node
= cgraph_nodes
; node
; node
= node
->next
)
1499 initial_insns
+= node
->local
.self_insns
;
1500 overall_insns
= initial_insns
;
1502 nnodes
= cgraph_postorder (order
);
1504 if (cgraph_dump_file
)
1505 fprintf (cgraph_dump_file
,
1506 "\nDeciding on inlining. Starting with %i insns.\n",
1509 for (node
= cgraph_nodes
; node
; node
= node
->next
)
1512 if (cgraph_dump_file
)
1513 fprintf (cgraph_dump_file
, "\nInlining always_inline functions:\n");
1515 /* In the first pass mark all always_inline edges. Do this with a priority
1516 so none of our later choices will make this impossible. */
1517 for (i
= nnodes
- 1; i
>= 0; i
--)
1519 struct cgraph_edge
*e
, *next
;
1523 if (!node
->local
.disregard_inline_limits
)
1525 if (cgraph_dump_file
)
1526 fprintf (cgraph_dump_file
,
1527 "\nConsidering %s %i insns (always inline)\n",
1528 cgraph_node_name (node
), node
->global
.insns
);
1529 old_insns
= overall_insns
;
1530 for (e
= node
->callers
; e
; e
= next
)
1532 next
= e
->next_caller
;
1533 if (!e
->inline_failed
)
1535 if (cgraph_recursive_inlining_p (e
->caller
, e
->callee
,
1538 cgraph_mark_inline_edge (e
);
1539 if (cgraph_dump_file
)
1540 fprintf (cgraph_dump_file
,
1541 " Inlined into %s which now has %i insns.\n",
1542 cgraph_node_name (e
->caller
),
1543 e
->caller
->global
.insns
);
1545 if (cgraph_dump_file
)
1546 fprintf (cgraph_dump_file
,
1547 " Inlined for a net change of %+i insns.\n",
1548 overall_insns
- old_insns
);
1551 if (!flag_really_no_inline
)
1552 cgraph_decide_inlining_of_small_functions ();
1554 if (!flag_really_no_inline
1555 && flag_inline_functions_called_once
)
1557 if (cgraph_dump_file
)
1558 fprintf (cgraph_dump_file
, "\nDeciding on functions called once:\n");
1560 /* And finally decide what functions are called once. */
1562 for (i
= nnodes
- 1; i
>= 0; i
--)
1566 if (node
->callers
&& !node
->callers
->next_caller
&& !node
->needed
1567 && node
->local
.inlinable
&& node
->callers
->inline_failed
1568 && !DECL_EXTERNAL (node
->decl
) && !DECL_COMDAT (node
->decl
))
1571 struct cgraph_node
*node1
;
1573 /* Verify that we won't duplicate the caller. */
1574 for (node1
= node
->callers
->caller
;
1575 node1
->callers
&& !node1
->callers
->inline_failed
1576 && ok
; node1
= node1
->callers
->caller
)
1577 if (node1
->callers
->next_caller
|| node1
->needed
)
1581 if (cgraph_dump_file
)
1582 fprintf (cgraph_dump_file
,
1583 "\nConsidering %s %i insns.\n"
1584 " Called once from %s %i insns.\n",
1585 cgraph_node_name (node
), node
->global
.insns
,
1586 cgraph_node_name (node
->callers
->caller
),
1587 node
->callers
->caller
->global
.insns
);
1589 old_insns
= overall_insns
;
1591 if (cgraph_check_inline_limits (node
->callers
->caller
, node
,
1594 cgraph_mark_inline (node
->callers
);
1595 if (cgraph_dump_file
)
1596 fprintf (cgraph_dump_file
,
1597 " Inlined into %s which now has %i insns"
1598 " for a net change of %+i insns.\n",
1599 cgraph_node_name (node
->callers
->caller
),
1600 node
->callers
->caller
->global
.insns
,
1601 overall_insns
- old_insns
);
1605 if (cgraph_dump_file
)
1606 fprintf (cgraph_dump_file
,
1607 " Inline limit reached, not inlined.\n");
1614 /* We will never output extern functions we didn't inline.
1615 ??? Perhaps we can prevent accounting of growth of external
1616 inline functions. */
1617 cgraph_remove_unreachable_nodes ();
1619 if (cgraph_dump_file
)
1620 fprintf (cgraph_dump_file
,
1621 "\nInlined %i calls, eliminated %i functions, "
1622 "%i insns turned to %i insns.\n\n",
1623 ncalls_inlined
, nfunctions_inlined
, initial_insns
,
1628 /* Decide on the inlining. We do so in the topological order to avoid
1629 expenses on updating data structures. */
1632 cgraph_decide_inlining_incrementally (struct cgraph_node
*node
)
1634 struct cgraph_edge
*e
;
1636 /* First of all look for always inline functions. */
1637 for (e
= node
->callees
; e
; e
= e
->next_callee
)
1638 if (e
->callee
->local
.disregard_inline_limits
1640 && !cgraph_recursive_inlining_p (node
, e
->callee
, &e
->inline_failed
)
1641 /* ??? It is possible that renaming variable removed the function body
1642 in duplicate_decls. See gcc.c-torture/compile/20011119-2.c */
1643 && DECL_SAVED_TREE (e
->callee
->decl
))
1644 cgraph_mark_inline (e
);
1646 /* Now do the automatic inlining. */
1647 if (!flag_really_no_inline
)
1648 for (e
= node
->callees
; e
; e
= e
->next_callee
)
1649 if (e
->callee
->local
.inlinable
1651 && !e
->callee
->local
.disregard_inline_limits
1652 && !cgraph_recursive_inlining_p (node
, e
->callee
, &e
->inline_failed
)
1653 && cgraph_check_inline_limits (node
, e
->callee
, &e
->inline_failed
)
1654 && DECL_SAVED_TREE (e
->callee
->decl
))
1656 if (cgraph_default_inline_p (e
->callee
))
1657 cgraph_mark_inline (e
);
1660 = N_("--param max-inline-insns-single limit reached");
1665 /* Return true when CALLER_DECL should be inlined into CALLEE_DECL. */
1668 cgraph_inline_p (struct cgraph_edge
*e
, const char **reason
)
1670 *reason
= e
->inline_failed
;
1671 return !e
->inline_failed
;
1676 /* Expand all functions that must be output.
1678 Attempt to topologically sort the nodes so function is output when
1679 all called functions are already assembled to allow data to be
1680 propagated across the callgraph. Use a stack to get smaller distance
1681 between a function and its callees (later we may choose to use a more
1682 sophisticated algorithm for function reordering; we will likely want
1683 to use subsections to make the output functions appear in top-down
1687 cgraph_expand_all_functions (void)
1689 struct cgraph_node
*node
;
1690 struct cgraph_node
**order
=
1691 xcalloc (cgraph_n_nodes
, sizeof (struct cgraph_node
*));
1692 int order_pos
= 0, new_order_pos
= 0;
1695 order_pos
= cgraph_postorder (order
);
1696 gcc_assert (order_pos
== cgraph_n_nodes
);
1698 /* Garbage collector may remove inline clones we eliminate during
1699 optimization. So we must be sure to not reference them. */
1700 for (i
= 0; i
< order_pos
; i
++)
1701 if (order
[i
]->output
)
1702 order
[new_order_pos
++] = order
[i
];
1704 for (i
= new_order_pos
- 1; i
>= 0; i
--)
1709 gcc_assert (node
->reachable
);
1711 cgraph_expand_function (node
);
1717 /* Mark all local functions.
1719 A local function is one whose calls can occur only in the current
1720 compilation unit and all its calls are explicit, so we can change
1721 its calling convention. We simply mark all static functions whose
1722 address is not taken as local. */
1725 cgraph_mark_local_functions (void)
1727 struct cgraph_node
*node
;
1729 /* Figure out functions we want to assemble. */
1730 for (node
= cgraph_nodes
; node
; node
= node
->next
)
1732 node
->local
.local
= (!node
->needed
1733 && DECL_SAVED_TREE (node
->decl
)
1734 && !TREE_PUBLIC (node
->decl
));
1737 if (cgraph_dump_file
)
1739 fprintf (cgraph_dump_file
, "\nMarking local functions:");
1740 for (node
= cgraph_nodes
; node
; node
= node
->next
)
1741 if (node
->local
.local
)
1742 fprintf (cgraph_dump_file
, " %s", cgraph_node_name (node
));
1743 fprintf (cgraph_dump_file
, "\n\n");
1747 /* Return true when function body of DECL still needs to be kept around
1748 for later re-use. */
1750 cgraph_preserve_function_body_p (tree decl
)
1752 struct cgraph_node
*node
;
1753 /* Keep the body; we're going to dump it. */
1754 if (dump_enabled_p (TDI_tree_all
))
1756 if (!cgraph_global_info_ready
)
1757 return (DECL_INLINE (decl
) && !flag_really_no_inline
);
1758 /* Look if there is any clone around. */
1759 for (node
= cgraph_node (decl
); node
; node
= node
->next_clone
)
1760 if (node
->global
.inlined_to
)
1765 /* Perform simple optimizations based on callgraph. */
1768 cgraph_optimize (void)
1770 if (errorcount
|| sorrycount
)
1773 #ifdef ENABLE_CHECKING
1776 if (!flag_unit_at_a_time
)
1779 process_pending_assemble_externals ();
1781 timevar_push (TV_CGRAPHOPT
);
1783 fprintf (stderr
, "Performing intraprocedural optimizations\n");
1785 cgraph_mark_local_functions ();
1786 if (cgraph_dump_file
)
1788 fprintf (cgraph_dump_file
, "Marked ");
1789 dump_cgraph (cgraph_dump_file
);
1792 if (flag_inline_trees
)
1793 cgraph_decide_inlining ();
1794 cgraph_global_info_ready
= true;
1795 if (cgraph_dump_file
)
1797 fprintf (cgraph_dump_file
, "Optimized ");
1798 dump_cgraph (cgraph_dump_file
);
1800 timevar_pop (TV_CGRAPHOPT
);
1802 /* Output everything. */
1804 fprintf (stderr
, "Assembling functions:\n");
1805 #ifdef ENABLE_CHECKING
1809 cgraph_mark_functions_to_output ();
1811 cgraph_expand_all_functions ();
1812 if (cgraph_dump_file
)
1814 fprintf (cgraph_dump_file
, "\nFinal ");
1815 dump_cgraph (cgraph_dump_file
);
1817 #ifdef ENABLE_CHECKING
1819 /* Double check that all inline clones are gone and that all
1820 function bodies have been released from memory. */
1821 if (flag_unit_at_a_time
1822 && !dump_enabled_p (TDI_tree_all
)
1823 && !(sorrycount
|| errorcount
))
1825 struct cgraph_node
*node
;
1826 bool error_found
= false;
1828 for (node
= cgraph_nodes
; node
; node
= node
->next
)
1830 && (node
->global
.inlined_to
1831 || DECL_SAVED_TREE (node
->decl
)))
1834 dump_cgraph_node (stderr
, node
);
1837 internal_error ("Nodes with no released memory found.");
1842 /* Generate and emit a static constructor or destructor. WHICH must be
1843 one of 'I' or 'D'. BODY should be a STATEMENT_LIST containing
1844 GENERIC statements. */
1847 cgraph_build_static_cdtor (char which
, tree body
, int priority
)
1849 static int counter
= 0;
1851 tree decl
, name
, resdecl
;
1853 sprintf (which_buf
, "%c_%d", which
, counter
++);
1854 name
= get_file_function_name_long (which_buf
);
1856 decl
= build_decl (FUNCTION_DECL
, name
,
1857 build_function_type (void_type_node
, void_list_node
));
1858 current_function_decl
= decl
;
1860 resdecl
= build_decl (RESULT_DECL
, NULL_TREE
, void_type_node
);
1861 DECL_ARTIFICIAL (resdecl
) = 1;
1862 DECL_IGNORED_P (resdecl
) = 1;
1863 DECL_RESULT (decl
) = resdecl
;
1865 allocate_struct_function (decl
);
1867 TREE_STATIC (decl
) = 1;
1868 TREE_USED (decl
) = 1;
1869 DECL_ARTIFICIAL (decl
) = 1;
1870 DECL_IGNORED_P (decl
) = 1;
1871 DECL_NO_INSTRUMENT_FUNCTION_ENTRY_EXIT (decl
) = 1;
1872 DECL_SAVED_TREE (decl
) = body
;
1873 TREE_PUBLIC (decl
) = ! targetm
.have_ctors_dtors
;
1874 DECL_UNINLINABLE (decl
) = 1;
1876 DECL_INITIAL (decl
) = make_node (BLOCK
);
1877 TREE_USED (DECL_INITIAL (decl
)) = 1;
1879 DECL_SOURCE_LOCATION (decl
) = input_location
;
1880 cfun
->function_end_locus
= input_location
;
1885 DECL_STATIC_CONSTRUCTOR (decl
) = 1;
1888 DECL_STATIC_DESTRUCTOR (decl
) = 1;
1894 gimplify_function_tree (decl
);
1896 /* ??? We will get called LATE in the compilation process. */
1897 if (cgraph_global_info_ready
)
1898 tree_rest_of_compilation (decl
);
1900 cgraph_finalize_function (decl
, 0);
1902 if (targetm
.have_ctors_dtors
)
1904 void (*fn
) (rtx
, int);
1907 fn
= targetm
.asm_out
.constructor
;
1909 fn
= targetm
.asm_out
.destructor
;
1910 fn (XEXP (DECL_RTL (decl
), 0), priority
);
1917 cgraph_dump_file
= dump_begin (TDI_cgraph
, NULL
);