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
 233 /* Walk tree and record all calls.  Called via walk_tree.  */
 234 static tree
 235 record_call_1 (tree *tp, int *walk_subtrees, void *data)
 236 {
 237   tree t = *tp;
 238
 239   switch (TREE_CODE (t))
 240     {
 241     case VAR_DECL:
 242       /* ??? Really, we should mark this decl as *potentially* referenced
 243          by this function and re-examine whether the decl is actually used
 244          after rtl has been generated.  */
 245       if (TREE_STATIC (t))
 246         cgraph_varpool_mark_needed_node (cgraph_varpool_node (t));
 247       break;
 248
 249     case ADDR_EXPR:
 250       if (flag_unit_at_a_time)
 251         {
 252           /* Record dereferences to the functions.  This makes the
 253              functions reachable unconditionally.  */
 254           tree decl = TREE_OPERAND (*tp, 0);
 255           if (TREE_CODE (decl) == FUNCTION_DECL)
 256             cgraph_mark_needed_node (cgraph_node (decl));
 257         }
 258       break;
 259
 260     case CALL_EXPR:
 261       {
 262         tree decl = get_callee_fndecl (*tp);
 263         if (decl && TREE_CODE (decl) == FUNCTION_DECL)
 264           {
 265             cgraph_record_call (data, decl);
 266
 267             /* When we see a function call, we don't want to look at the
 268                function reference in the ADDR_EXPR that is hanging from
 269                the CALL_EXPR we're examining here, because we would
 270                conclude incorrectly that the function's address could be
 271                taken by something that is not a function call.  So only
 272                walk the function parameter list, skip the other subtrees.  */
 273
 274             walk_tree (&TREE_OPERAND (*tp, 1), record_call_1, data,
 275                        visited_nodes);
 276             *walk_subtrees = 0;
 277           }
 278         break;
 279       }
 280
 281     default:
 282       /* Save some cycles by not walking types and declaration as we
 283          won't find anything useful there anyway.  */
 284       if (DECL_P (*tp) || TYPE_P (*tp))
 285         {
 286           *walk_subtrees = 0;
 287           break;
 288         }
 289
 290       if ((unsigned int) TREE_CODE (t) >= LAST_AND_UNUSED_TREE_CODE)
 291         return (*lang_hooks.callgraph.analyze_expr) (tp, walk_subtrees, data);
 292       break;
 293     }
 294
 295   return NULL;
 296 }
 297
 298 /* Create cgraph edges for function calls inside BODY from DECL.  */
 299
 300 void
 301 cgraph_create_edges (tree decl, tree body)
 302 {
 303   /* The nodes we're interested in are never shared, so walk
 304      the tree ignoring duplicates.  */
 305   visited_nodes = htab_create (37, htab_hash_pointer,
 306                                     htab_eq_pointer, NULL);
 307   walk_tree (&body, record_call_1, decl, visited_nodes);
 308   htab_delete (visited_nodes);
 309   visited_nodes = NULL;
 310 }
 311
 312 /* Analyze the function scheduled to be output.  */
 313 static void
 314 cgraph_analyze_function (struct cgraph_node *node)
 315 {
 316   tree decl = node->decl;
 317   struct cgraph_edge *e;
 318
 319   current_function_decl = decl;
 320
 321   /* First kill forward declaration so reverse inlining works properly.  */
 322   cgraph_create_edges (decl, DECL_SAVED_TREE (decl));
 323
 324   node->local.inlinable = tree_inlinable_function_p (decl);
 325   if (!DECL_ESTIMATED_INSNS (decl))
 326     DECL_ESTIMATED_INSNS (decl)
 327       = (*lang_hooks.tree_inlining.estimate_num_insns) (decl);
 328   node->local.self_insns = DECL_ESTIMATED_INSNS (decl);
 329   if (node->local.inlinable)
 330     node->local.disregard_inline_limits
 331       = (*lang_hooks.tree_inlining.disregard_inline_limits) (decl);
 332   for (e = node->callers; e; e = e->next_caller)
 333     if (e->inline_failed)
 334       {
 335         if (node->local.redefined_extern_inline)
 336           e->inline_failed = N_("redefined extern inline functions are not "
 337                                 "considered for inlining");
 338         else if (!node->local.inlinable)
 339           e->inline_failed = N_("function not inlinable");
 340         else
 341           e->inline_failed = N_("function not considered for inlining");
 342       }
 343   if (flag_really_no_inline && !node->local.disregard_inline_limits)
 344     node->local.inlinable = 0;
 345   /* Inlining characteristics are maintained by the cgraph_mark_inline.  */
 346   node->global.insns = node->local.self_insns;
 347   if (!DECL_EXTERNAL (decl))
 348     {
 349       node->global.cloned_times = 1;
 350       node->global.will_be_output = true;
 351     }
 352
 353   node->analyzed = true;
 354   current_function_decl = NULL;
 355 }
 356
 357 /* Analyze the whole compilation unit once it is parsed completely.  */
 358
 359 void
 360 cgraph_finalize_compilation_unit (void)
 361 {
 362   struct cgraph_node *node;
 363
 364   if (!flag_unit_at_a_time)
 365     {
 366       cgraph_assemble_pending_functions ();
 367       return;
 368     }
 369
 370   cgraph_varpool_assemble_pending_decls ();
 371   if (!quiet_flag)
 372     fprintf (stderr, "\nAnalyzing compilation unit\n");
 373
 374   timevar_push (TV_CGRAPH);
 375   if (cgraph_dump_file)
 376     {
 377       fprintf (cgraph_dump_file, "Initial entry points:");
 378       for (node = cgraph_nodes; node; node = node->next)
 379         if (node->needed && DECL_SAVED_TREE (node->decl))
 380           fprintf (cgraph_dump_file, " %s", cgraph_node_name (node));
 381       fprintf (cgraph_dump_file, "\n");
 382     }
 383
 384   /* Propagate reachability flag and lower representation of all reachable
 385      functions.  In the future, lowering will introduce new functions and
 386      new entry points on the way (by template instantiation and virtual
 387      method table generation for instance).  */
 388   while (cgraph_nodes_queue)
 389     {
 390       struct cgraph_edge *edge;
 391       tree decl = cgraph_nodes_queue->decl;
 392
 393       node = cgraph_nodes_queue;
 394       cgraph_nodes_queue = cgraph_nodes_queue->next_needed;
 395
 396       /* ??? It is possible to create extern inline function and later using
 397          weak alas attribute to kill it's body. See
 398          gcc.c-torture/compile/20011119-1.c  */
 399       if (!DECL_SAVED_TREE (decl))
 400         continue;
 401
 402       if (node->analyzed || !node->reachable || !DECL_SAVED_TREE (decl))
 403         abort ();
 404
 405       cgraph_analyze_function (node);
 406
 407       for (edge = node->callees; edge; edge = edge->next_callee)
 408         if (!edge->callee->reachable)
 409           cgraph_mark_reachable_node (edge->callee);
 410
 411       cgraph_varpool_assemble_pending_decls ();
 412     }
 413
 414   /* Collect entry points to the unit.  */
 415
 416   if (cgraph_dump_file)
 417     {
 418       fprintf (cgraph_dump_file, "Unit entry points:");
 419       for (node = cgraph_nodes; node; node = node->next)
 420         if (node->needed && DECL_SAVED_TREE (node->decl))
 421           fprintf (cgraph_dump_file, " %s", cgraph_node_name (node));
 422       fprintf (cgraph_dump_file, "\n\nInitial ");
 423       dump_cgraph (cgraph_dump_file);
 424     }
 425
 426   if (cgraph_dump_file)
 427     fprintf (cgraph_dump_file, "\nReclaiming functions:");
 428
 429   for (node = cgraph_nodes; node; node = node->next)
 430     {
 431       tree decl = node->decl;
 432
 433       if (!node->reachable && DECL_SAVED_TREE (decl))
 434         {
 435           cgraph_remove_node (node);
 436           if (cgraph_dump_file)
 437             fprintf (cgraph_dump_file, " %s", cgraph_node_name (node));
 438         }
 439     }
 440   if (cgraph_dump_file)
 441     {
 442       fprintf (cgraph_dump_file, "\n\nReclaimed ");
 443       dump_cgraph (cgraph_dump_file);
 444     }
 445   ggc_collect ();
 446   timevar_pop (TV_CGRAPH);
 447 }
 448
 449 /* Figure out what functions we want to assemble.  */
 450
 451 static void
 452 cgraph_mark_functions_to_output (void)
 453 {
 454   struct cgraph_node *node;
 455
 456   for (node = cgraph_nodes; node; node = node->next)
 457     {
 458       tree decl = node->decl;
 459       struct cgraph_edge *e;
 460
 461       if (node->output)
 462         abort ();
 463
 464       for (e = node->callers; e; e = e->next_caller)
 465         if (e->inline_failed)
 466           break;
 467
 468       /* We need to output all local functions that are used and not
 469          always inlined, as well as those that are reachable from
 470          outside the current compilation unit.  */
 471       if (DECL_SAVED_TREE (decl)
 472           && (node->needed
 473               || (e && node->reachable))
 474           && !TREE_ASM_WRITTEN (decl) && !node->origin
 475           && !DECL_EXTERNAL (decl))
 476         node->output = 1;
 477     }
 478 }
 479
 480 /* Optimize the function before expansion.  */
 481
 482 static void
 483 cgraph_optimize_function (struct cgraph_node *node)
 484 {
 485   tree decl = node->decl;
 486
 487   timevar_push (TV_INTEGRATION);
 488   /* optimize_inline_calls avoids inlining of current_function_decl.  */
 489   current_function_decl = decl;
 490   if (flag_inline_trees)
 491     {
 492       struct cgraph_edge *e;
 493
 494       for (e = node->callees; e; e = e->next_callee)
 495         if (!e->inline_failed || warn_inline
 496             || (DECL_DECLARED_INLINE_P (e->callee->decl)
 497                 && lookup_attribute ("always_inline",
 498                                      DECL_ATTRIBUTES (e->callee->decl))))
 499           break;
 500       if (e)
 501         optimize_inline_calls (decl);
 502     }
 503   if (node->nested)
 504     {
 505       for (node = node->nested; node; node = node->next_nested)
 506         cgraph_optimize_function (node);
 507     }
 508   timevar_pop (TV_INTEGRATION);
 509 }
 510
 511 /* Expand function specified by NODE.  */
 512
 513 static void
 514 cgraph_expand_function (struct cgraph_node *node)
 515 {
 516   tree decl = node->decl;
 517
 518   if (flag_unit_at_a_time)
 519     announce_function (decl);
 520
 521   cgraph_optimize_function (node);
 522
 523   /* Generate RTL for the body of DECL.  Nested functions are expanded
 524      via lang_expand_decl_stmt.  */
 525   (*lang_hooks.callgraph.expand_function) (decl);
 526
 527   if (!cgraph_function_possibly_inlined_p (decl))
 528     DECL_SAVED_TREE (decl) = NULL;
 529   current_function_decl = NULL;
 530 }
 531
 532 /* Fill array order with all nodes with output flag set in the reverse
 533    topological order.  */
 534
 535 static int
 536 cgraph_postorder (struct cgraph_node **order)
 537 {
 538   struct cgraph_node *node, *node2;
 539   int stack_size = 0;
 540   int order_pos = 0;
 541   struct cgraph_edge *edge, last;
 542
 543   struct cgraph_node **stack =
 544     xcalloc (cgraph_n_nodes, sizeof (struct cgraph_node *));
 545
 546   /* We have to deal with cycles nicely, so use a depth first traversal
 547      output algorithm.  Ignore the fact that some functions won't need
 548      to be output and put them into order as well, so we get dependencies
 549      right through intline functions.  */
 550   for (node = cgraph_nodes; node; node = node->next)
 551     node->aux = NULL;
 552   for (node = cgraph_nodes; node; node = node->next)
 553     if (!node->aux)
 554       {
 555         node2 = node;
 556         if (!node->callers)
 557           node->aux = &last;
 558         else
 559           node->aux = node->callers;
 560         while (node2)
 561           {
 562             while (node2->aux != &last)
 563               {
 564                 edge = node2->aux;
 565                 if (edge->next_caller)
 566                   node2->aux = edge->next_caller;
 567                 else
 568                   node2->aux = &last;
 569                 if (!edge->caller->aux)
 570                   {
 571                     if (!edge->caller->callers)
 572                       edge->caller->aux = &last;
 573                     else
 574                       edge->caller->aux = edge->caller->callers;
 575                     stack[stack_size++] = node2;
 576                     node2 = edge->caller;
 577                     break;
 578                   }
 579               }
 580             if (node2->aux == &last)
 581               {
 582                 order[order_pos++] = node2;
 583                 if (stack_size)
 584                   node2 = stack[--stack_size];
 585                 else
 586                   node2 = NULL;
 587               }
 588           }
 589       }
 590   free (stack);
 591   return order_pos;
 592 }
 593
 594 #define INLINED_TIMES(node) ((size_t)(node)->aux)
 595 #define SET_INLINED_TIMES(node,times) ((node)->aux = (void *)(times))
 596
 597 /* Return list of nodes we decided to inline NODE into, set their output
 598    flag and compute INLINED_TIMES.
 599
 600    We do simple backtracing to get INLINED_TIMES right.  This should not be
 601    expensive as we limit the amount of inlining.  Alternatively we may first
 602    discover set of nodes, topologically sort these and propagate
 603    INLINED_TIMES  */
 604
 605 static int
 606 cgraph_inlined_into (struct cgraph_node *node, struct cgraph_node **array)
 607 {
 608   int nfound = 0;
 609   struct cgraph_edge **stack;
 610   struct cgraph_edge *e, *e1;
 611   int sp;
 612   int i;
 613
 614   /* Fast path: since we traverse in mostly topological order, we will likely
 615      find no edges.  */
 616   for (e = node->callers; e; e = e->next_caller)
 617     if (!e->inline_failed)
 618       break;
 619
 620   if (!e)
 621     return 0;
 622
 623   /* Allocate stack for back-tracking up callgraph.  */
 624   stack = xmalloc ((cgraph_n_nodes + 1) * sizeof (struct cgraph_edge));
 625   sp = 0;
 626
 627   /* Push the first edge on to the stack.  */
 628   stack[sp++] = e;
 629
 630   while (sp)
 631     {
 632       struct cgraph_node *caller;
 633
 634       /* Look at the edge on the top of the stack.  */
 635       e = stack[sp - 1];
 636       caller = e->caller;
 637
 638       /* Check if the caller destination has been visited yet.  */
 639       if (!caller->output)
 640         {
 641           array[nfound++] = e->caller;
 642           /* Mark that we have visited the destination.  */
 643           caller->output = true;
 644           SET_INLINED_TIMES (caller, 0);
 645         }
 646       SET_INLINED_TIMES (caller, INLINED_TIMES (caller) + 1);
 647
 648       for (e1 = caller->callers; e1; e1 = e1->next_caller)
 649         if (!e1->inline_failed)
 650           break;
 651
 652       if (e1)
 653         stack[sp++] = e1;
 654       else
 655         {
 656           while (true)
 657             {
 658               for (e1 = e->next_caller; e1; e1 = e1->next_caller)
 659                 if (!e1->inline_failed)
 660                   break;
 661
 662               if (e1)
 663                 {
 664                   stack[sp - 1] = e1;
 665                   break;
 666                 }
 667               else
 668                 {
 669                   sp--;
 670                   if (!sp)
 671                     break;
 672                   e = stack[sp - 1];
 673                 }
 674             }
 675         }
 676     }
 677
 678   free (stack);
 679
 680
 681   if (cgraph_dump_file)
 682     {
 683       fprintf (cgraph_dump_file, " Found inline predecesors of %s:",
 684                cgraph_node_name (node));
 685       for (i = 0; i < nfound; i++)
 686         {
 687           fprintf (cgraph_dump_file, " %s", cgraph_node_name (array[i]));
 688           if (INLINED_TIMES (array[i]) != 1)
 689             fprintf (cgraph_dump_file, " (%i times)",
 690                      (int)INLINED_TIMES (array[i]));
 691         }
 692       fprintf (cgraph_dump_file, "\n");
 693     }
 694
 695   return nfound;
 696 }
 697
 698 /* Return list of nodes we decided to inline into NODE, set their output
 699    flag and compute INLINED_TIMES.
 700
 701    This function is identical to cgraph_inlined_into with callers and callees
 702    nodes swapped.  */
 703
 704 static int
 705 cgraph_inlined_callees (struct cgraph_node *node, struct cgraph_node **array)
 706 {
 707   int nfound = 0;
 708   struct cgraph_edge **stack;
 709   struct cgraph_edge *e, *e1;
 710   int sp;
 711   int i;
 712
 713   /* Fast path: since we traverse in mostly topological order, we will likely
 714      find no edges.  */
 715   for (e = node->callees; e; e = e->next_callee)
 716     if (!e->inline_failed)
 717       break;
 718
 719   if (!e)
 720     return 0;
 721
 722   /* Allocate stack for back-tracking up callgraph.  */
 723   stack = xmalloc ((cgraph_n_nodes + 1) * sizeof (struct cgraph_edge));
 724   sp = 0;
 725
 726   /* Push the first edge on to the stack.  */
 727   stack[sp++] = e;
 728
 729   while (sp)
 730     {
 731       struct cgraph_node *callee;
 732
 733       /* Look at the edge on the top of the stack.  */
 734       e = stack[sp - 1];
 735       callee = e->callee;
 736
 737       /* Check if the callee destination has been visited yet.  */
 738       if (!callee->output)
 739         {
 740           array[nfound++] = e->callee;
 741           /* Mark that we have visited the destination.  */
 742           callee->output = true;
 743           SET_INLINED_TIMES (callee, 0);
 744         }
 745       SET_INLINED_TIMES (callee, INLINED_TIMES (callee) + 1);
 746
 747       for (e1 = callee->callees; e1; e1 = e1->next_callee)
 748         if (!e1->inline_failed)
 749           break;
 750       if (e1)
 751         stack[sp++] = e1;
 752       else
 753         {
 754           while (true)
 755             {
 756               for (e1 = e->next_callee; e1; e1 = e1->next_callee)
 757                 if (!e1->inline_failed)
 758                   break;
 759
 760               if (e1)
 761                 {
 762                   stack[sp - 1] = e1;
 763                   break;
 764                 }
 765               else
 766                 {
 767                   sp--;
 768                   if (!sp)
 769                     break;
 770                   e = stack[sp - 1];
 771                 }
 772             }
 773         }
 774     }
 775
 776   free (stack);
 777
 778   if (cgraph_dump_file)
 779     {
 780       fprintf (cgraph_dump_file, " Found inline successors of %s:",
 781                cgraph_node_name (node));
 782       for (i = 0; i < nfound; i++)
 783         {
 784           fprintf (cgraph_dump_file, " %s", cgraph_node_name (array[i]));
 785           if (INLINED_TIMES (array[i]) != 1)
 786             fprintf (cgraph_dump_file, " (%i times)",
 787                      (int)INLINED_TIMES (array[i]));
 788         }
 789       fprintf (cgraph_dump_file, "\n");
 790     }
 791
 792   return nfound;
 793 }
 794
 795 /* Estimate size of the function after inlining WHAT into TO.  */
 796
 797 static int
 798 cgraph_estimate_size_after_inlining (int times, struct cgraph_node *to,
 799                                      struct cgraph_node *what)
 800 {
 801   return (what->global.insns - INSNS_PER_CALL) * times + to->global.insns;
 802 }
 803
 804 /* Estimate the growth caused by inlining NODE into all callees.  */
 805
 806 static int
 807 cgraph_estimate_growth (struct cgraph_node *node)
 808 {
 809   int growth = 0;
 810   int calls_saved = 0;
 811   int clones_added = 0;
 812   struct cgraph_edge *e;
 813
 814   for (e = node->callers; e; e = e->next_caller)
 815     if (e->inline_failed)
 816       {
 817         growth += ((cgraph_estimate_size_after_inlining (1, e->caller, node)
 818                     -
 819                     e->caller->global.insns) *e->caller->global.cloned_times);
 820         calls_saved += e->caller->global.cloned_times;
 821         clones_added += e->caller->global.cloned_times;
 822       }
 823
 824   /* ??? Wrong for self recursive functions or cases where we decide to not
 825      inline for different reasons, but it is not big deal as in that case
 826      we will keep the body around, but we will also avoid some inlining.  */
 827   if (!node->needed && !node->origin && !DECL_EXTERNAL (node->decl))
 828     growth -= node->global.insns, clones_added--;
 829
 830   if (!calls_saved)
 831     calls_saved = 1;
 832
 833   return growth;
 834 }
 835
 836 /* Update insn sizes after inlining WHAT into TO that is already inlined into
 837    all nodes in INLINED array.  */
 838
 839 static void
 840 cgraph_mark_inline (struct cgraph_node *to, struct cgraph_node *what,
 841                     struct cgraph_node **inlined, int ninlined,
 842                     struct cgraph_node **inlined_callees,
 843                     int ninlined_callees)
 844 {
 845   int i;
 846   int times = 0;
 847   int clones = 0;
 848   struct cgraph_edge *e;
 849   bool called = false;
 850   int new_insns;
 851
 852   what->global.inlined = 1;
 853   for (e = what->callers; e; e = e->next_caller)
 854     {
 855       if (e->caller == to)
 856         {
 857           if (!e->inline_failed)
 858             continue;
 859           e->inline_failed = NULL;
 860           times++;
 861           clones += e->caller->global.cloned_times;
 862         }
 863       else if (e->inline_failed)
 864         called = true;
 865     }
 866   if (!times)
 867     abort ();
 868   ncalls_inlined += times;
 869
 870   new_insns = cgraph_estimate_size_after_inlining (times, to, what);
 871   if (to->global.will_be_output)
 872     overall_insns += new_insns - to->global.insns;
 873   to->global.insns = new_insns;
 874
 875   if (!called && !what->needed && !what->origin
 876       && flag_unit_at_a_time
 877       && !DECL_EXTERNAL (what->decl))
 878     {
 879       if (!what->global.will_be_output)
 880         abort ();
 881       clones--;
 882       nfunctions_inlined++;
 883       what->global.will_be_output = 0;
 884       overall_insns -= what->global.insns;
 885     }
 886   what->global.cloned_times += clones;
 887   for (i = 0; i < ninlined; i++)
 888     {
 889       new_insns =
 890         cgraph_estimate_size_after_inlining (INLINED_TIMES (inlined[i]) *
 891                                              times, inlined[i], what);
 892       if (inlined[i]->global.will_be_output)
 893         overall_insns += new_insns - inlined[i]->global.insns;
 894       inlined[i]->global.insns = new_insns;
 895     }
 896   for (i = 0; i < ninlined_callees; i++)
 897     {
 898       inlined_callees[i]->global.cloned_times +=
 899         INLINED_TIMES (inlined_callees[i]) * clones;
 900     }
 901 }
 902
 903 /* Return false when inlining WHAT into TO is not good idea as it would cause
 904    too large growth of function bodies.  */
 905
 906 static bool
 907 cgraph_check_inline_limits (struct cgraph_node *to, struct cgraph_node *what,
 908                             struct cgraph_node **inlined, int ninlined,
 909                             const char **reason)
 910 {
 911   int i;
 912   int times = 0;
 913   struct cgraph_edge *e;
 914   int newsize;
 915   int limit;
 916
 917   for (e = to->callees; e; e = e->next_callee)
 918     if (e->callee == what)
 919       times++;
 920
 921   /* When inlining large function body called once into small function,
 922      take the inlined function as base for limiting the growth.  */
 923   if (to->local.self_insns > what->local.self_insns)
 924     limit = to->local.self_insns;
 925   else
 926     limit = what->local.self_insns;
 927
 928   limit += limit * PARAM_VALUE (PARAM_LARGE_FUNCTION_GROWTH) / 100;
 929
 930   newsize = cgraph_estimate_size_after_inlining (times, to, what);
 931   if (newsize > PARAM_VALUE (PARAM_LARGE_FUNCTION_INSNS)
 932       && newsize > limit)
 933     {
 934       *reason = N_("--param large-function-growth limit reached");
 935       return false;
 936     }
 937   for (i = 0; i < ninlined; i++)
 938     {
 939       newsize =
 940         cgraph_estimate_size_after_inlining (INLINED_TIMES (inlined[i]) *
 941                                              times, inlined[i], what);
 942       if (newsize > PARAM_VALUE (PARAM_LARGE_FUNCTION_INSNS)
 943           && newsize >
 944           inlined[i]->local.self_insns *
 945           (100 + PARAM_VALUE (PARAM_LARGE_FUNCTION_GROWTH)) / 100)
 946         {
 947           *reason = N_("--param large-function-growth limit reached while inlining the caller");
 948           return false;
 949         }
 950     }
 951   return true;
 952 }
 953
 954 /* Return true when function N is small enough to be inlined.  */
 955
 956 static bool
 957 cgraph_default_inline_p (struct cgraph_node *n)
 958 {
 959   if (!DECL_INLINE (n->decl) || !DECL_SAVED_TREE (n->decl))
 960     return false;
 961   if (DECL_DECLARED_INLINE_P (n->decl))
 962     return n->global.insns < MAX_INLINE_INSNS_SINGLE;
 963   else
 964     return n->global.insns < MAX_INLINE_INSNS_AUTO;
 965 }
 966
 967 /* Set inline_failed for all callers of given function to REASON.  */
 968
 969 static void
 970 cgraph_set_inline_failed (struct cgraph_node *node, const char *reason)
 971 {
 972   struct cgraph_edge *e;
 973
 974   if (cgraph_dump_file)
 975     fprintf (cgraph_dump_file, "Inlining failed: %s\n", reason);
 976   for (e = node->callers; e; e = e->next_caller)
 977     if (e->inline_failed)
 978       e->inline_failed = reason;
 979 }
 980
 981 /* We use greedy algorithm for inlining of small functions:
 982    All inline candidates are put into prioritized heap based on estimated
 983    growth of the overall number of instructions and then update the estimates.
 984
 985    INLINED and INLINED_CALEES are just pointers to arrays large enough
 986    to be passed to cgraph_inlined_into and cgraph_inlined_callees.  */
 987
 988 static void
 989 cgraph_decide_inlining_of_small_functions (struct cgraph_node **inlined,
 990                                            struct cgraph_node **inlined_callees)
 991 {
 992   int i;
 993   struct cgraph_node *node;
 994   fibheap_t heap = fibheap_new ();
 995   struct fibnode **heap_node =
 996     xcalloc (cgraph_max_uid, sizeof (struct fibnode *));
 997   int ninlined, ninlined_callees;
 998   int max_insns = ((HOST_WIDEST_INT) initial_insns
 999                    * (100 + PARAM_VALUE (PARAM_INLINE_UNIT_GROWTH)) / 100);
1000
1001   /* Put all inline candidates into the heap.  */
1002
1003   for (node = cgraph_nodes; node; node = node->next)
1004     {
1005       if (!node->local.inlinable || !node->callers
1006           || node->local.disregard_inline_limits)
1007         continue;
1008
1009       if (!cgraph_default_inline_p (node))
1010         {
1011           cgraph_set_inline_failed (node,
1012             N_("--param max-inline-insns-single limit reached"));
1013           continue;
1014         }
1015       heap_node[node->uid] =
1016         fibheap_insert (heap, cgraph_estimate_growth (node), node);
1017     }
1018
1019   if (cgraph_dump_file)
1020     fprintf (cgraph_dump_file, "\nDeciding on smaller functions:\n");
1021   while (overall_insns <= max_insns && (node = fibheap_extract_min (heap)))
1022     {
1023       struct cgraph_edge *e;
1024       int old_insns = overall_insns;
1025
1026       heap_node[node->uid] = NULL;
1027       if (cgraph_dump_file)
1028         fprintf (cgraph_dump_file,
1029                  "\nConsidering %s with %i insns\n"
1030                  " Estimated growth is %+i insns.\n",
1031                  cgraph_node_name (node), node->global.insns,
1032                  cgraph_estimate_growth (node));
1033       if (!cgraph_default_inline_p (node))
1034         {
1035           cgraph_set_inline_failed (node,
1036             N_("--param max-inline-insns-single limit reached after inlining into the callee"));
1037           continue;
1038         }
1039       ninlined_callees = cgraph_inlined_callees (node, inlined_callees);
1040       for (e = node->callers; e; e = e->next_caller)
1041         if (e->inline_failed)
1042           {
1043             /* Marking recursive function inlinine has sane semantic and
1044                thus we should not warn on it.  */
1045             if (e->caller == node)
1046               {
1047                 e->inline_failed = "";
1048                 continue;
1049               }
1050             ninlined = cgraph_inlined_into (e->caller, inlined);
1051             if (e->callee->output)
1052               e->inline_failed = "";
1053             if (e->callee->output
1054                 || !cgraph_check_inline_limits (e->caller, node, inlined,
1055                                                 ninlined, &e->inline_failed))
1056               {
1057                 for (i = 0; i < ninlined; i++)
1058                   inlined[i]->output = 0, node->aux = 0;
1059                 if (cgraph_dump_file)
1060                   fprintf (cgraph_dump_file, " Not inlining into %s.\n",
1061                            cgraph_node_name (e->caller));
1062                 continue;
1063               }
1064             cgraph_mark_inline (e->caller, node, inlined, ninlined,
1065                                 inlined_callees, ninlined_callees);
1066             if (heap_node[e->caller->uid])
1067               fibheap_replace_key (heap, heap_node[e->caller->uid],
1068                                    cgraph_estimate_growth (e->caller));
1069
1070             /* Size of the functions we updated into has changed, so update
1071                the keys.  */
1072             for (i = 0; i < ninlined; i++)
1073               {
1074                 inlined[i]->output = 0, node->aux = 0;
1075                 if (heap_node[inlined[i]->uid])
1076                   fibheap_replace_key (heap, heap_node[inlined[i]->uid],
1077                                        cgraph_estimate_growth (inlined[i]));
1078               }
1079         if (cgraph_dump_file)
1080           fprintf (cgraph_dump_file,
1081                    " Inlined into %s which now has %i insns.\n",
1082                    cgraph_node_name (e->caller),
1083                    e->caller->global.insns);
1084
1085           }
1086
1087       /* Similarly all functions called by the function we just inlined
1088          are now called more times; update keys.  */
1089
1090       for (e = node->callees; e; e = e->next_callee)
1091         if (e->inline_failed && heap_node[e->callee->uid])
1092           fibheap_replace_key (heap, heap_node[e->callee->uid],
1093                                cgraph_estimate_growth (e->callee));
1094
1095       for (i = 0; i < ninlined_callees; i++)
1096         {
1097           struct cgraph_edge *e;
1098
1099           for (e = inlined_callees[i]->callees; e; e = e->next_callee)
1100             if (e->inline_failed && heap_node[e->callee->uid])
1101               fibheap_replace_key (heap, heap_node[e->callee->uid],
1102                                    cgraph_estimate_growth (e->callee));
1103
1104           inlined_callees[i]->output = 0, node->aux = 0;
1105         }
1106       if (cgraph_dump_file)
1107         fprintf (cgraph_dump_file,
1108                  " Inlined %i times for a net change of %+i insns.\n",
1109                  node->global.cloned_times, overall_insns - old_insns);
1110     }
1111   while ((node = fibheap_extract_min (heap)) != NULL)
1112     if (!node->local.disregard_inline_limits)
1113       cgraph_set_inline_failed (node, N_("--param inline-unit-growth limit reached"));
1114   fibheap_delete (heap);
1115   free (heap_node);
1116 }
1117
1118 /* Decide on the inlining.  We do so in the topological order to avoid
1119    expenses on updating datastructures.  */
1120
1121 static void
1122 cgraph_decide_inlining (void)
1123 {
1124   struct cgraph_node *node;
1125   int nnodes;
1126   struct cgraph_node **order =
1127     xcalloc (cgraph_n_nodes, sizeof (struct cgraph_node *));
1128   struct cgraph_node **inlined =
1129     xcalloc (cgraph_n_nodes, sizeof (struct cgraph_node *));
1130   struct cgraph_node **inlined_callees =
1131     xcalloc (cgraph_n_nodes, sizeof (struct cgraph_node *));
1132   int ninlined;
1133   int ninlined_callees;
1134   int old_insns = 0;
1135   int i, y;
1136
1137   for (node = cgraph_nodes; node; node = node->next)
1138     initial_insns += node->local.self_insns;
1139   overall_insns = initial_insns;
1140
1141   nnodes = cgraph_postorder (order);
1142
1143   if (cgraph_dump_file)
1144     fprintf (cgraph_dump_file,
1145              "\nDeciding on inlining.  Starting with %i insns.\n",
1146              initial_insns);
1147
1148   for (node = cgraph_nodes; node; node = node->next)
1149     node->aux = 0;
1150
1151   if (cgraph_dump_file)
1152     fprintf (cgraph_dump_file, "\nInlining always_inline functions:\n");
1153
1154   /* In the first pass mark all always_inline edges.  Do this with a priority
1155      so none of our later choices will make this impossible.  */
1156   for (i = nnodes - 1; i >= 0; i--)
1157     {
1158       struct cgraph_edge *e;
1159
1160       node = order[i];
1161
1162       for (e = node->callees; e; e = e->next_callee)
1163         if (e->callee->local.disregard_inline_limits)
1164           break;
1165       if (!e)
1166         continue;
1167       if (cgraph_dump_file)
1168         fprintf (cgraph_dump_file,
1169                  "\nConsidering %s %i insns (always inline)\n",
1170                  cgraph_node_name (e->callee), e->callee->global.insns);
1171       ninlined = cgraph_inlined_into (order[i], inlined);
1172       for (; e; e = e->next_callee)
1173         {
1174           old_insns = overall_insns;
1175           if (!e->inline_failed || !e->callee->local.inlinable
1176               || !e->callee->local.disregard_inline_limits)
1177             continue;
1178           if (e->callee->output || e->callee == node)
1179             {
1180               e->inline_failed = N_("recursive inlining");
1181               continue;
1182             }
1183           ninlined_callees =
1184             cgraph_inlined_callees (e->callee, inlined_callees);
1185           cgraph_mark_inline (node, e->callee, inlined, ninlined,
1186                               inlined_callees, ninlined_callees);
1187           for (y = 0; y < ninlined_callees; y++)
1188             inlined_callees[y]->output = 0, node->aux = 0;
1189           if (cgraph_dump_file)
1190             fprintf (cgraph_dump_file,
1191                      " Inlined into %s which now has %i insns.\n",
1192                      cgraph_node_name (node->callees->caller),
1193                      node->callees->caller->global.insns);
1194         }
1195       if (cgraph_dump_file && node->global.cloned_times > 0)
1196         fprintf (cgraph_dump_file,
1197                  " Inlined %i times for a net change of %+i insns.\n",
1198                  node->global.cloned_times, overall_insns - old_insns);
1199       for (y = 0; y < ninlined; y++)
1200         inlined[y]->output = 0, node->aux = 0;
1201     }
1202
1203   if (!flag_really_no_inline)
1204     {
1205       cgraph_decide_inlining_of_small_functions (inlined, inlined_callees);
1206
1207       if (cgraph_dump_file)
1208         fprintf (cgraph_dump_file, "\nDeciding on functions called once:\n");
1209
1210       /* And finally decide what functions are called once.  */
1211
1212       for (i = nnodes - 1; i >= 0; i--)
1213         {
1214           node = order[i];
1215
1216           if (node->callers && !node->callers->next_caller && !node->needed
1217               && node->local.inlinable && node->callers->inline_failed
1218               && !DECL_EXTERNAL (node->decl) && !DECL_COMDAT (node->decl))
1219             {
1220               bool ok = true;
1221               struct cgraph_node *node1;
1222
1223               /* Verify that we won't duplicate the caller.  */
1224               for (node1 = node->callers->caller;
1225                    node1->callers && !node1->callers->inline_failed
1226                    && ok; node1 = node1->callers->caller)
1227                 if (node1->callers->next_caller || node1->needed)
1228                   ok = false;
1229               if (ok)
1230                 {
1231                   const char *dummy_reason;
1232                   if (cgraph_dump_file)
1233                     fprintf (cgraph_dump_file,
1234                              "\nConsidering %s %i insns.\n"
1235                              " Called once from %s %i insns.\n",
1236                              cgraph_node_name (node), node->global.insns,
1237                              cgraph_node_name (node->callers->caller),
1238                              node->callers->caller->global.insns);
1239                   ninlined = cgraph_inlined_into (node->callers->caller,
1240                                                   inlined);
1241                   old_insns = overall_insns;
1242
1243                   /* Inlining functions once would never cause inlining warnings.  */
1244                   if (cgraph_check_inline_limits
1245                       (node->callers->caller, node, inlined, ninlined,
1246                        &dummy_reason))
1247                     {
1248                       ninlined_callees =
1249                         cgraph_inlined_callees (node, inlined_callees);
1250                       cgraph_mark_inline (node->callers->caller, node, inlined,
1251                                           ninlined, inlined_callees,
1252                                           ninlined_callees);
1253                       for (y = 0; y < ninlined_callees; y++)
1254                         inlined_callees[y]->output = 0, node->aux = 0;
1255                       if (cgraph_dump_file)
1256                         fprintf (cgraph_dump_file,
1257                                  " Inlined into %s which now has %i insns"
1258                                  " for a net change of %+i insns.\n",
1259                                  cgraph_node_name (node->callers->caller),
1260                                  node->callers->caller->global.insns,
1261                                  overall_insns - old_insns);
1262                     }
1263                   else
1264                     {
1265                       if (cgraph_dump_file)
1266                         fprintf (cgraph_dump_file,
1267                                  " Inline limit reached, not inlined.\n");
1268                     }
1269                   for (y = 0; y < ninlined; y++)
1270                     inlined[y]->output = 0, node->aux = 0;
1271                 }
1272             }
1273         }
1274     }
1275
1276   if (cgraph_dump_file)
1277     fprintf (cgraph_dump_file,
1278              "\nInlined %i calls, eliminated %i functions, "
1279              "%i insns turned to %i insns.\n\n",
1280              ncalls_inlined, nfunctions_inlined, initial_insns,
1281              overall_insns);
1282   free (order);
1283   free (inlined);
1284   free (inlined_callees);
1285 }
1286
1287 /* Decide on the inlining.  We do so in the topological order to avoid
1288    expenses on updating datastructures.  */
1289
1290 static void
1291 cgraph_decide_inlining_incrementally (struct cgraph_node *node)
1292 {
1293   struct cgraph_edge *e;
1294   struct cgraph_node **inlined =
1295     xmalloc (sizeof (struct cgraph_node *) * cgraph_n_nodes);
1296   struct cgraph_node **inlined_callees =
1297     xmalloc (sizeof (struct cgraph_node *) * cgraph_n_nodes);
1298   int ninlined;
1299   int ninlined_callees;
1300   int y;
1301
1302   ninlined = cgraph_inlined_into (node, inlined);
1303
1304   /* First of all look for always inline functions.  */
1305   for (e = node->callees; e; e = e->next_callee)
1306     if (e->callee->local.disregard_inline_limits && e->inline_failed
1307         /* ??? It is possible that renaming variable removed the function body
1308            in duplicate_decls. See gcc.c-torture/compile/20011119-2.c  */
1309         && DECL_SAVED_TREE (e->callee->decl))
1310       {
1311         if (e->callee->output || e->callee == node)
1312           {
1313             e->inline_failed = N_("recursive inlining");
1314             continue;
1315           }
1316         ninlined_callees = cgraph_inlined_callees (e->callee, inlined_callees);
1317         cgraph_mark_inline (node, e->callee, inlined, ninlined,
1318                             inlined_callees, ninlined_callees);
1319         for (y = 0; y < ninlined_callees; y++)
1320           inlined_callees[y]->output = 0, node->aux = 0;
1321       }
1322
1323   if (!flag_really_no_inline)
1324     {
1325       /* Now do the automatic inlining.  */
1326       for (e = node->callees; e; e = e->next_callee)
1327         if (e->callee->local.inlinable && e->inline_failed
1328             && cgraph_default_inline_p (e->callee)
1329             && cgraph_check_inline_limits (node, e->callee, inlined,
1330                                            ninlined, &e->inline_failed)
1331             && DECL_SAVED_TREE (e->callee->decl))
1332           {
1333             /* Marking recursive function inlinine has sane semantic and thus
1334                we should not warn on it.  */
1335             if (e->callee->output || e->callee == node)
1336               {
1337                 e->inline_failed = "";
1338                 continue;
1339               }
1340             ninlined_callees = cgraph_inlined_callees (e->callee,
1341                                                        inlined_callees);
1342             cgraph_mark_inline (node, e->callee, inlined, ninlined,
1343                                 inlined_callees, ninlined_callees);
1344             for (y = 0; y < ninlined_callees; y++)
1345               inlined_callees[y]->output = 0, node->aux = 0;
1346           }
1347     }
1348
1349   /* Clear the flags set by cgraph_inlined_into.  */
1350   for (y = 0; y < ninlined; y++)
1351     inlined[y]->output = 0, node->aux = 0;
1352
1353   free (inlined);
1354   free (inlined_callees);
1355 }
1356
1357
1358 /* Return true when CALLER_DECL should be inlined into CALLEE_DECL.
1359    When returned false and reason is non-NULL, set it to the reason
1360    why the call was not inlined.  */
1361
1362 bool
1363 cgraph_inline_p (tree caller_decl, tree callee_decl, const char **reason)
1364 {
1365   struct cgraph_node *caller = cgraph_node (caller_decl);
1366   struct cgraph_node *callee = cgraph_node (callee_decl);
1367   struct cgraph_edge *e;
1368
1369   for (e = caller->callees; e; e = e->next_callee)
1370     if (e->callee == callee)
1371       {
1372         if (e->inline_failed && reason)
1373           *reason = e->inline_failed;
1374         return !e->inline_failed;
1375       }
1376   /* We do not record builtins in the callgraph.  Perhaps it would make more
1377      sense to do so and then prune out those not overwritten by explicit
1378      function body.  */
1379   if (reason)
1380     *reason = "originally indirect function calls never inlined";
1381   return false;
1382 }
1383 /* Expand all functions that must be output.
1384
1385    Attempt to topologically sort the nodes so function is output when
1386    all called functions are already assembled to allow data to be
1387    propagated across the callgraph.  Use a stack to get smaller distance
1388    between a function and it's callees (later we may choose to use a more
1389    sophisticated algorithm for function reordering; we will likely want
1390    to use subsections to make the output functions appear in top-down
1391    order).  */
1392
1393 static void
1394 cgraph_expand_all_functions (void)
1395 {
1396   struct cgraph_node *node;
1397   struct cgraph_node **order =
1398     xcalloc (cgraph_n_nodes, sizeof (struct cgraph_node *));
1399   int order_pos = 0;
1400   int i;
1401
1402   cgraph_mark_functions_to_output ();
1403
1404   order_pos = cgraph_postorder (order);
1405
1406   for (i = order_pos - 1; i >= 0; i--)
1407     {
1408       node = order[i];
1409       if (node->output)
1410         {
1411           if (!node->reachable)
1412             abort ();
1413           node->output = 0;
1414           cgraph_expand_function (node);
1415         }
1416     }
1417   free (order);
1418 }
1419
1420 /* Mark all local functions.
1421
1422    A local function is one whose calls can occur only in the
1423    current compilation unit and all it's calls are explicit,
1424    so we can change its calling convention.
1425    We simply mark all static functions whose address is not taken
1426    as local.  */
1427
1428 static void
1429 cgraph_mark_local_functions (void)
1430 {
1431   struct cgraph_node *node;
1432
1433   if (cgraph_dump_file)
1434     fprintf (cgraph_dump_file, "\nMarking local functions:");
1435
1436   /* Figure out functions we want to assemble.  */
1437   for (node = cgraph_nodes; node; node = node->next)
1438     {
1439       node->local.local = (!node->needed
1440                            && DECL_SAVED_TREE (node->decl)
1441                            && !TREE_PUBLIC (node->decl));
1442       if (cgraph_dump_file && node->local.local)
1443         fprintf (cgraph_dump_file, " %s", cgraph_node_name (node));
1444     }
1445   if (cgraph_dump_file)
1446     fprintf (cgraph_dump_file, "\n\n");
1447 }
1448
1449 /* Perform simple optimizations based on callgraph.  */
1450
1451 void
1452 cgraph_optimize (void)
1453 {
1454   if (!flag_unit_at_a_time)
1455     return;
1456   timevar_push (TV_CGRAPHOPT);
1457   if (!quiet_flag)
1458     fprintf (stderr, "Performing intraprocedural optimizations\n");
1459
1460   cgraph_mark_local_functions ();
1461   if (cgraph_dump_file)
1462     {
1463       fprintf (cgraph_dump_file, "Marked ");
1464       dump_cgraph (cgraph_dump_file);
1465     }
1466
1467   cgraph_decide_inlining ();
1468   cgraph_global_info_ready = true;
1469   if (cgraph_dump_file)
1470     {
1471       fprintf (cgraph_dump_file, "Optimized ");
1472       dump_cgraph (cgraph_dump_file);
1473     }
1474   timevar_pop (TV_CGRAPHOPT);
1475
1476   /* Output everything.  */
1477   if (!quiet_flag)
1478     fprintf (stderr, "Assembling functions:\n");
1479   cgraph_expand_all_functions ();
1480   if (cgraph_dump_file)
1481     {
1482       fprintf (cgraph_dump_file, "\nFinal ");
1483       dump_cgraph (cgraph_dump_file);
1484     }
1485 }