gcc/cgraphbuild.c

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