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