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