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