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       if (!node->needed && !DECL_COMDAT (node->decl))
 169         node->local.can_inline_once = tree_inlinable_function_p (decl, 1);
 170       else
 171         node->local.can_inline_once = 0;
 172       if (flag_inline_trees)
 173         node->local.inline_many = tree_inlinable_function_p (decl, 0);
 174       else
 175         node->local.inline_many = 0;
 176
 177       /* At the moment frontend automatically emits all nested functions.  */
 178       if (node->nested)
 179         {
 180           struct cgraph_node *node2;
 181
 182           for (node2 = node->nested; node2; node2 = node2->next_nested)
 183             if (!node2->reachable)
 184               cgraph_mark_needed_node (node2, 0);
 185         }
 186
 187       /* First kill forward declaration so reverse inling works properly.  */
 188       cgraph_create_edges (decl, DECL_SAVED_TREE (decl));
 189
 190       for (edge = node->callees; edge; edge = edge->next_callee)
 191         {
 192           if (!edge->callee->reachable)
 193             cgraph_mark_needed_node (edge->callee, 0);
 194         }
 195       node->lowered = true;
 196       cgraph_varpool_assemble_pending_decls ();
 197     }
 198   /* Collect entry points to the unit.  */
 199
 200   if (!quiet_flag)
 201     {
 202       fprintf (stderr, "\n\nUnit entry points:");
 203       for (node = cgraph_nodes; node; node = node->next)
 204         if (node->needed && DECL_SAVED_TREE (node->decl))
 205           announce_function (node->decl);
 206     }
 207
 208   if (!quiet_flag)
 209     fprintf (stderr, "\n\nReclaiming functions:");
 210
 211   for (node = cgraph_nodes; node; node = node->next)
 212     {
 213       tree decl = node->decl;
 214
 215       if (!node->reachable && DECL_SAVED_TREE (decl))
 216         {
 217           cgraph_remove_node (node);
 218           announce_function (decl);
 219         }
 220     }
 221   ggc_collect ();
 222 }
 223
 224 /* Figure out what functions we want to assemble.  */
 225
 226 static void
 227 cgraph_mark_functions_to_output ()
 228 {
 229   struct cgraph_node *node;
 230
 231   for (node = cgraph_nodes; node; node = node->next)
 232     {
 233       tree decl = node->decl;
 234
 235       /* We need to output all local functions that are used and not
 236          always inlined, as well as those that are reachable from
 237          outside the current compilation unit.  */
 238       if (DECL_SAVED_TREE (decl)
 239           && (node->needed
 240               || (!node->local.inline_many && !node->global.inline_once
 241                   && node->reachable)
 242               || (DECL_ASSEMBLER_NAME_SET_P (decl)
 243                   && TREE_SYMBOL_REFERENCED (DECL_ASSEMBLER_NAME (decl))))
 244           && !TREE_ASM_WRITTEN (decl) && !node->origin
 245           && !DECL_EXTERNAL (decl))
 246         node->output = 1;
 247     }
 248 }
 249
 250 /* Optimize the function before expansion.  */
 251
 252 static void
 253 cgraph_optimize_function (node)
 254      struct cgraph_node *node;
 255 {
 256   tree decl = node->decl;
 257
 258   if (flag_inline_trees)
 259     optimize_inline_calls (decl);
 260   if (node->nested)
 261     {
 262       for (node = node->nested; node; node = node->next_nested)
 263         cgraph_optimize_function (node);
 264     }
 265 }
 266
 267 /* Expand function specified by NODE.  */
 268
 269 static void
 270 cgraph_expand_function (node)
 271      struct cgraph_node *node;
 272 {
 273   tree decl = node->decl;
 274
 275   announce_function (decl);
 276
 277   cgraph_optimize_function (node);
 278
 279   /* Generate RTL for the body of DECL.  Nested functions are expanded
 280      via lang_expand_decl_stmt.  */
 281   (*lang_hooks.callgraph.expand_function) (decl);
 282
 283   /* When we decided to inline the function once, we never ever should
 284      need to output it separately.  */
 285   if (node->global.inline_once)
 286     abort ();
 287   if (!node->local.inline_many
 288       || !node->callers)
 289     DECL_SAVED_TREE (decl) = NULL;
 290   current_function_decl = NULL;
 291 }
 292
 293
 294 /* Expand all functions that must be output.
 295
 296    Attempt to topologically sort the nodes so function is output when
 297    all called functions are already assembled to allow data to be
 298    propagated across the callgraph.  Use a stack to get smaller distance
 299    between a function and it's callees (later we may choose to use a more
 300    sophisticated algorithm for function reordering; we will likely want
 301    to use subsections to make the output functions appear in top-down
 302    order.  */
 303
 304 static void
 305 cgraph_expand_functions ()
 306 {
 307   struct cgraph_node *node, *node2;
 308   struct cgraph_node **stack =
 309     xcalloc (sizeof (struct cgraph_node *), cgraph_n_nodes);
 310   struct cgraph_node **order =
 311     xcalloc (sizeof (struct cgraph_node *), cgraph_n_nodes);
 312   int stack_size = 0;
 313   int order_pos = 0;
 314   struct cgraph_edge *edge, last;
 315   int i;
 316
 317   cgraph_mark_functions_to_output ();
 318
 319   /* We have to deal with cycles nicely, so use a depth first traversal
 320      output algorithm.  Ignore the fact that some functions won't need
 321      to be output and put them into order as well, so we get dependencies
 322      right through intline functions.  */
 323   for (node = cgraph_nodes; node; node = node->next)
 324     node->aux = NULL;
 325   for (node = cgraph_nodes; node; node = node->next)
 326     if (!node->aux)
 327       {
 328         node2 = node;
 329         if (!node->callers)
 330           node->aux = &last;
 331         else
 332           node->aux = node->callers;
 333         while (node2)
 334           {
 335             while (node2->aux != &last)
 336               {
 337                 edge = node2->aux;
 338                 if (edge->next_caller)
 339                   node2->aux = edge->next_caller;
 340                 else
 341                   node2->aux = &last;
 342                 if (!edge->caller->aux)
 343                   {
 344                     if (!edge->caller->callers)
 345                       edge->caller->aux = &last;
 346                     else
 347                       edge->caller->aux = edge->caller->callers;
 348                     stack[stack_size++] = node2;
 349                     node2 = edge->caller;
 350                     break;
 351                   }
 352               }
 353             if (node2->aux == &last)
 354               {
 355                 order[order_pos++] = node2;
 356                 if (stack_size)
 357                   node2 = stack[--stack_size];
 358                 else
 359                   node2 = NULL;
 360               }
 361           }
 362       }
 363   for (i = order_pos - 1; i >= 0; i--)
 364     {
 365       node = order[i];
 366       if (node->output)
 367         {
 368           if (!node->reachable)
 369             abort ();
 370           node->output = 0;
 371           cgraph_expand_function (node);
 372         }
 373     }
 374   free (stack);
 375   free (order);
 376 }
 377
 378 /* Mark all local functions.
 379    We can not use node->needed directly as it is modified during
 380    execution of cgraph_optimize.  */
 381
 382 static void
 383 cgraph_mark_local_functions ()
 384 {
 385   struct cgraph_node *node;
 386
 387   if (!quiet_flag)
 388     fprintf (stderr, "\n\nMarking local functions:");
 389
 390   /* Figure out functions we want to assemble.  */
 391   for (node = cgraph_nodes; node; node = node->next)
 392     {
 393       node->local.local = (!node->needed
 394                            && DECL_SAVED_TREE (node->decl)
 395                            && !DECL_COMDAT (node->decl)
 396                            && !TREE_PUBLIC (node->decl));
 397       if (node->local.local)
 398         announce_function (node->decl);
 399     }
 400 }
 401
 402 /* Decide what function should be inlined because they are invoked once
 403    (so inlining won't result in duplication of the code).  */
 404
 405 static void
 406 cgraph_mark_functions_to_inline_once ()
 407 {
 408   struct cgraph_node *node, *node1;
 409
 410   if (!quiet_flag)
 411     fprintf (stderr, "\n\nMarking functions to inline once:");
 412
 413   /* Now look for function called only once and mark them to inline.
 414      From this point number of calls to given function won't grow.  */
 415   for (node = cgraph_nodes; node; node = node->next)
 416     {
 417       if (node->callers && !node->callers->next_caller && !node->needed
 418           && node->local.can_inline_once)
 419         {
 420           bool ok = true;
 421
 422           /* Verify that we won't duplicate the caller.  */
 423           for (node1 = node->callers->caller;
 424                node1->local.inline_many
 425                && node1->callers
 426                && ok;
 427                node1 = node1->callers->caller)
 428             if (node1->callers->next_caller || node1->needed)
 429               ok = false;
 430           if (ok)
 431             {
 432               node->global.inline_once = true;
 433               announce_function (node->decl);
 434             }
 435         }
 436     }
 437 }
 438
 439
 440 /* Perform simple optimizations based on callgraph.  */
 441
 442 void
 443 cgraph_optimize ()
 444 {
 445   struct cgraph_node *node;
 446   bool changed = true;
 447
 448   cgraph_mark_local_functions ();
 449
 450   cgraph_mark_functions_to_inline_once ();
 451
 452   cgraph_global_info_ready = true;
 453   if (!quiet_flag)
 454     fprintf (stderr, "\n\nAssembling functions:");
 455
 456   /* Output everything.
 457      ??? Our inline heuristic may decide to not inline functions previously
 458      marked as inlinable thus adding new function bodies that must be output.
 459      Later we should move all inlining decisions to callgraph code to make
 460      this impossible.  */
 461   cgraph_expand_functions ();
 462   if (!quiet_flag)
 463     fprintf (stderr, "\n\nAssembling functions that failed to inline:");
 464   while (changed && !errorcount && !sorrycount)
 465     {
 466       changed = false;
 467       for (node = cgraph_nodes; node; node = node->next)
 468         {
 469           tree decl = node->decl;
 470           if (!node->origin
 471               && !TREE_ASM_WRITTEN (decl)
 472               && DECL_SAVED_TREE (decl)
 473               && !DECL_EXTERNAL (decl))
 474             {
 475               struct cgraph_edge *edge;
 476
 477               for (edge = node->callers; edge; edge = edge->next_caller)
 478                 if (TREE_ASM_WRITTEN (edge->caller->decl))
 479                   {
 480                     changed = true;
 481                     cgraph_expand_function (node);
 482                     break;
 483                   }
 484             }
 485         }
 486     }
 487 }