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