gcc/cgraphunit.c

   1 /* Callgraph based intraprocedural optimizations.
   2    Copyright (C) 2003, 2004 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 #include "params.h"
  39 #include "fibheap.h"
  40 #include "c-common.h"
  41
  42 #define INSNS_PER_CALL 10
  43
  44 static void cgraph_expand_all_functions (void);
  45 static void cgraph_mark_functions_to_output (void);
  46 static void cgraph_expand_function (struct cgraph_node *);
  47 static tree record_call_1 (tree *, int *, void *);
  48 static void cgraph_mark_local_functions (void);
  49 static void cgraph_optimize_function (struct cgraph_node *);
  50 static bool cgraph_default_inline_p (struct cgraph_node *n);
  51 static void cgraph_analyze_function (struct cgraph_node *node);
  52 static void cgraph_decide_inlining_incrementally (struct cgraph_node *);
  53
  54 /* Statistics we collect about inlining algorithm.  */
  55 static int ncalls_inlined;
  56 static int nfunctions_inlined;
  57 static int initial_insns;
  58 static int overall_insns;
  59
  60 /* Records tree nodes seen in cgraph_create_edges.  Simply using
  61    walk_tree_without_duplicates doesn't guarantee each node is visited
  62    once because it gets a new htab upon each recursive call from
  63    record_calls_1.  */
  64 static htab_t visited_nodes;
  65
  66 /* Determine if function DECL is needed.  That is, visible to something
  67    either outside this translation unit, something magic in the system
  68    configury, or (if not doing unit-at-a-time) to something we havn't
  69    seen yet.  */
  70
  71 static bool
  72 decide_is_function_needed (struct cgraph_node *node, tree decl)
  73 {
  74   /* If we decided it was needed before, but at the time we didn't have
  75      the body of the function available, then it's still needed.  We have
  76      to go back and re-check its dependencies now.  */
  77   if (node->needed)
  78     return true;
  79
  80   /* Externally visible functions must be output.  The exception is
  81      COMDAT functions that must be output only when they are needed.  */
  82   if (TREE_PUBLIC (decl) && !DECL_COMDAT (decl) && !DECL_EXTERNAL (decl))
  83     return true;
  84
  85   /* Constructors and destructors are reachable from the runtime by
  86      some mechanism.  */
  87   if (DECL_STATIC_CONSTRUCTOR (decl) || DECL_STATIC_DESTRUCTOR (decl))
  88     return true;
  89
  90   /* If the user told us it is used, then it must be so.  */
  91   if (lookup_attribute ("used", DECL_ATTRIBUTES (decl)))
  92     return true;
  93
  94   /* ??? If the assembler name is set by hand, it is possible to assemble
  95      the name later after finalizing the function and the fact is noticed
  96      in assemble_name then.  This is arguably a bug.  */
  97   if (DECL_ASSEMBLER_NAME_SET_P (decl)
  98       && TREE_SYMBOL_REFERENCED (DECL_ASSEMBLER_NAME (decl)))
  99     return true;
 100
 101   if (flag_unit_at_a_time)
 102     return false;
 103
 104   /* If not doing unit at a time, then we'll only defer this function
 105      if its marked for inlining.  Otherwise we want to emit it now.  */
 106
 107   /* "extern inline" functions are never output locally.  */
 108   if (DECL_EXTERNAL (decl))
 109     return false;
 110   /* We want to emit COMDAT functions only when absolutely necessary.  */
 111   if (DECL_COMDAT (decl))
 112     return false;
 113   if (!DECL_INLINE (decl)
 114       || (!node->local.disregard_inline_limits
 115           /* When declared inline, defer even the uninlinable functions.
 116              This allows them to be eliminated when unused.  */
 117           && !DECL_DECLARED_INLINE_P (decl)
 118           && (!node->local.inlinable || !cgraph_default_inline_p (node))))
 119     return true;
 120
 121   return false;
 122 }
 123
 124 /* When not doing unit-at-a-time, output all functions enqueued.
 125    Return true when such a functions were found.  */
 126
 127 bool
 128 cgraph_assemble_pending_functions (void)
 129 {
 130   bool output = false;
 131
 132   if (flag_unit_at_a_time)
 133     return false;
 134
 135   while (cgraph_nodes_queue)
 136     {
 137       struct cgraph_node *n = cgraph_nodes_queue;
 138
 139       cgraph_nodes_queue = cgraph_nodes_queue->next_needed;
 140       if (!n->origin && !DECL_EXTERNAL (n->decl))
 141         {
 142           cgraph_expand_function (n);
 143           output = true;
 144         }
 145     }
 146
 147   return output;
 148 }
 149
 150 /* DECL has been parsed.  Take it, queue it, compile it at the whim of the
 151    logic in effect.  If NESTED is true, then our caller cannot stand to have
 152    the garbage collector run at the moment.  We would need to either create
 153    a new GC context, or just not compile right now.  */
 154
 155 void
 156 cgraph_finalize_function (tree decl, bool nested)
 157 {
 158   struct cgraph_node *node = cgraph_node (decl);
 159
 160   if (node->local.finalized)
 161     {
 162       /* As an GCC extension we allow redefinition of the function.  The
 163          semantics when both copies of bodies differ is not well defined.
 164          We replace the old body with new body so in unit at a time mode
 165          we always use new body, while in normal mode we may end up with
 166          old body inlined into some functions and new body expanded and
 167          inlined in others.
 168
 169          ??? It may make more sense to use one body for inlining and other
 170          body for expanding the function but this is difficult to do.  */
 171
 172       /* If node->output is set, then this is a unit-at-a-time compilation
 173          and we have already begun whole-unit analysis.  This is *not*
 174          testing for whether we've already emitted the function.  That
 175          case can be sort-of legitimately seen with real function
 176          redefinition errors.  I would argue that the front end should
 177          never present us with such a case, but don't enforce that for now.  */
 178       if (node->output)
 179         abort ();
 180
 181       /* Reset our datastructures so we can analyze the function again.  */
 182       memset (&node->local, 0, sizeof (node->local));
 183       memset (&node->global, 0, sizeof (node->global));
 184       memset (&node->rtl, 0, sizeof (node->rtl));
 185       node->analyzed = false;
 186       while (node->callees)
 187         cgraph_remove_edge (node, node->callees->callee);
 188
 189       /* We may need to re-queue the node for assembling in case
 190          we already proceeded it and ignored as not needed.  */
 191       if (node->reachable && !flag_unit_at_a_time)
 192         {
 193           struct cgraph_node *n;
 194
 195           for (n = cgraph_nodes_queue; n; n = n->next_needed)
 196             if (n == node)
 197               break;
 198           if (!n)
 199             node->reachable = 0;
 200         }
 201     }
 202
 203   notice_global_symbol (decl);
 204   node->decl = decl;
 205   node->local.finalized = true;
 206
 207   /* If not unit at a time, then we need to create the call graph
 208      now, so that called functions can be queued and emitted now.  */
 209   if (!flag_unit_at_a_time)
 210     {
 211       cgraph_analyze_function (node);
 212       cgraph_decide_inlining_incrementally (node);
 213     }
 214
 215   if (decide_is_function_needed (node, decl))
 216     cgraph_mark_needed_node (node);
 217
 218   /* If not unit at a time, go ahead and emit everything we've found
 219      to be reachable at this time.  */
 220   if (!nested)
 221     cgraph_assemble_pending_functions ();
 222
 223   /* If we've not yet emitted decl, tell the debug info about it.  */
 224   if (!TREE_ASM_WRITTEN (decl))
 225     (*debug_hooks->deferred_inline_function) (decl);
 226 }
 227
 228 /* Walk tree and record all calls.  Called via walk_tree.  */
 229 static tree
 230 record_call_1 (tree *tp, int *walk_subtrees, void *data)
 231 {
 232   tree t = *tp;
 233
 234   switch (TREE_CODE (t))
 235     {
 236     case VAR_DECL:
 237       /* ??? Really, we should mark this decl as *potentially* referenced
 238          by this function and re-examine whether the decl is actually used
 239          after rtl has been generated.  */
 240       if (TREE_STATIC (t))
 241         cgraph_varpool_mark_needed_node (cgraph_varpool_node (t));
 242       break;
 243
 244     case ADDR_EXPR:
 245       if (flag_unit_at_a_time)
 246         {
 247           /* Record dereferences to the functions.  This makes the
 248              functions reachable unconditionally.  */
 249           tree decl = TREE_OPERAND (*tp, 0);
 250           if (TREE_CODE (decl) == FUNCTION_DECL)
 251             cgraph_mark_needed_node (cgraph_node (decl));
 252         }
 253       break;
 254
 255     case CALL_EXPR:
 256       {
 257         tree decl = get_callee_fndecl (*tp);
 258         if (decl && TREE_CODE (decl) == FUNCTION_DECL)
 259           {
 260             if (DECL_BUILT_IN (decl))
 261               return NULL;
 262             cgraph_record_call (data, decl);
 263
 264             /* When we see a function call, we don't want to look at the
 265                function reference in the ADDR_EXPR that is hanging from
 266                the CALL_EXPR we're examining here, because we would
 267                conclude incorrectly that the function's address could be
 268                taken by something that is not a function call.  So only
 269                walk the function parameter list, skip the other subtrees.  */
 270
 271             walk_tree (&TREE_OPERAND (*tp, 1), record_call_1, data,
 272                        visited_nodes);
 273             *walk_subtrees = 0;
 274           }
 275         break;
 276       }
 277
 278     default:
 279       /* Save some cycles by not walking types and declaration as we
 280          won't find anything useful there anyway.  */
 281       if (DECL_P (*tp) || TYPE_P (*tp))
 282         {
 283           *walk_subtrees = 0;
 284           break;
 285         }
 286
 287       if ((unsigned int) TREE_CODE (t) >= LAST_AND_UNUSED_TREE_CODE)
 288         return (*lang_hooks.callgraph.analyze_expr) (tp, walk_subtrees, data);
 289       break;
 290     }
 291
 292   return NULL;
 293 }
 294
 295 /* Create cgraph edges for function calls inside BODY from DECL.  */
 296
 297 void
 298 cgraph_create_edges (tree decl, tree body)
 299 {
 300   /* The nodes we're interested in are never shared, so walk
 301      the tree ignoring duplicates.  */
 302   visited_nodes = htab_create (37, htab_hash_pointer,
 303                                     htab_eq_pointer, NULL);
 304   walk_tree (&body, record_call_1, decl, visited_nodes);
 305   htab_delete (visited_nodes);
 306   visited_nodes = NULL;
 307 }
 308
 309 /* Analyze the function scheduled to be output.  */
 310 static void
 311 cgraph_analyze_function (struct cgraph_node *node)
 312 {
 313   tree decl = node->decl;
 314
 315   current_function_decl = decl;
 316
 317   /* First kill forward declaration so reverse inlining works properly.  */
 318   cgraph_create_edges (decl, DECL_SAVED_TREE (decl));
 319
 320   node->local.inlinable = tree_inlinable_function_p (decl);
 321   if (!DECL_ESTIMATED_INSNS (decl))
 322     DECL_ESTIMATED_INSNS (decl)
 323       = (*lang_hooks.tree_inlining.estimate_num_insns) (decl);
 324   node->local.self_insns = DECL_ESTIMATED_INSNS (decl);
 325   if (node->local.inlinable)
 326     node->local.disregard_inline_limits
 327       = (*lang_hooks.tree_inlining.disregard_inline_limits) (decl);
 328   if (flag_really_no_inline && !node->local.disregard_inline_limits)
 329     node->local.inlinable = 0;
 330   /* Inlining characteristics are maintained by the cgraph_mark_inline.  */
 331   node->global.insns = node->local.self_insns;
 332   if (!DECL_EXTERNAL (decl))
 333     {
 334       node->global.cloned_times = 1;
 335       node->global.will_be_output = true;
 336     }
 337
 338   node->analyzed = true;
 339   current_function_decl = NULL;
 340 }
 341
 342 /* Analyze the whole compilation unit once it is parsed completely.  */
 343
 344 void
 345 cgraph_finalize_compilation_unit (void)
 346 {
 347   struct cgraph_node *node;
 348
 349   if (!flag_unit_at_a_time)
 350     {
 351       cgraph_assemble_pending_functions ();
 352       return;
 353     }
 354
 355   cgraph_varpool_assemble_pending_decls ();
 356   if (!quiet_flag)
 357     fprintf (stderr, "\nAnalyzing compilation unit\n");
 358
 359   timevar_push (TV_CGRAPH);
 360   if (cgraph_dump_file)
 361     {
 362       fprintf (cgraph_dump_file, "Initial entry points:");
 363       for (node = cgraph_nodes; node; node = node->next)
 364         if (node->needed && DECL_SAVED_TREE (node->decl))
 365           fprintf (cgraph_dump_file, " %s", cgraph_node_name (node));
 366       fprintf (cgraph_dump_file, "\n");
 367     }
 368
 369   /* Propagate reachability flag and lower representation of all reachable
 370      functions.  In the future, lowering will introduce new functions and
 371      new entry points on the way (by template instantiation and virtual
 372      method table generation for instance).  */
 373   while (cgraph_nodes_queue)
 374     {
 375       struct cgraph_edge *edge;
 376       tree decl = cgraph_nodes_queue->decl;
 377
 378       node = cgraph_nodes_queue;
 379       cgraph_nodes_queue = cgraph_nodes_queue->next_needed;
 380
 381       /* ??? It is possible to create extern inline function and later using
 382          weak alas attribute to kill it's body. See
 383          gcc.c-torture/compile/20011119-1.c  */
 384       if (!DECL_SAVED_TREE (decl))
 385         continue;
 386
 387       if (node->analyzed || !node->reachable || !DECL_SAVED_TREE (decl))
 388         abort ();
 389
 390       cgraph_analyze_function (node);
 391
 392       for (edge = node->callees; edge; edge = edge->next_callee)
 393         if (!edge->callee->reachable)
 394           cgraph_mark_reachable_node (edge->callee);
 395
 396       cgraph_varpool_assemble_pending_decls ();
 397     }
 398
 399   /* Collect entry points to the unit.  */
 400
 401   if (cgraph_dump_file)
 402     {
 403       fprintf (cgraph_dump_file, "Unit entry points:");
 404       for (node = cgraph_nodes; node; node = node->next)
 405         if (node->needed && DECL_SAVED_TREE (node->decl))
 406           fprintf (cgraph_dump_file, " %s", cgraph_node_name (node));
 407       fprintf (cgraph_dump_file, "\n\nInitial ");
 408       dump_cgraph (cgraph_dump_file);
 409     }
 410
 411   if (cgraph_dump_file)
 412     fprintf (cgraph_dump_file, "\nReclaiming functions:");
 413
 414   for (node = cgraph_nodes; node; node = node->next)
 415     {
 416       tree decl = node->decl;
 417
 418       if (!node->reachable && DECL_SAVED_TREE (decl))
 419         {
 420           cgraph_remove_node (node);
 421           if (cgraph_dump_file)
 422             fprintf (cgraph_dump_file, " %s", cgraph_node_name (node));
 423         }
 424     }
 425   if (cgraph_dump_file)
 426     {
 427       fprintf (cgraph_dump_file, "\n\nReclaimed ");
 428       dump_cgraph (cgraph_dump_file);
 429     }
 430   ggc_collect ();
 431   timevar_pop (TV_CGRAPH);
 432 }
 433
 434 /* Figure out what functions we want to assemble.  */
 435
 436 static void
 437 cgraph_mark_functions_to_output (void)
 438 {
 439   struct cgraph_node *node;
 440
 441   for (node = cgraph_nodes; node; node = node->next)
 442     {
 443       tree decl = node->decl;
 444       struct cgraph_edge *e;
 445       if (node->output)
 446         abort ();
 447
 448       for (e = node->callers; e; e = e->next_caller)
 449         if (!e->inline_call)
 450           break;
 451
 452       /* We need to output all local functions that are used and not
 453          always inlined, as well as those that are reachable from
 454          outside the current compilation unit.  */
 455       if (DECL_SAVED_TREE (decl)
 456           && (node->needed
 457               || (e && node->reachable))
 458           && !TREE_ASM_WRITTEN (decl) && !node->origin
 459           && !DECL_EXTERNAL (decl))
 460         node->output = 1;
 461     }
 462 }
 463
 464 /* Optimize the function before expansion.  */
 465
 466 static void
 467 cgraph_optimize_function (struct cgraph_node *node)
 468 {
 469   tree decl = node->decl;
 470
 471   timevar_push (TV_INTEGRATION);
 472   /* optimize_inline_calls avoids inlining of current_function_decl.  */
 473   current_function_decl = decl;
 474   if (flag_inline_trees)
 475     {
 476       struct cgraph_edge *e;
 477
 478       for (e = node->callees; e; e = e->next_callee)
 479         if (e->inline_call)
 480           break;
 481       if (e)
 482         optimize_inline_calls (decl);
 483     }
 484   if (node->nested)
 485     {
 486       for (node = node->nested; node; node = node->next_nested)
 487         cgraph_optimize_function (node);
 488     }
 489   timevar_pop (TV_INTEGRATION);
 490 }
 491
 492 /* Expand function specified by NODE.  */
 493
 494 static void
 495 cgraph_expand_function (struct cgraph_node *node)
 496 {
 497   tree decl = node->decl;
 498
 499   if (flag_unit_at_a_time)
 500     announce_function (decl);
 501
 502   cgraph_optimize_function (node);
 503
 504   /* Generate RTL for the body of DECL.  Nested functions are expanded
 505      via lang_expand_decl_stmt.  */
 506   (*lang_hooks.callgraph.expand_function) (decl);
 507
 508   if (!cgraph_function_possibly_inlined_p (decl))
 509     DECL_SAVED_TREE (decl) = NULL;
 510   current_function_decl = NULL;
 511 }
 512
 513 /* Fill array order with all nodes with output flag set in the reverse
 514    topological order.  */
 515 static int
 516 cgraph_postorder (struct cgraph_node **order)
 517 {
 518   struct cgraph_node *node, *node2;
 519   int stack_size = 0;
 520   int order_pos = 0;
 521   struct cgraph_edge *edge, last;
 522
 523   struct cgraph_node **stack =
 524     xcalloc (cgraph_n_nodes, sizeof (struct cgraph_node *));
 525
 526   /* We have to deal with cycles nicely, so use a depth first traversal
 527      output algorithm.  Ignore the fact that some functions won't need
 528      to be output and put them into order as well, so we get dependencies
 529      right through intline functions.  */
 530   for (node = cgraph_nodes; node; node = node->next)
 531     node->aux = NULL;
 532   for (node = cgraph_nodes; node; node = node->next)
 533     if (!node->aux)
 534       {
 535         node2 = node;
 536         if (!node->callers)
 537           node->aux = &last;
 538         else
 539           node->aux = node->callers;
 540         while (node2)
 541           {
 542             while (node2->aux != &last)
 543               {
 544                 edge = node2->aux;
 545                 if (edge->next_caller)
 546                   node2->aux = edge->next_caller;
 547                 else
 548                   node2->aux = &last;
 549                 if (!edge->caller->aux)
 550                   {
 551                     if (!edge->caller->callers)
 552                       edge->caller->aux = &last;
 553                     else
 554                       edge->caller->aux = edge->caller->callers;
 555                     stack[stack_size++] = node2;
 556                     node2 = edge->caller;
 557                     break;
 558                   }
 559               }
 560             if (node2->aux == &last)
 561               {
 562                 order[order_pos++] = node2;
 563                 if (stack_size)
 564                   node2 = stack[--stack_size];
 565                 else
 566                   node2 = NULL;
 567               }
 568           }
 569       }
 570   free (stack);
 571   return order_pos;
 572 }
 573
 574 #define INLINED_TIMES(node) ((size_t)(node)->aux)
 575 #define SET_INLINED_TIMES(node,times) ((node)->aux = (void *)(times))
 576
 577 /* Return list of nodes we decided to inline NODE into, set their output
 578    flag and compute INLINED_TIMES.
 579
 580    We do simple backtracing to get INLINED_TIMES right.  This should not be
 581    expensive as we limit the amount of inlining.  Alternatively we may first
 582    discover set of nodes, topologically sort these and propagate
 583    INLINED_TIMES  */
 584
 585 static int
 586 cgraph_inlined_into (struct cgraph_node *node, struct cgraph_node **array)
 587 {
 588   int nfound = 0;
 589   struct cgraph_edge **stack;
 590   struct cgraph_edge *e, *e1;
 591   int sp;
 592   int i;
 593
 594   /* Fast path: since we traverse in mostly topological order, we will likely
 595      find no edges.  */
 596   for (e = node->callers; e; e = e->next_caller)
 597     if (e->inline_call)
 598       break;
 599
 600   if (!e)
 601     return 0;
 602
 603   /* Allocate stack for back-tracking up callgraph.  */
 604   stack = xmalloc ((cgraph_n_nodes + 1) * sizeof (struct cgraph_edge));
 605   sp = 0;
 606
 607   /* Push the first edge on to the stack.  */
 608   stack[sp++] = e;
 609
 610   while (sp)
 611     {
 612       struct cgraph_node *caller;
 613
 614       /* Look at the edge on the top of the stack.  */
 615       e = stack[sp - 1];
 616       caller = e->caller;
 617
 618       /* Check if the caller destination has been visited yet.  */
 619       if (!caller->output)
 620         {
 621           array[nfound++] = e->caller;
 622           /* Mark that we have visited the destination.  */
 623           caller->output = true;
 624           SET_INLINED_TIMES (caller, 0);
 625         }
 626       SET_INLINED_TIMES (caller, INLINED_TIMES (caller) + 1);
 627
 628       for (e1 = caller->callers; e1; e1 = e1->next_caller)
 629         if (e1->inline_call)
 630           break;
 631       if (e1)
 632         stack[sp++] = e1;
 633       else
 634         {
 635           while (true)
 636             {
 637               for (e1 = e->next_caller; e1; e1 = e1->next_caller)
 638                 if (e1->inline_call)
 639                   break;
 640
 641               if (e1)
 642                 {
 643                   stack[sp - 1] = e1;
 644                   break;
 645                 }
 646               else
 647                 {
 648                   sp--;
 649                   if (!sp)
 650                     break;
 651                   e = stack[sp - 1];
 652                 }
 653             }
 654         }
 655     }
 656
 657   free (stack);
 658
 659
 660   if (cgraph_dump_file)
 661     {
 662       fprintf (cgraph_dump_file, " Found inline predecesors of %s:",
 663                cgraph_node_name (node));
 664       for (i = 0; i < nfound; i++)
 665         {
 666           fprintf (cgraph_dump_file, " %s", cgraph_node_name (array[i]));
 667           if (INLINED_TIMES (array[i]) != 1)
 668             fprintf (cgraph_dump_file, " (%i times)",
 669                      (int)INLINED_TIMES (array[i]));
 670         }
 671       fprintf (cgraph_dump_file, "\n");
 672     }
 673
 674   return nfound;
 675 }
 676
 677 /* Return list of nodes we decided to inline into NODE, set their output
 678    flag and compute INLINED_TIMES.
 679
 680    This function is identical to cgraph_inlined_into with callers and callees
 681    nodes swapped.  */
 682
 683 static int
 684 cgraph_inlined_callees (struct cgraph_node *node, struct cgraph_node **array)
 685 {
 686   int nfound = 0;
 687   struct cgraph_edge **stack;
 688   struct cgraph_edge *e, *e1;
 689   int sp;
 690   int i;
 691
 692   /* Fast path: since we traverse in mostly topological order, we will likely
 693      find no edges.  */
 694   for (e = node->callees; e; e = e->next_callee)
 695     if (e->inline_call)
 696       break;
 697
 698   if (!e)
 699     return 0;
 700
 701   /* Allocate stack for back-tracking up callgraph.  */
 702   stack = xmalloc ((cgraph_n_nodes + 1) * sizeof (struct cgraph_edge));
 703   sp = 0;
 704
 705   /* Push the first edge on to the stack.  */
 706   stack[sp++] = e;
 707
 708   while (sp)
 709     {
 710       struct cgraph_node *callee;
 711
 712       /* Look at the edge on the top of the stack.  */
 713       e = stack[sp - 1];
 714       callee = e->callee;
 715
 716       /* Check if the callee destination has been visited yet.  */
 717       if (!callee->output)
 718         {
 719           array[nfound++] = e->callee;
 720           /* Mark that we have visited the destination.  */
 721           callee->output = true;
 722           SET_INLINED_TIMES (callee, 0);
 723         }
 724       SET_INLINED_TIMES (callee, INLINED_TIMES (callee) + 1);
 725
 726       for (e1 = callee->callees; e1; e1 = e1->next_callee)
 727         if (e1->inline_call)
 728           break;
 729       if (e1)
 730         stack[sp++] = e1;
 731       else
 732         {
 733           while (true)
 734             {
 735               for (e1 = e->next_callee; e1; e1 = e1->next_callee)
 736                 if (e1->inline_call)
 737                   break;
 738
 739               if (e1)
 740                 {
 741                   stack[sp - 1] = e1;
 742                   break;
 743                 }
 744               else
 745                 {
 746                   sp--;
 747                   if (!sp)
 748                     break;
 749                   e = stack[sp - 1];
 750                 }
 751             }
 752         }
 753     }
 754
 755   free (stack);
 756
 757   if (cgraph_dump_file)
 758     {
 759       fprintf (cgraph_dump_file, " Found inline successors of %s:",
 760                cgraph_node_name (node));
 761       for (i = 0; i < nfound; i++)
 762         {
 763           fprintf (cgraph_dump_file, " %s", cgraph_node_name (array[i]));
 764           if (INLINED_TIMES (array[i]) != 1)
 765             fprintf (cgraph_dump_file, " (%i times)",
 766                      (int)INLINED_TIMES (array[i]));
 767         }
 768       fprintf (cgraph_dump_file, "\n");
 769     }
 770
 771   return nfound;
 772 }
 773
 774 /* Estimate size of the function after inlining WHAT into TO.  */
 775
 776 static int
 777 cgraph_estimate_size_after_inlining (int times, struct cgraph_node *to,
 778                                      struct cgraph_node *what)
 779 {
 780   return (what->global.insns - INSNS_PER_CALL) * times + to->global.insns;
 781 }
 782
 783 /* Estimate the growth caused by inlining NODE into all callees.  */
 784
 785 static int
 786 cgraph_estimate_growth (struct cgraph_node *node)
 787 {
 788   int growth = 0;
 789   int calls_saved = 0;
 790   int clones_added = 0;
 791   struct cgraph_edge *e;
 792
 793   for (e = node->callers; e; e = e->next_caller)
 794     if (!e->inline_call)
 795       {
 796         growth += ((cgraph_estimate_size_after_inlining (1, e->caller, node)
 797                     -
 798                     e->caller->global.insns) *e->caller->global.cloned_times);
 799         calls_saved += e->caller->global.cloned_times;
 800         clones_added += e->caller->global.cloned_times;
 801       }
 802
 803   /* ??? Wrong for self recursive functions or cases where we decide to not
 804      inline for different reasons, but it is not big deal as in that case
 805      we will keep the body around, but we will also avoid some inlining.  */
 806   if (!node->needed && !node->origin && !DECL_EXTERNAL (node->decl))
 807     growth -= node->global.insns, clones_added--;
 808
 809   if (!calls_saved)
 810     calls_saved = 1;
 811
 812   return growth;
 813 }
 814
 815 /* Update insn sizes after inlining WHAT into TO that is already inlined into
 816    all nodes in INLINED array.  */
 817
 818 static void
 819 cgraph_mark_inline (struct cgraph_node *to, struct cgraph_node *what,
 820                     struct cgraph_node **inlined, int ninlined,
 821                     struct cgraph_node **inlined_callees,
 822                     int ninlined_callees)
 823 {
 824   int i;
 825   int times = 0;
 826   int clones = 0;
 827   struct cgraph_edge *e;
 828   bool called = false;
 829   int new_insns;
 830
 831   what->global.inlined = 1;
 832   for (e = what->callers; e; e = e->next_caller)
 833     {
 834       if (e->caller == to)
 835         {
 836           if (e->inline_call)
 837             abort ();
 838           e->inline_call = true;
 839           times++;
 840           clones += e->caller->global.cloned_times;
 841         }
 842       else if (!e->inline_call)
 843         called = true;
 844     }
 845   if (!times)
 846     abort ();
 847   ncalls_inlined += times;
 848
 849   new_insns = cgraph_estimate_size_after_inlining (times, to, what);
 850   if (to->global.will_be_output)
 851     overall_insns += new_insns - to->global.insns;
 852   to->global.insns = new_insns;
 853
 854   if (!called && !what->needed && !what->origin
 855       && flag_unit_at_a_time
 856       && !DECL_EXTERNAL (what->decl))
 857     {
 858       if (!what->global.will_be_output)
 859         abort ();
 860       clones--;
 861       nfunctions_inlined++;
 862       what->global.will_be_output = 0;
 863       overall_insns -= what->global.insns;
 864     }
 865   what->global.cloned_times += clones;
 866   for (i = 0; i < ninlined; i++)
 867     {
 868       new_insns =
 869         cgraph_estimate_size_after_inlining (INLINED_TIMES (inlined[i]) *
 870                                              times, inlined[i], what);
 871       if (inlined[i]->global.will_be_output)
 872         overall_insns += new_insns - inlined[i]->global.insns;
 873       inlined[i]->global.insns = new_insns;
 874     }
 875   for (i = 0; i < ninlined_callees; i++)
 876     {
 877       inlined_callees[i]->global.cloned_times +=
 878         INLINED_TIMES (inlined_callees[i]) * clones;
 879     }
 880 }
 881
 882 /* Return false when inlining WHAT into TO is not good idea as it would cause
 883    too large growth of function bodies.  */
 884
 885 static bool
 886 cgraph_check_inline_limits (struct cgraph_node *to, struct cgraph_node *what,
 887                             struct cgraph_node **inlined, int ninlined)
 888 {
 889   int i;
 890   int times = 0;
 891   struct cgraph_edge *e;
 892   int newsize;
 893   int limit;
 894
 895   for (e = to->callees; e; e = e->next_callee)
 896     if (e->callee == what)
 897       times++;
 898
 899   /* When inlining large function body called once into small function,
 900      take the inlined function as base for limiting the growth.  */
 901   if (to->local.self_insns > what->local.self_insns)
 902     limit = to->local.self_insns;
 903   else
 904     limit = what->local.self_insns;
 905
 906   limit += limit * PARAM_VALUE (PARAM_LARGE_FUNCTION_GROWTH) / 100;
 907
 908   newsize = cgraph_estimate_size_after_inlining (times, to, what);
 909   if (newsize > PARAM_VALUE (PARAM_LARGE_FUNCTION_INSNS)
 910       && newsize > limit)
 911     return false;
 912   for (i = 0; i < ninlined; i++)
 913     {
 914       newsize =
 915         cgraph_estimate_size_after_inlining (INLINED_TIMES (inlined[i]) *
 916                                              times, inlined[i], what);
 917       if (newsize > PARAM_VALUE (PARAM_LARGE_FUNCTION_INSNS)
 918           && newsize >
 919           inlined[i]->local.self_insns *
 920           (100 + PARAM_VALUE (PARAM_LARGE_FUNCTION_GROWTH)) / 100)
 921         return false;
 922     }
 923   return true;
 924 }
 925
 926 /* Return true when function N is small enough to be inlined.  */
 927
 928 static bool
 929 cgraph_default_inline_p (struct cgraph_node *n)
 930 {
 931   if (!DECL_INLINE (n->decl) || !DECL_SAVED_TREE (n->decl))
 932     return false;
 933   if (DECL_DECLARED_INLINE_P (n->decl))
 934     return n->global.insns < MAX_INLINE_INSNS_SINGLE;
 935   else
 936     return n->global.insns < MAX_INLINE_INSNS_AUTO;
 937 }
 938
 939 /* We use greedy algorithm for inlining of small functions:
 940    All inline candidates are put into prioritized heap based on estimated
 941    growth of the overall number of instructions and then update the estimates.
 942
 943    INLINED and INLINED_CALEES are just pointers to arrays large enough
 944    to be passed to cgraph_inlined_into and cgraph_inlined_callees.  */
 945
 946 static void
 947 cgraph_decide_inlining_of_small_functions (struct cgraph_node **inlined,
 948                                            struct cgraph_node **inlined_callees)
 949 {
 950   int i;
 951   struct cgraph_node *node;
 952   fibheap_t heap = fibheap_new ();
 953   struct fibnode **heap_node =
 954     xcalloc (cgraph_max_uid, sizeof (struct fibnode *));
 955   int ninlined, ninlined_callees;
 956   int max_insns = ((HOST_WIDEST_INT) initial_insns
 957                    * (100 + PARAM_VALUE (PARAM_INLINE_UNIT_GROWTH)) / 100);
 958
 959   /* Put all inline candidates into the heap.  */
 960
 961   for (node = cgraph_nodes; node; node = node->next)
 962     {
 963       struct cgraph_edge *e;
 964
 965       if (!node->local.inlinable || !node->callers
 966           || !cgraph_default_inline_p (node))
 967         continue;
 968
 969       /* Rule out always_inline functions we dealt with earlier.  */
 970       for (e = node->callers; e; e = e->next_caller)
 971         if (e->inline_call)
 972           break;
 973       if (e)
 974         continue;
 975       heap_node[node->uid] =
 976         fibheap_insert (heap, cgraph_estimate_growth (node), node);
 977     }
 978
 979   if (cgraph_dump_file)
 980     fprintf (cgraph_dump_file, "\nDeciding on smaller functions:\n");
 981   while ((node = fibheap_extract_min (heap)) && overall_insns <= max_insns)
 982     {
 983       struct cgraph_edge *e;
 984       int old_insns = overall_insns;
 985
 986       heap_node[node->uid] = NULL;
 987       if (cgraph_dump_file)
 988         fprintf (cgraph_dump_file,
 989                  "\nConsidering %s with %i insns\n"
 990                  " Estimated growth is %+i insns.\n",
 991                  cgraph_node_name (node), node->global.insns,
 992                  cgraph_estimate_growth (node));
 993       if (!cgraph_default_inline_p (node))
 994         {
 995           if (cgraph_dump_file)
 996             fprintf (cgraph_dump_file, " Function too large.\n");
 997           continue;
 998         }
 999       ninlined_callees = cgraph_inlined_callees (node, inlined_callees);
1000       for (e = node->callers; e; e = e->next_caller)
1001         if (!e->inline_call && e->caller != node)
1002           {
1003             ninlined = cgraph_inlined_into (e->caller, inlined);
1004             if (e->callee->output
1005                 || !cgraph_check_inline_limits (e->caller, node, inlined,
1006                                                 ninlined))
1007               {
1008                 for (i = 0; i < ninlined; i++)
1009                   inlined[i]->output = 0, node->aux = 0;
1010                 if (cgraph_dump_file)
1011                   fprintf (cgraph_dump_file, " Not inlining into %s.\n",
1012                            cgraph_node_name (e->caller));
1013                 continue;
1014               }
1015             cgraph_mark_inline (e->caller, node, inlined, ninlined,
1016                                 inlined_callees, ninlined_callees);
1017             if (heap_node[e->caller->uid])
1018               fibheap_replace_key (heap, heap_node[e->caller->uid],
1019                                    cgraph_estimate_growth (e->caller));
1020
1021             /* Size of the functions we updated into has changed, so update
1022                the keys.  */
1023             for (i = 0; i < ninlined; i++)
1024               {
1025                 inlined[i]->output = 0, node->aux = 0;
1026                 if (heap_node[inlined[i]->uid])
1027                   fibheap_replace_key (heap, heap_node[inlined[i]->uid],
1028                                        cgraph_estimate_growth (inlined[i]));
1029               }
1030         if (cgraph_dump_file)
1031           fprintf (cgraph_dump_file,
1032                    " Inlined into %s which now has %i insns.\n",
1033                    cgraph_node_name (e->caller),
1034                    e->caller->global.insns);
1035
1036           }
1037
1038       /* Similarly all functions called by the function we just inlined
1039          are now called more times; update keys.  */
1040
1041       for (e = node->callees; e; e = e->next_callee)
1042         if (!e->inline_call && heap_node[e->callee->uid])
1043           fibheap_replace_key (heap, heap_node[e->callee->uid],
1044                                cgraph_estimate_growth (e->callee));
1045
1046       for (i = 0; i < ninlined_callees; i++)
1047         {
1048           struct cgraph_edge *e;
1049
1050           for (e = inlined_callees[i]->callees; e; e = e->next_callee)
1051             if (!e->inline_call && heap_node[e->callee->uid])
1052               fibheap_replace_key (heap, heap_node[e->callee->uid],
1053                                    cgraph_estimate_growth (e->callee));
1054
1055           inlined_callees[i]->output = 0, node->aux = 0;
1056         }
1057       if (cgraph_dump_file)
1058         fprintf (cgraph_dump_file,
1059                  " Inlined %i times for a net change of %+i insns.\n",
1060                  node->global.cloned_times, overall_insns - old_insns);
1061     }
1062   if (cgraph_dump_file && !fibheap_empty (heap))
1063     fprintf (cgraph_dump_file, "\nReached the inline-unit-growth limit.\n");
1064   fibheap_delete (heap);
1065   free (heap_node);
1066 }
1067
1068 /* Decide on the inlining.  We do so in the topological order to avoid
1069    expenses on updating datastructures.  */
1070
1071 static void
1072 cgraph_decide_inlining (void)
1073 {
1074   struct cgraph_node *node;
1075   int nnodes;
1076   struct cgraph_node **order =
1077     xcalloc (cgraph_n_nodes, sizeof (struct cgraph_node *));
1078   struct cgraph_node **inlined =
1079     xcalloc (cgraph_n_nodes, sizeof (struct cgraph_node *));
1080   struct cgraph_node **inlined_callees =
1081     xcalloc (cgraph_n_nodes, sizeof (struct cgraph_node *));
1082   int ninlined;
1083   int ninlined_callees;
1084   int old_insns = 0;
1085   int i, y;
1086
1087   for (node = cgraph_nodes; node; node = node->next)
1088     initial_insns += node->local.self_insns;
1089   overall_insns = initial_insns;
1090
1091   nnodes = cgraph_postorder (order);
1092
1093   if (cgraph_dump_file)
1094     fprintf (cgraph_dump_file,
1095              "\nDeciding on inlining.  Starting with %i insns.\n",
1096              initial_insns);
1097
1098   for (node = cgraph_nodes; node; node = node->next)
1099     node->aux = 0;
1100
1101   if (cgraph_dump_file)
1102     fprintf (cgraph_dump_file, "\nInlining always_inline functions:\n");
1103
1104   /* In the first pass mark all always_inline edges.  Do this with a priority
1105      so none of our later choices will make this impossible.  */
1106   for (i = nnodes - 1; i >= 0; i--)
1107     {
1108       struct cgraph_edge *e;
1109
1110       node = order[i];
1111
1112       for (e = node->callees; e; e = e->next_callee)
1113         if (e->callee->local.disregard_inline_limits)
1114           break;
1115       if (!e)
1116         continue;
1117       if (cgraph_dump_file)
1118         fprintf (cgraph_dump_file,
1119                  "\nConsidering %s %i insns (always inline)\n",
1120                  cgraph_node_name (e->callee), e->callee->global.insns);
1121       ninlined = cgraph_inlined_into (order[i], inlined);
1122       for (; e; e = e->next_callee)
1123         {
1124           old_insns = overall_insns;
1125           if (e->inline_call || !e->callee->local.disregard_inline_limits)
1126             continue;
1127           if (e->callee->output || e->callee == node)
1128             continue;
1129           ninlined_callees =
1130             cgraph_inlined_callees (e->callee, inlined_callees);
1131           cgraph_mark_inline (node, e->callee, inlined, ninlined,
1132                               inlined_callees, ninlined_callees);
1133           for (y = 0; y < ninlined_callees; y++)
1134             inlined_callees[y]->output = 0, node->aux = 0;
1135           if (cgraph_dump_file)
1136             fprintf (cgraph_dump_file,
1137                      " Inlined into %s which now has %i insns.\n",
1138                      cgraph_node_name (node->callees->caller),
1139                      node->callees->caller->global.insns);
1140         }
1141         if (cgraph_dump_file && node->global.cloned_times > 0)
1142           fprintf (cgraph_dump_file,
1143                    " Inlined %i times for a net change of %+i insns.\n",
1144                    node->global.cloned_times, overall_insns - old_insns);
1145       for (y = 0; y < ninlined; y++)
1146         inlined[y]->output = 0, node->aux = 0;
1147     }
1148
1149   if (!flag_really_no_inline)
1150     {
1151       cgraph_decide_inlining_of_small_functions (inlined, inlined_callees);
1152
1153       if (cgraph_dump_file)
1154         fprintf (cgraph_dump_file, "\nDeciding on functions called once:\n");
1155
1156       /* And finally decide what functions are called once.  */
1157
1158       for (i = nnodes - 1; i >= 0; i--)
1159         {
1160           node = order[i];
1161
1162           if (node->callers && !node->callers->next_caller && !node->needed
1163               && node->local.inlinable && !node->callers->inline_call
1164               && !DECL_EXTERNAL (node->decl) && !DECL_COMDAT (node->decl))
1165             {
1166               bool ok = true;
1167               struct cgraph_node *node1;
1168
1169               /* Verify that we won't duplicate the caller.  */
1170               for (node1 = node->callers->caller;
1171                    node1->callers && node1->callers->inline_call
1172                    && ok; node1 = node1->callers->caller)
1173                 if (node1->callers->next_caller || node1->needed)
1174                   ok = false;
1175               if (ok)
1176                 {
1177                   if (cgraph_dump_file)
1178                     fprintf (cgraph_dump_file,
1179                              "\nConsidering %s %i insns.\n"
1180                              " Called once from %s %i insns.\n",
1181                              cgraph_node_name (node), node->global.insns,
1182                              cgraph_node_name (node->callers->caller),
1183                              node->callers->caller->global.insns);
1184                   ninlined = cgraph_inlined_into (node->callers->caller,
1185                                                   inlined);
1186                   old_insns = overall_insns;
1187                   if (cgraph_check_inline_limits
1188                       (node->callers->caller, node, inlined, ninlined))
1189                     {
1190                       ninlined_callees =
1191                         cgraph_inlined_callees (node, inlined_callees);
1192                       cgraph_mark_inline (node->callers->caller, node, inlined,
1193                                           ninlined, inlined_callees,
1194                                           ninlined_callees);
1195                       for (y = 0; y < ninlined_callees; y++)
1196                         inlined_callees[y]->output = 0, node->aux = 0;
1197                       if (cgraph_dump_file)
1198                         fprintf (cgraph_dump_file,
1199                                  " Inlined into %s which now has %i insns"
1200                                  " for a net change of %+i insns.\n",
1201                                  cgraph_node_name (node->callers->caller),
1202                                  node->callers->caller->global.insns,
1203                                  overall_insns - old_insns);
1204                     }
1205                   else
1206                     {
1207                       if (cgraph_dump_file)
1208                         fprintf (cgraph_dump_file,
1209                                  " Inline limit reached, not inlined.\n");
1210                     }
1211                   for (y = 0; y < ninlined; y++)
1212                     inlined[y]->output = 0, node->aux = 0;
1213                 }
1214             }
1215         }
1216
1217       if (cgraph_dump_file)
1218         fprintf (cgraph_dump_file,
1219                  "\nInlined %i calls, eliminated %i functions, "
1220                  "%i insns turned to %i insns.\n\n",
1221                  ncalls_inlined, nfunctions_inlined, initial_insns,
1222                  overall_insns);
1223       free (order);
1224       free (inlined);
1225       free (inlined_callees);
1226     }
1227 }
1228
1229 /* Decide on the inlining.  We do so in the topological order to avoid
1230    expenses on updating datastructures.  */
1231
1232 static void
1233 cgraph_decide_inlining_incrementally (struct cgraph_node *node)
1234 {
1235   struct cgraph_edge *e;
1236   struct cgraph_node **inlined =
1237     xmalloc (sizeof (struct cgraph_node *) * cgraph_n_nodes);
1238   struct cgraph_node **inlined_callees =
1239     xmalloc (sizeof (struct cgraph_node *) * cgraph_n_nodes);
1240   int ninlined;
1241   int ninlined_callees;
1242   int y;
1243
1244   ninlined = cgraph_inlined_into (node, inlined);
1245
1246   /* First of all look for always inline functions.  */
1247   for (e = node->callees; e; e = e->next_callee)
1248     if (e->callee->local.disregard_inline_limits && !e->callee->output
1249         && e->callee != node && !e->inline_call)
1250       {
1251         ninlined_callees = cgraph_inlined_callees (e->callee, inlined_callees);
1252         cgraph_mark_inline (node, e->callee, inlined, ninlined,
1253                             inlined_callees, ninlined_callees);
1254         for (y = 0; y < ninlined_callees; y++)
1255           inlined_callees[y]->output = 0, node->aux = 0;
1256       }
1257
1258   if (!flag_really_no_inline)
1259     {
1260       /* Now do the automatic inlining.  */
1261       for (e = node->callees; e; e = e->next_callee)
1262         if (e->callee->local.inlinable && !e->callee->output
1263             && e->callee != node && !e->inline_call
1264             && cgraph_default_inline_p (e->callee)
1265             && cgraph_check_inline_limits (node, e->callee, inlined,
1266                                            ninlined))
1267           {
1268             ninlined_callees = cgraph_inlined_callees (e->callee,
1269                                                        inlined_callees);
1270             cgraph_mark_inline (node, e->callee, inlined, ninlined,
1271                                 inlined_callees, ninlined_callees);
1272             for (y = 0; y < ninlined_callees; y++)
1273               inlined_callees[y]->output = 0, node->aux = 0;
1274           }
1275     }
1276
1277   /* Clear the flags set by cgraph_inlined_into.  */
1278   for (y = 0; y < ninlined; y++)
1279     inlined[y]->output = 0, node->aux = 0;
1280
1281   free (inlined);
1282   free (inlined_callees);
1283 }
1284
1285
1286 /* Return true when CALLER_DECL should be inlined into CALLEE_DECL.  */
1287
1288 bool
1289 cgraph_inline_p (tree caller_decl, tree callee_decl)
1290 {
1291   struct cgraph_node *caller = cgraph_node (caller_decl);
1292   struct cgraph_node *callee = cgraph_node (callee_decl);
1293   struct cgraph_edge *e;
1294
1295   for (e = caller->callees; e; e = e->next_callee)
1296     if (e->callee == callee)
1297       return e->inline_call;
1298   /* We do not record builtins in the callgraph.  Perhaps it would make more
1299      sense to do so and then prune out those not overwritten by explicit
1300      function body.  */
1301   return false;
1302 }
1303 /* Expand all functions that must be output.
1304
1305    Attempt to topologically sort the nodes so function is output when
1306    all called functions are already assembled to allow data to be
1307    propagated across the callgraph.  Use a stack to get smaller distance
1308    between a function and it's callees (later we may choose to use a more
1309    sophisticated algorithm for function reordering; we will likely want
1310    to use subsections to make the output functions appear in top-down
1311    order).  */
1312
1313 static void
1314 cgraph_expand_all_functions (void)
1315 {
1316   struct cgraph_node *node;
1317   struct cgraph_node **order =
1318     xcalloc (cgraph_n_nodes, sizeof (struct cgraph_node *));
1319   int order_pos = 0;
1320   int i;
1321
1322   cgraph_mark_functions_to_output ();
1323
1324   order_pos = cgraph_postorder (order);
1325
1326   for (i = order_pos - 1; i >= 0; i--)
1327     {
1328       node = order[i];
1329       if (node->output)
1330         {
1331           if (!node->reachable)
1332             abort ();
1333           node->output = 0;
1334           cgraph_expand_function (node);
1335         }
1336     }
1337   free (order);
1338 }
1339
1340 /* Mark all local functions.
1341
1342    A local function is one whose calls can occur only in the
1343    current compilation unit, so we change its calling convention.
1344    We simply mark all static functions whose address is not taken
1345    as local.  */
1346
1347 static void
1348 cgraph_mark_local_functions (void)
1349 {
1350   struct cgraph_node *node;
1351
1352   if (cgraph_dump_file)
1353     fprintf (cgraph_dump_file, "\nMarking local functions:");
1354
1355   /* Figure out functions we want to assemble.  */
1356   for (node = cgraph_nodes; node; node = node->next)
1357     {
1358       node->local.local = (!node->needed
1359                            && DECL_SAVED_TREE (node->decl)
1360                            && !TREE_PUBLIC (node->decl));
1361       if (cgraph_dump_file && node->local.local)
1362         fprintf (cgraph_dump_file, " %s", cgraph_node_name (node));
1363     }
1364   if (cgraph_dump_file)
1365     fprintf (cgraph_dump_file, "\n\n");
1366 }
1367
1368 /* Perform simple optimizations based on callgraph.  */
1369
1370 void
1371 cgraph_optimize (void)
1372 {
1373   if (!flag_unit_at_a_time)
1374     return;
1375   timevar_push (TV_CGRAPHOPT);
1376   if (!quiet_flag)
1377     fprintf (stderr, "Performing intraprocedural optimizations\n");
1378
1379   cgraph_mark_local_functions ();
1380   if (cgraph_dump_file)
1381     {
1382       fprintf (cgraph_dump_file, "Marked ");
1383       dump_cgraph (cgraph_dump_file);
1384     }
1385
1386   cgraph_decide_inlining ();
1387   cgraph_global_info_ready = true;
1388   if (cgraph_dump_file)
1389     {
1390       fprintf (cgraph_dump_file, "Optimized ");
1391       dump_cgraph (cgraph_dump_file);
1392     }
1393   timevar_pop (TV_CGRAPHOPT);
1394
1395   /* Output everything.  */
1396   if (!quiet_flag)
1397     fprintf (stderr, "Assembling functions:\n");
1398   cgraph_expand_all_functions ();
1399   if (cgraph_dump_file)
1400     {
1401       fprintf (cgraph_dump_file, "\nFinal ");
1402       dump_cgraph (cgraph_dump_file);
1403     }
1404 }