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