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 (cgraph_recursive_inlining_p (edge->caller, edge->callee,
 958                                        &edge->inline_failed))
 959         {
 960           where = edge->caller;
 961           if (where->global.inlined_to)
 962             where = where->global.inlined_to;
 963           if (!cgraph_decide_recursive_inlining (where))
 964             continue;
 965           update_callee_keys (heap, where, updated_nodes);
 966         }
 967       else
 968         {
 969           struct cgraph_node *callee;
 970           if (CALL_STMT_CANNOT_INLINE_P (edge->call_stmt)
 971               || !cgraph_check_inline_limits (edge->caller, edge->callee,
 972                                               &edge->inline_failed, true))
 973             {
 974               if (dump_file)
 975                 fprintf (dump_file, " Not inlining into %s:%s.\n",
 976                          cgraph_node_name (edge->caller), edge->inline_failed);
 977               continue;
 978             }
 979           callee = edge->callee;
 980           cgraph_mark_inline_edge (edge, true);
 981           update_callee_keys (heap, callee, updated_nodes);
 982         }
 983       where = edge->caller;
 984       if (where->global.inlined_to)
 985         where = where->global.inlined_to;
 986
 987       /* Our profitability metric can depend on local properties
 988          such as number of inlinable calls and size of the function body.
 989          After inlining these properties might change for the function we
 990          inlined into (since it's body size changed) and for the functions
 991          called by function we inlined (since number of it inlinable callers
 992          might change).  */
 993       update_caller_keys (heap, where, updated_nodes);
 994       bitmap_clear (updated_nodes);
 995
 996       if (dump_file)
 997         {
 998           fprintf (dump_file,
 999                    " Inlined into %s which now has %i insns,"
1000                    "net change of %+i insns.\n",
1001                    cgraph_node_name (edge->caller),
1002                    edge->caller->global.insns,
1003                    overall_insns - old_insns);
1004         }
1005       if (min_insns > overall_insns)
1006         {
1007           min_insns = overall_insns;
1008           max_insns = compute_max_insns (min_insns);
1009
1010           if (dump_file)
1011             fprintf (dump_file, "New minimal insns reached: %i\n", min_insns);
1012         }
1013     }
1014   while ((edge = (struct cgraph_edge *) fibheap_extract_min (heap)) != NULL)
1015     {
1016       gcc_assert (edge->aux);
1017       edge->aux = NULL;
1018       if (!edge->callee->local.disregard_inline_limits && edge->inline_failed
1019           && !cgraph_recursive_inlining_p (edge->caller, edge->callee,
1020                                            &edge->inline_failed))
1021         edge->inline_failed = N_("--param inline-unit-growth limit reached");
1022     }
1023   fibheap_delete (heap);
1024   BITMAP_FREE (updated_nodes);
1025 }
1026
1027 /* Decide on the inlining.  We do so in the topological order to avoid
1028    expenses on updating data structures.  */
1029
1030 static unsigned int
1031 cgraph_decide_inlining (void)
1032 {
1033   struct cgraph_node *node;
1034   int nnodes;
1035   struct cgraph_node **order =
1036     XCNEWVEC (struct cgraph_node *, cgraph_n_nodes);
1037   int old_insns = 0;
1038   int i;
1039   int initial_insns = 0;
1040
1041   max_count = 0;
1042   for (node = cgraph_nodes; node; node = node->next)
1043     if (node->analyzed && (node->needed || node->reachable))
1044       {
1045         struct cgraph_edge *e;
1046
1047         initial_insns += inline_summary (node)->self_insns;
1048         gcc_assert (inline_summary (node)->self_insns == node->global.insns);
1049         for (e = node->callees; e; e = e->next_callee)
1050           if (max_count < e->count)
1051             max_count = e->count;
1052       }
1053   overall_insns = initial_insns;
1054   gcc_assert (!max_count || (profile_info && flag_branch_probabilities));
1055
1056   nnodes = cgraph_postorder (order);
1057
1058   if (dump_file)
1059     fprintf (dump_file,
1060              "\nDeciding on inlining.  Starting with %i insns.\n",
1061              initial_insns);
1062
1063   for (node = cgraph_nodes; node; node = node->next)
1064     node->aux = 0;
1065
1066   if (dump_file)
1067     fprintf (dump_file, "\nInlining always_inline functions:\n");
1068
1069   /* In the first pass mark all always_inline edges.  Do this with a priority
1070      so none of our later choices will make this impossible.  */
1071   for (i = nnodes - 1; i >= 0; i--)
1072     {
1073       struct cgraph_edge *e, *next;
1074
1075       node = order[i];
1076
1077       /* Handle nodes to be flattened, but don't update overall unit size.  */
1078       if (lookup_attribute ("flatten", DECL_ATTRIBUTES (node->decl)) != NULL)
1079         {
1080           if (dump_file)
1081             fprintf (dump_file,
1082                      "Flattening %s\n", cgraph_node_name (node));
1083           cgraph_decide_inlining_incrementally (node, INLINE_ALL, 0);
1084         }
1085
1086       if (!node->local.disregard_inline_limits)
1087         continue;
1088       if (dump_file)
1089         fprintf (dump_file,
1090                  "\nConsidering %s %i insns (always inline)\n",
1091                  cgraph_node_name (node), node->global.insns);
1092       old_insns = overall_insns;
1093       for (e = node->callers; e; e = next)
1094         {
1095           next = e->next_caller;
1096           if (!e->inline_failed || CALL_STMT_CANNOT_INLINE_P (e->call_stmt))
1097             continue;
1098           if (cgraph_recursive_inlining_p (e->caller, e->callee,
1099                                            &e->inline_failed))
1100             continue;
1101           cgraph_mark_inline_edge (e, true);
1102           if (dump_file)
1103             fprintf (dump_file,
1104                      " Inlined into %s which now has %i insns.\n",
1105                      cgraph_node_name (e->caller),
1106                      e->caller->global.insns);
1107         }
1108       /* Inlining self recursive function might introduce new calls to
1109          themselves we didn't see in the loop above.  Fill in the proper
1110          reason why inline failed.  */
1111       for (e = node->callers; e; e = e->next_caller)
1112         if (e->inline_failed)
1113           e->inline_failed = N_("recursive inlining");
1114       if (dump_file)
1115         fprintf (dump_file,
1116                  " Inlined for a net change of %+i insns.\n",
1117                  overall_insns - old_insns);
1118     }
1119
1120   if (!flag_really_no_inline)
1121     cgraph_decide_inlining_of_small_functions ();
1122
1123   if (!flag_really_no_inline
1124       && flag_inline_functions_called_once)
1125     {
1126       if (dump_file)
1127         fprintf (dump_file, "\nDeciding on functions called once:\n");
1128
1129       /* And finally decide what functions are called once.  */
1130
1131       for (i = nnodes - 1; i >= 0; i--)
1132         {
1133           node = order[i];
1134
1135           if (node->callers && !node->callers->next_caller && !node->needed
1136               && node->local.inlinable && node->callers->inline_failed
1137               && !CALL_STMT_CANNOT_INLINE_P (node->callers->call_stmt)
1138               && !DECL_EXTERNAL (node->decl) && !DECL_COMDAT (node->decl))
1139             {
1140               if (dump_file)
1141                 {
1142                   fprintf (dump_file,
1143                            "\nConsidering %s %i insns.\n",
1144                            cgraph_node_name (node), node->global.insns);
1145                   fprintf (dump_file,
1146                            " Called once from %s %i insns.\n",
1147                            cgraph_node_name (node->callers->caller),
1148                            node->callers->caller->global.insns);
1149                 }
1150
1151               old_insns = overall_insns;
1152
1153               if (cgraph_check_inline_limits (node->callers->caller, node,
1154                                               NULL, false))
1155                 {
1156                   cgraph_mark_inline (node->callers);
1157                   if (dump_file)
1158                     fprintf (dump_file,
1159                              " Inlined into %s which now has %i insns"
1160                              " for a net change of %+i insns.\n",
1161                              cgraph_node_name (node->callers->caller),
1162                              node->callers->caller->global.insns,
1163                              overall_insns - old_insns);
1164                 }
1165               else
1166                 {
1167                   if (dump_file)
1168                     fprintf (dump_file,
1169                              " Inline limit reached, not inlined.\n");
1170                 }
1171             }
1172         }
1173     }
1174
1175   if (dump_file)
1176     fprintf (dump_file,
1177              "\nInlined %i calls, eliminated %i functions, "
1178              "%i insns turned to %i insns.\n\n",
1179              ncalls_inlined, nfunctions_inlined, initial_insns,
1180              overall_insns);
1181   free (order);
1182   return 0;
1183 }
1184
1185 /* Try to inline edge E from incremental inliner.  MODE specifies mode
1186    of inliner.
1187
1188    We are detecting cycles by storing mode of inliner into cgraph_node last
1189    time we visited it in the recursion.  In general when mode is set, we have
1190    recursive inlining, but as an special case, we want to try harder inline
1191    ALWAYS_INLINE functions: consider callgraph a->b->c->b, with a being
1192    flatten, b being always inline.  Flattening 'a' will collapse
1193    a->b->c before hitting cycle.  To accommodate always inline, we however
1194    need to inline a->b->c->b.
1195
1196    So after hitting cycle first time, we switch into ALWAYS_INLINE mode and
1197    stop inlining only after hitting ALWAYS_INLINE in ALWAY_INLINE mode.  */
1198 static bool
1199 try_inline (struct cgraph_edge *e, enum inlining_mode mode, int depth)
1200 {
1201   struct cgraph_node *callee = e->callee;
1202   enum inlining_mode callee_mode = (enum inlining_mode) (size_t) callee->aux;
1203   bool always_inline = e->callee->local.disregard_inline_limits;
1204
1205   /* We've hit cycle?  */
1206   if (callee_mode)
1207     {
1208       /* It is first time we see it and we are not in ALWAY_INLINE only
1209          mode yet.  and the function in question is always_inline.  */
1210       if (always_inline && mode != INLINE_ALWAYS_INLINE)
1211         {
1212           if (dump_file)
1213             {
1214               indent_to (dump_file, depth);
1215               fprintf (dump_file,
1216                        "Hit cycle in %s, switching to always inline only.\n",
1217                        cgraph_node_name (callee));
1218             }
1219           mode = INLINE_ALWAYS_INLINE;
1220         }
1221       /* Otherwise it is time to give up.  */
1222       else
1223         {
1224           if (dump_file)
1225             {
1226               indent_to (dump_file, depth);
1227               fprintf (dump_file,
1228                        "Not inlining %s into %s to avoid cycle.\n",
1229                        cgraph_node_name (callee),
1230                        cgraph_node_name (e->caller));
1231             }
1232           e->inline_failed = (e->callee->local.disregard_inline_limits
1233                               ? N_("recursive inlining") : "");
1234           return false;
1235         }
1236     }
1237
1238   callee->aux = (void *)(size_t) mode;
1239   if (dump_file)
1240     {
1241       indent_to (dump_file, depth);
1242       fprintf (dump_file, " Inlining %s into %s.\n",
1243                cgraph_node_name (e->callee),
1244                cgraph_node_name (e->caller));
1245     }
1246   if (e->inline_failed)
1247     cgraph_mark_inline (e);
1248
1249   /* In order to fully inline always_inline functions at -O0, we need to
1250      recurse here, since the inlined functions might not be processed by
1251      incremental inlining at all yet.
1252
1253      Also flattening needs to be done recursively.  */
1254
1255   if (!flag_unit_at_a_time || mode == INLINE_ALL || always_inline)
1256     cgraph_decide_inlining_incrementally (e->callee, mode, depth + 1);
1257   callee->aux = (void *)(size_t) callee_mode;
1258   return true;
1259 }
1260
1261 /* Decide on the inlining.  We do so in the topological order to avoid
1262    expenses on updating data structures.
1263    DEPTH is depth of recursion, used only for debug output.  */
1264
1265 static bool
1266 cgraph_decide_inlining_incrementally (struct cgraph_node *node,
1267                                       enum inlining_mode mode,
1268                                       int depth)
1269 {
1270   struct cgraph_edge *e;
1271   bool inlined = false;
1272   const char *failed_reason;
1273   enum inlining_mode old_mode;
1274
1275 #ifdef ENABLE_CHECKING
1276   verify_cgraph_node (node);
1277 #endif
1278
1279   old_mode = (enum inlining_mode) (size_t)node->aux;
1280
1281   if (mode != INLINE_ALWAYS_INLINE
1282       && lookup_attribute ("flatten", DECL_ATTRIBUTES (node->decl)) != NULL)
1283     {
1284       if (dump_file)
1285         {
1286           indent_to (dump_file, depth);
1287           fprintf (dump_file, "Flattening %s\n", cgraph_node_name (node));
1288         }
1289       mode = INLINE_ALL;
1290     }
1291
1292   node->aux = (void *)(size_t) mode;
1293
1294   /* First of all look for always inline functions.  */
1295   for (e = node->callees; e; e = e->next_callee)
1296     {
1297       if (!e->callee->local.disregard_inline_limits
1298           && (mode != INLINE_ALL || !e->callee->local.inlinable))
1299         continue;
1300       if (CALL_STMT_CANNOT_INLINE_P (e->call_stmt))
1301         continue;
1302       /* When the edge is already inlined, we just need to recurse into
1303          it in order to fully flatten the leaves.  */
1304       if (!e->inline_failed && mode == INLINE_ALL)
1305         {
1306           inlined |= try_inline (e, mode, depth);
1307           continue;
1308         }
1309       if (dump_file)
1310         {
1311           indent_to (dump_file, depth);
1312           fprintf (dump_file,
1313                    "Considering to always inline inline candidate %s.\n",
1314                    cgraph_node_name (e->callee));
1315         }
1316       if (cgraph_recursive_inlining_p (node, e->callee, &e->inline_failed))
1317         {
1318           if (dump_file)
1319             {
1320               indent_to (dump_file, depth);
1321               fprintf (dump_file, "Not inlining: recursive call.\n");
1322             }
1323           continue;
1324         }
1325       if (gimple_in_ssa_p (DECL_STRUCT_FUNCTION (node->decl))
1326           != gimple_in_ssa_p (DECL_STRUCT_FUNCTION (e->callee->decl)))
1327         {
1328           if (dump_file)
1329             {
1330               indent_to (dump_file, depth);
1331               fprintf (dump_file, "Not inlining: SSA form does not match.\n");
1332             }
1333           continue;
1334         }
1335       if (!DECL_SAVED_TREE (e->callee->decl) && !e->callee->inline_decl)
1336         {
1337           if (dump_file)
1338             {
1339               indent_to (dump_file, depth);
1340               fprintf (dump_file,
1341                        "Not inlining: Function body no longer available.\n");
1342             }
1343           continue;
1344         }
1345       inlined |= try_inline (e, mode, depth);
1346     }
1347
1348   /* Now do the automatic inlining.  */
1349   if (!flag_really_no_inline && mode != INLINE_ALL
1350       && mode != INLINE_ALWAYS_INLINE)
1351     for (e = node->callees; e; e = e->next_callee)
1352       {
1353         if (!e->callee->local.inlinable
1354             || !e->inline_failed
1355             || e->callee->local.disregard_inline_limits)
1356           continue;
1357         if (dump_file)
1358           fprintf (dump_file, "Considering inline candidate %s.\n",
1359                    cgraph_node_name (e->callee));
1360         if (cgraph_recursive_inlining_p (node, e->callee, &e->inline_failed))
1361           {
1362             if (dump_file)
1363               {
1364                 indent_to (dump_file, depth);
1365                 fprintf (dump_file, "Not inlining: recursive call.\n");
1366               }
1367             continue;
1368           }
1369         if (gimple_in_ssa_p (DECL_STRUCT_FUNCTION (node->decl))
1370             != gimple_in_ssa_p (DECL_STRUCT_FUNCTION (e->callee->decl)))
1371           {
1372             if (dump_file)
1373               {
1374                 indent_to (dump_file, depth);
1375                 fprintf (dump_file, "Not inlining: SSA form does not match.\n");
1376               }
1377             continue;
1378           }
1379         /* When the function body would grow and inlining the function won't
1380            eliminate the need for offline copy of the function, don't inline.
1381          */
1382         if ((mode == INLINE_SIZE
1383              || (!flag_inline_functions
1384                  && !DECL_DECLARED_INLINE_P (e->callee->decl)))
1385             && (cgraph_estimate_size_after_inlining (1, e->caller, e->callee)
1386                 > e->caller->global.insns)
1387             && cgraph_estimate_growth (e->callee) > 0)
1388           {
1389             if (dump_file)
1390               {
1391                 indent_to (dump_file, depth);
1392                 fprintf (dump_file,
1393                          "Not inlining: code size would grow by %i insns.\n",
1394                          cgraph_estimate_size_after_inlining (1, e->caller,
1395                                                               e->callee)
1396                          - e->caller->global.insns);
1397               }
1398             continue;
1399           }
1400         if (!cgraph_check_inline_limits (node, e->callee, &e->inline_failed,
1401                                         false)
1402             || CALL_STMT_CANNOT_INLINE_P (e->call_stmt))
1403           {
1404             if (dump_file)
1405               {
1406                 indent_to (dump_file, depth);
1407                 fprintf (dump_file, "Not inlining: %s.\n", e->inline_failed);
1408               }
1409             continue;
1410           }
1411         if (!DECL_SAVED_TREE (e->callee->decl) && !e->callee->inline_decl)
1412           {
1413             if (dump_file)
1414               {
1415                 indent_to (dump_file, depth);
1416                 fprintf (dump_file,
1417                          "Not inlining: Function body no longer available.\n");
1418               }
1419             continue;
1420           }
1421         if (cgraph_default_inline_p (e->callee, &failed_reason))
1422           inlined |= try_inline (e, mode, depth);
1423         else if (!flag_unit_at_a_time)
1424           e->inline_failed = failed_reason;
1425       }
1426   node->aux = (void *)(size_t) old_mode;
1427   return inlined;
1428 }
1429
1430 /* When inlining shall be performed.  */
1431 static bool
1432 cgraph_gate_inlining (void)
1433 {
1434   return flag_inline_trees;
1435 }
1436
1437 /* Because inlining might remove no-longer reachable nodes, we need to
1438    keep the array visible to garbage collector to avoid reading collected
1439    out nodes.  */
1440 static int nnodes;
1441 static GTY ((length ("nnodes"))) struct cgraph_node **order;
1442
1443 /* Do inlining of small functions.  Doing so early helps profiling and other
1444    passes to be somewhat more effective and avoids some code duplication in
1445    later real inlining pass for testcases with very many function calls.  */
1446 static unsigned int
1447 cgraph_early_inlining (void)
1448 {
1449   struct cgraph_node *node = cgraph_node (current_function_decl);
1450   unsigned int todo = 0;
1451
1452   if (sorrycount || errorcount)
1453     return 0;
1454   if (cgraph_decide_inlining_incrementally (node,
1455                                             flag_unit_at_a_time || optimize_size
1456                                             ? INLINE_SIZE : INLINE_SPEED, 0))
1457     {
1458       timevar_push (TV_INTEGRATION);
1459       todo = optimize_inline_calls (current_function_decl);
1460       timevar_pop (TV_INTEGRATION);
1461     }
1462   return todo;
1463 }
1464
1465 /* When inlining shall be performed.  */
1466 static bool
1467 cgraph_gate_early_inlining (void)
1468 {
1469   return flag_inline_trees && flag_early_inlining;
1470 }
1471
1472 struct gimple_opt_pass pass_early_inline =
1473 {
1474  {
1475   GIMPLE_PASS,
1476   "einline",                            /* name */
1477   cgraph_gate_early_inlining,           /* gate */
1478   cgraph_early_inlining,                /* execute */
1479   NULL,                                 /* sub */
1480   NULL,                                 /* next */
1481   0,                                    /* static_pass_number */
1482   TV_INLINE_HEURISTICS,                 /* tv_id */
1483   0,                                    /* properties_required */
1484   PROP_cfg,                             /* properties_provided */
1485   0,                                    /* properties_destroyed */
1486   0,                                    /* todo_flags_start */
1487   TODO_dump_func                        /* todo_flags_finish */
1488  }
1489 };
1490
1491 /* When inlining shall be performed.  */
1492 static bool
1493 cgraph_gate_ipa_early_inlining (void)
1494 {
1495   return (flag_inline_trees && flag_early_inlining
1496           && (flag_branch_probabilities || flag_test_coverage
1497               || profile_arc_flag));
1498 }
1499
1500 /* IPA pass wrapper for early inlining pass.  We need to run early inlining
1501    before tree profiling so we have stand alone IPA pass for doing so.  */
1502 struct simple_ipa_opt_pass pass_ipa_early_inline =
1503 {
1504  {
1505   SIMPLE_IPA_PASS,
1506   "einline_ipa",                        /* name */
1507   cgraph_gate_ipa_early_inlining,       /* gate */
1508   NULL,                                 /* execute */
1509   NULL,                                 /* sub */
1510   NULL,                                 /* next */
1511   0,                                    /* static_pass_number */
1512   TV_INLINE_HEURISTICS,                 /* tv_id */
1513   0,                                    /* properties_required */
1514   PROP_cfg,                             /* properties_provided */
1515   0,                                    /* properties_destroyed */
1516   0,                                    /* todo_flags_start */
1517   TODO_dump_cgraph                      /* todo_flags_finish */
1518  }
1519 };
1520
1521 /* Compute parameters of functions used by inliner.  */
1522 unsigned int
1523 compute_inline_parameters (struct cgraph_node *node)
1524 {
1525   gcc_assert (!node->global.inlined_to);
1526   inline_summary (node)->estimated_self_stack_size
1527     = estimated_stack_frame_size ();
1528   node->global.estimated_stack_size
1529     = inline_summary (node)->estimated_self_stack_size;
1530   node->global.stack_frame_offset = 0;
1531   node->local.inlinable = tree_inlinable_function_p (current_function_decl);
1532   inline_summary (node)->self_insns = estimate_num_insns (current_function_decl,
1533                                                           &eni_inlining_weights);
1534   if (node->local.inlinable && !node->local.disregard_inline_limits)
1535     node->local.disregard_inline_limits
1536       = DECL_DISREGARD_INLINE_LIMITS (current_function_decl);
1537   if (flag_really_no_inline && !node->local.disregard_inline_limits)
1538     node->local.inlinable = 0;
1539   /* Inlining characteristics are maintained by the cgraph_mark_inline.  */
1540   node->global.insns = inline_summary (node)->self_insns;
1541   return 0;
1542 }
1543
1544
1545 /* Compute parameters of functions used by inliner using
1546    current_function_decl.  */
1547 static unsigned int
1548 compute_inline_parameters_for_current (void)
1549 {
1550   compute_inline_parameters (cgraph_node (current_function_decl));
1551   return 0;
1552 }
1553
1554 /* When inlining shall be performed.  */
1555 static bool
1556 gate_inline_passes (void)
1557 {
1558   return flag_inline_trees;
1559 }
1560
1561 struct gimple_opt_pass pass_inline_parameters =
1562 {
1563  {
1564   GIMPLE_PASS,
1565   NULL,                                 /* name */
1566   gate_inline_passes,                   /* gate */
1567   compute_inline_parameters_for_current,/* execute */
1568   NULL,                                 /* sub */
1569   NULL,                                 /* next */
1570   0,                                    /* static_pass_number */
1571   TV_INLINE_HEURISTICS,                 /* tv_id */
1572   0,                                    /* properties_required */
1573   PROP_cfg,                             /* properties_provided */
1574   0,                                    /* properties_destroyed */
1575   0,                                    /* todo_flags_start */
1576   0                                     /* todo_flags_finish */
1577  }
1578 };
1579
1580 /* Note function body size.  */
1581 static void
1582 inline_generate_summary (void)
1583 {
1584   struct cgraph_node **order =
1585     XCNEWVEC (struct cgraph_node *, cgraph_n_nodes);
1586   int nnodes = cgraph_postorder (order);
1587   int i;
1588
1589   for (i = nnodes - 1; i >= 0; i--)
1590     {
1591       struct cgraph_node *node = order[i];
1592
1593       /* Allow possibly removed nodes to be garbage collected.  */
1594       order[i] = NULL;
1595       if (node->analyzed && (node->needed || node->reachable))
1596         {
1597           push_cfun (DECL_STRUCT_FUNCTION (node->decl));
1598           current_function_decl = node->decl;
1599           compute_inline_parameters (node);
1600           pop_cfun ();
1601         }
1602     }
1603
1604   current_function_decl = NULL;
1605   free (order);
1606   return;
1607 }
1608
1609 /* Apply inline plan to function.  */
1610 static unsigned int
1611 inline_transform (struct cgraph_node *node)
1612 {
1613   unsigned int todo = 0;
1614   struct cgraph_edge *e;
1615
1616   /* We might need the body of this function so that we can expand
1617      it inline somewhere else.  */
1618   if (cgraph_preserve_function_body_p (current_function_decl))
1619     save_inline_function_body (node);
1620
1621   for (e = node->callees; e; e = e->next_callee)
1622     if (!e->inline_failed || warn_inline)
1623       break;
1624   if (e)
1625     {
1626       timevar_push (TV_INTEGRATION);
1627       todo = optimize_inline_calls (current_function_decl);
1628       timevar_pop (TV_INTEGRATION);
1629     }
1630   return todo | execute_fixup_cfg ();
1631 }
1632
1633 struct ipa_opt_pass pass_ipa_inline =
1634 {
1635  {
1636   IPA_PASS,
1637   "inline",                             /* name */
1638   cgraph_gate_inlining,                 /* gate */
1639   cgraph_decide_inlining,               /* execute */
1640   NULL,                                 /* sub */
1641   NULL,                                 /* next */
1642   0,                                    /* static_pass_number */
1643   TV_INLINE_HEURISTICS,                 /* tv_id */
1644   0,                                    /* properties_required */
1645   PROP_cfg,                             /* properties_provided */
1646   0,                                    /* properties_destroyed */
1647   TODO_remove_functions,                /* todo_flags_finish */
1648   TODO_dump_cgraph | TODO_dump_func
1649   | TODO_remove_functions               /* todo_flags_finish */
1650  },
1651  inline_generate_summary,               /* generate_summary */
1652  NULL,                                  /* write_summary */
1653  NULL,                                  /* read_summary */
1654  NULL,                                  /* function_read_summary */
1655  0,                                     /* TODOs */
1656  inline_transform,                      /* function_transform */
1657  NULL,                                  /* variable_transform */
1658 };
1659
1660
1661 /* When inlining shall be performed.  */
1662 static bool
1663 cgraph_gate_O0_always_inline (void)
1664 {
1665   return !flag_unit_at_a_time || !flag_inline_trees;
1666 }
1667
1668 static unsigned int
1669 cgraph_O0_always_inline (void)
1670 {
1671   struct cgraph_node *node = cgraph_node (current_function_decl);
1672   unsigned int todo = 0;
1673   bool inlined;
1674
1675   if (sorrycount || errorcount)
1676     return 0;
1677   inlined = cgraph_decide_inlining_incrementally (node, INLINE_SPEED, 0);
1678   /* We might need the body of this function so that we can expand
1679      it inline somewhere else.  */
1680   if (cgraph_preserve_function_body_p (current_function_decl))
1681     save_inline_function_body (node);
1682   if (inlined || warn_inline)
1683     {
1684       timevar_push (TV_INTEGRATION);
1685       todo = optimize_inline_calls (current_function_decl);
1686       timevar_pop (TV_INTEGRATION);
1687     }
1688   /* In non-unit-at-a-time we must mark all referenced functions as needed.  */
1689   if (!flag_unit_at_a_time)
1690     {
1691       struct cgraph_edge *e;
1692       for (e = node->callees; e; e = e->next_callee)
1693         if (e->callee->analyzed)
1694           cgraph_mark_needed_node (e->callee);
1695     }
1696   return todo | execute_fixup_cfg ();
1697 }
1698
1699 struct gimple_opt_pass pass_O0_always_inline =
1700 {
1701  {
1702   GIMPLE_PASS,
1703   "always_inline",                      /* name */
1704   cgraph_gate_O0_always_inline,         /* gate */
1705   cgraph_O0_always_inline,              /* execute */
1706   NULL,                                 /* sub */
1707   NULL,                                 /* next */
1708   0,                                    /* static_pass_number */
1709   TV_INLINE_HEURISTICS,                 /* tv_id */
1710   0,                                    /* properties_required */
1711   PROP_cfg,                             /* properties_provided */
1712   0,                                    /* properties_destroyed */
1713   0,                                    /* todo_flags_start */
1714   TODO_dump_func | TODO_verify_flow
1715   | TODO_verify_stmts                   /* todo_flags_finish */
1716  }
1717 };
1718
1719 #include "gt-ipa-inline.h"