gcc/ipa-inline-analysis.c

   1 /* Analysis used by inlining decision heuristics.
   2    Copyright (C) 2003-2018 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 "params.h"
  38 #include "cfganal.h"
  39 #include "gimple-iterator.h"
  40 #include "tree-cfg.h"
  41 #include "tree-ssa-loop-niter.h"
  42 #include "tree-ssa-loop.h"
  43 #include "symbol-summary.h"
  44 #include "ipa-prop.h"
  45 #include "ipa-fnsummary.h"
  46 #include "ipa-inline.h"
  47 #include "cfgloop.h"
  48 #include "tree-scalar-evolution.h"
  49 #include "ipa-utils.h"
  50 #include "cfgexpand.h"
  51 #include "gimplify.h"
  52
  53 /* Cached node/edge growths.  */
  54 call_summary<edge_growth_cache_entry *> *edge_growth_cache = NULL;
  55
  56 /* Give initial reasons why inlining would fail on EDGE.  This gets either
  57    nullified or usually overwritten by more precise reasons later.  */
  58
  59 void
  60 initialize_inline_failed (struct cgraph_edge *e)
  61 {
  62   struct cgraph_node *callee = e->callee;
  63
  64   if (e->inline_failed && e->inline_failed != CIF_BODY_NOT_AVAILABLE
  65       && cgraph_inline_failed_type (e->inline_failed) == CIF_FINAL_ERROR)
  66     ;
  67   else if (e->indirect_unknown_callee)
  68     e->inline_failed = CIF_INDIRECT_UNKNOWN_CALL;
  69   else if (!callee->definition)
  70     e->inline_failed = CIF_BODY_NOT_AVAILABLE;
  71   else if (callee->local.redefined_extern_inline)
  72     e->inline_failed = CIF_REDEFINED_EXTERN_INLINE;
  73   else
  74     e->inline_failed = CIF_FUNCTION_NOT_CONSIDERED;
  75   gcc_checking_assert (!e->call_stmt_cannot_inline_p
  76                        || cgraph_inline_failed_type (e->inline_failed)
  77                             == CIF_FINAL_ERROR);
  78 }
  79
  80
  81 /* Free growth caches.  */
  82
  83 void
  84 free_growth_caches (void)
  85 {
  86   delete edge_growth_cache;
  87   edge_growth_cache = NULL;
  88 }
  89
  90 /* Return hints derrived from EDGE.   */
  91
  92 int
  93 simple_edge_hints (struct cgraph_edge *edge)
  94 {
  95   int hints = 0;
  96   struct cgraph_node *to = (edge->caller->global.inlined_to
  97                             ? edge->caller->global.inlined_to : edge->caller);
  98   struct cgraph_node *callee = edge->callee->ultimate_alias_target ();
  99   int to_scc_no = ipa_fn_summaries->get (to)->scc_no;
 100   int callee_scc_no = ipa_fn_summaries->get (callee)->scc_no;
 101
 102   if (to_scc_no && to_scc_no  == callee_scc_no && !edge->recursive_p ())
 103     hints |= INLINE_HINT_same_scc;
 104
 105   if (callee->lto_file_data && edge->caller->lto_file_data
 106       && edge->caller->lto_file_data != callee->lto_file_data
 107       && !callee->merged_comdat && !callee->icf_merged)
 108     hints |= INLINE_HINT_cross_module;
 109
 110   return hints;
 111 }
 112
 113 /* Estimate the time cost for the caller when inlining EDGE.
 114    Only to be called via estimate_edge_time, that handles the
 115    caching mechanism.
 116
 117    When caching, also update the cache entry.  Compute both time and
 118    size, since we always need both metrics eventually.  */
 119
 120 sreal
 121 do_estimate_edge_time (struct cgraph_edge *edge)
 122 {
 123   sreal time, nonspec_time;
 124   int size;
 125   ipa_hints hints;
 126   struct cgraph_node *callee;
 127   clause_t clause, nonspec_clause;
 128   vec<tree> known_vals;
 129   vec<ipa_polymorphic_call_context> known_contexts;
 130   vec<ipa_agg_jump_function_p> known_aggs;
 131   struct ipa_call_summary *es = ipa_call_summaries->get (edge);
 132   int min_size;
 133
 134   callee = edge->callee->ultimate_alias_target ();
 135
 136   gcc_checking_assert (edge->inline_failed);
 137   evaluate_properties_for_edge (edge, true,
 138                                 &clause, &nonspec_clause, &known_vals,
 139                                 &known_contexts, &known_aggs);
 140   estimate_node_size_and_time (callee, clause, nonspec_clause, known_vals,
 141                                known_contexts, known_aggs, &size, &min_size,
 142                                &time, &nonspec_time, &hints, es->param);
 143
 144   /* When we have profile feedback, we can quite safely identify hot
 145      edges and for those we disable size limits.  Don't do that when
 146      probability that caller will call the callee is low however, since it
 147      may hurt optimization of the caller's hot path.  */
 148   if (edge->count.ipa ().initialized_p () && edge->maybe_hot_p ()
 149       && (edge->count.ipa ().apply_scale (2, 1)
 150           > (edge->caller->global.inlined_to
 151              ? edge->caller->global.inlined_to->count.ipa ()
 152              : edge->caller->count.ipa ())))
 153     hints |= INLINE_HINT_known_hot;
 154
 155   known_vals.release ();
 156   known_contexts.release ();
 157   known_aggs.release ();
 158   gcc_checking_assert (size >= 0);
 159   gcc_checking_assert (time >= 0);
 160
 161   /* When caching, update the cache entry.  */
 162   if (edge_growth_cache != NULL)
 163     {
 164       ipa_fn_summaries->get_create (edge->callee)->min_size = min_size;
 165       edge_growth_cache_entry *entry
 166         = edge_growth_cache->get_create (edge);
 167       entry->time = time;
 168       entry->nonspec_time = nonspec_time;
 169
 170       entry->size = size + (size >= 0);
 171       hints |= simple_edge_hints (edge);
 172       entry->hints = hints + 1;
 173     }
 174   return time;
 175 }
 176
 177
 178 /* Return estimated callee growth after inlining EDGE.
 179    Only to be called via estimate_edge_size.  */
 180
 181 int
 182 do_estimate_edge_size (struct cgraph_edge *edge)
 183 {
 184   int size;
 185   struct cgraph_node *callee;
 186   clause_t clause, nonspec_clause;
 187   vec<tree> known_vals;
 188   vec<ipa_polymorphic_call_context> known_contexts;
 189   vec<ipa_agg_jump_function_p> known_aggs;
 190
 191   /* When we do caching, use do_estimate_edge_time to populate the entry.  */
 192
 193   if (edge_growth_cache != NULL)
 194     {
 195       do_estimate_edge_time (edge);
 196       size = edge_growth_cache->get (edge)->size;
 197       gcc_checking_assert (size);
 198       return size - (size > 0);
 199     }
 200
 201   callee = edge->callee->ultimate_alias_target ();
 202
 203   /* Early inliner runs without caching, go ahead and do the dirty work.  */
 204   gcc_checking_assert (edge->inline_failed);
 205   evaluate_properties_for_edge (edge, true,
 206                                 &clause, &nonspec_clause,
 207                                 &known_vals, &known_contexts,
 208                                 &known_aggs);
 209   estimate_node_size_and_time (callee, clause, nonspec_clause, known_vals,
 210                                known_contexts, known_aggs, &size, NULL, NULL,
 211                                NULL, NULL, vNULL);
 212   known_vals.release ();
 213   known_contexts.release ();
 214   known_aggs.release ();
 215   return size;
 216 }
 217
 218
 219 /* Estimate the growth of the caller when inlining EDGE.
 220    Only to be called via estimate_edge_size.  */
 221
 222 ipa_hints
 223 do_estimate_edge_hints (struct cgraph_edge *edge)
 224 {
 225   ipa_hints hints;
 226   struct cgraph_node *callee;
 227   clause_t clause, nonspec_clause;
 228   vec<tree> known_vals;
 229   vec<ipa_polymorphic_call_context> known_contexts;
 230   vec<ipa_agg_jump_function_p> known_aggs;
 231
 232   /* When we do caching, use do_estimate_edge_time to populate the entry.  */
 233
 234   if (edge_growth_cache != NULL)
 235     {
 236       do_estimate_edge_time (edge);
 237       hints = edge_growth_cache->get (edge)->hints;
 238       gcc_checking_assert (hints);
 239       return hints - 1;
 240     }
 241
 242   callee = edge->callee->ultimate_alias_target ();
 243
 244   /* Early inliner runs without caching, go ahead and do the dirty work.  */
 245   gcc_checking_assert (edge->inline_failed);
 246   evaluate_properties_for_edge (edge, true,
 247                                 &clause, &nonspec_clause,
 248                                 &known_vals, &known_contexts,
 249                                 &known_aggs);
 250   estimate_node_size_and_time (callee, clause, nonspec_clause, known_vals,
 251                                known_contexts, known_aggs, NULL, NULL,
 252                                NULL, NULL, &hints, vNULL);
 253   known_vals.release ();
 254   known_contexts.release ();
 255   known_aggs.release ();
 256   hints |= simple_edge_hints (edge);
 257   return hints;
 258 }
 259
 260 /* Estimate the size of NODE after inlining EDGE which should be an
 261    edge to either NODE or a call inlined into NODE.  */
 262
 263 int
 264 estimate_size_after_inlining (struct cgraph_node *node,
 265                               struct cgraph_edge *edge)
 266 {
 267   struct ipa_call_summary *es = ipa_call_summaries->get (edge);
 268   ipa_fn_summary *s = ipa_fn_summaries->get (node);
 269   if (!es->predicate || *es->predicate != false)
 270     {
 271       int size = s->size + estimate_edge_growth (edge);
 272       gcc_assert (size >= 0);
 273       return size;
 274     }
 275   return s->size;
 276 }
 277
 278
 279 struct growth_data
 280 {
 281   struct cgraph_node *node;
 282   bool self_recursive;
 283   bool uninlinable;
 284   int growth;
 285 };
 286
 287
 288 /* Worker for do_estimate_growth.  Collect growth for all callers.  */
 289
 290 static bool
 291 do_estimate_growth_1 (struct cgraph_node *node, void *data)
 292 {
 293   struct cgraph_edge *e;
 294   struct growth_data *d = (struct growth_data *) data;
 295
 296   for (e = node->callers; e; e = e->next_caller)
 297     {
 298       gcc_checking_assert (e->inline_failed);
 299
 300       if (cgraph_inline_failed_type (e->inline_failed) == CIF_FINAL_ERROR
 301           || !opt_for_fn (e->caller->decl, optimize))
 302         {
 303           d->uninlinable = true;
 304           continue;
 305         }
 306
 307       if (e->recursive_p ())
 308         {
 309           d->self_recursive = true;
 310           continue;
 311         }
 312       d->growth += estimate_edge_growth (e);
 313     }
 314   return false;
 315 }
 316
 317
 318 /* Estimate the growth caused by inlining NODE into all callees.  */
 319
 320 int
 321 estimate_growth (struct cgraph_node *node)
 322 {
 323   struct growth_data d = { node, false, false, 0 };
 324   struct ipa_fn_summary *info = ipa_fn_summaries->get (node);
 325
 326   node->call_for_symbol_and_aliases (do_estimate_growth_1, &d, true);
 327
 328   /* For self recursive functions the growth estimation really should be
 329      infinity.  We don't want to return very large values because the growth
 330      plays various roles in badness computation fractions.  Be sure to not
 331      return zero or negative growths. */
 332   if (d.self_recursive)
 333     d.growth = d.growth < info->size ? info->size : d.growth;
 334   else if (DECL_EXTERNAL (node->decl) || d.uninlinable)
 335     ;
 336   else
 337     {
 338       if (node->will_be_removed_from_program_if_no_direct_calls_p ())
 339         d.growth -= info->size;
 340       /* COMDAT functions are very often not shared across multiple units
 341          since they come from various template instantiations.
 342          Take this into account.  */
 343       else if (DECL_COMDAT (node->decl)
 344                && node->can_remove_if_no_direct_calls_p ())
 345         d.growth -= (info->size
 346                      * (100 - PARAM_VALUE (PARAM_COMDAT_SHARING_PROBABILITY))
 347                      + 50) / 100;
 348     }
 349
 350   return d.growth;
 351 }
 352
 353 /* Verify if there are fewer than MAX_CALLERS.  */
 354
 355 static bool
 356 check_callers (cgraph_node *node, int *max_callers)
 357 {
 358   ipa_ref *ref;
 359
 360   if (!node->can_remove_if_no_direct_calls_and_refs_p ())
 361     return true;
 362
 363   for (cgraph_edge *e = node->callers; e; e = e->next_caller)
 364     {
 365       (*max_callers)--;
 366       if (!*max_callers
 367           || cgraph_inline_failed_type (e->inline_failed) == CIF_FINAL_ERROR)
 368         return true;
 369     }
 370
 371   FOR_EACH_ALIAS (node, ref)
 372     if (check_callers (dyn_cast <cgraph_node *> (ref->referring), max_callers))
 373       return true;
 374
 375   return false;
 376 }
 377
 378
 379 /* Make cheap estimation if growth of NODE is likely positive knowing
 380    EDGE_GROWTH of one particular edge.
 381    We assume that most of other edges will have similar growth
 382    and skip computation if there are too many callers.  */
 383
 384 bool
 385 growth_likely_positive (struct cgraph_node *node,
 386                         int edge_growth)
 387 {
 388   int max_callers;
 389   struct cgraph_edge *e;
 390   gcc_checking_assert (edge_growth > 0);
 391
 392   /* First quickly check if NODE is removable at all.  */
 393   if (DECL_EXTERNAL (node->decl))
 394     return true;
 395   if (!node->can_remove_if_no_direct_calls_and_refs_p ()
 396       || node->address_taken)
 397     return true;
 398
 399   max_callers = ipa_fn_summaries->get (node)->size * 4 / edge_growth + 2;
 400
 401   for (e = node->callers; e; e = e->next_caller)
 402     {
 403       max_callers--;
 404       if (!max_callers
 405           || cgraph_inline_failed_type (e->inline_failed) == CIF_FINAL_ERROR)
 406         return true;
 407     }
 408
 409   ipa_ref *ref;
 410   FOR_EACH_ALIAS (node, ref)
 411     if (check_callers (dyn_cast <cgraph_node *> (ref->referring), &max_callers))
 412       return true;
 413
 414   /* Unlike for functions called once, we play unsafe with
 415      COMDATs.  We can allow that since we know functions
 416      in consideration are small (and thus risk is small) and
 417      moreover grow estimates already accounts that COMDAT
 418      functions may or may not disappear when eliminated from
 419      current unit. With good probability making aggressive
 420      choice in all units is going to make overall program
 421      smaller.  */
 422   if (DECL_COMDAT (node->decl))
 423     {
 424       if (!node->can_remove_if_no_direct_calls_p ())
 425         return true;
 426     }
 427   else if (!node->will_be_removed_from_program_if_no_direct_calls_p ())
 428     return true;
 429
 430   return estimate_growth (node) > 0;
 431 }