1 /* Callgraph construction.
2 Copyright (C) 2003-2015 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"
31 #include "hard-reg-set.h"
34 #include "dominance.h"
36 #include "basic-block.h"
37 #include "tree-ssa-alias.h"
38 #include "internal-fn.h"
39 #include "gimple-fold.h"
40 #include "gimple-expr.h"
43 #include "gimple-iterator.h"
44 #include "gimple-walk.h"
45 #include "langhooks.h"
47 #include "tree-pass.h"
49 #include "plugin-api.h"
52 #include "ipa-utils.h"
54 #include "alloc-pool.h"
55 #include "symbol-summary.h"
57 #include "ipa-inline.h"
59 /* Context of record_reference. */
60 struct record_reference_ctx
63 class varpool_node
*varpool_node
;
66 /* Walk tree and record all calls and references to functions/variables.
67 Called via walk_tree: TP is pointer to tree to be examined.
68 When DATA is non-null, record references to callgraph.
72 record_reference (tree
*tp
, int *walk_subtrees
, void *data
)
76 record_reference_ctx
*ctx
= (record_reference_ctx
*)data
;
78 t
= canonicalize_constructor_val (t
, NULL
);
84 switch (TREE_CODE (t
))
93 /* Record dereferences to the functions. This makes the
94 functions reachable unconditionally. */
95 decl
= get_base_var (*tp
);
96 if (TREE_CODE (decl
) == FUNCTION_DECL
)
98 cgraph_node
*node
= cgraph_node::get_create (decl
);
100 node
->mark_address_taken ();
101 ctx
->varpool_node
->create_reference (node
, IPA_REF_ADDR
);
104 if (TREE_CODE (decl
) == VAR_DECL
)
106 varpool_node
*vnode
= varpool_node::get_create (decl
);
107 ctx
->varpool_node
->create_reference (vnode
, IPA_REF_ADDR
);
113 /* Save some cycles by not walking types and declaration as we
114 won't find anything useful there anyway. */
115 if (IS_TYPE_OR_DECL_P (*tp
))
126 /* Record references to typeinfos in the type list LIST. */
129 record_type_list (cgraph_node
*node
, tree list
)
131 for (; list
; list
= TREE_CHAIN (list
))
133 tree type
= TREE_VALUE (list
);
136 type
= lookup_type_for_runtime (type
);
138 if (TREE_CODE (type
) == ADDR_EXPR
)
140 type
= TREE_OPERAND (type
, 0);
141 if (TREE_CODE (type
) == VAR_DECL
)
143 varpool_node
*vnode
= varpool_node::get_create (type
);
144 node
->create_reference (vnode
, IPA_REF_ADDR
);
150 /* Record all references we will introduce by producing EH tables
154 record_eh_tables (cgraph_node
*node
, function
*fun
)
158 if (DECL_FUNCTION_PERSONALITY (node
->decl
))
160 tree per_decl
= DECL_FUNCTION_PERSONALITY (node
->decl
);
161 cgraph_node
*per_node
= cgraph_node::get_create (per_decl
);
163 node
->create_reference (per_node
, IPA_REF_ADDR
);
164 per_node
->mark_address_taken ();
167 i
= fun
->eh
->region_tree
;
176 case ERT_MUST_NOT_THROW
:
182 for (c
= i
->u
.eh_try
.first_catch
; c
; c
= c
->next_catch
)
183 record_type_list (node
, c
->type_list
);
187 case ERT_ALLOWED_EXCEPTIONS
:
188 record_type_list (node
, i
->u
.allowed
.type_list
);
191 /* If there are sub-regions, process them. */
194 /* If there are peers, process them. */
195 else if (i
->next_peer
)
197 /* Otherwise, step back up the tree to the next peer. */
206 while (i
->next_peer
== NULL
);
212 /* Computes the frequency of the call statement so that it can be stored in
213 cgraph_edge. BB is the basic block of the call statement. */
215 compute_call_stmt_bb_frequency (tree decl
, basic_block bb
)
217 int entry_freq
= ENTRY_BLOCK_PTR_FOR_FN
218 (DECL_STRUCT_FUNCTION (decl
))->frequency
;
219 int freq
= bb
->frequency
;
221 if (profile_status_for_fn (DECL_STRUCT_FUNCTION (decl
)) == PROFILE_ABSENT
)
222 return CGRAPH_FREQ_BASE
;
225 entry_freq
= 1, freq
++;
227 freq
= freq
* CGRAPH_FREQ_BASE
/ entry_freq
;
228 if (freq
> CGRAPH_FREQ_MAX
)
229 freq
= CGRAPH_FREQ_MAX
;
234 /* Mark address taken in STMT. */
237 mark_address (gimple stmt
, tree addr
, tree
, void *data
)
239 addr
= get_base_address (addr
);
240 if (TREE_CODE (addr
) == FUNCTION_DECL
)
242 cgraph_node
*node
= cgraph_node::get_create (addr
);
243 node
->mark_address_taken ();
244 ((symtab_node
*)data
)->create_reference (node
, IPA_REF_ADDR
, stmt
);
246 else if (addr
&& TREE_CODE (addr
) == VAR_DECL
247 && (TREE_STATIC (addr
) || DECL_EXTERNAL (addr
)))
249 varpool_node
*vnode
= varpool_node::get_create (addr
);
251 ((symtab_node
*)data
)->create_reference (vnode
, IPA_REF_ADDR
, stmt
);
257 /* Mark load of T. */
260 mark_load (gimple stmt
, tree t
, tree
, void *data
)
262 t
= get_base_address (t
);
263 if (t
&& TREE_CODE (t
) == FUNCTION_DECL
)
265 /* ??? This can happen on platforms with descriptors when these are
266 directly manipulated in the code. Pretend that it's an address. */
267 cgraph_node
*node
= cgraph_node::get_create (t
);
268 node
->mark_address_taken ();
269 ((symtab_node
*)data
)->create_reference (node
, IPA_REF_ADDR
, stmt
);
271 else if (t
&& TREE_CODE (t
) == VAR_DECL
272 && (TREE_STATIC (t
) || DECL_EXTERNAL (t
)))
274 varpool_node
*vnode
= varpool_node::get_create (t
);
276 ((symtab_node
*)data
)->create_reference (vnode
, IPA_REF_LOAD
, stmt
);
281 /* Mark store of T. */
284 mark_store (gimple stmt
, tree t
, tree
, void *data
)
286 t
= get_base_address (t
);
287 if (t
&& TREE_CODE (t
) == VAR_DECL
288 && (TREE_STATIC (t
) || DECL_EXTERNAL (t
)))
290 varpool_node
*vnode
= varpool_node::get_create (t
);
292 ((symtab_node
*)data
)->create_reference (vnode
, IPA_REF_STORE
, stmt
);
297 /* Record all references from cgraph_node that are taken in statement STMT. */
300 cgraph_node::record_stmt_references (gimple stmt
)
302 walk_stmt_load_store_addr_ops (stmt
, this, mark_load
, mark_store
,
306 /* Create cgraph edges for function calls.
307 Also look for functions and variables having addresses taken. */
311 const pass_data pass_data_build_cgraph_edges
=
313 GIMPLE_PASS
, /* type */
314 "*build_cgraph_edges", /* name */
315 OPTGROUP_NONE
, /* optinfo_flags */
317 PROP_cfg
, /* properties_required */
318 0, /* properties_provided */
319 0, /* properties_destroyed */
320 0, /* todo_flags_start */
321 0, /* todo_flags_finish */
324 class pass_build_cgraph_edges
: public gimple_opt_pass
327 pass_build_cgraph_edges (gcc::context
*ctxt
)
328 : gimple_opt_pass (pass_data_build_cgraph_edges
, ctxt
)
331 /* opt_pass methods: */
332 virtual unsigned int execute (function
*);
334 }; // class pass_build_cgraph_edges
337 pass_build_cgraph_edges::execute (function
*fun
)
340 cgraph_node
*node
= cgraph_node::get (current_function_decl
);
341 gimple_stmt_iterator gsi
;
345 /* Create the callgraph edges and record the nodes referenced by the function.
347 FOR_EACH_BB_FN (bb
, fun
)
349 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
351 gimple stmt
= gsi_stmt (gsi
);
354 if (is_gimple_debug (stmt
))
357 if (gcall
*call_stmt
= dyn_cast
<gcall
*> (stmt
))
359 int freq
= compute_call_stmt_bb_frequency (current_function_decl
,
361 decl
= gimple_call_fndecl (call_stmt
);
363 node
->create_edge (cgraph_node::get_create (decl
), call_stmt
, bb
->count
, freq
);
364 else if (gimple_call_internal_p (call_stmt
))
367 node
->create_indirect_edge (call_stmt
,
368 gimple_call_flags (call_stmt
),
371 node
->record_stmt_references (stmt
);
372 if (gomp_parallel
*omp_par_stmt
= dyn_cast
<gomp_parallel
*> (stmt
))
374 tree fn
= gimple_omp_parallel_child_fn (omp_par_stmt
);
375 node
->create_reference (cgraph_node::get_create (fn
),
378 if (gimple_code (stmt
) == GIMPLE_OMP_TASK
)
380 tree fn
= gimple_omp_task_child_fn (stmt
);
382 node
->create_reference (cgraph_node::get_create (fn
),
384 fn
= gimple_omp_task_copy_fn (stmt
);
386 node
->create_reference (cgraph_node::get_create (fn
),
390 for (gsi
= gsi_start_phis (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
391 node
->record_stmt_references (gsi_stmt (gsi
));
394 /* Look for initializers of constant variables and private statics. */
395 FOR_EACH_LOCAL_DECL (fun
, ix
, decl
)
396 if (TREE_CODE (decl
) == VAR_DECL
397 && (TREE_STATIC (decl
) && !DECL_EXTERNAL (decl
))
398 && !DECL_HAS_VALUE_EXPR_P (decl
))
399 varpool_node::finalize_decl (decl
);
400 record_eh_tables (node
, fun
);
408 make_pass_build_cgraph_edges (gcc::context
*ctxt
)
410 return new pass_build_cgraph_edges (ctxt
);
413 /* Record references to functions and other variables present in the
414 initial value of DECL, a variable.
415 When ONLY_VARS is true, we mark needed only variables, not functions. */
418 record_references_in_initializer (tree decl
, bool only_vars
)
420 varpool_node
*node
= varpool_node::get_create (decl
);
421 hash_set
<tree
> visited_nodes
;
422 record_reference_ctx ctx
= {false, NULL
};
424 ctx
.varpool_node
= node
;
425 ctx
.only_vars
= only_vars
;
426 walk_tree (&DECL_INITIAL (decl
), record_reference
,
427 &ctx
, &visited_nodes
);
430 /* Rebuild cgraph edges for current function node. This needs to be run after
431 passes that don't update the cgraph. */
434 cgraph_edge::rebuild_edges (void)
437 cgraph_node
*node
= cgraph_node::get (current_function_decl
);
438 gimple_stmt_iterator gsi
;
440 node
->remove_callees ();
441 node
->remove_all_references ();
443 node
->count
= ENTRY_BLOCK_PTR_FOR_FN (cfun
)->count
;
445 FOR_EACH_BB_FN (bb
, cfun
)
447 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
449 gimple stmt
= gsi_stmt (gsi
);
452 if (gcall
*call_stmt
= dyn_cast
<gcall
*> (stmt
))
454 int freq
= compute_call_stmt_bb_frequency (current_function_decl
,
456 decl
= gimple_call_fndecl (call_stmt
);
458 node
->create_edge (cgraph_node::get_create (decl
), call_stmt
,
460 else if (gimple_call_internal_p (call_stmt
))
463 node
->create_indirect_edge (call_stmt
,
464 gimple_call_flags (call_stmt
),
467 node
->record_stmt_references (stmt
);
469 for (gsi
= gsi_start_phis (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
470 node
->record_stmt_references (gsi_stmt (gsi
));
472 record_eh_tables (node
, cfun
);
473 gcc_assert (!node
->global
.inlined_to
);
475 if (node
->instrumented_version
476 && !node
->instrumentation_clone
)
477 node
->create_reference (node
->instrumented_version
, IPA_REF_CHKP
, NULL
);
482 /* Rebuild cgraph references for current function node. This needs to be run
483 after passes that don't update the cgraph. */
486 cgraph_edge::rebuild_references (void)
489 cgraph_node
*node
= cgraph_node::get (current_function_decl
);
490 gimple_stmt_iterator gsi
;
494 /* Keep speculative references for further cgraph edge expansion. */
495 for (i
= 0; node
->iterate_reference (i
, ref
);)
496 if (!ref
->speculative
)
497 ref
->remove_reference ();
501 node
->count
= ENTRY_BLOCK_PTR_FOR_FN (cfun
)->count
;
503 FOR_EACH_BB_FN (bb
, cfun
)
505 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
506 node
->record_stmt_references (gsi_stmt (gsi
));
507 for (gsi
= gsi_start_phis (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
508 node
->record_stmt_references (gsi_stmt (gsi
));
510 record_eh_tables (node
, cfun
);
512 if (node
->instrumented_version
513 && !node
->instrumentation_clone
)
514 node
->create_reference (node
->instrumented_version
, IPA_REF_CHKP
, NULL
);
519 const pass_data pass_data_rebuild_cgraph_edges
=
521 GIMPLE_PASS
, /* type */
522 "*rebuild_cgraph_edges", /* name */
523 OPTGROUP_NONE
, /* optinfo_flags */
524 TV_CGRAPH
, /* tv_id */
525 PROP_cfg
, /* properties_required */
526 0, /* properties_provided */
527 0, /* properties_destroyed */
528 0, /* todo_flags_start */
529 0, /* todo_flags_finish */
532 class pass_rebuild_cgraph_edges
: public gimple_opt_pass
535 pass_rebuild_cgraph_edges (gcc::context
*ctxt
)
536 : gimple_opt_pass (pass_data_rebuild_cgraph_edges
, ctxt
)
539 /* opt_pass methods: */
540 opt_pass
* clone () { return new pass_rebuild_cgraph_edges (m_ctxt
); }
541 virtual unsigned int execute (function
*)
543 return cgraph_edge::rebuild_edges ();
546 }; // class pass_rebuild_cgraph_edges
551 make_pass_rebuild_cgraph_edges (gcc::context
*ctxt
)
553 return new pass_rebuild_cgraph_edges (ctxt
);
559 const pass_data pass_data_remove_cgraph_callee_edges
=
561 GIMPLE_PASS
, /* type */
562 "*remove_cgraph_callee_edges", /* name */
563 OPTGROUP_NONE
, /* optinfo_flags */
565 0, /* properties_required */
566 0, /* properties_provided */
567 0, /* properties_destroyed */
568 0, /* todo_flags_start */
569 0, /* todo_flags_finish */
572 class pass_remove_cgraph_callee_edges
: public gimple_opt_pass
575 pass_remove_cgraph_callee_edges (gcc::context
*ctxt
)
576 : gimple_opt_pass (pass_data_remove_cgraph_callee_edges
, ctxt
)
579 /* opt_pass methods: */
580 opt_pass
* clone () {
581 return new pass_remove_cgraph_callee_edges (m_ctxt
);
583 virtual unsigned int execute (function
*);
585 }; // class pass_remove_cgraph_callee_edges
588 pass_remove_cgraph_callee_edges::execute (function
*)
590 cgraph_node
*node
= cgraph_node::get (current_function_decl
);
591 node
->remove_callees ();
592 node
->remove_all_references ();
599 make_pass_remove_cgraph_callee_edges (gcc::context
*ctxt
)
601 return new pass_remove_cgraph_callee_edges (ctxt
);