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 data structures are divided into three components: local_info that
  54       is produced while analyzing the function, global_info that is result
  55       of global walking 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 callee's node is cloned to represent the
  64       new function copy produced by inlininer.
  65       Each inlined call gets a unique corresponding clone node of the callee
  66       and the data structure is updated while inlining is performed, so
  67       the clones are eliminated 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 happened 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 data structures.  */
 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 }
 412
 413 /* Likewise indicate that a node is needed, i.e. reachable via some
 414    external means.  */
 415
 416 void
 417 cgraph_mark_needed_node (struct cgraph_node *node)
 418 {
 419   node->needed = 1;
 420   cgraph_mark_reachable_node (node);
 421 }
 422
 423 /* Return true when CALLER_DECL calls CALLEE_DECL.  */
 424
 425 bool
 426 cgraph_calls_p (tree caller_decl, tree callee_decl)
 427 {
 428   struct cgraph_node *caller = cgraph_node (caller_decl);
 429   struct cgraph_node *callee = cgraph_node (callee_decl);
 430   struct cgraph_edge *edge;
 431
 432   for (edge = callee->callers; edge && (edge)->caller != caller;
 433        edge = (edge->next_caller))
 434     continue;
 435   return edge != NULL;
 436 }
 437
 438 /* Return local info for the compiled function.  */
 439
 440 struct cgraph_local_info *
 441 cgraph_local_info (tree decl)
 442 {
 443   struct cgraph_node *node;
 444   if (TREE_CODE (decl) != FUNCTION_DECL)
 445     abort ();
 446   node = cgraph_node (decl);
 447   return &node->local;
 448 }
 449
 450 /* Return local info for the compiled function.  */
 451
 452 struct cgraph_global_info *
 453 cgraph_global_info (tree decl)
 454 {
 455   struct cgraph_node *node;
 456   if (TREE_CODE (decl) != FUNCTION_DECL || !cgraph_global_info_ready)
 457     abort ();
 458   node = cgraph_node (decl);
 459   return &node->global;
 460 }
 461
 462 /* Return local info for the compiled function.  */
 463
 464 struct cgraph_rtl_info *
 465 cgraph_rtl_info (tree decl)
 466 {
 467   struct cgraph_node *node;
 468   if (TREE_CODE (decl) != FUNCTION_DECL)
 469     abort ();
 470   node = cgraph_node (decl);
 471   if (decl != current_function_decl
 472       && !TREE_ASM_WRITTEN (node->decl))
 473     return NULL;
 474   return &node->rtl;
 475 }
 476
 477 /* Return name of the node used in debug output.  */
 478 const char *
 479 cgraph_node_name (struct cgraph_node *node)
 480 {
 481   return lang_hooks.decl_printable_name (node->decl, 2);
 482 }
 483
 484 /* Dump given cgraph node.  */
 485 void
 486 dump_cgraph_node (FILE *f, struct cgraph_node *node)
 487 {
 488   struct cgraph_edge *edge;
 489   fprintf (f, "%s/%i:", cgraph_node_name (node), node->uid);
 490   if (node->global.inlined_to)
 491     fprintf (f, " (inline copy in %s/%i)",
 492              cgraph_node_name (node->global.inlined_to),
 493              node->global.inlined_to->uid);
 494   if (node->local.self_insns)
 495     fprintf (f, " %i insns", node->local.self_insns);
 496   if (node->global.insns && node->global.insns != node->local.self_insns)
 497     fprintf (f, " (%i after inlining)", node->global.insns);
 498   if (node->origin)
 499     fprintf (f, " nested in: %s", cgraph_node_name (node->origin));
 500   if (node->needed)
 501     fprintf (f, " needed");
 502   else if (node->reachable)
 503     fprintf (f, " reachable");
 504   if (DECL_SAVED_TREE (node->decl))
 505     fprintf (f, " tree");
 506   if (node->output)
 507     fprintf (f, " output");
 508
 509   if (node->local.local)
 510     fprintf (f, " local");
 511   if (node->local.disregard_inline_limits)
 512     fprintf (f, " always_inline");
 513   else if (node->local.inlinable)
 514     fprintf (f, " inlinable");
 515   if (TREE_ASM_WRITTEN (node->decl))
 516     fprintf (f, " asm_written");
 517
 518   fprintf (f, "\n  called by: ");
 519   for (edge = node->callers; edge; edge = edge->next_caller)
 520     {
 521       fprintf (f, "%s/%i ", cgraph_node_name (edge->caller),
 522                edge->caller->uid);
 523       if (!edge->inline_failed)
 524         fprintf(f, "(inlined) ");
 525     }
 526
 527   fprintf (f, "\n  calls: ");
 528   for (edge = node->callees; edge; edge = edge->next_callee)
 529     {
 530       fprintf (f, "%s/%i ", cgraph_node_name (edge->callee),
 531                edge->callee->uid);
 532       if (!edge->inline_failed)
 533         fprintf(f, "(inlined) ");
 534     }
 535   fprintf (f, "\n");
 536 }
 537
 538 /* Dump the callgraph.  */
 539
 540 void
 541 dump_cgraph (FILE *f)
 542 {
 543   struct cgraph_node *node;
 544
 545   fprintf (f, "callgraph:\n\n");
 546   for (node = cgraph_nodes; node; node = node->next)
 547     dump_cgraph_node (f, node);
 548 }
 549
 550 /* Returns a hash code for P.  */
 551
 552 static hashval_t
 553 cgraph_varpool_hash_node (const void *p)
 554 {
 555   return ((hashval_t)
 556           IDENTIFIER_HASH_VALUE (DECL_ASSEMBLER_NAME
 557                                  (((struct cgraph_varpool_node *) p)->decl)));
 558 }
 559
 560 /* Returns nonzero if P1 and P2 are equal.  */
 561
 562 static int
 563 eq_cgraph_varpool_node (const void *p1, const void *p2)
 564 {
 565   return ((DECL_ASSEMBLER_NAME (((struct cgraph_varpool_node *) p1)->decl)) ==
 566           (tree) p2);
 567 }
 568
 569 /* Return cgraph_varpool node assigned to DECL.  Create new one when needed.  */
 570 struct cgraph_varpool_node *
 571 cgraph_varpool_node (tree decl)
 572 {
 573   struct cgraph_varpool_node *node;
 574   struct cgraph_varpool_node **slot;
 575
 576   if (!DECL_P (decl) || TREE_CODE (decl) == FUNCTION_DECL)
 577     abort ();
 578
 579   if (!cgraph_varpool_hash)
 580     cgraph_varpool_hash = htab_create_ggc (10, cgraph_varpool_hash_node,
 581                                            eq_cgraph_varpool_node, NULL);
 582   slot = (struct cgraph_varpool_node **)
 583     htab_find_slot_with_hash (cgraph_varpool_hash, DECL_ASSEMBLER_NAME (decl),
 584                               IDENTIFIER_HASH_VALUE (DECL_ASSEMBLER_NAME (decl)),
 585                               INSERT);
 586   if (*slot)
 587     return *slot;
 588   node = ggc_alloc_cleared (sizeof (*node));
 589   node->decl = decl;
 590   cgraph_varpool_n_nodes++;
 591   cgraph_varpool_nodes = node;
 592   *slot = node;
 593   return node;
 594 }
 595
 596 /* Set the DECL_ASSEMBLER_NAME and update cgraph hashtables.  */
 597 void
 598 change_decl_assembler_name (tree decl, tree name)
 599 {
 600   struct cgraph_node *node = NULL;
 601   struct cgraph_varpool_node *vnode = NULL;
 602   void **slot;
 603
 604   if (!DECL_ASSEMBLER_NAME_SET_P (decl))
 605     {
 606       SET_DECL_ASSEMBLER_NAME (decl, name);
 607       return;
 608     }
 609   if (name == DECL_ASSEMBLER_NAME (decl))
 610     return;
 611
 612   if (TREE_SYMBOL_REFERENCED (DECL_ASSEMBLER_NAME (decl))
 613       && DECL_RTL_SET_P (decl))
 614     warning ("%D renamed after being referenced in assembly", decl);
 615
 616   if (TREE_CODE (decl) == FUNCTION_DECL && cgraph_hash)
 617     {
 618       /* Take a look whether declaration is in the cgraph structure.  */
 619       slot =
 620         htab_find_slot_with_hash (cgraph_hash, DECL_ASSEMBLER_NAME (decl),
 621                                    IDENTIFIER_HASH_VALUE (DECL_ASSEMBLER_NAME
 622                                                           (decl)), NO_INSERT);
 623       if (slot)
 624         node = *slot;
 625
 626       /* It is, verify that we are the canonical node for this decl.  */
 627       if (node && node->decl == decl)
 628         {
 629           node = *slot;
 630           htab_clear_slot (cgraph_hash, slot);
 631          }
 632        else
 633          node = NULL;
 634     }
 635   if (TREE_CODE (decl) == VAR_DECL && TREE_STATIC (decl) && cgraph_varpool_hash)
 636     {
 637       /* Take a look whether declaration is in the cgraph structure.  */
 638       slot =
 639         htab_find_slot_with_hash (cgraph_varpool_hash, DECL_ASSEMBLER_NAME (decl),
 640                                    IDENTIFIER_HASH_VALUE (DECL_ASSEMBLER_NAME
 641                                                           (decl)), NO_INSERT);
 642       if (slot)
 643         vnode = *slot;
 644
 645       /* It is, verify that we are the canonical vnode for this decl.  */
 646       if (vnode && vnode->decl == decl)
 647         {
 648           vnode = *slot;
 649           htab_clear_slot (cgraph_varpool_hash, slot);
 650          }
 651        else
 652          vnode = NULL;
 653     }
 654   SET_DECL_ASSEMBLER_NAME (decl, name);
 655   if (node)
 656     {
 657       slot =
 658         htab_find_slot_with_hash (cgraph_hash, name,
 659                                   IDENTIFIER_HASH_VALUE (name), INSERT);
 660       if (*slot)
 661         abort ();
 662       *slot = node;
 663     }
 664   if (vnode)
 665     {
 666       slot =
 667         htab_find_slot_with_hash (cgraph_varpool_hash, name,
 668                                   IDENTIFIER_HASH_VALUE (name), INSERT);
 669       if (*slot)
 670         abort ();
 671       *slot = vnode;
 672     }
 673 }
 674
 675 /* Try to find existing function for identifier ID.  */
 676 struct cgraph_varpool_node *
 677 cgraph_varpool_node_for_identifier (tree id)
 678 {
 679   struct cgraph_varpool_node **slot;
 680
 681   if (TREE_CODE (id) != IDENTIFIER_NODE)
 682     abort ();
 683
 684   if (!cgraph_varpool_hash)
 685     return NULL;
 686
 687   slot = (struct cgraph_varpool_node **)
 688     htab_find_slot_with_hash (cgraph_varpool_hash, id,
 689                               IDENTIFIER_HASH_VALUE (id), NO_INSERT);
 690   if (!slot)
 691     return NULL;
 692   return *slot;
 693 }
 694
 695 /* Notify finalize_compilation_unit that given node is reachable
 696    or needed.  */
 697 void
 698 cgraph_varpool_mark_needed_node (struct cgraph_varpool_node *node)
 699 {
 700   if (!node->needed && node->finalized)
 701     {
 702       node->next_needed = cgraph_varpool_nodes_queue;
 703       cgraph_varpool_nodes_queue = node;
 704       notice_global_symbol (node->decl);
 705     }
 706   node->needed = 1;
 707 }
 708
 709 void
 710 cgraph_varpool_finalize_decl (tree decl)
 711 {
 712   struct cgraph_varpool_node *node = cgraph_varpool_node (decl);
 713
 714   /* The first declaration of a variable that comes through this function
 715      decides whether it is global (in C, has external linkage)
 716      or local (in C, has internal linkage).  So do nothing more
 717      if this function has already run.  */
 718   if (node->finalized)
 719     return;
 720   if (node->needed)
 721     {
 722       node->next_needed = cgraph_varpool_nodes_queue;
 723       cgraph_varpool_nodes_queue = node;
 724       notice_global_symbol (decl);
 725     }
 726   node->finalized = true;
 727
 728   if (/* Externally visible variables must be output.  The exception are
 729          COMDAT functions that must be output only when they are needed.  */
 730       (TREE_PUBLIC (decl) && !DECL_COMDAT (decl))
 731       /* Function whose name is output to the assembler file must be produced.
 732          It is possible to assemble the name later after finalizing the function
 733          and the fact is noticed in assemble_name then.  */
 734       || (DECL_ASSEMBLER_NAME_SET_P (decl)
 735           && TREE_SYMBOL_REFERENCED (DECL_ASSEMBLER_NAME (decl))))
 736     {
 737       cgraph_varpool_mark_needed_node (node);
 738     }
 739 }
 740
 741 bool
 742 cgraph_varpool_assemble_pending_decls (void)
 743 {
 744   bool changed = false;
 745
 746   while (cgraph_varpool_nodes_queue)
 747     {
 748       tree decl = cgraph_varpool_nodes_queue->decl;
 749       struct cgraph_varpool_node *node = cgraph_varpool_nodes_queue;
 750
 751       cgraph_varpool_nodes_queue = cgraph_varpool_nodes_queue->next_needed;
 752       if (!TREE_ASM_WRITTEN (decl))
 753         {
 754           assemble_variable (decl, 0, 1, 0);
 755           changed = true;
 756         }
 757       node->next_needed = NULL;
 758     }
 759   return changed;
 760 }
 761
 762 /* Return true when the DECL can possibly be inlined.  */
 763 bool
 764 cgraph_function_possibly_inlined_p (tree decl)
 765 {
 766   if (!cgraph_global_info_ready)
 767     return (DECL_INLINE (decl) && !flag_really_no_inline);
 768   if (!cgraph_inline_hash)
 769     return false;
 770   return (htab_find_slot (cgraph_inline_hash, DECL_ASSEMBLER_NAME (decl),
 771                           NO_INSERT) != NULL);
 772 }
 773
 774 /* Create clone of E in the node N represented by CALL_EXPR the callgraph.  */
 775 struct cgraph_edge *
 776 cgraph_clone_edge (struct cgraph_edge *e, struct cgraph_node *n, tree call_expr)
 777 {
 778   struct cgraph_edge *new = cgraph_create_edge (n, e->callee, call_expr);
 779
 780   new->inline_failed = e->inline_failed;
 781   return new;
 782 }
 783
 784 /* Create node representing clone of N.  */
 785 struct cgraph_node *
 786 cgraph_clone_node (struct cgraph_node *n)
 787 {
 788   struct cgraph_node *new = cgraph_create_node ();
 789   struct cgraph_edge *e;
 790
 791   new->decl = n->decl;
 792   new->origin = n->origin;
 793   if (new->origin)
 794     {
 795       new->next_nested = new->origin->nested;
 796       new->origin->nested = new;
 797     }
 798   new->analyzed = n->analyzed;
 799   new->local = n->local;
 800   new->global = n->global;
 801   new->rtl = n->rtl;
 802
 803   for (e = n->callees;e; e=e->next_callee)
 804     cgraph_clone_edge (e, new, e->call_expr);
 805
 806   new->next_clone = n->next_clone;
 807   n->next_clone = new;
 808
 809   return new;
 810 }
 811 #include "gt-cgraph.h"