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