Mercurial > hg > CbC > CbC_gcc

comparison gcc/ipa-inline-analysis.c @ 111:04ced10e8804

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
gcc 7
author kono
date Fri, 27 Oct 2017 22:46:09 +0900
parents
children 84e7813d76e9
comparison
equal deleted inserted replaced
68:561a7518be6b 111:04ced10e8804
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 }