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 /* Maximum count of any basic block in the function. */ 166 gcov_type max_bb_count; 167 /* Unique id of the node. */ 168 int uid; 169 /* Ordering of all cgraph nodes. */ 170 int order; 171 172 /* unique id for profiling. pid is not suitable because of different 173 number of cfg nodes with -fprofile-generate and -fprofile-use */ 174 int pid; 175 176 /* Set when function must be output - it is externally visible 177 or its address is taken. */ 178 unsigned needed : 1; 179 /* Set when decl is an abstract function pointed to by the 180 ABSTRACT_DECL_ORIGIN of a reachable function. */ 181 unsigned abstract_and_needed : 1; 182 /* Set when function is reachable by call from other function 183 that is either reachable or needed. */ 184 unsigned reachable : 1; 185 /* Set once the function is lowered (i.e. its CFG is built). */ 186 unsigned lowered : 1; 187 /* Set once the function has been instantiated and its callee 188 lists created. */ 189 unsigned analyzed : 1; 190 /* Set when function is scheduled to be assembled. */ 191 unsigned output : 1; 192 /* Set for aliases once they got through assemble_alias. */ 193 unsigned alias : 1; 194 195 /* Is this function cloned during versioning ? */ 196 unsigned is_versioned_clone : 1; 197 198 /* In non-unit-at-a-time mode the function body of inline candidates is saved 199 into clone before compiling so the function in original form can be 200 inlined later. This pointer points to the clone. */ 201 tree inline_decl; 202 }; 203 204 struct cgraph_edge GTY((chain_next ("%h.next_caller"), chain_prev ("%h.prev_caller"))) 205 { 206 struct cgraph_node *caller; 207 struct cgraph_node *callee; 208 struct cgraph_edge *prev_caller; 209 struct cgraph_edge *next_caller; 210 struct cgraph_edge *prev_callee; 211 struct cgraph_edge *next_callee; 212 gimple call_stmt; 213 PTR GTY ((skip (""))) aux; 214 /* When NULL, inline this call. When non-NULL, points to the explanation 215 why function was not inlined. */ 216 const char *inline_failed; 217 /* Expected number of executions: calculated in profile.c. */ 218 gcov_type count; 219 /* Expected frequency of executions within the function. 220 When set to CGRAPH_FREQ_BASE, the edge is expected to be called once 221 per function call. The range is 0 to CGRAPH_FREQ_MAX. */ 222 int frequency; 223 /* Depth of loop nest, 1 means no loop nest. */ 224 unsigned int loop_nest : 31; 225 /* Whether this edge describes a call that was originally indirect. */ 226 unsigned int indirect_call : 1; 227 /* Unique id of the edge. */ 228 int uid; 229 }; 230 231 #define CGRAPH_FREQ_BASE 1000 232 #define CGRAPH_FREQ_MAX 100000 233 234 typedef struct cgraph_edge *cgraph_edge_p; 235 236 DEF_VEC_P(cgraph_edge_p); 237 DEF_VEC_ALLOC_P(cgraph_edge_p,heap); 238 239 /* The varpool data structure. 240 Each static variable decl has assigned varpool_node. */ 241 242 struct varpool_node GTY((chain_next ("%h.next"))) 243 { 244 tree decl; 245 /* Pointer to the next function in varpool_nodes. */ 246 struct varpool_node *next; 247 /* Pointer to the next function in varpool_nodes_queue. */ 248 struct varpool_node *next_needed; 249 /* Ordering of all cgraph nodes. */ 250 int order; 251 252 /* The module in which it is first declared. */ 253 unsigned module_id; 254 /* Set when function must be output - it is externally visible 255 or its address is taken. */ 256 unsigned needed : 1; 257 /* Needed variables might become dead by optimization. This flag 258 forces the variable to be output even if it appears dead otherwise. */ 259 unsigned force_output : 1; 260 /* Set once the variable has been instantiated and its callee 261 lists created. */ 262 unsigned analyzed : 1; 263 /* Set once it has been finalized so we consider it to be output. */ 264 unsigned finalized : 1; 265 /* Set when variable is scheduled to be assembled. */ 266 unsigned output : 1; 267 /* Set when function is visible by other units. */ 268 unsigned externally_visible : 1; 269 /* Set for aliases once they got through assemble_alias. */ 270 unsigned alias : 1; 271 }; 272 273 /* Every top level asm statement is put into a cgraph_asm_node. */ 274 275 struct cgraph_asm_node GTY(()) 276 { 277 /* Next asm node. */ 278 struct cgraph_asm_node *next; 279 /* String for this asm node. */ 280 tree asm_str; 281 /* Ordering of all cgraph nodes. */ 282 int order; 283 }; 284 285 extern GTY(()) struct cgraph_node *cgraph_nodes; 286 extern GTY(()) int cgraph_n_nodes; 287 extern GTY(()) int cgraph_max_uid; 288 extern GTY(()) int cgraph_edge_max_uid; 289 extern GTY(()) int cgraph_max_pid; 290 extern bool cgraph_global_info_ready; 291 enum cgraph_state 292 { 293 /* Callgraph is being constructed. It is safe to add new functions. */ 294 CGRAPH_STATE_CONSTRUCTION, 295 /* Callgraph is built and IPA passes are being run. */ 296 CGRAPH_STATE_IPA, 297 /* Callgraph is built and all functions are transformed to SSA form. */ 298 CGRAPH_STATE_IPA_SSA, 299 /* Functions are now ordered and being passed to RTL expanders. */ 300 CGRAPH_STATE_EXPANSION, 301 /* All cgraph expansion is done. */ 302 CGRAPH_STATE_FINISHED 303 }; 304 extern enum cgraph_state cgraph_state; 305 extern bool cgraph_function_flags_ready; 306 extern GTY(()) struct cgraph_node *cgraph_nodes_queue; 307 extern GTY(()) struct cgraph_node *cgraph_new_nodes; 308 309 extern GTY(()) struct cgraph_asm_node *cgraph_asm_nodes; 310 extern GTY(()) int cgraph_order; 311 312 /* In cgraph.c */ 313 void dump_cgraph (FILE *); 314 void debug_cgraph (void); 315 void dump_cgraph_node (FILE *, struct cgraph_node *); 316 void debug_cgraph_node (struct cgraph_node *); 317 void cgraph_insert_node_to_hashtable (struct cgraph_node *node); 318 void cgraph_remove_edge (struct cgraph_edge *); 319 void cgraph_remove_node (struct cgraph_node *); 320 void cgraph_add_assembler_hash_node (struct cgraph_node *); 321 void cgraph_remove_assembler_hash_node (struct cgraph_node *); 322 void cgraph_remove_fake_indirect_call_in_edges (struct cgraph_node *); 323 extern bool cgraph_need_artificial_indirect_call_edges; 324 extern bool cgraph_is_fake_indirect_call_edge (struct cgraph_edge *e); 325 326 void cgraph_release_function_body (struct cgraph_node *); 327 void cgraph_node_remove_callees (struct cgraph_node *node); 328 struct cgraph_edge *cgraph_create_edge (struct cgraph_node *, 329 struct cgraph_node *, 330 gimple, gcov_type, int, int); 331 struct cgraph_node *cgraph_node (tree); 332 struct cgraph_node *cgraph_node_for_asm (tree asmname); 333 struct cgraph_edge *cgraph_edge (struct cgraph_node *, gimple); 334 void cgraph_set_call_stmt (struct cgraph_edge *, gimple); 335 void cgraph_update_edges_for_call_stmt (gimple, gimple); 336 struct cgraph_local_info *cgraph_local_info (tree); 337 struct cgraph_global_info *cgraph_global_info (tree); 338 struct cgraph_rtl_info *cgraph_rtl_info (tree); 339 const char * cgraph_node_name (struct cgraph_node *); 340 struct cgraph_edge * cgraph_clone_edge (struct cgraph_edge *, 341 struct cgraph_node *, 342 gimple, gcov_type, int, int, bool); 343 struct cgraph_node * cgraph_clone_node (struct cgraph_node *, gcov_type, int, 344 int, bool); 345 346 void cgraph_redirect_edge_callee (struct cgraph_edge *, struct cgraph_node *); 347 348 struct cgraph_asm_node *cgraph_add_asm_node (tree); 349 350 bool cgraph_function_possibly_inlined_p (tree); 351 void cgraph_unnest_node (struct cgraph_node *); 352 353 enum availability cgraph_function_body_availability (struct cgraph_node *); 354 bool cgraph_is_master_clone (struct cgraph_node *); 355 struct cgraph_node *cgraph_master_clone (struct cgraph_node *); 356 void cgraph_add_new_function (tree, bool); 357 358 void dump_vcg_cgraph (FILE *, int, bool); 359 360 /* In cgraphunit.c */ 361 void cgraph_finalize_function (tree, bool); 362 void cgraph_mark_if_needed (tree); 363 void cgraph_finalize_compilation_unit (void); 364 void cgraph_optimize (void); 365 void cgraph_mark_needed_node (struct cgraph_node *); 366 void cgraph_mark_reachable_node (struct cgraph_node *); 367 bool cgraph_inline_p (struct cgraph_edge *, const char **reason); 368 bool cgraph_preserve_function_body_p (tree); 369 void verify_cgraph (void); 370 void verify_cgraph_node (struct cgraph_node *); 371 void cgraph_build_static_cdtor (char which, tree body, int priority); 372 void cgraph_reset_static_var_maps (void); 373 void init_cgraph (void); 374 struct cgraph_node *cgraph_function_versioning (struct cgraph_node *, 375 VEC(cgraph_edge_p,heap)*, 376 varray_type, 377 bitmap); 378 void cgraph_analyze_function (struct cgraph_node *); 379 struct cgraph_node *save_inline_function_body (struct cgraph_node *); 380 void record_references_in_initializer (tree); 381 bool cgraph_process_new_functions (void); 382 383 /* Module info structure. */ 384 struct cgraph_mod_info GTY (()) 385 { 386 unsigned module_id; 387 }; 388 389 /* LIPO linker symbol table entry for functions. */ 390 391 struct cgraph_sym GTY(()) 392 { 393 tree assembler_name; 394 struct cgraph_node *rep_node; 395 tree rep_decl; 396 htab_t GTY ((param_is (struct cgraph_mod_info))) def_module_hash; 397 bool is_promoted_static; 398 }; 399 400 void cgraph_init_gid_map (void); 401 void cgraph_add_fake_indirect_call_edges (void); 402 void cgraph_do_link (void); 403 struct cgraph_sym *cgraph_link_node (struct cgraph_node *); 404 tree cgraph_find_decl (tree asm_name); 405 void cgraph_remove_link_node (struct cgraph_node *node); 406 struct cgraph_node *cgraph_real_node (tree decl); 407 struct cgraph_node *cgraph_real_node_1 (tree decl, bool); 408 unsigned cgraph_get_module_id (tree fndecl); 409 bool cgraph_is_auxiliary (tree fndecl); 410 void cgraph_process_module_scope_statics (void); 411 bool cgraph_is_promoted_static_func (tree fndecl); 412 bool cgraph_is_inline_body_available_in_module (tree fndecl, unsigned module_id); 413 bool cgraph_is_decl_external (struct cgraph_node *); 414 void cgraph_unify_type_alias_sets (void); 415 void varpool_do_link (void); 416 void varpool_link_node (struct varpool_node *); 417 void varpool_remove_link_node (struct varpool_node *node); 418 struct varpool_node *real_varpool_node (tree decl); 419 bool varpool_is_auxiliary (struct varpool_node *node); 420 void varpool_get_referenced_asm_ids (VEC(tree, gc) **); 421 void varpool_clear_asm_id_reference_bit (void); 422 void varpool_reset_queue (void); 423 void varpool_remove_duplicate_weak_decls (void); 424 425 typedef void (*cgraph_edge_hook)(struct cgraph_edge *, void *); 426 typedef void (*cgraph_node_hook)(struct cgraph_node *, void *); 427 typedef void (*cgraph_2edge_hook)(struct cgraph_edge *, struct cgraph_edge *, 428 void *); 429 typedef void (*cgraph_2node_hook)(struct cgraph_node *, struct cgraph_node *, 430 void *); 431 struct cgraph_edge_hook_list; 432 struct cgraph_node_hook_list; 433 struct cgraph_2edge_hook_list; 434 struct cgraph_2node_hook_list; 435 struct cgraph_edge_hook_list *cgraph_add_edge_removal_hook (cgraph_edge_hook, void *); 436 void cgraph_remove_edge_removal_hook (struct cgraph_edge_hook_list *); 437 struct cgraph_node_hook_list *cgraph_add_node_removal_hook (cgraph_node_hook, 438 void *); 439 void cgraph_remove_node_removal_hook (struct cgraph_node_hook_list *); 440 struct cgraph_node_hook_list *cgraph_add_function_insertion_hook (cgraph_node_hook, 441 void *); 442 void cgraph_remove_function_insertion_hook (struct cgraph_node_hook_list *); 443 void cgraph_call_function_insertion_hooks (struct cgraph_node *node); 444 struct cgraph_2edge_hook_list *cgraph_add_edge_duplication_hook (cgraph_2edge_hook, void *); 445 void cgraph_remove_edge_duplication_hook (struct cgraph_2edge_hook_list *); 446 struct cgraph_2node_hook_list *cgraph_add_node_duplication_hook (cgraph_2node_hook, void *); 447 void cgraph_remove_node_duplication_hook (struct cgraph_2node_hook_list *); 448 449 /* In cgraphbuild.c */ 450 unsigned int rebuild_cgraph_edges (void); 451 int compute_call_stmt_bb_frequency (basic_block bb); 452 453 /* In ipa.c */ 454 bool cgraph_remove_unreachable_nodes (bool, FILE *); 455 int cgraph_postorder (struct cgraph_node **); 456 457 bool cgraph_maybe_hot_edge_p (struct cgraph_edge *e); 458 459 /* In varpool.c */ 460 461 extern GTY(()) struct varpool_node *varpool_nodes_queue; 462 extern GTY(()) struct varpool_node *varpool_nodes; 463 464 struct varpool_node *varpool_node (tree); 465 struct varpool_node *varpool_node_for_asm (tree asmname); 466 void varpool_mark_needed_node (struct varpool_node *); 467 void dump_varpool (FILE *); 468 void dump_varpool_node (FILE *, struct varpool_node *); 469 470 void varpool_finalize_decl (tree); 471 bool decide_is_variable_needed (struct varpool_node *, tree); 472 enum availability cgraph_variable_initializer_availability (struct varpool_node *); 473 474 bool varpool_assemble_pending_decls (void); 475 bool varpool_assemble_decl (struct varpool_node *node); 476 bool varpool_analyze_pending_decls (void); 477 void varpool_remove_unreferenced_decls (void); 478 void varpool_empty_needed_queue (void); 479 480 /* Walk all reachable static variables. */ 481 #define FOR_EACH_STATIC_VARIABLE(node) \ 482 for ((node) = varpool_nodes_queue; (node); (node) = (node)->next_needed) 483 484 /* Return first reachable static variable with initializer. */ 485 static inline struct varpool_node * 486 varpool_first_static_initializer (void) 487 { 488 struct varpool_node *node; 489 for (node = varpool_nodes_queue; node; node = node->next_needed) 490 { 491 gcc_assert (TREE_CODE (node->decl) == VAR_DECL); 492 if (DECL_INITIAL (node->decl)) 493 return node; 494 } 495 return NULL; 496 } 497 498 /* Return next reachable static variable with initializer after NODE. */ 499 static inline struct varpool_node * 500 varpool_next_static_initializer (struct varpool_node *node) 501 { 502 for (node = node->next_needed; node; node = node->next_needed) 503 { 504 gcc_assert (TREE_CODE (node->decl) == VAR_DECL); 505 if (DECL_INITIAL (node->decl)) 506 return node; 507 } 508 return NULL; 509 } 510 511 /* Walk all static variables with initializer set. */ 512 #define FOR_EACH_STATIC_INITIALIZER(node) \ 513 for ((node) = varpool_first_static_initializer (); (node); \ 514 (node) = varpool_next_static_initializer (node)) 515 516 /* In ipa-inline.c */ 517 518 /* Contains list of user-specified files containing inlining decisions 519 for particular inlining passes. */ 520 521 struct inline_plan_file 522 { 523 char *pass_name; 524 char *filename; 525 struct inline_plan_file *next; 526 }; 527 extern struct inline_plan_file *inline_plan_files; 528 529 void cgraph_clone_inlined_nodes (struct cgraph_edge *, bool, bool); 530 bool cgraph_default_inline_p (struct cgraph_node *, const char **); 531 unsigned int compute_inline_parameters (struct cgraph_node *); 532 533 void compute_hot_components (void); 534 void free_hot_components (void); 535 void dump_hot_components (FILE *); 536 void verify_hot_components (void); 537 bool cgraph_gate_ipa_early_inlining (void); 538 539 /* Create a new static variable of type TYPE. */ 540 tree add_new_static_var (tree type); 541 542 #endif /* GCC_CGRAPH_H */ 543
