gcc/cgraphbuild.c

   1 /* Callgraph construction.
   2    Copyright (C) 2003, 2004, 2005, 2006, 2007 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 "tree-flow.h"
  27 #include "langhooks.h"
  28 #include "pointer-set.h"
  29 #include "cgraph.h"
  30 #include "intl.h"
  31 #include "tree-gimple.h"
  32 #include "tree-pass.h"
  33
  34 /* Walk tree and record all calls and references to functions/variables.
  35    Called via walk_tree: TP is pointer to tree to be examined.  */
  36
  37 static tree
  38 record_reference (tree *tp, int *walk_subtrees, void *data)
  39 {
  40   tree t = *tp;
  41
  42   switch (TREE_CODE (t))
  43     {
  44     case VAR_DECL:
  45       if (TREE_STATIC (t) || DECL_EXTERNAL (t))
  46         {
  47           varpool_mark_needed_node (varpool_node (t));
  48           if (lang_hooks.callgraph.analyze_expr)
  49             return lang_hooks.callgraph.analyze_expr (tp, walk_subtrees,
  50                                                       data);
  51         }
  52       break;
  53
  54     case FDESC_EXPR:
  55     case ADDR_EXPR:
  56       if (flag_unit_at_a_time)
  57         {
  58           /* Record dereferences to the functions.  This makes the
  59              functions reachable unconditionally.  */
  60           tree decl = TREE_OPERAND (*tp, 0);
  61           if (TREE_CODE (decl) == FUNCTION_DECL)
  62             cgraph_mark_needed_node (cgraph_node (decl));
  63         }
  64       break;
  65
  66     default:
  67       /* Save some cycles by not walking types and declaration as we
  68          won't find anything useful there anyway.  */
  69       if (IS_TYPE_OR_DECL_P (*tp))
  70         {
  71           *walk_subtrees = 0;
  72           break;
  73         }
  74
  75       if ((unsigned int) TREE_CODE (t) >= LAST_AND_UNUSED_TREE_CODE)
  76         return lang_hooks.callgraph.analyze_expr (tp, walk_subtrees, data);
  77       break;
  78     }
  79
  80   return NULL_TREE;
  81 }
  82
  83 /* Give initial reasons why inlining would fail on all calls from
  84    NODE.  Those get either nullified or usually overwritten by more precise
  85    reason later.  */
  86
  87 static void
  88 initialize_inline_failed (struct cgraph_node *node)
  89 {
  90   struct cgraph_edge *e;
  91
  92   for (e = node->callers; e; e = e->next_caller)
  93     {
  94       gcc_assert (!e->callee->global.inlined_to);
  95       gcc_assert (e->inline_failed);
  96       if (node->local.redefined_extern_inline)
  97         e->inline_failed = N_("redefined extern inline functions are not "
  98                            "considered for inlining");
  99       else if (!node->local.inlinable)
 100         e->inline_failed = N_("function not inlinable");
 101       else if (CALL_CANNOT_INLINE_P (e->call_stmt))
 102         e->inline_failed = N_("mismatched arguments");
 103       else
 104         e->inline_failed = N_("function not considered for inlining");
 105     }
 106 }
 107
 108 /* Create cgraph edges for function calls.
 109    Also look for functions and variables having addresses taken.  */
 110
 111 static unsigned int
 112 build_cgraph_edges (void)
 113 {
 114   basic_block bb;
 115   struct cgraph_node *node = cgraph_node (current_function_decl);
 116   struct pointer_set_t *visited_nodes = pointer_set_create ();
 117   block_stmt_iterator bsi;
 118   tree step;
 119   int entry_freq = ENTRY_BLOCK_PTR->frequency;
 120
 121   if (!entry_freq)
 122     entry_freq = 1;
 123
 124   /* Create the callgraph edges and record the nodes referenced by the function.
 125      body.  */
 126   FOR_EACH_BB (bb)
 127     for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
 128       {
 129         tree stmt = bsi_stmt (bsi);
 130         tree call = get_call_expr_in (stmt);
 131         tree decl;
 132
 133         if (call && (decl = get_callee_fndecl (call)))
 134           {
 135             int i;
 136             int n = call_expr_nargs (call);
 137             int freq = (!bb->frequency && !entry_freq ? CGRAPH_FREQ_BASE
 138                         : bb->frequency * CGRAPH_FREQ_BASE / entry_freq);
 139             if (freq > CGRAPH_FREQ_MAX)
 140               freq = CGRAPH_FREQ_MAX;
 141             cgraph_create_edge (node, cgraph_node (decl), stmt,
 142                                 bb->count, freq,
 143                                 bb->loop_depth);
 144             for (i = 0; i < n; i++)
 145               walk_tree (&CALL_EXPR_ARG (call, i),
 146                          record_reference, node, visited_nodes);
 147             if (TREE_CODE (stmt) == GIMPLE_MODIFY_STMT)
 148               walk_tree (&GIMPLE_STMT_OPERAND (stmt, 0),
 149                          record_reference, node, visited_nodes);
 150           }
 151         else
 152           walk_tree (bsi_stmt_ptr (bsi), record_reference, node, visited_nodes);
 153       }
 154
 155   /* Look for initializers of constant variables and private statics.  */
 156   for (step = cfun->unexpanded_var_list;
 157        step;
 158        step = TREE_CHAIN (step))
 159     {
 160       tree decl = TREE_VALUE (step);
 161       if (TREE_CODE (decl) == VAR_DECL
 162           && (TREE_STATIC (decl) && !DECL_EXTERNAL (decl))
 163           && flag_unit_at_a_time)
 164         varpool_finalize_decl (decl);
 165       else if (TREE_CODE (decl) == VAR_DECL && DECL_INITIAL (decl))
 166         walk_tree (&DECL_INITIAL (decl), record_reference, node, visited_nodes);
 167     }
 168
 169   pointer_set_destroy (visited_nodes);
 170   initialize_inline_failed (node);
 171   return 0;
 172 }
 173
 174 struct tree_opt_pass pass_build_cgraph_edges =
 175 {
 176   NULL,                                 /* name */
 177   NULL,                                 /* gate */
 178   build_cgraph_edges,                   /* execute */
 179   NULL,                                 /* sub */
 180   NULL,                                 /* next */
 181   0,                                    /* static_pass_number */
 182   0,                                    /* tv_id */
 183   PROP_cfg,                             /* properties_required */
 184   0,                                    /* properties_provided */
 185   0,                                    /* properties_destroyed */
 186   0,                                    /* todo_flags_start */
 187   0,                                    /* todo_flags_finish */
 188   0                                     /* letter */
 189 };
 190
 191 /* Record references to functions and other variables present in the
 192    initial value of DECL, a variable.  */
 193
 194 void
 195 record_references_in_initializer (tree decl)
 196 {
 197   struct pointer_set_t *visited_nodes = pointer_set_create ();
 198   walk_tree (&DECL_INITIAL (decl), record_reference, NULL, visited_nodes);
 199   pointer_set_destroy (visited_nodes);
 200 }
 201
 202 /* Rebuild cgraph edges for current function node.  This needs to be run after
 203    passes that don't update the cgraph.  */
 204
 205 static unsigned int
 206 rebuild_cgraph_edges (void)
 207 {
 208   basic_block bb;
 209   struct cgraph_node *node = cgraph_node (current_function_decl);
 210   block_stmt_iterator bsi;
 211   int entry_freq = ENTRY_BLOCK_PTR->frequency;
 212
 213   if (!entry_freq)
 214     entry_freq = 1;
 215
 216   cgraph_node_remove_callees (node);
 217
 218   node->count = ENTRY_BLOCK_PTR->count;
 219
 220   FOR_EACH_BB (bb)
 221     for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
 222       {
 223         tree stmt = bsi_stmt (bsi);
 224         tree call = get_call_expr_in (stmt);
 225         tree decl;
 226
 227         if (call && (decl = get_callee_fndecl (call)))
 228           {
 229             int freq = (!bb->frequency && !entry_freq ? CGRAPH_FREQ_BASE
 230                         : bb->frequency * CGRAPH_FREQ_BASE / entry_freq);
 231             if (freq > CGRAPH_FREQ_MAX)
 232               freq = CGRAPH_FREQ_MAX;
 233             cgraph_create_edge (node, cgraph_node (decl), stmt,
 234                                 bb->count, freq, bb->loop_depth);
 235            }
 236       }
 237   initialize_inline_failed (node);
 238   gcc_assert (!node->global.inlined_to);
 239   return 0;
 240 }
 241
 242 struct tree_opt_pass pass_rebuild_cgraph_edges =
 243 {
 244   NULL,                                 /* name */
 245   NULL,                                 /* gate */
 246   rebuild_cgraph_edges,                 /* execute */
 247   NULL,                                 /* sub */
 248   NULL,                                 /* next */
 249   0,                                    /* static_pass_number */
 250   0,                                    /* tv_id */
 251   PROP_cfg,                             /* properties_required */
 252   0,                                    /* properties_provided */
 253   0,                                    /* properties_destroyed */
 254   0,                                    /* todo_flags_start */
 255   0,                                    /* todo_flags_finish */
 256   0                                     /* letter */
 257 };