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 14817220 : record_reference (tree *tp, int *walk_subtrees, void *data)
49 : {
50 14817255 : tree t = *tp;
51 14817255 : tree decl;
52 14817255 : record_reference_ctx *ctx = (record_reference_ctx *)data;
53 :
54 14817255 : t = canonicalize_constructor_val (t, NULL);
55 14817255 : if (!t)
56 83 : t = *tp;
57 14817172 : else if (t != *tp)
58 4464579 : *tp = t;
59 :
60 14817255 : switch (TREE_CODE (t))
61 : {
62 0 : case VAR_DECL:
63 0 : case FUNCTION_DECL:
64 0 : gcc_unreachable ();
65 4664684 : break;
66 :
67 4664684 : case FDESC_EXPR:
68 4664684 : case ADDR_EXPR:
69 : /* Record dereferences to the functions. This makes the
70 : functions reachable unconditionally. */
71 4664684 : decl = get_base_var (*tp);
72 4664684 : if (TREE_CODE (decl) == FUNCTION_DECL)
73 : {
74 1130115 : cgraph_node *node = cgraph_node::get_create (decl);
75 1130115 : if (!ctx->only_vars)
76 1130115 : node->mark_address_taken ();
77 1130115 : ctx->varpool_node->create_reference (node, IPA_REF_ADDR);
78 : }
79 :
80 4664684 : 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 2608660 : 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 2608625 : varpool_node *vnode = varpool_node::get_create (decl);
94 2608625 : ctx->varpool_node->create_reference (vnode, IPA_REF_ADDR);
95 : }
96 4664649 : *walk_subtrees = 0;
97 4664649 : break;
98 :
99 10152571 : default:
100 : /* Save some cycles by not walking types and declaration as we
101 : won't find anything useful there anyway. */
102 10152571 : 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 199821 : record_type_list (cgraph_node *node, tree list)
117 : {
118 226436 : for (; list; list = TREE_CHAIN (list))
119 : {
120 26615 : tree type = TREE_VALUE (list);
121 :
122 26615 : if (TYPE_P (type))
123 25998 : type = lookup_type_for_runtime (type);
124 26615 : STRIP_NOPS (type);
125 26615 : if (TREE_CODE (type) == ADDR_EXPR)
126 : {
127 26615 : type = TREE_OPERAND (type, 0);
128 26615 : if (VAR_P (type))
129 : {
130 26615 : varpool_node *vnode = varpool_node::get_create (type);
131 26615 : node->create_reference (vnode, IPA_REF_ADDR);
132 : }
133 : }
134 : }
135 199821 : }
136 :
137 : /* Record all references we will introduce by producing EH tables
138 : for NODE. */
139 :
140 : static void
141 12329027 : record_eh_tables (cgraph_node *node, function *fun)
142 : {
143 12329027 : eh_region i;
144 :
145 12329027 : if (DECL_FUNCTION_PERSONALITY (node->decl))
146 : {
147 2552318 : tree per_decl = DECL_FUNCTION_PERSONALITY (node->decl);
148 2552318 : cgraph_node *per_node = cgraph_node::get_create (per_decl);
149 :
150 2552318 : node->create_reference (per_node, IPA_REF_ADDR);
151 2552318 : per_node->mark_address_taken ();
152 : }
153 :
154 12329027 : i = fun->eh->region_tree;
155 12329027 : if (!i)
156 : return;
157 :
158 8512162 : while (1)
159 : {
160 8512162 : switch (i->type)
161 : {
162 : case ERT_CLEANUP:
163 : case ERT_MUST_NOT_THROW:
164 : break;
165 :
166 183136 : case ERT_TRY:
167 183136 : {
168 183136 : eh_catch c;
169 363851 : for (c = i->u.eh_try.first_catch; c; c = c->next_catch)
170 180715 : record_type_list (node, c->type_list);
171 : }
172 : break;
173 :
174 19106 : case ERT_ALLOWED_EXCEPTIONS:
175 19106 : record_type_list (node, i->u.allowed.type_list);
176 19106 : break;
177 : }
178 : /* If there are sub-regions, process them. */
179 8512162 : if (i->inner)
180 : i = i->inner;
181 : /* If there are peers, process them. */
182 6607048 : 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 5459145 : do
188 : {
189 5459145 : i = i->outer;
190 5459145 : if (i == NULL)
191 : return;
192 : }
193 1905114 : 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 33808331 : mark_address (gimple *stmt, tree addr, tree, void *data)
212 : {
213 33808331 : addr = get_base_address (addr);
214 33808331 : if (TREE_CODE (addr) == FUNCTION_DECL)
215 : {
216 1127428 : cgraph_node *caller = (cgraph_node *) data;
217 1127428 : 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 1127428 : cgraph_edge *e = caller->get_edge (stmt);
222 1127428 : if (e && e->has_callback)
223 : {
224 529 : for (cgraph_edge *cbe = e->first_callback_edge ();
225 561 : cbe;
226 32 : cbe = cbe->next_callback_edge ())
227 : {
228 32 : if (cbe->callee->is_clone_of (node))
229 : {
230 0 : node = cbe->callee;
231 0 : break;
232 : }
233 : }
234 : }
235 1127428 : node->mark_address_taken ();
236 1127428 : caller->create_reference (node, IPA_REF_ADDR, stmt);
237 : }
238 32680903 : else if (addr && VAR_P (addr)
239 19565933 : && (TREE_STATIC (addr) || DECL_EXTERNAL (addr)))
240 : {
241 8091603 : varpool_node *vnode = varpool_node::get_create (addr);
242 :
243 8091603 : ((symtab_node *)data)->create_reference (vnode, IPA_REF_ADDR, stmt);
244 : }
245 :
246 33808331 : return false;
247 : }
248 :
249 : /* Mark load of T. */
250 :
251 : static bool
252 62410427 : mark_load (gimple *stmt, tree t, tree, void *data)
253 : {
254 62410427 : t = get_base_address (t);
255 62410427 : 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 62410322 : else if (t && VAR_P (t) && (TREE_STATIC (t) || DECL_EXTERNAL (t)))
264 : {
265 11371698 : varpool_node *vnode = varpool_node::get_create (t);
266 :
267 11371698 : ((symtab_node *)data)->create_reference (vnode, IPA_REF_LOAD, stmt);
268 : }
269 62410427 : return false;
270 : }
271 :
272 : /* Mark store of T. */
273 :
274 : static bool
275 63696217 : mark_store (gimple *stmt, tree t, tree, void *data)
276 : {
277 63696217 : t = get_base_address (t);
278 63696217 : if (t && VAR_P (t) && (TREE_STATIC (t) || DECL_EXTERNAL (t)))
279 : {
280 5699581 : varpool_node *vnode = varpool_node::get_create (t);
281 :
282 5699581 : ((symtab_node *)data)->create_reference (vnode, IPA_REF_STORE, stmt);
283 : }
284 63696217 : return false;
285 : }
286 :
287 : /* Record all references from cgraph_node that are taken in statement STMT. */
288 :
289 : void
290 317702701 : cgraph_node::record_stmt_references (gimple *stmt)
291 : {
292 317702701 : walk_stmt_load_store_addr_ops (stmt, this, mark_load, mark_store,
293 : mark_address);
294 317702701 : }
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 292371 : pass_build_cgraph_edges (gcc::context *ctxt)
318 584742 : : 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 3008124 : pass_build_cgraph_edges::execute (function *fun)
328 : {
329 3008124 : basic_block bb;
330 3008124 : cgraph_node *node = cgraph_node::get (current_function_decl);
331 3008124 : gimple_stmt_iterator gsi;
332 3008124 : tree decl;
333 3008124 : unsigned ix;
334 :
335 : /* Create the callgraph edges and record the nodes referenced by the function.
336 : body. */
337 20525843 : FOR_EACH_BB_FN (bb, fun)
338 : {
339 101324595 : for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
340 : {
341 66289157 : gimple *stmt = gsi_stmt (gsi);
342 66289157 : tree decl;
343 :
344 66289157 : if (is_gimple_debug (stmt))
345 2370362 : continue;
346 :
347 63918795 : if (gcall *call_stmt = dyn_cast <gcall *> (stmt))
348 : {
349 10518181 : decl = gimple_call_fndecl (call_stmt);
350 10518181 : if (decl)
351 9971981 : node->create_edge (cgraph_node::get_create (decl), call_stmt, bb->count);
352 546200 : else if (gimple_call_internal_p (call_stmt))
353 : ;
354 : else
355 163477 : node->create_indirect_edge (call_stmt,
356 : gimple_call_flags (call_stmt),
357 : bb->count);
358 : }
359 63918795 : node->record_stmt_references (stmt);
360 63918795 : 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 63918795 : 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 17517719 : 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 20980011 : FOR_EACH_LOCAL_DECL (fun, ix, decl)
384 15746808 : if (VAR_P (decl)
385 15746808 : && (TREE_STATIC (decl) && !DECL_EXTERNAL (decl))
386 294291 : && !DECL_HAS_VALUE_EXPR_P (decl)
387 15993805 : && TREE_TYPE (decl) != error_mark_node)
388 246928 : varpool_node::finalize_decl (decl);
389 3008124 : record_eh_tables (node, fun);
390 :
391 3008124 : return 0;
392 : }
393 :
394 : } // anon namespace
395 :
396 : gimple_opt_pass *
397 292371 : make_pass_build_cgraph_edges (gcc::context *ctxt)
398 : {
399 292371 : 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 2027746 : record_references_in_initializer (tree decl, bool only_vars)
408 : {
409 2027746 : varpool_node *node = varpool_node::get_create (decl);
410 2027746 : hash_set<tree> visited_nodes;
411 2027746 : record_reference_ctx ctx = {false, NULL};
412 :
413 2027746 : ctx.varpool_node = node;
414 2027746 : ctx.only_vars = only_vars;
415 2027746 : walk_tree (&DECL_INITIAL (decl), record_reference,
416 : &ctx, &visited_nodes);
417 2027746 : }
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 9070766 : cgraph_edge::rebuild_edges (void)
424 : {
425 9070766 : basic_block bb;
426 9070766 : cgraph_node *node = cgraph_node::get (current_function_decl);
427 9070766 : gimple_stmt_iterator gsi;
428 :
429 9070766 : node->remove_callees ();
430 9070766 : node->remove_all_references ();
431 :
432 9070766 : node->count = ENTRY_BLOCK_PTR_FOR_FN (cfun)->count;
433 :
434 60159920 : FOR_EACH_BB_FN (bb, cfun)
435 : {
436 329536361 : for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
437 : {
438 227358053 : gimple *stmt = gsi_stmt (gsi);
439 227358053 : tree decl;
440 :
441 227358053 : if (gcall *call_stmt = dyn_cast <gcall *> (stmt))
442 : {
443 29849829 : decl = gimple_call_fndecl (call_stmt);
444 29849829 : if (decl)
445 27575214 : node->create_edge (cgraph_node::get_create (decl), call_stmt,
446 : bb->count);
447 2274615 : else if (gimple_call_internal_p (call_stmt))
448 : ;
449 : else
450 506143 : node->create_indirect_edge (call_stmt,
451 : gimple_call_flags (call_stmt),
452 : bb->count);
453 : }
454 227358053 : node->record_stmt_references (stmt);
455 : }
456 64360667 : for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi))
457 13271513 : node->record_stmt_references (gsi_stmt (gsi));
458 : }
459 9070766 : record_eh_tables (node, cfun);
460 9070766 : gcc_assert (!node->inlined_to);
461 9070766 : 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 250137 : cgraph_edge::rebuild_references (void)
469 : {
470 250137 : basic_block bb;
471 250137 : cgraph_node *node = cgraph_node::get (current_function_decl);
472 250137 : gimple_stmt_iterator gsi;
473 250137 : ipa_ref *ref = NULL;
474 250137 : int i;
475 :
476 : /* Keep speculative references for further cgraph edge expansion. */
477 707167 : for (i = 0; node->iterate_reference (i, ref);)
478 206893 : if (!ref->speculative)
479 204627 : ref->remove_reference ();
480 : else
481 2266 : i++;
482 :
483 2322471 : FOR_EACH_BB_FN (bb, cfun)
484 : {
485 16965366 : for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
486 12820698 : node->record_stmt_references (gsi_stmt (gsi));
487 2405976 : for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi))
488 333642 : node->record_stmt_references (gsi_stmt (gsi));
489 : }
490 250137 : record_eh_tables (node, cfun);
491 250137 : }
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 1169484 : pass_rebuild_cgraph_edges (gcc::context *ctxt)
512 2338968 : : gimple_opt_pass (pass_data_rebuild_cgraph_edges, ctxt)
513 : {}
514 :
515 : /* opt_pass methods: */
516 877113 : opt_pass * clone () final override
517 : {
518 877113 : return new pass_rebuild_cgraph_edges (m_ctxt);
519 : }
520 8957277 : unsigned int execute (function *) final override
521 : {
522 8957277 : return cgraph_edge::rebuild_edges ();
523 : }
524 :
525 : }; // class pass_rebuild_cgraph_edges
526 :
527 : } // anon namespace
528 :
529 : gimple_opt_pass *
530 292371 : make_pass_rebuild_cgraph_edges (gcc::context *ctxt)
531 : {
532 292371 : 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 877113 : pass_remove_cgraph_callee_edges (gcc::context *ctxt)
555 1754226 : : gimple_opt_pass (pass_data_remove_cgraph_callee_edges, ctxt)
556 : {}
557 :
558 : /* opt_pass methods: */
559 584742 : opt_pass * clone () final override {
560 584742 : 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 3585458 : pass_remove_cgraph_callee_edges::execute (function *)
568 : {
569 3585458 : cgraph_node *node = cgraph_node::get (current_function_decl);
570 3585458 : node->remove_callees ();
571 3585458 : node->remove_all_references ();
572 3585458 : return 0;
573 : }
574 :
575 : } // anon namespace
576 :
577 : gimple_opt_pass *
578 292371 : make_pass_remove_cgraph_callee_edges (gcc::context *ctxt)
579 : {
580 292371 : return new pass_remove_cgraph_callee_edges (ctxt);
581 : }
|
