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