gcc/ipa-inline-analysis.c

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