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