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