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