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 14834692 : record_reference (tree *tp, int *walk_subtrees, void *data)
49 : {
50 14834727 : tree t = *tp;
51 14834727 : tree decl;
52 14834727 : record_reference_ctx *ctx = (record_reference_ctx *)data;
53 :
54 14834727 : t = canonicalize_constructor_val (t, NULL);
55 14834727 : if (!t)
56 83 : t = *tp;
57 14834644 : else if (t != *tp)
58 4468205 : *tp = t;
59 :
60 14834727 : switch (TREE_CODE (t))
61 : {
62 0 : case VAR_DECL:
63 0 : case FUNCTION_DECL:
64 0 : gcc_unreachable ();
65 4669169 : break;
66 :
67 4669169 : case FDESC_EXPR:
68 4669169 : case ADDR_EXPR:
69 : /* Record dereferences to the functions. This makes the
70 : functions reachable unconditionally. */
71 4669169 : decl = get_base_var (*tp);
72 4669169 : if (TREE_CODE (decl) == FUNCTION_DECL)
73 : {
74 1131273 : cgraph_node *node = cgraph_node::get_create (decl);
75 1131273 : if (!ctx->only_vars)
76 1131273 : node->mark_address_taken ();
77 1131273 : ctx->varpool_node->create_reference (node, IPA_REF_ADDR);
78 : }
79 :
80 4669169 : 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 2611753 : 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 2611718 : varpool_node *vnode = varpool_node::get_create (decl);
94 2611718 : ctx->varpool_node->create_reference (vnode, IPA_REF_ADDR);
95 : }
96 4669134 : *walk_subtrees = 0;
97 4669134 : break;
98 :
99 10165558 : default:
100 : /* Save some cycles by not walking types and declaration as we
101 : won't find anything useful there anyway. */
102 10165558 : 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 200909 : record_type_list (cgraph_node *node, tree list)
117 : {
118 227957 : for (; list; list = TREE_CHAIN (list))
119 : {
120 27048 : tree type = TREE_VALUE (list);
121 :
122 27048 : if (TYPE_P (type))
123 26431 : type = lookup_type_for_runtime (type);
124 27048 : STRIP_NOPS (type);
125 27048 : if (TREE_CODE (type) == ADDR_EXPR)
126 : {
127 27048 : type = TREE_OPERAND (type, 0);
128 27048 : if (VAR_P (type))
129 : {
130 27048 : varpool_node *vnode = varpool_node::get_create (type);
131 27048 : node->create_reference (vnode, IPA_REF_ADDR);
132 : }
133 : }
134 : }
135 200909 : }
136 :
137 : /* Record all references we will introduce by producing EH tables
138 : for NODE. */
139 :
140 : static void
141 12406235 : record_eh_tables (cgraph_node *node, function *fun)
142 : {
143 12406235 : eh_region i;
144 :
145 12406235 : if (DECL_FUNCTION_PERSONALITY (node->decl))
146 : {
147 2571784 : tree per_decl = DECL_FUNCTION_PERSONALITY (node->decl);
148 2571784 : cgraph_node *per_node = cgraph_node::get_create (per_decl);
149 :
150 2571784 : node->create_reference (per_node, IPA_REF_ADDR);
151 2571784 : per_node->mark_address_taken ();
152 : }
153 :
154 12406235 : i = fun->eh->region_tree;
155 12406235 : if (!i)
156 : return;
157 :
158 8575114 : while (1)
159 : {
160 8575114 : switch (i->type)
161 : {
162 : case ERT_CLEANUP:
163 : case ERT_MUST_NOT_THROW:
164 : break;
165 :
166 183919 : case ERT_TRY:
167 183919 : {
168 183919 : eh_catch c;
169 365492 : for (c = i->u.eh_try.first_catch; c; c = c->next_catch)
170 181573 : record_type_list (node, c->type_list);
171 : }
172 : break;
173 :
174 19336 : case ERT_ALLOWED_EXCEPTIONS:
175 19336 : record_type_list (node, i->u.allowed.type_list);
176 19336 : break;
177 : }
178 : /* If there are sub-regions, process them. */
179 8575114 : if (i->inner)
180 : i = i->inner;
181 : /* If there are peers, process them. */
182 6654072 : 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 5499330 : do
188 : {
189 5499330 : i = i->outer;
190 5499330 : if (i == NULL)
191 : return;
192 : }
193 1921042 : 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 33948339 : mark_address (gimple *stmt, tree addr, tree, void *data)
212 : {
213 33948339 : addr = get_base_address (addr);
214 33948339 : if (TREE_CODE (addr) == FUNCTION_DECL)
215 : {
216 1131977 : cgraph_node *caller = (cgraph_node *) data;
217 1131977 : 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 1131977 : cgraph_edge *e = caller->get_edge (stmt);
222 1131977 : if (e && e->has_callback)
223 : {
224 531 : for (cgraph_edge *cbe = e->first_callback_edge ();
225 560 : cbe;
226 29 : cbe = cbe->next_callback_edge ())
227 : {
228 29 : if (cbe->callee->is_clone_of (node))
229 : {
230 0 : node = cbe->callee;
231 0 : break;
232 : }
233 : }
234 : }
235 1131977 : node->mark_address_taken ();
236 1131977 : caller->create_reference (node, IPA_REF_ADDR, stmt);
237 : }
238 32816362 : else if (addr && VAR_P (addr)
239 19633514 : && (TREE_STATIC (addr) || DECL_EXTERNAL (addr)))
240 : {
241 8104529 : varpool_node *vnode = varpool_node::get_create (addr);
242 :
243 8104529 : ((symtab_node *)data)->create_reference (vnode, IPA_REF_ADDR, stmt);
244 : }
245 :
246 33948339 : return false;
247 : }
248 :
249 : /* Mark load of T. */
250 :
251 : static bool
252 62658332 : mark_load (gimple *stmt, tree t, tree, void *data)
253 : {
254 62658332 : t = get_base_address (t);
255 62658332 : 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 62658227 : else if (t && VAR_P (t) && (TREE_STATIC (t) || DECL_EXTERNAL (t)))
264 : {
265 11393695 : varpool_node *vnode = varpool_node::get_create (t);
266 :
267 11393695 : ((symtab_node *)data)->create_reference (vnode, IPA_REF_LOAD, stmt);
268 : }
269 62658332 : return false;
270 : }
271 :
272 : /* Mark store of T. */
273 :
274 : static bool
275 63968596 : mark_store (gimple *stmt, tree t, tree, void *data)
276 : {
277 63968596 : t = get_base_address (t);
278 63968596 : if (t && VAR_P (t) && (TREE_STATIC (t) || DECL_EXTERNAL (t)))
279 : {
280 5710425 : varpool_node *vnode = varpool_node::get_create (t);
281 :
282 5710425 : ((symtab_node *)data)->create_reference (vnode, IPA_REF_STORE, stmt);
283 : }
284 63968596 : return false;
285 : }
286 :
287 : /* Record all references from cgraph_node that are taken in statement STMT. */
288 :
289 : void
290 319859637 : cgraph_node::record_stmt_references (gimple *stmt)
291 : {
292 319859637 : walk_stmt_load_store_addr_ops (stmt, this, mark_load, mark_store,
293 : mark_address);
294 319859637 : }
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 294196 : pass_build_cgraph_edges (gcc::context *ctxt)
318 588392 : : 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 3027071 : pass_build_cgraph_edges::execute (function *fun)
328 : {
329 3027071 : basic_block bb;
330 3027071 : cgraph_node *node = cgraph_node::get (current_function_decl);
331 3027071 : gimple_stmt_iterator gsi;
332 3027071 : tree decl;
333 3027071 : unsigned ix;
334 :
335 : /* Create the callgraph edges and record the nodes referenced by the function.
336 : body. */
337 20628700 : FOR_EACH_BB_FN (bb, fun)
338 : {
339 101810533 : for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
340 : {
341 66607275 : gimple *stmt = gsi_stmt (gsi);
342 66607275 : tree decl;
343 :
344 66607275 : if (is_gimple_debug (stmt))
345 2377363 : continue;
346 :
347 64229912 : if (gcall *call_stmt = dyn_cast <gcall *> (stmt))
348 : {
349 10575182 : decl = gimple_call_fndecl (call_stmt);
350 10575182 : if (decl)
351 10025086 : node->create_edge (cgraph_node::get_create (decl), call_stmt, bb->count);
352 550096 : else if (gimple_call_internal_p (call_stmt))
353 : ;
354 : else
355 164169 : node->create_indirect_edge (call_stmt,
356 : gimple_call_flags (call_stmt),
357 : bb->count);
358 : }
359 64229912 : node->record_stmt_references (stmt);
360 64229912 : 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 64229912 : 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 17601629 : 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 21087327 : FOR_EACH_LOCAL_DECL (fun, ix, decl)
384 15820736 : if (VAR_P (decl)
385 15820736 : && (TREE_STATIC (decl) && !DECL_EXTERNAL (decl))
386 295523 : && !DECL_HAS_VALUE_EXPR_P (decl)
387 16068771 : && TREE_TYPE (decl) != error_mark_node)
388 247966 : varpool_node::finalize_decl (decl);
389 3027071 : record_eh_tables (node, fun);
390 :
391 3027071 : return 0;
392 : }
393 :
394 : } // anon namespace
395 :
396 : gimple_opt_pass *
397 294196 : make_pass_build_cgraph_edges (gcc::context *ctxt)
398 : {
399 294196 : 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 2031505 : record_references_in_initializer (tree decl, bool only_vars)
408 : {
409 2031505 : varpool_node *node = varpool_node::get_create (decl);
410 2031505 : hash_set<tree> visited_nodes;
411 2031505 : record_reference_ctx ctx = {false, NULL};
412 :
413 2031505 : ctx.varpool_node = node;
414 2031505 : ctx.only_vars = only_vars;
415 2031505 : walk_tree (&DECL_INITIAL (decl), record_reference,
416 : &ctx, &visited_nodes);
417 2031505 : }
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 9127399 : cgraph_edge::rebuild_edges (void)
424 : {
425 9127399 : basic_block bb;
426 9127399 : cgraph_node *node = cgraph_node::get (current_function_decl);
427 9127399 : gimple_stmt_iterator gsi;
428 :
429 9127399 : node->remove_callees ();
430 9127399 : node->remove_all_references ();
431 :
432 9127399 : node->count = ENTRY_BLOCK_PTR_FOR_FN (cfun)->count;
433 :
434 60466409 : FOR_EACH_BB_FN (bb, cfun)
435 : {
436 331680816 : for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
437 : {
438 229002796 : gimple *stmt = gsi_stmt (gsi);
439 229002796 : tree decl;
440 :
441 229002796 : if (gcall *call_stmt = dyn_cast <gcall *> (stmt))
442 : {
443 30006486 : decl = gimple_call_fndecl (call_stmt);
444 30006486 : if (decl)
445 27721499 : node->create_edge (cgraph_node::get_create (decl), call_stmt,
446 : bb->count);
447 2284987 : else if (gimple_call_internal_p (call_stmt))
448 : ;
449 : else
450 508191 : node->create_indirect_edge (call_stmt,
451 : gimple_call_flags (call_stmt),
452 : bb->count);
453 : }
454 229002796 : node->record_stmt_references (stmt);
455 : }
456 64673911 : for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi))
457 13334901 : node->record_stmt_references (gsi_stmt (gsi));
458 : }
459 9127399 : record_eh_tables (node, cfun);
460 9127399 : gcc_assert (!node->inlined_to);
461 9127399 : 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 251765 : cgraph_edge::rebuild_references (void)
469 : {
470 251765 : basic_block bb;
471 251765 : cgraph_node *node = cgraph_node::get (current_function_decl);
472 251765 : gimple_stmt_iterator gsi;
473 251765 : ipa_ref *ref = NULL;
474 251765 : int i;
475 :
476 : /* Keep speculative references for further cgraph edge expansion. */
477 710935 : for (i = 0; node->iterate_reference (i, ref);)
478 207405 : if (!ref->speculative)
479 205145 : ref->remove_reference ();
480 : else
481 2260 : i++;
482 :
483 2329734 : FOR_EACH_BB_FN (bb, cfun)
484 : {
485 17114231 : for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
486 12958293 : node->record_stmt_references (gsi_stmt (gsi));
487 2411704 : for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi))
488 333735 : node->record_stmt_references (gsi_stmt (gsi));
489 : }
490 251765 : record_eh_tables (node, cfun);
491 251765 : }
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 1176784 : pass_rebuild_cgraph_edges (gcc::context *ctxt)
512 2353568 : : gimple_opt_pass (pass_data_rebuild_cgraph_edges, ctxt)
513 : {}
514 :
515 : /* opt_pass methods: */
516 882588 : opt_pass * clone () final override
517 : {
518 882588 : return new pass_rebuild_cgraph_edges (m_ctxt);
519 : }
520 9012744 : unsigned int execute (function *) final override
521 : {
522 9012744 : return cgraph_edge::rebuild_edges ();
523 : }
524 :
525 : }; // class pass_rebuild_cgraph_edges
526 :
527 : } // anon namespace
528 :
529 : gimple_opt_pass *
530 294196 : make_pass_rebuild_cgraph_edges (gcc::context *ctxt)
531 : {
532 294196 : 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 882588 : pass_remove_cgraph_callee_edges (gcc::context *ctxt)
555 1765176 : : gimple_opt_pass (pass_data_remove_cgraph_callee_edges, ctxt)
556 : {}
557 :
558 : /* opt_pass methods: */
559 588392 : opt_pass * clone () final override {
560 588392 : 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 3604281 : pass_remove_cgraph_callee_edges::execute (function *)
568 : {
569 3604281 : cgraph_node *node = cgraph_node::get (current_function_decl);
570 3604281 : node->remove_callees ();
571 3604281 : node->remove_all_references ();
572 3604281 : return 0;
573 : }
574 :
575 : } // anon namespace
576 :
577 : gimple_opt_pass *
578 294196 : make_pass_remove_cgraph_callee_edges (gcc::context *ctxt)
579 : {
580 294196 : return new pass_remove_cgraph_callee_edges (ctxt);
581 : }
|
