Daily bump.
[official-gcc.git] / gcc / ipa-inline.h
blob85041f67dd74a1a0a8bd6b9468578b817e38e540
1 /* Inlining decision heuristics.
2 Copyright (C) 2003-2015 Free Software Foundation, Inc.
3 Contributed by Jan Hubicka
5 This file is part of GCC.
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.
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.
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/>. */
21 #ifndef GCC_IPA_INLINE_H
22 #define GCC_IPA_INLINE_H
25 /* Representation of inline parameters that do depend on context function is
26 inlined into (i.e. known constant values of function parameters.
28 Conditions that are interesting for function body are collected into CONDS
29 vector. They are of simple for function_param OP VAL, where VAL is
30 IPA invariant. The conditions are then referred by predicates. */
32 struct GTY(()) condition
34 /* If agg_contents is set, this is the offset from which the used data was
35 loaded. */
36 HOST_WIDE_INT offset;
37 tree val;
38 int operand_num;
39 ENUM_BITFIELD(tree_code) code : 16;
40 /* Set if the used data were loaded from an aggregate parameter or from
41 data received by reference. */
42 unsigned agg_contents : 1;
43 /* If agg_contents is set, this differentiates between loads from data
44 passed by reference and by value. */
45 unsigned by_ref : 1;
48 /* Inline hints are reasons why inline heuristics should preffer inlining given
49 function. They are represtented as bitmap of the following values. */
50 enum inline_hints_vals {
51 /* When inlining turns indirect call into a direct call,
52 it is good idea to do so. */
53 INLINE_HINT_indirect_call = 1,
54 /* Inlining may make loop iterations or loop stride known. It is good idea
55 to do so because it enables loop optimizatoins. */
56 INLINE_HINT_loop_iterations = 2,
57 INLINE_HINT_loop_stride = 4,
58 /* Inlining within same strongly connected component of callgraph is often
59 a loss due to increased stack frame usage and prologue setup costs. */
60 INLINE_HINT_same_scc = 8,
61 /* Inlining functions in strongly connected component is not such a great
62 win. */
63 INLINE_HINT_in_scc = 16,
64 /* If function is declared inline by user, it may be good idea to inline
65 it. */
66 INLINE_HINT_declared_inline = 32,
67 /* Programs are usually still organized for non-LTO compilation and thus
68 if functions are in different modules, inlining may not be so important.
70 INLINE_HINT_cross_module = 64,
71 /* If array indexes of loads/stores become known there may be room for
72 further optimization. */
73 INLINE_HINT_array_index = 128,
74 /* We know that the callee is hot by profile. */
75 INLINE_HINT_known_hot = 256
77 typedef int inline_hints;
80 typedef vec<condition, va_gc> *conditions;
82 /* Representation of predicates i.e. formulas using conditions defined
83 above. Predicates are simple logical formulas in conjunctive-disjunctive
84 form.
86 Predicate is array of clauses terminated by 0. Every clause must be true
87 in order to make predicate true.
88 Clauses are represented as bitmaps of conditions. One of conditions
89 must be true in order for clause to be true. */
91 #define MAX_CLAUSES 8
92 typedef unsigned int clause_t;
93 struct GTY(()) predicate
95 clause_t clause[MAX_CLAUSES + 1];
98 /* Represnetation of function body size and time depending on the inline
99 context. We keep simple array of record, every containing of predicate
100 and time/size to account.
102 We keep values scaled up, so fractional sizes and times can be
103 accounted. */
104 #define INLINE_SIZE_SCALE 2
105 #define INLINE_TIME_SCALE (CGRAPH_FREQ_BASE * 2)
106 struct GTY(()) size_time_entry
108 struct predicate predicate;
109 int size;
110 int time;
113 /* Function inlining information. */
114 struct GTY(()) inline_summary
116 /* Information about the function body itself. */
118 /* Estimated stack frame consumption by the function. */
119 HOST_WIDE_INT estimated_self_stack_size;
120 /* Size of the function body. */
121 int self_size;
122 /* Time of the function body. */
123 int self_time;
124 /* Minimal size increase after inlining. */
125 int min_size;
127 /* False when there something makes inlining impossible (such as va_arg). */
128 unsigned inlinable : 1;
129 /* True when function contains cilk spawn (and thus we can not inline
130 into it). */
131 unsigned contains_cilk_spawn : 1;
132 /* True wen there is only one caller of the function before small function
133 inlining. */
134 unsigned int single_caller : 1;
136 /* Information about function that will result after applying all the
137 inline decisions present in the callgraph. Generally kept up to
138 date only for functions that are not inline clones. */
140 /* Estimated stack frame consumption by the function. */
141 HOST_WIDE_INT estimated_stack_size;
142 /* Expected offset of the stack frame of inlined function. */
143 HOST_WIDE_INT stack_frame_offset;
144 /* Estimated size of the function after inlining. */
145 int time;
146 int size;
148 /* Conditional size/time information. The summaries are being
149 merged during inlining. */
150 conditions conds;
151 vec<size_time_entry, va_gc> *entry;
153 /* Predicate on when some loop in the function becomes to have known
154 bounds. */
155 struct predicate * GTY((skip)) loop_iterations;
156 /* Predicate on when some loop in the function becomes to have known
157 stride. */
158 struct predicate * GTY((skip)) loop_stride;
159 /* Predicate on when some array indexes become constants. */
160 struct predicate * GTY((skip)) array_index;
161 /* Estimated growth for inlining all copies of the function before start
162 of small functions inlining.
163 This value will get out of date as the callers are duplicated, but
164 using up-to-date value in the badness metric mean a lot of extra
165 expenses. */
166 int growth;
167 /* Number of SCC on the beginning of inlining process. */
168 int scc_no;
171 class GTY((user)) inline_summary_t: public function_summary <inline_summary *>
173 public:
174 inline_summary_t (symbol_table *symtab, bool ggc):
175 function_summary <inline_summary *> (symtab, ggc) {}
177 static inline_summary_t *create_ggc (symbol_table *symtab)
179 struct inline_summary_t *summary = new (ggc_cleared_alloc <inline_summary_t> ())
180 inline_summary_t(symtab, true);
181 summary->disable_insertion_hook ();
182 return summary;
186 virtual void insert (cgraph_node *, inline_summary *);
187 virtual void remove (cgraph_node *node, inline_summary *);
188 virtual void duplicate (cgraph_node *src, cgraph_node *dst,
189 inline_summary *src_data, inline_summary *dst_data);
192 extern GTY(()) function_summary <inline_summary *> *inline_summaries;
194 /* Information kept about parameter of call site. */
195 struct inline_param_summary
197 /* REG_BR_PROB_BASE based probability that parameter will change in between
198 two invocation of the calls.
199 I.e. loop invariant parameters
200 REG_BR_PROB_BASE/estimated_iterations and regular
201 parameters REG_BR_PROB_BASE.
203 Value 0 is reserved for compile time invariants. */
204 int change_prob;
207 /* Information kept about callgraph edges. */
208 struct inline_edge_summary
210 /* Estimated size and time of the call statement. */
211 int call_stmt_size;
212 int call_stmt_time;
213 /* Depth of loop nest, 0 means no nesting. */
214 unsigned short int loop_depth;
215 struct predicate *predicate;
216 /* Array indexed by parameters.
217 0 means that parameter change all the time, REG_BR_PROB_BASE means
218 that parameter is constant. */
219 vec<inline_param_summary> param;
222 /* Need a typedef for inline_edge_summary because of inline function
223 'inline_edge_summary' below. */
224 typedef struct inline_edge_summary inline_edge_summary_t;
225 extern vec<inline_edge_summary_t> inline_edge_summary_vec;
227 struct edge_growth_cache_entry
229 int time, size;
230 inline_hints hints;
233 extern vec<edge_growth_cache_entry> edge_growth_cache;
235 /* In ipa-inline-analysis.c */
236 void debug_inline_summary (struct cgraph_node *);
237 void dump_inline_summaries (FILE *f);
238 void dump_inline_summary (FILE *f, struct cgraph_node *node);
239 void dump_inline_hints (FILE *f, inline_hints);
240 void inline_generate_summary (void);
241 void inline_read_summary (void);
242 void inline_write_summary (void);
243 void inline_free_summary (void);
244 void inline_analyze_function (struct cgraph_node *node);
245 void initialize_inline_failed (struct cgraph_edge *);
246 int estimate_time_after_inlining (struct cgraph_node *, struct cgraph_edge *);
247 int estimate_size_after_inlining (struct cgraph_node *, struct cgraph_edge *);
248 void estimate_ipcp_clone_size_and_time (struct cgraph_node *,
249 vec<tree>,
250 vec<ipa_polymorphic_call_context>,
251 vec<ipa_agg_jump_function_p>,
252 int *, int *, inline_hints *);
253 int estimate_growth (struct cgraph_node *);
254 bool growth_likely_positive (struct cgraph_node *, int);
255 void inline_merge_summary (struct cgraph_edge *edge);
256 void inline_update_overall_summary (struct cgraph_node *node);
257 int do_estimate_edge_size (struct cgraph_edge *edge);
258 int do_estimate_edge_time (struct cgraph_edge *edge);
259 inline_hints do_estimate_edge_hints (struct cgraph_edge *edge);
260 void initialize_growth_caches (void);
261 void free_growth_caches (void);
262 void compute_inline_parameters (struct cgraph_node *, bool);
263 bool speculation_useful_p (struct cgraph_edge *e, bool anticipate_inlining);
264 unsigned int early_inliner (function *fun);
265 bool inline_account_function_p (struct cgraph_node *node);
268 /* In ipa-inline-transform.c */
269 bool inline_call (struct cgraph_edge *, bool, vec<cgraph_edge *> *, int *, bool,
270 bool *callee_removed = NULL);
271 unsigned int inline_transform (struct cgraph_node *);
272 void clone_inlined_nodes (struct cgraph_edge *e, bool, bool, int *,
273 int freq_scale);
275 extern int ncalls_inlined;
276 extern int nfunctions_inlined;
278 static inline struct inline_edge_summary *
279 inline_edge_summary (struct cgraph_edge *edge)
281 return &inline_edge_summary_vec[edge->uid];
285 /* Return estimated size of the inline sequence of EDGE. */
287 static inline int
288 estimate_edge_size (struct cgraph_edge *edge)
290 int ret;
291 if ((int)edge_growth_cache.length () <= edge->uid
292 || !(ret = edge_growth_cache[edge->uid].size))
293 return do_estimate_edge_size (edge);
294 return ret - (ret > 0);
297 /* Return estimated callee growth after inlining EDGE. */
299 static inline int
300 estimate_edge_growth (struct cgraph_edge *edge)
302 #ifdef ENABLE_CHECKING
303 gcc_checking_assert (inline_edge_summary (edge)->call_stmt_size
304 || !edge->callee->analyzed);
305 #endif
306 return (estimate_edge_size (edge)
307 - inline_edge_summary (edge)->call_stmt_size);
310 /* Return estimated callee runtime increase after inlning
311 EDGE. */
313 static inline int
314 estimate_edge_time (struct cgraph_edge *edge)
316 int ret;
317 if ((int)edge_growth_cache.length () <= edge->uid
318 || !(ret = edge_growth_cache[edge->uid].time))
319 return do_estimate_edge_time (edge);
320 return ret - (ret > 0);
324 /* Return estimated callee runtime increase after inlning
325 EDGE. */
327 static inline inline_hints
328 estimate_edge_hints (struct cgraph_edge *edge)
330 inline_hints ret;
331 if ((int)edge_growth_cache.length () <= edge->uid
332 || !(ret = edge_growth_cache[edge->uid].hints))
333 return do_estimate_edge_hints (edge);
334 return ret - 1;
337 /* Reset cached value for EDGE. */
339 static inline void
340 reset_edge_growth_cache (struct cgraph_edge *edge)
342 if ((int)edge_growth_cache.length () > edge->uid)
344 struct edge_growth_cache_entry zero = {0, 0, 0};
345 edge_growth_cache[edge->uid] = zero;
349 #endif /* GCC_IPA_INLINE_H */