gcc/cgraph.c

   1 /* Callgraph handling code.
   2    Copyright (C) 2003, 2004, 2005, 2006, 2007, 2008, 2009, 2010,
   3    2011, 2012 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 /*  This file contains basic routines manipulating call graph
  23
  24     The call-graph is a data structure designed for intra-procedural optimization.
  25     It represents a multi-graph where nodes are functions and edges are call sites. */
  26
  27 #include "config.h"
  28 #include "system.h"
  29 #include "coretypes.h"
  30 #include "tm.h"
  31 #include "tree.h"
  32 #include "tree-inline.h"
  33 #include "langhooks.h"
  34 #include "hashtab.h"
  35 #include "toplev.h"
  36 #include "flags.h"
  37 #include "ggc.h"
  38 #include "debug.h"
  39 #include "target.h"
  40 #include "basic-block.h"
  41 #include "cgraph.h"
  42 #include "output.h"
  43 #include "intl.h"
  44 #include "gimple.h"
  45 #include "tree-dump.h"
  46 #include "tree-flow.h"
  47 #include "value-prof.h"
  48 #include "except.h"
  49 #include "diagnostic-core.h"
  50 #include "rtl.h"
  51 #include "ipa-utils.h"
  52 #include "lto-streamer.h"
  53 #include "ipa-inline.h"
  54 #include "cfgloop.h"
  55 #include "gimple-pretty-print.h"
  56
  57 static void cgraph_node_remove_callers (struct cgraph_node *node);
  58 static inline void cgraph_edge_remove_caller (struct cgraph_edge *e);
  59 static inline void cgraph_edge_remove_callee (struct cgraph_edge *e);
  60
  61 /* Queue of cgraph nodes scheduled to be lowered.  */
  62 symtab_node x_cgraph_nodes_queue;
  63 #define cgraph_nodes_queue ((struct cgraph_node *)x_cgraph_nodes_queue)
  64
  65 /* Number of nodes in existence.  */
  66 int cgraph_n_nodes;
  67
  68 /* Maximal uid used in cgraph nodes.  */
  69 int cgraph_max_uid;
  70
  71 /* Maximal uid used in cgraph edges.  */
  72 int cgraph_edge_max_uid;
  73
  74 /* Set when whole unit has been analyzed so we can access global info.  */
  75 bool cgraph_global_info_ready = false;
  76
  77 /* What state callgraph is in right now.  */
  78 enum cgraph_state cgraph_state = CGRAPH_STATE_PARSING;
  79
  80 /* Set when the cgraph is fully build and the basic flags are computed.  */
  81 bool cgraph_function_flags_ready = false;
  82
  83 /* List of hooks triggered on cgraph_edge events.  */
  84 struct cgraph_edge_hook_list {
  85   cgraph_edge_hook hook;
  86   void *data;
  87   struct cgraph_edge_hook_list *next;
  88 };
  89
  90 /* List of hooks triggered on cgraph_node events.  */
  91 struct cgraph_node_hook_list {
  92   cgraph_node_hook hook;
  93   void *data;
  94   struct cgraph_node_hook_list *next;
  95 };
  96
  97 /* List of hooks triggered on events involving two cgraph_edges.  */
  98 struct cgraph_2edge_hook_list {
  99   cgraph_2edge_hook hook;
 100   void *data;
 101   struct cgraph_2edge_hook_list *next;
 102 };
 103
 104 /* List of hooks triggered on events involving two cgraph_nodes.  */
 105 struct cgraph_2node_hook_list {
 106   cgraph_2node_hook hook;
 107   void *data;
 108   struct cgraph_2node_hook_list *next;
 109 };
 110
 111 /* List of hooks triggered when an edge is removed.  */
 112 struct cgraph_edge_hook_list *first_cgraph_edge_removal_hook;
 113 /* List of hooks triggered when a node is removed.  */
 114 struct cgraph_node_hook_list *first_cgraph_node_removal_hook;
 115 /* List of hooks triggered when an edge is duplicated.  */
 116 struct cgraph_2edge_hook_list *first_cgraph_edge_duplicated_hook;
 117 /* List of hooks triggered when a node is duplicated.  */
 118 struct cgraph_2node_hook_list *first_cgraph_node_duplicated_hook;
 119 /* List of hooks triggered when an function is inserted.  */
 120 struct cgraph_node_hook_list *first_cgraph_function_insertion_hook;
 121
 122 /* Head of a linked list of unused (freed) call graph nodes.
 123    Do not GTY((delete)) this list so UIDs gets reliably recycled.  */
 124 static GTY(()) struct cgraph_node *free_nodes;
 125 /* Head of a linked list of unused (freed) call graph edges.
 126    Do not GTY((delete)) this list so UIDs gets reliably recycled.  */
 127 static GTY(()) struct cgraph_edge *free_edges;
 128
 129 /* Did procss_same_body_aliases run?  */
 130 bool same_body_aliases_done;
 131
 132 /* Macros to access the next item in the list of free cgraph nodes and
 133    edges. */
 134 #define NEXT_FREE_NODE(NODE) cgraph ((NODE)->symbol.next)
 135 #define SET_NEXT_FREE_NODE(NODE,NODE2) ((NODE))->symbol.next = (symtab_node)NODE2
 136 #define NEXT_FREE_EDGE(EDGE) (EDGE)->prev_caller
 137
 138 /* Register HOOK to be called with DATA on each removed edge.  */
 139 struct cgraph_edge_hook_list *
 140 cgraph_add_edge_removal_hook (cgraph_edge_hook hook, void *data)
 141 {
 142   struct cgraph_edge_hook_list *entry;
 143   struct cgraph_edge_hook_list **ptr = &first_cgraph_edge_removal_hook;
 144
 145   entry = (struct cgraph_edge_hook_list *) xmalloc (sizeof (*entry));
 146   entry->hook = hook;
 147   entry->data = data;
 148   entry->next = NULL;
 149   while (*ptr)
 150     ptr = &(*ptr)->next;
 151   *ptr = entry;
 152   return entry;
 153 }
 154
 155 /* Remove ENTRY from the list of hooks called on removing edges.  */
 156 void
 157 cgraph_remove_edge_removal_hook (struct cgraph_edge_hook_list *entry)
 158 {
 159   struct cgraph_edge_hook_list **ptr = &first_cgraph_edge_removal_hook;
 160
 161   while (*ptr != entry)
 162     ptr = &(*ptr)->next;
 163   *ptr = entry->next;
 164   free (entry);
 165 }
 166
 167 /* Call all edge removal hooks.  */
 168 static void
 169 cgraph_call_edge_removal_hooks (struct cgraph_edge *e)
 170 {
 171   struct cgraph_edge_hook_list *entry = first_cgraph_edge_removal_hook;
 172   while (entry)
 173   {
 174     entry->hook (e, entry->data);
 175     entry = entry->next;
 176   }
 177 }
 178
 179 /* Register HOOK to be called with DATA on each removed node.  */
 180 struct cgraph_node_hook_list *
 181 cgraph_add_node_removal_hook (cgraph_node_hook hook, void *data)
 182 {
 183   struct cgraph_node_hook_list *entry;
 184   struct cgraph_node_hook_list **ptr = &first_cgraph_node_removal_hook;
 185
 186   entry = (struct cgraph_node_hook_list *) xmalloc (sizeof (*entry));
 187   entry->hook = hook;
 188   entry->data = data;
 189   entry->next = NULL;
 190   while (*ptr)
 191     ptr = &(*ptr)->next;
 192   *ptr = entry;
 193   return entry;
 194 }
 195
 196 /* Remove ENTRY from the list of hooks called on removing nodes.  */
 197 void
 198 cgraph_remove_node_removal_hook (struct cgraph_node_hook_list *entry)
 199 {
 200   struct cgraph_node_hook_list **ptr = &first_cgraph_node_removal_hook;
 201
 202   while (*ptr != entry)
 203     ptr = &(*ptr)->next;
 204   *ptr = entry->next;
 205   free (entry);
 206 }
 207
 208 /* Call all node removal hooks.  */
 209 static void
 210 cgraph_call_node_removal_hooks (struct cgraph_node *node)
 211 {
 212   struct cgraph_node_hook_list *entry = first_cgraph_node_removal_hook;
 213   while (entry)
 214   {
 215     entry->hook (node, entry->data);
 216     entry = entry->next;
 217   }
 218 }
 219
 220 /* Register HOOK to be called with DATA on each inserted node.  */
 221 struct cgraph_node_hook_list *
 222 cgraph_add_function_insertion_hook (cgraph_node_hook hook, void *data)
 223 {
 224   struct cgraph_node_hook_list *entry;
 225   struct cgraph_node_hook_list **ptr = &first_cgraph_function_insertion_hook;
 226
 227   entry = (struct cgraph_node_hook_list *) xmalloc (sizeof (*entry));
 228   entry->hook = hook;
 229   entry->data = data;
 230   entry->next = NULL;
 231   while (*ptr)
 232     ptr = &(*ptr)->next;
 233   *ptr = entry;
 234   return entry;
 235 }
 236
 237 /* Remove ENTRY from the list of hooks called on inserted nodes.  */
 238 void
 239 cgraph_remove_function_insertion_hook (struct cgraph_node_hook_list *entry)
 240 {
 241   struct cgraph_node_hook_list **ptr = &first_cgraph_function_insertion_hook;
 242
 243   while (*ptr != entry)
 244     ptr = &(*ptr)->next;
 245   *ptr = entry->next;
 246   free (entry);
 247 }
 248
 249 /* Call all node insertion hooks.  */
 250 void
 251 cgraph_call_function_insertion_hooks (struct cgraph_node *node)
 252 {
 253   struct cgraph_node_hook_list *entry = first_cgraph_function_insertion_hook;
 254   while (entry)
 255   {
 256     entry->hook (node, entry->data);
 257     entry = entry->next;
 258   }
 259 }
 260
 261 /* Register HOOK to be called with DATA on each duplicated edge.  */
 262 struct cgraph_2edge_hook_list *
 263 cgraph_add_edge_duplication_hook (cgraph_2edge_hook hook, void *data)
 264 {
 265   struct cgraph_2edge_hook_list *entry;
 266   struct cgraph_2edge_hook_list **ptr = &first_cgraph_edge_duplicated_hook;
 267
 268   entry = (struct cgraph_2edge_hook_list *) xmalloc (sizeof (*entry));
 269   entry->hook = hook;
 270   entry->data = data;
 271   entry->next = NULL;
 272   while (*ptr)
 273     ptr = &(*ptr)->next;
 274   *ptr = entry;
 275   return entry;
 276 }
 277
 278 /* Remove ENTRY from the list of hooks called on duplicating edges.  */
 279 void
 280 cgraph_remove_edge_duplication_hook (struct cgraph_2edge_hook_list *entry)
 281 {
 282   struct cgraph_2edge_hook_list **ptr = &first_cgraph_edge_duplicated_hook;
 283
 284   while (*ptr != entry)
 285     ptr = &(*ptr)->next;
 286   *ptr = entry->next;
 287   free (entry);
 288 }
 289
 290 /* Call all edge duplication hooks.  */
 291 void
 292 cgraph_call_edge_duplication_hooks (struct cgraph_edge *cs1,
 293                                     struct cgraph_edge *cs2)
 294 {
 295   struct cgraph_2edge_hook_list *entry = first_cgraph_edge_duplicated_hook;
 296   while (entry)
 297   {
 298     entry->hook (cs1, cs2, entry->data);
 299     entry = entry->next;
 300   }
 301 }
 302
 303 /* Register HOOK to be called with DATA on each duplicated node.  */
 304 struct cgraph_2node_hook_list *
 305 cgraph_add_node_duplication_hook (cgraph_2node_hook hook, void *data)
 306 {
 307   struct cgraph_2node_hook_list *entry;
 308   struct cgraph_2node_hook_list **ptr = &first_cgraph_node_duplicated_hook;
 309
 310   entry = (struct cgraph_2node_hook_list *) xmalloc (sizeof (*entry));
 311   entry->hook = hook;
 312   entry->data = data;
 313   entry->next = NULL;
 314   while (*ptr)
 315     ptr = &(*ptr)->next;
 316   *ptr = entry;
 317   return entry;
 318 }
 319
 320 /* Remove ENTRY from the list of hooks called on duplicating nodes.  */
 321 void
 322 cgraph_remove_node_duplication_hook (struct cgraph_2node_hook_list *entry)
 323 {
 324   struct cgraph_2node_hook_list **ptr = &first_cgraph_node_duplicated_hook;
 325
 326   while (*ptr != entry)
 327     ptr = &(*ptr)->next;
 328   *ptr = entry->next;
 329   free (entry);
 330 }
 331
 332 /* Call all node duplication hooks.  */
 333 void
 334 cgraph_call_node_duplication_hooks (struct cgraph_node *node1,
 335                                     struct cgraph_node *node2)
 336 {
 337   struct cgraph_2node_hook_list *entry = first_cgraph_node_duplicated_hook;
 338   while (entry)
 339   {
 340     entry->hook (node1, node2, entry->data);
 341     entry = entry->next;
 342   }
 343 }
 344
 345 /* Allocate new callgraph node.  */
 346
 347 static inline struct cgraph_node *
 348 cgraph_allocate_node (void)
 349 {
 350   struct cgraph_node *node;
 351
 352   if (free_nodes)
 353     {
 354       node = free_nodes;
 355       free_nodes = NEXT_FREE_NODE (node);
 356     }
 357   else
 358     {
 359       node = ggc_alloc_cleared_cgraph_node ();
 360       node->uid = cgraph_max_uid++;
 361     }
 362
 363   return node;
 364 }
 365
 366 /* Allocate new callgraph node and insert it into basic data structures.  */
 367
 368 struct cgraph_node *
 369 cgraph_create_empty_node (void)
 370 {
 371   struct cgraph_node *node = cgraph_allocate_node ();
 372
 373   node->symbol.type = SYMTAB_FUNCTION;
 374   node->frequency = NODE_FREQUENCY_NORMAL;
 375   node->count_materialization_scale = REG_BR_PROB_BASE;
 376   cgraph_n_nodes++;
 377   return node;
 378 }
 379
 380 /* Return cgraph node assigned to DECL.  Create new one when needed.  */
 381
 382 struct cgraph_node *
 383 cgraph_create_node (tree decl)
 384 {
 385   struct cgraph_node *node = cgraph_create_empty_node ();
 386   gcc_assert (TREE_CODE (decl) == FUNCTION_DECL);
 387
 388   node->symbol.decl = decl;
 389   symtab_register_node ((symtab_node) node);
 390
 391   if (DECL_CONTEXT (decl) && TREE_CODE (DECL_CONTEXT (decl)) == FUNCTION_DECL)
 392     {
 393       node->origin = cgraph_get_create_node (DECL_CONTEXT (decl));
 394       node->next_nested = node->origin->nested;
 395       node->origin->nested = node;
 396     }
 397   return node;
 398 }
 399
 400 /* Try to find a call graph node for declaration DECL and if it does not exist,
 401    create it.  */
 402
 403 struct cgraph_node *
 404 cgraph_get_create_node (tree decl)
 405 {
 406   struct cgraph_node *node;
 407
 408   node = cgraph_get_node (decl);
 409   if (node)
 410     return node;
 411
 412   return cgraph_create_node (decl);
 413 }
 414
 415 /* Mark ALIAS as an alias to DECL.  DECL_NODE is cgraph node representing
 416    the function body is associated with (not neccesarily cgraph_node (DECL).  */
 417
 418 struct cgraph_node *
 419 cgraph_create_function_alias (tree alias, tree decl)
 420 {
 421   struct cgraph_node *alias_node;
 422
 423   gcc_assert (TREE_CODE (decl) == FUNCTION_DECL);
 424   gcc_assert (TREE_CODE (alias) == FUNCTION_DECL);
 425   alias_node = cgraph_get_create_node (alias);
 426   gcc_assert (!alias_node->local.finalized);
 427   alias_node->thunk.alias = decl;
 428   alias_node->local.finalized = true;
 429   alias_node->alias = 1;
 430   return alias_node;
 431 }
 432
 433 /* Attempt to mark ALIAS as an alias to DECL.  Return alias node if successful
 434    and NULL otherwise.
 435    Same body aliases are output whenever the body of DECL is output,
 436    and cgraph_get_node (ALIAS) transparently returns cgraph_get_node (DECL).  */
 437
 438 struct cgraph_node *
 439 cgraph_same_body_alias (struct cgraph_node *decl_node ATTRIBUTE_UNUSED, tree alias, tree decl)
 440 {
 441   struct cgraph_node *n;
 442 #ifndef ASM_OUTPUT_DEF
 443   /* If aliases aren't supported by the assembler, fail.  */
 444   return NULL;
 445 #endif
 446   /* Langhooks can create same body aliases of symbols not defined.
 447      Those are useless. Drop them on the floor.  */
 448   if (cgraph_global_info_ready)
 449     return NULL;
 450
 451   n = cgraph_create_function_alias (alias, decl);
 452   n->same_body_alias = true;
 453   if (same_body_aliases_done)
 454     ipa_record_reference ((symtab_node)n, (symtab_node)cgraph_get_node (decl),
 455                           IPA_REF_ALIAS, NULL);
 456   return n;
 457 }
 458
 459 /* Add thunk alias into callgraph.  The alias declaration is ALIAS and it
 460    aliases DECL with an adjustments made into the first parameter.
 461    See comments in thunk_adjust for detail on the parameters.  */
 462
 463 struct cgraph_node *
 464 cgraph_add_thunk (struct cgraph_node *decl_node ATTRIBUTE_UNUSED,
 465                   tree alias, tree decl ATTRIBUTE_UNUSED,
 466                   bool this_adjusting,
 467                   HOST_WIDE_INT fixed_offset, HOST_WIDE_INT virtual_value,
 468                   tree virtual_offset,
 469                   tree real_alias)
 470 {
 471   struct cgraph_node *node;
 472
 473   node = cgraph_get_node (alias);
 474   if (node)
 475     {
 476       gcc_assert (node->local.finalized);
 477       gcc_assert (!node->alias);
 478       gcc_assert (!node->thunk.thunk_p);
 479       cgraph_remove_node (node);
 480     }
 481
 482   node = cgraph_create_node (alias);
 483   gcc_checking_assert (!virtual_offset
 484                        || double_int_equal_p
 485                             (tree_to_double_int (virtual_offset),
 486                              shwi_to_double_int (virtual_value)));
 487   node->thunk.fixed_offset = fixed_offset;
 488   node->thunk.this_adjusting = this_adjusting;
 489   node->thunk.virtual_value = virtual_value;
 490   node->thunk.virtual_offset_p = virtual_offset != NULL;
 491   node->thunk.alias = real_alias;
 492   node->thunk.thunk_p = true;
 493   node->local.finalized = true;
 494
 495   return node;
 496 }
 497
 498 /* Return the cgraph node that has ASMNAME for its DECL_ASSEMBLER_NAME.
 499    Return NULL if there's no such node.  */
 500
 501 struct cgraph_node *
 502 cgraph_node_for_asm (tree asmname)
 503 {
 504   symtab_node node = symtab_node_for_asm (asmname);
 505
 506   /* We do not want to look at inline clones.  */
 507   for (node = symtab_node_for_asm (asmname); node; node = node->symbol.next_sharing_asm_name)
 508     if (symtab_function_p (node) && !cgraph(node)->global.inlined_to)
 509       return cgraph (node);
 510   return NULL;
 511 }
 512
 513 /* Returns a hash value for X (which really is a die_struct).  */
 514
 515 static hashval_t
 516 edge_hash (const void *x)
 517 {
 518   return htab_hash_pointer (((const struct cgraph_edge *) x)->call_stmt);
 519 }
 520
 521 /* Return nonzero if decl_id of die_struct X is the same as UID of decl *Y.  */
 522
 523 static int
 524 edge_eq (const void *x, const void *y)
 525 {
 526   return ((const struct cgraph_edge *) x)->call_stmt == y;
 527 }
 528
 529 /* Add call graph edge E to call site hash of its caller.  */
 530
 531 static inline void
 532 cgraph_add_edge_to_call_site_hash (struct cgraph_edge *e)
 533 {
 534   void **slot;
 535   slot = htab_find_slot_with_hash (e->caller->call_site_hash,
 536                                    e->call_stmt,
 537                                    htab_hash_pointer (e->call_stmt),
 538                                    INSERT);
 539   gcc_assert (!*slot);
 540   *slot = e;
 541 }
 542
 543 /* Return the callgraph edge representing the GIMPLE_CALL statement
 544    CALL_STMT.  */
 545
 546 struct cgraph_edge *
 547 cgraph_edge (struct cgraph_node *node, gimple call_stmt)
 548 {
 549   struct cgraph_edge *e, *e2;
 550   int n = 0;
 551
 552   if (node->call_site_hash)
 553     return (struct cgraph_edge *)
 554       htab_find_with_hash (node->call_site_hash, call_stmt,
 555                            htab_hash_pointer (call_stmt));
 556
 557   /* This loop may turn out to be performance problem.  In such case adding
 558      hashtables into call nodes with very many edges is probably best
 559      solution.  It is not good idea to add pointer into CALL_EXPR itself
 560      because we want to make possible having multiple cgraph nodes representing
 561      different clones of the same body before the body is actually cloned.  */
 562   for (e = node->callees; e; e = e->next_callee)
 563     {
 564       if (e->call_stmt == call_stmt)
 565         break;
 566       n++;
 567     }
 568
 569   if (!e)
 570     for (e = node->indirect_calls; e; e = e->next_callee)
 571       {
 572         if (e->call_stmt == call_stmt)
 573           break;
 574         n++;
 575       }
 576
 577   if (n > 100)
 578     {
 579       node->call_site_hash = htab_create_ggc (120, edge_hash, edge_eq, NULL);
 580       for (e2 = node->callees; e2; e2 = e2->next_callee)
 581         cgraph_add_edge_to_call_site_hash (e2);
 582       for (e2 = node->indirect_calls; e2; e2 = e2->next_callee)
 583         cgraph_add_edge_to_call_site_hash (e2);
 584     }
 585
 586   return e;
 587 }
 588
 589
 590 /* Change field call_stmt of edge E to NEW_STMT.  */
 591
 592 void
 593 cgraph_set_call_stmt (struct cgraph_edge *e, gimple new_stmt)
 594 {
 595   tree decl;
 596
 597   if (e->caller->call_site_hash)
 598     {
 599       htab_remove_elt_with_hash (e->caller->call_site_hash,
 600                                  e->call_stmt,
 601                                  htab_hash_pointer (e->call_stmt));
 602     }
 603
 604   e->call_stmt = new_stmt;
 605   if (e->indirect_unknown_callee
 606       && (decl = gimple_call_fndecl (new_stmt)))
 607     {
 608       /* Constant propagation (and possibly also inlining?) can turn an
 609          indirect call into a direct one.  */
 610       struct cgraph_node *new_callee = cgraph_get_node (decl);
 611
 612       gcc_checking_assert (new_callee);
 613       cgraph_make_edge_direct (e, new_callee);
 614     }
 615
 616   push_cfun (DECL_STRUCT_FUNCTION (e->caller->symbol.decl));
 617   e->can_throw_external = stmt_can_throw_external (new_stmt);
 618   pop_cfun ();
 619   if (e->caller->call_site_hash)
 620     cgraph_add_edge_to_call_site_hash (e);
 621 }
 622
 623 /* Allocate a cgraph_edge structure and fill it with data according to the
 624    parameters of which only CALLEE can be NULL (when creating an indirect call
 625    edge).  */
 626
 627 static struct cgraph_edge *
 628 cgraph_create_edge_1 (struct cgraph_node *caller, struct cgraph_node *callee,
 629                        gimple call_stmt, gcov_type count, int freq)
 630 {
 631   struct cgraph_edge *edge;
 632
 633   /* LTO does not actually have access to the call_stmt since these
 634      have not been loaded yet.  */
 635   if (call_stmt)
 636     {
 637       /* This is a rather expensive check possibly triggering
 638          construction of call stmt hashtable.  */
 639       gcc_checking_assert (!cgraph_edge (caller, call_stmt));
 640
 641       gcc_assert (is_gimple_call (call_stmt));
 642     }
 643
 644   if (free_edges)
 645     {
 646       edge = free_edges;
 647       free_edges = NEXT_FREE_EDGE (edge);
 648     }
 649   else
 650     {
 651       edge = ggc_alloc_cgraph_edge ();
 652       edge->uid = cgraph_edge_max_uid++;
 653     }
 654
 655   edge->aux = NULL;
 656   edge->caller = caller;
 657   edge->callee = callee;
 658   edge->prev_caller = NULL;
 659   edge->next_caller = NULL;
 660   edge->prev_callee = NULL;
 661   edge->next_callee = NULL;
 662
 663   edge->count = count;
 664   gcc_assert (count >= 0);
 665   edge->frequency = freq;
 666   gcc_assert (freq >= 0);
 667   gcc_assert (freq <= CGRAPH_FREQ_MAX);
 668
 669   edge->call_stmt = call_stmt;
 670   push_cfun (DECL_STRUCT_FUNCTION (caller->symbol.decl));
 671   edge->can_throw_external
 672     = call_stmt ? stmt_can_throw_external (call_stmt) : false;
 673   pop_cfun ();
 674   if (call_stmt
 675       && callee && callee->symbol.decl
 676       && !gimple_check_call_matching_types (call_stmt, callee->symbol.decl))
 677     edge->call_stmt_cannot_inline_p = true;
 678   else
 679     edge->call_stmt_cannot_inline_p = false;
 680   if (call_stmt && caller->call_site_hash)
 681     cgraph_add_edge_to_call_site_hash (edge);
 682
 683   edge->indirect_info = NULL;
 684   edge->indirect_inlining_edge = 0;
 685
 686   return edge;
 687 }
 688
 689 /* Create edge from CALLER to CALLEE in the cgraph.  */
 690
 691 struct cgraph_edge *
 692 cgraph_create_edge (struct cgraph_node *caller, struct cgraph_node *callee,
 693                     gimple call_stmt, gcov_type count, int freq)
 694 {
 695   struct cgraph_edge *edge = cgraph_create_edge_1 (caller, callee, call_stmt,
 696                                                    count, freq);
 697
 698   edge->indirect_unknown_callee = 0;
 699   initialize_inline_failed (edge);
 700
 701   edge->next_caller = callee->callers;
 702   if (callee->callers)
 703     callee->callers->prev_caller = edge;
 704   edge->next_callee = caller->callees;
 705   if (caller->callees)
 706     caller->callees->prev_callee = edge;
 707   caller->callees = edge;
 708   callee->callers = edge;
 709
 710   return edge;
 711 }
 712
 713 /* Allocate cgraph_indirect_call_info and set its fields to default values. */
 714
 715 struct cgraph_indirect_call_info *
 716 cgraph_allocate_init_indirect_info (void)
 717 {
 718   struct cgraph_indirect_call_info *ii;
 719
 720   ii = ggc_alloc_cleared_cgraph_indirect_call_info ();
 721   ii->param_index = -1;
 722   return ii;
 723 }
 724
 725 /* Create an indirect edge with a yet-undetermined callee where the call
 726    statement destination is a formal parameter of the caller with index
 727    PARAM_INDEX. */
 728
 729 struct cgraph_edge *
 730 cgraph_create_indirect_edge (struct cgraph_node *caller, gimple call_stmt,
 731                              int ecf_flags,
 732                              gcov_type count, int freq)
 733 {
 734   struct cgraph_edge *edge = cgraph_create_edge_1 (caller, NULL, call_stmt,
 735                                                    count, freq);
 736
 737   edge->indirect_unknown_callee = 1;
 738   initialize_inline_failed (edge);
 739
 740   edge->indirect_info = cgraph_allocate_init_indirect_info ();
 741   edge->indirect_info->ecf_flags = ecf_flags;
 742
 743   edge->next_callee = caller->indirect_calls;
 744   if (caller->indirect_calls)
 745     caller->indirect_calls->prev_callee = edge;
 746   caller->indirect_calls = edge;
 747
 748   return edge;
 749 }
 750
 751 /* Remove the edge E from the list of the callers of the callee.  */
 752
 753 static inline void
 754 cgraph_edge_remove_callee (struct cgraph_edge *e)
 755 {
 756   gcc_assert (!e->indirect_unknown_callee);
 757   if (e->prev_caller)
 758     e->prev_caller->next_caller = e->next_caller;
 759   if (e->next_caller)
 760     e->next_caller->prev_caller = e->prev_caller;
 761   if (!e->prev_caller)
 762     e->callee->callers = e->next_caller;
 763 }
 764
 765 /* Remove the edge E from the list of the callees of the caller.  */
 766
 767 static inline void
 768 cgraph_edge_remove_caller (struct cgraph_edge *e)
 769 {
 770   if (e->prev_callee)
 771     e->prev_callee->next_callee = e->next_callee;
 772   if (e->next_callee)
 773     e->next_callee->prev_callee = e->prev_callee;
 774   if (!e->prev_callee)
 775     {
 776       if (e->indirect_unknown_callee)
 777         e->caller->indirect_calls = e->next_callee;
 778       else
 779         e->caller->callees = e->next_callee;
 780     }
 781   if (e->caller->call_site_hash)
 782     htab_remove_elt_with_hash (e->caller->call_site_hash,
 783                                e->call_stmt,
 784                                htab_hash_pointer (e->call_stmt));
 785 }
 786
 787 /* Put the edge onto the free list.  */
 788
 789 static void
 790 cgraph_free_edge (struct cgraph_edge *e)
 791 {
 792   int uid = e->uid;
 793
 794   /* Clear out the edge so we do not dangle pointers.  */
 795   memset (e, 0, sizeof (*e));
 796   e->uid = uid;
 797   NEXT_FREE_EDGE (e) = free_edges;
 798   free_edges = e;
 799 }
 800
 801 /* Remove the edge E in the cgraph.  */
 802
 803 void
 804 cgraph_remove_edge (struct cgraph_edge *e)
 805 {
 806   /* Call all edge removal hooks.  */
 807   cgraph_call_edge_removal_hooks (e);
 808
 809   if (!e->indirect_unknown_callee)
 810     /* Remove from callers list of the callee.  */
 811     cgraph_edge_remove_callee (e);
 812
 813   /* Remove from callees list of the callers.  */
 814   cgraph_edge_remove_caller (e);
 815
 816   /* Put the edge onto the free list.  */
 817   cgraph_free_edge (e);
 818 }
 819
 820 /* Set callee of call graph edge E and add it to the corresponding set of
 821    callers. */
 822
 823 static void
 824 cgraph_set_edge_callee (struct cgraph_edge *e, struct cgraph_node *n)
 825 {
 826   e->prev_caller = NULL;
 827   if (n->callers)
 828     n->callers->prev_caller = e;
 829   e->next_caller = n->callers;
 830   n->callers = e;
 831   e->callee = n;
 832 }
 833
 834 /* Redirect callee of E to N.  The function does not update underlying
 835    call expression.  */
 836
 837 void
 838 cgraph_redirect_edge_callee (struct cgraph_edge *e, struct cgraph_node *n)
 839 {
 840   /* Remove from callers list of the current callee.  */
 841   cgraph_edge_remove_callee (e);
 842
 843   /* Insert to callers list of the new callee.  */
 844   cgraph_set_edge_callee (e, n);
 845 }
 846
 847 /* Make an indirect EDGE with an unknown callee an ordinary edge leading to
 848    CALLEE.  DELTA is an integer constant that is to be added to the this
 849    pointer (first parameter) to compensate for skipping a thunk adjustment.  */
 850
 851 void
 852 cgraph_make_edge_direct (struct cgraph_edge *edge, struct cgraph_node *callee)
 853 {
 854   edge->indirect_unknown_callee = 0;
 855
 856   /* Get the edge out of the indirect edge list. */
 857   if (edge->prev_callee)
 858     edge->prev_callee->next_callee = edge->next_callee;
 859   if (edge->next_callee)
 860     edge->next_callee->prev_callee = edge->prev_callee;
 861   if (!edge->prev_callee)
 862     edge->caller->indirect_calls = edge->next_callee;
 863
 864   /* Put it into the normal callee list */
 865   edge->prev_callee = NULL;
 866   edge->next_callee = edge->caller->callees;
 867   if (edge->caller->callees)
 868     edge->caller->callees->prev_callee = edge;
 869   edge->caller->callees = edge;
 870
 871   /* Insert to callers list of the new callee.  */
 872   cgraph_set_edge_callee (edge, callee);
 873
 874   if (edge->call_stmt)
 875     edge->call_stmt_cannot_inline_p
 876       = !gimple_check_call_matching_types (edge->call_stmt, callee->symbol.decl);
 877
 878   /* We need to re-determine the inlining status of the edge.  */
 879   initialize_inline_failed (edge);
 880 }
 881
 882 /* If necessary, change the function declaration in the call statement
 883    associated with E so that it corresponds to the edge callee.  */
 884
 885 gimple
 886 cgraph_redirect_edge_call_stmt_to_callee (struct cgraph_edge *e)
 887 {
 888   tree decl = gimple_call_fndecl (e->call_stmt);
 889   gimple new_stmt;
 890   gimple_stmt_iterator gsi;
 891 #ifdef ENABLE_CHECKING
 892   struct cgraph_node *node;
 893 #endif
 894
 895   if (e->indirect_unknown_callee
 896       || decl == e->callee->symbol.decl)
 897     return e->call_stmt;
 898
 899 #ifdef ENABLE_CHECKING
 900   if (decl)
 901     {
 902       node = cgraph_get_node (decl);
 903       gcc_assert (!node || !node->clone.combined_args_to_skip);
 904     }
 905 #endif
 906
 907   if (cgraph_dump_file)
 908     {
 909       fprintf (cgraph_dump_file, "updating call of %s/%i -> %s/%i: ",
 910                xstrdup (cgraph_node_name (e->caller)), e->caller->uid,
 911                xstrdup (cgraph_node_name (e->callee)), e->callee->uid);
 912       print_gimple_stmt (cgraph_dump_file, e->call_stmt, 0, dump_flags);
 913       if (e->callee->clone.combined_args_to_skip)
 914         {
 915           fprintf (cgraph_dump_file, " combined args to skip: ");
 916           dump_bitmap (cgraph_dump_file,
 917                        e->callee->clone.combined_args_to_skip);
 918         }
 919     }
 920
 921   if (e->callee->clone.combined_args_to_skip)
 922     {
 923       int lp_nr;
 924
 925       new_stmt
 926         = gimple_call_copy_skip_args (e->call_stmt,
 927                                       e->callee->clone.combined_args_to_skip);
 928       gimple_call_set_fndecl (new_stmt, e->callee->symbol.decl);
 929
 930       if (gimple_vdef (new_stmt)
 931           && TREE_CODE (gimple_vdef (new_stmt)) == SSA_NAME)
 932         SSA_NAME_DEF_STMT (gimple_vdef (new_stmt)) = new_stmt;
 933
 934       gsi = gsi_for_stmt (e->call_stmt);
 935       gsi_replace (&gsi, new_stmt, false);
 936       /* We need to defer cleaning EH info on the new statement to
 937          fixup-cfg.  We may not have dominator information at this point
 938          and thus would end up with unreachable blocks and have no way
 939          to communicate that we need to run CFG cleanup then.  */
 940       lp_nr = lookup_stmt_eh_lp (e->call_stmt);
 941       if (lp_nr != 0)
 942         {
 943           remove_stmt_from_eh_lp (e->call_stmt);
 944           add_stmt_to_eh_lp (new_stmt, lp_nr);
 945         }
 946     }
 947   else
 948     {
 949       new_stmt = e->call_stmt;
 950       gimple_call_set_fndecl (new_stmt, e->callee->symbol.decl);
 951       update_stmt (new_stmt);
 952     }
 953
 954   cgraph_set_call_stmt_including_clones (e->caller, e->call_stmt, new_stmt);
 955
 956   if (cgraph_dump_file)
 957     {
 958       fprintf (cgraph_dump_file, "  updated to:");
 959       print_gimple_stmt (cgraph_dump_file, e->call_stmt, 0, dump_flags);
 960     }
 961   return new_stmt;
 962 }
 963
 964 /* Update or remove the corresponding cgraph edge if a GIMPLE_CALL
 965    OLD_STMT changed into NEW_STMT.  OLD_CALL is gimple_call_fndecl
 966    of OLD_STMT if it was previously call statement.
 967    If NEW_STMT is NULL, the call has been dropped without any
 968    replacement.  */
 969
 970 static void
 971 cgraph_update_edges_for_call_stmt_node (struct cgraph_node *node,
 972                                         gimple old_stmt, tree old_call,
 973                                         gimple new_stmt)
 974 {
 975   tree new_call = (new_stmt && is_gimple_call (new_stmt))
 976                   ? gimple_call_fndecl (new_stmt) : 0;
 977
 978   /* We are seeing indirect calls, then there is nothing to update.  */
 979   if (!new_call && !old_call)
 980     return;
 981   /* See if we turned indirect call into direct call or folded call to one builtin
 982      into different builtin.  */
 983   if (old_call != new_call)
 984     {
 985       struct cgraph_edge *e = cgraph_edge (node, old_stmt);
 986       struct cgraph_edge *ne = NULL;
 987       gcov_type count;
 988       int frequency;
 989
 990       if (e)
 991         {
 992           /* See if the edge is already there and has the correct callee.  It
 993              might be so because of indirect inlining has already updated
 994              it.  We also might've cloned and redirected the edge.  */
 995           if (new_call && e->callee)
 996             {
 997               struct cgraph_node *callee = e->callee;
 998               while (callee)
 999                 {
1000                   if (callee->symbol.decl == new_call
1001                       || callee->former_clone_of == new_call)
1002                     return;
1003                   callee = callee->clone_of;
1004                 }
1005             }
1006
1007           /* Otherwise remove edge and create new one; we can't simply redirect
1008              since function has changed, so inline plan and other information
1009              attached to edge is invalid.  */
1010           count = e->count;
1011           frequency = e->frequency;
1012           cgraph_remove_edge (e);
1013         }
1014       else if (new_call)
1015         {
1016           /* We are seeing new direct call; compute profile info based on BB.  */
1017           basic_block bb = gimple_bb (new_stmt);
1018           count = bb->count;
1019           frequency = compute_call_stmt_bb_frequency (current_function_decl,
1020                                                       bb);
1021         }
1022
1023       if (new_call)
1024         {
1025           ne = cgraph_create_edge (node, cgraph_get_create_node (new_call),
1026                                    new_stmt, count, frequency);
1027           gcc_assert (ne->inline_failed);
1028         }
1029     }
1030   /* We only updated the call stmt; update pointer in cgraph edge..  */
1031   else if (old_stmt != new_stmt)
1032     cgraph_set_call_stmt (cgraph_edge (node, old_stmt), new_stmt);
1033 }
1034
1035 /* Update or remove the corresponding cgraph edge if a GIMPLE_CALL
1036    OLD_STMT changed into NEW_STMT.  OLD_DECL is gimple_call_fndecl
1037    of OLD_STMT before it was updated (updating can happen inplace).  */
1038
1039 void
1040 cgraph_update_edges_for_call_stmt (gimple old_stmt, tree old_decl, gimple new_stmt)
1041 {
1042   struct cgraph_node *orig = cgraph_get_node (cfun->decl);
1043   struct cgraph_node *node;
1044
1045   gcc_checking_assert (orig);
1046   cgraph_update_edges_for_call_stmt_node (orig, old_stmt, old_decl, new_stmt);
1047   if (orig->clones)
1048     for (node = orig->clones; node != orig;)
1049       {
1050         cgraph_update_edges_for_call_stmt_node (node, old_stmt, old_decl, new_stmt);
1051         if (node->clones)
1052           node = node->clones;
1053         else if (node->next_sibling_clone)
1054           node = node->next_sibling_clone;
1055         else
1056           {
1057             while (node != orig && !node->next_sibling_clone)
1058               node = node->clone_of;
1059             if (node != orig)
1060               node = node->next_sibling_clone;
1061           }
1062       }
1063 }
1064
1065
1066 /* Remove all callees from the node.  */
1067
1068 void
1069 cgraph_node_remove_callees (struct cgraph_node *node)
1070 {
1071   struct cgraph_edge *e, *f;
1072
1073   /* It is sufficient to remove the edges from the lists of callers of
1074      the callees.  The callee list of the node can be zapped with one
1075      assignment.  */
1076   for (e = node->callees; e; e = f)
1077     {
1078       f = e->next_callee;
1079       cgraph_call_edge_removal_hooks (e);
1080       if (!e->indirect_unknown_callee)
1081         cgraph_edge_remove_callee (e);
1082       cgraph_free_edge (e);
1083     }
1084   for (e = node->indirect_calls; e; e = f)
1085     {
1086       f = e->next_callee;
1087       cgraph_call_edge_removal_hooks (e);
1088       if (!e->indirect_unknown_callee)
1089         cgraph_edge_remove_callee (e);
1090       cgraph_free_edge (e);
1091     }
1092   node->indirect_calls = NULL;
1093   node->callees = NULL;
1094   if (node->call_site_hash)
1095     {
1096       htab_delete (node->call_site_hash);
1097       node->call_site_hash = NULL;
1098     }
1099 }
1100
1101 /* Remove all callers from the node.  */
1102
1103 static void
1104 cgraph_node_remove_callers (struct cgraph_node *node)
1105 {
1106   struct cgraph_edge *e, *f;
1107
1108   /* It is sufficient to remove the edges from the lists of callees of
1109      the callers.  The caller list of the node can be zapped with one
1110      assignment.  */
1111   for (e = node->callers; e; e = f)
1112     {
1113       f = e->next_caller;
1114       cgraph_call_edge_removal_hooks (e);
1115       cgraph_edge_remove_caller (e);
1116       cgraph_free_edge (e);
1117     }
1118   node->callers = NULL;
1119 }
1120
1121 /* Release memory used to represent body of function NODE.  */
1122
1123 void
1124 cgraph_release_function_body (struct cgraph_node *node)
1125 {
1126   if (DECL_STRUCT_FUNCTION (node->symbol.decl))
1127     {
1128       tree old_decl = current_function_decl;
1129       push_cfun (DECL_STRUCT_FUNCTION (node->symbol.decl));
1130       if (cfun->cfg
1131           && current_loops)
1132         {
1133           cfun->curr_properties &= ~PROP_loops;
1134           loop_optimizer_finalize ();
1135         }
1136       if (cfun->gimple_df)
1137         {
1138           current_function_decl = node->symbol.decl;
1139           delete_tree_ssa ();
1140           delete_tree_cfg_annotations ();
1141           cfun->eh = NULL;
1142           current_function_decl = old_decl;
1143         }
1144       if (cfun->cfg)
1145         {
1146           gcc_assert (dom_computed[0] == DOM_NONE);
1147           gcc_assert (dom_computed[1] == DOM_NONE);
1148           clear_edges ();
1149         }
1150       if (cfun->value_histograms)
1151         free_histograms ();
1152       pop_cfun();
1153       gimple_set_body (node->symbol.decl, NULL);
1154       VEC_free (ipa_opt_pass, heap,
1155                 node->ipa_transforms_to_apply);
1156       /* Struct function hangs a lot of data that would leak if we didn't
1157          removed all pointers to it.   */
1158       ggc_free (DECL_STRUCT_FUNCTION (node->symbol.decl));
1159       DECL_STRUCT_FUNCTION (node->symbol.decl) = NULL;
1160     }
1161   DECL_SAVED_TREE (node->symbol.decl) = NULL;
1162   /* If the node is abstract and needed, then do not clear DECL_INITIAL
1163      of its associated function function declaration because it's
1164      needed to emit debug info later.  */
1165   if (!node->abstract_and_needed && DECL_INITIAL (node->symbol.decl))
1166     DECL_INITIAL (node->symbol.decl) = error_mark_node;
1167 }
1168
1169 /* Remove the node from cgraph.  */
1170
1171 void
1172 cgraph_remove_node (struct cgraph_node *node)
1173 {
1174   struct cgraph_node *n;
1175   int uid = node->uid;
1176
1177   cgraph_call_node_removal_hooks (node);
1178   cgraph_node_remove_callers (node);
1179   cgraph_node_remove_callees (node);
1180   VEC_free (ipa_opt_pass, heap,
1181             node->ipa_transforms_to_apply);
1182
1183   /* Incremental inlining access removed nodes stored in the postorder list.
1184      */
1185   node->symbol.force_output = false;
1186   for (n = node->nested; n; n = n->next_nested)
1187     n->origin = NULL;
1188   node->nested = NULL;
1189   if (node->origin)
1190     {
1191       struct cgraph_node **node2 = &node->origin->nested;
1192
1193       while (*node2 != node)
1194         node2 = &(*node2)->next_nested;
1195       *node2 = node->next_nested;
1196     }
1197   symtab_unregister_node ((symtab_node)node);
1198   if (node->prev_sibling_clone)
1199     node->prev_sibling_clone->next_sibling_clone = node->next_sibling_clone;
1200   else if (node->clone_of)
1201     node->clone_of->clones = node->next_sibling_clone;
1202   if (node->next_sibling_clone)
1203     node->next_sibling_clone->prev_sibling_clone = node->prev_sibling_clone;
1204   if (node->clones)
1205     {
1206       struct cgraph_node *n, *next;
1207
1208       if (node->clone_of)
1209         {
1210           for (n = node->clones; n->next_sibling_clone; n = n->next_sibling_clone)
1211             n->clone_of = node->clone_of;
1212           n->clone_of = node->clone_of;
1213           n->next_sibling_clone = node->clone_of->clones;
1214           if (node->clone_of->clones)
1215             node->clone_of->clones->prev_sibling_clone = n;
1216           node->clone_of->clones = node->clones;
1217         }
1218       else
1219         {
1220           /* We are removing node with clones.  This makes clones inconsistent,
1221              but assume they will be removed subsequently and just keep clone
1222              tree intact.  This can happen in unreachable function removal since
1223              we remove unreachable functions in random order, not by bottom-up
1224              walk of clone trees.  */
1225           for (n = node->clones; n; n = next)
1226             {
1227                next = n->next_sibling_clone;
1228                n->next_sibling_clone = NULL;
1229                n->prev_sibling_clone = NULL;
1230                n->clone_of = NULL;
1231             }
1232         }
1233     }
1234
1235   /* While all the clones are removed after being proceeded, the function
1236      itself is kept in the cgraph even after it is compiled.  Check whether
1237      we are done with this body and reclaim it proactively if this is the case.
1238      */
1239   n = cgraph_get_node (node->symbol.decl);
1240   if (!n
1241       || (!n->clones && !n->clone_of && !n->global.inlined_to
1242           && (cgraph_global_info_ready
1243               && (TREE_ASM_WRITTEN (n->symbol.decl)
1244                   || DECL_EXTERNAL (n->symbol.decl)
1245                   || !n->analyzed
1246                   || n->symbol.in_other_partition))))
1247     cgraph_release_function_body (node);
1248
1249   node->symbol.decl = NULL;
1250   if (node->call_site_hash)
1251     {
1252       htab_delete (node->call_site_hash);
1253       node->call_site_hash = NULL;
1254     }
1255   cgraph_n_nodes--;
1256
1257   /* Clear out the node to NULL all pointers and add the node to the free
1258      list.  */
1259   memset (node, 0, sizeof(*node));
1260   node->symbol.type = SYMTAB_FUNCTION;
1261   node->uid = uid;
1262   SET_NEXT_FREE_NODE (node, free_nodes);
1263   free_nodes = node;
1264 }
1265
1266 /* Likewise indicate that a node is having address taken.  */
1267
1268 void
1269 cgraph_mark_address_taken_node (struct cgraph_node *node)
1270 {
1271   gcc_assert (!node->global.inlined_to);
1272   /* FIXME: address_taken flag is used both as a shortcut for testing whether
1273      IPA_REF_ADDR reference exists (and thus it should be set on node
1274      representing alias we take address of) and as a test whether address
1275      of the object was taken (and thus it should be set on node alias is
1276      referring to).  We should remove the first use and the remove the
1277      following set.  */
1278   node->symbol.address_taken = 1;
1279   node = cgraph_function_or_thunk_node (node, NULL);
1280   node->symbol.address_taken = 1;
1281 }
1282
1283 /* Return local info for the compiled function.  */
1284
1285 struct cgraph_local_info *
1286 cgraph_local_info (tree decl)
1287 {
1288   struct cgraph_node *node;
1289
1290   gcc_assert (TREE_CODE (decl) == FUNCTION_DECL);
1291   node = cgraph_get_node (decl);
1292   if (!node)
1293     return NULL;
1294   return &node->local;
1295 }
1296
1297 /* Return local info for the compiled function.  */
1298
1299 struct cgraph_global_info *
1300 cgraph_global_info (tree decl)
1301 {
1302   struct cgraph_node *node;
1303
1304   gcc_assert (TREE_CODE (decl) == FUNCTION_DECL && cgraph_global_info_ready);
1305   node = cgraph_get_node (decl);
1306   if (!node)
1307     return NULL;
1308   return &node->global;
1309 }
1310
1311 /* Return local info for the compiled function.  */
1312
1313 struct cgraph_rtl_info *
1314 cgraph_rtl_info (tree decl)
1315 {
1316   struct cgraph_node *node;
1317
1318   gcc_assert (TREE_CODE (decl) == FUNCTION_DECL);
1319   node = cgraph_get_node (decl);
1320   if (!node
1321       || (decl != current_function_decl
1322           && !TREE_ASM_WRITTEN (node->symbol.decl)))
1323     return NULL;
1324   return &node->rtl;
1325 }
1326
1327 /* Return a string describing the failure REASON.  */
1328
1329 const char*
1330 cgraph_inline_failed_string (cgraph_inline_failed_t reason)
1331 {
1332 #undef DEFCIFCODE
1333 #define DEFCIFCODE(code, string)        string,
1334
1335   static const char *cif_string_table[CIF_N_REASONS] = {
1336 #include "cif-code.def"
1337   };
1338
1339   /* Signedness of an enum type is implementation defined, so cast it
1340      to unsigned before testing. */
1341   gcc_assert ((unsigned) reason < CIF_N_REASONS);
1342   return cif_string_table[reason];
1343 }
1344
1345 /* Names used to print out the availability enum.  */
1346 const char * const cgraph_availability_names[] =
1347   {"unset", "not_available", "overwritable", "available", "local"};
1348
1349
1350 /* Dump call graph node NODE to file F.  */
1351
1352 void
1353 dump_cgraph_node (FILE *f, struct cgraph_node *node)
1354 {
1355   struct cgraph_edge *edge;
1356   int indirect_calls_count = 0;
1357
1358   dump_symtab_base (f, (symtab_node) node);
1359
1360   if (node->global.inlined_to)
1361     fprintf (f, "  Function %s/%i is inline copy in %s/%i\n",
1362              xstrdup (cgraph_node_name (node)),
1363              node->symbol.order,
1364              xstrdup (cgraph_node_name (node->global.inlined_to)),
1365              node->global.inlined_to->symbol.order);
1366   if (node->clone_of)
1367     fprintf (f, "  Clone of %s/%i\n",
1368              cgraph_node_asm_name (node->clone_of),
1369              node->clone_of->symbol.order);
1370   if (cgraph_function_flags_ready)
1371     fprintf (f, "  Availability: %s\n",
1372              cgraph_availability_names [cgraph_function_body_availability (node)]);
1373
1374   fprintf (f, "  Function flags:");
1375   if (node->analyzed)
1376     fprintf (f, " analyzed");
1377   if (node->count)
1378     fprintf (f, " executed "HOST_WIDEST_INT_PRINT_DEC"x",
1379              (HOST_WIDEST_INT)node->count);
1380   if (node->origin)
1381     fprintf (f, " nested in: %s", cgraph_node_asm_name (node->origin));
1382   if (gimple_has_body_p (node->symbol.decl))
1383     fprintf (f, " body");
1384   if (node->process)
1385     fprintf (f, " process");
1386   if (node->local.local)
1387     fprintf (f, " local");
1388   if (node->local.finalized)
1389     fprintf (f, " finalized");
1390   if (node->local.redefined_extern_inline)
1391     fprintf (f, " redefined_extern_inline");
1392   if (node->only_called_at_startup)
1393     fprintf (f, " only_called_at_startup");
1394   if (node->only_called_at_exit)
1395     fprintf (f, " only_called_at_exit");
1396   else if (node->alias)
1397     fprintf (f, " alias");
1398   if (node->tm_clone)
1399     fprintf (f, " tm_clone");
1400
1401   fprintf (f, "\n");
1402
1403   if (node->thunk.thunk_p)
1404     {
1405       fprintf (f, "  Thunk of %s (asm: %s) fixed offset %i virtual value %i has "
1406                "virtual offset %i)\n",
1407                lang_hooks.decl_printable_name (node->thunk.alias, 2),
1408                IDENTIFIER_POINTER (DECL_ASSEMBLER_NAME (node->thunk.alias)),
1409                (int)node->thunk.fixed_offset,
1410                (int)node->thunk.virtual_value,
1411                (int)node->thunk.virtual_offset_p);
1412     }
1413   if (node->alias && node->thunk.alias)
1414     {
1415       fprintf (f, "  Alias of %s",
1416                lang_hooks.decl_printable_name (node->thunk.alias, 2));
1417       if (DECL_ASSEMBLER_NAME_SET_P (node->thunk.alias))
1418         fprintf (f, " (asm: %s)",
1419                  IDENTIFIER_POINTER (DECL_ASSEMBLER_NAME (node->thunk.alias)));
1420       fprintf (f, "\n");
1421     }
1422
1423   fprintf (f, "  Called by: ");
1424
1425   for (edge = node->callers; edge; edge = edge->next_caller)
1426     {
1427       fprintf (f, "%s/%i ", cgraph_node_asm_name (edge->caller),
1428                edge->caller->symbol.order);
1429       if (edge->count)
1430         fprintf (f, "("HOST_WIDEST_INT_PRINT_DEC"x) ",
1431                  (HOST_WIDEST_INT)edge->count);
1432       if (edge->frequency)
1433         fprintf (f, "(%.2f per call) ",
1434                  edge->frequency / (double)CGRAPH_FREQ_BASE);
1435       if (!edge->inline_failed)
1436         fprintf(f, "(inlined) ");
1437       if (edge->indirect_inlining_edge)
1438         fprintf(f, "(indirect_inlining) ");
1439       if (edge->can_throw_external)
1440         fprintf(f, "(can throw external) ");
1441     }
1442
1443   fprintf (f, "\n  Calls: ");
1444   for (edge = node->callees; edge; edge = edge->next_callee)
1445     {
1446       fprintf (f, "%s/%i ", cgraph_node_asm_name (edge->callee),
1447                edge->callee->symbol.order);
1448       if (!edge->inline_failed)
1449         fprintf(f, "(inlined) ");
1450       if (edge->indirect_inlining_edge)
1451         fprintf(f, "(indirect_inlining) ");
1452       if (edge->count)
1453         fprintf (f, "("HOST_WIDEST_INT_PRINT_DEC"x) ",
1454                  (HOST_WIDEST_INT)edge->count);
1455       if (edge->frequency)
1456         fprintf (f, "(%.2f per call) ",
1457                  edge->frequency / (double)CGRAPH_FREQ_BASE);
1458       if (edge->can_throw_external)
1459         fprintf(f, "(can throw external) ");
1460     }
1461   fprintf (f, "\n");
1462
1463   for (edge = node->indirect_calls; edge; edge = edge->next_callee)
1464     indirect_calls_count++;
1465   if (indirect_calls_count)
1466     fprintf (f, "  Has %i outgoing edges for indirect calls.\n",
1467              indirect_calls_count);
1468 }
1469
1470
1471 /* Dump call graph node NODE to stderr.  */
1472
1473 DEBUG_FUNCTION void
1474 debug_cgraph_node (struct cgraph_node *node)
1475 {
1476   dump_cgraph_node (stderr, node);
1477 }
1478
1479
1480 /* Dump the callgraph to file F.  */
1481
1482 void
1483 dump_cgraph (FILE *f)
1484 {
1485   struct cgraph_node *node;
1486
1487   fprintf (f, "callgraph:\n\n");
1488   FOR_EACH_FUNCTION (node)
1489     dump_cgraph_node (f, node);
1490 }
1491
1492
1493 /* Dump the call graph to stderr.  */
1494
1495 DEBUG_FUNCTION void
1496 debug_cgraph (void)
1497 {
1498   dump_cgraph (stderr);
1499 }
1500
1501 /* Return true when the DECL can possibly be inlined.  */
1502 bool
1503 cgraph_function_possibly_inlined_p (tree decl)
1504 {
1505   if (!cgraph_global_info_ready)
1506     return !DECL_UNINLINABLE (decl);
1507   return DECL_POSSIBLY_INLINED (decl);
1508 }
1509
1510 /* NODE is no longer nested function; update cgraph accordingly.  */
1511 void
1512 cgraph_unnest_node (struct cgraph_node *node)
1513 {
1514   struct cgraph_node **node2 = &node->origin->nested;
1515   gcc_assert (node->origin);
1516
1517   while (*node2 != node)
1518     node2 = &(*node2)->next_nested;
1519   *node2 = node->next_nested;
1520   node->origin = NULL;
1521 }
1522
1523 /* Return function availability.  See cgraph.h for description of individual
1524    return values.  */
1525 enum availability
1526 cgraph_function_body_availability (struct cgraph_node *node)
1527 {
1528   enum availability avail;
1529   gcc_assert (cgraph_function_flags_ready);
1530   if (!node->analyzed)
1531     avail = AVAIL_NOT_AVAILABLE;
1532   else if (node->local.local)
1533     avail = AVAIL_LOCAL;
1534   else if (!node->symbol.externally_visible)
1535     avail = AVAIL_AVAILABLE;
1536   /* Inline functions are safe to be analyzed even if their symbol can
1537      be overwritten at runtime.  It is not meaningful to enforce any sane
1538      behaviour on replacing inline function by different body.  */
1539   else if (DECL_DECLARED_INLINE_P (node->symbol.decl))
1540     avail = AVAIL_AVAILABLE;
1541
1542   /* If the function can be overwritten, return OVERWRITABLE.  Take
1543      care at least of two notable extensions - the COMDAT functions
1544      used to share template instantiations in C++ (this is symmetric
1545      to code cp_cannot_inline_tree_fn and probably shall be shared and
1546      the inlinability hooks completely eliminated).
1547
1548      ??? Does the C++ one definition rule allow us to always return
1549      AVAIL_AVAILABLE here?  That would be good reason to preserve this
1550      bit.  */
1551
1552   else if (decl_replaceable_p (node->symbol.decl)
1553            && !DECL_EXTERNAL (node->symbol.decl))
1554     avail = AVAIL_OVERWRITABLE;
1555   else avail = AVAIL_AVAILABLE;
1556
1557   return avail;
1558 }
1559
1560 /* Worker for cgraph_node_can_be_local_p.  */
1561 static bool
1562 cgraph_node_cannot_be_local_p_1 (struct cgraph_node *node,
1563                                  void *data ATTRIBUTE_UNUSED)
1564 {
1565   return !(!node->symbol.force_output
1566            && ((DECL_COMDAT (node->symbol.decl)
1567                 && !node->symbol.same_comdat_group)
1568                || !node->symbol.externally_visible));
1569 }
1570
1571 /* Return true if NODE can be made local for API change.
1572    Extern inline functions and C++ COMDAT functions can be made local
1573    at the expense of possible code size growth if function is used in multiple
1574    compilation units.  */
1575 bool
1576 cgraph_node_can_be_local_p (struct cgraph_node *node)
1577 {
1578   return (!node->symbol.address_taken
1579           && !cgraph_for_node_and_aliases (node,
1580                                            cgraph_node_cannot_be_local_p_1,
1581                                            NULL, true));
1582 }
1583
1584 /* Call calback on NODE, thunks and aliases asociated to NODE.
1585    When INCLUDE_OVERWRITABLE is false, overwritable aliases and thunks are
1586    skipped. */
1587
1588 bool
1589 cgraph_for_node_thunks_and_aliases (struct cgraph_node *node,
1590                                     bool (*callback) (struct cgraph_node *, void *),
1591                                     void *data,
1592                                     bool include_overwritable)
1593 {
1594   struct cgraph_edge *e;
1595   int i;
1596   struct ipa_ref *ref;
1597
1598   if (callback (node, data))
1599     return true;
1600   for (e = node->callers; e; e = e->next_caller)
1601     if (e->caller->thunk.thunk_p
1602         && (include_overwritable
1603             || cgraph_function_body_availability (e->caller) > AVAIL_OVERWRITABLE))
1604       if (cgraph_for_node_thunks_and_aliases (e->caller, callback, data,
1605                                               include_overwritable))
1606         return true;
1607   for (i = 0; ipa_ref_list_referring_iterate (&node->symbol.ref_list, i, ref); i++)
1608     if (ref->use == IPA_REF_ALIAS)
1609       {
1610         struct cgraph_node *alias = ipa_ref_referring_node (ref);
1611         if (include_overwritable
1612             || cgraph_function_body_availability (alias) > AVAIL_OVERWRITABLE)
1613           if (cgraph_for_node_thunks_and_aliases (alias, callback, data,
1614                                                   include_overwritable))
1615             return true;
1616       }
1617   return false;
1618 }
1619
1620 /* Call calback on NODE and aliases asociated to NODE.
1621    When INCLUDE_OVERWRITABLE is false, overwritable aliases and thunks are
1622    skipped. */
1623
1624 bool
1625 cgraph_for_node_and_aliases (struct cgraph_node *node,
1626                              bool (*callback) (struct cgraph_node *, void *),
1627                              void *data,
1628                              bool include_overwritable)
1629 {
1630   int i;
1631   struct ipa_ref *ref;
1632
1633   if (callback (node, data))
1634     return true;
1635   for (i = 0; ipa_ref_list_referring_iterate (&node->symbol.ref_list, i, ref); i++)
1636     if (ref->use == IPA_REF_ALIAS)
1637       {
1638         struct cgraph_node *alias = ipa_ref_referring_node (ref);
1639         if (include_overwritable
1640             || cgraph_function_body_availability (alias) > AVAIL_OVERWRITABLE)
1641           if (cgraph_for_node_and_aliases (alias, callback, data,
1642                                            include_overwritable))
1643             return true;
1644       }
1645   return false;
1646 }
1647
1648 /* Worker to bring NODE local.  */
1649
1650 static bool
1651 cgraph_make_node_local_1 (struct cgraph_node *node, void *data ATTRIBUTE_UNUSED)
1652 {
1653   gcc_checking_assert (cgraph_node_can_be_local_p (node));
1654   if (DECL_COMDAT (node->symbol.decl) || DECL_EXTERNAL (node->symbol.decl))
1655     {
1656       symtab_make_decl_local (node->symbol.decl);
1657
1658       node->symbol.externally_visible = false;
1659       node->local.local = true;
1660       node->symbol.resolution = LDPR_PREVAILING_DEF_IRONLY;
1661       gcc_assert (cgraph_function_body_availability (node) == AVAIL_LOCAL);
1662     }
1663   return false;
1664 }
1665
1666 /* Bring NODE local.  */
1667
1668 void
1669 cgraph_make_node_local (struct cgraph_node *node)
1670 {
1671   cgraph_for_node_thunks_and_aliases (node, cgraph_make_node_local_1,
1672                                       NULL, true);
1673 }
1674
1675 /* Worker to set nothrow flag.  */
1676
1677 static bool
1678 cgraph_set_nothrow_flag_1 (struct cgraph_node *node, void *data)
1679 {
1680   struct cgraph_edge *e;
1681
1682   TREE_NOTHROW (node->symbol.decl) = data != NULL;
1683
1684   if (data != NULL)
1685     for (e = node->callers; e; e = e->next_caller)
1686       e->can_throw_external = false;
1687   return false;
1688 }
1689
1690 /* Set TREE_NOTHROW on NODE's decl and on aliases of NODE
1691    if any to NOTHROW.  */
1692
1693 void
1694 cgraph_set_nothrow_flag (struct cgraph_node *node, bool nothrow)
1695 {
1696   cgraph_for_node_thunks_and_aliases (node, cgraph_set_nothrow_flag_1,
1697                                       (void *)(size_t)nothrow, false);
1698 }
1699
1700 /* Worker to set const flag.  */
1701
1702 static bool
1703 cgraph_set_const_flag_1 (struct cgraph_node *node, void *data)
1704 {
1705   /* Static constructors and destructors without a side effect can be
1706      optimized out.  */
1707   if (data && !((size_t)data & 2))
1708     {
1709       if (DECL_STATIC_CONSTRUCTOR (node->symbol.decl))
1710         DECL_STATIC_CONSTRUCTOR (node->symbol.decl) = 0;
1711       if (DECL_STATIC_DESTRUCTOR (node->symbol.decl))
1712         DECL_STATIC_DESTRUCTOR (node->symbol.decl) = 0;
1713     }
1714   TREE_READONLY (node->symbol.decl) = data != NULL;
1715   DECL_LOOPING_CONST_OR_PURE_P (node->symbol.decl) = ((size_t)data & 2) != 0;
1716   return false;
1717 }
1718
1719 /* Set TREE_READONLY on NODE's decl and on aliases of NODE
1720    if any to READONLY.  */
1721
1722 void
1723 cgraph_set_const_flag (struct cgraph_node *node, bool readonly, bool looping)
1724 {
1725   cgraph_for_node_thunks_and_aliases (node, cgraph_set_const_flag_1,
1726                                       (void *)(size_t)(readonly + (int)looping * 2),
1727                                       false);
1728 }
1729
1730 /* Worker to set pure flag.  */
1731
1732 static bool
1733 cgraph_set_pure_flag_1 (struct cgraph_node *node, void *data)
1734 {
1735   /* Static pureructors and destructors without a side effect can be
1736      optimized out.  */
1737   if (data && !((size_t)data & 2))
1738     {
1739       if (DECL_STATIC_CONSTRUCTOR (node->symbol.decl))
1740         DECL_STATIC_CONSTRUCTOR (node->symbol.decl) = 0;
1741       if (DECL_STATIC_DESTRUCTOR (node->symbol.decl))
1742         DECL_STATIC_DESTRUCTOR (node->symbol.decl) = 0;
1743     }
1744   DECL_PURE_P (node->symbol.decl) = data != NULL;
1745   DECL_LOOPING_CONST_OR_PURE_P (node->symbol.decl) = ((size_t)data & 2) != 0;
1746   return false;
1747 }
1748
1749 /* Set DECL_PURE_P on NODE's decl and on aliases of NODE
1750    if any to PURE.  */
1751
1752 void
1753 cgraph_set_pure_flag (struct cgraph_node *node, bool pure, bool looping)
1754 {
1755   cgraph_for_node_thunks_and_aliases (node, cgraph_set_pure_flag_1,
1756                                       (void *)(size_t)(pure + (int)looping * 2),
1757                                       false);
1758 }
1759
1760 /* Data used by cgraph_propagate_frequency.  */
1761
1762 struct cgraph_propagate_frequency_data
1763 {
1764   bool maybe_unlikely_executed;
1765   bool maybe_executed_once;
1766   bool only_called_at_startup;
1767   bool only_called_at_exit;
1768 };
1769
1770 /* Worker for cgraph_propagate_frequency_1.  */
1771
1772 static bool
1773 cgraph_propagate_frequency_1 (struct cgraph_node *node, void *data)
1774 {
1775   struct cgraph_propagate_frequency_data *d;
1776   struct cgraph_edge *edge;
1777
1778   d = (struct cgraph_propagate_frequency_data *)data;
1779   for (edge = node->callers;
1780        edge && (d->maybe_unlikely_executed || d->maybe_executed_once
1781                 || d->only_called_at_startup || d->only_called_at_exit);
1782        edge = edge->next_caller)
1783     {
1784       if (edge->caller != node)
1785         {
1786           d->only_called_at_startup &= edge->caller->only_called_at_startup;
1787           /* It makes sense to put main() together with the static constructors.
1788              It will be executed for sure, but rest of functions called from
1789              main are definitely not at startup only.  */
1790           if (MAIN_NAME_P (DECL_NAME (edge->caller->symbol.decl)))
1791             d->only_called_at_startup = 0;
1792           d->only_called_at_exit &= edge->caller->only_called_at_exit;
1793         }
1794       if (!edge->frequency)
1795         continue;
1796       switch (edge->caller->frequency)
1797         {
1798         case NODE_FREQUENCY_UNLIKELY_EXECUTED:
1799           break;
1800         case NODE_FREQUENCY_EXECUTED_ONCE:
1801           if (dump_file && (dump_flags & TDF_DETAILS))
1802             fprintf (dump_file, "  Called by %s that is executed once\n",
1803                      cgraph_node_name (edge->caller));
1804           d->maybe_unlikely_executed = false;
1805           if (inline_edge_summary (edge)->loop_depth)
1806             {
1807               d->maybe_executed_once = false;
1808               if (dump_file && (dump_flags & TDF_DETAILS))
1809                 fprintf (dump_file, "  Called in loop\n");
1810             }
1811           break;
1812         case NODE_FREQUENCY_HOT:
1813         case NODE_FREQUENCY_NORMAL:
1814           if (dump_file && (dump_flags & TDF_DETAILS))
1815             fprintf (dump_file, "  Called by %s that is normal or hot\n",
1816                      cgraph_node_name (edge->caller));
1817           d->maybe_unlikely_executed = false;
1818           d->maybe_executed_once = false;
1819           break;
1820         }
1821     }
1822   return edge != NULL;
1823 }
1824
1825 /* See if the frequency of NODE can be updated based on frequencies of its
1826    callers.  */
1827 bool
1828 cgraph_propagate_frequency (struct cgraph_node *node)
1829 {
1830   struct cgraph_propagate_frequency_data d = {true, true, true, true};
1831   bool changed = false;
1832
1833   if (!node->local.local)
1834     return false;
1835   gcc_assert (node->analyzed);
1836   if (dump_file && (dump_flags & TDF_DETAILS))
1837     fprintf (dump_file, "Processing frequency %s\n", cgraph_node_name (node));
1838
1839   cgraph_for_node_and_aliases (node, cgraph_propagate_frequency_1, &d, true);
1840
1841   if ((d.only_called_at_startup && !d.only_called_at_exit)
1842       && !node->only_called_at_startup)
1843     {
1844        node->only_called_at_startup = true;
1845        if (dump_file)
1846          fprintf (dump_file, "Node %s promoted to only called at startup.\n",
1847                   cgraph_node_name (node));
1848        changed = true;
1849     }
1850   if ((d.only_called_at_exit && !d.only_called_at_startup)
1851       && !node->only_called_at_exit)
1852     {
1853        node->only_called_at_exit = true;
1854        if (dump_file)
1855          fprintf (dump_file, "Node %s promoted to only called at exit.\n",
1856                   cgraph_node_name (node));
1857        changed = true;
1858     }
1859   /* These come either from profile or user hints; never update them.  */
1860   if (node->frequency == NODE_FREQUENCY_HOT
1861       || node->frequency == NODE_FREQUENCY_UNLIKELY_EXECUTED)
1862     return changed;
1863   if (d.maybe_unlikely_executed)
1864     {
1865       node->frequency = NODE_FREQUENCY_UNLIKELY_EXECUTED;
1866       if (dump_file)
1867         fprintf (dump_file, "Node %s promoted to unlikely executed.\n",
1868                  cgraph_node_name (node));
1869       changed = true;
1870     }
1871   else if (d.maybe_executed_once && node->frequency != NODE_FREQUENCY_EXECUTED_ONCE)
1872     {
1873       node->frequency = NODE_FREQUENCY_EXECUTED_ONCE;
1874       if (dump_file)
1875         fprintf (dump_file, "Node %s promoted to executed once.\n",
1876                  cgraph_node_name (node));
1877       changed = true;
1878     }
1879   return changed;
1880 }
1881
1882 /* Return true when NODE can not return or throw and thus
1883    it is safe to ignore its side effects for IPA analysis.  */
1884
1885 bool
1886 cgraph_node_cannot_return (struct cgraph_node *node)
1887 {
1888   int flags = flags_from_decl_or_type (node->symbol.decl);
1889   if (!flag_exceptions)
1890     return (flags & ECF_NORETURN) != 0;
1891   else
1892     return ((flags & (ECF_NORETURN | ECF_NOTHROW))
1893              == (ECF_NORETURN | ECF_NOTHROW));
1894 }
1895
1896 /* Return true when call of E can not lead to return from caller
1897    and thus it is safe to ignore its side effects for IPA analysis
1898    when computing side effects of the caller.
1899    FIXME: We could actually mark all edges that have no reaching
1900    patch to EXIT_BLOCK_PTR or throw to get better results.  */
1901 bool
1902 cgraph_edge_cannot_lead_to_return (struct cgraph_edge *e)
1903 {
1904   if (cgraph_node_cannot_return (e->caller))
1905     return true;
1906   if (e->indirect_unknown_callee)
1907     {
1908       int flags = e->indirect_info->ecf_flags;
1909       if (!flag_exceptions)
1910         return (flags & ECF_NORETURN) != 0;
1911       else
1912         return ((flags & (ECF_NORETURN | ECF_NOTHROW))
1913                  == (ECF_NORETURN | ECF_NOTHROW));
1914     }
1915   else
1916     return cgraph_node_cannot_return (e->callee);
1917 }
1918
1919 /* Return true when function NODE can be removed from callgraph
1920    if all direct calls are eliminated.  */
1921
1922 bool
1923 cgraph_can_remove_if_no_direct_calls_and_refs_p (struct cgraph_node *node)
1924 {
1925   gcc_assert (!node->global.inlined_to);
1926   /* Extern inlines can always go, we will use the external definition.  */
1927   if (DECL_EXTERNAL (node->symbol.decl))
1928     return true;
1929   /* When function is needed, we can not remove it.  */
1930   if (node->symbol.force_output || node->symbol.used_from_other_partition)
1931     return false;
1932   if (DECL_STATIC_CONSTRUCTOR (node->symbol.decl)
1933       || DECL_STATIC_DESTRUCTOR (node->symbol.decl))
1934     return false;
1935   /* Only COMDAT functions can be removed if externally visible.  */
1936   if (node->symbol.externally_visible
1937       && (!DECL_COMDAT (node->symbol.decl)
1938           || symtab_used_from_object_file_p ((symtab_node) node)))
1939     return false;
1940   return true;
1941 }
1942
1943 /* Worker for cgraph_can_remove_if_no_direct_calls_p.  */
1944
1945 static bool
1946 nonremovable_p (struct cgraph_node *node, void *data ATTRIBUTE_UNUSED)
1947 {
1948   return !cgraph_can_remove_if_no_direct_calls_and_refs_p (node);
1949 }
1950
1951 /* Return true when function NODE and its aliases can be removed from callgraph
1952    if all direct calls are eliminated.  */
1953
1954 bool
1955 cgraph_can_remove_if_no_direct_calls_p (struct cgraph_node *node)
1956 {
1957   /* Extern inlines can always go, we will use the external definition.  */
1958   if (DECL_EXTERNAL (node->symbol.decl))
1959     return true;
1960   if (node->symbol.address_taken)
1961     return false;
1962   return !cgraph_for_node_and_aliases (node, nonremovable_p, NULL, true);
1963 }
1964
1965 /* Worker for cgraph_can_remove_if_no_direct_calls_p.  */
1966
1967 static bool
1968 used_from_object_file_p (struct cgraph_node *node, void *data ATTRIBUTE_UNUSED)
1969 {
1970   return symtab_used_from_object_file_p ((symtab_node) node);
1971 }
1972
1973 /* Return true when function NODE can be expected to be removed
1974    from program when direct calls in this compilation unit are removed.
1975
1976    As a special case COMDAT functions are
1977    cgraph_can_remove_if_no_direct_calls_p while the are not
1978    cgraph_only_called_directly_p (it is possible they are called from other
1979    unit)
1980
1981    This function behaves as cgraph_only_called_directly_p because eliminating
1982    all uses of COMDAT function does not make it necessarily disappear from
1983    the program unless we are compiling whole program or we do LTO.  In this
1984    case we know we win since dynamic linking will not really discard the
1985    linkonce section.  */
1986
1987 bool
1988 cgraph_will_be_removed_from_program_if_no_direct_calls (struct cgraph_node *node)
1989 {
1990   gcc_assert (!node->global.inlined_to);
1991   if (cgraph_for_node_and_aliases (node, used_from_object_file_p, NULL, true))
1992     return false;
1993   if (!in_lto_p && !flag_whole_program)
1994     return cgraph_only_called_directly_p (node);
1995   else
1996     {
1997        if (DECL_EXTERNAL (node->symbol.decl))
1998          return true;
1999       return cgraph_can_remove_if_no_direct_calls_p (node);
2000     }
2001 }
2002
2003
2004 /* Worker for cgraph_only_called_directly_p.  */
2005
2006 static bool
2007 cgraph_not_only_called_directly_p_1 (struct cgraph_node *node, void *data ATTRIBUTE_UNUSED)
2008 {
2009   return !cgraph_only_called_directly_or_aliased_p (node);
2010 }
2011
2012 /* Return true when function NODE and all its aliases are only called
2013    directly.
2014    i.e. it is not externally visible, address was not taken and
2015    it is not used in any other non-standard way.  */
2016
2017 bool
2018 cgraph_only_called_directly_p (struct cgraph_node *node)
2019 {
2020   gcc_assert (cgraph_function_or_thunk_node (node, NULL) == node);
2021   return !cgraph_for_node_and_aliases (node, cgraph_not_only_called_directly_p_1,
2022                                        NULL, true);
2023 }
2024
2025
2026 /* Collect all callers of NODE.  Worker for collect_callers_of_node.  */
2027
2028 static bool
2029 collect_callers_of_node_1 (struct cgraph_node *node, void *data)
2030 {
2031   VEC (cgraph_edge_p, heap) ** redirect_callers = (VEC (cgraph_edge_p, heap) **)data;
2032   struct cgraph_edge *cs;
2033   enum availability avail;
2034   cgraph_function_or_thunk_node (node, &avail);
2035
2036   if (avail > AVAIL_OVERWRITABLE)
2037     for (cs = node->callers; cs != NULL; cs = cs->next_caller)
2038       if (!cs->indirect_inlining_edge)
2039         VEC_safe_push (cgraph_edge_p, heap, *redirect_callers, cs);
2040   return false;
2041 }
2042
2043 /* Collect all callers of NODE and its aliases that are known to lead to NODE
2044    (i.e. are not overwritable).  */
2045
2046 VEC (cgraph_edge_p, heap) *
2047 collect_callers_of_node (struct cgraph_node *node)
2048 {
2049   VEC (cgraph_edge_p, heap) * redirect_callers = NULL;
2050   cgraph_for_node_and_aliases (node, collect_callers_of_node_1,
2051                                &redirect_callers, false);
2052   return redirect_callers;
2053 }
2054
2055 /* Return TRUE if NODE2 is equivalent to NODE or its clone.  */
2056 static bool
2057 clone_of_p (struct cgraph_node *node, struct cgraph_node *node2)
2058 {
2059   node = cgraph_function_or_thunk_node (node, NULL);
2060   node2 = cgraph_function_or_thunk_node (node2, NULL);
2061   while (node != node2 && node2)
2062     node2 = node2->clone_of;
2063   return node2 != NULL;
2064 }
2065
2066 /* Verify edge E count and frequency.  */
2067
2068 static bool
2069 verify_edge_count_and_frequency (struct cgraph_edge *e)
2070 {
2071   bool error_found = false;
2072   if (e->count < 0)
2073     {
2074       error ("caller edge count is negative");
2075       error_found = true;
2076     }
2077   if (e->frequency < 0)
2078     {
2079       error ("caller edge frequency is negative");
2080       error_found = true;
2081     }
2082   if (e->frequency > CGRAPH_FREQ_MAX)
2083     {
2084       error ("caller edge frequency is too large");
2085       error_found = true;
2086     }
2087   if (gimple_has_body_p (e->caller->symbol.decl)
2088       && !e->caller->global.inlined_to
2089       /* FIXME: Inline-analysis sets frequency to 0 when edge is optimized out.
2090          Remove this once edges are actualy removed from the function at that time.  */
2091       && (e->frequency
2092           || (inline_edge_summary_vec
2093               && ((VEC_length(inline_edge_summary_t, inline_edge_summary_vec)
2094                   <= (unsigned) e->uid)
2095                   || !inline_edge_summary (e)->predicate)))
2096       && (e->frequency
2097           != compute_call_stmt_bb_frequency (e->caller->symbol.decl,
2098                                              gimple_bb (e->call_stmt))))
2099     {
2100       error ("caller edge frequency %i does not match BB frequency %i",
2101              e->frequency,
2102              compute_call_stmt_bb_frequency (e->caller->symbol.decl,
2103                                              gimple_bb (e->call_stmt)));
2104       error_found = true;
2105     }
2106   return error_found;
2107 }
2108
2109 /* Switch to THIS_CFUN if needed and print STMT to stderr.  */
2110 static void
2111 cgraph_debug_gimple_stmt (struct function *this_cfun, gimple stmt)
2112 {
2113   /* debug_gimple_stmt needs correct cfun */
2114   if (cfun != this_cfun)
2115     set_cfun (this_cfun);
2116   debug_gimple_stmt (stmt);
2117 }
2118
2119 /* Verify that call graph edge E corresponds to DECL from the associated
2120    statement.  Return true if the verification should fail.  */
2121
2122 static bool
2123 verify_edge_corresponds_to_fndecl (struct cgraph_edge *e, tree decl)
2124 {
2125   struct cgraph_node *node;
2126
2127   if (!decl || e->callee->global.inlined_to)
2128     return false;
2129   node = cgraph_get_node (decl);
2130
2131   /* We do not know if a node from a different partition is an alias or what it
2132      aliases and therefore cannot do the former_clone_of check reliably.  */
2133   if (!node || node->symbol.in_other_partition)
2134     return false;
2135   node = cgraph_function_or_thunk_node (node, NULL);
2136
2137   if ((e->callee->former_clone_of != node->symbol.decl
2138        && (!node->same_body_alias
2139            || e->callee->former_clone_of != node->thunk.alias))
2140       /* IPA-CP sometimes redirect edge to clone and then back to the former
2141          function.  This ping-pong has to go, eventually.  */
2142       && (node != cgraph_function_or_thunk_node (e->callee, NULL))
2143       && !clone_of_p (node, e->callee)
2144       /* If decl is a same body alias of some other decl, allow e->callee to be
2145          a clone of a clone of that other decl too.  */
2146       && (!node->same_body_alias
2147           || !clone_of_p (cgraph_get_node (node->thunk.alias), e->callee)))
2148     return true;
2149   else
2150     return false;
2151 }
2152
2153 /* Verify cgraph nodes of given cgraph node.  */
2154 DEBUG_FUNCTION void
2155 verify_cgraph_node (struct cgraph_node *node)
2156 {
2157   struct cgraph_edge *e;
2158   struct function *this_cfun = DECL_STRUCT_FUNCTION (node->symbol.decl);
2159   basic_block this_block;
2160   gimple_stmt_iterator gsi;
2161   bool error_found = false;
2162
2163   if (seen_error ())
2164     return;
2165
2166   timevar_push (TV_CGRAPH_VERIFY);
2167   error_found |= verify_symtab_base ((symtab_node) node);
2168   for (e = node->callees; e; e = e->next_callee)
2169     if (e->aux)
2170       {
2171         error ("aux field set for edge %s->%s",
2172                identifier_to_locale (cgraph_node_name (e->caller)),
2173                identifier_to_locale (cgraph_node_name (e->callee)));
2174         error_found = true;
2175       }
2176   if (node->count < 0)
2177     {
2178       error ("execution count is negative");
2179       error_found = true;
2180     }
2181   if (node->global.inlined_to && node->symbol.same_comdat_group)
2182     {
2183       error ("inline clone in same comdat group list");
2184       error_found = true;
2185     }
2186   if (node->global.inlined_to && node->symbol.externally_visible)
2187     {
2188       error ("externally visible inline clone");
2189       error_found = true;
2190     }
2191   if (node->global.inlined_to && node->symbol.address_taken)
2192     {
2193       error ("inline clone with address taken");
2194       error_found = true;
2195     }
2196   if (node->global.inlined_to && node->symbol.force_output)
2197     {
2198       error ("inline clone is forced to output");
2199       error_found = true;
2200     }
2201   for (e = node->indirect_calls; e; e = e->next_callee)
2202     {
2203       if (e->aux)
2204         {
2205           error ("aux field set for indirect edge from %s",
2206                  identifier_to_locale (cgraph_node_name (e->caller)));
2207           error_found = true;
2208         }
2209       if (!e->indirect_unknown_callee
2210           || !e->indirect_info)
2211         {
2212           error ("An indirect edge from %s is not marked as indirect or has "
2213                  "associated indirect_info, the corresponding statement is: ",
2214                  identifier_to_locale (cgraph_node_name (e->caller)));
2215           cgraph_debug_gimple_stmt (this_cfun, e->call_stmt);
2216           error_found = true;
2217         }
2218     }
2219   for (e = node->callers; e; e = e->next_caller)
2220     {
2221       if (verify_edge_count_and_frequency (e))
2222         error_found = true;
2223       if (!e->inline_failed)
2224         {
2225           if (node->global.inlined_to
2226               != (e->caller->global.inlined_to
2227                   ? e->caller->global.inlined_to : e->caller))
2228             {
2229               error ("inlined_to pointer is wrong");
2230               error_found = true;
2231             }
2232           if (node->callers->next_caller)
2233             {
2234               error ("multiple inline callers");
2235               error_found = true;
2236             }
2237         }
2238       else
2239         if (node->global.inlined_to)
2240           {
2241             error ("inlined_to pointer set for noninline callers");
2242             error_found = true;
2243           }
2244     }
2245   for (e = node->indirect_calls; e; e = e->next_callee)
2246     if (verify_edge_count_and_frequency (e))
2247       error_found = true;
2248   if (!node->callers && node->global.inlined_to)
2249     {
2250       error ("inlined_to pointer is set but no predecessors found");
2251       error_found = true;
2252     }
2253   if (node->global.inlined_to == node)
2254     {
2255       error ("inlined_to pointer refers to itself");
2256       error_found = true;
2257     }
2258
2259   if (node->clone_of)
2260     {
2261       struct cgraph_node *n;
2262       for (n = node->clone_of->clones; n; n = n->next_sibling_clone)
2263         if (n == node)
2264           break;
2265       if (!n)
2266         {
2267           error ("node has wrong clone_of");
2268           error_found = true;
2269         }
2270     }
2271   if (node->clones)
2272     {
2273       struct cgraph_node *n;
2274       for (n = node->clones; n; n = n->next_sibling_clone)
2275         if (n->clone_of != node)
2276           break;
2277       if (n)
2278         {
2279           error ("node has wrong clone list");
2280           error_found = true;
2281         }
2282     }
2283   if ((node->prev_sibling_clone || node->next_sibling_clone) && !node->clone_of)
2284     {
2285        error ("node is in clone list but it is not clone");
2286        error_found = true;
2287     }
2288   if (!node->prev_sibling_clone && node->clone_of && node->clone_of->clones != node)
2289     {
2290       error ("node has wrong prev_clone pointer");
2291       error_found = true;
2292     }
2293   if (node->prev_sibling_clone && node->prev_sibling_clone->next_sibling_clone != node)
2294     {
2295       error ("double linked list of clones corrupted");
2296       error_found = true;
2297     }
2298
2299   if (node->analyzed && node->alias)
2300     {
2301       bool ref_found = false;
2302       int i;
2303       struct ipa_ref *ref;
2304
2305       if (node->callees)
2306         {
2307           error ("Alias has call edges");
2308           error_found = true;
2309         }
2310       for (i = 0; ipa_ref_list_reference_iterate (&node->symbol.ref_list,
2311                                                   i, ref); i++)
2312         if (ref->use != IPA_REF_ALIAS)
2313           {
2314             error ("Alias has non-alias reference");
2315             error_found = true;
2316           }
2317         else if (ref_found)
2318           {
2319             error ("Alias has more than one alias reference");
2320             error_found = true;
2321           }
2322         else
2323           ref_found = true;
2324         if (!ref_found)
2325           {
2326             error ("Analyzed alias has no reference");
2327             error_found = true;
2328           }
2329     }
2330   if (node->analyzed && node->thunk.thunk_p)
2331     {
2332       if (!node->callees)
2333         {
2334           error ("No edge out of thunk node");
2335           error_found = true;
2336         }
2337       else if (node->callees->next_callee)
2338         {
2339           error ("More than one edge out of thunk node");
2340           error_found = true;
2341         }
2342       if (gimple_has_body_p (node->symbol.decl))
2343         {
2344           error ("Thunk is not supposed to have body");
2345           error_found = true;
2346         }
2347     }
2348   else if (node->analyzed && gimple_has_body_p (node->symbol.decl)
2349            && !TREE_ASM_WRITTEN (node->symbol.decl)
2350            && (!DECL_EXTERNAL (node->symbol.decl) || node->global.inlined_to)
2351            && !flag_wpa)
2352     {
2353       if (this_cfun->cfg)
2354         {
2355           /* The nodes we're interested in are never shared, so walk
2356              the tree ignoring duplicates.  */
2357           struct pointer_set_t *visited_nodes = pointer_set_create ();
2358           /* Reach the trees by walking over the CFG, and note the
2359              enclosing basic-blocks in the call edges.  */
2360           FOR_EACH_BB_FN (this_block, this_cfun)
2361             for (gsi = gsi_start_bb (this_block);
2362                  !gsi_end_p (gsi);
2363                  gsi_next (&gsi))
2364               {
2365                 gimple stmt = gsi_stmt (gsi);
2366                 if (is_gimple_call (stmt))
2367                   {
2368                     struct cgraph_edge *e = cgraph_edge (node, stmt);
2369                     tree decl = gimple_call_fndecl (stmt);
2370                     if (e)
2371                       {
2372                         if (e->aux)
2373                           {
2374                             error ("shared call_stmt:");
2375                             cgraph_debug_gimple_stmt (this_cfun, stmt);
2376                             error_found = true;
2377                           }
2378                         if (!e->indirect_unknown_callee)
2379                           {
2380                             if (verify_edge_corresponds_to_fndecl (e, decl))
2381                               {
2382                                 error ("edge points to wrong declaration:");
2383                                 debug_tree (e->callee->symbol.decl);
2384                                 fprintf (stderr," Instead of:");
2385                                 debug_tree (decl);
2386                                 error_found = true;
2387                               }
2388                           }
2389                         else if (decl)
2390                           {
2391                             error ("an indirect edge with unknown callee "
2392                                    "corresponding to a call_stmt with "
2393                                    "a known declaration:");
2394                             error_found = true;
2395                             cgraph_debug_gimple_stmt (this_cfun, e->call_stmt);
2396                           }
2397                         e->aux = (void *)1;
2398                       }
2399                     else if (decl)
2400                       {
2401                         error ("missing callgraph edge for call stmt:");
2402                         cgraph_debug_gimple_stmt (this_cfun, stmt);
2403                         error_found = true;
2404                       }
2405                   }
2406               }
2407           pointer_set_destroy (visited_nodes);
2408         }
2409       else
2410         /* No CFG available?!  */
2411         gcc_unreachable ();
2412
2413       for (e = node->callees; e; e = e->next_callee)
2414         {
2415           if (!e->aux)
2416             {
2417               error ("edge %s->%s has no corresponding call_stmt",
2418                      identifier_to_locale (cgraph_node_name (e->caller)),
2419                      identifier_to_locale (cgraph_node_name (e->callee)));
2420               cgraph_debug_gimple_stmt (this_cfun, e->call_stmt);
2421               error_found = true;
2422             }
2423           e->aux = 0;
2424         }
2425       for (e = node->indirect_calls; e; e = e->next_callee)
2426         {
2427           if (!e->aux)
2428             {
2429               error ("an indirect edge from %s has no corresponding call_stmt",
2430                      identifier_to_locale (cgraph_node_name (e->caller)));
2431               cgraph_debug_gimple_stmt (this_cfun, e->call_stmt);
2432               error_found = true;
2433             }
2434           e->aux = 0;
2435         }
2436     }
2437   if (error_found)
2438     {
2439       dump_cgraph_node (stderr, node);
2440       internal_error ("verify_cgraph_node failed");
2441     }
2442   timevar_pop (TV_CGRAPH_VERIFY);
2443 }
2444
2445 /* Verify whole cgraph structure.  */
2446 DEBUG_FUNCTION void
2447 verify_cgraph (void)
2448 {
2449   struct cgraph_node *node;
2450
2451   if (seen_error ())
2452     return;
2453
2454   FOR_EACH_FUNCTION (node)
2455     verify_cgraph_node (node);
2456 }
2457 #include "gt-cgraph.h"