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