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);
 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         /* FIXME: Once counts and frequencies are available we should drive the
 460            order by these.  For now force the order to be simple queue since
 461            we get order dependent on recursion depth for free by this.  */
 462         fibheap_insert (heap, priority++, e);
 463       }
 464   for (e = where->callees; e; e = e->next_callee)
 465     if (!e->inline_failed)
 466       lookup_recursive_calls (node, e->callee, heap);
 467 }
 468
 469 /* Find callgraph nodes closing a circle in the graph.  The
 470    resulting hashtab can be used to avoid walking the circles.
 471    Uses the cgraph nodes ->aux field which needs to be zero
 472    before and will be zero after operation.  */
 473
 474 static void
 475 cgraph_find_cycles (struct cgraph_node *node, htab_t cycles)
 476 {
 477   struct cgraph_edge *e;
 478
 479   if (node->aux)
 480     {
 481       void **slot;
 482       slot = htab_find_slot (cycles, node, INSERT);
 483       if (!*slot)
 484         {
 485           if (dump_file)
 486             fprintf (dump_file, "Cycle contains %s\n", cgraph_node_name (node));
 487           *slot = node;
 488         }
 489       return;
 490     }
 491
 492   node->aux = node;
 493   for (e = node->callees; e; e = e->next_callee)
 494     cgraph_find_cycles (e->callee, cycles);
 495   node->aux = 0;
 496 }
 497
 498 /* Leafify the cgraph node.  We have to be careful in recursing
 499    as to not run endlessly in circles of the callgraph.
 500    We do so by using a hashtab of cycle entering nodes as generated
 501    by cgraph_find_cycles.  */
 502
 503 static void
 504 cgraph_flatten_node (struct cgraph_node *node, htab_t cycles)
 505 {
 506   struct cgraph_edge *e;
 507
 508   for (e = node->callees; e; e = e->next_callee)
 509     {
 510       /* Inline call, if possible, and recurse.  Be sure we are not
 511          entering callgraph circles here.  */
 512       if (e->inline_failed
 513           && e->callee->local.inlinable
 514           && !cgraph_recursive_inlining_p (node, e->callee,
 515                                            &e->inline_failed)
 516           && !htab_find (cycles, e->callee))
 517         {
 518           if (dump_file)
 519             fprintf (dump_file, " inlining %s", cgraph_node_name (e->callee));
 520           cgraph_mark_inline_edge (e);
 521           cgraph_flatten_node (e->callee, cycles);
 522         }
 523       else if (dump_file)
 524         fprintf (dump_file, " !inlining %s", cgraph_node_name (e->callee));
 525     }
 526 }
 527
 528 /* Decide on recursive inlining: in the case function has recursive calls,
 529    inline until body size reaches given argument.  */
 530
 531 static bool
 532 cgraph_decide_recursive_inlining (struct cgraph_node *node)
 533 {
 534   int limit = PARAM_VALUE (PARAM_MAX_INLINE_INSNS_RECURSIVE_AUTO);
 535   int max_depth = PARAM_VALUE (PARAM_MAX_INLINE_RECURSIVE_DEPTH_AUTO);
 536   fibheap_t heap;
 537   struct cgraph_edge *e;
 538   struct cgraph_node *master_clone;
 539   int depth = 0;
 540   int n = 0;
 541
 542   if (DECL_DECLARED_INLINE_P (node->decl))
 543     {
 544       limit = PARAM_VALUE (PARAM_MAX_INLINE_INSNS_RECURSIVE);
 545       max_depth = PARAM_VALUE (PARAM_MAX_INLINE_RECURSIVE_DEPTH);
 546     }
 547
 548   /* Make sure that function is small enough to be considered for inlining.  */
 549   if (!max_depth
 550       || cgraph_estimate_size_after_inlining (1, node, node)  >= limit)
 551     return false;
 552   heap = fibheap_new ();
 553   lookup_recursive_calls (node, node, heap);
 554   if (fibheap_empty (heap))
 555     {
 556       fibheap_delete (heap);
 557       return false;
 558     }
 559
 560   if (dump_file)
 561     fprintf (dump_file,
 562              "  Performing recursive inlining on %s\n",
 563              cgraph_node_name (node));
 564
 565   /* We need original clone to copy around.  */
 566   master_clone = cgraph_clone_node (node, 0, 1);
 567   master_clone->needed = true;
 568   for (e = master_clone->callees; e; e = e->next_callee)
 569     if (!e->inline_failed)
 570       cgraph_clone_inlined_nodes (e, true);
 571
 572   /* Do the inlining and update list of recursive call during process.  */
 573   while (!fibheap_empty (heap)
 574          && cgraph_estimate_size_after_inlining (1, node, master_clone) <= limit)
 575     {
 576       struct cgraph_edge *curr = fibheap_extract_min (heap);
 577       struct cgraph_node *node;
 578
 579       depth = 0;
 580       for (node = curr->caller;
 581            node; node = node->global.inlined_to)
 582         if (node->decl == curr->callee->decl)
 583           depth++;
 584       if (depth > max_depth)
 585         continue;
 586
 587       if (dump_file)
 588         fprintf (dump_file,
 589                  "   Inlining call of depth %i\n", depth);
 590       cgraph_redirect_edge_callee (curr, master_clone);
 591       cgraph_mark_inline_edge (curr);
 592       lookup_recursive_calls (node, curr->callee, heap);
 593       n++;
 594     }
 595
 596   fibheap_delete (heap);
 597   if (dump_file)
 598     fprintf (dump_file,
 599              "\n   Inlined %i times, body grown from %i to %i insns\n", n,
 600              master_clone->global.insns, node->global.insns);
 601
 602   /* Remove master clone we used for inlining.  We rely that clones inlined
 603      into master clone gets queued just before master clone so we don't
 604      need recursion.  */
 605   for (node = cgraph_nodes; node != master_clone;
 606        node = node->next)
 607     if (node->global.inlined_to == master_clone)
 608       cgraph_remove_node (node);
 609   cgraph_remove_node (master_clone);
 610   return true;
 611 }
 612
 613 /* Set inline_failed for all callers of given function to REASON.  */
 614
 615 static void
 616 cgraph_set_inline_failed (struct cgraph_node *node, const char *reason)
 617 {
 618   struct cgraph_edge *e;
 619
 620   if (dump_file)
 621     fprintf (dump_file, "Inlining failed: %s\n", reason);
 622   for (e = node->callers; e; e = e->next_caller)
 623     if (e->inline_failed)
 624       e->inline_failed = reason;
 625 }
 626
 627 /* We use greedy algorithm for inlining of small functions:
 628    All inline candidates are put into prioritized heap based on estimated
 629    growth of the overall number of instructions and then update the estimates.
 630
 631    INLINED and INLINED_CALEES are just pointers to arrays large enough
 632    to be passed to cgraph_inlined_into and cgraph_inlined_callees.  */
 633
 634 static void
 635 cgraph_decide_inlining_of_small_functions (void)
 636 {
 637   struct cgraph_node *node;
 638   struct cgraph_edge *edge;
 639   const char *failed_reason;
 640   fibheap_t heap = fibheap_new ();
 641   bitmap updated_nodes = BITMAP_ALLOC (NULL);
 642
 643   if (dump_file)
 644     fprintf (dump_file, "\nDeciding on smaller functions:\n");
 645
 646   /* Put all inline candidates into the heap.  */
 647
 648   for (node = cgraph_nodes; node; node = node->next)
 649     {
 650       if (!node->local.inlinable || !node->callers
 651           || node->local.disregard_inline_limits)
 652         continue;
 653       if (dump_file)
 654         fprintf (dump_file, "Considering inline candidate %s.\n", cgraph_node_name (node));
 655
 656       node->global.estimated_growth = INT_MIN;
 657       if (!cgraph_default_inline_p (node, &failed_reason))
 658         {
 659           cgraph_set_inline_failed (node, failed_reason);
 660           continue;
 661         }
 662
 663       for (edge = node->callers; edge; edge = edge->next_caller)
 664         if (edge->inline_failed)
 665           {
 666             gcc_assert (!edge->aux);
 667             edge->aux = fibheap_insert (heap, cgraph_edge_badness (edge), edge);
 668           }
 669     }
 670   while (overall_insns <= max_insns && (edge = fibheap_extract_min (heap)))
 671     {
 672       int old_insns = overall_insns;
 673       struct cgraph_node *where;
 674       int growth =
 675         cgraph_estimate_size_after_inlining (1, edge->caller, edge->callee);
 676
 677       growth -= edge->caller->global.insns;
 678
 679       if (dump_file)
 680         {
 681           fprintf (dump_file,
 682                    "\nConsidering %s with %i insns to be inlined into %s\n"
 683                    " Estimated growth after inlined into all callees is %+i insns.\n"
 684                    " Estimated badness is %i.\n",
 685                    cgraph_node_name (edge->callee),
 686                    edge->callee->global.insns,
 687                    cgraph_node_name (edge->caller),
 688                    cgraph_estimate_growth (edge->callee),
 689                    cgraph_edge_badness (edge));
 690           if (edge->count)
 691             fprintf (dump_file," Called "HOST_WIDEST_INT_PRINT_DEC"x\n", edge->count);
 692         }
 693       gcc_assert (edge->aux);
 694       edge->aux = NULL;
 695       if (!edge->inline_failed)
 696         continue;
 697
 698       /* When not having profile info ready we don't weight by any way the
 699          position of call in procedure itself.  This means if call of
 700          function A from function B seems profitable to inline, the recursive
 701          call of function A in inline copy of A in B will look profitable too
 702          and we end up inlining until reaching maximal function growth.  This
 703          is not good idea so prohibit the recursive inlining.
 704
 705          ??? When the frequencies are taken into account we might not need this
 706          restriction.   */
 707       if (!max_count)
 708         {
 709           where = edge->caller;
 710           while (where->global.inlined_to)
 711             {
 712               if (where->decl == edge->callee->decl)
 713                 break;
 714               where = where->callers->caller;
 715             }
 716           if (where->global.inlined_to)
 717             {
 718               edge->inline_failed
 719                 = (edge->callee->local.disregard_inline_limits ? N_("recursive inlining") : "");
 720               if (dump_file)
 721                 fprintf (dump_file, " inline_failed:Recursive inlining performed only for function itself.\n");
 722               continue;
 723             }
 724         }
 725
 726       if (!cgraph_maybe_hot_edge_p (edge) && growth > 0)
 727         {
 728           if (!cgraph_recursive_inlining_p (edge->caller, edge->callee,
 729                                             &edge->inline_failed))
 730             {
 731               edge->inline_failed =
 732                 N_("call is unlikely");
 733               if (dump_file)
 734                 fprintf (dump_file, " inline_failed:%s.\n", edge->inline_failed);
 735             }
 736           continue;
 737         }
 738       if (!cgraph_default_inline_p (edge->callee, &edge->inline_failed))
 739         {
 740           if (!cgraph_recursive_inlining_p (edge->caller, edge->callee,
 741                                             &edge->inline_failed))
 742             {
 743               if (dump_file)
 744                 fprintf (dump_file, " inline_failed:%s.\n", edge->inline_failed);
 745             }
 746           continue;
 747         }
 748       if (cgraph_recursive_inlining_p (edge->caller, edge->callee,
 749                                        &edge->inline_failed))
 750         {
 751           where = edge->caller;
 752           if (where->global.inlined_to)
 753             where = where->global.inlined_to;
 754           if (!cgraph_decide_recursive_inlining (where))
 755             continue;
 756           update_callee_keys (heap, where, updated_nodes);
 757         }
 758       else
 759         {
 760           struct cgraph_node *callee;
 761           if (!cgraph_check_inline_limits (edge->caller, edge->callee,
 762                                            &edge->inline_failed))
 763             {
 764               if (dump_file)
 765                 fprintf (dump_file, " Not inlining into %s:%s.\n",
 766                          cgraph_node_name (edge->caller), edge->inline_failed);
 767               continue;
 768             }
 769           callee = edge->callee;
 770           cgraph_mark_inline_edge (edge);
 771           update_callee_keys (heap, callee, updated_nodes);
 772         }
 773       where = edge->caller;
 774       if (where->global.inlined_to)
 775         where = where->global.inlined_to;
 776
 777       /* Our profitability metric can depend on local properties
 778          such as number of inlinable calls and size of the function body.
 779          After inlining these properties might change for the function we
 780          inlined into (since it's body size changed) and for the functions
 781          called by function we inlined (since number of it inlinable callers
 782          might change).  */
 783       update_caller_keys (heap, where, updated_nodes);
 784       bitmap_clear (updated_nodes);
 785
 786       if (dump_file)
 787         fprintf (dump_file,
 788                  " Inlined into %s which now has %i insns.\n",
 789                  cgraph_node_name (edge->caller),
 790                  edge->caller->global.insns);
 791       if (dump_file)
 792         fprintf (dump_file,
 793                  " Inlined for a net change of %+i insns.\n",
 794                  overall_insns - old_insns);
 795     }
 796   while ((edge = fibheap_extract_min (heap)) != NULL)
 797     {
 798       gcc_assert (edge->aux);
 799       edge->aux = NULL;
 800       if (!edge->callee->local.disregard_inline_limits && edge->inline_failed
 801           && !cgraph_recursive_inlining_p (edge->caller, edge->callee,
 802                                            &edge->inline_failed))
 803         edge->inline_failed = N_("--param inline-unit-growth limit reached");
 804     }
 805   fibheap_delete (heap);
 806   BITMAP_FREE (updated_nodes);
 807 }
 808
 809 /* Decide on the inlining.  We do so in the topological order to avoid
 810    expenses on updating data structures.  */
 811
 812 static void
 813 cgraph_decide_inlining (void)
 814 {
 815   struct cgraph_node *node;
 816   int nnodes;
 817   struct cgraph_node **order =
 818     xcalloc (cgraph_n_nodes, sizeof (struct cgraph_node *));
 819   int old_insns = 0;
 820   int i;
 821
 822   timevar_push (TV_INLINE_HEURISTICS);
 823   max_count = 0;
 824   for (node = cgraph_nodes; node; node = node->next)
 825     {
 826       struct cgraph_edge *e;
 827       initial_insns += node->local.self_insns;
 828       for (e = node->callees; e; e = e->next_callee)
 829         if (max_count < e->count)
 830           max_count = e->count;
 831     }
 832   overall_insns = initial_insns;
 833   gcc_assert (!max_count || (profile_info && flag_branch_probabilities));
 834
 835   max_insns = ((HOST_WIDEST_INT) overall_insns
 836                * (100 + PARAM_VALUE (PARAM_INLINE_UNIT_GROWTH)) / 100);
 837
 838   nnodes = cgraph_postorder (order);
 839
 840   if (dump_file)
 841     fprintf (dump_file,
 842              "\nDeciding on inlining.  Starting with %i insns.\n",
 843              initial_insns);
 844
 845   for (node = cgraph_nodes; node; node = node->next)
 846     node->aux = 0;
 847
 848   if (dump_file)
 849     fprintf (dump_file, "\nInlining always_inline functions:\n");
 850
 851   /* In the first pass mark all always_inline edges.  Do this with a priority
 852      so none of our later choices will make this impossible.  */
 853   for (i = nnodes - 1; i >= 0; i--)
 854     {
 855       struct cgraph_edge *e, *next;
 856
 857       node = order[i];
 858
 859       /* Handle nodes to be flattened, but don't update overall unit size.  */
 860       if (lookup_attribute ("flatten", DECL_ATTRIBUTES (node->decl)) != NULL)
 861         {
 862           int old_overall_insns = overall_insns;
 863           htab_t cycles;
 864           if (dump_file)
 865             fprintf (dump_file,
 866                      "Leafifying %s\n", cgraph_node_name (node));
 867           cycles = htab_create (7, htab_hash_pointer, htab_eq_pointer, NULL);
 868           cgraph_find_cycles (node, cycles);
 869           cgraph_flatten_node (node, cycles);
 870           htab_delete (cycles);
 871           overall_insns = old_overall_insns;
 872           /* We don't need to consider always_inline functions inside the flattened
 873              function anymore.  */
 874           continue;
 875         }
 876
 877       if (!node->local.disregard_inline_limits)
 878         continue;
 879       if (dump_file)
 880         fprintf (dump_file,
 881                  "\nConsidering %s %i insns (always inline)\n",
 882                  cgraph_node_name (node), node->global.insns);
 883       old_insns = overall_insns;
 884       for (e = node->callers; e; e = next)
 885         {
 886           next = e->next_caller;
 887           if (!e->inline_failed)
 888             continue;
 889           if (cgraph_recursive_inlining_p (e->caller, e->callee,
 890                                            &e->inline_failed))
 891             continue;
 892           cgraph_mark_inline_edge (e);
 893           if (dump_file)
 894             fprintf (dump_file,
 895                      " Inlined into %s which now has %i insns.\n",
 896                      cgraph_node_name (e->caller),
 897                      e->caller->global.insns);
 898         }
 899       if (dump_file)
 900         fprintf (dump_file,
 901                  " Inlined for a net change of %+i insns.\n",
 902                  overall_insns - old_insns);
 903     }
 904
 905   if (!flag_really_no_inline)
 906     {
 907       cgraph_decide_inlining_of_small_functions ();
 908
 909       if (dump_file)
 910         fprintf (dump_file, "\nDeciding on functions called once:\n");
 911
 912       /* And finally decide what functions are called once.  */
 913
 914       for (i = nnodes - 1; i >= 0; i--)
 915         {
 916           node = order[i];
 917
 918           if (node->callers && !node->callers->next_caller && !node->needed
 919               && node->local.inlinable && node->callers->inline_failed
 920               && !DECL_EXTERNAL (node->decl) && !DECL_COMDAT (node->decl))
 921             {
 922               bool ok = true;
 923               struct cgraph_node *node1;
 924
 925               /* Verify that we won't duplicate the caller.  */
 926               for (node1 = node->callers->caller;
 927                    node1->callers && !node1->callers->inline_failed
 928                    && ok; node1 = node1->callers->caller)
 929                 if (node1->callers->next_caller || node1->needed)
 930                   ok = false;
 931               if (ok)
 932                 {
 933                   if (dump_file)
 934                     fprintf (dump_file,
 935                              "\nConsidering %s %i insns.\n"
 936                              " Called once from %s %i insns.\n",
 937                              cgraph_node_name (node), node->global.insns,
 938                              cgraph_node_name (node->callers->caller),
 939                              node->callers->caller->global.insns);
 940
 941                   old_insns = overall_insns;
 942
 943                   if (cgraph_check_inline_limits (node->callers->caller, node,
 944                                                   NULL))
 945                     {
 946                       cgraph_mark_inline (node->callers);
 947                       if (dump_file)
 948                         fprintf (dump_file,
 949                                  " Inlined into %s which now has %i insns"
 950                                  " for a net change of %+i insns.\n",
 951                                  cgraph_node_name (node->callers->caller),
 952                                  node->callers->caller->global.insns,
 953                                  overall_insns - old_insns);
 954                     }
 955                   else
 956                     {
 957                       if (dump_file)
 958                         fprintf (dump_file,
 959                                  " Inline limit reached, not inlined.\n");
 960                     }
 961                 }
 962             }
 963         }
 964     }
 965
 966   if (dump_file)
 967     fprintf (dump_file,
 968              "\nInlined %i calls, eliminated %i functions, "
 969              "%i insns turned to %i insns.\n\n",
 970              ncalls_inlined, nfunctions_inlined, initial_insns,
 971              overall_insns);
 972   free (order);
 973   timevar_pop (TV_INLINE_HEURISTICS);
 974 }
 975
 976 /* Decide on the inlining.  We do so in the topological order to avoid
 977    expenses on updating data structures.  */
 978
 979 bool
 980 cgraph_decide_inlining_incrementally (struct cgraph_node *node, bool early)
 981 {
 982   struct cgraph_edge *e;
 983   bool inlined = false;
 984   const char *failed_reason;
 985
 986   /* First of all look for always inline functions.  */
 987   for (e = node->callees; e; e = e->next_callee)
 988     if (e->callee->local.disregard_inline_limits
 989         && e->inline_failed
 990         && !cgraph_recursive_inlining_p (node, e->callee, &e->inline_failed)
 991         /* ??? It is possible that renaming variable removed the function body
 992            in duplicate_decls. See gcc.c-torture/compile/20011119-2.c  */
 993         && DECL_SAVED_TREE (e->callee->decl))
 994       {
 995         if (dump_file && early)
 996           fprintf (dump_file, "  Early inlining %s into %s\n",
 997                    cgraph_node_name (e->callee), cgraph_node_name (node));
 998         cgraph_mark_inline (e);
 999         inlined = true;
1000       }
1001
1002   /* Now do the automatic inlining.  */
1003   if (!flag_really_no_inline)
1004     for (e = node->callees; e; e = e->next_callee)
1005       if (e->callee->local.inlinable
1006           && e->inline_failed
1007           && !e->callee->local.disregard_inline_limits
1008           && !cgraph_recursive_inlining_p (node, e->callee, &e->inline_failed)
1009           && (!early
1010               || (cgraph_estimate_size_after_inlining (1, e->caller, node)
1011                   <= e->caller->global.insns))
1012           && cgraph_check_inline_limits (node, e->callee, &e->inline_failed)
1013           && DECL_SAVED_TREE (e->callee->decl))
1014         {
1015           if (cgraph_default_inline_p (e->callee, &failed_reason))
1016             {
1017               if (dump_file && early)
1018                 fprintf (dump_file, "  Early inlining %s into %s\n",
1019                          cgraph_node_name (e->callee), cgraph_node_name (node));
1020               cgraph_mark_inline (e);
1021               inlined = true;
1022             }
1023           else if (!early)
1024             e->inline_failed = failed_reason;
1025         }
1026   if (early && inlined)
1027     {
1028       push_cfun (DECL_STRUCT_FUNCTION (node->decl));
1029       tree_register_cfg_hooks ();
1030       current_function_decl = node->decl;
1031       optimize_inline_calls (current_function_decl);
1032       node->local.self_insns = node->global.insns;
1033       current_function_decl = NULL;
1034       pop_cfun ();
1035       ggc_collect ();
1036     }
1037   return inlined;
1038 }
1039
1040 /* When inlining shall be performed.  */
1041 static bool
1042 cgraph_gate_inlining (void)
1043 {
1044   return flag_inline_trees;
1045 }
1046
1047 struct tree_opt_pass pass_ipa_inline =
1048 {
1049   "inline",                             /* name */
1050   cgraph_gate_inlining,                 /* gate */
1051   cgraph_decide_inlining,               /* execute */
1052   NULL,                                 /* sub */
1053   NULL,                                 /* next */
1054   0,                                    /* static_pass_number */
1055   TV_INTEGRATION,                       /* tv_id */
1056   0,                                    /* properties_required */
1057   PROP_cfg,                             /* properties_provided */
1058   0,                                    /* properties_destroyed */
1059   0,                                    /* todo_flags_start */
1060   TODO_dump_cgraph | TODO_dump_func,    /* todo_flags_finish */
1061   0                                     /* letter */
1062 };
1063
1064 /* Do inlining of small functions.  Doing so early helps profiling and other
1065    passes to be somewhat more effective and avoids some code duplication in
1066    later real inlining pass for testcases with very many function calls.  */
1067 static void
1068 cgraph_early_inlining (void)
1069 {
1070   struct cgraph_node *node;
1071   int nnodes;
1072   struct cgraph_node **order =
1073     xcalloc (cgraph_n_nodes, sizeof (struct cgraph_node *));
1074   int i;
1075
1076   if (sorrycount || errorcount)
1077     return;
1078 #ifdef ENABLE_CHECKING
1079   for (node = cgraph_nodes; node; node = node->next)
1080     gcc_assert (!node->aux);
1081 #endif
1082
1083   nnodes = cgraph_postorder (order);
1084   for (i = nnodes - 1; i >= 0; i--)
1085     {
1086       node = order[i];
1087       if (node->analyzed && node->local.inlinable
1088           && (node->needed || node->reachable)
1089           && node->callers)
1090         cgraph_decide_inlining_incrementally (node, true);
1091     }
1092   cgraph_remove_unreachable_nodes (true, dump_file);
1093 #ifdef ENABLE_CHECKING
1094   for (node = cgraph_nodes; node; node = node->next)
1095     gcc_assert (!node->global.inlined_to);
1096 #endif
1097   free (order);
1098 }
1099
1100 /* When inlining shall be performed.  */
1101 static bool
1102 cgraph_gate_early_inlining (void)
1103 {
1104   return flag_inline_trees && flag_early_inlining;
1105 }
1106
1107 struct tree_opt_pass pass_early_ipa_inline =
1108 {
1109   "einline",                            /* name */
1110   cgraph_gate_early_inlining,           /* gate */
1111   cgraph_early_inlining,                /* execute */
1112   NULL,                                 /* sub */
1113   NULL,                                 /* next */
1114   0,                                    /* static_pass_number */
1115   TV_INTEGRATION,                       /* tv_id */
1116   0,                                    /* properties_required */
1117   PROP_cfg,                             /* properties_provided */
1118   0,                                    /* properties_destroyed */
1119   0,                                    /* todo_flags_start */
1120   TODO_dump_cgraph | TODO_dump_func,    /* todo_flags_finish */
1121   0                                     /* letter */
1122 };