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.externally_visible)
 586     fprintf (f, " externally_visible");
 587   if (node->local.finalized)
 588     fprintf (f, " finalized");
 589   if (node->local.disregard_inline_limits)
 590     fprintf (f, " always_inline");
 591   else if (node->local.inlinable)
 592     fprintf (f, " inlinable");
 593   if (node->local.redefined_extern_inline)
 594     fprintf (f, " redefined_extern_inline");
 595   if (TREE_ASM_WRITTEN (node->decl))
 596     fprintf (f, " asm_written");
 597
 598   fprintf (f, "\n  called by: ");
 599   for (edge = node->callers; edge; edge = edge->next_caller)
 600     {
 601       fprintf (f, "%s/%i ", cgraph_node_name (edge->caller),
 602                edge->caller->uid);
 603       if (edge->count)
 604         fprintf (f, "("HOST_WIDEST_INT_PRINT_DEC"x) ",
 605                  (HOST_WIDEST_INT)edge->count);
 606       if (!edge->inline_failed)
 607         fprintf(f, "(inlined) ");
 608     }
 609
 610   fprintf (f, "\n  calls: ");
 611   for (edge = node->callees; edge; edge = edge->next_callee)
 612     {
 613       fprintf (f, "%s/%i ", cgraph_node_name (edge->callee),
 614                edge->callee->uid);
 615       if (!edge->inline_failed)
 616         fprintf(f, "(inlined) ");
 617     }
 618   fprintf (f, "\n");
 619 }
 620
 621 /* Dump the callgraph.  */
 622
 623 void
 624 dump_cgraph (FILE *f)
 625 {
 626   struct cgraph_node *node;
 627
 628   fprintf (f, "callgraph:\n\n");
 629   for (node = cgraph_nodes; node; node = node->next)
 630     dump_cgraph_node (f, node);
 631 }
 632
 633 /* Dump given cgraph node.  */
 634 void
 635 dump_cgraph_varpool_node (FILE *f, struct cgraph_varpool_node *node)
 636 {
 637   fprintf (f, "%s:", cgraph_varpool_node_name (node));
 638   if (DECL_INITIAL (node->decl))
 639     fprintf (f, " initialized");
 640   if (node->needed)
 641     fprintf (f, " needed");
 642   if (node->analyzed)
 643     fprintf (f, " analyzed");
 644   if (node->finalized)
 645     fprintf (f, " finalized");
 646   if (node->output)
 647     fprintf (f, " output");
 648   if (node->externally_visible)
 649     fprintf (f, " externally_visible");
 650   fprintf (f, "\n");
 651 }
 652
 653 /* Dump the callgraph.  */
 654
 655 void
 656 dump_varpool (FILE *f)
 657 {
 658   struct cgraph_varpool_node *node;
 659
 660   fprintf (f, "variable pool:\n\n");
 661   for (node = cgraph_varpool_nodes; node; node = node->next_needed)
 662     dump_cgraph_varpool_node (f, node);
 663 }
 664
 665 /* Returns a hash code for P.  */
 666
 667 static hashval_t
 668 hash_varpool_node (const void *p)
 669 {
 670   const struct cgraph_varpool_node *n = p;
 671   return (hashval_t) DECL_UID (n->decl);
 672 }
 673
 674 /* Returns nonzero if P1 and P2 are equal.  */
 675
 676 static int
 677 eq_varpool_node (const void *p1, const void *p2)
 678 {
 679   const struct cgraph_varpool_node *n1 = p1, *n2 = p2;
 680   return DECL_UID (n1->decl) == DECL_UID (n2->decl);
 681 }
 682
 683 /* Return cgraph_varpool node assigned to DECL.  Create new one when needed.  */
 684 struct cgraph_varpool_node *
 685 cgraph_varpool_node (tree decl)
 686 {
 687   struct cgraph_varpool_node key, *node, **slot;
 688
 689   gcc_assert (DECL_P (decl) && TREE_CODE (decl) != FUNCTION_DECL);
 690
 691   if (!cgraph_varpool_hash)
 692     cgraph_varpool_hash = htab_create_ggc (10, hash_varpool_node,
 693                                            eq_varpool_node, NULL);
 694   key.decl = decl;
 695   slot = (struct cgraph_varpool_node **)
 696     htab_find_slot (cgraph_varpool_hash, &key, INSERT);
 697   if (*slot)
 698     return *slot;
 699   node = ggc_alloc_cleared (sizeof (*node));
 700   node->decl = decl;
 701   node->next = cgraph_varpool_nodes;
 702   cgraph_varpool_nodes = node;
 703   *slot = node;
 704   return node;
 705 }
 706
 707 struct cgraph_varpool_node *
 708 cgraph_varpool_node_for_asm (tree asmname)
 709 {
 710   struct cgraph_varpool_node *node;
 711
 712   for (node = cgraph_varpool_nodes; node ; node = node->next)
 713     if (decl_assembler_name_equal (node->decl, asmname))
 714       return node;
 715
 716   return NULL;
 717 }
 718
 719 /* Set the DECL_ASSEMBLER_NAME and update cgraph hashtables.  */
 720 void
 721 change_decl_assembler_name (tree decl, tree name)
 722 {
 723   if (!DECL_ASSEMBLER_NAME_SET_P (decl))
 724     {
 725       SET_DECL_ASSEMBLER_NAME (decl, name);
 726       return;
 727     }
 728   if (name == DECL_ASSEMBLER_NAME (decl))
 729     return;
 730
 731   if (TREE_SYMBOL_REFERENCED (DECL_ASSEMBLER_NAME (decl))
 732       && DECL_RTL_SET_P (decl))
 733     warning (0, "%D renamed after being referenced in assembly", decl);
 734
 735   SET_DECL_ASSEMBLER_NAME (decl, name);
 736 }
 737
 738 /* Helper function for finalization code - add node into lists so it will
 739    be analyzed and compiled.  */
 740 void
 741 cgraph_varpool_enqueue_needed_node (struct cgraph_varpool_node *node)
 742 {
 743   if (cgraph_varpool_last_needed_node)
 744     cgraph_varpool_last_needed_node->next_needed = node;
 745   cgraph_varpool_last_needed_node = node;
 746   node->next_needed = NULL;
 747   if (!cgraph_varpool_nodes_queue)
 748     cgraph_varpool_nodes_queue = node;
 749   if (!cgraph_varpool_first_unanalyzed_node)
 750     cgraph_varpool_first_unanalyzed_node = node;
 751   notice_global_symbol (node->decl);
 752 }
 753
 754 /* Reset the queue of needed nodes.  */
 755 void
 756 cgraph_varpool_reset_queue (void)
 757 {
 758   cgraph_varpool_last_needed_node = NULL;
 759   cgraph_varpool_nodes_queue = NULL;
 760   cgraph_varpool_first_unanalyzed_node = NULL;
 761 }
 762
 763 /* Notify finalize_compilation_unit that given node is reachable
 764    or needed.  */
 765 void
 766 cgraph_varpool_mark_needed_node (struct cgraph_varpool_node *node)
 767 {
 768   if (!node->needed && node->finalized)
 769     cgraph_varpool_enqueue_needed_node (node);
 770   node->needed = 1;
 771 }
 772
 773 /* Determine if variable DECL is needed.  That is, visible to something
 774    either outside this translation unit, something magic in the system
 775    configury, or (if not doing unit-at-a-time) to something we haven't
 776    seen yet.  */
 777
 778 bool
 779 decide_is_variable_needed (struct cgraph_varpool_node *node, tree decl)
 780 {
 781   /* If the user told us it is used, then it must be so.  */
 782   if (lookup_attribute ("used", DECL_ATTRIBUTES (decl)))
 783     return true;
 784
 785   /* ??? If the assembler name is set by hand, it is possible to assemble
 786      the name later after finalizing the function and the fact is noticed
 787      in assemble_name then.  This is arguably a bug.  */
 788   if (DECL_ASSEMBLER_NAME_SET_P (decl)
 789       && TREE_SYMBOL_REFERENCED (DECL_ASSEMBLER_NAME (decl)))
 790     return true;
 791
 792   /* If we decided it was needed before, but at the time we didn't have
 793      the definition available, then it's still needed.  */
 794   if (node->needed)
 795     return true;
 796
 797   /* Externally visible variables must be output.  The exception is
 798      COMDAT variables that must be output only when they are needed.  */
 799   if (TREE_PUBLIC (decl) && !DECL_COMDAT (decl) && !DECL_EXTERNAL (decl))
 800     return true;
 801
 802   if (flag_unit_at_a_time)
 803     return false;
 804
 805   /* If not doing unit at a time, then we'll only defer this function
 806      if its marked for inlining.  Otherwise we want to emit it now.  */
 807
 808   /* We want to emit COMDAT variables only when absolutely necessary.  */
 809   if (DECL_COMDAT (decl))
 810     return false;
 811   return true;
 812 }
 813
 814 void
 815 cgraph_varpool_finalize_decl (tree decl)
 816 {
 817   struct cgraph_varpool_node *node = cgraph_varpool_node (decl);
 818
 819   /* The first declaration of a variable that comes through this function
 820      decides whether it is global (in C, has external linkage)
 821      or local (in C, has internal linkage).  So do nothing more
 822      if this function has already run.  */
 823   if (node->finalized)
 824     {
 825       if (cgraph_global_info_ready || !flag_unit_at_a_time)
 826         cgraph_varpool_assemble_pending_decls ();
 827       return;
 828     }
 829   if (node->needed)
 830     cgraph_varpool_enqueue_needed_node (node);
 831   node->finalized = true;
 832
 833   if (decide_is_variable_needed (node, decl))
 834     cgraph_varpool_mark_needed_node (node);
 835   /* Since we reclaim unrechable nodes at the end of every language
 836      level unit, we need to be conservative about possible entry points
 837      there.  */
 838   if (TREE_PUBLIC (decl) && !DECL_COMDAT (decl) && !DECL_EXTERNAL (decl))
 839     cgraph_varpool_mark_needed_node (node);
 840   if (cgraph_global_info_ready || !flag_unit_at_a_time)
 841     cgraph_varpool_assemble_pending_decls ();
 842 }
 843
 844 /* Return true when the DECL can possibly be inlined.  */
 845 bool
 846 cgraph_function_possibly_inlined_p (tree decl)
 847 {
 848   if (!cgraph_global_info_ready)
 849     return (DECL_INLINE (decl) && !flag_really_no_inline);
 850   return DECL_POSSIBLY_INLINED (decl);
 851 }
 852
 853 /* Create clone of E in the node N represented by CALL_EXPR the callgraph.  */
 854 struct cgraph_edge *
 855 cgraph_clone_edge (struct cgraph_edge *e, struct cgraph_node *n,
 856                    tree call_stmt, int count_scale, int loop_nest)
 857 {
 858   struct cgraph_edge *new;
 859
 860   new = cgraph_create_edge (n, e->callee, call_stmt,
 861                             e->count * count_scale / REG_BR_PROB_BASE,
 862                             e->loop_nest + loop_nest);
 863
 864   new->inline_failed = e->inline_failed;
 865   e->count -= new->count;
 866   return new;
 867 }
 868
 869 /* Create node representing clone of N executed COUNT times.  Decrease
 870    the execution counts from original node too.  */
 871 struct cgraph_node *
 872 cgraph_clone_node (struct cgraph_node *n, gcov_type count, int loop_nest)
 873 {
 874   struct cgraph_node *new = cgraph_create_node ();
 875   struct cgraph_edge *e;
 876   int count_scale;
 877
 878   new->decl = n->decl;
 879   new->origin = n->origin;
 880   if (new->origin)
 881     {
 882       new->next_nested = new->origin->nested;
 883       new->origin->nested = new;
 884     }
 885   new->analyzed = n->analyzed;
 886   new->local = n->local;
 887   new->global = n->global;
 888   new->rtl = n->rtl;
 889   new->count = count;
 890   if (n->count)
 891     count_scale = new->count * REG_BR_PROB_BASE / n->count;
 892   else
 893     count_scale = 0;
 894   n->count -= count;
 895
 896   for (e = n->callees;e; e=e->next_callee)
 897     cgraph_clone_edge (e, new, e->call_stmt, count_scale, loop_nest);
 898
 899   new->next_clone = n->next_clone;
 900   new->prev_clone = n;
 901   n->next_clone = new;
 902   if (new->next_clone)
 903     new->next_clone->prev_clone = new;
 904
 905   return new;
 906 }
 907
 908 /* NODE is no longer nested function; update cgraph accordingly.  */
 909 void
 910 cgraph_unnest_node (struct cgraph_node *node)
 911 {
 912   struct cgraph_node **node2 = &node->origin->nested;
 913   gcc_assert (node->origin);
 914
 915   while (*node2 != node)
 916     node2 = &(*node2)->next_nested;
 917   *node2 = node->next_nested;
 918   node->origin = NULL;
 919 }
 920 #include "gt-cgraph.h"