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