gcc/cgraph.c

   1 /* Callgraph handling code.
   2    Copyright (C) 2003, 2004, 2005 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 an 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 inliner.
  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 "tree-inline.h"
  88 #include "langhooks.h"
  89 #include "hashtab.h"
  90 #include "toplev.h"
  91 #include "flags.h"
  92 #include "ggc.h"
  93 #include "debug.h"
  94 #include "target.h"
  95 #include "basic-block.h"
  96 #include "cgraph.h"
  97 #include "varray.h"
  98 #include "output.h"
  99 #include "intl.h"
 100
 101 static void cgraph_node_remove_callers (struct cgraph_node *node);
 102 static inline void cgraph_edge_remove_caller (struct cgraph_edge *e);
 103 static inline void cgraph_edge_remove_callee (struct cgraph_edge *e);
 104
 105 /* Hash table used to convert declarations into nodes.  */
 106 static GTY((param_is (struct cgraph_node))) htab_t cgraph_hash;
 107
 108 /* The linked list of cgraph nodes.  */
 109 struct cgraph_node *cgraph_nodes;
 110
 111 /* Queue of cgraph nodes scheduled to be lowered.  */
 112 struct cgraph_node *cgraph_nodes_queue;
 113
 114 /* Number of nodes in existence.  */
 115 int cgraph_n_nodes;
 116
 117 /* Maximal uid used in cgraph nodes.  */
 118 int cgraph_max_uid;
 119
 120 /* Set when whole unit has been analyzed so we can access global info.  */
 121 bool cgraph_global_info_ready = false;
 122
 123 /* Set when the cgraph is fully build and the basic flags are computed.  */
 124 bool cgraph_function_flags_ready = false;
 125
 126 /* Hash table used to convert declarations into nodes.  */
 127 static GTY((param_is (struct cgraph_varpool_node))) htab_t cgraph_varpool_hash;
 128
 129 /* Queue of cgraph nodes scheduled to be lowered and output.  */
 130 struct cgraph_varpool_node *cgraph_varpool_nodes_queue, *cgraph_varpool_first_unanalyzed_node;
 131
 132
 133 /* The linked list of cgraph varpool nodes.  */
 134 static GTY(()) struct cgraph_varpool_node *cgraph_varpool_nodes;
 135
 136 /* End of the varpool queue.  Needs to be QTYed to work with PCH.  */
 137 static GTY(()) struct cgraph_varpool_node *cgraph_varpool_last_needed_node;
 138
 139 static hashval_t hash_node (const void *);
 140 static int eq_node (const void *, const void *);
 141
 142 /* Returns a hash code for P.  */
 143
 144 static hashval_t
 145 hash_node (const void *p)
 146 {
 147   const struct cgraph_node *n = p;
 148   return (hashval_t) DECL_UID (n->decl);
 149 }
 150
 151 /* Returns nonzero if P1 and P2 are equal.  */
 152
 153 static int
 154 eq_node (const void *p1, const void *p2)
 155 {
 156   const struct cgraph_node *n1 = p1, *n2 = p2;
 157   return DECL_UID (n1->decl) == DECL_UID (n2->decl);
 158 }
 159
 160 /* Allocate new callgraph node and insert it into basic data structures.  */
 161 static struct cgraph_node *
 162 cgraph_create_node (void)
 163 {
 164   struct cgraph_node *node;
 165
 166   node = ggc_alloc_cleared (sizeof (*node));
 167   node->next = cgraph_nodes;
 168   node->uid = cgraph_max_uid++;
 169   if (cgraph_nodes)
 170     cgraph_nodes->previous = node;
 171   node->previous = NULL;
 172   cgraph_nodes = node;
 173   cgraph_n_nodes++;
 174   return node;
 175 }
 176
 177 /* Return cgraph node assigned to DECL.  Create new one when needed.  */
 178 struct cgraph_node *
 179 cgraph_node (tree decl)
 180 {
 181   struct cgraph_node key, *node, **slot;
 182
 183   gcc_assert (TREE_CODE (decl) == FUNCTION_DECL);
 184
 185   if (!cgraph_hash)
 186     cgraph_hash = htab_create_ggc (10, hash_node, eq_node, NULL);
 187
 188   key.decl = decl;
 189
 190   slot = (struct cgraph_node **) htab_find_slot (cgraph_hash, &key, INSERT);
 191
 192   if (*slot)
 193     return *slot;
 194
 195   node = cgraph_create_node ();
 196   node->decl = decl;
 197   *slot = node;
 198   if (DECL_CONTEXT (decl) && TREE_CODE (DECL_CONTEXT (decl)) == FUNCTION_DECL)
 199     {
 200       node->origin = cgraph_node (DECL_CONTEXT (decl));
 201       node->next_nested = node->origin->nested;
 202       node->origin->nested = node;
 203     }
 204   return node;
 205 }
 206
 207 /* Compare ASMNAME with the DECL_ASSEMBLER_NAME of DECL.  */
 208
 209 static bool
 210 decl_assembler_name_equal (tree decl, tree asmname)
 211 {
 212   tree decl_asmname = DECL_ASSEMBLER_NAME (decl);
 213
 214   if (decl_asmname == asmname)
 215     return true;
 216
 217   /* If the target assembler name was set by the user, things are trickier.
 218      We have a leading '*' to begin with.  After that, it's arguable what
 219      is the correct thing to do with -fleading-underscore.  Arguably, we've
 220      historically been doing the wrong thing in assemble_alias by always
 221      printing the leading underscore.  Since we're not changing that, make
 222      sure user_label_prefix follows the '*' before matching.  */
 223   if (IDENTIFIER_POINTER (decl_asmname)[0] == '*')
 224     {
 225       const char *decl_str = IDENTIFIER_POINTER (decl_asmname) + 1;
 226       size_t ulp_len = strlen (user_label_prefix);
 227
 228       if (ulp_len == 0)
 229         ;
 230       else if (strncmp (decl_str, user_label_prefix, ulp_len) == 0)
 231         decl_str += ulp_len;
 232       else
 233         return false;
 234
 235       return strcmp (decl_str, IDENTIFIER_POINTER (asmname)) == 0;
 236     }
 237
 238   return false;
 239 }
 240
 241
 242 /* Return the cgraph node that has ASMNAME for its DECL_ASSEMBLER_NAME.
 243    Return NULL if there's no such node.  */
 244
 245 struct cgraph_node *
 246 cgraph_node_for_asm (tree asmname)
 247 {
 248   struct cgraph_node *node;
 249
 250   for (node = cgraph_nodes; node ; node = node->next)
 251     if (decl_assembler_name_equal (node->decl, asmname))
 252       return node;
 253
 254   return NULL;
 255 }
 256
 257 /* Return callgraph edge representing CALL_EXPR.  */
 258 struct cgraph_edge *
 259 cgraph_edge (struct cgraph_node *node, tree call_expr)
 260 {
 261   struct cgraph_edge *e;
 262
 263   /* This loop may turn out to be performance problem.  In such case adding
 264      hashtables into call nodes with very many edges is probably best
 265      solution.  It is not good idea to add pointer into CALL_EXPR itself
 266      because we want to make possible having multiple cgraph nodes representing
 267      different clones of the same body before the body is actually cloned.  */
 268   for (e = node->callees; e; e= e->next_callee)
 269     if (e->call_expr == call_expr)
 270       break;
 271   return e;
 272 }
 273
 274 /* Create edge from CALLER to CALLEE in the cgraph.  */
 275
 276 struct cgraph_edge *
 277 cgraph_create_edge (struct cgraph_node *caller, struct cgraph_node *callee,
 278                     tree call_expr)
 279 {
 280   struct cgraph_edge *edge = ggc_alloc (sizeof (struct cgraph_edge));
 281 #ifdef ENABLE_CHECKING
 282   struct cgraph_edge *e;
 283
 284   for (e = caller->callees; e; e = e->next_callee)
 285     gcc_assert (e->call_expr != call_expr);
 286 #endif
 287
 288   gcc_assert (TREE_CODE (call_expr) == CALL_EXPR);
 289
 290   if (!DECL_SAVED_TREE (callee->decl))
 291     edge->inline_failed = N_("function body not available");
 292   else if (callee->local.redefined_extern_inline)
 293     edge->inline_failed = N_("redefined extern inline functions are not "
 294                              "considered for inlining");
 295   else if (callee->local.inlinable)
 296     edge->inline_failed = N_("function not considered for inlining");
 297   else
 298     edge->inline_failed = N_("function not inlinable");
 299
 300   edge->aux = NULL;
 301
 302   edge->caller = caller;
 303   edge->callee = callee;
 304   edge->call_expr = call_expr;
 305   edge->prev_caller = NULL;
 306   edge->next_caller = callee->callers;
 307   if (callee->callers)
 308     callee->callers->prev_caller = edge;
 309   edge->prev_callee = NULL;
 310   edge->next_callee = caller->callees;
 311   if (caller->callees)
 312     caller->callees->prev_callee = edge;
 313   caller->callees = edge;
 314   callee->callers = edge;
 315   return edge;
 316 }
 317
 318 /* Remove the edge E from the list of the callers of the callee.  */
 319
 320 static inline void
 321 cgraph_edge_remove_callee (struct cgraph_edge *e)
 322 {
 323   if (e->prev_caller)
 324     e->prev_caller->next_caller = e->next_caller;
 325   if (e->next_caller)
 326     e->next_caller->prev_caller = e->prev_caller;
 327   if (!e->prev_caller)
 328     e->callee->callers = e->next_caller;
 329 }
 330
 331 /* Remove the edge E from the list of the callees of the caller.  */
 332
 333 static inline void
 334 cgraph_edge_remove_caller (struct cgraph_edge *e)
 335 {
 336   if (e->prev_callee)
 337     e->prev_callee->next_callee = e->next_callee;
 338   if (e->next_callee)
 339     e->next_callee->prev_callee = e->prev_callee;
 340   if (!e->prev_callee)
 341     e->caller->callees = e->next_callee;
 342 }
 343
 344 /* Remove the edge E in the cgraph.  */
 345
 346 void
 347 cgraph_remove_edge (struct cgraph_edge *e)
 348 {
 349   /* Remove from callers list of the callee.  */
 350   cgraph_edge_remove_callee (e);
 351
 352   /* Remove from callees list of the callers.  */
 353   cgraph_edge_remove_caller (e);
 354 }
 355
 356 /* Redirect callee of E to N.  The function does not update underlying
 357    call expression.  */
 358
 359 void
 360 cgraph_redirect_edge_callee (struct cgraph_edge *e, struct cgraph_node *n)
 361 {
 362   /* Remove from callers list of the current callee.  */
 363   cgraph_edge_remove_callee (e);
 364
 365   /* Insert to callers list of the new callee.  */
 366   e->prev_caller = NULL;
 367   if (n->callers)
 368     n->callers->prev_caller = e;
 369   e->next_caller = n->callers;
 370   n->callers = e;
 371   e->callee = n;
 372 }
 373
 374 /* Remove all callees from the node.  */
 375
 376 void
 377 cgraph_node_remove_callees (struct cgraph_node *node)
 378 {
 379   struct cgraph_edge *e;
 380
 381   /* It is sufficient to remove the edges from the lists of callers of
 382      the callees.  The callee list of the node can be zapped with one
 383      assignment.  */
 384   for (e = node->callees; e; e = e->next_callee)
 385     cgraph_edge_remove_callee (e);
 386   node->callees = NULL;
 387 }
 388
 389 /* Remove all callers from the node.  */
 390
 391 static void
 392 cgraph_node_remove_callers (struct cgraph_node *node)
 393 {
 394   struct cgraph_edge *e;
 395
 396   /* It is sufficient to remove the edges from the lists of callees of
 397      the callers.  The caller list of the node can be zapped with one
 398      assignment.  */
 399   for (e = node->callers; e; e = e->next_caller)
 400     cgraph_edge_remove_caller (e);
 401   node->callers = NULL;
 402 }
 403
 404 /* Remove the node from cgraph.  */
 405
 406 void
 407 cgraph_remove_node (struct cgraph_node *node)
 408 {
 409   void **slot;
 410   bool kill_body = false;
 411
 412   cgraph_node_remove_callers (node);
 413   cgraph_node_remove_callees (node);
 414   while (node->nested)
 415     cgraph_remove_node (node->nested);
 416   if (node->origin)
 417     {
 418       struct cgraph_node **node2 = &node->origin->nested;
 419
 420       while (*node2 != node)
 421         node2 = &(*node2)->next_nested;
 422       *node2 = node->next_nested;
 423     }
 424   if (node->previous)
 425     node->previous->next = node->next;
 426   else
 427     cgraph_nodes = node->next;
 428   if (node->next)
 429     node->next->previous = node->previous;
 430   slot = htab_find_slot (cgraph_hash, node, NO_INSERT);
 431   if (*slot == node)
 432     {
 433       if (node->next_clone)
 434       {
 435         *slot = node->next_clone;
 436         node->next_clone->prev_clone = NULL;
 437       }
 438       else
 439         {
 440           htab_clear_slot (cgraph_hash, slot);
 441           kill_body = true;
 442         }
 443     }
 444   else
 445     {
 446       node->prev_clone->next_clone = node->next_clone;
 447       if (node->next_clone)
 448         node->next_clone->prev_clone = node->prev_clone;
 449     }
 450
 451   /* While all the clones are removed after being proceeded, the function
 452      itself is kept in the cgraph even after it is compiled.  Check whether
 453      we are done with this body and reclaim it proactively if this is the case.
 454      */
 455   if (!kill_body && *slot)
 456     {
 457       struct cgraph_node *n = *slot;
 458       if (!n->next_clone && !n->global.inlined_to
 459           && (TREE_ASM_WRITTEN (n->decl) || DECL_EXTERNAL (n->decl)))
 460         kill_body = true;
 461     }
 462
 463   if (kill_body && !dump_enabled_p (TDI_tree_all) && flag_unit_at_a_time)
 464     {
 465       DECL_SAVED_TREE (node->decl) = NULL;
 466       DECL_STRUCT_FUNCTION (node->decl) = NULL;
 467       DECL_INITIAL (node->decl) = error_mark_node;
 468     }
 469   cgraph_n_nodes--;
 470   /* Do not free the structure itself so the walk over chain can continue.  */
 471 }
 472
 473 /* Notify finalize_compilation_unit that given node is reachable.  */
 474
 475 void
 476 cgraph_mark_reachable_node (struct cgraph_node *node)
 477 {
 478   if (!node->reachable && node->local.finalized)
 479     {
 480       notice_global_symbol (node->decl);
 481       node->reachable = 1;
 482       gcc_assert (!cgraph_global_info_ready);
 483
 484       node->next_needed = cgraph_nodes_queue;
 485       cgraph_nodes_queue = node;
 486     }
 487 }
 488
 489 /* Likewise indicate that a node is needed, i.e. reachable via some
 490    external means.  */
 491
 492 void
 493 cgraph_mark_needed_node (struct cgraph_node *node)
 494 {
 495   node->needed = 1;
 496   cgraph_mark_reachable_node (node);
 497 }
 498
 499 /* Return local info for the compiled function.  */
 500
 501 struct cgraph_local_info *
 502 cgraph_local_info (tree decl)
 503 {
 504   struct cgraph_node *node;
 505
 506   gcc_assert (TREE_CODE (decl) == FUNCTION_DECL);
 507   node = cgraph_node (decl);
 508   return &node->local;
 509 }
 510
 511 /* Return local info for the compiled function.  */
 512
 513 struct cgraph_global_info *
 514 cgraph_global_info (tree decl)
 515 {
 516   struct cgraph_node *node;
 517
 518   gcc_assert (TREE_CODE (decl) == FUNCTION_DECL && cgraph_global_info_ready);
 519   node = cgraph_node (decl);
 520   return &node->global;
 521 }
 522
 523 /* Return local info for the compiled function.  */
 524
 525 struct cgraph_rtl_info *
 526 cgraph_rtl_info (tree decl)
 527 {
 528   struct cgraph_node *node;
 529
 530   gcc_assert (TREE_CODE (decl) == FUNCTION_DECL);
 531   node = cgraph_node (decl);
 532   if (decl != current_function_decl
 533       && !TREE_ASM_WRITTEN (node->decl))
 534     return NULL;
 535   return &node->rtl;
 536 }
 537
 538 /* Return name of the node used in debug output.  */
 539 const char *
 540 cgraph_node_name (struct cgraph_node *node)
 541 {
 542   return lang_hooks.decl_printable_name (node->decl, 2);
 543 }
 544
 545 /* Return name of the node used in debug output.  */
 546 static const char *
 547 cgraph_varpool_node_name (struct cgraph_varpool_node *node)
 548 {
 549   return lang_hooks.decl_printable_name (node->decl, 2);
 550 }
 551
 552 /* Dump given cgraph node.  */
 553 void
 554 dump_cgraph_node (FILE *f, struct cgraph_node *node)
 555 {
 556   struct cgraph_edge *edge;
 557   fprintf (f, "%s/%i:", cgraph_node_name (node), node->uid);
 558   if (node->global.inlined_to)
 559     fprintf (f, " (inline copy in %s/%i)",
 560              cgraph_node_name (node->global.inlined_to),
 561              node->global.inlined_to->uid);
 562   if (node->local.self_insns)
 563     fprintf (f, " %i insns", node->local.self_insns);
 564   if (node->global.insns && node->global.insns != node->local.self_insns)
 565     fprintf (f, " (%i after inlining)", node->global.insns);
 566   if (node->origin)
 567     fprintf (f, " nested in: %s", cgraph_node_name (node->origin));
 568   if (node->needed)
 569     fprintf (f, " needed");
 570   else if (node->reachable)
 571     fprintf (f, " reachable");
 572   if (DECL_SAVED_TREE (node->decl))
 573     fprintf (f, " tree");
 574   if (node->output)
 575     fprintf (f, " output");
 576   if (node->local.local)
 577     fprintf (f, " local");
 578   if (node->local.disregard_inline_limits)
 579     fprintf (f, " always_inline");
 580   else if (node->local.inlinable)
 581     fprintf (f, " inlinable");
 582   if (TREE_ASM_WRITTEN (node->decl))
 583     fprintf (f, " asm_written");
 584
 585   fprintf (f, "\n  called by: ");
 586   for (edge = node->callers; edge; edge = edge->next_caller)
 587     {
 588       fprintf (f, "%s/%i ", cgraph_node_name (edge->caller),
 589                edge->caller->uid);
 590       if (!edge->inline_failed)
 591         fprintf(f, "(inlined) ");
 592     }
 593
 594   fprintf (f, "\n  calls: ");
 595   for (edge = node->callees; edge; edge = edge->next_callee)
 596     {
 597       fprintf (f, "%s/%i ", cgraph_node_name (edge->callee),
 598                edge->callee->uid);
 599       if (!edge->inline_failed)
 600         fprintf(f, "(inlined) ");
 601     }
 602   fprintf (f, "\n");
 603 }
 604
 605 /* Dump the callgraph.  */
 606
 607 void
 608 dump_cgraph (FILE *f)
 609 {
 610   struct cgraph_node *node;
 611
 612   fprintf (f, "callgraph:\n\n");
 613   for (node = cgraph_nodes; node; node = node->next)
 614     dump_cgraph_node (f, node);
 615 }
 616
 617 /* Dump given cgraph node.  */
 618 void
 619 dump_cgraph_varpool_node (FILE *f, struct cgraph_varpool_node *node)
 620 {
 621   fprintf (f, "%s:", cgraph_varpool_node_name (node));
 622   if (DECL_INITIAL (node->decl))
 623     fprintf (f, " initialized");
 624   if (node->needed)
 625     fprintf (f, " needed");
 626   if (node->analyzed)
 627     fprintf (f, " analyzed");
 628   if (node->finalized)
 629     fprintf (f, " finalized");
 630   if (node->output)
 631     fprintf (f, " output");
 632   fprintf (f, "\n");
 633 }
 634
 635 /* Dump the callgraph.  */
 636
 637 void
 638 dump_varpool (FILE *f)
 639 {
 640   struct cgraph_varpool_node *node;
 641
 642   fprintf (f, "variable pool:\n\n");
 643   for (node = cgraph_varpool_nodes; node; node = node->next_needed)
 644     dump_cgraph_varpool_node (f, node);
 645 }
 646
 647 /* Returns a hash code for P.  */
 648
 649 static hashval_t
 650 hash_varpool_node (const void *p)
 651 {
 652   const struct cgraph_varpool_node *n = p;
 653   return (hashval_t) DECL_UID (n->decl);
 654 }
 655
 656 /* Returns nonzero if P1 and P2 are equal.  */
 657
 658 static int
 659 eq_varpool_node (const void *p1, const void *p2)
 660 {
 661   const struct cgraph_varpool_node *n1 = p1, *n2 = p2;
 662   return DECL_UID (n1->decl) == DECL_UID (n2->decl);
 663 }
 664
 665 /* Return cgraph_varpool node assigned to DECL.  Create new one when needed.  */
 666 struct cgraph_varpool_node *
 667 cgraph_varpool_node (tree decl)
 668 {
 669   struct cgraph_varpool_node key, *node, **slot;
 670
 671   gcc_assert (DECL_P (decl) && TREE_CODE (decl) != FUNCTION_DECL);
 672
 673   if (!cgraph_varpool_hash)
 674     cgraph_varpool_hash = htab_create_ggc (10, hash_varpool_node,
 675                                            eq_varpool_node, NULL);
 676   key.decl = decl;
 677   slot = (struct cgraph_varpool_node **)
 678     htab_find_slot (cgraph_varpool_hash, &key, INSERT);
 679   if (*slot)
 680     return *slot;
 681   node = ggc_alloc_cleared (sizeof (*node));
 682   node->decl = decl;
 683   node->next = cgraph_varpool_nodes;
 684   cgraph_varpool_nodes = node;
 685   *slot = node;
 686   return node;
 687 }
 688
 689 struct cgraph_varpool_node *
 690 cgraph_varpool_node_for_asm (tree asmname)
 691 {
 692   struct cgraph_varpool_node *node;
 693
 694   for (node = cgraph_varpool_nodes; node ; node = node->next)
 695     if (decl_assembler_name_equal (node->decl, asmname))
 696       return node;
 697
 698   return NULL;
 699 }
 700
 701 /* Set the DECL_ASSEMBLER_NAME and update cgraph hashtables.  */
 702 void
 703 change_decl_assembler_name (tree decl, tree name)
 704 {
 705   if (!DECL_ASSEMBLER_NAME_SET_P (decl))
 706     {
 707       SET_DECL_ASSEMBLER_NAME (decl, name);
 708       return;
 709     }
 710   if (name == DECL_ASSEMBLER_NAME (decl))
 711     return;
 712
 713   if (TREE_SYMBOL_REFERENCED (DECL_ASSEMBLER_NAME (decl))
 714       && DECL_RTL_SET_P (decl))
 715     warning ("%D renamed after being referenced in assembly", decl);
 716
 717   SET_DECL_ASSEMBLER_NAME (decl, name);
 718 }
 719
 720 /* Helper function for finalization code - add node into lists so it will
 721    be analyzed and compiled.  */
 722 void
 723 cgraph_varpool_enqueue_needed_node (struct cgraph_varpool_node *node)
 724 {
 725   if (cgraph_varpool_last_needed_node)
 726     cgraph_varpool_last_needed_node->next_needed = node;
 727   cgraph_varpool_last_needed_node = node;
 728   node->next_needed = NULL;
 729   if (!cgraph_varpool_nodes_queue)
 730     cgraph_varpool_nodes_queue = node;
 731   if (!cgraph_varpool_first_unanalyzed_node)
 732     cgraph_varpool_first_unanalyzed_node = node;
 733   notice_global_symbol (node->decl);
 734 }
 735
 736 /* Reset the queue of needed nodes.  */
 737 void
 738 cgraph_varpool_reset_queue (void)
 739 {
 740   cgraph_varpool_last_needed_node = NULL;
 741   cgraph_varpool_nodes_queue = NULL;
 742   cgraph_varpool_first_unanalyzed_node = NULL;
 743 }
 744
 745 /* Notify finalize_compilation_unit that given node is reachable
 746    or needed.  */
 747 void
 748 cgraph_varpool_mark_needed_node (struct cgraph_varpool_node *node)
 749 {
 750   if (!node->needed && node->finalized)
 751     cgraph_varpool_enqueue_needed_node (node);
 752   node->needed = 1;
 753 }
 754
 755 /* Determine if variable DECL is needed.  That is, visible to something
 756    either outside this translation unit, something magic in the system
 757    configury, or (if not doing unit-at-a-time) to something we haven't
 758    seen yet.  */
 759
 760 bool
 761 decide_is_variable_needed (struct cgraph_varpool_node *node, tree decl)
 762 {
 763   /* If the user told us it is used, then it must be so.  */
 764   if (lookup_attribute ("used", DECL_ATTRIBUTES (decl)))
 765     return true;
 766
 767   /* ??? If the assembler name is set by hand, it is possible to assemble
 768      the name later after finalizing the function and the fact is noticed
 769      in assemble_name then.  This is arguably a bug.  */
 770   if (DECL_ASSEMBLER_NAME_SET_P (decl)
 771       && TREE_SYMBOL_REFERENCED (DECL_ASSEMBLER_NAME (decl)))
 772     return true;
 773
 774   /* If we decided it was needed before, but at the time we didn't have
 775      the definition available, then it's still needed.  */
 776   if (node->needed)
 777     return true;
 778
 779   /* Externally visible functions must be output.  The exception is
 780      COMDAT functions that must be output only when they are needed.  */
 781   if (TREE_PUBLIC (decl) && !DECL_COMDAT (decl) && !DECL_EXTERNAL (decl))
 782     return true;
 783
 784   if (flag_unit_at_a_time)
 785     return false;
 786
 787   /* If not doing unit at a time, then we'll only defer this function
 788      if its marked for inlining.  Otherwise we want to emit it now.  */
 789
 790   /* We want to emit COMDAT variables only when absolutely necessary.  */
 791   if (DECL_COMDAT (decl))
 792     return false;
 793   return true;
 794 }
 795
 796 void
 797 cgraph_varpool_finalize_decl (tree decl)
 798 {
 799   struct cgraph_varpool_node *node = cgraph_varpool_node (decl);
 800
 801   /* The first declaration of a variable that comes through this function
 802      decides whether it is global (in C, has external linkage)
 803      or local (in C, has internal linkage).  So do nothing more
 804      if this function has already run.  */
 805   if (node->finalized)
 806     {
 807       if (cgraph_global_info_ready || !flag_unit_at_a_time)
 808         cgraph_varpool_assemble_pending_decls ();
 809       return;
 810     }
 811   if (node->needed)
 812     cgraph_varpool_enqueue_needed_node (node);
 813   node->finalized = true;
 814
 815   if (decide_is_variable_needed (node, decl))
 816     cgraph_varpool_mark_needed_node (node);
 817   if (cgraph_global_info_ready || !flag_unit_at_a_time)
 818     cgraph_varpool_assemble_pending_decls ();
 819 }
 820
 821 /* Return true when the DECL can possibly be inlined.  */
 822 bool
 823 cgraph_function_possibly_inlined_p (tree decl)
 824 {
 825   if (!cgraph_global_info_ready)
 826     return (DECL_INLINE (decl) && !flag_really_no_inline);
 827   return DECL_POSSIBLY_INLINED (decl);
 828 }
 829
 830 /* Create clone of E in the node N represented by CALL_EXPR the callgraph.  */
 831 struct cgraph_edge *
 832 cgraph_clone_edge (struct cgraph_edge *e, struct cgraph_node *n, tree call_expr)
 833 {
 834   struct cgraph_edge *new = cgraph_create_edge (n, e->callee, call_expr);
 835
 836   new->inline_failed = e->inline_failed;
 837   return new;
 838 }
 839
 840 /* Create node representing clone of N.  */
 841 struct cgraph_node *
 842 cgraph_clone_node (struct cgraph_node *n)
 843 {
 844   struct cgraph_node *new = cgraph_create_node ();
 845   struct cgraph_edge *e;
 846
 847   new->decl = n->decl;
 848   new->origin = n->origin;
 849   if (new->origin)
 850     {
 851       new->next_nested = new->origin->nested;
 852       new->origin->nested = new;
 853     }
 854   new->analyzed = n->analyzed;
 855   new->local = n->local;
 856   new->global = n->global;
 857   new->rtl = n->rtl;
 858
 859   for (e = n->callees;e; e=e->next_callee)
 860     cgraph_clone_edge (e, new, e->call_expr);
 861
 862   new->next_clone = n->next_clone;
 863   new->prev_clone = n;
 864   n->next_clone = new;
 865   if (new->next_clone)
 866     new->next_clone->prev_clone = new;
 867
 868   return new;
 869 }
 870
 871 /* NODE is no longer nested function; update cgraph accordingly.  */
 872 void
 873 cgraph_unnest_node (struct cgraph_node *node)
 874 {
 875   struct cgraph_node **node2 = &node->origin->nested;
 876   gcc_assert (node->origin);
 877
 878   while (*node2 != node)
 879     node2 = &(*node2)->next_nested;
 880   *node2 = node->next_nested;
 881   node->origin = NULL;
 882 }
 883 #include "gt-cgraph.h"