1 /* Callgraph construction.
2 Copyright (C) 2003, 2004, 2005, 2006, 2007, 2008, 2009
3 Free Software Foundation, Inc.
4 Contributed by Jan Hubicka
6 This file is part of GCC.
8 GCC is free software; you can redistribute it and/or modify it under
9 the terms of the GNU General Public License as published by the Free
10 Software Foundation; either version 3, or (at your option) any later
13 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
14 WARRANTY; without even the implied warranty of MERCHANTABILITY or
15 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
18 You should have received a copy of the GNU General Public License
19 along with GCC; see the file COPYING3. If not see
20 <http://www.gnu.org/licenses/>. */
24 #include "coretypes.h"
27 #include "tree-flow.h"
28 #include "langhooks.h"
29 #include "pointer-set.h"
33 #include "tree-pass.h"
34 #include "ipa-utils.h"
36 /* Context of record_reference. */
37 struct record_reference_ctx
42 /* Walk tree and record all calls and references to functions/variables.
43 Called via walk_tree: TP is pointer to tree to be examined.
44 When DATA is non-null, record references to callgraph.
48 record_reference (tree
*tp
, int *walk_subtrees
, void *data
)
52 struct record_reference_ctx
*ctx
= (struct record_reference_ctx
*)data
;
54 switch (TREE_CODE (t
))
63 /* Record dereferences to the functions. This makes the
64 functions reachable unconditionally. */
65 decl
= get_base_var (*tp
);
66 if (TREE_CODE (decl
) == FUNCTION_DECL
&& !ctx
->only_vars
)
67 cgraph_mark_address_taken_node (cgraph_node (decl
));
69 if (TREE_CODE (decl
) == VAR_DECL
)
71 gcc_assert (TREE_STATIC (decl
) || DECL_EXTERNAL (decl
));
72 if (lang_hooks
.callgraph
.analyze_expr
)
73 lang_hooks
.callgraph
.analyze_expr (&decl
, walk_subtrees
);
74 varpool_mark_needed_node (varpool_node (decl
));
80 /* Save some cycles by not walking types and declaration as we
81 won't find anything useful there anyway. */
82 if (IS_TYPE_OR_DECL_P (*tp
))
88 if ((unsigned int) TREE_CODE (t
) >= LAST_AND_UNUSED_TREE_CODE
)
89 return lang_hooks
.callgraph
.analyze_expr (tp
, walk_subtrees
);
96 /* Reset inlining information of all incoming call edges of NODE. */
99 reset_inline_failed (struct cgraph_node
*node
)
101 struct cgraph_edge
*e
;
103 for (e
= node
->callers
; e
; e
= e
->next_caller
)
105 e
->callee
->global
.inlined_to
= NULL
;
107 e
->inline_failed
= CIF_BODY_NOT_AVAILABLE
;
108 else if (node
->local
.redefined_extern_inline
)
109 e
->inline_failed
= CIF_REDEFINED_EXTERN_INLINE
;
110 else if (!node
->local
.inlinable
)
111 e
->inline_failed
= CIF_FUNCTION_NOT_INLINABLE
;
112 else if (e
->call_stmt_cannot_inline_p
)
113 e
->inline_failed
= CIF_MISMATCHED_ARGUMENTS
;
115 e
->inline_failed
= CIF_FUNCTION_NOT_CONSIDERED
;
119 /* Computes the frequency of the call statement so that it can be stored in
120 cgraph_edge. BB is the basic block of the call statement. */
122 compute_call_stmt_bb_frequency (tree decl
, basic_block bb
)
124 int entry_freq
= ENTRY_BLOCK_PTR_FOR_FUNCTION
125 (DECL_STRUCT_FUNCTION (decl
))->frequency
;
126 int freq
= bb
->frequency
;
128 if (profile_status_for_function (DECL_STRUCT_FUNCTION (decl
)) == PROFILE_ABSENT
)
129 return CGRAPH_FREQ_BASE
;
132 entry_freq
= 1, freq
++;
134 freq
= freq
* CGRAPH_FREQ_BASE
/ entry_freq
;
135 if (freq
> CGRAPH_FREQ_MAX
)
136 freq
= CGRAPH_FREQ_MAX
;
141 /* Mark address taken in STMT. */
144 mark_address (gimple stmt ATTRIBUTE_UNUSED
, tree addr
,
145 void *data ATTRIBUTE_UNUSED
)
147 if (TREE_CODE (addr
) == FUNCTION_DECL
)
149 struct cgraph_node
*node
= cgraph_node (addr
);
150 cgraph_mark_address_taken_node (node
);
154 addr
= get_base_address (addr
);
155 if (addr
&& TREE_CODE (addr
) == VAR_DECL
156 && (TREE_STATIC (addr
) || DECL_EXTERNAL (addr
)))
158 struct varpool_node
*vnode
= varpool_node (addr
);
161 if (lang_hooks
.callgraph
.analyze_expr
)
162 lang_hooks
.callgraph
.analyze_expr (&addr
, &walk_subtrees
);
163 varpool_mark_needed_node (vnode
);
170 /* Mark load of T. */
173 mark_load (gimple stmt ATTRIBUTE_UNUSED
, tree t
,
174 void *data ATTRIBUTE_UNUSED
)
176 t
= get_base_address (t
);
177 if (TREE_CODE (t
) == VAR_DECL
178 && (TREE_STATIC (t
) || DECL_EXTERNAL (t
)))
180 struct varpool_node
*vnode
= varpool_node (t
);
183 if (lang_hooks
.callgraph
.analyze_expr
)
184 lang_hooks
.callgraph
.analyze_expr (&t
, &walk_subtrees
);
185 varpool_mark_needed_node (vnode
);
190 /* Mark store of T. */
193 mark_store (gimple stmt ATTRIBUTE_UNUSED
, tree t
,
194 void *data ATTRIBUTE_UNUSED
)
196 t
= get_base_address (t
);
197 if (TREE_CODE (t
) == VAR_DECL
198 && (TREE_STATIC (t
) || DECL_EXTERNAL (t
)))
200 struct varpool_node
*vnode
= varpool_node (t
);
203 if (lang_hooks
.callgraph
.analyze_expr
)
204 lang_hooks
.callgraph
.analyze_expr (&t
, &walk_subtrees
);
205 varpool_mark_needed_node (vnode
);
210 /* Create cgraph edges for function calls.
211 Also look for functions and variables having addresses taken. */
214 build_cgraph_edges (void)
217 struct cgraph_node
*node
= cgraph_node (current_function_decl
);
218 struct pointer_set_t
*visited_nodes
= pointer_set_create ();
219 gimple_stmt_iterator gsi
;
222 /* Create the callgraph edges and record the nodes referenced by the function.
226 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
228 gimple stmt
= gsi_stmt (gsi
);
231 if (is_gimple_call (stmt
) && (decl
= gimple_call_fndecl (stmt
)))
232 cgraph_create_edge (node
, cgraph_node (decl
), stmt
,
234 compute_call_stmt_bb_frequency
235 (current_function_decl
, bb
),
237 walk_stmt_load_store_addr_ops (stmt
, node
, mark_load
,
238 mark_store
, mark_address
);
239 if (gimple_code (stmt
) == GIMPLE_OMP_PARALLEL
240 && gimple_omp_parallel_child_fn (stmt
))
242 tree fn
= gimple_omp_parallel_child_fn (stmt
);
243 cgraph_mark_needed_node (cgraph_node (fn
));
245 if (gimple_code (stmt
) == GIMPLE_OMP_TASK
)
247 tree fn
= gimple_omp_task_child_fn (stmt
);
249 cgraph_mark_needed_node (cgraph_node (fn
));
250 fn
= gimple_omp_task_copy_fn (stmt
);
252 cgraph_mark_needed_node (cgraph_node (fn
));
255 for (gsi
= gsi_start (phi_nodes (bb
)); !gsi_end_p (gsi
); gsi_next (&gsi
))
256 walk_stmt_load_store_addr_ops (gsi_stmt (gsi
), node
,
257 mark_load
, mark_store
, mark_address
);
260 /* Look for initializers of constant variables and private statics. */
261 for (step
= cfun
->local_decls
;
263 step
= TREE_CHAIN (step
))
265 tree decl
= TREE_VALUE (step
);
266 if (TREE_CODE (decl
) == VAR_DECL
267 && (TREE_STATIC (decl
) && !DECL_EXTERNAL (decl
)))
268 varpool_finalize_decl (decl
);
271 pointer_set_destroy (visited_nodes
);
275 struct gimple_opt_pass pass_build_cgraph_edges
=
279 "*build_cgraph_edges", /* name */
281 build_cgraph_edges
, /* execute */
284 0, /* static_pass_number */
286 PROP_cfg
, /* properties_required */
287 0, /* properties_provided */
288 0, /* properties_destroyed */
289 0, /* todo_flags_start */
290 0 /* todo_flags_finish */
294 /* Record references to functions and other variables present in the
295 initial value of DECL, a variable.
296 When ONLY_VARS is true, we mark needed only variables, not functions. */
299 record_references_in_initializer (tree decl
, bool only_vars
)
301 struct pointer_set_t
*visited_nodes
= pointer_set_create ();
302 struct record_reference_ctx ctx
= {false};
304 ctx
.only_vars
= only_vars
;
305 walk_tree (&DECL_INITIAL (decl
), record_reference
,
306 &ctx
, visited_nodes
);
307 pointer_set_destroy (visited_nodes
);
310 /* Rebuild cgraph edges for current function node. This needs to be run after
311 passes that don't update the cgraph. */
314 rebuild_cgraph_edges (void)
317 struct cgraph_node
*node
= cgraph_node (current_function_decl
);
318 gimple_stmt_iterator gsi
;
320 cgraph_node_remove_callees (node
);
322 node
->count
= ENTRY_BLOCK_PTR
->count
;
326 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
328 gimple stmt
= gsi_stmt (gsi
);
331 if (is_gimple_call (stmt
) && (decl
= gimple_call_fndecl (stmt
)))
332 cgraph_create_edge (node
, cgraph_node (decl
), stmt
,
334 compute_call_stmt_bb_frequency
335 (current_function_decl
, bb
),
337 walk_stmt_load_store_addr_ops (stmt
, node
, mark_load
,
338 mark_store
, mark_address
);
341 for (gsi
= gsi_start (phi_nodes (bb
)); !gsi_end_p (gsi
); gsi_next (&gsi
))
342 walk_stmt_load_store_addr_ops (gsi_stmt (gsi
), node
,
343 mark_load
, mark_store
, mark_address
);
345 gcc_assert (!node
->global
.inlined_to
);
350 struct gimple_opt_pass pass_rebuild_cgraph_edges
=
354 "*rebuild_cgraph_edges", /* name */
356 rebuild_cgraph_edges
, /* execute */
359 0, /* static_pass_number */
361 PROP_cfg
, /* properties_required */
362 0, /* properties_provided */
363 0, /* properties_destroyed */
364 0, /* todo_flags_start */
365 0, /* todo_flags_finish */
371 remove_cgraph_callee_edges (void)
373 cgraph_node_remove_callees (cgraph_node (current_function_decl
));
377 struct gimple_opt_pass pass_remove_cgraph_callee_edges
=
381 "*remove_cgraph_callee_edges", /* name */
383 remove_cgraph_callee_edges
, /* execute */
386 0, /* static_pass_number */
388 0, /* properties_required */
389 0, /* properties_provided */
390 0, /* properties_destroyed */
391 0, /* todo_flags_start */
392 0, /* todo_flags_finish */