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
  36 /* The cgraph data strutcture.
  37    Each function decl has assigned cgraph_node listing calees and callers.  */
  38
  39 struct cgraph_node
  40 {
  41   tree decl;
  42   struct cgraph_edge *callees;
  43   struct cgraph_edge *callers;
  44   struct cgraph_node *next;
  45   /* For nested functions points to function the node is nested in.  */
  46   struct cgraph_node *origin;
  47   /* Points to first nested function, if any.  */
  48   struct cgraph_node *nested;
  49   /* Pointer to the next function with same origin, if any.  */
  50   struct cgraph_node *next_nested;
  51   void *aux;
  52
  53   /* Set when function must be output - it is externally visible
  54      or it's address is taken.  */
  55   bool needed;
  56   /* Set when function is reachable by call from other function
  57      that is eighter reachable or needed.  */
  58   bool reachable;
  59   /* Set when the frontend has been asked to lower representation of this
  60      function into trees.  Callees lists are not available when lowered
  61      is not set.  */
  62   bool lowered;
  63   /* Set when function is scheduled to be assembled.  */
  64   bool output;
  65 };
  66
  67 struct cgraph_edge
  68 {
  69   struct cgraph_node *caller, *callee;
  70   struct cgraph_edge *next_caller;
  71   struct cgraph_edge *next_callee;
  72 };
  73
  74 /* Hash table used to convert declarations into nodes.  */
  75 static htab_t cgraph_hash = 0;
  76
  77 /* The linked list of cgraph nodes.  */
  78 static struct cgraph_node *cgraph_nodes;
  79
  80 /* Number of nodes in existence.  */
  81 static int cgraph_n_nodes;
  82
  83 static struct cgraph_node *cgraph_node PARAMS ((tree decl));
  84 static struct cgraph_edge *create_edge PARAMS ((struct cgraph_node *,
  85                                                 struct cgraph_node *));
  86 static void remove_edge PARAMS ((struct cgraph_node *, struct cgraph_node *));
  87 static struct cgraph_edge *record_call PARAMS ((tree, tree));
  88 static tree record_call_1 PARAMS ((tree *, int *, void *));
  89 static hashval_t hash_node PARAMS ((const PTR));
  90 static int eq_node PARAMS ((const PTR, const PTR));
  91 static struct cgraph_node *cgraph_node PARAMS ((tree));
  92 static void cgraph_expand_functions PARAMS ((void));
  93 static void cgraph_mark_functions_to_output PARAMS ((void));
  94 static void cgraph_expand_function PARAMS ((struct cgraph_node *));
  95 static void cgraph_mark_needed_node PARAMS ((struct cgraph_node *, int));
  96
  97 /* Returns a hash code for P.  */
  98
  99 static hashval_t
 100 hash_node (p)
 101      const PTR p;
 102 {
 103   return (hashval_t)
 104     htab_hash_pointer (DECL_ASSEMBLER_NAME
 105                        (((struct cgraph_node *) p)->decl));
 106 }
 107
 108 /* Returns non-zero if P1 and P2 are equal.  */
 109
 110 static int
 111 eq_node (p1, p2)
 112      const PTR p1;
 113      const PTR p2;
 114 {
 115   return ((DECL_ASSEMBLER_NAME (((struct cgraph_node *) p1)->decl)) ==
 116           DECL_ASSEMBLER_NAME ((tree) p2));
 117 }
 118
 119 /* Return cgraph node assigned to DECL.  Create new one when needed.  */
 120 static struct cgraph_node *
 121 cgraph_node (decl)
 122      tree decl;
 123 {
 124   struct cgraph_node *node;
 125   struct cgraph_node **slot;
 126
 127   if (!cgraph_hash)
 128     cgraph_hash = htab_create (10, hash_node, eq_node, NULL);
 129
 130   slot =
 131     (struct cgraph_node **) htab_find_slot_with_hash (cgraph_hash, decl,
 132                                                       htab_hash_pointer
 133                                                       (DECL_ASSEMBLER_NAME
 134                                                        (decl)), 1);
 135   if (*slot)
 136     return *slot;
 137   node = xcalloc (sizeof (*node), 1);
 138   node->decl = decl;
 139   node->next = cgraph_nodes;
 140   cgraph_nodes = node;
 141   cgraph_n_nodes++;
 142   *slot = node;
 143   if (DECL_CONTEXT (decl))
 144     {
 145       node->origin = cgraph_node (DECL_CONTEXT (decl));
 146       node->next_nested = node->origin->nested;
 147       node->origin->nested = node;
 148     }
 149   return node;
 150 }
 151
 152 /* Create edge from CALLER to CALLEE in the cgraph.  */
 153
 154 static struct cgraph_edge *
 155 create_edge (caller, callee)
 156      struct cgraph_node *caller, *callee;
 157 {
 158   struct cgraph_edge *edge = xmalloc (sizeof (struct cgraph_edge));
 159
 160   edge->caller = caller;
 161   edge->callee = callee;
 162   edge->next_caller = callee->callers;
 163   edge->next_callee = caller->callees;
 164   caller->callees = edge;
 165   callee->callers = edge;
 166   return edge;
 167 }
 168
 169 /* Remove the edge from CALLER to CALLEE in the cgraph.  */
 170
 171 static void
 172 remove_edge (caller, callee)
 173      struct cgraph_node *caller, *callee;
 174 {
 175   struct cgraph_edge **edge, **edge2;
 176
 177   for (edge = &callee->callers; *edge && (*edge)->caller != caller;
 178        edge = &((*edge)->next_caller))
 179     continue;
 180   if (!*edge)
 181     abort ();
 182   *edge = (*edge)->next_caller;
 183   for (edge2 = &caller->callees; *edge2 && (*edge2)->callee != callee;
 184        edge2 = &(*edge2)->next_callee)
 185     continue;
 186   if (!*edge2)
 187     abort ();
 188   *edge2 = (*edge2)->next_callee;
 189 }
 190
 191 /* Record call from CALLER to CALLEE  */
 192
 193 static struct cgraph_edge *
 194 record_call (caller, callee)
 195      tree caller, callee;
 196 {
 197   return create_edge (cgraph_node (caller), cgraph_node (callee));
 198 }
 199
 200 void
 201 cgraph_remove_call (caller, callee)
 202      tree caller, callee;
 203 {
 204   remove_edge (cgraph_node (caller), cgraph_node (callee));
 205 }
 206
 207 /* Return true when CALLER_DECL calls CALLEE_DECL.  */
 208
 209 bool
 210 cgraph_calls_p (caller_decl, callee_decl)
 211      tree caller_decl, callee_decl;
 212 {
 213   struct cgraph_node *caller = cgraph_node (caller_decl);
 214   struct cgraph_node *callee = cgraph_node (callee_decl);
 215   struct cgraph_edge *edge;
 216
 217   for (edge = callee->callers; edge && (edge)->caller != caller;
 218        edge = (edge->next_caller))
 219     continue;
 220   return edge != NULL;
 221 }
 222
 223 /* Walk tree and record all calls.  Called via walk_tree.  */
 224 static tree
 225 record_call_1 (tp, walk_subtrees, data)
 226      tree *tp;
 227      int *walk_subtrees;
 228      void *data;
 229 {
 230   /* Record dereferences to the functions.  This makes the functions
 231      reachable unconditionally.  */
 232   if (TREE_CODE (*tp) == ADDR_EXPR)
 233     {
 234       tree decl = TREE_OPERAND (*tp, 0);
 235       if (TREE_CODE (decl) == FUNCTION_DECL)
 236         cgraph_mark_needed_node (cgraph_node (decl), 1);
 237     }
 238   else if (TREE_CODE (*tp) == CALL_EXPR)
 239     {
 240       tree decl = TREE_OPERAND (*tp, 0);
 241       if (TREE_CODE (decl) == ADDR_EXPR)
 242         decl = TREE_OPERAND (decl, 0);
 243       if (TREE_CODE (decl) == FUNCTION_DECL)
 244         {
 245           if (DECL_BUILT_IN (decl))
 246             return NULL;
 247           record_call (data, decl);
 248           walk_tree (&TREE_OPERAND (*tp, 1), record_call_1, data, NULL);
 249           *walk_subtrees = 0;
 250         }
 251     }
 252   return NULL;
 253 }
 254
 255 /* Create cgraph edges for function calles via BODY.  */
 256
 257 void
 258 cgraph_create_edges (decl, body)
 259      tree decl;
 260      tree body;
 261 {
 262   walk_tree (&body, record_call_1, decl, NULL);
 263 }
 264
 265 /* Analyze function once it is parsed.  Set up the local information
 266    available - create cgraph edges for function calles via BODY.  */
 267
 268 void
 269 cgraph_finalize_function (decl, body)
 270      tree decl;
 271      tree body ATTRIBUTE_UNUSED;
 272 {
 273   struct cgraph_node *node = cgraph_node (decl);
 274
 275   node->decl = decl;
 276
 277   /* Set TREE_UNINLINABLE flag.  */
 278   tree_inlinable_function_p (decl);
 279
 280   (*debug_hooks->deferred_inline_function) (decl);
 281 }
 282
 283 /* Dump the callgraph.  */
 284
 285 void
 286 dump_cgraph (f)
 287      FILE *f;
 288 {
 289   struct cgraph_node *node;
 290
 291   fprintf (f, "\nCallgraph:\n\n");
 292   for (node = cgraph_nodes; node; node = node->next)
 293     {
 294       struct cgraph_edge *edge;
 295       fprintf (f, "%s", IDENTIFIER_POINTER (DECL_NAME (node->decl)));
 296       if (node->origin)
 297         fprintf (f, " nested in: %s",
 298                  IDENTIFIER_POINTER (DECL_NAME (node->origin->decl)));
 299       if (node->needed)
 300         fprintf (f, " needed");
 301       else if (node->reachable)
 302         fprintf (f, " reachable");
 303       if (DECL_SAVED_TREE (node->decl))
 304         fprintf (f, " tree");
 305
 306       fprintf (f, "\n  called by :");
 307       for (edge = node->callers; edge; edge = edge->next_caller)
 308         fprintf (f, "%s ",
 309                  IDENTIFIER_POINTER (DECL_NAME (edge->caller->decl)));
 310
 311       fprintf (f, "\n  calls: ");
 312       for (edge = node->callees; edge; edge = edge->next_callee)
 313         fprintf (f, "%s ",
 314                  IDENTIFIER_POINTER (DECL_NAME (edge->callee->decl)));
 315       fprintf (f, "\n");
 316     }
 317 }
 318
 319 static struct cgraph_node *queue = NULL;
 320
 321 /* Notify finalize_compilation_unit that given node is reachable
 322    or needed.  */
 323 static void
 324 cgraph_mark_needed_node (node, needed)
 325      struct cgraph_node *node;
 326      int needed;
 327 {
 328   if (needed)
 329     {
 330       if (DECL_SAVED_TREE (node->decl))
 331         announce_function (node->decl);
 332       node->needed = 1;
 333     }
 334   if (!node->reachable)
 335     {
 336       node->reachable = 1;
 337       if (DECL_SAVED_TREE (node->decl))
 338         {
 339           node->aux = queue;
 340           queue = node;
 341         }
 342     }
 343 }
 344
 345 /* Analyze the whole compilation unit once it is parsed completely.  */
 346
 347 void
 348 cgraph_finalize_compilation_unit ()
 349 {
 350   struct cgraph_node *node;
 351   struct cgraph_edge *edge;
 352
 353   /* Collect entry points to the unit.  */
 354
 355   if (!quiet_flag)
 356     fprintf (stderr, "\n\nUnit entry points:");
 357
 358   for (node = cgraph_nodes; node; node = node->next)
 359     {
 360       tree decl = node->decl;
 361
 362       if (!DECL_SAVED_TREE (decl))
 363         continue;
 364       if ((TREE_PUBLIC (decl) && !DECL_COMDAT (decl) && !DECL_EXTERNAL (decl))
 365           || (DECL_ASSEMBLER_NAME_SET_P (decl)
 366               && TREE_SYMBOL_REFERENCED (DECL_ASSEMBLER_NAME (decl))))
 367         {
 368           cgraph_mark_needed_node (node, 1);
 369         }
 370     }
 371
 372   /*  Propagate reachability flag and lower representation of all reachable
 373       functions.  In the future, lowering will introduce new functions and
 374       new entry points on the way (by template instantiation and virtual
 375       method table generation for instance).  */
 376   while (queue)
 377     {
 378       tree decl = queue->decl;
 379
 380       node = queue;
 381       queue = queue->aux;
 382       if (node->lowered || !node->reachable || !DECL_SAVED_TREE (decl))
 383         abort ();
 384
 385       /* At the moment frontend automatically emits all nested functions.  */
 386       if (node->nested)
 387         {
 388           struct cgraph_node *node2;
 389
 390           for (node2 = node->nested; node2; node2 = node2->next_nested)
 391             if (!node2->reachable)
 392               cgraph_mark_needed_node (node2, 0);
 393         }
 394
 395       if (lang_hooks.callgraph.lower_function)
 396         (*lang_hooks.callgraph.lower_function) (decl);
 397       /* First kill forward declaration so reverse inling works properly.  */
 398       cgraph_create_edges (decl, DECL_SAVED_TREE (decl));
 399
 400       for (edge = node->callees; edge; edge = edge->next_callee)
 401         {
 402           if (!edge->callee->reachable)
 403             cgraph_mark_needed_node (edge->callee, 0);
 404         }
 405       node->lowered = true;
 406     }
 407   if (!quiet_flag)
 408     fprintf (stderr, "\n\nReclaiming functions:");
 409
 410   for (node = cgraph_nodes; node; node = node->next)
 411     {
 412       tree decl = node->decl;
 413
 414       if (!node->reachable && DECL_SAVED_TREE (decl))
 415         {
 416           DECL_SAVED_TREE (decl) = NULL;
 417           announce_function (decl);
 418         }
 419     }
 420   ggc_collect ();
 421 }
 422
 423 /* Expand all functions that must be output.  */
 424
 425 #define NPREDECESORS(node) ((size_t) (node)->aux)
 426 #define SET_NPREDECESORS(node, n) ((node)->aux = (void *) (size_t) (n))
 427
 428 /* Figure out what functions we want to assemble.  */
 429
 430 static void
 431 cgraph_mark_functions_to_output ()
 432 {
 433   struct cgraph_node *node;
 434
 435   /* Figure out functions we want to assemble.  */
 436   for (node = cgraph_nodes; node; node = node->next)
 437     {
 438       tree decl = node->decl;
 439
 440       if (DECL_SAVED_TREE (decl)
 441           && (node->needed
 442               || (DECL_UNINLINABLE (decl) && node->reachable)
 443               || TREE_SYMBOL_REFERENCED (DECL_ASSEMBLER_NAME (decl)))
 444           && !TREE_ASM_WRITTEN (decl) && !node->origin
 445           && !DECL_EXTERNAL (decl))
 446         node->output = 1;
 447     }
 448 }
 449
 450 /* Expand function specified by NODE.  */
 451 static void
 452 cgraph_expand_function (node)
 453      struct cgraph_node *node;
 454 {
 455   tree decl = node->decl;
 456
 457   announce_function (decl);
 458   if (flag_inline_trees)
 459     optimize_inline_calls (decl);
 460   (*lang_hooks.callgraph.expand_function) (decl);
 461   if (DECL_UNINLINABLE (decl))
 462     DECL_SAVED_TREE (decl) = NULL;
 463   current_function_decl = NULL;
 464 }
 465
 466
 467 /* Expand all functions that must be output.
 468
 469    Attempt to topologically sort the nodes so function is output when
 470    all called functions are already assembled to allow data to be propagated
 471    accross the callgraph.  Use stack to get smaller distance between function
 472    and it's callees (later we may use more sophisticated algorithm for
 473    function reordering, we will likely want to use subsections to make output
 474    functions to appear in top-down order, not bottom-up they are assembled).  */
 475
 476 static void
 477 cgraph_expand_functions ()
 478 {
 479   struct cgraph_node *node;
 480   struct cgraph_node **stack =
 481     xcalloc (sizeof (struct cgraph_node *), cgraph_n_nodes);
 482   int stack_size = 0;
 483   struct cgraph_edge *edge;
 484
 485   cgraph_mark_functions_to_output ();
 486
 487   for (node = cgraph_nodes; node; node = node->next)
 488     if (node->output)
 489       {
 490         int n = 0;
 491         for (edge = node->callees; edge; edge = edge->next_callee)
 492           if (edge->callee->output)
 493             n++;
 494         SET_NPREDECESORS (node, n);
 495         if (n == 0)
 496           stack[stack_size++] = node;
 497       }
 498   while (1)
 499     {
 500       struct cgraph_node *minnode;
 501       while (stack_size)
 502         {
 503           node = stack[--stack_size];
 504           node->output = 0;
 505
 506           for (edge = node->callers; edge; edge = edge->next_caller)
 507             if (edge->caller->output)
 508               {
 509                 SET_NPREDECESORS (edge->caller,
 510                                   NPREDECESORS (edge->caller) - 1);
 511                 if (!NPREDECESORS (edge->caller))
 512                   stack[stack_size++] = edge->caller;
 513               }
 514           if (!node->reachable)
 515             abort ();
 516           cgraph_expand_function (node);
 517         }
 518       minnode = NULL;
 519       /* We found cycle.  Break it and try again.  */
 520       for (node = cgraph_nodes; node; node = node->next)
 521         if (node->output
 522             && (!minnode
 523                 || NPREDECESORS (minnode) > NPREDECESORS (node)))
 524           minnode = node;
 525       if (!minnode)
 526         return;
 527       stack[stack_size++] = minnode;
 528     }
 529 }
 530
 531 /* Perform simple optimizations based on callgraph.  */
 532
 533 void
 534 cgraph_optimize ()
 535 {
 536   struct cgraph_node *node;
 537   bool changed = true;
 538   struct cgraph_edge *edge;
 539
 540   if (!quiet_flag)
 541     fprintf (stderr, "\n\nAssembling functions:");
 542
 543   /* Output everything.
 544      ??? Our inline heuristic may decide to not inline functions previously
 545      marked as inlinable thus adding new function bodies that must be output.
 546      Later we should move all inlining decisions to callgraph code to make
 547      this impossible.  */
 548   cgraph_expand_functions ();
 549   while (changed)
 550     {
 551       changed = false;
 552       for (node = cgraph_nodes; node; node = node->next)
 553         {
 554           if (!node->needed)
 555             continue;
 556
 557           for (edge = node->callees; edge; edge = edge->next_callee)
 558             if (!edge->callee->needed)
 559               changed = edge->callee->needed = true;
 560         }
 561     }
 562   cgraph_expand_functions ();
 563 }