1 /* Callgraph based interprocedural optimizations.
2 Copyright (C) 2003, 2004, 2005, 2006, 2007, 2008
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"
129 #include "c-common.h"
131 #include "function.h"
132 #include "ipa-prop.h"
133 #include "tree-gimple.h"
134 #include "tree-pass.h"
137 static void cgraph_expand_all_functions (void);
138 static void cgraph_mark_functions_to_output (void);
139 static void cgraph_expand_function (struct cgraph_node *);
140 static void cgraph_output_pending_asms (void);
142 static FILE *cgraph_dump_file;
144 /* A vector of FUNCTION_DECLs declared as static constructors. */
145 static GTY (()) VEC(tree, gc) *static_ctors;
146 /* A vector of FUNCTION_DECLs declared as static destructors. */
147 static GTY (()) VEC(tree, gc) *static_dtors;
149 /* When target does not have ctors and dtors, we call all constructor
150 and destructor by special initialization/destruction function
151 recognized by collect2.
153 When we are going to build this function, collect all constructors and
154 destructors and turn them into normal functions. */
157 record_cdtor_fn (tree fndecl)
159 struct cgraph_node *node;
160 if (targetm.have_ctors_dtors
161 || (!DECL_STATIC_CONSTRUCTOR (fndecl)
162 && !DECL_STATIC_DESTRUCTOR (fndecl)))
165 if (DECL_STATIC_CONSTRUCTOR (fndecl))
167 VEC_safe_push (tree, gc, static_ctors, fndecl);
168 DECL_STATIC_CONSTRUCTOR (fndecl) = 0;
170 if (DECL_STATIC_DESTRUCTOR (fndecl))
172 VEC_safe_push (tree, gc, static_dtors, fndecl);
173 DECL_STATIC_DESTRUCTOR (fndecl) = 0;
175 DECL_INLINE (fndecl) = 1;
176 node = cgraph_node (fndecl);
177 node->local.disregard_inline_limits = 1;
178 cgraph_mark_reachable_node (node);
181 /* Define global constructors/destructor functions for the CDTORS, of
182 which they are LEN. The CDTORS are sorted by initialization
183 priority. If CTOR_P is true, these are constructors; otherwise,
184 they are destructors. */
187 build_cdtor (bool ctor_p, tree *cdtors, size_t len)
196 priority_type priority;
200 /* Find the next batch of constructors/destructors with the same
201 initialization priority. */
206 p = ctor_p ? DECL_INIT_PRIORITY (fn) : DECL_FINI_PRIORITY (fn);
209 else if (p != priority)
211 append_to_statement_list (build_function_call_expr (fn, 0),
216 gcc_assert (body != NULL_TREE);
217 /* Generate a function to call all the function of like
219 cgraph_build_static_cdtor (ctor_p ? 'I' : 'D', body, priority);
223 /* Comparison function for qsort. P1 and P2 are actually of type
224 "tree *" and point to static constructors. DECL_INIT_PRIORITY is
225 used to determine the sort order. */
228 compare_ctor (const void *p1, const void *p2)
235 f1 = *(const tree *)p1;
236 f2 = *(const tree *)p2;
237 priority1 = DECL_INIT_PRIORITY (f1);
238 priority2 = DECL_INIT_PRIORITY (f2);
240 if (priority1 < priority2)
242 else if (priority1 > priority2)
245 /* Ensure a stable sort. */
246 return (const tree *)p1 - (const tree *)p2;
249 /* Comparison function for qsort. P1 and P2 are actually of type
250 "tree *" and point to static destructors. DECL_FINI_PRIORITY is
251 used to determine the sort order. */
254 compare_dtor (const void *p1, const void *p2)
261 f1 = *(const tree *)p1;
262 f2 = *(const tree *)p2;
263 priority1 = DECL_FINI_PRIORITY (f1);
264 priority2 = DECL_FINI_PRIORITY (f2);
266 if (priority1 < priority2)
268 else if (priority1 > priority2)
271 /* Ensure a stable sort. */
272 return (const tree *)p1 - (const tree *)p2;
275 /* Generate functions to call static constructors and destructors
276 for targets that do not support .ctors/.dtors sections. These
277 functions have magic names which are detected by collect2. */
280 cgraph_build_cdtor_fns (void)
282 if (!VEC_empty (tree, static_ctors))
284 gcc_assert (!targetm.have_ctors_dtors);
285 qsort (VEC_address (tree, static_ctors),
286 VEC_length (tree, static_ctors),
289 build_cdtor (/*ctor_p=*/true,
290 VEC_address (tree, static_ctors),
291 VEC_length (tree, static_ctors));
292 VEC_truncate (tree, static_ctors, 0);
295 if (!VEC_empty (tree, static_dtors))
297 gcc_assert (!targetm.have_ctors_dtors);
298 qsort (VEC_address (tree, static_dtors),
299 VEC_length (tree, static_dtors),
302 build_cdtor (/*ctor_p=*/false,
303 VEC_address (tree, static_dtors),
304 VEC_length (tree, static_dtors));
305 VEC_truncate (tree, static_dtors, 0);
309 /* Determine if function DECL is needed. That is, visible to something
310 either outside this translation unit, something magic in the system
314 decide_is_function_needed (struct cgraph_node *node, tree decl)
316 if (MAIN_NAME_P (DECL_NAME (decl))
317 && TREE_PUBLIC (decl))
319 node->local.externally_visible = true;
323 /* If the user told us it is used, then it must be so. */
324 if (node->local.externally_visible)
327 /* ??? If the assembler name is set by hand, it is possible to assemble
328 the name later after finalizing the function and the fact is noticed
329 in assemble_name then. This is arguably a bug. */
330 if (DECL_ASSEMBLER_NAME_SET_P (decl)
331 && TREE_SYMBOL_REFERENCED (DECL_ASSEMBLER_NAME (decl)))
334 /* With -fkeep-inline-functions we are keeping all inline functions except
335 for extern inline ones. */
336 if (flag_keep_inline_functions
337 && DECL_DECLARED_INLINE_P (decl)
338 && !DECL_EXTERNAL (decl)
339 && !lookup_attribute ("always_inline", DECL_ATTRIBUTES (decl)))
342 /* If we decided it was needed before, but at the time we didn't have
343 the body of the function available, then it's still needed. We have
344 to go back and re-check its dependencies now. */
348 /* Externally visible functions must be output. The exception is
349 COMDAT functions that must be output only when they are needed.
351 When not optimizing, also output the static functions. (see
352 PR24561), but don't do so for always_inline functions, functions
353 declared inline and nested functions. These was optimized out
354 in the original implementation and it is unclear whether we want
355 to change the behavior here. */
356 if (((TREE_PUBLIC (decl)
357 || (!optimize && !node->local.disregard_inline_limits
358 && !DECL_DECLARED_INLINE_P (decl)
360 && !flag_whole_program)
361 && !DECL_COMDAT (decl) && !DECL_EXTERNAL (decl))
364 /* Constructors and destructors are reachable from the runtime by
366 if (DECL_STATIC_CONSTRUCTOR (decl) || DECL_STATIC_DESTRUCTOR (decl))
372 /* Process CGRAPH_NEW_FUNCTIONS and perform actions necessary to add these
373 functions into callgraph in a way so they look like ordinary reachable
374 functions inserted into callgraph already at construction time. */
377 cgraph_process_new_functions (void)
381 struct cgraph_node *node;
383 /* Note that this queue may grow as its being processed, as the new
384 functions may generate new ones. */
385 while (cgraph_new_nodes)
387 node = cgraph_new_nodes;
389 cgraph_new_nodes = cgraph_new_nodes->next_needed;
390 switch (cgraph_state)
392 case CGRAPH_STATE_CONSTRUCTION:
393 /* At construction time we just need to finalize function and move
394 it into reachable functions list. */
396 node->next_needed = NULL;
397 cgraph_finalize_function (fndecl, false);
398 cgraph_mark_reachable_node (node);
402 case CGRAPH_STATE_IPA:
403 case CGRAPH_STATE_IPA_SSA:
404 /* When IPA optimization already started, do all essential
405 transformations that has been already performed on the whole
406 cgraph but not on this function. */
408 tree_register_cfg_hooks ();
410 cgraph_analyze_function (node);
411 push_cfun (DECL_STRUCT_FUNCTION (fndecl));
412 current_function_decl = fndecl;
413 compute_inline_parameters (node);
414 if ((cgraph_state == CGRAPH_STATE_IPA_SSA
415 && !gimple_in_ssa_p (DECL_STRUCT_FUNCTION (fndecl)))
416 /* When not optimizing, be sure we run early local passes anyway
419 execute_pass_list (pass_early_local_passes.pass.sub);
420 free_dominance_info (CDI_POST_DOMINATORS);
421 free_dominance_info (CDI_DOMINATORS);
423 current_function_decl = NULL;
426 case CGRAPH_STATE_EXPANSION:
427 /* Functions created during expansion shall be compiled
430 cgraph_expand_function (node);
441 /* As an GCC extension we allow redefinition of the function. The
442 semantics when both copies of bodies differ is not well defined.
443 We replace the old body with new body so in unit at a time mode
444 we always use new body, while in normal mode we may end up with
445 old body inlined into some functions and new body expanded and
448 ??? It may make more sense to use one body for inlining and other
449 body for expanding the function but this is difficult to do. */
452 cgraph_reset_node (struct cgraph_node *node)
454 /* If node->output is set, then we have already begun whole-unit analysis.
455 This is *not* testing for whether we've already emitted the function.
456 That case can be sort-of legitimately seen with real function redefinition
457 errors. I would argue that the front end should never present us with
458 such a case, but don't enforce that for now. */
459 gcc_assert (!node->output);
461 /* Reset our data structures so we can analyze the function again. */
462 memset (&node->local, 0, sizeof (node->local));
463 memset (&node->global, 0, sizeof (node->global));
464 memset (&node->rtl, 0, sizeof (node->rtl));
465 node->analyzed = false;
466 node->local.redefined_extern_inline = true;
467 node->local.finalized = false;
469 cgraph_node_remove_callees (node);
471 /* We may need to re-queue the node for assembling in case
472 we already proceeded it and ignored as not needed or got
473 a re-declaration in IMA mode. */
476 struct cgraph_node *n;
478 for (n = cgraph_nodes_queue; n; n = n->next_needed)
487 cgraph_lower_function (struct cgraph_node *node)
491 tree_lowering_passes (node->decl);
492 node->lowered = true;
495 /* DECL has been parsed. Take it, queue it, compile it at the whim of the
496 logic in effect. If NESTED is true, then our caller cannot stand to have
497 the garbage collector run at the moment. We would need to either create
498 a new GC context, or just not compile right now. */
501 cgraph_finalize_function (tree decl, bool nested)
503 struct cgraph_node *node = cgraph_node (decl);
505 if (node->local.finalized)
506 cgraph_reset_node (node);
508 node->pid = cgraph_max_pid ++;
509 notice_global_symbol (decl);
510 node->local.finalized = true;
511 node->lowered = DECL_STRUCT_FUNCTION (decl)->cfg != NULL;
512 record_cdtor_fn (node->decl);
514 lower_nested_functions (decl);
515 gcc_assert (!node->nested);
517 if (decide_is_function_needed (node, decl))
518 cgraph_mark_needed_node (node);
520 /* Since we reclaim unreachable nodes at the end of every language
521 level unit, we need to be conservative about possible entry points
523 if ((TREE_PUBLIC (decl) && !DECL_COMDAT (decl) && !DECL_EXTERNAL (decl)))
524 cgraph_mark_reachable_node (node);
526 /* If we've not yet emitted decl, tell the debug info about it. */
527 if (!TREE_ASM_WRITTEN (decl))
528 (*debug_hooks->deferred_inline_function) (decl);
530 /* Possibly warn about unused parameters. */
531 if (warn_unused_parameter)
532 do_warn_unused_parameter (decl);
538 /* C99 extern inline keywords allow changing of declaration after function
539 has been finalized. We need to re-decide if we want to mark the function as
543 cgraph_mark_if_needed (tree decl)
545 struct cgraph_node *node = cgraph_node (decl);
546 if (node->local.finalized && decide_is_function_needed (node, decl))
547 cgraph_mark_needed_node (node);
550 /* Verify cgraph nodes of given cgraph node. */
552 verify_cgraph_node (struct cgraph_node *node)
554 struct cgraph_edge *e;
555 struct cgraph_node *main_clone;
556 struct function *this_cfun = DECL_STRUCT_FUNCTION (node->decl);
557 struct function *saved_cfun = cfun;
558 basic_block this_block;
559 block_stmt_iterator bsi;
560 bool error_found = false;
562 if (errorcount || sorrycount)
565 timevar_push (TV_CGRAPH_VERIFY);
566 /* debug_generic_stmt needs correct cfun */
567 set_cfun (this_cfun);
568 for (e = node->callees; e; e = e->next_callee)
571 error ("aux field set for edge %s->%s",
572 cgraph_node_name (e->caller), cgraph_node_name (e->callee));
577 error ("Execution count is negative");
580 for (e = node->callers; e; e = e->next_caller)
584 error ("caller edge count is negative");
587 if (e->frequency < 0)
589 error ("caller edge frequency is negative");
592 if (e->frequency > CGRAPH_FREQ_MAX)
594 error ("caller edge frequency is too large");
597 if (!e->inline_failed)
599 if (node->global.inlined_to
600 != (e->caller->global.inlined_to
601 ? e->caller->global.inlined_to : e->caller))
603 error ("inlined_to pointer is wrong");
606 if (node->callers->next_caller)
608 error ("multiple inline callers");
613 if (node->global.inlined_to)
615 error ("inlined_to pointer set for noninline callers");
619 if (!node->callers && node->global.inlined_to)
621 error ("inlined_to pointer is set but no predecessors found");
624 if (node->global.inlined_to == node)
626 error ("inlined_to pointer refers to itself");
630 for (main_clone = cgraph_node (node->decl); main_clone;
631 main_clone = main_clone->next_clone)
632 if (main_clone == node)
634 if (!cgraph_node (node->decl))
636 error ("node not found in cgraph_hash");
641 && DECL_SAVED_TREE (node->decl) && !TREE_ASM_WRITTEN (node->decl)
642 && (!DECL_EXTERNAL (node->decl) || node->global.inlined_to))
646 /* The nodes we're interested in are never shared, so walk
647 the tree ignoring duplicates. */
648 struct pointer_set_t *visited_nodes = pointer_set_create ();
649 /* Reach the trees by walking over the CFG, and note the
650 enclosing basic-blocks in the call edges. */
651 FOR_EACH_BB_FN (this_block, this_cfun)
652 for (bsi = bsi_start (this_block); !bsi_end_p (bsi); bsi_next (&bsi))
654 tree stmt = bsi_stmt (bsi);
655 tree call = get_call_expr_in (stmt);
657 if (call && (decl = get_callee_fndecl (call)))
659 struct cgraph_edge *e = cgraph_edge (node, stmt);
664 error ("shared call_stmt:");
665 debug_generic_stmt (stmt);
668 if (e->callee->decl != cgraph_node (decl)->decl
671 error ("edge points to wrong declaration:");
672 debug_tree (e->callee->decl);
673 fprintf (stderr," Instead of:");
680 error ("missing callgraph edge for call stmt:");
681 debug_generic_stmt (stmt);
686 pointer_set_destroy (visited_nodes);
689 /* No CFG available?! */
692 for (e = node->callees; e; e = e->next_callee)
694 if (!e->aux && !e->indirect_call)
696 error ("edge %s->%s has no corresponding call_stmt",
697 cgraph_node_name (e->caller),
698 cgraph_node_name (e->callee));
699 debug_generic_stmt (e->call_stmt);
707 dump_cgraph_node (stderr, node);
708 internal_error ("verify_cgraph_node failed");
710 set_cfun (saved_cfun);
711 timevar_pop (TV_CGRAPH_VERIFY);
714 /* Verify whole cgraph structure. */
718 struct cgraph_node *node;
720 if (sorrycount || errorcount)
723 for (node = cgraph_nodes; node; node = node->next)
724 verify_cgraph_node (node);
727 /* Output all asm statements we have stored up to be output. */
730 cgraph_output_pending_asms (void)
732 struct cgraph_asm_node *can;
734 if (errorcount || sorrycount)
737 for (can = cgraph_asm_nodes; can; can = can->next)
738 assemble_asm (can->asm_str);
739 cgraph_asm_nodes = NULL;
742 /* Analyze the function scheduled to be output. */
744 cgraph_analyze_function (struct cgraph_node *node)
746 tree decl = node->decl;
748 current_function_decl = decl;
749 push_cfun (DECL_STRUCT_FUNCTION (decl));
750 cgraph_lower_function (node);
751 node->analyzed = true;
754 current_function_decl = NULL;
757 /* Look for externally_visible and used attributes and mark cgraph nodes
760 We cannot mark the nodes at the point the attributes are processed (in
761 handle_*_attribute) because the copy of the declarations available at that
762 point may not be canonical. For example, in:
765 void f() __attribute__((used));
767 the declaration we see in handle_used_attribute will be the second
768 declaration -- but the front end will subsequently merge that declaration
769 with the original declaration and discard the second declaration.
771 Furthermore, we can't mark these nodes in cgraph_finalize_function because:
774 void f() __attribute__((externally_visible));
778 So, we walk the nodes at the end of the translation unit, applying the
779 attributes at that point. */
782 process_function_and_variable_attributes (struct cgraph_node *first,
783 struct varpool_node *first_var)
785 struct cgraph_node *node;
786 struct varpool_node *vnode;
788 for (node = cgraph_nodes; node != first; node = node->next)
790 tree decl = node->decl;
791 if (lookup_attribute ("used", DECL_ATTRIBUTES (decl)))
793 mark_decl_referenced (decl);
794 if (node->local.finalized)
795 cgraph_mark_needed_node (node);
797 if (lookup_attribute ("externally_visible", DECL_ATTRIBUTES (decl)))
799 if (! TREE_PUBLIC (node->decl))
800 warning (OPT_Wattributes,
801 "%J%<externally_visible%> attribute have effect only on public objects",
805 if (node->local.finalized)
806 cgraph_mark_needed_node (node);
807 node->local.externally_visible = true;
811 for (vnode = varpool_nodes; vnode != first_var; vnode = vnode->next)
813 tree decl = vnode->decl;
814 if (lookup_attribute ("used", DECL_ATTRIBUTES (decl)))
816 mark_decl_referenced (decl);
817 if (vnode->finalized)
818 varpool_mark_needed_node (vnode);
820 if (lookup_attribute ("externally_visible", DECL_ATTRIBUTES (decl)))
822 if (! TREE_PUBLIC (vnode->decl))
823 warning (OPT_Wattributes,
824 "%J%<externally_visible%> attribute have effect only on public objects",
828 if (vnode->finalized)
829 varpool_mark_needed_node (vnode);
830 vnode->externally_visible = true;
836 /* Process CGRAPH_NODES_NEEDED queue, analyze each function (and transitively
837 each reachable functions) and build cgraph.
838 The function can be called multiple times after inserting new nodes
839 into beginning of queue. Just the new part of queue is re-scanned then. */
842 cgraph_analyze_functions (void)
844 /* Keep track of already processed nodes when called multiple times for
845 intermodule optimization. */
846 static struct cgraph_node *first_analyzed;
847 struct cgraph_node *first_processed = first_analyzed;
848 static struct varpool_node *first_analyzed_var;
849 struct cgraph_node *node, *next;
851 process_function_and_variable_attributes (first_processed,
853 first_processed = cgraph_nodes;
854 first_analyzed_var = varpool_nodes;
855 varpool_analyze_pending_decls ();
856 if (cgraph_dump_file)
858 fprintf (cgraph_dump_file, "Initial entry points:");
859 for (node = cgraph_nodes; node != first_analyzed; node = node->next)
860 if (node->needed && DECL_SAVED_TREE (node->decl))
861 fprintf (cgraph_dump_file, " %s", cgraph_node_name (node));
862 fprintf (cgraph_dump_file, "\n");
864 cgraph_process_new_functions ();
866 /* Propagate reachability flag and lower representation of all reachable
867 functions. In the future, lowering will introduce new functions and
868 new entry points on the way (by template instantiation and virtual
869 method table generation for instance). */
870 while (cgraph_nodes_queue)
872 struct cgraph_edge *edge;
873 tree decl = cgraph_nodes_queue->decl;
875 node = cgraph_nodes_queue;
876 cgraph_nodes_queue = cgraph_nodes_queue->next_needed;
877 node->next_needed = NULL;
879 /* ??? It is possible to create extern inline function and later using
880 weak alias attribute to kill its body. See
881 gcc.c-torture/compile/20011119-1.c */
882 if (!DECL_SAVED_TREE (decl))
884 cgraph_reset_node (node);
888 gcc_assert (!node->analyzed && node->reachable);
889 gcc_assert (DECL_SAVED_TREE (decl));
891 cgraph_analyze_function (node);
893 for (edge = node->callees; edge; edge = edge->next_callee)
894 if (!edge->callee->reachable)
895 cgraph_mark_reachable_node (edge->callee);
897 /* We finalize local static variables during constructing callgraph
898 edges. Process their attributes too. */
899 process_function_and_variable_attributes (first_processed,
901 first_processed = cgraph_nodes;
902 first_analyzed_var = varpool_nodes;
903 varpool_analyze_pending_decls ();
904 cgraph_process_new_functions ();
907 /* Collect entry points to the unit. */
908 if (cgraph_dump_file)
910 fprintf (cgraph_dump_file, "Unit entry points:");
911 for (node = cgraph_nodes; node != first_analyzed; node = node->next)
912 if (node->needed && DECL_SAVED_TREE (node->decl))
913 fprintf (cgraph_dump_file, " %s", cgraph_node_name (node));
914 fprintf (cgraph_dump_file, "\n\nInitial ");
915 dump_cgraph (cgraph_dump_file);
918 if (cgraph_dump_file)
919 fprintf (cgraph_dump_file, "\nReclaiming functions:");
921 for (node = cgraph_nodes; node != first_analyzed; node = next)
923 tree decl = node->decl;
926 if (node->local.finalized && !DECL_SAVED_TREE (decl))
927 cgraph_reset_node (node);
929 if (!node->reachable && DECL_SAVED_TREE (decl))
931 if (cgraph_dump_file)
932 fprintf (cgraph_dump_file, " %s", cgraph_node_name (node));
933 cgraph_remove_node (node);
937 node->next_needed = NULL;
938 gcc_assert (!node->local.finalized || DECL_SAVED_TREE (decl));
939 gcc_assert (node->analyzed == node->local.finalized);
941 if (cgraph_dump_file)
943 fprintf (cgraph_dump_file, "\n\nReclaimed ");
944 dump_cgraph (cgraph_dump_file);
946 first_analyzed = cgraph_nodes;
950 /* Analyze the whole compilation unit once it is parsed completely. */
953 cgraph_finalize_compilation_unit (void)
955 if (errorcount || sorrycount)
962 fprintf (stderr, "\nAnalyzing compilation unit\n");
966 timevar_push (TV_CGRAPH);
967 cgraph_analyze_functions ();
968 timevar_pop (TV_CGRAPH);
970 /* Figure out what functions we want to assemble. */
973 cgraph_mark_functions_to_output (void)
975 struct cgraph_node *node;
977 for (node = cgraph_nodes; node; node = node->next)
979 tree decl = node->decl;
980 struct cgraph_edge *e;
982 gcc_assert (!node->output);
984 for (e = node->callers; e; e = e->next_caller)
985 if (e->inline_failed)
988 /* We need to output all local functions that are used and not
989 always inlined, as well as those that are reachable from
990 outside the current compilation unit. */
991 if (DECL_SAVED_TREE (decl)
992 && !node->global.inlined_to
994 || (e && node->reachable))
995 && !TREE_ASM_WRITTEN (decl)
996 && !DECL_EXTERNAL (decl))
1000 /* We should've reclaimed all functions that are not needed. */
1001 #ifdef ENABLE_CHECKING
1002 if (!node->global.inlined_to && DECL_SAVED_TREE (decl)
1003 && !DECL_EXTERNAL (decl))
1005 dump_cgraph_node (stderr, node);
1006 internal_error ("failed to reclaim unneeded function");
1009 gcc_assert (node->global.inlined_to || !DECL_SAVED_TREE (decl)
1010 || DECL_EXTERNAL (decl));
1017 /* Expand function specified by NODE. */
1020 cgraph_expand_function (struct cgraph_node *node)
1022 tree decl = node->decl;
1024 /* We ought to not compile any inline clones. */
1025 gcc_assert (!node->global.inlined_to);
1027 announce_function (decl);
1029 gcc_assert (node->lowered);
1031 /* Generate RTL for the body of DECL. */
1032 if (lang_hooks.callgraph.emit_associated_thunks)
1033 lang_hooks.callgraph.emit_associated_thunks (decl);
1034 tree_rest_of_compilation (decl);
1036 /* Make sure that BE didn't give up on compiling. */
1037 /* ??? Can happen with nested function of extern inline. */
1038 gcc_assert (TREE_ASM_WRITTEN (decl));
1040 current_function_decl = NULL;
1041 if (!cgraph_preserve_function_body_p (decl))
1043 cgraph_release_function_body (node);
1044 /* Eliminate all call edges. This is important so the call_expr no longer
1045 points to the dead function body. */
1046 cgraph_node_remove_callees (node);
1049 cgraph_function_flags_ready = true;
1052 /* Return true when CALLER_DECL should be inlined into CALLEE_DECL. */
1055 cgraph_inline_p (struct cgraph_edge *e, const char **reason)
1057 *reason = e->inline_failed;
1058 return !e->inline_failed;
1063 /* Expand all functions that must be output.
1065 Attempt to topologically sort the nodes so function is output when
1066 all called functions are already assembled to allow data to be
1067 propagated across the callgraph. Use a stack to get smaller distance
1068 between a function and its callees (later we may choose to use a more
1069 sophisticated algorithm for function reordering; we will likely want
1070 to use subsections to make the output functions appear in top-down
1074 cgraph_expand_all_functions (void)
1076 struct cgraph_node *node;
1077 struct cgraph_node **order = XCNEWVEC (struct cgraph_node *, cgraph_n_nodes);
1078 int order_pos, new_order_pos = 0;
1081 order_pos = cgraph_postorder (order);
1082 gcc_assert (order_pos == cgraph_n_nodes);
1084 /* Garbage collector may remove inline clones we eliminate during
1085 optimization. So we must be sure to not reference them. */
1086 for (i = 0; i < order_pos; i++)
1087 if (order[i]->output)
1088 order[new_order_pos++] = order[i];
1090 for (i = new_order_pos - 1; i >= 0; i--)
1095 gcc_assert (node->reachable);
1097 cgraph_expand_function (node);
1100 cgraph_process_new_functions ();
1106 /* This is used to sort the node types by the cgraph order number. */
1108 struct cgraph_order_sort
1110 enum { ORDER_UNDEFINED = 0, ORDER_FUNCTION, ORDER_VAR, ORDER_ASM } kind;
1113 struct cgraph_node *f;
1114 struct varpool_node *v;
1115 struct cgraph_asm_node *a;
1119 /* Output all functions, variables, and asm statements in the order
1120 according to their order fields, which is the order in which they
1121 appeared in the file. This implements -fno-toplevel-reorder. In
1122 this mode we may output functions and variables which don't really
1123 need to be output. */
1126 cgraph_output_in_order (void)
1130 struct cgraph_order_sort *nodes;
1132 struct cgraph_node *pf;
1133 struct varpool_node *pv;
1134 struct cgraph_asm_node *pa;
1137 size = max * sizeof (struct cgraph_order_sort);
1138 nodes = (struct cgraph_order_sort *) alloca (size);
1139 memset (nodes, 0, size);
1141 varpool_analyze_pending_decls ();
1143 for (pf = cgraph_nodes; pf; pf = pf->next)
1148 gcc_assert (nodes[i].kind == ORDER_UNDEFINED);
1149 nodes[i].kind = ORDER_FUNCTION;
1154 for (pv = varpool_nodes_queue; pv; pv = pv->next_needed)
1157 gcc_assert (nodes[i].kind == ORDER_UNDEFINED);
1158 nodes[i].kind = ORDER_VAR;
1162 for (pa = cgraph_asm_nodes; pa; pa = pa->next)
1165 gcc_assert (nodes[i].kind == ORDER_UNDEFINED);
1166 nodes[i].kind = ORDER_ASM;
1170 /* In toplevel reorder mode we output all statics; mark them as needed. */
1171 for (i = 0; i < max; ++i)
1173 if (nodes[i].kind == ORDER_VAR)
1175 varpool_mark_needed_node (nodes[i].u.v);
1178 varpool_empty_needed_queue ();
1180 for (i = 0; i < max; ++i)
1182 switch (nodes[i].kind)
1184 case ORDER_FUNCTION:
1185 nodes[i].u.f->output = 0;
1186 cgraph_expand_function (nodes[i].u.f);
1190 varpool_assemble_decl (nodes[i].u.v);
1194 assemble_asm (nodes[i].u.a->asm_str);
1197 case ORDER_UNDEFINED:
1205 cgraph_asm_nodes = NULL;
1208 /* Return true when function body of DECL still needs to be kept around
1209 for later re-use. */
1211 cgraph_preserve_function_body_p (tree decl)
1213 struct cgraph_node *node;
1214 if (!cgraph_global_info_ready)
1215 return (flag_really_no_inline
1216 ? DECL_DISREGARD_INLINE_LIMITS (decl)
1217 : DECL_INLINE (decl));
1218 /* Look if there is any clone around. */
1219 for (node = cgraph_node (decl); node; node = node->next_clone)
1220 if (node->global.inlined_to)
1229 current_function_decl = NULL;
1230 tree_register_cfg_hooks ();
1231 bitmap_obstack_initialize (NULL);
1232 execute_ipa_pass_list (all_ipa_passes);
1233 bitmap_obstack_release (NULL);
1236 /* Perform simple optimizations based on callgraph. */
1239 cgraph_optimize (void)
1241 if (errorcount || sorrycount)
1244 #ifdef ENABLE_CHECKING
1248 /* Call functions declared with the "constructor" or "destructor"
1250 cgraph_build_cdtor_fns ();
1252 /* Frontend may output common variables after the unit has been finalized.
1253 It is safe to deal with them here as they are always zero initialized. */
1254 varpool_analyze_pending_decls ();
1255 cgraph_analyze_functions ();
1257 timevar_push (TV_CGRAPHOPT);
1258 if (pre_ipa_mem_report)
1260 fprintf (stderr, "Memory consumption before IPA\n");
1261 dump_memory_report (false);
1264 fprintf (stderr, "Performing interprocedural optimizations\n");
1265 cgraph_state = CGRAPH_STATE_IPA;
1267 /* Don't run the IPA passes if there was any error or sorry messages. */
1268 if (errorcount == 0 && sorrycount == 0)
1271 /* This pass remove bodies of extern inline functions we never inlined.
1272 Do this later so other IPA passes see what is really going on. */
1273 cgraph_remove_unreachable_nodes (false, dump_file);
1274 cgraph_global_info_ready = true;
1275 if (cgraph_dump_file)
1277 fprintf (cgraph_dump_file, "Optimized ");
1278 dump_cgraph (cgraph_dump_file);
1279 dump_varpool (cgraph_dump_file);
1281 if (post_ipa_mem_report)
1283 fprintf (stderr, "Memory consumption after IPA\n");
1284 dump_memory_report (false);
1286 timevar_pop (TV_CGRAPHOPT);
1288 /* Output everything. */
1290 fprintf (stderr, "Assembling functions:\n");
1291 #ifdef ENABLE_CHECKING
1295 cgraph_mark_functions_to_output ();
1297 cgraph_state = CGRAPH_STATE_EXPANSION;
1298 if (!flag_toplevel_reorder)
1299 cgraph_output_in_order ();
1302 cgraph_output_pending_asms ();
1304 cgraph_expand_all_functions ();
1305 varpool_remove_unreferenced_decls ();
1307 varpool_assemble_pending_decls ();
1309 varpool_output_debug_info ();
1310 cgraph_process_new_functions ();
1311 cgraph_state = CGRAPH_STATE_FINISHED;
1313 if (cgraph_dump_file)
1315 fprintf (cgraph_dump_file, "\nFinal ");
1316 dump_cgraph (cgraph_dump_file);
1318 #ifdef ENABLE_CHECKING
1320 /* Double check that all inline clones are gone and that all
1321 function bodies have been released from memory. */
1322 if (!(sorrycount || errorcount))
1324 struct cgraph_node *node;
1325 bool error_found = false;
1327 for (node = cgraph_nodes; node; node = node->next)
1329 && (node->global.inlined_to
1330 || DECL_SAVED_TREE (node->decl)))
1333 dump_cgraph_node (stderr, node);
1336 internal_error ("nodes with unreleased memory found");
1340 /* Generate and emit a static constructor or destructor. WHICH must
1341 be one of 'I' (for a constructor) or 'D' (for a destructor). BODY
1342 is a STATEMENT_LIST containing GENERIC statements. PRIORITY is the
1343 initialization priority for this constructor or destructor. */
1346 cgraph_build_static_cdtor (char which, tree body, int priority)
1348 static int counter = 0;
1350 tree decl, name, resdecl;
1352 /* The priority is encoded in the constructor or destructor name.
1353 collect2 will sort the names and arrange that they are called at
1355 sprintf (which_buf, "%c_%.5d_%d", which, priority, counter++);
1356 name = get_file_function_name (which_buf);
1358 decl = build_decl (FUNCTION_DECL, name,
1359 build_function_type (void_type_node, void_list_node));
1360 current_function_decl = decl;
1362 resdecl = build_decl (RESULT_DECL, NULL_TREE, void_type_node);
1363 DECL_ARTIFICIAL (resdecl) = 1;
1364 DECL_RESULT (decl) = resdecl;
1366 allocate_struct_function (decl, false);
1368 TREE_STATIC (decl) = 1;
1369 TREE_USED (decl) = 1;
1370 DECL_ARTIFICIAL (decl) = 1;
1371 DECL_NO_INSTRUMENT_FUNCTION_ENTRY_EXIT (decl) = 1;
1372 DECL_SAVED_TREE (decl) = body;
1373 TREE_PUBLIC (decl) = ! targetm.have_ctors_dtors;
1374 DECL_UNINLINABLE (decl) = 1;
1376 DECL_INITIAL (decl) = make_node (BLOCK);
1377 TREE_USED (DECL_INITIAL (decl)) = 1;
1379 DECL_SOURCE_LOCATION (decl) = input_location;
1380 cfun->function_end_locus = input_location;
1385 DECL_STATIC_CONSTRUCTOR (decl) = 1;
1386 decl_init_priority_insert (decl, priority);
1389 DECL_STATIC_DESTRUCTOR (decl) = 1;
1390 decl_fini_priority_insert (decl, priority);
1396 gimplify_function_tree (decl);
1398 cgraph_add_new_function (decl, false);
1399 cgraph_mark_needed_node (cgraph_node (decl));
1406 cgraph_dump_file = dump_begin (TDI_cgraph, NULL);
1409 /* The edges representing the callers of the NEW_VERSION node were
1410 fixed by cgraph_function_versioning (), now the call_expr in their
1411 respective tree code should be updated to call the NEW_VERSION. */
1414 update_call_expr (struct cgraph_node *new_version)
1416 struct cgraph_edge *e;
1418 gcc_assert (new_version);
1419 for (e = new_version->callers; e; e = e->next_caller)
1420 /* Update the call expr on the edges
1421 to call the new version. */
1422 TREE_OPERAND (CALL_EXPR_FN (get_call_expr_in (e->call_stmt)), 0) = new_version->decl;
1426 /* Create a new cgraph node which is the new version of
1427 OLD_VERSION node. REDIRECT_CALLERS holds the callers
1428 edges which should be redirected to point to
1429 NEW_VERSION. ALL the callees edges of OLD_VERSION
1430 are cloned to the new version node. Return the new
1433 static struct cgraph_node *
1434 cgraph_copy_node_for_versioning (struct cgraph_node *old_version,
1436 VEC(cgraph_edge_p,heap) *redirect_callers)
1438 struct cgraph_node *new_version;
1439 struct cgraph_edge *e, *new_e;
1440 struct cgraph_edge *next_callee;
1443 gcc_assert (old_version);
1445 new_version = cgraph_node (new_decl);
1447 new_version->analyzed = true;
1448 new_version->local = old_version->local;
1449 new_version->global = old_version->global;
1450 new_version->rtl = new_version->rtl;
1451 new_version->reachable = true;
1452 new_version->count = old_version->count;
1454 /* Clone the old node callees. Recursive calls are
1456 for (e = old_version->callees;e; e=e->next_callee)
1458 new_e = cgraph_clone_edge (e, new_version, e->call_stmt, 0, e->frequency,
1459 e->loop_nest, true);
1460 new_e->count = e->count;
1462 /* Fix recursive calls.
1463 If OLD_VERSION has a recursive call after the
1464 previous edge cloning, the new version will have an edge
1465 pointing to the old version, which is wrong;
1466 Redirect it to point to the new version. */
1467 for (e = new_version->callees ; e; e = next_callee)
1469 next_callee = e->next_callee;
1470 if (e->callee == old_version)
1471 cgraph_redirect_edge_callee (e, new_version);
1476 for (i = 0; VEC_iterate (cgraph_edge_p, redirect_callers, i, e); i++)
1478 /* Redirect calls to the old version node to point to its new
1480 cgraph_redirect_edge_callee (e, new_version);
1486 /* Perform function versioning.
1487 Function versioning includes copying of the tree and
1488 a callgraph update (creating a new cgraph node and updating
1489 its callees and callers).
1491 REDIRECT_CALLERS varray includes the edges to be redirected
1494 TREE_MAP is a mapping of tree nodes we want to replace with
1495 new ones (according to results of prior analysis).
1496 OLD_VERSION_NODE is the node that is versioned.
1497 It returns the new version's cgraph node. */
1499 struct cgraph_node *
1500 cgraph_function_versioning (struct cgraph_node *old_version_node,
1501 VEC(cgraph_edge_p,heap) *redirect_callers,
1502 varray_type tree_map)
1504 tree old_decl = old_version_node->decl;
1505 struct cgraph_node *new_version_node = NULL;
1508 if (!tree_versionable_function_p (old_decl))
1511 /* Make a new FUNCTION_DECL tree node for the
1513 new_decl = copy_node (old_decl);
1515 /* Create the new version's call-graph node.
1516 and update the edges of the new node. */
1518 cgraph_copy_node_for_versioning (old_version_node, new_decl,
1521 /* Copy the OLD_VERSION_NODE function tree to the new version. */
1522 tree_function_versioning (old_decl, new_decl, tree_map, false);
1523 /* Update the call_expr on the edges to call the new version node. */
1524 update_call_expr (new_version_node);
1526 /* Update the new version's properties.
1527 Make The new version visible only within this translation unit.
1528 ??? We cannot use COMDAT linkage because there is no
1529 ABI support for this. */
1530 DECL_EXTERNAL (new_version_node->decl) = 0;
1531 DECL_ONE_ONLY (new_version_node->decl) = 0;
1532 TREE_PUBLIC (new_version_node->decl) = 0;
1533 DECL_COMDAT (new_version_node->decl) = 0;
1534 new_version_node->local.externally_visible = 0;
1535 new_version_node->local.local = 1;
1536 new_version_node->lowered = true;
1537 return new_version_node;
1540 /* Produce separate function body for inline clones so the offline copy can be
1541 modified without affecting them. */
1542 struct cgraph_node *
1543 save_inline_function_body (struct cgraph_node *node)
1545 struct cgraph_node *first_clone;
1547 gcc_assert (node == cgraph_node (node->decl));
1549 cgraph_lower_function (node);
1551 first_clone = node->next_clone;
1553 first_clone->decl = copy_node (node->decl);
1554 node->next_clone = NULL;
1555 first_clone->prev_clone = NULL;
1556 cgraph_insert_node_to_hashtable (first_clone);
1557 gcc_assert (first_clone == cgraph_node (first_clone->decl));
1559 /* Copy the OLD_VERSION_NODE function tree to the new version. */
1560 tree_function_versioning (node->decl, first_clone->decl, NULL, true);
1562 DECL_EXTERNAL (first_clone->decl) = 0;
1563 DECL_ONE_ONLY (first_clone->decl) = 0;
1564 TREE_PUBLIC (first_clone->decl) = 0;
1565 DECL_COMDAT (first_clone->decl) = 0;
1567 for (node = first_clone->next_clone; node; node = node->next_clone)
1568 node->decl = first_clone->decl;
1569 #ifdef ENABLE_CHECKING
1570 verify_cgraph_node (first_clone);
1575 #include "gt-cgraphunit.h"