Daily bump.
[official-gcc.git] / gcc / ipa-inline-analysis.c
blob0312beca2b8633b55519e351f56cc5658fe6899d
1 /* Analysis used by inlining decision heuristics.
2 Copyright (C) 2003-2021 Free Software Foundation, Inc.
3 Contributed by Jan Hubicka
5 This file is part of GCC.
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.
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.
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/>. */
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 "cfganal.h"
38 #include "gimple-iterator.h"
39 #include "tree-cfg.h"
40 #include "tree-ssa-loop-niter.h"
41 #include "tree-ssa-loop.h"
42 #include "symbol-summary.h"
43 #include "ipa-prop.h"
44 #include "ipa-fnsummary.h"
45 #include "ipa-inline.h"
46 #include "cfgloop.h"
47 #include "tree-scalar-evolution.h"
48 #include "ipa-utils.h"
49 #include "cfgexpand.h"
50 #include "gimplify.h"
52 /* Cached node/edge growths. */
53 fast_call_summary<edge_growth_cache_entry *, va_heap> *edge_growth_cache = NULL;
55 /* The context cache remembers estimated time/size and hints for given
56 ipa_call_context of a call. */
57 class node_context_cache_entry
59 public:
60 ipa_cached_call_context ctx;
61 sreal time, nonspec_time;
62 int size;
63 ipa_hints hints;
65 node_context_cache_entry ()
66 : ctx ()
69 ~node_context_cache_entry ()
71 ctx.release ();
75 /* At the moment we implement primitive single entry LRU cache. */
76 class node_context_summary
78 public:
79 node_context_cache_entry entry;
81 node_context_summary ()
82 : entry ()
85 ~node_context_summary ()
90 /* Summary holding the context cache. */
91 static fast_function_summary <node_context_summary *, va_heap>
92 *node_context_cache = NULL;
93 /* Statistics about the context cache effectivity. */
94 static long node_context_cache_hit, node_context_cache_miss,
95 node_context_cache_clear;
97 /* Give initial reasons why inlining would fail on EDGE. This gets either
98 nullified or usually overwritten by more precise reasons later. */
100 void
101 initialize_inline_failed (struct cgraph_edge *e)
103 struct cgraph_node *callee = e->callee;
105 if (e->inline_failed && e->inline_failed != CIF_BODY_NOT_AVAILABLE
106 && cgraph_inline_failed_type (e->inline_failed) == CIF_FINAL_ERROR)
108 else if (e->indirect_unknown_callee)
109 e->inline_failed = CIF_INDIRECT_UNKNOWN_CALL;
110 else if (!callee->definition)
111 e->inline_failed = CIF_BODY_NOT_AVAILABLE;
112 else if (callee->redefined_extern_inline)
113 e->inline_failed = CIF_REDEFINED_EXTERN_INLINE;
114 else
115 e->inline_failed = CIF_FUNCTION_NOT_CONSIDERED;
116 gcc_checking_assert (!e->call_stmt_cannot_inline_p
117 || cgraph_inline_failed_type (e->inline_failed)
118 == CIF_FINAL_ERROR);
121 /* Allocate edge growth caches. */
123 void
124 initialize_growth_caches ()
126 edge_growth_cache
127 = new fast_call_summary<edge_growth_cache_entry *, va_heap> (symtab);
128 node_context_cache
129 = new fast_function_summary<node_context_summary *, va_heap> (symtab);
130 edge_growth_cache->disable_duplication_hook ();
131 node_context_cache->disable_insertion_hook ();
132 node_context_cache->disable_duplication_hook ();
135 /* Free growth caches. */
137 void
138 free_growth_caches (void)
140 delete edge_growth_cache;
141 delete node_context_cache;
142 edge_growth_cache = NULL;
143 node_context_cache = NULL;
144 if (dump_file)
145 fprintf (dump_file, "node context cache: %li hits, %li misses,"
146 " %li initializations\n",
147 node_context_cache_hit, node_context_cache_miss,
148 node_context_cache_clear);
149 node_context_cache_hit = 0;
150 node_context_cache_miss = 0;
151 node_context_cache_clear = 0;
154 /* Return hints derived from EDGE. */
157 simple_edge_hints (struct cgraph_edge *edge)
159 int hints = 0;
160 struct cgraph_node *to = (edge->caller->inlined_to
161 ? edge->caller->inlined_to : edge->caller);
162 struct cgraph_node *callee = edge->callee->ultimate_alias_target ();
163 int to_scc_no = ipa_fn_summaries->get (to)->scc_no;
164 int callee_scc_no = ipa_fn_summaries->get (callee)->scc_no;
166 if (to_scc_no && to_scc_no == callee_scc_no && !edge->recursive_p ())
167 hints |= INLINE_HINT_same_scc;
169 if (cross_module_call_p (edge))
170 hints |= INLINE_HINT_cross_module;
172 return hints;
175 /* Estimate the time cost for the caller when inlining EDGE.
176 Only to be called via estimate_edge_time, that handles the
177 caching mechanism.
179 When caching, also update the cache entry. Compute both time and
180 size, since we always need both metrics eventually. */
182 sreal
183 do_estimate_edge_time (struct cgraph_edge *edge, sreal *ret_nonspec_time)
185 sreal time, nonspec_time;
186 int size;
187 ipa_hints hints;
188 struct cgraph_node *callee;
189 clause_t clause, nonspec_clause;
190 ipa_auto_call_arg_values avals;
191 class ipa_call_summary *es = ipa_call_summaries->get (edge);
192 int min_size = -1;
194 callee = edge->callee->ultimate_alias_target ();
196 gcc_checking_assert (edge->inline_failed);
197 evaluate_properties_for_edge (edge, true, &clause, &nonspec_clause,
198 &avals, true);
199 ipa_call_context ctx (callee, clause, nonspec_clause, es->param, &avals);
200 if (node_context_cache != NULL)
202 node_context_summary *e = node_context_cache->get_create (callee);
203 if (e->entry.ctx.equal_to (ctx))
205 node_context_cache_hit++;
206 size = e->entry.size;
207 time = e->entry.time;
208 nonspec_time = e->entry.nonspec_time;
209 hints = e->entry.hints;
210 if (flag_checking
211 && !opt_for_fn (callee->decl, flag_profile_partial_training)
212 && !callee->count.ipa_p ())
214 ipa_call_estimates chk_estimates;
215 ctx.estimate_size_and_time (&chk_estimates);
216 gcc_assert (chk_estimates.size == size
217 && chk_estimates.time == time
218 && chk_estimates.nonspecialized_time == nonspec_time
219 && chk_estimates.hints == hints);
222 else
224 if (e->entry.ctx.exists_p ())
225 node_context_cache_miss++;
226 else
227 node_context_cache_clear++;
228 e->entry.ctx.release ();
229 ipa_call_estimates estimates;
230 ctx.estimate_size_and_time (&estimates);
231 size = estimates.size;
232 e->entry.size = size;
233 time = estimates.time;
234 e->entry.time = time;
235 nonspec_time = estimates.nonspecialized_time;
236 e->entry.nonspec_time = nonspec_time;
237 hints = estimates.hints;
238 e->entry.hints = hints;
239 e->entry.ctx.duplicate_from (ctx);
242 else
244 ipa_call_estimates estimates;
245 ctx.estimate_size_and_time (&estimates);
246 size = estimates.size;
247 time = estimates.time;
248 nonspec_time = estimates.nonspecialized_time;
249 hints = estimates.hints;
252 /* When we have profile feedback, we can quite safely identify hot
253 edges and for those we disable size limits. Don't do that when
254 probability that caller will call the callee is low however, since it
255 may hurt optimization of the caller's hot path. */
256 if (edge->count.ipa ().initialized_p () && edge->maybe_hot_p ()
257 && (edge->count.ipa ().apply_scale (2, 1)
258 > (edge->caller->inlined_to
259 ? edge->caller->inlined_to->count.ipa ()
260 : edge->caller->count.ipa ())))
261 hints |= INLINE_HINT_known_hot;
263 gcc_checking_assert (size >= 0);
264 gcc_checking_assert (time >= 0);
266 /* When caching, update the cache entry. */
267 if (edge_growth_cache != NULL)
269 if (min_size >= 0)
270 ipa_fn_summaries->get (edge->callee->function_symbol ())->min_size
271 = min_size;
272 edge_growth_cache_entry *entry
273 = edge_growth_cache->get_create (edge);
274 entry->time = time;
275 entry->nonspec_time = nonspec_time;
277 entry->size = size + (size >= 0);
278 hints |= simple_edge_hints (edge);
279 entry->hints = hints + 1;
281 if (ret_nonspec_time)
282 *ret_nonspec_time = nonspec_time;
283 return time;
286 /* Reset cache for NODE.
287 This must be done each time NODE body is modified. */
288 void
289 reset_node_cache (struct cgraph_node *node)
291 if (node_context_cache)
292 node_context_cache->remove (node);
295 /* Remove EDGE from caches once it was inlined. */
296 void
297 ipa_remove_from_growth_caches (struct cgraph_edge *edge)
299 if (node_context_cache)
300 node_context_cache->remove (edge->callee);
301 if (edge_growth_cache)
302 edge_growth_cache->remove (edge);
305 /* Return estimated callee growth after inlining EDGE.
306 Only to be called via estimate_edge_size. */
309 do_estimate_edge_size (struct cgraph_edge *edge)
311 int size;
312 struct cgraph_node *callee;
313 clause_t clause, nonspec_clause;
315 /* When we do caching, use do_estimate_edge_time to populate the entry. */
317 if (edge_growth_cache != NULL)
319 do_estimate_edge_time (edge);
320 size = edge_growth_cache->get (edge)->size;
321 gcc_checking_assert (size);
322 return size - (size > 0);
325 callee = edge->callee->ultimate_alias_target ();
327 /* Early inliner runs without caching, go ahead and do the dirty work. */
328 gcc_checking_assert (edge->inline_failed);
329 ipa_auto_call_arg_values avals;
330 evaluate_properties_for_edge (edge, true, &clause, &nonspec_clause,
331 &avals, true);
332 ipa_call_context ctx (callee, clause, nonspec_clause, vNULL, &avals);
333 ipa_call_estimates estimates;
334 ctx.estimate_size_and_time (&estimates, false, false);
335 return estimates.size;
339 /* Estimate the growth of the caller when inlining EDGE.
340 Only to be called via estimate_edge_size. */
342 ipa_hints
343 do_estimate_edge_hints (struct cgraph_edge *edge)
345 struct cgraph_node *callee;
346 clause_t clause, nonspec_clause;
348 /* When we do caching, use do_estimate_edge_time to populate the entry. */
350 if (edge_growth_cache != NULL)
352 do_estimate_edge_time (edge);
353 ipa_hints hints = edge_growth_cache->get (edge)->hints;
354 gcc_checking_assert (hints);
355 return hints - 1;
358 callee = edge->callee->ultimate_alias_target ();
360 /* Early inliner runs without caching, go ahead and do the dirty work. */
361 gcc_checking_assert (edge->inline_failed);
362 ipa_auto_call_arg_values avals;
363 evaluate_properties_for_edge (edge, true, &clause, &nonspec_clause,
364 &avals, true);
365 ipa_call_context ctx (callee, clause, nonspec_clause, vNULL, &avals);
366 ipa_call_estimates estimates;
367 ctx.estimate_size_and_time (&estimates, false, true);
368 ipa_hints hints = estimates.hints | simple_edge_hints (edge);
369 return hints;
372 /* Estimate the size of NODE after inlining EDGE which should be an
373 edge to either NODE or a call inlined into NODE. */
376 estimate_size_after_inlining (struct cgraph_node *node,
377 struct cgraph_edge *edge)
379 class ipa_call_summary *es = ipa_call_summaries->get (edge);
380 ipa_size_summary *s = ipa_size_summaries->get (node);
381 if (!es->predicate || *es->predicate != false)
383 int size = s->size + estimate_edge_growth (edge);
384 gcc_assert (size >= 0);
385 return size;
387 return s->size;
391 struct growth_data
393 struct cgraph_node *node;
394 bool self_recursive;
395 bool uninlinable;
396 int growth;
397 int cap;
401 /* Worker for do_estimate_growth. Collect growth for all callers. */
403 static bool
404 do_estimate_growth_1 (struct cgraph_node *node, void *data)
406 struct cgraph_edge *e;
407 struct growth_data *d = (struct growth_data *) data;
409 for (e = node->callers; e; e = e->next_caller)
411 gcc_checking_assert (e->inline_failed);
413 if (cgraph_inline_failed_type (e->inline_failed) == CIF_FINAL_ERROR
414 || !opt_for_fn (e->caller->decl, optimize))
416 d->uninlinable = true;
417 if (d->cap < INT_MAX)
418 return true;
419 continue;
422 if (e->recursive_p ())
424 d->self_recursive = true;
425 if (d->cap < INT_MAX)
426 return true;
427 continue;
429 d->growth += estimate_edge_growth (e);
430 if (d->growth > d->cap)
431 return true;
433 return false;
436 /* Return estimated savings for eliminating offline copy of NODE by inlining
437 it everywhere. */
439 static int
440 offline_size (struct cgraph_node *node, ipa_size_summary *info)
442 if (!DECL_EXTERNAL (node->decl))
444 if (node->will_be_removed_from_program_if_no_direct_calls_p ())
445 return info->size;
446 /* COMDAT functions are very often not shared across multiple units
447 since they come from various template instantiations.
448 Take this into account. */
449 else if (DECL_COMDAT (node->decl)
450 && node->can_remove_if_no_direct_calls_p ())
452 int prob = opt_for_fn (node->decl, param_comdat_sharing_probability);
453 return (info->size * (100 - prob) + 50) / 100;
456 return 0;
459 /* Estimate the growth caused by inlining NODE into all callers. */
462 estimate_growth (struct cgraph_node *node)
464 struct growth_data d = { node, false, false, 0, INT_MAX };
465 ipa_size_summary *info = ipa_size_summaries->get (node);
467 if (node->call_for_symbol_and_aliases (do_estimate_growth_1, &d, true))
468 return 1;
470 /* For self recursive functions the growth estimation really should be
471 infinity. We don't want to return very large values because the growth
472 plays various roles in badness computation fractions. Be sure to not
473 return zero or negative growths. */
474 if (d.self_recursive)
475 d.growth = d.growth < info->size ? info->size : d.growth;
476 else if (!d.uninlinable)
477 d.growth -= offline_size (node, info);
479 return d.growth;
482 /* Verify if there are fewer than MAX_CALLERS. */
484 static bool
485 check_callers (cgraph_node *node, int *growth, int *n, int offline,
486 int min_size, struct cgraph_edge *known_edge)
488 ipa_ref *ref;
490 if (!node->can_remove_if_no_direct_calls_and_refs_p ())
491 return true;
493 for (cgraph_edge *e = node->callers; e; e = e->next_caller)
495 edge_growth_cache_entry *entry;
497 if (e == known_edge)
498 continue;
499 if (cgraph_inline_failed_type (e->inline_failed) == CIF_FINAL_ERROR)
500 return true;
501 if (edge_growth_cache != NULL
502 && (entry = edge_growth_cache->get (e)) != NULL
503 && entry->size != 0)
504 *growth += entry->size - (entry->size > 0);
505 else
507 class ipa_call_summary *es = ipa_call_summaries->get (e);
508 if (!es)
509 return true;
510 *growth += min_size - es->call_stmt_size;
511 if (--(*n) < 0)
512 return false;
514 if (*growth > offline)
515 return true;
518 if (*n > 0)
519 FOR_EACH_ALIAS (node, ref)
520 if (check_callers (dyn_cast <cgraph_node *> (ref->referring), growth, n,
521 offline, min_size, known_edge))
522 return true;
524 return false;
528 /* Decide if growth of NODE is positive. This is cheaper than calculating
529 actual growth. If edge growth of KNOWN_EDGE is known
530 it is passed by EDGE_GROWTH. */
532 bool
533 growth_positive_p (struct cgraph_node *node,
534 struct cgraph_edge * known_edge, int edge_growth)
536 struct cgraph_edge *e;
538 ipa_size_summary *s = ipa_size_summaries->get (node);
540 /* First quickly check if NODE is removable at all. */
541 int offline = offline_size (node, s);
542 if (offline <= 0 && known_edge && edge_growth > 0)
543 return true;
545 int min_size = ipa_fn_summaries->get (node)->min_size;
546 int n = 10;
548 int min_growth = known_edge ? edge_growth : 0;
549 for (e = node->callers; e; e = e->next_caller)
551 edge_growth_cache_entry *entry;
553 if (cgraph_inline_failed_type (e->inline_failed) == CIF_FINAL_ERROR)
554 return true;
555 if (e == known_edge)
556 continue;
557 if (edge_growth_cache != NULL
558 && (entry = edge_growth_cache->get (e)) != NULL
559 && entry->size != 0)
560 min_growth += entry->size - (entry->size > 0);
561 else
563 class ipa_call_summary *es = ipa_call_summaries->get (e);
564 if (!es)
565 return true;
566 min_growth += min_size - es->call_stmt_size;
567 if (--n <= 0)
568 break;
570 if (min_growth > offline)
571 return true;
574 ipa_ref *ref;
575 if (n > 0)
576 FOR_EACH_ALIAS (node, ref)
577 if (check_callers (dyn_cast <cgraph_node *> (ref->referring),
578 &min_growth, &n, offline, min_size, known_edge))
579 return true;
581 struct growth_data d = { node, false, false, 0, offline };
582 if (node->call_for_symbol_and_aliases (do_estimate_growth_1, &d, true))
583 return true;
584 if (d.self_recursive || d.uninlinable)
585 return true;
586 return (d.growth > offline);