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

source code of gcc/cgraphbuild.cc