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