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_smtt of edge E to NEW_STMT.  */
 300
 301 void
 302 cgraph_set_call_stmt (struct cgraph_edge *e, tree new_stmt)
 303 {
 304   if (e->caller->call_site_hash)
 305     {
 306       htab_remove_elt_with_hash (e->caller->call_site_hash,
 307                                  e->call_stmt,
 308                                  htab_hash_pointer (e->call_stmt));
 309     }
 310   e->call_stmt = new_stmt;
 311   if (e->caller->call_site_hash)
 312     {
 313       void **slot;
 314       slot = htab_find_slot_with_hash (e->caller->call_site_hash,
 315                                        e->call_stmt,
 316                                        htab_hash_pointer
 317                                        (e->call_stmt), INSERT);
 318       gcc_assert (!*slot);
 319       *slot = e;
 320     }
 321 }
 322
 323 /* Create edge from CALLER to CALLEE in the cgraph.  */
 324
 325 struct cgraph_edge *
 326 cgraph_create_edge (struct cgraph_node *caller, struct cgraph_node *callee,
 327                     tree call_stmt, gcov_type count, int freq, int nest)
 328 {
 329   struct cgraph_edge *edge = GGC_NEW (struct cgraph_edge);
 330 #ifdef ENABLE_CHECKING
 331   struct cgraph_edge *e;
 332
 333   for (e = caller->callees; e; e = e->next_callee)
 334     gcc_assert (e->call_stmt != call_stmt);
 335 #endif
 336
 337   gcc_assert (get_call_expr_in (call_stmt));
 338
 339   if (!DECL_SAVED_TREE (callee->decl))
 340     edge->inline_failed = N_("function body not available");
 341   else if (callee->local.redefined_extern_inline)
 342     edge->inline_failed = N_("redefined extern inline functions are not "
 343                              "considered for inlining");
 344   else if (callee->local.inlinable)
 345     edge->inline_failed = N_("function not considered for inlining");
 346   else
 347     edge->inline_failed = N_("function not inlinable");
 348
 349   edge->aux = NULL;
 350
 351   edge->caller = caller;
 352   edge->callee = callee;
 353   edge->call_stmt = call_stmt;
 354   edge->prev_caller = NULL;
 355   edge->next_caller = callee->callers;
 356   if (callee->callers)
 357     callee->callers->prev_caller = edge;
 358   edge->prev_callee = NULL;
 359   edge->next_callee = caller->callees;
 360   if (caller->callees)
 361     caller->callees->prev_callee = edge;
 362   caller->callees = edge;
 363   callee->callers = edge;
 364   edge->count = count;
 365   gcc_assert (count >= 0);
 366   edge->frequency = freq;
 367   gcc_assert (freq >= 0);
 368   gcc_assert (freq <= CGRAPH_FREQ_MAX);
 369   edge->loop_nest = nest;
 370   if (caller->call_site_hash)
 371     {
 372       void **slot;
 373       slot = htab_find_slot_with_hash (caller->call_site_hash,
 374                                        edge->call_stmt,
 375                                        htab_hash_pointer
 376                                          (edge->call_stmt),
 377                                        INSERT);
 378       gcc_assert (!*slot);
 379       *slot = edge;
 380     }
 381   return edge;
 382 }
 383
 384 /* Remove the edge E from the list of the callers of the callee.  */
 385
 386 static inline void
 387 cgraph_edge_remove_callee (struct cgraph_edge *e)
 388 {
 389   if (e->prev_caller)
 390     e->prev_caller->next_caller = e->next_caller;
 391   if (e->next_caller)
 392     e->next_caller->prev_caller = e->prev_caller;
 393   if (!e->prev_caller)
 394     e->callee->callers = e->next_caller;
 395 }
 396
 397 /* Remove the edge E from the list of the callees of the caller.  */
 398
 399 static inline void
 400 cgraph_edge_remove_caller (struct cgraph_edge *e)
 401 {
 402   if (e->prev_callee)
 403     e->prev_callee->next_callee = e->next_callee;
 404   if (e->next_callee)
 405     e->next_callee->prev_callee = e->prev_callee;
 406   if (!e->prev_callee)
 407     e->caller->callees = e->next_callee;
 408   if (e->caller->call_site_hash)
 409     htab_remove_elt_with_hash (e->caller->call_site_hash,
 410                                e->call_stmt,
 411                                htab_hash_pointer (e->call_stmt));
 412 }
 413
 414 /* Remove the edge E in the cgraph.  */
 415
 416 void
 417 cgraph_remove_edge (struct cgraph_edge *e)
 418 {
 419   /* Remove from callers list of the callee.  */
 420   cgraph_edge_remove_callee (e);
 421
 422   /* Remove from callees list of the callers.  */
 423   cgraph_edge_remove_caller (e);
 424 }
 425
 426 /* Redirect callee of E to N.  The function does not update underlying
 427    call expression.  */
 428
 429 void
 430 cgraph_redirect_edge_callee (struct cgraph_edge *e, struct cgraph_node *n)
 431 {
 432   /* Remove from callers list of the current callee.  */
 433   cgraph_edge_remove_callee (e);
 434
 435   /* Insert to callers list of the new callee.  */
 436   e->prev_caller = NULL;
 437   if (n->callers)
 438     n->callers->prev_caller = e;
 439   e->next_caller = n->callers;
 440   n->callers = e;
 441   e->callee = n;
 442 }
 443
 444 /* 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", "overwrittable", "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.self_insns)
 727     fprintf (f, " %i insns", node->local.self_insns);
 728   if (node->global.insns && node->global.insns != node->local.self_insns)
 729     fprintf (f, " (%i after inlining)", node->global.insns);
 730   if (node->local.estimated_self_stack_size)
 731     fprintf (f, " %i bytes stack usage", (int)node->local.estimated_self_stack_size);
 732   if (node->global.estimated_stack_size != node->local.estimated_self_stack_size)
 733     fprintf (f, " %i bytes after inlining", (int)node->global.estimated_stack_size);
 734   if (node->origin)
 735     fprintf (f, " nested in: %s", cgraph_node_name (node->origin));
 736   if (node->needed)
 737     fprintf (f, " needed");
 738   else if (node->reachable)
 739     fprintf (f, " reachable");
 740   if (DECL_SAVED_TREE (node->decl))
 741     fprintf (f, " tree");
 742   if (node->output)
 743     fprintf (f, " output");
 744   if (node->local.local)
 745     fprintf (f, " local");
 746   if (node->local.externally_visible)
 747     fprintf (f, " externally_visible");
 748   if (node->local.finalized)
 749     fprintf (f, " finalized");
 750   if (node->local.disregard_inline_limits)
 751     fprintf (f, " always_inline");
 752   else if (node->local.inlinable)
 753     fprintf (f, " inlinable");
 754   if (node->local.redefined_extern_inline)
 755     fprintf (f, " redefined_extern_inline");
 756   if (TREE_ASM_WRITTEN (node->decl))
 757     fprintf (f, " asm_written");
 758
 759   fprintf (f, "\n  called by: ");
 760   for (edge = node->callers; edge; edge = edge->next_caller)
 761     {
 762       fprintf (f, "%s/%i ", cgraph_node_name (edge->caller),
 763                edge->caller->uid);
 764       if (edge->count)
 765         fprintf (f, "("HOST_WIDEST_INT_PRINT_DEC"x) ",
 766                  (HOST_WIDEST_INT)edge->count);
 767       if (edge->frequency)
 768         fprintf (f, "(%.2f per call) ",
 769                  edge->frequency / (double)CGRAPH_FREQ_BASE);
 770       if (!edge->inline_failed)
 771         fprintf(f, "(inlined) ");
 772     }
 773
 774   fprintf (f, "\n  calls: ");
 775   for (edge = node->callees; edge; edge = edge->next_callee)
 776     {
 777       fprintf (f, "%s/%i ", cgraph_node_name (edge->callee),
 778                edge->callee->uid);
 779       if (!edge->inline_failed)
 780         fprintf(f, "(inlined) ");
 781       if (edge->count)
 782         fprintf (f, "("HOST_WIDEST_INT_PRINT_DEC"x) ",
 783                  (HOST_WIDEST_INT)edge->count);
 784       if (edge->frequency)
 785         fprintf (f, "(%.2f per call) ",
 786                  edge->frequency / (double)CGRAPH_FREQ_BASE);
 787       if (edge->loop_nest)
 788         fprintf (f, "(nested in %i loops) ", edge->loop_nest);
 789     }
 790   fprintf (f, "\n");
 791 }
 792
 793
 794 /* Dump call graph node NODE to stderr.  */
 795
 796 void
 797 debug_cgraph_node (struct cgraph_node *node)
 798 {
 799   dump_cgraph_node (stderr, node);
 800 }
 801
 802
 803 /* Dump the callgraph to file F.  */
 804
 805 void
 806 dump_cgraph (FILE *f)
 807 {
 808   struct cgraph_node *node;
 809
 810   fprintf (f, "callgraph:\n\n");
 811   for (node = cgraph_nodes; node; node = node->next)
 812     dump_cgraph_node (f, node);
 813 }
 814
 815
 816 /* Dump the call graph to stderr.  */
 817
 818 void
 819 debug_cgraph (void)
 820 {
 821   dump_cgraph (stderr);
 822 }
 823
 824
 825 /* Set the DECL_ASSEMBLER_NAME and update cgraph hashtables.  */
 826
 827 void
 828 change_decl_assembler_name (tree decl, tree name)
 829 {
 830   if (!DECL_ASSEMBLER_NAME_SET_P (decl))
 831     {
 832       SET_DECL_ASSEMBLER_NAME (decl, name);
 833       return;
 834     }
 835   if (name == DECL_ASSEMBLER_NAME (decl))
 836     return;
 837
 838   if (TREE_SYMBOL_REFERENCED (DECL_ASSEMBLER_NAME (decl))
 839       && DECL_RTL_SET_P (decl))
 840     warning (0, "%D renamed after being referenced in assembly", decl);
 841
 842   SET_DECL_ASSEMBLER_NAME (decl, name);
 843 }
 844
 845 /* Add a top-level asm statement to the list.  */
 846
 847 struct cgraph_asm_node *
 848 cgraph_add_asm_node (tree asm_str)
 849 {
 850   struct cgraph_asm_node *node;
 851
 852   node = GGC_CNEW (struct cgraph_asm_node);
 853   node->asm_str = asm_str;
 854   node->order = cgraph_order++;
 855   node->next = NULL;
 856   if (cgraph_asm_nodes == NULL)
 857     cgraph_asm_nodes = node;
 858   else
 859     cgraph_asm_last_node->next = node;
 860   cgraph_asm_last_node = node;
 861   return node;
 862 }
 863
 864 /* Return true when the DECL can possibly be inlined.  */
 865 bool
 866 cgraph_function_possibly_inlined_p (tree decl)
 867 {
 868   if (!cgraph_global_info_ready)
 869     return (DECL_INLINE (decl) && !flag_really_no_inline);
 870   return DECL_POSSIBLY_INLINED (decl);
 871 }
 872
 873 /* Create clone of E in the node N represented by CALL_EXPR the callgraph.  */
 874 struct cgraph_edge *
 875 cgraph_clone_edge (struct cgraph_edge *e, struct cgraph_node *n,
 876                    tree call_stmt, gcov_type count_scale, int freq_scale,
 877                    int loop_nest, bool update_original)
 878 {
 879   struct cgraph_edge *new;
 880   gcov_type count = e->count * count_scale / REG_BR_PROB_BASE;
 881   gcov_type freq = e->frequency * (gcov_type) freq_scale / CGRAPH_FREQ_BASE;
 882
 883   if (freq > CGRAPH_FREQ_MAX)
 884     freq = CGRAPH_FREQ_MAX;
 885   new = cgraph_create_edge (n, e->callee, call_stmt, count, freq,
 886                             e->loop_nest + loop_nest);
 887
 888   new->inline_failed = e->inline_failed;
 889   if (update_original)
 890     {
 891       e->count -= new->count;
 892       if (e->count < 0)
 893         e->count = 0;
 894     }
 895   return new;
 896 }
 897
 898 /* Create node representing clone of N executed COUNT times.  Decrease
 899    the execution counts from original node too.
 900
 901    When UPDATE_ORIGINAL is true, the counts are subtracted from the original
 902    function's profile to reflect the fact that part of execution is handled
 903    by node.  */
 904 struct cgraph_node *
 905 cgraph_clone_node (struct cgraph_node *n, gcov_type count, int freq, int loop_nest,
 906                    bool update_original)
 907 {
 908   struct cgraph_node *new = cgraph_create_node ();
 909   struct cgraph_edge *e;
 910   gcov_type count_scale;
 911
 912   new->decl = n->decl;
 913   new->origin = n->origin;
 914   if (new->origin)
 915     {
 916       new->next_nested = new->origin->nested;
 917       new->origin->nested = new;
 918     }
 919   new->analyzed = n->analyzed;
 920   new->local = n->local;
 921   new->global = n->global;
 922   new->rtl = n->rtl;
 923   new->master_clone = n->master_clone;
 924   new->count = count;
 925   if (n->count)
 926     count_scale = new->count * REG_BR_PROB_BASE / n->count;
 927   else
 928     count_scale = 0;
 929   if (update_original)
 930     {
 931       n->count -= count;
 932       if (n->count < 0)
 933         n->count = 0;
 934     }
 935
 936   for (e = n->callees;e; e=e->next_callee)
 937     cgraph_clone_edge (e, new, e->call_stmt, count_scale, freq, loop_nest,
 938                        update_original);
 939
 940   new->next_clone = n->next_clone;
 941   new->prev_clone = n;
 942   n->next_clone = new;
 943   if (new->next_clone)
 944     new->next_clone->prev_clone = new;
 945
 946   return new;
 947 }
 948
 949 /* Return true if N is an master_clone, (see cgraph_master_clone).  */
 950
 951 bool
 952 cgraph_is_master_clone (struct cgraph_node *n)
 953 {
 954   return (n == cgraph_master_clone (n));
 955 }
 956
 957 struct cgraph_node *
 958 cgraph_master_clone (struct cgraph_node *n)
 959 {
 960   enum availability avail = cgraph_function_body_availability (n);
 961
 962   if (avail == AVAIL_NOT_AVAILABLE || avail == AVAIL_OVERWRITABLE)
 963     return NULL;
 964
 965   if (!n->master_clone)
 966     n->master_clone = cgraph_node (n->decl);
 967
 968   return n->master_clone;
 969 }
 970
 971 /* NODE is no longer nested function; update cgraph accordingly.  */
 972 void
 973 cgraph_unnest_node (struct cgraph_node *node)
 974 {
 975   struct cgraph_node **node2 = &node->origin->nested;
 976   gcc_assert (node->origin);
 977
 978   while (*node2 != node)
 979     node2 = &(*node2)->next_nested;
 980   *node2 = node->next_nested;
 981   node->origin = NULL;
 982 }
 983
 984 /* Return function availability.  See cgraph.h for description of individual
 985    return values.  */
 986 enum availability
 987 cgraph_function_body_availability (struct cgraph_node *node)
 988 {
 989   enum availability avail;
 990   gcc_assert (cgraph_function_flags_ready);
 991   if (!node->analyzed)
 992     avail = AVAIL_NOT_AVAILABLE;
 993   else if (node->local.local)
 994     avail = AVAIL_LOCAL;
 995   else if (node->local.externally_visible)
 996     avail = AVAIL_AVAILABLE;
 997
 998   /* If the function can be overwritten, return OVERWRITABLE.  Take
 999      care at least of two notable extensions - the COMDAT functions
1000      used to share template instantiations in C++ (this is symmetric
1001      to code cp_cannot_inline_tree_fn and probably shall be shared and
1002      the inlinability hooks completely eliminated).
1003
1004      ??? Does the C++ one definition rule allow us to always return
1005      AVAIL_AVAILABLE here?  That would be good reason to preserve this
1006      hook Similarly deal with extern inline functions - this is again
1007      necessary to get C++ shared functions having keyed templates
1008      right and in the C extension documentation we probably should
1009      document the requirement of both versions of function (extern
1010      inline and offline) having same side effect characteristics as
1011      good optimization is what this optimization is about.  */
1012
1013   else if (!(*targetm.binds_local_p) (node->decl)
1014            && !DECL_COMDAT (node->decl) && !DECL_EXTERNAL (node->decl))
1015     avail = AVAIL_OVERWRITABLE;
1016   else avail = AVAIL_AVAILABLE;
1017
1018   return avail;
1019 }
1020
1021 /* Add the function FNDECL to the call graph.
1022    Unlike cgraph_finalize_function, this function is intended to be used
1023    by middle end and allows insertion of new function at arbitrary point
1024    of compilation.  The function can be either in high, low or SSA form
1025    GIMPLE.
1026
1027    The function is assumed to be reachable and have address taken (so no
1028    API breaking optimizations are performed on it).
1029
1030    Main work done by this function is to enqueue the function for later
1031    processing to avoid need the passes to be re-entrant.  */
1032
1033 void
1034 cgraph_add_new_function (tree fndecl, bool lowered)
1035 {
1036   struct cgraph_node *node;
1037   switch (cgraph_state)
1038     {
1039       case CGRAPH_STATE_CONSTRUCTION:
1040         /* Just enqueue function to be processed at nearest occurence.  */
1041         node = cgraph_node (fndecl);
1042         node->next_needed = cgraph_new_nodes;
1043         if (lowered)
1044           node->lowered = true;
1045         cgraph_new_nodes = node;
1046         break;
1047
1048       case CGRAPH_STATE_IPA:
1049       case CGRAPH_STATE_IPA_SSA:
1050       case CGRAPH_STATE_EXPANSION:
1051         /* Bring the function into finalized state and enqueue for later
1052            analyzing and compilation.  */
1053         node = cgraph_node (fndecl);
1054         node->local.local = false;
1055         node->local.finalized = true;
1056         node->reachable = node->needed = true;
1057         if (lowered)
1058           node->lowered = true;
1059         node->next_needed = cgraph_new_nodes;
1060         cgraph_new_nodes = node;
1061         break;
1062
1063       case CGRAPH_STATE_FINISHED:
1064         /* At the very end of compilation we have to do all the work up
1065            to expansion.  */
1066         push_cfun (DECL_STRUCT_FUNCTION (fndecl));
1067         current_function_decl = fndecl;
1068         tree_register_cfg_hooks ();
1069         if (!lowered)
1070           tree_lowering_passes (fndecl);
1071         bitmap_obstack_initialize (NULL);
1072         if (!gimple_in_ssa_p (DECL_STRUCT_FUNCTION (fndecl)) && optimize)
1073           execute_pass_list (pass_early_local_passes.pass.sub);
1074         bitmap_obstack_release (NULL);
1075         tree_rest_of_compilation (fndecl);
1076         pop_cfun ();
1077         current_function_decl = NULL;
1078         break;
1079     }
1080 }
1081
1082 #include "gt-cgraph.h"