gcc/cgraphunit.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 static void cgraph_expand_functions PARAMS ((void));
  38 static void cgraph_mark_functions_to_output PARAMS ((void));
  39 static void cgraph_expand_function PARAMS ((struct cgraph_node *));
  40 static tree record_call_1 PARAMS ((tree *, int *, void *));
  41
  42 /* Analyze function once it is parsed.  Set up the local information
  43    available - create cgraph edges for function calles via BODY.  */
  44
  45 void
  46 cgraph_finalize_function (decl, body)
  47      tree decl;
  48      tree body ATTRIBUTE_UNUSED;
  49 {
  50   struct cgraph_node *node = cgraph_node (decl);
  51
  52   node->decl = decl;
  53
  54   /* Set TREE_UNINLINABLE flag.  */
  55   tree_inlinable_function_p (decl);
  56
  57   (*debug_hooks->deferred_inline_function) (decl);
  58 }
  59
  60 static struct cgraph_node *queue = NULL;
  61
  62 /* Notify finalize_compilation_unit that given node is reachable
  63    or needed.  */
  64 void
  65 cgraph_mark_needed_node (node, needed)
  66      struct cgraph_node *node;
  67      int needed;
  68 {
  69   if (needed)
  70     {
  71       if (DECL_SAVED_TREE (node->decl))
  72         announce_function (node->decl);
  73       node->needed = 1;
  74     }
  75   if (!node->reachable)
  76     {
  77       node->reachable = 1;
  78       if (DECL_SAVED_TREE (node->decl))
  79         {
  80           node->aux = queue;
  81           queue = node;
  82         }
  83     }
  84 }
  85
  86 /* Walk tree and record all calls.  Called via walk_tree.  */
  87 static tree
  88 record_call_1 (tp, walk_subtrees, data)
  89      tree *tp;
  90      int *walk_subtrees;
  91      void *data;
  92 {
  93   /* Record dereferences to the functions.  This makes the functions
  94      reachable unconditionally.  */
  95   if (TREE_CODE (*tp) == ADDR_EXPR)
  96     {
  97       tree decl = TREE_OPERAND (*tp, 0);
  98       if (TREE_CODE (decl) == FUNCTION_DECL)
  99         cgraph_mark_needed_node (cgraph_node (decl), 1);
 100     }
 101   else if (TREE_CODE (*tp) == CALL_EXPR)
 102     {
 103       tree decl = TREE_OPERAND (*tp, 0);
 104       if (TREE_CODE (decl) == ADDR_EXPR)
 105         decl = TREE_OPERAND (decl, 0);
 106       if (TREE_CODE (decl) == FUNCTION_DECL)
 107         {
 108           if (DECL_BUILT_IN (decl))
 109             return NULL;
 110           cgraph_record_call (data, decl);
 111           walk_tree (&TREE_OPERAND (*tp, 1), record_call_1, data, NULL);
 112           *walk_subtrees = 0;
 113         }
 114     }
 115   return NULL;
 116 }
 117
 118 /* Create cgraph edges for function calles via BODY.  */
 119
 120 void
 121 cgraph_create_edges (decl, body)
 122      tree decl;
 123      tree body;
 124 {
 125   walk_tree (&body, record_call_1, decl, NULL);
 126 }
 127
 128 /* Analyze the whole compilation unit once it is parsed completely.  */
 129
 130 void
 131 cgraph_finalize_compilation_unit ()
 132 {
 133   struct cgraph_node *node;
 134   struct cgraph_edge *edge;
 135
 136   /* Collect entry points to the unit.  */
 137
 138   if (!quiet_flag)
 139     fprintf (stderr, "\n\nUnit entry points:");
 140
 141   for (node = cgraph_nodes; node; node = node->next)
 142     {
 143       tree decl = node->decl;
 144
 145       if (!DECL_SAVED_TREE (decl))
 146         continue;
 147       if ((TREE_PUBLIC (decl) && !DECL_COMDAT (decl) && !DECL_EXTERNAL (decl))
 148           || (DECL_ASSEMBLER_NAME_SET_P (decl)
 149               && TREE_SYMBOL_REFERENCED (DECL_ASSEMBLER_NAME (decl))))
 150         {
 151           cgraph_mark_needed_node (node, 1);
 152         }
 153     }
 154
 155   /*  Propagate reachability flag and lower representation of all reachable
 156       functions.  In the future, lowering will introduce new functions and
 157       new entry points on the way (by template instantiation and virtual
 158       method table generation for instance).  */
 159   while (queue)
 160     {
 161       tree decl = queue->decl;
 162
 163       node = queue;
 164       queue = queue->aux;
 165       if (node->lowered || !node->reachable || !DECL_SAVED_TREE (decl))
 166         abort ();
 167
 168       /* At the moment frontend automatically emits all nested functions.  */
 169       if (node->nested)
 170         {
 171           struct cgraph_node *node2;
 172
 173           for (node2 = node->nested; node2; node2 = node2->next_nested)
 174             if (!node2->reachable)
 175               cgraph_mark_needed_node (node2, 0);
 176         }
 177
 178       if (lang_hooks.callgraph.lower_function)
 179         (*lang_hooks.callgraph.lower_function) (decl);
 180       /* First kill forward declaration so reverse inling works properly.  */
 181       cgraph_create_edges (decl, DECL_SAVED_TREE (decl));
 182
 183       for (edge = node->callees; edge; edge = edge->next_callee)
 184         {
 185           if (!edge->callee->reachable)
 186             cgraph_mark_needed_node (edge->callee, 0);
 187         }
 188       node->lowered = true;
 189     }
 190   if (!quiet_flag)
 191     fprintf (stderr, "\n\nReclaiming functions:");
 192
 193   for (node = cgraph_nodes; node; node = node->next)
 194     {
 195       tree decl = node->decl;
 196
 197       if (!node->reachable && DECL_SAVED_TREE (decl))
 198         {
 199           DECL_SAVED_TREE (decl) = NULL;
 200           announce_function (decl);
 201         }
 202     }
 203   ggc_collect ();
 204 }
 205
 206 /* Figure out what functions we want to assemble.  */
 207
 208 static void
 209 cgraph_mark_functions_to_output ()
 210 {
 211   struct cgraph_node *node;
 212
 213   /* Figure out functions we want to assemble.  */
 214   for (node = cgraph_nodes; node; node = node->next)
 215     {
 216       tree decl = node->decl;
 217
 218       if (DECL_SAVED_TREE (decl)
 219           && (node->needed
 220               || (DECL_UNINLINABLE (decl) && node->reachable)
 221               || TREE_SYMBOL_REFERENCED (DECL_ASSEMBLER_NAME (decl)))
 222           && !TREE_ASM_WRITTEN (decl) && !node->origin
 223           && !DECL_EXTERNAL (decl))
 224         node->output = 1;
 225     }
 226 }
 227
 228 /* Expand function specified by NODE.  */
 229 static void
 230 cgraph_expand_function (node)
 231      struct cgraph_node *node;
 232 {
 233   tree decl = node->decl;
 234
 235   announce_function (decl);
 236   if (flag_inline_trees)
 237     optimize_inline_calls (decl);
 238   (*lang_hooks.callgraph.expand_function) (decl);
 239   if (DECL_UNINLINABLE (decl))
 240     DECL_SAVED_TREE (decl) = NULL;
 241   current_function_decl = NULL;
 242 }
 243
 244
 245 /* Expand all functions that must be output.
 246
 247    Attempt to topologically sort the nodes so function is output when
 248    all called functions are already assembled to allow data to be propagated
 249    accross the callgraph.  Use stack to get smaller distance between function
 250    and it's callees (later we may use more sophisticated algorithm for
 251    function reordering, we will likely want to use subsections to make output
 252    functions to appear in top-down order, not bottom-up they are assembled).  */
 253
 254 static void
 255 cgraph_expand_functions ()
 256 {
 257   struct cgraph_node *node, *node2;
 258   struct cgraph_node **stack =
 259     xcalloc (sizeof (struct cgraph_node *), cgraph_n_nodes);
 260   struct cgraph_node **order =
 261     xcalloc (sizeof (struct cgraph_node *), cgraph_n_nodes);
 262   int stack_size = 0;
 263   int order_pos = 0;
 264   struct cgraph_edge *edge, last;
 265   int i;
 266
 267   cgraph_mark_functions_to_output ();
 268
 269   /*  We have to deal with cycles nicely, so use depth first traversal
 270       algorithm.  Ignore the fact that some functions won't need to be output
 271       and put them into order as well, so we get dependencies right trought inlined
 272       functions.  */
 273   for (node = cgraph_nodes; node; node = node->next)
 274     node->aux = NULL;
 275   for (node = cgraph_nodes; node; node = node->next)
 276     if (node->output && !node->aux)
 277       {
 278         node2 = node;
 279         if (!node->callers)
 280           node->aux = &last;
 281         else
 282           node->aux = node->callers;
 283         while (node2)
 284           {
 285             while (node2->aux != &last)
 286               {
 287                 edge = node2->aux;
 288                 if (edge->next_caller)
 289                   node2->aux = edge->next_caller;
 290                 else
 291                   node2->aux = &last;
 292                 if (!edge->caller->aux)
 293                   {
 294                     if (!edge->caller->callers)
 295                       edge->caller->aux = &last;
 296                     else
 297                       edge->caller->aux = edge->caller->callers;
 298                     stack[stack_size++] = node2;
 299                     node2 = edge->caller;
 300                     break;
 301                   }
 302               }
 303             if (node2->aux == &last)
 304               {
 305                 order[order_pos++] = node2;
 306                 if (stack_size)
 307                   node2 = stack[--stack_size];
 308                 else
 309                   node2 = NULL;
 310               }
 311           }
 312       }
 313   for (i = order_pos - 1; i >=0; i--)
 314     {
 315       node = order[i];
 316       if (node->output)
 317         {
 318           if (!node->reachable)
 319             abort ();
 320           node->output = 0;
 321           cgraph_expand_function (node);
 322         }
 323     }
 324   free (stack);
 325   free (order);
 326 }
 327
 328 /* Perform simple optimizations based on callgraph.  */
 329
 330 void
 331 cgraph_optimize ()
 332 {
 333   struct cgraph_node *node;
 334   bool changed = true;
 335   struct cgraph_edge *edge;
 336
 337   if (!quiet_flag)
 338     fprintf (stderr, "\n\nAssembling functions:");
 339
 340   /* Output everything.
 341      ??? Our inline heuristic may decide to not inline functions previously
 342      marked as inlinable thus adding new function bodies that must be output.
 343      Later we should move all inlining decisions to callgraph code to make
 344      this impossible.  */
 345   cgraph_expand_functions ();
 346   while (changed)
 347     {
 348       changed = false;
 349       for (node = cgraph_nodes; node; node = node->next)
 350         {
 351           if (!node->needed)
 352             continue;
 353
 354           for (edge = node->callees; edge; edge = edge->next_callee)
 355             if (!edge->callee->needed)
 356               changed = edge->callee->needed = true;
 357         }
 358     }
 359   cgraph_expand_functions ();
 360 }