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 /* Return name of the node used in debug output.  */
 320 const char *
 321 cgraph_node_name (node)
 322      struct cgraph_node *node;
 323 {
 324   return (*lang_hooks.decl_printable_name) (node->decl, 2);
 325 }
 326
 327 /* Dump the callgraph.  */
 328
 329 void
 330 dump_cgraph (f)
 331      FILE *f;
 332 {
 333   struct cgraph_node *node;
 334
 335   fprintf (f, "\nCallgraph:\n\n");
 336   for (node = cgraph_nodes; node; node = node->next)
 337     {
 338       struct cgraph_edge *edge;
 339       fprintf (f, "%s", cgraph_node_name (node));
 340       if (node->origin)
 341         fprintf (f, " nested in: %s", cgraph_node_name (node->origin));
 342       if (node->needed)
 343         fprintf (f, " needed");
 344       else if (node->reachable)
 345         fprintf (f, " reachable");
 346       if (DECL_SAVED_TREE (node->decl))
 347         fprintf (f, " tree");
 348
 349       fprintf (f, "\n  called by :");
 350       for (edge = node->callers; edge; edge = edge->next_caller)
 351         fprintf (f, "%s ", cgraph_node_name (edge->caller));
 352
 353       fprintf (f, "\n  calls: ");
 354       for (edge = node->callees; edge; edge = edge->next_callee)
 355         fprintf (f, "%s ", cgraph_node_name (edge->callee));
 356       fprintf (f, "\n");
 357     }
 358 }
 359
 360 /* Returns a hash code for P.  */
 361
 362 static hashval_t
 363 cgraph_varpool_hash_node (const PTR p)
 364 {
 365   return ((hashval_t)
 366           IDENTIFIER_HASH_VALUE (DECL_ASSEMBLER_NAME
 367                                  (((struct cgraph_varpool_node *) p)->decl)));
 368 }
 369
 370 /* Returns nonzero if P1 and P2 are equal.  */
 371
 372 static int
 373 eq_cgraph_varpool_node (const PTR p1, const PTR p2)
 374 {
 375   return ((DECL_ASSEMBLER_NAME (((struct cgraph_varpool_node *) p1)->decl)) ==
 376           (tree) p2);
 377 }
 378
 379 /* Return cgraph_varpool node assigned to DECL.  Create new one when needed.  */
 380 struct cgraph_varpool_node *
 381 cgraph_varpool_node (tree decl)
 382 {
 383   struct cgraph_varpool_node *node;
 384   struct cgraph_varpool_node **slot;
 385
 386   if (!DECL_P (decl) || TREE_CODE (decl) == FUNCTION_DECL)
 387     abort ();
 388
 389   if (!cgraph_varpool_hash)
 390     cgraph_varpool_hash = htab_create_ggc (10, cgraph_varpool_hash_node,
 391                                            eq_cgraph_varpool_node, NULL);
 392
 393
 394   slot = (struct cgraph_varpool_node **)
 395     htab_find_slot_with_hash (cgraph_varpool_hash, DECL_ASSEMBLER_NAME (decl),
 396                               IDENTIFIER_HASH_VALUE (DECL_ASSEMBLER_NAME (decl)),
 397                               1);
 398   if (*slot)
 399     return *slot;
 400   node = ggc_alloc_cleared (sizeof (*node));
 401   node->decl = decl;
 402   cgraph_varpool_n_nodes++;
 403   cgraph_varpool_nodes = node;
 404   *slot = node;
 405   return node;
 406 }
 407
 408 /* Try to find existing function for identifier ID.  */
 409 struct cgraph_varpool_node *
 410 cgraph_varpool_node_for_identifier (tree id)
 411 {
 412   struct cgraph_varpool_node **slot;
 413
 414   if (TREE_CODE (id) != IDENTIFIER_NODE)
 415     abort ();
 416
 417   if (!cgraph_varpool_hash)
 418     return NULL;
 419
 420   slot = (struct cgraph_varpool_node **)
 421     htab_find_slot_with_hash (cgraph_varpool_hash, id,
 422                               IDENTIFIER_HASH_VALUE (id), 0);
 423   if (!slot)
 424     return NULL;
 425   return *slot;
 426 }
 427
 428 /* Notify finalize_compilation_unit that given node is reachable
 429    or needed.  */
 430 void
 431 cgraph_varpool_mark_needed_node (struct cgraph_varpool_node *node)
 432 {
 433   if (!node->needed && node->finalized)
 434     {
 435       node->next_needed = cgraph_varpool_nodes_queue;
 436       cgraph_varpool_nodes_queue = node;
 437     }
 438   node->needed = 1;
 439 }
 440
 441 void
 442 cgraph_varpool_finalize_decl (tree decl)
 443 {
 444   struct cgraph_varpool_node *node = cgraph_varpool_node (decl);
 445
 446   if (node->needed && !node->finalized)
 447     {
 448       node->next_needed = cgraph_varpool_nodes_queue;
 449       cgraph_varpool_nodes_queue = node;
 450     }
 451   node->finalized = true;
 452
 453   if (/* Externally visible variables must be output.  The exception are
 454          COMDAT functions that must be output only when they are needed.  */
 455       (TREE_PUBLIC (decl) && !DECL_COMDAT (decl))
 456       /* Function whose name is output to the assembler file must be produced.
 457          It is possible to assemble the name later after finalizing the function
 458          and the fact is noticed in assemble_name then.  */
 459       || (DECL_ASSEMBLER_NAME_SET_P (decl)
 460           && TREE_SYMBOL_REFERENCED (DECL_ASSEMBLER_NAME (decl))))
 461     {
 462       cgraph_varpool_mark_needed_node (node);
 463     }
 464 }
 465
 466 bool
 467 cgraph_varpool_assemble_pending_decls ()
 468 {
 469   bool changed = false;
 470
 471   while (cgraph_varpool_nodes_queue)
 472     {
 473       tree decl = cgraph_varpool_nodes_queue->decl;
 474       struct cgraph_varpool_node *node = cgraph_varpool_nodes_queue;
 475
 476       cgraph_varpool_nodes_queue = cgraph_varpool_nodes_queue->next_needed;
 477       if (!TREE_ASM_WRITTEN (decl))
 478         {
 479           assemble_variable (decl, 0, 1, 0);
 480           changed = true;
 481         }
 482       node->next_needed = NULL;
 483     }
 484   return changed;
 485 }
 486
 487
 488 #include "gt-cgraph.h"