gcc/cgraph.c

   1 /* Callgraph handling code.
   2    Copyright (C) 2003, 2004 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   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                               INSERT);
 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 /* Set the DECL_ASSEMBLER_NAME and update cgraph hashtables.  */
 446 void
 447 change_decl_assembler_name (tree decl, tree name)
 448 {
 449   struct cgraph_node *node = NULL;
 450   struct cgraph_varpool_node *vnode = NULL;
 451   void **slot;
 452
 453   if (!DECL_ASSEMBLER_NAME_SET_P (decl))
 454     {
 455       SET_DECL_ASSEMBLER_NAME (decl, name);
 456       return;
 457     }
 458   if (name == DECL_ASSEMBLER_NAME (decl))
 459     return;
 460
 461   if (TREE_SYMBOL_REFERENCED (DECL_ASSEMBLER_NAME (decl))
 462       && DECL_RTL_SET_P (decl))
 463     warning ("%D renamed after being referenced in assembly", decl);
 464
 465   if (TREE_CODE (decl) == FUNCTION_DECL && cgraph_hash)
 466     {
 467       /* Take a look whether declaration is in the cgraph structure.  */
 468       slot =
 469         htab_find_slot_with_hash (cgraph_hash, DECL_ASSEMBLER_NAME (decl),
 470                                    IDENTIFIER_HASH_VALUE (DECL_ASSEMBLER_NAME
 471                                                           (decl)), NO_INSERT);
 472       if (slot)
 473         node = *slot;
 474
 475       /* It is, verify that we are the canonical node for this decl.  */
 476       if (node && node->decl == decl)
 477         {
 478           node = *slot;
 479           htab_clear_slot (cgraph_hash, slot);
 480          }
 481        else
 482          node = NULL;
 483     }
 484   if (TREE_CODE (decl) == VAR_DECL && TREE_STATIC (decl) && cgraph_varpool_hash)
 485     {
 486       /* Take a look whether declaration is in the cgraph structure.  */
 487       slot =
 488         htab_find_slot_with_hash (cgraph_varpool_hash, DECL_ASSEMBLER_NAME (decl),
 489                                    IDENTIFIER_HASH_VALUE (DECL_ASSEMBLER_NAME
 490                                                           (decl)), NO_INSERT);
 491       if (slot)
 492         vnode = *slot;
 493
 494       /* It is, verify that we are the canonical vnode for this decl.  */
 495       if (vnode && vnode->decl == decl)
 496         {
 497           vnode = *slot;
 498           htab_clear_slot (cgraph_varpool_hash, slot);
 499          }
 500        else
 501          vnode = NULL;
 502     }
 503   SET_DECL_ASSEMBLER_NAME (decl, name);
 504   if (node)
 505     {
 506       slot =
 507         htab_find_slot_with_hash (cgraph_hash, name,
 508                                   IDENTIFIER_HASH_VALUE (name), INSERT);
 509       if (*slot)
 510         abort ();
 511       *slot = node;
 512     }
 513   if (vnode)
 514     {
 515       slot =
 516         htab_find_slot_with_hash (cgraph_varpool_hash, name,
 517                                   IDENTIFIER_HASH_VALUE (name), INSERT);
 518       if (*slot)
 519         abort ();
 520       *slot = vnode;
 521     }
 522 }
 523
 524 /* Try to find existing function for identifier ID.  */
 525 struct cgraph_varpool_node *
 526 cgraph_varpool_node_for_identifier (tree id)
 527 {
 528   struct cgraph_varpool_node **slot;
 529
 530   if (TREE_CODE (id) != IDENTIFIER_NODE)
 531     abort ();
 532
 533   if (!cgraph_varpool_hash)
 534     return NULL;
 535
 536   slot = (struct cgraph_varpool_node **)
 537     htab_find_slot_with_hash (cgraph_varpool_hash, id,
 538                               IDENTIFIER_HASH_VALUE (id), NO_INSERT);
 539   if (!slot)
 540     return NULL;
 541   return *slot;
 542 }
 543
 544 /* Notify finalize_compilation_unit that given node is reachable
 545    or needed.  */
 546 void
 547 cgraph_varpool_mark_needed_node (struct cgraph_varpool_node *node)
 548 {
 549   if (!node->needed && node->finalized)
 550     {
 551       node->next_needed = cgraph_varpool_nodes_queue;
 552       cgraph_varpool_nodes_queue = node;
 553       notice_global_symbol (node->decl);
 554     }
 555   node->needed = 1;
 556 }
 557
 558 void
 559 cgraph_varpool_finalize_decl (tree decl)
 560 {
 561   struct cgraph_varpool_node *node = cgraph_varpool_node (decl);
 562
 563   /* The first declaration of a variable that comes through this function
 564      decides whether it is global (in C, has external linkage)
 565      or local (in C, has internal linkage).  So do nothing more
 566      if this function has already run.  */
 567   if (node->finalized)
 568     return;
 569   if (node->needed)
 570     {
 571       node->next_needed = cgraph_varpool_nodes_queue;
 572       cgraph_varpool_nodes_queue = node;
 573       notice_global_symbol (decl);
 574     }
 575   node->finalized = true;
 576
 577   if (/* Externally visible variables must be output.  The exception are
 578          COMDAT functions that must be output only when they are needed.  */
 579       (TREE_PUBLIC (decl) && !DECL_COMDAT (decl))
 580       /* Function whose name is output to the assembler file must be produced.
 581          It is possible to assemble the name later after finalizing the function
 582          and the fact is noticed in assemble_name then.  */
 583       || (DECL_ASSEMBLER_NAME_SET_P (decl)
 584           && TREE_SYMBOL_REFERENCED (DECL_ASSEMBLER_NAME (decl))))
 585     {
 586       cgraph_varpool_mark_needed_node (node);
 587     }
 588 }
 589
 590 bool
 591 cgraph_varpool_assemble_pending_decls (void)
 592 {
 593   bool changed = false;
 594
 595   while (cgraph_varpool_nodes_queue)
 596     {
 597       tree decl = cgraph_varpool_nodes_queue->decl;
 598       struct cgraph_varpool_node *node = cgraph_varpool_nodes_queue;
 599
 600       cgraph_varpool_nodes_queue = cgraph_varpool_nodes_queue->next_needed;
 601       if (!TREE_ASM_WRITTEN (decl))
 602         {
 603           assemble_variable (decl, 0, 1, 0);
 604           changed = true;
 605         }
 606       node->next_needed = NULL;
 607     }
 608   return changed;
 609 }
 610
 611 /* Return true when the DECL can possibly be inlined.  */
 612 bool
 613 cgraph_function_possibly_inlined_p (tree decl)
 614 {
 615   if (!cgraph_global_info_ready)
 616     return (DECL_INLINE (decl)
 617             && (!flag_really_no_inline
 618                 || (*lang_hooks.tree_inlining.disregard_inline_limits) (decl)));
 619   return cgraph_node (decl)->global.inlined;
 620 }
 621
 622 #include "gt-cgraph.h"