gcc/ipa-inline.c

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