1132718Skan/* Callgraph handling code. 2169689Skan Copyright (C) 2003, 2004, 2005 Free Software Foundation, Inc. 3132718Skan Contributed by Jan Hubicka 4132718Skan 5132718SkanThis file is part of GCC. 6132718Skan 7132718SkanGCC is free software; you can redistribute it and/or modify it under 8132718Skanthe terms of the GNU General Public License as published by the Free 9132718SkanSoftware Foundation; either version 2, or (at your option) any later 10132718Skanversion. 11132718Skan 12132718SkanGCC is distributed in the hope that it will be useful, but WITHOUT ANY 13132718SkanWARRANTY; without even the implied warranty of MERCHANTABILITY or 14132718SkanFITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 15132718Skanfor more details. 16132718Skan 17132718SkanYou should have received a copy of the GNU General Public License 18132718Skanalong with GCC; see the file COPYING. If not, write to the Free 19169689SkanSoftware Foundation, 51 Franklin Street, Fifth Floor, Boston, MA 20169689Skan02110-1301, USA. */ 21132718Skan 22132718Skan#ifndef GCC_CGRAPH_H 23132718Skan#define GCC_CGRAPH_H 24169689Skan#include "tree.h" 25169689Skan#include "basic-block.h" 26132718Skan 27169689Skanenum availability 28169689Skan{ 29169689Skan /* Not yet set by cgraph_function_body_availability. */ 30169689Skan AVAIL_UNSET, 31169689Skan /* Function body/variable initializer is unknown. */ 32169689Skan AVAIL_NOT_AVAILABLE, 33169689Skan /* Function body/variable initializer is known but might be replaced 34169689Skan by a different one from other compilation unit and thus needs to 35169689Skan be dealt with a care. Like AVAIL_NOT_AVAILABLE it can have 36169689Skan arbitrary side effects on escaping variables and functions, while 37169689Skan like AVAILABLE it might access static variables. */ 38169689Skan AVAIL_OVERWRITABLE, 39169689Skan /* Function body/variable initializer is known and will be used in final 40169689Skan program. */ 41169689Skan AVAIL_AVAILABLE, 42169689Skan /* Function body/variable initializer is known and all it's uses are explicitly 43169689Skan visible within current unit (ie it's address is never taken and it is not 44169689Skan exported to other units). 45169689Skan Currently used only for functions. */ 46169689Skan AVAIL_LOCAL 47169689Skan}; 48169689Skan 49132718Skan/* Information about the function collected locally. 50132718Skan Available after function is analyzed. */ 51132718Skan 52132718Skanstruct cgraph_local_info GTY(()) 53132718Skan{ 54132718Skan /* Size of the function before inlining. */ 55132718Skan int self_insns; 56132718Skan 57132718Skan /* Set when function function is visible in current compilation unit only 58169689Skan and its address is never taken. */ 59169689Skan unsigned local : 1; 60169689Skan 61169689Skan /* Set when function is visible by other units. */ 62169689Skan unsigned externally_visible : 1; 63169689Skan 64132718Skan /* Set once it has been finalized so we consider it to be output. */ 65169689Skan unsigned finalized : 1; 66132718Skan 67132718Skan /* False when there something makes inlining impossible (such as va_arg). */ 68169689Skan unsigned inlinable : 1; 69169689Skan 70169689Skan /* True when function should be inlined independently on its size. */ 71169689Skan unsigned disregard_inline_limits : 1; 72169689Skan 73132718Skan /* True when the function has been originally extern inline, but it is 74132718Skan redefined now. */ 75169689Skan unsigned redefined_extern_inline : 1; 76169689Skan 77169689Skan /* True if statics_read_for_function and 78169689Skan statics_written_for_function contain valid data. */ 79169689Skan unsigned for_functions_valid : 1; 80169689Skan 81169689Skan /* True if the function is going to be emitted in some other translation 82169689Skan unit, referenced from vtable. */ 83169689Skan unsigned vtable_method : 1; 84132718Skan}; 85132718Skan 86132718Skan/* Information about the function that needs to be computed globally 87132718Skan once compilation is finished. Available only with -funit-at-time. */ 88132718Skan 89132718Skanstruct cgraph_global_info GTY(()) 90132718Skan{ 91169689Skan /* For inline clones this points to the function they will be inlined into. */ 92169689Skan struct cgraph_node *inlined_to; 93169689Skan 94132718Skan /* Estimated size of the function after inlining. */ 95132718Skan int insns; 96132718Skan 97169689Skan /* Estimated growth after inlining. INT_MIN if not computed. */ 98169689Skan int estimated_growth; 99132718Skan 100169689Skan /* Set iff the function has been inlined at least once. */ 101132718Skan bool inlined; 102132718Skan}; 103132718Skan 104132718Skan/* Information about the function that is propagated by the RTL backend. 105132718Skan Available only for functions that has been already assembled. */ 106132718Skan 107132718Skanstruct cgraph_rtl_info GTY(()) 108132718Skan{ 109132718Skan int preferred_incoming_stack_boundary; 110132718Skan}; 111132718Skan 112132718Skan/* The cgraph data structure. 113132718Skan Each function decl has assigned cgraph_node listing callees and callers. */ 114132718Skan 115132718Skanstruct cgraph_node GTY((chain_next ("%h.next"), chain_prev ("%h.previous"))) 116132718Skan{ 117132718Skan tree decl; 118132718Skan struct cgraph_edge *callees; 119132718Skan struct cgraph_edge *callers; 120132718Skan struct cgraph_node *next; 121132718Skan struct cgraph_node *previous; 122132718Skan /* For nested functions points to function the node is nested in. */ 123132718Skan struct cgraph_node *origin; 124132718Skan /* Points to first nested function, if any. */ 125132718Skan struct cgraph_node *nested; 126132718Skan /* Pointer to the next function with same origin, if any. */ 127132718Skan struct cgraph_node *next_nested; 128132718Skan /* Pointer to the next function in cgraph_nodes_queue. */ 129132718Skan struct cgraph_node *next_needed; 130169689Skan /* Pointer to the next clone. */ 131169689Skan struct cgraph_node *next_clone; 132169689Skan struct cgraph_node *prev_clone; 133169689Skan /* Pointer to a single unique cgraph node for this function. If the 134169689Skan function is to be output, this is the copy that will survive. */ 135169689Skan struct cgraph_node *master_clone; 136169689Skan /* For functions with many calls sites it holds map from call expression 137169689Skan to the edge to speed up cgraph_edge function. */ 138169689Skan htab_t GTY((param_is (struct cgraph_edge))) call_site_hash; 139132718Skan 140169689Skan PTR GTY ((skip)) aux; 141169689Skan 142132718Skan struct cgraph_local_info local; 143132718Skan struct cgraph_global_info global; 144132718Skan struct cgraph_rtl_info rtl; 145169689Skan 146169689Skan /* Expected number of executions: calculated in profile.c. */ 147169689Skan gcov_type count; 148132718Skan /* Unique id of the node. */ 149132718Skan int uid; 150169689Skan /* Ordering of all cgraph nodes. */ 151169689Skan int order; 152169689Skan 153132718Skan /* Set when function must be output - it is externally visible 154169689Skan or its address is taken. */ 155169689Skan unsigned needed : 1; 156132718Skan /* Set when function is reachable by call from other function 157132718Skan that is either reachable or needed. */ 158169689Skan unsigned reachable : 1; 159169689Skan /* Set once the function is lowered (i.e. its CFG is built). */ 160169689Skan unsigned lowered : 1; 161132718Skan /* Set once the function has been instantiated and its callee 162132718Skan lists created. */ 163169689Skan unsigned analyzed : 1; 164132718Skan /* Set when function is scheduled to be assembled. */ 165169689Skan unsigned output : 1; 166169689Skan /* Set for aliases once they got through assemble_alias. */ 167169689Skan unsigned alias : 1; 168169689Skan 169169689Skan /* In non-unit-at-a-time mode the function body of inline candidates is saved 170169689Skan into clone before compiling so the function in original form can be 171169689Skan inlined later. This pointer points to the clone. */ 172169689Skan tree inline_decl; 173132718Skan}; 174132718Skan 175169689Skanstruct cgraph_edge GTY((chain_next ("%h.next_caller"), chain_prev ("%h.prev_caller"))) 176132718Skan{ 177132718Skan struct cgraph_node *caller; 178132718Skan struct cgraph_node *callee; 179169689Skan struct cgraph_edge *prev_caller; 180132718Skan struct cgraph_edge *next_caller; 181169689Skan struct cgraph_edge *prev_callee; 182132718Skan struct cgraph_edge *next_callee; 183169689Skan tree call_stmt; 184169689Skan PTR GTY ((skip (""))) aux; 185132718Skan /* When NULL, inline this call. When non-NULL, points to the explanation 186132718Skan why function was not inlined. */ 187132718Skan const char *inline_failed; 188169689Skan /* Expected number of executions: calculated in profile.c. */ 189169689Skan gcov_type count; 190169689Skan /* Depth of loop nest, 1 means no loop nest. */ 191169689Skan int loop_nest; 192132718Skan}; 193132718Skan 194169689Skantypedef struct cgraph_edge *cgraph_edge_p; 195169689Skan 196169689SkanDEF_VEC_P(cgraph_edge_p); 197169689SkanDEF_VEC_ALLOC_P(cgraph_edge_p,heap); 198169689Skan 199132718Skan/* The cgraph_varpool data structure. 200132718Skan Each static variable decl has assigned cgraph_varpool_node. */ 201132718Skan 202132718Skanstruct cgraph_varpool_node GTY(()) 203132718Skan{ 204132718Skan tree decl; 205169689Skan /* Pointer to the next function in cgraph_varpool_nodes. */ 206169689Skan struct cgraph_varpool_node *next; 207132718Skan /* Pointer to the next function in cgraph_varpool_nodes_queue. */ 208132718Skan struct cgraph_varpool_node *next_needed; 209169689Skan /* Ordering of all cgraph nodes. */ 210169689Skan int order; 211132718Skan 212132718Skan /* Set when function must be output - it is externally visible 213169689Skan or its address is taken. */ 214169689Skan unsigned needed : 1; 215169689Skan /* Needed variables might become dead by optimization. This flag 216169689Skan forces the variable to be output even if it appears dead otherwise. */ 217169689Skan unsigned force_output : 1; 218169689Skan /* Set once the variable has been instantiated and its callee 219169689Skan lists created. */ 220169689Skan unsigned analyzed : 1; 221132718Skan /* Set once it has been finalized so we consider it to be output. */ 222169689Skan unsigned finalized : 1; 223169689Skan /* Set when variable is scheduled to be assembled. */ 224169689Skan unsigned output : 1; 225169689Skan /* Set when function is visible by other units. */ 226169689Skan unsigned externally_visible : 1; 227169689Skan /* Set for aliases once they got through assemble_alias. */ 228169689Skan unsigned alias : 1; 229132718Skan}; 230132718Skan 231169689Skan/* Every top level asm statement is put into a cgraph_asm_node. */ 232169689Skan 233169689Skanstruct cgraph_asm_node GTY(()) 234169689Skan{ 235169689Skan /* Next asm node. */ 236169689Skan struct cgraph_asm_node *next; 237169689Skan /* String for this asm node. */ 238169689Skan tree asm_str; 239169689Skan /* Ordering of all cgraph nodes. */ 240169689Skan int order; 241169689Skan}; 242169689Skan 243132718Skanextern GTY(()) struct cgraph_node *cgraph_nodes; 244132718Skanextern GTY(()) int cgraph_n_nodes; 245132718Skanextern GTY(()) int cgraph_max_uid; 246132718Skanextern bool cgraph_global_info_ready; 247169689Skanextern bool cgraph_function_flags_ready; 248132718Skanextern GTY(()) struct cgraph_node *cgraph_nodes_queue; 249169689Skanextern GTY(()) struct cgraph_node *cgraph_expand_queue; 250132718Skan 251169689Skanextern GTY(()) struct cgraph_varpool_node *cgraph_varpool_first_unanalyzed_node; 252169689Skanextern GTY(()) struct cgraph_varpool_node *cgraph_varpool_last_needed_node; 253132718Skanextern GTY(()) struct cgraph_varpool_node *cgraph_varpool_nodes_queue; 254169689Skanextern GTY(()) struct cgraph_varpool_node *cgraph_varpool_nodes; 255169689Skanextern GTY(()) struct cgraph_asm_node *cgraph_asm_nodes; 256169689Skanextern GTY(()) int cgraph_order; 257132718Skan 258132718Skan/* In cgraph.c */ 259132718Skanvoid dump_cgraph (FILE *); 260169689Skanvoid dump_cgraph_node (FILE *, struct cgraph_node *); 261169689Skanvoid cgraph_insert_node_to_hashtable (struct cgraph_node *node); 262169689Skanvoid dump_varpool (FILE *); 263169689Skanvoid dump_cgraph_varpool_node (FILE *, struct cgraph_varpool_node *); 264169689Skanvoid cgraph_remove_edge (struct cgraph_edge *); 265132718Skanvoid cgraph_remove_node (struct cgraph_node *); 266169689Skanvoid cgraph_node_remove_callees (struct cgraph_node *node); 267169689Skanstruct cgraph_edge *cgraph_create_edge (struct cgraph_node *, 268169689Skan struct cgraph_node *, 269169689Skan tree, gcov_type, int); 270169689Skanstruct cgraph_node *cgraph_node (tree); 271169689Skanstruct cgraph_node *cgraph_node_for_asm (tree asmname); 272169689Skanstruct cgraph_edge *cgraph_edge (struct cgraph_node *, tree); 273169689Skanvoid cgraph_set_call_stmt (struct cgraph_edge *, tree); 274132718Skanstruct cgraph_local_info *cgraph_local_info (tree); 275132718Skanstruct cgraph_global_info *cgraph_global_info (tree); 276132718Skanstruct cgraph_rtl_info *cgraph_rtl_info (tree); 277132718Skanconst char * cgraph_node_name (struct cgraph_node *); 278169689Skanstruct cgraph_edge * cgraph_clone_edge (struct cgraph_edge *, 279169689Skan struct cgraph_node *, 280169689Skan tree, gcov_type, int, bool); 281169689Skanstruct cgraph_node * cgraph_clone_node (struct cgraph_node *, gcov_type, 282169689Skan int, bool); 283132718Skan 284169689Skanstruct cgraph_varpool_node *cgraph_varpool_node (tree); 285169689Skanstruct cgraph_varpool_node *cgraph_varpool_node_for_asm (tree asmname); 286132718Skanvoid cgraph_varpool_mark_needed_node (struct cgraph_varpool_node *); 287132718Skanvoid cgraph_varpool_finalize_decl (tree); 288169689Skanvoid cgraph_redirect_edge_callee (struct cgraph_edge *, struct cgraph_node *); 289132718Skan 290169689Skanstruct cgraph_asm_node *cgraph_add_asm_node (tree); 291169689Skan 292132718Skanbool cgraph_function_possibly_inlined_p (tree); 293169689Skanvoid cgraph_unnest_node (struct cgraph_node *); 294169689Skanvoid cgraph_varpool_enqueue_needed_node (struct cgraph_varpool_node *); 295169689Skanvoid cgraph_varpool_reset_queue (void); 296169689Skanbool decide_is_variable_needed (struct cgraph_varpool_node *, tree); 297132718Skan 298169689Skanenum availability cgraph_function_body_availability (struct cgraph_node *); 299169689Skanenum availability cgraph_variable_initializer_availability (struct cgraph_varpool_node *); 300169689Skanbool cgraph_is_master_clone (struct cgraph_node *); 301169689Skanstruct cgraph_node *cgraph_master_clone (struct cgraph_node *); 302169689Skanvoid cgraph_add_new_function (tree); 303169689Skan 304132718Skan/* In cgraphunit.c */ 305261188Spfg/* APPLE LOCAL radar 6305545 */ 306261188Spfgvoid lower_if_nested_functions (tree); 307132718Skanbool cgraph_assemble_pending_functions (void); 308169689Skanbool cgraph_varpool_assemble_pending_decls (void); 309132718Skanvoid cgraph_finalize_function (tree, bool); 310132718Skanvoid cgraph_finalize_compilation_unit (void); 311132718Skanvoid cgraph_optimize (void); 312132718Skanvoid cgraph_mark_needed_node (struct cgraph_node *); 313132718Skanvoid cgraph_mark_reachable_node (struct cgraph_node *); 314169689Skanbool cgraph_inline_p (struct cgraph_edge *, const char **reason); 315169689Skanbool cgraph_preserve_function_body_p (tree); 316169689Skanvoid verify_cgraph (void); 317169689Skanvoid verify_cgraph_node (struct cgraph_node *); 318169689Skanvoid cgraph_build_static_cdtor (char which, tree body, int priority); 319169689Skanvoid cgraph_reset_static_var_maps (void); 320169689Skanvoid init_cgraph (void); 321169689Skanstruct cgraph_node *cgraph_function_versioning (struct cgraph_node *, 322169689Skan VEC(cgraph_edge_p,heap)*, 323169689Skan varray_type); 324169689Skanvoid cgraph_analyze_function (struct cgraph_node *); 325169689Skanstruct cgraph_node *save_inline_function_body (struct cgraph_node *); 326132718Skan 327169689Skan/* In ipa.c */ 328169689Skanbool cgraph_remove_unreachable_nodes (bool, FILE *); 329169689Skanint cgraph_postorder (struct cgraph_node **); 330169689Skan 331169689Skan/* In ipa-inline.c */ 332169689Skanbool cgraph_decide_inlining_incrementally (struct cgraph_node *, bool); 333169689Skanvoid cgraph_clone_inlined_nodes (struct cgraph_edge *, bool, bool); 334169689Skanvoid cgraph_mark_inline_edge (struct cgraph_edge *, bool); 335169689Skanbool cgraph_default_inline_p (struct cgraph_node *, const char **); 336132718Skan#endif /* GCC_CGRAPH_H */ 337