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 static 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 was 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)
359 || (!optimize && !node->local.disregard_inline_limits
360 && !DECL_DECLARED_INLINE_P (decl)
362 && !flag_whole_program
365 && !DECL_COMDAT (decl) && !DECL_EXTERNAL (decl))
368 /* Constructors and destructors are reachable from the runtime by
370 if (DECL_STATIC_CONSTRUCTOR (decl) || DECL_STATIC_DESTRUCTOR (decl))
376 /* Process CGRAPH_NEW_FUNCTIONS and perform actions necessary to add these
377 functions into callgraph in a way so they look like ordinary reachable
378 functions inserted into callgraph already at construction time. */
381 cgraph_process_new_functions (void)
385 struct cgraph_node *node;
387 varpool_analyze_pending_decls ();
388 /* Note that this queue may grow as its being processed, as the new
389 functions may generate new ones. */
390 while (cgraph_new_nodes)
392 node = cgraph_new_nodes;
394 cgraph_new_nodes = cgraph_new_nodes->next_needed;
395 switch (cgraph_state)
397 case CGRAPH_STATE_CONSTRUCTION:
398 /* At construction time we just need to finalize function and move
399 it into reachable functions list. */
401 node->next_needed = NULL;
402 cgraph_finalize_function (fndecl, false);
403 cgraph_mark_reachable_node (node);
407 case CGRAPH_STATE_IPA:
408 case CGRAPH_STATE_IPA_SSA:
409 /* When IPA optimization already started, do all essential
410 transformations that has been already performed on the whole
411 cgraph but not on this function. */
413 gimple_register_cfg_hooks ();
415 cgraph_analyze_function (node);
416 push_cfun (DECL_STRUCT_FUNCTION (fndecl));
417 current_function_decl = fndecl;
418 compute_inline_parameters (node);
419 if ((cgraph_state == CGRAPH_STATE_IPA_SSA
420 && !gimple_in_ssa_p (DECL_STRUCT_FUNCTION (fndecl)))
421 /* When not optimizing, be sure we run early local passes anyway
424 execute_pass_list (pass_early_local_passes.pass.sub);
425 free_dominance_info (CDI_POST_DOMINATORS);
426 free_dominance_info (CDI_DOMINATORS);
428 current_function_decl = NULL;
431 case CGRAPH_STATE_EXPANSION:
432 /* Functions created during expansion shall be compiled
435 cgraph_expand_function (node);
442 cgraph_call_function_insertion_hooks (node);
443 varpool_analyze_pending_decls ();
448 /* As an GCC extension we allow redefinition of the function. The
449 semantics when both copies of bodies differ is not well defined.
450 We replace the old body with new body so in unit at a time mode
451 we always use new body, while in normal mode we may end up with
452 old body inlined into some functions and new body expanded and
455 ??? It may make more sense to use one body for inlining and other
456 body for expanding the function but this is difficult to do. */
459 cgraph_reset_node (struct cgraph_node *node)
461 /* If node->process is set, then we have already begun whole-unit analysis.
462 This is *not* testing for whether we've already emitted the function.
463 That case can be sort-of legitimately seen with real function redefinition
464 errors. I would argue that the front end should never present us with
465 such a case, but don't enforce that for now. */
466 gcc_assert (!node->process);
468 /* Reset our data structures so we can analyze the function again. */
469 memset (&node->local, 0, sizeof (node->local));
470 memset (&node->global, 0, sizeof (node->global));
471 memset (&node->rtl, 0, sizeof (node->rtl));
472 node->analyzed = false;
473 node->local.redefined_extern_inline = true;
474 node->local.finalized = false;
476 cgraph_node_remove_callees (node);
478 /* We may need to re-queue the node for assembling in case
479 we already proceeded it and ignored as not needed or got
480 a re-declaration in IMA mode. */
483 struct cgraph_node *n;
485 for (n = cgraph_nodes_queue; n; n = n->next_needed)
494 cgraph_lower_function (struct cgraph_node *node)
500 lower_nested_functions (node->decl);
501 gcc_assert (!node->nested);
503 tree_lowering_passes (node->decl);
504 node->lowered = true;
507 /* DECL has been parsed. Take it, queue it, compile it at the whim of the
508 logic in effect. If NESTED is true, then our caller cannot stand to have
509 the garbage collector run at the moment. We would need to either create
510 a new GC context, or just not compile right now. */
513 cgraph_finalize_function (tree decl, bool nested)
515 struct cgraph_node *node = cgraph_node (decl);
517 if (node->local.finalized)
518 cgraph_reset_node (node);
520 node->pid = cgraph_max_pid ++;
521 notice_global_symbol (decl);
522 node->local.finalized = true;
523 node->lowered = DECL_STRUCT_FUNCTION (decl)->cfg != NULL;
524 node->finalized_by_frontend = true;
525 record_cdtor_fn (node->decl);
527 if (cgraph_decide_is_function_needed (node, decl))
528 cgraph_mark_needed_node (node);
530 /* Since we reclaim unreachable nodes at the end of every language
531 level unit, we need to be conservative about possible entry points
533 if ((TREE_PUBLIC (decl) && !DECL_COMDAT (decl) && !DECL_EXTERNAL (decl)))
534 cgraph_mark_reachable_node (node);
536 /* If we've not yet emitted decl, tell the debug info about it. */
537 if (!TREE_ASM_WRITTEN (decl))
538 (*debug_hooks->deferred_inline_function) (decl);
540 /* Possibly warn about unused parameters. */
541 if (warn_unused_parameter)
542 do_warn_unused_parameter (decl);
548 /* C99 extern inline keywords allow changing of declaration after function
549 has been finalized. We need to re-decide if we want to mark the function as
553 cgraph_mark_if_needed (tree decl)
555 struct cgraph_node *node = cgraph_node (decl);
556 if (node->local.finalized && cgraph_decide_is_function_needed (node, decl))
557 cgraph_mark_needed_node (node);
560 /* Return TRUE if NODE2 is equivalent to NODE or its clone. */
562 clone_of_p (struct cgraph_node *node, struct cgraph_node *node2)
564 while (node != node2 && node2)
565 node2 = node2->clone_of;
566 return node2 != NULL;
569 /* Verify cgraph nodes of given cgraph node. */
571 verify_cgraph_node (struct cgraph_node *node)
573 struct cgraph_edge *e;
574 struct function *this_cfun = DECL_STRUCT_FUNCTION (node->decl);
575 struct function *saved_cfun = cfun;
576 basic_block this_block;
577 gimple_stmt_iterator gsi;
578 bool error_found = false;
580 if (errorcount || sorrycount)
583 timevar_push (TV_CGRAPH_VERIFY);
584 /* debug_generic_stmt needs correct cfun */
585 set_cfun (this_cfun);
586 for (e = node->callees; e; e = e->next_callee)
589 error ("aux field set for edge %s->%s",
590 identifier_to_locale (cgraph_node_name (e->caller)),
591 identifier_to_locale (cgraph_node_name (e->callee)));
596 error ("Execution count is negative");
599 if (node->global.inlined_to && node->local.externally_visible)
601 error ("Externally visible inline clone");
604 if (node->global.inlined_to && node->address_taken)
606 error ("Inline clone with address taken");
609 if (node->global.inlined_to && node->needed)
611 error ("Inline clone is needed");
614 for (e = node->indirect_calls; e; e = e->next_callee)
618 error ("aux field set for indirect edge from %s",
619 identifier_to_locale (cgraph_node_name (e->caller)));
622 if (!e->indirect_unknown_callee
623 || !e->indirect_info)
625 error ("An indirect edge from %s is not marked as indirect or has "
626 "associated indirect_info, the corresponding statement is: ",
627 identifier_to_locale (cgraph_node_name (e->caller)));
628 debug_gimple_stmt (e->call_stmt);
632 for (e = node->callers; e; e = e->next_caller)
636 error ("caller edge count is negative");
639 if (e->frequency < 0)
641 error ("caller edge frequency is negative");
644 if (e->frequency > CGRAPH_FREQ_MAX)
646 error ("caller edge frequency is too large");
649 if (gimple_has_body_p (e->caller->decl)
650 && !e->caller->global.inlined_to
652 != compute_call_stmt_bb_frequency (e->caller->decl,
653 gimple_bb (e->call_stmt))))
655 error ("caller edge frequency %i does not match BB freqency %i",
657 compute_call_stmt_bb_frequency (e->caller->decl,
658 gimple_bb (e->call_stmt)));
661 if (!e->inline_failed)
663 if (node->global.inlined_to
664 != (e->caller->global.inlined_to
665 ? e->caller->global.inlined_to : e->caller))
667 error ("inlined_to pointer is wrong");
670 if (node->callers->next_caller)
672 error ("multiple inline callers");
677 if (node->global.inlined_to)
679 error ("inlined_to pointer set for noninline callers");
683 if (!node->callers && node->global.inlined_to)
685 error ("inlined_to pointer is set but no predecessors found");
688 if (node->global.inlined_to == node)
690 error ("inlined_to pointer refers to itself");
694 if (!cgraph_node (node->decl))
696 error ("node not found in cgraph_hash");
702 struct cgraph_node *n;
703 for (n = node->clone_of->clones; n; n = n->next_sibling_clone)
708 error ("node has wrong clone_of");
714 struct cgraph_node *n;
715 for (n = node->clones; n; n = n->next_sibling_clone)
716 if (n->clone_of != node)
720 error ("node has wrong clone list");
724 if ((node->prev_sibling_clone || node->next_sibling_clone) && !node->clone_of)
726 error ("node is in clone list but it is not clone");
729 if (!node->prev_sibling_clone && node->clone_of && node->clone_of->clones != node)
731 error ("node has wrong prev_clone pointer");
734 if (node->prev_sibling_clone && node->prev_sibling_clone->next_sibling_clone != node)
736 error ("double linked list of clones corrupted");
739 if (node->same_comdat_group)
741 struct cgraph_node *n = node->same_comdat_group;
743 if (!DECL_ONE_ONLY (node->decl))
745 error ("non-DECL_ONE_ONLY node in a same_comdat_group list");
750 error ("node is alone in a comdat group");
755 if (!n->same_comdat_group)
757 error ("same_comdat_group is not a circular list");
761 n = n->same_comdat_group;
766 if (node->analyzed && gimple_has_body_p (node->decl)
767 && !TREE_ASM_WRITTEN (node->decl)
768 && (!DECL_EXTERNAL (node->decl) || node->global.inlined_to)
773 /* The nodes we're interested in are never shared, so walk
774 the tree ignoring duplicates. */
775 struct pointer_set_t *visited_nodes = pointer_set_create ();
776 /* Reach the trees by walking over the CFG, and note the
777 enclosing basic-blocks in the call edges. */
778 FOR_EACH_BB_FN (this_block, this_cfun)
779 for (gsi = gsi_start_bb (this_block);
783 gimple stmt = gsi_stmt (gsi);
784 if (is_gimple_call (stmt))
786 struct cgraph_edge *e = cgraph_edge (node, stmt);
787 tree decl = gimple_call_fndecl (stmt);
792 error ("shared call_stmt:");
793 debug_gimple_stmt (stmt);
796 if (!e->indirect_unknown_callee)
798 if (e->callee->same_body_alias)
800 error ("edge points to same body alias:");
801 debug_tree (e->callee->decl);
804 #ifdef ENABLE_CHECKING
805 else if (!e->callee->global.inlined_to
807 && cgraph_get_node (decl)
808 && (e->callee->former_clone_of
809 != cgraph_get_node (decl)->decl)
810 && !clone_of_p (cgraph_node (decl),
813 error ("edge points to wrong declaration:");
814 debug_tree (e->callee->decl);
815 fprintf (stderr," Instead of:");
823 error ("an indirect edge with unknown callee "
824 "corresponding to a call_stmt with "
825 "a known declaration:");
827 debug_gimple_stmt (e->call_stmt);
833 error ("missing callgraph edge for call stmt:");
834 debug_gimple_stmt (stmt);
839 pointer_set_destroy (visited_nodes);
842 /* No CFG available?! */
845 for (e = node->callees; e; e = e->next_callee)
849 error ("edge %s->%s has no corresponding call_stmt",
850 identifier_to_locale (cgraph_node_name (e->caller)),
851 identifier_to_locale (cgraph_node_name (e->callee)));
852 debug_gimple_stmt (e->call_stmt);
857 for (e = node->indirect_calls; e; e = e->next_callee)
861 error ("an indirect edge from %s has no corresponding call_stmt",
862 identifier_to_locale (cgraph_node_name (e->caller)));
863 debug_gimple_stmt (e->call_stmt);
871 dump_cgraph_node (stderr, node);
872 internal_error ("verify_cgraph_node failed");
874 set_cfun (saved_cfun);
875 timevar_pop (TV_CGRAPH_VERIFY);
878 /* Verify whole cgraph structure. */
882 struct cgraph_node *node;
884 if (sorrycount || errorcount)
887 for (node = cgraph_nodes; node; node = node->next)
888 verify_cgraph_node (node);
891 /* Output all asm statements we have stored up to be output. */
894 cgraph_output_pending_asms (void)
896 struct cgraph_asm_node *can;
898 if (errorcount || sorrycount)
901 for (can = cgraph_asm_nodes; can; can = can->next)
902 assemble_asm (can->asm_str);
903 cgraph_asm_nodes = NULL;
906 /* Analyze the function scheduled to be output. */
908 cgraph_analyze_function (struct cgraph_node *node)
910 tree save = current_function_decl;
911 tree decl = node->decl;
913 current_function_decl = decl;
914 push_cfun (DECL_STRUCT_FUNCTION (decl));
916 assign_assembler_name_if_neeeded (node->decl);
918 /* Make sure to gimplify bodies only once. During analyzing a
919 function we lower it, which will require gimplified nested
920 functions, so we can end up here with an already gimplified
922 if (!gimple_body (decl))
923 gimplify_function_tree (decl);
924 dump_function (TDI_generic, decl);
926 cgraph_lower_function (node);
927 node->analyzed = true;
930 current_function_decl = save;
933 /* Look for externally_visible and used attributes and mark cgraph nodes
936 We cannot mark the nodes at the point the attributes are processed (in
937 handle_*_attribute) because the copy of the declarations available at that
938 point may not be canonical. For example, in:
941 void f() __attribute__((used));
943 the declaration we see in handle_used_attribute will be the second
944 declaration -- but the front end will subsequently merge that declaration
945 with the original declaration and discard the second declaration.
947 Furthermore, we can't mark these nodes in cgraph_finalize_function because:
950 void f() __attribute__((externally_visible));
954 So, we walk the nodes at the end of the translation unit, applying the
955 attributes at that point. */
958 process_function_and_variable_attributes (struct cgraph_node *first,
959 struct varpool_node *first_var)
961 struct cgraph_node *node;
962 struct varpool_node *vnode;
964 for (node = cgraph_nodes; node != first; node = node->next)
966 tree decl = node->decl;
967 if (DECL_PRESERVE_P (decl))
968 cgraph_mark_needed_node (node);
969 if (lookup_attribute ("externally_visible", DECL_ATTRIBUTES (decl)))
971 if (! TREE_PUBLIC (node->decl))
972 warning_at (DECL_SOURCE_LOCATION (node->decl), OPT_Wattributes,
973 "%<externally_visible%>"
974 " attribute have effect only on public objects");
975 else if (node->local.finalized)
976 cgraph_mark_needed_node (node);
979 for (vnode = varpool_nodes; vnode != first_var; vnode = vnode->next)
981 tree decl = vnode->decl;
982 if (DECL_PRESERVE_P (decl))
984 vnode->force_output = true;
985 if (vnode->finalized)
986 varpool_mark_needed_node (vnode);
988 if (lookup_attribute ("externally_visible", DECL_ATTRIBUTES (decl)))
990 if (! TREE_PUBLIC (vnode->decl))
991 warning_at (DECL_SOURCE_LOCATION (vnode->decl), OPT_Wattributes,
992 "%<externally_visible%>"
993 " attribute have effect only on public objects");
994 else if (vnode->finalized)
995 varpool_mark_needed_node (vnode);
1000 /* Process CGRAPH_NODES_NEEDED queue, analyze each function (and transitively
1001 each reachable functions) and build cgraph.
1002 The function can be called multiple times after inserting new nodes
1003 into beginning of queue. Just the new part of queue is re-scanned then. */
1006 cgraph_analyze_functions (void)
1008 /* Keep track of already processed nodes when called multiple times for
1009 intermodule optimization. */
1010 static struct cgraph_node *first_analyzed;
1011 struct cgraph_node *first_processed = first_analyzed;
1012 static struct varpool_node *first_analyzed_var;
1013 struct cgraph_node *node, *next;
1015 process_function_and_variable_attributes (first_processed,
1016 first_analyzed_var);
1017 first_processed = cgraph_nodes;
1018 first_analyzed_var = varpool_nodes;
1019 varpool_analyze_pending_decls ();
1020 if (cgraph_dump_file)
1022 fprintf (cgraph_dump_file, "Initial entry points:");
1023 for (node = cgraph_nodes; node != first_analyzed; node = node->next)
1025 fprintf (cgraph_dump_file, " %s", cgraph_node_name (node));
1026 fprintf (cgraph_dump_file, "\n");
1028 cgraph_process_new_functions ();
1030 /* Propagate reachability flag and lower representation of all reachable
1031 functions. In the future, lowering will introduce new functions and
1032 new entry points on the way (by template instantiation and virtual
1033 method table generation for instance). */
1034 while (cgraph_nodes_queue)
1036 struct cgraph_edge *edge;
1037 tree decl = cgraph_nodes_queue->decl;
1039 node = cgraph_nodes_queue;
1040 cgraph_nodes_queue = cgraph_nodes_queue->next_needed;
1041 node->next_needed = NULL;
1043 /* ??? It is possible to create extern inline function and later using
1044 weak alias attribute to kill its body. See
1045 gcc.c-torture/compile/20011119-1.c */
1046 if (!DECL_STRUCT_FUNCTION (decl))
1048 cgraph_reset_node (node);
1052 if (!node->analyzed)
1053 cgraph_analyze_function (node);
1055 for (edge = node->callees; edge; edge = edge->next_callee)
1056 if (!edge->callee->reachable)
1057 cgraph_mark_reachable_node (edge->callee);
1059 if (node->same_comdat_group)
1061 for (next = node->same_comdat_group;
1063 next = next->same_comdat_group)
1064 cgraph_mark_reachable_node (next);
1067 /* If decl is a clone of an abstract function, mark that abstract
1068 function so that we don't release its body. The DECL_INITIAL() of that
1069 abstract function declaration will be later needed to output debug info. */
1070 if (DECL_ABSTRACT_ORIGIN (decl))
1072 struct cgraph_node *origin_node = cgraph_node (DECL_ABSTRACT_ORIGIN (decl));
1073 origin_node->abstract_and_needed = true;
1076 /* We finalize local static variables during constructing callgraph
1077 edges. Process their attributes too. */
1078 process_function_and_variable_attributes (first_processed,
1079 first_analyzed_var);
1080 first_processed = cgraph_nodes;
1081 first_analyzed_var = varpool_nodes;
1082 varpool_analyze_pending_decls ();
1083 cgraph_process_new_functions ();
1086 /* Collect entry points to the unit. */
1087 if (cgraph_dump_file)
1089 fprintf (cgraph_dump_file, "Unit entry points:");
1090 for (node = cgraph_nodes; node != first_analyzed; node = node->next)
1092 fprintf (cgraph_dump_file, " %s", cgraph_node_name (node));
1093 fprintf (cgraph_dump_file, "\n\nInitial ");
1094 dump_cgraph (cgraph_dump_file);
1097 if (cgraph_dump_file)
1098 fprintf (cgraph_dump_file, "\nReclaiming functions:");
1100 for (node = cgraph_nodes; node != first_analyzed; node = next)
1102 tree decl = node->decl;
1105 if (node->local.finalized && !gimple_has_body_p (decl))
1106 cgraph_reset_node (node);
1108 if (!node->reachable && gimple_has_body_p (decl))
1110 if (cgraph_dump_file)
1111 fprintf (cgraph_dump_file, " %s", cgraph_node_name (node));
1112 cgraph_remove_node (node);
1116 node->next_needed = NULL;
1117 gcc_assert (!node->local.finalized || gimple_has_body_p (decl));
1118 gcc_assert (node->analyzed == node->local.finalized);
1120 if (cgraph_dump_file)
1122 fprintf (cgraph_dump_file, "\n\nReclaimed ");
1123 dump_cgraph (cgraph_dump_file);
1125 first_analyzed = cgraph_nodes;
1130 /* Analyze the whole compilation unit once it is parsed completely. */
1133 cgraph_finalize_compilation_unit (void)
1135 timevar_push (TV_CGRAPH);
1137 /* Do not skip analyzing the functions if there were errors, we
1138 miss diagnostics for following functions otherwise. */
1140 /* Emit size functions we didn't inline. */
1141 finalize_size_functions ();
1143 /* Call functions declared with the "constructor" or "destructor"
1145 cgraph_build_cdtor_fns ();
1147 /* Mark alias targets necessary and emit diagnostics. */
1148 finish_aliases_1 ();
1152 fprintf (stderr, "\nAnalyzing compilation unit\n");
1156 /* Gimplify and lower all functions, compute reachability and
1157 remove unreachable nodes. */
1158 cgraph_analyze_functions ();
1160 /* Mark alias targets necessary and emit diagnostics. */
1161 finish_aliases_1 ();
1163 /* Gimplify and lower thunks. */
1164 cgraph_analyze_functions ();
1166 /* Finally drive the pass manager. */
1169 timevar_pop (TV_CGRAPH);
1173 /* Figure out what functions we want to assemble. */
1176 cgraph_mark_functions_to_output (void)
1178 struct cgraph_node *node;
1179 #ifdef ENABLE_CHECKING
1180 bool check_same_comdat_groups = false;
1182 for (node = cgraph_nodes; node; node = node->next)
1183 gcc_assert (!node->process);
1186 for (node = cgraph_nodes; node; node = node->next)
1188 tree decl = node->decl;
1189 struct cgraph_edge *e;
1191 gcc_assert (!node->process || node->same_comdat_group);
1195 for (e = node->callers; e; e = e->next_caller)
1196 if (e->inline_failed)
1199 /* We need to output all local functions that are used and not
1200 always inlined, as well as those that are reachable from
1201 outside the current compilation unit. */
1203 && !node->global.inlined_to
1204 && (node->needed || node->reachable_from_other_partition
1205 || node->address_taken
1206 || (e && node->reachable))
1207 && !TREE_ASM_WRITTEN (decl)
1208 && !DECL_EXTERNAL (decl))
1211 if (node->same_comdat_group)
1213 struct cgraph_node *next;
1214 for (next = node->same_comdat_group;
1216 next = next->same_comdat_group)
1220 else if (node->same_comdat_group)
1222 #ifdef ENABLE_CHECKING
1223 check_same_comdat_groups = true;
1228 /* We should've reclaimed all functions that are not needed. */
1229 #ifdef ENABLE_CHECKING
1230 if (!node->global.inlined_to
1231 && gimple_has_body_p (decl)
1232 /* FIXME: in ltrans unit when offline copy is outside partition but inline copies
1233 are inside partition, we can end up not removing the body since we no longer
1234 have analyzed node pointing to it. */
1235 && !node->in_other_partition
1236 && !DECL_EXTERNAL (decl))
1238 dump_cgraph_node (stderr, node);
1239 internal_error ("failed to reclaim unneeded function");
1242 gcc_assert (node->global.inlined_to
1243 || !gimple_has_body_p (decl)
1244 || node->in_other_partition
1245 || DECL_EXTERNAL (decl));
1250 #ifdef ENABLE_CHECKING
1251 if (check_same_comdat_groups)
1252 for (node = cgraph_nodes; node; node = node->next)
1253 if (node->same_comdat_group && !node->process)
1255 tree decl = node->decl;
1256 if (!node->global.inlined_to
1257 && gimple_has_body_p (decl)
1258 /* FIXME: in ltrans unit when offline copy is outside partition but inline copies
1259 are inside partition, we can end up not removing the body since we no longer
1260 have analyzed node pointing to it. */
1261 && !node->in_other_partition
1262 && !DECL_EXTERNAL (decl))
1264 dump_cgraph_node (stderr, node);
1265 internal_error ("failed to reclaim unneeded function");
1271 /* DECL is FUNCTION_DECL. Initialize datastructures so DECL is a function
1272 in lowered gimple form.
1274 Set current_function_decl and cfun to newly constructed empty function body.
1275 return basic block in the function body. */
1278 init_lowered_empty_function (tree decl)
1282 current_function_decl = decl;
1283 allocate_struct_function (decl, false);
1284 gimple_register_cfg_hooks ();
1285 init_empty_tree_cfg ();
1286 init_tree_ssa (cfun);
1287 init_ssa_operands ();
1288 cfun->gimple_df->in_ssa_p = true;
1289 DECL_INITIAL (decl) = make_node (BLOCK);
1291 DECL_SAVED_TREE (decl) = error_mark_node;
1292 cfun->curr_properties |=
1293 (PROP_gimple_lcf | PROP_gimple_leh | PROP_cfg | PROP_referenced_vars |
1296 /* Create BB for body of the function and connect it properly. */
1297 bb = create_basic_block (NULL, (void *) 0, ENTRY_BLOCK_PTR);
1298 make_edge (ENTRY_BLOCK_PTR, bb, 0);
1299 make_edge (bb, EXIT_BLOCK_PTR, 0);
1304 /* Adjust PTR by the constant FIXED_OFFSET, and by the vtable
1305 offset indicated by VIRTUAL_OFFSET, if that is
1306 non-null. THIS_ADJUSTING is nonzero for a this adjusting thunk and
1307 zero for a result adjusting thunk. */
1310 thunk_adjust (gimple_stmt_iterator * bsi,
1311 tree ptr, bool this_adjusting,
1312 HOST_WIDE_INT fixed_offset, tree virtual_offset)
1318 && fixed_offset != 0)
1320 stmt = gimple_build_assign (ptr,
1321 fold_build2_loc (input_location,
1323 TREE_TYPE (ptr), ptr,
1324 size_int (fixed_offset)));
1325 gsi_insert_after (bsi, stmt, GSI_NEW_STMT);
1328 /* If there's a virtual offset, look up that value in the vtable and
1329 adjust the pointer again. */
1337 if (!vtable_entry_type)
1339 tree vfunc_type = make_node (FUNCTION_TYPE);
1340 TREE_TYPE (vfunc_type) = integer_type_node;
1341 TYPE_ARG_TYPES (vfunc_type) = NULL_TREE;
1342 layout_type (vfunc_type);
1344 vtable_entry_type = build_pointer_type (vfunc_type);
1348 create_tmp_var (build_pointer_type
1349 (build_pointer_type (vtable_entry_type)), "vptr");
1351 /* The vptr is always at offset zero in the object. */
1352 stmt = gimple_build_assign (vtabletmp,
1353 build1 (NOP_EXPR, TREE_TYPE (vtabletmp),
1355 gsi_insert_after (bsi, stmt, GSI_NEW_STMT);
1356 mark_symbols_for_renaming (stmt);
1357 find_referenced_vars_in (stmt);
1359 /* Form the vtable address. */
1360 vtabletmp2 = create_tmp_var (TREE_TYPE (TREE_TYPE (vtabletmp)),
1362 stmt = gimple_build_assign (vtabletmp2,
1363 build1 (INDIRECT_REF,
1364 TREE_TYPE (vtabletmp2), vtabletmp));
1365 gsi_insert_after (bsi, stmt, GSI_NEW_STMT);
1366 mark_symbols_for_renaming (stmt);
1367 find_referenced_vars_in (stmt);
1369 /* Find the entry with the vcall offset. */
1370 stmt = gimple_build_assign (vtabletmp2,
1371 fold_build2_loc (input_location,
1373 TREE_TYPE (vtabletmp2),
1375 fold_convert (sizetype,
1377 gsi_insert_after (bsi, stmt, GSI_NEW_STMT);
1379 /* Get the offset itself. */
1380 vtabletmp3 = create_tmp_var (TREE_TYPE (TREE_TYPE (vtabletmp2)),
1382 stmt = gimple_build_assign (vtabletmp3,
1383 build1 (INDIRECT_REF,
1384 TREE_TYPE (vtabletmp3),
1386 gsi_insert_after (bsi, stmt, GSI_NEW_STMT);
1387 mark_symbols_for_renaming (stmt);
1388 find_referenced_vars_in (stmt);
1390 /* Cast to sizetype. */
1391 offsettmp = create_tmp_var (sizetype, "offset");
1392 stmt = gimple_build_assign (offsettmp, fold_convert (sizetype, vtabletmp3));
1393 gsi_insert_after (bsi, stmt, GSI_NEW_STMT);
1394 mark_symbols_for_renaming (stmt);
1395 find_referenced_vars_in (stmt);
1397 /* Adjust the `this' pointer. */
1398 ptr = fold_build2_loc (input_location,
1399 POINTER_PLUS_EXPR, TREE_TYPE (ptr), ptr,
1404 && fixed_offset != 0)
1405 /* Adjust the pointer by the constant. */
1409 if (TREE_CODE (ptr) == VAR_DECL)
1413 ptrtmp = create_tmp_var (TREE_TYPE (ptr), "ptr");
1414 stmt = gimple_build_assign (ptrtmp, ptr);
1415 gsi_insert_after (bsi, stmt, GSI_NEW_STMT);
1416 mark_symbols_for_renaming (stmt);
1417 find_referenced_vars_in (stmt);
1419 ptr = fold_build2_loc (input_location,
1420 POINTER_PLUS_EXPR, TREE_TYPE (ptrtmp), ptrtmp,
1421 size_int (fixed_offset));
1424 /* Emit the statement and gimplify the adjustment expression. */
1425 ret = create_tmp_var (TREE_TYPE (ptr), "adjusted_this");
1426 stmt = gimple_build_assign (ret, ptr);
1427 mark_symbols_for_renaming (stmt);
1428 find_referenced_vars_in (stmt);
1429 gsi_insert_after (bsi, stmt, GSI_NEW_STMT);
1434 /* Produce assembler for thunk NODE. */
1437 assemble_thunk (struct cgraph_node *node)
1439 bool this_adjusting = node->thunk.this_adjusting;
1440 HOST_WIDE_INT fixed_offset = node->thunk.fixed_offset;
1441 HOST_WIDE_INT virtual_value = node->thunk.virtual_value;
1442 tree virtual_offset = NULL;
1443 tree alias = node->thunk.alias;
1444 tree thunk_fndecl = node->decl;
1445 tree a = DECL_ARGUMENTS (thunk_fndecl);
1447 current_function_decl = thunk_fndecl;
1450 && targetm.asm_out.can_output_mi_thunk (thunk_fndecl, fixed_offset,
1451 virtual_value, alias))
1456 DECL_RESULT (thunk_fndecl)
1457 = build_decl (DECL_SOURCE_LOCATION (thunk_fndecl),
1458 RESULT_DECL, 0, integer_type_node);
1459 fnname = IDENTIFIER_POINTER (DECL_ASSEMBLER_NAME (thunk_fndecl));
1461 /* The back end expects DECL_INITIAL to contain a BLOCK, so we
1463 fn_block = make_node (BLOCK);
1464 BLOCK_VARS (fn_block) = a;
1465 DECL_INITIAL (thunk_fndecl) = fn_block;
1466 init_function_start (thunk_fndecl);
1468 assemble_start_function (thunk_fndecl, fnname);
1470 targetm.asm_out.output_mi_thunk (asm_out_file, thunk_fndecl,
1471 fixed_offset, virtual_value, alias);
1473 assemble_end_function (thunk_fndecl, fnname);
1474 init_insn_lengths ();
1475 free_after_compilation (cfun);
1477 TREE_ASM_WRITTEN (thunk_fndecl) = 1;
1482 basic_block bb, then_bb, else_bb, return_bb;
1483 gimple_stmt_iterator bsi;
1489 VEC(tree, heap) *vargs;
1494 DECL_IGNORED_P (thunk_fndecl) = 1;
1495 bitmap_obstack_initialize (NULL);
1497 if (node->thunk.virtual_offset_p)
1498 virtual_offset = size_int (virtual_value);
1500 /* Build the return declaration for the function. */
1501 restype = TREE_TYPE (TREE_TYPE (thunk_fndecl));
1502 if (DECL_RESULT (thunk_fndecl) == NULL_TREE)
1504 resdecl = build_decl (input_location, RESULT_DECL, 0, restype);
1505 DECL_ARTIFICIAL (resdecl) = 1;
1506 DECL_IGNORED_P (resdecl) = 1;
1507 DECL_RESULT (thunk_fndecl) = resdecl;
1510 resdecl = DECL_RESULT (thunk_fndecl);
1512 bb = then_bb = else_bb = return_bb = init_lowered_empty_function (thunk_fndecl);
1514 bsi = gsi_start_bb (bb);
1516 /* Build call to the function being thunked. */
1517 if (!VOID_TYPE_P (restype))
1519 if (!is_gimple_reg_type (restype))
1522 cfun->local_decls = tree_cons (NULL_TREE, restmp, cfun->local_decls);
1523 BLOCK_VARS (DECL_INITIAL (current_function_decl)) = restmp;
1526 restmp = create_tmp_var_raw (restype, "retval");
1529 for (arg = a; arg; arg = TREE_CHAIN (arg))
1531 vargs = VEC_alloc (tree, heap, nargs);
1533 VEC_quick_push (tree, vargs,
1538 VEC_quick_push (tree, vargs, a);
1539 for (i = 1, arg = TREE_CHAIN (a); i < nargs; i++, arg = TREE_CHAIN (arg))
1540 VEC_quick_push (tree, vargs, arg);
1541 call = gimple_build_call_vec (build_fold_addr_expr_loc (0, alias), vargs);
1542 VEC_free (tree, heap, vargs);
1543 gimple_call_set_cannot_inline (call, true);
1544 gimple_call_set_from_thunk (call, true);
1546 gimple_call_set_lhs (call, restmp);
1547 gsi_insert_after (&bsi, call, GSI_NEW_STMT);
1548 mark_symbols_for_renaming (call);
1549 find_referenced_vars_in (call);
1552 if (restmp && !this_adjusting)
1554 tree true_label = NULL_TREE;
1556 if (TREE_CODE (TREE_TYPE (restmp)) == POINTER_TYPE)
1559 /* If the return type is a pointer, we need to
1560 protect against NULL. We know there will be an
1561 adjustment, because that's why we're emitting a
1563 then_bb = create_basic_block (NULL, (void *) 0, bb);
1564 return_bb = create_basic_block (NULL, (void *) 0, then_bb);
1565 else_bb = create_basic_block (NULL, (void *) 0, else_bb);
1566 remove_edge (single_succ_edge (bb));
1567 true_label = gimple_block_label (then_bb);
1568 stmt = gimple_build_cond (NE_EXPR, restmp,
1569 fold_convert (TREE_TYPE (restmp),
1571 NULL_TREE, NULL_TREE);
1572 gsi_insert_after (&bsi, stmt, GSI_NEW_STMT);
1573 make_edge (bb, then_bb, EDGE_TRUE_VALUE);
1574 make_edge (bb, else_bb, EDGE_FALSE_VALUE);
1575 make_edge (return_bb, EXIT_BLOCK_PTR, 0);
1576 make_edge (then_bb, return_bb, EDGE_FALLTHRU);
1577 make_edge (else_bb, return_bb, EDGE_FALLTHRU);
1578 bsi = gsi_last_bb (then_bb);
1581 restmp = thunk_adjust (&bsi, restmp, /*this_adjusting=*/0,
1582 fixed_offset, virtual_offset);
1586 bsi = gsi_last_bb (else_bb);
1587 stmt = gimple_build_assign (restmp, fold_convert (TREE_TYPE (restmp),
1588 integer_zero_node));
1589 gsi_insert_after (&bsi, stmt, GSI_NEW_STMT);
1590 bsi = gsi_last_bb (return_bb);
1594 gimple_call_set_tail (call, true);
1596 /* Build return value. */
1597 ret = gimple_build_return (restmp);
1598 gsi_insert_after (&bsi, ret, GSI_NEW_STMT);
1600 delete_unreachable_blocks ();
1601 update_ssa (TODO_update_ssa);
1603 cgraph_remove_same_body_alias (node);
1604 /* Since we want to emit the thunk, we explicitly mark its name as
1606 cgraph_add_new_function (thunk_fndecl, true);
1607 bitmap_obstack_release (NULL);
1609 current_function_decl = NULL;
1612 /* Expand function specified by NODE. */
1615 cgraph_expand_function (struct cgraph_node *node)
1617 tree decl = node->decl;
1619 /* We ought to not compile any inline clones. */
1620 gcc_assert (!node->global.inlined_to);
1622 announce_function (decl);
1625 gcc_assert (node->lowered);
1627 /* Generate RTL for the body of DECL. */
1628 tree_rest_of_compilation (decl);
1630 /* Make sure that BE didn't give up on compiling. */
1631 gcc_assert (TREE_ASM_WRITTEN (decl));
1632 current_function_decl = NULL;
1633 if (node->same_body)
1635 struct cgraph_node *alias, *next;
1636 bool saved_alias = node->alias;
1637 for (alias = node->same_body;
1638 alias && alias->next; alias = alias->next)
1640 /* Walk aliases in the order they were created; it is possible that
1641 thunks reffers to the aliases made earlier. */
1642 for (; alias; alias = next)
1644 next = alias->previous;
1645 if (!alias->thunk.thunk_p)
1646 assemble_alias (alias->decl,
1647 DECL_ASSEMBLER_NAME (alias->thunk.alias));
1649 assemble_thunk (alias);
1651 node->alias = saved_alias;
1653 gcc_assert (!cgraph_preserve_function_body_p (decl));
1654 cgraph_release_function_body (node);
1655 /* Eliminate all call edges. This is important so the GIMPLE_CALL no longer
1656 points to the dead function body. */
1657 cgraph_node_remove_callees (node);
1659 cgraph_function_flags_ready = true;
1662 /* Return true when CALLER_DECL should be inlined into CALLEE_DECL. */
1665 cgraph_inline_p (struct cgraph_edge *e, cgraph_inline_failed_t *reason)
1667 *reason = e->inline_failed;
1668 return !e->inline_failed;
1673 /* Expand all functions that must be output.
1675 Attempt to topologically sort the nodes so function is output when
1676 all called functions are already assembled to allow data to be
1677 propagated across the callgraph. Use a stack to get smaller distance
1678 between a function and its callees (later we may choose to use a more
1679 sophisticated algorithm for function reordering; we will likely want
1680 to use subsections to make the output functions appear in top-down
1684 cgraph_expand_all_functions (void)
1686 struct cgraph_node *node;
1687 struct cgraph_node **order = XCNEWVEC (struct cgraph_node *, cgraph_n_nodes);
1688 int order_pos, new_order_pos = 0;
1691 order_pos = cgraph_postorder (order);
1692 gcc_assert (order_pos == cgraph_n_nodes);
1694 /* Garbage collector may remove inline clones we eliminate during
1695 optimization. So we must be sure to not reference them. */
1696 for (i = 0; i < order_pos; i++)
1697 if (order[i]->process)
1698 order[new_order_pos++] = order[i];
1700 for (i = new_order_pos - 1; i >= 0; i--)
1705 gcc_assert (node->reachable);
1707 cgraph_expand_function (node);
1710 cgraph_process_new_functions ();
1716 /* This is used to sort the node types by the cgraph order number. */
1718 enum cgraph_order_sort_kind
1720 ORDER_UNDEFINED = 0,
1726 struct cgraph_order_sort
1728 enum cgraph_order_sort_kind kind;
1731 struct cgraph_node *f;
1732 struct varpool_node *v;
1733 struct cgraph_asm_node *a;
1737 /* Output all functions, variables, and asm statements in the order
1738 according to their order fields, which is the order in which they
1739 appeared in the file. This implements -fno-toplevel-reorder. In
1740 this mode we may output functions and variables which don't really
1741 need to be output. */
1744 cgraph_output_in_order (void)
1747 struct cgraph_order_sort *nodes;
1749 struct cgraph_node *pf;
1750 struct varpool_node *pv;
1751 struct cgraph_asm_node *pa;
1754 nodes = XCNEWVEC (struct cgraph_order_sort, max);
1756 varpool_analyze_pending_decls ();
1758 for (pf = cgraph_nodes; pf; pf = pf->next)
1763 gcc_assert (nodes[i].kind == ORDER_UNDEFINED);
1764 nodes[i].kind = ORDER_FUNCTION;
1769 for (pv = varpool_nodes_queue; pv; pv = pv->next_needed)
1772 gcc_assert (nodes[i].kind == ORDER_UNDEFINED);
1773 nodes[i].kind = ORDER_VAR;
1777 for (pa = cgraph_asm_nodes; pa; pa = pa->next)
1780 gcc_assert (nodes[i].kind == ORDER_UNDEFINED);
1781 nodes[i].kind = ORDER_ASM;
1785 /* In toplevel reorder mode we output all statics; mark them as needed. */
1786 for (i = 0; i < max; ++i)
1788 if (nodes[i].kind == ORDER_VAR)
1790 varpool_mark_needed_node (nodes[i].u.v);
1793 varpool_empty_needed_queue ();
1795 for (i = 0; i < max; ++i)
1797 switch (nodes[i].kind)
1799 case ORDER_FUNCTION:
1800 nodes[i].u.f->process = 0;
1801 cgraph_expand_function (nodes[i].u.f);
1805 varpool_assemble_decl (nodes[i].u.v);
1809 assemble_asm (nodes[i].u.a->asm_str);
1812 case ORDER_UNDEFINED:
1820 cgraph_asm_nodes = NULL;
1824 /* Return true when function body of DECL still needs to be kept around
1825 for later re-use. */
1827 cgraph_preserve_function_body_p (tree decl)
1829 struct cgraph_node *node;
1831 gcc_assert (cgraph_global_info_ready);
1832 /* Look if there is any clone around. */
1833 node = cgraph_node (decl);
1843 current_function_decl = NULL;
1844 gimple_register_cfg_hooks ();
1845 bitmap_obstack_initialize (NULL);
1847 invoke_plugin_callbacks (PLUGIN_ALL_IPA_PASSES_START, NULL);
1850 execute_ipa_pass_list (all_small_ipa_passes);
1852 /* If pass_all_early_optimizations was not scheduled, the state of
1853 the cgraph will not be properly updated. Update it now. */
1854 if (cgraph_state < CGRAPH_STATE_IPA_SSA)
1855 cgraph_state = CGRAPH_STATE_IPA_SSA;
1859 /* Generate coverage variables and constructors. */
1862 /* Process new functions added. */
1864 current_function_decl = NULL;
1865 cgraph_process_new_functions ();
1867 execute_ipa_summary_passes
1868 ((struct ipa_opt_pass_d *) all_regular_ipa_passes);
1871 /* Some targets need to handle LTO assembler output specially. */
1872 if (flag_generate_lto)
1873 targetm.asm_out.lto_start ();
1875 execute_ipa_summary_passes ((struct ipa_opt_pass_d *) all_lto_gen_passes);
1878 ipa_write_summaries ();
1880 if (flag_generate_lto)
1881 targetm.asm_out.lto_end ();
1884 execute_ipa_pass_list (all_regular_ipa_passes);
1885 invoke_plugin_callbacks (PLUGIN_ALL_IPA_PASSES_END, NULL);
1887 bitmap_obstack_release (NULL);
1891 /* Perform simple optimizations based on callgraph. */
1894 cgraph_optimize (void)
1896 if (errorcount || sorrycount)
1899 #ifdef ENABLE_CHECKING
1903 /* Frontend may output common variables after the unit has been finalized.
1904 It is safe to deal with them here as they are always zero initialized. */
1905 varpool_analyze_pending_decls ();
1907 timevar_push (TV_CGRAPHOPT);
1908 if (pre_ipa_mem_report)
1910 fprintf (stderr, "Memory consumption before IPA\n");
1911 dump_memory_report (false);
1914 fprintf (stderr, "Performing interprocedural optimizations\n");
1915 cgraph_state = CGRAPH_STATE_IPA;
1917 /* Don't run the IPA passes if there was any error or sorry messages. */
1918 if (errorcount == 0 && sorrycount == 0)
1921 /* Do nothing else if any IPA pass found errors. */
1922 if (errorcount || sorrycount)
1924 timevar_pop (TV_CGRAPHOPT);
1928 /* This pass remove bodies of extern inline functions we never inlined.
1929 Do this later so other IPA passes see what is really going on. */
1930 cgraph_remove_unreachable_nodes (false, dump_file);
1931 cgraph_global_info_ready = true;
1932 if (cgraph_dump_file)
1934 fprintf (cgraph_dump_file, "Optimized ");
1935 dump_cgraph (cgraph_dump_file);
1936 dump_varpool (cgraph_dump_file);
1938 if (post_ipa_mem_report)
1940 fprintf (stderr, "Memory consumption after IPA\n");
1941 dump_memory_report (false);
1943 timevar_pop (TV_CGRAPHOPT);
1945 /* Output everything. */
1946 (*debug_hooks->assembly_start) ();
1948 fprintf (stderr, "Assembling functions:\n");
1949 #ifdef ENABLE_CHECKING
1953 cgraph_materialize_all_clones ();
1954 cgraph_mark_functions_to_output ();
1956 cgraph_state = CGRAPH_STATE_EXPANSION;
1957 if (!flag_toplevel_reorder)
1958 cgraph_output_in_order ();
1961 cgraph_output_pending_asms ();
1963 cgraph_expand_all_functions ();
1964 varpool_remove_unreferenced_decls ();
1966 varpool_assemble_pending_decls ();
1968 cgraph_process_new_functions ();
1969 cgraph_state = CGRAPH_STATE_FINISHED;
1971 if (cgraph_dump_file)
1973 fprintf (cgraph_dump_file, "\nFinal ");
1974 dump_cgraph (cgraph_dump_file);
1976 #ifdef ENABLE_CHECKING
1978 /* Double check that all inline clones are gone and that all
1979 function bodies have been released from memory. */
1980 if (!(sorrycount || errorcount))
1982 struct cgraph_node *node;
1983 bool error_found = false;
1985 for (node = cgraph_nodes; node; node = node->next)
1987 && (node->global.inlined_to
1988 || gimple_has_body_p (node->decl)))
1991 dump_cgraph_node (stderr, node);
1994 internal_error ("nodes with unreleased memory found");
2000 /* Generate and emit a static constructor or destructor. WHICH must
2001 be one of 'I' (for a constructor) or 'D' (for a destructor). BODY
2002 is a STATEMENT_LIST containing GENERIC statements. PRIORITY is the
2003 initialization priority for this constructor or destructor. */
2006 cgraph_build_static_cdtor (char which, tree body, int priority)
2008 static int counter = 0;
2010 tree decl, name, resdecl;
2012 /* The priority is encoded in the constructor or destructor name.
2013 collect2 will sort the names and arrange that they are called at
2015 sprintf (which_buf, "%c_%.5d_%d", which, priority, counter++);
2016 name = get_file_function_name (which_buf);
2018 decl = build_decl (input_location, FUNCTION_DECL, name,
2019 build_function_type (void_type_node, void_list_node));
2020 current_function_decl = decl;
2022 resdecl = build_decl (input_location,
2023 RESULT_DECL, NULL_TREE, void_type_node);
2024 DECL_ARTIFICIAL (resdecl) = 1;
2025 DECL_RESULT (decl) = resdecl;
2026 DECL_CONTEXT (resdecl) = decl;
2028 allocate_struct_function (decl, false);
2030 TREE_STATIC (decl) = 1;
2031 TREE_USED (decl) = 1;
2032 DECL_ARTIFICIAL (decl) = 1;
2033 DECL_NO_INSTRUMENT_FUNCTION_ENTRY_EXIT (decl) = 1;
2034 DECL_SAVED_TREE (decl) = body;
2035 if (!targetm.have_ctors_dtors)
2037 TREE_PUBLIC (decl) = 1;
2038 DECL_PRESERVE_P (decl) = 1;
2040 DECL_UNINLINABLE (decl) = 1;
2042 DECL_INITIAL (decl) = make_node (BLOCK);
2043 TREE_USED (DECL_INITIAL (decl)) = 1;
2045 DECL_SOURCE_LOCATION (decl) = input_location;
2046 cfun->function_end_locus = input_location;
2051 DECL_STATIC_CONSTRUCTOR (decl) = 1;
2052 decl_init_priority_insert (decl, priority);
2055 DECL_STATIC_DESTRUCTOR (decl) = 1;
2056 decl_fini_priority_insert (decl, priority);
2062 gimplify_function_tree (decl);
2064 cgraph_add_new_function (decl, false);
2065 cgraph_mark_needed_node (cgraph_node (decl));
2072 cgraph_dump_file = dump_begin (TDI_cgraph, NULL);
2075 /* The edges representing the callers of the NEW_VERSION node were
2076 fixed by cgraph_function_versioning (), now the call_expr in their
2077 respective tree code should be updated to call the NEW_VERSION. */
2080 update_call_expr (struct cgraph_node *new_version)
2082 struct cgraph_edge *e;
2084 gcc_assert (new_version);
2086 /* Update the call expr on the edges to call the new version. */
2087 for (e = new_version->callers; e; e = e->next_caller)
2089 struct function *inner_function = DECL_STRUCT_FUNCTION (e->caller->decl);
2090 gimple_call_set_fndecl (e->call_stmt, new_version->decl);
2091 maybe_clean_eh_stmt_fn (inner_function, e->call_stmt);
2096 /* Create a new cgraph node which is the new version of
2097 OLD_VERSION node. REDIRECT_CALLERS holds the callers
2098 edges which should be redirected to point to
2099 NEW_VERSION. ALL the callees edges of OLD_VERSION
2100 are cloned to the new version node. Return the new
2103 static struct cgraph_node *
2104 cgraph_copy_node_for_versioning (struct cgraph_node *old_version,
2106 VEC(cgraph_edge_p,heap) *redirect_callers)
2108 struct cgraph_node *new_version;
2109 struct cgraph_edge *e;
2110 struct cgraph_edge *next_callee;
2113 gcc_assert (old_version);
2115 new_version = cgraph_node (new_decl);
2117 new_version->analyzed = true;
2118 new_version->local = old_version->local;
2119 new_version->global = old_version->global;
2120 new_version->rtl = new_version->rtl;
2121 new_version->reachable = true;
2122 new_version->count = old_version->count;
2124 /* Clone the old node callees. Recursive calls are
2126 for (e = old_version->callees;e; e=e->next_callee)
2128 cgraph_clone_edge (e, new_version, e->call_stmt,
2129 e->lto_stmt_uid, REG_BR_PROB_BASE,
2131 e->loop_nest, true);
2133 /* Fix recursive calls.
2134 If OLD_VERSION has a recursive call after the
2135 previous edge cloning, the new version will have an edge
2136 pointing to the old version, which is wrong;
2137 Redirect it to point to the new version. */
2138 for (e = new_version->callees ; e; e = next_callee)
2140 next_callee = e->next_callee;
2141 if (e->callee == old_version)
2142 cgraph_redirect_edge_callee (e, new_version);
2147 for (i = 0; VEC_iterate (cgraph_edge_p, redirect_callers, i, e); i++)
2149 /* Redirect calls to the old version node to point to its new
2151 cgraph_redirect_edge_callee (e, new_version);
2157 /* Perform function versioning.
2158 Function versioning includes copying of the tree and
2159 a callgraph update (creating a new cgraph node and updating
2160 its callees and callers).
2162 REDIRECT_CALLERS varray includes the edges to be redirected
2165 TREE_MAP is a mapping of tree nodes we want to replace with
2166 new ones (according to results of prior analysis).
2167 OLD_VERSION_NODE is the node that is versioned.
2168 It returns the new version's cgraph node.
2169 ARGS_TO_SKIP lists arguments to be omitted from functions
2172 struct cgraph_node *
2173 cgraph_function_versioning (struct cgraph_node *old_version_node,
2174 VEC(cgraph_edge_p,heap) *redirect_callers,
2175 VEC (ipa_replace_map_p,gc)* tree_map,
2176 bitmap args_to_skip)
2178 tree old_decl = old_version_node->decl;
2179 struct cgraph_node *new_version_node = NULL;
2182 if (!tree_versionable_function_p (old_decl))
2185 /* Make a new FUNCTION_DECL tree node for the
2188 new_decl = copy_node (old_decl);
2190 new_decl = build_function_decl_skip_args (old_decl, args_to_skip);
2192 /* Create the new version's call-graph node.
2193 and update the edges of the new node. */
2195 cgraph_copy_node_for_versioning (old_version_node, new_decl,
2198 /* Copy the OLD_VERSION_NODE function tree to the new version. */
2199 tree_function_versioning (old_decl, new_decl, tree_map, false, args_to_skip);
2201 /* Update the new version's properties.
2202 Make The new version visible only within this translation unit. Make sure
2203 that is not weak also.
2204 ??? We cannot use COMDAT linkage because there is no
2205 ABI support for this. */
2206 cgraph_make_decl_local (new_version_node->decl);
2207 DECL_VIRTUAL_P (new_version_node->decl) = 0;
2208 new_version_node->local.externally_visible = 0;
2209 new_version_node->local.local = 1;
2210 new_version_node->lowered = true;
2212 /* Update the call_expr on the edges to call the new version node. */
2213 update_call_expr (new_version_node);
2215 cgraph_call_function_insertion_hooks (new_version_node);
2216 return new_version_node;
2219 /* Produce separate function body for inline clones so the offline copy can be
2220 modified without affecting them. */
2221 struct cgraph_node *
2222 save_inline_function_body (struct cgraph_node *node)
2224 struct cgraph_node *first_clone, *n;
2226 gcc_assert (node == cgraph_node (node->decl));
2228 cgraph_lower_function (node);
2230 first_clone = node->clones;
2232 first_clone->decl = copy_node (node->decl);
2233 cgraph_insert_node_to_hashtable (first_clone);
2234 gcc_assert (first_clone == cgraph_node (first_clone->decl));
2235 if (first_clone->next_sibling_clone)
2237 for (n = first_clone->next_sibling_clone; n->next_sibling_clone; n = n->next_sibling_clone)
2238 n->clone_of = first_clone;
2239 n->clone_of = first_clone;
2240 n->next_sibling_clone = first_clone->clones;
2241 if (first_clone->clones)
2242 first_clone->clones->prev_sibling_clone = n;
2243 first_clone->clones = first_clone->next_sibling_clone;
2244 first_clone->next_sibling_clone->prev_sibling_clone = NULL;
2245 first_clone->next_sibling_clone = NULL;
2246 gcc_assert (!first_clone->prev_sibling_clone);
2248 first_clone->clone_of = NULL;
2249 node->clones = NULL;
2251 if (first_clone->clones)
2252 for (n = first_clone->clones; n != first_clone;)
2254 gcc_assert (n->decl == node->decl);
2255 n->decl = first_clone->decl;
2258 else if (n->next_sibling_clone)
2259 n = n->next_sibling_clone;
2262 while (n != first_clone && !n->next_sibling_clone)
2264 if (n != first_clone)
2265 n = n->next_sibling_clone;
2269 /* Copy the OLD_VERSION_NODE function tree to the new version. */
2270 tree_function_versioning (node->decl, first_clone->decl, NULL, true, NULL);
2272 DECL_EXTERNAL (first_clone->decl) = 0;
2273 DECL_COMDAT_GROUP (first_clone->decl) = NULL_TREE;
2274 TREE_PUBLIC (first_clone->decl) = 0;
2275 DECL_COMDAT (first_clone->decl) = 0;
2276 VEC_free (ipa_opt_pass, heap,
2277 first_clone->ipa_transforms_to_apply);
2278 first_clone->ipa_transforms_to_apply = NULL;
2280 #ifdef ENABLE_CHECKING
2281 verify_cgraph_node (first_clone);
2286 /* Given virtual clone, turn it into actual clone. */
2288 cgraph_materialize_clone (struct cgraph_node *node)
2290 bitmap_obstack_initialize (NULL);
2291 #ifdef ENABLE_CHECKING
2292 node->former_clone_of = node->clone_of->decl;
2293 if (node->clone_of->former_clone_of)
2294 node->former_clone_of = node->clone_of->former_clone_of;
2296 /* Copy the OLD_VERSION_NODE function tree to the new version. */
2297 tree_function_versioning (node->clone_of->decl, node->decl,
2298 node->clone.tree_map, true,
2299 node->clone.args_to_skip);
2300 if (cgraph_dump_file)
2302 dump_function_to_file (node->clone_of->decl, cgraph_dump_file, dump_flags);
2303 dump_function_to_file (node->decl, cgraph_dump_file, dump_flags);
2306 /* Function is no longer clone. */
2307 if (node->next_sibling_clone)
2308 node->next_sibling_clone->prev_sibling_clone = node->prev_sibling_clone;
2309 if (node->prev_sibling_clone)
2310 node->prev_sibling_clone->next_sibling_clone = node->next_sibling_clone;
2312 node->clone_of->clones = node->next_sibling_clone;
2313 node->next_sibling_clone = NULL;
2314 node->prev_sibling_clone = NULL;
2315 if (!node->clone_of->analyzed && !node->clone_of->clones)
2316 cgraph_remove_node (node->clone_of);
2317 node->clone_of = NULL;
2318 bitmap_obstack_release (NULL);
2321 /* If necessary, change the function declaration in the call statement
2322 associated with E so that it corresponds to the edge callee. */
2325 cgraph_redirect_edge_call_stmt_to_callee (struct cgraph_edge *e)
2327 tree decl = gimple_call_fndecl (e->call_stmt);
2329 gimple_stmt_iterator gsi;
2331 if (!decl || decl == e->callee->decl
2332 /* Don't update call from same body alias to the real function. */
2333 || cgraph_get_node (decl) == cgraph_get_node (e->callee->decl))
2334 return e->call_stmt;
2336 gcc_assert (!cgraph_node (decl)->clone.combined_args_to_skip);
2338 if (cgraph_dump_file)
2340 fprintf (cgraph_dump_file, "updating call of %s/%i -> %s/%i: ",
2341 cgraph_node_name (e->caller), e->caller->uid,
2342 cgraph_node_name (e->callee), e->callee->uid);
2343 print_gimple_stmt (cgraph_dump_file, e->call_stmt, 0, dump_flags);
2344 if (e->callee->clone.combined_args_to_skip)
2346 fprintf (cgraph_dump_file, " combined args to skip: ");
2347 dump_bitmap (cgraph_dump_file, e->callee->clone.combined_args_to_skip);
2351 if (e->callee->clone.combined_args_to_skip)
2352 new_stmt = gimple_call_copy_skip_args (e->call_stmt,
2353 e->callee->clone.combined_args_to_skip);
2355 new_stmt = e->call_stmt;
2356 if (gimple_vdef (new_stmt)
2357 && TREE_CODE (gimple_vdef (new_stmt)) == SSA_NAME)
2358 SSA_NAME_DEF_STMT (gimple_vdef (new_stmt)) = new_stmt;
2359 gimple_call_set_fndecl (new_stmt, e->callee->decl);
2361 gsi = gsi_for_stmt (e->call_stmt);
2362 gsi_replace (&gsi, new_stmt, true);
2363 update_stmt (new_stmt);
2365 /* Update EH information too, just in case. */
2366 maybe_clean_or_replace_eh_stmt (e->call_stmt, new_stmt);
2368 cgraph_set_call_stmt_including_clones (e->caller, e->call_stmt, new_stmt);
2370 if (cgraph_dump_file)
2372 fprintf (cgraph_dump_file, " updated to:");
2373 print_gimple_stmt (cgraph_dump_file, e->call_stmt, 0, dump_flags);
2378 /* Once all functions from compilation unit are in memory, produce all clones
2379 and update all calls. We might also do this on demand if we don't want to
2380 bring all functions to memory prior compilation, but current WHOPR
2381 implementation does that and it is is bit easier to keep everything right in
2384 cgraph_materialize_all_clones (void)
2386 struct cgraph_node *node;
2387 bool stabilized = false;
2389 if (cgraph_dump_file)
2390 fprintf (cgraph_dump_file, "Materializing clones\n");
2391 #ifdef ENABLE_CHECKING
2395 /* We can also do topological order, but number of iterations should be
2396 bounded by number of IPA passes since single IPA pass is probably not
2397 going to create clones of clones it created itself. */
2401 for (node = cgraph_nodes; node; node = node->next)
2403 if (node->clone_of && node->decl != node->clone_of->decl
2404 && !gimple_has_body_p (node->decl))
2406 if (gimple_has_body_p (node->clone_of->decl))
2408 if (cgraph_dump_file)
2410 fprintf (cgraph_dump_file, "clonning %s to %s\n",
2411 cgraph_node_name (node->clone_of),
2412 cgraph_node_name (node));
2413 if (node->clone.tree_map)
2416 fprintf (cgraph_dump_file, " replace map: ");
2417 for (i = 0; i < VEC_length (ipa_replace_map_p,
2418 node->clone.tree_map);
2421 struct ipa_replace_map *replace_info;
2422 replace_info = VEC_index (ipa_replace_map_p,
2423 node->clone.tree_map,
2425 print_generic_expr (cgraph_dump_file, replace_info->old_tree, 0);
2426 fprintf (cgraph_dump_file, " -> ");
2427 print_generic_expr (cgraph_dump_file, replace_info->new_tree, 0);
2428 fprintf (cgraph_dump_file, "%s%s;",
2429 replace_info->replace_p ? "(replace)":"",
2430 replace_info->ref_p ? "(ref)":"");
2432 fprintf (cgraph_dump_file, "\n");
2434 if (node->clone.args_to_skip)
2436 fprintf (cgraph_dump_file, " args_to_skip: ");
2437 dump_bitmap (cgraph_dump_file, node->clone.args_to_skip);
2439 if (node->clone.args_to_skip)
2441 fprintf (cgraph_dump_file, " combined_args_to_skip:");
2442 dump_bitmap (cgraph_dump_file, node->clone.combined_args_to_skip);
2445 cgraph_materialize_clone (node);
2451 for (node = cgraph_nodes; node; node = node->next)
2452 if (!node->analyzed && node->callees)
2453 cgraph_node_remove_callees (node);
2454 if (cgraph_dump_file)
2455 fprintf (cgraph_dump_file, "Materialization Call site updates done.\n");
2456 #ifdef ENABLE_CHECKING
2459 cgraph_remove_unreachable_nodes (false, cgraph_dump_file);
2462 #include "gt-cgraphunit.h"