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 "hashtab.h"
  82 #include "coverage.h"
  83 #include "ggc.h"
  84
  85 /* Statistics we collect about inlining algorithm.  */
  86 static int ncalls_inlined;
  87 static int nfunctions_inlined;
  88 static int initial_insns;
  89 static int overall_insns;
  90 static int max_insns;
  91 static gcov_type max_count;
  92
  93 /* Estimate size of the function after inlining WHAT into TO.  */
  94
  95 static int
  96 cgraph_estimate_size_after_inlining (int times, struct cgraph_node *to,
  97                                      struct cgraph_node *what)
  98 {
  99   int size;
 100   tree fndecl = what->decl, arg;
 101   int call_insns = PARAM_VALUE (PARAM_INLINE_CALL_COST);
 102
 103   for (arg = DECL_ARGUMENTS (fndecl); arg; arg = TREE_CHAIN (arg))
 104     call_insns += estimate_move_cost (TREE_TYPE (arg));
 105   size = (what->global.insns - call_insns) * times + to->global.insns;
 106   gcc_assert (size >= 0);
 107   return size;
 108 }
 109
 110 /* E is expected to be an edge being inlined.  Clone destination node of
 111    the edge and redirect it to the new clone.
 112    DUPLICATE is used for bookkeeping on whether we are actually creating new
 113    clones or re-using node originally representing out-of-line function call.
 114    */
 115 void
 116 cgraph_clone_inlined_nodes (struct cgraph_edge *e, bool duplicate)
 117 {
 118   struct cgraph_node *n;
 119
 120   /* We may eliminate the need for out-of-line copy to be output.  In that
 121      case just go ahead and re-use it.  */
 122   if (!e->callee->callers->next_caller
 123       && (!e->callee->needed || DECL_EXTERNAL (e->callee->decl))
 124       && duplicate
 125       && flag_unit_at_a_time)
 126     {
 127       gcc_assert (!e->callee->global.inlined_to);
 128       if (!DECL_EXTERNAL (e->callee->decl))
 129         overall_insns -= e->callee->global.insns, nfunctions_inlined++;
 130       duplicate = 0;
 131     }
 132    else if (duplicate)
 133     {
 134       n = cgraph_clone_node (e->callee, e->count, e->loop_nest, true);
 135       cgraph_redirect_edge_callee (e, n);
 136     }
 137
 138   if (e->caller->global.inlined_to)
 139     e->callee->global.inlined_to = e->caller->global.inlined_to;
 140   else
 141     e->callee->global.inlined_to = e->caller;
 142
 143   /* Recursively clone all bodies.  */
 144   for (e = e->callee->callees; e; e = e->next_callee)
 145     if (!e->inline_failed)
 146       cgraph_clone_inlined_nodes (e, duplicate);
 147 }
 148
 149 /* Mark edge E as inlined and update callgraph accordingly.  */
 150
 151 void
 152 cgraph_mark_inline_edge (struct cgraph_edge *e)
 153 {
 154   int old_insns = 0, new_insns = 0;
 155   struct cgraph_node *to = NULL, *what;
 156
 157   gcc_assert (e->inline_failed);
 158   e->inline_failed = NULL;
 159
 160   if (!e->callee->global.inlined && flag_unit_at_a_time)
 161     DECL_POSSIBLY_INLINED (e->callee->decl) = true;
 162   e->callee->global.inlined = true;
 163
 164   cgraph_clone_inlined_nodes (e, true);
 165
 166   what = e->callee;
 167
 168   /* Now update size of caller and all functions caller is inlined into.  */
 169   for (;e && !e->inline_failed; e = e->caller->callers)
 170     {
 171       old_insns = e->caller->global.insns;
 172       new_insns = cgraph_estimate_size_after_inlining (1, e->caller,
 173                                                        what);
 174       gcc_assert (new_insns >= 0);
 175       to = e->caller;
 176       to->global.insns = new_insns;
 177     }
 178   gcc_assert (what->global.inlined_to == to);
 179   if (new_insns > old_insns)
 180     overall_insns += new_insns - old_insns;
 181   ncalls_inlined++;
 182 }
 183
 184 /* Mark all calls of EDGE->CALLEE inlined into EDGE->CALLER.
 185    Return following unredirected edge in the list of callers
 186    of EDGE->CALLEE  */
 187
 188 static struct cgraph_edge *
 189 cgraph_mark_inline (struct cgraph_edge *edge)
 190 {
 191   struct cgraph_node *to = edge->caller;
 192   struct cgraph_node *what = edge->callee;
 193   struct cgraph_edge *e, *next;
 194   int times = 0;
 195
 196   /* Look for all calls, mark them inline and clone recursively
 197      all inlined functions.  */
 198   for (e = what->callers; e; e = next)
 199     {
 200       next = e->next_caller;
 201       if (e->caller == to && e->inline_failed)
 202         {
 203           cgraph_mark_inline_edge (e);
 204           if (e == edge)
 205             edge = next;
 206           times++;
 207         }
 208     }
 209   gcc_assert (times);
 210   return edge;
 211 }
 212
 213 /* Estimate the growth caused by inlining NODE into all callees.  */
 214
 215 static int
 216 cgraph_estimate_growth (struct cgraph_node *node)
 217 {
 218   int growth = 0;
 219   struct cgraph_edge *e;
 220   if (node->global.estimated_growth != INT_MIN)
 221     return node->global.estimated_growth;
 222
 223   for (e = node->callers; e; e = e->next_caller)
 224     if (e->inline_failed)
 225       growth += (cgraph_estimate_size_after_inlining (1, e->caller, node)
 226                  - e->caller->global.insns);
 227
 228   /* ??? Wrong for self recursive functions or cases where we decide to not
 229      inline for different reasons, but it is not big deal as in that case
 230      we will keep the body around, but we will also avoid some inlining.  */
 231   if (!node->needed && !DECL_EXTERNAL (node->decl))
 232     growth -= node->global.insns;
 233
 234   node->global.estimated_growth = growth;
 235   return growth;
 236 }
 237
 238 /* Return false when inlining WHAT into TO is not good idea
 239    as it would cause too large growth of function bodies.  */
 240
 241 static bool
 242 cgraph_check_inline_limits (struct cgraph_node *to, struct cgraph_node *what,
 243                             const char **reason)
 244 {
 245   int times = 0;
 246   struct cgraph_edge *e;
 247   int newsize;
 248   int limit;
 249
 250   if (to->global.inlined_to)
 251     to = to->global.inlined_to;
 252
 253   for (e = to->callees; e; e = e->next_callee)
 254     if (e->callee == what)
 255       times++;
 256
 257   /* When inlining large function body called once into small function,
 258      take the inlined function as base for limiting the growth.  */
 259   if (to->local.self_insns > what->local.self_insns)
 260     limit = to->local.self_insns;
 261   else
 262     limit = what->local.self_insns;
 263
 264   limit += limit * PARAM_VALUE (PARAM_LARGE_FUNCTION_GROWTH) / 100;
 265
 266   newsize = cgraph_estimate_size_after_inlining (times, to, what);
 267   if (newsize > PARAM_VALUE (PARAM_LARGE_FUNCTION_INSNS)
 268       && newsize > limit)
 269     {
 270       if (reason)
 271         *reason = N_("--param large-function-growth limit reached");
 272       return false;
 273     }
 274   return true;
 275 }
 276
 277 /* Return true when function N is small enough to be inlined.  */
 278
 279 bool
 280 cgraph_default_inline_p (struct cgraph_node *n, const char **reason)
 281 {
 282   if (!DECL_INLINE (n->decl))
 283     {
 284       if (reason)
 285         *reason = N_("function not inlinable");
 286       return false;
 287     }
 288
 289   if (!DECL_SAVED_TREE (n->decl))
 290     {
 291       if (reason)
 292         *reason = N_("function body not available");
 293       return false;
 294     }
 295
 296   if (DECL_DECLARED_INLINE_P (n->decl))
 297     {
 298       if (n->global.insns >= MAX_INLINE_INSNS_SINGLE)
 299         {
 300           if (reason)
 301             *reason = N_("--param max-inline-insns-single limit reached");
 302           return false;
 303         }
 304     }
 305   else
 306     {
 307       if (n->global.insns >= MAX_INLINE_INSNS_AUTO)
 308         {
 309           if (reason)
 310             *reason = N_("--param max-inline-insns-auto limit reached");
 311           return false;
 312         }
 313     }
 314
 315   return true;
 316 }
 317
 318 /* Return true when inlining WHAT would create recursive inlining.
 319    We call recursive inlining all cases where same function appears more than
 320    once in the single recursion nest path in the inline graph.  */
 321
 322 static bool
 323 cgraph_recursive_inlining_p (struct cgraph_node *to,
 324                              struct cgraph_node *what,
 325                              const char **reason)
 326 {
 327   bool recursive;
 328   if (to->global.inlined_to)
 329     recursive = what->decl == to->global.inlined_to->decl;
 330   else
 331     recursive = what->decl == to->decl;
 332   /* Marking recursive function inline has sane semantic and thus we should
 333      not warn on it.  */
 334   if (recursive && reason)
 335     *reason = (what->local.disregard_inline_limits
 336                ? N_("recursive inlining") : "");
 337   return recursive;
 338 }
 339
 340 /* Return true if the call can be hot.  */
 341 static bool
 342 cgraph_maybe_hot_edge_p (struct cgraph_edge *edge)
 343 {
 344   if (profile_info && flag_branch_probabilities
 345       && (edge->count
 346           <= profile_info->sum_max / PARAM_VALUE (HOT_BB_COUNT_FRACTION)))
 347     return false;
 348   return true;
 349 }
 350
 351 /* A cost model driving the inlining heuristics in a way so the edges with
 352    smallest badness are inlined first.  After each inlining is performed
 353    the costs of all caller edges of nodes affected are recomputed so the
 354    metrics may accurately depend on values such as number of inlinable callers
 355    of the function or function body size.
 356
 357    With profiling we use number of executions of each edge to drive the cost.
 358    We also should distinguish hot and cold calls where the cold calls are
 359    inlined into only when code size is overall improved.
 360    */
 361
 362 static int
 363 cgraph_edge_badness (struct cgraph_edge *edge)
 364 {
 365   if (max_count)
 366     {
 367       int growth =
 368         cgraph_estimate_size_after_inlining (1, edge->caller, edge->callee);
 369       growth -= edge->caller->global.insns;
 370
 371       /* Always prefer inlining saving code size.  */
 372       if (growth <= 0)
 373         return INT_MIN - growth;
 374       return ((int)((double)edge->count * INT_MIN / max_count)) / growth;
 375     }
 376   else
 377   {
 378     int nest = MIN (edge->loop_nest, 8);
 379     int badness = cgraph_estimate_growth (edge->callee) * 256;
 380
 381     /* Decrease badness if call is nested.  */
 382     if (badness > 0)
 383       badness >>= nest;
 384     else
 385       badness <<= nest;
 386
 387     /* Make recursive inlining happen always after other inlining is done.  */
 388     if (cgraph_recursive_inlining_p (edge->caller, edge->callee, NULL))
 389       return badness + 1;
 390     else
 391       return badness;
 392   }
 393 }
 394
 395 /* Recompute heap nodes for each of caller edge.  */
 396
 397 static void
 398 update_caller_keys (fibheap_t heap, struct cgraph_node *node,
 399                     bitmap updated_nodes)
 400 {
 401   struct cgraph_edge *edge;
 402
 403   if (!node->local.inlinable || node->local.disregard_inline_limits
 404       || node->global.inlined_to)
 405     return;
 406   if (bitmap_bit_p (updated_nodes, node->uid))
 407     return;
 408   bitmap_set_bit (updated_nodes, node->uid);
 409   node->global.estimated_growth = INT_MIN;
 410
 411   for (edge = node->callers; edge; edge = edge->next_caller)
 412     if (edge->inline_failed)
 413       {
 414         int badness = cgraph_edge_badness (edge);
 415         if (edge->aux)
 416           {
 417             fibnode_t n = edge->aux;
 418             gcc_assert (n->data == edge);
 419             if (n->key == badness)
 420               continue;
 421
 422             /* fibheap_replace_key only increase the keys.  */
 423             if (fibheap_replace_key (heap, n, badness))
 424               continue;
 425             fibheap_delete_node (heap, edge->aux);
 426           }
 427         edge->aux = fibheap_insert (heap, badness, edge);
 428       }
 429 }
 430
 431 /* Recompute heap nodes for each of caller edges of each of callees.  */
 432
 433 static void
 434 update_callee_keys (fibheap_t heap, struct cgraph_node *node,
 435                     bitmap updated_nodes)
 436 {
 437   struct cgraph_edge *e;
 438   node->global.estimated_growth = INT_MIN;
 439
 440   for (e = node->callees; e; e = e->next_callee)
 441     if (e->inline_failed)
 442       update_caller_keys (heap, e->callee, updated_nodes);
 443     else if (!e->inline_failed)
 444       update_callee_keys (heap, e->callee, updated_nodes);
 445 }
 446
 447 /* Enqueue all recursive calls from NODE into priority queue depending on
 448    how likely we want to recursively inline the call.  */
 449
 450 static void
 451 lookup_recursive_calls (struct cgraph_node *node, struct cgraph_node *where,
 452                         fibheap_t heap)
 453 {
 454   static int priority;
 455   struct cgraph_edge *e;
 456   for (e = where->callees; e; e = e->next_callee)
 457     if (e->callee == node)
 458       {
 459         /* When profile feedback is available, prioritize by expected number
 460            of calls.  Without profile feedback we maintain simple queue
 461            to order candidates via recursive depths.  */
 462         fibheap_insert (heap,
 463                         !max_count ? priority++
 464                         : -(e->count / ((max_count + (1<<24) - 1) / (1<<24))),
 465                         e);
 466       }
 467   for (e = where->callees; e; e = e->next_callee)
 468     if (!e->inline_failed)
 469       lookup_recursive_calls (node, e->callee, heap);
 470 }
 471
 472 /* Find callgraph nodes closing a circle in the graph.  The
 473    resulting hashtab can be used to avoid walking the circles.
 474    Uses the cgraph nodes ->aux field which needs to be zero
 475    before and will be zero after operation.  */
 476
 477 static void
 478 cgraph_find_cycles (struct cgraph_node *node, htab_t cycles)
 479 {
 480   struct cgraph_edge *e;
 481
 482   if (node->aux)
 483     {
 484       void **slot;
 485       slot = htab_find_slot (cycles, node, INSERT);
 486       if (!*slot)
 487         {
 488           if (dump_file)
 489             fprintf (dump_file, "Cycle contains %s\n", cgraph_node_name (node));
 490           *slot = node;
 491         }
 492       return;
 493     }
 494
 495   node->aux = node;
 496   for (e = node->callees; e; e = e->next_callee)
 497     cgraph_find_cycles (e->callee, cycles);
 498   node->aux = 0;
 499 }
 500
 501 /* Leafify the cgraph node.  We have to be careful in recursing
 502    as to not run endlessly in circles of the callgraph.
 503    We do so by using a hashtab of cycle entering nodes as generated
 504    by cgraph_find_cycles.  */
 505
 506 static void
 507 cgraph_flatten_node (struct cgraph_node *node, htab_t cycles)
 508 {
 509   struct cgraph_edge *e;
 510
 511   for (e = node->callees; e; e = e->next_callee)
 512     {
 513       /* Inline call, if possible, and recurse.  Be sure we are not
 514          entering callgraph circles here.  */
 515       if (e->inline_failed
 516           && e->callee->local.inlinable
 517           && !cgraph_recursive_inlining_p (node, e->callee,
 518                                            &e->inline_failed)
 519           && !htab_find (cycles, e->callee))
 520         {
 521           if (dump_file)
 522             fprintf (dump_file, " inlining %s", cgraph_node_name (e->callee));
 523           cgraph_mark_inline_edge (e);
 524           cgraph_flatten_node (e->callee, cycles);
 525         }
 526       else if (dump_file)
 527         fprintf (dump_file, " !inlining %s", cgraph_node_name (e->callee));
 528     }
 529 }
 530
 531 /* Decide on recursive inlining: in the case function has recursive calls,
 532    inline until body size reaches given argument.  */
 533
 534 static bool
 535 cgraph_decide_recursive_inlining (struct cgraph_node *node)
 536 {
 537   int limit = PARAM_VALUE (PARAM_MAX_INLINE_INSNS_RECURSIVE_AUTO);
 538   int max_depth = PARAM_VALUE (PARAM_MAX_INLINE_RECURSIVE_DEPTH_AUTO);
 539   int probability = PARAM_VALUE (PARAM_MIN_INLINE_RECURSIVE_PROBABILITY);
 540   fibheap_t heap;
 541   struct cgraph_edge *e;
 542   struct cgraph_node *master_clone;
 543   int depth = 0;
 544   int n = 0;
 545
 546   if (DECL_DECLARED_INLINE_P (node->decl))
 547     {
 548       limit = PARAM_VALUE (PARAM_MAX_INLINE_INSNS_RECURSIVE);
 549       max_depth = PARAM_VALUE (PARAM_MAX_INLINE_RECURSIVE_DEPTH);
 550     }
 551
 552   /* Make sure that function is small enough to be considered for inlining.  */
 553   if (!max_depth
 554       || cgraph_estimate_size_after_inlining (1, node, node)  >= limit)
 555     return false;
 556   heap = fibheap_new ();
 557   lookup_recursive_calls (node, node, heap);
 558   if (fibheap_empty (heap))
 559     {
 560       fibheap_delete (heap);
 561       return false;
 562     }
 563
 564   if (dump_file)
 565     fprintf (dump_file,
 566              "  Performing recursive inlining on %s\n",
 567              cgraph_node_name (node));
 568
 569   /* We need original clone to copy around.  */
 570   master_clone = cgraph_clone_node (node, node->count, 1, false);
 571   master_clone->needed = true;
 572   for (e = master_clone->callees; e; e = e->next_callee)
 573     if (!e->inline_failed)
 574       cgraph_clone_inlined_nodes (e, true);
 575
 576   /* Do the inlining and update list of recursive call during process.  */
 577   while (!fibheap_empty (heap)
 578          && (cgraph_estimate_size_after_inlining (1, node, master_clone)
 579              <= limit))
 580     {
 581       struct cgraph_edge *curr = fibheap_extract_min (heap);
 582       struct cgraph_node *cnode;
 583
 584       depth = 1;
 585       for (cnode = curr->caller;
 586            cnode->global.inlined_to; cnode = cnode->callers->caller)
 587         if (node->decl == curr->callee->decl)
 588           depth++;
 589       if (depth > max_depth)
 590         {
 591           if (dump_file)
 592             fprintf (dump_file,
 593                      "   maxmal depth reached\n");
 594           continue;
 595         }
 596
 597       if (max_count)
 598         {
 599           if (!cgraph_maybe_hot_edge_p (curr))
 600             {
 601               if (dump_file)
 602                 fprintf (dump_file, "   Not inlining cold call\n");
 603               continue;
 604             }
 605           if (curr->count * 100 / node->count < probability)
 606             {
 607               if (dump_file)
 608                 fprintf (dump_file,
 609                          "   Probability of edge is too small\n");
 610               continue;
 611             }
 612         }
 613
 614       if (dump_file)
 615         {
 616           fprintf (dump_file,
 617                    "   Inlining call of depth %i", depth);
 618           if (node->count)
 619             {
 620               fprintf (dump_file, " called approx. %.2f times per call",
 621                        (double)curr->count / node->count);
 622             }
 623           fprintf (dump_file, "\n");
 624         }
 625       cgraph_redirect_edge_callee (curr, master_clone);
 626       cgraph_mark_inline_edge (curr);
 627       lookup_recursive_calls (node, curr->callee, heap);
 628       n++;
 629     }
 630   if (!fibheap_empty (heap) && dump_file)
 631     fprintf (dump_file, "    Recursive inlining growth limit met.\n");
 632
 633   fibheap_delete (heap);
 634   if (dump_file)
 635     fprintf (dump_file,
 636              "\n   Inlined %i times, body grown from %i to %i insns\n", n,
 637              master_clone->global.insns, node->global.insns);
 638
 639   /* Remove master clone we used for inlining.  We rely that clones inlined
 640      into master clone gets queued just before master clone so we don't
 641      need recursion.  */
 642   for (node = cgraph_nodes; node != master_clone;
 643        node = node->next)
 644     if (node->global.inlined_to == master_clone)
 645       cgraph_remove_node (node);
 646   cgraph_remove_node (master_clone);
 647   /* FIXME: Recursive inlining actually reduces number of calls of the
 648      function.  At this place we should probably walk the function and
 649      inline clones and compensate the counts accordingly.  This probably
 650      doesn't matter much in practice.  */
 651   return true;
 652 }
 653
 654 /* Set inline_failed for all callers of given function to REASON.  */
 655
 656 static void
 657 cgraph_set_inline_failed (struct cgraph_node *node, const char *reason)
 658 {
 659   struct cgraph_edge *e;
 660
 661   if (dump_file)
 662     fprintf (dump_file, "Inlining failed: %s\n", reason);
 663   for (e = node->callers; e; e = e->next_caller)
 664     if (e->inline_failed)
 665       e->inline_failed = reason;
 666 }
 667
 668 /* We use greedy algorithm for inlining of small functions:
 669    All inline candidates are put into prioritized heap based on estimated
 670    growth of the overall number of instructions and then update the estimates.
 671
 672    INLINED and INLINED_CALEES are just pointers to arrays large enough
 673    to be passed to cgraph_inlined_into and cgraph_inlined_callees.  */
 674
 675 static void
 676 cgraph_decide_inlining_of_small_functions (void)
 677 {
 678   struct cgraph_node *node;
 679   struct cgraph_edge *edge;
 680   const char *failed_reason;
 681   fibheap_t heap = fibheap_new ();
 682   bitmap updated_nodes = BITMAP_ALLOC (NULL);
 683
 684   if (dump_file)
 685     fprintf (dump_file, "\nDeciding on smaller functions:\n");
 686
 687   /* Put all inline candidates into the heap.  */
 688
 689   for (node = cgraph_nodes; node; node = node->next)
 690     {
 691       if (!node->local.inlinable || !node->callers
 692           || node->local.disregard_inline_limits)
 693         continue;
 694       if (dump_file)
 695         fprintf (dump_file, "Considering inline candidate %s.\n", cgraph_node_name (node));
 696
 697       node->global.estimated_growth = INT_MIN;
 698       if (!cgraph_default_inline_p (node, &failed_reason))
 699         {
 700           cgraph_set_inline_failed (node, failed_reason);
 701           continue;
 702         }
 703
 704       for (edge = node->callers; edge; edge = edge->next_caller)
 705         if (edge->inline_failed)
 706           {
 707             gcc_assert (!edge->aux);
 708             edge->aux = fibheap_insert (heap, cgraph_edge_badness (edge), edge);
 709           }
 710     }
 711   while (overall_insns <= max_insns && (edge = fibheap_extract_min (heap)))
 712     {
 713       int old_insns = overall_insns;
 714       struct cgraph_node *where;
 715       int growth =
 716         cgraph_estimate_size_after_inlining (1, edge->caller, edge->callee);
 717
 718       growth -= edge->caller->global.insns;
 719
 720       if (dump_file)
 721         {
 722           fprintf (dump_file,
 723                    "\nConsidering %s with %i insns to be inlined into %s\n"
 724                    " Estimated growth after inlined into all callees is %+i insns.\n"
 725                    " Estimated badness is %i.\n",
 726                    cgraph_node_name (edge->callee),
 727                    edge->callee->global.insns,
 728                    cgraph_node_name (edge->caller),
 729                    cgraph_estimate_growth (edge->callee),
 730                    cgraph_edge_badness (edge));
 731           if (edge->count)
 732             fprintf (dump_file," Called "HOST_WIDEST_INT_PRINT_DEC"x\n", edge->count);
 733         }
 734       gcc_assert (edge->aux);
 735       edge->aux = NULL;
 736       if (!edge->inline_failed)
 737         continue;
 738
 739       /* When not having profile info ready we don't weight by any way the
 740          position of call in procedure itself.  This means if call of
 741          function A from function B seems profitable to inline, the recursive
 742          call of function A in inline copy of A in B will look profitable too
 743          and we end up inlining until reaching maximal function growth.  This
 744          is not good idea so prohibit the recursive inlining.
 745
 746          ??? When the frequencies are taken into account we might not need this
 747          restriction.   */
 748       if (!max_count)
 749         {
 750           where = edge->caller;
 751           while (where->global.inlined_to)
 752             {
 753               if (where->decl == edge->callee->decl)
 754                 break;
 755               where = where->callers->caller;
 756             }
 757           if (where->global.inlined_to)
 758             {
 759               edge->inline_failed
 760                 = (edge->callee->local.disregard_inline_limits ? N_("recursive inlining") : "");
 761               if (dump_file)
 762                 fprintf (dump_file, " inline_failed:Recursive inlining performed only for function itself.\n");
 763               continue;
 764             }
 765         }
 766
 767       if (!cgraph_maybe_hot_edge_p (edge) && growth > 0)
 768         {
 769           if (!cgraph_recursive_inlining_p (edge->caller, edge->callee,
 770                                             &edge->inline_failed))
 771             {
 772               edge->inline_failed =
 773                 N_("call is unlikely");
 774               if (dump_file)
 775                 fprintf (dump_file, " inline_failed:%s.\n", edge->inline_failed);
 776             }
 777           continue;
 778         }
 779       if (!cgraph_default_inline_p (edge->callee, &edge->inline_failed))
 780         {
 781           if (!cgraph_recursive_inlining_p (edge->caller, edge->callee,
 782                                             &edge->inline_failed))
 783             {
 784               if (dump_file)
 785                 fprintf (dump_file, " inline_failed:%s.\n", edge->inline_failed);
 786             }
 787           continue;
 788         }
 789       if (cgraph_recursive_inlining_p (edge->caller, edge->callee,
 790                                        &edge->inline_failed))
 791         {
 792           where = edge->caller;
 793           if (where->global.inlined_to)
 794             where = where->global.inlined_to;
 795           if (!cgraph_decide_recursive_inlining (where))
 796             continue;
 797           update_callee_keys (heap, where, updated_nodes);
 798         }
 799       else
 800         {
 801           struct cgraph_node *callee;
 802           if (!cgraph_check_inline_limits (edge->caller, edge->callee,
 803                                            &edge->inline_failed))
 804             {
 805               if (dump_file)
 806                 fprintf (dump_file, " Not inlining into %s:%s.\n",
 807                          cgraph_node_name (edge->caller), edge->inline_failed);
 808               continue;
 809             }
 810           callee = edge->callee;
 811           cgraph_mark_inline_edge (edge);
 812           update_callee_keys (heap, callee, updated_nodes);
 813         }
 814       where = edge->caller;
 815       if (where->global.inlined_to)
 816         where = where->global.inlined_to;
 817
 818       /* Our profitability metric can depend on local properties
 819          such as number of inlinable calls and size of the function body.
 820          After inlining these properties might change for the function we
 821          inlined into (since it's body size changed) and for the functions
 822          called by function we inlined (since number of it inlinable callers
 823          might change).  */
 824       update_caller_keys (heap, where, updated_nodes);
 825       bitmap_clear (updated_nodes);
 826
 827       if (dump_file)
 828         fprintf (dump_file,
 829                  " Inlined into %s which now has %i insns.\n",
 830                  cgraph_node_name (edge->caller),
 831                  edge->caller->global.insns);
 832       if (dump_file)
 833         fprintf (dump_file,
 834                  " Inlined for a net change of %+i insns.\n",
 835                  overall_insns - old_insns);
 836     }
 837   while ((edge = fibheap_extract_min (heap)) != NULL)
 838     {
 839       gcc_assert (edge->aux);
 840       edge->aux = NULL;
 841       if (!edge->callee->local.disregard_inline_limits && edge->inline_failed
 842           && !cgraph_recursive_inlining_p (edge->caller, edge->callee,
 843                                            &edge->inline_failed))
 844         edge->inline_failed = N_("--param inline-unit-growth limit reached");
 845     }
 846   fibheap_delete (heap);
 847   BITMAP_FREE (updated_nodes);
 848 }
 849
 850 /* Decide on the inlining.  We do so in the topological order to avoid
 851    expenses on updating data structures.  */
 852
 853 static void
 854 cgraph_decide_inlining (void)
 855 {
 856   struct cgraph_node *node;
 857   int nnodes;
 858   struct cgraph_node **order =
 859     xcalloc (cgraph_n_nodes, sizeof (struct cgraph_node *));
 860   int old_insns = 0;
 861   int i;
 862
 863   timevar_push (TV_INLINE_HEURISTICS);
 864   max_count = 0;
 865   for (node = cgraph_nodes; node; node = node->next)
 866     {
 867       struct cgraph_edge *e;
 868       initial_insns += node->local.self_insns;
 869       for (e = node->callees; e; e = e->next_callee)
 870         if (max_count < e->count)
 871           max_count = e->count;
 872     }
 873   overall_insns = initial_insns;
 874   gcc_assert (!max_count || (profile_info && flag_branch_probabilities));
 875
 876   max_insns = ((HOST_WIDEST_INT) overall_insns
 877                * (100 + PARAM_VALUE (PARAM_INLINE_UNIT_GROWTH)) / 100);
 878
 879   nnodes = cgraph_postorder (order);
 880
 881   if (dump_file)
 882     fprintf (dump_file,
 883              "\nDeciding on inlining.  Starting with %i insns.\n",
 884              initial_insns);
 885
 886   for (node = cgraph_nodes; node; node = node->next)
 887     node->aux = 0;
 888
 889   if (dump_file)
 890     fprintf (dump_file, "\nInlining always_inline functions:\n");
 891
 892   /* In the first pass mark all always_inline edges.  Do this with a priority
 893      so none of our later choices will make this impossible.  */
 894   for (i = nnodes - 1; i >= 0; i--)
 895     {
 896       struct cgraph_edge *e, *next;
 897
 898       node = order[i];
 899
 900       /* Handle nodes to be flattened, but don't update overall unit size.  */
 901       if (lookup_attribute ("flatten", DECL_ATTRIBUTES (node->decl)) != NULL)
 902         {
 903           int old_overall_insns = overall_insns;
 904           htab_t cycles;
 905           if (dump_file)
 906             fprintf (dump_file,
 907                      "Leafifying %s\n", cgraph_node_name (node));
 908           cycles = htab_create (7, htab_hash_pointer, htab_eq_pointer, NULL);
 909           cgraph_find_cycles (node, cycles);
 910           cgraph_flatten_node (node, cycles);
 911           htab_delete (cycles);
 912           overall_insns = old_overall_insns;
 913           /* We don't need to consider always_inline functions inside the flattened
 914              function anymore.  */
 915           continue;
 916         }
 917
 918       if (!node->local.disregard_inline_limits)
 919         continue;
 920       if (dump_file)
 921         fprintf (dump_file,
 922                  "\nConsidering %s %i insns (always inline)\n",
 923                  cgraph_node_name (node), node->global.insns);
 924       old_insns = overall_insns;
 925       for (e = node->callers; e; e = next)
 926         {
 927           next = e->next_caller;
 928           if (!e->inline_failed)
 929             continue;
 930           if (cgraph_recursive_inlining_p (e->caller, e->callee,
 931                                            &e->inline_failed))
 932             continue;
 933           cgraph_mark_inline_edge (e);
 934           if (dump_file)
 935             fprintf (dump_file,
 936                      " Inlined into %s which now has %i insns.\n",
 937                      cgraph_node_name (e->caller),
 938                      e->caller->global.insns);
 939         }
 940       if (dump_file)
 941         fprintf (dump_file,
 942                  " Inlined for a net change of %+i insns.\n",
 943                  overall_insns - old_insns);
 944     }
 945
 946   if (!flag_really_no_inline)
 947     cgraph_decide_inlining_of_small_functions ();
 948
 949   if (!flag_really_no_inline
 950       && flag_inline_functions_called_once)
 951     {
 952       if (dump_file)
 953         fprintf (dump_file, "\nDeciding on functions called once:\n");
 954
 955       /* And finally decide what functions are called once.  */
 956
 957       for (i = nnodes - 1; i >= 0; i--)
 958         {
 959           node = order[i];
 960
 961           if (node->callers && !node->callers->next_caller && !node->needed
 962               && node->local.inlinable && node->callers->inline_failed
 963               && !DECL_EXTERNAL (node->decl) && !DECL_COMDAT (node->decl))
 964             {
 965               bool ok = true;
 966               struct cgraph_node *node1;
 967
 968               /* Verify that we won't duplicate the caller.  */
 969               for (node1 = node->callers->caller;
 970                    node1->callers && !node1->callers->inline_failed
 971                    && ok; node1 = node1->callers->caller)
 972                 if (node1->callers->next_caller || node1->needed)
 973                   ok = false;
 974               if (ok)
 975                 {
 976                   if (dump_file)
 977                     fprintf (dump_file,
 978                              "\nConsidering %s %i insns.\n"
 979                              " Called once from %s %i insns.\n",
 980                              cgraph_node_name (node), node->global.insns,
 981                              cgraph_node_name (node->callers->caller),
 982                              node->callers->caller->global.insns);
 983
 984                   old_insns = overall_insns;
 985
 986                   if (cgraph_check_inline_limits (node->callers->caller, node,
 987                                                   NULL))
 988                     {
 989                       cgraph_mark_inline (node->callers);
 990                       if (dump_file)
 991                         fprintf (dump_file,
 992                                  " Inlined into %s which now has %i insns"
 993                                  " for a net change of %+i insns.\n",
 994                                  cgraph_node_name (node->callers->caller),
 995                                  node->callers->caller->global.insns,
 996                                  overall_insns - old_insns);
 997                     }
 998                   else
 999                     {
1000                       if (dump_file)
1001                         fprintf (dump_file,
1002                                  " Inline limit reached, not inlined.\n");
1003                     }
1004                 }
1005             }
1006         }
1007     }
1008
1009   if (dump_file)
1010     fprintf (dump_file,
1011              "\nInlined %i calls, eliminated %i functions, "
1012              "%i insns turned to %i insns.\n\n",
1013              ncalls_inlined, nfunctions_inlined, initial_insns,
1014              overall_insns);
1015   free (order);
1016   timevar_pop (TV_INLINE_HEURISTICS);
1017 }
1018
1019 /* Decide on the inlining.  We do so in the topological order to avoid
1020    expenses on updating data structures.  */
1021
1022 bool
1023 cgraph_decide_inlining_incrementally (struct cgraph_node *node, bool early)
1024 {
1025   struct cgraph_edge *e;
1026   bool inlined = false;
1027   const char *failed_reason;
1028
1029   /* First of all look for always inline functions.  */
1030   for (e = node->callees; e; e = e->next_callee)
1031     if (e->callee->local.disregard_inline_limits
1032         && e->inline_failed
1033         && !cgraph_recursive_inlining_p (node, e->callee, &e->inline_failed)
1034         /* ??? It is possible that renaming variable removed the function body
1035            in duplicate_decls. See gcc.c-torture/compile/20011119-2.c  */
1036         && DECL_SAVED_TREE (e->callee->decl))
1037       {
1038         if (dump_file && early)
1039           fprintf (dump_file, "  Early inlining %s into %s\n",
1040                    cgraph_node_name (e->callee), cgraph_node_name (node));
1041         cgraph_mark_inline (e);
1042         inlined = true;
1043       }
1044
1045   /* Now do the automatic inlining.  */
1046   if (!flag_really_no_inline)
1047     for (e = node->callees; e; e = e->next_callee)
1048       if (e->callee->local.inlinable
1049           && e->inline_failed
1050           && !e->callee->local.disregard_inline_limits
1051           && !cgraph_recursive_inlining_p (node, e->callee, &e->inline_failed)
1052           && (!early
1053               || (cgraph_estimate_size_after_inlining (1, e->caller, node)
1054                   <= e->caller->global.insns))
1055           && cgraph_check_inline_limits (node, e->callee, &e->inline_failed)
1056           && DECL_SAVED_TREE (e->callee->decl))
1057         {
1058           if (cgraph_default_inline_p (e->callee, &failed_reason))
1059             {
1060               if (dump_file && early)
1061                 fprintf (dump_file, "  Early inlining %s into %s\n",
1062                          cgraph_node_name (e->callee), cgraph_node_name (node));
1063               cgraph_mark_inline (e);
1064               inlined = true;
1065             }
1066           else if (!early)
1067             e->inline_failed = failed_reason;
1068         }
1069   if (early && inlined)
1070     {
1071       push_cfun (DECL_STRUCT_FUNCTION (node->decl));
1072       tree_register_cfg_hooks ();
1073       current_function_decl = node->decl;
1074       optimize_inline_calls (current_function_decl);
1075       node->local.self_insns = node->global.insns;
1076       current_function_decl = NULL;
1077       pop_cfun ();
1078     }
1079   return inlined;
1080 }
1081
1082 /* When inlining shall be performed.  */
1083 static bool
1084 cgraph_gate_inlining (void)
1085 {
1086   return flag_inline_trees;
1087 }
1088
1089 struct tree_opt_pass pass_ipa_inline =
1090 {
1091   "inline",                             /* name */
1092   cgraph_gate_inlining,                 /* gate */
1093   cgraph_decide_inlining,               /* execute */
1094   NULL,                                 /* sub */
1095   NULL,                                 /* next */
1096   0,                                    /* static_pass_number */
1097   TV_INTEGRATION,                       /* tv_id */
1098   0,                                    /* properties_required */
1099   PROP_cfg,                             /* properties_provided */
1100   0,                                    /* properties_destroyed */
1101   0,                                    /* todo_flags_start */
1102   TODO_dump_cgraph | TODO_dump_func,    /* todo_flags_finish */
1103   0                                     /* letter */
1104 };
1105
1106 /* Do inlining of small functions.  Doing so early helps profiling and other
1107    passes to be somewhat more effective and avoids some code duplication in
1108    later real inlining pass for testcases with very many function calls.  */
1109 static void
1110 cgraph_early_inlining (void)
1111 {
1112   struct cgraph_node *node;
1113   int nnodes;
1114   struct cgraph_node **order =
1115     xcalloc (cgraph_n_nodes, sizeof (struct cgraph_node *));
1116   int i;
1117
1118   if (sorrycount || errorcount)
1119     return;
1120 #ifdef ENABLE_CHECKING
1121   for (node = cgraph_nodes; node; node = node->next)
1122     gcc_assert (!node->aux);
1123 #endif
1124
1125   nnodes = cgraph_postorder (order);
1126   for (i = nnodes - 1; i >= 0; i--)
1127     {
1128       node = order[i];
1129       if (node->analyzed && node->local.inlinable
1130           && (node->needed || node->reachable)
1131           && node->callers)
1132         cgraph_decide_inlining_incrementally (node, true);
1133     }
1134   cgraph_remove_unreachable_nodes (true, dump_file);
1135 #ifdef ENABLE_CHECKING
1136   for (node = cgraph_nodes; node; node = node->next)
1137     gcc_assert (!node->global.inlined_to);
1138 #endif
1139   free (order);
1140 }
1141
1142 /* When inlining shall be performed.  */
1143 static bool
1144 cgraph_gate_early_inlining (void)
1145 {
1146   return flag_inline_trees && flag_early_inlining;
1147 }
1148
1149 struct tree_opt_pass pass_early_ipa_inline =
1150 {
1151   "einline",                            /* name */
1152   cgraph_gate_early_inlining,           /* gate */
1153   cgraph_early_inlining,                /* execute */
1154   NULL,                                 /* sub */
1155   NULL,                                 /* next */
1156   0,                                    /* static_pass_number */
1157   TV_INTEGRATION,                       /* tv_id */
1158   0,                                    /* properties_required */
1159   PROP_cfg,                             /* properties_provided */
1160   0,                                    /* properties_destroyed */
1161   0,                                    /* todo_flags_start */
1162   TODO_dump_cgraph | TODO_dump_func,    /* todo_flags_finish */
1163   0                                     /* letter */
1164 };