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