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 allow 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
  82 /* Statistics we collect about inlining algorithm.  */
  83 static int ncalls_inlined;
  84 static int nfunctions_inlined;
  85 static int initial_insns;
  86 static int overall_insns;
  87
  88 /* Estimate size of the function after inlining WHAT into TO.  */
  89
  90 static int
  91 cgraph_estimate_size_after_inlining (int times, struct cgraph_node *to,
  92                                      struct cgraph_node *what)
  93 {
  94   tree fndecl = what->decl;
  95   tree arg;
  96   int call_insns = PARAM_VALUE (PARAM_INLINE_CALL_COST);
  97   for (arg = DECL_ARGUMENTS (fndecl); arg; arg = TREE_CHAIN (arg))
  98     call_insns += estimate_move_cost (TREE_TYPE (arg));
  99   return (what->global.insns - call_insns) * times + to->global.insns;
 100 }
 101
 102 /* E is expected to be an edge being inlined.  Clone destination node of
 103    the edge and redirect it to the new clone.
 104    DUPLICATE is used for bookkeeping on whether we are actually creating new
 105    clones or re-using node originally representing out-of-line function call.
 106    */
 107 void
 108 cgraph_clone_inlined_nodes (struct cgraph_edge *e, bool duplicate)
 109 {
 110   struct cgraph_node *n;
 111
 112   /* We may eliminate the need for out-of-line copy to be output.  In that
 113      case just go ahead and re-use it.  */
 114   if (!e->callee->callers->next_caller
 115       && (!e->callee->needed || DECL_EXTERNAL (e->callee->decl))
 116       && duplicate
 117       && flag_unit_at_a_time)
 118     {
 119       gcc_assert (!e->callee->global.inlined_to);
 120       if (!DECL_EXTERNAL (e->callee->decl))
 121         overall_insns -= e->callee->global.insns, nfunctions_inlined++;
 122       duplicate = 0;
 123     }
 124    else if (duplicate)
 125     {
 126       n = cgraph_clone_node (e->callee);
 127       cgraph_redirect_edge_callee (e, n);
 128     }
 129
 130   if (e->caller->global.inlined_to)
 131     e->callee->global.inlined_to = e->caller->global.inlined_to;
 132   else
 133     e->callee->global.inlined_to = e->caller;
 134
 135   /* Recursively clone all bodies.  */
 136   for (e = e->callee->callees; e; e = e->next_callee)
 137     if (!e->inline_failed)
 138       cgraph_clone_inlined_nodes (e, duplicate);
 139 }
 140
 141 /* Mark edge E as inlined and update callgraph accordingly.  */
 142
 143 void
 144 cgraph_mark_inline_edge (struct cgraph_edge *e)
 145 {
 146   int old_insns = 0, new_insns = 0;
 147   struct cgraph_node *to = NULL, *what;
 148
 149   gcc_assert (e->inline_failed);
 150   e->inline_failed = NULL;
 151
 152   if (!e->callee->global.inlined && flag_unit_at_a_time)
 153     DECL_POSSIBLY_INLINED (e->callee->decl) = true;
 154   e->callee->global.inlined = true;
 155
 156   cgraph_clone_inlined_nodes (e, true);
 157
 158   what = e->callee;
 159
 160   /* Now update size of caller and all functions caller is inlined into.  */
 161   for (;e && !e->inline_failed; e = e->caller->callers)
 162     {
 163       old_insns = e->caller->global.insns;
 164       new_insns = cgraph_estimate_size_after_inlining (1, e->caller,
 165                                                        what);
 166       gcc_assert (new_insns >= 0);
 167       to = e->caller;
 168       to->global.insns = new_insns;
 169     }
 170   gcc_assert (what->global.inlined_to == to);
 171   if (new_insns > old_insns)
 172     overall_insns += new_insns - old_insns;
 173   ncalls_inlined++;
 174 }
 175
 176 /* Mark all calls of EDGE->CALLEE inlined into EDGE->CALLER.
 177    Return following unredirected edge in the list of callers
 178    of EDGE->CALLEE  */
 179
 180 static struct cgraph_edge *
 181 cgraph_mark_inline (struct cgraph_edge *edge)
 182 {
 183   struct cgraph_node *to = edge->caller;
 184   struct cgraph_node *what = edge->callee;
 185   struct cgraph_edge *e, *next;
 186   int times = 0;
 187
 188   /* Look for all calls, mark them inline and clone recursively
 189      all inlined functions.  */
 190   for (e = what->callers; e; e = next)
 191     {
 192       next = e->next_caller;
 193       if (e->caller == to && e->inline_failed)
 194         {
 195           cgraph_mark_inline_edge (e);
 196           if (e == edge)
 197             edge = next;
 198           times++;
 199         }
 200     }
 201   gcc_assert (times);
 202   return edge;
 203 }
 204
 205 /* Estimate the growth caused by inlining NODE into all callees.  */
 206
 207 static int
 208 cgraph_estimate_growth (struct cgraph_node *node)
 209 {
 210   int growth = 0;
 211   struct cgraph_edge *e;
 212
 213   for (e = node->callers; e; e = e->next_caller)
 214     if (e->inline_failed)
 215       growth += (cgraph_estimate_size_after_inlining (1, e->caller, node)
 216                  - e->caller->global.insns);
 217
 218   /* ??? Wrong for self recursive functions or cases where we decide to not
 219      inline for different reasons, but it is not big deal as in that case
 220      we will keep the body around, but we will also avoid some inlining.  */
 221   if (!node->needed && !DECL_EXTERNAL (node->decl))
 222     growth -= node->global.insns;
 223
 224   return growth;
 225 }
 226
 227 /* Return false when inlining WHAT into TO is not good idea
 228    as it would cause too large growth of function bodies.  */
 229
 230 static bool
 231 cgraph_check_inline_limits (struct cgraph_node *to, struct cgraph_node *what,
 232                             const char **reason)
 233 {
 234   int times = 0;
 235   struct cgraph_edge *e;
 236   int newsize;
 237   int limit;
 238
 239   if (to->global.inlined_to)
 240     to = to->global.inlined_to;
 241
 242   for (e = to->callees; e; e = e->next_callee)
 243     if (e->callee == what)
 244       times++;
 245
 246   /* When inlining large function body called once into small function,
 247      take the inlined function as base for limiting the growth.  */
 248   if (to->local.self_insns > what->local.self_insns)
 249     limit = to->local.self_insns;
 250   else
 251     limit = what->local.self_insns;
 252
 253   limit += limit * PARAM_VALUE (PARAM_LARGE_FUNCTION_GROWTH) / 100;
 254
 255   newsize = cgraph_estimate_size_after_inlining (times, to, what);
 256   if (newsize > PARAM_VALUE (PARAM_LARGE_FUNCTION_INSNS)
 257       && newsize > limit)
 258     {
 259       if (reason)
 260         *reason = N_("--param large-function-growth limit reached");
 261       return false;
 262     }
 263   return true;
 264 }
 265
 266 /* Return true when function N is small enough to be inlined.  */
 267
 268 bool
 269 cgraph_default_inline_p (struct cgraph_node *n)
 270 {
 271   if (!DECL_INLINE (n->decl) || !DECL_SAVED_TREE (n->decl))
 272     return false;
 273   if (DECL_DECLARED_INLINE_P (n->decl))
 274     return n->global.insns < MAX_INLINE_INSNS_SINGLE;
 275   else
 276     return n->global.insns < MAX_INLINE_INSNS_AUTO;
 277 }
 278
 279 /* Return true when inlining WHAT would create recursive inlining.
 280    We call recursive inlining all cases where same function appears more than
 281    once in the single recursion nest path in the inline graph.  */
 282
 283 static bool
 284 cgraph_recursive_inlining_p (struct cgraph_node *to,
 285                              struct cgraph_node *what,
 286                              const char **reason)
 287 {
 288   bool recursive;
 289   if (to->global.inlined_to)
 290     recursive = what->decl == to->global.inlined_to->decl;
 291   else
 292     recursive = what->decl == to->decl;
 293   /* Marking recursive function inline has sane semantic and thus we should
 294      not warn on it.  */
 295   if (recursive && reason)
 296     *reason = (what->local.disregard_inline_limits
 297                ? N_("recursive inlining") : "");
 298   return recursive;
 299 }
 300
 301 /* Recompute heap nodes for each of callees.  */
 302 static void
 303 update_callee_keys (fibheap_t heap, struct fibnode **heap_node,
 304                     struct cgraph_node *node)
 305 {
 306   struct cgraph_edge *e;
 307
 308   for (e = node->callees; e; e = e->next_callee)
 309     if (e->inline_failed && heap_node[e->callee->uid])
 310       fibheap_replace_key (heap, heap_node[e->callee->uid],
 311                            cgraph_estimate_growth (e->callee));
 312     else if (!e->inline_failed)
 313       update_callee_keys (heap, heap_node, e->callee);
 314 }
 315
 316 /* Enqueue all recursive calls from NODE into queue linked via aux pointers
 317    in between FIRST and LAST.  WHERE is used for bookkeeping while looking
 318    int calls inlined within NODE.  */
 319 static void
 320 lookup_recursive_calls (struct cgraph_node *node, struct cgraph_node *where,
 321                         struct cgraph_edge **first, struct cgraph_edge **last)
 322 {
 323   struct cgraph_edge *e;
 324   for (e = where->callees; e; e = e->next_callee)
 325     if (e->callee == node)
 326       {
 327         if (!*first)
 328           *first = e;
 329         else
 330           (*last)->aux = e;
 331         *last = e;
 332       }
 333   for (e = where->callees; e; e = e->next_callee)
 334     if (!e->inline_failed)
 335       lookup_recursive_calls (node, e->callee, first, last);
 336 }
 337
 338 /* Decide on recursive inlining: in the case function has recursive calls,
 339    inline until body size reaches given argument.  */
 340 static void
 341 cgraph_decide_recursive_inlining (struct cgraph_node *node)
 342 {
 343   int limit = PARAM_VALUE (PARAM_MAX_INLINE_INSNS_RECURSIVE_AUTO);
 344   int max_depth = PARAM_VALUE (PARAM_MAX_INLINE_RECURSIVE_DEPTH_AUTO);
 345   struct cgraph_edge *first_call = NULL, *last_call = NULL;
 346   struct cgraph_edge *last_in_current_depth;
 347   struct cgraph_edge *e;
 348   struct cgraph_node *master_clone;
 349   int depth = 0;
 350   int n = 0;
 351
 352   if (DECL_DECLARED_INLINE_P (node->decl))
 353     {
 354       limit = PARAM_VALUE (PARAM_MAX_INLINE_INSNS_RECURSIVE);
 355       max_depth = PARAM_VALUE (PARAM_MAX_INLINE_RECURSIVE_DEPTH);
 356     }
 357
 358   /* Make sure that function is small enough to be considered for inlining.  */
 359   if (!max_depth
 360       || cgraph_estimate_size_after_inlining (1, node, node)  >= limit)
 361     return;
 362   lookup_recursive_calls (node, node, &first_call, &last_call);
 363   if (!first_call)
 364     return;
 365
 366   if (dump_file)
 367     fprintf (dump_file,
 368              "\nPerforming recursive inlining on %s\n",
 369              cgraph_node_name (node));
 370
 371   /* We need original clone to copy around.  */
 372   master_clone = cgraph_clone_node (node);
 373   master_clone->needed = true;
 374   for (e = master_clone->callees; e; e = e->next_callee)
 375     if (!e->inline_failed)
 376       cgraph_clone_inlined_nodes (e, true);
 377
 378   /* Do the inlining and update list of recursive call during process.  */
 379   last_in_current_depth = last_call;
 380   while (first_call
 381          && cgraph_estimate_size_after_inlining (1, node, master_clone) <= limit)
 382     {
 383       struct cgraph_edge *curr = first_call;
 384
 385       first_call = first_call->aux;
 386       curr->aux = NULL;
 387
 388       cgraph_redirect_edge_callee (curr, master_clone);
 389       cgraph_mark_inline_edge (curr);
 390       lookup_recursive_calls (node, curr->callee, &first_call, &last_call);
 391
 392       if (last_in_current_depth
 393           && ++depth >= max_depth)
 394         break;
 395       n++;
 396     }
 397
 398   /* Cleanup queue pointers.  */
 399   while (first_call)
 400     {
 401       struct cgraph_edge *next = first_call->aux;
 402       first_call->aux = NULL;
 403       first_call = next;
 404     }
 405   if (dump_file)
 406     fprintf (dump_file,
 407              "\n   Inlined %i times, body grown from %i to %i insns\n", n,
 408              master_clone->global.insns, node->global.insns);
 409
 410   /* Remove master clone we used for inlining.  We rely that clones inlined
 411      into master clone gets queued just before master clone so we don't
 412      need recursion.  */
 413   for (node = cgraph_nodes; node != master_clone;
 414        node = node->next)
 415     if (node->global.inlined_to == master_clone)
 416       cgraph_remove_node (node);
 417   cgraph_remove_node (master_clone);
 418 }
 419
 420 /* Set inline_failed for all callers of given function to REASON.  */
 421
 422 static void
 423 cgraph_set_inline_failed (struct cgraph_node *node, const char *reason)
 424 {
 425   struct cgraph_edge *e;
 426
 427   if (dump_file)
 428     fprintf (dump_file, "Inlining failed: %s\n", reason);
 429   for (e = node->callers; e; e = e->next_caller)
 430     if (e->inline_failed)
 431       e->inline_failed = reason;
 432 }
 433
 434 /* We use greedy algorithm for inlining of small functions:
 435    All inline candidates are put into prioritized heap based on estimated
 436    growth of the overall number of instructions and then update the estimates.
 437
 438    INLINED and INLINED_CALEES are just pointers to arrays large enough
 439    to be passed to cgraph_inlined_into and cgraph_inlined_callees.  */
 440
 441 static void
 442 cgraph_decide_inlining_of_small_functions (void)
 443 {
 444   struct cgraph_node *node;
 445   fibheap_t heap = fibheap_new ();
 446   struct fibnode **heap_node =
 447     xcalloc (cgraph_max_uid, sizeof (struct fibnode *));
 448   int max_insns = ((HOST_WIDEST_INT) initial_insns
 449                    * (100 + PARAM_VALUE (PARAM_INLINE_UNIT_GROWTH)) / 100);
 450
 451   /* Put all inline candidates into the heap.  */
 452
 453   for (node = cgraph_nodes; node; node = node->next)
 454     {
 455       if (!node->local.inlinable || !node->callers
 456           || node->local.disregard_inline_limits)
 457         continue;
 458
 459       if (!cgraph_default_inline_p (node))
 460         {
 461           cgraph_set_inline_failed (node,
 462             N_("--param max-inline-insns-single limit reached"));
 463           continue;
 464         }
 465       heap_node[node->uid] =
 466         fibheap_insert (heap, cgraph_estimate_growth (node), node);
 467     }
 468
 469   if (dump_file)
 470     fprintf (dump_file, "\nDeciding on smaller functions:\n");
 471   while (overall_insns <= max_insns && (node = fibheap_extract_min (heap)))
 472     {
 473       struct cgraph_edge *e, *next;
 474       int old_insns = overall_insns;
 475
 476       heap_node[node->uid] = NULL;
 477       if (dump_file)
 478         fprintf (dump_file,
 479                  "\nConsidering %s with %i insns\n"
 480                  " Estimated growth is %+i insns.\n",
 481                  cgraph_node_name (node), node->global.insns,
 482                  cgraph_estimate_growth (node));
 483       if (!cgraph_default_inline_p (node))
 484         {
 485           cgraph_set_inline_failed (node,
 486             N_("--param max-inline-insns-single limit reached after inlining into the callee"));
 487           continue;
 488         }
 489       for (e = node->callers; e; e = next)
 490         {
 491           next = e->next_caller;
 492           if (e->inline_failed)
 493             {
 494               struct cgraph_node *where;
 495
 496               if (cgraph_recursive_inlining_p (e->caller, e->callee,
 497                                                &e->inline_failed)
 498                   || !cgraph_check_inline_limits (e->caller, e->callee,
 499                                                   &e->inline_failed))
 500                 {
 501                   if (dump_file)
 502                     fprintf (dump_file, " Not inlining into %s:%s.\n",
 503                              cgraph_node_name (e->caller), e->inline_failed);
 504                   continue;
 505                 }
 506               next = cgraph_mark_inline (e);
 507               where = e->caller;
 508               if (where->global.inlined_to)
 509                 where = where->global.inlined_to;
 510
 511               if (heap_node[where->uid])
 512                 fibheap_replace_key (heap, heap_node[where->uid],
 513                                      cgraph_estimate_growth (where));
 514
 515               if (dump_file)
 516                 fprintf (dump_file,
 517                          " Inlined into %s which now has %i insns.\n",
 518                          cgraph_node_name (e->caller),
 519                          e->caller->global.insns);
 520             }
 521         }
 522
 523       cgraph_decide_recursive_inlining (node);
 524
 525       /* Similarly all functions called by the function we just inlined
 526          are now called more times; update keys.  */
 527       update_callee_keys (heap, heap_node, node);
 528
 529       if (dump_file)
 530         fprintf (dump_file,
 531                  " Inlined for a net change of %+i insns.\n",
 532                  overall_insns - old_insns);
 533     }
 534   while ((node = fibheap_extract_min (heap)) != NULL)
 535     if (!node->local.disregard_inline_limits)
 536       cgraph_set_inline_failed (node, N_("--param inline-unit-growth limit reached"));
 537   fibheap_delete (heap);
 538   free (heap_node);
 539 }
 540
 541 /* Decide on the inlining.  We do so in the topological order to avoid
 542    expenses on updating data structures.  */
 543
 544 static void
 545 cgraph_decide_inlining (void)
 546 {
 547   struct cgraph_node *node;
 548   int nnodes;
 549   struct cgraph_node **order =
 550     xcalloc (cgraph_n_nodes, sizeof (struct cgraph_node *));
 551   int old_insns = 0;
 552   int i;
 553
 554   for (node = cgraph_nodes; node; node = node->next)
 555     initial_insns += node->local.self_insns;
 556   overall_insns = initial_insns;
 557
 558   nnodes = cgraph_postorder (order);
 559
 560   if (dump_file)
 561     fprintf (dump_file,
 562              "\nDeciding on inlining.  Starting with %i insns.\n",
 563              initial_insns);
 564
 565   for (node = cgraph_nodes; node; node = node->next)
 566     node->aux = 0;
 567
 568   if (dump_file)
 569     fprintf (dump_file, "\nInlining always_inline functions:\n");
 570
 571   /* In the first pass mark all always_inline edges.  Do this with a priority
 572      so none of our later choices will make this impossible.  */
 573   for (i = nnodes - 1; i >= 0; i--)
 574     {
 575       struct cgraph_edge *e, *next;
 576
 577       node = order[i];
 578
 579       if (!node->local.disregard_inline_limits)
 580         continue;
 581       if (dump_file)
 582         fprintf (dump_file,
 583                  "\nConsidering %s %i insns (always inline)\n",
 584                  cgraph_node_name (node), node->global.insns);
 585       old_insns = overall_insns;
 586       for (e = node->callers; e; e = next)
 587         {
 588           next = e->next_caller;
 589           if (!e->inline_failed)
 590             continue;
 591           if (cgraph_recursive_inlining_p (e->caller, e->callee,
 592                                            &e->inline_failed))
 593             continue;
 594           cgraph_mark_inline_edge (e);
 595           if (dump_file)
 596             fprintf (dump_file,
 597                      " Inlined into %s which now has %i insns.\n",
 598                      cgraph_node_name (e->caller),
 599                      e->caller->global.insns);
 600         }
 601       if (dump_file)
 602         fprintf (dump_file,
 603                  " Inlined for a net change of %+i insns.\n",
 604                  overall_insns - old_insns);
 605     }
 606
 607   if (!flag_really_no_inline)
 608     {
 609       cgraph_decide_inlining_of_small_functions ();
 610
 611       if (dump_file)
 612         fprintf (dump_file, "\nDeciding on functions called once:\n");
 613
 614       /* And finally decide what functions are called once.  */
 615
 616       for (i = nnodes - 1; i >= 0; i--)
 617         {
 618           node = order[i];
 619
 620           if (node->callers && !node->callers->next_caller && !node->needed
 621               && node->local.inlinable && node->callers->inline_failed
 622               && !DECL_EXTERNAL (node->decl) && !DECL_COMDAT (node->decl))
 623             {
 624               bool ok = true;
 625               struct cgraph_node *node1;
 626
 627               /* Verify that we won't duplicate the caller.  */
 628               for (node1 = node->callers->caller;
 629                    node1->callers && !node1->callers->inline_failed
 630                    && ok; node1 = node1->callers->caller)
 631                 if (node1->callers->next_caller || node1->needed)
 632                   ok = false;
 633               if (ok)
 634                 {
 635                   if (dump_file)
 636                     fprintf (dump_file,
 637                              "\nConsidering %s %i insns.\n"
 638                              " Called once from %s %i insns.\n",
 639                              cgraph_node_name (node), node->global.insns,
 640                              cgraph_node_name (node->callers->caller),
 641                              node->callers->caller->global.insns);
 642
 643                   old_insns = overall_insns;
 644
 645                   if (cgraph_check_inline_limits (node->callers->caller, node,
 646                                                   NULL))
 647                     {
 648                       cgraph_mark_inline (node->callers);
 649                       if (dump_file)
 650                         fprintf (dump_file,
 651                                  " Inlined into %s which now has %i insns"
 652                                  " for a net change of %+i insns.\n",
 653                                  cgraph_node_name (node->callers->caller),
 654                                  node->callers->caller->global.insns,
 655                                  overall_insns - old_insns);
 656                     }
 657                   else
 658                     {
 659                       if (dump_file)
 660                         fprintf (dump_file,
 661                                  " Inline limit reached, not inlined.\n");
 662                     }
 663                 }
 664             }
 665         }
 666     }
 667
 668   /* We will never output extern functions we didn't inline.
 669      ??? Perhaps we can prevent accounting of growth of external
 670      inline functions.  */
 671   cgraph_remove_unreachable_nodes (false, dump_file);
 672
 673   if (dump_file)
 674     fprintf (dump_file,
 675              "\nInlined %i calls, eliminated %i functions, "
 676              "%i insns turned to %i insns.\n\n",
 677              ncalls_inlined, nfunctions_inlined, initial_insns,
 678              overall_insns);
 679   free (order);
 680 }
 681
 682 /* Decide on the inlining.  We do so in the topological order to avoid
 683    expenses on updating data structures.  */
 684
 685 void
 686 cgraph_decide_inlining_incrementally (struct cgraph_node *node)
 687 {
 688   struct cgraph_edge *e;
 689
 690   /* First of all look for always inline functions.  */
 691   for (e = node->callees; e; e = e->next_callee)
 692     if (e->callee->local.disregard_inline_limits
 693         && e->inline_failed
 694         && !cgraph_recursive_inlining_p (node, e->callee, &e->inline_failed)
 695         /* ??? It is possible that renaming variable removed the function body
 696            in duplicate_decls. See gcc.c-torture/compile/20011119-2.c  */
 697         && DECL_SAVED_TREE (e->callee->decl))
 698       cgraph_mark_inline (e);
 699
 700   /* Now do the automatic inlining.  */
 701   if (!flag_really_no_inline)
 702     for (e = node->callees; e; e = e->next_callee)
 703       if (e->callee->local.inlinable
 704           && e->inline_failed
 705           && !e->callee->local.disregard_inline_limits
 706           && !cgraph_recursive_inlining_p (node, e->callee, &e->inline_failed)
 707           && cgraph_check_inline_limits (node, e->callee, &e->inline_failed)
 708           && DECL_SAVED_TREE (e->callee->decl))
 709         {
 710           if (cgraph_default_inline_p (e->callee))
 711             cgraph_mark_inline (e);
 712           else
 713             e->inline_failed
 714               = N_("--param max-inline-insns-single limit reached");
 715         }
 716 }
 717
 718 /* When inlining shall be performed.  */
 719 static bool
 720 cgraph_gate_inlining (void)
 721 {
 722   return flag_inline_trees;
 723 }
 724
 725 struct tree_opt_pass pass_ipa_inline =
 726 {
 727   "inline",                             /* name */
 728   cgraph_gate_inlining,                 /* gate */
 729   cgraph_decide_inlining,               /* execute */
 730   NULL,                                 /* sub */
 731   NULL,                                 /* next */
 732   0,                                    /* static_pass_number */
 733   TV_INTEGRATION,                       /* tv_id */
 734   0,                                    /* properties_required */
 735   PROP_trees,                           /* properties_provided */
 736   0,                                    /* properties_destroyed */
 737   0,                                    /* todo_flags_start */
 738   TODO_dump_cgraph | TODO_dump_func,    /* todo_flags_finish */
 739   0                                     /* letter */
 740 };