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