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 "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
)
192 if (MAIN_NAME_P (DECL_NAME (decl
))
193 && TREE_PUBLIC (decl
))
195 node
->local
.externally_visible
= true;
199 /* If the user told us it is used, then it must be so. */
200 if (node
->local
.externally_visible
201 || lookup_attribute ("used", DECL_ATTRIBUTES (decl
)))
204 /* ??? If the assembler name is set by hand, it is possible to assemble
205 the name later after finalizing the function and the fact is noticed
206 in assemble_name then. This is arguably a bug. */
207 if (DECL_ASSEMBLER_NAME_SET_P (decl
)
208 && TREE_SYMBOL_REFERENCED (DECL_ASSEMBLER_NAME (decl
)))
211 /* If we decided it was needed before, but at the time we didn't have
212 the body of the function available, then it's still needed. We have
213 to go back and re-check its dependencies now. */
217 /* Externally visible functions must be output. The exception is
218 COMDAT functions that must be output only when they are needed. */
219 if ((TREE_PUBLIC (decl
) && !flag_whole_program
)
220 && !DECL_COMDAT (decl
) && !DECL_EXTERNAL (decl
))
223 /* Constructors and destructors are reachable from the runtime by
225 if (DECL_STATIC_CONSTRUCTOR (decl
) || DECL_STATIC_DESTRUCTOR (decl
))
228 if (flag_unit_at_a_time
)
231 /* If not doing unit at a time, then we'll only defer this function
232 if its marked for inlining. Otherwise we want to emit it now. */
234 /* "extern inline" functions are never output locally. */
235 if (DECL_EXTERNAL (decl
))
237 /* Nested functions of extern inline function shall not be emit unless
238 we inlined the origin. */
239 for (origin
= decl_function_context (decl
); origin
;
240 origin
= decl_function_context (origin
))
241 if (DECL_EXTERNAL (origin
))
243 /* We want to emit COMDAT functions only when absolutely necessary. */
244 if (DECL_COMDAT (decl
))
246 if (!DECL_INLINE (decl
)
247 || (!node
->local
.disregard_inline_limits
248 /* When declared inline, defer even the uninlinable functions.
249 This allows them to be eliminated when unused. */
250 && !DECL_DECLARED_INLINE_P (decl
)
251 && (!node
->local
.inlinable
|| !cgraph_default_inline_p (node
))))
257 /* Walk the decls we marked as necessary and see if they reference new
258 variables or functions and add them into the worklists. */
260 cgraph_varpool_analyze_pending_decls (void)
262 bool changed
= false;
263 timevar_push (TV_CGRAPH
);
265 while (cgraph_varpool_first_unanalyzed_node
)
267 tree decl
= cgraph_varpool_first_unanalyzed_node
->decl
;
269 cgraph_varpool_first_unanalyzed_node
->analyzed
= true;
271 cgraph_varpool_first_unanalyzed_node
= cgraph_varpool_first_unanalyzed_node
->next_needed
;
273 if (DECL_INITIAL (decl
))
275 visited_nodes
= pointer_set_create ();
276 walk_tree (&DECL_INITIAL (decl
), record_reference
, NULL
, visited_nodes
);
277 pointer_set_destroy (visited_nodes
);
278 visited_nodes
= NULL
;
282 timevar_pop (TV_CGRAPH
);
286 /* Optimization of function bodies might've rendered some variables as
287 unnecessary so we want to avoid these from being compiled.
289 This is done by pruning the queue and keeping only the variables that
290 really appear needed (ie they are either externally visible or referenced
291 by compiled function). Re-doing the reachability analysis on variables
292 brings back the remaining variables referenced by these. */
294 cgraph_varpool_remove_unreferenced_decls (void)
296 struct cgraph_varpool_node
*next
, *node
= cgraph_varpool_nodes_queue
;
298 cgraph_varpool_reset_queue ();
300 if (errorcount
|| sorrycount
)
305 tree decl
= node
->decl
;
306 next
= node
->next_needed
;
310 && ((DECL_ASSEMBLER_NAME_SET_P (decl
)
311 && TREE_SYMBOL_REFERENCED (DECL_ASSEMBLER_NAME (decl
)))
312 || node
->force_output
313 || decide_is_variable_needed (node
, decl
)))
314 cgraph_varpool_mark_needed_node (node
);
318 cgraph_varpool_analyze_pending_decls ();
322 /* When not doing unit-at-a-time, output all functions enqueued.
323 Return true when such a functions were found. */
326 cgraph_assemble_pending_functions (void)
330 if (flag_unit_at_a_time
)
333 while (cgraph_nodes_queue
)
335 struct cgraph_node
*n
= cgraph_nodes_queue
;
337 cgraph_nodes_queue
= cgraph_nodes_queue
->next_needed
;
338 n
->next_needed
= NULL
;
339 if (!n
->global
.inlined_to
341 && !DECL_EXTERNAL (n
->decl
))
343 cgraph_expand_function (n
);
350 /* As an GCC extension we allow redefinition of the function. The
351 semantics when both copies of bodies differ is not well defined.
352 We replace the old body with new body so in unit at a time mode
353 we always use new body, while in normal mode we may end up with
354 old body inlined into some functions and new body expanded and
357 ??? It may make more sense to use one body for inlining and other
358 body for expanding the function but this is difficult to do. */
361 cgraph_reset_node (struct cgraph_node
*node
)
363 /* If node->output is set, then this is a unit-at-a-time compilation
364 and we have already begun whole-unit analysis. This is *not*
365 testing for whether we've already emitted the function. That
366 case can be sort-of legitimately seen with real function
367 redefinition errors. I would argue that the front end should
368 never present us with such a case, but don't enforce that for now. */
369 gcc_assert (!node
->output
);
371 /* Reset our data structures so we can analyze the function again. */
372 memset (&node
->local
, 0, sizeof (node
->local
));
373 memset (&node
->global
, 0, sizeof (node
->global
));
374 memset (&node
->rtl
, 0, sizeof (node
->rtl
));
375 node
->analyzed
= false;
376 node
->local
.redefined_extern_inline
= true;
377 node
->local
.finalized
= false;
379 if (!flag_unit_at_a_time
)
381 struct cgraph_node
*n
;
383 for (n
= cgraph_nodes
; n
; n
= n
->next
)
384 if (n
->global
.inlined_to
== node
)
385 cgraph_remove_node (n
);
388 cgraph_node_remove_callees (node
);
390 /* We may need to re-queue the node for assembling in case
391 we already proceeded it and ignored as not needed. */
392 if (node
->reachable
&& !flag_unit_at_a_time
)
394 struct cgraph_node
*n
;
396 for (n
= cgraph_nodes_queue
; n
; n
= n
->next_needed
)
404 /* DECL has been parsed. Take it, queue it, compile it at the whim of the
405 logic in effect. If NESTED is true, then our caller cannot stand to have
406 the garbage collector run at the moment. We would need to either create
407 a new GC context, or just not compile right now. */
410 cgraph_finalize_function (tree decl
, bool nested
)
412 struct cgraph_node
*node
= cgraph_node (decl
);
414 if (node
->local
.finalized
)
415 cgraph_reset_node (node
);
417 notice_global_symbol (decl
);
419 node
->local
.finalized
= true;
420 node
->lowered
= DECL_STRUCT_FUNCTION (decl
)->cfg
!= NULL
;
422 lower_nested_functions (decl
);
423 gcc_assert (!node
->nested
);
425 /* If not unit at a time, then we need to create the call graph
426 now, so that called functions can be queued and emitted now. */
427 if (!flag_unit_at_a_time
)
429 cgraph_analyze_function (node
);
430 cgraph_decide_inlining_incrementally (node
, false);
433 if (decide_is_function_needed (node
, decl
))
434 cgraph_mark_needed_node (node
);
436 /* Since we reclaim unreachable nodes at the end of every language
437 level unit, we need to be conservative about possible entry points
439 if ((TREE_PUBLIC (decl
) && !DECL_COMDAT (decl
) && !DECL_EXTERNAL (decl
)))
440 cgraph_mark_reachable_node (node
);
442 /* If not unit at a time, go ahead and emit everything we've found
443 to be reachable at this time. */
446 if (!cgraph_assemble_pending_functions ())
450 /* If we've not yet emitted decl, tell the debug info about it. */
451 if (!TREE_ASM_WRITTEN (decl
))
452 (*debug_hooks
->deferred_inline_function
) (decl
);
454 /* Possibly warn about unused parameters. */
455 if (warn_unused_parameter
)
456 do_warn_unused_parameter (decl
);
460 cgraph_lower_function (struct cgraph_node
*node
)
464 tree_lowering_passes (node
->decl
);
465 node
->lowered
= true;
468 /* Walk tree and record all calls. Called via walk_tree. */
470 record_reference (tree
*tp
, int *walk_subtrees
, void *data
)
474 switch (TREE_CODE (t
))
477 /* ??? Really, we should mark this decl as *potentially* referenced
478 by this function and re-examine whether the decl is actually used
479 after rtl has been generated. */
480 if (TREE_STATIC (t
) || DECL_EXTERNAL (t
))
482 cgraph_varpool_mark_needed_node (cgraph_varpool_node (t
));
483 if (lang_hooks
.callgraph
.analyze_expr
)
484 return lang_hooks
.callgraph
.analyze_expr (tp
, walk_subtrees
,
491 if (flag_unit_at_a_time
)
493 /* Record dereferences to the functions. This makes the
494 functions reachable unconditionally. */
495 tree decl
= TREE_OPERAND (*tp
, 0);
496 if (TREE_CODE (decl
) == FUNCTION_DECL
)
497 cgraph_mark_needed_node (cgraph_node (decl
));
502 /* Save some cycles by not walking types and declaration as we
503 won't find anything useful there anyway. */
504 if (IS_TYPE_OR_DECL_P (*tp
))
510 if ((unsigned int) TREE_CODE (t
) >= LAST_AND_UNUSED_TREE_CODE
)
511 return lang_hooks
.callgraph
.analyze_expr (tp
, walk_subtrees
, data
);
518 /* Create cgraph edges for function calls inside BODY from NODE. */
521 cgraph_create_edges (struct cgraph_node
*node
, tree body
)
525 struct function
*this_cfun
= DECL_STRUCT_FUNCTION (body
);
526 block_stmt_iterator bsi
;
528 visited_nodes
= pointer_set_create ();
530 /* Reach the trees by walking over the CFG, and note the
531 enclosing basic-blocks in the call edges. */
532 FOR_EACH_BB_FN (bb
, this_cfun
)
533 for (bsi
= bsi_start (bb
); !bsi_end_p (bsi
); bsi_next (&bsi
))
535 tree stmt
= bsi_stmt (bsi
);
536 tree call
= get_call_expr_in (stmt
);
539 if (call
&& (decl
= get_callee_fndecl (call
)))
541 cgraph_create_edge (node
, cgraph_node (decl
), stmt
,
544 walk_tree (&TREE_OPERAND (call
, 1),
545 record_reference
, node
, visited_nodes
);
546 if (TREE_CODE (stmt
) == MODIFY_EXPR
)
547 walk_tree (&TREE_OPERAND (stmt
, 0),
548 record_reference
, node
, visited_nodes
);
551 walk_tree (bsi_stmt_ptr (bsi
), record_reference
, node
, visited_nodes
);
554 /* Look for initializers of constant variables and private statics. */
555 for (step
= DECL_STRUCT_FUNCTION (body
)->unexpanded_var_list
;
557 step
= TREE_CHAIN (step
))
559 tree decl
= TREE_VALUE (step
);
560 if (TREE_CODE (decl
) == VAR_DECL
561 && (TREE_STATIC (decl
) && !DECL_EXTERNAL (decl
))
562 && flag_unit_at_a_time
)
563 cgraph_varpool_finalize_decl (decl
);
564 else if (TREE_CODE (decl
) == VAR_DECL
&& DECL_INITIAL (decl
))
565 walk_tree (&DECL_INITIAL (decl
), record_reference
, node
, visited_nodes
);
568 pointer_set_destroy (visited_nodes
);
569 visited_nodes
= NULL
;
572 /* Give initial reasons why inlining would fail. Those gets
573 either NULLified or usually overwritten by more precise reason
576 initialize_inline_failed (struct cgraph_node
*node
)
578 struct cgraph_edge
*e
;
580 for (e
= node
->callers
; e
; e
= e
->next_caller
)
582 gcc_assert (!e
->callee
->global
.inlined_to
);
583 gcc_assert (e
->inline_failed
);
584 if (node
->local
.redefined_extern_inline
)
585 e
->inline_failed
= N_("redefined extern inline functions are not "
586 "considered for inlining");
587 else if (!node
->local
.inlinable
)
588 e
->inline_failed
= N_("function not inlinable");
590 e
->inline_failed
= N_("function not considered for inlining");
594 /* Rebuild call edges from current function after a passes not aware
595 of cgraph updating. */
597 rebuild_cgraph_edges (void)
600 struct cgraph_node
*node
= cgraph_node (current_function_decl
);
601 block_stmt_iterator bsi
;
603 cgraph_node_remove_callees (node
);
605 node
->count
= ENTRY_BLOCK_PTR
->count
;
608 for (bsi
= bsi_start (bb
); !bsi_end_p (bsi
); bsi_next (&bsi
))
610 tree stmt
= bsi_stmt (bsi
);
611 tree call
= get_call_expr_in (stmt
);
614 if (call
&& (decl
= get_callee_fndecl (call
)))
615 cgraph_create_edge (node
, cgraph_node (decl
), stmt
,
619 initialize_inline_failed (node
);
620 gcc_assert (!node
->global
.inlined_to
);
623 struct tree_opt_pass pass_rebuild_cgraph_edges
=
627 rebuild_cgraph_edges
, /* execute */
630 0, /* static_pass_number */
632 PROP_cfg
, /* properties_required */
633 0, /* properties_provided */
634 0, /* properties_destroyed */
635 0, /* todo_flags_start */
636 0, /* todo_flags_finish */
640 /* Verify cgraph nodes of given cgraph node. */
642 verify_cgraph_node (struct cgraph_node
*node
)
644 struct cgraph_edge
*e
;
645 struct cgraph_node
*main_clone
;
646 struct function
*this_cfun
= DECL_STRUCT_FUNCTION (node
->decl
);
647 basic_block this_block
;
648 block_stmt_iterator bsi
;
649 bool error_found
= false;
651 timevar_push (TV_CGRAPH_VERIFY
);
652 for (e
= node
->callees
; e
; e
= e
->next_callee
)
655 error ("aux field set for edge %s->%s",
656 cgraph_node_name (e
->caller
), cgraph_node_name (e
->callee
));
659 for (e
= node
->callers
; e
; e
= e
->next_caller
)
661 if (!e
->inline_failed
)
663 if (node
->global
.inlined_to
664 != (e
->caller
->global
.inlined_to
665 ? e
->caller
->global
.inlined_to
: e
->caller
))
667 error ("inlined_to pointer is wrong");
670 if (node
->callers
->next_caller
)
672 error ("multiple inline callers");
677 if (node
->global
.inlined_to
)
679 error ("inlined_to pointer set for noninline callers");
683 if (!node
->callers
&& node
->global
.inlined_to
)
685 error ("inlined_to pointer is set but no predecesors found");
688 if (node
->global
.inlined_to
== node
)
690 error ("inlined_to pointer refers to itself");
694 for (main_clone
= cgraph_node (node
->decl
); main_clone
;
695 main_clone
= main_clone
->next_clone
)
696 if (main_clone
== node
)
700 error ("node not found in DECL_ASSEMBLER_NAME hash");
705 && DECL_SAVED_TREE (node
->decl
) && !TREE_ASM_WRITTEN (node
->decl
)
706 && (!DECL_EXTERNAL (node
->decl
) || node
->global
.inlined_to
))
710 /* The nodes we're interested in are never shared, so walk
711 the tree ignoring duplicates. */
712 visited_nodes
= pointer_set_create ();
713 /* Reach the trees by walking over the CFG, and note the
714 enclosing basic-blocks in the call edges. */
715 FOR_EACH_BB_FN (this_block
, this_cfun
)
716 for (bsi
= bsi_start (this_block
); !bsi_end_p (bsi
); bsi_next (&bsi
))
718 tree stmt
= bsi_stmt (bsi
);
719 tree call
= get_call_expr_in (stmt
);
721 if (call
&& (decl
= get_callee_fndecl (call
)))
723 struct cgraph_edge
*e
= cgraph_edge (node
, stmt
);
728 error ("shared call_stmt:");
729 debug_generic_stmt (stmt
);
732 if (e
->callee
->decl
!= cgraph_node (decl
)->decl
)
734 error ("edge points to wrong declaration:");
735 debug_tree (e
->callee
->decl
);
736 fprintf (stderr
," Instead of:");
743 error ("missing callgraph edge for call stmt:");
744 debug_generic_stmt (stmt
);
749 pointer_set_destroy (visited_nodes
);
750 visited_nodes
= NULL
;
753 /* No CFG available?! */
756 for (e
= node
->callees
; e
; e
= e
->next_callee
)
760 error ("edge %s->%s has no corresponding call_stmt",
761 cgraph_node_name (e
->caller
),
762 cgraph_node_name (e
->callee
));
763 debug_generic_stmt (e
->call_stmt
);
771 dump_cgraph_node (stderr
, node
);
772 internal_error ("verify_cgraph_node failed");
774 timevar_pop (TV_CGRAPH_VERIFY
);
777 /* Verify whole cgraph structure. */
781 struct cgraph_node
*node
;
783 if (sorrycount
|| errorcount
)
786 for (node
= cgraph_nodes
; node
; node
= node
->next
)
787 verify_cgraph_node (node
);
791 /* Output all variables enqueued to be assembled. */
793 cgraph_varpool_assemble_pending_decls (void)
795 bool changed
= false;
797 if (errorcount
|| sorrycount
)
800 /* EH might mark decls as needed during expansion. This should be safe since
801 we don't create references to new function, but it should not be used
803 cgraph_varpool_analyze_pending_decls ();
805 while (cgraph_varpool_nodes_queue
)
807 tree decl
= cgraph_varpool_nodes_queue
->decl
;
808 struct cgraph_varpool_node
*node
= cgraph_varpool_nodes_queue
;
810 cgraph_varpool_nodes_queue
= cgraph_varpool_nodes_queue
->next_needed
;
811 if (!TREE_ASM_WRITTEN (decl
) && !node
->alias
&& !DECL_EXTERNAL (decl
))
813 assemble_variable (decl
, 0, 1, 0);
814 /* Local static variables are never seen by check_global_declarations
815 so we need to output debug info by hand. */
816 if (decl_function_context (decl
) && errorcount
== 0 && sorrycount
== 0)
818 timevar_push (TV_SYMOUT
);
819 (*debug_hooks
->global_decl
) (decl
);
820 timevar_pop (TV_SYMOUT
);
824 node
->next_needed
= NULL
;
829 /* Analyze the function scheduled to be output. */
831 cgraph_analyze_function (struct cgraph_node
*node
)
833 tree decl
= node
->decl
;
835 current_function_decl
= decl
;
836 push_cfun (DECL_STRUCT_FUNCTION (decl
));
837 cgraph_lower_function (node
);
839 /* First kill forward declaration so reverse inlining works properly. */
840 cgraph_create_edges (node
, decl
);
842 node
->local
.inlinable
= tree_inlinable_function_p (decl
);
843 node
->local
.self_insns
= estimate_num_insns (decl
);
844 if (node
->local
.inlinable
)
845 node
->local
.disregard_inline_limits
846 = lang_hooks
.tree_inlining
.disregard_inline_limits (decl
);
847 initialize_inline_failed (node
);
848 if (flag_really_no_inline
&& !node
->local
.disregard_inline_limits
)
849 node
->local
.inlinable
= 0;
850 /* Inlining characteristics are maintained by the cgraph_mark_inline. */
851 node
->global
.insns
= node
->local
.self_insns
;
853 node
->analyzed
= true;
855 current_function_decl
= NULL
;
858 /* Analyze the whole compilation unit once it is parsed completely. */
861 cgraph_finalize_compilation_unit (void)
863 struct cgraph_node
*node
;
864 /* Keep track of already processed nodes when called multiple times for
865 intermodule optimization. */
866 static struct cgraph_node
*first_analyzed
;
870 if (!flag_unit_at_a_time
)
872 cgraph_assemble_pending_functions ();
878 fprintf (stderr
, "\nAnalyzing compilation unit");
882 timevar_push (TV_CGRAPH
);
883 cgraph_varpool_analyze_pending_decls ();
884 if (cgraph_dump_file
)
886 fprintf (cgraph_dump_file
, "Initial entry points:");
887 for (node
= cgraph_nodes
; node
!= first_analyzed
; node
= node
->next
)
888 if (node
->needed
&& DECL_SAVED_TREE (node
->decl
))
889 fprintf (cgraph_dump_file
, " %s", cgraph_node_name (node
));
890 fprintf (cgraph_dump_file
, "\n");
893 /* Propagate reachability flag and lower representation of all reachable
894 functions. In the future, lowering will introduce new functions and
895 new entry points on the way (by template instantiation and virtual
896 method table generation for instance). */
897 while (cgraph_nodes_queue
)
899 struct cgraph_edge
*edge
;
900 tree decl
= cgraph_nodes_queue
->decl
;
902 node
= cgraph_nodes_queue
;
903 cgraph_nodes_queue
= cgraph_nodes_queue
->next_needed
;
904 node
->next_needed
= NULL
;
906 /* ??? It is possible to create extern inline function and later using
907 weak alias attribute to kill its body. See
908 gcc.c-torture/compile/20011119-1.c */
909 if (!DECL_SAVED_TREE (decl
))
911 cgraph_reset_node (node
);
915 gcc_assert (!node
->analyzed
&& node
->reachable
);
916 gcc_assert (DECL_SAVED_TREE (decl
));
918 cgraph_analyze_function (node
);
920 for (edge
= node
->callees
; edge
; edge
= edge
->next_callee
)
921 if (!edge
->callee
->reachable
)
922 cgraph_mark_reachable_node (edge
->callee
);
924 cgraph_varpool_analyze_pending_decls ();
927 /* Collect entry points to the unit. */
929 if (cgraph_dump_file
)
931 fprintf (cgraph_dump_file
, "Unit entry points:");
932 for (node
= cgraph_nodes
; node
!= first_analyzed
; node
= node
->next
)
933 if (node
->needed
&& DECL_SAVED_TREE (node
->decl
))
934 fprintf (cgraph_dump_file
, " %s", cgraph_node_name (node
));
935 fprintf (cgraph_dump_file
, "\n\nInitial ");
936 dump_cgraph (cgraph_dump_file
);
939 if (cgraph_dump_file
)
940 fprintf (cgraph_dump_file
, "\nReclaiming functions:");
942 for (node
= cgraph_nodes
; node
!= first_analyzed
; node
= node
->next
)
944 tree decl
= node
->decl
;
946 if (node
->local
.finalized
&& !DECL_SAVED_TREE (decl
))
947 cgraph_reset_node (node
);
949 if (!node
->reachable
&& DECL_SAVED_TREE (decl
))
951 if (cgraph_dump_file
)
952 fprintf (cgraph_dump_file
, " %s", cgraph_node_name (node
));
953 cgraph_remove_node (node
);
957 node
->next_needed
= NULL
;
958 gcc_assert (!node
->local
.finalized
|| DECL_SAVED_TREE (decl
));
959 gcc_assert (node
->analyzed
== node
->local
.finalized
);
961 if (cgraph_dump_file
)
963 fprintf (cgraph_dump_file
, "\n\nReclaimed ");
964 dump_cgraph (cgraph_dump_file
);
966 first_analyzed
= cgraph_nodes
;
968 timevar_pop (TV_CGRAPH
);
970 /* Figure out what functions we want to assemble. */
973 cgraph_mark_functions_to_output (void)
975 struct cgraph_node
*node
;
977 for (node
= cgraph_nodes
; node
; node
= node
->next
)
979 tree decl
= node
->decl
;
980 struct cgraph_edge
*e
;
982 gcc_assert (!node
->output
);
984 for (e
= node
->callers
; e
; e
= e
->next_caller
)
985 if (e
->inline_failed
)
988 /* We need to output all local functions that are used and not
989 always inlined, as well as those that are reachable from
990 outside the current compilation unit. */
991 if (DECL_SAVED_TREE (decl
)
992 && !node
->global
.inlined_to
994 || (e
&& node
->reachable
))
995 && !TREE_ASM_WRITTEN (decl
)
996 && !DECL_EXTERNAL (decl
))
1000 /* We should've reclaimed all functions that are not needed. */
1001 #ifdef ENABLE_CHECKING
1002 if (!node
->global
.inlined_to
&& DECL_SAVED_TREE (decl
)
1003 && !DECL_EXTERNAL (decl
))
1005 dump_cgraph_node (stderr
, node
);
1006 internal_error ("failed to reclaim unneeded function");
1009 gcc_assert (node
->global
.inlined_to
|| !DECL_SAVED_TREE (decl
)
1010 || DECL_EXTERNAL (decl
));
1017 /* Expand function specified by NODE. */
1020 cgraph_expand_function (struct cgraph_node
*node
)
1022 tree decl
= node
->decl
;
1024 /* We ought to not compile any inline clones. */
1025 gcc_assert (!node
->global
.inlined_to
);
1027 if (flag_unit_at_a_time
)
1028 announce_function (decl
);
1030 cgraph_lower_function (node
);
1032 /* Generate RTL for the body of DECL. */
1033 lang_hooks
.callgraph
.expand_function (decl
);
1035 /* Make sure that BE didn't give up on compiling. */
1036 /* ??? Can happen with nested function of extern inline. */
1037 gcc_assert (TREE_ASM_WRITTEN (node
->decl
));
1039 current_function_decl
= NULL
;
1040 if (!cgraph_preserve_function_body_p (node
->decl
))
1042 DECL_SAVED_TREE (node
->decl
) = NULL
;
1043 DECL_STRUCT_FUNCTION (node
->decl
) = NULL
;
1044 DECL_INITIAL (node
->decl
) = error_mark_node
;
1045 /* Eliminate all call edges. This is important so the call_expr no longer
1046 points to the dead function body. */
1047 cgraph_node_remove_callees (node
);
1050 cgraph_function_flags_ready
= true;
1053 /* Return true when CALLER_DECL should be inlined into CALLEE_DECL. */
1056 cgraph_inline_p (struct cgraph_edge
*e
, const char **reason
)
1058 *reason
= e
->inline_failed
;
1059 return !e
->inline_failed
;
1064 /* Expand all functions that must be output.
1066 Attempt to topologically sort the nodes so function is output when
1067 all called functions are already assembled to allow data to be
1068 propagated across the callgraph. Use a stack to get smaller distance
1069 between a function and its callees (later we may choose to use a more
1070 sophisticated algorithm for function reordering; we will likely want
1071 to use subsections to make the output functions appear in top-down
1075 cgraph_expand_all_functions (void)
1077 struct cgraph_node
*node
;
1078 struct cgraph_node
**order
=
1079 xcalloc (cgraph_n_nodes
, sizeof (struct cgraph_node
*));
1080 int order_pos
= 0, new_order_pos
= 0;
1083 order_pos
= cgraph_postorder (order
);
1084 gcc_assert (order_pos
== cgraph_n_nodes
);
1086 /* Garbage collector may remove inline clones we eliminate during
1087 optimization. So we must be sure to not reference them. */
1088 for (i
= 0; i
< order_pos
; i
++)
1089 if (order
[i
]->output
)
1090 order
[new_order_pos
++] = order
[i
];
1092 for (i
= new_order_pos
- 1; i
>= 0; i
--)
1097 gcc_assert (node
->reachable
);
1099 cgraph_expand_function (node
);
1105 /* Mark visibility of all functions.
1107 A local function is one whose calls can occur only in the current
1108 compilation unit and all its calls are explicit, so we can change
1109 its calling convention. We simply mark all static functions whose
1110 address is not taken as local.
1112 We also change the TREE_PUBLIC flag of all declarations that are public
1113 in language point of view but we want to overwrite this default
1114 via visibilities for the backend point of view. */
1117 cgraph_function_and_variable_visibility (void)
1119 struct cgraph_node
*node
;
1120 struct cgraph_varpool_node
*vnode
;
1122 for (node
= cgraph_nodes
; node
; node
= node
->next
)
1125 && (DECL_COMDAT (node
->decl
)
1126 || (TREE_PUBLIC (node
->decl
) && !DECL_EXTERNAL (node
->decl
))))
1127 node
->local
.externally_visible
= true;
1128 if (!node
->local
.externally_visible
&& node
->analyzed
1129 && !DECL_EXTERNAL (node
->decl
))
1131 gcc_assert (flag_whole_program
|| !TREE_PUBLIC (node
->decl
));
1132 TREE_PUBLIC (node
->decl
) = 0;
1134 node
->local
.local
= (!node
->needed
1136 && !DECL_EXTERNAL (node
->decl
)
1137 && !node
->local
.externally_visible
);
1139 for (vnode
= cgraph_varpool_nodes_queue
; vnode
; vnode
= vnode
->next_needed
)
1142 && (DECL_COMDAT (vnode
->decl
) || TREE_PUBLIC (vnode
->decl
)))
1143 vnode
->externally_visible
= 1;
1144 if (!vnode
->externally_visible
)
1146 gcc_assert (flag_whole_program
|| !TREE_PUBLIC (vnode
->decl
));
1147 TREE_PUBLIC (vnode
->decl
) = 0;
1149 gcc_assert (TREE_STATIC (vnode
->decl
));
1152 /* Because we have to be conservative on the boundaries of source
1153 level units, it is possible that we marked some functions in
1154 reachable just because they might be used later via external
1155 linkage, but after making them local they are really unreachable
1157 cgraph_remove_unreachable_nodes (true, cgraph_dump_file
);
1159 if (cgraph_dump_file
)
1161 fprintf (cgraph_dump_file
, "\nMarking local functions:");
1162 for (node
= cgraph_nodes
; node
; node
= node
->next
)
1163 if (node
->local
.local
)
1164 fprintf (cgraph_dump_file
, " %s", cgraph_node_name (node
));
1165 fprintf (cgraph_dump_file
, "\n\n");
1166 fprintf (cgraph_dump_file
, "\nMarking externally visible functions:");
1167 for (node
= cgraph_nodes
; node
; node
= node
->next
)
1168 if (node
->local
.externally_visible
)
1169 fprintf (cgraph_dump_file
, " %s", cgraph_node_name (node
));
1170 fprintf (cgraph_dump_file
, "\n\n");
1172 cgraph_function_flags_ready
= true;
1175 /* Return true when function body of DECL still needs to be kept around
1176 for later re-use. */
1178 cgraph_preserve_function_body_p (tree decl
)
1180 struct cgraph_node
*node
;
1181 /* Keep the body; we're going to dump it. */
1182 if (dump_enabled_p (TDI_tree_all
))
1184 if (!cgraph_global_info_ready
)
1185 return (DECL_INLINE (decl
) && !flag_really_no_inline
);
1186 /* Look if there is any clone around. */
1187 for (node
= cgraph_node (decl
); node
; node
= node
->next_clone
)
1188 if (node
->global
.inlined_to
)
1197 tree_register_cfg_hooks ();
1198 bitmap_obstack_initialize (NULL
);
1199 execute_ipa_pass_list (all_ipa_passes
);
1200 bitmap_obstack_release (NULL
);
1203 /* Perform simple optimizations based on callgraph. */
1206 cgraph_optimize (void)
1208 #ifdef ENABLE_CHECKING
1211 if (!flag_unit_at_a_time
)
1213 cgraph_varpool_assemble_pending_decls ();
1217 process_pending_assemble_externals ();
1219 /* Frontend may output common variables after the unit has been finalized.
1220 It is safe to deal with them here as they are always zero initialized. */
1221 cgraph_varpool_analyze_pending_decls ();
1223 timevar_push (TV_CGRAPHOPT
);
1225 fprintf (stderr
, "Performing intraprocedural optimizations\n");
1227 cgraph_function_and_variable_visibility ();
1228 if (cgraph_dump_file
)
1230 fprintf (cgraph_dump_file
, "Marked ");
1231 dump_cgraph (cgraph_dump_file
);
1234 /* This pass remove bodies of extern inline functions we never inlined.
1235 Do this later so other IPA passes see what is really going on. */
1236 cgraph_remove_unreachable_nodes (false, dump_file
);
1237 cgraph_global_info_ready
= true;
1238 if (cgraph_dump_file
)
1240 fprintf (cgraph_dump_file
, "Optimized ");
1241 dump_cgraph (cgraph_dump_file
);
1242 dump_varpool (cgraph_dump_file
);
1244 timevar_pop (TV_CGRAPHOPT
);
1246 /* Output everything. */
1248 fprintf (stderr
, "Assembling functions:\n");
1249 #ifdef ENABLE_CHECKING
1253 cgraph_mark_functions_to_output ();
1254 cgraph_expand_all_functions ();
1255 cgraph_varpool_remove_unreferenced_decls ();
1257 cgraph_varpool_assemble_pending_decls ();
1259 if (cgraph_dump_file
)
1261 fprintf (cgraph_dump_file
, "\nFinal ");
1262 dump_cgraph (cgraph_dump_file
);
1264 #ifdef ENABLE_CHECKING
1266 /* Double check that all inline clones are gone and that all
1267 function bodies have been released from memory. */
1268 if (flag_unit_at_a_time
1269 && !dump_enabled_p (TDI_tree_all
)
1270 && !(sorrycount
|| errorcount
))
1272 struct cgraph_node
*node
;
1273 bool error_found
= false;
1275 for (node
= cgraph_nodes
; node
; node
= node
->next
)
1277 && (node
->global
.inlined_to
1278 || DECL_SAVED_TREE (node
->decl
)))
1281 dump_cgraph_node (stderr
, node
);
1284 internal_error ("nodes with no released memory found");
1289 /* Generate and emit a static constructor or destructor. WHICH must be
1290 one of 'I' or 'D'. BODY should be a STATEMENT_LIST containing
1291 GENERIC statements. */
1294 cgraph_build_static_cdtor (char which
, tree body
, int priority
)
1296 static int counter
= 0;
1298 tree decl
, name
, resdecl
;
1300 sprintf (which_buf
, "%c_%d", which
, counter
++);
1301 name
= get_file_function_name_long (which_buf
);
1303 decl
= build_decl (FUNCTION_DECL
, name
,
1304 build_function_type (void_type_node
, void_list_node
));
1305 current_function_decl
= decl
;
1307 resdecl
= build_decl (RESULT_DECL
, NULL_TREE
, void_type_node
);
1308 DECL_ARTIFICIAL (resdecl
) = 1;
1309 DECL_IGNORED_P (resdecl
) = 1;
1310 DECL_RESULT (decl
) = resdecl
;
1312 allocate_struct_function (decl
);
1314 TREE_STATIC (decl
) = 1;
1315 TREE_USED (decl
) = 1;
1316 DECL_ARTIFICIAL (decl
) = 1;
1317 DECL_IGNORED_P (decl
) = 1;
1318 DECL_NO_INSTRUMENT_FUNCTION_ENTRY_EXIT (decl
) = 1;
1319 DECL_SAVED_TREE (decl
) = body
;
1320 TREE_PUBLIC (decl
) = ! targetm
.have_ctors_dtors
;
1321 DECL_UNINLINABLE (decl
) = 1;
1323 DECL_INITIAL (decl
) = make_node (BLOCK
);
1324 TREE_USED (DECL_INITIAL (decl
)) = 1;
1326 DECL_SOURCE_LOCATION (decl
) = input_location
;
1327 cfun
->function_end_locus
= input_location
;
1332 DECL_STATIC_CONSTRUCTOR (decl
) = 1;
1335 DECL_STATIC_DESTRUCTOR (decl
) = 1;
1341 gimplify_function_tree (decl
);
1343 /* ??? We will get called LATE in the compilation process. */
1344 if (cgraph_global_info_ready
)
1346 tree_lowering_passes (decl
);
1347 tree_rest_of_compilation (decl
);
1350 cgraph_finalize_function (decl
, 0);
1352 if (targetm
.have_ctors_dtors
)
1354 void (*fn
) (rtx
, int);
1357 fn
= targetm
.asm_out
.constructor
;
1359 fn
= targetm
.asm_out
.destructor
;
1360 fn (XEXP (DECL_RTL (decl
), 0), priority
);
1367 cgraph_dump_file
= dump_begin (TDI_cgraph
, NULL
);