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 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 (((const 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 ((const 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_stmt 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 /* Update or remove corresponding cgraph edge if a call OLD_CALL
 445    in OLD_STMT changed into NEW_STMT.  */
 446
 447 void
 448 cgraph_update_edges_for_call_stmt (tree old_stmt, tree old_call,
 449                                    tree new_stmt)
 450 {
 451   tree new_call = get_call_expr_in (new_stmt);
 452   struct cgraph_node *node = cgraph_node (cfun->decl);
 453
 454   if (old_call != new_call)
 455     {
 456       struct cgraph_edge *e = cgraph_edge (node, old_stmt);
 457       struct cgraph_edge *ne = NULL;
 458       tree new_decl;
 459
 460       if (e)
 461         {
 462           gcov_type count = e->count;
 463           int frequency = e->frequency;
 464           int loop_nest = e->loop_nest;
 465
 466           cgraph_remove_edge (e);
 467           if (new_call)
 468             {
 469               new_decl = get_callee_fndecl (new_call);
 470               if (new_decl)
 471                 {
 472                   ne = cgraph_create_edge (node, cgraph_node (new_decl),
 473                                            new_stmt, count, frequency,
 474                                            loop_nest);
 475                   gcc_assert (ne->inline_failed);
 476                 }
 477             }
 478         }
 479     }
 480   else if (old_stmt != new_stmt)
 481     {
 482       struct cgraph_edge *e = cgraph_edge (node, old_stmt);
 483
 484       if (e)
 485         cgraph_set_call_stmt (e, new_stmt);
 486     }
 487 }
 488
 489 /* Remove all callees from the node.  */
 490
 491 void
 492 cgraph_node_remove_callees (struct cgraph_node *node)
 493 {
 494   struct cgraph_edge *e;
 495
 496   /* It is sufficient to remove the edges from the lists of callers of
 497      the callees.  The callee list of the node can be zapped with one
 498      assignment.  */
 499   for (e = node->callees; e; e = e->next_callee)
 500     cgraph_edge_remove_callee (e);
 501   node->callees = NULL;
 502   if (node->call_site_hash)
 503     {
 504       htab_delete (node->call_site_hash);
 505       node->call_site_hash = NULL;
 506     }
 507 }
 508
 509 /* Remove all callers from the node.  */
 510
 511 static void
 512 cgraph_node_remove_callers (struct cgraph_node *node)
 513 {
 514   struct cgraph_edge *e;
 515
 516   /* It is sufficient to remove the edges from the lists of callees of
 517      the callers.  The caller list of the node can be zapped with one
 518      assignment.  */
 519   for (e = node->callers; e; e = e->next_caller)
 520     cgraph_edge_remove_caller (e);
 521   node->callers = NULL;
 522 }
 523
 524 /* Release memory used to represent body of function NODE.  */
 525
 526 void
 527 cgraph_release_function_body (struct cgraph_node *node)
 528 {
 529   if (DECL_STRUCT_FUNCTION (node->decl)
 530       && DECL_STRUCT_FUNCTION (node->decl)->gimple_df)
 531     {
 532       tree old_decl = current_function_decl;
 533       push_cfun (DECL_STRUCT_FUNCTION (node->decl));
 534       current_function_decl = node->decl;
 535       delete_tree_ssa ();
 536       delete_tree_cfg_annotations ();
 537       cfun->eh = NULL;
 538       current_function_decl = old_decl;
 539       pop_cfun();
 540     }
 541   DECL_SAVED_TREE (node->decl) = NULL;
 542   DECL_STRUCT_FUNCTION (node->decl) = NULL;
 543   DECL_INITIAL (node->decl) = error_mark_node;
 544 }
 545
 546 /* Remove the node from cgraph.  */
 547
 548 void
 549 cgraph_remove_node (struct cgraph_node *node)
 550 {
 551   void **slot;
 552   bool kill_body = false;
 553
 554   cgraph_node_remove_callers (node);
 555   cgraph_node_remove_callees (node);
 556   /* Incremental inlining access removed nodes stored in the postorder list.
 557      */
 558   node->needed = node->reachable = false;
 559   while (node->nested)
 560     cgraph_remove_node (node->nested);
 561   if (node->origin)
 562     {
 563       struct cgraph_node **node2 = &node->origin->nested;
 564
 565       while (*node2 != node)
 566         node2 = &(*node2)->next_nested;
 567       *node2 = node->next_nested;
 568     }
 569   if (node->previous)
 570     node->previous->next = node->next;
 571   else
 572     cgraph_nodes = node->next;
 573   if (node->next)
 574     node->next->previous = node->previous;
 575   node->next = NULL;
 576   node->previous = NULL;
 577   slot = htab_find_slot (cgraph_hash, node, NO_INSERT);
 578   if (*slot == node)
 579     {
 580       if (node->next_clone)
 581       {
 582         struct cgraph_node *new_node = node->next_clone;
 583         struct cgraph_node *n;
 584
 585         /* Make the next clone be the master clone */
 586         for (n = new_node; n; n = n->next_clone)
 587           n->master_clone = new_node;
 588
 589         *slot = new_node;
 590         node->next_clone->prev_clone = NULL;
 591       }
 592       else
 593         {
 594           htab_clear_slot (cgraph_hash, slot);
 595           kill_body = true;
 596         }
 597     }
 598   else
 599     {
 600       node->prev_clone->next_clone = node->next_clone;
 601       if (node->next_clone)
 602         node->next_clone->prev_clone = node->prev_clone;
 603     }
 604
 605   /* While all the clones are removed after being proceeded, the function
 606      itself is kept in the cgraph even after it is compiled.  Check whether
 607      we are done with this body and reclaim it proactively if this is the case.
 608      */
 609   if (!kill_body && *slot)
 610     {
 611       struct cgraph_node *n = (struct cgraph_node *) *slot;
 612       if (!n->next_clone && !n->global.inlined_to
 613           && (cgraph_global_info_ready
 614               && (TREE_ASM_WRITTEN (n->decl) || DECL_EXTERNAL (n->decl))))
 615         kill_body = true;
 616     }
 617
 618   if (kill_body && flag_unit_at_a_time)
 619     cgraph_release_function_body (node);
 620   node->decl = NULL;
 621   if (node->call_site_hash)
 622     {
 623       htab_delete (node->call_site_hash);
 624       node->call_site_hash = NULL;
 625     }
 626   cgraph_n_nodes--;
 627   /* Do not free the structure itself so the walk over chain can continue.  */
 628 }
 629
 630 /* Notify finalize_compilation_unit that given node is reachable.  */
 631
 632 void
 633 cgraph_mark_reachable_node (struct cgraph_node *node)
 634 {
 635   if (!node->reachable && node->local.finalized)
 636     {
 637       notice_global_symbol (node->decl);
 638       node->reachable = 1;
 639       gcc_assert (!cgraph_global_info_ready);
 640
 641       node->next_needed = cgraph_nodes_queue;
 642       cgraph_nodes_queue = node;
 643     }
 644 }
 645
 646 /* Likewise indicate that a node is needed, i.e. reachable via some
 647    external means.  */
 648
 649 void
 650 cgraph_mark_needed_node (struct cgraph_node *node)
 651 {
 652   node->needed = 1;
 653   cgraph_mark_reachable_node (node);
 654 }
 655
 656 /* Return local info for the compiled function.  */
 657
 658 struct cgraph_local_info *
 659 cgraph_local_info (tree decl)
 660 {
 661   struct cgraph_node *node;
 662
 663   gcc_assert (TREE_CODE (decl) == FUNCTION_DECL);
 664   node = cgraph_node (decl);
 665   return &node->local;
 666 }
 667
 668 /* Return local info for the compiled function.  */
 669
 670 struct cgraph_global_info *
 671 cgraph_global_info (tree decl)
 672 {
 673   struct cgraph_node *node;
 674
 675   gcc_assert (TREE_CODE (decl) == FUNCTION_DECL && cgraph_global_info_ready);
 676   node = cgraph_node (decl);
 677   return &node->global;
 678 }
 679
 680 /* Return local info for the compiled function.  */
 681
 682 struct cgraph_rtl_info *
 683 cgraph_rtl_info (tree decl)
 684 {
 685   struct cgraph_node *node;
 686
 687   gcc_assert (TREE_CODE (decl) == FUNCTION_DECL);
 688   node = cgraph_node (decl);
 689   if (decl != current_function_decl
 690       && !TREE_ASM_WRITTEN (node->decl))
 691     return NULL;
 692   return &node->rtl;
 693 }
 694
 695 /* Return name of the node used in debug output.  */
 696 const char *
 697 cgraph_node_name (struct cgraph_node *node)
 698 {
 699   return lang_hooks.decl_printable_name (node->decl, 2);
 700 }
 701
 702 /* Names used to print out the availability enum.  */
 703 const char * const cgraph_availability_names[] =
 704   {"unset", "not_available", "overwritable", "available", "local"};
 705
 706
 707 /* Dump call graph node NODE to file F.  */
 708
 709 void
 710 dump_cgraph_node (FILE *f, struct cgraph_node *node)
 711 {
 712   struct cgraph_edge *edge;
 713   fprintf (f, "%s/%i(%i):", cgraph_node_name (node), node->uid, node->pid);
 714   if (node->global.inlined_to)
 715     fprintf (f, " (inline copy in %s/%i)",
 716              cgraph_node_name (node->global.inlined_to),
 717              node->global.inlined_to->uid);
 718   if (cgraph_function_flags_ready)
 719     fprintf (f, " availability:%s",
 720              cgraph_availability_names [cgraph_function_body_availability (node)]);
 721   if (node->master_clone && node->master_clone->uid != node->uid)
 722     fprintf (f, "(%i)", node->master_clone->uid);
 723   if (node->count)
 724     fprintf (f, " executed "HOST_WIDEST_INT_PRINT_DEC"x",
 725              (HOST_WIDEST_INT)node->count);
 726   if (node->local.inline_summary.self_insns)
 727     fprintf (f, " %i insns", node->local.inline_summary.self_insns);
 728   if (node->global.insns && node->global.insns
 729       != node->local.inline_summary.self_insns)
 730     fprintf (f, " (%i after inlining)", node->global.insns);
 731   if (node->local.inline_summary.estimated_self_stack_size)
 732     fprintf (f, " %i bytes stack usage", (int)node->local.inline_summary.estimated_self_stack_size);
 733   if (node->global.estimated_stack_size != node->local.inline_summary.estimated_self_stack_size)
 734     fprintf (f, " %i bytes after inlining", (int)node->global.estimated_stack_size);
 735   if (node->origin)
 736     fprintf (f, " nested in: %s", cgraph_node_name (node->origin));
 737   if (node->needed)
 738     fprintf (f, " needed");
 739   else if (node->reachable)
 740     fprintf (f, " reachable");
 741   if (DECL_SAVED_TREE (node->decl))
 742     fprintf (f, " tree");
 743   if (node->output)
 744     fprintf (f, " output");
 745   if (node->local.local)
 746     fprintf (f, " local");
 747   if (node->local.externally_visible)
 748     fprintf (f, " externally_visible");
 749   if (node->local.finalized)
 750     fprintf (f, " finalized");
 751   if (node->local.disregard_inline_limits)
 752     fprintf (f, " always_inline");
 753   else if (node->local.inlinable)
 754     fprintf (f, " inlinable");
 755   if (node->local.redefined_extern_inline)
 756     fprintf (f, " redefined_extern_inline");
 757   if (TREE_ASM_WRITTEN (node->decl))
 758     fprintf (f, " asm_written");
 759
 760   fprintf (f, "\n  called by: ");
 761   for (edge = node->callers; edge; edge = edge->next_caller)
 762     {
 763       fprintf (f, "%s/%i ", cgraph_node_name (edge->caller),
 764                edge->caller->uid);
 765       if (edge->count)
 766         fprintf (f, "("HOST_WIDEST_INT_PRINT_DEC"x) ",
 767                  (HOST_WIDEST_INT)edge->count);
 768       if (edge->frequency)
 769         fprintf (f, "(%.2f per call) ",
 770                  edge->frequency / (double)CGRAPH_FREQ_BASE);
 771       if (!edge->inline_failed)
 772         fprintf(f, "(inlined) ");
 773     }
 774
 775   fprintf (f, "\n  calls: ");
 776   for (edge = node->callees; edge; edge = edge->next_callee)
 777     {
 778       fprintf (f, "%s/%i ", cgraph_node_name (edge->callee),
 779                edge->callee->uid);
 780       if (!edge->inline_failed)
 781         fprintf(f, "(inlined) ");
 782       if (edge->count)
 783         fprintf (f, "("HOST_WIDEST_INT_PRINT_DEC"x) ",
 784                  (HOST_WIDEST_INT)edge->count);
 785       if (edge->frequency)
 786         fprintf (f, "(%.2f per call) ",
 787                  edge->frequency / (double)CGRAPH_FREQ_BASE);
 788       if (edge->loop_nest)
 789         fprintf (f, "(nested in %i loops) ", edge->loop_nest);
 790     }
 791   fprintf (f, "\n");
 792 }
 793
 794
 795 /* Dump call graph node NODE to stderr.  */
 796
 797 void
 798 debug_cgraph_node (struct cgraph_node *node)
 799 {
 800   dump_cgraph_node (stderr, node);
 801 }
 802
 803
 804 /* Dump the callgraph to file F.  */
 805
 806 void
 807 dump_cgraph (FILE *f)
 808 {
 809   struct cgraph_node *node;
 810
 811   fprintf (f, "callgraph:\n\n");
 812   for (node = cgraph_nodes; node; node = node->next)
 813     dump_cgraph_node (f, node);
 814 }
 815
 816
 817 /* Dump the call graph to stderr.  */
 818
 819 void
 820 debug_cgraph (void)
 821 {
 822   dump_cgraph (stderr);
 823 }
 824
 825
 826 /* Set the DECL_ASSEMBLER_NAME and update cgraph hashtables.  */
 827
 828 void
 829 change_decl_assembler_name (tree decl, tree name)
 830 {
 831   if (!DECL_ASSEMBLER_NAME_SET_P (decl))
 832     {
 833       SET_DECL_ASSEMBLER_NAME (decl, name);
 834       return;
 835     }
 836   if (name == DECL_ASSEMBLER_NAME (decl))
 837     return;
 838
 839   if (TREE_SYMBOL_REFERENCED (DECL_ASSEMBLER_NAME (decl))
 840       && DECL_RTL_SET_P (decl))
 841     warning (0, "%D renamed after being referenced in assembly", decl);
 842
 843   SET_DECL_ASSEMBLER_NAME (decl, name);
 844 }
 845
 846 /* Add a top-level asm statement to the list.  */
 847
 848 struct cgraph_asm_node *
 849 cgraph_add_asm_node (tree asm_str)
 850 {
 851   struct cgraph_asm_node *node;
 852
 853   node = GGC_CNEW (struct cgraph_asm_node);
 854   node->asm_str = asm_str;
 855   node->order = cgraph_order++;
 856   node->next = NULL;
 857   if (cgraph_asm_nodes == NULL)
 858     cgraph_asm_nodes = node;
 859   else
 860     cgraph_asm_last_node->next = node;
 861   cgraph_asm_last_node = node;
 862   return node;
 863 }
 864
 865 /* Return true when the DECL can possibly be inlined.  */
 866 bool
 867 cgraph_function_possibly_inlined_p (tree decl)
 868 {
 869   if (!cgraph_global_info_ready)
 870     return (DECL_INLINE (decl) && !flag_really_no_inline);
 871   return DECL_POSSIBLY_INLINED (decl);
 872 }
 873
 874 /* Create clone of E in the node N represented by CALL_EXPR the callgraph.  */
 875 struct cgraph_edge *
 876 cgraph_clone_edge (struct cgraph_edge *e, struct cgraph_node *n,
 877                    tree call_stmt, gcov_type count_scale, int freq_scale,
 878                    int loop_nest, bool update_original)
 879 {
 880   struct cgraph_edge *new;
 881   gcov_type count = e->count * count_scale / REG_BR_PROB_BASE;
 882   gcov_type freq = e->frequency * (gcov_type) freq_scale / CGRAPH_FREQ_BASE;
 883
 884   if (freq > CGRAPH_FREQ_MAX)
 885     freq = CGRAPH_FREQ_MAX;
 886   new = cgraph_create_edge (n, e->callee, call_stmt, count, freq,
 887                             e->loop_nest + loop_nest);
 888
 889   new->inline_failed = e->inline_failed;
 890   if (update_original)
 891     {
 892       e->count -= new->count;
 893       if (e->count < 0)
 894         e->count = 0;
 895     }
 896   return new;
 897 }
 898
 899 /* Create node representing clone of N executed COUNT times.  Decrease
 900    the execution counts from original node too.
 901
 902    When UPDATE_ORIGINAL is true, the counts are subtracted from the original
 903    function's profile to reflect the fact that part of execution is handled
 904    by node.  */
 905 struct cgraph_node *
 906 cgraph_clone_node (struct cgraph_node *n, gcov_type count, int freq, int loop_nest,
 907                    bool update_original)
 908 {
 909   struct cgraph_node *new = cgraph_create_node ();
 910   struct cgraph_edge *e;
 911   gcov_type count_scale;
 912
 913   new->decl = n->decl;
 914   new->origin = n->origin;
 915   if (new->origin)
 916     {
 917       new->next_nested = new->origin->nested;
 918       new->origin->nested = new;
 919     }
 920   new->analyzed = n->analyzed;
 921   new->local = n->local;
 922   new->global = n->global;
 923   new->rtl = n->rtl;
 924   new->master_clone = n->master_clone;
 925   new->count = count;
 926   if (n->count)
 927     count_scale = new->count * REG_BR_PROB_BASE / n->count;
 928   else
 929     count_scale = 0;
 930   if (update_original)
 931     {
 932       n->count -= count;
 933       if (n->count < 0)
 934         n->count = 0;
 935     }
 936
 937   for (e = n->callees;e; e=e->next_callee)
 938     cgraph_clone_edge (e, new, e->call_stmt, count_scale, freq, loop_nest,
 939                        update_original);
 940
 941   new->next_clone = n->next_clone;
 942   new->prev_clone = n;
 943   n->next_clone = new;
 944   if (new->next_clone)
 945     new->next_clone->prev_clone = new;
 946
 947   return new;
 948 }
 949
 950 /* Return true if N is an master_clone, (see cgraph_master_clone).  */
 951
 952 bool
 953 cgraph_is_master_clone (struct cgraph_node *n)
 954 {
 955   return (n == cgraph_master_clone (n));
 956 }
 957
 958 struct cgraph_node *
 959 cgraph_master_clone (struct cgraph_node *n)
 960 {
 961   enum availability avail = cgraph_function_body_availability (n);
 962
 963   if (avail == AVAIL_NOT_AVAILABLE || avail == AVAIL_OVERWRITABLE)
 964     return NULL;
 965
 966   if (!n->master_clone)
 967     n->master_clone = cgraph_node (n->decl);
 968
 969   return n->master_clone;
 970 }
 971
 972 /* NODE is no longer nested function; update cgraph accordingly.  */
 973 void
 974 cgraph_unnest_node (struct cgraph_node *node)
 975 {
 976   struct cgraph_node **node2 = &node->origin->nested;
 977   gcc_assert (node->origin);
 978
 979   while (*node2 != node)
 980     node2 = &(*node2)->next_nested;
 981   *node2 = node->next_nested;
 982   node->origin = NULL;
 983 }
 984
 985 /* Return function availability.  See cgraph.h for description of individual
 986    return values.  */
 987 enum availability
 988 cgraph_function_body_availability (struct cgraph_node *node)
 989 {
 990   enum availability avail;
 991   gcc_assert (cgraph_function_flags_ready);
 992   if (!node->analyzed)
 993     avail = AVAIL_NOT_AVAILABLE;
 994   else if (node->local.local)
 995     avail = AVAIL_LOCAL;
 996   else if (node->local.externally_visible)
 997     avail = AVAIL_AVAILABLE;
 998
 999   /* If the function can be overwritten, return OVERWRITABLE.  Take
1000      care at least of two notable extensions - the COMDAT functions
1001      used to share template instantiations in C++ (this is symmetric
1002      to code cp_cannot_inline_tree_fn and probably shall be shared and
1003      the inlinability hooks completely eliminated).
1004
1005      ??? Does the C++ one definition rule allow us to always return
1006      AVAIL_AVAILABLE here?  That would be good reason to preserve this
1007      hook Similarly deal with extern inline functions - this is again
1008      necessary to get C++ shared functions having keyed templates
1009      right and in the C extension documentation we probably should
1010      document the requirement of both versions of function (extern
1011      inline and offline) having same side effect characteristics as
1012      good optimization is what this optimization is about.  */
1013
1014   else if (!(*targetm.binds_local_p) (node->decl)
1015            && !DECL_COMDAT (node->decl) && !DECL_EXTERNAL (node->decl))
1016     avail = AVAIL_OVERWRITABLE;
1017   else avail = AVAIL_AVAILABLE;
1018
1019   return avail;
1020 }
1021
1022 /* Add the function FNDECL to the call graph.
1023    Unlike cgraph_finalize_function, this function is intended to be used
1024    by middle end and allows insertion of new function at arbitrary point
1025    of compilation.  The function can be either in high, low or SSA form
1026    GIMPLE.
1027
1028    The function is assumed to be reachable and have address taken (so no
1029    API breaking optimizations are performed on it).
1030
1031    Main work done by this function is to enqueue the function for later
1032    processing to avoid need the passes to be re-entrant.  */
1033
1034 void
1035 cgraph_add_new_function (tree fndecl, bool lowered)
1036 {
1037   struct cgraph_node *node;
1038   switch (cgraph_state)
1039     {
1040       case CGRAPH_STATE_CONSTRUCTION:
1041         /* Just enqueue function to be processed at nearest occurrence.  */
1042         node = cgraph_node (fndecl);
1043         node->next_needed = cgraph_new_nodes;
1044         if (lowered)
1045           node->lowered = true;
1046         cgraph_new_nodes = node;
1047         break;
1048
1049       case CGRAPH_STATE_IPA:
1050       case CGRAPH_STATE_IPA_SSA:
1051       case CGRAPH_STATE_EXPANSION:
1052         /* Bring the function into finalized state and enqueue for later
1053            analyzing and compilation.  */
1054         node = cgraph_node (fndecl);
1055         node->local.local = false;
1056         node->local.finalized = true;
1057         node->reachable = node->needed = true;
1058         if (lowered)
1059           node->lowered = true;
1060         node->next_needed = cgraph_new_nodes;
1061         cgraph_new_nodes = node;
1062         break;
1063
1064       case CGRAPH_STATE_FINISHED:
1065         /* At the very end of compilation we have to do all the work up
1066            to expansion.  */
1067         push_cfun (DECL_STRUCT_FUNCTION (fndecl));
1068         current_function_decl = fndecl;
1069         tree_register_cfg_hooks ();
1070         if (!lowered)
1071           tree_lowering_passes (fndecl);
1072         bitmap_obstack_initialize (NULL);
1073         if (!gimple_in_ssa_p (DECL_STRUCT_FUNCTION (fndecl)) && optimize)
1074           execute_pass_list (pass_early_local_passes.pass.sub);
1075         bitmap_obstack_release (NULL);
1076         tree_rest_of_compilation (fndecl);
1077         pop_cfun ();
1078         current_function_decl = NULL;
1079         break;
1080     }
1081 }
1082
1083 #include "gt-cgraph.h"