LCOV - code coverage report
Current view: top level - gcc - ipa-inline.cc (source / functions) Coverage Total Hit
Test: gcc.info Lines: 91.1 % 1528 1392
Test Date: 2026-11-14 16:39:50 Functions: 98.2 % 56 55
Legend: Lines:     hit not hit

            Line data    Source code
       1              : /* Inlining decision heuristics.
       2              :    Copyright (C) 2003-2026 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              :     The implementation of inliner is organized as follows:
      24              : 
      25              :     inlining heuristics limits
      26              : 
      27              :       can_inline_edge_p allow to check that particular inlining is allowed
      28              :       by the limits specified by user (allowed function growth, growth and so
      29              :       on).
      30              : 
      31              :       Functions are inlined when it is obvious the result is profitable (such
      32              :       as functions called once or when inlining reduce code size).
      33              :       In addition to that we perform inlining of small functions and recursive
      34              :       inlining.
      35              : 
      36              :     inlining heuristics
      37              : 
      38              :        The inliner itself is split into two passes:
      39              : 
      40              :        pass_early_inlining
      41              : 
      42              :          Simple local inlining pass inlining callees into current function.
      43              :          This pass makes no use of whole unit analysis and thus it can do only
      44              :          very simple decisions based on local properties.
      45              : 
      46              :          The strength of the pass is that it is run in topological order
      47              :          (reverse postorder) on the callgraph. Functions are converted into SSA
      48              :          form just before this pass and optimized subsequently. As a result, the
      49              :          callees of the function seen by the early inliner was already optimized
      50              :          and results of early inlining adds a lot of optimization opportunities
      51              :          for the local optimization.
      52              : 
      53              :          The pass handle the obvious inlining decisions within the compilation
      54              :          unit - inlining auto inline functions, inlining for size and
      55              :          flattening.
      56              : 
      57              :          main strength of the pass is the ability to eliminate abstraction
      58              :          penalty in C++ code (via combination of inlining and early
      59              :          optimization) and thus improve quality of analysis done by real IPA
      60              :          optimizers.
      61              : 
      62              :          Because of lack of whole unit knowledge, the pass cannot really make
      63              :          good code size/performance tradeoffs.  It however does very simple
      64              :          speculative inlining allowing code size to grow by
      65              :          EARLY_INLINING_INSNS when callee is leaf function.  In this case the
      66              :          optimizations performed later are very likely to eliminate the cost.
      67              : 
      68              :        pass_ipa_inline
      69              : 
      70              :          This is the real inliner able to handle inlining with whole program
      71              :          knowledge. It performs following steps:
      72              : 
      73              :          1) inlining of small functions.  This is implemented by greedy
      74              :          algorithm ordering all inlinable cgraph edges by their badness and
      75              :          inlining them in this order as long as inline limits allows doing so.
      76              : 
      77              :          This heuristics is not very good on inlining recursive calls. Recursive
      78              :          calls can be inlined with results similar to loop unrolling. To do so,
      79              :          special purpose recursive inliner is executed on function when
      80              :          recursive edge is met as viable candidate.
      81              : 
      82              :          2) Unreachable functions are removed from callgraph.  Inlining leads
      83              :          to devirtualization and other modification of callgraph so functions
      84              :          may become unreachable during the process. Also functions declared as
      85              :          extern inline or virtual functions are removed, since after inlining
      86              :          we no longer need the offline bodies.
      87              : 
      88              :          3) Functions called once and not exported from the unit are inlined.
      89              :          This should almost always lead to reduction of code size by eliminating
      90              :          the need for offline copy of the function.  */
      91              : 
      92              : #include "config.h"
      93              : #include "system.h"
      94              : #include "coretypes.h"
      95              : #include "backend.h"
      96              : #include "target.h"
      97              : #include "rtl.h"
      98              : #include "tree.h"
      99              : #include "gimple.h"
     100              : #include "alloc-pool.h"
     101              : #include "tree-pass.h"
     102              : #include "gimple-ssa.h"
     103              : #include "cgraph.h"
     104              : #include "lto-streamer.h"
     105              : #include "trans-mem.h"
     106              : #include "calls.h"
     107              : #include "tree-inline.h"
     108              : #include "profile.h"
     109              : #include "symbol-summary.h"
     110              : #include "tree-vrp.h"
     111              : #include "sreal.h"
     112              : #include "ipa-cp.h"
     113              : #include "ipa-prop.h"
     114              : #include "ipa-fnsummary.h"
     115              : #include "ipa-inline.h"
     116              : #include "ipa-utils.h"
     117              : #include "auto-profile.h"
     118              : #include "builtins.h"
     119              : #include "fibonacci_heap.h"
     120              : #include "stringpool.h"
     121              : #include "attribs.h"
     122              : #include "asan.h"
     123              : #include "ipa-strub.h"
     124              : #include "ipa-modref-tree.h"
     125              : #include "ipa-modref.h"
     126              : 
     127              : /* Inliner uses greedy algorithm to inline calls in a priority order.
     128              :    Badness is used as the key in a Fibonacci heap which roughly corresponds
     129              :    to negation of benefit to cost ratios.
     130              :    In case multiple calls has same priority we want to stabilize the outcomes
     131              :    for which we use ids.  */
     132              : class inline_badness
     133              : {
     134              : public:
     135              :   sreal badness;
     136              :   int uid;
     137      1049869 :   inline_badness ()
     138      1049869 :   : badness (sreal::min ()), uid (0)
     139              :   {
     140              :   }
     141      3606948 :   inline_badness (cgraph_edge *e, sreal b)
     142        18514 :   : badness (b), uid (e->get_uid ())
     143              :   {
     144              :   }
     145       936841 :   bool operator<= (const inline_badness &other)
     146              :   {
     147       936841 :     if (badness != other.badness)
     148       936841 :       return badness <= other.badness;
     149            0 :     return uid <= other.uid;
     150              :   }
     151      1049869 :   bool operator== (const inline_badness &other)
     152              :   {
     153      1911302 :     return badness == other.badness && uid == other.uid;
     154              :   }
     155            0 :   bool operator!= (const inline_badness &other)
     156              :   {
     157      1049869 :     return badness != other.badness || uid != other.uid;
     158              :   }
     159     28019112 :   bool operator< (const inline_badness &other)
     160              :   {
     161     28019112 :     if (badness != other.badness)
     162     23957021 :       return badness < other.badness;
     163      4062091 :     return uid < other.uid;
     164              :   }
     165     12788315 :   bool operator> (const inline_badness &other)
     166              :   {
     167     12788315 :     if (badness != other.badness)
     168     10864831 :       return badness > other.badness;
     169      1923484 :     return uid > other.uid;
     170              :   }
     171              : };
     172              : 
     173              : typedef fibonacci_heap <inline_badness, cgraph_edge> edge_heap_t;
     174              : typedef fibonacci_node <inline_badness, cgraph_edge> edge_heap_node_t;
     175              : 
     176              : /* Statistics we collect about inlining algorithm.  */
     177              : static int overall_size;
     178              : static bool has_nonzero_ipa_profile;
     179              : static profile_count spec_rem;
     180              : 
     181              : /* Return false when inlining edge E would lead to violating
     182              :    limits on function unit growth or stack usage growth.
     183              : 
     184              :    The relative function body growth limit is present generally
     185              :    to avoid problems with non-linear behavior of the compiler.
     186              :    To allow inlining huge functions into tiny wrapper, the limit
     187              :    is always based on the bigger of the two functions considered.
     188              : 
     189              :    For stack growth limits we always base the growth in stack usage
     190              :    of the callers.  We want to prevent applications from segfaulting
     191              :    on stack overflow when functions with huge stack frames gets
     192              :    inlined. */
     193              : 
     194              : static bool
     195      6941530 : caller_growth_limits (struct cgraph_edge *e)
     196              : {
     197      6941530 :   struct cgraph_node *to = e->caller;
     198      6941530 :   struct cgraph_node *what = e->callee->ultimate_alias_target ();
     199      6941530 :   int newsize;
     200      6941530 :   int limit = 0;
     201      6941530 :   HOST_WIDE_INT stack_size_limit = 0, inlined_stack;
     202      6941530 :   ipa_size_summary *outer_info = ipa_size_summaries->get (to);
     203              : 
     204              :   /* Look for function e->caller is inlined to.  While doing
     205              :      so work out the largest function body on the way.  As
     206              :      described above, we want to base our function growth
     207              :      limits based on that.  Not on the self size of the
     208              :      outer function, not on the self size of inline code
     209              :      we immediately inline to.  This is the most relaxed
     210              :      interpretation of the rule "do not grow large functions
     211              :      too much in order to prevent compiler from exploding".  */
     212     10389448 :   while (true)
     213              :     {
     214      8665489 :       ipa_size_summary *size_info = ipa_size_summaries->get (to);
     215      8665489 :       if (limit < size_info->self_size)
     216              :         limit = size_info->self_size;
     217      8665489 :       if (stack_size_limit < size_info->estimated_self_stack_size)
     218              :         stack_size_limit = size_info->estimated_self_stack_size;
     219      8665489 :       if (to->inlined_to)
     220      1723959 :         to = to->callers->caller;
     221              :       else
     222              :         break;
     223      1723959 :     }
     224              : 
     225      6941530 :   ipa_fn_summary *what_info = ipa_fn_summaries->get (what);
     226      6941530 :   ipa_size_summary *what_size_info = ipa_size_summaries->get (what);
     227              : 
     228      6941530 :   if (limit < what_size_info->self_size)
     229              :     limit = what_size_info->self_size;
     230              : 
     231      6941530 :   limit += limit * opt_for_fn (to->decl, param_large_function_growth) / 100;
     232              : 
     233              :   /* Check the size after inlining against the function limits.  But allow
     234              :      the function to shrink if it went over the limits by forced inlining.  */
     235      6941530 :   newsize = estimate_size_after_inlining (to, e);
     236      6941530 :   if (newsize >= ipa_size_summaries->get (what)->size
     237      6759670 :       && newsize > opt_for_fn (to->decl, param_large_function_insns)
     238      7198930 :       && newsize > limit)
     239              :     {
     240         5559 :       e->inline_failed = CIF_LARGE_FUNCTION_GROWTH_LIMIT;
     241         5559 :       return false;
     242              :     }
     243              : 
     244      6935971 :   if (!what_info->estimated_stack_size)
     245              :     return true;
     246              : 
     247              :   /* FIXME: Stack size limit often prevents inlining in Fortran programs
     248              :      due to large i/o datastructures used by the Fortran front-end.
     249              :      We ought to ignore this limit when we know that the edge is executed
     250              :      on every invocation of the caller (i.e. its call statement dominates
     251              :      exit block).  We do not track this information, yet.  */
     252      2159824 :   stack_size_limit += ((gcov_type)stack_size_limit
     253      1079912 :                        * opt_for_fn (to->decl, param_stack_frame_growth)
     254      1079912 :                        / 100);
     255              : 
     256      1079912 :   inlined_stack = (ipa_get_stack_frame_offset (to)
     257      1079912 :                    + outer_info->estimated_self_stack_size
     258      1079912 :                    + what_info->estimated_stack_size);
     259              :   /* Check new stack consumption with stack consumption at the place
     260              :      stack is used.  */
     261      1079912 :   if (inlined_stack > stack_size_limit
     262              :       /* If function already has large stack usage from sibling
     263              :          inline call, we can inline, too.
     264              :          This bit overoptimistically assume that we are good at stack
     265              :          packing.  */
     266       313191 :       && inlined_stack > ipa_fn_summaries->get (to)->estimated_stack_size
     267      1379824 :       && inlined_stack > opt_for_fn (to->decl, param_large_stack_frame))
     268              :     {
     269        64628 :       e->inline_failed = CIF_LARGE_STACK_FRAME_GROWTH_LIMIT;
     270        64628 :       return false;
     271              :     }
     272              :   return true;
     273              : }
     274              : 
     275              : /* Dump info about why inlining has failed.  */
     276              : 
     277              : static void
     278      5158952 : report_inline_failed_reason (struct cgraph_edge *e)
     279              : {
     280      5158952 :   if (dump_enabled_p ())
     281              :     {
     282         2387 :       dump_printf_loc (MSG_MISSED_OPTIMIZATION, e->call_stmt,
     283              :                        "  not inlinable: %C -> %C, %s\n",
     284              :                        e->caller, e->callee,
     285              :                        cgraph_inline_failed_string (e->inline_failed));
     286         2387 :       if ((e->inline_failed == CIF_TARGET_OPTION_MISMATCH
     287         2387 :            || e->inline_failed == CIF_OPTIMIZATION_MISMATCH)
     288            2 :           && e->caller->lto_file_data
     289         2387 :           && e->callee->ultimate_alias_target ()->lto_file_data)
     290              :         {
     291            0 :           dump_printf_loc (MSG_MISSED_OPTIMIZATION, e->call_stmt,
     292              :                            "  LTO objects: %s, %s\n",
     293            0 :                            e->caller->lto_file_data->file_name,
     294            0 :                            e->callee->ultimate_alias_target ()->lto_file_data->file_name);
     295              :         }
     296         2387 :       if (e->inline_failed == CIF_TARGET_OPTION_MISMATCH
     297            2 :           && dump_file)
     298              :         {
     299            0 :           struct cl_target_option *opt_caller
     300            0 :             = target_opts_for_fn (e->caller->decl);
     301            0 :           struct cl_target_option *opt_callee
     302            0 :             = target_opts_for_fn (e->callee->ultimate_alias_target ()->decl);
     303            0 :           if (opt_caller != NULL && opt_callee != NULL)
     304            0 :             cl_target_option_print_diff (dump_file, 2, opt_caller, opt_callee);
     305              :         }
     306         2387 :       if (e->inline_failed == CIF_OPTIMIZATION_MISMATCH)
     307            0 :         if (dump_file)
     308            0 :           cl_optimization_print_diff
     309            0 :             (dump_file, 2, opts_for_fn (e->caller->decl),
     310            0 :              opts_for_fn (e->callee->ultimate_alias_target ()->decl));
     311              :     }
     312      5158952 : }
     313              : 
     314              :  /* Decide whether sanitizer-related attributes allow inlining. */
     315              : 
     316              : static bool
     317     10161699 : sanitize_attrs_match_for_inline_p (const_tree caller, const_tree callee)
     318              : {
     319     10161699 :   if (!caller || !callee)
     320              :     return true;
     321              : 
     322              :   /* Follow clang and allow inlining for always_inline functions.  */
     323     10161699 :   if (lookup_attribute ("always_inline", DECL_ATTRIBUTES (callee)))
     324              :     return true;
     325              : 
     326      9535635 :   const sanitize_code codes[] =
     327              :     {
     328              :       SANITIZE_ADDRESS,
     329              :       SANITIZE_THREAD,
     330              :       SANITIZE_UNDEFINED,
     331              :       SANITIZE_UNDEFINED_NONDEFAULT,
     332              :       SANITIZE_POINTER_COMPARE,
     333              :       SANITIZE_POINTER_SUBTRACT
     334              :     };
     335              : 
     336     66748453 :   for (unsigned i = 0; i < ARRAY_SIZE (codes); i++)
     337    114426008 :     if (sanitize_flags_p (codes[i], caller)
     338     57213004 :         != sanitize_flags_p (codes[i], callee))
     339              :       return false;
     340              : 
     341      9535449 :   if (sanitize_coverage_p (caller) != sanitize_coverage_p (callee))
     342            0 :     return false;
     343              : 
     344              :   return true;
     345              : }
     346              : 
     347              : /* Used for flags where it is safe to inline when caller's value is
     348              :    grater than callee's.  */
     349              : #define check_maybe_up(flag) \
     350              :       (opts_for_fn (caller->decl)->x_##flag               \
     351              :        != opts_for_fn (callee->decl)->x_##flag            \
     352              :        && (!always_inline                               \
     353              :            || opts_for_fn (caller->decl)->x_##flag        \
     354              :               < opts_for_fn (callee->decl)->x_##flag))
     355              : /* Used for flags where it is safe to inline when caller's value is
     356              :    smaller than callee's.  */
     357              : #define check_maybe_down(flag) \
     358              :       (opts_for_fn (caller->decl)->x_##flag               \
     359              :        != opts_for_fn (callee->decl)->x_##flag            \
     360              :        && (!always_inline                               \
     361              :            || opts_for_fn (caller->decl)->x_##flag        \
     362              :               > opts_for_fn (callee->decl)->x_##flag))
     363              : /* Used for flags where exact match is needed for correctness.  */
     364              : #define check_match(flag) \
     365              :       (opts_for_fn (caller->decl)->x_##flag               \
     366              :        != opts_for_fn (callee->decl)->x_##flag)
     367              : 
     368              : /* Decide if we can inline the edge and possibly update
     369              :    inline_failed reason.
     370              :    We check whether inlining is possible at all and whether
     371              :    caller growth limits allow doing so.
     372              : 
     373              :    if REPORT is true, output reason to the dump file. */
     374              : 
     375              : static bool
     376     14411406 : can_inline_edge_p (struct cgraph_edge *e, bool report,
     377              :                    bool early = false)
     378              : {
     379     14411406 :   gcc_checking_assert (e->inline_failed);
     380              : 
     381     14411406 :   if (cgraph_inline_failed_type (e->inline_failed) == CIF_FINAL_ERROR)
     382              :     {
     383      3754381 :       if (report)
     384      3722504 :         report_inline_failed_reason (e);
     385              :       return false;
     386              :     }
     387              : 
     388     10657025 :   bool inlinable = true;
     389     10657025 :   enum availability avail;
     390      9225388 :   cgraph_node *caller = (e->caller->inlined_to
     391     10657025 :                          ? e->caller->inlined_to : e->caller);
     392     10657025 :   cgraph_node *callee = e->callee->ultimate_alias_target (&avail, caller);
     393              : 
     394     10657025 :   if (!callee->definition)
     395              :     {
     396          950 :       e->inline_failed = CIF_BODY_NOT_AVAILABLE;
     397          950 :       inlinable = false;
     398              :     }
     399     10657025 :   if (!early && (!opt_for_fn (callee->decl, optimize)
     400      6231198 :                  || !opt_for_fn (caller->decl, optimize)))
     401              :     {
     402          458 :       e->inline_failed = CIF_FUNCTION_NOT_OPTIMIZED;
     403          458 :       inlinable = false;
     404              :     }
     405     10656567 :   else if (callee->calls_comdat_local)
     406              :     {
     407        23489 :       e->inline_failed = CIF_USES_COMDAT_LOCAL;
     408        23489 :       inlinable = false;
     409              :     }
     410     10633078 :   else if (avail <= AVAIL_INTERPOSABLE)
     411              :     {
     412       136397 :       e->inline_failed = CIF_OVERWRITABLE;
     413       136397 :       inlinable = false;
     414              :     }
     415              :   /* All edges with call_stmt_cannot_inline_p should have inline_failed
     416              :      initialized to one of FINAL_ERROR reasons.  */
     417     10496681 :   else if (e->call_stmt_cannot_inline_p)
     418            0 :     gcc_unreachable ();
     419              :   /* Don't inline if the functions have different EH personalities.  */
     420     10496681 :   else if (DECL_FUNCTION_PERSONALITY (caller->decl)
     421      3113791 :            && DECL_FUNCTION_PERSONALITY (callee->decl)
     422     10496681 :            && (DECL_FUNCTION_PERSONALITY (caller->decl)
     423       278263 :                != DECL_FUNCTION_PERSONALITY (callee->decl)))
     424              :     {
     425            0 :       e->inline_failed = CIF_EH_PERSONALITY;
     426            0 :       inlinable = false;
     427              :     }
     428              :   /* TM pure functions should not be inlined into non-TM_pure
     429              :      functions.  */
     430     10496681 :   else if (is_tm_pure (callee->decl) && !is_tm_pure (caller->decl))
     431              :     {
     432           30 :       e->inline_failed = CIF_UNSPECIFIED;
     433           30 :       inlinable = false;
     434              :     }
     435              :   /* Check compatibility of target optimization options.  */
     436     10496651 :   else if (!targetm.target_option.can_inline_p (caller->decl,
     437              :                                                 callee->decl))
     438              :     {
     439          477 :       e->inline_failed = CIF_TARGET_OPTION_MISMATCH;
     440          477 :       inlinable = false;
     441              :     }
     442     10496174 :   else if (ipa_fn_summaries->get (callee) == NULL
     443     10496172 :            || !ipa_fn_summaries->get (callee)->inlinable)
     444              :     {
     445       334475 :       e->inline_failed = CIF_FUNCTION_NOT_INLINABLE;
     446       334475 :       inlinable = false;
     447              :     }
     448              :   /* Don't inline a function with mismatched sanitization attributes. */
     449     10161699 :   else if (!sanitize_attrs_match_for_inline_p (caller->decl, callee->decl))
     450              :     {
     451          186 :       e->inline_failed = CIF_SANITIZE_ATTRIBUTE_MISMATCH;
     452          186 :       inlinable = false;
     453              :     }
     454              : 
     455     10657025 :   if (inlinable && !strub_inlinable_to_p (callee, caller))
     456              :     {
     457         1104 :       e->inline_failed = CIF_UNSPECIFIED;
     458         1104 :       inlinable = false;
     459              :     }
     460     10657025 :   if (inlinable && callee->must_remain_in_tu_body
     461            9 :       && caller->lto_file_data != callee->lto_file_data)
     462              :     {
     463            9 :       e->inline_failed = CIF_MUST_REMAIN_IN_TU;
     464            9 :       inlinable = false;
     465              :     }
     466     10657025 :   if (!inlinable && report)
     467       489212 :     report_inline_failed_reason (e);
     468              :   return inlinable;
     469              : }
     470              : 
     471              : /* Return inlining_insns_single limit for function N.  If HINT or HINT2 is true
     472              :    scale up the bound.  */
     473              : 
     474              : static int
     475      9784289 : inline_insns_single (cgraph_node *n, bool hint, bool hint2)
     476              : {
     477      9784289 :   if (hint && hint2)
     478              :     {
     479      3422858 :       int64_t spd = opt_for_fn (n->decl, param_inline_heuristics_hint_percent);
     480      3422858 :       spd = spd * spd;
     481      3422858 :       if (spd > 1000000)
     482              :         spd = 1000000;
     483      3422858 :       return opt_for_fn (n->decl, param_max_inline_insns_single) * spd / 100;
     484              :     }
     485      6361431 :   if (hint || hint2)
     486       724462 :     return opt_for_fn (n->decl, param_max_inline_insns_single)
     487       724462 :            * opt_for_fn (n->decl, param_inline_heuristics_hint_percent) / 100;
     488      5636969 :   return opt_for_fn (n->decl, param_max_inline_insns_single);
     489              : }
     490              : 
     491              : /* Return inlining_insns_auto limit for function N.  If HINT or HINT2 is true
     492              :    scale up the bound.   */
     493              : 
     494              : static int
     495      5619700 : inline_insns_auto (cgraph_node *n, bool hint, bool hint2)
     496              : {
     497      5619700 :   int max_inline_insns_auto = opt_for_fn (n->decl, param_max_inline_insns_auto);
     498      5619700 :   if (hint && hint2)
     499              :     {
     500      2053642 :       int64_t spd = opt_for_fn (n->decl, param_inline_heuristics_hint_percent);
     501      2053642 :       spd = spd * spd;
     502      2053642 :       if (spd > 1000000)
     503              :         spd = 1000000;
     504      2053642 :       return max_inline_insns_auto * spd / 100;
     505              :     }
     506      3566058 :   if (hint || hint2)
     507      1502032 :     return max_inline_insns_auto
     508      1502032 :            * opt_for_fn (n->decl, param_inline_heuristics_hint_percent) / 100;
     509              :   return max_inline_insns_auto;
     510              : }
     511              : 
     512              : enum can_inline_edge_by_limits_flags
     513              : {
     514              :   /* True if we are early inlining.  */
     515              :   CAN_INLINE_EARLY = 1,
     516              :   /* Ignore size limits.  */
     517              :   CAN_INLINE_DISREGARD_LIMITS = 2,
     518              :   /* Force size limits (ignore always_inline).  This is used for
     519              :      recursive inlining where always_inline may lead to inline bombs
     520              :      and technically it is non-sential anyway.  */
     521              :   CAN_INLINE_FORCE_LIMITS = 4,
     522              :   /* Report decision to dump file.  */
     523              :   CAN_INLINE_REPORT = 8,
     524              : };
     525              : 
     526              : /* Decide if we can inline the edge and possibly update
     527              :    inline_failed reason.
     528              :    We check whether inlining is possible at all and whether
     529              :    caller growth limits allow doing so.  */
     530              : 
     531              : static bool
     532      7578927 : can_inline_edge_by_limits_p (struct cgraph_edge *e, int flags)
     533              : {
     534      7578927 :   gcc_checking_assert (e->inline_failed);
     535              : 
     536      7578927 :   if (cgraph_inline_failed_type (e->inline_failed) == CIF_FINAL_ERROR)
     537              :     {
     538          210 :       if (flags & CAN_INLINE_REPORT)
     539          210 :         report_inline_failed_reason (e);
     540              :       return false;
     541              :     }
     542              : 
     543      7578717 :   bool inlinable = true;
     544      7578717 :   enum availability avail;
     545      6730371 :   cgraph_node *caller = (e->caller->inlined_to
     546      7578717 :                          ? e->caller->inlined_to : e->caller);
     547      7578717 :   cgraph_node *callee = e->callee->ultimate_alias_target (&avail, caller);
     548      7578717 :   tree caller_tree = DECL_FUNCTION_SPECIFIC_OPTIMIZATION (caller->decl);
     549      7578717 :   tree callee_tree
     550      7578717 :     = callee ? DECL_FUNCTION_SPECIFIC_OPTIMIZATION (callee->decl) : NULL;
     551              :   /* Check if caller growth allows the inlining.  */
     552      7578717 :   if (!(flags & CAN_INLINE_DISREGARD_LIMITS)
     553      7570268 :       && ((flags & CAN_INLINE_FORCE_LIMITS)
     554      7534856 :           || (!DECL_DISREGARD_INLINE_LIMITS (callee->decl)
     555      6906262 :               && !lookup_attribute ("flatten",
     556      6906262 :                          DECL_ATTRIBUTES (caller->decl))))
     557     14520247 :       && !caller_growth_limits (e))
     558              :     inlinable = false;
     559      7508530 :   else if (callee->externally_visible
     560      4995279 :            && !DECL_DISREGARD_INLINE_LIMITS (callee->decl)
     561     12004693 :            && flag_live_patching == LIVE_PATCHING_INLINE_ONLY_STATIC)
     562              :     {
     563            2 :       e->inline_failed = CIF_EXTERN_LIVE_ONLY_STATIC;
     564            2 :       inlinable = false;
     565              :     }
     566              :   /* Don't inline a function with a higher optimization level than the
     567              :      caller.  FIXME: this is really just tip of iceberg of handling
     568              :      optimization attribute.  */
     569      7508528 :   else if (caller_tree != callee_tree)
     570              :     {
     571         9999 :       bool always_inline =
     572         9999 :              (DECL_DISREGARD_INLINE_LIMITS (callee->decl)
     573        12690 :               && lookup_attribute ("always_inline",
     574         2691 :                                    DECL_ATTRIBUTES (callee->decl)));
     575         9999 :       ipa_fn_summary *caller_info = ipa_fn_summaries->get (caller);
     576         9999 :       ipa_fn_summary *callee_info = ipa_fn_summaries->get (callee);
     577              : 
     578              :      /* Until GCC 4.9 we did not check the semantics-altering flags
     579              :         below and inlined across optimization boundaries.
     580              :         Enabling checks below breaks several packages by refusing
     581              :         to inline library always_inline functions. See PR65873.
     582              :         Disable the check for early inlining for now until better solution
     583              :         is found.  */
     584         9999 :      if (always_inline && (flags & CAN_INLINE_EARLY))
     585              :         ;
     586              :       /* There are some options that change IL semantics which means
     587              :          we cannot inline in these cases for correctness reason.
     588              :          Not even for always_inline declared functions.  */
     589         7308 :      else if (check_match (flag_wrapv)
     590         7308 :               || check_match (flag_wrapv_pointer)
     591         7307 :               || check_match (flag_trapv)
     592         7307 :               || check_match (flag_pcc_struct_return)
     593         7307 :               || check_maybe_down (optimize_debug)
     594              :               /* When caller or callee does FP math, be sure FP codegen flags
     595              :                  compatible.  */
     596         7301 :               || ((caller_info->fp_expressions && callee_info->fp_expressions)
     597         1273 :                   && (check_maybe_up (flag_rounding_math)
     598         1273 :                       || check_maybe_up (flag_trapping_math)
     599         1271 :                       || check_maybe_down (flag_unsafe_math_optimizations)
     600         1271 :                       || check_maybe_down (flag_finite_math_only)
     601         1270 :                       || check_maybe_up (flag_signaling_nans)
     602         1270 :                       || check_maybe_up (flag_complex_method)
     603         1269 :                       || check_maybe_up (flag_signed_zeros)
     604         1269 :                       || check_maybe_down (flag_associative_math)
     605         1253 :                       || check_maybe_down (flag_reciprocal_math)
     606         1253 :                       || check_maybe_down (flag_fp_int_builtin_inexact)
     607              :                       /* Strictly speaking only when the callee contains function
     608              :                          calls that may end up setting errno.  */
     609         1253 :                       || check_maybe_up (flag_errno_math)))
     610              :               /* We do not want to make code compiled with exceptions to be
     611              :                  brought into a non-EH function unless we know that the callee
     612              :                  does not throw.
     613              :                  This is tracked by DECL_FUNCTION_PERSONALITY.  */
     614         7281 :               || (check_maybe_up (flag_non_call_exceptions)
     615            0 :                   && DECL_FUNCTION_PERSONALITY (callee->decl))
     616         7281 :               || (check_maybe_up (flag_exceptions)
     617           16 :                   && DECL_FUNCTION_PERSONALITY (callee->decl))
     618              :               /* When devirtualization is disabled for callee, it is not safe
     619              :                  to inline it as we possibly mangled the type info.
     620              :                  Allow early inlining of always inlines.  */
     621        14589 :               || (!(flags & CAN_INLINE_EARLY) && check_maybe_down (flag_devirtualize)))
     622              :         {
     623           35 :           e->inline_failed = CIF_OPTIMIZATION_MISMATCH;
     624           35 :           inlinable = false;
     625              :         }
     626              :       /* gcc.dg/pr43564.c.  Apply user-forced inline even at -O0.  */
     627         7273 :       else if (always_inline)
     628              :         ;
     629              :       /* When user added an attribute to the callee honor it.  */
     630         7273 :       else if (lookup_attribute ("optimize", DECL_ATTRIBUTES (callee->decl))
     631         7273 :                && opts_for_fn (caller->decl) != opts_for_fn (callee->decl))
     632              :         {
     633         2456 :           e->inline_failed = CIF_OPTIMIZATION_MISMATCH;
     634         2456 :           inlinable = false;
     635              :         }
     636              :       /* If explicit optimize attribute are not used, the mismatch is caused
     637              :          by different command line options used to build different units.
     638              :          Do not care about COMDAT functions - those are intended to be
     639              :          optimized with the optimization flags of module they are used in.
     640              :          Also do not care about mixing up size/speed optimization when
     641              :          DECL_DISREGARD_INLINE_LIMITS is set.  */
     642         4817 :       else if ((callee->merged_comdat
     643            0 :                 && !lookup_attribute ("optimize",
     644            0 :                                       DECL_ATTRIBUTES (caller->decl)))
     645         4817 :                || DECL_DISREGARD_INLINE_LIMITS (callee->decl))
     646              :         ;
     647              :       /* If mismatch is caused by merging two LTO units with different
     648              :          optimization flags we want to be bit nicer.  However never inline
     649              :          if one of functions is not optimized at all.  */
     650         4817 :       else if (!opt_for_fn (callee->decl, optimize)
     651         4817 :                || !opt_for_fn (caller->decl, optimize))
     652              :         {
     653            0 :           e->inline_failed = CIF_OPTIMIZATION_MISMATCH;
     654            0 :           inlinable = false;
     655              :         }
     656              :       /* If callee is optimized for size and caller is not, allow inlining if
     657              :          code shrinks or we are in param_max_inline_insns_single limit and
     658              :          callee is inline (and thus likely an unified comdat).
     659              :          This will allow caller to run faster.  */
     660         4817 :       else if (opt_for_fn (callee->decl, optimize_size)
     661         4817 :                > opt_for_fn (caller->decl, optimize_size))
     662              :         {
     663          118 :           int growth = estimate_edge_growth (e);
     664          118 :           if (growth > opt_for_fn (caller->decl, param_max_inline_insns_size)
     665          118 :               && (!DECL_DECLARED_INLINE_P (callee->decl)
     666           65 :                   && growth >= MAX (inline_insns_single (caller, false, false),
     667              :                                     inline_insns_auto (caller, false, false))))
     668              :             {
     669            0 :               e->inline_failed = CIF_OPTIMIZATION_MISMATCH;
     670            0 :               inlinable = false;
     671              :             }
     672              :         }
     673              :       /* If callee is more aggressively optimized for performance than caller,
     674              :          we generally want to inline only cheap (runtime wise) functions.  */
     675         4699 :       else if (opt_for_fn (callee->decl, optimize_size)
     676              :                < opt_for_fn (caller->decl, optimize_size)
     677         4699 :                || (opt_for_fn (callee->decl, optimize)
     678              :                    > opt_for_fn (caller->decl, optimize)))
     679              :         {
     680        12675 :           if (estimate_edge_time (e)
     681         4225 :               >= 20 + ipa_call_summaries->get (e)->call_stmt_time)
     682              :             {
     683         1492 :               e->inline_failed = CIF_OPTIMIZATION_MISMATCH;
     684         1492 :               inlinable = false;
     685              :             }
     686              :         }
     687              : 
     688              :     }
     689              : 
     690        74172 :   if (!inlinable && (flags & CAN_INLINE_REPORT))
     691        67477 :     report_inline_failed_reason (e);
     692              :   return inlinable;
     693              : }
     694              : 
     695              : 
     696              : /* Return true if the edge E is inlinable during early inlining.  */
     697              : 
     698              : static bool
     699      4425763 : can_early_inline_edge_p (struct cgraph_edge *e)
     700              : {
     701      4424200 :   cgraph_node *caller = (e->caller->inlined_to
     702      4425763 :                          ? e->caller->inlined_to : e->caller);
     703      4425763 :   struct cgraph_node *callee = e->callee->ultimate_alias_target ();
     704              :   /* Early inliner might get called at WPA stage when IPA pass adds new
     705              :      function.  In this case we cannot really do any of early inlining
     706              :      because function bodies are missing.  */
     707      4425763 :   if (cgraph_inline_failed_type (e->inline_failed) == CIF_FINAL_ERROR)
     708              :     return false;
     709      4425431 :   if (!gimple_has_body_p (callee->decl))
     710              :     {
     711            0 :       e->inline_failed = CIF_BODY_NOT_AVAILABLE;
     712            0 :       return false;
     713              :     }
     714      8850862 :   gcc_assert (gimple_in_ssa_p (DECL_STRUCT_FUNCTION (e->caller->decl))
     715              :               && gimple_in_ssa_p (DECL_STRUCT_FUNCTION (callee->decl)));
     716      4425431 :   if (coverage_instrumentation_p ()
     717      4427107 :       && ((lookup_attribute ("no_profile_instrument_function",
     718         1676 :                             DECL_ATTRIBUTES (caller->decl)) == NULL_TREE)
     719         1676 :           != (lookup_attribute ("no_profile_instrument_function",
     720         3352 :                                 DECL_ATTRIBUTES (callee->decl)) == NULL_TREE)))
     721              :     return false;
     722              : 
     723      4425429 :   if (!can_inline_edge_p (e, true, true)
     724      4425429 :       || !can_inline_edge_by_limits_p (e, CAN_INLINE_EARLY | CAN_INLINE_REPORT))
     725              :     return false;
     726              :   /* When inlining regular functions into always-inline functions
     727              :      during early inlining watch for possible inline cycles.  */
     728      4336019 :   if (DECL_DISREGARD_INLINE_LIMITS (caller->decl)
     729       276872 :       && lookup_attribute ("always_inline", DECL_ATTRIBUTES (caller->decl))
     730      4612015 :       && (!DECL_DISREGARD_INLINE_LIMITS (callee->decl)
     731       164109 :           || !lookup_attribute ("always_inline", DECL_ATTRIBUTES (callee->decl))))
     732              :     {
     733              :       /* If there are indirect calls, inlining may produce direct call.
     734              :          TODO: We may lift this restriction if we avoid errors on formerly
     735              :          indirect calls to always_inline functions.  Taking address
     736              :          of always_inline function is generally bad idea and should
     737              :          have been declared as undefined, but sadly we allow this.  */
     738       111888 :       if (caller->indirect_calls || e->callee->indirect_calls)
     739              :         return false;
     740       110326 :       ipa_fn_summary *callee_info = ipa_fn_summaries->get (callee);
     741       110326 :       if (callee_info->safe_to_inline_to_always_inline)
     742        31230 :         return callee_info->safe_to_inline_to_always_inline - 1;
     743       174235 :       for (cgraph_edge *e2 = callee->callees; e2; e2 = e2->next_callee)
     744              :         {
     745        95165 :           struct cgraph_node *callee2 = e2->callee->ultimate_alias_target ();
     746              :           /* As early inliner runs in RPO order, we will see uninlined
     747              :              always_inline calls only in the case of cyclic graphs.  */
     748        95165 :           if (DECL_DISREGARD_INLINE_LIMITS (callee2->decl)
     749        95165 :               || lookup_attribute ("always_inline", DECL_ATTRIBUTES (callee2->decl)))
     750              :             {
     751            0 :               callee_info->safe_to_inline_to_always_inline = 1;
     752            0 :               return false;
     753              :             }
     754              :           /* With LTO watch for case where function is later replaced
     755              :              by always_inline definition.
     756              :              TODO: We may either stop treating noninlined cross-module always
     757              :              inlines as errors, or we can extend decl merging to produce
     758              :              syntacic alias and honor always inline only in units it has
     759              :              been declared as such.  */
     760        95165 :           if (flag_lto && callee2->externally_visible)
     761              :             {
     762           26 :               callee_info->safe_to_inline_to_always_inline = 1;
     763           26 :               return false;
     764              :             }
     765              :         }
     766        79070 :       callee_info->safe_to_inline_to_always_inline = 2;
     767              :     }
     768              :   return true;
     769              : }
     770              : 
     771              : 
     772              : /* Return number of calls in N.  Ignore cheap builtins.  */
     773              : 
     774              : static int
     775       914205 : num_calls (struct cgraph_node *n)
     776              : {
     777       914205 :   struct cgraph_edge *e;
     778       914205 :   int num = 0;
     779              : 
     780      1849898 :   for (e = n->callees; e; e = e->next_callee)
     781       935693 :     if (!is_inexpensive_builtin (e->callee->decl))
     782       843084 :       num++;
     783       914205 :   return num;
     784              : }
     785              : 
     786              : 
     787              : /* Return true if we are interested in inlining small function.  */
     788              : 
     789              : static bool
     790      3702183 : want_early_inline_function_p (struct cgraph_edge *e)
     791              : {
     792      3702183 :   bool want_inline = true;
     793      3702183 :   struct cgraph_node *callee = e->callee->ultimate_alias_target ();
     794              : 
     795      3702183 :   if (DECL_DISREGARD_INLINE_LIMITS (callee->decl))
     796              :     ;
     797      3702171 :   else if (!DECL_DECLARED_INLINE_P (callee->decl)
     798      3702171 :            && !opt_for_fn (e->caller->decl, flag_inline_small_functions))
     799              :     {
     800           62 :       e->inline_failed = CIF_FUNCTION_NOT_INLINE_CANDIDATE;
     801           62 :       report_inline_failed_reason (e);
     802           62 :       want_inline = false;
     803              :     }
     804              :   else
     805              :     {
     806              :       /* First take care of very large functions.  */
     807      3702109 :       int min_growth = estimate_min_edge_growth (e), growth = 0;
     808      3702109 :       int n;
     809      3702109 :       int early_inlining_insns = param_early_inlining_insns;
     810              : 
     811      3702109 :       if (min_growth > early_inlining_insns)
     812              :         {
     813       436886 :           if (dump_enabled_p ())
     814           40 :             dump_printf_loc (MSG_MISSED_OPTIMIZATION, e->call_stmt,
     815              :                              "  will not early inline: %C->%C, "
     816              :                              "call is cold and code would grow "
     817              :                              "at least by %i\n",
     818              :                              e->caller, callee,
     819              :                              min_growth);
     820              :           want_inline = false;
     821              :         }
     822              :       else
     823      3265223 :         growth = estimate_edge_growth (e);
     824              : 
     825              : 
     826      3265263 :       if (!want_inline || growth <= param_max_inline_insns_size)
     827              :         ;
     828      1321399 :       else if (!e->maybe_hot_p ())
     829              :         {
     830        21402 :           if (dump_enabled_p ())
     831            0 :             dump_printf_loc (MSG_MISSED_OPTIMIZATION, e->call_stmt,
     832              :                              "  will not early inline: %C->%C, "
     833              :                              "call is cold and code would grow by %i\n",
     834              :                              e->caller, callee,
     835              :                              growth);
     836              :           want_inline = false;
     837              :         }
     838      1299997 :       else if (growth > early_inlining_insns)
     839              :         {
     840       385792 :           if (dump_enabled_p ())
     841            0 :             dump_printf_loc (MSG_MISSED_OPTIMIZATION, e->call_stmt,
     842              :                              "  will not early inline: %C->%C, "
     843              :                              "growth %i exceeds --param early-inlining-insns\n",
     844              :                              e->caller, callee, growth);
     845              :           want_inline = false;
     846              :         }
     847       914205 :       else if ((n = num_calls (callee)) != 0
     848       914205 :                && growth * (n + 1) > early_inlining_insns)
     849              :         {
     850       271124 :           if (dump_enabled_p ())
     851           11 :             dump_printf_loc (MSG_MISSED_OPTIMIZATION, e->call_stmt,
     852              :                              "  will not early inline: %C->%C, "
     853              :                              "growth %i exceeds --param early-inlining-insns "
     854              :                              "divided by number of calls\n",
     855              :                              e->caller, callee, growth);
     856              :           want_inline = false;
     857              :         }
     858              :     }
     859      3702183 :   return want_inline;
     860              : }
     861              : 
     862              : /* Compute time of the edge->caller + edge->callee execution when inlining
     863              :    does not happen.  */
     864              : 
     865              : inline sreal
     866       587504 : compute_uninlined_call_time (struct cgraph_edge *edge,
     867              :                              sreal uninlined_call_time,
     868              :                              sreal freq)
     869              : {
     870       428376 :   cgraph_node *caller = (edge->caller->inlined_to
     871       587504 :                          ? edge->caller->inlined_to
     872              :                          : edge->caller);
     873              : 
     874       587504 :   if (freq > 0)
     875       570199 :     uninlined_call_time *= freq;
     876              :   else
     877        17305 :     uninlined_call_time = uninlined_call_time >> 11;
     878              : 
     879       587504 :   sreal caller_time = ipa_fn_summaries->get (caller)->time;
     880       587504 :   return uninlined_call_time + caller_time;
     881              : }
     882              : 
     883              : /* Same as compute_uinlined_call_time but compute time when inlining
     884              :    does happen.  */
     885              : 
     886              : inline sreal
     887       587504 : compute_inlined_call_time (struct cgraph_edge *edge,
     888              :                            sreal time,
     889              :                            sreal freq)
     890              : {
     891       428376 :   cgraph_node *caller = (edge->caller->inlined_to
     892       587504 :                          ? edge->caller->inlined_to
     893              :                          : edge->caller);
     894       587504 :   sreal caller_time = ipa_fn_summaries->get (caller)->time;
     895              : 
     896       587504 :   if (freq > 0)
     897       570199 :     time *= freq;
     898              :   else
     899        17305 :     time = time >> 11;
     900              : 
     901              :   /* This calculation should match one in ipa-inline-analysis.cc
     902              :      (estimate_edge_size_and_time).  */
     903       587504 :   time -= (sreal)ipa_call_summaries->get (edge)->call_stmt_time * freq;
     904       587504 :   time += caller_time;
     905       587504 :   if (time <= 0)
     906            0 :     time = ((sreal) 1) >> 8;
     907       587504 :   gcc_checking_assert (time >= 0);
     908       587504 :   return time;
     909              : }
     910              : 
     911              : /* Determine time saved by inlining EDGE of frequency FREQ
     912              :    where callee's runtime w/o inlining is UNINLINED_TYPE
     913              :    and with inlined is INLINED_TYPE.  */
     914              : 
     915              : inline sreal
     916      9645053 : inlining_speedup (struct cgraph_edge *edge,
     917              :                   sreal freq,
     918              :                   sreal uninlined_time,
     919              :                   sreal inlined_time)
     920              : {
     921      9645053 :   sreal speedup = uninlined_time - inlined_time;
     922              :   /* Handling of call_time should match one in ipa-inline-fnsummary.c
     923              :      (estimate_edge_size_and_time).  */
     924      9645053 :   sreal call_time = ipa_call_summaries->get (edge)->call_stmt_time;
     925              : 
     926      9645053 :   if (freq > 0)
     927              :     {
     928      9606652 :       speedup = (speedup + call_time);
     929     12016864 :       if (freq != 1)
     930      7196440 :        speedup = speedup * freq;
     931              :     }
     932        38401 :   else if (freq == 0)
     933        38401 :     speedup = speedup >> 11;
     934      9645053 :   gcc_checking_assert (speedup >= 0);
     935      9645053 :   return speedup;
     936              : }
     937              : 
     938              : /* Return expected speedup of the callee function alone
     939              :    (i.e. not estimate of call overhead and also no scalling
     940              :     by call frequency.  */
     941              : 
     942              : static sreal
     943      3401688 : callee_speedup (struct cgraph_edge *e)
     944              : {
     945      3401688 :   sreal unspec_time;
     946      3401688 :   sreal spec_time = estimate_edge_time (e, &unspec_time);
     947      3401688 :   return unspec_time - spec_time;
     948              : }
     949              : 
     950              : /* Return true if the speedup for inlining E is bigger than
     951              :    param_inline_min_speedup.  */
     952              : 
     953              : static bool
     954       587504 : big_speedup_p (struct cgraph_edge *e)
     955              : {
     956       587504 :   sreal unspec_time;
     957       587504 :   sreal spec_time = estimate_edge_time (e, &unspec_time);
     958       587504 :   sreal freq = e->sreal_frequency ();
     959       587504 :   sreal time = compute_uninlined_call_time (e, unspec_time, freq);
     960       587504 :   sreal inlined_time = compute_inlined_call_time (e, spec_time, freq);
     961       428376 :   cgraph_node *caller = (e->caller->inlined_to
     962       587504 :                          ? e->caller->inlined_to
     963              :                          : e->caller);
     964       587504 :   int limit = opt_for_fn (caller->decl, param_inline_min_speedup);
     965              : 
     966       587504 :   if ((time - inlined_time) * 100 > time * limit)
     967              :     return true;
     968              :   return false;
     969              : }
     970              : 
     971              : /* Return true if we are interested in inlining small function.
     972              :    When REPORT is true, report reason to dump file.  */
     973              : 
     974              : static bool
     975      5535260 : want_inline_small_function_p (struct cgraph_edge *e, bool report)
     976              : {
     977      5535260 :   bool want_inline = true;
     978      5535260 :   struct cgraph_node *callee = e->callee->ultimate_alias_target ();
     979      4190785 :   cgraph_node *to  = (e->caller->inlined_to
     980      5535260 :                       ? e->caller->inlined_to : e->caller);
     981              : 
     982              :   /* Allow this function to be called before can_inline_edge_p,
     983              :      since it's usually cheaper.  */
     984      5535260 :   if (cgraph_inline_failed_type (e->inline_failed) == CIF_FINAL_ERROR)
     985              :     want_inline = false;
     986      5535260 :   else if (DECL_DISREGARD_INLINE_LIMITS (callee->decl))
     987              :     return true;
     988      5529285 :   else if (!DECL_DECLARED_INLINE_P (callee->decl)
     989      5529285 :            && !opt_for_fn (e->caller->decl, flag_inline_small_functions))
     990              :     {
     991        52809 :       e->inline_failed = CIF_FUNCTION_NOT_INLINE_CANDIDATE;
     992        52809 :       want_inline = false;
     993              :     }
     994              : 
     995              :   /* Early return before lookup of summaries.  */
     996        52809 :   if (!want_inline)
     997              :     {
     998        52809 :       if (report)
     999        48546 :         report_inline_failed_reason (e);
    1000              :       return false;
    1001              :     }
    1002              : 
    1003      5476476 :   ipa_fn_summary *callee_info = ipa_fn_summaries->get (callee);
    1004      5476476 :   ipa_call_summary *call_info = ipa_call_summaries->get (e);
    1005              : 
    1006              :   /* Do fast and conservative check if the function can be good
    1007              :      inline candidate.  */
    1008      5476476 :   if ((!DECL_DECLARED_INLINE_P (callee->decl)
    1009      2053927 :       && (!e->count.ipa ().initialized_p ()
    1010        51106 :           || !e->maybe_hot_p (callee_info->time)))
    1011      7530118 :       && callee_info->min_size - call_info->call_stmt_size
    1012      2053642 :          > inline_insns_auto (e->caller, true, true))
    1013              :     {
    1014          107 :       e->inline_failed = CIF_MAX_INLINE_INSNS_AUTO_LIMIT;
    1015          107 :       want_inline = false;
    1016              :     }
    1017      5476369 :   else if ((DECL_DECLARED_INLINE_P (callee->decl)
    1018      2053820 :             || e->count.ipa ().nonzero_p ())
    1019      8899227 :            && callee_info->min_size - call_info->call_stmt_size
    1020      3422858 :               > inline_insns_single (e->caller, true, true))
    1021              :     {
    1022            0 :       e->inline_failed = (DECL_DECLARED_INLINE_P (callee->decl)
    1023            0 :                           ? CIF_MAX_INLINE_INSNS_SINGLE_LIMIT
    1024              :                           : CIF_MAX_INLINE_INSNS_AUTO_LIMIT);
    1025            0 :       want_inline = false;
    1026              :     }
    1027              :   else
    1028              :     {
    1029      5476369 :       int growth = estimate_edge_growth (e);
    1030      5476369 :       ipa_hints hints = estimate_edge_hints (e);
    1031              :       /* We have two independent groups of hints.  If one matches in each
    1032              :          of groups the limits are inreased.  If both groups matches, limit
    1033              :          is increased even more.  */
    1034      5476369 :       bool apply_hints = (hints & (INLINE_HINT_indirect_call
    1035              :                                    | INLINE_HINT_known_hot
    1036              :                                    | INLINE_HINT_loop_iterations
    1037              :                                    | INLINE_HINT_loop_stride));
    1038      5476369 :       bool apply_hints2 = (hints & INLINE_HINT_builtin_constant_p);
    1039              : 
    1040      5476369 :       if (growth <= opt_for_fn (to->decl,
    1041              :                                 param_max_inline_insns_size))
    1042              :         ;
    1043              :       /* Apply param_max_inline_insns_single limit.  Do not do so when
    1044              :          hints suggests that inlining given function is very profitable.
    1045              :          Avoid computation of big_speedup_p when not necessary to change
    1046              :          outcome of decision.  */
    1047      5337549 :       else if (DECL_DECLARED_INLINE_P (callee->decl)
    1048      3360734 :                && growth >= inline_insns_single (e->caller, apply_hints,
    1049              :                                                  apply_hints2)
    1050      6044317 :                && (apply_hints || apply_hints2
    1051       705545 :                    || growth >= inline_insns_single (e->caller, true,
    1052              :                                                      apply_hints2)
    1053       365288 :                    || !big_speedup_p (e)))
    1054              :         {
    1055       705417 :           e->inline_failed = CIF_MAX_INLINE_INSNS_SINGLE_LIMIT;
    1056       705417 :           want_inline = false;
    1057              :         }
    1058      4632132 :       else if (!DECL_DECLARED_INLINE_P (callee->decl)
    1059      1976815 :                && !opt_for_fn (e->caller->decl, flag_inline_functions)
    1060      4637483 :                && growth >= opt_for_fn (to->decl,
    1061              :                                         param_max_inline_insns_small))
    1062              :         {
    1063              :           /* growth_positive_p is expensive, always test it last.  */
    1064         5351 :           if (growth >= inline_insns_single (e->caller, false, false)
    1065         5351 :               || growth_positive_p (callee, e, growth))
    1066              :             {
    1067         4964 :               e->inline_failed = CIF_NOT_DECLARED_INLINED;
    1068         4964 :               want_inline = false;
    1069              :             }
    1070              :         }
    1071              :       /* Apply param_max_inline_insns_auto limit for functions not declared
    1072              :          inline.  Bypass the limit when speedup seems big.  */
    1073      4626781 :       else if (!DECL_DECLARED_INLINE_P (callee->decl)
    1074      1971464 :                && growth >= inline_insns_auto (e->caller, apply_hints,
    1075              :                                                apply_hints2)
    1076      5863006 :                && (apply_hints || apply_hints2
    1077      1220613 :                    || growth >= inline_insns_auto (e->caller, true,
    1078              :                                                    apply_hints2)
    1079       222031 :                    || !big_speedup_p (e)))
    1080              :         {
    1081              :           /* growth_positive_p is expensive, always test it last.  */
    1082      1225093 :           if (growth >= inline_insns_single (e->caller, false, false)
    1083      1225093 :               || growth_positive_p (callee, e, growth))
    1084              :             {
    1085      1142500 :               e->inline_failed = CIF_MAX_INLINE_INSNS_AUTO_LIMIT;
    1086      1142500 :               want_inline = false;
    1087              :             }
    1088              :         }
    1089              :       /* If call is cold, do not inline when function body would grow. */
    1090      3401688 :       else if (!e->maybe_hot_p (callee_speedup (e))
    1091      3401688 :                && (growth >= inline_insns_single (e->caller, false, false)
    1092       777147 :                    || growth_positive_p (callee, e, growth)))
    1093              :         {
    1094       698376 :           e->inline_failed = CIF_UNLIKELY_CALL;
    1095       698376 :           want_inline = false;
    1096              :         }
    1097              :     }
    1098      5476476 :   if (!want_inline && report)
    1099       609828 :     report_inline_failed_reason (e);
    1100              :   return want_inline;
    1101              : }
    1102              : 
    1103              : /* EDGE is self recursive edge.
    1104              :    We handle two cases - when function A is inlining into itself
    1105              :    or when function A is being inlined into another inliner copy of function
    1106              :    A within function B.
    1107              : 
    1108              :    In first case OUTER_NODE points to the toplevel copy of A, while
    1109              :    in the second case OUTER_NODE points to the outermost copy of A in B.
    1110              : 
    1111              :    In both cases we want to be extra selective since
    1112              :    inlining the call will just introduce new recursive calls to appear.  */
    1113              : 
    1114              : static bool
    1115        20160 : want_inline_self_recursive_call_p (struct cgraph_edge *edge,
    1116              :                                    struct cgraph_node *outer_node,
    1117              :                                    bool peeling,
    1118              :                                    int depth)
    1119              : {
    1120        20160 :   char const *reason = NULL;
    1121        20160 :   bool want_inline = true;
    1122        20160 :   sreal caller_freq = 1;
    1123        20160 :   int max_depth = opt_for_fn (outer_node->decl,
    1124              :                               param_max_inline_recursive_depth_auto);
    1125              : 
    1126        20160 :   if (DECL_DECLARED_INLINE_P (edge->caller->decl))
    1127         3043 :     max_depth = opt_for_fn (outer_node->decl,
    1128              :                             param_max_inline_recursive_depth);
    1129              : 
    1130        20160 :   if (!edge->maybe_hot_p ())
    1131              :     {
    1132              :       reason = "recursive call is cold";
    1133              :       want_inline = false;
    1134              :     }
    1135        19676 :   else if (depth > max_depth)
    1136              :     {
    1137              :       reason = "--param max-inline-recursive-depth exceeded.";
    1138              :       want_inline = false;
    1139              :     }
    1140        17437 :   else if (outer_node->inlined_to
    1141        21948 :            && (caller_freq = outer_node->callers->sreal_frequency ()) == 0)
    1142              :     {
    1143              :       reason = "caller frequency is 0";
    1144              :       want_inline = false;
    1145              :     }
    1146              : 
    1147        17437 :   if (!want_inline)
    1148              :     ;
    1149              :   /* Inlining of self recursive function into copy of itself within other
    1150              :      function is transformation similar to loop peeling.
    1151              : 
    1152              :      Peeling is profitable if we can inline enough copies to make probability
    1153              :      of actual call to the self recursive function very small.  Be sure that
    1154              :      the probability of recursion is small.
    1155              : 
    1156              :      We ensure that the frequency of recursing is at most 1 - (1/max_depth).
    1157              :      This way the expected number of recursion is at most max_depth.  */
    1158        17437 :   else if (peeling)
    1159              :     {
    1160         4511 :       sreal max_prob = (sreal)1 - ((sreal)1 / (sreal)max_depth);
    1161         4511 :       int i;
    1162        10001 :       for (i = 1; i < depth; i++)
    1163         5490 :         max_prob = max_prob * max_prob;
    1164         4511 :       if (edge->sreal_frequency () >= max_prob * caller_freq)
    1165              :         {
    1166         1615 :           reason = "frequency of recursive call is too large";
    1167         1615 :           want_inline = false;
    1168              :         }
    1169              :     }
    1170              :   /* Recursive inlining, i.e. equivalent of unrolling, is profitable if
    1171              :      recursion depth is large.  We reduce function call overhead and increase
    1172              :      chances that things fit in hardware return predictor.
    1173              : 
    1174              :      Recursive inlining might however increase cost of stack frame setup
    1175              :      actually slowing down functions whose recursion tree is wide rather than
    1176              :      deep.
    1177              : 
    1178              :      Deciding reliably on when to do recursive inlining without profile feedback
    1179              :      is tricky.  For now we disable recursive inlining when probability of self
    1180              :      recursion is low.
    1181              : 
    1182              :      Recursive inlining of self recursive call within loop also results in
    1183              :      large loop depths that generally optimize badly.  We may want to throttle
    1184              :      down inlining in those cases.  In particular this seems to happen in one
    1185              :      of libstdc++ rb tree methods.  */
    1186              :   else
    1187              :     {
    1188        12926 :       if (edge->sreal_frequency () * 100
    1189        12926 :           <= caller_freq
    1190        25852 :              * opt_for_fn (outer_node->decl,
    1191              :                            param_min_inline_recursive_probability))
    1192              :         {
    1193          806 :           reason = "frequency of recursive call is too small";
    1194          806 :           want_inline = false;
    1195              :         }
    1196              :     }
    1197        20160 :   if (!can_inline_edge_by_limits_p (edge, CAN_INLINE_FORCE_LIMITS | CAN_INLINE_REPORT))
    1198              :     {
    1199              :       reason = "inline limits exceeded for always_inline function";
    1200              :       want_inline = false;
    1201              :     }
    1202        20160 :   if (!want_inline && dump_enabled_p ())
    1203            7 :     dump_printf_loc (MSG_MISSED_OPTIMIZATION, edge->call_stmt,
    1204              :                      "   not inlining recursively: %s\n", reason);
    1205        20160 :   return want_inline;
    1206              : }
    1207              : 
    1208              : /* Return true when NODE has uninlinable caller;
    1209              :    set HAS_HOT_CALL if it has hot call.
    1210              :    Worker for cgraph_for_node_and_aliases.  */
    1211              : 
    1212              : static bool
    1213        77976 : check_callers (struct cgraph_node *node, void *has_hot_call)
    1214              : {
    1215        77976 :   struct cgraph_edge *e;
    1216       135672 :   for (e = node->callers; e; e = e->next_caller)
    1217              :     {
    1218        86138 :       if (!opt_for_fn (e->caller->decl, flag_inline_functions_called_once)
    1219        86138 :           || !opt_for_fn (e->caller->decl, optimize))
    1220              :         return true;
    1221        86138 :       if (!can_inline_edge_p (e, true))
    1222              :         return true;
    1223        86099 :       if (e->recursive_p ())
    1224              :         return true;
    1225        86099 :       if (!can_inline_edge_by_limits_p (e, CAN_INLINE_REPORT))
    1226              :         return true;
    1227              :       /* Inlining large functions to large loop depth is often harmful because
    1228              :          of register pressure it implies.  */
    1229        57768 :       if ((int)ipa_call_summaries->get (e)->loop_depth
    1230        57768 :           > param_inline_functions_called_once_loop_depth)
    1231              :         return true;
    1232              :       /* Do not produce gigantic functions.  */
    1233       105754 :       if (estimate_size_after_inlining (e->caller->inlined_to ?
    1234              :                                         e->caller->inlined_to : e->caller, e)
    1235        57768 :           > param_inline_functions_called_once_insns)
    1236              :         return true;
    1237        57696 :       if (!(*(bool *)has_hot_call) && e->maybe_hot_p ())
    1238        12020 :         *(bool *)has_hot_call = true;
    1239              :     }
    1240              :   return false;
    1241              : }
    1242              : 
    1243              : /* If NODE has a caller, return true.  */
    1244              : 
    1245              : static bool
    1246      2204388 : has_caller_p (struct cgraph_node *node, void *data ATTRIBUTE_UNUSED)
    1247              : {
    1248      2204388 :   if (node->callers)
    1249       691577 :     return true;
    1250              :   return false;
    1251              : }
    1252              : 
    1253              : /* Decide if inlining NODE would reduce unit size by eliminating
    1254              :    the offline copy of function.
    1255              :    When COLD is true the cold calls are considered, too.  */
    1256              : 
    1257              : static bool
    1258      5052771 : want_inline_function_to_all_callers_p (struct cgraph_node *node, bool cold)
    1259              : {
    1260      5052771 :   bool has_hot_call = false;
    1261              : 
    1262              :   /* Aliases gets inlined along with the function they alias.  */
    1263      5052771 :   if (node->alias)
    1264              :     return false;
    1265              :   /* Already inlined?  */
    1266      4972971 :   if (node->inlined_to)
    1267              :     return false;
    1268              :   /* Does it have callers?  */
    1269      2154086 :   if (!node->call_for_symbol_and_aliases (has_caller_p, NULL, true))
    1270              :     return false;
    1271              :   /* Inlining into all callers would increase size?  */
    1272       691577 :   if (growth_positive_p (node, NULL, INT_MIN) > 0)
    1273              :     return false;
    1274              :   /* All inlines must be possible.  */
    1275        72915 :   if (node->call_for_symbol_and_aliases (check_callers, &has_hot_call,
    1276              :                                          true))
    1277              :     return false;
    1278        44473 :   if (!cold && !has_hot_call)
    1279              :     return false;
    1280              :   return true;
    1281              : }
    1282              : 
    1283              : /* Return true if WHERE of SIZE is a possible candidate for wrapper heuristics
    1284              :    in estimate_edge_badness.  */
    1285              : 
    1286              : static bool
    1287       661359 : wrapper_heuristics_may_apply (struct cgraph_node *where, int size)
    1288              : {
    1289       661359 :   return size < (DECL_DECLARED_INLINE_P (where->decl)
    1290       661359 :                  ? inline_insns_single (where, false, false)
    1291       373916 :                  : inline_insns_auto (where, false, false));
    1292              : }
    1293              : 
    1294              : /* A cost model driving the inlining heuristics in a way so the edges with
    1295              :    smallest badness are inlined first.  After each inlining is performed
    1296              :    the costs of all caller edges of nodes affected are recomputed so the
    1297              :    metrics may accurately depend on values such as number of inlinable callers
    1298              :    of the function or function body size.  */
    1299              : 
    1300              : static sreal
    1301     10219620 : edge_badness (struct cgraph_edge *edge, bool dump)
    1302              : {
    1303     10219620 :   sreal badness;
    1304     10219620 :   int growth;
    1305     10219620 :   sreal edge_time, unspec_edge_time;
    1306     10219620 :   struct cgraph_node *callee = edge->callee->ultimate_alias_target ();
    1307     10219620 :   class ipa_fn_summary *callee_info = ipa_fn_summaries->get (callee);
    1308     10219620 :   ipa_hints hints;
    1309      7765988 :   cgraph_node *caller = (edge->caller->inlined_to
    1310     10219620 :                          ? edge->caller->inlined_to
    1311              :                          : edge->caller);
    1312              : 
    1313     10219620 :   growth = estimate_edge_growth (edge);
    1314     10219620 :   edge_time = estimate_edge_time (edge, &unspec_edge_time);
    1315     10219620 :   hints = estimate_edge_hints (edge);
    1316     10219620 :   gcc_checking_assert (edge_time >= 0);
    1317              :   /* Check that inlined time is better, but tolerate some roundoff issues.
    1318              :      FIXME: When callee profile drops to 0 we account calls more.  This
    1319              :      should be fixed by never doing that.  */
    1320     10219620 :   gcc_checking_assert ((edge_time * 100
    1321              :                         - callee_info->time * 101).to_int () <= 0
    1322              :                         || callee->count.ipa ().initialized_p ());
    1323     10219620 :   gcc_checking_assert (growth <= ipa_size_summaries->get (callee)->size);
    1324              : 
    1325     10219620 :   if (dump)
    1326              :     {
    1327          185 :       fprintf (dump_file, "    Badness calculation for %s -> %s\n",
    1328          185 :                edge->caller->dump_name (),
    1329          185 :                edge->callee->dump_name ());
    1330          185 :       fprintf (dump_file, "      size growth %i, time %f unspec %f ",
    1331              :                growth,
    1332              :                edge_time.to_double (),
    1333              :                unspec_edge_time.to_double ());
    1334          185 :       ipa_dump_hints (dump_file, hints);
    1335          185 :       if (big_speedup_p (edge))
    1336          151 :         fprintf (dump_file, " big_speedup");
    1337          185 :       fprintf (dump_file, "\n");
    1338              :     }
    1339              : 
    1340              :   /* Always prefer inlining saving code size.  */
    1341     10219620 :   if (growth <= 0)
    1342              :     {
    1343       527306 :       badness = (sreal) (-SREAL_MIN_SIG + growth) << (SREAL_MAX_EXP / 256);
    1344       527306 :       if (dump)
    1345          108 :         fprintf (dump_file, "      %f: Growth %d <= 0\n", badness.to_double (),
    1346              :                  growth);
    1347              :     }
    1348              :    /* Inlining into EXTERNAL functions is not going to change anything unless
    1349              :       they are themselves inlined.  */
    1350      9692314 :    else if (DECL_EXTERNAL (caller->decl))
    1351              :     {
    1352        45982 :       if (dump)
    1353            0 :         fprintf (dump_file, "      max: function is external\n");
    1354        45982 :       return sreal::max ();
    1355              :     }
    1356              :   /* When profile is available. Compute badness as:
    1357              : 
    1358              :                  time_saved * caller_count
    1359              :      goodness =  -------------------------------------------------
    1360              :                  growth_of_caller * overall_growth * combined_size
    1361              : 
    1362              :      badness = - goodness
    1363              : 
    1364              :      Again use negative value to make calls with profile appear hotter
    1365              :      then calls without.
    1366              :   */
    1367      9646332 :   else if (opt_for_fn (caller->decl, flag_guess_branch_prob)
    1368      9646332 :            || caller->count.ipa ().nonzero_p ())
    1369              :     {
    1370      9644976 :       sreal numerator, denominator;
    1371      9644976 :       int overall_growth;
    1372      9644976 :       sreal freq = edge->sreal_frequency ();
    1373              : 
    1374      9644976 :       numerator = inlining_speedup (edge, freq, unspec_edge_time, edge_time);
    1375      9644976 :       if (numerator <= 0)
    1376         8855 :         numerator = ((sreal) 1 >> 8);
    1377      9644976 :       if (caller->count.ipa ().nonzero_p ())
    1378          204 :         numerator *= caller->count.ipa ().to_gcov_type ();
    1379      9644772 :       else if (caller->count.ipa ().initialized_p ())
    1380          926 :         numerator = numerator >> 11;
    1381      9644976 :       denominator = growth;
    1382              : 
    1383      9644976 :       overall_growth = callee_info->growth;
    1384              : 
    1385              :       /* Look for inliner wrappers of the form:
    1386              : 
    1387              :          inline_caller ()
    1388              :            {
    1389              :              do_fast_job...
    1390              :              if (need_more_work)
    1391              :                noninline_callee ();
    1392              :            }
    1393              :          Without penalizing this case, we usually inline noninline_callee
    1394              :          into the inline_caller because overall_growth is small preventing
    1395              :          further inlining of inline_caller.
    1396              : 
    1397              :          Penalize only callgraph edges to functions with small overall
    1398              :          growth ...
    1399              :         */
    1400      9644976 :       if (growth > overall_growth
    1401              :           /* ... and having only one caller which is not inlined ... */
    1402      2163175 :           && callee_info->single_caller
    1403      1208554 :           && !edge->caller->inlined_to
    1404              :           /* ... and edges executed only conditionally ... */
    1405       831125 :           && freq < 1
    1406              :           /* ... consider case where callee is not inline but caller is ... */
    1407      9999022 :           && ((!DECL_DECLARED_INLINE_P (edge->callee->decl)
    1408        93946 :                && DECL_DECLARED_INLINE_P (caller->decl))
    1409              :               /* ... or when early optimizers decided to split and edge
    1410              :                  frequency still indicates splitting is a win ... */
    1411       345588 :               || (callee->split_part && !caller->split_part
    1412        95474 :                   && freq * 100
    1413      9835509 :                          < opt_for_fn (caller->decl,
    1414              :                                        param_partial_inlining_entry_probability)
    1415              :                   /* ... and do not overwrite user specified hints.   */
    1416        95059 :                   && (!DECL_DECLARED_INLINE_P (edge->callee->decl)
    1417        70721 :                       || DECL_DECLARED_INLINE_P (caller->decl)))))
    1418              :         {
    1419       102079 :           ipa_fn_summary *caller_info = ipa_fn_summaries->get (caller);
    1420       102079 :           int caller_growth = caller_info->growth;
    1421              : 
    1422              :           /* Only apply the penalty when caller looks like inline candidate,
    1423              :              and it is not called once.  */
    1424        54810 :           if (!caller_info->single_caller && overall_growth < caller_growth
    1425        52349 :               && caller_info->inlinable
    1426       154380 :               && wrapper_heuristics_may_apply
    1427        52301 :                  (caller, ipa_size_summaries->get (caller)->size))
    1428              :             {
    1429        41966 :               if (dump)
    1430            1 :                 fprintf (dump_file,
    1431              :                          "     Wrapper penalty. Increasing growth %i to %i\n",
    1432              :                          overall_growth, caller_growth);
    1433              :               overall_growth = caller_growth;
    1434              :             }
    1435              :         }
    1436      9644976 :       if (overall_growth > 0)
    1437              :         {
    1438              :           /* Strongly prefer functions with few callers that can be inlined
    1439              :              fully.  The square root here leads to smaller binaries at average.
    1440              :              Watch however for extreme cases and return to linear function
    1441              :              when growth is large.  */
    1442      8215703 :           if (overall_growth < 256)
    1443      4519631 :             overall_growth *= overall_growth;
    1444              :           else
    1445      3696072 :             overall_growth += 256 * 256 - 256;
    1446      8215703 :           denominator *= overall_growth;
    1447              :         }
    1448      9644976 :       denominator *= ipa_size_summaries->get (caller)->size + growth;
    1449              : 
    1450      9644976 :       badness = - numerator / denominator;
    1451              : 
    1452      9644976 :       if (dump)
    1453              :         {
    1454          308 :           fprintf (dump_file,
    1455              :                    "      %f: guessed profile. frequency %f, count %" PRId64
    1456              :                    " caller count %" PRId64
    1457              :                    " time saved %f"
    1458              :                    " overall growth %i (current) %i (original)"
    1459              :                    " %i (compensated)\n",
    1460              :                    badness.to_double (),
    1461              :                    freq.to_double (),
    1462           77 :                    edge->count.ipa ().initialized_p ()
    1463            0 :                    ? edge->count.ipa ().to_gcov_type () : -1,
    1464           77 :                    caller->count.ipa ().initialized_p ()
    1465            0 :                    ? caller->count.ipa ().to_gcov_type () : -1,
    1466          154 :                    inlining_speedup (edge, freq, unspec_edge_time,
    1467              :                                      edge_time).to_double (),
    1468              :                    estimate_growth (callee),
    1469              :                    callee_info->growth, overall_growth);
    1470              :         }
    1471              :     }
    1472              :   /* When function local profile is not available or it does not give
    1473              :      useful information (i.e. frequency is zero), base the cost on
    1474              :      loop nest and overall size growth, so we optimize for overall number
    1475              :      of functions fully inlined in program.  */
    1476              :   else
    1477              :     {
    1478         1356 :       int nest = MIN (ipa_call_summaries->get (edge)->loop_depth, 8);
    1479         1356 :       badness = growth;
    1480              : 
    1481              :       /* Decrease badness if call is nested.  */
    1482         1356 :       if (badness > 0)
    1483         1356 :         badness = badness >> nest;
    1484              :       else
    1485            0 :         badness = badness << nest;
    1486         1356 :       if (dump)
    1487            0 :         fprintf (dump_file, "      %f: no profile. nest %i\n",
    1488              :                  badness.to_double (), nest);
    1489              :     }
    1490     10173638 :   gcc_checking_assert (badness != 0);
    1491              : 
    1492     10173638 :   if (edge->recursive_p ())
    1493        19089 :     badness = badness.shift (badness > 0 ? 4 : -4);
    1494     10173638 :   if ((hints & (INLINE_HINT_indirect_call
    1495              :                 | INLINE_HINT_loop_iterations
    1496              :                 | INLINE_HINT_loop_stride))
    1497      9351047 :       || callee_info->growth <= 0)
    1498      4865609 :     badness = badness.shift (badness > 0 ? -2 : 2);
    1499     10173638 :   if (hints & INLINE_HINT_builtin_constant_p)
    1500        24228 :     badness = badness.shift (badness > 0 ? -4 : 4);
    1501     10173638 :   if (hints & (INLINE_HINT_same_scc))
    1502        72340 :     badness = badness.shift (badness > 0 ? 3 : -3);
    1503     10137467 :   else if (hints & (INLINE_HINT_in_scc))
    1504       172894 :     badness = badness.shift (badness > 0 ? 2 : -2);
    1505     10051020 :   else if (hints & (INLINE_HINT_cross_module))
    1506         3970 :     badness = badness.shift (badness > 0 ? 1 : -1);
    1507     10173638 :   if (DECL_DISREGARD_INLINE_LIMITS (callee->decl))
    1508        17896 :     badness = badness.shift (badness > 0 ? -4 : 4);
    1509     10164690 :   else if ((hints & INLINE_HINT_declared_inline))
    1510     15356561 :     badness = badness.shift (badness > 0 ? -3 : 3);
    1511     10173638 :   if (dump)
    1512          185 :     fprintf (dump_file, "      Adjusted by hints %f\n", badness.to_double ());
    1513     10173638 :   return badness;
    1514              : }
    1515              : 
    1516              : /* Recompute badness of EDGE and update its key in HEAP if needed.  */
    1517              : static inline void
    1518      5467990 : update_edge_key (edge_heap_t *heap, struct cgraph_edge *edge)
    1519              : {
    1520      5467990 :   sreal badness = edge_badness (edge, false);
    1521      5467990 :   if (edge->aux)
    1522              :     {
    1523      4306813 :       edge_heap_node_t *n = (edge_heap_node_t *) edge->aux;
    1524      4306813 :       gcc_checking_assert (n->get_data () == edge);
    1525              : 
    1526              :       /* fibonacci_heap::replace_key does busy updating of the
    1527              :          heap that is unnecessarily expensive.
    1528              :          We do lazy increases: after extracting minimum if the key
    1529              :          turns out to be out of date, it is re-inserted into heap
    1530              :          with correct value.  */
    1531      4306813 :       if (badness < n->get_key ().badness)
    1532              :         {
    1533       936841 :           if (dump_file && (dump_flags & TDF_DETAILS))
    1534              :             {
    1535           90 :               fprintf (dump_file,
    1536              :                        "  decreasing badness %s -> %s, %f to %f\n",
    1537           45 :                        edge->caller->dump_name (),
    1538           45 :                        edge->callee->dump_name (),
    1539           90 :                        n->get_key ().badness.to_double (),
    1540              :                        badness.to_double ());
    1541              :             }
    1542       936841 :           inline_badness b (edge, badness);
    1543       936841 :           heap->decrease_key (n, b);
    1544              :         }
    1545              :     }
    1546              :   else
    1547              :     {
    1548      1161177 :        if (dump_file && (dump_flags & TDF_DETAILS))
    1549              :          {
    1550          338 :            fprintf (dump_file,
    1551              :                     "  enqueuing call %s -> %s, badness %f\n",
    1552          169 :                     edge->caller->dump_name (),
    1553          169 :                     edge->callee->dump_name (),
    1554              :                     badness.to_double ());
    1555              :          }
    1556      1161177 :       inline_badness b (edge, badness);
    1557      1161177 :       edge->aux = heap->insert (b, edge);
    1558              :     }
    1559      5467990 : }
    1560              : 
    1561              : 
    1562              : /* NODE was inlined.
    1563              :    All caller edges needs to be reset because
    1564              :    size estimates change. Similarly callees needs reset
    1565              :    because better context may be known.  */
    1566              : 
    1567              : static void
    1568       992716 : reset_edge_caches (struct cgraph_node *node)
    1569              : {
    1570       992716 :   struct cgraph_edge *edge;
    1571       992716 :   struct cgraph_edge *e = node->callees;
    1572       992716 :   struct cgraph_node *where = node;
    1573       992716 :   struct ipa_ref *ref;
    1574              : 
    1575       992716 :   if (where->inlined_to)
    1576       927212 :     where = where->inlined_to;
    1577              : 
    1578       992716 :   reset_node_cache (where);
    1579              : 
    1580       992716 :   if (edge_growth_cache != NULL)
    1581      3500630 :     for (edge = where->callers; edge; edge = edge->next_caller)
    1582      2510172 :       if (edge->inline_failed)
    1583      2510172 :         edge_growth_cache->remove (edge);
    1584              : 
    1585      1053094 :   FOR_EACH_ALIAS (where, ref)
    1586       120756 :     reset_edge_caches (dyn_cast <cgraph_node *> (ref->referring));
    1587              : 
    1588       992716 :   if (!e)
    1589              :     return;
    1590              : 
    1591      3192001 :   while (true)
    1592      3192001 :     if (!e->inline_failed && e->callee->callees)
    1593              :       e = e->callee->callees;
    1594              :     else
    1595              :       {
    1596      2545622 :         if (edge_growth_cache != NULL && e->inline_failed)
    1597      2300119 :           edge_growth_cache->remove (e);
    1598      2545622 :         if (e->next_callee)
    1599              :           e = e->next_callee;
    1600              :         else
    1601              :           {
    1602      1477366 :             do
    1603              :               {
    1604      1477366 :                 if (e->caller == node)
    1605              :                   return;
    1606       646379 :                 e = e->caller->callers;
    1607              :               }
    1608       646379 :             while (!e->next_callee);
    1609              :             e = e->next_callee;
    1610              :           }
    1611              :       }
    1612              : }
    1613              : 
    1614              : /* Recompute HEAP nodes for each of caller of NODE.
    1615              :    UPDATED_NODES track nodes we already visited, to avoid redundant work.
    1616              :    When CHECK_INLINABLITY_FOR is set, re-check for specified edge that
    1617              :    it is inlinable. Otherwise check all edges.  */
    1618              : 
    1619              : static void
    1620       990152 : update_caller_keys (edge_heap_t *heap, struct cgraph_node *node,
    1621              :                     bitmap updated_nodes,
    1622              :                     struct cgraph_edge *check_inlinablity_for)
    1623              : {
    1624       990152 :   struct cgraph_edge *edge;
    1625       990152 :   struct ipa_ref *ref;
    1626              : 
    1627       990152 :   if ((!node->alias && !ipa_fn_summaries->get (node)->inlinable)
    1628       977817 :       || node->inlined_to)
    1629        12335 :     return;
    1630       977817 :   if (!bitmap_set_bit (updated_nodes, node->get_summary_id ()))
    1631              :     return;
    1632              : 
    1633      1037694 :   FOR_EACH_ALIAS (node, ref)
    1634              :     {
    1635        59877 :       struct cgraph_node *alias = dyn_cast <cgraph_node *> (ref->referring);
    1636        59877 :       update_caller_keys (heap, alias, updated_nodes, check_inlinablity_for);
    1637              :     }
    1638              : 
    1639      3379885 :   for (edge = node->callers; edge; edge = edge->next_caller)
    1640      2402068 :     if (edge->inline_failed)
    1641              :       {
    1642      2402068 :         if (!check_inlinablity_for
    1643      2402068 :             || check_inlinablity_for == edge)
    1644              :           {
    1645      2402068 :             if (can_inline_edge_p (edge, false)
    1646      2368142 :                 && want_inline_small_function_p (edge, false)
    1647      3043815 :                 && can_inline_edge_by_limits_p (edge, 0))
    1648       635875 :               update_edge_key (heap, edge);
    1649      1766193 :             else if (edge->aux)
    1650              :               {
    1651       102479 :                 report_inline_failed_reason (edge);
    1652       102479 :                 heap->delete_node ((edge_heap_node_t *) edge->aux);
    1653       102479 :                 edge->aux = NULL;
    1654              :               }
    1655              :           }
    1656            0 :         else if (edge->aux)
    1657            0 :           update_edge_key (heap, edge);
    1658              :       }
    1659              : }
    1660              : 
    1661              : /* Recompute HEAP nodes for each uninlined call in NODE
    1662              :    If UPDATE_SINCE is non-NULL check if edges called within that function
    1663              :    are inlinable (typically UPDATE_SINCE is the inline clone we introduced
    1664              :    where all edges have new context).
    1665              : 
    1666              :    This is used when we know that edge badnesses are going only to increase
    1667              :    (we introduced new call site) and thus all we need is to insert newly
    1668              :    created edges into heap.  */
    1669              : 
    1670              : static void
    1671       930344 : update_callee_keys (edge_heap_t *heap, struct cgraph_node *node,
    1672              :                     struct cgraph_node *update_since,
    1673              :                     bitmap updated_nodes)
    1674              : {
    1675       930344 :   struct cgraph_edge *e = node->callees;
    1676       930344 :   bool check_inlinability = update_since == node;
    1677              : 
    1678       930344 :   if (!e)
    1679              :     return;
    1680     29267849 :   while (true)
    1681     29267849 :     if (!e->inline_failed && e->callee->callees)
    1682              :       {
    1683      5349330 :         if (e->callee == update_since)
    1684       433667 :           check_inlinability = true;
    1685     28370780 :         e = e->callee->callees;
    1686              :       }
    1687              :     else
    1688              :       {
    1689     23918519 :         enum availability avail;
    1690     23918519 :         struct cgraph_node *callee;
    1691     23918519 :         if (!check_inlinability)
    1692              :           {
    1693     21560975 :             if (e->aux
    1694     25044486 :                 && !bitmap_bit_p (updated_nodes,
    1695      3483511 :                                   e->callee->ultimate_alias_target
    1696      3483511 :                                     (&avail, e->caller)->get_summary_id ()))
    1697      3483505 :               update_edge_key (heap, e);
    1698              :           }
    1699              :         /* We do not reset callee growth cache here.  Since we added a new call,
    1700              :            growth should have just increased and consequently badness metric
    1701              :            don't need updating.  */
    1702      2357544 :         else if (e->inline_failed
    1703      2257838 :                  && (callee = e->callee->ultimate_alias_target (&avail,
    1704      2257838 :                                                                 e->caller))
    1705      2257838 :                  && avail >= AVAIL_AVAILABLE
    1706       612006 :                  && ipa_fn_summaries->get (callee) != NULL
    1707       611990 :                  && ipa_fn_summaries->get (callee)->inlinable
    1708      2955240 :                  && !bitmap_bit_p (updated_nodes, callee->get_summary_id ()))
    1709              :           {
    1710       597696 :             if (can_inline_edge_p (e, false)
    1711       592338 :                 && want_inline_small_function_p (e, false)
    1712       970630 :                 && can_inline_edge_by_limits_p (e, 0))
    1713              :               {
    1714       372111 :                 gcc_checking_assert (check_inlinability || can_inline_edge_p (e, false));
    1715              :                 gcc_checking_assert (check_inlinability || e->aux);
    1716       372111 :                 update_edge_key (heap, e);
    1717              :               }
    1718       225585 :             else if (e->aux)
    1719              :               {
    1720         6997 :                 report_inline_failed_reason (e);
    1721         6997 :                 heap->delete_node ((edge_heap_node_t *) e->aux);
    1722         6997 :                 e->aux = NULL;
    1723              :               }
    1724              :           }
    1725              :         /* In case we redirected to unreachable node we only need to remove the
    1726              :            fibheap entry.  */
    1727      1759848 :         else if (e->aux)
    1728              :           {
    1729         3515 :             heap->delete_node ((edge_heap_node_t *) e->aux);
    1730         3515 :             e->aux = NULL;
    1731              :           }
    1732     23918519 :         if (e->next_callee)
    1733              :           e = e->next_callee;
    1734              :         else
    1735              :           {
    1736      6246399 :             do
    1737              :               {
    1738      6246399 :                 if (e->caller == node)
    1739       897069 :                   return;
    1740      5349330 :                 if (e->caller == update_since)
    1741       433667 :                   check_inlinability = false;
    1742      5349330 :                 e = e->caller->callers;
    1743              :               }
    1744      5349330 :             while (!e->next_callee);
    1745              :             e = e->next_callee;
    1746              :           }
    1747              :       }
    1748              : }
    1749              : 
    1750              : /* Enqueue all recursive calls from NODE into priority queue depending on
    1751              :    how likely we want to recursively inline the call.  */
    1752              : 
    1753              : static void
    1754        22514 : lookup_recursive_calls (struct cgraph_node *node, struct cgraph_node *where,
    1755              :                         edge_heap_t *heap)
    1756              : {
    1757        22514 :   struct cgraph_edge *e;
    1758        22514 :   enum availability avail;
    1759              : 
    1760        62660 :   for (e = where->callees; e; e = e->next_callee)
    1761        40146 :     if (e->callee == node
    1762        40146 :         || (e->callee->ultimate_alias_target (&avail, e->caller) == node
    1763         1193 :             && avail > AVAIL_INTERPOSABLE))
    1764              :     {
    1765        16473 :       inline_badness b (e, -e->sreal_frequency ());
    1766        16473 :       heap->insert (b, e);
    1767              :     }
    1768        62660 :   for (e = where->callees; e; e = e->next_callee)
    1769        40146 :     if (!e->inline_failed)
    1770         8353 :       lookup_recursive_calls (node, e->callee, heap);
    1771        22514 : }
    1772              : 
    1773              : /* Decide on recursive inlining: in the case function has recursive calls,
    1774              :    inline until body size reaches given argument.  If any new indirect edges
    1775              :    are discovered in the process, add them to *NEW_EDGES, unless NEW_EDGES
    1776              :    is NULL.  */
    1777              : 
    1778              : static bool
    1779         2041 : recursive_inlining (struct cgraph_edge *edge,
    1780              :                     vec<cgraph_edge *> *new_edges)
    1781              : {
    1782         1462 :   cgraph_node *to  = (edge->caller->inlined_to
    1783         2041 :                       ? edge->caller->inlined_to : edge->caller);
    1784         2041 :   int limit = opt_for_fn (to->decl,
    1785              :                           param_max_inline_insns_recursive_auto);
    1786         2041 :   inline_badness b (edge, sreal::min ());
    1787         2041 :   edge_heap_t heap (b);
    1788         2041 :   struct cgraph_node *node;
    1789         2041 :   struct cgraph_edge *e;
    1790         2041 :   struct cgraph_node *master_clone = NULL, *next;
    1791         2041 :   int depth = 0;
    1792         2041 :   int n = 0;
    1793              : 
    1794         2041 :   node = edge->caller;
    1795         2041 :   if (node->inlined_to)
    1796          579 :     node = node->inlined_to;
    1797              : 
    1798         2041 :   if (DECL_DECLARED_INLINE_P (node->decl))
    1799          446 :     limit = opt_for_fn (to->decl, param_max_inline_insns_recursive);
    1800              : 
    1801              :   /* Make sure that function is small enough to be considered for inlining.  */
    1802         2041 :   if (estimate_size_after_inlining (node, edge)  >= limit)
    1803              :     return false;
    1804         2041 :   lookup_recursive_calls (node, node, &heap);
    1805         2041 :   if (heap.empty ())
    1806              :     return false;
    1807              : 
    1808         2041 :   if (dump_file)
    1809            4 :     fprintf (dump_file,
    1810              :              "  Performing recursive inlining on %s\n", node->dump_name ());
    1811              : 
    1812              :   /* Do the inlining and update list of recursive call during process.  */
    1813        17265 :   while (!heap.empty ())
    1814              :     {
    1815        15252 :       struct cgraph_edge *curr = heap.extract_min ();
    1816        15252 :       struct cgraph_node *cnode, *dest = curr->callee;
    1817              : 
    1818        15252 :       if (!can_inline_edge_p (curr, true)
    1819        15252 :           || !can_inline_edge_by_limits_p (curr, CAN_INLINE_REPORT | CAN_INLINE_FORCE_LIMITS))
    1820            0 :         continue;
    1821              : 
    1822              :       /* MASTER_CLONE is produced in the case we already started modified
    1823              :          the function. Be sure to redirect edge to the original body before
    1824              :          estimating growths otherwise we will be seeing growths after inlining
    1825              :          the already modified body.  */
    1826        15252 :       if (master_clone)
    1827              :         {
    1828        13105 :           curr->redirect_callee (master_clone);
    1829        13105 :           if (edge_growth_cache != NULL)
    1830        13105 :             edge_growth_cache->remove (curr);
    1831              :         }
    1832              : 
    1833        15252 :       if (estimate_size_after_inlining (node, curr) > limit)
    1834              :         {
    1835           28 :           curr->redirect_callee (dest);
    1836           28 :           if (edge_growth_cache != NULL)
    1837           28 :             edge_growth_cache->remove (curr);
    1838              :           break;
    1839              :         }
    1840              : 
    1841        15224 :       depth = 1;
    1842        15224 :       for (cnode = curr->caller;
    1843        79145 :            cnode->inlined_to; cnode = cnode->callers->caller)
    1844       127842 :         if (node->decl
    1845        63921 :             == curr->callee->ultimate_alias_target ()->decl)
    1846        63921 :           depth++;
    1847              : 
    1848        15224 :       if (!want_inline_self_recursive_call_p (curr, node, false, depth))
    1849              :         {
    1850         3104 :           curr->redirect_callee (dest);
    1851         3104 :           if (edge_growth_cache != NULL)
    1852         3104 :             edge_growth_cache->remove (curr);
    1853         3104 :           continue;
    1854              :         }
    1855              : 
    1856        12120 :       if (dump_file)
    1857              :         {
    1858           14 :           fprintf (dump_file,
    1859              :                    "   Inlining call of depth %i", depth);
    1860           28 :           if (node->count.nonzero_p () && curr->count.initialized_p ())
    1861              :             {
    1862            2 :               fprintf (dump_file, " called approx. %.2f times per call",
    1863            2 :                        (double)curr->count.to_gcov_type ()
    1864            2 :                        / node->count.to_gcov_type ());
    1865              :             }
    1866           14 :           fprintf (dump_file, "\n");
    1867              :         }
    1868        12120 :       if (!master_clone)
    1869              :         {
    1870              :           /* We need original clone to copy around.  */
    1871         1670 :           master_clone = node->create_clone (node->decl, node->count,
    1872         1670 :             false, vNULL, true, NULL, NULL, NULL);
    1873         4782 :           for (e = master_clone->callees; e; e = e->next_callee)
    1874         3112 :             if (!e->inline_failed)
    1875          511 :               clone_inlined_nodes (e, true, true, false, NULL);
    1876         1670 :           curr->redirect_callee (master_clone);
    1877         1670 :           if (edge_growth_cache != NULL)
    1878         1670 :             edge_growth_cache->remove (curr);
    1879              :         }
    1880              : 
    1881        12120 :       inline_call (curr, false, new_edges, &overall_size, true);
    1882        12120 :       reset_node_cache (node);
    1883        12120 :       lookup_recursive_calls (node, curr->callee, &heap);
    1884        12120 :       n++;
    1885              :     }
    1886              : 
    1887         2041 :   if (!heap.empty () && dump_file)
    1888            0 :     fprintf (dump_file, "    Recursive inlining growth limit met.\n");
    1889              : 
    1890         2041 :   if (!master_clone)
    1891              :     return false;
    1892              : 
    1893         1670 :   if (dump_enabled_p ())
    1894            4 :     dump_printf_loc (MSG_NOTE, edge->call_stmt,
    1895              :                      "\n   Inlined %i times, "
    1896              :                      "body grown from size %i to %i, time %f to %f\n", n,
    1897            4 :                      ipa_size_summaries->get (master_clone)->size,
    1898            4 :                      ipa_size_summaries->get (node)->size,
    1899            4 :                      ipa_fn_summaries->get (master_clone)->time.to_double (),
    1900            4 :                      ipa_fn_summaries->get (node)->time.to_double ());
    1901              : 
    1902              :   /* Remove master clone we used for inlining.  We rely that clones inlined
    1903              :      into master clone gets queued just before master clone so we don't
    1904              :      need recursion.  */
    1905        19670 :   for (node = symtab->first_function (); node != master_clone;
    1906        18000 :        node = next)
    1907              :     {
    1908        18000 :       next = symtab->next_function (node);
    1909        18000 :       if (node->inlined_to == master_clone)
    1910          974 :         node->remove ();
    1911              :     }
    1912         1670 :   master_clone->remove ();
    1913         1670 :   return true;
    1914         2041 : }
    1915              : 
    1916              : 
    1917              : /* Given whole compilation unit estimate of INSNS, compute how large we can
    1918              :    allow the unit to grow.  */
    1919              : 
    1920              : static int64_t
    1921      1045296 : compute_max_insns (cgraph_node *node, int insns)
    1922              : {
    1923      1045296 :   int max_insns = insns;
    1924      1045296 :   if (max_insns < opt_for_fn (node->decl, param_large_unit_insns))
    1925              :     max_insns = opt_for_fn (node->decl, param_large_unit_insns);
    1926              : 
    1927      1045296 :   return ((int64_t) max_insns
    1928      1045296 :           * (100 + opt_for_fn (node->decl, param_inline_unit_growth)) / 100);
    1929              : }
    1930              : 
    1931              : 
    1932              : /* Compute badness of all edges in NEW_EDGES and add them to the HEAP.  */
    1933              : 
    1934              : static void
    1935       928857 : add_new_edges_to_heap (edge_heap_t *heap, vec<cgraph_edge *> &new_edges)
    1936              : {
    1937       931626 :   while (new_edges.length () > 0)
    1938              :     {
    1939         2769 :       struct cgraph_edge *edge = new_edges.pop ();
    1940              : 
    1941         2769 :       gcc_assert (!edge->aux);
    1942         2769 :       gcc_assert (edge->callee);
    1943         2769 :       if (edge->inline_failed
    1944         2769 :           && can_inline_edge_p (edge, true)
    1945         1294 :           && want_inline_small_function_p (edge, true)
    1946         3691 :           && can_inline_edge_by_limits_p (edge, CAN_INLINE_REPORT))
    1947              :         {
    1948          922 :           inline_badness b (edge, edge_badness (edge, false));
    1949          922 :           edge->aux = heap->insert (b, edge);
    1950              :         }
    1951              :     }
    1952       928857 : }
    1953              : 
    1954              : /* Remove EDGE from the fibheap.  */
    1955              : 
    1956              : static void
    1957         8055 : heap_edge_removal_hook (struct cgraph_edge *e, void *data)
    1958              : {
    1959         8055 :   if (e->aux)
    1960              :     {
    1961           37 :       ((edge_heap_t *)data)->delete_node ((edge_heap_node_t *)e->aux);
    1962           37 :       e->aux = NULL;
    1963              :     }
    1964         8055 : }
    1965              : 
    1966              : /* Return true if speculation of edge E seems useful.
    1967              :    If ANTICIPATE_INLINING is true, be conservative and hope that E
    1968              :    may get inlined.  */
    1969              : 
    1970              : bool
    1971       123024 : speculation_useful_p (struct cgraph_edge *e, bool anticipate_inlining)
    1972              : {
    1973              :   /* If we have already decided to inline the edge, it seems useful.
    1974              :      Also if ipa-cp or other pass worked hard enough to produce a clone,
    1975              :      we already decided this is a good idea.  */
    1976       123024 :   if (!e->inline_failed
    1977        35359 :       || e->callee->clone_of)
    1978              :     return true;
    1979              : 
    1980        34606 :   enum availability avail;
    1981        34606 :   struct cgraph_node *target = e->callee->ultimate_alias_target (&avail,
    1982              :                                                                  e->callee);
    1983              : 
    1984        34606 :   gcc_assert (e->speculative && !e->indirect_unknown_callee);
    1985              : 
    1986              :   /* Even if call statement is not hot, we can still have useful speculation
    1987              :      in cases where a lot of time is spent is callee.
    1988              :      Do not check maybe_hot_p.  */
    1989        34606 :   if (!e->count.nonzero_p ())
    1990              :     return false;
    1991              : 
    1992              :   /* See if IP optimizations found something potentially useful about the
    1993              :      function.  Do this only if the call seems hot since this is about
    1994              :      optimizing the code surrounding call site rahter than improving
    1995              :      callee.  */
    1996        34564 :   if (avail >= AVAIL_AVAILABLE && e->maybe_hot_p ())
    1997              :     {
    1998        33618 :       int ecf_flags = flags_from_decl_or_type (target->decl);
    1999        33618 :       if (ecf_flags & ECF_CONST)
    2000              :         {
    2001          488 :           if (!(e->speculative_call_indirect_edge ()->indirect_info
    2002          488 :                 ->ecf_flags & ECF_CONST))
    2003              :             return true;
    2004              :         }
    2005        33130 :       else if (ecf_flags & ECF_PURE)
    2006              :         {
    2007         4188 :           if (!(e->speculative_call_indirect_edge ()->indirect_info
    2008         4188 :                 ->ecf_flags & ECF_PURE))
    2009              :             return true;
    2010              :         }
    2011        28942 :       else if (get_modref_function_summary (target))
    2012              :         return true;
    2013              :     }
    2014              :   /* If we did not managed to inline the function nor redirect
    2015              :      to an ipa-cp clone (that are seen by having local flag set),
    2016              :      it is probably pointless to inline it unless hardware is missing
    2017              :      indirect call predictor.
    2018              : 
    2019              :      At this point we know we will not dispatch into faster version of
    2020              :      callee, so if call itself is not hot, we definitely can give up
    2021              :      speculating.  */
    2022        12452 :   if (!anticipate_inlining && (!target->local || !e->maybe_hot_p ()))
    2023              :     return false;
    2024              :   /* For overwritable targets there is not much to do.  */
    2025         8455 :   if (!can_inline_edge_p (e, false)
    2026         8455 :       || !can_inline_edge_by_limits_p (e, CAN_INLINE_DISREGARD_LIMITS))
    2027            6 :     return false;
    2028              :   /* OK, speculation seems interesting.  */
    2029              :   return true;
    2030              : }
    2031              : 
    2032              : /* We know that EDGE is not going to be inlined.
    2033              :    See if we can remove speculation.  */
    2034              : 
    2035              : static void
    2036       120104 : resolve_noninline_speculation (edge_heap_t *edge_heap, struct cgraph_edge *edge)
    2037              : {
    2038       120104 :   if (edge->speculative && !speculation_useful_p (edge, false))
    2039              :     {
    2040          981 :       struct cgraph_node *node = edge->caller;
    2041          976 :       struct cgraph_node *where = node->inlined_to
    2042          981 :                                   ? node->inlined_to : node;
    2043          981 :       auto_bitmap updated_nodes;
    2044              : 
    2045          981 :       if (edge->count.ipa ().initialized_p ())
    2046            0 :         spec_rem += edge->count.ipa ();
    2047          981 :       cgraph_edge::resolve_speculation (edge);
    2048          981 :       reset_edge_caches (where);
    2049          981 :       ipa_update_overall_fn_summary (where);
    2050          981 :       update_caller_keys (edge_heap, where,
    2051              :                           updated_nodes, NULL);
    2052          981 :       update_callee_keys (edge_heap, where, NULL,
    2053              :                           updated_nodes);
    2054          981 :     }
    2055       120104 : }
    2056              : 
    2057              : /* Return true if NODE should be accounted for overall size estimate.
    2058              :    Skip all nodes optimized for size so we can measure the growth of hot
    2059              :    part of program no matter of the padding.  */
    2060              : 
    2061              : bool
    2062      3839011 : inline_account_function_p (struct cgraph_node *node)
    2063              : {
    2064      3839011 :    return (!DECL_EXTERNAL (node->decl)
    2065      3645285 :            && !opt_for_fn (node->decl, optimize_size)
    2066      7387905 :            && node->frequency != NODE_FREQUENCY_UNLIKELY_EXECUTED);
    2067              : }
    2068              : 
    2069              : /* Count number of callers of NODE and store it into DATA (that
    2070              :    points to int.  Worker for cgraph_for_node_and_aliases.  */
    2071              : 
    2072              : static bool
    2073      1504212 : sum_callers (struct cgraph_node *node, void *data)
    2074              : {
    2075      1504212 :   struct cgraph_edge *e;
    2076      1504212 :   int *num_calls = (int *)data;
    2077              : 
    2078      3611945 :   for (e = node->callers; e; e = e->next_caller)
    2079      2107733 :     (*num_calls)++;
    2080      1504212 :   return false;
    2081              : }
    2082              : 
    2083              : /* We only propagate across edges with non-interposable callee.  */
    2084              : 
    2085              : inline bool
    2086      7232082 : ignore_edge_p (struct cgraph_edge *e)
    2087              : {
    2088      7232082 :   enum availability avail;
    2089      7232082 :   e->callee->function_or_virtual_thunk_symbol (&avail, e->caller);
    2090      7232082 :   return (avail <= AVAIL_INTERPOSABLE);
    2091              : }
    2092              : 
    2093              : /* We use greedy algorithm for inlining of small functions:
    2094              :    All inline candidates are put into prioritized heap ordered in
    2095              :    increasing badness.
    2096              : 
    2097              :    The inlining of small functions is bounded by unit growth parameters.  */
    2098              : 
    2099              : static void
    2100       239354 : inline_small_functions (void)
    2101              : {
    2102       239354 :   struct cgraph_node *node;
    2103       239354 :   struct cgraph_edge *edge;
    2104       239354 :   inline_badness b;
    2105       239354 :   edge_heap_t edge_heap (b);
    2106       239354 :   auto_bitmap updated_nodes;
    2107       239354 :   int min_size;
    2108       239354 :   auto_vec<cgraph_edge *> new_indirect_edges;
    2109       239354 :   int initial_size = 0;
    2110       239354 :   struct cgraph_node **order = XCNEWVEC (cgraph_node *, symtab->cgraph_count);
    2111       239354 :   struct cgraph_edge_hook_list *edge_removal_hook_holder;
    2112       239354 :   new_indirect_edges.create (8);
    2113              : 
    2114       239354 :   edge_removal_hook_holder
    2115       239354 :     = symtab->add_edge_removal_hook (&heap_edge_removal_hook, &edge_heap);
    2116              : 
    2117              :   /* Compute overall unit size and other global parameters used by badness
    2118              :      metrics.  */
    2119              : 
    2120       239354 :   has_nonzero_ipa_profile = false;
    2121       239354 :   ipa_reduced_postorder (order, true, ignore_edge_p);
    2122       239354 :   free (order);
    2123              : 
    2124      2191618 :   FOR_EACH_DEFINED_FUNCTION (node)
    2125      1952264 :     if (!node->inlined_to)
    2126              :       {
    2127      1849433 :         if (!node->alias && node->analyzed
    2128      1849433 :             && (node->has_gimple_body_p () || node->thunk)
    2129      3801663 :             && opt_for_fn (node->decl, optimize))
    2130              :           {
    2131      1397451 :             class ipa_fn_summary *info = ipa_fn_summaries->get (node);
    2132      1397451 :             struct ipa_dfs_info *dfs = (struct ipa_dfs_info *) node->aux;
    2133              : 
    2134              :             /* Do not account external functions, they will be optimized out
    2135              :                if not inlined.  Also only count the non-cold portion of program.  */
    2136      1397451 :             if (inline_account_function_p (node))
    2137      1289786 :               initial_size += ipa_size_summaries->get (node)->size;
    2138      1397451 :             info->growth = estimate_growth (node);
    2139              : 
    2140      1397451 :             int num_calls = 0;
    2141      1397451 :             node->call_for_symbol_and_aliases (sum_callers, &num_calls,
    2142              :                                                true);
    2143      1397451 :             if (num_calls == 1)
    2144       473625 :               info->single_caller = true;
    2145      1397451 :             if (dfs && dfs->next_cycle)
    2146              :               {
    2147         5250 :                 struct cgraph_node *n2;
    2148         5250 :                 int id = dfs->scc_no + 1;
    2149        11924 :                 for (n2 = node; n2;
    2150         6674 :                      n2 = ((struct ipa_dfs_info *) n2->aux)->next_cycle)
    2151        10501 :                   if (opt_for_fn (n2->decl, optimize))
    2152              :                     {
    2153        10493 :                       ipa_fn_summary *info2 = ipa_fn_summaries->get
    2154        10493 :                          (n2->inlined_to ? n2->inlined_to : n2);
    2155        10493 :                       if (info2->scc_no)
    2156              :                         break;
    2157         6666 :                       info2->scc_no = id;
    2158              :                     }
    2159              :               }
    2160              :           }
    2161              : 
    2162      4463197 :         for (edge = node->callers; edge; edge = edge->next_caller)
    2163      2510967 :           if (edge->count.ipa ().initialized_p ()
    2164      2646332 :               && edge->count.ipa ().nonzero_p ())
    2165          439 :           has_nonzero_ipa_profile = true;
    2166              :       }
    2167       239354 :   ipa_free_postorder_info ();
    2168       239354 :   initialize_growth_caches ();
    2169              : 
    2170       239354 :   if (dump_file)
    2171          178 :     fprintf (dump_file,
    2172              :              "\nDeciding on inlining of small functions.  Starting with size %i.\n",
    2173              :              initial_size);
    2174              : 
    2175       239354 :   overall_size = initial_size;
    2176       239354 :   min_size = overall_size;
    2177              : 
    2178              :   /* Populate the heap with all edges we might inline.  */
    2179              : 
    2180      2191618 :   FOR_EACH_DEFINED_FUNCTION (node)
    2181              :     {
    2182      1952264 :       bool update = false;
    2183      1952264 :       struct cgraph_edge *next = NULL;
    2184      1952264 :       bool has_speculative = false;
    2185              : 
    2186      1952264 :       if (!opt_for_fn (node->decl, optimize)
    2187              :           /* With -Og we do not want to perform IPA inlining of small
    2188              :              functions since there are no scalar cleanups after it
    2189              :              that would realize the anticipated win.  All abstraction
    2190              :              is removed during early inlining.  */
    2191      1952264 :           || opt_for_fn (node->decl, optimize_debug))
    2192       481027 :         continue;
    2193              : 
    2194      1471237 :       if (dump_file)
    2195          803 :         fprintf (dump_file, "Enqueueing calls in %s.\n", node->dump_name ());
    2196              : 
    2197      7259583 :       for (edge = node->callees; edge; edge = edge->next_callee)
    2198              :         {
    2199      5788346 :           if (edge->inline_failed
    2200      5788312 :               && !edge->aux
    2201      5788172 :               && can_inline_edge_p (edge, true)
    2202      1639827 :               && want_inline_small_function_p (edge, true)
    2203       984191 :               && can_inline_edge_by_limits_p (edge, CAN_INLINE_REPORT)
    2204      6764845 :               && edge->inline_failed)
    2205              :             {
    2206       976499 :               gcc_assert (!edge->aux);
    2207       976499 :               update_edge_key (&edge_heap, edge);
    2208              :             }
    2209      5788346 :           if (edge->speculative)
    2210        15907 :             has_speculative = true;
    2211              :         }
    2212      1471237 :       if (has_speculative)
    2213        64794 :         for (edge = node->callees; edge; edge = next)
    2214              :           {
    2215        56633 :             next = edge->next_callee;
    2216        56633 :             if (edge->speculative
    2217        56633 :                 && !speculation_useful_p (edge, edge->aux != NULL))
    2218              :               {
    2219          486 :                 cgraph_edge::resolve_speculation (edge);
    2220          486 :                 update = true;
    2221              :               }
    2222              :           }
    2223         8161 :       if (update)
    2224              :         {
    2225            0 :           struct cgraph_node *where = node->inlined_to
    2226          412 :                                       ? node->inlined_to : node;
    2227          412 :           ipa_update_overall_fn_summary (where);
    2228          412 :           reset_edge_caches (where);
    2229          412 :           update_caller_keys (&edge_heap, where,
    2230              :                               updated_nodes, NULL);
    2231          412 :           update_callee_keys (&edge_heap, where, NULL,
    2232              :                               updated_nodes);
    2233          412 :           bitmap_clear (updated_nodes);
    2234              :         }
    2235              :     }
    2236              : 
    2237       239354 :   gcc_assert (in_lto_p
    2238              :               || !has_nonzero_ipa_profile
    2239              :               || flag_auto_profile
    2240              :               || (profile_info && flag_branch_probabilities));
    2241              : 
    2242      2777919 :   while (!edge_heap.empty ())
    2243              :     {
    2244      2538565 :       int old_size = overall_size;
    2245      2538565 :       struct cgraph_node *where, *callee;
    2246      2538565 :       sreal badness = edge_heap.min_key ().badness;
    2247      2538565 :       sreal current_badness;
    2248      2538565 :       int growth;
    2249              : 
    2250      2538565 :       edge = edge_heap.extract_min ();
    2251      2538565 :       gcc_assert (edge->aux);
    2252      2538565 :       edge->aux = NULL;
    2253      2538565 :       if (!edge->inline_failed || !edge->callee->analyzed)
    2254      1609683 :         continue;
    2255              : 
    2256              :       /* Be sure that caches are maintained consistent.
    2257              :          This check is affected by scaling roundoff errors when compiling for
    2258              :          IPA this we skip it in that case.  */
    2259      2538477 :       if (flag_checking && !edge->callee->count.ipa_p ()
    2260      4750523 :           && !has_nonzero_ipa_profile)
    2261              :         {
    2262      2212043 :           sreal cached_badness = edge_badness (edge, false);
    2263              : 
    2264      2212043 :           int old_size_est = estimate_edge_size (edge);
    2265      2212043 :           sreal old_time_est = estimate_edge_time (edge);
    2266      2212043 :           int old_hints_est = estimate_edge_hints (edge);
    2267              : 
    2268      2212043 :           if (edge_growth_cache != NULL)
    2269      2212043 :             edge_growth_cache->remove (edge);
    2270      3806881 :           reset_node_cache (edge->caller->inlined_to
    2271              :                             ? edge->caller->inlined_to
    2272              :                             : edge->caller);
    2273      2212043 :           gcc_assert (old_size_est == estimate_edge_size (edge));
    2274      2212043 :           gcc_assert (old_time_est == estimate_edge_time (edge));
    2275              :           /* FIXME:
    2276              : 
    2277              :              gcc_assert (old_hints_est == estimate_edge_hints (edge));
    2278              : 
    2279              :              fails with profile feedback because some hints depends on
    2280              :              maybe_hot_edge_p predicate and because callee gets inlined to other
    2281              :              calls, the edge may become cold.
    2282              :              This ought to be fixed by computing relative probabilities
    2283              :              for given invocation but that will be better done once whole
    2284              :              code is converted to sreals.  Disable for now and revert to "wrong"
    2285              :              value so enable/disable checking paths agree.  */
    2286      2212043 :           edge_growth_cache->get (edge)->hints = old_hints_est + 1;
    2287              : 
    2288              :           /* When updating the edge costs, we only decrease badness in the keys.
    2289              :              Increases of badness are handled lazily; when we see key with out
    2290              :              of date value on it, we re-insert it now.  */
    2291      2212043 :           current_badness = edge_badness (edge, false);
    2292      2212043 :           gcc_assert (cached_badness == current_badness);
    2293      2212043 :           gcc_assert (current_badness >= badness);
    2294              :         }
    2295              :       else
    2296       326437 :         current_badness = edge_badness (edge, false);
    2297      2538480 :       if (current_badness != badness)
    2298              :         {
    2299      1671494 :           if (edge_heap.min () && current_badness > edge_heap.min_key ().badness)
    2300              :             {
    2301      1489494 :               inline_badness b (edge, current_badness);
    2302      1489494 :               edge->aux = edge_heap.insert (b, edge);
    2303      1489494 :               continue;
    2304      1489494 :             }
    2305              :           else
    2306       182000 :             badness = current_badness;
    2307              :         }
    2308              : 
    2309      1048986 :       if (!can_inline_edge_p (edge, true)
    2310      1048986 :           || !can_inline_edge_by_limits_p (edge, CAN_INLINE_REPORT))
    2311              :         {
    2312         3690 :           resolve_noninline_speculation (&edge_heap, edge);
    2313         3690 :           continue;
    2314              :         }
    2315              : 
    2316      1045296 :       callee = edge->callee->ultimate_alias_target ();
    2317      1045296 :       growth = estimate_edge_growth (edge);
    2318      1045296 :       if (dump_file)
    2319              :         {
    2320          525 :           fprintf (dump_file,
    2321              :                    "\nConsidering %s with %i size\n",
    2322              :                    callee->dump_name (),
    2323          525 :                    ipa_size_summaries->get (callee)->size);
    2324         1050 :           fprintf (dump_file,
    2325              :                    " to be inlined into %s in %s:%i\n"
    2326              :                    " Estimated badness is %f, frequency %.2f.\n",
    2327          525 :                    edge->caller->dump_name (),
    2328          525 :                    edge->call_stmt
    2329          497 :                    && (LOCATION_LOCUS (gimple_location ((const gimple *)
    2330              :                                                         edge->call_stmt))
    2331              :                        > BUILTINS_LOCATION)
    2332          488 :                    ? gimple_filename ((const gimple *) edge->call_stmt)
    2333              :                    : "unknown",
    2334          525 :                    edge->call_stmt
    2335          497 :                    ? gimple_lineno ((const gimple *) edge->call_stmt)
    2336              :                    : -1,
    2337              :                    badness.to_double (),
    2338          525 :                    edge->sreal_frequency ().to_double ());
    2339          525 :           if (edge->count.ipa ().initialized_p ())
    2340              :             {
    2341            0 :               fprintf (dump_file, " Called ");
    2342            0 :               edge->count.ipa ().dump (dump_file);
    2343            0 :               fprintf (dump_file, " times\n");
    2344              :             }
    2345          525 :           if (dump_flags & TDF_DETAILS)
    2346          185 :             edge_badness (edge, true);
    2347              :         }
    2348              : 
    2349      1045296 :       where = edge->caller;
    2350              : 
    2351      1045296 :       if (overall_size + growth > compute_max_insns (where, min_size)
    2352      1045296 :           && !DECL_DISREGARD_INLINE_LIMITS (callee->decl))
    2353              :         {
    2354       111637 :           edge->inline_failed = CIF_INLINE_UNIT_GROWTH_LIMIT;
    2355       111637 :           report_inline_failed_reason (edge);
    2356       111637 :           resolve_noninline_speculation (&edge_heap, edge);
    2357       111637 :           continue;
    2358              :         }
    2359              : 
    2360       933659 :       if (!want_inline_small_function_p (edge, true))
    2361              :         {
    2362         2366 :           resolve_noninline_speculation (&edge_heap, edge);
    2363         2366 :           continue;
    2364              :         }
    2365              : 
    2366       931293 :       profile_count old_count = callee->count;
    2367              : 
    2368              :       /* Heuristics for inlining small functions work poorly for
    2369              :          recursive calls where we do effects similar to loop unrolling.
    2370              :          When inlining such edge seems profitable, leave decision on
    2371              :          specific inliner.  */
    2372       931293 :       if (edge->recursive_p ())
    2373              :         {
    2374         2041 :           if (where->inlined_to)
    2375          579 :             where = where->inlined_to;
    2376              : 
    2377              :           /* Disable always_inline on self recursive functions.
    2378              :              This prevents some inlining bombs such as one in PR113291
    2379              :              from exploding.
    2380              :              It is not enough to stop inlining in self recursive always_inlines
    2381              :              since they may grow large enough so always inlining them even
    2382              :              with recursin depth 0 is too much.
    2383              : 
    2384              :              All sane uses of always_inline should be handled during
    2385              :              early optimizations.  */
    2386         2041 :           DECL_DISREGARD_INLINE_LIMITS (where->decl) = false;
    2387              : 
    2388         2041 :           if (!recursive_inlining (edge,
    2389         2041 :                                    opt_for_fn (edge->caller->decl,
    2390              :                                                flag_indirect_inlining)
    2391              :                                    ? &new_indirect_edges : NULL))
    2392              :             {
    2393          371 :               edge->inline_failed = CIF_RECURSIVE_INLINING;
    2394          371 :               resolve_noninline_speculation (&edge_heap, edge);
    2395          371 :               continue;
    2396              :             }
    2397         1670 :           reset_edge_caches (where);
    2398              :           /* Recursive inliner inlines all recursive calls of the function
    2399              :              at once. Consequently we need to update all callee keys.  */
    2400         1670 :           if (opt_for_fn (edge->caller->decl, flag_indirect_inlining))
    2401         1645 :             add_new_edges_to_heap (&edge_heap, new_indirect_edges);
    2402         1670 :           update_callee_keys (&edge_heap, where, where, updated_nodes);
    2403         1670 :           bitmap_clear (updated_nodes);
    2404              :         }
    2405              :       else
    2406              :         {
    2407       929252 :           struct cgraph_node *outer_node = NULL;
    2408       929252 :           int depth = 0;
    2409              : 
    2410              :           /* Consider the case where self recursive function A is inlined
    2411              :              into B.  This is desired optimization in some cases, since it
    2412              :              leads to effect similar of loop peeling and we might completely
    2413              :              optimize out the recursive call.  However we must be extra
    2414              :              selective.  */
    2415              : 
    2416       929252 :           where = edge->caller;
    2417      1492116 :           while (where->inlined_to)
    2418              :             {
    2419       562864 :               if (where->decl == callee->decl)
    2420        11268 :                 outer_node = where, depth++;
    2421       562864 :               where = where->callers->caller;
    2422              :             }
    2423       931292 :           if (outer_node
    2424       929252 :               && !want_inline_self_recursive_call_p (edge, outer_node,
    2425              :                                                      true, depth))
    2426              :             {
    2427         2040 :               edge->inline_failed
    2428         2040 :                 = (DECL_DISREGARD_INLINE_LIMITS (edge->callee->decl)
    2429         2040 :                    ? CIF_RECURSIVE_INLINING : CIF_UNSPECIFIED);
    2430         2040 :               resolve_noninline_speculation (&edge_heap, edge);
    2431         2040 :               continue;
    2432              :             }
    2433       927212 :           else if (depth && dump_file)
    2434            6 :             fprintf (dump_file, " Peeling recursion with depth %i\n", depth);
    2435              : 
    2436       927212 :           gcc_checking_assert (!callee->inlined_to);
    2437              : 
    2438       927212 :           int old_size = ipa_size_summaries->get (where)->size;
    2439       927212 :           sreal old_time = ipa_fn_summaries->get (where)->time;
    2440              : 
    2441       927212 :           inline_call (edge, true, &new_indirect_edges, &overall_size, true);
    2442       927212 :           reset_edge_caches (edge->callee);
    2443       927212 :           add_new_edges_to_heap (&edge_heap, new_indirect_edges);
    2444              : 
    2445              :           /* If caller's size and time increased we do not need to update
    2446              :              all edges because badness is not going to decrease.  */
    2447       927212 :           if (old_size <= ipa_size_summaries->get (where)->size
    2448       871553 :               && old_time <= ipa_fn_summaries->get (where)->time
    2449              :               /* Wrapper penalty may be non-monotonous in this respect.
    2450              :                  Fortunately it only affects small functions.  */
    2451      1536270 :               && !wrapper_heuristics_may_apply (where, old_size))
    2452       425428 :             update_callee_keys (&edge_heap, edge->callee, edge->callee,
    2453              :                                 updated_nodes);
    2454              :           else
    2455       501784 :             update_callee_keys (&edge_heap, where,
    2456              :                                 edge->callee,
    2457              :                                 updated_nodes);
    2458              :         }
    2459       928882 :       where = edge->caller;
    2460       928882 :       if (where->inlined_to)
    2461       271957 :         where = where->inlined_to;
    2462              : 
    2463              :       /* Our profitability metric can depend on local properties
    2464              :          such as number of inlinable calls and size of the function body.
    2465              :          After inlining these properties might change for the function we
    2466              :          inlined into (since it's body size changed) and for the functions
    2467              :          called by function we inlined (since number of it inlinable callers
    2468              :          might change).  */
    2469       928882 :       update_caller_keys (&edge_heap, where, updated_nodes, NULL);
    2470              :       /* Offline copy count has possibly changed, recompute if profile is
    2471              :          available.  */
    2472       928882 :       struct cgraph_node *n
    2473       928882 :               = cgraph_node::get (edge->callee->decl)->ultimate_alias_target ();
    2474       632736 :       if (n != edge->callee && n->analyzed && !(n->count == old_count)
    2475       928951 :           && n->count.ipa_p ())
    2476           69 :         update_callee_keys (&edge_heap, n, NULL, updated_nodes);
    2477       928882 :       bitmap_clear (updated_nodes);
    2478              : 
    2479       928882 :       if (dump_enabled_p ())
    2480              :         {
    2481          534 :           ipa_fn_summary *s = ipa_fn_summaries->get (where);
    2482              : 
    2483              :           /* dump_printf can't handle %+i.  */
    2484          534 :           char buf_net_change[100];
    2485          534 :           snprintf (buf_net_change, sizeof buf_net_change, "%+i",
    2486              :                     overall_size - old_size);
    2487              : 
    2488         1068 :           dump_printf_loc (MSG_OPTIMIZED_LOCATIONS, edge->call_stmt,
    2489              :                            " Inlined %C into %C which now has time %f and "
    2490              :                            "size %i, net change of %s%s.\n",
    2491              :                            edge->callee, edge->caller,
    2492              :                            s->time.to_double (),
    2493          534 :                            ipa_size_summaries->get (edge->caller)->size,
    2494              :                            buf_net_change,
    2495          534 :                            cross_module_call_p (edge)
    2496              :                            ? " (cross module)" : "");
    2497              :         }
    2498       928882 :       if (min_size > overall_size)
    2499              :         {
    2500       225233 :           min_size = overall_size;
    2501              : 
    2502       225233 :           if (dump_file)
    2503          398 :             fprintf (dump_file, "New minimal size reached: %i\n", min_size);
    2504              :         }
    2505              :     }
    2506              : 
    2507       239354 :   free_growth_caches ();
    2508       239354 :   if (dump_enabled_p ())
    2509          434 :     dump_printf (MSG_NOTE,
    2510              :                  "Unit growth for small function inlining: %i->%i (%i%%)\n",
    2511              :                  initial_size, overall_size,
    2512          193 :                  initial_size ? overall_size * 100 / (initial_size) - 100 : 0);
    2513       239354 :   symtab->remove_edge_removal_hook (edge_removal_hook_holder);
    2514       239354 : }
    2515              : 
    2516              : /* Flatten NODE.  Performed both during early inlining and
    2517              :    at IPA inlining time.  */
    2518              : 
    2519              : static void
    2520          716 : flatten_function (struct cgraph_node *node, bool early, bool update)
    2521              : {
    2522          716 :   struct cgraph_edge *e;
    2523              : 
    2524              :   /* We shouldn't be called recursively when we are being processed.  */
    2525          716 :   gcc_assert (node->aux == NULL);
    2526              : 
    2527          716 :   node->aux = (void *) node;
    2528              : 
    2529         1648 :   for (e = node->callees; e; e = e->next_callee)
    2530              :     {
    2531          932 :       struct cgraph_node *orig_callee;
    2532          932 :       struct cgraph_node *callee = e->callee->ultimate_alias_target ();
    2533              : 
    2534              :       /* We've hit cycle?  It is time to give up.  */
    2535          932 :       if (callee->aux)
    2536              :         {
    2537           15 :           if (dump_enabled_p ())
    2538            0 :             dump_printf_loc (MSG_MISSED_OPTIMIZATION, e->call_stmt,
    2539              :                              "Not inlining %C into %C to avoid cycle.\n",
    2540              :                              callee, e->caller);
    2541           15 :           if (cgraph_inline_failed_type (e->inline_failed) != CIF_FINAL_ERROR)
    2542           15 :             e->inline_failed = CIF_RECURSIVE_INLINING;
    2543           15 :           continue;
    2544              :         }
    2545              : 
    2546              :       /* When the edge is already inlined, we just need to recurse into
    2547              :          it in order to fully flatten the leaves.  */
    2548          917 :       if (!e->inline_failed)
    2549              :         {
    2550          350 :           flatten_function (callee, early, false);
    2551          350 :           continue;
    2552              :         }
    2553              : 
    2554              :       /* Flatten attribute needs to be processed during late inlining. For
    2555              :          extra code quality we however do flattening during early optimization,
    2556              :          too.  */
    2557          321 :       if (!early
    2558          567 :           ? !can_inline_edge_p (e, true)
    2559          246 :             && !can_inline_edge_by_limits_p (e, CAN_INLINE_REPORT)
    2560          321 :           : !can_early_inline_edge_p (e))
    2561          419 :         continue;
    2562              : 
    2563          148 :       if (e->recursive_p ())
    2564              :         {
    2565            0 :           if (dump_enabled_p ())
    2566            0 :             dump_printf_loc (MSG_MISSED_OPTIMIZATION, e->call_stmt,
    2567              :                              "Not inlining: recursive call.\n");
    2568            0 :           continue;
    2569              :         }
    2570              : 
    2571          148 :       if (gimple_in_ssa_p (DECL_STRUCT_FUNCTION (node->decl))
    2572          296 :           != gimple_in_ssa_p (DECL_STRUCT_FUNCTION (callee->decl)))
    2573              :         {
    2574            2 :           if (dump_enabled_p ())
    2575            2 :             dump_printf_loc (MSG_MISSED_OPTIMIZATION, e->call_stmt,
    2576              :                              "Not inlining: SSA form does not match.\n");
    2577            2 :           continue;
    2578              :         }
    2579              : 
    2580              :       /* Inline the edge and flatten the inline clone.  Avoid
    2581              :          recursing through the original node if the node was cloned.  */
    2582          146 :       if (dump_enabled_p ())
    2583            6 :         dump_printf_loc (MSG_OPTIMIZED_LOCATIONS, e->call_stmt,
    2584              :                          " Inlining %C into %C.\n",
    2585              :                          callee, e->caller);
    2586          146 :       orig_callee = callee;
    2587          146 :       inline_call (e, true, NULL, NULL, false);
    2588          146 :       if (e->callee != orig_callee)
    2589          106 :         orig_callee->aux = (void *) node;
    2590          146 :       flatten_function (e->callee, early, false);
    2591          146 :       if (e->callee != orig_callee)
    2592          106 :         orig_callee->aux = NULL;
    2593              :     }
    2594              : 
    2595          716 :   node->aux = NULL;
    2596          716 :   cgraph_node *where = node->inlined_to ? node->inlined_to : node;
    2597          716 :   if (update && opt_for_fn (where->decl, optimize))
    2598          209 :     ipa_update_overall_fn_summary (where);
    2599          716 : }
    2600              : 
    2601              : /* Inline NODE to all callers.  Worker for cgraph_for_node_and_aliases.
    2602              :    DATA points to number of calls originally found so we avoid infinite
    2603              :    recursion.  */
    2604              : 
    2605              : static bool
    2606        31807 : inline_to_all_callers_1 (struct cgraph_node *node, void *data,
    2607              :                          hash_set<cgraph_node *> *callers)
    2608              : {
    2609        31807 :   int *num_calls = (int *)data;
    2610        31807 :   bool callee_removed = false;
    2611              : 
    2612        66665 :   while (node->callers && !node->inlined_to)
    2613              :     {
    2614        36195 :       struct cgraph_node *caller = node->callers->caller;
    2615              : 
    2616        36195 :       if (!can_inline_edge_p (node->callers, true)
    2617        36195 :           || !can_inline_edge_by_limits_p (node->callers, CAN_INLINE_REPORT)
    2618        72389 :           || node->callers->recursive_p ())
    2619              :         {
    2620            1 :           if (dump_file)
    2621            0 :             fprintf (dump_file, "Uninlinable call found; giving up.\n");
    2622            1 :           *num_calls = 0;
    2623            1 :           return false;
    2624              :         }
    2625              : 
    2626        36194 :       if (dump_file)
    2627              :         {
    2628            2 :           cgraph_node *ultimate = node->ultimate_alias_target ();
    2629            2 :           fprintf (dump_file,
    2630              :                    "\nInlining %s size %i.\n",
    2631              :                    ultimate->dump_name (),
    2632            2 :                    ipa_size_summaries->get (ultimate)->size);
    2633            2 :           fprintf (dump_file,
    2634              :                    " Called once from %s %i insns.\n",
    2635              :                    node->callers->caller->dump_name (),
    2636            2 :                    ipa_size_summaries->get (node->callers->caller)->size);
    2637              :         }
    2638              : 
    2639              :       /* Remember which callers we inlined to, delaying updating the
    2640              :          overall summary.  */
    2641        36194 :       callers->add (node->callers->caller);
    2642        36194 :       inline_call (node->callers, true, NULL, NULL, false, &callee_removed);
    2643        36194 :       if (dump_file)
    2644            2 :         fprintf (dump_file,
    2645              :                  " Inlined into %s which now has %i size\n",
    2646              :                  caller->dump_name (),
    2647            2 :                  ipa_size_summaries->get (caller)->size);
    2648        36194 :       if (!(*num_calls)--)
    2649              :         {
    2650            0 :           if (dump_file)
    2651            0 :             fprintf (dump_file, "New calls found; giving up.\n");
    2652            0 :           return callee_removed;
    2653              :         }
    2654        36194 :       if (callee_removed)
    2655              :         return true;
    2656              :     }
    2657              :   return false;
    2658              : }
    2659              : 
    2660              : /* Wrapper around inline_to_all_callers_1 doing delayed overall summary
    2661              :    update.  */
    2662              : 
    2663              : static bool
    2664        31807 : inline_to_all_callers (struct cgraph_node *node, void *data)
    2665              : {
    2666        31807 :   hash_set<cgraph_node *> callers;
    2667        31807 :   bool res = inline_to_all_callers_1 (node, data, &callers);
    2668              :   /* Perform the delayed update of the overall summary of all callers
    2669              :      processed.  This avoids quadratic behavior in the cases where
    2670              :      we have a lot of calls to the same function.  */
    2671        62165 :   for (hash_set<cgraph_node *>::iterator i = callers.begin ();
    2672        62165 :        i != callers.end (); ++i)
    2673        30358 :     ipa_update_overall_fn_summary ((*i)->inlined_to ? (*i)->inlined_to : *i);
    2674        31807 :   return res;
    2675        31807 : }
    2676              : 
    2677              : /* Output overall time estimate.  */
    2678              : static void
    2679          356 : dump_overall_stats (void)
    2680              : {
    2681          356 :   sreal sum_weighted = 0, sum = 0;
    2682          356 :   struct cgraph_node *node;
    2683              : 
    2684         2288 :   FOR_EACH_DEFINED_FUNCTION (node)
    2685         1932 :     if (!node->inlined_to
    2686         1373 :         && !node->alias)
    2687              :       {
    2688         1265 :         ipa_fn_summary *s = ipa_fn_summaries->get (node);
    2689         1265 :         if (s != NULL)
    2690              :           {
    2691         1161 :           sum += s->time;
    2692         1161 :           if (node->count.ipa ().initialized_p ())
    2693           14 :             sum_weighted += s->time * node->count.ipa ().to_gcov_type ();
    2694              :           }
    2695              :       }
    2696          356 :   fprintf (dump_file, "Overall time estimate: "
    2697              :            "%f weighted by profile: "
    2698              :            "%f\n", sum.to_double (), sum_weighted.to_double ());
    2699          356 : }
    2700              : 
    2701              : /* Output some useful stats about inlining.  */
    2702              : 
    2703              : static void
    2704          178 : dump_inline_stats (void)
    2705              : {
    2706          178 :   int64_t inlined_cnt = 0, inlined_indir_cnt = 0;
    2707          178 :   int64_t inlined_virt_cnt = 0, inlined_virt_indir_cnt = 0;
    2708          178 :   int64_t noninlined_cnt = 0, noninlined_indir_cnt = 0;
    2709          178 :   int64_t noninlined_virt_cnt = 0, noninlined_virt_indir_cnt = 0;
    2710          178 :   int64_t  inlined_speculative = 0, inlined_speculative_ply = 0;
    2711          178 :   int64_t indirect_poly_cnt = 0, indirect_cnt = 0;
    2712          178 :   int64_t reason[CIF_N_REASONS][2];
    2713         5874 :   sreal reason_freq[CIF_N_REASONS];
    2714          178 :   int i;
    2715          178 :   struct cgraph_node *node;
    2716              : 
    2717          178 :   memset (reason, 0, sizeof (reason));
    2718         5874 :   for (i=0; i < CIF_N_REASONS; i++)
    2719         5696 :     reason_freq[i] = 0;
    2720         1242 :   FOR_EACH_DEFINED_FUNCTION (node)
    2721              :   {
    2722         1064 :     struct cgraph_edge *e;
    2723         5947 :     for (e = node->callees; e; e = e->next_callee)
    2724              :       {
    2725         4883 :         if (e->inline_failed)
    2726              :           {
    2727         4330 :             if (e->count.ipa ().initialized_p ())
    2728         2611 :               reason[(int) e->inline_failed][0] += e->count.ipa ().to_gcov_type ();
    2729         4330 :             reason_freq[(int) e->inline_failed] += e->sreal_frequency ();
    2730         4330 :             reason[(int) e->inline_failed][1] ++;
    2731         4330 :             if (DECL_VIRTUAL_P (e->callee->decl)
    2732         4330 :                 && e->count.ipa ().initialized_p ())
    2733              :               {
    2734            0 :                 if (e->indirect_inlining_edge)
    2735            0 :                   noninlined_virt_indir_cnt += e->count.ipa ().to_gcov_type ();
    2736              :                 else
    2737            0 :                   noninlined_virt_cnt += e->count.ipa ().to_gcov_type ();
    2738              :               }
    2739         4330 :             else if (e->count.ipa ().initialized_p ())
    2740              :               {
    2741         2611 :                 if (e->indirect_inlining_edge)
    2742            0 :                   noninlined_indir_cnt += e->count.ipa ().to_gcov_type ();
    2743              :                 else
    2744         2611 :                   noninlined_cnt += e->count.ipa ().to_gcov_type ();
    2745              :               }
    2746              :           }
    2747          553 :         else if (e->count.ipa ().initialized_p ())
    2748              :           {
    2749            0 :             if (e->speculative)
    2750              :               {
    2751            0 :                 if (DECL_VIRTUAL_P (e->callee->decl))
    2752            0 :                   inlined_speculative_ply += e->count.ipa ().to_gcov_type ();
    2753              :                 else
    2754            0 :                   inlined_speculative += e->count.ipa ().to_gcov_type ();
    2755              :               }
    2756            0 :             else if (DECL_VIRTUAL_P (e->callee->decl))
    2757              :               {
    2758            0 :                 if (e->indirect_inlining_edge)
    2759            0 :                   inlined_virt_indir_cnt += e->count.ipa ().to_gcov_type ();
    2760              :                 else
    2761            0 :                   inlined_virt_cnt += e->count.ipa ().to_gcov_type ();
    2762              :               }
    2763              :             else
    2764              :               {
    2765            0 :                 if (e->indirect_inlining_edge)
    2766            0 :                   inlined_indir_cnt += e->count.ipa ().to_gcov_type ();
    2767              :                 else
    2768            0 :                   inlined_cnt += e->count.ipa ().to_gcov_type ();
    2769              :               }
    2770              :           }
    2771              :       }
    2772         1163 :     for (e = node->indirect_calls; e; e = e->next_callee)
    2773          198 :       if (is_a <cgraph_polymorphic_indirect_info *> (e->indirect_info)
    2774           99 :           & e->count.ipa ().initialized_p ())
    2775            0 :         indirect_poly_cnt += e->count.ipa ().to_gcov_type ();
    2776           99 :       else if (e->count.ipa ().initialized_p ())
    2777            0 :         indirect_cnt += e->count.ipa ().to_gcov_type ();
    2778              :   }
    2779          178 :   if (has_nonzero_ipa_profile)
    2780              :     {
    2781            0 :       fprintf (dump_file,
    2782              :                "Inlined %" PRId64 " + speculative "
    2783              :                "%" PRId64 " + speculative polymorphic "
    2784              :                "%" PRId64 " + previously indirect "
    2785              :                "%" PRId64 " + virtual "
    2786              :                "%" PRId64 " + virtual and previously indirect "
    2787              :                "%" PRId64 "\n" "Not inlined "
    2788              :                "%" PRId64 " + previously indirect "
    2789              :                "%" PRId64 " + virtual "
    2790              :                "%" PRId64 " + virtual and previously indirect "
    2791              :                "%" PRId64 " + still indirect "
    2792              :                "%" PRId64 " + still indirect polymorphic "
    2793              :                "%" PRId64 "\n", inlined_cnt,
    2794              :                inlined_speculative, inlined_speculative_ply,
    2795              :                inlined_indir_cnt, inlined_virt_cnt, inlined_virt_indir_cnt,
    2796              :                noninlined_cnt, noninlined_indir_cnt, noninlined_virt_cnt,
    2797              :                noninlined_virt_indir_cnt, indirect_cnt, indirect_poly_cnt);
    2798            0 :       fprintf (dump_file, "Removed speculations ");
    2799            0 :       spec_rem.dump (dump_file);
    2800            0 :       fprintf (dump_file, "\n");
    2801              :     }
    2802          178 :   dump_overall_stats ();
    2803          178 :   fprintf (dump_file, "\nWhy inlining failed?\n");
    2804         6052 :   for (i = 0; i < CIF_N_REASONS; i++)
    2805         5696 :     if (reason[i][1])
    2806          146 :       fprintf (dump_file, "%-50s: %8i calls, %8f freq, %" PRId64" count\n",
    2807              :                cgraph_inline_failed_string ((cgraph_inline_failed_t) i),
    2808              :                (int) reason[i][1], reason_freq[i].to_double (), reason[i][0]);
    2809          178 : }
    2810              : 
    2811              : /* Called when node is removed.  */
    2812              : 
    2813              : static void
    2814            0 : flatten_remove_node_hook (struct cgraph_node *node, void *data)
    2815              : {
    2816            0 :   if (lookup_attribute ("flatten", DECL_ATTRIBUTES (node->decl)) == NULL)
    2817              :     return;
    2818              : 
    2819            0 :   hash_set<struct cgraph_node *> *removed
    2820              :     = (hash_set<struct cgraph_node *> *) data;
    2821            0 :   removed->add (node);
    2822              : }
    2823              : 
    2824              : /* Decide on the inlining.  We do so in the topological order to avoid
    2825              :    expenses on updating data structures.  */
    2826              : 
    2827              : static unsigned int
    2828       239354 : ipa_inline (void)
    2829              : {
    2830       239354 :   struct cgraph_node *node;
    2831       239354 :   int nnodes;
    2832       239354 :   struct cgraph_node **order;
    2833       239354 :   int i, j;
    2834       239354 :   int cold;
    2835       239354 :   bool remove_functions = false;
    2836              : 
    2837       239354 :   order = XCNEWVEC (struct cgraph_node *, symtab->cgraph_count);
    2838              : 
    2839       239354 :   if (dump_file)
    2840          178 :     ipa_dump_fn_summaries (dump_file);
    2841              : 
    2842       239354 :   nnodes = ipa_reverse_postorder (order);
    2843       239354 :   spec_rem = profile_count::zero ();
    2844              : 
    2845      3997654 :   FOR_EACH_FUNCTION (node)
    2846              :     {
    2847      3758300 :       node->aux = 0;
    2848              : 
    2849              :       /* Recompute the default reasons for inlining because they may have
    2850              :          changed during merging.  */
    2851      3758300 :       if (in_lto_p)
    2852              :         {
    2853       443154 :           for (cgraph_edge *e = node->callees; e; e = e->next_callee)
    2854              :             {
    2855       334298 :               gcc_assert (e->inline_failed);
    2856       334298 :               initialize_inline_failed (e);
    2857              :             }
    2858       110148 :           for (cgraph_edge *e = node->indirect_calls; e; e = e->next_callee)
    2859         1292 :             initialize_inline_failed (e);
    2860              :         }
    2861              :     }
    2862              : 
    2863       239354 :   if (dump_file)
    2864          178 :     fprintf (dump_file, "\nFlattening functions:\n");
    2865              : 
    2866              :   /* First shrink order array, so that it only contains nodes with
    2867              :      flatten attribute.  */
    2868      3997654 :   for (i = nnodes - 1, j = i; i >= 0; i--)
    2869              :     {
    2870      3758300 :       node = order[i];
    2871      3758300 :       if (node->definition
    2872              :           /* Do not try to flatten aliases.  These may happen for example when
    2873              :              creating local aliases.  */
    2874      1952246 :           && !node->alias
    2875      5607749 :           && lookup_attribute ("flatten",
    2876      1849449 :                                DECL_ATTRIBUTES (node->decl)) != NULL)
    2877           85 :         order[j--] = order[i];
    2878              :     }
    2879              : 
    2880              :   /* After the above loop, order[j + 1] ... order[nnodes - 1] contain
    2881              :      nodes with flatten attribute.  If there is more than one such
    2882              :      node, we need to register a node removal hook, as flatten_function
    2883              :      could remove other nodes with flatten attribute.  See PR82801.  */
    2884       239354 :   struct cgraph_node_hook_list *node_removal_hook_holder = NULL;
    2885       239354 :   hash_set<struct cgraph_node *> *flatten_removed_nodes = NULL;
    2886       239354 :   if (j < nnodes - 2)
    2887              :     {
    2888           15 :       flatten_removed_nodes = new hash_set<struct cgraph_node *>;
    2889           15 :       node_removal_hook_holder
    2890           15 :         = symtab->add_cgraph_removal_hook (&flatten_remove_node_hook,
    2891              :                                            flatten_removed_nodes);
    2892              :     }
    2893              : 
    2894              :   /* In the first pass handle functions to be flattened.  Do this with
    2895              :      a priority so none of our later choices will make this impossible.  */
    2896       239439 :   for (i = nnodes - 1; i > j; i--)
    2897              :     {
    2898           85 :       node = order[i];
    2899           85 :       if (flatten_removed_nodes
    2900           85 :           && flatten_removed_nodes->contains (node))
    2901            0 :         continue;
    2902              : 
    2903              :       /* Handle nodes to be flattened.
    2904              :          Ideally when processing callees we stop inlining at the
    2905              :          entry of cycles, possibly cloning that entry point and
    2906              :          try to flatten itself turning it into a self-recursive
    2907              :          function.  */
    2908           85 :       if (dump_file)
    2909            4 :         fprintf (dump_file, "Flattening %s\n", node->dump_name ());
    2910           85 :       flatten_function (node, false, true);
    2911              :     }
    2912              : 
    2913       239354 :   if (j < nnodes - 2)
    2914              :     {
    2915           15 :       symtab->remove_cgraph_removal_hook (node_removal_hook_holder);
    2916           30 :       delete flatten_removed_nodes;
    2917              :     }
    2918       239354 :   free (order);
    2919              : 
    2920       239354 :   if (dump_file)
    2921          178 :     dump_overall_stats ();
    2922              : 
    2923       239354 :   inline_small_functions ();
    2924              : 
    2925       239354 :   gcc_assert (symtab->state == IPA_SSA);
    2926       239354 :   symtab->state = IPA_SSA_AFTER_INLINING;
    2927              :   /* Do first after-inlining removal.  We want to remove all "stale" extern
    2928              :      inline functions and virtual functions so we really know what is called
    2929              :      once.  */
    2930       239354 :   symtab->remove_unreachable_nodes (dump_file);
    2931              : 
    2932              :   /* Inline functions with a property that after inlining into all callers the
    2933              :      code size will shrink because the out-of-line copy is eliminated.
    2934              :      We do this regardless on the callee size as long as function growth limits
    2935              :      are met.  */
    2936       239354 :   if (dump_file)
    2937          178 :     fprintf (dump_file,
    2938              :              "\nDeciding on functions to be inlined into all callers and "
    2939              :              "removing useless speculations:\n");
    2940              : 
    2941              :   /* Inlining one function called once has good chance of preventing
    2942              :      inlining other function into the same callee.  Ideally we should
    2943              :      work in priority order, but probably inlining hot functions first
    2944              :      is good cut without the extra pain of maintaining the queue.
    2945              : 
    2946              :      ??? this is not really fitting the bill perfectly: inlining function
    2947              :      into callee often leads to better optimization of callee due to
    2948              :      increased context for optimization.
    2949              :      For example if main() function calls a function that outputs help
    2950              :      and then function that does the main optimization, we should inline
    2951              :      the second with priority even if both calls are cold by themselves.
    2952              : 
    2953              :      We probably want to implement new predicate replacing our use of
    2954              :      maybe_hot_edge interpreted as maybe_hot_edge || callee is known
    2955              :      to be hot.  */
    2956       718062 :   for (cold = 0; cold <= 1; cold ++)
    2957              :     {
    2958      6493409 :       FOR_EACH_DEFINED_FUNCTION (node)
    2959              :         {
    2960      6014701 :           struct cgraph_edge *edge, *next;
    2961      6014701 :           bool update=false;
    2962              : 
    2963      6014701 :           if (!opt_for_fn (node->decl, optimize)
    2964      6014701 :               || !opt_for_fn (node->decl, flag_inline_functions_called_once))
    2965       961930 :             continue;
    2966              : 
    2967     20373224 :           for (edge = node->callees; edge; edge = next)
    2968              :             {
    2969     15320453 :               next = edge->next_callee;
    2970     15320453 :               if (edge->speculative && !speculation_useful_p (edge, false))
    2971              :                 {
    2972         2530 :                   if (edge->count.ipa ().initialized_p ())
    2973            0 :                     spec_rem += edge->count.ipa ();
    2974         2530 :                   cgraph_edge::resolve_speculation (edge);
    2975         2530 :                   update = true;
    2976         2530 :                   remove_functions = true;
    2977              :                 }
    2978              :             }
    2979      5052771 :           if (update)
    2980              :             {
    2981          152 :               struct cgraph_node *where = node->inlined_to
    2982         2063 :                                           ? node->inlined_to : node;
    2983         2063 :               reset_edge_caches (where);
    2984         2063 :               ipa_update_overall_fn_summary (where);
    2985              :             }
    2986      5052771 :           if (want_inline_function_to_all_callers_p (node, cold))
    2987              :             {
    2988        27856 :               int num_calls = 0;
    2989        27856 :               node->call_for_symbol_and_aliases (sum_callers, &num_calls,
    2990              :                                                  true);
    2991        27856 :               while (node->call_for_symbol_and_aliases
    2992        29192 :                        (inline_to_all_callers, &num_calls, true))
    2993              :                 ;
    2994        27856 :               remove_functions = true;
    2995              :             }
    2996              :         }
    2997              :     }
    2998              : 
    2999       239354 :   if (dump_enabled_p ())
    3000          241 :     dump_printf (MSG_NOTE,
    3001              :                  "\nInlined %i calls, eliminated %i functions\n\n",
    3002              :                  ncalls_inlined, nfunctions_inlined);
    3003       239354 :   if (dump_file)
    3004          178 :     dump_inline_stats ();
    3005              : 
    3006       239354 :   if (dump_file)
    3007          178 :     ipa_dump_fn_summaries (dump_file);
    3008       239354 :   return remove_functions ? TODO_remove_functions : 0;
    3009              : }
    3010              : 
    3011              : /* Inline always-inline function calls in NODE
    3012              :    (which itself is possibly inline).  */
    3013              : 
    3014              : static bool
    3015      3608823 : inline_always_inline_functions (struct cgraph_node *node)
    3016              : {
    3017      3608823 :   struct cgraph_edge *e;
    3018      3608823 :   bool inlined = false;
    3019              : 
    3020     13955580 :   for (e = node->callees; e; e = e->next_callee)
    3021              :     {
    3022     10346757 :       struct cgraph_node *callee = e->callee->ultimate_alias_target ();
    3023     10346757 :       gcc_checking_assert (!callee->aux || callee->aux == (void *)(size_t)1);
    3024     10346757 :       if (!DECL_DISREGARD_INLINE_LIMITS (callee->decl)
    3025              :           /* Watch for self-recursive cycles.  */
    3026     10346757 :           || callee->aux)
    3027      9723977 :         continue;
    3028              : 
    3029       622780 :       if (e->recursive_p ())
    3030              :         {
    3031            6 :           if (dump_enabled_p ())
    3032            0 :             dump_printf_loc (MSG_MISSED_OPTIMIZATION, e->call_stmt,
    3033              :                              "  Not inlining recursive call to %C.\n",
    3034              :                              e->callee);
    3035            6 :           e->inline_failed = CIF_RECURSIVE_INLINING;
    3036            6 :           continue;
    3037              :         }
    3038       622774 :       if (callee->definition
    3039       622652 :           && !ipa_fn_summaries->get (callee))
    3040          221 :         compute_fn_summary (callee, true);
    3041              : 
    3042       622774 :       if (!can_early_inline_edge_p (e))
    3043              :         {
    3044              :           /* Set inlined to true if the callee is marked "always_inline" but
    3045              :              is not inlinable.  This will allow flagging an error later in
    3046              :              expand_call_inline in tree-inline.cc.  */
    3047          172 :           if (lookup_attribute ("always_inline",
    3048          172 :                                  DECL_ATTRIBUTES (callee->decl)) != NULL)
    3049           28 :             inlined = true;
    3050          172 :           continue;
    3051              :         }
    3052              : 
    3053       622602 :       if (dump_enabled_p ())
    3054           18 :         dump_printf_loc (MSG_OPTIMIZED_LOCATIONS, e->call_stmt,
    3055              :                          "  Inlining %C into %C (always_inline).\n",
    3056              :                          e->callee, e->caller);
    3057       622602 :       inline_call (e, true, NULL, NULL, false);
    3058       622602 :       callee->aux = (void *)(size_t)1;
    3059              :       /* Inline recursively to handle the case where always_inline function was
    3060              :          not optimized yet since it is a part of a cycle in callgraph.  */
    3061       622602 :       inline_always_inline_functions (e->callee);
    3062       622602 :       callee->aux = NULL;
    3063       622602 :       inlined = true;
    3064              :     }
    3065      3608823 :   return inlined;
    3066              : }
    3067              : 
    3068              : /* Decide on the inlining.  We do so in the topological order to avoid
    3069              :    expenses on updating data structures.  */
    3070              : 
    3071              : static bool
    3072      2499159 : early_inline_small_functions (struct cgraph_node *node)
    3073              : {
    3074      2499159 :   struct cgraph_edge *e;
    3075      2499159 :   bool inlined = false;
    3076              : 
    3077     10733348 :   for (e = node->callees; e; e = e->next_callee)
    3078              :     {
    3079      8234189 :       struct cgraph_node *callee = e->callee->ultimate_alias_target ();
    3080              : 
    3081              :       /* We can encounter not-yet-analyzed function during
    3082              :          early inlining on callgraphs with strongly
    3083              :          connected components.  */
    3084      8234189 :       ipa_fn_summary *s = ipa_fn_summaries->get (callee);
    3085      8234189 :       if (s == NULL || !s->inlinable || !e->inline_failed)
    3086      4378155 :         continue;
    3087              : 
    3088              :       /* Do not consider functions not declared inline.  */
    3089      3856034 :       if (!DECL_DECLARED_INLINE_P (callee->decl)
    3090       882923 :           && !opt_for_fn (node->decl, flag_inline_small_functions)
    3091      3909465 :           && !opt_for_fn (node->decl, flag_inline_functions))
    3092        53366 :         continue;
    3093              : 
    3094      3802668 :       if (dump_enabled_p ())
    3095          158 :         dump_printf_loc (MSG_NOTE, e->call_stmt,
    3096              :                          "Considering inline candidate %C.\n",
    3097              :                          callee);
    3098              : 
    3099      3802668 :       if (!can_early_inline_edge_p (e))
    3100        90975 :         continue;
    3101              : 
    3102      3711693 :       if (e->recursive_p ())
    3103              :         {
    3104         9510 :           if (dump_enabled_p ())
    3105            0 :             dump_printf_loc (MSG_MISSED_OPTIMIZATION, e->call_stmt,
    3106              :                              "  Not inlining: recursive call.\n");
    3107         9510 :           continue;
    3108              :         }
    3109              : 
    3110      3702183 :       if (!want_early_inline_function_p (e))
    3111      1115266 :         continue;
    3112              : 
    3113      2586917 :       if (dump_enabled_p ())
    3114          105 :         dump_printf_loc (MSG_OPTIMIZED_LOCATIONS, e->call_stmt,
    3115              :                          " Inlining %C into %C.\n",
    3116              :                          callee, e->caller);
    3117      2586917 :       inline_call (e, true, NULL, NULL, false);
    3118      2586917 :       inlined = true;
    3119              :     }
    3120              : 
    3121      2499159 :   if (inlined)
    3122       874444 :     ipa_update_overall_fn_summary (node);
    3123              : 
    3124      2499159 :   return inlined;
    3125              : }
    3126              : 
    3127              : /* With auto-fdo inline all functions that was inlined in the train run
    3128              :    and inlining seems useful.  That is there are enough samples in the callee
    3129              :    function.
    3130              : 
    3131              :    Unlike early inlining, we inline recursively.  Profile data is also used
    3132              :    to produce speculative calls which we then inline.  In the case some
    3133              :    speculatin was introduced, set SPECULATIVE_CALLS.  */
    3134              : 
    3135              : static bool
    3136      2500708 : inline_functions_by_afdo (struct cgraph_node *node, bool *speculative_calls)
    3137              : {
    3138      2500708 :   if (!flag_auto_profile || !flag_auto_profile_inlining)
    3139              :     return false;
    3140            0 :   struct cgraph_edge *e;
    3141            0 :   bool inlined = false;
    3142              : 
    3143            0 :   *speculative_calls |= afdo_vpt_for_early_inline (node);
    3144              : 
    3145            0 :   cgraph_edge *next;
    3146            0 :   for (e = node->callees; e; e = next)
    3147              :     {
    3148            0 :       next = e->next_callee;
    3149              : 
    3150            0 :       if (!e->inline_failed)
    3151              :         {
    3152            0 :           inlined |= inline_functions_by_afdo (e->callee, speculative_calls);
    3153            0 :           continue;
    3154              :         }
    3155            0 :       if (!afdo_callsite_hot_enough_for_early_inline (e))
    3156              :         {
    3157              :           /* If we do not want to inline, remove the speculation.  */
    3158            0 :           if (e->speculative)
    3159            0 :             cgraph_edge::resolve_speculation (e);
    3160            0 :           continue;
    3161              :         }
    3162              : 
    3163            0 :       struct cgraph_node *callee = e->callee->ultimate_alias_target ();
    3164            0 :       if (callee->definition
    3165            0 :           && !ipa_fn_summaries->get (callee))
    3166            0 :         compute_fn_summary (callee, true);
    3167              : 
    3168            0 :       if (!can_early_inline_edge_p (e))
    3169              :         {
    3170            0 :           if (dump_enabled_p ())
    3171            0 :             dump_printf_loc (MSG_MISSED_OPTIMIZATION, e->call_stmt,
    3172              :                              "Not inlining %C -> %C using auto-profile, %s.",
    3173              :                              e->caller, e->callee,
    3174              :                              cgraph_inline_failed_string (e->inline_failed));
    3175              :           /* If we do not want to inline, remove the speculation.  */
    3176            0 :           if (e->speculative)
    3177            0 :             cgraph_edge::resolve_speculation (e);
    3178            0 :           continue;
    3179              :         }
    3180              :       /* We can handle recursive inlining by first producing
    3181              :          inline clone.  */
    3182            0 :       if (e->recursive_p ())
    3183              :         {
    3184            0 :           if (dump_enabled_p ())
    3185            0 :             dump_printf_loc (MSG_MISSED_OPTIMIZATION, e->call_stmt,
    3186              :                              "Not inlining %C recursively"
    3187              :                              " using auto-profile.\n",
    3188              :                              e->callee);
    3189              :           /* If we do not want to inline, remove the speculation.  */
    3190            0 :           if (e->speculative)
    3191            0 :             cgraph_edge::resolve_speculation (e);
    3192            0 :           continue;
    3193              :         }
    3194              : 
    3195            0 :       if (dump_enabled_p ())
    3196              :         {
    3197            0 :           if (e->caller->inlined_to)
    3198            0 :             dump_printf_loc (MSG_OPTIMIZED_LOCATIONS, e->call_stmt,
    3199              :                              "Inlining using auto-profile %C into %C "
    3200              :                              "which is transitively inlined to %C.\n",
    3201              :                              callee, e->caller, e->caller->inlined_to);
    3202              :           else
    3203            0 :             dump_printf_loc (MSG_OPTIMIZED_LOCATIONS, e->call_stmt,
    3204              :                              "Inlining using auto-profile %C into %C.\n",
    3205              :                              callee, e->caller);
    3206              :         }
    3207            0 :       if (e->speculative)
    3208            0 :         remove_afdo_speculative_target (e);
    3209            0 :       inline_call (e, true, NULL, NULL, false);
    3210            0 :       inlined |= inline_functions_by_afdo (e->callee, speculative_calls);
    3211            0 :       inlined = true;
    3212              :     }
    3213              : 
    3214            0 :   if (inlined && !node->inlined_to)
    3215            0 :     ipa_update_overall_fn_summary (node);
    3216              : 
    3217              :   return inlined;
    3218              : }
    3219              : 
    3220              : unsigned int
    3221      2986235 : early_inliner (function *fun)
    3222              : {
    3223      2986235 :   struct cgraph_node *node = cgraph_node::get (current_function_decl);
    3224      2986235 :   struct cgraph_edge *edge;
    3225      2986235 :   unsigned int todo = 0;
    3226      2986235 :   int iterations = 0;
    3227      2986235 :   bool inlined = false;
    3228              : 
    3229      2986235 :   if (seen_error ())
    3230              :     return 0;
    3231              : 
    3232              :   /* Do nothing if datastructures for ipa-inliner are already computed.  This
    3233              :      happens when some pass decides to construct new function and
    3234              :      cgraph_add_new_function calls lowering passes and early optimization on
    3235              :      it.  This may confuse ourself when early inliner decide to inline call to
    3236              :      function clone, because function clones don't have parameter list in
    3237              :      ipa-prop matching their signature.  */
    3238      2986229 :   if (ipa_node_params_sum)
    3239              :     return 0;
    3240              : 
    3241      2986221 :   if (flag_checking)
    3242      2986191 :     node->verify ();
    3243      2986221 :   node->remove_all_references ();
    3244              : 
    3245              :   /* Even when not optimizing or not inlining inline always-inline
    3246              :      functions.  */
    3247      2986221 :   inlined = inline_always_inline_functions (node);
    3248              : 
    3249      2986221 :   if (!optimize
    3250      2524504 :       || flag_no_inline
    3251      2500746 :       || !flag_early_inlining)
    3252              :     ;
    3253      2499197 :   else if (lookup_attribute ("flatten",
    3254      2499197 :                              DECL_ATTRIBUTES (node->decl)) != NULL)
    3255              :     {
    3256              :       /* When the function is marked to be flattened, recursively inline
    3257              :          all calls in it.  */
    3258          135 :       if (dump_enabled_p ())
    3259            0 :         dump_printf (MSG_OPTIMIZED_LOCATIONS,
    3260              :                      "Flattening %C\n", node);
    3261          135 :       flatten_function (node, true, true);
    3262          135 :       inlined = true;
    3263              :     }
    3264              :   else
    3265              :     {
    3266              :       /* If some always_inline functions was inlined, apply the changes.
    3267              :          This way we will not account always inline into growth limits and
    3268              :          moreover we will inline calls from always inlines that we skipped
    3269              :          previously because of conditional in can_early_inline_edge_p
    3270              :          which prevents some inlining to always_inline.  */
    3271      2499062 :       if (inlined)
    3272              :         {
    3273       321454 :           timevar_push (TV_INTEGRATION);
    3274       321454 :           todo |= optimize_inline_calls (current_function_decl);
    3275              :           /* optimize_inline_calls call above might have introduced new
    3276              :              statements that don't have inline parameters computed.  */
    3277      1671593 :           for (edge = node->callees; edge; edge = edge->next_callee)
    3278              :             {
    3279              :               /* We can encounter not-yet-analyzed function during
    3280              :                  early inlining on callgraphs with strongly
    3281              :                  connected components.  */
    3282      1350139 :               ipa_call_summary *es = ipa_call_summaries->get_create (edge);
    3283      1350139 :               es->call_stmt_size
    3284      1350139 :                 = estimate_num_insns (edge->call_stmt, &eni_size_weights);
    3285      1350139 :               es->call_stmt_time
    3286      1350139 :                 = estimate_num_insns (edge->call_stmt, &eni_time_weights);
    3287              :             }
    3288       321454 :           ipa_update_overall_fn_summary (node);
    3289       321454 :           inlined = false;
    3290       321454 :           timevar_pop (TV_INTEGRATION);
    3291              :         }
    3292              :       /* We iterate incremental inlining to get trivial cases of indirect
    3293              :          inlining.  */
    3294      3373506 :       while (iterations < opt_for_fn (node->decl,
    3295              :                                       param_early_inliner_max_iterations))
    3296              :         {
    3297      2499159 :           bool inlined = early_inline_small_functions (node);
    3298      2499159 :           bool speculative_calls = false;
    3299      2499159 :           inlined |= inline_functions_by_afdo (node, &speculative_calls);
    3300      2499159 :           if (!inlined)
    3301              :             break;
    3302       874444 :           timevar_push (TV_INTEGRATION);
    3303       874444 :           if (speculative_calls)
    3304              :             {
    3305            0 :               cgraph_edge *next;
    3306            0 :               for (cgraph_edge *e = node->callees; e; e = next)
    3307              :                 {
    3308            0 :                   next = e->next_callee;
    3309            0 :                   cgraph_edge::redirect_call_stmt_to_callee (e);
    3310              :                 }
    3311              :             }
    3312       874444 :           todo |= optimize_inline_calls (current_function_decl);
    3313              : 
    3314              :           /* Technically we ought to recompute inline parameters so the new
    3315              :              iteration of early inliner works as expected.  We however have
    3316              :              values approximately right and thus we only need to update edge
    3317              :              info that might be cleared out for newly discovered edges.  */
    3318      3638516 :           for (edge = node->callees; edge; edge = edge->next_callee)
    3319              :             {
    3320              :               /* We have no summary for new bound store calls yet.  */
    3321      2764072 :               ipa_call_summary *es = ipa_call_summaries->get_create (edge);
    3322      2764072 :               es->call_stmt_size
    3323      2764072 :                 = estimate_num_insns (edge->call_stmt, &eni_size_weights);
    3324      2764072 :               es->call_stmt_time
    3325      2764072 :                 = estimate_num_insns (edge->call_stmt, &eni_time_weights);
    3326              :             }
    3327       874444 :           if (iterations < opt_for_fn (node->decl,
    3328       874444 :                                        param_early_inliner_max_iterations) - 1)
    3329           97 :             ipa_update_overall_fn_summary (node);
    3330       874444 :           timevar_pop (TV_INTEGRATION);
    3331       874444 :           iterations++;
    3332       874444 :           inlined = false;
    3333              :         }
    3334      2499062 :       if (dump_file)
    3335          206 :         fprintf (dump_file, "Iterations: %i\n", iterations);
    3336              :     }
    3337              : 
    3338              :   /* do AFDO inlining in case it was not done as part of early inlining.  */
    3339      2986221 :   if (optimize
    3340      2524504 :       && !flag_no_inline
    3341      2500746 :       && !flag_early_inlining
    3342         1549 :       && flag_auto_profile_inlining)
    3343              :     {
    3344         1549 :       bool speculative_calls = false;
    3345         1549 :       inlined |= inline_functions_by_afdo (node, &speculative_calls);
    3346         1549 :       if (speculative_calls)
    3347              :         {
    3348            0 :           cgraph_edge *next;
    3349            0 :           for (cgraph_edge *e = node->callees; e; e = next)
    3350              :             {
    3351            0 :               next = e->next_callee;
    3352            0 :               cgraph_edge::redirect_call_stmt_to_callee (e);
    3353              :             }
    3354              :         }
    3355              :     }
    3356              : 
    3357      2986221 :   if (inlined)
    3358              :     {
    3359        23683 :       timevar_push (TV_INTEGRATION);
    3360        23683 :       todo |= optimize_inline_calls (current_function_decl);
    3361        23683 :       timevar_pop (TV_INTEGRATION);
    3362              :     }
    3363              : 
    3364      2986221 :   fun->always_inline_functions_inlined = true;
    3365              : 
    3366      2986221 :   return todo;
    3367              : }
    3368              : 
    3369              : /* Do inlining of small functions.  Doing so early helps profiling and other
    3370              :    passes to be somewhat more effective and avoids some code duplication in
    3371              :    later real inlining pass for testcases with very many function calls.  */
    3372              : 
    3373              : namespace {
    3374              : 
    3375              : const pass_data pass_data_early_inline =
    3376              : {
    3377              :   GIMPLE_PASS, /* type */
    3378              :   "einline", /* name */
    3379              :   OPTGROUP_INLINE, /* optinfo_flags */
    3380              :   TV_EARLY_INLINING, /* tv_id */
    3381              :   PROP_ssa, /* properties_required */
    3382              :   0, /* properties_provided */
    3383              :   0, /* properties_destroyed */
    3384              :   0, /* todo_flags_start */
    3385              :   0, /* todo_flags_finish */
    3386              : };
    3387              : 
    3388              : class pass_early_inline : public gimple_opt_pass
    3389              : {
    3390              : public:
    3391       297180 :   pass_early_inline (gcc::context *ctxt)
    3392       594360 :     : gimple_opt_pass (pass_data_early_inline, ctxt)
    3393              :   {}
    3394              : 
    3395              :   /* opt_pass methods: */
    3396              :   unsigned int execute (function *) final override;
    3397              : 
    3398              : }; // class pass_early_inline
    3399              : 
    3400              : unsigned int
    3401      2986235 : pass_early_inline::execute (function *fun)
    3402              : {
    3403      2986235 :   return early_inliner (fun);
    3404              : }
    3405              : 
    3406              : } // anon namespace
    3407              : 
    3408              : gimple_opt_pass *
    3409       297180 : make_pass_early_inline (gcc::context *ctxt)
    3410              : {
    3411       297180 :   return new pass_early_inline (ctxt);
    3412              : }
    3413              : 
    3414              : namespace {
    3415              : 
    3416              : const pass_data pass_data_ipa_inline =
    3417              : {
    3418              :   IPA_PASS, /* type */
    3419              :   "inline", /* name */
    3420              :   OPTGROUP_INLINE, /* optinfo_flags */
    3421              :   TV_IPA_INLINING, /* tv_id */
    3422              :   0, /* properties_required */
    3423              :   0, /* properties_provided */
    3424              :   0, /* properties_destroyed */
    3425              :   0, /* todo_flags_start */
    3426              :   ( TODO_dump_symtab ), /* todo_flags_finish */
    3427              : };
    3428              : 
    3429              : class pass_ipa_inline : public ipa_opt_pass_d
    3430              : {
    3431              : public:
    3432       297180 :   pass_ipa_inline (gcc::context *ctxt)
    3433              :     : ipa_opt_pass_d (pass_data_ipa_inline, ctxt,
    3434              :                       NULL, /* generate_summary */
    3435              :                       NULL, /* write_summary */
    3436              :                       NULL, /* read_summary */
    3437              :                       NULL, /* write_optimization_summary */
    3438              :                       NULL, /* read_optimization_summary */
    3439              :                       NULL, /* stmt_fixup */
    3440              :                       0, /* function_transform_todo_flags_start */
    3441              :                       inline_transform, /* function_transform */
    3442       297180 :                       NULL) /* variable_transform */
    3443       297180 :   {}
    3444              : 
    3445              :   /* opt_pass methods: */
    3446       239354 :   unsigned int execute (function *) final override { return ipa_inline (); }
    3447              : 
    3448              : }; // class pass_ipa_inline
    3449              : 
    3450              : } // anon namespace
    3451              : 
    3452              : ipa_opt_pass_d *
    3453       297180 : make_pass_ipa_inline (gcc::context *ctxt)
    3454              : {
    3455       297180 :   return new pass_ipa_inline (ctxt);
    3456              : }
        

Generated by: LCOV version 2.5.0-beta

LCOV profile is generated on x86_64 machine using following configure options: configure --disable-bootstrap --enable-coverage=opt --enable-languages=c,c++,fortran,go,jit,lto,rust,m2 --enable-host-shared. GCC test suite is run with the built compiler.