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 "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 class 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_node::get_create (decl
);
84 node
->mark_address_taken ();
85 ctx
->varpool_node
->add_reference (node
, IPA_REF_ADDR
);
88 if (TREE_CODE (decl
) == VAR_DECL
)
90 varpool_node
*vnode
= varpool_node::get_create (decl
);
91 ctx
->varpool_node
->add_reference (vnode
, IPA_REF_ADDR
);
97 /* Save some cycles by not walking types and declaration as we
98 won't find anything useful there anyway. */
99 if (IS_TYPE_OR_DECL_P (*tp
))
110 /* Record references to typeinfos in the type list LIST. */
113 record_type_list (struct cgraph_node
*node
, tree list
)
115 for (; list
; list
= TREE_CHAIN (list
))
117 tree type
= TREE_VALUE (list
);
120 type
= lookup_type_for_runtime (type
);
122 if (TREE_CODE (type
) == ADDR_EXPR
)
124 type
= TREE_OPERAND (type
, 0);
125 if (TREE_CODE (type
) == VAR_DECL
)
127 varpool_node
*vnode
= varpool_node::get_create (type
);
128 node
->add_reference (vnode
, IPA_REF_ADDR
);
134 /* Record all references we will introduce by producing EH tables
138 record_eh_tables (struct cgraph_node
*node
, struct function
*fun
)
142 if (DECL_FUNCTION_PERSONALITY (node
->decl
))
144 tree per_decl
= DECL_FUNCTION_PERSONALITY (node
->decl
);
145 struct cgraph_node
*per_node
= cgraph_node::get_create (per_decl
);
147 node
->add_reference (per_node
, IPA_REF_ADDR
);
148 per_node
->mark_address_taken ();
151 i
= fun
->eh
->region_tree
;
160 case ERT_MUST_NOT_THROW
:
166 for (c
= i
->u
.eh_try
.first_catch
; c
; c
= c
->next_catch
)
167 record_type_list (node
, c
->type_list
);
171 case ERT_ALLOWED_EXCEPTIONS
:
172 record_type_list (node
, i
->u
.allowed
.type_list
);
175 /* If there are sub-regions, process them. */
178 /* If there are peers, process them. */
179 else if (i
->next_peer
)
181 /* Otherwise, step back up the tree to the next peer. */
190 while (i
->next_peer
== NULL
);
196 /* Computes the frequency of the call statement so that it can be stored in
197 cgraph_edge. BB is the basic block of the call statement. */
199 compute_call_stmt_bb_frequency (tree decl
, basic_block bb
)
201 int entry_freq
= ENTRY_BLOCK_PTR_FOR_FN
202 (DECL_STRUCT_FUNCTION (decl
))->frequency
;
203 int freq
= bb
->frequency
;
205 if (profile_status_for_fn (DECL_STRUCT_FUNCTION (decl
)) == PROFILE_ABSENT
)
206 return CGRAPH_FREQ_BASE
;
209 entry_freq
= 1, freq
++;
211 freq
= freq
* CGRAPH_FREQ_BASE
/ entry_freq
;
212 if (freq
> CGRAPH_FREQ_MAX
)
213 freq
= CGRAPH_FREQ_MAX
;
218 /* Mark address taken in STMT. */
221 mark_address (gimple stmt
, tree addr
, tree
, void *data
)
223 addr
= get_base_address (addr
);
224 if (TREE_CODE (addr
) == FUNCTION_DECL
)
226 struct cgraph_node
*node
= cgraph_node::get_create (addr
);
227 node
->mark_address_taken ();
228 ((symtab_node
*)data
)->add_reference (node
, IPA_REF_ADDR
, stmt
);
230 else if (addr
&& TREE_CODE (addr
) == VAR_DECL
231 && (TREE_STATIC (addr
) || DECL_EXTERNAL (addr
)))
233 varpool_node
*vnode
= varpool_node::get_create (addr
);
235 ((symtab_node
*)data
)->add_reference (vnode
, IPA_REF_ADDR
, stmt
);
241 /* Mark load of T. */
244 mark_load (gimple stmt
, tree t
, tree
, void *data
)
246 t
= get_base_address (t
);
247 if (t
&& TREE_CODE (t
) == FUNCTION_DECL
)
249 /* ??? This can happen on platforms with descriptors when these are
250 directly manipulated in the code. Pretend that it's an address. */
251 struct cgraph_node
*node
= cgraph_node::get_create (t
);
252 node
->mark_address_taken ();
253 ((symtab_node
*)data
)->add_reference (node
, IPA_REF_ADDR
, stmt
);
255 else if (t
&& TREE_CODE (t
) == VAR_DECL
256 && (TREE_STATIC (t
) || DECL_EXTERNAL (t
)))
258 varpool_node
*vnode
= varpool_node::get_create (t
);
260 ((symtab_node
*)data
)->add_reference (vnode
, IPA_REF_LOAD
, stmt
);
265 /* Mark store of T. */
268 mark_store (gimple stmt
, tree t
, tree
, void *data
)
270 t
= get_base_address (t
);
271 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
)->add_reference (vnode
, IPA_REF_STORE
, stmt
);
281 /* Record all references from cgraph_node that are taken in statement STMT. */
284 cgraph_node::record_stmt_references (gimple stmt
)
286 walk_stmt_load_store_addr_ops (stmt
, this, mark_load
, mark_store
,
290 /* Create cgraph edges for function calls.
291 Also look for functions and variables having addresses taken. */
295 const pass_data pass_data_build_cgraph_edges
=
297 GIMPLE_PASS
, /* type */
298 "*build_cgraph_edges", /* name */
299 OPTGROUP_NONE
, /* optinfo_flags */
301 PROP_cfg
, /* properties_required */
302 0, /* properties_provided */
303 0, /* properties_destroyed */
304 0, /* todo_flags_start */
305 0, /* todo_flags_finish */
308 class pass_build_cgraph_edges
: public gimple_opt_pass
311 pass_build_cgraph_edges (gcc::context
*ctxt
)
312 : gimple_opt_pass (pass_data_build_cgraph_edges
, ctxt
)
315 /* opt_pass methods: */
316 virtual unsigned int execute (function
*);
318 }; // class pass_build_cgraph_edges
321 pass_build_cgraph_edges::execute (function
*fun
)
324 struct cgraph_node
*node
= cgraph_node::get (current_function_decl
);
325 struct pointer_set_t
*visited_nodes
= pointer_set_create ();
326 gimple_stmt_iterator gsi
;
330 /* Create the callgraph edges and record the nodes referenced by the function.
332 FOR_EACH_BB_FN (bb
, fun
)
334 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
336 gimple stmt
= gsi_stmt (gsi
);
339 if (is_gimple_debug (stmt
))
342 if (is_gimple_call (stmt
))
344 int freq
= compute_call_stmt_bb_frequency (current_function_decl
,
346 decl
= gimple_call_fndecl (stmt
);
348 node
->create_edge (cgraph_node::get_create (decl
),
349 stmt
, bb
->count
, freq
);
350 else if (gimple_call_internal_p (stmt
))
353 node
->create_indirect_edge (stmt
,
354 gimple_call_flags (stmt
),
357 node
->record_stmt_references (stmt
);
358 if (gimple_code (stmt
) == GIMPLE_OMP_PARALLEL
359 && gimple_omp_parallel_child_fn (stmt
))
361 tree fn
= gimple_omp_parallel_child_fn (stmt
);
362 node
->add_reference (cgraph_node::get_create (fn
),
365 if (gimple_code (stmt
) == GIMPLE_OMP_TASK
)
367 tree fn
= gimple_omp_task_child_fn (stmt
);
369 node
->add_reference (cgraph_node::get_create (fn
),
371 fn
= gimple_omp_task_copy_fn (stmt
);
373 node
->add_reference (cgraph_node::get_create (fn
),
377 for (gsi
= gsi_start_phis (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
378 node
->record_stmt_references (gsi_stmt (gsi
));
381 /* Look for initializers of constant variables and private statics. */
382 FOR_EACH_LOCAL_DECL (fun
, ix
, decl
)
383 if (TREE_CODE (decl
) == VAR_DECL
384 && (TREE_STATIC (decl
) && !DECL_EXTERNAL (decl
))
385 && !DECL_HAS_VALUE_EXPR_P (decl
))
386 varpool_node::finalize_decl (decl
);
387 record_eh_tables (node
, fun
);
389 pointer_set_destroy (visited_nodes
);
396 make_pass_build_cgraph_edges (gcc::context
*ctxt
)
398 return new pass_build_cgraph_edges (ctxt
);
401 /* Record references to functions and other variables present in the
402 initial value of DECL, a variable.
403 When ONLY_VARS is true, we mark needed only variables, not functions. */
406 record_references_in_initializer (tree decl
, bool only_vars
)
408 struct pointer_set_t
*visited_nodes
= pointer_set_create ();
409 varpool_node
*node
= varpool_node::get_create (decl
);
410 struct record_reference_ctx ctx
= {false, NULL
};
412 ctx
.varpool_node
= node
;
413 ctx
.only_vars
= only_vars
;
414 walk_tree (&DECL_INITIAL (decl
), record_reference
,
415 &ctx
, visited_nodes
);
416 pointer_set_destroy (visited_nodes
);
419 /* Rebuild cgraph edges for current function node. This needs to be run after
420 passes that don't update the cgraph. */
423 rebuild_cgraph_edges (void)
426 struct cgraph_node
*node
= cgraph_node::get (current_function_decl
);
427 gimple_stmt_iterator gsi
;
429 node
->remove_callees ();
430 node
->remove_all_references ();
432 node
->count
= ENTRY_BLOCK_PTR_FOR_FN (cfun
)->count
;
434 FOR_EACH_BB_FN (bb
, cfun
)
436 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
438 gimple stmt
= gsi_stmt (gsi
);
441 if (is_gimple_call (stmt
))
443 int freq
= compute_call_stmt_bb_frequency (current_function_decl
,
445 decl
= gimple_call_fndecl (stmt
);
447 node
->create_edge (cgraph_node::get_create (decl
), stmt
,
449 else if (gimple_call_internal_p (stmt
))
452 node
->create_indirect_edge (stmt
,
453 gimple_call_flags (stmt
),
456 node
->record_stmt_references (stmt
);
458 for (gsi
= gsi_start_phis (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
459 node
->record_stmt_references (gsi_stmt (gsi
));
461 record_eh_tables (node
, cfun
);
462 gcc_assert (!node
->global
.inlined_to
);
467 /* Rebuild cgraph edges for current function node. This needs to be run after
468 passes that don't update the cgraph. */
471 cgraph_rebuild_references (void)
474 struct cgraph_node
*node
= cgraph_node::get (current_function_decl
);
475 gimple_stmt_iterator gsi
;
476 struct ipa_ref
*ref
= NULL
;
479 /* Keep speculative references for further cgraph edge expansion. */
480 for (i
= 0; node
->iterate_reference (i
, ref
);)
481 if (!ref
->speculative
)
482 ref
->remove_reference ();
486 node
->count
= ENTRY_BLOCK_PTR_FOR_FN (cfun
)->count
;
488 FOR_EACH_BB_FN (bb
, cfun
)
490 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
491 node
->record_stmt_references (gsi_stmt (gsi
));
492 for (gsi
= gsi_start_phis (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
493 node
->record_stmt_references (gsi_stmt (gsi
));
495 record_eh_tables (node
, cfun
);
500 const pass_data pass_data_rebuild_cgraph_edges
=
502 GIMPLE_PASS
, /* type */
503 "*rebuild_cgraph_edges", /* name */
504 OPTGROUP_NONE
, /* optinfo_flags */
505 TV_CGRAPH
, /* tv_id */
506 PROP_cfg
, /* properties_required */
507 0, /* properties_provided */
508 0, /* properties_destroyed */
509 0, /* todo_flags_start */
510 0, /* todo_flags_finish */
513 class pass_rebuild_cgraph_edges
: public gimple_opt_pass
516 pass_rebuild_cgraph_edges (gcc::context
*ctxt
)
517 : gimple_opt_pass (pass_data_rebuild_cgraph_edges
, ctxt
)
520 /* opt_pass methods: */
521 opt_pass
* clone () { return new pass_rebuild_cgraph_edges (m_ctxt
); }
522 virtual unsigned int execute (function
*) { return rebuild_cgraph_edges (); }
524 }; // class pass_rebuild_cgraph_edges
529 make_pass_rebuild_cgraph_edges (gcc::context
*ctxt
)
531 return new pass_rebuild_cgraph_edges (ctxt
);
537 const pass_data pass_data_remove_cgraph_callee_edges
=
539 GIMPLE_PASS
, /* type */
540 "*remove_cgraph_callee_edges", /* name */
541 OPTGROUP_NONE
, /* optinfo_flags */
543 0, /* properties_required */
544 0, /* properties_provided */
545 0, /* properties_destroyed */
546 0, /* todo_flags_start */
547 0, /* todo_flags_finish */
550 class pass_remove_cgraph_callee_edges
: public gimple_opt_pass
553 pass_remove_cgraph_callee_edges (gcc::context
*ctxt
)
554 : gimple_opt_pass (pass_data_remove_cgraph_callee_edges
, ctxt
)
557 /* opt_pass methods: */
558 opt_pass
* clone () {
559 return new pass_remove_cgraph_callee_edges (m_ctxt
);
561 virtual unsigned int execute (function
*);
563 }; // class pass_remove_cgraph_callee_edges
566 pass_remove_cgraph_callee_edges::execute (function
*)
568 struct cgraph_node
*node
= cgraph_node::get (current_function_decl
);
569 node
->remove_callees ();
570 node
->remove_all_references ();
577 make_pass_remove_cgraph_callee_edges (gcc::context
*ctxt
)
579 return new pass_remove_cgraph_callee_edges (ctxt
);