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 35 /* Walk tree and record all calls and references to functions/variables. 36 Called via walk_tree: TP is pointer to tree to be examined. 37 When DATA is non-null, record references to callgraph. 38 */ 39 40 static tree 41 record_reference (tree *tp, int *walk_subtrees, void *data) 42 { 43 tree t = *tp; 44 tree decl; 45 bool do_callgraph = data != NULL; 46 47 switch (TREE_CODE (t)) 48 { 49 case VAR_DECL: 50 if (TREE_STATIC (t) || DECL_EXTERNAL (t)) 51 { 52 varpool_mark_needed_node (varpool_node (t)); 53 if (lang_hooks.callgraph.analyze_expr) 54 return lang_hooks.callgraph.analyze_expr (tp, walk_subtrees); 55 } 56 break; 57 58 case FDESC_EXPR: 59 case ADDR_EXPR: 60 /* Record dereferences to the functions. This makes the 61 functions reachable unconditionally. */ 62 decl = TREE_OPERAND (*tp, 0); 63 if (TREE_CODE (decl) == FUNCTION_DECL && do_callgraph) 64 cgraph_mark_address_taken_node (cgraph_node (decl)); 65 break; 66 67 default: 68 /* Save some cycles by not walking types and declaration as we 69 won't find anything useful there anyway. */ 70 if (IS_TYPE_OR_DECL_P (*tp)) 71 { 72 *walk_subtrees = 0; 73 break; 74 } 75 76 if ((unsigned int) TREE_CODE (t) >= LAST_AND_UNUSED_TREE_CODE) 77 return lang_hooks.callgraph.analyze_expr (tp, walk_subtrees); 78 break; 79 } 80 81 return NULL_TREE; 82 } 83 84 /* Reset inlining information of all incoming call edges of NODE. */ 85 86 void 87 reset_inline_failed (struct cgraph_node *node) 88 { 89 struct cgraph_edge *e; 90 91 for (e = node->callers; e; e = e->next_caller) 92 { 93 e->callee->global.inlined_to = NULL; 94 if (!node->analyzed) 95 e->inline_failed = CIF_BODY_NOT_AVAILABLE; 96 else if (node->local.redefined_extern_inline) 97 e->inline_failed = CIF_REDEFINED_EXTERN_INLINE; 98 else if (!node->local.inlinable) 99 e->inline_failed = CIF_FUNCTION_NOT_INLINABLE; 100 else if (e->call_stmt_cannot_inline_p) 101 e->inline_failed = CIF_MISMATCHED_ARGUMENTS; 102 else 103 e->inline_failed = CIF_FUNCTION_NOT_CONSIDERED; 104 } 105 } 106 107 /* Computes the frequency of the call statement so that it can be stored in 108 cgraph_edge. BB is the basic block of the call statement. */ 109 int 110 compute_call_stmt_bb_frequency (tree decl, basic_block bb) 111 { 112 int entry_freq = ENTRY_BLOCK_PTR_FOR_FUNCTION 113 (DECL_STRUCT_FUNCTION (decl))->frequency; 114 int freq = bb->frequency; 115 116 if (profile_status_for_function (DECL_STRUCT_FUNCTION (decl)) == PROFILE_ABSENT) 117 return CGRAPH_FREQ_BASE; 118 119 if (!entry_freq) 120 entry_freq = 1, freq++; 121 122 freq = freq * CGRAPH_FREQ_BASE / entry_freq; 123 if (freq > CGRAPH_FREQ_MAX) 124 freq = CGRAPH_FREQ_MAX; 125 126 return freq; 127 } 128 129 /* Create cgraph edges for function calls. 130 Also look for functions and variables having addresses taken. */ 131 132 static unsigned int 133 build_cgraph_edges (void) 134 { 135 basic_block bb; 136 struct cgraph_node *node = cgraph_node (current_function_decl); 137 struct pointer_set_t *visited_nodes = pointer_set_create (); 138 gimple_stmt_iterator gsi; 139 tree step; 140 141 /* Create the callgraph edges and record the nodes referenced by the function. 142 body. */ 143 FOR_EACH_BB (bb) 144 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi)) 145 { 146 gimple stmt = gsi_stmt (gsi); 147 tree decl; 148 149 if (is_gimple_call (stmt) && (decl = gimple_call_fndecl (stmt))) 150 { 151 size_t i; 152 size_t n = gimple_call_num_args (stmt); 153 cgraph_create_edge (node, cgraph_node (decl), stmt, 154 bb->count, compute_call_stmt_bb_frequency (current_function_decl, bb), 155 bb->loop_depth); 156 for (i = 0; i < n; i++) 157 walk_tree (gimple_call_arg_ptr (stmt, i), record_reference, 158 node, visited_nodes); 159 if (gimple_call_lhs (stmt)) 160 walk_tree (gimple_call_lhs_ptr (stmt), record_reference, node, 161 visited_nodes); 162 } 163 else 164 { 165 struct walk_stmt_info wi; 166 memset (&wi, 0, sizeof (wi)); 167 wi.info = node; 168 wi.pset = visited_nodes; 169 walk_gimple_op (stmt, record_reference, &wi); 170 if (gimple_code (stmt) == GIMPLE_OMP_PARALLEL 171 && gimple_omp_parallel_child_fn (stmt)) 172 { 173 tree fn = gimple_omp_parallel_child_fn (stmt); 174 cgraph_mark_needed_node (cgraph_node (fn)); 175 } 176 if (gimple_code (stmt) == GIMPLE_OMP_TASK) 177 { 178 tree fn = gimple_omp_task_child_fn (stmt); 179 if (fn) 180 cgraph_mark_needed_node (cgraph_node (fn)); 181 fn = gimple_omp_task_copy_fn (stmt); 182 if (fn) 183 cgraph_mark_needed_node (cgraph_node (fn)); 184 } 185 } 186 } 187 188 /* Look for initializers of constant variables and private statics. */ 189 for (step = cfun->local_decls; 190 step; 191 step = TREE_CHAIN (step)) 192 { 193 tree decl = TREE_VALUE (step); 194 if (TREE_CODE (decl) == VAR_DECL 195 && (TREE_STATIC (decl) && !DECL_EXTERNAL (decl))) 196 varpool_finalize_decl (decl); 197 else if (TREE_CODE (decl) == VAR_DECL && DECL_INITIAL (decl)) 198 walk_tree (&DECL_INITIAL (decl), record_reference, node, visited_nodes); 199 } 200 201 pointer_set_destroy (visited_nodes); 202 return 0; 203 } 204 205 struct gimple_opt_pass pass_build_cgraph_edges = 206 { 207 { 208 GIMPLE_PASS, 209 "*build_cgraph_edges", /* name */ 210 NULL, /* gate */ 211 build_cgraph_edges, /* execute */ 212 NULL, /* sub */ 213 NULL, /* next */ 214 0, /* static_pass_number */ 215 TV_NONE, /* tv_id */ 216 PROP_cfg, /* properties_required */ 217 0, /* properties_provided */ 218 0, /* properties_destroyed */ 219 0, /* todo_flags_start */ 220 0 /* todo_flags_finish */ 221 } 222 }; 223 224 /* Record references to functions and other variables present in the 225 initial value of DECL, a variable. 226 When ONLY_VARS is true, we mark needed only variables, not functions. */ 227 228 void 229 record_references_in_initializer (tree decl, bool only_vars) 230 { 231 struct pointer_set_t *visited_nodes = pointer_set_create (); 232 walk_tree (&DECL_INITIAL (decl), record_reference, 233 only_vars ? NULL : decl, visited_nodes); 234 pointer_set_destroy (visited_nodes); 235 } 236 237 /* Rebuild cgraph edges for current function node. This needs to be run after 238 passes that don't update the cgraph. */ 239 240 unsigned int 241 rebuild_cgraph_edges (void) 242 { 243 basic_block bb; 244 struct cgraph_node *node = cgraph_node (current_function_decl); 245 gimple_stmt_iterator gsi; 246 247 cgraph_node_remove_callees (node); 248 249 node->count = ENTRY_BLOCK_PTR->count; 250 251 FOR_EACH_BB (bb) 252 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi)) 253 { 254 gimple stmt = gsi_stmt (gsi); 255 tree decl; 256 257 if (is_gimple_call (stmt) && (decl = gimple_call_fndecl (stmt))) 258 cgraph_create_edge (node, cgraph_node (decl), stmt, 259 bb->count, 260 compute_call_stmt_bb_frequency 261 (current_function_decl, bb), 262 bb->loop_depth); 263 264 } 265 gcc_assert (!node->global.inlined_to); 266 267 return 0; 268 } 269 270 struct gimple_opt_pass pass_rebuild_cgraph_edges = 271 { 272 { 273 GIMPLE_PASS, 274 "*rebuild_cgraph_edges", /* name */ 275 NULL, /* gate */ 276 rebuild_cgraph_edges, /* execute */ 277 NULL, /* sub */ 278 NULL, /* next */ 279 0, /* static_pass_number */ 280 TV_NONE, /* tv_id */ 281 PROP_cfg, /* properties_required */ 282 0, /* properties_provided */ 283 0, /* properties_destroyed */ 284 0, /* todo_flags_start */ 285 0, /* todo_flags_finish */ 286 } 287 }; 288 289 290 static unsigned int 291 remove_cgraph_callee_edges (void) 292 { 293 cgraph_node_remove_callees (cgraph_node (current_function_decl)); 294 return 0; 295 } 296 297 struct gimple_opt_pass pass_remove_cgraph_callee_edges = 298 { 299 { 300 GIMPLE_PASS, 301 "*remove_cgraph_callee_edges", /* name */ 302 NULL, /* gate */ 303 remove_cgraph_callee_edges, /* execute */ 304 NULL, /* sub */ 305 NULL, /* next */ 306 0, /* static_pass_number */ 307 TV_NONE, /* tv_id */ 308 0, /* properties_required */ 309 0, /* properties_provided */ 310 0, /* properties_destroyed */ 311 0, /* todo_flags_start */ 312 0, /* todo_flags_finish */ 313 } 314 }; 315