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, 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 = 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, 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 = fibheap_extract_min (heap);
 709       struct cgraph_node *cnode;
 710
 711       depth = 1;
 712       for (cnode = curr->caller;
 713            cnode->global.inlined_to; cnode = cnode->callers->caller)
 714         if (node->decl == curr->callee->decl)
 715           depth++;
 716       if (depth > max_depth)
 717         {
 718           if (dump_file)
 719             fprintf (dump_file,
 720                      "   maximal depth reached\n");
 721           continue;
 722         }
 723
 724       if (max_count)
 725         {
 726           if (!cgraph_maybe_hot_edge_p (curr))
 727             {
 728               if (dump_file)
 729                 fprintf (dump_file, "   Not inlining cold call\n");
 730               continue;
 731             }
 732           if (curr->count * 100 / node->count < probability)
 733             {
 734               if (dump_file)
 735                 fprintf (dump_file,
 736                          "   Probability of edge is too small\n");
 737               continue;
 738             }
 739         }
 740
 741       if (dump_file)
 742         {
 743           fprintf (dump_file,
 744                    "   Inlining call of depth %i", depth);
 745           if (node->count)
 746             {
 747               fprintf (dump_file, " called approx. %.2f times per call",
 748                        (double)curr->count / node->count);
 749             }
 750           fprintf (dump_file, "\n");
 751         }
 752       cgraph_redirect_edge_callee (curr, master_clone);
 753       cgraph_mark_inline_edge (curr, false);
 754       lookup_recursive_calls (node, curr->callee, heap);
 755       n++;
 756     }
 757   if (!fibheap_empty (heap) && dump_file)
 758     fprintf (dump_file, "    Recursive inlining growth limit met.\n");
 759
 760   fibheap_delete (heap);
 761   if (dump_file)
 762     fprintf (dump_file,
 763              "\n   Inlined %i times, body grown from %i to %i insns\n", n,
 764              master_clone->global.insns, node->global.insns);
 765
 766   /* Remove master clone we used for inlining.  We rely that clones inlined
 767      into master clone gets queued just before master clone so we don't
 768      need recursion.  */
 769   for (node = cgraph_nodes; node != master_clone;
 770        node = next)
 771     {
 772       next = node->next;
 773       if (node->global.inlined_to == master_clone)
 774         cgraph_remove_node (node);
 775     }
 776   cgraph_remove_node (master_clone);
 777   /* FIXME: Recursive inlining actually reduces number of calls of the
 778      function.  At this place we should probably walk the function and
 779      inline clones and compensate the counts accordingly.  This probably
 780      doesn't matter much in practice.  */
 781   return n > 0;
 782 }
 783
 784 /* Set inline_failed for all callers of given function to REASON.  */
 785
 786 static void
 787 cgraph_set_inline_failed (struct cgraph_node *node, const char *reason)
 788 {
 789   struct cgraph_edge *e;
 790
 791   if (dump_file)
 792     fprintf (dump_file, "Inlining failed: %s\n", reason);
 793   for (e = node->callers; e; e = e->next_caller)
 794     if (e->inline_failed)
 795       e->inline_failed = reason;
 796 }
 797
 798 /* Given whole compilation unit estimate of INSNS, compute how large we can
 799    allow the unit to grow.  */
 800 static int
 801 compute_max_insns (int insns)
 802 {
 803   int max_insns = insns;
 804   if (max_insns < PARAM_VALUE (PARAM_LARGE_UNIT_INSNS))
 805     max_insns = PARAM_VALUE (PARAM_LARGE_UNIT_INSNS);
 806
 807   return ((HOST_WIDEST_INT) max_insns
 808           * (100 + PARAM_VALUE (PARAM_INLINE_UNIT_GROWTH)) / 100);
 809 }
 810
 811 /* We use greedy algorithm for inlining of small functions:
 812    All inline candidates are put into prioritized heap based on estimated
 813    growth of the overall number of instructions and then update the estimates.
 814
 815    INLINED and INLINED_CALEES are just pointers to arrays large enough
 816    to be passed to cgraph_inlined_into and cgraph_inlined_callees.  */
 817
 818 static void
 819 cgraph_decide_inlining_of_small_functions (void)
 820 {
 821   struct cgraph_node *node;
 822   struct cgraph_edge *edge;
 823   const char *failed_reason;
 824   fibheap_t heap = fibheap_new ();
 825   bitmap updated_nodes = BITMAP_ALLOC (NULL);
 826   int min_insns, max_insns;
 827
 828   if (dump_file)
 829     fprintf (dump_file, "\nDeciding on smaller functions:\n");
 830
 831   /* Put all inline candidates into the heap.  */
 832
 833   for (node = cgraph_nodes; node; node = node->next)
 834     {
 835       if (!node->local.inlinable || !node->callers
 836           || node->local.disregard_inline_limits)
 837         continue;
 838       if (dump_file)
 839         fprintf (dump_file, "Considering inline candidate %s.\n", cgraph_node_name (node));
 840
 841       node->global.estimated_growth = INT_MIN;
 842       if (!cgraph_default_inline_p (node, &failed_reason))
 843         {
 844           cgraph_set_inline_failed (node, failed_reason);
 845           continue;
 846         }
 847
 848       for (edge = node->callers; edge; edge = edge->next_caller)
 849         if (edge->inline_failed)
 850           {
 851             gcc_assert (!edge->aux);
 852             edge->aux = fibheap_insert (heap, cgraph_edge_badness (edge), edge);
 853           }
 854     }
 855
 856   max_insns = compute_max_insns (overall_insns);
 857   min_insns = overall_insns;
 858
 859   while (overall_insns <= max_insns && (edge = fibheap_extract_min (heap)))
 860     {
 861       int old_insns = overall_insns;
 862       struct cgraph_node *where;
 863       int growth =
 864         cgraph_estimate_size_after_inlining (1, edge->caller, edge->callee);
 865
 866       growth -= edge->caller->global.insns;
 867
 868       if (dump_file)
 869         {
 870           fprintf (dump_file,
 871                    "\nConsidering %s with %i insns\n",
 872                    cgraph_node_name (edge->callee),
 873                    edge->callee->global.insns);
 874           fprintf (dump_file,
 875                    " to be inlined into %s\n"
 876                    " Estimated growth after inlined into all callees is %+i insns.\n"
 877                    " Estimated badness is %i, frequency %.2f.\n",
 878                    cgraph_node_name (edge->caller),
 879                    cgraph_estimate_growth (edge->callee),
 880                    cgraph_edge_badness (edge),
 881                    edge->frequency / (double)CGRAPH_FREQ_BASE);
 882           if (edge->count)
 883             fprintf (dump_file," Called "HOST_WIDEST_INT_PRINT_DEC"x\n", edge->count);
 884         }
 885       gcc_assert (edge->aux);
 886       edge->aux = NULL;
 887       if (!edge->inline_failed)
 888         continue;
 889
 890       /* When not having profile info ready we don't weight by any way the
 891          position of call in procedure itself.  This means if call of
 892          function A from function B seems profitable to inline, the recursive
 893          call of function A in inline copy of A in B will look profitable too
 894          and we end up inlining until reaching maximal function growth.  This
 895          is not good idea so prohibit the recursive inlining.
 896
 897          ??? When the frequencies are taken into account we might not need this
 898          restriction.   */
 899       if (!max_count)
 900         {
 901           where = edge->caller;
 902           while (where->global.inlined_to)
 903             {
 904               if (where->decl == edge->callee->decl)
 905                 break;
 906               where = where->callers->caller;
 907             }
 908           if (where->global.inlined_to)
 909             {
 910               edge->inline_failed
 911                 = (edge->callee->local.disregard_inline_limits ? N_("recursive inlining") : "");
 912               if (dump_file)
 913                 fprintf (dump_file, " inline_failed:Recursive inlining performed only for function itself.\n");
 914               continue;
 915             }
 916         }
 917
 918       if ((!cgraph_maybe_hot_edge_p (edge) || optimize_size) && growth > 0)
 919         {
 920           if (!cgraph_recursive_inlining_p (edge->caller, edge->callee,
 921                                             &edge->inline_failed))
 922             {
 923               edge->inline_failed =
 924                 N_("call is unlikely");
 925               if (dump_file)
 926                 fprintf (dump_file, " inline_failed:%s.\n", edge->inline_failed);
 927             }
 928           continue;
 929         }
 930       if (!cgraph_default_inline_p (edge->callee, &edge->inline_failed))
 931         {
 932           if (!cgraph_recursive_inlining_p (edge->caller, edge->callee,
 933                                             &edge->inline_failed))
 934             {
 935               if (dump_file)
 936                 fprintf (dump_file, " inline_failed:%s.\n", edge->inline_failed);
 937             }
 938           continue;
 939         }
 940       if (cgraph_recursive_inlining_p (edge->caller, edge->callee,
 941                                        &edge->inline_failed))
 942         {
 943           where = edge->caller;
 944           if (where->global.inlined_to)
 945             where = where->global.inlined_to;
 946           if (!cgraph_decide_recursive_inlining (where))
 947             continue;
 948           update_callee_keys (heap, where, updated_nodes);
 949         }
 950       else
 951         {
 952           struct cgraph_node *callee;
 953           if (CALL_CANNOT_INLINE_P (edge->call_stmt)
 954               || !cgraph_check_inline_limits (edge->caller, edge->callee,
 955                                               &edge->inline_failed, true))
 956             {
 957               if (dump_file)
 958                 fprintf (dump_file, " Not inlining into %s:%s.\n",
 959                          cgraph_node_name (edge->caller), edge->inline_failed);
 960               continue;
 961             }
 962           callee = edge->callee;
 963           cgraph_mark_inline_edge (edge, true);
 964           update_callee_keys (heap, callee, updated_nodes);
 965         }
 966       where = edge->caller;
 967       if (where->global.inlined_to)
 968         where = where->global.inlined_to;
 969
 970       /* Our profitability metric can depend on local properties
 971          such as number of inlinable calls and size of the function body.
 972          After inlining these properties might change for the function we
 973          inlined into (since it's body size changed) and for the functions
 974          called by function we inlined (since number of it inlinable callers
 975          might change).  */
 976       update_caller_keys (heap, where, updated_nodes);
 977       bitmap_clear (updated_nodes);
 978
 979       if (dump_file)
 980         {
 981           fprintf (dump_file,
 982                    " Inlined into %s which now has %i insns,"
 983                    "net change of %+i insns.\n",
 984                    cgraph_node_name (edge->caller),
 985                    edge->caller->global.insns,
 986                    overall_insns - old_insns);
 987         }
 988       if (min_insns > overall_insns)
 989         {
 990           min_insns = overall_insns;
 991           max_insns = compute_max_insns (min_insns);
 992
 993           if (dump_file)
 994             fprintf (dump_file, "New minimal insns reached: %i\n", min_insns);
 995         }
 996     }
 997   while ((edge = fibheap_extract_min (heap)) != NULL)
 998     {
 999       gcc_assert (edge->aux);
1000       edge->aux = NULL;
1001       if (!edge->callee->local.disregard_inline_limits && edge->inline_failed
1002           && !cgraph_recursive_inlining_p (edge->caller, edge->callee,
1003                                            &edge->inline_failed))
1004         edge->inline_failed = N_("--param inline-unit-growth limit reached");
1005     }
1006   fibheap_delete (heap);
1007   BITMAP_FREE (updated_nodes);
1008 }
1009
1010 /* Decide on the inlining.  We do so in the topological order to avoid
1011    expenses on updating data structures.  */
1012
1013 static unsigned int
1014 cgraph_decide_inlining (void)
1015 {
1016   struct cgraph_node *node;
1017   int nnodes;
1018   struct cgraph_node **order =
1019     XCNEWVEC (struct cgraph_node *, cgraph_n_nodes);
1020   int old_insns = 0;
1021   int i;
1022   int initial_insns = 0;
1023
1024   max_count = 0;
1025   for (node = cgraph_nodes; node; node = node->next)
1026     if (node->analyzed && (node->needed || node->reachable))
1027       {
1028         struct cgraph_edge *e;
1029
1030         initial_insns += node->local.self_insns;
1031         gcc_assert (node->local.self_insns == node->global.insns);
1032         for (e = node->callees; e; e = e->next_callee)
1033           if (max_count < e->count)
1034             max_count = e->count;
1035       }
1036   overall_insns = initial_insns;
1037   gcc_assert (!max_count || (profile_info && flag_branch_probabilities));
1038
1039   nnodes = cgraph_postorder (order);
1040
1041   if (dump_file)
1042     fprintf (dump_file,
1043              "\nDeciding on inlining.  Starting with %i insns.\n",
1044              initial_insns);
1045
1046   for (node = cgraph_nodes; node; node = node->next)
1047     node->aux = 0;
1048
1049   if (dump_file)
1050     fprintf (dump_file, "\nInlining always_inline functions:\n");
1051
1052   /* In the first pass mark all always_inline edges.  Do this with a priority
1053      so none of our later choices will make this impossible.  */
1054   for (i = nnodes - 1; i >= 0; i--)
1055     {
1056       struct cgraph_edge *e, *next;
1057
1058       node = order[i];
1059
1060       /* Handle nodes to be flattened, but don't update overall unit size.  */
1061       if (lookup_attribute ("flatten", DECL_ATTRIBUTES (node->decl)) != NULL)
1062         {
1063           if (dump_file)
1064             fprintf (dump_file,
1065                      "Flattening %s\n", cgraph_node_name (node));
1066           cgraph_decide_inlining_incrementally (node, INLINE_ALL, 0);
1067         }
1068
1069       if (!node->local.disregard_inline_limits)
1070         continue;
1071       if (dump_file)
1072         fprintf (dump_file,
1073                  "\nConsidering %s %i insns (always inline)\n",
1074                  cgraph_node_name (node), node->global.insns);
1075       old_insns = overall_insns;
1076       for (e = node->callers; e; e = next)
1077         {
1078           next = e->next_caller;
1079           if (!e->inline_failed || CALL_CANNOT_INLINE_P (e->call_stmt))
1080             continue;
1081           if (cgraph_recursive_inlining_p (e->caller, e->callee,
1082                                            &e->inline_failed))
1083             continue;
1084           cgraph_mark_inline_edge (e, true);
1085           if (dump_file)
1086             fprintf (dump_file,
1087                      " Inlined into %s which now has %i insns.\n",
1088                      cgraph_node_name (e->caller),
1089                      e->caller->global.insns);
1090         }
1091       /* Inlining self recursive function might introduce new calls to
1092          themselves we didn't see in the loop above.  Fill in the proper
1093          reason why inline failed.  */
1094       for (e = node->callers; e; e = e->next_caller)
1095         if (e->inline_failed)
1096           e->inline_failed = N_("recursive inlining");
1097       if (dump_file)
1098         fprintf (dump_file,
1099                  " Inlined for a net change of %+i insns.\n",
1100                  overall_insns - old_insns);
1101     }
1102
1103   if (!flag_really_no_inline)
1104     cgraph_decide_inlining_of_small_functions ();
1105
1106   if (!flag_really_no_inline
1107       && flag_inline_functions_called_once)
1108     {
1109       if (dump_file)
1110         fprintf (dump_file, "\nDeciding on functions called once:\n");
1111
1112       /* And finally decide what functions are called once.  */
1113
1114       for (i = nnodes - 1; i >= 0; i--)
1115         {
1116           node = order[i];
1117
1118           if (node->callers && !node->callers->next_caller && !node->needed
1119               && node->local.inlinable && node->callers->inline_failed
1120               && !CALL_CANNOT_INLINE_P (node->callers->call_stmt)
1121               && !DECL_EXTERNAL (node->decl) && !DECL_COMDAT (node->decl))
1122             {
1123               if (dump_file)
1124                 {
1125                   fprintf (dump_file,
1126                            "\nConsidering %s %i insns.\n",
1127                            cgraph_node_name (node), node->global.insns);
1128                   fprintf (dump_file,
1129                            " Called once from %s %i insns.\n",
1130                            cgraph_node_name (node->callers->caller),
1131                            node->callers->caller->global.insns);
1132                 }
1133
1134               old_insns = overall_insns;
1135
1136               if (cgraph_check_inline_limits (node->callers->caller, node,
1137                                               NULL, false))
1138                 {
1139                   cgraph_mark_inline (node->callers);
1140                   if (dump_file)
1141                     fprintf (dump_file,
1142                              " Inlined into %s which now has %i insns"
1143                              " for a net change of %+i insns.\n",
1144                              cgraph_node_name (node->callers->caller),
1145                              node->callers->caller->global.insns,
1146                              overall_insns - old_insns);
1147                 }
1148               else
1149                 {
1150                   if (dump_file)
1151                     fprintf (dump_file,
1152                              " Inline limit reached, not inlined.\n");
1153                 }
1154             }
1155         }
1156     }
1157
1158   if (dump_file)
1159     fprintf (dump_file,
1160              "\nInlined %i calls, eliminated %i functions, "
1161              "%i insns turned to %i insns.\n\n",
1162              ncalls_inlined, nfunctions_inlined, initial_insns,
1163              overall_insns);
1164   free (order);
1165   return 0;
1166 }
1167
1168 /* Try to inline edge E from incremental inliner.  MODE specifies mode
1169    of inliner.
1170
1171    We are detecting cycles by storing mode of inliner into cgraph_node last
1172    time we visited it in the recursion.  In general when mode is set, we have
1173    recursive inlining, but as an special case, we want to try harder inline
1174    ALWAYS_INLINE functions: consider callgraph a->b->c->b, with a being
1175    flatten, b being always inline.  Flattening 'a' will collapse
1176    a->b->c before hitting cycle.  To accommodate always inline, we however
1177    need to inline a->b->c->b.
1178
1179    So after hitting cycle first time, we switch into ALWAYS_INLINE mode and
1180    stop inlining only after hitting ALWAYS_INLINE in ALWAY_INLINE mode.  */
1181 static bool
1182 try_inline (struct cgraph_edge *e, enum inlining_mode mode, int depth)
1183 {
1184   struct cgraph_node *callee = e->callee;
1185   enum inlining_mode callee_mode = (size_t) callee->aux;
1186   bool always_inline = e->callee->local.disregard_inline_limits;
1187
1188   /* We've hit cycle?  */
1189   if (callee_mode)
1190     {
1191       /* It is first time we see it and we are not in ALWAY_INLINE only
1192          mode yet.  and the function in question is always_inline.  */
1193       if (always_inline && mode != INLINE_ALWAYS_INLINE)
1194         {
1195           if (dump_file)
1196             {
1197               indent_to (dump_file, depth);
1198               fprintf (dump_file,
1199                        "Hit cycle in %s, switching to always inline only.\n",
1200                        cgraph_node_name (callee));
1201             }
1202           mode = INLINE_ALWAYS_INLINE;
1203         }
1204       /* Otherwise it is time to give up.  */
1205       else
1206         {
1207           if (dump_file)
1208             {
1209               indent_to (dump_file, depth);
1210               fprintf (dump_file,
1211                        "Not inlining %s into %s to avoid cycle.\n",
1212                        cgraph_node_name (callee),
1213                        cgraph_node_name (e->caller));
1214             }
1215           e->inline_failed = (e->callee->local.disregard_inline_limits
1216                               ? N_("recursive inlining") : "");
1217           return false;
1218         }
1219     }
1220
1221   callee->aux = (void *)(size_t) mode;
1222   if (dump_file)
1223     {
1224       indent_to (dump_file, depth);
1225       fprintf (dump_file, " Inlining %s into %s.\n",
1226                cgraph_node_name (e->callee),
1227                cgraph_node_name (e->caller));
1228     }
1229   if (e->inline_failed)
1230     cgraph_mark_inline (e);
1231
1232   /* In order to fully inline always_inline functions at -O0, we need to
1233      recurse here, since the inlined functions might not be processed by
1234      incremental inlining at all yet.
1235
1236      Also flattening needs to be done recursively.  */
1237
1238   if (!flag_unit_at_a_time || mode == INLINE_ALL || always_inline)
1239     cgraph_decide_inlining_incrementally (e->callee, mode, depth + 1);
1240   callee->aux = (void *)(size_t) callee_mode;
1241   return true;
1242 }
1243
1244 /* Decide on the inlining.  We do so in the topological order to avoid
1245    expenses on updating data structures.
1246    DEPTH is depth of recursion, used only for debug output.  */
1247
1248 static bool
1249 cgraph_decide_inlining_incrementally (struct cgraph_node *node,
1250                                       enum inlining_mode mode,
1251                                       int depth)
1252 {
1253   struct cgraph_edge *e;
1254   bool inlined = false;
1255   const char *failed_reason;
1256   enum inlining_mode old_mode;
1257
1258 #ifdef ENABLE_CHECKING
1259   verify_cgraph_node (node);
1260 #endif
1261
1262   old_mode = (size_t)node->aux;
1263
1264   if (mode != INLINE_ALWAYS_INLINE
1265       && lookup_attribute ("flatten", DECL_ATTRIBUTES (node->decl)) != NULL)
1266     {
1267       if (dump_file)
1268         {
1269           indent_to (dump_file, depth);
1270           fprintf (dump_file, "Flattening %s\n", cgraph_node_name (node));
1271         }
1272       mode = INLINE_ALL;
1273     }
1274
1275   node->aux = (void *)(size_t) mode;
1276
1277   /* First of all look for always inline functions.  */
1278   for (e = node->callees; e; e = e->next_callee)
1279     {
1280       if (!e->callee->local.disregard_inline_limits
1281           && (mode != INLINE_ALL || !e->callee->local.inlinable))
1282         continue;
1283       if (CALL_CANNOT_INLINE_P (e->call_stmt))
1284         continue;
1285       /* When the edge is already inlined, we just need to recurse into
1286          it in order to fully flatten the leaves.  */
1287       if (!e->inline_failed && mode == INLINE_ALL)
1288         {
1289           inlined |= try_inline (e, mode, depth);
1290           continue;
1291         }
1292       if (dump_file)
1293         {
1294           indent_to (dump_file, depth);
1295           fprintf (dump_file,
1296                    "Considering to always inline inline candidate %s.\n",
1297                    cgraph_node_name (e->callee));
1298         }
1299       if (cgraph_recursive_inlining_p (node, e->callee, &e->inline_failed))
1300         {
1301           if (dump_file)
1302             {
1303               indent_to (dump_file, depth);
1304               fprintf (dump_file, "Not inlining: recursive call.\n");
1305             }
1306           continue;
1307         }
1308       if (gimple_in_ssa_p (DECL_STRUCT_FUNCTION (node->decl))
1309           != gimple_in_ssa_p (DECL_STRUCT_FUNCTION (e->callee->decl)))
1310         {
1311           if (dump_file)
1312             {
1313               indent_to (dump_file, depth);
1314               fprintf (dump_file, "Not inlining: SSA form does not match.\n");
1315             }
1316           continue;
1317         }
1318       if (!DECL_SAVED_TREE (e->callee->decl) && !e->callee->inline_decl)
1319         {
1320           if (dump_file)
1321             {
1322               indent_to (dump_file, depth);
1323               fprintf (dump_file,
1324                        "Not inlining: Function body no longer available.\n");
1325             }
1326           continue;
1327         }
1328       inlined |= try_inline (e, mode, depth);
1329     }
1330
1331   /* Now do the automatic inlining.  */
1332   if (!flag_really_no_inline && mode != INLINE_ALL
1333       && mode != INLINE_ALWAYS_INLINE)
1334     for (e = node->callees; e; e = e->next_callee)
1335       {
1336         if (!e->callee->local.inlinable
1337             || !e->inline_failed
1338             || e->callee->local.disregard_inline_limits)
1339           continue;
1340         if (dump_file)
1341           fprintf (dump_file, "Considering inline candidate %s.\n",
1342                    cgraph_node_name (e->callee));
1343         if (cgraph_recursive_inlining_p (node, e->callee, &e->inline_failed))
1344           {
1345             if (dump_file)
1346               {
1347                 indent_to (dump_file, depth);
1348                 fprintf (dump_file, "Not inlining: recursive call.\n");
1349               }
1350             continue;
1351           }
1352         if (gimple_in_ssa_p (DECL_STRUCT_FUNCTION (node->decl))
1353             != gimple_in_ssa_p (DECL_STRUCT_FUNCTION (e->callee->decl)))
1354           {
1355             if (dump_file)
1356               {
1357                 indent_to (dump_file, depth);
1358                 fprintf (dump_file, "Not inlining: SSA form does not match.\n");
1359               }
1360             continue;
1361           }
1362         /* When the function body would grow and inlining the function won't
1363            eliminate the need for offline copy of the function, don't inline.
1364          */
1365         if (mode == INLINE_SIZE
1366             && (cgraph_estimate_size_after_inlining (1, e->caller, e->callee)
1367                 > e->caller->global.insns)
1368             && cgraph_estimate_growth (e->callee) > 0)
1369           {
1370             if (dump_file)
1371               {
1372                 indent_to (dump_file, depth);
1373                 fprintf (dump_file,
1374                          "Not inlining: code size would grow by %i insns.\n",
1375                          cgraph_estimate_size_after_inlining (1, e->caller,
1376                                                               e->callee)
1377                          - e->caller->global.insns);
1378               }
1379             continue;
1380           }
1381         if (!cgraph_check_inline_limits (node, e->callee, &e->inline_failed,
1382                                         false)
1383             || CALL_CANNOT_INLINE_P (e->call_stmt))
1384           {
1385             if (dump_file)
1386               {
1387                 indent_to (dump_file, depth);
1388                 fprintf (dump_file, "Not inlining: %s.\n", e->inline_failed);
1389               }
1390             continue;
1391           }
1392         if (!DECL_SAVED_TREE (e->callee->decl) && !e->callee->inline_decl)
1393           {
1394             if (dump_file)
1395               {
1396                 indent_to (dump_file, depth);
1397                 fprintf (dump_file,
1398                          "Not inlining: Function body no longer available.\n");
1399               }
1400             continue;
1401           }
1402         if (cgraph_default_inline_p (e->callee, &failed_reason))
1403           inlined |= try_inline (e, mode, depth);
1404         else if (!flag_unit_at_a_time)
1405           e->inline_failed = failed_reason;
1406       }
1407   node->aux = (void *)(size_t) old_mode;
1408   return inlined;
1409 }
1410
1411 /* When inlining shall be performed.  */
1412 static bool
1413 cgraph_gate_inlining (void)
1414 {
1415   return flag_inline_trees;
1416 }
1417
1418 struct tree_opt_pass pass_ipa_inline =
1419 {
1420   "inline",                             /* name */
1421   cgraph_gate_inlining,                 /* gate */
1422   cgraph_decide_inlining,               /* execute */
1423   NULL,                                 /* sub */
1424   NULL,                                 /* next */
1425   0,                                    /* static_pass_number */
1426   TV_INLINE_HEURISTICS,                 /* tv_id */
1427   0,                                    /* properties_required */
1428   PROP_cfg,                             /* properties_provided */
1429   0,                                    /* properties_destroyed */
1430   TODO_remove_functions,                /* todo_flags_finish */
1431   TODO_dump_cgraph | TODO_dump_func
1432   | TODO_remove_functions,              /* todo_flags_finish */
1433   0                                     /* letter */
1434 };
1435
1436 /* Because inlining might remove no-longer reachable nodes, we need to
1437    keep the array visible to garbage collector to avoid reading collected
1438    out nodes.  */
1439 static int nnodes;
1440 static GTY ((length ("nnodes"))) struct cgraph_node **order;
1441
1442 /* Do inlining of small functions.  Doing so early helps profiling and other
1443    passes to be somewhat more effective and avoids some code duplication in
1444    later real inlining pass for testcases with very many function calls.  */
1445 static unsigned int
1446 cgraph_early_inlining (void)
1447 {
1448   struct cgraph_node *node = cgraph_node (current_function_decl);
1449   unsigned int todo = 0;
1450
1451   if (sorrycount || errorcount)
1452     return 0;
1453   if (cgraph_decide_inlining_incrementally (node,
1454                                             flag_unit_at_a_time || optimize_size
1455                                             ? INLINE_SIZE : INLINE_SPEED, 0))
1456     {
1457       timevar_push (TV_INTEGRATION);
1458       todo = optimize_inline_calls (current_function_decl);
1459       timevar_pop (TV_INTEGRATION);
1460     }
1461   return todo;
1462 }
1463
1464 /* When inlining shall be performed.  */
1465 static bool
1466 cgraph_gate_early_inlining (void)
1467 {
1468   return flag_inline_trees && flag_early_inlining;
1469 }
1470
1471 struct tree_opt_pass pass_early_inline =
1472 {
1473   "einline",                            /* name */
1474   cgraph_gate_early_inlining,           /* gate */
1475   cgraph_early_inlining,                /* execute */
1476   NULL,                                 /* sub */
1477   NULL,                                 /* next */
1478   0,                                    /* static_pass_number */
1479   TV_INLINE_HEURISTICS,                 /* tv_id */
1480   0,                                    /* properties_required */
1481   PROP_cfg,                             /* properties_provided */
1482   0,                                    /* properties_destroyed */
1483   0,                                    /* todo_flags_start */
1484   TODO_dump_func,                       /* todo_flags_finish */
1485   0                                     /* letter */
1486 };
1487
1488 /* When inlining shall be performed.  */
1489 static bool
1490 cgraph_gate_ipa_early_inlining (void)
1491 {
1492   return (flag_inline_trees && flag_early_inlining
1493           && (flag_branch_probabilities || flag_test_coverage
1494               || profile_arc_flag));
1495 }
1496
1497 /* IPA pass wrapper for early inlining pass.  We need to run early inlining
1498    before tree profiling so we have stand alone IPA pass for doing so.  */
1499 struct tree_opt_pass pass_ipa_early_inline =
1500 {
1501   "einline_ipa",                        /* name */
1502   cgraph_gate_ipa_early_inlining,       /* gate */
1503   NULL,                                 /* execute */
1504   NULL,                                 /* sub */
1505   NULL,                                 /* next */
1506   0,                                    /* static_pass_number */
1507   TV_INLINE_HEURISTICS,                 /* tv_id */
1508   0,                                    /* properties_required */
1509   PROP_cfg,                             /* properties_provided */
1510   0,                                    /* properties_destroyed */
1511   0,                                    /* todo_flags_start */
1512   TODO_dump_cgraph,                     /* todo_flags_finish */
1513   0                                     /* letter */
1514 };
1515
1516 /* Compute parameters of functions used by inliner.  */
1517 static unsigned int
1518 compute_inline_parameters (void)
1519 {
1520   struct cgraph_node *node = cgraph_node (current_function_decl);
1521
1522   gcc_assert (!node->global.inlined_to);
1523   node->local.estimated_self_stack_size = estimated_stack_frame_size ();
1524   node->global.estimated_stack_size = node->local.estimated_self_stack_size;
1525   node->global.stack_frame_offset = 0;
1526   node->local.inlinable = tree_inlinable_function_p (current_function_decl);
1527   node->local.self_insns = estimate_num_insns (current_function_decl,
1528                                                &eni_inlining_weights);
1529   if (node->local.inlinable)
1530     node->local.disregard_inline_limits
1531       = lang_hooks.tree_inlining.disregard_inline_limits (current_function_decl);
1532   if (flag_really_no_inline && !node->local.disregard_inline_limits)
1533     node->local.inlinable = 0;
1534   /* Inlining characteristics are maintained by the cgraph_mark_inline.  */
1535   node->global.insns = node->local.self_insns;
1536   return 0;
1537 }
1538
1539 /* When inlining shall be performed.  */
1540 static bool
1541 gate_inline_passes (void)
1542 {
1543   return flag_inline_trees;
1544 }
1545
1546 struct tree_opt_pass pass_inline_parameters =
1547 {
1548   NULL,                                 /* name */
1549   gate_inline_passes,                   /* gate */
1550   compute_inline_parameters,            /* execute */
1551   NULL,                                 /* sub */
1552   NULL,                                 /* next */
1553   0,                                    /* static_pass_number */
1554   TV_INLINE_HEURISTICS,                 /* tv_id */
1555   0,                                    /* properties_required */
1556   PROP_cfg,                             /* properties_provided */
1557   0,                                    /* properties_destroyed */
1558   0,                                    /* todo_flags_start */
1559   0,                                    /* todo_flags_finish */
1560   0                                     /* letter */
1561 };
1562
1563 /* Apply inline plan to the function.  */
1564 static unsigned int
1565 apply_inline (void)
1566 {
1567   unsigned int todo = 0;
1568   struct cgraph_edge *e;
1569   struct cgraph_node *node = cgraph_node (current_function_decl);
1570
1571   /* Even when not optimizing, ensure that always_inline functions get inlined.
1572    */
1573   if (!optimize)
1574    cgraph_decide_inlining_incrementally (node, INLINE_SPEED, 0);
1575
1576   /* We might need the body of this function so that we can expand
1577      it inline somewhere else.  */
1578   if (cgraph_preserve_function_body_p (current_function_decl))
1579     save_inline_function_body (node);
1580
1581   for (e = node->callees; e; e = e->next_callee)
1582     if (!e->inline_failed || warn_inline)
1583       break;
1584   if (e)
1585     {
1586       timevar_push (TV_INTEGRATION);
1587       todo = optimize_inline_calls (current_function_decl);
1588       timevar_pop (TV_INTEGRATION);
1589     }
1590   /* In non-unit-at-a-time we must mark all referenced functions as needed.  */
1591   if (!flag_unit_at_a_time)
1592     {
1593       struct cgraph_edge *e;
1594       for (e = node->callees; e; e = e->next_callee)
1595         if (e->callee->analyzed)
1596           cgraph_mark_needed_node (e->callee);
1597     }
1598   return todo | execute_fixup_cfg ();
1599 }
1600
1601 struct tree_opt_pass pass_apply_inline =
1602 {
1603   "apply_inline",                       /* name */
1604   NULL,                                 /* gate */
1605   apply_inline,                         /* execute */
1606   NULL,                                 /* sub */
1607   NULL,                                 /* next */
1608   0,                                    /* static_pass_number */
1609   TV_INLINE_HEURISTICS,                 /* tv_id */
1610   0,                                    /* properties_required */
1611   PROP_cfg,                             /* properties_provided */
1612   0,                                    /* properties_destroyed */
1613   0,                                    /* todo_flags_start */
1614   TODO_dump_func | TODO_verify_flow
1615   | TODO_verify_stmts,                  /* todo_flags_finish */
1616   0                                     /* letter */
1617 };
1618
1619 #include "gt-ipa-inline.h"