gcc/cgraph.c

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