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)), INSERT);
 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), NO_INSERT);
 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)), NO_INSERT);
 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, "callgraph:\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->global.insns && node->global.insns != node->local.self_insns)
 361         fprintf (f, " (%i after inlining)", node->global.insns);
 362       if (node->origin)
 363         fprintf (f, " nested in: %s", cgraph_node_name (node->origin));
 364       if (node->needed)
 365         fprintf (f, " needed");
 366       else if (node->reachable)
 367         fprintf (f, " reachable");
 368       if (DECL_SAVED_TREE (node->decl))
 369         fprintf (f, " tree");
 370
 371       if (node->local.local)
 372         fprintf (f, " local");
 373       if (node->local.disregard_inline_limits)
 374         fprintf (f, " always_inline");
 375       else if (node->local.inlinable)
 376         fprintf (f, " inlinable");
 377       if (node->global.cloned_times > 1)
 378         fprintf (f, " cloned %ix", node->global.cloned_times);
 379
 380       fprintf (f, "\n  called by: ");
 381       for (edge = node->callers; edge; edge = edge->next_caller)
 382         {
 383           fprintf (f, "%s ", cgraph_node_name (edge->caller));
 384           if (edge->inline_call)
 385             fprintf(f, "(inlined) ");
 386         }
 387
 388       fprintf (f, "\n  calls: ");
 389       for (edge = node->callees; edge; edge = edge->next_callee)
 390         {
 391           fprintf (f, "%s ", cgraph_node_name (edge->callee));
 392           if (edge->inline_call)
 393             fprintf(f, "(inlined) ");
 394         }
 395       fprintf (f, "\n");
 396     }
 397 }
 398
 399 /* Returns a hash code for P.  */
 400
 401 static hashval_t
 402 cgraph_varpool_hash_node (const void *p)
 403 {
 404   return ((hashval_t)
 405           IDENTIFIER_HASH_VALUE (DECL_ASSEMBLER_NAME
 406                                  (((struct cgraph_varpool_node *) p)->decl)));
 407 }
 408
 409 /* Returns nonzero if P1 and P2 are equal.  */
 410
 411 static int
 412 eq_cgraph_varpool_node (const void *p1, const void *p2)
 413 {
 414   return ((DECL_ASSEMBLER_NAME (((struct cgraph_varpool_node *) p1)->decl)) ==
 415           (tree) p2);
 416 }
 417
 418 /* Return cgraph_varpool node assigned to DECL.  Create new one when needed.  */
 419 struct cgraph_varpool_node *
 420 cgraph_varpool_node (tree decl)
 421 {
 422   struct cgraph_varpool_node *node;
 423   struct cgraph_varpool_node **slot;
 424
 425   if (!DECL_P (decl) || TREE_CODE (decl) == FUNCTION_DECL)
 426     abort ();
 427
 428   if (!cgraph_varpool_hash)
 429     cgraph_varpool_hash = htab_create_ggc (10, cgraph_varpool_hash_node,
 430                                            eq_cgraph_varpool_node, NULL);
 431
 432
 433   slot = (struct cgraph_varpool_node **)
 434     htab_find_slot_with_hash (cgraph_varpool_hash, DECL_ASSEMBLER_NAME (decl),
 435                               IDENTIFIER_HASH_VALUE (DECL_ASSEMBLER_NAME (decl)),
 436                               INSERT);
 437   if (*slot)
 438     return *slot;
 439   node = ggc_alloc_cleared (sizeof (*node));
 440   node->decl = decl;
 441   cgraph_varpool_n_nodes++;
 442   cgraph_varpool_nodes = node;
 443   *slot = node;
 444   return node;
 445 }
 446
 447 /* Try to find existing function for identifier ID.  */
 448 struct cgraph_varpool_node *
 449 cgraph_varpool_node_for_identifier (tree id)
 450 {
 451   struct cgraph_varpool_node **slot;
 452
 453   if (TREE_CODE (id) != IDENTIFIER_NODE)
 454     abort ();
 455
 456   if (!cgraph_varpool_hash)
 457     return NULL;
 458
 459   slot = (struct cgraph_varpool_node **)
 460     htab_find_slot_with_hash (cgraph_varpool_hash, id,
 461                               IDENTIFIER_HASH_VALUE (id), NO_INSERT);
 462   if (!slot)
 463     return NULL;
 464   return *slot;
 465 }
 466
 467 /* Notify finalize_compilation_unit that given node is reachable
 468    or needed.  */
 469 void
 470 cgraph_varpool_mark_needed_node (struct cgraph_varpool_node *node)
 471 {
 472   if (!node->needed && node->finalized)
 473     {
 474       node->next_needed = cgraph_varpool_nodes_queue;
 475       cgraph_varpool_nodes_queue = node;
 476       notice_global_symbol (node->decl);
 477     }
 478   node->needed = 1;
 479 }
 480
 481 void
 482 cgraph_varpool_finalize_decl (tree decl)
 483 {
 484   struct cgraph_varpool_node *node = cgraph_varpool_node (decl);
 485
 486   /* The first declaration of a variable that comes through this function
 487      decides whether it is global (in C, has external linkage)
 488      or local (in C, has internal linkage).  So do nothing more
 489      if this function has already run.  */
 490   if (node->finalized)
 491     return;
 492   if (node->needed)
 493     {
 494       node->next_needed = cgraph_varpool_nodes_queue;
 495       cgraph_varpool_nodes_queue = node;
 496       notice_global_symbol (decl);
 497     }
 498   node->finalized = true;
 499
 500   if (/* Externally visible variables must be output.  The exception are
 501          COMDAT functions that must be output only when they are needed.  */
 502       (TREE_PUBLIC (decl) && !DECL_COMDAT (decl))
 503       /* Function whose name is output to the assembler file must be produced.
 504          It is possible to assemble the name later after finalizing the function
 505          and the fact is noticed in assemble_name then.  */
 506       || (DECL_ASSEMBLER_NAME_SET_P (decl)
 507           && TREE_SYMBOL_REFERENCED (DECL_ASSEMBLER_NAME (decl))))
 508     {
 509       cgraph_varpool_mark_needed_node (node);
 510     }
 511 }
 512
 513 bool
 514 cgraph_varpool_assemble_pending_decls (void)
 515 {
 516   bool changed = false;
 517
 518   while (cgraph_varpool_nodes_queue)
 519     {
 520       tree decl = cgraph_varpool_nodes_queue->decl;
 521       struct cgraph_varpool_node *node = cgraph_varpool_nodes_queue;
 522
 523       cgraph_varpool_nodes_queue = cgraph_varpool_nodes_queue->next_needed;
 524       if (!TREE_ASM_WRITTEN (decl))
 525         {
 526           assemble_variable (decl, 0, 1, 0);
 527           changed = true;
 528         }
 529       node->next_needed = NULL;
 530     }
 531   return changed;
 532 }
 533
 534 /* Return true when the DECL can possibly be inlined.  */
 535 bool
 536 cgraph_function_possibly_inlined_p (tree decl)
 537 {
 538   if (!cgraph_global_info_ready)
 539     return (DECL_INLINE (decl) && !flag_no_inline);
 540   return cgraph_node (decl)->global.inlined;
 541 }
 542
 543 #include "gt-cgraph.h"