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 /* Queue of cgraph nodes scheduled to be lowered.  */
  52 struct cgraph_node *cgraph_nodes_queue;
  53
  54 /* Number of nodes in existence.  */
  55 int cgraph_n_nodes;
  56
  57 /* Set when whole unit has been analyzed so we can access global info.  */
  58 bool cgraph_global_info_ready = false;
  59
  60 static struct cgraph_edge *create_edge PARAMS ((struct cgraph_node *,
  61                                                 struct cgraph_node *));
  62 static void cgraph_remove_edge PARAMS ((struct cgraph_node *, struct cgraph_node *));
  63 static hashval_t hash_node PARAMS ((const void *));
  64 static int eq_node PARAMS ((const void *, const void *));
  65
  66 /* Returns a hash code for P.  */
  67
  68 static hashval_t
  69 hash_node (p)
  70      const void *p;
  71 {
  72   return (hashval_t)
  73     htab_hash_pointer (DECL_ASSEMBLER_NAME
  74                        (((struct cgraph_node *) p)->decl));
  75 }
  76
  77 /* Returns nonzero if P1 and P2 are equal.  */
  78
  79 static int
  80 eq_node (p1, p2)
  81      const void *p1;
  82      const void *p2;
  83 {
  84   return ((DECL_ASSEMBLER_NAME (((struct cgraph_node *) p1)->decl)) ==
  85           (tree) p2);
  86 }
  87
  88 /* Return cgraph node assigned to DECL.  Create new one when needed.  */
  89 struct cgraph_node *
  90 cgraph_node (decl)
  91      tree decl;
  92 {
  93   struct cgraph_node *node;
  94   struct cgraph_node **slot;
  95
  96   if (TREE_CODE (decl) != FUNCTION_DECL)
  97     abort ();
  98
  99   if (!cgraph_hash)
 100     {
 101       cgraph_hash = htab_create (10, hash_node, eq_node, NULL);
 102       VARRAY_TREE_INIT (known_fns, 32, "known_fns");
 103     }
 104
 105   slot =
 106     (struct cgraph_node **) htab_find_slot_with_hash (cgraph_hash,
 107                                                       DECL_ASSEMBLER_NAME (decl),
 108                                                       htab_hash_pointer
 109                                                       (DECL_ASSEMBLER_NAME
 110                                                        (decl)), 1);
 111   if (*slot)
 112     return *slot;
 113   node = xcalloc (sizeof (*node), 1);
 114   node->decl = decl;
 115   node->next = cgraph_nodes;
 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   VARRAY_PUSH_TREE (known_fns, decl);
 129   return node;
 130 }
 131
 132 /* Try to find existing function for identifier ID.  */
 133 struct cgraph_node *
 134 cgraph_node_for_identifier (id)
 135      tree id;
 136 {
 137   struct cgraph_node **slot;
 138
 139   if (TREE_CODE (id) != IDENTIFIER_NODE)
 140     abort ();
 141
 142   if (!cgraph_hash)
 143     {
 144       cgraph_hash = htab_create (10, hash_node, eq_node, NULL);
 145       VARRAY_TREE_INIT (known_fns, 32, "known_fns");
 146     }
 147
 148   slot =
 149     (struct cgraph_node **) htab_find_slot_with_hash (cgraph_hash, id,
 150                                                       htab_hash_pointer (id), 0);
 151   if (!slot)
 152     return NULL;
 153   return *slot;
 154 }
 155
 156 /* Create edge from CALLER to CALLEE in the cgraph.  */
 157
 158 static struct cgraph_edge *
 159 create_edge (caller, callee)
 160      struct cgraph_node *caller, *callee;
 161 {
 162   struct cgraph_edge *edge = xmalloc (sizeof (struct cgraph_edge));
 163
 164   edge->caller = caller;
 165   edge->callee = callee;
 166   edge->next_caller = callee->callers;
 167   edge->next_callee = caller->callees;
 168   caller->callees = edge;
 169   callee->callers = edge;
 170   return edge;
 171 }
 172
 173 /* Remove the edge from CALLER to CALLEE in the cgraph.  */
 174
 175 static void
 176 cgraph_remove_edge (caller, callee)
 177      struct cgraph_node *caller, *callee;
 178 {
 179   struct cgraph_edge **edge, **edge2;
 180
 181   for (edge = &callee->callers; *edge && (*edge)->caller != caller;
 182        edge = &((*edge)->next_caller))
 183     continue;
 184   if (!*edge)
 185     abort ();
 186   *edge = (*edge)->next_caller;
 187   for (edge2 = &caller->callees; *edge2 && (*edge2)->callee != callee;
 188        edge2 = &(*edge2)->next_callee)
 189     continue;
 190   if (!*edge2)
 191     abort ();
 192   *edge2 = (*edge2)->next_callee;
 193 }
 194
 195 /* Remove the node from cgraph.  */
 196
 197 void
 198 cgraph_remove_node (node)
 199      struct cgraph_node *node;
 200 {
 201   while (node->callers)
 202     cgraph_remove_edge (node->callers->caller, node);
 203   while (node->callees)
 204     cgraph_remove_edge (node, node->callees->callee);
 205   while (node->nested)
 206     cgraph_remove_node (node->nested);
 207   if (node->origin)
 208     {
 209       struct cgraph_node **node2 = &node->origin->nested;
 210
 211       while (*node2 != node)
 212         node2 = &(*node2)->next_nested;
 213       *node2 = node->next_nested;
 214     }
 215   if (node->previous)
 216     node->previous->next = node->next;
 217   else
 218     cgraph_nodes = node;
 219   if (node->next)
 220     node->next->previous = node->previous;
 221   DECL_SAVED_TREE (node->decl) = NULL;
 222   /* Do not free the structure itself so the walk over chain can continue.  */
 223 }
 224
 225 /* Notify finalize_compilation_unit that given node is reachable
 226    or needed.  */
 227 void
 228 cgraph_mark_needed_node (node, needed)
 229      struct cgraph_node *node;
 230      int needed;
 231 {
 232   if (needed)
 233     {
 234       node->needed = 1;
 235     }
 236   if (!node->reachable)
 237     {
 238       node->reachable = 1;
 239       if (DECL_SAVED_TREE (node->decl))
 240         {
 241           node->aux = cgraph_nodes_queue;
 242           cgraph_nodes_queue = node;
 243         }
 244     }
 245 }
 246
 247
 248 /* Record call from CALLER to CALLEE  */
 249
 250 struct cgraph_edge *
 251 cgraph_record_call (caller, callee)
 252      tree caller, callee;
 253 {
 254   return create_edge (cgraph_node (caller), cgraph_node (callee));
 255 }
 256
 257 void
 258 cgraph_remove_call (caller, callee)
 259      tree caller, callee;
 260 {
 261   cgraph_remove_edge (cgraph_node (caller), cgraph_node (callee));
 262 }
 263
 264 /* Return true when CALLER_DECL calls CALLEE_DECL.  */
 265
 266 bool
 267 cgraph_calls_p (caller_decl, callee_decl)
 268      tree caller_decl, callee_decl;
 269 {
 270   struct cgraph_node *caller = cgraph_node (caller_decl);
 271   struct cgraph_node *callee = cgraph_node (callee_decl);
 272   struct cgraph_edge *edge;
 273
 274   for (edge = callee->callers; edge && (edge)->caller != caller;
 275        edge = (edge->next_caller))
 276     continue;
 277   return edge != NULL;
 278 }
 279
 280 /* Return local info for the compiled function.  */
 281
 282 struct cgraph_local_info *
 283 cgraph_local_info (decl)
 284      tree decl;
 285 {
 286   struct cgraph_node *node;
 287   if (TREE_CODE (decl) != FUNCTION_DECL)
 288     abort ();
 289   node = cgraph_node (decl);
 290   return &node->local;
 291 }
 292
 293 /* Return local info for the compiled function.  */
 294
 295 struct cgraph_global_info *
 296 cgraph_global_info (decl)
 297      tree decl;
 298 {
 299   struct cgraph_node *node;
 300   if (TREE_CODE (decl) != FUNCTION_DECL || !cgraph_global_info_ready)
 301     abort ();
 302   node = cgraph_node (decl);
 303   return &node->global;
 304 }
 305
 306 /* Return local info for the compiled function.  */
 307
 308 struct cgraph_rtl_info *
 309 cgraph_rtl_info (decl)
 310      tree decl;
 311 {
 312   struct cgraph_node *node;
 313   if (TREE_CODE (decl) != FUNCTION_DECL)
 314     abort ();
 315   node = cgraph_node (decl);
 316   if (decl != current_function_decl
 317       && !TREE_ASM_WRITTEN (node->decl))
 318     return NULL;
 319   return &node->rtl;
 320 }
 321
 322
 323 /* Dump the callgraph.  */
 324
 325 void
 326 dump_cgraph (f)
 327      FILE *f;
 328 {
 329   struct cgraph_node *node;
 330
 331   fprintf (f, "\nCallgraph:\n\n");
 332   for (node = cgraph_nodes; node; node = node->next)
 333     {
 334       struct cgraph_edge *edge;
 335       fprintf (f, "%s", IDENTIFIER_POINTER (DECL_NAME (node->decl)));
 336       if (node->origin)
 337         fprintf (f, " nested in: %s",
 338                  IDENTIFIER_POINTER (DECL_NAME (node->origin->decl)));
 339       if (node->needed)
 340         fprintf (f, " needed");
 341       else if (node->reachable)
 342         fprintf (f, " reachable");
 343       if (DECL_SAVED_TREE (node->decl))
 344         fprintf (f, " tree");
 345
 346       fprintf (f, "\n  called by :");
 347       for (edge = node->callers; edge; edge = edge->next_caller)
 348         fprintf (f, "%s ",
 349                  IDENTIFIER_POINTER (DECL_NAME (edge->caller->decl)));
 350
 351       fprintf (f, "\n  calls: ");
 352       for (edge = node->callees; edge; edge = edge->next_callee)
 353         fprintf (f, "%s ",
 354                  IDENTIFIER_POINTER (DECL_NAME (edge->callee->decl)));
 355       fprintf (f, "\n");
 356     }
 357 }
 358
 359 #include "gt-cgraph.h"