gcc/cgraph.c

   1 /* Callgraph handling code.
   2    Copyright (C) 2003 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
  38
  39 /* Hash table used to convert declarations into nodes.  */
  40 static GTY((param_is (struct cgraph_node))) htab_t cgraph_hash;
  41
  42 /* The linked list of cgraph nodes.  */
  43 struct cgraph_node *cgraph_nodes;
  44
  45 /* Queue of cgraph nodes scheduled to be lowered.  */
  46 struct cgraph_node *cgraph_nodes_queue;
  47
  48 /* Number of nodes in existence.  */
  49 int cgraph_n_nodes;
  50
  51 /* Set when whole unit has been analyzed so we can access global info.  */
  52 bool cgraph_global_info_ready = false;
  53
  54 /* Hash table used to convert declarations into nodes.  */
  55 static GTY((param_is (struct cgraph_varpool_node))) htab_t cgraph_varpool_hash;
  56
  57 /* Queue of cgraph nodes scheduled to be lowered and output.  */
  58 struct cgraph_varpool_node *cgraph_varpool_nodes_queue;
  59
  60 /* Number of nodes in existence.  */
  61 int cgraph_varpool_n_nodes;
  62
  63 /* The linked list of cgraph varpool nodes.  */
  64 static GTY(())  struct cgraph_varpool_node *cgraph_varpool_nodes;
  65
  66 static struct cgraph_edge *create_edge PARAMS ((struct cgraph_node *,
  67                                                 struct cgraph_node *));
  68 static void cgraph_remove_edge PARAMS ((struct cgraph_node *, struct cgraph_node *));
  69 static hashval_t hash_node PARAMS ((const void *));
  70 static int eq_node PARAMS ((const void *, const void *));
  71
  72 /* Returns a hash code for P.  */
  73
  74 static hashval_t
  75 hash_node (p)
  76      const void *p;
  77 {
  78   return ((hashval_t)
  79           IDENTIFIER_HASH_VALUE (DECL_ASSEMBLER_NAME
  80                                  (((struct cgraph_node *) p)->decl)));
  81 }
  82
  83 /* Returns nonzero if P1 and P2 are equal.  */
  84
  85 static int
  86 eq_node (p1, p2)
  87      const void *p1;
  88      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 (decl)
  97      tree decl;
  98 {
  99   struct cgraph_node *node;
 100   struct cgraph_node **slot;
 101
 102   if (TREE_CODE (decl) != FUNCTION_DECL)
 103     abort ();
 104
 105   if (!cgraph_hash)
 106     cgraph_hash = htab_create_ggc (10, hash_node, eq_node, NULL);
 107
 108   slot = (struct cgraph_node **)
 109     htab_find_slot_with_hash (cgraph_hash, DECL_ASSEMBLER_NAME (decl),
 110                               IDENTIFIER_HASH_VALUE
 111                                 (DECL_ASSEMBLER_NAME (decl)), 1);
 112   if (*slot)
 113     return *slot;
 114   node = ggc_alloc_cleared (sizeof (*node));
 115   node->decl = decl;
 116   node->next = cgraph_nodes;
 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 (id)
 135      tree id;
 136 {
 137   struct cgraph_node **slot;
 138
 139   if (TREE_CODE (id) != IDENTIFIER_NODE)
 140     abort ();
 141
 142   if (!cgraph_hash)
 143     return NULL;
 144
 145   slot = (struct cgraph_node **)
 146     htab_find_slot_with_hash (cgraph_hash, id,
 147                               IDENTIFIER_HASH_VALUE (id), 0);
 148   if (!slot)
 149     return NULL;
 150   return *slot;
 151 }
 152
 153 /* Create edge from CALLER to CALLEE in the cgraph.  */
 154
 155 static struct cgraph_edge *
 156 create_edge (caller, callee)
 157      struct cgraph_node *caller, *callee;
 158 {
 159   struct cgraph_edge *edge = ggc_alloc (sizeof (struct cgraph_edge));
 160
 161   edge->caller = caller;
 162   edge->callee = callee;
 163   edge->next_caller = callee->callers;
 164   edge->next_callee = caller->callees;
 165   caller->callees = edge;
 166   callee->callers = edge;
 167   return edge;
 168 }
 169
 170 /* Remove the edge from CALLER to CALLEE in the cgraph.  */
 171
 172 static void
 173 cgraph_remove_edge (caller, callee)
 174      struct cgraph_node *caller, *callee;
 175 {
 176   struct cgraph_edge **edge, **edge2;
 177
 178   for (edge = &callee->callers; *edge && (*edge)->caller != caller;
 179        edge = &((*edge)->next_caller))
 180     continue;
 181   if (!*edge)
 182     abort ();
 183   *edge = (*edge)->next_caller;
 184   for (edge2 = &caller->callees; *edge2 && (*edge2)->callee != callee;
 185        edge2 = &(*edge2)->next_callee)
 186     continue;
 187   if (!*edge2)
 188     abort ();
 189   *edge2 = (*edge2)->next_callee;
 190 }
 191
 192 /* Remove the node from cgraph.  */
 193
 194 void
 195 cgraph_remove_node (node)
 196      struct cgraph_node *node;
 197 {
 198   while (node->callers)
 199     cgraph_remove_edge (node->callers->caller, node);
 200   while (node->callees)
 201     cgraph_remove_edge (node, node->callees->callee);
 202   while (node->nested)
 203     cgraph_remove_node (node->nested);
 204   if (node->origin)
 205     {
 206       struct cgraph_node **node2 = &node->origin->nested;
 207
 208       while (*node2 != node)
 209         node2 = &(*node2)->next_nested;
 210       *node2 = node->next_nested;
 211     }
 212   if (node->previous)
 213     node->previous->next = node->next;
 214   else
 215     cgraph_nodes = node;
 216   if (node->next)
 217     node->next->previous = node->previous;
 218   DECL_SAVED_TREE (node->decl) = NULL;
 219   /* Do not free the structure itself so the walk over chain can continue.  */
 220 }
 221
 222 /* Notify finalize_compilation_unit that given node is reachable
 223    or needed.  */
 224 void
 225 cgraph_mark_needed_node (node, needed)
 226      struct cgraph_node *node;
 227      int needed;
 228 {
 229   if (needed)
 230     {
 231       node->needed = 1;
 232     }
 233   if (!node->reachable)
 234     {
 235       node->reachable = 1;
 236       if (DECL_SAVED_TREE (node->decl))
 237         {
 238           node->next_needed = cgraph_nodes_queue;
 239           cgraph_nodes_queue = node;
 240         }
 241     }
 242 }
 243
 244
 245 /* Record call from CALLER to CALLEE  */
 246
 247 struct cgraph_edge *
 248 cgraph_record_call (caller, callee)
 249      tree caller, callee;
 250 {
 251   return create_edge (cgraph_node (caller), cgraph_node (callee));
 252 }
 253
 254 void
 255 cgraph_remove_call (caller, callee)
 256      tree caller, callee;
 257 {
 258   cgraph_remove_edge (cgraph_node (caller), cgraph_node (callee));
 259 }
 260
 261 /* Return true when CALLER_DECL calls CALLEE_DECL.  */
 262
 263 bool
 264 cgraph_calls_p (caller_decl, callee_decl)
 265      tree caller_decl, callee_decl;
 266 {
 267   struct cgraph_node *caller = cgraph_node (caller_decl);
 268   struct cgraph_node *callee = cgraph_node (callee_decl);
 269   struct cgraph_edge *edge;
 270
 271   for (edge = callee->callers; edge && (edge)->caller != caller;
 272        edge = (edge->next_caller))
 273     continue;
 274   return edge != NULL;
 275 }
 276
 277 /* Return local info for the compiled function.  */
 278
 279 struct cgraph_local_info *
 280 cgraph_local_info (decl)
 281      tree decl;
 282 {
 283   struct cgraph_node *node;
 284   if (TREE_CODE (decl) != FUNCTION_DECL)
 285     abort ();
 286   node = cgraph_node (decl);
 287   return &node->local;
 288 }
 289
 290 /* Return local info for the compiled function.  */
 291
 292 struct cgraph_global_info *
 293 cgraph_global_info (decl)
 294      tree decl;
 295 {
 296   struct cgraph_node *node;
 297   if (TREE_CODE (decl) != FUNCTION_DECL || !cgraph_global_info_ready)
 298     abort ();
 299   node = cgraph_node (decl);
 300   return &node->global;
 301 }
 302
 303 /* Return local info for the compiled function.  */
 304
 305 struct cgraph_rtl_info *
 306 cgraph_rtl_info (decl)
 307      tree decl;
 308 {
 309   struct cgraph_node *node;
 310   if (TREE_CODE (decl) != FUNCTION_DECL)
 311     abort ();
 312   node = cgraph_node (decl);
 313   if (decl != current_function_decl
 314       && !TREE_ASM_WRITTEN (node->decl))
 315     return NULL;
 316   return &node->rtl;
 317 }
 318
 319
 320 /* Dump the callgraph.  */
 321
 322 void
 323 dump_cgraph (f)
 324      FILE *f;
 325 {
 326   struct cgraph_node *node;
 327
 328   fprintf (f, "\nCallgraph:\n\n");
 329   for (node = cgraph_nodes; node; node = node->next)
 330     {
 331       struct cgraph_edge *edge;
 332       fprintf (f, "%s", IDENTIFIER_POINTER (DECL_NAME (node->decl)));
 333       if (node->origin)
 334         fprintf (f, " nested in: %s",
 335                  IDENTIFIER_POINTER (DECL_NAME (node->origin->decl)));
 336       if (node->needed)
 337         fprintf (f, " needed");
 338       else if (node->reachable)
 339         fprintf (f, " reachable");
 340       if (DECL_SAVED_TREE (node->decl))
 341         fprintf (f, " tree");
 342
 343       fprintf (f, "\n  called by :");
 344       for (edge = node->callers; edge; edge = edge->next_caller)
 345         fprintf (f, "%s ",
 346                  IDENTIFIER_POINTER (DECL_NAME (edge->caller->decl)));
 347
 348       fprintf (f, "\n  calls: ");
 349       for (edge = node->callees; edge; edge = edge->next_callee)
 350         fprintf (f, "%s ",
 351                  IDENTIFIER_POINTER (DECL_NAME (edge->callee->decl)));
 352       fprintf (f, "\n");
 353     }
 354 }
 355
 356 /* Returns a hash code for P.  */
 357
 358 static hashval_t
 359 cgraph_varpool_hash_node (const PTR p)
 360 {
 361   return ((hashval_t)
 362           IDENTIFIER_HASH_VALUE (DECL_ASSEMBLER_NAME
 363                                  (((struct cgraph_varpool_node *) p)->decl)));
 364 }
 365
 366 /* Returns nonzero if P1 and P2 are equal.  */
 367
 368 static int
 369 eq_cgraph_varpool_node (const PTR p1, const PTR p2)
 370 {
 371   return ((DECL_ASSEMBLER_NAME (((struct cgraph_varpool_node *) p1)->decl)) ==
 372           (tree) p2);
 373 }
 374
 375 /* Return cgraph_varpool node assigned to DECL.  Create new one when needed.  */
 376 struct cgraph_varpool_node *
 377 cgraph_varpool_node (tree decl)
 378 {
 379   struct cgraph_varpool_node *node;
 380   struct cgraph_varpool_node **slot;
 381
 382   if (!DECL_P (decl) || TREE_CODE (decl) == FUNCTION_DECL)
 383     abort ();
 384
 385   if (!cgraph_varpool_hash)
 386     cgraph_varpool_hash = htab_create_ggc (10, cgraph_varpool_hash_node,
 387                                            eq_cgraph_varpool_node, NULL);
 388
 389
 390   slot = (struct cgraph_varpool_node **)
 391     htab_find_slot_with_hash (cgraph_varpool_hash, DECL_ASSEMBLER_NAME (decl),
 392                               IDENTIFIER_HASH_VALUE (DECL_ASSEMBLER_NAME (decl)),
 393                               1);
 394   if (*slot)
 395     return *slot;
 396   node = ggc_alloc_cleared (sizeof (*node));
 397   node->decl = decl;
 398   cgraph_varpool_n_nodes++;
 399   cgraph_varpool_nodes = node;
 400   *slot = node;
 401   return node;
 402 }
 403
 404 /* Try to find existing function for identifier ID.  */
 405 struct cgraph_varpool_node *
 406 cgraph_varpool_node_for_identifier (tree id)
 407 {
 408   struct cgraph_varpool_node **slot;
 409
 410   if (TREE_CODE (id) != IDENTIFIER_NODE)
 411     abort ();
 412
 413   if (!cgraph_varpool_hash)
 414     return NULL;
 415
 416   slot = (struct cgraph_varpool_node **)
 417     htab_find_slot_with_hash (cgraph_varpool_hash, id,
 418                               IDENTIFIER_HASH_VALUE (id), 0);
 419   if (!slot)
 420     return NULL;
 421   return *slot;
 422 }
 423
 424 /* Notify finalize_compilation_unit that given node is reachable
 425    or needed.  */
 426 void
 427 cgraph_varpool_mark_needed_node (struct cgraph_varpool_node *node)
 428 {
 429   if (!node->needed && node->finalized)
 430     {
 431       node->next_needed = cgraph_varpool_nodes_queue;
 432       cgraph_varpool_nodes_queue = node;
 433     }
 434   node->needed = 1;
 435 }
 436
 437 void
 438 cgraph_varpool_finalize_decl (tree decl)
 439 {
 440   struct cgraph_varpool_node *node = cgraph_varpool_node (decl);
 441
 442   if (node->needed && !node->finalized)
 443     {
 444       node->next_needed = cgraph_varpool_nodes_queue;
 445       cgraph_varpool_nodes_queue = node;
 446     }
 447   node->finalized = true;
 448
 449   if (/* Externally visible variables must be output.  The exception are
 450          COMDAT functions that must be output only when they are needed.  */
 451       (TREE_PUBLIC (decl) && !DECL_COMDAT (decl))
 452       /* Function whose name is output to the assembler file must be produced.
 453          It is possible to assemble the name later after finalizing the function
 454          and the fact is noticed in assemble_name then.  */
 455       || (DECL_ASSEMBLER_NAME_SET_P (decl)
 456           && TREE_SYMBOL_REFERENCED (DECL_ASSEMBLER_NAME (decl))))
 457     {
 458       cgraph_varpool_mark_needed_node (node);
 459     }
 460 }
 461
 462 bool
 463 cgraph_varpool_assemble_pending_decls ()
 464 {
 465   bool changed = false;
 466
 467   while (cgraph_varpool_nodes_queue)
 468     {
 469       tree decl = cgraph_varpool_nodes_queue->decl;
 470       struct cgraph_varpool_node *node = cgraph_varpool_nodes_queue;
 471
 472       cgraph_varpool_nodes_queue = cgraph_varpool_nodes_queue->next_needed;
 473       if (!TREE_ASM_WRITTEN (decl))
 474         {
 475           assemble_variable (decl, 0, 1, 0);
 476           changed = true;
 477         }
 478       node->next_needed = NULL;
 479     }
 480   return changed;
 481 }
 482
 483
 484 #include "gt-cgraph.h"