1 /* Callgraph based interprocedural optimizations.
2 Copyright (C) 2003, 2004, 2005, 2006, 2007, 2008, 2009, 2010
3 Free Software Foundation, Inc.
4 Contributed by Jan Hubicka
6 This file is part of GCC.
8 GCC is free software; you can redistribute it and/or modify it under
9 the terms of the GNU General Public License as published by the Free
10 Software Foundation; either version 3, or (at your option) any later
13 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
14 WARRANTY; without even the implied warranty of MERCHANTABILITY or
15 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
18 You should have received a copy of the GNU General Public License
19 along with GCC; see the file COPYING3. If not see
20 <http://www.gnu.org/licenses/>. */
22 /* This module implements main driver of compilation process as well as
23 few basic interprocedural 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
38 - varpool_finalize_variable
40 This function has same behavior as the above but is used for static
43 - cgraph_finalize_compilation_unit
45 This function is called once (source level) compilation unit is finalized
46 and it will no longer change.
48 In the the call-graph construction and local function
49 analysis takes place here. Bodies of unreachable functions are released
50 to conserve memory usage.
52 The function can be called multiple times when multiple source level
53 compilation units are combined (such as in C frontend)
57 In this unit-at-a-time compilation the intra procedural analysis takes
58 place here. In particular the static functions whose address is never
59 taken are marked as local. Backend can then use this information to
60 modify calling conventions, do better inlining or similar optimizations.
62 - cgraph_mark_needed_node
63 - varpool_mark_needed_node
65 When function or variable is referenced by some hidden way the call-graph
66 data structure must be updated accordingly by this function.
67 There should be little need to call this function and all the references
68 should be made explicit to cgraph code. At present these functions are
69 used by C++ frontend to explicitly mark the keyed methods.
71 - analyze_expr callback
73 This function is responsible for lowering tree nodes not understood by
74 generic code into understandable ones or alternatively marking
75 callgraph and varpool nodes referenced by the as needed.
77 ??? On the tree-ssa genericizing should take place here and we will avoid
78 need for these hooks (replacing them by genericizing hook)
80 Analyzing of all functions is deferred
81 to cgraph_finalize_compilation_unit and expansion into cgraph_optimize.
83 In cgraph_finalize_compilation_unit the reachable functions are
84 analyzed. During analysis the call-graph edges from reachable
85 functions are constructed and their destinations are marked as
86 reachable. References to functions and variables are discovered too
87 and variables found to be needed output to the assembly file. Via
88 mark_referenced call in assemble_variable functions referenced by
89 static variables are noticed too.
91 The intra-procedural information is produced and its existence
92 indicated by global_info_ready. Once this flag is set it is impossible
93 to change function from !reachable to reachable and thus
94 assemble_variable no longer call mark_referenced.
96 Finally the call-graph is topologically sorted and all reachable functions
97 that has not been completely inlined or are not external are output.
99 ??? It is possible that reference to function or variable is optimized
100 out. We can not deal with this nicely because topological order is not
101 suitable for it. For tree-ssa we may consider another pass doing
102 optimization and re-discovering reachable functions.
104 ??? Reorganize code so variables are output very last and only if they
105 really has been referenced by produced code, so we catch more cases
106 where reference has been optimized out. */
111 #include "coretypes.h"
115 #include "tree-flow.h"
116 #include "tree-inline.h"
117 #include "langhooks.h"
118 #include "pointer-set.h"
125 #include "diagnostic.h"
126 #include "tree-pretty-print.h"
127 #include "gimple-pretty-print.h"
132 #include "function.h"
133 #include "ipa-prop.h"
135 #include "tree-iterator.h"
136 #include "tree-pass.h"
137 #include "tree-dump.h"
139 #include "coverage.h"
142 static void cgraph_expand_all_functions (void);
143 static void cgraph_mark_functions_to_output (void);
144 static void cgraph_expand_function (struct cgraph_node
*);
145 static void cgraph_output_pending_asms (void);
146 static void cgraph_analyze_function (struct cgraph_node
*);
148 FILE *cgraph_dump_file
;
150 /* Used for vtable lookup in thunk adjusting. */
151 static GTY (()) tree vtable_entry_type
;
153 /* Determine if function DECL is needed. That is, visible to something
154 either outside this translation unit, something magic in the system
158 cgraph_decide_is_function_needed (struct cgraph_node
*node
, tree decl
)
160 /* If the user told us it is used, then it must be so. */
161 if (node
->local
.externally_visible
)
164 /* ??? If the assembler name is set by hand, it is possible to assemble
165 the name later after finalizing the function and the fact is noticed
166 in assemble_name then. This is arguably a bug. */
167 if (DECL_ASSEMBLER_NAME_SET_P (decl
)
168 && TREE_SYMBOL_REFERENCED (DECL_ASSEMBLER_NAME (decl
)))
171 /* With -fkeep-inline-functions we are keeping all inline functions except
172 for extern inline ones. */
173 if (flag_keep_inline_functions
174 && DECL_DECLARED_INLINE_P (decl
)
175 && !DECL_EXTERNAL (decl
)
176 && !lookup_attribute ("always_inline", DECL_ATTRIBUTES (decl
)))
179 /* If we decided it was needed before, but at the time we didn't have
180 the body of the function available, then it's still needed. We have
181 to go back and re-check its dependencies now. */
185 /* Externally visible functions must be output. The exception is
186 COMDAT functions that must be output only when they are needed.
188 When not optimizing, also output the static functions. (see
189 PR24561), but don't do so for always_inline functions, functions
190 declared inline and nested functions. These were optimized out
191 in the original implementation and it is unclear whether we want
192 to change the behavior here. */
193 if (((TREE_PUBLIC (decl
)
195 && !node
->local
.disregard_inline_limits
196 && !DECL_DECLARED_INLINE_P (decl
)
197 && !(DECL_CONTEXT (decl
)
198 && TREE_CODE (DECL_CONTEXT (decl
)) == FUNCTION_DECL
)))
199 && !flag_whole_program
202 && !DECL_COMDAT (decl
) && !DECL_EXTERNAL (decl
))
208 /* Process CGRAPH_NEW_FUNCTIONS and perform actions necessary to add these
209 functions into callgraph in a way so they look like ordinary reachable
210 functions inserted into callgraph already at construction time. */
213 cgraph_process_new_functions (void)
217 struct cgraph_node
*node
;
219 varpool_analyze_pending_decls ();
220 /* Note that this queue may grow as its being processed, as the new
221 functions may generate new ones. */
222 while (cgraph_new_nodes
)
224 node
= cgraph_new_nodes
;
226 cgraph_new_nodes
= cgraph_new_nodes
->next_needed
;
227 switch (cgraph_state
)
229 case CGRAPH_STATE_CONSTRUCTION
:
230 /* At construction time we just need to finalize function and move
231 it into reachable functions list. */
233 node
->next_needed
= NULL
;
234 cgraph_finalize_function (fndecl
, false);
235 cgraph_mark_reachable_node (node
);
239 case CGRAPH_STATE_IPA
:
240 case CGRAPH_STATE_IPA_SSA
:
241 /* When IPA optimization already started, do all essential
242 transformations that has been already performed on the whole
243 cgraph but not on this function. */
245 gimple_register_cfg_hooks ();
247 cgraph_analyze_function (node
);
248 push_cfun (DECL_STRUCT_FUNCTION (fndecl
));
249 current_function_decl
= fndecl
;
250 compute_inline_parameters (node
);
251 if ((cgraph_state
== CGRAPH_STATE_IPA_SSA
252 && !gimple_in_ssa_p (DECL_STRUCT_FUNCTION (fndecl
)))
253 /* When not optimizing, be sure we run early local passes anyway
256 execute_pass_list (pass_early_local_passes
.pass
.sub
);
257 free_dominance_info (CDI_POST_DOMINATORS
);
258 free_dominance_info (CDI_DOMINATORS
);
260 current_function_decl
= NULL
;
263 case CGRAPH_STATE_EXPANSION
:
264 /* Functions created during expansion shall be compiled
267 cgraph_expand_function (node
);
274 cgraph_call_function_insertion_hooks (node
);
275 varpool_analyze_pending_decls ();
280 /* As an GCC extension we allow redefinition of the function. The
281 semantics when both copies of bodies differ is not well defined.
282 We replace the old body with new body so in unit at a time mode
283 we always use new body, while in normal mode we may end up with
284 old body inlined into some functions and new body expanded and
287 ??? It may make more sense to use one body for inlining and other
288 body for expanding the function but this is difficult to do. */
291 cgraph_reset_node (struct cgraph_node
*node
)
293 /* If node->process is set, then we have already begun whole-unit analysis.
294 This is *not* testing for whether we've already emitted the function.
295 That case can be sort-of legitimately seen with real function redefinition
296 errors. I would argue that the front end should never present us with
297 such a case, but don't enforce that for now. */
298 gcc_assert (!node
->process
);
300 /* Reset our data structures so we can analyze the function again. */
301 memset (&node
->local
, 0, sizeof (node
->local
));
302 memset (&node
->global
, 0, sizeof (node
->global
));
303 memset (&node
->rtl
, 0, sizeof (node
->rtl
));
304 node
->analyzed
= false;
305 node
->local
.redefined_extern_inline
= true;
306 node
->local
.finalized
= false;
308 cgraph_node_remove_callees (node
);
310 /* We may need to re-queue the node for assembling in case
311 we already proceeded it and ignored as not needed or got
312 a re-declaration in IMA mode. */
315 struct cgraph_node
*n
;
317 for (n
= cgraph_nodes_queue
; n
; n
= n
->next_needed
)
326 cgraph_lower_function (struct cgraph_node
*node
)
332 lower_nested_functions (node
->decl
);
333 gcc_assert (!node
->nested
);
335 tree_lowering_passes (node
->decl
);
336 node
->lowered
= true;
339 /* DECL has been parsed. Take it, queue it, compile it at the whim of the
340 logic in effect. If NESTED is true, then our caller cannot stand to have
341 the garbage collector run at the moment. We would need to either create
342 a new GC context, or just not compile right now. */
345 cgraph_finalize_function (tree decl
, bool nested
)
347 struct cgraph_node
*node
= cgraph_node (decl
);
349 if (node
->local
.finalized
)
350 cgraph_reset_node (node
);
352 node
->pid
= cgraph_max_pid
++;
353 notice_global_symbol (decl
);
354 node
->local
.finalized
= true;
355 node
->lowered
= DECL_STRUCT_FUNCTION (decl
)->cfg
!= NULL
;
356 node
->finalized_by_frontend
= true;
358 if (cgraph_decide_is_function_needed (node
, decl
))
359 cgraph_mark_needed_node (node
);
361 /* Since we reclaim unreachable nodes at the end of every language
362 level unit, we need to be conservative about possible entry points
364 if ((TREE_PUBLIC (decl
) && !DECL_COMDAT (decl
) && !DECL_EXTERNAL (decl
))
365 || DECL_STATIC_CONSTRUCTOR (decl
)
366 || DECL_STATIC_DESTRUCTOR (decl
)
367 /* COMDAT virtual functions may be referenced by vtable from
368 other compilatoin unit. Still we want to devirtualize calls
369 to those so we need to analyze them.
370 FIXME: We should introduce may edges for this purpose and update
371 their handling in unreachable function removal and inliner too. */
372 || (DECL_VIRTUAL_P (decl
) && (DECL_COMDAT (decl
) || DECL_EXTERNAL (decl
))))
373 cgraph_mark_reachable_node (node
);
375 /* If we've not yet emitted decl, tell the debug info about it. */
376 if (!TREE_ASM_WRITTEN (decl
))
377 (*debug_hooks
->deferred_inline_function
) (decl
);
379 /* Possibly warn about unused parameters. */
380 if (warn_unused_parameter
)
381 do_warn_unused_parameter (decl
);
387 /* C99 extern inline keywords allow changing of declaration after function
388 has been finalized. We need to re-decide if we want to mark the function as
392 cgraph_mark_if_needed (tree decl
)
394 struct cgraph_node
*node
= cgraph_node (decl
);
395 if (node
->local
.finalized
&& cgraph_decide_is_function_needed (node
, decl
))
396 cgraph_mark_needed_node (node
);
399 #ifdef ENABLE_CHECKING
400 /* Return TRUE if NODE2 is equivalent to NODE or its clone. */
402 clone_of_p (struct cgraph_node
*node
, struct cgraph_node
*node2
)
404 while (node
!= node2
&& node2
)
405 node2
= node2
->clone_of
;
406 return node2
!= NULL
;
410 /* Verify edge E count and frequency. */
413 verify_edge_count_and_frequency (struct cgraph_edge
*e
)
415 bool error_found
= false;
418 error ("caller edge count is negative");
421 if (e
->frequency
< 0)
423 error ("caller edge frequency is negative");
426 if (e
->frequency
> CGRAPH_FREQ_MAX
)
428 error ("caller edge frequency is too large");
431 if (gimple_has_body_p (e
->caller
->decl
)
432 && !e
->caller
->global
.inlined_to
434 != compute_call_stmt_bb_frequency (e
->caller
->decl
,
435 gimple_bb (e
->call_stmt
))))
437 error ("caller edge frequency %i does not match BB freqency %i",
439 compute_call_stmt_bb_frequency (e
->caller
->decl
,
440 gimple_bb (e
->call_stmt
)));
446 /* Verify cgraph nodes of given cgraph node. */
448 verify_cgraph_node (struct cgraph_node
*node
)
450 struct cgraph_edge
*e
;
451 struct function
*this_cfun
= DECL_STRUCT_FUNCTION (node
->decl
);
452 struct function
*saved_cfun
= cfun
;
453 basic_block this_block
;
454 gimple_stmt_iterator gsi
;
455 bool error_found
= false;
460 timevar_push (TV_CGRAPH_VERIFY
);
461 /* debug_generic_stmt needs correct cfun */
462 set_cfun (this_cfun
);
463 for (e
= node
->callees
; e
; e
= e
->next_callee
)
466 error ("aux field set for edge %s->%s",
467 identifier_to_locale (cgraph_node_name (e
->caller
)),
468 identifier_to_locale (cgraph_node_name (e
->callee
)));
473 error ("Execution count is negative");
476 if (node
->global
.inlined_to
&& node
->local
.externally_visible
)
478 error ("Externally visible inline clone");
481 if (node
->global
.inlined_to
&& node
->address_taken
)
483 error ("Inline clone with address taken");
486 if (node
->global
.inlined_to
&& node
->needed
)
488 error ("Inline clone is needed");
491 for (e
= node
->indirect_calls
; e
; e
= e
->next_callee
)
495 error ("aux field set for indirect edge from %s",
496 identifier_to_locale (cgraph_node_name (e
->caller
)));
499 if (!e
->indirect_unknown_callee
500 || !e
->indirect_info
)
502 error ("An indirect edge from %s is not marked as indirect or has "
503 "associated indirect_info, the corresponding statement is: ",
504 identifier_to_locale (cgraph_node_name (e
->caller
)));
505 debug_gimple_stmt (e
->call_stmt
);
509 for (e
= node
->callers
; e
; e
= e
->next_caller
)
511 if (verify_edge_count_and_frequency (e
))
513 if (!e
->inline_failed
)
515 if (node
->global
.inlined_to
516 != (e
->caller
->global
.inlined_to
517 ? e
->caller
->global
.inlined_to
: e
->caller
))
519 error ("inlined_to pointer is wrong");
522 if (node
->callers
->next_caller
)
524 error ("multiple inline callers");
529 if (node
->global
.inlined_to
)
531 error ("inlined_to pointer set for noninline callers");
535 for (e
= node
->indirect_calls
; e
; e
= e
->next_callee
)
536 if (verify_edge_count_and_frequency (e
))
538 if (!node
->callers
&& node
->global
.inlined_to
)
540 error ("inlined_to pointer is set but no predecessors found");
543 if (node
->global
.inlined_to
== node
)
545 error ("inlined_to pointer refers to itself");
549 if (!cgraph_node (node
->decl
))
551 error ("node not found in cgraph_hash");
557 struct cgraph_node
*n
;
558 for (n
= node
->clone_of
->clones
; n
; n
= n
->next_sibling_clone
)
563 error ("node has wrong clone_of");
569 struct cgraph_node
*n
;
570 for (n
= node
->clones
; n
; n
= n
->next_sibling_clone
)
571 if (n
->clone_of
!= node
)
575 error ("node has wrong clone list");
579 if ((node
->prev_sibling_clone
|| node
->next_sibling_clone
) && !node
->clone_of
)
581 error ("node is in clone list but it is not clone");
584 if (!node
->prev_sibling_clone
&& node
->clone_of
&& node
->clone_of
->clones
!= node
)
586 error ("node has wrong prev_clone pointer");
589 if (node
->prev_sibling_clone
&& node
->prev_sibling_clone
->next_sibling_clone
!= node
)
591 error ("double linked list of clones corrupted");
594 if (node
->same_comdat_group
)
596 struct cgraph_node
*n
= node
->same_comdat_group
;
598 if (!DECL_ONE_ONLY (node
->decl
))
600 error ("non-DECL_ONE_ONLY node in a same_comdat_group list");
605 error ("node is alone in a comdat group");
610 if (!n
->same_comdat_group
)
612 error ("same_comdat_group is not a circular list");
616 n
= n
->same_comdat_group
;
621 if (node
->analyzed
&& gimple_has_body_p (node
->decl
)
622 && !TREE_ASM_WRITTEN (node
->decl
)
623 && (!DECL_EXTERNAL (node
->decl
) || node
->global
.inlined_to
)
628 /* The nodes we're interested in are never shared, so walk
629 the tree ignoring duplicates. */
630 struct pointer_set_t
*visited_nodes
= pointer_set_create ();
631 /* Reach the trees by walking over the CFG, and note the
632 enclosing basic-blocks in the call edges. */
633 FOR_EACH_BB_FN (this_block
, this_cfun
)
634 for (gsi
= gsi_start_bb (this_block
);
638 gimple stmt
= gsi_stmt (gsi
);
639 if (is_gimple_call (stmt
))
641 struct cgraph_edge
*e
= cgraph_edge (node
, stmt
);
642 tree decl
= gimple_call_fndecl (stmt
);
647 error ("shared call_stmt:");
648 debug_gimple_stmt (stmt
);
651 if (!e
->indirect_unknown_callee
)
653 if (e
->callee
->same_body_alias
)
655 error ("edge points to same body alias:");
656 debug_tree (e
->callee
->decl
);
659 else if (!e
->callee
->global
.inlined_to
661 && cgraph_get_node (decl
)
662 && (e
->callee
->former_clone_of
663 != cgraph_get_node (decl
)->decl
)
664 && !clone_of_p (cgraph_node (decl
),
667 error ("edge points to wrong declaration:");
668 debug_tree (e
->callee
->decl
);
669 fprintf (stderr
," Instead of:");
676 error ("an indirect edge with unknown callee "
677 "corresponding to a call_stmt with "
678 "a known declaration:");
680 debug_gimple_stmt (e
->call_stmt
);
686 error ("missing callgraph edge for call stmt:");
687 debug_gimple_stmt (stmt
);
692 pointer_set_destroy (visited_nodes
);
695 /* No CFG available?! */
698 for (e
= node
->callees
; e
; e
= e
->next_callee
)
702 error ("edge %s->%s has no corresponding call_stmt",
703 identifier_to_locale (cgraph_node_name (e
->caller
)),
704 identifier_to_locale (cgraph_node_name (e
->callee
)));
705 debug_gimple_stmt (e
->call_stmt
);
710 for (e
= node
->indirect_calls
; e
; e
= e
->next_callee
)
714 error ("an indirect edge from %s has no corresponding call_stmt",
715 identifier_to_locale (cgraph_node_name (e
->caller
)));
716 debug_gimple_stmt (e
->call_stmt
);
724 dump_cgraph_node (stderr
, node
);
725 internal_error ("verify_cgraph_node failed");
727 set_cfun (saved_cfun
);
728 timevar_pop (TV_CGRAPH_VERIFY
);
731 /* Verify whole cgraph structure. */
735 struct cgraph_node
*node
;
740 for (node
= cgraph_nodes
; node
; node
= node
->next
)
741 verify_cgraph_node (node
);
744 /* Output all asm statements we have stored up to be output. */
747 cgraph_output_pending_asms (void)
749 struct cgraph_asm_node
*can
;
754 for (can
= cgraph_asm_nodes
; can
; can
= can
->next
)
755 assemble_asm (can
->asm_str
);
756 cgraph_asm_nodes
= NULL
;
759 /* Analyze the function scheduled to be output. */
761 cgraph_analyze_function (struct cgraph_node
*node
)
763 tree save
= current_function_decl
;
764 tree decl
= node
->decl
;
766 current_function_decl
= decl
;
767 push_cfun (DECL_STRUCT_FUNCTION (decl
));
769 assign_assembler_name_if_neeeded (node
->decl
);
771 /* Make sure to gimplify bodies only once. During analyzing a
772 function we lower it, which will require gimplified nested
773 functions, so we can end up here with an already gimplified
775 if (!gimple_body (decl
))
776 gimplify_function_tree (decl
);
777 dump_function (TDI_generic
, decl
);
779 cgraph_lower_function (node
);
780 node
->analyzed
= true;
783 current_function_decl
= save
;
786 /* Look for externally_visible and used attributes and mark cgraph nodes
789 We cannot mark the nodes at the point the attributes are processed (in
790 handle_*_attribute) because the copy of the declarations available at that
791 point may not be canonical. For example, in:
794 void f() __attribute__((used));
796 the declaration we see in handle_used_attribute will be the second
797 declaration -- but the front end will subsequently merge that declaration
798 with the original declaration and discard the second declaration.
800 Furthermore, we can't mark these nodes in cgraph_finalize_function because:
803 void f() __attribute__((externally_visible));
807 So, we walk the nodes at the end of the translation unit, applying the
808 attributes at that point. */
811 process_function_and_variable_attributes (struct cgraph_node
*first
,
812 struct varpool_node
*first_var
)
814 struct cgraph_node
*node
;
815 struct varpool_node
*vnode
;
817 for (node
= cgraph_nodes
; node
!= first
; node
= node
->next
)
819 tree decl
= node
->decl
;
820 if (DECL_PRESERVE_P (decl
))
821 cgraph_mark_needed_node (node
);
822 if (lookup_attribute ("externally_visible", DECL_ATTRIBUTES (decl
)))
824 if (! TREE_PUBLIC (node
->decl
))
825 warning_at (DECL_SOURCE_LOCATION (node
->decl
), OPT_Wattributes
,
826 "%<externally_visible%>"
827 " attribute have effect only on public objects");
828 else if (node
->local
.finalized
)
829 cgraph_mark_needed_node (node
);
832 for (vnode
= varpool_nodes
; vnode
!= first_var
; vnode
= vnode
->next
)
834 tree decl
= vnode
->decl
;
835 if (DECL_PRESERVE_P (decl
))
837 vnode
->force_output
= true;
838 if (vnode
->finalized
)
839 varpool_mark_needed_node (vnode
);
841 if (lookup_attribute ("externally_visible", DECL_ATTRIBUTES (decl
)))
843 if (! TREE_PUBLIC (vnode
->decl
))
844 warning_at (DECL_SOURCE_LOCATION (vnode
->decl
), OPT_Wattributes
,
845 "%<externally_visible%>"
846 " attribute have effect only on public objects");
847 else if (vnode
->finalized
)
848 varpool_mark_needed_node (vnode
);
853 /* Process CGRAPH_NODES_NEEDED queue, analyze each function (and transitively
854 each reachable functions) and build cgraph.
855 The function can be called multiple times after inserting new nodes
856 into beginning of queue. Just the new part of queue is re-scanned then. */
859 cgraph_analyze_functions (void)
861 /* Keep track of already processed nodes when called multiple times for
862 intermodule optimization. */
863 static struct cgraph_node
*first_analyzed
;
864 struct cgraph_node
*first_processed
= first_analyzed
;
865 static struct varpool_node
*first_analyzed_var
;
866 struct cgraph_node
*node
, *next
;
868 bitmap_obstack_initialize (NULL
);
869 process_function_and_variable_attributes (first_processed
,
871 first_processed
= cgraph_nodes
;
872 first_analyzed_var
= varpool_nodes
;
873 varpool_analyze_pending_decls ();
874 if (cgraph_dump_file
)
876 fprintf (cgraph_dump_file
, "Initial entry points:");
877 for (node
= cgraph_nodes
; node
!= first_analyzed
; node
= node
->next
)
879 fprintf (cgraph_dump_file
, " %s", cgraph_node_name (node
));
880 fprintf (cgraph_dump_file
, "\n");
882 cgraph_process_new_functions ();
884 /* Propagate reachability flag and lower representation of all reachable
885 functions. In the future, lowering will introduce new functions and
886 new entry points on the way (by template instantiation and virtual
887 method table generation for instance). */
888 while (cgraph_nodes_queue
)
890 struct cgraph_edge
*edge
;
891 tree decl
= cgraph_nodes_queue
->decl
;
893 node
= cgraph_nodes_queue
;
894 cgraph_nodes_queue
= cgraph_nodes_queue
->next_needed
;
895 node
->next_needed
= NULL
;
897 /* ??? It is possible to create extern inline function and later using
898 weak alias attribute to kill its body. See
899 gcc.c-torture/compile/20011119-1.c */
900 if (!DECL_STRUCT_FUNCTION (decl
))
902 cgraph_reset_node (node
);
907 cgraph_analyze_function (node
);
909 for (edge
= node
->callees
; edge
; edge
= edge
->next_callee
)
910 if (!edge
->callee
->reachable
)
911 cgraph_mark_reachable_node (edge
->callee
);
913 if (node
->same_comdat_group
)
915 for (next
= node
->same_comdat_group
;
917 next
= next
->same_comdat_group
)
918 cgraph_mark_reachable_node (next
);
921 /* If decl is a clone of an abstract function, mark that abstract
922 function so that we don't release its body. The DECL_INITIAL() of that
923 abstract function declaration will be later needed to output debug info. */
924 if (DECL_ABSTRACT_ORIGIN (decl
))
926 struct cgraph_node
*origin_node
= cgraph_node (DECL_ABSTRACT_ORIGIN (decl
));
927 origin_node
->abstract_and_needed
= true;
930 /* We finalize local static variables during constructing callgraph
931 edges. Process their attributes too. */
932 process_function_and_variable_attributes (first_processed
,
934 first_processed
= cgraph_nodes
;
935 first_analyzed_var
= varpool_nodes
;
936 varpool_analyze_pending_decls ();
937 cgraph_process_new_functions ();
940 /* Collect entry points to the unit. */
941 if (cgraph_dump_file
)
943 fprintf (cgraph_dump_file
, "Unit entry points:");
944 for (node
= cgraph_nodes
; node
!= first_analyzed
; node
= node
->next
)
946 fprintf (cgraph_dump_file
, " %s", cgraph_node_name (node
));
947 fprintf (cgraph_dump_file
, "\n\nInitial ");
948 dump_cgraph (cgraph_dump_file
);
951 if (cgraph_dump_file
)
952 fprintf (cgraph_dump_file
, "\nReclaiming functions:");
954 for (node
= cgraph_nodes
; node
!= first_analyzed
; node
= next
)
956 tree decl
= node
->decl
;
959 if (node
->local
.finalized
&& !gimple_has_body_p (decl
))
960 cgraph_reset_node (node
);
962 if (!node
->reachable
&& gimple_has_body_p (decl
))
964 if (cgraph_dump_file
)
965 fprintf (cgraph_dump_file
, " %s", cgraph_node_name (node
));
966 cgraph_remove_node (node
);
970 node
->next_needed
= NULL
;
971 gcc_assert (!node
->local
.finalized
|| gimple_has_body_p (decl
));
972 gcc_assert (node
->analyzed
== node
->local
.finalized
);
974 if (cgraph_dump_file
)
976 fprintf (cgraph_dump_file
, "\n\nReclaimed ");
977 dump_cgraph (cgraph_dump_file
);
979 bitmap_obstack_release (NULL
);
980 first_analyzed
= cgraph_nodes
;
985 /* Analyze the whole compilation unit once it is parsed completely. */
988 cgraph_finalize_compilation_unit (void)
990 timevar_push (TV_CGRAPH
);
992 /* Do not skip analyzing the functions if there were errors, we
993 miss diagnostics for following functions otherwise. */
995 /* Emit size functions we didn't inline. */
996 finalize_size_functions ();
998 /* Mark alias targets necessary and emit diagnostics. */
1003 fprintf (stderr
, "\nAnalyzing compilation unit\n");
1007 /* Gimplify and lower all functions, compute reachability and
1008 remove unreachable nodes. */
1009 cgraph_analyze_functions ();
1011 /* Mark alias targets necessary and emit diagnostics. */
1012 finish_aliases_1 ();
1014 /* Gimplify and lower thunks. */
1015 cgraph_analyze_functions ();
1017 /* Finally drive the pass manager. */
1020 timevar_pop (TV_CGRAPH
);
1024 /* Figure out what functions we want to assemble. */
1027 cgraph_mark_functions_to_output (void)
1029 struct cgraph_node
*node
;
1030 #ifdef ENABLE_CHECKING
1031 bool check_same_comdat_groups
= false;
1033 for (node
= cgraph_nodes
; node
; node
= node
->next
)
1034 gcc_assert (!node
->process
);
1037 for (node
= cgraph_nodes
; node
; node
= node
->next
)
1039 tree decl
= node
->decl
;
1040 struct cgraph_edge
*e
;
1042 gcc_assert (!node
->process
|| node
->same_comdat_group
);
1046 for (e
= node
->callers
; e
; e
= e
->next_caller
)
1047 if (e
->inline_failed
)
1050 /* We need to output all local functions that are used and not
1051 always inlined, as well as those that are reachable from
1052 outside the current compilation unit. */
1054 && !node
->global
.inlined_to
1055 && (!cgraph_only_called_directly_p (node
)
1056 || (e
&& node
->reachable
))
1057 && !TREE_ASM_WRITTEN (decl
)
1058 && !DECL_EXTERNAL (decl
))
1061 if (node
->same_comdat_group
)
1063 struct cgraph_node
*next
;
1064 for (next
= node
->same_comdat_group
;
1066 next
= next
->same_comdat_group
)
1070 else if (node
->same_comdat_group
)
1072 #ifdef ENABLE_CHECKING
1073 check_same_comdat_groups
= true;
1078 /* We should've reclaimed all functions that are not needed. */
1079 #ifdef ENABLE_CHECKING
1080 if (!node
->global
.inlined_to
1081 && gimple_has_body_p (decl
)
1082 /* FIXME: in ltrans unit when offline copy is outside partition but inline copies
1083 are inside partition, we can end up not removing the body since we no longer
1084 have analyzed node pointing to it. */
1085 && !node
->in_other_partition
1086 && !DECL_EXTERNAL (decl
))
1088 dump_cgraph_node (stderr
, node
);
1089 internal_error ("failed to reclaim unneeded function");
1092 gcc_assert (node
->global
.inlined_to
1093 || !gimple_has_body_p (decl
)
1094 || node
->in_other_partition
1095 || DECL_EXTERNAL (decl
));
1100 #ifdef ENABLE_CHECKING
1101 if (check_same_comdat_groups
)
1102 for (node
= cgraph_nodes
; node
; node
= node
->next
)
1103 if (node
->same_comdat_group
&& !node
->process
)
1105 tree decl
= node
->decl
;
1106 if (!node
->global
.inlined_to
1107 && gimple_has_body_p (decl
)
1108 /* FIXME: in ltrans unit when offline copy is outside partition but inline copies
1109 are inside partition, we can end up not removing the body since we no longer
1110 have analyzed node pointing to it. */
1111 && !node
->in_other_partition
1112 && !DECL_EXTERNAL (decl
))
1114 dump_cgraph_node (stderr
, node
);
1115 internal_error ("failed to reclaim unneeded function");
1121 /* DECL is FUNCTION_DECL. Initialize datastructures so DECL is a function
1122 in lowered gimple form.
1124 Set current_function_decl and cfun to newly constructed empty function body.
1125 return basic block in the function body. */
1128 init_lowered_empty_function (tree decl
)
1132 current_function_decl
= decl
;
1133 allocate_struct_function (decl
, false);
1134 gimple_register_cfg_hooks ();
1135 init_empty_tree_cfg ();
1136 init_tree_ssa (cfun
);
1137 init_ssa_operands ();
1138 cfun
->gimple_df
->in_ssa_p
= true;
1139 DECL_INITIAL (decl
) = make_node (BLOCK
);
1141 DECL_SAVED_TREE (decl
) = error_mark_node
;
1142 cfun
->curr_properties
|=
1143 (PROP_gimple_lcf
| PROP_gimple_leh
| PROP_cfg
| PROP_referenced_vars
|
1146 /* Create BB for body of the function and connect it properly. */
1147 bb
= create_basic_block (NULL
, (void *) 0, ENTRY_BLOCK_PTR
);
1148 make_edge (ENTRY_BLOCK_PTR
, bb
, 0);
1149 make_edge (bb
, EXIT_BLOCK_PTR
, 0);
1154 /* Adjust PTR by the constant FIXED_OFFSET, and by the vtable
1155 offset indicated by VIRTUAL_OFFSET, if that is
1156 non-null. THIS_ADJUSTING is nonzero for a this adjusting thunk and
1157 zero for a result adjusting thunk. */
1160 thunk_adjust (gimple_stmt_iterator
* bsi
,
1161 tree ptr
, bool this_adjusting
,
1162 HOST_WIDE_INT fixed_offset
, tree virtual_offset
)
1168 && fixed_offset
!= 0)
1170 stmt
= gimple_build_assign (ptr
,
1171 fold_build2_loc (input_location
,
1173 TREE_TYPE (ptr
), ptr
,
1174 size_int (fixed_offset
)));
1175 gsi_insert_after (bsi
, stmt
, GSI_NEW_STMT
);
1178 /* If there's a virtual offset, look up that value in the vtable and
1179 adjust the pointer again. */
1187 if (!vtable_entry_type
)
1189 tree vfunc_type
= make_node (FUNCTION_TYPE
);
1190 TREE_TYPE (vfunc_type
) = integer_type_node
;
1191 TYPE_ARG_TYPES (vfunc_type
) = NULL_TREE
;
1192 layout_type (vfunc_type
);
1194 vtable_entry_type
= build_pointer_type (vfunc_type
);
1198 create_tmp_var (build_pointer_type
1199 (build_pointer_type (vtable_entry_type
)), "vptr");
1201 /* The vptr is always at offset zero in the object. */
1202 stmt
= gimple_build_assign (vtabletmp
,
1203 build1 (NOP_EXPR
, TREE_TYPE (vtabletmp
),
1205 gsi_insert_after (bsi
, stmt
, GSI_NEW_STMT
);
1206 mark_symbols_for_renaming (stmt
);
1207 find_referenced_vars_in (stmt
);
1209 /* Form the vtable address. */
1210 vtabletmp2
= create_tmp_var (TREE_TYPE (TREE_TYPE (vtabletmp
)),
1212 stmt
= gimple_build_assign (vtabletmp2
,
1213 build_simple_mem_ref (vtabletmp
));
1214 gsi_insert_after (bsi
, stmt
, GSI_NEW_STMT
);
1215 mark_symbols_for_renaming (stmt
);
1216 find_referenced_vars_in (stmt
);
1218 /* Find the entry with the vcall offset. */
1219 stmt
= gimple_build_assign (vtabletmp2
,
1220 fold_build2_loc (input_location
,
1222 TREE_TYPE (vtabletmp2
),
1224 fold_convert (sizetype
,
1226 gsi_insert_after (bsi
, stmt
, GSI_NEW_STMT
);
1228 /* Get the offset itself. */
1229 vtabletmp3
= create_tmp_var (TREE_TYPE (TREE_TYPE (vtabletmp2
)),
1231 stmt
= gimple_build_assign (vtabletmp3
,
1232 build_simple_mem_ref (vtabletmp2
));
1233 gsi_insert_after (bsi
, stmt
, GSI_NEW_STMT
);
1234 mark_symbols_for_renaming (stmt
);
1235 find_referenced_vars_in (stmt
);
1237 /* Cast to sizetype. */
1238 offsettmp
= create_tmp_var (sizetype
, "offset");
1239 stmt
= gimple_build_assign (offsettmp
, fold_convert (sizetype
, vtabletmp3
));
1240 gsi_insert_after (bsi
, stmt
, GSI_NEW_STMT
);
1241 mark_symbols_for_renaming (stmt
);
1242 find_referenced_vars_in (stmt
);
1244 /* Adjust the `this' pointer. */
1245 ptr
= fold_build2_loc (input_location
,
1246 POINTER_PLUS_EXPR
, TREE_TYPE (ptr
), ptr
,
1251 && fixed_offset
!= 0)
1252 /* Adjust the pointer by the constant. */
1256 if (TREE_CODE (ptr
) == VAR_DECL
)
1260 ptrtmp
= create_tmp_var (TREE_TYPE (ptr
), "ptr");
1261 stmt
= gimple_build_assign (ptrtmp
, ptr
);
1262 gsi_insert_after (bsi
, stmt
, GSI_NEW_STMT
);
1263 mark_symbols_for_renaming (stmt
);
1264 find_referenced_vars_in (stmt
);
1266 ptr
= fold_build2_loc (input_location
,
1267 POINTER_PLUS_EXPR
, TREE_TYPE (ptrtmp
), ptrtmp
,
1268 size_int (fixed_offset
));
1271 /* Emit the statement and gimplify the adjustment expression. */
1272 ret
= create_tmp_var (TREE_TYPE (ptr
), "adjusted_this");
1273 stmt
= gimple_build_assign (ret
, ptr
);
1274 mark_symbols_for_renaming (stmt
);
1275 find_referenced_vars_in (stmt
);
1276 gsi_insert_after (bsi
, stmt
, GSI_NEW_STMT
);
1281 /* Produce assembler for thunk NODE. */
1284 assemble_thunk (struct cgraph_node
*node
)
1286 bool this_adjusting
= node
->thunk
.this_adjusting
;
1287 HOST_WIDE_INT fixed_offset
= node
->thunk
.fixed_offset
;
1288 HOST_WIDE_INT virtual_value
= node
->thunk
.virtual_value
;
1289 tree virtual_offset
= NULL
;
1290 tree alias
= node
->thunk
.alias
;
1291 tree thunk_fndecl
= node
->decl
;
1292 tree a
= DECL_ARGUMENTS (thunk_fndecl
);
1294 current_function_decl
= thunk_fndecl
;
1297 && targetm
.asm_out
.can_output_mi_thunk (thunk_fndecl
, fixed_offset
,
1298 virtual_value
, alias
))
1303 DECL_RESULT (thunk_fndecl
)
1304 = build_decl (DECL_SOURCE_LOCATION (thunk_fndecl
),
1305 RESULT_DECL
, 0, integer_type_node
);
1306 fnname
= IDENTIFIER_POINTER (DECL_ASSEMBLER_NAME (thunk_fndecl
));
1308 /* The back end expects DECL_INITIAL to contain a BLOCK, so we
1310 fn_block
= make_node (BLOCK
);
1311 BLOCK_VARS (fn_block
) = a
;
1312 DECL_INITIAL (thunk_fndecl
) = fn_block
;
1313 init_function_start (thunk_fndecl
);
1315 assemble_start_function (thunk_fndecl
, fnname
);
1317 targetm
.asm_out
.output_mi_thunk (asm_out_file
, thunk_fndecl
,
1318 fixed_offset
, virtual_value
, alias
);
1320 assemble_end_function (thunk_fndecl
, fnname
);
1321 init_insn_lengths ();
1322 free_after_compilation (cfun
);
1324 TREE_ASM_WRITTEN (thunk_fndecl
) = 1;
1329 basic_block bb
, then_bb
, else_bb
, return_bb
;
1330 gimple_stmt_iterator bsi
;
1336 VEC(tree
, heap
) *vargs
;
1341 DECL_IGNORED_P (thunk_fndecl
) = 1;
1342 bitmap_obstack_initialize (NULL
);
1344 if (node
->thunk
.virtual_offset_p
)
1345 virtual_offset
= size_int (virtual_value
);
1347 /* Build the return declaration for the function. */
1348 restype
= TREE_TYPE (TREE_TYPE (thunk_fndecl
));
1349 if (DECL_RESULT (thunk_fndecl
) == NULL_TREE
)
1351 resdecl
= build_decl (input_location
, RESULT_DECL
, 0, restype
);
1352 DECL_ARTIFICIAL (resdecl
) = 1;
1353 DECL_IGNORED_P (resdecl
) = 1;
1354 DECL_RESULT (thunk_fndecl
) = resdecl
;
1357 resdecl
= DECL_RESULT (thunk_fndecl
);
1359 bb
= then_bb
= else_bb
= return_bb
= init_lowered_empty_function (thunk_fndecl
);
1361 bsi
= gsi_start_bb (bb
);
1363 /* Build call to the function being thunked. */
1364 if (!VOID_TYPE_P (restype
))
1366 if (!is_gimple_reg_type (restype
))
1369 add_local_decl (cfun
, restmp
);
1370 BLOCK_VARS (DECL_INITIAL (current_function_decl
)) = restmp
;
1373 restmp
= create_tmp_var_raw (restype
, "retval");
1376 for (arg
= a
; arg
; arg
= DECL_CHAIN (arg
))
1378 vargs
= VEC_alloc (tree
, heap
, nargs
);
1380 VEC_quick_push (tree
, vargs
,
1385 VEC_quick_push (tree
, vargs
, a
);
1386 for (i
= 1, arg
= DECL_CHAIN (a
); i
< nargs
; i
++, arg
= DECL_CHAIN (arg
))
1387 VEC_quick_push (tree
, vargs
, arg
);
1388 call
= gimple_build_call_vec (build_fold_addr_expr_loc (0, alias
), vargs
);
1389 VEC_free (tree
, heap
, vargs
);
1390 gimple_call_set_cannot_inline (call
, true);
1391 gimple_call_set_from_thunk (call
, true);
1393 gimple_call_set_lhs (call
, restmp
);
1394 gsi_insert_after (&bsi
, call
, GSI_NEW_STMT
);
1395 mark_symbols_for_renaming (call
);
1396 find_referenced_vars_in (call
);
1399 if (restmp
&& !this_adjusting
)
1401 tree true_label
= NULL_TREE
;
1403 if (TREE_CODE (TREE_TYPE (restmp
)) == POINTER_TYPE
)
1406 /* If the return type is a pointer, we need to
1407 protect against NULL. We know there will be an
1408 adjustment, because that's why we're emitting a
1410 then_bb
= create_basic_block (NULL
, (void *) 0, bb
);
1411 return_bb
= create_basic_block (NULL
, (void *) 0, then_bb
);
1412 else_bb
= create_basic_block (NULL
, (void *) 0, else_bb
);
1413 remove_edge (single_succ_edge (bb
));
1414 true_label
= gimple_block_label (then_bb
);
1415 stmt
= gimple_build_cond (NE_EXPR
, restmp
,
1416 fold_convert (TREE_TYPE (restmp
),
1418 NULL_TREE
, NULL_TREE
);
1419 gsi_insert_after (&bsi
, stmt
, GSI_NEW_STMT
);
1420 make_edge (bb
, then_bb
, EDGE_TRUE_VALUE
);
1421 make_edge (bb
, else_bb
, EDGE_FALSE_VALUE
);
1422 make_edge (return_bb
, EXIT_BLOCK_PTR
, 0);
1423 make_edge (then_bb
, return_bb
, EDGE_FALLTHRU
);
1424 make_edge (else_bb
, return_bb
, EDGE_FALLTHRU
);
1425 bsi
= gsi_last_bb (then_bb
);
1428 restmp
= thunk_adjust (&bsi
, restmp
, /*this_adjusting=*/0,
1429 fixed_offset
, virtual_offset
);
1433 bsi
= gsi_last_bb (else_bb
);
1434 stmt
= gimple_build_assign (restmp
, fold_convert (TREE_TYPE (restmp
),
1435 integer_zero_node
));
1436 gsi_insert_after (&bsi
, stmt
, GSI_NEW_STMT
);
1437 bsi
= gsi_last_bb (return_bb
);
1441 gimple_call_set_tail (call
, true);
1443 /* Build return value. */
1444 ret
= gimple_build_return (restmp
);
1445 gsi_insert_after (&bsi
, ret
, GSI_NEW_STMT
);
1447 delete_unreachable_blocks ();
1448 update_ssa (TODO_update_ssa
);
1450 cgraph_remove_same_body_alias (node
);
1451 /* Since we want to emit the thunk, we explicitly mark its name as
1453 cgraph_add_new_function (thunk_fndecl
, true);
1454 bitmap_obstack_release (NULL
);
1456 current_function_decl
= NULL
;
1459 /* Expand function specified by NODE. */
1462 cgraph_expand_function (struct cgraph_node
*node
)
1464 tree decl
= node
->decl
;
1466 /* We ought to not compile any inline clones. */
1467 gcc_assert (!node
->global
.inlined_to
);
1469 announce_function (decl
);
1471 if (node
->same_body
)
1473 struct cgraph_node
*alias
, *next
;
1474 bool saved_alias
= node
->alias
;
1475 for (alias
= node
->same_body
;
1476 alias
&& alias
->next
; alias
= alias
->next
)
1478 /* Walk aliases in the order they were created; it is possible that
1479 thunks reffers to the aliases made earlier. */
1480 for (; alias
; alias
= next
)
1482 next
= alias
->previous
;
1483 if (!alias
->thunk
.thunk_p
)
1484 assemble_alias (alias
->decl
,
1485 DECL_ASSEMBLER_NAME (alias
->thunk
.alias
));
1487 assemble_thunk (alias
);
1489 node
->alias
= saved_alias
;
1490 cgraph_process_new_functions ();
1493 gcc_assert (node
->lowered
);
1495 /* Generate RTL for the body of DECL. */
1496 tree_rest_of_compilation (decl
);
1498 /* Make sure that BE didn't give up on compiling. */
1499 gcc_assert (TREE_ASM_WRITTEN (decl
));
1500 current_function_decl
= NULL
;
1501 gcc_assert (!cgraph_preserve_function_body_p (decl
));
1502 cgraph_release_function_body (node
);
1503 /* Eliminate all call edges. This is important so the GIMPLE_CALL no longer
1504 points to the dead function body. */
1505 cgraph_node_remove_callees (node
);
1507 cgraph_function_flags_ready
= true;
1510 /* Return true when CALLER_DECL should be inlined into CALLEE_DECL. */
1513 cgraph_inline_p (struct cgraph_edge
*e
, cgraph_inline_failed_t
*reason
)
1515 *reason
= e
->inline_failed
;
1516 return !e
->inline_failed
;
1521 /* Expand all functions that must be output.
1523 Attempt to topologically sort the nodes so function is output when
1524 all called functions are already assembled to allow data to be
1525 propagated across the callgraph. Use a stack to get smaller distance
1526 between a function and its callees (later we may choose to use a more
1527 sophisticated algorithm for function reordering; we will likely want
1528 to use subsections to make the output functions appear in top-down
1532 cgraph_expand_all_functions (void)
1534 struct cgraph_node
*node
;
1535 struct cgraph_node
**order
= XCNEWVEC (struct cgraph_node
*, cgraph_n_nodes
);
1536 int order_pos
, new_order_pos
= 0;
1539 order_pos
= cgraph_postorder (order
);
1540 gcc_assert (order_pos
== cgraph_n_nodes
);
1542 /* Garbage collector may remove inline clones we eliminate during
1543 optimization. So we must be sure to not reference them. */
1544 for (i
= 0; i
< order_pos
; i
++)
1545 if (order
[i
]->process
)
1546 order
[new_order_pos
++] = order
[i
];
1548 for (i
= new_order_pos
- 1; i
>= 0; i
--)
1553 gcc_assert (node
->reachable
);
1555 cgraph_expand_function (node
);
1558 cgraph_process_new_functions ();
1564 /* This is used to sort the node types by the cgraph order number. */
1566 enum cgraph_order_sort_kind
1568 ORDER_UNDEFINED
= 0,
1574 struct cgraph_order_sort
1576 enum cgraph_order_sort_kind kind
;
1579 struct cgraph_node
*f
;
1580 struct varpool_node
*v
;
1581 struct cgraph_asm_node
*a
;
1585 /* Output all functions, variables, and asm statements in the order
1586 according to their order fields, which is the order in which they
1587 appeared in the file. This implements -fno-toplevel-reorder. In
1588 this mode we may output functions and variables which don't really
1589 need to be output. */
1592 cgraph_output_in_order (void)
1595 struct cgraph_order_sort
*nodes
;
1597 struct cgraph_node
*pf
;
1598 struct varpool_node
*pv
;
1599 struct cgraph_asm_node
*pa
;
1602 nodes
= XCNEWVEC (struct cgraph_order_sort
, max
);
1604 varpool_analyze_pending_decls ();
1606 for (pf
= cgraph_nodes
; pf
; pf
= pf
->next
)
1611 gcc_assert (nodes
[i
].kind
== ORDER_UNDEFINED
);
1612 nodes
[i
].kind
= ORDER_FUNCTION
;
1617 for (pv
= varpool_nodes_queue
; pv
; pv
= pv
->next_needed
)
1620 gcc_assert (nodes
[i
].kind
== ORDER_UNDEFINED
);
1621 nodes
[i
].kind
= ORDER_VAR
;
1625 for (pa
= cgraph_asm_nodes
; pa
; pa
= pa
->next
)
1628 gcc_assert (nodes
[i
].kind
== ORDER_UNDEFINED
);
1629 nodes
[i
].kind
= ORDER_ASM
;
1633 /* In toplevel reorder mode we output all statics; mark them as needed. */
1634 for (i
= 0; i
< max
; ++i
)
1636 if (nodes
[i
].kind
== ORDER_VAR
)
1638 varpool_mark_needed_node (nodes
[i
].u
.v
);
1641 varpool_empty_needed_queue ();
1643 for (i
= 0; i
< max
; ++i
)
1645 switch (nodes
[i
].kind
)
1647 case ORDER_FUNCTION
:
1648 nodes
[i
].u
.f
->process
= 0;
1649 cgraph_expand_function (nodes
[i
].u
.f
);
1653 varpool_assemble_decl (nodes
[i
].u
.v
);
1657 assemble_asm (nodes
[i
].u
.a
->asm_str
);
1660 case ORDER_UNDEFINED
:
1668 cgraph_asm_nodes
= NULL
;
1672 /* Return true when function body of DECL still needs to be kept around
1673 for later re-use. */
1675 cgraph_preserve_function_body_p (tree decl
)
1677 struct cgraph_node
*node
;
1679 gcc_assert (cgraph_global_info_ready
);
1680 /* Look if there is any clone around. */
1681 node
= cgraph_node (decl
);
1691 current_function_decl
= NULL
;
1692 gimple_register_cfg_hooks ();
1693 bitmap_obstack_initialize (NULL
);
1695 invoke_plugin_callbacks (PLUGIN_ALL_IPA_PASSES_START
, NULL
);
1698 execute_ipa_pass_list (all_small_ipa_passes
);
1700 /* If pass_all_early_optimizations was not scheduled, the state of
1701 the cgraph will not be properly updated. Update it now. */
1702 if (cgraph_state
< CGRAPH_STATE_IPA_SSA
)
1703 cgraph_state
= CGRAPH_STATE_IPA_SSA
;
1707 /* Generate coverage variables and constructors. */
1710 /* Process new functions added. */
1712 current_function_decl
= NULL
;
1713 cgraph_process_new_functions ();
1715 execute_ipa_summary_passes
1716 ((struct ipa_opt_pass_d
*) all_regular_ipa_passes
);
1719 /* Some targets need to handle LTO assembler output specially. */
1720 if (flag_generate_lto
)
1721 targetm
.asm_out
.lto_start ();
1723 execute_ipa_summary_passes ((struct ipa_opt_pass_d
*) all_lto_gen_passes
);
1726 ipa_write_summaries ();
1728 if (flag_generate_lto
)
1729 targetm
.asm_out
.lto_end ();
1732 execute_ipa_pass_list (all_regular_ipa_passes
);
1733 invoke_plugin_callbacks (PLUGIN_ALL_IPA_PASSES_END
, NULL
);
1735 bitmap_obstack_release (NULL
);
1739 /* Perform simple optimizations based on callgraph. */
1742 cgraph_optimize (void)
1747 #ifdef ENABLE_CHECKING
1751 /* Frontend may output common variables after the unit has been finalized.
1752 It is safe to deal with them here as they are always zero initialized. */
1753 varpool_analyze_pending_decls ();
1755 timevar_push (TV_CGRAPHOPT
);
1756 if (pre_ipa_mem_report
)
1758 fprintf (stderr
, "Memory consumption before IPA\n");
1759 dump_memory_report (false);
1762 fprintf (stderr
, "Performing interprocedural optimizations\n");
1763 cgraph_state
= CGRAPH_STATE_IPA
;
1765 /* Don't run the IPA passes if there was any error or sorry messages. */
1769 /* Do nothing else if any IPA pass found errors. */
1772 timevar_pop (TV_CGRAPHOPT
);
1776 /* This pass remove bodies of extern inline functions we never inlined.
1777 Do this later so other IPA passes see what is really going on. */
1778 cgraph_remove_unreachable_nodes (false, dump_file
);
1779 cgraph_global_info_ready
= true;
1780 if (cgraph_dump_file
)
1782 fprintf (cgraph_dump_file
, "Optimized ");
1783 dump_cgraph (cgraph_dump_file
);
1784 dump_varpool (cgraph_dump_file
);
1786 if (post_ipa_mem_report
)
1788 fprintf (stderr
, "Memory consumption after IPA\n");
1789 dump_memory_report (false);
1791 timevar_pop (TV_CGRAPHOPT
);
1793 /* Output everything. */
1794 (*debug_hooks
->assembly_start
) ();
1796 fprintf (stderr
, "Assembling functions:\n");
1797 #ifdef ENABLE_CHECKING
1801 cgraph_materialize_all_clones ();
1802 cgraph_mark_functions_to_output ();
1804 cgraph_state
= CGRAPH_STATE_EXPANSION
;
1805 if (!flag_toplevel_reorder
)
1806 cgraph_output_in_order ();
1809 cgraph_output_pending_asms ();
1811 cgraph_expand_all_functions ();
1812 varpool_remove_unreferenced_decls ();
1814 varpool_assemble_pending_decls ();
1816 cgraph_process_new_functions ();
1817 cgraph_state
= CGRAPH_STATE_FINISHED
;
1819 if (cgraph_dump_file
)
1821 fprintf (cgraph_dump_file
, "\nFinal ");
1822 dump_cgraph (cgraph_dump_file
);
1824 #ifdef ENABLE_CHECKING
1826 /* Double check that all inline clones are gone and that all
1827 function bodies have been released from memory. */
1830 struct cgraph_node
*node
;
1831 bool error_found
= false;
1833 for (node
= cgraph_nodes
; node
; node
= node
->next
)
1835 && (node
->global
.inlined_to
1836 || gimple_has_body_p (node
->decl
)))
1839 dump_cgraph_node (stderr
, node
);
1842 internal_error ("nodes with unreleased memory found");
1850 if (!cgraph_dump_file
)
1851 cgraph_dump_file
= dump_begin (TDI_cgraph
, NULL
);
1854 /* The edges representing the callers of the NEW_VERSION node were
1855 fixed by cgraph_function_versioning (), now the call_expr in their
1856 respective tree code should be updated to call the NEW_VERSION. */
1859 update_call_expr (struct cgraph_node
*new_version
)
1861 struct cgraph_edge
*e
;
1863 gcc_assert (new_version
);
1865 /* Update the call expr on the edges to call the new version. */
1866 for (e
= new_version
->callers
; e
; e
= e
->next_caller
)
1868 struct function
*inner_function
= DECL_STRUCT_FUNCTION (e
->caller
->decl
);
1869 gimple_call_set_fndecl (e
->call_stmt
, new_version
->decl
);
1870 maybe_clean_eh_stmt_fn (inner_function
, e
->call_stmt
);
1875 /* Create a new cgraph node which is the new version of
1876 OLD_VERSION node. REDIRECT_CALLERS holds the callers
1877 edges which should be redirected to point to
1878 NEW_VERSION. ALL the callees edges of OLD_VERSION
1879 are cloned to the new version node. Return the new
1882 If non-NULL BLOCK_TO_COPY determine what basic blocks
1883 was copied to prevent duplications of calls that are dead
1886 static struct cgraph_node
*
1887 cgraph_copy_node_for_versioning (struct cgraph_node
*old_version
,
1889 VEC(cgraph_edge_p
,heap
) *redirect_callers
,
1892 struct cgraph_node
*new_version
;
1893 struct cgraph_edge
*e
;
1896 gcc_assert (old_version
);
1898 new_version
= cgraph_node (new_decl
);
1900 new_version
->analyzed
= true;
1901 new_version
->local
= old_version
->local
;
1902 new_version
->local
.externally_visible
= false;
1903 new_version
->local
.local
= true;
1904 new_version
->local
.vtable_method
= false;
1905 new_version
->global
= old_version
->global
;
1906 new_version
->rtl
= old_version
->rtl
;
1907 new_version
->reachable
= true;
1908 new_version
->count
= old_version
->count
;
1910 for (e
= old_version
->callees
; e
; e
=e
->next_callee
)
1912 || bitmap_bit_p (bbs_to_copy
, gimple_bb (e
->call_stmt
)->index
))
1913 cgraph_clone_edge (e
, new_version
, e
->call_stmt
,
1914 e
->lto_stmt_uid
, REG_BR_PROB_BASE
,
1916 e
->loop_nest
, true);
1917 for (e
= old_version
->indirect_calls
; e
; e
=e
->next_callee
)
1919 || bitmap_bit_p (bbs_to_copy
, gimple_bb (e
->call_stmt
)->index
))
1920 cgraph_clone_edge (e
, new_version
, e
->call_stmt
,
1921 e
->lto_stmt_uid
, REG_BR_PROB_BASE
,
1923 e
->loop_nest
, true);
1924 FOR_EACH_VEC_ELT (cgraph_edge_p
, redirect_callers
, i
, e
)
1926 /* Redirect calls to the old version node to point to its new
1928 cgraph_redirect_edge_callee (e
, new_version
);
1934 /* Perform function versioning.
1935 Function versioning includes copying of the tree and
1936 a callgraph update (creating a new cgraph node and updating
1937 its callees and callers).
1939 REDIRECT_CALLERS varray includes the edges to be redirected
1942 TREE_MAP is a mapping of tree nodes we want to replace with
1943 new ones (according to results of prior analysis).
1944 OLD_VERSION_NODE is the node that is versioned.
1945 It returns the new version's cgraph node.
1946 If non-NULL ARGS_TO_SKIP determine function parameters to remove
1948 If non-NULL BLOCK_TO_COPY determine what basic blocks to copy.
1949 If non_NULL NEW_ENTRY determine new entry BB of the clone. */
1951 struct cgraph_node
*
1952 cgraph_function_versioning (struct cgraph_node
*old_version_node
,
1953 VEC(cgraph_edge_p
,heap
) *redirect_callers
,
1954 VEC (ipa_replace_map_p
,gc
)* tree_map
,
1955 bitmap args_to_skip
,
1957 basic_block new_entry_block
,
1958 const char *clone_name
)
1960 tree old_decl
= old_version_node
->decl
;
1961 struct cgraph_node
*new_version_node
= NULL
;
1964 if (!tree_versionable_function_p (old_decl
))
1967 /* Make a new FUNCTION_DECL tree node for the
1970 new_decl
= copy_node (old_decl
);
1972 new_decl
= build_function_decl_skip_args (old_decl
, args_to_skip
);
1974 /* Generate a new name for the new version. */
1975 DECL_NAME (new_decl
) = clone_function_name (old_decl
, clone_name
);
1976 SET_DECL_ASSEMBLER_NAME (new_decl
, DECL_NAME (new_decl
));
1977 SET_DECL_RTL (new_decl
, NULL
);
1979 /* Create the new version's call-graph node.
1980 and update the edges of the new node. */
1982 cgraph_copy_node_for_versioning (old_version_node
, new_decl
,
1983 redirect_callers
, bbs_to_copy
);
1985 /* Copy the OLD_VERSION_NODE function tree to the new version. */
1986 tree_function_versioning (old_decl
, new_decl
, tree_map
, false, args_to_skip
,
1987 bbs_to_copy
, new_entry_block
);
1989 /* Update the new version's properties.
1990 Make The new version visible only within this translation unit. Make sure
1991 that is not weak also.
1992 ??? We cannot use COMDAT linkage because there is no
1993 ABI support for this. */
1994 cgraph_make_decl_local (new_version_node
->decl
);
1995 DECL_VIRTUAL_P (new_version_node
->decl
) = 0;
1996 new_version_node
->local
.externally_visible
= 0;
1997 new_version_node
->local
.local
= 1;
1998 new_version_node
->lowered
= true;
2000 /* Update the call_expr on the edges to call the new version node. */
2001 update_call_expr (new_version_node
);
2003 cgraph_call_function_insertion_hooks (new_version_node
);
2004 return new_version_node
;
2007 /* Produce separate function body for inline clones so the offline copy can be
2008 modified without affecting them. */
2009 struct cgraph_node
*
2010 save_inline_function_body (struct cgraph_node
*node
)
2012 struct cgraph_node
*first_clone
, *n
;
2014 gcc_assert (node
== cgraph_node (node
->decl
));
2016 cgraph_lower_function (node
);
2018 first_clone
= node
->clones
;
2020 first_clone
->decl
= copy_node (node
->decl
);
2021 cgraph_insert_node_to_hashtable (first_clone
);
2022 gcc_assert (first_clone
== cgraph_node (first_clone
->decl
));
2023 if (first_clone
->next_sibling_clone
)
2025 for (n
= first_clone
->next_sibling_clone
; n
->next_sibling_clone
; n
= n
->next_sibling_clone
)
2026 n
->clone_of
= first_clone
;
2027 n
->clone_of
= first_clone
;
2028 n
->next_sibling_clone
= first_clone
->clones
;
2029 if (first_clone
->clones
)
2030 first_clone
->clones
->prev_sibling_clone
= n
;
2031 first_clone
->clones
= first_clone
->next_sibling_clone
;
2032 first_clone
->next_sibling_clone
->prev_sibling_clone
= NULL
;
2033 first_clone
->next_sibling_clone
= NULL
;
2034 gcc_assert (!first_clone
->prev_sibling_clone
);
2036 first_clone
->clone_of
= NULL
;
2037 node
->clones
= NULL
;
2039 if (first_clone
->clones
)
2040 for (n
= first_clone
->clones
; n
!= first_clone
;)
2042 gcc_assert (n
->decl
== node
->decl
);
2043 n
->decl
= first_clone
->decl
;
2046 else if (n
->next_sibling_clone
)
2047 n
= n
->next_sibling_clone
;
2050 while (n
!= first_clone
&& !n
->next_sibling_clone
)
2052 if (n
!= first_clone
)
2053 n
= n
->next_sibling_clone
;
2057 /* Copy the OLD_VERSION_NODE function tree to the new version. */
2058 tree_function_versioning (node
->decl
, first_clone
->decl
, NULL
, true, NULL
,
2061 DECL_EXTERNAL (first_clone
->decl
) = 0;
2062 DECL_COMDAT_GROUP (first_clone
->decl
) = NULL_TREE
;
2063 TREE_PUBLIC (first_clone
->decl
) = 0;
2064 DECL_COMDAT (first_clone
->decl
) = 0;
2065 VEC_free (ipa_opt_pass
, heap
,
2066 first_clone
->ipa_transforms_to_apply
);
2067 first_clone
->ipa_transforms_to_apply
= NULL
;
2069 #ifdef ENABLE_CHECKING
2070 verify_cgraph_node (first_clone
);
2075 /* Given virtual clone, turn it into actual clone. */
2077 cgraph_materialize_clone (struct cgraph_node
*node
)
2079 bitmap_obstack_initialize (NULL
);
2080 node
->former_clone_of
= node
->clone_of
->decl
;
2081 if (node
->clone_of
->former_clone_of
)
2082 node
->former_clone_of
= node
->clone_of
->former_clone_of
;
2083 /* Copy the OLD_VERSION_NODE function tree to the new version. */
2084 tree_function_versioning (node
->clone_of
->decl
, node
->decl
,
2085 node
->clone
.tree_map
, true,
2086 node
->clone
.args_to_skip
, NULL
, NULL
);
2087 if (cgraph_dump_file
)
2089 dump_function_to_file (node
->clone_of
->decl
, cgraph_dump_file
, dump_flags
);
2090 dump_function_to_file (node
->decl
, cgraph_dump_file
, dump_flags
);
2093 /* Function is no longer clone. */
2094 if (node
->next_sibling_clone
)
2095 node
->next_sibling_clone
->prev_sibling_clone
= node
->prev_sibling_clone
;
2096 if (node
->prev_sibling_clone
)
2097 node
->prev_sibling_clone
->next_sibling_clone
= node
->next_sibling_clone
;
2099 node
->clone_of
->clones
= node
->next_sibling_clone
;
2100 node
->next_sibling_clone
= NULL
;
2101 node
->prev_sibling_clone
= NULL
;
2102 if (!node
->clone_of
->analyzed
&& !node
->clone_of
->clones
)
2104 cgraph_release_function_body (node
->clone_of
);
2105 cgraph_node_remove_callees (node
->clone_of
);
2106 ipa_remove_all_references (&node
->clone_of
->ref_list
);
2108 node
->clone_of
= NULL
;
2109 bitmap_obstack_release (NULL
);
2112 /* If necessary, change the function declaration in the call statement
2113 associated with E so that it corresponds to the edge callee. */
2116 cgraph_redirect_edge_call_stmt_to_callee (struct cgraph_edge
*e
)
2118 tree decl
= gimple_call_fndecl (e
->call_stmt
);
2120 #ifdef ENABLE_CHECKING
2121 struct cgraph_node
*node
;
2124 if (e
->indirect_unknown_callee
2125 || decl
== e
->callee
->decl
2126 /* Don't update call from same body alias to the real function. */
2127 || (decl
&& cgraph_get_node (decl
) == cgraph_get_node (e
->callee
->decl
)))
2128 return e
->call_stmt
;
2130 #ifdef ENABLE_CHECKING
2133 node
= cgraph_get_node (decl
);
2134 gcc_assert (!node
|| !node
->clone
.combined_args_to_skip
);
2138 if (cgraph_dump_file
)
2140 fprintf (cgraph_dump_file
, "updating call of %s/%i -> %s/%i: ",
2141 cgraph_node_name (e
->caller
), e
->caller
->uid
,
2142 cgraph_node_name (e
->callee
), e
->callee
->uid
);
2143 print_gimple_stmt (cgraph_dump_file
, e
->call_stmt
, 0, dump_flags
);
2144 if (e
->callee
->clone
.combined_args_to_skip
)
2146 fprintf (cgraph_dump_file
, " combined args to skip: ");
2147 dump_bitmap (cgraph_dump_file
,
2148 e
->callee
->clone
.combined_args_to_skip
);
2152 if (e
->callee
->clone
.combined_args_to_skip
)
2154 gimple_stmt_iterator gsi
;
2158 = gimple_call_copy_skip_args (e
->call_stmt
,
2159 e
->callee
->clone
.combined_args_to_skip
);
2160 gimple_call_set_fndecl (new_stmt
, e
->callee
->decl
);
2162 if (gimple_vdef (new_stmt
)
2163 && TREE_CODE (gimple_vdef (new_stmt
)) == SSA_NAME
)
2164 SSA_NAME_DEF_STMT (gimple_vdef (new_stmt
)) = new_stmt
;
2166 gsi
= gsi_for_stmt (e
->call_stmt
);
2167 gsi_replace (&gsi
, new_stmt
, false);
2168 /* We need to defer cleaning EH info on the new statement to
2169 fixup-cfg. We may not have dominator information at this point
2170 and thus would end up with unreachable blocks and have no way
2171 to communicate that we need to run CFG cleanup then. */
2172 lp_nr
= lookup_stmt_eh_lp (e
->call_stmt
);
2175 remove_stmt_from_eh_lp (e
->call_stmt
);
2176 add_stmt_to_eh_lp (new_stmt
, lp_nr
);
2181 new_stmt
= e
->call_stmt
;
2182 gimple_call_set_fndecl (new_stmt
, e
->callee
->decl
);
2183 update_stmt (new_stmt
);
2186 cgraph_set_call_stmt_including_clones (e
->caller
, e
->call_stmt
, new_stmt
);
2188 if (cgraph_dump_file
)
2190 fprintf (cgraph_dump_file
, " updated to:");
2191 print_gimple_stmt (cgraph_dump_file
, e
->call_stmt
, 0, dump_flags
);
2196 /* Once all functions from compilation unit are in memory, produce all clones
2197 and update all calls. We might also do this on demand if we don't want to
2198 bring all functions to memory prior compilation, but current WHOPR
2199 implementation does that and it is is bit easier to keep everything right in
2202 cgraph_materialize_all_clones (void)
2204 struct cgraph_node
*node
;
2205 bool stabilized
= false;
2207 if (cgraph_dump_file
)
2208 fprintf (cgraph_dump_file
, "Materializing clones\n");
2209 #ifdef ENABLE_CHECKING
2213 /* We can also do topological order, but number of iterations should be
2214 bounded by number of IPA passes since single IPA pass is probably not
2215 going to create clones of clones it created itself. */
2219 for (node
= cgraph_nodes
; node
; node
= node
->next
)
2221 if (node
->clone_of
&& node
->decl
!= node
->clone_of
->decl
2222 && !gimple_has_body_p (node
->decl
))
2224 if (gimple_has_body_p (node
->clone_of
->decl
))
2226 if (cgraph_dump_file
)
2228 fprintf (cgraph_dump_file
, "clonning %s to %s\n",
2229 cgraph_node_name (node
->clone_of
),
2230 cgraph_node_name (node
));
2231 if (node
->clone
.tree_map
)
2234 fprintf (cgraph_dump_file
, " replace map: ");
2235 for (i
= 0; i
< VEC_length (ipa_replace_map_p
,
2236 node
->clone
.tree_map
);
2239 struct ipa_replace_map
*replace_info
;
2240 replace_info
= VEC_index (ipa_replace_map_p
,
2241 node
->clone
.tree_map
,
2243 print_generic_expr (cgraph_dump_file
, replace_info
->old_tree
, 0);
2244 fprintf (cgraph_dump_file
, " -> ");
2245 print_generic_expr (cgraph_dump_file
, replace_info
->new_tree
, 0);
2246 fprintf (cgraph_dump_file
, "%s%s;",
2247 replace_info
->replace_p
? "(replace)":"",
2248 replace_info
->ref_p
? "(ref)":"");
2250 fprintf (cgraph_dump_file
, "\n");
2252 if (node
->clone
.args_to_skip
)
2254 fprintf (cgraph_dump_file
, " args_to_skip: ");
2255 dump_bitmap (cgraph_dump_file
, node
->clone
.args_to_skip
);
2257 if (node
->clone
.args_to_skip
)
2259 fprintf (cgraph_dump_file
, " combined_args_to_skip:");
2260 dump_bitmap (cgraph_dump_file
, node
->clone
.combined_args_to_skip
);
2263 cgraph_materialize_clone (node
);
2269 for (node
= cgraph_nodes
; node
; node
= node
->next
)
2270 if (!node
->analyzed
&& node
->callees
)
2271 cgraph_node_remove_callees (node
);
2272 if (cgraph_dump_file
)
2273 fprintf (cgraph_dump_file
, "Materialization Call site updates done.\n");
2274 #ifdef ENABLE_CHECKING
2277 cgraph_remove_unreachable_nodes (false, cgraph_dump_file
);
2280 #include "gt-cgraphunit.h"