/* IPA function body analysis.
- Copyright (C) 2003-2017 Free Software Foundation, Inc.
+ Copyright (C) 2003-2021 Free Software Foundation, Inc.
Contributed by Jan Hubicka
This file is part of GCC.
#include "ipa-predicate.h"
-/* Hints are reasons why IPA heuristics should preffer specializing given
- function. They are represtented as bitmap of the following values. */
+/* Hints are reasons why IPA heuristics should prefer specializing given
+ function. They are represented as bitmap of the following values. */
enum ipa_hints_vals {
/* When specialization turns indirect call into a direct call,
it is good idea to do so. */
INLINE_HINT_indirect_call = 1,
/* Inlining may make loop iterations or loop stride known. It is good idea
- to do so because it enables loop optimizatoins. */
+ to do so because it enables loop optimizations. */
INLINE_HINT_loop_iterations = 2,
INLINE_HINT_loop_stride = 4,
/* Inlining within same strongly connected component of callgraph is often
if functions are in different modules, inlining may not be so important.
Set by simple_edge_hints in ipa-inline-analysis.c. */
INLINE_HINT_cross_module = 64,
- /* If array indexes of loads/stores become known there may be room for
- further optimization. */
- INLINE_HINT_array_index = 128,
/* We know that the callee is hot by profile. */
- INLINE_HINT_known_hot = 256
+ INLINE_HINT_known_hot = 128,
+ /* There is builtin_constant_p dependent on parameter which is usually
+ a strong hint to inline. */
+ INLINE_HINT_builtin_constant_p = 256
};
typedef int ipa_hints;
/* Representation of function body size and time depending on the call
context. We keep simple array of record, every containing of predicate
and time/size to account. */
-struct GTY(()) size_time_entry
+class size_time_entry
{
+public:
/* Predicate for code to be executed. */
predicate exec_predicate;
/* Predicate for value to be constant and optimized out in a specialized copy.
the executed code paths will simplify. */
predicate nonconst_predicate;
int size;
- sreal GTY((skip)) time;
+ sreal time;
};
-/* Function inlining information. */
-struct GTY(()) ipa_fn_summary
+/* Summary about function and stack frame sizes. We keep this info
+ for inline clones and also for WPA streaming. For this reason this is not
+ part of ipa_fn_summary which exists only for offline functions. */
+class ipa_size_summary
{
- /* Information about the function body itself. */
-
+public:
/* Estimated stack frame consumption by the function. */
HOST_WIDE_INT estimated_self_stack_size;
/* Size of the function body. */
int self_size;
+ /* Estimated size of the function after inlining. */
+ int size;
+
+ ipa_size_summary ()
+ : estimated_self_stack_size (0), self_size (0), size (0)
+ {
+ }
+};
+
+/* Structure to capture how frequently some interesting events occur given a
+ particular predicate. The structure is used to estimate how often we
+ encounter loops with known iteration count or stride in various
+ contexts. */
+
+struct GTY(()) ipa_freqcounting_predicate
+{
+ /* The described event happens with this frequency... */
+ sreal freq;
+ /* ...when this predicate evaluates to false. */
+ class predicate * GTY((skip)) predicate;
+};
+
+/* Function inlining information. */
+class GTY(()) ipa_fn_summary
+{
+public:
+ /* Keep all field empty so summary dumping works during its computation.
+ This is useful for debugging. */
+ ipa_fn_summary ()
+ : min_size (0),
+ inlinable (false), single_caller (false),
+ fp_expressions (false),
+ estimated_stack_size (false),
+ time (0), conds (NULL),
+ size_time_table (), call_size_time_table (vNULL),
+ loop_iterations (NULL), loop_strides (NULL),
+ builtin_constant_p_parms (vNULL),
+ growth (0), scc_no (0)
+ {
+ }
+
+ /* Copy constructor. */
+ ipa_fn_summary (const ipa_fn_summary &s)
+ : min_size (s.min_size),
+ inlinable (s.inlinable), single_caller (s.single_caller),
+ fp_expressions (s.fp_expressions),
+ estimated_stack_size (s.estimated_stack_size),
+ time (s.time), conds (s.conds), size_time_table (),
+ call_size_time_table (vNULL),
+ loop_iterations (s.loop_iterations), loop_strides (s.loop_strides),
+ builtin_constant_p_parms (s.builtin_constant_p_parms),
+ growth (s.growth), scc_no (s.scc_no)
+ {}
+
+ /* Default constructor. */
+ ~ipa_fn_summary ();
+
+ /* Information about the function body itself. */
+
/* Minimal size increase after inlining. */
int min_size;
/* False when there something makes inlining impossible (such as va_arg). */
unsigned inlinable : 1;
- /* True when function contains cilk spawn (and thus we can not inline
- into it). */
- unsigned contains_cilk_spawn : 1;
/* True wen there is only one caller of the function before small function
inlining. */
unsigned int single_caller : 1;
/* Estimated stack frame consumption by the function. */
HOST_WIDE_INT estimated_stack_size;
- /* Expected offset of the stack frame of function. */
- HOST_WIDE_INT stack_frame_offset;
- /* Estimated size of the function after inlining. */
+ /* Estimated runtime of function after inlining. */
sreal GTY((skip)) time;
- int size;
/* Conditional size/time information. The summaries are being
merged during inlining. */
conditions conds;
- vec<size_time_entry, va_gc> *size_time_table;
-
- /* Predicate on when some loop in the function becomes to have known
- bounds. */
- predicate * GTY((skip)) loop_iterations;
- /* Predicate on when some loop in the function becomes to have known
- stride. */
- predicate * GTY((skip)) loop_stride;
- /* Predicate on when some array indexes become constants. */
- predicate * GTY((skip)) array_index;
+ /* Normal code is accounted in size_time_table, while calls are
+ accounted in call_size_time_table. This is because calls
+ are often adjusted by IPA optimizations and thus this summary
+ is generated from call summary information when needed. */
+ auto_vec<size_time_entry> GTY((skip)) size_time_table;
+ /* Unlike size_time_table that is initialized for all summaries
+ call_size_time_table is allocated only for functions with
+ many calls. Use effecient vl_ptr storage. */
+ vec<size_time_entry, va_heap, vl_ptr> GTY((skip)) call_size_time_table;
+
+ /* Predicates on when some loops in the function can have known bounds. */
+ vec<ipa_freqcounting_predicate, va_gc> *loop_iterations;
+ /* Predicates on when some loops in the function can have known strides. */
+ vec<ipa_freqcounting_predicate, va_gc> *loop_strides;
+ /* Parameters tested by builtin_constant_p. */
+ vec<int, va_heap, vl_ptr> GTY((skip)) builtin_constant_p_parms;
/* Estimated growth for inlining all copies of the function before start
of small functions inlining.
This value will get out of date as the callers are duplicated, but
/* Number of SCC on the beginning of inlining process. */
int scc_no;
- /* Keep all field empty so summary dumping works during its computation.
- This is useful for debugging. */
- ipa_fn_summary ()
- : estimated_self_stack_size (0), self_size (0), min_size (0),
- inlinable (false), contains_cilk_spawn (false), single_caller (false),
- fp_expressions (false), estimated_stack_size (false),
- stack_frame_offset (false), time (0), size (0), conds (NULL),
- size_time_table (NULL), loop_iterations (NULL), loop_stride (NULL),
- array_index (NULL), growth (0), scc_no (0)
- {
- }
-
/* Record time and size under given predicates. */
- void account_size_time (int, sreal, const predicate &, const predicate &);
-
- /* Reset summary to empty state. */
- void reset (struct cgraph_node *node);
+ void account_size_time (int, sreal, const predicate &, const predicate &,
+ bool call = false);
/* We keep values scaled up, so fractional sizes can be accounted. */
static const int size_scale = 2;
+ /* Maximal size of size_time_table before we start to be conservative. */
+ static const int max_size_time_table_size = 256;
};
-class GTY((user)) ipa_fn_summary_t: public function_summary <ipa_fn_summary *>
+class GTY((user)) ipa_fn_summary_t:
+ public fast_function_summary <ipa_fn_summary *, va_gc>
{
public:
- ipa_fn_summary_t (symbol_table *symtab, bool ggc):
- function_summary <ipa_fn_summary *> (symtab, ggc) {}
+ ipa_fn_summary_t (symbol_table *symtab):
+ fast_function_summary <ipa_fn_summary *, va_gc> (symtab) {}
static ipa_fn_summary_t *create_ggc (symbol_table *symtab)
{
- struct ipa_fn_summary_t *summary = new (ggc_alloc <ipa_fn_summary_t> ())
- ipa_fn_summary_t(symtab, true);
+ class ipa_fn_summary_t *summary
+ = new (ggc_alloc_no_dtor<ipa_fn_summary_t> ()) ipa_fn_summary_t (symtab);
summary->disable_insertion_hook ();
return summary;
}
+ /* Remove ipa_fn_summary for all callees of NODE. */
+ void remove_callees (cgraph_node *node);
virtual void insert (cgraph_node *, ipa_fn_summary *);
- virtual void remove (cgraph_node *node, ipa_fn_summary *);
+ virtual void remove (cgraph_node *node, ipa_fn_summary *)
+ {
+ remove_callees (node);
+ }
+
virtual void duplicate (cgraph_node *src, cgraph_node *dst,
ipa_fn_summary *src_data, ipa_fn_summary *dst_data);
};
-extern GTY(()) function_summary <ipa_fn_summary *> *ipa_fn_summaries;
+extern GTY(()) fast_function_summary <ipa_fn_summary *, va_gc>
+ *ipa_fn_summaries;
+
+class ipa_size_summary_t:
+ public fast_function_summary <ipa_size_summary *, va_heap>
+{
+public:
+ ipa_size_summary_t (symbol_table *symtab):
+ fast_function_summary <ipa_size_summary *, va_heap> (symtab)
+ {
+ disable_insertion_hook ();
+ }
+
+ virtual void duplicate (cgraph_node *, cgraph_node *,
+ ipa_size_summary *src_data,
+ ipa_size_summary *dst_data)
+ {
+ *dst_data = *src_data;
+ }
+};
+extern fast_function_summary <ipa_size_summary *, va_heap>
+ *ipa_size_summaries;
/* Information kept about callgraph edges. */
-struct ipa_call_summary
+class ipa_call_summary
{
+public:
+ /* Keep all field empty so summary dumping works during its computation.
+ This is useful for debugging. */
+ ipa_call_summary ()
+ : predicate (NULL), param (vNULL), call_stmt_size (0), call_stmt_time (0),
+ loop_depth (0), is_return_callee_uncaptured (false)
+ {
+ }
+
+ /* Copy constructor. */
+ ipa_call_summary (const ipa_call_summary &s):
+ predicate (s.predicate), param (s.param), call_stmt_size (s.call_stmt_size),
+ call_stmt_time (s.call_stmt_time), loop_depth (s.loop_depth),
+ is_return_callee_uncaptured (s.is_return_callee_uncaptured)
+ {
+ }
+
+ /* Default destructor. */
+ ~ipa_call_summary ();
+
class predicate *predicate;
/* Vector indexed by parameters. */
vec<inline_param_summary> param;
int call_stmt_time;
/* Depth of loop nest, 0 means no nesting. */
unsigned int loop_depth;
-
- /* Keep all field empty so summary dumping works during its computation.
- This is useful for debugging. */
- ipa_call_summary ()
- : predicate (NULL), param (vNULL), call_stmt_size (0), call_stmt_time (0),
- loop_depth (0)
- {
- }
-
- /* Reset inline summary to empty state. */
- void reset ();
+ /* Indicates whether the caller returns the value of it's callee. */
+ bool is_return_callee_uncaptured;
};
-class ipa_call_summary_t: public call_summary <ipa_call_summary *>
+class ipa_call_summary_t: public fast_call_summary <ipa_call_summary *, va_heap>
{
public:
- ipa_call_summary_t (symbol_table *symtab, bool ggc):
- call_summary <ipa_call_summary *> (symtab, ggc) {}
+ ipa_call_summary_t (symbol_table *symtab):
+ fast_call_summary <ipa_call_summary *, va_heap> (symtab) {}
/* Hook that is called by summary when an edge is duplicated. */
- virtual void remove (cgraph_edge *cs, ipa_call_summary *);
- /* Hook that is called by summary when an edge is duplicated. */
virtual void duplicate (cgraph_edge *src, cgraph_edge *dst,
ipa_call_summary *src_data,
ipa_call_summary *dst_data);
};
-extern call_summary <ipa_call_summary *> *ipa_call_summaries;
+/* Estimated execution times, code sizes and other information about the
+ code executing a call described by ipa_call_context. */
+
+struct ipa_call_estimates
+{
+ /* Estimated size needed to execute call in the given context. */
+ int size;
+
+ /* Minimal size needed for the call that is + independent on the call context
+ and can be used for fast estimates. */
+ int min_size;
+
+ /* Estimated time needed to execute call in the given context. */
+ sreal time;
+
+ /* Estimated time needed to execute the function when not ignoring
+ computations known to be constant in this context. */
+ sreal nonspecialized_time;
+
+ /* Further discovered reasons why to inline or specialize the give calls. */
+ ipa_hints hints;
+
+ /* Frequency how often a loop with known number of iterations is encountered.
+ Calculated with hints. */
+ sreal loops_with_known_iterations;
+
+ /* Frequency how often a loop with known strides is encountered. Calculated
+ with hints. */
+ sreal loops_with_known_strides;
+};
+
+class ipa_cached_call_context;
+
+/* This object describe a context of call. That is a summary of known
+ information about its parameters. Main purpose of this context is
+ to give more realistic estimations of function runtime, size and
+ inline hints. */
+class ipa_call_context
+{
+public:
+ ipa_call_context (cgraph_node *node,
+ clause_t possible_truths,
+ clause_t nonspec_possible_truths,
+ vec<inline_param_summary> inline_param_summary,
+ ipa_auto_call_arg_values *arg_values);
+ ipa_call_context ()
+ : m_node(NULL)
+ {
+ }
+ void estimate_size_and_time (ipa_call_estimates *estimates,
+ bool est_times = true, bool est_hints = true);
+ bool equal_to (const ipa_call_context &);
+ bool exists_p ()
+ {
+ return m_node != NULL;
+ }
+private:
+ /* Called function. */
+ cgraph_node *m_node;
+ /* Clause describing what predicate conditionals can be satisfied
+ in this context if function is inlined/specialized. */
+ clause_t m_possible_truths;
+ /* Clause describing what predicate conditionals can be satisfied
+ in this context if function is kept offline. */
+ clause_t m_nonspec_possible_truths;
+ /* Inline summary maintains info about change probabilities. */
+ vec<inline_param_summary> m_inline_param_summary;
+
+ /* Even after having calculated clauses, the information about argument
+ values is used to resolve indirect calls. */
+ ipa_call_arg_values m_avals;
+
+ friend ipa_cached_call_context;
+};
+
+/* Variant of ipa_call_context that is stored in a cache over a longer period
+ of time. */
+
+class ipa_cached_call_context : public ipa_call_context
+{
+public:
+ void duplicate_from (const ipa_call_context &ctx);
+ void release ();
+};
+
+extern fast_call_summary <ipa_call_summary *, va_heap> *ipa_call_summaries;
/* In ipa-fnsummary.c */
void ipa_debug_fn_summary (struct cgraph_node *);
void ipa_dump_fn_summaries (FILE *f);
void ipa_dump_fn_summary (FILE *f, struct cgraph_node *node);
void ipa_dump_hints (FILE *f, ipa_hints);
-void inline_generate_summary (void);
-void inline_read_summary (void);
-void inline_write_summary (void);
-void inline_free_summary (void);
+void ipa_free_fn_summary (void);
+void ipa_free_size_summary (void);
void inline_analyze_function (struct cgraph_node *node);
-void estimate_ipcp_clone_size_and_time (struct cgraph_node *,
- vec<tree>,
- vec<ipa_polymorphic_call_context>,
- vec<ipa_agg_jump_function_p>,
- int *, sreal *, sreal *,
- ipa_hints *);
+void estimate_ipcp_clone_size_and_time (struct cgraph_node *node,
+ ipa_auto_call_arg_values *avals,
+ ipa_call_estimates *estimates);
void ipa_merge_fn_summary_after_inlining (struct cgraph_edge *edge);
-void ipa_update_overall_fn_summary (struct cgraph_node *node);
+void ipa_update_overall_fn_summary (struct cgraph_node *node, bool reset = true);
void compute_fn_summary (struct cgraph_node *, bool);
+bool refs_local_or_readonly_memory_p (tree);
+bool points_to_local_or_readonly_memory_p (tree);
-void evaluate_properties_for_edge (struct cgraph_edge *e, bool inline_p,
+void evaluate_properties_for_edge (struct cgraph_edge *e,
+ bool inline_p,
clause_t *clause_ptr,
clause_t *nonspec_clause_ptr,
- vec<tree> *known_vals_ptr,
- vec<ipa_polymorphic_call_context>
- *known_contexts_ptr,
- vec<ipa_agg_jump_function_p> *);
-void estimate_node_size_and_time (struct cgraph_node *node,
- clause_t possible_truths,
- clause_t nonspec_possible_truths,
- vec<tree> known_vals,
- vec<ipa_polymorphic_call_context>,
- vec<ipa_agg_jump_function_p> known_aggs,
- int *ret_size, int *ret_min_size,
- sreal *ret_time,
- sreal *ret_nonspecialized_time,
- ipa_hints *ret_hints,
- vec<inline_param_summary>
- inline_param_summary);
+ ipa_auto_call_arg_values *avals,
+ bool compute_contexts);
+
+void ipa_fnsummary_c_finalize (void);
+HOST_WIDE_INT ipa_get_stack_frame_offset (struct cgraph_node *node);
+void ipa_remove_from_growth_caches (struct cgraph_edge *edge);
+
+/* Return true if EDGE is a cross module call. */
+
+static inline bool
+cross_module_call_p (struct cgraph_edge *edge)
+{
+ /* Here we do not want to walk to alias target becuase ICF may create
+ cross-unit aliases. */
+ if (edge->caller->unit_id == edge->callee->unit_id)
+ return false;
+ /* If the call is to a (former) comdat function or s symbol with mutiple
+ extern inline definitions then treat is as in-module call. */
+ if (edge->callee->merged_extern_inline || edge->callee->merged_comdat
+ || DECL_COMDAT (edge->callee->decl))
+ return false;
+ return true;
+}
#endif /* GCC_IPA_FNSUMMARY_H */