1 /* Callgraph construction.
2 Copyright (C) 2003-2014 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 "basic-block.h"
27 #include "tree-ssa-alias.h"
28 #include "internal-fn.h"
29 #include "gimple-fold.h"
30 #include "gimple-expr.h"
33 #include "gimple-iterator.h"
34 #include "gimple-walk.h"
35 #include "langhooks.h"
37 #include "tree-pass.h"
38 #include "ipa-utils.h"
40 #include "ipa-inline.h"
42 /* Context of record_reference. */
43 struct record_reference_ctx
46 class varpool_node
*varpool_node
;
49 /* Walk tree and record all calls and references to functions/variables.
50 Called via walk_tree: TP is pointer to tree to be examined.
51 When DATA is non-null, record references to callgraph.
55 record_reference (tree
*tp
, int *walk_subtrees
, void *data
)
59 struct record_reference_ctx
*ctx
= (struct record_reference_ctx
*)data
;
61 t
= canonicalize_constructor_val (t
, NULL
);
67 switch (TREE_CODE (t
))
76 /* Record dereferences to the functions. This makes the
77 functions reachable unconditionally. */
78 decl
= get_base_var (*tp
);
79 if (TREE_CODE (decl
) == FUNCTION_DECL
)
81 struct cgraph_node
*node
= cgraph_node::get_create (decl
);
83 node
->mark_address_taken ();
84 ctx
->varpool_node
->add_reference (node
, IPA_REF_ADDR
);
87 if (TREE_CODE (decl
) == VAR_DECL
)
89 varpool_node
*vnode
= varpool_node::get_create (decl
);
90 ctx
->varpool_node
->add_reference (vnode
, IPA_REF_ADDR
);
96 /* Save some cycles by not walking types and declaration as we
97 won't find anything useful there anyway. */
98 if (IS_TYPE_OR_DECL_P (*tp
))
109 /* Record references to typeinfos in the type list LIST. */
112 record_type_list (struct cgraph_node
*node
, tree list
)
114 for (; list
; list
= TREE_CHAIN (list
))
116 tree type
= TREE_VALUE (list
);
119 type
= lookup_type_for_runtime (type
);
121 if (TREE_CODE (type
) == ADDR_EXPR
)
123 type
= TREE_OPERAND (type
, 0);
124 if (TREE_CODE (type
) == VAR_DECL
)
126 varpool_node
*vnode
= varpool_node::get_create (type
);
127 node
->add_reference (vnode
, IPA_REF_ADDR
);
133 /* Record all references we will introduce by producing EH tables
137 record_eh_tables (struct cgraph_node
*node
, struct function
*fun
)
141 if (DECL_FUNCTION_PERSONALITY (node
->decl
))
143 tree per_decl
= DECL_FUNCTION_PERSONALITY (node
->decl
);
144 struct cgraph_node
*per_node
= cgraph_node::get_create (per_decl
);
146 node
->add_reference (per_node
, IPA_REF_ADDR
);
147 per_node
->mark_address_taken ();
150 i
= fun
->eh
->region_tree
;
159 case ERT_MUST_NOT_THROW
:
165 for (c
= i
->u
.eh_try
.first_catch
; c
; c
= c
->next_catch
)
166 record_type_list (node
, c
->type_list
);
170 case ERT_ALLOWED_EXCEPTIONS
:
171 record_type_list (node
, i
->u
.allowed
.type_list
);
174 /* If there are sub-regions, process them. */
177 /* If there are peers, process them. */
178 else if (i
->next_peer
)
180 /* Otherwise, step back up the tree to the next peer. */
189 while (i
->next_peer
== NULL
);
195 /* Computes the frequency of the call statement so that it can be stored in
196 cgraph_edge. BB is the basic block of the call statement. */
198 compute_call_stmt_bb_frequency (tree decl
, basic_block bb
)
200 int entry_freq
= ENTRY_BLOCK_PTR_FOR_FN
201 (DECL_STRUCT_FUNCTION (decl
))->frequency
;
202 int freq
= bb
->frequency
;
204 if (profile_status_for_fn (DECL_STRUCT_FUNCTION (decl
)) == PROFILE_ABSENT
)
205 return CGRAPH_FREQ_BASE
;
208 entry_freq
= 1, freq
++;
210 freq
= freq
* CGRAPH_FREQ_BASE
/ entry_freq
;
211 if (freq
> CGRAPH_FREQ_MAX
)
212 freq
= CGRAPH_FREQ_MAX
;
217 /* Mark address taken in STMT. */
220 mark_address (gimple stmt
, tree addr
, tree
, void *data
)
222 addr
= get_base_address (addr
);
223 if (TREE_CODE (addr
) == FUNCTION_DECL
)
225 struct cgraph_node
*node
= cgraph_node::get_create (addr
);
226 node
->mark_address_taken ();
227 ((symtab_node
*)data
)->add_reference (node
, IPA_REF_ADDR
, stmt
);
229 else if (addr
&& TREE_CODE (addr
) == VAR_DECL
230 && (TREE_STATIC (addr
) || DECL_EXTERNAL (addr
)))
232 varpool_node
*vnode
= varpool_node::get_create (addr
);
234 ((symtab_node
*)data
)->add_reference (vnode
, IPA_REF_ADDR
, stmt
);
240 /* Mark load of T. */
243 mark_load (gimple stmt
, tree t
, tree
, void *data
)
245 t
= get_base_address (t
);
246 if (t
&& TREE_CODE (t
) == FUNCTION_DECL
)
248 /* ??? This can happen on platforms with descriptors when these are
249 directly manipulated in the code. Pretend that it's an address. */
250 struct cgraph_node
*node
= cgraph_node::get_create (t
);
251 node
->mark_address_taken ();
252 ((symtab_node
*)data
)->add_reference (node
, IPA_REF_ADDR
, stmt
);
254 else if (t
&& TREE_CODE (t
) == VAR_DECL
255 && (TREE_STATIC (t
) || DECL_EXTERNAL (t
)))
257 varpool_node
*vnode
= varpool_node::get_create (t
);
259 ((symtab_node
*)data
)->add_reference (vnode
, IPA_REF_LOAD
, stmt
);
264 /* Mark store of T. */
267 mark_store (gimple stmt
, tree t
, tree
, void *data
)
269 t
= get_base_address (t
);
270 if (t
&& TREE_CODE (t
) == VAR_DECL
271 && (TREE_STATIC (t
) || DECL_EXTERNAL (t
)))
273 varpool_node
*vnode
= varpool_node::get_create (t
);
275 ((symtab_node
*)data
)->add_reference (vnode
, IPA_REF_STORE
, stmt
);
280 /* Record all references from cgraph_node that are taken in statement STMT. */
283 cgraph_node::record_stmt_references (gimple stmt
)
285 walk_stmt_load_store_addr_ops (stmt
, this, mark_load
, mark_store
,
289 /* Create cgraph edges for function calls.
290 Also look for functions and variables having addresses taken. */
294 const pass_data pass_data_build_cgraph_edges
=
296 GIMPLE_PASS
, /* type */
297 "*build_cgraph_edges", /* name */
298 OPTGROUP_NONE
, /* optinfo_flags */
300 PROP_cfg
, /* properties_required */
301 0, /* properties_provided */
302 0, /* properties_destroyed */
303 0, /* todo_flags_start */
304 0, /* todo_flags_finish */
307 class pass_build_cgraph_edges
: public gimple_opt_pass
310 pass_build_cgraph_edges (gcc::context
*ctxt
)
311 : gimple_opt_pass (pass_data_build_cgraph_edges
, ctxt
)
314 /* opt_pass methods: */
315 virtual unsigned int execute (function
*);
317 }; // class pass_build_cgraph_edges
320 pass_build_cgraph_edges::execute (function
*fun
)
323 struct cgraph_node
*node
= cgraph_node::get (current_function_decl
);
324 gimple_stmt_iterator gsi
;
328 /* Create the callgraph edges and record the nodes referenced by the function.
330 FOR_EACH_BB_FN (bb
, fun
)
332 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
334 gimple stmt
= gsi_stmt (gsi
);
337 if (is_gimple_debug (stmt
))
340 if (is_gimple_call (stmt
))
342 int freq
= compute_call_stmt_bb_frequency (current_function_decl
,
344 decl
= gimple_call_fndecl (stmt
);
346 node
->create_edge (cgraph_node::get_create (decl
),
347 stmt
, bb
->count
, freq
);
348 else if (gimple_call_internal_p (stmt
))
351 node
->create_indirect_edge (stmt
,
352 gimple_call_flags (stmt
),
355 node
->record_stmt_references (stmt
);
356 if (gimple_code (stmt
) == GIMPLE_OMP_PARALLEL
357 && gimple_omp_parallel_child_fn (stmt
))
359 tree fn
= gimple_omp_parallel_child_fn (stmt
);
360 node
->add_reference (cgraph_node::get_create (fn
),
363 if (gimple_code (stmt
) == GIMPLE_OMP_TASK
)
365 tree fn
= gimple_omp_task_child_fn (stmt
);
367 node
->add_reference (cgraph_node::get_create (fn
),
369 fn
= gimple_omp_task_copy_fn (stmt
);
371 node
->add_reference (cgraph_node::get_create (fn
),
375 for (gsi
= gsi_start_phis (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
376 node
->record_stmt_references (gsi_stmt (gsi
));
379 /* Look for initializers of constant variables and private statics. */
380 FOR_EACH_LOCAL_DECL (fun
, ix
, decl
)
381 if (TREE_CODE (decl
) == VAR_DECL
382 && (TREE_STATIC (decl
) && !DECL_EXTERNAL (decl
))
383 && !DECL_HAS_VALUE_EXPR_P (decl
))
384 varpool_node::finalize_decl (decl
);
385 record_eh_tables (node
, fun
);
393 make_pass_build_cgraph_edges (gcc::context
*ctxt
)
395 return new pass_build_cgraph_edges (ctxt
);
398 /* Record references to functions and other variables present in the
399 initial value of DECL, a variable.
400 When ONLY_VARS is true, we mark needed only variables, not functions. */
403 record_references_in_initializer (tree decl
, bool only_vars
)
405 varpool_node
*node
= varpool_node::get_create (decl
);
406 hash_set
<tree
> visited_nodes
;
407 struct record_reference_ctx ctx
= {false, NULL
};
409 ctx
.varpool_node
= node
;
410 ctx
.only_vars
= only_vars
;
411 walk_tree (&DECL_INITIAL (decl
), record_reference
,
412 &ctx
, &visited_nodes
);
415 /* Rebuild cgraph edges for current function node. This needs to be run after
416 passes that don't update the cgraph. */
419 rebuild_cgraph_edges (void)
422 struct cgraph_node
*node
= cgraph_node::get (current_function_decl
);
423 gimple_stmt_iterator gsi
;
425 node
->remove_callees ();
426 node
->remove_all_references ();
428 node
->count
= ENTRY_BLOCK_PTR_FOR_FN (cfun
)->count
;
430 FOR_EACH_BB_FN (bb
, cfun
)
432 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
434 gimple stmt
= gsi_stmt (gsi
);
437 if (is_gimple_call (stmt
))
439 int freq
= compute_call_stmt_bb_frequency (current_function_decl
,
441 decl
= gimple_call_fndecl (stmt
);
443 node
->create_edge (cgraph_node::get_create (decl
), stmt
,
445 else if (gimple_call_internal_p (stmt
))
448 node
->create_indirect_edge (stmt
,
449 gimple_call_flags (stmt
),
452 node
->record_stmt_references (stmt
);
454 for (gsi
= gsi_start_phis (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
455 node
->record_stmt_references (gsi_stmt (gsi
));
457 record_eh_tables (node
, cfun
);
458 gcc_assert (!node
->global
.inlined_to
);
463 /* Rebuild cgraph edges for current function node. This needs to be run after
464 passes that don't update the cgraph. */
467 cgraph_rebuild_references (void)
470 struct cgraph_node
*node
= cgraph_node::get (current_function_decl
);
471 gimple_stmt_iterator gsi
;
472 struct ipa_ref
*ref
= NULL
;
475 /* Keep speculative references for further cgraph edge expansion. */
476 for (i
= 0; node
->iterate_reference (i
, ref
);)
477 if (!ref
->speculative
)
478 ref
->remove_reference ();
482 node
->count
= ENTRY_BLOCK_PTR_FOR_FN (cfun
)->count
;
484 FOR_EACH_BB_FN (bb
, cfun
)
486 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
487 node
->record_stmt_references (gsi_stmt (gsi
));
488 for (gsi
= gsi_start_phis (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
489 node
->record_stmt_references (gsi_stmt (gsi
));
491 record_eh_tables (node
, cfun
);
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
*) { return rebuild_cgraph_edges (); }
520 }; // class pass_rebuild_cgraph_edges
525 make_pass_rebuild_cgraph_edges (gcc::context
*ctxt
)
527 return new pass_rebuild_cgraph_edges (ctxt
);
533 const pass_data pass_data_remove_cgraph_callee_edges
=
535 GIMPLE_PASS
, /* type */
536 "*remove_cgraph_callee_edges", /* name */
537 OPTGROUP_NONE
, /* optinfo_flags */
539 0, /* properties_required */
540 0, /* properties_provided */
541 0, /* properties_destroyed */
542 0, /* todo_flags_start */
543 0, /* todo_flags_finish */
546 class pass_remove_cgraph_callee_edges
: public gimple_opt_pass
549 pass_remove_cgraph_callee_edges (gcc::context
*ctxt
)
550 : gimple_opt_pass (pass_data_remove_cgraph_callee_edges
, ctxt
)
553 /* opt_pass methods: */
554 opt_pass
* clone () {
555 return new pass_remove_cgraph_callee_edges (m_ctxt
);
557 virtual unsigned int execute (function
*);
559 }; // class pass_remove_cgraph_callee_edges
562 pass_remove_cgraph_callee_edges::execute (function
*)
564 struct cgraph_node
*node
= cgraph_node::get (current_function_decl
);
565 node
->remove_callees ();
566 node
->remove_all_references ();
573 make_pass_remove_cgraph_callee_edges (gcc::context
*ctxt
)
575 return new pass_remove_cgraph_callee_edges (ctxt
);