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     {
 948       cgraph_decide_inlining_of_small_functions ();
 949
 950       if (dump_file)
 951         fprintf (dump_file, "\nDeciding on functions called once:\n");
 952
 953       /* And finally decide what functions are called once.  */
 954
 955       for (i = nnodes - 1; i >= 0; i--)
 956         {
 957           node = order[i];
 958
 959           if (node->callers && !node->callers->next_caller && !node->needed
 960               && node->local.inlinable && node->callers->inline_failed
 961               && !DECL_EXTERNAL (node->decl) && !DECL_COMDAT (node->decl))
 962             {
 963               bool ok = true;
 964               struct cgraph_node *node1;
 965
 966               /* Verify that we won't duplicate the caller.  */
 967               for (node1 = node->callers->caller;
 968                    node1->callers && !node1->callers->inline_failed
 969                    && ok; node1 = node1->callers->caller)
 970                 if (node1->callers->next_caller || node1->needed)
 971                   ok = false;
 972               if (ok)
 973                 {
 974                   if (dump_file)
 975                     fprintf (dump_file,
 976                              "\nConsidering %s %i insns.\n"
 977                              " Called once from %s %i insns.\n",
 978                              cgraph_node_name (node), node->global.insns,
 979                              cgraph_node_name (node->callers->caller),
 980                              node->callers->caller->global.insns);
 981
 982                   old_insns = overall_insns;
 983
 984                   if (cgraph_check_inline_limits (node->callers->caller, node,
 985                                                   NULL))
 986                     {
 987                       cgraph_mark_inline (node->callers);
 988                       if (dump_file)
 989                         fprintf (dump_file,
 990                                  " Inlined into %s which now has %i insns"
 991                                  " for a net change of %+i insns.\n",
 992                                  cgraph_node_name (node->callers->caller),
 993                                  node->callers->caller->global.insns,
 994                                  overall_insns - old_insns);
 995                     }
 996                   else
 997                     {
 998                       if (dump_file)
 999                         fprintf (dump_file,
1000                                  " Inline limit reached, not inlined.\n");
1001                     }
1002                 }
1003             }
1004         }
1005     }
1006
1007   if (dump_file)
1008     fprintf (dump_file,
1009              "\nInlined %i calls, eliminated %i functions, "
1010              "%i insns turned to %i insns.\n\n",
1011              ncalls_inlined, nfunctions_inlined, initial_insns,
1012              overall_insns);
1013   free (order);
1014   timevar_pop (TV_INLINE_HEURISTICS);
1015 }
1016
1017 /* Decide on the inlining.  We do so in the topological order to avoid
1018    expenses on updating data structures.  */
1019
1020 bool
1021 cgraph_decide_inlining_incrementally (struct cgraph_node *node, bool early)
1022 {
1023   struct cgraph_edge *e;
1024   bool inlined = false;
1025   const char *failed_reason;
1026
1027   /* First of all look for always inline functions.  */
1028   for (e = node->callees; e; e = e->next_callee)
1029     if (e->callee->local.disregard_inline_limits
1030         && e->inline_failed
1031         && !cgraph_recursive_inlining_p (node, e->callee, &e->inline_failed)
1032         /* ??? It is possible that renaming variable removed the function body
1033            in duplicate_decls. See gcc.c-torture/compile/20011119-2.c  */
1034         && DECL_SAVED_TREE (e->callee->decl))
1035       {
1036         if (dump_file && early)
1037           fprintf (dump_file, "  Early inlining %s into %s\n",
1038                    cgraph_node_name (e->callee), cgraph_node_name (node));
1039         cgraph_mark_inline (e);
1040         inlined = true;
1041       }
1042
1043   /* Now do the automatic inlining.  */
1044   if (!flag_really_no_inline)
1045     for (e = node->callees; e; e = e->next_callee)
1046       if (e->callee->local.inlinable
1047           && e->inline_failed
1048           && !e->callee->local.disregard_inline_limits
1049           && !cgraph_recursive_inlining_p (node, e->callee, &e->inline_failed)
1050           && (!early
1051               || (cgraph_estimate_size_after_inlining (1, e->caller, node)
1052                   <= e->caller->global.insns))
1053           && cgraph_check_inline_limits (node, e->callee, &e->inline_failed)
1054           && DECL_SAVED_TREE (e->callee->decl))
1055         {
1056           if (cgraph_default_inline_p (e->callee, &failed_reason))
1057             {
1058               if (dump_file && early)
1059                 fprintf (dump_file, "  Early inlining %s into %s\n",
1060                          cgraph_node_name (e->callee), cgraph_node_name (node));
1061               cgraph_mark_inline (e);
1062               inlined = true;
1063             }
1064           else if (!early)
1065             e->inline_failed = failed_reason;
1066         }
1067   if (early && inlined)
1068     {
1069       push_cfun (DECL_STRUCT_FUNCTION (node->decl));
1070       tree_register_cfg_hooks ();
1071       current_function_decl = node->decl;
1072       optimize_inline_calls (current_function_decl);
1073       node->local.self_insns = node->global.insns;
1074       current_function_decl = NULL;
1075       pop_cfun ();
1076       ggc_collect ();
1077     }
1078   return inlined;
1079 }
1080
1081 /* When inlining shall be performed.  */
1082 static bool
1083 cgraph_gate_inlining (void)
1084 {
1085   return flag_inline_trees;
1086 }
1087
1088 struct tree_opt_pass pass_ipa_inline =
1089 {
1090   "inline",                             /* name */
1091   cgraph_gate_inlining,                 /* gate */
1092   cgraph_decide_inlining,               /* execute */
1093   NULL,                                 /* sub */
1094   NULL,                                 /* next */
1095   0,                                    /* static_pass_number */
1096   TV_INTEGRATION,                       /* tv_id */
1097   0,                                    /* properties_required */
1098   PROP_cfg,                             /* properties_provided */
1099   0,                                    /* properties_destroyed */
1100   0,                                    /* todo_flags_start */
1101   TODO_dump_cgraph | TODO_dump_func,    /* todo_flags_finish */
1102   0                                     /* letter */
1103 };
1104
1105 /* Do inlining of small functions.  Doing so early helps profiling and other
1106    passes to be somewhat more effective and avoids some code duplication in
1107    later real inlining pass for testcases with very many function calls.  */
1108 static void
1109 cgraph_early_inlining (void)
1110 {
1111   struct cgraph_node *node;
1112   int nnodes;
1113   struct cgraph_node **order =
1114     xcalloc (cgraph_n_nodes, sizeof (struct cgraph_node *));
1115   int i;
1116
1117   if (sorrycount || errorcount)
1118     return;
1119 #ifdef ENABLE_CHECKING
1120   for (node = cgraph_nodes; node; node = node->next)
1121     gcc_assert (!node->aux);
1122 #endif
1123
1124   nnodes = cgraph_postorder (order);
1125   for (i = nnodes - 1; i >= 0; i--)
1126     {
1127       node = order[i];
1128       if (node->analyzed && node->local.inlinable
1129           && (node->needed || node->reachable)
1130           && node->callers)
1131         cgraph_decide_inlining_incrementally (node, true);
1132     }
1133   cgraph_remove_unreachable_nodes (true, dump_file);
1134 #ifdef ENABLE_CHECKING
1135   for (node = cgraph_nodes; node; node = node->next)
1136     gcc_assert (!node->global.inlined_to);
1137 #endif
1138   free (order);
1139 }
1140
1141 /* When inlining shall be performed.  */
1142 static bool
1143 cgraph_gate_early_inlining (void)
1144 {
1145   return flag_inline_trees && flag_early_inlining;
1146 }
1147
1148 struct tree_opt_pass pass_early_ipa_inline =
1149 {
1150   "einline",                            /* name */
1151   cgraph_gate_early_inlining,           /* gate */
1152   cgraph_early_inlining,                /* execute */
1153   NULL,                                 /* sub */
1154   NULL,                                 /* next */
1155   0,                                    /* static_pass_number */
1156   TV_INTEGRATION,                       /* tv_id */
1157   0,                                    /* properties_required */
1158   PROP_cfg,                             /* properties_provided */
1159   0,                                    /* properties_destroyed */
1160   0,                                    /* todo_flags_start */
1161   TODO_dump_cgraph | TODO_dump_func,    /* todo_flags_finish */
1162   0                                     /* letter */
1163 };