gcc/cgraph.c

   1 /* Callgraph handling code.
   2    Copyright (C) 2003, 2004, 2005, 2006, 2007 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 3, 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 COPYING3.  If not see
  19 <http://www.gnu.org/licenses/>.  */
  20
  21 /*  This file contains basic routines manipulating call graph
  22
  23 The callgraph:
  24
  25     The call-graph is data structure designed for intra-procedural optimization
  26     but it is also used in non-unit-at-a-time compilation to allow easier code
  27     sharing.
  28
  29     The call-graph consist of nodes and edges represented via linked lists.
  30     Each function (external or not) corresponds to the unique node.
  31
  32     The mapping from declarations to call-graph nodes is done using hash table
  33     based on DECL_UID.  The call-graph nodes are created lazily using
  34     cgraph_node function when called for unknown declaration.
  35
  36     The callgraph at the moment does not represent indirect calls or calls
  37     from other compilation unit.  Flag NEEDED is set for each node that may
  38     be accessed in such an invisible way and it shall be considered an
  39     entry point to the callgraph.
  40
  41     Interprocedural information:
  42
  43       Callgraph is place to store data needed for interprocedural optimization.
  44       All data structures are divided into three components: local_info that
  45       is produced while analyzing the function, global_info that is result
  46       of global walking of the callgraph on the end of compilation and
  47       rtl_info used by RTL backend to propagate data from already compiled
  48       functions to their callers.
  49
  50     Inlining plans:
  51
  52       The function inlining information is decided in advance and maintained
  53       in the callgraph as so called inline plan.
  54       For each inlined call, the callee's node is cloned to represent the
  55       new function copy produced by inliner.
  56       Each inlined call gets a unique corresponding clone node of the callee
  57       and the data structure is updated while inlining is performed, so
  58       the clones are eliminated and their callee edges redirected to the
  59       caller.
  60
  61       Each edge has "inline_failed" field.  When the field is set to NULL,
  62       the call will be inlined.  When it is non-NULL it contains a reason
  63       why inlining wasn't performed.  */
  64
  65 #include "config.h"
  66 #include "system.h"
  67 #include "coretypes.h"
  68 #include "tm.h"
  69 #include "tree.h"
  70 #include "tree-inline.h"
  71 #include "langhooks.h"
  72 #include "hashtab.h"
  73 #include "toplev.h"
  74 #include "flags.h"
  75 #include "ggc.h"
  76 #include "debug.h"
  77 #include "target.h"
  78 #include "basic-block.h"
  79 #include "cgraph.h"
  80 #include "varray.h"
  81 #include "output.h"
  82 #include "intl.h"
  83 #include "tree-gimple.h"
  84 #include "tree-dump.h"
  85 #include "tree-flow.h"
  86
  87 static void cgraph_node_remove_callers (struct cgraph_node *node);
  88 static inline void cgraph_edge_remove_caller (struct cgraph_edge *e);
  89 static inline void cgraph_edge_remove_callee (struct cgraph_edge *e);
  90
  91 /* Hash table used to convert declarations into nodes.  */
  92 static GTY((param_is (struct cgraph_node))) htab_t cgraph_hash;
  93
  94 /* The linked list of cgraph nodes.  */
  95 struct cgraph_node *cgraph_nodes;
  96
  97 /* Queue of cgraph nodes scheduled to be lowered.  */
  98 struct cgraph_node *cgraph_nodes_queue;
  99
 100 /* Queue of cgraph nodes scheduled to be added into cgraph.  This is a
 101    secondary queue used during optimization to accommodate passes that
 102    may generate new functions that need to be optimized and expanded.  */
 103 struct cgraph_node *cgraph_new_nodes;
 104
 105 /* Number of nodes in existence.  */
 106 int cgraph_n_nodes;
 107
 108 /* Maximal uid used in cgraph nodes.  */
 109 int cgraph_max_uid;
 110
 111 /* Maximal pid used for profiling */
 112 int cgraph_max_pid;
 113
 114 /* Set when whole unit has been analyzed so we can access global info.  */
 115 bool cgraph_global_info_ready = false;
 116
 117 /* What state callgraph is in right now.  */
 118 enum cgraph_state cgraph_state = CGRAPH_STATE_CONSTRUCTION;
 119
 120 /* Set when the cgraph is fully build and the basic flags are computed.  */
 121 bool cgraph_function_flags_ready = false;
 122
 123 /* Linked list of cgraph asm nodes.  */
 124 struct cgraph_asm_node *cgraph_asm_nodes;
 125
 126 /* Last node in cgraph_asm_nodes.  */
 127 static GTY(()) struct cgraph_asm_node *cgraph_asm_last_node;
 128
 129 /* The order index of the next cgraph node to be created.  This is
 130    used so that we can sort the cgraph nodes in order by when we saw
 131    them, to support -fno-toplevel-reorder.  */
 132 int cgraph_order;
 133
 134 static hashval_t hash_node (const void *);
 135 static int eq_node (const void *, const void *);
 136
 137 /* Returns a hash code for P.  */
 138
 139 static hashval_t
 140 hash_node (const void *p)
 141 {
 142   const struct cgraph_node *n = (const struct cgraph_node *) p;
 143   return (hashval_t) DECL_UID (n->decl);
 144 }
 145
 146 /* Returns nonzero if P1 and P2 are equal.  */
 147
 148 static int
 149 eq_node (const void *p1, const void *p2)
 150 {
 151   const struct cgraph_node *n1 = (const struct cgraph_node *) p1;
 152   const struct cgraph_node *n2 = (const struct cgraph_node *) p2;
 153   return DECL_UID (n1->decl) == DECL_UID (n2->decl);
 154 }
 155
 156 /* Allocate new callgraph node and insert it into basic data structures.  */
 157
 158 static struct cgraph_node *
 159 cgraph_create_node (void)
 160 {
 161   struct cgraph_node *node;
 162
 163   node = GGC_CNEW (struct cgraph_node);
 164   node->next = cgraph_nodes;
 165   node->uid = cgraph_max_uid++;
 166   node->pid = -1;
 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   return node;
 175 }
 176
 177 /* Return cgraph node assigned to DECL.  Create new one when needed.  */
 178
 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 (((const 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 ((const 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
 300 void
 301 cgraph_set_call_stmt (struct cgraph_edge *e, tree new_stmt)
 302 {
 303   if (e->caller->call_site_hash)
 304     {
 305       htab_remove_elt_with_hash (e->caller->call_site_hash,
 306                                  e->call_stmt,
 307                                  htab_hash_pointer (e->call_stmt));
 308     }
 309   e->call_stmt = new_stmt;
 310   if (e->caller->call_site_hash)
 311     {
 312       void **slot;
 313       slot = htab_find_slot_with_hash (e->caller->call_site_hash,
 314                                        e->call_stmt,
 315                                        htab_hash_pointer
 316                                        (e->call_stmt), INSERT);
 317       gcc_assert (!*slot);
 318       *slot = e;
 319     }
 320 }
 321
 322 /* Create edge from CALLER to CALLEE in the cgraph.  */
 323
 324 struct cgraph_edge *
 325 cgraph_create_edge (struct cgraph_node *caller, struct cgraph_node *callee,
 326                     tree call_stmt, gcov_type count, int freq, int nest)
 327 {
 328   struct cgraph_edge *edge = GGC_NEW (struct cgraph_edge);
 329 #ifdef ENABLE_CHECKING
 330   struct cgraph_edge *e;
 331
 332   for (e = caller->callees; e; e = e->next_callee)
 333     gcc_assert (e->call_stmt != call_stmt);
 334 #endif
 335
 336   gcc_assert (get_call_expr_in (call_stmt));
 337
 338   if (!DECL_SAVED_TREE (callee->decl))
 339     edge->inline_failed = N_("function body not available");
 340   else if (callee->local.redefined_extern_inline)
 341     edge->inline_failed = N_("redefined extern inline functions are not "
 342                              "considered for inlining");
 343   else if (callee->local.inlinable)
 344     edge->inline_failed = N_("function not considered for inlining");
 345   else
 346     edge->inline_failed = N_("function not inlinable");
 347
 348   edge->aux = NULL;
 349
 350   edge->caller = caller;
 351   edge->callee = callee;
 352   edge->call_stmt = call_stmt;
 353   edge->prev_caller = NULL;
 354   edge->next_caller = callee->callers;
 355   if (callee->callers)
 356     callee->callers->prev_caller = edge;
 357   edge->prev_callee = NULL;
 358   edge->next_callee = caller->callees;
 359   if (caller->callees)
 360     caller->callees->prev_callee = edge;
 361   caller->callees = edge;
 362   callee->callers = edge;
 363   edge->count = count;
 364   gcc_assert (count >= 0);
 365   edge->frequency = freq;
 366   gcc_assert (freq >= 0);
 367   gcc_assert (freq <= CGRAPH_FREQ_MAX);
 368   edge->loop_nest = nest;
 369   if (caller->call_site_hash)
 370     {
 371       void **slot;
 372       slot = htab_find_slot_with_hash (caller->call_site_hash,
 373                                        edge->call_stmt,
 374                                        htab_hash_pointer
 375                                          (edge->call_stmt),
 376                                        INSERT);
 377       gcc_assert (!*slot);
 378       *slot = edge;
 379     }
 380   return edge;
 381 }
 382
 383 /* Remove the edge E from the list of the callers of the callee.  */
 384
 385 static inline void
 386 cgraph_edge_remove_callee (struct cgraph_edge *e)
 387 {
 388   if (e->prev_caller)
 389     e->prev_caller->next_caller = e->next_caller;
 390   if (e->next_caller)
 391     e->next_caller->prev_caller = e->prev_caller;
 392   if (!e->prev_caller)
 393     e->callee->callers = e->next_caller;
 394 }
 395
 396 /* Remove the edge E from the list of the callees of the caller.  */
 397
 398 static inline void
 399 cgraph_edge_remove_caller (struct cgraph_edge *e)
 400 {
 401   if (e->prev_callee)
 402     e->prev_callee->next_callee = e->next_callee;
 403   if (e->next_callee)
 404     e->next_callee->prev_callee = e->prev_callee;
 405   if (!e->prev_callee)
 406     e->caller->callees = e->next_callee;
 407   if (e->caller->call_site_hash)
 408     htab_remove_elt_with_hash (e->caller->call_site_hash,
 409                                e->call_stmt,
 410                                htab_hash_pointer (e->call_stmt));
 411 }
 412
 413 /* Remove the edge E in the cgraph.  */
 414
 415 void
 416 cgraph_remove_edge (struct cgraph_edge *e)
 417 {
 418   /* Remove from callers list of the callee.  */
 419   cgraph_edge_remove_callee (e);
 420
 421   /* Remove from callees list of the callers.  */
 422   cgraph_edge_remove_caller (e);
 423 }
 424
 425 /* Redirect callee of E to N.  The function does not update underlying
 426    call expression.  */
 427
 428 void
 429 cgraph_redirect_edge_callee (struct cgraph_edge *e, struct cgraph_node *n)
 430 {
 431   /* Remove from callers list of the current callee.  */
 432   cgraph_edge_remove_callee (e);
 433
 434   /* Insert to callers list of the new callee.  */
 435   e->prev_caller = NULL;
 436   if (n->callers)
 437     n->callers->prev_caller = e;
 438   e->next_caller = n->callers;
 439   n->callers = e;
 440   e->callee = n;
 441 }
 442
 443 /* Remove all callees from the node.  */
 444
 445 void
 446 cgraph_node_remove_callees (struct cgraph_node *node)
 447 {
 448   struct cgraph_edge *e;
 449
 450   /* It is sufficient to remove the edges from the lists of callers of
 451      the callees.  The callee list of the node can be zapped with one
 452      assignment.  */
 453   for (e = node->callees; e; e = e->next_callee)
 454     cgraph_edge_remove_callee (e);
 455   node->callees = NULL;
 456   if (node->call_site_hash)
 457     {
 458       htab_delete (node->call_site_hash);
 459       node->call_site_hash = NULL;
 460     }
 461 }
 462
 463 /* Remove all callers from the node.  */
 464
 465 static void
 466 cgraph_node_remove_callers (struct cgraph_node *node)
 467 {
 468   struct cgraph_edge *e;
 469
 470   /* It is sufficient to remove the edges from the lists of callees of
 471      the callers.  The caller list of the node can be zapped with one
 472      assignment.  */
 473   for (e = node->callers; e; e = e->next_caller)
 474     cgraph_edge_remove_caller (e);
 475   node->callers = NULL;
 476 }
 477
 478 /* Release memory used to represent body of function NODE.  */
 479
 480 void
 481 cgraph_release_function_body (struct cgraph_node *node)
 482 {
 483   if (DECL_STRUCT_FUNCTION (node->decl)
 484       && DECL_STRUCT_FUNCTION (node->decl)->gimple_df)
 485     {
 486       tree old_decl = current_function_decl;
 487       push_cfun (DECL_STRUCT_FUNCTION (node->decl));
 488       current_function_decl = node->decl;
 489       delete_tree_ssa ();
 490       delete_tree_cfg_annotations ();
 491       cfun->eh = NULL;
 492       current_function_decl = old_decl;
 493       pop_cfun();
 494     }
 495   DECL_SAVED_TREE (node->decl) = NULL;
 496   DECL_STRUCT_FUNCTION (node->decl) = NULL;
 497   DECL_INITIAL (node->decl) = error_mark_node;
 498 }
 499
 500 /* Remove the node from cgraph.  */
 501
 502 void
 503 cgraph_remove_node (struct cgraph_node *node)
 504 {
 505   void **slot;
 506   bool kill_body = false;
 507
 508   cgraph_node_remove_callers (node);
 509   cgraph_node_remove_callees (node);
 510   /* Incremental inlining access removed nodes stored in the postorder list.
 511      */
 512   node->needed = node->reachable = false;
 513   while (node->nested)
 514     cgraph_remove_node (node->nested);
 515   if (node->origin)
 516     {
 517       struct cgraph_node **node2 = &node->origin->nested;
 518
 519       while (*node2 != node)
 520         node2 = &(*node2)->next_nested;
 521       *node2 = node->next_nested;
 522     }
 523   if (node->previous)
 524     node->previous->next = node->next;
 525   else
 526     cgraph_nodes = node->next;
 527   if (node->next)
 528     node->next->previous = node->previous;
 529   node->next = NULL;
 530   node->previous = NULL;
 531   slot = htab_find_slot (cgraph_hash, node, NO_INSERT);
 532   if (*slot == node)
 533     {
 534       if (node->next_clone)
 535       {
 536         struct cgraph_node *new_node = node->next_clone;
 537         struct cgraph_node *n;
 538
 539         /* Make the next clone be the master clone */
 540         for (n = new_node; n; n = n->next_clone)
 541           n->master_clone = new_node;
 542
 543         *slot = new_node;
 544         node->next_clone->prev_clone = NULL;
 545       }
 546       else
 547         {
 548           htab_clear_slot (cgraph_hash, slot);
 549           kill_body = true;
 550         }
 551     }
 552   else
 553     {
 554       node->prev_clone->next_clone = node->next_clone;
 555       if (node->next_clone)
 556         node->next_clone->prev_clone = node->prev_clone;
 557     }
 558
 559   /* While all the clones are removed after being proceeded, the function
 560      itself is kept in the cgraph even after it is compiled.  Check whether
 561      we are done with this body and reclaim it proactively if this is the case.
 562      */
 563   if (!kill_body && *slot)
 564     {
 565       struct cgraph_node *n = (struct cgraph_node *) *slot;
 566       if (!n->next_clone && !n->global.inlined_to
 567           && (cgraph_global_info_ready
 568               && (TREE_ASM_WRITTEN (n->decl) || DECL_EXTERNAL (n->decl))))
 569         kill_body = true;
 570     }
 571
 572   if (kill_body && flag_unit_at_a_time)
 573     cgraph_release_function_body (node);
 574   node->decl = NULL;
 575   if (node->call_site_hash)
 576     {
 577       htab_delete (node->call_site_hash);
 578       node->call_site_hash = NULL;
 579     }
 580   cgraph_n_nodes--;
 581   /* Do not free the structure itself so the walk over chain can continue.  */
 582 }
 583
 584 /* Notify finalize_compilation_unit that given node is reachable.  */
 585
 586 void
 587 cgraph_mark_reachable_node (struct cgraph_node *node)
 588 {
 589   if (!node->reachable && node->local.finalized)
 590     {
 591       notice_global_symbol (node->decl);
 592       node->reachable = 1;
 593       gcc_assert (!cgraph_global_info_ready);
 594
 595       node->next_needed = cgraph_nodes_queue;
 596       cgraph_nodes_queue = node;
 597     }
 598 }
 599
 600 /* Likewise indicate that a node is needed, i.e. reachable via some
 601    external means.  */
 602
 603 void
 604 cgraph_mark_needed_node (struct cgraph_node *node)
 605 {
 606   node->needed = 1;
 607   cgraph_mark_reachable_node (node);
 608 }
 609
 610 /* Return local info for the compiled function.  */
 611
 612 struct cgraph_local_info *
 613 cgraph_local_info (tree decl)
 614 {
 615   struct cgraph_node *node;
 616
 617   gcc_assert (TREE_CODE (decl) == FUNCTION_DECL);
 618   node = cgraph_node (decl);
 619   return &node->local;
 620 }
 621
 622 /* Return local info for the compiled function.  */
 623
 624 struct cgraph_global_info *
 625 cgraph_global_info (tree decl)
 626 {
 627   struct cgraph_node *node;
 628
 629   gcc_assert (TREE_CODE (decl) == FUNCTION_DECL && cgraph_global_info_ready);
 630   node = cgraph_node (decl);
 631   return &node->global;
 632 }
 633
 634 /* Return local info for the compiled function.  */
 635
 636 struct cgraph_rtl_info *
 637 cgraph_rtl_info (tree decl)
 638 {
 639   struct cgraph_node *node;
 640
 641   gcc_assert (TREE_CODE (decl) == FUNCTION_DECL);
 642   node = cgraph_node (decl);
 643   if (decl != current_function_decl
 644       && !TREE_ASM_WRITTEN (node->decl))
 645     return NULL;
 646   return &node->rtl;
 647 }
 648
 649 /* Return name of the node used in debug output.  */
 650 const char *
 651 cgraph_node_name (struct cgraph_node *node)
 652 {
 653   return lang_hooks.decl_printable_name (node->decl, 2);
 654 }
 655
 656 /* Names used to print out the availability enum.  */
 657 const char * const cgraph_availability_names[] =
 658   {"unset", "not_available", "overwrittable", "available", "local"};
 659
 660 /* Dump given cgraph node.  */
 661 void
 662 dump_cgraph_node (FILE *f, struct cgraph_node *node)
 663 {
 664   struct cgraph_edge *edge;
 665   fprintf (f, "%s/%i(%i):", cgraph_node_name (node), node->uid, node->pid);
 666   if (node->global.inlined_to)
 667     fprintf (f, " (inline copy in %s/%i)",
 668              cgraph_node_name (node->global.inlined_to),
 669              node->global.inlined_to->uid);
 670   if (cgraph_function_flags_ready)
 671     fprintf (f, " availability:%s",
 672              cgraph_availability_names [cgraph_function_body_availability (node)]);
 673   if (node->master_clone && node->master_clone->uid != node->uid)
 674     fprintf (f, "(%i)", node->master_clone->uid);
 675   if (node->count)
 676     fprintf (f, " executed "HOST_WIDEST_INT_PRINT_DEC"x",
 677              (HOST_WIDEST_INT)node->count);
 678   if (node->local.self_insns)
 679     fprintf (f, " %i insns", node->local.self_insns);
 680   if (node->global.insns && node->global.insns != node->local.self_insns)
 681     fprintf (f, " (%i after inlining)", node->global.insns);
 682   if (node->local.estimated_self_stack_size)
 683     fprintf (f, " %i bytes stack usage", (int)node->local.estimated_self_stack_size);
 684   if (node->global.estimated_stack_size != node->local.estimated_self_stack_size)
 685     fprintf (f, " %i bytes after inlining", (int)node->global.estimated_stack_size);
 686   if (node->origin)
 687     fprintf (f, " nested in: %s", cgraph_node_name (node->origin));
 688   if (node->needed)
 689     fprintf (f, " needed");
 690   else if (node->reachable)
 691     fprintf (f, " reachable");
 692   if (DECL_SAVED_TREE (node->decl))
 693     fprintf (f, " tree");
 694   if (node->output)
 695     fprintf (f, " output");
 696   if (node->local.local)
 697     fprintf (f, " local");
 698   if (node->local.externally_visible)
 699     fprintf (f, " externally_visible");
 700   if (node->local.finalized)
 701     fprintf (f, " finalized");
 702   if (node->local.disregard_inline_limits)
 703     fprintf (f, " always_inline");
 704   else if (node->local.inlinable)
 705     fprintf (f, " inlinable");
 706   if (node->local.redefined_extern_inline)
 707     fprintf (f, " redefined_extern_inline");
 708   if (TREE_ASM_WRITTEN (node->decl))
 709     fprintf (f, " asm_written");
 710
 711   fprintf (f, "\n  called by: ");
 712   for (edge = node->callers; edge; edge = edge->next_caller)
 713     {
 714       fprintf (f, "%s/%i ", cgraph_node_name (edge->caller),
 715                edge->caller->uid);
 716       if (edge->count)
 717         fprintf (f, "("HOST_WIDEST_INT_PRINT_DEC"x) ",
 718                  (HOST_WIDEST_INT)edge->count);
 719       if (edge->frequency)
 720         fprintf (f, "(%.2f per call) ",
 721                  edge->frequency / (double)CGRAPH_FREQ_BASE);
 722       if (!edge->inline_failed)
 723         fprintf(f, "(inlined) ");
 724     }
 725
 726   fprintf (f, "\n  calls: ");
 727   for (edge = node->callees; edge; edge = edge->next_callee)
 728     {
 729       fprintf (f, "%s/%i ", cgraph_node_name (edge->callee),
 730                edge->callee->uid);
 731       if (!edge->inline_failed)
 732         fprintf(f, "(inlined) ");
 733       if (edge->count)
 734         fprintf (f, "("HOST_WIDEST_INT_PRINT_DEC"x) ",
 735                  (HOST_WIDEST_INT)edge->count);
 736       if (edge->frequency)
 737         fprintf (f, "(%.2f per call) ",
 738                  edge->frequency / (double)CGRAPH_FREQ_BASE);
 739       if (edge->loop_nest)
 740         fprintf (f, "(nested in %i loops) ", edge->loop_nest);
 741     }
 742   fprintf (f, "\n");
 743 }
 744
 745 /* Dump the callgraph.  */
 746
 747 void
 748 dump_cgraph (FILE *f)
 749 {
 750   struct cgraph_node *node;
 751
 752   fprintf (f, "callgraph:\n\n");
 753   for (node = cgraph_nodes; node; node = node->next)
 754     dump_cgraph_node (f, node);
 755 }
 756
 757 /* Set the DECL_ASSEMBLER_NAME and update cgraph hashtables.  */
 758 void
 759 change_decl_assembler_name (tree decl, tree name)
 760 {
 761   if (!DECL_ASSEMBLER_NAME_SET_P (decl))
 762     {
 763       SET_DECL_ASSEMBLER_NAME (decl, name);
 764       return;
 765     }
 766   if (name == DECL_ASSEMBLER_NAME (decl))
 767     return;
 768
 769   if (TREE_SYMBOL_REFERENCED (DECL_ASSEMBLER_NAME (decl))
 770       && DECL_RTL_SET_P (decl))
 771     warning (0, "%D renamed after being referenced in assembly", decl);
 772
 773   SET_DECL_ASSEMBLER_NAME (decl, name);
 774 }
 775
 776 /* Add a top-level asm statement to the list.  */
 777
 778 struct cgraph_asm_node *
 779 cgraph_add_asm_node (tree asm_str)
 780 {
 781   struct cgraph_asm_node *node;
 782
 783   node = GGC_CNEW (struct cgraph_asm_node);
 784   node->asm_str = asm_str;
 785   node->order = cgraph_order++;
 786   node->next = NULL;
 787   if (cgraph_asm_nodes == NULL)
 788     cgraph_asm_nodes = node;
 789   else
 790     cgraph_asm_last_node->next = node;
 791   cgraph_asm_last_node = node;
 792   return node;
 793 }
 794
 795 /* Return true when the DECL can possibly be inlined.  */
 796 bool
 797 cgraph_function_possibly_inlined_p (tree decl)
 798 {
 799   if (!cgraph_global_info_ready)
 800     return (DECL_INLINE (decl) && !flag_really_no_inline);
 801   return DECL_POSSIBLY_INLINED (decl);
 802 }
 803
 804 /* Create clone of E in the node N represented by CALL_EXPR the callgraph.  */
 805 struct cgraph_edge *
 806 cgraph_clone_edge (struct cgraph_edge *e, struct cgraph_node *n,
 807                    tree call_stmt, gcov_type count_scale, int freq_scale,
 808                    int loop_nest, bool update_original)
 809 {
 810   struct cgraph_edge *new;
 811   gcov_type count = e->count * count_scale / REG_BR_PROB_BASE;
 812   gcov_type freq = e->frequency * (gcov_type) freq_scale / CGRAPH_FREQ_BASE;
 813
 814   if (freq > CGRAPH_FREQ_MAX)
 815     freq = CGRAPH_FREQ_MAX;
 816   new = cgraph_create_edge (n, e->callee, call_stmt, count, freq,
 817                             e->loop_nest + loop_nest);
 818
 819   new->inline_failed = e->inline_failed;
 820   if (update_original)
 821     {
 822       e->count -= new->count;
 823       if (e->count < 0)
 824         e->count = 0;
 825     }
 826   return new;
 827 }
 828
 829 /* Create node representing clone of N executed COUNT times.  Decrease
 830    the execution counts from original node too.
 831
 832    When UPDATE_ORIGINAL is true, the counts are subtracted from the original
 833    function's profile to reflect the fact that part of execution is handled
 834    by node.  */
 835 struct cgraph_node *
 836 cgraph_clone_node (struct cgraph_node *n, gcov_type count, int freq, int loop_nest,
 837                    bool update_original)
 838 {
 839   struct cgraph_node *new = cgraph_create_node ();
 840   struct cgraph_edge *e;
 841   gcov_type count_scale;
 842
 843   new->decl = n->decl;
 844   new->origin = n->origin;
 845   if (new->origin)
 846     {
 847       new->next_nested = new->origin->nested;
 848       new->origin->nested = new;
 849     }
 850   new->analyzed = n->analyzed;
 851   new->local = n->local;
 852   new->global = n->global;
 853   new->rtl = n->rtl;
 854   new->master_clone = n->master_clone;
 855   new->count = count;
 856   if (n->count)
 857     count_scale = new->count * REG_BR_PROB_BASE / n->count;
 858   else
 859     count_scale = 0;
 860   if (update_original)
 861     {
 862       n->count -= count;
 863       if (n->count < 0)
 864         n->count = 0;
 865     }
 866
 867   for (e = n->callees;e; e=e->next_callee)
 868     cgraph_clone_edge (e, new, e->call_stmt, count_scale, freq, loop_nest,
 869                        update_original);
 870
 871   new->next_clone = n->next_clone;
 872   new->prev_clone = n;
 873   n->next_clone = new;
 874   if (new->next_clone)
 875     new->next_clone->prev_clone = new;
 876
 877   return new;
 878 }
 879
 880 /* Return true if N is an master_clone, (see cgraph_master_clone).  */
 881
 882 bool
 883 cgraph_is_master_clone (struct cgraph_node *n)
 884 {
 885   return (n == cgraph_master_clone (n));
 886 }
 887
 888 struct cgraph_node *
 889 cgraph_master_clone (struct cgraph_node *n)
 890 {
 891   enum availability avail = cgraph_function_body_availability (n);
 892
 893   if (avail == AVAIL_NOT_AVAILABLE || avail == AVAIL_OVERWRITABLE)
 894     return NULL;
 895
 896   if (!n->master_clone)
 897     n->master_clone = cgraph_node (n->decl);
 898
 899   return n->master_clone;
 900 }
 901
 902 /* NODE is no longer nested function; update cgraph accordingly.  */
 903 void
 904 cgraph_unnest_node (struct cgraph_node *node)
 905 {
 906   struct cgraph_node **node2 = &node->origin->nested;
 907   gcc_assert (node->origin);
 908
 909   while (*node2 != node)
 910     node2 = &(*node2)->next_nested;
 911   *node2 = node->next_nested;
 912   node->origin = NULL;
 913 }
 914
 915 /* Return function availability.  See cgraph.h for description of individual
 916    return values.  */
 917 enum availability
 918 cgraph_function_body_availability (struct cgraph_node *node)
 919 {
 920   enum availability avail;
 921   gcc_assert (cgraph_function_flags_ready);
 922   if (!node->analyzed)
 923     avail = AVAIL_NOT_AVAILABLE;
 924   else if (node->local.local)
 925     avail = AVAIL_LOCAL;
 926   else if (node->local.externally_visible)
 927     avail = AVAIL_AVAILABLE;
 928
 929   /* If the function can be overwritten, return OVERWRITABLE.  Take
 930      care at least of two notable extensions - the COMDAT functions
 931      used to share template instantiations in C++ (this is symmetric
 932      to code cp_cannot_inline_tree_fn and probably shall be shared and
 933      the inlinability hooks completely eliminated).
 934
 935      ??? Does the C++ one definition rule allow us to always return
 936      AVAIL_AVAILABLE here?  That would be good reason to preserve this
 937      hook Similarly deal with extern inline functions - this is again
 938      necessary to get C++ shared functions having keyed templates
 939      right and in the C extension documentation we probably should
 940      document the requirement of both versions of function (extern
 941      inline and offline) having same side effect characteristics as
 942      good optimization is what this optimization is about.  */
 943
 944   else if (!(*targetm.binds_local_p) (node->decl)
 945            && !DECL_COMDAT (node->decl) && !DECL_EXTERNAL (node->decl))
 946     avail = AVAIL_OVERWRITABLE;
 947   else avail = AVAIL_AVAILABLE;
 948
 949   return avail;
 950 }
 951
 952 /* Add the function FNDECL to the call graph.
 953    Unlike cgraph_finalize_function, this function is intended to be used
 954    by middle end and allows insertion of new function at arbitrary point
 955    of compilation.  The function can be either in high, low or SSA form
 956    GIMPLE.
 957
 958    The function is assumed to be reachable and have address taken (so no
 959    API breaking optimizations are performed on it).
 960
 961    Main work done by this function is to enqueue the function for later
 962    processing to avoid need the passes to be re-entrant.  */
 963
 964 void
 965 cgraph_add_new_function (tree fndecl, bool lowered)
 966 {
 967   struct cgraph_node *node;
 968   switch (cgraph_state)
 969     {
 970       case CGRAPH_STATE_CONSTRUCTION:
 971         /* Just enqueue function to be processed at nearest occurence.  */
 972         node = cgraph_node (fndecl);
 973         node->next_needed = cgraph_new_nodes;
 974         if (lowered)
 975           node->lowered = true;
 976         cgraph_new_nodes = node;
 977         break;
 978
 979       case CGRAPH_STATE_IPA:
 980       case CGRAPH_STATE_IPA_SSA:
 981       case CGRAPH_STATE_EXPANSION:
 982         /* Bring the function into finalized state and enqueue for later
 983            analyzing and compilation.  */
 984         node = cgraph_node (fndecl);
 985         node->local.local = false;
 986         node->local.finalized = true;
 987         node->reachable = node->needed = true;
 988         if (lowered)
 989           node->lowered = true;
 990         node->next_needed = cgraph_new_nodes;
 991         cgraph_new_nodes = node;
 992         break;
 993
 994       case CGRAPH_STATE_FINISHED:
 995         /* At the very end of compilation we have to do all the work up
 996            to expansion.  */
 997         push_cfun (DECL_STRUCT_FUNCTION (fndecl));
 998         current_function_decl = fndecl;
 999         tree_register_cfg_hooks ();
1000         if (!lowered)
1001           tree_lowering_passes (fndecl);
1002         bitmap_obstack_initialize (NULL);
1003         if (!gimple_in_ssa_p (DECL_STRUCT_FUNCTION (fndecl)) && optimize)
1004           execute_pass_list (pass_early_local_passes.sub);
1005         bitmap_obstack_release (NULL);
1006         tree_rest_of_compilation (fndecl);
1007         pop_cfun ();
1008         current_function_decl = NULL;
1009         break;
1010     }
1011 }
1012
1013 #include "gt-cgraph.h"