1 /* Callgraph construction.
2 Copyright (C) 2003-2016 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"
27 #include "tree-pass.h"
29 #include "gimple-fold.h"
30 #include "gimple-iterator.h"
31 #include "gimple-walk.h"
32 #include "ipa-utils.h"
35 /* Context of record_reference. */
36 struct record_reference_ctx
39 class varpool_node *varpool_node;
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 record_reference_ctx *ctx = (record_reference_ctx *)data;
54 t = canonicalize_constructor_val (t, NULL);
60 switch (TREE_CODE (t))
69 /* Record dereferences to the functions. This makes the
70 functions reachable unconditionally. */
71 decl = get_base_var (*tp);
72 if (TREE_CODE (decl) == FUNCTION_DECL)
74 cgraph_node *node = cgraph_node::get_create (decl);
76 node->mark_address_taken ();
77 ctx->varpool_node->create_reference (node, IPA_REF_ADDR);
80 if (TREE_CODE (decl) == VAR_DECL)
82 varpool_node *vnode = varpool_node::get_create (decl);
83 ctx->varpool_node->create_reference (vnode, IPA_REF_ADDR);
89 /* Save some cycles by not walking types and declaration as we
90 won't find anything useful there anyway. */
91 if (IS_TYPE_OR_DECL_P (*tp))
102 /* Record references to typeinfos in the type list LIST. */
105 record_type_list (cgraph_node *node, tree list)
107 for (; list; list = TREE_CHAIN (list))
109 tree type = TREE_VALUE (list);
112 type = lookup_type_for_runtime (type);
114 if (TREE_CODE (type) == ADDR_EXPR)
116 type = TREE_OPERAND (type, 0);
117 if (TREE_CODE (type) == VAR_DECL)
119 varpool_node *vnode = varpool_node::get_create (type);
120 node->create_reference (vnode, IPA_REF_ADDR);
126 /* Record all references we will introduce by producing EH tables
130 record_eh_tables (cgraph_node *node, function *fun)
134 if (DECL_FUNCTION_PERSONALITY (node->decl))
136 tree per_decl = DECL_FUNCTION_PERSONALITY (node->decl);
137 cgraph_node *per_node = cgraph_node::get_create (per_decl);
139 node->create_reference (per_node, IPA_REF_ADDR);
140 per_node->mark_address_taken ();
143 i = fun->eh->region_tree;
152 case ERT_MUST_NOT_THROW:
158 for (c = i->u.eh_try.first_catch; c; c = c->next_catch)
159 record_type_list (node, c->type_list);
163 case ERT_ALLOWED_EXCEPTIONS:
164 record_type_list (node, i->u.allowed.type_list);
167 /* If there are sub-regions, process them. */
170 /* If there are peers, process them. */
171 else if (i->next_peer)
173 /* Otherwise, step back up the tree to the next peer. */
182 while (i->next_peer == NULL);
188 /* Computes the frequency of the call statement so that it can be stored in
189 cgraph_edge. BB is the basic block of the call statement. */
191 compute_call_stmt_bb_frequency (tree decl, basic_block bb)
193 int entry_freq = ENTRY_BLOCK_PTR_FOR_FN
194 (DECL_STRUCT_FUNCTION (decl))->frequency;
195 int freq = bb->frequency;
197 if (profile_status_for_fn (DECL_STRUCT_FUNCTION (decl)) == PROFILE_ABSENT)
198 return CGRAPH_FREQ_BASE;
201 entry_freq = 1, freq++;
203 freq = freq * CGRAPH_FREQ_BASE / entry_freq;
204 if (freq > CGRAPH_FREQ_MAX)
205 freq = CGRAPH_FREQ_MAX;
210 /* Mark address taken in STMT. */
213 mark_address (gimple *stmt, tree addr, tree, void *data)
215 addr = get_base_address (addr);
216 if (TREE_CODE (addr) == FUNCTION_DECL)
218 cgraph_node *node = cgraph_node::get_create (addr);
219 node->mark_address_taken ();
220 ((symtab_node *)data)->create_reference (node, IPA_REF_ADDR, stmt);
222 else if (addr && TREE_CODE (addr) == VAR_DECL
223 && (TREE_STATIC (addr) || DECL_EXTERNAL (addr)))
225 varpool_node *vnode = varpool_node::get_create (addr);
227 ((symtab_node *)data)->create_reference (vnode, IPA_REF_ADDR, stmt);
233 /* Mark load of T. */
236 mark_load (gimple *stmt, tree t, tree, void *data)
238 t = get_base_address (t);
239 if (t && TREE_CODE (t) == FUNCTION_DECL)
241 /* ??? This can happen on platforms with descriptors when these are
242 directly manipulated in the code. Pretend that it's an address. */
243 cgraph_node *node = cgraph_node::get_create (t);
244 node->mark_address_taken ();
245 ((symtab_node *)data)->create_reference (node, IPA_REF_ADDR, stmt);
247 else if (t && TREE_CODE (t) == VAR_DECL
248 && (TREE_STATIC (t) || DECL_EXTERNAL (t)))
250 varpool_node *vnode = varpool_node::get_create (t);
252 ((symtab_node *)data)->create_reference (vnode, IPA_REF_LOAD, stmt);
257 /* Mark store of T. */
260 mark_store (gimple *stmt, tree t, tree, void *data)
262 t = get_base_address (t);
263 if (t && TREE_CODE (t) == VAR_DECL
264 && (TREE_STATIC (t) || DECL_EXTERNAL (t)))
266 varpool_node *vnode = varpool_node::get_create (t);
268 ((symtab_node *)data)->create_reference (vnode, IPA_REF_STORE, stmt);
273 /* Record all references from cgraph_node that are taken in statement STMT. */
276 cgraph_node::record_stmt_references (gimple *stmt)
278 walk_stmt_load_store_addr_ops (stmt, this, mark_load, mark_store,
282 /* Create cgraph edges for function calls.
283 Also look for functions and variables having addresses taken. */
287 const pass_data pass_data_build_cgraph_edges =
289 GIMPLE_PASS, /* type */
290 "*build_cgraph_edges", /* name */
291 OPTGROUP_NONE, /* optinfo_flags */
293 PROP_cfg, /* properties_required */
294 0, /* properties_provided */
295 0, /* properties_destroyed */
296 0, /* todo_flags_start */
297 0, /* todo_flags_finish */
300 class pass_build_cgraph_edges : public gimple_opt_pass
303 pass_build_cgraph_edges (gcc::context *ctxt)
304 : gimple_opt_pass (pass_data_build_cgraph_edges, ctxt)
307 /* opt_pass methods: */
308 virtual unsigned int execute (function *);
310 }; // class pass_build_cgraph_edges
313 pass_build_cgraph_edges::execute (function *fun)
316 cgraph_node *node = cgraph_node::get (current_function_decl);
317 gimple_stmt_iterator gsi;
321 /* Create the callgraph edges and record the nodes referenced by the function.
323 FOR_EACH_BB_FN (bb, fun)
325 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
327 gimple *stmt = gsi_stmt (gsi);
330 if (is_gimple_debug (stmt))
333 if (gcall *call_stmt = dyn_cast <gcall *> (stmt))
335 int freq = compute_call_stmt_bb_frequency (current_function_decl,
337 decl = gimple_call_fndecl (call_stmt);
339 node->create_edge (cgraph_node::get_create (decl), call_stmt, bb->count, freq);
340 else if (gimple_call_internal_p (call_stmt))
343 node->create_indirect_edge (call_stmt,
344 gimple_call_flags (call_stmt),
347 node->record_stmt_references (stmt);
348 if (gomp_parallel *omp_par_stmt = dyn_cast <gomp_parallel *> (stmt))
350 tree fn = gimple_omp_parallel_child_fn (omp_par_stmt);
351 node->create_reference (cgraph_node::get_create (fn),
354 if (gimple_code (stmt) == GIMPLE_OMP_TASK)
356 tree fn = gimple_omp_task_child_fn (stmt);
358 node->create_reference (cgraph_node::get_create (fn),
360 fn = gimple_omp_task_copy_fn (stmt);
362 node->create_reference (cgraph_node::get_create (fn),
366 for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi))
367 node->record_stmt_references (gsi_stmt (gsi));
370 /* Look for initializers of constant variables and private statics. */
371 FOR_EACH_LOCAL_DECL (fun, ix, decl)
372 if (TREE_CODE (decl) == VAR_DECL
373 && (TREE_STATIC (decl) && !DECL_EXTERNAL (decl))
374 && !DECL_HAS_VALUE_EXPR_P (decl)
375 && TREE_TYPE (decl) != error_mark_node)
376 varpool_node::finalize_decl (decl);
377 record_eh_tables (node, fun);
385 make_pass_build_cgraph_edges (gcc::context *ctxt)
387 return new pass_build_cgraph_edges (ctxt);
390 /* Record references to functions and other variables present in the
391 initial value of DECL, a variable.
392 When ONLY_VARS is true, we mark needed only variables, not functions. */
395 record_references_in_initializer (tree decl, bool only_vars)
397 varpool_node *node = varpool_node::get_create (decl);
398 hash_set<tree> visited_nodes;
399 record_reference_ctx ctx = {false, NULL};
401 ctx.varpool_node = node;
402 ctx.only_vars = only_vars;
403 walk_tree (&DECL_INITIAL (decl), record_reference,
404 &ctx, &visited_nodes);
407 /* Rebuild cgraph edges for current function node. This needs to be run after
408 passes that don't update the cgraph. */
411 cgraph_edge::rebuild_edges (void)
414 cgraph_node *node = cgraph_node::get (current_function_decl);
415 gimple_stmt_iterator gsi;
417 node->remove_callees ();
418 node->remove_all_references ();
420 node->count = ENTRY_BLOCK_PTR_FOR_FN (cfun)->count;
422 FOR_EACH_BB_FN (bb, cfun)
424 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
426 gimple *stmt = gsi_stmt (gsi);
429 if (gcall *call_stmt = dyn_cast <gcall *> (stmt))
431 int freq = compute_call_stmt_bb_frequency (current_function_decl,
433 decl = gimple_call_fndecl (call_stmt);
435 node->create_edge (cgraph_node::get_create (decl), call_stmt,
437 else if (gimple_call_internal_p (call_stmt))
440 node->create_indirect_edge (call_stmt,
441 gimple_call_flags (call_stmt),
444 node->record_stmt_references (stmt);
446 for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi))
447 node->record_stmt_references (gsi_stmt (gsi));
449 record_eh_tables (node, cfun);
450 gcc_assert (!node->global.inlined_to);
452 if (node->instrumented_version
453 && !node->instrumentation_clone)
454 node->create_reference (node->instrumented_version, IPA_REF_CHKP, NULL);
459 /* Rebuild cgraph references for current function node. This needs to be run
460 after passes that don't update the cgraph. */
463 cgraph_edge::rebuild_references (void)
466 cgraph_node *node = cgraph_node::get (current_function_decl);
467 gimple_stmt_iterator gsi;
471 /* Keep speculative references for further cgraph edge expansion. */
472 for (i = 0; node->iterate_reference (i, ref);)
473 if (!ref->speculative)
474 ref->remove_reference ();
478 node->count = ENTRY_BLOCK_PTR_FOR_FN (cfun)->count;
480 FOR_EACH_BB_FN (bb, cfun)
482 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
483 node->record_stmt_references (gsi_stmt (gsi));
484 for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi))
485 node->record_stmt_references (gsi_stmt (gsi));
487 record_eh_tables (node, cfun);
489 if (node->instrumented_version
490 && !node->instrumentation_clone)
491 node->create_reference (node->instrumented_version, IPA_REF_CHKP, NULL);
496 const pass_data pass_data_rebuild_cgraph_edges =
498 GIMPLE_PASS, /* type */
499 "*rebuild_cgraph_edges", /* name */
500 OPTGROUP_NONE, /* optinfo_flags */
501 TV_CGRAPH, /* tv_id */
502 PROP_cfg, /* properties_required */
503 0, /* properties_provided */
504 0, /* properties_destroyed */
505 0, /* todo_flags_start */
506 0, /* todo_flags_finish */
509 class pass_rebuild_cgraph_edges : public gimple_opt_pass
512 pass_rebuild_cgraph_edges (gcc::context *ctxt)
513 : gimple_opt_pass (pass_data_rebuild_cgraph_edges, ctxt)
516 /* opt_pass methods: */
517 opt_pass * clone () { return new pass_rebuild_cgraph_edges (m_ctxt); }
518 virtual unsigned int execute (function *)
520 return cgraph_edge::rebuild_edges ();
523 }; // class pass_rebuild_cgraph_edges
528 make_pass_rebuild_cgraph_edges (gcc::context *ctxt)
530 return new pass_rebuild_cgraph_edges (ctxt);
536 const pass_data pass_data_remove_cgraph_callee_edges =
538 GIMPLE_PASS, /* type */
539 "*remove_cgraph_callee_edges", /* name */
540 OPTGROUP_NONE, /* optinfo_flags */
542 0, /* properties_required */
543 0, /* properties_provided */
544 0, /* properties_destroyed */
545 0, /* todo_flags_start */
546 0, /* todo_flags_finish */
549 class pass_remove_cgraph_callee_edges : public gimple_opt_pass
552 pass_remove_cgraph_callee_edges (gcc::context *ctxt)
553 : gimple_opt_pass (pass_data_remove_cgraph_callee_edges, ctxt)
556 /* opt_pass methods: */
557 opt_pass * clone () {
558 return new pass_remove_cgraph_callee_edges (m_ctxt);
560 virtual unsigned int execute (function *);
562 }; // class pass_remove_cgraph_callee_edges
565 pass_remove_cgraph_callee_edges::execute (function *)
567 cgraph_node *node = cgraph_node::get (current_function_decl);
568 node->remove_callees ();
569 node->remove_all_references ();
576 make_pass_remove_cgraph_callee_edges (gcc::context *ctxt)
578 return new pass_remove_cgraph_callee_edges (ctxt);