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 to be inlined into %s\n"
 726                    " Estimated growth after inlined into all callees is %+i insns.\n"
 727                    " Estimated badness is %i.\n",
 728                    cgraph_node_name (edge->callee),
 729                    edge->callee->global.insns,
 730                    cgraph_node_name (edge->caller),
 731                    cgraph_estimate_growth (edge->callee),
 732                    cgraph_edge_badness (edge));
 733           if (edge->count)
 734             fprintf (dump_file," Called "HOST_WIDEST_INT_PRINT_DEC"x\n", edge->count);
 735         }
 736       gcc_assert (edge->aux);
 737       edge->aux = NULL;
 738       if (!edge->inline_failed)
 739         continue;
 740
 741       /* When not having profile info ready we don't weight by any way the
 742          position of call in procedure itself.  This means if call of
 743          function A from function B seems profitable to inline, the recursive
 744          call of function A in inline copy of A in B will look profitable too
 745          and we end up inlining until reaching maximal function growth.  This
 746          is not good idea so prohibit the recursive inlining.
 747
 748          ??? When the frequencies are taken into account we might not need this
 749          restriction.   */
 750       if (!max_count)
 751         {
 752           where = edge->caller;
 753           while (where->global.inlined_to)
 754             {
 755               if (where->decl == edge->callee->decl)
 756                 break;
 757               where = where->callers->caller;
 758             }
 759           if (where->global.inlined_to)
 760             {
 761               edge->inline_failed
 762                 = (edge->callee->local.disregard_inline_limits ? N_("recursive inlining") : "");
 763               if (dump_file)
 764                 fprintf (dump_file, " inline_failed:Recursive inlining performed only for function itself.\n");
 765               continue;
 766             }
 767         }
 768
 769       if (!cgraph_maybe_hot_edge_p (edge) && growth > 0)
 770         {
 771           if (!cgraph_recursive_inlining_p (edge->caller, edge->callee,
 772                                             &edge->inline_failed))
 773             {
 774               edge->inline_failed =
 775                 N_("call is unlikely");
 776               if (dump_file)
 777                 fprintf (dump_file, " inline_failed:%s.\n", edge->inline_failed);
 778             }
 779           continue;
 780         }
 781       if (!cgraph_default_inline_p (edge->callee, &edge->inline_failed))
 782         {
 783           if (!cgraph_recursive_inlining_p (edge->caller, edge->callee,
 784                                             &edge->inline_failed))
 785             {
 786               if (dump_file)
 787                 fprintf (dump_file, " inline_failed:%s.\n", edge->inline_failed);
 788             }
 789           continue;
 790         }
 791       if (cgraph_recursive_inlining_p (edge->caller, edge->callee,
 792                                        &edge->inline_failed))
 793         {
 794           where = edge->caller;
 795           if (where->global.inlined_to)
 796             where = where->global.inlined_to;
 797           if (!cgraph_decide_recursive_inlining (where))
 798             continue;
 799           update_callee_keys (heap, where, updated_nodes);
 800         }
 801       else
 802         {
 803           struct cgraph_node *callee;
 804           if (!cgraph_check_inline_limits (edge->caller, edge->callee,
 805                                            &edge->inline_failed))
 806             {
 807               if (dump_file)
 808                 fprintf (dump_file, " Not inlining into %s:%s.\n",
 809                          cgraph_node_name (edge->caller), edge->inline_failed);
 810               continue;
 811             }
 812           callee = edge->callee;
 813           cgraph_mark_inline_edge (edge, true);
 814           update_callee_keys (heap, callee, updated_nodes);
 815         }
 816       where = edge->caller;
 817       if (where->global.inlined_to)
 818         where = where->global.inlined_to;
 819
 820       /* Our profitability metric can depend on local properties
 821          such as number of inlinable calls and size of the function body.
 822          After inlining these properties might change for the function we
 823          inlined into (since it's body size changed) and for the functions
 824          called by function we inlined (since number of it inlinable callers
 825          might change).  */
 826       update_caller_keys (heap, where, updated_nodes);
 827       bitmap_clear (updated_nodes);
 828
 829       if (dump_file)
 830         fprintf (dump_file,
 831                  " Inlined into %s which now has %i insns.\n",
 832                  cgraph_node_name (edge->caller),
 833                  edge->caller->global.insns);
 834       if (dump_file)
 835         fprintf (dump_file,
 836                  " Inlined for a net change of %+i insns.\n",
 837                  overall_insns - old_insns);
 838     }
 839   while ((edge = fibheap_extract_min (heap)) != NULL)
 840     {
 841       gcc_assert (edge->aux);
 842       edge->aux = NULL;
 843       if (!edge->callee->local.disregard_inline_limits && edge->inline_failed
 844           && !cgraph_recursive_inlining_p (edge->caller, edge->callee,
 845                                            &edge->inline_failed))
 846         edge->inline_failed = N_("--param inline-unit-growth limit reached");
 847     }
 848   fibheap_delete (heap);
 849   BITMAP_FREE (updated_nodes);
 850 }
 851
 852 /* Decide on the inlining.  We do so in the topological order to avoid
 853    expenses on updating data structures.  */
 854
 855 static void
 856 cgraph_decide_inlining (void)
 857 {
 858   struct cgraph_node *node;
 859   int nnodes;
 860   struct cgraph_node **order =
 861     xcalloc (cgraph_n_nodes, sizeof (struct cgraph_node *));
 862   int old_insns = 0;
 863   int i;
 864
 865   timevar_push (TV_INLINE_HEURISTICS);
 866   max_count = 0;
 867   for (node = cgraph_nodes; node; node = node->next)
 868     {
 869       struct cgraph_edge *e;
 870       initial_insns += node->local.self_insns;
 871       for (e = node->callees; e; e = e->next_callee)
 872         if (max_count < e->count)
 873           max_count = e->count;
 874     }
 875   overall_insns = initial_insns;
 876   gcc_assert (!max_count || (profile_info && flag_branch_probabilities));
 877
 878   max_insns = ((HOST_WIDEST_INT) overall_insns
 879                * (100 + PARAM_VALUE (PARAM_INLINE_UNIT_GROWTH)) / 100);
 880
 881   nnodes = cgraph_postorder (order);
 882
 883   if (dump_file)
 884     fprintf (dump_file,
 885              "\nDeciding on inlining.  Starting with %i insns.\n",
 886              initial_insns);
 887
 888   for (node = cgraph_nodes; node; node = node->next)
 889     node->aux = 0;
 890
 891   if (dump_file)
 892     fprintf (dump_file, "\nInlining always_inline functions:\n");
 893
 894   /* In the first pass mark all always_inline edges.  Do this with a priority
 895      so none of our later choices will make this impossible.  */
 896   for (i = nnodes - 1; i >= 0; i--)
 897     {
 898       struct cgraph_edge *e, *next;
 899
 900       node = order[i];
 901
 902       /* Handle nodes to be flattened, but don't update overall unit size.  */
 903       if (lookup_attribute ("flatten", DECL_ATTRIBUTES (node->decl)) != NULL)
 904         {
 905           int old_overall_insns = overall_insns;
 906           htab_t cycles;
 907           if (dump_file)
 908             fprintf (dump_file,
 909                      "Leafifying %s\n", cgraph_node_name (node));
 910           cycles = htab_create (7, htab_hash_pointer, htab_eq_pointer, NULL);
 911           cgraph_find_cycles (node, cycles);
 912           cgraph_flatten_node (node, cycles);
 913           htab_delete (cycles);
 914           overall_insns = old_overall_insns;
 915           /* We don't need to consider always_inline functions inside the flattened
 916              function anymore.  */
 917           continue;
 918         }
 919
 920       if (!node->local.disregard_inline_limits)
 921         continue;
 922       if (dump_file)
 923         fprintf (dump_file,
 924                  "\nConsidering %s %i insns (always inline)\n",
 925                  cgraph_node_name (node), node->global.insns);
 926       old_insns = overall_insns;
 927       for (e = node->callers; e; e = next)
 928         {
 929           next = e->next_caller;
 930           if (!e->inline_failed)
 931             continue;
 932           if (cgraph_recursive_inlining_p (e->caller, e->callee,
 933                                            &e->inline_failed))
 934             continue;
 935           cgraph_mark_inline_edge (e, true);
 936           if (dump_file)
 937             fprintf (dump_file,
 938                      " Inlined into %s which now has %i insns.\n",
 939                      cgraph_node_name (e->caller),
 940                      e->caller->global.insns);
 941         }
 942       if (dump_file)
 943         fprintf (dump_file,
 944                  " Inlined for a net change of %+i insns.\n",
 945                  overall_insns - old_insns);
 946     }
 947
 948   if (!flag_really_no_inline)
 949     cgraph_decide_inlining_of_small_functions ();
 950
 951   if (!flag_really_no_inline
 952       && flag_inline_functions_called_once)
 953     {
 954       if (dump_file)
 955         fprintf (dump_file, "\nDeciding on functions called once:\n");
 956
 957       /* And finally decide what functions are called once.  */
 958
 959       for (i = nnodes - 1; i >= 0; i--)
 960         {
 961           node = order[i];
 962
 963           if (node->callers && !node->callers->next_caller && !node->needed
 964               && node->local.inlinable && node->callers->inline_failed
 965               && !DECL_EXTERNAL (node->decl) && !DECL_COMDAT (node->decl))
 966             {
 967               bool ok = true;
 968               struct cgraph_node *node1;
 969
 970               /* Verify that we won't duplicate the caller.  */
 971               for (node1 = node->callers->caller;
 972                    node1->callers && !node1->callers->inline_failed
 973                    && ok; node1 = node1->callers->caller)
 974                 if (node1->callers->next_caller || node1->needed)
 975                   ok = false;
 976               if (ok)
 977                 {
 978                   if (dump_file)
 979                     fprintf (dump_file,
 980                              "\nConsidering %s %i insns.\n"
 981                              " Called once from %s %i insns.\n",
 982                              cgraph_node_name (node), node->global.insns,
 983                              cgraph_node_name (node->callers->caller),
 984                              node->callers->caller->global.insns);
 985
 986                   old_insns = overall_insns;
 987
 988                   if (cgraph_check_inline_limits (node->callers->caller, node,
 989                                                   NULL))
 990                     {
 991                       cgraph_mark_inline (node->callers);
 992                       if (dump_file)
 993                         fprintf (dump_file,
 994                                  " Inlined into %s which now has %i insns"
 995                                  " for a net change of %+i insns.\n",
 996                                  cgraph_node_name (node->callers->caller),
 997                                  node->callers->caller->global.insns,
 998                                  overall_insns - old_insns);
 999                     }
1000                   else
1001                     {
1002                       if (dump_file)
1003                         fprintf (dump_file,
1004                                  " Inline limit reached, not inlined.\n");
1005                     }
1006                 }
1007             }
1008         }
1009     }
1010
1011   if (dump_file)
1012     fprintf (dump_file,
1013              "\nInlined %i calls, eliminated %i functions, "
1014              "%i insns turned to %i insns.\n\n",
1015              ncalls_inlined, nfunctions_inlined, initial_insns,
1016              overall_insns);
1017   free (order);
1018   timevar_pop (TV_INLINE_HEURISTICS);
1019 }
1020
1021 /* Decide on the inlining.  We do so in the topological order to avoid
1022    expenses on updating data structures.  */
1023
1024 bool
1025 cgraph_decide_inlining_incrementally (struct cgraph_node *node, bool early)
1026 {
1027   struct cgraph_edge *e;
1028   bool inlined = false;
1029   const char *failed_reason;
1030
1031   /* First of all look for always inline functions.  */
1032   for (e = node->callees; e; e = e->next_callee)
1033     if (e->callee->local.disregard_inline_limits
1034         && e->inline_failed
1035         && !cgraph_recursive_inlining_p (node, e->callee, &e->inline_failed)
1036         /* ??? It is possible that renaming variable removed the function body
1037            in duplicate_decls. See gcc.c-torture/compile/20011119-2.c  */
1038         && DECL_SAVED_TREE (e->callee->decl))
1039       {
1040         if (dump_file && early)
1041           fprintf (dump_file, "  Early inlining %s into %s\n",
1042                    cgraph_node_name (e->callee), cgraph_node_name (node));
1043         cgraph_mark_inline (e);
1044         inlined = true;
1045       }
1046
1047   /* Now do the automatic inlining.  */
1048   if (!flag_really_no_inline)
1049     for (e = node->callees; e; e = e->next_callee)
1050       if (e->callee->local.inlinable
1051           && e->inline_failed
1052           && !e->callee->local.disregard_inline_limits
1053           && !cgraph_recursive_inlining_p (node, e->callee, &e->inline_failed)
1054           && (!early
1055               || (cgraph_estimate_size_after_inlining (1, e->caller, node)
1056                   <= e->caller->global.insns))
1057           && cgraph_check_inline_limits (node, e->callee, &e->inline_failed)
1058           && DECL_SAVED_TREE (e->callee->decl))
1059         {
1060           if (cgraph_default_inline_p (e->callee, &failed_reason))
1061             {
1062               if (dump_file && early)
1063                 fprintf (dump_file, "  Early inlining %s into %s\n",
1064                          cgraph_node_name (e->callee), cgraph_node_name (node));
1065               cgraph_mark_inline (e);
1066               inlined = true;
1067             }
1068           else if (!early)
1069             e->inline_failed = failed_reason;
1070         }
1071   if (early && inlined)
1072     {
1073       push_cfun (DECL_STRUCT_FUNCTION (node->decl));
1074       tree_register_cfg_hooks ();
1075       current_function_decl = node->decl;
1076       optimize_inline_calls (current_function_decl);
1077       node->local.self_insns = node->global.insns;
1078       current_function_decl = NULL;
1079       pop_cfun ();
1080     }
1081   return inlined;
1082 }
1083
1084 /* When inlining shall be performed.  */
1085 static bool
1086 cgraph_gate_inlining (void)
1087 {
1088   return flag_inline_trees;
1089 }
1090
1091 struct tree_opt_pass pass_ipa_inline =
1092 {
1093   "inline",                             /* name */
1094   cgraph_gate_inlining,                 /* gate */
1095   cgraph_decide_inlining,               /* execute */
1096   NULL,                                 /* sub */
1097   NULL,                                 /* next */
1098   0,                                    /* static_pass_number */
1099   TV_INTEGRATION,                       /* tv_id */
1100   0,                                    /* properties_required */
1101   PROP_cfg,                             /* properties_provided */
1102   0,                                    /* properties_destroyed */
1103   0,                                    /* todo_flags_start */
1104   TODO_dump_cgraph | TODO_dump_func,    /* todo_flags_finish */
1105   0                                     /* letter */
1106 };
1107
1108 /* Do inlining of small functions.  Doing so early helps profiling and other
1109    passes to be somewhat more effective and avoids some code duplication in
1110    later real inlining pass for testcases with very many function calls.  */
1111 static void
1112 cgraph_early_inlining (void)
1113 {
1114   struct cgraph_node *node;
1115   int nnodes;
1116   struct cgraph_node **order =
1117     xcalloc (cgraph_n_nodes, sizeof (struct cgraph_node *));
1118   int i;
1119
1120   if (sorrycount || errorcount)
1121     return;
1122 #ifdef ENABLE_CHECKING
1123   for (node = cgraph_nodes; node; node = node->next)
1124     gcc_assert (!node->aux);
1125 #endif
1126
1127   nnodes = cgraph_postorder (order);
1128   for (i = nnodes - 1; i >= 0; i--)
1129     {
1130       node = order[i];
1131       if (node->analyzed && node->local.inlinable
1132           && (node->needed || node->reachable)
1133           && node->callers)
1134         cgraph_decide_inlining_incrementally (node, true);
1135     }
1136   cgraph_remove_unreachable_nodes (true, dump_file);
1137 #ifdef ENABLE_CHECKING
1138   for (node = cgraph_nodes; node; node = node->next)
1139     gcc_assert (!node->global.inlined_to);
1140 #endif
1141   free (order);
1142 }
1143
1144 /* When inlining shall be performed.  */
1145 static bool
1146 cgraph_gate_early_inlining (void)
1147 {
1148   return flag_inline_trees && flag_early_inlining;
1149 }
1150
1151 struct tree_opt_pass pass_early_ipa_inline =
1152 {
1153   "einline",                            /* name */
1154   cgraph_gate_early_inlining,           /* gate */
1155   cgraph_early_inlining,                /* execute */
1156   NULL,                                 /* sub */
1157   NULL,                                 /* next */
1158   0,                                    /* static_pass_number */
1159   TV_INTEGRATION,                       /* tv_id */
1160   0,                                    /* properties_required */
1161   PROP_cfg,                             /* properties_provided */
1162   0,                                    /* properties_destroyed */
1163   0,                                    /* todo_flags_start */
1164   TODO_dump_cgraph | TODO_dump_func,    /* todo_flags_finish */
1165   0                                     /* letter */
1166 };