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