1	/* Inlining decision heuristics.
2	Copyright (C) 2003-2023 Free Software Foundation, Inc.
3	Contributed by Jan Hubicka
4
5	This file is part of GCC.
6
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.
11
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.
16
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/>. */
20
21	/* Inlining decision heuristics
22
23	The implementation of inliner is organized as follows:
24
25	inlining heuristics limits
26
27	can_inline_edge_p allow to check that particular inlining is allowed
28	by the limits specified by user (allowed function growth, growth and so
29	on).
30
31	Functions are inlined when it is obvious the result is profitable (such
32	as functions called once or when inlining reduce code size).
33	In addition to that we perform inlining of small functions and recursive
34	inlining.
35
36	inlining heuristics
37
38	The inliner itself is split into two passes:
39
40	pass_early_inlining
41
42	Simple local inlining pass inlining callees into current function.
43	This pass makes no use of whole unit analysis and thus it can do only
44	very simple decisions based on local properties.
45
46	The strength of the pass is that it is run in topological order
47	(reverse postorder) on the callgraph. Functions are converted into SSA
48	form just before this pass and optimized subsequently. As a result, the
49	callees of the function seen by the early inliner was already optimized
50	and results of early inlining adds a lot of optimization opportunities
51	for the local optimization.
52
53	The pass handle the obvious inlining decisions within the compilation
54	unit - inlining auto inline functions, inlining for size and
55	flattening.
56
57	main strength of the pass is the ability to eliminate abstraction
58	penalty in C++ code (via combination of inlining and early
59	optimization) and thus improve quality of analysis done by real IPA
60	optimizers.
61
62	Because of lack of whole unit knowledge, the pass cannot really make
63	good code size/performance tradeoffs. It however does very simple
64	speculative inlining allowing code size to grow by
65	EARLY_INLINING_INSNS when callee is leaf function. In this case the
66	optimizations performed later are very likely to eliminate the cost.
67
68	pass_ipa_inline
69
70	This is the real inliner able to handle inlining with whole program
71	knowledge. It performs following steps:
72
73	1) inlining of small functions. This is implemented by greedy
74	algorithm ordering all inlinable cgraph edges by their badness and
75	inlining them in this order as long as inline limits allows doing so.
76
77	This heuristics is not very good on inlining recursive calls. Recursive
78	calls can be inlined with results similar to loop unrolling. To do so,
79	special purpose recursive inliner is executed on function when
80	recursive edge is met as viable candidate.
81
82	2) Unreachable functions are removed from callgraph. Inlining leads
83	to devirtualization and other modification of callgraph so functions
84	may become unreachable during the process. Also functions declared as
85	extern inline or virtual functions are removed, since after inlining
86	we no longer need the offline bodies.
87
88	3) Functions called once and not exported from the unit are inlined.
89	This should almost always lead to reduction of code size by eliminating
90	the need for offline copy of the function. */
91
92	#include "config.h"
93	#include "system.h"
94	#include "coretypes.h"
95	#include "backend.h"
96	#include "target.h"
97	#include "rtl.h"
98	#include "tree.h"
99	#include "gimple.h"
100	#include "alloc-pool.h"
101	#include "tree-pass.h"
102	#include "gimple-ssa.h"
103	#include "cgraph.h"
104	#include "lto-streamer.h"
105	#include "trans-mem.h"
106	#include "calls.h"
107	#include "tree-inline.h"
108	#include "profile.h"
109	#include "symbol-summary.h"
110	#include "tree-vrp.h"
111	#include "ipa-prop.h"
112	#include "ipa-fnsummary.h"
113	#include "ipa-inline.h"
114	#include "ipa-utils.h"
115	#include "sreal.h"
116	#include "auto-profile.h"
117	#include "builtins.h"
118	#include "fibonacci_heap.h"
119	#include "stringpool.h"
120	#include "attribs.h"
121	#include "asan.h"
122
123	/* Inliner uses greedy algorithm to inline calls in a priority order.
124	Badness is used as the key in a Fibonacci heap which roughly corresponds
125	to negation of benefit to cost ratios.
126	In case multiple calls has same priority we want to stabilize the outcomes
127	for which we use ids. */
128	class inline_badness
129	{
130	public:
131	sreal badness;
132	int uid;
133	inline_badness ()
134	: badness (sreal::min ()), uid (0)
135	{
136	}
137	inline_badness (cgraph_edge *e, sreal b)
138	: badness (b), uid (e->get_uid ())
139	{
140	}
141	bool operator<= (const inline_badness &other)
142	{
143	if (badness != other.badness)
144	return badness <= other.badness;
145	return uid <= other.uid;
146	}
147	bool operator== (const inline_badness &other)
148	{
149	return badness == other.badness && uid == other.uid;
150	}
151	bool operator!= (const inline_badness &other)
152	{
153	return badness != other.badness || uid != other.uid;
154	}
155	bool operator< (const inline_badness &other)
156	{
157	if (badness != other.badness)
158	return badness < other.badness;
159	return uid < other.uid;
160	}
161	bool operator> (const inline_badness &other)
162	{
163	if (badness != other.badness)
164	return badness > other.badness;
165	return uid > other.uid;
166	}
167	};
168
169	typedef fibonacci_heap <inline_badness, cgraph_edge> edge_heap_t;
170	typedef fibonacci_node <inline_badness, cgraph_edge> edge_heap_node_t;
171
172	/* Statistics we collect about inlining algorithm. */
173	static int overall_size;
174	static profile_count max_count;
175	static profile_count spec_rem;
176
177	/* Return false when inlining edge E would lead to violating
178	limits on function unit growth or stack usage growth.
179
180	The relative function body growth limit is present generally
181	to avoid problems with non-linear behavior of the compiler.
182	To allow inlining huge functions into tiny wrapper, the limit
183	is always based on the bigger of the two functions considered.
184
185	For stack growth limits we always base the growth in stack usage
186	of the callers. We want to prevent applications from segfaulting
187	on stack overflow when functions with huge stack frames gets
188	inlined. */
189
190	static bool
191	caller_growth_limits (struct cgraph_edge *e)
192	{
193	struct cgraph_node *to = e->caller;
194	struct cgraph_node *what = e->callee->ultimate_alias_target ();
195	int newsize;
196	int limit = 0;
197	HOST_WIDE_INT stack_size_limit = 0, inlined_stack;
198	ipa_size_summary *outer_info = ipa_size_summaries->get (node: to);
199
200	/* Look for function e->caller is inlined to. While doing
201	so work out the largest function body on the way. As
202	described above, we want to base our function growth
203	limits based on that. Not on the self size of the
204	outer function, not on the self size of inline code
205	we immediately inline to. This is the most relaxed
206	interpretation of the rule "do not grow large functions
207	too much in order to prevent compiler from exploding". */
208	while (true)
209	{
210	ipa_size_summary *size_info = ipa_size_summaries->get (node: to);
211	if (limit < size_info->self_size)
212	limit = size_info->self_size;
213	if (stack_size_limit < size_info->estimated_self_stack_size)
214	stack_size_limit = size_info->estimated_self_stack_size;
215	if (to->inlined_to)
216	to = to->callers->caller;
217	else
218	break;
219	}
220
221	ipa_fn_summary *what_info = ipa_fn_summaries->get (node: what);
222	ipa_size_summary *what_size_info = ipa_size_summaries->get (node: what);
223
224	if (limit < what_size_info->self_size)
225	limit = what_size_info->self_size;
226
227	limit += limit * opt_for_fn (to->decl, param_large_function_growth) / 100;
228
229	/* Check the size after inlining against the function limits. But allow
230	the function to shrink if it went over the limits by forced inlining. */
231	newsize = estimate_size_after_inlining (to, e);
232	if (newsize >= ipa_size_summaries->get (node: what)->size
233	&& newsize > opt_for_fn (to->decl, param_large_function_insns)
234	&& newsize > limit)
235	{
236	e->inline_failed = CIF_LARGE_FUNCTION_GROWTH_LIMIT;
237	return false;
238	}
239
240	if (!what_info->estimated_stack_size)
241	return true;
242
243	/* FIXME: Stack size limit often prevents inlining in Fortran programs
244	due to large i/o datastructures used by the Fortran front-end.
245	We ought to ignore this limit when we know that the edge is executed
246	on every invocation of the caller (i.e. its call statement dominates
247	exit block). We do not track this information, yet. */
248	stack_size_limit += ((gcov_type)stack_size_limit
249	* opt_for_fn (to->decl, param_stack_frame_growth)
250	/ 100);
251
252	inlined_stack = (ipa_get_stack_frame_offset (node: to)
253	+ outer_info->estimated_self_stack_size
254	+ what_info->estimated_stack_size);
255	/* Check new stack consumption with stack consumption at the place
256	stack is used. */
257	if (inlined_stack > stack_size_limit
258	/* If function already has large stack usage from sibling
259	inline call, we can inline, too.
260	This bit overoptimistically assume that we are good at stack
261	packing. */
262	&& inlined_stack > ipa_fn_summaries->get (node: to)->estimated_stack_size
263	&& inlined_stack > opt_for_fn (to->decl, param_large_stack_frame))
264	{
265	e->inline_failed = CIF_LARGE_STACK_FRAME_GROWTH_LIMIT;
266	return false;
267	}
268	return true;
269	}
270
271	/* Dump info about why inlining has failed. */
272
273	static void
274	report_inline_failed_reason (struct cgraph_edge *e)
275	{
276	if (dump_enabled_p ())
277	{
278	dump_printf_loc (MSG_MISSED_OPTIMIZATION, e->call_stmt,
279	" not inlinable: %C -> %C, %s\n",
280	e->caller, e->callee,
281	cgraph_inline_failed_string (e->inline_failed));
282	if ((e->inline_failed == CIF_TARGET_OPTION_MISMATCH
283	|| e->inline_failed == CIF_OPTIMIZATION_MISMATCH)
284	&& e->caller->lto_file_data
285	&& e->callee->ultimate_alias_target ()->lto_file_data)
286	{
287	dump_printf_loc (MSG_MISSED_OPTIMIZATION, e->call_stmt,
288	" LTO objects: %s, %s\n",
289	e->caller->lto_file_data->file_name,
290	e->callee->ultimate_alias_target ()->lto_file_data->file_name);
291	}
292	if (e->inline_failed == CIF_TARGET_OPTION_MISMATCH)
293	if (dump_file)
294	cl_target_option_print_diff
295	(dump_file, 2, ptr1: target_opts_for_fn (fndecl: e->caller->decl),
296	ptr2: target_opts_for_fn (fndecl: e->callee->ultimate_alias_target ()->decl));
297	if (e->inline_failed == CIF_OPTIMIZATION_MISMATCH)
298	if (dump_file)
299	cl_optimization_print_diff
300	(dump_file, 2, ptr1: opts_for_fn (fndecl: e->caller->decl),
301	ptr2: opts_for_fn (fndecl: e->callee->ultimate_alias_target ()->decl));
302	}
303	}
304
305	/* Decide whether sanitizer-related attributes allow inlining. */
306
307	static bool
308	sanitize_attrs_match_for_inline_p (const_tree caller, const_tree callee)
309	{
310	if (!caller || !callee)
311	return true;
312
313	/* Follow clang and allow inlining for always_inline functions. */
314	if (lookup_attribute (attr_name: "always_inline", DECL_ATTRIBUTES (callee)))
315	return true;
316
317	const sanitize_code codes[] =
318	{
319	SANITIZE_ADDRESS,
320	SANITIZE_THREAD,
321	SANITIZE_UNDEFINED,
322	SANITIZE_UNDEFINED_NONDEFAULT,
323	SANITIZE_POINTER_COMPARE,
324	SANITIZE_POINTER_SUBTRACT
325	};
326
327	for (unsigned i = 0; i < ARRAY_SIZE (codes); i++)
328	if (sanitize_flags_p (flag: codes[i], fn: caller)
329	!= sanitize_flags_p (flag: codes[i], fn: callee))
330	return false;
331
332	if (sanitize_coverage_p (fn: caller) != sanitize_coverage_p (fn: callee))
333	return false;
334
335	return true;
336	}
337
338	/* Used for flags where it is safe to inline when caller's value is
339	grater than callee's. */
340	#define check_maybe_up(flag) \
341	(opts_for_fn (caller->decl)->x_##flag \
342	!= opts_for_fn (callee->decl)->x_##flag \
343	&& (!always_inline \
344	|| opts_for_fn (caller->decl)->x_##flag \
345	< opts_for_fn (callee->decl)->x_##flag))
346	/* Used for flags where it is safe to inline when caller's value is
347	smaller than callee's. */
348	#define check_maybe_down(flag) \
349	(opts_for_fn (caller->decl)->x_##flag \
350	!= opts_for_fn (callee->decl)->x_##flag \
351	&& (!always_inline \
352	|| opts_for_fn (caller->decl)->x_##flag \
353	> opts_for_fn (callee->decl)->x_##flag))
354	/* Used for flags where exact match is needed for correctness. */
355	#define check_match(flag) \
356	(opts_for_fn (caller->decl)->x_##flag \
357	!= opts_for_fn (callee->decl)->x_##flag)
358
359	/* Decide if we can inline the edge and possibly update
360	inline_failed reason.
361	We check whether inlining is possible at all and whether
362	caller growth limits allow doing so.
363
364	if REPORT is true, output reason to the dump file. */
365
366	static bool
367	can_inline_edge_p (struct cgraph_edge *e, bool report,
368	bool early = false)
369	{
370	gcc_checking_assert (e->inline_failed);
371
372	if (cgraph_inline_failed_type (e->inline_failed) == CIF_FINAL_ERROR)
373	{
374	if (report)
375	report_inline_failed_reason (e);
376	return false;
377	}
378
379	bool inlinable = true;
380	enum availability avail;
381	cgraph_node *caller = (e->caller->inlined_to
382	? e->caller->inlined_to : e->caller);
383	cgraph_node *callee = e->callee->ultimate_alias_target (availability: &avail, ref: caller);
384
385	if (!callee->definition)
386	{
387	e->inline_failed = CIF_BODY_NOT_AVAILABLE;
388	inlinable = false;
389	}
390	if (!early && (!opt_for_fn (callee->decl, optimize)
391	|| !opt_for_fn (caller->decl, optimize)))
392	{
393	e->inline_failed = CIF_FUNCTION_NOT_OPTIMIZED;
394	inlinable = false;
395	}
396	else if (callee->calls_comdat_local)
397	{
398	e->inline_failed = CIF_USES_COMDAT_LOCAL;
399	inlinable = false;
400	}
401	else if (avail <= AVAIL_INTERPOSABLE)
402	{
403	e->inline_failed = CIF_OVERWRITABLE;
404	inlinable = false;
405	}
406	/* All edges with call_stmt_cannot_inline_p should have inline_failed
407	initialized to one of FINAL_ERROR reasons. */
408	else if (e->call_stmt_cannot_inline_p)
409	gcc_unreachable ();
410	/* Don't inline if the functions have different EH personalities. */
411	else if (DECL_FUNCTION_PERSONALITY (caller->decl)
412	&& DECL_FUNCTION_PERSONALITY (callee->decl)
413	&& (DECL_FUNCTION_PERSONALITY (caller->decl)
414	!= DECL_FUNCTION_PERSONALITY (callee->decl)))
415	{
416	e->inline_failed = CIF_EH_PERSONALITY;
417	inlinable = false;
418	}
419	/* TM pure functions should not be inlined into non-TM_pure
420	functions. */
421	else if (is_tm_pure (callee->decl) && !is_tm_pure (caller->decl))
422	{
423	e->inline_failed = CIF_UNSPECIFIED;
424	inlinable = false;
425	}
426	/* Check compatibility of target optimization options. */
427	else if (!targetm.target_option.can_inline_p (caller->decl,
428	callee->decl))
429	{
430	e->inline_failed = CIF_TARGET_OPTION_MISMATCH;
431	inlinable = false;
432	}
433	else if (ipa_fn_summaries->get (node: callee) == NULL
434	|| !ipa_fn_summaries->get (node: callee)->inlinable)
435	{
436	e->inline_failed = CIF_FUNCTION_NOT_INLINABLE;
437	inlinable = false;
438	}
439	/* Don't inline a function with mismatched sanitization attributes. */
440	else if (!sanitize_attrs_match_for_inline_p (caller: caller->decl, callee: callee->decl))
441	{
442	e->inline_failed = CIF_SANITIZE_ATTRIBUTE_MISMATCH;
443	inlinable = false;
444	}
445
446	if (!inlinable && report)
447	report_inline_failed_reason (e);
448	return inlinable;
449	}
450
451	/* Return inlining_insns_single limit for function N. If HINT or HINT2 is true
452	scale up the bound. */
453
454	static int
455	inline_insns_single (cgraph_node *n, bool hint, bool hint2)
456	{
457	if (hint && hint2)
458	{
459	int64_t spd = opt_for_fn (n->decl, param_inline_heuristics_hint_percent);
460	spd = spd * spd;
461	if (spd > 1000000)
462	spd = 1000000;
463	return opt_for_fn (n->decl, param_max_inline_insns_single) * spd / 100;
464	}
465	if (hint || hint2)
466	return opt_for_fn (n->decl, param_max_inline_insns_single)
467	* opt_for_fn (n->decl, param_inline_heuristics_hint_percent) / 100;
468	return opt_for_fn (n->decl, param_max_inline_insns_single);
469	}
470
471	/* Return inlining_insns_auto limit for function N. If HINT or HINT2 is true
472	scale up the bound. */
473
474	static int
475	inline_insns_auto (cgraph_node *n, bool hint, bool hint2)
476	{
477	int max_inline_insns_auto = opt_for_fn (n->decl, param_max_inline_insns_auto);
478	if (hint && hint2)
479	{
480	int64_t spd = opt_for_fn (n->decl, param_inline_heuristics_hint_percent);
481	spd = spd * spd;
482	if (spd > 1000000)
483	spd = 1000000;
484	return max_inline_insns_auto * spd / 100;
485	}
486	if (hint || hint2)
487	return max_inline_insns_auto
488	* opt_for_fn (n->decl, param_inline_heuristics_hint_percent) / 100;
489	return max_inline_insns_auto;
490	}
491
492	/* Decide if we can inline the edge and possibly update
493	inline_failed reason.
494	We check whether inlining is possible at all and whether
495	caller growth limits allow doing so.
496
497	if REPORT is true, output reason to the dump file.
498
499	if DISREGARD_LIMITS is true, ignore size limits. */
500
501	static bool
502	can_inline_edge_by_limits_p (struct cgraph_edge *e, bool report,
503	bool disregard_limits = false, bool early = false)
504	{
505	gcc_checking_assert (e->inline_failed);
506
507	if (cgraph_inline_failed_type (e->inline_failed) == CIF_FINAL_ERROR)
508	{
509	if (report)
510	report_inline_failed_reason (e);
511	return false;
512	}
513
514	bool inlinable = true;
515	enum availability avail;
516	cgraph_node *caller = (e->caller->inlined_to
517	? e->caller->inlined_to : e->caller);
518	cgraph_node *callee = e->callee->ultimate_alias_target (availability: &avail, ref: caller);
519	tree caller_tree = DECL_FUNCTION_SPECIFIC_OPTIMIZATION (caller->decl);
520	tree callee_tree
521	= callee ? DECL_FUNCTION_SPECIFIC_OPTIMIZATION (callee->decl) : NULL;
522	/* Check if caller growth allows the inlining. */
523	if (!DECL_DISREGARD_INLINE_LIMITS (callee->decl)
524	&& !disregard_limits
525	&& !lookup_attribute (attr_name: "flatten",
526	DECL_ATTRIBUTES (caller->decl))
527	&& !caller_growth_limits (e))
528	inlinable = false;
529	else if (callee->externally_visible
530	&& !DECL_DISREGARD_INLINE_LIMITS (callee->decl)
531	&& flag_live_patching == LIVE_PATCHING_INLINE_ONLY_STATIC)
532	{
533	e->inline_failed = CIF_EXTERN_LIVE_ONLY_STATIC;
534	inlinable = false;
535	}
536	/* Don't inline a function with a higher optimization level than the
537	caller. FIXME: this is really just tip of iceberg of handling
538	optimization attribute. */
539	else if (caller_tree != callee_tree)
540	{
541	bool always_inline =
542	(DECL_DISREGARD_INLINE_LIMITS (callee->decl)
543	&& lookup_attribute (attr_name: "always_inline",
544	DECL_ATTRIBUTES (callee->decl)));
545	ipa_fn_summary *caller_info = ipa_fn_summaries->get (node: caller);
546	ipa_fn_summary *callee_info = ipa_fn_summaries->get (node: callee);
547
548	/* Until GCC 4.9 we did not check the semantics-altering flags
549	below and inlined across optimization boundaries.
550	Enabling checks below breaks several packages by refusing
551	to inline library always_inline functions. See PR65873.
552	Disable the check for early inlining for now until better solution
553	is found. */
554	if (always_inline && early)
555	;
556	/* There are some options that change IL semantics which means
557	we cannot inline in these cases for correctness reason.
558	Not even for always_inline declared functions. */
559	else if (check_match (flag_wrapv)
560	|| check_match (flag_trapv)
561	|| check_match (flag_pcc_struct_return)
562	|| check_maybe_down (optimize_debug)
563	/* When caller or callee does FP math, be sure FP codegen flags
564	compatible. */
565	|| ((caller_info->fp_expressions && callee_info->fp_expressions)
566	&& (check_maybe_up (flag_rounding_math)
567	|| check_maybe_up (flag_trapping_math)
568	|| check_maybe_down (flag_unsafe_math_optimizations)
569	|| check_maybe_down (flag_finite_math_only)
570	|| check_maybe_up (flag_signaling_nans)
571	|| check_maybe_down (flag_cx_limited_range)
572	|| check_maybe_up (flag_signed_zeros)
573	|| check_maybe_down (flag_associative_math)
574	|| check_maybe_down (flag_reciprocal_math)
575	|| check_maybe_down (flag_fp_int_builtin_inexact)
576	/* Strictly speaking only when the callee contains function
577	calls that may end up setting errno. */
578	|| check_maybe_up (flag_errno_math)))
579	/* We do not want to make code compiled with exceptions to be
580	brought into a non-EH function unless we know that the callee
581	does not throw.
582	This is tracked by DECL_FUNCTION_PERSONALITY. */
583	|| (check_maybe_up (flag_non_call_exceptions)
584	&& DECL_FUNCTION_PERSONALITY (callee->decl))
585	|| (check_maybe_up (flag_exceptions)
586	&& DECL_FUNCTION_PERSONALITY (callee->decl))
587	/* When devirtualization is disabled for callee, it is not safe
588	to inline it as we possibly mangled the type info.
589	Allow early inlining of always inlines. */
590	|| (!early && check_maybe_down (flag_devirtualize)))
591	{
592	e->inline_failed = CIF_OPTIMIZATION_MISMATCH;
593	inlinable = false;
594	}
595	/* gcc.dg/pr43564.c. Apply user-forced inline even at -O0. */
596	else if (always_inline)
597	;
598	/* When user added an attribute to the callee honor it. */
599	else if (lookup_attribute (attr_name: "optimize", DECL_ATTRIBUTES (callee->decl))
600	&& opts_for_fn (fndecl: caller->decl) != opts_for_fn (fndecl: callee->decl))
601	{
602	e->inline_failed = CIF_OPTIMIZATION_MISMATCH;
603	inlinable = false;
604	}
605	/* If explicit optimize attribute are not used, the mismatch is caused
606	by different command line options used to build different units.
607	Do not care about COMDAT functions - those are intended to be
608	optimized with the optimization flags of module they are used in.
609	Also do not care about mixing up size/speed optimization when
610	DECL_DISREGARD_INLINE_LIMITS is set. */
611	else if ((callee->merged_comdat
612	&& !lookup_attribute (attr_name: "optimize",
613	DECL_ATTRIBUTES (caller->decl)))
614	|| DECL_DISREGARD_INLINE_LIMITS (callee->decl))
615	;
616	/* If mismatch is caused by merging two LTO units with different
617	optimization flags we want to be bit nicer. However never inline
618	if one of functions is not optimized at all. */
619	else if (!opt_for_fn (callee->decl, optimize)
620	|| !opt_for_fn (caller->decl, optimize))
621	{
622	e->inline_failed = CIF_OPTIMIZATION_MISMATCH;
623	inlinable = false;
624	}
625	/* If callee is optimized for size and caller is not, allow inlining if
626	code shrinks or we are in param_max_inline_insns_single limit and
627	callee is inline (and thus likely an unified comdat).
628	This will allow caller to run faster. */
629	else if (opt_for_fn (callee->decl, optimize_size)
630	> opt_for_fn (caller->decl, optimize_size))
631	{
632	int growth = estimate_edge_growth (edge: e);
633	if (growth > opt_for_fn (caller->decl, param_max_inline_insns_size)
634	&& (!DECL_DECLARED_INLINE_P (callee->decl)
635	&& growth >= MAX (inline_insns_single (caller, false, false),
636	inline_insns_auto (caller, false, false))))
637	{
638	e->inline_failed = CIF_OPTIMIZATION_MISMATCH;
639	inlinable = false;
640	}
641	}
642	/* If callee is more aggressively optimized for performance than caller,
643	we generally want to inline only cheap (runtime wise) functions. */
644	else if (opt_for_fn (callee->decl, optimize_size)
645	< opt_for_fn (caller->decl, optimize_size)
646	|| (opt_for_fn (callee->decl, optimize)
647	> opt_for_fn (caller->decl, optimize)))
648	{
649	if (estimate_edge_time (edge: e)
650	>= 20 + ipa_call_summaries->get (edge: e)->call_stmt_time)
651	{
652	e->inline_failed = CIF_OPTIMIZATION_MISMATCH;
653	inlinable = false;
654	}
655	}
656
657	}
658
659	if (!inlinable && report)
660	report_inline_failed_reason (e);
661	return inlinable;
662	}
663
664
665	/* Return true if the edge E is inlinable during early inlining. */
666
667	static bool
668	can_early_inline_edge_p (struct cgraph_edge *e)
669	{
670	cgraph_node *caller = (e->caller->inlined_to
671	? e->caller->inlined_to : e->caller);
672	struct cgraph_node *callee = e->callee->ultimate_alias_target ();
673	/* Early inliner might get called at WPA stage when IPA pass adds new
674	function. In this case we cannot really do any of early inlining
675	because function bodies are missing. */
676	if (cgraph_inline_failed_type (e->inline_failed) == CIF_FINAL_ERROR)
677	return false;
678	if (!gimple_has_body_p (callee->decl))
679	{
680	e->inline_failed = CIF_BODY_NOT_AVAILABLE;
681	return false;
682	}
683	gcc_assert (gimple_in_ssa_p (DECL_STRUCT_FUNCTION (e->caller->decl))
684	&& gimple_in_ssa_p (DECL_STRUCT_FUNCTION (callee->decl)));
685	if (profile_arc_flag
686	&& ((lookup_attribute (attr_name: "no_profile_instrument_function",
687	DECL_ATTRIBUTES (caller->decl)) == NULL_TREE)
688	!= (lookup_attribute (attr_name: "no_profile_instrument_function",
689	DECL_ATTRIBUTES (callee->decl)) == NULL_TREE)))
690	return false;
691
692	if (!can_inline_edge_p (e, report: true, early: true)
693	|| !can_inline_edge_by_limits_p (e, report: true, disregard_limits: false, early: true))
694	return false;
695	/* When inlining regular functions into always-inline functions
696	during early inlining watch for possible inline cycles. */
697	if (DECL_DISREGARD_INLINE_LIMITS (caller->decl)
698	&& lookup_attribute (attr_name: "always_inline", DECL_ATTRIBUTES (caller->decl))
699	&& (!DECL_DISREGARD_INLINE_LIMITS (callee->decl)
700	|| !lookup_attribute (attr_name: "always_inline", DECL_ATTRIBUTES (callee->decl))))
701	{
702	/* If there are indirect calls, inlining may produce direct call.
703	TODO: We may lift this restriction if we avoid errors on formely
704	indirect calls to always_inline functions. Taking address
705	of always_inline function is generally bad idea and should
706	have been declared as undefined, but sadly we allow this. */
707	if (caller->indirect_calls || e->callee->indirect_calls)
708	return false;
709	ipa_fn_summary *callee_info = ipa_fn_summaries->get (node: callee);
710	if (callee_info->safe_to_inline_to_always_inline)
711	return callee_info->safe_to_inline_to_always_inline - 1;
712	for (cgraph_edge *e2 = callee->callees; e2; e2 = e2->next_callee)
713	{
714	struct cgraph_node *callee2 = e2->callee->ultimate_alias_target ();
715	/* As early inliner runs in RPO order, we will see uninlined
716	always_inline calls only in the case of cyclic graphs. */
717	if (DECL_DISREGARD_INLINE_LIMITS (callee2->decl)
718	|| lookup_attribute (attr_name: "always_inline", DECL_ATTRIBUTES (callee2->decl)))
719	{
720	callee_info->safe_to_inline_to_always_inline = 1;
721	return false;
722	}
723	/* With LTO watch for case where function is later replaced
724	by always_inline definition.
725	TODO: We may either stop treating noninlined cross-module always
726	inlines as errors, or we can extend decl merging to produce
727	syntacic alias and honor always inline only in units it has
728	been declared as such. */
729	if (flag_lto && callee2->externally_visible)
730	{
731	callee_info->safe_to_inline_to_always_inline = 1;
732	return false;
733	}
734	}
735	callee_info->safe_to_inline_to_always_inline = 2;
736	}
737	return true;
738	}
739
740
741	/* Return number of calls in N. Ignore cheap builtins. */
742
743	static int
744	num_calls (struct cgraph_node *n)
745	{
746	struct cgraph_edge *e;
747	int num = 0;
748
749	for (e = n->callees; e; e = e->next_callee)
750	if (!is_inexpensive_builtin (e->callee->decl))
751	num++;
752	return num;
753	}
754
755
756	/* Return true if we are interested in inlining small function. */
757
758	static bool
759	want_early_inline_function_p (struct cgraph_edge *e)
760	{
761	bool want_inline = true;
762	struct cgraph_node *callee = e->callee->ultimate_alias_target ();
763
764	if (DECL_DISREGARD_INLINE_LIMITS (callee->decl))
765	;
766	/* For AutoFDO, we need to make sure that before profile summary, all
767	hot paths' IR look exactly the same as profiled binary. As a result,
768	in einliner, we will disregard size limit and inline those callsites
769	that are:
770	* inlined in the profiled binary, and
771	* the cloned callee has enough samples to be considered "hot". */
772	else if (flag_auto_profile && afdo_callsite_hot_enough_for_early_inline (e))
773	;
774	else if (!DECL_DECLARED_INLINE_P (callee->decl)
775	&& !opt_for_fn (e->caller->decl, flag_inline_small_functions))
776	{
777	e->inline_failed = CIF_FUNCTION_NOT_INLINE_CANDIDATE;
778	report_inline_failed_reason (e);
779	want_inline = false;
780	}
781	else
782	{
783	/* First take care of very large functions. */
784	int min_growth = estimate_min_edge_growth (edge: e), growth = 0;
785	int n;
786	int early_inlining_insns = param_early_inlining_insns;
787
788	if (min_growth > early_inlining_insns)
789	{
790	if (dump_enabled_p ())
791	dump_printf_loc (MSG_MISSED_OPTIMIZATION, e->call_stmt,
792	" will not early inline: %C->%C, "
793	"call is cold and code would grow "
794	"at least by %i\n",
795	e->caller, callee,
796	min_growth);
797	want_inline = false;
798	}
799	else
800	growth = estimate_edge_growth (edge: e);
801
802
803	if (!want_inline || growth <= param_max_inline_insns_size)
804	;
805	else if (!e->maybe_hot_p ())
806	{
807	if (dump_enabled_p ())
808	dump_printf_loc (MSG_MISSED_OPTIMIZATION, e->call_stmt,
809	" will not early inline: %C->%C, "
810	"call is cold and code would grow by %i\n",
811	e->caller, callee,
812	growth);
813	want_inline = false;
814	}
815	else if (growth > early_inlining_insns)
816	{
817	if (dump_enabled_p ())
818	dump_printf_loc (MSG_MISSED_OPTIMIZATION, e->call_stmt,
819	" will not early inline: %C->%C, "
820	"growth %i exceeds --param early-inlining-insns\n",
821	e->caller, callee, growth);
822	want_inline = false;
823	}
824	else if ((n = num_calls (n: callee)) != 0
825	&& growth * (n + 1) > early_inlining_insns)
826	{
827	if (dump_enabled_p ())
828	dump_printf_loc (MSG_MISSED_OPTIMIZATION, e->call_stmt,
829	" will not early inline: %C->%C, "
830	"growth %i exceeds --param early-inlining-insns "
831	"divided by number of calls\n",
832	e->caller, callee, growth);
833	want_inline = false;
834	}
835	}
836	return want_inline;
837	}
838
839	/* Compute time of the edge->caller + edge->callee execution when inlining
840	does not happen. */
841
842	inline sreal
843	compute_uninlined_call_time (struct cgraph_edge *edge,
844	sreal uninlined_call_time,
845	sreal freq)
846	{
847	cgraph_node *caller = (edge->caller->inlined_to
848	? edge->caller->inlined_to
849	: edge->caller);
850
851	if (freq > 0)
852	uninlined_call_time *= freq;
853	else
854	uninlined_call_time = uninlined_call_time >> 11;
855
856	sreal caller_time = ipa_fn_summaries->get (node: caller)->time;
857	return uninlined_call_time + caller_time;
858	}
859
860	/* Same as compute_uinlined_call_time but compute time when inlining
861	does happen. */
862
863	inline sreal
864	compute_inlined_call_time (struct cgraph_edge *edge,
865	sreal time,
866	sreal freq)
867	{
868	cgraph_node *caller = (edge->caller->inlined_to
869	? edge->caller->inlined_to
870	: edge->caller);
871	sreal caller_time = ipa_fn_summaries->get (node: caller)->time;
872
873	if (freq > 0)
874	time *= freq;
875	else
876	time = time >> 11;
877
878	/* This calculation should match one in ipa-inline-analysis.cc
879	(estimate_edge_size_and_time). */
880	time -= (sreal)ipa_call_summaries->get (edge)->call_stmt_time * freq;
881	time += caller_time;
882	if (time <= 0)
883	time = ((sreal) 1) >> 8;
884	gcc_checking_assert (time >= 0);
885	return time;
886	}
887
888	/* Determine time saved by inlining EDGE of frequency FREQ
889	where callee's runtime w/o inlining is UNINLINED_TYPE
890	and with inlined is INLINED_TYPE. */
891
892	inline sreal
893	inlining_speedup (struct cgraph_edge *edge,
894	sreal freq,
895	sreal uninlined_time,
896	sreal inlined_time)
897	{
898	sreal speedup = uninlined_time - inlined_time;
899	/* Handling of call_time should match one in ipa-inline-fnsummary.c
900	(estimate_edge_size_and_time). */
901	sreal call_time = ipa_call_summaries->get (edge)->call_stmt_time;
902
903	if (freq > 0)
904	{
905	speedup = (speedup + call_time);
906	if (freq != 1)
907	speedup = speedup * freq;
908	}
909	else if (freq == 0)
910	speedup = speedup >> 11;
911	gcc_checking_assert (speedup >= 0);
912	return speedup;
913	}
914
915	/* Return true if the speedup for inlining E is bigger than
916	param_inline_min_speedup. */
917
918	static bool
919	big_speedup_p (struct cgraph_edge *e)
920	{
921	sreal unspec_time;
922	sreal spec_time = estimate_edge_time (edge: e, nonspec_time: &unspec_time);
923	sreal freq = e->sreal_frequency ();
924	sreal time = compute_uninlined_call_time (edge: e, uninlined_call_time: unspec_time, freq);
925	sreal inlined_time = compute_inlined_call_time (edge: e, time: spec_time, freq);
926	cgraph_node *caller = (e->caller->inlined_to
927	? e->caller->inlined_to
928	: e->caller);
929	int limit = opt_for_fn (caller->decl, param_inline_min_speedup);
930
931	if ((time - inlined_time) * 100 > time * limit)
932	return true;
933	return false;
934	}
935
936	/* Return true if we are interested in inlining small function.
937	When REPORT is true, report reason to dump file. */
938
939	static bool
940	want_inline_small_function_p (struct cgraph_edge *e, bool report)
941	{
942	bool want_inline = true;
943	struct cgraph_node *callee = e->callee->ultimate_alias_target ();
944	cgraph_node *to = (e->caller->inlined_to
945	? e->caller->inlined_to : e->caller);
946
947	/* Allow this function to be called before can_inline_edge_p,
948	since it's usually cheaper. */
949	if (cgraph_inline_failed_type (e->inline_failed) == CIF_FINAL_ERROR)
950	want_inline = false;
951	else if (DECL_DISREGARD_INLINE_LIMITS (callee->decl))
952	;
953	else if (!DECL_DECLARED_INLINE_P (callee->decl)
954	&& !opt_for_fn (e->caller->decl, flag_inline_small_functions))
955	{
956	e->inline_failed = CIF_FUNCTION_NOT_INLINE_CANDIDATE;
957	want_inline = false;
958	}
959	/* Do fast and conservative check if the function can be good
960	inline candidate. */
961	else if ((!DECL_DECLARED_INLINE_P (callee->decl)
962	&& (!e->count.ipa ().initialized_p () || !e->maybe_hot_p ()))
963	&& ipa_fn_summaries->get (node: callee)->min_size
964	- ipa_call_summaries->get (edge: e)->call_stmt_size
965	> inline_insns_auto (n: e->caller, hint: true, hint2: true))
966	{
967	e->inline_failed = CIF_MAX_INLINE_INSNS_AUTO_LIMIT;
968	want_inline = false;
969	}
970	else if ((DECL_DECLARED_INLINE_P (callee->decl)
971	|| e->count.ipa ().nonzero_p ())
972	&& ipa_fn_summaries->get (node: callee)->min_size
973	- ipa_call_summaries->get (edge: e)->call_stmt_size
974	> inline_insns_single (n: e->caller, hint: true, hint2: true))
975	{
976	e->inline_failed = (DECL_DECLARED_INLINE_P (callee->decl)
977	? CIF_MAX_INLINE_INSNS_SINGLE_LIMIT
978	: CIF_MAX_INLINE_INSNS_AUTO_LIMIT);
979	want_inline = false;
980	}
981	else
982	{
983	int growth = estimate_edge_growth (edge: e);
984	ipa_hints hints = estimate_edge_hints (edge: e);
985	/* We have two independent groups of hints. If one matches in each
986	of groups the limits are inreased. If both groups matches, limit
987	is increased even more. */
988	bool apply_hints = (hints & (INLINE_HINT_indirect_call
989	| INLINE_HINT_known_hot
990	| INLINE_HINT_loop_iterations
991	| INLINE_HINT_loop_stride));
992	bool apply_hints2 = (hints & INLINE_HINT_builtin_constant_p);
993
994	if (growth <= opt_for_fn (to->decl,
995	param_max_inline_insns_size))
996	;
997	/* Apply param_max_inline_insns_single limit. Do not do so when
998	hints suggests that inlining given function is very profitable.
999	Avoid computation of big_speedup_p when not necessary to change
1000	outcome of decision. */
1001	else if (DECL_DECLARED_INLINE_P (callee->decl)
1002	&& growth >= inline_insns_single (n: e->caller, hint: apply_hints,
1003	hint2: apply_hints2)
1004	&& (apply_hints || apply_hints2
1005	|| growth >= inline_insns_single (n: e->caller, hint: true,
1006	hint2: apply_hints2)
1007	|| !big_speedup_p (e)))
1008	{
1009	e->inline_failed = CIF_MAX_INLINE_INSNS_SINGLE_LIMIT;
1010	want_inline = false;
1011	}
1012	else if (!DECL_DECLARED_INLINE_P (callee->decl)
1013	&& !opt_for_fn (e->caller->decl, flag_inline_functions)
1014	&& growth >= opt_for_fn (to->decl,
1015	param_max_inline_insns_small))
1016	{
1017	/* growth_positive_p is expensive, always test it last. */
1018	if (growth >= inline_insns_single (n: e->caller, hint: false, hint2: false)
1019	|| growth_positive_p (callee, e, growth))
1020	{
1021	e->inline_failed = CIF_NOT_DECLARED_INLINED;
1022	want_inline = false;
1023	}
1024	}
1025	/* Apply param_max_inline_insns_auto limit for functions not declared
1026	inline. Bypass the limit when speedup seems big. */
1027	else if (!DECL_DECLARED_INLINE_P (callee->decl)
1028	&& growth >= inline_insns_auto (n: e->caller, hint: apply_hints,
1029	hint2: apply_hints2)
1030	&& (apply_hints || apply_hints2
1031	|| growth >= inline_insns_auto (n: e->caller, hint: true,
1032	hint2: apply_hints2)
1033	|| !big_speedup_p (e)))
1034	{
1035	/* growth_positive_p is expensive, always test it last. */
1036	if (growth >= inline_insns_single (n: e->caller, hint: false, hint2: false)
1037	|| growth_positive_p (callee, e, growth))
1038	{
1039	e->inline_failed = CIF_MAX_INLINE_INSNS_AUTO_LIMIT;
1040	want_inline = false;
1041	}
1042	}
1043	/* If call is cold, do not inline when function body would grow. */
1044	else if (!e->maybe_hot_p ()
1045	&& (growth >= inline_insns_single (n: e->caller, hint: false, hint2: false)
1046	|| growth_positive_p (callee, e, growth)))
1047	{
1048	e->inline_failed = CIF_UNLIKELY_CALL;
1049	want_inline = false;
1050	}
1051	}
1052	if (!want_inline && report)
1053	report_inline_failed_reason (e);
1054	return want_inline;
1055	}
1056
1057	/* EDGE is self recursive edge.
1058	We handle two cases - when function A is inlining into itself
1059	or when function A is being inlined into another inliner copy of function
1060	A within function B.
1061
1062	In first case OUTER_NODE points to the toplevel copy of A, while
1063	in the second case OUTER_NODE points to the outermost copy of A in B.
1064
1065	In both cases we want to be extra selective since
1066	inlining the call will just introduce new recursive calls to appear. */
1067
1068	static bool
1069	want_inline_self_recursive_call_p (struct cgraph_edge *edge,
1070	struct cgraph_node *outer_node,
1071	bool peeling,
1072	int depth)
1073	{
1074	char const *reason = NULL;
1075	bool want_inline = true;
1076	sreal caller_freq = 1;
1077	int max_depth = opt_for_fn (outer_node->decl,
1078	param_max_inline_recursive_depth_auto);
1079
1080	if (DECL_DECLARED_INLINE_P (edge->caller->decl))
1081	max_depth = opt_for_fn (outer_node->decl,
1082	param_max_inline_recursive_depth);
1083
1084	if (!edge->maybe_hot_p ())
1085	{
1086	reason = "recursive call is cold";
1087	want_inline = false;
1088	}
1089	else if (depth > max_depth)
1090	{
1091	reason = "--param max-inline-recursive-depth exceeded.";
1092	want_inline = false;
1093	}
1094	else if (outer_node->inlined_to
1095	&& (caller_freq = outer_node->callers->sreal_frequency ()) == 0)
1096	{
1097	reason = "caller frequency is 0";
1098	want_inline = false;
1099	}
1100
1101	if (!want_inline)
1102	;
1103	/* Inlining of self recursive function into copy of itself within other
1104	function is transformation similar to loop peeling.
1105
1106	Peeling is profitable if we can inline enough copies to make probability
1107	of actual call to the self recursive function very small. Be sure that
1108	the probability of recursion is small.
1109
1110	We ensure that the frequency of recursing is at most 1 - (1/max_depth).
1111	This way the expected number of recursion is at most max_depth. */
1112	else if (peeling)
1113	{
1114	sreal max_prob = (sreal)1 - ((sreal)1 / (sreal)max_depth);
1115	int i;
1116	for (i = 1; i < depth; i++)
1117	max_prob = max_prob * max_prob;
1118	if (edge->sreal_frequency () >= max_prob * caller_freq)
1119	{
1120	reason = "frequency of recursive call is too large";
1121	want_inline = false;
1122	}
1123	}
1124	/* Recursive inlining, i.e. equivalent of unrolling, is profitable if
1125	recursion depth is large. We reduce function call overhead and increase
1126	chances that things fit in hardware return predictor.
1127
1128	Recursive inlining might however increase cost of stack frame setup
1129	actually slowing down functions whose recursion tree is wide rather than
1130	deep.
1131
1132	Deciding reliably on when to do recursive inlining without profile feedback
1133	is tricky. For now we disable recursive inlining when probability of self
1134	recursion is low.
1135
1136	Recursive inlining of self recursive call within loop also results in
1137	large loop depths that generally optimize badly. We may want to throttle
1138	down inlining in those cases. In particular this seems to happen in one
1139	of libstdc++ rb tree methods. */
1140	else
1141	{
1142	if (edge->sreal_frequency () * 100
1143	<= caller_freq
1144	* opt_for_fn (outer_node->decl,
1145	param_min_inline_recursive_probability))
1146	{
1147	reason = "frequency of recursive call is too small";
1148	want_inline = false;
1149	}
1150	}
1151	if (!want_inline && dump_enabled_p ())
1152	dump_printf_loc (MSG_MISSED_OPTIMIZATION, edge->call_stmt,
1153	" not inlining recursively: %s\n", reason);
1154	return want_inline;
1155	}
1156
1157	/* Return true when NODE has uninlinable caller;
1158	set HAS_HOT_CALL if it has hot call.
1159	Worker for cgraph_for_node_and_aliases. */
1160
1161	static bool
1162	check_callers (struct cgraph_node *node, void *has_hot_call)
1163	{
1164	struct cgraph_edge *e;
1165	for (e = node->callers; e; e = e->next_caller)
1166	{
1167	if (!opt_for_fn (e->caller->decl, flag_inline_functions_called_once)
1168	|| !opt_for_fn (e->caller->decl, optimize))
1169	return true;
1170	if (!can_inline_edge_p (e, report: true))
1171	return true;
1172	if (e->recursive_p ())
1173	return true;
1174	if (!can_inline_edge_by_limits_p (e, report: true))
1175	return true;
1176	/* Inlining large functions to large loop depth is often harmful because
1177	of register pressure it implies. */
1178	if ((int)ipa_call_summaries->get (edge: e)->loop_depth
1179	> param_inline_functions_called_once_loop_depth)
1180	return true;
1181	/* Do not produce gigantic functions. */
1182	if (estimate_size_after_inlining (e->caller->inlined_to ?
1183	e->caller->inlined_to : e->caller, e)
1184	> param_inline_functions_called_once_insns)
1185	return true;
1186	if (!(*(bool *)has_hot_call) && e->maybe_hot_p ())
1187	*(bool *)has_hot_call = true;
1188	}
1189	return false;
1190	}
1191
1192	/* If NODE has a caller, return true. */
1193
1194	static bool
1195	has_caller_p (struct cgraph_node *node, void *data ATTRIBUTE_UNUSED)
1196	{
1197	if (node->callers)
1198	return true;
1199	return false;
1200	}
1201
1202	/* Decide if inlining NODE would reduce unit size by eliminating
1203	the offline copy of function.
1204	When COLD is true the cold calls are considered, too. */
1205
1206	static bool
1207	want_inline_function_to_all_callers_p (struct cgraph_node *node, bool cold)
1208	{
1209	bool has_hot_call = false;
1210
1211	/* Aliases gets inlined along with the function they alias. */
1212	if (node->alias)
1213	return false;
1214	/* Already inlined? */
1215	if (node->inlined_to)
1216	return false;
1217	/* Does it have callers? */
1218	if (!node->call_for_symbol_and_aliases (callback: has_caller_p, NULL, include_overwritable: true))
1219	return false;
1220	/* Inlining into all callers would increase size? */
1221	if (growth_positive_p (node, NULL, INT_MIN) > 0)
1222	return false;
1223	/* All inlines must be possible. */
1224	if (node->call_for_symbol_and_aliases (callback: check_callers, data: &has_hot_call,
1225	include_overwritable: true))
1226	return false;
1227	if (!cold && !has_hot_call)
1228	return false;
1229	return true;
1230	}
1231
1232	/* Return true if WHERE of SIZE is a possible candidate for wrapper heuristics
1233	in estimate_edge_badness. */
1234
1235	static bool
1236	wrapper_heuristics_may_apply (struct cgraph_node *where, int size)
1237	{
1238	return size < (DECL_DECLARED_INLINE_P (where->decl)
1239	? inline_insns_single (n: where, hint: false, hint2: false)
1240	: inline_insns_auto (n: where, hint: false, hint2: false));
1241	}
1242
1243	/* A cost model driving the inlining heuristics in a way so the edges with
1244	smallest badness are inlined first. After each inlining is performed
1245	the costs of all caller edges of nodes affected are recomputed so the
1246	metrics may accurately depend on values such as number of inlinable callers
1247	of the function or function body size. */
1248
1249	static sreal
1250	edge_badness (struct cgraph_edge *edge, bool dump)
1251	{
1252	sreal badness;
1253	int growth;
1254	sreal edge_time, unspec_edge_time;
1255	struct cgraph_node *callee = edge->callee->ultimate_alias_target ();
1256	class ipa_fn_summary *callee_info = ipa_fn_summaries->get (node: callee);
1257	ipa_hints hints;
1258	cgraph_node *caller = (edge->caller->inlined_to
1259	? edge->caller->inlined_to
1260	: edge->caller);
1261
1262	growth = estimate_edge_growth (edge);
1263	edge_time = estimate_edge_time (edge, nonspec_time: &unspec_edge_time);
1264	hints = estimate_edge_hints (edge);
1265	gcc_checking_assert (edge_time >= 0);
1266	/* Check that inlined time is better, but tolerate some roundoff issues.
1267	FIXME: When callee profile drops to 0 we account calls more. This
1268	should be fixed by never doing that. */
1269	gcc_checking_assert ((edge_time * 100
1270	- callee_info->time * 101).to_int () <= 0
1271	|| callee->count.ipa ().initialized_p ());
1272	gcc_checking_assert (growth <= ipa_size_summaries->get (callee)->size);
1273
1274	if (dump)
1275	{
1276	fprintf (stream: dump_file, format: " Badness calculation for %s -> %s\n",
1277	edge->caller->dump_name (),
1278	edge->callee->dump_name ());
1279	fprintf (stream: dump_file, format: " size growth %i, time %f unspec %f ",
1280	growth,
1281	edge_time.to_double (),
1282	unspec_edge_time.to_double ());
1283	ipa_dump_hints (f: dump_file, hints);
1284	if (big_speedup_p (e: edge))
1285	fprintf (stream: dump_file, format: " big_speedup");
1286	fprintf (stream: dump_file, format: "\n");
1287	}
1288
1289	/* Always prefer inlining saving code size. */
1290	if (growth <= 0)
1291	{
1292	badness = (sreal) (-SREAL_MIN_SIG + growth) << (SREAL_MAX_EXP / 256);
1293	if (dump)
1294	fprintf (stream: dump_file, format: " %f: Growth %d <= 0\n", badness.to_double (),
1295	growth);
1296	}
1297	/* Inlining into EXTERNAL functions is not going to change anything unless
1298	they are themselves inlined. */
1299	else if (DECL_EXTERNAL (caller->decl))
1300	{
1301	if (dump)
1302	fprintf (stream: dump_file, format: " max: function is external\n");
1303	return sreal::max ();
1304	}
1305	/* When profile is available. Compute badness as:
1306
1307	time_saved * caller_count
1308	goodness = -------------------------------------------------
1309	growth_of_caller * overall_growth * combined_size
1310
1311	badness = - goodness
1312
1313	Again use negative value to make calls with profile appear hotter
1314	then calls without.
1315	*/
1316	else if (opt_for_fn (caller->decl, flag_guess_branch_prob)
1317	|| caller->count.ipa ().nonzero_p ())
1318	{
1319	sreal numerator, denominator;
1320	int overall_growth;
1321	sreal freq = edge->sreal_frequency ();
1322
1323	numerator = inlining_speedup (edge, freq, uninlined_time: unspec_edge_time, inlined_time: edge_time);
1324	if (numerator <= 0)
1325	numerator = ((sreal) 1 >> 8);
1326	if (caller->count.ipa ().nonzero_p ())
1327	numerator *= caller->count.ipa ().to_gcov_type ();
1328	else if (caller->count.ipa ().initialized_p ())
1329	numerator = numerator >> 11;
1330	denominator = growth;
1331
1332	overall_growth = callee_info->growth;
1333
1334	/* Look for inliner wrappers of the form:
1335
1336	inline_caller ()
1337	{
1338	do_fast_job...
1339	if (need_more_work)
1340	noninline_callee ();
1341	}
1342	Without penalizing this case, we usually inline noninline_callee
1343	into the inline_caller because overall_growth is small preventing
1344	further inlining of inline_caller.
1345
1346	Penalize only callgraph edges to functions with small overall
1347	growth ...
1348	*/
1349	if (growth > overall_growth
1350	/* ... and having only one caller which is not inlined ... */
1351	&& callee_info->single_caller
1352	&& !edge->caller->inlined_to
1353	/* ... and edges executed only conditionally ... */
1354	&& freq < 1
1355	/* ... consider case where callee is not inline but caller is ... */
1356	&& ((!DECL_DECLARED_INLINE_P (edge->callee->decl)
1357	&& DECL_DECLARED_INLINE_P (caller->decl))
1358	/* ... or when early optimizers decided to split and edge
1359	frequency still indicates splitting is a win ... */
1360	|| (callee->split_part && !caller->split_part
1361	&& freq * 100
1362	< opt_for_fn (caller->decl,
1363	param_partial_inlining_entry_probability)
1364	/* ... and do not overwrite user specified hints. */
1365	&& (!DECL_DECLARED_INLINE_P (edge->callee->decl)
1366	|| DECL_DECLARED_INLINE_P (caller->decl)))))
1367	{
1368	ipa_fn_summary *caller_info = ipa_fn_summaries->get (node: caller);
1369	int caller_growth = caller_info->growth;
1370
1371	/* Only apply the penalty when caller looks like inline candidate,
1372	and it is not called once. */
1373	if (!caller_info->single_caller && overall_growth < caller_growth
1374	&& caller_info->inlinable
1375	&& wrapper_heuristics_may_apply
1376	(where: caller, size: ipa_size_summaries->get (node: caller)->size))
1377	{
1378	if (dump)
1379	fprintf (stream: dump_file,
1380	format: " Wrapper penalty. Increasing growth %i to %i\n",
1381	overall_growth, caller_growth);
1382	overall_growth = caller_growth;
1383	}
1384	}
1385	if (overall_growth > 0)
1386	{
1387	/* Strongly prefer functions with few callers that can be inlined
1388	fully. The square root here leads to smaller binaries at average.
1389	Watch however for extreme cases and return to linear function
1390	when growth is large. */
1391	if (overall_growth < 256)
1392	overall_growth *= overall_growth;
1393	else
1394	overall_growth += 256 * 256 - 256;
1395	denominator *= overall_growth;
1396	}
1397	denominator *= ipa_size_summaries->get (node: caller)->size + growth;
1398
1399	badness = - numerator / denominator;
1400
1401	if (dump)
1402	{
1403	fprintf (stream: dump_file,
1404	format: " %f: guessed profile. frequency %f, count %" PRId64
1405	" caller count %" PRId64
1406	" time saved %f"
1407	" overall growth %i (current) %i (original)"
1408	" %i (compensated)\n",
1409	badness.to_double (),
1410	freq.to_double (),
1411	edge->count.ipa ().initialized_p ()
1412	? edge->count.ipa ().to_gcov_type () : -1,
1413	caller->count.ipa ().initialized_p ()
1414	? caller->count.ipa ().to_gcov_type () : -1,
1415	inlining_speedup (edge, freq, uninlined_time: unspec_edge_time,
1416	inlined_time: edge_time).to_double (),
1417	estimate_growth (callee),
1418	callee_info->growth, overall_growth);
1419	}
1420	}
1421	/* When function local profile is not available or it does not give
1422	useful information (i.e. frequency is zero), base the cost on
1423	loop nest and overall size growth, so we optimize for overall number
1424	of functions fully inlined in program. */
1425	else
1426	{
1427	int nest = MIN (ipa_call_summaries->get (edge)->loop_depth, 8);
1428	badness = growth;
1429
1430	/* Decrease badness if call is nested. */
1431	if (badness > 0)
1432	badness = badness >> nest;
1433	else
1434	badness = badness << nest;
1435	if (dump)
1436	fprintf (stream: dump_file, format: " %f: no profile. nest %i\n",
1437	badness.to_double (), nest);
1438	}
1439	gcc_checking_assert (badness != 0);
1440
1441	if (edge->recursive_p ())
1442	badness = badness.shift (s: badness > 0 ? 4 : -4);
1443	if ((hints & (INLINE_HINT_indirect_call
1444	| INLINE_HINT_loop_iterations
1445	| INLINE_HINT_loop_stride))
1446	|| callee_info->growth <= 0)
1447	badness = badness.shift (s: badness > 0 ? -2 : 2);
1448	if (hints & INLINE_HINT_builtin_constant_p)
1449	badness = badness.shift (s: badness > 0 ? -4 : 4);
1450	if (hints & (INLINE_HINT_same_scc))
1451	badness = badness.shift (s: badness > 0 ? 3 : -3);
1452	else if (hints & (INLINE_HINT_in_scc))
1453	badness = badness.shift (s: badness > 0 ? 2 : -2);
1454	else if (hints & (INLINE_HINT_cross_module))
1455	badness = badness.shift (s: badness > 0 ? 1 : -1);
1456	if (DECL_DISREGARD_INLINE_LIMITS (callee->decl))
1457	badness = badness.shift (s: badness > 0 ? -4 : 4);
1458	else if ((hints & INLINE_HINT_declared_inline))
1459	badness = badness.shift (s: badness > 0 ? -3 : 3);
1460	if (dump)
1461	fprintf (stream: dump_file, format: " Adjusted by hints %f\n", badness.to_double ());
1462	return badness;
1463	}
1464
1465	/* Recompute badness of EDGE and update its key in HEAP if needed. */
1466	static inline void
1467	update_edge_key (edge_heap_t *heap, struct cgraph_edge *edge)
1468	{
1469	sreal badness = edge_badness (edge, dump: false);
1470	if (edge->aux)
1471	{
1472	edge_heap_node_t *n = (edge_heap_node_t *) edge->aux;
1473	gcc_checking_assert (n->get_data () == edge);
1474
1475	/* fibonacci_heap::replace_key does busy updating of the
1476	heap that is unnecessarily expensive.
1477	We do lazy increases: after extracting minimum if the key
1478	turns out to be out of date, it is re-inserted into heap
1479	with correct value. */
1480	if (badness < n->get_key ().badness)
1481	{
1482	if (dump_file && (dump_flags & TDF_DETAILS))
1483	{
1484	fprintf (stream: dump_file,
1485	format: " decreasing badness %s -> %s, %f to %f\n",
1486	edge->caller->dump_name (),
1487	edge->callee->dump_name (),
1488	n->get_key ().badness.to_double (),
1489	badness.to_double ());
1490	}
1491	inline_badness b (edge, badness);
1492	heap->decrease_key (node: n, key: b);
1493	}
1494	}
1495	else
1496	{
1497	if (dump_file && (dump_flags & TDF_DETAILS))
1498	{
1499	fprintf (stream: dump_file,
1500	format: " enqueuing call %s -> %s, badness %f\n",
1501	edge->caller->dump_name (),
1502	edge->callee->dump_name (),
1503	badness.to_double ());
1504	}
1505	inline_badness b (edge, badness);
1506	edge->aux = heap->insert (key: b, data: edge);
1507	}
1508	}
1509
1510
1511	/* NODE was inlined.
1512	All caller edges needs to be reset because
1513	size estimates change. Similarly callees needs reset
1514	because better context may be known. */
1515
1516	static void
1517	reset_edge_caches (struct cgraph_node *node)
1518	{
1519	struct cgraph_edge *edge;
1520	struct cgraph_edge *e = node->callees;
1521	struct cgraph_node *where = node;
1522	struct ipa_ref *ref;
1523
1524	if (where->inlined_to)
1525	where = where->inlined_to;
1526
1527	reset_node_cache (node: where);
1528
1529	if (edge_growth_cache != NULL)
1530	for (edge = where->callers; edge; edge = edge->next_caller)
1531	if (edge->inline_failed)
1532	edge_growth_cache->remove (edge);
1533
1534	FOR_EACH_ALIAS (where, ref)
1535	reset_edge_caches (node: dyn_cast <cgraph_node *> (p: ref->referring));
1536
1537	if (!e)
1538	return;
1539
1540	while (true)
1541	if (!e->inline_failed && e->callee->callees)
1542	e = e->callee->callees;
1543	else
1544	{
1545	if (edge_growth_cache != NULL && e->inline_failed)
1546	edge_growth_cache->remove (edge: e);
1547	if (e->next_callee)
1548	e = e->next_callee;
1549	else
1550	{
1551	do
1552	{
1553	if (e->caller == node)
1554	return;
1555	e = e->caller->callers;
1556	}
1557	while (!e->next_callee);
1558	e = e->next_callee;
1559	}
1560	}
1561	}
1562
1563	/* Recompute HEAP nodes for each of caller of NODE.
1564	UPDATED_NODES track nodes we already visited, to avoid redundant work.
1565	When CHECK_INLINABLITY_FOR is set, re-check for specified edge that
1566	it is inlinable. Otherwise check all edges. */
1567
1568	static void
1569	update_caller_keys (edge_heap_t *heap, struct cgraph_node *node,
1570	bitmap updated_nodes,
1571	struct cgraph_edge *check_inlinablity_for)
1572	{
1573	struct cgraph_edge *edge;
1574	struct ipa_ref *ref;
1575
1576	if ((!node->alias && !ipa_fn_summaries->get (node)->inlinable)
1577	|| node->inlined_to)
1578	return;
1579	if (!bitmap_set_bit (updated_nodes, node->get_uid ()))
1580	return;
1581
1582	FOR_EACH_ALIAS (node, ref)
1583	{
1584	struct cgraph_node *alias = dyn_cast <cgraph_node *> (p: ref->referring);
1585	update_caller_keys (heap, node: alias, updated_nodes, check_inlinablity_for);
1586	}
1587
1588	for (edge = node->callers; edge; edge = edge->next_caller)
1589	if (edge->inline_failed)
1590	{
1591	if (!check_inlinablity_for
1592	|| check_inlinablity_for == edge)
1593	{
1594	if (can_inline_edge_p (e: edge, report: false)
1595	&& want_inline_small_function_p (e: edge, report: false)
1596	&& can_inline_edge_by_limits_p (e: edge, report: false))
1597	update_edge_key (heap, edge);
1598	else if (edge->aux)
1599	{
1600	report_inline_failed_reason (e: edge);
1601	heap->delete_node (node: (edge_heap_node_t *) edge->aux);
1602	edge->aux = NULL;
1603	}
1604	}
1605	else if (edge->aux)
1606	update_edge_key (heap, edge);
1607	}
1608	}
1609
1610	/* Recompute HEAP nodes for each uninlined call in NODE
1611	If UPDATE_SINCE is non-NULL check if edges called within that function
1612	are inlinable (typically UPDATE_SINCE is the inline clone we introduced
1613	where all edges have new context).
1614
1615	This is used when we know that edge badnesses are going only to increase
1616	(we introduced new call site) and thus all we need is to insert newly
1617	created edges into heap. */
1618
1619	static void
1620	update_callee_keys (edge_heap_t *heap, struct cgraph_node *node,
1621	struct cgraph_node *update_since,
1622	bitmap updated_nodes)
1623	{
1624	struct cgraph_edge *e = node->callees;
1625	bool check_inlinability = update_since == node;
1626
1627	if (!e)
1628	return;
1629	while (true)
1630	if (!e->inline_failed && e->callee->callees)
1631	{
1632	if (e->callee == update_since)
1633	check_inlinability = true;
1634	e = e->callee->callees;
1635	}
1636	else
1637	{
1638	enum availability avail;
1639	struct cgraph_node *callee;
1640	if (!check_inlinability)
1641	{
1642	if (e->aux
1643	&& !bitmap_bit_p (updated_nodes,
1644	e->callee->ultimate_alias_target
1645	(availability: &avail, ref: e->caller)->get_uid ()))
1646	update_edge_key (heap, edge: e);
1647	}
1648	/* We do not reset callee growth cache here. Since we added a new call,
1649	growth should have just increased and consequently badness metric
1650	don't need updating. */
1651	else if (e->inline_failed
1652	&& (callee = e->callee->ultimate_alias_target (availability: &avail,
1653	ref: e->caller))
1654	&& avail >= AVAIL_AVAILABLE
1655	&& ipa_fn_summaries->get (node: callee) != NULL
1656	&& ipa_fn_summaries->get (node: callee)->inlinable
1657	&& !bitmap_bit_p (updated_nodes, callee->get_uid ()))
1658	{
1659	if (can_inline_edge_p (e, report: false)
1660	&& want_inline_small_function_p (e, report: false)
1661	&& can_inline_edge_by_limits_p (e, report: false))
1662	{
1663	gcc_checking_assert (check_inlinability || can_inline_edge_p (e, false));
1664	gcc_checking_assert (check_inlinability || e->aux);
1665	update_edge_key (heap, edge: e);
1666	}
1667	else if (e->aux)
1668	{
1669	report_inline_failed_reason (e);
1670	heap->delete_node (node: (edge_heap_node_t *) e->aux);
1671	e->aux = NULL;
1672	}
1673	}
1674	/* In case we redirected to unreachable node we only need to remove the
1675	fibheap entry. */
1676	else if (e->aux)
1677	{
1678	heap->delete_node (node: (edge_heap_node_t *) e->aux);
1679	e->aux = NULL;
1680	}
1681	if (e->next_callee)
1682	e = e->next_callee;
1683	else
1684	{
1685	do
1686	{
1687	if (e->caller == node)
1688	return;
1689	if (e->caller == update_since)
1690	check_inlinability = false;
1691	e = e->caller->callers;
1692	}
1693	while (!e->next_callee);
1694	e = e->next_callee;
1695	}
1696	}
1697	}
1698
1699	/* Enqueue all recursive calls from NODE into priority queue depending on
1700	how likely we want to recursively inline the call. */
1701
1702	static void
1703	lookup_recursive_calls (struct cgraph_node *node, struct cgraph_node *where,
1704	edge_heap_t *heap)
1705	{
1706	struct cgraph_edge *e;
1707	enum availability avail;
1708
1709	for (e = where->callees; e; e = e->next_callee)
1710	if (e->callee == node
1711	|| (e->callee->ultimate_alias_target (availability: &avail, ref: e->caller) == node
1712	&& avail > AVAIL_INTERPOSABLE))
1713	{
1714	inline_badness b (e, -e->sreal_frequency ());
1715	heap->insert (key: b, data: e);
1716	}
1717	for (e = where->callees; e; e = e->next_callee)
1718	if (!e->inline_failed)
1719	lookup_recursive_calls (node, where: e->callee, heap);
1720	}
1721
1722	/* Decide on recursive inlining: in the case function has recursive calls,
1723	inline until body size reaches given argument. If any new indirect edges
1724	are discovered in the process, add them to *NEW_EDGES, unless NEW_EDGES
1725	is NULL. */
1726
1727	static bool
1728	recursive_inlining (struct cgraph_edge *edge,
1729	vec<cgraph_edge *> *new_edges)
1730	{
1731	cgraph_node *to = (edge->caller->inlined_to
1732	? edge->caller->inlined_to : edge->caller);
1733	int limit = opt_for_fn (to->decl,
1734	param_max_inline_insns_recursive_auto);
1735	inline_badness b (edge, sreal::min ());
1736	edge_heap_t heap (b);
1737	struct cgraph_node *node;
1738	struct cgraph_edge *e;
1739	struct cgraph_node *master_clone = NULL, *next;
1740	int depth = 0;
1741	int n = 0;
1742
1743	node = edge->caller;
1744	if (node->inlined_to)
1745	node = node->inlined_to;
1746
1747	if (DECL_DECLARED_INLINE_P (node->decl))
1748	limit = opt_for_fn (to->decl, param_max_inline_insns_recursive);
1749
1750	/* Make sure that function is small enough to be considered for inlining. */
1751	if (estimate_size_after_inlining (node, edge) >= limit)
1752	return false;
1753	lookup_recursive_calls (node, where: node, heap: &heap);
1754	if (heap.empty ())
1755	return false;
1756
1757	if (dump_file)
1758	fprintf (stream: dump_file,
1759	format: " Performing recursive inlining on %s\n", node->dump_name ());
1760
1761	/* Do the inlining and update list of recursive call during process. */
1762	while (!heap.empty ())
1763	{
1764	struct cgraph_edge *curr = heap.extract_min ();
1765	struct cgraph_node *cnode, *dest = curr->callee;
1766
1767	if (!can_inline_edge_p (e: curr, report: true)
1768	|| !can_inline_edge_by_limits_p (e: curr, report: true))
1769	continue;
1770
1771	/* MASTER_CLONE is produced in the case we already started modified
1772	the function. Be sure to redirect edge to the original body before
1773	estimating growths otherwise we will be seeing growths after inlining
1774	the already modified body. */
1775	if (master_clone)
1776	{
1777	curr->redirect_callee (n: master_clone);
1778	if (edge_growth_cache != NULL)
1779	edge_growth_cache->remove (edge: curr);
1780	}
1781
1782	if (estimate_size_after_inlining (node, curr) > limit)
1783	{
1784	curr->redirect_callee (n: dest);
1785	if (edge_growth_cache != NULL)
1786	edge_growth_cache->remove (edge: curr);
1787	break;
1788	}
1789
1790	depth = 1;
1791	for (cnode = curr->caller;
1792	cnode->inlined_to; cnode = cnode->callers->caller)
1793	if (node->decl
1794	== curr->callee->ultimate_alias_target ()->decl)
1795	depth++;
1796
1797	if (!want_inline_self_recursive_call_p (edge: curr, outer_node: node, peeling: false, depth))
1798	{
1799	curr->redirect_callee (n: dest);
1800	if (edge_growth_cache != NULL)
1801	edge_growth_cache->remove (edge: curr);
1802	continue;
1803	}
1804
1805	if (dump_file)
1806	{
1807	fprintf (stream: dump_file,
1808	format: " Inlining call of depth %i", depth);
1809	if (node->count.nonzero_p () && curr->count.initialized_p ())
1810	{
1811	fprintf (stream: dump_file, format: " called approx. %.2f times per call",
1812	(double)curr->count.to_gcov_type ()
1813	/ node->count.to_gcov_type ());
1814	}
1815	fprintf (stream: dump_file, format: "\n");
1816	}
1817	if (!master_clone)
1818	{
1819	/* We need original clone to copy around. */
1820	master_clone = node->create_clone (decl: node->decl, count: node->count,
1821	update_original: false, redirect_callers: vNULL, call_duplication_hook: true, NULL, NULL);
1822	for (e = master_clone->callees; e; e = e->next_callee)
1823	if (!e->inline_failed)
1824	clone_inlined_nodes (e, true, false, NULL);
1825	curr->redirect_callee (n: master_clone);
1826	if (edge_growth_cache != NULL)
1827	edge_growth_cache->remove (edge: curr);
1828	}
1829
1830	inline_call (curr, false, new_edges, &overall_size, true);
1831	reset_node_cache (node);
1832	lookup_recursive_calls (node, where: curr->callee, heap: &heap);
1833	n++;
1834	}
1835
1836	if (!heap.empty () && dump_file)
1837	fprintf (stream: dump_file, format: " Recursive inlining growth limit met.\n");
1838
1839	if (!master_clone)
1840	return false;
1841
1842	if (dump_enabled_p ())
1843	dump_printf_loc (MSG_NOTE, edge->call_stmt,
1844	"\n Inlined %i times, "
1845	"body grown from size %i to %i, time %f to %f\n", n,
1846	ipa_size_summaries->get (node: master_clone)->size,
1847	ipa_size_summaries->get (node)->size,
1848	ipa_fn_summaries->get (node: master_clone)->time.to_double (),
1849	ipa_fn_summaries->get (node)->time.to_double ());
1850
1851	/* Remove master clone we used for inlining. We rely that clones inlined
1852	into master clone gets queued just before master clone so we don't
1853	need recursion. */
1854	for (node = symtab->first_function (); node != master_clone;
1855	node = next)
1856	{
1857	next = symtab->next_function (node);
1858	if (node->inlined_to == master_clone)
1859	node->remove ();
1860	}
1861	master_clone->remove ();
1862	return true;
1863	}
1864
1865
1866	/* Given whole compilation unit estimate of INSNS, compute how large we can
1867	allow the unit to grow. */
1868
1869	static int64_t
1870	compute_max_insns (cgraph_node *node, int insns)
1871	{
1872	int max_insns = insns;
1873	if (max_insns < opt_for_fn (node->decl, param_large_unit_insns))
1874	max_insns = opt_for_fn (node->decl, param_large_unit_insns);
1875
1876	return ((int64_t) max_insns
1877	* (100 + opt_for_fn (node->decl, param_inline_unit_growth)) / 100);
1878	}
1879
1880
1881	/* Compute badness of all edges in NEW_EDGES and add them to the HEAP. */
1882
1883	static void
1884	add_new_edges_to_heap (edge_heap_t *heap, vec<cgraph_edge *> &new_edges)
1885	{
1886	while (new_edges.length () > 0)
1887	{
1888	struct cgraph_edge *edge = new_edges.pop ();
1889
1890	gcc_assert (!edge->aux);
1891	gcc_assert (edge->callee);
1892	if (edge->inline_failed
1893	&& can_inline_edge_p (e: edge, report: true)
1894	&& want_inline_small_function_p (e: edge, report: true)
1895	&& can_inline_edge_by_limits_p (e: edge, report: true))
1896	{
1897	inline_badness b (edge, edge_badness (edge, dump: false));
1898	edge->aux = heap->insert (key: b, data: edge);
1899	}
1900	}
1901	}
1902
1903	/* Remove EDGE from the fibheap. */
1904
1905	static void
1906	heap_edge_removal_hook (struct cgraph_edge *e, void *data)
1907	{
1908	if (e->aux)
1909	{
1910	((edge_heap_t *)data)->delete_node (node: (edge_heap_node_t *)e->aux);
1911	e->aux = NULL;
1912	}
1913	}
1914
1915	/* Return true if speculation of edge E seems useful.
1916	If ANTICIPATE_INLINING is true, be conservative and hope that E
1917	may get inlined. */
1918
1919	bool
1920	speculation_useful_p (struct cgraph_edge *e, bool anticipate_inlining)
1921	{
1922	/* If we have already decided to inline the edge, it seems useful. */
1923	if (!e->inline_failed)
1924	return true;
1925
1926	enum availability avail;
1927	struct cgraph_node *target = e->callee->ultimate_alias_target (availability: &avail,
1928	ref: e->caller);
1929
1930	gcc_assert (e->speculative && !e->indirect_unknown_callee);
1931
1932	if (!e->maybe_hot_p ())
1933	return false;
1934
1935	/* See if IP optimizations found something potentially useful about the
1936	function. For now we look only for CONST/PURE flags. Almost everything
1937	else we propagate is useless. */
1938	if (avail >= AVAIL_AVAILABLE)
1939	{
1940	int ecf_flags = flags_from_decl_or_type (target->decl);
1941	if (ecf_flags & ECF_CONST)
1942	{
1943	if (!(e->speculative_call_indirect_edge ()->indirect_info
1944	->ecf_flags & ECF_CONST))
1945	return true;
1946	}
1947	else if (ecf_flags & ECF_PURE)
1948	{
1949	if (!(e->speculative_call_indirect_edge ()->indirect_info
1950	->ecf_flags & ECF_PURE))
1951	return true;
1952	}
1953	}
1954	/* If we did not managed to inline the function nor redirect
1955	to an ipa-cp clone (that are seen by having local flag set),
1956	it is probably pointless to inline it unless hardware is missing
1957	indirect call predictor. */
1958	if (!anticipate_inlining && !target->local)
1959	return false;
1960	/* For overwritable targets there is not much to do. */
1961	if (!can_inline_edge_p (e, report: false)
1962	|| !can_inline_edge_by_limits_p (e, report: false, disregard_limits: true))
1963	return false;
1964	/* OK, speculation seems interesting. */
1965	return true;
1966	}
1967
1968	/* We know that EDGE is not going to be inlined.
1969	See if we can remove speculation. */
1970
1971	static void
1972	resolve_noninline_speculation (edge_heap_t *edge_heap, struct cgraph_edge *edge)
1973	{
1974	if (edge->speculative && !speculation_useful_p (e: edge, anticipate_inlining: false))
1975	{
1976	struct cgraph_node *node = edge->caller;
1977	struct cgraph_node *where = node->inlined_to
1978	? node->inlined_to : node;
1979	auto_bitmap updated_nodes;
1980
1981	if (edge->count.ipa ().initialized_p ())
1982	spec_rem += edge->count.ipa ();
1983	cgraph_edge::resolve_speculation (edge);
1984	reset_edge_caches (node: where);
1985	ipa_update_overall_fn_summary (node: where);
1986	update_caller_keys (heap: edge_heap, node: where,
1987	updated_nodes, NULL);
1988	update_callee_keys (heap: edge_heap, node: where, NULL,
1989	updated_nodes);
1990	}
1991	}
1992
1993	/* Return true if NODE should be accounted for overall size estimate.
1994	Skip all nodes optimized for size so we can measure the growth of hot
1995	part of program no matter of the padding. */
1996
1997	bool
1998	inline_account_function_p (struct cgraph_node *node)
1999	{
2000	return (!DECL_EXTERNAL (node->decl)
2001	&& !opt_for_fn (node->decl, optimize_size)
2002	&& node->frequency != NODE_FREQUENCY_UNLIKELY_EXECUTED);
2003	}
2004
2005	/* Count number of callers of NODE and store it into DATA (that
2006	points to int. Worker for cgraph_for_node_and_aliases. */
2007
2008	static bool
2009	sum_callers (struct cgraph_node *node, void *data)
2010	{
2011	struct cgraph_edge *e;
2012	int *num_calls = (int *)data;
2013
2014	for (e = node->callers; e; e = e->next_caller)
2015	(*num_calls)++;
2016	return false;
2017	}
2018
2019	/* We only propagate across edges with non-interposable callee. */
2020
2021	inline bool
2022	ignore_edge_p (struct cgraph_edge *e)
2023	{
2024	enum availability avail;
2025	e->callee->function_or_virtual_thunk_symbol (avail: &avail, ref: e->caller);
2026	return (avail <= AVAIL_INTERPOSABLE);
2027	}
2028
2029	/* We use greedy algorithm for inlining of small functions:
2030	All inline candidates are put into prioritized heap ordered in
2031	increasing badness.
2032
2033	The inlining of small functions is bounded by unit growth parameters. */
2034
2035	static void
2036	inline_small_functions (void)
2037	{
2038	struct cgraph_node *node;
2039	struct cgraph_edge *edge;
2040	inline_badness b;
2041	edge_heap_t edge_heap (b);
2042	auto_bitmap updated_nodes;
2043	int min_size;
2044	auto_vec<cgraph_edge *> new_indirect_edges;
2045	int initial_size = 0;
2046	struct cgraph_node **order = XCNEWVEC (cgraph_node *, symtab->cgraph_count);
2047	struct cgraph_edge_hook_list *edge_removal_hook_holder;
2048	new_indirect_edges.create (nelems: 8);
2049
2050	edge_removal_hook_holder
2051	= symtab->add_edge_removal_hook (hook: &heap_edge_removal_hook, data: &edge_heap);
2052
2053	/* Compute overall unit size and other global parameters used by badness
2054	metrics. */
2055
2056	max_count = profile_count::uninitialized ();
2057	ipa_reduced_postorder (order, true, ignore_edge: ignore_edge_p);
2058	free (ptr: order);
2059
2060	FOR_EACH_DEFINED_FUNCTION (node)
2061	if (!node->inlined_to)
2062	{
2063	if (!node->alias && node->analyzed
2064	&& (node->has_gimple_body_p () || node->thunk)
2065	&& opt_for_fn (node->decl, optimize))
2066	{
2067	class ipa_fn_summary *info = ipa_fn_summaries->get (node);
2068	struct ipa_dfs_info *dfs = (struct ipa_dfs_info *) node->aux;
2069
2070	/* Do not account external functions, they will be optimized out
2071	if not inlined. Also only count the non-cold portion of program. */
2072	if (inline_account_function_p (node))
2073	initial_size += ipa_size_summaries->get (node)->size;
2074	info->growth = estimate_growth (node);
2075
2076	int num_calls = 0;
2077	node->call_for_symbol_and_aliases (callback: sum_callers, data: &num_calls,
2078	include_overwritable: true);
2079	if (num_calls == 1)
2080	info->single_caller = true;
2081	if (dfs && dfs->next_cycle)
2082	{
2083	struct cgraph_node *n2;
2084	int id = dfs->scc_no + 1;
2085	for (n2 = node; n2;
2086	n2 = ((struct ipa_dfs_info *) n2->aux)->next_cycle)
2087	if (opt_for_fn (n2->decl, optimize))
2088	{
2089	ipa_fn_summary *info2 = ipa_fn_summaries->get
2090	(node: n2->inlined_to ? n2->inlined_to : n2);
2091	if (info2->scc_no)
2092	break;
2093	info2->scc_no = id;
2094	}
2095	}
2096	}
2097
2098	for (edge = node->callers; edge; edge = edge->next_caller)
2099	max_count = max_count.max (other: edge->count.ipa ());
2100	}
2101	ipa_free_postorder_info ();
2102	initialize_growth_caches ();
2103
2104	if (dump_file)
2105	fprintf (stream: dump_file,
2106	format: "\nDeciding on inlining of small functions. Starting with size %i.\n",
2107	initial_size);
2108
2109	overall_size = initial_size;
2110	min_size = overall_size;
2111
2112	/* Populate the heap with all edges we might inline. */
2113
2114	FOR_EACH_DEFINED_FUNCTION (node)
2115	{
2116	bool update = false;
2117	struct cgraph_edge *next = NULL;
2118	bool has_speculative = false;
2119
2120	if (!opt_for_fn (node->decl, optimize)
2121	/* With -Og we do not want to perform IPA inlining of small
2122	functions since there are no scalar cleanups after it
2123	that would realize the anticipated win. All abstraction
2124	is removed during early inlining. */
2125	|| opt_for_fn (node->decl, optimize_debug))
2126	continue;
2127
2128	if (dump_file)
2129	fprintf (stream: dump_file, format: "Enqueueing calls in %s.\n", node->dump_name ());
2130
2131	for (edge = node->callees; edge; edge = edge->next_callee)
2132	{
2133	if (edge->inline_failed
2134	&& !edge->aux
2135	&& can_inline_edge_p (e: edge, report: true)
2136	&& want_inline_small_function_p (e: edge, report: true)
2137	&& can_inline_edge_by_limits_p (e: edge, report: true)
2138	&& edge->inline_failed)
2139	{
2140	gcc_assert (!edge->aux);
2141	update_edge_key (heap: &edge_heap, edge);
2142	}
2143	if (edge->speculative)
2144	has_speculative = true;
2145	}
2146	if (has_speculative)
2147	for (edge = node->callees; edge; edge = next)
2148	{
2149	next = edge->next_callee;
2150	if (edge->speculative
2151	&& !speculation_useful_p (e: edge, anticipate_inlining: edge->aux != NULL))
2152	{
2153	cgraph_edge::resolve_speculation (edge);
2154	update = true;
2155	}
2156	}
2157	if (update)
2158	{
2159	struct cgraph_node *where = node->inlined_to
2160	? node->inlined_to : node;
2161	ipa_update_overall_fn_summary (node: where);
2162	reset_edge_caches (node: where);
2163	update_caller_keys (heap: &edge_heap, node: where,
2164	updated_nodes, NULL);
2165	update_callee_keys (heap: &edge_heap, node: where, NULL,
2166	updated_nodes);
2167	bitmap_clear (updated_nodes);
2168	}
2169	}
2170
2171	gcc_assert (in_lto_p
2172	|| !(max_count > 0)
2173	|| (profile_info && flag_branch_probabilities));
2174
2175	while (!edge_heap.empty ())
2176	{
2177	int old_size = overall_size;
2178	struct cgraph_node *where, *callee;
2179	sreal badness = edge_heap.min_key ().badness;
2180	sreal current_badness;
2181	int growth;
2182
2183	edge = edge_heap.extract_min ();
2184	gcc_assert (edge->aux);
2185	edge->aux = NULL;
2186	if (!edge->inline_failed || !edge->callee->analyzed)
2187	continue;
2188
2189	/* Be sure that caches are maintained consistent.
2190	This check is affected by scaling roundoff errors when compiling for
2191	IPA this we skip it in that case. */
2192	if (flag_checking && !edge->callee->count.ipa_p ()
2193	&& (!max_count.initialized_p () || !max_count.nonzero_p ()))
2194	{
2195	sreal cached_badness = edge_badness (edge, dump: false);
2196
2197	int old_size_est = estimate_edge_size (edge);
2198	sreal old_time_est = estimate_edge_time (edge);
2199	int old_hints_est = estimate_edge_hints (edge);
2200
2201	if (edge_growth_cache != NULL)
2202	edge_growth_cache->remove (edge);
2203	reset_node_cache (node: edge->caller->inlined_to
2204	? edge->caller->inlined_to
2205	: edge->caller);
2206	gcc_assert (old_size_est == estimate_edge_size (edge));
2207	gcc_assert (old_time_est == estimate_edge_time (edge));
2208	/* FIXME:
2209
2210	gcc_assert (old_hints_est == estimate_edge_hints (edge));
2211
2212	fails with profile feedback because some hints depends on
2213	maybe_hot_edge_p predicate and because callee gets inlined to other
2214	calls, the edge may become cold.
2215	This ought to be fixed by computing relative probabilities
2216	for given invocation but that will be better done once whole
2217	code is converted to sreals. Disable for now and revert to "wrong"
2218	value so enable/disable checking paths agree. */
2219	edge_growth_cache->get (edge)->hints = old_hints_est + 1;
2220
2221	/* When updating the edge costs, we only decrease badness in the keys.
2222	Increases of badness are handled lazily; when we see key with out
2223	of date value on it, we re-insert it now. */
2224	current_badness = edge_badness (edge, dump: false);
2225	gcc_assert (cached_badness == current_badness);
2226	gcc_assert (current_badness >= badness);
2227	}
2228	else
2229	current_badness = edge_badness (edge, dump: false);
2230	if (current_badness != badness)
2231	{
2232	if (edge_heap.min () && current_badness > edge_heap.min_key ().badness)
2233	{
2234	inline_badness b (edge, current_badness);
2235	edge->aux = edge_heap.insert (key: b, data: edge);
2236	continue;
2237	}
2238	else
2239	badness = current_badness;
2240	}
2241
2242	if (!can_inline_edge_p (e: edge, report: true)
2243	|| !can_inline_edge_by_limits_p (e: edge, report: true))
2244	{
2245	resolve_noninline_speculation (edge_heap: &edge_heap, edge);
2246	continue;
2247	}
2248
2249	callee = edge->callee->ultimate_alias_target ();
2250	growth = estimate_edge_growth (edge);
2251	if (dump_file)
2252	{
2253	fprintf (stream: dump_file,
2254	format: "\nConsidering %s with %i size\n",
2255	callee->dump_name (),
2256	ipa_size_summaries->get (node: callee)->size);
2257	fprintf (stream: dump_file,
2258	format: " to be inlined into %s in %s:%i\n"
2259	" Estimated badness is %f, frequency %.2f.\n",
2260	edge->caller->dump_name (),
2261	edge->call_stmt
2262	&& (LOCATION_LOCUS (gimple_location ((const gimple *)
2263	edge->call_stmt))
2264	> BUILTINS_LOCATION)
2265	? gimple_filename (stmt: (const gimple *) edge->call_stmt)
2266	: "unknown",
2267	edge->call_stmt
2268	? gimple_lineno (stmt: (const gimple *) edge->call_stmt)
2269	: -1,
2270	badness.to_double (),
2271	edge->sreal_frequency ().to_double ());
2272	if (edge->count.ipa ().initialized_p ())
2273	{
2274	fprintf (stream: dump_file, format: " Called ");
2275	edge->count.ipa ().dump (f: dump_file);
2276	fprintf (stream: dump_file, format: " times\n");
2277	}
2278	if (dump_flags & TDF_DETAILS)
2279	edge_badness (edge, dump: true);
2280	}
2281
2282	where = edge->caller;
2283
2284	if (overall_size + growth > compute_max_insns (node: where, insns: min_size)
2285	&& !DECL_DISREGARD_INLINE_LIMITS (callee->decl))
2286	{
2287	edge->inline_failed = CIF_INLINE_UNIT_GROWTH_LIMIT;
2288	report_inline_failed_reason (e: edge);
2289	resolve_noninline_speculation (edge_heap: &edge_heap, edge);
2290	continue;
2291	}
2292
2293	if (!want_inline_small_function_p (e: edge, report: true))
2294	{
2295	resolve_noninline_speculation (edge_heap: &edge_heap, edge);
2296	continue;
2297	}
2298
2299	profile_count old_count = callee->count;
2300
2301	/* Heuristics for inlining small functions work poorly for
2302	recursive calls where we do effects similar to loop unrolling.
2303	When inlining such edge seems profitable, leave decision on
2304	specific inliner. */
2305	if (edge->recursive_p ())
2306	{
2307	if (where->inlined_to)
2308	where = where->inlined_to;
2309	if (!recursive_inlining (edge,
2310	opt_for_fn (edge->caller->decl,
2311	flag_indirect_inlining)
2312	? &new_indirect_edges : NULL))
2313	{
2314	edge->inline_failed = CIF_RECURSIVE_INLINING;
2315	resolve_noninline_speculation (edge_heap: &edge_heap, edge);
2316	continue;
2317	}
2318	reset_edge_caches (node: where);
2319	/* Recursive inliner inlines all recursive calls of the function
2320	at once. Consequently we need to update all callee keys. */
2321	if (opt_for_fn (edge->caller->decl, flag_indirect_inlining))
2322	add_new_edges_to_heap (heap: &edge_heap, new_edges&: new_indirect_edges);
2323	update_callee_keys (heap: &edge_heap, node: where, update_since: where, updated_nodes);
2324	bitmap_clear (updated_nodes);
2325	}
2326	else
2327	{
2328	struct cgraph_node *outer_node = NULL;
2329	int depth = 0;
2330
2331	/* Consider the case where self recursive function A is inlined
2332	into B. This is desired optimization in some cases, since it
2333	leads to effect similar of loop peeling and we might completely
2334	optimize out the recursive call. However we must be extra
2335	selective. */
2336
2337	where = edge->caller;
2338	while (where->inlined_to)
2339	{
2340	if (where->decl == callee->decl)
2341	outer_node = where, depth++;
2342	where = where->callers->caller;
2343	}
2344	if (outer_node
2345	&& !want_inline_self_recursive_call_p (edge, outer_node,
2346	peeling: true, depth))
2347	{
2348	edge->inline_failed
2349	= (DECL_DISREGARD_INLINE_LIMITS (edge->callee->decl)
2350	? CIF_RECURSIVE_INLINING : CIF_UNSPECIFIED);
2351	resolve_noninline_speculation (edge_heap: &edge_heap, edge);
2352	continue;
2353	}
2354	else if (depth && dump_file)
2355	fprintf (stream: dump_file, format: " Peeling recursion with depth %i\n", depth);
2356
2357	gcc_checking_assert (!callee->inlined_to);
2358
2359	int old_size = ipa_size_summaries->get (node: where)->size;
2360	sreal old_time = ipa_fn_summaries->get (node: where)->time;
2361
2362	inline_call (edge, true, &new_indirect_edges, &overall_size, true);
2363	reset_edge_caches (node: edge->callee);
2364	add_new_edges_to_heap (heap: &edge_heap, new_edges&: new_indirect_edges);
2365
2366	/* If caller's size and time increased we do not need to update
2367	all edges because badness is not going to decrease. */
2368	if (old_size <= ipa_size_summaries->get (node: where)->size
2369	&& old_time <= ipa_fn_summaries->get (node: where)->time
2370	/* Wrapper penalty may be non-monotonous in this respect.
2371	Fortunately it only affects small functions. */
2372	&& !wrapper_heuristics_may_apply (where, size: old_size))
2373	update_callee_keys (heap: &edge_heap, node: edge->callee, update_since: edge->callee,
2374	updated_nodes);
2375	else
2376	update_callee_keys (heap: &edge_heap, node: where,
2377	update_since: edge->callee,
2378	updated_nodes);
2379	}
2380	where = edge->caller;
2381	if (where->inlined_to)
2382	where = where->inlined_to;
2383
2384	/* Our profitability metric can depend on local properties
2385	such as number of inlinable calls and size of the function body.
2386	After inlining these properties might change for the function we
2387	inlined into (since it's body size changed) and for the functions
2388	called by function we inlined (since number of it inlinable callers
2389	might change). */
2390	update_caller_keys (heap: &edge_heap, node: where, updated_nodes, NULL);
2391	/* Offline copy count has possibly changed, recompute if profile is
2392	available. */
2393	struct cgraph_node *n
2394	= cgraph_node::get (decl: edge->callee->decl)->ultimate_alias_target ();
2395	if (n != edge->callee && n->analyzed && !(n->count == old_count)
2396	&& n->count.ipa_p ())
2397	update_callee_keys (heap: &edge_heap, node: n, NULL, updated_nodes);
2398	bitmap_clear (updated_nodes);
2399
2400	if (dump_enabled_p ())
2401	{
2402	ipa_fn_summary *s = ipa_fn_summaries->get (node: where);
2403
2404	/* dump_printf can't handle %+i. */
2405	char buf_net_change[100];
2406	snprintf (s: buf_net_change, maxlen: sizeof buf_net_change, format: "%+i",
2407	overall_size - old_size);
2408
2409	dump_printf_loc (MSG_OPTIMIZED_LOCATIONS, edge->call_stmt,
2410	" Inlined %C into %C which now has time %f and "
2411	"size %i, net change of %s%s.\n",
2412	edge->callee, edge->caller,
2413	s->time.to_double (),
2414	ipa_size_summaries->get (node: edge->caller)->size,
2415	buf_net_change,
2416	cross_module_call_p (edge) ? " (cross module)":"");
2417	}
2418	if (min_size > overall_size)
2419	{
2420	min_size = overall_size;
2421
2422	if (dump_file)
2423	fprintf (stream: dump_file, format: "New minimal size reached: %i\n", min_size);
2424	}
2425	}
2426
2427	free_growth_caches ();
2428	if (dump_enabled_p ())
2429	dump_printf (MSG_NOTE,
2430	"Unit growth for small function inlining: %i->%i (%i%%)\n",
2431	initial_size, overall_size,
2432	initial_size ? overall_size * 100 / (initial_size) - 100: 0);
2433	symtab->remove_edge_removal_hook (entry: edge_removal_hook_holder);
2434	}
2435
2436	/* Flatten NODE. Performed both during early inlining and
2437	at IPA inlining time. */
2438
2439	static void
2440	flatten_function (struct cgraph_node *node, bool early, bool update)
2441	{
2442	struct cgraph_edge *e;
2443
2444	/* We shouldn't be called recursively when we are being processed. */
2445	gcc_assert (node->aux == NULL);
2446
2447	node->aux = (void *) node;
2448
2449	for (e = node->callees; e; e = e->next_callee)
2450	{
2451	struct cgraph_node *orig_callee;
2452	struct cgraph_node *callee = e->callee->ultimate_alias_target ();
2453
2454	/* We've hit cycle? It is time to give up. */
2455	if (callee->aux)
2456	{
2457	if (dump_enabled_p ())
2458	dump_printf_loc (MSG_MISSED_OPTIMIZATION, e->call_stmt,
2459	"Not inlining %C into %C to avoid cycle.\n",
2460	callee, e->caller);
2461	if (cgraph_inline_failed_type (e->inline_failed) != CIF_FINAL_ERROR)
2462	e->inline_failed = CIF_RECURSIVE_INLINING;
2463	continue;
2464	}
2465
2466	/* When the edge is already inlined, we just need to recurse into
2467	it in order to fully flatten the leaves. */
2468	if (!e->inline_failed)
2469	{
2470	flatten_function (node: callee, early, update: false);
2471	continue;
2472	}
2473
2474	/* Flatten attribute needs to be processed during late inlining. For
2475	extra code quality we however do flattening during early optimization,
2476	too. */
2477	if (!early
2478	? !can_inline_edge_p (e, report: true)
2479	&& !can_inline_edge_by_limits_p (e, report: true)
2480	: !can_early_inline_edge_p (e))
2481	continue;
2482
2483	if (e->recursive_p ())
2484	{
2485	if (dump_enabled_p ())
2486	dump_printf_loc (MSG_MISSED_OPTIMIZATION, e->call_stmt,
2487	"Not inlining: recursive call.\n");
2488	continue;
2489	}
2490
2491	if (gimple_in_ssa_p (DECL_STRUCT_FUNCTION (node->decl))
2492	!= gimple_in_ssa_p (DECL_STRUCT_FUNCTION (callee->decl)))
2493	{
2494	if (dump_enabled_p ())
2495	dump_printf_loc (MSG_MISSED_OPTIMIZATION, e->call_stmt,
2496	"Not inlining: SSA form does not match.\n");
2497	continue;
2498	}
2499
2500	/* Inline the edge and flatten the inline clone. Avoid
2501	recursing through the original node if the node was cloned. */
2502	if (dump_enabled_p ())
2503	dump_printf_loc (MSG_OPTIMIZED_LOCATIONS, e->call_stmt,
2504	" Inlining %C into %C.\n",
2505	callee, e->caller);
2506	orig_callee = callee;
2507	inline_call (e, true, NULL, NULL, false);
2508	if (e->callee != orig_callee)
2509	orig_callee->aux = (void *) node;
2510	flatten_function (node: e->callee, early, update: false);
2511	if (e->callee != orig_callee)
2512	orig_callee->aux = NULL;
2513	}
2514
2515	node->aux = NULL;
2516	cgraph_node *where = node->inlined_to ? node->inlined_to : node;
2517	if (update && opt_for_fn (where->decl, optimize))
2518	ipa_update_overall_fn_summary (node: where);
2519	}
2520
2521	/* Inline NODE to all callers. Worker for cgraph_for_node_and_aliases.
2522	DATA points to number of calls originally found so we avoid infinite
2523	recursion. */
2524
2525	static bool
2526	inline_to_all_callers_1 (struct cgraph_node *node, void *data,
2527	hash_set<cgraph_node *> *callers)
2528	{
2529	int *num_calls = (int *)data;
2530	bool callee_removed = false;
2531
2532	while (node->callers && !node->inlined_to)
2533	{
2534	struct cgraph_node *caller = node->callers->caller;
2535
2536	if (!can_inline_edge_p (e: node->callers, report: true)
2537	|| !can_inline_edge_by_limits_p (e: node->callers, report: true)
2538	|| node->callers->recursive_p ())
2539	{
2540	if (dump_file)
2541	fprintf (stream: dump_file, format: "Uninlinable call found; giving up.\n");
2542	*num_calls = 0;
2543	return false;
2544	}
2545
2546	if (dump_file)
2547	{
2548	cgraph_node *ultimate = node->ultimate_alias_target ();
2549	fprintf (stream: dump_file,
2550	format: "\nInlining %s size %i.\n",
2551	ultimate->dump_name (),
2552	ipa_size_summaries->get (node: ultimate)->size);
2553	fprintf (stream: dump_file,
2554	format: " Called once from %s %i insns.\n",
2555	node->callers->caller->dump_name (),
2556	ipa_size_summaries->get (node: node->callers->caller)->size);
2557	}
2558
2559	/* Remember which callers we inlined to, delaying updating the
2560	overall summary. */
2561	callers->add (k: node->callers->caller);
2562	inline_call (node->callers, true, NULL, NULL, false, callee_removed: &callee_removed);
2563	if (dump_file)
2564	fprintf (stream: dump_file,
2565	format: " Inlined into %s which now has %i size\n",
2566	caller->dump_name (),
2567	ipa_size_summaries->get (node: caller)->size);
2568	if (!(*num_calls)--)
2569	{
2570	if (dump_file)
2571	fprintf (stream: dump_file, format: "New calls found; giving up.\n");
2572	return callee_removed;
2573	}
2574	if (callee_removed)
2575	return true;
2576	}
2577	return false;
2578	}
2579
2580	/* Wrapper around inline_to_all_callers_1 doing delayed overall summary
2581	update. */
2582
2583	static bool
2584	inline_to_all_callers (struct cgraph_node *node, void *data)
2585	{
2586	hash_set<cgraph_node *> callers;
2587	bool res = inline_to_all_callers_1 (node, data, callers: &callers);
2588	/* Perform the delayed update of the overall summary of all callers
2589	processed. This avoids quadratic behavior in the cases where
2590	we have a lot of calls to the same function. */
2591	for (hash_set<cgraph_node *>::iterator i = callers.begin ();
2592	i != callers.end (); ++i)
2593	ipa_update_overall_fn_summary (node: (*i)->inlined_to ? (*i)->inlined_to : *i);
2594	return res;
2595	}
2596
2597	/* Output overall time estimate. */
2598	static void
2599	dump_overall_stats (void)
2600	{
2601	sreal sum_weighted = 0, sum = 0;
2602	struct cgraph_node *node;
2603
2604	FOR_EACH_DEFINED_FUNCTION (node)
2605	if (!node->inlined_to
2606	&& !node->alias)
2607	{
2608	ipa_fn_summary *s = ipa_fn_summaries->get (node);
2609	if (s != NULL)
2610	{
2611	sum += s->time;
2612	if (node->count.ipa ().initialized_p ())
2613	sum_weighted += s->time * node->count.ipa ().to_gcov_type ();
2614	}
2615	}
2616	fprintf (stream: dump_file, format: "Overall time estimate: "
2617	"%f weighted by profile: "
2618	"%f\n", sum.to_double (), sum_weighted.to_double ());
2619	}
2620
2621	/* Output some useful stats about inlining. */
2622
2623	static void
2624	dump_inline_stats (void)
2625	{
2626	int64_t inlined_cnt = 0, inlined_indir_cnt = 0;
2627	int64_t inlined_virt_cnt = 0, inlined_virt_indir_cnt = 0;
2628	int64_t noninlined_cnt = 0, noninlined_indir_cnt = 0;
2629	int64_t noninlined_virt_cnt = 0, noninlined_virt_indir_cnt = 0;
2630	int64_t inlined_speculative = 0, inlined_speculative_ply = 0;
2631	int64_t indirect_poly_cnt = 0, indirect_cnt = 0;
2632	int64_t reason[CIF_N_REASONS][2];
2633	sreal reason_freq[CIF_N_REASONS];
2634	int i;
2635	struct cgraph_node *node;
2636
2637	memset (s: reason, c: 0, n: sizeof (reason));
2638	for (i=0; i < CIF_N_REASONS; i++)
2639	reason_freq[i] = 0;
2640	FOR_EACH_DEFINED_FUNCTION (node)
2641	{
2642	struct cgraph_edge *e;
2643	for (e = node->callees; e; e = e->next_callee)
2644	{
2645	if (e->inline_failed)
2646	{
2647	if (e->count.ipa ().initialized_p ())
2648	reason[(int) e->inline_failed][0] += e->count.ipa ().to_gcov_type ();
2649	reason_freq[(int) e->inline_failed] += e->sreal_frequency ();
2650	reason[(int) e->inline_failed][1] ++;
2651	if (DECL_VIRTUAL_P (e->callee->decl)
2652	&& e->count.ipa ().initialized_p ())
2653	{
2654	if (e->indirect_inlining_edge)
2655	noninlined_virt_indir_cnt += e->count.ipa ().to_gcov_type ();
2656	else
2657	noninlined_virt_cnt += e->count.ipa ().to_gcov_type ();
2658	}
2659	else if (e->count.ipa ().initialized_p ())
2660	{
2661	if (e->indirect_inlining_edge)
2662	noninlined_indir_cnt += e->count.ipa ().to_gcov_type ();
2663	else
2664	noninlined_cnt += e->count.ipa ().to_gcov_type ();
2665	}
2666	}
2667	else if (e->count.ipa ().initialized_p ())
2668	{
2669	if (e->speculative)
2670	{
2671	if (DECL_VIRTUAL_P (e->callee->decl))
2672	inlined_speculative_ply += e->count.ipa ().to_gcov_type ();
2673	else
2674	inlined_speculative += e->count.ipa ().to_gcov_type ();
2675	}
2676	else if (DECL_VIRTUAL_P (e->callee->decl))
2677	{
2678	if (e->indirect_inlining_edge)
2679	inlined_virt_indir_cnt += e->count.ipa ().to_gcov_type ();
2680	else
2681	inlined_virt_cnt += e->count.ipa ().to_gcov_type ();
2682	}
2683	else
2684	{
2685	if (e->indirect_inlining_edge)
2686	inlined_indir_cnt += e->count.ipa ().to_gcov_type ();
2687	else
2688	inlined_cnt += e->count.ipa ().to_gcov_type ();
2689	}
2690	}
2691	}
2692	for (e = node->indirect_calls; e; e = e->next_callee)
2693	if (e->indirect_info->polymorphic
2694	& e->count.ipa ().initialized_p ())
2695	indirect_poly_cnt += e->count.ipa ().to_gcov_type ();
2696	else if (e->count.ipa ().initialized_p ())
2697	indirect_cnt += e->count.ipa ().to_gcov_type ();
2698	}
2699	if (max_count.initialized_p ())
2700	{
2701	fprintf (stream: dump_file,
2702	format: "Inlined %" PRId64 " + speculative "
2703	"%" PRId64 " + speculative polymorphic "
2704	"%" PRId64 " + previously indirect "
2705	"%" PRId64 " + virtual "
2706	"%" PRId64 " + virtual and previously indirect "
2707	"%" PRId64 "\n" "Not inlined "
2708	"%" PRId64 " + previously indirect "
2709	"%" PRId64 " + virtual "
2710	"%" PRId64 " + virtual and previously indirect "
2711	"%" PRId64 " + still indirect "
2712	"%" PRId64 " + still indirect polymorphic "
2713	"%" PRId64 "\n", inlined_cnt,
2714	inlined_speculative, inlined_speculative_ply,
2715	inlined_indir_cnt, inlined_virt_cnt, inlined_virt_indir_cnt,
2716	noninlined_cnt, noninlined_indir_cnt, noninlined_virt_cnt,
2717	noninlined_virt_indir_cnt, indirect_cnt, indirect_poly_cnt);
2718	fprintf (stream: dump_file, format: "Removed speculations ");
2719	spec_rem.dump (f: dump_file);
2720	fprintf (stream: dump_file, format: "\n");
2721	}
2722	dump_overall_stats ();
2723	fprintf (stream: dump_file, format: "\nWhy inlining failed?\n");
2724	for (i = 0; i < CIF_N_REASONS; i++)
2725	if (reason[i][1])
2726	fprintf (stream: dump_file, format: "%-50s: %8i calls, %8f freq, %" PRId64" count\n",
2727	cgraph_inline_failed_string ((cgraph_inline_failed_t) i),
2728	(int) reason[i][1], reason_freq[i].to_double (), reason[i][0]);
2729	}
2730
2731	/* Called when node is removed. */
2732
2733	static void
2734	flatten_remove_node_hook (struct cgraph_node *node, void *data)
2735	{
2736	if (lookup_attribute (attr_name: "flatten", DECL_ATTRIBUTES (node->decl)) == NULL)
2737	return;
2738
2739	hash_set<struct cgraph_node *> *removed
2740	= (hash_set<struct cgraph_node *> *) data;
2741	removed->add (k: node);
2742	}
2743
2744	/* Decide on the inlining. We do so in the topological order to avoid
2745	expenses on updating data structures. */
2746
2747	static unsigned int
2748	ipa_inline (void)
2749	{
2750	struct cgraph_node *node;
2751	int nnodes;
2752	struct cgraph_node **order;
2753	int i, j;
2754	int cold;
2755	bool remove_functions = false;
2756
2757	order = XCNEWVEC (struct cgraph_node *, symtab->cgraph_count);
2758
2759	if (dump_file)
2760	ipa_dump_fn_summaries (f: dump_file);
2761
2762	nnodes = ipa_reverse_postorder (order);
2763	spec_rem = profile_count::zero ();
2764
2765	FOR_EACH_FUNCTION (node)
2766	{
2767	node->aux = 0;
2768
2769	/* Recompute the default reasons for inlining because they may have
2770	changed during merging. */
2771	if (in_lto_p)
2772	{
2773	for (cgraph_edge *e = node->callees; e; e = e->next_callee)
2774	{
2775	gcc_assert (e->inline_failed);
2776	initialize_inline_failed (e);
2777	}
2778	for (cgraph_edge *e = node->indirect_calls; e; e = e->next_callee)
2779	initialize_inline_failed (e);
2780	}
2781	}
2782
2783	if (dump_file)
2784	fprintf (stream: dump_file, format: "\nFlattening functions:\n");
2785
2786	/* First shrink order array, so that it only contains nodes with
2787	flatten attribute. */
2788	for (i = nnodes - 1, j = i; i >= 0; i--)
2789	{
2790	node = order[i];
2791	if (node->definition
2792	/* Do not try to flatten aliases. These may happen for example when
2793	creating local aliases. */
2794	&& !node->alias
2795	&& lookup_attribute (attr_name: "flatten",
2796	DECL_ATTRIBUTES (node->decl)) != NULL)
2797	order[j--] = order[i];
2798	}
2799
2800	/* After the above loop, order[j + 1] ... order[nnodes - 1] contain
2801	nodes with flatten attribute. If there is more than one such
2802	node, we need to register a node removal hook, as flatten_function
2803	could remove other nodes with flatten attribute. See PR82801. */
2804	struct cgraph_node_hook_list *node_removal_hook_holder = NULL;
2805	hash_set<struct cgraph_node *> *flatten_removed_nodes = NULL;
2806	if (j < nnodes - 2)
2807	{
2808	flatten_removed_nodes = new hash_set<struct cgraph_node *>;
2809	node_removal_hook_holder
2810	= symtab->add_cgraph_removal_hook (hook: &flatten_remove_node_hook,
2811	data: flatten_removed_nodes);
2812	}
2813
2814	/* In the first pass handle functions to be flattened. Do this with
2815	a priority so none of our later choices will make this impossible. */
2816	for (i = nnodes - 1; i > j; i--)
2817	{
2818	node = order[i];
2819	if (flatten_removed_nodes
2820	&& flatten_removed_nodes->contains (k: node))
2821	continue;
2822
2823	/* Handle nodes to be flattened.
2824	Ideally when processing callees we stop inlining at the
2825	entry of cycles, possibly cloning that entry point and
2826	try to flatten itself turning it into a self-recursive
2827	function. */
2828	if (dump_file)
2829	fprintf (stream: dump_file, format: "Flattening %s\n", node->dump_name ());
2830	flatten_function (node, early: false, update: true);
2831	}
2832
2833	if (j < nnodes - 2)
2834	{
2835	symtab->remove_cgraph_removal_hook (entry: node_removal_hook_holder);
2836	delete flatten_removed_nodes;
2837	}
2838	free (ptr: order);
2839
2840	if (dump_file)
2841	dump_overall_stats ();
2842
2843	inline_small_functions ();
2844
2845	gcc_assert (symtab->state == IPA_SSA);
2846	symtab->state = IPA_SSA_AFTER_INLINING;
2847	/* Do first after-inlining removal. We want to remove all "stale" extern
2848	inline functions and virtual functions so we really know what is called
2849	once. */
2850	symtab->remove_unreachable_nodes (file: dump_file);
2851
2852	/* Inline functions with a property that after inlining into all callers the
2853	code size will shrink because the out-of-line copy is eliminated.
2854	We do this regardless on the callee size as long as function growth limits
2855	are met. */
2856	if (dump_file)
2857	fprintf (stream: dump_file,
2858	format: "\nDeciding on functions to be inlined into all callers and "
2859	"removing useless speculations:\n");
2860
2861	/* Inlining one function called once has good chance of preventing
2862	inlining other function into the same callee. Ideally we should
2863	work in priority order, but probably inlining hot functions first
2864	is good cut without the extra pain of maintaining the queue.
2865
2866	??? this is not really fitting the bill perfectly: inlining function
2867	into callee often leads to better optimization of callee due to
2868	increased context for optimization.
2869	For example if main() function calls a function that outputs help
2870	and then function that does the main optimization, we should inline
2871	the second with priority even if both calls are cold by themselves.
2872
2873	We probably want to implement new predicate replacing our use of
2874	maybe_hot_edge interpreted as maybe_hot_edge || callee is known
2875	to be hot. */
2876	for (cold = 0; cold <= 1; cold ++)
2877	{
2878	FOR_EACH_DEFINED_FUNCTION (node)
2879	{
2880	struct cgraph_edge *edge, *next;
2881	bool update=false;
2882
2883	if (!opt_for_fn (node->decl, optimize)
2884	|| !opt_for_fn (node->decl, flag_inline_functions_called_once))
2885	continue;
2886
2887	for (edge = node->callees; edge; edge = next)
2888	{
2889	next = edge->next_callee;
2890	if (edge->speculative && !speculation_useful_p (e: edge, anticipate_inlining: false))
2891	{
2892	if (edge->count.ipa ().initialized_p ())
2893	spec_rem += edge->count.ipa ();
2894	cgraph_edge::resolve_speculation (edge);
2895	update = true;
2896	remove_functions = true;
2897	}
2898	}
2899	if (update)
2900	{
2901	struct cgraph_node *where = node->inlined_to
2902	? node->inlined_to : node;
2903	reset_edge_caches (node: where);
2904	ipa_update_overall_fn_summary (node: where);
2905	}
2906	if (want_inline_function_to_all_callers_p (node, cold))
2907	{
2908	int num_calls = 0;
2909	node->call_for_symbol_and_aliases (callback: sum_callers, data: &num_calls,
2910	include_overwritable: true);
2911	while (node->call_for_symbol_and_aliases
2912	(callback: inline_to_all_callers, data: &num_calls, include_overwritable: true))
2913	;
2914	remove_functions = true;
2915	}
2916	}
2917	}
2918
2919	if (dump_enabled_p ())
2920	dump_printf (MSG_NOTE,
2921	"\nInlined %i calls, eliminated %i functions\n\n",
2922	ncalls_inlined, nfunctions_inlined);
2923	if (dump_file)
2924	dump_inline_stats ();
2925
2926	if (dump_file)
2927	ipa_dump_fn_summaries (f: dump_file);
2928	return remove_functions ? TODO_remove_functions : 0;
2929	}
2930
2931	/* Inline always-inline function calls in NODE
2932	(which itself is possibly inline). */
2933
2934	static bool
2935	inline_always_inline_functions (struct cgraph_node *node)
2936	{
2937	struct cgraph_edge *e;
2938	bool inlined = false;
2939
2940	for (e = node->callees; e; e = e->next_callee)
2941	{
2942	struct cgraph_node *callee = e->callee->ultimate_alias_target ();
2943	gcc_checking_assert (!callee->aux || callee->aux == (void *)(size_t)1);
2944	if (!DECL_DISREGARD_INLINE_LIMITS (callee->decl)
2945	/* Watch for self-recursive cycles. */
2946	|| callee->aux)
2947	continue;
2948
2949	if (e->recursive_p ())
2950	{
2951	if (dump_enabled_p ())
2952	dump_printf_loc (MSG_MISSED_OPTIMIZATION, e->call_stmt,
2953	" Not inlining recursive call to %C.\n",
2954	e->callee);
2955	e->inline_failed = CIF_RECURSIVE_INLINING;
2956	continue;
2957	}
2958	if (callee->definition
2959	&& !ipa_fn_summaries->get (node: callee))
2960	compute_fn_summary (callee, true);
2961
2962	if (!can_early_inline_edge_p (e))
2963	{
2964	/* Set inlined to true if the callee is marked "always_inline" but
2965	is not inlinable. This will allow flagging an error later in
2966	expand_call_inline in tree-inline.cc. */
2967	if (lookup_attribute (attr_name: "always_inline",
2968	DECL_ATTRIBUTES (callee->decl)) != NULL)
2969	inlined = true;
2970	continue;
2971	}
2972
2973	if (dump_enabled_p ())
2974	dump_printf_loc (MSG_OPTIMIZED_LOCATIONS, e->call_stmt,
2975	" Inlining %C into %C (always_inline).\n",
2976	e->callee, e->caller);
2977	inline_call (e, true, NULL, NULL, false);
2978	callee->aux = (void *)(size_t)1;
2979	/* Inline recursively to handle the case where always_inline function was
2980	not optimized yet since it is a part of a cycle in callgraph. */
2981	inline_always_inline_functions (node: e->callee);
2982	callee->aux = NULL;
2983	inlined = true;
2984	}
2985	return inlined;
2986	}
2987
2988	/* Decide on the inlining. We do so in the topological order to avoid
2989	expenses on updating data structures. */
2990
2991	static bool
2992	early_inline_small_functions (struct cgraph_node *node)
2993	{
2994	struct cgraph_edge *e;
2995	bool inlined = false;
2996
2997	for (e = node->callees; e; e = e->next_callee)
2998	{
2999	struct cgraph_node *callee = e->callee->ultimate_alias_target ();
3000
3001	/* We can encounter not-yet-analyzed function during
3002	early inlining on callgraphs with strongly
3003	connected components. */
3004	ipa_fn_summary *s = ipa_fn_summaries->get (node: callee);
3005	if (s == NULL || !s->inlinable || !e->inline_failed)
3006	continue;
3007
3008	/* Do not consider functions not declared inline. */
3009	if (!DECL_DECLARED_INLINE_P (callee->decl)
3010	&& !opt_for_fn (node->decl, flag_inline_small_functions)
3011	&& !opt_for_fn (node->decl, flag_inline_functions))
3012	continue;
3013
3014	if (dump_enabled_p ())
3015	dump_printf_loc (MSG_NOTE, e->call_stmt,
3016	"Considering inline candidate %C.\n",
3017	callee);
3018
3019	if (!can_early_inline_edge_p (e))
3020	continue;
3021
3022	if (e->recursive_p ())
3023	{
3024	if (dump_enabled_p ())
3025	dump_printf_loc (MSG_MISSED_OPTIMIZATION, e->call_stmt,
3026	" Not inlining: recursive call.\n");
3027	continue;
3028	}
3029
3030	if (!want_early_inline_function_p (e))
3031	continue;
3032
3033	if (dump_enabled_p ())
3034	dump_printf_loc (MSG_OPTIMIZED_LOCATIONS, e->call_stmt,
3035	" Inlining %C into %C.\n",
3036	callee, e->caller);
3037	inline_call (e, true, NULL, NULL, false);
3038	inlined = true;
3039	}
3040
3041	if (inlined)
3042	ipa_update_overall_fn_summary (node);
3043
3044	return inlined;
3045	}
3046
3047	unsigned int
3048	early_inliner (function *fun)
3049	{
3050	struct cgraph_node *node = cgraph_node::get (decl: current_function_decl);
3051	struct cgraph_edge *edge;
3052	unsigned int todo = 0;
3053	int iterations = 0;
3054	bool inlined = false;
3055
3056	if (seen_error ())
3057	return 0;
3058
3059	/* Do nothing if datastructures for ipa-inliner are already computed. This
3060	happens when some pass decides to construct new function and
3061	cgraph_add_new_function calls lowering passes and early optimization on
3062	it. This may confuse ourself when early inliner decide to inline call to
3063	function clone, because function clones don't have parameter list in
3064	ipa-prop matching their signature. */
3065	if (ipa_node_params_sum)
3066	return 0;
3067
3068	if (flag_checking)
3069	node->verify ();
3070	node->remove_all_references ();
3071
3072	/* Even when not optimizing or not inlining inline always-inline
3073	functions. */
3074	inlined = inline_always_inline_functions (node);
3075
3076	if (!optimize
3077	|| flag_no_inline
3078	|| !flag_early_inlining)
3079	;
3080	else if (lookup_attribute (attr_name: "flatten",
3081	DECL_ATTRIBUTES (node->decl)) != NULL)
3082	{
3083	/* When the function is marked to be flattened, recursively inline
3084	all calls in it. */
3085	if (dump_enabled_p ())
3086	dump_printf (MSG_OPTIMIZED_LOCATIONS,
3087	"Flattening %C\n", node);
3088	flatten_function (node, early: true, update: true);
3089	inlined = true;
3090	}
3091	else
3092	{
3093	/* If some always_inline functions was inlined, apply the changes.
3094	This way we will not account always inline into growth limits and
3095	moreover we will inline calls from always inlines that we skipped
3096	previously because of conditional in can_early_inline_edge_p
3097	which prevents some inlining to always_inline. */
3098	if (inlined)
3099	{
3100	timevar_push (tv: TV_INTEGRATION);
3101	todo |= optimize_inline_calls (current_function_decl);
3102	/* optimize_inline_calls call above might have introduced new
3103	statements that don't have inline parameters computed. */
3104	for (edge = node->callees; edge; edge = edge->next_callee)
3105	{
3106	/* We can enounter not-yet-analyzed function during
3107	early inlining on callgraphs with strongly
3108	connected components. */
3109	ipa_call_summary *es = ipa_call_summaries->get_create (edge);
3110	es->call_stmt_size
3111	= estimate_num_insns (edge->call_stmt, &eni_size_weights);
3112	es->call_stmt_time
3113	= estimate_num_insns (edge->call_stmt, &eni_time_weights);
3114	}
3115	ipa_update_overall_fn_summary (node);
3116	inlined = false;
3117	timevar_pop (tv: TV_INTEGRATION);
3118	}
3119	/* We iterate incremental inlining to get trivial cases of indirect
3120	inlining. */
3121	while (iterations < opt_for_fn (node->decl,
3122	param_early_inliner_max_iterations)
3123	&& early_inline_small_functions (node))
3124	{
3125	timevar_push (tv: TV_INTEGRATION);
3126	todo |= optimize_inline_calls (current_function_decl);
3127
3128	/* Technically we ought to recompute inline parameters so the new
3129	iteration of early inliner works as expected. We however have
3130	values approximately right and thus we only need to update edge
3131	info that might be cleared out for newly discovered edges. */
3132	for (edge = node->callees; edge; edge = edge->next_callee)
3133	{
3134	/* We have no summary for new bound store calls yet. */
3135	ipa_call_summary *es = ipa_call_summaries->get_create (edge);
3136	es->call_stmt_size
3137	= estimate_num_insns (edge->call_stmt, &eni_size_weights);
3138	es->call_stmt_time
3139	= estimate_num_insns (edge->call_stmt, &eni_time_weights);
3140	}
3141	if (iterations < opt_for_fn (node->decl,
3142	param_early_inliner_max_iterations) - 1)
3143	ipa_update_overall_fn_summary (node);
3144	timevar_pop (tv: TV_INTEGRATION);
3145	iterations++;
3146	inlined = false;
3147	}
3148	if (dump_file)
3149	fprintf (stream: dump_file, format: "Iterations: %i\n", iterations);
3150	}
3151
3152	if (inlined)
3153	{
3154	timevar_push (tv: TV_INTEGRATION);
3155	todo |= optimize_inline_calls (current_function_decl);
3156	timevar_pop (tv: TV_INTEGRATION);
3157	}
3158
3159	fun->always_inline_functions_inlined = true;
3160
3161	return todo;
3162	}
3163
3164	/* Do inlining of small functions. Doing so early helps profiling and other
3165	passes to be somewhat more effective and avoids some code duplication in
3166	later real inlining pass for testcases with very many function calls. */
3167
3168	namespace {
3169
3170	const pass_data pass_data_early_inline =
3171	{
3172	.type: GIMPLE_PASS, /* type */
3173	.name: "einline", /* name */
3174	.optinfo_flags: OPTGROUP_INLINE, /* optinfo_flags */
3175	.tv_id: TV_EARLY_INLINING, /* tv_id */
3176	PROP_ssa, /* properties_required */
3177	.properties_provided: 0, /* properties_provided */
3178	.properties_destroyed: 0, /* properties_destroyed */
3179	.todo_flags_start: 0, /* todo_flags_start */
3180	.todo_flags_finish: 0, /* todo_flags_finish */
3181	};
3182
3183	class pass_early_inline : public gimple_opt_pass
3184	{
3185	public:
3186	pass_early_inline (gcc::context *ctxt)
3187	: gimple_opt_pass (pass_data_early_inline, ctxt)
3188	{}
3189
3190	/* opt_pass methods: */
3191	unsigned int execute (function *) final override;
3192
3193	}; // class pass_early_inline
3194
3195	unsigned int
3196	pass_early_inline::execute (function *fun)
3197	{
3198	return early_inliner (fun);
3199	}
3200
3201	} // anon namespace
3202
3203	gimple_opt_pass *
3204	make_pass_early_inline (gcc::context *ctxt)
3205	{
3206	return new pass_early_inline (ctxt);
3207	}
3208
3209	namespace {
3210
3211	const pass_data pass_data_ipa_inline =
3212	{
3213	.type: IPA_PASS, /* type */
3214	.name: "inline", /* name */
3215	.optinfo_flags: OPTGROUP_INLINE, /* optinfo_flags */
3216	.tv_id: TV_IPA_INLINING, /* tv_id */
3217	.properties_required: 0, /* properties_required */
3218	.properties_provided: 0, /* properties_provided */
3219	.properties_destroyed: 0, /* properties_destroyed */
3220	.todo_flags_start: 0, /* todo_flags_start */
3221	.todo_flags_finish: ( TODO_dump_symtab ), /* todo_flags_finish */
3222	};
3223
3224	class pass_ipa_inline : public ipa_opt_pass_d
3225	{
3226	public:
3227	pass_ipa_inline (gcc::context *ctxt)
3228	: ipa_opt_pass_d (pass_data_ipa_inline, ctxt,
3229	NULL, /* generate_summary */
3230	NULL, /* write_summary */
3231	NULL, /* read_summary */
3232	NULL, /* write_optimization_summary */
3233	NULL, /* read_optimization_summary */
3234	NULL, /* stmt_fixup */
3235	0, /* function_transform_todo_flags_start */
3236	inline_transform, /* function_transform */
3237	NULL) /* variable_transform */
3238	{}
3239
3240	/* opt_pass methods: */
3241	unsigned int execute (function *) final override { return ipa_inline (); }
3242
3243	}; // class pass_ipa_inline
3244
3245	} // anon namespace
3246
3247	ipa_opt_pass_d *
3248	make_pass_ipa_inline (gcc::context *ctxt)
3249	{
3250	return new pass_ipa_inline (ctxt);
3251	}
3252