gcc/ipa-inline.c

   1 /* Inlining decision heuristics.
   2    Copyright (C) 2003, 2004 Free Software Foundation, Inc.
   3    Contributed by Jan Hubicka
   4
   5 This file is part of GCC.
   6
   7 GCC is free software; you can redistribute it and/or modify it under
   8 the terms of the GNU General Public License as published by the Free
   9 Software Foundation; either version 2, or (at your option) any later
  10 version.
  11
  12 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
  13 WARRANTY; without even the implied warranty of MERCHANTABILITY or
  14 FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  15 for more details.
  16
  17 You should have received a copy of the GNU General Public License
  18 along with GCC; see the file COPYING.  If not, write to the Free
  19 Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA
  20 02110-1301, USA.  */
  21
  22 /*  Inlining decision heuristics
  23
  24     We separate inlining decisions from the inliner itself and store it
  25     inside callgraph as so called inline plan.  Refer to cgraph.c
  26     documentation about particular representation of inline plans in the
  27     callgraph.
  28
  29     There are three major parts of this file:
  30
  31     cgraph_mark_inline implementation
  32
  33       This function allows to mark given call inline and performs necessary
  34       modifications of cgraph (production of the clones and updating overall
  35       statistics)
  36
  37     inlining heuristics limits
  38
  39       These functions allow to check that particular inlining is allowed
  40       by the limits specified by user (allowed function growth, overall unit
  41       growth and so on).
  42
  43     inlining heuristics
  44
  45       This is implementation of IPA pass aiming to get as much of benefit
  46       from inlining obeying the limits checked above.
  47
  48       The implementation of particular heuristics is separated from
  49       the rest of code to make it easier to replace it with more complicated
  50       implementation in the future.  The rest of inlining code acts as a
  51       library aimed to modify the callgraph and verify that the parameters
  52       on code size growth fits.
  53
  54       To mark given call inline, use cgraph_mark_inline function, the
  55       verification is performed by cgraph_default_inline_p and
  56       cgraph_check_inline_limits.
  57
  58       The heuristics implements simple knapsack style algorithm ordering
  59       all functions by their "profitability" (estimated by code size growth)
  60       and inlining them in priority order.
  61
  62       cgraph_decide_inlining implements heuristics taking whole callgraph
  63       into account, while cgraph_decide_inlining_incrementally considers
  64       only one function at a time and is used in non-unit-at-a-time mode.
  65
  66    The inliner itself is split into several passes:
  67
  68    pass_inline_parameters
  69
  70      This pass computes local properties of functions that are used by inliner:
  71      estimated function body size, whether function is inlinable at all and
  72      stack frame consumption.
  73
  74      Before executing any of inliner passes, this local pass has to be applied
  75      to each function in the callgraph (ie run as subpass of some earlier
  76      IPA pass).  The results are made out of date by any optimization applied
  77      on the function body.
  78
  79    pass_early_inlining
  80
  81      Simple local inlining pass inlining callees into current function.  This
  82      pass makes no global whole compilation unit analysis and this when allowed
  83      to do inlining expanding code size it might result in unbounded growth of
  84      whole unit.
  85
  86      This is the main inlining pass in non-unit-at-a-time.
  87
  88      With unit-at-a-time the pass is run during conversion into SSA form.
  89      Only functions already converted into SSA form are inlined, so the
  90      conversion must happen in topological order on the callgraph (that is
  91      maintained by pass manager).  The functions after inlining are early
  92      optimized so the early inliner sees unoptimized function itself, but
  93      all considered callees are already optimized allowing it to unfold
  94      abstraction penalty on C++ effectively and cheaply.
  95
  96    pass_ipa_early_inlining
  97
  98      With profiling, the early inlining is also necessary to reduce
  99      instrumentation costs on program with high abstraction penalty (doing
 100      many redundant calls).  This can't happen in parallel with early
 101      optimization and profile instrumentation, because we would end up
 102      re-instrumenting already instrumented function bodies we brought in via
 103      inlining.
 104
 105      To avoid this, this pass is executed as IPA pass before profiling.  It is
 106      simple wrapper to pass_early_inlining and ensures first inlining.
 107
 108    pass_ipa_inline
 109
 110      This is the main pass implementing simple greedy algorithm to do inlining
 111      of small functions that results in overall growth of compilation unit and
 112      inlining of functions called once.  The pass compute just so called inline
 113      plan (representation of inlining to be done in callgraph) and unlike early
 114      inlining it is not performing the inlining itself.
 115
 116    pass_apply_inline
 117
 118      This pass performs actual inlining according to pass_ipa_inline on given
 119      function.  Possible the function body before inlining is saved when it is
 120      needed for further inlining later.
 121  */
 122
 123 #include "config.h"
 124 #include "system.h"
 125 #include "coretypes.h"
 126 #include "tm.h"
 127 #include "tree.h"
 128 #include "tree-inline.h"
 129 #include "langhooks.h"
 130 #include "flags.h"
 131 #include "cgraph.h"
 132 #include "diagnostic.h"
 133 #include "timevar.h"
 134 #include "params.h"
 135 #include "fibheap.h"
 136 #include "intl.h"
 137 #include "tree-pass.h"
 138 #include "hashtab.h"
 139 #include "coverage.h"
 140 #include "ggc.h"
 141 #include "tree-flow.h"
 142 #include "rtl.h"
 143
 144 /* Mode incremental inliner operate on:
 145
 146    In ALWAYS_INLINE only functions marked
 147    always_inline are inlined.  This mode is used after detecting cycle during
 148    flattening.
 149
 150    In SIZE mode, only functions that reduce function body size after inlining
 151    are inlined, this is used during early inlining.
 152
 153    In SPEED mode, all small functions are inlined.  This might result in
 154    unbounded growth of compilation unit and is used only in non-unit-at-a-time
 155    mode.
 156
 157    in ALL mode, everything is inlined.  This is used during flattening.  */
 158 enum inlining_mode {
 159   INLINE_NONE = 0,
 160   INLINE_ALWAYS_INLINE,
 161   INLINE_SIZE,
 162   INLINE_SPEED,
 163   INLINE_ALL
 164 };
 165 static bool
 166 cgraph_decide_inlining_incrementally (struct cgraph_node *, enum inlining_mode,
 167                                       int);
 168
 169
 170 /* Statistics we collect about inlining algorithm.  */
 171 static int ncalls_inlined;
 172 static int nfunctions_inlined;
 173 static int overall_insns;
 174 static gcov_type max_count;
 175
 176 /* Estimate size of the function after inlining WHAT into TO.  */
 177
 178 static int
 179 cgraph_estimate_size_after_inlining (int times, struct cgraph_node *to,
 180                                      struct cgraph_node *what)
 181 {
 182   int size;
 183   tree fndecl = what->decl, arg;
 184   int call_insns = PARAM_VALUE (PARAM_INLINE_CALL_COST);
 185
 186   for (arg = DECL_ARGUMENTS (fndecl); arg; arg = TREE_CHAIN (arg))
 187     call_insns += estimate_move_cost (TREE_TYPE (arg));
 188   size = (what->global.insns - call_insns) * times + to->global.insns;
 189   gcc_assert (size >= 0);
 190   return size;
 191 }
 192
 193 /* E is expected to be an edge being inlined.  Clone destination node of
 194    the edge and redirect it to the new clone.
 195    DUPLICATE is used for bookkeeping on whether we are actually creating new
 196    clones or re-using node originally representing out-of-line function call.
 197    */
 198 void
 199 cgraph_clone_inlined_nodes (struct cgraph_edge *e, bool duplicate, bool update_original)
 200 {
 201   HOST_WIDE_INT peak;
 202   if (duplicate)
 203     {
 204       /* We may eliminate the need for out-of-line copy to be output.
 205          In that case just go ahead and re-use it.  */
 206       if (!e->callee->callers->next_caller
 207           && !e->callee->needed
 208           && !cgraph_new_nodes
 209           && flag_unit_at_a_time)
 210         {
 211           gcc_assert (!e->callee->global.inlined_to);
 212           if (DECL_SAVED_TREE (e->callee->decl))
 213             overall_insns -= e->callee->global.insns, nfunctions_inlined++;
 214           duplicate = false;
 215         }
 216       else
 217         {
 218           struct cgraph_node *n;
 219           n = cgraph_clone_node (e->callee, e->count, e->frequency, e->loop_nest,
 220                                  update_original);
 221           cgraph_redirect_edge_callee (e, n);
 222         }
 223     }
 224
 225   if (e->caller->global.inlined_to)
 226     e->callee->global.inlined_to = e->caller->global.inlined_to;
 227   else
 228     e->callee->global.inlined_to = e->caller;
 229   e->callee->global.stack_frame_offset
 230     = e->caller->global.stack_frame_offset + e->caller->local.estimated_self_stack_size;
 231   peak = e->callee->global.stack_frame_offset + e->callee->local.estimated_self_stack_size;
 232   if (e->callee->global.inlined_to->global.estimated_stack_size < peak)
 233     e->callee->global.inlined_to->global.estimated_stack_size = peak;
 234
 235   /* Recursively clone all bodies.  */
 236   for (e = e->callee->callees; e; e = e->next_callee)
 237     if (!e->inline_failed)
 238       cgraph_clone_inlined_nodes (e, duplicate, update_original);
 239 }
 240
 241 /* Mark edge E as inlined and update callgraph accordingly.
 242    UPDATE_ORIGINAL specify whether profile of original function should be
 243    updated. */
 244
 245 void
 246 cgraph_mark_inline_edge (struct cgraph_edge *e, bool update_original)
 247 {
 248   int old_insns = 0, new_insns = 0;
 249   struct cgraph_node *to = NULL, *what;
 250
 251   if (e->callee->inline_decl)
 252     cgraph_redirect_edge_callee (e, cgraph_node (e->callee->inline_decl));
 253
 254   gcc_assert (e->inline_failed);
 255   e->inline_failed = NULL;
 256
 257   if (!e->callee->global.inlined && flag_unit_at_a_time)
 258     DECL_POSSIBLY_INLINED (e->callee->decl) = true;
 259   e->callee->global.inlined = true;
 260
 261   cgraph_clone_inlined_nodes (e, true, update_original);
 262
 263   what = e->callee;
 264
 265   /* Now update size of caller and all functions caller is inlined into.  */
 266   for (;e && !e->inline_failed; e = e->caller->callers)
 267     {
 268       old_insns = e->caller->global.insns;
 269       new_insns = cgraph_estimate_size_after_inlining (1, e->caller,
 270                                                        what);
 271       gcc_assert (new_insns >= 0);
 272       to = e->caller;
 273       to->global.insns = new_insns;
 274     }
 275   gcc_assert (what->global.inlined_to == to);
 276   if (new_insns > old_insns)
 277     overall_insns += new_insns - old_insns;
 278   ncalls_inlined++;
 279 }
 280
 281 /* Mark all calls of EDGE->CALLEE inlined into EDGE->CALLER.
 282    Return following unredirected edge in the list of callers
 283    of EDGE->CALLEE  */
 284
 285 static struct cgraph_edge *
 286 cgraph_mark_inline (struct cgraph_edge *edge)
 287 {
 288   struct cgraph_node *to = edge->caller;
 289   struct cgraph_node *what = edge->callee;
 290   struct cgraph_edge *e, *next;
 291
 292   gcc_assert (!CALL_CANNOT_INLINE_P (edge->call_stmt));
 293   /* Look for all calls, mark them inline and clone recursively
 294      all inlined functions.  */
 295   for (e = what->callers; e; e = next)
 296     {
 297       next = e->next_caller;
 298       if (e->caller == to && e->inline_failed)
 299         {
 300           cgraph_mark_inline_edge (e, true);
 301           if (e == edge)
 302             edge = next;
 303         }
 304     }
 305
 306   return edge;
 307 }
 308
 309 /* Estimate the growth caused by inlining NODE into all callees.  */
 310
 311 static int
 312 cgraph_estimate_growth (struct cgraph_node *node)
 313 {
 314   int growth = 0;
 315   struct cgraph_edge *e;
 316   if (node->global.estimated_growth != INT_MIN)
 317     return node->global.estimated_growth;
 318
 319   for (e = node->callers; e; e = e->next_caller)
 320     if (e->inline_failed)
 321       growth += (cgraph_estimate_size_after_inlining (1, e->caller, node)
 322                  - e->caller->global.insns);
 323
 324   /* ??? Wrong for self recursive functions or cases where we decide to not
 325      inline for different reasons, but it is not big deal as in that case
 326      we will keep the body around, but we will also avoid some inlining.  */
 327   if (!node->needed && !DECL_EXTERNAL (node->decl))
 328     growth -= node->global.insns;
 329
 330   node->global.estimated_growth = growth;
 331   return growth;
 332 }
 333
 334 /* Return false when inlining WHAT into TO is not good idea
 335    as it would cause too large growth of function bodies.
 336    When ONE_ONLY is true, assume that only one call site is going
 337    to be inlined, otherwise figure out how many call sites in
 338    TO calls WHAT and verify that all can be inlined.
 339    */
 340
 341 static bool
 342 cgraph_check_inline_limits (struct cgraph_node *to, struct cgraph_node *what,
 343                             const char **reason, bool one_only)
 344 {
 345   int times = 0;
 346   struct cgraph_edge *e;
 347   int newsize;
 348   int limit;
 349   HOST_WIDE_INT stack_size_limit, inlined_stack;
 350
 351   if (one_only)
 352     times = 1;
 353   else
 354     for (e = to->callees; e; e = e->next_callee)
 355       if (e->callee == what)
 356         times++;
 357
 358   if (to->global.inlined_to)
 359     to = to->global.inlined_to;
 360
 361   /* When inlining large function body called once into small function,
 362      take the inlined function as base for limiting the growth.  */
 363   if (to->local.self_insns > what->local.self_insns)
 364     limit = to->local.self_insns;
 365   else
 366     limit = what->local.self_insns;
 367
 368   limit += limit * PARAM_VALUE (PARAM_LARGE_FUNCTION_GROWTH) / 100;
 369
 370   /* Check the size after inlining against the function limits.  But allow
 371      the function to shrink if it went over the limits by forced inlining.  */
 372   newsize = cgraph_estimate_size_after_inlining (times, to, what);
 373   if (newsize >= to->global.insns
 374       && newsize > PARAM_VALUE (PARAM_LARGE_FUNCTION_INSNS)
 375       && newsize > limit)
 376     {
 377       if (reason)
 378         *reason = N_("--param large-function-growth limit reached");
 379       return false;
 380     }
 381
 382   stack_size_limit = to->local.estimated_self_stack_size;
 383
 384   stack_size_limit += stack_size_limit * PARAM_VALUE (PARAM_STACK_FRAME_GROWTH) / 100;
 385
 386   inlined_stack = (to->global.stack_frame_offset
 387                    + to->local.estimated_self_stack_size
 388                    + what->global.estimated_stack_size);
 389   if (inlined_stack  > stack_size_limit
 390       && inlined_stack > PARAM_VALUE (PARAM_LARGE_STACK_FRAME))
 391     {
 392       if (reason)
 393         *reason = N_("--param large-stack-frame-growth limit reached");
 394       return false;
 395     }
 396   return true;
 397 }
 398
 399 /* Return true when function N is small enough to be inlined.  */
 400
 401 bool
 402 cgraph_default_inline_p (struct cgraph_node *n, const char **reason)
 403 {
 404   tree decl = n->decl;
 405
 406   if (n->inline_decl)
 407     decl = n->inline_decl;
 408   if (!DECL_INLINE (decl))
 409     {
 410       if (reason)
 411         *reason = N_("function not inlinable");
 412       return false;
 413     }
 414
 415   if (!DECL_STRUCT_FUNCTION (decl)->cfg)
 416     {
 417       if (reason)
 418         *reason = N_("function body not available");
 419       return false;
 420     }
 421
 422   if (DECL_DECLARED_INLINE_P (decl))
 423     {
 424       if (n->global.insns >= MAX_INLINE_INSNS_SINGLE)
 425         {
 426           if (reason)
 427             *reason = N_("--param max-inline-insns-single limit reached");
 428           return false;
 429         }
 430     }
 431   else
 432     {
 433       if (n->global.insns >= MAX_INLINE_INSNS_AUTO)
 434         {
 435           if (reason)
 436             *reason = N_("--param max-inline-insns-auto limit reached");
 437           return false;
 438         }
 439     }
 440
 441   return true;
 442 }
 443
 444 /* Return true when inlining WHAT would create recursive inlining.
 445    We call recursive inlining all cases where same function appears more than
 446    once in the single recursion nest path in the inline graph.  */
 447
 448 static bool
 449 cgraph_recursive_inlining_p (struct cgraph_node *to,
 450                              struct cgraph_node *what,
 451                              const char **reason)
 452 {
 453   bool recursive;
 454   if (to->global.inlined_to)
 455     recursive = what->decl == to->global.inlined_to->decl;
 456   else
 457     recursive = what->decl == to->decl;
 458   /* Marking recursive function inline has sane semantic and thus we should
 459      not warn on it.  */
 460   if (recursive && reason)
 461     *reason = (what->local.disregard_inline_limits
 462                ? N_("recursive inlining") : "");
 463   return recursive;
 464 }
 465
 466 /* Return true if the call can be hot.  */
 467 static bool
 468 cgraph_maybe_hot_edge_p (struct cgraph_edge *edge)
 469 {
 470   if (profile_info && flag_branch_probabilities
 471       && (edge->count
 472           <= profile_info->sum_max / PARAM_VALUE (HOT_BB_COUNT_FRACTION)))
 473     return false;
 474   if (lookup_attribute ("cold", DECL_ATTRIBUTES (edge->callee->decl))
 475       || lookup_attribute ("cold", DECL_ATTRIBUTES (edge->caller->decl)))
 476     return false;
 477   if (lookup_attribute ("hot", DECL_ATTRIBUTES (edge->caller->decl)))
 478     return true;
 479   if (flag_guess_branch_prob
 480       && edge->frequency < (CGRAPH_FREQ_MAX
 481                             / PARAM_VALUE (HOT_BB_FREQUENCY_FRACTION)))
 482     return false;
 483   return true;
 484 }
 485
 486 /* A cost model driving the inlining heuristics in a way so the edges with
 487    smallest badness are inlined first.  After each inlining is performed
 488    the costs of all caller edges of nodes affected are recomputed so the
 489    metrics may accurately depend on values such as number of inlinable callers
 490    of the function or function body size.  */
 491
 492 static int
 493 cgraph_edge_badness (struct cgraph_edge *edge)
 494 {
 495   int badness;
 496   int growth =
 497     cgraph_estimate_size_after_inlining (1, edge->caller, edge->callee);
 498
 499   growth -= edge->caller->global.insns;
 500
 501   /* Always prefer inlining saving code size.  */
 502   if (growth <= 0)
 503     badness = INT_MIN - growth;
 504
 505   /* When profiling is available, base priorities -(#calls / growth).
 506      So we optimize for overall number of "executed" inlined calls.  */
 507   else if (max_count)
 508     badness = ((int)((double)edge->count * INT_MIN / max_count)) / growth;
 509
 510   /* When function local profile is available, base priorities on
 511      growth / frequency, so we optimize for overall frequency of inlined
 512      calls.  This is not too accurate since while the call might be frequent
 513      within function, the function itself is infrequent.
 514
 515      Other objective to optimize for is number of different calls inlined.
 516      We add the estimated growth after inlining all functions to biass the
 517      priorities slightly in this direction (so fewer times called functions
 518      of the same size gets priority).  */
 519   else if (flag_guess_branch_prob)
 520     {
 521       int div = edge->frequency * 100 / CGRAPH_FREQ_BASE;
 522       int growth =
 523         cgraph_estimate_size_after_inlining (1, edge->caller, edge->callee);
 524       growth -= edge->caller->global.insns;
 525       badness = growth * 256;
 526
 527       /* Decrease badness if call is nested.  */
 528       /* Compress the range so we don't overflow.  */
 529       if (div > 256)
 530         div = 256 + ceil_log2 (div) - 8;
 531       if (div < 1)
 532         div = 1;
 533       if (badness > 0)
 534         badness /= div;
 535       badness += cgraph_estimate_growth (edge->callee);
 536     }
 537   /* When function local profile is not available or it does not give
 538      useful information (ie frequency is zero), base the cost on
 539      loop nest and overall size growth, so we optimize for overall number
 540      of functions fully inlined in program.  */
 541   else
 542     {
 543       int nest = MIN (edge->loop_nest, 8);
 544       badness = cgraph_estimate_growth (edge->callee) * 256;
 545
 546       /* Decrease badness if call is nested.  */
 547       if (badness > 0)
 548         badness >>= nest;
 549       else
 550         {
 551           badness <<= nest;
 552         }
 553     }
 554   /* Make recursive inlining happen always after other inlining is done.  */
 555   if (cgraph_recursive_inlining_p (edge->caller, edge->callee, NULL))
 556     return badness + 1;
 557   else
 558     return badness;
 559 }
 560
 561 /* Recompute heap nodes for each of caller edge.  */
 562
 563 static void
 564 update_caller_keys (fibheap_t heap, struct cgraph_node *node,
 565                     bitmap updated_nodes)
 566 {
 567   struct cgraph_edge *edge;
 568   const char *failed_reason;
 569
 570   if (!node->local.inlinable || node->local.disregard_inline_limits
 571       || node->global.inlined_to)
 572     return;
 573   if (bitmap_bit_p (updated_nodes, node->uid))
 574     return;
 575   bitmap_set_bit (updated_nodes, node->uid);
 576   node->global.estimated_growth = INT_MIN;
 577
 578   if (!node->local.inlinable)
 579     return;
 580   /* Prune out edges we won't inline into anymore.  */
 581   if (!cgraph_default_inline_p (node, &failed_reason))
 582     {
 583       for (edge = node->callers; edge; edge = edge->next_caller)
 584         if (edge->aux)
 585           {
 586             fibheap_delete_node (heap, (fibnode_t) edge->aux);
 587             edge->aux = NULL;
 588             if (edge->inline_failed)
 589               edge->inline_failed = failed_reason;
 590           }
 591       return;
 592     }
 593
 594   for (edge = node->callers; edge; edge = edge->next_caller)
 595     if (edge->inline_failed)
 596       {
 597         int badness = cgraph_edge_badness (edge);
 598         if (edge->aux)
 599           {
 600             fibnode_t n = (fibnode_t) edge->aux;
 601             gcc_assert (n->data == edge);
 602             if (n->key == badness)
 603               continue;
 604
 605             /* fibheap_replace_key only increase the keys.  */
 606             if (fibheap_replace_key (heap, n, badness))
 607               continue;
 608             fibheap_delete_node (heap, (fibnode_t) edge->aux);
 609           }
 610         edge->aux = fibheap_insert (heap, badness, edge);
 611       }
 612 }
 613
 614 /* Recompute heap nodes for each of caller edges of each of callees.  */
 615
 616 static void
 617 update_callee_keys (fibheap_t heap, struct cgraph_node *node,
 618                     bitmap updated_nodes)
 619 {
 620   struct cgraph_edge *e;
 621   node->global.estimated_growth = INT_MIN;
 622
 623   for (e = node->callees; e; e = e->next_callee)
 624     if (e->inline_failed)
 625       update_caller_keys (heap, e->callee, updated_nodes);
 626     else if (!e->inline_failed)
 627       update_callee_keys (heap, e->callee, updated_nodes);
 628 }
 629
 630 /* Enqueue all recursive calls from NODE into priority queue depending on
 631    how likely we want to recursively inline the call.  */
 632
 633 static void
 634 lookup_recursive_calls (struct cgraph_node *node, struct cgraph_node *where,
 635                         fibheap_t heap)
 636 {
 637   static int priority;
 638   struct cgraph_edge *e;
 639   for (e = where->callees; e; e = e->next_callee)
 640     if (e->callee == node)
 641       {
 642         /* When profile feedback is available, prioritize by expected number
 643            of calls.  Without profile feedback we maintain simple queue
 644            to order candidates via recursive depths.  */
 645         fibheap_insert (heap,
 646                         !max_count ? priority++
 647                         : -(e->count / ((max_count + (1<<24) - 1) / (1<<24))),
 648                         e);
 649       }
 650   for (e = where->callees; e; e = e->next_callee)
 651     if (!e->inline_failed)
 652       lookup_recursive_calls (node, e->callee, heap);
 653 }
 654
 655 /* Decide on recursive inlining: in the case function has recursive calls,
 656    inline until body size reaches given argument.  */
 657
 658 static bool
 659 cgraph_decide_recursive_inlining (struct cgraph_node *node)
 660 {
 661   int limit = PARAM_VALUE (PARAM_MAX_INLINE_INSNS_RECURSIVE_AUTO);
 662   int max_depth = PARAM_VALUE (PARAM_MAX_INLINE_RECURSIVE_DEPTH_AUTO);
 663   int probability = PARAM_VALUE (PARAM_MIN_INLINE_RECURSIVE_PROBABILITY);
 664   fibheap_t heap;
 665   struct cgraph_edge *e;
 666   struct cgraph_node *master_clone, *next;
 667   int depth = 0;
 668   int n = 0;
 669
 670   if (optimize_size)
 671     return false;
 672
 673   if (DECL_DECLARED_INLINE_P (node->decl))
 674     {
 675       limit = PARAM_VALUE (PARAM_MAX_INLINE_INSNS_RECURSIVE);
 676       max_depth = PARAM_VALUE (PARAM_MAX_INLINE_RECURSIVE_DEPTH);
 677     }
 678
 679   /* Make sure that function is small enough to be considered for inlining.  */
 680   if (!max_depth
 681       || cgraph_estimate_size_after_inlining (1, node, node)  >= limit)
 682     return false;
 683   heap = fibheap_new ();
 684   lookup_recursive_calls (node, node, heap);
 685   if (fibheap_empty (heap))
 686     {
 687       fibheap_delete (heap);
 688       return false;
 689     }
 690
 691   if (dump_file)
 692     fprintf (dump_file,
 693              "  Performing recursive inlining on %s\n",
 694              cgraph_node_name (node));
 695
 696   /* We need original clone to copy around.  */
 697   master_clone = cgraph_clone_node (node, node->count, CGRAPH_FREQ_BASE, 1, false);
 698   master_clone->needed = true;
 699   for (e = master_clone->callees; e; e = e->next_callee)
 700     if (!e->inline_failed)
 701       cgraph_clone_inlined_nodes (e, true, false);
 702
 703   /* Do the inlining and update list of recursive call during process.  */
 704   while (!fibheap_empty (heap)
 705          && (cgraph_estimate_size_after_inlining (1, node, master_clone)
 706              <= limit))
 707     {
 708       struct cgraph_edge *curr
 709         = (struct cgraph_edge *) fibheap_extract_min (heap);
 710       struct cgraph_node *cnode;
 711
 712       depth = 1;
 713       for (cnode = curr->caller;
 714            cnode->global.inlined_to; cnode = cnode->callers->caller)
 715         if (node->decl == curr->callee->decl)
 716           depth++;
 717       if (depth > max_depth)
 718         {
 719           if (dump_file)
 720             fprintf (dump_file,
 721                      "   maximal depth reached\n");
 722           continue;
 723         }
 724
 725       if (max_count)
 726         {
 727           if (!cgraph_maybe_hot_edge_p (curr))
 728             {
 729               if (dump_file)
 730                 fprintf (dump_file, "   Not inlining cold call\n");
 731               continue;
 732             }
 733           if (curr->count * 100 / node->count < probability)
 734             {
 735               if (dump_file)
 736                 fprintf (dump_file,
 737                          "   Probability of edge is too small\n");
 738               continue;
 739             }
 740         }
 741
 742       if (dump_file)
 743         {
 744           fprintf (dump_file,
 745                    "   Inlining call of depth %i", depth);
 746           if (node->count)
 747             {
 748               fprintf (dump_file, " called approx. %.2f times per call",
 749                        (double)curr->count / node->count);
 750             }
 751           fprintf (dump_file, "\n");
 752         }
 753       cgraph_redirect_edge_callee (curr, master_clone);
 754       cgraph_mark_inline_edge (curr, false);
 755       lookup_recursive_calls (node, curr->callee, heap);
 756       n++;
 757     }
 758   if (!fibheap_empty (heap) && dump_file)
 759     fprintf (dump_file, "    Recursive inlining growth limit met.\n");
 760
 761   fibheap_delete (heap);
 762   if (dump_file)
 763     fprintf (dump_file,
 764              "\n   Inlined %i times, body grown from %i to %i insns\n", n,
 765              master_clone->global.insns, node->global.insns);
 766
 767   /* Remove master clone we used for inlining.  We rely that clones inlined
 768      into master clone gets queued just before master clone so we don't
 769      need recursion.  */
 770   for (node = cgraph_nodes; node != master_clone;
 771        node = next)
 772     {
 773       next = node->next;
 774       if (node->global.inlined_to == master_clone)
 775         cgraph_remove_node (node);
 776     }
 777   cgraph_remove_node (master_clone);
 778   /* FIXME: Recursive inlining actually reduces number of calls of the
 779      function.  At this place we should probably walk the function and
 780      inline clones and compensate the counts accordingly.  This probably
 781      doesn't matter much in practice.  */
 782   return n > 0;
 783 }
 784
 785 /* Set inline_failed for all callers of given function to REASON.  */
 786
 787 static void
 788 cgraph_set_inline_failed (struct cgraph_node *node, const char *reason)
 789 {
 790   struct cgraph_edge *e;
 791
 792   if (dump_file)
 793     fprintf (dump_file, "Inlining failed: %s\n", reason);
 794   for (e = node->callers; e; e = e->next_caller)
 795     if (e->inline_failed)
 796       e->inline_failed = reason;
 797 }
 798
 799 /* Given whole compilation unit estimate of INSNS, compute how large we can
 800    allow the unit to grow.  */
 801 static int
 802 compute_max_insns (int insns)
 803 {
 804   int max_insns = insns;
 805   if (max_insns < PARAM_VALUE (PARAM_LARGE_UNIT_INSNS))
 806     max_insns = PARAM_VALUE (PARAM_LARGE_UNIT_INSNS);
 807
 808   return ((HOST_WIDEST_INT) max_insns
 809           * (100 + PARAM_VALUE (PARAM_INLINE_UNIT_GROWTH)) / 100);
 810 }
 811
 812 /* We use greedy algorithm for inlining of small functions:
 813    All inline candidates are put into prioritized heap based on estimated
 814    growth of the overall number of instructions and then update the estimates.
 815
 816    INLINED and INLINED_CALEES are just pointers to arrays large enough
 817    to be passed to cgraph_inlined_into and cgraph_inlined_callees.  */
 818
 819 static void
 820 cgraph_decide_inlining_of_small_functions (void)
 821 {
 822   struct cgraph_node *node;
 823   struct cgraph_edge *edge;
 824   const char *failed_reason;
 825   fibheap_t heap = fibheap_new ();
 826   bitmap updated_nodes = BITMAP_ALLOC (NULL);
 827   int min_insns, max_insns;
 828
 829   if (dump_file)
 830     fprintf (dump_file, "\nDeciding on smaller functions:\n");
 831
 832   /* Put all inline candidates into the heap.  */
 833
 834   for (node = cgraph_nodes; node; node = node->next)
 835     {
 836       if (!node->local.inlinable || !node->callers
 837           || node->local.disregard_inline_limits)
 838         continue;
 839       if (dump_file)
 840         fprintf (dump_file, "Considering inline candidate %s.\n", cgraph_node_name (node));
 841
 842       node->global.estimated_growth = INT_MIN;
 843       if (!cgraph_default_inline_p (node, &failed_reason))
 844         {
 845           cgraph_set_inline_failed (node, failed_reason);
 846           continue;
 847         }
 848
 849       for (edge = node->callers; edge; edge = edge->next_caller)
 850         if (edge->inline_failed)
 851           {
 852             gcc_assert (!edge->aux);
 853             edge->aux = fibheap_insert (heap, cgraph_edge_badness (edge), edge);
 854           }
 855     }
 856
 857   max_insns = compute_max_insns (overall_insns);
 858   min_insns = overall_insns;
 859
 860   while (overall_insns <= max_insns
 861          && (edge = (struct cgraph_edge *) fibheap_extract_min (heap)))
 862     {
 863       int old_insns = overall_insns;
 864       struct cgraph_node *where;
 865       int growth =
 866         cgraph_estimate_size_after_inlining (1, edge->caller, edge->callee);
 867
 868       growth -= edge->caller->global.insns;
 869
 870       if (dump_file)
 871         {
 872           fprintf (dump_file,
 873                    "\nConsidering %s with %i insns\n",
 874                    cgraph_node_name (edge->callee),
 875                    edge->callee->global.insns);
 876           fprintf (dump_file,
 877                    " to be inlined into %s\n"
 878                    " Estimated growth after inlined into all callees is %+i insns.\n"
 879                    " Estimated badness is %i, frequency %.2f.\n",
 880                    cgraph_node_name (edge->caller),
 881                    cgraph_estimate_growth (edge->callee),
 882                    cgraph_edge_badness (edge),
 883                    edge->frequency / (double)CGRAPH_FREQ_BASE);
 884           if (edge->count)
 885             fprintf (dump_file," Called "HOST_WIDEST_INT_PRINT_DEC"x\n", edge->count);
 886         }
 887       gcc_assert (edge->aux);
 888       edge->aux = NULL;
 889       if (!edge->inline_failed)
 890         continue;
 891
 892       /* When not having profile info ready we don't weight by any way the
 893          position of call in procedure itself.  This means if call of
 894          function A from function B seems profitable to inline, the recursive
 895          call of function A in inline copy of A in B will look profitable too
 896          and we end up inlining until reaching maximal function growth.  This
 897          is not good idea so prohibit the recursive inlining.
 898
 899          ??? When the frequencies are taken into account we might not need this
 900          restriction.   */
 901       if (!max_count)
 902         {
 903           where = edge->caller;
 904           while (where->global.inlined_to)
 905             {
 906               if (where->decl == edge->callee->decl)
 907                 break;
 908               where = where->callers->caller;
 909             }
 910           if (where->global.inlined_to)
 911             {
 912               edge->inline_failed
 913                 = (edge->callee->local.disregard_inline_limits ? N_("recursive inlining") : "");
 914               if (dump_file)
 915                 fprintf (dump_file, " inline_failed:Recursive inlining performed only for function itself.\n");
 916               continue;
 917             }
 918         }
 919
 920       if ((!cgraph_maybe_hot_edge_p (edge) || optimize_size) && growth > 0)
 921         {
 922           if (!cgraph_recursive_inlining_p (edge->caller, edge->callee,
 923                                             &edge->inline_failed))
 924             {
 925               edge->inline_failed =
 926                 N_("call is unlikely");
 927               if (dump_file)
 928                 fprintf (dump_file, " inline_failed:%s.\n", edge->inline_failed);
 929             }
 930           continue;
 931         }
 932       if (!cgraph_default_inline_p (edge->callee, &edge->inline_failed))
 933         {
 934           if (!cgraph_recursive_inlining_p (edge->caller, edge->callee,
 935                                             &edge->inline_failed))
 936             {
 937               if (dump_file)
 938                 fprintf (dump_file, " inline_failed:%s.\n", edge->inline_failed);
 939             }
 940           continue;
 941         }
 942       if (cgraph_recursive_inlining_p (edge->caller, edge->callee,
 943                                        &edge->inline_failed))
 944         {
 945           where = edge->caller;
 946           if (where->global.inlined_to)
 947             where = where->global.inlined_to;
 948           if (!cgraph_decide_recursive_inlining (where))
 949             continue;
 950           update_callee_keys (heap, where, updated_nodes);
 951         }
 952       else
 953         {
 954           struct cgraph_node *callee;
 955           if (CALL_CANNOT_INLINE_P (edge->call_stmt)
 956               || !cgraph_check_inline_limits (edge->caller, edge->callee,
 957                                               &edge->inline_failed, true))
 958             {
 959               if (dump_file)
 960                 fprintf (dump_file, " Not inlining into %s:%s.\n",
 961                          cgraph_node_name (edge->caller), edge->inline_failed);
 962               continue;
 963             }
 964           callee = edge->callee;
 965           cgraph_mark_inline_edge (edge, true);
 966           update_callee_keys (heap, callee, updated_nodes);
 967         }
 968       where = edge->caller;
 969       if (where->global.inlined_to)
 970         where = where->global.inlined_to;
 971
 972       /* Our profitability metric can depend on local properties
 973          such as number of inlinable calls and size of the function body.
 974          After inlining these properties might change for the function we
 975          inlined into (since it's body size changed) and for the functions
 976          called by function we inlined (since number of it inlinable callers
 977          might change).  */
 978       update_caller_keys (heap, where, updated_nodes);
 979       bitmap_clear (updated_nodes);
 980
 981       if (dump_file)
 982         {
 983           fprintf (dump_file,
 984                    " Inlined into %s which now has %i insns,"
 985                    "net change of %+i insns.\n",
 986                    cgraph_node_name (edge->caller),
 987                    edge->caller->global.insns,
 988                    overall_insns - old_insns);
 989         }
 990       if (min_insns > overall_insns)
 991         {
 992           min_insns = overall_insns;
 993           max_insns = compute_max_insns (min_insns);
 994
 995           if (dump_file)
 996             fprintf (dump_file, "New minimal insns reached: %i\n", min_insns);
 997         }
 998     }
 999   while ((edge = (struct cgraph_edge *) fibheap_extract_min (heap)) != NULL)
1000     {
1001       gcc_assert (edge->aux);
1002       edge->aux = NULL;
1003       if (!edge->callee->local.disregard_inline_limits && edge->inline_failed
1004           && !cgraph_recursive_inlining_p (edge->caller, edge->callee,
1005                                            &edge->inline_failed))
1006         edge->inline_failed = N_("--param inline-unit-growth limit reached");
1007     }
1008   fibheap_delete (heap);
1009   BITMAP_FREE (updated_nodes);
1010 }
1011
1012 /* Decide on the inlining.  We do so in the topological order to avoid
1013    expenses on updating data structures.  */
1014
1015 static unsigned int
1016 cgraph_decide_inlining (void)
1017 {
1018   struct cgraph_node *node;
1019   int nnodes;
1020   struct cgraph_node **order =
1021     XCNEWVEC (struct cgraph_node *, cgraph_n_nodes);
1022   int old_insns = 0;
1023   int i;
1024   int initial_insns = 0;
1025
1026   max_count = 0;
1027   for (node = cgraph_nodes; node; node = node->next)
1028     if (node->analyzed && (node->needed || node->reachable))
1029       {
1030         struct cgraph_edge *e;
1031
1032         initial_insns += node->local.self_insns;
1033         gcc_assert (node->local.self_insns == node->global.insns);
1034         for (e = node->callees; e; e = e->next_callee)
1035           if (max_count < e->count)
1036             max_count = e->count;
1037       }
1038   overall_insns = initial_insns;
1039   gcc_assert (!max_count || (profile_info && flag_branch_probabilities));
1040
1041   nnodes = cgraph_postorder (order);
1042
1043   if (dump_file)
1044     fprintf (dump_file,
1045              "\nDeciding on inlining.  Starting with %i insns.\n",
1046              initial_insns);
1047
1048   for (node = cgraph_nodes; node; node = node->next)
1049     node->aux = 0;
1050
1051   if (dump_file)
1052     fprintf (dump_file, "\nInlining always_inline functions:\n");
1053
1054   /* In the first pass mark all always_inline edges.  Do this with a priority
1055      so none of our later choices will make this impossible.  */
1056   for (i = nnodes - 1; i >= 0; i--)
1057     {
1058       struct cgraph_edge *e, *next;
1059
1060       node = order[i];
1061
1062       /* Handle nodes to be flattened, but don't update overall unit size.  */
1063       if (lookup_attribute ("flatten", DECL_ATTRIBUTES (node->decl)) != NULL)
1064         {
1065           if (dump_file)
1066             fprintf (dump_file,
1067                      "Flattening %s\n", cgraph_node_name (node));
1068           cgraph_decide_inlining_incrementally (node, INLINE_ALL, 0);
1069         }
1070
1071       if (!node->local.disregard_inline_limits)
1072         continue;
1073       if (dump_file)
1074         fprintf (dump_file,
1075                  "\nConsidering %s %i insns (always inline)\n",
1076                  cgraph_node_name (node), node->global.insns);
1077       old_insns = overall_insns;
1078       for (e = node->callers; e; e = next)
1079         {
1080           next = e->next_caller;
1081           if (!e->inline_failed || CALL_CANNOT_INLINE_P (e->call_stmt))
1082             continue;
1083           if (cgraph_recursive_inlining_p (e->caller, e->callee,
1084                                            &e->inline_failed))
1085             continue;
1086           cgraph_mark_inline_edge (e, true);
1087           if (dump_file)
1088             fprintf (dump_file,
1089                      " Inlined into %s which now has %i insns.\n",
1090                      cgraph_node_name (e->caller),
1091                      e->caller->global.insns);
1092         }
1093       /* Inlining self recursive function might introduce new calls to
1094          themselves we didn't see in the loop above.  Fill in the proper
1095          reason why inline failed.  */
1096       for (e = node->callers; e; e = e->next_caller)
1097         if (e->inline_failed)
1098           e->inline_failed = N_("recursive inlining");
1099       if (dump_file)
1100         fprintf (dump_file,
1101                  " Inlined for a net change of %+i insns.\n",
1102                  overall_insns - old_insns);
1103     }
1104
1105   if (!flag_really_no_inline)
1106     cgraph_decide_inlining_of_small_functions ();
1107
1108   if (!flag_really_no_inline
1109       && flag_inline_functions_called_once)
1110     {
1111       if (dump_file)
1112         fprintf (dump_file, "\nDeciding on functions called once:\n");
1113
1114       /* And finally decide what functions are called once.  */
1115
1116       for (i = nnodes - 1; i >= 0; i--)
1117         {
1118           node = order[i];
1119
1120           if (node->callers && !node->callers->next_caller && !node->needed
1121               && node->local.inlinable && node->callers->inline_failed
1122               && !CALL_CANNOT_INLINE_P (node->callers->call_stmt)
1123               && !DECL_EXTERNAL (node->decl) && !DECL_COMDAT (node->decl))
1124             {
1125               if (dump_file)
1126                 {
1127                   fprintf (dump_file,
1128                            "\nConsidering %s %i insns.\n",
1129                            cgraph_node_name (node), node->global.insns);
1130                   fprintf (dump_file,
1131                            " Called once from %s %i insns.\n",
1132                            cgraph_node_name (node->callers->caller),
1133                            node->callers->caller->global.insns);
1134                 }
1135
1136               old_insns = overall_insns;
1137
1138               if (cgraph_check_inline_limits (node->callers->caller, node,
1139                                               NULL, false))
1140                 {
1141                   cgraph_mark_inline (node->callers);
1142                   if (dump_file)
1143                     fprintf (dump_file,
1144                              " Inlined into %s which now has %i insns"
1145                              " for a net change of %+i insns.\n",
1146                              cgraph_node_name (node->callers->caller),
1147                              node->callers->caller->global.insns,
1148                              overall_insns - old_insns);
1149                 }
1150               else
1151                 {
1152                   if (dump_file)
1153                     fprintf (dump_file,
1154                              " Inline limit reached, not inlined.\n");
1155                 }
1156             }
1157         }
1158     }
1159
1160   if (dump_file)
1161     fprintf (dump_file,
1162              "\nInlined %i calls, eliminated %i functions, "
1163              "%i insns turned to %i insns.\n\n",
1164              ncalls_inlined, nfunctions_inlined, initial_insns,
1165              overall_insns);
1166   free (order);
1167   return 0;
1168 }
1169
1170 /* Try to inline edge E from incremental inliner.  MODE specifies mode
1171    of inliner.
1172
1173    We are detecting cycles by storing mode of inliner into cgraph_node last
1174    time we visited it in the recursion.  In general when mode is set, we have
1175    recursive inlining, but as an special case, we want to try harder inline
1176    ALWAYS_INLINE functions: consider callgraph a->b->c->b, with a being
1177    flatten, b being always inline.  Flattening 'a' will collapse
1178    a->b->c before hitting cycle.  To accommodate always inline, we however
1179    need to inline a->b->c->b.
1180
1181    So after hitting cycle first time, we switch into ALWAYS_INLINE mode and
1182    stop inlining only after hitting ALWAYS_INLINE in ALWAY_INLINE mode.  */
1183 static bool
1184 try_inline (struct cgraph_edge *e, enum inlining_mode mode, int depth)
1185 {
1186   struct cgraph_node *callee = e->callee;
1187   enum inlining_mode callee_mode = (enum inlining_mode) (size_t) callee->aux;
1188   bool always_inline = e->callee->local.disregard_inline_limits;
1189
1190   /* We've hit cycle?  */
1191   if (callee_mode)
1192     {
1193       /* It is first time we see it and we are not in ALWAY_INLINE only
1194          mode yet.  and the function in question is always_inline.  */
1195       if (always_inline && mode != INLINE_ALWAYS_INLINE)
1196         {
1197           if (dump_file)
1198             {
1199               indent_to (dump_file, depth);
1200               fprintf (dump_file,
1201                        "Hit cycle in %s, switching to always inline only.\n",
1202                        cgraph_node_name (callee));
1203             }
1204           mode = INLINE_ALWAYS_INLINE;
1205         }
1206       /* Otherwise it is time to give up.  */
1207       else
1208         {
1209           if (dump_file)
1210             {
1211               indent_to (dump_file, depth);
1212               fprintf (dump_file,
1213                        "Not inlining %s into %s to avoid cycle.\n",
1214                        cgraph_node_name (callee),
1215                        cgraph_node_name (e->caller));
1216             }
1217           e->inline_failed = (e->callee->local.disregard_inline_limits
1218                               ? N_("recursive inlining") : "");
1219           return false;
1220         }
1221     }
1222
1223   callee->aux = (void *)(size_t) mode;
1224   if (dump_file)
1225     {
1226       indent_to (dump_file, depth);
1227       fprintf (dump_file, " Inlining %s into %s.\n",
1228                cgraph_node_name (e->callee),
1229                cgraph_node_name (e->caller));
1230     }
1231   if (e->inline_failed)
1232     cgraph_mark_inline (e);
1233
1234   /* In order to fully inline always_inline functions at -O0, we need to
1235      recurse here, since the inlined functions might not be processed by
1236      incremental inlining at all yet.
1237
1238      Also flattening needs to be done recursively.  */
1239
1240   if (!flag_unit_at_a_time || mode == INLINE_ALL || always_inline)
1241     cgraph_decide_inlining_incrementally (e->callee, mode, depth + 1);
1242   callee->aux = (void *)(size_t) callee_mode;
1243   return true;
1244 }
1245
1246 /* Decide on the inlining.  We do so in the topological order to avoid
1247    expenses on updating data structures.
1248    DEPTH is depth of recursion, used only for debug output.  */
1249
1250 static bool
1251 cgraph_decide_inlining_incrementally (struct cgraph_node *node,
1252                                       enum inlining_mode mode,
1253                                       int depth)
1254 {
1255   struct cgraph_edge *e;
1256   bool inlined = false;
1257   const char *failed_reason;
1258   enum inlining_mode old_mode;
1259
1260 #ifdef ENABLE_CHECKING
1261   verify_cgraph_node (node);
1262 #endif
1263
1264   old_mode = (enum inlining_mode) (size_t)node->aux;
1265
1266   if (mode != INLINE_ALWAYS_INLINE
1267       && lookup_attribute ("flatten", DECL_ATTRIBUTES (node->decl)) != NULL)
1268     {
1269       if (dump_file)
1270         {
1271           indent_to (dump_file, depth);
1272           fprintf (dump_file, "Flattening %s\n", cgraph_node_name (node));
1273         }
1274       mode = INLINE_ALL;
1275     }
1276
1277   node->aux = (void *)(size_t) mode;
1278
1279   /* First of all look for always inline functions.  */
1280   for (e = node->callees; e; e = e->next_callee)
1281     {
1282       if (!e->callee->local.disregard_inline_limits
1283           && (mode != INLINE_ALL || !e->callee->local.inlinable))
1284         continue;
1285       if (CALL_CANNOT_INLINE_P (e->call_stmt))
1286         continue;
1287       /* When the edge is already inlined, we just need to recurse into
1288          it in order to fully flatten the leaves.  */
1289       if (!e->inline_failed && mode == INLINE_ALL)
1290         {
1291           inlined |= try_inline (e, mode, depth);
1292           continue;
1293         }
1294       if (dump_file)
1295         {
1296           indent_to (dump_file, depth);
1297           fprintf (dump_file,
1298                    "Considering to always inline inline candidate %s.\n",
1299                    cgraph_node_name (e->callee));
1300         }
1301       if (cgraph_recursive_inlining_p (node, e->callee, &e->inline_failed))
1302         {
1303           if (dump_file)
1304             {
1305               indent_to (dump_file, depth);
1306               fprintf (dump_file, "Not inlining: recursive call.\n");
1307             }
1308           continue;
1309         }
1310       if (gimple_in_ssa_p (DECL_STRUCT_FUNCTION (node->decl))
1311           != gimple_in_ssa_p (DECL_STRUCT_FUNCTION (e->callee->decl)))
1312         {
1313           if (dump_file)
1314             {
1315               indent_to (dump_file, depth);
1316               fprintf (dump_file, "Not inlining: SSA form does not match.\n");
1317             }
1318           continue;
1319         }
1320       if (!DECL_SAVED_TREE (e->callee->decl) && !e->callee->inline_decl)
1321         {
1322           if (dump_file)
1323             {
1324               indent_to (dump_file, depth);
1325               fprintf (dump_file,
1326                        "Not inlining: Function body no longer available.\n");
1327             }
1328           continue;
1329         }
1330       inlined |= try_inline (e, mode, depth);
1331     }
1332
1333   /* Now do the automatic inlining.  */
1334   if (!flag_really_no_inline && mode != INLINE_ALL
1335       && mode != INLINE_ALWAYS_INLINE)
1336     for (e = node->callees; e; e = e->next_callee)
1337       {
1338         if (!e->callee->local.inlinable
1339             || !e->inline_failed
1340             || e->callee->local.disregard_inline_limits)
1341           continue;
1342         if (dump_file)
1343           fprintf (dump_file, "Considering inline candidate %s.\n",
1344                    cgraph_node_name (e->callee));
1345         if (cgraph_recursive_inlining_p (node, e->callee, &e->inline_failed))
1346           {
1347             if (dump_file)
1348               {
1349                 indent_to (dump_file, depth);
1350                 fprintf (dump_file, "Not inlining: recursive call.\n");
1351               }
1352             continue;
1353           }
1354         if (gimple_in_ssa_p (DECL_STRUCT_FUNCTION (node->decl))
1355             != gimple_in_ssa_p (DECL_STRUCT_FUNCTION (e->callee->decl)))
1356           {
1357             if (dump_file)
1358               {
1359                 indent_to (dump_file, depth);
1360                 fprintf (dump_file, "Not inlining: SSA form does not match.\n");
1361               }
1362             continue;
1363           }
1364         /* When the function body would grow and inlining the function won't
1365            eliminate the need for offline copy of the function, don't inline.
1366          */
1367         if (mode == INLINE_SIZE
1368             && (cgraph_estimate_size_after_inlining (1, e->caller, e->callee)
1369                 > e->caller->global.insns)
1370             && cgraph_estimate_growth (e->callee) > 0)
1371           {
1372             if (dump_file)
1373               {
1374                 indent_to (dump_file, depth);
1375                 fprintf (dump_file,
1376                          "Not inlining: code size would grow by %i insns.\n",
1377                          cgraph_estimate_size_after_inlining (1, e->caller,
1378                                                               e->callee)
1379                          - e->caller->global.insns);
1380               }
1381             continue;
1382           }
1383         if (!cgraph_check_inline_limits (node, e->callee, &e->inline_failed,
1384                                         false)
1385             || CALL_CANNOT_INLINE_P (e->call_stmt))
1386           {
1387             if (dump_file)
1388               {
1389                 indent_to (dump_file, depth);
1390                 fprintf (dump_file, "Not inlining: %s.\n", e->inline_failed);
1391               }
1392             continue;
1393           }
1394         if (!DECL_SAVED_TREE (e->callee->decl) && !e->callee->inline_decl)
1395           {
1396             if (dump_file)
1397               {
1398                 indent_to (dump_file, depth);
1399                 fprintf (dump_file,
1400                          "Not inlining: Function body no longer available.\n");
1401               }
1402             continue;
1403           }
1404         if (cgraph_default_inline_p (e->callee, &failed_reason))
1405           inlined |= try_inline (e, mode, depth);
1406         else if (!flag_unit_at_a_time)
1407           e->inline_failed = failed_reason;
1408       }
1409   node->aux = (void *)(size_t) old_mode;
1410   return inlined;
1411 }
1412
1413 /* When inlining shall be performed.  */
1414 static bool
1415 cgraph_gate_inlining (void)
1416 {
1417   return flag_inline_trees;
1418 }
1419
1420 struct tree_opt_pass pass_ipa_inline =
1421 {
1422   "inline",                             /* name */
1423   cgraph_gate_inlining,                 /* gate */
1424   cgraph_decide_inlining,               /* execute */
1425   NULL,                                 /* sub */
1426   NULL,                                 /* next */
1427   0,                                    /* static_pass_number */
1428   TV_INLINE_HEURISTICS,                 /* tv_id */
1429   0,                                    /* properties_required */
1430   PROP_cfg,                             /* properties_provided */
1431   0,                                    /* properties_destroyed */
1432   TODO_remove_functions,                /* todo_flags_finish */
1433   TODO_dump_cgraph | TODO_dump_func
1434   | TODO_remove_functions,              /* todo_flags_finish */
1435   0                                     /* letter */
1436 };
1437
1438 /* Because inlining might remove no-longer reachable nodes, we need to
1439    keep the array visible to garbage collector to avoid reading collected
1440    out nodes.  */
1441 static int nnodes;
1442 static GTY ((length ("nnodes"))) struct cgraph_node **order;
1443
1444 /* Do inlining of small functions.  Doing so early helps profiling and other
1445    passes to be somewhat more effective and avoids some code duplication in
1446    later real inlining pass for testcases with very many function calls.  */
1447 static unsigned int
1448 cgraph_early_inlining (void)
1449 {
1450   struct cgraph_node *node = cgraph_node (current_function_decl);
1451   unsigned int todo = 0;
1452
1453   if (sorrycount || errorcount)
1454     return 0;
1455   if (cgraph_decide_inlining_incrementally (node,
1456                                             flag_unit_at_a_time || optimize_size
1457                                             ? INLINE_SIZE : INLINE_SPEED, 0))
1458     {
1459       timevar_push (TV_INTEGRATION);
1460       todo = optimize_inline_calls (current_function_decl);
1461       timevar_pop (TV_INTEGRATION);
1462     }
1463   return todo;
1464 }
1465
1466 /* When inlining shall be performed.  */
1467 static bool
1468 cgraph_gate_early_inlining (void)
1469 {
1470   return flag_inline_trees && flag_early_inlining;
1471 }
1472
1473 struct tree_opt_pass pass_early_inline =
1474 {
1475   "einline",                            /* name */
1476   cgraph_gate_early_inlining,           /* gate */
1477   cgraph_early_inlining,                /* execute */
1478   NULL,                                 /* sub */
1479   NULL,                                 /* next */
1480   0,                                    /* static_pass_number */
1481   TV_INLINE_HEURISTICS,                 /* tv_id */
1482   0,                                    /* properties_required */
1483   PROP_cfg,                             /* properties_provided */
1484   0,                                    /* properties_destroyed */
1485   0,                                    /* todo_flags_start */
1486   TODO_dump_func,                       /* todo_flags_finish */
1487   0                                     /* letter */
1488 };
1489
1490 /* When inlining shall be performed.  */
1491 static bool
1492 cgraph_gate_ipa_early_inlining (void)
1493 {
1494   return (flag_inline_trees && flag_early_inlining
1495           && (flag_branch_probabilities || flag_test_coverage
1496               || profile_arc_flag));
1497 }
1498
1499 /* IPA pass wrapper for early inlining pass.  We need to run early inlining
1500    before tree profiling so we have stand alone IPA pass for doing so.  */
1501 struct tree_opt_pass pass_ipa_early_inline =
1502 {
1503   "einline_ipa",                        /* name */
1504   cgraph_gate_ipa_early_inlining,       /* gate */
1505   NULL,                                 /* execute */
1506   NULL,                                 /* sub */
1507   NULL,                                 /* next */
1508   0,                                    /* static_pass_number */
1509   TV_INLINE_HEURISTICS,                 /* tv_id */
1510   0,                                    /* properties_required */
1511   PROP_cfg,                             /* properties_provided */
1512   0,                                    /* properties_destroyed */
1513   0,                                    /* todo_flags_start */
1514   TODO_dump_cgraph,                     /* todo_flags_finish */
1515   0                                     /* letter */
1516 };
1517
1518 /* Compute parameters of functions used by inliner.  */
1519 static unsigned int
1520 compute_inline_parameters (void)
1521 {
1522   struct cgraph_node *node = cgraph_node (current_function_decl);
1523
1524   gcc_assert (!node->global.inlined_to);
1525   node->local.estimated_self_stack_size = estimated_stack_frame_size ();
1526   node->global.estimated_stack_size = node->local.estimated_self_stack_size;
1527   node->global.stack_frame_offset = 0;
1528   node->local.inlinable = tree_inlinable_function_p (current_function_decl);
1529   node->local.self_insns = estimate_num_insns (current_function_decl,
1530                                                &eni_inlining_weights);
1531   if (node->local.inlinable)
1532     node->local.disregard_inline_limits
1533       = lang_hooks.tree_inlining.disregard_inline_limits (current_function_decl);
1534   if (flag_really_no_inline && !node->local.disregard_inline_limits)
1535     node->local.inlinable = 0;
1536   /* Inlining characteristics are maintained by the cgraph_mark_inline.  */
1537   node->global.insns = node->local.self_insns;
1538   return 0;
1539 }
1540
1541 /* When inlining shall be performed.  */
1542 static bool
1543 gate_inline_passes (void)
1544 {
1545   return flag_inline_trees;
1546 }
1547
1548 struct tree_opt_pass pass_inline_parameters =
1549 {
1550   NULL,                                 /* name */
1551   gate_inline_passes,                   /* gate */
1552   compute_inline_parameters,            /* execute */
1553   NULL,                                 /* sub */
1554   NULL,                                 /* next */
1555   0,                                    /* static_pass_number */
1556   TV_INLINE_HEURISTICS,                 /* tv_id */
1557   0,                                    /* properties_required */
1558   PROP_cfg,                             /* properties_provided */
1559   0,                                    /* properties_destroyed */
1560   0,                                    /* todo_flags_start */
1561   0,                                    /* todo_flags_finish */
1562   0                                     /* letter */
1563 };
1564
1565 /* Apply inline plan to the function.  */
1566 static unsigned int
1567 apply_inline (void)
1568 {
1569   unsigned int todo = 0;
1570   struct cgraph_edge *e;
1571   struct cgraph_node *node = cgraph_node (current_function_decl);
1572
1573   /* Even when not optimizing, ensure that always_inline functions get inlined.
1574    */
1575   if (!optimize)
1576    cgraph_decide_inlining_incrementally (node, INLINE_SPEED, 0);
1577
1578   /* We might need the body of this function so that we can expand
1579      it inline somewhere else.  */
1580   if (cgraph_preserve_function_body_p (current_function_decl))
1581     save_inline_function_body (node);
1582
1583   for (e = node->callees; e; e = e->next_callee)
1584     if (!e->inline_failed || warn_inline)
1585       break;
1586   if (e)
1587     {
1588       timevar_push (TV_INTEGRATION);
1589       todo = optimize_inline_calls (current_function_decl);
1590       timevar_pop (TV_INTEGRATION);
1591     }
1592   /* In non-unit-at-a-time we must mark all referenced functions as needed.  */
1593   if (!flag_unit_at_a_time)
1594     {
1595       struct cgraph_edge *e;
1596       for (e = node->callees; e; e = e->next_callee)
1597         if (e->callee->analyzed)
1598           cgraph_mark_needed_node (e->callee);
1599     }
1600   return todo | execute_fixup_cfg ();
1601 }
1602
1603 struct tree_opt_pass pass_apply_inline =
1604 {
1605   "apply_inline",                       /* name */
1606   NULL,                                 /* gate */
1607   apply_inline,                         /* execute */
1608   NULL,                                 /* sub */
1609   NULL,                                 /* next */
1610   0,                                    /* static_pass_number */
1611   TV_INLINE_HEURISTICS,                 /* tv_id */
1612   0,                                    /* properties_required */
1613   PROP_cfg,                             /* properties_provided */
1614   0,                                    /* properties_destroyed */
1615   0,                                    /* todo_flags_start */
1616   TODO_dump_func | TODO_verify_flow
1617   | TODO_verify_stmts,                  /* todo_flags_finish */
1618   0                                     /* letter */
1619 };
1620
1621 #include "gt-ipa-inline.h"