gcc/ipa-inline-analysis.c

   1 /* Analysis used by inlining decision heuristics.
   2    Copyright (C) 2003-2019 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_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 derrived 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 (callee->lto_file_data && edge->caller->lto_file_data
 167       && edge->caller->lto_file_data != callee->lto_file_data
 168       && !callee->merged_comdat && !callee->icf_merged)
 169     hints |= INLINE_HINT_cross_module;
 170
 171   return hints;
 172 }
 173
 174 /* Estimate the time cost for the caller when inlining EDGE.
 175    Only to be called via estimate_edge_time, that handles the
 176    caching mechanism.
 177
 178    When caching, also update the cache entry.  Compute both time and
 179    size, since we always need both metrics eventually.  */
 180
 181 sreal
 182 do_estimate_edge_time (struct cgraph_edge *edge, sreal *ret_nonspec_time)
 183 {
 184   sreal time, nonspec_time;
 185   int size;
 186   ipa_hints hints;
 187   struct cgraph_node *callee;
 188   clause_t clause, nonspec_clause;
 189   auto_vec<tree, 32> known_vals;
 190   auto_vec<ipa_polymorphic_call_context, 32> known_contexts;
 191   auto_vec<ipa_agg_value_set, 32> known_aggs;
 192   class ipa_call_summary *es = ipa_call_summaries->get (edge);
 193   int min_size = -1;
 194
 195   callee = edge->callee->ultimate_alias_target ();
 196
 197   gcc_checking_assert (edge->inline_failed);
 198   evaluate_properties_for_edge (edge, true,
 199                                 &clause, &nonspec_clause, &known_vals,
 200                                 &known_contexts, &known_aggs);
 201   ipa_call_context ctx (callee, clause, nonspec_clause, known_vals,
 202                         known_contexts, known_aggs, es->param);
 203   if (node_context_cache != NULL)
 204     {
 205       node_context_summary *e = node_context_cache->get_create (callee);
 206       if (e->entry.ctx.equal_to (ctx))
 207         {
 208           node_context_cache_hit++;
 209           size = e->entry.size;
 210           time = e->entry.time;
 211           nonspec_time = e->entry.nonspec_time;
 212           hints = e->entry.hints;
 213           if (flag_checking
 214               && !callee->count.ipa_p ())
 215             {
 216               sreal chk_time, chk_nonspec_time;
 217               int chk_size, chk_min_size;
 218
 219               ipa_hints chk_hints;
 220               ctx.estimate_size_and_time (&chk_size, &chk_min_size,
 221                                           &chk_time, &chk_nonspec_time,
 222                                           &chk_hints);
 223               gcc_assert (chk_size == size && chk_time == time
 224                           && chk_nonspec_time == nonspec_time
 225                           && chk_hints == hints);
 226             }
 227         }
 228       else
 229         {
 230           if (e->entry.ctx.exists_p ())
 231             node_context_cache_miss++;
 232           else
 233             node_context_cache_clear++;
 234           e->entry.ctx.release (true);
 235           ctx.estimate_size_and_time (&size, &min_size,
 236                                       &time, &nonspec_time, &hints);
 237           e->entry.size = size;
 238           e->entry.time = time;
 239           e->entry.nonspec_time = nonspec_time;
 240           e->entry.hints = hints;
 241           e->entry.ctx.duplicate_from (ctx);
 242         }
 243     }
 244   else
 245     ctx.estimate_size_and_time (&size, &min_size,
 246                                 &time, &nonspec_time, &hints);
 247
 248   /* When we have profile feedback, we can quite safely identify hot
 249      edges and for those we disable size limits.  Don't do that when
 250      probability that caller will call the callee is low however, since it
 251      may hurt optimization of the caller's hot path.  */
 252   if (edge->count.ipa ().initialized_p () && edge->maybe_hot_p ()
 253       && (edge->count.ipa ().apply_scale (2, 1)
 254           > (edge->caller->inlined_to
 255              ? edge->caller->inlined_to->count.ipa ()
 256              : edge->caller->count.ipa ())))
 257     hints |= INLINE_HINT_known_hot;
 258
 259   ctx.release ();
 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   auto_vec<tree, 32> known_vals;
 312   auto_vec<ipa_polymorphic_call_context, 32> known_contexts;
 313   auto_vec<ipa_agg_value_set, 32> known_aggs;
 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   evaluate_properties_for_edge (edge, true,
 330                                 &clause, &nonspec_clause,
 331                                 &known_vals, &known_contexts,
 332                                 &known_aggs);
 333   ipa_call_context ctx (callee, clause, nonspec_clause, known_vals,
 334                         known_contexts, known_aggs, vNULL);
 335   ctx.estimate_size_and_time (&size, NULL, NULL, NULL, NULL);
 336   ctx.release ();
 337   return size;
 338 }
 339
 340
 341 /* Estimate the growth of the caller when inlining EDGE.
 342    Only to be called via estimate_edge_size.  */
 343
 344 ipa_hints
 345 do_estimate_edge_hints (struct cgraph_edge *edge)
 346 {
 347   ipa_hints hints;
 348   struct cgraph_node *callee;
 349   clause_t clause, nonspec_clause;
 350   auto_vec<tree, 32> known_vals;
 351   auto_vec<ipa_polymorphic_call_context, 32> known_contexts;
 352   auto_vec<ipa_agg_value_set, 32> known_aggs;
 353
 354   /* When we do caching, use do_estimate_edge_time to populate the entry.  */
 355
 356   if (edge_growth_cache != NULL)
 357     {
 358       do_estimate_edge_time (edge);
 359       hints = edge_growth_cache->get (edge)->hints;
 360       gcc_checking_assert (hints);
 361       return hints - 1;
 362     }
 363
 364   callee = edge->callee->ultimate_alias_target ();
 365
 366   /* Early inliner runs without caching, go ahead and do the dirty work.  */
 367   gcc_checking_assert (edge->inline_failed);
 368   evaluate_properties_for_edge (edge, true,
 369                                 &clause, &nonspec_clause,
 370                                 &known_vals, &known_contexts,
 371                                 &known_aggs);
 372   ipa_call_context ctx (callee, clause, nonspec_clause, known_vals,
 373                         known_contexts, known_aggs, vNULL);
 374   ctx.estimate_size_and_time (NULL, NULL, NULL, NULL, &hints);
 375   ctx.release ();
 376   hints |= simple_edge_hints (edge);
 377   return hints;
 378 }
 379
 380 /* Estimate the size of NODE after inlining EDGE which should be an
 381    edge to either NODE or a call inlined into NODE.  */
 382
 383 int
 384 estimate_size_after_inlining (struct cgraph_node *node,
 385                               struct cgraph_edge *edge)
 386 {
 387   class ipa_call_summary *es = ipa_call_summaries->get (edge);
 388   ipa_size_summary *s = ipa_size_summaries->get (node);
 389   if (!es->predicate || *es->predicate != false)
 390     {
 391       int size = s->size + estimate_edge_growth (edge);
 392       gcc_assert (size >= 0);
 393       return size;
 394     }
 395   return s->size;
 396 }
 397
 398
 399 struct growth_data
 400 {
 401   struct cgraph_node *node;
 402   bool self_recursive;
 403   bool uninlinable;
 404   int growth;
 405   int cap;
 406 };
 407
 408
 409 /* Worker for do_estimate_growth.  Collect growth for all callers.  */
 410
 411 static bool
 412 do_estimate_growth_1 (struct cgraph_node *node, void *data)
 413 {
 414   struct cgraph_edge *e;
 415   struct growth_data *d = (struct growth_data *) data;
 416
 417   for (e = node->callers; e; e = e->next_caller)
 418     {
 419       gcc_checking_assert (e->inline_failed);
 420
 421       if (cgraph_inline_failed_type (e->inline_failed) == CIF_FINAL_ERROR
 422           || !opt_for_fn (e->caller->decl, optimize))
 423         {
 424           d->uninlinable = true;
 425           if (d->cap < INT_MAX)
 426             return true;
 427           continue;
 428         }
 429
 430       if (e->recursive_p ())
 431         {
 432           d->self_recursive = true;
 433           if (d->cap < INT_MAX)
 434             return true;
 435           continue;
 436         }
 437       d->growth += estimate_edge_growth (e);
 438       if (d->growth > d->cap)
 439         return true;
 440     }
 441   return false;
 442 }
 443
 444 /* Return estimated savings for eliminating offline copy of NODE by inlining
 445    it everywhere.  */
 446
 447 static int
 448 offline_size (struct cgraph_node *node, ipa_size_summary *info)
 449 {
 450   if (!DECL_EXTERNAL (node->decl))
 451     {
 452       if (node->will_be_removed_from_program_if_no_direct_calls_p ())
 453         return info->size;
 454       /* COMDAT functions are very often not shared across multiple units
 455          since they come from various template instantiations.
 456          Take this into account.  */
 457       else if (DECL_COMDAT (node->decl)
 458                && node->can_remove_if_no_direct_calls_p ())
 459         return (info->size
 460                 * (100 - param_comdat_sharing_probability)
 461                 + 50) / 100;
 462     }
 463   return 0;
 464 }
 465
 466 /* Estimate the growth caused by inlining NODE into all callees.  */
 467
 468 int
 469 estimate_growth (struct cgraph_node *node)
 470 {
 471   struct growth_data d = { node, false, false, 0, INT_MAX };
 472   ipa_size_summary *info = ipa_size_summaries->get (node);
 473
 474   if (node->call_for_symbol_and_aliases (do_estimate_growth_1, &d, true))
 475     return 1;
 476
 477   /* For self recursive functions the growth estimation really should be
 478      infinity.  We don't want to return very large values because the growth
 479      plays various roles in badness computation fractions.  Be sure to not
 480      return zero or negative growths. */
 481   if (d.self_recursive)
 482     d.growth = d.growth < info->size ? info->size : d.growth;
 483   else if (!d.uninlinable)
 484     d.growth -= offline_size (node, info);
 485
 486   return d.growth;
 487 }
 488
 489 /* Verify if there are fewer than MAX_CALLERS.  */
 490
 491 static bool
 492 check_callers (cgraph_node *node, int *growth, int *n, int offline,
 493                int min_size, struct cgraph_edge *known_edge)
 494 {
 495   ipa_ref *ref;
 496
 497   if (!node->can_remove_if_no_direct_calls_and_refs_p ())
 498     return true;
 499
 500   for (cgraph_edge *e = node->callers; e; e = e->next_caller)
 501     {
 502       edge_growth_cache_entry *entry;
 503
 504       if (e == known_edge)
 505         continue;
 506       if (cgraph_inline_failed_type (e->inline_failed) == CIF_FINAL_ERROR)
 507         return true;
 508       if (edge_growth_cache != NULL
 509           && (entry = edge_growth_cache->get (e)) != NULL
 510           && entry->size != 0)
 511         *growth += entry->size - (entry->size > 0);
 512       else
 513         {
 514           class ipa_call_summary *es = ipa_call_summaries->get (e);
 515           if (!es)
 516             return true;
 517           *growth += min_size - es->call_stmt_size;
 518           if (--(*n) < 0)
 519             return false;
 520         }
 521       if (*growth > offline)
 522         return true;
 523     }
 524
 525   if (*n > 0)
 526     FOR_EACH_ALIAS (node, ref)
 527       if (check_callers (dyn_cast <cgraph_node *> (ref->referring), growth, n,
 528                          offline, min_size, known_edge))
 529         return true;
 530
 531   return false;
 532 }
 533
 534
 535 /* Decide if growth of NODE is positive.  This is cheaper than calculating
 536    actual growth.  If edge growth of KNOWN_EDGE is known
 537    it is passed by EDGE_GROWTH.  */
 538
 539 bool
 540 growth_positive_p (struct cgraph_node *node,
 541                    struct cgraph_edge * known_edge, int edge_growth)
 542 {
 543   struct cgraph_edge *e;
 544
 545   ipa_size_summary *s = ipa_size_summaries->get (node);
 546
 547   /* First quickly check if NODE is removable at all.  */
 548   int offline = offline_size (node, s);
 549   if (offline <= 0 && known_edge && edge_growth > 0)
 550     return true;
 551
 552   int min_size = ipa_fn_summaries->get (node)->min_size;
 553   int n = 10;
 554
 555   int min_growth = known_edge ? edge_growth : 0;
 556   for (e = node->callers; e; e = e->next_caller)
 557     {
 558       edge_growth_cache_entry *entry;
 559
 560       if (cgraph_inline_failed_type (e->inline_failed) == CIF_FINAL_ERROR)
 561         return true;
 562       if (e == known_edge)
 563         continue;
 564       if (edge_growth_cache != NULL
 565           && (entry = edge_growth_cache->get (e)) != NULL
 566           && entry->size != 0)
 567         min_growth += entry->size - (entry->size > 0);
 568       else
 569         {
 570           class ipa_call_summary *es = ipa_call_summaries->get (e);
 571           if (!es)
 572             return true;
 573           min_growth += min_size - es->call_stmt_size;
 574           if (--n <= 0)
 575             break;
 576         }
 577       if (min_growth > offline)
 578         return true;
 579     }
 580
 581   ipa_ref *ref;
 582   if (n > 0)
 583     FOR_EACH_ALIAS (node, ref)
 584       if (check_callers (dyn_cast <cgraph_node *> (ref->referring),
 585                          &min_growth, &n, offline, min_size, known_edge))
 586         return true;
 587
 588   struct growth_data d = { node, false, false, 0, offline };
 589   if (node->call_for_symbol_and_aliases (do_estimate_growth_1, &d, true))
 590     return true;
 591   if (d.self_recursive || d.uninlinable)
 592     return true;
 593   return (d.growth > offline);
 594 }