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