1 /* Callgraph based interprocedural optimizations.
2 Copyright (C) 2003, 2004, 2005, 2006, 2007 Free Software Foundation, Inc.
3 Contributed by Jan Hubicka
5 This file is part of GCC.
7 GCC is free software; you can redistribute it and/or modify it under
8 the terms of the GNU General Public License as published by the Free
9 Software Foundation; either version 3, or (at your option) any later
12 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
13 WARRANTY; without even the implied warranty of MERCHANTABILITY or
14 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
17 You should have received a copy of the GNU General Public License
18 along with GCC; see the file COPYING3. If not see
19 <http://www.gnu.org/licenses/>. */
21 /* This module implements main driver of compilation process as well as
22 few basic interprocedural optimizers.
24 The main scope of this file is to act as an interface in between
25 tree based frontends and the backend (and middle end)
27 The front-end is supposed to use following functionality:
29 - cgraph_finalize_function
31 This function is called once front-end has parsed whole body of function
32 and it is certain that the function body nor the declaration will change.
34 (There is one exception needed for implementing GCC extern inline
37 - varpool_finalize_variable
39 This function has same behavior as the above but is used for static
42 - cgraph_finalize_compilation_unit
44 This function is called once (source level) compilation unit is finalized
45 and it will no longer change.
47 In the unit-at-a-time the call-graph construction and local function
48 analysis takes place here. Bodies of unreachable functions are released
49 to conserve memory usage.
51 The function can be called multiple times when multiple source level
52 compilation units are combined (such as in C frontend)
56 In this unit-at-a-time compilation the intra procedural analysis takes
57 place here. In particular the static functions whose address is never
58 taken are marked as local. Backend can then use this information to
59 modify calling conventions, do better inlining or similar optimizations.
61 - cgraph_mark_needed_node
62 - varpool_mark_needed_node
64 When function or variable is referenced by some hidden way the call-graph
65 data structure must be updated accordingly by this function.
66 There should be little need to call this function and all the references
67 should be made explicit to cgraph code. At present these functions are
68 used by C++ frontend to explicitly mark the keyed methods.
70 - analyze_expr callback
72 This function is responsible for lowering tree nodes not understood by
73 generic code into understandable ones or alternatively marking
74 callgraph and varpool nodes referenced by the as needed.
76 ??? On the tree-ssa genericizing should take place here and we will avoid
77 need for these hooks (replacing them by genericizing hook)
79 - expand_function callback
81 This function is used to expand function and pass it into RTL back-end.
82 Front-end should not make any assumptions about when this function can be
83 called. In particular cgraph_assemble_pending_functions,
84 varpool_assemble_pending_variables, cgraph_finalize_function,
85 varpool_finalize_function, cgraph_optimize can cause arbitrarily
86 previously finalized functions to be expanded.
88 We implement two compilation modes.
90 - unit-at-a-time: In this mode analyzing of all functions is deferred
91 to cgraph_finalize_compilation_unit and expansion into cgraph_optimize.
93 In cgraph_finalize_compilation_unit the reachable functions are
94 analyzed. During analysis the call-graph edges from reachable
95 functions are constructed and their destinations are marked as
96 reachable. References to functions and variables are discovered too
97 and variables found to be needed output to the assembly file. Via
98 mark_referenced call in assemble_variable functions referenced by
99 static variables are noticed too.
101 The intra-procedural information is produced and its existence
102 indicated by global_info_ready. Once this flag is set it is impossible
103 to change function from !reachable to reachable and thus
104 assemble_variable no longer call mark_referenced.
106 Finally the call-graph is topologically sorted and all reachable functions
107 that has not been completely inlined or are not external are output.
109 ??? It is possible that reference to function or variable is optimized
110 out. We can not deal with this nicely because topological order is not
111 suitable for it. For tree-ssa we may consider another pass doing
112 optimization and re-discovering reachable functions.
114 ??? Reorganize code so variables are output very last and only if they
115 really has been referenced by produced code, so we catch more cases
116 where reference has been optimized out.
120 All functions are variables are output as early as possible to conserve
121 memory consumption. This may or may not result in less memory used but
122 it is still needed for some legacy code that rely on particular ordering
123 of things output from the compiler.
125 Varpool data structures are not used and variables are output directly.
127 Functions are output early using call of
128 cgraph_assemble_pending_function from cgraph_finalize_function. The
129 decision on whether function is needed is made more conservative so
130 uninlininable static functions are needed too. During the call-graph
131 construction the edge destinations are not marked as reachable and it
132 is completely relied upn assemble_variable to mark them. */
137 #include "coretypes.h"
141 #include "tree-flow.h"
142 #include "tree-inline.h"
143 #include "langhooks.h"
144 #include "pointer-set.h"
151 #include "diagnostic.h"
155 #include "c-common.h"
157 #include "function.h"
158 #include "ipa-prop.h"
159 #include "tree-gimple.h"
160 #include "tree-pass.h"
163 static void cgraph_expand_all_functions (void);
164 static void cgraph_mark_functions_to_output (void);
165 static void cgraph_expand_function (struct cgraph_node *);
166 static void cgraph_output_pending_asms (void);
168 static FILE *cgraph_dump_file;
170 static GTY (()) tree static_ctors;
171 static GTY (()) tree static_dtors;
173 /* When target does not have ctors and dtors, we call all constructor
174 and destructor by special initialization/destruction function
175 recognized by collect2.
177 When we are going to build this function, collect all constructors and
178 destructors and turn them into normal functions. */
181 record_cdtor_fn (tree fndecl)
183 if (targetm.have_ctors_dtors)
186 if (DECL_STATIC_CONSTRUCTOR (fndecl))
188 static_ctors = tree_cons (NULL_TREE, fndecl, static_ctors);
189 DECL_STATIC_CONSTRUCTOR (fndecl) = 0;
190 cgraph_mark_reachable_node (cgraph_node (fndecl));
192 if (DECL_STATIC_DESTRUCTOR (fndecl))
194 static_dtors = tree_cons (NULL_TREE, fndecl, static_dtors);
195 DECL_STATIC_DESTRUCTOR (fndecl) = 0;
196 cgraph_mark_reachable_node (cgraph_node (fndecl));
200 /* Synthesize a function which calls all the global ctors or global
201 dtors in this file. This is only used for targets which do not
202 support .ctors/.dtors sections. */
204 build_cdtor (int method_type, tree cdtors)
211 for (; cdtors; cdtors = TREE_CHAIN (cdtors))
212 append_to_statement_list (build_function_call_expr (TREE_VALUE (cdtors), 0),
215 cgraph_build_static_cdtor (method_type, body, DEFAULT_INIT_PRIORITY);
218 /* Generate functions to call static constructors and destructors
219 for targets that do not support .ctors/.dtors sections. These
220 functions have magic names which are detected by collect2. */
223 cgraph_build_cdtor_fns (void)
225 if (!targetm.have_ctors_dtors)
227 build_cdtor ('I', static_ctors);
228 static_ctors = NULL_TREE;
229 build_cdtor ('D', static_dtors);
230 static_dtors = NULL_TREE;
234 gcc_assert (!static_ctors);
235 gcc_assert (!static_dtors);
239 /* Determine if function DECL is needed. That is, visible to something
240 either outside this translation unit, something magic in the system
241 configury, or (if not doing unit-at-a-time) to something we havn't
245 decide_is_function_needed (struct cgraph_node *node, tree decl)
248 if (MAIN_NAME_P (DECL_NAME (decl))
249 && TREE_PUBLIC (decl))
251 node->local.externally_visible = true;
255 /* If the user told us it is used, then it must be so. */
256 if (node->local.externally_visible)
259 if (!flag_unit_at_a_time && lookup_attribute ("used", DECL_ATTRIBUTES (decl)))
262 /* ??? If the assembler name is set by hand, it is possible to assemble
263 the name later after finalizing the function and the fact is noticed
264 in assemble_name then. This is arguably a bug. */
265 if (DECL_ASSEMBLER_NAME_SET_P (decl)
266 && TREE_SYMBOL_REFERENCED (DECL_ASSEMBLER_NAME (decl)))
269 /* With -fkeep-inline-functions we are keeping all inline functions except
270 for extern inline ones. */
271 if (flag_keep_inline_functions
272 && DECL_DECLARED_INLINE_P (decl)
273 && !DECL_EXTERNAL (decl)
274 && !lookup_attribute ("always_inline", DECL_ATTRIBUTES (decl)))
277 /* If we decided it was needed before, but at the time we didn't have
278 the body of the function available, then it's still needed. We have
279 to go back and re-check its dependencies now. */
283 /* Externally visible functions must be output. The exception is
284 COMDAT functions that must be output only when they are needed.
286 When not optimizing, also output the static functions. (see
287 PR24561), but don't do so for always_inline functions, functions
288 declared inline and nested functions. These was optimized out
289 in the original implementation and it is unclear whether we want
290 to change the behavior here. */
291 if (((TREE_PUBLIC (decl)
292 || (!optimize && !node->local.disregard_inline_limits
293 && !DECL_DECLARED_INLINE_P (decl)
295 && !flag_whole_program)
296 && !DECL_COMDAT (decl) && !DECL_EXTERNAL (decl))
299 /* Constructors and destructors are reachable from the runtime by
301 if (DECL_STATIC_CONSTRUCTOR (decl) || DECL_STATIC_DESTRUCTOR (decl))
304 if (flag_unit_at_a_time)
307 /* If not doing unit at a time, then we'll only defer this function
308 if its marked for inlining. Otherwise we want to emit it now. */
310 /* "extern inline" functions are never output locally. */
311 if (DECL_EXTERNAL (decl))
313 /* Nested functions of extern inline function shall not be emit unless
314 we inlined the origin. */
315 for (origin = decl_function_context (decl); origin;
316 origin = decl_function_context (origin))
317 if (DECL_EXTERNAL (origin))
319 /* We want to emit COMDAT functions only when absolutely necessary. */
320 if (DECL_COMDAT (decl))
322 if (!DECL_INLINE (decl)
323 || (!node->local.disregard_inline_limits
324 /* When declared inline, defer even the uninlinable functions.
325 This allows them to be eliminated when unused. */
326 && !DECL_DECLARED_INLINE_P (decl)
327 && (!node->local.inlinable || !cgraph_default_inline_p (node, NULL))))
333 /* Process CGRAPH_NEW_FUNCTIONS and perform actions necessary to add these
334 functions into callgraph in a way so they look like ordinary reachable
335 functions inserted into callgraph already at construction time. */
338 cgraph_process_new_functions (void)
342 struct cgraph_node *node;
344 /* Note that this queue may grow as its being processed, as the new
345 functions may generate new ones. */
346 while (cgraph_new_nodes)
348 node = cgraph_new_nodes;
350 cgraph_new_nodes = cgraph_new_nodes->next_needed;
351 switch (cgraph_state)
353 case CGRAPH_STATE_CONSTRUCTION:
354 /* At construction time we just need to finalize function and move
355 it into reachable functions list. */
357 node->next_needed = NULL;
358 node->needed = node->reachable = false;
359 cgraph_finalize_function (fndecl, false);
360 cgraph_mark_reachable_node (node);
364 case CGRAPH_STATE_IPA:
365 case CGRAPH_STATE_IPA_SSA:
366 /* When IPA optimization already started, do all essential
367 transformations that has been already performed on the whole
368 cgraph but not on this function. */
370 tree_register_cfg_hooks ();
372 cgraph_analyze_function (node);
373 push_cfun (DECL_STRUCT_FUNCTION (fndecl));
374 current_function_decl = fndecl;
375 node->local.inlinable = tree_inlinable_function_p (fndecl);
376 node->local.self_insns = estimate_num_insns (fndecl,
377 &eni_inlining_weights);
378 node->local.disregard_inline_limits
379 = lang_hooks.tree_inlining.disregard_inline_limits (fndecl);
380 /* Inlining characteristics are maintained by the
381 cgraph_mark_inline. */
382 node->global.insns = node->local.self_insns;
383 if (flag_really_no_inline && !node->local.disregard_inline_limits)
384 node->local.inlinable = 0;
385 if ((cgraph_state == CGRAPH_STATE_IPA_SSA
386 && !gimple_in_ssa_p (DECL_STRUCT_FUNCTION (fndecl)))
387 /* When not optimizing, be sure we run early local passes anyway
390 execute_pass_list (pass_early_local_passes.sub);
391 free_dominance_info (CDI_POST_DOMINATORS);
392 free_dominance_info (CDI_DOMINATORS);
394 current_function_decl = NULL;
397 case CGRAPH_STATE_EXPANSION:
398 /* Functions created during expansion shall be compiled
401 cgraph_expand_function (node);
412 /* When not doing unit-at-a-time, output all functions enqueued.
413 Return true when such a functions were found. */
416 cgraph_assemble_pending_functions (void)
420 if (flag_unit_at_a_time)
423 cgraph_output_pending_asms ();
425 while (cgraph_nodes_queue)
427 struct cgraph_node *n = cgraph_nodes_queue;
429 cgraph_nodes_queue = cgraph_nodes_queue->next_needed;
430 n->next_needed = NULL;
431 if (!n->global.inlined_to
433 && !DECL_EXTERNAL (n->decl))
435 cgraph_expand_function (n);
438 output |= cgraph_process_new_functions ();
445 /* As an GCC extension we allow redefinition of the function. The
446 semantics when both copies of bodies differ is not well defined.
447 We replace the old body with new body so in unit at a time mode
448 we always use new body, while in normal mode we may end up with
449 old body inlined into some functions and new body expanded and
452 ??? It may make more sense to use one body for inlining and other
453 body for expanding the function but this is difficult to do. */
456 cgraph_reset_node (struct cgraph_node *node)
458 /* If node->output is set, then this is a unit-at-a-time compilation
459 and we have already begun whole-unit analysis. This is *not*
460 testing for whether we've already emitted the function. That
461 case can be sort-of legitimately seen with real function
462 redefinition errors. I would argue that the front end should
463 never present us with such a case, but don't enforce that for now. */
464 gcc_assert (!node->output);
466 /* Reset our data structures so we can analyze the function again. */
467 memset (&node->local, 0, sizeof (node->local));
468 memset (&node->global, 0, sizeof (node->global));
469 memset (&node->rtl, 0, sizeof (node->rtl));
470 node->analyzed = false;
471 node->local.redefined_extern_inline = true;
472 node->local.finalized = false;
474 if (!flag_unit_at_a_time)
476 struct cgraph_node *n, *next;
478 for (n = cgraph_nodes; n; n = next)
481 if (n->global.inlined_to == node)
482 cgraph_remove_node (n);
486 cgraph_node_remove_callees (node);
488 /* We may need to re-queue the node for assembling in case
489 we already proceeded it and ignored as not needed. */
490 if (node->reachable && !flag_unit_at_a_time)
492 struct cgraph_node *n;
494 for (n = cgraph_nodes_queue; n; n = n->next_needed)
503 cgraph_lower_function (struct cgraph_node *node)
507 tree_lowering_passes (node->decl);
508 node->lowered = true;
511 /* DECL has been parsed. Take it, queue it, compile it at the whim of the
512 logic in effect. If NESTED is true, then our caller cannot stand to have
513 the garbage collector run at the moment. We would need to either create
514 a new GC context, or just not compile right now. */
517 cgraph_finalize_function (tree decl, bool nested)
519 struct cgraph_node *node = cgraph_node (decl);
521 if (node->local.finalized)
522 cgraph_reset_node (node);
524 node->pid = cgraph_max_pid ++;
525 notice_global_symbol (decl);
527 node->local.finalized = true;
528 node->lowered = DECL_STRUCT_FUNCTION (decl)->cfg != NULL;
529 record_cdtor_fn (node->decl);
531 lower_nested_functions (decl);
532 gcc_assert (!node->nested);
534 /* If not unit at a time, then we need to create the call graph
535 now, so that called functions can be queued and emitted now. */
536 if (!flag_unit_at_a_time)
537 cgraph_analyze_function (node);
539 if (decide_is_function_needed (node, decl))
540 cgraph_mark_needed_node (node);
542 /* Since we reclaim unreachable nodes at the end of every language
543 level unit, we need to be conservative about possible entry points
545 if ((TREE_PUBLIC (decl) && !DECL_COMDAT (decl) && !DECL_EXTERNAL (decl)))
546 cgraph_mark_reachable_node (node);
548 /* If not unit at a time, go ahead and emit everything we've found
549 to be reachable at this time. */
552 if (!cgraph_assemble_pending_functions ())
556 /* If we've not yet emitted decl, tell the debug info about it. */
557 if (!TREE_ASM_WRITTEN (decl))
558 (*debug_hooks->deferred_inline_function) (decl);
560 /* Possibly warn about unused parameters. */
561 if (warn_unused_parameter)
562 do_warn_unused_parameter (decl);
565 /* Verify cgraph nodes of given cgraph node. */
567 verify_cgraph_node (struct cgraph_node *node)
569 struct cgraph_edge *e;
570 struct cgraph_node *main_clone;
571 struct function *this_cfun = DECL_STRUCT_FUNCTION (node->decl);
572 basic_block this_block;
573 block_stmt_iterator bsi;
574 bool error_found = false;
576 if (errorcount || sorrycount)
579 timevar_push (TV_CGRAPH_VERIFY);
580 for (e = node->callees; e; e = e->next_callee)
583 error ("aux field set for edge %s->%s",
584 cgraph_node_name (e->caller), cgraph_node_name (e->callee));
589 error ("Execution count is negative");
592 for (e = node->callers; e; e = e->next_caller)
596 error ("caller edge count is negative");
599 if (e->frequency < 0)
601 error ("caller edge frequency is negative");
604 if (e->frequency > CGRAPH_FREQ_MAX)
606 error ("caller edge frequency is too large");
609 if (!e->inline_failed)
611 if (node->global.inlined_to
612 != (e->caller->global.inlined_to
613 ? e->caller->global.inlined_to : e->caller))
615 error ("inlined_to pointer is wrong");
618 if (node->callers->next_caller)
620 error ("multiple inline callers");
625 if (node->global.inlined_to)
627 error ("inlined_to pointer set for noninline callers");
631 if (!node->callers && node->global.inlined_to)
633 error ("inlined_to pointer is set but no predecessors found");
636 if (node->global.inlined_to == node)
638 error ("inlined_to pointer refers to itself");
642 for (main_clone = cgraph_node (node->decl); main_clone;
643 main_clone = main_clone->next_clone)
644 if (main_clone == node)
646 if (!cgraph_node (node->decl))
648 error ("node not found in cgraph_hash");
653 && DECL_SAVED_TREE (node->decl) && !TREE_ASM_WRITTEN (node->decl)
654 && (!DECL_EXTERNAL (node->decl) || node->global.inlined_to))
658 /* The nodes we're interested in are never shared, so walk
659 the tree ignoring duplicates. */
660 struct pointer_set_t *visited_nodes = pointer_set_create ();
661 /* Reach the trees by walking over the CFG, and note the
662 enclosing basic-blocks in the call edges. */
663 FOR_EACH_BB_FN (this_block, this_cfun)
664 for (bsi = bsi_start (this_block); !bsi_end_p (bsi); bsi_next (&bsi))
666 tree stmt = bsi_stmt (bsi);
667 tree call = get_call_expr_in (stmt);
669 if (call && (decl = get_callee_fndecl (call)))
671 struct cgraph_edge *e = cgraph_edge (node, stmt);
676 error ("shared call_stmt:");
677 debug_generic_stmt (stmt);
680 if (e->callee->decl != cgraph_node (decl)->decl
683 error ("edge points to wrong declaration:");
684 debug_tree (e->callee->decl);
685 fprintf (stderr," Instead of:");
692 error ("missing callgraph edge for call stmt:");
693 debug_generic_stmt (stmt);
698 pointer_set_destroy (visited_nodes);
701 /* No CFG available?! */
704 for (e = node->callees; e; e = e->next_callee)
708 error ("edge %s->%s has no corresponding call_stmt",
709 cgraph_node_name (e->caller),
710 cgraph_node_name (e->callee));
711 debug_generic_stmt (e->call_stmt);
719 dump_cgraph_node (stderr, node);
720 internal_error ("verify_cgraph_node failed");
722 timevar_pop (TV_CGRAPH_VERIFY);
725 /* Verify whole cgraph structure. */
729 struct cgraph_node *node;
731 if (sorrycount || errorcount)
734 for (node = cgraph_nodes; node; node = node->next)
735 verify_cgraph_node (node);
738 /* Output all asm statements we have stored up to be output. */
741 cgraph_output_pending_asms (void)
743 struct cgraph_asm_node *can;
745 if (errorcount || sorrycount)
748 for (can = cgraph_asm_nodes; can; can = can->next)
749 assemble_asm (can->asm_str);
750 cgraph_asm_nodes = NULL;
753 /* Analyze the function scheduled to be output. */
755 cgraph_analyze_function (struct cgraph_node *node)
757 tree decl = node->decl;
759 current_function_decl = decl;
760 push_cfun (DECL_STRUCT_FUNCTION (decl));
761 cgraph_lower_function (node);
762 node->analyzed = true;
764 if (!flag_unit_at_a_time)
766 bitmap_obstack_initialize (NULL);
767 tree_register_cfg_hooks ();
768 execute_pass_list (pass_early_local_passes.sub);
769 free_dominance_info (CDI_POST_DOMINATORS);
770 free_dominance_info (CDI_DOMINATORS);
771 bitmap_obstack_release (NULL);
775 current_function_decl = NULL;
778 /* Look for externally_visible and used attributes and mark cgraph nodes
781 We cannot mark the nodes at the point the attributes are processed (in
782 handle_*_attribute) because the copy of the declarations available at that
783 point may not be canonical. For example, in:
786 void f() __attribute__((used));
788 the declaration we see in handle_used_attribute will be the second
789 declaration -- but the front end will subsequently merge that declaration
790 with the original declaration and discard the second declaration.
792 Furthermore, we can't mark these nodes in cgraph_finalize_function because:
795 void f() __attribute__((externally_visible));
799 So, we walk the nodes at the end of the translation unit, applying the
800 attributes at that point. */
803 process_function_and_variable_attributes (struct cgraph_node *first,
804 struct varpool_node *first_var)
806 struct cgraph_node *node;
807 struct varpool_node *vnode;
809 for (node = cgraph_nodes; node != first; node = node->next)
811 tree decl = node->decl;
812 if (lookup_attribute ("used", DECL_ATTRIBUTES (decl)))
814 mark_decl_referenced (decl);
815 if (node->local.finalized)
816 cgraph_mark_needed_node (node);
818 if (lookup_attribute ("externally_visible", DECL_ATTRIBUTES (decl)))
820 if (! TREE_PUBLIC (node->decl))
821 warning (OPT_Wattributes,
822 "%J%<externally_visible%> attribute have effect only on public objects",
826 if (node->local.finalized)
827 cgraph_mark_needed_node (node);
828 node->local.externally_visible = true;
832 for (vnode = varpool_nodes; vnode != first_var; vnode = vnode->next)
834 tree decl = vnode->decl;
835 if (lookup_attribute ("used", DECL_ATTRIBUTES (decl)))
837 mark_decl_referenced (decl);
838 if (vnode->finalized)
839 varpool_mark_needed_node (vnode);
841 if (lookup_attribute ("externally_visible", DECL_ATTRIBUTES (decl)))
843 if (! TREE_PUBLIC (vnode->decl))
844 warning (OPT_Wattributes,
845 "%J%<externally_visible%> attribute have effect only on public objects",
849 if (vnode->finalized)
850 varpool_mark_needed_node (vnode);
851 vnode->externally_visible = true;
857 /* Process CGRAPH_NODES_NEEDED queue, analyze each function (and transitively
858 each reachable functions) and build cgraph.
859 The function can be called multiple times after inserting new nodes
860 into beginning of queue. Just the new part of queue is re-scanned then. */
863 cgraph_analyze_functions (void)
865 /* Keep track of already processed nodes when called multiple times for
866 intermodule optimization. */
867 static struct cgraph_node *first_analyzed;
868 struct cgraph_node *first_processed = first_analyzed;
869 static struct varpool_node *first_analyzed_var;
870 struct cgraph_node *node, *next;
872 process_function_and_variable_attributes (first_processed,
874 first_processed = cgraph_nodes;
875 first_analyzed_var = varpool_nodes;
876 varpool_analyze_pending_decls ();
877 if (cgraph_dump_file)
879 fprintf (cgraph_dump_file, "Initial entry points:");
880 for (node = cgraph_nodes; node != first_analyzed; node = node->next)
881 if (node->needed && DECL_SAVED_TREE (node->decl))
882 fprintf (cgraph_dump_file, " %s", cgraph_node_name (node));
883 fprintf (cgraph_dump_file, "\n");
885 cgraph_process_new_functions ();
887 /* Propagate reachability flag and lower representation of all reachable
888 functions. In the future, lowering will introduce new functions and
889 new entry points on the way (by template instantiation and virtual
890 method table generation for instance). */
891 while (cgraph_nodes_queue)
893 struct cgraph_edge *edge;
894 tree decl = cgraph_nodes_queue->decl;
896 node = cgraph_nodes_queue;
897 cgraph_nodes_queue = cgraph_nodes_queue->next_needed;
898 node->next_needed = NULL;
900 /* ??? It is possible to create extern inline function and later using
901 weak alias attribute to kill its body. See
902 gcc.c-torture/compile/20011119-1.c */
903 if (!DECL_SAVED_TREE (decl))
905 cgraph_reset_node (node);
909 gcc_assert (!node->analyzed && node->reachable);
910 gcc_assert (DECL_SAVED_TREE (decl));
912 cgraph_analyze_function (node);
914 for (edge = node->callees; edge; edge = edge->next_callee)
915 if (!edge->callee->reachable)
916 cgraph_mark_reachable_node (edge->callee);
918 /* We finalize local static variables during constructing callgraph
919 edges. Process their attributes too. */
920 process_function_and_variable_attributes (first_processed,
922 first_processed = cgraph_nodes;
923 first_analyzed_var = varpool_nodes;
924 varpool_analyze_pending_decls ();
925 cgraph_process_new_functions ();
928 /* Collect entry points to the unit. */
929 if (cgraph_dump_file)
931 fprintf (cgraph_dump_file, "Unit entry points:");
932 for (node = cgraph_nodes; node != first_analyzed; node = node->next)
933 if (node->needed && DECL_SAVED_TREE (node->decl))
934 fprintf (cgraph_dump_file, " %s", cgraph_node_name (node));
935 fprintf (cgraph_dump_file, "\n\nInitial ");
936 dump_cgraph (cgraph_dump_file);
939 if (cgraph_dump_file)
940 fprintf (cgraph_dump_file, "\nReclaiming functions:");
942 for (node = cgraph_nodes; node != first_analyzed; node = next)
944 tree decl = node->decl;
947 if (node->local.finalized && !DECL_SAVED_TREE (decl))
948 cgraph_reset_node (node);
950 if (!node->reachable && DECL_SAVED_TREE (decl))
952 if (cgraph_dump_file)
953 fprintf (cgraph_dump_file, " %s", cgraph_node_name (node));
954 cgraph_remove_node (node);
958 node->next_needed = NULL;
959 gcc_assert (!node->local.finalized || DECL_SAVED_TREE (decl));
960 gcc_assert (node->analyzed == node->local.finalized);
962 if (cgraph_dump_file)
964 fprintf (cgraph_dump_file, "\n\nReclaimed ");
965 dump_cgraph (cgraph_dump_file);
967 first_analyzed = cgraph_nodes;
971 /* Analyze the whole compilation unit once it is parsed completely. */
974 cgraph_finalize_compilation_unit (void)
976 if (errorcount || sorrycount)
981 if (!flag_unit_at_a_time)
983 cgraph_output_pending_asms ();
984 cgraph_assemble_pending_functions ();
985 varpool_output_debug_info ();
991 fprintf (stderr, "\nAnalyzing compilation unit\n");
995 timevar_push (TV_CGRAPH);
996 cgraph_analyze_functions ();
997 timevar_pop (TV_CGRAPH);
999 /* Figure out what functions we want to assemble. */
1002 cgraph_mark_functions_to_output (void)
1004 struct cgraph_node *node;
1006 for (node = cgraph_nodes; node; node = node->next)
1008 tree decl = node->decl;
1009 struct cgraph_edge *e;
1011 gcc_assert (!node->output);
1013 for (e = node->callers; e; e = e->next_caller)
1014 if (e->inline_failed)
1017 /* We need to output all local functions that are used and not
1018 always inlined, as well as those that are reachable from
1019 outside the current compilation unit. */
1020 if (DECL_SAVED_TREE (decl)
1021 && !node->global.inlined_to
1023 || (e && node->reachable))
1024 && !TREE_ASM_WRITTEN (decl)
1025 && !DECL_EXTERNAL (decl))
1029 /* We should've reclaimed all functions that are not needed. */
1030 #ifdef ENABLE_CHECKING
1031 if (!node->global.inlined_to && DECL_SAVED_TREE (decl)
1032 && !DECL_EXTERNAL (decl))
1034 dump_cgraph_node (stderr, node);
1035 internal_error ("failed to reclaim unneeded function");
1038 gcc_assert (node->global.inlined_to || !DECL_SAVED_TREE (decl)
1039 || DECL_EXTERNAL (decl));
1046 /* Expand function specified by NODE. */
1049 cgraph_expand_function (struct cgraph_node *node)
1051 enum debug_info_type save_write_symbols = NO_DEBUG;
1052 const struct gcc_debug_hooks *save_debug_hooks = NULL;
1053 tree decl = node->decl;
1055 /* We ought to not compile any inline clones. */
1056 gcc_assert (!node->global.inlined_to);
1058 if (flag_unit_at_a_time)
1059 announce_function (decl);
1061 gcc_assert (node->lowered);
1063 if (DECL_IGNORED_P (decl))
1065 save_write_symbols = write_symbols;
1066 write_symbols = NO_DEBUG;
1067 save_debug_hooks = debug_hooks;
1068 debug_hooks = &do_nothing_debug_hooks;
1071 /* Generate RTL for the body of DECL. */
1072 lang_hooks.callgraph.expand_function (decl);
1074 /* Make sure that BE didn't give up on compiling. */
1075 /* ??? Can happen with nested function of extern inline. */
1076 gcc_assert (TREE_ASM_WRITTEN (node->decl));
1078 if (DECL_IGNORED_P (decl))
1080 write_symbols = save_write_symbols;
1081 debug_hooks = save_debug_hooks;
1084 current_function_decl = NULL;
1085 if (!cgraph_preserve_function_body_p (node->decl))
1087 cgraph_release_function_body (node);
1088 /* Eliminate all call edges. This is important so the call_expr no longer
1089 points to the dead function body. */
1090 cgraph_node_remove_callees (node);
1093 cgraph_function_flags_ready = true;
1096 /* Return true when CALLER_DECL should be inlined into CALLEE_DECL. */
1099 cgraph_inline_p (struct cgraph_edge *e, const char **reason)
1101 *reason = e->inline_failed;
1102 return !e->inline_failed;
1107 /* Expand all functions that must be output.
1109 Attempt to topologically sort the nodes so function is output when
1110 all called functions are already assembled to allow data to be
1111 propagated across the callgraph. Use a stack to get smaller distance
1112 between a function and its callees (later we may choose to use a more
1113 sophisticated algorithm for function reordering; we will likely want
1114 to use subsections to make the output functions appear in top-down
1118 cgraph_expand_all_functions (void)
1120 struct cgraph_node *node;
1121 struct cgraph_node **order = XCNEWVEC (struct cgraph_node *, cgraph_n_nodes);
1122 int order_pos = 0, new_order_pos = 0;
1125 order_pos = cgraph_postorder (order);
1126 gcc_assert (order_pos == cgraph_n_nodes);
1128 /* Garbage collector may remove inline clones we eliminate during
1129 optimization. So we must be sure to not reference them. */
1130 for (i = 0; i < order_pos; i++)
1131 if (order[i]->output)
1132 order[new_order_pos++] = order[i];
1134 for (i = new_order_pos - 1; i >= 0; i--)
1139 gcc_assert (node->reachable);
1141 cgraph_expand_function (node);
1144 cgraph_process_new_functions ();
1150 /* This is used to sort the node types by the cgraph order number. */
1152 struct cgraph_order_sort
1154 enum { ORDER_UNDEFINED = 0, ORDER_FUNCTION, ORDER_VAR, ORDER_ASM } kind;
1157 struct cgraph_node *f;
1158 struct varpool_node *v;
1159 struct cgraph_asm_node *a;
1163 /* Output all functions, variables, and asm statements in the order
1164 according to their order fields, which is the order in which they
1165 appeared in the file. This implements -fno-toplevel-reorder. In
1166 this mode we may output functions and variables which don't really
1167 need to be output. */
1170 cgraph_output_in_order (void)
1174 struct cgraph_order_sort *nodes;
1176 struct cgraph_node *pf;
1177 struct varpool_node *pv;
1178 struct cgraph_asm_node *pa;
1181 size = max * sizeof (struct cgraph_order_sort);
1182 nodes = (struct cgraph_order_sort *) alloca (size);
1183 memset (nodes, 0, size);
1185 varpool_analyze_pending_decls ();
1187 for (pf = cgraph_nodes; pf; pf = pf->next)
1192 gcc_assert (nodes[i].kind == ORDER_UNDEFINED);
1193 nodes[i].kind = ORDER_FUNCTION;
1198 for (pv = varpool_nodes_queue; pv; pv = pv->next_needed)
1201 gcc_assert (nodes[i].kind == ORDER_UNDEFINED);
1202 nodes[i].kind = ORDER_VAR;
1206 for (pa = cgraph_asm_nodes; pa; pa = pa->next)
1209 gcc_assert (nodes[i].kind == ORDER_UNDEFINED);
1210 nodes[i].kind = ORDER_ASM;
1214 for (i = 0; i < max; ++i)
1216 switch (nodes[i].kind)
1218 case ORDER_FUNCTION:
1219 nodes[i].u.f->output = 0;
1220 cgraph_expand_function (nodes[i].u.f);
1224 varpool_assemble_decl (nodes[i].u.v);
1228 assemble_asm (nodes[i].u.a->asm_str);
1231 case ORDER_UNDEFINED:
1239 cgraph_asm_nodes = NULL;
1242 /* Return true when function body of DECL still needs to be kept around
1243 for later re-use. */
1245 cgraph_preserve_function_body_p (tree decl)
1247 struct cgraph_node *node;
1248 if (!cgraph_global_info_ready)
1249 return (flag_really_no_inline
1250 ? lang_hooks.tree_inlining.disregard_inline_limits (decl)
1251 : DECL_INLINE (decl));
1252 /* Look if there is any clone around. */
1253 for (node = cgraph_node (decl); node; node = node->next_clone)
1254 if (node->global.inlined_to)
1263 current_function_decl = NULL;
1264 tree_register_cfg_hooks ();
1265 bitmap_obstack_initialize (NULL);
1266 execute_ipa_pass_list (all_ipa_passes);
1267 bitmap_obstack_release (NULL);
1270 /* Perform simple optimizations based on callgraph. */
1273 cgraph_optimize (void)
1275 if (errorcount || sorrycount)
1278 #ifdef ENABLE_CHECKING
1282 /* Call functions declared with the "constructor" or "destructor"
1284 cgraph_build_cdtor_fns ();
1285 if (!flag_unit_at_a_time)
1287 cgraph_assemble_pending_functions ();
1288 cgraph_process_new_functions ();
1289 cgraph_state = CGRAPH_STATE_FINISHED;
1290 cgraph_output_pending_asms ();
1291 varpool_assemble_pending_decls ();
1292 varpool_output_debug_info ();
1296 /* Frontend may output common variables after the unit has been finalized.
1297 It is safe to deal with them here as they are always zero initialized. */
1298 varpool_analyze_pending_decls ();
1299 cgraph_analyze_functions ();
1301 timevar_push (TV_CGRAPHOPT);
1302 if (pre_ipa_mem_report)
1304 fprintf (stderr, "Memory consumption before IPA\n");
1305 dump_memory_report (false);
1308 fprintf (stderr, "Performing interprocedural optimizations\n");
1309 cgraph_state = CGRAPH_STATE_IPA;
1311 /* Don't run the IPA passes if there was any error or sorry messages. */
1312 if (errorcount == 0 && sorrycount == 0)
1315 /* This pass remove bodies of extern inline functions we never inlined.
1316 Do this later so other IPA passes see what is really going on. */
1317 cgraph_remove_unreachable_nodes (false, dump_file);
1318 cgraph_global_info_ready = true;
1319 if (cgraph_dump_file)
1321 fprintf (cgraph_dump_file, "Optimized ");
1322 dump_cgraph (cgraph_dump_file);
1323 dump_varpool (cgraph_dump_file);
1325 if (post_ipa_mem_report)
1327 fprintf (stderr, "Memory consumption after IPA\n");
1328 dump_memory_report (false);
1330 timevar_pop (TV_CGRAPHOPT);
1332 /* Output everything. */
1334 fprintf (stderr, "Assembling functions:\n");
1335 #ifdef ENABLE_CHECKING
1339 cgraph_mark_functions_to_output ();
1341 cgraph_state = CGRAPH_STATE_EXPANSION;
1342 if (!flag_toplevel_reorder)
1343 cgraph_output_in_order ();
1346 cgraph_output_pending_asms ();
1348 cgraph_expand_all_functions ();
1349 varpool_remove_unreferenced_decls ();
1351 varpool_assemble_pending_decls ();
1352 varpool_output_debug_info ();
1354 cgraph_process_new_functions ();
1355 cgraph_state = CGRAPH_STATE_FINISHED;
1357 if (cgraph_dump_file)
1359 fprintf (cgraph_dump_file, "\nFinal ");
1360 dump_cgraph (cgraph_dump_file);
1362 #ifdef ENABLE_CHECKING
1364 /* Double check that all inline clones are gone and that all
1365 function bodies have been released from memory. */
1366 if (flag_unit_at_a_time
1367 && !(sorrycount || errorcount))
1369 struct cgraph_node *node;
1370 bool error_found = false;
1372 for (node = cgraph_nodes; node; node = node->next)
1374 && (node->global.inlined_to
1375 || DECL_SAVED_TREE (node->decl)))
1378 dump_cgraph_node (stderr, node);
1381 internal_error ("nodes with no released memory found");
1385 /* Generate and emit a static constructor or destructor. WHICH must be
1386 one of 'I' or 'D'. BODY should be a STATEMENT_LIST containing
1387 GENERIC statements. */
1390 cgraph_build_static_cdtor (char which, tree body, int priority)
1392 static int counter = 0;
1394 tree decl, name, resdecl;
1396 sprintf (which_buf, "%c_%d", which, counter++);
1397 name = get_file_function_name (which_buf);
1399 decl = build_decl (FUNCTION_DECL, name,
1400 build_function_type (void_type_node, void_list_node));
1401 current_function_decl = decl;
1403 resdecl = build_decl (RESULT_DECL, NULL_TREE, void_type_node);
1404 DECL_ARTIFICIAL (resdecl) = 1;
1405 DECL_IGNORED_P (resdecl) = 1;
1406 DECL_RESULT (decl) = resdecl;
1408 allocate_struct_function (decl);
1410 TREE_STATIC (decl) = 1;
1411 TREE_USED (decl) = 1;
1412 DECL_ARTIFICIAL (decl) = 1;
1413 DECL_IGNORED_P (decl) = 1;
1414 DECL_NO_INSTRUMENT_FUNCTION_ENTRY_EXIT (decl) = 1;
1415 DECL_SAVED_TREE (decl) = body;
1416 TREE_PUBLIC (decl) = ! targetm.have_ctors_dtors;
1417 DECL_UNINLINABLE (decl) = 1;
1419 DECL_INITIAL (decl) = make_node (BLOCK);
1420 TREE_USED (DECL_INITIAL (decl)) = 1;
1422 DECL_SOURCE_LOCATION (decl) = input_location;
1423 cfun->function_end_locus = input_location;
1428 DECL_STATIC_CONSTRUCTOR (decl) = 1;
1429 decl_init_priority_insert (decl, priority);
1432 DECL_STATIC_DESTRUCTOR (decl) = 1;
1433 decl_fini_priority_insert (decl, priority);
1439 gimplify_function_tree (decl);
1441 cgraph_add_new_function (decl, false);
1442 cgraph_mark_needed_node (cgraph_node (decl));
1448 cgraph_dump_file = dump_begin (TDI_cgraph, NULL);
1451 /* The edges representing the callers of the NEW_VERSION node were
1452 fixed by cgraph_function_versioning (), now the call_expr in their
1453 respective tree code should be updated to call the NEW_VERSION. */
1456 update_call_expr (struct cgraph_node *new_version)
1458 struct cgraph_edge *e;
1460 gcc_assert (new_version);
1461 for (e = new_version->callers; e; e = e->next_caller)
1462 /* Update the call expr on the edges
1463 to call the new version. */
1464 TREE_OPERAND (CALL_EXPR_FN (get_call_expr_in (e->call_stmt)), 0) = new_version->decl;
1468 /* Create a new cgraph node which is the new version of
1469 OLD_VERSION node. REDIRECT_CALLERS holds the callers
1470 edges which should be redirected to point to
1471 NEW_VERSION. ALL the callees edges of OLD_VERSION
1472 are cloned to the new version node. Return the new
1475 static struct cgraph_node *
1476 cgraph_copy_node_for_versioning (struct cgraph_node *old_version,
1478 VEC(cgraph_edge_p,heap) *redirect_callers)
1480 struct cgraph_node *new_version;
1481 struct cgraph_edge *e, *new_e;
1482 struct cgraph_edge *next_callee;
1485 gcc_assert (old_version);
1487 new_version = cgraph_node (new_decl);
1489 new_version->analyzed = true;
1490 new_version->local = old_version->local;
1491 new_version->global = old_version->global;
1492 new_version->rtl = new_version->rtl;
1493 new_version->reachable = true;
1494 new_version->count = old_version->count;
1496 /* Clone the old node callees. Recursive calls are
1498 for (e = old_version->callees;e; e=e->next_callee)
1500 new_e = cgraph_clone_edge (e, new_version, e->call_stmt, 0, e->frequency,
1501 e->loop_nest, true);
1502 new_e->count = e->count;
1504 /* Fix recursive calls.
1505 If OLD_VERSION has a recursive call after the
1506 previous edge cloning, the new version will have an edge
1507 pointing to the old version, which is wrong;
1508 Redirect it to point to the new version. */
1509 for (e = new_version->callees ; e; e = next_callee)
1511 next_callee = e->next_callee;
1512 if (e->callee == old_version)
1513 cgraph_redirect_edge_callee (e, new_version);
1518 for (i = 0; VEC_iterate (cgraph_edge_p, redirect_callers, i, e); i++)
1520 /* Redirect calls to the old version node to point to its new
1522 cgraph_redirect_edge_callee (e, new_version);
1528 /* Perform function versioning.
1529 Function versioning includes copying of the tree and
1530 a callgraph update (creating a new cgraph node and updating
1531 its callees and callers).
1533 REDIRECT_CALLERS varray includes the edges to be redirected
1536 TREE_MAP is a mapping of tree nodes we want to replace with
1537 new ones (according to results of prior analysis).
1538 OLD_VERSION_NODE is the node that is versioned.
1539 It returns the new version's cgraph node. */
1541 struct cgraph_node *
1542 cgraph_function_versioning (struct cgraph_node *old_version_node,
1543 VEC(cgraph_edge_p,heap) *redirect_callers,
1544 varray_type tree_map)
1546 tree old_decl = old_version_node->decl;
1547 struct cgraph_node *new_version_node = NULL;
1550 if (!tree_versionable_function_p (old_decl))
1553 /* Make a new FUNCTION_DECL tree node for the
1555 new_decl = copy_node (old_decl);
1557 /* Create the new version's call-graph node.
1558 and update the edges of the new node. */
1560 cgraph_copy_node_for_versioning (old_version_node, new_decl,
1563 /* Copy the OLD_VERSION_NODE function tree to the new version. */
1564 tree_function_versioning (old_decl, new_decl, tree_map, false);
1565 /* Update the call_expr on the edges to call the new version node. */
1566 update_call_expr (new_version_node);
1568 /* Update the new version's properties.
1569 Make The new version visible only within this translation unit.
1570 ??? We cannot use COMDAT linkage because there is no
1571 ABI support for this. */
1572 DECL_EXTERNAL (new_version_node->decl) = 0;
1573 DECL_ONE_ONLY (new_version_node->decl) = 0;
1574 TREE_PUBLIC (new_version_node->decl) = 0;
1575 DECL_COMDAT (new_version_node->decl) = 0;
1576 new_version_node->local.externally_visible = 0;
1577 new_version_node->local.local = 1;
1578 new_version_node->lowered = true;
1579 return new_version_node;
1582 /* Produce separate function body for inline clones so the offline copy can be
1583 modified without affecting them. */
1584 struct cgraph_node *
1585 save_inline_function_body (struct cgraph_node *node)
1587 struct cgraph_node *first_clone;
1589 gcc_assert (node == cgraph_node (node->decl));
1591 cgraph_lower_function (node);
1593 /* In non-unit-at-a-time we construct full fledged clone we never output to
1594 assembly file. This clone is pointed out by inline_decl of original function
1595 and inlining infrastructure knows how to deal with this. */
1596 if (!flag_unit_at_a_time)
1598 struct cgraph_edge *e;
1600 first_clone = cgraph_clone_node (node, node->count, 0, CGRAPH_FREQ_BASE,
1602 first_clone->needed = 0;
1603 first_clone->reachable = 1;
1604 /* Recursively clone all bodies. */
1605 for (e = first_clone->callees; e; e = e->next_callee)
1606 if (!e->inline_failed)
1607 cgraph_clone_inlined_nodes (e, true, false);
1610 first_clone = node->next_clone;
1612 first_clone->decl = copy_node (node->decl);
1613 node->next_clone = NULL;
1614 if (!flag_unit_at_a_time)
1615 node->inline_decl = first_clone->decl;
1616 first_clone->prev_clone = NULL;
1617 cgraph_insert_node_to_hashtable (first_clone);
1618 gcc_assert (first_clone == cgraph_node (first_clone->decl));
1620 /* Copy the OLD_VERSION_NODE function tree to the new version. */
1621 tree_function_versioning (node->decl, first_clone->decl, NULL, true);
1623 DECL_EXTERNAL (first_clone->decl) = 0;
1624 DECL_ONE_ONLY (first_clone->decl) = 0;
1625 TREE_PUBLIC (first_clone->decl) = 0;
1626 DECL_COMDAT (first_clone->decl) = 0;
1628 for (node = first_clone->next_clone; node; node = node->next_clone)
1629 node->decl = first_clone->decl;
1630 #ifdef ENABLE_CHECKING
1631 verify_cgraph_node (first_clone);
1636 #include "gt-cgraphunit.h"