gcc/ipa-inline.c

   1 /* Inlining decision heuristics.
   2    Copyright (C) 2003, 2004 Free Software Foundation, Inc.
   3    Contributed by Jan Hubicka
   4
   5 This file is part of GCC.
   6
   7 GCC is free software; you can redistribute it and/or modify it under
   8 the terms of the GNU General Public License as published by the Free
   9 Software Foundation; either version 2, or (at your option) any later
  10 version.
  11
  12 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
  13 WARRANTY; without even the implied warranty of MERCHANTABILITY or
  14 FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  15 for more details.
  16
  17 You should have received a copy of the GNU General Public License
  18 along with GCC; see the file COPYING.  If not, write to the Free
  19 Software Foundation, 59 Temple Place - Suite 330, Boston, MA
  20 02111-1307, USA.  */
  21
  22 /*  Inlining decision heuristics
  23
  24     We separate inlining decisions from the inliner itself and store it
  25     inside callgraph as so called inline plan.  Refer to cgraph.c
  26     documentation about particular representation of inline plans in the
  27     callgraph.
  28
  29     There are three major parts of this file:
  30
  31     cgraph_mark_inline implementation
  32
  33       This function allows to mark given call inline and performs necessary
  34       modifications of cgraph (production of the clones and updating overall
  35       statistics)
  36
  37     inlining heuristics limits
  38
  39       These functions allow to check that particular inlining is allowed
  40       by the limits specified by user (allowed function growth, overall unit
  41       growth and so on).
  42
  43     inlining heuristics
  44
  45       This is implementation of IPA pass aiming to get as much of benefit
  46       from inlining obeying the limits checked above.
  47
  48       The implementation of particular heuristics is separated from
  49       the rest of code to make it easier to replace it with more complicated
  50       implementation in the future.  The rest of inlining code acts as a
  51       library aimed to modify the callgraph and verify that the parameters
  52       on code size growth fits.
  53
  54       To mark given call inline, use cgraph_mark_inline function, the
  55       verification is performed by cgraph_default_inline_p and
  56       cgraph_check_inline_limits.
  57
  58       The heuristics implements simple knapsack style algorithm ordering
  59       all functions by their "profitability" (estimated by code size growth)
  60       and inlining them in priority order.
  61
  62       cgraph_decide_inlining implements heuristics taking whole callgraph
  63       into account, while cgraph_decide_inlining_incrementally considers
  64       only one function at a time and is used in non-unit-at-a-time mode.  */
  65
  66 #include "config.h"
  67 #include "system.h"
  68 #include "coretypes.h"
  69 #include "tm.h"
  70 #include "tree.h"
  71 #include "tree-inline.h"
  72 #include "langhooks.h"
  73 #include "flags.h"
  74 #include "cgraph.h"
  75 #include "diagnostic.h"
  76 #include "timevar.h"
  77 #include "params.h"
  78 #include "fibheap.h"
  79 #include "intl.h"
  80 #include "tree-pass.h"
  81 #include "coverage.h"
  82
  83 /* Statistics we collect about inlining algorithm.  */
  84 static int ncalls_inlined;
  85 static int nfunctions_inlined;
  86 static int initial_insns;
  87 static int overall_insns;
  88 static int max_insns;
  89 static gcov_type max_count;
  90
  91 /* Estimate size of the function after inlining WHAT into TO.  */
  92
  93 static int
  94 cgraph_estimate_size_after_inlining (int times, struct cgraph_node *to,
  95                                      struct cgraph_node *what)
  96 {
  97   int size;
  98   tree fndecl = what->decl, arg;
  99   int call_insns = PARAM_VALUE (PARAM_INLINE_CALL_COST);
 100
 101   for (arg = DECL_ARGUMENTS (fndecl); arg; arg = TREE_CHAIN (arg))
 102     call_insns += estimate_move_cost (TREE_TYPE (arg));
 103   size = (what->global.insns - call_insns) * times + to->global.insns;
 104   gcc_assert (size >= 0);
 105   return size;
 106 }
 107
 108 /* E is expected to be an edge being inlined.  Clone destination node of
 109    the edge and redirect it to the new clone.
 110    DUPLICATE is used for bookkeeping on whether we are actually creating new
 111    clones or re-using node originally representing out-of-line function call.
 112    */
 113 void
 114 cgraph_clone_inlined_nodes (struct cgraph_edge *e, bool duplicate)
 115 {
 116   struct cgraph_node *n;
 117
 118   /* We may eliminate the need for out-of-line copy to be output.  In that
 119      case just go ahead and re-use it.  */
 120   if (!e->callee->callers->next_caller
 121       && (!e->callee->needed || DECL_EXTERNAL (e->callee->decl))
 122       && duplicate
 123       && flag_unit_at_a_time)
 124     {
 125       gcc_assert (!e->callee->global.inlined_to);
 126       if (!DECL_EXTERNAL (e->callee->decl))
 127         overall_insns -= e->callee->global.insns, nfunctions_inlined++;
 128       duplicate = 0;
 129     }
 130    else if (duplicate)
 131     {
 132       n = cgraph_clone_node (e->callee, e->count, e->loop_nest);
 133       cgraph_redirect_edge_callee (e, n);
 134     }
 135
 136   if (e->caller->global.inlined_to)
 137     e->callee->global.inlined_to = e->caller->global.inlined_to;
 138   else
 139     e->callee->global.inlined_to = e->caller;
 140
 141   /* Recursively clone all bodies.  */
 142   for (e = e->callee->callees; e; e = e->next_callee)
 143     if (!e->inline_failed)
 144       cgraph_clone_inlined_nodes (e, duplicate);
 145 }
 146
 147 /* Mark edge E as inlined and update callgraph accordingly.  */
 148
 149 void
 150 cgraph_mark_inline_edge (struct cgraph_edge *e)
 151 {
 152   int old_insns = 0, new_insns = 0;
 153   struct cgraph_node *to = NULL, *what;
 154
 155   gcc_assert (e->inline_failed);
 156   e->inline_failed = NULL;
 157
 158   if (!e->callee->global.inlined && flag_unit_at_a_time)
 159     DECL_POSSIBLY_INLINED (e->callee->decl) = true;
 160   e->callee->global.inlined = true;
 161
 162   cgraph_clone_inlined_nodes (e, true);
 163
 164   what = e->callee;
 165
 166   /* Now update size of caller and all functions caller is inlined into.  */
 167   for (;e && !e->inline_failed; e = e->caller->callers)
 168     {
 169       old_insns = e->caller->global.insns;
 170       new_insns = cgraph_estimate_size_after_inlining (1, e->caller,
 171                                                        what);
 172       gcc_assert (new_insns >= 0);
 173       to = e->caller;
 174       to->global.insns = new_insns;
 175     }
 176   gcc_assert (what->global.inlined_to == to);
 177   if (new_insns > old_insns)
 178     overall_insns += new_insns - old_insns;
 179   ncalls_inlined++;
 180 }
 181
 182 /* Mark all calls of EDGE->CALLEE inlined into EDGE->CALLER.
 183    Return following unredirected edge in the list of callers
 184    of EDGE->CALLEE  */
 185
 186 static struct cgraph_edge *
 187 cgraph_mark_inline (struct cgraph_edge *edge)
 188 {
 189   struct cgraph_node *to = edge->caller;
 190   struct cgraph_node *what = edge->callee;
 191   struct cgraph_edge *e, *next;
 192   int times = 0;
 193
 194   /* Look for all calls, mark them inline and clone recursively
 195      all inlined functions.  */
 196   for (e = what->callers; e; e = next)
 197     {
 198       next = e->next_caller;
 199       if (e->caller == to && e->inline_failed)
 200         {
 201           cgraph_mark_inline_edge (e);
 202           if (e == edge)
 203             edge = next;
 204           times++;
 205         }
 206     }
 207   gcc_assert (times);
 208   return edge;
 209 }
 210
 211 /* Estimate the growth caused by inlining NODE into all callees.  */
 212
 213 static int
 214 cgraph_estimate_growth (struct cgraph_node *node)
 215 {
 216   int growth = 0;
 217   struct cgraph_edge *e;
 218   if (node->global.estimated_growth != INT_MIN)
 219     return node->global.estimated_growth;
 220
 221   for (e = node->callers; e; e = e->next_caller)
 222     if (e->inline_failed)
 223       growth += (cgraph_estimate_size_after_inlining (1, e->caller, node)
 224                  - e->caller->global.insns);
 225
 226   /* ??? Wrong for self recursive functions or cases where we decide to not
 227      inline for different reasons, but it is not big deal as in that case
 228      we will keep the body around, but we will also avoid some inlining.  */
 229   if (!node->needed && !DECL_EXTERNAL (node->decl))
 230     growth -= node->global.insns;
 231
 232   node->global.estimated_growth = growth;
 233   return growth;
 234 }
 235
 236 /* Return false when inlining WHAT into TO is not good idea
 237    as it would cause too large growth of function bodies.  */
 238
 239 static bool
 240 cgraph_check_inline_limits (struct cgraph_node *to, struct cgraph_node *what,
 241                             const char **reason)
 242 {
 243   int times = 0;
 244   struct cgraph_edge *e;
 245   int newsize;
 246   int limit;
 247
 248   if (to->global.inlined_to)
 249     to = to->global.inlined_to;
 250
 251   for (e = to->callees; e; e = e->next_callee)
 252     if (e->callee == what)
 253       times++;
 254
 255   /* When inlining large function body called once into small function,
 256      take the inlined function as base for limiting the growth.  */
 257   if (to->local.self_insns > what->local.self_insns)
 258     limit = to->local.self_insns;
 259   else
 260     limit = what->local.self_insns;
 261
 262   limit += limit * PARAM_VALUE (PARAM_LARGE_FUNCTION_GROWTH) / 100;
 263
 264   newsize = cgraph_estimate_size_after_inlining (times, to, what);
 265   if (newsize > PARAM_VALUE (PARAM_LARGE_FUNCTION_INSNS)
 266       && newsize > limit)
 267     {
 268       if (reason)
 269         *reason = N_("--param large-function-growth limit reached");
 270       return false;
 271     }
 272   return true;
 273 }
 274
 275 /* Return true when function N is small enough to be inlined.  */
 276
 277 bool
 278 cgraph_default_inline_p (struct cgraph_node *n)
 279 {
 280   if (!DECL_INLINE (n->decl) || !DECL_SAVED_TREE (n->decl))
 281     return false;
 282   if (DECL_DECLARED_INLINE_P (n->decl))
 283     return n->global.insns < MAX_INLINE_INSNS_SINGLE;
 284   else
 285     return n->global.insns < MAX_INLINE_INSNS_AUTO;
 286 }
 287
 288 /* Return true when inlining WHAT would create recursive inlining.
 289    We call recursive inlining all cases where same function appears more than
 290    once in the single recursion nest path in the inline graph.  */
 291
 292 static bool
 293 cgraph_recursive_inlining_p (struct cgraph_node *to,
 294                              struct cgraph_node *what,
 295                              const char **reason)
 296 {
 297   bool recursive;
 298   if (to->global.inlined_to)
 299     recursive = what->decl == to->global.inlined_to->decl;
 300   else
 301     recursive = what->decl == to->decl;
 302   /* Marking recursive function inline has sane semantic and thus we should
 303      not warn on it.  */
 304   if (recursive && reason)
 305     *reason = (what->local.disregard_inline_limits
 306                ? N_("recursive inlining") : "");
 307   return recursive;
 308 }
 309
 310 /* Return true if the call can be hot.  */
 311 static bool
 312 cgraph_maybe_hot_edge_p (struct cgraph_edge *edge)
 313 {
 314   if (profile_info && flag_branch_probabilities
 315       && (edge->count
 316           <= profile_info->sum_max / PARAM_VALUE (HOT_BB_COUNT_FRACTION)))
 317     return false;
 318   return true;
 319 }
 320
 321 /* A cost model driving the inlining heuristics in a way so the edges with
 322    smallest badness are inlined first.  After each inlining is performed
 323    the costs of all caller edges of nodes affected are recomputed so the
 324    metrics may accurately depend on values such as number of inlinable callers
 325    of the function or function body size.
 326
 327    For the moment we use estimated growth caused by inlining callee into all
 328    it's callers for driving the inlining but once we have loop depth or
 329    frequency information readily available we should do better.
 330
 331    With profiling we use number of executions of each edge to drive the cost.
 332    We also should distinguish hot and cold calls where the cold calls are
 333    inlined into only when code size is overall improved.
 334
 335    Value INT_MAX can be returned to prevent function from being inlined.
 336    */
 337
 338 static int
 339 cgraph_edge_badness (struct cgraph_edge *edge)
 340 {
 341   if (max_count)
 342     {
 343       int growth =
 344         cgraph_estimate_size_after_inlining (1, edge->caller, edge->callee);
 345       growth -= edge->caller->global.insns;
 346
 347       /* Always prefer inlining saving code size.  */
 348       if (growth <= 0)
 349         return INT_MIN - growth;
 350       return ((int)((double)edge->count * INT_MIN / max_count)) / growth;
 351     }
 352   else
 353   {
 354     int nest = MIN (edge->loop_nest, 8);
 355     int badness = cgraph_estimate_growth (edge->callee) * 256;
 356
 357     badness >>= nest;
 358
 359     /* Make recursive inlining happen always after other inlining is done.  */
 360     if (cgraph_recursive_inlining_p (edge->caller, edge->callee, NULL))
 361       return badness + 1;
 362     else
 363       return badness;
 364   }
 365 }
 366
 367 /* Recompute heap nodes for each of caller edge.  */
 368
 369 static void
 370 update_caller_keys (fibheap_t heap, struct cgraph_node *node,
 371                     bitmap updated_nodes)
 372 {
 373   struct cgraph_edge *edge;
 374
 375   if (!node->local.inlinable || node->local.disregard_inline_limits
 376       || node->global.inlined_to)
 377     return;
 378   if (bitmap_bit_p (updated_nodes, node->uid))
 379     return;
 380   bitmap_set_bit (updated_nodes, node->uid);
 381
 382   for (edge = node->callers; edge; edge = edge->next_caller)
 383     if (edge->inline_failed)
 384       {
 385         int badness = cgraph_edge_badness (edge);
 386         if (edge->aux)
 387           {
 388             fibnode_t n = edge->aux;
 389             gcc_assert (n->data == edge);
 390             if (n->key == badness)
 391               continue;
 392
 393             /* fibheap_replace_key only increase the keys.  */
 394             if (fibheap_replace_key (heap, n, badness))
 395               continue;
 396             fibheap_delete_node (heap, edge->aux);
 397           }
 398         edge->aux = fibheap_insert (heap, badness, edge);
 399       }
 400 }
 401
 402 /* Recompute heap nodes for each of caller edges of each of callees.  */
 403
 404 static void
 405 update_callee_keys (fibheap_t heap, struct cgraph_node *node,
 406                     bitmap updated_nodes)
 407 {
 408   struct cgraph_edge *e;
 409   node->global.estimated_growth = INT_MIN;
 410
 411   for (e = node->callees; e; e = e->next_callee)
 412     if (e->inline_failed)
 413       update_caller_keys (heap, e->callee, updated_nodes);
 414     else if (!e->inline_failed)
 415       update_callee_keys (heap, e->callee, updated_nodes);
 416 }
 417
 418 /* Enqueue all recursive calls from NODE into priority queue depending on
 419    how likely we want to recursively inline the call.  */
 420
 421 static void
 422 lookup_recursive_calls (struct cgraph_node *node, struct cgraph_node *where,
 423                         fibheap_t heap)
 424 {
 425   static int priority;
 426   struct cgraph_edge *e;
 427   for (e = where->callees; e; e = e->next_callee)
 428     if (e->callee == node)
 429       {
 430         /* FIXME: Once counts and frequencies are available we should drive the
 431            order by these.  For now force the order to be simple queue since
 432            we get order dependent on recursion depth for free by this.  */
 433         fibheap_insert (heap, priority++, e);
 434       }
 435   for (e = where->callees; e; e = e->next_callee)
 436     if (!e->inline_failed)
 437       lookup_recursive_calls (node, e->callee, heap);
 438 }
 439
 440 /* Decide on recursive inlining: in the case function has recursive calls,
 441    inline until body size reaches given argument.  */
 442
 443 static bool
 444 cgraph_decide_recursive_inlining (struct cgraph_node *node)
 445 {
 446   int limit = PARAM_VALUE (PARAM_MAX_INLINE_INSNS_RECURSIVE_AUTO);
 447   int max_depth = PARAM_VALUE (PARAM_MAX_INLINE_RECURSIVE_DEPTH_AUTO);
 448   fibheap_t heap;
 449   struct cgraph_edge *e;
 450   struct cgraph_node *master_clone;
 451   int depth = 0;
 452   int n = 0;
 453
 454   if (DECL_DECLARED_INLINE_P (node->decl))
 455     {
 456       limit = PARAM_VALUE (PARAM_MAX_INLINE_INSNS_RECURSIVE);
 457       max_depth = PARAM_VALUE (PARAM_MAX_INLINE_RECURSIVE_DEPTH);
 458     }
 459
 460   /* Make sure that function is small enough to be considered for inlining.  */
 461   if (!max_depth
 462       || cgraph_estimate_size_after_inlining (1, node, node)  >= limit)
 463     return false;
 464   heap = fibheap_new ();
 465   lookup_recursive_calls (node, node, heap);
 466   if (fibheap_empty (heap))
 467     {
 468       fibheap_delete (heap);
 469       return false;
 470     }
 471
 472   if (dump_file)
 473     fprintf (dump_file,
 474              "  Performing recursive inlining on %s\n",
 475              cgraph_node_name (node));
 476
 477   /* We need original clone to copy around.  */
 478   master_clone = cgraph_clone_node (node, 0, 1);
 479   master_clone->needed = true;
 480   for (e = master_clone->callees; e; e = e->next_callee)
 481     if (!e->inline_failed)
 482       cgraph_clone_inlined_nodes (e, true);
 483
 484   /* Do the inlining and update list of recursive call during process.  */
 485   while (!fibheap_empty (heap)
 486          && cgraph_estimate_size_after_inlining (1, node, master_clone) <= limit)
 487     {
 488       struct cgraph_edge *curr = fibheap_extract_min (heap);
 489       struct cgraph_node *node;
 490
 491       depth = 0;
 492       for (node = curr->caller;
 493            node; node = node->global.inlined_to)
 494         if (node->decl == curr->callee->decl)
 495           depth++;
 496       if (depth > max_depth)
 497         continue;
 498
 499       if (dump_file)
 500         fprintf (dump_file,
 501                  "   Inlining call of depth %i\n", depth);
 502       cgraph_redirect_edge_callee (curr, master_clone);
 503       cgraph_mark_inline_edge (curr);
 504       lookup_recursive_calls (node, curr->callee, heap);
 505       n++;
 506     }
 507
 508   fibheap_delete (heap);
 509   if (dump_file)
 510     fprintf (dump_file,
 511              "\n   Inlined %i times, body grown from %i to %i insns\n", n,
 512              master_clone->global.insns, node->global.insns);
 513
 514   /* Remove master clone we used for inlining.  We rely that clones inlined
 515      into master clone gets queued just before master clone so we don't
 516      need recursion.  */
 517   for (node = cgraph_nodes; node != master_clone;
 518        node = node->next)
 519     if (node->global.inlined_to == master_clone)
 520       cgraph_remove_node (node);
 521   cgraph_remove_node (master_clone);
 522   return true;
 523 }
 524
 525 /* Set inline_failed for all callers of given function to REASON.  */
 526
 527 static void
 528 cgraph_set_inline_failed (struct cgraph_node *node, const char *reason)
 529 {
 530   struct cgraph_edge *e;
 531
 532   if (dump_file)
 533     fprintf (dump_file, "Inlining failed: %s\n", reason);
 534   for (e = node->callers; e; e = e->next_caller)
 535     if (e->inline_failed)
 536       e->inline_failed = reason;
 537 }
 538
 539 /* We use greedy algorithm for inlining of small functions:
 540    All inline candidates are put into prioritized heap based on estimated
 541    growth of the overall number of instructions and then update the estimates.
 542
 543    INLINED and INLINED_CALEES are just pointers to arrays large enough
 544    to be passed to cgraph_inlined_into and cgraph_inlined_callees.  */
 545
 546 static void
 547 cgraph_decide_inlining_of_small_functions (void)
 548 {
 549   struct cgraph_node *node;
 550   struct cgraph_edge *edge;
 551   fibheap_t heap = fibheap_new ();
 552   bitmap updated_nodes = BITMAP_ALLOC (NULL);
 553
 554   if (dump_file)
 555     fprintf (dump_file, "\nDeciding on smaller functions:\n");
 556
 557   /* Put all inline candidates into the heap.  */
 558
 559   for (node = cgraph_nodes; node; node = node->next)
 560     {
 561       if (!node->local.inlinable || !node->callers
 562           || node->local.disregard_inline_limits)
 563         continue;
 564       if (dump_file)
 565         fprintf (dump_file, "Considering inline candidate %s.\n", cgraph_node_name (node));
 566
 567       node->global.estimated_growth = INT_MIN;
 568       if (!cgraph_default_inline_p (node))
 569         {
 570           cgraph_set_inline_failed (node,
 571             N_("--param max-inline-insns-single limit reached"));
 572           continue;
 573         }
 574
 575       for (edge = node->callers; edge; edge = edge->next_caller)
 576         if (edge->inline_failed)
 577           {
 578             gcc_assert (!edge->aux);
 579             edge->aux = fibheap_insert (heap, cgraph_edge_badness (edge), edge);
 580           }
 581     }
 582   while (overall_insns <= max_insns && (edge = fibheap_extract_min (heap)))
 583     {
 584       int old_insns = overall_insns;
 585       struct cgraph_node *where;
 586       int growth =
 587         cgraph_estimate_size_after_inlining (1, edge->caller, edge->callee);
 588
 589       growth -= edge->caller->global.insns;
 590
 591       if (dump_file)
 592         {
 593           fprintf (dump_file,
 594                    "\nConsidering %s with %i insns to be inlined into %s\n"
 595                    " Estimated growth after inlined into all callees is %+i insns.\n"
 596                    " Estimated badness is %i.\n",
 597                    cgraph_node_name (edge->callee),
 598                    edge->callee->global.insns,
 599                    cgraph_node_name (edge->caller),
 600                    cgraph_estimate_growth (edge->callee),
 601                    cgraph_edge_badness (edge));
 602           if (edge->count)
 603             fprintf (dump_file," Called "HOST_WIDEST_INT_PRINT_DEC"x\n", edge->count);
 604         }
 605       gcc_assert (edge->aux);
 606       edge->aux = NULL;
 607       if (!edge->inline_failed)
 608         continue;
 609
 610       /* When not having profile info ready we don't weight by any way the
 611          position of call in procedure itself.  This means if call of
 612          function A from function B seems profitable to inline, the recursive
 613          call of function A in inline copy of A in B will look profitable too
 614          and we end up inlining until reaching maximal function growth.  This
 615          is not good idea so prohibit the recursive inlining.
 616
 617          ??? When the frequencies are taken into account we might not need this
 618          restriction.   */
 619       if (!max_count)
 620         {
 621           where = edge->caller;
 622           while (where->global.inlined_to)
 623             {
 624               if (where->decl == edge->callee->decl)
 625                 break;
 626               where = where->callers->caller;
 627             }
 628           if (where->global.inlined_to)
 629             {
 630               edge->inline_failed
 631                 = (edge->callee->local.disregard_inline_limits ? N_("recursive inlining") : "");
 632               if (dump_file)
 633                 fprintf (dump_file, " inline_failed:Recursive inlining performed only for function itself.\n");
 634               continue;
 635             }
 636         }
 637
 638       if (!cgraph_maybe_hot_edge_p (edge) && growth > 0)
 639         {
 640           if (!cgraph_recursive_inlining_p (edge->caller, edge->callee,
 641                                             &edge->inline_failed))
 642             {
 643               edge->inline_failed =
 644                 N_("call is unlikely");
 645               if (dump_file)
 646                 fprintf (dump_file, " inline_failed:%s.\n", edge->inline_failed);
 647             }
 648           continue;
 649         }
 650       if (!cgraph_default_inline_p (edge->callee))
 651         {
 652           if (!cgraph_recursive_inlining_p (edge->caller, edge->callee,
 653                                             &edge->inline_failed))
 654             {
 655               edge->inline_failed =
 656                 N_("--param max-inline-insns-single limit reached after inlining into the callee");
 657               if (dump_file)
 658                 fprintf (dump_file, " inline_failed:%s.\n", edge->inline_failed);
 659             }
 660           continue;
 661         }
 662       if (cgraph_recursive_inlining_p (edge->caller, edge->callee,
 663                                        &edge->inline_failed))
 664         {
 665           where = edge->caller;
 666           if (where->global.inlined_to)
 667             where = where->global.inlined_to;
 668           if (!cgraph_decide_recursive_inlining (where))
 669             continue;
 670           update_callee_keys (heap, where, updated_nodes);
 671         }
 672       else
 673         {
 674           if (!cgraph_check_inline_limits (edge->caller, edge->callee,
 675                                            &edge->inline_failed))
 676             {
 677               if (dump_file)
 678                 fprintf (dump_file, " Not inlining into %s:%s.\n",
 679                          cgraph_node_name (edge->caller), edge->inline_failed);
 680               continue;
 681             }
 682           cgraph_mark_inline_edge (edge);
 683          update_callee_keys (heap, edge->callee, updated_nodes);
 684         }
 685       where = edge->caller;
 686       if (where->global.inlined_to)
 687         where = where->global.inlined_to;
 688
 689       /* Our profitability metric can depend on local properties
 690          such as number of inlinable calls and size of the function body.
 691          After inlining these properties might change for the function we
 692          inlined into (since it's body size changed) and for the functions
 693          called by function we inlined (since number of it inlinable callers
 694          might change).  */
 695       update_caller_keys (heap, where, updated_nodes);
 696       bitmap_clear (updated_nodes);
 697
 698       if (dump_file)
 699         fprintf (dump_file,
 700                  " Inlined into %s which now has %i insns.\n",
 701                  cgraph_node_name (edge->caller),
 702                  edge->caller->global.insns);
 703       if (dump_file)
 704         fprintf (dump_file,
 705                  " Inlined for a net change of %+i insns.\n",
 706                  overall_insns - old_insns);
 707     }
 708   while ((edge = fibheap_extract_min (heap)) != NULL)
 709     {
 710       gcc_assert (edge->aux);
 711       edge->aux = NULL;
 712       if (!edge->callee->local.disregard_inline_limits && edge->inline_failed
 713           && !cgraph_recursive_inlining_p (edge->caller, edge->callee,
 714                                            &edge->inline_failed))
 715         edge->inline_failed = N_("--param inline-unit-growth limit reached");
 716     }
 717   fibheap_delete (heap);
 718   BITMAP_FREE (updated_nodes);
 719 }
 720
 721 /* Decide on the inlining.  We do so in the topological order to avoid
 722    expenses on updating data structures.  */
 723
 724 static void
 725 cgraph_decide_inlining (void)
 726 {
 727   struct cgraph_node *node;
 728   int nnodes;
 729   struct cgraph_node **order =
 730     xcalloc (cgraph_n_nodes, sizeof (struct cgraph_node *));
 731   int old_insns = 0;
 732   int i;
 733
 734   timevar_push (TV_INLINE_HEURISTICS);
 735   max_count = 0;
 736   for (node = cgraph_nodes; node; node = node->next)
 737     {
 738       struct cgraph_edge *e;
 739       initial_insns += node->local.self_insns;
 740       for (e = node->callees; e; e = e->next_callee)
 741         if (max_count < e->count)
 742           max_count = e->count;
 743     }
 744   overall_insns = initial_insns;
 745   gcc_assert (!max_count || (profile_info && flag_branch_probabilities));
 746
 747   max_insns = ((HOST_WIDEST_INT) overall_insns
 748                * (100 + PARAM_VALUE (PARAM_INLINE_UNIT_GROWTH)) / 100);
 749
 750   nnodes = cgraph_postorder (order);
 751
 752   if (dump_file)
 753     fprintf (dump_file,
 754              "\nDeciding on inlining.  Starting with %i insns.\n",
 755              initial_insns);
 756
 757   for (node = cgraph_nodes; node; node = node->next)
 758     node->aux = 0;
 759
 760   if (dump_file)
 761     fprintf (dump_file, "\nInlining always_inline functions:\n");
 762
 763   /* In the first pass mark all always_inline edges.  Do this with a priority
 764      so none of our later choices will make this impossible.  */
 765   for (i = nnodes - 1; i >= 0; i--)
 766     {
 767       struct cgraph_edge *e, *next;
 768
 769       node = order[i];
 770
 771       if (!node->local.disregard_inline_limits)
 772         continue;
 773       if (dump_file)
 774         fprintf (dump_file,
 775                  "\nConsidering %s %i insns (always inline)\n",
 776                  cgraph_node_name (node), node->global.insns);
 777       old_insns = overall_insns;
 778       for (e = node->callers; e; e = next)
 779         {
 780           next = e->next_caller;
 781           if (!e->inline_failed)
 782             continue;
 783           if (cgraph_recursive_inlining_p (e->caller, e->callee,
 784                                            &e->inline_failed))
 785             continue;
 786           cgraph_mark_inline_edge (e);
 787           if (dump_file)
 788             fprintf (dump_file,
 789                      " Inlined into %s which now has %i insns.\n",
 790                      cgraph_node_name (e->caller),
 791                      e->caller->global.insns);
 792         }
 793       if (dump_file)
 794         fprintf (dump_file,
 795                  " Inlined for a net change of %+i insns.\n",
 796                  overall_insns - old_insns);
 797     }
 798
 799   if (!flag_really_no_inline)
 800     {
 801       cgraph_decide_inlining_of_small_functions ();
 802
 803       if (dump_file)
 804         fprintf (dump_file, "\nDeciding on functions called once:\n");
 805
 806       /* And finally decide what functions are called once.  */
 807
 808       for (i = nnodes - 1; i >= 0; i--)
 809         {
 810           node = order[i];
 811
 812           if (node->callers && !node->callers->next_caller && !node->needed
 813               && node->local.inlinable && node->callers->inline_failed
 814               && !DECL_EXTERNAL (node->decl) && !DECL_COMDAT (node->decl))
 815             {
 816               bool ok = true;
 817               struct cgraph_node *node1;
 818
 819               /* Verify that we won't duplicate the caller.  */
 820               for (node1 = node->callers->caller;
 821                    node1->callers && !node1->callers->inline_failed
 822                    && ok; node1 = node1->callers->caller)
 823                 if (node1->callers->next_caller || node1->needed)
 824                   ok = false;
 825               if (ok)
 826                 {
 827                   if (dump_file)
 828                     fprintf (dump_file,
 829                              "\nConsidering %s %i insns.\n"
 830                              " Called once from %s %i insns.\n",
 831                              cgraph_node_name (node), node->global.insns,
 832                              cgraph_node_name (node->callers->caller),
 833                              node->callers->caller->global.insns);
 834
 835                   old_insns = overall_insns;
 836
 837                   if (cgraph_check_inline_limits (node->callers->caller, node,
 838                                                   NULL))
 839                     {
 840                       cgraph_mark_inline (node->callers);
 841                       if (dump_file)
 842                         fprintf (dump_file,
 843                                  " Inlined into %s which now has %i insns"
 844                                  " for a net change of %+i insns.\n",
 845                                  cgraph_node_name (node->callers->caller),
 846                                  node->callers->caller->global.insns,
 847                                  overall_insns - old_insns);
 848                     }
 849                   else
 850                     {
 851                       if (dump_file)
 852                         fprintf (dump_file,
 853                                  " Inline limit reached, not inlined.\n");
 854                     }
 855                 }
 856             }
 857         }
 858     }
 859
 860   /* We will never output extern functions we didn't inline.
 861      ??? Perhaps we can prevent accounting of growth of external
 862      inline functions.  */
 863
 864   cgraph_remove_unreachable_nodes (false, dump_file);
 865
 866   if (dump_file)
 867     fprintf (dump_file,
 868              "\nInlined %i calls, eliminated %i functions, "
 869              "%i insns turned to %i insns.\n\n",
 870              ncalls_inlined, nfunctions_inlined, initial_insns,
 871              overall_insns);
 872   free (order);
 873   timevar_pop (TV_INLINE_HEURISTICS);
 874 }
 875
 876 /* Decide on the inlining.  We do so in the topological order to avoid
 877    expenses on updating data structures.  */
 878
 879 void
 880 cgraph_decide_inlining_incrementally (struct cgraph_node *node)
 881 {
 882   struct cgraph_edge *e;
 883
 884   /* First of all look for always inline functions.  */
 885   for (e = node->callees; e; e = e->next_callee)
 886     if (e->callee->local.disregard_inline_limits
 887         && e->inline_failed
 888         && !cgraph_recursive_inlining_p (node, e->callee, &e->inline_failed)
 889         /* ??? It is possible that renaming variable removed the function body
 890            in duplicate_decls. See gcc.c-torture/compile/20011119-2.c  */
 891         && DECL_SAVED_TREE (e->callee->decl))
 892       cgraph_mark_inline (e);
 893
 894   /* Now do the automatic inlining.  */
 895   if (!flag_really_no_inline)
 896     for (e = node->callees; e; e = e->next_callee)
 897       if (e->callee->local.inlinable
 898           && e->inline_failed
 899           && !e->callee->local.disregard_inline_limits
 900           && !cgraph_recursive_inlining_p (node, e->callee, &e->inline_failed)
 901           && cgraph_check_inline_limits (node, e->callee, &e->inline_failed)
 902           && DECL_SAVED_TREE (e->callee->decl))
 903         {
 904           if (cgraph_default_inline_p (e->callee))
 905             cgraph_mark_inline (e);
 906           else
 907             e->inline_failed
 908               = N_("--param max-inline-insns-single limit reached");
 909         }
 910 }
 911
 912 /* When inlining shall be performed.  */
 913 static bool
 914 cgraph_gate_inlining (void)
 915 {
 916   return flag_inline_trees;
 917 }
 918
 919 struct tree_opt_pass pass_ipa_inline =
 920 {
 921   "inline",                             /* name */
 922   cgraph_gate_inlining,                 /* gate */
 923   cgraph_decide_inlining,               /* execute */
 924   NULL,                                 /* sub */
 925   NULL,                                 /* next */
 926   0,                                    /* static_pass_number */
 927   TV_INTEGRATION,                       /* tv_id */
 928   0,                                    /* properties_required */
 929   PROP_trees,                           /* properties_provided */
 930   0,                                    /* properties_destroyed */
 931   0,                                    /* todo_flags_start */
 932   TODO_dump_cgraph | TODO_dump_func,    /* todo_flags_finish */
 933   0                                     /* letter */
 934 };