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