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