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