gcc/ipa-inline.c

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