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