1 /* Callgraph construction.
2 Copyright (C) 2003, 2004, 2005, 2006, 2007, 2008, 2009, 2010
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"
37 /* Context of record_reference. */
38 struct record_reference_ctx
41 struct varpool_node
*varpool_node
;
44 /* Walk tree and record all calls and references to functions/variables.
45 Called via walk_tree: TP is pointer to tree to be examined.
46 When DATA is non-null, record references to callgraph.
50 record_reference (tree
*tp
, int *walk_subtrees
, void *data
)
54 struct record_reference_ctx
*ctx
= (struct record_reference_ctx
*)data
;
56 t
= canonicalize_constructor_val (t
);
62 switch (TREE_CODE (t
))
71 /* Record dereferences to the functions. This makes the
72 functions reachable unconditionally. */
73 decl
= get_base_var (*tp
);
74 if (TREE_CODE (decl
) == FUNCTION_DECL
)
77 cgraph_mark_address_taken_node (cgraph_node (decl
));
78 ipa_record_reference (NULL
, ctx
->varpool_node
,
79 cgraph_node (decl
), NULL
,
83 if (TREE_CODE (decl
) == VAR_DECL
)
85 struct varpool_node
*vnode
= varpool_node (decl
);
86 if (lang_hooks
.callgraph
.analyze_expr
)
87 lang_hooks
.callgraph
.analyze_expr (&decl
, walk_subtrees
);
88 varpool_mark_needed_node (vnode
);
89 if (vnode
->alias
&& vnode
->extra_name
)
90 vnode
= vnode
->extra_name
;
91 ipa_record_reference (NULL
, ctx
->varpool_node
,
99 /* Save some cycles by not walking types and declaration as we
100 won't find anything useful there anyway. */
101 if (IS_TYPE_OR_DECL_P (*tp
))
107 if ((unsigned int) TREE_CODE (t
) >= LAST_AND_UNUSED_TREE_CODE
)
108 return lang_hooks
.callgraph
.analyze_expr (tp
, walk_subtrees
);
115 /* Record references to typeinfos in the type list LIST. */
118 record_type_list (struct cgraph_node
*node
, tree list
)
120 for (; list
; list
= TREE_CHAIN (list
))
122 tree type
= TREE_VALUE (list
);
125 type
= lookup_type_for_runtime (type
);
127 if (TREE_CODE (type
) == ADDR_EXPR
)
129 type
= TREE_OPERAND (type
, 0);
130 if (TREE_CODE (type
) == VAR_DECL
)
132 struct varpool_node
*vnode
= varpool_node (type
);
133 varpool_mark_needed_node (vnode
);
134 ipa_record_reference (node
, NULL
,
142 /* Record all references we will introduce by producing EH tables
146 record_eh_tables (struct cgraph_node
*node
, struct function
*fun
)
150 if (DECL_FUNCTION_PERSONALITY (node
->decl
))
151 ipa_record_reference (node
, NULL
,
152 cgraph_node (DECL_FUNCTION_PERSONALITY (node
->decl
)),
153 NULL
, IPA_REF_ADDR
, NULL
);
155 i
= fun
->eh
->region_tree
;
164 case ERT_MUST_NOT_THROW
:
170 for (c
= i
->u
.eh_try
.first_catch
; c
; c
= c
->next_catch
)
171 record_type_list (node
, c
->type_list
);
175 case ERT_ALLOWED_EXCEPTIONS
:
176 record_type_list (node
, i
->u
.allowed
.type_list
);
179 /* If there are sub-regions, process them. */
182 /* If there are peers, process them. */
183 else if (i
->next_peer
)
185 /* Otherwise, step back up the tree to the next peer. */
194 while (i
->next_peer
== NULL
);
200 /* Reset inlining information of all incoming call edges of NODE. */
203 reset_inline_failed (struct cgraph_node
*node
)
205 struct cgraph_edge
*e
;
207 for (e
= node
->callers
; e
; e
= e
->next_caller
)
209 e
->callee
->global
.inlined_to
= NULL
;
211 e
->inline_failed
= CIF_BODY_NOT_AVAILABLE
;
212 else if (node
->local
.redefined_extern_inline
)
213 e
->inline_failed
= CIF_REDEFINED_EXTERN_INLINE
;
214 else if (!node
->local
.inlinable
)
215 e
->inline_failed
= CIF_FUNCTION_NOT_INLINABLE
;
216 else if (e
->call_stmt_cannot_inline_p
)
217 e
->inline_failed
= CIF_MISMATCHED_ARGUMENTS
;
219 e
->inline_failed
= CIF_FUNCTION_NOT_CONSIDERED
;
223 /* Computes the frequency of the call statement so that it can be stored in
224 cgraph_edge. BB is the basic block of the call statement. */
226 compute_call_stmt_bb_frequency (tree decl
, basic_block bb
)
228 int entry_freq
= ENTRY_BLOCK_PTR_FOR_FUNCTION
229 (DECL_STRUCT_FUNCTION (decl
))->frequency
;
230 int freq
= bb
->frequency
;
232 if (profile_status_for_function (DECL_STRUCT_FUNCTION (decl
)) == PROFILE_ABSENT
)
233 return CGRAPH_FREQ_BASE
;
236 entry_freq
= 1, freq
++;
238 freq
= freq
* CGRAPH_FREQ_BASE
/ entry_freq
;
239 if (freq
> CGRAPH_FREQ_MAX
)
240 freq
= CGRAPH_FREQ_MAX
;
245 /* Mark address taken in STMT. */
248 mark_address (gimple stmt
, tree addr
, void *data
)
250 addr
= get_base_address (addr
);
251 if (TREE_CODE (addr
) == FUNCTION_DECL
)
253 struct cgraph_node
*node
= cgraph_node (addr
);
254 cgraph_mark_address_taken_node (node
);
255 ipa_record_reference ((struct cgraph_node
*)data
, NULL
,
259 else if (addr
&& TREE_CODE (addr
) == VAR_DECL
260 && (TREE_STATIC (addr
) || DECL_EXTERNAL (addr
)))
262 struct varpool_node
*vnode
= varpool_node (addr
);
265 if (lang_hooks
.callgraph
.analyze_expr
)
266 lang_hooks
.callgraph
.analyze_expr (&addr
, &walk_subtrees
);
267 varpool_mark_needed_node (vnode
);
268 if (vnode
->alias
&& vnode
->extra_name
)
269 vnode
= vnode
->extra_name
;
270 ipa_record_reference ((struct cgraph_node
*)data
, NULL
,
278 /* Mark load of T. */
281 mark_load (gimple stmt
, tree t
, void *data
)
283 t
= get_base_address (t
);
284 if (t
&& TREE_CODE (t
) == FUNCTION_DECL
)
286 /* ??? This can happen on platforms with descriptors when these are
287 directly manipulated in the code. Pretend that it's an address. */
288 struct cgraph_node
*node
= cgraph_node (t
);
289 cgraph_mark_address_taken_node (node
);
290 ipa_record_reference ((struct cgraph_node
*)data
, NULL
,
294 else if (t
&& TREE_CODE (t
) == VAR_DECL
295 && (TREE_STATIC (t
) || DECL_EXTERNAL (t
)))
297 struct varpool_node
*vnode
= varpool_node (t
);
300 if (lang_hooks
.callgraph
.analyze_expr
)
301 lang_hooks
.callgraph
.analyze_expr (&t
, &walk_subtrees
);
302 varpool_mark_needed_node (vnode
);
303 if (vnode
->alias
&& vnode
->extra_name
)
304 vnode
= vnode
->extra_name
;
305 ipa_record_reference ((struct cgraph_node
*)data
, NULL
,
312 /* Mark store of T. */
315 mark_store (gimple stmt
, tree t
, void *data
)
317 t
= get_base_address (t
);
318 if (t
&& TREE_CODE (t
) == VAR_DECL
319 && (TREE_STATIC (t
) || DECL_EXTERNAL (t
)))
321 struct varpool_node
*vnode
= varpool_node (t
);
324 if (lang_hooks
.callgraph
.analyze_expr
)
325 lang_hooks
.callgraph
.analyze_expr (&t
, &walk_subtrees
);
326 varpool_mark_needed_node (vnode
);
327 if (vnode
->alias
&& vnode
->extra_name
)
328 vnode
= vnode
->extra_name
;
329 ipa_record_reference ((struct cgraph_node
*)data
, NULL
,
331 IPA_REF_STORE
, stmt
);
336 /* Create cgraph edges for function calls.
337 Also look for functions and variables having addresses taken. */
340 build_cgraph_edges (void)
343 struct cgraph_node
*node
= cgraph_node (current_function_decl
);
344 struct pointer_set_t
*visited_nodes
= pointer_set_create ();
345 gimple_stmt_iterator gsi
;
349 /* Create the callgraph edges and record the nodes referenced by the function.
353 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
355 gimple stmt
= gsi_stmt (gsi
);
358 if (is_gimple_call (stmt
))
360 int freq
= compute_call_stmt_bb_frequency (current_function_decl
,
362 decl
= gimple_call_fndecl (stmt
);
364 cgraph_create_edge (node
, cgraph_node (decl
), stmt
,
368 cgraph_create_indirect_edge (node
, stmt
,
369 gimple_call_flags (stmt
),
373 walk_stmt_load_store_addr_ops (stmt
, node
, mark_load
,
374 mark_store
, mark_address
);
375 if (gimple_code (stmt
) == GIMPLE_OMP_PARALLEL
376 && gimple_omp_parallel_child_fn (stmt
))
378 tree fn
= gimple_omp_parallel_child_fn (stmt
);
379 ipa_record_reference (node
, NULL
, cgraph_node (fn
),
380 NULL
, IPA_REF_ADDR
, stmt
);
382 if (gimple_code (stmt
) == GIMPLE_OMP_TASK
)
384 tree fn
= gimple_omp_task_child_fn (stmt
);
386 ipa_record_reference (node
, NULL
, cgraph_node (fn
),
387 NULL
, IPA_REF_ADDR
, stmt
);
388 fn
= gimple_omp_task_copy_fn (stmt
);
390 ipa_record_reference (node
, NULL
, cgraph_node (fn
),
391 NULL
, IPA_REF_ADDR
, stmt
);
394 for (gsi
= gsi_start (phi_nodes (bb
)); !gsi_end_p (gsi
); gsi_next (&gsi
))
395 walk_stmt_load_store_addr_ops (gsi_stmt (gsi
), node
,
396 mark_load
, mark_store
, mark_address
);
399 /* Look for initializers of constant variables and private statics. */
400 FOR_EACH_LOCAL_DECL (cfun
, ix
, decl
)
401 if (TREE_CODE (decl
) == VAR_DECL
402 && (TREE_STATIC (decl
) && !DECL_EXTERNAL (decl
)))
403 varpool_finalize_decl (decl
);
404 record_eh_tables (node
, cfun
);
406 pointer_set_destroy (visited_nodes
);
410 struct gimple_opt_pass pass_build_cgraph_edges
=
414 "*build_cgraph_edges", /* name */
416 build_cgraph_edges
, /* execute */
419 0, /* static_pass_number */
421 PROP_cfg
, /* properties_required */
422 0, /* properties_provided */
423 0, /* properties_destroyed */
424 0, /* todo_flags_start */
425 0 /* todo_flags_finish */
429 /* Record references to functions and other variables present in the
430 initial value of DECL, a variable.
431 When ONLY_VARS is true, we mark needed only variables, not functions. */
434 record_references_in_initializer (tree decl
, bool only_vars
)
436 struct pointer_set_t
*visited_nodes
= pointer_set_create ();
437 struct varpool_node
*node
= varpool_node (decl
);
438 struct record_reference_ctx ctx
= {false, NULL
};
440 ctx
.varpool_node
= node
;
441 ctx
.only_vars
= only_vars
;
442 walk_tree (&DECL_INITIAL (decl
), record_reference
,
443 &ctx
, visited_nodes
);
444 pointer_set_destroy (visited_nodes
);
447 /* Rebuild cgraph edges for current function node. This needs to be run after
448 passes that don't update the cgraph. */
451 rebuild_cgraph_edges (void)
454 struct cgraph_node
*node
= cgraph_node (current_function_decl
);
455 gimple_stmt_iterator gsi
;
457 cgraph_node_remove_callees (node
);
458 ipa_remove_all_references (&node
->ref_list
);
460 node
->count
= ENTRY_BLOCK_PTR
->count
;
464 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
466 gimple stmt
= gsi_stmt (gsi
);
469 if (is_gimple_call (stmt
))
471 int freq
= compute_call_stmt_bb_frequency (current_function_decl
,
473 decl
= gimple_call_fndecl (stmt
);
475 cgraph_create_edge (node
, cgraph_node (decl
), stmt
,
479 cgraph_create_indirect_edge (node
, stmt
,
480 gimple_call_flags (stmt
),
484 walk_stmt_load_store_addr_ops (stmt
, node
, mark_load
,
485 mark_store
, mark_address
);
488 for (gsi
= gsi_start (phi_nodes (bb
)); !gsi_end_p (gsi
); gsi_next (&gsi
))
489 walk_stmt_load_store_addr_ops (gsi_stmt (gsi
), node
,
490 mark_load
, mark_store
, mark_address
);
492 record_eh_tables (node
, cfun
);
493 gcc_assert (!node
->global
.inlined_to
);
498 /* Rebuild cgraph edges for current function node. This needs to be run after
499 passes that don't update the cgraph. */
502 cgraph_rebuild_references (void)
505 struct cgraph_node
*node
= cgraph_node (current_function_decl
);
506 gimple_stmt_iterator gsi
;
508 ipa_remove_all_references (&node
->ref_list
);
510 node
->count
= ENTRY_BLOCK_PTR
->count
;
514 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
516 gimple stmt
= gsi_stmt (gsi
);
518 walk_stmt_load_store_addr_ops (stmt
, node
, mark_load
,
519 mark_store
, mark_address
);
522 for (gsi
= gsi_start (phi_nodes (bb
)); !gsi_end_p (gsi
); gsi_next (&gsi
))
523 walk_stmt_load_store_addr_ops (gsi_stmt (gsi
), node
,
524 mark_load
, mark_store
, mark_address
);
526 record_eh_tables (node
, cfun
);
529 struct gimple_opt_pass pass_rebuild_cgraph_edges
=
533 "*rebuild_cgraph_edges", /* name */
535 rebuild_cgraph_edges
, /* execute */
538 0, /* static_pass_number */
539 TV_CGRAPH
, /* tv_id */
540 PROP_cfg
, /* properties_required */
541 0, /* properties_provided */
542 0, /* properties_destroyed */
543 0, /* todo_flags_start */
544 0, /* todo_flags_finish */
550 remove_cgraph_callee_edges (void)
552 cgraph_node_remove_callees (cgraph_node (current_function_decl
));
556 struct gimple_opt_pass pass_remove_cgraph_callee_edges
=
560 "*remove_cgraph_callee_edges", /* name */
562 remove_cgraph_callee_edges
, /* execute */
565 0, /* static_pass_number */
567 0, /* properties_required */
568 0, /* properties_provided */
569 0, /* properties_destroyed */
570 0, /* todo_flags_start */
571 0, /* todo_flags_finish */