gcc/cgraph.h

   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 GTY(()) cgraph_local_info {
  55   struct inline_summary {
  56     /* Estimated stack frame consumption by the function.  */
  57     HOST_WIDE_INT estimated_self_stack_size;
  58
  59     /* Size of the function before inlining.  */
  60     int self_insns;
  61   } inline_summary;
  62
  63   /* Set when function function is visible in current compilation unit only
  64      and its address is never taken.  */
  65   unsigned local : 1;
  66
  67   /* Set when function is visible by other units.  */
  68   unsigned externally_visible : 1;
  69
  70   /* Set once it has been finalized so we consider it to be output.  */
  71   unsigned finalized : 1;
  72
  73   /* False when there something makes inlining impossible (such as va_arg).  */
  74   unsigned inlinable : 1;
  75
  76   /* True when function should be inlined independently on its size.  */
  77   unsigned disregard_inline_limits : 1;
  78
  79   /* True when the function has been originally extern inline, but it is
  80      redefined now.  */
  81   unsigned redefined_extern_inline : 1;
  82
  83   /* True if statics_read_for_function and
  84      statics_written_for_function contain valid data.  */
  85   unsigned for_functions_valid : 1;
  86
  87   /* True if the function is going to be emitted in some other translation
  88      unit, referenced from vtable.  */
  89   unsigned vtable_method : 1;
  90 };
  91
  92 /* Information about the function that needs to be computed globally
  93    once compilation is finished.  Available only with -funit-at-a-time.  */
  94
  95 struct GTY(()) cgraph_global_info {
  96   /* Estimated stack frame consumption by the function.  */
  97   HOST_WIDE_INT estimated_stack_size;
  98   /* Expected offset of the stack frame of inlined function.  */
  99   HOST_WIDE_INT stack_frame_offset;
 100
 101   /* For inline clones this points to the function they will be
 102      inlined into.  */
 103   struct cgraph_node *inlined_to;
 104
 105   /* Estimated size of the function after inlining.  */
 106   int insns;
 107
 108   /* Estimated growth after inlining.  INT_MIN if not computed.  */
 109   int estimated_growth;
 110
 111   /* Set iff the function has been inlined at least once.  */
 112   bool inlined;
 113 };
 114
 115 /* Information about the function that is propagated by the RTL backend.
 116    Available only for functions that has been already assembled.  */
 117
 118 struct GTY(()) cgraph_rtl_info {
 119    unsigned int preferred_incoming_stack_boundary;
 120 };
 121
 122 /* The cgraph data structure.
 123    Each function decl has assigned cgraph_node listing callees and callers.  */
 124
 125 struct GTY((chain_next ("%h.next"), chain_prev ("%h.previous"))) cgraph_node {
 126   tree decl;
 127   struct cgraph_edge *callees;
 128   struct cgraph_edge *callers;
 129   struct cgraph_node *next;
 130   struct cgraph_node *previous;
 131   /* For nested functions points to function the node is nested in.  */
 132   struct cgraph_node *origin;
 133   /* Points to first nested function, if any.  */
 134   struct cgraph_node *nested;
 135   /* Pointer to the next function with same origin, if any.  */
 136   struct cgraph_node *next_nested;
 137   /* Pointer to the next function in cgraph_nodes_queue.  */
 138   struct cgraph_node *next_needed;
 139   /* Pointer to the next clone.  */
 140   struct cgraph_node *next_clone;
 141   struct cgraph_node *prev_clone;
 142   /* For functions with many calls sites it holds map from call expression
 143      to the edge to speed up cgraph_edge function.  */
 144   htab_t GTY((param_is (struct cgraph_edge))) call_site_hash;
 145
 146   PTR GTY ((skip)) aux;
 147
 148   struct cgraph_local_info local;
 149   struct cgraph_global_info global;
 150   struct cgraph_rtl_info rtl;
 151
 152   /* Expected number of executions: calculated in profile.c.  */
 153   gcov_type count;
 154   /* Unique id of the node.  */
 155   int uid;
 156   /* Ordering of all cgraph nodes.  */
 157   int order;
 158
 159   /* unique id for profiling. pid is not suitable because of different
 160      number of cfg nodes with -fprofile-generate and -fprofile-use */
 161   int pid;
 162
 163   /* Set when function must be output - it is externally visible
 164      or its address is taken.  */
 165   unsigned needed : 1;
 166   /* Set when decl is an abstract function pointed to by the
 167      ABSTRACT_DECL_ORIGIN of a reachable function.  */
 168   unsigned abstract_and_needed : 1;
 169   /* Set when function is reachable by call from other function
 170      that is either reachable or needed.  */
 171   unsigned reachable : 1;
 172   /* Set once the function is lowered (i.e. its CFG is built).  */
 173   unsigned lowered : 1;
 174   /* Set once the function has been instantiated and its callee
 175      lists created.  */
 176   unsigned analyzed : 1;
 177   /* Set when function is scheduled to be processed by local passes.  */
 178   unsigned process : 1;
 179   /* Set for aliases once they got through assemble_alias.  */
 180   unsigned alias : 1;
 181
 182   /* In non-unit-at-a-time mode the function body of inline candidates is saved
 183      into clone before compiling so the function in original form can be
 184      inlined later.  This pointer points to the clone.  */
 185   tree inline_decl;
 186 };
 187
 188 typedef struct cgraph_node *cgraph_node_ptr;
 189
 190 DEF_VEC_P(cgraph_node_ptr);
 191 DEF_VEC_ALLOC_P(cgraph_node_ptr,heap);
 192 DEF_VEC_ALLOC_P(cgraph_node_ptr,gc);
 193
 194 /* A cgraph node set is a collection of cgraph nodes.  A cgraph node
 195    can appear in multiple sets.  */
 196 struct GTY(()) cgraph_node_set_def
 197 {
 198   htab_t GTY((param_is (struct cgraph_node_set_element_def))) hashtab;
 199   VEC(cgraph_node_ptr, gc) *nodes;
 200   PTR GTY ((skip)) aux;
 201 };
 202
 203 typedef struct cgraph_node_set_def *cgraph_node_set;
 204
 205 DEF_VEC_P(cgraph_node_set);
 206 DEF_VEC_ALLOC_P(cgraph_node_set,gc);
 207 DEF_VEC_ALLOC_P(cgraph_node_set,heap);
 208
 209 /* A cgraph node set element contains an index in the vector of nodes in
 210    the set.  */
 211 struct GTY(()) cgraph_node_set_element_def
 212 {
 213   struct cgraph_node *node;
 214   HOST_WIDE_INT index;
 215 };
 216
 217 typedef struct cgraph_node_set_element_def *cgraph_node_set_element;
 218 typedef const struct cgraph_node_set_element_def *const_cgraph_node_set_element;
 219
 220 /* Iterator structure for cgraph node sets.  */
 221 typedef struct
 222 {
 223   cgraph_node_set set;
 224   unsigned index;
 225 } cgraph_node_set_iterator;
 226
 227 #define DEFCIFCODE(code, string)        CIF_ ## code,
 228 /* Reasons for inlining failures.  */
 229 typedef enum {
 230 #include "cif-code.def"
 231   CIF_N_REASONS
 232 } cgraph_inline_failed_t;
 233
 234 struct GTY((chain_next ("%h.next_caller"), chain_prev ("%h.prev_caller"))) cgraph_edge {
 235   struct cgraph_node *caller;
 236   struct cgraph_node *callee;
 237   struct cgraph_edge *prev_caller;
 238   struct cgraph_edge *next_caller;
 239   struct cgraph_edge *prev_callee;
 240   struct cgraph_edge *next_callee;
 241   gimple call_stmt;
 242   PTR GTY ((skip (""))) aux;
 243   /* When equal to CIF_OK, inline this call.  Otherwise, points to the
 244      explanation why function was not inlined.  */
 245   cgraph_inline_failed_t inline_failed;
 246   /* Expected number of executions: calculated in profile.c.  */
 247   gcov_type count;
 248   /* Expected frequency of executions within the function.
 249      When set to CGRAPH_FREQ_BASE, the edge is expected to be called once
 250      per function call.  The range is 0 to CGRAPH_FREQ_MAX.  */
 251   int frequency;
 252   /* Depth of loop nest, 1 means no loop nest.  */
 253   unsigned int loop_nest : 30;
 254   /* Whether this edge describes a call that was originally indirect.  */
 255   unsigned int indirect_call : 1;
 256   /* Can this call throw externally?  */
 257   unsigned int can_throw_external : 1;
 258   /* Unique id of the edge.  */
 259   int uid;
 260 };
 261
 262 #define CGRAPH_FREQ_BASE 1000
 263 #define CGRAPH_FREQ_MAX 100000
 264
 265 typedef struct cgraph_edge *cgraph_edge_p;
 266
 267 DEF_VEC_P(cgraph_edge_p);
 268 DEF_VEC_ALLOC_P(cgraph_edge_p,heap);
 269
 270 /* The varpool data structure.
 271    Each static variable decl has assigned varpool_node.  */
 272
 273 struct GTY((chain_next ("%h.next"))) varpool_node {
 274   tree decl;
 275   /* Pointer to the next function in varpool_nodes.  */
 276   struct varpool_node *next;
 277   /* Pointer to the next function in varpool_nodes_queue.  */
 278   struct varpool_node *next_needed;
 279   /* Ordering of all cgraph nodes.  */
 280   int order;
 281
 282   /* Set when function must be output - it is externally visible
 283      or its address is taken.  */
 284   unsigned needed : 1;
 285   /* Needed variables might become dead by optimization.  This flag
 286      forces the variable to be output even if it appears dead otherwise.  */
 287   unsigned force_output : 1;
 288   /* Set once the variable has been instantiated and its callee
 289      lists created.  */
 290   unsigned analyzed : 1;
 291   /* Set once it has been finalized so we consider it to be output.  */
 292   unsigned finalized : 1;
 293   /* Set when variable is scheduled to be assembled.  */
 294   unsigned output : 1;
 295   /* Set when function is visible by other units.  */
 296   unsigned externally_visible : 1;
 297   /* Set for aliases once they got through assemble_alias.  */
 298   unsigned alias : 1;
 299 };
 300
 301 /* Every top level asm statement is put into a cgraph_asm_node.  */
 302
 303 struct GTY(()) cgraph_asm_node {
 304   /* Next asm node.  */
 305   struct cgraph_asm_node *next;
 306   /* String for this asm node.  */
 307   tree asm_str;
 308   /* Ordering of all cgraph nodes.  */
 309   int order;
 310 };
 311
 312 extern GTY(()) struct cgraph_node *cgraph_nodes;
 313 extern GTY(()) int cgraph_n_nodes;
 314 extern GTY(()) int cgraph_max_uid;
 315 extern GTY(()) int cgraph_edge_max_uid;
 316 extern GTY(()) int cgraph_max_pid;
 317 extern bool cgraph_global_info_ready;
 318 enum cgraph_state
 319 {
 320   /* Callgraph is being constructed.  It is safe to add new functions.  */
 321   CGRAPH_STATE_CONSTRUCTION,
 322   /* Callgraph is built and IPA passes are being run.  */
 323   CGRAPH_STATE_IPA,
 324   /* Callgraph is built and all functions are transformed to SSA form.  */
 325   CGRAPH_STATE_IPA_SSA,
 326   /* Functions are now ordered and being passed to RTL expanders.  */
 327   CGRAPH_STATE_EXPANSION,
 328   /* All cgraph expansion is done.  */
 329   CGRAPH_STATE_FINISHED
 330 };
 331 extern enum cgraph_state cgraph_state;
 332 extern bool cgraph_function_flags_ready;
 333 extern GTY(()) struct cgraph_node *cgraph_nodes_queue;
 334 extern GTY(()) struct cgraph_node *cgraph_new_nodes;
 335
 336 extern GTY(()) struct cgraph_asm_node *cgraph_asm_nodes;
 337 extern GTY(()) int cgraph_order;
 338
 339 /* In cgraph.c  */
 340 void dump_cgraph (FILE *);
 341 void debug_cgraph (void);
 342 void dump_cgraph_node (FILE *, struct cgraph_node *);
 343 void debug_cgraph_node (struct cgraph_node *);
 344 void cgraph_insert_node_to_hashtable (struct cgraph_node *node);
 345 void cgraph_remove_edge (struct cgraph_edge *);
 346 void cgraph_remove_node (struct cgraph_node *);
 347 void cgraph_release_function_body (struct cgraph_node *);
 348 void cgraph_node_remove_callees (struct cgraph_node *node);
 349 struct cgraph_edge *cgraph_create_edge (struct cgraph_node *,
 350                                         struct cgraph_node *,
 351                                         gimple, gcov_type, int, int);
 352 struct cgraph_node *cgraph_node (tree);
 353 struct cgraph_node *cgraph_node_for_asm (tree asmname);
 354 struct cgraph_edge *cgraph_edge (struct cgraph_node *, gimple);
 355 void cgraph_set_call_stmt (struct cgraph_edge *, gimple);
 356 void cgraph_update_edges_for_call_stmt (gimple, gimple);
 357 struct cgraph_local_info *cgraph_local_info (tree);
 358 struct cgraph_global_info *cgraph_global_info (tree);
 359 struct cgraph_rtl_info *cgraph_rtl_info (tree);
 360 const char * cgraph_node_name (struct cgraph_node *);
 361 struct cgraph_edge * cgraph_clone_edge (struct cgraph_edge *,
 362                                         struct cgraph_node *,
 363                                         gimple, gcov_type, int, int, bool);
 364 struct cgraph_node * cgraph_clone_node (struct cgraph_node *, gcov_type, int,
 365                                         int, bool);
 366
 367 void cgraph_redirect_edge_callee (struct cgraph_edge *, struct cgraph_node *);
 368
 369 struct cgraph_asm_node *cgraph_add_asm_node (tree);
 370
 371 bool cgraph_function_possibly_inlined_p (tree);
 372 void cgraph_unnest_node (struct cgraph_node *);
 373
 374 enum availability cgraph_function_body_availability (struct cgraph_node *);
 375 void cgraph_add_new_function (tree, bool);
 376 const char* cgraph_inline_failed_string (cgraph_inline_failed_t);
 377
 378 /* In cgraphunit.c  */
 379 void cgraph_finalize_function (tree, bool);
 380 void cgraph_mark_if_needed (tree);
 381 void cgraph_finalize_compilation_unit (void);
 382 void cgraph_optimize (void);
 383 void cgraph_mark_needed_node (struct cgraph_node *);
 384 void cgraph_mark_reachable_node (struct cgraph_node *);
 385 bool cgraph_inline_p (struct cgraph_edge *, cgraph_inline_failed_t *reason);
 386 bool cgraph_preserve_function_body_p (tree);
 387 void verify_cgraph (void);
 388 void verify_cgraph_node (struct cgraph_node *);
 389 void cgraph_build_static_cdtor (char which, tree body, int priority);
 390 void cgraph_reset_static_var_maps (void);
 391 void init_cgraph (void);
 392 struct cgraph_node *cgraph_function_versioning (struct cgraph_node *,
 393                                                 VEC(cgraph_edge_p,heap)*,
 394                                                 varray_type,
 395                                                 bitmap);
 396 void cgraph_analyze_function (struct cgraph_node *);
 397 struct cgraph_node *save_inline_function_body (struct cgraph_node *);
 398 void record_references_in_initializer (tree);
 399 bool cgraph_process_new_functions (void);
 400
 401 typedef void (*cgraph_edge_hook)(struct cgraph_edge *, void *);
 402 typedef void (*cgraph_node_hook)(struct cgraph_node *, void *);
 403 typedef void (*cgraph_2edge_hook)(struct cgraph_edge *, struct cgraph_edge *,
 404                                   void *);
 405 typedef void (*cgraph_2node_hook)(struct cgraph_node *, struct cgraph_node *,
 406                                   void *);
 407 struct cgraph_edge_hook_list;
 408 struct cgraph_node_hook_list;
 409 struct cgraph_2edge_hook_list;
 410 struct cgraph_2node_hook_list;
 411 struct cgraph_edge_hook_list *cgraph_add_edge_removal_hook (cgraph_edge_hook, void *);
 412 void cgraph_remove_edge_removal_hook (struct cgraph_edge_hook_list *);
 413 struct cgraph_node_hook_list *cgraph_add_node_removal_hook (cgraph_node_hook,
 414                                                             void *);
 415 void cgraph_remove_node_removal_hook (struct cgraph_node_hook_list *);
 416 struct cgraph_node_hook_list *cgraph_add_function_insertion_hook (cgraph_node_hook,
 417                                                                   void *);
 418 void cgraph_remove_function_insertion_hook (struct cgraph_node_hook_list *);
 419 void cgraph_call_function_insertion_hooks (struct cgraph_node *node);
 420 struct cgraph_2edge_hook_list *cgraph_add_edge_duplication_hook (cgraph_2edge_hook, void *);
 421 void cgraph_remove_edge_duplication_hook (struct cgraph_2edge_hook_list *);
 422 struct cgraph_2node_hook_list *cgraph_add_node_duplication_hook (cgraph_2node_hook, void *);
 423 void cgraph_remove_node_duplication_hook (struct cgraph_2node_hook_list *);
 424
 425 /* In cgraphbuild.c  */
 426 unsigned int rebuild_cgraph_edges (void);
 427 int compute_call_stmt_bb_frequency (basic_block bb);
 428
 429 /* In ipa.c  */
 430 bool cgraph_remove_unreachable_nodes (bool, FILE *);
 431 int cgraph_postorder (struct cgraph_node **);
 432 cgraph_node_set cgraph_node_set_new (void);
 433 cgraph_node_set_iterator cgraph_node_set_find (cgraph_node_set,
 434                                                struct cgraph_node *);
 435 void cgraph_node_set_add (cgraph_node_set, struct cgraph_node *);
 436 void cgraph_node_set_remove (cgraph_node_set, struct cgraph_node *);
 437 void dump_cgraph_node_set (FILE *, cgraph_node_set);
 438 void debug_cgraph_node_set (cgraph_node_set);
 439
 440
 441 /* In predict.c  */
 442 bool cgraph_maybe_hot_edge_p (struct cgraph_edge *e);
 443
 444 /* In varpool.c  */
 445 extern GTY(()) struct varpool_node *varpool_nodes_queue;
 446 extern GTY(()) struct varpool_node *varpool_nodes;
 447
 448 struct varpool_node *varpool_node (tree);
 449 struct varpool_node *varpool_node_for_asm (tree asmname);
 450 void varpool_mark_needed_node (struct varpool_node *);
 451 void debug_varpool (void);
 452 void dump_varpool (FILE *);
 453 void dump_varpool_node (FILE *, struct varpool_node *);
 454
 455 void varpool_finalize_decl (tree);
 456 bool decide_is_variable_needed (struct varpool_node *, tree);
 457 enum availability cgraph_variable_initializer_availability (struct varpool_node *);
 458
 459 bool varpool_assemble_pending_decls (void);
 460 bool varpool_assemble_decl (struct varpool_node *node);
 461 bool varpool_analyze_pending_decls (void);
 462 void varpool_remove_unreferenced_decls (void);
 463 void varpool_empty_needed_queue (void);
 464
 465 /* Walk all reachable static variables.  */
 466 #define FOR_EACH_STATIC_VARIABLE(node) \
 467    for ((node) = varpool_nodes_queue; (node); (node) = (node)->next_needed)
 468
 469 /* Return first reachable static variable with initializer.  */
 470 static inline struct varpool_node *
 471 varpool_first_static_initializer (void)
 472 {
 473   struct varpool_node *node;
 474   for (node = varpool_nodes_queue; node; node = node->next_needed)
 475     {
 476       gcc_assert (TREE_CODE (node->decl) == VAR_DECL);
 477       if (DECL_INITIAL (node->decl))
 478         return node;
 479     }
 480   return NULL;
 481 }
 482
 483 /* Return next reachable static variable with initializer after NODE.  */
 484 static inline struct varpool_node *
 485 varpool_next_static_initializer (struct varpool_node *node)
 486 {
 487   for (node = node->next_needed; node; node = node->next_needed)
 488     {
 489       gcc_assert (TREE_CODE (node->decl) == VAR_DECL);
 490       if (DECL_INITIAL (node->decl))
 491         return node;
 492     }
 493   return NULL;
 494 }
 495
 496 /* Walk all static variables with initializer set.  */
 497 #define FOR_EACH_STATIC_INITIALIZER(node) \
 498    for ((node) = varpool_first_static_initializer (); (node); \
 499         (node) = varpool_next_static_initializer (node))
 500
 501 /* In ipa-inline.c  */
 502 void cgraph_clone_inlined_nodes (struct cgraph_edge *, bool, bool);
 503 unsigned int compute_inline_parameters (struct cgraph_node *);
 504
 505
 506 /* Create a new static variable of type TYPE.  */
 507 tree add_new_static_var (tree type);
 508
 509
 510 /* Return true if iterator CSI points to nothing.  */
 511 static inline bool
 512 csi_end_p (cgraph_node_set_iterator csi)
 513 {
 514   return csi.index >= VEC_length (cgraph_node_ptr, csi.set->nodes);
 515 }
 516
 517 /* Advance iterator CSI.  */
 518 static inline void
 519 csi_next (cgraph_node_set_iterator *csi)
 520 {
 521   csi->index++;
 522 }
 523
 524 /* Return the node pointed to by CSI.  */
 525 static inline struct cgraph_node *
 526 csi_node (cgraph_node_set_iterator csi)
 527 {
 528   return VEC_index (cgraph_node_ptr, csi.set->nodes, csi.index);
 529 }
 530
 531 /* Return an iterator to the first node in SET.  */
 532 static inline cgraph_node_set_iterator
 533 csi_start (cgraph_node_set set)
 534 {
 535   cgraph_node_set_iterator csi;
 536
 537   csi.set = set;
 538   csi.index = 0;
 539   return csi;
 540 }
 541
 542 /* Return true if SET contains NODE.  */
 543 static inline bool
 544 cgraph_node_in_set_p (struct cgraph_node *node, cgraph_node_set set)
 545 {
 546   cgraph_node_set_iterator csi;
 547   csi = cgraph_node_set_find (set, node);
 548   return !csi_end_p (csi);
 549 }
 550
 551 /* Return number of nodes in SET.  */
 552 static inline size_t
 553 cgraph_node_set_size (cgraph_node_set set)
 554 {
 555   return htab_elements (set->hashtab);
 556 }
 557
 558
 559 #endif  /* GCC_CGRAPH_H  */