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"
39 #include "gimple-iterator.h"
41 #include "tree-ssa-loop-niter.h"
42 #include "tree-ssa-loop.h"
43 #include "symbol-summary.h"
45 #include "ipa-fnsummary.h"
46 #include "ipa-inline.h"
48 #include "tree-scalar-evolution.h"
49 #include "ipa-utils.h"
50 #include "cfgexpand.h"
53 /* Cached node/edge growths. */
54 call_summary
<edge_growth_cache_entry
*> *edge_growth_cache
= NULL
;
56 /* Give initial reasons why inlining would fail on EDGE. This gets either
57 nullified or usually overwritten by more precise reasons later. */
60 initialize_inline_failed (struct cgraph_edge
*e
)
62 struct cgraph_node
*callee
= e
->callee
;
64 if (e
->inline_failed
&& e
->inline_failed
!= CIF_BODY_NOT_AVAILABLE
65 && cgraph_inline_failed_type (e
->inline_failed
) == CIF_FINAL_ERROR
)
67 else if (e
->indirect_unknown_callee
)
68 e
->inline_failed
= CIF_INDIRECT_UNKNOWN_CALL
;
69 else if (!callee
->definition
)
70 e
->inline_failed
= CIF_BODY_NOT_AVAILABLE
;
71 else if (callee
->redefined_extern_inline
)
72 e
->inline_failed
= CIF_REDEFINED_EXTERN_INLINE
;
74 e
->inline_failed
= CIF_FUNCTION_NOT_CONSIDERED
;
75 gcc_checking_assert (!e
->call_stmt_cannot_inline_p
76 || cgraph_inline_failed_type (e
->inline_failed
)
81 /* Free growth caches. */
84 free_growth_caches (void)
86 delete edge_growth_cache
;
87 edge_growth_cache
= NULL
;
90 /* Return hints derrived from EDGE. */
93 simple_edge_hints (struct cgraph_edge
*edge
)
96 struct cgraph_node
*to
= (edge
->caller
->inlined_to
97 ? edge
->caller
->inlined_to
: edge
->caller
);
98 struct cgraph_node
*callee
= edge
->callee
->ultimate_alias_target ();
99 int to_scc_no
= ipa_fn_summaries
->get (to
)->scc_no
;
100 int callee_scc_no
= ipa_fn_summaries
->get (callee
)->scc_no
;
102 if (to_scc_no
&& to_scc_no
== callee_scc_no
&& !edge
->recursive_p ())
103 hints
|= INLINE_HINT_same_scc
;
105 if (callee
->lto_file_data
&& edge
->caller
->lto_file_data
106 && edge
->caller
->lto_file_data
!= callee
->lto_file_data
107 && !callee
->merged_comdat
&& !callee
->icf_merged
)
108 hints
|= INLINE_HINT_cross_module
;
113 /* Estimate the time cost for the caller when inlining EDGE.
114 Only to be called via estimate_edge_time, that handles the
117 When caching, also update the cache entry. Compute both time and
118 size, since we always need both metrics eventually. */
121 do_estimate_edge_time (struct cgraph_edge
*edge
)
123 sreal time
, nonspec_time
;
126 struct cgraph_node
*callee
;
127 clause_t clause
, nonspec_clause
;
128 vec
<tree
> known_vals
;
129 vec
<ipa_polymorphic_call_context
> known_contexts
;
130 vec
<ipa_agg_jump_function_p
> known_aggs
;
131 class ipa_call_summary
*es
= ipa_call_summaries
->get (edge
);
134 callee
= edge
->callee
->ultimate_alias_target ();
136 gcc_checking_assert (edge
->inline_failed
);
137 evaluate_properties_for_edge (edge
, true,
138 &clause
, &nonspec_clause
, &known_vals
,
139 &known_contexts
, &known_aggs
);
140 estimate_node_size_and_time (callee
, clause
, nonspec_clause
, known_vals
,
141 known_contexts
, known_aggs
, &size
, &min_size
,
142 &time
, &nonspec_time
, &hints
, es
->param
);
144 /* When we have profile feedback, we can quite safely identify hot
145 edges and for those we disable size limits. Don't do that when
146 probability that caller will call the callee is low however, since it
147 may hurt optimization of the caller's hot path. */
148 if (edge
->count
.ipa ().initialized_p () && edge
->maybe_hot_p ()
149 && (edge
->count
.ipa ().apply_scale (2, 1)
150 > (edge
->caller
->inlined_to
151 ? edge
->caller
->inlined_to
->count
.ipa ()
152 : edge
->caller
->count
.ipa ())))
153 hints
|= INLINE_HINT_known_hot
;
155 known_vals
.release ();
156 known_contexts
.release ();
157 known_aggs
.release ();
158 gcc_checking_assert (size
>= 0);
159 gcc_checking_assert (time
>= 0);
161 /* When caching, update the cache entry. */
162 if (edge_growth_cache
!= NULL
)
164 ipa_fn_summaries
->get (edge
->callee
->function_symbol ())->min_size
166 edge_growth_cache_entry
*entry
167 = edge_growth_cache
->get_create (edge
);
169 entry
->nonspec_time
= nonspec_time
;
171 entry
->size
= size
+ (size
>= 0);
172 hints
|= simple_edge_hints (edge
);
173 entry
->hints
= hints
+ 1;
179 /* Return estimated callee growth after inlining EDGE.
180 Only to be called via estimate_edge_size. */
183 do_estimate_edge_size (struct cgraph_edge
*edge
)
186 struct cgraph_node
*callee
;
187 clause_t clause
, nonspec_clause
;
188 vec
<tree
> known_vals
;
189 vec
<ipa_polymorphic_call_context
> known_contexts
;
190 vec
<ipa_agg_jump_function_p
> known_aggs
;
192 /* When we do caching, use do_estimate_edge_time to populate the entry. */
194 if (edge_growth_cache
!= NULL
)
196 do_estimate_edge_time (edge
);
197 size
= edge_growth_cache
->get (edge
)->size
;
198 gcc_checking_assert (size
);
199 return size
- (size
> 0);
202 callee
= edge
->callee
->ultimate_alias_target ();
204 /* Early inliner runs without caching, go ahead and do the dirty work. */
205 gcc_checking_assert (edge
->inline_failed
);
206 evaluate_properties_for_edge (edge
, true,
207 &clause
, &nonspec_clause
,
208 &known_vals
, &known_contexts
,
210 estimate_node_size_and_time (callee
, clause
, nonspec_clause
, known_vals
,
211 known_contexts
, known_aggs
, &size
, NULL
, NULL
,
213 known_vals
.release ();
214 known_contexts
.release ();
215 known_aggs
.release ();
220 /* Estimate the growth of the caller when inlining EDGE.
221 Only to be called via estimate_edge_size. */
224 do_estimate_edge_hints (struct cgraph_edge
*edge
)
227 struct cgraph_node
*callee
;
228 clause_t clause
, nonspec_clause
;
229 vec
<tree
> known_vals
;
230 vec
<ipa_polymorphic_call_context
> known_contexts
;
231 vec
<ipa_agg_jump_function_p
> known_aggs
;
233 /* When we do caching, use do_estimate_edge_time to populate the entry. */
235 if (edge_growth_cache
!= NULL
)
237 do_estimate_edge_time (edge
);
238 hints
= edge_growth_cache
->get (edge
)->hints
;
239 gcc_checking_assert (hints
);
243 callee
= edge
->callee
->ultimate_alias_target ();
245 /* Early inliner runs without caching, go ahead and do the dirty work. */
246 gcc_checking_assert (edge
->inline_failed
);
247 evaluate_properties_for_edge (edge
, true,
248 &clause
, &nonspec_clause
,
249 &known_vals
, &known_contexts
,
251 estimate_node_size_and_time (callee
, clause
, nonspec_clause
, known_vals
,
252 known_contexts
, known_aggs
, NULL
, NULL
,
253 NULL
, NULL
, &hints
, vNULL
);
254 known_vals
.release ();
255 known_contexts
.release ();
256 known_aggs
.release ();
257 hints
|= simple_edge_hints (edge
);
261 /* Estimate the size of NODE after inlining EDGE which should be an
262 edge to either NODE or a call inlined into NODE. */
265 estimate_size_after_inlining (struct cgraph_node
*node
,
266 struct cgraph_edge
*edge
)
268 class ipa_call_summary
*es
= ipa_call_summaries
->get (edge
);
269 ipa_size_summary
*s
= ipa_size_summaries
->get (node
);
270 if (!es
->predicate
|| *es
->predicate
!= false)
272 int size
= s
->size
+ estimate_edge_growth (edge
);
273 gcc_assert (size
>= 0);
282 struct cgraph_node
*node
;
289 /* Worker for do_estimate_growth. Collect growth for all callers. */
292 do_estimate_growth_1 (struct cgraph_node
*node
, void *data
)
294 struct cgraph_edge
*e
;
295 struct growth_data
*d
= (struct growth_data
*) data
;
297 for (e
= node
->callers
; e
; e
= e
->next_caller
)
299 gcc_checking_assert (e
->inline_failed
);
301 if (cgraph_inline_failed_type (e
->inline_failed
) == CIF_FINAL_ERROR
302 || !opt_for_fn (e
->caller
->decl
, optimize
))
304 d
->uninlinable
= true;
308 if (e
->recursive_p ())
310 d
->self_recursive
= true;
313 d
->growth
+= estimate_edge_growth (e
);
319 /* Estimate the growth caused by inlining NODE into all callees. */
322 estimate_growth (struct cgraph_node
*node
)
324 struct growth_data d
= { node
, false, false, 0 };
325 class ipa_size_summary
*info
= ipa_size_summaries
->get (node
);
327 node
->call_for_symbol_and_aliases (do_estimate_growth_1
, &d
, true);
329 /* For self recursive functions the growth estimation really should be
330 infinity. We don't want to return very large values because the growth
331 plays various roles in badness computation fractions. Be sure to not
332 return zero or negative growths. */
333 if (d
.self_recursive
)
334 d
.growth
= d
.growth
< info
->size
? info
->size
: d
.growth
;
335 else if (DECL_EXTERNAL (node
->decl
) || d
.uninlinable
)
339 if (node
->will_be_removed_from_program_if_no_direct_calls_p ())
340 d
.growth
-= info
->size
;
341 /* COMDAT functions are very often not shared across multiple units
342 since they come from various template instantiations.
343 Take this into account. */
344 else if (DECL_COMDAT (node
->decl
)
345 && node
->can_remove_if_no_direct_calls_p ())
346 d
.growth
-= (info
->size
347 * (100 - PARAM_VALUE (PARAM_COMDAT_SHARING_PROBABILITY
))
354 /* Verify if there are fewer than MAX_CALLERS. */
357 check_callers (cgraph_node
*node
, int *max_callers
)
361 if (!node
->can_remove_if_no_direct_calls_and_refs_p ())
364 for (cgraph_edge
*e
= node
->callers
; e
; e
= e
->next_caller
)
368 || cgraph_inline_failed_type (e
->inline_failed
) == CIF_FINAL_ERROR
)
372 FOR_EACH_ALIAS (node
, ref
)
373 if (check_callers (dyn_cast
<cgraph_node
*> (ref
->referring
), max_callers
))
380 /* Make cheap estimation if growth of NODE is likely positive knowing
381 EDGE_GROWTH of one particular edge.
382 We assume that most of other edges will have similar growth
383 and skip computation if there are too many callers. */
386 growth_likely_positive (struct cgraph_node
*node
,
390 struct cgraph_edge
*e
;
391 gcc_checking_assert (edge_growth
> 0);
393 /* First quickly check if NODE is removable at all. */
394 if (DECL_EXTERNAL (node
->decl
))
396 if (!node
->can_remove_if_no_direct_calls_and_refs_p ()
397 || node
->address_taken
)
400 max_callers
= ipa_size_summaries
->get (node
)->size
* 4 / edge_growth
+ 2;
402 for (e
= node
->callers
; e
; e
= e
->next_caller
)
406 || cgraph_inline_failed_type (e
->inline_failed
) == CIF_FINAL_ERROR
)
411 FOR_EACH_ALIAS (node
, ref
)
412 if (check_callers (dyn_cast
<cgraph_node
*> (ref
->referring
), &max_callers
))
415 /* Unlike for functions called once, we play unsafe with
416 COMDATs. We can allow that since we know functions
417 in consideration are small (and thus risk is small) and
418 moreover grow estimates already accounts that COMDAT
419 functions may or may not disappear when eliminated from
420 current unit. With good probability making aggressive
421 choice in all units is going to make overall program
423 if (DECL_COMDAT (node
->decl
))
425 if (!node
->can_remove_if_no_direct_calls_p ())
428 else if (!node
->will_be_removed_from_program_if_no_direct_calls_p ())
431 return estimate_growth (node
) > 0;