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