gcc/cgraph.c

   1 /* Callgraph handling code.
   2    Copyright (C) 2003, 2004, 2005, 2006 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
  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.
  32
  33     The mapping from declarations to call-graph nodes is done using hash table
  34     based on DECL_UID.  The call-graph nodes are created lazily using
  35     cgraph_node function when called for unknown declaration.
  36
  37     The callgraph at the moment does not represent indirect calls or calls
  38     from other compilation unit.  Flag NEEDED is set for each node that may
  39     be accessed in such an invisible way and it shall be considered an
  40     entry point to the callgraph.
  41
  42     Interprocedural information:
  43
  44       Callgraph is place to store data needed for interprocedural optimization.
  45       All data structures are divided into three components: local_info that
  46       is produced while analyzing the function, global_info that is result
  47       of global walking of the callgraph on the end of compilation and
  48       rtl_info used by RTL backend to propagate data from already compiled
  49       functions to their callers.
  50
  51     Inlining plans:
  52
  53       The function inlining information is decided in advance and maintained
  54       in the callgraph as so called inline plan.
  55       For each inlined call, the callee's node is cloned to represent the
  56       new function copy produced by inliner.
  57       Each inlined call gets a unique corresponding clone node of the callee
  58       and the data structure is updated while inlining is performed, so
  59       the clones are eliminated and their callee edges redirected to the
  60       caller.
  61
  62       Each edge has "inline_failed" field.  When the field is set to NULL,
  63       the call will be inlined.  When it is non-NULL it contains a reason
  64       why inlining wasn't performed.  */
  65
  66 #include "config.h"
  67 #include "system.h"
  68 #include "coretypes.h"
  69 #include "tm.h"
  70 #include "tree.h"
  71 #include "tree-inline.h"
  72 #include "langhooks.h"
  73 #include "hashtab.h"
  74 #include "toplev.h"
  75 #include "flags.h"
  76 #include "ggc.h"
  77 #include "debug.h"
  78 #include "target.h"
  79 #include "basic-block.h"
  80 #include "cgraph.h"
  81 #include "varray.h"
  82 #include "output.h"
  83 #include "intl.h"
  84 #include "tree-gimple.h"
  85 #include "tree-dump.h"
  86
  87 static void cgraph_node_remove_callers (struct cgraph_node *node);
  88 static inline void cgraph_edge_remove_caller (struct cgraph_edge *e);
  89 static inline void cgraph_edge_remove_callee (struct cgraph_edge *e);
  90
  91 /* Hash table used to convert declarations into nodes.  */
  92 static GTY((param_is (struct cgraph_node))) htab_t cgraph_hash;
  93
  94 /* The linked list of cgraph nodes.  */
  95 struct cgraph_node *cgraph_nodes;
  96
  97 /* Queue of cgraph nodes scheduled to be lowered.  */
  98 struct cgraph_node *cgraph_nodes_queue;
  99
 100 /* Queue of cgraph nodes scheduled to be expanded.  This is a
 101    secondary queue used during optimization to accommodate passes that
 102    may generate new functions that need to be optimized and expanded.  */
 103 struct cgraph_node *cgraph_expand_queue;
 104
 105 /* Number of nodes in existence.  */
 106 int cgraph_n_nodes;
 107
 108 /* Maximal uid used in cgraph nodes.  */
 109 int cgraph_max_uid;
 110
 111 /* Set when whole unit has been analyzed so we can access global info.  */
 112 bool cgraph_global_info_ready = false;
 113
 114 /* Set when the cgraph is fully build and the basic flags are computed.  */
 115 bool cgraph_function_flags_ready = false;
 116
 117 /* Linked list of cgraph asm nodes.  */
 118 struct cgraph_asm_node *cgraph_asm_nodes;
 119
 120 /* Last node in cgraph_asm_nodes.  */
 121 static GTY(()) struct cgraph_asm_node *cgraph_asm_last_node;
 122
 123 /* The order index of the next cgraph node to be created.  This is
 124    used so that we can sort the cgraph nodes in order by when we saw
 125    them, to support -fno-toplevel-reorder.  */
 126 int cgraph_order;
 127
 128 static hashval_t hash_node (const void *);
 129 static int eq_node (const void *, const void *);
 130
 131 /* Returns a hash code for P.  */
 132
 133 static hashval_t
 134 hash_node (const void *p)
 135 {
 136   const struct cgraph_node *n = (const struct cgraph_node *) p;
 137   return (hashval_t) DECL_UID (n->decl);
 138 }
 139
 140 /* Returns nonzero if P1 and P2 are equal.  */
 141
 142 static int
 143 eq_node (const void *p1, const void *p2)
 144 {
 145   const struct cgraph_node *n1 = (const struct cgraph_node *) p1;
 146   const struct cgraph_node *n2 = (const struct cgraph_node *) p2;
 147   return DECL_UID (n1->decl) == DECL_UID (n2->decl);
 148 }
 149
 150 /* Allocate new callgraph node and insert it into basic data structures.  */
 151
 152 static struct cgraph_node *
 153 cgraph_create_node (void)
 154 {
 155   struct cgraph_node *node;
 156
 157   node = GGC_CNEW (struct cgraph_node);
 158   node->next = cgraph_nodes;
 159   node->uid = cgraph_max_uid++;
 160   node->order = cgraph_order++;
 161   if (cgraph_nodes)
 162     cgraph_nodes->previous = node;
 163   node->previous = NULL;
 164   node->global.estimated_growth = INT_MIN;
 165   cgraph_nodes = node;
 166   cgraph_n_nodes++;
 167   return node;
 168 }
 169
 170 /* Return cgraph node assigned to DECL.  Create new one when needed.  */
 171
 172 struct cgraph_node *
 173 cgraph_node (tree decl)
 174 {
 175   struct cgraph_node key, *node, **slot;
 176
 177   gcc_assert (TREE_CODE (decl) == FUNCTION_DECL);
 178
 179   if (!cgraph_hash)
 180     cgraph_hash = htab_create_ggc (10, hash_node, eq_node, NULL);
 181
 182   key.decl = decl;
 183
 184   slot = (struct cgraph_node **) htab_find_slot (cgraph_hash, &key, INSERT);
 185
 186   if (*slot)
 187     {
 188       node = *slot;
 189       if (!node->master_clone)
 190         node->master_clone = node;
 191       return node;
 192     }
 193
 194   node = cgraph_create_node ();
 195   node->decl = decl;
 196   *slot = node;
 197   if (DECL_CONTEXT (decl) && TREE_CODE (DECL_CONTEXT (decl)) == FUNCTION_DECL)
 198     {
 199       node->origin = cgraph_node (DECL_CONTEXT (decl));
 200       node->next_nested = node->origin->nested;
 201       node->origin->nested = node;
 202       node->master_clone = node;
 203     }
 204   return node;
 205 }
 206
 207 /* Insert already constructed node into hashtable.  */
 208
 209 void
 210 cgraph_insert_node_to_hashtable (struct cgraph_node *node)
 211 {
 212   struct cgraph_node **slot;
 213
 214   slot = (struct cgraph_node **) htab_find_slot (cgraph_hash, node, INSERT);
 215
 216   gcc_assert (!*slot);
 217   *slot = node;
 218 }
 219
 220
 221 /* Return the cgraph node that has ASMNAME for its DECL_ASSEMBLER_NAME.
 222    Return NULL if there's no such node.  */
 223
 224 struct cgraph_node *
 225 cgraph_node_for_asm (tree asmname)
 226 {
 227   struct cgraph_node *node;
 228
 229   for (node = cgraph_nodes; node ; node = node->next)
 230     if (decl_assembler_name_equal (node->decl, asmname))
 231       return node;
 232
 233   return NULL;
 234 }
 235
 236 /* Returns a hash value for X (which really is a die_struct).  */
 237
 238 static hashval_t
 239 edge_hash (const void *x)
 240 {
 241   return htab_hash_pointer (((struct cgraph_edge *) x)->call_stmt);
 242 }
 243
 244 /* Return nonzero if decl_id of die_struct X is the same as UID of decl *Y.  */
 245
 246 static int
 247 edge_eq (const void *x, const void *y)
 248 {
 249   return ((struct cgraph_edge *) x)->call_stmt == y;
 250 }
 251
 252 /* Return callgraph edge representing CALL_EXPR statement.  */
 253 struct cgraph_edge *
 254 cgraph_edge (struct cgraph_node *node, tree call_stmt)
 255 {
 256   struct cgraph_edge *e, *e2;
 257   int n = 0;
 258
 259   if (node->call_site_hash)
 260     return htab_find_with_hash (node->call_site_hash, call_stmt,
 261                                 htab_hash_pointer (call_stmt));
 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     {
 270       if (e->call_stmt == call_stmt)
 271         break;
 272       n++;
 273     }
 274   if (n > 100)
 275     {
 276       node->call_site_hash = htab_create_ggc (120, edge_hash, edge_eq, NULL);
 277       for (e2 = node->callees; e2; e2 = e2->next_callee)
 278         {
 279           void **slot;
 280           slot = htab_find_slot_with_hash (node->call_site_hash,
 281                                            e2->call_stmt,
 282                                            htab_hash_pointer (e2->call_stmt),
 283                                            INSERT);
 284           gcc_assert (!*slot);
 285           *slot = e2;
 286         }
 287     }
 288   return e;
 289 }
 290
 291 /* Change call_smtt of edge E to NEW_STMT.  */
 292
 293 void
 294 cgraph_set_call_stmt (struct cgraph_edge *e, tree new_stmt)
 295 {
 296   if (e->caller->call_site_hash)
 297     {
 298       htab_remove_elt_with_hash (e->caller->call_site_hash,
 299                                  e->call_stmt,
 300                                  htab_hash_pointer (e->call_stmt));
 301     }
 302   e->call_stmt = new_stmt;
 303   if (e->caller->call_site_hash)
 304     {
 305       void **slot;
 306       slot = htab_find_slot_with_hash (e->caller->call_site_hash,
 307                                        e->call_stmt,
 308                                        htab_hash_pointer
 309                                        (e->call_stmt), INSERT);
 310       gcc_assert (!*slot);
 311       *slot = e;
 312     }
 313 }
 314
 315 /* Create edge from CALLER to CALLEE in the cgraph.  */
 316
 317 struct cgraph_edge *
 318 cgraph_create_edge (struct cgraph_node *caller, struct cgraph_node *callee,
 319                     tree call_stmt, gcov_type count, int nest)
 320 {
 321   struct cgraph_edge *edge = GGC_NEW (struct cgraph_edge);
 322 #ifdef ENABLE_CHECKING
 323   struct cgraph_edge *e;
 324
 325   for (e = caller->callees; e; e = e->next_callee)
 326     gcc_assert (e->call_stmt != call_stmt);
 327 #endif
 328
 329   gcc_assert (get_call_expr_in (call_stmt));
 330
 331   if (!DECL_SAVED_TREE (callee->decl))
 332     edge->inline_failed = N_("function body not available");
 333   else if (callee->local.redefined_extern_inline)
 334     edge->inline_failed = N_("redefined extern inline functions are not "
 335                              "considered for inlining");
 336   else if (callee->local.inlinable)
 337     edge->inline_failed = N_("function not considered for inlining");
 338   else
 339     edge->inline_failed = N_("function not inlinable");
 340
 341   edge->aux = NULL;
 342
 343   edge->caller = caller;
 344   edge->callee = callee;
 345   edge->call_stmt = call_stmt;
 346   edge->prev_caller = NULL;
 347   edge->next_caller = callee->callers;
 348   if (callee->callers)
 349     callee->callers->prev_caller = edge;
 350   edge->prev_callee = NULL;
 351   edge->next_callee = caller->callees;
 352   if (caller->callees)
 353     caller->callees->prev_callee = edge;
 354   caller->callees = edge;
 355   callee->callers = edge;
 356   edge->count = count;
 357   edge->loop_nest = nest;
 358   if (caller->call_site_hash)
 359     {
 360       void **slot;
 361       slot = htab_find_slot_with_hash (caller->call_site_hash,
 362                                        edge->call_stmt,
 363                                        htab_hash_pointer
 364                                          (edge->call_stmt),
 365                                        INSERT);
 366       gcc_assert (!*slot);
 367       *slot = edge;
 368     }
 369   return edge;
 370 }
 371
 372 /* Remove the edge E from the list of the callers of the callee.  */
 373
 374 static inline void
 375 cgraph_edge_remove_callee (struct cgraph_edge *e)
 376 {
 377   if (e->prev_caller)
 378     e->prev_caller->next_caller = e->next_caller;
 379   if (e->next_caller)
 380     e->next_caller->prev_caller = e->prev_caller;
 381   if (!e->prev_caller)
 382     e->callee->callers = e->next_caller;
 383 }
 384
 385 /* Remove the edge E from the list of the callees of the caller.  */
 386
 387 static inline void
 388 cgraph_edge_remove_caller (struct cgraph_edge *e)
 389 {
 390   if (e->prev_callee)
 391     e->prev_callee->next_callee = e->next_callee;
 392   if (e->next_callee)
 393     e->next_callee->prev_callee = e->prev_callee;
 394   if (!e->prev_callee)
 395     e->caller->callees = e->next_callee;
 396   if (e->caller->call_site_hash)
 397     htab_remove_elt_with_hash (e->caller->call_site_hash,
 398                                e->call_stmt,
 399                                htab_hash_pointer (e->call_stmt));
 400 }
 401
 402 /* Remove the edge E in the cgraph.  */
 403
 404 void
 405 cgraph_remove_edge (struct cgraph_edge *e)
 406 {
 407   /* Remove from callers list of the callee.  */
 408   cgraph_edge_remove_callee (e);
 409
 410   /* Remove from callees list of the callers.  */
 411   cgraph_edge_remove_caller (e);
 412 }
 413
 414 /* Redirect callee of E to N.  The function does not update underlying
 415    call expression.  */
 416
 417 void
 418 cgraph_redirect_edge_callee (struct cgraph_edge *e, struct cgraph_node *n)
 419 {
 420   /* Remove from callers list of the current callee.  */
 421   cgraph_edge_remove_callee (e);
 422
 423   /* Insert to callers list of the new callee.  */
 424   e->prev_caller = NULL;
 425   if (n->callers)
 426     n->callers->prev_caller = e;
 427   e->next_caller = n->callers;
 428   n->callers = e;
 429   e->callee = n;
 430 }
 431
 432 /* Remove all callees from the node.  */
 433
 434 void
 435 cgraph_node_remove_callees (struct cgraph_node *node)
 436 {
 437   struct cgraph_edge *e;
 438
 439   /* It is sufficient to remove the edges from the lists of callers of
 440      the callees.  The callee list of the node can be zapped with one
 441      assignment.  */
 442   for (e = node->callees; e; e = e->next_callee)
 443     cgraph_edge_remove_callee (e);
 444   node->callees = NULL;
 445   if (node->call_site_hash)
 446     {
 447       htab_delete (node->call_site_hash);
 448       node->call_site_hash = NULL;
 449     }
 450 }
 451
 452 /* Remove all callers from the node.  */
 453
 454 static void
 455 cgraph_node_remove_callers (struct cgraph_node *node)
 456 {
 457   struct cgraph_edge *e;
 458
 459   /* It is sufficient to remove the edges from the lists of callees of
 460      the callers.  The caller list of the node can be zapped with one
 461      assignment.  */
 462   for (e = node->callers; e; e = e->next_caller)
 463     cgraph_edge_remove_caller (e);
 464   node->callers = NULL;
 465 }
 466
 467 /* Remove the node from cgraph.  */
 468
 469 void
 470 cgraph_remove_node (struct cgraph_node *node)
 471 {
 472   void **slot;
 473   bool kill_body = false;
 474
 475   cgraph_node_remove_callers (node);
 476   cgraph_node_remove_callees (node);
 477   /* Incremental inlining access removed nodes stored in the postorder list.
 478      */
 479   node->needed = node->reachable = false;
 480   while (node->nested)
 481     cgraph_remove_node (node->nested);
 482   if (node->origin)
 483     {
 484       struct cgraph_node **node2 = &node->origin->nested;
 485
 486       while (*node2 != node)
 487         node2 = &(*node2)->next_nested;
 488       *node2 = node->next_nested;
 489     }
 490   if (node->previous)
 491     node->previous->next = node->next;
 492   else
 493     cgraph_nodes = node->next;
 494   if (node->next)
 495     node->next->previous = node->previous;
 496   node->next = NULL;
 497   node->previous = NULL;
 498   slot = htab_find_slot (cgraph_hash, node, NO_INSERT);
 499   if (*slot == node)
 500     {
 501       if (node->next_clone)
 502       {
 503         struct cgraph_node *new_node = node->next_clone;
 504         struct cgraph_node *n;
 505
 506         /* Make the next clone be the master clone */
 507         for (n = new_node; n; n = n->next_clone)
 508           n->master_clone = new_node;
 509
 510         *slot = new_node;
 511         node->next_clone->prev_clone = NULL;
 512       }
 513       else
 514         {
 515           htab_clear_slot (cgraph_hash, slot);
 516           kill_body = true;
 517         }
 518     }
 519   else
 520     {
 521       node->prev_clone->next_clone = node->next_clone;
 522       if (node->next_clone)
 523         node->next_clone->prev_clone = node->prev_clone;
 524     }
 525
 526   /* While all the clones are removed after being proceeded, the function
 527      itself is kept in the cgraph even after it is compiled.  Check whether
 528      we are done with this body and reclaim it proactively if this is the case.
 529      */
 530   if (!kill_body && *slot)
 531     {
 532       struct cgraph_node *n = (struct cgraph_node *) *slot;
 533       if (!n->next_clone && !n->global.inlined_to
 534           && (cgraph_global_info_ready
 535               && (TREE_ASM_WRITTEN (n->decl) || DECL_EXTERNAL (n->decl))))
 536         kill_body = true;
 537     }
 538
 539   if (kill_body && flag_unit_at_a_time)
 540     {
 541       DECL_SAVED_TREE (node->decl) = NULL;
 542       DECL_STRUCT_FUNCTION (node->decl) = NULL;
 543       DECL_INITIAL (node->decl) = error_mark_node;
 544     }
 545   node->decl = NULL;
 546   if (node->call_site_hash)
 547     {
 548       htab_delete (node->call_site_hash);
 549       node->call_site_hash = NULL;
 550     }
 551   cgraph_n_nodes--;
 552   /* Do not free the structure itself so the walk over chain can continue.  */
 553 }
 554
 555 /* Notify finalize_compilation_unit that given node is reachable.  */
 556
 557 void
 558 cgraph_mark_reachable_node (struct cgraph_node *node)
 559 {
 560   if (!node->reachable && node->local.finalized)
 561     {
 562       notice_global_symbol (node->decl);
 563       node->reachable = 1;
 564       gcc_assert (!cgraph_global_info_ready);
 565
 566       node->next_needed = cgraph_nodes_queue;
 567       cgraph_nodes_queue = node;
 568     }
 569 }
 570
 571 /* Likewise indicate that a node is needed, i.e. reachable via some
 572    external means.  */
 573
 574 void
 575 cgraph_mark_needed_node (struct cgraph_node *node)
 576 {
 577   node->needed = 1;
 578   cgraph_mark_reachable_node (node);
 579 }
 580
 581 /* Return local info for the compiled function.  */
 582
 583 struct cgraph_local_info *
 584 cgraph_local_info (tree decl)
 585 {
 586   struct cgraph_node *node;
 587
 588   gcc_assert (TREE_CODE (decl) == FUNCTION_DECL);
 589   node = cgraph_node (decl);
 590   return &node->local;
 591 }
 592
 593 /* Return local info for the compiled function.  */
 594
 595 struct cgraph_global_info *
 596 cgraph_global_info (tree decl)
 597 {
 598   struct cgraph_node *node;
 599
 600   gcc_assert (TREE_CODE (decl) == FUNCTION_DECL && cgraph_global_info_ready);
 601   node = cgraph_node (decl);
 602   return &node->global;
 603 }
 604
 605 /* Return local info for the compiled function.  */
 606
 607 struct cgraph_rtl_info *
 608 cgraph_rtl_info (tree decl)
 609 {
 610   struct cgraph_node *node;
 611
 612   gcc_assert (TREE_CODE (decl) == FUNCTION_DECL);
 613   node = cgraph_node (decl);
 614   if (decl != current_function_decl
 615       && !TREE_ASM_WRITTEN (node->decl))
 616     return NULL;
 617   return &node->rtl;
 618 }
 619
 620 /* Return name of the node used in debug output.  */
 621 const char *
 622 cgraph_node_name (struct cgraph_node *node)
 623 {
 624   return lang_hooks.decl_printable_name (node->decl, 2);
 625 }
 626
 627 /* Names used to print out the availability enum.  */
 628 const char * const cgraph_availability_names[] =
 629   {"unset", "not_available", "overwrittable", "available", "local"};
 630
 631 /* Dump given cgraph node.  */
 632 void
 633 dump_cgraph_node (FILE *f, struct cgraph_node *node)
 634 {
 635   struct cgraph_edge *edge;
 636   fprintf (f, "%s/%i:", cgraph_node_name (node), node->uid);
 637   if (node->global.inlined_to)
 638     fprintf (f, " (inline copy in %s/%i)",
 639              cgraph_node_name (node->global.inlined_to),
 640              node->global.inlined_to->uid);
 641   if (cgraph_function_flags_ready)
 642     fprintf (f, " availability:%s",
 643              cgraph_availability_names [cgraph_function_body_availability (node)]);
 644   if (node->master_clone && node->master_clone->uid != node->uid)
 645     fprintf (f, "(%i)", node->master_clone->uid);
 646   if (node->count)
 647     fprintf (f, " executed "HOST_WIDEST_INT_PRINT_DEC"x",
 648              (HOST_WIDEST_INT)node->count);
 649   if (node->local.self_insns)
 650     fprintf (f, " %i insns", node->local.self_insns);
 651   if (node->global.insns && node->global.insns != node->local.self_insns)
 652     fprintf (f, " (%i after inlining)", node->global.insns);
 653   if (node->local.estimated_self_stack_size)
 654     fprintf (f, " %i bytes stack usage", (int)node->local.estimated_self_stack_size);
 655   if (node->global.estimated_stack_size != node->local.estimated_self_stack_size)
 656     fprintf (f, " %i bytes after inlining", (int)node->global.estimated_stack_size);
 657   if (node->origin)
 658     fprintf (f, " nested in: %s", cgraph_node_name (node->origin));
 659   if (node->needed)
 660     fprintf (f, " needed");
 661   else if (node->reachable)
 662     fprintf (f, " reachable");
 663   if (DECL_SAVED_TREE (node->decl))
 664     fprintf (f, " tree");
 665   if (node->output)
 666     fprintf (f, " output");
 667   if (node->local.local)
 668     fprintf (f, " local");
 669   if (node->local.externally_visible)
 670     fprintf (f, " externally_visible");
 671   if (node->local.finalized)
 672     fprintf (f, " finalized");
 673   if (node->local.disregard_inline_limits)
 674     fprintf (f, " always_inline");
 675   else if (node->local.inlinable)
 676     fprintf (f, " inlinable");
 677   if (node->local.redefined_extern_inline)
 678     fprintf (f, " redefined_extern_inline");
 679   if (TREE_ASM_WRITTEN (node->decl))
 680     fprintf (f, " asm_written");
 681
 682   fprintf (f, "\n  called by: ");
 683   for (edge = node->callers; edge; edge = edge->next_caller)
 684     {
 685       fprintf (f, "%s/%i ", cgraph_node_name (edge->caller),
 686                edge->caller->uid);
 687       if (edge->count)
 688         fprintf (f, "("HOST_WIDEST_INT_PRINT_DEC"x) ",
 689                  (HOST_WIDEST_INT)edge->count);
 690       if (!edge->inline_failed)
 691         fprintf(f, "(inlined) ");
 692     }
 693
 694   fprintf (f, "\n  calls: ");
 695   for (edge = node->callees; edge; edge = edge->next_callee)
 696     {
 697       fprintf (f, "%s/%i ", cgraph_node_name (edge->callee),
 698                edge->callee->uid);
 699       if (!edge->inline_failed)
 700         fprintf(f, "(inlined) ");
 701       if (edge->count)
 702         fprintf (f, "("HOST_WIDEST_INT_PRINT_DEC"x) ",
 703                  (HOST_WIDEST_INT)edge->count);
 704       if (edge->loop_nest)
 705         fprintf (f, "(nested in %i loops) ", edge->loop_nest);
 706     }
 707   fprintf (f, "\n");
 708 }
 709
 710 /* Dump the callgraph.  */
 711
 712 void
 713 dump_cgraph (FILE *f)
 714 {
 715   struct cgraph_node *node;
 716
 717   fprintf (f, "callgraph:\n\n");
 718   for (node = cgraph_nodes; node; node = node->next)
 719     dump_cgraph_node (f, node);
 720 }
 721
 722 /* Set the DECL_ASSEMBLER_NAME and update cgraph hashtables.  */
 723 void
 724 change_decl_assembler_name (tree decl, tree name)
 725 {
 726   if (!DECL_ASSEMBLER_NAME_SET_P (decl))
 727     {
 728       SET_DECL_ASSEMBLER_NAME (decl, name);
 729       return;
 730     }
 731   if (name == DECL_ASSEMBLER_NAME (decl))
 732     return;
 733
 734   if (TREE_SYMBOL_REFERENCED (DECL_ASSEMBLER_NAME (decl))
 735       && DECL_RTL_SET_P (decl))
 736     warning (0, "%D renamed after being referenced in assembly", decl);
 737
 738   SET_DECL_ASSEMBLER_NAME (decl, name);
 739 }
 740
 741 /* Add a top-level asm statement to the list.  */
 742
 743 struct cgraph_asm_node *
 744 cgraph_add_asm_node (tree asm_str)
 745 {
 746   struct cgraph_asm_node *node;
 747
 748   node = GGC_CNEW (struct cgraph_asm_node);
 749   node->asm_str = asm_str;
 750   node->order = cgraph_order++;
 751   node->next = NULL;
 752   if (cgraph_asm_nodes == NULL)
 753     cgraph_asm_nodes = node;
 754   else
 755     cgraph_asm_last_node->next = node;
 756   cgraph_asm_last_node = node;
 757   return node;
 758 }
 759
 760 /* Return true when the DECL can possibly be inlined.  */
 761 bool
 762 cgraph_function_possibly_inlined_p (tree decl)
 763 {
 764   if (!cgraph_global_info_ready)
 765     return (DECL_INLINE (decl) && !flag_really_no_inline);
 766   return DECL_POSSIBLY_INLINED (decl);
 767 }
 768
 769 /* Create clone of E in the node N represented by CALL_EXPR the callgraph.  */
 770 struct cgraph_edge *
 771 cgraph_clone_edge (struct cgraph_edge *e, struct cgraph_node *n,
 772                    tree call_stmt, gcov_type count_scale, int loop_nest,
 773                    bool update_original)
 774 {
 775   struct cgraph_edge *new;
 776
 777   new = cgraph_create_edge (n, e->callee, call_stmt,
 778                             e->count * count_scale / REG_BR_PROB_BASE,
 779                             e->loop_nest + loop_nest);
 780
 781   new->inline_failed = e->inline_failed;
 782   if (update_original)
 783     {
 784       e->count -= new->count;
 785       if (e->count < 0)
 786         e->count = 0;
 787     }
 788   return new;
 789 }
 790
 791 /* Create node representing clone of N executed COUNT times.  Decrease
 792    the execution counts from original node too.
 793
 794    When UPDATE_ORIGINAL is true, the counts are subtracted from the original
 795    function's profile to reflect the fact that part of execution is handled
 796    by node.  */
 797 struct cgraph_node *
 798 cgraph_clone_node (struct cgraph_node *n, gcov_type count, int loop_nest,
 799                    bool update_original)
 800 {
 801   struct cgraph_node *new = cgraph_create_node ();
 802   struct cgraph_edge *e;
 803   gcov_type count_scale;
 804
 805   new->decl = n->decl;
 806   new->origin = n->origin;
 807   if (new->origin)
 808     {
 809       new->next_nested = new->origin->nested;
 810       new->origin->nested = new;
 811     }
 812   new->analyzed = n->analyzed;
 813   new->local = n->local;
 814   new->global = n->global;
 815   new->rtl = n->rtl;
 816   new->master_clone = n->master_clone;
 817   new->count = count;
 818   if (n->count)
 819     count_scale = new->count * REG_BR_PROB_BASE / n->count;
 820   else
 821     count_scale = 0;
 822   if (update_original)
 823     {
 824       n->count -= count;
 825       if (n->count < 0)
 826         n->count = 0;
 827     }
 828
 829   for (e = n->callees;e; e=e->next_callee)
 830     cgraph_clone_edge (e, new, e->call_stmt, count_scale, loop_nest,
 831                        update_original);
 832
 833   new->next_clone = n->next_clone;
 834   new->prev_clone = n;
 835   n->next_clone = new;
 836   if (new->next_clone)
 837     new->next_clone->prev_clone = new;
 838
 839   return new;
 840 }
 841
 842 /* Return true if N is an master_clone, (see cgraph_master_clone).  */
 843
 844 bool
 845 cgraph_is_master_clone (struct cgraph_node *n)
 846 {
 847   return (n == cgraph_master_clone (n));
 848 }
 849
 850 struct cgraph_node *
 851 cgraph_master_clone (struct cgraph_node *n)
 852 {
 853   enum availability avail = cgraph_function_body_availability (n);
 854
 855   if (avail == AVAIL_NOT_AVAILABLE || avail == AVAIL_OVERWRITABLE)
 856     return NULL;
 857
 858   if (!n->master_clone)
 859     n->master_clone = cgraph_node (n->decl);
 860
 861   return n->master_clone;
 862 }
 863
 864 /* NODE is no longer nested function; update cgraph accordingly.  */
 865 void
 866 cgraph_unnest_node (struct cgraph_node *node)
 867 {
 868   struct cgraph_node **node2 = &node->origin->nested;
 869   gcc_assert (node->origin);
 870
 871   while (*node2 != node)
 872     node2 = &(*node2)->next_nested;
 873   *node2 = node->next_nested;
 874   node->origin = NULL;
 875 }
 876
 877 /* Return function availability.  See cgraph.h for description of individual
 878    return values.  */
 879 enum availability
 880 cgraph_function_body_availability (struct cgraph_node *node)
 881 {
 882   enum availability avail;
 883   gcc_assert (cgraph_function_flags_ready);
 884   if (!node->analyzed)
 885     avail = AVAIL_NOT_AVAILABLE;
 886   else if (node->local.local)
 887     avail = AVAIL_LOCAL;
 888   else if (node->local.externally_visible)
 889     avail = AVAIL_AVAILABLE;
 890
 891   /* If the function can be overwritten, return OVERWRITABLE.  Take
 892      care at least of two notable extensions - the COMDAT functions
 893      used to share template instantiations in C++ (this is symmetric
 894      to code cp_cannot_inline_tree_fn and probably shall be shared and
 895      the inlinability hooks completely eliminated).
 896
 897      ??? Does the C++ one definition rule allow us to always return
 898      AVAIL_AVAILABLE here?  That would be good reason to preserve this
 899      hook Similarly deal with extern inline functions - this is again
 900      necessary to get C++ shared functions having keyed templates
 901      right and in the C extension documentation we probably should
 902      document the requirement of both versions of function (extern
 903      inline and offline) having same side effect characteristics as
 904      good optimization is what this optimization is about.  */
 905
 906   else if (!(*targetm.binds_local_p) (node->decl)
 907            && !DECL_COMDAT (node->decl) && !DECL_EXTERNAL (node->decl))
 908     avail = AVAIL_OVERWRITABLE;
 909   else avail = AVAIL_AVAILABLE;
 910
 911   return avail;
 912 }
 913
 914 /* Add the function FNDECL to the call graph.  FNDECL is assumed to be
 915    in low GIMPLE form and ready to be processed by cgraph_finalize_function.
 916
 917    When operating in unit-at-a-time, a new callgraph node is added to
 918    CGRAPH_EXPAND_QUEUE, which is processed after all the original
 919    functions in the call graph .
 920
 921    When not in unit-at-a-time, the new callgraph node is added to
 922    CGRAPH_NODES_QUEUE for cgraph_assemble_pending_functions to
 923    process.  */
 924
 925 void
 926 cgraph_add_new_function (tree fndecl)
 927 {
 928   struct cgraph_node *n = cgraph_node (fndecl);
 929   n->next_needed = cgraph_expand_queue;
 930   cgraph_expand_queue = n;
 931 }
 932
 933 #include "gt-cgraph.h"