1 /* Analysis used by inlining decision heuristics.
2 Copyright (C) 2003-2019 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
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
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/>. */
23 #include "coretypes.h"
27 #include "alloc-pool.h"
28 #include "tree-pass.h"
30 #include "tree-streamer.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"
38 #include "gimple-iterator.h"
40 #include "tree-ssa-loop-niter.h"
41 #include "tree-ssa-loop.h"
42 #include "symbol-summary.h"
44 #include "ipa-fnsummary.h"
45 #include "ipa-inline.h"
47 #include "tree-scalar-evolution.h"
48 #include "ipa-utils.h"
49 #include "cfgexpand.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
61 sreal time
, nonspec_time
;
65 node_context_cache_entry ()
69 ~node_context_cache_entry ()
75 /* At the moment we implement primitive single entry LRU cache. */
76 class node_context_summary
79 node_context_cache_entry entry
;
81 node_context_summary ()
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. */
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
;
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
)
121 /* Allocate edge growth caches. */
124 initialize_growth_caches ()
127 = new fast_call_summary
<edge_growth_cache_entry
*, va_heap
> (symtab
);
129 = new fast_function_summary
<node_context_summary
*, va_heap
> (symtab
);
132 /* Free growth caches. */
135 free_growth_caches (void)
137 delete edge_growth_cache
;
138 delete node_context_cache
;
139 edge_growth_cache
= NULL
;
140 node_context_cache
= NULL
;
142 fprintf (dump_file
, "node context cache: %li hits, %li misses,"
143 " %li initializations\n",
144 node_context_cache_hit
, node_context_cache_miss
,
145 node_context_cache_clear
);
146 node_context_cache_hit
= 0;
147 node_context_cache_miss
= 0;
148 node_context_cache_clear
= 0;
151 /* Return hints derrived from EDGE. */
154 simple_edge_hints (struct cgraph_edge
*edge
)
157 struct cgraph_node
*to
= (edge
->caller
->inlined_to
158 ? edge
->caller
->inlined_to
: edge
->caller
);
159 struct cgraph_node
*callee
= edge
->callee
->ultimate_alias_target ();
160 int to_scc_no
= ipa_fn_summaries
->get (to
)->scc_no
;
161 int callee_scc_no
= ipa_fn_summaries
->get (callee
)->scc_no
;
163 if (to_scc_no
&& to_scc_no
== callee_scc_no
&& !edge
->recursive_p ())
164 hints
|= INLINE_HINT_same_scc
;
166 if (callee
->lto_file_data
&& edge
->caller
->lto_file_data
167 && edge
->caller
->lto_file_data
!= callee
->lto_file_data
168 && !callee
->merged_comdat
&& !callee
->icf_merged
)
169 hints
|= INLINE_HINT_cross_module
;
174 /* Estimate the time cost for the caller when inlining EDGE.
175 Only to be called via estimate_edge_time, that handles the
178 When caching, also update the cache entry. Compute both time and
179 size, since we always need both metrics eventually. */
182 do_estimate_edge_time (struct cgraph_edge
*edge
, sreal
*ret_nonspec_time
)
184 sreal time
, nonspec_time
;
187 struct cgraph_node
*callee
;
188 clause_t clause
, nonspec_clause
;
189 vec
<tree
> known_vals
;
190 vec
<ipa_polymorphic_call_context
> known_contexts
;
191 vec
<ipa_agg_value_set
> known_aggs
;
192 class ipa_call_summary
*es
= ipa_call_summaries
->get (edge
);
195 callee
= edge
->callee
->ultimate_alias_target ();
197 gcc_checking_assert (edge
->inline_failed
);
198 evaluate_properties_for_edge (edge
, true,
199 &clause
, &nonspec_clause
, &known_vals
,
200 &known_contexts
, &known_aggs
);
201 ipa_call_context
ctx (callee
, clause
, nonspec_clause
, known_vals
,
202 known_contexts
, known_aggs
, es
->param
);
203 if (node_context_cache
!= NULL
)
205 node_context_summary
*e
= node_context_cache
->get_create (callee
);
206 if (e
->entry
.ctx
.equal_to (ctx
))
208 node_context_cache_hit
++;
209 size
= e
->entry
.size
;
210 time
= e
->entry
.time
;
211 nonspec_time
= e
->entry
.nonspec_time
;
212 hints
= e
->entry
.hints
;
214 && !callee
->count
.ipa_p ())
216 sreal chk_time
, chk_nonspec_time
;
217 int chk_size
, chk_min_size
;
220 ctx
.estimate_size_and_time (&chk_size
, &chk_min_size
,
221 &chk_time
, &chk_nonspec_time
,
223 gcc_assert (chk_size
== size
&& chk_time
== time
224 && chk_nonspec_time
== nonspec_time
225 && chk_hints
== hints
);
230 if (e
->entry
.ctx
.exists_p ())
231 node_context_cache_miss
++;
233 node_context_cache_clear
++;
234 e
->entry
.ctx
.release (true);
235 ctx
.estimate_size_and_time (&size
, &min_size
,
236 &time
, &nonspec_time
, &hints
);
237 e
->entry
.size
= size
;
238 e
->entry
.time
= time
;
239 e
->entry
.nonspec_time
= nonspec_time
;
240 e
->entry
.hints
= hints
;
241 e
->entry
.ctx
.duplicate_from (ctx
);
245 ctx
.estimate_size_and_time (&size
, &min_size
,
246 &time
, &nonspec_time
, &hints
);
248 /* When we have profile feedback, we can quite safely identify hot
249 edges and for those we disable size limits. Don't do that when
250 probability that caller will call the callee is low however, since it
251 may hurt optimization of the caller's hot path. */
252 if (edge
->count
.ipa ().initialized_p () && edge
->maybe_hot_p ()
253 && (edge
->count
.ipa ().apply_scale (2, 1)
254 > (edge
->caller
->inlined_to
255 ? edge
->caller
->inlined_to
->count
.ipa ()
256 : edge
->caller
->count
.ipa ())))
257 hints
|= INLINE_HINT_known_hot
;
260 gcc_checking_assert (size
>= 0);
261 gcc_checking_assert (time
>= 0);
263 /* When caching, update the cache entry. */
264 if (edge_growth_cache
!= NULL
)
267 ipa_fn_summaries
->get (edge
->callee
->function_symbol ())->min_size
269 edge_growth_cache_entry
*entry
270 = edge_growth_cache
->get_create (edge
);
272 entry
->nonspec_time
= nonspec_time
;
274 entry
->size
= size
+ (size
>= 0);
275 hints
|= simple_edge_hints (edge
);
276 entry
->hints
= hints
+ 1;
278 if (ret_nonspec_time
)
279 *ret_nonspec_time
= nonspec_time
;
283 /* Reset cache for NODE.
284 This must be done each time NODE body is modified. */
286 reset_node_cache (struct cgraph_node
*node
)
288 if (node_context_cache
)
289 node_context_cache
->remove (node
);
292 /* Remove EDGE from caches once it was inlined. */
294 ipa_remove_from_growth_caches (struct cgraph_edge
*edge
)
296 if (node_context_cache
)
297 node_context_cache
->remove (edge
->callee
);
298 if (edge_growth_cache
)
299 edge_growth_cache
->remove (edge
);
302 /* Return estimated callee growth after inlining EDGE.
303 Only to be called via estimate_edge_size. */
306 do_estimate_edge_size (struct cgraph_edge
*edge
)
309 struct cgraph_node
*callee
;
310 clause_t clause
, nonspec_clause
;
311 vec
<tree
> known_vals
;
312 vec
<ipa_polymorphic_call_context
> known_contexts
;
313 vec
<ipa_agg_value_set
> known_aggs
;
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 evaluate_properties_for_edge (edge
, true,
330 &clause
, &nonspec_clause
,
331 &known_vals
, &known_contexts
,
333 ipa_call_context
ctx (callee
, clause
, nonspec_clause
, known_vals
,
334 known_contexts
, known_aggs
, vNULL
);
335 ctx
.estimate_size_and_time (&size
, NULL
, NULL
, NULL
, NULL
);
341 /* Estimate the growth of the caller when inlining EDGE.
342 Only to be called via estimate_edge_size. */
345 do_estimate_edge_hints (struct cgraph_edge
*edge
)
348 struct cgraph_node
*callee
;
349 clause_t clause
, nonspec_clause
;
350 vec
<tree
> known_vals
;
351 vec
<ipa_polymorphic_call_context
> known_contexts
;
352 vec
<ipa_agg_value_set
> known_aggs
;
354 /* When we do caching, use do_estimate_edge_time to populate the entry. */
356 if (edge_growth_cache
!= NULL
)
358 do_estimate_edge_time (edge
);
359 hints
= edge_growth_cache
->get (edge
)->hints
;
360 gcc_checking_assert (hints
);
364 callee
= edge
->callee
->ultimate_alias_target ();
366 /* Early inliner runs without caching, go ahead and do the dirty work. */
367 gcc_checking_assert (edge
->inline_failed
);
368 evaluate_properties_for_edge (edge
, true,
369 &clause
, &nonspec_clause
,
370 &known_vals
, &known_contexts
,
372 ipa_call_context
ctx (callee
, clause
, nonspec_clause
, known_vals
,
373 known_contexts
, known_aggs
, vNULL
);
374 ctx
.estimate_size_and_time (NULL
, NULL
, NULL
, NULL
, &hints
);
376 hints
|= simple_edge_hints (edge
);
380 /* Estimate the size of NODE after inlining EDGE which should be an
381 edge to either NODE or a call inlined into NODE. */
384 estimate_size_after_inlining (struct cgraph_node
*node
,
385 struct cgraph_edge
*edge
)
387 class ipa_call_summary
*es
= ipa_call_summaries
->get (edge
);
388 ipa_size_summary
*s
= ipa_size_summaries
->get (node
);
389 if (!es
->predicate
|| *es
->predicate
!= false)
391 int size
= s
->size
+ estimate_edge_growth (edge
);
392 gcc_assert (size
>= 0);
401 struct cgraph_node
*node
;
409 /* Worker for do_estimate_growth. Collect growth for all callers. */
412 do_estimate_growth_1 (struct cgraph_node
*node
, void *data
)
414 struct cgraph_edge
*e
;
415 struct growth_data
*d
= (struct growth_data
*) data
;
417 for (e
= node
->callers
; e
; e
= e
->next_caller
)
419 gcc_checking_assert (e
->inline_failed
);
421 if (cgraph_inline_failed_type (e
->inline_failed
) == CIF_FINAL_ERROR
422 || !opt_for_fn (e
->caller
->decl
, optimize
))
424 d
->uninlinable
= true;
425 if (d
->cap
< INT_MAX
)
430 if (e
->recursive_p ())
432 d
->self_recursive
= true;
433 if (d
->cap
< INT_MAX
)
437 d
->growth
+= estimate_edge_growth (e
);
438 if (d
->growth
> d
->cap
)
444 /* Return estimated savings for eliminating offline copy of NODE by inlining
448 offline_size (struct cgraph_node
*node
, ipa_size_summary
*info
)
450 if (!DECL_EXTERNAL (node
->decl
))
452 if (node
->will_be_removed_from_program_if_no_direct_calls_p ())
454 /* COMDAT functions are very often not shared across multiple units
455 since they come from various template instantiations.
456 Take this into account. */
457 else if (DECL_COMDAT (node
->decl
)
458 && node
->can_remove_if_no_direct_calls_p ())
460 * (100 - param_comdat_sharing_probability
)
466 /* Estimate the growth caused by inlining NODE into all callees. */
469 estimate_growth (struct cgraph_node
*node
)
471 struct growth_data d
= { node
, false, false, 0, INT_MAX
};
472 ipa_size_summary
*info
= ipa_size_summaries
->get (node
);
474 if (node
->call_for_symbol_and_aliases (do_estimate_growth_1
, &d
, true))
477 /* For self recursive functions the growth estimation really should be
478 infinity. We don't want to return very large values because the growth
479 plays various roles in badness computation fractions. Be sure to not
480 return zero or negative growths. */
481 if (d
.self_recursive
)
482 d
.growth
= d
.growth
< info
->size
? info
->size
: d
.growth
;
483 else if (!d
.uninlinable
)
484 d
.growth
-= offline_size (node
, info
);
489 /* Verify if there are fewer than MAX_CALLERS. */
492 check_callers (cgraph_node
*node
, int *growth
, int *n
, int offline
,
493 int min_size
, struct cgraph_edge
*known_edge
)
497 if (!node
->can_remove_if_no_direct_calls_and_refs_p ())
500 for (cgraph_edge
*e
= node
->callers
; e
; e
= e
->next_caller
)
502 edge_growth_cache_entry
*entry
;
506 if (cgraph_inline_failed_type (e
->inline_failed
) == CIF_FINAL_ERROR
)
508 if (edge_growth_cache
!= NULL
509 && (entry
= edge_growth_cache
->get (e
)) != NULL
511 *growth
+= entry
->size
- (entry
->size
> 0);
514 class ipa_call_summary
*es
= ipa_call_summaries
->get (e
);
517 *growth
+= min_size
- es
->call_stmt_size
;
521 if (*growth
> offline
)
526 FOR_EACH_ALIAS (node
, ref
)
527 if (check_callers (dyn_cast
<cgraph_node
*> (ref
->referring
), growth
, n
,
528 offline
, min_size
, known_edge
))
535 /* Decide if growth of NODE is positive. This is cheaper than calculating
536 actual growth. If edge growth of KNOWN_EDGE is known
537 it is passed by EDGE_GROWTH. */
540 growth_positive_p (struct cgraph_node
*node
,
541 struct cgraph_edge
* known_edge
, int edge_growth
)
543 struct cgraph_edge
*e
;
545 ipa_size_summary
*s
= ipa_size_summaries
->get (node
);
547 /* First quickly check if NODE is removable at all. */
548 int offline
= offline_size (node
, s
);
549 if (offline
<= 0 && known_edge
&& edge_growth
> 0)
552 int min_size
= ipa_fn_summaries
->get (node
)->min_size
;
555 int min_growth
= known_edge
? edge_growth
: 0;
556 for (e
= node
->callers
; e
; e
= e
->next_caller
)
558 edge_growth_cache_entry
*entry
;
560 if (cgraph_inline_failed_type (e
->inline_failed
) == CIF_FINAL_ERROR
)
564 if (edge_growth_cache
!= NULL
565 && (entry
= edge_growth_cache
->get (e
)) != NULL
567 min_growth
+= entry
->size
- (entry
->size
> 0);
570 class ipa_call_summary
*es
= ipa_call_summaries
->get (e
);
573 min_growth
+= min_size
- es
->call_stmt_size
;
577 if (min_growth
> offline
)
583 FOR_EACH_ALIAS (node
, ref
)
584 if (check_callers (dyn_cast
<cgraph_node
*> (ref
->referring
),
585 &min_growth
, &n
, offline
, min_size
, known_edge
))
588 struct growth_data d
= { node
, false, false, 0, offline
};
589 if (node
->call_for_symbol_and_aliases (do_estimate_growth_1
, &d
, true))
591 if (d
.self_recursive
|| d
.uninlinable
)
593 return (d
.growth
> offline
);