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_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   auto_vec<tree, 32> known_vals;
 188   auto_vec<ipa_polymorphic_call_context, 32> known_contexts;
 189   auto_vec<ipa_agg_value_set, 32> known_aggs;
 190   class ipa_call_summary *es = ipa_call_summaries->get (edge);
 191   int min_size = -1;
 192
 193   callee = edge->callee->ultimate_alias_target ();
 194
 195   gcc_checking_assert (edge->inline_failed);
 196   evaluate_properties_for_edge (edge, true,
 197                                 &clause, &nonspec_clause, &known_vals,
 198                                 &known_contexts, &known_aggs);
 199   ipa_call_context ctx (callee, clause, nonspec_clause, known_vals,
 200                         known_contexts, known_aggs, es->param);
 201   if (node_context_cache != NULL)
 202     {
 203       node_context_summary *e = node_context_cache->get_create (callee);
 204       if (e->entry.ctx.equal_to (ctx))
 205         {
 206           node_context_cache_hit++;
 207           size = e->entry.size;
 208           time = e->entry.time;
 209           nonspec_time = e->entry.nonspec_time;
 210           hints = e->entry.hints;
 211           if (flag_checking
 212               && !opt_for_fn (callee->decl, flag_profile_partial_training)
 213               && !callee->count.ipa_p ())
 214             {
 215               sreal chk_time, chk_nonspec_time;
 216               int chk_size, chk_min_size;
 217
 218               ipa_hints chk_hints;
 219               ctx.estimate_size_and_time (&chk_size, &chk_min_size,
 220                                           &chk_time, &chk_nonspec_time,
 221                                           &chk_hints);
 222               gcc_assert (chk_size == size && chk_time == time
 223                           && chk_nonspec_time == nonspec_time
 224                           && chk_hints == hints);
 225             }
 226         }
 227       else
 228         {
 229           if (e->entry.ctx.exists_p ())
 230             node_context_cache_miss++;
 231           else
 232             node_context_cache_clear++;
 233           e->entry.ctx.release (true);
 234           ctx.estimate_size_and_time (&size, &min_size,
 235                                       &time, &nonspec_time, &hints);
 236           e->entry.size = size;
 237           e->entry.time = time;
 238           e->entry.nonspec_time = nonspec_time;
 239           e->entry.hints = hints;
 240           e->entry.ctx.duplicate_from (ctx);
 241         }
 242     }
 243   else
 244     ctx.estimate_size_and_time (&size, &min_size,
 245                                 &time, &nonspec_time, &hints);
 246
 247   /* When we have profile feedback, we can quite safely identify hot
 248      edges and for those we disable size limits.  Don't do that when
 249      probability that caller will call the callee is low however, since it
 250      may hurt optimization of the caller's hot path.  */
 251   if (edge->count.ipa ().initialized_p () && edge->maybe_hot_p ()
 252       && (edge->count.ipa ().apply_scale (2, 1)
 253           > (edge->caller->inlined_to
 254              ? edge->caller->inlined_to->count.ipa ()
 255              : edge->caller->count.ipa ())))
 256     hints |= INLINE_HINT_known_hot;
 257
 258   ctx.release ();
 259   gcc_checking_assert (size >= 0);
 260   gcc_checking_assert (time >= 0);
 261
 262   /* When caching, update the cache entry.  */
 263   if (edge_growth_cache != NULL)
 264     {
 265       if (min_size >= 0)
 266         ipa_fn_summaries->get (edge->callee->function_symbol ())->min_size
 267            = min_size;
 268       edge_growth_cache_entry *entry
 269         = edge_growth_cache->get_create (edge);
 270       entry->time = time;
 271       entry->nonspec_time = nonspec_time;
 272
 273       entry->size = size + (size >= 0);
 274       hints |= simple_edge_hints (edge);
 275       entry->hints = hints + 1;
 276     }
 277   if (ret_nonspec_time)
 278     *ret_nonspec_time = nonspec_time;
 279   return time;
 280 }
 281
 282 /* Reset cache for NODE.
 283    This must be done each time NODE body is modified.  */
 284 void
 285 reset_node_cache (struct cgraph_node *node)
 286 {
 287   if (node_context_cache)
 288     node_context_cache->remove (node);
 289 }
 290
 291 /* Remove EDGE from caches once it was inlined.  */
 292 void
 293 ipa_remove_from_growth_caches (struct cgraph_edge *edge)
 294 {
 295   if (node_context_cache)
 296     node_context_cache->remove (edge->callee);
 297   if (edge_growth_cache)
 298     edge_growth_cache->remove (edge);
 299 }
 300
 301 /* Return estimated callee growth after inlining EDGE.
 302    Only to be called via estimate_edge_size.  */
 303
 304 int
 305 do_estimate_edge_size (struct cgraph_edge *edge)
 306 {
 307   int size;
 308   struct cgraph_node *callee;
 309   clause_t clause, nonspec_clause;
 310   auto_vec<tree, 32> known_vals;
 311   auto_vec<ipa_polymorphic_call_context, 32> known_contexts;
 312   auto_vec<ipa_agg_value_set, 32> known_aggs;
 313
 314   /* When we do caching, use do_estimate_edge_time to populate the entry.  */
 315
 316   if (edge_growth_cache != NULL)
 317     {
 318       do_estimate_edge_time (edge);
 319       size = edge_growth_cache->get (edge)->size;
 320       gcc_checking_assert (size);
 321       return size - (size > 0);
 322     }
 323
 324   callee = edge->callee->ultimate_alias_target ();
 325
 326   /* Early inliner runs without caching, go ahead and do the dirty work.  */
 327   gcc_checking_assert (edge->inline_failed);
 328   evaluate_properties_for_edge (edge, true,
 329                                 &clause, &nonspec_clause,
 330                                 &known_vals, &known_contexts,
 331                                 &known_aggs);
 332   ipa_call_context ctx (callee, clause, nonspec_clause, known_vals,
 333                         known_contexts, known_aggs, vNULL);
 334   ctx.estimate_size_and_time (&size, NULL, NULL, NULL, NULL);
 335   ctx.release ();
 336   return size;
 337 }
 338
 339
 340 /* Estimate the growth of the caller when inlining EDGE.
 341    Only to be called via estimate_edge_size.  */
 342
 343 ipa_hints
 344 do_estimate_edge_hints (struct cgraph_edge *edge)
 345 {
 346   ipa_hints hints;
 347   struct cgraph_node *callee;
 348   clause_t clause, nonspec_clause;
 349   auto_vec<tree, 32> known_vals;
 350   auto_vec<ipa_polymorphic_call_context, 32> known_contexts;
 351   auto_vec<ipa_agg_value_set, 32> known_aggs;
 352
 353   /* When we do caching, use do_estimate_edge_time to populate the entry.  */
 354
 355   if (edge_growth_cache != NULL)
 356     {
 357       do_estimate_edge_time (edge);
 358       hints = edge_growth_cache->get (edge)->hints;
 359       gcc_checking_assert (hints);
 360       return hints - 1;
 361     }
 362
 363   callee = edge->callee->ultimate_alias_target ();
 364
 365   /* Early inliner runs without caching, go ahead and do the dirty work.  */
 366   gcc_checking_assert (edge->inline_failed);
 367   evaluate_properties_for_edge (edge, true,
 368                                 &clause, &nonspec_clause,
 369                                 &known_vals, &known_contexts,
 370                                 &known_aggs);
 371   ipa_call_context ctx (callee, clause, nonspec_clause, known_vals,
 372                         known_contexts, known_aggs, vNULL);
 373   ctx.estimate_size_and_time (NULL, NULL, NULL, NULL, &hints);
 374   ctx.release ();
 375   hints |= simple_edge_hints (edge);
 376   return hints;
 377 }
 378
 379 /* Estimate the size of NODE after inlining EDGE which should be an
 380    edge to either NODE or a call inlined into NODE.  */
 381
 382 int
 383 estimate_size_after_inlining (struct cgraph_node *node,
 384                               struct cgraph_edge *edge)
 385 {
 386   class ipa_call_summary *es = ipa_call_summaries->get (edge);
 387   ipa_size_summary *s = ipa_size_summaries->get (node);
 388   if (!es->predicate || *es->predicate != false)
 389     {
 390       int size = s->size + estimate_edge_growth (edge);
 391       gcc_assert (size >= 0);
 392       return size;
 393     }
 394   return s->size;
 395 }
 396
 397
 398 struct growth_data
 399 {
 400   struct cgraph_node *node;
 401   bool self_recursive;
 402   bool uninlinable;
 403   int growth;
 404   int cap;
 405 };
 406
 407
 408 /* Worker for do_estimate_growth.  Collect growth for all callers.  */
 409
 410 static bool
 411 do_estimate_growth_1 (struct cgraph_node *node, void *data)
 412 {
 413   struct cgraph_edge *e;
 414   struct growth_data *d = (struct growth_data *) data;
 415
 416   for (e = node->callers; e; e = e->next_caller)
 417     {
 418       gcc_checking_assert (e->inline_failed);
 419
 420       if (cgraph_inline_failed_type (e->inline_failed) == CIF_FINAL_ERROR
 421           || !opt_for_fn (e->caller->decl, optimize))
 422         {
 423           d->uninlinable = true;
 424           if (d->cap < INT_MAX)
 425             return true;
 426           continue;
 427         }
 428
 429       if (e->recursive_p ())
 430         {
 431           d->self_recursive = true;
 432           if (d->cap < INT_MAX)
 433             return true;
 434           continue;
 435         }
 436       d->growth += estimate_edge_growth (e);
 437       if (d->growth > d->cap)
 438         return true;
 439     }
 440   return false;
 441 }
 442
 443 /* Return estimated savings for eliminating offline copy of NODE by inlining
 444    it everywhere.  */
 445
 446 static int
 447 offline_size (struct cgraph_node *node, ipa_size_summary *info)
 448 {
 449   if (!DECL_EXTERNAL (node->decl))
 450     {
 451       if (node->will_be_removed_from_program_if_no_direct_calls_p ())
 452         return info->size;
 453       /* COMDAT functions are very often not shared across multiple units
 454          since they come from various template instantiations.
 455          Take this into account.  */
 456       else if (DECL_COMDAT (node->decl)
 457                && node->can_remove_if_no_direct_calls_p ())
 458         {
 459           int prob = opt_for_fn (node->decl, param_comdat_sharing_probability);
 460           return (info->size * (100 - prob) + 50) / 100;
 461         }
 462     }
 463   return 0;
 464 }
 465
 466 /* Estimate the growth caused by inlining NODE into all callers.  */
 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 }