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   slot =
 239     htab_find_slot_with_hash (cgraph_hash, DECL_ASSEMBLER_NAME (node->decl),
 240                               IDENTIFIER_HASH_VALUE (DECL_ASSEMBLER_NAME
 241                                                      (node->decl)), NO_INSERT);
 242   htab_clear_slot (cgraph_hash, slot);
 243   /* Do not free the structure itself so the walk over chain can continue.  */
 244 }
 245
 246 /* Notify finalize_compilation_unit that given node is reachable.  */
 247
 248 void
 249 cgraph_mark_reachable_node (struct cgraph_node *node)
 250 {
 251   if (!node->reachable && node->local.finalized)
 252     {
 253       notice_global_symbol (node->decl);
 254       node->reachable = 1;
 255
 256       node->next_needed = cgraph_nodes_queue;
 257       cgraph_nodes_queue = node;
 258
 259       /* At the moment frontend automatically emits all nested functions.  */
 260       if (node->nested)
 261         {
 262           struct cgraph_node *node2;
 263
 264           for (node2 = node->nested; node2; node2 = node2->next_nested)
 265             if (!node2->reachable)
 266               cgraph_mark_reachable_node (node2);
 267         }
 268     }
 269 }
 270
 271 /* Likewise indicate that a node is needed, i.e. reachable via some
 272    external means.  */
 273
 274 void
 275 cgraph_mark_needed_node (struct cgraph_node *node)
 276 {
 277   node->needed = 1;
 278   cgraph_mark_reachable_node (node);
 279 }
 280
 281 /* Record call from CALLER to CALLEE.  */
 282
 283 struct cgraph_edge *
 284 cgraph_record_call (tree caller, tree callee)
 285 {
 286   return create_edge (cgraph_node (caller), cgraph_node (callee));
 287 }
 288
 289 void
 290 cgraph_remove_call (tree caller, tree callee)
 291 {
 292   cgraph_remove_edge (cgraph_node (caller), cgraph_node (callee));
 293 }
 294
 295 /* Return true when CALLER_DECL calls CALLEE_DECL.  */
 296
 297 bool
 298 cgraph_calls_p (tree caller_decl, tree callee_decl)
 299 {
 300   struct cgraph_node *caller = cgraph_node (caller_decl);
 301   struct cgraph_node *callee = cgraph_node (callee_decl);
 302   struct cgraph_edge *edge;
 303
 304   for (edge = callee->callers; edge && (edge)->caller != caller;
 305        edge = (edge->next_caller))
 306     continue;
 307   return edge != NULL;
 308 }
 309
 310 /* Return local info for the compiled function.  */
 311
 312 struct cgraph_local_info *
 313 cgraph_local_info (tree decl)
 314 {
 315   struct cgraph_node *node;
 316   if (TREE_CODE (decl) != FUNCTION_DECL)
 317     abort ();
 318   node = cgraph_node (decl);
 319   return &node->local;
 320 }
 321
 322 /* Return local info for the compiled function.  */
 323
 324 struct cgraph_global_info *
 325 cgraph_global_info (tree decl)
 326 {
 327   struct cgraph_node *node;
 328   if (TREE_CODE (decl) != FUNCTION_DECL || !cgraph_global_info_ready)
 329     abort ();
 330   node = cgraph_node (decl);
 331   return &node->global;
 332 }
 333
 334 /* Return local info for the compiled function.  */
 335
 336 struct cgraph_rtl_info *
 337 cgraph_rtl_info (tree decl)
 338 {
 339   struct cgraph_node *node;
 340   if (TREE_CODE (decl) != FUNCTION_DECL)
 341     abort ();
 342   node = cgraph_node (decl);
 343   if (decl != current_function_decl
 344       && !TREE_ASM_WRITTEN (node->decl))
 345     return NULL;
 346   return &node->rtl;
 347 }
 348
 349 /* Return name of the node used in debug output.  */
 350 const char *
 351 cgraph_node_name (struct cgraph_node *node)
 352 {
 353   return (*lang_hooks.decl_printable_name) (node->decl, 2);
 354 }
 355
 356 /* Dump the callgraph.  */
 357
 358 void
 359 dump_cgraph (FILE *f)
 360 {
 361   struct cgraph_node *node;
 362
 363   fprintf (f, "callgraph:\n\n");
 364   for (node = cgraph_nodes; node; node = node->next)
 365     {
 366       struct cgraph_edge *edge;
 367       fprintf (f, "%s:", cgraph_node_name (node));
 368       if (node->local.self_insns)
 369         fprintf (f, " %i insns", node->local.self_insns);
 370       if (node->global.insns && node->global.insns != node->local.self_insns)
 371         fprintf (f, " (%i after inlining)", node->global.insns);
 372       if (node->origin)
 373         fprintf (f, " nested in: %s", cgraph_node_name (node->origin));
 374       if (node->needed)
 375         fprintf (f, " needed");
 376       else if (node->reachable)
 377         fprintf (f, " reachable");
 378       if (DECL_SAVED_TREE (node->decl))
 379         fprintf (f, " tree");
 380
 381       if (node->local.local)
 382         fprintf (f, " local");
 383       if (node->local.disregard_inline_limits)
 384         fprintf (f, " always_inline");
 385       else if (node->local.inlinable)
 386         fprintf (f, " inlinable");
 387       if (node->global.cloned_times > 1)
 388         fprintf (f, " cloned %ix", node->global.cloned_times);
 389
 390       fprintf (f, "\n  called by: ");
 391       for (edge = node->callers; edge; edge = edge->next_caller)
 392         {
 393           fprintf (f, "%s ", cgraph_node_name (edge->caller));
 394           if (!edge->inline_failed)
 395             fprintf(f, "(inlined) ");
 396         }
 397
 398       fprintf (f, "\n  calls: ");
 399       for (edge = node->callees; edge; edge = edge->next_callee)
 400         {
 401           fprintf (f, "%s ", cgraph_node_name (edge->callee));
 402           if (!edge->inline_failed)
 403             fprintf(f, "(inlined) ");
 404         }
 405       fprintf (f, "\n");
 406     }
 407 }
 408
 409 /* Returns a hash code for P.  */
 410
 411 static hashval_t
 412 cgraph_varpool_hash_node (const void *p)
 413 {
 414   return ((hashval_t)
 415           IDENTIFIER_HASH_VALUE (DECL_ASSEMBLER_NAME
 416                                  (((struct cgraph_varpool_node *) p)->decl)));
 417 }
 418
 419 /* Returns nonzero if P1 and P2 are equal.  */
 420
 421 static int
 422 eq_cgraph_varpool_node (const void *p1, const void *p2)
 423 {
 424   return ((DECL_ASSEMBLER_NAME (((struct cgraph_varpool_node *) p1)->decl)) ==
 425           (tree) p2);
 426 }
 427
 428 /* Return cgraph_varpool node assigned to DECL.  Create new one when needed.  */
 429 struct cgraph_varpool_node *
 430 cgraph_varpool_node (tree decl)
 431 {
 432   struct cgraph_varpool_node *node;
 433   struct cgraph_varpool_node **slot;
 434
 435   if (!DECL_P (decl) || TREE_CODE (decl) == FUNCTION_DECL)
 436     abort ();
 437
 438   if (!cgraph_varpool_hash)
 439     cgraph_varpool_hash = htab_create_ggc (10, cgraph_varpool_hash_node,
 440                                            eq_cgraph_varpool_node, NULL);
 441   slot = (struct cgraph_varpool_node **)
 442     htab_find_slot_with_hash (cgraph_varpool_hash, DECL_ASSEMBLER_NAME (decl),
 443                               IDENTIFIER_HASH_VALUE (DECL_ASSEMBLER_NAME (decl)),
 444                               INSERT);
 445   if (*slot)
 446     return *slot;
 447   node = ggc_alloc_cleared (sizeof (*node));
 448   node->decl = decl;
 449   cgraph_varpool_n_nodes++;
 450   cgraph_varpool_nodes = node;
 451   *slot = node;
 452   return node;
 453 }
 454
 455 /* Set the DECL_ASSEMBLER_NAME and update cgraph hashtables.  */
 456 void
 457 change_decl_assembler_name (tree decl, tree name)
 458 {
 459   struct cgraph_node *node = NULL;
 460   struct cgraph_varpool_node *vnode = NULL;
 461   void **slot;
 462
 463   if (!DECL_ASSEMBLER_NAME_SET_P (decl))
 464     {
 465       SET_DECL_ASSEMBLER_NAME (decl, name);
 466       return;
 467     }
 468   if (name == DECL_ASSEMBLER_NAME (decl))
 469     return;
 470
 471   if (TREE_SYMBOL_REFERENCED (DECL_ASSEMBLER_NAME (decl))
 472       && DECL_RTL_SET_P (decl))
 473     warning ("%D renamed after being referenced in assembly", decl);
 474
 475   if (TREE_CODE (decl) == FUNCTION_DECL && cgraph_hash)
 476     {
 477       /* Take a look whether declaration is in the cgraph structure.  */
 478       slot =
 479         htab_find_slot_with_hash (cgraph_hash, DECL_ASSEMBLER_NAME (decl),
 480                                    IDENTIFIER_HASH_VALUE (DECL_ASSEMBLER_NAME
 481                                                           (decl)), NO_INSERT);
 482       if (slot)
 483         node = *slot;
 484
 485       /* It is, verify that we are the canonical node for this decl.  */
 486       if (node && node->decl == decl)
 487         {
 488           node = *slot;
 489           htab_clear_slot (cgraph_hash, slot);
 490          }
 491        else
 492          node = NULL;
 493     }
 494   if (TREE_CODE (decl) == VAR_DECL && TREE_STATIC (decl) && cgraph_varpool_hash)
 495     {
 496       /* Take a look whether declaration is in the cgraph structure.  */
 497       slot =
 498         htab_find_slot_with_hash (cgraph_varpool_hash, DECL_ASSEMBLER_NAME (decl),
 499                                    IDENTIFIER_HASH_VALUE (DECL_ASSEMBLER_NAME
 500                                                           (decl)), NO_INSERT);
 501       if (slot)
 502         vnode = *slot;
 503
 504       /* It is, verify that we are the canonical vnode for this decl.  */
 505       if (vnode && vnode->decl == decl)
 506         {
 507           vnode = *slot;
 508           htab_clear_slot (cgraph_varpool_hash, slot);
 509          }
 510        else
 511          vnode = NULL;
 512     }
 513   SET_DECL_ASSEMBLER_NAME (decl, name);
 514   if (node)
 515     {
 516       slot =
 517         htab_find_slot_with_hash (cgraph_hash, name,
 518                                   IDENTIFIER_HASH_VALUE (name), INSERT);
 519       if (*slot)
 520         abort ();
 521       *slot = node;
 522     }
 523   if (vnode)
 524     {
 525       slot =
 526         htab_find_slot_with_hash (cgraph_varpool_hash, name,
 527                                   IDENTIFIER_HASH_VALUE (name), INSERT);
 528       if (*slot)
 529         abort ();
 530       *slot = vnode;
 531     }
 532 }
 533
 534 /* Try to find existing function for identifier ID.  */
 535 struct cgraph_varpool_node *
 536 cgraph_varpool_node_for_identifier (tree id)
 537 {
 538   struct cgraph_varpool_node **slot;
 539
 540   if (TREE_CODE (id) != IDENTIFIER_NODE)
 541     abort ();
 542
 543   if (!cgraph_varpool_hash)
 544     return NULL;
 545
 546   slot = (struct cgraph_varpool_node **)
 547     htab_find_slot_with_hash (cgraph_varpool_hash, id,
 548                               IDENTIFIER_HASH_VALUE (id), NO_INSERT);
 549   if (!slot)
 550     return NULL;
 551   return *slot;
 552 }
 553
 554 /* Notify finalize_compilation_unit that given node is reachable
 555    or needed.  */
 556 void
 557 cgraph_varpool_mark_needed_node (struct cgraph_varpool_node *node)
 558 {
 559   if (!node->needed && node->finalized)
 560     {
 561       node->next_needed = cgraph_varpool_nodes_queue;
 562       cgraph_varpool_nodes_queue = node;
 563       notice_global_symbol (node->decl);
 564     }
 565   node->needed = 1;
 566 }
 567
 568 void
 569 cgraph_varpool_finalize_decl (tree decl)
 570 {
 571   struct cgraph_varpool_node *node = cgraph_varpool_node (decl);
 572
 573   /* The first declaration of a variable that comes through this function
 574      decides whether it is global (in C, has external linkage)
 575      or local (in C, has internal linkage).  So do nothing more
 576      if this function has already run.  */
 577   if (node->finalized)
 578     return;
 579   if (node->needed)
 580     {
 581       node->next_needed = cgraph_varpool_nodes_queue;
 582       cgraph_varpool_nodes_queue = node;
 583       notice_global_symbol (decl);
 584     }
 585   node->finalized = true;
 586
 587   if (/* Externally visible variables must be output.  The exception are
 588          COMDAT functions that must be output only when they are needed.  */
 589       (TREE_PUBLIC (decl) && !DECL_COMDAT (decl))
 590       /* Function whose name is output to the assembler file must be produced.
 591          It is possible to assemble the name later after finalizing the function
 592          and the fact is noticed in assemble_name then.  */
 593       || (DECL_ASSEMBLER_NAME_SET_P (decl)
 594           && TREE_SYMBOL_REFERENCED (DECL_ASSEMBLER_NAME (decl))))
 595     {
 596       cgraph_varpool_mark_needed_node (node);
 597     }
 598 }
 599
 600 bool
 601 cgraph_varpool_assemble_pending_decls (void)
 602 {
 603   bool changed = false;
 604
 605   while (cgraph_varpool_nodes_queue)
 606     {
 607       tree decl = cgraph_varpool_nodes_queue->decl;
 608       struct cgraph_varpool_node *node = cgraph_varpool_nodes_queue;
 609
 610       cgraph_varpool_nodes_queue = cgraph_varpool_nodes_queue->next_needed;
 611       if (!TREE_ASM_WRITTEN (decl))
 612         {
 613           assemble_variable (decl, 0, 1, 0);
 614           changed = true;
 615         }
 616       node->next_needed = NULL;
 617     }
 618   return changed;
 619 }
 620
 621 /* Return true when the DECL can possibly be inlined.  */
 622 bool
 623 cgraph_function_possibly_inlined_p (tree decl)
 624 {
 625   if (!cgraph_global_info_ready)
 626     return (DECL_INLINE (decl)
 627             && (!flag_really_no_inline
 628                 || (*lang_hooks.tree_inlining.disregard_inline_limits) (decl)));
 629   return cgraph_node (decl)->global.inlined;
 630 }
 631
 632 #include "gt-cgraph.h"