cgraphbuild.c revision 1.8
1/* Callgraph construction. 2 Copyright (C) 2003-2017 Free Software Foundation, Inc. 3 Contributed by Jan Hubicka 4 5This file is part of GCC. 6 7GCC is free software; you can redistribute it and/or modify it under 8the terms of the GNU General Public License as published by the Free 9Software Foundation; either version 3, or (at your option) any later 10version. 11 12GCC is distributed in the hope that it will be useful, but WITHOUT ANY 13WARRANTY; without even the implied warranty of MERCHANTABILITY or 14FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 15for more details. 16 17You should have received a copy of the GNU General Public License 18along 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. */ 36struct 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 47static tree 48record_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 104static void 105record_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 129static void 130record_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. */ 190int 191compute_call_stmt_bb_frequency (tree decl, basic_block bb) 192{ 193 int entry_freq = ENTRY_BLOCK_PTR_FOR_FN 194 (DECL_STRUCT_FUNCTION (decl))->frequency; 195 int freq = bb->frequency; 196 197 if (profile_status_for_fn (DECL_STRUCT_FUNCTION (decl)) == PROFILE_ABSENT) 198 return CGRAPH_FREQ_BASE; 199 200 if (!entry_freq) 201 entry_freq = 1, freq++; 202 203 freq = freq * CGRAPH_FREQ_BASE / entry_freq; 204 if (freq > CGRAPH_FREQ_MAX) 205 freq = CGRAPH_FREQ_MAX; 206 207 return freq; 208} 209 210/* Mark address taken in STMT. */ 211 212static bool 213mark_address (gimple *stmt, tree addr, tree, void *data) 214{ 215 addr = get_base_address (addr); 216 if (TREE_CODE (addr) == FUNCTION_DECL) 217 { 218 cgraph_node *node = cgraph_node::get_create (addr); 219 node->mark_address_taken (); 220 ((symtab_node *)data)->create_reference (node, IPA_REF_ADDR, stmt); 221 } 222 else if (addr && VAR_P (addr) 223 && (TREE_STATIC (addr) || DECL_EXTERNAL (addr))) 224 { 225 varpool_node *vnode = varpool_node::get_create (addr); 226 227 ((symtab_node *)data)->create_reference (vnode, IPA_REF_ADDR, stmt); 228 } 229 230 return false; 231} 232 233/* Mark load of T. */ 234 235static bool 236mark_load (gimple *stmt, tree t, tree, void *data) 237{ 238 t = get_base_address (t); 239 if (t && TREE_CODE (t) == FUNCTION_DECL) 240 { 241 /* ??? This can happen on platforms with descriptors when these are 242 directly manipulated in the code. Pretend that it's an address. */ 243 cgraph_node *node = cgraph_node::get_create (t); 244 node->mark_address_taken (); 245 ((symtab_node *)data)->create_reference (node, IPA_REF_ADDR, stmt); 246 } 247 else if (t && VAR_P (t) && (TREE_STATIC (t) || DECL_EXTERNAL (t))) 248 { 249 varpool_node *vnode = varpool_node::get_create (t); 250 251 ((symtab_node *)data)->create_reference (vnode, IPA_REF_LOAD, stmt); 252 } 253 return false; 254} 255 256/* Mark store of T. */ 257 258static bool 259mark_store (gimple *stmt, tree t, tree, void *data) 260{ 261 t = get_base_address (t); 262 if (t && VAR_P (t) && (TREE_STATIC (t) || DECL_EXTERNAL (t))) 263 { 264 varpool_node *vnode = varpool_node::get_create (t); 265 266 ((symtab_node *)data)->create_reference (vnode, IPA_REF_STORE, stmt); 267 } 268 return false; 269} 270 271/* Record all references from cgraph_node that are taken in statement STMT. */ 272 273void 274cgraph_node::record_stmt_references (gimple *stmt) 275{ 276 walk_stmt_load_store_addr_ops (stmt, this, mark_load, mark_store, 277 mark_address); 278} 279 280/* Create cgraph edges for function calls. 281 Also look for functions and variables having addresses taken. */ 282 283namespace { 284 285const pass_data pass_data_build_cgraph_edges = 286{ 287 GIMPLE_PASS, /* type */ 288 "*build_cgraph_edges", /* name */ 289 OPTGROUP_NONE, /* optinfo_flags */ 290 TV_NONE, /* tv_id */ 291 PROP_cfg, /* properties_required */ 292 0, /* properties_provided */ 293 0, /* properties_destroyed */ 294 0, /* todo_flags_start */ 295 0, /* todo_flags_finish */ 296}; 297 298class pass_build_cgraph_edges : public gimple_opt_pass 299{ 300public: 301 pass_build_cgraph_edges (gcc::context *ctxt) 302 : gimple_opt_pass (pass_data_build_cgraph_edges, ctxt) 303 {} 304 305 /* opt_pass methods: */ 306 virtual unsigned int execute (function *); 307 308}; // class pass_build_cgraph_edges 309 310unsigned int 311pass_build_cgraph_edges::execute (function *fun) 312{ 313 basic_block bb; 314 cgraph_node *node = cgraph_node::get (current_function_decl); 315 gimple_stmt_iterator gsi; 316 tree decl; 317 unsigned ix; 318 319 /* Create the callgraph edges and record the nodes referenced by the function. 320 body. */ 321 FOR_EACH_BB_FN (bb, fun) 322 { 323 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi)) 324 { 325 gimple *stmt = gsi_stmt (gsi); 326 tree decl; 327 328 if (is_gimple_debug (stmt)) 329 continue; 330 331 if (gcall *call_stmt = dyn_cast <gcall *> (stmt)) 332 { 333 int freq = compute_call_stmt_bb_frequency (current_function_decl, 334 bb); 335 decl = gimple_call_fndecl (call_stmt); 336 if (decl) 337 node->create_edge (cgraph_node::get_create (decl), call_stmt, bb->count, freq); 338 else if (gimple_call_internal_p (call_stmt)) 339 ; 340 else 341 node->create_indirect_edge (call_stmt, 342 gimple_call_flags (call_stmt), 343 bb->count, freq); 344 } 345 node->record_stmt_references (stmt); 346 if (gomp_parallel *omp_par_stmt = dyn_cast <gomp_parallel *> (stmt)) 347 { 348 tree fn = gimple_omp_parallel_child_fn (omp_par_stmt); 349 node->create_reference (cgraph_node::get_create (fn), 350 IPA_REF_ADDR, stmt); 351 } 352 if (gimple_code (stmt) == GIMPLE_OMP_TASK) 353 { 354 tree fn = gimple_omp_task_child_fn (stmt); 355 if (fn) 356 node->create_reference (cgraph_node::get_create (fn), 357 IPA_REF_ADDR, stmt); 358 fn = gimple_omp_task_copy_fn (stmt); 359 if (fn) 360 node->create_reference (cgraph_node::get_create (fn), 361 IPA_REF_ADDR, stmt); 362 } 363 } 364 for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi)) 365 node->record_stmt_references (gsi_stmt (gsi)); 366 } 367 368 /* Look for initializers of constant variables and private statics. */ 369 FOR_EACH_LOCAL_DECL (fun, ix, decl) 370 if (VAR_P (decl) 371 && (TREE_STATIC (decl) && !DECL_EXTERNAL (decl)) 372 && !DECL_HAS_VALUE_EXPR_P (decl) 373 && TREE_TYPE (decl) != error_mark_node) 374 varpool_node::finalize_decl (decl); 375 record_eh_tables (node, fun); 376 377 return 0; 378} 379 380} // anon namespace 381 382gimple_opt_pass * 383make_pass_build_cgraph_edges (gcc::context *ctxt) 384{ 385 return new pass_build_cgraph_edges (ctxt); 386} 387 388/* Record references to functions and other variables present in the 389 initial value of DECL, a variable. 390 When ONLY_VARS is true, we mark needed only variables, not functions. */ 391 392void 393record_references_in_initializer (tree decl, bool only_vars) 394{ 395 varpool_node *node = varpool_node::get_create (decl); 396 hash_set<tree> visited_nodes; 397 record_reference_ctx ctx = {false, NULL}; 398 399 ctx.varpool_node = node; 400 ctx.only_vars = only_vars; 401 walk_tree (&DECL_INITIAL (decl), record_reference, 402 &ctx, &visited_nodes); 403} 404 405/* Rebuild cgraph edges for current function node. This needs to be run after 406 passes that don't update the cgraph. */ 407 408unsigned int 409cgraph_edge::rebuild_edges (void) 410{ 411 basic_block bb; 412 cgraph_node *node = cgraph_node::get (current_function_decl); 413 gimple_stmt_iterator gsi; 414 415 node->remove_callees (); 416 node->remove_all_references (); 417 418 node->count = ENTRY_BLOCK_PTR_FOR_FN (cfun)->count; 419 420 FOR_EACH_BB_FN (bb, cfun) 421 { 422 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi)) 423 { 424 gimple *stmt = gsi_stmt (gsi); 425 tree decl; 426 427 if (gcall *call_stmt = dyn_cast <gcall *> (stmt)) 428 { 429 int freq = compute_call_stmt_bb_frequency (current_function_decl, 430 bb); 431 decl = gimple_call_fndecl (call_stmt); 432 if (decl) 433 node->create_edge (cgraph_node::get_create (decl), call_stmt, 434 bb->count, freq); 435 else if (gimple_call_internal_p (call_stmt)) 436 ; 437 else 438 node->create_indirect_edge (call_stmt, 439 gimple_call_flags (call_stmt), 440 bb->count, freq); 441 } 442 node->record_stmt_references (stmt); 443 } 444 for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi)) 445 node->record_stmt_references (gsi_stmt (gsi)); 446 } 447 record_eh_tables (node, cfun); 448 gcc_assert (!node->global.inlined_to); 449 450 if (node->instrumented_version 451 && !node->instrumentation_clone) 452 node->create_reference (node->instrumented_version, IPA_REF_CHKP, NULL); 453 454 return 0; 455} 456 457/* Rebuild cgraph references for current function node. This needs to be run 458 after passes that don't update the cgraph. */ 459 460void 461cgraph_edge::rebuild_references (void) 462{ 463 basic_block bb; 464 cgraph_node *node = cgraph_node::get (current_function_decl); 465 gimple_stmt_iterator gsi; 466 ipa_ref *ref = NULL; 467 int i; 468 469 /* Keep speculative references for further cgraph edge expansion. */ 470 for (i = 0; node->iterate_reference (i, ref);) 471 if (!ref->speculative) 472 ref->remove_reference (); 473 else 474 i++; 475 476 node->count = ENTRY_BLOCK_PTR_FOR_FN (cfun)->count; 477 478 FOR_EACH_BB_FN (bb, cfun) 479 { 480 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi)) 481 node->record_stmt_references (gsi_stmt (gsi)); 482 for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi)) 483 node->record_stmt_references (gsi_stmt (gsi)); 484 } 485 record_eh_tables (node, cfun); 486 487 if (node->instrumented_version 488 && !node->instrumentation_clone) 489 node->create_reference (node->instrumented_version, IPA_REF_CHKP, NULL); 490} 491 492namespace { 493 494const pass_data pass_data_rebuild_cgraph_edges = 495{ 496 GIMPLE_PASS, /* type */ 497 "*rebuild_cgraph_edges", /* name */ 498 OPTGROUP_NONE, /* optinfo_flags */ 499 TV_CGRAPH, /* tv_id */ 500 PROP_cfg, /* properties_required */ 501 0, /* properties_provided */ 502 0, /* properties_destroyed */ 503 0, /* todo_flags_start */ 504 0, /* todo_flags_finish */ 505}; 506 507class pass_rebuild_cgraph_edges : public gimple_opt_pass 508{ 509public: 510 pass_rebuild_cgraph_edges (gcc::context *ctxt) 511 : gimple_opt_pass (pass_data_rebuild_cgraph_edges, ctxt) 512 {} 513 514 /* opt_pass methods: */ 515 opt_pass * clone () { return new pass_rebuild_cgraph_edges (m_ctxt); } 516 virtual unsigned int execute (function *) 517 { 518 return cgraph_edge::rebuild_edges (); 519 } 520 521}; // class pass_rebuild_cgraph_edges 522 523} // anon namespace 524 525gimple_opt_pass * 526make_pass_rebuild_cgraph_edges (gcc::context *ctxt) 527{ 528 return new pass_rebuild_cgraph_edges (ctxt); 529} 530 531 532namespace { 533 534const pass_data pass_data_remove_cgraph_callee_edges = 535{ 536 GIMPLE_PASS, /* type */ 537 "*remove_cgraph_callee_edges", /* name */ 538 OPTGROUP_NONE, /* optinfo_flags */ 539 TV_NONE, /* tv_id */ 540 0, /* properties_required */ 541 0, /* properties_provided */ 542 0, /* properties_destroyed */ 543 0, /* todo_flags_start */ 544 0, /* todo_flags_finish */ 545}; 546 547class pass_remove_cgraph_callee_edges : public gimple_opt_pass 548{ 549public: 550 pass_remove_cgraph_callee_edges (gcc::context *ctxt) 551 : gimple_opt_pass (pass_data_remove_cgraph_callee_edges, ctxt) 552 {} 553 554 /* opt_pass methods: */ 555 opt_pass * clone () { 556 return new pass_remove_cgraph_callee_edges (m_ctxt); 557 } 558 virtual unsigned int execute (function *); 559 560}; // class pass_remove_cgraph_callee_edges 561 562unsigned int 563pass_remove_cgraph_callee_edges::execute (function *) 564{ 565 cgraph_node *node = cgraph_node::get (current_function_decl); 566 node->remove_callees (); 567 node->remove_all_references (); 568 return 0; 569} 570 571} // anon namespace 572 573gimple_opt_pass * 574make_pass_remove_cgraph_callee_edges (gcc::context *ctxt) 575{ 576 return new pass_remove_cgraph_callee_edges (ctxt); 577} 578