]>
Commit | Line | Data |
---|---|---|
99c67f24 | 1 | /* Inlining decision heuristics. |
f1717362 | 2 | Copyright (C) 2003-2016 Free Software Foundation, Inc. |
99c67f24 | 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 | ||
ce6bb0f3 | 21 | #ifndef GCC_IPA_INLINE_H |
22 | #define GCC_IPA_INLINE_H | |
23 | ||
803a7988 | 24 | |
a41f2a28 | 25 | /* Representation of inline parameters that do depend on context function is |
26 | inlined into (i.e. known constant values of function parameters. | |
27 | ||
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 | |
04ec15fa | 30 | IPA invariant. The conditions are then referred by predicates. */ |
a41f2a28 | 31 | |
b3e7c666 | 32 | struct GTY(()) condition |
33 | { | |
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; | |
46 | }; | |
a41f2a28 | 47 | |
be343a9c | 48 | /* Inline hints are reasons why inline heuristics should preffer inlining given |
49 | function. They are represtented as bitmap of the following values. */ | |
eb7c606e | 50 | enum inline_hints_vals { |
be343a9c | 51 | /* When inlining turns indirect call into a direct call, |
52 | it is good idea to do so. */ | |
7c07aa3d | 53 | INLINE_HINT_indirect_call = 1, |
be343a9c | 54 | /* Inlining may make loop iterations or loop stride known. It is good idea |
55 | to do so because it enables loop optimizatoins. */ | |
3716ee8f | 56 | INLINE_HINT_loop_iterations = 2, |
41d39f38 | 57 | INLINE_HINT_loop_stride = 4, |
a04e8d62 | 58 | /* Inlining within same strongly connected component of callgraph is often |
be343a9c | 59 | a loss due to increased stack frame usage and prologue setup costs. */ |
41d39f38 | 60 | INLINE_HINT_same_scc = 8, |
be343a9c | 61 | /* Inlining functions in strongly connected component is not such a great |
62 | win. */ | |
3172b7bf | 63 | INLINE_HINT_in_scc = 16, |
be343a9c | 64 | /* If function is declared inline by user, it may be good idea to inline |
65 | it. */ | |
3172b7bf | 66 | INLINE_HINT_declared_inline = 32, |
be343a9c | 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. | |
69 | */ | |
70 | INLINE_HINT_cross_module = 64, | |
71 | /* If array indexes of loads/stores become known there may be room for | |
a04e8d62 | 72 | further optimization. */ |
3072aa32 | 73 | INLINE_HINT_array_index = 128, |
74 | /* We know that the callee is hot by profile. */ | |
75 | INLINE_HINT_known_hot = 256 | |
eb7c606e | 76 | }; |
77 | typedef int inline_hints; | |
78 | ||
a41f2a28 | 79 | |
f1f41a6c | 80 | typedef vec<condition, va_gc> *conditions; |
a41f2a28 | 81 | |
82 | /* Representation of predicates i.e. formulas using conditions defined | |
83 | above. Predicates are simple logical formulas in conjunctive-disjunctive | |
84 | form. | |
85 | ||
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. */ | |
90 | ||
91 | #define MAX_CLAUSES 8 | |
905aa3bd | 92 | typedef unsigned int clause_t; |
a41f2a28 | 93 | struct GTY(()) predicate |
94 | { | |
95 | clause_t clause[MAX_CLAUSES + 1]; | |
96 | }; | |
97 | ||
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. | |
c7b2cc59 | 101 | |
a41f2a28 | 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) | |
b3e7c666 | 106 | struct GTY(()) size_time_entry |
a41f2a28 | 107 | { |
108 | struct predicate predicate; | |
109 | int size; | |
110 | int time; | |
b3e7c666 | 111 | }; |
a41f2a28 | 112 | |
113 | /* Function inlining information. */ | |
114 | struct GTY(()) inline_summary | |
c7b2cc59 | 115 | { |
cbd7f5a0 | 116 | /* Information about the function body itself. */ |
117 | ||
c7b2cc59 | 118 | /* Estimated stack frame consumption by the function. */ |
119 | HOST_WIDE_INT estimated_self_stack_size; | |
c7b2cc59 | 120 | /* Size of the function body. */ |
121 | int self_size; | |
a41f2a28 | 122 | /* Time of the function body. */ |
c7b2cc59 | 123 | int self_time; |
db197f90 | 124 | /* Minimal size increase after inlining. */ |
125 | int min_size; | |
cbd7f5a0 | 126 | |
127 | /* False when there something makes inlining impossible (such as va_arg). */ | |
128 | unsigned inlinable : 1; | |
e806c56f | 129 | /* True when function contains cilk spawn (and thus we can not inline |
130 | into it). */ | |
131 | unsigned contains_cilk_spawn : 1; | |
71e37927 | 132 | /* True wen there is only one caller of the function before small function |
133 | inlining. */ | |
134 | unsigned int single_caller : 1; | |
cbd7f5a0 | 135 | |
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. */ | |
139 | ||
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; | |
a41f2a28 | 147 | |
0835ad03 | 148 | /* Conditional size/time information. The summaries are being |
149 | merged during inlining. */ | |
a41f2a28 | 150 | conditions conds; |
f1f41a6c | 151 | vec<size_time_entry, va_gc> *entry; |
7c07aa3d | 152 | |
3716ee8f | 153 | /* Predicate on when some loop in the function becomes to have known |
7c07aa3d | 154 | bounds. */ |
155 | struct predicate * GTY((skip)) loop_iterations; | |
3716ee8f | 156 | /* Predicate on when some loop in the function becomes to have known |
157 | stride. */ | |
158 | struct predicate * GTY((skip)) loop_stride; | |
be343a9c | 159 | /* Predicate on when some array indexes become constants. */ |
160 | struct predicate * GTY((skip)) array_index; | |
3172b7bf | 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; | |
a04e8d62 | 167 | /* Number of SCC on the beginning of inlining process. */ |
41d39f38 | 168 | int scc_no; |
c7b2cc59 | 169 | }; |
170 | ||
b4bae7a0 | 171 | class GTY((user)) inline_summary_t: public function_summary <inline_summary *> |
172 | { | |
173 | public: | |
174 | inline_summary_t (symbol_table *symtab, bool ggc): | |
175 | function_summary <inline_summary *> (symtab, ggc) {} | |
176 | ||
177 | static inline_summary_t *create_ggc (symbol_table *symtab) | |
178 | { | |
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; | |
183 | } | |
184 | ||
185 | ||
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); | |
190 | }; | |
191 | ||
192 | extern GTY(()) function_summary <inline_summary *> *inline_summaries; | |
a41f2a28 | 193 | |
eb4ae064 | 194 | /* Information kept about parameter of call site. */ |
195 | struct inline_param_summary | |
196 | { | |
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. | |
202 | ||
203 | Value 0 is reserved for compile time invariants. */ | |
204 | int change_prob; | |
205 | }; | |
eb4ae064 | 206 | |
0835ad03 | 207 | /* Information kept about callgraph edges. */ |
208 | struct inline_edge_summary | |
209 | { | |
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; | |
6a18c0be | 215 | struct predicate *predicate; |
eb4ae064 | 216 | /* Array indexed by parameters. |
217 | 0 means that parameter change all the time, REG_BR_PROB_BASE means | |
218 | that parameter is constant. */ | |
b3e7c666 | 219 | vec<inline_param_summary> param; |
0835ad03 | 220 | }; |
221 | ||
b3e7c666 | 222 | /* Need a typedef for inline_edge_summary because of inline function |
223 | 'inline_edge_summary' below. */ | |
0835ad03 | 224 | typedef struct inline_edge_summary inline_edge_summary_t; |
f1f41a6c | 225 | extern vec<inline_edge_summary_t> inline_edge_summary_vec; |
0835ad03 | 226 | |
b3e7c666 | 227 | struct edge_growth_cache_entry |
a41f2a28 | 228 | { |
229 | int time, size; | |
eb7c606e | 230 | inline_hints hints; |
b3e7c666 | 231 | }; |
a41f2a28 | 232 | |
f1f41a6c | 233 | extern vec<edge_growth_cache_entry> edge_growth_cache; |
c7b2cc59 | 234 | |
8cbc43ff | 235 | /* In ipa-inline-analysis.c */ |
c7b2cc59 | 236 | void debug_inline_summary (struct cgraph_node *); |
237 | void dump_inline_summaries (FILE *f); | |
eb7c606e | 238 | void dump_inline_summary (FILE *f, struct cgraph_node *node); |
239 | void dump_inline_hints (FILE *f, inline_hints); | |
99c67f24 | 240 | void inline_generate_summary (void); |
241 | void inline_read_summary (void); | |
eab36a5a | 242 | void inline_write_summary (void); |
99c67f24 | 243 | void inline_free_summary (void); |
cb8994e9 | 244 | void inline_analyze_function (struct cgraph_node *node); |
cbd7f5a0 | 245 | void initialize_inline_failed (struct cgraph_edge *); |
99c67f24 | 246 | int estimate_time_after_inlining (struct cgraph_node *, struct cgraph_edge *); |
247 | int estimate_size_after_inlining (struct cgraph_node *, struct cgraph_edge *); | |
93f713da | 248 | void estimate_ipcp_clone_size_and_time (struct cgraph_node *, |
245ab191 | 249 | vec<tree>, |
250 | vec<ipa_polymorphic_call_context>, | |
f1f41a6c | 251 | vec<ipa_agg_jump_function_p>, |
803a7988 | 252 | int *, int *, inline_hints *); |
bc42c20c | 253 | int estimate_growth (struct cgraph_node *); |
db197f90 | 254 | bool growth_likely_positive (struct cgraph_node *, int); |
a41f2a28 | 255 | void inline_merge_summary (struct cgraph_edge *edge); |
6331b6fa | 256 | void inline_update_overall_summary (struct cgraph_node *node); |
6c2c7775 | 257 | int do_estimate_edge_size (struct cgraph_edge *edge); |
a41f2a28 | 258 | int do_estimate_edge_time (struct cgraph_edge *edge); |
eb7c606e | 259 | inline_hints do_estimate_edge_hints (struct cgraph_edge *edge); |
a41f2a28 | 260 | void initialize_growth_caches (void); |
261 | void free_growth_caches (void); | |
262 | void compute_inline_parameters (struct cgraph_node *, bool); | |
12d5ae9f | 263 | bool speculation_useful_p (struct cgraph_edge *e, bool anticipate_inlining); |
94bed7c3 | 264 | unsigned int early_inliner (function *fun); |
a6d60179 | 265 | bool inline_account_function_p (struct cgraph_node *node); |
266 | ||
99c67f24 | 267 | |
8cbc43ff | 268 | /* In ipa-inline-transform.c */ |
415d1b9a | 269 | bool inline_call (struct cgraph_edge *, bool, vec<cgraph_edge *> *, int *, bool, |
7c5c01f1 | 270 | bool *callee_removed = NULL); |
8cbc43ff | 271 | unsigned int inline_transform (struct cgraph_node *); |
b8731470 | 272 | void clone_inlined_nodes (struct cgraph_edge *e, bool, bool, int *, |
273 | int freq_scale); | |
8cbc43ff | 274 | |
275 | extern int ncalls_inlined; | |
276 | extern int nfunctions_inlined; | |
277 | ||
0835ad03 | 278 | static inline struct inline_edge_summary * |
279 | inline_edge_summary (struct cgraph_edge *edge) | |
280 | { | |
f1f41a6c | 281 | return &inline_edge_summary_vec[edge->uid]; |
0835ad03 | 282 | } |
a41f2a28 | 283 | |
a41f2a28 | 284 | |
6c2c7775 | 285 | /* Return estimated size of the inline sequence of EDGE. */ |
99c67f24 | 286 | |
287 | static inline int | |
6c2c7775 | 288 | estimate_edge_size (struct cgraph_edge *edge) |
99c67f24 | 289 | { |
a41f2a28 | 290 | int ret; |
f1f41a6c | 291 | if ((int)edge_growth_cache.length () <= edge->uid |
292 | || !(ret = edge_growth_cache[edge->uid].size)) | |
6c2c7775 | 293 | return do_estimate_edge_size (edge); |
a41f2a28 | 294 | return ret - (ret > 0); |
295 | } | |
296 | ||
6c2c7775 | 297 | /* Return estimated callee growth after inlining EDGE. */ |
298 | ||
299 | static inline int | |
300 | estimate_edge_growth (struct cgraph_edge *edge) | |
301 | { | |
5a7ad253 | 302 | gcc_checking_assert (inline_edge_summary (edge)->call_stmt_size |
303 | || !edge->callee->analyzed); | |
6c2c7775 | 304 | return (estimate_edge_size (edge) |
305 | - inline_edge_summary (edge)->call_stmt_size); | |
306 | } | |
a41f2a28 | 307 | |
308 | /* Return estimated callee runtime increase after inlning | |
309 | EDGE. */ | |
310 | ||
311 | static inline int | |
312 | estimate_edge_time (struct cgraph_edge *edge) | |
313 | { | |
314 | int ret; | |
f1f41a6c | 315 | if ((int)edge_growth_cache.length () <= edge->uid |
316 | || !(ret = edge_growth_cache[edge->uid].time)) | |
a41f2a28 | 317 | return do_estimate_edge_time (edge); |
318 | return ret - (ret > 0); | |
319 | } | |
320 | ||
321 | ||
eb7c606e | 322 | /* Return estimated callee runtime increase after inlning |
323 | EDGE. */ | |
324 | ||
325 | static inline inline_hints | |
326 | estimate_edge_hints (struct cgraph_edge *edge) | |
327 | { | |
328 | inline_hints ret; | |
f1f41a6c | 329 | if ((int)edge_growth_cache.length () <= edge->uid |
330 | || !(ret = edge_growth_cache[edge->uid].hints)) | |
6e300957 | 331 | return do_estimate_edge_hints (edge); |
eb7c606e | 332 | return ret - 1; |
333 | } | |
334 | ||
a41f2a28 | 335 | /* Reset cached value for EDGE. */ |
336 | ||
337 | static inline void | |
338 | reset_edge_growth_cache (struct cgraph_edge *edge) | |
339 | { | |
f1f41a6c | 340 | if ((int)edge_growth_cache.length () > edge->uid) |
a41f2a28 | 341 | { |
eb7c606e | 342 | struct edge_growth_cache_entry zero = {0, 0, 0}; |
f1f41a6c | 343 | edge_growth_cache[edge->uid] = zero; |
a41f2a28 | 344 | } |
99c67f24 | 345 | } |
ce6bb0f3 | 346 | |
347 | #endif /* GCC_IPA_INLINE_H */ |