1 /* Callgraph handling code. 2 Copyright (C) 2003, 2004, 2005, 2006, 2007, 2008 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 #ifndef GCC_CGRAPH_H 23 #define GCC_CGRAPH_H 24 #include "tree.h" 25 #include "basic-block.h" 26 27 enum availability 28 { 29 /* Not yet set by cgraph_function_body_availability. */ 30 AVAIL_UNSET, 31 /* Function body/variable initializer is unknown. */ 32 AVAIL_NOT_AVAILABLE, 33 /* Function body/variable initializer is known but might be replaced 34 by a different one from other compilation unit and thus needs to 35 be dealt with a care. Like AVAIL_NOT_AVAILABLE it can have 36 arbitrary side effects on escaping variables and functions, while 37 like AVAILABLE it might access static variables. */ 38 AVAIL_OVERWRITABLE, 39 /* Function body/variable initializer is known and will be used in final 40 program. */ 41 AVAIL_AVAILABLE, 42 /* Function body/variable initializer is known and all it's uses are explicitly 43 visible within current unit (ie it's address is never taken and it is not 44 exported to other units). 45 Currently used only for functions. */ 46 AVAIL_LOCAL 47 }; 48 49 extern const char * const cgraph_availability_names[]; 50 51 /* Information about the function collected locally. 52 Available after function is analyzed. */ 53 54 struct cgraph_local_info GTY(()) 55 { 56 struct inline_summary { 57 /* Estimated stack frame consumption by the function. */ 58 HOST_WIDE_INT estimated_self_stack_size; 59 60 /* Size of the function before inlining. */ 61 int self_insns; 62 /* Size of the hot regions of the function before inlining. */ 63 int self_hot_insns; 64 } inline_summary; 65 66 /* Set when function function is visible in current compilation unit only 67 and its address is never taken. */ 68 unsigned local : 1; 69 70 /* Set when function is visible by other units. */ 71 unsigned externally_visible : 1; 72 73 /* Set once it has been finalized so we consider it to be output. */ 74 unsigned finalized : 1; 75 76 /* False when there something makes inlining impossible (such as va_arg). */ 77 unsigned inlinable : 1; 78 79 /* True when function should be inlined independently on its size. */ 80 unsigned disregard_inline_limits : 1; 81 82 /* True when the function has been originally extern inline, but it is 83 redefined now. */ 84 unsigned redefined_extern_inline : 1; 85 86 /* True if statics_read_for_function and 87 statics_written_for_function contain valid data. */ 88 unsigned for_functions_valid : 1; 89 90 /* True if the function is going to be emitted in some other translation 91 unit, referenced from vtable. */ 92 unsigned vtable_method : 1; 93 }; 94 95 /* Information about the function that needs to be computed globally 96 once compilation is finished. Available only with -funit-at-a-time. */ 97 98 struct cgraph_global_info GTY(()) 99 { 100 /* Estimated stack frame consumption by the function. */ 101 HOST_WIDE_INT estimated_stack_size; 102 HOST_WIDE_INT estimated_stack_size_pessimistic; 103 104 /* Expected offset of the stack frame of inlined function. */ 105 HOST_WIDE_INT stack_frame_offset; 106 107 /* For inline clones this points to the function they will be 108 inlined into. */ 109 struct cgraph_node *inlined_to; 110 111 /* Estimated size of the function after inlining. */ 112 int insns; 113 114 /* Estimated growth after inlining. INT_MIN if not computed. */ 115 int estimated_growth; 116 117 /* Set iff the function has been inlined at least once. */ 118 bool inlined; 119 }; 120 121 /* Information about the function that is propagated by the RTL backend. 122 Available only for functions that has been already assembled. */ 123 124 struct cgraph_rtl_info GTY(()) 125 { 126 unsigned int preferred_incoming_stack_boundary; 127 }; 128 129 /* The cgraph data structure. 130 Each function decl has assigned cgraph_node listing callees and callers. */ 131 132 struct cgraph_node GTY((chain_next ("%h.next"), chain_prev ("%h.previous"))) 133 { 134 tree decl; 135 struct cgraph_edge *callees; 136 struct cgraph_edge *callers; 137 struct cgraph_node *next; 138 struct cgraph_node *previous; 139 /* For nested functions points to function the node is nested in. */ 140 struct cgraph_node *origin; 141 /* Points to first nested function, if any. */ 142 struct cgraph_node *nested; 143 /* Pointer to the next function with same origin, if any. */ 144 struct cgraph_node *next_nested; 145 /* Pointer to the next function in cgraph_nodes_queue. */ 146 struct cgraph_node *next_needed; 147 /* Pointer to the next clone. */ 148 struct cgraph_node *next_clone; 149 struct cgraph_node *prev_clone; 150 /* Pointer to a single unique cgraph node for this function. If the 151 function is to be output, this is the copy that will survive. */ 152 struct cgraph_node *master_clone; 153 /* For functions with many calls sites it holds map from call expression 154 to the edge to speed up cgraph_edge function. */ 155 htab_t GTY((param_is (struct cgraph_edge))) call_site_hash; 156 157 PTR GTY ((skip)) aux; 158 159 struct cgraph_local_info local; 160 struct cgraph_global_info global; 161 struct cgraph_rtl_info rtl; 162 163 /* Expected number of executions: calculated in profile.c. */ 164 gcov_type count; 165 /* Unique id of the node. */ 166 int uid; 167 /* Ordering of all cgraph nodes. */ 168 int order; 169 170 /* unique id for profiling. pid is not suitable because of different 171 number of cfg nodes with -fprofile-generate and -fprofile-use */ 172 int pid; 173 174 /* Set when function must be output - it is externally visible 175 or its address is taken. */ 176 unsigned needed : 1; 177 /* Set when decl is an abstract function pointed to by the 178 ABSTRACT_DECL_ORIGIN of a reachable function. */ 179 unsigned abstract_and_needed : 1; 180 /* Set when function is reachable by call from other function 181 that is either reachable or needed. */ 182 unsigned reachable : 1; 183 /* Set once the function is lowered (i.e. its CFG is built). */ 184 unsigned lowered : 1; 185 /* Set once the function has been instantiated and its callee 186 lists created. */ 187 unsigned analyzed : 1; 188 /* Set when function is scheduled to be assembled. */ 189 unsigned output : 1; 190 /* Set for aliases once they got through assemble_alias. */ 191 unsigned alias : 1; 192 193 /* Is this function cloned during versioning ? */ 194 unsigned is_versioned_clone : 1; 195 196 /* In non-unit-at-a-time mode the function body of inline candidates is saved 197 into clone before compiling so the function in original form can be 198 inlined later. This pointer points to the clone. */ 199 tree inline_decl; 200 }; 201 202 struct cgraph_edge GTY((chain_next ("%h.next_caller"), chain_prev ("%h.prev_caller"))) 203 { 204 struct cgraph_node *caller; 205 struct cgraph_node *callee; 206 struct cgraph_edge *prev_caller; 207 struct cgraph_edge *next_caller; 208 struct cgraph_edge *prev_callee; 209 struct cgraph_edge *next_callee; 210 gimple call_stmt; 211 PTR GTY ((skip (""))) aux; 212 /* When NULL, inline this call. When non-NULL, points to the explanation 213 why function was not inlined. */ 214 const char *inline_failed; 215 /* Expected number of executions: calculated in profile.c. */ 216 gcov_type count; 217 /* Expected frequency of executions within the function. 218 When set to CGRAPH_FREQ_BASE, the edge is expected to be called once 219 per function call. The range is 0 to CGRAPH_FREQ_MAX. */ 220 int frequency; 221 /* Depth of loop nest, 1 means no loop nest. */ 222 unsigned int loop_nest : 31; 223 /* Whether this edge describes a call that was originally indirect. */ 224 unsigned int indirect_call : 1; 225 /* Unique id of the edge. */ 226 int uid; 227 }; 228 229 #define CGRAPH_FREQ_BASE 1000 230 #define CGRAPH_FREQ_MAX 100000 231 232 typedef struct cgraph_edge *cgraph_edge_p; 233 234 DEF_VEC_P(cgraph_edge_p); 235 DEF_VEC_ALLOC_P(cgraph_edge_p,heap); 236 237 /* The varpool data structure. 238 Each static variable decl has assigned varpool_node. */ 239 240 struct varpool_node GTY((chain_next ("%h.next"))) 241 { 242 tree decl; 243 /* Pointer to the next function in varpool_nodes. */ 244 struct varpool_node *next; 245 /* Pointer to the next function in varpool_nodes_queue. */ 246 struct varpool_node *next_needed; 247 /* Ordering of all cgraph nodes. */ 248 int order; 249 250 /* The module in which it is first declared. */ 251 unsigned module_id; 252 /* Set when function must be output - it is externally visible 253 or its address is taken. */ 254 unsigned needed : 1; 255 /* Needed variables might become dead by optimization. This flag 256 forces the variable to be output even if it appears dead otherwise. */ 257 unsigned force_output : 1; 258 /* Set once the variable has been instantiated and its callee 259 lists created. */ 260 unsigned analyzed : 1; 261 /* Set once it has been finalized so we consider it to be output. */ 262 unsigned finalized : 1; 263 /* Set when variable is scheduled to be assembled. */ 264 unsigned output : 1; 265 /* Set when function is visible by other units. */ 266 unsigned externally_visible : 1; 267 /* Set for aliases once they got through assemble_alias. */ 268 unsigned alias : 1; 269 }; 270 271 /* Every top level asm statement is put into a cgraph_asm_node. */ 272 273 struct cgraph_asm_node GTY(()) 274 { 275 /* Next asm node. */ 276 struct cgraph_asm_node *next; 277 /* String for this asm node. */ 278 tree asm_str; 279 /* Ordering of all cgraph nodes. */ 280 int order; 281 }; 282 283 extern GTY(()) struct cgraph_node *cgraph_nodes; 284 extern GTY(()) int cgraph_n_nodes; 285 extern GTY(()) int cgraph_max_uid; 286 extern GTY(()) int cgraph_edge_max_uid; 287 extern GTY(()) int cgraph_max_pid; 288 extern bool cgraph_global_info_ready; 289 enum cgraph_state 290 { 291 /* Callgraph is being constructed. It is safe to add new functions. */ 292 CGRAPH_STATE_CONSTRUCTION, 293 /* Callgraph is built and IPA passes are being run. */ 294 CGRAPH_STATE_IPA, 295 /* Callgraph is built and all functions are transformed to SSA form. */ 296 CGRAPH_STATE_IPA_SSA, 297 /* Functions are now ordered and being passed to RTL expanders. */ 298 CGRAPH_STATE_EXPANSION, 299 /* All cgraph expansion is done. */ 300 CGRAPH_STATE_FINISHED 301 }; 302 extern enum cgraph_state cgraph_state; 303 extern bool cgraph_function_flags_ready; 304 extern GTY(()) struct cgraph_node *cgraph_nodes_queue; 305 extern GTY(()) struct cgraph_node *cgraph_new_nodes; 306 307 extern GTY(()) struct cgraph_asm_node *cgraph_asm_nodes; 308 extern GTY(()) int cgraph_order; 309 310 /* In cgraph.c */ 311 void dump_cgraph (FILE *); 312 void debug_cgraph (void); 313 void dump_cgraph_node (FILE *, struct cgraph_node *); 314 void debug_cgraph_node (struct cgraph_node *); 315 void cgraph_insert_node_to_hashtable (struct cgraph_node *node); 316 void cgraph_remove_edge (struct cgraph_edge *); 317 void cgraph_remove_node (struct cgraph_node *); 318 void cgraph_add_assembler_hash_node (struct cgraph_node *); 319 void cgraph_remove_assembler_hash_node (struct cgraph_node *); 320 void cgraph_remove_fake_indirect_call_in_edges (struct cgraph_node *); 321 extern bool cgraph_need_artificial_indirect_call_edges; 322 extern bool cgraph_is_fake_indirect_call_edge (struct cgraph_edge *e); 323 324 void cgraph_release_function_body (struct cgraph_node *); 325 void cgraph_node_remove_callees (struct cgraph_node *node); 326 struct cgraph_edge *cgraph_create_edge (struct cgraph_node *, 327 struct cgraph_node *, 328 gimple, gcov_type, int, int); 329 struct cgraph_node *cgraph_node (tree); 330 struct cgraph_node *cgraph_node_for_asm (tree asmname); 331 struct cgraph_edge *cgraph_edge (struct cgraph_node *, gimple); 332 void cgraph_set_call_stmt (struct cgraph_edge *, gimple); 333 void cgraph_update_edges_for_call_stmt (gimple, gimple); 334 struct cgraph_local_info *cgraph_local_info (tree); 335 struct cgraph_global_info *cgraph_global_info (tree); 336 struct cgraph_rtl_info *cgraph_rtl_info (tree); 337 const char * cgraph_node_name (struct cgraph_node *); 338 struct cgraph_edge * cgraph_clone_edge (struct cgraph_edge *, 339 struct cgraph_node *, 340 gimple, gcov_type, int, int, bool); 341 struct cgraph_node * cgraph_clone_node (struct cgraph_node *, gcov_type, int, 342 int, bool); 343 344 void cgraph_redirect_edge_callee (struct cgraph_edge *, struct cgraph_node *); 345 346 struct cgraph_asm_node *cgraph_add_asm_node (tree); 347 348 bool cgraph_function_possibly_inlined_p (tree); 349 void cgraph_unnest_node (struct cgraph_node *); 350 351 enum availability cgraph_function_body_availability (struct cgraph_node *); 352 bool cgraph_is_master_clone (struct cgraph_node *); 353 struct cgraph_node *cgraph_master_clone (struct cgraph_node *); 354 void cgraph_add_new_function (tree, bool); 355 356 /* In cgraphunit.c */ 357 void cgraph_finalize_function (tree, bool); 358 void cgraph_mark_if_needed (tree); 359 void cgraph_finalize_compilation_unit (void); 360 void cgraph_optimize (void); 361 void cgraph_mark_needed_node (struct cgraph_node *); 362 void cgraph_mark_reachable_node (struct cgraph_node *); 363 bool cgraph_inline_p (struct cgraph_edge *, const char **reason); 364 bool cgraph_preserve_function_body_p (tree); 365 void verify_cgraph (void); 366 void verify_cgraph_node (struct cgraph_node *); 367 void cgraph_build_static_cdtor (char which, tree body, int priority); 368 void cgraph_reset_static_var_maps (void); 369 void init_cgraph (void); 370 struct cgraph_node *cgraph_function_versioning (struct cgraph_node *, 371 VEC(cgraph_edge_p,heap)*, 372 varray_type, 373 bitmap); 374 void cgraph_analyze_function (struct cgraph_node *); 375 struct cgraph_node *save_inline_function_body (struct cgraph_node *); 376 void record_references_in_initializer (tree); 377 bool cgraph_process_new_functions (void); 378 379 /* Module info structure. */ 380 struct cgraph_mod_info GTY (()) 381 { 382 unsigned module_id; 383 }; 384 385 /* LIPO linker symbol table entry for functions. */ 386 387 struct cgraph_sym GTY(()) 388 { 389 tree assembler_name; 390 struct cgraph_node *rep_node; 391 tree rep_decl; 392 htab_t GTY ((param_is (struct cgraph_mod_info))) def_module_hash; 393 bool is_promoted_static; 394 }; 395 396 void cgraph_init_gid_map (void); 397 void cgraph_add_fake_indirect_call_edges (void); 398 void cgraph_do_link (void); 399 struct cgraph_sym *cgraph_link_node (struct cgraph_node *); 400 tree cgraph_find_decl (tree asm_name); 401 void cgraph_remove_link_node (struct cgraph_node *node); 402 struct cgraph_node *cgraph_real_node (tree decl); 403 struct cgraph_node *cgraph_real_node_1 (tree decl, bool); 404 unsigned cgraph_get_module_id (tree fndecl); 405 bool cgraph_is_auxiliary (tree fndecl); 406 void cgraph_process_module_scope_statics (void); 407 bool cgraph_is_promoted_static_func (tree fndecl); 408 bool cgraph_is_inline_body_available_in_module (tree fndecl, unsigned module_id); 409 bool cgraph_is_decl_external (struct cgraph_node *); 410 void cgraph_unify_type_alias_sets (void); 411 void varpool_do_link (void); 412 void varpool_link_node (struct varpool_node *); 413 void varpool_remove_link_node (struct varpool_node *node); 414 struct varpool_node *real_varpool_node (tree decl); 415 bool varpool_is_auxiliary (struct varpool_node *node); 416 void varpool_get_referenced_asm_ids (VEC(tree, gc) **); 417 void varpool_clear_asm_id_reference_bit (void); 418 419 typedef void (*cgraph_edge_hook)(struct cgraph_edge *, void *); 420 typedef void (*cgraph_node_hook)(struct cgraph_node *, void *); 421 typedef void (*cgraph_2edge_hook)(struct cgraph_edge *, struct cgraph_edge *, 422 void *); 423 typedef void (*cgraph_2node_hook)(struct cgraph_node *, struct cgraph_node *, 424 void *); 425 struct cgraph_edge_hook_list; 426 struct cgraph_node_hook_list; 427 struct cgraph_2edge_hook_list; 428 struct cgraph_2node_hook_list; 429 struct cgraph_edge_hook_list *cgraph_add_edge_removal_hook (cgraph_edge_hook, void *); 430 void cgraph_remove_edge_removal_hook (struct cgraph_edge_hook_list *); 431 struct cgraph_node_hook_list *cgraph_add_node_removal_hook (cgraph_node_hook, 432 void *); 433 void cgraph_remove_node_removal_hook (struct cgraph_node_hook_list *); 434 struct cgraph_node_hook_list *cgraph_add_function_insertion_hook (cgraph_node_hook, 435 void *); 436 void cgraph_remove_function_insertion_hook (struct cgraph_node_hook_list *); 437 void cgraph_call_function_insertion_hooks (struct cgraph_node *node); 438 struct cgraph_2edge_hook_list *cgraph_add_edge_duplication_hook (cgraph_2edge_hook, void *); 439 void cgraph_remove_edge_duplication_hook (struct cgraph_2edge_hook_list *); 440 struct cgraph_2node_hook_list *cgraph_add_node_duplication_hook (cgraph_2node_hook, void *); 441 void cgraph_remove_node_duplication_hook (struct cgraph_2node_hook_list *); 442 443 /* In cgraphbuild.c */ 444 unsigned int rebuild_cgraph_edges (void); 445 int compute_call_stmt_bb_frequency (basic_block bb); 446 447 /* In ipa.c */ 448 bool cgraph_remove_unreachable_nodes (bool, FILE *); 449 int cgraph_postorder (struct cgraph_node **); 450 451 bool cgraph_maybe_hot_edge_p (struct cgraph_edge *e); 452 453 /* In varpool.c */ 454 455 extern GTY(()) struct varpool_node *varpool_nodes_queue; 456 extern GTY(()) struct varpool_node *varpool_nodes; 457 458 struct varpool_node *varpool_node (tree); 459 struct varpool_node *varpool_node_for_asm (tree asmname); 460 void varpool_mark_needed_node (struct varpool_node *); 461 void dump_varpool (FILE *); 462 void dump_varpool_node (FILE *, struct varpool_node *); 463 464 void varpool_finalize_decl (tree); 465 bool decide_is_variable_needed (struct varpool_node *, tree); 466 enum availability cgraph_variable_initializer_availability (struct varpool_node *); 467 468 bool varpool_assemble_pending_decls (void); 469 bool varpool_assemble_decl (struct varpool_node *node); 470 bool varpool_analyze_pending_decls (void); 471 void varpool_remove_unreferenced_decls (void); 472 void varpool_empty_needed_queue (void); 473 474 /* Walk all reachable static variables. */ 475 #define FOR_EACH_STATIC_VARIABLE(node) \ 476 for ((node) = varpool_nodes_queue; (node); (node) = (node)->next_needed) 477 478 /* Return first reachable static variable with initializer. */ 479 static inline struct varpool_node * 480 varpool_first_static_initializer (void) 481 { 482 struct varpool_node *node; 483 for (node = varpool_nodes_queue; node; node = node->next_needed) 484 { 485 gcc_assert (TREE_CODE (node->decl) == VAR_DECL); 486 if (DECL_INITIAL (node->decl)) 487 return node; 488 } 489 return NULL; 490 } 491 492 /* Return next reachable static variable with initializer after NODE. */ 493 static inline struct varpool_node * 494 varpool_next_static_initializer (struct varpool_node *node) 495 { 496 for (node = node->next_needed; node; node = node->next_needed) 497 { 498 gcc_assert (TREE_CODE (node->decl) == VAR_DECL); 499 if (DECL_INITIAL (node->decl)) 500 return node; 501 } 502 return NULL; 503 } 504 505 /* Walk all static variables with initializer set. */ 506 #define FOR_EACH_STATIC_INITIALIZER(node) \ 507 for ((node) = varpool_first_static_initializer (); (node); \ 508 (node) = varpool_next_static_initializer (node)) 509 510 /* In ipa-inline.c */ 511 512 /* Contains list of user-specified files containing inlining decisions 513 for particular inlining passes. */ 514 515 struct inline_plan_file 516 { 517 char *pass_name; 518 char *filename; 519 struct inline_plan_file *next; 520 }; 521 extern struct inline_plan_file *inline_plan_files; 522 523 void cgraph_clone_inlined_nodes (struct cgraph_edge *, bool, bool); 524 bool cgraph_default_inline_p (struct cgraph_node *, const char **); 525 unsigned int compute_inline_parameters (struct cgraph_node *); 526 527 void compute_hot_components (void); 528 void free_hot_components (void); 529 void dump_hot_components (FILE *); 530 void verify_hot_components (void); 531 532 /* Create a new static variable of type TYPE. */ 533 tree add_new_static_var (tree type); 534 535 #endif /* GCC_CGRAPH_H */ 536
