gcc/cgraphbuild.c

   1 /* Callgraph construction.
   2    Copyright (C) 2003, 2004, 2005, 2006, 2007, 2008, 2009
   3    Free Software Foundation, Inc.
   4    Contributed by Jan Hubicka
   5
   6 This file is part of GCC.
   7
   8 GCC is free software; you can redistribute it and/or modify it under
   9 the terms of the GNU General Public License as published by the Free
  10 Software Foundation; either version 3, or (at your option) any later
  11 version.
  12
  13 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
  14 WARRANTY; without even the implied warranty of MERCHANTABILITY or
  15 FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  16 for more details.
  17
  18 You should have received a copy of the GNU General Public License
  19 along with GCC; see the file COPYING3.  If not see
  20 <http://www.gnu.org/licenses/>.  */
  21
  22 #include "config.h"
  23 #include "system.h"
  24 #include "coretypes.h"
  25 #include "tm.h"
  26 #include "tree.h"
  27 #include "tree-flow.h"
  28 #include "langhooks.h"
  29 #include "pointer-set.h"
  30 #include "cgraph.h"
  31 #include "intl.h"
  32 #include "gimple.h"
  33 #include "tree-pass.h"
  34 #include "ipa-utils.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   struct record_reference_ctx *ctx = (struct record_reference_ctx *)data;
  54
  55   switch (TREE_CODE (t))
  56     {
  57     case VAR_DECL:
  58     case FUNCTION_DECL:
  59       gcc_unreachable ();
  60       break;
  61
  62     case FDESC_EXPR:
  63     case ADDR_EXPR:
  64       /* Record dereferences to the functions.  This makes the
  65          functions reachable unconditionally.  */
  66       decl = get_base_var (*tp);
  67       if (TREE_CODE (decl) == FUNCTION_DECL)
  68         {
  69           if (!ctx->only_vars)
  70           cgraph_mark_address_taken_node (cgraph_node (decl));
  71           ipa_record_reference (NULL, ctx->varpool_node,
  72                                 cgraph_node (decl), NULL,
  73                                 IPA_REF_ADDR, NULL);
  74         }
  75
  76       if (TREE_CODE (decl) == VAR_DECL)
  77         {
  78           struct varpool_node *vnode = varpool_node (decl);
  79           if (lang_hooks.callgraph.analyze_expr)
  80             lang_hooks.callgraph.analyze_expr (&decl, walk_subtrees);
  81           varpool_mark_needed_node (vnode);
  82           if (vnode->alias && vnode->extra_name)
  83             vnode = vnode->extra_name;
  84           ipa_record_reference (NULL, ctx->varpool_node,
  85                                 NULL, 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
 100       if ((unsigned int) TREE_CODE (t) >= LAST_AND_UNUSED_TREE_CODE)
 101         return lang_hooks.callgraph.analyze_expr (tp, walk_subtrees);
 102       break;
 103     }
 104
 105   return NULL_TREE;
 106 }
 107
 108 /* Reset inlining information of all incoming call edges of NODE.  */
 109
 110 void
 111 reset_inline_failed (struct cgraph_node *node)
 112 {
 113   struct cgraph_edge *e;
 114
 115   for (e = node->callers; e; e = e->next_caller)
 116     {
 117       e->callee->global.inlined_to = NULL;
 118       if (!node->analyzed)
 119         e->inline_failed = CIF_BODY_NOT_AVAILABLE;
 120       else if (node->local.redefined_extern_inline)
 121         e->inline_failed = CIF_REDEFINED_EXTERN_INLINE;
 122       else if (!node->local.inlinable)
 123         e->inline_failed = CIF_FUNCTION_NOT_INLINABLE;
 124       else if (e->call_stmt_cannot_inline_p)
 125         e->inline_failed = CIF_MISMATCHED_ARGUMENTS;
 126       else
 127         e->inline_failed = CIF_FUNCTION_NOT_CONSIDERED;
 128     }
 129 }
 130
 131 /* Computes the frequency of the call statement so that it can be stored in
 132    cgraph_edge.  BB is the basic block of the call statement.  */
 133 int
 134 compute_call_stmt_bb_frequency (tree decl, basic_block bb)
 135 {
 136   int entry_freq = ENTRY_BLOCK_PTR_FOR_FUNCTION
 137                      (DECL_STRUCT_FUNCTION (decl))->frequency;
 138   int freq = bb->frequency;
 139
 140   if (profile_status_for_function (DECL_STRUCT_FUNCTION (decl)) == PROFILE_ABSENT)
 141     return CGRAPH_FREQ_BASE;
 142
 143   if (!entry_freq)
 144     entry_freq = 1, freq++;
 145
 146   freq = freq * CGRAPH_FREQ_BASE / entry_freq;
 147   if (freq > CGRAPH_FREQ_MAX)
 148     freq = CGRAPH_FREQ_MAX;
 149
 150   return freq;
 151 }
 152
 153 /* Mark address taken in STMT.  */
 154
 155 static bool
 156 mark_address (gimple stmt ATTRIBUTE_UNUSED, tree addr,
 157               void *data ATTRIBUTE_UNUSED)
 158 {
 159   if (TREE_CODE (addr) == FUNCTION_DECL)
 160     {
 161       struct cgraph_node *node = cgraph_node (addr);
 162       cgraph_mark_address_taken_node (node);
 163       ipa_record_reference ((struct cgraph_node *)data, NULL,
 164                             node, NULL,
 165                             IPA_REF_ADDR, stmt);
 166     }
 167   else
 168     {
 169       addr = get_base_address (addr);
 170       if (addr && TREE_CODE (addr) == VAR_DECL
 171           && (TREE_STATIC (addr) || DECL_EXTERNAL (addr)))
 172         {
 173           struct varpool_node *vnode = varpool_node (addr);
 174           int walk_subtrees;
 175
 176           if (lang_hooks.callgraph.analyze_expr)
 177             lang_hooks.callgraph.analyze_expr (&addr, &walk_subtrees);
 178           varpool_mark_needed_node (vnode);
 179           if (vnode->alias && vnode->extra_name)
 180             vnode = vnode->extra_name;
 181           ipa_record_reference ((struct cgraph_node *)data, NULL,
 182                                 NULL, vnode,
 183                                 IPA_REF_ADDR, stmt);
 184         }
 185     }
 186
 187   return false;
 188 }
 189
 190 /* Mark load of T.  */
 191
 192 static bool
 193 mark_load (gimple stmt ATTRIBUTE_UNUSED, tree t,
 194            void *data ATTRIBUTE_UNUSED)
 195 {
 196   t = get_base_address (t);
 197   if (TREE_CODE (t) == VAR_DECL
 198       && (TREE_STATIC (t) || DECL_EXTERNAL (t)))
 199     {
 200       struct varpool_node *vnode = varpool_node (t);
 201       int walk_subtrees;
 202
 203       if (lang_hooks.callgraph.analyze_expr)
 204         lang_hooks.callgraph.analyze_expr (&t, &walk_subtrees);
 205       varpool_mark_needed_node (vnode);
 206       if (vnode->alias && vnode->extra_name)
 207         vnode = vnode->extra_name;
 208       ipa_record_reference ((struct cgraph_node *)data, NULL,
 209                             NULL, vnode,
 210                             IPA_REF_LOAD, stmt);
 211     }
 212   return false;
 213 }
 214
 215 /* Mark store of T.  */
 216
 217 static bool
 218 mark_store (gimple stmt ATTRIBUTE_UNUSED, tree t,
 219             void *data ATTRIBUTE_UNUSED)
 220 {
 221   t = get_base_address (t);
 222   if (TREE_CODE (t) == VAR_DECL
 223       && (TREE_STATIC (t) || DECL_EXTERNAL (t)))
 224     {
 225       struct varpool_node *vnode = varpool_node (t);
 226       int walk_subtrees;
 227
 228       if (lang_hooks.callgraph.analyze_expr)
 229         lang_hooks.callgraph.analyze_expr (&t, &walk_subtrees);
 230       varpool_mark_needed_node (vnode);
 231       if (vnode->alias && vnode->extra_name)
 232         vnode = vnode->extra_name;
 233       ipa_record_reference ((struct cgraph_node *)data, NULL,
 234                             NULL, vnode,
 235                             IPA_REF_STORE, NULL);
 236      }
 237   return false;
 238 }
 239
 240 /* Create cgraph edges for function calls.
 241    Also look for functions and variables having addresses taken.  */
 242
 243 static unsigned int
 244 build_cgraph_edges (void)
 245 {
 246   basic_block bb;
 247   struct cgraph_node *node = cgraph_node (current_function_decl);
 248   struct pointer_set_t *visited_nodes = pointer_set_create ();
 249   gimple_stmt_iterator gsi;
 250   tree step;
 251
 252   /* Create the callgraph edges and record the nodes referenced by the function.
 253      body.  */
 254   FOR_EACH_BB (bb)
 255     {
 256       for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
 257         {
 258           gimple stmt = gsi_stmt (gsi);
 259           tree decl;
 260
 261           if (is_gimple_call (stmt) && (decl = gimple_call_fndecl (stmt)))
 262             cgraph_create_edge (node, cgraph_node (decl), stmt,
 263                                 bb->count,
 264                                 compute_call_stmt_bb_frequency
 265                                   (current_function_decl, bb),
 266                                 bb->loop_depth);
 267           walk_stmt_load_store_addr_ops (stmt, node, mark_load,
 268                                          mark_store, mark_address);
 269           if (gimple_code (stmt) == GIMPLE_OMP_PARALLEL
 270               && gimple_omp_parallel_child_fn (stmt))
 271             {
 272               tree fn = gimple_omp_parallel_child_fn (stmt);
 273               cgraph_mark_needed_node (cgraph_node (fn));
 274             }
 275           if (gimple_code (stmt) == GIMPLE_OMP_TASK)
 276             {
 277               tree fn = gimple_omp_task_child_fn (stmt);
 278               if (fn)
 279                 cgraph_mark_needed_node (cgraph_node (fn));
 280               fn = gimple_omp_task_copy_fn (stmt);
 281               if (fn)
 282                 cgraph_mark_needed_node (cgraph_node (fn));
 283             }
 284         }
 285       for (gsi = gsi_start (phi_nodes (bb)); !gsi_end_p (gsi); gsi_next (&gsi))
 286         walk_stmt_load_store_addr_ops (gsi_stmt (gsi), node,
 287                                        mark_load, mark_store, mark_address);
 288    }
 289
 290   /* Look for initializers of constant variables and private statics.  */
 291   for (step = cfun->local_decls;
 292        step;
 293        step = TREE_CHAIN (step))
 294     {
 295       tree decl = TREE_VALUE (step);
 296       if (TREE_CODE (decl) == VAR_DECL
 297           && (TREE_STATIC (decl) && !DECL_EXTERNAL (decl)))
 298         varpool_finalize_decl (decl);
 299     }
 300
 301   pointer_set_destroy (visited_nodes);
 302   return 0;
 303 }
 304
 305 struct gimple_opt_pass pass_build_cgraph_edges =
 306 {
 307  {
 308   GIMPLE_PASS,
 309   "*build_cgraph_edges",                        /* name */
 310   NULL,                                 /* gate */
 311   build_cgraph_edges,                   /* execute */
 312   NULL,                                 /* sub */
 313   NULL,                                 /* next */
 314   0,                                    /* static_pass_number */
 315   TV_NONE,                              /* tv_id */
 316   PROP_cfg,                             /* properties_required */
 317   0,                                    /* properties_provided */
 318   0,                                    /* properties_destroyed */
 319   0,                                    /* todo_flags_start */
 320   0                                     /* todo_flags_finish */
 321  }
 322 };
 323
 324 /* Record references to functions and other variables present in the
 325    initial value of DECL, a variable.
 326    When ONLY_VARS is true, we mark needed only variables, not functions.  */
 327
 328 void
 329 record_references_in_initializer (tree decl, bool only_vars)
 330 {
 331   struct pointer_set_t *visited_nodes = pointer_set_create ();
 332   struct varpool_node *node = varpool_node (decl);
 333   struct record_reference_ctx ctx = {false, NULL};
 334
 335   ctx.varpool_node = node;
 336   ctx.only_vars = only_vars;
 337   walk_tree (&DECL_INITIAL (decl), record_reference,
 338              &ctx, visited_nodes);
 339   pointer_set_destroy (visited_nodes);
 340 }
 341
 342 /* Rebuild cgraph edges for current function node.  This needs to be run after
 343    passes that don't update the cgraph.  */
 344
 345 unsigned int
 346 rebuild_cgraph_edges (void)
 347 {
 348   basic_block bb;
 349   struct cgraph_node *node = cgraph_node (current_function_decl);
 350   gimple_stmt_iterator gsi;
 351
 352   cgraph_node_remove_callees (node);
 353   ipa_remove_all_references (&node->ref_list);
 354
 355   node->count = ENTRY_BLOCK_PTR->count;
 356
 357   FOR_EACH_BB (bb)
 358     {
 359       for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
 360         {
 361           gimple stmt = gsi_stmt (gsi);
 362           tree decl;
 363
 364           if (is_gimple_call (stmt) && (decl = gimple_call_fndecl (stmt)))
 365             cgraph_create_edge (node, cgraph_node (decl), stmt,
 366                                 bb->count,
 367                                 compute_call_stmt_bb_frequency
 368                                   (current_function_decl, bb),
 369                                 bb->loop_depth);
 370           walk_stmt_load_store_addr_ops (stmt, node, mark_load,
 371                                          mark_store, mark_address);
 372
 373         }
 374       for (gsi = gsi_start (phi_nodes (bb)); !gsi_end_p (gsi); gsi_next (&gsi))
 375         walk_stmt_load_store_addr_ops (gsi_stmt (gsi), node,
 376                                        mark_load, mark_store, mark_address);
 377     }
 378   gcc_assert (!node->global.inlined_to);
 379
 380   return 0;
 381 }
 382
 383 struct gimple_opt_pass pass_rebuild_cgraph_edges =
 384 {
 385  {
 386   GIMPLE_PASS,
 387   "*rebuild_cgraph_edges",              /* name */
 388   NULL,                                 /* gate */
 389   rebuild_cgraph_edges,                 /* execute */
 390   NULL,                                 /* sub */
 391   NULL,                                 /* next */
 392   0,                                    /* static_pass_number */
 393   TV_NONE,                              /* tv_id */
 394   PROP_cfg,                             /* properties_required */
 395   0,                                    /* properties_provided */
 396   0,                                    /* properties_destroyed */
 397   0,                                    /* todo_flags_start */
 398   0,                                    /* todo_flags_finish */
 399  }
 400 };
 401
 402
 403 static unsigned int
 404 remove_cgraph_callee_edges (void)
 405 {
 406   cgraph_node_remove_callees (cgraph_node (current_function_decl));
 407   return 0;
 408 }
 409
 410 struct gimple_opt_pass pass_remove_cgraph_callee_edges =
 411 {
 412  {
 413   GIMPLE_PASS,
 414   "*remove_cgraph_callee_edges",                /* name */
 415   NULL,                                 /* gate */
 416   remove_cgraph_callee_edges,           /* execute */
 417   NULL,                                 /* sub */
 418   NULL,                                 /* next */
 419   0,                                    /* static_pass_number */
 420   TV_NONE,                              /* tv_id */
 421   0,                                    /* properties_required */
 422   0,                                    /* properties_provided */
 423   0,                                    /* properties_destroyed */
 424   0,                                    /* todo_flags_start */
 425   0,                                    /* todo_flags_finish */
 426  }
 427 };