1 /* Callgraph construction.
2 Copyright (C) 2003-2013 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/>. */
23 #include "coretypes.h"
26 #include "pointer-set.h"
27 #include "basic-block.h"
28 #include "tree-ssa-alias.h"
29 #include "internal-fn.h"
30 #include "gimple-fold.h"
31 #include "gimple-expr.h"
34 #include "gimple-iterator.h"
35 #include "gimple-walk.h"
36 #include "langhooks.h"
38 #include "tree-pass.h"
39 #include "ipa-utils.h"
41 #include "ipa-inline.h"
43 /* Context of record_reference. */
44 struct record_reference_ctx
47 struct varpool_node
*varpool_node
;
50 /* Walk tree and record all calls and references to functions/variables.
51 Called via walk_tree: TP is pointer to tree to be examined.
52 When DATA is non-null, record references to callgraph.
56 record_reference (tree
*tp
, int *walk_subtrees
, void *data
)
60 struct record_reference_ctx
*ctx
= (struct record_reference_ctx
*)data
;
62 t
= canonicalize_constructor_val (t
, NULL
);
68 switch (TREE_CODE (t
))
77 /* Record dereferences to the functions. This makes the
78 functions reachable unconditionally. */
79 decl
= get_base_var (*tp
);
80 if (TREE_CODE (decl
) == FUNCTION_DECL
)
82 struct cgraph_node
*node
= cgraph_get_create_node (decl
);
84 cgraph_mark_address_taken_node (node
);
85 ipa_record_reference (ctx
->varpool_node
,
90 if (TREE_CODE (decl
) == VAR_DECL
)
92 struct varpool_node
*vnode
= varpool_node_for_decl (decl
);
93 ipa_record_reference (ctx
->varpool_node
,
101 /* Save some cycles by not walking types and declaration as we
102 won't find anything useful there anyway. */
103 if (IS_TYPE_OR_DECL_P (*tp
))
114 /* Record references to typeinfos in the type list LIST. */
117 record_type_list (struct cgraph_node
*node
, tree list
)
119 for (; list
; list
= TREE_CHAIN (list
))
121 tree type
= TREE_VALUE (list
);
124 type
= lookup_type_for_runtime (type
);
126 if (TREE_CODE (type
) == ADDR_EXPR
)
128 type
= TREE_OPERAND (type
, 0);
129 if (TREE_CODE (type
) == VAR_DECL
)
131 struct varpool_node
*vnode
= varpool_node_for_decl (type
);
132 ipa_record_reference (node
,
140 /* Record all references we will introduce by producing EH tables
144 record_eh_tables (struct cgraph_node
*node
, struct function
*fun
)
148 if (DECL_FUNCTION_PERSONALITY (node
->decl
))
150 tree per_decl
= DECL_FUNCTION_PERSONALITY (node
->decl
);
151 struct cgraph_node
*per_node
= cgraph_get_create_node (per_decl
);
153 ipa_record_reference (node
, per_node
, IPA_REF_ADDR
, NULL
);
154 cgraph_mark_address_taken_node (per_node
);
157 i
= fun
->eh
->region_tree
;
166 case ERT_MUST_NOT_THROW
:
172 for (c
= i
->u
.eh_try
.first_catch
; c
; c
= c
->next_catch
)
173 record_type_list (node
, c
->type_list
);
177 case ERT_ALLOWED_EXCEPTIONS
:
178 record_type_list (node
, i
->u
.allowed
.type_list
);
181 /* If there are sub-regions, process them. */
184 /* If there are peers, process them. */
185 else if (i
->next_peer
)
187 /* Otherwise, step back up the tree to the next peer. */
196 while (i
->next_peer
== NULL
);
202 /* Computes the frequency of the call statement so that it can be stored in
203 cgraph_edge. BB is the basic block of the call statement. */
205 compute_call_stmt_bb_frequency (tree decl
, basic_block bb
)
207 int entry_freq
= ENTRY_BLOCK_PTR_FOR_FN
208 (DECL_STRUCT_FUNCTION (decl
))->frequency
;
209 int freq
= bb
->frequency
;
211 if (profile_status_for_function (DECL_STRUCT_FUNCTION (decl
)) == PROFILE_ABSENT
)
212 return CGRAPH_FREQ_BASE
;
215 entry_freq
= 1, freq
++;
217 freq
= freq
* CGRAPH_FREQ_BASE
/ entry_freq
;
218 if (freq
> CGRAPH_FREQ_MAX
)
219 freq
= CGRAPH_FREQ_MAX
;
224 /* Mark address taken in STMT. */
227 mark_address (gimple stmt
, tree addr
, void *data
)
229 addr
= get_base_address (addr
);
230 if (TREE_CODE (addr
) == FUNCTION_DECL
)
232 struct cgraph_node
*node
= cgraph_get_create_node (addr
);
233 cgraph_mark_address_taken_node (node
);
234 ipa_record_reference ((symtab_node
*)data
,
238 else if (addr
&& TREE_CODE (addr
) == VAR_DECL
239 && (TREE_STATIC (addr
) || DECL_EXTERNAL (addr
)))
241 struct varpool_node
*vnode
= varpool_node_for_decl (addr
);
243 ipa_record_reference ((symtab_node
*)data
,
251 /* Mark load of T. */
254 mark_load (gimple stmt
, tree t
, void *data
)
256 t
= get_base_address (t
);
257 if (t
&& TREE_CODE (t
) == FUNCTION_DECL
)
259 /* ??? This can happen on platforms with descriptors when these are
260 directly manipulated in the code. Pretend that it's an address. */
261 struct cgraph_node
*node
= cgraph_get_create_node (t
);
262 cgraph_mark_address_taken_node (node
);
263 ipa_record_reference ((symtab_node
*)data
,
267 else if (t
&& TREE_CODE (t
) == VAR_DECL
268 && (TREE_STATIC (t
) || DECL_EXTERNAL (t
)))
270 struct varpool_node
*vnode
= varpool_node_for_decl (t
);
272 ipa_record_reference ((symtab_node
*)data
,
279 /* Mark store of T. */
282 mark_store (gimple stmt
, tree t
, void *data
)
284 t
= get_base_address (t
);
285 if (t
&& TREE_CODE (t
) == VAR_DECL
286 && (TREE_STATIC (t
) || DECL_EXTERNAL (t
)))
288 struct varpool_node
*vnode
= varpool_node_for_decl (t
);
290 ipa_record_reference ((symtab_node
*)data
,
292 IPA_REF_STORE
, stmt
);
297 /* Record all references from NODE that are taken in statement STMT. */
299 ipa_record_stmt_references (struct cgraph_node
*node
, gimple stmt
)
301 walk_stmt_load_store_addr_ops (stmt
, node
, mark_load
, mark_store
,
305 /* Create cgraph edges for function calls.
306 Also look for functions and variables having addresses taken. */
309 build_cgraph_edges (void)
312 struct cgraph_node
*node
= cgraph_get_node (current_function_decl
);
313 struct pointer_set_t
*visited_nodes
= pointer_set_create ();
314 gimple_stmt_iterator gsi
;
318 /* Create the callgraph edges and record the nodes referenced by the function.
322 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
324 gimple stmt
= gsi_stmt (gsi
);
327 if (is_gimple_debug (stmt
))
330 if (is_gimple_call (stmt
))
332 int freq
= compute_call_stmt_bb_frequency (current_function_decl
,
334 decl
= gimple_call_fndecl (stmt
);
336 cgraph_create_edge (node
, cgraph_get_create_node (decl
),
337 stmt
, bb
->count
, freq
);
339 cgraph_create_indirect_edge (node
, stmt
,
340 gimple_call_flags (stmt
),
343 ipa_record_stmt_references (node
, stmt
);
344 if (gimple_code (stmt
) == GIMPLE_OMP_PARALLEL
345 && gimple_omp_parallel_child_fn (stmt
))
347 tree fn
= gimple_omp_parallel_child_fn (stmt
);
348 ipa_record_reference (node
,
349 cgraph_get_create_node (fn
),
352 if (gimple_code (stmt
) == GIMPLE_OMP_TASK
)
354 tree fn
= gimple_omp_task_child_fn (stmt
);
356 ipa_record_reference (node
,
357 cgraph_get_create_node (fn
),
359 fn
= gimple_omp_task_copy_fn (stmt
);
361 ipa_record_reference (node
,
362 cgraph_get_create_node (fn
),
366 for (gsi
= gsi_start_phis (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
367 ipa_record_stmt_references (node
, gsi_stmt (gsi
));
370 /* Look for initializers of constant variables and private statics. */
371 FOR_EACH_LOCAL_DECL (cfun
, ix
, decl
)
372 if (TREE_CODE (decl
) == VAR_DECL
373 && (TREE_STATIC (decl
) && !DECL_EXTERNAL (decl
))
374 && !DECL_HAS_VALUE_EXPR_P (decl
))
375 varpool_finalize_decl (decl
);
376 record_eh_tables (node
, cfun
);
378 pointer_set_destroy (visited_nodes
);
384 const pass_data pass_data_build_cgraph_edges
=
386 GIMPLE_PASS
, /* type */
387 "*build_cgraph_edges", /* name */
388 OPTGROUP_NONE
, /* optinfo_flags */
389 false, /* has_gate */
390 true, /* has_execute */
392 PROP_cfg
, /* properties_required */
393 0, /* properties_provided */
394 0, /* properties_destroyed */
395 0, /* todo_flags_start */
396 0, /* todo_flags_finish */
399 class pass_build_cgraph_edges
: public gimple_opt_pass
402 pass_build_cgraph_edges (gcc::context
*ctxt
)
403 : gimple_opt_pass (pass_data_build_cgraph_edges
, ctxt
)
406 /* opt_pass methods: */
407 unsigned int execute () { return build_cgraph_edges (); }
409 }; // class pass_build_cgraph_edges
414 make_pass_build_cgraph_edges (gcc::context
*ctxt
)
416 return new pass_build_cgraph_edges (ctxt
);
419 /* Record references to functions and other variables present in the
420 initial value of DECL, a variable.
421 When ONLY_VARS is true, we mark needed only variables, not functions. */
424 record_references_in_initializer (tree decl
, bool only_vars
)
426 struct pointer_set_t
*visited_nodes
= pointer_set_create ();
427 struct varpool_node
*node
= varpool_node_for_decl (decl
);
428 struct record_reference_ctx ctx
= {false, NULL
};
430 ctx
.varpool_node
= node
;
431 ctx
.only_vars
= only_vars
;
432 walk_tree (&DECL_INITIAL (decl
), record_reference
,
433 &ctx
, visited_nodes
);
434 pointer_set_destroy (visited_nodes
);
437 /* Rebuild cgraph edges for current function node. This needs to be run after
438 passes that don't update the cgraph. */
441 rebuild_cgraph_edges (void)
444 struct cgraph_node
*node
= cgraph_get_node (current_function_decl
);
445 gimple_stmt_iterator gsi
;
447 cgraph_node_remove_callees (node
);
448 ipa_remove_all_references (&node
->ref_list
);
450 node
->count
= ENTRY_BLOCK_PTR_FOR_FN (cfun
)->count
;
454 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
456 gimple stmt
= gsi_stmt (gsi
);
459 if (is_gimple_call (stmt
))
461 int freq
= compute_call_stmt_bb_frequency (current_function_decl
,
463 decl
= gimple_call_fndecl (stmt
);
465 cgraph_create_edge (node
, cgraph_get_create_node (decl
), stmt
,
468 cgraph_create_indirect_edge (node
, stmt
,
469 gimple_call_flags (stmt
),
472 ipa_record_stmt_references (node
, stmt
);
474 for (gsi
= gsi_start_phis (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
475 ipa_record_stmt_references (node
, gsi_stmt (gsi
));
477 record_eh_tables (node
, cfun
);
478 gcc_assert (!node
->global
.inlined_to
);
483 /* Rebuild cgraph edges for current function node. This needs to be run after
484 passes that don't update the cgraph. */
487 cgraph_rebuild_references (void)
490 struct cgraph_node
*node
= cgraph_get_node (current_function_decl
);
491 gimple_stmt_iterator gsi
;
495 /* Keep speculative references for further cgraph edge expansion. */
496 for (i
= 0; ipa_ref_list_reference_iterate (&node
->ref_list
, i
, ref
);)
497 if (!ref
->speculative
)
498 ipa_remove_reference (ref
);
502 node
->count
= ENTRY_BLOCK_PTR_FOR_FN (cfun
)->count
;
506 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
507 ipa_record_stmt_references (node
, gsi_stmt (gsi
));
508 for (gsi
= gsi_start_phis (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
509 ipa_record_stmt_references (node
, gsi_stmt (gsi
));
511 record_eh_tables (node
, cfun
);
516 const pass_data pass_data_rebuild_cgraph_edges
=
518 GIMPLE_PASS
, /* type */
519 "*rebuild_cgraph_edges", /* name */
520 OPTGROUP_NONE
, /* optinfo_flags */
521 false, /* has_gate */
522 true, /* has_execute */
523 TV_CGRAPH
, /* tv_id */
524 PROP_cfg
, /* properties_required */
525 0, /* properties_provided */
526 0, /* properties_destroyed */
527 0, /* todo_flags_start */
528 0, /* todo_flags_finish */
531 class pass_rebuild_cgraph_edges
: public gimple_opt_pass
534 pass_rebuild_cgraph_edges (gcc::context
*ctxt
)
535 : gimple_opt_pass (pass_data_rebuild_cgraph_edges
, ctxt
)
538 /* opt_pass methods: */
539 opt_pass
* clone () { return new pass_rebuild_cgraph_edges (m_ctxt
); }
540 unsigned int execute () { return rebuild_cgraph_edges (); }
542 }; // class pass_rebuild_cgraph_edges
547 make_pass_rebuild_cgraph_edges (gcc::context
*ctxt
)
549 return new pass_rebuild_cgraph_edges (ctxt
);
554 remove_cgraph_callee_edges (void)
556 struct cgraph_node
*node
= cgraph_get_node (current_function_decl
);
557 cgraph_node_remove_callees (node
);
558 ipa_remove_all_references (&node
->ref_list
);
564 const pass_data pass_data_remove_cgraph_callee_edges
=
566 GIMPLE_PASS
, /* type */
567 "*remove_cgraph_callee_edges", /* name */
568 OPTGROUP_NONE
, /* optinfo_flags */
569 false, /* has_gate */
570 true, /* has_execute */
572 0, /* properties_required */
573 0, /* properties_provided */
574 0, /* properties_destroyed */
575 0, /* todo_flags_start */
576 0, /* todo_flags_finish */
579 class pass_remove_cgraph_callee_edges
: public gimple_opt_pass
582 pass_remove_cgraph_callee_edges (gcc::context
*ctxt
)
583 : gimple_opt_pass (pass_data_remove_cgraph_callee_edges
, ctxt
)
586 /* opt_pass methods: */
587 opt_pass
* clone () {
588 return new pass_remove_cgraph_callee_edges (m_ctxt
);
590 unsigned int execute () { return remove_cgraph_callee_edges (); }
592 }; // class pass_remove_cgraph_callee_edges
597 make_pass_remove_cgraph_callee_edges (gcc::context
*ctxt
)
599 return new pass_remove_cgraph_callee_edges (ctxt
);