1 | /* Callgraph construction. |
2 | Copyright (C) 2003-2023 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 | record_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 | |
116 | static void |
117 | record_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 | |
141 | static void |
142 | record_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. */ |
202 | int |
203 | compute_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 | |
211 | static bool |
212 | mark_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 | |
234 | static bool |
235 | mark_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 | |
257 | static bool |
258 | mark_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 | |
272 | void |
273 | cgraph_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 | |
282 | namespace { |
283 | |
284 | const 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 | |
297 | class pass_build_cgraph_edges : public gimple_opt_pass |
298 | { |
299 | public: |
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 | |
309 | unsigned int |
310 | pass_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 | |
379 | gimple_opt_pass * |
380 | make_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 | |
389 | void |
390 | record_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 | |
405 | unsigned int |
406 | cgraph_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 | |
450 | void |
451 | cgraph_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 | |
476 | namespace { |
477 | |
478 | const 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 | |
491 | class pass_rebuild_cgraph_edges : public gimple_opt_pass |
492 | { |
493 | public: |
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 | |
512 | gimple_opt_pass * |
513 | make_pass_rebuild_cgraph_edges (gcc::context *ctxt) |
514 | { |
515 | return new pass_rebuild_cgraph_edges (ctxt); |
516 | } |
517 | |
518 | |
519 | namespace { |
520 | |
521 | const 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 | |
534 | class pass_remove_cgraph_callee_edges : public gimple_opt_pass |
535 | { |
536 | public: |
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 | |
549 | unsigned int |
550 | pass_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 | |
560 | gimple_opt_pass * |
561 | make_pass_remove_cgraph_callee_edges (gcc::context *ctxt) |
562 | { |
563 | return new pass_remove_cgraph_callee_edges (ctxt); |
564 | } |
565 | |