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"
38 static void cgraph_expand_functions
PARAMS ((void));
39 static void cgraph_mark_functions_to_output
PARAMS ((void));
40 static void cgraph_expand_function
PARAMS ((struct cgraph_node
*));
41 static tree record_call_1
PARAMS ((tree
*, int *, void *));
42 static void cgraph_mark_local_functions
PARAMS ((void));
43 static void cgraph_mark_functions_to_inline_once
PARAMS ((void));
44 static void cgraph_optimize_function
PARAMS ((struct cgraph_node
*));
46 /* Analyze function once it is parsed. Set up the local information
47 available - create cgraph edges for function calles via BODY. */
50 cgraph_finalize_function (decl
, body
)
52 tree body ATTRIBUTE_UNUSED
;
54 struct cgraph_node
*node
= cgraph_node (decl
);
58 node
->local
.can_inline_once
= tree_inlinable_function_p (decl
, 1);
59 if (flag_inline_trees
)
60 node
->local
.inline_many
= tree_inlinable_function_p (decl
, 0);
62 node
->local
.inline_many
= 0;
64 (*debug_hooks
->deferred_inline_function
) (decl
);
67 static struct cgraph_node
*queue
= NULL
;
69 /* Notify finalize_compilation_unit that given node is reachable
72 cgraph_mark_needed_node (node
, needed
)
73 struct cgraph_node
*node
;
78 if (DECL_SAVED_TREE (node
->decl
))
79 announce_function (node
->decl
);
85 if (DECL_SAVED_TREE (node
->decl
))
93 /* Walk tree and record all calls. Called via walk_tree. */
95 record_call_1 (tp
, walk_subtrees
, data
)
100 /* Record dereferences to the functions. This makes the functions
101 reachable unconditionally. */
102 if (TREE_CODE (*tp
) == ADDR_EXPR
)
104 tree decl
= TREE_OPERAND (*tp
, 0);
105 if (TREE_CODE (decl
) == FUNCTION_DECL
)
106 cgraph_mark_needed_node (cgraph_node (decl
), 1);
108 else if (TREE_CODE (*tp
) == CALL_EXPR
)
110 tree decl
= TREE_OPERAND (*tp
, 0);
111 if (TREE_CODE (decl
) == ADDR_EXPR
)
112 decl
= TREE_OPERAND (decl
, 0);
113 if (TREE_CODE (decl
) == FUNCTION_DECL
)
115 if (DECL_BUILT_IN (decl
))
117 cgraph_record_call (data
, decl
);
118 walk_tree (&TREE_OPERAND (*tp
, 1), record_call_1
, data
, NULL
);
125 /* Create cgraph edges for function calles via BODY. */
128 cgraph_create_edges (decl
, body
)
132 walk_tree (&body
, record_call_1
, decl
, NULL
);
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 /* Collect entry points to the unit. */
146 fprintf (stderr
, "\n\nUnit entry points:");
148 for (node
= cgraph_nodes
; node
; node
= node
->next
)
150 tree decl
= node
->decl
;
152 if (!DECL_SAVED_TREE (decl
))
154 if ((TREE_PUBLIC (decl
) && !DECL_COMDAT (decl
) && !DECL_EXTERNAL (decl
))
155 || (DECL_ASSEMBLER_NAME_SET_P (decl
)
156 && TREE_SYMBOL_REFERENCED (DECL_ASSEMBLER_NAME (decl
))))
158 cgraph_mark_needed_node (node
, 1);
162 /* Propagate reachability flag and lower representation of all reachable
163 functions. In the future, lowering will introduce new functions and
164 new entry points on the way (by template instantiation and virtual
165 method table generation for instance). */
168 tree decl
= queue
->decl
;
172 if (node
->lowered
|| !node
->reachable
|| !DECL_SAVED_TREE (decl
))
175 /* At the moment frontend automatically emits all nested functions. */
178 struct cgraph_node
*node2
;
180 for (node2
= node
->nested
; node2
; node2
= node2
->next_nested
)
181 if (!node2
->reachable
)
182 cgraph_mark_needed_node (node2
, 0);
185 if (lang_hooks
.callgraph
.lower_function
)
186 (*lang_hooks
.callgraph
.lower_function
) (decl
);
187 /* First kill forward declaration so reverse inling works properly. */
188 cgraph_create_edges (decl
, DECL_SAVED_TREE (decl
));
190 for (edge
= node
->callees
; edge
; edge
= edge
->next_callee
)
192 if (!edge
->callee
->reachable
)
193 cgraph_mark_needed_node (edge
->callee
, 0);
195 node
->lowered
= true;
198 fprintf (stderr
, "\n\nReclaiming functions:");
200 for (node
= cgraph_nodes
; node
; node
= node
->next
)
202 tree decl
= node
->decl
;
204 if (!node
->reachable
&& DECL_SAVED_TREE (decl
))
206 cgraph_remove_node (node
);
207 announce_function (decl
);
213 /* Figure out what functions we want to assemble. */
216 cgraph_mark_functions_to_output ()
218 struct cgraph_node
*node
;
220 /* Figure out functions we want to assemble. */
221 for (node
= cgraph_nodes
; node
; node
= node
->next
)
223 tree decl
= node
->decl
;
225 if (DECL_SAVED_TREE (decl
)
227 || (!node
->local
.inline_many
&& !node
->global
.inline_once
229 || TREE_SYMBOL_REFERENCED (DECL_ASSEMBLER_NAME (decl
)))
230 && !TREE_ASM_WRITTEN (decl
) && !node
->origin
231 && !DECL_EXTERNAL (decl
))
236 /* Optimize the function before expansion. */
238 cgraph_optimize_function (node
)
239 struct cgraph_node
*node
;
241 tree decl
= node
->decl
;
243 if (flag_inline_trees
)
244 optimize_inline_calls (decl
);
247 for (node
= node
->nested
; node
; node
= node
->next_nested
)
248 cgraph_optimize_function (node
);
252 /* Expand function specified by NODE. */
254 cgraph_expand_function (node
)
255 struct cgraph_node
*node
;
257 tree decl
= node
->decl
;
259 announce_function (decl
);
261 cgraph_optimize_function (node
);
263 /* Avoid RTL inlining from taking place. */
264 (*lang_hooks
.callgraph
.expand_function
) (decl
);
266 /* When we decided to inline the function once, we never ever should need to
267 output it separately. */
268 if (node
->global
.inline_once
)
270 if (!node
->local
.inline_many
272 DECL_SAVED_TREE (decl
) = NULL
;
273 current_function_decl
= NULL
;
277 /* Expand all functions that must be output.
279 Attempt to topologically sort the nodes so function is output when
280 all called functions are already assembled to allow data to be propagated
281 accross the callgraph. Use stack to get smaller distance between function
282 and it's callees (later we may use more sophisticated algorithm for
283 function reordering, we will likely want to use subsections to make output
284 functions to appear in top-down order, not bottom-up they are assembled). */
287 cgraph_expand_functions ()
289 struct cgraph_node
*node
, *node2
;
290 struct cgraph_node
**stack
=
291 xcalloc (sizeof (struct cgraph_node
*), cgraph_n_nodes
);
292 struct cgraph_node
**order
=
293 xcalloc (sizeof (struct cgraph_node
*), cgraph_n_nodes
);
296 struct cgraph_edge
*edge
, last
;
299 cgraph_mark_functions_to_output ();
301 /* We have to deal with cycles nicely, so use depth first traversal
302 algorithm. Ignore the fact that some functions won't need to be output
303 and put them into order as well, so we get dependencies right trought inlined
305 for (node
= cgraph_nodes
; node
; node
= node
->next
)
307 for (node
= cgraph_nodes
; node
; node
= node
->next
)
308 if (node
->output
&& !node
->aux
)
314 node
->aux
= node
->callers
;
317 while (node2
->aux
!= &last
)
320 if (edge
->next_caller
)
321 node2
->aux
= edge
->next_caller
;
324 if (!edge
->caller
->aux
)
326 if (!edge
->caller
->callers
)
327 edge
->caller
->aux
= &last
;
329 edge
->caller
->aux
= edge
->caller
->callers
;
330 stack
[stack_size
++] = node2
;
331 node2
= edge
->caller
;
335 if (node2
->aux
== &last
)
337 order
[order_pos
++] = node2
;
339 node2
= stack
[--stack_size
];
345 for (i
= order_pos
- 1; i
>= 0; i
--)
350 if (!node
->reachable
)
353 cgraph_expand_function (node
);
360 /* Mark all local functions.
361 We can not use node->needed directly as it is modified during
362 execution of cgraph_optimize. */
365 cgraph_mark_local_functions ()
367 struct cgraph_node
*node
;
370 fprintf (stderr
, "\n\nMarking local functions:");
372 /* Figure out functions we want to assemble. */
373 for (node
= cgraph_nodes
; node
; node
= node
->next
)
375 node
->local
.local
= (!node
->needed
376 && DECL_SAVED_TREE (node
->decl
)
377 && !TREE_PUBLIC (node
->decl
));
378 if (node
->local
.local
)
379 announce_function (node
->decl
);
383 /* Decide what function should be inlined because they are invoked once
384 (so inlining won't result in duplication of the code). */
387 cgraph_mark_functions_to_inline_once ()
389 struct cgraph_node
*node
, *node1
;
392 fprintf (stderr
, "\n\nMarking functions to inline once:");
394 /* Now look for function called only once and mark them to inline. From this
395 point number of calls to given function won't grow. */
396 for (node
= cgraph_nodes
; node
; node
= node
->next
)
398 if (node
->callers
&& !node
->callers
->next_caller
&& !node
->needed
399 && node
->local
.can_inline_once
)
403 /* Verify that we won't duplicate the caller. */
404 for (node1
= node
->callers
->caller
;
405 node1
->local
.inline_many
408 node1
= node1
->callers
->caller
)
409 if (node1
->callers
->next_caller
|| node1
->needed
)
413 node
->global
.inline_once
= true;
414 announce_function (node
->decl
);
421 /* Perform simple optimizations based on callgraph. */
426 struct cgraph_node
*node
;
429 cgraph_mark_local_functions ();
431 cgraph_mark_functions_to_inline_once ();
433 cgraph_global_info_ready
= true;
435 fprintf (stderr
, "\n\nAssembling functions:");
437 /* Output everything.
438 ??? Our inline heuristic may decide to not inline functions previously
439 marked as inlinable thus adding new function bodies that must be output.
440 Later we should move all inlining decisions to callgraph code to make
442 cgraph_expand_functions ();
444 fprintf (stderr
, "\n\nAssembling functions that failed to inline:");
445 while (changed
&& !errorcount
&& !sorrycount
)
448 for (node
= cgraph_nodes
; node
; node
= node
->next
)
450 tree decl
= node
->decl
;
452 && !TREE_ASM_WRITTEN (decl
)
453 && DECL_SAVED_TREE (decl
)
454 && !DECL_EXTERNAL (decl
))
456 struct cgraph_edge
*edge
;
458 for (edge
= node
->callers
; edge
; edge
= edge
->next_caller
)
459 if (TREE_ASM_WRITTEN (edge
->caller
->decl
))
462 cgraph_expand_function (node
);