gcc/ipa-inline.c

   1 /* Inlining decision heuristics.
   2    Copyright (C) 2003, 2004, 2007, 2008, 2009, 2010, 2011
   3    Free Software Foundation, Inc.
   4    Contributed by Jan Hubicka
   5
   6 This file is part of GCC.
   7
   8 GCC is free software; you can redistribute it and/or modify it under
   9 the terms of the GNU General Public License as published by the Free
  10 Software Foundation; either version 3, or (at your option) any later
  11 version.
  12
  13 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
  14 WARRANTY; without even the implied warranty of MERCHANTABILITY or
  15 FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  16 for more details.
  17
  18 You should have received a copy of the GNU General Public License
  19 along with GCC; see the file COPYING3.  If not see
  20 <http://www.gnu.org/licenses/>.  */
  21
  22 /*  Inlining decision heuristics
  23
  24     The implementation of inliner is organized as follows:
  25
  26     inlining heuristics limits
  27
  28       can_inline_edge_p allow to check that particular inlining is allowed
  29       by the limits specified by user (allowed function growth, growth and so
  30       on).
  31
  32       Functions are inlined when it is obvious the result is profitable (such
  33       as functions called once or when inlining reduce code size).
  34       In addition to that we perform inlining of small functions and recursive
  35       inlining.
  36
  37     inlining heuristics
  38
  39        The inliner itself is split into two passes:
  40
  41        pass_early_inlining
  42
  43          Simple local inlining pass inlining callees into current function.
  44          This pass makes no use of whole unit analysis and thus it can do only
  45          very simple decisions based on local properties.
  46
  47          The strength of the pass is that it is run in topological order
  48          (reverse postorder) on the callgraph. Functions are converted into SSA
  49          form just before this pass and optimized subsequently. As a result, the
  50          callees of the function seen by the early inliner was already optimized
  51          and results of early inlining adds a lot of optimization opportunities
  52          for the local optimization.
  53
  54          The pass handle the obvious inlining decisions within the compilation
  55          unit - inlining auto inline functions, inlining for size and
  56          flattening.
  57
  58          main strength of the pass is the ability to eliminate abstraction
  59          penalty in C++ code (via combination of inlining and early
  60          optimization) and thus improve quality of analysis done by real IPA
  61          optimizers.
  62
  63          Because of lack of whole unit knowledge, the pass can not really make
  64          good code size/performance tradeoffs.  It however does very simple
  65          speculative inlining allowing code size to grow by
  66          EARLY_INLINING_INSNS when callee is leaf function.  In this case the
  67          optimizations performed later are very likely to eliminate the cost.
  68
  69        pass_ipa_inline
  70
  71          This is the real inliner able to handle inlining with whole program
  72          knowledge. It performs following steps:
  73
  74          1) inlining of small functions.  This is implemented by greedy
  75          algorithm ordering all inlinable cgraph edges by their badness and
  76          inlining them in this order as long as inline limits allows doing so.
  77
  78          This heuristics is not very good on inlining recursive calls. Recursive
  79          calls can be inlined with results similar to loop unrolling. To do so,
  80          special purpose recursive inliner is executed on function when
  81          recursive edge is met as viable candidate.
  82
  83          2) Unreachable functions are removed from callgraph.  Inlining leads
  84          to devirtualization and other modification of callgraph so functions
  85          may become unreachable during the process. Also functions declared as
  86          extern inline or virtual functions are removed, since after inlining
  87          we no longer need the offline bodies.
  88
  89          3) Functions called once and not exported from the unit are inlined.
  90          This should almost always lead to reduction of code size by eliminating
  91          the need for offline copy of the function.  */
  92
  93 #include "config.h"
  94 #include "system.h"
  95 #include "coretypes.h"
  96 #include "tm.h"
  97 #include "tree.h"
  98 #include "tree-inline.h"
  99 #include "langhooks.h"
 100 #include "flags.h"
 101 #include "cgraph.h"
 102 #include "diagnostic.h"
 103 #include "gimple-pretty-print.h"
 104 #include "timevar.h"
 105 #include "params.h"
 106 #include "fibheap.h"
 107 #include "intl.h"
 108 #include "tree-pass.h"
 109 #include "coverage.h"
 110 #include "ggc.h"
 111 #include "rtl.h"
 112 #include "tree-flow.h"
 113 #include "ipa-prop.h"
 114 #include "except.h"
 115 #include "target.h"
 116 #include "ipa-inline.h"
 117 #include "ipa-utils.h"
 118
 119 /* Statistics we collect about inlining algorithm.  */
 120 static int overall_size;
 121 static gcov_type max_count;
 122
 123 /* Return false when inlining edge E would lead to violating
 124    limits on function unit growth or stack usage growth.
 125
 126    The relative function body growth limit is present generally
 127    to avoid problems with non-linear behavior of the compiler.
 128    To allow inlining huge functions into tiny wrapper, the limit
 129    is always based on the bigger of the two functions considered.
 130
 131    For stack growth limits we always base the growth in stack usage
 132    of the callers.  We want to prevent applications from segfaulting
 133    on stack overflow when functions with huge stack frames gets
 134    inlined. */
 135
 136 static bool
 137 caller_growth_limits (struct cgraph_edge *e)
 138 {
 139   struct cgraph_node *to = e->caller;
 140   struct cgraph_node *what = cgraph_function_or_thunk_node (e->callee, NULL);
 141   int newsize;
 142   int limit = 0;
 143   HOST_WIDE_INT stack_size_limit = 0, inlined_stack;
 144   struct inline_summary *info, *what_info, *outer_info = inline_summary (to);
 145
 146   /* Look for function e->caller is inlined to.  While doing
 147      so work out the largest function body on the way.  As
 148      described above, we want to base our function growth
 149      limits based on that.  Not on the self size of the
 150      outer function, not on the self size of inline code
 151      we immediately inline to.  This is the most relaxed
 152      interpretation of the rule "do not grow large functions
 153      too much in order to prevent compiler from exploding".  */
 154   while (true)
 155     {
 156       info = inline_summary (to);
 157       if (limit < info->self_size)
 158         limit = info->self_size;
 159       if (stack_size_limit < info->estimated_self_stack_size)
 160         stack_size_limit = info->estimated_self_stack_size;
 161       if (to->global.inlined_to)
 162         to = to->callers->caller;
 163       else
 164         break;
 165     }
 166
 167   what_info = inline_summary (what);
 168
 169   if (limit < what_info->self_size)
 170     limit = what_info->self_size;
 171
 172   limit += limit * PARAM_VALUE (PARAM_LARGE_FUNCTION_GROWTH) / 100;
 173
 174   /* Check the size after inlining against the function limits.  But allow
 175      the function to shrink if it went over the limits by forced inlining.  */
 176   newsize = estimate_size_after_inlining (to, e);
 177   if (newsize >= info->size
 178       && newsize > PARAM_VALUE (PARAM_LARGE_FUNCTION_INSNS)
 179       && newsize > limit)
 180     {
 181       e->inline_failed = CIF_LARGE_FUNCTION_GROWTH_LIMIT;
 182       return false;
 183     }
 184
 185   if (!what_info->estimated_stack_size)
 186     return true;
 187
 188   /* FIXME: Stack size limit often prevents inlining in Fortran programs
 189      due to large i/o datastructures used by the Fortran front-end.
 190      We ought to ignore this limit when we know that the edge is executed
 191      on every invocation of the caller (i.e. its call statement dominates
 192      exit block).  We do not track this information, yet.  */
 193   stack_size_limit += ((gcov_type)stack_size_limit
 194                        * PARAM_VALUE (PARAM_STACK_FRAME_GROWTH) / 100);
 195
 196   inlined_stack = (outer_info->stack_frame_offset
 197                    + outer_info->estimated_self_stack_size
 198                    + what_info->estimated_stack_size);
 199   /* Check new stack consumption with stack consumption at the place
 200      stack is used.  */
 201   if (inlined_stack > stack_size_limit
 202       /* If function already has large stack usage from sibling
 203          inline call, we can inline, too.
 204          This bit overoptimistically assume that we are good at stack
 205          packing.  */
 206       && inlined_stack > info->estimated_stack_size
 207       && inlined_stack > PARAM_VALUE (PARAM_LARGE_STACK_FRAME))
 208     {
 209       e->inline_failed = CIF_LARGE_STACK_FRAME_GROWTH_LIMIT;
 210       return false;
 211     }
 212   return true;
 213 }
 214
 215 /* Dump info about why inlining has failed.  */
 216
 217 static void
 218 report_inline_failed_reason (struct cgraph_edge *e)
 219 {
 220   if (dump_file)
 221     {
 222       fprintf (dump_file, "  not inlinable: %s/%i -> %s/%i, %s\n",
 223                cgraph_node_name (e->caller), e->caller->uid,
 224                cgraph_node_name (e->callee), e->callee->uid,
 225                cgraph_inline_failed_string (e->inline_failed));
 226     }
 227 }
 228
 229 /* Decide if we can inline the edge and possibly update
 230    inline_failed reason.
 231    We check whether inlining is possible at all and whether
 232    caller growth limits allow doing so.
 233
 234    if REPORT is true, output reason to the dump file.  */
 235
 236 static bool
 237 can_inline_edge_p (struct cgraph_edge *e, bool report)
 238 {
 239   bool inlinable = true;
 240   enum availability avail;
 241   struct cgraph_node *callee
 242     = cgraph_function_or_thunk_node (e->callee, &avail);
 243   tree caller_tree = DECL_FUNCTION_SPECIFIC_OPTIMIZATION (e->caller->decl);
 244   tree callee_tree
 245     = callee ? DECL_FUNCTION_SPECIFIC_OPTIMIZATION (callee->decl) : NULL;
 246   struct function *caller_cfun = DECL_STRUCT_FUNCTION (e->caller->decl);
 247   struct function *callee_cfun
 248     = callee ? DECL_STRUCT_FUNCTION (callee->decl) : NULL;
 249
 250   if (!caller_cfun && e->caller->clone_of)
 251     caller_cfun = DECL_STRUCT_FUNCTION (e->caller->clone_of->decl);
 252
 253   if (!callee_cfun && callee && callee->clone_of)
 254     callee_cfun = DECL_STRUCT_FUNCTION (callee->clone_of->decl);
 255
 256   gcc_assert (e->inline_failed);
 257
 258   if (!callee || !callee->analyzed)
 259     {
 260       e->inline_failed = CIF_BODY_NOT_AVAILABLE;
 261       inlinable = false;
 262     }
 263   else if (!inline_summary (callee)->inlinable)
 264     {
 265       e->inline_failed = CIF_FUNCTION_NOT_INLINABLE;
 266       inlinable = false;
 267     }
 268   else if (avail <= AVAIL_OVERWRITABLE)
 269     {
 270       e->inline_failed = CIF_OVERWRITABLE;
 271       return false;
 272     }
 273   else if (e->call_stmt_cannot_inline_p)
 274     {
 275       e->inline_failed = CIF_MISMATCHED_ARGUMENTS;
 276       inlinable = false;
 277     }
 278   /* Don't inline if the functions have different EH personalities.  */
 279   else if (DECL_FUNCTION_PERSONALITY (e->caller->decl)
 280            && DECL_FUNCTION_PERSONALITY (callee->decl)
 281            && (DECL_FUNCTION_PERSONALITY (e->caller->decl)
 282                != DECL_FUNCTION_PERSONALITY (callee->decl)))
 283     {
 284       e->inline_failed = CIF_EH_PERSONALITY;
 285       inlinable = false;
 286     }
 287   /* Don't inline if the callee can throw non-call exceptions but the
 288      caller cannot.
 289      FIXME: this is obviously wrong for LTO where STRUCT_FUNCTION is missing.
 290      Move the flag into cgraph node or mirror it in the inline summary.  */
 291   else if (callee_cfun && callee_cfun->can_throw_non_call_exceptions
 292            && !(caller_cfun && caller_cfun->can_throw_non_call_exceptions))
 293     {
 294       e->inline_failed = CIF_NON_CALL_EXCEPTIONS;
 295       inlinable = false;
 296     }
 297   /* Check compatibility of target optimization options.  */
 298   else if (!targetm.target_option.can_inline_p (e->caller->decl,
 299                                                 callee->decl))
 300     {
 301       e->inline_failed = CIF_TARGET_OPTION_MISMATCH;
 302       inlinable = false;
 303     }
 304   /* Check if caller growth allows the inlining.  */
 305   else if (!DECL_DISREGARD_INLINE_LIMITS (callee->decl)
 306            && !lookup_attribute ("flatten",
 307                                  DECL_ATTRIBUTES
 308                                    (e->caller->global.inlined_to
 309                                     ? e->caller->global.inlined_to->decl
 310                                     : e->caller->decl))
 311            && !caller_growth_limits (e))
 312     inlinable = false;
 313   /* Don't inline a function with a higher optimization level than the
 314      caller.  FIXME: this is really just tip of iceberg of handling
 315      optimization attribute.  */
 316   else if (caller_tree != callee_tree)
 317     {
 318       struct cl_optimization *caller_opt
 319         = TREE_OPTIMIZATION ((caller_tree)
 320                              ? caller_tree
 321                              : optimization_default_node);
 322
 323       struct cl_optimization *callee_opt
 324         = TREE_OPTIMIZATION ((callee_tree)
 325                              ? callee_tree
 326                              : optimization_default_node);
 327
 328       if (((caller_opt->x_optimize > callee_opt->x_optimize)
 329            || (caller_opt->x_optimize_size != callee_opt->x_optimize_size))
 330           /* gcc.dg/pr43564.c.  Look at forced inline even in -O0.  */
 331           && !DECL_DISREGARD_INLINE_LIMITS (e->callee->decl))
 332         {
 333           e->inline_failed = CIF_OPTIMIZATION_MISMATCH;
 334           inlinable = false;
 335         }
 336     }
 337
 338   /* Be sure that the cannot_inline_p flag is up to date.  */
 339   gcc_checking_assert (!e->call_stmt
 340                        || (gimple_call_cannot_inline_p (e->call_stmt)
 341                            == e->call_stmt_cannot_inline_p)
 342                        /* In -flto-partition=none mode we really keep things out of
 343                           sync because call_stmt_cannot_inline_p is set at cgraph
 344                           merging when function bodies are not there yet.  */
 345                        || (in_lto_p && !gimple_call_cannot_inline_p (e->call_stmt)));
 346   if (!inlinable && report)
 347     report_inline_failed_reason (e);
 348   return inlinable;
 349 }
 350
 351
 352 /* Return true if the edge E is inlinable during early inlining.  */
 353
 354 static bool
 355 can_early_inline_edge_p (struct cgraph_edge *e)
 356 {
 357   struct cgraph_node *callee = cgraph_function_or_thunk_node (e->callee,
 358                                                               NULL);
 359   /* Early inliner might get called at WPA stage when IPA pass adds new
 360      function.  In this case we can not really do any of early inlining
 361      because function bodies are missing.  */
 362   if (!gimple_has_body_p (callee->decl))
 363     {
 364       e->inline_failed = CIF_BODY_NOT_AVAILABLE;
 365       return false;
 366     }
 367   /* In early inliner some of callees may not be in SSA form yet
 368      (i.e. the callgraph is cyclic and we did not process
 369      the callee by early inliner, yet).  We don't have CIF code for this
 370      case; later we will re-do the decision in the real inliner.  */
 371   if (!gimple_in_ssa_p (DECL_STRUCT_FUNCTION (e->caller->decl))
 372       || !gimple_in_ssa_p (DECL_STRUCT_FUNCTION (callee->decl)))
 373     {
 374       if (dump_file)
 375         fprintf (dump_file, "  edge not inlinable: not in SSA form\n");
 376       return false;
 377     }
 378   if (!can_inline_edge_p (e, true))
 379     return false;
 380   return true;
 381 }
 382
 383
 384 /* Return true when N is leaf function.  Accept cheap builtins
 385    in leaf functions.  */
 386
 387 static bool
 388 leaf_node_p (struct cgraph_node *n)
 389 {
 390   struct cgraph_edge *e;
 391   for (e = n->callees; e; e = e->next_callee)
 392     if (!is_inexpensive_builtin (e->callee->decl))
 393       return false;
 394   return true;
 395 }
 396
 397
 398 /* Return true if we are interested in inlining small function.  */
 399
 400 static bool
 401 want_early_inline_function_p (struct cgraph_edge *e)
 402 {
 403   bool want_inline = true;
 404   struct cgraph_node *callee = cgraph_function_or_thunk_node (e->callee, NULL);
 405
 406   if (DECL_DISREGARD_INLINE_LIMITS (callee->decl))
 407     ;
 408   else if (!DECL_DECLARED_INLINE_P (callee->decl)
 409            && !flag_inline_small_functions)
 410     {
 411       e->inline_failed = CIF_FUNCTION_NOT_INLINE_CANDIDATE;
 412       report_inline_failed_reason (e);
 413       want_inline = false;
 414     }
 415   else
 416     {
 417       int growth = estimate_edge_growth (e);
 418       if (growth <= 0)
 419         ;
 420       else if (!cgraph_maybe_hot_edge_p (e)
 421                && growth > 0)
 422         {
 423           if (dump_file)
 424             fprintf (dump_file, "  will not early inline: %s/%i->%s/%i, "
 425                      "call is cold and code would grow by %i\n",
 426                      cgraph_node_name (e->caller), e->caller->uid,
 427                      cgraph_node_name (callee), callee->uid,
 428                      growth);
 429           want_inline = false;
 430         }
 431       else if (!leaf_node_p (callee)
 432                && growth > 0)
 433         {
 434           if (dump_file)
 435             fprintf (dump_file, "  will not early inline: %s/%i->%s/%i, "
 436                      "callee is not leaf and code would grow by %i\n",
 437                      cgraph_node_name (e->caller), e->caller->uid,
 438                      cgraph_node_name (callee), callee->uid,
 439                      growth);
 440           want_inline = false;
 441         }
 442       else if (growth > PARAM_VALUE (PARAM_EARLY_INLINING_INSNS))
 443         {
 444           if (dump_file)
 445             fprintf (dump_file, "  will not early inline: %s/%i->%s/%i, "
 446                      "growth %i exceeds --param early-inlining-insns\n",
 447                      cgraph_node_name (e->caller), e->caller->uid,
 448                      cgraph_node_name (callee), callee->uid,
 449                      growth);
 450           want_inline = false;
 451         }
 452     }
 453   return want_inline;
 454 }
 455
 456 /* Return true if we are interested in inlining small function.
 457    When REPORT is true, report reason to dump file.  */
 458
 459 static bool
 460 want_inline_small_function_p (struct cgraph_edge *e, bool report)
 461 {
 462   bool want_inline = true;
 463   struct cgraph_node *callee = cgraph_function_or_thunk_node (e->callee, NULL);
 464
 465   if (DECL_DISREGARD_INLINE_LIMITS (callee->decl))
 466     ;
 467   else if (!DECL_DECLARED_INLINE_P (callee->decl)
 468            && !flag_inline_small_functions)
 469     {
 470       e->inline_failed = CIF_FUNCTION_NOT_INLINE_CANDIDATE;
 471       want_inline = false;
 472     }
 473   else
 474     {
 475       int growth = estimate_edge_growth (e);
 476
 477       if (growth <= 0)
 478         ;
 479       else if (DECL_DECLARED_INLINE_P (callee->decl)
 480                && growth >= MAX_INLINE_INSNS_SINGLE)
 481         {
 482           e->inline_failed = CIF_MAX_INLINE_INSNS_SINGLE_LIMIT;
 483           want_inline = false;
 484         }
 485       else if (!DECL_DECLARED_INLINE_P (callee->decl)
 486                && !flag_inline_functions)
 487         {
 488           e->inline_failed = CIF_NOT_DECLARED_INLINED;
 489           want_inline = false;
 490         }
 491       else if (!DECL_DECLARED_INLINE_P (callee->decl)
 492                && growth >= MAX_INLINE_INSNS_AUTO)
 493         {
 494           e->inline_failed = CIF_MAX_INLINE_INSNS_AUTO_LIMIT;
 495           want_inline = false;
 496         }
 497       /* If call is cold, do not inline when function body would grow.
 498          Still inline when the overall unit size will shrink because the offline
 499          copy of function being eliminated.
 500
 501          This is slightly wrong on aggressive side:  it is entirely possible
 502          that function is called many times with a context where inlining
 503          reduces code size and few times with a context where inlining increase
 504          code size.  Resoluting growth estimate will be negative even if it
 505          would make more sense to keep offline copy and do not inline into the
 506          call sites that makes the code size grow.
 507
 508          When badness orders the calls in a way that code reducing calls come
 509          first, this situation is not a problem at all: after inlining all
 510          "good" calls, we will realize that keeping the function around is
 511          better.  */
 512       else if (!cgraph_maybe_hot_edge_p (e)
 513                && (DECL_EXTERNAL (callee->decl)
 514
 515                    /* Unlike for functions called once, we play unsafe with
 516                       COMDATs.  We can allow that since we know functions
 517                       in consideration are small (and thus risk is small) and
 518                       moreover grow estimates already accounts that COMDAT
 519                       functions may or may not disappear when eliminated from
 520                       current unit. With good probability making aggressive
 521                       choice in all units is going to make overall program
 522                       smaller.
 523
 524                       Consequently we ask cgraph_can_remove_if_no_direct_calls_p
 525                       instead of
 526                       cgraph_will_be_removed_from_program_if_no_direct_calls  */
 527
 528                    || !cgraph_can_remove_if_no_direct_calls_p (callee)
 529                    || estimate_growth (callee) > 0))
 530         {
 531           e->inline_failed = CIF_UNLIKELY_CALL;
 532           want_inline = false;
 533         }
 534     }
 535   if (!want_inline && report)
 536     report_inline_failed_reason (e);
 537   return want_inline;
 538 }
 539
 540 /* EDGE is self recursive edge.
 541    We hand two cases - when function A is inlining into itself
 542    or when function A is being inlined into another inliner copy of function
 543    A within function B.
 544
 545    In first case OUTER_NODE points to the toplevel copy of A, while
 546    in the second case OUTER_NODE points to the outermost copy of A in B.
 547
 548    In both cases we want to be extra selective since
 549    inlining the call will just introduce new recursive calls to appear.  */
 550
 551 static bool
 552 want_inline_self_recursive_call_p (struct cgraph_edge *edge,
 553                                    struct cgraph_node *outer_node,
 554                                    bool peeling,
 555                                    int depth)
 556 {
 557   char const *reason = NULL;
 558   bool want_inline = true;
 559   int caller_freq = CGRAPH_FREQ_BASE;
 560   int max_depth = PARAM_VALUE (PARAM_MAX_INLINE_RECURSIVE_DEPTH_AUTO);
 561
 562   if (DECL_DECLARED_INLINE_P (edge->caller->decl))
 563     max_depth = PARAM_VALUE (PARAM_MAX_INLINE_RECURSIVE_DEPTH);
 564
 565   if (!cgraph_maybe_hot_edge_p (edge))
 566     {
 567       reason = "recursive call is cold";
 568       want_inline = false;
 569     }
 570   else if (max_count && !outer_node->count)
 571     {
 572       reason = "not executed in profile";
 573       want_inline = false;
 574     }
 575   else if (depth > max_depth)
 576     {
 577       reason = "--param max-inline-recursive-depth exceeded.";
 578       want_inline = false;
 579     }
 580
 581   if (outer_node->global.inlined_to)
 582     caller_freq = outer_node->callers->frequency;
 583
 584   if (!want_inline)
 585     ;
 586   /* Inlining of self recursive function into copy of itself within other function
 587      is transformation similar to loop peeling.
 588
 589      Peeling is profitable if we can inline enough copies to make probability
 590      of actual call to the self recursive function very small.  Be sure that
 591      the probability of recursion is small.
 592
 593      We ensure that the frequency of recursing is at most 1 - (1/max_depth).
 594      This way the expected number of recision is at most max_depth.  */
 595   else if (peeling)
 596     {
 597       int max_prob = CGRAPH_FREQ_BASE - ((CGRAPH_FREQ_BASE + max_depth - 1)
 598                                          / max_depth);
 599       int i;
 600       for (i = 1; i < depth; i++)
 601         max_prob = max_prob * max_prob / CGRAPH_FREQ_BASE;
 602       if (max_count
 603           && (edge->count * CGRAPH_FREQ_BASE / outer_node->count
 604               >= max_prob))
 605         {
 606           reason = "profile of recursive call is too large";
 607           want_inline = false;
 608         }
 609       if (!max_count
 610           && (edge->frequency * CGRAPH_FREQ_BASE / caller_freq
 611               >= max_prob))
 612         {
 613           reason = "frequency of recursive call is too large";
 614           want_inline = false;
 615         }
 616     }
 617   /* Recursive inlining, i.e. equivalent of unrolling, is profitable if recursion
 618      depth is large.  We reduce function call overhead and increase chances that
 619      things fit in hardware return predictor.
 620
 621      Recursive inlining might however increase cost of stack frame setup
 622      actually slowing down functions whose recursion tree is wide rather than
 623      deep.
 624
 625      Deciding reliably on when to do recursive inlining without profile feedback
 626      is tricky.  For now we disable recursive inlining when probability of self
 627      recursion is low.
 628
 629      Recursive inlining of self recursive call within loop also results in large loop
 630      depths that generally optimize badly.  We may want to throttle down inlining
 631      in those cases.  In particular this seems to happen in one of libstdc++ rb tree
 632      methods.  */
 633   else
 634     {
 635       if (max_count
 636           && (edge->count * 100 / outer_node->count
 637               <= PARAM_VALUE (PARAM_MIN_INLINE_RECURSIVE_PROBABILITY)))
 638         {
 639           reason = "profile of recursive call is too small";
 640           want_inline = false;
 641         }
 642       else if (!max_count
 643                && (edge->frequency * 100 / caller_freq
 644                    <= PARAM_VALUE (PARAM_MIN_INLINE_RECURSIVE_PROBABILITY)))
 645         {
 646           reason = "frequency of recursive call is too small";
 647           want_inline = false;
 648         }
 649     }
 650   if (!want_inline && dump_file)
 651     fprintf (dump_file, "   not inlining recursively: %s\n", reason);
 652   return want_inline;
 653 }
 654
 655 /* Return true when NODE has caller other than EDGE.
 656    Worker for cgraph_for_node_and_aliases.  */
 657
 658 static bool
 659 check_caller_edge (struct cgraph_node *node, void *edge)
 660 {
 661   return (node->callers
 662           && node->callers != edge);
 663 }
 664
 665
 666 /* Decide if NODE is called once inlining it would eliminate need
 667    for the offline copy of function.  */
 668
 669 static bool
 670 want_inline_function_called_once_p (struct cgraph_node *node)
 671 {
 672    struct cgraph_node *function = cgraph_function_or_thunk_node (node, NULL);
 673    /* Already inlined?  */
 674    if (function->global.inlined_to)
 675      return false;
 676    /* Zero or more then one callers?  */
 677    if (!node->callers
 678        || node->callers->next_caller)
 679      return false;
 680    /* Maybe other aliases has more direct calls.  */
 681    if (cgraph_for_node_and_aliases (node, check_caller_edge, node->callers, true))
 682      return false;
 683    /* Recursive call makes no sense to inline.  */
 684    if (cgraph_edge_recursive_p (node->callers))
 685      return false;
 686    /* External functions are not really in the unit, so inlining
 687       them when called once would just increase the program size.  */
 688    if (DECL_EXTERNAL (function->decl))
 689      return false;
 690    /* Offline body must be optimized out.  */
 691    if (!cgraph_will_be_removed_from_program_if_no_direct_calls (function))
 692      return false;
 693    if (!can_inline_edge_p (node->callers, true))
 694      return false;
 695    return true;
 696 }
 697
 698
 699 /* Return relative time improvement for inlining EDGE in range
 700    1...2^9.  */
 701
 702 static inline int
 703 relative_time_benefit (struct inline_summary *callee_info,
 704                        struct cgraph_edge *edge,
 705                        int time_growth)
 706 {
 707   int relbenefit;
 708   gcov_type uninlined_call_time;
 709
 710   uninlined_call_time =
 711     ((gcov_type)
 712      (callee_info->time
 713       + inline_edge_summary (edge)->call_stmt_time) * edge->frequency
 714      + CGRAPH_FREQ_BASE / 2) / CGRAPH_FREQ_BASE;
 715   /* Compute relative time benefit, i.e. how much the call becomes faster.
 716      ??? perhaps computing how much the caller+calle together become faster
 717      would lead to more realistic results.  */
 718   if (!uninlined_call_time)
 719     uninlined_call_time = 1;
 720   relbenefit =
 721     (uninlined_call_time - time_growth) * 256 / (uninlined_call_time);
 722   relbenefit = MIN (relbenefit, 512);
 723   relbenefit = MAX (relbenefit, 1);
 724   return relbenefit;
 725 }
 726
 727
 728 /* A cost model driving the inlining heuristics in a way so the edges with
 729    smallest badness are inlined first.  After each inlining is performed
 730    the costs of all caller edges of nodes affected are recomputed so the
 731    metrics may accurately depend on values such as number of inlinable callers
 732    of the function or function body size.  */
 733
 734 static int
 735 edge_badness (struct cgraph_edge *edge, bool dump)
 736 {
 737   gcov_type badness;
 738   int growth, time_growth;
 739   struct cgraph_node *callee = cgraph_function_or_thunk_node (edge->callee,
 740                                                               NULL);
 741   struct inline_summary *callee_info = inline_summary (callee);
 742
 743   if (DECL_DISREGARD_INLINE_LIMITS (callee->decl))
 744     return INT_MIN;
 745
 746   growth = estimate_edge_growth (edge);
 747   time_growth = estimate_edge_time (edge);
 748
 749   if (dump)
 750     {
 751       fprintf (dump_file, "    Badness calculation for %s -> %s\n",
 752                cgraph_node_name (edge->caller),
 753                cgraph_node_name (callee));
 754       fprintf (dump_file, "      size growth %i, time growth %i\n",
 755                growth,
 756                time_growth);
 757     }
 758
 759   /* Always prefer inlining saving code size.  */
 760   if (growth <= 0)
 761     {
 762       badness = INT_MIN / 2 + growth;
 763       if (dump)
 764         fprintf (dump_file, "      %i: Growth %i <= 0\n", (int) badness,
 765                  growth);
 766     }
 767
 768   /* When profiling is available, compute badness as:
 769
 770                 relative_edge_count * relative_time_benefit
 771      goodness = -------------------------------------------
 772                 edge_growth
 773      badness = -goodness
 774
 775     The fraction is upside down, becuase on edge counts and time beneits
 776     the bounds are known. Edge growth is essentially unlimited.  */
 777
 778   else if (max_count)
 779     {
 780       int relbenefit = relative_time_benefit (callee_info, edge, time_growth);
 781       badness =
 782         ((int)
 783          ((double) edge->count * INT_MIN / 2 / max_count / 512) *
 784          relative_time_benefit (callee_info, edge, time_growth)) / growth;
 785
 786       /* Be sure that insanity of the profile won't lead to increasing counts
 787          in the scalling and thus to overflow in the computation above.  */
 788       gcc_assert (max_count >= edge->count);
 789       if (dump)
 790         {
 791           fprintf (dump_file,
 792                    "      %i (relative %f): profile info. Relative count %f"
 793                    " * Relative benefit %f\n",
 794                    (int) badness, (double) badness / INT_MIN,
 795                    (double) edge->count / max_count,
 796                    relbenefit * 100 / 256.0);
 797         }
 798     }
 799
 800   /* When function local profile is available. Compute badness as:
 801
 802
 803                growth_of_callee
 804      badness = -------------------------------------- + growth_for-all
 805                relative_time_benefit * edge_frequency
 806
 807   */
 808   else if (flag_guess_branch_prob)
 809     {
 810       int div = edge->frequency * (1<<10) / CGRAPH_FREQ_MAX;
 811       int growth_for_all;
 812
 813       div = MAX (div, 1);
 814       gcc_checking_assert (edge->frequency <= CGRAPH_FREQ_MAX);
 815       div *= relative_time_benefit (callee_info, edge, time_growth);
 816
 817       /* frequency is normalized in range 1...2^10.
 818          relbenefit in range 1...2^9
 819          DIV should be in range 1....2^19.  */
 820       gcc_checking_assert (div >= 1 && div <= (1<<19));
 821
 822       /* Result must be integer in range 0...INT_MAX.
 823          Set the base of fixed point calculation so we don't lose much of
 824          precision for small bandesses (those are interesting) yet we don't
 825          overflow for growths that are still in interesting range.
 826
 827          Fixed point arithmetic with point at 8th bit. */
 828       badness = ((gcov_type)growth) * (1<<(19+8));
 829       badness = (badness + div / 2) / div;
 830
 831       /* Overall growth of inlining all calls of function matters: we want to
 832          inline so offline copy of function is no longer needed.
 833
 834          Additionally functions that can be fully inlined without much of
 835          effort are better inline candidates than functions that can be fully
 836          inlined only after noticeable overall unit growths. The latter
 837          are better in a sense compressing of code size by factoring out common
 838          code into separate function shared by multiple code paths.
 839
 840          We might mix the valud into the fraction by taking into account
 841          relative growth of the unit, but for now just add the number
 842          into resulting fraction.  */
 843       if (badness > INT_MAX / 2)
 844         {
 845           badness = INT_MAX / 2;
 846           if (dump)
 847             fprintf (dump_file, "Badness overflow\n");
 848         }
 849       growth_for_all = estimate_growth (callee);
 850       badness += growth_for_all;
 851       if (dump)
 852         {
 853           fprintf (dump_file,
 854                    "      %i: guessed profile. frequency %f, overall growth %i,"
 855                    " benefit %f%%, divisor %i\n",
 856                    (int) badness, (double)edge->frequency / CGRAPH_FREQ_BASE, growth_for_all,
 857                    relative_time_benefit (callee_info, edge, time_growth) * 100 / 256.0, div);
 858         }
 859     }
 860   /* When function local profile is not available or it does not give
 861      useful information (ie frequency is zero), base the cost on
 862      loop nest and overall size growth, so we optimize for overall number
 863      of functions fully inlined in program.  */
 864   else
 865     {
 866       int nest = MIN (inline_edge_summary (edge)->loop_depth, 8);
 867       badness = estimate_growth (callee) * 256;
 868
 869       /* Decrease badness if call is nested.  */
 870       if (badness > 0)
 871         badness >>= nest;
 872       else
 873         {
 874           badness <<= nest;
 875         }
 876       if (dump)
 877         fprintf (dump_file, "      %i: no profile. nest %i\n", (int) badness,
 878                  nest);
 879     }
 880
 881   /* Ensure that we did not overflow in all the fixed point math above.  */
 882   gcc_assert (badness >= INT_MIN);
 883   gcc_assert (badness <= INT_MAX - 1);
 884   /* Make recursive inlining happen always after other inlining is done.  */
 885   if (cgraph_edge_recursive_p (edge))
 886     return badness + 1;
 887   else
 888     return badness;
 889 }
 890
 891 /* Recompute badness of EDGE and update its key in HEAP if needed.  */
 892 static inline void
 893 update_edge_key (fibheap_t heap, struct cgraph_edge *edge)
 894 {
 895   int badness = edge_badness (edge, false);
 896   if (edge->aux)
 897     {
 898       fibnode_t n = (fibnode_t) edge->aux;
 899       gcc_checking_assert (n->data == edge);
 900
 901       /* fibheap_replace_key only decrease the keys.
 902          When we increase the key we do not update heap
 903          and instead re-insert the element once it becomes
 904          a minimum of heap.  */
 905       if (badness < n->key)
 906         {
 907           if (dump_file && (dump_flags & TDF_DETAILS))
 908             {
 909               fprintf (dump_file,
 910                        "  decreasing badness %s/%i -> %s/%i, %i to %i\n",
 911                        cgraph_node_name (edge->caller), edge->caller->uid,
 912                        cgraph_node_name (edge->callee), edge->callee->uid,
 913                        (int)n->key,
 914                        badness);
 915             }
 916           fibheap_replace_key (heap, n, badness);
 917           gcc_checking_assert (n->key == badness);
 918         }
 919     }
 920   else
 921     {
 922        if (dump_file && (dump_flags & TDF_DETAILS))
 923          {
 924            fprintf (dump_file,
 925                     "  enqueuing call %s/%i -> %s/%i, badness %i\n",
 926                     cgraph_node_name (edge->caller), edge->caller->uid,
 927                     cgraph_node_name (edge->callee), edge->callee->uid,
 928                     badness);
 929          }
 930       edge->aux = fibheap_insert (heap, badness, edge);
 931     }
 932 }
 933
 934
 935 /* NODE was inlined.
 936    All caller edges needs to be resetted because
 937    size estimates change. Similarly callees needs reset
 938    because better context may be known.  */
 939
 940 static void
 941 reset_edge_caches (struct cgraph_node *node)
 942 {
 943   struct cgraph_edge *edge;
 944   struct cgraph_edge *e = node->callees;
 945   struct cgraph_node *where = node;
 946   int i;
 947   struct ipa_ref *ref;
 948
 949   if (where->global.inlined_to)
 950     where = where->global.inlined_to;
 951
 952   /* WHERE body size has changed, the cached growth is invalid.  */
 953   reset_node_growth_cache (where);
 954
 955   for (edge = where->callers; edge; edge = edge->next_caller)
 956     if (edge->inline_failed)
 957       reset_edge_growth_cache (edge);
 958   for (i = 0; ipa_ref_list_refering_iterate (&where->ref_list, i, ref); i++)
 959     if (ref->use == IPA_REF_ALIAS)
 960       reset_edge_caches (ipa_ref_refering_node (ref));
 961
 962   if (!e)
 963     return;
 964
 965   while (true)
 966     if (!e->inline_failed && e->callee->callees)
 967       e = e->callee->callees;
 968     else
 969       {
 970         if (e->inline_failed)
 971           reset_edge_growth_cache (e);
 972         if (e->next_callee)
 973           e = e->next_callee;
 974         else
 975           {
 976             do
 977               {
 978                 if (e->caller == node)
 979                   return;
 980                 e = e->caller->callers;
 981               }
 982             while (!e->next_callee);
 983             e = e->next_callee;
 984           }
 985       }
 986 }
 987
 988 /* Recompute HEAP nodes for each of caller of NODE.
 989    UPDATED_NODES track nodes we already visited, to avoid redundant work.
 990    When CHECK_INLINABLITY_FOR is set, re-check for specified edge that
 991    it is inlinable. Otherwise check all edges.  */
 992
 993 static void
 994 update_caller_keys (fibheap_t heap, struct cgraph_node *node,
 995                     bitmap updated_nodes,
 996                     struct cgraph_edge *check_inlinablity_for)
 997 {
 998   struct cgraph_edge *edge;
 999   int i;
1000   struct ipa_ref *ref;
1001
1002   if ((!node->alias && !inline_summary (node)->inlinable)
1003       || cgraph_function_body_availability (node) <= AVAIL_OVERWRITABLE
1004       || node->global.inlined_to)
1005     return;
1006   if (!bitmap_set_bit (updated_nodes, node->uid))
1007     return;
1008
1009   for (i = 0; ipa_ref_list_refering_iterate (&node->ref_list, i, ref); i++)
1010     if (ref->use == IPA_REF_ALIAS)
1011       {
1012         struct cgraph_node *alias = ipa_ref_refering_node (ref);
1013         update_caller_keys (heap, alias, updated_nodes, check_inlinablity_for);
1014       }
1015
1016   for (edge = node->callers; edge; edge = edge->next_caller)
1017     if (edge->inline_failed)
1018       {
1019         if (!check_inlinablity_for
1020             || check_inlinablity_for == edge)
1021           {
1022             if (can_inline_edge_p (edge, false)
1023                 && want_inline_small_function_p (edge, false))
1024               update_edge_key (heap, edge);
1025             else if (edge->aux)
1026               {
1027                 report_inline_failed_reason (edge);
1028                 fibheap_delete_node (heap, (fibnode_t) edge->aux);
1029                 edge->aux = NULL;
1030               }
1031           }
1032         else if (edge->aux)
1033           update_edge_key (heap, edge);
1034       }
1035 }
1036
1037 /* Recompute HEAP nodes for each uninlined call in NODE.
1038    This is used when we know that edge badnesses are going only to increase
1039    (we introduced new call site) and thus all we need is to insert newly
1040    created edges into heap.  */
1041
1042 static void
1043 update_callee_keys (fibheap_t heap, struct cgraph_node *node,
1044                     bitmap updated_nodes)
1045 {
1046   struct cgraph_edge *e = node->callees;
1047
1048   if (!e)
1049     return;
1050   while (true)
1051     if (!e->inline_failed && e->callee->callees)
1052       e = e->callee->callees;
1053     else
1054       {
1055         enum availability avail;
1056         struct cgraph_node *callee;
1057         /* We do not reset callee growth cache here.  Since we added a new call,
1058            growth chould have just increased and consequentely badness metric
1059            don't need updating.  */
1060         if (e->inline_failed
1061             && (callee = cgraph_function_or_thunk_node (e->callee, &avail))
1062             && inline_summary (callee)->inlinable
1063             && cgraph_function_body_availability (callee) >= AVAIL_AVAILABLE
1064             && !bitmap_bit_p (updated_nodes, callee->uid))
1065           {
1066             if (can_inline_edge_p (e, false)
1067                 && want_inline_small_function_p (e, false))
1068               update_edge_key (heap, e);
1069             else if (e->aux)
1070               {
1071                 report_inline_failed_reason (e);
1072                 fibheap_delete_node (heap, (fibnode_t) e->aux);
1073                 e->aux = NULL;
1074               }
1075           }
1076         if (e->next_callee)
1077           e = e->next_callee;
1078         else
1079           {
1080             do
1081               {
1082                 if (e->caller == node)
1083                   return;
1084                 e = e->caller->callers;
1085               }
1086             while (!e->next_callee);
1087             e = e->next_callee;
1088           }
1089       }
1090 }
1091
1092 /* Recompute heap nodes for each of caller edges of each of callees.
1093    Walk recursively into all inline clones.  */
1094
1095 static void
1096 update_all_callee_keys (fibheap_t heap, struct cgraph_node *node,
1097                         bitmap updated_nodes)
1098 {
1099   struct cgraph_edge *e = node->callees;
1100   if (!e)
1101     return;
1102   while (true)
1103     if (!e->inline_failed && e->callee->callees)
1104       e = e->callee->callees;
1105     else
1106       {
1107         struct cgraph_node *callee = cgraph_function_or_thunk_node (e->callee,
1108                                                                     NULL);
1109
1110         /* We inlined and thus callees might have different number of calls.
1111            Reset their caches  */
1112         reset_node_growth_cache (callee);
1113         if (e->inline_failed)
1114           update_caller_keys (heap, callee, updated_nodes, e);
1115         if (e->next_callee)
1116           e = e->next_callee;
1117         else
1118           {
1119             do
1120               {
1121                 if (e->caller == node)
1122                   return;
1123                 e = e->caller->callers;
1124               }
1125             while (!e->next_callee);
1126             e = e->next_callee;
1127           }
1128       }
1129 }
1130
1131 /* Enqueue all recursive calls from NODE into priority queue depending on
1132    how likely we want to recursively inline the call.  */
1133
1134 static void
1135 lookup_recursive_calls (struct cgraph_node *node, struct cgraph_node *where,
1136                         fibheap_t heap)
1137 {
1138   struct cgraph_edge *e;
1139   enum availability avail;
1140
1141   for (e = where->callees; e; e = e->next_callee)
1142     if (e->callee == node
1143         || (cgraph_function_or_thunk_node (e->callee, &avail) == node
1144             && avail > AVAIL_OVERWRITABLE))
1145       {
1146         /* When profile feedback is available, prioritize by expected number
1147            of calls.  */
1148         fibheap_insert (heap,
1149                         !max_count ? -e->frequency
1150                         : -(e->count / ((max_count + (1<<24) - 1) / (1<<24))),
1151                         e);
1152       }
1153   for (e = where->callees; e; e = e->next_callee)
1154     if (!e->inline_failed)
1155       lookup_recursive_calls (node, e->callee, heap);
1156 }
1157
1158 /* Decide on recursive inlining: in the case function has recursive calls,
1159    inline until body size reaches given argument.  If any new indirect edges
1160    are discovered in the process, add them to *NEW_EDGES, unless NEW_EDGES
1161    is NULL.  */
1162
1163 static bool
1164 recursive_inlining (struct cgraph_edge *edge,
1165                     VEC (cgraph_edge_p, heap) **new_edges)
1166 {
1167   int limit = PARAM_VALUE (PARAM_MAX_INLINE_INSNS_RECURSIVE_AUTO);
1168   fibheap_t heap;
1169   struct cgraph_node *node;
1170   struct cgraph_edge *e;
1171   struct cgraph_node *master_clone = NULL, *next;
1172   int depth = 0;
1173   int n = 0;
1174
1175   node = edge->caller;
1176   if (node->global.inlined_to)
1177     node = node->global.inlined_to;
1178
1179   if (DECL_DECLARED_INLINE_P (node->decl))
1180     limit = PARAM_VALUE (PARAM_MAX_INLINE_INSNS_RECURSIVE);
1181
1182   /* Make sure that function is small enough to be considered for inlining.  */
1183   if (estimate_size_after_inlining (node, edge)  >= limit)
1184     return false;
1185   heap = fibheap_new ();
1186   lookup_recursive_calls (node, node, heap);
1187   if (fibheap_empty (heap))
1188     {
1189       fibheap_delete (heap);
1190       return false;
1191     }
1192
1193   if (dump_file)
1194     fprintf (dump_file,
1195              "  Performing recursive inlining on %s\n",
1196              cgraph_node_name (node));
1197
1198   /* Do the inlining and update list of recursive call during process.  */
1199   while (!fibheap_empty (heap))
1200     {
1201       struct cgraph_edge *curr
1202         = (struct cgraph_edge *) fibheap_extract_min (heap);
1203       struct cgraph_node *cnode;
1204
1205       if (estimate_size_after_inlining (node, curr) > limit)
1206         break;
1207
1208       if (!can_inline_edge_p (curr, true))
1209         continue;
1210
1211       depth = 1;
1212       for (cnode = curr->caller;
1213            cnode->global.inlined_to; cnode = cnode->callers->caller)
1214         if (node->decl
1215             == cgraph_function_or_thunk_node (curr->callee, NULL)->decl)
1216           depth++;
1217
1218       if (!want_inline_self_recursive_call_p (curr, node, false, depth))
1219         continue;
1220
1221       if (dump_file)
1222         {
1223           fprintf (dump_file,
1224                    "   Inlining call of depth %i", depth);
1225           if (node->count)
1226             {
1227               fprintf (dump_file, " called approx. %.2f times per call",
1228                        (double)curr->count / node->count);
1229             }
1230           fprintf (dump_file, "\n");
1231         }
1232       if (!master_clone)
1233         {
1234           /* We need original clone to copy around.  */
1235           master_clone = cgraph_clone_node (node, node->decl,
1236                                             node->count, CGRAPH_FREQ_BASE,
1237                                             false, NULL, true);
1238           for (e = master_clone->callees; e; e = e->next_callee)
1239             if (!e->inline_failed)
1240               clone_inlined_nodes (e, true, false, NULL);
1241         }
1242
1243       cgraph_redirect_edge_callee (curr, master_clone);
1244       inline_call (curr, false, new_edges, &overall_size);
1245       lookup_recursive_calls (node, curr->callee, heap);
1246       n++;
1247     }
1248
1249   if (!fibheap_empty (heap) && dump_file)
1250     fprintf (dump_file, "    Recursive inlining growth limit met.\n");
1251   fibheap_delete (heap);
1252
1253   if (!master_clone)
1254     return false;
1255
1256   if (dump_file)
1257     fprintf (dump_file,
1258              "\n   Inlined %i times, "
1259              "body grown from size %i to %i, time %i to %i\n", n,
1260              inline_summary (master_clone)->size, inline_summary (node)->size,
1261              inline_summary (master_clone)->time, inline_summary (node)->time);
1262
1263   /* Remove master clone we used for inlining.  We rely that clones inlined
1264      into master clone gets queued just before master clone so we don't
1265      need recursion.  */
1266   for (node = cgraph_nodes; node != master_clone;
1267        node = next)
1268     {
1269       next = node->next;
1270       if (node->global.inlined_to == master_clone)
1271         cgraph_remove_node (node);
1272     }
1273   cgraph_remove_node (master_clone);
1274   return true;
1275 }
1276
1277
1278 /* Given whole compilation unit estimate of INSNS, compute how large we can
1279    allow the unit to grow.  */
1280
1281 static int
1282 compute_max_insns (int insns)
1283 {
1284   int max_insns = insns;
1285   if (max_insns < PARAM_VALUE (PARAM_LARGE_UNIT_INSNS))
1286     max_insns = PARAM_VALUE (PARAM_LARGE_UNIT_INSNS);
1287
1288   return ((HOST_WIDEST_INT) max_insns
1289           * (100 + PARAM_VALUE (PARAM_INLINE_UNIT_GROWTH)) / 100);
1290 }
1291
1292
1293 /* Compute badness of all edges in NEW_EDGES and add them to the HEAP.  */
1294
1295 static void
1296 add_new_edges_to_heap (fibheap_t heap, VEC (cgraph_edge_p, heap) *new_edges)
1297 {
1298   while (VEC_length (cgraph_edge_p, new_edges) > 0)
1299     {
1300       struct cgraph_edge *edge = VEC_pop (cgraph_edge_p, new_edges);
1301
1302       gcc_assert (!edge->aux);
1303       if (edge->inline_failed
1304           && can_inline_edge_p (edge, true)
1305           && want_inline_small_function_p (edge, true))
1306         edge->aux = fibheap_insert (heap, edge_badness (edge, false), edge);
1307     }
1308 }
1309
1310
1311 /* We use greedy algorithm for inlining of small functions:
1312    All inline candidates are put into prioritized heap ordered in
1313    increasing badness.
1314
1315    The inlining of small functions is bounded by unit growth parameters.  */
1316
1317 static void
1318 inline_small_functions (void)
1319 {
1320   struct cgraph_node *node;
1321   struct cgraph_edge *edge;
1322   fibheap_t heap = fibheap_new ();
1323   bitmap updated_nodes = BITMAP_ALLOC (NULL);
1324   int min_size, max_size;
1325   VEC (cgraph_edge_p, heap) *new_indirect_edges = NULL;
1326   int initial_size = 0;
1327
1328   if (flag_indirect_inlining)
1329     new_indirect_edges = VEC_alloc (cgraph_edge_p, heap, 8);
1330
1331   if (dump_file)
1332     fprintf (dump_file,
1333              "\nDeciding on inlining of small functions.  Starting with size %i.\n",
1334              initial_size);
1335
1336   /* Compute overall unit size and other global parameters used by badness
1337      metrics.  */
1338
1339   max_count = 0;
1340   initialize_growth_caches ();
1341
1342   FOR_EACH_DEFINED_FUNCTION (node)
1343     if (!node->global.inlined_to)
1344       {
1345         if (cgraph_function_with_gimple_body_p (node)
1346             || node->thunk.thunk_p)
1347           {
1348             struct inline_summary *info = inline_summary (node);
1349
1350             if (!DECL_EXTERNAL (node->decl))
1351               initial_size += info->size;
1352           }
1353
1354         for (edge = node->callers; edge; edge = edge->next_caller)
1355           if (max_count < edge->count)
1356             max_count = edge->count;
1357       }
1358
1359   overall_size = initial_size;
1360   max_size = compute_max_insns (overall_size);
1361   min_size = overall_size;
1362
1363   /* Populate the heeap with all edges we might inline.  */
1364
1365   FOR_EACH_DEFINED_FUNCTION (node)
1366     if (!node->global.inlined_to)
1367       {
1368         if (dump_file)
1369           fprintf (dump_file, "Enqueueing calls of %s/%i.\n",
1370                    cgraph_node_name (node), node->uid);
1371
1372         for (edge = node->callers; edge; edge = edge->next_caller)
1373           if (edge->inline_failed
1374               && can_inline_edge_p (edge, true)
1375               && want_inline_small_function_p (edge, true)
1376               && edge->inline_failed)
1377             {
1378               gcc_assert (!edge->aux);
1379               update_edge_key (heap, edge);
1380             }
1381       }
1382
1383   gcc_assert (in_lto_p
1384               || !max_count
1385               || (profile_info && flag_branch_probabilities));
1386
1387   while (!fibheap_empty (heap))
1388     {
1389       int old_size = overall_size;
1390       struct cgraph_node *where, *callee;
1391       int badness = fibheap_min_key (heap);
1392       int current_badness;
1393       int cached_badness;
1394       int growth;
1395
1396       edge = (struct cgraph_edge *) fibheap_extract_min (heap);
1397       gcc_assert (edge->aux);
1398       edge->aux = NULL;
1399       if (!edge->inline_failed)
1400         continue;
1401
1402       /* Be sure that caches are maintained consistent.
1403          We can not make this ENABLE_CHECKING only because it cause differnt
1404          updates of the fibheap queue.  */
1405       cached_badness = edge_badness (edge, false);
1406       reset_edge_growth_cache (edge);
1407       reset_node_growth_cache (edge->callee);
1408
1409       /* When updating the edge costs, we only decrease badness in the keys.
1410          Increases of badness are handled lazilly; when we see key with out
1411          of date value on it, we re-insert it now.  */
1412       current_badness = edge_badness (edge, false);
1413       gcc_assert (cached_badness == current_badness);
1414       gcc_assert (current_badness >= badness);
1415       if (current_badness != badness)
1416         {
1417           edge->aux = fibheap_insert (heap, current_badness, edge);
1418           continue;
1419         }
1420
1421       if (!can_inline_edge_p (edge, true))
1422         continue;
1423
1424       callee = cgraph_function_or_thunk_node (edge->callee, NULL);
1425       growth = estimate_edge_growth (edge);
1426       if (dump_file)
1427         {
1428           fprintf (dump_file,
1429                    "\nConsidering %s with %i size\n",
1430                    cgraph_node_name (callee),
1431                    inline_summary (callee)->size);
1432           fprintf (dump_file,
1433                    " to be inlined into %s in %s:%i\n"
1434                    " Estimated growth after inlined into all is %+i insns.\n"
1435                    " Estimated badness is %i, frequency %.2f.\n",
1436                    cgraph_node_name (edge->caller),
1437                    flag_wpa ? "unknown"
1438                    : gimple_filename ((const_gimple) edge->call_stmt),
1439                    flag_wpa ? -1
1440                    : gimple_lineno ((const_gimple) edge->call_stmt),
1441                    estimate_growth (callee),
1442                    badness,
1443                    edge->frequency / (double)CGRAPH_FREQ_BASE);
1444           if (edge->count)
1445             fprintf (dump_file," Called "HOST_WIDEST_INT_PRINT_DEC"x\n",
1446                      edge->count);
1447           if (dump_flags & TDF_DETAILS)
1448             edge_badness (edge, true);
1449         }
1450
1451       if (overall_size + growth > max_size
1452           && !DECL_DISREGARD_INLINE_LIMITS (callee->decl))
1453         {
1454           edge->inline_failed = CIF_INLINE_UNIT_GROWTH_LIMIT;
1455           report_inline_failed_reason (edge);
1456           continue;
1457         }
1458
1459       if (!want_inline_small_function_p (edge, true))
1460         continue;
1461
1462       /* Heuristics for inlining small functions works poorly for
1463          recursive calls where we do efect similar to loop unrolling.
1464          When inliing such edge seems profitable, leave decision on
1465          specific inliner.  */
1466       if (cgraph_edge_recursive_p (edge))
1467         {
1468           where = edge->caller;
1469           if (where->global.inlined_to)
1470             where = where->global.inlined_to;
1471           if (!recursive_inlining (edge,
1472                                    flag_indirect_inlining
1473                                    ? &new_indirect_edges : NULL))
1474             {
1475               edge->inline_failed = CIF_RECURSIVE_INLINING;
1476               continue;
1477             }
1478           reset_edge_caches (where);
1479           /* Recursive inliner inlines all recursive calls of the function
1480              at once. Consequently we need to update all callee keys.  */
1481           if (flag_indirect_inlining)
1482             add_new_edges_to_heap (heap, new_indirect_edges);
1483           update_all_callee_keys (heap, where, updated_nodes);
1484         }
1485       else
1486         {
1487           struct cgraph_node *outer_node = NULL;
1488           int depth = 0;
1489
1490           /* Consider the case where self recursive function A is inlined into B.
1491              This is desired optimization in some cases, since it leads to effect
1492              similar of loop peeling and we might completely optimize out the
1493              recursive call.  However we must be extra selective.  */
1494
1495           where = edge->caller;
1496           while (where->global.inlined_to)
1497             {
1498               if (where->decl == callee->decl)
1499                 outer_node = where, depth++;
1500               where = where->callers->caller;
1501             }
1502           if (outer_node
1503               && !want_inline_self_recursive_call_p (edge, outer_node,
1504                                                      true, depth))
1505             {
1506               edge->inline_failed
1507                 = (DECL_DISREGARD_INLINE_LIMITS (edge->callee->decl)
1508                    ? CIF_RECURSIVE_INLINING : CIF_UNSPECIFIED);
1509               continue;
1510             }
1511           else if (depth && dump_file)
1512             fprintf (dump_file, " Peeling recursion with depth %i\n", depth);
1513
1514           gcc_checking_assert (!callee->global.inlined_to);
1515           inline_call (edge, true, &new_indirect_edges, &overall_size);
1516           if (flag_indirect_inlining)
1517             add_new_edges_to_heap (heap, new_indirect_edges);
1518
1519           reset_edge_caches (edge->callee);
1520           reset_node_growth_cache (callee);
1521
1522           /* We inlined last offline copy to the body.  This might lead
1523              to callees of function having fewer call sites and thus they
1524              may need updating.
1525
1526              FIXME: the callee size could also shrink because more information
1527              is propagated from caller.  We don't track when this happen and
1528              thus we need to recompute everything all the time.  Once this is
1529              solved, "|| 1" should go away.  */
1530           if (callee->global.inlined_to || 1)
1531             update_all_callee_keys (heap, callee, updated_nodes);
1532           else
1533             update_callee_keys (heap, edge->callee, updated_nodes);
1534         }
1535       where = edge->caller;
1536       if (where->global.inlined_to)
1537         where = where->global.inlined_to;
1538
1539       /* Our profitability metric can depend on local properties
1540          such as number of inlinable calls and size of the function body.
1541          After inlining these properties might change for the function we
1542          inlined into (since it's body size changed) and for the functions
1543          called by function we inlined (since number of it inlinable callers
1544          might change).  */
1545       update_caller_keys (heap, where, updated_nodes, NULL);
1546
1547       /* We removed one call of the function we just inlined.  If offline
1548          copy is still needed, be sure to update the keys.  */
1549       if (callee != where && !callee->global.inlined_to)
1550         update_caller_keys (heap, callee, updated_nodes, NULL);
1551       bitmap_clear (updated_nodes);
1552
1553       if (dump_file)
1554         {
1555           fprintf (dump_file,
1556                    " Inlined into %s which now has time %i and size %i,"
1557                    "net change of %+i.\n",
1558                    cgraph_node_name (edge->caller),
1559                    inline_summary (edge->caller)->time,
1560                    inline_summary (edge->caller)->size,
1561                    overall_size - old_size);
1562         }
1563       if (min_size > overall_size)
1564         {
1565           min_size = overall_size;
1566           max_size = compute_max_insns (min_size);
1567
1568           if (dump_file)
1569             fprintf (dump_file, "New minimal size reached: %i\n", min_size);
1570         }
1571     }
1572
1573   free_growth_caches ();
1574   if (new_indirect_edges)
1575     VEC_free (cgraph_edge_p, heap, new_indirect_edges);
1576   fibheap_delete (heap);
1577   if (dump_file)
1578     fprintf (dump_file,
1579              "Unit growth for small function inlining: %i->%i (%i%%)\n",
1580              initial_size, overall_size,
1581              initial_size ? overall_size * 100 / (initial_size) - 100: 0);
1582   BITMAP_FREE (updated_nodes);
1583 }
1584
1585 /* Flatten NODE.  Performed both during early inlining and
1586    at IPA inlining time.  */
1587
1588 static void
1589 flatten_function (struct cgraph_node *node, bool early)
1590 {
1591   struct cgraph_edge *e;
1592
1593   /* We shouldn't be called recursively when we are being processed.  */
1594   gcc_assert (node->aux == NULL);
1595
1596   node->aux = (void *) node;
1597
1598   for (e = node->callees; e; e = e->next_callee)
1599     {
1600       struct cgraph_node *orig_callee;
1601       struct cgraph_node *callee = cgraph_function_or_thunk_node (e->callee, NULL);
1602
1603       /* We've hit cycle?  It is time to give up.  */
1604       if (callee->aux)
1605         {
1606           if (dump_file)
1607             fprintf (dump_file,
1608                      "Not inlining %s into %s to avoid cycle.\n",
1609                      cgraph_node_name (callee),
1610                      cgraph_node_name (e->caller));
1611           e->inline_failed = CIF_RECURSIVE_INLINING;
1612           continue;
1613         }
1614
1615       /* When the edge is already inlined, we just need to recurse into
1616          it in order to fully flatten the leaves.  */
1617       if (!e->inline_failed)
1618         {
1619           flatten_function (callee, early);
1620           continue;
1621         }
1622
1623       /* Flatten attribute needs to be processed during late inlining. For
1624          extra code quality we however do flattening during early optimization,
1625          too.  */
1626       if (!early
1627           ? !can_inline_edge_p (e, true)
1628           : !can_early_inline_edge_p (e))
1629         continue;
1630
1631       if (cgraph_edge_recursive_p (e))
1632         {
1633           if (dump_file)
1634             fprintf (dump_file, "Not inlining: recursive call.\n");
1635           continue;
1636         }
1637
1638       if (gimple_in_ssa_p (DECL_STRUCT_FUNCTION (node->decl))
1639           != gimple_in_ssa_p (DECL_STRUCT_FUNCTION (callee->decl)))
1640         {
1641           if (dump_file)
1642             fprintf (dump_file, "Not inlining: SSA form does not match.\n");
1643           continue;
1644         }
1645
1646       /* Inline the edge and flatten the inline clone.  Avoid
1647          recursing through the original node if the node was cloned.  */
1648       if (dump_file)
1649         fprintf (dump_file, " Inlining %s into %s.\n",
1650                  cgraph_node_name (callee),
1651                  cgraph_node_name (e->caller));
1652       orig_callee = callee;
1653       inline_call (e, true, NULL, NULL);
1654       if (e->callee != orig_callee)
1655         orig_callee->aux = (void *) node;
1656       flatten_function (e->callee, early);
1657       if (e->callee != orig_callee)
1658         orig_callee->aux = NULL;
1659     }
1660
1661   node->aux = NULL;
1662 }
1663
1664 /* Decide on the inlining.  We do so in the topological order to avoid
1665    expenses on updating data structures.  */
1666
1667 static unsigned int
1668 ipa_inline (void)
1669 {
1670   struct cgraph_node *node;
1671   int nnodes;
1672   struct cgraph_node **order =
1673     XCNEWVEC (struct cgraph_node *, cgraph_n_nodes);
1674   int i;
1675
1676   if (in_lto_p && optimize)
1677     ipa_update_after_lto_read ();
1678
1679   if (dump_file)
1680     dump_inline_summaries (dump_file);
1681
1682   nnodes = ipa_reverse_postorder (order);
1683
1684   for (node = cgraph_nodes; node; node = node->next)
1685     node->aux = 0;
1686
1687   if (dump_file)
1688     fprintf (dump_file, "\nFlattening functions:\n");
1689
1690   /* In the first pass handle functions to be flattened.  Do this with
1691      a priority so none of our later choices will make this impossible.  */
1692   for (i = nnodes - 1; i >= 0; i--)
1693     {
1694       node = order[i];
1695
1696       /* Handle nodes to be flattened.
1697          Ideally when processing callees we stop inlining at the
1698          entry of cycles, possibly cloning that entry point and
1699          try to flatten itself turning it into a self-recursive
1700          function.  */
1701       if (lookup_attribute ("flatten",
1702                             DECL_ATTRIBUTES (node->decl)) != NULL)
1703         {
1704           if (dump_file)
1705             fprintf (dump_file,
1706                      "Flattening %s\n", cgraph_node_name (node));
1707           flatten_function (node, false);
1708         }
1709     }
1710
1711   inline_small_functions ();
1712   cgraph_remove_unreachable_nodes (true, dump_file);
1713   free (order);
1714
1715   /* We already perform some inlining of functions called once during
1716      inlining small functions above.  After unreachable nodes are removed,
1717      we still might do a quick check that nothing new is found.  */
1718   if (flag_inline_functions_called_once)
1719     {
1720       int cold;
1721       if (dump_file)
1722         fprintf (dump_file, "\nDeciding on functions called once:\n");
1723
1724       /* Inlining one function called once has good chance of preventing
1725          inlining other function into the same callee.  Ideally we should
1726          work in priority order, but probably inlining hot functions first
1727          is good cut without the extra pain of maintaining the queue.
1728
1729          ??? this is not really fitting the bill perfectly: inlining function
1730          into callee often leads to better optimization of callee due to
1731          increased context for optimization.
1732          For example if main() function calls a function that outputs help
1733          and then function that does the main optmization, we should inline
1734          the second with priority even if both calls are cold by themselves.
1735
1736          We probably want to implement new predicate replacing our use of
1737          maybe_hot_edge interpreted as maybe_hot_edge || callee is known
1738          to be hot.  */
1739       for (cold = 0; cold <= 1; cold ++)
1740         {
1741           for (node = cgraph_nodes; node; node = node->next)
1742             {
1743               if (want_inline_function_called_once_p (node)
1744                   && (cold
1745                       || cgraph_maybe_hot_edge_p (node->callers)))
1746                 {
1747                   struct cgraph_node *caller = node->callers->caller;
1748
1749                   if (dump_file)
1750                     {
1751                       fprintf (dump_file,
1752                                "\nInlining %s size %i.\n",
1753                                cgraph_node_name (node), inline_summary (node)->size);
1754                       fprintf (dump_file,
1755                                " Called once from %s %i insns.\n",
1756                                cgraph_node_name (node->callers->caller),
1757                                inline_summary (node->callers->caller)->size);
1758                     }
1759
1760                   inline_call (node->callers, true, NULL, NULL);
1761                   if (dump_file)
1762                     fprintf (dump_file,
1763                              " Inlined into %s which now has %i size\n",
1764                              cgraph_node_name (caller),
1765                              inline_summary (caller)->size);
1766                 }
1767             }
1768         }
1769     }
1770
1771   /* Free ipa-prop structures if they are no longer needed.  */
1772   if (optimize)
1773     ipa_free_all_structures_after_iinln ();
1774
1775   if (dump_file)
1776     fprintf (dump_file,
1777              "\nInlined %i calls, eliminated %i functions\n\n",
1778              ncalls_inlined, nfunctions_inlined);
1779
1780   if (dump_file)
1781     dump_inline_summaries (dump_file);
1782   /* In WPA we use inline summaries for partitioning process.  */
1783   if (!flag_wpa)
1784     inline_free_summary ();
1785   return 0;
1786 }
1787
1788 /* Inline always-inline function calls in NODE.  */
1789
1790 static bool
1791 inline_always_inline_functions (struct cgraph_node *node)
1792 {
1793   struct cgraph_edge *e;
1794   bool inlined = false;
1795
1796   for (e = node->callees; e; e = e->next_callee)
1797     {
1798       struct cgraph_node *callee = cgraph_function_or_thunk_node (e->callee, NULL);
1799       if (!DECL_DISREGARD_INLINE_LIMITS (callee->decl))
1800         continue;
1801
1802       if (cgraph_edge_recursive_p (e))
1803         {
1804           if (dump_file)
1805             fprintf (dump_file, "  Not inlining recursive call to %s.\n",
1806                      cgraph_node_name (e->callee));
1807           e->inline_failed = CIF_RECURSIVE_INLINING;
1808           continue;
1809         }
1810
1811       if (!can_early_inline_edge_p (e))
1812         continue;
1813
1814       if (dump_file)
1815         fprintf (dump_file, "  Inlining %s into %s (always_inline).\n",
1816                  cgraph_node_name (e->callee),
1817                  cgraph_node_name (e->caller));
1818       inline_call (e, true, NULL, NULL);
1819       inlined = true;
1820     }
1821
1822   return inlined;
1823 }
1824
1825 /* Decide on the inlining.  We do so in the topological order to avoid
1826    expenses on updating data structures.  */
1827
1828 static bool
1829 early_inline_small_functions (struct cgraph_node *node)
1830 {
1831   struct cgraph_edge *e;
1832   bool inlined = false;
1833
1834   for (e = node->callees; e; e = e->next_callee)
1835     {
1836       struct cgraph_node *callee = cgraph_function_or_thunk_node (e->callee, NULL);
1837       if (!inline_summary (callee)->inlinable
1838           || !e->inline_failed)
1839         continue;
1840
1841       /* Do not consider functions not declared inline.  */
1842       if (!DECL_DECLARED_INLINE_P (callee->decl)
1843           && !flag_inline_small_functions
1844           && !flag_inline_functions)
1845         continue;
1846
1847       if (dump_file)
1848         fprintf (dump_file, "Considering inline candidate %s.\n",
1849                  cgraph_node_name (callee));
1850
1851       if (!can_early_inline_edge_p (e))
1852         continue;
1853
1854       if (cgraph_edge_recursive_p (e))
1855         {
1856           if (dump_file)
1857             fprintf (dump_file, "  Not inlining: recursive call.\n");
1858           continue;
1859         }
1860
1861       if (!want_early_inline_function_p (e))
1862         continue;
1863
1864       if (dump_file)
1865         fprintf (dump_file, " Inlining %s into %s.\n",
1866                  cgraph_node_name (callee),
1867                  cgraph_node_name (e->caller));
1868       inline_call (e, true, NULL, NULL);
1869       inlined = true;
1870     }
1871
1872   return inlined;
1873 }
1874
1875 /* Do inlining of small functions.  Doing so early helps profiling and other
1876    passes to be somewhat more effective and avoids some code duplication in
1877    later real inlining pass for testcases with very many function calls.  */
1878 static unsigned int
1879 early_inliner (void)
1880 {
1881   struct cgraph_node *node = cgraph_get_node (current_function_decl);
1882   struct cgraph_edge *edge;
1883   unsigned int todo = 0;
1884   int iterations = 0;
1885   bool inlined = false;
1886
1887   if (seen_error ())
1888     return 0;
1889
1890   /* Do nothing if datastructures for ipa-inliner are already computed.  This
1891      happens when some pass decides to construct new function and
1892      cgraph_add_new_function calls lowering passes and early optimization on
1893      it.  This may confuse ourself when early inliner decide to inline call to
1894      function clone, because function clones don't have parameter list in
1895      ipa-prop matching their signature.  */
1896   if (ipa_node_params_vector)
1897     return 0;
1898
1899 #ifdef ENABLE_CHECKING
1900   verify_cgraph_node (node);
1901 #endif
1902
1903   /* Even when not optimizing or not inlining inline always-inline
1904      functions.  */
1905   inlined = inline_always_inline_functions (node);
1906
1907   if (!optimize
1908       || flag_no_inline
1909       || !flag_early_inlining
1910       /* Never inline regular functions into always-inline functions
1911          during incremental inlining.  This sucks as functions calling
1912          always inline functions will get less optimized, but at the
1913          same time inlining of functions calling always inline
1914          function into an always inline function might introduce
1915          cycles of edges to be always inlined in the callgraph.
1916
1917          We might want to be smarter and just avoid this type of inlining.  */
1918       || DECL_DISREGARD_INLINE_LIMITS (node->decl))
1919     ;
1920   else if (lookup_attribute ("flatten",
1921                              DECL_ATTRIBUTES (node->decl)) != NULL)
1922     {
1923       /* When the function is marked to be flattened, recursively inline
1924          all calls in it.  */
1925       if (dump_file)
1926         fprintf (dump_file,
1927                  "Flattening %s\n", cgraph_node_name (node));
1928       flatten_function (node, true);
1929       inlined = true;
1930     }
1931   else
1932     {
1933       /* We iterate incremental inlining to get trivial cases of indirect
1934          inlining.  */
1935       while (iterations < PARAM_VALUE (PARAM_EARLY_INLINER_MAX_ITERATIONS)
1936              && early_inline_small_functions (node))
1937         {
1938           timevar_push (TV_INTEGRATION);
1939           todo |= optimize_inline_calls (current_function_decl);
1940
1941           /* Technically we ought to recompute inline parameters so the new
1942              iteration of early inliner works as expected.  We however have
1943              values approximately right and thus we only need to update edge
1944              info that might be cleared out for newly discovered edges.  */
1945           for (edge = node->callees; edge; edge = edge->next_callee)
1946             {
1947               struct inline_edge_summary *es = inline_edge_summary (edge);
1948               es->call_stmt_size
1949                 = estimate_num_insns (edge->call_stmt, &eni_size_weights);
1950               es->call_stmt_time
1951                 = estimate_num_insns (edge->call_stmt, &eni_time_weights);
1952               edge->call_stmt_cannot_inline_p
1953                 = gimple_call_cannot_inline_p (edge->call_stmt);
1954             }
1955           timevar_pop (TV_INTEGRATION);
1956           iterations++;
1957           inlined = false;
1958         }
1959       if (dump_file)
1960         fprintf (dump_file, "Iterations: %i\n", iterations);
1961     }
1962
1963   if (inlined)
1964     {
1965       timevar_push (TV_INTEGRATION);
1966       todo |= optimize_inline_calls (current_function_decl);
1967       timevar_pop (TV_INTEGRATION);
1968     }
1969
1970   cfun->always_inline_functions_inlined = true;
1971
1972   return todo;
1973 }
1974
1975 struct gimple_opt_pass pass_early_inline =
1976 {
1977  {
1978   GIMPLE_PASS,
1979   "einline",                            /* name */
1980   NULL,                                 /* gate */
1981   early_inliner,                        /* execute */
1982   NULL,                                 /* sub */
1983   NULL,                                 /* next */
1984   0,                                    /* static_pass_number */
1985   TV_INLINE_HEURISTICS,                 /* tv_id */
1986   PROP_ssa,                             /* properties_required */
1987   0,                                    /* properties_provided */
1988   0,                                    /* properties_destroyed */
1989   0,                                    /* todo_flags_start */
1990   0                                     /* todo_flags_finish */
1991  }
1992 };
1993
1994
1995 /* When to run IPA inlining.  Inlining of always-inline functions
1996    happens during early inlining.
1997
1998    Enable inlining unconditoinally at -flto.  We need size estimates to
1999    drive partitioning.  */
2000
2001 static bool
2002 gate_ipa_inline (void)
2003 {
2004   return optimize || flag_lto || flag_wpa;
2005 }
2006
2007 struct ipa_opt_pass_d pass_ipa_inline =
2008 {
2009  {
2010   IPA_PASS,
2011   "inline",                             /* name */
2012   gate_ipa_inline,                      /* gate */
2013   ipa_inline,                           /* execute */
2014   NULL,                                 /* sub */
2015   NULL,                                 /* next */
2016   0,                                    /* static_pass_number */
2017   TV_INLINE_HEURISTICS,                 /* tv_id */
2018   0,                                    /* properties_required */
2019   0,                                    /* properties_provided */
2020   0,                                    /* properties_destroyed */
2021   TODO_remove_functions,                /* todo_flags_finish */
2022   TODO_dump_cgraph
2023   | TODO_remove_functions | TODO_ggc_collect    /* todo_flags_finish */
2024  },
2025  inline_generate_summary,               /* generate_summary */
2026  inline_write_summary,                  /* write_summary */
2027  inline_read_summary,                   /* read_summary */
2028  NULL,                                  /* write_optimization_summary */
2029  NULL,                                  /* read_optimization_summary */
2030  NULL,                                  /* stmt_fixup */
2031  0,                                     /* TODOs */
2032  inline_transform,                      /* function_transform */
2033  NULL,                                  /* variable_transform */
2034 };