gcc/cgraph.c

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