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