1 /* Callgraph based interprocedural optimizations.
2 Copyright (C) 2003, 2004, 2005, 2006, 2007, 2008, 2009, 2010
3 Free Software Foundation, Inc.
4 Contributed by Jan Hubicka
6 This file is part of GCC.
8 GCC is free software; you can redistribute it and/or modify it under
9 the terms of the GNU General Public License as published by the Free
10 Software Foundation; either version 3, or (at your option) any later
13 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
14 WARRANTY; without even the implied warranty of MERCHANTABILITY or
15 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
18 You should have received a copy of the GNU General Public License
19 along with GCC; see the file COPYING3. If not see
20 <http://www.gnu.org/licenses/>. */
22 /* This module implements main driver of compilation process as well as
23 few basic interprocedural optimizers.
25 The main scope of this file is to act as an interface in between
26 tree based frontends and the backend (and middle end)
28 The front-end is supposed to use following functionality:
30 - cgraph_finalize_function
32 This function is called once front-end has parsed whole body of function
33 and it is certain that the function body nor the declaration will change.
35 (There is one exception needed for implementing GCC extern inline
38 - varpool_finalize_variable
40 This function has same behavior as the above but is used for static
43 - cgraph_finalize_compilation_unit
45 This function is called once (source level) compilation unit is finalized
46 and it will no longer change.
48 In the the call-graph construction and local function
49 analysis takes place here. Bodies of unreachable functions are released
50 to conserve memory usage.
52 The function can be called multiple times when multiple source level
53 compilation units are combined (such as in C frontend)
57 In this unit-at-a-time compilation the intra procedural analysis takes
58 place here. In particular the static functions whose address is never
59 taken are marked as local. Backend can then use this information to
60 modify calling conventions, do better inlining or similar optimizations.
62 - cgraph_mark_needed_node
63 - varpool_mark_needed_node
65 When function or variable is referenced by some hidden way the call-graph
66 data structure must be updated accordingly by this function.
67 There should be little need to call this function and all the references
68 should be made explicit to cgraph code. At present these functions are
69 used by C++ frontend to explicitly mark the keyed methods.
71 - analyze_expr callback
73 This function is responsible for lowering tree nodes not understood by
74 generic code into understandable ones or alternatively marking
75 callgraph and varpool nodes referenced by the as needed.
77 ??? On the tree-ssa genericizing should take place here and we will avoid
78 need for these hooks (replacing them by genericizing hook)
80 Analyzing of all functions is deferred
81 to cgraph_finalize_compilation_unit and expansion into cgraph_optimize.
83 In cgraph_finalize_compilation_unit the reachable functions are
84 analyzed. During analysis the call-graph edges from reachable
85 functions are constructed and their destinations are marked as
86 reachable. References to functions and variables are discovered too
87 and variables found to be needed output to the assembly file. Via
88 mark_referenced call in assemble_variable functions referenced by
89 static variables are noticed too.
91 The intra-procedural information is produced and its existence
92 indicated by global_info_ready. Once this flag is set it is impossible
93 to change function from !reachable to reachable and thus
94 assemble_variable no longer call mark_referenced.
96 Finally the call-graph is topologically sorted and all reachable functions
97 that has not been completely inlined or are not external are output.
99 ??? It is possible that reference to function or variable is optimized
100 out. We can not deal with this nicely because topological order is not
101 suitable for it. For tree-ssa we may consider another pass doing
102 optimization and re-discovering reachable functions.
104 ??? Reorganize code so variables are output very last and only if they
105 really has been referenced by produced code, so we catch more cases
106 where reference has been optimized out. */
111 #include "coretypes.h"
115 #include "tree-flow.h"
116 #include "tree-inline.h"
117 #include "langhooks.h"
118 #include "pointer-set.h"
125 #include "diagnostic.h"
126 #include "tree-pretty-print.h"
127 #include "gimple-pretty-print.h"
132 #include "function.h"
133 #include "ipa-prop.h"
135 #include "tree-iterator.h"
136 #include "tree-pass.h"
137 #include "tree-dump.h"
139 #include "coverage.h"
142 static void cgraph_expand_all_functions (void);
143 static void cgraph_mark_functions_to_output (void);
144 static void cgraph_expand_function (struct cgraph_node *);
145 static void cgraph_output_pending_asms (void);
146 static void cgraph_analyze_function (struct cgraph_node *);
148 FILE *cgraph_dump_file;
150 /* Used for vtable lookup in thunk adjusting. */
151 static GTY (()) tree vtable_entry_type;
153 /* Determine if function DECL is needed. That is, visible to something
154 either outside this translation unit, something magic in the system
158 cgraph_decide_is_function_needed (struct cgraph_node *node, tree decl)
160 /* If the user told us it is used, then it must be so. */
161 if (node->local.externally_visible)
164 /* ??? If the assembler name is set by hand, it is possible to assemble
165 the name later after finalizing the function and the fact is noticed
166 in assemble_name then. This is arguably a bug. */
167 if (DECL_ASSEMBLER_NAME_SET_P (decl)
168 && TREE_SYMBOL_REFERENCED (DECL_ASSEMBLER_NAME (decl)))
171 /* With -fkeep-inline-functions we are keeping all inline functions except
172 for extern inline ones. */
173 if (flag_keep_inline_functions
174 && DECL_DECLARED_INLINE_P (decl)
175 && !DECL_EXTERNAL (decl)
176 && !lookup_attribute ("always_inline", DECL_ATTRIBUTES (decl)))
179 /* If we decided it was needed before, but at the time we didn't have
180 the body of the function available, then it's still needed. We have
181 to go back and re-check its dependencies now. */
185 /* Externally visible functions must be output. The exception is
186 COMDAT functions that must be output only when they are needed.
188 When not optimizing, also output the static functions. (see
189 PR24561), but don't do so for always_inline functions, functions
190 declared inline and nested functions. These were optimized out
191 in the original implementation and it is unclear whether we want
192 to change the behavior here. */
193 if (((TREE_PUBLIC (decl)
195 && !node->local.disregard_inline_limits
196 && !DECL_DECLARED_INLINE_P (decl)
197 && !(DECL_CONTEXT (decl)
198 && TREE_CODE (DECL_CONTEXT (decl)) == FUNCTION_DECL)))
199 && !flag_whole_program
202 && !DECL_COMDAT (decl) && !DECL_EXTERNAL (decl))
208 /* Process CGRAPH_NEW_FUNCTIONS and perform actions necessary to add these
209 functions into callgraph in a way so they look like ordinary reachable
210 functions inserted into callgraph already at construction time. */
213 cgraph_process_new_functions (void)
217 struct cgraph_node *node;
219 varpool_analyze_pending_decls ();
220 /* Note that this queue may grow as its being processed, as the new
221 functions may generate new ones. */
222 while (cgraph_new_nodes)
224 node = cgraph_new_nodes;
226 cgraph_new_nodes = cgraph_new_nodes->next_needed;
227 switch (cgraph_state)
229 case CGRAPH_STATE_CONSTRUCTION:
230 /* At construction time we just need to finalize function and move
231 it into reachable functions list. */
233 node->next_needed = NULL;
234 cgraph_finalize_function (fndecl, false);
235 cgraph_mark_reachable_node (node);
239 case CGRAPH_STATE_IPA:
240 case CGRAPH_STATE_IPA_SSA:
241 /* When IPA optimization already started, do all essential
242 transformations that has been already performed on the whole
243 cgraph but not on this function. */
245 gimple_register_cfg_hooks ();
247 cgraph_analyze_function (node);
248 push_cfun (DECL_STRUCT_FUNCTION (fndecl));
249 current_function_decl = fndecl;
250 compute_inline_parameters (node);
251 if ((cgraph_state == CGRAPH_STATE_IPA_SSA
252 && !gimple_in_ssa_p (DECL_STRUCT_FUNCTION (fndecl)))
253 /* When not optimizing, be sure we run early local passes anyway
256 execute_pass_list (pass_early_local_passes.pass.sub);
257 free_dominance_info (CDI_POST_DOMINATORS);
258 free_dominance_info (CDI_DOMINATORS);
260 current_function_decl = NULL;
263 case CGRAPH_STATE_EXPANSION:
264 /* Functions created during expansion shall be compiled
267 cgraph_expand_function (node);
274 cgraph_call_function_insertion_hooks (node);
275 varpool_analyze_pending_decls ();
280 /* As an GCC extension we allow redefinition of the function. The
281 semantics when both copies of bodies differ is not well defined.
282 We replace the old body with new body so in unit at a time mode
283 we always use new body, while in normal mode we may end up with
284 old body inlined into some functions and new body expanded and
287 ??? It may make more sense to use one body for inlining and other
288 body for expanding the function but this is difficult to do. */
291 cgraph_reset_node (struct cgraph_node *node)
293 /* If node->process is set, then we have already begun whole-unit analysis.
294 This is *not* testing for whether we've already emitted the function.
295 That case can be sort-of legitimately seen with real function redefinition
296 errors. I would argue that the front end should never present us with
297 such a case, but don't enforce that for now. */
298 gcc_assert (!node->process);
300 /* Reset our data structures so we can analyze the function again. */
301 memset (&node->local, 0, sizeof (node->local));
302 memset (&node->global, 0, sizeof (node->global));
303 memset (&node->rtl, 0, sizeof (node->rtl));
304 node->analyzed = false;
305 node->local.redefined_extern_inline = true;
306 node->local.finalized = false;
308 cgraph_node_remove_callees (node);
310 /* We may need to re-queue the node for assembling in case
311 we already proceeded it and ignored as not needed or got
312 a re-declaration in IMA mode. */
315 struct cgraph_node *n;
317 for (n = cgraph_nodes_queue; n; n = n->next_needed)
326 cgraph_lower_function (struct cgraph_node *node)
332 lower_nested_functions (node->decl);
333 gcc_assert (!node->nested);
335 tree_lowering_passes (node->decl);
336 node->lowered = true;
339 /* DECL has been parsed. Take it, queue it, compile it at the whim of the
340 logic in effect. If NESTED is true, then our caller cannot stand to have
341 the garbage collector run at the moment. We would need to either create
342 a new GC context, or just not compile right now. */
345 cgraph_finalize_function (tree decl, bool nested)
347 struct cgraph_node *node = cgraph_node (decl);
349 if (node->local.finalized)
350 cgraph_reset_node (node);
352 node->pid = cgraph_max_pid ++;
353 notice_global_symbol (decl);
354 node->local.finalized = true;
355 node->lowered = DECL_STRUCT_FUNCTION (decl)->cfg != NULL;
356 node->finalized_by_frontend = true;
358 if (cgraph_decide_is_function_needed (node, decl))
359 cgraph_mark_needed_node (node);
361 /* Since we reclaim unreachable nodes at the end of every language
362 level unit, we need to be conservative about possible entry points
364 if ((TREE_PUBLIC (decl) && !DECL_COMDAT (decl) && !DECL_EXTERNAL (decl))
365 || DECL_STATIC_CONSTRUCTOR (decl)
366 || DECL_STATIC_DESTRUCTOR (decl)
367 /* COMDAT virtual functions may be referenced by vtable from
368 other compilatoin unit. Still we want to devirtualize calls
369 to those so we need to analyze them.
370 FIXME: We should introduce may edges for this purpose and update
371 their handling in unreachable function removal and inliner too. */
372 || (DECL_VIRTUAL_P (decl) && (DECL_COMDAT (decl) || DECL_EXTERNAL (decl))))
373 cgraph_mark_reachable_node (node);
375 /* If we've not yet emitted decl, tell the debug info about it. */
376 if (!TREE_ASM_WRITTEN (decl))
377 (*debug_hooks->deferred_inline_function) (decl);
379 /* Possibly warn about unused parameters. */
380 if (warn_unused_parameter)
381 do_warn_unused_parameter (decl);
387 /* C99 extern inline keywords allow changing of declaration after function
388 has been finalized. We need to re-decide if we want to mark the function as
392 cgraph_mark_if_needed (tree decl)
394 struct cgraph_node *node = cgraph_node (decl);
395 if (node->local.finalized && cgraph_decide_is_function_needed (node, decl))
396 cgraph_mark_needed_node (node);
399 /* Return TRUE if NODE2 is equivalent to NODE or its clone. */
401 clone_of_p (struct cgraph_node *node, struct cgraph_node *node2)
403 while (node != node2 && node2)
404 node2 = node2->clone_of;
405 return node2 != NULL;
408 /* Verify edge E count and frequency. */
411 verify_edge_count_and_frequency (struct cgraph_edge *e)
413 bool error_found = false;
416 error ("caller edge count is negative");
419 if (e->frequency < 0)
421 error ("caller edge frequency is negative");
424 if (e->frequency > CGRAPH_FREQ_MAX)
426 error ("caller edge frequency is too large");
429 if (gimple_has_body_p (e->caller->decl)
430 && !e->caller->global.inlined_to
432 != compute_call_stmt_bb_frequency (e->caller->decl,
433 gimple_bb (e->call_stmt))))
435 error ("caller edge frequency %i does not match BB freqency %i",
437 compute_call_stmt_bb_frequency (e->caller->decl,
438 gimple_bb (e->call_stmt)));
444 /* Verify cgraph nodes of given cgraph node. */
446 verify_cgraph_node (struct cgraph_node *node)
448 struct cgraph_edge *e;
449 struct function *this_cfun = DECL_STRUCT_FUNCTION (node->decl);
450 struct function *saved_cfun = cfun;
451 basic_block this_block;
452 gimple_stmt_iterator gsi;
453 bool error_found = false;
458 timevar_push (TV_CGRAPH_VERIFY);
459 /* debug_generic_stmt needs correct cfun */
460 set_cfun (this_cfun);
461 for (e = node->callees; e; e = e->next_callee)
464 error ("aux field set for edge %s->%s",
465 identifier_to_locale (cgraph_node_name (e->caller)),
466 identifier_to_locale (cgraph_node_name (e->callee)));
471 error ("Execution count is negative");
474 if (node->global.inlined_to && node->local.externally_visible)
476 error ("Externally visible inline clone");
479 if (node->global.inlined_to && node->address_taken)
481 error ("Inline clone with address taken");
484 if (node->global.inlined_to && node->needed)
486 error ("Inline clone is needed");
489 for (e = node->indirect_calls; e; e = e->next_callee)
493 error ("aux field set for indirect edge from %s",
494 identifier_to_locale (cgraph_node_name (e->caller)));
497 if (!e->indirect_unknown_callee
498 || !e->indirect_info)
500 error ("An indirect edge from %s is not marked as indirect or has "
501 "associated indirect_info, the corresponding statement is: ",
502 identifier_to_locale (cgraph_node_name (e->caller)));
503 debug_gimple_stmt (e->call_stmt);
507 for (e = node->callers; e; e = e->next_caller)
509 if (verify_edge_count_and_frequency (e))
511 if (!e->inline_failed)
513 if (node->global.inlined_to
514 != (e->caller->global.inlined_to
515 ? e->caller->global.inlined_to : e->caller))
517 error ("inlined_to pointer is wrong");
520 if (node->callers->next_caller)
522 error ("multiple inline callers");
527 if (node->global.inlined_to)
529 error ("inlined_to pointer set for noninline callers");
533 for (e = node->indirect_calls; e; e = e->next_callee)
534 if (verify_edge_count_and_frequency (e))
536 if (!node->callers && node->global.inlined_to)
538 error ("inlined_to pointer is set but no predecessors found");
541 if (node->global.inlined_to == node)
543 error ("inlined_to pointer refers to itself");
547 if (!cgraph_node (node->decl))
549 error ("node not found in cgraph_hash");
555 struct cgraph_node *n;
556 for (n = node->clone_of->clones; n; n = n->next_sibling_clone)
561 error ("node has wrong clone_of");
567 struct cgraph_node *n;
568 for (n = node->clones; n; n = n->next_sibling_clone)
569 if (n->clone_of != node)
573 error ("node has wrong clone list");
577 if ((node->prev_sibling_clone || node->next_sibling_clone) && !node->clone_of)
579 error ("node is in clone list but it is not clone");
582 if (!node->prev_sibling_clone && node->clone_of && node->clone_of->clones != node)
584 error ("node has wrong prev_clone pointer");
587 if (node->prev_sibling_clone && node->prev_sibling_clone->next_sibling_clone != node)
589 error ("double linked list of clones corrupted");
592 if (node->same_comdat_group)
594 struct cgraph_node *n = node->same_comdat_group;
596 if (!DECL_ONE_ONLY (node->decl))
598 error ("non-DECL_ONE_ONLY node in a same_comdat_group list");
603 error ("node is alone in a comdat group");
608 if (!n->same_comdat_group)
610 error ("same_comdat_group is not a circular list");
614 n = n->same_comdat_group;
619 if (node->analyzed && gimple_has_body_p (node->decl)
620 && !TREE_ASM_WRITTEN (node->decl)
621 && (!DECL_EXTERNAL (node->decl) || node->global.inlined_to)
626 /* The nodes we're interested in are never shared, so walk
627 the tree ignoring duplicates. */
628 struct pointer_set_t *visited_nodes = pointer_set_create ();
629 /* Reach the trees by walking over the CFG, and note the
630 enclosing basic-blocks in the call edges. */
631 FOR_EACH_BB_FN (this_block, this_cfun)
632 for (gsi = gsi_start_bb (this_block);
636 gimple stmt = gsi_stmt (gsi);
637 if (is_gimple_call (stmt))
639 struct cgraph_edge *e = cgraph_edge (node, stmt);
640 tree decl = gimple_call_fndecl (stmt);
645 error ("shared call_stmt:");
646 debug_gimple_stmt (stmt);
649 if (!e->indirect_unknown_callee)
651 if (e->callee->same_body_alias)
653 error ("edge points to same body alias:");
654 debug_tree (e->callee->decl);
657 else if (!e->callee->global.inlined_to
659 && cgraph_get_node (decl)
660 && (e->callee->former_clone_of
661 != cgraph_get_node (decl)->decl)
662 && !clone_of_p (cgraph_node (decl),
665 error ("edge points to wrong declaration:");
666 debug_tree (e->callee->decl);
667 fprintf (stderr," Instead of:");
674 error ("an indirect edge with unknown callee "
675 "corresponding to a call_stmt with "
676 "a known declaration:");
678 debug_gimple_stmt (e->call_stmt);
684 error ("missing callgraph edge for call stmt:");
685 debug_gimple_stmt (stmt);
690 pointer_set_destroy (visited_nodes);
693 /* No CFG available?! */
696 for (e = node->callees; e; e = e->next_callee)
700 error ("edge %s->%s has no corresponding call_stmt",
701 identifier_to_locale (cgraph_node_name (e->caller)),
702 identifier_to_locale (cgraph_node_name (e->callee)));
703 debug_gimple_stmt (e->call_stmt);
708 for (e = node->indirect_calls; e; e = e->next_callee)
712 error ("an indirect edge from %s has no corresponding call_stmt",
713 identifier_to_locale (cgraph_node_name (e->caller)));
714 debug_gimple_stmt (e->call_stmt);
722 dump_cgraph_node (stderr, node);
723 internal_error ("verify_cgraph_node failed");
725 set_cfun (saved_cfun);
726 timevar_pop (TV_CGRAPH_VERIFY);
729 /* Verify whole cgraph structure. */
733 struct cgraph_node *node;
738 for (node = cgraph_nodes; node; node = node->next)
739 verify_cgraph_node (node);
742 /* Output all asm statements we have stored up to be output. */
745 cgraph_output_pending_asms (void)
747 struct cgraph_asm_node *can;
752 for (can = cgraph_asm_nodes; can; can = can->next)
753 assemble_asm (can->asm_str);
754 cgraph_asm_nodes = NULL;
757 /* Analyze the function scheduled to be output. */
759 cgraph_analyze_function (struct cgraph_node *node)
761 tree save = current_function_decl;
762 tree decl = node->decl;
764 current_function_decl = decl;
765 push_cfun (DECL_STRUCT_FUNCTION (decl));
767 assign_assembler_name_if_neeeded (node->decl);
769 /* Make sure to gimplify bodies only once. During analyzing a
770 function we lower it, which will require gimplified nested
771 functions, so we can end up here with an already gimplified
773 if (!gimple_body (decl))
774 gimplify_function_tree (decl);
775 dump_function (TDI_generic, decl);
777 cgraph_lower_function (node);
778 node->analyzed = true;
781 current_function_decl = save;
784 /* Look for externally_visible and used attributes and mark cgraph nodes
787 We cannot mark the nodes at the point the attributes are processed (in
788 handle_*_attribute) because the copy of the declarations available at that
789 point may not be canonical. For example, in:
792 void f() __attribute__((used));
794 the declaration we see in handle_used_attribute will be the second
795 declaration -- but the front end will subsequently merge that declaration
796 with the original declaration and discard the second declaration.
798 Furthermore, we can't mark these nodes in cgraph_finalize_function because:
801 void f() __attribute__((externally_visible));
805 So, we walk the nodes at the end of the translation unit, applying the
806 attributes at that point. */
809 process_function_and_variable_attributes (struct cgraph_node *first,
810 struct varpool_node *first_var)
812 struct cgraph_node *node;
813 struct varpool_node *vnode;
815 for (node = cgraph_nodes; node != first; node = node->next)
817 tree decl = node->decl;
818 if (DECL_PRESERVE_P (decl))
819 cgraph_mark_needed_node (node);
820 if (lookup_attribute ("externally_visible", DECL_ATTRIBUTES (decl)))
822 if (! TREE_PUBLIC (node->decl))
823 warning_at (DECL_SOURCE_LOCATION (node->decl), OPT_Wattributes,
824 "%<externally_visible%>"
825 " attribute have effect only on public objects");
826 else if (node->local.finalized)
827 cgraph_mark_needed_node (node);
830 for (vnode = varpool_nodes; vnode != first_var; vnode = vnode->next)
832 tree decl = vnode->decl;
833 if (DECL_PRESERVE_P (decl))
835 vnode->force_output = true;
836 if (vnode->finalized)
837 varpool_mark_needed_node (vnode);
839 if (lookup_attribute ("externally_visible", DECL_ATTRIBUTES (decl)))
841 if (! TREE_PUBLIC (vnode->decl))
842 warning_at (DECL_SOURCE_LOCATION (vnode->decl), OPT_Wattributes,
843 "%<externally_visible%>"
844 " attribute have effect only on public objects");
845 else if (vnode->finalized)
846 varpool_mark_needed_node (vnode);
851 /* Process CGRAPH_NODES_NEEDED queue, analyze each function (and transitively
852 each reachable functions) and build cgraph.
853 The function can be called multiple times after inserting new nodes
854 into beginning of queue. Just the new part of queue is re-scanned then. */
857 cgraph_analyze_functions (void)
859 /* Keep track of already processed nodes when called multiple times for
860 intermodule optimization. */
861 static struct cgraph_node *first_analyzed;
862 struct cgraph_node *first_processed = first_analyzed;
863 static struct varpool_node *first_analyzed_var;
864 struct cgraph_node *node, *next;
866 bitmap_obstack_initialize (NULL);
867 process_function_and_variable_attributes (first_processed,
869 first_processed = cgraph_nodes;
870 first_analyzed_var = varpool_nodes;
871 varpool_analyze_pending_decls ();
872 if (cgraph_dump_file)
874 fprintf (cgraph_dump_file, "Initial entry points:");
875 for (node = cgraph_nodes; node != first_analyzed; node = node->next)
877 fprintf (cgraph_dump_file, " %s", cgraph_node_name (node));
878 fprintf (cgraph_dump_file, "\n");
880 cgraph_process_new_functions ();
882 /* Propagate reachability flag and lower representation of all reachable
883 functions. In the future, lowering will introduce new functions and
884 new entry points on the way (by template instantiation and virtual
885 method table generation for instance). */
886 while (cgraph_nodes_queue)
888 struct cgraph_edge *edge;
889 tree decl = cgraph_nodes_queue->decl;
891 node = cgraph_nodes_queue;
892 cgraph_nodes_queue = cgraph_nodes_queue->next_needed;
893 node->next_needed = NULL;
895 /* ??? It is possible to create extern inline function and later using
896 weak alias attribute to kill its body. See
897 gcc.c-torture/compile/20011119-1.c */
898 if (!DECL_STRUCT_FUNCTION (decl))
900 cgraph_reset_node (node);
905 cgraph_analyze_function (node);
907 for (edge = node->callees; edge; edge = edge->next_callee)
908 if (!edge->callee->reachable)
909 cgraph_mark_reachable_node (edge->callee);
911 if (node->same_comdat_group)
913 for (next = node->same_comdat_group;
915 next = next->same_comdat_group)
916 cgraph_mark_reachable_node (next);
919 /* If decl is a clone of an abstract function, mark that abstract
920 function so that we don't release its body. The DECL_INITIAL() of that
921 abstract function declaration will be later needed to output debug info. */
922 if (DECL_ABSTRACT_ORIGIN (decl))
924 struct cgraph_node *origin_node = cgraph_node (DECL_ABSTRACT_ORIGIN (decl));
925 origin_node->abstract_and_needed = true;
928 /* We finalize local static variables during constructing callgraph
929 edges. Process their attributes too. */
930 process_function_and_variable_attributes (first_processed,
932 first_processed = cgraph_nodes;
933 first_analyzed_var = varpool_nodes;
934 varpool_analyze_pending_decls ();
935 cgraph_process_new_functions ();
938 /* Collect entry points to the unit. */
939 if (cgraph_dump_file)
941 fprintf (cgraph_dump_file, "Unit entry points:");
942 for (node = cgraph_nodes; node != first_analyzed; node = node->next)
944 fprintf (cgraph_dump_file, " %s", cgraph_node_name (node));
945 fprintf (cgraph_dump_file, "\n\nInitial ");
946 dump_cgraph (cgraph_dump_file);
949 if (cgraph_dump_file)
950 fprintf (cgraph_dump_file, "\nReclaiming functions:");
952 for (node = cgraph_nodes; node != first_analyzed; node = next)
954 tree decl = node->decl;
957 if (node->local.finalized && !gimple_has_body_p (decl))
958 cgraph_reset_node (node);
960 if (!node->reachable && gimple_has_body_p (decl))
962 if (cgraph_dump_file)
963 fprintf (cgraph_dump_file, " %s", cgraph_node_name (node));
964 cgraph_remove_node (node);
968 node->next_needed = NULL;
969 gcc_assert (!node->local.finalized || gimple_has_body_p (decl));
970 gcc_assert (node->analyzed == node->local.finalized);
972 if (cgraph_dump_file)
974 fprintf (cgraph_dump_file, "\n\nReclaimed ");
975 dump_cgraph (cgraph_dump_file);
977 bitmap_obstack_release (NULL);
978 first_analyzed = cgraph_nodes;
983 /* Analyze the whole compilation unit once it is parsed completely. */
986 cgraph_finalize_compilation_unit (void)
988 timevar_push (TV_CGRAPH);
990 /* Do not skip analyzing the functions if there were errors, we
991 miss diagnostics for following functions otherwise. */
993 /* Emit size functions we didn't inline. */
994 finalize_size_functions ();
996 /* Mark alias targets necessary and emit diagnostics. */
1001 fprintf (stderr, "\nAnalyzing compilation unit\n");
1005 /* Gimplify and lower all functions, compute reachability and
1006 remove unreachable nodes. */
1007 cgraph_analyze_functions ();
1009 /* Mark alias targets necessary and emit diagnostics. */
1010 finish_aliases_1 ();
1012 /* Gimplify and lower thunks. */
1013 cgraph_analyze_functions ();
1015 /* Finally drive the pass manager. */
1018 timevar_pop (TV_CGRAPH);
1022 /* Figure out what functions we want to assemble. */
1025 cgraph_mark_functions_to_output (void)
1027 struct cgraph_node *node;
1028 #ifdef ENABLE_CHECKING
1029 bool check_same_comdat_groups = false;
1031 for (node = cgraph_nodes; node; node = node->next)
1032 gcc_assert (!node->process);
1035 for (node = cgraph_nodes; node; node = node->next)
1037 tree decl = node->decl;
1038 struct cgraph_edge *e;
1040 gcc_assert (!node->process || node->same_comdat_group);
1044 for (e = node->callers; e; e = e->next_caller)
1045 if (e->inline_failed)
1048 /* We need to output all local functions that are used and not
1049 always inlined, as well as those that are reachable from
1050 outside the current compilation unit. */
1052 && !node->global.inlined_to
1053 && (!cgraph_only_called_directly_p (node)
1054 || (e && node->reachable))
1055 && !TREE_ASM_WRITTEN (decl)
1056 && !DECL_EXTERNAL (decl))
1059 if (node->same_comdat_group)
1061 struct cgraph_node *next;
1062 for (next = node->same_comdat_group;
1064 next = next->same_comdat_group)
1068 else if (node->same_comdat_group)
1070 #ifdef ENABLE_CHECKING
1071 check_same_comdat_groups = true;
1076 /* We should've reclaimed all functions that are not needed. */
1077 #ifdef ENABLE_CHECKING
1078 if (!node->global.inlined_to
1079 && gimple_has_body_p (decl)
1080 /* FIXME: in ltrans unit when offline copy is outside partition but inline copies
1081 are inside partition, we can end up not removing the body since we no longer
1082 have analyzed node pointing to it. */
1083 && !node->in_other_partition
1084 && !DECL_EXTERNAL (decl))
1086 dump_cgraph_node (stderr, node);
1087 internal_error ("failed to reclaim unneeded function");
1090 gcc_assert (node->global.inlined_to
1091 || !gimple_has_body_p (decl)
1092 || node->in_other_partition
1093 || DECL_EXTERNAL (decl));
1098 #ifdef ENABLE_CHECKING
1099 if (check_same_comdat_groups)
1100 for (node = cgraph_nodes; node; node = node->next)
1101 if (node->same_comdat_group && !node->process)
1103 tree decl = node->decl;
1104 if (!node->global.inlined_to
1105 && gimple_has_body_p (decl)
1106 /* FIXME: in ltrans unit when offline copy is outside partition but inline copies
1107 are inside partition, we can end up not removing the body since we no longer
1108 have analyzed node pointing to it. */
1109 && !node->in_other_partition
1110 && !DECL_EXTERNAL (decl))
1112 dump_cgraph_node (stderr, node);
1113 internal_error ("failed to reclaim unneeded function");
1119 /* DECL is FUNCTION_DECL. Initialize datastructures so DECL is a function
1120 in lowered gimple form.
1122 Set current_function_decl and cfun to newly constructed empty function body.
1123 return basic block in the function body. */
1126 init_lowered_empty_function (tree decl)
1130 current_function_decl = decl;
1131 allocate_struct_function (decl, false);
1132 gimple_register_cfg_hooks ();
1133 init_empty_tree_cfg ();
1134 init_tree_ssa (cfun);
1135 init_ssa_operands ();
1136 cfun->gimple_df->in_ssa_p = true;
1137 DECL_INITIAL (decl) = make_node (BLOCK);
1139 DECL_SAVED_TREE (decl) = error_mark_node;
1140 cfun->curr_properties |=
1141 (PROP_gimple_lcf | PROP_gimple_leh | PROP_cfg | PROP_referenced_vars |
1144 /* Create BB for body of the function and connect it properly. */
1145 bb = create_basic_block (NULL, (void *) 0, ENTRY_BLOCK_PTR);
1146 make_edge (ENTRY_BLOCK_PTR, bb, 0);
1147 make_edge (bb, EXIT_BLOCK_PTR, 0);
1152 /* Adjust PTR by the constant FIXED_OFFSET, and by the vtable
1153 offset indicated by VIRTUAL_OFFSET, if that is
1154 non-null. THIS_ADJUSTING is nonzero for a this adjusting thunk and
1155 zero for a result adjusting thunk. */
1158 thunk_adjust (gimple_stmt_iterator * bsi,
1159 tree ptr, bool this_adjusting,
1160 HOST_WIDE_INT fixed_offset, tree virtual_offset)
1166 && fixed_offset != 0)
1168 stmt = gimple_build_assign (ptr,
1169 fold_build2_loc (input_location,
1171 TREE_TYPE (ptr), ptr,
1172 size_int (fixed_offset)));
1173 gsi_insert_after (bsi, stmt, GSI_NEW_STMT);
1176 /* If there's a virtual offset, look up that value in the vtable and
1177 adjust the pointer again. */
1185 if (!vtable_entry_type)
1187 tree vfunc_type = make_node (FUNCTION_TYPE);
1188 TREE_TYPE (vfunc_type) = integer_type_node;
1189 TYPE_ARG_TYPES (vfunc_type) = NULL_TREE;
1190 layout_type (vfunc_type);
1192 vtable_entry_type = build_pointer_type (vfunc_type);
1196 create_tmp_var (build_pointer_type
1197 (build_pointer_type (vtable_entry_type)), "vptr");
1199 /* The vptr is always at offset zero in the object. */
1200 stmt = gimple_build_assign (vtabletmp,
1201 build1 (NOP_EXPR, TREE_TYPE (vtabletmp),
1203 gsi_insert_after (bsi, stmt, GSI_NEW_STMT);
1204 mark_symbols_for_renaming (stmt);
1205 find_referenced_vars_in (stmt);
1207 /* Form the vtable address. */
1208 vtabletmp2 = create_tmp_var (TREE_TYPE (TREE_TYPE (vtabletmp)),
1210 stmt = gimple_build_assign (vtabletmp2,
1211 build_simple_mem_ref (vtabletmp));
1212 gsi_insert_after (bsi, stmt, GSI_NEW_STMT);
1213 mark_symbols_for_renaming (stmt);
1214 find_referenced_vars_in (stmt);
1216 /* Find the entry with the vcall offset. */
1217 stmt = gimple_build_assign (vtabletmp2,
1218 fold_build2_loc (input_location,
1220 TREE_TYPE (vtabletmp2),
1222 fold_convert (sizetype,
1224 gsi_insert_after (bsi, stmt, GSI_NEW_STMT);
1226 /* Get the offset itself. */
1227 vtabletmp3 = create_tmp_var (TREE_TYPE (TREE_TYPE (vtabletmp2)),
1229 stmt = gimple_build_assign (vtabletmp3,
1230 build_simple_mem_ref (vtabletmp2));
1231 gsi_insert_after (bsi, stmt, GSI_NEW_STMT);
1232 mark_symbols_for_renaming (stmt);
1233 find_referenced_vars_in (stmt);
1235 /* Cast to sizetype. */
1236 offsettmp = create_tmp_var (sizetype, "offset");
1237 stmt = gimple_build_assign (offsettmp, fold_convert (sizetype, vtabletmp3));
1238 gsi_insert_after (bsi, stmt, GSI_NEW_STMT);
1239 mark_symbols_for_renaming (stmt);
1240 find_referenced_vars_in (stmt);
1242 /* Adjust the `this' pointer. */
1243 ptr = fold_build2_loc (input_location,
1244 POINTER_PLUS_EXPR, TREE_TYPE (ptr), ptr,
1249 && fixed_offset != 0)
1250 /* Adjust the pointer by the constant. */
1254 if (TREE_CODE (ptr) == VAR_DECL)
1258 ptrtmp = create_tmp_var (TREE_TYPE (ptr), "ptr");
1259 stmt = gimple_build_assign (ptrtmp, ptr);
1260 gsi_insert_after (bsi, stmt, GSI_NEW_STMT);
1261 mark_symbols_for_renaming (stmt);
1262 find_referenced_vars_in (stmt);
1264 ptr = fold_build2_loc (input_location,
1265 POINTER_PLUS_EXPR, TREE_TYPE (ptrtmp), ptrtmp,
1266 size_int (fixed_offset));
1269 /* Emit the statement and gimplify the adjustment expression. */
1270 ret = create_tmp_var (TREE_TYPE (ptr), "adjusted_this");
1271 stmt = gimple_build_assign (ret, ptr);
1272 mark_symbols_for_renaming (stmt);
1273 find_referenced_vars_in (stmt);
1274 gsi_insert_after (bsi, stmt, GSI_NEW_STMT);
1279 /* Produce assembler for thunk NODE. */
1282 assemble_thunk (struct cgraph_node *node)
1284 bool this_adjusting = node->thunk.this_adjusting;
1285 HOST_WIDE_INT fixed_offset = node->thunk.fixed_offset;
1286 HOST_WIDE_INT virtual_value = node->thunk.virtual_value;
1287 tree virtual_offset = NULL;
1288 tree alias = node->thunk.alias;
1289 tree thunk_fndecl = node->decl;
1290 tree a = DECL_ARGUMENTS (thunk_fndecl);
1292 current_function_decl = thunk_fndecl;
1295 && targetm.asm_out.can_output_mi_thunk (thunk_fndecl, fixed_offset,
1296 virtual_value, alias))
1301 DECL_RESULT (thunk_fndecl)
1302 = build_decl (DECL_SOURCE_LOCATION (thunk_fndecl),
1303 RESULT_DECL, 0, integer_type_node);
1304 fnname = IDENTIFIER_POINTER (DECL_ASSEMBLER_NAME (thunk_fndecl));
1306 /* The back end expects DECL_INITIAL to contain a BLOCK, so we
1308 fn_block = make_node (BLOCK);
1309 BLOCK_VARS (fn_block) = a;
1310 DECL_INITIAL (thunk_fndecl) = fn_block;
1311 init_function_start (thunk_fndecl);
1313 assemble_start_function (thunk_fndecl, fnname);
1315 targetm.asm_out.output_mi_thunk (asm_out_file, thunk_fndecl,
1316 fixed_offset, virtual_value, alias);
1318 assemble_end_function (thunk_fndecl, fnname);
1319 init_insn_lengths ();
1320 free_after_compilation (cfun);
1322 TREE_ASM_WRITTEN (thunk_fndecl) = 1;
1327 basic_block bb, then_bb, else_bb, return_bb;
1328 gimple_stmt_iterator bsi;
1334 VEC(tree, heap) *vargs;
1339 DECL_IGNORED_P (thunk_fndecl) = 1;
1340 bitmap_obstack_initialize (NULL);
1342 if (node->thunk.virtual_offset_p)
1343 virtual_offset = size_int (virtual_value);
1345 /* Build the return declaration for the function. */
1346 restype = TREE_TYPE (TREE_TYPE (thunk_fndecl));
1347 if (DECL_RESULT (thunk_fndecl) == NULL_TREE)
1349 resdecl = build_decl (input_location, RESULT_DECL, 0, restype);
1350 DECL_ARTIFICIAL (resdecl) = 1;
1351 DECL_IGNORED_P (resdecl) = 1;
1352 DECL_RESULT (thunk_fndecl) = resdecl;
1355 resdecl = DECL_RESULT (thunk_fndecl);
1357 bb = then_bb = else_bb = return_bb = init_lowered_empty_function (thunk_fndecl);
1359 bsi = gsi_start_bb (bb);
1361 /* Build call to the function being thunked. */
1362 if (!VOID_TYPE_P (restype))
1364 if (!is_gimple_reg_type (restype))
1367 add_local_decl (cfun, restmp);
1368 BLOCK_VARS (DECL_INITIAL (current_function_decl)) = restmp;
1371 restmp = create_tmp_var_raw (restype, "retval");
1374 for (arg = a; arg; arg = DECL_CHAIN (arg))
1376 vargs = VEC_alloc (tree, heap, nargs);
1378 VEC_quick_push (tree, vargs,
1383 VEC_quick_push (tree, vargs, a);
1384 for (i = 1, arg = DECL_CHAIN (a); i < nargs; i++, arg = DECL_CHAIN (arg))
1385 VEC_quick_push (tree, vargs, arg);
1386 call = gimple_build_call_vec (build_fold_addr_expr_loc (0, alias), vargs);
1387 VEC_free (tree, heap, vargs);
1388 gimple_call_set_cannot_inline (call, true);
1389 gimple_call_set_from_thunk (call, true);
1391 gimple_call_set_lhs (call, restmp);
1392 gsi_insert_after (&bsi, call, GSI_NEW_STMT);
1393 mark_symbols_for_renaming (call);
1394 find_referenced_vars_in (call);
1397 if (restmp && !this_adjusting)
1399 tree true_label = NULL_TREE;
1401 if (TREE_CODE (TREE_TYPE (restmp)) == POINTER_TYPE)
1404 /* If the return type is a pointer, we need to
1405 protect against NULL. We know there will be an
1406 adjustment, because that's why we're emitting a
1408 then_bb = create_basic_block (NULL, (void *) 0, bb);
1409 return_bb = create_basic_block (NULL, (void *) 0, then_bb);
1410 else_bb = create_basic_block (NULL, (void *) 0, else_bb);
1411 remove_edge (single_succ_edge (bb));
1412 true_label = gimple_block_label (then_bb);
1413 stmt = gimple_build_cond (NE_EXPR, restmp,
1414 fold_convert (TREE_TYPE (restmp),
1416 NULL_TREE, NULL_TREE);
1417 gsi_insert_after (&bsi, stmt, GSI_NEW_STMT);
1418 make_edge (bb, then_bb, EDGE_TRUE_VALUE);
1419 make_edge (bb, else_bb, EDGE_FALSE_VALUE);
1420 make_edge (return_bb, EXIT_BLOCK_PTR, 0);
1421 make_edge (then_bb, return_bb, EDGE_FALLTHRU);
1422 make_edge (else_bb, return_bb, EDGE_FALLTHRU);
1423 bsi = gsi_last_bb (then_bb);
1426 restmp = thunk_adjust (&bsi, restmp, /*this_adjusting=*/0,
1427 fixed_offset, virtual_offset);
1431 bsi = gsi_last_bb (else_bb);
1432 stmt = gimple_build_assign (restmp, fold_convert (TREE_TYPE (restmp),
1433 integer_zero_node));
1434 gsi_insert_after (&bsi, stmt, GSI_NEW_STMT);
1435 bsi = gsi_last_bb (return_bb);
1439 gimple_call_set_tail (call, true);
1441 /* Build return value. */
1442 ret = gimple_build_return (restmp);
1443 gsi_insert_after (&bsi, ret, GSI_NEW_STMT);
1445 delete_unreachable_blocks ();
1446 update_ssa (TODO_update_ssa);
1448 cgraph_remove_same_body_alias (node);
1449 /* Since we want to emit the thunk, we explicitly mark its name as
1451 cgraph_add_new_function (thunk_fndecl, true);
1452 bitmap_obstack_release (NULL);
1454 current_function_decl = NULL;
1457 /* Expand function specified by NODE. */
1460 cgraph_expand_function (struct cgraph_node *node)
1462 tree decl = node->decl;
1464 /* We ought to not compile any inline clones. */
1465 gcc_assert (!node->global.inlined_to);
1467 announce_function (decl);
1469 if (node->same_body)
1471 struct cgraph_node *alias, *next;
1472 bool saved_alias = node->alias;
1473 for (alias = node->same_body;
1474 alias && alias->next; alias = alias->next)
1476 /* Walk aliases in the order they were created; it is possible that
1477 thunks reffers to the aliases made earlier. */
1478 for (; alias; alias = next)
1480 next = alias->previous;
1481 if (!alias->thunk.thunk_p)
1482 assemble_alias (alias->decl,
1483 DECL_ASSEMBLER_NAME (alias->thunk.alias));
1485 assemble_thunk (alias);
1487 node->alias = saved_alias;
1488 cgraph_process_new_functions ();
1491 gcc_assert (node->lowered);
1493 /* Generate RTL for the body of DECL. */
1494 tree_rest_of_compilation (decl);
1496 /* Make sure that BE didn't give up on compiling. */
1497 gcc_assert (TREE_ASM_WRITTEN (decl));
1498 current_function_decl = NULL;
1499 gcc_assert (!cgraph_preserve_function_body_p (decl));
1500 cgraph_release_function_body (node);
1501 /* Eliminate all call edges. This is important so the GIMPLE_CALL no longer
1502 points to the dead function body. */
1503 cgraph_node_remove_callees (node);
1505 cgraph_function_flags_ready = true;
1508 /* Return true when CALLER_DECL should be inlined into CALLEE_DECL. */
1511 cgraph_inline_p (struct cgraph_edge *e, cgraph_inline_failed_t *reason)
1513 *reason = e->inline_failed;
1514 return !e->inline_failed;
1519 /* Expand all functions that must be output.
1521 Attempt to topologically sort the nodes so function is output when
1522 all called functions are already assembled to allow data to be
1523 propagated across the callgraph. Use a stack to get smaller distance
1524 between a function and its callees (later we may choose to use a more
1525 sophisticated algorithm for function reordering; we will likely want
1526 to use subsections to make the output functions appear in top-down
1530 cgraph_expand_all_functions (void)
1532 struct cgraph_node *node;
1533 struct cgraph_node **order = XCNEWVEC (struct cgraph_node *, cgraph_n_nodes);
1534 int order_pos, new_order_pos = 0;
1537 order_pos = cgraph_postorder (order);
1538 gcc_assert (order_pos == cgraph_n_nodes);
1540 /* Garbage collector may remove inline clones we eliminate during
1541 optimization. So we must be sure to not reference them. */
1542 for (i = 0; i < order_pos; i++)
1543 if (order[i]->process)
1544 order[new_order_pos++] = order[i];
1546 for (i = new_order_pos - 1; i >= 0; i--)
1551 gcc_assert (node->reachable);
1553 cgraph_expand_function (node);
1556 cgraph_process_new_functions ();
1562 /* This is used to sort the node types by the cgraph order number. */
1564 enum cgraph_order_sort_kind
1566 ORDER_UNDEFINED = 0,
1572 struct cgraph_order_sort
1574 enum cgraph_order_sort_kind kind;
1577 struct cgraph_node *f;
1578 struct varpool_node *v;
1579 struct cgraph_asm_node *a;
1583 /* Output all functions, variables, and asm statements in the order
1584 according to their order fields, which is the order in which they
1585 appeared in the file. This implements -fno-toplevel-reorder. In
1586 this mode we may output functions and variables which don't really
1587 need to be output. */
1590 cgraph_output_in_order (void)
1593 struct cgraph_order_sort *nodes;
1595 struct cgraph_node *pf;
1596 struct varpool_node *pv;
1597 struct cgraph_asm_node *pa;
1600 nodes = XCNEWVEC (struct cgraph_order_sort, max);
1602 varpool_analyze_pending_decls ();
1604 for (pf = cgraph_nodes; pf; pf = pf->next)
1609 gcc_assert (nodes[i].kind == ORDER_UNDEFINED);
1610 nodes[i].kind = ORDER_FUNCTION;
1615 for (pv = varpool_nodes_queue; pv; pv = pv->next_needed)
1618 gcc_assert (nodes[i].kind == ORDER_UNDEFINED);
1619 nodes[i].kind = ORDER_VAR;
1623 for (pa = cgraph_asm_nodes; pa; pa = pa->next)
1626 gcc_assert (nodes[i].kind == ORDER_UNDEFINED);
1627 nodes[i].kind = ORDER_ASM;
1631 /* In toplevel reorder mode we output all statics; mark them as needed. */
1632 for (i = 0; i < max; ++i)
1634 if (nodes[i].kind == ORDER_VAR)
1636 varpool_mark_needed_node (nodes[i].u.v);
1639 varpool_empty_needed_queue ();
1641 for (i = 0; i < max; ++i)
1643 switch (nodes[i].kind)
1645 case ORDER_FUNCTION:
1646 nodes[i].u.f->process = 0;
1647 cgraph_expand_function (nodes[i].u.f);
1651 varpool_assemble_decl (nodes[i].u.v);
1655 assemble_asm (nodes[i].u.a->asm_str);
1658 case ORDER_UNDEFINED:
1666 cgraph_asm_nodes = NULL;
1670 /* Return true when function body of DECL still needs to be kept around
1671 for later re-use. */
1673 cgraph_preserve_function_body_p (tree decl)
1675 struct cgraph_node *node;
1677 gcc_assert (cgraph_global_info_ready);
1678 /* Look if there is any clone around. */
1679 node = cgraph_node (decl);
1689 current_function_decl = NULL;
1690 gimple_register_cfg_hooks ();
1691 bitmap_obstack_initialize (NULL);
1693 invoke_plugin_callbacks (PLUGIN_ALL_IPA_PASSES_START, NULL);
1696 execute_ipa_pass_list (all_small_ipa_passes);
1698 /* If pass_all_early_optimizations was not scheduled, the state of
1699 the cgraph will not be properly updated. Update it now. */
1700 if (cgraph_state < CGRAPH_STATE_IPA_SSA)
1701 cgraph_state = CGRAPH_STATE_IPA_SSA;
1705 /* Generate coverage variables and constructors. */
1708 /* Process new functions added. */
1710 current_function_decl = NULL;
1711 cgraph_process_new_functions ();
1713 execute_ipa_summary_passes
1714 ((struct ipa_opt_pass_d *) all_regular_ipa_passes);
1717 /* Some targets need to handle LTO assembler output specially. */
1718 if (flag_generate_lto)
1719 targetm.asm_out.lto_start ();
1721 execute_ipa_summary_passes ((struct ipa_opt_pass_d *) all_lto_gen_passes);
1724 ipa_write_summaries ();
1726 if (flag_generate_lto)
1727 targetm.asm_out.lto_end ();
1730 execute_ipa_pass_list (all_regular_ipa_passes);
1731 invoke_plugin_callbacks (PLUGIN_ALL_IPA_PASSES_END, NULL);
1733 bitmap_obstack_release (NULL);
1737 /* Perform simple optimizations based on callgraph. */
1740 cgraph_optimize (void)
1745 #ifdef ENABLE_CHECKING
1749 /* Frontend may output common variables after the unit has been finalized.
1750 It is safe to deal with them here as they are always zero initialized. */
1751 varpool_analyze_pending_decls ();
1753 timevar_push (TV_CGRAPHOPT);
1754 if (pre_ipa_mem_report)
1756 fprintf (stderr, "Memory consumption before IPA\n");
1757 dump_memory_report (false);
1760 fprintf (stderr, "Performing interprocedural optimizations\n");
1761 cgraph_state = CGRAPH_STATE_IPA;
1763 /* Don't run the IPA passes if there was any error or sorry messages. */
1767 /* Do nothing else if any IPA pass found errors. */
1770 timevar_pop (TV_CGRAPHOPT);
1774 /* This pass remove bodies of extern inline functions we never inlined.
1775 Do this later so other IPA passes see what is really going on. */
1776 cgraph_remove_unreachable_nodes (false, dump_file);
1777 cgraph_global_info_ready = true;
1778 if (cgraph_dump_file)
1780 fprintf (cgraph_dump_file, "Optimized ");
1781 dump_cgraph (cgraph_dump_file);
1782 dump_varpool (cgraph_dump_file);
1784 if (post_ipa_mem_report)
1786 fprintf (stderr, "Memory consumption after IPA\n");
1787 dump_memory_report (false);
1789 timevar_pop (TV_CGRAPHOPT);
1791 /* Output everything. */
1792 (*debug_hooks->assembly_start) ();
1794 fprintf (stderr, "Assembling functions:\n");
1795 #ifdef ENABLE_CHECKING
1799 cgraph_materialize_all_clones ();
1800 cgraph_mark_functions_to_output ();
1802 cgraph_state = CGRAPH_STATE_EXPANSION;
1803 if (!flag_toplevel_reorder)
1804 cgraph_output_in_order ();
1807 cgraph_output_pending_asms ();
1809 cgraph_expand_all_functions ();
1810 varpool_remove_unreferenced_decls ();
1812 varpool_assemble_pending_decls ();
1814 cgraph_process_new_functions ();
1815 cgraph_state = CGRAPH_STATE_FINISHED;
1817 if (cgraph_dump_file)
1819 fprintf (cgraph_dump_file, "\nFinal ");
1820 dump_cgraph (cgraph_dump_file);
1822 #ifdef ENABLE_CHECKING
1824 /* Double check that all inline clones are gone and that all
1825 function bodies have been released from memory. */
1828 struct cgraph_node *node;
1829 bool error_found = false;
1831 for (node = cgraph_nodes; node; node = node->next)
1833 && (node->global.inlined_to
1834 || gimple_has_body_p (node->decl)))
1837 dump_cgraph_node (stderr, node);
1840 internal_error ("nodes with unreleased memory found");
1848 if (!cgraph_dump_file)
1849 cgraph_dump_file = dump_begin (TDI_cgraph, NULL);
1852 /* The edges representing the callers of the NEW_VERSION node were
1853 fixed by cgraph_function_versioning (), now the call_expr in their
1854 respective tree code should be updated to call the NEW_VERSION. */
1857 update_call_expr (struct cgraph_node *new_version)
1859 struct cgraph_edge *e;
1861 gcc_assert (new_version);
1863 /* Update the call expr on the edges to call the new version. */
1864 for (e = new_version->callers; e; e = e->next_caller)
1866 struct function *inner_function = DECL_STRUCT_FUNCTION (e->caller->decl);
1867 gimple_call_set_fndecl (e->call_stmt, new_version->decl);
1868 maybe_clean_eh_stmt_fn (inner_function, e->call_stmt);
1873 /* Create a new cgraph node which is the new version of
1874 OLD_VERSION node. REDIRECT_CALLERS holds the callers
1875 edges which should be redirected to point to
1876 NEW_VERSION. ALL the callees edges of OLD_VERSION
1877 are cloned to the new version node. Return the new
1880 If non-NULL BLOCK_TO_COPY determine what basic blocks
1881 was copied to prevent duplications of calls that are dead
1884 static struct cgraph_node *
1885 cgraph_copy_node_for_versioning (struct cgraph_node *old_version,
1887 VEC(cgraph_edge_p,heap) *redirect_callers,
1890 struct cgraph_node *new_version;
1891 struct cgraph_edge *e;
1894 gcc_assert (old_version);
1896 new_version = cgraph_node (new_decl);
1898 new_version->analyzed = true;
1899 new_version->local = old_version->local;
1900 new_version->local.externally_visible = false;
1901 new_version->local.local = true;
1902 new_version->local.vtable_method = false;
1903 new_version->global = old_version->global;
1904 new_version->rtl = old_version->rtl;
1905 new_version->reachable = true;
1906 new_version->count = old_version->count;
1908 for (e = old_version->callees; e; e=e->next_callee)
1910 || bitmap_bit_p (bbs_to_copy, gimple_bb (e->call_stmt)->index))
1911 cgraph_clone_edge (e, new_version, e->call_stmt,
1912 e->lto_stmt_uid, REG_BR_PROB_BASE,
1914 e->loop_nest, true);
1915 for (e = old_version->indirect_calls; e; e=e->next_callee)
1917 || bitmap_bit_p (bbs_to_copy, gimple_bb (e->call_stmt)->index))
1918 cgraph_clone_edge (e, new_version, e->call_stmt,
1919 e->lto_stmt_uid, REG_BR_PROB_BASE,
1921 e->loop_nest, true);
1922 FOR_EACH_VEC_ELT (cgraph_edge_p, redirect_callers, i, e)
1924 /* Redirect calls to the old version node to point to its new
1926 cgraph_redirect_edge_callee (e, new_version);
1932 /* Perform function versioning.
1933 Function versioning includes copying of the tree and
1934 a callgraph update (creating a new cgraph node and updating
1935 its callees and callers).
1937 REDIRECT_CALLERS varray includes the edges to be redirected
1940 TREE_MAP is a mapping of tree nodes we want to replace with
1941 new ones (according to results of prior analysis).
1942 OLD_VERSION_NODE is the node that is versioned.
1943 It returns the new version's cgraph node.
1944 If non-NULL ARGS_TO_SKIP determine function parameters to remove
1946 If non-NULL BLOCK_TO_COPY determine what basic blocks to copy.
1947 If non_NULL NEW_ENTRY determine new entry BB of the clone. */
1949 struct cgraph_node *
1950 cgraph_function_versioning (struct cgraph_node *old_version_node,
1951 VEC(cgraph_edge_p,heap) *redirect_callers,
1952 VEC (ipa_replace_map_p,gc)* tree_map,
1953 bitmap args_to_skip,
1955 basic_block new_entry_block,
1956 const char *clone_name)
1958 tree old_decl = old_version_node->decl;
1959 struct cgraph_node *new_version_node = NULL;
1962 if (!tree_versionable_function_p (old_decl))
1965 /* Make a new FUNCTION_DECL tree node for the
1968 new_decl = copy_node (old_decl);
1970 new_decl = build_function_decl_skip_args (old_decl, args_to_skip);
1972 /* Generate a new name for the new version. */
1973 DECL_NAME (new_decl) = clone_function_name (old_decl, clone_name);
1974 SET_DECL_ASSEMBLER_NAME (new_decl, DECL_NAME (new_decl));
1975 SET_DECL_RTL (new_decl, NULL);
1977 /* Create the new version's call-graph node.
1978 and update the edges of the new node. */
1980 cgraph_copy_node_for_versioning (old_version_node, new_decl,
1981 redirect_callers, bbs_to_copy);
1983 /* Copy the OLD_VERSION_NODE function tree to the new version. */
1984 tree_function_versioning (old_decl, new_decl, tree_map, false, args_to_skip,
1985 bbs_to_copy, new_entry_block);
1987 /* Update the new version's properties.
1988 Make The new version visible only within this translation unit. Make sure
1989 that is not weak also.
1990 ??? We cannot use COMDAT linkage because there is no
1991 ABI support for this. */
1992 cgraph_make_decl_local (new_version_node->decl);
1993 DECL_VIRTUAL_P (new_version_node->decl) = 0;
1994 new_version_node->local.externally_visible = 0;
1995 new_version_node->local.local = 1;
1996 new_version_node->lowered = true;
1998 /* Update the call_expr on the edges to call the new version node. */
1999 update_call_expr (new_version_node);
2001 cgraph_call_function_insertion_hooks (new_version_node);
2002 return new_version_node;
2005 /* Produce separate function body for inline clones so the offline copy can be
2006 modified without affecting them. */
2007 struct cgraph_node *
2008 save_inline_function_body (struct cgraph_node *node)
2010 struct cgraph_node *first_clone, *n;
2012 gcc_assert (node == cgraph_node (node->decl));
2014 cgraph_lower_function (node);
2016 first_clone = node->clones;
2018 first_clone->decl = copy_node (node->decl);
2019 cgraph_insert_node_to_hashtable (first_clone);
2020 gcc_assert (first_clone == cgraph_node (first_clone->decl));
2021 if (first_clone->next_sibling_clone)
2023 for (n = first_clone->next_sibling_clone; n->next_sibling_clone; n = n->next_sibling_clone)
2024 n->clone_of = first_clone;
2025 n->clone_of = first_clone;
2026 n->next_sibling_clone = first_clone->clones;
2027 if (first_clone->clones)
2028 first_clone->clones->prev_sibling_clone = n;
2029 first_clone->clones = first_clone->next_sibling_clone;
2030 first_clone->next_sibling_clone->prev_sibling_clone = NULL;
2031 first_clone->next_sibling_clone = NULL;
2032 gcc_assert (!first_clone->prev_sibling_clone);
2034 first_clone->clone_of = NULL;
2035 node->clones = NULL;
2037 if (first_clone->clones)
2038 for (n = first_clone->clones; n != first_clone;)
2040 gcc_assert (n->decl == node->decl);
2041 n->decl = first_clone->decl;
2044 else if (n->next_sibling_clone)
2045 n = n->next_sibling_clone;
2048 while (n != first_clone && !n->next_sibling_clone)
2050 if (n != first_clone)
2051 n = n->next_sibling_clone;
2055 /* Copy the OLD_VERSION_NODE function tree to the new version. */
2056 tree_function_versioning (node->decl, first_clone->decl, NULL, true, NULL,
2059 DECL_EXTERNAL (first_clone->decl) = 0;
2060 DECL_COMDAT_GROUP (first_clone->decl) = NULL_TREE;
2061 TREE_PUBLIC (first_clone->decl) = 0;
2062 DECL_COMDAT (first_clone->decl) = 0;
2063 VEC_free (ipa_opt_pass, heap,
2064 first_clone->ipa_transforms_to_apply);
2065 first_clone->ipa_transforms_to_apply = NULL;
2067 #ifdef ENABLE_CHECKING
2068 verify_cgraph_node (first_clone);
2073 /* Given virtual clone, turn it into actual clone. */
2075 cgraph_materialize_clone (struct cgraph_node *node)
2077 bitmap_obstack_initialize (NULL);
2078 node->former_clone_of = node->clone_of->decl;
2079 if (node->clone_of->former_clone_of)
2080 node->former_clone_of = node->clone_of->former_clone_of;
2081 /* Copy the OLD_VERSION_NODE function tree to the new version. */
2082 tree_function_versioning (node->clone_of->decl, node->decl,
2083 node->clone.tree_map, true,
2084 node->clone.args_to_skip, NULL, NULL);
2085 if (cgraph_dump_file)
2087 dump_function_to_file (node->clone_of->decl, cgraph_dump_file, dump_flags);
2088 dump_function_to_file (node->decl, cgraph_dump_file, dump_flags);
2091 /* Function is no longer clone. */
2092 if (node->next_sibling_clone)
2093 node->next_sibling_clone->prev_sibling_clone = node->prev_sibling_clone;
2094 if (node->prev_sibling_clone)
2095 node->prev_sibling_clone->next_sibling_clone = node->next_sibling_clone;
2097 node->clone_of->clones = node->next_sibling_clone;
2098 node->next_sibling_clone = NULL;
2099 node->prev_sibling_clone = NULL;
2100 if (!node->clone_of->analyzed && !node->clone_of->clones)
2102 cgraph_release_function_body (node->clone_of);
2103 cgraph_node_remove_callees (node->clone_of);
2104 ipa_remove_all_references (&node->clone_of->ref_list);
2106 node->clone_of = NULL;
2107 bitmap_obstack_release (NULL);
2110 /* If necessary, change the function declaration in the call statement
2111 associated with E so that it corresponds to the edge callee. */
2114 cgraph_redirect_edge_call_stmt_to_callee (struct cgraph_edge *e)
2116 tree decl = gimple_call_fndecl (e->call_stmt);
2118 #ifdef ENABLE_CHECKING
2119 struct cgraph_node *node;
2122 if (e->indirect_unknown_callee
2123 || decl == e->callee->decl
2124 /* Don't update call from same body alias to the real function. */
2125 || (decl && cgraph_get_node (decl) == cgraph_get_node (e->callee->decl)))
2126 return e->call_stmt;
2128 #ifdef ENABLE_CHECKING
2131 node = cgraph_get_node (decl);
2132 gcc_assert (!node || !node->clone.combined_args_to_skip);
2136 if (cgraph_dump_file)
2138 fprintf (cgraph_dump_file, "updating call of %s/%i -> %s/%i: ",
2139 cgraph_node_name (e->caller), e->caller->uid,
2140 cgraph_node_name (e->callee), e->callee->uid);
2141 print_gimple_stmt (cgraph_dump_file, e->call_stmt, 0, dump_flags);
2142 if (e->callee->clone.combined_args_to_skip)
2144 fprintf (cgraph_dump_file, " combined args to skip: ");
2145 dump_bitmap (cgraph_dump_file,
2146 e->callee->clone.combined_args_to_skip);
2150 if (e->callee->clone.combined_args_to_skip)
2152 gimple_stmt_iterator gsi;
2156 = gimple_call_copy_skip_args (e->call_stmt,
2157 e->callee->clone.combined_args_to_skip);
2158 gimple_call_set_fndecl (new_stmt, e->callee->decl);
2160 if (gimple_vdef (new_stmt)
2161 && TREE_CODE (gimple_vdef (new_stmt)) == SSA_NAME)
2162 SSA_NAME_DEF_STMT (gimple_vdef (new_stmt)) = new_stmt;
2164 gsi = gsi_for_stmt (e->call_stmt);
2165 gsi_replace (&gsi, new_stmt, false);
2166 /* We need to defer cleaning EH info on the new statement to
2167 fixup-cfg. We may not have dominator information at this point
2168 and thus would end up with unreachable blocks and have no way
2169 to communicate that we need to run CFG cleanup then. */
2170 lp_nr = lookup_stmt_eh_lp (e->call_stmt);
2173 remove_stmt_from_eh_lp (e->call_stmt);
2174 add_stmt_to_eh_lp (new_stmt, lp_nr);
2179 new_stmt = e->call_stmt;
2180 gimple_call_set_fndecl (new_stmt, e->callee->decl);
2181 update_stmt (new_stmt);
2184 cgraph_set_call_stmt_including_clones (e->caller, e->call_stmt, new_stmt);
2186 if (cgraph_dump_file)
2188 fprintf (cgraph_dump_file, " updated to:");
2189 print_gimple_stmt (cgraph_dump_file, e->call_stmt, 0, dump_flags);
2194 /* Once all functions from compilation unit are in memory, produce all clones
2195 and update all calls. We might also do this on demand if we don't want to
2196 bring all functions to memory prior compilation, but current WHOPR
2197 implementation does that and it is is bit easier to keep everything right in
2200 cgraph_materialize_all_clones (void)
2202 struct cgraph_node *node;
2203 bool stabilized = false;
2205 if (cgraph_dump_file)
2206 fprintf (cgraph_dump_file, "Materializing clones\n");
2207 #ifdef ENABLE_CHECKING
2211 /* We can also do topological order, but number of iterations should be
2212 bounded by number of IPA passes since single IPA pass is probably not
2213 going to create clones of clones it created itself. */
2217 for (node = cgraph_nodes; node; node = node->next)
2219 if (node->clone_of && node->decl != node->clone_of->decl
2220 && !gimple_has_body_p (node->decl))
2222 if (gimple_has_body_p (node->clone_of->decl))
2224 if (cgraph_dump_file)
2226 fprintf (cgraph_dump_file, "clonning %s to %s\n",
2227 cgraph_node_name (node->clone_of),
2228 cgraph_node_name (node));
2229 if (node->clone.tree_map)
2232 fprintf (cgraph_dump_file, " replace map: ");
2233 for (i = 0; i < VEC_length (ipa_replace_map_p,
2234 node->clone.tree_map);
2237 struct ipa_replace_map *replace_info;
2238 replace_info = VEC_index (ipa_replace_map_p,
2239 node->clone.tree_map,
2241 print_generic_expr (cgraph_dump_file, replace_info->old_tree, 0);
2242 fprintf (cgraph_dump_file, " -> ");
2243 print_generic_expr (cgraph_dump_file, replace_info->new_tree, 0);
2244 fprintf (cgraph_dump_file, "%s%s;",
2245 replace_info->replace_p ? "(replace)":"",
2246 replace_info->ref_p ? "(ref)":"");
2248 fprintf (cgraph_dump_file, "\n");
2250 if (node->clone.args_to_skip)
2252 fprintf (cgraph_dump_file, " args_to_skip: ");
2253 dump_bitmap (cgraph_dump_file, node->clone.args_to_skip);
2255 if (node->clone.args_to_skip)
2257 fprintf (cgraph_dump_file, " combined_args_to_skip:");
2258 dump_bitmap (cgraph_dump_file, node->clone.combined_args_to_skip);
2261 cgraph_materialize_clone (node);
2267 for (node = cgraph_nodes; node; node = node->next)
2268 if (!node->analyzed && node->callees)
2269 cgraph_node_remove_callees (node);
2270 if (cgraph_dump_file)
2271 fprintf (cgraph_dump_file, "Materialization Call site updates done.\n");
2272 #ifdef ENABLE_CHECKING
2275 cgraph_remove_unreachable_nodes (false, cgraph_dump_file);
2278 #include "gt-cgraphunit.h"