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