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 "tree-inline.h"
  28 #include "langhooks.h"
  29 #include "hashtab.h"
  30 #include "toplev.h"
  31 #include "flags.h"
  32 #include "ggc.h"
  33 #include "debug.h"
  34 #include "target.h"
  35 #include "cgraph.h"
  36 #include "varray.h"
  37
  38 /* The known declarations must not get garbage collected.  Callgraph
  39    datastructures should not get saved via PCH code since this would
  40    make it difficult to extend into intra-module optimizer later.  So
  41    we store only the references into the array to prevent gabrage
  42    collector from deleting live data.  */
  43 static GTY(()) varray_type known_fns;
  44
  45 /* Hash table used to convert declarations into nodes.  */
  46 static htab_t cgraph_hash = 0;
  47
  48 /* The linked list of cgraph nodes.  */
  49 struct cgraph_node *cgraph_nodes;
  50
  51 /* Number of nodes in existence.  */
  52 int cgraph_n_nodes;
  53
  54 /* Set when whole unit has been analyzed so we can access global info.  */
  55 bool cgraph_global_info_ready = false;
  56
  57 static struct cgraph_edge *create_edge PARAMS ((struct cgraph_node *,
  58                                                 struct cgraph_node *));
  59 static void cgraph_remove_edge PARAMS ((struct cgraph_node *, struct cgraph_node *));
  60 static hashval_t hash_node PARAMS ((const PTR));
  61 static int eq_node PARAMS ((const PTR, const PTR));
  62
  63 /* Returns a hash code for P.  */
  64
  65 static hashval_t
  66 hash_node (p)
  67      const PTR p;
  68 {
  69   return (hashval_t)
  70     htab_hash_pointer (DECL_ASSEMBLER_NAME
  71                        (((struct cgraph_node *) p)->decl));
  72 }
  73
  74 /* Returns nonzero if P1 and P2 are equal.  */
  75
  76 static int
  77 eq_node (p1, p2)
  78      const PTR p1;
  79      const PTR p2;
  80 {
  81   return ((DECL_ASSEMBLER_NAME (((struct cgraph_node *) p1)->decl)) ==
  82           DECL_ASSEMBLER_NAME ((tree) p2));
  83 }
  84
  85 /* Return cgraph node assigned to DECL.  Create new one when needed.  */
  86 struct cgraph_node *
  87 cgraph_node (decl)
  88      tree decl;
  89 {
  90   struct cgraph_node *node;
  91   struct cgraph_node **slot;
  92
  93   if (TREE_CODE (decl) != FUNCTION_DECL)
  94     abort ();
  95
  96   if (!cgraph_hash)
  97     {
  98       cgraph_hash = htab_create (10, hash_node, eq_node, NULL);
  99       VARRAY_TREE_INIT (known_fns, 32, "known_fns");
 100     }
 101
 102   slot =
 103     (struct cgraph_node **) htab_find_slot_with_hash (cgraph_hash, decl,
 104                                                       htab_hash_pointer
 105                                                       (DECL_ASSEMBLER_NAME
 106                                                        (decl)), 1);
 107   if (*slot)
 108     return *slot;
 109   node = xcalloc (sizeof (*node), 1);
 110   node->decl = decl;
 111   node->next = cgraph_nodes;
 112   if (cgraph_nodes)
 113     cgraph_nodes->previous = node;
 114   node->previous = NULL;
 115   cgraph_nodes = node;
 116   cgraph_n_nodes++;
 117   *slot = node;
 118   if (DECL_CONTEXT (decl) && TREE_CODE (DECL_CONTEXT (decl)) == FUNCTION_DECL)
 119     {
 120       node->origin = cgraph_node (DECL_CONTEXT (decl));
 121       node->next_nested = node->origin->nested;
 122       node->origin->nested = node;
 123     }
 124   VARRAY_PUSH_TREE (known_fns, decl);
 125   return node;
 126 }
 127
 128 /* Create edge from CALLER to CALLEE in the cgraph.  */
 129
 130 static struct cgraph_edge *
 131 create_edge (caller, callee)
 132      struct cgraph_node *caller, *callee;
 133 {
 134   struct cgraph_edge *edge = xmalloc (sizeof (struct cgraph_edge));
 135
 136   edge->caller = caller;
 137   edge->callee = callee;
 138   edge->next_caller = callee->callers;
 139   edge->next_callee = caller->callees;
 140   caller->callees = edge;
 141   callee->callers = edge;
 142   return edge;
 143 }
 144
 145 /* Remove the edge from CALLER to CALLEE in the cgraph.  */
 146
 147 static void
 148 cgraph_remove_edge (caller, callee)
 149      struct cgraph_node *caller, *callee;
 150 {
 151   struct cgraph_edge **edge, **edge2;
 152
 153   for (edge = &callee->callers; *edge && (*edge)->caller != caller;
 154        edge = &((*edge)->next_caller))
 155     continue;
 156   if (!*edge)
 157     abort ();
 158   *edge = (*edge)->next_caller;
 159   for (edge2 = &caller->callees; *edge2 && (*edge2)->callee != callee;
 160        edge2 = &(*edge2)->next_callee)
 161     continue;
 162   if (!*edge2)
 163     abort ();
 164   *edge2 = (*edge2)->next_callee;
 165 }
 166
 167 /* Remove the node from cgraph.  */
 168
 169 void
 170 cgraph_remove_node (node)
 171      struct cgraph_node *node;
 172 {
 173   while (node->callers)
 174     cgraph_remove_edge (node->callers->caller, node);
 175   while (node->callees)
 176     cgraph_remove_edge (node, node->callees->callee);
 177   while (node->nested)
 178     cgraph_remove_node (node->nested);
 179   if (node->origin)
 180     {
 181       struct cgraph_node **node2 = &node->origin->nested;
 182
 183       while (*node2 != node)
 184         node2 = &(*node2)->next_nested;
 185       *node2 = node->next_nested;
 186     }
 187   if (node->previous)
 188     node->previous->next = node->next;
 189   else
 190     cgraph_nodes = node;
 191   if (node->next)
 192     node->next->previous = node->previous;
 193   DECL_SAVED_TREE (node->decl) = NULL;
 194   /* Do not free the structure itself so the walk over chain can continue.  */
 195 }
 196
 197
 198 /* Record call from CALLER to CALLEE  */
 199
 200 struct cgraph_edge *
 201 cgraph_record_call (caller, callee)
 202      tree caller, callee;
 203 {
 204   return create_edge (cgraph_node (caller), cgraph_node (callee));
 205 }
 206
 207 void
 208 cgraph_remove_call (caller, callee)
 209      tree caller, callee;
 210 {
 211   cgraph_remove_edge (cgraph_node (caller), cgraph_node (callee));
 212 }
 213
 214 /* Return true when CALLER_DECL calls CALLEE_DECL.  */
 215
 216 bool
 217 cgraph_calls_p (caller_decl, callee_decl)
 218      tree caller_decl, callee_decl;
 219 {
 220   struct cgraph_node *caller = cgraph_node (caller_decl);
 221   struct cgraph_node *callee = cgraph_node (callee_decl);
 222   struct cgraph_edge *edge;
 223
 224   for (edge = callee->callers; edge && (edge)->caller != caller;
 225        edge = (edge->next_caller))
 226     continue;
 227   return edge != NULL;
 228 }
 229
 230 /* Return local info for the compiled function.  */
 231
 232 struct cgraph_local_info *
 233 cgraph_local_info (decl)
 234      tree decl;
 235 {
 236   struct cgraph_node *node;
 237   if (TREE_CODE (decl) != FUNCTION_DECL)
 238     abort ();
 239   node = cgraph_node (decl);
 240   return &node->local;
 241 }
 242
 243 /* Return local info for the compiled function.  */
 244
 245 struct cgraph_global_info *
 246 cgraph_global_info (decl)
 247      tree decl;
 248 {
 249   struct cgraph_node *node;
 250   if (TREE_CODE (decl) != FUNCTION_DECL || !cgraph_global_info_ready)
 251     abort ();
 252   node = cgraph_node (decl);
 253   return &node->global;
 254 }
 255
 256 /* Return local info for the compiled function.  */
 257
 258 struct cgraph_rtl_info *
 259 cgraph_rtl_info (decl)
 260      tree decl;
 261 {
 262   struct cgraph_node *node;
 263   if (TREE_CODE (decl) != FUNCTION_DECL)
 264     abort ();
 265   node = cgraph_node (decl);
 266   if (decl != current_function_decl
 267       && !TREE_ASM_WRITTEN (node->decl))
 268     return NULL;
 269   return &node->rtl;
 270 }
 271
 272
 273 /* Dump the callgraph.  */
 274
 275 void
 276 dump_cgraph (f)
 277      FILE *f;
 278 {
 279   struct cgraph_node *node;
 280
 281   fprintf (f, "\nCallgraph:\n\n");
 282   for (node = cgraph_nodes; node; node = node->next)
 283     {
 284       struct cgraph_edge *edge;
 285       fprintf (f, "%s", IDENTIFIER_POINTER (DECL_NAME (node->decl)));
 286       if (node->origin)
 287         fprintf (f, " nested in: %s",
 288                  IDENTIFIER_POINTER (DECL_NAME (node->origin->decl)));
 289       if (node->needed)
 290         fprintf (f, " needed");
 291       else if (node->reachable)
 292         fprintf (f, " reachable");
 293       if (DECL_SAVED_TREE (node->decl))
 294         fprintf (f, " tree");
 295
 296       fprintf (f, "\n  called by :");
 297       for (edge = node->callers; edge; edge = edge->next_caller)
 298         fprintf (f, "%s ",
 299                  IDENTIFIER_POINTER (DECL_NAME (edge->caller->decl)));
 300
 301       fprintf (f, "\n  calls: ");
 302       for (edge = node->callees; edge; edge = edge->next_callee)
 303         fprintf (f, "%s ",
 304                  IDENTIFIER_POINTER (DECL_NAME (edge->callee->decl)));
 305       fprintf (f, "\n");
 306     }
 307 }
 308
 309 #include "gt-cgraph.h"