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