/* Analysis used by inlining decision heuristics.
- Copyright (C) 2003-2019 Free Software Foundation, Inc.
+ Copyright (C) 2003-2020 Free Software Foundation, Inc.
Contributed by Jan Hubicka
This file is part of GCC.
#include "print-tree.h"
#include "tree-inline.h"
#include "gimple-pretty-print.h"
-#include "params.h"
#include "cfganal.h"
#include "gimple-iterator.h"
#include "tree-cfg.h"
#include "gimplify.h"
/* Cached node/edge growths. */
-call_summary<edge_growth_cache_entry *> *edge_growth_cache = NULL;
+fast_call_summary<edge_growth_cache_entry *, va_heap> *edge_growth_cache = NULL;
+
+/* The context cache remembers estimated time/size and hints for given
+ ipa_call_context of a call. */
+class node_context_cache_entry
+{
+public:
+ ipa_call_context ctx;
+ sreal time, nonspec_time;
+ int size;
+ ipa_hints hints;
+
+ node_context_cache_entry ()
+ : ctx ()
+ {
+ }
+ ~node_context_cache_entry ()
+ {
+ ctx.release ();
+ }
+};
+
+/* At the moment we implement primitive single entry LRU cache. */
+class node_context_summary
+{
+public:
+ node_context_cache_entry entry;
+
+ node_context_summary ()
+ : entry ()
+ {
+ }
+ ~node_context_summary ()
+ {
+ }
+};
+
+/* Summary holding the context cache. */
+static fast_function_summary <node_context_summary *, va_heap>
+ *node_context_cache = NULL;
+/* Statistics about the context cache effectivity. */
+static long node_context_cache_hit, node_context_cache_miss,
+ node_context_cache_clear;
/* Give initial reasons why inlining would fail on EDGE. This gets either
nullified or usually overwritten by more precise reasons later. */
== CIF_FINAL_ERROR);
}
+/* Allocate edge growth caches. */
+
+void
+initialize_growth_caches ()
+{
+ edge_growth_cache
+ = new fast_call_summary<edge_growth_cache_entry *, va_heap> (symtab);
+ node_context_cache
+ = new fast_function_summary<node_context_summary *, va_heap> (symtab);
+}
/* Free growth caches. */
free_growth_caches (void)
{
delete edge_growth_cache;
+ delete node_context_cache;
edge_growth_cache = NULL;
+ node_context_cache = NULL;
+ if (dump_file)
+ fprintf (dump_file, "node context cache: %li hits, %li misses,"
+ " %li initializations\n",
+ node_context_cache_hit, node_context_cache_miss,
+ node_context_cache_clear);
+ node_context_cache_hit = 0;
+ node_context_cache_miss = 0;
+ node_context_cache_clear = 0;
}
-/* Return hints derrived from EDGE. */
+/* Return hints derived from EDGE. */
int
simple_edge_hints (struct cgraph_edge *edge)
if (to_scc_no && to_scc_no == callee_scc_no && !edge->recursive_p ())
hints |= INLINE_HINT_same_scc;
- if (callee->lto_file_data && edge->caller->lto_file_data
- && edge->caller->lto_file_data != callee->lto_file_data
- && !callee->merged_comdat && !callee->icf_merged)
+ if (cross_module_call_p (edge))
hints |= INLINE_HINT_cross_module;
return hints;
size, since we always need both metrics eventually. */
sreal
-do_estimate_edge_time (struct cgraph_edge *edge)
+do_estimate_edge_time (struct cgraph_edge *edge, sreal *ret_nonspec_time)
{
sreal time, nonspec_time;
int size;
ipa_hints hints;
struct cgraph_node *callee;
clause_t clause, nonspec_clause;
- vec<tree> known_vals;
- vec<ipa_polymorphic_call_context> known_contexts;
- vec<ipa_agg_jump_function_p> known_aggs;
+ auto_vec<tree, 32> known_vals;
+ auto_vec<ipa_polymorphic_call_context, 32> known_contexts;
+ auto_vec<ipa_agg_value_set, 32> known_aggs;
class ipa_call_summary *es = ipa_call_summaries->get (edge);
- int min_size;
+ int min_size = -1;
callee = edge->callee->ultimate_alias_target ();
evaluate_properties_for_edge (edge, true,
&clause, &nonspec_clause, &known_vals,
&known_contexts, &known_aggs);
- estimate_node_size_and_time (callee, clause, nonspec_clause, known_vals,
- known_contexts, known_aggs, &size, &min_size,
- &time, &nonspec_time, &hints, es->param);
+ ipa_call_context ctx (callee, clause, nonspec_clause, known_vals,
+ known_contexts, known_aggs, es->param);
+ if (node_context_cache != NULL)
+ {
+ node_context_summary *e = node_context_cache->get_create (callee);
+ if (e->entry.ctx.equal_to (ctx))
+ {
+ node_context_cache_hit++;
+ size = e->entry.size;
+ time = e->entry.time;
+ nonspec_time = e->entry.nonspec_time;
+ hints = e->entry.hints;
+ if (flag_checking
+ && !opt_for_fn (callee->decl, flag_profile_partial_training)
+ && !callee->count.ipa_p ())
+ {
+ sreal chk_time, chk_nonspec_time;
+ int chk_size, chk_min_size;
+
+ ipa_hints chk_hints;
+ ctx.estimate_size_and_time (&chk_size, &chk_min_size,
+ &chk_time, &chk_nonspec_time,
+ &chk_hints);
+ gcc_assert (chk_size == size && chk_time == time
+ && chk_nonspec_time == nonspec_time
+ && chk_hints == hints);
+ }
+ }
+ else
+ {
+ if (e->entry.ctx.exists_p ())
+ node_context_cache_miss++;
+ else
+ node_context_cache_clear++;
+ e->entry.ctx.release (true);
+ ctx.estimate_size_and_time (&size, &min_size,
+ &time, &nonspec_time, &hints);
+ e->entry.size = size;
+ e->entry.time = time;
+ e->entry.nonspec_time = nonspec_time;
+ e->entry.hints = hints;
+ e->entry.ctx.duplicate_from (ctx);
+ }
+ }
+ else
+ ctx.estimate_size_and_time (&size, &min_size,
+ &time, &nonspec_time, &hints);
/* When we have profile feedback, we can quite safely identify hot
edges and for those we disable size limits. Don't do that when
: edge->caller->count.ipa ())))
hints |= INLINE_HINT_known_hot;
- known_vals.release ();
- known_contexts.release ();
- known_aggs.release ();
+ ctx.release ();
gcc_checking_assert (size >= 0);
gcc_checking_assert (time >= 0);
/* When caching, update the cache entry. */
if (edge_growth_cache != NULL)
{
- ipa_fn_summaries->get (edge->callee->function_symbol ())->min_size
- = min_size;
+ if (min_size >= 0)
+ ipa_fn_summaries->get (edge->callee->function_symbol ())->min_size
+ = min_size;
edge_growth_cache_entry *entry
= edge_growth_cache->get_create (edge);
entry->time = time;
hints |= simple_edge_hints (edge);
entry->hints = hints + 1;
}
+ if (ret_nonspec_time)
+ *ret_nonspec_time = nonspec_time;
return time;
}
+/* Reset cache for NODE.
+ This must be done each time NODE body is modified. */
+void
+reset_node_cache (struct cgraph_node *node)
+{
+ if (node_context_cache)
+ node_context_cache->remove (node);
+}
+
+/* Remove EDGE from caches once it was inlined. */
+void
+ipa_remove_from_growth_caches (struct cgraph_edge *edge)
+{
+ if (node_context_cache)
+ node_context_cache->remove (edge->callee);
+ if (edge_growth_cache)
+ edge_growth_cache->remove (edge);
+}
/* Return estimated callee growth after inlining EDGE.
Only to be called via estimate_edge_size. */
int size;
struct cgraph_node *callee;
clause_t clause, nonspec_clause;
- vec<tree> known_vals;
- vec<ipa_polymorphic_call_context> known_contexts;
- vec<ipa_agg_jump_function_p> known_aggs;
+ auto_vec<tree, 32> known_vals;
+ auto_vec<ipa_polymorphic_call_context, 32> known_contexts;
+ auto_vec<ipa_agg_value_set, 32> known_aggs;
/* When we do caching, use do_estimate_edge_time to populate the entry. */
&clause, &nonspec_clause,
&known_vals, &known_contexts,
&known_aggs);
- estimate_node_size_and_time (callee, clause, nonspec_clause, known_vals,
- known_contexts, known_aggs, &size, NULL, NULL,
- NULL, NULL, vNULL);
- known_vals.release ();
- known_contexts.release ();
- known_aggs.release ();
+ ipa_call_context ctx (callee, clause, nonspec_clause, known_vals,
+ known_contexts, known_aggs, vNULL);
+ ctx.estimate_size_and_time (&size, NULL, NULL, NULL, NULL);
+ ctx.release ();
return size;
}
ipa_hints hints;
struct cgraph_node *callee;
clause_t clause, nonspec_clause;
- vec<tree> known_vals;
- vec<ipa_polymorphic_call_context> known_contexts;
- vec<ipa_agg_jump_function_p> known_aggs;
+ auto_vec<tree, 32> known_vals;
+ auto_vec<ipa_polymorphic_call_context, 32> known_contexts;
+ auto_vec<ipa_agg_value_set, 32> known_aggs;
/* When we do caching, use do_estimate_edge_time to populate the entry. */
&clause, &nonspec_clause,
&known_vals, &known_contexts,
&known_aggs);
- estimate_node_size_and_time (callee, clause, nonspec_clause, known_vals,
- known_contexts, known_aggs, NULL, NULL,
- NULL, NULL, &hints, vNULL);
- known_vals.release ();
- known_contexts.release ();
- known_aggs.release ();
+ ipa_call_context ctx (callee, clause, nonspec_clause, known_vals,
+ known_contexts, known_aggs, vNULL);
+ ctx.estimate_size_and_time (NULL, NULL, NULL, NULL, &hints);
+ ctx.release ();
hints |= simple_edge_hints (edge);
return hints;
}
bool self_recursive;
bool uninlinable;
int growth;
+ int cap;
};
|| !opt_for_fn (e->caller->decl, optimize))
{
d->uninlinable = true;
+ if (d->cap < INT_MAX)
+ return true;
continue;
}
if (e->recursive_p ())
{
d->self_recursive = true;
+ if (d->cap < INT_MAX)
+ return true;
continue;
}
d->growth += estimate_edge_growth (e);
+ if (d->growth > d->cap)
+ return true;
}
return false;
}
+/* Return estimated savings for eliminating offline copy of NODE by inlining
+ it everywhere. */
+
+static int
+offline_size (struct cgraph_node *node, ipa_size_summary *info)
+{
+ if (!DECL_EXTERNAL (node->decl))
+ {
+ if (node->will_be_removed_from_program_if_no_direct_calls_p ())
+ return info->size;
+ /* COMDAT functions are very often not shared across multiple units
+ since they come from various template instantiations.
+ Take this into account. */
+ else if (DECL_COMDAT (node->decl)
+ && node->can_remove_if_no_direct_calls_p ())
+ {
+ int prob = opt_for_fn (node->decl, param_comdat_sharing_probability);
+ return (info->size * (100 - prob) + 50) / 100;
+ }
+ }
+ return 0;
+}
-/* Estimate the growth caused by inlining NODE into all callees. */
+/* Estimate the growth caused by inlining NODE into all callers. */
int
estimate_growth (struct cgraph_node *node)
{
- struct growth_data d = { node, false, false, 0 };
- class ipa_size_summary *info = ipa_size_summaries->get (node);
+ struct growth_data d = { node, false, false, 0, INT_MAX };
+ ipa_size_summary *info = ipa_size_summaries->get (node);
- node->call_for_symbol_and_aliases (do_estimate_growth_1, &d, true);
+ if (node->call_for_symbol_and_aliases (do_estimate_growth_1, &d, true))
+ return 1;
/* For self recursive functions the growth estimation really should be
infinity. We don't want to return very large values because the growth
return zero or negative growths. */
if (d.self_recursive)
d.growth = d.growth < info->size ? info->size : d.growth;
- else if (DECL_EXTERNAL (node->decl) || d.uninlinable)
- ;
- else
- {
- if (node->will_be_removed_from_program_if_no_direct_calls_p ())
- d.growth -= info->size;
- /* COMDAT functions are very often not shared across multiple units
- since they come from various template instantiations.
- Take this into account. */
- else if (DECL_COMDAT (node->decl)
- && node->can_remove_if_no_direct_calls_p ())
- d.growth -= (info->size
- * (100 - PARAM_VALUE (PARAM_COMDAT_SHARING_PROBABILITY))
- + 50) / 100;
- }
+ else if (!d.uninlinable)
+ d.growth -= offline_size (node, info);
return d.growth;
}
/* Verify if there are fewer than MAX_CALLERS. */
static bool
-check_callers (cgraph_node *node, int *max_callers)
+check_callers (cgraph_node *node, int *growth, int *n, int offline,
+ int min_size, struct cgraph_edge *known_edge)
{
ipa_ref *ref;
for (cgraph_edge *e = node->callers; e; e = e->next_caller)
{
- (*max_callers)--;
- if (!*max_callers
- || cgraph_inline_failed_type (e->inline_failed) == CIF_FINAL_ERROR)
+ edge_growth_cache_entry *entry;
+
+ if (e == known_edge)
+ continue;
+ if (cgraph_inline_failed_type (e->inline_failed) == CIF_FINAL_ERROR)
+ return true;
+ if (edge_growth_cache != NULL
+ && (entry = edge_growth_cache->get (e)) != NULL
+ && entry->size != 0)
+ *growth += entry->size - (entry->size > 0);
+ else
+ {
+ class ipa_call_summary *es = ipa_call_summaries->get (e);
+ if (!es)
+ return true;
+ *growth += min_size - es->call_stmt_size;
+ if (--(*n) < 0)
+ return false;
+ }
+ if (*growth > offline)
return true;
}
- FOR_EACH_ALIAS (node, ref)
- if (check_callers (dyn_cast <cgraph_node *> (ref->referring), max_callers))
- return true;
+ if (*n > 0)
+ FOR_EACH_ALIAS (node, ref)
+ if (check_callers (dyn_cast <cgraph_node *> (ref->referring), growth, n,
+ offline, min_size, known_edge))
+ return true;
return false;
}
-/* Make cheap estimation if growth of NODE is likely positive knowing
- EDGE_GROWTH of one particular edge.
- We assume that most of other edges will have similar growth
- and skip computation if there are too many callers. */
+/* Decide if growth of NODE is positive. This is cheaper than calculating
+ actual growth. If edge growth of KNOWN_EDGE is known
+ it is passed by EDGE_GROWTH. */
bool
-growth_likely_positive (struct cgraph_node *node,
- int edge_growth)
+growth_positive_p (struct cgraph_node *node,
+ struct cgraph_edge * known_edge, int edge_growth)
{
- int max_callers;
struct cgraph_edge *e;
- gcc_checking_assert (edge_growth > 0);
+
+ ipa_size_summary *s = ipa_size_summaries->get (node);
/* First quickly check if NODE is removable at all. */
- if (DECL_EXTERNAL (node->decl))
- return true;
- if (!node->can_remove_if_no_direct_calls_and_refs_p ()
- || node->address_taken)
+ int offline = offline_size (node, s);
+ if (offline <= 0 && known_edge && edge_growth > 0)
return true;
- max_callers = ipa_size_summaries->get (node)->size * 4 / edge_growth + 2;
+ int min_size = ipa_fn_summaries->get (node)->min_size;
+ int n = 10;
+ int min_growth = known_edge ? edge_growth : 0;
for (e = node->callers; e; e = e->next_caller)
{
- max_callers--;
- if (!max_callers
- || cgraph_inline_failed_type (e->inline_failed) == CIF_FINAL_ERROR)
+ edge_growth_cache_entry *entry;
+
+ if (cgraph_inline_failed_type (e->inline_failed) == CIF_FINAL_ERROR)
+ return true;
+ if (e == known_edge)
+ continue;
+ if (edge_growth_cache != NULL
+ && (entry = edge_growth_cache->get (e)) != NULL
+ && entry->size != 0)
+ min_growth += entry->size - (entry->size > 0);
+ else
+ {
+ class ipa_call_summary *es = ipa_call_summaries->get (e);
+ if (!es)
+ return true;
+ min_growth += min_size - es->call_stmt_size;
+ if (--n <= 0)
+ break;
+ }
+ if (min_growth > offline)
return true;
}
ipa_ref *ref;
- FOR_EACH_ALIAS (node, ref)
- if (check_callers (dyn_cast <cgraph_node *> (ref->referring), &max_callers))
- return true;
-
- /* Unlike for functions called once, we play unsafe with
- COMDATs. We can allow that since we know functions
- in consideration are small (and thus risk is small) and
- moreover grow estimates already accounts that COMDAT
- functions may or may not disappear when eliminated from
- current unit. With good probability making aggressive
- choice in all units is going to make overall program
- smaller. */
- if (DECL_COMDAT (node->decl))
- {
- if (!node->can_remove_if_no_direct_calls_p ())
+ if (n > 0)
+ FOR_EACH_ALIAS (node, ref)
+ if (check_callers (dyn_cast <cgraph_node *> (ref->referring),
+ &min_growth, &n, offline, min_size, known_edge))
return true;
- }
- else if (!node->will_be_removed_from_program_if_no_direct_calls_p ())
- return true;
- return estimate_growth (node) > 0;
+ struct growth_data d = { node, false, false, 0, offline };
+ if (node->call_for_symbol_and_aliases (do_estimate_growth_1, &d, true))
+ return true;
+ if (d.self_recursive || d.uninlinable)
+ return true;
+ return (d.growth > offline);
}
projects / gcc.git / blobdiff