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. */
144 #include "coretypes.h"
148 #include "tree-flow.h"
149 #include "tree-inline.h"
150 #include "langhooks.h"
151 #include "pointer-set.h"
158 #include "diagnostic.h"
162 #include "c-common.h"
164 #include "function.h"
165 #include "tree-gimple.h"
166 #include "tree-pass.h"
169 static void cgraph_expand_all_functions (void);
170 static void cgraph_mark_functions_to_output (void);
171 static void cgraph_expand_function (struct cgraph_node
*);
172 static tree
record_reference (tree
*, int *, void *);
173 static void cgraph_analyze_function (struct cgraph_node
*node
);
175 /* Records tree nodes seen in record_reference. Simply using
176 walk_tree_without_duplicates doesn't guarantee each node is visited
177 once because it gets a new htab upon each recursive call from
178 record_reference itself. */
179 static struct pointer_set_t
*visited_nodes
;
181 static FILE *cgraph_dump_file
;
183 /* Determine if function DECL is needed. That is, visible to something
184 either outside this translation unit, something magic in the system
185 configury, or (if not doing unit-at-a-time) to something we havn't
189 decide_is_function_needed (struct cgraph_node
*node
, tree decl
)
193 /* If the user told us it is used, then it must be so. */
194 if (lookup_attribute ("used", DECL_ATTRIBUTES (decl
)))
197 /* ??? If the assembler name is set by hand, it is possible to assemble
198 the name later after finalizing the function and the fact is noticed
199 in assemble_name then. This is arguably a bug. */
200 if (DECL_ASSEMBLER_NAME_SET_P (decl
)
201 && TREE_SYMBOL_REFERENCED (DECL_ASSEMBLER_NAME (decl
)))
204 /* If we decided it was needed before, but at the time we didn't have
205 the body of the function available, then it's still needed. We have
206 to go back and re-check its dependencies now. */
210 /* Externally visible functions must be output. The exception is
211 COMDAT functions that must be output only when they are needed. */
212 if (TREE_PUBLIC (decl
) && !DECL_COMDAT (decl
) && !DECL_EXTERNAL (decl
))
215 /* Constructors and destructors are reachable from the runtime by
217 if (DECL_STATIC_CONSTRUCTOR (decl
) || DECL_STATIC_DESTRUCTOR (decl
))
220 if (flag_unit_at_a_time
)
223 /* If not doing unit at a time, then we'll only defer this function
224 if its marked for inlining. Otherwise we want to emit it now. */
226 /* "extern inline" functions are never output locally. */
227 if (DECL_EXTERNAL (decl
))
229 /* Nested functions of extern inline function shall not be emit unless
230 we inlined the origin. */
231 for (origin
= decl_function_context (decl
); origin
;
232 origin
= decl_function_context (origin
))
233 if (DECL_EXTERNAL (origin
))
235 /* We want to emit COMDAT functions only when absolutely necessary. */
236 if (DECL_COMDAT (decl
))
238 if (!DECL_INLINE (decl
)
239 || (!node
->local
.disregard_inline_limits
240 /* When declared inline, defer even the uninlinable functions.
241 This allows them to be eliminated when unused. */
242 && !DECL_DECLARED_INLINE_P (decl
)
243 && (!node
->local
.inlinable
|| !cgraph_default_inline_p (node
))))
249 /* Walk the decls we marked as necessary and see if they reference new
250 variables or functions and add them into the worklists. */
252 cgraph_varpool_analyze_pending_decls (void)
254 bool changed
= false;
255 timevar_push (TV_CGRAPH
);
257 while (cgraph_varpool_first_unanalyzed_node
)
259 tree decl
= cgraph_varpool_first_unanalyzed_node
->decl
;
261 cgraph_varpool_first_unanalyzed_node
->analyzed
= true;
263 cgraph_varpool_first_unanalyzed_node
= cgraph_varpool_first_unanalyzed_node
->next_needed
;
265 if (DECL_INITIAL (decl
))
267 visited_nodes
= pointer_set_create ();
268 walk_tree (&DECL_INITIAL (decl
), record_reference
, NULL
, visited_nodes
);
269 pointer_set_destroy (visited_nodes
);
270 visited_nodes
= NULL
;
274 timevar_pop (TV_CGRAPH
);
278 /* Optimization of function bodies might've rendered some variables as
279 unnecessary so we want to avoid these from being compiled.
281 This is done by pruning the queue and keeping only the variables that
282 really appear needed (ie they are either externally visible or referenced
283 by compiled function). Re-doing the reachability analysis on variables
284 brings back the remaining variables referenced by these. */
286 cgraph_varpool_remove_unreferenced_decls (void)
288 struct cgraph_varpool_node
*next
, *node
= cgraph_varpool_nodes_queue
;
290 cgraph_varpool_reset_queue ();
292 if (errorcount
|| sorrycount
)
297 tree decl
= node
->decl
;
298 next
= node
->next_needed
;
302 && ((DECL_ASSEMBLER_NAME_SET_P (decl
)
303 && TREE_SYMBOL_REFERENCED (DECL_ASSEMBLER_NAME (decl
)))
304 || node
->force_output
305 || decide_is_variable_needed (node
, decl
)))
306 cgraph_varpool_mark_needed_node (node
);
310 cgraph_varpool_analyze_pending_decls ();
314 /* When not doing unit-at-a-time, output all functions enqueued.
315 Return true when such a functions were found. */
318 cgraph_assemble_pending_functions (void)
322 if (flag_unit_at_a_time
)
325 while (cgraph_nodes_queue
)
327 struct cgraph_node
*n
= cgraph_nodes_queue
;
329 cgraph_nodes_queue
= cgraph_nodes_queue
->next_needed
;
330 n
->next_needed
= NULL
;
331 if (!n
->global
.inlined_to
333 && !DECL_EXTERNAL (n
->decl
))
335 cgraph_expand_function (n
);
343 /* DECL has been parsed. Take it, queue it, compile it at the whim of the
344 logic in effect. If NESTED is true, then our caller cannot stand to have
345 the garbage collector run at the moment. We would need to either create
346 a new GC context, or just not compile right now. */
349 cgraph_finalize_function (tree decl
, bool nested
)
351 struct cgraph_node
*node
= cgraph_node (decl
);
353 if (node
->local
.finalized
)
355 /* As an GCC extension we allow redefinition of the function. The
356 semantics when both copies of bodies differ is not well defined.
357 We replace the old body with new body so in unit at a time mode
358 we always use new body, while in normal mode we may end up with
359 old body inlined into some functions and new body expanded and
362 ??? It may make more sense to use one body for inlining and other
363 body for expanding the function but this is difficult to do. */
365 /* If node->output is set, then this is a unit-at-a-time compilation
366 and we have already begun whole-unit analysis. This is *not*
367 testing for whether we've already emitted the function. That
368 case can be sort-of legitimately seen with real function
369 redefinition errors. I would argue that the front end should
370 never present us with such a case, but don't enforce that for now. */
371 gcc_assert (!node
->output
);
373 /* Reset our data structures so we can analyze the function again. */
374 memset (&node
->local
, 0, sizeof (node
->local
));
375 memset (&node
->global
, 0, sizeof (node
->global
));
376 memset (&node
->rtl
, 0, sizeof (node
->rtl
));
377 node
->analyzed
= false;
378 node
->local
.redefined_extern_inline
= true;
380 if (!flag_unit_at_a_time
)
382 struct cgraph_node
*n
;
384 for (n
= cgraph_nodes
; n
; n
= n
->next
)
385 if (n
->global
.inlined_to
== node
)
386 cgraph_remove_node (n
);
389 cgraph_node_remove_callees (node
);
391 /* We may need to re-queue the node for assembling in case
392 we already proceeded it and ignored as not needed. */
393 if (node
->reachable
&& !flag_unit_at_a_time
)
395 struct cgraph_node
*n
;
397 for (n
= cgraph_nodes_queue
; n
; n
= n
->next_needed
)
405 notice_global_symbol (decl
);
407 node
->local
.finalized
= true;
408 node
->lowered
= DECL_STRUCT_FUNCTION (decl
)->cfg
!= NULL
;
410 lower_nested_functions (decl
);
411 gcc_assert (!node
->nested
);
413 /* If not unit at a time, then we need to create the call graph
414 now, so that called functions can be queued and emitted now. */
415 if (!flag_unit_at_a_time
)
417 cgraph_analyze_function (node
);
418 cgraph_decide_inlining_incrementally (node
);
421 if (decide_is_function_needed (node
, decl
))
422 cgraph_mark_needed_node (node
);
424 /* Since we reclaim unrechable nodes at the end of every language
425 level unit, we need to be conservative about possible entry points
427 if (TREE_PUBLIC (decl
) && !DECL_COMDAT (decl
) && !DECL_EXTERNAL (decl
))
428 cgraph_mark_reachable_node (node
);
430 /* If not unit at a time, go ahead and emit everything we've found
431 to be reachable at this time. */
434 if (!cgraph_assemble_pending_functions ())
438 /* If we've not yet emitted decl, tell the debug info about it. */
439 if (!TREE_ASM_WRITTEN (decl
))
440 (*debug_hooks
->deferred_inline_function
) (decl
);
442 /* Possibly warn about unused parameters. */
443 if (warn_unused_parameter
)
444 do_warn_unused_parameter (decl
);
448 cgraph_lower_function (struct cgraph_node
*node
)
452 tree_lowering_passes (node
->decl
);
453 node
->lowered
= true;
456 /* Walk tree and record all calls. Called via walk_tree. */
458 record_reference (tree
*tp
, int *walk_subtrees
, void *data
)
462 switch (TREE_CODE (t
))
465 /* ??? Really, we should mark this decl as *potentially* referenced
466 by this function and re-examine whether the decl is actually used
467 after rtl has been generated. */
468 if (TREE_STATIC (t
) || DECL_EXTERNAL (t
))
470 cgraph_varpool_mark_needed_node (cgraph_varpool_node (t
));
471 if (lang_hooks
.callgraph
.analyze_expr
)
472 return lang_hooks
.callgraph
.analyze_expr (tp
, walk_subtrees
,
479 if (flag_unit_at_a_time
)
481 /* Record dereferences to the functions. This makes the
482 functions reachable unconditionally. */
483 tree decl
= TREE_OPERAND (*tp
, 0);
484 if (TREE_CODE (decl
) == FUNCTION_DECL
)
485 cgraph_mark_needed_node (cgraph_node (decl
));
490 /* Save some cycles by not walking types and declaration as we
491 won't find anything useful there anyway. */
492 if (IS_TYPE_OR_DECL_P (*tp
))
498 if ((unsigned int) TREE_CODE (t
) >= LAST_AND_UNUSED_TREE_CODE
)
499 return lang_hooks
.callgraph
.analyze_expr (tp
, walk_subtrees
, data
);
506 /* Create cgraph edges for function calls inside BODY from NODE. */
509 cgraph_create_edges (struct cgraph_node
*node
, tree body
)
513 struct function
*this_cfun
= DECL_STRUCT_FUNCTION (body
);
514 block_stmt_iterator bsi
;
516 visited_nodes
= pointer_set_create ();
518 /* Reach the trees by walking over the CFG, and note the
519 enclosing basic-blocks in the call edges. */
520 FOR_EACH_BB_FN (bb
, this_cfun
)
521 for (bsi
= bsi_start (bb
); !bsi_end_p (bsi
); bsi_next (&bsi
))
523 tree stmt
= bsi_stmt (bsi
);
524 tree call
= get_call_expr_in (stmt
);
527 if (call
&& (decl
= get_callee_fndecl (call
)))
529 cgraph_create_edge (node
, cgraph_node (decl
), stmt
,
532 walk_tree (&TREE_OPERAND (call
, 1),
533 record_reference
, node
, visited_nodes
);
534 if (TREE_CODE (stmt
) == MODIFY_EXPR
)
535 walk_tree (&TREE_OPERAND (stmt
, 0),
536 record_reference
, node
, visited_nodes
);
539 walk_tree (bsi_stmt_ptr (bsi
), record_reference
, node
, visited_nodes
);
542 /* Walk over any private statics that may take addresses of functions. */
543 if (TREE_CODE (DECL_INITIAL (body
)) == BLOCK
)
545 for (step
= BLOCK_VARS (DECL_INITIAL (body
));
547 step
= TREE_CHAIN (step
))
548 if (DECL_INITIAL (step
))
549 walk_tree (&DECL_INITIAL (step
), record_reference
, node
, visited_nodes
);
552 /* Also look here for private statics. */
553 if (DECL_STRUCT_FUNCTION (body
))
554 for (step
= DECL_STRUCT_FUNCTION (body
)->unexpanded_var_list
;
556 step
= TREE_CHAIN (step
))
558 tree decl
= TREE_VALUE (step
);
559 if (DECL_INITIAL (decl
) && TREE_STATIC (decl
))
560 walk_tree (&DECL_INITIAL (decl
), record_reference
, node
, visited_nodes
);
563 pointer_set_destroy (visited_nodes
);
564 visited_nodes
= NULL
;
568 /* Verify cgraph nodes of given cgraph node. */
570 verify_cgraph_node (struct cgraph_node
*node
)
572 struct cgraph_edge
*e
;
573 struct cgraph_node
*main_clone
;
574 struct function
*this_cfun
= DECL_STRUCT_FUNCTION (node
->decl
);
575 basic_block this_block
;
576 block_stmt_iterator bsi
;
577 bool error_found
= false;
579 timevar_push (TV_CGRAPH_VERIFY
);
580 for (e
= node
->callees
; e
; e
= e
->next_callee
)
583 error ("Aux field set for edge %s->%s",
584 cgraph_node_name (e
->caller
), cgraph_node_name (e
->callee
));
587 for (e
= node
->callers
; e
; e
= e
->next_caller
)
589 if (!e
->inline_failed
)
591 if (node
->global
.inlined_to
592 != (e
->caller
->global
.inlined_to
593 ? e
->caller
->global
.inlined_to
: e
->caller
))
595 error ("Inlined_to pointer is wrong");
598 if (node
->callers
->next_caller
)
600 error ("Multiple inline callers");
605 if (node
->global
.inlined_to
)
607 error ("Inlined_to pointer set for noninline callers");
611 if (!node
->callers
&& node
->global
.inlined_to
)
613 error ("Inlined_to pointer is set but no predecesors found");
616 if (node
->global
.inlined_to
== node
)
618 error ("Inlined_to pointer refers to itself");
622 for (main_clone
= cgraph_node (node
->decl
); main_clone
;
623 main_clone
= main_clone
->next_clone
)
624 if (main_clone
== node
)
628 error ("Node not found in DECL_ASSEMBLER_NAME hash");
633 && DECL_SAVED_TREE (node
->decl
) && !TREE_ASM_WRITTEN (node
->decl
)
634 && (!DECL_EXTERNAL (node
->decl
) || node
->global
.inlined_to
))
638 /* The nodes we're interested in are never shared, so walk
639 the tree ignoring duplicates. */
640 visited_nodes
= pointer_set_create ();
641 /* Reach the trees by walking over the CFG, and note the
642 enclosing basic-blocks in the call edges. */
643 FOR_EACH_BB_FN (this_block
, this_cfun
)
644 for (bsi
= bsi_start (this_block
); !bsi_end_p (bsi
); bsi_next (&bsi
))
646 tree stmt
= bsi_stmt (bsi
);
647 tree call
= get_call_expr_in (stmt
);
649 if (call
&& (decl
= get_callee_fndecl (call
)))
651 struct cgraph_edge
*e
= cgraph_edge (node
, stmt
);
656 error ("Shared call_stmt:");
657 debug_generic_stmt (stmt
);
660 if (e
->callee
->decl
!= cgraph_node (decl
)->decl
)
662 error ("Edge points to wrong declaration:");
663 debug_tree (e
->callee
->decl
);
664 fprintf (stderr
," Instead of:");
671 error ("Missing callgraph edge for call stmt:");
672 debug_generic_stmt (stmt
);
677 pointer_set_destroy (visited_nodes
);
678 visited_nodes
= NULL
;
681 /* No CFG available?! */
684 for (e
= node
->callees
; e
; e
= e
->next_callee
)
688 error ("Edge %s->%s has no corresponding call_stmt",
689 cgraph_node_name (e
->caller
),
690 cgraph_node_name (e
->callee
));
691 debug_generic_stmt (e
->call_stmt
);
699 dump_cgraph_node (stderr
, node
);
700 internal_error ("verify_cgraph_node failed.");
702 timevar_pop (TV_CGRAPH_VERIFY
);
705 /* Verify whole cgraph structure. */
709 struct cgraph_node
*node
;
711 if (sorrycount
|| errorcount
)
714 for (node
= cgraph_nodes
; node
; node
= node
->next
)
715 verify_cgraph_node (node
);
719 /* Output all variables enqueued to be assembled. */
721 cgraph_varpool_assemble_pending_decls (void)
723 bool changed
= false;
725 if (errorcount
|| sorrycount
)
728 /* EH might mark decls as needed during expansion. This should be safe since
729 we don't create references to new function, but it should not be used
731 cgraph_varpool_analyze_pending_decls ();
733 while (cgraph_varpool_nodes_queue
)
735 tree decl
= cgraph_varpool_nodes_queue
->decl
;
736 struct cgraph_varpool_node
*node
= cgraph_varpool_nodes_queue
;
738 cgraph_varpool_nodes_queue
= cgraph_varpool_nodes_queue
->next_needed
;
739 if (!TREE_ASM_WRITTEN (decl
) && !node
->alias
&& !DECL_EXTERNAL (decl
))
741 assemble_variable (decl
, 0, 1, 0);
744 node
->next_needed
= NULL
;
749 /* Analyze the function scheduled to be output. */
751 cgraph_analyze_function (struct cgraph_node
*node
)
753 tree decl
= node
->decl
;
754 struct cgraph_edge
*e
;
756 current_function_decl
= decl
;
757 push_cfun (DECL_STRUCT_FUNCTION (decl
));
758 cgraph_lower_function (node
);
760 /* First kill forward declaration so reverse inlining works properly. */
761 cgraph_create_edges (node
, decl
);
763 node
->local
.inlinable
= tree_inlinable_function_p (decl
);
764 node
->local
.self_insns
= estimate_num_insns (decl
);
765 if (node
->local
.inlinable
)
766 node
->local
.disregard_inline_limits
767 = lang_hooks
.tree_inlining
.disregard_inline_limits (decl
);
768 for (e
= node
->callers
; e
; e
= e
->next_caller
)
770 if (node
->local
.redefined_extern_inline
)
771 e
->inline_failed
= N_("redefined extern inline functions are not "
772 "considered for inlining");
773 else if (!node
->local
.inlinable
)
774 e
->inline_failed
= N_("function not inlinable");
776 e
->inline_failed
= N_("function not considered for inlining");
778 if (flag_really_no_inline
&& !node
->local
.disregard_inline_limits
)
779 node
->local
.inlinable
= 0;
780 /* Inlining characteristics are maintained by the cgraph_mark_inline. */
781 node
->global
.insns
= node
->local
.self_insns
;
783 node
->analyzed
= true;
785 current_function_decl
= NULL
;
788 /* Analyze the whole compilation unit once it is parsed completely. */
791 cgraph_finalize_compilation_unit (void)
793 struct cgraph_node
*node
;
794 /* Keep track of already processed nodes when called multiple times for
795 intermodule optimization. */
796 static struct cgraph_node
*first_analyzed
;
800 if (!flag_unit_at_a_time
)
802 cgraph_assemble_pending_functions ();
808 fprintf (stderr
, "\nAnalyzing compilation unit");
812 timevar_push (TV_CGRAPH
);
813 cgraph_varpool_analyze_pending_decls ();
814 if (cgraph_dump_file
)
816 fprintf (cgraph_dump_file
, "Initial entry points:");
817 for (node
= cgraph_nodes
; node
!= first_analyzed
; node
= node
->next
)
818 if (node
->needed
&& DECL_SAVED_TREE (node
->decl
))
819 fprintf (cgraph_dump_file
, " %s", cgraph_node_name (node
));
820 fprintf (cgraph_dump_file
, "\n");
823 /* Propagate reachability flag and lower representation of all reachable
824 functions. In the future, lowering will introduce new functions and
825 new entry points on the way (by template instantiation and virtual
826 method table generation for instance). */
827 while (cgraph_nodes_queue
)
829 struct cgraph_edge
*edge
;
830 tree decl
= cgraph_nodes_queue
->decl
;
832 node
= cgraph_nodes_queue
;
833 cgraph_nodes_queue
= cgraph_nodes_queue
->next_needed
;
834 node
->next_needed
= NULL
;
836 /* ??? It is possible to create extern inline function and later using
837 weak alias attribute to kill its body. See
838 gcc.c-torture/compile/20011119-1.c */
839 if (!DECL_SAVED_TREE (decl
))
842 gcc_assert (!node
->analyzed
&& node
->reachable
);
843 gcc_assert (DECL_SAVED_TREE (decl
));
845 cgraph_analyze_function (node
);
847 for (edge
= node
->callees
; edge
; edge
= edge
->next_callee
)
848 if (!edge
->callee
->reachable
)
849 cgraph_mark_reachable_node (edge
->callee
);
851 cgraph_varpool_analyze_pending_decls ();
854 /* Collect entry points to the unit. */
856 if (cgraph_dump_file
)
858 fprintf (cgraph_dump_file
, "Unit entry points:");
859 for (node
= cgraph_nodes
; node
!= first_analyzed
; node
= node
->next
)
860 if (node
->needed
&& DECL_SAVED_TREE (node
->decl
))
861 fprintf (cgraph_dump_file
, " %s", cgraph_node_name (node
));
862 fprintf (cgraph_dump_file
, "\n\nInitial ");
863 dump_cgraph (cgraph_dump_file
);
866 if (cgraph_dump_file
)
867 fprintf (cgraph_dump_file
, "\nReclaiming functions:");
869 for (node
= cgraph_nodes
; node
!= first_analyzed
; node
= node
->next
)
871 tree decl
= node
->decl
;
873 if (!node
->reachable
&& DECL_SAVED_TREE (decl
))
875 if (cgraph_dump_file
)
876 fprintf (cgraph_dump_file
, " %s", cgraph_node_name (node
));
877 cgraph_remove_node (node
);
880 node
->next_needed
= NULL
;
882 if (cgraph_dump_file
)
884 fprintf (cgraph_dump_file
, "\n\nReclaimed ");
885 dump_cgraph (cgraph_dump_file
);
887 first_analyzed
= cgraph_nodes
;
889 timevar_pop (TV_CGRAPH
);
891 /* Figure out what functions we want to assemble. */
894 cgraph_mark_functions_to_output (void)
896 struct cgraph_node
*node
;
898 for (node
= cgraph_nodes
; node
; node
= node
->next
)
900 tree decl
= node
->decl
;
901 struct cgraph_edge
*e
;
903 gcc_assert (!node
->output
);
905 for (e
= node
->callers
; e
; e
= e
->next_caller
)
906 if (e
->inline_failed
)
909 /* We need to output all local functions that are used and not
910 always inlined, as well as those that are reachable from
911 outside the current compilation unit. */
912 if (DECL_SAVED_TREE (decl
)
913 && !node
->global
.inlined_to
915 || (e
&& node
->reachable
))
916 && !TREE_ASM_WRITTEN (decl
)
917 && !DECL_EXTERNAL (decl
))
921 /* We should've reclaimed all functions that are not needed. */
922 #ifdef ENABLE_CHECKING
923 if (!node
->global
.inlined_to
&& DECL_SAVED_TREE (decl
)
924 && !DECL_EXTERNAL (decl
))
926 dump_cgraph_node (stderr
, node
);
927 internal_error ("failed to reclaim unneeded function");
930 gcc_assert (node
->global
.inlined_to
|| !DECL_SAVED_TREE (decl
)
931 || DECL_EXTERNAL (decl
));
938 /* Expand function specified by NODE. */
941 cgraph_expand_function (struct cgraph_node
*node
)
943 tree decl
= node
->decl
;
945 /* We ought to not compile any inline clones. */
946 gcc_assert (!node
->global
.inlined_to
);
948 if (flag_unit_at_a_time
)
949 announce_function (decl
);
951 cgraph_lower_function (node
);
953 /* Generate RTL for the body of DECL. */
954 lang_hooks
.callgraph
.expand_function (decl
);
956 /* Make sure that BE didn't give up on compiling. */
957 /* ??? Can happen with nested function of extern inline. */
958 gcc_assert (TREE_ASM_WRITTEN (node
->decl
));
960 current_function_decl
= NULL
;
961 if (!cgraph_preserve_function_body_p (node
->decl
))
963 DECL_SAVED_TREE (node
->decl
) = NULL
;
964 DECL_STRUCT_FUNCTION (node
->decl
) = NULL
;
965 DECL_INITIAL (node
->decl
) = error_mark_node
;
966 /* Eliminate all call edges. This is important so the call_expr no longer
967 points to the dead function body. */
968 cgraph_node_remove_callees (node
);
971 cgraph_function_flags_ready
= true;
974 /* Return true when CALLER_DECL should be inlined into CALLEE_DECL. */
977 cgraph_inline_p (struct cgraph_edge
*e
, const char **reason
)
979 *reason
= e
->inline_failed
;
980 return !e
->inline_failed
;
985 /* Expand all functions that must be output.
987 Attempt to topologically sort the nodes so function is output when
988 all called functions are already assembled to allow data to be
989 propagated across the callgraph. Use a stack to get smaller distance
990 between a function and its callees (later we may choose to use a more
991 sophisticated algorithm for function reordering; we will likely want
992 to use subsections to make the output functions appear in top-down
996 cgraph_expand_all_functions (void)
998 struct cgraph_node
*node
;
999 struct cgraph_node
**order
=
1000 xcalloc (cgraph_n_nodes
, sizeof (struct cgraph_node
*));
1001 int order_pos
= 0, new_order_pos
= 0;
1004 order_pos
= cgraph_postorder (order
);
1005 gcc_assert (order_pos
== cgraph_n_nodes
);
1007 /* Garbage collector may remove inline clones we eliminate during
1008 optimization. So we must be sure to not reference them. */
1009 for (i
= 0; i
< order_pos
; i
++)
1010 if (order
[i
]->output
)
1011 order
[new_order_pos
++] = order
[i
];
1013 for (i
= new_order_pos
- 1; i
>= 0; i
--)
1018 gcc_assert (node
->reachable
);
1020 cgraph_expand_function (node
);
1026 /* Mark visibility of all functions.
1028 A local function is one whose calls can occur only in the current
1029 compilation unit and all its calls are explicit, so we can change
1030 its calling convention. We simply mark all static functions whose
1031 address is not taken as local.
1033 We also change the TREE_PUBLIC flag of all declarations that are public
1034 in language point of view but we want to overwrite this default
1035 via visibilities for the backend point of view. */
1038 cgraph_function_and_variable_visibility (void)
1040 struct cgraph_node
*node
;
1041 struct cgraph_varpool_node
*vnode
;
1043 for (node
= cgraph_nodes
; node
; node
= node
->next
)
1046 && (DECL_COMDAT (node
->decl
)
1047 || (TREE_PUBLIC (node
->decl
) && !DECL_EXTERNAL (node
->decl
))))
1048 node
->local
.externally_visible
= 1;
1049 node
->local
.local
= (!node
->needed
1051 && !node
->local
.externally_visible
);
1053 for (vnode
= cgraph_varpool_nodes_queue
; vnode
; vnode
= vnode
->next_needed
)
1056 && (DECL_COMDAT (vnode
->decl
) || TREE_PUBLIC (vnode
->decl
)))
1057 vnode
->externally_visible
= 1;
1058 gcc_assert (TREE_STATIC (vnode
->decl
));
1061 /* Because we have to be conservative on the boundaries of source
1062 level units, it is possible that we marked some functions in
1063 reachable just because they might be used later via external
1064 linkage, but after making them local they are really unreachable
1066 cgraph_remove_unreachable_nodes (true, cgraph_dump_file
);
1068 if (cgraph_dump_file
)
1070 fprintf (cgraph_dump_file
, "\nMarking local functions:");
1071 for (node
= cgraph_nodes
; node
; node
= node
->next
)
1072 if (node
->local
.local
)
1073 fprintf (cgraph_dump_file
, " %s", cgraph_node_name (node
));
1074 fprintf (cgraph_dump_file
, "\n\n");
1075 fprintf (cgraph_dump_file
, "\nMarking externally visible functions:");
1076 for (node
= cgraph_nodes
; node
; node
= node
->next
)
1077 if (node
->local
.externally_visible
)
1078 fprintf (cgraph_dump_file
, " %s", cgraph_node_name (node
));
1079 fprintf (cgraph_dump_file
, "\n\n");
1081 cgraph_function_flags_ready
= true;
1084 /* Return true when function body of DECL still needs to be kept around
1085 for later re-use. */
1087 cgraph_preserve_function_body_p (tree decl
)
1089 struct cgraph_node
*node
;
1090 /* Keep the body; we're going to dump it. */
1091 if (dump_enabled_p (TDI_tree_all
))
1093 if (!cgraph_global_info_ready
)
1094 return (DECL_INLINE (decl
) && !flag_really_no_inline
);
1095 /* Look if there is any clone around. */
1096 for (node
= cgraph_node (decl
); node
; node
= node
->next_clone
)
1097 if (node
->global
.inlined_to
)
1102 /* Perform simple optimizations based on callgraph. */
1105 cgraph_optimize (void)
1107 #ifdef ENABLE_CHECKING
1110 if (!flag_unit_at_a_time
)
1112 cgraph_varpool_assemble_pending_decls ();
1116 process_pending_assemble_externals ();
1118 /* Frontend may output common variables after the unit has been finalized.
1119 It is safe to deal with them here as they are always zero initialized. */
1120 cgraph_varpool_analyze_pending_decls ();
1122 timevar_push (TV_CGRAPHOPT
);
1124 fprintf (stderr
, "Performing intraprocedural optimizations\n");
1126 cgraph_function_and_variable_visibility ();
1127 if (cgraph_dump_file
)
1129 fprintf (cgraph_dump_file
, "Marked ");
1130 dump_cgraph (cgraph_dump_file
);
1133 /* This pass remove bodies of extern inline functions we never inlined.
1134 Do this later so other IPA passes see what is really going on. */
1135 cgraph_remove_unreachable_nodes (false, dump_file
);
1136 cgraph_global_info_ready
= true;
1137 if (cgraph_dump_file
)
1139 fprintf (cgraph_dump_file
, "Optimized ");
1140 dump_cgraph (cgraph_dump_file
);
1141 dump_varpool (cgraph_dump_file
);
1143 timevar_pop (TV_CGRAPHOPT
);
1145 /* Output everything. */
1147 fprintf (stderr
, "Assembling functions:\n");
1148 #ifdef ENABLE_CHECKING
1152 cgraph_mark_functions_to_output ();
1153 cgraph_expand_all_functions ();
1154 cgraph_varpool_remove_unreferenced_decls ();
1156 cgraph_varpool_assemble_pending_decls ();
1158 if (cgraph_dump_file
)
1160 fprintf (cgraph_dump_file
, "\nFinal ");
1161 dump_cgraph (cgraph_dump_file
);
1163 #ifdef ENABLE_CHECKING
1165 /* Double check that all inline clones are gone and that all
1166 function bodies have been released from memory. */
1167 if (flag_unit_at_a_time
1168 && !dump_enabled_p (TDI_tree_all
)
1169 && !(sorrycount
|| errorcount
))
1171 struct cgraph_node
*node
;
1172 bool error_found
= false;
1174 for (node
= cgraph_nodes
; node
; node
= node
->next
)
1176 && (node
->global
.inlined_to
1177 || DECL_SAVED_TREE (node
->decl
)))
1180 dump_cgraph_node (stderr
, node
);
1183 internal_error ("Nodes with no released memory found.");
1188 /* Generate and emit a static constructor or destructor. WHICH must be
1189 one of 'I' or 'D'. BODY should be a STATEMENT_LIST containing
1190 GENERIC statements. */
1193 cgraph_build_static_cdtor (char which
, tree body
, int priority
)
1195 static int counter
= 0;
1197 tree decl
, name
, resdecl
;
1199 sprintf (which_buf
, "%c_%d", which
, counter
++);
1200 name
= get_file_function_name_long (which_buf
);
1202 decl
= build_decl (FUNCTION_DECL
, name
,
1203 build_function_type (void_type_node
, void_list_node
));
1204 current_function_decl
= decl
;
1206 resdecl
= build_decl (RESULT_DECL
, NULL_TREE
, void_type_node
);
1207 DECL_ARTIFICIAL (resdecl
) = 1;
1208 DECL_IGNORED_P (resdecl
) = 1;
1209 DECL_RESULT (decl
) = resdecl
;
1211 allocate_struct_function (decl
);
1213 TREE_STATIC (decl
) = 1;
1214 TREE_USED (decl
) = 1;
1215 DECL_ARTIFICIAL (decl
) = 1;
1216 DECL_IGNORED_P (decl
) = 1;
1217 DECL_NO_INSTRUMENT_FUNCTION_ENTRY_EXIT (decl
) = 1;
1218 DECL_SAVED_TREE (decl
) = body
;
1219 TREE_PUBLIC (decl
) = ! targetm
.have_ctors_dtors
;
1220 DECL_UNINLINABLE (decl
) = 1;
1222 DECL_INITIAL (decl
) = make_node (BLOCK
);
1223 TREE_USED (DECL_INITIAL (decl
)) = 1;
1225 DECL_SOURCE_LOCATION (decl
) = input_location
;
1226 cfun
->function_end_locus
= input_location
;
1231 DECL_STATIC_CONSTRUCTOR (decl
) = 1;
1234 DECL_STATIC_DESTRUCTOR (decl
) = 1;
1240 gimplify_function_tree (decl
);
1242 /* ??? We will get called LATE in the compilation process. */
1243 if (cgraph_global_info_ready
)
1245 tree_lowering_passes (decl
);
1246 tree_rest_of_compilation (decl
);
1249 cgraph_finalize_function (decl
, 0);
1251 if (targetm
.have_ctors_dtors
)
1253 void (*fn
) (rtx
, int);
1256 fn
= targetm
.asm_out
.constructor
;
1258 fn
= targetm
.asm_out
.destructor
;
1259 fn (XEXP (DECL_RTL (decl
), 0), priority
);
1266 cgraph_dump_file
= dump_begin (TDI_cgraph
, NULL
);