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