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         {
 331           d->uninlinable = true;
 332           continue;
 333         }
 334
 335       if (e->recursive_p ())
 336         {
 337           d->self_recursive = true;
 338           continue;
 339         }
 340       d->growth += estimate_edge_growth (e);
 341     }
 342   return false;
 343 }
 344
 345
 346 /* Estimate the growth caused by inlining NODE into all callees.  */
 347
 348 int
 349 estimate_growth (struct cgraph_node *node)
 350 {
 351   struct growth_data d = { node, false, false, 0 };
 352   struct ipa_fn_summary *info = ipa_fn_summaries->get (node);
 353
 354   node->call_for_symbol_and_aliases (do_estimate_growth_1, &d, true);
 355
 356   /* For self recursive functions the growth estimation really should be
 357      infinity.  We don't want to return very large values because the growth
 358      plays various roles in badness computation fractions.  Be sure to not
 359      return zero or negative growths. */
 360   if (d.self_recursive)
 361     d.growth = d.growth < info->size ? info->size : d.growth;
 362   else if (DECL_EXTERNAL (node->decl) || d.uninlinable)
 363     ;
 364   else
 365     {
 366       if (node->will_be_removed_from_program_if_no_direct_calls_p ())
 367         d.growth -= info->size;
 368       /* COMDAT functions are very often not shared across multiple units
 369          since they come from various template instantiations.
 370          Take this into account.  */
 371       else if (DECL_COMDAT (node->decl)
 372                && node->can_remove_if_no_direct_calls_p ())
 373         d.growth -= (info->size
 374                      * (100 - PARAM_VALUE (PARAM_COMDAT_SHARING_PROBABILITY))
 375                      + 50) / 100;
 376     }
 377
 378   return d.growth;
 379 }
 380
 381 /* Verify if there are fewer than MAX_CALLERS.  */
 382
 383 static bool
 384 check_callers (cgraph_node *node, int *max_callers)
 385 {
 386   ipa_ref *ref;
 387
 388   if (!node->can_remove_if_no_direct_calls_and_refs_p ())
 389     return true;
 390
 391   for (cgraph_edge *e = node->callers; e; e = e->next_caller)
 392     {
 393       (*max_callers)--;
 394       if (!*max_callers
 395           || cgraph_inline_failed_type (e->inline_failed) == CIF_FINAL_ERROR)
 396         return true;
 397     }
 398
 399   FOR_EACH_ALIAS (node, ref)
 400     if (check_callers (dyn_cast <cgraph_node *> (ref->referring), max_callers))
 401       return true;
 402
 403   return false;
 404 }
 405
 406
 407 /* Make cheap estimation if growth of NODE is likely positive knowing
 408    EDGE_GROWTH of one particular edge.
 409    We assume that most of other edges will have similar growth
 410    and skip computation if there are too many callers.  */
 411
 412 bool
 413 growth_likely_positive (struct cgraph_node *node,
 414                         int edge_growth)
 415 {
 416   int max_callers;
 417   struct cgraph_edge *e;
 418   gcc_checking_assert (edge_growth > 0);
 419
 420   /* First quickly check if NODE is removable at all.  */
 421   if (DECL_EXTERNAL (node->decl))
 422     return true;
 423   if (!node->can_remove_if_no_direct_calls_and_refs_p ()
 424       || node->address_taken)
 425     return true;
 426
 427   max_callers = ipa_fn_summaries->get (node)->size * 4 / edge_growth + 2;
 428
 429   for (e = node->callers; e; e = e->next_caller)
 430     {
 431       max_callers--;
 432       if (!max_callers
 433           || cgraph_inline_failed_type (e->inline_failed) == CIF_FINAL_ERROR)
 434         return true;
 435     }
 436
 437   ipa_ref *ref;
 438   FOR_EACH_ALIAS (node, ref)
 439     if (check_callers (dyn_cast <cgraph_node *> (ref->referring), &max_callers))
 440       return true;
 441
 442   /* Unlike for functions called once, we play unsafe with
 443      COMDATs.  We can allow that since we know functions
 444      in consideration are small (and thus risk is small) and
 445      moreover grow estimates already accounts that COMDAT
 446      functions may or may not disappear when eliminated from
 447      current unit. With good probability making aggressive
 448      choice in all units is going to make overall program
 449      smaller.  */
 450   if (DECL_COMDAT (node->decl))
 451     {
 452       if (!node->can_remove_if_no_direct_calls_p ())
 453         return true;
 454     }
 455   else if (!node->will_be_removed_from_program_if_no_direct_calls_p ())
 456     return true;
 457
 458   return estimate_growth (node) > 0;
 459 }