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