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
  37 /* Hash table used to convert declarations into nodes.  */
  38 static htab_t cgraph_hash = 0;
  39
  40 /* The linked list of cgraph nodes.  */
  41 struct cgraph_node *cgraph_nodes;
  42
  43 /* Number of nodes in existence.  */
  44 int cgraph_n_nodes;
  45
  46 static struct cgraph_edge *create_edge PARAMS ((struct cgraph_node *,
  47                                                 struct cgraph_node *));
  48 static void remove_edge PARAMS ((struct cgraph_node *, struct cgraph_node *));
  49 static hashval_t hash_node PARAMS ((const PTR));
  50 static int eq_node PARAMS ((const PTR, const PTR));
  51
  52 /* Returns a hash code for P.  */
  53
  54 static hashval_t
  55 hash_node (p)
  56      const PTR p;
  57 {
  58   return (hashval_t)
  59     htab_hash_pointer (DECL_ASSEMBLER_NAME
  60                        (((struct cgraph_node *) p)->decl));
  61 }
  62
  63 /* Returns non-zero if P1 and P2 are equal.  */
  64
  65 static int
  66 eq_node (p1, p2)
  67      const PTR p1;
  68      const PTR p2;
  69 {
  70   return ((DECL_ASSEMBLER_NAME (((struct cgraph_node *) p1)->decl)) ==
  71           DECL_ASSEMBLER_NAME ((tree) p2));
  72 }
  73
  74 /* Return cgraph node assigned to DECL.  Create new one when needed.  */
  75 struct cgraph_node *
  76 cgraph_node (decl)
  77      tree decl;
  78 {
  79   struct cgraph_node *node;
  80   struct cgraph_node **slot;
  81
  82   if (!cgraph_hash)
  83     cgraph_hash = htab_create (10, hash_node, eq_node, NULL);
  84
  85   slot =
  86     (struct cgraph_node **) htab_find_slot_with_hash (cgraph_hash, decl,
  87                                                       htab_hash_pointer
  88                                                       (DECL_ASSEMBLER_NAME
  89                                                        (decl)), 1);
  90   if (*slot)
  91     return *slot;
  92   node = xcalloc (sizeof (*node), 1);
  93   node->decl = decl;
  94   node->next = cgraph_nodes;
  95   cgraph_nodes = node;
  96   cgraph_n_nodes++;
  97   *slot = node;
  98   if (DECL_CONTEXT (decl))
  99     {
 100       node->origin = cgraph_node (DECL_CONTEXT (decl));
 101       node->next_nested = node->origin->nested;
 102       node->origin->nested = node;
 103     }
 104   return node;
 105 }
 106
 107 /* Create edge from CALLER to CALLEE in the cgraph.  */
 108
 109 static struct cgraph_edge *
 110 create_edge (caller, callee)
 111      struct cgraph_node *caller, *callee;
 112 {
 113   struct cgraph_edge *edge = xmalloc (sizeof (struct cgraph_edge));
 114
 115   edge->caller = caller;
 116   edge->callee = callee;
 117   edge->next_caller = callee->callers;
 118   edge->next_callee = caller->callees;
 119   caller->callees = edge;
 120   callee->callers = edge;
 121   return edge;
 122 }
 123
 124 /* Remove the edge from CALLER to CALLEE in the cgraph.  */
 125
 126 static void
 127 remove_edge (caller, callee)
 128      struct cgraph_node *caller, *callee;
 129 {
 130   struct cgraph_edge **edge, **edge2;
 131
 132   for (edge = &callee->callers; *edge && (*edge)->caller != caller;
 133        edge = &((*edge)->next_caller))
 134     continue;
 135   if (!*edge)
 136     abort ();
 137   *edge = (*edge)->next_caller;
 138   for (edge2 = &caller->callees; *edge2 && (*edge2)->callee != callee;
 139        edge2 = &(*edge2)->next_callee)
 140     continue;
 141   if (!*edge2)
 142     abort ();
 143   *edge2 = (*edge2)->next_callee;
 144 }
 145
 146 /* Record call from CALLER to CALLEE  */
 147
 148 struct cgraph_edge *
 149 cgraph_record_call (caller, callee)
 150      tree caller, callee;
 151 {
 152   return create_edge (cgraph_node (caller), cgraph_node (callee));
 153 }
 154
 155 void
 156 cgraph_remove_call (caller, callee)
 157      tree caller, callee;
 158 {
 159   remove_edge (cgraph_node (caller), cgraph_node (callee));
 160 }
 161
 162 /* Return true when CALLER_DECL calls CALLEE_DECL.  */
 163
 164 bool
 165 cgraph_calls_p (caller_decl, callee_decl)
 166      tree caller_decl, callee_decl;
 167 {
 168   struct cgraph_node *caller = cgraph_node (caller_decl);
 169   struct cgraph_node *callee = cgraph_node (callee_decl);
 170   struct cgraph_edge *edge;
 171
 172   for (edge = callee->callers; edge && (edge)->caller != caller;
 173        edge = (edge->next_caller))
 174     continue;
 175   return edge != NULL;
 176 }
 177
 178 /* Dump the callgraph.  */
 179
 180 void
 181 dump_cgraph (f)
 182      FILE *f;
 183 {
 184   struct cgraph_node *node;
 185
 186   fprintf (f, "\nCallgraph:\n\n");
 187   for (node = cgraph_nodes; node; node = node->next)
 188     {
 189       struct cgraph_edge *edge;
 190       fprintf (f, "%s", IDENTIFIER_POINTER (DECL_NAME (node->decl)));
 191       if (node->origin)
 192         fprintf (f, " nested in: %s",
 193                  IDENTIFIER_POINTER (DECL_NAME (node->origin->decl)));
 194       if (node->needed)
 195         fprintf (f, " needed");
 196       else if (node->reachable)
 197         fprintf (f, " reachable");
 198       if (DECL_SAVED_TREE (node->decl))
 199         fprintf (f, " tree");
 200
 201       fprintf (f, "\n  called by :");
 202       for (edge = node->callers; edge; edge = edge->next_caller)
 203         fprintf (f, "%s ",
 204                  IDENTIFIER_POINTER (DECL_NAME (edge->caller->decl)));
 205
 206       fprintf (f, "\n  calls: ");
 207       for (edge = node->callees; edge; edge = edge->next_callee)
 208         fprintf (f, "%s ",
 209                  IDENTIFIER_POINTER (DECL_NAME (edge->callee->decl)));
 210       fprintf (f, "\n");
 211     }
 212 }