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"
130 #include "function.h"
131 #include "ipa-prop.h"
133 #include "tree-iterator.h"
134 #include "tree-pass.h"
135 #include "tree-dump.h"
137 #include "coverage.h"
140 static void cgraph_expand_all_functions (void);
141 static void cgraph_mark_functions_to_output (void);
142 static void cgraph_expand_function (struct cgraph_node *);
143 static void cgraph_output_pending_asms (void);
144 static void cgraph_analyze_function (struct cgraph_node *);
146 static FILE *cgraph_dump_file;
148 /* A vector of FUNCTION_DECLs declared as static constructors. */
149 static GTY (()) VEC(tree, gc) *static_ctors;
150 /* A vector of FUNCTION_DECLs declared as static destructors. */
151 static GTY (()) VEC(tree, gc) *static_dtors;
153 /* Used for vtable lookup in thunk adjusting. */
154 static GTY (()) tree vtable_entry_type;
156 /* When target does not have ctors and dtors, we call all constructor
157 and destructor by special initialization/destruction function
158 recognized by collect2.
160 When we are going to build this function, collect all constructors and
161 destructors and turn them into normal functions. */
164 record_cdtor_fn (tree fndecl)
166 struct cgraph_node *node;
167 if (targetm.have_ctors_dtors
168 || (!DECL_STATIC_CONSTRUCTOR (fndecl)
169 && !DECL_STATIC_DESTRUCTOR (fndecl)))
172 if (DECL_STATIC_CONSTRUCTOR (fndecl))
174 VEC_safe_push (tree, gc, static_ctors, fndecl);
175 DECL_STATIC_CONSTRUCTOR (fndecl) = 0;
177 if (DECL_STATIC_DESTRUCTOR (fndecl))
179 VEC_safe_push (tree, gc, static_dtors, fndecl);
180 DECL_STATIC_DESTRUCTOR (fndecl) = 0;
182 node = cgraph_node (fndecl);
183 node->local.disregard_inline_limits = 1;
184 cgraph_mark_reachable_node (node);
187 /* Define global constructors/destructor functions for the CDTORS, of
188 which they are LEN. The CDTORS are sorted by initialization
189 priority. If CTOR_P is true, these are constructors; otherwise,
190 they are destructors. */
193 build_cdtor (bool ctor_p, tree *cdtors, size_t len)
202 priority_type priority;
206 /* Find the next batch of constructors/destructors with the same
207 initialization priority. */
212 p = ctor_p ? DECL_INIT_PRIORITY (fn) : DECL_FINI_PRIORITY (fn);
215 else if (p != priority)
217 append_to_statement_list (build_function_call_expr (UNKNOWN_LOCATION,
223 gcc_assert (body != NULL_TREE);
224 /* Generate a function to call all the function of like
226 cgraph_build_static_cdtor (ctor_p ? 'I' : 'D', body, priority);
230 /* Comparison function for qsort. P1 and P2 are actually of type
231 "tree *" and point to static constructors. DECL_INIT_PRIORITY is
232 used to determine the sort order. */
235 compare_ctor (const void *p1, const void *p2)
242 f1 = *(const tree *)p1;
243 f2 = *(const tree *)p2;
244 priority1 = DECL_INIT_PRIORITY (f1);
245 priority2 = DECL_INIT_PRIORITY (f2);
247 if (priority1 < priority2)
249 else if (priority1 > priority2)
252 /* Ensure a stable sort. */
253 return (const tree *)p1 - (const tree *)p2;
256 /* Comparison function for qsort. P1 and P2 are actually of type
257 "tree *" and point to static destructors. DECL_FINI_PRIORITY is
258 used to determine the sort order. */
261 compare_dtor (const void *p1, const void *p2)
268 f1 = *(const tree *)p1;
269 f2 = *(const tree *)p2;
270 priority1 = DECL_FINI_PRIORITY (f1);
271 priority2 = DECL_FINI_PRIORITY (f2);
273 if (priority1 < priority2)
275 else if (priority1 > priority2)
278 /* Ensure a stable sort. */
279 return (const tree *)p1 - (const tree *)p2;
282 /* Generate functions to call static constructors and destructors
283 for targets that do not support .ctors/.dtors sections. These
284 functions have magic names which are detected by collect2. */
287 cgraph_build_cdtor_fns (void)
289 if (!VEC_empty (tree, static_ctors))
291 gcc_assert (!targetm.have_ctors_dtors);
292 qsort (VEC_address (tree, static_ctors),
293 VEC_length (tree, static_ctors),
296 build_cdtor (/*ctor_p=*/true,
297 VEC_address (tree, static_ctors),
298 VEC_length (tree, static_ctors));
299 VEC_truncate (tree, static_ctors, 0);
302 if (!VEC_empty (tree, static_dtors))
304 gcc_assert (!targetm.have_ctors_dtors);
305 qsort (VEC_address (tree, static_dtors),
306 VEC_length (tree, static_dtors),
309 build_cdtor (/*ctor_p=*/false,
310 VEC_address (tree, static_dtors),
311 VEC_length (tree, static_dtors));
312 VEC_truncate (tree, static_dtors, 0);
316 /* Determine if function DECL is needed. That is, visible to something
317 either outside this translation unit, something magic in the system
321 cgraph_decide_is_function_needed (struct cgraph_node *node, tree decl)
323 /* If the user told us it is used, then it must be so. */
324 if (node->local.externally_visible)
327 /* ??? If the assembler name is set by hand, it is possible to assemble
328 the name later after finalizing the function and the fact is noticed
329 in assemble_name then. This is arguably a bug. */
330 if (DECL_ASSEMBLER_NAME_SET_P (decl)
331 && TREE_SYMBOL_REFERENCED (DECL_ASSEMBLER_NAME (decl)))
334 /* With -fkeep-inline-functions we are keeping all inline functions except
335 for extern inline ones. */
336 if (flag_keep_inline_functions
337 && DECL_DECLARED_INLINE_P (decl)
338 && !DECL_EXTERNAL (decl)
339 && !lookup_attribute ("always_inline", DECL_ATTRIBUTES (decl)))
342 /* If we decided it was needed before, but at the time we didn't have
343 the body of the function available, then it's still needed. We have
344 to go back and re-check its dependencies now. */
348 /* Externally visible functions must be output. The exception is
349 COMDAT functions that must be output only when they are needed.
351 When not optimizing, also output the static functions. (see
352 PR24561), but don't do so for always_inline functions, functions
353 declared inline and nested functions. These was optimized out
354 in the original implementation and it is unclear whether we want
355 to change the behavior here. */
356 if (((TREE_PUBLIC (decl)
357 || (!optimize && !node->local.disregard_inline_limits
358 && !DECL_DECLARED_INLINE_P (decl)
360 && !flag_whole_program
363 && !DECL_COMDAT (decl) && !DECL_EXTERNAL (decl))
366 /* Constructors and destructors are reachable from the runtime by
368 if (DECL_STATIC_CONSTRUCTOR (decl) || DECL_STATIC_DESTRUCTOR (decl))
374 /* Process CGRAPH_NEW_FUNCTIONS and perform actions necessary to add these
375 functions into callgraph in a way so they look like ordinary reachable
376 functions inserted into callgraph already at construction time. */
379 cgraph_process_new_functions (void)
383 struct cgraph_node *node;
385 varpool_analyze_pending_decls ();
386 /* Note that this queue may grow as its being processed, as the new
387 functions may generate new ones. */
388 while (cgraph_new_nodes)
390 node = cgraph_new_nodes;
392 cgraph_new_nodes = cgraph_new_nodes->next_needed;
393 switch (cgraph_state)
395 case CGRAPH_STATE_CONSTRUCTION:
396 /* At construction time we just need to finalize function and move
397 it into reachable functions list. */
399 node->next_needed = NULL;
400 cgraph_finalize_function (fndecl, false);
401 cgraph_mark_reachable_node (node);
405 case CGRAPH_STATE_IPA:
406 case CGRAPH_STATE_IPA_SSA:
407 /* When IPA optimization already started, do all essential
408 transformations that has been already performed on the whole
409 cgraph but not on this function. */
411 gimple_register_cfg_hooks ();
413 cgraph_analyze_function (node);
414 push_cfun (DECL_STRUCT_FUNCTION (fndecl));
415 current_function_decl = fndecl;
416 compute_inline_parameters (node);
417 if ((cgraph_state == CGRAPH_STATE_IPA_SSA
418 && !gimple_in_ssa_p (DECL_STRUCT_FUNCTION (fndecl)))
419 /* When not optimizing, be sure we run early local passes anyway
422 execute_pass_list (pass_early_local_passes.pass.sub);
423 free_dominance_info (CDI_POST_DOMINATORS);
424 free_dominance_info (CDI_DOMINATORS);
426 current_function_decl = NULL;
429 case CGRAPH_STATE_EXPANSION:
430 /* Functions created during expansion shall be compiled
433 cgraph_expand_function (node);
440 cgraph_call_function_insertion_hooks (node);
441 varpool_analyze_pending_decls ();
446 /* As an GCC extension we allow redefinition of the function. The
447 semantics when both copies of bodies differ is not well defined.
448 We replace the old body with new body so in unit at a time mode
449 we always use new body, while in normal mode we may end up with
450 old body inlined into some functions and new body expanded and
453 ??? It may make more sense to use one body for inlining and other
454 body for expanding the function but this is difficult to do. */
457 cgraph_reset_node (struct cgraph_node *node)
459 /* If node->process is set, then we have already begun whole-unit analysis.
460 This is *not* testing for whether we've already emitted the function.
461 That case can be sort-of legitimately seen with real function redefinition
462 errors. I would argue that the front end should never present us with
463 such a case, but don't enforce that for now. */
464 gcc_assert (!node->process);
466 /* Reset our data structures so we can analyze the function again. */
467 memset (&node->local, 0, sizeof (node->local));
468 memset (&node->global, 0, sizeof (node->global));
469 memset (&node->rtl, 0, sizeof (node->rtl));
470 node->analyzed = false;
471 node->local.redefined_extern_inline = true;
472 node->local.finalized = false;
474 cgraph_node_remove_callees (node);
476 /* We may need to re-queue the node for assembling in case
477 we already proceeded it and ignored as not needed or got
478 a re-declaration in IMA mode. */
481 struct cgraph_node *n;
483 for (n = cgraph_nodes_queue; n; n = n->next_needed)
492 cgraph_lower_function (struct cgraph_node *node)
498 lower_nested_functions (node->decl);
499 gcc_assert (!node->nested);
501 tree_lowering_passes (node->decl);
502 node->lowered = true;
505 /* DECL has been parsed. Take it, queue it, compile it at the whim of the
506 logic in effect. If NESTED is true, then our caller cannot stand to have
507 the garbage collector run at the moment. We would need to either create
508 a new GC context, or just not compile right now. */
511 cgraph_finalize_function (tree decl, bool nested)
513 struct cgraph_node *node = cgraph_node (decl);
515 if (node->local.finalized)
516 cgraph_reset_node (node);
518 node->pid = cgraph_max_pid ++;
519 notice_global_symbol (decl);
520 node->local.finalized = true;
521 node->lowered = DECL_STRUCT_FUNCTION (decl)->cfg != NULL;
522 node->finalized_by_frontend = true;
523 record_cdtor_fn (node->decl);
525 if (cgraph_decide_is_function_needed (node, decl))
526 cgraph_mark_needed_node (node);
528 /* Since we reclaim unreachable nodes at the end of every language
529 level unit, we need to be conservative about possible entry points
531 if ((TREE_PUBLIC (decl) && !DECL_COMDAT (decl) && !DECL_EXTERNAL (decl)))
532 cgraph_mark_reachable_node (node);
534 /* If we've not yet emitted decl, tell the debug info about it. */
535 if (!TREE_ASM_WRITTEN (decl))
536 (*debug_hooks->deferred_inline_function) (decl);
538 /* Possibly warn about unused parameters. */
539 if (warn_unused_parameter)
540 do_warn_unused_parameter (decl);
546 /* C99 extern inline keywords allow changing of declaration after function
547 has been finalized. We need to re-decide if we want to mark the function as
551 cgraph_mark_if_needed (tree decl)
553 struct cgraph_node *node = cgraph_node (decl);
554 if (node->local.finalized && cgraph_decide_is_function_needed (node, decl))
555 cgraph_mark_needed_node (node);
558 /* Return TRUE if NODE2 is equivalent to NODE or its clone. */
560 clone_of_p (struct cgraph_node *node, struct cgraph_node *node2)
562 while (node != node2 && node2)
563 node2 = node2->clone_of;
564 return node2 != NULL;
567 /* Verify cgraph nodes of given cgraph node. */
569 verify_cgraph_node (struct cgraph_node *node)
571 struct cgraph_edge *e;
572 struct function *this_cfun = DECL_STRUCT_FUNCTION (node->decl);
573 struct function *saved_cfun = cfun;
574 basic_block this_block;
575 gimple_stmt_iterator gsi;
576 bool error_found = false;
578 if (errorcount || sorrycount)
581 timevar_push (TV_CGRAPH_VERIFY);
582 /* debug_generic_stmt needs correct cfun */
583 set_cfun (this_cfun);
584 for (e = node->callees; e; e = e->next_callee)
587 error ("aux field set for edge %s->%s",
588 identifier_to_locale (cgraph_node_name (e->caller)),
589 identifier_to_locale (cgraph_node_name (e->callee)));
594 error ("Execution count is negative");
597 if (node->global.inlined_to && node->local.externally_visible)
599 error ("Externally visible inline clone");
602 if (node->global.inlined_to && node->address_taken)
604 error ("Inline clone with address taken");
607 if (node->global.inlined_to && node->needed)
609 error ("Inline clone is needed");
612 for (e = node->indirect_calls; e; e = e->next_callee)
616 error ("aux field set for indirect edge from %s",
617 identifier_to_locale (cgraph_node_name (e->caller)));
620 if (!e->indirect_unknown_callee
621 || !e->indirect_info)
623 error ("An indirect edge from %s is not marked as indirect or has "
624 "associated indirect_info, the corresponding statement is: ",
625 identifier_to_locale (cgraph_node_name (e->caller)));
626 debug_gimple_stmt (e->call_stmt);
630 for (e = node->callers; e; e = e->next_caller)
634 error ("caller edge count is negative");
637 if (e->frequency < 0)
639 error ("caller edge frequency is negative");
642 if (e->frequency > CGRAPH_FREQ_MAX)
644 error ("caller edge frequency is too large");
647 if (gimple_has_body_p (e->caller->decl)
648 && !e->caller->global.inlined_to
650 != compute_call_stmt_bb_frequency (e->caller->decl,
651 gimple_bb (e->call_stmt))))
653 error ("caller edge frequency %i does not match BB freqency %i",
655 compute_call_stmt_bb_frequency (e->caller->decl,
656 gimple_bb (e->call_stmt)));
659 if (!e->inline_failed)
661 if (node->global.inlined_to
662 != (e->caller->global.inlined_to
663 ? e->caller->global.inlined_to : e->caller))
665 error ("inlined_to pointer is wrong");
668 if (node->callers->next_caller)
670 error ("multiple inline callers");
675 if (node->global.inlined_to)
677 error ("inlined_to pointer set for noninline callers");
681 if (!node->callers && node->global.inlined_to)
683 error ("inlined_to pointer is set but no predecessors found");
686 if (node->global.inlined_to == node)
688 error ("inlined_to pointer refers to itself");
692 if (!cgraph_node (node->decl))
694 error ("node not found in cgraph_hash");
700 struct cgraph_node *n;
701 for (n = node->clone_of->clones; n; n = n->next_sibling_clone)
706 error ("node has wrong clone_of");
712 struct cgraph_node *n;
713 for (n = node->clones; n; n = n->next_sibling_clone)
714 if (n->clone_of != node)
718 error ("node has wrong clone list");
722 if ((node->prev_sibling_clone || node->next_sibling_clone) && !node->clone_of)
724 error ("node is in clone list but it is not clone");
727 if (!node->prev_sibling_clone && node->clone_of && node->clone_of->clones != node)
729 error ("node has wrong prev_clone pointer");
732 if (node->prev_sibling_clone && node->prev_sibling_clone->next_sibling_clone != node)
734 error ("double linked list of clones corrupted");
737 if (node->same_comdat_group)
739 struct cgraph_node *n = node->same_comdat_group;
741 if (!DECL_ONE_ONLY (node->decl))
743 error ("non-DECL_ONE_ONLY node in a same_comdat_group list");
748 error ("node is alone in a comdat group");
753 if (!n->same_comdat_group)
755 error ("same_comdat_group is not a circular list");
759 n = n->same_comdat_group;
764 if (node->analyzed && gimple_has_body_p (node->decl)
765 && !TREE_ASM_WRITTEN (node->decl)
766 && (!DECL_EXTERNAL (node->decl) || node->global.inlined_to)
771 /* The nodes we're interested in are never shared, so walk
772 the tree ignoring duplicates. */
773 struct pointer_set_t *visited_nodes = pointer_set_create ();
774 /* Reach the trees by walking over the CFG, and note the
775 enclosing basic-blocks in the call edges. */
776 FOR_EACH_BB_FN (this_block, this_cfun)
777 for (gsi = gsi_start_bb (this_block);
781 gimple stmt = gsi_stmt (gsi);
782 if (is_gimple_call (stmt))
784 struct cgraph_edge *e = cgraph_edge (node, stmt);
785 tree decl = gimple_call_fndecl (stmt);
790 error ("shared call_stmt:");
791 debug_gimple_stmt (stmt);
794 if (!e->indirect_unknown_callee)
796 if (e->callee->same_body_alias)
798 error ("edge points to same body alias:");
799 debug_tree (e->callee->decl);
802 else if (!node->global.inlined_to
803 && !e->callee->global.inlined_to
805 && !clone_of_p (cgraph_node (decl),
808 error ("edge points to wrong declaration:");
809 debug_tree (e->callee->decl);
810 fprintf (stderr," Instead of:");
817 error ("an indirect edge with unknown callee "
818 "corresponding to a call_stmt with "
819 "a known declaration:");
821 debug_gimple_stmt (e->call_stmt);
827 error ("missing callgraph edge for call stmt:");
828 debug_gimple_stmt (stmt);
833 pointer_set_destroy (visited_nodes);
836 /* No CFG available?! */
839 for (e = node->callees; e; e = e->next_callee)
843 error ("edge %s->%s has no corresponding call_stmt",
844 identifier_to_locale (cgraph_node_name (e->caller)),
845 identifier_to_locale (cgraph_node_name (e->callee)));
846 debug_gimple_stmt (e->call_stmt);
851 for (e = node->indirect_calls; e; e = e->next_callee)
855 error ("an indirect edge from %s has no corresponding call_stmt",
856 identifier_to_locale (cgraph_node_name (e->caller)));
857 debug_gimple_stmt (e->call_stmt);
865 dump_cgraph_node (stderr, node);
866 internal_error ("verify_cgraph_node failed");
868 set_cfun (saved_cfun);
869 timevar_pop (TV_CGRAPH_VERIFY);
872 /* Verify whole cgraph structure. */
876 struct cgraph_node *node;
878 if (sorrycount || errorcount)
881 for (node = cgraph_nodes; node; node = node->next)
882 verify_cgraph_node (node);
885 /* Output all asm statements we have stored up to be output. */
888 cgraph_output_pending_asms (void)
890 struct cgraph_asm_node *can;
892 if (errorcount || sorrycount)
895 for (can = cgraph_asm_nodes; can; can = can->next)
896 assemble_asm (can->asm_str);
897 cgraph_asm_nodes = NULL;
900 /* Analyze the function scheduled to be output. */
902 cgraph_analyze_function (struct cgraph_node *node)
904 tree save = current_function_decl;
905 tree decl = node->decl;
907 current_function_decl = decl;
908 push_cfun (DECL_STRUCT_FUNCTION (decl));
910 assign_assembler_name_if_neeeded (node->decl);
912 /* Make sure to gimplify bodies only once. During analyzing a
913 function we lower it, which will require gimplified nested
914 functions, so we can end up here with an already gimplified
916 if (!gimple_body (decl))
917 gimplify_function_tree (decl);
918 dump_function (TDI_generic, decl);
920 cgraph_lower_function (node);
921 node->analyzed = true;
924 current_function_decl = save;
927 /* Look for externally_visible and used attributes and mark cgraph nodes
930 We cannot mark the nodes at the point the attributes are processed (in
931 handle_*_attribute) because the copy of the declarations available at that
932 point may not be canonical. For example, in:
935 void f() __attribute__((used));
937 the declaration we see in handle_used_attribute will be the second
938 declaration -- but the front end will subsequently merge that declaration
939 with the original declaration and discard the second declaration.
941 Furthermore, we can't mark these nodes in cgraph_finalize_function because:
944 void f() __attribute__((externally_visible));
948 So, we walk the nodes at the end of the translation unit, applying the
949 attributes at that point. */
952 process_function_and_variable_attributes (struct cgraph_node *first,
953 struct varpool_node *first_var)
955 struct cgraph_node *node;
956 struct varpool_node *vnode;
958 for (node = cgraph_nodes; node != first; node = node->next)
960 tree decl = node->decl;
961 if (DECL_PRESERVE_P (decl))
962 cgraph_mark_needed_node (node);
963 if (lookup_attribute ("externally_visible", DECL_ATTRIBUTES (decl)))
965 if (! TREE_PUBLIC (node->decl))
966 warning_at (DECL_SOURCE_LOCATION (node->decl), OPT_Wattributes,
967 "%<externally_visible%>"
968 " attribute have effect only on public objects");
969 else if (node->local.finalized)
970 cgraph_mark_needed_node (node);
973 for (vnode = varpool_nodes; vnode != first_var; vnode = vnode->next)
975 tree decl = vnode->decl;
976 if (DECL_PRESERVE_P (decl))
978 vnode->force_output = true;
979 if (vnode->finalized)
980 varpool_mark_needed_node (vnode);
982 if (lookup_attribute ("externally_visible", DECL_ATTRIBUTES (decl)))
984 if (! TREE_PUBLIC (vnode->decl))
985 warning_at (DECL_SOURCE_LOCATION (vnode->decl), OPT_Wattributes,
986 "%<externally_visible%>"
987 " attribute have effect only on public objects");
988 else if (vnode->finalized)
989 varpool_mark_needed_node (vnode);
994 /* Process CGRAPH_NODES_NEEDED queue, analyze each function (and transitively
995 each reachable functions) and build cgraph.
996 The function can be called multiple times after inserting new nodes
997 into beginning of queue. Just the new part of queue is re-scanned then. */
1000 cgraph_analyze_functions (void)
1002 /* Keep track of already processed nodes when called multiple times for
1003 intermodule optimization. */
1004 static struct cgraph_node *first_analyzed;
1005 struct cgraph_node *first_processed = first_analyzed;
1006 static struct varpool_node *first_analyzed_var;
1007 struct cgraph_node *node, *next;
1009 process_function_and_variable_attributes (first_processed,
1010 first_analyzed_var);
1011 first_processed = cgraph_nodes;
1012 first_analyzed_var = varpool_nodes;
1013 varpool_analyze_pending_decls ();
1014 if (cgraph_dump_file)
1016 fprintf (cgraph_dump_file, "Initial entry points:");
1017 for (node = cgraph_nodes; node != first_analyzed; node = node->next)
1019 fprintf (cgraph_dump_file, " %s", cgraph_node_name (node));
1020 fprintf (cgraph_dump_file, "\n");
1022 cgraph_process_new_functions ();
1024 /* Propagate reachability flag and lower representation of all reachable
1025 functions. In the future, lowering will introduce new functions and
1026 new entry points on the way (by template instantiation and virtual
1027 method table generation for instance). */
1028 while (cgraph_nodes_queue)
1030 struct cgraph_edge *edge;
1031 tree decl = cgraph_nodes_queue->decl;
1033 node = cgraph_nodes_queue;
1034 cgraph_nodes_queue = cgraph_nodes_queue->next_needed;
1035 node->next_needed = NULL;
1037 /* ??? It is possible to create extern inline function and later using
1038 weak alias attribute to kill its body. See
1039 gcc.c-torture/compile/20011119-1.c */
1040 if (!DECL_STRUCT_FUNCTION (decl))
1042 cgraph_reset_node (node);
1046 if (!node->analyzed)
1047 cgraph_analyze_function (node);
1049 for (edge = node->callees; edge; edge = edge->next_callee)
1050 if (!edge->callee->reachable)
1051 cgraph_mark_reachable_node (edge->callee);
1053 if (node->same_comdat_group)
1055 for (next = node->same_comdat_group;
1057 next = next->same_comdat_group)
1058 cgraph_mark_reachable_node (next);
1061 /* If decl is a clone of an abstract function, mark that abstract
1062 function so that we don't release its body. The DECL_INITIAL() of that
1063 abstract function declaration will be later needed to output debug info. */
1064 if (DECL_ABSTRACT_ORIGIN (decl))
1066 struct cgraph_node *origin_node = cgraph_node (DECL_ABSTRACT_ORIGIN (decl));
1067 origin_node->abstract_and_needed = true;
1070 /* We finalize local static variables during constructing callgraph
1071 edges. Process their attributes too. */
1072 process_function_and_variable_attributes (first_processed,
1073 first_analyzed_var);
1074 first_processed = cgraph_nodes;
1075 first_analyzed_var = varpool_nodes;
1076 varpool_analyze_pending_decls ();
1077 cgraph_process_new_functions ();
1080 /* Collect entry points to the unit. */
1081 if (cgraph_dump_file)
1083 fprintf (cgraph_dump_file, "Unit entry points:");
1084 for (node = cgraph_nodes; node != first_analyzed; node = node->next)
1086 fprintf (cgraph_dump_file, " %s", cgraph_node_name (node));
1087 fprintf (cgraph_dump_file, "\n\nInitial ");
1088 dump_cgraph (cgraph_dump_file);
1091 if (cgraph_dump_file)
1092 fprintf (cgraph_dump_file, "\nReclaiming functions:");
1094 for (node = cgraph_nodes; node != first_analyzed; node = next)
1096 tree decl = node->decl;
1099 if (node->local.finalized && !gimple_has_body_p (decl))
1100 cgraph_reset_node (node);
1102 if (!node->reachable && gimple_has_body_p (decl))
1104 if (cgraph_dump_file)
1105 fprintf (cgraph_dump_file, " %s", cgraph_node_name (node));
1106 cgraph_remove_node (node);
1110 node->next_needed = NULL;
1111 gcc_assert (!node->local.finalized || gimple_has_body_p (decl));
1112 gcc_assert (node->analyzed == node->local.finalized);
1114 if (cgraph_dump_file)
1116 fprintf (cgraph_dump_file, "\n\nReclaimed ");
1117 dump_cgraph (cgraph_dump_file);
1119 first_analyzed = cgraph_nodes;
1124 /* Analyze the whole compilation unit once it is parsed completely. */
1127 cgraph_finalize_compilation_unit (void)
1129 timevar_push (TV_CGRAPH);
1131 /* Do not skip analyzing the functions if there were errors, we
1132 miss diagnostics for following functions otherwise. */
1134 /* Emit size functions we didn't inline. */
1135 finalize_size_functions ();
1137 /* Call functions declared with the "constructor" or "destructor"
1139 cgraph_build_cdtor_fns ();
1141 /* Mark alias targets necessary and emit diagnostics. */
1142 finish_aliases_1 ();
1146 fprintf (stderr, "\nAnalyzing compilation unit\n");
1150 /* Gimplify and lower all functions, compute reachability and
1151 remove unreachable nodes. */
1152 cgraph_analyze_functions ();
1154 /* Mark alias targets necessary and emit diagnostics. */
1155 finish_aliases_1 ();
1157 /* Gimplify and lower thunks. */
1158 cgraph_analyze_functions ();
1160 /* Finally drive the pass manager. */
1163 timevar_pop (TV_CGRAPH);
1167 /* Figure out what functions we want to assemble. */
1170 cgraph_mark_functions_to_output (void)
1172 struct cgraph_node *node;
1173 #ifdef ENABLE_CHECKING
1174 bool check_same_comdat_groups = false;
1176 for (node = cgraph_nodes; node; node = node->next)
1177 gcc_assert (!node->process);
1180 for (node = cgraph_nodes; node; node = node->next)
1182 tree decl = node->decl;
1183 struct cgraph_edge *e;
1185 gcc_assert (!node->process || node->same_comdat_group);
1189 for (e = node->callers; e; e = e->next_caller)
1190 if (e->inline_failed)
1193 /* We need to output all local functions that are used and not
1194 always inlined, as well as those that are reachable from
1195 outside the current compilation unit. */
1197 && !node->global.inlined_to
1198 && (node->needed || node->reachable_from_other_partition
1199 || node->address_taken
1200 || (e && node->reachable))
1201 && !TREE_ASM_WRITTEN (decl)
1202 && !DECL_EXTERNAL (decl))
1205 if (node->same_comdat_group)
1207 struct cgraph_node *next;
1208 for (next = node->same_comdat_group;
1210 next = next->same_comdat_group)
1214 else if (node->same_comdat_group)
1216 #ifdef ENABLE_CHECKING
1217 check_same_comdat_groups = true;
1222 /* We should've reclaimed all functions that are not needed. */
1223 #ifdef ENABLE_CHECKING
1224 if (!node->global.inlined_to
1225 && gimple_has_body_p (decl)
1226 /* FIXME: in ltrans unit when offline copy is outside partition but inline copies
1227 are inside partition, we can end up not removing the body since we no longer
1228 have analyzed node pointing to it. */
1229 && !node->in_other_partition
1230 && !DECL_EXTERNAL (decl))
1232 dump_cgraph_node (stderr, node);
1233 internal_error ("failed to reclaim unneeded function");
1236 gcc_assert (node->global.inlined_to
1237 || !gimple_has_body_p (decl)
1238 || node->in_other_partition
1239 || DECL_EXTERNAL (decl));
1244 #ifdef ENABLE_CHECKING
1245 if (check_same_comdat_groups)
1246 for (node = cgraph_nodes; node; node = node->next)
1247 if (node->same_comdat_group && !node->process)
1249 tree decl = node->decl;
1250 if (!node->global.inlined_to
1251 && gimple_has_body_p (decl)
1252 /* FIXME: in ltrans unit when offline copy is outside partition but inline copies
1253 are inside partition, we can end up not removing the body since we no longer
1254 have analyzed node pointing to it. */
1255 && !node->in_other_partition
1256 && !DECL_EXTERNAL (decl))
1258 dump_cgraph_node (stderr, node);
1259 internal_error ("failed to reclaim unneeded function");
1265 /* DECL is FUNCTION_DECL. Initialize datastructures so DECL is a function
1266 in lowered gimple form.
1268 Set current_function_decl and cfun to newly constructed empty function body.
1269 return basic block in the function body. */
1272 init_lowered_empty_function (tree decl)
1276 current_function_decl = decl;
1277 allocate_struct_function (decl, false);
1278 gimple_register_cfg_hooks ();
1279 init_empty_tree_cfg ();
1280 init_tree_ssa (cfun);
1281 init_ssa_operands ();
1282 cfun->gimple_df->in_ssa_p = true;
1283 DECL_INITIAL (decl) = make_node (BLOCK);
1285 DECL_SAVED_TREE (decl) = error_mark_node;
1286 cfun->curr_properties |=
1287 (PROP_gimple_lcf | PROP_gimple_leh | PROP_cfg | PROP_referenced_vars |
1290 /* Create BB for body of the function and connect it properly. */
1291 bb = create_basic_block (NULL, (void *) 0, ENTRY_BLOCK_PTR);
1292 make_edge (ENTRY_BLOCK_PTR, bb, 0);
1293 make_edge (bb, EXIT_BLOCK_PTR, 0);
1298 /* Adjust PTR by the constant FIXED_OFFSET, and by the vtable
1299 offset indicated by VIRTUAL_OFFSET, if that is
1300 non-null. THIS_ADJUSTING is nonzero for a this adjusting thunk and
1301 zero for a result adjusting thunk. */
1304 thunk_adjust (gimple_stmt_iterator * bsi,
1305 tree ptr, bool this_adjusting,
1306 HOST_WIDE_INT fixed_offset, tree virtual_offset)
1312 && fixed_offset != 0)
1314 stmt = gimple_build_assign (ptr,
1315 fold_build2_loc (input_location,
1317 TREE_TYPE (ptr), ptr,
1318 size_int (fixed_offset)));
1319 gsi_insert_after (bsi, stmt, GSI_NEW_STMT);
1322 /* If there's a virtual offset, look up that value in the vtable and
1323 adjust the pointer again. */
1331 if (!vtable_entry_type)
1333 tree vfunc_type = make_node (FUNCTION_TYPE);
1334 TREE_TYPE (vfunc_type) = integer_type_node;
1335 TYPE_ARG_TYPES (vfunc_type) = NULL_TREE;
1336 layout_type (vfunc_type);
1338 vtable_entry_type = build_pointer_type (vfunc_type);
1342 create_tmp_var (build_pointer_type
1343 (build_pointer_type (vtable_entry_type)), "vptr");
1345 /* The vptr is always at offset zero in the object. */
1346 stmt = gimple_build_assign (vtabletmp,
1347 build1 (NOP_EXPR, TREE_TYPE (vtabletmp),
1349 gsi_insert_after (bsi, stmt, GSI_NEW_STMT);
1350 mark_symbols_for_renaming (stmt);
1351 find_referenced_vars_in (stmt);
1353 /* Form the vtable address. */
1354 vtabletmp2 = create_tmp_var (TREE_TYPE (TREE_TYPE (vtabletmp)),
1356 stmt = gimple_build_assign (vtabletmp2,
1357 build1 (INDIRECT_REF,
1358 TREE_TYPE (vtabletmp2), vtabletmp));
1359 gsi_insert_after (bsi, stmt, GSI_NEW_STMT);
1360 mark_symbols_for_renaming (stmt);
1361 find_referenced_vars_in (stmt);
1363 /* Find the entry with the vcall offset. */
1364 stmt = gimple_build_assign (vtabletmp2,
1365 fold_build2_loc (input_location,
1367 TREE_TYPE (vtabletmp2),
1369 fold_convert (sizetype,
1371 gsi_insert_after (bsi, stmt, GSI_NEW_STMT);
1373 /* Get the offset itself. */
1374 vtabletmp3 = create_tmp_var (TREE_TYPE (TREE_TYPE (vtabletmp2)),
1376 stmt = gimple_build_assign (vtabletmp3,
1377 build1 (INDIRECT_REF,
1378 TREE_TYPE (vtabletmp3),
1380 gsi_insert_after (bsi, stmt, GSI_NEW_STMT);
1381 mark_symbols_for_renaming (stmt);
1382 find_referenced_vars_in (stmt);
1384 /* Cast to sizetype. */
1385 offsettmp = create_tmp_var (sizetype, "offset");
1386 stmt = gimple_build_assign (offsettmp, fold_convert (sizetype, vtabletmp3));
1387 gsi_insert_after (bsi, stmt, GSI_NEW_STMT);
1388 mark_symbols_for_renaming (stmt);
1389 find_referenced_vars_in (stmt);
1391 /* Adjust the `this' pointer. */
1392 ptr = fold_build2_loc (input_location,
1393 POINTER_PLUS_EXPR, TREE_TYPE (ptr), ptr,
1398 && fixed_offset != 0)
1399 /* Adjust the pointer by the constant. */
1403 if (TREE_CODE (ptr) == VAR_DECL)
1407 ptrtmp = create_tmp_var (TREE_TYPE (ptr), "ptr");
1408 stmt = gimple_build_assign (ptrtmp, ptr);
1409 gsi_insert_after (bsi, stmt, GSI_NEW_STMT);
1410 mark_symbols_for_renaming (stmt);
1411 find_referenced_vars_in (stmt);
1413 ptr = fold_build2_loc (input_location,
1414 POINTER_PLUS_EXPR, TREE_TYPE (ptrtmp), ptrtmp,
1415 size_int (fixed_offset));
1418 /* Emit the statement and gimplify the adjustment expression. */
1419 ret = create_tmp_var (TREE_TYPE (ptr), "adjusted_this");
1420 stmt = gimple_build_assign (ret, ptr);
1421 mark_symbols_for_renaming (stmt);
1422 find_referenced_vars_in (stmt);
1423 gsi_insert_after (bsi, stmt, GSI_NEW_STMT);
1428 /* Produce assembler for thunk NODE. */
1431 assemble_thunk (struct cgraph_node *node)
1433 bool this_adjusting = node->thunk.this_adjusting;
1434 HOST_WIDE_INT fixed_offset = node->thunk.fixed_offset;
1435 HOST_WIDE_INT virtual_value = node->thunk.virtual_value;
1436 tree virtual_offset = NULL;
1437 tree alias = node->thunk.alias;
1438 tree thunk_fndecl = node->decl;
1439 tree a = DECL_ARGUMENTS (thunk_fndecl);
1441 current_function_decl = thunk_fndecl;
1444 && targetm.asm_out.can_output_mi_thunk (thunk_fndecl, fixed_offset,
1445 virtual_value, alias))
1450 DECL_RESULT (thunk_fndecl)
1451 = build_decl (DECL_SOURCE_LOCATION (thunk_fndecl),
1452 RESULT_DECL, 0, integer_type_node);
1453 fnname = IDENTIFIER_POINTER (DECL_ASSEMBLER_NAME (thunk_fndecl));
1455 /* The back end expects DECL_INITIAL to contain a BLOCK, so we
1457 fn_block = make_node (BLOCK);
1458 BLOCK_VARS (fn_block) = a;
1459 DECL_INITIAL (thunk_fndecl) = fn_block;
1460 init_function_start (thunk_fndecl);
1462 assemble_start_function (thunk_fndecl, fnname);
1464 targetm.asm_out.output_mi_thunk (asm_out_file, thunk_fndecl,
1465 fixed_offset, virtual_value, alias);
1467 assemble_end_function (thunk_fndecl, fnname);
1468 init_insn_lengths ();
1469 free_after_compilation (cfun);
1471 TREE_ASM_WRITTEN (thunk_fndecl) = 1;
1476 basic_block bb, then_bb, else_bb, return_bb;
1477 gimple_stmt_iterator bsi;
1483 VEC(tree, heap) *vargs;
1488 DECL_IGNORED_P (thunk_fndecl) = 1;
1489 bitmap_obstack_initialize (NULL);
1491 if (node->thunk.virtual_offset_p)
1492 virtual_offset = size_int (virtual_value);
1494 /* Build the return declaration for the function. */
1495 restype = TREE_TYPE (TREE_TYPE (thunk_fndecl));
1496 if (DECL_RESULT (thunk_fndecl) == NULL_TREE)
1498 resdecl = build_decl (input_location, RESULT_DECL, 0, restype);
1499 DECL_ARTIFICIAL (resdecl) = 1;
1500 DECL_IGNORED_P (resdecl) = 1;
1501 DECL_RESULT (thunk_fndecl) = resdecl;
1504 resdecl = DECL_RESULT (thunk_fndecl);
1506 bb = then_bb = else_bb = return_bb = init_lowered_empty_function (thunk_fndecl);
1508 bsi = gsi_start_bb (bb);
1510 /* Build call to the function being thunked. */
1511 if (!VOID_TYPE_P (restype))
1513 if (!is_gimple_reg_type (restype))
1516 cfun->local_decls = tree_cons (NULL_TREE, restmp, cfun->local_decls);
1517 BLOCK_VARS (DECL_INITIAL (current_function_decl)) = restmp;
1520 restmp = create_tmp_var_raw (restype, "retval");
1523 for (arg = a; arg; arg = TREE_CHAIN (arg))
1525 vargs = VEC_alloc (tree, heap, nargs);
1527 VEC_quick_push (tree, vargs,
1532 VEC_quick_push (tree, vargs, a);
1533 for (i = 1, arg = TREE_CHAIN (a); i < nargs; i++, arg = TREE_CHAIN (arg))
1534 VEC_quick_push (tree, vargs, arg);
1535 call = gimple_build_call_vec (build_fold_addr_expr_loc (0, alias), vargs);
1536 VEC_free (tree, heap, vargs);
1537 gimple_call_set_cannot_inline (call, true);
1538 gimple_call_set_from_thunk (call, true);
1540 gimple_call_set_lhs (call, restmp);
1541 gsi_insert_after (&bsi, call, GSI_NEW_STMT);
1542 mark_symbols_for_renaming (call);
1543 find_referenced_vars_in (call);
1546 if (restmp && !this_adjusting)
1548 tree true_label = NULL_TREE;
1550 if (TREE_CODE (TREE_TYPE (restmp)) == POINTER_TYPE)
1553 /* If the return type is a pointer, we need to
1554 protect against NULL. We know there will be an
1555 adjustment, because that's why we're emitting a
1557 then_bb = create_basic_block (NULL, (void *) 0, bb);
1558 return_bb = create_basic_block (NULL, (void *) 0, then_bb);
1559 else_bb = create_basic_block (NULL, (void *) 0, else_bb);
1560 remove_edge (single_succ_edge (bb));
1561 true_label = gimple_block_label (then_bb);
1562 stmt = gimple_build_cond (NE_EXPR, restmp,
1563 fold_convert (TREE_TYPE (restmp),
1565 NULL_TREE, NULL_TREE);
1566 gsi_insert_after (&bsi, stmt, GSI_NEW_STMT);
1567 make_edge (bb, then_bb, EDGE_TRUE_VALUE);
1568 make_edge (bb, else_bb, EDGE_FALSE_VALUE);
1569 make_edge (return_bb, EXIT_BLOCK_PTR, 0);
1570 make_edge (then_bb, return_bb, EDGE_FALLTHRU);
1571 make_edge (else_bb, return_bb, EDGE_FALLTHRU);
1572 bsi = gsi_last_bb (then_bb);
1575 restmp = thunk_adjust (&bsi, restmp, /*this_adjusting=*/0,
1576 fixed_offset, virtual_offset);
1580 bsi = gsi_last_bb (else_bb);
1581 stmt = gimple_build_assign (restmp, fold_convert (TREE_TYPE (restmp),
1582 integer_zero_node));
1583 gsi_insert_after (&bsi, stmt, GSI_NEW_STMT);
1584 bsi = gsi_last_bb (return_bb);
1588 gimple_call_set_tail (call, true);
1590 /* Build return value. */
1591 ret = gimple_build_return (restmp);
1592 gsi_insert_after (&bsi, ret, GSI_NEW_STMT);
1594 delete_unreachable_blocks ();
1595 update_ssa (TODO_update_ssa);
1597 cgraph_remove_same_body_alias (node);
1598 /* Since we want to emit the thunk, we explicitly mark its name as
1600 cgraph_add_new_function (thunk_fndecl, true);
1601 bitmap_obstack_release (NULL);
1603 current_function_decl = NULL;
1606 /* Expand function specified by NODE. */
1609 cgraph_expand_function (struct cgraph_node *node)
1611 tree decl = node->decl;
1613 /* We ought to not compile any inline clones. */
1614 gcc_assert (!node->global.inlined_to);
1616 announce_function (decl);
1619 gcc_assert (node->lowered);
1621 /* Generate RTL for the body of DECL. */
1622 tree_rest_of_compilation (decl);
1624 /* Make sure that BE didn't give up on compiling. */
1625 gcc_assert (TREE_ASM_WRITTEN (decl));
1626 current_function_decl = NULL;
1627 if (node->same_body)
1629 struct cgraph_node *alias, *next;
1630 bool saved_alias = node->alias;
1631 for (alias = node->same_body;
1632 alias && alias->next; alias = alias->next)
1634 /* Walk aliases in the order they were created; it is possible that
1635 thunks reffers to the aliases made earlier. */
1636 for (; alias; alias = next)
1638 next = alias->previous;
1639 if (!alias->thunk.thunk_p)
1640 assemble_alias (alias->decl,
1641 DECL_ASSEMBLER_NAME (alias->thunk.alias));
1643 assemble_thunk (alias);
1645 node->alias = saved_alias;
1647 gcc_assert (!cgraph_preserve_function_body_p (decl));
1648 cgraph_release_function_body (node);
1649 /* Eliminate all call edges. This is important so the GIMPLE_CALL no longer
1650 points to the dead function body. */
1651 cgraph_node_remove_callees (node);
1653 cgraph_function_flags_ready = true;
1656 /* Return true when CALLER_DECL should be inlined into CALLEE_DECL. */
1659 cgraph_inline_p (struct cgraph_edge *e, cgraph_inline_failed_t *reason)
1661 *reason = e->inline_failed;
1662 return !e->inline_failed;
1667 /* Expand all functions that must be output.
1669 Attempt to topologically sort the nodes so function is output when
1670 all called functions are already assembled to allow data to be
1671 propagated across the callgraph. Use a stack to get smaller distance
1672 between a function and its callees (later we may choose to use a more
1673 sophisticated algorithm for function reordering; we will likely want
1674 to use subsections to make the output functions appear in top-down
1678 cgraph_expand_all_functions (void)
1680 struct cgraph_node *node;
1681 struct cgraph_node **order = XCNEWVEC (struct cgraph_node *, cgraph_n_nodes);
1682 int order_pos, new_order_pos = 0;
1685 order_pos = cgraph_postorder (order);
1686 gcc_assert (order_pos == cgraph_n_nodes);
1688 /* Garbage collector may remove inline clones we eliminate during
1689 optimization. So we must be sure to not reference them. */
1690 for (i = 0; i < order_pos; i++)
1691 if (order[i]->process)
1692 order[new_order_pos++] = order[i];
1694 for (i = new_order_pos - 1; i >= 0; i--)
1699 gcc_assert (node->reachable);
1701 cgraph_expand_function (node);
1704 cgraph_process_new_functions ();
1710 /* This is used to sort the node types by the cgraph order number. */
1712 enum cgraph_order_sort_kind
1714 ORDER_UNDEFINED = 0,
1720 struct cgraph_order_sort
1722 enum cgraph_order_sort_kind kind;
1725 struct cgraph_node *f;
1726 struct varpool_node *v;
1727 struct cgraph_asm_node *a;
1731 /* Output all functions, variables, and asm statements in the order
1732 according to their order fields, which is the order in which they
1733 appeared in the file. This implements -fno-toplevel-reorder. In
1734 this mode we may output functions and variables which don't really
1735 need to be output. */
1738 cgraph_output_in_order (void)
1741 struct cgraph_order_sort *nodes;
1743 struct cgraph_node *pf;
1744 struct varpool_node *pv;
1745 struct cgraph_asm_node *pa;
1748 nodes = XCNEWVEC (struct cgraph_order_sort, max);
1750 varpool_analyze_pending_decls ();
1752 for (pf = cgraph_nodes; pf; pf = pf->next)
1757 gcc_assert (nodes[i].kind == ORDER_UNDEFINED);
1758 nodes[i].kind = ORDER_FUNCTION;
1763 for (pv = varpool_nodes_queue; pv; pv = pv->next_needed)
1766 gcc_assert (nodes[i].kind == ORDER_UNDEFINED);
1767 nodes[i].kind = ORDER_VAR;
1771 for (pa = cgraph_asm_nodes; pa; pa = pa->next)
1774 gcc_assert (nodes[i].kind == ORDER_UNDEFINED);
1775 nodes[i].kind = ORDER_ASM;
1779 /* In toplevel reorder mode we output all statics; mark them as needed. */
1780 for (i = 0; i < max; ++i)
1782 if (nodes[i].kind == ORDER_VAR)
1784 varpool_mark_needed_node (nodes[i].u.v);
1787 varpool_empty_needed_queue ();
1789 for (i = 0; i < max; ++i)
1791 switch (nodes[i].kind)
1793 case ORDER_FUNCTION:
1794 nodes[i].u.f->process = 0;
1795 cgraph_expand_function (nodes[i].u.f);
1799 varpool_assemble_decl (nodes[i].u.v);
1803 assemble_asm (nodes[i].u.a->asm_str);
1806 case ORDER_UNDEFINED:
1814 cgraph_asm_nodes = NULL;
1818 /* Return true when function body of DECL still needs to be kept around
1819 for later re-use. */
1821 cgraph_preserve_function_body_p (tree decl)
1823 struct cgraph_node *node;
1825 gcc_assert (cgraph_global_info_ready);
1826 /* Look if there is any clone around. */
1827 node = cgraph_node (decl);
1837 current_function_decl = NULL;
1838 gimple_register_cfg_hooks ();
1839 bitmap_obstack_initialize (NULL);
1841 invoke_plugin_callbacks (PLUGIN_ALL_IPA_PASSES_START, NULL);
1844 execute_ipa_pass_list (all_small_ipa_passes);
1846 /* If pass_all_early_optimizations was not scheduled, the state of
1847 the cgraph will not be properly updated. Update it now. */
1848 if (cgraph_state < CGRAPH_STATE_IPA_SSA)
1849 cgraph_state = CGRAPH_STATE_IPA_SSA;
1853 /* Generate coverage variables and constructors. */
1856 /* Process new functions added. */
1858 current_function_decl = NULL;
1859 cgraph_process_new_functions ();
1861 execute_ipa_summary_passes
1862 ((struct ipa_opt_pass_d *) all_regular_ipa_passes);
1865 /* Some targets need to handle LTO assembler output specially. */
1866 if (flag_generate_lto)
1867 targetm.asm_out.lto_start ();
1869 execute_ipa_summary_passes ((struct ipa_opt_pass_d *) all_lto_gen_passes);
1872 ipa_write_summaries ();
1874 if (flag_generate_lto)
1875 targetm.asm_out.lto_end ();
1878 execute_ipa_pass_list (all_regular_ipa_passes);
1879 invoke_plugin_callbacks (PLUGIN_ALL_IPA_PASSES_END, NULL);
1881 bitmap_obstack_release (NULL);
1885 /* Perform simple optimizations based on callgraph. */
1888 cgraph_optimize (void)
1890 if (errorcount || sorrycount)
1893 #ifdef ENABLE_CHECKING
1897 /* Frontend may output common variables after the unit has been finalized.
1898 It is safe to deal with them here as they are always zero initialized. */
1899 varpool_analyze_pending_decls ();
1901 timevar_push (TV_CGRAPHOPT);
1902 if (pre_ipa_mem_report)
1904 fprintf (stderr, "Memory consumption before IPA\n");
1905 dump_memory_report (false);
1908 fprintf (stderr, "Performing interprocedural optimizations\n");
1909 cgraph_state = CGRAPH_STATE_IPA;
1911 /* Don't run the IPA passes if there was any error or sorry messages. */
1912 if (errorcount == 0 && sorrycount == 0)
1915 /* Do nothing else if any IPA pass found errors. */
1916 if (errorcount || sorrycount)
1918 timevar_pop (TV_CGRAPHOPT);
1922 /* This pass remove bodies of extern inline functions we never inlined.
1923 Do this later so other IPA passes see what is really going on. */
1924 cgraph_remove_unreachable_nodes (false, dump_file);
1925 cgraph_global_info_ready = true;
1926 if (cgraph_dump_file)
1928 fprintf (cgraph_dump_file, "Optimized ");
1929 dump_cgraph (cgraph_dump_file);
1930 dump_varpool (cgraph_dump_file);
1932 if (post_ipa_mem_report)
1934 fprintf (stderr, "Memory consumption after IPA\n");
1935 dump_memory_report (false);
1937 timevar_pop (TV_CGRAPHOPT);
1939 /* Output everything. */
1940 (*debug_hooks->assembly_start) ();
1942 fprintf (stderr, "Assembling functions:\n");
1943 #ifdef ENABLE_CHECKING
1947 cgraph_materialize_all_clones ();
1948 cgraph_mark_functions_to_output ();
1950 cgraph_state = CGRAPH_STATE_EXPANSION;
1951 if (!flag_toplevel_reorder)
1952 cgraph_output_in_order ();
1955 cgraph_output_pending_asms ();
1957 cgraph_expand_all_functions ();
1958 varpool_remove_unreferenced_decls ();
1960 varpool_assemble_pending_decls ();
1962 cgraph_process_new_functions ();
1963 cgraph_state = CGRAPH_STATE_FINISHED;
1965 if (cgraph_dump_file)
1967 fprintf (cgraph_dump_file, "\nFinal ");
1968 dump_cgraph (cgraph_dump_file);
1970 #ifdef ENABLE_CHECKING
1972 /* Double check that all inline clones are gone and that all
1973 function bodies have been released from memory. */
1974 if (!(sorrycount || errorcount))
1976 struct cgraph_node *node;
1977 bool error_found = false;
1979 for (node = cgraph_nodes; node; node = node->next)
1981 && (node->global.inlined_to
1982 || gimple_has_body_p (node->decl)))
1985 dump_cgraph_node (stderr, node);
1988 internal_error ("nodes with unreleased memory found");
1994 /* Generate and emit a static constructor or destructor. WHICH must
1995 be one of 'I' (for a constructor) or 'D' (for a destructor). BODY
1996 is a STATEMENT_LIST containing GENERIC statements. PRIORITY is the
1997 initialization priority for this constructor or destructor. */
2000 cgraph_build_static_cdtor (char which, tree body, int priority)
2002 static int counter = 0;
2004 tree decl, name, resdecl;
2006 /* The priority is encoded in the constructor or destructor name.
2007 collect2 will sort the names and arrange that they are called at
2009 sprintf (which_buf, "%c_%.5d_%d", which, priority, counter++);
2010 name = get_file_function_name (which_buf);
2012 decl = build_decl (input_location, FUNCTION_DECL, name,
2013 build_function_type (void_type_node, void_list_node));
2014 current_function_decl = decl;
2016 resdecl = build_decl (input_location,
2017 RESULT_DECL, NULL_TREE, void_type_node);
2018 DECL_ARTIFICIAL (resdecl) = 1;
2019 DECL_RESULT (decl) = resdecl;
2020 DECL_CONTEXT (resdecl) = decl;
2022 allocate_struct_function (decl, false);
2024 TREE_STATIC (decl) = 1;
2025 TREE_USED (decl) = 1;
2026 DECL_ARTIFICIAL (decl) = 1;
2027 DECL_NO_INSTRUMENT_FUNCTION_ENTRY_EXIT (decl) = 1;
2028 DECL_SAVED_TREE (decl) = body;
2029 if (!targetm.have_ctors_dtors)
2031 TREE_PUBLIC (decl) = 1;
2032 DECL_PRESERVE_P (decl) = 1;
2034 DECL_UNINLINABLE (decl) = 1;
2036 DECL_INITIAL (decl) = make_node (BLOCK);
2037 TREE_USED (DECL_INITIAL (decl)) = 1;
2039 DECL_SOURCE_LOCATION (decl) = input_location;
2040 cfun->function_end_locus = input_location;
2045 DECL_STATIC_CONSTRUCTOR (decl) = 1;
2046 decl_init_priority_insert (decl, priority);
2049 DECL_STATIC_DESTRUCTOR (decl) = 1;
2050 decl_fini_priority_insert (decl, priority);
2056 gimplify_function_tree (decl);
2058 cgraph_add_new_function (decl, false);
2059 cgraph_mark_needed_node (cgraph_node (decl));
2066 cgraph_dump_file = dump_begin (TDI_cgraph, NULL);
2069 /* The edges representing the callers of the NEW_VERSION node were
2070 fixed by cgraph_function_versioning (), now the call_expr in their
2071 respective tree code should be updated to call the NEW_VERSION. */
2074 update_call_expr (struct cgraph_node *new_version)
2076 struct cgraph_edge *e;
2078 gcc_assert (new_version);
2080 /* Update the call expr on the edges to call the new version. */
2081 for (e = new_version->callers; e; e = e->next_caller)
2083 struct function *inner_function = DECL_STRUCT_FUNCTION (e->caller->decl);
2084 gimple_call_set_fndecl (e->call_stmt, new_version->decl);
2085 maybe_clean_eh_stmt_fn (inner_function, e->call_stmt);
2090 /* Create a new cgraph node which is the new version of
2091 OLD_VERSION node. REDIRECT_CALLERS holds the callers
2092 edges which should be redirected to point to
2093 NEW_VERSION. ALL the callees edges of OLD_VERSION
2094 are cloned to the new version node. Return the new
2097 static struct cgraph_node *
2098 cgraph_copy_node_for_versioning (struct cgraph_node *old_version,
2100 VEC(cgraph_edge_p,heap) *redirect_callers)
2102 struct cgraph_node *new_version;
2103 struct cgraph_edge *e;
2104 struct cgraph_edge *next_callee;
2107 gcc_assert (old_version);
2109 new_version = cgraph_node (new_decl);
2111 new_version->analyzed = true;
2112 new_version->local = old_version->local;
2113 new_version->global = old_version->global;
2114 new_version->rtl = new_version->rtl;
2115 new_version->reachable = true;
2116 new_version->count = old_version->count;
2118 /* Clone the old node callees. Recursive calls are
2120 for (e = old_version->callees;e; e=e->next_callee)
2122 cgraph_clone_edge (e, new_version, e->call_stmt,
2123 e->lto_stmt_uid, REG_BR_PROB_BASE,
2125 e->loop_nest, true);
2127 /* Fix recursive calls.
2128 If OLD_VERSION has a recursive call after the
2129 previous edge cloning, the new version will have an edge
2130 pointing to the old version, which is wrong;
2131 Redirect it to point to the new version. */
2132 for (e = new_version->callees ; e; e = next_callee)
2134 next_callee = e->next_callee;
2135 if (e->callee == old_version)
2136 cgraph_redirect_edge_callee (e, new_version);
2141 for (i = 0; VEC_iterate (cgraph_edge_p, redirect_callers, i, e); i++)
2143 /* Redirect calls to the old version node to point to its new
2145 cgraph_redirect_edge_callee (e, new_version);
2151 /* Perform function versioning.
2152 Function versioning includes copying of the tree and
2153 a callgraph update (creating a new cgraph node and updating
2154 its callees and callers).
2156 REDIRECT_CALLERS varray includes the edges to be redirected
2159 TREE_MAP is a mapping of tree nodes we want to replace with
2160 new ones (according to results of prior analysis).
2161 OLD_VERSION_NODE is the node that is versioned.
2162 It returns the new version's cgraph node.
2163 ARGS_TO_SKIP lists arguments to be omitted from functions
2166 struct cgraph_node *
2167 cgraph_function_versioning (struct cgraph_node *old_version_node,
2168 VEC(cgraph_edge_p,heap) *redirect_callers,
2169 VEC (ipa_replace_map_p,gc)* tree_map,
2170 bitmap args_to_skip)
2172 tree old_decl = old_version_node->decl;
2173 struct cgraph_node *new_version_node = NULL;
2176 if (!tree_versionable_function_p (old_decl))
2179 /* Make a new FUNCTION_DECL tree node for the
2182 new_decl = copy_node (old_decl);
2184 new_decl = build_function_decl_skip_args (old_decl, args_to_skip);
2186 /* Create the new version's call-graph node.
2187 and update the edges of the new node. */
2189 cgraph_copy_node_for_versioning (old_version_node, new_decl,
2192 /* Copy the OLD_VERSION_NODE function tree to the new version. */
2193 tree_function_versioning (old_decl, new_decl, tree_map, false, args_to_skip);
2195 /* Update the new version's properties.
2196 Make The new version visible only within this translation unit. Make sure
2197 that is not weak also.
2198 ??? We cannot use COMDAT linkage because there is no
2199 ABI support for this. */
2200 cgraph_make_decl_local (new_version_node->decl);
2201 DECL_VIRTUAL_P (new_version_node->decl) = 0;
2202 new_version_node->local.externally_visible = 0;
2203 new_version_node->local.local = 1;
2204 new_version_node->lowered = true;
2206 /* Update the call_expr on the edges to call the new version node. */
2207 update_call_expr (new_version_node);
2209 cgraph_call_function_insertion_hooks (new_version_node);
2210 return new_version_node;
2213 /* Produce separate function body for inline clones so the offline copy can be
2214 modified without affecting them. */
2215 struct cgraph_node *
2216 save_inline_function_body (struct cgraph_node *node)
2218 struct cgraph_node *first_clone, *n;
2220 gcc_assert (node == cgraph_node (node->decl));
2222 cgraph_lower_function (node);
2224 first_clone = node->clones;
2226 first_clone->decl = copy_node (node->decl);
2227 cgraph_insert_node_to_hashtable (first_clone);
2228 gcc_assert (first_clone == cgraph_node (first_clone->decl));
2229 if (first_clone->next_sibling_clone)
2231 for (n = first_clone->next_sibling_clone; n->next_sibling_clone; n = n->next_sibling_clone)
2232 n->clone_of = first_clone;
2233 n->clone_of = first_clone;
2234 n->next_sibling_clone = first_clone->clones;
2235 if (first_clone->clones)
2236 first_clone->clones->prev_sibling_clone = n;
2237 first_clone->clones = first_clone->next_sibling_clone;
2238 first_clone->next_sibling_clone->prev_sibling_clone = NULL;
2239 first_clone->next_sibling_clone = NULL;
2240 gcc_assert (!first_clone->prev_sibling_clone);
2242 first_clone->clone_of = NULL;
2243 node->clones = NULL;
2245 if (first_clone->clones)
2246 for (n = first_clone->clones; n != first_clone;)
2248 gcc_assert (n->decl == node->decl);
2249 n->decl = first_clone->decl;
2252 else if (n->next_sibling_clone)
2253 n = n->next_sibling_clone;
2256 while (n != first_clone && !n->next_sibling_clone)
2258 if (n != first_clone)
2259 n = n->next_sibling_clone;
2263 /* Copy the OLD_VERSION_NODE function tree to the new version. */
2264 tree_function_versioning (node->decl, first_clone->decl, NULL, true, NULL);
2266 DECL_EXTERNAL (first_clone->decl) = 0;
2267 DECL_COMDAT_GROUP (first_clone->decl) = NULL_TREE;
2268 TREE_PUBLIC (first_clone->decl) = 0;
2269 DECL_COMDAT (first_clone->decl) = 0;
2270 VEC_free (ipa_opt_pass, heap,
2271 first_clone->ipa_transforms_to_apply);
2272 first_clone->ipa_transforms_to_apply = NULL;
2274 #ifdef ENABLE_CHECKING
2275 verify_cgraph_node (first_clone);
2280 /* Given virtual clone, turn it into actual clone. */
2282 cgraph_materialize_clone (struct cgraph_node *node)
2284 bitmap_obstack_initialize (NULL);
2285 /* Copy the OLD_VERSION_NODE function tree to the new version. */
2286 tree_function_versioning (node->clone_of->decl, node->decl,
2287 node->clone.tree_map, true,
2288 node->clone.args_to_skip);
2289 if (cgraph_dump_file)
2291 dump_function_to_file (node->clone_of->decl, cgraph_dump_file, dump_flags);
2292 dump_function_to_file (node->decl, cgraph_dump_file, dump_flags);
2295 /* Function is no longer clone. */
2296 if (node->next_sibling_clone)
2297 node->next_sibling_clone->prev_sibling_clone = node->prev_sibling_clone;
2298 if (node->prev_sibling_clone)
2299 node->prev_sibling_clone->next_sibling_clone = node->next_sibling_clone;
2301 node->clone_of->clones = node->next_sibling_clone;
2302 node->next_sibling_clone = NULL;
2303 node->prev_sibling_clone = NULL;
2304 if (!node->clone_of->analyzed && !node->clone_of->clones)
2305 cgraph_remove_node (node->clone_of);
2306 node->clone_of = NULL;
2307 bitmap_obstack_release (NULL);
2310 /* If necessary, change the function declaration in the call statement
2311 associated with E so that it corresponds to the edge callee. */
2314 cgraph_redirect_edge_call_stmt_to_callee (struct cgraph_edge *e)
2316 tree decl = gimple_call_fndecl (e->call_stmt);
2318 gimple_stmt_iterator gsi;
2320 if (!decl || decl == e->callee->decl
2321 /* Don't update call from same body alias to the real function. */
2322 || cgraph_get_node (decl) == cgraph_get_node (e->callee->decl))
2323 return e->call_stmt;
2325 if (cgraph_dump_file)
2327 fprintf (cgraph_dump_file, "updating call of %s/%i -> %s/%i: ",
2328 cgraph_node_name (e->caller), e->caller->uid,
2329 cgraph_node_name (e->callee), e->callee->uid);
2330 print_gimple_stmt (cgraph_dump_file, e->call_stmt, 0, dump_flags);
2333 if (e->callee->clone.combined_args_to_skip)
2334 new_stmt = gimple_call_copy_skip_args (e->call_stmt,
2335 e->callee->clone.combined_args_to_skip);
2337 new_stmt = e->call_stmt;
2338 if (gimple_vdef (new_stmt)
2339 && TREE_CODE (gimple_vdef (new_stmt)) == SSA_NAME)
2340 SSA_NAME_DEF_STMT (gimple_vdef (new_stmt)) = new_stmt;
2341 gimple_call_set_fndecl (new_stmt, e->callee->decl);
2343 gsi = gsi_for_stmt (e->call_stmt);
2344 gsi_replace (&gsi, new_stmt, true);
2345 update_stmt (new_stmt);
2347 /* Update EH information too, just in case. */
2348 maybe_clean_or_replace_eh_stmt (e->call_stmt, new_stmt);
2350 cgraph_set_call_stmt_including_clones (e->caller, e->call_stmt, new_stmt);
2352 if (cgraph_dump_file)
2354 fprintf (cgraph_dump_file, " updated to:");
2355 print_gimple_stmt (cgraph_dump_file, e->call_stmt, 0, dump_flags);
2360 /* Once all functions from compilation unit are in memory, produce all clones
2361 and update all calls. We might also do this on demand if we don't want to
2362 bring all functions to memory prior compilation, but current WHOPR
2363 implementation does that and it is is bit easier to keep everything right in
2366 cgraph_materialize_all_clones (void)
2368 struct cgraph_node *node;
2369 bool stabilized = false;
2371 if (cgraph_dump_file)
2372 fprintf (cgraph_dump_file, "Materializing clones\n");
2373 #ifdef ENABLE_CHECKING
2377 /* We can also do topological order, but number of iterations should be
2378 bounded by number of IPA passes since single IPA pass is probably not
2379 going to create clones of clones it created itself. */
2383 for (node = cgraph_nodes; node; node = node->next)
2385 if (node->clone_of && node->decl != node->clone_of->decl
2386 && !gimple_has_body_p (node->decl))
2388 if (gimple_has_body_p (node->clone_of->decl))
2390 if (cgraph_dump_file)
2392 fprintf (cgraph_dump_file, "clonning %s to %s\n",
2393 cgraph_node_name (node->clone_of),
2394 cgraph_node_name (node));
2395 if (node->clone.tree_map)
2398 fprintf (cgraph_dump_file, " replace map: ");
2399 for (i = 0; i < VEC_length (ipa_replace_map_p,
2400 node->clone.tree_map);
2403 struct ipa_replace_map *replace_info;
2404 replace_info = VEC_index (ipa_replace_map_p,
2405 node->clone.tree_map,
2407 print_generic_expr (cgraph_dump_file, replace_info->old_tree, 0);
2408 fprintf (cgraph_dump_file, " -> ");
2409 print_generic_expr (cgraph_dump_file, replace_info->new_tree, 0);
2410 fprintf (cgraph_dump_file, "%s%s;",
2411 replace_info->replace_p ? "(replace)":"",
2412 replace_info->ref_p ? "(ref)":"");
2414 fprintf (cgraph_dump_file, "\n");
2416 if (node->clone.args_to_skip)
2418 fprintf (cgraph_dump_file, " args_to_skip: ");
2419 dump_bitmap (cgraph_dump_file, node->clone.args_to_skip);
2421 if (node->clone.args_to_skip)
2423 fprintf (cgraph_dump_file, " combined_args_to_skip:");
2424 dump_bitmap (cgraph_dump_file, node->clone.combined_args_to_skip);
2427 cgraph_materialize_clone (node);
2434 for (node = cgraph_nodes; node; node = node->next)
2435 if (!node->analyzed && node->callees)
2436 cgraph_node_remove_callees (node);
2437 if (cgraph_dump_file)
2438 fprintf (cgraph_dump_file, "Updating call sites\n");
2439 for (node = cgraph_nodes; node; node = node->next)
2440 if (node->analyzed && !node->clone_of
2441 && gimple_has_body_p (node->decl))
2443 struct cgraph_edge *e;
2445 current_function_decl = node->decl;
2446 push_cfun (DECL_STRUCT_FUNCTION (node->decl));
2447 for (e = node->callees; e; e = e->next_callee)
2448 cgraph_redirect_edge_call_stmt_to_callee (e);
2449 gcc_assert (!need_ssa_update_p (cfun));
2451 current_function_decl = NULL;
2452 #ifdef ENABLE_CHECKING
2453 verify_cgraph_node (node);
2456 if (cgraph_dump_file)
2457 fprintf (cgraph_dump_file, "Materialization Call site updates done.\n");
2458 /* All changes to parameters have been performed. In order not to
2459 incorrectly repeat them, we simply dispose of the bitmaps that drive the
2461 for (node = cgraph_nodes; node; node = node->next)
2462 node->clone.combined_args_to_skip = NULL;
2463 #ifdef ENABLE_CHECKING
2466 cgraph_remove_unreachable_nodes (false, cgraph_dump_file);
2469 #include "gt-cgraphunit.h"