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