gcc/cgraph.c

   1 /* Callgraph handling code.
   2    Copyright (C) 2003, 2004 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, 59 Temple Place - Suite 330, Boston, MA
  20 02111-1307, USA.  */
  21
  22 #include "config.h"
  23 #include "system.h"
  24 #include "coretypes.h"
  25 #include "tm.h"
  26 #include "tree.h"
  27 #include "langhooks.h"
  28 #include "hashtab.h"
  29 #include "toplev.h"
  30 #include "flags.h"
  31 #include "ggc.h"
  32 #include "debug.h"
  33 #include "target.h"
  34 #include "cgraph.h"
  35 #include "varray.h"
  36 #include "output.h"
  37 #include "intl.h"
  38
  39
  40 /* Hash table used to convert declarations into nodes.  */
  41 static GTY((param_is (struct cgraph_node))) htab_t cgraph_hash;
  42
  43 /* The linked list of cgraph nodes.  */
  44 struct cgraph_node *cgraph_nodes;
  45
  46 /* Queue of cgraph nodes scheduled to be lowered.  */
  47 struct cgraph_node *cgraph_nodes_queue;
  48
  49 /* Number of nodes in existence.  */
  50 int cgraph_n_nodes;
  51
  52 /* Maximal uid used in cgraph nodes.  */
  53 int cgraph_max_uid;
  54
  55 /* Set when whole unit has been analyzed so we can access global info.  */
  56 bool cgraph_global_info_ready = false;
  57
  58 /* Hash table used to convert declarations into nodes.  */
  59 static GTY((param_is (struct cgraph_varpool_node))) htab_t cgraph_varpool_hash;
  60
  61 /* Queue of cgraph nodes scheduled to be lowered and output.  */
  62 struct cgraph_varpool_node *cgraph_varpool_nodes_queue;
  63
  64 /* Number of nodes in existence.  */
  65 int cgraph_varpool_n_nodes;
  66
  67 /* The linked list of cgraph varpool nodes.  */
  68 static GTY(())  struct cgraph_varpool_node *cgraph_varpool_nodes;
  69
  70 static struct cgraph_edge *create_edge (struct cgraph_node *,
  71                                         struct cgraph_node *);
  72 static hashval_t hash_node (const void *);
  73 static int eq_node (const void *, const void *);
  74
  75 /* Returns a hash code for P.  */
  76
  77 static hashval_t
  78 hash_node (const void *p)
  79 {
  80   return ((hashval_t)
  81           IDENTIFIER_HASH_VALUE (DECL_ASSEMBLER_NAME
  82                                  (((struct cgraph_node *) p)->decl)));
  83 }
  84
  85 /* Returns nonzero if P1 and P2 are equal.  */
  86
  87 static int
  88 eq_node (const void *p1, const void *p2)
  89 {
  90   return ((DECL_ASSEMBLER_NAME (((struct cgraph_node *) p1)->decl)) ==
  91           (tree) p2);
  92 }
  93
  94 /* Return cgraph node assigned to DECL.  Create new one when needed.  */
  95 struct cgraph_node *
  96 cgraph_node (tree decl)
  97 {
  98   struct cgraph_node *node;
  99   struct cgraph_node **slot;
 100
 101   if (TREE_CODE (decl) != FUNCTION_DECL)
 102     abort ();
 103
 104   if (!cgraph_hash)
 105     cgraph_hash = htab_create_ggc (10, hash_node, eq_node, NULL);
 106
 107   slot = (struct cgraph_node **)
 108     htab_find_slot_with_hash (cgraph_hash, DECL_ASSEMBLER_NAME (decl),
 109                               IDENTIFIER_HASH_VALUE
 110                                 (DECL_ASSEMBLER_NAME (decl)), INSERT);
 111   if (*slot)
 112     return *slot;
 113   node = ggc_alloc_cleared (sizeof (*node));
 114   node->decl = decl;
 115   node->next = cgraph_nodes;
 116   node->uid = cgraph_max_uid++;
 117   if (cgraph_nodes)
 118     cgraph_nodes->previous = node;
 119   node->previous = NULL;
 120   cgraph_nodes = node;
 121   cgraph_n_nodes++;
 122   *slot = node;
 123   if (DECL_CONTEXT (decl) && TREE_CODE (DECL_CONTEXT (decl)) == FUNCTION_DECL)
 124     {
 125       node->origin = cgraph_node (DECL_CONTEXT (decl));
 126       node->next_nested = node->origin->nested;
 127       node->origin->nested = node;
 128     }
 129   return node;
 130 }
 131
 132 /* Try to find existing function for identifier ID.  */
 133 struct cgraph_node *
 134 cgraph_node_for_identifier (tree id)
 135 {
 136   struct cgraph_node **slot;
 137
 138   if (TREE_CODE (id) != IDENTIFIER_NODE)
 139     abort ();
 140
 141   if (!cgraph_hash)
 142     return NULL;
 143
 144   slot = (struct cgraph_node **)
 145     htab_find_slot_with_hash (cgraph_hash, id,
 146                               IDENTIFIER_HASH_VALUE (id), NO_INSERT);
 147   if (!slot)
 148     return NULL;
 149   return *slot;
 150 }
 151
 152 /* Create edge from CALLER to CALLEE in the cgraph.  */
 153
 154 static struct cgraph_edge *
 155 create_edge (struct cgraph_node *caller, struct cgraph_node *callee)
 156 {
 157   struct cgraph_edge *edge = ggc_alloc (sizeof (struct cgraph_edge));
 158   struct cgraph_edge *edge2;
 159
 160   if (!DECL_SAVED_TREE (callee->decl))
 161     edge->inline_failed = N_("function body not available");
 162   else if (callee->local.redefined_extern_inline)
 163     edge->inline_failed = N_("redefined extern inline functions are not "
 164                              "considered for inlining");
 165   else if (callee->local.inlinable)
 166     edge->inline_failed = N_("function not considered for inlining");
 167   else
 168     edge->inline_failed = N_("function not inlinable");
 169
 170   /* At the moment we don't associate calls with specific CALL_EXPRs
 171      as we probably ought to, so we must preserve inline_call flags to
 172      be the same in all copies of the same edge.  */
 173   if (cgraph_global_info_ready)
 174     for (edge2 = caller->callees; edge2; edge2 = edge2->next_callee)
 175       if (edge2->callee == callee)
 176         {
 177           edge->inline_failed = edge2->inline_failed;
 178           break;
 179         }
 180
 181   edge->caller = caller;
 182   edge->callee = callee;
 183   edge->next_caller = callee->callers;
 184   edge->next_callee = caller->callees;
 185   caller->callees = edge;
 186   callee->callers = edge;
 187   return edge;
 188 }
 189
 190 /* Remove the edge from CALLER to CALLEE in the cgraph.  */
 191
 192 void
 193 cgraph_remove_edge (struct cgraph_node *caller, struct cgraph_node *callee)
 194 {
 195   struct cgraph_edge **edge, **edge2;
 196
 197   for (edge = &callee->callers; *edge && (*edge)->caller != caller;
 198        edge = &((*edge)->next_caller))
 199     continue;
 200   if (!*edge)
 201     abort ();
 202   *edge = (*edge)->next_caller;
 203   for (edge2 = &caller->callees; *edge2 && (*edge2)->callee != callee;
 204        edge2 = &(*edge2)->next_callee)
 205     continue;
 206   if (!*edge2)
 207     abort ();
 208   *edge2 = (*edge2)->next_callee;
 209 }
 210
 211 /* Remove the node from cgraph.  */
 212
 213 void
 214 cgraph_remove_node (struct cgraph_node *node)
 215 {
 216   void **slot;
 217   while (node->callers)
 218     cgraph_remove_edge (node->callers->caller, node);
 219   while (node->callees)
 220     cgraph_remove_edge (node, node->callees->callee);
 221   while (node->nested)
 222     cgraph_remove_node (node->nested);
 223   if (node->origin)
 224     {
 225       struct cgraph_node **node2 = &node->origin->nested;
 226
 227       while (*node2 != node)
 228         node2 = &(*node2)->next_nested;
 229       *node2 = node->next_nested;
 230     }
 231   if (node->previous)
 232     node->previous->next = node->next;
 233   else
 234     cgraph_nodes = node->next;
 235   if (node->next)
 236     node->next->previous = node->previous;
 237   DECL_SAVED_TREE (node->decl) = NULL;
 238   DECL_STRUCT_FUNCTION (node->decl) = NULL;
 239   DECL_ARGUMENTS (node->decl) = NULL;
 240   DECL_INITIAL (node->decl) = error_mark_node;
 241   slot =
 242     htab_find_slot_with_hash (cgraph_hash, DECL_ASSEMBLER_NAME (node->decl),
 243                               IDENTIFIER_HASH_VALUE (DECL_ASSEMBLER_NAME
 244                                                      (node->decl)), NO_INSERT);
 245   htab_clear_slot (cgraph_hash, slot);
 246   /* Do not free the structure itself so the walk over chain can continue.  */
 247 }
 248
 249 /* Notify finalize_compilation_unit that given node is reachable.  */
 250
 251 void
 252 cgraph_mark_reachable_node (struct cgraph_node *node)
 253 {
 254   if (!node->reachable && node->local.finalized)
 255     {
 256       notice_global_symbol (node->decl);
 257       node->reachable = 1;
 258
 259       node->next_needed = cgraph_nodes_queue;
 260       cgraph_nodes_queue = node;
 261
 262       /* At the moment frontend automatically emits all nested functions.  */
 263       if (node->nested)
 264         {
 265           struct cgraph_node *node2;
 266
 267           for (node2 = node->nested; node2; node2 = node2->next_nested)
 268             if (!node2->reachable)
 269               cgraph_mark_reachable_node (node2);
 270         }
 271     }
 272 }
 273
 274 /* Likewise indicate that a node is needed, i.e. reachable via some
 275    external means.  */
 276
 277 void
 278 cgraph_mark_needed_node (struct cgraph_node *node)
 279 {
 280   node->needed = 1;
 281   cgraph_mark_reachable_node (node);
 282 }
 283
 284 /* Record call from CALLER to CALLEE.  */
 285
 286 struct cgraph_edge *
 287 cgraph_record_call (tree caller, tree callee)
 288 {
 289   return create_edge (cgraph_node (caller), cgraph_node (callee));
 290 }
 291
 292 void
 293 cgraph_remove_call (tree caller, tree callee)
 294 {
 295   cgraph_remove_edge (cgraph_node (caller), cgraph_node (callee));
 296 }
 297
 298 /* Return true when CALLER_DECL calls CALLEE_DECL.  */
 299
 300 bool
 301 cgraph_calls_p (tree caller_decl, tree callee_decl)
 302 {
 303   struct cgraph_node *caller = cgraph_node (caller_decl);
 304   struct cgraph_node *callee = cgraph_node (callee_decl);
 305   struct cgraph_edge *edge;
 306
 307   for (edge = callee->callers; edge && (edge)->caller != caller;
 308        edge = (edge->next_caller))
 309     continue;
 310   return edge != NULL;
 311 }
 312
 313 /* Return local info for the compiled function.  */
 314
 315 struct cgraph_local_info *
 316 cgraph_local_info (tree decl)
 317 {
 318   struct cgraph_node *node;
 319   if (TREE_CODE (decl) != FUNCTION_DECL)
 320     abort ();
 321   node = cgraph_node (decl);
 322   return &node->local;
 323 }
 324
 325 /* Return local info for the compiled function.  */
 326
 327 struct cgraph_global_info *
 328 cgraph_global_info (tree decl)
 329 {
 330   struct cgraph_node *node;
 331   if (TREE_CODE (decl) != FUNCTION_DECL || !cgraph_global_info_ready)
 332     abort ();
 333   node = cgraph_node (decl);
 334   return &node->global;
 335 }
 336
 337 /* Return local info for the compiled function.  */
 338
 339 struct cgraph_rtl_info *
 340 cgraph_rtl_info (tree decl)
 341 {
 342   struct cgraph_node *node;
 343   if (TREE_CODE (decl) != FUNCTION_DECL)
 344     abort ();
 345   node = cgraph_node (decl);
 346   if (decl != current_function_decl
 347       && !TREE_ASM_WRITTEN (node->decl))
 348     return NULL;
 349   return &node->rtl;
 350 }
 351
 352 /* Return name of the node used in debug output.  */
 353 const char *
 354 cgraph_node_name (struct cgraph_node *node)
 355 {
 356   return (*lang_hooks.decl_printable_name) (node->decl, 2);
 357 }
 358
 359 /* Dump the callgraph.  */
 360
 361 void
 362 dump_cgraph (FILE *f)
 363 {
 364   struct cgraph_node *node;
 365
 366   fprintf (f, "callgraph:\n\n");
 367   for (node = cgraph_nodes; node; node = node->next)
 368     {
 369       struct cgraph_edge *edge;
 370       fprintf (f, "%s:", cgraph_node_name (node));
 371       if (node->local.self_insns)
 372         fprintf (f, " %i insns", node->local.self_insns);
 373       if (node->global.insns && node->global.insns != node->local.self_insns)
 374         fprintf (f, " (%i after inlining)", node->global.insns);
 375       if (node->origin)
 376         fprintf (f, " nested in: %s", cgraph_node_name (node->origin));
 377       if (node->needed)
 378         fprintf (f, " needed");
 379       else if (node->reachable)
 380         fprintf (f, " reachable");
 381       if (DECL_SAVED_TREE (node->decl))
 382         fprintf (f, " tree");
 383
 384       if (node->local.local)
 385         fprintf (f, " local");
 386       if (node->local.disregard_inline_limits)
 387         fprintf (f, " always_inline");
 388       else if (node->local.inlinable)
 389         fprintf (f, " inlinable");
 390       if (node->global.cloned_times > 1)
 391         fprintf (f, " cloned %ix", node->global.cloned_times);
 392
 393       fprintf (f, "\n  called by: ");
 394       for (edge = node->callers; edge; edge = edge->next_caller)
 395         {
 396           fprintf (f, "%s ", cgraph_node_name (edge->caller));
 397           if (!edge->inline_failed)
 398             fprintf(f, "(inlined) ");
 399         }
 400
 401       fprintf (f, "\n  calls: ");
 402       for (edge = node->callees; edge; edge = edge->next_callee)
 403         {
 404           fprintf (f, "%s ", cgraph_node_name (edge->callee));
 405           if (!edge->inline_failed)
 406             fprintf(f, "(inlined) ");
 407         }
 408       fprintf (f, "\n");
 409     }
 410 }
 411
 412 /* Returns a hash code for P.  */
 413
 414 static hashval_t
 415 cgraph_varpool_hash_node (const void *p)
 416 {
 417   return ((hashval_t)
 418           IDENTIFIER_HASH_VALUE (DECL_ASSEMBLER_NAME
 419                                  (((struct cgraph_varpool_node *) p)->decl)));
 420 }
 421
 422 /* Returns nonzero if P1 and P2 are equal.  */
 423
 424 static int
 425 eq_cgraph_varpool_node (const void *p1, const void *p2)
 426 {
 427   return ((DECL_ASSEMBLER_NAME (((struct cgraph_varpool_node *) p1)->decl)) ==
 428           (tree) p2);
 429 }
 430
 431 /* Return cgraph_varpool node assigned to DECL.  Create new one when needed.  */
 432 struct cgraph_varpool_node *
 433 cgraph_varpool_node (tree decl)
 434 {
 435   struct cgraph_varpool_node *node;
 436   struct cgraph_varpool_node **slot;
 437
 438   if (!DECL_P (decl) || TREE_CODE (decl) == FUNCTION_DECL)
 439     abort ();
 440
 441   if (!cgraph_varpool_hash)
 442     cgraph_varpool_hash = htab_create_ggc (10, cgraph_varpool_hash_node,
 443                                            eq_cgraph_varpool_node, NULL);
 444   slot = (struct cgraph_varpool_node **)
 445     htab_find_slot_with_hash (cgraph_varpool_hash, DECL_ASSEMBLER_NAME (decl),
 446                               IDENTIFIER_HASH_VALUE (DECL_ASSEMBLER_NAME (decl)),
 447                               INSERT);
 448   if (*slot)
 449     return *slot;
 450   node = ggc_alloc_cleared (sizeof (*node));
 451   node->decl = decl;
 452   cgraph_varpool_n_nodes++;
 453   cgraph_varpool_nodes = node;
 454   *slot = node;
 455   return node;
 456 }
 457
 458 /* Set the DECL_ASSEMBLER_NAME and update cgraph hashtables.  */
 459 void
 460 change_decl_assembler_name (tree decl, tree name)
 461 {
 462   struct cgraph_node *node = NULL;
 463   struct cgraph_varpool_node *vnode = NULL;
 464   void **slot;
 465
 466   if (!DECL_ASSEMBLER_NAME_SET_P (decl))
 467     {
 468       SET_DECL_ASSEMBLER_NAME (decl, name);
 469       return;
 470     }
 471   if (name == DECL_ASSEMBLER_NAME (decl))
 472     return;
 473
 474   if (TREE_SYMBOL_REFERENCED (DECL_ASSEMBLER_NAME (decl))
 475       && DECL_RTL_SET_P (decl))
 476     warning ("%D renamed after being referenced in assembly", decl);
 477
 478   if (TREE_CODE (decl) == FUNCTION_DECL && cgraph_hash)
 479     {
 480       /* Take a look whether declaration is in the cgraph structure.  */
 481       slot =
 482         htab_find_slot_with_hash (cgraph_hash, DECL_ASSEMBLER_NAME (decl),
 483                                    IDENTIFIER_HASH_VALUE (DECL_ASSEMBLER_NAME
 484                                                           (decl)), NO_INSERT);
 485       if (slot)
 486         node = *slot;
 487
 488       /* It is, verify that we are the canonical node for this decl.  */
 489       if (node && node->decl == decl)
 490         {
 491           node = *slot;
 492           htab_clear_slot (cgraph_hash, slot);
 493          }
 494        else
 495          node = NULL;
 496     }
 497   if (TREE_CODE (decl) == VAR_DECL && TREE_STATIC (decl) && cgraph_varpool_hash)
 498     {
 499       /* Take a look whether declaration is in the cgraph structure.  */
 500       slot =
 501         htab_find_slot_with_hash (cgraph_varpool_hash, DECL_ASSEMBLER_NAME (decl),
 502                                    IDENTIFIER_HASH_VALUE (DECL_ASSEMBLER_NAME
 503                                                           (decl)), NO_INSERT);
 504       if (slot)
 505         vnode = *slot;
 506
 507       /* It is, verify that we are the canonical vnode for this decl.  */
 508       if (vnode && vnode->decl == decl)
 509         {
 510           vnode = *slot;
 511           htab_clear_slot (cgraph_varpool_hash, slot);
 512          }
 513        else
 514          vnode = NULL;
 515     }
 516   SET_DECL_ASSEMBLER_NAME (decl, name);
 517   if (node)
 518     {
 519       slot =
 520         htab_find_slot_with_hash (cgraph_hash, name,
 521                                   IDENTIFIER_HASH_VALUE (name), INSERT);
 522       if (*slot)
 523         abort ();
 524       *slot = node;
 525     }
 526   if (vnode)
 527     {
 528       slot =
 529         htab_find_slot_with_hash (cgraph_varpool_hash, name,
 530                                   IDENTIFIER_HASH_VALUE (name), INSERT);
 531       if (*slot)
 532         abort ();
 533       *slot = vnode;
 534     }
 535 }
 536
 537 /* Try to find existing function for identifier ID.  */
 538 struct cgraph_varpool_node *
 539 cgraph_varpool_node_for_identifier (tree id)
 540 {
 541   struct cgraph_varpool_node **slot;
 542
 543   if (TREE_CODE (id) != IDENTIFIER_NODE)
 544     abort ();
 545
 546   if (!cgraph_varpool_hash)
 547     return NULL;
 548
 549   slot = (struct cgraph_varpool_node **)
 550     htab_find_slot_with_hash (cgraph_varpool_hash, id,
 551                               IDENTIFIER_HASH_VALUE (id), NO_INSERT);
 552   if (!slot)
 553     return NULL;
 554   return *slot;
 555 }
 556
 557 /* Notify finalize_compilation_unit that given node is reachable
 558    or needed.  */
 559 void
 560 cgraph_varpool_mark_needed_node (struct cgraph_varpool_node *node)
 561 {
 562   if (!node->needed && node->finalized)
 563     {
 564       node->next_needed = cgraph_varpool_nodes_queue;
 565       cgraph_varpool_nodes_queue = node;
 566       notice_global_symbol (node->decl);
 567     }
 568   node->needed = 1;
 569 }
 570
 571 void
 572 cgraph_varpool_finalize_decl (tree decl)
 573 {
 574   struct cgraph_varpool_node *node = cgraph_varpool_node (decl);
 575
 576   /* The first declaration of a variable that comes through this function
 577      decides whether it is global (in C, has external linkage)
 578      or local (in C, has internal linkage).  So do nothing more
 579      if this function has already run.  */
 580   if (node->finalized)
 581     return;
 582   if (node->needed)
 583     {
 584       node->next_needed = cgraph_varpool_nodes_queue;
 585       cgraph_varpool_nodes_queue = node;
 586       notice_global_symbol (decl);
 587     }
 588   node->finalized = true;
 589
 590   if (/* Externally visible variables must be output.  The exception are
 591          COMDAT functions that must be output only when they are needed.  */
 592       (TREE_PUBLIC (decl) && !DECL_COMDAT (decl))
 593       /* Function whose name is output to the assembler file must be produced.
 594          It is possible to assemble the name later after finalizing the function
 595          and the fact is noticed in assemble_name then.  */
 596       || (DECL_ASSEMBLER_NAME_SET_P (decl)
 597           && TREE_SYMBOL_REFERENCED (DECL_ASSEMBLER_NAME (decl))))
 598     {
 599       cgraph_varpool_mark_needed_node (node);
 600     }
 601 }
 602
 603 bool
 604 cgraph_varpool_assemble_pending_decls (void)
 605 {
 606   bool changed = false;
 607
 608   while (cgraph_varpool_nodes_queue)
 609     {
 610       tree decl = cgraph_varpool_nodes_queue->decl;
 611       struct cgraph_varpool_node *node = cgraph_varpool_nodes_queue;
 612
 613       cgraph_varpool_nodes_queue = cgraph_varpool_nodes_queue->next_needed;
 614       if (!TREE_ASM_WRITTEN (decl))
 615         {
 616           assemble_variable (decl, 0, 1, 0);
 617           changed = true;
 618         }
 619       node->next_needed = NULL;
 620     }
 621   return changed;
 622 }
 623
 624 /* Return true when the DECL can possibly be inlined.  */
 625 bool
 626 cgraph_function_possibly_inlined_p (tree decl)
 627 {
 628   if (!cgraph_global_info_ready)
 629     return (DECL_INLINE (decl)
 630             && (!flag_really_no_inline
 631                 || (*lang_hooks.tree_inlining.disregard_inline_limits) (decl)));
 632   return cgraph_node (decl)->global.inlined;
 633 }
 634
 635 #include "gt-cgraph.h"