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 provide accestor to the inline_summary datastructure and
40 basic logic updating the parameters when inlining is performed.
42 The summaries are context sensitive. Context means
43 1) partial assignment of known constant values of operands
44 2) whether function is inlined into the call or not.
45 It is easy to add more variants. To represent function size and time
46 that depends on context (i.e. it is known to be optimized away when
47 context is known either by inlining or from IP-CP and clonning),
48 we use predicates. Predicates are logical formulas in
49 conjunctive-disjunctive form consisting of clauses. Clauses are bitmaps
50 specifying what conditions must be true. Conditions are simple test
51 of the form described above.
53 In order to make predicate (possibly) true, all of its clauses must
54 be (possibly) true. To make clause (possibly) true, one of conditions
55 it mentions must be (possibly) true. There are fixed bounds on
56 number of clauses and conditions and all the manipulation functions
57 are conservative in positive direction. I.e. we may lose precision
58 by thinking that predicate may be true even when it is not.
60 estimate_edge_size and estimate_edge_growth can be used to query
61 function size/time in the given context. inline_merge_summary merges
62 properties of caller and callee after inlining.
64 Finally pass_inline_parameters is exported. This is used to drive
65 computation of function parameters used by the early inliner. IPA
66 inlined performs analysis via its analyze_function method. */
70 #include "coretypes.h"
73 #include "tree-inline.h"
74 #include "langhooks.h"
77 #include "diagnostic.h"
78 #include "gimple-pretty-print.h"
81 #include "tree-pass.h"
84 #include "tree-flow.h"
86 #include "lto-streamer.h"
87 #include "ipa-inline.h"
89 /* Estimate runtime of function can easilly run into huge numbers with many
90 nested loops. Be sure we can compute time * INLINE_SIZE_SCALE in integer.
91 For anything larger we use gcov_type. */
92 #define MAX_TIME 1000000
94 /* Number of bits in integer, but we really want to be stable across different
96 #define NUM_CONDITIONS 32
98 enum predicate_conditions
100 predicate_false_condition
= 0,
101 predicate_not_inlined_condition
= 1,
102 predicate_first_dynamic_condition
= 2
105 /* Special condition code we use to represent test that operand is compile time
107 #define IS_NOT_CONSTANT ERROR_MARK
109 /* Holders of ipa cgraph hooks: */
110 static struct cgraph_node_hook_list
*function_insertion_hook_holder
;
111 static struct cgraph_node_hook_list
*node_removal_hook_holder
;
112 static struct cgraph_2node_hook_list
*node_duplication_hook_holder
;
113 static struct cgraph_2edge_hook_list
*edge_duplication_hook_holder
;
114 static struct cgraph_edge_hook_list
*edge_removal_hook_holder
;
115 static void inline_node_removal_hook (struct cgraph_node
*, void *);
116 static void inline_node_duplication_hook (struct cgraph_node
*,
117 struct cgraph_node
*, void *);
118 static void inline_edge_removal_hook (struct cgraph_edge
*, void *);
119 static void inline_edge_duplication_hook (struct cgraph_edge
*,
120 struct cgraph_edge
*,
123 /* VECtor holding inline summaries.
124 In GGC memory because conditions might point to constant trees. */
125 VEC(inline_summary_t
,gc
) *inline_summary_vec
;
126 VEC(inline_edge_summary_t
,heap
) *inline_edge_summary_vec
;
128 /* Cached node/edge growths. */
129 VEC(int,heap
) *node_growth_cache
;
130 VEC(edge_growth_cache_entry
,heap
) *edge_growth_cache
;
133 /* Return true predicate (tautology).
134 We represent it by empty list of clauses. */
136 static inline struct predicate
137 true_predicate (void)
145 /* Return predicate testing single condition number COND. */
147 static inline struct predicate
148 single_cond_predicate (int cond
)
151 p
.clause
[0]=1 << cond
;
157 /* Return false predicate. First clause require false condition. */
159 static inline struct predicate
160 false_predicate (void)
162 return single_cond_predicate (predicate_false_condition
);
166 /* Return predicate that is set true when function is not inlined. */
167 static inline struct predicate
168 not_inlined_predicate (void)
170 return single_cond_predicate (predicate_not_inlined_condition
);
174 /* Add condition to condition list CONDS. */
176 static struct predicate
177 add_condition (struct inline_summary
*summary
, int operand_num
,
178 enum tree_code code
, tree val
)
182 struct condition new_cond
;
184 for (i
= 0; VEC_iterate (condition
, summary
->conds
, i
, c
); i
++)
186 if (c
->operand_num
== operand_num
189 return single_cond_predicate (i
+ predicate_first_dynamic_condition
);
191 /* Too many conditions. Give up and return constant true. */
192 if (i
== NUM_CONDITIONS
- predicate_first_dynamic_condition
)
193 return true_predicate ();
195 new_cond
.operand_num
= operand_num
;
196 new_cond
.code
= code
;
198 VEC_safe_push (condition
, gc
, summary
->conds
, &new_cond
);
199 return single_cond_predicate (i
+ predicate_first_dynamic_condition
);
203 /* Add clause CLAUSE into the predicate. */
206 add_clause (struct predicate
*p
, clause_t clause
)
209 int insert_here
= -1;
214 /* Flase clause makes the whole predicate false. Kill the other variants. */
215 if (clause
& (1 << predicate_false_condition
))
217 p
->clause
[0] = (1 << predicate_false_condition
);
220 for (i
= 0; i
< MAX_CLAUSES
- 1; i
++)
222 if (p
->clause
[i
] == clause
)
226 if (p
->clause
[i
] < clause
&& !insert_here
)
229 /* We run out of variants. Be conservative in positive direciton. */
230 if (i
== MAX_CLAUSES
)
232 /* Keep clauses ordered by index, so equivalence testing is easy. */
233 p
->clause
[i
+ 1] = 0;
234 if (insert_here
>= 0)
235 for (;i
> insert_here
; i
--)
236 p
->clause
[i
] = p
->clause
[i
- 1];
239 p
->clause
[insert_here
] = clause
;
245 static struct predicate
246 and_predicates (struct predicate
*p
, struct predicate
*p2
)
248 struct predicate out
= *p
;
250 for (i
= 0; p2
->clause
[i
]; i
++)
252 gcc_checking_assert (i
< MAX_CLAUSES
);
253 add_clause (&out
, p2
->clause
[i
]);
261 static struct predicate
262 or_predicates (struct predicate
*p
, struct predicate
*p2
)
264 struct predicate out
= true_predicate ();
266 /* If one of conditions is false, return the other. */
267 if (p2
->clause
[0] == 1 << predicate_false_condition
)
269 gcc_checking_assert (!p2
->clause
[1]);
272 if (p
->clause
[0] == 1 << predicate_false_condition
)
274 gcc_checking_assert (!p
->clause
[1]);
277 for (i
= 0; p
->clause
[i
]; i
++)
278 for (j
= 0; p2
->clause
[j
]; j
++)
280 gcc_checking_assert (i
< MAX_CLAUSES
&& j
< MAX_CLAUSES
);
281 add_clause (&out
, p
->clause
[i
] | p2
->clause
[j
]);
287 /* Return true if predicates are obviously equal. */
290 predicates_equal_p (struct predicate
*p
, struct predicate
*p2
)
293 for (i
= 0; p
->clause
[i
]; i
++)
295 gcc_checking_assert (i
< MAX_CLAUSES
);
296 if (p
->clause
[i
] != p2
->clause
[i
])
299 return !p2
->clause
[i
];
303 /* Having partial truth assignment in POSSIBLE_TRUTHS, return false if predicate P
307 evaulate_predicate (struct predicate
*p
, clause_t possible_truths
)
311 /* True remains true. */
315 /* See if we can find clause we can disprove. */
316 for (i
= 0; p
->clause
[i
]; i
++)
318 gcc_checking_assert (i
< MAX_CLAUSES
);
319 if (!(p
->clause
[i
] & possible_truths
))
326 /* Dump conditional COND. */
329 dump_condition (FILE *f
, conditions conditions
, int cond
)
332 if (cond
== predicate_false_condition
)
333 fprintf (f
, "false");
334 else if (cond
== predicate_not_inlined_condition
)
335 fprintf (f
, "not inlined");
338 c
= VEC_index (condition
, conditions
, cond
- predicate_first_dynamic_condition
);
339 fprintf (f
, "op%i", c
->operand_num
);
340 if (c
->code
== IS_NOT_CONSTANT
)
342 fprintf (f
, " not constant");
345 fprintf (f
, " %s ", op_symbol_code (c
->code
));
346 print_generic_expr (f
, c
->val
, 1);
351 /* Dump clause CLAUSE. */
354 dump_clause (FILE *f
, conditions conds
, clause_t clause
)
361 for (i
= 0; i
< NUM_CONDITIONS
; i
++)
362 if (clause
& (1 << i
))
367 dump_condition (f
, conds
, i
);
373 /* Dump predicate PREDICATE. */
376 dump_predicate (FILE *f
, conditions conds
, struct predicate
*pred
)
379 if (!pred
->clause
[0])
380 dump_clause (f
, conds
, 0);
382 for (i
= 0; pred
->clause
[i
]; i
++)
386 dump_clause (f
, conds
, pred
->clause
[i
]);
392 /* Record SIZE and TIME under condition PRED into the inline summary. */
395 account_size_time (struct inline_summary
*summary
, int size
, int time
, struct predicate
*pred
)
401 if (pred
->clause
[0] == (1 << predicate_false_condition
))
404 /* We need to create initial empty unconitional clause, but otherwie
405 we don't need to account empty times and sizes. */
406 if (!size
&& !time
&& summary
->conds
)
409 /* Watch overflow that might result from insane profiles. */
410 if (time
> MAX_TIME
* INLINE_TIME_SCALE
)
411 time
= MAX_TIME
* INLINE_TIME_SCALE
;
412 gcc_assert (time
>= 0);
414 for (i
= 0; VEC_iterate (size_time_entry
, summary
->entry
, i
, e
); i
++)
415 if (predicates_equal_p (&e
->predicate
, pred
))
424 e
= VEC_index (size_time_entry
, summary
->entry
, 0);
425 gcc_assert (!e
->predicate
.clause
[0]);
427 if (dump_file
&& (dump_flags
& TDF_DETAILS
) && (time
|| size
))
429 fprintf (dump_file
, "\t\tAccounting size:%3.2f, time:%3.2f on %spredicate:",
430 ((double)size
) / INLINE_SIZE_SCALE
, ((double)time
) / INLINE_TIME_SCALE
,
431 found
? "" : "new ");
432 dump_predicate (dump_file
, summary
->conds
, pred
);
436 struct size_time_entry new_entry
;
437 new_entry
.size
= size
;
438 new_entry
.time
= time
;
439 new_entry
.predicate
= *pred
;
440 VEC_safe_push (size_time_entry
, gc
, summary
->entry
, &new_entry
);
446 if (e
->time
> MAX_TIME
* INLINE_TIME_SCALE
)
447 e
->time
= MAX_TIME
* INLINE_TIME_SCALE
;
452 /* Work out what conditions might be true at invocation of E. */
455 evaulate_conditions_for_edge (struct cgraph_edge
*e
, bool inline_p
)
457 clause_t clause
= inline_p
? 0 : 1 << predicate_not_inlined_condition
;
458 struct inline_summary
*info
= inline_summary (e
->callee
);
461 if (ipa_node_params_vector
&& info
->conds
462 /* FIXME: it seems that we forget to get argument count in some cases,
463 probaby for previously indirect edges or so. */
464 && ipa_get_cs_argument_count (IPA_EDGE_REF (e
)))
466 struct ipa_node_params
*parms_info
;
467 struct ipa_edge_args
*args
= IPA_EDGE_REF (e
);
468 int i
, count
= ipa_get_cs_argument_count (args
);
469 struct ipcp_lattice lat
;
471 VEC (tree
, heap
) *known_vals
= NULL
;
473 if (e
->caller
->global
.inlined_to
)
474 parms_info
= IPA_NODE_REF (e
->caller
->global
.inlined_to
);
476 parms_info
= IPA_NODE_REF (e
->caller
);
478 VEC_safe_grow_cleared (tree
, heap
, known_vals
, count
);
479 for (i
= 0; i
< count
; i
++)
481 ipa_lattice_from_jfunc (parms_info
, &lat
, ipa_get_ith_jump_func (args
, i
));
482 if (lat
.type
== IPA_CONST_VALUE
)
483 VEC_replace (tree
, known_vals
, i
, lat
.constant
);
485 for (i
= 0; VEC_iterate (condition
, info
->conds
, i
, c
); i
++)
487 tree val
= VEC_index (tree
, known_vals
, c
->operand_num
);
492 clause
|= 1 << (i
+ predicate_first_dynamic_condition
);
495 if (c
->code
== IS_NOT_CONSTANT
)
497 res
= fold_binary_to_constant (c
->code
, boolean_type_node
, val
, c
->val
);
499 && integer_zerop (res
))
501 clause
|= 1 << (i
+ predicate_first_dynamic_condition
);
503 VEC_free (tree
, heap
, known_vals
);
506 for (i
= 0; i
< (int)VEC_length (condition
, info
->conds
); i
++)
507 clause
|= 1 << (i
+ predicate_first_dynamic_condition
);
513 /* Allocate the inline summary vector or resize it to cover all cgraph nodes. */
516 inline_summary_alloc (void)
518 if (!node_removal_hook_holder
)
519 node_removal_hook_holder
=
520 cgraph_add_node_removal_hook (&inline_node_removal_hook
, NULL
);
521 if (!edge_removal_hook_holder
)
522 edge_removal_hook_holder
=
523 cgraph_add_edge_removal_hook (&inline_edge_removal_hook
, NULL
);
524 if (!node_duplication_hook_holder
)
525 node_duplication_hook_holder
=
526 cgraph_add_node_duplication_hook (&inline_node_duplication_hook
, NULL
);
527 if (!edge_duplication_hook_holder
)
528 edge_duplication_hook_holder
=
529 cgraph_add_edge_duplication_hook (&inline_edge_duplication_hook
, NULL
);
531 if (VEC_length (inline_summary_t
, inline_summary_vec
)
532 <= (unsigned) cgraph_max_uid
)
533 VEC_safe_grow_cleared (inline_summary_t
, gc
,
534 inline_summary_vec
, cgraph_max_uid
+ 1);
535 if (VEC_length (inline_edge_summary_t
, inline_edge_summary_vec
)
536 <= (unsigned) cgraph_edge_max_uid
)
537 VEC_safe_grow_cleared (inline_edge_summary_t
, heap
,
538 inline_edge_summary_vec
, cgraph_edge_max_uid
+ 1);
541 /* Hook that is called by cgraph.c when a node is removed. */
544 inline_node_removal_hook (struct cgraph_node
*node
, void *data ATTRIBUTE_UNUSED
)
546 struct inline_summary
*info
;
547 if (VEC_length (inline_summary_t
, inline_summary_vec
)
548 <= (unsigned)node
->uid
)
550 info
= inline_summary (node
);
551 reset_node_growth_cache (node
);
552 VEC_free (condition
, gc
, info
->conds
);
553 VEC_free (size_time_entry
, gc
, info
->entry
);
556 memset (info
, 0, sizeof (inline_summary_t
));
560 /* Hook that is called by cgraph.c when a node is duplicated. */
563 inline_node_duplication_hook (struct cgraph_node
*src
, struct cgraph_node
*dst
,
564 ATTRIBUTE_UNUSED
void *data
)
566 struct inline_summary
*info
;
567 inline_summary_alloc ();
568 info
= inline_summary (dst
);
569 memcpy (info
, inline_summary (src
),
570 sizeof (struct inline_summary
));
571 info
->conds
= VEC_copy (condition
, gc
, info
->conds
);
572 info
->entry
= VEC_copy (size_time_entry
, gc
, info
->entry
);
576 /* Hook that is called by cgraph.c when a node is duplicated. */
579 inline_edge_duplication_hook (struct cgraph_edge
*src
, struct cgraph_edge
*dst
,
580 ATTRIBUTE_UNUSED
void *data
)
582 struct inline_edge_summary
*info
;
583 inline_summary_alloc ();
584 info
= inline_edge_summary (dst
);
585 memcpy (info
, inline_edge_summary (src
),
586 sizeof (struct inline_edge_summary
));
590 /* Keep edge cache consistent across edge removal. */
593 inline_edge_removal_hook (struct cgraph_edge
*edge
, void *data ATTRIBUTE_UNUSED
)
595 if (edge_growth_cache
)
596 reset_edge_growth_cache (edge
);
597 if (edge
->uid
< (int)VEC_length (inline_edge_summary_t
, inline_edge_summary_vec
))
598 memset (inline_edge_summary (edge
), 0, sizeof (struct inline_edge_summary
));
602 /* Initialize growth caches. */
605 initialize_growth_caches (void)
607 if (cgraph_edge_max_uid
)
608 VEC_safe_grow_cleared (edge_growth_cache_entry
, heap
, edge_growth_cache
,
609 cgraph_edge_max_uid
);
611 VEC_safe_grow_cleared (int, heap
, node_growth_cache
, cgraph_max_uid
);
615 /* Free growth caches. */
618 free_growth_caches (void)
620 VEC_free (edge_growth_cache_entry
, heap
, edge_growth_cache
);
621 edge_growth_cache
= 0;
622 VEC_free (int, heap
, node_growth_cache
);
623 node_growth_cache
= 0;
627 /* Dump edge summaries associated to NODE and recursively to all clones.
631 dump_inline_edge_summary (FILE * f
, int indent
, struct cgraph_node
*node
)
633 struct cgraph_edge
*edge
;
634 for (edge
= node
->callees
; edge
; edge
= edge
->next_callee
)
636 struct inline_edge_summary
*es
= inline_edge_summary (edge
);
637 fprintf (f
, "%*s%s/%i %s\n%*s loop depth:%2i freq:%4i size:%2i time: %2i\n",
638 indent
, "", cgraph_node_name (edge
->callee
),
640 edge
->inline_failed
? "inlined"
641 : cgraph_inline_failed_string (edge
->inline_failed
),
647 if (!edge
->inline_failed
)
648 dump_inline_edge_summary (f
, indent
+2, edge
->callee
);
650 for (edge
= node
->indirect_calls
; edge
; edge
= edge
->next_callee
)
652 struct inline_edge_summary
*es
= inline_edge_summary (edge
);
653 fprintf (f
, "%*sindirect call loop depth:%2i freq:%4i size:%2i time: %2i\n",
664 dump_inline_summary (FILE * f
, struct cgraph_node
*node
)
668 struct inline_summary
*s
= inline_summary (node
);
671 fprintf (f
, "Inline summary for %s/%i", cgraph_node_name (node
),
673 if (DECL_DISREGARD_INLINE_LIMITS (node
->decl
))
674 fprintf (f
, " always_inline");
676 fprintf (f
, " inlinable");
678 fprintf (f
, " versionable");
679 fprintf (f
, "\n self time: %i\n",
681 fprintf (f
, " global time: %i\n", s
->time
);
682 fprintf (f
, " self size: %i\n",
684 fprintf (f
, " global size: %i\n", s
->size
);
685 fprintf (f
, " self stack: %i\n",
686 (int) s
->estimated_self_stack_size
);
687 fprintf (f
, " global stack: %i\n",
688 (int) s
->estimated_stack_size
);
690 VEC_iterate (size_time_entry
, s
->entry
, i
, e
);
693 fprintf (f
, " size:%f, time:%f, predicate:",
694 (double) e
->size
/ INLINE_SIZE_SCALE
,
695 (double) e
->time
/ INLINE_TIME_SCALE
);
696 dump_predicate (f
, s
->conds
, &e
->predicate
);
698 fprintf (f
, " calls:\n");
699 dump_inline_edge_summary (f
, 4, node
);
705 debug_inline_summary (struct cgraph_node
*node
)
707 dump_inline_summary (stderr
, node
);
711 dump_inline_summaries (FILE *f
)
713 struct cgraph_node
*node
;
715 for (node
= cgraph_nodes
; node
; node
= node
->next
)
716 if (node
->analyzed
&& !node
->global
.inlined_to
)
717 dump_inline_summary (f
, node
);
720 /* Give initial reasons why inlining would fail on EDGE. This gets either
721 nullified or usually overwritten by more precise reasons later. */
724 initialize_inline_failed (struct cgraph_edge
*e
)
726 struct cgraph_node
*callee
= e
->callee
;
728 if (e
->indirect_unknown_callee
)
729 e
->inline_failed
= CIF_INDIRECT_UNKNOWN_CALL
;
730 else if (!callee
->analyzed
)
731 e
->inline_failed
= CIF_BODY_NOT_AVAILABLE
;
732 else if (callee
->local
.redefined_extern_inline
)
733 e
->inline_failed
= CIF_REDEFINED_EXTERN_INLINE
;
734 else if (e
->call_stmt
&& gimple_call_cannot_inline_p (e
->call_stmt
))
735 e
->inline_failed
= CIF_MISMATCHED_ARGUMENTS
;
737 e
->inline_failed
= CIF_FUNCTION_NOT_CONSIDERED
;
740 /* See if statement might disappear after inlining.
741 0 - means not eliminated
742 1 - half of statements goes away
743 2 - for sure it is eliminated.
744 We are not terribly sophisticated, basically looking for simple abstraction
748 eliminated_by_inlining_prob (gimple stmt
)
750 enum gimple_code code
= gimple_code (stmt
);
756 if (gimple_num_ops (stmt
) != 2)
759 /* Casts of parameters, loads from parameters passed by reference
760 and stores to return value or parameters are often free after
761 inlining dua to SRA and further combining.
762 Assume that half of statements goes away. */
763 if (gimple_assign_rhs_code (stmt
) == CONVERT_EXPR
764 || gimple_assign_rhs_code (stmt
) == NOP_EXPR
765 || gimple_assign_rhs_code (stmt
) == VIEW_CONVERT_EXPR
766 || gimple_assign_rhs_class (stmt
) == GIMPLE_SINGLE_RHS
)
768 tree rhs
= gimple_assign_rhs1 (stmt
);
769 tree lhs
= gimple_assign_lhs (stmt
);
770 tree inner_rhs
= rhs
;
771 tree inner_lhs
= lhs
;
772 bool rhs_free
= false;
773 bool lhs_free
= false;
775 while (handled_component_p (inner_lhs
)
776 || TREE_CODE (inner_lhs
) == MEM_REF
)
777 inner_lhs
= TREE_OPERAND (inner_lhs
, 0);
778 while (handled_component_p (inner_rhs
)
779 || TREE_CODE (inner_rhs
) == ADDR_EXPR
780 || TREE_CODE (inner_rhs
) == MEM_REF
)
781 inner_rhs
= TREE_OPERAND (inner_rhs
, 0);
784 if (TREE_CODE (inner_rhs
) == PARM_DECL
785 || (TREE_CODE (inner_rhs
) == SSA_NAME
786 && SSA_NAME_IS_DEFAULT_DEF (inner_rhs
)
787 && TREE_CODE (SSA_NAME_VAR (inner_rhs
)) == PARM_DECL
))
789 if (rhs_free
&& is_gimple_reg (lhs
))
791 if (((TREE_CODE (inner_lhs
) == PARM_DECL
792 || (TREE_CODE (inner_lhs
) == SSA_NAME
793 && SSA_NAME_IS_DEFAULT_DEF (inner_lhs
)
794 && TREE_CODE (SSA_NAME_VAR (inner_lhs
)) == PARM_DECL
))
796 || TREE_CODE (inner_lhs
) == RESULT_DECL
797 || (TREE_CODE (inner_lhs
) == SSA_NAME
798 && TREE_CODE (SSA_NAME_VAR (inner_lhs
)) == RESULT_DECL
))
801 && (is_gimple_reg (rhs
) || is_gimple_min_invariant (rhs
)))
803 if (lhs_free
&& rhs_free
)
813 /* Return predicate that must be true when is E executable. */
815 static struct predicate
816 edge_execution_predicate (struct ipa_node_params
*info
,
817 struct inline_summary
*summary
,
820 struct predicate p
= true_predicate ();
826 if (e
->src
== ENTRY_BLOCK_PTR
)
829 last
= last_stmt (e
->src
);
830 /* TODO: handle switch. */
832 || gimple_code (last
) != GIMPLE_COND
)
834 if (!is_gimple_ip_invariant (gimple_cond_rhs (last
)))
836 op
= gimple_cond_lhs (last
);
837 /* TODO: handle conditionals like
840 and __bulitin_constant_p. */
841 if (TREE_CODE (op
) != SSA_NAME
842 || !SSA_NAME_IS_DEFAULT_DEF (op
))
844 index
= ipa_get_param_decl_index (info
, SSA_NAME_VAR (op
));
847 code
= gimple_cond_code (last
);
850 code
= invert_tree_comparison (code
,
851 HONOR_NANS (TYPE_MODE (TREE_TYPE (op
))));
853 return add_condition (summary
,
855 gimple_cond_code (last
),
856 gimple_cond_rhs (last
));
859 static struct predicate
860 will_be_nonconstant_predicate (struct ipa_node_params
*info
,
861 struct inline_summary
*summary
,
864 struct predicate p
= true_predicate ();
867 struct predicate op_non_const
;
869 /* What statments might be optimized away
870 when their arguments are constant
871 TODO: also trivial builtins, especially builtin_constant_p. */
872 if (gimple_code (stmt
) != GIMPLE_ASSIGN
873 && gimple_code (stmt
) != GIMPLE_COND
874 && gimple_code (stmt
) != GIMPLE_SWITCH
)
877 /* Stores and loads will stay anyway. */
878 if (gimple_vuse (stmt
))
881 /* See if we understand all operands before we start
882 adding conditionals. */
883 FOR_EACH_SSA_TREE_OPERAND (use
, stmt
, iter
, SSA_OP_USE
)
885 /* TODO: handle nested expressions and constant
887 if (TREE_CODE (use
) != SSA_NAME
888 || !SSA_NAME_IS_DEFAULT_DEF (use
)
889 || ipa_get_param_decl_index (info
, SSA_NAME_VAR (use
)) < 0)
892 op_non_const
= false_predicate ();
893 FOR_EACH_SSA_TREE_OPERAND (use
, stmt
, iter
, SSA_OP_USE
)
895 p
= add_condition (summary
,
896 ipa_get_param_decl_index (info
, SSA_NAME_VAR (use
)),
897 IS_NOT_CONSTANT
, NULL
);
898 op_non_const
= or_predicates (&p
, &op_non_const
);
904 /* Compute function body size parameters for NODE.
905 When EARLY is true, we compute only simple summaries without
906 non-trivial predicates to drive the early inliner. */
909 estimate_function_body_sizes (struct cgraph_node
*node
, bool early
)
912 /* Estimate static overhead for function prologue/epilogue and alignment. */
914 /* Benefits are scaled by probability of elimination that is in range
917 gimple_stmt_iterator bsi
;
918 struct function
*my_function
= DECL_STRUCT_FUNCTION (node
->decl
);
920 struct inline_summary
*info
= inline_summary (node
);
921 struct predicate bb_predicate
;
922 struct ipa_node_params
*parms_info
;
924 parms_info
= ipa_node_params_vector
&& !early
? IPA_NODE_REF (node
) : NULL
;
931 fprintf (dump_file
, "\nAnalyzing function body size: %s\n",
932 cgraph_node_name (node
));
934 /* When we run into maximal number of entries, we assign everything to the
935 constant truth case. Be sure to have it in list. */
936 bb_predicate
= true_predicate ();
937 account_size_time (info
, 0, 0, &bb_predicate
);
939 bb_predicate
= not_inlined_predicate ();
940 account_size_time (info
, 2 * INLINE_SIZE_SCALE
, 0, &bb_predicate
);
943 gcc_assert (my_function
&& my_function
->cfg
);
944 FOR_EACH_BB_FN (bb
, my_function
)
949 freq
= compute_call_stmt_bb_frequency (node
->decl
, bb
);
951 /* TODO: Obviously predicates can be propagated down across CFG. */
954 bb_predicate
= false_predicate ();
955 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
958 ep
= edge_execution_predicate (parms_info
, info
, e
);
959 bb_predicate
= or_predicates (&ep
, &bb_predicate
);
963 bb_predicate
= true_predicate ();
965 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
967 fprintf (dump_file
, "\n BB %i predicate:", bb
->index
);
968 dump_predicate (dump_file
, info
->conds
, &bb_predicate
);
971 for (bsi
= gsi_start_bb (bb
); !gsi_end_p (bsi
); gsi_next (&bsi
))
973 gimple stmt
= gsi_stmt (bsi
);
974 int this_size
= estimate_num_insns (stmt
, &eni_size_weights
);
975 int this_time
= estimate_num_insns (stmt
, &eni_time_weights
);
978 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
980 fprintf (dump_file
, " ");
981 print_gimple_stmt (dump_file
, stmt
, 0, 0);
982 fprintf (dump_file
, "\t\tfreq:%3.2f size:%3i time:%3i\n",
983 ((double)freq
)/CGRAPH_FREQ_BASE
, this_size
, this_time
);
986 if (is_gimple_call (stmt
))
988 struct cgraph_edge
*edge
= cgraph_edge (node
, stmt
);
989 struct inline_edge_summary
*es
= inline_edge_summary (edge
);
991 es
->call_stmt_size
= this_size
;
992 es
->call_stmt_time
= this_time
;
993 es
->loop_depth
= bb
->loop_depth
;
995 /* Do not inline calls where we cannot triviall work around
996 mismatches in argument or return types. */
998 && !gimple_check_call_matching_types (stmt
, edge
->callee
->decl
))
1000 edge
->call_stmt_cannot_inline_p
= true;
1001 gimple_call_set_cannot_inline (stmt
, true);
1004 gcc_assert (!gimple_call_cannot_inline_p (stmt
));
1007 if (this_time
|| this_size
)
1009 struct predicate will_be_nonconstant
;
1016 prob
= eliminated_by_inlining_prob (stmt
);
1017 if (prob
== 1 && dump_file
&& (dump_flags
& TDF_DETAILS
))
1018 fprintf (dump_file
, "\t\t50%% will be eliminated by inlining\n");
1019 if (prob
== 2 && dump_file
&& (dump_flags
& TDF_DETAILS
))
1020 fprintf (dump_file
, "\t\twill eliminated by inlining\n");
1025 = will_be_nonconstant_predicate (parms_info
, info
, stmt
);
1026 p
= and_predicates (&bb_predicate
, &will_be_nonconstant
);
1029 p
= true_predicate ();
1031 /* We account everything but the calls. Calls have their own
1032 size/time info attached to cgraph edges. This is neccesary
1033 in order to make the cost disappear after inlining. */
1034 if (!is_gimple_call (stmt
))
1038 struct predicate ip
= not_inlined_predicate ();
1039 ip
= and_predicates (&ip
, &p
);
1040 account_size_time (info
, this_size
* prob
,
1041 this_time
* prob
, &ip
);
1044 account_size_time (info
, this_size
* (2 - prob
),
1045 this_time
* (2 - prob
), &p
);
1048 gcc_assert (time
>= 0);
1049 gcc_assert (size
>= 0);
1053 time
= (time
+ CGRAPH_FREQ_BASE
/ 2) / CGRAPH_FREQ_BASE
;
1054 if (time
> MAX_TIME
)
1056 inline_summary (node
)->self_time
= time
;
1057 inline_summary (node
)->self_size
= size
;
1060 fprintf (dump_file
, "\n");
1061 dump_inline_summary (dump_file
, node
);
1066 /* Compute parameters of functions used by inliner.
1067 EARLY is true when we compute parameters for the early inliner */
1070 compute_inline_parameters (struct cgraph_node
*node
, bool early
)
1072 HOST_WIDE_INT self_stack_size
;
1073 struct cgraph_edge
*e
;
1074 struct inline_summary
*info
;
1076 gcc_assert (!node
->global
.inlined_to
);
1078 inline_summary_alloc ();
1080 info
= inline_summary (node
);
1082 /* Estimate the stack size for the function if we're optimizing. */
1083 self_stack_size
= optimize
? estimated_stack_frame_size (node
) : 0;
1084 info
->estimated_self_stack_size
= self_stack_size
;
1085 info
->estimated_stack_size
= self_stack_size
;
1086 info
->stack_frame_offset
= 0;
1088 /* Can this function be inlined at all? */
1089 info
->inlinable
= tree_inlinable_function_p (node
->decl
);
1091 /* Inlinable functions always can change signature. */
1092 if (info
->inlinable
)
1093 node
->local
.can_change_signature
= true;
1096 /* Functions calling builtin_apply can not change signature. */
1097 for (e
= node
->callees
; e
; e
= e
->next_callee
)
1098 if (DECL_BUILT_IN (e
->callee
->decl
)
1099 && DECL_BUILT_IN_CLASS (e
->callee
->decl
) == BUILT_IN_NORMAL
1100 && DECL_FUNCTION_CODE (e
->callee
->decl
) == BUILT_IN_APPLY_ARGS
)
1102 node
->local
.can_change_signature
= !e
;
1104 estimate_function_body_sizes (node
, early
);
1106 /* Inlining characteristics are maintained by the cgraph_mark_inline. */
1107 info
->time
= info
->self_time
;
1108 info
->size
= info
->self_size
;
1109 info
->stack_frame_offset
= 0;
1110 info
->estimated_stack_size
= info
->estimated_self_stack_size
;
1114 /* Compute parameters of functions used by inliner using
1115 current_function_decl. */
1118 compute_inline_parameters_for_current (void)
1120 compute_inline_parameters (cgraph_get_node (current_function_decl
), true);
1124 struct gimple_opt_pass pass_inline_parameters
=
1128 "inline_param", /* name */
1130 compute_inline_parameters_for_current
,/* execute */
1133 0, /* static_pass_number */
1134 TV_INLINE_HEURISTICS
, /* tv_id */
1135 0, /* properties_required */
1136 0, /* properties_provided */
1137 0, /* properties_destroyed */
1138 0, /* todo_flags_start */
1139 0 /* todo_flags_finish */
1144 /* Increase SIZE and TIME for size and time needed to handle edge E. */
1147 estimate_edge_size_and_time (struct cgraph_edge
*e
, int *size
, int *time
)
1149 struct inline_edge_summary
*es
= inline_edge_summary (e
);
1150 *size
+= es
->call_stmt_size
* INLINE_SIZE_SCALE
;
1151 *time
+= (es
->call_stmt_time
1152 * e
->frequency
* (INLINE_TIME_SCALE
/ CGRAPH_FREQ_BASE
));
1153 if (*time
> MAX_TIME
* INLINE_TIME_SCALE
)
1154 *time
= MAX_TIME
* INLINE_TIME_SCALE
;
1158 /* Increase SIZE and TIME for size and time needed to handle all calls in NODE. */
1161 estimate_calls_size_and_time (struct cgraph_node
*node
, int *size
, int *time
)
1163 struct cgraph_edge
*e
;
1164 for (e
= node
->callees
; e
; e
= e
->next_callee
)
1165 if (e
->inline_failed
)
1166 estimate_edge_size_and_time (e
, size
, time
);
1168 estimate_calls_size_and_time (e
->callee
, size
, time
);
1169 /* TODO: look for devirtualizing oppurtunities. */
1170 for (e
= node
->indirect_calls
; e
; e
= e
->next_callee
)
1171 estimate_edge_size_and_time (e
, size
, time
);
1175 /* Estimate size and time needed to execute callee of EDGE assuming
1176 that parameters known to be constant at caller of EDGE are
1177 propagated. If INLINE_P is true, it is assumed that call will
1181 estimate_callee_size_and_time (struct cgraph_edge
*edge
, bool inline_p
,
1182 int *ret_size
, int *ret_time
)
1184 struct inline_summary
*info
= inline_summary (edge
->callee
);
1185 clause_t clause
= evaulate_conditions_for_edge (edge
, inline_p
);
1187 int size
= 0, time
= 0;
1191 && (dump_flags
& TDF_DETAILS
))
1194 fprintf (dump_file
, " Estimating callee body: %s/%i\n"
1195 " Known to be false: ",
1196 cgraph_node_name (edge
->callee
),
1199 for (i
= predicate_not_inlined_condition
;
1200 i
< (predicate_first_dynamic_condition
1201 + (int)VEC_length (condition
, info
->conds
)); i
++)
1202 if (!(clause
& (1 << i
)))
1205 fprintf (dump_file
, ", ");
1207 dump_condition (dump_file
, info
->conds
, i
);
1211 for (i
= 0; VEC_iterate (size_time_entry
, info
->entry
, i
, e
); i
++)
1212 if (evaulate_predicate (&e
->predicate
, clause
))
1213 time
+= e
->time
, size
+= e
->size
;
1215 if (time
> MAX_TIME
* INLINE_TIME_SCALE
)
1216 time
= MAX_TIME
* INLINE_TIME_SCALE
;
1218 estimate_calls_size_and_time (edge
->callee
, &size
, &time
);
1219 time
= (time
+ INLINE_TIME_SCALE
/ 2) / INLINE_TIME_SCALE
;
1220 size
= (size
+ INLINE_SIZE_SCALE
/ 2) / INLINE_SIZE_SCALE
;
1224 && (dump_flags
& TDF_DETAILS
))
1225 fprintf (dump_file
, "\n size:%i time:%i\n", size
, time
);
1234 /* Translate all conditions from callee representation into caller representaiton and
1235 symbolically evaulate predicate P into new predicate. */
1237 static struct predicate
1238 remap_predicate (struct inline_summary
*info
, struct inline_summary
*callee_info
,
1239 struct predicate
*p
,
1240 VEC (int, heap
) *operand_map
,
1241 clause_t possible_truths
)
1244 struct predicate out
= true_predicate ();
1246 /* True predicate is easy. */
1247 if (p
->clause
[0] == 0)
1249 for (i
= 0; p
->clause
[i
]; i
++)
1251 clause_t clause
= p
->clause
[i
];
1253 struct predicate clause_predicate
= false_predicate ();
1255 gcc_assert (i
< MAX_CLAUSES
);
1257 for (cond
= 0; cond
< NUM_CONDITIONS
; cond
++)
1258 /* Do we have condition we can't disprove? */
1259 if (clause
& possible_truths
& (1 << cond
))
1261 struct predicate cond_predicate
;
1262 /* Work out if the condition can translate to predicate in the
1263 inlined function. */
1264 if (cond
>= predicate_first_dynamic_condition
)
1266 struct condition
*c
;
1268 c
= VEC_index (condition
, callee_info
->conds
,
1269 cond
- predicate_first_dynamic_condition
);
1270 /* See if we can remap condition operand to caller's operand.
1271 Otherwise give up. */
1273 || VEC_index (int, operand_map
, c
->operand_num
) == -1)
1274 cond_predicate
= true_predicate ();
1276 cond_predicate
= add_condition (info
,
1277 VEC_index (int, operand_map
,
1281 /* Fixed conditions remains same, construct single
1282 condition predicate. */
1285 cond_predicate
.clause
[0] = 1 << cond
;
1286 cond_predicate
.clause
[1] = 0;
1288 clause_predicate
= or_predicates (&clause_predicate
, &cond_predicate
);
1290 out
= and_predicates (&out
, &clause_predicate
);
1296 /* Update summary information of inline clones after inlining.
1297 Compute peak stack usage. */
1300 inline_update_callee_summaries (struct cgraph_node
*node
,
1303 struct cgraph_edge
*e
;
1304 struct inline_summary
*callee_info
= inline_summary (node
);
1305 struct inline_summary
*caller_info
= inline_summary (node
->callers
->caller
);
1308 callee_info
->stack_frame_offset
1309 = caller_info
->stack_frame_offset
1310 + caller_info
->estimated_self_stack_size
;
1311 peak
= callee_info
->stack_frame_offset
1312 + callee_info
->estimated_self_stack_size
;
1313 if (inline_summary (node
->global
.inlined_to
)->estimated_stack_size
1315 inline_summary (node
->global
.inlined_to
)->estimated_stack_size
= peak
;
1316 cgraph_propagate_frequency (node
);
1317 for (e
= node
->callees
; e
; e
= e
->next_callee
)
1319 if (!e
->inline_failed
)
1320 inline_update_callee_summaries (e
->callee
, depth
);
1321 inline_edge_summary (e
)->loop_depth
+= depth
;
1323 for (e
= node
->indirect_calls
; e
; e
= e
->next_callee
)
1324 inline_edge_summary (e
)->loop_depth
+= depth
;
1328 /* We inlined EDGE. Update summary of the function we inlined into. */
1331 inline_merge_summary (struct cgraph_edge
*edge
)
1333 struct inline_summary
*callee_info
= inline_summary (edge
->callee
);
1334 struct cgraph_node
*to
= (edge
->caller
->global
.inlined_to
1335 ? edge
->caller
->global
.inlined_to
: edge
->caller
);
1336 struct inline_summary
*info
= inline_summary (to
);
1337 clause_t clause
= 0; /* not_inline is known to be false. */
1339 VEC (int, heap
) *operand_map
= NULL
;
1342 if (ipa_node_params_vector
&& callee_info
->conds
1343 /* FIXME: it seems that we forget to get argument count in some cases,
1344 probaby for previously indirect edges or so.
1345 Removing the test leads to ICE on tramp3d. */
1346 && ipa_get_cs_argument_count (IPA_EDGE_REF (edge
)))
1348 struct ipa_edge_args
*args
= IPA_EDGE_REF (edge
);
1349 int count
= ipa_get_cs_argument_count (args
);
1352 clause
= evaulate_conditions_for_edge (edge
, true);
1353 VEC_safe_grow_cleared (int, heap
, operand_map
, count
);
1354 for (i
= 0; i
< count
; i
++)
1356 struct ipa_jump_func
*jfunc
= ipa_get_ith_jump_func (args
, i
);
1358 /* TODO: handle non-NOPs when merging. */
1359 if (jfunc
->type
== IPA_JF_PASS_THROUGH
1360 && jfunc
->value
.pass_through
.operation
== NOP_EXPR
)
1361 map
= jfunc
->value
.pass_through
.formal_id
;
1362 VEC_replace (int, operand_map
, i
, map
);
1363 gcc_assert (map
< ipa_get_param_count (IPA_NODE_REF (to
)));
1366 for (i
= 0; VEC_iterate (size_time_entry
, callee_info
->entry
, i
, e
); i
++)
1368 struct predicate p
= remap_predicate (info
, callee_info
,
1369 &e
->predicate
, operand_map
, clause
);
1370 gcov_type add_time
= ((gcov_type
)e
->time
* edge
->frequency
1371 + CGRAPH_FREQ_BASE
/ 2) / CGRAPH_FREQ_BASE
;
1372 if (add_time
> MAX_TIME
)
1373 add_time
= MAX_TIME
;
1374 account_size_time (info
, e
->size
, add_time
, &p
);
1378 for (i
= 0; VEC_iterate (size_time_entry
, info
->entry
, i
, e
); i
++)
1379 info
->size
+= e
->size
, info
->time
+= e
->time
;
1380 estimate_calls_size_and_time (to
, &info
->size
, &info
->time
);
1382 inline_update_callee_summaries (edge
->callee
,
1383 inline_edge_summary (edge
)->loop_depth
);
1385 info
->time
= (info
->time
+ INLINE_TIME_SCALE
/ 2) / INLINE_TIME_SCALE
;
1386 info
->size
= (info
->size
+ INLINE_SIZE_SCALE
/ 2) / INLINE_SIZE_SCALE
;
1390 /* Estimate the time cost for the caller when inlining EDGE.
1391 Only to be called via estimate_edge_time, that handles the
1394 When caching, also update the cache entry. Compute both time and
1395 size, since we always need both metrics eventually. */
1398 do_estimate_edge_time (struct cgraph_edge
*edge
)
1403 struct inline_edge_summary
*es
= inline_edge_summary (edge
);
1405 gcc_checking_assert (edge
->inline_failed
);
1406 estimate_callee_size_and_time (edge
, true, &size
, &time
);
1408 ret
= (((gcov_type
)time
- es
->call_stmt_time
) * edge
->frequency
1409 + CGRAPH_FREQ_BASE
/ 2) / CGRAPH_FREQ_BASE
;
1413 /* When caching, update the cache entry. */
1414 if (edge_growth_cache
)
1417 if ((int)VEC_length (edge_growth_cache_entry
, edge_growth_cache
)
1419 VEC_safe_grow_cleared (edge_growth_cache_entry
, heap
, edge_growth_cache
,
1420 cgraph_edge_max_uid
);
1421 VEC_index (edge_growth_cache_entry
, edge_growth_cache
, edge
->uid
)->time
1424 ret_size
= size
- es
->call_stmt_size
;
1425 gcc_checking_assert (es
->call_stmt_size
);
1426 VEC_index (edge_growth_cache_entry
, edge_growth_cache
, edge
->uid
)->size
1427 = ret_size
+ (ret_size
>= 0);
1433 /* Estimate the growth of the caller when inlining EDGE.
1434 Only to be called via estimate_edge_size. */
1437 do_estimate_edge_growth (struct cgraph_edge
*edge
)
1441 /* When we do caching, use do_estimate_edge_time to populate the entry. */
1443 if (edge_growth_cache
)
1445 do_estimate_edge_time (edge
);
1446 size
= VEC_index (edge_growth_cache_entry
,
1449 gcc_checking_assert (size
);
1450 return size
- (size
> 0);
1453 /* Early inliner runs without caching, go ahead and do the dirty work. */
1454 gcc_checking_assert (edge
->inline_failed
);
1455 estimate_callee_size_and_time (edge
, true, &size
, NULL
);
1456 gcc_checking_assert (inline_edge_summary (edge
)->call_stmt_size
);
1457 return size
- inline_edge_summary (edge
)->call_stmt_size
;
1461 /* Estimate self time of the function NODE after inlining EDGE. */
1464 estimate_time_after_inlining (struct cgraph_node
*node
,
1465 struct cgraph_edge
*edge
)
1467 gcov_type time
= inline_summary (node
)->time
+ estimate_edge_time (edge
);
1470 if (time
> MAX_TIME
)
1476 /* Estimate the size of NODE after inlining EDGE which should be an
1477 edge to either NODE or a call inlined into NODE. */
1480 estimate_size_after_inlining (struct cgraph_node
*node
,
1481 struct cgraph_edge
*edge
)
1483 int size
= inline_summary (node
)->size
+ estimate_edge_growth (edge
);
1484 gcc_assert (size
>= 0);
1489 /* Estimate the growth caused by inlining NODE into all callees. */
1492 do_estimate_growth (struct cgraph_node
*node
)
1495 struct cgraph_edge
*e
;
1496 bool self_recursive
= false;
1497 struct inline_summary
*info
= inline_summary (node
);
1499 for (e
= node
->callers
; e
; e
= e
->next_caller
)
1501 gcc_checking_assert (e
->inline_failed
);
1503 if (e
->caller
== node
1504 || (e
->caller
->global
.inlined_to
1505 && e
->caller
->global
.inlined_to
== node
))
1506 self_recursive
= true;
1507 growth
+= estimate_edge_growth (e
);
1511 /* For self recursive functions the growth estimation really should be
1512 infinity. We don't want to return very large values because the growth
1513 plays various roles in badness computation fractions. Be sure to not
1514 return zero or negative growths. */
1516 growth
= growth
< info
->size
? info
->size
: growth
;
1519 if (cgraph_will_be_removed_from_program_if_no_direct_calls (node
)
1520 && !DECL_EXTERNAL (node
->decl
))
1521 growth
-= info
->size
;
1522 /* COMDAT functions are very often not shared across multiple units since they
1523 come from various template instantiations. Take this into account. */
1524 else if (DECL_COMDAT (node
->decl
)
1525 && cgraph_can_remove_if_no_direct_calls_p (node
))
1526 growth
-= (info
->size
1527 * (100 - PARAM_VALUE (PARAM_COMDAT_SHARING_PROBABILITY
)) + 50) / 100;
1530 if (node_growth_cache
)
1532 if ((int)VEC_length (int, node_growth_cache
) <= node
->uid
)
1533 VEC_safe_grow_cleared (int, heap
, node_growth_cache
, cgraph_max_uid
);
1534 VEC_replace (int, node_growth_cache
, node
->uid
, growth
+ (growth
>= 0));
1540 /* This function performs intraprocedural analysis in NODE that is required to
1541 inline indirect calls. */
1544 inline_indirect_intraprocedural_analysis (struct cgraph_node
*node
)
1546 ipa_analyze_node (node
);
1547 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1549 ipa_print_node_params (dump_file
, node
);
1550 ipa_print_node_jump_functions (dump_file
, node
);
1555 /* Note function body size. */
1558 inline_analyze_function (struct cgraph_node
*node
)
1560 push_cfun (DECL_STRUCT_FUNCTION (node
->decl
));
1561 current_function_decl
= node
->decl
;
1564 fprintf (dump_file
, "\nAnalyzing function: %s/%u\n",
1565 cgraph_node_name (node
), node
->uid
);
1566 /* FIXME: We should remove the optimize check after we ensure we never run
1567 IPA passes when not optimizing. */
1568 if (flag_indirect_inlining
&& optimize
)
1569 inline_indirect_intraprocedural_analysis (node
);
1570 compute_inline_parameters (node
, false);
1572 current_function_decl
= NULL
;
1577 /* Called when new function is inserted to callgraph late. */
1580 add_new_function (struct cgraph_node
*node
, void *data ATTRIBUTE_UNUSED
)
1582 inline_analyze_function (node
);
1586 /* Note function body size. */
1589 inline_generate_summary (void)
1591 struct cgraph_node
*node
;
1593 function_insertion_hook_holder
=
1594 cgraph_add_function_insertion_hook (&add_new_function
, NULL
);
1596 if (flag_indirect_inlining
)
1597 ipa_register_cgraph_hooks ();
1599 for (node
= cgraph_nodes
; node
; node
= node
->next
)
1601 inline_analyze_function (node
);
1605 /* Write inline summary for edge E to OB. */
1608 read_inline_edge_summary (struct lto_input_block
*ib
, struct cgraph_edge
*e
)
1610 struct inline_edge_summary
*es
= inline_edge_summary (e
);
1611 es
->call_stmt_size
= lto_input_uleb128 (ib
);
1612 es
->call_stmt_time
= lto_input_uleb128 (ib
);
1613 es
->loop_depth
= lto_input_uleb128 (ib
);
1617 /* Stream in inline summaries from the section. */
1620 inline_read_section (struct lto_file_decl_data
*file_data
, const char *data
,
1623 const struct lto_function_header
*header
=
1624 (const struct lto_function_header
*) data
;
1625 const int32_t cfg_offset
= sizeof (struct lto_function_header
);
1626 const int32_t main_offset
= cfg_offset
+ header
->cfg_size
;
1627 const int32_t string_offset
= main_offset
+ header
->main_size
;
1628 struct data_in
*data_in
;
1629 struct lto_input_block ib
;
1630 unsigned int i
, count2
, j
;
1631 unsigned int f_count
;
1633 LTO_INIT_INPUT_BLOCK (ib
, (const char *) data
+ main_offset
, 0,
1637 lto_data_in_create (file_data
, (const char *) data
+ string_offset
,
1638 header
->string_size
, NULL
);
1639 f_count
= lto_input_uleb128 (&ib
);
1640 for (i
= 0; i
< f_count
; i
++)
1643 struct cgraph_node
*node
;
1644 struct inline_summary
*info
;
1645 lto_cgraph_encoder_t encoder
;
1646 struct bitpack_d bp
;
1647 struct cgraph_edge
*e
;
1649 index
= lto_input_uleb128 (&ib
);
1650 encoder
= file_data
->cgraph_node_encoder
;
1651 node
= lto_cgraph_encoder_deref (encoder
, index
);
1652 info
= inline_summary (node
);
1654 info
->estimated_stack_size
1655 = info
->estimated_self_stack_size
= lto_input_uleb128 (&ib
);
1656 info
->size
= info
->self_size
= lto_input_uleb128 (&ib
);
1657 info
->time
= info
->self_time
= lto_input_uleb128 (&ib
);
1659 bp
= lto_input_bitpack (&ib
);
1660 info
->inlinable
= bp_unpack_value (&bp
, 1);
1661 info
->versionable
= bp_unpack_value (&bp
, 1);
1663 count2
= lto_input_uleb128 (&ib
);
1664 gcc_assert (!info
->conds
);
1665 for (j
= 0; j
< count2
; j
++)
1668 c
.operand_num
= lto_input_uleb128 (&ib
);
1669 c
.code
= (enum tree_code
) lto_input_uleb128 (&ib
);
1670 c
.val
= lto_input_tree (&ib
, data_in
);
1671 VEC_safe_push (condition
, gc
, info
->conds
, &c
);
1673 count2
= lto_input_uleb128 (&ib
);
1674 gcc_assert (!info
->entry
);
1675 for (j
= 0; j
< count2
; j
++)
1677 struct size_time_entry e
;
1681 e
.size
= lto_input_uleb128 (&ib
);
1682 e
.time
= lto_input_uleb128 (&ib
);
1685 clause
= e
.predicate
.clause
[k
++] = lto_input_uleb128 (&ib
);
1686 gcc_assert (k
< MAX_CLAUSES
);
1690 VEC_safe_push (size_time_entry
, gc
, info
->entry
, &e
);
1692 for (e
= node
->callees
; e
; e
= e
->next_callee
)
1693 read_inline_edge_summary (&ib
, e
);
1694 for (e
= node
->indirect_calls
; e
; e
= e
->next_callee
)
1695 read_inline_edge_summary (&ib
, e
);
1698 lto_free_section_data (file_data
, LTO_section_inline_summary
, NULL
, data
,
1700 lto_data_in_delete (data_in
);
1704 /* Read inline summary. Jump functions are shared among ipa-cp
1705 and inliner, so when ipa-cp is active, we don't need to write them
1709 inline_read_summary (void)
1711 struct lto_file_decl_data
**file_data_vec
= lto_get_file_decl_data ();
1712 struct lto_file_decl_data
*file_data
;
1715 inline_summary_alloc ();
1717 while ((file_data
= file_data_vec
[j
++]))
1720 const char *data
= lto_get_section_data (file_data
, LTO_section_inline_summary
, NULL
, &len
);
1722 inline_read_section (file_data
, data
, len
);
1724 /* Fatal error here. We do not want to support compiling ltrans units with
1725 different version of compiler or different flags than the WPA unit, so
1726 this should never happen. */
1727 fatal_error ("ipa inline summary is missing in input file");
1729 if (flag_indirect_inlining
)
1731 ipa_register_cgraph_hooks ();
1733 ipa_prop_read_jump_functions ();
1735 function_insertion_hook_holder
=
1736 cgraph_add_function_insertion_hook (&add_new_function
, NULL
);
1739 /* Write inline summary for edge E to OB. */
1742 write_inline_edge_summary (struct output_block
*ob
, struct cgraph_edge
*e
)
1744 struct inline_edge_summary
*es
= inline_edge_summary (e
);
1745 lto_output_uleb128_stream (ob
->main_stream
, es
->call_stmt_size
);
1746 lto_output_uleb128_stream (ob
->main_stream
, es
->call_stmt_time
);
1747 lto_output_uleb128_stream (ob
->main_stream
, es
->loop_depth
);
1751 /* Write inline summary for node in SET.
1752 Jump functions are shared among ipa-cp and inliner, so when ipa-cp is
1753 active, we don't need to write them twice. */
1756 inline_write_summary (cgraph_node_set set
,
1757 varpool_node_set vset ATTRIBUTE_UNUSED
)
1759 struct cgraph_node
*node
;
1760 struct output_block
*ob
= create_output_block (LTO_section_inline_summary
);
1761 lto_cgraph_encoder_t encoder
= ob
->decl_state
->cgraph_node_encoder
;
1762 unsigned int count
= 0;
1765 for (i
= 0; i
< lto_cgraph_encoder_size (encoder
); i
++)
1766 if (lto_cgraph_encoder_deref (encoder
, i
)->analyzed
)
1768 lto_output_uleb128_stream (ob
->main_stream
, count
);
1770 for (i
= 0; i
< lto_cgraph_encoder_size (encoder
); i
++)
1772 node
= lto_cgraph_encoder_deref (encoder
, i
);
1775 struct inline_summary
*info
= inline_summary (node
);
1776 struct bitpack_d bp
;
1777 struct cgraph_edge
*edge
;
1780 struct condition
*c
;
1783 lto_output_uleb128_stream (ob
->main_stream
,
1784 lto_cgraph_encoder_encode (encoder
, node
));
1785 lto_output_sleb128_stream (ob
->main_stream
,
1786 info
->estimated_self_stack_size
);
1787 lto_output_sleb128_stream (ob
->main_stream
,
1789 lto_output_sleb128_stream (ob
->main_stream
,
1791 bp
= bitpack_create (ob
->main_stream
);
1792 bp_pack_value (&bp
, info
->inlinable
, 1);
1793 bp_pack_value (&bp
, info
->versionable
, 1);
1794 lto_output_bitpack (&bp
);
1795 lto_output_uleb128_stream (ob
->main_stream
,
1796 VEC_length (condition
, info
->conds
));
1797 for (i
= 0; VEC_iterate (condition
, info
->conds
, i
, c
); i
++)
1799 lto_output_uleb128_stream (ob
->main_stream
,
1801 lto_output_uleb128_stream (ob
->main_stream
,
1803 lto_output_tree (ob
, c
->val
, true);
1805 lto_output_uleb128_stream (ob
->main_stream
,
1806 VEC_length (size_time_entry
, info
->entry
));
1808 VEC_iterate (size_time_entry
, info
->entry
, i
, e
);
1812 lto_output_uleb128_stream (ob
->main_stream
,
1814 lto_output_uleb128_stream (ob
->main_stream
,
1816 for (j
= 0; e
->predicate
.clause
[j
]; j
++)
1818 gcc_assert (j
< MAX_CLAUSES
);
1819 lto_output_uleb128_stream (ob
->main_stream
,
1820 e
->predicate
.clause
[j
]);
1822 lto_output_uleb128_stream (ob
->main_stream
, 0);
1824 for (edge
= node
->callees
; edge
; edge
= edge
->next_callee
)
1825 write_inline_edge_summary (ob
, edge
);
1826 for (edge
= node
->indirect_calls
; edge
; edge
= edge
->next_callee
)
1827 write_inline_edge_summary (ob
, edge
);
1830 lto_output_1_stream (ob
->main_stream
, 0);
1831 produce_asm (ob
, NULL
);
1832 destroy_output_block (ob
);
1834 if (flag_indirect_inlining
&& !flag_ipa_cp
)
1835 ipa_prop_write_jump_functions (set
);
1839 /* Release inline summary. */
1842 inline_free_summary (void)
1844 if (function_insertion_hook_holder
)
1845 cgraph_remove_function_insertion_hook (function_insertion_hook_holder
);
1846 function_insertion_hook_holder
= NULL
;
1847 if (node_removal_hook_holder
)
1848 cgraph_remove_node_removal_hook (node_removal_hook_holder
);
1849 if (edge_removal_hook_holder
)
1850 cgraph_remove_edge_removal_hook (edge_removal_hook_holder
);
1851 node_removal_hook_holder
= NULL
;
1852 if (node_duplication_hook_holder
)
1853 cgraph_remove_node_duplication_hook (node_duplication_hook_holder
);
1854 if (edge_duplication_hook_holder
)
1855 cgraph_remove_edge_duplication_hook (edge_duplication_hook_holder
);
1856 node_duplication_hook_holder
= NULL
;
1857 VEC_free (inline_summary_t
, gc
, inline_summary_vec
);
1858 inline_summary_vec
= NULL
;