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