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