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           && (cgraph_global_info_ready
 477               && (TREE_ASM_WRITTEN (n->decl) || DECL_EXTERNAL (n->decl))))
 478         kill_body = true;
 479     }
 480
 481   if (kill_body && !dump_enabled_p (TDI_tree_all) && flag_unit_at_a_time)
 482     {
 483       DECL_SAVED_TREE (node->decl) = NULL;
 484       DECL_STRUCT_FUNCTION (node->decl) = NULL;
 485       DECL_INITIAL (node->decl) = error_mark_node;
 486     }
 487   cgraph_n_nodes--;
 488   /* Do not free the structure itself so the walk over chain can continue.  */
 489 }
 490
 491 /* Notify finalize_compilation_unit that given node is reachable.  */
 492
 493 void
 494 cgraph_mark_reachable_node (struct cgraph_node *node)
 495 {
 496   if (!node->reachable && node->local.finalized)
 497     {
 498       notice_global_symbol (node->decl);
 499       node->reachable = 1;
 500       gcc_assert (!cgraph_global_info_ready);
 501
 502       node->next_needed = cgraph_nodes_queue;
 503       cgraph_nodes_queue = node;
 504     }
 505 }
 506
 507 /* Likewise indicate that a node is needed, i.e. reachable via some
 508    external means.  */
 509
 510 void
 511 cgraph_mark_needed_node (struct cgraph_node *node)
 512 {
 513   node->needed = 1;
 514   cgraph_mark_reachable_node (node);
 515 }
 516
 517 /* Return local info for the compiled function.  */
 518
 519 struct cgraph_local_info *
 520 cgraph_local_info (tree decl)
 521 {
 522   struct cgraph_node *node;
 523
 524   gcc_assert (TREE_CODE (decl) == FUNCTION_DECL);
 525   node = cgraph_node (decl);
 526   return &node->local;
 527 }
 528
 529 /* Return local info for the compiled function.  */
 530
 531 struct cgraph_global_info *
 532 cgraph_global_info (tree decl)
 533 {
 534   struct cgraph_node *node;
 535
 536   gcc_assert (TREE_CODE (decl) == FUNCTION_DECL && cgraph_global_info_ready);
 537   node = cgraph_node (decl);
 538   return &node->global;
 539 }
 540
 541 /* Return local info for the compiled function.  */
 542
 543 struct cgraph_rtl_info *
 544 cgraph_rtl_info (tree decl)
 545 {
 546   struct cgraph_node *node;
 547
 548   gcc_assert (TREE_CODE (decl) == FUNCTION_DECL);
 549   node = cgraph_node (decl);
 550   if (decl != current_function_decl
 551       && !TREE_ASM_WRITTEN (node->decl))
 552     return NULL;
 553   return &node->rtl;
 554 }
 555
 556 /* Return name of the node used in debug output.  */
 557 const char *
 558 cgraph_node_name (struct cgraph_node *node)
 559 {
 560   return lang_hooks.decl_printable_name (node->decl, 2);
 561 }
 562
 563 /* Return name of the node used in debug output.  */
 564 static const char *
 565 cgraph_varpool_node_name (struct cgraph_varpool_node *node)
 566 {
 567   return lang_hooks.decl_printable_name (node->decl, 2);
 568 }
 569
 570 /* Names used to print out the availability enum.  */
 571 static const char * const availability_names[] =
 572   {"unset", "not_available", "overwrittable", "available", "local"};
 573
 574 /* Dump given cgraph node.  */
 575 void
 576 dump_cgraph_node (FILE *f, struct cgraph_node *node)
 577 {
 578   struct cgraph_edge *edge;
 579   fprintf (f, "%s/%i:", cgraph_node_name (node), node->uid);
 580   if (node->global.inlined_to)
 581     fprintf (f, " (inline copy in %s/%i)",
 582              cgraph_node_name (node->global.inlined_to),
 583              node->global.inlined_to->uid);
 584   if (cgraph_function_flags_ready)
 585     fprintf (f, " availability:%s",
 586              availability_names [cgraph_function_body_availability (node)]);
 587   if (node->master_clone && node->master_clone->uid != node->uid)
 588     fprintf (f, "(%i)", node->master_clone->uid);
 589   if (node->count)
 590     fprintf (f, " executed "HOST_WIDEST_INT_PRINT_DEC"x",
 591              (HOST_WIDEST_INT)node->count);
 592   if (node->local.self_insns)
 593     fprintf (f, " %i insns", node->local.self_insns);
 594   if (node->global.insns && node->global.insns != node->local.self_insns)
 595     fprintf (f, " (%i after inlining)", node->global.insns);
 596   if (node->origin)
 597     fprintf (f, " nested in: %s", cgraph_node_name (node->origin));
 598   if (node->needed)
 599     fprintf (f, " needed");
 600   else if (node->reachable)
 601     fprintf (f, " reachable");
 602   if (DECL_SAVED_TREE (node->decl))
 603     fprintf (f, " tree");
 604   if (node->output)
 605     fprintf (f, " output");
 606   if (node->local.local)
 607     fprintf (f, " local");
 608   if (node->local.externally_visible)
 609     fprintf (f, " externally_visible");
 610   if (node->local.finalized)
 611     fprintf (f, " finalized");
 612   if (node->local.disregard_inline_limits)
 613     fprintf (f, " always_inline");
 614   else if (node->local.inlinable)
 615     fprintf (f, " inlinable");
 616   if (node->local.redefined_extern_inline)
 617     fprintf (f, " redefined_extern_inline");
 618   if (TREE_ASM_WRITTEN (node->decl))
 619     fprintf (f, " asm_written");
 620
 621   fprintf (f, "\n  called by: ");
 622   for (edge = node->callers; edge; edge = edge->next_caller)
 623     {
 624       fprintf (f, "%s/%i ", cgraph_node_name (edge->caller),
 625                edge->caller->uid);
 626       if (edge->count)
 627         fprintf (f, "("HOST_WIDEST_INT_PRINT_DEC"x) ",
 628                  (HOST_WIDEST_INT)edge->count);
 629       if (!edge->inline_failed)
 630         fprintf(f, "(inlined) ");
 631     }
 632
 633   fprintf (f, "\n  calls: ");
 634   for (edge = node->callees; edge; edge = edge->next_callee)
 635     {
 636       fprintf (f, "%s/%i ", cgraph_node_name (edge->callee),
 637                edge->callee->uid);
 638       if (!edge->inline_failed)
 639         fprintf(f, "(inlined) ");
 640       if (edge->count)
 641         fprintf (f, "("HOST_WIDEST_INT_PRINT_DEC"x) ",
 642                  (HOST_WIDEST_INT)edge->count);
 643       if (edge->loop_nest)
 644         fprintf (f, "(nested in %i loops) ", edge->loop_nest);
 645     }
 646   fprintf (f, "\n");
 647 }
 648
 649 /* Dump the callgraph.  */
 650
 651 void
 652 dump_cgraph (FILE *f)
 653 {
 654   struct cgraph_node *node;
 655
 656   fprintf (f, "callgraph:\n\n");
 657   for (node = cgraph_nodes; node; node = node->next)
 658     dump_cgraph_node (f, node);
 659 }
 660
 661 /* Dump given cgraph node.  */
 662 void
 663 dump_cgraph_varpool_node (FILE *f, struct cgraph_varpool_node *node)
 664 {
 665   fprintf (f, "%s:", cgraph_varpool_node_name (node));
 666   fprintf (f, " availability:%s", availability_names [cgraph_variable_initializer_availability (node)]);
 667   if (DECL_INITIAL (node->decl))
 668     fprintf (f, " initialized");
 669   if (node->needed)
 670     fprintf (f, " needed");
 671   if (node->analyzed)
 672     fprintf (f, " analyzed");
 673   if (node->finalized)
 674     fprintf (f, " finalized");
 675   if (node->output)
 676     fprintf (f, " output");
 677   if (node->externally_visible)
 678     fprintf (f, " externally_visible");
 679   fprintf (f, "\n");
 680 }
 681
 682 /* Dump the callgraph.  */
 683
 684 void
 685 dump_varpool (FILE *f)
 686 {
 687   struct cgraph_varpool_node *node;
 688
 689   fprintf (f, "variable pool:\n\n");
 690   for (node = cgraph_varpool_nodes; node; node = node->next_needed)
 691     dump_cgraph_varpool_node (f, node);
 692 }
 693
 694 /* Returns a hash code for P.  */
 695
 696 static hashval_t
 697 hash_varpool_node (const void *p)
 698 {
 699   const struct cgraph_varpool_node *n = p;
 700   return (hashval_t) DECL_UID (n->decl);
 701 }
 702
 703 /* Returns nonzero if P1 and P2 are equal.  */
 704
 705 static int
 706 eq_varpool_node (const void *p1, const void *p2)
 707 {
 708   const struct cgraph_varpool_node *n1 = p1, *n2 = p2;
 709   return DECL_UID (n1->decl) == DECL_UID (n2->decl);
 710 }
 711
 712 /* Return cgraph_varpool node assigned to DECL.  Create new one when needed.  */
 713 struct cgraph_varpool_node *
 714 cgraph_varpool_node (tree decl)
 715 {
 716   struct cgraph_varpool_node key, *node, **slot;
 717
 718   gcc_assert (DECL_P (decl) && TREE_CODE (decl) != FUNCTION_DECL);
 719
 720   if (!cgraph_varpool_hash)
 721     cgraph_varpool_hash = htab_create_ggc (10, hash_varpool_node,
 722                                            eq_varpool_node, NULL);
 723   key.decl = decl;
 724   slot = (struct cgraph_varpool_node **)
 725     htab_find_slot (cgraph_varpool_hash, &key, INSERT);
 726   if (*slot)
 727     return *slot;
 728   node = ggc_alloc_cleared (sizeof (*node));
 729   node->decl = decl;
 730   node->next = cgraph_varpool_nodes;
 731   cgraph_varpool_nodes = node;
 732   *slot = node;
 733   return node;
 734 }
 735
 736 struct cgraph_varpool_node *
 737 cgraph_varpool_node_for_asm (tree asmname)
 738 {
 739   struct cgraph_varpool_node *node;
 740
 741   for (node = cgraph_varpool_nodes; node ; node = node->next)
 742     if (decl_assembler_name_equal (node->decl, asmname))
 743       return node;
 744
 745   return NULL;
 746 }
 747
 748 /* Set the DECL_ASSEMBLER_NAME and update cgraph hashtables.  */
 749 void
 750 change_decl_assembler_name (tree decl, tree name)
 751 {
 752   if (!DECL_ASSEMBLER_NAME_SET_P (decl))
 753     {
 754       SET_DECL_ASSEMBLER_NAME (decl, name);
 755       return;
 756     }
 757   if (name == DECL_ASSEMBLER_NAME (decl))
 758     return;
 759
 760   if (TREE_SYMBOL_REFERENCED (DECL_ASSEMBLER_NAME (decl))
 761       && DECL_RTL_SET_P (decl))
 762     warning (0, "%D renamed after being referenced in assembly", decl);
 763
 764   SET_DECL_ASSEMBLER_NAME (decl, name);
 765 }
 766
 767 /* Helper function for finalization code - add node into lists so it will
 768    be analyzed and compiled.  */
 769 void
 770 cgraph_varpool_enqueue_needed_node (struct cgraph_varpool_node *node)
 771 {
 772   if (cgraph_varpool_last_needed_node)
 773     cgraph_varpool_last_needed_node->next_needed = node;
 774   cgraph_varpool_last_needed_node = node;
 775   node->next_needed = NULL;
 776   if (!cgraph_varpool_nodes_queue)
 777     cgraph_varpool_nodes_queue = node;
 778   if (!cgraph_varpool_first_unanalyzed_node)
 779     cgraph_varpool_first_unanalyzed_node = node;
 780   notice_global_symbol (node->decl);
 781 }
 782
 783 /* Reset the queue of needed nodes.  */
 784 void
 785 cgraph_varpool_reset_queue (void)
 786 {
 787   cgraph_varpool_last_needed_node = NULL;
 788   cgraph_varpool_nodes_queue = NULL;
 789   cgraph_varpool_first_unanalyzed_node = NULL;
 790 }
 791
 792 /* Notify finalize_compilation_unit that given node is reachable
 793    or needed.  */
 794 void
 795 cgraph_varpool_mark_needed_node (struct cgraph_varpool_node *node)
 796 {
 797   if (!node->needed && node->finalized)
 798     cgraph_varpool_enqueue_needed_node (node);
 799   node->needed = 1;
 800 }
 801
 802 /* Determine if variable DECL is needed.  That is, visible to something
 803    either outside this translation unit, something magic in the system
 804    configury, or (if not doing unit-at-a-time) to something we haven't
 805    seen yet.  */
 806
 807 bool
 808 decide_is_variable_needed (struct cgraph_varpool_node *node, tree decl)
 809 {
 810   /* If the user told us it is used, then it must be so.  */
 811   if (node->externally_visible
 812       || lookup_attribute ("used", DECL_ATTRIBUTES (decl)))
 813     return true;
 814
 815   /* ??? If the assembler name is set by hand, it is possible to assemble
 816      the name later after finalizing the function and the fact is noticed
 817      in assemble_name then.  This is arguably a bug.  */
 818   if (DECL_ASSEMBLER_NAME_SET_P (decl)
 819       && TREE_SYMBOL_REFERENCED (DECL_ASSEMBLER_NAME (decl)))
 820     return true;
 821
 822   /* If we decided it was needed before, but at the time we didn't have
 823      the definition available, then it's still needed.  */
 824   if (node->needed)
 825     return true;
 826
 827   /* Externally visible variables must be output.  The exception is
 828      COMDAT variables that must be output only when they are needed.  */
 829   if (TREE_PUBLIC (decl) && !DECL_COMDAT (decl) && !DECL_EXTERNAL (decl))
 830     return true;
 831
 832   if (flag_unit_at_a_time)
 833     return false;
 834
 835   /* If not doing unit at a time, then we'll only defer this function
 836      if its marked for inlining.  Otherwise we want to emit it now.  */
 837
 838   /* We want to emit COMDAT variables only when absolutely necessary.  */
 839   if (DECL_COMDAT (decl))
 840     return false;
 841   return true;
 842 }
 843
 844 void
 845 cgraph_varpool_finalize_decl (tree decl)
 846 {
 847   struct cgraph_varpool_node *node = cgraph_varpool_node (decl);
 848
 849   /* The first declaration of a variable that comes through this function
 850      decides whether it is global (in C, has external linkage)
 851      or local (in C, has internal linkage).  So do nothing more
 852      if this function has already run.  */
 853   if (node->finalized)
 854     {
 855       if (cgraph_global_info_ready || !flag_unit_at_a_time)
 856         cgraph_varpool_assemble_pending_decls ();
 857       return;
 858     }
 859   if (node->needed)
 860     cgraph_varpool_enqueue_needed_node (node);
 861   node->finalized = true;
 862
 863   if (decide_is_variable_needed (node, decl))
 864     cgraph_varpool_mark_needed_node (node);
 865   /* Since we reclaim unreachable nodes at the end of every language
 866      level unit, we need to be conservative about possible entry points
 867      there.  */
 868   else if (TREE_PUBLIC (decl) && !DECL_COMDAT (decl) && !DECL_EXTERNAL (decl))
 869     cgraph_varpool_mark_needed_node (node);
 870   if (cgraph_global_info_ready || !flag_unit_at_a_time)
 871     cgraph_varpool_assemble_pending_decls ();
 872 }
 873
 874 /* Return true when the DECL can possibly be inlined.  */
 875 bool
 876 cgraph_function_possibly_inlined_p (tree decl)
 877 {
 878   if (!cgraph_global_info_ready)
 879     return (DECL_INLINE (decl) && !flag_really_no_inline);
 880   return DECL_POSSIBLY_INLINED (decl);
 881 }
 882
 883 /* Create clone of E in the node N represented by CALL_EXPR the callgraph.  */
 884 struct cgraph_edge *
 885 cgraph_clone_edge (struct cgraph_edge *e, struct cgraph_node *n,
 886                    tree call_stmt, int count_scale, int loop_nest)
 887 {
 888   struct cgraph_edge *new;
 889
 890   new = cgraph_create_edge (n, e->callee, call_stmt,
 891                             e->count * count_scale / REG_BR_PROB_BASE,
 892                             e->loop_nest + loop_nest);
 893
 894   new->inline_failed = e->inline_failed;
 895   e->count -= new->count;
 896   return new;
 897 }
 898
 899 /* Create node representing clone of N executed COUNT times.  Decrease
 900    the execution counts from original node too.  */
 901 struct cgraph_node *
 902 cgraph_clone_node (struct cgraph_node *n, gcov_type count, int loop_nest)
 903 {
 904   struct cgraph_node *new = cgraph_create_node ();
 905   struct cgraph_edge *e;
 906   int count_scale;
 907
 908   new->decl = n->decl;
 909   new->origin = n->origin;
 910   if (new->origin)
 911     {
 912       new->next_nested = new->origin->nested;
 913       new->origin->nested = new;
 914     }
 915   new->analyzed = n->analyzed;
 916   new->local = n->local;
 917   new->global = n->global;
 918   new->rtl = n->rtl;
 919   new->master_clone = n->master_clone;
 920   new->count = count;
 921   if (n->count)
 922     count_scale = new->count * REG_BR_PROB_BASE / n->count;
 923   else
 924     count_scale = 0;
 925   n->count -= count;
 926
 927   for (e = n->callees;e; e=e->next_callee)
 928     cgraph_clone_edge (e, new, e->call_stmt, count_scale, loop_nest);
 929
 930   new->next_clone = n->next_clone;
 931   new->prev_clone = n;
 932   n->next_clone = new;
 933   if (new->next_clone)
 934     new->next_clone->prev_clone = new;
 935
 936   return new;
 937 }
 938
 939 /* Return true if N is an master_clone, (see cgraph_master_clone).  */
 940
 941 bool
 942 cgraph_is_master_clone (struct cgraph_node *n)
 943 {
 944   return (n == cgraph_master_clone (n));
 945 }
 946
 947 struct cgraph_node *
 948 cgraph_master_clone (struct cgraph_node *n)
 949 {
 950   enum availability avail = cgraph_function_body_availability (n);
 951
 952   if (avail == AVAIL_NOT_AVAILABLE || avail == AVAIL_OVERWRITABLE)
 953     return NULL;
 954
 955   if (!n->master_clone)
 956     n->master_clone = cgraph_node (n->decl);
 957
 958   return n->master_clone;
 959 }
 960
 961 /* NODE is no longer nested function; update cgraph accordingly.  */
 962 void
 963 cgraph_unnest_node (struct cgraph_node *node)
 964 {
 965   struct cgraph_node **node2 = &node->origin->nested;
 966   gcc_assert (node->origin);
 967
 968   while (*node2 != node)
 969     node2 = &(*node2)->next_nested;
 970   *node2 = node->next_nested;
 971   node->origin = NULL;
 972 }
 973
 974 /* Return function availability.  See cgraph.h for description of individual
 975    return values.  */
 976 enum availability
 977 cgraph_function_body_availability (struct cgraph_node *node)
 978 {
 979   enum availability avail;
 980   gcc_assert (cgraph_function_flags_ready);
 981   if (!node->local.finalized)
 982     avail = AVAIL_NOT_AVAILABLE;
 983   else if (node->local.local)
 984     avail = AVAIL_LOCAL;
 985   else if (node->local.externally_visible)
 986     avail = AVAIL_AVAILABLE;
 987
 988   /* If the function can be overwritten, return OVERWRITABLE.  Take
 989      care at least of two notable extensions - the COMDAT functions
 990      used to share template instantiations in C++ (this is symmetric
 991      to code cp_cannot_inline_tree_fn and probably shall be shared and
 992      the inlinability hooks completely eliminated).
 993
 994      ??? Does the C++ one definition rule allow us to always return
 995      AVAIL_AVAILABLE here?  That would be good reason to preserve this
 996      hook Similarly deal with extern inline functions - this is again
 997      necessary to get C++ shared functions having keyed templates
 998      right and in the C extension documentation we probably should
 999      document the requirement of both versions of function (extern
1000      inline and offline) having same side effect characteristics as
1001      good optimization is what this optimization is about.  */
1002
1003   else if (!(*targetm.binds_local_p) (node->decl)
1004            && !DECL_COMDAT (node->decl) && !DECL_EXTERNAL (node->decl))
1005     avail = AVAIL_OVERWRITABLE;
1006   else avail = AVAIL_AVAILABLE;
1007
1008   return avail;
1009 }
1010
1011 /* Return variable availability.  See cgraph.h for description of individual
1012    return values.  */
1013 enum availability
1014 cgraph_variable_initializer_availability (struct cgraph_varpool_node *node)
1015 {
1016   gcc_assert (cgraph_function_flags_ready);
1017   if (!node->finalized)
1018     return AVAIL_NOT_AVAILABLE;
1019   if (!TREE_PUBLIC (node->decl))
1020     return AVAIL_AVAILABLE;
1021   /* If the variable can be overwritten, return OVERWRITABLE.  Takes
1022      care of at least two notable extensions - the COMDAT variables
1023      used to share template instantiations in C++.  */
1024   if (!(*targetm.binds_local_p) (node->decl) && !DECL_COMDAT (node->decl))
1025     return AVAIL_OVERWRITABLE;
1026   return AVAIL_AVAILABLE;
1027 }
1028
1029 #include "gt-cgraph.h"