ada: Fix spurious -Wstringop-overflow with link time optimization
[official-gcc.git] / gcc / ipa-inline-analysis.cc
bloba4ef955cd795ce22d9b48dd64fe44a007f39f9e8
1 /* Analysis used by inlining decision heuristics.
2 Copyright (C) 2003-2023 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"
51 #include "attribs.h"
53 /* Cached node/edge growths. */
54 fast_call_summary<edge_growth_cache_entry *, va_heap> *edge_growth_cache = NULL;
56 /* The context cache remembers estimated time/size and hints for given
57 ipa_call_context of a call. */
58 class node_context_cache_entry
60 public:
61 ipa_cached_call_context ctx;
62 sreal time, nonspec_time;
63 int size;
64 ipa_hints hints;
66 node_context_cache_entry ()
67 : ctx ()
70 ~node_context_cache_entry ()
72 ctx.release ();
76 /* At the moment we implement primitive single entry LRU cache. */
77 class node_context_summary
79 public:
80 node_context_cache_entry entry;
82 node_context_summary ()
83 : entry ()
86 ~node_context_summary ()
91 /* Summary holding the context cache. */
92 static fast_function_summary <node_context_summary *, va_heap>
93 *node_context_cache = NULL;
94 /* Statistics about the context cache effectivity. */
95 static long node_context_cache_hit, node_context_cache_miss,
96 node_context_cache_clear;
98 /* Give initial reasons why inlining would fail on EDGE. This gets either
99 nullified or usually overwritten by more precise reasons later. */
101 void
102 initialize_inline_failed (struct cgraph_edge *e)
104 struct cgraph_node *callee = e->callee;
106 if (e->inline_failed && e->inline_failed != CIF_BODY_NOT_AVAILABLE
107 && cgraph_inline_failed_type (e->inline_failed) == CIF_FINAL_ERROR)
109 else if (e->indirect_unknown_callee)
110 e->inline_failed = CIF_INDIRECT_UNKNOWN_CALL;
111 else if (!callee->definition)
112 e->inline_failed = CIF_BODY_NOT_AVAILABLE;
113 else if (callee->redefined_extern_inline)
114 e->inline_failed = CIF_REDEFINED_EXTERN_INLINE;
115 else
116 e->inline_failed = CIF_FUNCTION_NOT_CONSIDERED;
117 gcc_checking_assert (!e->call_stmt_cannot_inline_p
118 || cgraph_inline_failed_type (e->inline_failed)
119 == CIF_FINAL_ERROR);
122 /* Allocate edge growth caches. */
124 void
125 initialize_growth_caches ()
127 edge_growth_cache
128 = new fast_call_summary<edge_growth_cache_entry *, va_heap> (symtab);
129 node_context_cache
130 = new fast_function_summary<node_context_summary *, va_heap> (symtab);
131 edge_growth_cache->disable_duplication_hook ();
132 node_context_cache->disable_insertion_hook ();
133 node_context_cache->disable_duplication_hook ();
136 /* Free growth caches. */
138 void
139 free_growth_caches (void)
141 delete edge_growth_cache;
142 delete node_context_cache;
143 edge_growth_cache = NULL;
144 node_context_cache = NULL;
145 if (dump_file)
146 fprintf (dump_file, "node context cache: %li hits, %li misses,"
147 " %li initializations\n",
148 node_context_cache_hit, node_context_cache_miss,
149 node_context_cache_clear);
150 node_context_cache_hit = 0;
151 node_context_cache_miss = 0;
152 node_context_cache_clear = 0;
155 /* Return hints derived from EDGE. */
158 simple_edge_hints (struct cgraph_edge *edge)
160 int hints = 0;
161 struct cgraph_node *to = (edge->caller->inlined_to
162 ? edge->caller->inlined_to : edge->caller);
163 struct cgraph_node *callee = edge->callee->ultimate_alias_target ();
164 int to_scc_no = ipa_fn_summaries->get (to)->scc_no;
165 int callee_scc_no = ipa_fn_summaries->get (callee)->scc_no;
167 if (to_scc_no && to_scc_no == callee_scc_no && !edge->recursive_p ())
168 hints |= INLINE_HINT_same_scc;
170 if (cross_module_call_p (edge))
171 hints |= INLINE_HINT_cross_module;
173 return hints;
176 /* Estimate the time cost for the caller when inlining EDGE.
177 Only to be called via estimate_edge_time, that handles the
178 caching mechanism.
180 When caching, also update the cache entry. Compute both time and
181 size, since we always need both metrics eventually. */
183 sreal
184 do_estimate_edge_time (struct cgraph_edge *edge, sreal *ret_nonspec_time)
186 sreal time, nonspec_time;
187 int size;
188 ipa_hints hints;
189 struct cgraph_node *callee;
190 clause_t clause, nonspec_clause;
191 ipa_auto_call_arg_values avals;
192 class ipa_call_summary *es = ipa_call_summaries->get (edge);
193 int min_size = -1;
195 callee = edge->callee->ultimate_alias_target ();
197 gcc_checking_assert (edge->inline_failed);
198 evaluate_properties_for_edge (edge, true, &clause, &nonspec_clause,
199 &avals, true);
200 ipa_call_context ctx (callee, clause, nonspec_clause, es->param, &avals);
201 if (node_context_cache != NULL)
203 node_context_summary *e = node_context_cache->get_create (callee);
204 if (e->entry.ctx.equal_to (ctx))
206 node_context_cache_hit++;
207 size = e->entry.size;
208 time = e->entry.time;
209 nonspec_time = e->entry.nonspec_time;
210 hints = e->entry.hints;
211 if (flag_checking
212 && !opt_for_fn (callee->decl, flag_profile_partial_training)
213 && !callee->count.ipa_p ())
215 ipa_call_estimates chk_estimates;
216 ctx.estimate_size_and_time (&chk_estimates);
217 gcc_assert (chk_estimates.size == size
218 && chk_estimates.time == time
219 && chk_estimates.nonspecialized_time == nonspec_time
220 && chk_estimates.hints == hints);
223 else
225 if (e->entry.ctx.exists_p ())
226 node_context_cache_miss++;
227 else
228 node_context_cache_clear++;
229 e->entry.ctx.release ();
230 ipa_call_estimates estimates;
231 ctx.estimate_size_and_time (&estimates);
232 size = estimates.size;
233 e->entry.size = size;
234 time = estimates.time;
235 e->entry.time = time;
236 nonspec_time = estimates.nonspecialized_time;
237 e->entry.nonspec_time = nonspec_time;
238 hints = estimates.hints;
239 e->entry.hints = hints;
240 e->entry.ctx.duplicate_from (ctx);
243 else
245 ipa_call_estimates estimates;
246 ctx.estimate_size_and_time (&estimates);
247 size = estimates.size;
248 time = estimates.time;
249 nonspec_time = estimates.nonspecialized_time;
250 hints = estimates.hints;
253 /* When we have profile feedback or function attribute, we can quite safely
254 identify hot edges and for those we disable size limits. Don't do that
255 when probability that caller will call the callee is low however, since it
256 may hurt optimization of the caller's hot path. */
257 if ((edge->count.ipa ().initialized_p () && edge->maybe_hot_p ()
258 && (edge->count.ipa () * 2
259 > (edge->caller->inlined_to
260 ? edge->caller->inlined_to->count.ipa ()
261 : edge->caller->count.ipa ())))
262 || (lookup_attribute ("hot", DECL_ATTRIBUTES (edge->caller->decl))
263 != NULL
264 && lookup_attribute ("hot", DECL_ATTRIBUTES (edge->callee->decl))
265 != NULL))
266 hints |= INLINE_HINT_known_hot;
268 gcc_checking_assert (size >= 0);
269 gcc_checking_assert (time >= 0);
271 /* When caching, update the cache entry. */
272 if (edge_growth_cache != NULL)
274 if (min_size >= 0)
275 ipa_fn_summaries->get (edge->callee->function_symbol ())->min_size
276 = min_size;
277 edge_growth_cache_entry *entry
278 = edge_growth_cache->get_create (edge);
279 entry->time = time;
280 entry->nonspec_time = nonspec_time;
282 entry->size = size + (size >= 0);
283 hints |= simple_edge_hints (edge);
284 entry->hints = hints + 1;
286 if (ret_nonspec_time)
287 *ret_nonspec_time = nonspec_time;
288 return time;
291 /* Reset cache for NODE.
292 This must be done each time NODE body is modified. */
293 void
294 reset_node_cache (struct cgraph_node *node)
296 if (node_context_cache)
297 node_context_cache->remove (node);
300 /* Remove EDGE from caches once it was inlined. */
301 void
302 ipa_remove_from_growth_caches (struct cgraph_edge *edge)
304 if (node_context_cache)
305 node_context_cache->remove (edge->callee);
306 if (edge_growth_cache)
307 edge_growth_cache->remove (edge);
310 /* Return estimated callee growth after inlining EDGE.
311 Only to be called via estimate_edge_size. */
314 do_estimate_edge_size (struct cgraph_edge *edge)
316 int size;
317 struct cgraph_node *callee;
318 clause_t clause, nonspec_clause;
320 /* When we do caching, use do_estimate_edge_time to populate the entry. */
322 if (edge_growth_cache != NULL)
324 do_estimate_edge_time (edge);
325 size = edge_growth_cache->get (edge)->size;
326 gcc_checking_assert (size);
327 return size - (size > 0);
330 callee = edge->callee->ultimate_alias_target ();
332 /* Early inliner runs without caching, go ahead and do the dirty work. */
333 gcc_checking_assert (edge->inline_failed);
334 ipa_auto_call_arg_values avals;
335 evaluate_properties_for_edge (edge, true, &clause, &nonspec_clause,
336 &avals, true);
337 ipa_call_context ctx (callee, clause, nonspec_clause, vNULL, &avals);
338 ipa_call_estimates estimates;
339 ctx.estimate_size_and_time (&estimates, false, false);
340 return estimates.size;
344 /* Estimate the growth of the caller when inlining EDGE.
345 Only to be called via estimate_edge_size. */
347 ipa_hints
348 do_estimate_edge_hints (struct cgraph_edge *edge)
350 struct cgraph_node *callee;
351 clause_t clause, nonspec_clause;
353 /* When we do caching, use do_estimate_edge_time to populate the entry. */
355 if (edge_growth_cache != NULL)
357 do_estimate_edge_time (edge);
358 ipa_hints hints = edge_growth_cache->get (edge)->hints;
359 gcc_checking_assert (hints);
360 return hints - 1;
363 callee = edge->callee->ultimate_alias_target ();
365 /* Early inliner runs without caching, go ahead and do the dirty work. */
366 gcc_checking_assert (edge->inline_failed);
367 ipa_auto_call_arg_values avals;
368 evaluate_properties_for_edge (edge, true, &clause, &nonspec_clause,
369 &avals, true);
370 ipa_call_context ctx (callee, clause, nonspec_clause, vNULL, &avals);
371 ipa_call_estimates estimates;
372 ctx.estimate_size_and_time (&estimates, false, true);
373 ipa_hints hints = estimates.hints | simple_edge_hints (edge);
374 return hints;
377 /* Estimate the size of NODE after inlining EDGE which should be an
378 edge to either NODE or a call inlined into NODE. */
381 estimate_size_after_inlining (struct cgraph_node *node,
382 struct cgraph_edge *edge)
384 class ipa_call_summary *es = ipa_call_summaries->get (edge);
385 ipa_size_summary *s = ipa_size_summaries->get (node);
386 if (!es->predicate || *es->predicate != false)
388 int size = s->size + estimate_edge_growth (edge);
389 gcc_assert (size >= 0);
390 return size;
392 return s->size;
396 struct growth_data
398 struct cgraph_node *node;
399 bool self_recursive;
400 bool uninlinable;
401 int growth;
402 int cap;
406 /* Worker for do_estimate_growth. Collect growth for all callers. */
408 static bool
409 do_estimate_growth_1 (struct cgraph_node *node, void *data)
411 struct cgraph_edge *e;
412 struct growth_data *d = (struct growth_data *) data;
414 for (e = node->callers; e; e = e->next_caller)
416 gcc_checking_assert (e->inline_failed);
418 if (cgraph_inline_failed_type (e->inline_failed) == CIF_FINAL_ERROR
419 || !opt_for_fn (e->caller->decl, optimize))
421 d->uninlinable = true;
422 if (d->cap < INT_MAX)
423 return true;
424 continue;
427 if (e->recursive_p ())
429 d->self_recursive = true;
430 if (d->cap < INT_MAX)
431 return true;
432 continue;
434 d->growth += estimate_edge_growth (e);
435 if (d->growth > d->cap)
436 return true;
438 return false;
441 /* Return estimated savings for eliminating offline copy of NODE by inlining
442 it everywhere. */
444 static int
445 offline_size (struct cgraph_node *node, ipa_size_summary *info)
447 if (!DECL_EXTERNAL (node->decl))
449 if (node->will_be_removed_from_program_if_no_direct_calls_p ())
450 return info->size;
451 /* COMDAT functions are very often not shared across multiple units
452 since they come from various template instantiations.
453 Take this into account. */
454 else if (DECL_COMDAT (node->decl)
455 && node->can_remove_if_no_direct_calls_p ())
457 int prob = opt_for_fn (node->decl, param_comdat_sharing_probability);
458 return (info->size * (100 - prob) + 50) / 100;
461 return 0;
464 /* Estimate the growth caused by inlining NODE into all callers. */
467 estimate_growth (struct cgraph_node *node)
469 struct growth_data d = { node, false, false, 0, INT_MAX };
470 ipa_size_summary *info = ipa_size_summaries->get (node);
472 if (node->call_for_symbol_and_aliases (do_estimate_growth_1, &d, true))
473 return 1;
475 /* For self recursive functions the growth estimation really should be
476 infinity. We don't want to return very large values because the growth
477 plays various roles in badness computation fractions. Be sure to not
478 return zero or negative growths. */
479 if (d.self_recursive)
480 d.growth = d.growth < info->size ? info->size : d.growth;
481 else if (!d.uninlinable)
482 d.growth -= offline_size (node, info);
484 return d.growth;
487 /* Verify if there are fewer than MAX_CALLERS. */
489 static bool
490 check_callers (cgraph_node *node, int *growth, int *n, int offline,
491 int min_size, struct cgraph_edge *known_edge)
493 ipa_ref *ref;
495 if (!node->can_remove_if_no_direct_calls_and_refs_p ())
496 return true;
498 for (cgraph_edge *e = node->callers; e; e = e->next_caller)
500 edge_growth_cache_entry *entry;
502 if (e == known_edge)
503 continue;
504 if (cgraph_inline_failed_type (e->inline_failed) == CIF_FINAL_ERROR)
505 return true;
506 if (edge_growth_cache != NULL
507 && (entry = edge_growth_cache->get (e)) != NULL
508 && entry->size != 0)
509 *growth += entry->size - (entry->size > 0);
510 else
512 class ipa_call_summary *es = ipa_call_summaries->get (e);
513 if (!es)
514 return true;
515 *growth += min_size - es->call_stmt_size;
516 if (--(*n) < 0)
517 return false;
519 if (*growth > offline)
520 return true;
523 if (*n > 0)
524 FOR_EACH_ALIAS (node, ref)
525 if (check_callers (dyn_cast <cgraph_node *> (ref->referring), growth, n,
526 offline, min_size, known_edge))
527 return true;
529 return false;
533 /* Decide if growth of NODE is positive. This is cheaper than calculating
534 actual growth. If edge growth of KNOWN_EDGE is known
535 it is passed by EDGE_GROWTH. */
537 bool
538 growth_positive_p (struct cgraph_node *node,
539 struct cgraph_edge * known_edge, int edge_growth)
541 struct cgraph_edge *e;
543 ipa_size_summary *s = ipa_size_summaries->get (node);
545 /* First quickly check if NODE is removable at all. */
546 int offline = offline_size (node, s);
547 if (offline <= 0 && known_edge && edge_growth > 0)
548 return true;
550 int min_size = ipa_fn_summaries->get (node)->min_size;
551 int n = 10;
553 int min_growth = known_edge ? edge_growth : 0;
554 for (e = node->callers; e; e = e->next_caller)
556 edge_growth_cache_entry *entry;
558 if (cgraph_inline_failed_type (e->inline_failed) == CIF_FINAL_ERROR)
559 return true;
560 if (e == known_edge)
561 continue;
562 if (edge_growth_cache != NULL
563 && (entry = edge_growth_cache->get (e)) != NULL
564 && entry->size != 0)
565 min_growth += entry->size - (entry->size > 0);
566 else
568 class ipa_call_summary *es = ipa_call_summaries->get (e);
569 if (!es)
570 return true;
571 min_growth += min_size - es->call_stmt_size;
572 if (--n <= 0)
573 break;
575 if (min_growth > offline)
576 return true;
579 ipa_ref *ref;
580 if (n > 0)
581 FOR_EACH_ALIAS (node, ref)
582 if (check_callers (dyn_cast <cgraph_node *> (ref->referring),
583 &min_growth, &n, offline, min_size, known_edge))
584 return true;
586 struct growth_data d = { node, false, false, 0, offline };
587 if (node->call_for_symbol_and_aliases (do_estimate_growth_1, &d, true))
588 return true;
589 if (d.self_recursive || d.uninlinable)
590 return true;
591 return (d.growth > offline);