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