gcc/cgraph.c

   1 /* Callgraph handling code.
   2    Copyright (C) 2003, 2004, 2005 Free Software Foundation, Inc.
   3    Contributed by Jan Hubicka
   4
   5 This file is part of GCC.
   6
   7 GCC is free software; you can redistribute it and/or modify it under
   8 the terms of the GNU General Public License as published by the Free
   9 Software Foundation; either version 2, or (at your option) any later
  10 version.
  11
  12 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
  13 WARRANTY; without even the implied warranty of MERCHANTABILITY or
  14 FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  15 for more details.
  16
  17 You should have received a copy of the GNU General Public License
  18 along with GCC; see the file COPYING.  If not, write to the Free
  19 Software Foundation, 59 Temple Place - Suite 330, Boston, MA
  20 02111-1307, USA.  */
  21
  22 /*  This file contains basic routines manipulating call graph and variable pool
  23
  24 The callgraph:
  25
  26     The call-graph is data structure designed for intra-procedural optimization
  27     but it is also used in non-unit-at-a-time compilation to allow easier code
  28     sharing.
  29
  30     The call-graph consist of nodes and edges represented via linked lists.
  31     Each function (external or not) corresponds to the unique node (in
  32     contrast to tree DECL nodes where we can have multiple nodes for each
  33     function).
  34
  35     The mapping from declarations to call-graph nodes is done using hash table
  36     based on DECL_ASSEMBLER_NAME, so it is essential for assembler name to
  37     not change once the declaration is inserted into the call-graph.
  38     The call-graph nodes are created lazily using cgraph_node function when
  39     called for unknown declaration.
  40
  41     When built, there is one edge for each direct call.  It is possible that
  42     the reference will be later optimized out.  The call-graph is built
  43     conservatively in order to make conservative data flow analysis possible.
  44
  45     The callgraph at the moment does not represent indirect calls or calls
  46     from other compilation unit.  Flag NEEDED is set for each node that may
  47     be accessed in such an invisible way and it shall be considered an
  48     entry point to the callgraph.
  49
  50     Intraprocedural information:
  51
  52       Callgraph is place to store data needed for intraprocedural optimization.
  53       All data structures are divided into three components: local_info that
  54       is produced while analyzing the function, global_info that is result
  55       of global walking of the callgraph on the end of compilation and
  56       rtl_info used by RTL backend to propagate data from already compiled
  57       functions to their callers.
  58
  59     Inlining plans:
  60
  61       The function inlining information is decided in advance and maintained
  62       in the callgraph as so called inline plan.
  63       For each inlined call, the callee's node is cloned to represent the
  64       new function copy produced by inliner.
  65       Each inlined call gets a unique corresponding clone node of the callee
  66       and the data structure is updated while inlining is performed, so
  67       the clones are eliminated and their callee edges redirected to the
  68       caller.
  69
  70       Each edge has "inline_failed" field.  When the field is set to NULL,
  71       the call will be inlined.  When it is non-NULL it contains a reason
  72       why inlining wasn't performed.
  73
  74
  75 The varpool data structure:
  76
  77     Varpool is used to maintain variables in similar manner as call-graph
  78     is used for functions.  Most of the API is symmetric replacing cgraph
  79     function prefix by cgraph_varpool  */
  80
  81
  82 #include "config.h"
  83 #include "system.h"
  84 #include "coretypes.h"
  85 #include "tm.h"
  86 #include "tree.h"
  87 #include "tree-inline.h"
  88 #include "langhooks.h"
  89 #include "hashtab.h"
  90 #include "toplev.h"
  91 #include "flags.h"
  92 #include "ggc.h"
  93 #include "debug.h"
  94 #include "target.h"
  95 #include "basic-block.h"
  96 #include "cgraph.h"
  97 #include "varray.h"
  98 #include "output.h"
  99 #include "intl.h"
 100
 101 static void cgraph_node_remove_callers (struct cgraph_node *node);
 102 static inline void cgraph_edge_remove_caller (struct cgraph_edge *e);
 103 static inline void cgraph_edge_remove_callee (struct cgraph_edge *e);
 104
 105 /* Hash table used to convert declarations into nodes.  */
 106 static GTY((param_is (struct cgraph_node))) htab_t cgraph_hash;
 107
 108 /* The linked list of cgraph nodes.  */
 109 struct cgraph_node *cgraph_nodes;
 110
 111 /* Queue of cgraph nodes scheduled to be lowered.  */
 112 struct cgraph_node *cgraph_nodes_queue;
 113
 114 /* Number of nodes in existence.  */
 115 int cgraph_n_nodes;
 116
 117 /* Maximal uid used in cgraph nodes.  */
 118 int cgraph_max_uid;
 119
 120 /* Set when whole unit has been analyzed so we can access global info.  */
 121 bool cgraph_global_info_ready = false;
 122
 123 /* Set when the cgraph is fully build and the basic flags are computed.  */
 124 bool cgraph_function_flags_ready = false;
 125
 126 /* Hash table used to convert declarations into nodes.  */
 127 static GTY((param_is (struct cgraph_varpool_node))) htab_t cgraph_varpool_hash;
 128
 129 /* Queue of cgraph nodes scheduled to be lowered and output.  */
 130 struct cgraph_varpool_node *cgraph_varpool_nodes_queue, *cgraph_varpool_first_unanalyzed_node;
 131
 132
 133 /* The linked list of cgraph varpool nodes.  */
 134 static GTY(()) struct cgraph_varpool_node *cgraph_varpool_nodes;
 135
 136 /* End of the varpool queue.  Needs to be QTYed to work with PCH.  */
 137 static GTY(()) struct cgraph_varpool_node *cgraph_varpool_last_needed_node;
 138
 139 static hashval_t hash_node (const void *);
 140 static int eq_node (const void *, const void *);
 141
 142 /* Returns a hash code for P.  */
 143
 144 static hashval_t
 145 hash_node (const void *p)
 146 {
 147   const struct cgraph_node *n = p;
 148   return (hashval_t) DECL_UID (n->decl);
 149 }
 150
 151 /* Returns nonzero if P1 and P2 are equal.  */
 152
 153 static int
 154 eq_node (const void *p1, const void *p2)
 155 {
 156   const struct cgraph_node *n1 = p1, *n2 = p2;
 157   return DECL_UID (n1->decl) == DECL_UID (n2->decl);
 158 }
 159
 160 /* Allocate new callgraph node and insert it into basic data structures.  */
 161 static struct cgraph_node *
 162 cgraph_create_node (void)
 163 {
 164   struct cgraph_node *node;
 165
 166   node = ggc_alloc_cleared (sizeof (*node));
 167   node->next = cgraph_nodes;
 168   node->uid = cgraph_max_uid++;
 169   if (cgraph_nodes)
 170     cgraph_nodes->previous = node;
 171   node->previous = NULL;
 172   cgraph_nodes = node;
 173   cgraph_n_nodes++;
 174   return node;
 175 }
 176
 177 /* Return cgraph node assigned to DECL.  Create new one when needed.  */
 178 struct cgraph_node *
 179 cgraph_node (tree decl)
 180 {
 181   struct cgraph_node key, *node, **slot;
 182
 183   gcc_assert (TREE_CODE (decl) == FUNCTION_DECL);
 184
 185   if (!cgraph_hash)
 186     cgraph_hash = htab_create_ggc (10, hash_node, eq_node, NULL);
 187
 188   key.decl = decl;
 189
 190   slot = (struct cgraph_node **) htab_find_slot (cgraph_hash, &key, INSERT);
 191
 192   if (*slot)
 193     return *slot;
 194
 195   node = cgraph_create_node ();
 196   node->decl = decl;
 197   *slot = node;
 198   if (DECL_CONTEXT (decl) && TREE_CODE (DECL_CONTEXT (decl)) == FUNCTION_DECL)
 199     {
 200       node->origin = cgraph_node (DECL_CONTEXT (decl));
 201       node->next_nested = node->origin->nested;
 202       node->origin->nested = node;
 203     }
 204   return node;
 205 }
 206
 207 /* Compare ASMNAME with the DECL_ASSEMBLER_NAME of DECL.  */
 208
 209 static bool
 210 decl_assembler_name_equal (tree decl, tree asmname)
 211 {
 212   tree decl_asmname = DECL_ASSEMBLER_NAME (decl);
 213
 214   if (decl_asmname == asmname)
 215     return true;
 216
 217   /* If the target assembler name was set by the user, things are trickier.
 218      We have a leading '*' to begin with.  After that, it's arguable what
 219      is the correct thing to do with -fleading-underscore.  Arguably, we've
 220      historically been doing the wrong thing in assemble_alias by always
 221      printing the leading underscore.  Since we're not changing that, make
 222      sure user_label_prefix follows the '*' before matching.  */
 223   if (IDENTIFIER_POINTER (decl_asmname)[0] == '*')
 224     {
 225       const char *decl_str = IDENTIFIER_POINTER (decl_asmname) + 1;
 226       size_t ulp_len = strlen (user_label_prefix);
 227
 228       if (ulp_len == 0)
 229         ;
 230       else if (strncmp (decl_str, user_label_prefix, ulp_len) == 0)
 231         decl_str += ulp_len;
 232       else
 233         return false;
 234
 235       return strcmp (decl_str, IDENTIFIER_POINTER (asmname)) == 0;
 236     }
 237
 238   return false;
 239 }
 240
 241
 242 /* Return the cgraph node that has ASMNAME for its DECL_ASSEMBLER_NAME.
 243    Return NULL if there's no such node.  */
 244
 245 struct cgraph_node *
 246 cgraph_node_for_asm (tree asmname)
 247 {
 248   struct cgraph_node *node;
 249
 250   for (node = cgraph_nodes; node ; node = node->next)
 251     if (decl_assembler_name_equal (node->decl, asmname))
 252       return node;
 253
 254   return NULL;
 255 }
 256
 257 /* Return callgraph edge representing CALL_EXPR.  */
 258 struct cgraph_edge *
 259 cgraph_edge (struct cgraph_node *node, tree call_expr)
 260 {
 261   struct cgraph_edge *e;
 262
 263   /* This loop may turn out to be performance problem.  In such case adding
 264      hashtables into call nodes with very many edges is probably best
 265      solution.  It is not good idea to add pointer into CALL_EXPR itself
 266      because we want to make possible having multiple cgraph nodes representing
 267      different clones of the same body before the body is actually cloned.  */
 268   for (e = node->callees; e; e= e->next_callee)
 269     if (e->call_expr == call_expr)
 270       break;
 271   return e;
 272 }
 273
 274 /* Create edge from CALLER to CALLEE in the cgraph.  */
 275
 276 struct cgraph_edge *
 277 cgraph_create_edge (struct cgraph_node *caller, struct cgraph_node *callee,
 278                     tree call_expr, gcov_type count, int nest)
 279 {
 280   struct cgraph_edge *edge = ggc_alloc (sizeof (struct cgraph_edge));
 281 #ifdef ENABLE_CHECKING
 282   struct cgraph_edge *e;
 283
 284   for (e = caller->callees; e; e = e->next_callee)
 285     gcc_assert (e->call_expr != call_expr);
 286 #endif
 287
 288   gcc_assert (TREE_CODE (call_expr) == CALL_EXPR);
 289
 290   if (!DECL_SAVED_TREE (callee->decl))
 291     edge->inline_failed = N_("function body not available");
 292   else if (callee->local.redefined_extern_inline)
 293     edge->inline_failed = N_("redefined extern inline functions are not "
 294                              "considered for inlining");
 295   else if (callee->local.inlinable)
 296     edge->inline_failed = N_("function not considered for inlining");
 297   else
 298     edge->inline_failed = N_("function not inlinable");
 299
 300   edge->aux = NULL;
 301
 302   edge->caller = caller;
 303   edge->callee = callee;
 304   edge->call_expr = call_expr;
 305   edge->prev_caller = NULL;
 306   edge->next_caller = callee->callers;
 307   if (callee->callers)
 308     callee->callers->prev_caller = edge;
 309   edge->prev_callee = NULL;
 310   edge->next_callee = caller->callees;
 311   if (caller->callees)
 312     caller->callees->prev_callee = edge;
 313   caller->callees = edge;
 314   callee->callers = edge;
 315   edge->count = count;
 316   edge->loop_nest = nest;
 317   return edge;
 318 }
 319
 320 /* Remove the edge E from the list of the callers of the callee.  */
 321
 322 static inline void
 323 cgraph_edge_remove_callee (struct cgraph_edge *e)
 324 {
 325   if (e->prev_caller)
 326     e->prev_caller->next_caller = e->next_caller;
 327   if (e->next_caller)
 328     e->next_caller->prev_caller = e->prev_caller;
 329   if (!e->prev_caller)
 330     e->callee->callers = e->next_caller;
 331 }
 332
 333 /* Remove the edge E from the list of the callees of the caller.  */
 334
 335 static inline void
 336 cgraph_edge_remove_caller (struct cgraph_edge *e)
 337 {
 338   if (e->prev_callee)
 339     e->prev_callee->next_callee = e->next_callee;
 340   if (e->next_callee)
 341     e->next_callee->prev_callee = e->prev_callee;
 342   if (!e->prev_callee)
 343     e->caller->callees = e->next_callee;
 344 }
 345
 346 /* Remove the edge E in the cgraph.  */
 347
 348 void
 349 cgraph_remove_edge (struct cgraph_edge *e)
 350 {
 351   /* Remove from callers list of the callee.  */
 352   cgraph_edge_remove_callee (e);
 353
 354   /* Remove from callees list of the callers.  */
 355   cgraph_edge_remove_caller (e);
 356 }
 357
 358 /* Redirect callee of E to N.  The function does not update underlying
 359    call expression.  */
 360
 361 void
 362 cgraph_redirect_edge_callee (struct cgraph_edge *e, struct cgraph_node *n)
 363 {
 364   /* Remove from callers list of the current callee.  */
 365   cgraph_edge_remove_callee (e);
 366
 367   /* Insert to callers list of the new callee.  */
 368   e->prev_caller = NULL;
 369   if (n->callers)
 370     n->callers->prev_caller = e;
 371   e->next_caller = n->callers;
 372   n->callers = e;
 373   e->callee = n;
 374 }
 375
 376 /* Remove all callees from the node.  */
 377
 378 void
 379 cgraph_node_remove_callees (struct cgraph_node *node)
 380 {
 381   struct cgraph_edge *e;
 382
 383   /* It is sufficient to remove the edges from the lists of callers of
 384      the callees.  The callee list of the node can be zapped with one
 385      assignment.  */
 386   for (e = node->callees; e; e = e->next_callee)
 387     cgraph_edge_remove_callee (e);
 388   node->callees = NULL;
 389 }
 390
 391 /* Remove all callers from the node.  */
 392
 393 static void
 394 cgraph_node_remove_callers (struct cgraph_node *node)
 395 {
 396   struct cgraph_edge *e;
 397
 398   /* It is sufficient to remove the edges from the lists of callees of
 399      the callers.  The caller list of the node can be zapped with one
 400      assignment.  */
 401   for (e = node->callers; e; e = e->next_caller)
 402     cgraph_edge_remove_caller (e);
 403   node->callers = NULL;
 404 }
 405
 406 /* Remove the node from cgraph.  */
 407
 408 void
 409 cgraph_remove_node (struct cgraph_node *node)
 410 {
 411   void **slot;
 412   bool kill_body = false;
 413
 414   cgraph_node_remove_callers (node);
 415   cgraph_node_remove_callees (node);
 416   while (node->nested)
 417     cgraph_remove_node (node->nested);
 418   if (node->origin)
 419     {
 420       struct cgraph_node **node2 = &node->origin->nested;
 421
 422       while (*node2 != node)
 423         node2 = &(*node2)->next_nested;
 424       *node2 = node->next_nested;
 425     }
 426   if (node->previous)
 427     node->previous->next = node->next;
 428   else
 429     cgraph_nodes = node->next;
 430   if (node->next)
 431     node->next->previous = node->previous;
 432   slot = htab_find_slot (cgraph_hash, node, NO_INSERT);
 433   if (*slot == node)
 434     {
 435       if (node->next_clone)
 436       {
 437         *slot = node->next_clone;
 438         node->next_clone->prev_clone = NULL;
 439       }
 440       else
 441         {
 442           htab_clear_slot (cgraph_hash, slot);
 443           kill_body = true;
 444         }
 445     }
 446   else
 447     {
 448       node->prev_clone->next_clone = node->next_clone;
 449       if (node->next_clone)
 450         node->next_clone->prev_clone = node->prev_clone;
 451     }
 452
 453   /* While all the clones are removed after being proceeded, the function
 454      itself is kept in the cgraph even after it is compiled.  Check whether
 455      we are done with this body and reclaim it proactively if this is the case.
 456      */
 457   if (!kill_body && *slot)
 458     {
 459       struct cgraph_node *n = *slot;
 460       if (!n->next_clone && !n->global.inlined_to
 461           && (TREE_ASM_WRITTEN (n->decl) || DECL_EXTERNAL (n->decl)))
 462         kill_body = true;
 463     }
 464
 465   if (kill_body && !dump_enabled_p (TDI_tree_all) && flag_unit_at_a_time)
 466     {
 467       DECL_SAVED_TREE (node->decl) = NULL;
 468       DECL_STRUCT_FUNCTION (node->decl) = NULL;
 469       DECL_INITIAL (node->decl) = error_mark_node;
 470     }
 471   cgraph_n_nodes--;
 472   /* Do not free the structure itself so the walk over chain can continue.  */
 473 }
 474
 475 /* Notify finalize_compilation_unit that given node is reachable.  */
 476
 477 void
 478 cgraph_mark_reachable_node (struct cgraph_node *node)
 479 {
 480   if (!node->reachable && node->local.finalized)
 481     {
 482       notice_global_symbol (node->decl);
 483       node->reachable = 1;
 484       gcc_assert (!cgraph_global_info_ready);
 485
 486       node->next_needed = cgraph_nodes_queue;
 487       cgraph_nodes_queue = node;
 488     }
 489 }
 490
 491 /* Likewise indicate that a node is needed, i.e. reachable via some
 492    external means.  */
 493
 494 void
 495 cgraph_mark_needed_node (struct cgraph_node *node)
 496 {
 497   node->needed = 1;
 498   cgraph_mark_reachable_node (node);
 499 }
 500
 501 /* Return local info for the compiled function.  */
 502
 503 struct cgraph_local_info *
 504 cgraph_local_info (tree decl)
 505 {
 506   struct cgraph_node *node;
 507
 508   gcc_assert (TREE_CODE (decl) == FUNCTION_DECL);
 509   node = cgraph_node (decl);
 510   return &node->local;
 511 }
 512
 513 /* Return local info for the compiled function.  */
 514
 515 struct cgraph_global_info *
 516 cgraph_global_info (tree decl)
 517 {
 518   struct cgraph_node *node;
 519
 520   gcc_assert (TREE_CODE (decl) == FUNCTION_DECL && cgraph_global_info_ready);
 521   node = cgraph_node (decl);
 522   return &node->global;
 523 }
 524
 525 /* Return local info for the compiled function.  */
 526
 527 struct cgraph_rtl_info *
 528 cgraph_rtl_info (tree decl)
 529 {
 530   struct cgraph_node *node;
 531
 532   gcc_assert (TREE_CODE (decl) == FUNCTION_DECL);
 533   node = cgraph_node (decl);
 534   if (decl != current_function_decl
 535       && !TREE_ASM_WRITTEN (node->decl))
 536     return NULL;
 537   return &node->rtl;
 538 }
 539
 540 /* Return name of the node used in debug output.  */
 541 const char *
 542 cgraph_node_name (struct cgraph_node *node)
 543 {
 544   return lang_hooks.decl_printable_name (node->decl, 2);
 545 }
 546
 547 /* Return name of the node used in debug output.  */
 548 static const char *
 549 cgraph_varpool_node_name (struct cgraph_varpool_node *node)
 550 {
 551   return lang_hooks.decl_printable_name (node->decl, 2);
 552 }
 553
 554 /* Dump given cgraph node.  */
 555 void
 556 dump_cgraph_node (FILE *f, struct cgraph_node *node)
 557 {
 558   struct cgraph_edge *edge;
 559   fprintf (f, "%s/%i:", cgraph_node_name (node), node->uid);
 560   if (node->global.inlined_to)
 561     fprintf (f, " (inline copy in %s/%i)",
 562              cgraph_node_name (node->global.inlined_to),
 563              node->global.inlined_to->uid);
 564   if (node->count)
 565     fprintf (f, " executed "HOST_WIDEST_INT_PRINT_DEC"x",
 566              (HOST_WIDEST_INT)node->count);
 567   if (node->local.self_insns)
 568     fprintf (f, " %i insns", node->local.self_insns);
 569   if (node->global.insns && node->global.insns != node->local.self_insns)
 570     fprintf (f, " (%i after inlining)", node->global.insns);
 571   if (node->origin)
 572     fprintf (f, " nested in: %s", cgraph_node_name (node->origin));
 573   if (node->needed)
 574     fprintf (f, " needed");
 575   else if (node->reachable)
 576     fprintf (f, " reachable");
 577   if (DECL_SAVED_TREE (node->decl))
 578     fprintf (f, " tree");
 579   if (node->output)
 580     fprintf (f, " output");
 581   if (node->local.local)
 582     fprintf (f, " local");
 583   if (node->local.disregard_inline_limits)
 584     fprintf (f, " always_inline");
 585   else if (node->local.inlinable)
 586     fprintf (f, " inlinable");
 587   if (TREE_ASM_WRITTEN (node->decl))
 588     fprintf (f, " asm_written");
 589
 590   fprintf (f, "\n  called by: ");
 591   for (edge = node->callers; edge; edge = edge->next_caller)
 592     {
 593       fprintf (f, "%s/%i ", cgraph_node_name (edge->caller),
 594                edge->caller->uid);
 595       if (edge->count)
 596         fprintf (f, "("HOST_WIDEST_INT_PRINT_DEC"x) ",
 597                  (HOST_WIDEST_INT)edge->count);
 598       if (!edge->inline_failed)
 599         fprintf(f, "(inlined) ");
 600     }
 601
 602   fprintf (f, "\n  calls: ");
 603   for (edge = node->callees; edge; edge = edge->next_callee)
 604     {
 605       fprintf (f, "%s/%i ", cgraph_node_name (edge->callee),
 606                edge->callee->uid);
 607       if (!edge->inline_failed)
 608         fprintf(f, "(inlined) ");
 609     }
 610   fprintf (f, "\n");
 611 }
 612
 613 /* Dump the callgraph.  */
 614
 615 void
 616 dump_cgraph (FILE *f)
 617 {
 618   struct cgraph_node *node;
 619
 620   fprintf (f, "callgraph:\n\n");
 621   for (node = cgraph_nodes; node; node = node->next)
 622     dump_cgraph_node (f, node);
 623 }
 624
 625 /* Dump given cgraph node.  */
 626 void
 627 dump_cgraph_varpool_node (FILE *f, struct cgraph_varpool_node *node)
 628 {
 629   fprintf (f, "%s:", cgraph_varpool_node_name (node));
 630   if (DECL_INITIAL (node->decl))
 631     fprintf (f, " initialized");
 632   if (node->needed)
 633     fprintf (f, " needed");
 634   if (node->analyzed)
 635     fprintf (f, " analyzed");
 636   if (node->finalized)
 637     fprintf (f, " finalized");
 638   if (node->output)
 639     fprintf (f, " output");
 640   fprintf (f, "\n");
 641 }
 642
 643 /* Dump the callgraph.  */
 644
 645 void
 646 dump_varpool (FILE *f)
 647 {
 648   struct cgraph_varpool_node *node;
 649
 650   fprintf (f, "variable pool:\n\n");
 651   for (node = cgraph_varpool_nodes; node; node = node->next_needed)
 652     dump_cgraph_varpool_node (f, node);
 653 }
 654
 655 /* Returns a hash code for P.  */
 656
 657 static hashval_t
 658 hash_varpool_node (const void *p)
 659 {
 660   const struct cgraph_varpool_node *n = p;
 661   return (hashval_t) DECL_UID (n->decl);
 662 }
 663
 664 /* Returns nonzero if P1 and P2 are equal.  */
 665
 666 static int
 667 eq_varpool_node (const void *p1, const void *p2)
 668 {
 669   const struct cgraph_varpool_node *n1 = p1, *n2 = p2;
 670   return DECL_UID (n1->decl) == DECL_UID (n2->decl);
 671 }
 672
 673 /* Return cgraph_varpool node assigned to DECL.  Create new one when needed.  */
 674 struct cgraph_varpool_node *
 675 cgraph_varpool_node (tree decl)
 676 {
 677   struct cgraph_varpool_node key, *node, **slot;
 678
 679   gcc_assert (DECL_P (decl) && TREE_CODE (decl) != FUNCTION_DECL);
 680
 681   if (!cgraph_varpool_hash)
 682     cgraph_varpool_hash = htab_create_ggc (10, hash_varpool_node,
 683                                            eq_varpool_node, NULL);
 684   key.decl = decl;
 685   slot = (struct cgraph_varpool_node **)
 686     htab_find_slot (cgraph_varpool_hash, &key, INSERT);
 687   if (*slot)
 688     return *slot;
 689   node = ggc_alloc_cleared (sizeof (*node));
 690   node->decl = decl;
 691   node->next = cgraph_varpool_nodes;
 692   cgraph_varpool_nodes = node;
 693   *slot = node;
 694   return node;
 695 }
 696
 697 struct cgraph_varpool_node *
 698 cgraph_varpool_node_for_asm (tree asmname)
 699 {
 700   struct cgraph_varpool_node *node;
 701
 702   for (node = cgraph_varpool_nodes; node ; node = node->next)
 703     if (decl_assembler_name_equal (node->decl, asmname))
 704       return node;
 705
 706   return NULL;
 707 }
 708
 709 /* Set the DECL_ASSEMBLER_NAME and update cgraph hashtables.  */
 710 void
 711 change_decl_assembler_name (tree decl, tree name)
 712 {
 713   if (!DECL_ASSEMBLER_NAME_SET_P (decl))
 714     {
 715       SET_DECL_ASSEMBLER_NAME (decl, name);
 716       return;
 717     }
 718   if (name == DECL_ASSEMBLER_NAME (decl))
 719     return;
 720
 721   if (TREE_SYMBOL_REFERENCED (DECL_ASSEMBLER_NAME (decl))
 722       && DECL_RTL_SET_P (decl))
 723     warning (0, "%D renamed after being referenced in assembly", decl);
 724
 725   SET_DECL_ASSEMBLER_NAME (decl, name);
 726 }
 727
 728 /* Helper function for finalization code - add node into lists so it will
 729    be analyzed and compiled.  */
 730 void
 731 cgraph_varpool_enqueue_needed_node (struct cgraph_varpool_node *node)
 732 {
 733   if (cgraph_varpool_last_needed_node)
 734     cgraph_varpool_last_needed_node->next_needed = node;
 735   cgraph_varpool_last_needed_node = node;
 736   node->next_needed = NULL;
 737   if (!cgraph_varpool_nodes_queue)
 738     cgraph_varpool_nodes_queue = node;
 739   if (!cgraph_varpool_first_unanalyzed_node)
 740     cgraph_varpool_first_unanalyzed_node = node;
 741   notice_global_symbol (node->decl);
 742 }
 743
 744 /* Reset the queue of needed nodes.  */
 745 void
 746 cgraph_varpool_reset_queue (void)
 747 {
 748   cgraph_varpool_last_needed_node = NULL;
 749   cgraph_varpool_nodes_queue = NULL;
 750   cgraph_varpool_first_unanalyzed_node = NULL;
 751 }
 752
 753 /* Notify finalize_compilation_unit that given node is reachable
 754    or needed.  */
 755 void
 756 cgraph_varpool_mark_needed_node (struct cgraph_varpool_node *node)
 757 {
 758   if (!node->needed && node->finalized)
 759     cgraph_varpool_enqueue_needed_node (node);
 760   node->needed = 1;
 761 }
 762
 763 /* Determine if variable DECL is needed.  That is, visible to something
 764    either outside this translation unit, something magic in the system
 765    configury, or (if not doing unit-at-a-time) to something we haven't
 766    seen yet.  */
 767
 768 bool
 769 decide_is_variable_needed (struct cgraph_varpool_node *node, tree decl)
 770 {
 771   /* If the user told us it is used, then it must be so.  */
 772   if (lookup_attribute ("used", DECL_ATTRIBUTES (decl)))
 773     return true;
 774
 775   /* ??? If the assembler name is set by hand, it is possible to assemble
 776      the name later after finalizing the function and the fact is noticed
 777      in assemble_name then.  This is arguably a bug.  */
 778   if (DECL_ASSEMBLER_NAME_SET_P (decl)
 779       && TREE_SYMBOL_REFERENCED (DECL_ASSEMBLER_NAME (decl)))
 780     return true;
 781
 782   /* If we decided it was needed before, but at the time we didn't have
 783      the definition available, then it's still needed.  */
 784   if (node->needed)
 785     return true;
 786
 787   /* Externally visible functions must be output.  The exception is
 788      COMDAT functions that must be output only when they are needed.  */
 789   if (TREE_PUBLIC (decl) && !DECL_COMDAT (decl) && !DECL_EXTERNAL (decl))
 790     return true;
 791
 792   if (flag_unit_at_a_time)
 793     return false;
 794
 795   /* If not doing unit at a time, then we'll only defer this function
 796      if its marked for inlining.  Otherwise we want to emit it now.  */
 797
 798   /* We want to emit COMDAT variables only when absolutely necessary.  */
 799   if (DECL_COMDAT (decl))
 800     return false;
 801   return true;
 802 }
 803
 804 void
 805 cgraph_varpool_finalize_decl (tree decl)
 806 {
 807   struct cgraph_varpool_node *node = cgraph_varpool_node (decl);
 808
 809   /* The first declaration of a variable that comes through this function
 810      decides whether it is global (in C, has external linkage)
 811      or local (in C, has internal linkage).  So do nothing more
 812      if this function has already run.  */
 813   if (node->finalized)
 814     {
 815       if (cgraph_global_info_ready || !flag_unit_at_a_time)
 816         cgraph_varpool_assemble_pending_decls ();
 817       return;
 818     }
 819   if (node->needed)
 820     cgraph_varpool_enqueue_needed_node (node);
 821   node->finalized = true;
 822
 823   if (decide_is_variable_needed (node, decl))
 824     cgraph_varpool_mark_needed_node (node);
 825   if (cgraph_global_info_ready || !flag_unit_at_a_time)
 826     cgraph_varpool_assemble_pending_decls ();
 827 }
 828
 829 /* Return true when the DECL can possibly be inlined.  */
 830 bool
 831 cgraph_function_possibly_inlined_p (tree decl)
 832 {
 833   if (!cgraph_global_info_ready)
 834     return (DECL_INLINE (decl) && !flag_really_no_inline);
 835   return DECL_POSSIBLY_INLINED (decl);
 836 }
 837
 838 /* Create clone of E in the node N represented by CALL_EXPR the callgraph.  */
 839 struct cgraph_edge *
 840 cgraph_clone_edge (struct cgraph_edge *e, struct cgraph_node *n,
 841                    tree call_expr, int count_scale, int loop_nest)
 842 {
 843   struct cgraph_edge *new;
 844
 845   new = cgraph_create_edge (n, e->callee, call_expr,
 846                             e->count * count_scale / REG_BR_PROB_BASE,
 847                             e->loop_nest + loop_nest);
 848
 849   new->inline_failed = e->inline_failed;
 850   e->count -= new->count;
 851   return new;
 852 }
 853
 854 /* Create node representing clone of N executed COUNT times.  Decrease
 855    the execution counts from original node too.  */
 856 struct cgraph_node *
 857 cgraph_clone_node (struct cgraph_node *n, gcov_type count, int loop_nest)
 858 {
 859   struct cgraph_node *new = cgraph_create_node ();
 860   struct cgraph_edge *e;
 861   int count_scale;
 862
 863   new->decl = n->decl;
 864   new->origin = n->origin;
 865   if (new->origin)
 866     {
 867       new->next_nested = new->origin->nested;
 868       new->origin->nested = new;
 869     }
 870   new->analyzed = n->analyzed;
 871   new->local = n->local;
 872   new->global = n->global;
 873   new->rtl = n->rtl;
 874   new->count = count;
 875   if (n->count)
 876     count_scale = new->count * REG_BR_PROB_BASE / n->count;
 877   else
 878     count_scale = 0;
 879   n->count -= count;
 880
 881   for (e = n->callees;e; e=e->next_callee)
 882     cgraph_clone_edge (e, new, e->call_expr, count_scale, loop_nest);
 883
 884   new->next_clone = n->next_clone;
 885   new->prev_clone = n;
 886   n->next_clone = new;
 887   if (new->next_clone)
 888     new->next_clone->prev_clone = new;
 889
 890   return new;
 891 }
 892
 893 /* NODE is no longer nested function; update cgraph accordingly.  */
 894 void
 895 cgraph_unnest_node (struct cgraph_node *node)
 896 {
 897   struct cgraph_node **node2 = &node->origin->nested;
 898   gcc_assert (node->origin);
 899
 900   while (*node2 != node)
 901     node2 = &(*node2)->next_nested;
 902   *node2 = node->next_nested;
 903   node->origin = NULL;
 904 }
 905 #include "gt-cgraph.h"