]>
Commit | Line | Data |
---|---|---|
03dfc36d | 1 | /* Inlining decision heuristics. |
d1e082c2 | 2 | Copyright (C) 2003-2013 Free Software Foundation, Inc. |
03dfc36d JH |
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 | ||
2c9561b5 MJ |
21 | #include "ipa-prop.h" |
22 | ||
632b4f8e JH |
23 | /* Representation of inline parameters that do depend on context function is |
24 | inlined into (i.e. known constant values of function parameters. | |
25 | ||
26 | Conditions that are interesting for function body are collected into CONDS | |
27 | vector. They are of simple for function_param OP VAL, where VAL is | |
5932a4d4 | 28 | IPA invariant. The conditions are then referred by predicates. */ |
632b4f8e JH |
29 | |
30 | typedef struct GTY(()) condition | |
31 | { | |
8810cc52 MJ |
32 | /* If agg_contents is set, this is the offset from which the used data was |
33 | loaded. */ | |
34 | HOST_WIDE_INT offset; | |
632b4f8e JH |
35 | tree val; |
36 | int operand_num; | |
8810cc52 MJ |
37 | ENUM_BITFIELD(tree_code) code : 16; |
38 | /* Set if the used data were loaded from an aggregate parameter or from | |
39 | data received by reference. */ | |
40 | unsigned agg_contents : 1; | |
41 | /* If agg_contents is set, this differentiates between loads from data | |
42 | passed by reference and by value. */ | |
43 | unsigned by_ref : 1; | |
632b4f8e JH |
44 | } condition; |
45 | ||
52843a47 JH |
46 | /* Inline hints are reasons why inline heuristics should preffer inlining given |
47 | function. They are represtented as bitmap of the following values. */ | |
37678631 | 48 | enum inline_hints_vals { |
52843a47 JH |
49 | /* When inlining turns indirect call into a direct call, |
50 | it is good idea to do so. */ | |
2daffc47 | 51 | INLINE_HINT_indirect_call = 1, |
52843a47 JH |
52 | /* Inlining may make loop iterations or loop stride known. It is good idea |
53 | to do so because it enables loop optimizatoins. */ | |
128e0d89 | 54 | INLINE_HINT_loop_iterations = 2, |
b48ccf0d | 55 | INLINE_HINT_loop_stride = 4, |
52843a47 JH |
56 | /* Inlining withing same strongly connected component of callgraph is often |
57 | a loss due to increased stack frame usage and prologue setup costs. */ | |
b48ccf0d | 58 | INLINE_HINT_same_scc = 8, |
52843a47 JH |
59 | /* Inlining functions in strongly connected component is not such a great |
60 | win. */ | |
d59171da | 61 | INLINE_HINT_in_scc = 16, |
52843a47 JH |
62 | /* If function is declared inline by user, it may be good idea to inline |
63 | it. */ | |
d59171da | 64 | INLINE_HINT_declared_inline = 32, |
52843a47 JH |
65 | /* Programs are usually still organized for non-LTO compilation and thus |
66 | if functions are in different modules, inlining may not be so important. | |
67 | */ | |
68 | INLINE_HINT_cross_module = 64, | |
69 | /* If array indexes of loads/stores become known there may be room for | |
70 | futher optimization. */ | |
71 | INLINE_HINT_array_index = 128 | |
37678631 JH |
72 | }; |
73 | typedef int inline_hints; | |
74 | ||
632b4f8e | 75 | |
9771b263 | 76 | typedef vec<condition, va_gc> *conditions; |
632b4f8e JH |
77 | |
78 | /* Representation of predicates i.e. formulas using conditions defined | |
79 | above. Predicates are simple logical formulas in conjunctive-disjunctive | |
80 | form. | |
81 | ||
82 | Predicate is array of clauses terminated by 0. Every clause must be true | |
83 | in order to make predicate true. | |
84 | Clauses are represented as bitmaps of conditions. One of conditions | |
85 | must be true in order for clause to be true. */ | |
86 | ||
87 | #define MAX_CLAUSES 8 | |
b15c64ee | 88 | typedef unsigned int clause_t; |
632b4f8e JH |
89 | struct GTY(()) predicate |
90 | { | |
91 | clause_t clause[MAX_CLAUSES + 1]; | |
92 | }; | |
93 | ||
94 | /* Represnetation of function body size and time depending on the inline | |
95 | context. We keep simple array of record, every containing of predicate | |
96 | and time/size to account. | |
10a5dd5d | 97 | |
632b4f8e JH |
98 | We keep values scaled up, so fractional sizes and times can be |
99 | accounted. */ | |
100 | #define INLINE_SIZE_SCALE 2 | |
101 | #define INLINE_TIME_SCALE (CGRAPH_FREQ_BASE * 2) | |
102 | typedef struct GTY(()) size_time_entry | |
103 | { | |
104 | struct predicate predicate; | |
105 | int size; | |
106 | int time; | |
107 | } size_time_entry; | |
632b4f8e JH |
108 | |
109 | /* Function inlining information. */ | |
110 | struct GTY(()) inline_summary | |
10a5dd5d | 111 | { |
e7f23018 JH |
112 | /* Information about the function body itself. */ |
113 | ||
10a5dd5d JH |
114 | /* Estimated stack frame consumption by the function. */ |
115 | HOST_WIDE_INT estimated_self_stack_size; | |
10a5dd5d JH |
116 | /* Size of the function body. */ |
117 | int self_size; | |
632b4f8e | 118 | /* Time of the function body. */ |
10a5dd5d | 119 | int self_time; |
e7f23018 JH |
120 | |
121 | /* False when there something makes inlining impossible (such as va_arg). */ | |
122 | unsigned inlinable : 1; | |
e7f23018 JH |
123 | |
124 | /* Information about function that will result after applying all the | |
125 | inline decisions present in the callgraph. Generally kept up to | |
126 | date only for functions that are not inline clones. */ | |
127 | ||
128 | /* Estimated stack frame consumption by the function. */ | |
129 | HOST_WIDE_INT estimated_stack_size; | |
130 | /* Expected offset of the stack frame of inlined function. */ | |
131 | HOST_WIDE_INT stack_frame_offset; | |
132 | /* Estimated size of the function after inlining. */ | |
133 | int time; | |
134 | int size; | |
632b4f8e | 135 | |
898b8927 JH |
136 | /* Conditional size/time information. The summaries are being |
137 | merged during inlining. */ | |
632b4f8e | 138 | conditions conds; |
9771b263 | 139 | vec<size_time_entry, va_gc> *entry; |
2daffc47 | 140 | |
128e0d89 | 141 | /* Predicate on when some loop in the function becomes to have known |
2daffc47 JH |
142 | bounds. */ |
143 | struct predicate * GTY((skip)) loop_iterations; | |
128e0d89 JH |
144 | /* Predicate on when some loop in the function becomes to have known |
145 | stride. */ | |
146 | struct predicate * GTY((skip)) loop_stride; | |
52843a47 JH |
147 | /* Predicate on when some array indexes become constants. */ |
148 | struct predicate * GTY((skip)) array_index; | |
d59171da JH |
149 | /* Estimated growth for inlining all copies of the function before start |
150 | of small functions inlining. | |
151 | This value will get out of date as the callers are duplicated, but | |
152 | using up-to-date value in the badness metric mean a lot of extra | |
153 | expenses. */ | |
154 | int growth; | |
b48ccf0d JH |
155 | /* Number of SCC on the beggining of inlining process. */ |
156 | int scc_no; | |
10a5dd5d JH |
157 | }; |
158 | ||
25837a2f | 159 | |
10a5dd5d | 160 | typedef struct inline_summary inline_summary_t; |
9771b263 | 161 | extern GTY(()) vec<inline_summary_t, va_gc> *inline_summary_vec; |
632b4f8e | 162 | |
25837a2f JH |
163 | /* Information kept about parameter of call site. */ |
164 | struct inline_param_summary | |
165 | { | |
166 | /* REG_BR_PROB_BASE based probability that parameter will change in between | |
167 | two invocation of the calls. | |
168 | I.e. loop invariant parameters | |
169 | REG_BR_PROB_BASE/estimated_iterations and regular | |
170 | parameters REG_BR_PROB_BASE. | |
171 | ||
172 | Value 0 is reserved for compile time invariants. */ | |
173 | int change_prob; | |
174 | }; | |
175 | typedef struct inline_param_summary inline_param_summary_t; | |
25837a2f | 176 | |
898b8927 JH |
177 | /* Information kept about callgraph edges. */ |
178 | struct inline_edge_summary | |
179 | { | |
180 | /* Estimated size and time of the call statement. */ | |
181 | int call_stmt_size; | |
182 | int call_stmt_time; | |
183 | /* Depth of loop nest, 0 means no nesting. */ | |
184 | unsigned short int loop_depth; | |
991278ab | 185 | struct predicate *predicate; |
25837a2f JH |
186 | /* Array indexed by parameters. |
187 | 0 means that parameter change all the time, REG_BR_PROB_BASE means | |
188 | that parameter is constant. */ | |
9771b263 | 189 | vec<inline_param_summary_t> param; |
898b8927 JH |
190 | }; |
191 | ||
192 | typedef struct inline_edge_summary inline_edge_summary_t; | |
9771b263 | 193 | extern vec<inline_edge_summary_t> inline_edge_summary_vec; |
898b8927 | 194 | |
632b4f8e JH |
195 | typedef struct edge_growth_cache_entry |
196 | { | |
197 | int time, size; | |
37678631 | 198 | inline_hints hints; |
632b4f8e | 199 | } edge_growth_cache_entry; |
632b4f8e | 200 | |
9771b263 DN |
201 | extern vec<int> node_growth_cache; |
202 | extern vec<edge_growth_cache_entry> edge_growth_cache; | |
10a5dd5d | 203 | |
fee8b6da | 204 | /* In ipa-inline-analysis.c */ |
10a5dd5d JH |
205 | void debug_inline_summary (struct cgraph_node *); |
206 | void dump_inline_summaries (FILE *f); | |
37678631 JH |
207 | void dump_inline_summary (FILE *f, struct cgraph_node *node); |
208 | void dump_inline_hints (FILE *f, inline_hints); | |
03dfc36d JH |
209 | void inline_generate_summary (void); |
210 | void inline_read_summary (void); | |
f27c1867 | 211 | void inline_write_summary (void); |
03dfc36d | 212 | void inline_free_summary (void); |
e7f23018 | 213 | void initialize_inline_failed (struct cgraph_edge *); |
03dfc36d JH |
214 | int estimate_time_after_inlining (struct cgraph_node *, struct cgraph_edge *); |
215 | int estimate_size_after_inlining (struct cgraph_node *, struct cgraph_edge *); | |
411a20d6 | 216 | void estimate_ipcp_clone_size_and_time (struct cgraph_node *, |
9771b263 DN |
217 | vec<tree>, vec<tree>, |
218 | vec<ipa_agg_jump_function_p>, | |
2c9561b5 | 219 | int *, int *, inline_hints *); |
632b4f8e JH |
220 | int do_estimate_growth (struct cgraph_node *); |
221 | void inline_merge_summary (struct cgraph_edge *edge); | |
c170d40f | 222 | void inline_update_overall_summary (struct cgraph_node *node); |
ed901e4c | 223 | int do_estimate_edge_size (struct cgraph_edge *edge); |
632b4f8e | 224 | int do_estimate_edge_time (struct cgraph_edge *edge); |
37678631 | 225 | inline_hints do_estimate_edge_hints (struct cgraph_edge *edge); |
632b4f8e JH |
226 | void initialize_growth_caches (void); |
227 | void free_growth_caches (void); | |
228 | void compute_inline_parameters (struct cgraph_node *, bool); | |
03dfc36d | 229 | |
fee8b6da | 230 | /* In ipa-inline-transform.c */ |
9771b263 | 231 | bool inline_call (struct cgraph_edge *, bool, vec<cgraph_edge_p> *, int *, bool); |
fee8b6da JH |
232 | unsigned int inline_transform (struct cgraph_node *); |
233 | void clone_inlined_nodes (struct cgraph_edge *e, bool, bool, int *); | |
234 | ||
235 | extern int ncalls_inlined; | |
236 | extern int nfunctions_inlined; | |
237 | ||
03dfc36d JH |
238 | static inline struct inline_summary * |
239 | inline_summary (struct cgraph_node *node) | |
240 | { | |
9771b263 | 241 | return &(*inline_summary_vec)[node->uid]; |
03dfc36d JH |
242 | } |
243 | ||
898b8927 JH |
244 | static inline struct inline_edge_summary * |
245 | inline_edge_summary (struct cgraph_edge *edge) | |
246 | { | |
9771b263 | 247 | return &inline_edge_summary_vec[edge->uid]; |
898b8927 | 248 | } |
632b4f8e JH |
249 | |
250 | /* Return estimated unit growth after inlning all calls to NODE. | |
251 | Quick accesors to the inline growth caches. | |
252 | For convenience we keep zero 0 as unknown. Because growth | |
253 | can be both positive and negative, we simply increase positive | |
254 | growths by 1. */ | |
255 | static inline int | |
256 | estimate_growth (struct cgraph_node *node) | |
257 | { | |
258 | int ret; | |
9771b263 DN |
259 | if ((int)node_growth_cache.length () <= node->uid |
260 | || !(ret = node_growth_cache[node->uid])) | |
632b4f8e JH |
261 | return do_estimate_growth (node); |
262 | return ret - (ret > 0); | |
263 | } | |
264 | ||
265 | ||
ed901e4c | 266 | /* Return estimated size of the inline sequence of EDGE. */ |
03dfc36d JH |
267 | |
268 | static inline int | |
ed901e4c | 269 | estimate_edge_size (struct cgraph_edge *edge) |
03dfc36d | 270 | { |
632b4f8e | 271 | int ret; |
9771b263 DN |
272 | if ((int)edge_growth_cache.length () <= edge->uid |
273 | || !(ret = edge_growth_cache[edge->uid].size)) | |
ed901e4c | 274 | return do_estimate_edge_size (edge); |
632b4f8e JH |
275 | return ret - (ret > 0); |
276 | } | |
277 | ||
ed901e4c JH |
278 | /* Return estimated callee growth after inlining EDGE. */ |
279 | ||
280 | static inline int | |
281 | estimate_edge_growth (struct cgraph_edge *edge) | |
282 | { | |
283 | #ifdef ENABLE_CHECKING | |
284 | gcc_checking_assert (inline_edge_summary (edge)->call_stmt_size); | |
285 | #endif | |
286 | return (estimate_edge_size (edge) | |
287 | - inline_edge_summary (edge)->call_stmt_size); | |
288 | } | |
632b4f8e JH |
289 | |
290 | /* Return estimated callee runtime increase after inlning | |
291 | EDGE. */ | |
292 | ||
293 | static inline int | |
294 | estimate_edge_time (struct cgraph_edge *edge) | |
295 | { | |
296 | int ret; | |
9771b263 DN |
297 | if ((int)edge_growth_cache.length () <= edge->uid |
298 | || !(ret = edge_growth_cache[edge->uid].time)) | |
632b4f8e JH |
299 | return do_estimate_edge_time (edge); |
300 | return ret - (ret > 0); | |
301 | } | |
302 | ||
303 | ||
37678631 JH |
304 | /* Return estimated callee runtime increase after inlning |
305 | EDGE. */ | |
306 | ||
307 | static inline inline_hints | |
308 | estimate_edge_hints (struct cgraph_edge *edge) | |
309 | { | |
310 | inline_hints ret; | |
9771b263 DN |
311 | if ((int)edge_growth_cache.length () <= edge->uid |
312 | || !(ret = edge_growth_cache[edge->uid].hints)) | |
de99ac70 | 313 | return do_estimate_edge_hints (edge); |
37678631 JH |
314 | return ret - 1; |
315 | } | |
316 | ||
317 | ||
632b4f8e JH |
318 | /* Reset cached value for NODE. */ |
319 | ||
320 | static inline void | |
321 | reset_node_growth_cache (struct cgraph_node *node) | |
322 | { | |
9771b263 DN |
323 | if ((int)node_growth_cache.length () > node->uid) |
324 | node_growth_cache[node->uid] = 0; | |
632b4f8e JH |
325 | } |
326 | ||
327 | /* Reset cached value for EDGE. */ | |
328 | ||
329 | static inline void | |
330 | reset_edge_growth_cache (struct cgraph_edge *edge) | |
331 | { | |
9771b263 | 332 | if ((int)edge_growth_cache.length () > edge->uid) |
632b4f8e | 333 | { |
37678631 | 334 | struct edge_growth_cache_entry zero = {0, 0, 0}; |
9771b263 | 335 | edge_growth_cache[edge->uid] = zero; |
632b4f8e | 336 | } |
03dfc36d | 337 | } |