1 /* Inlining decision heuristics.
2 Copyright (C) 2003, 2004, 2007, 2008, 2009, 2010, 2011
3 Free Software Foundation, Inc.
4 Contributed by Jan Hubicka
6 This file is part of GCC.
8 GCC is free software; you can redistribute it and/or modify it under
9 the terms of the GNU General Public License as published by the Free
10 Software Foundation; either version 3, or (at your option) any later
13 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
14 WARRANTY; without even the implied warranty of MERCHANTABILITY or
15 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
18 You should have received a copy of the GNU General Public License
19 along with GCC; see the file COPYING3. If not see
20 <http://www.gnu.org/licenses/>. */
22 /* Analysis used by the inliner and other passes limiting code size growth.
24 We estimate for each function
26 - average function execution time
27 - inlining size benefit (that is how much of function body size
28 and its call sequence is expected to disappear by inlining)
29 - inlining time benefit
32 - call statement size and time
34 inlinie_summary datastructures store above information locally (i.e.
35 parameters of the function itself) and globally (i.e. parameters of
36 the function created by applying all the inline decisions already
37 present in the callgraph).
39 We also provide accestor to the inline_summary datastructure and
40 basic logic updating the parameters when inlining is performed.
42 Finally pass_inline_parameters is exported. This is used to drive
43 computation of function parameters used by the early inliner. IPA
44 inlined performs analysis via its analyze_function method. */
48 #include "coretypes.h"
51 #include "tree-inline.h"
52 #include "langhooks.h"
55 #include "diagnostic.h"
56 #include "gimple-pretty-print.h"
59 #include "tree-pass.h"
62 #include "tree-flow.h"
64 #include "lto-streamer.h"
65 #include "ipa-inline.h"
67 #define MAX_TIME 1000000000
69 /* Holders of ipa cgraph hooks: */
70 static struct cgraph_node_hook_list
*function_insertion_hook_holder
;
71 static struct cgraph_node_hook_list
*node_removal_hook_holder
;
72 static struct cgraph_2node_hook_list
*node_duplication_hook_holder
;
73 static void inline_node_removal_hook (struct cgraph_node
*, void *);
74 static void inline_node_duplication_hook (struct cgraph_node
*,
75 struct cgraph_node
*, void *);
77 /* VECtor holding inline summaries. */
78 VEC(inline_summary_t
,heap
) *inline_summary_vec
;
80 /* Allocate the inline summary vector or resize it to cover all cgraph nodes. */
83 inline_summary_alloc (void)
85 if (!node_removal_hook_holder
)
86 node_removal_hook_holder
=
87 cgraph_add_node_removal_hook (&inline_node_removal_hook
, NULL
);
88 if (!node_duplication_hook_holder
)
89 node_duplication_hook_holder
=
90 cgraph_add_node_duplication_hook (&inline_node_duplication_hook
, NULL
);
92 if (VEC_length (inline_summary_t
, inline_summary_vec
)
93 <= (unsigned) cgraph_max_uid
)
94 VEC_safe_grow_cleared (inline_summary_t
, heap
,
95 inline_summary_vec
, cgraph_max_uid
+ 1);
98 /* Hook that is called by cgraph.c when a node is removed. */
101 inline_node_removal_hook (struct cgraph_node
*node
, void *data ATTRIBUTE_UNUSED
)
103 struct inline_summary
*info
;
104 if (VEC_length (inline_summary_t
, inline_summary_vec
)
105 <= (unsigned)node
->uid
)
107 info
= inline_summary (node
);
108 info
->estimated_growth
= INT_MIN
;
109 memset (info
, 0, sizeof (inline_summary_t
));
112 /* Hook that is called by cgraph.c when a node is duplicated. */
115 inline_node_duplication_hook (struct cgraph_node
*src
, struct cgraph_node
*dst
,
116 ATTRIBUTE_UNUSED
void *data
)
118 struct inline_summary
*info
;
119 inline_summary_alloc ();
120 info
= inline_summary (dst
);
121 memcpy (info
, inline_summary (src
),
122 sizeof (struct inline_summary
));
123 info
->estimated_growth
= INT_MIN
;
127 dump_inline_summary (FILE *f
, struct cgraph_node
*node
)
131 struct inline_summary
*s
= inline_summary (node
);
132 fprintf (f
, "Inline summary for %s/%i", cgraph_node_name (node
),
134 if (DECL_DISREGARD_INLINE_LIMITS (node
->decl
))
135 fprintf (f
, " always_inline");
137 fprintf (f
, " inlinable");
139 fprintf (f
, " versionable");
140 fprintf (f
, "\n self time: %i, benefit: %i\n",
141 s
->self_time
, s
->time_inlining_benefit
);
142 fprintf (f
, " global time: %i\n", s
->time
);
143 fprintf (f
, " self size: %i, benefit: %i\n",
144 s
->self_size
, s
->size_inlining_benefit
);
145 fprintf (f
, " global size: %i\n", s
->size
);
146 fprintf (f
, " self stack: %i\n",
147 (int)s
->estimated_self_stack_size
);
148 fprintf (f
, " global stack: %i\n\n",
149 (int)s
->estimated_stack_size
);
154 debug_inline_summary (struct cgraph_node
*node
)
156 dump_inline_summary (stderr
, node
);
160 dump_inline_summaries (FILE *f
)
162 struct cgraph_node
*node
;
164 for (node
= cgraph_nodes
; node
; node
= node
->next
)
166 dump_inline_summary (f
, node
);
169 /* Give initial reasons why inlining would fail on EDGE. This gets either
170 nullified or usually overwritten by more precise reasons later. */
173 initialize_inline_failed (struct cgraph_edge
*e
)
175 struct cgraph_node
*callee
= e
->callee
;
177 if (e
->indirect_unknown_callee
)
178 e
->inline_failed
= CIF_INDIRECT_UNKNOWN_CALL
;
179 else if (!callee
->analyzed
)
180 e
->inline_failed
= CIF_BODY_NOT_AVAILABLE
;
181 else if (callee
->local
.redefined_extern_inline
)
182 e
->inline_failed
= CIF_REDEFINED_EXTERN_INLINE
;
183 else if (e
->call_stmt
&& gimple_call_cannot_inline_p (e
->call_stmt
))
184 e
->inline_failed
= CIF_MISMATCHED_ARGUMENTS
;
186 e
->inline_failed
= CIF_FUNCTION_NOT_CONSIDERED
;
189 /* See if statement might disappear after inlining.
190 0 - means not eliminated
191 1 - half of statements goes away
192 2 - for sure it is eliminated.
193 We are not terribly sophisticated, basically looking for simple abstraction
197 eliminated_by_inlining_prob (gimple stmt
)
199 enum gimple_code code
= gimple_code (stmt
);
205 if (gimple_num_ops (stmt
) != 2)
208 /* Casts of parameters, loads from parameters passed by reference
209 and stores to return value or parameters are often free after
210 inlining dua to SRA and further combining.
211 Assume that half of statements goes away. */
212 if (gimple_assign_rhs_code (stmt
) == CONVERT_EXPR
213 || gimple_assign_rhs_code (stmt
) == NOP_EXPR
214 || gimple_assign_rhs_code (stmt
) == VIEW_CONVERT_EXPR
215 || gimple_assign_rhs_class (stmt
) == GIMPLE_SINGLE_RHS
)
217 tree rhs
= gimple_assign_rhs1 (stmt
);
218 tree lhs
= gimple_assign_lhs (stmt
);
219 tree inner_rhs
= rhs
;
220 tree inner_lhs
= lhs
;
221 bool rhs_free
= false;
222 bool lhs_free
= false;
224 while (handled_component_p (inner_lhs
)
225 || TREE_CODE (inner_lhs
) == MEM_REF
)
226 inner_lhs
= TREE_OPERAND (inner_lhs
, 0);
227 while (handled_component_p (inner_rhs
)
228 || TREE_CODE (inner_rhs
) == ADDR_EXPR
229 || TREE_CODE (inner_rhs
) == MEM_REF
)
230 inner_rhs
= TREE_OPERAND (inner_rhs
, 0);
233 if (TREE_CODE (inner_rhs
) == PARM_DECL
234 || (TREE_CODE (inner_rhs
) == SSA_NAME
235 && SSA_NAME_IS_DEFAULT_DEF (inner_rhs
)
236 && TREE_CODE (SSA_NAME_VAR (inner_rhs
)) == PARM_DECL
))
238 if (rhs_free
&& is_gimple_reg (lhs
))
240 if (((TREE_CODE (inner_lhs
) == PARM_DECL
241 || (TREE_CODE (inner_lhs
) == SSA_NAME
242 && SSA_NAME_IS_DEFAULT_DEF (inner_lhs
)
243 && TREE_CODE (SSA_NAME_VAR (inner_lhs
)) == PARM_DECL
))
245 || TREE_CODE (inner_lhs
) == RESULT_DECL
246 || (TREE_CODE (inner_lhs
) == SSA_NAME
247 && TREE_CODE (SSA_NAME_VAR (inner_lhs
)) == RESULT_DECL
))
250 && (is_gimple_reg (rhs
) || is_gimple_min_invariant (rhs
)))
252 if (lhs_free
&& rhs_free
)
262 /* Compute function body size parameters for NODE. */
265 estimate_function_body_sizes (struct cgraph_node
*node
)
268 gcov_type time_inlining_benefit
= 0;
269 /* Estimate static overhead for function prologue/epilogue and alignment. */
271 /* Benefits are scaled by probability of elimination that is in range
273 int size_inlining_benefit
= 2 * 2;
275 gimple_stmt_iterator bsi
;
276 struct function
*my_function
= DECL_STRUCT_FUNCTION (node
->decl
);
280 fprintf (dump_file
, "Analyzing function body size: %s\n",
281 cgraph_node_name (node
));
283 gcc_assert (my_function
&& my_function
->cfg
);
284 FOR_EACH_BB_FN (bb
, my_function
)
286 freq
= compute_call_stmt_bb_frequency (node
->decl
, bb
);
287 for (bsi
= gsi_start_bb (bb
); !gsi_end_p (bsi
); gsi_next (&bsi
))
289 gimple stmt
= gsi_stmt (bsi
);
290 int this_size
= estimate_num_insns (stmt
, &eni_size_weights
);
291 int this_time
= estimate_num_insns (stmt
, &eni_time_weights
);
294 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
296 fprintf (dump_file
, " freq:%6i size:%3i time:%3i ",
297 freq
, this_size
, this_time
);
298 print_gimple_stmt (dump_file
, stmt
, 0, 0);
301 if (is_gimple_call (stmt
))
303 struct cgraph_edge
*edge
= cgraph_edge (node
, stmt
);
304 edge
->call_stmt_size
= this_size
;
305 edge
->call_stmt_time
= this_time
;
307 /* Do not inline calls where we cannot triviall work around mismatches
308 in argument or return types. */
310 && !gimple_check_call_matching_types (stmt
, edge
->callee
->decl
))
312 edge
->call_stmt_cannot_inline_p
= true;
313 gimple_call_set_cannot_inline (stmt
, true);
316 gcc_assert (!gimple_call_cannot_inline_p (stmt
));
323 prob
= eliminated_by_inlining_prob (stmt
);
324 if (prob
== 1 && dump_file
&& (dump_flags
& TDF_DETAILS
))
325 fprintf (dump_file
, " 50%% will be eliminated by inlining\n");
326 if (prob
== 2 && dump_file
&& (dump_flags
& TDF_DETAILS
))
327 fprintf (dump_file
, " will eliminated by inlining\n");
329 size_inlining_benefit
+= this_size
* prob
;
330 time_inlining_benefit
+= this_time
* prob
;
332 gcc_assert (time
>= 0);
333 gcc_assert (size
>= 0);
336 time
= (time
+ CGRAPH_FREQ_BASE
/ 2) / CGRAPH_FREQ_BASE
;
337 time_inlining_benefit
= ((time_inlining_benefit
+ CGRAPH_FREQ_BASE
)
338 / (CGRAPH_FREQ_BASE
* 2));
339 size_inlining_benefit
= (size_inlining_benefit
+ 1) / 2;
340 if (time_inlining_benefit
> MAX_TIME
)
341 time_inlining_benefit
= MAX_TIME
;
345 fprintf (dump_file
, "Overall function body time: %i-%i size: %i-%i\n",
346 (int)time
, (int)time_inlining_benefit
,
347 size
, size_inlining_benefit
);
348 inline_summary (node
)->self_time
= time
;
349 inline_summary (node
)->self_size
= size
;
350 inline_summary (node
)->time_inlining_benefit
= time_inlining_benefit
;
351 inline_summary (node
)->size_inlining_benefit
= size_inlining_benefit
;
355 /* Compute parameters of functions used by inliner. */
358 compute_inline_parameters (struct cgraph_node
*node
)
360 HOST_WIDE_INT self_stack_size
;
361 struct cgraph_edge
*e
;
362 struct inline_summary
*info
;
364 gcc_assert (!node
->global
.inlined_to
);
366 inline_summary_alloc ();
368 info
= inline_summary (node
);
370 /* Estimate the stack size for the function if we're optimizing. */
371 self_stack_size
= optimize
? estimated_stack_frame_size (node
) : 0;
372 info
->estimated_self_stack_size
= self_stack_size
;
373 info
->estimated_stack_size
= self_stack_size
;
374 info
->stack_frame_offset
= 0;
376 /* Can this function be inlined at all? */
377 info
->inlinable
= tree_inlinable_function_p (node
->decl
);
379 /* Inlinable functions always can change signature. */
381 node
->local
.can_change_signature
= true;
384 /* Functions calling builtin_apply can not change signature. */
385 for (e
= node
->callees
; e
; e
= e
->next_callee
)
386 if (DECL_BUILT_IN (e
->callee
->decl
)
387 && DECL_BUILT_IN_CLASS (e
->callee
->decl
) == BUILT_IN_NORMAL
388 && DECL_FUNCTION_CODE (e
->callee
->decl
) == BUILT_IN_APPLY_ARGS
)
390 node
->local
.can_change_signature
= !e
;
392 estimate_function_body_sizes (node
);
394 /* Inlining characteristics are maintained by the cgraph_mark_inline. */
395 info
->time
= info
->self_time
;
396 info
->size
= info
->self_size
;
397 info
->estimated_growth
= INT_MIN
;
398 info
->stack_frame_offset
= 0;
399 info
->estimated_stack_size
= info
->estimated_self_stack_size
;
403 /* Compute parameters of functions used by inliner using
404 current_function_decl. */
407 compute_inline_parameters_for_current (void)
409 compute_inline_parameters (cgraph_get_node (current_function_decl
));
413 struct gimple_opt_pass pass_inline_parameters
=
417 "inline_param", /* name */
419 compute_inline_parameters_for_current
,/* execute */
422 0, /* static_pass_number */
423 TV_INLINE_HEURISTICS
, /* tv_id */
424 0, /* properties_required */
425 0, /* properties_provided */
426 0, /* properties_destroyed */
427 0, /* todo_flags_start */
428 0 /* todo_flags_finish */
433 /* Estimate the time cost for the caller when inlining EDGE. */
436 estimate_edge_time (struct cgraph_edge
*edge
)
439 struct inline_summary
*info
= inline_summary (edge
->callee
);
441 call_stmt_time
= edge
->call_stmt_time
;
442 gcc_checking_assert (call_stmt_time
);
443 return (((gcov_type
)info
->time
444 - info
->time_inlining_benefit
445 - call_stmt_time
) * edge
->frequency
446 + CGRAPH_FREQ_BASE
/ 2) / CGRAPH_FREQ_BASE
;
450 /* Estimate self time of the function NODE after inlining EDGE. */
453 estimate_time_after_inlining (struct cgraph_node
*node
,
454 struct cgraph_edge
*edge
)
456 gcov_type time
= inline_summary (node
)->time
+ estimate_edge_time (edge
);
465 /* Estimate the size of NODE after inlining EDGE which should be an
466 edge to either NODE or a call inlined into NODE. */
469 estimate_size_after_inlining (struct cgraph_node
*node
,
470 struct cgraph_edge
*edge
)
472 int size
= inline_summary (node
)->size
+ estimate_edge_growth (edge
);
473 gcc_assert (size
>= 0);
478 /* Estimate the growth caused by inlining NODE into all callees. */
481 estimate_growth (struct cgraph_node
*node
)
484 struct cgraph_edge
*e
;
485 bool self_recursive
= false;
486 struct inline_summary
*info
= inline_summary (node
);
488 if (info
->estimated_growth
!= INT_MIN
)
489 return info
->estimated_growth
;
491 for (e
= node
->callers
; e
; e
= e
->next_caller
)
493 gcc_checking_assert (e
->inline_failed
);
495 if (e
->caller
== node
496 || (e
->caller
->global
.inlined_to
497 && e
->caller
->global
.inlined_to
== node
))
498 self_recursive
= true;
499 growth
+= estimate_edge_growth (e
);
503 /* For self recursive functions the growth estimation really should be
504 infinity. We don't want to return very large values because the growth
505 plays various roles in badness computation fractions. Be sure to not
506 return zero or negative growths. */
508 growth
= growth
< info
->size
? info
->size
: growth
;
511 if (cgraph_will_be_removed_from_program_if_no_direct_calls (node
)
512 && !DECL_EXTERNAL (node
->decl
))
513 growth
-= info
->size
;
514 /* COMDAT functions are very often not shared across multiple units since they
515 come from various template instantiations. Take this into account. */
516 else if (DECL_COMDAT (node
->decl
)
517 && cgraph_can_remove_if_no_direct_calls_p (node
))
518 growth
-= (info
->size
519 * (100 - PARAM_VALUE (PARAM_COMDAT_SHARING_PROBABILITY
)) + 50) / 100;
522 info
->estimated_growth
= growth
;
527 /* This function performs intraprocedural analysis in NODE that is required to
528 inline indirect calls. */
531 inline_indirect_intraprocedural_analysis (struct cgraph_node
*node
)
533 ipa_analyze_node (node
);
534 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
536 ipa_print_node_params (dump_file
, node
);
537 ipa_print_node_jump_functions (dump_file
, node
);
542 /* Note function body size. */
545 inline_analyze_function (struct cgraph_node
*node
)
547 push_cfun (DECL_STRUCT_FUNCTION (node
->decl
));
548 current_function_decl
= node
->decl
;
550 compute_inline_parameters (node
);
551 /* FIXME: We should remove the optimize check after we ensure we never run
552 IPA passes when not optimizing. */
553 if (flag_indirect_inlining
&& optimize
)
554 inline_indirect_intraprocedural_analysis (node
);
556 current_function_decl
= NULL
;
561 /* Called when new function is inserted to callgraph late. */
564 add_new_function (struct cgraph_node
*node
, void *data ATTRIBUTE_UNUSED
)
566 inline_analyze_function (node
);
570 /* Note function body size. */
573 inline_generate_summary (void)
575 struct cgraph_node
*node
;
577 function_insertion_hook_holder
=
578 cgraph_add_function_insertion_hook (&add_new_function
, NULL
);
580 if (flag_indirect_inlining
)
581 ipa_register_cgraph_hooks ();
583 for (node
= cgraph_nodes
; node
; node
= node
->next
)
585 inline_analyze_function (node
);
589 /* Read inline summary. Jump functions are shared among ipa-cp
590 and inliner, so when ipa-cp is active, we don't need to write them
594 inline_read_summary (void)
596 struct lto_file_decl_data
**file_data_vec
= lto_get_file_decl_data ();
597 struct lto_file_decl_data
*file_data
;
600 inline_summary_alloc ();
602 while ((file_data
= file_data_vec
[j
++]))
605 const char *data
= lto_get_section_data (file_data
, LTO_section_inline_summary
, NULL
, &len
);
607 struct lto_input_block
*ib
608 = lto_create_simple_input_block (file_data
,
609 LTO_section_inline_summary
,
614 unsigned int f_count
= lto_input_uleb128 (ib
);
616 for (i
= 0; i
< f_count
; i
++)
619 struct cgraph_node
*node
;
620 struct inline_summary
*info
;
621 lto_cgraph_encoder_t encoder
;
624 index
= lto_input_uleb128 (ib
);
625 encoder
= file_data
->cgraph_node_encoder
;
626 node
= lto_cgraph_encoder_deref (encoder
, index
);
627 info
= inline_summary (node
);
629 info
->estimated_stack_size
630 = info
->estimated_self_stack_size
= lto_input_uleb128 (ib
);
631 info
->size
= info
->self_size
= lto_input_uleb128 (ib
);
632 info
->size_inlining_benefit
= lto_input_uleb128 (ib
);
633 info
->time
= info
->self_time
= lto_input_uleb128 (ib
);
634 info
->time_inlining_benefit
= lto_input_uleb128 (ib
);
635 info
->estimated_growth
= INT_MIN
;
637 bp
= lto_input_bitpack (ib
);
638 info
->inlinable
= bp_unpack_value (&bp
, 1);
639 info
->versionable
= bp_unpack_value (&bp
, 1);
642 lto_destroy_simple_input_block (file_data
,
643 LTO_section_inline_summary
,
647 /* Fatal error here. We do not want to support compiling ltrans units with
648 different version of compiler or different flags than the WPA unit, so
649 this should never happen. */
650 fatal_error ("ipa inline summary is missing in input file");
652 if (flag_indirect_inlining
)
654 ipa_register_cgraph_hooks ();
656 ipa_prop_read_jump_functions ();
658 function_insertion_hook_holder
=
659 cgraph_add_function_insertion_hook (&add_new_function
, NULL
);
663 /* Write inline summary for node in SET.
664 Jump functions are shared among ipa-cp and inliner, so when ipa-cp is
665 active, we don't need to write them twice. */
668 inline_write_summary (cgraph_node_set set
,
669 varpool_node_set vset ATTRIBUTE_UNUSED
)
671 struct cgraph_node
*node
;
672 struct lto_simple_output_block
*ob
673 = lto_create_simple_output_block (LTO_section_inline_summary
);
674 lto_cgraph_encoder_t encoder
= ob
->decl_state
->cgraph_node_encoder
;
675 unsigned int count
= 0;
678 for (i
= 0; i
< lto_cgraph_encoder_size (encoder
); i
++)
679 if (lto_cgraph_encoder_deref (encoder
, i
)->analyzed
)
681 lto_output_uleb128_stream (ob
->main_stream
, count
);
683 for (i
= 0; i
< lto_cgraph_encoder_size (encoder
); i
++)
685 node
= lto_cgraph_encoder_deref (encoder
, i
);
688 struct inline_summary
*info
= inline_summary (node
);
691 lto_output_uleb128_stream (ob
->main_stream
,
692 lto_cgraph_encoder_encode (encoder
, node
));
693 lto_output_sleb128_stream (ob
->main_stream
,
694 info
->estimated_self_stack_size
);
695 lto_output_sleb128_stream (ob
->main_stream
,
697 lto_output_sleb128_stream (ob
->main_stream
,
698 info
->size_inlining_benefit
);
699 lto_output_sleb128_stream (ob
->main_stream
,
701 lto_output_sleb128_stream (ob
->main_stream
,
702 info
->time_inlining_benefit
);
703 bp
= bitpack_create (ob
->main_stream
);
704 bp_pack_value (&bp
, info
->inlinable
, 1);
705 bp_pack_value (&bp
, info
->versionable
, 1);
706 lto_output_bitpack (&bp
);
709 lto_destroy_simple_output_block (ob
);
711 if (flag_indirect_inlining
&& !flag_ipa_cp
)
712 ipa_prop_write_jump_functions (set
);
716 /* Release inline summary. */
719 inline_free_summary (void)
721 if (function_insertion_hook_holder
)
722 cgraph_remove_function_insertion_hook (function_insertion_hook_holder
);
723 function_insertion_hook_holder
= NULL
;
724 if (node_removal_hook_holder
)
725 cgraph_remove_node_removal_hook (node_removal_hook_holder
);
726 node_removal_hook_holder
= NULL
;
727 if (node_duplication_hook_holder
)
728 cgraph_remove_node_duplication_hook (node_duplication_hook_holder
);
729 node_duplication_hook_holder
= NULL
;
730 VEC_free (inline_summary_t
, heap
, inline_summary_vec
);