1/* Callgraph construction.
2 Copyright (C) 2003-2017 Free Software Foundation, Inc.
3 Contributed by Jan Hubicka
4
5This file is part of GCC.
6
7GCC is free software; you can redistribute it and/or modify it under
8the terms of the GNU General Public License as published by the Free
9Software Foundation; either version 3, or (at your option) any later
10version.
11
12GCC is distributed in the hope that it will be useful, but WITHOUT ANY
13WARRANTY; without even the implied warranty of MERCHANTABILITY or
14FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
15for more details.
16
17You should have received a copy of the GNU General Public License
18along with GCC; see the file COPYING3. If not see
19<http://www.gnu.org/licenses/>. */
20
21#include "config.h"
22#include "system.h"
23#include "coretypes.h"
24#include "backend.h"
25#include "tree.h"
26#include "gimple.h"
27#include "tree-pass.h"
28#include "cgraph.h"
29#include "gimple-fold.h"
30#include "gimple-iterator.h"
31#include "gimple-walk.h"
32#include "ipa-utils.h"
33#include "except.h"
34
35/* Context of record_reference. */
36struct record_reference_ctx
37{
38 bool only_vars;
39 class varpool_node *varpool_node;
40};
41
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.
45 */
46
47static tree
48record_reference (tree *tp, int *walk_subtrees, void *data)
49{
50 tree t = *tp;
51 tree decl;
52 record_reference_ctx *ctx = (record_reference_ctx *)data;
53
54 t = canonicalize_constructor_val (t, NULL);
55 if (!t)
56 t = *tp;
57 else if (t != *tp)
58 *tp = t;
59
60 switch (TREE_CODE (t))
61 {
62 case VAR_DECL:
63 case FUNCTION_DECL:
64 gcc_unreachable ();
65 break;
66
67 case FDESC_EXPR:
68 case ADDR_EXPR:
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)
73 {
74 cgraph_node *node = cgraph_node::get_create (decl);
75 if (!ctx->only_vars)
76 node->mark_address_taken ();
77 ctx->varpool_node->create_reference (node, IPA_REF_ADDR);
78 }
79
80 if (VAR_P (decl))
81 {
82 varpool_node *vnode = varpool_node::get_create (decl);
83 ctx->varpool_node->create_reference (vnode, IPA_REF_ADDR);
84 }
85 *walk_subtrees = 0;
86 break;
87
88 default:
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))
92 {
93 *walk_subtrees = 0;
94 break;
95 }
96 break;
97 }
98
99 return NULL_TREE;
100}
101
102/* Record references to typeinfos in the type list LIST. */
103
104static void
105record_type_list (cgraph_node *node, tree list)
106{
107 for (; list; list = TREE_CHAIN (list))
108 {
109 tree type = TREE_VALUE (list);
110
111 if (TYPE_P (type))
112 type = lookup_type_for_runtime (type);
113 STRIP_NOPS (type);
114 if (TREE_CODE (type) == ADDR_EXPR)
115 {
116 type = TREE_OPERAND (type, 0);
117 if (VAR_P (type))
118 {
119 varpool_node *vnode = varpool_node::get_create (type);
120 node->create_reference (vnode, IPA_REF_ADDR);
121 }
122 }
123 }
124}
125
126/* Record all references we will introduce by producing EH tables
127 for NODE. */
128
129static void
130record_eh_tables (cgraph_node *node, function *fun)
131{
132 eh_region i;
133
134 if (DECL_FUNCTION_PERSONALITY (node->decl))
135 {
136 tree per_decl = DECL_FUNCTION_PERSONALITY (node->decl);
137 cgraph_node *per_node = cgraph_node::get_create (per_decl);
138
139 node->create_reference (per_node, IPA_REF_ADDR);
140 per_node->mark_address_taken ();
141 }
142
143 i = fun->eh->region_tree;
144 if (!i)
145 return;
146
147 while (1)
148 {
149 switch (i->type)
150 {
151 case ERT_CLEANUP:
152 case ERT_MUST_NOT_THROW:
153 break;
154
155 case ERT_TRY:
156 {
157 eh_catch c;
158 for (c = i->u.eh_try.first_catch; c; c = c->next_catch)
159 record_type_list (node, c->type_list);
160 }
161 break;
162
163 case ERT_ALLOWED_EXCEPTIONS:
164 record_type_list (node, i->u.allowed.type_list);
165 break;
166 }
167 /* If there are sub-regions, process them. */
168 if (i->inner)
169 i = i->inner;
170 /* If there are peers, process them. */
171 else if (i->next_peer)
172 i = i->next_peer;
173 /* Otherwise, step back up the tree to the next peer. */
174 else
175 {
176 do
177 {
178 i = i->outer;
179 if (i == NULL)
180 return;
181 }
182 while (i->next_peer == NULL);
183 i = i->next_peer;
184 }
185 }
186}
187
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. */
190int
191compute_call_stmt_bb_frequency (tree decl, basic_block bb)
192{
193 return bb->count.to_cgraph_frequency
194 (ENTRY_BLOCK_PTR_FOR_FN (DECL_STRUCT_FUNCTION (decl))->count);
195}
196
197/* Mark address taken in STMT. */
198
199static bool
200mark_address (gimple *stmt, tree addr, tree, void *data)
201{
202 addr = get_base_address (addr);
203 if (TREE_CODE (addr) == FUNCTION_DECL)
204 {
205 cgraph_node *node = cgraph_node::get_create (addr);
206 node->mark_address_taken ();
207 ((symtab_node *)data)->create_reference (node, IPA_REF_ADDR, stmt);
208 }
209 else if (addr && VAR_P (addr)
210 && (TREE_STATIC (addr) || DECL_EXTERNAL (addr)))
211 {
212 varpool_node *vnode = varpool_node::get_create (addr);
213
214 ((symtab_node *)data)->create_reference (vnode, IPA_REF_ADDR, stmt);
215 }
216
217 return false;
218}
219
220/* Mark load of T. */
221
222static bool
223mark_load (gimple *stmt, tree t, tree, void *data)
224{
225 t = get_base_address (t);
226 if (t && TREE_CODE (t) == FUNCTION_DECL)
227 {
228 /* ??? This can happen on platforms with descriptors when these are
229 directly manipulated in the code. Pretend that it's an address. */
230 cgraph_node *node = cgraph_node::get_create (t);
231 node->mark_address_taken ();
232 ((symtab_node *)data)->create_reference (node, IPA_REF_ADDR, stmt);
233 }
234 else if (t && VAR_P (t) && (TREE_STATIC (t) || DECL_EXTERNAL (t)))
235 {
236 varpool_node *vnode = varpool_node::get_create (t);
237
238 ((symtab_node *)data)->create_reference (vnode, IPA_REF_LOAD, stmt);
239 }
240 return false;
241}
242
243/* Mark store of T. */
244
245static bool
246mark_store (gimple *stmt, tree t, tree, void *data)
247{
248 t = get_base_address (t);
249 if (t && VAR_P (t) && (TREE_STATIC (t) || DECL_EXTERNAL (t)))
250 {
251 varpool_node *vnode = varpool_node::get_create (t);
252
253 ((symtab_node *)data)->create_reference (vnode, IPA_REF_STORE, stmt);
254 }
255 return false;
256}
257
258/* Record all references from cgraph_node that are taken in statement STMT. */
259
260void
261cgraph_node::record_stmt_references (gimple *stmt)
262{
263 walk_stmt_load_store_addr_ops (stmt, this, mark_load, mark_store,
264 mark_address);
265}
266
267/* Create cgraph edges for function calls.
268 Also look for functions and variables having addresses taken. */
269
270namespace {
271
272const pass_data pass_data_build_cgraph_edges =
273{
274 GIMPLE_PASS, /* type */
275 "*build_cgraph_edges", /* name */
276 OPTGROUP_NONE, /* optinfo_flags */
277 TV_NONE, /* tv_id */
278 PROP_cfg, /* properties_required */
279 0, /* properties_provided */
280 0, /* properties_destroyed */
281 0, /* todo_flags_start */
282 0, /* todo_flags_finish */
283};
284
285class pass_build_cgraph_edges : public gimple_opt_pass
286{
287public:
288 pass_build_cgraph_edges (gcc::context *ctxt)
289 : gimple_opt_pass (pass_data_build_cgraph_edges, ctxt)
290 {}
291
292 /* opt_pass methods: */
293 virtual unsigned int execute (function *);
294
295}; // class pass_build_cgraph_edges
296
297unsigned int
298pass_build_cgraph_edges::execute (function *fun)
299{
300 basic_block bb;
301 cgraph_node *node = cgraph_node::get (current_function_decl);
302 gimple_stmt_iterator gsi;
303 tree decl;
304 unsigned ix;
305
306 /* Create the callgraph edges and record the nodes referenced by the function.
307 body. */
308 FOR_EACH_BB_FN (bb, fun)
309 {
310 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
311 {
312 gimple *stmt = gsi_stmt (gsi);
313 tree decl;
314
315 if (is_gimple_debug (stmt))
316 continue;
317
318 if (gcall *call_stmt = dyn_cast <gcall *> (stmt))
319 {
320 decl = gimple_call_fndecl (call_stmt);
321 if (decl)
322 node->create_edge (cgraph_node::get_create (decl), call_stmt, bb->count);
323 else if (gimple_call_internal_p (call_stmt))
324 ;
325 else
326 node->create_indirect_edge (call_stmt,
327 gimple_call_flags (call_stmt),
328 bb->count);
329 }
330 node->record_stmt_references (stmt);
331 if (gomp_parallel *omp_par_stmt = dyn_cast <gomp_parallel *> (stmt))
332 {
333 tree fn = gimple_omp_parallel_child_fn (omp_par_stmt);
334 node->create_reference (cgraph_node::get_create (fn),
335 IPA_REF_ADDR, stmt);
336 }
337 if (gimple_code (stmt) == GIMPLE_OMP_TASK)
338 {
339 tree fn = gimple_omp_task_child_fn (stmt);
340 if (fn)
341 node->create_reference (cgraph_node::get_create (fn),
342 IPA_REF_ADDR, stmt);
343 fn = gimple_omp_task_copy_fn (stmt);
344 if (fn)
345 node->create_reference (cgraph_node::get_create (fn),
346 IPA_REF_ADDR, stmt);
347 }
348 }
349 for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi))
350 node->record_stmt_references (gsi_stmt (gsi));
351 }
352
353 /* Look for initializers of constant variables and private statics. */
354 FOR_EACH_LOCAL_DECL (fun, ix, decl)
355 if (VAR_P (decl)
356 && (TREE_STATIC (decl) && !DECL_EXTERNAL (decl))
357 && !DECL_HAS_VALUE_EXPR_P (decl)
358 && TREE_TYPE (decl) != error_mark_node)
359 varpool_node::finalize_decl (decl);
360 record_eh_tables (node, fun);
361
362 return 0;
363}
364
365} // anon namespace
366
367gimple_opt_pass *
368make_pass_build_cgraph_edges (gcc::context *ctxt)
369{
370 return new pass_build_cgraph_edges (ctxt);
371}
372
373/* Record references to functions and other variables present in the
374 initial value of DECL, a variable.
375 When ONLY_VARS is true, we mark needed only variables, not functions. */
376
377void
378record_references_in_initializer (tree decl, bool only_vars)
379{
380 varpool_node *node = varpool_node::get_create (decl);
381 hash_set<tree> visited_nodes;
382 record_reference_ctx ctx = {false, NULL};
383
384 ctx.varpool_node = node;
385 ctx.only_vars = only_vars;
386 walk_tree (&DECL_INITIAL (decl), record_reference,
387 &ctx, &visited_nodes);
388}
389
390/* Rebuild cgraph edges for current function node. This needs to be run after
391 passes that don't update the cgraph. */
392
393unsigned int
394cgraph_edge::rebuild_edges (void)
395{
396 basic_block bb;
397 cgraph_node *node = cgraph_node::get (current_function_decl);
398 gimple_stmt_iterator gsi;
399
400 node->remove_callees ();
401 node->remove_all_references ();
402
403 node->count = ENTRY_BLOCK_PTR_FOR_FN (cfun)->count;
404
405 FOR_EACH_BB_FN (bb, cfun)
406 {
407 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
408 {
409 gimple *stmt = gsi_stmt (gsi);
410 tree decl;
411
412 if (gcall *call_stmt = dyn_cast <gcall *> (stmt))
413 {
414 decl = gimple_call_fndecl (call_stmt);
415 if (decl)
416 node->create_edge (cgraph_node::get_create (decl), call_stmt,
417 bb->count);
418 else if (gimple_call_internal_p (call_stmt))
419 ;
420 else
421 node->create_indirect_edge (call_stmt,
422 gimple_call_flags (call_stmt),
423 bb->count);
424 }
425 node->record_stmt_references (stmt);
426 }
427 for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi))
428 node->record_stmt_references (gsi_stmt (gsi));
429 }
430 record_eh_tables (node, cfun);
431 gcc_assert (!node->global.inlined_to);
432
433 if (node->instrumented_version
434 && !node->instrumentation_clone)
435 node->create_reference (node->instrumented_version, IPA_REF_CHKP, NULL);
436
437 return 0;
438}
439
440/* Rebuild cgraph references for current function node. This needs to be run
441 after passes that don't update the cgraph. */
442
443void
444cgraph_edge::rebuild_references (void)
445{
446 basic_block bb;
447 cgraph_node *node = cgraph_node::get (current_function_decl);
448 gimple_stmt_iterator gsi;
449 ipa_ref *ref = NULL;
450 int i;
451
452 /* Keep speculative references for further cgraph edge expansion. */
453 for (i = 0; node->iterate_reference (i, ref);)
454 if (!ref->speculative)
455 ref->remove_reference ();
456 else
457 i++;
458
459 FOR_EACH_BB_FN (bb, cfun)
460 {
461 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
462 node->record_stmt_references (gsi_stmt (gsi));
463 for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi))
464 node->record_stmt_references (gsi_stmt (gsi));
465 }
466 record_eh_tables (node, cfun);
467
468 if (node->instrumented_version
469 && !node->instrumentation_clone)
470 node->create_reference (node->instrumented_version, IPA_REF_CHKP, NULL);
471}
472
473namespace {
474
475const pass_data pass_data_rebuild_cgraph_edges =
476{
477 GIMPLE_PASS, /* type */
478 "*rebuild_cgraph_edges", /* name */
479 OPTGROUP_NONE, /* optinfo_flags */
480 TV_CGRAPH, /* tv_id */
481 PROP_cfg, /* properties_required */
482 0, /* properties_provided */
483 0, /* properties_destroyed */
484 0, /* todo_flags_start */
485 0, /* todo_flags_finish */
486};
487
488class pass_rebuild_cgraph_edges : public gimple_opt_pass
489{
490public:
491 pass_rebuild_cgraph_edges (gcc::context *ctxt)
492 : gimple_opt_pass (pass_data_rebuild_cgraph_edges, ctxt)
493 {}
494
495 /* opt_pass methods: */
496 opt_pass * clone () { return new pass_rebuild_cgraph_edges (m_ctxt); }
497 virtual unsigned int execute (function *)
498 {
499 return cgraph_edge::rebuild_edges ();
500 }
501
502}; // class pass_rebuild_cgraph_edges
503
504} // anon namespace
505
506gimple_opt_pass *
507make_pass_rebuild_cgraph_edges (gcc::context *ctxt)
508{
509 return new pass_rebuild_cgraph_edges (ctxt);
510}
511
512
513namespace {
514
515const pass_data pass_data_remove_cgraph_callee_edges =
516{
517 GIMPLE_PASS, /* type */
518 "*remove_cgraph_callee_edges", /* name */
519 OPTGROUP_NONE, /* optinfo_flags */
520 TV_NONE, /* tv_id */
521 0, /* properties_required */
522 0, /* properties_provided */
523 0, /* properties_destroyed */
524 0, /* todo_flags_start */
525 0, /* todo_flags_finish */
526};
527
528class pass_remove_cgraph_callee_edges : public gimple_opt_pass
529{
530public:
531 pass_remove_cgraph_callee_edges (gcc::context *ctxt)
532 : gimple_opt_pass (pass_data_remove_cgraph_callee_edges, ctxt)
533 {}
534
535 /* opt_pass methods: */
536 opt_pass * clone () {
537 return new pass_remove_cgraph_callee_edges (m_ctxt);
538 }
539 virtual unsigned int execute (function *);
540
541}; // class pass_remove_cgraph_callee_edges
542
543unsigned int
544pass_remove_cgraph_callee_edges::execute (function *)
545{
546 cgraph_node *node = cgraph_node::get (current_function_decl);
547 node->remove_callees ();
548 node->remove_all_references ();
549 return 0;
550}
551
552} // anon namespace
553
554gimple_opt_pass *
555make_pass_remove_cgraph_callee_edges (gcc::context *ctxt)
556{
557 return new pass_remove_cgraph_callee_edges (ctxt);
558}
559