gcc/cgraph.c

   1 /* Callgraph handling code.
   2    Copyright (C) 2003, 2004, 2005, 2006, 2007, 2008, 2009, 2010
   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 /*  This file contains basic routines manipulating call graph
  23
  24 The callgraph:
  25
  26     The call-graph is data structure designed for intra-procedural optimization
  27     but it is also used in non-unit-at-a-time compilation to allow easier code
  28     sharing.
  29
  30     The call-graph consist of nodes and edges represented via linked lists.
  31     Each function (external or not) corresponds to the unique node.
  32
  33     The mapping from declarations to call-graph nodes is done using hash table
  34     based on DECL_UID.  The call-graph nodes are created lazily using
  35     cgraph_node function when called for unknown declaration.
  36
  37     The callgraph at the moment does not represent indirect calls or calls
  38     from other compilation unit.  Flag NEEDED is set for each node that may
  39     be accessed in such an invisible way and it shall be considered an
  40     entry point to the callgraph.
  41
  42     Interprocedural information:
  43
  44       Callgraph is place to store data needed for interprocedural optimization.
  45       All data structures are divided into three components: local_info that
  46       is produced while analyzing the function, global_info that is result
  47       of global walking of the callgraph on the end of compilation and
  48       rtl_info used by RTL backend to propagate data from already compiled
  49       functions to their callers.
  50
  51     Inlining plans:
  52
  53       The function inlining information is decided in advance and maintained
  54       in the callgraph as so called inline plan.
  55       For each inlined call, the callee's node is cloned to represent the
  56       new function copy produced by inliner.
  57       Each inlined call gets a unique corresponding clone node of the callee
  58       and the data structure is updated while inlining is performed, so
  59       the clones are eliminated and their callee edges redirected to the
  60       caller.
  61
  62       Each edge has "inline_failed" field.  When the field is set to NULL,
  63       the call will be inlined.  When it is non-NULL it contains a reason
  64       why inlining wasn't performed.  */
  65
  66 #include "config.h"
  67 #include "system.h"
  68 #include "coretypes.h"
  69 #include "tm.h"
  70 #include "tree.h"
  71 #include "tree-inline.h"
  72 #include "langhooks.h"
  73 #include "hashtab.h"
  74 #include "toplev.h"
  75 #include "flags.h"
  76 #include "ggc.h"
  77 #include "debug.h"
  78 #include "target.h"
  79 #include "basic-block.h"
  80 #include "cgraph.h"
  81 #include "output.h"
  82 #include "intl.h"
  83 #include "gimple.h"
  84 #include "tree-dump.h"
  85 #include "tree-flow.h"
  86 #include "value-prof.h"
  87 #include "except.h"
  88 #include "diagnostic.h"
  89 #include "rtl.h"
  90
  91 static void cgraph_node_remove_callers (struct cgraph_node *node);
  92 static inline void cgraph_edge_remove_caller (struct cgraph_edge *e);
  93 static inline void cgraph_edge_remove_callee (struct cgraph_edge *e);
  94
  95 /* Hash table used to convert declarations into nodes.  */
  96 static GTY((param_is (struct cgraph_node))) htab_t cgraph_hash;
  97 /* Hash table used to convert assembler names into nodes.  */
  98 static GTY((param_is (struct cgraph_node))) htab_t assembler_name_hash;
  99
 100 /* The linked list of cgraph nodes.  */
 101 struct cgraph_node *cgraph_nodes;
 102
 103 /* Queue of cgraph nodes scheduled to be lowered.  */
 104 struct cgraph_node *cgraph_nodes_queue;
 105
 106 /* Queue of cgraph nodes scheduled to be added into cgraph.  This is a
 107    secondary queue used during optimization to accommodate passes that
 108    may generate new functions that need to be optimized and expanded.  */
 109 struct cgraph_node *cgraph_new_nodes;
 110
 111 /* Number of nodes in existence.  */
 112 int cgraph_n_nodes;
 113
 114 /* Maximal uid used in cgraph nodes.  */
 115 int cgraph_max_uid;
 116
 117 /* Maximal uid used in cgraph edges.  */
 118 int cgraph_edge_max_uid;
 119
 120 /* Maximal pid used for profiling */
 121 int cgraph_max_pid;
 122
 123 /* Set when whole unit has been analyzed so we can access global info.  */
 124 bool cgraph_global_info_ready = false;
 125
 126 /* What state callgraph is in right now.  */
 127 enum cgraph_state cgraph_state = CGRAPH_STATE_CONSTRUCTION;
 128
 129 /* Set when the cgraph is fully build and the basic flags are computed.  */
 130 bool cgraph_function_flags_ready = false;
 131
 132 /* Linked list of cgraph asm nodes.  */
 133 struct cgraph_asm_node *cgraph_asm_nodes;
 134
 135 /* Last node in cgraph_asm_nodes.  */
 136 static GTY(()) struct cgraph_asm_node *cgraph_asm_last_node;
 137
 138 /* The order index of the next cgraph node to be created.  This is
 139    used so that we can sort the cgraph nodes in order by when we saw
 140    them, to support -fno-toplevel-reorder.  */
 141 int cgraph_order;
 142
 143 /* List of hooks trigerred on cgraph_edge events.  */
 144 struct cgraph_edge_hook_list {
 145   cgraph_edge_hook hook;
 146   void *data;
 147   struct cgraph_edge_hook_list *next;
 148 };
 149
 150 /* List of hooks trigerred on cgraph_node events.  */
 151 struct cgraph_node_hook_list {
 152   cgraph_node_hook hook;
 153   void *data;
 154   struct cgraph_node_hook_list *next;
 155 };
 156
 157 /* List of hooks trigerred on events involving two cgraph_edges.  */
 158 struct cgraph_2edge_hook_list {
 159   cgraph_2edge_hook hook;
 160   void *data;
 161   struct cgraph_2edge_hook_list *next;
 162 };
 163
 164 /* List of hooks trigerred on events involving two cgraph_nodes.  */
 165 struct cgraph_2node_hook_list {
 166   cgraph_2node_hook hook;
 167   void *data;
 168   struct cgraph_2node_hook_list *next;
 169 };
 170
 171 /* List of hooks triggered when an edge is removed.  */
 172 struct cgraph_edge_hook_list *first_cgraph_edge_removal_hook;
 173 /* List of hooks triggered when a node is removed.  */
 174 struct cgraph_node_hook_list *first_cgraph_node_removal_hook;
 175 /* List of hooks triggered when an edge is duplicated.  */
 176 struct cgraph_2edge_hook_list *first_cgraph_edge_duplicated_hook;
 177 /* List of hooks triggered when a node is duplicated.  */
 178 struct cgraph_2node_hook_list *first_cgraph_node_duplicated_hook;
 179 /* List of hooks triggered when an function is inserted.  */
 180 struct cgraph_node_hook_list *first_cgraph_function_insertion_hook;
 181
 182 /* Head of a linked list of unused (freed) call graph nodes.
 183    Do not GTY((delete)) this list so UIDs gets reliably recycled.  */
 184 static GTY(()) struct cgraph_node *free_nodes;
 185 /* Head of a linked list of unused (freed) call graph edges.
 186    Do not GTY((delete)) this list so UIDs gets reliably recycled.  */
 187 static GTY(()) struct cgraph_edge *free_edges;
 188
 189 /* Macros to access the next item in the list of free cgraph nodes and
 190    edges. */
 191 #define NEXT_FREE_NODE(NODE) (NODE)->next
 192 #define NEXT_FREE_EDGE(EDGE) (EDGE)->prev_caller
 193
 194 /* Register HOOK to be called with DATA on each removed edge.  */
 195 struct cgraph_edge_hook_list *
 196 cgraph_add_edge_removal_hook (cgraph_edge_hook hook, void *data)
 197 {
 198   struct cgraph_edge_hook_list *entry;
 199   struct cgraph_edge_hook_list **ptr = &first_cgraph_edge_removal_hook;
 200
 201   entry = (struct cgraph_edge_hook_list *) xmalloc (sizeof (*entry));
 202   entry->hook = hook;
 203   entry->data = data;
 204   entry->next = NULL;
 205   while (*ptr)
 206     ptr = &(*ptr)->next;
 207   *ptr = entry;
 208   return entry;
 209 }
 210
 211 /* Remove ENTRY from the list of hooks called on removing edges.  */
 212 void
 213 cgraph_remove_edge_removal_hook (struct cgraph_edge_hook_list *entry)
 214 {
 215   struct cgraph_edge_hook_list **ptr = &first_cgraph_edge_removal_hook;
 216
 217   while (*ptr != entry)
 218     ptr = &(*ptr)->next;
 219   *ptr = entry->next;
 220   free (entry);
 221 }
 222
 223 /* Call all edge removal hooks.  */
 224 static void
 225 cgraph_call_edge_removal_hooks (struct cgraph_edge *e)
 226 {
 227   struct cgraph_edge_hook_list *entry = first_cgraph_edge_removal_hook;
 228   while (entry)
 229   {
 230     entry->hook (e, entry->data);
 231     entry = entry->next;
 232   }
 233 }
 234
 235 /* Register HOOK to be called with DATA on each removed node.  */
 236 struct cgraph_node_hook_list *
 237 cgraph_add_node_removal_hook (cgraph_node_hook hook, void *data)
 238 {
 239   struct cgraph_node_hook_list *entry;
 240   struct cgraph_node_hook_list **ptr = &first_cgraph_node_removal_hook;
 241
 242   entry = (struct cgraph_node_hook_list *) xmalloc (sizeof (*entry));
 243   entry->hook = hook;
 244   entry->data = data;
 245   entry->next = NULL;
 246   while (*ptr)
 247     ptr = &(*ptr)->next;
 248   *ptr = entry;
 249   return entry;
 250 }
 251
 252 /* Remove ENTRY from the list of hooks called on removing nodes.  */
 253 void
 254 cgraph_remove_node_removal_hook (struct cgraph_node_hook_list *entry)
 255 {
 256   struct cgraph_node_hook_list **ptr = &first_cgraph_node_removal_hook;
 257
 258   while (*ptr != entry)
 259     ptr = &(*ptr)->next;
 260   *ptr = entry->next;
 261   free (entry);
 262 }
 263
 264 /* Call all node removal hooks.  */
 265 static void
 266 cgraph_call_node_removal_hooks (struct cgraph_node *node)
 267 {
 268   struct cgraph_node_hook_list *entry = first_cgraph_node_removal_hook;
 269   while (entry)
 270   {
 271     entry->hook (node, entry->data);
 272     entry = entry->next;
 273   }
 274 }
 275
 276 /* Register HOOK to be called with DATA on each inserted node.  */
 277 struct cgraph_node_hook_list *
 278 cgraph_add_function_insertion_hook (cgraph_node_hook hook, void *data)
 279 {
 280   struct cgraph_node_hook_list *entry;
 281   struct cgraph_node_hook_list **ptr = &first_cgraph_function_insertion_hook;
 282
 283   entry = (struct cgraph_node_hook_list *) xmalloc (sizeof (*entry));
 284   entry->hook = hook;
 285   entry->data = data;
 286   entry->next = NULL;
 287   while (*ptr)
 288     ptr = &(*ptr)->next;
 289   *ptr = entry;
 290   return entry;
 291 }
 292
 293 /* Remove ENTRY from the list of hooks called on inserted nodes.  */
 294 void
 295 cgraph_remove_function_insertion_hook (struct cgraph_node_hook_list *entry)
 296 {
 297   struct cgraph_node_hook_list **ptr = &first_cgraph_function_insertion_hook;
 298
 299   while (*ptr != entry)
 300     ptr = &(*ptr)->next;
 301   *ptr = entry->next;
 302   free (entry);
 303 }
 304
 305 /* Call all node insertion hooks.  */
 306 void
 307 cgraph_call_function_insertion_hooks (struct cgraph_node *node)
 308 {
 309   struct cgraph_node_hook_list *entry = first_cgraph_function_insertion_hook;
 310   while (entry)
 311   {
 312     entry->hook (node, entry->data);
 313     entry = entry->next;
 314   }
 315 }
 316
 317 /* Register HOOK to be called with DATA on each duplicated edge.  */
 318 struct cgraph_2edge_hook_list *
 319 cgraph_add_edge_duplication_hook (cgraph_2edge_hook hook, void *data)
 320 {
 321   struct cgraph_2edge_hook_list *entry;
 322   struct cgraph_2edge_hook_list **ptr = &first_cgraph_edge_duplicated_hook;
 323
 324   entry = (struct cgraph_2edge_hook_list *) xmalloc (sizeof (*entry));
 325   entry->hook = hook;
 326   entry->data = data;
 327   entry->next = NULL;
 328   while (*ptr)
 329     ptr = &(*ptr)->next;
 330   *ptr = entry;
 331   return entry;
 332 }
 333
 334 /* Remove ENTRY from the list of hooks called on duplicating edges.  */
 335 void
 336 cgraph_remove_edge_duplication_hook (struct cgraph_2edge_hook_list *entry)
 337 {
 338   struct cgraph_2edge_hook_list **ptr = &first_cgraph_edge_duplicated_hook;
 339
 340   while (*ptr != entry)
 341     ptr = &(*ptr)->next;
 342   *ptr = entry->next;
 343   free (entry);
 344 }
 345
 346 /* Call all edge duplication hooks.  */
 347 static void
 348 cgraph_call_edge_duplication_hooks (struct cgraph_edge *cs1,
 349                                     struct cgraph_edge *cs2)
 350 {
 351   struct cgraph_2edge_hook_list *entry = first_cgraph_edge_duplicated_hook;
 352   while (entry)
 353   {
 354     entry->hook (cs1, cs2, entry->data);
 355     entry = entry->next;
 356   }
 357 }
 358
 359 /* Register HOOK to be called with DATA on each duplicated node.  */
 360 struct cgraph_2node_hook_list *
 361 cgraph_add_node_duplication_hook (cgraph_2node_hook hook, void *data)
 362 {
 363   struct cgraph_2node_hook_list *entry;
 364   struct cgraph_2node_hook_list **ptr = &first_cgraph_node_duplicated_hook;
 365
 366   entry = (struct cgraph_2node_hook_list *) xmalloc (sizeof (*entry));
 367   entry->hook = hook;
 368   entry->data = data;
 369   entry->next = NULL;
 370   while (*ptr)
 371     ptr = &(*ptr)->next;
 372   *ptr = entry;
 373   return entry;
 374 }
 375
 376 /* Remove ENTRY from the list of hooks called on duplicating nodes.  */
 377 void
 378 cgraph_remove_node_duplication_hook (struct cgraph_2node_hook_list *entry)
 379 {
 380   struct cgraph_2node_hook_list **ptr = &first_cgraph_node_duplicated_hook;
 381
 382   while (*ptr != entry)
 383     ptr = &(*ptr)->next;
 384   *ptr = entry->next;
 385   free (entry);
 386 }
 387
 388 /* Call all node duplication hooks.  */
 389 static void
 390 cgraph_call_node_duplication_hooks (struct cgraph_node *node1,
 391                                     struct cgraph_node *node2)
 392 {
 393   struct cgraph_2node_hook_list *entry = first_cgraph_node_duplicated_hook;
 394   while (entry)
 395   {
 396     entry->hook (node1, node2, entry->data);
 397     entry = entry->next;
 398   }
 399 }
 400
 401 /* Returns a hash code for P.  */
 402
 403 static hashval_t
 404 hash_node (const void *p)
 405 {
 406   const struct cgraph_node *n = (const struct cgraph_node *) p;
 407   return (hashval_t) DECL_UID (n->decl);
 408 }
 409
 410
 411 /* Returns nonzero if P1 and P2 are equal.  */
 412
 413 static int
 414 eq_node (const void *p1, const void *p2)
 415 {
 416   const struct cgraph_node *n1 = (const struct cgraph_node *) p1;
 417   const struct cgraph_node *n2 = (const struct cgraph_node *) p2;
 418   return DECL_UID (n1->decl) == DECL_UID (n2->decl);
 419 }
 420
 421 /* Allocate new callgraph node.  */
 422
 423 static inline struct cgraph_node *
 424 cgraph_allocate_node (void)
 425 {
 426   struct cgraph_node *node;
 427
 428   if (free_nodes)
 429     {
 430       node = free_nodes;
 431       free_nodes = NEXT_FREE_NODE (node);
 432     }
 433   else
 434     {
 435       node = GGC_CNEW (struct cgraph_node);
 436       node->uid = cgraph_max_uid++;
 437     }
 438
 439   return node;
 440 }
 441
 442 /* Allocate new callgraph node and insert it into basic data structures.  */
 443
 444 static struct cgraph_node *
 445 cgraph_create_node (void)
 446 {
 447   struct cgraph_node *node = cgraph_allocate_node ();
 448
 449   node->next = cgraph_nodes;
 450   node->pid = -1;
 451   node->order = cgraph_order++;
 452   if (cgraph_nodes)
 453     cgraph_nodes->previous = node;
 454   node->previous = NULL;
 455   node->global.estimated_growth = INT_MIN;
 456   node->frequency = NODE_FREQUENCY_NORMAL;
 457   cgraph_nodes = node;
 458   cgraph_n_nodes++;
 459   return node;
 460 }
 461
 462 /* Return cgraph node assigned to DECL.  Create new one when needed.  */
 463
 464 struct cgraph_node *
 465 cgraph_node (tree decl)
 466 {
 467   struct cgraph_node key, *node, **slot;
 468
 469   gcc_assert (TREE_CODE (decl) == FUNCTION_DECL);
 470
 471   if (!cgraph_hash)
 472     cgraph_hash = htab_create_ggc (10, hash_node, eq_node, NULL);
 473
 474   key.decl = decl;
 475
 476   slot = (struct cgraph_node **) htab_find_slot (cgraph_hash, &key, INSERT);
 477
 478   if (*slot)
 479     {
 480       node = *slot;
 481       if (node->same_body_alias)
 482         node = node->same_body;
 483       return node;
 484     }
 485
 486   node = cgraph_create_node ();
 487   node->decl = decl;
 488   *slot = node;
 489   if (DECL_CONTEXT (decl) && TREE_CODE (DECL_CONTEXT (decl)) == FUNCTION_DECL)
 490     {
 491       node->origin = cgraph_node (DECL_CONTEXT (decl));
 492       node->next_nested = node->origin->nested;
 493       node->origin->nested = node;
 494     }
 495   if (assembler_name_hash)
 496     {
 497       void **aslot;
 498       tree name = DECL_ASSEMBLER_NAME (decl);
 499
 500       aslot = htab_find_slot_with_hash (assembler_name_hash, name,
 501                                         decl_assembler_name_hash (name),
 502                                         INSERT);
 503       /* We can have multiple declarations with same assembler name. For C++
 504          it is __builtin_strlen and strlen, for instance.  Do we need to
 505          record them all?  Original implementation marked just first one
 506          so lets hope for the best.  */
 507       if (*aslot == NULL)
 508         *aslot = node;
 509     }
 510   return node;
 511 }
 512
 513 /* Mark ALIAS as an alias to DECL.  */
 514
 515 static struct cgraph_node *
 516 cgraph_same_body_alias_1 (tree alias, tree decl)
 517 {
 518   struct cgraph_node key, *alias_node, *decl_node, **slot;
 519
 520   gcc_assert (TREE_CODE (decl) == FUNCTION_DECL);
 521   gcc_assert (TREE_CODE (alias) == FUNCTION_DECL);
 522   decl_node = cgraph_node (decl);
 523
 524   key.decl = alias;
 525
 526   slot = (struct cgraph_node **) htab_find_slot (cgraph_hash, &key, INSERT);
 527
 528   /* If the cgraph_node has been already created, fail.  */
 529   if (*slot)
 530     return NULL;
 531
 532   alias_node = cgraph_allocate_node ();
 533   alias_node->decl = alias;
 534   alias_node->same_body_alias = 1;
 535   alias_node->same_body = decl_node;
 536   alias_node->previous = NULL;
 537   if (decl_node->same_body)
 538     decl_node->same_body->previous = alias_node;
 539   alias_node->next = decl_node->same_body;
 540   alias_node->thunk.alias = decl;
 541   decl_node->same_body = alias_node;
 542   *slot = alias_node;
 543   return alias_node;
 544 }
 545
 546 /* Attempt to mark ALIAS as an alias to DECL.  Return TRUE if successful.
 547    Same body aliases are output whenever the body of DECL is output,
 548    and cgraph_node (ALIAS) transparently returns cgraph_node (DECL).   */
 549
 550 bool
 551 cgraph_same_body_alias (tree alias, tree decl)
 552 {
 553 #ifndef ASM_OUTPUT_DEF
 554   /* If aliases aren't supported by the assembler, fail.  */
 555   return false;
 556 #endif
 557
 558   /*gcc_assert (!assembler_name_hash);*/
 559
 560   return cgraph_same_body_alias_1 (alias, decl) != NULL;
 561 }
 562
 563 void
 564 cgraph_add_thunk (tree alias, tree decl, bool this_adjusting,
 565                   HOST_WIDE_INT fixed_offset, HOST_WIDE_INT virtual_value,
 566                   tree virtual_offset,
 567                   tree real_alias)
 568 {
 569   struct cgraph_node *node = cgraph_get_node (alias);
 570
 571   if (node)
 572     {
 573       gcc_assert (node->local.finalized);
 574       gcc_assert (!node->same_body);
 575       cgraph_remove_node (node);
 576     }
 577
 578   node = cgraph_same_body_alias_1 (alias, decl);
 579   gcc_assert (node);
 580 #ifdef ENABLE_CHECKING
 581   gcc_assert (!virtual_offset
 582               || tree_int_cst_equal (virtual_offset, size_int (virtual_value)));
 583 #endif
 584   node->thunk.fixed_offset = fixed_offset;
 585   node->thunk.this_adjusting = this_adjusting;
 586   node->thunk.virtual_value = virtual_value;
 587   node->thunk.virtual_offset_p = virtual_offset != NULL;
 588   node->thunk.alias = real_alias;
 589   node->thunk.thunk_p = true;
 590 }
 591
 592 /* Returns the cgraph node assigned to DECL or NULL if no cgraph node
 593    is assigned.  */
 594
 595 struct cgraph_node *
 596 cgraph_get_node (tree decl)
 597 {
 598   struct cgraph_node key, *node = NULL, **slot;
 599
 600   gcc_assert (TREE_CODE (decl) == FUNCTION_DECL);
 601
 602   if (!cgraph_hash)
 603     return NULL;
 604
 605   key.decl = decl;
 606
 607   slot = (struct cgraph_node **) htab_find_slot (cgraph_hash, &key,
 608                                                  NO_INSERT);
 609
 610   if (slot && *slot)
 611     {
 612       node = *slot;
 613       if (node->same_body_alias)
 614         node = node->same_body;
 615     }
 616   return node;
 617 }
 618
 619 /* Insert already constructed node into hashtable.  */
 620
 621 void
 622 cgraph_insert_node_to_hashtable (struct cgraph_node *node)
 623 {
 624   struct cgraph_node **slot;
 625
 626   slot = (struct cgraph_node **) htab_find_slot (cgraph_hash, node, INSERT);
 627
 628   gcc_assert (!*slot);
 629   *slot = node;
 630 }
 631
 632 /* Returns a hash code for P.  */
 633
 634 static hashval_t
 635 hash_node_by_assembler_name (const void *p)
 636 {
 637   const struct cgraph_node *n = (const struct cgraph_node *) p;
 638   return (hashval_t) decl_assembler_name_hash (DECL_ASSEMBLER_NAME (n->decl));
 639 }
 640
 641 /* Returns nonzero if P1 and P2 are equal.  */
 642
 643 static int
 644 eq_assembler_name (const void *p1, const void *p2)
 645 {
 646   const struct cgraph_node *n1 = (const struct cgraph_node *) p1;
 647   const_tree name = (const_tree)p2;
 648   return (decl_assembler_name_equal (n1->decl, name));
 649 }
 650
 651 /* Return the cgraph node that has ASMNAME for its DECL_ASSEMBLER_NAME.
 652    Return NULL if there's no such node.  */
 653
 654 struct cgraph_node *
 655 cgraph_node_for_asm (tree asmname)
 656 {
 657   struct cgraph_node *node;
 658   void **slot;
 659
 660   if (!assembler_name_hash)
 661     {
 662       assembler_name_hash =
 663         htab_create_ggc (10, hash_node_by_assembler_name, eq_assembler_name,
 664                          NULL);
 665       for (node = cgraph_nodes; node; node = node->next)
 666         if (!node->global.inlined_to)
 667           {
 668             tree name = DECL_ASSEMBLER_NAME (node->decl);
 669             slot = htab_find_slot_with_hash (assembler_name_hash, name,
 670                                              decl_assembler_name_hash (name),
 671                                              INSERT);
 672             /* We can have multiple declarations with same assembler name. For C++
 673                it is __builtin_strlen and strlen, for instance.  Do we need to
 674                record them all?  Original implementation marked just first one
 675                so lets hope for the best.  */
 676             if (!*slot)
 677               *slot = node;
 678             if (node->same_body)
 679               {
 680                 struct cgraph_node *alias;
 681
 682                 for (alias = node->same_body; alias; alias = alias->next)
 683                   {
 684                     hashval_t hash;
 685                     name = DECL_ASSEMBLER_NAME (alias->decl);
 686                     hash = decl_assembler_name_hash (name);
 687                     slot = htab_find_slot_with_hash (assembler_name_hash, name,
 688                                                      hash,  INSERT);
 689                     if (!*slot)
 690                       *slot = alias;
 691                   }
 692               }
 693           }
 694     }
 695
 696   slot = htab_find_slot_with_hash (assembler_name_hash, asmname,
 697                                    decl_assembler_name_hash (asmname),
 698                                    NO_INSERT);
 699
 700   if (slot)
 701     {
 702       node = (struct cgraph_node *) *slot;
 703       if (node->same_body_alias)
 704         node = node->same_body;
 705       return node;
 706     }
 707   return NULL;
 708 }
 709
 710 /* Returns a hash value for X (which really is a die_struct).  */
 711
 712 static hashval_t
 713 edge_hash (const void *x)
 714 {
 715   return htab_hash_pointer (((const struct cgraph_edge *) x)->call_stmt);
 716 }
 717
 718 /* Return nonzero if decl_id of die_struct X is the same as UID of decl *Y.  */
 719
 720 static int
 721 edge_eq (const void *x, const void *y)
 722 {
 723   return ((const struct cgraph_edge *) x)->call_stmt == y;
 724 }
 725
 726
 727 /* Return the callgraph edge representing the GIMPLE_CALL statement
 728    CALL_STMT.  */
 729
 730 struct cgraph_edge *
 731 cgraph_edge (struct cgraph_node *node, gimple call_stmt)
 732 {
 733   struct cgraph_edge *e, *e2;
 734   int n = 0;
 735
 736   if (node->call_site_hash)
 737     return (struct cgraph_edge *)
 738       htab_find_with_hash (node->call_site_hash, call_stmt,
 739                            htab_hash_pointer (call_stmt));
 740
 741   /* This loop may turn out to be performance problem.  In such case adding
 742      hashtables into call nodes with very many edges is probably best
 743      solution.  It is not good idea to add pointer into CALL_EXPR itself
 744      because we want to make possible having multiple cgraph nodes representing
 745      different clones of the same body before the body is actually cloned.  */
 746   for (e = node->callees; e; e= e->next_callee)
 747     {
 748       if (e->call_stmt == call_stmt)
 749         break;
 750       n++;
 751     }
 752
 753   if (n > 100)
 754     {
 755       node->call_site_hash = htab_create_ggc (120, edge_hash, edge_eq, NULL);
 756       for (e2 = node->callees; e2; e2 = e2->next_callee)
 757         {
 758           void **slot;
 759           slot = htab_find_slot_with_hash (node->call_site_hash,
 760                                            e2->call_stmt,
 761                                            htab_hash_pointer (e2->call_stmt),
 762                                            INSERT);
 763           gcc_assert (!*slot);
 764           *slot = e2;
 765         }
 766     }
 767
 768   return e;
 769 }
 770
 771
 772 /* Change field call_stmt of edge E to NEW_STMT.  */
 773
 774 void
 775 cgraph_set_call_stmt (struct cgraph_edge *e, gimple new_stmt)
 776 {
 777   if (e->caller->call_site_hash)
 778     {
 779       htab_remove_elt_with_hash (e->caller->call_site_hash,
 780                                  e->call_stmt,
 781                                  htab_hash_pointer (e->call_stmt));
 782     }
 783   e->call_stmt = new_stmt;
 784   push_cfun (DECL_STRUCT_FUNCTION (e->caller->decl));
 785   e->can_throw_external = stmt_can_throw_external (new_stmt);
 786   pop_cfun ();
 787   if (e->caller->call_site_hash)
 788     {
 789       void **slot;
 790       slot = htab_find_slot_with_hash (e->caller->call_site_hash,
 791                                        e->call_stmt,
 792                                        htab_hash_pointer
 793                                        (e->call_stmt), INSERT);
 794       gcc_assert (!*slot);
 795       *slot = e;
 796     }
 797 }
 798
 799 /* Like cgraph_set_call_stmt but walk the clone tree and update all
 800    clones sharing the same function body.  */
 801
 802 void
 803 cgraph_set_call_stmt_including_clones (struct cgraph_node *orig,
 804                                        gimple old_stmt, gimple new_stmt)
 805 {
 806   struct cgraph_node *node;
 807   struct cgraph_edge *edge = cgraph_edge (orig, old_stmt);
 808
 809   if (edge)
 810     cgraph_set_call_stmt (edge, new_stmt);
 811
 812   node = orig->clones;
 813   if (node)
 814     while (node != orig)
 815       {
 816         struct cgraph_edge *edge = cgraph_edge (node, old_stmt);
 817         if (edge)
 818           cgraph_set_call_stmt (edge, new_stmt);
 819         if (node->clones)
 820           node = node->clones;
 821         else if (node->next_sibling_clone)
 822           node = node->next_sibling_clone;
 823         else
 824           {
 825             while (node != orig && !node->next_sibling_clone)
 826               node = node->clone_of;
 827             if (node != orig)
 828               node = node->next_sibling_clone;
 829           }
 830       }
 831 }
 832
 833 /* Like cgraph_create_edge walk the clone tree and update all clones sharing
 834    same function body.  If clones already have edge for OLD_STMT; only
 835    update the edge same way as cgraph_set_call_stmt_including_clones does.
 836
 837    TODO: COUNT and LOOP_DEPTH should be properly distributed based on relative
 838    frequencies of the clones.  */
 839
 840 void
 841 cgraph_create_edge_including_clones (struct cgraph_node *orig,
 842                                      struct cgraph_node *callee,
 843                                      gimple old_stmt,
 844                                      gimple stmt, gcov_type count,
 845                                      int freq, int loop_depth,
 846                                      cgraph_inline_failed_t reason)
 847 {
 848   struct cgraph_node *node;
 849   struct cgraph_edge *edge;
 850
 851   if (!cgraph_edge (orig, stmt))
 852     {
 853       edge = cgraph_create_edge (orig, callee, stmt, count, freq, loop_depth);
 854       edge->inline_failed = reason;
 855     }
 856
 857   node = orig->clones;
 858   if (node)
 859     while (node != orig)
 860       {
 861         struct cgraph_edge *edge = cgraph_edge (node, old_stmt);
 862
 863         /* It is possible that clones already contain the edge while
 864            master didn't.  Either we promoted indirect call into direct
 865            call in the clone or we are processing clones of unreachable
 866            master where edges has been rmeoved.  */
 867         if (edge)
 868           cgraph_set_call_stmt (edge, stmt);
 869         else if (!cgraph_edge (node, stmt))
 870           {
 871             edge = cgraph_create_edge (node, callee, stmt, count,
 872                                        freq, loop_depth);
 873             edge->inline_failed = reason;
 874           }
 875
 876         if (node->clones)
 877           node = node->clones;
 878         else if (node->next_sibling_clone)
 879           node = node->next_sibling_clone;
 880         else
 881           {
 882             while (node != orig && !node->next_sibling_clone)
 883               node = node->clone_of;
 884             if (node != orig)
 885               node = node->next_sibling_clone;
 886           }
 887       }
 888 }
 889
 890 /* Give initial reasons why inlining would fail on EDGE.  This gets either
 891    nullified or usually overwritten by more precise reasons later.  */
 892
 893 static void
 894 initialize_inline_failed (struct cgraph_edge *e)
 895 {
 896   struct cgraph_node *callee = e->callee;
 897
 898   if (!callee->analyzed)
 899     e->inline_failed = CIF_BODY_NOT_AVAILABLE;
 900   else if (callee->local.redefined_extern_inline)
 901     e->inline_failed = CIF_REDEFINED_EXTERN_INLINE;
 902   else if (!callee->local.inlinable)
 903     e->inline_failed = CIF_FUNCTION_NOT_INLINABLE;
 904   else if (e->call_stmt && gimple_call_cannot_inline_p (e->call_stmt))
 905     e->inline_failed = CIF_MISMATCHED_ARGUMENTS;
 906   else
 907     e->inline_failed = CIF_FUNCTION_NOT_CONSIDERED;
 908 }
 909
 910 /* Create edge from CALLER to CALLEE in the cgraph.  */
 911
 912 struct cgraph_edge *
 913 cgraph_create_edge (struct cgraph_node *caller, struct cgraph_node *callee,
 914                     gimple call_stmt, gcov_type count, int freq, int nest)
 915 {
 916   struct cgraph_edge *edge;
 917
 918
 919   /* LTO does not actually have access to the call_stmt since these
 920      have not been loaded yet.  */
 921   if (call_stmt)
 922     {
 923 #ifdef ENABLE_CHECKING
 924       /* This is rather pricely check possibly trigerring construction of
 925          call stmt hashtable.  */
 926       gcc_assert (!cgraph_edge (caller, call_stmt));
 927 #endif
 928
 929       gcc_assert (is_gimple_call (call_stmt));
 930     }
 931
 932   if (free_edges)
 933     {
 934       edge = free_edges;
 935       free_edges = NEXT_FREE_EDGE (edge);
 936     }
 937   else
 938     {
 939       edge = GGC_NEW (struct cgraph_edge);
 940       edge->uid = cgraph_edge_max_uid++;
 941     }
 942
 943   edge->aux = NULL;
 944
 945   edge->caller = caller;
 946   edge->callee = callee;
 947   edge->call_stmt = call_stmt;
 948   push_cfun (DECL_STRUCT_FUNCTION (caller->decl));
 949   edge->can_throw_external
 950     = call_stmt ? stmt_can_throw_external (call_stmt) : false;
 951   pop_cfun ();
 952   edge->prev_caller = NULL;
 953   edge->next_caller = callee->callers;
 954   if (callee->callers)
 955     callee->callers->prev_caller = edge;
 956   edge->prev_callee = NULL;
 957   edge->next_callee = caller->callees;
 958   if (caller->callees)
 959     caller->callees->prev_callee = edge;
 960   caller->callees = edge;
 961   callee->callers = edge;
 962   edge->count = count;
 963   gcc_assert (count >= 0);
 964   edge->frequency = freq;
 965   gcc_assert (freq >= 0);
 966   gcc_assert (freq <= CGRAPH_FREQ_MAX);
 967   edge->loop_nest = nest;
 968   edge->indirect_call = 0;
 969   edge->call_stmt_cannot_inline_p =
 970     (call_stmt ? gimple_call_cannot_inline_p (call_stmt) : false);
 971   if (call_stmt && caller->call_site_hash)
 972     {
 973       void **slot;
 974       slot = htab_find_slot_with_hash (caller->call_site_hash,
 975                                        edge->call_stmt,
 976                                        htab_hash_pointer
 977                                          (edge->call_stmt),
 978                                        INSERT);
 979       gcc_assert (!*slot);
 980       *slot = edge;
 981     }
 982
 983   initialize_inline_failed (edge);
 984
 985   return edge;
 986 }
 987
 988 /* Remove the edge E from the list of the callers of the callee.  */
 989
 990 static inline void
 991 cgraph_edge_remove_callee (struct cgraph_edge *e)
 992 {
 993   if (e->prev_caller)
 994     e->prev_caller->next_caller = e->next_caller;
 995   if (e->next_caller)
 996     e->next_caller->prev_caller = e->prev_caller;
 997   if (!e->prev_caller)
 998     e->callee->callers = e->next_caller;
 999 }
