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_caller)
 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     {
 244       node->needed = 1;
 245     }
 246   if (!node->reachable)
 247     {
 248       node->reachable = 1;
 249       if (DECL_SAVED_TREE (node->decl))
 250         {
 251           node->next_needed = cgraph_nodes_queue;
 252           cgraph_nodes_queue = node;
 253         }
 254     }
 255 }
 256
 257
 258 /* Record call from CALLER to CALLEE  */
 259
 260 struct cgraph_edge *
 261 cgraph_record_call (tree caller, tree callee)
 262 {
 263   return create_edge (cgraph_node (caller), cgraph_node (callee));
 264 }
 265
 266 void
 267 cgraph_remove_call (tree caller, tree callee)
 268 {
 269   cgraph_remove_edge (cgraph_node (caller), cgraph_node (callee));
 270 }
 271
 272 /* Return true when CALLER_DECL calls CALLEE_DECL.  */
 273
 274 bool
 275 cgraph_calls_p (tree caller_decl, tree 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 (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 (tree decl)
 303 {
 304   struct cgraph_node *node;
 305   if (TREE_CODE (decl) != FUNCTION_DECL || !cgraph_global_info_ready)
 306     abort ();
 307   node = cgraph_node (decl);
 308   return &node->global;
 309 }
 310
 311 /* Return local info for the compiled function.  */
 312
 313 struct cgraph_rtl_info *
 314 cgraph_rtl_info (tree decl)
 315 {
 316   struct cgraph_node *node;
 317   if (TREE_CODE (decl) != FUNCTION_DECL)
 318     abort ();
 319   node = cgraph_node (decl);
 320   if (decl != current_function_decl
 321       && !TREE_ASM_WRITTEN (node->decl))
 322     return NULL;
 323   return &node->rtl;
 324 }
 325
 326 /* Return name of the node used in debug output.  */
 327 const char *
 328 cgraph_node_name (struct cgraph_node *node)
 329 {
 330   return (*lang_hooks.decl_printable_name) (node->decl, 2);
 331 }
 332
 333 /* Dump the callgraph.  */
 334
 335 void
 336 dump_cgraph (FILE *f)
 337 {
 338   struct cgraph_node *node;
 339
 340   fprintf (f, "\nCallgraph:\n\n");
 341   for (node = cgraph_nodes; node; node = node->next)
 342     {
 343       struct cgraph_edge *edge;
 344       fprintf (f, "%s", cgraph_node_name (node));
 345       if (node->local.self_insns)
 346         fprintf (f, " %i insns", node->local.self_insns);
 347       if (node->origin)
 348         fprintf (f, " nested in: %s", cgraph_node_name (node->origin));
 349       if (node->needed)
 350         fprintf (f, " needed");
 351       else if (node->reachable)
 352         fprintf (f, " reachable");
 353       if (DECL_SAVED_TREE (node->decl))
 354         fprintf (f, " tree");
 355
 356       if (node->local.disgread_inline_limits)
 357         fprintf (f, " always_inline");
 358       else if (node->local.inlinable)
 359         fprintf (f, " inlinable");
 360       if (node->global.insns && node->global.insns != node->local.self_insns)
 361         fprintf (f, " %i insns after inlining", node->global.insns);
 362       if (node->global.cloned_times > 1)
 363         fprintf (f, " cloned %ix", node->global.cloned_times);
 364       if (node->global.calls)
 365         fprintf (f, " %i calls", node->global.calls);
 366
 367       fprintf (f, "\n  called by :");
 368       for (edge = node->callers; edge; edge = edge->next_caller)
 369         {
 370           fprintf (f, "%s ", cgraph_node_name (edge->caller));
 371           if (edge->inline_call)
 372             fprintf(f, "(inlined) ");
 373         }
 374
 375       fprintf (f, "\n  calls: ");
 376       for (edge = node->callees; edge; edge = edge->next_callee)
 377         {
 378           fprintf (f, "%s ", cgraph_node_name (edge->callee));
 379           if (edge->inline_call)
 380             fprintf(f, "(inlined) ");
 381         }
 382       fprintf (f, "\n");
 383     }
 384 }
 385
 386 /* Returns a hash code for P.  */
 387
 388 static hashval_t
 389 cgraph_varpool_hash_node (const void *p)
 390 {
 391   return ((hashval_t)
 392           IDENTIFIER_HASH_VALUE (DECL_ASSEMBLER_NAME
 393                                  (((struct cgraph_varpool_node *) p)->decl)));
 394 }
 395
 396 /* Returns nonzero if P1 and P2 are equal.  */
 397
 398 static int
 399 eq_cgraph_varpool_node (const void *p1, const void *p2)
 400 {
 401   return ((DECL_ASSEMBLER_NAME (((struct cgraph_varpool_node *) p1)->decl)) ==
 402           (tree) p2);
 403 }
 404
 405 /* Return cgraph_varpool node assigned to DECL.  Create new one when needed.  */
 406 struct cgraph_varpool_node *
 407 cgraph_varpool_node (tree decl)
 408 {
 409   struct cgraph_varpool_node *node;
 410   struct cgraph_varpool_node **slot;
 411
 412   if (!DECL_P (decl) || TREE_CODE (decl) == FUNCTION_DECL)
 413     abort ();
 414
 415   if (!cgraph_varpool_hash)
 416     cgraph_varpool_hash = htab_create_ggc (10, cgraph_varpool_hash_node,
 417                                            eq_cgraph_varpool_node, NULL);
 418
 419
 420   slot = (struct cgraph_varpool_node **)
 421     htab_find_slot_with_hash (cgraph_varpool_hash, DECL_ASSEMBLER_NAME (decl),
 422                               IDENTIFIER_HASH_VALUE (DECL_ASSEMBLER_NAME (decl)),
 423                               1);
 424   if (*slot)
 425     return *slot;
 426   node = ggc_alloc_cleared (sizeof (*node));
 427   node->decl = decl;
 428   cgraph_varpool_n_nodes++;
 429   cgraph_varpool_nodes = node;
 430   *slot = node;
 431   return node;
 432 }
 433
 434 /* Try to find existing function for identifier ID.  */
 435 struct cgraph_varpool_node *
 436 cgraph_varpool_node_for_identifier (tree id)
 437 {
 438   struct cgraph_varpool_node **slot;
 439
 440   if (TREE_CODE (id) != IDENTIFIER_NODE)
 441     abort ();
 442
 443   if (!cgraph_varpool_hash)
 444     return NULL;
 445
 446   slot = (struct cgraph_varpool_node **)
 447     htab_find_slot_with_hash (cgraph_varpool_hash, id,
 448                               IDENTIFIER_HASH_VALUE (id), 0);
 449   if (!slot)
 450     return NULL;
 451   return *slot;
 452 }
 453
 454 /* Notify finalize_compilation_unit that given node is reachable
 455    or needed.  */
 456 void
 457 cgraph_varpool_mark_needed_node (struct cgraph_varpool_node *node)
 458 {
 459   if (!node->needed && node->finalized)
 460     {
 461       node->next_needed = cgraph_varpool_nodes_queue;
 462       cgraph_varpool_nodes_queue = node;
 463     }
 464   node->needed = 1;
 465 }
 466
 467 void
 468 cgraph_varpool_finalize_decl (tree decl)
 469 {
 470   struct cgraph_varpool_node *node = cgraph_varpool_node (decl);
 471
 472   if (node->needed && !node->finalized)
 473     {
 474       node->next_needed = cgraph_varpool_nodes_queue;
 475       cgraph_varpool_nodes_queue = node;
 476     }
 477   node->finalized = true;
 478
 479   if (/* Externally visible variables must be output.  The exception are
 480          COMDAT functions that must be output only when they are needed.  */
 481       (TREE_PUBLIC (decl) && !DECL_COMDAT (decl))
 482       /* Function whose name is output to the assembler file must be produced.
 483          It is possible to assemble the name later after finalizing the function
 484          and the fact is noticed in assemble_name then.  */
 485       || (DECL_ASSEMBLER_NAME_SET_P (decl)
 486           && TREE_SYMBOL_REFERENCED (DECL_ASSEMBLER_NAME (decl))))
 487     {
 488       cgraph_varpool_mark_needed_node (node);
 489     }
 490 }
 491
 492 bool
 493 cgraph_varpool_assemble_pending_decls (void)
 494 {
 495   bool changed = false;
 496
 497   while (cgraph_varpool_nodes_queue)
 498     {
 499       tree decl = cgraph_varpool_nodes_queue->decl;
 500       struct cgraph_varpool_node *node = cgraph_varpool_nodes_queue;
 501
 502       cgraph_varpool_nodes_queue = cgraph_varpool_nodes_queue->next_needed;
 503       if (!TREE_ASM_WRITTEN (decl))
 504         {
 505           assemble_variable (decl, 0, 1, 0);
 506           changed = true;
 507         }
 508       node->next_needed = NULL;
 509     }
 510   return changed;
 511 }
 512
 513
 514 #include "gt-cgraph.h"