1 /* Callgraph based interprocedural optimizations.
2 Copyright (C) 2003, 2004, 2005, 2006, 2007, 2008, 2009
3 Free Software Foundation, Inc.
4 Contributed by Jan Hubicka
6 This file is part of GCC.
8 GCC is free software; you can redistribute it and/or modify it under
9 the terms of the GNU General Public License as published by the Free
10 Software Foundation; either version 3, or (at your option) any later
13 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
14 WARRANTY; without even the implied warranty of MERCHANTABILITY or
15 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
18 You should have received a copy of the GNU General Public License
19 along with GCC; see the file COPYING3. If not see
20 <http://www.gnu.org/licenses/>. */
22 /* This module implements main driver of compilation process as well as
23 few basic interprocedural optimizers.
25 The main scope of this file is to act as an interface in between
26 tree based frontends and the backend (and middle end)
28 The front-end is supposed to use following functionality:
30 - cgraph_finalize_function
32 This function is called once front-end has parsed whole body of function
33 and it is certain that the function body nor the declaration will change.
35 (There is one exception needed for implementing GCC extern inline
38 - varpool_finalize_variable
40 This function has same behavior as the above but is used for static
43 - cgraph_finalize_compilation_unit
45 This function is called once (source level) compilation unit is finalized
46 and it will no longer change.
48 In the the call-graph construction and local function
49 analysis takes place here. Bodies of unreachable functions are released
50 to conserve memory usage.
52 The function can be called multiple times when multiple source level
53 compilation units are combined (such as in C frontend)
57 In this unit-at-a-time compilation the intra procedural analysis takes
58 place here. In particular the static functions whose address is never
59 taken are marked as local. Backend can then use this information to
60 modify calling conventions, do better inlining or similar optimizations.
62 - cgraph_mark_needed_node
63 - varpool_mark_needed_node
65 When function or variable is referenced by some hidden way the call-graph
66 data structure must be updated accordingly by this function.
67 There should be little need to call this function and all the references
68 should be made explicit to cgraph code. At present these functions are
69 used by C++ frontend to explicitly mark the keyed methods.
71 - analyze_expr callback
73 This function is responsible for lowering tree nodes not understood by
74 generic code into understandable ones or alternatively marking
75 callgraph and varpool nodes referenced by the as needed.
77 ??? On the tree-ssa genericizing should take place here and we will avoid
78 need for these hooks (replacing them by genericizing hook)
80 Analyzing of all functions is deferred
81 to cgraph_finalize_compilation_unit and expansion into cgraph_optimize.
83 In cgraph_finalize_compilation_unit the reachable functions are
84 analyzed. During analysis the call-graph edges from reachable
85 functions are constructed and their destinations are marked as
86 reachable. References to functions and variables are discovered too
87 and variables found to be needed output to the assembly file. Via
88 mark_referenced call in assemble_variable functions referenced by
89 static variables are noticed too.
91 The intra-procedural information is produced and its existence
92 indicated by global_info_ready. Once this flag is set it is impossible
93 to change function from !reachable to reachable and thus
94 assemble_variable no longer call mark_referenced.
96 Finally the call-graph is topologically sorted and all reachable functions
97 that has not been completely inlined or are not external are output.
99 ??? It is possible that reference to function or variable is optimized
100 out. We can not deal with this nicely because topological order is not
101 suitable for it. For tree-ssa we may consider another pass doing
102 optimization and re-discovering reachable functions.
104 ??? Reorganize code so variables are output very last and only if they
105 really has been referenced by produced code, so we catch more cases
106 where reference has been optimized out. */
111 #include "coretypes.h"
115 #include "tree-flow.h"
116 #include "tree-inline.h"
117 #include "langhooks.h"
118 #include "pointer-set.h"
125 #include "diagnostic.h"
130 #include "function.h"
131 #include "ipa-prop.h"
133 #include "tree-iterator.h"
134 #include "tree-pass.h"
135 #include "tree-dump.h"
137 #include "coverage.h"
139 static void cgraph_expand_all_functions (void);
140 static void cgraph_mark_functions_to_output (void);
141 static void cgraph_expand_function (struct cgraph_node *);
142 static void cgraph_output_pending_asms (void);
143 static void cgraph_analyze_function (struct cgraph_node *);
145 static FILE *cgraph_dump_file;
147 /* A vector of FUNCTION_DECLs declared as static constructors. */
148 static GTY (()) VEC(tree, gc) *static_ctors;
149 /* A vector of FUNCTION_DECLs declared as static destructors. */
150 static GTY (()) VEC(tree, gc) *static_dtors;
152 /* Used for vtable lookup in thunk adjusting. */
153 static GTY (()) tree vtable_entry_type;
155 /* When target does not have ctors and dtors, we call all constructor
156 and destructor by special initialization/destruction function
157 recognized by collect2.
159 When we are going to build this function, collect all constructors and
160 destructors and turn them into normal functions. */
163 record_cdtor_fn (tree fndecl)
165 struct cgraph_node *node;
166 if (targetm.have_ctors_dtors
167 || (!DECL_STATIC_CONSTRUCTOR (fndecl)
168 && !DECL_STATIC_DESTRUCTOR (fndecl)))
171 if (DECL_STATIC_CONSTRUCTOR (fndecl))
173 VEC_safe_push (tree, gc, static_ctors, fndecl);
174 DECL_STATIC_CONSTRUCTOR (fndecl) = 0;
176 if (DECL_STATIC_DESTRUCTOR (fndecl))
178 VEC_safe_push (tree, gc, static_dtors, fndecl);
179 DECL_STATIC_DESTRUCTOR (fndecl) = 0;
181 node = cgraph_node (fndecl);
182 node->local.disregard_inline_limits = 1;
183 cgraph_mark_reachable_node (node);
186 /* Define global constructors/destructor functions for the CDTORS, of
187 which they are LEN. The CDTORS are sorted by initialization
188 priority. If CTOR_P is true, these are constructors; otherwise,
189 they are destructors. */
192 build_cdtor (bool ctor_p, tree *cdtors, size_t len)
201 priority_type priority;
205 /* Find the next batch of constructors/destructors with the same
206 initialization priority. */
211 p = ctor_p ? DECL_INIT_PRIORITY (fn) : DECL_FINI_PRIORITY (fn);
214 else if (p != priority)
216 append_to_statement_list (build_function_call_expr (UNKNOWN_LOCATION,
222 gcc_assert (body != NULL_TREE);
223 /* Generate a function to call all the function of like
225 cgraph_build_static_cdtor (ctor_p ? 'I' : 'D', body, priority);
229 /* Comparison function for qsort. P1 and P2 are actually of type
230 "tree *" and point to static constructors. DECL_INIT_PRIORITY is
231 used to determine the sort order. */
234 compare_ctor (const void *p1, const void *p2)
241 f1 = *(const tree *)p1;
242 f2 = *(const tree *)p2;
243 priority1 = DECL_INIT_PRIORITY (f1);
244 priority2 = DECL_INIT_PRIORITY (f2);
246 if (priority1 < priority2)
248 else if (priority1 > priority2)
251 /* Ensure a stable sort. */
252 return (const tree *)p1 - (const tree *)p2;
255 /* Comparison function for qsort. P1 and P2 are actually of type
256 "tree *" and point to static destructors. DECL_FINI_PRIORITY is
257 used to determine the sort order. */
260 compare_dtor (const void *p1, const void *p2)
267 f1 = *(const tree *)p1;
268 f2 = *(const tree *)p2;
269 priority1 = DECL_FINI_PRIORITY (f1);
270 priority2 = DECL_FINI_PRIORITY (f2);
272 if (priority1 < priority2)
274 else if (priority1 > priority2)
277 /* Ensure a stable sort. */
278 return (const tree *)p1 - (const tree *)p2;
281 /* Generate functions to call static constructors and destructors
282 for targets that do not support .ctors/.dtors sections. These
283 functions have magic names which are detected by collect2. */
286 cgraph_build_cdtor_fns (void)
288 if (!VEC_empty (tree, static_ctors))
290 gcc_assert (!targetm.have_ctors_dtors);
291 qsort (VEC_address (tree, static_ctors),
292 VEC_length (tree, static_ctors),
295 build_cdtor (/*ctor_p=*/true,
296 VEC_address (tree, static_ctors),
297 VEC_length (tree, static_ctors));
298 VEC_truncate (tree, static_ctors, 0);
301 if (!VEC_empty (tree, static_dtors))
303 gcc_assert (!targetm.have_ctors_dtors);
304 qsort (VEC_address (tree, static_dtors),
305 VEC_length (tree, static_dtors),
308 build_cdtor (/*ctor_p=*/false,
309 VEC_address (tree, static_dtors),
310 VEC_length (tree, static_dtors));
311 VEC_truncate (tree, static_dtors, 0);
315 /* Determine if function DECL is needed. That is, visible to something
316 either outside this translation unit, something magic in the system
320 cgraph_decide_is_function_needed (struct cgraph_node *node, tree decl)
322 /* If the user told us it is used, then it must be so. */
323 if (node->local.externally_visible)
326 /* ??? If the assembler name is set by hand, it is possible to assemble
327 the name later after finalizing the function and the fact is noticed
328 in assemble_name then. This is arguably a bug. */
329 if (DECL_ASSEMBLER_NAME_SET_P (decl)
330 && TREE_SYMBOL_REFERENCED (DECL_ASSEMBLER_NAME (decl)))
333 /* With -fkeep-inline-functions we are keeping all inline functions except
334 for extern inline ones. */
335 if (flag_keep_inline_functions
336 && DECL_DECLARED_INLINE_P (decl)
337 && !DECL_EXTERNAL (decl)
338 && !lookup_attribute ("always_inline", DECL_ATTRIBUTES (decl)))
341 /* If we decided it was needed before, but at the time we didn't have
342 the body of the function available, then it's still needed. We have
343 to go back and re-check its dependencies now. */
347 /* Externally visible functions must be output. The exception is
348 COMDAT functions that must be output only when they are needed.
350 When not optimizing, also output the static functions. (see
351 PR24561), but don't do so for always_inline functions, functions
352 declared inline and nested functions. These was optimized out
353 in the original implementation and it is unclear whether we want
354 to change the behavior here. */
355 if (((TREE_PUBLIC (decl)
356 || (!optimize && !node->local.disregard_inline_limits
357 && !DECL_DECLARED_INLINE_P (decl)
359 && !flag_whole_program
362 && !DECL_COMDAT (decl) && !DECL_EXTERNAL (decl))
365 /* Constructors and destructors are reachable from the runtime by
367 if (DECL_STATIC_CONSTRUCTOR (decl) || DECL_STATIC_DESTRUCTOR (decl))
373 /* Process CGRAPH_NEW_FUNCTIONS and perform actions necessary to add these
374 functions into callgraph in a way so they look like ordinary reachable
375 functions inserted into callgraph already at construction time. */
378 cgraph_process_new_functions (void)
382 struct cgraph_node *node;
384 /* Note that this queue may grow as its being processed, as the new
385 functions may generate new ones. */
386 while (cgraph_new_nodes)
388 node = cgraph_new_nodes;
390 cgraph_new_nodes = cgraph_new_nodes->next_needed;
391 switch (cgraph_state)
393 case CGRAPH_STATE_CONSTRUCTION:
394 /* At construction time we just need to finalize function and move
395 it into reachable functions list. */
397 node->next_needed = NULL;
398 cgraph_finalize_function (fndecl, false);
399 cgraph_mark_reachable_node (node);
403 case CGRAPH_STATE_IPA:
404 case CGRAPH_STATE_IPA_SSA:
405 /* When IPA optimization already started, do all essential
406 transformations that has been already performed on the whole
407 cgraph but not on this function. */
409 gimple_register_cfg_hooks ();
411 cgraph_analyze_function (node);
412 push_cfun (DECL_STRUCT_FUNCTION (fndecl));
413 current_function_decl = fndecl;
414 compute_inline_parameters (node);
415 if ((cgraph_state == CGRAPH_STATE_IPA_SSA
416 && !gimple_in_ssa_p (DECL_STRUCT_FUNCTION (fndecl)))
417 /* When not optimizing, be sure we run early local passes anyway
420 execute_pass_list (pass_early_local_passes.pass.sub);
421 free_dominance_info (CDI_POST_DOMINATORS);
422 free_dominance_info (CDI_DOMINATORS);
424 current_function_decl = NULL;
427 case CGRAPH_STATE_EXPANSION:
428 /* Functions created during expansion shall be compiled
431 cgraph_expand_function (node);
438 cgraph_call_function_insertion_hooks (node);
443 /* As an GCC extension we allow redefinition of the function. The
444 semantics when both copies of bodies differ is not well defined.
445 We replace the old body with new body so in unit at a time mode
446 we always use new body, while in normal mode we may end up with
447 old body inlined into some functions and new body expanded and
450 ??? It may make more sense to use one body for inlining and other
451 body for expanding the function but this is difficult to do. */
454 cgraph_reset_node (struct cgraph_node *node)
456 /* If node->process is set, then we have already begun whole-unit analysis.
457 This is *not* testing for whether we've already emitted the function.
458 That case can be sort-of legitimately seen with real function redefinition
459 errors. I would argue that the front end should never present us with
460 such a case, but don't enforce that for now. */
461 gcc_assert (!node->process);
463 /* Reset our data structures so we can analyze the function again. */
464 memset (&node->local, 0, sizeof (node->local));
465 memset (&node->global, 0, sizeof (node->global));
466 memset (&node->rtl, 0, sizeof (node->rtl));
467 node->analyzed = false;
468 node->local.redefined_extern_inline = true;
469 node->local.finalized = false;
471 cgraph_node_remove_callees (node);
473 /* We may need to re-queue the node for assembling in case
474 we already proceeded it and ignored as not needed or got
475 a re-declaration in IMA mode. */
478 struct cgraph_node *n;
480 for (n = cgraph_nodes_queue; n; n = n->next_needed)
489 cgraph_lower_function (struct cgraph_node *node)
495 lower_nested_functions (node->decl);
496 gcc_assert (!node->nested);
498 tree_lowering_passes (node->decl);
499 node->lowered = true;
502 /* DECL has been parsed. Take it, queue it, compile it at the whim of the
503 logic in effect. If NESTED is true, then our caller cannot stand to have
504 the garbage collector run at the moment. We would need to either create
505 a new GC context, or just not compile right now. */
508 cgraph_finalize_function (tree decl, bool nested)
510 struct cgraph_node *node = cgraph_node (decl);
512 if (node->local.finalized)
513 cgraph_reset_node (node);
515 node->pid = cgraph_max_pid ++;
516 notice_global_symbol (decl);
517 node->local.finalized = true;
518 node->lowered = DECL_STRUCT_FUNCTION (decl)->cfg != NULL;
519 node->finalized_by_frontend = true;
520 record_cdtor_fn (node->decl);
522 if (cgraph_decide_is_function_needed (node, decl))
523 cgraph_mark_needed_node (node);
525 /* Since we reclaim unreachable nodes at the end of every language
526 level unit, we need to be conservative about possible entry points
528 if ((TREE_PUBLIC (decl) && !DECL_COMDAT (decl) && !DECL_EXTERNAL (decl)))
529 cgraph_mark_reachable_node (node);
531 /* If we've not yet emitted decl, tell the debug info about it. */
532 if (!TREE_ASM_WRITTEN (decl))
533 (*debug_hooks->deferred_inline_function) (decl);
535 /* Possibly warn about unused parameters. */
536 if (warn_unused_parameter)
537 do_warn_unused_parameter (decl);
543 /* C99 extern inline keywords allow changing of declaration after function
544 has been finalized. We need to re-decide if we want to mark the function as
548 cgraph_mark_if_needed (tree decl)
550 struct cgraph_node *node = cgraph_node (decl);
551 if (node->local.finalized && cgraph_decide_is_function_needed (node, decl))
552 cgraph_mark_needed_node (node);
555 /* Return TRUE if NODE2 is equivalent to NODE or its clone. */
557 clone_of_p (struct cgraph_node *node, struct cgraph_node *node2)
559 while (node != node2 && node2)
560 node2 = node2->clone_of;
561 return node2 != NULL;
564 /* Verify cgraph nodes of given cgraph node. */
566 verify_cgraph_node (struct cgraph_node *node)
568 struct cgraph_edge *e;
569 struct function *this_cfun = DECL_STRUCT_FUNCTION (node->decl);
570 struct function *saved_cfun = cfun;
571 basic_block this_block;
572 gimple_stmt_iterator gsi;
573 bool error_found = false;
575 if (errorcount || sorrycount)
578 timevar_push (TV_CGRAPH_VERIFY);
579 /* debug_generic_stmt needs correct cfun */
580 set_cfun (this_cfun);
581 for (e = node->callees; e; e = e->next_callee)
584 error ("aux field set for edge %s->%s",
585 identifier_to_locale (cgraph_node_name (e->caller)),
586 identifier_to_locale (cgraph_node_name (e->callee)));
591 error ("Execution count is negative");
594 if (node->global.inlined_to && node->local.externally_visible)
596 error ("Externally visible inline clone");
599 if (node->global.inlined_to && node->address_taken)
601 error ("Inline clone with address taken");
604 if (node->global.inlined_to && node->needed)
606 error ("Inline clone is needed");
609 for (e = node->callers; e; e = e->next_caller)
613 error ("caller edge count is negative");
616 if (e->frequency < 0)
618 error ("caller edge frequency is negative");
621 if (e->frequency > CGRAPH_FREQ_MAX)
623 error ("caller edge frequency is too large");
626 if (gimple_has_body_p (e->caller->decl)
627 && !e->caller->global.inlined_to
629 != compute_call_stmt_bb_frequency (e->caller->decl,
630 gimple_bb (e->call_stmt))))
632 error ("caller edge frequency %i does not match BB freqency %i",
634 compute_call_stmt_bb_frequency (e->caller->decl,
635 gimple_bb (e->call_stmt)));
638 if (!e->inline_failed)
640 if (node->global.inlined_to
641 != (e->caller->global.inlined_to
642 ? e->caller->global.inlined_to : e->caller))
644 error ("inlined_to pointer is wrong");
647 if (node->callers->next_caller)
649 error ("multiple inline callers");
654 if (node->global.inlined_to)
656 error ("inlined_to pointer set for noninline callers");
660 if (!node->callers && node->global.inlined_to)
662 error ("inlined_to pointer is set but no predecessors found");
665 if (node->global.inlined_to == node)
667 error ("inlined_to pointer refers to itself");
671 if (!cgraph_node (node->decl))
673 error ("node not found in cgraph_hash");
679 struct cgraph_node *n;
680 for (n = node->clone_of->clones; n; n = n->next_sibling_clone)
685 error ("node has wrong clone_of");
691 struct cgraph_node *n;
692 for (n = node->clones; n; n = n->next_sibling_clone)
693 if (n->clone_of != node)
697 error ("node has wrong clone list");
701 if ((node->prev_sibling_clone || node->next_sibling_clone) && !node->clone_of)
703 error ("node is in clone list but it is not clone");
706 if (!node->prev_sibling_clone && node->clone_of && node->clone_of->clones != node)
708 error ("node has wrong prev_clone pointer");
711 if (node->prev_sibling_clone && node->prev_sibling_clone->next_sibling_clone != node)
713 error ("double linked list of clones corrupted");
717 if (node->analyzed && gimple_has_body_p (node->decl)
718 && !TREE_ASM_WRITTEN (node->decl)
719 && (!DECL_EXTERNAL (node->decl) || node->global.inlined_to)
724 /* The nodes we're interested in are never shared, so walk
725 the tree ignoring duplicates. */
726 struct pointer_set_t *visited_nodes = pointer_set_create ();
727 /* Reach the trees by walking over the CFG, and note the
728 enclosing basic-blocks in the call edges. */
729 FOR_EACH_BB_FN (this_block, this_cfun)
730 for (gsi = gsi_start_bb (this_block);
734 gimple stmt = gsi_stmt (gsi);
736 if (is_gimple_call (stmt) && (decl = gimple_call_fndecl (stmt)))
738 struct cgraph_edge *e = cgraph_edge (node, stmt);
743 error ("shared call_stmt:");
744 debug_gimple_stmt (stmt);
747 if (e->callee->same_body_alias)
749 error ("edge points to same body alias:");
750 debug_tree (e->callee->decl);
752 else if (!clone_of_p (cgraph_node (decl), e->callee)
753 && !e->callee->global.inlined_to)
755 error ("edge points to wrong declaration:");
756 debug_tree (e->callee->decl);
757 fprintf (stderr," Instead of:");
764 error ("missing callgraph edge for call stmt:");
765 debug_gimple_stmt (stmt);
770 pointer_set_destroy (visited_nodes);
773 /* No CFG available?! */
776 for (e = node->callees; e; e = e->next_callee)
778 if (!e->aux && !e->indirect_call)
780 error ("edge %s->%s has no corresponding call_stmt",
781 identifier_to_locale (cgraph_node_name (e->caller)),
782 identifier_to_locale (cgraph_node_name (e->callee)));
783 debug_gimple_stmt (e->call_stmt);
791 dump_cgraph_node (stderr, node);
792 internal_error ("verify_cgraph_node failed");
794 set_cfun (saved_cfun);
795 timevar_pop (TV_CGRAPH_VERIFY);
798 /* Verify whole cgraph structure. */
802 struct cgraph_node *node;
804 if (sorrycount || errorcount)
807 for (node = cgraph_nodes; node; node = node->next)
808 verify_cgraph_node (node);
811 /* Output all asm statements we have stored up to be output. */
814 cgraph_output_pending_asms (void)
816 struct cgraph_asm_node *can;
818 if (errorcount || sorrycount)
821 for (can = cgraph_asm_nodes; can; can = can->next)
822 assemble_asm (can->asm_str);
823 cgraph_asm_nodes = NULL;
826 /* Analyze the function scheduled to be output. */
828 cgraph_analyze_function (struct cgraph_node *node)
830 tree save = current_function_decl;
831 tree decl = node->decl;
833 current_function_decl = decl;
834 push_cfun (DECL_STRUCT_FUNCTION (decl));
836 /* Make sure to gimplify bodies only once. During analyzing a
837 function we lower it, which will require gimplified nested
838 functions, so we can end up here with an already gimplified
840 if (!gimple_body (decl))
841 gimplify_function_tree (decl);
842 dump_function (TDI_generic, decl);
844 cgraph_lower_function (node);
845 node->analyzed = true;
848 current_function_decl = save;
851 /* Look for externally_visible and used attributes and mark cgraph nodes
854 We cannot mark the nodes at the point the attributes are processed (in
855 handle_*_attribute) because the copy of the declarations available at that
856 point may not be canonical. For example, in:
859 void f() __attribute__((used));
861 the declaration we see in handle_used_attribute will be the second
862 declaration -- but the front end will subsequently merge that declaration
863 with the original declaration and discard the second declaration.
865 Furthermore, we can't mark these nodes in cgraph_finalize_function because:
868 void f() __attribute__((externally_visible));
872 So, we walk the nodes at the end of the translation unit, applying the
873 attributes at that point. */
876 process_function_and_variable_attributes (struct cgraph_node *first,
877 struct varpool_node *first_var)
879 struct cgraph_node *node;
880 struct varpool_node *vnode;
882 for (node = cgraph_nodes; node != first; node = node->next)
884 tree decl = node->decl;
885 if (lookup_attribute ("used", DECL_ATTRIBUTES (decl)))
887 mark_decl_referenced (decl);
888 if (node->local.finalized)
889 cgraph_mark_needed_node (node);
891 if (lookup_attribute ("externally_visible", DECL_ATTRIBUTES (decl)))
893 if (! TREE_PUBLIC (node->decl))
894 warning_at (DECL_SOURCE_LOCATION (node->decl), OPT_Wattributes,
895 "%<externally_visible%>"
896 " attribute have effect only on public objects");
897 else if (node->local.finalized)
898 cgraph_mark_needed_node (node);
901 for (vnode = varpool_nodes; vnode != first_var; vnode = vnode->next)
903 tree decl = vnode->decl;
904 if (lookup_attribute ("used", DECL_ATTRIBUTES (decl)))
906 mark_decl_referenced (decl);
907 vnode->force_output = true;
908 if (vnode->finalized)
909 varpool_mark_needed_node (vnode);
911 if (lookup_attribute ("externally_visible", DECL_ATTRIBUTES (decl)))
913 if (! TREE_PUBLIC (vnode->decl))
914 warning_at (DECL_SOURCE_LOCATION (vnode->decl), OPT_Wattributes,
915 "%<externally_visible%>"
916 " attribute have effect only on public objects");
917 else if (vnode->finalized)
918 varpool_mark_needed_node (vnode);
923 /* Process CGRAPH_NODES_NEEDED queue, analyze each function (and transitively
924 each reachable functions) and build cgraph.
925 The function can be called multiple times after inserting new nodes
926 into beginning of queue. Just the new part of queue is re-scanned then. */
929 cgraph_analyze_functions (void)
931 /* Keep track of already processed nodes when called multiple times for
932 intermodule optimization. */
933 static struct cgraph_node *first_analyzed;
934 struct cgraph_node *first_processed = first_analyzed;
935 static struct varpool_node *first_analyzed_var;
936 struct cgraph_node *node, *next;
938 process_function_and_variable_attributes (first_processed,
940 first_processed = cgraph_nodes;
941 first_analyzed_var = varpool_nodes;
942 varpool_analyze_pending_decls ();
943 if (cgraph_dump_file)
945 fprintf (cgraph_dump_file, "Initial entry points:");
946 for (node = cgraph_nodes; node != first_analyzed; node = node->next)
948 fprintf (cgraph_dump_file, " %s", cgraph_node_name (node));
949 fprintf (cgraph_dump_file, "\n");
951 cgraph_process_new_functions ();
953 /* Propagate reachability flag and lower representation of all reachable
954 functions. In the future, lowering will introduce new functions and
955 new entry points on the way (by template instantiation and virtual
956 method table generation for instance). */
957 while (cgraph_nodes_queue)
959 struct cgraph_edge *edge;
960 tree decl = cgraph_nodes_queue->decl;
962 node = cgraph_nodes_queue;
963 cgraph_nodes_queue = cgraph_nodes_queue->next_needed;
964 node->next_needed = NULL;
966 /* ??? It is possible to create extern inline function and later using
967 weak alias attribute to kill its body. See
968 gcc.c-torture/compile/20011119-1.c */
969 if (!DECL_STRUCT_FUNCTION (decl))
971 cgraph_reset_node (node);
976 cgraph_analyze_function (node);
978 for (edge = node->callees; edge; edge = edge->next_callee)
979 if (!edge->callee->reachable)
980 cgraph_mark_reachable_node (edge->callee);
982 /* If decl is a clone of an abstract function, mark that abstract
983 function so that we don't release its body. The DECL_INITIAL() of that
984 abstract function declaration will be later needed to output debug info. */
985 if (DECL_ABSTRACT_ORIGIN (decl))
987 struct cgraph_node *origin_node = cgraph_node (DECL_ABSTRACT_ORIGIN (decl));
988 origin_node->abstract_and_needed = true;
991 /* We finalize local static variables during constructing callgraph
992 edges. Process their attributes too. */
993 process_function_and_variable_attributes (first_processed,
995 first_processed = cgraph_nodes;
996 first_analyzed_var = varpool_nodes;
997 varpool_analyze_pending_decls ();
998 cgraph_process_new_functions ();
1001 /* Collect entry points to the unit. */
1002 if (cgraph_dump_file)
1004 fprintf (cgraph_dump_file, "Unit entry points:");
1005 for (node = cgraph_nodes; node != first_analyzed; node = node->next)
1007 fprintf (cgraph_dump_file, " %s", cgraph_node_name (node));
1008 fprintf (cgraph_dump_file, "\n\nInitial ");
1009 dump_cgraph (cgraph_dump_file);
1012 if (cgraph_dump_file)
1013 fprintf (cgraph_dump_file, "\nReclaiming functions:");
1015 for (node = cgraph_nodes; node != first_analyzed; node = next)
1017 tree decl = node->decl;
1020 if (node->local.finalized && !gimple_has_body_p (decl))
1021 cgraph_reset_node (node);
1023 if (!node->reachable && gimple_has_body_p (decl))
1025 if (cgraph_dump_file)
1026 fprintf (cgraph_dump_file, " %s", cgraph_node_name (node));
1027 cgraph_remove_node (node);
1031 node->next_needed = NULL;
1032 gcc_assert (!node->local.finalized || gimple_has_body_p (decl));
1033 gcc_assert (node->analyzed == node->local.finalized);
1035 if (cgraph_dump_file)
1037 fprintf (cgraph_dump_file, "\n\nReclaimed ");
1038 dump_cgraph (cgraph_dump_file);
1040 first_analyzed = cgraph_nodes;
1045 /* Analyze the whole compilation unit once it is parsed completely. */
1048 cgraph_finalize_compilation_unit (void)
1050 timevar_push (TV_CGRAPH);
1052 /* Do not skip analyzing the functions if there were errors, we
1053 miss diagnostics for following functions otherwise. */
1055 /* Emit size functions we didn't inline. */
1056 finalize_size_functions ();
1058 /* Call functions declared with the "constructor" or "destructor"
1060 cgraph_build_cdtor_fns ();
1062 /* Mark alias targets necessary and emit diagnostics. */
1063 finish_aliases_1 ();
1067 fprintf (stderr, "\nAnalyzing compilation unit\n");
1071 /* Gimplify and lower all functions, compute reachability and
1072 remove unreachable nodes. */
1073 cgraph_analyze_functions ();
1075 /* Mark alias targets necessary and emit diagnostics. */
1076 finish_aliases_1 ();
1078 /* Gimplify and lower thunks. */
1079 cgraph_analyze_functions ();
1081 /* Finally drive the pass manager. */
1084 timevar_pop (TV_CGRAPH);
1088 /* Figure out what functions we want to assemble. */
1091 cgraph_mark_functions_to_output (void)
1093 struct cgraph_node *node;
1095 for (node = cgraph_nodes; node; node = node->next)
1097 tree decl = node->decl;
1098 struct cgraph_edge *e;
1100 gcc_assert (!node->process);
1102 for (e = node->callers; e; e = e->next_caller)
1103 if (e->inline_failed)
1106 /* We need to output all local functions that are used and not
1107 always inlined, as well as those that are reachable from
1108 outside the current compilation unit. */
1110 && !node->global.inlined_to
1112 || (e && node->reachable))
1113 && !TREE_ASM_WRITTEN (decl)
1114 && !DECL_EXTERNAL (decl))
1118 /* We should've reclaimed all functions that are not needed. */
1119 #ifdef ENABLE_CHECKING
1120 if (!node->global.inlined_to
1121 && gimple_has_body_p (decl)
1122 && !DECL_EXTERNAL (decl))
1124 dump_cgraph_node (stderr, node);
1125 internal_error ("failed to reclaim unneeded function");
1128 gcc_assert (node->global.inlined_to
1129 || !gimple_has_body_p (decl)
1130 || DECL_EXTERNAL (decl));
1137 /* DECL is FUNCTION_DECL. Initialize datastructures so DECL is a function
1138 in lowered gimple form.
1140 Set current_function_decl and cfun to newly constructed empty function body.
1141 return basic block in the function body. */
1144 init_lowered_empty_function (tree decl)
1148 current_function_decl = decl;
1149 allocate_struct_function (decl, false);
1150 gimple_register_cfg_hooks ();
1151 init_empty_tree_cfg ();
1152 init_tree_ssa (cfun);
1153 init_ssa_operands ();
1154 cfun->gimple_df->in_ssa_p = true;
1155 DECL_INITIAL (decl) = make_node (BLOCK);
1157 DECL_SAVED_TREE (decl) = error_mark_node;
1158 cfun->curr_properties |=
1159 (PROP_gimple_lcf | PROP_gimple_leh | PROP_cfg | PROP_referenced_vars |
1162 /* Create BB for body of the function and connect it properly. */
1163 bb = create_basic_block (NULL, (void *) 0, ENTRY_BLOCK_PTR);
1164 make_edge (ENTRY_BLOCK_PTR, bb, 0);
1165 make_edge (bb, EXIT_BLOCK_PTR, 0);
1170 /* Adjust PTR by the constant FIXED_OFFSET, and by the vtable
1171 offset indicated by VIRTUAL_OFFSET, if that is
1172 non-null. THIS_ADJUSTING is nonzero for a this adjusting thunk and
1173 zero for a result adjusting thunk. */
1176 thunk_adjust (gimple_stmt_iterator * bsi,
1177 tree ptr, bool this_adjusting,
1178 HOST_WIDE_INT fixed_offset, tree virtual_offset)
1185 stmt = gimple_build_assign (ptr,
1186 fold_build2_loc (input_location,
1188 TREE_TYPE (ptr), ptr,
1189 size_int (fixed_offset)));
1190 gsi_insert_after (bsi, stmt, GSI_NEW_STMT);
1193 /* If there's a virtual offset, look up that value in the vtable and
1194 adjust the pointer again. */
1202 if (!vtable_entry_type)
1204 tree vfunc_type = make_node (FUNCTION_TYPE);
1205 TREE_TYPE (vfunc_type) = integer_type_node;
1206 TYPE_ARG_TYPES (vfunc_type) = NULL_TREE;
1207 layout_type (vfunc_type);
1209 vtable_entry_type = build_pointer_type (vfunc_type);
1213 create_tmp_var (build_pointer_type
1214 (build_pointer_type (vtable_entry_type)), "vptr");
1216 /* The vptr is always at offset zero in the object. */
1217 stmt = gimple_build_assign (vtabletmp,
1218 build1 (NOP_EXPR, TREE_TYPE (vtabletmp),
1220 gsi_insert_after (bsi, stmt, GSI_NEW_STMT);
1221 mark_symbols_for_renaming (stmt);
1222 find_referenced_vars_in (stmt);
1224 /* Form the vtable address. */
1225 vtabletmp2 = create_tmp_var (TREE_TYPE (TREE_TYPE (vtabletmp)),
1227 stmt = gimple_build_assign (vtabletmp2,
1228 build1 (INDIRECT_REF,
1229 TREE_TYPE (vtabletmp2), vtabletmp));
1230 gsi_insert_after (bsi, stmt, GSI_NEW_STMT);
1231 mark_symbols_for_renaming (stmt);
1232 find_referenced_vars_in (stmt);
1234 /* Find the entry with the vcall offset. */
1235 stmt = gimple_build_assign (vtabletmp2,
1236 fold_build2_loc (input_location,
1238 TREE_TYPE (vtabletmp2),
1240 fold_convert (sizetype,
1242 gsi_insert_after (bsi, stmt, GSI_NEW_STMT);
1244 /* Get the offset itself. */
1245 vtabletmp3 = create_tmp_var (TREE_TYPE (TREE_TYPE (vtabletmp2)),
1247 stmt = gimple_build_assign (vtabletmp3,
1248 build1 (INDIRECT_REF,
1249 TREE_TYPE (vtabletmp3),
1251 gsi_insert_after (bsi, stmt, GSI_NEW_STMT);
1252 mark_symbols_for_renaming (stmt);
1253 find_referenced_vars_in (stmt);
1255 /* Cast to sizetype. */
1256 offsettmp = create_tmp_var (sizetype, "offset");
1257 stmt = gimple_build_assign (offsettmp, fold_convert (sizetype, vtabletmp3));
1258 gsi_insert_after (bsi, stmt, GSI_NEW_STMT);
1259 mark_symbols_for_renaming (stmt);
1260 find_referenced_vars_in (stmt);
1262 /* Adjust the `this' pointer. */
1263 ptr = fold_build2_loc (input_location,
1264 POINTER_PLUS_EXPR, TREE_TYPE (ptr), ptr,
1268 if (!this_adjusting)
1269 /* Adjust the pointer by the constant. */
1273 if (TREE_CODE (ptr) == VAR_DECL)
1277 ptrtmp = create_tmp_var (TREE_TYPE (ptr), "ptr");
1278 stmt = gimple_build_assign (ptrtmp, ptr);
1279 gsi_insert_after (bsi, stmt, GSI_NEW_STMT);
1280 mark_symbols_for_renaming (stmt);
1281 find_referenced_vars_in (stmt);
1283 ptr = fold_build2_loc (input_location,
1284 POINTER_PLUS_EXPR, TREE_TYPE (ptrtmp), ptrtmp,
1285 size_int (fixed_offset));
1288 /* Emit the statement and gimplify the adjustment expression. */
1289 ret = create_tmp_var (TREE_TYPE (ptr), "adjusted_this");
1290 stmt = gimple_build_assign (ret, ptr);
1291 mark_symbols_for_renaming (stmt);
1292 find_referenced_vars_in (stmt);
1293 gsi_insert_after (bsi, stmt, GSI_NEW_STMT);
1298 /* Produce assembler for thunk NODE. */
1301 assemble_thunk (struct cgraph_node *node)
1303 bool this_adjusting = node->thunk.this_adjusting;
1304 HOST_WIDE_INT fixed_offset = node->thunk.fixed_offset;
1305 HOST_WIDE_INT virtual_value = node->thunk.virtual_value;
1306 tree virtual_offset = NULL;
1307 tree alias = node->thunk.alias;
1308 tree thunk_fndecl = node->decl;
1309 tree a = DECL_ARGUMENTS (thunk_fndecl);
1311 current_function_decl = thunk_fndecl;
1314 && targetm.asm_out.can_output_mi_thunk (thunk_fndecl, fixed_offset,
1315 virtual_value, alias))
1320 DECL_RESULT (thunk_fndecl)
1321 = build_decl (DECL_SOURCE_LOCATION (thunk_fndecl),
1322 RESULT_DECL, 0, integer_type_node);
1323 fnname = IDENTIFIER_POINTER (DECL_NAME (thunk_fndecl));
1325 /* The back end expects DECL_INITIAL to contain a BLOCK, so we
1327 fn_block = make_node (BLOCK);
1328 BLOCK_VARS (fn_block) = a;
1329 DECL_INITIAL (thunk_fndecl) = fn_block;
1330 init_function_start (thunk_fndecl);
1332 assemble_start_function (thunk_fndecl, fnname);
1334 targetm.asm_out.output_mi_thunk (asm_out_file, thunk_fndecl,
1335 fixed_offset, virtual_value, alias);
1337 assemble_end_function (thunk_fndecl, fnname);
1338 init_insn_lengths ();
1339 free_after_compilation (cfun);
1341 TREE_ASM_WRITTEN (thunk_fndecl) = 1;
1346 basic_block bb, then_bb, else_bb, return_bb;
1347 gimple_stmt_iterator bsi;
1353 VEC(tree, heap) *vargs;
1358 DECL_IGNORED_P (thunk_fndecl) = 1;
1359 bitmap_obstack_initialize (NULL);
1361 if (node->thunk.virtual_offset_p)
1362 virtual_offset = size_int (virtual_value);
1364 /* Build the return declaration for the function. */
1365 restype = TREE_TYPE (TREE_TYPE (thunk_fndecl));
1366 if (DECL_RESULT (thunk_fndecl) == NULL_TREE)
1368 resdecl = build_decl (input_location, RESULT_DECL, 0, restype);
1369 DECL_ARTIFICIAL (resdecl) = 1;
1370 DECL_IGNORED_P (resdecl) = 1;
1371 DECL_RESULT (thunk_fndecl) = resdecl;
1374 resdecl = DECL_RESULT (thunk_fndecl);
1376 bb = then_bb = else_bb = return_bb = init_lowered_empty_function (thunk_fndecl);
1378 bsi = gsi_start_bb (bb);
1380 /* Build call to the function being thunked. */
1381 if (!VOID_TYPE_P (restype))
1383 if (!is_gimple_reg_type (restype))
1386 cfun->local_decls = tree_cons (NULL_TREE, restmp, cfun->local_decls);
1387 BLOCK_VARS (DECL_INITIAL (current_function_decl)) = restmp;
1390 restmp = create_tmp_var_raw (restype, "retval");
1393 for (arg = a; arg; arg = TREE_CHAIN (arg))
1395 vargs = VEC_alloc (tree, heap, nargs);
1397 VEC_quick_push (tree, vargs,
1402 VEC_quick_push (tree, vargs, a);
1403 for (i = 1, arg = TREE_CHAIN (a); i < nargs; i++, arg = TREE_CHAIN (arg))
1404 VEC_quick_push (tree, vargs, arg);
1405 call = gimple_build_call_vec (build_fold_addr_expr_loc (0, alias), vargs);
1406 VEC_free (tree, heap, vargs);
1407 gimple_call_set_cannot_inline (call, true);
1408 gimple_call_set_from_thunk (call, true);
1410 gimple_call_set_lhs (call, restmp);
1411 gsi_insert_after (&bsi, call, GSI_NEW_STMT);
1412 mark_symbols_for_renaming (call);
1413 find_referenced_vars_in (call);
1416 if (restmp && !this_adjusting)
1418 tree true_label = NULL_TREE, false_label = NULL_TREE;
1420 if (TREE_CODE (TREE_TYPE (restmp)) == POINTER_TYPE)
1423 /* If the return type is a pointer, we need to
1424 protect against NULL. We know there will be an
1425 adjustment, because that's why we're emitting a
1427 then_bb = create_basic_block (NULL, (void *) 0, bb);
1428 return_bb = create_basic_block (NULL, (void *) 0, then_bb);
1429 else_bb = create_basic_block (NULL, (void *) 0, else_bb);
1430 remove_edge (single_succ_edge (bb));
1431 true_label = gimple_block_label (then_bb);
1432 false_label = gimple_block_label (else_bb);
1433 stmt = gimple_build_cond (NE_EXPR, restmp,
1434 fold_convert (TREE_TYPE (restmp),
1436 NULL_TREE, NULL_TREE);
1437 gsi_insert_after (&bsi, stmt, GSI_NEW_STMT);
1438 make_edge (bb, then_bb, EDGE_TRUE_VALUE);
1439 make_edge (bb, else_bb, EDGE_FALSE_VALUE);
1440 make_edge (return_bb, EXIT_BLOCK_PTR, 0);
1441 make_edge (then_bb, return_bb, EDGE_FALLTHRU);
1442 make_edge (else_bb, return_bb, EDGE_FALLTHRU);
1443 bsi = gsi_last_bb (then_bb);
1446 restmp = thunk_adjust (&bsi, restmp, /*this_adjusting=*/0,
1447 fixed_offset, virtual_offset);
1451 bsi = gsi_last_bb (else_bb);
1452 stmt = gimple_build_assign (restmp, fold_convert (TREE_TYPE (restmp),
1453 integer_zero_node));
1454 gsi_insert_after (&bsi, stmt, GSI_NEW_STMT);
1455 bsi = gsi_last_bb (return_bb);
1459 gimple_call_set_tail (call, true);
1461 /* Build return value. */
1462 ret = gimple_build_return (restmp);
1463 gsi_insert_after (&bsi, ret, GSI_NEW_STMT);
1465 delete_unreachable_blocks ();
1466 update_ssa (TODO_update_ssa);
1468 cgraph_remove_same_body_alias (node);
1469 /* Since we want to emit the thunk, we explicitly mark its name as
1471 mark_decl_referenced (thunk_fndecl);
1472 cgraph_add_new_function (thunk_fndecl, true);
1473 bitmap_obstack_release (NULL);
1475 current_function_decl = NULL;
1478 /* Expand function specified by NODE. */
1481 cgraph_expand_function (struct cgraph_node *node)
1483 tree decl = node->decl;
1485 /* We ought to not compile any inline clones. */
1486 gcc_assert (!node->global.inlined_to);
1488 announce_function (decl);
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 if (node->same_body)
1501 struct cgraph_node *alias, *next;
1502 bool saved_alias = node->alias;
1503 for (alias = node->same_body;
1504 alias && alias->next; alias = alias->next)
1506 /* Walk aliases in the order they were created; it is possible that
1507 thunks reffers to the aliases made earlier. */
1508 for (; alias; alias = next)
1510 next = alias->previous;
1511 if (!alias->thunk.thunk_p)
1512 assemble_alias (alias->decl,
1513 DECL_ASSEMBLER_NAME (alias->thunk.alias));
1515 assemble_thunk (alias);
1517 node->alias = saved_alias;
1519 gcc_assert (!cgraph_preserve_function_body_p (decl));
1520 cgraph_release_function_body (node);
1521 /* Eliminate all call edges. This is important so the GIMPLE_CALL no longer
1522 points to the dead function body. */
1523 cgraph_node_remove_callees (node);
1525 cgraph_function_flags_ready = true;
1528 /* Return true when CALLER_DECL should be inlined into CALLEE_DECL. */
1531 cgraph_inline_p (struct cgraph_edge *e, cgraph_inline_failed_t *reason)
1533 *reason = e->inline_failed;
1534 return !e->inline_failed;
1539 /* Expand all functions that must be output.
1541 Attempt to topologically sort the nodes so function is output when
1542 all called functions are already assembled to allow data to be
1543 propagated across the callgraph. Use a stack to get smaller distance
1544 between a function and its callees (later we may choose to use a more
1545 sophisticated algorithm for function reordering; we will likely want
1546 to use subsections to make the output functions appear in top-down
1550 cgraph_expand_all_functions (void)
1552 struct cgraph_node *node;
1553 struct cgraph_node **order = XCNEWVEC (struct cgraph_node *, cgraph_n_nodes);
1554 int order_pos, new_order_pos = 0;
1557 order_pos = cgraph_postorder (order);
1558 gcc_assert (order_pos == cgraph_n_nodes);
1560 /* Garbage collector may remove inline clones we eliminate during
1561 optimization. So we must be sure to not reference them. */
1562 for (i = 0; i < order_pos; i++)
1563 if (order[i]->process)
1564 order[new_order_pos++] = order[i];
1566 for (i = new_order_pos - 1; i >= 0; i--)
1571 gcc_assert (node->reachable);
1573 cgraph_expand_function (node);
1576 cgraph_process_new_functions ();
1582 /* This is used to sort the node types by the cgraph order number. */
1584 enum cgraph_order_sort_kind
1586 ORDER_UNDEFINED = 0,
1592 struct cgraph_order_sort
1594 enum cgraph_order_sort_kind kind;
1597 struct cgraph_node *f;
1598 struct varpool_node *v;
1599 struct cgraph_asm_node *a;
1603 /* Output all functions, variables, and asm statements in the order
1604 according to their order fields, which is the order in which they
1605 appeared in the file. This implements -fno-toplevel-reorder. In
1606 this mode we may output functions and variables which don't really
1607 need to be output. */
1610 cgraph_output_in_order (void)
1614 struct cgraph_order_sort *nodes;
1616 struct cgraph_node *pf;
1617 struct varpool_node *pv;
1618 struct cgraph_asm_node *pa;
1621 size = max * sizeof (struct cgraph_order_sort);
1622 nodes = (struct cgraph_order_sort *) alloca (size);
1623 memset (nodes, 0, size);
1625 varpool_analyze_pending_decls ();
1627 for (pf = cgraph_nodes; pf; pf = pf->next)
1632 gcc_assert (nodes[i].kind == ORDER_UNDEFINED);
1633 nodes[i].kind = ORDER_FUNCTION;
1638 for (pv = varpool_nodes_queue; pv; pv = pv->next_needed)
1641 gcc_assert (nodes[i].kind == ORDER_UNDEFINED);
1642 nodes[i].kind = ORDER_VAR;
1646 for (pa = cgraph_asm_nodes; pa; pa = pa->next)
1649 gcc_assert (nodes[i].kind == ORDER_UNDEFINED);
1650 nodes[i].kind = ORDER_ASM;
1654 /* In toplevel reorder mode we output all statics; mark them as needed. */
1655 for (i = 0; i < max; ++i)
1657 if (nodes[i].kind == ORDER_VAR)
1659 varpool_mark_needed_node (nodes[i].u.v);
1662 varpool_empty_needed_queue ();
1664 for (i = 0; i < max; ++i)
1666 switch (nodes[i].kind)
1668 case ORDER_FUNCTION:
1669 nodes[i].u.f->process = 0;
1670 cgraph_expand_function (nodes[i].u.f);
1674 varpool_assemble_decl (nodes[i].u.v);
1678 assemble_asm (nodes[i].u.a->asm_str);
1681 case ORDER_UNDEFINED:
1689 cgraph_asm_nodes = NULL;
1692 /* Return true when function body of DECL still needs to be kept around
1693 for later re-use. */
1695 cgraph_preserve_function_body_p (tree decl)
1697 struct cgraph_node *node;
1699 gcc_assert (cgraph_global_info_ready);
1700 /* Look if there is any clone around. */
1701 node = cgraph_node (decl);
1711 current_function_decl = NULL;
1712 gimple_register_cfg_hooks ();
1713 bitmap_obstack_initialize (NULL);
1716 execute_ipa_pass_list (all_small_ipa_passes);
1718 /* If pass_all_early_optimizations was not scheduled, the state of
1719 the cgraph will not be properly updated. Update it now. */
1720 if (cgraph_state < CGRAPH_STATE_IPA_SSA)
1721 cgraph_state = CGRAPH_STATE_IPA_SSA;
1725 /* Generate coverage variables and constructors. */
1728 /* Process new functions added. */
1730 current_function_decl = NULL;
1731 cgraph_process_new_functions ();
1733 execute_ipa_summary_passes ((struct ipa_opt_pass_d *) all_regular_ipa_passes);
1735 execute_ipa_summary_passes ((struct ipa_opt_pass_d *) all_lto_gen_passes);
1738 ipa_write_summaries ();
1741 execute_ipa_pass_list (all_regular_ipa_passes);
1743 bitmap_obstack_release (NULL);
1747 /* Perform simple optimizations based on callgraph. */
1750 cgraph_optimize (void)
1752 if (errorcount || sorrycount)
1755 #ifdef ENABLE_CHECKING
1759 /* Frontend may output common variables after the unit has been finalized.
1760 It is safe to deal with them here as they are always zero initialized. */
1761 varpool_analyze_pending_decls ();
1763 timevar_push (TV_CGRAPHOPT);
1764 if (pre_ipa_mem_report)
1766 fprintf (stderr, "Memory consumption before IPA\n");
1767 dump_memory_report (false);
1770 fprintf (stderr, "Performing interprocedural optimizations\n");
1771 cgraph_state = CGRAPH_STATE_IPA;
1773 /* Don't run the IPA passes if there was any error or sorry messages. */
1774 if (errorcount == 0 && sorrycount == 0)
1777 /* Do nothing else if any IPA pass found errors. */
1778 if (errorcount || sorrycount)
1780 timevar_pop (TV_CGRAPHOPT);
1784 /* This pass remove bodies of extern inline functions we never inlined.
1785 Do this later so other IPA passes see what is really going on. */
1786 cgraph_remove_unreachable_nodes (false, dump_file);
1787 cgraph_global_info_ready = true;
1788 if (cgraph_dump_file)
1790 fprintf (cgraph_dump_file, "Optimized ");
1791 dump_cgraph (cgraph_dump_file);
1792 dump_varpool (cgraph_dump_file);
1794 if (post_ipa_mem_report)
1796 fprintf (stderr, "Memory consumption after IPA\n");
1797 dump_memory_report (false);
1799 timevar_pop (TV_CGRAPHOPT);
1801 /* Output everything. */
1802 (*debug_hooks->assembly_start) ();
1804 fprintf (stderr, "Assembling functions:\n");
1805 #ifdef ENABLE_CHECKING
1809 cgraph_materialize_all_clones ();
1810 cgraph_mark_functions_to_output ();
1812 cgraph_state = CGRAPH_STATE_EXPANSION;
1813 if (!flag_toplevel_reorder)
1814 cgraph_output_in_order ();
1817 cgraph_output_pending_asms ();
1819 cgraph_expand_all_functions ();
1820 varpool_remove_unreferenced_decls ();
1822 varpool_assemble_pending_decls ();
1824 cgraph_process_new_functions ();
1825 cgraph_state = CGRAPH_STATE_FINISHED;
1827 if (cgraph_dump_file)
1829 fprintf (cgraph_dump_file, "\nFinal ");
1830 dump_cgraph (cgraph_dump_file);
1832 #ifdef ENABLE_CHECKING
1834 /* Double check that all inline clones are gone and that all
1835 function bodies have been released from memory. */
1836 if (!(sorrycount || errorcount))
1838 struct cgraph_node *node;
1839 bool error_found = false;
1841 for (node = cgraph_nodes; node; node = node->next)
1843 && (node->global.inlined_to
1844 || gimple_has_body_p (node->decl)))
1847 dump_cgraph_node (stderr, node);
1850 internal_error ("nodes with unreleased memory found");
1856 /* Generate and emit a static constructor or destructor. WHICH must
1857 be one of 'I' (for a constructor) or 'D' (for a destructor). BODY
1858 is a STATEMENT_LIST containing GENERIC statements. PRIORITY is the
1859 initialization priority for this constructor or destructor. */
1862 cgraph_build_static_cdtor (char which, tree body, int priority)
1864 static int counter = 0;
1866 tree decl, name, resdecl;
1868 /* The priority is encoded in the constructor or destructor name.
1869 collect2 will sort the names and arrange that they are called at
1871 sprintf (which_buf, "%c_%.5d_%d", which, priority, counter++);
1872 name = get_file_function_name (which_buf);
1874 decl = build_decl (input_location, FUNCTION_DECL, name,
1875 build_function_type (void_type_node, void_list_node));
1876 current_function_decl = decl;
1878 resdecl = build_decl (input_location,
1879 RESULT_DECL, NULL_TREE, void_type_node);
1880 DECL_ARTIFICIAL (resdecl) = 1;
1881 DECL_RESULT (decl) = resdecl;
1882 DECL_CONTEXT (resdecl) = decl;
1884 allocate_struct_function (decl, false);
1886 TREE_STATIC (decl) = 1;
1887 TREE_USED (decl) = 1;
1888 DECL_ARTIFICIAL (decl) = 1;
1889 DECL_NO_INSTRUMENT_FUNCTION_ENTRY_EXIT (decl) = 1;
1890 DECL_SAVED_TREE (decl) = body;
1891 TREE_PUBLIC (decl) = ! targetm.have_ctors_dtors;
1892 DECL_UNINLINABLE (decl) = 1;
1894 DECL_INITIAL (decl) = make_node (BLOCK);
1895 TREE_USED (DECL_INITIAL (decl)) = 1;
1897 DECL_SOURCE_LOCATION (decl) = input_location;
1898 cfun->function_end_locus = input_location;
1903 DECL_STATIC_CONSTRUCTOR (decl) = 1;
1904 decl_init_priority_insert (decl, priority);
1907 DECL_STATIC_DESTRUCTOR (decl) = 1;
1908 decl_fini_priority_insert (decl, priority);
1914 gimplify_function_tree (decl);
1916 cgraph_add_new_function (decl, false);
1917 cgraph_mark_needed_node (cgraph_node (decl));
1924 cgraph_dump_file = dump_begin (TDI_cgraph, NULL);
1927 /* The edges representing the callers of the NEW_VERSION node were
1928 fixed by cgraph_function_versioning (), now the call_expr in their
1929 respective tree code should be updated to call the NEW_VERSION. */
1932 update_call_expr (struct cgraph_node *new_version)
1934 struct cgraph_edge *e;
1936 gcc_assert (new_version);
1938 /* Update the call expr on the edges to call the new version. */
1939 for (e = new_version->callers; e; e = e->next_caller)
1941 struct function *inner_function = DECL_STRUCT_FUNCTION (e->caller->decl);
1942 gimple_call_set_fndecl (e->call_stmt, new_version->decl);
1943 maybe_clean_eh_stmt_fn (inner_function, e->call_stmt);
1948 /* Create a new cgraph node which is the new version of
1949 OLD_VERSION node. REDIRECT_CALLERS holds the callers
1950 edges which should be redirected to point to
1951 NEW_VERSION. ALL the callees edges of OLD_VERSION
1952 are cloned to the new version node. Return the new
1955 static struct cgraph_node *
1956 cgraph_copy_node_for_versioning (struct cgraph_node *old_version,
1958 VEC(cgraph_edge_p,heap) *redirect_callers)
1960 struct cgraph_node *new_version;
1961 struct cgraph_edge *e, *new_e;
1962 struct cgraph_edge *next_callee;
1965 gcc_assert (old_version);
1967 new_version = cgraph_node (new_decl);
1969 new_version->analyzed = true;
1970 new_version->local = old_version->local;
1971 new_version->global = old_version->global;
1972 new_version->rtl = new_version->rtl;
1973 new_version->reachable = true;
1974 new_version->count = old_version->count;
1976 /* Clone the old node callees. Recursive calls are
1978 for (e = old_version->callees;e; e=e->next_callee)
1980 new_e = cgraph_clone_edge (e, new_version, e->call_stmt,
1981 e->lto_stmt_uid, 0, e->frequency,
1982 e->loop_nest, true);
1983 new_e->count = e->count;
1985 /* Fix recursive calls.
1986 If OLD_VERSION has a recursive call after the
1987 previous edge cloning, the new version will have an edge
1988 pointing to the old version, which is wrong;
1989 Redirect it to point to the new version. */
1990 for (e = new_version->callees ; e; e = next_callee)
1992 next_callee = e->next_callee;
1993 if (e->callee == old_version)
1994 cgraph_redirect_edge_callee (e, new_version);
1999 for (i = 0; VEC_iterate (cgraph_edge_p, redirect_callers, i, e); i++)
2001 /* Redirect calls to the old version node to point to its new
2003 cgraph_redirect_edge_callee (e, new_version);
2009 /* Perform function versioning.
2010 Function versioning includes copying of the tree and
2011 a callgraph update (creating a new cgraph node and updating
2012 its callees and callers).
2014 REDIRECT_CALLERS varray includes the edges to be redirected
2017 TREE_MAP is a mapping of tree nodes we want to replace with
2018 new ones (according to results of prior analysis).
2019 OLD_VERSION_NODE is the node that is versioned.
2020 It returns the new version's cgraph node.
2021 ARGS_TO_SKIP lists arguments to be omitted from functions
2024 struct cgraph_node *
2025 cgraph_function_versioning (struct cgraph_node *old_version_node,
2026 VEC(cgraph_edge_p,heap) *redirect_callers,
2027 VEC (ipa_replace_map_p,gc)* tree_map,
2028 bitmap args_to_skip)
2030 tree old_decl = old_version_node->decl;
2031 struct cgraph_node *new_version_node = NULL;
2034 if (!tree_versionable_function_p (old_decl))
2037 /* Make a new FUNCTION_DECL tree node for the
2040 new_decl = copy_node (old_decl);
2042 new_decl = build_function_decl_skip_args (old_decl, args_to_skip);
2044 /* Create the new version's call-graph node.
2045 and update the edges of the new node. */
2047 cgraph_copy_node_for_versioning (old_version_node, new_decl,
2050 /* Copy the OLD_VERSION_NODE function tree to the new version. */
2051 tree_function_versioning (old_decl, new_decl, tree_map, false, args_to_skip);
2053 /* Update the new version's properties.
2054 Make The new version visible only within this translation unit. Make sure
2055 that is not weak also.
2056 ??? We cannot use COMDAT linkage because there is no
2057 ABI support for this. */
2058 DECL_EXTERNAL (new_version_node->decl) = 0;
2059 DECL_COMDAT_GROUP (new_version_node->decl) = NULL_TREE;
2060 TREE_PUBLIC (new_version_node->decl) = 0;
2061 DECL_COMDAT (new_version_node->decl) = 0;
2062 DECL_WEAK (new_version_node->decl) = 0;
2063 DECL_VIRTUAL_P (new_version_node->decl) = 0;
2064 new_version_node->local.externally_visible = 0;
2065 new_version_node->local.local = 1;
2066 new_version_node->lowered = true;
2068 /* Update the call_expr on the edges to call the new version node. */
2069 update_call_expr (new_version_node);
2071 cgraph_call_function_insertion_hooks (new_version_node);
2072 return new_version_node;
2075 /* Produce separate function body for inline clones so the offline copy can be
2076 modified without affecting them. */
2077 struct cgraph_node *
2078 save_inline_function_body (struct cgraph_node *node)
2080 struct cgraph_node *first_clone, *n;
2082 gcc_assert (node == cgraph_node (node->decl));
2084 cgraph_lower_function (node);
2086 first_clone = node->clones;
2088 first_clone->decl = copy_node (node->decl);
2089 cgraph_insert_node_to_hashtable (first_clone);
2090 gcc_assert (first_clone == cgraph_node (first_clone->decl));
2091 if (first_clone->next_sibling_clone)
2093 for (n = first_clone->next_sibling_clone; n->next_sibling_clone; n = n->next_sibling_clone)
2094 n->clone_of = first_clone;
2095 n->clone_of = first_clone;
2096 n->next_sibling_clone = first_clone->clones;
2097 if (first_clone->clones)
2098 first_clone->clones->prev_sibling_clone = n;
2099 first_clone->clones = first_clone->next_sibling_clone;
2100 first_clone->next_sibling_clone->prev_sibling_clone = NULL;
2101 first_clone->next_sibling_clone = NULL;
2102 gcc_assert (!first_clone->prev_sibling_clone);
2104 first_clone->clone_of = NULL;
2105 node->clones = NULL;
2107 if (first_clone->clones)
2108 for (n = first_clone->clones; n != first_clone;)
2110 gcc_assert (n->decl == node->decl);
2111 n->decl = first_clone->decl;
2114 else if (n->next_sibling_clone)
2115 n = n->next_sibling_clone;
2118 while (n != first_clone && !n->next_sibling_clone)
2120 if (n != first_clone)
2121 n = n->next_sibling_clone;
2125 /* Copy the OLD_VERSION_NODE function tree to the new version. */
2126 tree_function_versioning (node->decl, first_clone->decl, NULL, true, NULL);
2128 DECL_EXTERNAL (first_clone->decl) = 0;
2129 DECL_COMDAT_GROUP (first_clone->decl) = NULL_TREE;
2130 TREE_PUBLIC (first_clone->decl) = 0;
2131 DECL_COMDAT (first_clone->decl) = 0;
2132 VEC_free (ipa_opt_pass, heap,
2133 first_clone->ipa_transforms_to_apply);
2134 first_clone->ipa_transforms_to_apply = NULL;
2136 #ifdef ENABLE_CHECKING
2137 verify_cgraph_node (first_clone);
2142 /* Given virtual clone, turn it into actual clone. */
2144 cgraph_materialize_clone (struct cgraph_node *node)
2146 bitmap_obstack_initialize (NULL);
2147 /* Copy the OLD_VERSION_NODE function tree to the new version. */
2148 tree_function_versioning (node->clone_of->decl, node->decl,
2149 node->clone.tree_map, true,
2150 node->clone.args_to_skip);
2151 if (cgraph_dump_file)
2153 dump_function_to_file (node->clone_of->decl, cgraph_dump_file, dump_flags);
2154 dump_function_to_file (node->decl, cgraph_dump_file, dump_flags);
2157 /* Function is no longer clone. */
2158 if (node->next_sibling_clone)
2159 node->next_sibling_clone->prev_sibling_clone = node->prev_sibling_clone;
2160 if (node->prev_sibling_clone)
2161 node->prev_sibling_clone->next_sibling_clone = node->next_sibling_clone;
2163 node->clone_of->clones = node->next_sibling_clone;
2164 node->next_sibling_clone = NULL;
2165 node->prev_sibling_clone = NULL;
2166 if (!node->clone_of->analyzed && !node->clone_of->clones)
2167 cgraph_remove_node (node->clone_of);
2168 node->clone_of = NULL;
2169 bitmap_obstack_release (NULL);
2172 /* Once all functions from compilation unit are in memory, produce all clones
2173 and update all calls.
2174 We might also do this on demand if we don't want to bring all functions to
2175 memory prior compilation, but current WHOPR implementation does that and it is
2176 is bit easier to keep everything right in this order. */
2178 cgraph_materialize_all_clones (void)
2180 struct cgraph_node *node;
2181 bool stabilized = false;
2183 if (cgraph_dump_file)
2184 fprintf (cgraph_dump_file, "Materializing clones\n");
2185 #ifdef ENABLE_CHECKING
2189 /* We can also do topological order, but number of iterations should be
2190 bounded by number of IPA passes since single IPA pass is probably not
2191 going to create clones of clones it created itself. */
2195 for (node = cgraph_nodes; node; node = node->next)
2197 if (node->clone_of && node->decl != node->clone_of->decl
2198 && !gimple_has_body_p (node->decl))
2200 if (gimple_has_body_p (node->clone_of->decl))
2202 if (cgraph_dump_file)
2204 fprintf (cgraph_dump_file, "clonning %s to %s\n",
2205 cgraph_node_name (node->clone_of),
2206 cgraph_node_name (node));
2207 if (node->clone.tree_map)
2210 fprintf (cgraph_dump_file, " replace map: ");
2211 for (i = 0; i < VEC_length (ipa_replace_map_p,
2212 node->clone.tree_map);
2215 struct ipa_replace_map *replace_info;
2216 replace_info = VEC_index (ipa_replace_map_p,
2217 node->clone.tree_map,
2219 print_generic_expr (cgraph_dump_file, replace_info->old_tree, 0);
2220 fprintf (cgraph_dump_file, " -> ");
2221 print_generic_expr (cgraph_dump_file, replace_info->new_tree, 0);
2222 fprintf (cgraph_dump_file, "%s%s;",
2223 replace_info->replace_p ? "(replace)":"",
2224 replace_info->ref_p ? "(ref)":"");
2226 fprintf (cgraph_dump_file, "\n");
2228 if (node->clone.args_to_skip)
2230 fprintf (cgraph_dump_file, " args_to_skip: ");
2231 dump_bitmap (cgraph_dump_file, node->clone.args_to_skip);
2233 if (node->clone.args_to_skip)
2235 fprintf (cgraph_dump_file, " combined_args_to_skip:");
2236 dump_bitmap (cgraph_dump_file, node->clone.combined_args_to_skip);
2239 cgraph_materialize_clone (node);
2246 if (cgraph_dump_file)
2247 fprintf (cgraph_dump_file, "Updating call sites\n");
2248 for (node = cgraph_nodes; node; node = node->next)
2249 if (node->analyzed && gimple_has_body_p (node->decl)
2250 && (!node->clone_of || node->clone_of->decl != node->decl))
2252 struct cgraph_edge *e;
2254 current_function_decl = node->decl;
2255 push_cfun (DECL_STRUCT_FUNCTION (node->decl));
2256 for (e = node->callees; e; e = e->next_callee)
2258 tree decl = gimple_call_fndecl (e->call_stmt);
2259 /* When function gets inlined, indirect inlining might've invented
2260 new edge for orginally indirect stmt. Since we are not
2261 preserving clones in the original form, we must not update here
2262 since other inline clones don't need to contain call to the same
2263 call. Inliner will do the substitution for us later. */
2264 if (decl && decl != e->callee->decl)
2267 gimple_stmt_iterator gsi;
2269 if (e->callee->same_body)
2271 struct cgraph_node *alias;
2273 for (alias = e->callee->same_body;
2275 alias = alias->next)
2276 if (decl == alias->decl)
2278 /* Don't update call from same body alias to the real
2284 if (cgraph_dump_file)
2286 fprintf (cgraph_dump_file, "updating call of %s in %s:",
2287 cgraph_node_name (node),
2288 cgraph_node_name (e->callee));
2289 print_gimple_stmt (cgraph_dump_file, e->call_stmt, 0, dump_flags);
2292 if (e->callee->clone.combined_args_to_skip)
2293 new_stmt = gimple_call_copy_skip_args (e->call_stmt,
2294 e->callee->clone.combined_args_to_skip);
2296 new_stmt = e->call_stmt;
2297 if (gimple_vdef (new_stmt)
2298 && TREE_CODE (gimple_vdef (new_stmt)) == SSA_NAME)
2299 SSA_NAME_DEF_STMT (gimple_vdef (new_stmt)) = new_stmt;
2300 gimple_call_set_fndecl (new_stmt, e->callee->decl);
2302 gsi = gsi_for_stmt (e->call_stmt);
2303 gsi_replace (&gsi, new_stmt, true);
2305 /* Update EH information too, just in case. */
2306 maybe_clean_or_replace_eh_stmt (e->call_stmt, new_stmt);
2308 cgraph_set_call_stmt_including_clones (node, e->call_stmt, new_stmt);
2310 if (cgraph_dump_file)
2312 fprintf (cgraph_dump_file, " updated to:");
2313 print_gimple_stmt (cgraph_dump_file, e->call_stmt, 0, dump_flags);
2318 current_function_decl = NULL;
2319 #ifdef ENABLE_CHECKING
2320 verify_cgraph_node (node);
2323 #ifdef ENABLE_CHECKING
2326 cgraph_remove_unreachable_nodes (false, cgraph_dump_file);
2329 #include "gt-cgraphunit.h"