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 static void cgraph_mark_functions_to_inline_once PARAMS ((void));
  44 static void cgraph_optimize_function PARAMS ((struct cgraph_node *));
  45
  46 /* Analyze function once it is parsed.  Set up the local information
  47    available - create cgraph edges for function calls via BODY.  */
  48
  49 void
  50 cgraph_finalize_function (decl, body)
  51      tree decl;
  52      tree body ATTRIBUTE_UNUSED;
  53 {
  54   struct cgraph_node *node = cgraph_node (decl);
  55
  56   node->decl = decl;
  57   node->local.finalized = true;
  58
  59   if (/* Externally visible functions must be output.  The exception are
  60          COMDAT functions that must be output only when they are needed.
  61          Similarly are handled deferred functions and
  62          external functions (GCC extension "extern inline") */
  63       (TREE_PUBLIC (decl) && !DECL_COMDAT (decl) && !DECL_EXTERNAL (decl))
  64       /* ??? Constructors and destructors not called otherwise can be inlined
  65          into single construction/destruction function per section to save some
  66          resources.  For now just mark it as reachable.  */
  67       || DECL_STATIC_CONSTRUCTOR (decl)
  68       || DECL_STATIC_DESTRUCTOR (decl)
  69       /* Function whose name is output to the assembler file must be produced.
  70          It is possible to assemble the name later after finalizing the function
  71          and the fact is noticed in assemble_name then.  */
  72       || (DECL_ASSEMBLER_NAME_SET_P (decl)
  73           && TREE_SYMBOL_REFERENCED (DECL_ASSEMBLER_NAME (decl))))
  74     {
  75       cgraph_mark_needed_node (node, 1);
  76     }
  77
  78   (*debug_hooks->deferred_inline_function) (decl);
  79 }
  80
  81 /* Walk tree and record all calls.  Called via walk_tree.  */
  82 static tree
  83 record_call_1 (tp, walk_subtrees, data)
  84      tree *tp;
  85      int *walk_subtrees;
  86      void *data;
  87 {
  88   if (TREE_CODE (*tp) == VAR_DECL && TREE_STATIC (*tp))
  89     cgraph_varpool_mark_needed_node (cgraph_varpool_node (*tp));
  90   /* Record dereferences to the functions.  This makes the functions
  91      reachable unconditionally.  */
  92   else if (TREE_CODE (*tp) == ADDR_EXPR)
  93     {
  94       tree decl = TREE_OPERAND (*tp, 0);
  95       if (TREE_CODE (decl) == FUNCTION_DECL)
  96         cgraph_mark_needed_node (cgraph_node (decl), 1);
  97     }
  98   else if (TREE_CODE (*tp) == CALL_EXPR)
  99     {
 100       tree decl = get_callee_fndecl (*tp);
 101       if (decl && TREE_CODE (decl) == FUNCTION_DECL)
 102         {
 103           if (DECL_BUILT_IN (decl))
 104             return NULL;
 105           cgraph_record_call (data, decl);
 106
 107           /* When we see a function call, we don't want to look at the
 108              function reference in the ADDR_EXPR that is hanging from
 109              the CALL_EXPR we're examining here, because we would
 110              conclude incorrectly that the function's address could be
 111              taken by something that is not a function call.  So only
 112              walk the function parameter list, skip the other subtrees.  */
 113
 114           walk_tree (&TREE_OPERAND (*tp, 1), record_call_1, data, NULL);
 115           *walk_subtrees = 0;
 116         }
 117     }
 118   return NULL;
 119 }
 120
 121 /* Create cgraph edges for function calls inside BODY from DECL.  */
 122
 123 void
 124 cgraph_create_edges (decl, body)
 125      tree decl;
 126      tree body;
 127 {
 128   /* The nodes we're interested in are never shared, so walk
 129      the tree ignoring duplicates.  */
 130   walk_tree_without_duplicates (&body, record_call_1, decl);
 131 }
 132
 133 /* Analyze the whole compilation unit once it is parsed completely.  */
 134
 135 void
 136 cgraph_finalize_compilation_unit ()
 137 {
 138   struct cgraph_node *node;
 139   struct cgraph_edge *edge;
 140
 141   cgraph_varpool_assemble_pending_decls ();
 142
 143   if (!quiet_flag)
 144     {
 145       fprintf (stderr, "\n\nInitial entry points:");
 146       for (node = cgraph_nodes; node; node = node->next)
 147         if (node->needed && DECL_SAVED_TREE (node->decl))
 148           announce_function (node->decl);
 149     }
 150
 151   /* Propagate reachability flag and lower representation of all reachable
 152      functions.  In the future, lowering will introduce new functions and
 153      new entry points on the way (by template instantiation and virtual
 154      method table generation for instance).  */
 155   while (cgraph_nodes_queue)
 156     {
 157       tree decl = cgraph_nodes_queue->decl;
 158
 159       node = cgraph_nodes_queue;
 160       cgraph_nodes_queue = cgraph_nodes_queue->next_needed;
 161
 162       if (node->lowered || !node->reachable || !DECL_SAVED_TREE (decl))
 163         abort ();
 164
 165       if (lang_hooks.callgraph.lower_function)
 166         (*lang_hooks.callgraph.lower_function) (decl);
 167
 168       current_function_decl = node->decl;
 169       if (!node->needed && !DECL_COMDAT (node->decl))
 170         node->local.can_inline_once = tree_inlinable_function_p (decl, 1);
 171       else
 172         node->local.can_inline_once = 0;
 173       if (flag_inline_trees)
 174         node->local.inline_many = tree_inlinable_function_p (decl, 0);
 175       else
 176         node->local.inline_many = 0;
 177
 178       /* At the moment frontend automatically emits all nested functions.  */
 179       if (node->nested)
 180         {
 181           struct cgraph_node *node2;
 182
 183           for (node2 = node->nested; node2; node2 = node2->next_nested)
 184             if (!node2->reachable)
 185               cgraph_mark_needed_node (node2, 0);
 186         }
 187
 188       /* First kill forward declaration so reverse inling works properly.  */
 189       cgraph_create_edges (decl, DECL_SAVED_TREE (decl));
 190
 191       for (edge = node->callees; edge; edge = edge->next_callee)
 192         {
 193           if (!edge->callee->reachable)
 194             cgraph_mark_needed_node (edge->callee, 0);
 195         }
 196       node->lowered = true;
 197       cgraph_varpool_assemble_pending_decls ();
 198     }
 199   /* Collect entry points to the unit.  */
 200
 201   if (!quiet_flag)
 202     {
 203       fprintf (stderr, "\n\nUnit entry points:");
 204       for (node = cgraph_nodes; node; node = node->next)
 205         if (node->needed && DECL_SAVED_TREE (node->decl))
 206           announce_function (node->decl);
 207     }
 208
 209   if (!quiet_flag)
 210     fprintf (stderr, "\n\nReclaiming functions:");
 211
 212   for (node = cgraph_nodes; node; node = node->next)
 213     {
 214       tree decl = node->decl;
 215
 216       if (!node->reachable && DECL_SAVED_TREE (decl))
 217         {
 218           cgraph_remove_node (node);
 219           announce_function (decl);
 220         }
 221     }
 222   ggc_collect ();
 223 }
 224
 225 /* Figure out what functions we want to assemble.  */
 226
 227 static void
 228 cgraph_mark_functions_to_output ()
 229 {
 230   struct cgraph_node *node;
 231
 232   for (node = cgraph_nodes; node; node = node->next)
 233     {
 234       tree decl = node->decl;
 235
 236       /* We need to output all local functions that are used and not
 237          always inlined, as well as those that are reachable from
 238          outside the current compilation unit.  */
 239       if (DECL_SAVED_TREE (decl)
 240           && (node->needed
 241               || (!node->local.inline_many && !node->global.inline_once
 242                   && node->reachable)
 243               || (DECL_ASSEMBLER_NAME_SET_P (decl)
 244                   && TREE_SYMBOL_REFERENCED (DECL_ASSEMBLER_NAME (decl))))
 245           && !TREE_ASM_WRITTEN (decl) && !node->origin
 246           && !DECL_EXTERNAL (decl))
 247         node->output = 1;
 248     }
 249 }
 250
 251 /* Optimize the function before expansion.  */
 252
 253 static void
 254 cgraph_optimize_function (node)
 255      struct cgraph_node *node;
 256 {
 257   tree decl = node->decl;
 258
 259   if (flag_inline_trees)
 260     optimize_inline_calls (decl);
 261   if (node->nested)
 262     {
 263       for (node = node->nested; node; node = node->next_nested)
 264         cgraph_optimize_function (node);
 265     }
 266 }
 267
 268 /* Expand function specified by NODE.  */
 269
 270 static void
 271 cgraph_expand_function (node)
 272      struct cgraph_node *node;
 273 {
 274   tree decl = node->decl;
 275
 276   announce_function (decl);
 277
 278   cgraph_optimize_function (node);
 279
 280   /* Generate RTL for the body of DECL.  Nested functions are expanded
 281      via lang_expand_decl_stmt.  */
 282   (*lang_hooks.callgraph.expand_function) (decl);
 283
 284   /* When we decided to inline the function once, we never ever should
 285      need to output it separately.  */
 286   if (node->global.inline_once)
 287     abort ();
 288   if (!node->local.inline_many
 289       || !node->callers)
 290     DECL_SAVED_TREE (decl) = NULL;
 291   current_function_decl = NULL;
 292 }
 293
 294
 295 /* Expand all functions that must be output.
 296
 297    Attempt to topologically sort the nodes so function is output when
 298    all called functions are already assembled to allow data to be
 299    propagated across the callgraph.  Use a stack to get smaller distance
 300    between a function and it's callees (later we may choose to use a more
 301    sophisticated algorithm for function reordering; we will likely want
 302    to use subsections to make the output functions appear in top-down
 303    order.  */
 304
 305 static void
 306 cgraph_expand_functions ()
 307 {
 308   struct cgraph_node *node, *node2;
 309   struct cgraph_node **stack =
 310     xcalloc (sizeof (struct cgraph_node *), cgraph_n_nodes);
 311   struct cgraph_node **order =
 312     xcalloc (sizeof (struct cgraph_node *), cgraph_n_nodes);
 313   int stack_size = 0;
 314   int order_pos = 0;
 315   struct cgraph_edge *edge, last;
 316   int i;
 317
 318   cgraph_mark_functions_to_output ();
 319
 320   /* We have to deal with cycles nicely, so use a depth first traversal
 321      output algorithm.  Ignore the fact that some functions won't need
 322      to be output and put them into order as well, so we get dependencies
 323      right through intline functions.  */
 324   for (node = cgraph_nodes; node; node = node->next)
 325     node->aux = NULL;
 326   for (node = cgraph_nodes; node; node = node->next)
 327     if (!node->aux)
 328       {
 329         node2 = node;
 330         if (!node->callers)
 331           node->aux = &last;
 332         else
 333           node->aux = node->callers;
 334         while (node2)
 335           {
 336             while (node2->aux != &last)
 337               {
 338                 edge = node2->aux;
 339                 if (edge->next_caller)
 340                   node2->aux = edge->next_caller;
 341                 else
 342                   node2->aux = &last;
 343                 if (!edge->caller->aux)
 344                   {
 345                     if (!edge->caller->callers)
 346                       edge->caller->aux = &last;
 347                     else
 348                       edge->caller->aux = edge->caller->callers;
 349                     stack[stack_size++] = node2;
 350                     node2 = edge->caller;
 351                     break;
 352                   }
 353               }
 354             if (node2->aux == &last)
 355               {
 356                 order[order_pos++] = node2;
 357                 if (stack_size)
 358                   node2 = stack[--stack_size];
 359                 else
 360                   node2 = NULL;
 361               }
 362           }
 363       }
 364   for (i = order_pos - 1; i >= 0; i--)
 365     {
 366       node = order[i];
 367       if (node->output)
 368         {
 369           if (!node->reachable)
 370             abort ();
 371           node->output = 0;
 372           cgraph_expand_function (node);
 373         }
 374     }
 375   free (stack);
 376   free (order);
 377 }
 378
 379 /* Mark all local functions.
 380    We can not use node->needed directly as it is modified during
 381    execution of cgraph_optimize.  */
 382
 383 static void
 384 cgraph_mark_local_functions ()
 385 {
 386   struct cgraph_node *node;
 387
 388   if (!quiet_flag)
 389     fprintf (stderr, "\n\nMarking local functions:");
 390
 391   /* Figure out functions we want to assemble.  */
 392   for (node = cgraph_nodes; node; node = node->next)
 393     {
 394       node->local.local = (!node->needed
 395                            && DECL_SAVED_TREE (node->decl)
 396                            && !DECL_COMDAT (node->decl)
 397                            && !TREE_PUBLIC (node->decl));
 398       if (node->local.local)
 399         announce_function (node->decl);
 400     }
 401 }
 402
 403 /* Decide what function should be inlined because they are invoked once
 404    (so inlining won't result in duplication of the code).  */
 405
 406 static void
 407 cgraph_mark_functions_to_inline_once ()
 408 {
 409   struct cgraph_node *node, *node1;
 410
 411   if (!quiet_flag)
 412     fprintf (stderr, "\n\nMarking functions to inline once:");
 413
 414   /* Now look for function called only once and mark them to inline.
 415      From this point number of calls to given function won't grow.  */
 416   for (node = cgraph_nodes; node; node = node->next)
 417     {
 418       if (node->callers && !node->callers->next_caller && !node->needed
 419           && node->local.can_inline_once)
 420         {
 421           bool ok = true;
 422
 423           /* Verify that we won't duplicate the caller.  */
 424           for (node1 = node->callers->caller;
 425                node1->local.inline_many
 426                && node1->callers
 427                && ok;
 428                node1 = node1->callers->caller)
 429             if (node1->callers->next_caller || node1->needed)
 430               ok = false;
 431           if (ok)
 432             {
 433               node->global.inline_once = true;
 434               announce_function (node->decl);
 435             }
 436         }
 437     }
 438 }
 439
 440
 441 /* Perform simple optimizations based on callgraph.  */
 442
 443 void
 444 cgraph_optimize ()
 445 {
 446   struct cgraph_node *node;
 447   bool changed = true;
 448
 449   cgraph_mark_local_functions ();
 450
 451   cgraph_mark_functions_to_inline_once ();
 452
 453   cgraph_global_info_ready = true;
 454   if (!quiet_flag)
 455     fprintf (stderr, "\n\nAssembling functions:");
 456
 457   /* Output everything.
 458      ??? Our inline heuristic may decide to not inline functions previously
 459      marked as inlinable thus adding new function bodies that must be output.
 460      Later we should move all inlining decisions to callgraph code to make
 461      this impossible.  */
 462   cgraph_expand_functions ();
 463   if (!quiet_flag)
 464     fprintf (stderr, "\n\nAssembling functions that failed to inline:");
 465   while (changed && !errorcount && !sorrycount)
 466     {
 467       changed = false;
 468       for (node = cgraph_nodes; node; node = node->next)
 469         {
 470           tree decl = node->decl;
 471           if (!node->origin
 472               && !TREE_ASM_WRITTEN (decl)
 473               && DECL_SAVED_TREE (decl)
 474               && !DECL_EXTERNAL (decl))
 475             {
 476               struct cgraph_edge *edge;
 477
 478               for (edge = node->callers; edge; edge = edge->next_caller)
 479                 if (TREE_ASM_WRITTEN (edge->caller->decl))
 480                   {
 481                     changed = true;
 482                     cgraph_expand_function (node);
 483                     break;
 484                   }
 485             }
 486         }
 487     }
 488 }