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