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