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_mark_local_functions (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
)
194 /* If we decided it was needed before, but at the time we didn't have
195 the body of the function available, then it's still needed. We have
196 to go back and re-check its dependencies now. */
200 /* Externally visible functions must be output. The exception is
201 COMDAT functions that must be output only when they are needed. */
202 if (TREE_PUBLIC (decl
) && !DECL_COMDAT (decl
) && !DECL_EXTERNAL (decl
))
205 /* Constructors and destructors are reachable from the runtime by
207 if (DECL_STATIC_CONSTRUCTOR (decl
) || DECL_STATIC_DESTRUCTOR (decl
))
210 /* If the user told us it is used, then it must be so. */
211 if (lookup_attribute ("used", DECL_ATTRIBUTES (decl
)))
214 /* ??? If the assembler name is set by hand, it is possible to assemble
215 the name later after finalizing the function and the fact is noticed
216 in assemble_name then. This is arguably a bug. */
217 if (DECL_ASSEMBLER_NAME_SET_P (decl
)
218 && TREE_SYMBOL_REFERENCED (DECL_ASSEMBLER_NAME (decl
)))
221 if (flag_unit_at_a_time
)
224 /* If not doing unit at a time, then we'll only defer this function
225 if its marked for inlining. Otherwise we want to emit it now. */
227 /* "extern inline" functions are never output locally. */
228 if (DECL_EXTERNAL (decl
))
230 /* Nested functions of extern inline function shall not be emit unless
231 we inlined the origin. */
232 for (origin
= decl_function_context (decl
); origin
;
233 origin
= decl_function_context (origin
))
234 if (DECL_EXTERNAL (origin
))
236 /* We want to emit COMDAT functions only when absolutely necessary. */
237 if (DECL_COMDAT (decl
))
239 if (!DECL_INLINE (decl
)
240 || (!node
->local
.disregard_inline_limits
241 /* When declared inline, defer even the uninlinable functions.
242 This allows them to be eliminated when unused. */
243 && !DECL_DECLARED_INLINE_P (decl
)
244 && (!node
->local
.inlinable
|| !cgraph_default_inline_p (node
))))
250 /* Walk the decls we marked as necessary and see if they reference new
251 variables or functions and add them into the worklists. */
253 cgraph_varpool_analyze_pending_decls (void)
255 bool changed
= false;
256 timevar_push (TV_CGRAPH
);
258 while (cgraph_varpool_first_unanalyzed_node
)
260 tree decl
= cgraph_varpool_first_unanalyzed_node
->decl
;
262 cgraph_varpool_first_unanalyzed_node
->analyzed
= true;
264 cgraph_varpool_first_unanalyzed_node
= cgraph_varpool_first_unanalyzed_node
->next_needed
;
266 if (DECL_INITIAL (decl
))
268 visited_nodes
= pointer_set_create ();
269 walk_tree (&DECL_INITIAL (decl
), record_reference
, NULL
, visited_nodes
);
270 pointer_set_destroy (visited_nodes
);
271 visited_nodes
= NULL
;
275 timevar_pop (TV_CGRAPH
);
279 /* Optimization of function bodies might've rendered some variables as
280 unnecessary so we want to avoid these from being compiled.
282 This is done by pruning the queue and keeping only the variables that
283 really appear needed (ie they are either externally visible or referenced
284 by compiled function). Re-doing the reachability analysis on variables
285 brings back the remaining variables referenced by these. */
287 cgraph_varpool_remove_unreferenced_decls (void)
289 struct cgraph_varpool_node
*next
, *node
= cgraph_varpool_nodes_queue
;
291 cgraph_varpool_reset_queue ();
293 if (errorcount
|| sorrycount
)
298 tree decl
= node
->decl
;
299 next
= node
->next_needed
;
303 && ((DECL_ASSEMBLER_NAME_SET_P (decl
)
304 && TREE_SYMBOL_REFERENCED (DECL_ASSEMBLER_NAME (decl
)))
305 || node
->force_output
306 || decide_is_variable_needed (node
, decl
)))
307 cgraph_varpool_mark_needed_node (node
);
311 cgraph_varpool_analyze_pending_decls ();
315 /* When not doing unit-at-a-time, output all functions enqueued.
316 Return true when such a functions were found. */
319 cgraph_assemble_pending_functions (void)
323 if (flag_unit_at_a_time
)
326 while (cgraph_nodes_queue
)
328 struct cgraph_node
*n
= cgraph_nodes_queue
;
330 cgraph_nodes_queue
= cgraph_nodes_queue
->next_needed
;
331 n
->next_needed
= NULL
;
332 if (!n
->global
.inlined_to
334 && !DECL_EXTERNAL (n
->decl
))
336 cgraph_expand_function (n
);
344 /* DECL has been parsed. Take it, queue it, compile it at the whim of the
345 logic in effect. If NESTED is true, then our caller cannot stand to have
346 the garbage collector run at the moment. We would need to either create
347 a new GC context, or just not compile right now. */
350 cgraph_finalize_function (tree decl
, bool nested
)
352 struct cgraph_node
*node
= cgraph_node (decl
);
354 if (node
->local
.finalized
)
356 /* As an GCC extension we allow redefinition of the function. The
357 semantics when both copies of bodies differ is not well defined.
358 We replace the old body with new body so in unit at a time mode
359 we always use new body, while in normal mode we may end up with
360 old body inlined into some functions and new body expanded and
363 ??? It may make more sense to use one body for inlining and other
364 body for expanding the function but this is difficult to do. */
366 /* If node->output is set, then this is a unit-at-a-time compilation
367 and we have already begun whole-unit analysis. This is *not*
368 testing for whether we've already emitted the function. That
369 case can be sort-of legitimately seen with real function
370 redefinition errors. I would argue that the front end should
371 never present us with such a case, but don't enforce that for now. */
372 gcc_assert (!node
->output
);
374 /* Reset our data structures so we can analyze the function again. */
375 memset (&node
->local
, 0, sizeof (node
->local
));
376 memset (&node
->global
, 0, sizeof (node
->global
));
377 memset (&node
->rtl
, 0, sizeof (node
->rtl
));
378 node
->analyzed
= false;
379 node
->local
.redefined_extern_inline
= true;
381 if (!flag_unit_at_a_time
)
383 struct cgraph_node
*n
;
385 for (n
= cgraph_nodes
; n
; n
= n
->next
)
386 if (n
->global
.inlined_to
== node
)
387 cgraph_remove_node (n
);
390 cgraph_node_remove_callees (node
);
392 /* We may need to re-queue the node for assembling in case
393 we already proceeded it and ignored as not needed. */
394 if (node
->reachable
&& !flag_unit_at_a_time
)
396 struct cgraph_node
*n
;
398 for (n
= cgraph_nodes_queue
; n
; n
= n
->next_needed
)
406 notice_global_symbol (decl
);
408 node
->local
.finalized
= true;
409 node
->lowered
= DECL_STRUCT_FUNCTION (decl
)->cfg
!= NULL
;
411 lower_nested_functions (decl
);
412 gcc_assert (!node
->nested
);
414 /* If not unit at a time, then we need to create the call graph
415 now, so that called functions can be queued and emitted now. */
416 if (!flag_unit_at_a_time
)
418 cgraph_analyze_function (node
);
419 cgraph_decide_inlining_incrementally (node
);
422 if (decide_is_function_needed (node
, decl
))
423 cgraph_mark_needed_node (node
);
425 /* If not unit at a time, go ahead and emit everything we've found
426 to be reachable at this time. */
429 if (!cgraph_assemble_pending_functions ())
433 /* If we've not yet emitted decl, tell the debug info about it. */
434 if (!TREE_ASM_WRITTEN (decl
))
435 (*debug_hooks
->deferred_inline_function
) (decl
);
437 /* Possibly warn about unused parameters. */
438 if (warn_unused_parameter
)
439 do_warn_unused_parameter (decl
);
443 cgraph_lower_function (struct cgraph_node
*node
)
447 tree_lowering_passes (node
->decl
);
448 node
->lowered
= true;
451 /* Walk tree and record all calls. Called via walk_tree. */
453 record_reference (tree
*tp
, int *walk_subtrees
, void *data
)
457 switch (TREE_CODE (t
))
460 /* ??? Really, we should mark this decl as *potentially* referenced
461 by this function and re-examine whether the decl is actually used
462 after rtl has been generated. */
463 if (TREE_STATIC (t
) || DECL_EXTERNAL (t
))
465 cgraph_varpool_mark_needed_node (cgraph_varpool_node (t
));
466 if (lang_hooks
.callgraph
.analyze_expr
)
467 return lang_hooks
.callgraph
.analyze_expr (tp
, walk_subtrees
,
474 if (flag_unit_at_a_time
)
476 /* Record dereferences to the functions. This makes the
477 functions reachable unconditionally. */
478 tree decl
= TREE_OPERAND (*tp
, 0);
479 if (TREE_CODE (decl
) == FUNCTION_DECL
)
480 cgraph_mark_needed_node (cgraph_node (decl
));
485 /* Save some cycles by not walking types and declaration as we
486 won't find anything useful there anyway. */
487 if (IS_TYPE_OR_DECL_P (*tp
))
493 if ((unsigned int) TREE_CODE (t
) >= LAST_AND_UNUSED_TREE_CODE
)
494 return lang_hooks
.callgraph
.analyze_expr (tp
, walk_subtrees
, data
);
501 /* Create cgraph edges for function calls inside BODY from NODE. */
504 cgraph_create_edges (struct cgraph_node
*node
, tree body
)
508 struct function
*this_cfun
= DECL_STRUCT_FUNCTION (body
);
509 block_stmt_iterator bsi
;
511 visited_nodes
= pointer_set_create ();
513 /* Reach the trees by walking over the CFG, and note the
514 enclosing basic-blocks in the call edges. */
515 FOR_EACH_BB_FN (bb
, this_cfun
)
516 for (bsi
= bsi_start (bb
); !bsi_end_p (bsi
); bsi_next (&bsi
))
518 tree stmt
= bsi_stmt (bsi
);
519 tree call
= get_call_expr_in (stmt
);
522 if (call
&& (decl
= get_callee_fndecl (call
)))
524 cgraph_create_edge (node
, cgraph_node (decl
), stmt
,
527 walk_tree (&TREE_OPERAND (call
, 1),
528 record_reference
, node
, visited_nodes
);
529 if (TREE_CODE (stmt
) == MODIFY_EXPR
)
530 walk_tree (&TREE_OPERAND (stmt
, 0),
531 record_reference
, node
, visited_nodes
);
534 walk_tree (bsi_stmt_ptr (bsi
), record_reference
, node
, visited_nodes
);
537 /* Walk over any private statics that may take addresses of functions. */
538 if (TREE_CODE (DECL_INITIAL (body
)) == BLOCK
)
540 for (step
= BLOCK_VARS (DECL_INITIAL (body
));
542 step
= TREE_CHAIN (step
))
543 if (DECL_INITIAL (step
))
544 walk_tree (&DECL_INITIAL (step
), record_reference
, node
, visited_nodes
);
547 /* Also look here for private statics. */
548 if (DECL_STRUCT_FUNCTION (body
))
549 for (step
= DECL_STRUCT_FUNCTION (body
)->unexpanded_var_list
;
551 step
= TREE_CHAIN (step
))
553 tree decl
= TREE_VALUE (step
);
554 if (DECL_INITIAL (decl
) && TREE_STATIC (decl
))
555 walk_tree (&DECL_INITIAL (decl
), record_reference
, node
, visited_nodes
);
558 pointer_set_destroy (visited_nodes
);
559 visited_nodes
= NULL
;
563 /* Verify cgraph nodes of given cgraph node. */
565 verify_cgraph_node (struct cgraph_node
*node
)
567 struct cgraph_edge
*e
;
568 struct cgraph_node
*main_clone
;
569 struct function
*this_cfun
= DECL_STRUCT_FUNCTION (node
->decl
);
570 basic_block this_block
;
571 block_stmt_iterator bsi
;
572 bool error_found
= false;
574 timevar_push (TV_CGRAPH_VERIFY
);
575 for (e
= node
->callees
; e
; e
= e
->next_callee
)
578 error ("Aux field set for edge %s->%s",
579 cgraph_node_name (e
->caller
), cgraph_node_name (e
->callee
));
582 for (e
= node
->callers
; e
; e
= e
->next_caller
)
584 if (!e
->inline_failed
)
586 if (node
->global
.inlined_to
587 != (e
->caller
->global
.inlined_to
588 ? e
->caller
->global
.inlined_to
: e
->caller
))
590 error ("Inlined_to pointer is wrong");
593 if (node
->callers
->next_caller
)
595 error ("Multiple inline callers");
600 if (node
->global
.inlined_to
)
602 error ("Inlined_to pointer set for noninline callers");
606 if (!node
->callers
&& node
->global
.inlined_to
)
608 error ("Inlined_to pointer is set but no predecesors found");
611 if (node
->global
.inlined_to
== node
)
613 error ("Inlined_to pointer refers to itself");
617 for (main_clone
= cgraph_node (node
->decl
); main_clone
;
618 main_clone
= main_clone
->next_clone
)
619 if (main_clone
== node
)
623 error ("Node not found in DECL_ASSEMBLER_NAME hash");
628 && DECL_SAVED_TREE (node
->decl
) && !TREE_ASM_WRITTEN (node
->decl
)
629 && (!DECL_EXTERNAL (node
->decl
) || node
->global
.inlined_to
))
633 /* The nodes we're interested in are never shared, so walk
634 the tree ignoring duplicates. */
635 visited_nodes
= pointer_set_create ();
636 /* Reach the trees by walking over the CFG, and note the
637 enclosing basic-blocks in the call edges. */
638 FOR_EACH_BB_FN (this_block
, this_cfun
)
639 for (bsi
= bsi_start (this_block
); !bsi_end_p (bsi
); bsi_next (&bsi
))
641 tree stmt
= bsi_stmt (bsi
);
642 tree call
= get_call_expr_in (stmt
);
644 if (call
&& (decl
= get_callee_fndecl (call
)))
646 struct cgraph_edge
*e
= cgraph_edge (node
, stmt
);
651 error ("Shared call_stmt:");
652 debug_generic_stmt (stmt
);
655 if (e
->callee
->decl
!= cgraph_node (decl
)->decl
)
657 error ("Edge points to wrong declaration:");
658 debug_tree (e
->callee
->decl
);
659 fprintf (stderr
," Instead of:");
666 error ("Missing callgraph edge for call stmt:");
667 debug_generic_stmt (stmt
);
672 pointer_set_destroy (visited_nodes
);
673 visited_nodes
= NULL
;
676 /* No CFG available?! */
679 for (e
= node
->callees
; e
; e
= e
->next_callee
)
683 error ("Edge %s->%s has no corresponding call_stmt",
684 cgraph_node_name (e
->caller
),
685 cgraph_node_name (e
->callee
));
686 debug_generic_stmt (e
->call_stmt
);
694 dump_cgraph_node (stderr
, node
);
695 internal_error ("verify_cgraph_node failed.");
697 timevar_pop (TV_CGRAPH_VERIFY
);
700 /* Verify whole cgraph structure. */
704 struct cgraph_node
*node
;
706 if (sorrycount
|| errorcount
)
709 for (node
= cgraph_nodes
; node
; node
= node
->next
)
710 verify_cgraph_node (node
);
714 /* Output all variables enqueued to be assembled. */
716 cgraph_varpool_assemble_pending_decls (void)
718 bool changed
= false;
720 if (errorcount
|| sorrycount
)
723 /* EH might mark decls as needed during expansion. This should be safe since
724 we don't create references to new function, but it should not be used
726 cgraph_varpool_analyze_pending_decls ();
728 while (cgraph_varpool_nodes_queue
)
730 tree decl
= cgraph_varpool_nodes_queue
->decl
;
731 struct cgraph_varpool_node
*node
= cgraph_varpool_nodes_queue
;
733 cgraph_varpool_nodes_queue
= cgraph_varpool_nodes_queue
->next_needed
;
734 if (!TREE_ASM_WRITTEN (decl
) && !node
->alias
&& !DECL_EXTERNAL (decl
))
736 assemble_variable (decl
, 0, 1, 0);
739 node
->next_needed
= NULL
;
744 /* Analyze the function scheduled to be output. */
746 cgraph_analyze_function (struct cgraph_node
*node
)
748 tree decl
= node
->decl
;
749 struct cgraph_edge
*e
;
751 current_function_decl
= decl
;
752 push_cfun (DECL_STRUCT_FUNCTION (decl
));
753 cgraph_lower_function (node
);
755 /* First kill forward declaration so reverse inlining works properly. */
756 cgraph_create_edges (node
, decl
);
758 node
->local
.inlinable
= tree_inlinable_function_p (decl
);
759 node
->local
.self_insns
= estimate_num_insns (decl
);
760 if (node
->local
.inlinable
)
761 node
->local
.disregard_inline_limits
762 = lang_hooks
.tree_inlining
.disregard_inline_limits (decl
);
763 for (e
= node
->callers
; e
; e
= e
->next_caller
)
765 if (node
->local
.redefined_extern_inline
)
766 e
->inline_failed
= N_("redefined extern inline functions are not "
767 "considered for inlining");
768 else if (!node
->local
.inlinable
)
769 e
->inline_failed
= N_("function not inlinable");
771 e
->inline_failed
= N_("function not considered for inlining");
773 if (flag_really_no_inline
&& !node
->local
.disregard_inline_limits
)
774 node
->local
.inlinable
= 0;
775 /* Inlining characteristics are maintained by the cgraph_mark_inline. */
776 node
->global
.insns
= node
->local
.self_insns
;
778 node
->analyzed
= true;
780 current_function_decl
= NULL
;
783 /* Analyze the whole compilation unit once it is parsed completely. */
786 cgraph_finalize_compilation_unit (void)
788 struct cgraph_node
*node
;
789 /* Keep track of already processed nodes when called multiple times for
790 intermodule optimization. */
791 static struct cgraph_node
*first_analyzed
;
795 if (!flag_unit_at_a_time
)
797 cgraph_assemble_pending_functions ();
803 fprintf (stderr
, "\nAnalyzing compilation unit");
807 timevar_push (TV_CGRAPH
);
808 cgraph_varpool_analyze_pending_decls ();
809 if (cgraph_dump_file
)
811 fprintf (cgraph_dump_file
, "Initial entry points:");
812 for (node
= cgraph_nodes
; node
!= first_analyzed
; node
= node
->next
)
813 if (node
->needed
&& DECL_SAVED_TREE (node
->decl
))
814 fprintf (cgraph_dump_file
, " %s", cgraph_node_name (node
));
815 fprintf (cgraph_dump_file
, "\n");
818 /* Propagate reachability flag and lower representation of all reachable
819 functions. In the future, lowering will introduce new functions and
820 new entry points on the way (by template instantiation and virtual
821 method table generation for instance). */
822 while (cgraph_nodes_queue
)
824 struct cgraph_edge
*edge
;
825 tree decl
= cgraph_nodes_queue
->decl
;
827 node
= cgraph_nodes_queue
;
828 cgraph_nodes_queue
= cgraph_nodes_queue
->next_needed
;
829 node
->next_needed
= NULL
;
831 /* ??? It is possible to create extern inline function and later using
832 weak alias attribute to kill its body. See
833 gcc.c-torture/compile/20011119-1.c */
834 if (!DECL_SAVED_TREE (decl
))
837 gcc_assert (!node
->analyzed
&& node
->reachable
);
838 gcc_assert (DECL_SAVED_TREE (decl
));
840 cgraph_analyze_function (node
);
842 for (edge
= node
->callees
; edge
; edge
= edge
->next_callee
)
843 if (!edge
->callee
->reachable
)
844 cgraph_mark_reachable_node (edge
->callee
);
846 cgraph_varpool_analyze_pending_decls ();
849 /* Collect entry points to the unit. */
851 if (cgraph_dump_file
)
853 fprintf (cgraph_dump_file
, "Unit entry points:");
854 for (node
= cgraph_nodes
; node
!= first_analyzed
; node
= node
->next
)
855 if (node
->needed
&& DECL_SAVED_TREE (node
->decl
))
856 fprintf (cgraph_dump_file
, " %s", cgraph_node_name (node
));
857 fprintf (cgraph_dump_file
, "\n\nInitial ");
858 dump_cgraph (cgraph_dump_file
);
861 if (cgraph_dump_file
)
862 fprintf (cgraph_dump_file
, "\nReclaiming functions:");
864 for (node
= cgraph_nodes
; node
!= first_analyzed
; node
= node
->next
)
866 tree decl
= node
->decl
;
868 if (!node
->reachable
&& DECL_SAVED_TREE (decl
))
870 if (cgraph_dump_file
)
871 fprintf (cgraph_dump_file
, " %s", cgraph_node_name (node
));
872 cgraph_remove_node (node
);
875 node
->next_needed
= NULL
;
877 if (cgraph_dump_file
)
879 fprintf (cgraph_dump_file
, "\n\nReclaimed ");
880 dump_cgraph (cgraph_dump_file
);
882 first_analyzed
= cgraph_nodes
;
884 timevar_pop (TV_CGRAPH
);
886 /* Figure out what functions we want to assemble. */
889 cgraph_mark_functions_to_output (void)
891 struct cgraph_node
*node
;
893 for (node
= cgraph_nodes
; node
; node
= node
->next
)
895 tree decl
= node
->decl
;
896 struct cgraph_edge
*e
;
898 gcc_assert (!node
->output
);
900 for (e
= node
->callers
; e
; e
= e
->next_caller
)
901 if (e
->inline_failed
)
904 /* We need to output all local functions that are used and not
905 always inlined, as well as those that are reachable from
906 outside the current compilation unit. */
907 if (DECL_SAVED_TREE (decl
)
908 && !node
->global
.inlined_to
910 || (e
&& node
->reachable
))
911 && !TREE_ASM_WRITTEN (decl
)
912 && !DECL_EXTERNAL (decl
))
916 /* We should've reclaimed all functions that are not needed. */
917 #ifdef ENABLE_CHECKING
918 if (!node
->global
.inlined_to
&& DECL_SAVED_TREE (decl
)
919 && !DECL_EXTERNAL (decl
))
921 dump_cgraph_node (stderr
, node
);
922 internal_error ("failed to reclaim unneeded function");
925 gcc_assert (node
->global
.inlined_to
|| !DECL_SAVED_TREE (decl
)
926 || DECL_EXTERNAL (decl
));
933 /* Expand function specified by NODE. */
936 cgraph_expand_function (struct cgraph_node
*node
)
938 tree decl
= node
->decl
;
940 /* We ought to not compile any inline clones. */
941 gcc_assert (!node
->global
.inlined_to
);
943 if (flag_unit_at_a_time
)
944 announce_function (decl
);
946 cgraph_lower_function (node
);
948 /* Generate RTL for the body of DECL. */
949 lang_hooks
.callgraph
.expand_function (decl
);
951 /* Make sure that BE didn't give up on compiling. */
952 /* ??? Can happen with nested function of extern inline. */
953 gcc_assert (TREE_ASM_WRITTEN (node
->decl
));
955 current_function_decl
= NULL
;
956 if (!cgraph_preserve_function_body_p (node
->decl
))
958 DECL_SAVED_TREE (node
->decl
) = NULL
;
959 DECL_STRUCT_FUNCTION (node
->decl
) = NULL
;
960 DECL_INITIAL (node
->decl
) = error_mark_node
;
961 /* Eliminate all call edges. This is important so the call_expr no longer
962 points to the dead function body. */
963 cgraph_node_remove_callees (node
);
967 /* Return true when CALLER_DECL should be inlined into CALLEE_DECL. */
970 cgraph_inline_p (struct cgraph_edge
*e
, const char **reason
)
972 *reason
= e
->inline_failed
;
973 return !e
->inline_failed
;
978 /* Expand all functions that must be output.
980 Attempt to topologically sort the nodes so function is output when
981 all called functions are already assembled to allow data to be
982 propagated across the callgraph. Use a stack to get smaller distance
983 between a function and its callees (later we may choose to use a more
984 sophisticated algorithm for function reordering; we will likely want
985 to use subsections to make the output functions appear in top-down
989 cgraph_expand_all_functions (void)
991 struct cgraph_node
*node
;
992 struct cgraph_node
**order
=
993 xcalloc (cgraph_n_nodes
, sizeof (struct cgraph_node
*));
994 int order_pos
= 0, new_order_pos
= 0;
997 order_pos
= cgraph_postorder (order
);
998 gcc_assert (order_pos
== cgraph_n_nodes
);
1000 /* Garbage collector may remove inline clones we eliminate during
1001 optimization. So we must be sure to not reference them. */
1002 for (i
= 0; i
< order_pos
; i
++)
1003 if (order
[i
]->output
)
1004 order
[new_order_pos
++] = order
[i
];
1006 for (i
= new_order_pos
- 1; i
>= 0; i
--)
1011 gcc_assert (node
->reachable
);
1013 cgraph_expand_function (node
);
1019 /* Mark all local functions.
1021 A local function is one whose calls can occur only in the current
1022 compilation unit and all its calls are explicit, so we can change
1023 its calling convention. We simply mark all static functions whose
1024 address is not taken as local. */
1027 cgraph_mark_local_functions (void)
1029 struct cgraph_node
*node
;
1031 /* Figure out functions we want to assemble. */
1032 for (node
= cgraph_nodes
; node
; node
= node
->next
)
1034 node
->local
.local
= (!node
->needed
1035 && DECL_SAVED_TREE (node
->decl
)
1036 && !TREE_PUBLIC (node
->decl
));
1039 if (cgraph_dump_file
)
1041 fprintf (cgraph_dump_file
, "\nMarking local functions:");
1042 for (node
= cgraph_nodes
; node
; node
= node
->next
)
1043 if (node
->local
.local
)
1044 fprintf (cgraph_dump_file
, " %s", cgraph_node_name (node
));
1045 fprintf (cgraph_dump_file
, "\n\n");
1049 /* Return true when function body of DECL still needs to be kept around
1050 for later re-use. */
1052 cgraph_preserve_function_body_p (tree decl
)
1054 struct cgraph_node
*node
;
1055 /* Keep the body; we're going to dump it. */
1056 if (dump_enabled_p (TDI_tree_all
))
1058 if (!cgraph_global_info_ready
)
1059 return (DECL_INLINE (decl
) && !flag_really_no_inline
);
1060 /* Look if there is any clone around. */
1061 for (node
= cgraph_node (decl
); node
; node
= node
->next_clone
)
1062 if (node
->global
.inlined_to
)
1067 /* Perform simple optimizations based on callgraph. */
1070 cgraph_optimize (void)
1072 #ifdef ENABLE_CHECKING
1075 if (!flag_unit_at_a_time
)
1077 cgraph_varpool_assemble_pending_decls ();
1081 process_pending_assemble_externals ();
1083 /* Frontend may output common variables after the unit has been finalized.
1084 It is safe to deal with them here as they are always zero initialized. */
1085 cgraph_varpool_analyze_pending_decls ();
1087 timevar_push (TV_CGRAPHOPT
);
1089 fprintf (stderr
, "Performing intraprocedural optimizations\n");
1091 cgraph_mark_local_functions ();
1092 if (cgraph_dump_file
)
1094 fprintf (cgraph_dump_file
, "Marked ");
1095 dump_cgraph (cgraph_dump_file
);
1098 cgraph_global_info_ready
= true;
1099 if (cgraph_dump_file
)
1101 fprintf (cgraph_dump_file
, "Optimized ");
1102 dump_cgraph (cgraph_dump_file
);
1103 dump_varpool (cgraph_dump_file
);
1105 timevar_pop (TV_CGRAPHOPT
);
1107 /* Output everything. */
1109 fprintf (stderr
, "Assembling functions:\n");
1110 #ifdef ENABLE_CHECKING
1114 cgraph_mark_functions_to_output ();
1115 cgraph_expand_all_functions ();
1116 cgraph_varpool_remove_unreferenced_decls ();
1118 cgraph_varpool_assemble_pending_decls ();
1120 if (cgraph_dump_file
)
1122 fprintf (cgraph_dump_file
, "\nFinal ");
1123 dump_cgraph (cgraph_dump_file
);
1125 #ifdef ENABLE_CHECKING
1127 /* Double check that all inline clones are gone and that all
1128 function bodies have been released from memory. */
1129 if (flag_unit_at_a_time
1130 && !dump_enabled_p (TDI_tree_all
)
1131 && !(sorrycount
|| errorcount
))
1133 struct cgraph_node
*node
;
1134 bool error_found
= false;
1136 for (node
= cgraph_nodes
; node
; node
= node
->next
)
1138 && (node
->global
.inlined_to
1139 || DECL_SAVED_TREE (node
->decl
)))
1142 dump_cgraph_node (stderr
, node
);
1145 internal_error ("Nodes with no released memory found.");
1150 /* Generate and emit a static constructor or destructor. WHICH must be
1151 one of 'I' or 'D'. BODY should be a STATEMENT_LIST containing
1152 GENERIC statements. */
1155 cgraph_build_static_cdtor (char which
, tree body
, int priority
)
1157 static int counter
= 0;
1159 tree decl
, name
, resdecl
;
1161 sprintf (which_buf
, "%c_%d", which
, counter
++);
1162 name
= get_file_function_name_long (which_buf
);
1164 decl
= build_decl (FUNCTION_DECL
, name
,
1165 build_function_type (void_type_node
, void_list_node
));
1166 current_function_decl
= decl
;
1168 resdecl
= build_decl (RESULT_DECL
, NULL_TREE
, void_type_node
);
1169 DECL_ARTIFICIAL (resdecl
) = 1;
1170 DECL_IGNORED_P (resdecl
) = 1;
1171 DECL_RESULT (decl
) = resdecl
;
1173 allocate_struct_function (decl
);
1175 TREE_STATIC (decl
) = 1;
1176 TREE_USED (decl
) = 1;
1177 DECL_ARTIFICIAL (decl
) = 1;
1178 DECL_IGNORED_P (decl
) = 1;
1179 DECL_NO_INSTRUMENT_FUNCTION_ENTRY_EXIT (decl
) = 1;
1180 DECL_SAVED_TREE (decl
) = body
;
1181 TREE_PUBLIC (decl
) = ! targetm
.have_ctors_dtors
;
1182 DECL_UNINLINABLE (decl
) = 1;
1184 DECL_INITIAL (decl
) = make_node (BLOCK
);
1185 TREE_USED (DECL_INITIAL (decl
)) = 1;
1187 DECL_SOURCE_LOCATION (decl
) = input_location
;
1188 cfun
->function_end_locus
= input_location
;
1193 DECL_STATIC_CONSTRUCTOR (decl
) = 1;
1196 DECL_STATIC_DESTRUCTOR (decl
) = 1;
1202 gimplify_function_tree (decl
);
1204 /* ??? We will get called LATE in the compilation process. */
1205 if (cgraph_global_info_ready
)
1207 tree_lowering_passes (decl
);
1208 tree_rest_of_compilation (decl
);
1211 cgraph_finalize_function (decl
, 0);
1213 if (targetm
.have_ctors_dtors
)
1215 void (*fn
) (rtx
, int);
1218 fn
= targetm
.asm_out
.constructor
;
1220 fn
= targetm
.asm_out
.destructor
;
1221 fn (XEXP (DECL_RTL (decl
), 0), priority
);
1228 cgraph_dump_file
= dump_begin (TDI_cgraph
, NULL
);