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