1 /* Callgraph handling code.
2 Copyright (C) 2003 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 2, 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 COPYING. If not, write to the Free
19 Software Foundation, 59 Temple Place - Suite 330, Boston, MA
24 #include "coretypes.h"
27 #include "tree-inline.h"
28 #include "langhooks.h"
36 #include "diagnostic.h"
39 static void cgraph_expand_functions PARAMS ((void));
40 static void cgraph_mark_functions_to_output PARAMS ((void));
41 static void cgraph_expand_function PARAMS ((struct cgraph_node *));
42 static tree record_call_1 PARAMS ((tree *, int *, void *));
43 static void cgraph_mark_local_functions PARAMS ((void));
44 static void cgraph_mark_functions_to_inline_once PARAMS ((void));
45 static void cgraph_optimize_function PARAMS ((struct cgraph_node *));
47 /* Analyze function once it is parsed. Set up the local information
48 available - create cgraph edges for function calls via BODY. */
51 cgraph_finalize_function (decl, body)
53 tree body ATTRIBUTE_UNUSED;
55 struct cgraph_node *node = cgraph_node (decl);
58 node->local.finalized = true;
60 if (/* Externally visible functions must be output. The exception are
61 COMDAT functions that must be output only when they are needed.
62 Similarly are handled deferred functions and
63 external functions (GCC extension "extern inline") */
64 (TREE_PUBLIC (decl) && !DECL_COMDAT (decl) && !DECL_EXTERNAL (decl))
65 /* ??? Constructors and destructors not called otherwise can be inlined
66 into single construction/destruction function per section to save some
67 resources. For now just mark it as reachable. */
68 || DECL_STATIC_CONSTRUCTOR (decl)
69 || DECL_STATIC_DESTRUCTOR (decl)
70 /* Function whose name is output to the assembler file must be produced.
71 It is possible to assemble the name later after finalizing the function
72 and the fact is noticed in assemble_name then. */
73 || (DECL_ASSEMBLER_NAME_SET_P (decl)
74 && TREE_SYMBOL_REFERENCED (DECL_ASSEMBLER_NAME (decl)))
75 || lookup_attribute ("used", DECL_ATTRIBUTES (decl)))
77 cgraph_mark_needed_node (node, 1);
80 (*debug_hooks->deferred_inline_function) (decl);
83 /* Walk tree and record all calls. Called via walk_tree. */
85 record_call_1 (tp, walk_subtrees, data)
90 if (TREE_CODE (*tp) == VAR_DECL && TREE_STATIC (*tp))
91 cgraph_varpool_mark_needed_node (cgraph_varpool_node (*tp));
92 /* Record dereferences to the functions. This makes the functions
93 reachable unconditionally. */
94 else if (TREE_CODE (*tp) == ADDR_EXPR)
96 tree decl = TREE_OPERAND (*tp, 0);
97 if (TREE_CODE (decl) == FUNCTION_DECL)
98 cgraph_mark_needed_node (cgraph_node (decl), 1);
100 else if (TREE_CODE (*tp) == CALL_EXPR)
102 tree decl = get_callee_fndecl (*tp);
103 if (decl && TREE_CODE (decl) == FUNCTION_DECL)
105 if (DECL_BUILT_IN (decl))
107 cgraph_record_call (data, decl);
109 /* When we see a function call, we don't want to look at the
110 function reference in the ADDR_EXPR that is hanging from
111 the CALL_EXPR we're examining here, because we would
112 conclude incorrectly that the function's address could be
113 taken by something that is not a function call. So only
114 walk the function parameter list, skip the other subtrees. */
116 walk_tree (&TREE_OPERAND (*tp, 1), record_call_1, data, NULL);
123 /* Create cgraph edges for function calls inside BODY from DECL. */
126 cgraph_create_edges (decl, body)
130 /* The nodes we're interested in are never shared, so walk
131 the tree ignoring duplicates. */
132 walk_tree_without_duplicates (&body, record_call_1, decl);
135 /* Analyze the whole compilation unit once it is parsed completely. */
138 cgraph_finalize_compilation_unit ()
140 struct cgraph_node *node;
141 struct cgraph_edge *edge;
143 cgraph_varpool_assemble_pending_decls ();
145 timevar_push (TV_CGRAPH);
146 if (cgraph_dump_file)
148 fprintf (cgraph_dump_file, "\nInitial entry points:");
149 for (node = cgraph_nodes; node; node = node->next)
150 if (node->needed && DECL_SAVED_TREE (node->decl))
151 fprintf (cgraph_dump_file, " %s", cgraph_node_name (node));
152 fprintf (cgraph_dump_file, "\n");
155 /* Propagate reachability flag and lower representation of all reachable
156 functions. In the future, lowering will introduce new functions and
157 new entry points on the way (by template instantiation and virtual
158 method table generation for instance). */
159 while (cgraph_nodes_queue)
161 tree decl = cgraph_nodes_queue->decl;
163 node = cgraph_nodes_queue;
164 cgraph_nodes_queue = cgraph_nodes_queue->next_needed;
166 if (node->lowered || !node->reachable || !DECL_SAVED_TREE (decl))
169 if (lang_hooks.callgraph.lower_function)
170 (*lang_hooks.callgraph.lower_function) (decl);
172 current_function_decl = node->decl;
173 if (!node->needed && !DECL_COMDAT (node->decl))
174 node->local.can_inline_once = tree_inlinable_function_p (decl, 1);
176 node->local.can_inline_once = 0;
177 if (flag_inline_trees)
178 node->local.inline_many = tree_inlinable_function_p (decl, 0);
180 node->local.inline_many = 0;
182 /* At the moment frontend automatically emits all nested functions. */
185 struct cgraph_node *node2;
187 for (node2 = node->nested; node2; node2 = node2->next_nested)
188 if (!node2->reachable)
189 cgraph_mark_needed_node (node2, 0);
192 /* First kill forward declaration so reverse inling works properly. */
193 cgraph_create_edges (decl, DECL_SAVED_TREE (decl));
195 for (edge = node->callees; edge; edge = edge->next_callee)
197 if (!edge->callee->reachable)
198 cgraph_mark_needed_node (edge->callee, 0);
200 node->lowered = true;
201 cgraph_varpool_assemble_pending_decls ();
203 /* Collect entry points to the unit. */
205 if (cgraph_dump_file)
207 fprintf (cgraph_dump_file, "\nUnit entry points:");
208 for (node = cgraph_nodes; node; node = node->next)
209 if (node->needed && DECL_SAVED_TREE (node->decl))
210 fprintf (cgraph_dump_file, " %s", cgraph_node_name (node));
211 fprintf (cgraph_dump_file, "\n");
214 if (cgraph_dump_file)
215 fprintf (cgraph_dump_file, "\nReclaiming functions:");
217 for (node = cgraph_nodes; node; node = node->next)
219 tree decl = node->decl;
221 if (!node->reachable && DECL_SAVED_TREE (decl))
223 cgraph_remove_node (node);
224 if (cgraph_dump_file)
225 fprintf (cgraph_dump_file, " %s", cgraph_node_name (node));
228 if (cgraph_dump_file)
229 fprintf (cgraph_dump_file, "\n");
231 timevar_pop (TV_CGRAPH);
234 /* Figure out what functions we want to assemble. */
237 cgraph_mark_functions_to_output ()
239 struct cgraph_node *node;
241 for (node = cgraph_nodes; node; node = node->next)
243 tree decl = node->decl;
245 /* We need to output all local functions that are used and not
246 always inlined, as well as those that are reachable from
247 outside the current compilation unit. */
248 if (DECL_SAVED_TREE (decl)
250 || (!node->local.inline_many && !node->global.inline_once
252 || (DECL_ASSEMBLER_NAME_SET_P (decl)
253 && TREE_SYMBOL_REFERENCED (DECL_ASSEMBLER_NAME (decl))))
254 && !TREE_ASM_WRITTEN (decl) && !node->origin
255 && !DECL_EXTERNAL (decl))
260 /* Optimize the function before expansion. */
263 cgraph_optimize_function (node)
264 struct cgraph_node *node;
266 tree decl = node->decl;
268 timevar_push (TV_INTEGRATION);
269 if (flag_inline_trees)
270 optimize_inline_calls (decl);
273 for (node = node->nested; node; node = node->next_nested)
274 cgraph_optimize_function (node);
276 timevar_pop (TV_INTEGRATION);
279 /* Expand function specified by NODE. */
282 cgraph_expand_function (node)
283 struct cgraph_node *node;
285 tree decl = node->decl;
287 announce_function (decl);
289 cgraph_optimize_function (node);
291 /* Generate RTL for the body of DECL. Nested functions are expanded
292 via lang_expand_decl_stmt. */
293 (*lang_hooks.callgraph.expand_function) (decl);
295 /* When we decided to inline the function once, we never ever should
296 need to output it separately. */
297 if (node->global.inline_once)
299 if (!node->local.inline_many
301 DECL_SAVED_TREE (decl) = NULL;
302 current_function_decl = NULL;
306 /* Expand all functions that must be output.
308 Attempt to topologically sort the nodes so function is output when
309 all called functions are already assembled to allow data to be
310 propagated across the callgraph. Use a stack to get smaller distance
311 between a function and it's callees (later we may choose to use a more
312 sophisticated algorithm for function reordering; we will likely want
313 to use subsections to make the output functions appear in top-down
317 cgraph_expand_functions ()
319 struct cgraph_node *node, *node2;
320 struct cgraph_node **stack =
321 xcalloc (sizeof (struct cgraph_node *), cgraph_n_nodes);
322 struct cgraph_node **order =
323 xcalloc (sizeof (struct cgraph_node *), cgraph_n_nodes);
326 struct cgraph_edge *edge, last;
329 cgraph_mark_functions_to_output ();
331 /* We have to deal with cycles nicely, so use a depth first traversal
332 output algorithm. Ignore the fact that some functions won't need
333 to be output and put them into order as well, so we get dependencies
334 right through intline functions. */
335 for (node = cgraph_nodes; node; node = node->next)
337 for (node = cgraph_nodes; node; node = node->next)
344 node->aux = node->callers;
347 while (node2->aux != &last)
350 if (edge->next_caller)
351 node2->aux = edge->next_caller;
354 if (!edge->caller->aux)
356 if (!edge->caller->callers)
357 edge->caller->aux = &last;
359 edge->caller->aux = edge->caller->callers;
360 stack[stack_size++] = node2;
361 node2 = edge->caller;
365 if (node2->aux == &last)
367 order[order_pos++] = node2;
369 node2 = stack[--stack_size];
375 for (i = order_pos - 1; i >= 0; i--)
380 if (!node->reachable)
383 cgraph_expand_function (node);
390 /* Mark all local functions.
391 We can not use node->needed directly as it is modified during
392 execution of cgraph_optimize. */
395 cgraph_mark_local_functions ()
397 struct cgraph_node *node;
399 if (cgraph_dump_file)
400 fprintf (cgraph_dump_file, "Marking local functions:");
402 /* Figure out functions we want to assemble. */
403 for (node = cgraph_nodes; node; node = node->next)
405 node->local.local = (!node->needed
406 && DECL_SAVED_TREE (node->decl)
407 && !DECL_COMDAT (node->decl)
408 && !TREE_PUBLIC (node->decl));
409 if (cgraph_dump_file && node->local.local)
410 fprintf (cgraph_dump_file, " %s", cgraph_node_name (node));
412 if (cgraph_dump_file)
413 fprintf (cgraph_dump_file, "\n");
416 /* Decide what function should be inlined because they are invoked once
417 (so inlining won't result in duplication of the code). */
420 cgraph_mark_functions_to_inline_once ()
422 struct cgraph_node *node, *node1;
424 if (cgraph_dump_file)
425 fprintf (cgraph_dump_file, "\n\nMarking functions to inline once:");
427 /* Now look for function called only once and mark them to inline.
428 From this point number of calls to given function won't grow. */
429 for (node = cgraph_nodes; node; node = node->next)
431 if (node->callers && !node->callers->next_caller && !node->needed
432 && node->local.can_inline_once)
436 /* Verify that we won't duplicate the caller. */
437 for (node1 = node->callers->caller;
438 node1->local.inline_many
441 node1 = node1->callers->caller)
442 if (node1->callers->next_caller || node1->needed)
446 node->global.inline_once = true;
447 if (cgraph_dump_file)
448 fprintf (cgraph_dump_file, " %s", cgraph_node_name (node));
452 if (cgraph_dump_file)
453 fprintf (cgraph_dump_file, "\n");
457 /* Perform simple optimizations based on callgraph. */
462 struct cgraph_node *node;
465 timevar_push (TV_CGRAPHOPT);
466 if (cgraph_dump_file)
468 fprintf (cgraph_dump_file, "Initial callgraph:");
469 dump_cgraph (cgraph_dump_file);
471 cgraph_mark_local_functions ();
473 cgraph_mark_functions_to_inline_once ();
475 cgraph_global_info_ready = true;
476 if (cgraph_dump_file)
478 fprintf (cgraph_dump_file, "Optimized callgraph:");
479 dump_cgraph (cgraph_dump_file);
481 timevar_pop (TV_CGRAPHOPT);
483 fprintf (stderr, "\n\nAssembling functions:");
485 /* Output everything.
486 ??? Our inline heuristic may decide to not inline functions previously
487 marked as inlinable thus adding new function bodies that must be output.
488 Later we should move all inlining decisions to callgraph code to make
490 cgraph_expand_functions ();
492 fprintf (stderr, "\n\nAssembling functions that failed to inline:");
493 while (changed && !errorcount && !sorrycount)
496 for (node = cgraph_nodes; node; node = node->next)
498 tree decl = node->decl;
500 && !TREE_ASM_WRITTEN (decl)
501 && DECL_SAVED_TREE (decl)
502 && !DECL_EXTERNAL (decl))
504 struct cgraph_edge *edge;
506 for (edge = node->callers; edge; edge = edge->next_caller)
507 if (TREE_ASM_WRITTEN (edge->caller->decl))
510 cgraph_expand_function (node);
516 if (cgraph_dump_file)
518 fprintf (cgraph_dump_file, "Final callgraph:");
519 dump_cgraph (cgraph_dump_file);