1000
1001 /* Remove the edge E from the list of the callees of the caller.  */
1002
1003 static inline void
1004 cgraph_edge_remove_caller (struct cgraph_edge *e)
1005 {
1006   if (e->prev_callee)
1007     e->prev_callee->next_callee = e->next_callee;
1008   if (e->next_callee)
1009     e->next_callee->prev_callee = e->prev_callee;
1010   if (!e->prev_callee)
1011     e->caller->callees = e->next_callee;
1012   if (e->caller->call_site_hash)
1013     htab_remove_elt_with_hash (e->caller->call_site_hash,
1014                                e->call_stmt,
1015                                htab_hash_pointer (e->call_stmt));
1016 }
1017
1018 /* Put the edge onto the free list.  */
1019
1020 static void
1021 cgraph_free_edge (struct cgraph_edge *e)
1022 {
1023   int uid = e->uid;
1024
1025   /* Clear out the edge so we do not dangle pointers.  */
1026   memset (e, 0, sizeof (*e));
1027   e->uid = uid;
1028   NEXT_FREE_EDGE (e) = free_edges;
1029   free_edges = e;
1030 }
1031
1032 /* Remove the edge E in the cgraph.  */
1033
1034 void
1035 cgraph_remove_edge (struct cgraph_edge *e)
1036 {
1037   /* Call all edge removal hooks.  */
1038   cgraph_call_edge_removal_hooks (e);
1039
1040   /* Remove from callers list of the callee.  */
1041   cgraph_edge_remove_callee (e);
1042
1043   /* Remove from callees list of the callers.  */
1044   cgraph_edge_remove_caller (e);
1045
1046   /* Put the edge onto the free list.  */
1047   cgraph_free_edge (e);
1048 }
1049
1050 /* Redirect callee of E to N.  The function does not update underlying
1051    call expression.  */
1052
1053 void
1054 cgraph_redirect_edge_callee (struct cgraph_edge *e, struct cgraph_node *n)
1055 {
1056   /* Remove from callers list of the current callee.  */
1057   cgraph_edge_remove_callee (e);
1058
1059   /* Insert to callers list of the new callee.  */
1060   e->prev_caller = NULL;
1061   if (n->callers)
1062     n->callers->prev_caller = e;
1063   e->next_caller = n->callers;
1064   n->callers = e;
1065   e->callee = n;
1066 }
1067
1068
1069 /* Update or remove the corresponding cgraph edge if a GIMPLE_CALL
1070    OLD_STMT changed into NEW_STMT.  OLD_CALL is gimple_call_fndecl
1071    of OLD_STMT if it was previously call statement.  */
1072
1073 static void
1074 cgraph_update_edges_for_call_stmt_node (struct cgraph_node *node,
1075                                         gimple old_stmt, tree old_call, gimple new_stmt)
1076 {
1077   tree new_call = (is_gimple_call (new_stmt)) ? gimple_call_fndecl (new_stmt) : 0;
1078
1079   /* We are seeing indirect calls, then there is nothing to update.  */
1080   if (!new_call && !old_call)
1081     return;
1082   /* See if we turned indirect call into direct call or folded call to one builtin
1083      into different bultin.  */
1084   if (old_call != new_call)
1085     {
1086       struct cgraph_edge *e = cgraph_edge (node, old_stmt);
1087       struct cgraph_edge *ne = NULL;
1088       gcov_type count;
1089       int frequency;
1090       int loop_nest;
1091
1092       if (e)
1093         {
1094           /* See if the call is already there.  It might be because of indirect
1095              inlining already found it.  */
1096           if (new_call && e->callee->decl == new_call)
1097             return;
1098
1099           /* Otherwise remove edge and create new one; we can't simply redirect
1100              since function has changed, so inline plan and other information
1101              attached to edge is invalid.  */
1102           count = e->count;
1103           frequency = e->frequency;
1104           loop_nest = e->loop_nest;
1105           cgraph_remove_edge (e);
1106         }
1107       else
1108         {
1109           /* We are seeing new direct call; compute profile info based on BB.  */
1110           basic_block bb = gimple_bb (new_stmt);
1111           count = bb->count;
1112           frequency = compute_call_stmt_bb_frequency (current_function_decl,
1113                                                       bb);
1114           loop_nest = bb->loop_depth;
1115         }
1116
1117       if (new_call)
1118         {
1119           ne = cgraph_create_edge (node, cgraph_node (new_call),
1120                                    new_stmt, count, frequency,
1121                                    loop_nest);
1122           gcc_assert (ne->inline_failed);
1123         }
1124     }
1125   /* We only updated the call stmt; update pointer in cgraph edge..  */
1126   else if (old_stmt != new_stmt)
1127     cgraph_set_call_stmt (cgraph_edge (node, old_stmt), new_stmt);
1128 }
1129
1130 /* Update or remove the corresponding cgraph edge if a GIMPLE_CALL
1131    OLD_STMT changed into NEW_STMT.  OLD_DECL is gimple_call_fndecl
1132    of OLD_STMT before it was updated (updating can happen inplace).  */
1133
1134 void
1135 cgraph_update_edges_for_call_stmt (gimple old_stmt, tree old_decl, gimple new_stmt)
1136 {
1137   struct cgraph_node *orig = cgraph_node (cfun->decl);
1138   struct cgraph_node *node;
1139
1140   cgraph_update_edges_for_call_stmt_node (orig, old_stmt, old_decl, new_stmt);
1141   if (orig->clones)
1142     for (node = orig->clones; node != orig;)
1143       {
1144         cgraph_update_edges_for_call_stmt_node (node, old_stmt, old_decl, new_stmt);
1145         if (node->clones)
1146           node = node->clones;
1147         else if (node->next_sibling_clone)
1148           node = node->next_sibling_clone;
1149         else
1150           {
1151             while (node != orig && !node->next_sibling_clone)
1152               node = node->clone_of;
1153             if (node != orig)
1154               node = node->next_sibling_clone;
1155           }
1156       }
1157 }
1158
1159
1160 /* Remove all callees from the node.  */
1161
1162 void
1163 cgraph_node_remove_callees (struct cgraph_node *node)
1164 {
1165   struct cgraph_edge *e, *f;
1166
1167   /* It is sufficient to remove the edges from the lists of callers of
1168      the callees.  The callee list of the node can be zapped with one
1169      assignment.  */
1170   for (e = node->callees; e; e = f)
1171     {
1172       f = e->next_callee;
1173       cgraph_call_edge_removal_hooks (e);
1174       cgraph_edge_remove_callee (e);
1175       cgraph_free_edge (e);
1176     }
1177   node->callees = NULL;
1178   if (node->call_site_hash)
1179     {
1180       htab_delete (node->call_site_hash);
1181       node->call_site_hash = NULL;
1182     }
1183 }
1184
1185 /* Remove all callers from the node.  */
1186
1187 static void
1188 cgraph_node_remove_callers (struct cgraph_node *node)
1189 {
1190   struct cgraph_edge *e, *f;
1191
1192   /* It is sufficient to remove the edges from the lists of callees of
1193      the callers.  The caller list of the node can be zapped with one
1194      assignment.  */
1195   for (e = node->callers; e; e = f)
1196     {
1197       f = e->next_caller;
1198       cgraph_call_edge_removal_hooks (e);
1199       cgraph_edge_remove_caller (e);
1200       cgraph_free_edge (e);
1201     }
1202   node->callers = NULL;
1203 }
1204
1205 /* Release memory used to represent body of function NODE.  */
1206
1207 void
1208 cgraph_release_function_body (struct cgraph_node *node)
1209 {
1210   if (DECL_STRUCT_FUNCTION (node->decl))
1211     {
1212       tree old_decl = current_function_decl;
1213       push_cfun (DECL_STRUCT_FUNCTION (node->decl));
1214       if (cfun->gimple_df)
1215         {
1216           current_function_decl = node->decl;
1217           delete_tree_ssa ();
1218           delete_tree_cfg_annotations ();
1219           cfun->eh = NULL;
1220           current_function_decl = old_decl;
1221         }
1222       if (cfun->cfg)
1223         {
1224           gcc_assert (dom_computed[0] == DOM_NONE);
1225           gcc_assert (dom_computed[1] == DOM_NONE);
1226           clear_edges ();
1227         }
1228       if (cfun->value_histograms)
1229         free_histograms ();
1230       gcc_assert (!current_loops);
1231       pop_cfun();
1232       gimple_set_body (node->decl, NULL);
1233       VEC_free (ipa_opt_pass, heap,
1234                 node->ipa_transforms_to_apply);
1235       /* Struct function hangs a lot of data that would leak if we didn't
1236          removed all pointers to it.   */
1237       ggc_free (DECL_STRUCT_FUNCTION (node->decl));
1238       DECL_STRUCT_FUNCTION (node->decl) = NULL;
1239     }
1240   DECL_SAVED_TREE (node->decl) = NULL;
1241   /* If the node is abstract and needed, then do not clear DECL_INITIAL
1242      of its associated function function declaration because it's
1243      needed to emit debug info later.  */
1244   if (!node->abstract_and_needed)
1245     DECL_INITIAL (node->decl) = error_mark_node;
1246 }
1247
1248 /* Remove same body alias node.  */
1249
1250 void
1251 cgraph_remove_same_body_alias (struct cgraph_node *node)
1252 {
1253   void **slot;
1254   int uid = node->uid;
1255
1256   gcc_assert (node->same_body_alias);
1257   if (node->previous)
1258     node->previous->next = node->next;
1259   else
1260     node->same_body->same_body = node->next;
1261   if (node->next)
1262     node->next->previous = node->previous;
1263   node->next = NULL;
1264   node->previous = NULL;
1265   slot = htab_find_slot (cgraph_hash, node, NO_INSERT);
1266   if (*slot == node)
1267     htab_clear_slot (cgraph_hash, slot);
1268   if (assembler_name_hash)
1269     {
1270       tree name = DECL_ASSEMBLER_NAME (node->decl);
1271       slot = htab_find_slot_with_hash (assembler_name_hash, name,
1272                                        decl_assembler_name_hash (name),
1273                                        NO_INSERT);
1274       if (slot && *slot == node)
1275         htab_clear_slot (assembler_name_hash, slot);
1276     }
1277
1278   /* Clear out the node to NULL all pointers and add the node to the free
1279      list.  */
1280   memset (node, 0, sizeof(*node));
1281   node->uid = uid;
1282   NEXT_FREE_NODE (node) = free_nodes;
1283   free_nodes = node;
1284 }
1285
1286 /* Remove the node from cgraph.  */
1287
1288 void
1289 cgraph_remove_node (struct cgraph_node *node)
1290 {
1291   void **slot;
1292   bool kill_body = false;
1293   struct cgraph_node *n;
1294   int uid = node->uid;
1295
1296   cgraph_call_node_removal_hooks (node);
1297   cgraph_node_remove_callers (node);
1298   cgraph_node_remove_callees (node);
1299   VEC_free (ipa_opt_pass, heap,
1300             node->ipa_transforms_to_apply);
1301
1302   /* Incremental inlining access removed nodes stored in the postorder list.
1303      */
1304   node->needed = node->reachable = false;
1305   for (n = node->nested; n; n = n->next_nested)
1306     n->origin = NULL;
1307   node->nested = NULL;
1308   if (node->origin)
1309     {
1310       struct cgraph_node **node2 = &node->origin->nested;
1311
1312       while (*node2 != node)
1313         node2 = &(*node2)->next_nested;
1314       *node2 = node->next_nested;
1315     }
1316   if (node->previous)
1317     node->previous->next = node->next;
1318   else
1319     cgraph_nodes = node->next;
1320   if (node->next)
1321     node->next->previous = node->previous;
1322   node->next = NULL;
1323   node->previous = NULL;
1324   slot = htab_find_slot (cgraph_hash, node, NO_INSERT);
1325   if (*slot == node)
1326     {
1327       struct cgraph_node *next_inline_clone;
1328
1329       for (next_inline_clone = node->clones;
1330            next_inline_clone && next_inline_clone->decl != node->decl;
1331            next_inline_clone = next_inline_clone->next_sibling_clone)
1332         ;
1333
1334       /* If there is inline clone of the node being removed, we need
1335          to put it into the position of removed node and reorganize all
1336          other clones to be based on it.  */
1337       if (next_inline_clone)
1338         {
1339           struct cgraph_node *n;
1340           struct cgraph_node *new_clones;
1341
1342           *slot = next_inline_clone;
1343
1344           /* Unlink inline clone from the list of clones of removed node.  */
1345           if (next_inline_clone->next_sibling_clone)
1346             next_inline_clone->next_sibling_clone->prev_sibling_clone
1347               = next_inline_clone->prev_sibling_clone;
1348           if (next_inline_clone->prev_sibling_clone)
1349             {
1350               gcc_assert (node->clones != next_inline_clone);
1351               next_inline_clone->prev_sibling_clone->next_sibling_clone
1352                 = next_inline_clone->next_sibling_clone;
1353             }
1354           else
1355             {
1356               gcc_assert (node->clones == next_inline_clone);
1357               node->clones = next_inline_clone->next_sibling_clone;
1358             }
1359
1360           new_clones = node->clones;
1361           node->clones = NULL;
1362
1363           /* Copy clone info.  */
1364           next_inline_clone->clone = node->clone;
1365
1366           /* Now place it into clone tree at same level at NODE.  */
1367           next_inline_clone->clone_of = node->clone_of;
1368           next_inline_clone->prev_sibling_clone = NULL;
1369           next_inline_clone->next_sibling_clone = NULL;
1370           if (node->clone_of)
1371             {
1372               if (node->clone_of->clones)
1373                 node->clone_of->clones->prev_sibling_clone = next_inline_clone;
1374               next_inline_clone->next_sibling_clone = node->clone_of->clones;
1375               node->clone_of->clones = next_inline_clone;
1376             }
1377
1378           /* Merge the clone list.  */
1379           if (new_clones)
1380             {
1381               if (!next_inline_clone->clones)
1382                 next_inline_clone->clones = new_clones;
1383               else
1384                 {
1385                   n = next_inline_clone->clones;
1386                   while (n->next_sibling_clone)
1387                     n =  n->next_sibling_clone;
1388                   n->next_sibling_clone = new_clones;
1389                   new_clones->prev_sibling_clone = n;
1390                 }
1391             }
1392
1393           /* Update clone_of pointers.  */
1394           n = new_clones;
1395           while (n)
1396             {
1397               n->clone_of = next_inline_clone;
1398               n = n->next_sibling_clone;
1399             }
1400         }
1401       else
1402         {
1403           htab_clear_slot (cgraph_hash, slot);
1404           kill_body = true;
1405         }
1406
1407     }
1408   if (node->prev_sibling_clone)
1409     node->prev_sibling_clone->next_sibling_clone = node->next_sibling_clone;
1410   else if (node->clone_of)
1411     node->clone_of->clones = node->next_sibling_clone;
1412   if (node->next_sibling_clone)
1413     node->next_sibling_clone->prev_sibling_clone = node->prev_sibling_clone;
1414   if (node->clones)
1415     {
1416       struct cgraph_node *n, *next;
1417
1418       if (node->clone_of)
1419         {
1420           for (n = node->clones; n->next_sibling_clone; n = n->next_sibling_clone)
1421             n->clone_of = node->clone_of;
1422           n->clone_of = node->clone_of;
1423           n->next_sibling_clone = node->clone_of->clones;
1424           if (node->clone_of->clones)
1425             node->clone_of->clones->prev_sibling_clone = n;
1426           node->clone_of->clones = node->clones;
1427         }
1428       else
1429         {
1430           /* We are removing node with clones.  this makes clones inconsistent,
1431              but assume they will be removed subsequently and just keep clone
1432              tree intact.  This can happen in unreachable function removal since
1433              we remove unreachable functions in random order, not by bottom-up
1434              walk of clone trees.  */
1435           for (n = node->clones; n; n = next)
1436             {
1437                next = n->next_sibling_clone;
1438                n->next_sibling_clone = NULL;
1439                n->prev_sibling_clone = NULL;
1440                n->clone_of = NULL;
1441             }
1442         }
1443     }
1444
1445   while (node->same_body)
1446     cgraph_remove_same_body_alias (node->same_body);
1447
1448   if (node->same_comdat_group)
1449     {
1450       struct cgraph_node *prev;
1451       for (prev = node->same_comdat_group;
1452            prev->same_comdat_group != node;
1453            prev = prev->same_comdat_group)
1454         ;
1455       if (node->same_comdat_group == prev)
1456         prev->same_comdat_group = NULL;
1457       else
1458         prev->same_comdat_group = node->same_comdat_group;
1459       node->same_comdat_group = NULL;
1460     }
1461
1462   /* While all the clones are removed after being proceeded, the function
1463      itself is kept in the cgraph even after it is compiled.  Check whether
1464      we are done with this body and reclaim it proactively if this is the case.
1465      */
1466   if (!kill_body && *slot)
1467     {
1468       struct cgraph_node *n = (struct cgraph_node *) *slot;
1469       if (!n->clones && !n->clone_of && !n->global.inlined_to
1470           && (cgraph_global_info_ready
1471               && (TREE_ASM_WRITTEN (n->decl) || DECL_EXTERNAL (n->decl)
1472                   || n->in_other_partition)))
1473         kill_body = true;
1474     }
1475   if (assembler_name_hash)
1476     {
1477       tree name = DECL_ASSEMBLER_NAME (node->decl);
1478       slot = htab_find_slot_with_hash (assembler_name_hash, name,
1479                                        decl_assembler_name_hash (name),
1480                                        NO_INSERT);
1481       /* Inline clones are not hashed.  */
1482       if (slot && *slot == node)
1483         htab_clear_slot (assembler_name_hash, slot);
1484     }
1485
1486   if (kill_body)
1487     cgraph_release_function_body (node);
1488   node->decl = NULL;
1489   if (node->call_site_hash)
1490     {
1491       htab_delete (node->call_site_hash);
1492       node->call_site_hash = NULL;
1493     }
1494   cgraph_n_nodes--;
1495
1496   /* Clear out the node to NULL all pointers and add the node to the free
1497      list.  */
1498   memset (node, 0, sizeof(*node));
1499   node->uid = uid;
1500   NEXT_FREE_NODE (node) = free_nodes;
1501   free_nodes = node;
1502 }
1503
1504 /* Remove the node from cgraph.  */
1505
1506 void
1507 cgraph_remove_node_and_inline_clones (struct cgraph_node *node)
1508 {
1509   struct cgraph_edge *e, *next;
1510   for (e = node->callees; e; e = next)
1511     {
1512       next = e->next_callee;
1513       if (!e->inline_failed)
1514         cgraph_remove_node_and_inline_clones (e->callee);
1515     }
1516   cgraph_remove_node (node);
1517 }
1518
1519 /* Notify finalize_compilation_unit that given node is reachable.  */
1520
1521 void
1522 cgraph_mark_reachable_node (struct cgraph_node *node)
1523 {
1524   if (!node->reachable && node->local.finalized)
1525     {
1526       notice_global_symbol (node->decl);
1527       node->reachable = 1;
1528       gcc_assert (!cgraph_global_info_ready);
1529
1530       node->next_needed = cgraph_nodes_queue;
1531       cgraph_nodes_queue = node;
1532     }
1533 }
1534
1535 /* Likewise indicate that a node is needed, i.e. reachable via some
1536    external means.  */
1537
1538 void
1539 cgraph_mark_needed_node (struct cgraph_node *node)
1540 {
1541   node->needed = 1;
1542   gcc_assert (!node->global.inlined_to);
1543   cgraph_mark_reachable_node (node);
1544 }
1545
1546 /* Likewise indicate that a node is having address taken.  */
1547
1548 void
1549 cgraph_mark_address_taken_node (struct cgraph_node *node)
1550 {
1551   node->address_taken = 1;
1552   cgraph_mark_needed_node (node);
1553 }
1554
1555 /* Return local info for the compiled function.  */
1556
1557 struct cgraph_local_info *
1558 cgraph_local_info (tree decl)
1559 {
1560   struct cgraph_node *node;
1561
1562   gcc_assert (TREE_CODE (decl) == FUNCTION_DECL);
1563   node = cgraph_node (decl);
1564   return &node->local;
1565 }
1566
1567 /* Return local info for the compiled function.  */
1568
1569 struct cgraph_global_info *
1570 cgraph_global_info (tree decl)
1571 {
1572   struct cgraph_node *node;
1573
1574   gcc_assert (TREE_CODE (decl) == FUNCTION_DECL && cgraph_global_info_ready);
1575   node = cgraph_node (decl);
1576   return &node->global;
1577 }
1578
1579 /* Return local info for the compiled function.  */
1580
1581 struct cgraph_rtl_info *
1582 cgraph_rtl_info (tree decl)
1583 {
1584   struct cgraph_node *node;
1585
1586   gcc_assert (TREE_CODE (decl) == FUNCTION_DECL);
1587   node = cgraph_node (decl);
1588   if (decl != current_function_decl
1589       && !TREE_ASM_WRITTEN (node->decl))
1590     return NULL;
1591   return &node->rtl;
1592 }
1593
1594 /* Return a string describing the failure REASON.  */
1595
1596 const char*
1597 cgraph_inline_failed_string (cgraph_inline_failed_t reason)
1598 {
1599 #undef DEFCIFCODE
1600 #define DEFCIFCODE(code, string)        string,
1601
1602   static const char *cif_string_table[CIF_N_REASONS] = {
1603 #include "cif-code.def"
1604   };
1605
1606   /* Signedness of an enum type is implementation defined, so cast it
1607      to unsigned before testing. */
1608   gcc_assert ((unsigned) reason < CIF_N_REASONS);
1609   return cif_string_table[reason];
1610 }
1611
1612 /* Return name of the node used in debug output.  */
1613 const char *
1614 cgraph_node_name (struct cgraph_node *node)
1615 {
1616   return lang_hooks.decl_printable_name (node->decl, 2);
1617 }
1618
1619 /* Names used to print out the availability enum.  */
1620 const char * const cgraph_availability_names[] =
1621   {"unset", "not_available", "overwritable", "available", "local"};
1622
1623
1624 /* Dump call graph node NODE to file F.  */
1625
1626 void
1627 dump_cgraph_node (FILE *f, struct cgraph_node *node)
1628 {
1629   struct cgraph_edge *edge;
1630   fprintf (f, "%s/%i(%i)", cgraph_node_name (node), node->uid,
1631            node->pid);
1632   dump_addr (f, " @", (void *)node);
1633   if (DECL_ASSEMBLER_NAME_SET_P (node->decl))
1634     fprintf (f, " (asm: %s)", IDENTIFIER_POINTER (DECL_ASSEMBLER_NAME (node->decl)));
1635   if (node->global.inlined_to)
1636     fprintf (f, " (inline copy in %s/%i)",
1637              cgraph_node_name (node->global.inlined_to),
1638              node->global.inlined_to->uid);
1639   if (node->clone_of)
1640     fprintf (f, " (clone of %s/%i)",
1641              cgraph_node_name (node->clone_of),
1642              node->clone_of->uid);
1643   if (cgraph_function_flags_ready)
1644     fprintf (f, " availability:%s",
1645              cgraph_availability_names [cgraph_function_body_availability (node)]);
1646   if (node->analyzed)
1647     fprintf (f, " analyzed");
1648   if (node->in_other_partition)
1649     fprintf (f, " in_other_partition");
1650   if (node->count)
1651     fprintf (f, " executed "HOST_WIDEST_INT_PRINT_DEC"x",
1652              (HOST_WIDEST_INT)node->count);
1653   if (node->local.inline_summary.self_time)
1654     fprintf (f, " %i time, %i benefit", node->local.inline_summary.self_time,
1655                                         node->local.inline_summary.time_inlining_benefit);
1656   if (node->global.time && node->global.time
1657       != node->local.inline_summary.self_time)
1658     fprintf (f, " (%i after inlining)", node->global.time);
1659   if (node->local.inline_summary.self_size)
1660     fprintf (f, " %i size, %i benefit", node->local.inline_summary.self_size,
1661                                         node->local.inline_summary.size_inlining_benefit);
1662   if (node->global.size && node->global.size
1663       != node->local.inline_summary.self_size)
1664     fprintf (f, " (%i after inlining)", node->global.size);
1665   if (node->local.inline_summary.estimated_self_stack_size)
1666     fprintf (f, " %i bytes stack usage", (int)node->local.inline_summary.estimated_self_stack_size);
1667   if (node->global.estimated_stack_size != node->local.inline_summary.estimated_self_stack_size)
1668     fprintf (f, " %i bytes after inlining", (int)node->global.estimated_stack_size);
1669   if (node->origin)
1670     fprintf (f, " nested in: %s", cgraph_node_name (node->origin));
1671   if (node->needed)
1672     fprintf (f, " needed");
1673   if (node->address_taken)
1674     fprintf (f, " address_taken");
1675   else if (node->reachable)
1676     fprintf (f, " reachable");
1677   else if (node->reachable_from_other_partition)
1678     fprintf (f, " reachable_from_other_partition");
1679   if (gimple_has_body_p (node->decl))
1680     fprintf (f, " body");
1681   if (node->process)
1682     fprintf (f, " process");
1683   if (node->local.local)
1684     fprintf (f, " local");
1685   if (node->local.externally_visible)
1686     fprintf (f, " externally_visible");
1687   if (node->local.finalized)
1688     fprintf (f, " finalized");
1689   if (node->local.disregard_inline_limits)
1690     fprintf (f, " always_inline");
1691   else if (node->local.inlinable)
1692     fprintf (f, " inlinable");
1693   if (node->local.redefined_extern_inline)
1694     fprintf (f, " redefined_extern_inline");
1695   if (TREE_ASM_WRITTEN (node->decl))
1696     fprintf (f, " asm_written");
1697
1698   fprintf (f, "\n  called by: ");
1699   for (edge = node->callers; edge; edge = edge->next_caller)
1700     {
1701       fprintf (f, "%s/%i ", cgraph_node_name (edge->caller),
1702                edge->caller->uid);
1703       if (edge->count)
1704         fprintf (f, "("HOST_WIDEST_INT_PRINT_DEC"x) ",
1705                  (HOST_WIDEST_INT)edge->count);
1706       if (edge->frequency)
1707         fprintf (f, "(%.2f per call) ",
1708                  edge->frequency / (double)CGRAPH_FREQ_BASE);
1709       if (!edge->inline_failed)
1710         fprintf(f, "(inlined) ");
1711       if (edge->indirect_call)
1712         fprintf(f, "(indirect) ");
1713       if (edge->can_throw_external)
1714         fprintf(f, "(can throw external) ");
1715     }
1716
1717   fprintf (f, "\n  calls: ");
1718   for (edge = node->callees; edge; edge = edge->next_callee)
1719     {
1720       fprintf (f, "%s/%i ", cgraph_node_name (edge->callee),
1721                edge->callee->uid);
1722       if (!edge->inline_failed)
1723         fprintf(f, "(inlined) ");
1724       if (edge->indirect_call)
1725         fprintf(f, "(indirect) ");
1726       if (edge->count)
1727         fprintf (f, "("HOST_WIDEST_INT_PRINT_DEC"x) ",
1728                  (HOST_WIDEST_INT)edge->count);
1729       if (edge->frequency)
1730         fprintf (f, "(%.2f per call) ",
1731                  edge->frequency / (double)CGRAPH_FREQ_BASE);
1732       if (edge->loop_nest)
1733         fprintf (f, "(nested in %i loops) ", edge->loop_nest);
1734       if (edge->can_throw_external)
1735         fprintf(f, "(can throw external) ");
1736     }
1737   fprintf (f, "\n");
1738
1739   if (node->same_body)
1740     {
1741       struct cgraph_node *n;
1742       fprintf (f, "  aliases & thunks:");
1743       for (n = node->same_body; n; n = n->next)
1744         {
1745           fprintf (f, " %s/%i", cgraph_node_name (n), n->uid);
1746           if (n->thunk.thunk_p)
1747             {
1748               fprintf (f, " (thunk of %s fixed ofset %i virtual value %i has "
1749                        "virtual offset %i",
1750                        lang_hooks.decl_printable_name (n->thunk.alias, 2),
1751                        (int)n->thunk.fixed_offset,
1752                        (int)n->thunk.virtual_value,
1753                        (int)n->thunk.virtual_offset_p);
1754               fprintf (f, ")");
1755             }
1756         }
1757       fprintf (f, "\n");
1758     }
1759 }
1760
1761
1762 /* Dump call graph node NODE to stderr.  */
1763
1764 void
1765 debug_cgraph_node (struct cgraph_node *node)
1766 {
1767   dump_cgraph_node (stderr, node);
1768 }
1769
1770
1771 /* Dump the callgraph to file F.  */
1772
1773 void
1774 dump_cgraph (FILE *f)
1775 {
1776   struct cgraph_node *node;
1777
1778   fprintf (f, "callgraph:\n\n");
1779   for (node = cgraph_nodes; node; node = node->next)
1780     dump_cgraph_node (f, node);
1781 }
1782
1783
1784 /* Dump the call graph to stderr.  */
1785
1786 void
1787 debug_cgraph (void)
1788 {
1789   dump_cgraph (stderr);
1790 }
1791
1792
1793 /* Set the DECL_ASSEMBLER_NAME and update cgraph hashtables.  */
1794
1795 void
1796 change_decl_assembler_name (tree decl, tree name)
1797 {
1798   gcc_assert (!assembler_name_hash);
1799   if (!DECL_ASSEMBLER_NAME_SET_P (decl))
1800     {
1801       SET_DECL_ASSEMBLER_NAME (decl, name);
1802       return;
1803     }
1804   if (name == DECL_ASSEMBLER_NAME (decl))
1805     return;
1806
1807   if (TREE_SYMBOL_REFERENCED (DECL_ASSEMBLER_NAME (decl))
1808       && DECL_RTL_SET_P (decl))
1809     warning (0, "%D renamed after being referenced in assembly", decl);
1810
1811   SET_DECL_ASSEMBLER_NAME (decl, name);
1812 }
1813
1814 /* Add a top-level asm statement to the list.  */
1815
1816 struct cgraph_asm_node *
1817 cgraph_add_asm_node (tree asm_str)
1818 {
1819   struct cgraph_asm_node *node;
1820
1821   node = GGC_CNEW (struct cgraph_asm_node);
1822   node->asm_str = asm_str;
1823   node->order = cgraph_order++;
1824   node->next = NULL;
1825   if (cgraph_asm_nodes == NULL)
1826     cgraph_asm_nodes = node;
1827   else
1828     cgraph_asm_last_node->next = node;
1829   cgraph_asm_last_node = node;
1830   return node;
1831 }
1832
1833 /* Return true when the DECL can possibly be inlined.  */
1834 bool
1835 cgraph_function_possibly_inlined_p (tree decl)
1836 {
1837   if (!cgraph_global_info_ready)
1838     return !DECL_UNINLINABLE (decl);
1839   return DECL_POSSIBLY_INLINED (decl);
1840 }
1841
1842 /* Create clone of E in the node N represented by CALL_EXPR the callgraph.  */
1843 struct cgraph_edge *
1844 cgraph_clone_edge (struct cgraph_edge *e, struct cgraph_node *n,
1845                    gimple call_stmt, unsigned stmt_uid, gcov_type count_scale,
1846                    int freq_scale, int loop_nest, bool update_original)
1847 {
1848   struct cgraph_edge *new_edge;
1849   gcov_type count = e->count * count_scale / REG_BR_PROB_BASE;
1850   gcov_type freq;
1851
1852   /* We do not want to ignore loop nest after frequency drops to 0.  */
1853   if (!freq_scale)
1854     freq_scale = 1;
1855   freq = e->frequency * (gcov_type) freq_scale / CGRAPH_FREQ_BASE;
1856   if (freq > CGRAPH_FREQ_MAX)
1857     freq = CGRAPH_FREQ_MAX;
1858   new_edge = cgraph_create_edge (n, e->callee, call_stmt, count, freq,
1859                             e->loop_nest + loop_nest);
1860
1861   new_edge->inline_failed = e->inline_failed;
1862   new_edge->indirect_call = e->indirect_call;
1863   new_edge->lto_stmt_uid = stmt_uid;
1864   if (update_original)
1865     {
1866       e->count -= new_edge->count;
1867       if (e->count < 0)
1868         e->count = 0;
1869     }
1870   cgraph_call_edge_duplication_hooks (e, new_edge);
1871   return new_edge;
1872 }
1873
1874 /* Create node representing clone of N executed COUNT times.  Decrease
1875    the execution counts from original node too.
1876
1877    When UPDATE_ORIGINAL is true, the counts are subtracted from the original
1878    function's profile to reflect the fact that part of execution is handled
1879    by node.  */
1880 struct cgraph_node *
1881 cgraph_clone_node (struct cgraph_node *n, gcov_type count, int freq,
1882                    int loop_nest, bool update_original,
1883                    VEC(cgraph_edge_p,heap) *redirect_callers)
1884 {
1885   struct cgraph_node *new_node = cgraph_create_node ();
1886   struct cgraph_edge *e;
1887   gcov_type count_scale;
1888   unsigned i;
1889
1890   new_node->decl = n->decl;
1891   new_node->origin = n->origin;
1892   if (new_node->origin)
1893     {
1894       new_node->next_nested = new_node->origin->nested;
1895       new_node->origin->nested = new_node;
1896     }
1897   new_node->analyzed = n->analyzed;
1898   new_node->local = n->local;
1899   new_node->local.externally_visible = false;
1900   new_node->local.local = true;
1901   new_node->local.vtable_method = false;
1902   new_node->global = n->global;
1903   new_node->rtl = n->rtl;
1904   new_node->count = count;
1905   new_node->frequency = n->frequency;
1906   new_node->clone = n->clone;
1907   new_node->clone.tree_map = 0;
1908   if (n->count)
1909     {
1910       if (new_node->count > n->count)
1911         count_scale = REG_BR_PROB_BASE;
1912       else
1913         count_scale = new_node->count * REG_BR_PROB_BASE / n->count;
1914     }
1915   else
1916     count_scale = 0;
1917   if (update_original)
1918     {
1919       n->count -= count;
1920       if (n->count < 0)
1921         n->count = 0;
1922     }
1923
1924   for (i = 0; VEC_iterate (cgraph_edge_p, redirect_callers, i, e); i++)
1925     {
1926       /* Redirect calls to the old version node to point to its new
1927          version.  */
1928       cgraph_redirect_edge_callee (e, new_node);
1929     }
1930
1931
1932   for (e = n->callees;e; e=e->next_callee)
1933     cgraph_clone_edge (e, new_node, e->call_stmt, e->lto_stmt_uid,
1934                        count_scale, freq, loop_nest, update_original);
1935
1936   new_node->next_sibling_clone = n->clones;
1937   if (n->clones)
1938     n->clones->prev_sibling_clone = new_node;
1939   n->clones = new_node;
1940   new_node->clone_of = n;
1941
1942   cgraph_call_node_duplication_hooks (n, new_node);
1943   return new_node;
1944 }
1945
1946 /* Create a new name for omp child function.  Returns an identifier.  */
1947
1948 static GTY(()) unsigned int clone_fn_id_num;
1949
1950 static tree
1951 clone_function_name (tree decl)
1952 {
1953   tree name = DECL_ASSEMBLER_NAME (decl);
1954   size_t len = IDENTIFIER_LENGTH (name);
1955   char *tmp_name, *prefix;
1956
1957   prefix = XALLOCAVEC (char, len + strlen ("_clone") + 1);
1958   memcpy (prefix, IDENTIFIER_POINTER (name), len);
1959   strcpy (prefix + len, "_clone");
1960 #ifndef NO_DOT_IN_LABEL
1961   prefix[len] = '.';
1962 #elif !defined NO_DOLLAR_IN_LABEL
1963   prefix[len] = '$';
1964 #endif
1965   ASM_FORMAT_PRIVATE_NAME (tmp_name, prefix, clone_fn_id_num++);
1966   return get_identifier (tmp_name);
1967 }
1968
1969 /* Create callgraph node clone with new declaration.  The actual body will
1970    be copied later at compilation stage.
1971
1972    TODO: after merging in ipa-sra use function call notes instead of args_to_skip
1973    bitmap interface.
1974    */
1975 struct cgraph_node *
1976 cgraph_create_virtual_clone (struct cgraph_node *old_node,
1977                              VEC(cgraph_edge_p,heap) *redirect_callers,
1978                              VEC(ipa_replace_map_p,gc) *tree_map,
1979                              bitmap args_to_skip)
1980 {
1981   tree old_decl = old_node->decl;
1982   struct cgraph_node *new_node = NULL;
1983   tree new_decl;
1984   struct cgraph_node key, **slot;
1985
1986   gcc_assert  (tree_versionable_function_p (old_decl));
1987
1988   /* Make a new FUNCTION_DECL tree node */
1989   if (!args_to_skip)
1990     new_decl = copy_node (old_decl);
1991   else
1992     new_decl = build_function_decl_skip_args (old_decl, args_to_skip);
1993   DECL_STRUCT_FUNCTION (new_decl) = NULL;
1994
1995   /* Generate a new name for the new version. */
1996   DECL_NAME (new_decl) = clone_function_name (old_decl);
1997   SET_DECL_ASSEMBLER_NAME (new_decl, DECL_NAME (new_decl));
1998   SET_DECL_RTL (new_decl, NULL);
1999
2000   new_node = cgraph_clone_node (old_node, old_node->count,
2001                                 CGRAPH_FREQ_BASE, 0, false,
2002                                 redirect_callers);
2003   new_node->decl = new_decl;
2004   /* Update the properties.
2005      Make clone visible only within this translation unit.  Make sure
2006      that is not weak also.
2007      ??? We cannot use COMDAT linkage because there is no
2008      ABI support for this.  */
2009   DECL_EXTERNAL (new_node->decl) = 0;
2010   DECL_COMDAT_GROUP (new_node->decl) = 0;
2011   TREE_PUBLIC (new_node->decl) = 0;
2012   DECL_COMDAT (new_node->decl) = 0;
2013   DECL_WEAK (new_node->decl) = 0;
2014   new_node->clone.tree_map = tree_map;
2015   new_node->clone.args_to_skip = args_to_skip;
2016   if (!args_to_skip)
2017     new_node->clone.combined_args_to_skip = old_node->clone.combined_args_to_skip;
2018   else if (old_node->clone.combined_args_to_skip)
2019     {
2020       int newi = 0, oldi = 0;
2021       tree arg;
2022       bitmap new_args_to_skip = BITMAP_GGC_ALLOC ();
2023       struct cgraph_node *orig_node;
2024       for (orig_node = old_node; orig_node->clone_of; orig_node = orig_node->clone_of)
2025         ;
2026       for (arg = DECL_ARGUMENTS (orig_node->decl); arg; arg = TREE_CHAIN (arg), oldi++)
2027         {
2028           if (bitmap_bit_p (old_node->clone.combined_args_to_skip, oldi))
2029             {
2030               bitmap_set_bit (new_args_to_skip, oldi);
2031               continue;
2032             }
2033           if (bitmap_bit_p (args_to_skip, newi))
2034             bitmap_set_bit (new_args_to_skip, oldi);
2035           newi++;
2036         }
2037       new_node->clone.combined_args_to_skip = new_args_to_skip;
2038     }
2039   else
2040     new_node->clone.combined_args_to_skip = args_to_skip;
2041   new_node->local.externally_visible = 0;
2042   new_node->local.local = 1;
2043   new_node->lowered = true;
2044   new_node->reachable = true;
2045
2046   key.decl = new_decl;
2047   slot = (struct cgraph_node **) htab_find_slot (cgraph_hash, &key, INSERT);
2048   gcc_assert (!*slot);
2049   *slot = new_node;
2050   if (assembler_name_hash)
2051     {
2052       void **aslot;
2053       tree name = DECL_ASSEMBLER_NAME (new_decl);
2054
2055       aslot = htab_find_slot_with_hash (assembler_name_hash, name,
2056                                         decl_assembler_name_hash (name),
2057                                         INSERT);
2058       gcc_assert (!*aslot);
2059       *aslot = new_node;
2060     }
2061
2062   return new_node;
2063 }
2064
2065 /* NODE is no longer nested function; update cgraph accordingly.  */
2066 void
2067 cgraph_unnest_node (struct cgraph_node *node)
2068 {
2069   struct cgraph_node **node2 = &node->origin->nested;
2070   gcc_assert (node->origin);
2071
2072   while (*node2 != node)
2073     node2 = &(*node2)->next_nested;
2074   *node2 = node->next_nested;
2075   node->origin = NULL;
2076 }
2077
2078 /* Return function availability.  See cgraph.h for description of individual
2079    return values.  */
2080 enum availability
2081 cgraph_function_body_availability (struct cgraph_node *node)
2082 {
2083   enum availability avail;
2084   gcc_assert (cgraph_function_flags_ready);
2085   if (!node->analyzed)
2086     avail = AVAIL_NOT_AVAILABLE;
2087   else if (node->local.local)
2088     avail = AVAIL_LOCAL;
2089   else if (!node->local.externally_visible)
2090     avail = AVAIL_AVAILABLE;
2091   /* Inline functions are safe to be analyzed even if their sybol can
2092      be overwritten at runtime.  It is not meaningful to enfore any sane
2093      behaviour on replacing inline function by different body.  */
2094   else if (DECL_DECLARED_INLINE_P (node->decl))
2095     avail = AVAIL_AVAILABLE;
2096
2097   /* If the function can be overwritten, return OVERWRITABLE.  Take
2098      care at least of two notable extensions - the COMDAT functions
2099      used to share template instantiations in C++ (this is symmetric
2100      to code cp_cannot_inline_tree_fn and probably shall be shared and
2101      the inlinability hooks completely eliminated).
2102
2103      ??? Does the C++ one definition rule allow us to always return
2104      AVAIL_AVAILABLE here?  That would be good reason to preserve this
2105      bit.  */
2106
2107   else if (DECL_REPLACEABLE_P (node->decl) && !DECL_EXTERNAL (node->decl))
2108     avail = AVAIL_OVERWRITABLE;
2109   else avail = AVAIL_AVAILABLE;
2110
2111   return avail;
2112 }
2113
2114 /* Add the function FNDECL to the call graph.
2115    Unlike cgraph_finalize_function, this function is intended to be used
2116    by middle end and allows insertion of new function at arbitrary point
2117    of compilation.  The function can be either in high, low or SSA form
2118    GIMPLE.
2119
2120    The function is assumed to be reachable and have address taken (so no
2121    API breaking optimizations are performed on it).
2122
2123    Main work done by this function is to enqueue the function for later
2124    processing to avoid need the passes to be re-entrant.  */
2125
2126 void
2127 cgraph_add_new_function (tree fndecl, bool lowered)
2128 {
2129   struct cgraph_node *node;
2130   switch (cgraph_state)
2131     {
2132       case CGRAPH_STATE_CONSTRUCTION:
2133         /* Just enqueue function to be processed at nearest occurrence.  */
2134         node = cgraph_node (fndecl);
2135         node->next_needed = cgraph_new_nodes;
2136         if (lowered)
2137           node->lowered = true;
2138         cgraph_new_nodes = node;
2139         break;
2140
2141       case CGRAPH_STATE_IPA:
2142       case CGRAPH_STATE_IPA_SSA:
2143       case CGRAPH_STATE_EXPANSION:
2144         /* Bring the function into finalized state and enqueue for later
2145            analyzing and compilation.  */
2146         node = cgraph_node (fndecl);
2147         node->local.local = false;
2148         node->local.finalized = true;
2149         node->reachable = node->needed = true;
2150         if (!lowered && cgraph_state == CGRAPH_STATE_EXPANSION)
2151           {
2152             push_cfun (DECL_STRUCT_FUNCTION (fndecl));
2153             current_function_decl = fndecl;
2154             gimple_register_cfg_hooks ();
2155             tree_lowering_passes (fndecl);
2156             bitmap_obstack_initialize (NULL);
2157             if (!gimple_in_ssa_p (DECL_STRUCT_FUNCTION (fndecl)))
2158               execute_pass_list (pass_early_local_passes.pass.sub);
2159             bitmap_obstack_release (NULL);
2160             pop_cfun ();
2161             current_function_decl = NULL;
2162
2163             lowered = true;
2164           }
2165         if (lowered)
2166           node->lowered = true;
2167         node->next_needed = cgraph_new_nodes;
2168         cgraph_new_nodes = node;
2169         break;
2170
2171       case CGRAPH_STATE_FINISHED:
2172         /* At the very end of compilation we have to do all the work up
2173            to expansion.  */
2174         push_cfun (DECL_STRUCT_FUNCTION (fndecl));
2175         current_function_decl = fndecl;
2176         gimple_register_cfg_hooks ();
2177         if (!lowered)
2178           tree_lowering_passes (fndecl);
2179         bitmap_obstack_initialize (NULL);
2180         if (!gimple_in_ssa_p (DECL_STRUCT_FUNCTION (fndecl)))
2181           execute_pass_list (pass_early_local_passes.pass.sub);
2182         bitmap_obstack_release (NULL);
2183         tree_rest_of_compilation (fndecl);
2184         pop_cfun ();
2185         current_function_decl = NULL;
2186         break;
2187     }
2188
2189   /* Set a personality if required and we already passed EH lowering.  */
2190   if (lowered
2191       && (function_needs_eh_personality (DECL_STRUCT_FUNCTION (fndecl))
2192           == eh_personality_lang))
2193     DECL_FUNCTION_PERSONALITY (fndecl) = lang_hooks.eh_personality ();
2194 }
2195
2196 /* Return true if NODE can be made local for API change.
2197    Extern inline functions and C++ COMDAT functions can be made local
2198    at the expense of possible code size growth if function is used in multiple
2199    compilation units.  */
2200 bool
2201 cgraph_node_can_be_local_p (struct cgraph_node *node)
2202 {
2203   return (!node->needed
2204           && ((DECL_COMDAT (node->decl) && !node->same_comdat_group)
2205               || !node->local.externally_visible));
2206 }
2207
2208 /* Make DECL local.  FIXME: We shouldn't need to mess with rtl this early,
2209    but other code such as notice_global_symbol generates rtl.  */
2210 void
2211 cgraph_make_decl_local (tree decl)
2212 {
2213   rtx rtl, symbol;
2214
2215   if (TREE_CODE (decl) == VAR_DECL)
2216     DECL_COMMON (decl) = 0;
2217   else if (TREE_CODE (decl) == FUNCTION_DECL)
2218     {
2219       DECL_COMDAT (decl) = 0;
2220       DECL_COMDAT_GROUP (decl) = 0;
2221       DECL_WEAK (decl) = 0;
2222       DECL_EXTERNAL (decl) = 0;
2223     }
2224   else
2225     gcc_unreachable ();
2226   TREE_PUBLIC (decl) = 0;
2227   if (!DECL_RTL_SET_P (decl))
2228     return;
2229
2230   /* Update rtl flags.  */
2231   make_decl_rtl (decl);
2232
2233   rtl = DECL_RTL (decl);
2234   if (!MEM_P (rtl))
2235     return;
2236
2237   symbol = XEXP (rtl, 0);
2238   if (GET_CODE (symbol) != SYMBOL_REF)
2239     return;
2240
2241   SYMBOL_REF_WEAK (symbol) = DECL_WEAK (decl);
2242 }
2243
2244 /* Bring NODE local.  */
2245 void
2246 cgraph_make_node_local (struct cgraph_node *node)
2247 {
2248   gcc_assert (cgraph_node_can_be_local_p (node));
2249   if (DECL_COMDAT (node->decl) || DECL_EXTERNAL (node->decl))
2250     {
2251       struct cgraph_node *alias;
2252       cgraph_make_decl_local (node->decl);
2253
2254       for (alias = node->same_body; alias; alias = alias->next)
2255         cgraph_make_decl_local (alias->decl);
2256
2257       node->local.externally_visible = false;
2258       node->local.local = true;
2259       gcc_assert (cgraph_function_body_availability (node) == AVAIL_LOCAL);
2260     }
2261 }
2262
2263 /* Set TREE_NOTHROW on NODE's decl and on same_body aliases of NODE
2264    if any to NOTHROW.  */
2265
2266 void
2267 cgraph_set_nothrow_flag (struct cgraph_node *node, bool nothrow)
2268 {
2269   struct cgraph_node *alias;
2270   TREE_NOTHROW (node->decl) = nothrow;
2271   for (alias = node->same_body; alias; alias = alias->next)
2272     TREE_NOTHROW (alias->decl) = nothrow;
2273 }
2274
2275 /* Set TREE_READONLY on NODE's decl and on same_body aliases of NODE
2276    if any to READONLY.  */
2277
2278 void
2279 cgraph_set_readonly_flag (struct cgraph_node *node, bool readonly)
2280 {
2281   struct cgraph_node *alias;
2282   TREE_READONLY (node->decl) = readonly;
2283   for (alias = node->same_body; alias; alias = alias->next)
2284     TREE_READONLY (alias->decl) = readonly;
2285 }
2286
2287 /* Set DECL_PURE_P on NODE's decl and on same_body aliases of NODE
2288    if any to PURE.  */
2289
2290 void
2291 cgraph_set_pure_flag (struct cgraph_node *node, bool pure)
2292 {
2293   struct cgraph_node *alias;
2294   DECL_PURE_P (node->decl) = pure;
2295   for (alias = node->same_body; alias; alias = alias->next)
2296     DECL_PURE_P (alias->decl) = pure;
2297 }
2298
2299 /* Set DECL_LOOPING_CONST_OR_PURE_P on NODE's decl and on
2300    same_body aliases of NODE if any to LOOPING_CONST_OR_PURE.  */
2301
2302 void
2303 cgraph_set_looping_const_or_pure_flag (struct cgraph_node *node,
2304                                        bool looping_const_or_pure)
2305 {
2306   struct cgraph_node *alias;
2307   DECL_LOOPING_CONST_OR_PURE_P (node->decl) = looping_const_or_pure;
2308   for (alias = node->same_body; alias; alias = alias->next)
2309     DECL_LOOPING_CONST_OR_PURE_P (alias->decl) = looping_const_or_pure;
2310 }
2311
2312 /* See if the frequency of NODE can be updated based on frequencies of its
2313    callers.  */
2314 bool
2315 cgraph_propagate_frequency (struct cgraph_node *node)
2316 {
2317   bool maybe_unlikely_executed = true, maybe_executed_once = true;
2318   struct cgraph_edge *edge;
2319   if (!node->local.local)
2320     return false;
2321   gcc_assert (node->analyzed);
2322   if (node->frequency == NODE_FREQUENCY_HOT)
2323     return false;
2324   if (node->frequency == NODE_FREQUENCY_UNLIKELY_EXECUTED)
2325     return false;
2326   if (dump_file && (dump_flags & TDF_DETAILS))
2327     fprintf (dump_file, "Processing frequency %s\n", cgraph_node_name (node));
2328   for (edge = node->callers;
2329        edge && (maybe_unlikely_executed || maybe_executed_once);
2330        edge = edge->next_caller)
2331     {
2332       if (!edge->frequency)
2333         continue;
2334       switch (edge->caller->frequency)
2335         {
2336         case NODE_FREQUENCY_UNLIKELY_EXECUTED:
2337           break;
2338         case NODE_FREQUENCY_EXECUTED_ONCE:
2339           if (dump_file && (dump_flags & TDF_DETAILS))
2340             fprintf (dump_file, "  Called by %s that is executed once\n", cgraph_node_name (node));
2341           maybe_unlikely_executed = false;
2342           if (edge->loop_nest)
2343             {
2344               maybe_executed_once = false;
2345               if (dump_file && (dump_flags & TDF_DETAILS))
2346                 fprintf (dump_file, "  Called in loop\n");
2347             }
2348           break;
2349         case NODE_FREQUENCY_HOT:
2350         case NODE_FREQUENCY_NORMAL:
2351           if (dump_file && (dump_flags & TDF_DETAILS))
2352             fprintf (dump_file, "  Called by %s that is normal or hot\n", cgraph_node_name (node));
2353           maybe_unlikely_executed = false;
2354           maybe_executed_once = false;
2355           break;
2356         }
2357     }
2358    if (maybe_unlikely_executed)
2359      {
2360        node->frequency = NODE_FREQUENCY_UNLIKELY_EXECUTED;
2361        if (dump_file)
2362          fprintf (dump_file, "Node %s promoted to unlikely executed.\n", cgraph_node_name (node));
2363        return true;
2364      }
2365    if (maybe_executed_once && node->frequency != NODE_FREQUENCY_EXECUTED_ONCE)
2366      {
2367        node->frequency = NODE_FREQUENCY_EXECUTED_ONCE;
2368        if (dump_file)
2369          fprintf (dump_file, "Node %s promoted to executed once.\n", cgraph_node_name (node));
2370        return true;
2371      }
2372    return false;
2373 }
2374
2375 #include "gt-cgraph.h"