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, 51 Franklin Street, Fifth Floor, 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 "ipa-prop.h"
166 #include "tree-gimple.h"
167 #include "tree-pass.h"
170 static void cgraph_expand_all_functions (void);
171 static void cgraph_mark_functions_to_output (void);
172 static void cgraph_expand_function (struct cgraph_node
*);
173 static tree
record_reference (tree
*, int *, void *);
174 static void cgraph_analyze_function (struct cgraph_node
*node
);
176 /* Records tree nodes seen in record_reference. Simply using
177 walk_tree_without_duplicates doesn't guarantee each node is visited
178 once because it gets a new htab upon each recursive call from
179 record_reference itself. */
180 static struct pointer_set_t
*visited_nodes
;
182 static FILE *cgraph_dump_file
;
184 /* Determine if function DECL is needed. That is, visible to something
185 either outside this translation unit, something magic in the system
186 configury, or (if not doing unit-at-a-time) to something we havn't
190 decide_is_function_needed (struct cgraph_node
*node
, tree decl
)
193 if (MAIN_NAME_P (DECL_NAME (decl
))
194 && TREE_PUBLIC (decl
))
196 node
->local
.externally_visible
= true;
200 /* If the user told us it is used, then it must be so. */
201 if (node
->local
.externally_visible
202 || lookup_attribute ("used", DECL_ATTRIBUTES (decl
)))
205 /* ??? If the assembler name is set by hand, it is possible to assemble
206 the name later after finalizing the function and the fact is noticed
207 in assemble_name then. This is arguably a bug. */
208 if (DECL_ASSEMBLER_NAME_SET_P (decl
)
209 && TREE_SYMBOL_REFERENCED (DECL_ASSEMBLER_NAME (decl
)))
212 /* If we decided it was needed before, but at the time we didn't have
213 the body of the function available, then it's still needed. We have
214 to go back and re-check its dependencies now. */
218 /* Externally visible functions must be output. The exception is
219 COMDAT functions that must be output only when they are needed. */
220 if ((TREE_PUBLIC (decl
) && !flag_whole_program
)
221 && !DECL_COMDAT (decl
) && !DECL_EXTERNAL (decl
))
224 /* Constructors and destructors are reachable from the runtime by
226 if (DECL_STATIC_CONSTRUCTOR (decl
) || DECL_STATIC_DESTRUCTOR (decl
))
229 if (flag_unit_at_a_time
)
232 /* If not doing unit at a time, then we'll only defer this function
233 if its marked for inlining. Otherwise we want to emit it now. */
235 /* "extern inline" functions are never output locally. */
236 if (DECL_EXTERNAL (decl
))
238 /* Nested functions of extern inline function shall not be emit unless
239 we inlined the origin. */
240 for (origin
= decl_function_context (decl
); origin
;
241 origin
= decl_function_context (origin
))
242 if (DECL_EXTERNAL (origin
))
244 /* We want to emit COMDAT functions only when absolutely necessary. */
245 if (DECL_COMDAT (decl
))
247 if (!DECL_INLINE (decl
)
248 || (!node
->local
.disregard_inline_limits
249 /* When declared inline, defer even the uninlinable functions.
250 This allows them to be eliminated when unused. */
251 && !DECL_DECLARED_INLINE_P (decl
)
252 && (!node
->local
.inlinable
|| !cgraph_default_inline_p (node
, NULL
))))
258 /* Walk the decls we marked as necessary and see if they reference new
259 variables or functions and add them into the worklists. */
261 cgraph_varpool_analyze_pending_decls (void)
263 bool changed
= false;
264 timevar_push (TV_CGRAPH
);
266 while (cgraph_varpool_first_unanalyzed_node
)
268 tree decl
= cgraph_varpool_first_unanalyzed_node
->decl
;
270 cgraph_varpool_first_unanalyzed_node
->analyzed
= true;
272 cgraph_varpool_first_unanalyzed_node
= cgraph_varpool_first_unanalyzed_node
->next_needed
;
274 if (DECL_INITIAL (decl
))
276 visited_nodes
= pointer_set_create ();
277 walk_tree (&DECL_INITIAL (decl
), record_reference
, NULL
, visited_nodes
);
278 pointer_set_destroy (visited_nodes
);
279 visited_nodes
= NULL
;
283 timevar_pop (TV_CGRAPH
);
287 /* Optimization of function bodies might've rendered some variables as
288 unnecessary so we want to avoid these from being compiled.
290 This is done by pruning the queue and keeping only the variables that
291 really appear needed (ie they are either externally visible or referenced
292 by compiled function). Re-doing the reachability analysis on variables
293 brings back the remaining variables referenced by these. */
295 cgraph_varpool_remove_unreferenced_decls (void)
297 struct cgraph_varpool_node
*next
, *node
= cgraph_varpool_nodes_queue
;
299 cgraph_varpool_reset_queue ();
301 if (errorcount
|| sorrycount
)
306 tree decl
= node
->decl
;
307 next
= node
->next_needed
;
311 && ((DECL_ASSEMBLER_NAME_SET_P (decl
)
312 && TREE_SYMBOL_REFERENCED (DECL_ASSEMBLER_NAME (decl
)))
313 || node
->force_output
314 || decide_is_variable_needed (node
, decl
)
315 /* ??? Cgraph does not yet rule the world with an iron hand,
316 and does not control the emission of debug information.
317 After a variable has its DECL_RTL set, we must assume that
318 it may be referenced by the debug information, and we can
319 no longer elide it. */
320 || DECL_RTL_SET_P (decl
)))
321 cgraph_varpool_mark_needed_node (node
);
325 cgraph_varpool_analyze_pending_decls ();
329 /* When not doing unit-at-a-time, output all functions enqueued.
330 Return true when such a functions were found. */
333 cgraph_assemble_pending_functions (void)
337 if (flag_unit_at_a_time
)
340 while (cgraph_nodes_queue
)
342 struct cgraph_node
*n
= cgraph_nodes_queue
;
344 cgraph_nodes_queue
= cgraph_nodes_queue
->next_needed
;
345 n
->next_needed
= NULL
;
346 if (!n
->global
.inlined_to
348 && !DECL_EXTERNAL (n
->decl
))
350 cgraph_expand_function (n
);
357 /* As an GCC extension we allow redefinition of the function. The
358 semantics when both copies of bodies differ is not well defined.
359 We replace the old body with new body so in unit at a time mode
360 we always use new body, while in normal mode we may end up with
361 old body inlined into some functions and new body expanded and
364 ??? It may make more sense to use one body for inlining and other
365 body for expanding the function but this is difficult to do. */
368 cgraph_reset_node (struct cgraph_node
*node
)
370 /* If node->output is set, then this is a unit-at-a-time compilation
371 and we have already begun whole-unit analysis. This is *not*
372 testing for whether we've already emitted the function. That
373 case can be sort-of legitimately seen with real function
374 redefinition errors. I would argue that the front end should
375 never present us with such a case, but don't enforce that for now. */
376 gcc_assert (!node
->output
);
378 /* Reset our data structures so we can analyze the function again. */
379 memset (&node
->local
, 0, sizeof (node
->local
));
380 memset (&node
->global
, 0, sizeof (node
->global
));
381 memset (&node
->rtl
, 0, sizeof (node
->rtl
));
382 node
->analyzed
= false;
383 node
->local
.redefined_extern_inline
= true;
384 node
->local
.finalized
= false;
386 if (!flag_unit_at_a_time
)
388 struct cgraph_node
*n
;
390 for (n
= cgraph_nodes
; n
; n
= n
->next
)
391 if (n
->global
.inlined_to
== node
)
392 cgraph_remove_node (n
);
395 cgraph_node_remove_callees (node
);
397 /* We may need to re-queue the node for assembling in case
398 we already proceeded it and ignored as not needed. */
399 if (node
->reachable
&& !flag_unit_at_a_time
)
401 struct cgraph_node
*n
;
403 for (n
= cgraph_nodes_queue
; n
; n
= n
->next_needed
)
411 /* DECL has been parsed. Take it, queue it, compile it at the whim of the
412 logic in effect. If NESTED is true, then our caller cannot stand to have
413 the garbage collector run at the moment. We would need to either create
414 a new GC context, or just not compile right now. */
417 cgraph_finalize_function (tree decl
, bool nested
)
419 struct cgraph_node
*node
= cgraph_node (decl
);
421 if (node
->local
.finalized
)
422 cgraph_reset_node (node
);
424 notice_global_symbol (decl
);
426 node
->local
.finalized
= true;
427 node
->lowered
= DECL_STRUCT_FUNCTION (decl
)->cfg
!= NULL
;
429 lower_nested_functions (decl
);
430 gcc_assert (!node
->nested
);
432 /* If not unit at a time, then we need to create the call graph
433 now, so that called functions can be queued and emitted now. */
434 if (!flag_unit_at_a_time
)
436 cgraph_analyze_function (node
);
437 cgraph_decide_inlining_incrementally (node
, false);
440 if (decide_is_function_needed (node
, decl
))
441 cgraph_mark_needed_node (node
);
443 /* Since we reclaim unreachable nodes at the end of every language
444 level unit, we need to be conservative about possible entry points
446 if ((TREE_PUBLIC (decl
) && !DECL_COMDAT (decl
) && !DECL_EXTERNAL (decl
)))
447 cgraph_mark_reachable_node (node
);
449 /* If not unit at a time, go ahead and emit everything we've found
450 to be reachable at this time. */
453 if (!cgraph_assemble_pending_functions ())
457 /* If we've not yet emitted decl, tell the debug info about it. */
458 if (!TREE_ASM_WRITTEN (decl
))
459 (*debug_hooks
->deferred_inline_function
) (decl
);
461 /* Possibly warn about unused parameters. */
462 if (warn_unused_parameter
)
463 do_warn_unused_parameter (decl
);
467 cgraph_lower_function (struct cgraph_node
*node
)
471 tree_lowering_passes (node
->decl
);
472 node
->lowered
= true;
475 /* Walk tree and record all calls. Called via walk_tree. */
477 record_reference (tree
*tp
, int *walk_subtrees
, void *data
)
481 switch (TREE_CODE (t
))
484 /* ??? Really, we should mark this decl as *potentially* referenced
485 by this function and re-examine whether the decl is actually used
486 after rtl has been generated. */
487 if (TREE_STATIC (t
) || DECL_EXTERNAL (t
))
489 cgraph_varpool_mark_needed_node (cgraph_varpool_node (t
));
490 if (lang_hooks
.callgraph
.analyze_expr
)
491 return lang_hooks
.callgraph
.analyze_expr (tp
, walk_subtrees
,
498 if (flag_unit_at_a_time
)
500 /* Record dereferences to the functions. This makes the
501 functions reachable unconditionally. */
502 tree decl
= TREE_OPERAND (*tp
, 0);
503 if (TREE_CODE (decl
) == FUNCTION_DECL
)
504 cgraph_mark_needed_node (cgraph_node (decl
));
509 /* Save some cycles by not walking types and declaration as we
510 won't find anything useful there anyway. */
511 if (IS_TYPE_OR_DECL_P (*tp
))
517 if ((unsigned int) TREE_CODE (t
) >= LAST_AND_UNUSED_TREE_CODE
)
518 return lang_hooks
.callgraph
.analyze_expr (tp
, walk_subtrees
, data
);
525 /* Create cgraph edges for function calls inside BODY from NODE. */
528 cgraph_create_edges (struct cgraph_node
*node
, tree body
)
532 struct function
*this_cfun
= DECL_STRUCT_FUNCTION (body
);
533 block_stmt_iterator bsi
;
535 visited_nodes
= pointer_set_create ();
537 /* Reach the trees by walking over the CFG, and note the
538 enclosing basic-blocks in the call edges. */
539 FOR_EACH_BB_FN (bb
, this_cfun
)
540 for (bsi
= bsi_start (bb
); !bsi_end_p (bsi
); bsi_next (&bsi
))
542 tree stmt
= bsi_stmt (bsi
);
543 tree call
= get_call_expr_in (stmt
);
546 if (call
&& (decl
= get_callee_fndecl (call
)))
548 cgraph_create_edge (node
, cgraph_node (decl
), stmt
,
551 walk_tree (&TREE_OPERAND (call
, 1),
552 record_reference
, node
, visited_nodes
);
553 if (TREE_CODE (stmt
) == MODIFY_EXPR
)
554 walk_tree (&TREE_OPERAND (stmt
, 0),
555 record_reference
, node
, visited_nodes
);
558 walk_tree (bsi_stmt_ptr (bsi
), record_reference
, node
, visited_nodes
);
561 /* Look for initializers of constant variables and private statics. */
562 for (step
= DECL_STRUCT_FUNCTION (body
)->unexpanded_var_list
;
564 step
= TREE_CHAIN (step
))
566 tree decl
= TREE_VALUE (step
);
567 if (TREE_CODE (decl
) == VAR_DECL
568 && (TREE_STATIC (decl
) && !DECL_EXTERNAL (decl
))
569 && flag_unit_at_a_time
)
570 cgraph_varpool_finalize_decl (decl
);
571 else if (TREE_CODE (decl
) == VAR_DECL
&& DECL_INITIAL (decl
))
572 walk_tree (&DECL_INITIAL (decl
), record_reference
, node
, visited_nodes
);
575 pointer_set_destroy (visited_nodes
);
576 visited_nodes
= NULL
;
579 /* Give initial reasons why inlining would fail. Those gets
580 either NULLified or usually overwritten by more precise reason
583 initialize_inline_failed (struct cgraph_node
*node
)
585 struct cgraph_edge
*e
;
587 for (e
= node
->callers
; e
; e
= e
->next_caller
)
589 gcc_assert (!e
->callee
->global
.inlined_to
);
590 gcc_assert (e
->inline_failed
);
591 if (node
->local
.redefined_extern_inline
)
592 e
->inline_failed
= N_("redefined extern inline functions are not "
593 "considered for inlining");
594 else if (!node
->local
.inlinable
)
595 e
->inline_failed
= N_("function not inlinable");
597 e
->inline_failed
= N_("function not considered for inlining");
601 /* Rebuild call edges from current function after a passes not aware
602 of cgraph updating. */
604 rebuild_cgraph_edges (void)
607 struct cgraph_node
*node
= cgraph_node (current_function_decl
);
608 block_stmt_iterator bsi
;
610 cgraph_node_remove_callees (node
);
612 node
->count
= ENTRY_BLOCK_PTR
->count
;
615 for (bsi
= bsi_start (bb
); !bsi_end_p (bsi
); bsi_next (&bsi
))
617 tree stmt
= bsi_stmt (bsi
);
618 tree call
= get_call_expr_in (stmt
);
621 if (call
&& (decl
= get_callee_fndecl (call
)))
622 cgraph_create_edge (node
, cgraph_node (decl
), stmt
,
626 initialize_inline_failed (node
);
627 gcc_assert (!node
->global
.inlined_to
);
630 struct tree_opt_pass pass_rebuild_cgraph_edges
=
634 rebuild_cgraph_edges
, /* execute */
637 0, /* static_pass_number */
639 PROP_cfg
, /* properties_required */
640 0, /* properties_provided */
641 0, /* properties_destroyed */
642 0, /* todo_flags_start */
643 0, /* todo_flags_finish */
647 /* Verify cgraph nodes of given cgraph node. */
649 verify_cgraph_node (struct cgraph_node
*node
)
651 struct cgraph_edge
*e
;
652 struct cgraph_node
*main_clone
;
653 struct function
*this_cfun
= DECL_STRUCT_FUNCTION (node
->decl
);
654 basic_block this_block
;
655 block_stmt_iterator bsi
;
656 bool error_found
= false;
658 timevar_push (TV_CGRAPH_VERIFY
);
659 for (e
= node
->callees
; e
; e
= e
->next_callee
)
662 error ("aux field set for edge %s->%s",
663 cgraph_node_name (e
->caller
), cgraph_node_name (e
->callee
));
666 for (e
= node
->callers
; e
; e
= e
->next_caller
)
668 if (!e
->inline_failed
)
670 if (node
->global
.inlined_to
671 != (e
->caller
->global
.inlined_to
672 ? e
->caller
->global
.inlined_to
: e
->caller
))
674 error ("inlined_to pointer is wrong");
677 if (node
->callers
->next_caller
)
679 error ("multiple inline callers");
684 if (node
->global
.inlined_to
)
686 error ("inlined_to pointer set for noninline callers");
690 if (!node
->callers
&& node
->global
.inlined_to
)
692 error ("inlined_to pointer is set but no predecesors found");
695 if (node
->global
.inlined_to
== node
)
697 error ("inlined_to pointer refers to itself");
701 for (main_clone
= cgraph_node (node
->decl
); main_clone
;
702 main_clone
= main_clone
->next_clone
)
703 if (main_clone
== node
)
707 error ("node not found in DECL_ASSEMBLER_NAME hash");
712 && DECL_SAVED_TREE (node
->decl
) && !TREE_ASM_WRITTEN (node
->decl
)
713 && (!DECL_EXTERNAL (node
->decl
) || node
->global
.inlined_to
))
717 /* The nodes we're interested in are never shared, so walk
718 the tree ignoring duplicates. */
719 visited_nodes
= pointer_set_create ();
720 /* Reach the trees by walking over the CFG, and note the
721 enclosing basic-blocks in the call edges. */
722 FOR_EACH_BB_FN (this_block
, this_cfun
)
723 for (bsi
= bsi_start (this_block
); !bsi_end_p (bsi
); bsi_next (&bsi
))
725 tree stmt
= bsi_stmt (bsi
);
726 tree call
= get_call_expr_in (stmt
);
728 if (call
&& (decl
= get_callee_fndecl (call
)))
730 struct cgraph_edge
*e
= cgraph_edge (node
, stmt
);
735 error ("shared call_stmt:");
736 debug_generic_stmt (stmt
);
739 if (e
->callee
->decl
!= cgraph_node (decl
)->decl
)
741 error ("edge points to wrong declaration:");
742 debug_tree (e
->callee
->decl
);
743 fprintf (stderr
," Instead of:");
750 error ("missing callgraph edge for call stmt:");
751 debug_generic_stmt (stmt
);
756 pointer_set_destroy (visited_nodes
);
757 visited_nodes
= NULL
;
760 /* No CFG available?! */
763 for (e
= node
->callees
; e
; e
= e
->next_callee
)
767 error ("edge %s->%s has no corresponding call_stmt",
768 cgraph_node_name (e
->caller
),
769 cgraph_node_name (e
->callee
));
770 debug_generic_stmt (e
->call_stmt
);
778 dump_cgraph_node (stderr
, node
);
779 internal_error ("verify_cgraph_node failed");
781 timevar_pop (TV_CGRAPH_VERIFY
);
784 /* Verify whole cgraph structure. */
788 struct cgraph_node
*node
;
790 if (sorrycount
|| errorcount
)
793 for (node
= cgraph_nodes
; node
; node
= node
->next
)
794 verify_cgraph_node (node
);
798 /* Output all variables enqueued to be assembled. */
800 cgraph_varpool_assemble_pending_decls (void)
802 bool changed
= false;
804 if (errorcount
|| sorrycount
)
807 /* EH might mark decls as needed during expansion. This should be safe since
808 we don't create references to new function, but it should not be used
810 cgraph_varpool_analyze_pending_decls ();
812 while (cgraph_varpool_nodes_queue
)
814 tree decl
= cgraph_varpool_nodes_queue
->decl
;
815 struct cgraph_varpool_node
*node
= cgraph_varpool_nodes_queue
;
817 cgraph_varpool_nodes_queue
= cgraph_varpool_nodes_queue
->next_needed
;
818 if (!TREE_ASM_WRITTEN (decl
) && !node
->alias
&& !DECL_EXTERNAL (decl
))
820 assemble_variable (decl
, 0, 1, 0);
821 /* Local static variables are never seen by check_global_declarations
822 so we need to output debug info by hand. */
823 if (DECL_CONTEXT (decl
)
824 && (TREE_CODE (DECL_CONTEXT (decl
)) == BLOCK
825 || TREE_CODE (DECL_CONTEXT (decl
)) == FUNCTION_DECL
)
826 && errorcount
== 0 && sorrycount
== 0)
828 timevar_push (TV_SYMOUT
);
829 (*debug_hooks
->global_decl
) (decl
);
830 timevar_pop (TV_SYMOUT
);
834 node
->next_needed
= NULL
;
839 /* Analyze the function scheduled to be output. */
841 cgraph_analyze_function (struct cgraph_node
*node
)
843 tree decl
= node
->decl
;
845 current_function_decl
= decl
;
846 push_cfun (DECL_STRUCT_FUNCTION (decl
));
847 cgraph_lower_function (node
);
849 /* First kill forward declaration so reverse inlining works properly. */
850 cgraph_create_edges (node
, decl
);
852 node
->local
.inlinable
= tree_inlinable_function_p (decl
);
853 node
->local
.self_insns
= estimate_num_insns (decl
);
854 if (node
->local
.inlinable
)
855 node
->local
.disregard_inline_limits
856 = lang_hooks
.tree_inlining
.disregard_inline_limits (decl
);
857 initialize_inline_failed (node
);
858 if (flag_really_no_inline
&& !node
->local
.disregard_inline_limits
)
859 node
->local
.inlinable
= 0;
860 /* Inlining characteristics are maintained by the cgraph_mark_inline. */
861 node
->global
.insns
= node
->local
.self_insns
;
863 node
->analyzed
= true;
865 current_function_decl
= NULL
;
868 /* Analyze the whole compilation unit once it is parsed completely. */
871 cgraph_finalize_compilation_unit (void)
873 struct cgraph_node
*node
;
874 /* Keep track of already processed nodes when called multiple times for
875 intermodule optimization. */
876 static struct cgraph_node
*first_analyzed
;
880 if (!flag_unit_at_a_time
)
882 cgraph_assemble_pending_functions ();
888 fprintf (stderr
, "\nAnalyzing compilation unit");
892 timevar_push (TV_CGRAPH
);
893 cgraph_varpool_analyze_pending_decls ();
894 if (cgraph_dump_file
)
896 fprintf (cgraph_dump_file
, "Initial entry points:");
897 for (node
= cgraph_nodes
; node
!= first_analyzed
; node
= node
->next
)
898 if (node
->needed
&& DECL_SAVED_TREE (node
->decl
))
899 fprintf (cgraph_dump_file
, " %s", cgraph_node_name (node
));
900 fprintf (cgraph_dump_file
, "\n");
903 /* Propagate reachability flag and lower representation of all reachable
904 functions. In the future, lowering will introduce new functions and
905 new entry points on the way (by template instantiation and virtual
906 method table generation for instance). */
907 while (cgraph_nodes_queue
)
909 struct cgraph_edge
*edge
;
910 tree decl
= cgraph_nodes_queue
->decl
;
912 node
= cgraph_nodes_queue
;
913 cgraph_nodes_queue
= cgraph_nodes_queue
->next_needed
;
914 node
->next_needed
= NULL
;
916 /* ??? It is possible to create extern inline function and later using
917 weak alias attribute to kill its body. See
918 gcc.c-torture/compile/20011119-1.c */
919 if (!DECL_SAVED_TREE (decl
))
921 cgraph_reset_node (node
);
925 gcc_assert (!node
->analyzed
&& node
->reachable
);
926 gcc_assert (DECL_SAVED_TREE (decl
));
928 cgraph_analyze_function (node
);
930 for (edge
= node
->callees
; edge
; edge
= edge
->next_callee
)
931 if (!edge
->callee
->reachable
)
932 cgraph_mark_reachable_node (edge
->callee
);
934 cgraph_varpool_analyze_pending_decls ();
937 /* Collect entry points to the unit. */
939 if (cgraph_dump_file
)
941 fprintf (cgraph_dump_file
, "Unit entry points:");
942 for (node
= cgraph_nodes
; node
!= first_analyzed
; node
= node
->next
)
943 if (node
->needed
&& DECL_SAVED_TREE (node
->decl
))
944 fprintf (cgraph_dump_file
, " %s", cgraph_node_name (node
));
945 fprintf (cgraph_dump_file
, "\n\nInitial ");
946 dump_cgraph (cgraph_dump_file
);
949 if (cgraph_dump_file
)
950 fprintf (cgraph_dump_file
, "\nReclaiming functions:");
952 for (node
= cgraph_nodes
; node
!= first_analyzed
; node
= node
->next
)
954 tree decl
= node
->decl
;
956 if (node
->local
.finalized
&& !DECL_SAVED_TREE (decl
))
957 cgraph_reset_node (node
);
959 if (!node
->reachable
&& DECL_SAVED_TREE (decl
))
961 if (cgraph_dump_file
)
962 fprintf (cgraph_dump_file
, " %s", cgraph_node_name (node
));
963 cgraph_remove_node (node
);
967 node
->next_needed
= NULL
;
968 gcc_assert (!node
->local
.finalized
|| DECL_SAVED_TREE (decl
));
969 gcc_assert (node
->analyzed
== node
->local
.finalized
);
971 if (cgraph_dump_file
)
973 fprintf (cgraph_dump_file
, "\n\nReclaimed ");
974 dump_cgraph (cgraph_dump_file
);
976 first_analyzed
= cgraph_nodes
;
978 timevar_pop (TV_CGRAPH
);
980 /* Figure out what functions we want to assemble. */
983 cgraph_mark_functions_to_output (void)
985 struct cgraph_node
*node
;
987 for (node
= cgraph_nodes
; node
; node
= node
->next
)
989 tree decl
= node
->decl
;
990 struct cgraph_edge
*e
;
992 gcc_assert (!node
->output
);
994 for (e
= node
->callers
; e
; e
= e
->next_caller
)
995 if (e
->inline_failed
)
998 /* We need to output all local functions that are used and not
999 always inlined, as well as those that are reachable from
1000 outside the current compilation unit. */
1001 if (DECL_SAVED_TREE (decl
)
1002 && !node
->global
.inlined_to
1004 || (e
&& node
->reachable
))
1005 && !TREE_ASM_WRITTEN (decl
)
1006 && !DECL_EXTERNAL (decl
))
1010 /* We should've reclaimed all functions that are not needed. */
1011 #ifdef ENABLE_CHECKING
1012 if (!node
->global
.inlined_to
&& DECL_SAVED_TREE (decl
)
1013 && !DECL_EXTERNAL (decl
))
1015 dump_cgraph_node (stderr
, node
);
1016 internal_error ("failed to reclaim unneeded function");
1019 gcc_assert (node
->global
.inlined_to
|| !DECL_SAVED_TREE (decl
)
1020 || DECL_EXTERNAL (decl
));
1027 /* Expand function specified by NODE. */
1030 cgraph_expand_function (struct cgraph_node
*node
)
1032 tree decl
= node
->decl
;
1034 /* We ought to not compile any inline clones. */
1035 gcc_assert (!node
->global
.inlined_to
);
1037 if (flag_unit_at_a_time
)
1038 announce_function (decl
);
1040 cgraph_lower_function (node
);
1042 /* Generate RTL for the body of DECL. */
1043 lang_hooks
.callgraph
.expand_function (decl
);
1045 /* Make sure that BE didn't give up on compiling. */
1046 /* ??? Can happen with nested function of extern inline. */
1047 gcc_assert (TREE_ASM_WRITTEN (node
->decl
));
1049 current_function_decl
= NULL
;
1050 if (!cgraph_preserve_function_body_p (node
->decl
))
1052 DECL_SAVED_TREE (node
->decl
) = NULL
;
1053 DECL_STRUCT_FUNCTION (node
->decl
) = NULL
;
1054 DECL_INITIAL (node
->decl
) = error_mark_node
;
1055 /* Eliminate all call edges. This is important so the call_expr no longer
1056 points to the dead function body. */
1057 cgraph_node_remove_callees (node
);
1060 cgraph_function_flags_ready
= true;
1063 /* Return true when CALLER_DECL should be inlined into CALLEE_DECL. */
1066 cgraph_inline_p (struct cgraph_edge
*e
, const char **reason
)
1068 *reason
= e
->inline_failed
;
1069 return !e
->inline_failed
;
1074 /* Expand all functions that must be output.
1076 Attempt to topologically sort the nodes so function is output when
1077 all called functions are already assembled to allow data to be
1078 propagated across the callgraph. Use a stack to get smaller distance
1079 between a function and its callees (later we may choose to use a more
1080 sophisticated algorithm for function reordering; we will likely want
1081 to use subsections to make the output functions appear in top-down
1085 cgraph_expand_all_functions (void)
1087 struct cgraph_node
*node
;
1088 struct cgraph_node
**order
=
1089 xcalloc (cgraph_n_nodes
, sizeof (struct cgraph_node
*));
1090 int order_pos
= 0, new_order_pos
= 0;
1093 order_pos
= cgraph_postorder (order
);
1094 gcc_assert (order_pos
== cgraph_n_nodes
);
1096 /* Garbage collector may remove inline clones we eliminate during
1097 optimization. So we must be sure to not reference them. */
1098 for (i
= 0; i
< order_pos
; i
++)
1099 if (order
[i
]->output
)
1100 order
[new_order_pos
++] = order
[i
];
1102 for (i
= new_order_pos
- 1; i
>= 0; i
--)
1107 gcc_assert (node
->reachable
);
1109 cgraph_expand_function (node
);
1115 /* Mark visibility of all functions.
1117 A local function is one whose calls can occur only in the current
1118 compilation unit and all its calls are explicit, so we can change
1119 its calling convention. We simply mark all static functions whose
1120 address is not taken as local.
1122 We also change the TREE_PUBLIC flag of all declarations that are public
1123 in language point of view but we want to overwrite this default
1124 via visibilities for the backend point of view. */
1127 cgraph_function_and_variable_visibility (void)
1129 struct cgraph_node
*node
;
1130 struct cgraph_varpool_node
*vnode
;
1132 for (node
= cgraph_nodes
; node
; node
= node
->next
)
1135 && (DECL_COMDAT (node
->decl
)
1136 || (!flag_whole_program
1137 && TREE_PUBLIC (node
->decl
) && !DECL_EXTERNAL (node
->decl
))))
1138 node
->local
.externally_visible
= true;
1139 if (!node
->local
.externally_visible
&& node
->analyzed
1140 && !DECL_EXTERNAL (node
->decl
))
1142 gcc_assert (flag_whole_program
|| !TREE_PUBLIC (node
->decl
));
1143 TREE_PUBLIC (node
->decl
) = 0;
1145 node
->local
.local
= (!node
->needed
1147 && !DECL_EXTERNAL (node
->decl
)
1148 && !node
->local
.externally_visible
);
1150 for (vnode
= cgraph_varpool_nodes_queue
; vnode
; vnode
= vnode
->next_needed
)
1153 && !flag_whole_program
1154 && (DECL_COMDAT (vnode
->decl
) || TREE_PUBLIC (vnode
->decl
)))
1155 vnode
->externally_visible
= 1;
1156 if (!vnode
->externally_visible
)
1158 gcc_assert (flag_whole_program
|| !TREE_PUBLIC (vnode
->decl
));
1159 TREE_PUBLIC (vnode
->decl
) = 0;
1161 gcc_assert (TREE_STATIC (vnode
->decl
));
1164 /* Because we have to be conservative on the boundaries of source
1165 level units, it is possible that we marked some functions in
1166 reachable just because they might be used later via external
1167 linkage, but after making them local they are really unreachable
1169 cgraph_remove_unreachable_nodes (true, cgraph_dump_file
);
1171 if (cgraph_dump_file
)
1173 fprintf (cgraph_dump_file
, "\nMarking local functions:");
1174 for (node
= cgraph_nodes
; node
; node
= node
->next
)
1175 if (node
->local
.local
)
1176 fprintf (cgraph_dump_file
, " %s", cgraph_node_name (node
));
1177 fprintf (cgraph_dump_file
, "\n\n");
1178 fprintf (cgraph_dump_file
, "\nMarking externally visible functions:");
1179 for (node
= cgraph_nodes
; node
; node
= node
->next
)
1180 if (node
->local
.externally_visible
)
1181 fprintf (cgraph_dump_file
, " %s", cgraph_node_name (node
));
1182 fprintf (cgraph_dump_file
, "\n\n");
1184 cgraph_function_flags_ready
= true;
1187 /* Return true when function body of DECL still needs to be kept around
1188 for later re-use. */
1190 cgraph_preserve_function_body_p (tree decl
)
1192 struct cgraph_node
*node
;
1193 /* Keep the body; we're going to dump it. */
1194 if (dump_enabled_p (TDI_tree_all
))
1196 if (!cgraph_global_info_ready
)
1197 return (DECL_INLINE (decl
) && !flag_really_no_inline
);
1198 /* Look if there is any clone around. */
1199 for (node
= cgraph_node (decl
); node
; node
= node
->next_clone
)
1200 if (node
->global
.inlined_to
)
1209 tree_register_cfg_hooks ();
1210 bitmap_obstack_initialize (NULL
);
1211 execute_ipa_pass_list (all_ipa_passes
);
1212 bitmap_obstack_release (NULL
);
1215 /* Perform simple optimizations based on callgraph. */
1218 cgraph_optimize (void)
1220 #ifdef ENABLE_CHECKING
1223 if (!flag_unit_at_a_time
)
1225 cgraph_varpool_assemble_pending_decls ();
1229 process_pending_assemble_externals ();
1231 /* Frontend may output common variables after the unit has been finalized.
1232 It is safe to deal with them here as they are always zero initialized. */
1233 cgraph_varpool_analyze_pending_decls ();
1235 timevar_push (TV_CGRAPHOPT
);
1237 fprintf (stderr
, "Performing intraprocedural optimizations\n");
1239 cgraph_function_and_variable_visibility ();
1240 if (cgraph_dump_file
)
1242 fprintf (cgraph_dump_file
, "Marked ");
1243 dump_cgraph (cgraph_dump_file
);
1246 /* This pass remove bodies of extern inline functions we never inlined.
1247 Do this later so other IPA passes see what is really going on. */
1248 cgraph_remove_unreachable_nodes (false, dump_file
);
1249 cgraph_global_info_ready
= true;
1250 if (cgraph_dump_file
)
1252 fprintf (cgraph_dump_file
, "Optimized ");
1253 dump_cgraph (cgraph_dump_file
);
1254 dump_varpool (cgraph_dump_file
);
1256 timevar_pop (TV_CGRAPHOPT
);
1258 /* Output everything. */
1260 fprintf (stderr
, "Assembling functions:\n");
1261 #ifdef ENABLE_CHECKING
1265 cgraph_mark_functions_to_output ();
1266 cgraph_expand_all_functions ();
1267 cgraph_varpool_remove_unreferenced_decls ();
1269 cgraph_varpool_assemble_pending_decls ();
1271 if (cgraph_dump_file
)
1273 fprintf (cgraph_dump_file
, "\nFinal ");
1274 dump_cgraph (cgraph_dump_file
);
1276 #ifdef ENABLE_CHECKING
1278 /* Double check that all inline clones are gone and that all
1279 function bodies have been released from memory. */
1280 if (flag_unit_at_a_time
1281 && !dump_enabled_p (TDI_tree_all
)
1282 && !(sorrycount
|| errorcount
))
1284 struct cgraph_node
*node
;
1285 bool error_found
= false;
1287 for (node
= cgraph_nodes
; node
; node
= node
->next
)
1289 && (node
->global
.inlined_to
1290 || DECL_SAVED_TREE (node
->decl
)))
1293 dump_cgraph_node (stderr
, node
);
1296 internal_error ("nodes with no released memory found");
1301 /* Generate and emit a static constructor or destructor. WHICH must be
1302 one of 'I' or 'D'. BODY should be a STATEMENT_LIST containing
1303 GENERIC statements. */
1306 cgraph_build_static_cdtor (char which
, tree body
, int priority
)
1308 static int counter
= 0;
1310 tree decl
, name
, resdecl
;
1312 sprintf (which_buf
, "%c_%d", which
, counter
++);
1313 name
= get_file_function_name_long (which_buf
);
1315 decl
= build_decl (FUNCTION_DECL
, name
,
1316 build_function_type (void_type_node
, void_list_node
));
1317 current_function_decl
= decl
;
1319 resdecl
= build_decl (RESULT_DECL
, NULL_TREE
, void_type_node
);
1320 DECL_ARTIFICIAL (resdecl
) = 1;
1321 DECL_IGNORED_P (resdecl
) = 1;
1322 DECL_RESULT (decl
) = resdecl
;
1324 allocate_struct_function (decl
);
1326 TREE_STATIC (decl
) = 1;
1327 TREE_USED (decl
) = 1;
1328 DECL_ARTIFICIAL (decl
) = 1;
1329 DECL_IGNORED_P (decl
) = 1;
1330 DECL_NO_INSTRUMENT_FUNCTION_ENTRY_EXIT (decl
) = 1;
1331 DECL_SAVED_TREE (decl
) = body
;
1332 TREE_PUBLIC (decl
) = ! targetm
.have_ctors_dtors
;
1333 DECL_UNINLINABLE (decl
) = 1;
1335 DECL_INITIAL (decl
) = make_node (BLOCK
);
1336 TREE_USED (DECL_INITIAL (decl
)) = 1;
1338 DECL_SOURCE_LOCATION (decl
) = input_location
;
1339 cfun
->function_end_locus
= input_location
;
1344 DECL_STATIC_CONSTRUCTOR (decl
) = 1;
1347 DECL_STATIC_DESTRUCTOR (decl
) = 1;
1353 gimplify_function_tree (decl
);
1355 /* ??? We will get called LATE in the compilation process. */
1356 if (cgraph_global_info_ready
)
1358 tree_lowering_passes (decl
);
1359 tree_rest_of_compilation (decl
);
1362 cgraph_finalize_function (decl
, 0);
1364 if (targetm
.have_ctors_dtors
)
1366 void (*fn
) (rtx
, int);
1369 fn
= targetm
.asm_out
.constructor
;
1371 fn
= targetm
.asm_out
.destructor
;
1372 fn (XEXP (DECL_RTL (decl
), 0), priority
);
1379 cgraph_dump_file
= dump_begin (TDI_cgraph
, NULL
);
1382 /* The edges representing the callers of the NEW_VERSION node were
1383 fixed by cgraph_function_versioning (), now the call_expr in their
1384 respective tree code should be updated to call the NEW_VERSION. */
1387 update_call_expr (struct cgraph_node
*new_version
)
1389 struct cgraph_edge
*e
;
1391 gcc_assert (new_version
);
1392 for (e
= new_version
->callers
; e
; e
= e
->next_caller
)
1393 /* Update the call expr on the edges
1394 to call the new version. */
1395 TREE_OPERAND (TREE_OPERAND (get_call_expr_in (e
->call_stmt
), 0), 0) = new_version
->decl
;
1399 /* Create a new cgraph node which is the new version of
1400 OLD_VERSION node. REDIRECT_CALLERS holds the callers
1401 edges which should be redirected to point to
1402 NEW_VERSION. ALL the callees edges of OLD_VERSION
1403 are cloned to the new version node. Return the new
1406 static struct cgraph_node
*
1407 cgraph_copy_node_for_versioning (struct cgraph_node
*old_version
,
1408 tree new_decl
, varray_type redirect_callers
)
1410 struct cgraph_node
*new_version
;
1411 struct cgraph_edge
*e
, *new_e
;
1412 struct cgraph_edge
*next_callee
;
1415 gcc_assert (old_version
);
1417 new_version
= cgraph_node (new_decl
);
1419 new_version
->analyzed
= true;
1420 new_version
->local
= old_version
->local
;
1421 new_version
->global
= old_version
->global
;
1422 new_version
->rtl
= new_version
->rtl
;
1423 new_version
->reachable
= true;
1424 new_version
->count
= old_version
->count
;
1426 /* Clone the old node callees. Recursive calls are
1428 for (e
= old_version
->callees
;e
; e
=e
->next_callee
)
1430 new_e
= cgraph_clone_edge (e
, new_version
, e
->call_stmt
, 0, e
->loop_nest
, true);
1431 new_e
->count
= e
->count
;
1433 /* Fix recursive calls.
1434 If OLD_VERSION has a recursive call after the
1435 previous edge cloning, the new version will have an edge
1436 pointing to the old version, which is wrong;
1437 Redirect it to point to the new version. */
1438 for (e
= new_version
->callees
; e
; e
= next_callee
)
1440 next_callee
= e
->next_callee
;
1441 if (e
->callee
== old_version
)
1442 cgraph_redirect_edge_callee (e
, new_version
);
1447 if (redirect_callers
)
1448 for (i
= 0; i
< VARRAY_ACTIVE_SIZE (redirect_callers
); i
++)
1450 e
= VARRAY_GENERIC_PTR (redirect_callers
, i
);
1451 /* Redirect calls to the old version node
1452 to point to it's new version. */
1453 cgraph_redirect_edge_callee (e
, new_version
);
1459 /* Perform function versioning.
1460 Function versioning includes copying of the tree and
1461 a callgraph update (creating a new cgraph node and updating
1462 its callees and callers).
1464 REDIRECT_CALLERS varray includes the edges to be redirected
1467 TREE_MAP is a mapping of tree nodes we want to replace with
1468 new ones (according to results of prior analysis).
1469 OLD_VERSION_NODE is the node that is versioned.
1470 It returns the new version's cgraph node. */
1472 struct cgraph_node
*
1473 cgraph_function_versioning (struct cgraph_node
*old_version_node
,
1474 varray_type redirect_callers
,
1475 varray_type tree_map
)
1477 tree old_decl
= old_version_node
->decl
;
1478 struct cgraph_node
*new_version_node
= NULL
;
1481 if (!tree_versionable_function_p (old_decl
))
1484 /* Make a new FUNCTION_DECL tree node for the
1486 new_decl
= copy_node (old_decl
);
1488 /* Create the new version's call-graph node.
1489 and update the edges of the new node. */
1491 cgraph_copy_node_for_versioning (old_version_node
, new_decl
,
1494 /* Copy the OLD_VERSION_NODE function tree to the new version. */
1495 tree_function_versioning (old_decl
, new_decl
, tree_map
);
1496 /* Update the call_expr on the edges to call the new version node. */
1497 update_call_expr (new_version_node
);
1499 /* Update the new version's properties.
1500 Make The new version visible only within this translation unit.
1501 ??? We cannot use COMDAT linkage because there is no
1502 ABI support for this. */
1503 DECL_EXTERNAL (new_version_node
->decl
) = 0;
1504 DECL_ONE_ONLY (new_version_node
->decl
) = 0;
1505 TREE_PUBLIC (new_version_node
->decl
) = 0;
1506 DECL_COMDAT (new_version_node
->decl
) = 0;
1507 new_version_node
->local
.externally_visible
= 0;
1508 new_version_node
->local
.local
= 1;
1509 new_version_node
->lowered
= true;
1510 return new_version_node
;