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