gcc/ipa-inline-analysis.c

   1 /* Analysis used by inlining decision heuristics.
   2    Copyright (C) 2003-2021 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   edge_growth_cache->disable_duplication_hook ();
 131   node_context_cache->disable_insertion_hook ();
 132   node_context_cache->disable_duplication_hook ();
 133 }
 134
 135 /* Free growth caches.  */
 136
 137 void
 138 free_growth_caches (void)
 139 {
 140   delete edge_growth_cache;
 141   delete node_context_cache;
 142   edge_growth_cache = NULL;
 143   node_context_cache = NULL;
 144   if (dump_file)
 145     fprintf (dump_file, "node context cache: %li hits, %li misses,"
 146                         " %li initializations\n",
 147              node_context_cache_hit, node_context_cache_miss,
 148              node_context_cache_clear);
 149   node_context_cache_hit = 0;
 150   node_context_cache_miss = 0;
 151   node_context_cache_clear = 0;
 152 }
 153
 154 /* Return hints derived from EDGE.   */
 155
 156 int
 157 simple_edge_hints (struct cgraph_edge *edge)
 158 {
 159   int hints = 0;
 160   struct cgraph_node *to = (edge->caller->inlined_to
 161                             ? edge->caller->inlined_to : edge->caller);
 162   struct cgraph_node *callee = edge->callee->ultimate_alias_target ();
 163   int to_scc_no = ipa_fn_summaries->get (to)->scc_no;
 164   int callee_scc_no = ipa_fn_summaries->get (callee)->scc_no;
 165
 166   if (to_scc_no && to_scc_no  == callee_scc_no && !edge->recursive_p ())
 167     hints |= INLINE_HINT_same_scc;
 168
 169   if (cross_module_call_p (edge))
 170     hints |= INLINE_HINT_cross_module;
 171
 172   return hints;
 173 }
 174
 175 /* Estimate the time cost for the caller when inlining EDGE.
 176    Only to be called via estimate_edge_time, that handles the
 177    caching mechanism.
 178
 179    When caching, also update the cache entry.  Compute both time and
 180    size, since we always need both metrics eventually.  */
 181
 182 sreal
 183 do_estimate_edge_time (struct cgraph_edge *edge, sreal *ret_nonspec_time)
 184 {
 185   sreal time, nonspec_time;
 186   int size;
 187   ipa_hints hints;
 188   struct cgraph_node *callee;
 189   clause_t clause, nonspec_clause;
 190   ipa_auto_call_arg_values avals;
 191   class ipa_call_summary *es = ipa_call_summaries->get (edge);
 192   int min_size = -1;
 193
 194   callee = edge->callee->ultimate_alias_target ();
 195
 196   gcc_checking_assert (edge->inline_failed);
 197   evaluate_properties_for_edge (edge, true, &clause, &nonspec_clause,
 198                                 &avals, true);
 199   ipa_call_context ctx (callee, clause, nonspec_clause, es->param, &avals);
 200   if (node_context_cache != NULL)
 201     {
 202       node_context_summary *e = node_context_cache->get_create (callee);
 203       if (e->entry.ctx.equal_to (ctx))
 204         {
 205           node_context_cache_hit++;
 206           size = e->entry.size;
 207           time = e->entry.time;
 208           nonspec_time = e->entry.nonspec_time;
 209           hints = e->entry.hints;
 210           if (flag_checking
 211               && !opt_for_fn (callee->decl, flag_profile_partial_training)
 212               && !callee->count.ipa_p ())
 213             {
 214               ipa_call_estimates chk_estimates;
 215               ctx.estimate_size_and_time (&chk_estimates);
 216               gcc_assert (chk_estimates.size == size
 217                           && chk_estimates.time == time
 218                           && chk_estimates.nonspecialized_time == nonspec_time
 219                           && chk_estimates.hints == hints);
 220             }
 221         }
 222       else
 223         {
 224           if (e->entry.ctx.exists_p ())
 225             node_context_cache_miss++;
 226           else
 227             node_context_cache_clear++;
 228           e->entry.ctx.release ();
 229           ipa_call_estimates estimates;
 230           ctx.estimate_size_and_time (&estimates);
 231           size = estimates.size;
 232           e->entry.size = size;
 233           time = estimates.time;
 234           e->entry.time = time;
 235           nonspec_time = estimates.nonspecialized_time;
 236           e->entry.nonspec_time = nonspec_time;
 237           hints = estimates.hints;
 238           e->entry.hints = hints;
 239           e->entry.ctx.duplicate_from (ctx);
 240         }
 241     }
 242   else
 243     {
 244       ipa_call_estimates estimates;
 245       ctx.estimate_size_and_time (&estimates);
 246       size = estimates.size;
 247       time = estimates.time;
 248       nonspec_time = estimates.nonspecialized_time;
 249       hints = estimates.hints;
 250     }
 251
 252   /* When we have profile feedback, we can quite safely identify hot
 253      edges and for those we disable size limits.  Don't do that when
 254      probability that caller will call the callee is low however, since it
 255      may hurt optimization of the caller's hot path.  */
 256   if (edge->count.ipa ().initialized_p () && edge->maybe_hot_p ()
 257       && (edge->count.ipa ().apply_scale (2, 1)
 258           > (edge->caller->inlined_to
 259              ? edge->caller->inlined_to->count.ipa ()
 260              : edge->caller->count.ipa ())))
 261     hints |= INLINE_HINT_known_hot;
 262
 263   gcc_checking_assert (size >= 0);
 264   gcc_checking_assert (time >= 0);
 265
 266   /* When caching, update the cache entry.  */
 267   if (edge_growth_cache != NULL)
 268     {
 269       if (min_size >= 0)
 270         ipa_fn_summaries->get (edge->callee->function_symbol ())->min_size
 271            = min_size;
 272       edge_growth_cache_entry *entry
 273         = edge_growth_cache->get_create (edge);
 274       entry->time = time;
 275       entry->nonspec_time = nonspec_time;
 276
 277       entry->size = size + (size >= 0);
 278       hints |= simple_edge_hints (edge);
 279       entry->hints = hints + 1;
 280     }
 281   if (ret_nonspec_time)
 282     *ret_nonspec_time = nonspec_time;
 283   return time;
 284 }
 285
 286 /* Reset cache for NODE.
 287    This must be done each time NODE body is modified.  */
 288 void
 289 reset_node_cache (struct cgraph_node *node)
 290 {
 291   if (node_context_cache)
 292     node_context_cache->remove (node);
 293 }
 294
 295 /* Remove EDGE from caches once it was inlined.  */
 296 void
 297 ipa_remove_from_growth_caches (struct cgraph_edge *edge)
 298 {
 299   if (node_context_cache)
 300     node_context_cache->remove (edge->callee);
 301   if (edge_growth_cache)
 302     edge_growth_cache->remove (edge);
 303 }
 304
 305 /* Return estimated callee growth after inlining EDGE.
 306    Only to be called via estimate_edge_size.  */
 307
 308 int
 309 do_estimate_edge_size (struct cgraph_edge *edge)
 310 {
 311   int size;
 312   struct cgraph_node *callee;
 313   clause_t clause, nonspec_clause;
 314
 315   /* When we do caching, use do_estimate_edge_time to populate the entry.  */
 316
 317   if (edge_growth_cache != NULL)
 318     {
 319       do_estimate_edge_time (edge);
 320       size = edge_growth_cache->get (edge)->size;
 321       gcc_checking_assert (size);
 322       return size - (size > 0);
 323     }
 324
 325   callee = edge->callee->ultimate_alias_target ();
 326
 327   /* Early inliner runs without caching, go ahead and do the dirty work.  */
 328   gcc_checking_assert (edge->inline_failed);
 329   ipa_auto_call_arg_values avals;
 330   evaluate_properties_for_edge (edge, true, &clause, &nonspec_clause,
 331                                 &avals, true);
 332   ipa_call_context ctx (callee, clause, nonspec_clause, vNULL, &avals);
 333   ipa_call_estimates estimates;
 334   ctx.estimate_size_and_time (&estimates, false, false);
 335   return estimates.size;
 336 }
 337
 338
 339 /* Estimate the growth of the caller when inlining EDGE.
 340    Only to be called via estimate_edge_size.  */
 341
 342 ipa_hints
 343 do_estimate_edge_hints (struct cgraph_edge *edge)
 344 {
 345   struct cgraph_node *callee;
 346   clause_t clause, nonspec_clause;
 347
 348   /* When we do caching, use do_estimate_edge_time to populate the entry.  */
 349
 350   if (edge_growth_cache != NULL)
 351     {
 352       do_estimate_edge_time (edge);
 353       ipa_hints hints = edge_growth_cache->get (edge)->hints;
 354       gcc_checking_assert (hints);
 355       return hints - 1;
 356     }
 357
 358   callee = edge->callee->ultimate_alias_target ();
 359
 360   /* Early inliner runs without caching, go ahead and do the dirty work.  */
 361   gcc_checking_assert (edge->inline_failed);
 362   ipa_auto_call_arg_values avals;
 363   evaluate_properties_for_edge (edge, true, &clause, &nonspec_clause,
 364                                 &avals, true);
 365   ipa_call_context ctx (callee, clause, nonspec_clause, vNULL, &avals);
 366   ipa_call_estimates estimates;
 367   ctx.estimate_size_and_time (&estimates, false, true);
 368   ipa_hints hints = estimates.hints | simple_edge_hints (edge);
 369   return hints;
 370 }
 371
 372 /* Estimate the size of NODE after inlining EDGE which should be an
 373    edge to either NODE or a call inlined into NODE.  */
 374
 375 int
 376 estimate_size_after_inlining (struct cgraph_node *node,
 377                               struct cgraph_edge *edge)
 378 {
 379   class ipa_call_summary *es = ipa_call_summaries->get (edge);
 380   ipa_size_summary *s = ipa_size_summaries->get (node);
 381   if (!es->predicate || *es->predicate != false)
 382     {
 383       int size = s->size + estimate_edge_growth (edge);
 384       gcc_assert (size >= 0);
 385       return size;
 386     }
 387   return s->size;
 388 }
 389
 390
 391 struct growth_data
 392 {
 393   struct cgraph_node *node;
 394   bool self_recursive;
 395   bool uninlinable;
 396   int growth;
 397   int cap;
 398 };
 399
 400
 401 /* Worker for do_estimate_growth.  Collect growth for all callers.  */
 402
 403 static bool
 404 do_estimate_growth_1 (struct cgraph_node *node, void *data)
 405 {
 406   struct cgraph_edge *e;
 407   struct growth_data *d = (struct growth_data *) data;
 408
 409   for (e = node->callers; e; e = e->next_caller)
 410     {
 411       gcc_checking_assert (e->inline_failed);
 412
 413       if (cgraph_inline_failed_type (e->inline_failed) == CIF_FINAL_ERROR
 414           || !opt_for_fn (e->caller->decl, optimize))
 415         {
 416           d->uninlinable = true;
 417           if (d->cap < INT_MAX)
 418             return true;
 419           continue;
 420         }
 421
 422       if (e->recursive_p ())
 423         {
 424           d->self_recursive = true;
 425           if (d->cap < INT_MAX)
 426             return true;
 427           continue;
 428         }
 429       d->growth += estimate_edge_growth (e);
 430       if (d->growth > d->cap)
 431         return true;
 432     }
 433   return false;
 434 }
 435
 436 /* Return estimated savings for eliminating offline copy of NODE by inlining
 437    it everywhere.  */
 438
 439 static int
 440 offline_size (struct cgraph_node *node, ipa_size_summary *info)
 441 {
 442   if (!DECL_EXTERNAL (node->decl))
 443     {
 444       if (node->will_be_removed_from_program_if_no_direct_calls_p ())
 445         return info->size;
 446       /* COMDAT functions are very often not shared across multiple units
 447          since they come from various template instantiations.
 448          Take this into account.  */
 449       else if (DECL_COMDAT (node->decl)
 450                && node->can_remove_if_no_direct_calls_p ())
 451         {
 452           int prob = opt_for_fn (node->decl, param_comdat_sharing_probability);
 453           return (info->size * (100 - prob) + 50) / 100;
 454         }
 455     }
 456   return 0;
 457 }
 458
 459 /* Estimate the growth caused by inlining NODE into all callers.  */
 460
 461 int
 462 estimate_growth (struct cgraph_node *node)
 463 {
 464   struct growth_data d = { node, false, false, 0, INT_MAX };
 465   ipa_size_summary *info = ipa_size_summaries->get (node);
 466
 467   if (node->call_for_symbol_and_aliases (do_estimate_growth_1, &d, true))
 468     return 1;
 469
 470   /* For self recursive functions the growth estimation really should be
 471      infinity.  We don't want to return very large values because the growth
 472      plays various roles in badness computation fractions.  Be sure to not
 473      return zero or negative growths. */
 474   if (d.self_recursive)
 475     d.growth = d.growth < info->size ? info->size : d.growth;
 476   else if (!d.uninlinable)
 477     d.growth -= offline_size (node, info);
 478
 479   return d.growth;
 480 }
 481
 482 /* Verify if there are fewer than MAX_CALLERS.  */
 483
 484 static bool
 485 check_callers (cgraph_node *node, int *growth, int *n, int offline,
 486                int min_size, struct cgraph_edge *known_edge)
 487 {
 488   ipa_ref *ref;
 489
 490   if (!node->can_remove_if_no_direct_calls_and_refs_p ())
 491     return true;
 492
 493   for (cgraph_edge *e = node->callers; e; e = e->next_caller)
 494     {
 495       edge_growth_cache_entry *entry;
 496
 497       if (e == known_edge)
 498         continue;
 499       if (cgraph_inline_failed_type (e->inline_failed) == CIF_FINAL_ERROR)
 500         return true;
 501       if (edge_growth_cache != NULL
 502           && (entry = edge_growth_cache->get (e)) != NULL
 503           && entry->size != 0)
 504         *growth += entry->size - (entry->size > 0);
 505       else
 506         {
 507           class ipa_call_summary *es = ipa_call_summaries->get (e);
 508           if (!es)
 509             return true;
 510           *growth += min_size - es->call_stmt_size;
 511           if (--(*n) < 0)
 512             return false;
 513         }
 514       if (*growth > offline)
 515         return true;
 516     }
 517
 518   if (*n > 0)
 519     FOR_EACH_ALIAS (node, ref)
 520       if (check_callers (dyn_cast <cgraph_node *> (ref->referring), growth, n,
 521                          offline, min_size, known_edge))
 522         return true;
 523
 524   return false;
 525 }
 526
 527
 528 /* Decide if growth of NODE is positive.  This is cheaper than calculating
 529    actual growth.  If edge growth of KNOWN_EDGE is known
 530    it is passed by EDGE_GROWTH.  */
 531
 532 bool
 533 growth_positive_p (struct cgraph_node *node,
 534                    struct cgraph_edge * known_edge, int edge_growth)
 535 {
 536   struct cgraph_edge *e;
 537
 538   ipa_size_summary *s = ipa_size_summaries->get (node);
 539
 540   /* First quickly check if NODE is removable at all.  */
 541   int offline = offline_size (node, s);
 542   if (offline <= 0 && known_edge && edge_growth > 0)
 543     return true;
 544
 545   int min_size = ipa_fn_summaries->get (node)->min_size;
 546   int n = 10;
 547
 548   int min_growth = known_edge ? edge_growth : 0;
 549   for (e = node->callers; e; e = e->next_caller)
 550     {
 551       edge_growth_cache_entry *entry;
 552
 553       if (cgraph_inline_failed_type (e->inline_failed) == CIF_FINAL_ERROR)
 554         return true;
 555       if (e == known_edge)
 556         continue;
 557       if (edge_growth_cache != NULL
 558           && (entry = edge_growth_cache->get (e)) != NULL
 559           && entry->size != 0)
 560         min_growth += entry->size - (entry->size > 0);
 561       else
 562         {
 563           class ipa_call_summary *es = ipa_call_summaries->get (e);
 564           if (!es)
 565             return true;
 566           min_growth += min_size - es->call_stmt_size;
 567           if (--n <= 0)
 568             break;
 569         }
 570       if (min_growth > offline)
 571         return true;
 572     }
 573
 574   ipa_ref *ref;
 575   if (n > 0)
 576     FOR_EACH_ALIAS (node, ref)
 577       if (check_callers (dyn_cast <cgraph_node *> (ref->referring),
 578                          &min_growth, &n, offline, min_size, known_edge))
 579         return true;
 580
 581   struct growth_data d = { node, false, false, 0, offline };
 582   if (node->call_for_symbol_and_aliases (do_estimate_growth_1, &d, true))
 583     return true;
 584   if (d.self_recursive || d.uninlinable)
 585     return true;
 586   return (d.growth > offline);
 587 }