gcc/cgraph.c

   1 /* Callgraph handling code.
   2    Copyright (C) 2003, 2004 Free Software Foundation, Inc.
   3    Contributed by Jan Hubicka
   4
   5 This file is part of GCC.
   6
   7 GCC is free software; you can redistribute it and/or modify it under
   8 the terms of the GNU General Public License as published by the Free
   9 Software Foundation; either version 2, or (at your option) any later
  10 version.
  11
  12 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
  13 WARRANTY; without even the implied warranty of MERCHANTABILITY or
  14 FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  15 for more details.
  16
  17 You should have received a copy of the GNU General Public License
  18 along with GCC; see the file COPYING.  If not, write to the Free
  19 Software Foundation, 59 Temple Place - Suite 330, Boston, MA
  20 02111-1307, USA.  */
  21
  22 /*  This file contains basic routines manipulating call graph and variable pool
  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 (in
  32     contrast to tree DECL nodes where we can have multiple nodes for each
  33     function).
  34
  35     The mapping from declarations to call-graph nodes is done using hash table
  36     based on DECL_ASSEMBLER_NAME, so it is essential for assembler name to
  37     not change once the declaration is inserted into the call-graph.
  38     The call-graph nodes are created lazily using cgraph_node function when
  39     called for unknown declaration.
  40
  41     When built, there is one edge for each direct call.  It is possible that
  42     the reference will be later optimized out.  The call-graph is built
  43     conservatively in order to make conservative data flow analysis possible.
  44
  45     The callgraph at the moment does not represent indirect calls or calls
  46     from other compilation unit.  Flag NEEDED is set for each node that may
  47     be accessed in such a invisible way and it shall be considered an
  48     entry point to the callgraph.
  49
  50     Intraprocedural information:
  51
  52       Callgraph is place to store data needed for intraprocedural optimization.
  53       All datastructures are divided into three components: local_info that
  54       is produced while analyzing the function, global_info that is result
  55       of global walkking of the callgraph on the end of compilation and
  56       rtl_info used by RTL backend to propagate data from already compiled
  57       functions to their callers.
  58
  59     Inlining plans:
  60
  61       The function inlining information is decided in advance and maintained
  62       in the callgraph as so called inline plan.
  63       For each inlined call, the calle's node is clonned to represent the
  64       new function copy produced by inlininer.
  65       Each inlined call gets unque corresponding clone node of the callee
  66       and the datastructure is updated while inlining is performed, so
  67       the clones are elliminated and their callee edges redirected to the
  68       caller.
  69
  70       Each edge has "inline_failed" field.  When the field is set to NULL,
  71       the call will be inlined.  When it is non-NULL it contains a reason
  72       why inlining wasn't performed.
  73
  74
  75 The varpool data structure:
  76
  77     Varpool is used to maintain variables in similar manner as call-graph
  78     is used for functions.  Most of the API is symmetric replacing cgraph
  79     function prefix by cgraph_varpool  */
  80
  81
  82 #include "config.h"
  83 #include "system.h"
  84 #include "coretypes.h"
  85 #include "tm.h"
  86 #include "tree.h"
  87 #include "langhooks.h"
  88 #include "hashtab.h"
  89 #include "toplev.h"
  90 #include "flags.h"
  91 #include "ggc.h"
  92 #include "debug.h"
  93 #include "target.h"
  94 #include "cgraph.h"
  95 #include "varray.h"
  96 #include "output.h"
  97 #include "intl.h"
  98
  99 /* Hash table used to convert declarations into nodes.  */
 100 static GTY((param_is (struct cgraph_node))) htab_t cgraph_hash;
 101
 102 /* We destructively update callgraph during inlining and thus we need to
 103    keep information on whether inlining happend separately.  */
 104 htab_t cgraph_inline_hash;
 105
 106 /* The linked list of cgraph nodes.  */
 107 struct cgraph_node *cgraph_nodes;
 108
 109 /* Queue of cgraph nodes scheduled to be lowered.  */
 110 struct cgraph_node *cgraph_nodes_queue;
 111
 112 /* Number of nodes in existence.  */
 113 int cgraph_n_nodes;
 114
 115 /* Maximal uid used in cgraph nodes.  */
 116 int cgraph_max_uid;
 117
 118 /* Set when whole unit has been analyzed so we can access global info.  */
 119 bool cgraph_global_info_ready = false;
 120
 121 /* Hash table used to convert declarations into nodes.  */
 122 static GTY((param_is (struct cgraph_varpool_node))) htab_t cgraph_varpool_hash;
 123
 124 /* Queue of cgraph nodes scheduled to be lowered and output.  */
 125 struct cgraph_varpool_node *cgraph_varpool_nodes_queue;
 126
 127 /* Number of nodes in existence.  */
 128 int cgraph_varpool_n_nodes;
 129
 130 /* The linked list of cgraph varpool nodes.  */
 131 static GTY(())  struct cgraph_varpool_node *cgraph_varpool_nodes;
 132
 133 static hashval_t hash_node (const void *);
 134 static int eq_node (const void *, const void *);
 135
 136 /* Returns a hash code for P.  */
 137
 138 static hashval_t
 139 hash_node (const void *p)
 140 {
 141   return ((hashval_t)
 142           IDENTIFIER_HASH_VALUE (DECL_ASSEMBLER_NAME
 143                                  (((struct cgraph_node *) p)->decl)));
 144 }
 145
 146 /* Returns nonzero if P1 and P2 are equal.  */
 147
 148 static int
 149 eq_node (const void *p1, const void *p2)
 150 {
 151   return ((DECL_ASSEMBLER_NAME (((struct cgraph_node *) p1)->decl)) ==
 152           (tree) p2);
 153 }
 154
 155 /* Allocate new callgraph node and insert it into basic datastructures.  */
 156 static struct cgraph_node *
 157 cgraph_create_node (void)
 158 {
 159   struct cgraph_node *node;
 160
 161   node = ggc_alloc_cleared (sizeof (*node));
 162   node->next = cgraph_nodes;
 163   node->uid = cgraph_max_uid++;
 164   if (cgraph_nodes)
 165     cgraph_nodes->previous = node;
 166   node->previous = NULL;
 167   cgraph_nodes = node;
 168   cgraph_n_nodes++;
 169   return node;
 170 }
 171
 172 /* Return cgraph node assigned to DECL.  Create new one when needed.  */
 173 struct cgraph_node *
 174 cgraph_node (tree decl)
 175 {
 176   struct cgraph_node *node;
 177   struct cgraph_node **slot;
 178
 179   if (TREE_CODE (decl) != FUNCTION_DECL)
 180     abort ();
 181
 182   if (!cgraph_hash)
 183     cgraph_hash = htab_create_ggc (10, hash_node, eq_node, NULL);
 184
 185   slot = (struct cgraph_node **)
 186     htab_find_slot_with_hash (cgraph_hash, DECL_ASSEMBLER_NAME (decl),
 187                               IDENTIFIER_HASH_VALUE
 188                                 (DECL_ASSEMBLER_NAME (decl)), INSERT);
 189   if (*slot)
 190     return *slot;
 191
 192   node = cgraph_create_node ();
 193   node->decl = decl;
 194   *slot = node;
 195   if (DECL_CONTEXT (decl) && TREE_CODE (DECL_CONTEXT (decl)) == FUNCTION_DECL)
 196     {
 197       node->origin = cgraph_node (DECL_CONTEXT (decl));
 198       node->next_nested = node->origin->nested;
 199       node->origin->nested = node;
 200     }
 201   return node;
 202 }
 203
 204 /* Return callgraph edge representing CALL_EXPR.  */
 205 struct cgraph_edge *
 206 cgraph_edge (struct cgraph_node *node, tree call_expr)
 207 {
 208   struct cgraph_edge *e;
 209
 210   /* This loop may turn out to be performance problem.  In such case adding
 211      hashtables into call nodes with very many edges is probably best
 212      solution.  It is not good idea to add pointer into CALL_EXPR itself
 213      because we want to make possible having multiple cgraph nodes representing
 214      different clones of the same body before the body is actually cloned.  */
 215   for (e = node->callees; e; e= e->next_callee)
 216     if (e->call_expr == call_expr)
 217       break;
 218   return e;
 219 }
 220
 221 /* Try to find existing function for identifier ID.  */
 222 struct cgraph_node *
 223 cgraph_node_for_identifier (tree id)
 224 {
 225   struct cgraph_node **slot;
 226
 227   if (TREE_CODE (id) != IDENTIFIER_NODE)
 228     abort ();
 229
 230   if (!cgraph_hash)
 231     return NULL;
 232
 233   slot = (struct cgraph_node **)
 234     htab_find_slot_with_hash (cgraph_hash, id,
 235                               IDENTIFIER_HASH_VALUE (id), NO_INSERT);
 236   if (!slot)
 237     return NULL;
 238   return *slot;
 239 }
 240
 241 /* Create edge from CALLER to CALLEE in the cgraph.  */
 242
 243 struct cgraph_edge *
 244 cgraph_create_edge (struct cgraph_node *caller, struct cgraph_node *callee,
 245                     tree call_expr)
 246 {
 247   struct cgraph_edge *edge = ggc_alloc (sizeof (struct cgraph_edge));
 248 #ifdef ENABLE_CHECKING
 249   struct cgraph_edge *e;
 250
 251   for (e = caller->callees; e; e = e->next_callee)
 252     if (e->call_expr == call_expr)
 253       abort ();
 254 #endif
 255
 256   if (TREE_CODE (call_expr) != CALL_EXPR)
 257     abort ();
 258
 259   if (!DECL_SAVED_TREE (callee->decl))
 260     edge->inline_failed = N_("function body not available");
 261   else if (callee->local.redefined_extern_inline)
 262     edge->inline_failed = N_("redefined extern inline functions are not "
 263                              "considered for inlining");
 264   else if (callee->local.inlinable)
 265     edge->inline_failed = N_("function not considered for inlining");
 266   else
 267     edge->inline_failed = N_("function not inlinable");
 268
 269   edge->aux = NULL;
 270
 271   edge->caller = caller;
 272   edge->callee = callee;
 273   edge->call_expr = call_expr;
 274   edge->next_caller = callee->callers;
 275   edge->next_callee = caller->callees;
 276   caller->callees = edge;
 277   callee->callers = edge;
 278   return edge;
 279 }
 280
 281 /* Remove the edge E the cgraph.  */
 282
 283 void
 284 cgraph_remove_edge (struct cgraph_edge *e)
 285 {
 286   struct cgraph_edge **edge, **edge2;
 287
 288   for (edge = &e->callee->callers; *edge && *edge != e;
 289        edge = &((*edge)->next_caller))
 290     continue;
 291   if (!*edge)
 292     abort ();
 293   *edge = (*edge)->next_caller;
 294   for (edge2 = &e->caller->callees; *edge2 && *edge2 != e;
 295        edge2 = &(*edge2)->next_callee)
 296     continue;
 297   if (!*edge2)
 298     abort ();
 299   *edge2 = (*edge2)->next_callee;
 300 }
 301
 302 /* Redirect callee of E to N.  The function does not update underlying
 303    call expression.  */
 304
 305 void
 306 cgraph_redirect_edge_callee (struct cgraph_edge *e, struct cgraph_node *n)
 307 {
 308   struct cgraph_edge **edge;
 309
 310   for (edge = &e->callee->callers; *edge && *edge != e;
 311        edge = &((*edge)->next_caller))
 312     continue;
 313   if (!*edge)
 314     abort ();
 315   *edge = (*edge)->next_caller;
 316   e->callee = n;
 317   e->next_caller = n->callers;
 318   n->callers = e;
 319 }
 320
 321 /* Remove the node from cgraph.  */
 322
 323 void
 324 cgraph_remove_node (struct cgraph_node *node)
 325 {
 326   void **slot;
 327   bool check_dead = 1;
 328
 329   while (node->callers)
 330     cgraph_remove_edge (node->callers);
 331   while (node->callees)
 332     cgraph_remove_edge (node->callees);
 333   while (node->nested)
 334     cgraph_remove_node (node->nested);
 335   if (node->origin)
 336     {
 337       struct cgraph_node **node2 = &node->origin->nested;
 338
 339       while (*node2 != node)
 340         node2 = &(*node2)->next_nested;
 341       *node2 = node->next_nested;
 342     }
 343   if (node->previous)
 344     node->previous->next = node->next;
 345   else
 346     cgraph_nodes = node->next;
 347   if (node->next)
 348     node->next->previous = node->previous;
 349   slot =
 350     htab_find_slot_with_hash (cgraph_hash, DECL_ASSEMBLER_NAME (node->decl),
 351                               IDENTIFIER_HASH_VALUE (DECL_ASSEMBLER_NAME
 352                                                      (node->decl)), NO_INSERT);
 353   if (*slot == node)
 354     {
 355       if (node->next_clone)
 356         *slot = node->next_clone;
 357       else
 358         {
 359           htab_clear_slot (cgraph_hash, slot);
 360           if (!dump_enabled_p (TDI_all))
 361             {
 362               DECL_SAVED_TREE (node->decl) = NULL;
 363               DECL_STRUCT_FUNCTION (node->decl) = NULL;
 364             }
 365           check_dead = false;
 366         }
 367     }
 368   else
 369     {
 370       struct cgraph_node *n;
 371
 372       for (n = *slot; n->next_clone != node; n = n->next_clone)
 373         continue;
 374       n->next_clone = node->next_clone;
 375     }
 376
 377   /* Work out whether we still need a function body (either there is inline
 378      clone or there is out of line function whose body is not written).  */
 379   if (check_dead && flag_unit_at_a_time)
 380     {
 381       struct cgraph_node *n;
 382
 383       for (n = *slot; n; n = n->next_clone)
 384         if (n->global.inlined_to
 385             || (!n->global.inlined_to
 386                 && !TREE_ASM_WRITTEN (n->decl) && !DECL_EXTERNAL (n->decl)))
 387           break;
 388       if (!n && !dump_enabled_p (TDI_all))
 389         {
 390           DECL_SAVED_TREE (node->decl) = NULL;
 391           DECL_STRUCT_FUNCTION (node->decl) = NULL;
 392         }
 393     }
 394   cgraph_n_nodes--;
 395   /* Do not free the structure itself so the walk over chain can continue.  */
 396 }
 397
 398 /* Notify finalize_compilation_unit that given node is reachable.  */
 399
 400 void
 401 cgraph_mark_reachable_node (struct cgraph_node *node)
 402 {
 403   if (!node->reachable && node->local.finalized)
 404     {
 405       notice_global_symbol (node->decl);
 406       node->reachable = 1;
 407
 408       node->next_needed = cgraph_nodes_queue;
 409       cgraph_nodes_queue = node;
 410
 411       /* At the moment frontend automatically emits all nested functions.  */
 412       if (node->nested)
 413         {
 414           struct cgraph_node *node2;
 415
 416           for (node2 = node->nested; node2; node2 = node2->next_nested)
 417             if (!node2->reachable)
 418               cgraph_mark_reachable_node (node2);
 419         }
 420     }
 421 }
 422
 423 /* Likewise indicate that a node is needed, i.e. reachable via some
 424    external means.  */
 425
 426 void
 427 cgraph_mark_needed_node (struct cgraph_node *node)
 428 {
 429   node->needed = 1;
 430   cgraph_mark_reachable_node (node);
 431 }
 432
 433 /* Return true when CALLER_DECL calls CALLEE_DECL.  */
 434
 435 bool
 436 cgraph_calls_p (tree caller_decl, tree callee_decl)
 437 {
 438   struct cgraph_node *caller = cgraph_node (caller_decl);
 439   struct cgraph_node *callee = cgraph_node (callee_decl);
 440   struct cgraph_edge *edge;
 441
 442   for (edge = callee->callers; edge && (edge)->caller != caller;
 443        edge = (edge->next_caller))
 444     continue;
 445   return edge != NULL;
 446 }
 447
 448 /* Return local info for the compiled function.  */
 449
 450 struct cgraph_local_info *
 451 cgraph_local_info (tree decl)
 452 {
 453   struct cgraph_node *node;
 454   if (TREE_CODE (decl) != FUNCTION_DECL)
 455     abort ();
 456   node = cgraph_node (decl);
 457   return &node->local;
 458 }
 459
 460 /* Return local info for the compiled function.  */
 461
 462 struct cgraph_global_info *
 463 cgraph_global_info (tree decl)
 464 {
 465   struct cgraph_node *node;
 466   if (TREE_CODE (decl) != FUNCTION_DECL || !cgraph_global_info_ready)
 467     abort ();
 468   node = cgraph_node (decl);
 469   return &node->global;
 470 }
 471
 472 /* Return local info for the compiled function.  */
 473
 474 struct cgraph_rtl_info *
 475 cgraph_rtl_info (tree decl)
 476 {
 477   struct cgraph_node *node;
 478   if (TREE_CODE (decl) != FUNCTION_DECL)
 479     abort ();
 480   node = cgraph_node (decl);
 481   if (decl != current_function_decl
 482       && !TREE_ASM_WRITTEN (node->decl))
 483     return NULL;
 484   return &node->rtl;
 485 }
 486
 487 /* Return name of the node used in debug output.  */
 488 const char *
 489 cgraph_node_name (struct cgraph_node *node)
 490 {
 491   return lang_hooks.decl_printable_name (node->decl, 2);
 492 }
 493
 494 /* Dump given cgraph node.  */
 495 void
 496 dump_cgraph_node (FILE *f, struct cgraph_node *node)
 497 {
 498   struct cgraph_edge *edge;
 499   fprintf (f, "%s/%i:", cgraph_node_name (node), node->uid);
 500   if (node->global.inlined_to)
 501     fprintf (f, " (inline copy in %s/%i)",
 502              cgraph_node_name (node->global.inlined_to),
 503              node->global.inlined_to->uid);
 504   if (node->local.self_insns)
 505     fprintf (f, " %i insns", node->local.self_insns);
 506   if (node->global.insns && node->global.insns != node->local.self_insns)
 507     fprintf (f, " (%i after inlining)", node->global.insns);
 508   if (node->origin)
 509     fprintf (f, " nested in: %s", cgraph_node_name (node->origin));
 510   if (node->needed)
 511     fprintf (f, " needed");
 512   else if (node->reachable)
 513     fprintf (f, " reachable");
 514   if (DECL_SAVED_TREE (node->decl))
 515     fprintf (f, " tree");
 516   if (node->output)
 517     fprintf (f, " output");
 518
 519   if (node->local.local)
 520     fprintf (f, " local");
 521   if (node->local.disregard_inline_limits)
 522     fprintf (f, " always_inline");
 523   else if (node->local.inlinable)
 524     fprintf (f, " inlinable");
 525   if (TREE_ASM_WRITTEN (node->decl))
 526     fprintf (f, " asm_written");
 527
 528   fprintf (f, "\n  called by: ");
 529   for (edge = node->callers; edge; edge = edge->next_caller)
 530     {
 531       fprintf (f, "%s/%i ", cgraph_node_name (edge->caller),
 532                edge->caller->uid);
 533       if (!edge->inline_failed)
 534         fprintf(f, "(inlined) ");
 535     }
 536
 537   fprintf (f, "\n  calls: ");
 538   for (edge = node->callees; edge; edge = edge->next_callee)
 539     {
 540       fprintf (f, "%s/%i ", cgraph_node_name (edge->callee),
 541                edge->callee->uid);
 542       if (!edge->inline_failed)
 543         fprintf(f, "(inlined) ");
 544     }
 545   fprintf (f, "\n");
 546 }
 547
 548 /* Dump the callgraph.  */
 549
 550 void
 551 dump_cgraph (FILE *f)
 552 {
 553   struct cgraph_node *node;
 554
 555   fprintf (f, "callgraph:\n\n");
 556   for (node = cgraph_nodes; node; node = node->next)
 557     dump_cgraph_node (f, node);
 558 }
 559
 560 /* Returns a hash code for P.  */
 561
 562 static hashval_t
 563 cgraph_varpool_hash_node (const void *p)
 564 {
 565   return ((hashval_t)
 566           IDENTIFIER_HASH_VALUE (DECL_ASSEMBLER_NAME
 567                                  (((struct cgraph_varpool_node *) p)->decl)));
 568 }
 569
 570 /* Returns nonzero if P1 and P2 are equal.  */
 571
 572 static int
 573 eq_cgraph_varpool_node (const void *p1, const void *p2)
 574 {
 575   return ((DECL_ASSEMBLER_NAME (((struct cgraph_varpool_node *) p1)->decl)) ==
 576           (tree) p2);
 577 }
 578
 579 /* Return cgraph_varpool node assigned to DECL.  Create new one when needed.  */
 580 struct cgraph_varpool_node *
 581 cgraph_varpool_node (tree decl)
 582 {
 583   struct cgraph_varpool_node *node;
 584   struct cgraph_varpool_node **slot;
 585
 586   if (!DECL_P (decl) || TREE_CODE (decl) == FUNCTION_DECL)
 587     abort ();
 588
 589   if (!cgraph_varpool_hash)
 590     cgraph_varpool_hash = htab_create_ggc (10, cgraph_varpool_hash_node,
 591                                            eq_cgraph_varpool_node, NULL);
 592   slot = (struct cgraph_varpool_node **)
 593     htab_find_slot_with_hash (cgraph_varpool_hash, DECL_ASSEMBLER_NAME (decl),
 594                               IDENTIFIER_HASH_VALUE (DECL_ASSEMBLER_NAME (decl)),
 595                               INSERT);
 596   if (*slot)
 597     return *slot;
 598   node = ggc_alloc_cleared (sizeof (*node));
 599   node->decl = decl;
 600   cgraph_varpool_n_nodes++;
 601   cgraph_varpool_nodes = node;
 602   *slot = node;
 603   return node;
 604 }
 605
 606 /* Set the DECL_ASSEMBLER_NAME and update cgraph hashtables.  */
 607 void
 608 change_decl_assembler_name (tree decl, tree name)
 609 {
 610   struct cgraph_node *node = NULL;
 611   struct cgraph_varpool_node *vnode = NULL;
 612   void **slot;
 613
 614   if (!DECL_ASSEMBLER_NAME_SET_P (decl))
 615     {
 616       SET_DECL_ASSEMBLER_NAME (decl, name);
 617       return;
 618     }
 619   if (name == DECL_ASSEMBLER_NAME (decl))
 620     return;
 621
 622   if (TREE_SYMBOL_REFERENCED (DECL_ASSEMBLER_NAME (decl))
 623       && DECL_RTL_SET_P (decl))
 624     warning ("%D renamed after being referenced in assembly", decl);
 625
 626   if (TREE_CODE (decl) == FUNCTION_DECL && cgraph_hash)
 627     {
 628       /* Take a look whether declaration is in the cgraph structure.  */
 629       slot =
 630         htab_find_slot_with_hash (cgraph_hash, DECL_ASSEMBLER_NAME (decl),
 631                                    IDENTIFIER_HASH_VALUE (DECL_ASSEMBLER_NAME
 632                                                           (decl)), NO_INSERT);
 633       if (slot)
 634         node = *slot;
 635
 636       /* It is, verify that we are the canonical node for this decl.  */
 637       if (node && node->decl == decl)
 638         {
 639           node = *slot;
 640           htab_clear_slot (cgraph_hash, slot);
 641          }
 642        else
 643          node = NULL;
 644     }
 645   if (TREE_CODE (decl) == VAR_DECL && TREE_STATIC (decl) && cgraph_varpool_hash)
 646     {
 647       /* Take a look whether declaration is in the cgraph structure.  */
 648       slot =
 649         htab_find_slot_with_hash (cgraph_varpool_hash, DECL_ASSEMBLER_NAME (decl),
 650                                    IDENTIFIER_HASH_VALUE (DECL_ASSEMBLER_NAME
 651                                                           (decl)), NO_INSERT);
 652       if (slot)
 653         vnode = *slot;
 654
 655       /* It is, verify that we are the canonical vnode for this decl.  */
 656       if (vnode && vnode->decl == decl)
 657         {
 658           vnode = *slot;
 659           htab_clear_slot (cgraph_varpool_hash, slot);
 660          }
 661        else
 662          vnode = NULL;
 663     }
 664   SET_DECL_ASSEMBLER_NAME (decl, name);
 665   if (node)
 666     {
 667       slot =
 668         htab_find_slot_with_hash (cgraph_hash, name,
 669                                   IDENTIFIER_HASH_VALUE (name), INSERT);
 670       if (*slot)
 671         abort ();
 672       *slot = node;
 673     }
 674   if (vnode)
 675     {
 676       slot =
 677         htab_find_slot_with_hash (cgraph_varpool_hash, name,
 678                                   IDENTIFIER_HASH_VALUE (name), INSERT);
 679       if (*slot)
 680         abort ();
 681       *slot = vnode;
 682     }
 683 }
 684
 685 /* Try to find existing function for identifier ID.  */
 686 struct cgraph_varpool_node *
 687 cgraph_varpool_node_for_identifier (tree id)
 688 {
 689   struct cgraph_varpool_node **slot;
 690
 691   if (TREE_CODE (id) != IDENTIFIER_NODE)
 692     abort ();
 693
 694   if (!cgraph_varpool_hash)
 695     return NULL;
 696
 697   slot = (struct cgraph_varpool_node **)
 698     htab_find_slot_with_hash (cgraph_varpool_hash, id,
 699                               IDENTIFIER_HASH_VALUE (id), NO_INSERT);
 700   if (!slot)
 701     return NULL;
 702   return *slot;
 703 }
 704
 705 /* Notify finalize_compilation_unit that given node is reachable
 706    or needed.  */
 707 void
 708 cgraph_varpool_mark_needed_node (struct cgraph_varpool_node *node)
 709 {
 710   if (!node->needed && node->finalized)
 711     {
 712       node->next_needed = cgraph_varpool_nodes_queue;
 713       cgraph_varpool_nodes_queue = node;
 714       notice_global_symbol (node->decl);
 715     }
 716   node->needed = 1;
 717 }
 718
 719 void
 720 cgraph_varpool_finalize_decl (tree decl)
 721 {
 722   struct cgraph_varpool_node *node = cgraph_varpool_node (decl);
 723
 724   /* The first declaration of a variable that comes through this function
 725      decides whether it is global (in C, has external linkage)
 726      or local (in C, has internal linkage).  So do nothing more
 727      if this function has already run.  */
 728   if (node->finalized)
 729     return;
 730   if (node->needed)
 731     {
 732       node->next_needed = cgraph_varpool_nodes_queue;
 733       cgraph_varpool_nodes_queue = node;
 734       notice_global_symbol (decl);
 735     }
 736   node->finalized = true;
 737
 738   if (/* Externally visible variables must be output.  The exception are
 739          COMDAT functions that must be output only when they are needed.  */
 740       (TREE_PUBLIC (decl) && !DECL_COMDAT (decl))
 741       /* Function whose name is output to the assembler file must be produced.
 742          It is possible to assemble the name later after finalizing the function
 743          and the fact is noticed in assemble_name then.  */
 744       || (DECL_ASSEMBLER_NAME_SET_P (decl)
 745           && TREE_SYMBOL_REFERENCED (DECL_ASSEMBLER_NAME (decl))))
 746     {
 747       cgraph_varpool_mark_needed_node (node);
 748     }
 749 }
 750
 751 bool
 752 cgraph_varpool_assemble_pending_decls (void)
 753 {
 754   bool changed = false;
 755
 756   while (cgraph_varpool_nodes_queue)
 757     {
 758       tree decl = cgraph_varpool_nodes_queue->decl;
 759       struct cgraph_varpool_node *node = cgraph_varpool_nodes_queue;
 760
 761       cgraph_varpool_nodes_queue = cgraph_varpool_nodes_queue->next_needed;
 762       if (!TREE_ASM_WRITTEN (decl))
 763         {
 764           assemble_variable (decl, 0, 1, 0);
 765           changed = true;
 766         }
 767       node->next_needed = NULL;
 768     }
 769   return changed;
 770 }
 771
 772 /* Return true when the DECL can possibly be inlined.  */
 773 bool
 774 cgraph_function_possibly_inlined_p (tree decl)
 775 {
 776   if (!cgraph_global_info_ready)
 777     return (DECL_INLINE (decl) && !flag_really_no_inline);
 778   if (!cgraph_inline_hash)
 779     return false;
 780   return (htab_find_slot (cgraph_inline_hash, DECL_ASSEMBLER_NAME (decl),
 781                           NO_INSERT) != NULL);
 782 }
 783
 784 /* Create clone of E in the node N represented by CALL_EXPR the callgraph.  */
 785 struct cgraph_edge *
 786 cgraph_clone_edge (struct cgraph_edge *e, struct cgraph_node *n, tree call_expr)
 787 {
 788   struct cgraph_edge *new = cgraph_create_edge (n, e->callee, call_expr);
 789
 790   new->inline_failed = e->inline_failed;
 791   return new;
 792 }
 793
 794 /* Create node representing clone of N.  */
 795 struct cgraph_node *
 796 cgraph_clone_node (struct cgraph_node *n)
 797 {
 798   struct cgraph_node *new = cgraph_create_node ();
 799   struct cgraph_edge *e;
 800
 801   new->decl = n->decl;
 802   new->origin = n->origin;
 803   if (new->origin)
 804     {
 805       new->next_nested = new->origin->nested;
 806       new->origin->nested = new;
 807     }
 808   new->analyzed = n->analyzed;
 809   new->local = n->local;
 810   new->global = n->global;
 811   new->rtl = n->rtl;
 812
 813   for (e = n->callees;e; e=e->next_callee)
 814     cgraph_clone_edge (e, new, e->call_expr);
 815
 816   new->next_clone = n->next_clone;
 817   n->next_clone = new;
 818
 819   return new;
 820 }
 821 #include "gt-cgraph.h"