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 /* Figure out what functions we want to assemble.  */
 424
 425 static void
 426 cgraph_mark_functions_to_output ()
 427 {
 428   struct cgraph_node *node;
 429
 430   /* Figure out functions we want to assemble.  */
 431   for (node = cgraph_nodes; node; node = node->next)
 432     {
 433       tree decl = node->decl;
 434
 435       if (DECL_SAVED_TREE (decl)
 436           && (node->needed
 437               || (DECL_UNINLINABLE (decl) && node->reachable)
 438               || TREE_SYMBOL_REFERENCED (DECL_ASSEMBLER_NAME (decl)))
 439           && !TREE_ASM_WRITTEN (decl) && !node->origin
 440           && !DECL_EXTERNAL (decl))
 441         node->output = 1;
 442     }
 443 }
 444
 445 /* Expand function specified by NODE.  */
 446 static void
 447 cgraph_expand_function (node)
 448      struct cgraph_node *node;
 449 {
 450   tree decl = node->decl;
 451
 452   announce_function (decl);
 453   if (flag_inline_trees)
 454     optimize_inline_calls (decl);
 455   (*lang_hooks.callgraph.expand_function) (decl);
 456   if (DECL_UNINLINABLE (decl))
 457     DECL_SAVED_TREE (decl) = NULL;
 458   current_function_decl = NULL;
 459 }
 460
 461
 462 /* Expand all functions that must be output.
 463
 464    Attempt to topologically sort the nodes so function is output when
 465    all called functions are already assembled to allow data to be propagated
 466    accross the callgraph.  Use stack to get smaller distance between function
 467    and it's callees (later we may use more sophisticated algorithm for
 468    function reordering, we will likely want to use subsections to make output
 469    functions to appear in top-down order, not bottom-up they are assembled).  */
 470
 471 static void
 472 cgraph_expand_functions ()
 473 {
 474   struct cgraph_node *node, *node2;
 475   struct cgraph_node **stack =
 476     xcalloc (sizeof (struct cgraph_node *), cgraph_n_nodes);
 477   struct cgraph_node **order =
 478     xcalloc (sizeof (struct cgraph_node *), cgraph_n_nodes);
 479   int stack_size = 0;
 480   int order_pos = 0;
 481   struct cgraph_edge *edge, last;
 482   int i;
 483
 484   cgraph_mark_functions_to_output ();
 485
 486   /*  We have to deal with cycles nicely, so use depth first traversal
 487       algorithm.  Ignore the fact that some functions won't need to be output
 488       and put them into order as well, so we get dependencies right trought inlined
 489       functions.  */
 490   for (node = cgraph_nodes; node; node = node->next)
 491     node->aux = NULL;
 492   for (node = cgraph_nodes; node; node = node->next)
 493     if (node->output && !node->aux)
 494       {
 495         node2 = node;
 496         if (!node->callers)
 497           node->aux = &last;
 498         else
 499           node->aux = node->callers;
 500         while (node2)
 501           {
 502             while (node2->aux != &last)
 503               {
 504                 edge = node2->aux;
 505                 if (edge->next_caller)
 506                   node2->aux = edge->next_caller;
 507                 else
 508                   node2->aux = &last;
 509                 if (!edge->caller->aux)
 510                   {
 511                     if (!edge->caller->callers)
 512                       edge->caller->aux = &last;
 513                     else
 514                       edge->caller->aux = edge->caller->callers;
 515                     stack[stack_size++] = node2;
 516                     node2 = edge->caller;
 517                     break;
 518                   }
 519               }
 520             if (node2->aux == &last)
 521               {
 522                 order[order_pos++] = node2;
 523                 if (stack_size)
 524                   node2 = stack[--stack_size];
 525                 else
 526                   node2 = NULL;
 527               }
 528           }
 529       }
 530   for (i = order_pos - 1; i >=0; i--)
 531     {
 532       node = order[i];
 533       if (node->output)
 534         {
 535           if (!node->reachable)
 536             abort ();
 537           node->output = 0;
 538           cgraph_expand_function (node);
 539         }
 540     }
 541   free (stack);
 542   free (order);
 543 }
 544
 545 /* Perform simple optimizations based on callgraph.  */
 546
 547 void
 548 cgraph_optimize ()
 549 {
 550   struct cgraph_node *node;
 551   bool changed = true;
 552   struct cgraph_edge *edge;
 553
 554   if (!quiet_flag)
 555     fprintf (stderr, "\n\nAssembling functions:");
 556
 557   /* Output everything.
 558      ??? Our inline heuristic may decide to not inline functions previously
 559      marked as inlinable thus adding new function bodies that must be output.
 560      Later we should move all inlining decisions to callgraph code to make
 561      this impossible.  */
 562   cgraph_expand_functions ();
 563   while (changed)
 564     {
 565       changed = false;
 566       for (node = cgraph_nodes; node; node = node->next)
 567         {
 568           if (!node->needed)
 569             continue;
 570
 571           for (edge = node->callees; edge; edge = edge->next_callee)
 572             if (!edge->callee->needed)
 573               changed = edge->callee->needed = true;
 574         }
 575     }
 576   cgraph_expand_functions ();
 577 }