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 /* Maximal uid used in cgraph nodes.  */
  52 int cgraph_max_uid;
  53
  54 /* Set when whole unit has been analyzed so we can access global info.  */
  55 bool cgraph_global_info_ready = false;
  56
  57 /* Hash table used to convert declarations into nodes.  */
  58 static GTY((param_is (struct cgraph_varpool_node))) htab_t cgraph_varpool_hash;
  59
  60 /* Queue of cgraph nodes scheduled to be lowered and output.  */
  61 struct cgraph_varpool_node *cgraph_varpool_nodes_queue;
  62
  63 /* Number of nodes in existence.  */
  64 int cgraph_varpool_n_nodes;
  65
  66 /* The linked list of cgraph varpool nodes.  */
  67 static GTY(())  struct cgraph_varpool_node *cgraph_varpool_nodes;
  68
  69 static struct cgraph_edge *create_edge (struct cgraph_node *,
  70                                         struct cgraph_node *);
  71 static void cgraph_remove_edge (struct cgraph_node *, 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)), 1);
 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), 0);
 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   edge->inline_call = false;
 161   /* At the moment we don't associate calls with specific CALL_EXPRs
 162      as we probably ought to, so we must preserve inline_call flags to
 163      be the same in all copies of the same edge.  */
 164   if (cgraph_global_info_ready)
 165     for (edge2 = caller->callees; edge2; edge2 = edge2->next_callee)
 166       if (edge2->callee == callee)
 167         {
 168           edge->inline_call = edge2->inline_call;
 169           break;
 170         }
 171
 172   edge->caller = caller;
 173   edge->callee = callee;
 174   edge->next_caller = callee->callers;
 175   edge->next_callee = caller->callees;
 176   caller->callees = edge;
 177   callee->callers = edge;
 178   return edge;
 179 }
 180
 181 /* Remove the edge from CALLER to CALLEE in the cgraph.  */
 182
 183 static void
 184 cgraph_remove_edge (struct cgraph_node *caller, struct cgraph_node *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 (struct cgraph_node *node)
 206 {
 207   void **slot;
 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   slot =
 230     htab_find_slot_with_hash (cgraph_hash, DECL_ASSEMBLER_NAME (node->decl),
 231                               IDENTIFIER_HASH_VALUE (DECL_ASSEMBLER_NAME
 232                                                      (node->decl)), 1);
 233   htab_clear_slot (cgraph_hash, slot);
 234   /* Do not free the structure itself so the walk over chain can continue.  */
 235 }
 236
 237 /* Notify finalize_compilation_unit that given node is reachable
 238    or needed.  */
 239 void
 240 cgraph_mark_needed_node (struct cgraph_node *node, int needed)
 241 {
 242   if (needed)
 243     node->needed = 1;
 244
 245   if (!node->reachable && DECL_SAVED_TREE (node->decl))
 246     {
 247       node->reachable = 1;
 248
 249       node->next_needed = cgraph_nodes_queue;
 250       cgraph_nodes_queue = node;
 251
 252       /* At the moment frontend automatically emits all nested functions.  */
 253       if (node->nested)
 254         {
 255           struct cgraph_node *node2;
 256
 257           for (node2 = node->nested; node2; node2 = node2->next_nested)
 258             if (!node2->reachable)
 259               cgraph_mark_needed_node (node2, 0);
 260         }
 261     }
 262 }
 263
 264
 265 /* Record call from CALLER to CALLEE  */
 266
 267 struct cgraph_edge *
 268 cgraph_record_call (tree caller, tree callee)
 269 {
 270   return create_edge (cgraph_node (caller), cgraph_node (callee));
 271 }
 272
 273 void
 274 cgraph_remove_call (tree caller, tree callee)
 275 {
 276   cgraph_remove_edge (cgraph_node (caller), cgraph_node (callee));
 277 }
 278
 279 /* Return true when CALLER_DECL calls CALLEE_DECL.  */
 280
 281 bool
 282 cgraph_calls_p (tree caller_decl, tree callee_decl)
 283 {
 284   struct cgraph_node *caller = cgraph_node (caller_decl);
 285   struct cgraph_node *callee = cgraph_node (callee_decl);
 286   struct cgraph_edge *edge;
 287
 288   for (edge = callee->callers; edge && (edge)->caller != caller;
 289        edge = (edge->next_caller))
 290     continue;
 291   return edge != NULL;
 292 }
 293
 294 /* Return local info for the compiled function.  */
 295
 296 struct cgraph_local_info *
 297 cgraph_local_info (tree decl)
 298 {
 299   struct cgraph_node *node;
 300   if (TREE_CODE (decl) != FUNCTION_DECL)
 301     abort ();
 302   node = cgraph_node (decl);
 303   return &node->local;
 304 }
 305
 306 /* Return local info for the compiled function.  */
 307
 308 struct cgraph_global_info *
 309 cgraph_global_info (tree decl)
 310 {
 311   struct cgraph_node *node;
 312   if (TREE_CODE (decl) != FUNCTION_DECL || !cgraph_global_info_ready)
 313     abort ();
 314   node = cgraph_node (decl);
 315   return &node->global;
 316 }
 317
 318 /* Return local info for the compiled function.  */
 319
 320 struct cgraph_rtl_info *
 321 cgraph_rtl_info (tree decl)
 322 {
 323   struct cgraph_node *node;
 324   if (TREE_CODE (decl) != FUNCTION_DECL)
 325     abort ();
 326   node = cgraph_node (decl);
 327   if (decl != current_function_decl
 328       && !TREE_ASM_WRITTEN (node->decl))
 329     return NULL;
 330   return &node->rtl;
 331 }
 332
 333 /* Return name of the node used in debug output.  */
 334 const char *
 335 cgraph_node_name (struct cgraph_node *node)
 336 {
 337   return (*lang_hooks.decl_printable_name) (node->decl, 2);
 338 }
 339
 340 /* Dump the callgraph.  */
 341
 342 void
 343 dump_cgraph (FILE *f)
 344 {
 345   struct cgraph_node *node;
 346
 347   fprintf (f, "\nCallgraph:\n\n");
 348   for (node = cgraph_nodes; node; node = node->next)
 349     {
 350       struct cgraph_edge *edge;
 351       fprintf (f, "%s", cgraph_node_name (node));
 352       if (node->local.self_insns)
 353         fprintf (f, " %i insns", node->local.self_insns);
 354       if (node->origin)
 355         fprintf (f, " nested in: %s", cgraph_node_name (node->origin));
 356       if (node->needed)
 357         fprintf (f, " needed");
 358       else if (node->reachable)
 359         fprintf (f, " reachable");
 360       if (DECL_SAVED_TREE (node->decl))
 361         fprintf (f, " tree");
 362
 363       if (node->local.disregard_inline_limits)
 364         fprintf (f, " always_inline");
 365       else if (node->local.inlinable)
 366         fprintf (f, " inlinable");
 367       if (node->global.insns && node->global.insns != node->local.self_insns)
 368         fprintf (f, " %i insns after inlining", node->global.insns);
 369       if (node->global.cloned_times > 1)
 370         fprintf (f, " cloned %ix", node->global.cloned_times);
 371
 372       fprintf (f, "\n  called by :");
 373       for (edge = node->callers; edge; edge = edge->next_caller)
 374         {
 375           fprintf (f, "%s ", cgraph_node_name (edge->caller));
 376           if (edge->inline_call)
 377             fprintf(f, "(inlined) ");
 378         }
 379
 380       fprintf (f, "\n  calls: ");
 381       for (edge = node->callees; edge; edge = edge->next_callee)
 382         {
 383           fprintf (f, "%s ", cgraph_node_name (edge->callee));
 384           if (edge->inline_call)
 385             fprintf(f, "(inlined) ");
 386         }
 387       fprintf (f, "\n");
 388     }
 389 }
 390
 391 /* Returns a hash code for P.  */
 392
 393 static hashval_t
 394 cgraph_varpool_hash_node (const void *p)
 395 {
 396   return ((hashval_t)
 397           IDENTIFIER_HASH_VALUE (DECL_ASSEMBLER_NAME
 398                                  (((struct cgraph_varpool_node *) p)->decl)));
 399 }
 400
 401 /* Returns nonzero if P1 and P2 are equal.  */
 402
 403 static int
 404 eq_cgraph_varpool_node (const void *p1, const void *p2)
 405 {
 406   return ((DECL_ASSEMBLER_NAME (((struct cgraph_varpool_node *) p1)->decl)) ==
 407           (tree) p2);
 408 }
 409
 410 /* Return cgraph_varpool node assigned to DECL.  Create new one when needed.  */
 411 struct cgraph_varpool_node *
 412 cgraph_varpool_node (tree decl)
 413 {
 414   struct cgraph_varpool_node *node;
 415   struct cgraph_varpool_node **slot;
 416
 417   if (!DECL_P (decl) || TREE_CODE (decl) == FUNCTION_DECL)
 418     abort ();
 419
 420   if (!cgraph_varpool_hash)
 421     cgraph_varpool_hash = htab_create_ggc (10, cgraph_varpool_hash_node,
 422                                            eq_cgraph_varpool_node, NULL);
 423
 424
 425   slot = (struct cgraph_varpool_node **)
 426     htab_find_slot_with_hash (cgraph_varpool_hash, DECL_ASSEMBLER_NAME (decl),
 427                               IDENTIFIER_HASH_VALUE (DECL_ASSEMBLER_NAME (decl)),
 428                               1);
 429   if (*slot)
 430     return *slot;
 431   node = ggc_alloc_cleared (sizeof (*node));
 432   node->decl = decl;
 433   cgraph_varpool_n_nodes++;
 434   cgraph_varpool_nodes = node;
 435   *slot = node;
 436   return node;
 437 }
 438
 439 /* Try to find existing function for identifier ID.  */
 440 struct cgraph_varpool_node *
 441 cgraph_varpool_node_for_identifier (tree id)
 442 {
 443   struct cgraph_varpool_node **slot;
 444
 445   if (TREE_CODE (id) != IDENTIFIER_NODE)
 446     abort ();
 447
 448   if (!cgraph_varpool_hash)
 449     return NULL;
 450
 451   slot = (struct cgraph_varpool_node **)
 452     htab_find_slot_with_hash (cgraph_varpool_hash, id,
 453                               IDENTIFIER_HASH_VALUE (id), 0);
 454   if (!slot)
 455     return NULL;
 456   return *slot;
 457 }
 458
 459 /* Notify finalize_compilation_unit that given node is reachable
 460    or needed.  */
 461 void
 462 cgraph_varpool_mark_needed_node (struct cgraph_varpool_node *node)
 463 {
 464   if (!node->needed && node->finalized)
 465     {
 466       node->next_needed = cgraph_varpool_nodes_queue;
 467       cgraph_varpool_nodes_queue = node;
 468     }
 469   node->needed = 1;
 470 }
 471
 472 void
 473 cgraph_varpool_finalize_decl (tree decl)
 474 {
 475   struct cgraph_varpool_node *node = cgraph_varpool_node (decl);
 476
 477   if (node->needed && !node->finalized)
 478     {
 479       node->next_needed = cgraph_varpool_nodes_queue;
 480       cgraph_varpool_nodes_queue = node;
 481     }
 482   node->finalized = true;
 483
 484   if (/* Externally visible variables must be output.  The exception are
 485          COMDAT functions that must be output only when they are needed.  */
 486       (TREE_PUBLIC (decl) && !DECL_COMDAT (decl))
 487       /* Function whose name is output to the assembler file must be produced.
 488          It is possible to assemble the name later after finalizing the function
 489          and the fact is noticed in assemble_name then.  */
 490       || (DECL_ASSEMBLER_NAME_SET_P (decl)
 491           && TREE_SYMBOL_REFERENCED (DECL_ASSEMBLER_NAME (decl))))
 492     {
 493       cgraph_varpool_mark_needed_node (node);
 494     }
 495 }
 496
 497 bool
 498 cgraph_varpool_assemble_pending_decls (void)
 499 {
 500   bool changed = false;
 501
 502   while (cgraph_varpool_nodes_queue)
 503     {
 504       tree decl = cgraph_varpool_nodes_queue->decl;
 505       struct cgraph_varpool_node *node = cgraph_varpool_nodes_queue;
 506
 507       cgraph_varpool_nodes_queue = cgraph_varpool_nodes_queue->next_needed;
 508       if (!TREE_ASM_WRITTEN (decl))
 509         {
 510           assemble_variable (decl, 0, 1, 0);
 511           changed = true;
 512         }
 513       node->next_needed = NULL;
 514     }
 515   return changed;
 516 }
 517
 518
 519 #include "gt-cgraph.h"