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"
194 #define INSNS_PER_CALL 10
196 static void cgraph_expand_all_functions (void);
197 static void cgraph_mark_functions_to_output (void);
198 static void cgraph_expand_function (struct cgraph_node
*);
199 static tree
record_call_1 (tree
*, int *, void *);
200 static void cgraph_mark_local_functions (void);
201 static bool cgraph_default_inline_p (struct cgraph_node
*n
);
202 static void cgraph_analyze_function (struct cgraph_node
*node
);
203 static void cgraph_decide_inlining_incrementally (struct cgraph_node
*);
205 /* Statistics we collect about inlining algorithm. */
206 static int ncalls_inlined
;
207 static int nfunctions_inlined
;
208 static int initial_insns
;
209 static int overall_insns
;
211 /* Records tree nodes seen in cgraph_create_edges. Simply using
212 walk_tree_without_duplicates doesn't guarantee each node is visited
213 once because it gets a new htab upon each recursive call from
215 static struct pointer_set_t
*visited_nodes
;
217 static FILE *cgraph_dump_file
;
219 /* Determine if function DECL is needed. That is, visible to something
220 either outside this translation unit, something magic in the system
221 configury, or (if not doing unit-at-a-time) to something we havn't
225 decide_is_function_needed (struct cgraph_node
*node
, tree decl
)
229 /* If we decided it was needed before, but at the time we didn't have
230 the body of the function available, then it's still needed. We have
231 to go back and re-check its dependencies now. */
235 /* Externally visible functions must be output. The exception is
236 COMDAT functions that must be output only when they are needed. */
237 if (TREE_PUBLIC (decl
) && !DECL_COMDAT (decl
) && !DECL_EXTERNAL (decl
))
240 /* Constructors and destructors are reachable from the runtime by
242 if (DECL_STATIC_CONSTRUCTOR (decl
) || DECL_STATIC_DESTRUCTOR (decl
))
245 /* If the user told us it is used, then it must be so. */
246 if (lookup_attribute ("used", DECL_ATTRIBUTES (decl
)))
249 /* ??? If the assembler name is set by hand, it is possible to assemble
250 the name later after finalizing the function and the fact is noticed
251 in assemble_name then. This is arguably a bug. */
252 if (DECL_ASSEMBLER_NAME_SET_P (decl
)
253 && TREE_SYMBOL_REFERENCED (DECL_ASSEMBLER_NAME (decl
)))
256 if (flag_unit_at_a_time
)
259 /* If not doing unit at a time, then we'll only defer this function
260 if its marked for inlining. Otherwise we want to emit it now. */
262 /* "extern inline" functions are never output locally. */
263 if (DECL_EXTERNAL (decl
))
265 /* Nested functions of extern inline function shall not be emit unless
266 we inlined the origin. */
267 for (origin
= decl_function_context (decl
); origin
;
268 origin
= decl_function_context (origin
))
269 if (DECL_EXTERNAL (origin
))
271 /* We want to emit COMDAT functions only when absolutely necessary. */
272 if (DECL_COMDAT (decl
))
274 if (!DECL_INLINE (decl
)
275 || (!node
->local
.disregard_inline_limits
276 /* When declared inline, defer even the uninlinable functions.
277 This allows them to be eliminated when unused. */
278 && !DECL_DECLARED_INLINE_P (decl
)
279 && (!node
->local
.inlinable
|| !cgraph_default_inline_p (node
))))
285 /* Walk the decls we marked as necessary and see if they reference new
286 variables or functions and add them into the worklists. */
288 cgraph_varpool_analyze_pending_decls (void)
290 bool changed
= false;
291 timevar_push (TV_CGRAPH
);
293 while (cgraph_varpool_first_unanalyzed_node
)
295 tree decl
= cgraph_varpool_first_unanalyzed_node
->decl
;
297 cgraph_varpool_first_unanalyzed_node
->analyzed
= true;
299 cgraph_varpool_first_unanalyzed_node
= cgraph_varpool_first_unanalyzed_node
->next_needed
;
301 if (DECL_INITIAL (decl
))
302 cgraph_create_edges (NULL
, DECL_INITIAL (decl
));
305 timevar_pop (TV_CGRAPH
);
309 /* Optimization of function bodies might've rendered some variables as
310 unnecessary so we want to avoid these from being compiled.
312 This is done by prunning the queue and keeping only the variables that
313 really appear needed (ie they are either externally visible or referenced
314 by compiled function). Re-doing the reachability analysis on variables
315 brings back the remaining variables referenced by these. */
317 cgraph_varpool_remove_unreferenced_decls (void)
319 struct cgraph_varpool_node
*next
, *node
= cgraph_varpool_nodes_queue
;
321 cgraph_varpool_reset_queue ();
323 if (errorcount
|| sorrycount
)
328 tree decl
= node
->decl
;
329 next
= node
->next_needed
;
333 && ((DECL_ASSEMBLER_NAME_SET_P (decl
)
334 && TREE_SYMBOL_REFERENCED (DECL_ASSEMBLER_NAME (decl
)))
335 || node
->force_output
336 || decide_is_variable_needed (node
, decl
)))
337 cgraph_varpool_mark_needed_node (node
);
341 cgraph_varpool_analyze_pending_decls ();
345 /* When not doing unit-at-a-time, output all functions enqueued.
346 Return true when such a functions were found. */
349 cgraph_assemble_pending_functions (void)
353 if (flag_unit_at_a_time
)
356 while (cgraph_nodes_queue
)
358 struct cgraph_node
*n
= cgraph_nodes_queue
;
360 cgraph_nodes_queue
= cgraph_nodes_queue
->next_needed
;
361 n
->next_needed
= NULL
;
362 if (!n
->global
.inlined_to
364 && !DECL_EXTERNAL (n
->decl
))
366 cgraph_expand_function (n
);
374 /* DECL has been parsed. Take it, queue it, compile it at the whim of the
375 logic in effect. If NESTED is true, then our caller cannot stand to have
376 the garbage collector run at the moment. We would need to either create
377 a new GC context, or just not compile right now. */
380 cgraph_finalize_function (tree decl
, bool nested
)
382 struct cgraph_node
*node
= cgraph_node (decl
);
384 if (node
->local
.finalized
)
386 /* As an GCC extension we allow redefinition of the function. The
387 semantics when both copies of bodies differ is not well defined.
388 We replace the old body with new body so in unit at a time mode
389 we always use new body, while in normal mode we may end up with
390 old body inlined into some functions and new body expanded and
393 ??? It may make more sense to use one body for inlining and other
394 body for expanding the function but this is difficult to do. */
396 /* If node->output is set, then this is a unit-at-a-time compilation
397 and we have already begun whole-unit analysis. This is *not*
398 testing for whether we've already emitted the function. That
399 case can be sort-of legitimately seen with real function
400 redefinition errors. I would argue that the front end should
401 never present us with such a case, but don't enforce that for now. */
402 gcc_assert (!node
->output
);
404 /* Reset our data structures so we can analyze the function again. */
405 memset (&node
->local
, 0, sizeof (node
->local
));
406 memset (&node
->global
, 0, sizeof (node
->global
));
407 memset (&node
->rtl
, 0, sizeof (node
->rtl
));
408 node
->analyzed
= false;
409 node
->local
.redefined_extern_inline
= true;
411 if (!flag_unit_at_a_time
)
413 struct cgraph_node
*n
;
415 for (n
= cgraph_nodes
; n
; n
= n
->next
)
416 if (n
->global
.inlined_to
== node
)
417 cgraph_remove_node (n
);
420 cgraph_node_remove_callees (node
);
422 /* We may need to re-queue the node for assembling in case
423 we already proceeded it and ignored as not needed. */
424 if (node
->reachable
&& !flag_unit_at_a_time
)
426 struct cgraph_node
*n
;
428 for (n
= cgraph_nodes_queue
; n
; n
= n
->next_needed
)
436 notice_global_symbol (decl
);
438 node
->local
.finalized
= true;
440 lower_nested_functions (decl
);
441 gcc_assert (!node
->nested
);
443 /* If not unit at a time, then we need to create the call graph
444 now, so that called functions can be queued and emitted now. */
445 if (!flag_unit_at_a_time
)
447 cgraph_analyze_function (node
);
448 cgraph_decide_inlining_incrementally (node
);
451 if (decide_is_function_needed (node
, decl
))
452 cgraph_mark_needed_node (node
);
454 /* If not unit at a time, go ahead and emit everything we've found
455 to be reachable at this time. */
458 if (!cgraph_assemble_pending_functions ())
462 /* If we've not yet emitted decl, tell the debug info about it. */
463 if (!TREE_ASM_WRITTEN (decl
))
464 (*debug_hooks
->deferred_inline_function
) (decl
);
466 /* Possibly warn about unused parameters. */
467 if (warn_unused_parameter
)
468 do_warn_unused_parameter (decl
);
471 /* Walk tree and record all calls. Called via walk_tree. */
473 record_call_1 (tree
*tp
, int *walk_subtrees
, void *data
)
477 switch (TREE_CODE (t
))
480 /* ??? Really, we should mark this decl as *potentially* referenced
481 by this function and re-examine whether the decl is actually used
482 after rtl has been generated. */
483 if (TREE_STATIC (t
) || DECL_EXTERNAL (t
))
485 cgraph_varpool_mark_needed_node (cgraph_varpool_node (t
));
486 if (lang_hooks
.callgraph
.analyze_expr
)
487 return lang_hooks
.callgraph
.analyze_expr (tp
, walk_subtrees
,
494 if (flag_unit_at_a_time
)
496 /* Record dereferences to the functions. This makes the
497 functions reachable unconditionally. */
498 tree decl
= TREE_OPERAND (*tp
, 0);
499 if (TREE_CODE (decl
) == FUNCTION_DECL
)
500 cgraph_mark_needed_node (cgraph_node (decl
));
506 tree decl
= get_callee_fndecl (*tp
);
507 if (decl
&& TREE_CODE (decl
) == FUNCTION_DECL
)
509 cgraph_create_edge (data
, cgraph_node (decl
), *tp
);
511 /* When we see a function call, we don't want to look at the
512 function reference in the ADDR_EXPR that is hanging from
513 the CALL_EXPR we're examining here, because we would
514 conclude incorrectly that the function's address could be
515 taken by something that is not a function call. So only
516 walk the function parameter list, skip the other subtrees. */
518 walk_tree (&TREE_OPERAND (*tp
, 1), record_call_1
, data
,
526 /* Save some cycles by not walking types and declaration as we
527 won't find anything useful there anyway. */
528 if (IS_TYPE_OR_DECL_P (*tp
))
534 if ((unsigned int) TREE_CODE (t
) >= LAST_AND_UNUSED_TREE_CODE
)
535 return lang_hooks
.callgraph
.analyze_expr (tp
, walk_subtrees
, data
);
542 /* Create cgraph edges for function calls inside BODY from NODE. */
545 cgraph_create_edges (struct cgraph_node
*node
, tree body
)
547 /* The nodes we're interested in are never shared, so walk
548 the tree ignoring duplicates. */
549 visited_nodes
= pointer_set_create ();
550 walk_tree (&body
, record_call_1
, node
, visited_nodes
);
551 pointer_set_destroy (visited_nodes
);
552 visited_nodes
= NULL
;
555 static bool error_found
;
557 /* Callback of verify_cgraph_node. Check that all call_exprs have
561 verify_cgraph_node_1 (tree
*tp
, int *walk_subtrees
, void *data
)
566 if (TREE_CODE (t
) == CALL_EXPR
&& (decl
= get_callee_fndecl (t
)))
568 struct cgraph_edge
*e
= cgraph_edge (data
, t
);
573 error ("Shared call_expr:");
577 if (e
->callee
->decl
!= cgraph_node (decl
)->decl
)
579 error ("Edge points to wrong declaration:");
580 debug_tree (e
->callee
->decl
);
581 fprintf (stderr
," Instead of:");
588 error ("Missing callgraph edge for call expr:");
594 /* Save some cycles by not walking types and declaration as we
595 won't find anything useful there anyway. */
596 if (IS_TYPE_OR_DECL_P (*tp
))
602 /* Verify cgraph nodes of given cgraph node. */
604 verify_cgraph_node (struct cgraph_node
*node
)
606 struct cgraph_edge
*e
;
607 struct cgraph_node
*main_clone
;
609 timevar_push (TV_CGRAPH_VERIFY
);
611 for (e
= node
->callees
; e
; e
= e
->next_callee
)
614 error ("Aux field set for edge %s->%s",
615 cgraph_node_name (e
->caller
), cgraph_node_name (e
->callee
));
618 for (e
= node
->callers
; e
; e
= e
->next_caller
)
620 if (!e
->inline_failed
)
622 if (node
->global
.inlined_to
623 != (e
->caller
->global
.inlined_to
624 ? e
->caller
->global
.inlined_to
: e
->caller
))
626 error ("Inlined_to pointer is wrong");
629 if (node
->callers
->next_caller
)
631 error ("Multiple inline callers");
636 if (node
->global
.inlined_to
)
638 error ("Inlined_to pointer set for noninline callers");
642 if (!node
->callers
&& node
->global
.inlined_to
)
644 error ("Inlined_to pointer is set but no predecesors found");
647 if (node
->global
.inlined_to
== node
)
649 error ("Inlined_to pointer reffers to itself");
653 for (main_clone
= cgraph_node (node
->decl
); main_clone
;
654 main_clone
= main_clone
->next_clone
)
655 if (main_clone
== node
)
659 error ("Node not found in DECL_ASSEMBLER_NAME hash");
664 && DECL_SAVED_TREE (node
->decl
) && !TREE_ASM_WRITTEN (node
->decl
)
665 && (!DECL_EXTERNAL (node
->decl
) || node
->global
.inlined_to
))
667 walk_tree_without_duplicates (&DECL_SAVED_TREE (node
->decl
),
668 verify_cgraph_node_1
, node
);
669 for (e
= node
->callees
; e
; e
= e
->next_callee
)
673 error ("Edge %s->%s has no corresponding call_expr",
674 cgraph_node_name (e
->caller
),
675 cgraph_node_name (e
->callee
));
683 dump_cgraph_node (stderr
, node
);
684 internal_error ("verify_cgraph_node failed.");
686 timevar_pop (TV_CGRAPH_VERIFY
);
689 /* Verify whole cgraph structure. */
693 struct cgraph_node
*node
;
695 if (sorrycount
|| errorcount
)
698 for (node
= cgraph_nodes
; node
; node
= node
->next
)
699 verify_cgraph_node (node
);
703 /* Output all variables enqueued to be assembled. */
705 cgraph_varpool_assemble_pending_decls (void)
707 bool changed
= false;
709 if (errorcount
|| sorrycount
)
712 /* EH might mark decls as needed during expansion. This should be safe since
713 we don't create references to new function, but it should not be used
715 cgraph_varpool_analyze_pending_decls ();
717 while (cgraph_varpool_nodes_queue
)
719 tree decl
= cgraph_varpool_nodes_queue
->decl
;
720 struct cgraph_varpool_node
*node
= cgraph_varpool_nodes_queue
;
722 cgraph_varpool_nodes_queue
= cgraph_varpool_nodes_queue
->next_needed
;
723 if (!TREE_ASM_WRITTEN (decl
) && !node
->alias
&& !DECL_EXTERNAL (decl
))
725 assemble_variable (decl
, 0, 1, 0);
728 node
->next_needed
= NULL
;
733 /* Analyze the function scheduled to be output. */
735 cgraph_analyze_function (struct cgraph_node
*node
)
737 tree decl
= node
->decl
;
738 struct cgraph_edge
*e
;
740 current_function_decl
= decl
;
742 /* First kill forward declaration so reverse inlining works properly. */
743 cgraph_create_edges (node
, DECL_SAVED_TREE (decl
));
745 node
->local
.inlinable
= tree_inlinable_function_p (decl
);
746 node
->local
.self_insns
= estimate_num_insns (DECL_SAVED_TREE (decl
));
747 if (node
->local
.inlinable
)
748 node
->local
.disregard_inline_limits
749 = lang_hooks
.tree_inlining
.disregard_inline_limits (decl
);
750 for (e
= node
->callers
; e
; e
= e
->next_caller
)
752 if (node
->local
.redefined_extern_inline
)
753 e
->inline_failed
= N_("redefined extern inline functions are not "
754 "considered for inlining");
755 else if (!node
->local
.inlinable
)
756 e
->inline_failed
= N_("function not inlinable");
758 e
->inline_failed
= N_("function not considered for inlining");
760 if (flag_really_no_inline
&& !node
->local
.disregard_inline_limits
)
761 node
->local
.inlinable
= 0;
762 /* Inlining characteristics are maintained by the cgraph_mark_inline. */
763 node
->global
.insns
= node
->local
.self_insns
;
765 node
->analyzed
= true;
766 current_function_decl
= NULL
;
769 /* Analyze the whole compilation unit once it is parsed completely. */
772 cgraph_finalize_compilation_unit (void)
774 struct cgraph_node
*node
;
775 /* Keep track of already processed nodes when called multiple times for
776 intermodule optimization. */
777 static struct cgraph_node
*first_analyzed
;
781 if (!flag_unit_at_a_time
)
783 cgraph_assemble_pending_functions ();
789 fprintf (stderr
, "\nAnalyzing compilation unit");
793 timevar_push (TV_CGRAPH
);
794 cgraph_varpool_analyze_pending_decls ();
795 if (cgraph_dump_file
)
797 fprintf (cgraph_dump_file
, "Initial entry points:");
798 for (node
= cgraph_nodes
; node
!= first_analyzed
; node
= node
->next
)
799 if (node
->needed
&& DECL_SAVED_TREE (node
->decl
))
800 fprintf (cgraph_dump_file
, " %s", cgraph_node_name (node
));
801 fprintf (cgraph_dump_file
, "\n");
804 /* Propagate reachability flag and lower representation of all reachable
805 functions. In the future, lowering will introduce new functions and
806 new entry points on the way (by template instantiation and virtual
807 method table generation for instance). */
808 while (cgraph_nodes_queue
)
810 struct cgraph_edge
*edge
;
811 tree decl
= cgraph_nodes_queue
->decl
;
813 node
= cgraph_nodes_queue
;
814 cgraph_nodes_queue
= cgraph_nodes_queue
->next_needed
;
815 node
->next_needed
= NULL
;
817 /* ??? It is possible to create extern inline function and later using
818 weak alas attribute to kill its body. See
819 gcc.c-torture/compile/20011119-1.c */
820 if (!DECL_SAVED_TREE (decl
))
823 gcc_assert (!node
->analyzed
&& node
->reachable
);
824 gcc_assert (DECL_SAVED_TREE (decl
));
826 cgraph_analyze_function (node
);
828 for (edge
= node
->callees
; edge
; edge
= edge
->next_callee
)
829 if (!edge
->callee
->reachable
)
830 cgraph_mark_reachable_node (edge
->callee
);
832 cgraph_varpool_analyze_pending_decls ();
835 /* Collect entry points to the unit. */
837 if (cgraph_dump_file
)
839 fprintf (cgraph_dump_file
, "Unit entry points:");
840 for (node
= cgraph_nodes
; node
!= first_analyzed
; node
= node
->next
)
841 if (node
->needed
&& DECL_SAVED_TREE (node
->decl
))
842 fprintf (cgraph_dump_file
, " %s", cgraph_node_name (node
));
843 fprintf (cgraph_dump_file
, "\n\nInitial ");
844 dump_cgraph (cgraph_dump_file
);
847 if (cgraph_dump_file
)
848 fprintf (cgraph_dump_file
, "\nReclaiming functions:");
850 for (node
= cgraph_nodes
; node
!= first_analyzed
; node
= node
->next
)
852 tree decl
= node
->decl
;
854 if (!node
->reachable
&& DECL_SAVED_TREE (decl
))
856 if (cgraph_dump_file
)
857 fprintf (cgraph_dump_file
, " %s", cgraph_node_name (node
));
858 cgraph_remove_node (node
);
861 node
->next_needed
= NULL
;
863 if (cgraph_dump_file
)
865 fprintf (cgraph_dump_file
, "\n\nReclaimed ");
866 dump_cgraph (cgraph_dump_file
);
868 first_analyzed
= cgraph_nodes
;
870 timevar_pop (TV_CGRAPH
);
872 /* Figure out what functions we want to assemble. */
875 cgraph_mark_functions_to_output (void)
877 struct cgraph_node
*node
;
879 for (node
= cgraph_nodes
; node
; node
= node
->next
)
881 tree decl
= node
->decl
;
882 struct cgraph_edge
*e
;
884 gcc_assert (!node
->output
);
886 for (e
= node
->callers
; e
; e
= e
->next_caller
)
887 if (e
->inline_failed
)
890 /* We need to output all local functions that are used and not
891 always inlined, as well as those that are reachable from
892 outside the current compilation unit. */
893 if (DECL_SAVED_TREE (decl
)
894 && !node
->global
.inlined_to
896 || (e
&& node
->reachable
))
897 && !TREE_ASM_WRITTEN (decl
)
898 && !DECL_EXTERNAL (decl
))
902 /* We should've reclaimed all functions that are not needed. */
903 #ifdef ENABLE_CHECKING
904 if (!node
->global
.inlined_to
&& DECL_SAVED_TREE (decl
)
905 && !DECL_EXTERNAL (decl
))
907 dump_cgraph_node (stderr
, node
);
908 internal_error ("failed to reclaim unneeded function");
911 gcc_assert (node
->global
.inlined_to
|| !DECL_SAVED_TREE (decl
)
912 || DECL_EXTERNAL (decl
));
919 /* Expand function specified by NODE. */
922 cgraph_expand_function (struct cgraph_node
*node
)
924 tree decl
= node
->decl
;
926 /* We ought to not compile any inline clones. */
927 gcc_assert (!node
->global
.inlined_to
);
929 if (flag_unit_at_a_time
)
930 announce_function (decl
);
932 /* Generate RTL for the body of DECL. */
933 lang_hooks
.callgraph
.expand_function (decl
);
935 /* Make sure that BE didn't give up on compiling. */
936 /* ??? Can happen with nested function of extern inline. */
937 gcc_assert (TREE_ASM_WRITTEN (node
->decl
));
939 current_function_decl
= NULL
;
940 if (!cgraph_preserve_function_body_p (node
->decl
))
942 DECL_SAVED_TREE (node
->decl
) = NULL
;
943 DECL_STRUCT_FUNCTION (node
->decl
) = NULL
;
944 DECL_INITIAL (node
->decl
) = error_mark_node
;
945 /* Eliminate all call edges. This is important so the call_expr no longer
946 points to the dead function body. */
947 cgraph_node_remove_callees (node
);
951 /* Fill array order with all nodes with output flag set in the reverse
952 topological order. */
955 cgraph_postorder (struct cgraph_node
**order
)
957 struct cgraph_node
*node
, *node2
;
960 struct cgraph_edge
*edge
, last
;
962 struct cgraph_node
**stack
=
963 xcalloc (cgraph_n_nodes
, sizeof (struct cgraph_node
*));
965 /* We have to deal with cycles nicely, so use a depth first traversal
966 output algorithm. Ignore the fact that some functions won't need
967 to be output and put them into order as well, so we get dependencies
968 right through intline functions. */
969 for (node
= cgraph_nodes
; node
; node
= node
->next
)
971 for (node
= cgraph_nodes
; node
; node
= node
->next
)
978 node
->aux
= node
->callers
;
981 while (node2
->aux
!= &last
)
984 if (edge
->next_caller
)
985 node2
->aux
= edge
->next_caller
;
988 if (!edge
->caller
->aux
)
990 if (!edge
->caller
->callers
)
991 edge
->caller
->aux
= &last
;
993 edge
->caller
->aux
= edge
->caller
->callers
;
994 stack
[stack_size
++] = node2
;
995 node2
= edge
->caller
;
999 if (node2
->aux
== &last
)
1001 order
[order_pos
++] = node2
;
1003 node2
= stack
[--stack_size
];
1014 /* Perform reachability analysis and reclaim all unreachable nodes.
1015 This function also remove unneeded bodies of extern inline functions
1016 and thus needs to be done only after inlining decisions has been made. */
1018 cgraph_remove_unreachable_nodes (void)
1020 struct cgraph_node
*first
= (void *) 1;
1021 struct cgraph_node
*node
;
1022 bool changed
= false;
1025 #ifdef ENABLE_CHECKING
1028 if (cgraph_dump_file
)
1029 fprintf (cgraph_dump_file
, "\nReclaiming functions:");
1030 #ifdef ENABLE_CHECKING
1031 for (node
= cgraph_nodes
; node
; node
= node
->next
)
1032 gcc_assert (!node
->aux
);
1034 for (node
= cgraph_nodes
; node
; node
= node
->next
)
1035 if (node
->needed
&& !node
->global
.inlined_to
1036 && (!DECL_EXTERNAL (node
->decl
) || !node
->analyzed
))
1042 gcc_assert (!node
->aux
);
1044 /* Perform reachability analysis. As a special case do not consider
1045 extern inline functions not inlined as live because we won't output
1047 while (first
!= (void *) 1)
1049 struct cgraph_edge
*e
;
1053 for (e
= node
->callees
; e
; e
= e
->next_callee
)
1056 && (!e
->inline_failed
|| !e
->callee
->analyzed
1057 || !DECL_EXTERNAL (e
->callee
->decl
)))
1059 e
->callee
->aux
= first
;
1064 /* Remove unreachable nodes. Extern inline functions need special care;
1065 Unreachable extern inline functions shall be removed.
1066 Reachable extern inline functions we never inlined shall get their bodies
1068 Reachable extern inline functions we sometimes inlined will be turned into
1069 unanalyzed nodes so they look like for true extern functions to the rest
1070 of code. Body of such functions is released via remove_node once the
1071 inline clones are eliminated. */
1072 for (node
= cgraph_nodes
; node
; node
= node
->next
)
1077 tree decl
= node
->decl
;
1079 node
->global
.inlined_to
= NULL
;
1080 if (DECL_STRUCT_FUNCTION (decl
))
1081 local_insns
= node
->local
.self_insns
;
1084 if (cgraph_dump_file
)
1085 fprintf (cgraph_dump_file
, " %s", cgraph_node_name (node
));
1086 if (!node
->analyzed
|| !DECL_EXTERNAL (node
->decl
))
1087 cgraph_remove_node (node
);
1090 struct cgraph_edge
*e
;
1092 for (e
= node
->callers
; e
; e
= e
->next_caller
)
1095 if (e
|| node
->needed
)
1097 struct cgraph_node
*clone
;
1099 for (clone
= node
->next_clone
; clone
;
1100 clone
= clone
->next_clone
)
1105 DECL_SAVED_TREE (node
->decl
) = NULL
;
1106 DECL_STRUCT_FUNCTION (node
->decl
) = NULL
;
1107 DECL_INITIAL (node
->decl
) = error_mark_node
;
1109 cgraph_node_remove_callees (node
);
1110 node
->analyzed
= false;
1113 cgraph_remove_node (node
);
1115 if (!DECL_SAVED_TREE (decl
))
1116 insns
+= local_insns
;
1120 for (node
= cgraph_nodes
; node
; node
= node
->next
)
1122 if (cgraph_dump_file
)
1123 fprintf (cgraph_dump_file
, "\nReclaimed %i insns", insns
);
1127 /* Estimate size of the function after inlining WHAT into TO. */
1130 cgraph_estimate_size_after_inlining (int times
, struct cgraph_node
*to
,
1131 struct cgraph_node
*what
)
1133 tree fndecl
= what
->decl
;
1135 int call_insns
= PARAM_VALUE (PARAM_INLINE_CALL_COST
);
1136 for (arg
= DECL_ARGUMENTS (fndecl
); arg
; arg
= TREE_CHAIN (arg
))
1137 call_insns
+= estimate_move_cost (TREE_TYPE (arg
));
1138 return (what
->global
.insns
- call_insns
) * times
+ to
->global
.insns
;
1141 /* Estimate the growth caused by inlining NODE into all callees. */
1144 cgraph_estimate_growth (struct cgraph_node
*node
)
1147 struct cgraph_edge
*e
;
1149 for (e
= node
->callers
; e
; e
= e
->next_caller
)
1150 if (e
->inline_failed
)
1151 growth
+= (cgraph_estimate_size_after_inlining (1, e
->caller
, node
)
1152 - e
->caller
->global
.insns
);
1154 /* ??? Wrong for self recursive functions or cases where we decide to not
1155 inline for different reasons, but it is not big deal as in that case
1156 we will keep the body around, but we will also avoid some inlining. */
1157 if (!node
->needed
&& !DECL_EXTERNAL (node
->decl
))
1158 growth
-= node
->global
.insns
;
1163 /* E is expected to be an edge being inlined. Clone destination node of
1164 the edge and redirect it to the new clone.
1165 DUPLICATE is used for bookkeeping on whether we are actually creating new
1166 clones or re-using node originally representing out-of-line function call.
1169 cgraph_clone_inlined_nodes (struct cgraph_edge
*e
, bool duplicate
)
1171 struct cgraph_node
*n
;
1173 /* We may eliminate the need for out-of-line copy to be output. In that
1174 case just go ahead and re-use it. */
1175 if (!e
->callee
->callers
->next_caller
1176 && (!e
->callee
->needed
|| DECL_EXTERNAL (e
->callee
->decl
))
1178 && flag_unit_at_a_time
)
1180 gcc_assert (!e
->callee
->global
.inlined_to
);
1181 if (!DECL_EXTERNAL (e
->callee
->decl
))
1182 overall_insns
-= e
->callee
->global
.insns
, nfunctions_inlined
++;
1187 n
= cgraph_clone_node (e
->callee
);
1188 cgraph_redirect_edge_callee (e
, n
);
1191 if (e
->caller
->global
.inlined_to
)
1192 e
->callee
->global
.inlined_to
= e
->caller
->global
.inlined_to
;
1194 e
->callee
->global
.inlined_to
= e
->caller
;
1196 /* Recursively clone all bodies. */
1197 for (e
= e
->callee
->callees
; e
; e
= e
->next_callee
)
1198 if (!e
->inline_failed
)
1199 cgraph_clone_inlined_nodes (e
, duplicate
);
1202 /* Mark edge E as inlined and update callgraph accordingly. */
1205 cgraph_mark_inline_edge (struct cgraph_edge
*e
)
1207 int old_insns
= 0, new_insns
= 0;
1208 struct cgraph_node
*to
= NULL
, *what
;
1210 gcc_assert (e
->inline_failed
);
1211 e
->inline_failed
= NULL
;
1213 if (!e
->callee
->global
.inlined
&& flag_unit_at_a_time
)
1214 DECL_POSSIBLY_INLINED (e
->callee
->decl
) = true;
1215 e
->callee
->global
.inlined
= true;
1217 cgraph_clone_inlined_nodes (e
, true);
1221 /* Now update size of caller and all functions caller is inlined into. */
1222 for (;e
&& !e
->inline_failed
; e
= e
->caller
->callers
)
1224 old_insns
= e
->caller
->global
.insns
;
1225 new_insns
= cgraph_estimate_size_after_inlining (1, e
->caller
,
1227 gcc_assert (new_insns
>= 0);
1229 to
->global
.insns
= new_insns
;
1231 gcc_assert (what
->global
.inlined_to
== to
);
1232 if (new_insns
> old_insns
)
1233 overall_insns
+= new_insns
- old_insns
;
1237 /* Mark all calls of EDGE->CALLEE inlined into EDGE->CALLER.
1238 Return following unredirected edge in the list of callers
1241 static struct cgraph_edge
*
1242 cgraph_mark_inline (struct cgraph_edge
*edge
)
1244 struct cgraph_node
*to
= edge
->caller
;
1245 struct cgraph_node
*what
= edge
->callee
;
1246 struct cgraph_edge
*e
, *next
;
1249 /* Look for all calls, mark them inline and clone recursively
1250 all inlined functions. */
1251 for (e
= what
->callers
; e
; e
= next
)
1253 next
= e
->next_caller
;
1254 if (e
->caller
== to
&& e
->inline_failed
)
1256 cgraph_mark_inline_edge (e
);
1266 /* Return false when inlining WHAT into TO is not good idea
1267 as it would cause too large growth of function bodies. */
1270 cgraph_check_inline_limits (struct cgraph_node
*to
, struct cgraph_node
*what
,
1271 const char **reason
)
1274 struct cgraph_edge
*e
;
1278 if (to
->global
.inlined_to
)
1279 to
= to
->global
.inlined_to
;
1281 for (e
= to
->callees
; e
; e
= e
->next_callee
)
1282 if (e
->callee
== what
)
1285 /* When inlining large function body called once into small function,
1286 take the inlined function as base for limiting the growth. */
1287 if (to
->local
.self_insns
> what
->local
.self_insns
)
1288 limit
= to
->local
.self_insns
;
1290 limit
= what
->local
.self_insns
;
1292 limit
+= limit
* PARAM_VALUE (PARAM_LARGE_FUNCTION_GROWTH
) / 100;
1294 newsize
= cgraph_estimate_size_after_inlining (times
, to
, what
);
1295 if (newsize
> PARAM_VALUE (PARAM_LARGE_FUNCTION_INSNS
)
1299 *reason
= N_("--param large-function-growth limit reached");
1305 /* Return true when function N is small enough to be inlined. */
1308 cgraph_default_inline_p (struct cgraph_node
*n
)
1310 if (!DECL_INLINE (n
->decl
) || !DECL_SAVED_TREE (n
->decl
))
1312 if (DECL_DECLARED_INLINE_P (n
->decl
))
1313 return n
->global
.insns
< MAX_INLINE_INSNS_SINGLE
;
1315 return n
->global
.insns
< MAX_INLINE_INSNS_AUTO
;
1318 /* Return true when inlining WHAT would create recursive inlining.
1319 We call recursive inlining all cases where same function appears more than
1320 once in the single recursion nest path in the inline graph. */
1323 cgraph_recursive_inlining_p (struct cgraph_node
*to
,
1324 struct cgraph_node
*what
,
1325 const char **reason
)
1328 if (to
->global
.inlined_to
)
1329 recursive
= what
->decl
== to
->global
.inlined_to
->decl
;
1331 recursive
= what
->decl
== to
->decl
;
1332 /* Marking recursive function inline has sane semantic and thus we should
1334 if (recursive
&& reason
)
1335 *reason
= (what
->local
.disregard_inline_limits
1336 ? N_("recursive inlining") : "");
1340 /* Recompute heap nodes for each of callees. */
1342 update_callee_keys (fibheap_t heap
, struct fibnode
**heap_node
,
1343 struct cgraph_node
*node
)
1345 struct cgraph_edge
*e
;
1347 for (e
= node
->callees
; e
; e
= e
->next_callee
)
1348 if (e
->inline_failed
&& heap_node
[e
->callee
->uid
])
1349 fibheap_replace_key (heap
, heap_node
[e
->callee
->uid
],
1350 cgraph_estimate_growth (e
->callee
));
1351 else if (!e
->inline_failed
)
1352 update_callee_keys (heap
, heap_node
, e
->callee
);
1355 /* Enqueue all recursive calls from NODE into queue linked via aux pointers
1356 in between FIRST and LAST. WHERE is used for bookkeeping while looking
1357 int calls inlined within NODE. */
1359 lookup_recursive_calls (struct cgraph_node
*node
, struct cgraph_node
*where
,
1360 struct cgraph_edge
**first
, struct cgraph_edge
**last
)
1362 struct cgraph_edge
*e
;
1363 for (e
= where
->callees
; e
; e
= e
->next_callee
)
1364 if (e
->callee
== node
)
1372 for (e
= where
->callees
; e
; e
= e
->next_callee
)
1373 if (!e
->inline_failed
)
1374 lookup_recursive_calls (node
, e
->callee
, first
, last
);
1377 /* Decide on recursive inlining: in the case function has recursive calls,
1378 inline until body size reaches given argument. */
1380 cgraph_decide_recursive_inlining (struct cgraph_node
*node
)
1382 int limit
= PARAM_VALUE (PARAM_MAX_INLINE_INSNS_RECURSIVE_AUTO
);
1383 int max_depth
= PARAM_VALUE (PARAM_MAX_INLINE_RECURSIVE_DEPTH_AUTO
);
1384 struct cgraph_edge
*first_call
= NULL
, *last_call
= NULL
;
1385 struct cgraph_edge
*last_in_current_depth
;
1386 struct cgraph_edge
*e
;
1387 struct cgraph_node
*master_clone
;
1391 if (DECL_DECLARED_INLINE_P (node
->decl
))
1393 limit
= PARAM_VALUE (PARAM_MAX_INLINE_INSNS_RECURSIVE
);
1394 max_depth
= PARAM_VALUE (PARAM_MAX_INLINE_RECURSIVE_DEPTH
);
1397 /* Make sure that function is small enough to be considered for inlining. */
1399 || cgraph_estimate_size_after_inlining (1, node
, node
) >= limit
)
1401 lookup_recursive_calls (node
, node
, &first_call
, &last_call
);
1405 if (cgraph_dump_file
)
1406 fprintf (cgraph_dump_file
,
1407 "\nPerforming recursive inlining on %s\n",
1408 cgraph_node_name (node
));
1410 /* We need original clone to copy around. */
1411 master_clone
= cgraph_clone_node (node
);
1412 master_clone
->needed
= true;
1413 for (e
= master_clone
->callees
; e
; e
= e
->next_callee
)
1414 if (!e
->inline_failed
)
1415 cgraph_clone_inlined_nodes (e
, true);
1417 /* Do the inlining and update list of recursive call during process. */
1418 last_in_current_depth
= last_call
;
1420 && cgraph_estimate_size_after_inlining (1, node
, master_clone
) <= limit
)
1422 struct cgraph_edge
*curr
= first_call
;
1424 first_call
= first_call
->aux
;
1427 cgraph_redirect_edge_callee (curr
, master_clone
);
1428 cgraph_mark_inline_edge (curr
);
1429 lookup_recursive_calls (node
, curr
->callee
, &first_call
, &last_call
);
1431 if (last_in_current_depth
1432 && ++depth
>= max_depth
)
1437 /* Cleanup queue pointers. */
1440 struct cgraph_edge
*next
= first_call
->aux
;
1441 first_call
->aux
= NULL
;
1444 if (cgraph_dump_file
)
1445 fprintf (cgraph_dump_file
,
1446 "\n Inlined %i times, body grown from %i to %i insns\n", n
,
1447 master_clone
->global
.insns
, node
->global
.insns
);
1449 /* Remove master clone we used for inlining. We rely that clones inlined
1450 into master clone gets queued just before master clone so we don't
1452 for (node
= cgraph_nodes
; node
!= master_clone
;
1454 if (node
->global
.inlined_to
== master_clone
)
1455 cgraph_remove_node (node
);
1456 cgraph_remove_node (master_clone
);
1459 /* Set inline_failed for all callers of given function to REASON. */
1462 cgraph_set_inline_failed (struct cgraph_node
*node
, const char *reason
)
1464 struct cgraph_edge
*e
;
1466 if (cgraph_dump_file
)
1467 fprintf (cgraph_dump_file
, "Inlining failed: %s\n", reason
);
1468 for (e
= node
->callers
; e
; e
= e
->next_caller
)
1469 if (e
->inline_failed
)
1470 e
->inline_failed
= reason
;
1473 /* We use greedy algorithm for inlining of small functions:
1474 All inline candidates are put into prioritized heap based on estimated
1475 growth of the overall number of instructions and then update the estimates.
1477 INLINED and INLINED_CALEES are just pointers to arrays large enough
1478 to be passed to cgraph_inlined_into and cgraph_inlined_callees. */
1481 cgraph_decide_inlining_of_small_functions (void)
1483 struct cgraph_node
*node
;
1484 fibheap_t heap
= fibheap_new ();
1485 struct fibnode
**heap_node
=
1486 xcalloc (cgraph_max_uid
, sizeof (struct fibnode
*));
1487 int max_insns
= ((HOST_WIDEST_INT
) initial_insns
1488 * (100 + PARAM_VALUE (PARAM_INLINE_UNIT_GROWTH
)) / 100);
1490 /* Put all inline candidates into the heap. */
1492 for (node
= cgraph_nodes
; node
; node
= node
->next
)
1494 if (!node
->local
.inlinable
|| !node
->callers
1495 || node
->local
.disregard_inline_limits
)
1498 if (!cgraph_default_inline_p (node
))
1500 cgraph_set_inline_failed (node
,
1501 N_("--param max-inline-insns-single limit reached"));
1504 heap_node
[node
->uid
] =
1505 fibheap_insert (heap
, cgraph_estimate_growth (node
), node
);
1508 if (cgraph_dump_file
)
1509 fprintf (cgraph_dump_file
, "\nDeciding on smaller functions:\n");
1510 while (overall_insns
<= max_insns
&& (node
= fibheap_extract_min (heap
)))
1512 struct cgraph_edge
*e
, *next
;
1513 int old_insns
= overall_insns
;
1515 heap_node
[node
->uid
] = NULL
;
1516 if (cgraph_dump_file
)
1517 fprintf (cgraph_dump_file
,
1518 "\nConsidering %s with %i insns\n"
1519 " Estimated growth is %+i insns.\n",
1520 cgraph_node_name (node
), node
->global
.insns
,
1521 cgraph_estimate_growth (node
));
1522 if (!cgraph_default_inline_p (node
))
1524 cgraph_set_inline_failed (node
,
1525 N_("--param max-inline-insns-single limit reached after inlining into the callee"));
1528 for (e
= node
->callers
; e
; e
= next
)
1530 next
= e
->next_caller
;
1531 if (e
->inline_failed
)
1533 struct cgraph_node
*where
;
1535 if (cgraph_recursive_inlining_p (e
->caller
, e
->callee
,
1537 || !cgraph_check_inline_limits (e
->caller
, e
->callee
,
1540 if (cgraph_dump_file
)
1541 fprintf (cgraph_dump_file
, " Not inlining into %s:%s.\n",
1542 cgraph_node_name (e
->caller
), e
->inline_failed
);
1545 next
= cgraph_mark_inline (e
);
1547 if (where
->global
.inlined_to
)
1548 where
= where
->global
.inlined_to
;
1550 if (heap_node
[where
->uid
])
1551 fibheap_replace_key (heap
, heap_node
[where
->uid
],
1552 cgraph_estimate_growth (where
));
1554 if (cgraph_dump_file
)
1555 fprintf (cgraph_dump_file
,
1556 " Inlined into %s which now has %i insns.\n",
1557 cgraph_node_name (e
->caller
),
1558 e
->caller
->global
.insns
);
1562 cgraph_decide_recursive_inlining (node
);
1564 /* Similarly all functions called by the function we just inlined
1565 are now called more times; update keys. */
1566 update_callee_keys (heap
, heap_node
, node
);
1568 if (cgraph_dump_file
)
1569 fprintf (cgraph_dump_file
,
1570 " Inlined for a net change of %+i insns.\n",
1571 overall_insns
- old_insns
);
1573 while ((node
= fibheap_extract_min (heap
)) != NULL
)
1574 if (!node
->local
.disregard_inline_limits
)
1575 cgraph_set_inline_failed (node
, N_("--param inline-unit-growth limit reached"));
1576 fibheap_delete (heap
);
1580 /* Decide on the inlining. We do so in the topological order to avoid
1581 expenses on updating data structures. */
1584 cgraph_decide_inlining (void)
1586 struct cgraph_node
*node
;
1588 struct cgraph_node
**order
=
1589 xcalloc (cgraph_n_nodes
, sizeof (struct cgraph_node
*));
1593 for (node
= cgraph_nodes
; node
; node
= node
->next
)
1594 initial_insns
+= node
->local
.self_insns
;
1595 overall_insns
= initial_insns
;
1597 nnodes
= cgraph_postorder (order
);
1599 if (cgraph_dump_file
)
1600 fprintf (cgraph_dump_file
,
1601 "\nDeciding on inlining. Starting with %i insns.\n",
1604 for (node
= cgraph_nodes
; node
; node
= node
->next
)
1607 if (cgraph_dump_file
)
1608 fprintf (cgraph_dump_file
, "\nInlining always_inline functions:\n");
1610 /* In the first pass mark all always_inline edges. Do this with a priority
1611 so none of our later choices will make this impossible. */
1612 for (i
= nnodes
- 1; i
>= 0; i
--)
1614 struct cgraph_edge
*e
, *next
;
1618 if (!node
->local
.disregard_inline_limits
)
1620 if (cgraph_dump_file
)
1621 fprintf (cgraph_dump_file
,
1622 "\nConsidering %s %i insns (always inline)\n",
1623 cgraph_node_name (node
), node
->global
.insns
);
1624 old_insns
= overall_insns
;
1625 for (e
= node
->callers
; e
; e
= next
)
1627 next
= e
->next_caller
;
1628 if (!e
->inline_failed
)
1630 if (cgraph_recursive_inlining_p (e
->caller
, e
->callee
,
1633 cgraph_mark_inline_edge (e
);
1634 if (cgraph_dump_file
)
1635 fprintf (cgraph_dump_file
,
1636 " Inlined into %s which now has %i insns.\n",
1637 cgraph_node_name (e
->caller
),
1638 e
->caller
->global
.insns
);
1640 if (cgraph_dump_file
)
1641 fprintf (cgraph_dump_file
,
1642 " Inlined for a net change of %+i insns.\n",
1643 overall_insns
- old_insns
);
1646 if (!flag_really_no_inline
)
1648 cgraph_decide_inlining_of_small_functions ();
1650 if (cgraph_dump_file
)
1651 fprintf (cgraph_dump_file
, "\nDeciding on functions called once:\n");
1653 /* And finally decide what functions are called once. */
1655 for (i
= nnodes
- 1; i
>= 0; i
--)
1659 if (node
->callers
&& !node
->callers
->next_caller
&& !node
->needed
1660 && node
->local
.inlinable
&& node
->callers
->inline_failed
1661 && !DECL_EXTERNAL (node
->decl
) && !DECL_COMDAT (node
->decl
))
1664 struct cgraph_node
*node1
;
1666 /* Verify that we won't duplicate the caller. */
1667 for (node1
= node
->callers
->caller
;
1668 node1
->callers
&& !node1
->callers
->inline_failed
1669 && ok
; node1
= node1
->callers
->caller
)
1670 if (node1
->callers
->next_caller
|| node1
->needed
)
1674 if (cgraph_dump_file
)
1675 fprintf (cgraph_dump_file
,
1676 "\nConsidering %s %i insns.\n"
1677 " Called once from %s %i insns.\n",
1678 cgraph_node_name (node
), node
->global
.insns
,
1679 cgraph_node_name (node
->callers
->caller
),
1680 node
->callers
->caller
->global
.insns
);
1682 old_insns
= overall_insns
;
1684 if (cgraph_check_inline_limits (node
->callers
->caller
, node
,
1687 cgraph_mark_inline (node
->callers
);
1688 if (cgraph_dump_file
)
1689 fprintf (cgraph_dump_file
,
1690 " Inlined into %s which now has %i insns"
1691 " for a net change of %+i insns.\n",
1692 cgraph_node_name (node
->callers
->caller
),
1693 node
->callers
->caller
->global
.insns
,
1694 overall_insns
- old_insns
);
1698 if (cgraph_dump_file
)
1699 fprintf (cgraph_dump_file
,
1700 " Inline limit reached, not inlined.\n");
1707 /* We will never output extern functions we didn't inline.
1708 ??? Perhaps we can prevent accounting of growth of external
1709 inline functions. */
1710 cgraph_remove_unreachable_nodes ();
1712 if (cgraph_dump_file
)
1713 fprintf (cgraph_dump_file
,
1714 "\nInlined %i calls, eliminated %i functions, "
1715 "%i insns turned to %i insns.\n\n",
1716 ncalls_inlined
, nfunctions_inlined
, initial_insns
,
1721 /* Decide on the inlining. We do so in the topological order to avoid
1722 expenses on updating data structures. */
1725 cgraph_decide_inlining_incrementally (struct cgraph_node
*node
)
1727 struct cgraph_edge
*e
;
1729 /* First of all look for always inline functions. */
1730 for (e
= node
->callees
; e
; e
= e
->next_callee
)
1731 if (e
->callee
->local
.disregard_inline_limits
1733 && !cgraph_recursive_inlining_p (node
, e
->callee
, &e
->inline_failed
)
1734 /* ??? It is possible that renaming variable removed the function body
1735 in duplicate_decls. See gcc.c-torture/compile/20011119-2.c */
1736 && DECL_SAVED_TREE (e
->callee
->decl
))
1737 cgraph_mark_inline (e
);
1739 /* Now do the automatic inlining. */
1740 if (!flag_really_no_inline
)
1741 for (e
= node
->callees
; e
; e
= e
->next_callee
)
1742 if (e
->callee
->local
.inlinable
1744 && !e
->callee
->local
.disregard_inline_limits
1745 && !cgraph_recursive_inlining_p (node
, e
->callee
, &e
->inline_failed
)
1746 && cgraph_check_inline_limits (node
, e
->callee
, &e
->inline_failed
)
1747 && DECL_SAVED_TREE (e
->callee
->decl
))
1749 if (cgraph_default_inline_p (e
->callee
))
1750 cgraph_mark_inline (e
);
1753 = N_("--param max-inline-insns-single limit reached");
1758 /* Return true when CALLER_DECL should be inlined into CALLEE_DECL. */
1761 cgraph_inline_p (struct cgraph_edge
*e
, const char **reason
)
1763 *reason
= e
->inline_failed
;
1764 return !e
->inline_failed
;
1769 /* Expand all functions that must be output.
1771 Attempt to topologically sort the nodes so function is output when
1772 all called functions are already assembled to allow data to be
1773 propagated across the callgraph. Use a stack to get smaller distance
1774 between a function and its callees (later we may choose to use a more
1775 sophisticated algorithm for function reordering; we will likely want
1776 to use subsections to make the output functions appear in top-down
1780 cgraph_expand_all_functions (void)
1782 struct cgraph_node
*node
;
1783 struct cgraph_node
**order
=
1784 xcalloc (cgraph_n_nodes
, sizeof (struct cgraph_node
*));
1785 int order_pos
= 0, new_order_pos
= 0;
1788 order_pos
= cgraph_postorder (order
);
1789 gcc_assert (order_pos
== cgraph_n_nodes
);
1791 /* Garbage collector may remove inline clones we eliminate during
1792 optimization. So we must be sure to not reference them. */
1793 for (i
= 0; i
< order_pos
; i
++)
1794 if (order
[i
]->output
)
1795 order
[new_order_pos
++] = order
[i
];
1797 for (i
= new_order_pos
- 1; i
>= 0; i
--)
1802 gcc_assert (node
->reachable
);
1804 cgraph_expand_function (node
);
1810 /* Mark all local functions.
1812 A local function is one whose calls can occur only in the current
1813 compilation unit and all its calls are explicit, so we can change
1814 its calling convention. We simply mark all static functions whose
1815 address is not taken as local. */
1818 cgraph_mark_local_functions (void)
1820 struct cgraph_node
*node
;
1822 /* Figure out functions we want to assemble. */
1823 for (node
= cgraph_nodes
; node
; node
= node
->next
)
1825 node
->local
.local
= (!node
->needed
1826 && DECL_SAVED_TREE (node
->decl
)
1827 && !TREE_PUBLIC (node
->decl
));
1830 if (cgraph_dump_file
)
1832 fprintf (cgraph_dump_file
, "\nMarking local functions:");
1833 for (node
= cgraph_nodes
; node
; node
= node
->next
)
1834 if (node
->local
.local
)
1835 fprintf (cgraph_dump_file
, " %s", cgraph_node_name (node
));
1836 fprintf (cgraph_dump_file
, "\n\n");
1840 /* Return true when function body of DECL still needs to be kept around
1841 for later re-use. */
1843 cgraph_preserve_function_body_p (tree decl
)
1845 struct cgraph_node
*node
;
1846 /* Keep the body; we're going to dump it. */
1847 if (dump_enabled_p (TDI_tree_all
))
1849 if (!cgraph_global_info_ready
)
1850 return (DECL_INLINE (decl
) && !flag_really_no_inline
);
1851 /* Look if there is any clone around. */
1852 for (node
= cgraph_node (decl
); node
; node
= node
->next_clone
)
1853 if (node
->global
.inlined_to
)
1858 /* Perform simple optimizations based on callgraph. */
1861 cgraph_optimize (void)
1863 #ifdef ENABLE_CHECKING
1866 if (!flag_unit_at_a_time
)
1868 cgraph_varpool_assemble_pending_decls ();
1872 process_pending_assemble_externals ();
1874 /* Frontend may output common variables after the unit has been finalized.
1875 It is safe to deal with them here as they are always zero initialized. */
1876 cgraph_varpool_analyze_pending_decls ();
1878 timevar_push (TV_CGRAPHOPT
);
1880 fprintf (stderr
, "Performing intraprocedural optimizations\n");
1882 cgraph_mark_local_functions ();
1883 if (cgraph_dump_file
)
1885 fprintf (cgraph_dump_file
, "Marked ");
1886 dump_cgraph (cgraph_dump_file
);
1889 if (flag_inline_trees
)
1890 cgraph_decide_inlining ();
1891 cgraph_global_info_ready
= true;
1892 if (cgraph_dump_file
)
1894 fprintf (cgraph_dump_file
, "Optimized ");
1895 dump_cgraph (cgraph_dump_file
);
1896 dump_varpool (cgraph_dump_file
);
1898 timevar_pop (TV_CGRAPHOPT
);
1900 /* Output everything. */
1902 fprintf (stderr
, "Assembling functions:\n");
1903 #ifdef ENABLE_CHECKING
1907 cgraph_mark_functions_to_output ();
1908 cgraph_expand_all_functions ();
1909 cgraph_varpool_remove_unreferenced_decls ();
1911 cgraph_varpool_assemble_pending_decls ();
1913 if (cgraph_dump_file
)
1915 fprintf (cgraph_dump_file
, "\nFinal ");
1916 dump_cgraph (cgraph_dump_file
);
1918 #ifdef ENABLE_CHECKING
1920 /* Double check that all inline clones are gone and that all
1921 function bodies have been released from memory. */
1922 if (flag_unit_at_a_time
1923 && !dump_enabled_p (TDI_tree_all
)
1924 && !(sorrycount
|| errorcount
))
1926 struct cgraph_node
*node
;
1927 bool error_found
= false;
1929 for (node
= cgraph_nodes
; node
; node
= node
->next
)
1931 && (node
->global
.inlined_to
1932 || DECL_SAVED_TREE (node
->decl
)))
1935 dump_cgraph_node (stderr
, node
);
1938 internal_error ("Nodes with no released memory found.");
1943 /* Generate and emit a static constructor or destructor. WHICH must be
1944 one of 'I' or 'D'. BODY should be a STATEMENT_LIST containing
1945 GENERIC statements. */
1948 cgraph_build_static_cdtor (char which
, tree body
, int priority
)
1950 static int counter
= 0;
1952 tree decl
, name
, resdecl
;
1954 sprintf (which_buf
, "%c_%d", which
, counter
++);
1955 name
= get_file_function_name_long (which_buf
);
1957 decl
= build_decl (FUNCTION_DECL
, name
,
1958 build_function_type (void_type_node
, void_list_node
));
1959 current_function_decl
= decl
;
1961 resdecl
= build_decl (RESULT_DECL
, NULL_TREE
, void_type_node
);
1962 DECL_ARTIFICIAL (resdecl
) = 1;
1963 DECL_IGNORED_P (resdecl
) = 1;
1964 DECL_RESULT (decl
) = resdecl
;
1966 allocate_struct_function (decl
);
1968 TREE_STATIC (decl
) = 1;
1969 TREE_USED (decl
) = 1;
1970 DECL_ARTIFICIAL (decl
) = 1;
1971 DECL_IGNORED_P (decl
) = 1;
1972 DECL_NO_INSTRUMENT_FUNCTION_ENTRY_EXIT (decl
) = 1;
1973 DECL_SAVED_TREE (decl
) = body
;
1974 TREE_PUBLIC (decl
) = ! targetm
.have_ctors_dtors
;
1975 DECL_UNINLINABLE (decl
) = 1;
1977 DECL_INITIAL (decl
) = make_node (BLOCK
);
1978 TREE_USED (DECL_INITIAL (decl
)) = 1;
1980 DECL_SOURCE_LOCATION (decl
) = input_location
;
1981 cfun
->function_end_locus
= input_location
;
1986 DECL_STATIC_CONSTRUCTOR (decl
) = 1;
1989 DECL_STATIC_DESTRUCTOR (decl
) = 1;
1995 gimplify_function_tree (decl
);
1997 /* ??? We will get called LATE in the compilation process. */
1998 if (cgraph_global_info_ready
)
1999 tree_rest_of_compilation (decl
);
2001 cgraph_finalize_function (decl
, 0);
2003 if (targetm
.have_ctors_dtors
)
2005 void (*fn
) (rtx
, int);
2008 fn
= targetm
.asm_out
.constructor
;
2010 fn
= targetm
.asm_out
.destructor
;
2011 fn (XEXP (DECL_RTL (decl
), 0), priority
);
2018 cgraph_dump_file
= dump_begin (TDI_cgraph
, NULL
);