|
111
|
1 /* Analysis used by inlining decision heuristics.
|
|
|
2 Copyright (C) 2003-2017 Free Software Foundation, Inc.
|
|
|
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
|
|
|
21 #include "config.h"
|
|
|
22 #include "system.h"
|
|
|
23 #include "coretypes.h"
|
|
|
24 #include "backend.h"
|
|
|
25 #include "tree.h"
|
|
|
26 #include "gimple.h"
|
|
|
27 #include "alloc-pool.h"
|
|
|
28 #include "tree-pass.h"
|
|
|
29 #include "ssa.h"
|
|
|
30 #include "tree-streamer.h"
|
|
|
31 #include "cgraph.h"
|
|
|
32 #include "diagnostic.h"
|
|
|
33 #include "fold-const.h"
|
|
|
34 #include "print-tree.h"
|
|
|
35 #include "tree-inline.h"
|
|
|
36 #include "gimple-pretty-print.h"
|
|
|
37 #include "params.h"
|
|
|
38 #include "cfganal.h"
|
|
|
39 #include "gimple-iterator.h"
|
|
|
40 #include "tree-cfg.h"
|
|
|
41 #include "tree-ssa-loop-niter.h"
|
|
|
42 #include "tree-ssa-loop.h"
|
|
|
43 #include "symbol-summary.h"
|
|
|
44 #include "ipa-prop.h"
|
|
|
45 #include "ipa-fnsummary.h"
|
|
|
46 #include "ipa-inline.h"
|
|
|
47 #include "cfgloop.h"
|
|
|
48 #include "tree-scalar-evolution.h"
|
|
|
49 #include "ipa-utils.h"
|
|
|
50 #include "cilk.h"
|
|
|
51 #include "cfgexpand.h"
|
|
|
52 #include "gimplify.h"
|
|
|
53
|
|
|
54 /* Cached node/edge growths. */
|
|
|
55 vec<edge_growth_cache_entry> edge_growth_cache;
|
|
|
56 static struct cgraph_edge_hook_list *edge_removal_hook_holder;
|
|
|
57
|
|
|
58
|
|
|
59 /* Give initial reasons why inlining would fail on EDGE. This gets either
|
|
|
60 nullified or usually overwritten by more precise reasons later. */
|
|
|
61
|
|
|
62 void
|
|
|
63 initialize_inline_failed (struct cgraph_edge *e)
|
|
|
64 {
|
|
|
65 struct cgraph_node *callee = e->callee;
|
|
|
66
|
|
|
67 if (e->inline_failed && e->inline_failed != CIF_BODY_NOT_AVAILABLE
|
|
|
68 && cgraph_inline_failed_type (e->inline_failed) == CIF_FINAL_ERROR)
|
|
|
69 ;
|
|
|
70 else if (e->indirect_unknown_callee)
|
|
|
71 e->inline_failed = CIF_INDIRECT_UNKNOWN_CALL;
|
|
|
72 else if (!callee->definition)
|
|
|
73 e->inline_failed = CIF_BODY_NOT_AVAILABLE;
|
|
|
74 else if (callee->local.redefined_extern_inline)
|
|
|
75 e->inline_failed = CIF_REDEFINED_EXTERN_INLINE;
|
|
|
76 else
|
|
|
77 e->inline_failed = CIF_FUNCTION_NOT_CONSIDERED;
|
|
|
78 gcc_checking_assert (!e->call_stmt_cannot_inline_p
|
|
|
79 || cgraph_inline_failed_type (e->inline_failed)
|
|
|
80 == CIF_FINAL_ERROR);
|
|
|
81 }
|
|
|
82
|
|
|
83
|
|
|
84 /* Keep edge cache consistent across edge removal. */
|
|
|
85
|
|
|
86 static void
|
|
|
87 inline_edge_removal_hook (struct cgraph_edge *edge,
|
|
|
88 void *data ATTRIBUTE_UNUSED)
|
|
|
89 {
|
|
|
90 reset_edge_growth_cache (edge);
|
|
|
91 }
|
|
|
92
|
|
|
93
|
|
|
94 /* Initialize growth caches. */
|
|
|
95
|
|
|
96 void
|
|
|
97 initialize_growth_caches (void)
|
|
|
98 {
|
|
|
99 if (!edge_removal_hook_holder)
|
|
|
100 edge_removal_hook_holder =
|
|
|
101 symtab->add_edge_removal_hook (&inline_edge_removal_hook, NULL);
|
|
|
102 if (symtab->edges_max_uid)
|
|
|
103 edge_growth_cache.safe_grow_cleared (symtab->edges_max_uid);
|
|
|
104 }
|
|
|
105
|
|
|
106
|
|
|
107 /* Free growth caches. */
|
|
|
108
|
|
|
109 void
|
|
|
110 free_growth_caches (void)
|
|
|
111 {
|
|
|
112 if (edge_removal_hook_holder)
|
|
|
113 {
|
|
|
114 symtab->remove_edge_removal_hook (edge_removal_hook_holder);
|
|
|
115 edge_removal_hook_holder = NULL;
|
|
|
116 }
|
|
|
117 edge_growth_cache.release ();
|
|
|
118 }
|
|
|
119
|
|
|
120 /* Return hints derrived from EDGE. */
|
|
|
121
|
|
|
122 int
|
|
|
123 simple_edge_hints (struct cgraph_edge *edge)
|
|
|
124 {
|
|
|
125 int hints = 0;
|
|
|
126 struct cgraph_node *to = (edge->caller->global.inlined_to
|
|
|
127 ? edge->caller->global.inlined_to : edge->caller);
|
|
|
128 struct cgraph_node *callee = edge->callee->ultimate_alias_target ();
|
|
|
129 if (ipa_fn_summaries->get (to)->scc_no
|
|
|
130 && ipa_fn_summaries->get (to)->scc_no
|
|
|
131 == ipa_fn_summaries->get (callee)->scc_no
|
|
|
132 && !edge->recursive_p ())
|
|
|
133 hints |= INLINE_HINT_same_scc;
|
|
|
134
|
|
|
135 if (callee->lto_file_data && edge->caller->lto_file_data
|
|
|
136 && edge->caller->lto_file_data != callee->lto_file_data
|
|
|
137 && !callee->merged_comdat && !callee->icf_merged)
|
|
|
138 hints |= INLINE_HINT_cross_module;
|
|
|
139
|
|
|
140 return hints;
|
|
|
141 }
|
|
|
142
|
|
|
143 /* Estimate the time cost for the caller when inlining EDGE.
|
|
|
144 Only to be called via estimate_edge_time, that handles the
|
|
|
145 caching mechanism.
|
|
|
146
|
|
|
147 When caching, also update the cache entry. Compute both time and
|
|
|
148 size, since we always need both metrics eventually. */
|
|
|
149
|
|
|
150 sreal
|
|
|
151 do_estimate_edge_time (struct cgraph_edge *edge)
|
|
|
152 {
|
|
|
153 sreal time, nonspec_time;
|
|
|
154 int size;
|
|
|
155 ipa_hints hints;
|
|
|
156 struct cgraph_node *callee;
|
|
|
157 clause_t clause, nonspec_clause;
|
|
|
158 vec<tree> known_vals;
|
|
|
159 vec<ipa_polymorphic_call_context> known_contexts;
|
|
|
160 vec<ipa_agg_jump_function_p> known_aggs;
|
|
|
161 struct ipa_call_summary *es = ipa_call_summaries->get (edge);
|
|
|
162 int min_size;
|
|
|
163
|
|
|
164 callee = edge->callee->ultimate_alias_target ();
|
|
|
165
|
|
|
166 gcc_checking_assert (edge->inline_failed);
|
|
|
167 evaluate_properties_for_edge (edge, true,
|
|
|
168 &clause, &nonspec_clause, &known_vals,
|
|
|
169 &known_contexts, &known_aggs);
|
|
|
170 estimate_node_size_and_time (callee, clause, nonspec_clause, known_vals,
|
|
|
171 known_contexts, known_aggs, &size, &min_size,
|
|
|
172 &time, &nonspec_time, &hints, es->param);
|
|
|
173
|
|
|
174 /* When we have profile feedback, we can quite safely identify hot
|
|
|
175 edges and for those we disable size limits. Don't do that when
|
|
|
176 probability that caller will call the callee is low however, since it
|
|
|
177 may hurt optimization of the caller's hot path. */
|
|
|
178 if (edge->count.initialized_p () && edge->maybe_hot_p ()
|
|
|
179 && (edge->count.apply_scale (2, 1)
|
|
|
180 > (edge->caller->global.inlined_to
|
|
|
181 ? edge->caller->global.inlined_to->count
|
|
|
182 : edge->caller->count)))
|
|
|
183 hints |= INLINE_HINT_known_hot;
|
|
|
184
|
|
|
185 known_vals.release ();
|
|
|
186 known_contexts.release ();
|
|
|
187 known_aggs.release ();
|
|
|
188 gcc_checking_assert (size >= 0);
|
|
|
189 gcc_checking_assert (time >= 0);
|
|
|
190
|
|
|
191 /* When caching, update the cache entry. */
|
|
|
192 if (edge_growth_cache.exists ())
|
|
|
193 {
|
|
|
194 ipa_fn_summaries->get (edge->callee)->min_size = min_size;
|
|
|
195 if ((int) edge_growth_cache.length () <= edge->uid)
|
|
|
196 edge_growth_cache.safe_grow_cleared (symtab->edges_max_uid);
|
|
|
197 edge_growth_cache[edge->uid].time = time;
|
|
|
198 edge_growth_cache[edge->uid].nonspec_time = nonspec_time;
|
|
|
199
|
|
|
200 edge_growth_cache[edge->uid].size = size + (size >= 0);
|
|
|
201 hints |= simple_edge_hints (edge);
|
|
|
202 edge_growth_cache[edge->uid].hints = hints + 1;
|
|
|
203 }
|
|
|
204 return time;
|
|
|
205 }
|
|
|
206
|
|
|
207
|
|
|
208 /* Return estimated callee growth after inlining EDGE.
|
|
|
209 Only to be called via estimate_edge_size. */
|
|
|
210
|
|
|
211 int
|
|
|
212 do_estimate_edge_size (struct cgraph_edge *edge)
|
|
|
213 {
|
|
|
214 int size;
|
|
|
215 struct cgraph_node *callee;
|
|
|
216 clause_t clause, nonspec_clause;
|
|
|
217 vec<tree> known_vals;
|
|
|
218 vec<ipa_polymorphic_call_context> known_contexts;
|
|
|
219 vec<ipa_agg_jump_function_p> known_aggs;
|
|
|
220
|
|
|
221 /* When we do caching, use do_estimate_edge_time to populate the entry. */
|
|
|
222
|
|
|
223 if (edge_growth_cache.exists ())
|
|
|
224 {
|
|
|
225 do_estimate_edge_time (edge);
|
|
|
226 size = edge_growth_cache[edge->uid].size;
|
|
|
227 gcc_checking_assert (size);
|
|
|
228 return size - (size > 0);
|
|
|
229 }
|
|
|
230
|
|
|
231 callee = edge->callee->ultimate_alias_target ();
|
|
|
232
|
|
|
233 /* Early inliner runs without caching, go ahead and do the dirty work. */
|
|
|
234 gcc_checking_assert (edge->inline_failed);
|
|
|
235 evaluate_properties_for_edge (edge, true,
|
|
|
236 &clause, &nonspec_clause,
|
|
|
237 &known_vals, &known_contexts,
|
|
|
238 &known_aggs);
|
|
|
239 estimate_node_size_and_time (callee, clause, nonspec_clause, known_vals,
|
|
|
240 known_contexts, known_aggs, &size, NULL, NULL,
|
|
|
241 NULL, NULL, vNULL);
|
|
|
242 known_vals.release ();
|
|
|
243 known_contexts.release ();
|
|
|
244 known_aggs.release ();
|
|
|
245 return size;
|
|
|
246 }
|
|
|
247
|
|
|
248
|
|
|
249 /* Estimate the growth of the caller when inlining EDGE.
|
|
|
250 Only to be called via estimate_edge_size. */
|
|
|
251
|
|
|
252 ipa_hints
|
|
|
253 do_estimate_edge_hints (struct cgraph_edge *edge)
|
|
|
254 {
|
|
|
255 ipa_hints hints;
|
|
|
256 struct cgraph_node *callee;
|
|
|
257 clause_t clause, nonspec_clause;
|
|
|
258 vec<tree> known_vals;
|
|
|
259 vec<ipa_polymorphic_call_context> known_contexts;
|
|
|
260 vec<ipa_agg_jump_function_p> known_aggs;
|
|
|
261
|
|
|
262 /* When we do caching, use do_estimate_edge_time to populate the entry. */
|
|
|
263
|
|
|
264 if (edge_growth_cache.exists ())
|
|
|
265 {
|
|
|
266 do_estimate_edge_time (edge);
|
|
|
267 hints = edge_growth_cache[edge->uid].hints;
|
|
|
268 gcc_checking_assert (hints);
|
|
|
269 return hints - 1;
|
|
|
270 }
|
|
|
271
|
|
|
272 callee = edge->callee->ultimate_alias_target ();
|
|
|
273
|
|
|
274 /* Early inliner runs without caching, go ahead and do the dirty work. */
|
|
|
275 gcc_checking_assert (edge->inline_failed);
|
|
|
276 evaluate_properties_for_edge (edge, true,
|
|
|
277 &clause, &nonspec_clause,
|
|
|
278 &known_vals, &known_contexts,
|
|
|
279 &known_aggs);
|
|
|
280 estimate_node_size_and_time (callee, clause, nonspec_clause, known_vals,
|
|
|
281 known_contexts, known_aggs, NULL, NULL,
|
|
|
282 NULL, NULL, &hints, vNULL);
|
|
|
283 known_vals.release ();
|
|
|
284 known_contexts.release ();
|
|
|
285 known_aggs.release ();
|
|
|
286 hints |= simple_edge_hints (edge);
|
|
|
287 return hints;
|
|
|
288 }
|
|
|
289
|
|
|
290 /* Estimate the size of NODE after inlining EDGE which should be an
|
|
|
291 edge to either NODE or a call inlined into NODE. */
|
|
|
292
|
|
|
293 int
|
|
|
294 estimate_size_after_inlining (struct cgraph_node *node,
|
|
|
295 struct cgraph_edge *edge)
|
|
|
296 {
|
|
|
297 struct ipa_call_summary *es = ipa_call_summaries->get (edge);
|
|
|
298 if (!es->predicate || *es->predicate != false)
|
|
|
299 {
|
|
|
300 int size = ipa_fn_summaries->get (node)->size + estimate_edge_growth (edge);
|
|
|
301 gcc_assert (size >= 0);
|
|
|
302 return size;
|
|
|
303 }
|
|
|
304 return ipa_fn_summaries->get (node)->size;
|
|
|
305 }
|
|
|
306
|
|
|
307
|
|
|
308 struct growth_data
|
|
|
309 {
|
|
|
310 struct cgraph_node *node;
|
|
|
311 bool self_recursive;
|
|
|
312 bool uninlinable;
|
|
|
313 int growth;
|
|
|
314 };
|
|
|
315
|
|
|
316
|
|
|
317 /* Worker for do_estimate_growth. Collect growth for all callers. */
|
|
|
318
|
|
|
319 static bool
|
|
|
320 do_estimate_growth_1 (struct cgraph_node *node, void *data)
|
|
|
321 {
|
|
|
322 struct cgraph_edge *e;
|
|
|
323 struct growth_data *d = (struct growth_data *) data;
|
|
|
324
|
|
|
325 for (e = node->callers; e; e = e->next_caller)
|
|
|
326 {
|
|
|
327 gcc_checking_assert (e->inline_failed);
|
|
|
328
|
|
|
329 if (cgraph_inline_failed_type (e->inline_failed) == CIF_FINAL_ERROR
|
|
|
330 || !opt_for_fn (e->caller->decl, optimize))
|
|
|
331 {
|
|
|
332 d->uninlinable = true;
|
|
|
333 continue;
|
|
|
334 }
|
|
|
335
|
|
|
336 if (e->recursive_p ())
|
|
|
337 {
|
|
|
338 d->self_recursive = true;
|
|
|
339 continue;
|
|
|
340 }
|
|
|
341 d->growth += estimate_edge_growth (e);
|
|
|
342 }
|
|
|
343 return false;
|
|
|
344 }
|
|
|
345
|
|
|
346
|
|
|
347 /* Estimate the growth caused by inlining NODE into all callees. */
|
|
|
348
|
|
|
349 int
|
|
|
350 estimate_growth (struct cgraph_node *node)
|
|
|
351 {
|
|
|
352 struct growth_data d = { node, false, false, 0 };
|
|
|
353 struct ipa_fn_summary *info = ipa_fn_summaries->get (node);
|
|
|
354
|
|
|
355 node->call_for_symbol_and_aliases (do_estimate_growth_1, &d, true);
|
|
|
356
|
|
|
357 /* For self recursive functions the growth estimation really should be
|
|
|
358 infinity. We don't want to return very large values because the growth
|
|
|
359 plays various roles in badness computation fractions. Be sure to not
|
|
|
360 return zero or negative growths. */
|
|
|
361 if (d.self_recursive)
|
|
|
362 d.growth = d.growth < info->size ? info->size : d.growth;
|
|
|
363 else if (DECL_EXTERNAL (node->decl) || d.uninlinable)
|
|
|
364 ;
|
|
|
365 else
|
|
|
366 {
|
|
|
367 if (node->will_be_removed_from_program_if_no_direct_calls_p ())
|
|
|
368 d.growth -= info->size;
|
|
|
369 /* COMDAT functions are very often not shared across multiple units
|
|
|
370 since they come from various template instantiations.
|
|
|
371 Take this into account. */
|
|
|
372 else if (DECL_COMDAT (node->decl)
|
|
|
373 && node->can_remove_if_no_direct_calls_p ())
|
|
|
374 d.growth -= (info->size
|
|
|
375 * (100 - PARAM_VALUE (PARAM_COMDAT_SHARING_PROBABILITY))
|
|
|
376 + 50) / 100;
|
|
|
377 }
|
|
|
378
|
|
|
379 return d.growth;
|
|
|
380 }
|
|
|
381
|
|
|
382 /* Verify if there are fewer than MAX_CALLERS. */
|
|
|
383
|
|
|
384 static bool
|
|
|
385 check_callers (cgraph_node *node, int *max_callers)
|
|
|
386 {
|
|
|
387 ipa_ref *ref;
|
|
|
388
|
|
|
389 if (!node->can_remove_if_no_direct_calls_and_refs_p ())
|
|
|
390 return true;
|
|
|
391
|
|
|
392 for (cgraph_edge *e = node->callers; e; e = e->next_caller)
|
|
|
393 {
|
|
|
394 (*max_callers)--;
|
|
|
395 if (!*max_callers
|
|
|
396 || cgraph_inline_failed_type (e->inline_failed) == CIF_FINAL_ERROR)
|
|
|
397 return true;
|
|
|
398 }
|
|
|
399
|
|
|
400 FOR_EACH_ALIAS (node, ref)
|
|
|
401 if (check_callers (dyn_cast <cgraph_node *> (ref->referring), max_callers))
|
|
|
402 return true;
|
|
|
403
|
|
|
404 return false;
|
|
|
405 }
|
|
|
406
|
|
|
407
|
|
|
408 /* Make cheap estimation if growth of NODE is likely positive knowing
|
|
|
409 EDGE_GROWTH of one particular edge.
|
|
|
410 We assume that most of other edges will have similar growth
|
|
|
411 and skip computation if there are too many callers. */
|
|
|
412
|
|
|
413 bool
|
|
|
414 growth_likely_positive (struct cgraph_node *node,
|
|
|
415 int edge_growth)
|
|
|
416 {
|
|
|
417 int max_callers;
|
|
|
418 struct cgraph_edge *e;
|
|
|
419 gcc_checking_assert (edge_growth > 0);
|
|
|
420
|
|
|
421 /* First quickly check if NODE is removable at all. */
|
|
|
422 if (DECL_EXTERNAL (node->decl))
|
|
|
423 return true;
|
|
|
424 if (!node->can_remove_if_no_direct_calls_and_refs_p ()
|
|
|
425 || node->address_taken)
|
|
|
426 return true;
|
|
|
427
|
|
|
428 max_callers = ipa_fn_summaries->get (node)->size * 4 / edge_growth + 2;
|
|
|
429
|
|
|
430 for (e = node->callers; e; e = e->next_caller)
|
|
|
431 {
|
|
|
432 max_callers--;
|
|
|
433 if (!max_callers
|
|
|
434 || cgraph_inline_failed_type (e->inline_failed) == CIF_FINAL_ERROR)
|
|
|
435 return true;
|
|
|
436 }
|
|
|
437
|
|
|
438 ipa_ref *ref;
|
|
|
439 FOR_EACH_ALIAS (node, ref)
|
|
|
440 if (check_callers (dyn_cast <cgraph_node *> (ref->referring), &max_callers))
|
|
|
441 return true;
|
|
|
442
|
|
|
443 /* Unlike for functions called once, we play unsafe with
|
|
|
444 COMDATs. We can allow that since we know functions
|
|
|
445 in consideration are small (and thus risk is small) and
|
|
|
446 moreover grow estimates already accounts that COMDAT
|
|
|
447 functions may or may not disappear when eliminated from
|
|
|
448 current unit. With good probability making aggressive
|
|
|
449 choice in all units is going to make overall program
|
|
|
450 smaller. */
|
|
|
451 if (DECL_COMDAT (node->decl))
|
|
|
452 {
|
|
|
453 if (!node->can_remove_if_no_direct_calls_p ())
|
|
|
454 return true;
|
|
|
455 }
|
|
|
456 else if (!node->will_be_removed_from_program_if_no_direct_calls_p ())
|
|
|
457 return true;
|
|
|
458
|
|
|
459 return estimate_growth (node) > 0;
|
|
|
460 }
|
