gcc/ipa-inline-analysis.c

   1 /* Analysis used by inlining decision heuristics.
   2    Copyright (C) 2003-2020 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 3, 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 COPYING3.  If not see
  19 <http://www.gnu.org/licenses/>.  */
  20
  21 #include "config.h"
  22 #include "system.h"
  23 #include "coretypes.h"
  24 #include "backend.h"
  25 #include "tree.h"
  26 #include "gimple.h"
  27 #include "alloc-pool.h"
  28 #include "tree-pass.h"
  29 #include "ssa.h"
  30 #include "tree-streamer.h"
  31 #include "cgraph.h"
  32 #include "diagnostic.h"
  33 #include "fold-const.h"
  34 #include "print-tree.h"
  35 #include "tree-inline.h"
  36 #include "gimple-pretty-print.h"
  37 #include "cfganal.h"
  38 #include "gimple-iterator.h"
  39 #include "tree-cfg.h"
  40 #include "tree-ssa-loop-niter.h"
  41 #include "tree-ssa-loop.h"
  42 #include "symbol-summary.h"
  43 #include "ipa-prop.h"
  44 #include "ipa-fnsummary.h"
  45 #include "ipa-inline.h"
  46 #include "cfgloop.h"
  47 #include "tree-scalar-evolution.h"
  48 #include "ipa-utils.h"
  49 #include "cfgexpand.h"
  50 #include "gimplify.h"
  51
  52 /* Cached node/edge growths.  */
  53 fast_call_summary<edge_growth_cache_entry *, va_heap> *edge_growth_cache = NULL;
  54
  55 /* The context cache remembers estimated time/size and hints for given
  56    ipa_call_context of a call.  */
  57 class node_context_cache_entry
  58 {
  59 public:
  60   ipa_cached_call_context ctx;
  61   sreal time, nonspec_time;
  62   int size;
  63   ipa_hints hints;
  64
  65   node_context_cache_entry ()
  66   : ctx ()
  67   {
  68   }
  69   ~node_context_cache_entry ()
  70   {
  71     ctx.release ();
  72   }
  73 };
  74
  75 /* At the moment we implement primitive single entry LRU cache.  */
  76 class node_context_summary
  77 {
  78 public:
  79   node_context_cache_entry entry;
  80
  81   node_context_summary ()
  82   : entry ()
  83   {
  84   }
  85   ~node_context_summary ()
  86   {
  87   }
  88 };
  89
  90 /* Summary holding the context cache.  */
  91 static fast_function_summary <node_context_summary *, va_heap>
  92         *node_context_cache = NULL;
  93 /* Statistics about the context cache effectivity.  */
  94 static long node_context_cache_hit, node_context_cache_miss,
  95             node_context_cache_clear;
  96
  97 /* Give initial reasons why inlining would fail on EDGE.  This gets either
  98    nullified or usually overwritten by more precise reasons later.  */
  99
 100 void
 101 initialize_inline_failed (struct cgraph_edge *e)
 102 {
 103   struct cgraph_node *callee = e->callee;
 104
 105   if (e->inline_failed && e->inline_failed != CIF_BODY_NOT_AVAILABLE
 106       && cgraph_inline_failed_type (e->inline_failed) == CIF_FINAL_ERROR)
 107     ;
 108   else if (e->indirect_unknown_callee)
 109     e->inline_failed = CIF_INDIRECT_UNKNOWN_CALL;
 110   else if (!callee->definition)
 111     e->inline_failed = CIF_BODY_NOT_AVAILABLE;
 112   else if (callee->redefined_extern_inline)
 113     e->inline_failed = CIF_REDEFINED_EXTERN_INLINE;
 114   else
 115     e->inline_failed = CIF_FUNCTION_NOT_CONSIDERED;
 116   gcc_checking_assert (!e->call_stmt_cannot_inline_p
 117                        || cgraph_inline_failed_type (e->inline_failed)
 118                             == CIF_FINAL_ERROR);
 119 }
 120
 121 /* Allocate edge growth caches.  */
 122
 123 void
 124 initialize_growth_caches ()
 125 {
 126   edge_growth_cache
 127     = new fast_call_summary<edge_growth_cache_entry *, va_heap> (symtab);
 128   node_context_cache
 129     = new fast_function_summary<node_context_summary *, va_heap> (symtab);
 130 }
 131
 132 /* Free growth caches.  */
 133
 134 void
 135 free_growth_caches (void)
 136 {
 137   delete edge_growth_cache;
 138   delete node_context_cache;
 139   edge_growth_cache = NULL;
 140   node_context_cache = NULL;
 141   if (dump_file)
 142     fprintf (dump_file, "node context cache: %li hits, %li misses,"
 143                         " %li initializations\n",
 144              node_context_cache_hit, node_context_cache_miss,
 145              node_context_cache_clear);
 146   node_context_cache_hit = 0;
 147   node_context_cache_miss = 0;
 148   node_context_cache_clear = 0;
 149 }
 150
 151 /* Return hints derived from EDGE.   */
 152
 153 int
 154 simple_edge_hints (struct cgraph_edge *edge)
 155 {
 156   int hints = 0;
 157   struct cgraph_node *to = (edge->caller->inlined_to
 158                             ? edge->caller->inlined_to : edge->caller);
 159   struct cgraph_node *callee = edge->callee->ultimate_alias_target ();
 160   int to_scc_no = ipa_fn_summaries->get (to)->scc_no;
 161   int callee_scc_no = ipa_fn_summaries->get (callee)->scc_no;
 162
 163   if (to_scc_no && to_scc_no  == callee_scc_no && !edge->recursive_p ())
 164     hints |= INLINE_HINT_same_scc;
 165
 166   if (cross_module_call_p (edge))
 167     hints |= INLINE_HINT_cross_module;
 168
 169   return hints;
 170 }
 171
 172 /* Estimate the time cost for the caller when inlining EDGE.
 173    Only to be called via estimate_edge_time, that handles the
 174    caching mechanism.
 175
 176    When caching, also update the cache entry.  Compute both time and
 177    size, since we always need both metrics eventually.  */
 178
 179 sreal
 180 do_estimate_edge_time (struct cgraph_edge *edge, sreal *ret_nonspec_time)
 181 {
 182   sreal time, nonspec_time;
 183   int size;
 184   ipa_hints hints;
 185   struct cgraph_node *callee;
 186   clause_t clause, nonspec_clause;
 187   ipa_auto_call_arg_values avals;
 188   class ipa_call_summary *es = ipa_call_summaries->get (edge);
 189   int min_size = -1;
 190
 191   callee = edge->callee->ultimate_alias_target ();
 192
 193   gcc_checking_assert (edge->inline_failed);
 194   evaluate_properties_for_edge (edge, true, &clause, &nonspec_clause,
 195                                 &avals, true);
 196   ipa_call_context ctx (callee, clause, nonspec_clause, es->param, &avals);
 197   if (node_context_cache != NULL)
 198     {
 199       node_context_summary *e = node_context_cache->get_create (callee);
 200       if (e->entry.ctx.equal_to (ctx))
 201         {
 202           node_context_cache_hit++;
 203           size = e->entry.size;
 204           time = e->entry.time;
 205           nonspec_time = e->entry.nonspec_time;
 206           hints = e->entry.hints;
 207           if (flag_checking
 208               && !opt_for_fn (callee->decl, flag_profile_partial_training)
 209               && !callee->count.ipa_p ())
 210             {
 211               ipa_call_estimates chk_estimates;
 212               ctx.estimate_size_and_time (&chk_estimates);
 213               gcc_assert (chk_estimates.size == size
 214                           && chk_estimates.time == time
 215                           && chk_estimates.nonspecialized_time == nonspec_time
 216                           && chk_estimates.hints == hints);
 217             }
 218         }
 219       else
 220         {
 221           if (e->entry.ctx.exists_p ())
 222             node_context_cache_miss++;
 223           else
 224             node_context_cache_clear++;
 225           e->entry.ctx.release ();
 226           ipa_call_estimates estimates;
 227           ctx.estimate_size_and_time (&estimates);
 228           size = estimates.size;
 229           e->entry.size = size;
 230           time = estimates.time;
 231           e->entry.time = time;
 232           nonspec_time = estimates.nonspecialized_time;
 233           e->entry.nonspec_time = nonspec_time;
 234           hints = estimates.hints;
 235           e->entry.hints = hints;
 236           e->entry.ctx.duplicate_from (ctx);
 237         }
 238     }
 239   else
 240     {
 241       ipa_call_estimates estimates;
 242       ctx.estimate_size_and_time (&estimates);
 243       size = estimates.size;
 244       time = estimates.time;
 245       nonspec_time = estimates.nonspecialized_time;
 246       hints = estimates.hints;
 247     }
 248
 249   /* When we have profile feedback, we can quite safely identify hot
 250      edges and for those we disable size limits.  Don't do that when
 251      probability that caller will call the callee is low however, since it
 252      may hurt optimization of the caller's hot path.  */
 253   if (edge->count.ipa ().initialized_p () && edge->maybe_hot_p ()
 254       && (edge->count.ipa ().apply_scale (2, 1)
 255           > (edge->caller->inlined_to
 256              ? edge->caller->inlined_to->count.ipa ()
 257              : edge->caller->count.ipa ())))
 258     hints |= INLINE_HINT_known_hot;
 259
 260   gcc_checking_assert (size >= 0);
 261   gcc_checking_assert (time >= 0);
 262
 263   /* When caching, update the cache entry.  */
 264   if (edge_growth_cache != NULL)
 265     {
 266       if (min_size >= 0)
 267         ipa_fn_summaries->get (edge->callee->function_symbol ())->min_size
 268            = min_size;
 269       edge_growth_cache_entry *entry
 270         = edge_growth_cache->get_create (edge);
 271       entry->time = time;
 272       entry->nonspec_time = nonspec_time;
 273
 274       entry->size = size + (size >= 0);
 275       hints |= simple_edge_hints (edge);
 276       entry->hints = hints + 1;
 277     }
 278   if (ret_nonspec_time)
 279     *ret_nonspec_time = nonspec_time;
 280   return time;
 281 }
 282
 283 /* Reset cache for NODE.
 284    This must be done each time NODE body is modified.  */
 285 void
 286 reset_node_cache (struct cgraph_node *node)
 287 {
 288   if (node_context_cache)
 289     node_context_cache->remove (node);
 290 }
 291
 292 /* Remove EDGE from caches once it was inlined.  */
 293 void
 294 ipa_remove_from_growth_caches (struct cgraph_edge *edge)
 295 {
 296   if (node_context_cache)
 297     node_context_cache->remove (edge->callee);
 298   if (edge_growth_cache)
 299     edge_growth_cache->remove (edge);
 300 }
 301
 302 /* Return estimated callee growth after inlining EDGE.
 303    Only to be called via estimate_edge_size.  */
 304
 305 int
 306 do_estimate_edge_size (struct cgraph_edge *edge)
 307 {
 308   int size;
 309   struct cgraph_node *callee;
 310   clause_t clause, nonspec_clause;
 311
 312   /* When we do caching, use do_estimate_edge_time to populate the entry.  */
 313
 314   if (edge_growth_cache != NULL)
 315     {
 316       do_estimate_edge_time (edge);
 317       size = edge_growth_cache->get (edge)->size;
 318       gcc_checking_assert (size);
 319       return size - (size > 0);
 320     }
 321
 322   callee = edge->callee->ultimate_alias_target ();
 323
 324   /* Early inliner runs without caching, go ahead and do the dirty work.  */
 325   gcc_checking_assert (edge->inline_failed);
 326   ipa_auto_call_arg_values avals;
 327   evaluate_properties_for_edge (edge, true, &clause, &nonspec_clause,
 328                                 &avals, true);
 329   ipa_call_context ctx (callee, clause, nonspec_clause, vNULL, &avals);
 330   ipa_call_estimates estimates;
 331   ctx.estimate_size_and_time (&estimates, false, false);
 332   return estimates.size;
 333 }
 334
 335
 336 /* Estimate the growth of the caller when inlining EDGE.
 337    Only to be called via estimate_edge_size.  */
 338
 339 ipa_hints
 340 do_estimate_edge_hints (struct cgraph_edge *edge)
 341 {
 342   struct cgraph_node *callee;
 343   clause_t clause, nonspec_clause;
 344
 345   /* When we do caching, use do_estimate_edge_time to populate the entry.  */
 346
 347   if (edge_growth_cache != NULL)
 348     {
 349       do_estimate_edge_time (edge);
 350       ipa_hints hints = edge_growth_cache->get (edge)->hints;
 351       gcc_checking_assert (hints);
 352       return hints - 1;
 353     }
 354
 355   callee = edge->callee->ultimate_alias_target ();
 356
 357   /* Early inliner runs without caching, go ahead and do the dirty work.  */
 358   gcc_checking_assert (edge->inline_failed);
 359   ipa_auto_call_arg_values avals;
 360   evaluate_properties_for_edge (edge, true, &clause, &nonspec_clause,
 361                                 &avals, true);
 362   ipa_call_context ctx (callee, clause, nonspec_clause, vNULL, &avals);
 363   ipa_call_estimates estimates;
 364   ctx.estimate_size_and_time (&estimates, false, true);
 365   ipa_hints hints = estimates.hints | simple_edge_hints (edge);
 366   return hints;
 367 }
 368
 369 /* Estimate the size of NODE after inlining EDGE which should be an
 370    edge to either NODE or a call inlined into NODE.  */
 371
 372 int
 373 estimate_size_after_inlining (struct cgraph_node *node,
 374                               struct cgraph_edge *edge)
 375 {
 376   class ipa_call_summary *es = ipa_call_summaries->get (edge);
 377   ipa_size_summary *s = ipa_size_summaries->get (node);
 378   if (!es->predicate || *es->predicate != false)
 379     {
 380       int size = s->size + estimate_edge_growth (edge);
 381       gcc_assert (size >= 0);
 382       return size;
 383     }
 384   return s->size;
 385 }
 386
 387
 388 struct growth_data
 389 {
 390   struct cgraph_node *node;
 391   bool self_recursive;
 392   bool uninlinable;
 393   int growth;
 394   int cap;
 395 };
 396
 397
 398 /* Worker for do_estimate_growth.  Collect growth for all callers.  */
 399
 400 static bool
 401 do_estimate_growth_1 (struct cgraph_node *node, void *data)
 402 {
 403   struct cgraph_edge *e;
 404   struct growth_data *d = (struct growth_data *) data;
 405
 406   for (e = node->callers; e; e = e->next_caller)
 407     {
 408       gcc_checking_assert (e->inline_failed);
 409
 410       if (cgraph_inline_failed_type (e->inline_failed) == CIF_FINAL_ERROR
 411           || !opt_for_fn (e->caller->decl, optimize))
 412         {
 413           d->uninlinable = true;
 414           if (d->cap < INT_MAX)
 415             return true;
 416           continue;
 417         }
 418
 419       if (e->recursive_p ())
 420         {
 421           d->self_recursive = true;
 422           if (d->cap < INT_MAX)
 423             return true;
 424           continue;
 425         }
 426       d->growth += estimate_edge_growth (e);
 427       if (d->growth > d->cap)
 428         return true;
 429     }
 430   return false;
 431 }
 432
 433 /* Return estimated savings for eliminating offline copy of NODE by inlining
 434    it everywhere.  */
 435
 436 static int
 437 offline_size (struct cgraph_node *node, ipa_size_summary *info)
 438 {
 439   if (!DECL_EXTERNAL (node->decl))
 440     {
 441       if (node->will_be_removed_from_program_if_no_direct_calls_p ())
 442         return info->size;
 443       /* COMDAT functions are very often not shared across multiple units
 444          since they come from various template instantiations.
 445          Take this into account.  */
 446       else if (DECL_COMDAT (node->decl)
 447                && node->can_remove_if_no_direct_calls_p ())
 448         {
 449           int prob = opt_for_fn (node->decl, param_comdat_sharing_probability);
 450           return (info->size * (100 - prob) + 50) / 100;
 451         }
 452     }
 453   return 0;
 454 }
 455
 456 /* Estimate the growth caused by inlining NODE into all callers.  */
 457
 458 int
 459 estimate_growth (struct cgraph_node *node)
 460 {
 461   struct growth_data d = { node, false, false, 0, INT_MAX };
 462   ipa_size_summary *info = ipa_size_summaries->get (node);
 463
 464   if (node->call_for_symbol_and_aliases (do_estimate_growth_1, &d, true))
 465     return 1;
 466
 467   /* For self recursive functions the growth estimation really should be
 468      infinity.  We don't want to return very large values because the growth
 469      plays various roles in badness computation fractions.  Be sure to not
 470      return zero or negative growths. */
 471   if (d.self_recursive)
 472     d.growth = d.growth < info->size ? info->size : d.growth;
 473   else if (!d.uninlinable)
 474     d.growth -= offline_size (node, info);
 475
 476   return d.growth;
 477 }
 478
 479 /* Verify if there are fewer than MAX_CALLERS.  */
 480
 481 static bool
 482 check_callers (cgraph_node *node, int *growth, int *n, int offline,
 483                int min_size, struct cgraph_edge *known_edge)
 484 {
 485   ipa_ref *ref;
 486
 487   if (!node->can_remove_if_no_direct_calls_and_refs_p ())
 488     return true;
 489
 490   for (cgraph_edge *e = node->callers; e; e = e->next_caller)
 491     {
 492       edge_growth_cache_entry *entry;
 493
 494       if (e == known_edge)
 495         continue;
 496       if (cgraph_inline_failed_type (e->inline_failed) == CIF_FINAL_ERROR)
 497         return true;
 498       if (edge_growth_cache != NULL
 499           && (entry = edge_growth_cache->get (e)) != NULL
 500           && entry->size != 0)
 501         *growth += entry->size - (entry->size > 0);
 502       else
 503         {
 504           class ipa_call_summary *es = ipa_call_summaries->get (e);
 505           if (!es)
 506             return true;
 507           *growth += min_size - es->call_stmt_size;
 508           if (--(*n) < 0)
 509             return false;
 510         }
 511       if (*growth > offline)
 512         return true;
 513     }
 514
 515   if (*n > 0)
 516     FOR_EACH_ALIAS (node, ref)
 517       if (check_callers (dyn_cast <cgraph_node *> (ref->referring), growth, n,
 518                          offline, min_size, known_edge))
 519         return true;
 520
 521   return false;
 522 }
 523
 524
 525 /* Decide if growth of NODE is positive.  This is cheaper than calculating
 526    actual growth.  If edge growth of KNOWN_EDGE is known
 527    it is passed by EDGE_GROWTH.  */
 528
 529 bool
 530 growth_positive_p (struct cgraph_node *node,
 531                    struct cgraph_edge * known_edge, int edge_growth)
 532 {
 533   struct cgraph_edge *e;
 534
 535   ipa_size_summary *s = ipa_size_summaries->get (node);
 536
 537   /* First quickly check if NODE is removable at all.  */
 538   int offline = offline_size (node, s);
 539   if (offline <= 0 && known_edge && edge_growth > 0)
 540     return true;
 541
 542   int min_size = ipa_fn_summaries->get (node)->min_size;
 543   int n = 10;
 544
 545   int min_growth = known_edge ? edge_growth : 0;
 546   for (e = node->callers; e; e = e->next_caller)
 547     {
 548       edge_growth_cache_entry *entry;
 549
 550       if (cgraph_inline_failed_type (e->inline_failed) == CIF_FINAL_ERROR)
 551         return true;
 552       if (e == known_edge)
 553         continue;
 554       if (edge_growth_cache != NULL
 555           && (entry = edge_growth_cache->get (e)) != NULL
 556           && entry->size != 0)
 557         min_growth += entry->size - (entry->size > 0);
 558       else
 559         {
 560           class ipa_call_summary *es = ipa_call_summaries->get (e);
 561           if (!es)
 562             return true;
 563           min_growth += min_size - es->call_stmt_size;
 564           if (--n <= 0)
 565             break;
 566         }
 567       if (min_growth > offline)
 568         return true;
 569     }
 570
 571   ipa_ref *ref;
 572   if (n > 0)
 573     FOR_EACH_ALIAS (node, ref)
 574       if (check_callers (dyn_cast <cgraph_node *> (ref->referring),
 575                          &min_growth, &n, offline, min_size, known_edge))
 576         return true;
 577
 578   struct growth_data d = { node, false, false, 0, offline };
 579   if (node->call_for_symbol_and_aliases (do_estimate_growth_1, &d, true))
 580     return true;
 581   if (d.self_recursive || d.uninlinable)
 582     return true;
 583   return (d.growth > offline);
 584 }