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
 239 void
 240 cgraph_mark_reachable_node (struct cgraph_node *node)
 241 {
 242   if (!node->reachable && node->local.finalized)
 243     {
 244       notice_global_symbol (node->decl);
 245       node->reachable = 1;
 246
 247       node->next_needed = cgraph_nodes_queue;
 248       cgraph_nodes_queue = node;
 249
 250       /* At the moment frontend automatically emits all nested functions.  */
 251       if (node->nested)
 252         {
 253           struct cgraph_node *node2;
 254
 255           for (node2 = node->nested; node2; node2 = node2->next_nested)
 256             if (!node2->reachable)
 257               cgraph_mark_reachable_node (node2);
 258         }
 259     }
 260 }
 261
 262 /* Likewise indicate that a node is needed, i.e. reachable via some
 263    external means.  */
 264
 265 void
 266 cgraph_mark_needed_node (struct cgraph_node *node)
 267 {
 268   node->needed = 1;
 269   cgraph_mark_reachable_node (node);
 270 }
 271
 272 /* Record call from CALLER to CALLEE  */
 273
 274 struct cgraph_edge *
 275 cgraph_record_call (tree caller, tree callee)
 276 {
 277   return create_edge (cgraph_node (caller), cgraph_node (callee));
 278 }
 279
 280 void
 281 cgraph_remove_call (tree caller, tree callee)
 282 {
 283   cgraph_remove_edge (cgraph_node (caller), cgraph_node (callee));
 284 }
 285
 286 /* Return true when CALLER_DECL calls CALLEE_DECL.  */
 287
 288 bool
 289 cgraph_calls_p (tree caller_decl, tree callee_decl)
 290 {
 291   struct cgraph_node *caller = cgraph_node (caller_decl);
 292   struct cgraph_node *callee = cgraph_node (callee_decl);
 293   struct cgraph_edge *edge;
 294
 295   for (edge = callee->callers; edge && (edge)->caller != caller;
 296        edge = (edge->next_caller))
 297     continue;
 298   return edge != NULL;
 299 }
 300
 301 /* Return local info for the compiled function.  */
 302
 303 struct cgraph_local_info *
 304 cgraph_local_info (tree decl)
 305 {
 306   struct cgraph_node *node;
 307   if (TREE_CODE (decl) != FUNCTION_DECL)
 308     abort ();
 309   node = cgraph_node (decl);
 310   return &node->local;
 311 }
 312
 313 /* Return local info for the compiled function.  */
 314
 315 struct cgraph_global_info *
 316 cgraph_global_info (tree decl)
 317 {
 318   struct cgraph_node *node;
 319   if (TREE_CODE (decl) != FUNCTION_DECL || !cgraph_global_info_ready)
 320     abort ();
 321   node = cgraph_node (decl);
 322   return &node->global;
 323 }
 324
 325 /* Return local info for the compiled function.  */
 326
 327 struct cgraph_rtl_info *
 328 cgraph_rtl_info (tree decl)
 329 {
 330   struct cgraph_node *node;
 331   if (TREE_CODE (decl) != FUNCTION_DECL)
 332     abort ();
 333   node = cgraph_node (decl);
 334   if (decl != current_function_decl
 335       && !TREE_ASM_WRITTEN (node->decl))
 336     return NULL;
 337   return &node->rtl;
 338 }
 339
 340 /* Return name of the node used in debug output.  */
 341 const char *
 342 cgraph_node_name (struct cgraph_node *node)
 343 {
 344   return (*lang_hooks.decl_printable_name) (node->decl, 2);
 345 }
 346
 347 /* Dump the callgraph.  */
 348
 349 void
 350 dump_cgraph (FILE *f)
 351 {
 352   struct cgraph_node *node;
 353
 354   fprintf (f, "\nCallgraph:\n\n");
 355   for (node = cgraph_nodes; node; node = node->next)
 356     {
 357       struct cgraph_edge *edge;
 358       fprintf (f, "%s", cgraph_node_name (node));
 359       if (node->local.self_insns)
 360         fprintf (f, " %i insns", node->local.self_insns);
 361       if (node->origin)
 362         fprintf (f, " nested in: %s", cgraph_node_name (node->origin));
 363       if (node->needed)
 364         fprintf (f, " needed");
 365       else if (node->reachable)
 366         fprintf (f, " reachable");
 367       if (DECL_SAVED_TREE (node->decl))
 368         fprintf (f, " tree");
 369
 370       if (node->local.disregard_inline_limits)
 371         fprintf (f, " always_inline");
 372       else if (node->local.inlinable)
 373         fprintf (f, " inlinable");
 374       if (node->global.insns && node->global.insns != node->local.self_insns)
 375         fprintf (f, " %i insns after inlining", node->global.insns);
 376       if (node->global.cloned_times > 1)
 377         fprintf (f, " cloned %ix", node->global.cloned_times);
 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 void *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 void *p1, const void *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       notice_global_symbol (node->decl);
 476     }
 477   node->needed = 1;
 478 }
 479
 480 void
 481 cgraph_varpool_finalize_decl (tree decl)
 482 {
 483   struct cgraph_varpool_node *node = cgraph_varpool_node (decl);
 484
 485   /* The first declaration of a variable that comes through this function
 486      decides whether it is global (in C, has external linkage)
 487      or local (in C, has internal linkage).  So do nothing more
 488      if this function has already run.  */
 489   if (node->finalized)
 490     return;
 491   if (node->needed)
 492     {
 493       node->next_needed = cgraph_varpool_nodes_queue;
 494       cgraph_varpool_nodes_queue = node;
 495       notice_global_symbol (decl);
 496     }
 497   node->finalized = true;
 498
 499   if (/* Externally visible variables must be output.  The exception are
 500          COMDAT functions that must be output only when they are needed.  */
 501       (TREE_PUBLIC (decl) && !DECL_COMDAT (decl))
 502       /* Function whose name is output to the assembler file must be produced.
 503          It is possible to assemble the name later after finalizing the function
 504          and the fact is noticed in assemble_name then.  */
 505       || (DECL_ASSEMBLER_NAME_SET_P (decl)
 506           && TREE_SYMBOL_REFERENCED (DECL_ASSEMBLER_NAME (decl))))
 507     {
 508       cgraph_varpool_mark_needed_node (node);
 509     }
 510 }
 511
 512 bool
 513 cgraph_varpool_assemble_pending_decls (void)
 514 {
 515   bool changed = false;
 516
 517   while (cgraph_varpool_nodes_queue)
 518     {
 519       tree decl = cgraph_varpool_nodes_queue->decl;
 520       struct cgraph_varpool_node *node = cgraph_varpool_nodes_queue;
 521
 522       cgraph_varpool_nodes_queue = cgraph_varpool_nodes_queue->next_needed;
 523       if (!TREE_ASM_WRITTEN (decl))
 524         {
 525           assemble_variable (decl, 0, 1, 0);
 526           changed = true;
 527         }
 528       node->next_needed = NULL;
 529     }
 530   return changed;
 531 }
 532
 533
 534 #include "gt-cgraph.h"