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))
963 mark_decl_referenced (decl);
964 if (node->local.finalized)
965 cgraph_mark_needed_node (node);
967 if (lookup_attribute ("externally_visible", DECL_ATTRIBUTES (decl)))
969 if (! TREE_PUBLIC (node->decl))
970 warning_at (DECL_SOURCE_LOCATION (node->decl), OPT_Wattributes,
971 "%<externally_visible%>"
972 " attribute have effect only on public objects");
973 else if (node->local.finalized)
974 cgraph_mark_needed_node (node);
977 for (vnode = varpool_nodes; vnode != first_var; vnode = vnode->next)
979 tree decl = vnode->decl;
980 if (DECL_PRESERVE_P (decl))
982 mark_decl_referenced (decl);
983 vnode->force_output = true;
984 if (vnode->finalized)
985 varpool_mark_needed_node (vnode);
987 if (lookup_attribute ("externally_visible", DECL_ATTRIBUTES (decl)))
989 if (! TREE_PUBLIC (vnode->decl))
990 warning_at (DECL_SOURCE_LOCATION (vnode->decl), OPT_Wattributes,
991 "%<externally_visible%>"
992 " attribute have effect only on public objects");
993 else if (vnode->finalized)
994 varpool_mark_needed_node (vnode);
999 /* Process CGRAPH_NODES_NEEDED queue, analyze each function (and transitively
1000 each reachable functions) and build cgraph.
1001 The function can be called multiple times after inserting new nodes
1002 into beginning of queue. Just the new part of queue is re-scanned then. */
1005 cgraph_analyze_functions (void)
1007 /* Keep track of already processed nodes when called multiple times for
1008 intermodule optimization. */
1009 static struct cgraph_node *first_analyzed;
1010 struct cgraph_node *first_processed = first_analyzed;
1011 static struct varpool_node *first_analyzed_var;
1012 struct cgraph_node *node, *next;
1014 process_function_and_variable_attributes (first_processed,
1015 first_analyzed_var);
1016 first_processed = cgraph_nodes;
1017 first_analyzed_var = varpool_nodes;
1018 varpool_analyze_pending_decls ();
1019 if (cgraph_dump_file)
1021 fprintf (cgraph_dump_file, "Initial entry points:");
1022 for (node = cgraph_nodes; node != first_analyzed; node = node->next)
1024 fprintf (cgraph_dump_file, " %s", cgraph_node_name (node));
1025 fprintf (cgraph_dump_file, "\n");
1027 cgraph_process_new_functions ();
1029 /* Propagate reachability flag and lower representation of all reachable
1030 functions. In the future, lowering will introduce new functions and
1031 new entry points on the way (by template instantiation and virtual
1032 method table generation for instance). */
1033 while (cgraph_nodes_queue)
1035 struct cgraph_edge *edge;
1036 tree decl = cgraph_nodes_queue->decl;
1038 node = cgraph_nodes_queue;
1039 cgraph_nodes_queue = cgraph_nodes_queue->next_needed;
1040 node->next_needed = NULL;
1042 /* ??? It is possible to create extern inline function and later using
1043 weak alias attribute to kill its body. See
1044 gcc.c-torture/compile/20011119-1.c */
1045 if (!DECL_STRUCT_FUNCTION (decl))
1047 cgraph_reset_node (node);
1051 if (!node->analyzed)
1052 cgraph_analyze_function (node);
1054 for (edge = node->callees; edge; edge = edge->next_callee)
1055 if (!edge->callee->reachable)
1056 cgraph_mark_reachable_node (edge->callee);
1058 if (node->same_comdat_group)
1060 for (next = node->same_comdat_group;
1062 next = next->same_comdat_group)
1063 cgraph_mark_reachable_node (next);
1066 /* If decl is a clone of an abstract function, mark that abstract
1067 function so that we don't release its body. The DECL_INITIAL() of that
1068 abstract function declaration will be later needed to output debug info. */
1069 if (DECL_ABSTRACT_ORIGIN (decl))
1071 struct cgraph_node *origin_node = cgraph_node (DECL_ABSTRACT_ORIGIN (decl));
1072 origin_node->abstract_and_needed = true;
1075 /* We finalize local static variables during constructing callgraph
1076 edges. Process their attributes too. */
1077 process_function_and_variable_attributes (first_processed,
1078 first_analyzed_var);
1079 first_processed = cgraph_nodes;
1080 first_analyzed_var = varpool_nodes;
1081 varpool_analyze_pending_decls ();
1082 cgraph_process_new_functions ();
1085 /* Collect entry points to the unit. */
1086 if (cgraph_dump_file)
1088 fprintf (cgraph_dump_file, "Unit entry points:");
1089 for (node = cgraph_nodes; node != first_analyzed; node = node->next)
1091 fprintf (cgraph_dump_file, " %s", cgraph_node_name (node));
1092 fprintf (cgraph_dump_file, "\n\nInitial ");
1093 dump_cgraph (cgraph_dump_file);
1096 if (cgraph_dump_file)
1097 fprintf (cgraph_dump_file, "\nReclaiming functions:");
1099 for (node = cgraph_nodes; node != first_analyzed; node = next)
1101 tree decl = node->decl;
1104 if (node->local.finalized && !gimple_has_body_p (decl))
1105 cgraph_reset_node (node);
1107 if (!node->reachable && gimple_has_body_p (decl))
1109 if (cgraph_dump_file)
1110 fprintf (cgraph_dump_file, " %s", cgraph_node_name (node));
1111 cgraph_remove_node (node);
1115 node->next_needed = NULL;
1116 gcc_assert (!node->local.finalized || gimple_has_body_p (decl));
1117 gcc_assert (node->analyzed == node->local.finalized);
1119 if (cgraph_dump_file)
1121 fprintf (cgraph_dump_file, "\n\nReclaimed ");
1122 dump_cgraph (cgraph_dump_file);
1124 first_analyzed = cgraph_nodes;
1129 /* Analyze the whole compilation unit once it is parsed completely. */
1132 cgraph_finalize_compilation_unit (void)
1134 timevar_push (TV_CGRAPH);
1136 /* Do not skip analyzing the functions if there were errors, we
1137 miss diagnostics for following functions otherwise. */
1139 /* Emit size functions we didn't inline. */
1140 finalize_size_functions ();
1142 /* Call functions declared with the "constructor" or "destructor"
1144 cgraph_build_cdtor_fns ();
1146 /* Mark alias targets necessary and emit diagnostics. */
1147 finish_aliases_1 ();
1151 fprintf (stderr, "\nAnalyzing compilation unit\n");
1155 /* Gimplify and lower all functions, compute reachability and
1156 remove unreachable nodes. */
1157 cgraph_analyze_functions ();
1159 /* Mark alias targets necessary and emit diagnostics. */
1160 finish_aliases_1 ();
1162 /* Gimplify and lower thunks. */
1163 cgraph_analyze_functions ();
1165 /* Finally drive the pass manager. */
1168 timevar_pop (TV_CGRAPH);
1172 /* Figure out what functions we want to assemble. */
1175 cgraph_mark_functions_to_output (void)
1177 struct cgraph_node *node;
1178 #ifdef ENABLE_CHECKING
1179 bool check_same_comdat_groups = false;
1181 for (node = cgraph_nodes; node; node = node->next)
1182 gcc_assert (!node->process);
1185 for (node = cgraph_nodes; node; node = node->next)
1187 tree decl = node->decl;
1188 struct cgraph_edge *e;
1190 gcc_assert (!node->process || node->same_comdat_group);
1194 for (e = node->callers; e; e = e->next_caller)
1195 if (e->inline_failed)
1198 /* We need to output all local functions that are used and not
1199 always inlined, as well as those that are reachable from
1200 outside the current compilation unit. */
1202 && !node->global.inlined_to
1203 && (node->needed || node->reachable_from_other_partition
1204 || (e && node->reachable))
1205 && !TREE_ASM_WRITTEN (decl)
1206 && !DECL_EXTERNAL (decl))
1209 if (node->same_comdat_group)
1211 struct cgraph_node *next;
1212 for (next = node->same_comdat_group;
1214 next = next->same_comdat_group)
1218 else if (node->same_comdat_group)
1220 #ifdef ENABLE_CHECKING
1221 check_same_comdat_groups = true;
1226 /* We should've reclaimed all functions that are not needed. */
1227 #ifdef ENABLE_CHECKING
1228 if (!node->global.inlined_to
1229 && gimple_has_body_p (decl)
1230 /* FIXME: in ltrans unit when offline copy is outside partition but inline copies
1231 are inside partition, we can end up not removing the body since we no longer
1232 have analyzed node pointing to it. */
1233 && !node->in_other_partition
1234 && !DECL_EXTERNAL (decl))
1236 dump_cgraph_node (stderr, node);
1237 internal_error ("failed to reclaim unneeded function");
1240 gcc_assert (node->global.inlined_to
1241 || !gimple_has_body_p (decl)
1242 || node->in_other_partition
1243 || DECL_EXTERNAL (decl));
1248 #ifdef ENABLE_CHECKING
1249 if (check_same_comdat_groups)
1250 for (node = cgraph_nodes; node; node = node->next)
1251 if (node->same_comdat_group && !node->process)
1253 tree decl = node->decl;
1254 if (!node->global.inlined_to
1255 && gimple_has_body_p (decl)
1256 /* FIXME: in ltrans unit when offline copy is outside partition but inline copies
1257 are inside partition, we can end up not removing the body since we no longer
1258 have analyzed node pointing to it. */
1259 && !node->in_other_partition
1260 && !DECL_EXTERNAL (decl))
1262 dump_cgraph_node (stderr, node);
1263 internal_error ("failed to reclaim unneeded function");
1269 /* DECL is FUNCTION_DECL. Initialize datastructures so DECL is a function
1270 in lowered gimple form.
1272 Set current_function_decl and cfun to newly constructed empty function body.
1273 return basic block in the function body. */
1276 init_lowered_empty_function (tree decl)
1280 current_function_decl = decl;
1281 allocate_struct_function (decl, false);
1282 gimple_register_cfg_hooks ();
1283 init_empty_tree_cfg ();
1284 init_tree_ssa (cfun);
1285 init_ssa_operands ();
1286 cfun->gimple_df->in_ssa_p = true;
1287 DECL_INITIAL (decl) = make_node (BLOCK);
1289 DECL_SAVED_TREE (decl) = error_mark_node;
1290 cfun->curr_properties |=
1291 (PROP_gimple_lcf | PROP_gimple_leh | PROP_cfg | PROP_referenced_vars |
1294 /* Create BB for body of the function and connect it properly. */
1295 bb = create_basic_block (NULL, (void *) 0, ENTRY_BLOCK_PTR);
1296 make_edge (ENTRY_BLOCK_PTR, bb, 0);
1297 make_edge (bb, EXIT_BLOCK_PTR, 0);
1302 /* Adjust PTR by the constant FIXED_OFFSET, and by the vtable
1303 offset indicated by VIRTUAL_OFFSET, if that is
1304 non-null. THIS_ADJUSTING is nonzero for a this adjusting thunk and
1305 zero for a result adjusting thunk. */
1308 thunk_adjust (gimple_stmt_iterator * bsi,
1309 tree ptr, bool this_adjusting,
1310 HOST_WIDE_INT fixed_offset, tree virtual_offset)
1316 && fixed_offset != 0)
1318 stmt = gimple_build_assign (ptr,
1319 fold_build2_loc (input_location,
1321 TREE_TYPE (ptr), ptr,
1322 size_int (fixed_offset)));
1323 gsi_insert_after (bsi, stmt, GSI_NEW_STMT);
1326 /* If there's a virtual offset, look up that value in the vtable and
1327 adjust the pointer again. */
1335 if (!vtable_entry_type)
1337 tree vfunc_type = make_node (FUNCTION_TYPE);
1338 TREE_TYPE (vfunc_type) = integer_type_node;
1339 TYPE_ARG_TYPES (vfunc_type) = NULL_TREE;
1340 layout_type (vfunc_type);
1342 vtable_entry_type = build_pointer_type (vfunc_type);
1346 create_tmp_var (build_pointer_type
1347 (build_pointer_type (vtable_entry_type)), "vptr");
1349 /* The vptr is always at offset zero in the object. */
1350 stmt = gimple_build_assign (vtabletmp,
1351 build1 (NOP_EXPR, TREE_TYPE (vtabletmp),
1353 gsi_insert_after (bsi, stmt, GSI_NEW_STMT);
1354 mark_symbols_for_renaming (stmt);
1355 find_referenced_vars_in (stmt);
1357 /* Form the vtable address. */
1358 vtabletmp2 = create_tmp_var (TREE_TYPE (TREE_TYPE (vtabletmp)),
1360 stmt = gimple_build_assign (vtabletmp2,
1361 build1 (INDIRECT_REF,
1362 TREE_TYPE (vtabletmp2), vtabletmp));
1363 gsi_insert_after (bsi, stmt, GSI_NEW_STMT);
1364 mark_symbols_for_renaming (stmt);
1365 find_referenced_vars_in (stmt);
1367 /* Find the entry with the vcall offset. */
1368 stmt = gimple_build_assign (vtabletmp2,
1369 fold_build2_loc (input_location,
1371 TREE_TYPE (vtabletmp2),
1373 fold_convert (sizetype,
1375 gsi_insert_after (bsi, stmt, GSI_NEW_STMT);
1377 /* Get the offset itself. */
1378 vtabletmp3 = create_tmp_var (TREE_TYPE (TREE_TYPE (vtabletmp2)),
1380 stmt = gimple_build_assign (vtabletmp3,
1381 build1 (INDIRECT_REF,
1382 TREE_TYPE (vtabletmp3),
1384 gsi_insert_after (bsi, stmt, GSI_NEW_STMT);
1385 mark_symbols_for_renaming (stmt);
1386 find_referenced_vars_in (stmt);
1388 /* Cast to sizetype. */
1389 offsettmp = create_tmp_var (sizetype, "offset");
1390 stmt = gimple_build_assign (offsettmp, fold_convert (sizetype, vtabletmp3));
1391 gsi_insert_after (bsi, stmt, GSI_NEW_STMT);
1392 mark_symbols_for_renaming (stmt);
1393 find_referenced_vars_in (stmt);
1395 /* Adjust the `this' pointer. */
1396 ptr = fold_build2_loc (input_location,
1397 POINTER_PLUS_EXPR, TREE_TYPE (ptr), ptr,
1402 && fixed_offset != 0)
1403 /* Adjust the pointer by the constant. */
1407 if (TREE_CODE (ptr) == VAR_DECL)
1411 ptrtmp = create_tmp_var (TREE_TYPE (ptr), "ptr");
1412 stmt = gimple_build_assign (ptrtmp, ptr);
1413 gsi_insert_after (bsi, stmt, GSI_NEW_STMT);
1414 mark_symbols_for_renaming (stmt);
1415 find_referenced_vars_in (stmt);
1417 ptr = fold_build2_loc (input_location,
1418 POINTER_PLUS_EXPR, TREE_TYPE (ptrtmp), ptrtmp,
1419 size_int (fixed_offset));
1422 /* Emit the statement and gimplify the adjustment expression. */
1423 ret = create_tmp_var (TREE_TYPE (ptr), "adjusted_this");
1424 stmt = gimple_build_assign (ret, ptr);
1425 mark_symbols_for_renaming (stmt);
1426 find_referenced_vars_in (stmt);
1427 gsi_insert_after (bsi, stmt, GSI_NEW_STMT);
1432 /* Produce assembler for thunk NODE. */
1435 assemble_thunk (struct cgraph_node *node)
1437 bool this_adjusting = node->thunk.this_adjusting;
1438 HOST_WIDE_INT fixed_offset = node->thunk.fixed_offset;
1439 HOST_WIDE_INT virtual_value = node->thunk.virtual_value;
1440 tree virtual_offset = NULL;
1441 tree alias = node->thunk.alias;
1442 tree thunk_fndecl = node->decl;
1443 tree a = DECL_ARGUMENTS (thunk_fndecl);
1445 current_function_decl = thunk_fndecl;
1448 && targetm.asm_out.can_output_mi_thunk (thunk_fndecl, fixed_offset,
1449 virtual_value, alias))
1454 DECL_RESULT (thunk_fndecl)
1455 = build_decl (DECL_SOURCE_LOCATION (thunk_fndecl),
1456 RESULT_DECL, 0, integer_type_node);
1457 fnname = IDENTIFIER_POINTER (DECL_ASSEMBLER_NAME (thunk_fndecl));
1459 /* The back end expects DECL_INITIAL to contain a BLOCK, so we
1461 fn_block = make_node (BLOCK);
1462 BLOCK_VARS (fn_block) = a;
1463 DECL_INITIAL (thunk_fndecl) = fn_block;
1464 init_function_start (thunk_fndecl);
1466 assemble_start_function (thunk_fndecl, fnname);
1468 targetm.asm_out.output_mi_thunk (asm_out_file, thunk_fndecl,
1469 fixed_offset, virtual_value, alias);
1471 assemble_end_function (thunk_fndecl, fnname);
1472 init_insn_lengths ();
1473 free_after_compilation (cfun);
1475 TREE_ASM_WRITTEN (thunk_fndecl) = 1;
1480 basic_block bb, then_bb, else_bb, return_bb;
1481 gimple_stmt_iterator bsi;
1487 VEC(tree, heap) *vargs;
1492 DECL_IGNORED_P (thunk_fndecl) = 1;
1493 bitmap_obstack_initialize (NULL);
1495 if (node->thunk.virtual_offset_p)
1496 virtual_offset = size_int (virtual_value);
1498 /* Build the return declaration for the function. */
1499 restype = TREE_TYPE (TREE_TYPE (thunk_fndecl));
1500 if (DECL_RESULT (thunk_fndecl) == NULL_TREE)
1502 resdecl = build_decl (input_location, RESULT_DECL, 0, restype);
1503 DECL_ARTIFICIAL (resdecl) = 1;
1504 DECL_IGNORED_P (resdecl) = 1;
1505 DECL_RESULT (thunk_fndecl) = resdecl;
1508 resdecl = DECL_RESULT (thunk_fndecl);
1510 bb = then_bb = else_bb = return_bb = init_lowered_empty_function (thunk_fndecl);
1512 bsi = gsi_start_bb (bb);
1514 /* Build call to the function being thunked. */
1515 if (!VOID_TYPE_P (restype))
1517 if (!is_gimple_reg_type (restype))
1520 cfun->local_decls = tree_cons (NULL_TREE, restmp, cfun->local_decls);
1521 BLOCK_VARS (DECL_INITIAL (current_function_decl)) = restmp;
1524 restmp = create_tmp_var_raw (restype, "retval");
1527 for (arg = a; arg; arg = TREE_CHAIN (arg))
1529 vargs = VEC_alloc (tree, heap, nargs);
1531 VEC_quick_push (tree, vargs,
1536 VEC_quick_push (tree, vargs, a);
1537 for (i = 1, arg = TREE_CHAIN (a); i < nargs; i++, arg = TREE_CHAIN (arg))
1538 VEC_quick_push (tree, vargs, arg);
1539 call = gimple_build_call_vec (build_fold_addr_expr_loc (0, alias), vargs);
1540 VEC_free (tree, heap, vargs);
1541 gimple_call_set_cannot_inline (call, true);
1542 gimple_call_set_from_thunk (call, true);
1544 gimple_call_set_lhs (call, restmp);
1545 gsi_insert_after (&bsi, call, GSI_NEW_STMT);
1546 mark_symbols_for_renaming (call);
1547 find_referenced_vars_in (call);
1550 if (restmp && !this_adjusting)
1552 tree true_label = NULL_TREE;
1554 if (TREE_CODE (TREE_TYPE (restmp)) == POINTER_TYPE)
1557 /* If the return type is a pointer, we need to
1558 protect against NULL. We know there will be an
1559 adjustment, because that's why we're emitting a
1561 then_bb = create_basic_block (NULL, (void *) 0, bb);
1562 return_bb = create_basic_block (NULL, (void *) 0, then_bb);
1563 else_bb = create_basic_block (NULL, (void *) 0, else_bb);
1564 remove_edge (single_succ_edge (bb));
1565 true_label = gimple_block_label (then_bb);
1566 stmt = gimple_build_cond (NE_EXPR, restmp,
1567 fold_convert (TREE_TYPE (restmp),
1569 NULL_TREE, NULL_TREE);
1570 gsi_insert_after (&bsi, stmt, GSI_NEW_STMT);
1571 make_edge (bb, then_bb, EDGE_TRUE_VALUE);
1572 make_edge (bb, else_bb, EDGE_FALSE_VALUE);
1573 make_edge (return_bb, EXIT_BLOCK_PTR, 0);
1574 make_edge (then_bb, return_bb, EDGE_FALLTHRU);
1575 make_edge (else_bb, return_bb, EDGE_FALLTHRU);
1576 bsi = gsi_last_bb (then_bb);
1579 restmp = thunk_adjust (&bsi, restmp, /*this_adjusting=*/0,
1580 fixed_offset, virtual_offset);
1584 bsi = gsi_last_bb (else_bb);
1585 stmt = gimple_build_assign (restmp, fold_convert (TREE_TYPE (restmp),
1586 integer_zero_node));
1587 gsi_insert_after (&bsi, stmt, GSI_NEW_STMT);
1588 bsi = gsi_last_bb (return_bb);
1592 gimple_call_set_tail (call, true);
1594 /* Build return value. */
1595 ret = gimple_build_return (restmp);
1596 gsi_insert_after (&bsi, ret, GSI_NEW_STMT);
1598 delete_unreachable_blocks ();
1599 update_ssa (TODO_update_ssa);
1601 cgraph_remove_same_body_alias (node);
1602 /* Since we want to emit the thunk, we explicitly mark its name as
1604 mark_decl_referenced (thunk_fndecl);
1605 cgraph_add_new_function (thunk_fndecl, true);
1606 bitmap_obstack_release (NULL);
1608 current_function_decl = NULL;
1611 /* Expand function specified by NODE. */
1614 cgraph_expand_function (struct cgraph_node *node)
1616 tree decl = node->decl;
1618 /* We ought to not compile any inline clones. */
1619 gcc_assert (!node->global.inlined_to);
1621 announce_function (decl);
1624 gcc_assert (node->lowered);
1626 /* Generate RTL for the body of DECL. */
1627 tree_rest_of_compilation (decl);
1629 /* Make sure that BE didn't give up on compiling. */
1630 gcc_assert (TREE_ASM_WRITTEN (decl));
1631 current_function_decl = NULL;
1632 if (node->same_body)
1634 struct cgraph_node *alias, *next;
1635 bool saved_alias = node->alias;
1636 for (alias = node->same_body;
1637 alias && alias->next; alias = alias->next)
1639 /* Walk aliases in the order they were created; it is possible that
1640 thunks reffers to the aliases made earlier. */
1641 for (; alias; alias = next)
1643 next = alias->previous;
1644 if (!alias->thunk.thunk_p)
1645 assemble_alias (alias->decl,
1646 DECL_ASSEMBLER_NAME (alias->thunk.alias));
1648 assemble_thunk (alias);
1650 node->alias = saved_alias;
1652 gcc_assert (!cgraph_preserve_function_body_p (decl));
1653 cgraph_release_function_body (node);
1654 /* Eliminate all call edges. This is important so the GIMPLE_CALL no longer
1655 points to the dead function body. */
1656 cgraph_node_remove_callees (node);
1658 cgraph_function_flags_ready = true;
1661 /* Return true when CALLER_DECL should be inlined into CALLEE_DECL. */
1664 cgraph_inline_p (struct cgraph_edge *e, cgraph_inline_failed_t *reason)
1666 *reason = e->inline_failed;
1667 return !e->inline_failed;
1672 /* Expand all functions that must be output.
1674 Attempt to topologically sort the nodes so function is output when
1675 all called functions are already assembled to allow data to be
1676 propagated across the callgraph. Use a stack to get smaller distance
1677 between a function and its callees (later we may choose to use a more
1678 sophisticated algorithm for function reordering; we will likely want
1679 to use subsections to make the output functions appear in top-down
1683 cgraph_expand_all_functions (void)
1685 struct cgraph_node *node;
1686 struct cgraph_node **order = XCNEWVEC (struct cgraph_node *, cgraph_n_nodes);
1687 int order_pos, new_order_pos = 0;
1690 order_pos = cgraph_postorder (order);
1691 gcc_assert (order_pos == cgraph_n_nodes);
1693 /* Garbage collector may remove inline clones we eliminate during
1694 optimization. So we must be sure to not reference them. */
1695 for (i = 0; i < order_pos; i++)
1696 if (order[i]->process)
1697 order[new_order_pos++] = order[i];
1699 for (i = new_order_pos - 1; i >= 0; i--)
1704 gcc_assert (node->reachable);
1706 cgraph_expand_function (node);
1709 cgraph_process_new_functions ();
1715 /* This is used to sort the node types by the cgraph order number. */
1717 enum cgraph_order_sort_kind
1719 ORDER_UNDEFINED = 0,
1725 struct cgraph_order_sort
1727 enum cgraph_order_sort_kind kind;
1730 struct cgraph_node *f;
1731 struct varpool_node *v;
1732 struct cgraph_asm_node *a;
1736 /* Output all functions, variables, and asm statements in the order
1737 according to their order fields, which is the order in which they
1738 appeared in the file. This implements -fno-toplevel-reorder. In
1739 this mode we may output functions and variables which don't really
1740 need to be output. */
1743 cgraph_output_in_order (void)
1746 struct cgraph_order_sort *nodes;
1748 struct cgraph_node *pf;
1749 struct varpool_node *pv;
1750 struct cgraph_asm_node *pa;
1753 nodes = XCNEWVEC (struct cgraph_order_sort, max);
1755 varpool_analyze_pending_decls ();
1757 for (pf = cgraph_nodes; pf; pf = pf->next)
1762 gcc_assert (nodes[i].kind == ORDER_UNDEFINED);
1763 nodes[i].kind = ORDER_FUNCTION;
1768 for (pv = varpool_nodes_queue; pv; pv = pv->next_needed)
1771 gcc_assert (nodes[i].kind == ORDER_UNDEFINED);
1772 nodes[i].kind = ORDER_VAR;
1776 for (pa = cgraph_asm_nodes; pa; pa = pa->next)
1779 gcc_assert (nodes[i].kind == ORDER_UNDEFINED);
1780 nodes[i].kind = ORDER_ASM;
1784 /* In toplevel reorder mode we output all statics; mark them as needed. */
1785 for (i = 0; i < max; ++i)
1787 if (nodes[i].kind == ORDER_VAR)
1789 varpool_mark_needed_node (nodes[i].u.v);
1792 varpool_empty_needed_queue ();
1794 for (i = 0; i < max; ++i)
1796 switch (nodes[i].kind)
1798 case ORDER_FUNCTION:
1799 nodes[i].u.f->process = 0;
1800 cgraph_expand_function (nodes[i].u.f);
1804 varpool_assemble_decl (nodes[i].u.v);
1808 assemble_asm (nodes[i].u.a->asm_str);
1811 case ORDER_UNDEFINED:
1819 cgraph_asm_nodes = NULL;
1823 /* Return true when function body of DECL still needs to be kept around
1824 for later re-use. */
1826 cgraph_preserve_function_body_p (tree decl)
1828 struct cgraph_node *node;
1830 gcc_assert (cgraph_global_info_ready);
1831 /* Look if there is any clone around. */
1832 node = cgraph_node (decl);
1842 current_function_decl = NULL;
1843 gimple_register_cfg_hooks ();
1844 bitmap_obstack_initialize (NULL);
1846 invoke_plugin_callbacks (PLUGIN_ALL_IPA_PASSES_START, NULL);
1849 execute_ipa_pass_list (all_small_ipa_passes);
1851 /* If pass_all_early_optimizations was not scheduled, the state of
1852 the cgraph will not be properly updated. Update it now. */
1853 if (cgraph_state < CGRAPH_STATE_IPA_SSA)
1854 cgraph_state = CGRAPH_STATE_IPA_SSA;
1858 /* Generate coverage variables and constructors. */
1861 /* Process new functions added. */
1863 current_function_decl = NULL;
1864 cgraph_process_new_functions ();
1866 execute_ipa_summary_passes
1867 ((struct ipa_opt_pass_d *) all_regular_ipa_passes);
1870 /* Some targets need to handle LTO assembler output specially. */
1871 if (flag_generate_lto)
1872 targetm.asm_out.lto_start ();
1874 execute_ipa_summary_passes ((struct ipa_opt_pass_d *) all_lto_gen_passes);
1877 ipa_write_summaries ();
1879 if (flag_generate_lto)
1880 targetm.asm_out.lto_end ();
1883 execute_ipa_pass_list (all_regular_ipa_passes);
1884 invoke_plugin_callbacks (PLUGIN_ALL_IPA_PASSES_END, NULL);
1886 bitmap_obstack_release (NULL);
1890 /* Perform simple optimizations based on callgraph. */
1893 cgraph_optimize (void)
1895 if (errorcount || sorrycount)
1898 #ifdef ENABLE_CHECKING
1902 /* Frontend may output common variables after the unit has been finalized.
1903 It is safe to deal with them here as they are always zero initialized. */
1904 varpool_analyze_pending_decls ();
1906 timevar_push (TV_CGRAPHOPT);
1907 if (pre_ipa_mem_report)
1909 fprintf (stderr, "Memory consumption before IPA\n");
1910 dump_memory_report (false);
1913 fprintf (stderr, "Performing interprocedural optimizations\n");
1914 cgraph_state = CGRAPH_STATE_IPA;
1916 /* Don't run the IPA passes if there was any error or sorry messages. */
1917 if (errorcount == 0 && sorrycount == 0)
1920 /* Do nothing else if any IPA pass found errors. */
1921 if (errorcount || sorrycount)
1923 timevar_pop (TV_CGRAPHOPT);
1927 /* This pass remove bodies of extern inline functions we never inlined.
1928 Do this later so other IPA passes see what is really going on. */
1929 cgraph_remove_unreachable_nodes (false, dump_file);
1930 cgraph_global_info_ready = true;
1931 if (cgraph_dump_file)
1933 fprintf (cgraph_dump_file, "Optimized ");
1934 dump_cgraph (cgraph_dump_file);
1935 dump_varpool (cgraph_dump_file);
1937 if (post_ipa_mem_report)
1939 fprintf (stderr, "Memory consumption after IPA\n");
1940 dump_memory_report (false);
1942 timevar_pop (TV_CGRAPHOPT);
1944 /* Output everything. */
1945 (*debug_hooks->assembly_start) ();
1947 fprintf (stderr, "Assembling functions:\n");
1948 #ifdef ENABLE_CHECKING
1952 cgraph_materialize_all_clones ();
1953 cgraph_mark_functions_to_output ();
1955 cgraph_state = CGRAPH_STATE_EXPANSION;
1956 if (!flag_toplevel_reorder)
1957 cgraph_output_in_order ();
1960 cgraph_output_pending_asms ();
1962 cgraph_expand_all_functions ();
1963 varpool_remove_unreferenced_decls ();
1965 varpool_assemble_pending_decls ();
1967 cgraph_process_new_functions ();
1968 cgraph_state = CGRAPH_STATE_FINISHED;
1970 if (cgraph_dump_file)
1972 fprintf (cgraph_dump_file, "\nFinal ");
1973 dump_cgraph (cgraph_dump_file);
1975 #ifdef ENABLE_CHECKING
1977 /* Double check that all inline clones are gone and that all
1978 function bodies have been released from memory. */
1979 if (!(sorrycount || errorcount))
1981 struct cgraph_node *node;
1982 bool error_found = false;
1984 for (node = cgraph_nodes; node; node = node->next)
1986 && (node->global.inlined_to
1987 || gimple_has_body_p (node->decl)))
1990 dump_cgraph_node (stderr, node);
1993 internal_error ("nodes with unreleased memory found");
1999 /* Generate and emit a static constructor or destructor. WHICH must
2000 be one of 'I' (for a constructor) or 'D' (for a destructor). BODY
2001 is a STATEMENT_LIST containing GENERIC statements. PRIORITY is the
2002 initialization priority for this constructor or destructor. */
2005 cgraph_build_static_cdtor (char which, tree body, int priority)
2007 static int counter = 0;
2009 tree decl, name, resdecl;
2011 /* The priority is encoded in the constructor or destructor name.
2012 collect2 will sort the names and arrange that they are called at
2014 sprintf (which_buf, "%c_%.5d_%d", which, priority, counter++);
2015 name = get_file_function_name (which_buf);
2017 decl = build_decl (input_location, FUNCTION_DECL, name,
2018 build_function_type (void_type_node, void_list_node));
2019 current_function_decl = decl;
2021 resdecl = build_decl (input_location,
2022 RESULT_DECL, NULL_TREE, void_type_node);
2023 DECL_ARTIFICIAL (resdecl) = 1;
2024 DECL_RESULT (decl) = resdecl;
2025 DECL_CONTEXT (resdecl) = decl;
2027 allocate_struct_function (decl, false);
2029 TREE_STATIC (decl) = 1;
2030 TREE_USED (decl) = 1;
2031 DECL_ARTIFICIAL (decl) = 1;
2032 DECL_NO_INSTRUMENT_FUNCTION_ENTRY_EXIT (decl) = 1;
2033 DECL_SAVED_TREE (decl) = body;
2034 if (!targetm.have_ctors_dtors)
2036 TREE_PUBLIC (decl) = 1;
2037 DECL_PRESERVE_P (decl) = 1;
2039 DECL_UNINLINABLE (decl) = 1;
2041 DECL_INITIAL (decl) = make_node (BLOCK);
2042 TREE_USED (DECL_INITIAL (decl)) = 1;
2044 DECL_SOURCE_LOCATION (decl) = input_location;
2045 cfun->function_end_locus = input_location;
2050 DECL_STATIC_CONSTRUCTOR (decl) = 1;
2051 decl_init_priority_insert (decl, priority);
2054 DECL_STATIC_DESTRUCTOR (decl) = 1;
2055 decl_fini_priority_insert (decl, priority);
2061 gimplify_function_tree (decl);
2063 cgraph_add_new_function (decl, false);
2064 cgraph_mark_needed_node (cgraph_node (decl));
2071 cgraph_dump_file = dump_begin (TDI_cgraph, NULL);
2074 /* The edges representing the callers of the NEW_VERSION node were
2075 fixed by cgraph_function_versioning (), now the call_expr in their
2076 respective tree code should be updated to call the NEW_VERSION. */
2079 update_call_expr (struct cgraph_node *new_version)
2081 struct cgraph_edge *e;
2083 gcc_assert (new_version);
2085 /* Update the call expr on the edges to call the new version. */
2086 for (e = new_version->callers; e; e = e->next_caller)
2088 struct function *inner_function = DECL_STRUCT_FUNCTION (e->caller->decl);
2089 gimple_call_set_fndecl (e->call_stmt, new_version->decl);
2090 maybe_clean_eh_stmt_fn (inner_function, e->call_stmt);
2095 /* Create a new cgraph node which is the new version of
2096 OLD_VERSION node. REDIRECT_CALLERS holds the callers
2097 edges which should be redirected to point to
2098 NEW_VERSION. ALL the callees edges of OLD_VERSION
2099 are cloned to the new version node. Return the new
2102 static struct cgraph_node *
2103 cgraph_copy_node_for_versioning (struct cgraph_node *old_version,
2105 VEC(cgraph_edge_p,heap) *redirect_callers)
2107 struct cgraph_node *new_version;
2108 struct cgraph_edge *e;
2109 struct cgraph_edge *next_callee;
2112 gcc_assert (old_version);
2114 new_version = cgraph_node (new_decl);
2116 new_version->analyzed = true;
2117 new_version->local = old_version->local;
2118 new_version->global = old_version->global;
2119 new_version->rtl = new_version->rtl;
2120 new_version->reachable = true;
2121 new_version->count = old_version->count;
2123 /* Clone the old node callees. Recursive calls are
2125 for (e = old_version->callees;e; e=e->next_callee)
2127 cgraph_clone_edge (e, new_version, e->call_stmt,
2128 e->lto_stmt_uid, REG_BR_PROB_BASE,
2130 e->loop_nest, true);
2132 /* Fix recursive calls.
2133 If OLD_VERSION has a recursive call after the
2134 previous edge cloning, the new version will have an edge
2135 pointing to the old version, which is wrong;
2136 Redirect it to point to the new version. */
2137 for (e = new_version->callees ; e; e = next_callee)
2139 next_callee = e->next_callee;
2140 if (e->callee == old_version)
2141 cgraph_redirect_edge_callee (e, new_version);
2146 for (i = 0; VEC_iterate (cgraph_edge_p, redirect_callers, i, e); i++)
2148 /* Redirect calls to the old version node to point to its new
2150 cgraph_redirect_edge_callee (e, new_version);
2156 /* Perform function versioning.
2157 Function versioning includes copying of the tree and
2158 a callgraph update (creating a new cgraph node and updating
2159 its callees and callers).
2161 REDIRECT_CALLERS varray includes the edges to be redirected
2164 TREE_MAP is a mapping of tree nodes we want to replace with
2165 new ones (according to results of prior analysis).
2166 OLD_VERSION_NODE is the node that is versioned.
2167 It returns the new version's cgraph node.
2168 ARGS_TO_SKIP lists arguments to be omitted from functions
2171 struct cgraph_node *
2172 cgraph_function_versioning (struct cgraph_node *old_version_node,
2173 VEC(cgraph_edge_p,heap) *redirect_callers,
2174 VEC (ipa_replace_map_p,gc)* tree_map,
2175 bitmap args_to_skip)
2177 tree old_decl = old_version_node->decl;
2178 struct cgraph_node *new_version_node = NULL;
2181 if (!tree_versionable_function_p (old_decl))
2184 /* Make a new FUNCTION_DECL tree node for the
2187 new_decl = copy_node (old_decl);
2189 new_decl = build_function_decl_skip_args (old_decl, args_to_skip);
2191 /* Create the new version's call-graph node.
2192 and update the edges of the new node. */
2194 cgraph_copy_node_for_versioning (old_version_node, new_decl,
2197 /* Copy the OLD_VERSION_NODE function tree to the new version. */
2198 tree_function_versioning (old_decl, new_decl, tree_map, false, args_to_skip);
2200 /* Update the new version's properties.
2201 Make The new version visible only within this translation unit. Make sure
2202 that is not weak also.
2203 ??? We cannot use COMDAT linkage because there is no
2204 ABI support for this. */
2205 cgraph_make_decl_local (new_version_node->decl);
2206 DECL_VIRTUAL_P (new_version_node->decl) = 0;
2207 new_version_node->local.externally_visible = 0;
2208 new_version_node->local.local = 1;
2209 new_version_node->lowered = true;
2211 /* Update the call_expr on the edges to call the new version node. */
2212 update_call_expr (new_version_node);
2214 cgraph_call_function_insertion_hooks (new_version_node);
2215 return new_version_node;
2218 /* Produce separate function body for inline clones so the offline copy can be
2219 modified without affecting them. */
2220 struct cgraph_node *
2221 save_inline_function_body (struct cgraph_node *node)
2223 struct cgraph_node *first_clone, *n;
2225 gcc_assert (node == cgraph_node (node->decl));
2227 cgraph_lower_function (node);
2229 first_clone = node->clones;
2231 first_clone->decl = copy_node (node->decl);
2232 cgraph_insert_node_to_hashtable (first_clone);
2233 gcc_assert (first_clone == cgraph_node (first_clone->decl));
2234 if (first_clone->next_sibling_clone)
2236 for (n = first_clone->next_sibling_clone; n->next_sibling_clone; n = n->next_sibling_clone)
2237 n->clone_of = first_clone;
2238 n->clone_of = first_clone;
2239 n->next_sibling_clone = first_clone->clones;
2240 if (first_clone->clones)
2241 first_clone->clones->prev_sibling_clone = n;
2242 first_clone->clones = first_clone->next_sibling_clone;
2243 first_clone->next_sibling_clone->prev_sibling_clone = NULL;
2244 first_clone->next_sibling_clone = NULL;
2245 gcc_assert (!first_clone->prev_sibling_clone);
2247 first_clone->clone_of = NULL;
2248 node->clones = NULL;
2250 if (first_clone->clones)
2251 for (n = first_clone->clones; n != first_clone;)
2253 gcc_assert (n->decl == node->decl);
2254 n->decl = first_clone->decl;
2257 else if (n->next_sibling_clone)
2258 n = n->next_sibling_clone;
2261 while (n != first_clone && !n->next_sibling_clone)
2263 if (n != first_clone)
2264 n = n->next_sibling_clone;
2268 /* Copy the OLD_VERSION_NODE function tree to the new version. */
2269 tree_function_versioning (node->decl, first_clone->decl, NULL, true, NULL);
2271 DECL_EXTERNAL (first_clone->decl) = 0;
2272 DECL_COMDAT_GROUP (first_clone->decl) = NULL_TREE;
2273 TREE_PUBLIC (first_clone->decl) = 0;
2274 DECL_COMDAT (first_clone->decl) = 0;
2275 VEC_free (ipa_opt_pass, heap,
2276 first_clone->ipa_transforms_to_apply);
2277 first_clone->ipa_transforms_to_apply = NULL;
2279 #ifdef ENABLE_CHECKING
2280 verify_cgraph_node (first_clone);
2285 /* Given virtual clone, turn it into actual clone. */
2287 cgraph_materialize_clone (struct cgraph_node *node)
2289 bitmap_obstack_initialize (NULL);
2290 /* Copy the OLD_VERSION_NODE function tree to the new version. */
2291 tree_function_versioning (node->clone_of->decl, node->decl,
2292 node->clone.tree_map, true,
2293 node->clone.args_to_skip);
2294 if (cgraph_dump_file)
2296 dump_function_to_file (node->clone_of->decl, cgraph_dump_file, dump_flags);
2297 dump_function_to_file (node->decl, cgraph_dump_file, dump_flags);
2300 /* Function is no longer clone. */
2301 if (node->next_sibling_clone)
2302 node->next_sibling_clone->prev_sibling_clone = node->prev_sibling_clone;
2303 if (node->prev_sibling_clone)
2304 node->prev_sibling_clone->next_sibling_clone = node->next_sibling_clone;
2306 node->clone_of->clones = node->next_sibling_clone;
2307 node->next_sibling_clone = NULL;
2308 node->prev_sibling_clone = NULL;
2309 if (!node->clone_of->analyzed && !node->clone_of->clones)
2310 cgraph_remove_node (node->clone_of);
2311 node->clone_of = NULL;
2312 bitmap_obstack_release (NULL);
2315 /* If necessary, change the function declaration in the call statement
2316 associated with E so that it corresponds to the edge callee. */
2319 cgraph_redirect_edge_call_stmt_to_callee (struct cgraph_edge *e)
2321 tree decl = gimple_call_fndecl (e->call_stmt);
2323 gimple_stmt_iterator gsi;
2325 if (!decl || decl == e->callee->decl
2326 /* Don't update call from same body alias to the real function. */
2327 || cgraph_get_node (decl) == cgraph_get_node (e->callee->decl))
2328 return e->call_stmt;
2330 if (cgraph_dump_file)
2332 fprintf (cgraph_dump_file, "updating call of %s/%i -> %s/%i: ",
2333 cgraph_node_name (e->caller), e->caller->uid,
2334 cgraph_node_name (e->callee), e->callee->uid);
2335 print_gimple_stmt (cgraph_dump_file, e->call_stmt, 0, dump_flags);
2338 if (e->callee->clone.combined_args_to_skip)
2339 new_stmt = gimple_call_copy_skip_args (e->call_stmt,
2340 e->callee->clone.combined_args_to_skip);
2342 new_stmt = e->call_stmt;
2343 if (gimple_vdef (new_stmt)
2344 && TREE_CODE (gimple_vdef (new_stmt)) == SSA_NAME)
2345 SSA_NAME_DEF_STMT (gimple_vdef (new_stmt)) = new_stmt;
2346 gimple_call_set_fndecl (new_stmt, e->callee->decl);
2348 gsi = gsi_for_stmt (e->call_stmt);
2349 gsi_replace (&gsi, new_stmt, true);
2350 update_stmt (new_stmt);
2352 /* Update EH information too, just in case. */
2353 maybe_clean_or_replace_eh_stmt (e->call_stmt, new_stmt);
2355 cgraph_set_call_stmt_including_clones (e->caller, e->call_stmt, new_stmt);
2357 if (cgraph_dump_file)
2359 fprintf (cgraph_dump_file, " updated to:");
2360 print_gimple_stmt (cgraph_dump_file, e->call_stmt, 0, dump_flags);
2365 /* Once all functions from compilation unit are in memory, produce all clones
2366 and update all calls. We might also do this on demand if we don't want to
2367 bring all functions to memory prior compilation, but current WHOPR
2368 implementation does that and it is is bit easier to keep everything right in
2371 cgraph_materialize_all_clones (void)
2373 struct cgraph_node *node;
2374 bool stabilized = false;
2376 if (cgraph_dump_file)
2377 fprintf (cgraph_dump_file, "Materializing clones\n");
2378 #ifdef ENABLE_CHECKING
2382 /* We can also do topological order, but number of iterations should be
2383 bounded by number of IPA passes since single IPA pass is probably not
2384 going to create clones of clones it created itself. */
2388 for (node = cgraph_nodes; node; node = node->next)
2390 if (node->clone_of && node->decl != node->clone_of->decl
2391 && !gimple_has_body_p (node->decl))
2393 if (gimple_has_body_p (node->clone_of->decl))
2395 if (cgraph_dump_file)
2397 fprintf (cgraph_dump_file, "clonning %s to %s\n",
2398 cgraph_node_name (node->clone_of),
2399 cgraph_node_name (node));
2400 if (node->clone.tree_map)
2403 fprintf (cgraph_dump_file, " replace map: ");
2404 for (i = 0; i < VEC_length (ipa_replace_map_p,
2405 node->clone.tree_map);
2408 struct ipa_replace_map *replace_info;
2409 replace_info = VEC_index (ipa_replace_map_p,
2410 node->clone.tree_map,
2412 print_generic_expr (cgraph_dump_file, replace_info->old_tree, 0);
2413 fprintf (cgraph_dump_file, " -> ");
2414 print_generic_expr (cgraph_dump_file, replace_info->new_tree, 0);
2415 fprintf (cgraph_dump_file, "%s%s;",
2416 replace_info->replace_p ? "(replace)":"",
2417 replace_info->ref_p ? "(ref)":"");
2419 fprintf (cgraph_dump_file, "\n");
2421 if (node->clone.args_to_skip)
2423 fprintf (cgraph_dump_file, " args_to_skip: ");
2424 dump_bitmap (cgraph_dump_file, node->clone.args_to_skip);
2426 if (node->clone.args_to_skip)
2428 fprintf (cgraph_dump_file, " combined_args_to_skip:");
2429 dump_bitmap (cgraph_dump_file, node->clone.combined_args_to_skip);
2432 cgraph_materialize_clone (node);
2439 for (node = cgraph_nodes; node; node = node->next)
2440 if (!node->analyzed && node->callees)
2441 cgraph_node_remove_callees (node);
2442 if (cgraph_dump_file)
2443 fprintf (cgraph_dump_file, "Updating call sites\n");
2444 for (node = cgraph_nodes; node; node = node->next)
2445 if (node->analyzed && !node->clone_of
2446 && gimple_has_body_p (node->decl))
2448 struct cgraph_edge *e;
2450 current_function_decl = node->decl;
2451 push_cfun (DECL_STRUCT_FUNCTION (node->decl));
2452 for (e = node->callees; e; e = e->next_callee)
2453 cgraph_redirect_edge_call_stmt_to_callee (e);
2454 gcc_assert (!need_ssa_update_p (cfun));
2456 current_function_decl = NULL;
2457 #ifdef ENABLE_CHECKING
2458 verify_cgraph_node (node);
2461 if (cgraph_dump_file)
2462 fprintf (cgraph_dump_file, "Materialization Call site updates done.\n");
2463 /* All changes to parameters have been performed. In order not to
2464 incorrectly repeat them, we simply dispose of the bitmaps that drive the
2466 for (node = cgraph_nodes; node; node = node->next)
2467 node->clone.combined_args_to_skip = NULL;
2468 #ifdef ENABLE_CHECKING
2471 cgraph_remove_unreachable_nodes (false, cgraph_dump_file);
2474 #include "gt-cgraphunit.h"