1 /* Callgraph based interprocedural optimizations.
2 Copyright (C) 2003, 2004, 2005, 2006, 2007, 2008, 2009, 2010
3 Free Software Foundation, Inc.
4 Contributed by Jan Hubicka
6 This file is part of GCC.
8 GCC is free software; you can redistribute it and/or modify it under
9 the terms of the GNU General Public License as published by the Free
10 Software Foundation; either version 3, or (at your option) any later
13 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
14 WARRANTY; without even the implied warranty of MERCHANTABILITY or
15 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
18 You should have received a copy of the GNU General Public License
19 along with GCC; see the file COPYING3. If not see
20 <http://www.gnu.org/licenses/>. */
22 /* This module implements main driver of compilation process as well as
23 few basic interprocedural optimizers.
25 The main scope of this file is to act as an interface in between
26 tree based frontends and the backend (and middle end)
28 The front-end is supposed to use following functionality:
30 - cgraph_finalize_function
32 This function is called once front-end has parsed whole body of function
33 and it is certain that the function body nor the declaration will change.
35 (There is one exception needed for implementing GCC extern inline
38 - varpool_finalize_variable
40 This function has same behavior as the above but is used for static
43 - cgraph_finalize_compilation_unit
45 This function is called once (source level) compilation unit is finalized
46 and it will no longer change.
48 In the the call-graph construction and local function
49 analysis takes place here. Bodies of unreachable functions are released
50 to conserve memory usage.
52 The function can be called multiple times when multiple source level
53 compilation units are combined (such as in C frontend)
57 In this unit-at-a-time compilation the intra procedural analysis takes
58 place here. In particular the static functions whose address is never
59 taken are marked as local. Backend can then use this information to
60 modify calling conventions, do better inlining or similar optimizations.
62 - cgraph_mark_needed_node
63 - varpool_mark_needed_node
65 When function or variable is referenced by some hidden way the call-graph
66 data structure must be updated accordingly by this function.
67 There should be little need to call this function and all the references
68 should be made explicit to cgraph code. At present these functions are
69 used by C++ frontend to explicitly mark the keyed methods.
71 - analyze_expr callback
73 This function is responsible for lowering tree nodes not understood by
74 generic code into understandable ones or alternatively marking
75 callgraph and varpool nodes referenced by the as needed.
77 ??? On the tree-ssa genericizing should take place here and we will avoid
78 need for these hooks (replacing them by genericizing hook)
80 Analyzing of all functions is deferred
81 to cgraph_finalize_compilation_unit and expansion into cgraph_optimize.
83 In cgraph_finalize_compilation_unit the reachable functions are
84 analyzed. During analysis the call-graph edges from reachable
85 functions are constructed and their destinations are marked as
86 reachable. References to functions and variables are discovered too
87 and variables found to be needed output to the assembly file. Via
88 mark_referenced call in assemble_variable functions referenced by
89 static variables are noticed too.
91 The intra-procedural information is produced and its existence
92 indicated by global_info_ready. Once this flag is set it is impossible
93 to change function from !reachable to reachable and thus
94 assemble_variable no longer call mark_referenced.
96 Finally the call-graph is topologically sorted and all reachable functions
97 that has not been completely inlined or are not external are output.
99 ??? It is possible that reference to function or variable is optimized
100 out. We can not deal with this nicely because topological order is not
101 suitable for it. For tree-ssa we may consider another pass doing
102 optimization and re-discovering reachable functions.
104 ??? Reorganize code so variables are output very last and only if they
105 really has been referenced by produced code, so we catch more cases
106 where reference has been optimized out. */
111 #include "coretypes.h"
115 #include "tree-flow.h"
116 #include "tree-inline.h"
117 #include "langhooks.h"
118 #include "pointer-set.h"
125 #include "diagnostic.h"
126 #include "tree-pretty-print.h"
127 #include "gimple-pretty-print.h"
132 #include "function.h"
133 #include "ipa-prop.h"
135 #include "tree-iterator.h"
136 #include "tree-pass.h"
137 #include "tree-dump.h"
139 #include "coverage.h"
142 static void cgraph_expand_all_functions (void);
143 static void cgraph_mark_functions_to_output (void);
144 static void cgraph_expand_function (struct cgraph_node *);
145 static void cgraph_output_pending_asms (void);
146 static void cgraph_analyze_function (struct cgraph_node *);
148 FILE *cgraph_dump_file;
150 /* A vector of FUNCTION_DECLs declared as static constructors. */
151 static GTY (()) VEC(tree, gc) *static_ctors;
152 /* A vector of FUNCTION_DECLs declared as static destructors. */
153 static GTY (()) VEC(tree, gc) *static_dtors;
155 /* Used for vtable lookup in thunk adjusting. */
156 static GTY (()) tree vtable_entry_type;
158 /* When target does not have ctors and dtors, we call all constructor
159 and destructor by special initialization/destruction function
160 recognized by collect2.
162 When we are going to build this function, collect all constructors and
163 destructors and turn them into normal functions. */
166 record_cdtor_fn (tree fndecl)
168 struct cgraph_node *node;
169 if (targetm.have_ctors_dtors
170 || (!DECL_STATIC_CONSTRUCTOR (fndecl)
171 && !DECL_STATIC_DESTRUCTOR (fndecl)))
174 if (DECL_STATIC_CONSTRUCTOR (fndecl))
176 VEC_safe_push (tree, gc, static_ctors, fndecl);
177 DECL_STATIC_CONSTRUCTOR (fndecl) = 0;
179 if (DECL_STATIC_DESTRUCTOR (fndecl))
181 VEC_safe_push (tree, gc, static_dtors, fndecl);
182 DECL_STATIC_DESTRUCTOR (fndecl) = 0;
184 node = cgraph_node (fndecl);
185 node->local.disregard_inline_limits = 1;
186 cgraph_mark_reachable_node (node);
189 /* Define global constructors/destructor functions for the CDTORS, of
190 which they are LEN. The CDTORS are sorted by initialization
191 priority. If CTOR_P is true, these are constructors; otherwise,
192 they are destructors. */
195 build_cdtor (bool ctor_p, tree *cdtors, size_t len)
204 priority_type priority;
208 /* Find the next batch of constructors/destructors with the same
209 initialization priority. */
214 p = ctor_p ? DECL_INIT_PRIORITY (fn) : DECL_FINI_PRIORITY (fn);
217 else if (p != priority)
219 append_to_statement_list (build_function_call_expr (UNKNOWN_LOCATION,
225 gcc_assert (body != NULL_TREE);
226 /* Generate a function to call all the function of like
228 cgraph_build_static_cdtor (ctor_p ? 'I' : 'D', body, priority);
232 /* Comparison function for qsort. P1 and P2 are actually of type
233 "tree *" and point to static constructors. DECL_INIT_PRIORITY is
234 used to determine the sort order. */
237 compare_ctor (const void *p1, const void *p2)
244 f1 = *(const tree *)p1;
245 f2 = *(const tree *)p2;
246 priority1 = DECL_INIT_PRIORITY (f1);
247 priority2 = DECL_INIT_PRIORITY (f2);
249 if (priority1 < priority2)
251 else if (priority1 > priority2)
254 /* Ensure a stable sort. */
255 return (const tree *)p1 - (const tree *)p2;
258 /* Comparison function for qsort. P1 and P2 are actually of type
259 "tree *" and point to static destructors. DECL_FINI_PRIORITY is
260 used to determine the sort order. */
263 compare_dtor (const void *p1, const void *p2)
270 f1 = *(const tree *)p1;
271 f2 = *(const tree *)p2;
272 priority1 = DECL_FINI_PRIORITY (f1);
273 priority2 = DECL_FINI_PRIORITY (f2);
275 if (priority1 < priority2)
277 else if (priority1 > priority2)
280 /* Ensure a stable sort. */
281 return (const tree *)p1 - (const tree *)p2;
284 /* Generate functions to call static constructors and destructors
285 for targets that do not support .ctors/.dtors sections. These
286 functions have magic names which are detected by collect2. */
289 cgraph_build_cdtor_fns (void)
291 if (!VEC_empty (tree, static_ctors))
293 gcc_assert (!targetm.have_ctors_dtors);
294 qsort (VEC_address (tree, static_ctors),
295 VEC_length (tree, static_ctors),
298 build_cdtor (/*ctor_p=*/true,
299 VEC_address (tree, static_ctors),
300 VEC_length (tree, static_ctors));
301 VEC_truncate (tree, static_ctors, 0);
304 if (!VEC_empty (tree, static_dtors))
306 gcc_assert (!targetm.have_ctors_dtors);
307 qsort (VEC_address (tree, static_dtors),
308 VEC_length (tree, static_dtors),
311 build_cdtor (/*ctor_p=*/false,
312 VEC_address (tree, static_dtors),
313 VEC_length (tree, static_dtors));
314 VEC_truncate (tree, static_dtors, 0);
318 /* Determine if function DECL is needed. That is, visible to something
319 either outside this translation unit, something magic in the system
323 cgraph_decide_is_function_needed (struct cgraph_node *node, tree decl)
325 /* If the user told us it is used, then it must be so. */
326 if (node->local.externally_visible)
329 /* ??? If the assembler name is set by hand, it is possible to assemble
330 the name later after finalizing the function and the fact is noticed
331 in assemble_name then. This is arguably a bug. */
332 if (DECL_ASSEMBLER_NAME_SET_P (decl)
333 && TREE_SYMBOL_REFERENCED (DECL_ASSEMBLER_NAME (decl)))
336 /* With -fkeep-inline-functions we are keeping all inline functions except
337 for extern inline ones. */
338 if (flag_keep_inline_functions
339 && DECL_DECLARED_INLINE_P (decl)
340 && !DECL_EXTERNAL (decl)
341 && !lookup_attribute ("always_inline", DECL_ATTRIBUTES (decl)))
344 /* If we decided it was needed before, but at the time we didn't have
345 the body of the function available, then it's still needed. We have
346 to go back and re-check its dependencies now. */
350 /* Externally visible functions must be output. The exception is
351 COMDAT functions that must be output only when they are needed.
353 When not optimizing, also output the static functions. (see
354 PR24561), but don't do so for always_inline functions, functions
355 declared inline and nested functions. These were optimized out
356 in the original implementation and it is unclear whether we want
357 to change the behavior here. */
358 if (((TREE_PUBLIC (decl)
360 && !node->local.disregard_inline_limits
361 && !DECL_DECLARED_INLINE_P (decl)
362 && !(DECL_CONTEXT (decl)
363 && TREE_CODE (DECL_CONTEXT (decl)) == FUNCTION_DECL)))
364 && !flag_whole_program
367 && !DECL_COMDAT (decl) && !DECL_EXTERNAL (decl))
370 /* Constructors and destructors are reachable from the runtime by
372 if (DECL_STATIC_CONSTRUCTOR (decl) || DECL_STATIC_DESTRUCTOR (decl))
378 /* Process CGRAPH_NEW_FUNCTIONS and perform actions necessary to add these
379 functions into callgraph in a way so they look like ordinary reachable
380 functions inserted into callgraph already at construction time. */
383 cgraph_process_new_functions (void)
387 struct cgraph_node *node;
389 varpool_analyze_pending_decls ();
390 /* Note that this queue may grow as its being processed, as the new
391 functions may generate new ones. */
392 while (cgraph_new_nodes)
394 node = cgraph_new_nodes;
396 cgraph_new_nodes = cgraph_new_nodes->next_needed;
397 switch (cgraph_state)
399 case CGRAPH_STATE_CONSTRUCTION:
400 /* At construction time we just need to finalize function and move
401 it into reachable functions list. */
403 node->next_needed = NULL;
404 cgraph_finalize_function (fndecl, false);
405 cgraph_mark_reachable_node (node);
409 case CGRAPH_STATE_IPA:
410 case CGRAPH_STATE_IPA_SSA:
411 /* When IPA optimization already started, do all essential
412 transformations that has been already performed on the whole
413 cgraph but not on this function. */
415 gimple_register_cfg_hooks ();
417 cgraph_analyze_function (node);
418 push_cfun (DECL_STRUCT_FUNCTION (fndecl));
419 current_function_decl = fndecl;
420 compute_inline_parameters (node);
421 if ((cgraph_state == CGRAPH_STATE_IPA_SSA
422 && !gimple_in_ssa_p (DECL_STRUCT_FUNCTION (fndecl)))
423 /* When not optimizing, be sure we run early local passes anyway
426 execute_pass_list (pass_early_local_passes.pass.sub);
427 free_dominance_info (CDI_POST_DOMINATORS);
428 free_dominance_info (CDI_DOMINATORS);
430 current_function_decl = NULL;
433 case CGRAPH_STATE_EXPANSION:
434 /* Functions created during expansion shall be compiled
437 cgraph_expand_function (node);
444 cgraph_call_function_insertion_hooks (node);
445 varpool_analyze_pending_decls ();
450 /* As an GCC extension we allow redefinition of the function. The
451 semantics when both copies of bodies differ is not well defined.
452 We replace the old body with new body so in unit at a time mode
453 we always use new body, while in normal mode we may end up with
454 old body inlined into some functions and new body expanded and
457 ??? It may make more sense to use one body for inlining and other
458 body for expanding the function but this is difficult to do. */
461 cgraph_reset_node (struct cgraph_node *node)
463 /* If node->process is set, then we have already begun whole-unit analysis.
464 This is *not* testing for whether we've already emitted the function.
465 That case can be sort-of legitimately seen with real function redefinition
466 errors. I would argue that the front end should never present us with
467 such a case, but don't enforce that for now. */
468 gcc_assert (!node->process);
470 /* Reset our data structures so we can analyze the function again. */
471 memset (&node->local, 0, sizeof (node->local));
472 memset (&node->global, 0, sizeof (node->global));
473 memset (&node->rtl, 0, sizeof (node->rtl));
474 node->analyzed = false;
475 node->local.redefined_extern_inline = true;
476 node->local.finalized = false;
478 cgraph_node_remove_callees (node);
480 /* We may need to re-queue the node for assembling in case
481 we already proceeded it and ignored as not needed or got
482 a re-declaration in IMA mode. */
485 struct cgraph_node *n;
487 for (n = cgraph_nodes_queue; n; n = n->next_needed)
496 cgraph_lower_function (struct cgraph_node *node)
502 lower_nested_functions (node->decl);
503 gcc_assert (!node->nested);
505 tree_lowering_passes (node->decl);
506 node->lowered = true;
509 /* DECL has been parsed. Take it, queue it, compile it at the whim of the
510 logic in effect. If NESTED is true, then our caller cannot stand to have
511 the garbage collector run at the moment. We would need to either create
512 a new GC context, or just not compile right now. */
515 cgraph_finalize_function (tree decl, bool nested)
517 struct cgraph_node *node = cgraph_node (decl);
519 if (node->local.finalized)
520 cgraph_reset_node (node);
522 node->pid = cgraph_max_pid ++;
523 notice_global_symbol (decl);
524 node->local.finalized = true;
525 node->lowered = DECL_STRUCT_FUNCTION (decl)->cfg != NULL;
526 node->finalized_by_frontend = true;
527 record_cdtor_fn (node->decl);
529 if (cgraph_decide_is_function_needed (node, decl))
530 cgraph_mark_needed_node (node);
532 /* Since we reclaim unreachable nodes at the end of every language
533 level unit, we need to be conservative about possible entry points
535 if ((TREE_PUBLIC (decl) && !DECL_COMDAT (decl) && !DECL_EXTERNAL (decl)))
536 cgraph_mark_reachable_node (node);
538 /* If we've not yet emitted decl, tell the debug info about it. */
539 if (!TREE_ASM_WRITTEN (decl))
540 (*debug_hooks->deferred_inline_function) (decl);
542 /* Possibly warn about unused parameters. */
543 if (warn_unused_parameter)
544 do_warn_unused_parameter (decl);
550 /* C99 extern inline keywords allow changing of declaration after function
551 has been finalized. We need to re-decide if we want to mark the function as
555 cgraph_mark_if_needed (tree decl)
557 struct cgraph_node *node = cgraph_node (decl);
558 if (node->local.finalized && cgraph_decide_is_function_needed (node, decl))
559 cgraph_mark_needed_node (node);
562 #ifdef ENABLE_CHECKING
563 /* Return TRUE if NODE2 is equivalent to NODE or its clone. */
565 clone_of_p (struct cgraph_node *node, struct cgraph_node *node2)
567 while (node != node2 && node2)
568 node2 = node2->clone_of;
569 return node2 != NULL;
573 /* Verify cgraph nodes of given cgraph node. */
575 verify_cgraph_node (struct cgraph_node *node)
577 struct cgraph_edge *e;
578 struct function *this_cfun = DECL_STRUCT_FUNCTION (node->decl);
579 struct function *saved_cfun = cfun;
580 basic_block this_block;
581 gimple_stmt_iterator gsi;
582 bool error_found = false;
587 timevar_push (TV_CGRAPH_VERIFY);
588 /* debug_generic_stmt needs correct cfun */
589 set_cfun (this_cfun);
590 for (e = node->callees; e; e = e->next_callee)
593 error ("aux field set for edge %s->%s",
594 identifier_to_locale (cgraph_node_name (e->caller)),
595 identifier_to_locale (cgraph_node_name (e->callee)));
600 error ("Execution count is negative");
603 if (node->global.inlined_to && node->local.externally_visible)
605 error ("Externally visible inline clone");
608 if (node->global.inlined_to && node->address_taken)
610 error ("Inline clone with address taken");
613 if (node->global.inlined_to && node->needed)
615 error ("Inline clone is needed");
618 for (e = node->indirect_calls; e; e = e->next_callee)
622 error ("aux field set for indirect edge from %s",
623 identifier_to_locale (cgraph_node_name (e->caller)));
626 if (!e->indirect_unknown_callee
627 || !e->indirect_info)
629 error ("An indirect edge from %s is not marked as indirect or has "
630 "associated indirect_info, the corresponding statement is: ",
631 identifier_to_locale (cgraph_node_name (e->caller)));
632 debug_gimple_stmt (e->call_stmt);
636 for (e = node->callers; e; e = e->next_caller)
640 error ("caller edge count is negative");
643 if (e->frequency < 0)
645 error ("caller edge frequency is negative");
648 if (e->frequency > CGRAPH_FREQ_MAX)
650 error ("caller edge frequency is too large");
653 if (gimple_has_body_p (e->caller->decl)
654 && !e->caller->global.inlined_to
656 != compute_call_stmt_bb_frequency (e->caller->decl,
657 gimple_bb (e->call_stmt))))
659 error ("caller edge frequency %i does not match BB freqency %i",
661 compute_call_stmt_bb_frequency (e->caller->decl,
662 gimple_bb (e->call_stmt)));
665 if (!e->inline_failed)
667 if (node->global.inlined_to
668 != (e->caller->global.inlined_to
669 ? e->caller->global.inlined_to : e->caller))
671 error ("inlined_to pointer is wrong");
674 if (node->callers->next_caller)
676 error ("multiple inline callers");
681 if (node->global.inlined_to)
683 error ("inlined_to pointer set for noninline callers");
687 if (!node->callers && node->global.inlined_to)
689 error ("inlined_to pointer is set but no predecessors found");
692 if (node->global.inlined_to == node)
694 error ("inlined_to pointer refers to itself");
698 if (!cgraph_node (node->decl))
700 error ("node not found in cgraph_hash");
706 struct cgraph_node *n;
707 for (n = node->clone_of->clones; n; n = n->next_sibling_clone)
712 error ("node has wrong clone_of");
718 struct cgraph_node *n;
719 for (n = node->clones; n; n = n->next_sibling_clone)
720 if (n->clone_of != node)
724 error ("node has wrong clone list");
728 if ((node->prev_sibling_clone || node->next_sibling_clone) && !node->clone_of)
730 error ("node is in clone list but it is not clone");
733 if (!node->prev_sibling_clone && node->clone_of && node->clone_of->clones != node)
735 error ("node has wrong prev_clone pointer");
738 if (node->prev_sibling_clone && node->prev_sibling_clone->next_sibling_clone != node)
740 error ("double linked list of clones corrupted");
743 if (node->same_comdat_group)
745 struct cgraph_node *n = node->same_comdat_group;
747 if (!DECL_ONE_ONLY (node->decl))
749 error ("non-DECL_ONE_ONLY node in a same_comdat_group list");
754 error ("node is alone in a comdat group");
759 if (!n->same_comdat_group)
761 error ("same_comdat_group is not a circular list");
765 n = n->same_comdat_group;
770 if (node->analyzed && gimple_has_body_p (node->decl)
771 && !TREE_ASM_WRITTEN (node->decl)
772 && (!DECL_EXTERNAL (node->decl) || node->global.inlined_to)
777 /* The nodes we're interested in are never shared, so walk
778 the tree ignoring duplicates. */
779 struct pointer_set_t *visited_nodes = pointer_set_create ();
780 /* Reach the trees by walking over the CFG, and note the
781 enclosing basic-blocks in the call edges. */
782 FOR_EACH_BB_FN (this_block, this_cfun)
783 for (gsi = gsi_start_bb (this_block);
787 gimple stmt = gsi_stmt (gsi);
788 if (is_gimple_call (stmt))
790 struct cgraph_edge *e = cgraph_edge (node, stmt);
791 tree decl = gimple_call_fndecl (stmt);
796 error ("shared call_stmt:");
797 debug_gimple_stmt (stmt);
800 if (!e->indirect_unknown_callee)
802 if (e->callee->same_body_alias)
804 error ("edge points to same body alias:");
805 debug_tree (e->callee->decl);
808 #ifdef ENABLE_CHECKING
809 else if (!e->callee->global.inlined_to
811 && cgraph_get_node (decl)
812 && (e->callee->former_clone_of
813 != cgraph_get_node (decl)->decl)
814 && !clone_of_p (cgraph_node (decl),
817 error ("edge points to wrong declaration:");
818 debug_tree (e->callee->decl);
819 fprintf (stderr," Instead of:");
827 error ("an indirect edge with unknown callee "
828 "corresponding to a call_stmt with "
829 "a known declaration:");
831 debug_gimple_stmt (e->call_stmt);
837 error ("missing callgraph edge for call stmt:");
838 debug_gimple_stmt (stmt);
843 pointer_set_destroy (visited_nodes);
846 /* No CFG available?! */
849 for (e = node->callees; e; e = e->next_callee)
853 error ("edge %s->%s has no corresponding call_stmt",
854 identifier_to_locale (cgraph_node_name (e->caller)),
855 identifier_to_locale (cgraph_node_name (e->callee)));
856 debug_gimple_stmt (e->call_stmt);
861 for (e = node->indirect_calls; e; e = e->next_callee)
865 error ("an indirect edge from %s has no corresponding call_stmt",
866 identifier_to_locale (cgraph_node_name (e->caller)));
867 debug_gimple_stmt (e->call_stmt);
875 dump_cgraph_node (stderr, node);
876 internal_error ("verify_cgraph_node failed");
878 set_cfun (saved_cfun);
879 timevar_pop (TV_CGRAPH_VERIFY);
882 /* Verify whole cgraph structure. */
886 struct cgraph_node *node;
891 for (node = cgraph_nodes; node; node = node->next)
892 verify_cgraph_node (node);
895 /* Output all asm statements we have stored up to be output. */
898 cgraph_output_pending_asms (void)
900 struct cgraph_asm_node *can;
905 for (can = cgraph_asm_nodes; can; can = can->next)
906 assemble_asm (can->asm_str);
907 cgraph_asm_nodes = NULL;
910 /* Analyze the function scheduled to be output. */
912 cgraph_analyze_function (struct cgraph_node *node)
914 tree save = current_function_decl;
915 tree decl = node->decl;
917 current_function_decl = decl;
918 push_cfun (DECL_STRUCT_FUNCTION (decl));
920 assign_assembler_name_if_neeeded (node->decl);
922 /* Make sure to gimplify bodies only once. During analyzing a
923 function we lower it, which will require gimplified nested
924 functions, so we can end up here with an already gimplified
926 if (!gimple_body (decl))
927 gimplify_function_tree (decl);
928 dump_function (TDI_generic, decl);
930 cgraph_lower_function (node);
931 node->analyzed = true;
934 current_function_decl = save;
937 /* Look for externally_visible and used attributes and mark cgraph nodes
940 We cannot mark the nodes at the point the attributes are processed (in
941 handle_*_attribute) because the copy of the declarations available at that
942 point may not be canonical. For example, in:
945 void f() __attribute__((used));
947 the declaration we see in handle_used_attribute will be the second
948 declaration -- but the front end will subsequently merge that declaration
949 with the original declaration and discard the second declaration.
951 Furthermore, we can't mark these nodes in cgraph_finalize_function because:
954 void f() __attribute__((externally_visible));
958 So, we walk the nodes at the end of the translation unit, applying the
959 attributes at that point. */
962 process_function_and_variable_attributes (struct cgraph_node *first,
963 struct varpool_node *first_var)
965 struct cgraph_node *node;
966 struct varpool_node *vnode;
968 for (node = cgraph_nodes; node != first; node = node->next)
970 tree decl = node->decl;
971 if (DECL_PRESERVE_P (decl))
972 cgraph_mark_needed_node (node);
973 if (lookup_attribute ("externally_visible", DECL_ATTRIBUTES (decl)))
975 if (! TREE_PUBLIC (node->decl))
976 warning_at (DECL_SOURCE_LOCATION (node->decl), OPT_Wattributes,
977 "%<externally_visible%>"
978 " attribute have effect only on public objects");
979 else if (node->local.finalized)
980 cgraph_mark_needed_node (node);
983 for (vnode = varpool_nodes; vnode != first_var; vnode = vnode->next)
985 tree decl = vnode->decl;
986 if (DECL_PRESERVE_P (decl))
988 vnode->force_output = true;
989 if (vnode->finalized)
990 varpool_mark_needed_node (vnode);
992 if (lookup_attribute ("externally_visible", DECL_ATTRIBUTES (decl)))
994 if (! TREE_PUBLIC (vnode->decl))
995 warning_at (DECL_SOURCE_LOCATION (vnode->decl), OPT_Wattributes,
996 "%<externally_visible%>"
997 " attribute have effect only on public objects");
998 else if (vnode->finalized)
999 varpool_mark_needed_node (vnode);
1004 /* Process CGRAPH_NODES_NEEDED queue, analyze each function (and transitively
1005 each reachable functions) and build cgraph.
1006 The function can be called multiple times after inserting new nodes
1007 into beginning of queue. Just the new part of queue is re-scanned then. */
1010 cgraph_analyze_functions (void)
1012 /* Keep track of already processed nodes when called multiple times for
1013 intermodule optimization. */
1014 static struct cgraph_node *first_analyzed;
1015 struct cgraph_node *first_processed = first_analyzed;
1016 static struct varpool_node *first_analyzed_var;
1017 struct cgraph_node *node, *next;
1019 process_function_and_variable_attributes (first_processed,
1020 first_analyzed_var);
1021 first_processed = cgraph_nodes;
1022 first_analyzed_var = varpool_nodes;
1023 varpool_analyze_pending_decls ();
1024 if (cgraph_dump_file)
1026 fprintf (cgraph_dump_file, "Initial entry points:");
1027 for (node = cgraph_nodes; node != first_analyzed; node = node->next)
1029 fprintf (cgraph_dump_file, " %s", cgraph_node_name (node));
1030 fprintf (cgraph_dump_file, "\n");
1032 cgraph_process_new_functions ();
1034 /* Propagate reachability flag and lower representation of all reachable
1035 functions. In the future, lowering will introduce new functions and
1036 new entry points on the way (by template instantiation and virtual
1037 method table generation for instance). */
1038 while (cgraph_nodes_queue)
1040 struct cgraph_edge *edge;
1041 tree decl = cgraph_nodes_queue->decl;
1043 node = cgraph_nodes_queue;
1044 cgraph_nodes_queue = cgraph_nodes_queue->next_needed;
1045 node->next_needed = NULL;
1047 /* ??? It is possible to create extern inline function and later using
1048 weak alias attribute to kill its body. See
1049 gcc.c-torture/compile/20011119-1.c */
1050 if (!DECL_STRUCT_FUNCTION (decl))
1052 cgraph_reset_node (node);
1056 if (!node->analyzed)
1057 cgraph_analyze_function (node);
1059 for (edge = node->callees; edge; edge = edge->next_callee)
1060 if (!edge->callee->reachable)
1061 cgraph_mark_reachable_node (edge->callee);
1063 if (node->same_comdat_group)
1065 for (next = node->same_comdat_group;
1067 next = next->same_comdat_group)
1068 cgraph_mark_reachable_node (next);
1071 /* If decl is a clone of an abstract function, mark that abstract
1072 function so that we don't release its body. The DECL_INITIAL() of that
1073 abstract function declaration will be later needed to output debug info. */
1074 if (DECL_ABSTRACT_ORIGIN (decl))
1076 struct cgraph_node *origin_node = cgraph_node (DECL_ABSTRACT_ORIGIN (decl));
1077 origin_node->abstract_and_needed = true;
1080 /* We finalize local static variables during constructing callgraph
1081 edges. Process their attributes too. */
1082 process_function_and_variable_attributes (first_processed,
1083 first_analyzed_var);
1084 first_processed = cgraph_nodes;
1085 first_analyzed_var = varpool_nodes;
1086 varpool_analyze_pending_decls ();
1087 cgraph_process_new_functions ();
1090 /* Collect entry points to the unit. */
1091 if (cgraph_dump_file)
1093 fprintf (cgraph_dump_file, "Unit entry points:");
1094 for (node = cgraph_nodes; node != first_analyzed; node = node->next)
1096 fprintf (cgraph_dump_file, " %s", cgraph_node_name (node));
1097 fprintf (cgraph_dump_file, "\n\nInitial ");
1098 dump_cgraph (cgraph_dump_file);
1101 if (cgraph_dump_file)
1102 fprintf (cgraph_dump_file, "\nReclaiming functions:");
1104 for (node = cgraph_nodes; node != first_analyzed; node = next)
1106 tree decl = node->decl;
1109 if (node->local.finalized && !gimple_has_body_p (decl))
1110 cgraph_reset_node (node);
1112 if (!node->reachable && gimple_has_body_p (decl))
1114 if (cgraph_dump_file)
1115 fprintf (cgraph_dump_file, " %s", cgraph_node_name (node));
1116 cgraph_remove_node (node);
1120 node->next_needed = NULL;
1121 gcc_assert (!node->local.finalized || gimple_has_body_p (decl));
1122 gcc_assert (node->analyzed == node->local.finalized);
1124 if (cgraph_dump_file)
1126 fprintf (cgraph_dump_file, "\n\nReclaimed ");
1127 dump_cgraph (cgraph_dump_file);
1129 first_analyzed = cgraph_nodes;
1134 /* Analyze the whole compilation unit once it is parsed completely. */
1137 cgraph_finalize_compilation_unit (void)
1139 timevar_push (TV_CGRAPH);
1141 /* Do not skip analyzing the functions if there were errors, we
1142 miss diagnostics for following functions otherwise. */
1144 /* Emit size functions we didn't inline. */
1145 finalize_size_functions ();
1147 /* Call functions declared with the "constructor" or "destructor"
1149 cgraph_build_cdtor_fns ();
1151 /* Mark alias targets necessary and emit diagnostics. */
1152 finish_aliases_1 ();
1156 fprintf (stderr, "\nAnalyzing compilation unit\n");
1160 /* Gimplify and lower all functions, compute reachability and
1161 remove unreachable nodes. */
1162 cgraph_analyze_functions ();
1164 /* Mark alias targets necessary and emit diagnostics. */
1165 finish_aliases_1 ();
1167 /* Gimplify and lower thunks. */
1168 cgraph_analyze_functions ();
1170 /* Finally drive the pass manager. */
1173 timevar_pop (TV_CGRAPH);
1177 /* Figure out what functions we want to assemble. */
1180 cgraph_mark_functions_to_output (void)
1182 struct cgraph_node *node;
1183 #ifdef ENABLE_CHECKING
1184 bool check_same_comdat_groups = false;
1186 for (node = cgraph_nodes; node; node = node->next)
1187 gcc_assert (!node->process);
1190 for (node = cgraph_nodes; node; node = node->next)
1192 tree decl = node->decl;
1193 struct cgraph_edge *e;
1195 gcc_assert (!node->process || node->same_comdat_group);
1199 for (e = node->callers; e; e = e->next_caller)
1200 if (e->inline_failed)
1203 /* We need to output all local functions that are used and not
1204 always inlined, as well as those that are reachable from
1205 outside the current compilation unit. */
1207 && !node->global.inlined_to
1208 && (node->needed || node->reachable_from_other_partition
1209 || node->address_taken
1210 || (e && node->reachable))
1211 && !TREE_ASM_WRITTEN (decl)
1212 && !DECL_EXTERNAL (decl))
1215 if (node->same_comdat_group)
1217 struct cgraph_node *next;
1218 for (next = node->same_comdat_group;
1220 next = next->same_comdat_group)
1224 else if (node->same_comdat_group)
1226 #ifdef ENABLE_CHECKING
1227 check_same_comdat_groups = true;
1232 /* We should've reclaimed all functions that are not needed. */
1233 #ifdef ENABLE_CHECKING
1234 if (!node->global.inlined_to
1235 && gimple_has_body_p (decl)
1236 /* FIXME: in ltrans unit when offline copy is outside partition but inline copies
1237 are inside partition, we can end up not removing the body since we no longer
1238 have analyzed node pointing to it. */
1239 && !node->in_other_partition
1240 && !DECL_EXTERNAL (decl))
1242 dump_cgraph_node (stderr, node);
1243 internal_error ("failed to reclaim unneeded function");
1246 gcc_assert (node->global.inlined_to
1247 || !gimple_has_body_p (decl)
1248 || node->in_other_partition
1249 || DECL_EXTERNAL (decl));
1254 #ifdef ENABLE_CHECKING
1255 if (check_same_comdat_groups)
1256 for (node = cgraph_nodes; node; node = node->next)
1257 if (node->same_comdat_group && !node->process)
1259 tree decl = node->decl;
1260 if (!node->global.inlined_to
1261 && gimple_has_body_p (decl)
1262 /* FIXME: in ltrans unit when offline copy is outside partition but inline copies
1263 are inside partition, we can end up not removing the body since we no longer
1264 have analyzed node pointing to it. */
1265 && !node->in_other_partition
1266 && !DECL_EXTERNAL (decl))
1268 dump_cgraph_node (stderr, node);
1269 internal_error ("failed to reclaim unneeded function");
1275 /* DECL is FUNCTION_DECL. Initialize datastructures so DECL is a function
1276 in lowered gimple form.
1278 Set current_function_decl and cfun to newly constructed empty function body.
1279 return basic block in the function body. */
1282 init_lowered_empty_function (tree decl)
1286 current_function_decl = decl;
1287 allocate_struct_function (decl, false);
1288 gimple_register_cfg_hooks ();
1289 init_empty_tree_cfg ();
1290 init_tree_ssa (cfun);
1291 init_ssa_operands ();
1292 cfun->gimple_df->in_ssa_p = true;
1293 DECL_INITIAL (decl) = make_node (BLOCK);
1295 DECL_SAVED_TREE (decl) = error_mark_node;
1296 cfun->curr_properties |=
1297 (PROP_gimple_lcf | PROP_gimple_leh | PROP_cfg | PROP_referenced_vars |
1300 /* Create BB for body of the function and connect it properly. */
1301 bb = create_basic_block (NULL, (void *) 0, ENTRY_BLOCK_PTR);
1302 make_edge (ENTRY_BLOCK_PTR, bb, 0);
1303 make_edge (bb, EXIT_BLOCK_PTR, 0);
1308 /* Adjust PTR by the constant FIXED_OFFSET, and by the vtable
1309 offset indicated by VIRTUAL_OFFSET, if that is
1310 non-null. THIS_ADJUSTING is nonzero for a this adjusting thunk and
1311 zero for a result adjusting thunk. */
1314 thunk_adjust (gimple_stmt_iterator * bsi,
1315 tree ptr, bool this_adjusting,
1316 HOST_WIDE_INT fixed_offset, tree virtual_offset)
1322 && fixed_offset != 0)
1324 stmt = gimple_build_assign (ptr,
1325 fold_build2_loc (input_location,
1327 TREE_TYPE (ptr), ptr,
1328 size_int (fixed_offset)));
1329 gsi_insert_after (bsi, stmt, GSI_NEW_STMT);
1332 /* If there's a virtual offset, look up that value in the vtable and
1333 adjust the pointer again. */
1341 if (!vtable_entry_type)
1343 tree vfunc_type = make_node (FUNCTION_TYPE);
1344 TREE_TYPE (vfunc_type) = integer_type_node;
1345 TYPE_ARG_TYPES (vfunc_type) = NULL_TREE;
1346 layout_type (vfunc_type);
1348 vtable_entry_type = build_pointer_type (vfunc_type);
1352 create_tmp_var (build_pointer_type
1353 (build_pointer_type (vtable_entry_type)), "vptr");
1355 /* The vptr is always at offset zero in the object. */
1356 stmt = gimple_build_assign (vtabletmp,
1357 build1 (NOP_EXPR, TREE_TYPE (vtabletmp),
1359 gsi_insert_after (bsi, stmt, GSI_NEW_STMT);
1360 mark_symbols_for_renaming (stmt);
1361 find_referenced_vars_in (stmt);
1363 /* Form the vtable address. */
1364 vtabletmp2 = create_tmp_var (TREE_TYPE (TREE_TYPE (vtabletmp)),
1366 stmt = gimple_build_assign (vtabletmp2,
1367 build1 (INDIRECT_REF,
1368 TREE_TYPE (vtabletmp2), vtabletmp));
1369 gsi_insert_after (bsi, stmt, GSI_NEW_STMT);
1370 mark_symbols_for_renaming (stmt);
1371 find_referenced_vars_in (stmt);
1373 /* Find the entry with the vcall offset. */
1374 stmt = gimple_build_assign (vtabletmp2,
1375 fold_build2_loc (input_location,
1377 TREE_TYPE (vtabletmp2),
1379 fold_convert (sizetype,
1381 gsi_insert_after (bsi, stmt, GSI_NEW_STMT);
1383 /* Get the offset itself. */
1384 vtabletmp3 = create_tmp_var (TREE_TYPE (TREE_TYPE (vtabletmp2)),
1386 stmt = gimple_build_assign (vtabletmp3,
1387 build1 (INDIRECT_REF,
1388 TREE_TYPE (vtabletmp3),
1390 gsi_insert_after (bsi, stmt, GSI_NEW_STMT);
1391 mark_symbols_for_renaming (stmt);
1392 find_referenced_vars_in (stmt);
1394 /* Cast to sizetype. */
1395 offsettmp = create_tmp_var (sizetype, "offset");
1396 stmt = gimple_build_assign (offsettmp, fold_convert (sizetype, vtabletmp3));
1397 gsi_insert_after (bsi, stmt, GSI_NEW_STMT);
1398 mark_symbols_for_renaming (stmt);
1399 find_referenced_vars_in (stmt);
1401 /* Adjust the `this' pointer. */
1402 ptr = fold_build2_loc (input_location,
1403 POINTER_PLUS_EXPR, TREE_TYPE (ptr), ptr,
1408 && fixed_offset != 0)
1409 /* Adjust the pointer by the constant. */
1413 if (TREE_CODE (ptr) == VAR_DECL)
1417 ptrtmp = create_tmp_var (TREE_TYPE (ptr), "ptr");
1418 stmt = gimple_build_assign (ptrtmp, ptr);
1419 gsi_insert_after (bsi, stmt, GSI_NEW_STMT);
1420 mark_symbols_for_renaming (stmt);
1421 find_referenced_vars_in (stmt);
1423 ptr = fold_build2_loc (input_location,
1424 POINTER_PLUS_EXPR, TREE_TYPE (ptrtmp), ptrtmp,
1425 size_int (fixed_offset));
1428 /* Emit the statement and gimplify the adjustment expression. */
1429 ret = create_tmp_var (TREE_TYPE (ptr), "adjusted_this");
1430 stmt = gimple_build_assign (ret, ptr);
1431 mark_symbols_for_renaming (stmt);
1432 find_referenced_vars_in (stmt);
1433 gsi_insert_after (bsi, stmt, GSI_NEW_STMT);
1438 /* Produce assembler for thunk NODE. */
1441 assemble_thunk (struct cgraph_node *node)
1443 bool this_adjusting = node->thunk.this_adjusting;
1444 HOST_WIDE_INT fixed_offset = node->thunk.fixed_offset;
1445 HOST_WIDE_INT virtual_value = node->thunk.virtual_value;
1446 tree virtual_offset = NULL;
1447 tree alias = node->thunk.alias;
1448 tree thunk_fndecl = node->decl;
1449 tree a = DECL_ARGUMENTS (thunk_fndecl);
1451 current_function_decl = thunk_fndecl;
1454 && targetm.asm_out.can_output_mi_thunk (thunk_fndecl, fixed_offset,
1455 virtual_value, alias))
1460 DECL_RESULT (thunk_fndecl)
1461 = build_decl (DECL_SOURCE_LOCATION (thunk_fndecl),
1462 RESULT_DECL, 0, integer_type_node);
1463 fnname = IDENTIFIER_POINTER (DECL_ASSEMBLER_NAME (thunk_fndecl));
1465 /* The back end expects DECL_INITIAL to contain a BLOCK, so we
1467 fn_block = make_node (BLOCK);
1468 BLOCK_VARS (fn_block) = a;
1469 DECL_INITIAL (thunk_fndecl) = fn_block;
1470 init_function_start (thunk_fndecl);
1472 assemble_start_function (thunk_fndecl, fnname);
1474 targetm.asm_out.output_mi_thunk (asm_out_file, thunk_fndecl,
1475 fixed_offset, virtual_value, alias);
1477 assemble_end_function (thunk_fndecl, fnname);
1478 init_insn_lengths ();
1479 free_after_compilation (cfun);
1481 TREE_ASM_WRITTEN (thunk_fndecl) = 1;
1486 basic_block bb, then_bb, else_bb, return_bb;
1487 gimple_stmt_iterator bsi;
1493 VEC(tree, heap) *vargs;
1498 DECL_IGNORED_P (thunk_fndecl) = 1;
1499 bitmap_obstack_initialize (NULL);
1501 if (node->thunk.virtual_offset_p)
1502 virtual_offset = size_int (virtual_value);
1504 /* Build the return declaration for the function. */
1505 restype = TREE_TYPE (TREE_TYPE (thunk_fndecl));
1506 if (DECL_RESULT (thunk_fndecl) == NULL_TREE)
1508 resdecl = build_decl (input_location, RESULT_DECL, 0, restype);
1509 DECL_ARTIFICIAL (resdecl) = 1;
1510 DECL_IGNORED_P (resdecl) = 1;
1511 DECL_RESULT (thunk_fndecl) = resdecl;
1514 resdecl = DECL_RESULT (thunk_fndecl);
1516 bb = then_bb = else_bb = return_bb = init_lowered_empty_function (thunk_fndecl);
1518 bsi = gsi_start_bb (bb);
1520 /* Build call to the function being thunked. */
1521 if (!VOID_TYPE_P (restype))
1523 if (!is_gimple_reg_type (restype))
1526 cfun->local_decls = tree_cons (NULL_TREE, restmp, cfun->local_decls);
1527 BLOCK_VARS (DECL_INITIAL (current_function_decl)) = restmp;
1530 restmp = create_tmp_var_raw (restype, "retval");
1533 for (arg = a; arg; arg = TREE_CHAIN (arg))
1535 vargs = VEC_alloc (tree, heap, nargs);
1537 VEC_quick_push (tree, vargs,
1542 VEC_quick_push (tree, vargs, a);
1543 for (i = 1, arg = TREE_CHAIN (a); i < nargs; i++, arg = TREE_CHAIN (arg))
1544 VEC_quick_push (tree, vargs, arg);
1545 call = gimple_build_call_vec (build_fold_addr_expr_loc (0, alias), vargs);
1546 VEC_free (tree, heap, vargs);
1547 gimple_call_set_cannot_inline (call, true);
1548 gimple_call_set_from_thunk (call, true);
1550 gimple_call_set_lhs (call, restmp);
1551 gsi_insert_after (&bsi, call, GSI_NEW_STMT);
1552 mark_symbols_for_renaming (call);
1553 find_referenced_vars_in (call);
1556 if (restmp && !this_adjusting)
1558 tree true_label = NULL_TREE;
1560 if (TREE_CODE (TREE_TYPE (restmp)) == POINTER_TYPE)
1563 /* If the return type is a pointer, we need to
1564 protect against NULL. We know there will be an
1565 adjustment, because that's why we're emitting a
1567 then_bb = create_basic_block (NULL, (void *) 0, bb);
1568 return_bb = create_basic_block (NULL, (void *) 0, then_bb);
1569 else_bb = create_basic_block (NULL, (void *) 0, else_bb);
1570 remove_edge (single_succ_edge (bb));
1571 true_label = gimple_block_label (then_bb);
1572 stmt = gimple_build_cond (NE_EXPR, restmp,
1573 fold_convert (TREE_TYPE (restmp),
1575 NULL_TREE, NULL_TREE);
1576 gsi_insert_after (&bsi, stmt, GSI_NEW_STMT);
1577 make_edge (bb, then_bb, EDGE_TRUE_VALUE);
1578 make_edge (bb, else_bb, EDGE_FALSE_VALUE);
1579 make_edge (return_bb, EXIT_BLOCK_PTR, 0);
1580 make_edge (then_bb, return_bb, EDGE_FALLTHRU);
1581 make_edge (else_bb, return_bb, EDGE_FALLTHRU);
1582 bsi = gsi_last_bb (then_bb);
1585 restmp = thunk_adjust (&bsi, restmp, /*this_adjusting=*/0,
1586 fixed_offset, virtual_offset);
1590 bsi = gsi_last_bb (else_bb);
1591 stmt = gimple_build_assign (restmp, fold_convert (TREE_TYPE (restmp),
1592 integer_zero_node));
1593 gsi_insert_after (&bsi, stmt, GSI_NEW_STMT);
1594 bsi = gsi_last_bb (return_bb);
1598 gimple_call_set_tail (call, true);
1600 /* Build return value. */
1601 ret = gimple_build_return (restmp);
1602 gsi_insert_after (&bsi, ret, GSI_NEW_STMT);
1604 delete_unreachable_blocks ();
1605 update_ssa (TODO_update_ssa);
1607 cgraph_remove_same_body_alias (node);
1608 /* Since we want to emit the thunk, we explicitly mark its name as
1610 cgraph_add_new_function (thunk_fndecl, true);
1611 bitmap_obstack_release (NULL);
1613 current_function_decl = NULL;
1616 /* Expand function specified by NODE. */
1619 cgraph_expand_function (struct cgraph_node *node)
1621 tree decl = node->decl;
1623 /* We ought to not compile any inline clones. */
1624 gcc_assert (!node->global.inlined_to);
1626 announce_function (decl);
1629 gcc_assert (node->lowered);
1631 /* Generate RTL for the body of DECL. */
1632 tree_rest_of_compilation (decl);
1634 /* Make sure that BE didn't give up on compiling. */
1635 gcc_assert (TREE_ASM_WRITTEN (decl));
1636 current_function_decl = NULL;
1637 if (node->same_body)
1639 struct cgraph_node *alias, *next;
1640 bool saved_alias = node->alias;
1641 for (alias = node->same_body;
1642 alias && alias->next; alias = alias->next)
1644 /* Walk aliases in the order they were created; it is possible that
1645 thunks reffers to the aliases made earlier. */
1646 for (; alias; alias = next)
1648 next = alias->previous;
1649 if (!alias->thunk.thunk_p)
1650 assemble_alias (alias->decl,
1651 DECL_ASSEMBLER_NAME (alias->thunk.alias));
1653 assemble_thunk (alias);
1655 node->alias = saved_alias;
1657 gcc_assert (!cgraph_preserve_function_body_p (decl));
1658 cgraph_release_function_body (node);
1659 /* Eliminate all call edges. This is important so the GIMPLE_CALL no longer
1660 points to the dead function body. */
1661 cgraph_node_remove_callees (node);
1663 cgraph_function_flags_ready = true;
1666 /* Return true when CALLER_DECL should be inlined into CALLEE_DECL. */
1669 cgraph_inline_p (struct cgraph_edge *e, cgraph_inline_failed_t *reason)
1671 *reason = e->inline_failed;
1672 return !e->inline_failed;
1677 /* Expand all functions that must be output.
1679 Attempt to topologically sort the nodes so function is output when
1680 all called functions are already assembled to allow data to be
1681 propagated across the callgraph. Use a stack to get smaller distance
1682 between a function and its callees (later we may choose to use a more
1683 sophisticated algorithm for function reordering; we will likely want
1684 to use subsections to make the output functions appear in top-down
1688 cgraph_expand_all_functions (void)
1690 struct cgraph_node *node;
1691 struct cgraph_node **order = XCNEWVEC (struct cgraph_node *, cgraph_n_nodes);
1692 int order_pos, new_order_pos = 0;
1695 order_pos = cgraph_postorder (order);
1696 gcc_assert (order_pos == cgraph_n_nodes);
1698 /* Garbage collector may remove inline clones we eliminate during
1699 optimization. So we must be sure to not reference them. */
1700 for (i = 0; i < order_pos; i++)
1701 if (order[i]->process)
1702 order[new_order_pos++] = order[i];
1704 for (i = new_order_pos - 1; i >= 0; i--)
1709 gcc_assert (node->reachable);
1711 cgraph_expand_function (node);
1714 cgraph_process_new_functions ();
1720 /* This is used to sort the node types by the cgraph order number. */
1722 enum cgraph_order_sort_kind
1724 ORDER_UNDEFINED = 0,
1730 struct cgraph_order_sort
1732 enum cgraph_order_sort_kind kind;
1735 struct cgraph_node *f;
1736 struct varpool_node *v;
1737 struct cgraph_asm_node *a;
1741 /* Output all functions, variables, and asm statements in the order
1742 according to their order fields, which is the order in which they
1743 appeared in the file. This implements -fno-toplevel-reorder. In
1744 this mode we may output functions and variables which don't really
1745 need to be output. */
1748 cgraph_output_in_order (void)
1751 struct cgraph_order_sort *nodes;
1753 struct cgraph_node *pf;
1754 struct varpool_node *pv;
1755 struct cgraph_asm_node *pa;
1758 nodes = XCNEWVEC (struct cgraph_order_sort, max);
1760 varpool_analyze_pending_decls ();
1762 for (pf = cgraph_nodes; pf; pf = pf->next)
1767 gcc_assert (nodes[i].kind == ORDER_UNDEFINED);
1768 nodes[i].kind = ORDER_FUNCTION;
1773 for (pv = varpool_nodes_queue; pv; pv = pv->next_needed)
1776 gcc_assert (nodes[i].kind == ORDER_UNDEFINED);
1777 nodes[i].kind = ORDER_VAR;
1781 for (pa = cgraph_asm_nodes; pa; pa = pa->next)
1784 gcc_assert (nodes[i].kind == ORDER_UNDEFINED);
1785 nodes[i].kind = ORDER_ASM;
1789 /* In toplevel reorder mode we output all statics; mark them as needed. */
1790 for (i = 0; i < max; ++i)
1792 if (nodes[i].kind == ORDER_VAR)
1794 varpool_mark_needed_node (nodes[i].u.v);
1797 varpool_empty_needed_queue ();
1799 for (i = 0; i < max; ++i)
1801 switch (nodes[i].kind)
1803 case ORDER_FUNCTION:
1804 nodes[i].u.f->process = 0;
1805 cgraph_expand_function (nodes[i].u.f);
1809 varpool_assemble_decl (nodes[i].u.v);
1813 assemble_asm (nodes[i].u.a->asm_str);
1816 case ORDER_UNDEFINED:
1824 cgraph_asm_nodes = NULL;
1828 /* Return true when function body of DECL still needs to be kept around
1829 for later re-use. */
1831 cgraph_preserve_function_body_p (tree decl)
1833 struct cgraph_node *node;
1835 gcc_assert (cgraph_global_info_ready);
1836 /* Look if there is any clone around. */
1837 node = cgraph_node (decl);
1847 current_function_decl = NULL;
1848 gimple_register_cfg_hooks ();
1849 bitmap_obstack_initialize (NULL);
1851 invoke_plugin_callbacks (PLUGIN_ALL_IPA_PASSES_START, NULL);
1854 execute_ipa_pass_list (all_small_ipa_passes);
1856 /* If pass_all_early_optimizations was not scheduled, the state of
1857 the cgraph will not be properly updated. Update it now. */
1858 if (cgraph_state < CGRAPH_STATE_IPA_SSA)
1859 cgraph_state = CGRAPH_STATE_IPA_SSA;
1863 /* Generate coverage variables and constructors. */
1866 /* Process new functions added. */
1868 current_function_decl = NULL;
1869 cgraph_process_new_functions ();
1871 execute_ipa_summary_passes
1872 ((struct ipa_opt_pass_d *) all_regular_ipa_passes);
1875 /* Some targets need to handle LTO assembler output specially. */
1876 if (flag_generate_lto)
1877 targetm.asm_out.lto_start ();
1879 execute_ipa_summary_passes ((struct ipa_opt_pass_d *) all_lto_gen_passes);
1882 ipa_write_summaries ();
1884 if (flag_generate_lto)
1885 targetm.asm_out.lto_end ();
1888 execute_ipa_pass_list (all_regular_ipa_passes);
1889 invoke_plugin_callbacks (PLUGIN_ALL_IPA_PASSES_END, NULL);
1891 bitmap_obstack_release (NULL);
1895 /* Perform simple optimizations based on callgraph. */
1898 cgraph_optimize (void)
1903 #ifdef ENABLE_CHECKING
1907 /* Frontend may output common variables after the unit has been finalized.
1908 It is safe to deal with them here as they are always zero initialized. */
1909 varpool_analyze_pending_decls ();
1911 timevar_push (TV_CGRAPHOPT);
1912 if (pre_ipa_mem_report)
1914 fprintf (stderr, "Memory consumption before IPA\n");
1915 dump_memory_report (false);
1918 fprintf (stderr, "Performing interprocedural optimizations\n");
1919 cgraph_state = CGRAPH_STATE_IPA;
1921 /* Don't run the IPA passes if there was any error or sorry messages. */
1925 /* Do nothing else if any IPA pass found errors. */
1928 timevar_pop (TV_CGRAPHOPT);
1932 /* This pass remove bodies of extern inline functions we never inlined.
1933 Do this later so other IPA passes see what is really going on. */
1934 cgraph_remove_unreachable_nodes (false, dump_file);
1935 cgraph_global_info_ready = true;
1936 if (cgraph_dump_file)
1938 fprintf (cgraph_dump_file, "Optimized ");
1939 dump_cgraph (cgraph_dump_file);
1940 dump_varpool (cgraph_dump_file);
1942 if (post_ipa_mem_report)
1944 fprintf (stderr, "Memory consumption after IPA\n");
1945 dump_memory_report (false);
1947 timevar_pop (TV_CGRAPHOPT);
1949 /* Output everything. */
1950 (*debug_hooks->assembly_start) ();
1952 fprintf (stderr, "Assembling functions:\n");
1953 #ifdef ENABLE_CHECKING
1957 cgraph_materialize_all_clones ();
1958 cgraph_mark_functions_to_output ();
1960 cgraph_state = CGRAPH_STATE_EXPANSION;
1961 if (!flag_toplevel_reorder)
1962 cgraph_output_in_order ();
1965 cgraph_output_pending_asms ();
1967 cgraph_expand_all_functions ();
1968 varpool_remove_unreferenced_decls ();
1970 varpool_assemble_pending_decls ();
1972 cgraph_process_new_functions ();
1973 cgraph_state = CGRAPH_STATE_FINISHED;
1975 if (cgraph_dump_file)
1977 fprintf (cgraph_dump_file, "\nFinal ");
1978 dump_cgraph (cgraph_dump_file);
1980 #ifdef ENABLE_CHECKING
1982 /* Double check that all inline clones are gone and that all
1983 function bodies have been released from memory. */
1986 struct cgraph_node *node;
1987 bool error_found = false;
1989 for (node = cgraph_nodes; node; node = node->next)
1991 && (node->global.inlined_to
1992 || gimple_has_body_p (node->decl)))
1995 dump_cgraph_node (stderr, node);
1998 internal_error ("nodes with unreleased memory found");
2004 /* Generate and emit a static constructor or destructor. WHICH must
2005 be one of 'I' (for a constructor) or 'D' (for a destructor). BODY
2006 is a STATEMENT_LIST containing GENERIC statements. PRIORITY is the
2007 initialization priority for this constructor or destructor. */
2010 cgraph_build_static_cdtor (char which, tree body, int priority)
2012 static int counter = 0;
2014 tree decl, name, resdecl;
2016 /* The priority is encoded in the constructor or destructor name.
2017 collect2 will sort the names and arrange that they are called at
2019 sprintf (which_buf, "%c_%.5d_%d", which, priority, counter++);
2020 name = get_file_function_name (which_buf);
2022 decl = build_decl (input_location, FUNCTION_DECL, name,
2023 build_function_type (void_type_node, void_list_node));
2024 current_function_decl = decl;
2026 resdecl = build_decl (input_location,
2027 RESULT_DECL, NULL_TREE, void_type_node);
2028 DECL_ARTIFICIAL (resdecl) = 1;
2029 DECL_RESULT (decl) = resdecl;
2030 DECL_CONTEXT (resdecl) = decl;
2032 allocate_struct_function (decl, false);
2034 TREE_STATIC (decl) = 1;
2035 TREE_USED (decl) = 1;
2036 DECL_ARTIFICIAL (decl) = 1;
2037 DECL_NO_INSTRUMENT_FUNCTION_ENTRY_EXIT (decl) = 1;
2038 DECL_SAVED_TREE (decl) = body;
2039 if (!targetm.have_ctors_dtors)
2041 TREE_PUBLIC (decl) = 1;
2042 DECL_PRESERVE_P (decl) = 1;
2044 DECL_UNINLINABLE (decl) = 1;
2046 DECL_INITIAL (decl) = make_node (BLOCK);
2047 TREE_USED (DECL_INITIAL (decl)) = 1;
2049 DECL_SOURCE_LOCATION (decl) = input_location;
2050 cfun->function_end_locus = input_location;
2055 DECL_STATIC_CONSTRUCTOR (decl) = 1;
2056 decl_init_priority_insert (decl, priority);
2059 DECL_STATIC_DESTRUCTOR (decl) = 1;
2060 decl_fini_priority_insert (decl, priority);
2066 gimplify_function_tree (decl);
2068 cgraph_add_new_function (decl, false);
2069 cgraph_mark_needed_node (cgraph_node (decl));
2076 cgraph_dump_file = dump_begin (TDI_cgraph, NULL);
2079 /* The edges representing the callers of the NEW_VERSION node were
2080 fixed by cgraph_function_versioning (), now the call_expr in their
2081 respective tree code should be updated to call the NEW_VERSION. */
2084 update_call_expr (struct cgraph_node *new_version)
2086 struct cgraph_edge *e;
2088 gcc_assert (new_version);
2090 /* Update the call expr on the edges to call the new version. */
2091 for (e = new_version->callers; e; e = e->next_caller)
2093 struct function *inner_function = DECL_STRUCT_FUNCTION (e->caller->decl);
2094 gimple_call_set_fndecl (e->call_stmt, new_version->decl);
2095 maybe_clean_eh_stmt_fn (inner_function, e->call_stmt);
2100 /* Create a new cgraph node which is the new version of
2101 OLD_VERSION node. REDIRECT_CALLERS holds the callers
2102 edges which should be redirected to point to
2103 NEW_VERSION. ALL the callees edges of OLD_VERSION
2104 are cloned to the new version node. Return the new
2107 If non-NULL BLOCK_TO_COPY determine what basic blocks
2108 was copied to prevent duplications of calls that are dead
2111 static struct cgraph_node *
2112 cgraph_copy_node_for_versioning (struct cgraph_node *old_version,
2114 VEC(cgraph_edge_p,heap) *redirect_callers,
2117 struct cgraph_node *new_version;
2118 struct cgraph_edge *e;
2121 gcc_assert (old_version);
2123 new_version = cgraph_node (new_decl);
2125 new_version->analyzed = true;
2126 new_version->local = old_version->local;
2127 new_version->local.externally_visible = false;
2128 new_version->local.local = true;
2129 new_version->local.vtable_method = false;
2130 new_version->global = old_version->global;
2131 new_version->rtl = new_version->rtl;
2132 new_version->reachable = true;
2133 new_version->count = old_version->count;
2135 for (e = old_version->callees; e; e=e->next_callee)
2137 || bitmap_bit_p (bbs_to_copy, gimple_bb (e->call_stmt)->index))
2138 cgraph_clone_edge (e, new_version, e->call_stmt,
2139 e->lto_stmt_uid, REG_BR_PROB_BASE,
2141 e->loop_nest, true);
2142 for (e = old_version->indirect_calls; e; e=e->next_callee)
2144 || bitmap_bit_p (bbs_to_copy, gimple_bb (e->call_stmt)->index))
2145 cgraph_clone_edge (e, new_version, e->call_stmt,
2146 e->lto_stmt_uid, REG_BR_PROB_BASE,
2148 e->loop_nest, true);
2149 for (i = 0; VEC_iterate (cgraph_edge_p, redirect_callers, i, e); i++)
2151 /* Redirect calls to the old version node to point to its new
2153 cgraph_redirect_edge_callee (e, new_version);
2159 /* Perform function versioning.
2160 Function versioning includes copying of the tree and
2161 a callgraph update (creating a new cgraph node and updating
2162 its callees and callers).
2164 REDIRECT_CALLERS varray includes the edges to be redirected
2167 TREE_MAP is a mapping of tree nodes we want to replace with
2168 new ones (according to results of prior analysis).
2169 OLD_VERSION_NODE is the node that is versioned.
2170 It returns the new version's cgraph node.
2171 If non-NULL ARGS_TO_SKIP determine function parameters to remove
2173 If non-NULL BLOCK_TO_COPY determine what basic blocks to copy.
2174 If non_NULL NEW_ENTRY determine new entry BB of the clone. */
2176 struct cgraph_node *
2177 cgraph_function_versioning (struct cgraph_node *old_version_node,
2178 VEC(cgraph_edge_p,heap) *redirect_callers,
2179 VEC (ipa_replace_map_p,gc)* tree_map,
2180 bitmap args_to_skip,
2182 basic_block new_entry_block,
2183 const char *clone_name)
2185 tree old_decl = old_version_node->decl;
2186 struct cgraph_node *new_version_node = NULL;
2189 if (!tree_versionable_function_p (old_decl))
2192 /* Make a new FUNCTION_DECL tree node for the
2195 new_decl = copy_node (old_decl);
2197 new_decl = build_function_decl_skip_args (old_decl, args_to_skip);
2199 cgraph_make_decl_local (new_decl);
2200 /* Generate a new name for the new version. */
2201 DECL_NAME (new_decl) = clone_function_name (old_decl, clone_name);
2202 SET_DECL_ASSEMBLER_NAME (new_decl, DECL_NAME (new_decl));
2203 SET_DECL_RTL (new_decl, NULL);
2205 /* Create the new version's call-graph node.
2206 and update the edges of the new node. */
2208 cgraph_copy_node_for_versioning (old_version_node, new_decl,
2209 redirect_callers, bbs_to_copy);
2211 /* Copy the OLD_VERSION_NODE function tree to the new version. */
2212 tree_function_versioning (old_decl, new_decl, tree_map, false, args_to_skip,
2213 bbs_to_copy, new_entry_block);
2215 /* Update the new version's properties.
2216 Make The new version visible only within this translation unit. Make sure
2217 that is not weak also.
2218 ??? We cannot use COMDAT linkage because there is no
2219 ABI support for this. */
2220 cgraph_make_decl_local (new_version_node->decl);
2221 DECL_VIRTUAL_P (new_version_node->decl) = 0;
2222 new_version_node->local.externally_visible = 0;
2223 new_version_node->local.local = 1;
2224 new_version_node->lowered = true;
2226 /* Update the call_expr on the edges to call the new version node. */
2227 update_call_expr (new_version_node);
2229 cgraph_call_function_insertion_hooks (new_version_node);
2230 return new_version_node;
2233 /* Produce separate function body for inline clones so the offline copy can be
2234 modified without affecting them. */
2235 struct cgraph_node *
2236 save_inline_function_body (struct cgraph_node *node)
2238 struct cgraph_node *first_clone, *n;
2240 gcc_assert (node == cgraph_node (node->decl));
2242 cgraph_lower_function (node);
2244 first_clone = node->clones;
2246 first_clone->decl = copy_node (node->decl);
2247 cgraph_insert_node_to_hashtable (first_clone);
2248 gcc_assert (first_clone == cgraph_node (first_clone->decl));
2249 if (first_clone->next_sibling_clone)
2251 for (n = first_clone->next_sibling_clone; n->next_sibling_clone; n = n->next_sibling_clone)
2252 n->clone_of = first_clone;
2253 n->clone_of = first_clone;
2254 n->next_sibling_clone = first_clone->clones;
2255 if (first_clone->clones)
2256 first_clone->clones->prev_sibling_clone = n;
2257 first_clone->clones = first_clone->next_sibling_clone;
2258 first_clone->next_sibling_clone->prev_sibling_clone = NULL;
2259 first_clone->next_sibling_clone = NULL;
2260 gcc_assert (!first_clone->prev_sibling_clone);
2262 first_clone->clone_of = NULL;
2263 node->clones = NULL;
2265 if (first_clone->clones)
2266 for (n = first_clone->clones; n != first_clone;)
2268 gcc_assert (n->decl == node->decl);
2269 n->decl = first_clone->decl;
2272 else if (n->next_sibling_clone)
2273 n = n->next_sibling_clone;
2276 while (n != first_clone && !n->next_sibling_clone)
2278 if (n != first_clone)
2279 n = n->next_sibling_clone;
2283 /* Copy the OLD_VERSION_NODE function tree to the new version. */
2284 tree_function_versioning (node->decl, first_clone->decl, NULL, true, NULL,
2287 DECL_EXTERNAL (first_clone->decl) = 0;
2288 DECL_COMDAT_GROUP (first_clone->decl) = NULL_TREE;
2289 TREE_PUBLIC (first_clone->decl) = 0;
2290 DECL_COMDAT (first_clone->decl) = 0;
2291 VEC_free (ipa_opt_pass, heap,
2292 first_clone->ipa_transforms_to_apply);
2293 first_clone->ipa_transforms_to_apply = NULL;
2295 #ifdef ENABLE_CHECKING
2296 verify_cgraph_node (first_clone);
2301 /* Given virtual clone, turn it into actual clone. */
2303 cgraph_materialize_clone (struct cgraph_node *node)
2305 bitmap_obstack_initialize (NULL);
2306 #ifdef ENABLE_CHECKING
2307 node->former_clone_of = node->clone_of->decl;
2308 if (node->clone_of->former_clone_of)
2309 node->former_clone_of = node->clone_of->former_clone_of;
2311 /* Copy the OLD_VERSION_NODE function tree to the new version. */
2312 tree_function_versioning (node->clone_of->decl, node->decl,
2313 node->clone.tree_map, true,
2314 node->clone.args_to_skip, NULL, NULL);
2315 if (cgraph_dump_file)
2317 dump_function_to_file (node->clone_of->decl, cgraph_dump_file, dump_flags);
2318 dump_function_to_file (node->decl, cgraph_dump_file, dump_flags);
2321 /* Function is no longer clone. */
2322 if (node->next_sibling_clone)
2323 node->next_sibling_clone->prev_sibling_clone = node->prev_sibling_clone;
2324 if (node->prev_sibling_clone)
2325 node->prev_sibling_clone->next_sibling_clone = node->next_sibling_clone;
2327 node->clone_of->clones = node->next_sibling_clone;
2328 node->next_sibling_clone = NULL;
2329 node->prev_sibling_clone = NULL;
2330 if (!node->clone_of->analyzed && !node->clone_of->clones)
2332 cgraph_release_function_body (node->clone_of);
2333 cgraph_node_remove_callees (node->clone_of);
2334 ipa_remove_all_references (&node->clone_of->ref_list);
2336 node->clone_of = NULL;
2337 bitmap_obstack_release (NULL);
2340 /* If necessary, change the function declaration in the call statement
2341 associated with E so that it corresponds to the edge callee. */
2344 cgraph_redirect_edge_call_stmt_to_callee (struct cgraph_edge *e)
2346 tree decl = gimple_call_fndecl (e->call_stmt);
2348 #ifdef ENABLE_CHECKING
2349 struct cgraph_node *node;
2352 if (!decl || decl == e->callee->decl
2353 /* Don't update call from same body alias to the real function. */
2354 || cgraph_get_node (decl) == cgraph_get_node (e->callee->decl))
2355 return e->call_stmt;
2357 #ifdef ENABLE_CHECKING
2358 node = cgraph_get_node (decl);
2359 gcc_assert (!node || !node->clone.combined_args_to_skip);
2362 if (cgraph_dump_file)
2364 fprintf (cgraph_dump_file, "updating call of %s/%i -> %s/%i: ",
2365 cgraph_node_name (e->caller), e->caller->uid,
2366 cgraph_node_name (e->callee), e->callee->uid);
2367 print_gimple_stmt (cgraph_dump_file, e->call_stmt, 0, dump_flags);
2368 if (e->callee->clone.combined_args_to_skip)
2370 fprintf (cgraph_dump_file, " combined args to skip: ");
2371 dump_bitmap (cgraph_dump_file,
2372 e->callee->clone.combined_args_to_skip);
2376 if (e->callee->clone.combined_args_to_skip)
2378 gimple_stmt_iterator gsi;
2381 = gimple_call_copy_skip_args (e->call_stmt,
2382 e->callee->clone.combined_args_to_skip);
2384 if (gimple_vdef (new_stmt)
2385 && TREE_CODE (gimple_vdef (new_stmt)) == SSA_NAME)
2386 SSA_NAME_DEF_STMT (gimple_vdef (new_stmt)) = new_stmt;
2388 gsi = gsi_for_stmt (e->call_stmt);
2389 gsi_replace (&gsi, new_stmt, true);
2392 new_stmt = e->call_stmt;
2394 gimple_call_set_fndecl (new_stmt, e->callee->decl);
2395 update_stmt (new_stmt);
2397 cgraph_set_call_stmt_including_clones (e->caller, e->call_stmt, new_stmt);
2399 if (cgraph_dump_file)
2401 fprintf (cgraph_dump_file, " updated to:");
2402 print_gimple_stmt (cgraph_dump_file, e->call_stmt, 0, dump_flags);
2407 /* Once all functions from compilation unit are in memory, produce all clones
2408 and update all calls. We might also do this on demand if we don't want to
2409 bring all functions to memory prior compilation, but current WHOPR
2410 implementation does that and it is is bit easier to keep everything right in
2413 cgraph_materialize_all_clones (void)
2415 struct cgraph_node *node;
2416 bool stabilized = false;
2418 if (cgraph_dump_file)
2419 fprintf (cgraph_dump_file, "Materializing clones\n");
2420 #ifdef ENABLE_CHECKING
2424 /* We can also do topological order, but number of iterations should be
2425 bounded by number of IPA passes since single IPA pass is probably not
2426 going to create clones of clones it created itself. */
2430 for (node = cgraph_nodes; node; node = node->next)
2432 if (node->clone_of && node->decl != node->clone_of->decl
2433 && !gimple_has_body_p (node->decl))
2435 if (gimple_has_body_p (node->clone_of->decl))
2437 if (cgraph_dump_file)
2439 fprintf (cgraph_dump_file, "clonning %s to %s\n",
2440 cgraph_node_name (node->clone_of),
2441 cgraph_node_name (node));
2442 if (node->clone.tree_map)
2445 fprintf (cgraph_dump_file, " replace map: ");
2446 for (i = 0; i < VEC_length (ipa_replace_map_p,
2447 node->clone.tree_map);
2450 struct ipa_replace_map *replace_info;
2451 replace_info = VEC_index (ipa_replace_map_p,
2452 node->clone.tree_map,
2454 print_generic_expr (cgraph_dump_file, replace_info->old_tree, 0);
2455 fprintf (cgraph_dump_file, " -> ");
2456 print_generic_expr (cgraph_dump_file, replace_info->new_tree, 0);
2457 fprintf (cgraph_dump_file, "%s%s;",
2458 replace_info->replace_p ? "(replace)":"",
2459 replace_info->ref_p ? "(ref)":"");
2461 fprintf (cgraph_dump_file, "\n");
2463 if (node->clone.args_to_skip)
2465 fprintf (cgraph_dump_file, " args_to_skip: ");
2466 dump_bitmap (cgraph_dump_file, node->clone.args_to_skip);
2468 if (node->clone.args_to_skip)
2470 fprintf (cgraph_dump_file, " combined_args_to_skip:");
2471 dump_bitmap (cgraph_dump_file, node->clone.combined_args_to_skip);
2474 cgraph_materialize_clone (node);
2480 for (node = cgraph_nodes; node; node = node->next)
2481 if (!node->analyzed && node->callees)
2482 cgraph_node_remove_callees (node);
2483 if (cgraph_dump_file)
2484 fprintf (cgraph_dump_file, "Materialization Call site updates done.\n");
2485 #ifdef ENABLE_CHECKING
2488 cgraph_remove_unreachable_nodes (false, cgraph_dump_file);
2491 #include "gt-cgraphunit.h"