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                xstrdup (cgraph_node_name (e->caller)), e->caller->uid,
 224                xstrdup (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   /* TM pure functions should not be inlined into non-TM_pure
 288      functions.  */
 289   else if (is_tm_pure (callee->decl)
 290            && !is_tm_pure (e->caller->decl))
 291     {
 292       e->inline_failed = CIF_UNSPECIFIED;
 293       inlinable = false;
 294     }
 295   /* Don't inline if the callee can throw non-call exceptions but the
 296      caller cannot.
 297      FIXME: this is obviously wrong for LTO where STRUCT_FUNCTION is missing.
 298      Move the flag into cgraph node or mirror it in the inline summary.  */
 299   else if (callee_cfun && callee_cfun->can_throw_non_call_exceptions
 300            && !(caller_cfun && caller_cfun->can_throw_non_call_exceptions))
 301     {
 302       e->inline_failed = CIF_NON_CALL_EXCEPTIONS;
 303       inlinable = false;
 304     }
 305   /* Check compatibility of target optimization options.  */
 306   else if (!targetm.target_option.can_inline_p (e->caller->decl,
 307                                                 callee->decl))
 308     {
 309       e->inline_failed = CIF_TARGET_OPTION_MISMATCH;
 310       inlinable = false;
 311     }
 312   /* Check if caller growth allows the inlining.  */
 313   else if (!DECL_DISREGARD_INLINE_LIMITS (callee->decl)
 314            && !lookup_attribute ("flatten",
 315                                  DECL_ATTRIBUTES
 316                                    (e->caller->global.inlined_to
 317                                     ? e->caller->global.inlined_to->decl
 318                                     : e->caller->decl))
 319            && !caller_growth_limits (e))
 320     inlinable = false;
 321   /* Don't inline a function with a higher optimization level than the
 322      caller.  FIXME: this is really just tip of iceberg of handling
 323      optimization attribute.  */
 324   else if (caller_tree != callee_tree)
 325     {
 326       struct cl_optimization *caller_opt
 327         = TREE_OPTIMIZATION ((caller_tree)
 328                              ? caller_tree
 329                              : optimization_default_node);
 330
 331       struct cl_optimization *callee_opt
 332         = TREE_OPTIMIZATION ((callee_tree)
 333                              ? callee_tree
 334                              : optimization_default_node);
 335
 336       if (((caller_opt->x_optimize > callee_opt->x_optimize)
 337            || (caller_opt->x_optimize_size != callee_opt->x_optimize_size))
 338           /* gcc.dg/pr43564.c.  Look at forced inline even in -O0.  */
 339           && !DECL_DISREGARD_INLINE_LIMITS (e->callee->decl))
 340         {
 341           e->inline_failed = CIF_OPTIMIZATION_MISMATCH;
 342           inlinable = false;
 343         }
 344     }
 345
 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                      xstrdup (cgraph_node_name (e->caller)), e->caller->uid,
 427                      xstrdup (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                      xstrdup (cgraph_node_name (e->caller)), e->caller->uid,
 438                      xstrdup (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                      xstrdup (cgraph_node_name (e->caller)), e->caller->uid,
 448                      xstrdup (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       /* Before giving up based on fact that caller size will grow, allow
 486          functions that are called few times and eliminating the offline
 487          copy will lead to overall code size reduction.
 488          Not all of these will be handled by subsequent inlining of functions
 489          called once: in particular weak functions are not handled or funcitons
 490          that inline to multiple calls but a lot of bodies is optimized out.
 491          Finally we want to inline earlier to allow inlining of callbacks.
 492
 493          This is slightly wrong on aggressive side:  it is entirely possible
 494          that function is called many times with a context where inlining
 495          reduces code size and few times with a context where inlining increase
 496          code size.  Resoluting growth estimate will be negative even if it
 497          would make more sense to keep offline copy and do not inline into the
 498          call sites that makes the code size grow.
 499
 500          When badness orders the calls in a way that code reducing calls come
 501          first, this situation is not a problem at all: after inlining all
 502          "good" calls, we will realize that keeping the function around is
 503          better.  */
 504       else if (growth <= MAX_INLINE_INSNS_SINGLE
 505                /* Unlike for functions called once, we play unsafe with
 506                   COMDATs.  We can allow that since we know functions
 507                   in consideration are small (and thus risk is small) and
 508                   moreover grow estimates already accounts that COMDAT
 509                   functions may or may not disappear when eliminated from
 510                   current unit. With good probability making aggressive
 511                   choice in all units is going to make overall program
 512                   smaller.
 513
 514                   Consequently we ask cgraph_can_remove_if_no_direct_calls_p
 515                   instead of
 516                   cgraph_will_be_removed_from_program_if_no_direct_calls  */
 517                 && !DECL_EXTERNAL (callee->decl)
 518                 && cgraph_can_remove_if_no_direct_calls_p (callee)
 519                 && estimate_growth (callee) <= 0)
 520         ;
 521       else if (!DECL_DECLARED_INLINE_P (callee->decl)
 522                && !flag_inline_functions)
 523         {
 524           e->inline_failed = CIF_NOT_DECLARED_INLINED;
 525           want_inline = false;
 526         }
 527       else if (!DECL_DECLARED_INLINE_P (callee->decl)
 528                && growth >= MAX_INLINE_INSNS_AUTO)
 529         {
 530           e->inline_failed = CIF_MAX_INLINE_INSNS_AUTO_LIMIT;
 531           want_inline = false;
 532         }
 533       /* If call is cold, do not inline when function body would grow. */
 534       else if (!cgraph_maybe_hot_edge_p (e))
 535         {
 536           e->inline_failed = CIF_UNLIKELY_CALL;
 537           want_inline = false;
 538         }
 539     }
 540   if (!want_inline && report)
 541     report_inline_failed_reason (e);
 542   return want_inline;
 543 }
 544
 545 /* EDGE is self recursive edge.
 546    We hand two cases - when function A is inlining into itself
 547    or when function A is being inlined into another inliner copy of function
 548    A within function B.
 549
 550    In first case OUTER_NODE points to the toplevel copy of A, while
 551    in the second case OUTER_NODE points to the outermost copy of A in B.
 552
 553    In both cases we want to be extra selective since
 554    inlining the call will just introduce new recursive calls to appear.  */
 555
 556 static bool
 557 want_inline_self_recursive_call_p (struct cgraph_edge *edge,
 558                                    struct cgraph_node *outer_node,
 559                                    bool peeling,
 560                                    int depth)
 561 {
 562   char const *reason = NULL;
 563   bool want_inline = true;
 564   int caller_freq = CGRAPH_FREQ_BASE;
 565   int max_depth = PARAM_VALUE (PARAM_MAX_INLINE_RECURSIVE_DEPTH_AUTO);
 566
 567   if (DECL_DECLARED_INLINE_P (edge->caller->decl))
 568     max_depth = PARAM_VALUE (PARAM_MAX_INLINE_RECURSIVE_DEPTH);
 569
 570   if (!cgraph_maybe_hot_edge_p (edge))
 571     {
 572       reason = "recursive call is cold";
 573       want_inline = false;
 574     }
 575   else if (max_count && !outer_node->count)
 576     {
 577       reason = "not executed in profile";
 578       want_inline = false;
 579     }
 580   else if (depth > max_depth)
 581     {
 582       reason = "--param max-inline-recursive-depth exceeded.";
 583       want_inline = false;
 584     }
 585
 586   if (outer_node->global.inlined_to)
 587     caller_freq = outer_node->callers->frequency;
 588
 589   if (!want_inline)
 590     ;
 591   /* Inlining of self recursive function into copy of itself within other function
 592      is transformation similar to loop peeling.
 593
 594      Peeling is profitable if we can inline enough copies to make probability
 595      of actual call to the self recursive function very small.  Be sure that
 596      the probability of recursion is small.
 597
 598      We ensure that the frequency of recursing is at most 1 - (1/max_depth).
 599      This way the expected number of recision is at most max_depth.  */
 600   else if (peeling)
 601     {
 602       int max_prob = CGRAPH_FREQ_BASE - ((CGRAPH_FREQ_BASE + max_depth - 1)
 603                                          / max_depth);
 604       int i;
 605       for (i = 1; i < depth; i++)
 606         max_prob = max_prob * max_prob / CGRAPH_FREQ_BASE;
 607       if (max_count
 608           && (edge->count * CGRAPH_FREQ_BASE / outer_node->count
 609               >= max_prob))
 610         {
 611           reason = "profile of recursive call is too large";
 612           want_inline = false;
 613         }
 614       if (!max_count
 615           && (edge->frequency * CGRAPH_FREQ_BASE / caller_freq
 616               >= max_prob))
 617         {
 618           reason = "frequency of recursive call is too large";
 619           want_inline = false;
 620         }
 621     }
 622   /* Recursive inlining, i.e. equivalent of unrolling, is profitable if recursion
 623      depth is large.  We reduce function call overhead and increase chances that
 624      things fit in hardware return predictor.
 625
 626      Recursive inlining might however increase cost of stack frame setup
 627      actually slowing down functions whose recursion tree is wide rather than
 628      deep.
 629
 630      Deciding reliably on when to do recursive inlining without profile feedback
 631      is tricky.  For now we disable recursive inlining when probability of self
 632      recursion is low.
 633
 634      Recursive inlining of self recursive call within loop also results in large loop
 635      depths that generally optimize badly.  We may want to throttle down inlining
 636      in those cases.  In particular this seems to happen in one of libstdc++ rb tree
 637      methods.  */
 638   else
 639     {
 640       if (max_count
 641           && (edge->count * 100 / outer_node->count
 642               <= PARAM_VALUE (PARAM_MIN_INLINE_RECURSIVE_PROBABILITY)))
 643         {
 644           reason = "profile of recursive call is too small";
 645           want_inline = false;
 646         }
 647       else if (!max_count
 648                && (edge->frequency * 100 / caller_freq
 649                    <= PARAM_VALUE (PARAM_MIN_INLINE_RECURSIVE_PROBABILITY)))
 650         {
 651           reason = "frequency of recursive call is too small";
 652           want_inline = false;
 653         }
 654     }
 655   if (!want_inline && dump_file)
 656     fprintf (dump_file, "   not inlining recursively: %s\n", reason);
 657   return want_inline;
 658 }
 659
 660 /* Return true when NODE has caller other than EDGE.
 661    Worker for cgraph_for_node_and_aliases.  */
 662
 663 static bool
 664 check_caller_edge (struct cgraph_node *node, void *edge)
 665 {
 666   return (node->callers
 667           && node->callers != edge);
 668 }
 669
 670
 671 /* Decide if NODE is called once inlining it would eliminate need
 672    for the offline copy of function.  */
 673
 674 static bool
 675 want_inline_function_called_once_p (struct cgraph_node *node)
 676 {
 677    struct cgraph_node *function = cgraph_function_or_thunk_node (node, NULL);
 678    /* Already inlined?  */
 679    if (function->global.inlined_to)
 680      return false;
 681    /* Zero or more then one callers?  */
 682    if (!node->callers
 683        || node->callers->next_caller)
 684      return false;
 685    /* Maybe other aliases has more direct calls.  */
 686    if (cgraph_for_node_and_aliases (node, check_caller_edge, node->callers, true))
 687      return false;
 688    /* Recursive call makes no sense to inline.  */
 689    if (cgraph_edge_recursive_p (node->callers))
 690      return false;
 691    /* External functions are not really in the unit, so inlining
 692       them when called once would just increase the program size.  */
 693    if (DECL_EXTERNAL (function->decl))
 694      return false;
 695    /* Offline body must be optimized out.  */
 696    if (!cgraph_will_be_removed_from_program_if_no_direct_calls (function))
 697      return false;
 698    if (!can_inline_edge_p (node->callers, true))
 699      return false;
 700    return true;
 701 }
 702
 703
 704 /* Return relative time improvement for inlining EDGE in range
 705    1...2^9.  */
 706
 707 static inline int
 708 relative_time_benefit (struct inline_summary *callee_info,
 709                        struct cgraph_edge *edge,
 710                        int time_growth)
 711 {
 712   int relbenefit;
 713   gcov_type uninlined_call_time;
 714
 715   uninlined_call_time =
 716     ((gcov_type)
 717      (callee_info->time
 718       + inline_edge_summary (edge)->call_stmt_time) * edge->frequency
 719      + CGRAPH_FREQ_BASE / 2) / CGRAPH_FREQ_BASE;
 720   /* Compute relative time benefit, i.e. how much the call becomes faster.
 721      ??? perhaps computing how much the caller+calle together become faster
 722      would lead to more realistic results.  */
 723   if (!uninlined_call_time)
 724     uninlined_call_time = 1;
 725   relbenefit =
 726     (uninlined_call_time - time_growth) * 256 / (uninlined_call_time);
 727   relbenefit = MIN (relbenefit, 512);
 728   relbenefit = MAX (relbenefit, 1);
 729   return relbenefit;
 730 }
 731
 732
 733 /* A cost model driving the inlining heuristics in a way so the edges with
 734    smallest badness are inlined first.  After each inlining is performed
 735    the costs of all caller edges of nodes affected are recomputed so the
 736    metrics may accurately depend on values such as number of inlinable callers
 737    of the function or function body size.  */
 738
 739 static int
 740 edge_badness (struct cgraph_edge *edge, bool dump)
 741 {
 742   gcov_type badness;
 743   int growth, time_growth;
 744   struct cgraph_node *callee = cgraph_function_or_thunk_node (edge->callee,
 745                                                               NULL);
 746   struct inline_summary *callee_info = inline_summary (callee);
 747
 748   if (DECL_DISREGARD_INLINE_LIMITS (callee->decl))
 749     return INT_MIN;
 750
 751   growth = estimate_edge_growth (edge);
 752   time_growth = estimate_edge_time (edge);
 753
 754   if (dump)
 755     {
 756       fprintf (dump_file, "    Badness calculation for %s -> %s\n",
 757                xstrdup (cgraph_node_name (edge->caller)),
 758                xstrdup (cgraph_node_name (callee)));
 759       fprintf (dump_file, "      size growth %i, time growth %i\n",
 760                growth,
 761                time_growth);
 762     }
 763
 764   /* Always prefer inlining saving code size.  */
 765   if (growth <= 0)
 766     {
 767       badness = INT_MIN / 2 + growth;
 768       if (dump)
 769         fprintf (dump_file, "      %i: Growth %i <= 0\n", (int) badness,
 770                  growth);
 771     }
 772
 773   /* When profiling is available, compute badness as:
 774
 775                 relative_edge_count * relative_time_benefit
 776      goodness = -------------------------------------------
 777                 edge_growth
 778      badness = -goodness
 779
 780     The fraction is upside down, becuase on edge counts and time beneits
 781     the bounds are known. Edge growth is essentially unlimited.  */
 782
 783   else if (max_count)
 784     {
 785       int relbenefit = relative_time_benefit (callee_info, edge, time_growth);
 786       badness =
 787         ((int)
 788          ((double) edge->count * INT_MIN / 2 / max_count / 512) *
 789          relative_time_benefit (callee_info, edge, time_growth)) / growth;
 790
 791       /* Be sure that insanity of the profile won't lead to increasing counts
 792          in the scalling and thus to overflow in the computation above.  */
 793       gcc_assert (max_count >= edge->count);
 794       if (dump)
 795         {
 796           fprintf (dump_file,
 797                    "      %i (relative %f): profile info. Relative count %f"
 798                    " * Relative benefit %f\n",
 799                    (int) badness, (double) badness / INT_MIN,
 800                    (double) edge->count / max_count,
 801                    relbenefit * 100 / 256.0);
 802         }
 803     }
 804
 805   /* When function local profile is available. Compute badness as:
 806
 807
 808                growth_of_callee
 809      badness = -------------------------------------- + growth_for-all
 810                relative_time_benefit * edge_frequency
 811
 812   */
 813   else if (flag_guess_branch_prob)
 814     {
 815       int div = edge->frequency * (1<<10) / CGRAPH_FREQ_MAX;
 816
 817       div = MAX (div, 1);
 818       gcc_checking_assert (edge->frequency <= CGRAPH_FREQ_MAX);
 819       div *= relative_time_benefit (callee_info, edge, time_growth);
 820
 821       /* frequency is normalized in range 1...2^10.
 822          relbenefit in range 1...2^9
 823          DIV should be in range 1....2^19.  */
 824       gcc_checking_assert (div >= 1 && div <= (1<<19));
 825
 826       /* Result must be integer in range 0...INT_MAX.
 827          Set the base of fixed point calculation so we don't lose much of
 828          precision for small bandesses (those are interesting) yet we don't
 829          overflow for growths that are still in interesting range.
 830
 831          Fixed point arithmetic with point at 8th bit. */
 832       badness = ((gcov_type)growth) * (1<<(19+8));
 833       badness = (badness + div / 2) / div;
 834
 835       /* Overall growth of inlining all calls of function matters: we want to
 836          inline so offline copy of function is no longer needed.
 837
 838          Additionally functions that can be fully inlined without much of
 839          effort are better inline candidates than functions that can be fully
 840          inlined only after noticeable overall unit growths. The latter
 841          are better in a sense compressing of code size by factoring out common
 842          code into separate function shared by multiple code paths.
 843
 844          We might mix the valud into the fraction by taking into account
 845          relative growth of the unit, but for now just add the number
 846          into resulting fraction.  */
 847       if (badness > INT_MAX / 2)
 848         {
 849           badness = INT_MAX / 2;
 850           if (dump)
 851             fprintf (dump_file, "Badness overflow\n");
 852         }
 853       if (dump)
 854         {
 855           fprintf (dump_file,
 856                    "      %i: guessed profile. frequency %f,"
 857                    " benefit %f%%, divisor %i\n",
 858                    (int) badness, (double)edge->frequency / CGRAPH_FREQ_BASE,
 859                    relative_time_benefit (callee_info, edge, time_growth) * 100 / 256.0, div);
 860         }
 861     }
 862   /* When function local profile is not available or it does not give
 863      useful information (ie frequency is zero), base the cost on
 864      loop nest and overall size growth, so we optimize for overall number
 865      of functions fully inlined in program.  */
 866   else
 867     {
 868       int nest = MIN (inline_edge_summary (edge)->loop_depth, 8);
 869       badness = growth * 256;
 870
 871       /* Decrease badness if call is nested.  */
 872       if (badness > 0)
 873         badness >>= nest;
 874       else
 875         {
 876           badness <<= nest;
 877         }
 878       if (dump)
 879         fprintf (dump_file, "      %i: no profile. nest %i\n", (int) badness,
 880                  nest);
 881     }
 882
 883   /* Ensure that we did not overflow in all the fixed point math above.  */
 884   gcc_assert (badness >= INT_MIN);
 885   gcc_assert (badness <= INT_MAX - 1);
 886   /* Make recursive inlining happen always after other inlining is done.  */
 887   if (cgraph_edge_recursive_p (edge))
 888     return badness + 1;
 889   else
 890     return badness;
 891 }
 892
 893 /* Recompute badness of EDGE and update its key in HEAP if needed.  */
 894 static inline void
 895 update_edge_key (fibheap_t heap, struct cgraph_edge *edge)
 896 {
 897   int badness = edge_badness (edge, false);
 898   if (edge->aux)
 899     {
 900       fibnode_t n = (fibnode_t) edge->aux;
 901       gcc_checking_assert (n->data == edge);
 902
 903       /* fibheap_replace_key only decrease the keys.
 904          When we increase the key we do not update heap
 905          and instead re-insert the element once it becomes
 906          a minimum of heap.  */
 907       if (badness < n->key)
 908         {
 909           if (dump_file && (dump_flags & TDF_DETAILS))
 910             {
 911               fprintf (dump_file,
 912                        "  decreasing badness %s/%i -> %s/%i, %i to %i\n",
 913                        xstrdup (cgraph_node_name (edge->caller)),
 914                        edge->caller->uid,
 915                        xstrdup (cgraph_node_name (edge->callee)),
 916                        edge->callee->uid,
 917                        (int)n->key,
 918                        badness);
 919             }
 920           fibheap_replace_key (heap, n, badness);
 921           gcc_checking_assert (n->key == badness);
 922         }
 923     }
 924   else
 925     {
 926        if (dump_file && (dump_flags & TDF_DETAILS))
 927          {
 928            fprintf (dump_file,
 929                     "  enqueuing call %s/%i -> %s/%i, badness %i\n",
 930                     xstrdup (cgraph_node_name (edge->caller)),
 931                     edge->caller->uid,
 932                     xstrdup (cgraph_node_name (edge->callee)),
 933                     edge->callee->uid,
 934                     badness);
 935          }
 936       edge->aux = fibheap_insert (heap, badness, edge);
 937     }
 938 }
 939
 940
 941 /* NODE was inlined.
 942    All caller edges needs to be resetted because
 943    size estimates change. Similarly callees needs reset
 944    because better context may be known.  */
 945
 946 static void
 947 reset_edge_caches (struct cgraph_node *node)
 948 {
 949   struct cgraph_edge *edge;
 950   struct cgraph_edge *e = node->callees;
 951   struct cgraph_node *where = node;
 952   int i;
 953   struct ipa_ref *ref;
 954
 955   if (where->global.inlined_to)
 956     where = where->global.inlined_to;
 957
 958   /* WHERE body size has changed, the cached growth is invalid.  */
 959   reset_node_growth_cache (where);
 960
 961   for (edge = where->callers; edge; edge = edge->next_caller)
 962     if (edge->inline_failed)
 963       reset_edge_growth_cache (edge);
 964   for (i = 0; ipa_ref_list_refering_iterate (&where->ref_list, i, ref); i++)
 965     if (ref->use == IPA_REF_ALIAS)
 966       reset_edge_caches (ipa_ref_refering_node (ref));
 967
 968   if (!e)
 969     return;
 970
 971   while (true)
 972     if (!e->inline_failed && e->callee->callees)
 973       e = e->callee->callees;
 974     else
 975       {
 976         if (e->inline_failed)
 977           reset_edge_growth_cache (e);
 978         if (e->next_callee)
 979           e = e->next_callee;
 980         else
 981           {
 982             do
 983               {
 984                 if (e->caller == node)
 985                   return;
 986                 e = e->caller->callers;
 987               }
 988             while (!e->next_callee);
 989             e = e->next_callee;
 990           }
 991       }
 992 }
 993
 994 /* Recompute HEAP nodes for each of caller of NODE.
 995    UPDATED_NODES track nodes we already visited, to avoid redundant work.
 996    When CHECK_INLINABLITY_FOR is set, re-check for specified edge that
 997    it is inlinable. Otherwise check all edges.  */
 998
 999 static void
1000 update_caller_keys (fibheap_t heap, struct cgraph_node *node,
1001                     bitmap updated_nodes,
1002                     struct cgraph_edge *check_inlinablity_for)
1003 {
1004   struct cgraph_edge *edge;
1005   int i;
1006   struct ipa_ref *ref;
1007
1008   if ((!node->alias && !inline_summary (node)->inlinable)
1009       || cgraph_function_body_availability (node) <= AVAIL_OVERWRITABLE
1010       || node->global.inlined_to)
1011     return;
1012   if (!bitmap_set_bit (updated_nodes, node->uid))
1013     return;
1014
1015   for (i = 0; ipa_ref_list_refering_iterate (&node->ref_list, i, ref); i++)
1016     if (ref->use == IPA_REF_ALIAS)
1017       {
1018         struct cgraph_node *alias = ipa_ref_refering_node (ref);
1019         update_caller_keys (heap, alias, updated_nodes, check_inlinablity_for);
1020       }
1021
1022   for (edge = node->callers; edge; edge = edge->next_caller)
1023     if (edge->inline_failed)
1024       {
1025         if (!check_inlinablity_for
1026             || check_inlinablity_for == edge)
1027           {
1028             if (can_inline_edge_p (edge, false)
1029                 && want_inline_small_function_p (edge, false))
1030               update_edge_key (heap, edge);
1031             else if (edge->aux)
1032               {
1033                 report_inline_failed_reason (edge);
1034                 fibheap_delete_node (heap, (fibnode_t) edge->aux);
1035                 edge->aux = NULL;
1036               }
1037           }
1038         else if (edge->aux)
1039           update_edge_key (heap, edge);
1040       }
1041 }
1042
1043 /* Recompute HEAP nodes for each uninlined call in NODE.
1044    This is used when we know that edge badnesses are going only to increase
1045    (we introduced new call site) and thus all we need is to insert newly
1046    created edges into heap.  */
1047
1048 static void
1049 update_callee_keys (fibheap_t heap, struct cgraph_node *node,
1050                     bitmap updated_nodes)
1051 {
1052   struct cgraph_edge *e = node->callees;
1053
1054   if (!e)
1055     return;
1056   while (true)
1057     if (!e->inline_failed && e->callee->callees)
1058       e = e->callee->callees;
1059     else
1060       {
1061         enum availability avail;
1062         struct cgraph_node *callee;
1063         /* We do not reset callee growth cache here.  Since we added a new call,
1064            growth chould have just increased and consequentely badness metric
1065            don't need updating.  */
1066         if (e->inline_failed
1067             && (callee = cgraph_function_or_thunk_node (e->callee, &avail))
1068             && inline_summary (callee)->inlinable
1069             && cgraph_function_body_availability (callee) >= AVAIL_AVAILABLE
1070             && !bitmap_bit_p (updated_nodes, callee->uid))
1071           {
1072             if (can_inline_edge_p (e, false)
1073                 && want_inline_small_function_p (e, false))
1074               update_edge_key (heap, e);
1075             else if (e->aux)
1076               {
1077                 report_inline_failed_reason (e);
1078                 fibheap_delete_node (heap, (fibnode_t) e->aux);
1079                 e->aux = NULL;
1080               }
1081           }
1082         if (e->next_callee)
1083           e = e->next_callee;
1084         else
1085           {
1086             do
1087               {
1088                 if (e->caller == node)
1089                   return;
1090                 e = e->caller->callers;
1091               }
1092             while (!e->next_callee);
1093             e = e->next_callee;
1094           }
1095       }
1096 }
1097
1098 /* Recompute heap nodes for each of caller edges of each of callees.
1099    Walk recursively into all inline clones.  */
1100
1101 static void
1102 update_all_callee_keys (fibheap_t heap, struct cgraph_node *node,
1103                         bitmap updated_nodes)
1104 {
1105   struct cgraph_edge *e = node->callees;
1106   if (!e)
1107     return;
1108   while (true)
1109     if (!e->inline_failed && e->callee->callees)
1110       e = e->callee->callees;
1111     else
1112       {
1113         struct cgraph_node *callee = cgraph_function_or_thunk_node (e->callee,
1114                                                                     NULL);
1115
1116         /* We inlined and thus callees might have different number of calls.
1117            Reset their caches  */
1118         reset_node_growth_cache (callee);
1119         if (e->inline_failed)
1120           update_caller_keys (heap, callee, updated_nodes, e);
1121         if (e->next_callee)
1122           e = e->next_callee;
1123         else
1124           {
1125             do
1126               {
1127                 if (e->caller == node)
1128                   return;
1129                 e = e->caller->callers;
1130               }
1131             while (!e->next_callee);
1132             e = e->next_callee;
1133           }
1134       }
1135 }
1136
1137 /* Enqueue all recursive calls from NODE into priority queue depending on
1138    how likely we want to recursively inline the call.  */
1139
1140 static void
1141 lookup_recursive_calls (struct cgraph_node *node, struct cgraph_node *where,
1142                         fibheap_t heap)
1143 {
1144   struct cgraph_edge *e;
1145   enum availability avail;
1146
1147   for (e = where->callees; e; e = e->next_callee)
1148     if (e->callee == node
1149         || (cgraph_function_or_thunk_node (e->callee, &avail) == node
1150             && avail > AVAIL_OVERWRITABLE))
1151       {
1152         /* When profile feedback is available, prioritize by expected number
1153            of calls.  */
1154         fibheap_insert (heap,
1155                         !max_count ? -e->frequency
1156                         : -(e->count / ((max_count + (1<<24) - 1) / (1<<24))),
1157                         e);
1158       }
1159   for (e = where->callees; e; e = e->next_callee)
1160     if (!e->inline_failed)
1161       lookup_recursive_calls (node, e->callee, heap);
1162 }
1163
1164 /* Decide on recursive inlining: in the case function has recursive calls,
1165    inline until body size reaches given argument.  If any new indirect edges
1166    are discovered in the process, add them to *NEW_EDGES, unless NEW_EDGES
1167    is NULL.  */
1168
1169 static bool
1170 recursive_inlining (struct cgraph_edge *edge,
1171                     VEC (cgraph_edge_p, heap) **new_edges)
1172 {
1173   int limit = PARAM_VALUE (PARAM_MAX_INLINE_INSNS_RECURSIVE_AUTO);
1174   fibheap_t heap;
1175   struct cgraph_node *node;
1176   struct cgraph_edge *e;
1177   struct cgraph_node *master_clone = NULL, *next;
1178   int depth = 0;
1179   int n = 0;
1180
1181   node = edge->caller;
1182   if (node->global.inlined_to)
1183     node = node->global.inlined_to;
1184
1185   if (DECL_DECLARED_INLINE_P (node->decl))
1186     limit = PARAM_VALUE (PARAM_MAX_INLINE_INSNS_RECURSIVE);
1187
1188   /* Make sure that function is small enough to be considered for inlining.  */
1189   if (estimate_size_after_inlining (node, edge)  >= limit)
1190     return false;
1191   heap = fibheap_new ();
1192   lookup_recursive_calls (node, node, heap);
1193   if (fibheap_empty (heap))
1194     {
1195       fibheap_delete (heap);
1196       return false;
1197     }
1198
1199   if (dump_file)
1200     fprintf (dump_file,
1201              "  Performing recursive inlining on %s\n",
1202              cgraph_node_name (node));
1203
1204   /* Do the inlining and update list of recursive call during process.  */
1205   while (!fibheap_empty (heap))
1206     {
1207       struct cgraph_edge *curr
1208         = (struct cgraph_edge *) fibheap_extract_min (heap);
1209       struct cgraph_node *cnode;
1210
1211       if (estimate_size_after_inlining (node, curr) > limit)
1212         break;
1213
1214       if (!can_inline_edge_p (curr, true))
1215         continue;
1216
1217       depth = 1;
1218       for (cnode = curr->caller;
1219            cnode->global.inlined_to; cnode = cnode->callers->caller)
1220         if (node->decl
1221             == cgraph_function_or_thunk_node (curr->callee, NULL)->decl)
1222           depth++;
1223
1224       if (!want_inline_self_recursive_call_p (curr, node, false, depth))
1225         continue;
1226
1227       if (dump_file)
1228         {
1229           fprintf (dump_file,
1230                    "   Inlining call of depth %i", depth);
1231           if (node->count)
1232             {
1233               fprintf (dump_file, " called approx. %.2f times per call",
1234                        (double)curr->count / node->count);
1235             }
1236           fprintf (dump_file, "\n");
1237         }
1238       if (!master_clone)
1239         {
1240           /* We need original clone to copy around.  */
1241           master_clone = cgraph_clone_node (node, node->decl,
1242                                             node->count, CGRAPH_FREQ_BASE,
1243                                             false, NULL, true);
1244           for (e = master_clone->callees; e; e = e->next_callee)
1245             if (!e->inline_failed)
1246               clone_inlined_nodes (e, true, false, NULL);
1247         }
1248
1249       cgraph_redirect_edge_callee (curr, master_clone);
1250       inline_call (curr, false, new_edges, &overall_size);
1251       lookup_recursive_calls (node, curr->callee, heap);
1252       n++;
1253     }
1254
1255   if (!fibheap_empty (heap) && dump_file)
1256     fprintf (dump_file, "    Recursive inlining growth limit met.\n");
1257   fibheap_delete (heap);
1258
1259   if (!master_clone)
1260     return false;
1261
1262   if (dump_file)
1263     fprintf (dump_file,
1264              "\n   Inlined %i times, "
1265              "body grown from size %i to %i, time %i to %i\n", n,
1266              inline_summary (master_clone)->size, inline_summary (node)->size,
1267              inline_summary (master_clone)->time, inline_summary (node)->time);
1268
1269   /* Remove master clone we used for inlining.  We rely that clones inlined
1270      into master clone gets queued just before master clone so we don't
1271      need recursion.  */
1272   for (node = cgraph_nodes; node != master_clone;
1273        node = next)
1274     {
1275       next = node->next;
1276       if (node->global.inlined_to == master_clone)
1277         cgraph_remove_node (node);
1278     }
1279   cgraph_remove_node (master_clone);
1280   return true;
1281 }
1282
1283
1284 /* Given whole compilation unit estimate of INSNS, compute how large we can
1285    allow the unit to grow.  */
1286
1287 static int
1288 compute_max_insns (int insns)
1289 {
1290   int max_insns = insns;
1291   if (max_insns < PARAM_VALUE (PARAM_LARGE_UNIT_INSNS))
1292     max_insns = PARAM_VALUE (PARAM_LARGE_UNIT_INSNS);
1293
1294   return ((HOST_WIDEST_INT) max_insns
1295           * (100 + PARAM_VALUE (PARAM_INLINE_UNIT_GROWTH)) / 100);
1296 }
1297
1298
1299 /* Compute badness of all edges in NEW_EDGES and add them to the HEAP.  */
1300
1301 static void
1302 add_new_edges_to_heap (fibheap_t heap, VEC (cgraph_edge_p, heap) *new_edges)
1303 {
1304   while (VEC_length (cgraph_edge_p, new_edges) > 0)
1305     {
1306       struct cgraph_edge *edge = VEC_pop (cgraph_edge_p, new_edges);
1307
1308       gcc_assert (!edge->aux);
1309       if (edge->inline_failed
1310           && can_inline_edge_p (edge, true)
1311           && want_inline_small_function_p (edge, true))
1312         edge->aux = fibheap_insert (heap, edge_badness (edge, false), edge);
1313     }
1314 }
1315
1316
1317 /* We use greedy algorithm for inlining of small functions:
1318    All inline candidates are put into prioritized heap ordered in
1319    increasing badness.
1320
1321    The inlining of small functions is bounded by unit growth parameters.  */
1322
1323 static void
1324 inline_small_functions (void)
1325 {
1326   struct cgraph_node *node;
1327   struct cgraph_edge *edge;
1328   fibheap_t heap = fibheap_new ();
1329   bitmap updated_nodes = BITMAP_ALLOC (NULL);
1330   int min_size, max_size;
1331   VEC (cgraph_edge_p, heap) *new_indirect_edges = NULL;
1332   int initial_size = 0;
1333
1334   if (flag_indirect_inlining)
1335     new_indirect_edges = VEC_alloc (cgraph_edge_p, heap, 8);
1336
1337   if (dump_file)
1338     fprintf (dump_file,
1339              "\nDeciding on inlining of small functions.  Starting with size %i.\n",
1340              initial_size);
1341
1342   /* Compute overall unit size and other global parameters used by badness
1343      metrics.  */
1344
1345   max_count = 0;
1346   initialize_growth_caches ();
1347
1348   FOR_EACH_DEFINED_FUNCTION (node)
1349     if (!node->global.inlined_to)
1350       {
1351         if (cgraph_function_with_gimple_body_p (node)
1352             || node->thunk.thunk_p)
1353           {
1354             struct inline_summary *info = inline_summary (node);
1355
1356             if (!DECL_EXTERNAL (node->decl))
1357               initial_size += info->size;
1358           }
1359
1360         for (edge = node->callers; edge; edge = edge->next_caller)
1361           if (max_count < edge->count)
1362             max_count = edge->count;
1363       }
1364
1365   overall_size = initial_size;
1366   max_size = compute_max_insns (overall_size);
1367   min_size = overall_size;
1368
1369   /* Populate the heeap with all edges we might inline.  */
1370
1371   FOR_EACH_DEFINED_FUNCTION (node)
1372     if (!node->global.inlined_to)
1373       {
1374         if (dump_file)
1375           fprintf (dump_file, "Enqueueing calls of %s/%i.\n",
1376                    cgraph_node_name (node), node->uid);
1377
1378         for (edge = node->callers; edge; edge = edge->next_caller)
1379           if (edge->inline_failed
1380               && can_inline_edge_p (edge, true)
1381               && want_inline_small_function_p (edge, true)
1382               && edge->inline_failed)
1383             {
1384               gcc_assert (!edge->aux);
1385               update_edge_key (heap, edge);
1386             }
1387       }
1388
1389   gcc_assert (in_lto_p
1390               || !max_count
1391               || (profile_info && flag_branch_probabilities));
1392
1393   while (!fibheap_empty (heap))
1394     {
1395       int old_size = overall_size;
1396       struct cgraph_node *where, *callee;
1397       int badness = fibheap_min_key (heap);
1398       int current_badness;
1399       int cached_badness;
1400       int growth;
1401
1402       edge = (struct cgraph_edge *) fibheap_extract_min (heap);
1403       gcc_assert (edge->aux);
1404       edge->aux = NULL;
1405       if (!edge->inline_failed)
1406         continue;
1407
1408       /* Be sure that caches are maintained consistent.
1409          We can not make this ENABLE_CHECKING only because it cause differnt
1410          updates of the fibheap queue.  */
1411       cached_badness = edge_badness (edge, false);
1412       reset_edge_growth_cache (edge);
1413       reset_node_growth_cache (edge->callee);
1414
1415       /* When updating the edge costs, we only decrease badness in the keys.
1416          Increases of badness are handled lazilly; when we see key with out
1417          of date value on it, we re-insert it now.  */
1418       current_badness = edge_badness (edge, false);
1419       gcc_assert (cached_badness == current_badness);
1420       gcc_assert (current_badness >= badness);
1421       if (current_badness != badness)
1422         {
1423           edge->aux = fibheap_insert (heap, current_badness, edge);
1424           continue;
1425         }
1426
1427       if (!can_inline_edge_p (edge, true))
1428         continue;
1429
1430       callee = cgraph_function_or_thunk_node (edge->callee, NULL);
1431       growth = estimate_edge_growth (edge);
1432       if (dump_file)
1433         {
1434           fprintf (dump_file,
1435                    "\nConsidering %s with %i size\n",
1436                    cgraph_node_name (callee),
1437                    inline_summary (callee)->size);
1438           fprintf (dump_file,
1439                    " to be inlined into %s in %s:%i\n"
1440                    " Estimated growth after inlined into all is %+i insns.\n"
1441                    " Estimated badness is %i, frequency %.2f.\n",
1442                    cgraph_node_name (edge->caller),
1443                    flag_wpa ? "unknown"
1444                    : gimple_filename ((const_gimple) edge->call_stmt),
1445                    flag_wpa ? -1
1446                    : gimple_lineno ((const_gimple) edge->call_stmt),
1447                    estimate_growth (callee),
1448                    badness,
1449                    edge->frequency / (double)CGRAPH_FREQ_BASE);
1450           if (edge->count)
1451             fprintf (dump_file," Called "HOST_WIDEST_INT_PRINT_DEC"x\n",
1452                      edge->count);
1453           if (dump_flags & TDF_DETAILS)
1454             edge_badness (edge, true);
1455         }
1456
1457       if (overall_size + growth > max_size
1458           && !DECL_DISREGARD_INLINE_LIMITS (callee->decl))
1459         {
1460           edge->inline_failed = CIF_INLINE_UNIT_GROWTH_LIMIT;
1461           report_inline_failed_reason (edge);
1462           continue;
1463         }
1464
1465       if (!want_inline_small_function_p (edge, true))
1466         continue;
1467
1468       /* Heuristics for inlining small functions works poorly for
1469          recursive calls where we do efect similar to loop unrolling.
1470          When inliing such edge seems profitable, leave decision on
1471          specific inliner.  */
1472       if (cgraph_edge_recursive_p (edge))
1473         {
1474           where = edge->caller;
1475           if (where->global.inlined_to)
1476             where = where->global.inlined_to;
1477           if (!recursive_inlining (edge,
1478                                    flag_indirect_inlining
1479                                    ? &new_indirect_edges : NULL))
1480             {
1481               edge->inline_failed = CIF_RECURSIVE_INLINING;
1482               continue;
1483             }
1484           reset_edge_caches (where);
1485           /* Recursive inliner inlines all recursive calls of the function
1486              at once. Consequently we need to update all callee keys.  */
1487           if (flag_indirect_inlining)
1488             add_new_edges_to_heap (heap, new_indirect_edges);
1489           update_all_callee_keys (heap, where, updated_nodes);
1490         }
1491       else
1492         {
1493           struct cgraph_node *outer_node = NULL;
1494           int depth = 0;
1495
1496           /* Consider the case where self recursive function A is inlined into B.
1497              This is desired optimization in some cases, since it leads to effect
1498              similar of loop peeling and we might completely optimize out the
1499              recursive call.  However we must be extra selective.  */
1500
1501           where = edge->caller;
1502           while (where->global.inlined_to)
1503             {
1504               if (where->decl == callee->decl)
1505                 outer_node = where, depth++;
1506               where = where->callers->caller;
1507             }
1508           if (outer_node
1509               && !want_inline_self_recursive_call_p (edge, outer_node,
1510                                                      true, depth))
1511             {
1512               edge->inline_failed
1513                 = (DECL_DISREGARD_INLINE_LIMITS (edge->callee->decl)
1514                    ? CIF_RECURSIVE_INLINING : CIF_UNSPECIFIED);
1515               continue;
1516             }
1517           else if (depth && dump_file)
1518             fprintf (dump_file, " Peeling recursion with depth %i\n", depth);
1519
1520           gcc_checking_assert (!callee->global.inlined_to);
1521           inline_call (edge, true, &new_indirect_edges, &overall_size);
1522           if (flag_indirect_inlining)
1523             add_new_edges_to_heap (heap, new_indirect_edges);
1524
1525           reset_edge_caches (edge->callee);
1526           reset_node_growth_cache (callee);
1527
1528           /* We inlined last offline copy to the body.  This might lead
1529              to callees of function having fewer call sites and thus they
1530              may need updating.
1531
1532              FIXME: the callee size could also shrink because more information
1533              is propagated from caller.  We don't track when this happen and
1534              thus we need to recompute everything all the time.  Once this is
1535              solved, "|| 1" should go away.  */
1536           if (callee->global.inlined_to || 1)
1537             update_all_callee_keys (heap, callee, updated_nodes);
1538           else
1539             update_callee_keys (heap, edge->callee, updated_nodes);
1540         }
1541       where = edge->caller;
1542       if (where->global.inlined_to)
1543         where = where->global.inlined_to;
1544
1545       /* Our profitability metric can depend on local properties
1546          such as number of inlinable calls and size of the function body.
1547          After inlining these properties might change for the function we
1548          inlined into (since it's body size changed) and for the functions
1549          called by function we inlined (since number of it inlinable callers
1550          might change).  */
1551       update_caller_keys (heap, where, updated_nodes, NULL);
1552
1553       /* We removed one call of the function we just inlined.  If offline
1554          copy is still needed, be sure to update the keys.  */
1555       if (callee != where && !callee->global.inlined_to)
1556         update_caller_keys (heap, callee, updated_nodes, NULL);
1557       bitmap_clear (updated_nodes);
1558
1559       if (dump_file)
1560         {
1561           fprintf (dump_file,
1562                    " Inlined into %s which now has time %i and size %i,"
1563                    "net change of %+i.\n",
1564                    cgraph_node_name (edge->caller),
1565                    inline_summary (edge->caller)->time,
1566                    inline_summary (edge->caller)->size,
1567                    overall_size - old_size);
1568         }
1569       if (min_size > overall_size)
1570         {
1571           min_size = overall_size;
1572           max_size = compute_max_insns (min_size);
1573
1574           if (dump_file)
1575             fprintf (dump_file, "New minimal size reached: %i\n", min_size);
1576         }
1577     }
1578
1579   free_growth_caches ();
1580   if (new_indirect_edges)
1581     VEC_free (cgraph_edge_p, heap, new_indirect_edges);
1582   fibheap_delete (heap);
1583   if (dump_file)
1584     fprintf (dump_file,
1585              "Unit growth for small function inlining: %i->%i (%i%%)\n",
1586              initial_size, overall_size,
1587              initial_size ? overall_size * 100 / (initial_size) - 100: 0);
1588   BITMAP_FREE (updated_nodes);
1589 }
1590
1591 /* Flatten NODE.  Performed both during early inlining and
1592    at IPA inlining time.  */
1593
1594 static void
1595 flatten_function (struct cgraph_node *node, bool early)
1596 {
1597   struct cgraph_edge *e;
1598
1599   /* We shouldn't be called recursively when we are being processed.  */
1600   gcc_assert (node->aux == NULL);
1601
1602   node->aux = (void *) node;
1603
1604   for (e = node->callees; e; e = e->next_callee)
1605     {
1606       struct cgraph_node *orig_callee;
1607       struct cgraph_node *callee = cgraph_function_or_thunk_node (e->callee, NULL);
1608
1609       /* We've hit cycle?  It is time to give up.  */
1610       if (callee->aux)
1611         {
1612           if (dump_file)
1613             fprintf (dump_file,
1614                      "Not inlining %s into %s to avoid cycle.\n",
1615                      xstrdup (cgraph_node_name (callee)),
1616                      xstrdup (cgraph_node_name (e->caller)));
1617           e->inline_failed = CIF_RECURSIVE_INLINING;
1618           continue;
1619         }
1620
1621       /* When the edge is already inlined, we just need to recurse into
1622          it in order to fully flatten the leaves.  */
1623       if (!e->inline_failed)
1624         {
1625           flatten_function (callee, early);
1626           continue;
1627         }
1628
1629       /* Flatten attribute needs to be processed during late inlining. For
1630          extra code quality we however do flattening during early optimization,
1631          too.  */
1632       if (!early
1633           ? !can_inline_edge_p (e, true)
1634           : !can_early_inline_edge_p (e))
1635         continue;
1636
1637       if (cgraph_edge_recursive_p (e))
1638         {
1639           if (dump_file)
1640             fprintf (dump_file, "Not inlining: recursive call.\n");
1641           continue;
1642         }
1643
1644       if (gimple_in_ssa_p (DECL_STRUCT_FUNCTION (node->decl))
1645           != gimple_in_ssa_p (DECL_STRUCT_FUNCTION (callee->decl)))
1646         {
1647           if (dump_file)
1648             fprintf (dump_file, "Not inlining: SSA form does not match.\n");
1649           continue;
1650         }
1651
1652       /* Inline the edge and flatten the inline clone.  Avoid
1653          recursing through the original node if the node was cloned.  */
1654       if (dump_file)
1655         fprintf (dump_file, " Inlining %s into %s.\n",
1656                  xstrdup (cgraph_node_name (callee)),
1657                  xstrdup (cgraph_node_name (e->caller)));
1658       orig_callee = callee;
1659       inline_call (e, true, NULL, NULL);
1660       if (e->callee != orig_callee)
1661         orig_callee->aux = (void *) node;
1662       flatten_function (e->callee, early);
1663       if (e->callee != orig_callee)
1664         orig_callee->aux = NULL;
1665     }
1666
1667   node->aux = NULL;
1668 }
1669
1670 /* Decide on the inlining.  We do so in the topological order to avoid
1671    expenses on updating data structures.  */
1672
1673 static unsigned int
1674 ipa_inline (void)
1675 {
1676   struct cgraph_node *node;
1677   int nnodes;
1678   struct cgraph_node **order =
1679     XCNEWVEC (struct cgraph_node *, cgraph_n_nodes);
1680   int i;
1681
1682   if (in_lto_p && optimize)
1683     ipa_update_after_lto_read ();
1684
1685   if (dump_file)
1686     dump_inline_summaries (dump_file);
1687
1688   nnodes = ipa_reverse_postorder (order);
1689
1690   for (node = cgraph_nodes; node; node = node->next)
1691     node->aux = 0;
1692
1693   if (dump_file)
1694     fprintf (dump_file, "\nFlattening functions:\n");
1695
1696   /* In the first pass handle functions to be flattened.  Do this with
1697      a priority so none of our later choices will make this impossible.  */
1698   for (i = nnodes - 1; i >= 0; i--)
1699     {
1700       node = order[i];
1701
1702       /* Handle nodes to be flattened.
1703          Ideally when processing callees we stop inlining at the
1704          entry of cycles, possibly cloning that entry point and
1705          try to flatten itself turning it into a self-recursive
1706          function.  */
1707       if (lookup_attribute ("flatten",
1708                             DECL_ATTRIBUTES (node->decl)) != NULL)
1709         {
1710           if (dump_file)
1711             fprintf (dump_file,
1712                      "Flattening %s\n", cgraph_node_name (node));
1713           flatten_function (node, false);
1714         }
1715     }
1716
1717   inline_small_functions ();
1718   cgraph_remove_unreachable_nodes (true, dump_file);
1719   free (order);
1720
1721   /* We already perform some inlining of functions called once during
1722      inlining small functions above.  After unreachable nodes are removed,
1723      we still might do a quick check that nothing new is found.  */
1724   if (flag_inline_functions_called_once)
1725     {
1726       int cold;
1727       if (dump_file)
1728         fprintf (dump_file, "\nDeciding on functions called once:\n");
1729
1730       /* Inlining one function called once has good chance of preventing
1731          inlining other function into the same callee.  Ideally we should
1732          work in priority order, but probably inlining hot functions first
1733          is good cut without the extra pain of maintaining the queue.
1734
1735          ??? this is not really fitting the bill perfectly: inlining function
1736          into callee often leads to better optimization of callee due to
1737          increased context for optimization.
1738          For example if main() function calls a function that outputs help
1739          and then function that does the main optmization, we should inline
1740          the second with priority even if both calls are cold by themselves.
1741
1742          We probably want to implement new predicate replacing our use of
1743          maybe_hot_edge interpreted as maybe_hot_edge || callee is known
1744          to be hot.  */
1745       for (cold = 0; cold <= 1; cold ++)
1746         {
1747           for (node = cgraph_nodes; node; node = node->next)
1748             {
1749               if (want_inline_function_called_once_p (node)
1750                   && (cold
1751                       || cgraph_maybe_hot_edge_p (node->callers)))
1752                 {
1753                   struct cgraph_node *caller = node->callers->caller;
1754
1755                   if (dump_file)
1756                     {
1757                       fprintf (dump_file,
1758                                "\nInlining %s size %i.\n",
1759                                cgraph_node_name (node),
1760                                inline_summary (node)->size);
1761                       fprintf (dump_file,
1762                                " Called once from %s %i insns.\n",
1763                                cgraph_node_name (node->callers->caller),
1764                                inline_summary (node->callers->caller)->size);
1765                     }
1766
1767                   inline_call (node->callers, true, NULL, NULL);
1768                   if (dump_file)
1769                     fprintf (dump_file,
1770                              " Inlined into %s which now has %i size\n",
1771                              cgraph_node_name (caller),
1772                              inline_summary (caller)->size);
1773                 }
1774             }
1775         }
1776     }
1777
1778   /* Free ipa-prop structures if they are no longer needed.  */
1779   if (optimize)
1780     ipa_free_all_structures_after_iinln ();
1781
1782   if (dump_file)
1783     fprintf (dump_file,
1784              "\nInlined %i calls, eliminated %i functions\n\n",
1785              ncalls_inlined, nfunctions_inlined);
1786
1787   if (dump_file)
1788     dump_inline_summaries (dump_file);
1789   /* In WPA we use inline summaries for partitioning process.  */
1790   if (!flag_wpa)
1791     inline_free_summary ();
1792   return 0;
1793 }
1794
1795 /* Inline always-inline function calls in NODE.  */
1796
1797 static bool
1798 inline_always_inline_functions (struct cgraph_node *node)
1799 {
1800   struct cgraph_edge *e;
1801   bool inlined = false;
1802
1803   for (e = node->callees; e; e = e->next_callee)
1804     {
1805       struct cgraph_node *callee = cgraph_function_or_thunk_node (e->callee, NULL);
1806       if (!DECL_DISREGARD_INLINE_LIMITS (callee->decl))
1807         continue;
1808
1809       if (cgraph_edge_recursive_p (e))
1810         {
1811           if (dump_file)
1812             fprintf (dump_file, "  Not inlining recursive call to %s.\n",
1813                      cgraph_node_name (e->callee));
1814           e->inline_failed = CIF_RECURSIVE_INLINING;
1815           continue;
1816         }
1817
1818       if (!can_early_inline_edge_p (e))
1819         continue;
1820
1821       if (dump_file)
1822         fprintf (dump_file, "  Inlining %s into %s (always_inline).\n",
1823                  xstrdup (cgraph_node_name (e->callee)),
1824                  xstrdup (cgraph_node_name (e->caller)));
1825       inline_call (e, true, NULL, NULL);
1826       inlined = true;
1827     }
1828
1829   return inlined;
1830 }
1831
1832 /* Decide on the inlining.  We do so in the topological order to avoid
1833    expenses on updating data structures.  */
1834
1835 static bool
1836 early_inline_small_functions (struct cgraph_node *node)
1837 {
1838   struct cgraph_edge *e;
1839   bool inlined = false;
1840
1841   for (e = node->callees; e; e = e->next_callee)
1842     {
1843       struct cgraph_node *callee = cgraph_function_or_thunk_node (e->callee, NULL);
1844       if (!inline_summary (callee)->inlinable
1845           || !e->inline_failed)
1846         continue;
1847
1848       /* Do not consider functions not declared inline.  */
1849       if (!DECL_DECLARED_INLINE_P (callee->decl)
1850           && !flag_inline_small_functions
1851           && !flag_inline_functions)
1852         continue;
1853
1854       if (dump_file)
1855         fprintf (dump_file, "Considering inline candidate %s.\n",
1856                  cgraph_node_name (callee));
1857
1858       if (!can_early_inline_edge_p (e))
1859         continue;
1860
1861       if (cgraph_edge_recursive_p (e))
1862         {
1863           if (dump_file)
1864             fprintf (dump_file, "  Not inlining: recursive call.\n");
1865           continue;
1866         }
1867
1868       if (!want_early_inline_function_p (e))
1869         continue;
1870
1871       if (dump_file)
1872         fprintf (dump_file, " Inlining %s into %s.\n",
1873                  xstrdup (cgraph_node_name (callee)),
1874                  xstrdup (cgraph_node_name (e->caller)));
1875       inline_call (e, true, NULL, NULL);
1876       inlined = true;
1877     }
1878
1879   return inlined;
1880 }
1881
1882 /* Do inlining of small functions.  Doing so early helps profiling and other
1883    passes to be somewhat more effective and avoids some code duplication in
1884    later real inlining pass for testcases with very many function calls.  */
1885 static unsigned int
1886 early_inliner (void)
1887 {
1888   struct cgraph_node *node = cgraph_get_node (current_function_decl);
1889   struct cgraph_edge *edge;
1890   unsigned int todo = 0;
1891   int iterations = 0;
1892   bool inlined = false;
1893
1894   if (seen_error ())
1895     return 0;
1896
1897   /* Do nothing if datastructures for ipa-inliner are already computed.  This
1898      happens when some pass decides to construct new function and
1899      cgraph_add_new_function calls lowering passes and early optimization on
1900      it.  This may confuse ourself when early inliner decide to inline call to
1901      function clone, because function clones don't have parameter list in
1902      ipa-prop matching their signature.  */
1903   if (ipa_node_params_vector)
1904     return 0;
1905
1906 #ifdef ENABLE_CHECKING
1907   verify_cgraph_node (node);
1908 #endif
1909
1910   /* Even when not optimizing or not inlining inline always-inline
1911      functions.  */
1912   inlined = inline_always_inline_functions (node);
1913
1914   if (!optimize
1915       || flag_no_inline
1916       || !flag_early_inlining
1917       /* Never inline regular functions into always-inline functions
1918          during incremental inlining.  This sucks as functions calling
1919          always inline functions will get less optimized, but at the
1920          same time inlining of functions calling always inline
1921          function into an always inline function might introduce
1922          cycles of edges to be always inlined in the callgraph.
1923
1924          We might want to be smarter and just avoid this type of inlining.  */
1925       || DECL_DISREGARD_INLINE_LIMITS (node->decl))
1926     ;
1927   else if (lookup_attribute ("flatten",
1928                              DECL_ATTRIBUTES (node->decl)) != NULL)
1929     {
1930       /* When the function is marked to be flattened, recursively inline
1931          all calls in it.  */
1932       if (dump_file)
1933         fprintf (dump_file,
1934                  "Flattening %s\n", cgraph_node_name (node));
1935       flatten_function (node, true);
1936       inlined = true;
1937     }
1938   else
1939     {
1940       /* We iterate incremental inlining to get trivial cases of indirect
1941          inlining.  */
1942       while (iterations < PARAM_VALUE (PARAM_EARLY_INLINER_MAX_ITERATIONS)
1943              && early_inline_small_functions (node))
1944         {
1945           timevar_push (TV_INTEGRATION);
1946           todo |= optimize_inline_calls (current_function_decl);
1947
1948           /* Technically we ought to recompute inline parameters so the new
1949              iteration of early inliner works as expected.  We however have
1950              values approximately right and thus we only need to update edge
1951              info that might be cleared out for newly discovered edges.  */
1952           for (edge = node->callees; edge; edge = edge->next_callee)
1953             {
1954               struct inline_edge_summary *es = inline_edge_summary (edge);
1955               es->call_stmt_size
1956                 = estimate_num_insns (edge->call_stmt, &eni_size_weights);
1957               es->call_stmt_time
1958                 = estimate_num_insns (edge->call_stmt, &eni_time_weights);
1959               if (edge->callee->decl
1960                   && !gimple_check_call_matching_types (edge->call_stmt,
1961                                                         edge->callee->decl))
1962                 edge->call_stmt_cannot_inline_p = true;
1963             }
1964           timevar_pop (TV_INTEGRATION);
1965           iterations++;
1966           inlined = false;
1967         }
1968       if (dump_file)
1969         fprintf (dump_file, "Iterations: %i\n", iterations);
1970     }
1971
1972   if (inlined)
1973     {
1974       timevar_push (TV_INTEGRATION);
1975       todo |= optimize_inline_calls (current_function_decl);
1976       timevar_pop (TV_INTEGRATION);
1977     }
1978
1979   cfun->always_inline_functions_inlined = true;
1980
1981   return todo;
1982 }
1983
1984 struct gimple_opt_pass pass_early_inline =
1985 {
1986  {
1987   GIMPLE_PASS,
1988   "einline",                            /* name */
1989   NULL,                                 /* gate */
1990   early_inliner,                        /* execute */
1991   NULL,                                 /* sub */
1992   NULL,                                 /* next */
1993   0,                                    /* static_pass_number */
1994   TV_INLINE_HEURISTICS,                 /* tv_id */
1995   PROP_ssa,                             /* properties_required */
1996   0,                                    /* properties_provided */
1997   0,                                    /* properties_destroyed */
1998   0,                                    /* todo_flags_start */
1999   0                                     /* todo_flags_finish */
2000  }
2001 };
2002
2003
2004 /* When to run IPA inlining.  Inlining of always-inline functions
2005    happens during early inlining.
2006
2007    Enable inlining unconditoinally at -flto.  We need size estimates to
2008    drive partitioning.  */
2009
2010 static bool
2011 gate_ipa_inline (void)
2012 {
2013   return optimize || flag_lto || flag_wpa;
2014 }
2015
2016 struct ipa_opt_pass_d pass_ipa_inline =
2017 {
2018  {
2019   IPA_PASS,
2020   "inline",                             /* name */
2021   gate_ipa_inline,                      /* gate */
2022   ipa_inline,                           /* execute */
2023   NULL,                                 /* sub */
2024   NULL,                                 /* next */
2025   0,                                    /* static_pass_number */
2026   TV_INLINE_HEURISTICS,                 /* tv_id */
2027   0,                                    /* properties_required */
2028   0,                                    /* properties_provided */
2029   0,                                    /* properties_destroyed */
2030   TODO_remove_functions,                /* todo_flags_finish */
2031   TODO_dump_cgraph
2032   | TODO_remove_functions | TODO_ggc_collect    /* todo_flags_finish */
2033  },
2034  inline_generate_summary,               /* generate_summary */
2035  inline_write_summary,                  /* write_summary */
2036  inline_read_summary,                   /* read_summary */
2037  NULL,                                  /* write_optimization_summary */
2038  NULL,                                  /* read_optimization_summary */
2039  NULL,                                  /* stmt_fixup */
2040  0,                                     /* TODOs */
2041  inline_transform,                      /* function_transform */
2042  NULL,                                  /* variable_transform */
2043 };