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 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         return (info->size
 459                 * (100 - param_comdat_sharing_probability)
 460                 + 50) / 100;
 461     }
 462   return 0;
 463 }
 464
 465 /* Estimate the growth caused by inlining NODE into all callees.  */
 466
 467 int
 468 estimate_growth (struct cgraph_node *node)
 469 {
 470   struct growth_data d = { node, false, false, 0, INT_MAX };
 471   ipa_size_summary *info = ipa_size_summaries->get (node);
 472
 473   if (node->call_for_symbol_and_aliases (do_estimate_growth_1, &d, true))
 474     return 1;
 475
 476   /* For self recursive functions the growth estimation really should be
 477      infinity.  We don't want to return very large values because the growth
 478      plays various roles in badness computation fractions.  Be sure to not
 479      return zero or negative growths. */
 480   if (d.self_recursive)
 481     d.growth = d.growth < info->size ? info->size : d.growth;
 482   else if (!d.uninlinable)
 483     d.growth -= offline_size (node, info);
 484
 485   return d.growth;
 486 }
 487
 488 /* Verify if there are fewer than MAX_CALLERS.  */
 489
 490 static bool
 491 check_callers (cgraph_node *node, int *growth, int *n, int offline,
 492                int min_size, struct cgraph_edge *known_edge)
 493 {
 494   ipa_ref *ref;
 495
 496   if (!node->can_remove_if_no_direct_calls_and_refs_p ())
 497     return true;
 498
 499   for (cgraph_edge *e = node->callers; e; e = e->next_caller)
 500     {
 501       edge_growth_cache_entry *entry;
 502
 503       if (e == known_edge)
 504         continue;
 505       if (cgraph_inline_failed_type (e->inline_failed) == CIF_FINAL_ERROR)
 506         return true;
 507       if (edge_growth_cache != NULL
 508           && (entry = edge_growth_cache->get (e)) != NULL
 509           && entry->size != 0)
 510         *growth += entry->size - (entry->size > 0);
 511       else
 512         {
 513           class ipa_call_summary *es = ipa_call_summaries->get (e);
 514           if (!es)
 515             return true;
 516           *growth += min_size - es->call_stmt_size;
 517           if (--(*n) < 0)
 518             return false;
 519         }
 520       if (*growth > offline)
 521         return true;
 522     }
 523
 524   if (*n > 0)
 525     FOR_EACH_ALIAS (node, ref)
 526       if (check_callers (dyn_cast <cgraph_node *> (ref->referring), growth, n,
 527                          offline, min_size, known_edge))
 528         return true;
 529
 530   return false;
 531 }
 532
 533
 534 /* Decide if growth of NODE is positive.  This is cheaper than calculating
 535    actual growth.  If edge growth of KNOWN_EDGE is known
 536    it is passed by EDGE_GROWTH.  */
 537
 538 bool
 539 growth_positive_p (struct cgraph_node *node,
 540                    struct cgraph_edge * known_edge, int edge_growth)
 541 {
 542   struct cgraph_edge *e;
 543
 544   ipa_size_summary *s = ipa_size_summaries->get (node);
 545
 546   /* First quickly check if NODE is removable at all.  */
 547   int offline = offline_size (node, s);
 548   if (offline <= 0 && known_edge && edge_growth > 0)
 549     return true;
 550
 551   int min_size = ipa_fn_summaries->get (node)->min_size;
 552   int n = 10;
 553
 554   int min_growth = known_edge ? edge_growth : 0;
 555   for (e = node->callers; e; e = e->next_caller)
 556     {
 557       edge_growth_cache_entry *entry;
 558
 559       if (cgraph_inline_failed_type (e->inline_failed) == CIF_FINAL_ERROR)
 560         return true;
 561       if (e == known_edge)
 562         continue;
 563       if (edge_growth_cache != NULL
 564           && (entry = edge_growth_cache->get (e)) != NULL
 565           && entry->size != 0)
 566         min_growth += entry->size - (entry->size > 0);
 567       else
 568         {
 569           class ipa_call_summary *es = ipa_call_summaries->get (e);
 570           if (!es)
 571             return true;
 572           min_growth += min_size - es->call_stmt_size;
 573           if (--n <= 0)
 574             break;
 575         }
 576       if (min_growth > offline)
 577         return true;
 578     }
 579
 580   ipa_ref *ref;
 581   if (n > 0)
 582     FOR_EACH_ALIAS (node, ref)
 583       if (check_callers (dyn_cast <cgraph_node *> (ref->referring),
 584                          &min_growth, &n, offline, min_size, known_edge))
 585         return true;
 586
 587   struct growth_data d = { node, false, false, 0, offline };
 588   if (node->call_for_symbol_and_aliases (do_estimate_growth_1, &d, true))
 589     return true;
 590   if (d.self_recursive || d.uninlinable)
 591     return true;
 592   return (d.growth > offline);
 593 }