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 "data-streamer.h"
88 #include "tree-streamer.h"
89 #include "ipa-inline.h"
90 #include "alloc-pool.h"
92 /* Estimate runtime of function can easilly run into huge numbers with many
93 nested loops. Be sure we can compute time * INLINE_SIZE_SCALE in integer.
94 For anything larger we use gcov_type. */
95 #define MAX_TIME 1000000
97 /* Number of bits in integer, but we really want to be stable across different
99 #define NUM_CONDITIONS 32
101 enum predicate_conditions
103 predicate_false_condition
= 0,
104 predicate_not_inlined_condition
= 1,
105 predicate_first_dynamic_condition
= 2
108 /* Special condition code we use to represent test that operand is compile time
110 #define IS_NOT_CONSTANT ERROR_MARK
112 /* Holders of ipa cgraph hooks: */
113 static struct cgraph_node_hook_list
*function_insertion_hook_holder
;
114 static struct cgraph_node_hook_list
*node_removal_hook_holder
;
115 static struct cgraph_2node_hook_list
*node_duplication_hook_holder
;
116 static struct cgraph_2edge_hook_list
*edge_duplication_hook_holder
;
117 static struct cgraph_edge_hook_list
*edge_removal_hook_holder
;
118 static void inline_node_removal_hook (struct cgraph_node
*, void *);
119 static void inline_node_duplication_hook (struct cgraph_node
*,
120 struct cgraph_node
*, void *);
121 static void inline_edge_removal_hook (struct cgraph_edge
*, void *);
122 static void inline_edge_duplication_hook (struct cgraph_edge
*,
123 struct cgraph_edge
*,
126 /* VECtor holding inline summaries.
127 In GGC memory because conditions might point to constant trees. */
128 VEC(inline_summary_t
,gc
) *inline_summary_vec
;
129 VEC(inline_edge_summary_t
,heap
) *inline_edge_summary_vec
;
131 /* Cached node/edge growths. */
132 VEC(int,heap
) *node_growth_cache
;
133 VEC(edge_growth_cache_entry
,heap
) *edge_growth_cache
;
135 /* Edge predicates goes here. */
136 static alloc_pool edge_predicate_pool
;
138 /* Return true predicate (tautology).
139 We represent it by empty list of clauses. */
141 static inline struct predicate
142 true_predicate (void)
150 /* Return predicate testing single condition number COND. */
152 static inline struct predicate
153 single_cond_predicate (int cond
)
156 p
.clause
[0]=1 << cond
;
162 /* Return false predicate. First clause require false condition. */
164 static inline struct predicate
165 false_predicate (void)
167 return single_cond_predicate (predicate_false_condition
);
171 /* Return true if P is (false). */
174 true_predicate_p (struct predicate
*p
)
176 return !p
->clause
[0];
180 /* Return true if P is (false). */
183 false_predicate_p (struct predicate
*p
)
185 if (p
->clause
[0] == (1 << predicate_false_condition
))
187 gcc_checking_assert (!p
->clause
[1]
188 && p
->clause
[0] == 1 << predicate_false_condition
);
195 /* Return predicate that is set true when function is not inlined. */
196 static inline struct predicate
197 not_inlined_predicate (void)
199 return single_cond_predicate (predicate_not_inlined_condition
);
203 /* Add condition to condition list CONDS. */
205 static struct predicate
206 add_condition (struct inline_summary
*summary
, int operand_num
,
207 enum tree_code code
, tree val
)
211 struct condition new_cond
;
213 for (i
= 0; VEC_iterate (condition
, summary
->conds
, i
, c
); i
++)
215 if (c
->operand_num
== operand_num
218 return single_cond_predicate (i
+ predicate_first_dynamic_condition
);
220 /* Too many conditions. Give up and return constant true. */
221 if (i
== NUM_CONDITIONS
- predicate_first_dynamic_condition
)
222 return true_predicate ();
224 new_cond
.operand_num
= operand_num
;
225 new_cond
.code
= code
;
227 VEC_safe_push (condition
, gc
, summary
->conds
, &new_cond
);
228 return single_cond_predicate (i
+ predicate_first_dynamic_condition
);
232 /* Add clause CLAUSE into the predicate P. */
235 add_clause (conditions conditions
, struct predicate
*p
, clause_t clause
)
239 int insert_here
= -1;
246 /* False clause makes the whole predicate false. Kill the other variants. */
247 if (clause
== (1 << predicate_false_condition
))
249 p
->clause
[0] = (1 << predicate_false_condition
);
253 if (false_predicate_p (p
))
256 /* No one should be sily enough to add false into nontrivial clauses. */
257 gcc_checking_assert (!(clause
& (1 << predicate_false_condition
)));
259 /* Look where to insert the clause. At the same time prune out
260 clauses of P that are implied by the new clause and thus
262 for (i
= 0, i2
= 0; i
<= MAX_CLAUSES
; i
++)
264 p
->clause
[i2
] = p
->clause
[i
];
269 /* If p->clause[i] implies clause, there is nothing to add. */
270 if ((p
->clause
[i
] & clause
) == p
->clause
[i
])
272 /* We had nothing to add, none of clauses should've become redundant. */
273 gcc_checking_assert (i
== i2
);
277 if (p
->clause
[i
] < clause
&& insert_here
< 0)
280 /* If clause implies p->clause[i], then p->clause[i] becomes redundant.
281 Otherwise the p->clause[i] has to stay. */
282 if ((p
->clause
[i
] & clause
) != clause
)
286 /* Look for clauses that are obviously true. I.e.
287 op0 == 5 || op0 != 5. */
288 for (c1
= predicate_first_dynamic_condition
; c1
< NUM_CONDITIONS
; c1
++)
289 for (c2
= c1
+ 1; c2
<= NUM_CONDITIONS
; c2
++)
290 if ((clause
& (1 << c1
))
291 && (clause
& (1 << c2
)))
293 condition
*cc1
= VEC_index (condition
,
295 c1
- predicate_first_dynamic_condition
);
296 condition
*cc2
= VEC_index (condition
,
298 c2
- predicate_first_dynamic_condition
);
299 if (cc1
->operand_num
== cc2
->operand_num
300 && cc1
->val
== cc2
->val
301 && cc1
->code
== invert_tree_comparison (cc2
->code
,
302 HONOR_NANS (TYPE_MODE (TREE_TYPE (cc1
->val
)))))
307 /* We run out of variants. Be conservative in positive direction. */
308 if (i2
== MAX_CLAUSES
)
310 /* Keep clauses in decreasing order. This makes equivalence testing easy. */
311 p
->clause
[i2
+ 1] = 0;
312 if (insert_here
>= 0)
313 for (;i2
> insert_here
; i2
--)
314 p
->clause
[i2
] = p
->clause
[i2
- 1];
317 p
->clause
[insert_here
] = clause
;
323 static struct predicate
324 and_predicates (conditions conditions
,
325 struct predicate
*p
, struct predicate
*p2
)
327 struct predicate out
= *p
;
330 /* Avoid busy work. */
331 if (false_predicate_p (p2
) || true_predicate_p (p
))
333 if (false_predicate_p (p
) || true_predicate_p (p2
))
336 /* See how far predicates match. */
337 for (i
= 0; p
->clause
[i
] && p
->clause
[i
] == p2
->clause
[i
]; i
++)
339 gcc_checking_assert (i
< MAX_CLAUSES
);
342 /* Combine the predicates rest. */
343 for (; p2
->clause
[i
]; i
++)
345 gcc_checking_assert (i
< MAX_CLAUSES
);
346 add_clause (conditions
, &out
, p2
->clause
[i
]);
352 /* Return true if predicates are obviously equal. */
355 predicates_equal_p (struct predicate
*p
, struct predicate
*p2
)
358 for (i
= 0; p
->clause
[i
]; i
++)
360 gcc_checking_assert (i
< MAX_CLAUSES
);
361 gcc_checking_assert (p
->clause
[i
] > p
->clause
[i
+ 1]);
362 gcc_checking_assert (!p2
->clause
[i
] || p2
->clause
[i
] > p2
->clause
[i
+ 1]);
363 if (p
->clause
[i
] != p2
->clause
[i
])
366 return !p2
->clause
[i
];
372 static struct predicate
373 or_predicates (conditions conditions
, struct predicate
*p
, struct predicate
*p2
)
375 struct predicate out
= true_predicate ();
378 /* Avoid busy work. */
379 if (false_predicate_p (p2
) || true_predicate_p (p
))
381 if (false_predicate_p (p
) || true_predicate_p (p2
))
383 if (predicates_equal_p (p
, p2
))
386 /* OK, combine the predicates. */
387 for (i
= 0; p
->clause
[i
]; i
++)
388 for (j
= 0; p2
->clause
[j
]; j
++)
390 gcc_checking_assert (i
< MAX_CLAUSES
&& j
< MAX_CLAUSES
);
391 add_clause (conditions
, &out
, p
->clause
[i
] | p2
->clause
[j
]);
397 /* Having partial truth assignment in POSSIBLE_TRUTHS, return false if predicate P
401 evaluate_predicate (struct predicate
*p
, clause_t possible_truths
)
405 /* True remains true. */
406 if (true_predicate_p (p
))
409 gcc_assert (!(possible_truths
& (1 << predicate_false_condition
)));
411 /* See if we can find clause we can disprove. */
412 for (i
= 0; p
->clause
[i
]; i
++)
414 gcc_checking_assert (i
< MAX_CLAUSES
);
415 if (!(p
->clause
[i
] & possible_truths
))
422 /* Dump conditional COND. */
425 dump_condition (FILE *f
, conditions conditions
, int cond
)
428 if (cond
== predicate_false_condition
)
429 fprintf (f
, "false");
430 else if (cond
== predicate_not_inlined_condition
)
431 fprintf (f
, "not inlined");
434 c
= VEC_index (condition
, conditions
, cond
- predicate_first_dynamic_condition
);
435 fprintf (f
, "op%i", c
->operand_num
);
436 if (c
->code
== IS_NOT_CONSTANT
)
438 fprintf (f
, " not constant");
441 fprintf (f
, " %s ", op_symbol_code (c
->code
));
442 print_generic_expr (f
, c
->val
, 1);
447 /* Dump clause CLAUSE. */
450 dump_clause (FILE *f
, conditions conds
, clause_t clause
)
457 for (i
= 0; i
< NUM_CONDITIONS
; i
++)
458 if (clause
& (1 << i
))
463 dump_condition (f
, conds
, i
);
469 /* Dump predicate PREDICATE. */
472 dump_predicate (FILE *f
, conditions conds
, struct predicate
*pred
)
475 if (true_predicate_p (pred
))
476 dump_clause (f
, conds
, 0);
478 for (i
= 0; pred
->clause
[i
]; i
++)
482 dump_clause (f
, conds
, pred
->clause
[i
]);
488 /* Record SIZE and TIME under condition PRED into the inline summary. */
491 account_size_time (struct inline_summary
*summary
, int size
, int time
, struct predicate
*pred
)
497 if (false_predicate_p (pred
))
500 /* We need to create initial empty unconitional clause, but otherwie
501 we don't need to account empty times and sizes. */
502 if (!size
&& !time
&& summary
->entry
)
505 /* Watch overflow that might result from insane profiles. */
506 if (time
> MAX_TIME
* INLINE_TIME_SCALE
)
507 time
= MAX_TIME
* INLINE_TIME_SCALE
;
508 gcc_assert (time
>= 0);
510 for (i
= 0; VEC_iterate (size_time_entry
, summary
->entry
, i
, e
); i
++)
511 if (predicates_equal_p (&e
->predicate
, pred
))
520 e
= VEC_index (size_time_entry
, summary
->entry
, 0);
521 gcc_assert (!e
->predicate
.clause
[0]);
523 if (dump_file
&& (dump_flags
& TDF_DETAILS
) && (time
|| size
))
525 fprintf (dump_file
, "\t\tAccounting size:%3.2f, time:%3.2f on %spredicate:",
526 ((double)size
) / INLINE_SIZE_SCALE
, ((double)time
) / INLINE_TIME_SCALE
,
527 found
? "" : "new ");
528 dump_predicate (dump_file
, summary
->conds
, pred
);
532 struct size_time_entry new_entry
;
533 new_entry
.size
= size
;
534 new_entry
.time
= time
;
535 new_entry
.predicate
= *pred
;
536 VEC_safe_push (size_time_entry
, gc
, summary
->entry
, &new_entry
);
542 if (e
->time
> MAX_TIME
* INLINE_TIME_SCALE
)
543 e
->time
= MAX_TIME
* INLINE_TIME_SCALE
;
547 /* Set predicate for edge E. */
550 edge_set_predicate (struct cgraph_edge
*e
, struct predicate
*predicate
)
552 struct inline_edge_summary
*es
= inline_edge_summary (e
);
553 if (predicate
&& !true_predicate_p (predicate
))
556 es
->predicate
= (struct predicate
*)pool_alloc (edge_predicate_pool
);
557 *es
->predicate
= *predicate
;
562 pool_free (edge_predicate_pool
, es
->predicate
);
563 es
->predicate
= NULL
;
568 /* KNOWN_VALS is partial mapping of parameters of NODE to constant values.
569 Return clause of possible truths. When INLINE_P is true, assume that
573 evaluate_conditions_for_known_args (struct cgraph_node
*node
,
575 VEC (tree
, heap
) *known_vals
)
577 clause_t clause
= inline_p
? 0 : 1 << predicate_not_inlined_condition
;
578 struct inline_summary
*info
= inline_summary (node
);
582 for (i
= 0; VEC_iterate (condition
, info
->conds
, i
, c
); i
++)
587 /* We allow call stmt to have fewer arguments than the callee
588 function (especially for K&R style programs). So bound
590 if (c
->operand_num
< (int)VEC_length (tree
, known_vals
))
591 val
= VEC_index (tree
, known_vals
, c
->operand_num
);
597 clause
|= 1 << (i
+ predicate_first_dynamic_condition
);
600 if (c
->code
== IS_NOT_CONSTANT
)
602 res
= fold_binary_to_constant (c
->code
, boolean_type_node
, val
, c
->val
);
604 && integer_zerop (res
))
606 clause
|= 1 << (i
+ predicate_first_dynamic_condition
);
612 /* Work out what conditions might be true at invocation of E. */
615 evaluate_conditions_for_edge (struct cgraph_edge
*e
, bool inline_p
)
617 clause_t clause
= inline_p
? 0 : 1 << predicate_not_inlined_condition
;
618 struct cgraph_node
*callee
= cgraph_function_or_thunk_node (e
->callee
, NULL
);
619 struct inline_summary
*info
= inline_summary (callee
);
622 if (ipa_node_params_vector
&& info
->conds
623 /* FIXME: it seems that we forget to get argument count in some cases,
624 probaby for previously indirect edges or so. */
625 && ipa_get_cs_argument_count (IPA_EDGE_REF (e
)))
627 struct ipa_node_params
*parms_info
;
628 struct ipa_edge_args
*args
= IPA_EDGE_REF (e
);
629 int i
, count
= ipa_get_cs_argument_count (args
);
630 VEC (tree
, heap
) *known_vals
= NULL
;
632 if (e
->caller
->global
.inlined_to
)
633 parms_info
= IPA_NODE_REF (e
->caller
->global
.inlined_to
);
635 parms_info
= IPA_NODE_REF (e
->caller
);
637 VEC_safe_grow_cleared (tree
, heap
, known_vals
, count
);
638 for (i
= 0; i
< count
; i
++)
640 tree cst
= ipa_cst_from_jfunc (parms_info
,
641 ipa_get_ith_jump_func (args
, i
));
643 VEC_replace (tree
, known_vals
, i
, cst
);
645 clause
= evaluate_conditions_for_known_args (callee
,
646 inline_p
, known_vals
);
647 VEC_free (tree
, heap
, known_vals
);
650 for (i
= 0; i
< (int)VEC_length (condition
, info
->conds
); i
++)
651 clause
|= 1 << (i
+ predicate_first_dynamic_condition
);
657 /* Allocate the inline summary vector or resize it to cover all cgraph nodes. */
660 inline_summary_alloc (void)
662 if (!node_removal_hook_holder
)
663 node_removal_hook_holder
=
664 cgraph_add_node_removal_hook (&inline_node_removal_hook
, NULL
);
665 if (!edge_removal_hook_holder
)
666 edge_removal_hook_holder
=
667 cgraph_add_edge_removal_hook (&inline_edge_removal_hook
, NULL
);
668 if (!node_duplication_hook_holder
)
669 node_duplication_hook_holder
=
670 cgraph_add_node_duplication_hook (&inline_node_duplication_hook
, NULL
);
671 if (!edge_duplication_hook_holder
)
672 edge_duplication_hook_holder
=
673 cgraph_add_edge_duplication_hook (&inline_edge_duplication_hook
, NULL
);
675 if (VEC_length (inline_summary_t
, inline_summary_vec
)
676 <= (unsigned) cgraph_max_uid
)
677 VEC_safe_grow_cleared (inline_summary_t
, gc
,
678 inline_summary_vec
, cgraph_max_uid
+ 1);
679 if (VEC_length (inline_edge_summary_t
, inline_edge_summary_vec
)
680 <= (unsigned) cgraph_edge_max_uid
)
681 VEC_safe_grow_cleared (inline_edge_summary_t
, heap
,
682 inline_edge_summary_vec
, cgraph_edge_max_uid
+ 1);
683 if (!edge_predicate_pool
)
684 edge_predicate_pool
= create_alloc_pool ("edge predicates", sizeof (struct predicate
),
688 /* Hook that is called by cgraph.c when a node is removed. */
691 inline_node_removal_hook (struct cgraph_node
*node
, void *data ATTRIBUTE_UNUSED
)
693 struct inline_summary
*info
;
694 if (VEC_length (inline_summary_t
, inline_summary_vec
)
695 <= (unsigned)node
->uid
)
697 info
= inline_summary (node
);
698 reset_node_growth_cache (node
);
699 VEC_free (condition
, gc
, info
->conds
);
700 VEC_free (size_time_entry
, gc
, info
->entry
);
703 memset (info
, 0, sizeof (inline_summary_t
));
707 /* Hook that is called by cgraph.c when a node is duplicated. */
710 inline_node_duplication_hook (struct cgraph_node
*src
, struct cgraph_node
*dst
,
711 ATTRIBUTE_UNUSED
void *data
)
713 struct inline_summary
*info
;
714 inline_summary_alloc ();
715 info
= inline_summary (dst
);
716 memcpy (info
, inline_summary (src
),
717 sizeof (struct inline_summary
));
718 /* TODO: as an optimization, we may avoid copying conditions
719 that are known to be false or true. */
720 info
->conds
= VEC_copy (condition
, gc
, info
->conds
);
722 /* When there are any replacements in the function body, see if we can figure
723 out that something was optimized out. */
724 if (ipa_node_params_vector
&& dst
->clone
.tree_map
)
726 VEC(size_time_entry
,gc
) *entry
= info
->entry
;
727 /* Use SRC parm info since it may not be copied yet. */
728 struct ipa_node_params
*parms_info
= IPA_NODE_REF (src
);
729 VEC (tree
, heap
) *known_vals
= NULL
;
730 int count
= ipa_get_param_count (parms_info
);
732 clause_t possible_truths
;
733 struct predicate true_pred
= true_predicate ();
735 int optimized_out_size
= 0;
736 gcov_type optimized_out_time
= 0;
737 bool inlined_to_p
= false;
738 struct cgraph_edge
*edge
;
741 VEC_safe_grow_cleared (tree
, heap
, known_vals
, count
);
742 for (i
= 0; i
< count
; i
++)
744 tree t
= ipa_get_param (parms_info
, i
);
745 struct ipa_replace_map
*r
;
748 VEC_iterate (ipa_replace_map_p
, dst
->clone
.tree_map
, j
, r
);
755 VEC_replace (tree
, known_vals
, i
, r
->new_tree
);
760 possible_truths
= evaluate_conditions_for_known_args (dst
,
762 VEC_free (tree
, heap
, known_vals
);
764 account_size_time (info
, 0, 0, &true_pred
);
766 /* Remap size_time vectors.
767 Simplify the predicate by prunning out alternatives that are known
769 TODO: as on optimization, we can also eliminate conditions known to be true. */
770 for (i
= 0; VEC_iterate (size_time_entry
, entry
, i
, e
); i
++)
772 struct predicate new_predicate
= true_predicate ();
773 for (j
= 0; e
->predicate
.clause
[j
]; j
++)
774 if (!(possible_truths
& e
->predicate
.clause
[j
]))
776 new_predicate
= false_predicate ();
780 add_clause (info
->conds
, &new_predicate
,
781 possible_truths
& e
->predicate
.clause
[j
]);
782 if (false_predicate_p (&new_predicate
))
784 optimized_out_size
+= e
->size
;
785 optimized_out_time
+= e
->time
;
788 account_size_time (info
, e
->size
, e
->time
, &new_predicate
);
791 /* Remap edge predicates with the same simplificaiton as above. */
792 for (edge
= dst
->callees
; edge
; edge
= edge
->next_callee
)
794 struct predicate new_predicate
= true_predicate ();
795 struct inline_edge_summary
*es
= inline_edge_summary (edge
);
797 if (!edge
->inline_failed
)
801 for (j
= 0; es
->predicate
->clause
[j
]; j
++)
802 if (!(possible_truths
& es
->predicate
->clause
[j
]))
804 new_predicate
= false_predicate ();
808 add_clause (info
->conds
, &new_predicate
,
809 possible_truths
& es
->predicate
->clause
[j
]);
810 if (false_predicate_p (&new_predicate
)
811 && !false_predicate_p (es
->predicate
))
813 optimized_out_size
+= es
->call_stmt_size
* INLINE_SIZE_SCALE
;
814 optimized_out_time
+= (es
->call_stmt_time
815 * (INLINE_TIME_SCALE
/ CGRAPH_FREQ_BASE
)
819 *es
->predicate
= new_predicate
;
822 /* Remap indirect edge predicates with the same simplificaiton as above. */
823 for (edge
= dst
->indirect_calls
; edge
; edge
= edge
->next_callee
)
825 struct predicate new_predicate
= true_predicate ();
826 struct inline_edge_summary
*es
= inline_edge_summary (edge
);
828 if (!edge
->inline_failed
)
832 for (j
= 0; es
->predicate
->clause
[j
]; j
++)
833 if (!(possible_truths
& es
->predicate
->clause
[j
]))
835 new_predicate
= false_predicate ();
839 add_clause (info
->conds
, &new_predicate
,
840 possible_truths
& es
->predicate
->clause
[j
]);
841 if (false_predicate_p (&new_predicate
)
842 && !false_predicate_p (es
->predicate
))
844 optimized_out_size
+= es
->call_stmt_size
* INLINE_SIZE_SCALE
;
845 optimized_out_time
+= (es
->call_stmt_time
846 * (INLINE_TIME_SCALE
/ CGRAPH_FREQ_BASE
)
850 *es
->predicate
= new_predicate
;
853 /* If inliner or someone after inliner will ever start producing
854 non-trivial clones, we will get trouble with lack of information
855 about updating self sizes, because size vectors already contains
856 sizes of the calees. */
857 gcc_assert (!inlined_to_p
858 || (!optimized_out_size
&& !optimized_out_time
));
860 info
->size
-= optimized_out_size
/ INLINE_SIZE_SCALE
;
861 info
->self_size
-= optimized_out_size
/ INLINE_SIZE_SCALE
;
862 gcc_assert (info
->size
> 0);
863 gcc_assert (info
->self_size
> 0);
865 optimized_out_time
/= INLINE_TIME_SCALE
;
866 if (optimized_out_time
> MAX_TIME
)
867 optimized_out_time
= MAX_TIME
;
868 info
->time
-= optimized_out_time
;
869 info
->self_time
-= optimized_out_time
;
872 if (info
->self_time
< 0)
876 info
->entry
= VEC_copy (size_time_entry
, gc
, info
->entry
);
880 /* Hook that is called by cgraph.c when a node is duplicated. */
883 inline_edge_duplication_hook (struct cgraph_edge
*src
, struct cgraph_edge
*dst
,
884 ATTRIBUTE_UNUSED
void *data
)
886 struct inline_edge_summary
*info
;
887 struct inline_edge_summary
*srcinfo
;
888 inline_summary_alloc ();
889 info
= inline_edge_summary (dst
);
890 srcinfo
= inline_edge_summary (src
);
891 memcpy (info
, srcinfo
,
892 sizeof (struct inline_edge_summary
));
893 info
->predicate
= NULL
;
894 edge_set_predicate (dst
, srcinfo
->predicate
);
898 /* Keep edge cache consistent across edge removal. */
901 inline_edge_removal_hook (struct cgraph_edge
*edge
, void *data ATTRIBUTE_UNUSED
)
903 if (edge_growth_cache
)
904 reset_edge_growth_cache (edge
);
905 if (edge
->uid
< (int)VEC_length (inline_edge_summary_t
, inline_edge_summary_vec
))
907 edge_set_predicate (edge
, NULL
);
908 memset (inline_edge_summary (edge
), 0, sizeof (struct inline_edge_summary
));
913 /* Initialize growth caches. */
916 initialize_growth_caches (void)
918 if (cgraph_edge_max_uid
)
919 VEC_safe_grow_cleared (edge_growth_cache_entry
, heap
, edge_growth_cache
,
920 cgraph_edge_max_uid
);
922 VEC_safe_grow_cleared (int, heap
, node_growth_cache
, cgraph_max_uid
);
926 /* Free growth caches. */
929 free_growth_caches (void)
931 VEC_free (edge_growth_cache_entry
, heap
, edge_growth_cache
);
932 edge_growth_cache
= 0;
933 VEC_free (int, heap
, node_growth_cache
);
934 node_growth_cache
= 0;
938 /* Dump edge summaries associated to NODE and recursively to all clones.
942 dump_inline_edge_summary (FILE * f
, int indent
, struct cgraph_node
*node
,
943 struct inline_summary
*info
)
945 struct cgraph_edge
*edge
;
946 for (edge
= node
->callees
; edge
; edge
= edge
->next_callee
)
948 struct inline_edge_summary
*es
= inline_edge_summary (edge
);
949 struct cgraph_node
*callee
= cgraph_function_or_thunk_node (edge
->callee
, NULL
);
950 fprintf (f
, "%*s%s/%i %s\n%*s loop depth:%2i freq:%4i size:%2i time: %2i callee size:%2i stack:%2i",
951 indent
, "", cgraph_node_name (callee
),
953 !edge
->inline_failed
? "inlined"
954 : cgraph_inline_failed_string (edge
->inline_failed
),
960 (int)inline_summary (callee
)->size
,
961 (int)inline_summary (callee
)->estimated_stack_size
);
964 fprintf (f
, " predicate: ");
965 dump_predicate (f
, info
->conds
, es
->predicate
);
969 if (!edge
->inline_failed
)
971 fprintf (f
, "%*sStack frame offset %i, callee self size %i, callee size %i\n",
973 (int)inline_summary (callee
)->stack_frame_offset
,
974 (int)inline_summary (callee
)->estimated_self_stack_size
,
975 (int)inline_summary (callee
)->estimated_stack_size
);
976 dump_inline_edge_summary (f
, indent
+2, callee
, info
);
979 for (edge
= node
->indirect_calls
; edge
; edge
= edge
->next_callee
)
981 struct inline_edge_summary
*es
= inline_edge_summary (edge
);
982 fprintf (f
, "%*sindirect call loop depth:%2i freq:%4i size:%2i time: %2i\n",
990 fprintf (f
, "predicate: ");
991 dump_predicate (f
, info
->conds
, es
->predicate
);
1000 dump_inline_summary (FILE * f
, struct cgraph_node
*node
)
1004 struct inline_summary
*s
= inline_summary (node
);
1007 fprintf (f
, "Inline summary for %s/%i", cgraph_node_name (node
),
1009 if (DECL_DISREGARD_INLINE_LIMITS (node
->decl
))
1010 fprintf (f
, " always_inline");
1012 fprintf (f
, " inlinable");
1013 fprintf (f
, "\n self time: %i\n",
1015 fprintf (f
, " global time: %i\n", s
->time
);
1016 fprintf (f
, " self size: %i\n",
1018 fprintf (f
, " global size: %i\n", s
->size
);
1019 fprintf (f
, " self stack: %i\n",
1020 (int) s
->estimated_self_stack_size
);
1021 fprintf (f
, " global stack: %i\n",
1022 (int) s
->estimated_stack_size
);
1024 VEC_iterate (size_time_entry
, s
->entry
, i
, e
);
1027 fprintf (f
, " size:%f, time:%f, predicate:",
1028 (double) e
->size
/ INLINE_SIZE_SCALE
,
1029 (double) e
->time
/ INLINE_TIME_SCALE
);
1030 dump_predicate (f
, s
->conds
, &e
->predicate
);
1032 fprintf (f
, " calls:\n");
1033 dump_inline_edge_summary (f
, 4, node
, s
);
1039 debug_inline_summary (struct cgraph_node
*node
)
1041 dump_inline_summary (stderr
, node
);
1045 dump_inline_summaries (FILE *f
)
1047 struct cgraph_node
*node
;
1049 for (node
= cgraph_nodes
; node
; node
= node
->next
)
1050 if (node
->analyzed
&& !node
->global
.inlined_to
)
1051 dump_inline_summary (f
, node
);
1054 /* Give initial reasons why inlining would fail on EDGE. This gets either
1055 nullified or usually overwritten by more precise reasons later. */
1058 initialize_inline_failed (struct cgraph_edge
*e
)
1060 struct cgraph_node
*callee
= e
->callee
;
1062 if (e
->indirect_unknown_callee
)
1063 e
->inline_failed
= CIF_INDIRECT_UNKNOWN_CALL
;
1064 else if (!callee
->analyzed
)
1065 e
->inline_failed
= CIF_BODY_NOT_AVAILABLE
;
1066 else if (callee
->local
.redefined_extern_inline
)
1067 e
->inline_failed
= CIF_REDEFINED_EXTERN_INLINE
;
1068 else if (e
->call_stmt
&& gimple_call_cannot_inline_p (e
->call_stmt
))
1069 e
->inline_failed
= CIF_MISMATCHED_ARGUMENTS
;
1071 e
->inline_failed
= CIF_FUNCTION_NOT_CONSIDERED
;
1074 /* Callback of walk_aliased_vdefs. Flags that it has been invoked to the
1075 boolean variable pointed to by DATA. */
1078 mark_modified (ao_ref
*ao ATTRIBUTE_UNUSED
, tree vdef ATTRIBUTE_UNUSED
,
1081 bool *b
= (bool *) data
;
1086 /* If OP reffers to value of function parameter, return
1087 the corresponding parameter. */
1090 unmodified_parm (gimple stmt
, tree op
)
1092 /* SSA_NAME referring to parm default def? */
1093 if (TREE_CODE (op
) == SSA_NAME
1094 && SSA_NAME_IS_DEFAULT_DEF (op
)
1095 && TREE_CODE (SSA_NAME_VAR (op
)) == PARM_DECL
)
1096 return SSA_NAME_VAR (op
);
1097 /* Non-SSA parm reference? */
1098 if (TREE_CODE (op
) == PARM_DECL
)
1100 bool modified
= false;
1103 ao_ref_init (&refd
, op
);
1104 walk_aliased_vdefs (&refd
, gimple_vuse (stmt
), mark_modified
, &modified
,
1109 /* Assignment from a parameter? */
1110 if (TREE_CODE (op
) == SSA_NAME
1111 && !SSA_NAME_IS_DEFAULT_DEF (op
)
1112 && gimple_assign_single_p (SSA_NAME_DEF_STMT (op
)))
1113 return unmodified_parm (SSA_NAME_DEF_STMT (op
),
1114 gimple_assign_rhs1 (SSA_NAME_DEF_STMT (op
)));
1118 /* See if statement might disappear after inlining.
1119 0 - means not eliminated
1120 1 - half of statements goes away
1121 2 - for sure it is eliminated.
1122 We are not terribly sophisticated, basically looking for simple abstraction
1123 penalty wrappers. */
1126 eliminated_by_inlining_prob (gimple stmt
)
1128 enum gimple_code code
= gimple_code (stmt
);
1138 if (gimple_num_ops (stmt
) != 2)
1141 /* Casts of parameters, loads from parameters passed by reference
1142 and stores to return value or parameters are often free after
1143 inlining dua to SRA and further combining.
1144 Assume that half of statements goes away. */
1145 if (gimple_assign_rhs_code (stmt
) == CONVERT_EXPR
1146 || gimple_assign_rhs_code (stmt
) == NOP_EXPR
1147 || gimple_assign_rhs_code (stmt
) == VIEW_CONVERT_EXPR
1148 || gimple_assign_rhs_class (stmt
) == GIMPLE_SINGLE_RHS
)
1150 tree rhs
= gimple_assign_rhs1 (stmt
);
1151 tree lhs
= gimple_assign_lhs (stmt
);
1152 tree inner_rhs
= get_base_address (rhs
);
1153 tree inner_lhs
= get_base_address (lhs
);
1154 bool rhs_free
= false;
1155 bool lhs_free
= false;
1162 if (unmodified_parm (stmt
, inner_rhs
))
1164 if (rhs_free
&& is_gimple_reg (lhs
))
1166 if (((TREE_CODE (inner_lhs
) == PARM_DECL
1167 || (TREE_CODE (inner_lhs
) == SSA_NAME
1168 && SSA_NAME_IS_DEFAULT_DEF (inner_lhs
)
1169 && TREE_CODE (SSA_NAME_VAR (inner_lhs
)) == PARM_DECL
))
1170 && inner_lhs
!= lhs
)
1171 || TREE_CODE (inner_lhs
) == RESULT_DECL
1172 || (TREE_CODE (inner_lhs
) == SSA_NAME
1173 && TREE_CODE (SSA_NAME_VAR (inner_lhs
)) == RESULT_DECL
))
1176 && (is_gimple_reg (rhs
) || is_gimple_min_invariant (rhs
)))
1178 if (lhs_free
&& rhs_free
)
1188 /* If BB ends by a conditional we can turn into predicates, attach corresponding
1189 predicates to the CFG edges. */
1192 set_cond_stmt_execution_predicate (struct ipa_node_params
*info
,
1193 struct inline_summary
*summary
,
1199 enum tree_code code
, inverted_code
;
1206 last
= last_stmt (bb
);
1208 || gimple_code (last
) != GIMPLE_COND
)
1210 if (!is_gimple_ip_invariant (gimple_cond_rhs (last
)))
1212 op
= gimple_cond_lhs (last
);
1213 /* TODO: handle conditionals like
1216 parm
= unmodified_parm (last
, op
);
1219 index
= ipa_get_param_decl_index (info
, parm
);
1222 code
= gimple_cond_code (last
);
1223 inverted_code
= invert_tree_comparison (code
,
1224 HONOR_NANS (TYPE_MODE (TREE_TYPE (op
))));
1226 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1228 struct predicate p
= add_condition (summary
,
1230 e
->flags
& EDGE_TRUE_VALUE
1231 ? code
: inverted_code
,
1232 gimple_cond_rhs (last
));
1233 e
->aux
= pool_alloc (edge_predicate_pool
);
1234 *(struct predicate
*)e
->aux
= p
;
1238 if (TREE_CODE (op
) != SSA_NAME
)
1241 if (builtin_constant_p (op))
1245 Here we can predicate nonconstant_code. We can't
1246 really handle constant_code since we have no predicate
1247 for this and also the constant code is not known to be
1248 optimized away when inliner doen't see operand is constant.
1249 Other optimizers might think otherwise. */
1250 set_stmt
= SSA_NAME_DEF_STMT (op
);
1251 if (!gimple_call_builtin_p (set_stmt
, BUILT_IN_CONSTANT_P
)
1252 || gimple_call_num_args (set_stmt
) != 1)
1254 op2
= gimple_call_arg (set_stmt
, 0);
1255 parm
= unmodified_parm (set_stmt
, op2
);
1258 index
= ipa_get_param_decl_index (info
, parm
);
1261 if (gimple_cond_code (last
) != NE_EXPR
1262 || !integer_zerop (gimple_cond_rhs (last
)))
1264 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1265 if (e
->flags
& EDGE_FALSE_VALUE
)
1267 struct predicate p
= add_condition (summary
,
1271 e
->aux
= pool_alloc (edge_predicate_pool
);
1272 *(struct predicate
*)e
->aux
= p
;
1277 /* If BB ends by a switch we can turn into predicates, attach corresponding
1278 predicates to the CFG edges. */
1281 set_switch_stmt_execution_predicate (struct ipa_node_params
*info
,
1282 struct inline_summary
*summary
,
1294 last
= last_stmt (bb
);
1296 || gimple_code (last
) != GIMPLE_SWITCH
)
1298 op
= gimple_switch_index (last
);
1299 parm
= unmodified_parm (last
, op
);
1302 index
= ipa_get_param_decl_index (info
, parm
);
1306 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1308 e
->aux
= pool_alloc (edge_predicate_pool
);
1309 *(struct predicate
*)e
->aux
= false_predicate ();
1311 n
= gimple_switch_num_labels(last
);
1312 for (case_idx
= 0; case_idx
< n
; ++case_idx
)
1314 tree cl
= gimple_switch_label (last
, case_idx
);
1318 e
= find_edge (bb
, label_to_block (CASE_LABEL (cl
)));
1319 min
= CASE_LOW (cl
);
1320 max
= CASE_HIGH (cl
);
1322 /* For default we might want to construct predicate that none
1323 of cases is met, but it is bit hard to do not having negations
1324 of conditionals handy. */
1326 p
= true_predicate ();
1328 p
= add_condition (summary
, index
,
1333 struct predicate p1
, p2
;
1334 p1
= add_condition (summary
, index
,
1337 p2
= add_condition (summary
, index
,
1340 p
= and_predicates (summary
->conds
, &p1
, &p2
);
1342 *(struct predicate
*)e
->aux
1343 = or_predicates (summary
->conds
, &p
, (struct predicate
*)e
->aux
);
1348 /* For each BB in NODE attach to its AUX pointer predicate under
1349 which it is executable. */
1352 compute_bb_predicates (struct cgraph_node
*node
,
1353 struct ipa_node_params
*parms_info
,
1354 struct inline_summary
*summary
)
1356 struct function
*my_function
= DECL_STRUCT_FUNCTION (node
->decl
);
1360 FOR_EACH_BB_FN (bb
, my_function
)
1362 set_cond_stmt_execution_predicate (parms_info
, summary
, bb
);
1363 set_switch_stmt_execution_predicate (parms_info
, summary
, bb
);
1366 /* Entry block is always executable. */
1367 ENTRY_BLOCK_PTR_FOR_FUNCTION (my_function
)->aux
= pool_alloc (edge_predicate_pool
);
1368 *(struct predicate
*)ENTRY_BLOCK_PTR_FOR_FUNCTION (my_function
)->aux
1369 = true_predicate ();
1371 /* A simple dataflow propagation of predicates forward in the CFG.
1372 TODO: work in reverse postorder. */
1376 FOR_EACH_BB_FN (bb
, my_function
)
1378 struct predicate p
= false_predicate ();
1381 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
1385 struct predicate this_bb_predicate
= *(struct predicate
*)e
->src
->aux
;
1387 this_bb_predicate
= and_predicates (summary
->conds
, &this_bb_predicate
,
1388 (struct predicate
*)e
->aux
);
1389 p
= or_predicates (summary
->conds
, &p
, &this_bb_predicate
);
1390 if (true_predicate_p (&p
))
1394 if (false_predicate_p (&p
))
1395 gcc_assert (!bb
->aux
);
1401 bb
->aux
= pool_alloc (edge_predicate_pool
);
1402 *((struct predicate
*)bb
->aux
) = p
;
1404 else if (!predicates_equal_p (&p
, (struct predicate
*)bb
->aux
))
1407 *((struct predicate
*)bb
->aux
) = p
;
1415 /* We keep info about constantness of SSA names. */
1417 typedef struct predicate predicate_t
;
1418 DEF_VEC_O (predicate_t
);
1419 DEF_VEC_ALLOC_O (predicate_t
, heap
);
1422 /* Return predicate specifying when the STMT might have result that is not a compile
1425 static struct predicate
1426 will_be_nonconstant_predicate (struct ipa_node_params
*info
,
1427 struct inline_summary
*summary
,
1429 VEC (predicate_t
, heap
) *nonconstant_names
)
1432 struct predicate p
= true_predicate ();
1435 struct predicate op_non_const
;
1437 /* What statments might be optimized away
1438 when their arguments are constant
1439 TODO: also trivial builtins.
1440 builtin_constant_p is already handled later. */
1441 if (gimple_code (stmt
) != GIMPLE_ASSIGN
1442 && gimple_code (stmt
) != GIMPLE_COND
1443 && gimple_code (stmt
) != GIMPLE_SWITCH
)
1446 /* Stores and loads will stay anyway.
1447 TODO: Constant memory accesses could be handled here, too. */
1448 if (gimple_vuse (stmt
))
1451 /* See if we understand all operands before we start
1452 adding conditionals. */
1453 FOR_EACH_SSA_TREE_OPERAND (use
, stmt
, iter
, SSA_OP_USE
)
1455 tree parm
= unmodified_parm (stmt
, use
);
1456 /* For arguments we can build a condition. */
1457 if (parm
&& ipa_get_param_decl_index (info
, parm
) >= 0)
1459 if (TREE_CODE (use
) != SSA_NAME
)
1461 /* If we know when operand is constant,
1462 we still can say something useful. */
1463 if (!true_predicate_p (VEC_index (predicate_t
, nonconstant_names
,
1464 SSA_NAME_VERSION (use
))))
1468 op_non_const
= false_predicate ();
1469 FOR_EACH_SSA_TREE_OPERAND (use
, stmt
, iter
, SSA_OP_USE
)
1471 tree parm
= unmodified_parm (stmt
, use
);
1472 if (parm
&& ipa_get_param_decl_index (info
, parm
) >= 0)
1473 p
= add_condition (summary
,
1474 ipa_get_param_decl_index (info
, parm
),
1475 IS_NOT_CONSTANT
, NULL
);
1477 p
= *VEC_index (predicate_t
, nonconstant_names
,
1478 SSA_NAME_VERSION (use
));
1479 op_non_const
= or_predicates (summary
->conds
, &p
, &op_non_const
);
1481 if (gimple_code (stmt
) == GIMPLE_ASSIGN
1482 && TREE_CODE (gimple_assign_lhs (stmt
)) == SSA_NAME
)
1483 VEC_replace (predicate_t
, nonconstant_names
,
1484 SSA_NAME_VERSION (gimple_assign_lhs (stmt
)), &op_non_const
);
1485 return op_non_const
;
1489 /* Compute function body size parameters for NODE.
1490 When EARLY is true, we compute only simple summaries without
1491 non-trivial predicates to drive the early inliner. */
1494 estimate_function_body_sizes (struct cgraph_node
*node
, bool early
)
1497 /* Estimate static overhead for function prologue/epilogue and alignment. */
1499 /* Benefits are scaled by probability of elimination that is in range
1502 gimple_stmt_iterator bsi
;
1503 struct function
*my_function
= DECL_STRUCT_FUNCTION (node
->decl
);
1505 struct inline_summary
*info
= inline_summary (node
);
1506 struct predicate bb_predicate
;
1507 struct ipa_node_params
*parms_info
= NULL
;
1508 VEC (predicate_t
, heap
) *nonconstant_names
= NULL
;
1510 if (ipa_node_params_vector
&& !early
&& optimize
)
1512 parms_info
= IPA_NODE_REF (node
);
1513 VEC_safe_grow_cleared (predicate_t
, heap
, nonconstant_names
,
1514 VEC_length (tree
, SSANAMES (my_function
)));
1522 fprintf (dump_file
, "\nAnalyzing function body size: %s\n",
1523 cgraph_node_name (node
));
1525 /* When we run into maximal number of entries, we assign everything to the
1526 constant truth case. Be sure to have it in list. */
1527 bb_predicate
= true_predicate ();
1528 account_size_time (info
, 0, 0, &bb_predicate
);
1530 bb_predicate
= not_inlined_predicate ();
1531 account_size_time (info
, 2 * INLINE_SIZE_SCALE
, 0, &bb_predicate
);
1533 gcc_assert (my_function
&& my_function
->cfg
);
1535 compute_bb_predicates (node
, parms_info
, info
);
1536 FOR_EACH_BB_FN (bb
, my_function
)
1538 freq
= compute_call_stmt_bb_frequency (node
->decl
, bb
);
1540 /* TODO: Obviously predicates can be propagated down across CFG. */
1544 bb_predicate
= *(struct predicate
*)bb
->aux
;
1546 bb_predicate
= false_predicate ();
1549 bb_predicate
= true_predicate ();
1551 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1553 fprintf (dump_file
, "\n BB %i predicate:", bb
->index
);
1554 dump_predicate (dump_file
, info
->conds
, &bb_predicate
);
1557 for (bsi
= gsi_start_bb (bb
); !gsi_end_p (bsi
); gsi_next (&bsi
))
1559 gimple stmt
= gsi_stmt (bsi
);
1560 int this_size
= estimate_num_insns (stmt
, &eni_size_weights
);
1561 int this_time
= estimate_num_insns (stmt
, &eni_time_weights
);
1563 struct predicate will_be_nonconstant
;
1565 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1567 fprintf (dump_file
, " ");
1568 print_gimple_stmt (dump_file
, stmt
, 0, 0);
1569 fprintf (dump_file
, "\t\tfreq:%3.2f size:%3i time:%3i\n",
1570 ((double)freq
)/CGRAPH_FREQ_BASE
, this_size
, this_time
);
1573 if (is_gimple_call (stmt
))
1575 struct cgraph_edge
*edge
= cgraph_edge (node
, stmt
);
1576 struct inline_edge_summary
*es
= inline_edge_summary (edge
);
1578 /* Special case: results of BUILT_IN_CONSTANT_P will be always
1579 resolved as constant. We however don't want to optimize
1580 out the cgraph edges. */
1581 if (nonconstant_names
1582 && gimple_call_builtin_p (stmt
, BUILT_IN_CONSTANT_P
)
1583 && gimple_call_lhs (stmt
)
1584 && TREE_CODE (gimple_call_lhs (stmt
)) == SSA_NAME
)
1586 struct predicate false_p
= false_predicate ();
1587 VEC_replace (predicate_t
, nonconstant_names
,
1588 SSA_NAME_VERSION (gimple_call_lhs (stmt
)), &false_p
);
1591 es
->call_stmt_size
= this_size
;
1592 es
->call_stmt_time
= this_time
;
1593 es
->loop_depth
= bb
->loop_depth
;
1594 edge_set_predicate (edge
, &bb_predicate
);
1596 /* Do not inline calls where we cannot triviall work around
1597 mismatches in argument or return types. */
1599 && cgraph_function_or_thunk_node (edge
->callee
, NULL
)
1600 && !gimple_check_call_matching_types (stmt
,
1601 cgraph_function_or_thunk_node (edge
->callee
,
1604 edge
->call_stmt_cannot_inline_p
= true;
1605 gimple_call_set_cannot_inline (stmt
, true);
1608 gcc_assert (!gimple_call_cannot_inline_p (stmt
));
1611 /* TODO: When conditional jump or swithc is known to be constant, but
1612 we did not translate it into the predicates, we really can account
1613 just maximum of the possible paths. */
1616 = will_be_nonconstant_predicate (parms_info
, info
,
1617 stmt
, nonconstant_names
);
1618 if (this_time
|| this_size
)
1626 prob
= eliminated_by_inlining_prob (stmt
);
1627 if (prob
== 1 && dump_file
&& (dump_flags
& TDF_DETAILS
))
1628 fprintf (dump_file
, "\t\t50%% will be eliminated by inlining\n");
1629 if (prob
== 2 && dump_file
&& (dump_flags
& TDF_DETAILS
))
1630 fprintf (dump_file
, "\t\twill eliminated by inlining\n");
1633 p
= and_predicates (info
->conds
, &bb_predicate
, &will_be_nonconstant
);
1635 p
= true_predicate ();
1637 /* We account everything but the calls. Calls have their own
1638 size/time info attached to cgraph edges. This is neccesary
1639 in order to make the cost disappear after inlining. */
1640 if (!is_gimple_call (stmt
))
1644 struct predicate ip
= not_inlined_predicate ();
1645 ip
= and_predicates (info
->conds
, &ip
, &p
);
1646 account_size_time (info
, this_size
* prob
,
1647 this_time
* prob
, &ip
);
1650 account_size_time (info
, this_size
* (2 - prob
),
1651 this_time
* (2 - prob
), &p
);
1654 gcc_assert (time
>= 0);
1655 gcc_assert (size
>= 0);
1659 FOR_ALL_BB_FN (bb
, my_function
)
1665 pool_free (edge_predicate_pool
, bb
->aux
);
1667 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1670 pool_free (edge_predicate_pool
, e
->aux
);
1674 time
= (time
+ CGRAPH_FREQ_BASE
/ 2) / CGRAPH_FREQ_BASE
;
1675 if (time
> MAX_TIME
)
1677 inline_summary (node
)->self_time
= time
;
1678 inline_summary (node
)->self_size
= size
;
1679 VEC_free (predicate_t
, heap
, nonconstant_names
);
1682 fprintf (dump_file
, "\n");
1683 dump_inline_summary (dump_file
, node
);
1688 /* Compute parameters of functions used by inliner.
1689 EARLY is true when we compute parameters for the early inliner */
1692 compute_inline_parameters (struct cgraph_node
*node
, bool early
)
1694 HOST_WIDE_INT self_stack_size
;
1695 struct cgraph_edge
*e
;
1696 struct inline_summary
*info
;
1698 gcc_assert (!node
->global
.inlined_to
);
1700 inline_summary_alloc ();
1702 info
= inline_summary (node
);
1704 /* FIXME: Thunks are inlinable, but tree-inline don't know how to do that.
1705 Once this happen, we will need to more curefully predict call
1707 if (node
->thunk
.thunk_p
)
1709 struct inline_edge_summary
*es
= inline_edge_summary (node
->callees
);
1710 struct predicate t
= true_predicate ();
1712 info
->inlinable
= 0;
1713 node
->callees
->call_stmt_cannot_inline_p
= true;
1714 node
->local
.can_change_signature
= false;
1715 es
->call_stmt_time
= 1;
1716 es
->call_stmt_size
= 1;
1717 account_size_time (info
, 0, 0, &t
);
1721 /* Estimate the stack size for the function if we're optimizing. */
1722 self_stack_size
= optimize
? estimated_stack_frame_size (node
) : 0;
1723 info
->estimated_self_stack_size
= self_stack_size
;
1724 info
->estimated_stack_size
= self_stack_size
;
1725 info
->stack_frame_offset
= 0;
1727 /* Can this function be inlined at all? */
1728 info
->inlinable
= tree_inlinable_function_p (node
->decl
);
1730 /* Type attributes can use parameter indices to describe them. */
1731 if (TYPE_ATTRIBUTES (TREE_TYPE (node
->decl
)))
1732 node
->local
.can_change_signature
= false;
1735 /* Otherwise, inlinable functions always can change signature. */
1736 if (info
->inlinable
)
1737 node
->local
.can_change_signature
= true;
1740 /* Functions calling builtin_apply can not change signature. */
1741 for (e
= node
->callees
; e
; e
= e
->next_callee
)
1743 tree
cdecl = e
->callee
->decl
;
1744 if (DECL_BUILT_IN (cdecl)
1745 && DECL_BUILT_IN_CLASS (cdecl) == BUILT_IN_NORMAL
1746 && (DECL_FUNCTION_CODE (cdecl) == BUILT_IN_APPLY_ARGS
1747 || DECL_FUNCTION_CODE (cdecl) == BUILT_IN_VA_START
))
1750 node
->local
.can_change_signature
= !e
;
1753 estimate_function_body_sizes (node
, early
);
1755 /* Inlining characteristics are maintained by the cgraph_mark_inline. */
1756 info
->time
= info
->self_time
;
1757 info
->size
= info
->self_size
;
1758 info
->stack_frame_offset
= 0;
1759 info
->estimated_stack_size
= info
->estimated_self_stack_size
;
1763 /* Compute parameters of functions used by inliner using
1764 current_function_decl. */
1767 compute_inline_parameters_for_current (void)
1769 compute_inline_parameters (cgraph_get_node (current_function_decl
), true);
1773 struct gimple_opt_pass pass_inline_parameters
=
1777 "inline_param", /* name */
1779 compute_inline_parameters_for_current
,/* execute */
1782 0, /* static_pass_number */
1783 TV_INLINE_HEURISTICS
, /* tv_id */
1784 0, /* properties_required */
1785 0, /* properties_provided */
1786 0, /* properties_destroyed */
1787 0, /* todo_flags_start */
1788 0 /* todo_flags_finish */
1793 /* Increase SIZE and TIME for size and time needed to handle edge E. */
1796 estimate_edge_size_and_time (struct cgraph_edge
*e
, int *size
, int *time
)
1798 struct inline_edge_summary
*es
= inline_edge_summary (e
);
1799 *size
+= es
->call_stmt_size
* INLINE_SIZE_SCALE
;
1800 *time
+= (es
->call_stmt_time
1801 * e
->frequency
* (INLINE_TIME_SCALE
/ CGRAPH_FREQ_BASE
));
1802 if (*time
> MAX_TIME
* INLINE_TIME_SCALE
)
1803 *time
= MAX_TIME
* INLINE_TIME_SCALE
;
1807 /* Increase SIZE and TIME for size and time needed to handle all calls in NODE. */
1810 estimate_calls_size_and_time (struct cgraph_node
*node
, int *size
, int *time
,
1811 clause_t possible_truths
)
1813 struct cgraph_edge
*e
;
1814 for (e
= node
->callees
; e
; e
= e
->next_callee
)
1816 struct inline_edge_summary
*es
= inline_edge_summary (e
);
1817 if (!es
->predicate
|| evaluate_predicate (es
->predicate
, possible_truths
))
1819 if (e
->inline_failed
)
1820 estimate_edge_size_and_time (e
, size
, time
);
1822 estimate_calls_size_and_time (e
->callee
, size
, time
,
1826 /* TODO: look for devirtualizing oppurtunities. */
1827 for (e
= node
->indirect_calls
; e
; e
= e
->next_callee
)
1829 struct inline_edge_summary
*es
= inline_edge_summary (e
);
1830 if (!es
->predicate
|| evaluate_predicate (es
->predicate
, possible_truths
))
1831 estimate_edge_size_and_time (e
, size
, time
);
1836 /* Estimate size and time needed to execute NODE assuming
1837 POSSIBLE_TRUTHS clause. */
1840 estimate_node_size_and_time (struct cgraph_node
*node
,
1841 clause_t possible_truths
,
1842 int *ret_size
, int *ret_time
)
1844 struct inline_summary
*info
= inline_summary (node
);
1846 int size
= 0, time
= 0;
1850 && (dump_flags
& TDF_DETAILS
))
1853 fprintf (dump_file
, " Estimating body: %s/%i\n"
1854 " Known to be false: ",
1855 cgraph_node_name (node
),
1858 for (i
= predicate_not_inlined_condition
;
1859 i
< (predicate_first_dynamic_condition
1860 + (int)VEC_length (condition
, info
->conds
)); i
++)
1861 if (!(possible_truths
& (1 << i
)))
1864 fprintf (dump_file
, ", ");
1866 dump_condition (dump_file
, info
->conds
, i
);
1870 for (i
= 0; VEC_iterate (size_time_entry
, info
->entry
, i
, e
); i
++)
1871 if (evaluate_predicate (&e
->predicate
, possible_truths
))
1872 time
+= e
->time
, size
+= e
->size
;
1874 if (time
> MAX_TIME
* INLINE_TIME_SCALE
)
1875 time
= MAX_TIME
* INLINE_TIME_SCALE
;
1877 estimate_calls_size_and_time (node
, &size
, &time
, possible_truths
);
1878 time
= (time
+ INLINE_TIME_SCALE
/ 2) / INLINE_TIME_SCALE
;
1879 size
= (size
+ INLINE_SIZE_SCALE
/ 2) / INLINE_SIZE_SCALE
;
1883 && (dump_flags
& TDF_DETAILS
))
1884 fprintf (dump_file
, "\n size:%i time:%i\n", size
, time
);
1893 /* Estimate size and time needed to execute callee of EDGE assuming that
1894 parameters known to be constant at caller of EDGE are propagated.
1895 KNOWN_VALs is a vector of assumed known constant values for parameters. */
1898 estimate_ipcp_clone_size_and_time (struct cgraph_node
*node
,
1899 VEC (tree
, heap
) *known_vals
,
1900 int *ret_size
, int *ret_time
)
1904 clause
= evaluate_conditions_for_known_args (node
, false, known_vals
);
1905 estimate_node_size_and_time (node
, clause
, ret_size
, ret_time
);
1909 /* Translate all conditions from callee representation into caller representation and
1910 symbolically evaluate predicate P into new predicate.
1912 INFO is inline_summary of function we are adding predicate into, CALLEE_INFO is summary
1913 of function predicate P is from. OPERAND_MAP is array giving callee formal IDs the
1914 caller formal IDs. POSSSIBLE_TRUTHS is clausule of all callee conditions that
1915 may be true in caller context. TOPLEV_PREDICATE is predicate under which callee
1918 static struct predicate
1919 remap_predicate (struct inline_summary
*info
, struct inline_summary
*callee_info
,
1920 struct predicate
*p
,
1921 VEC (int, heap
) *operand_map
,
1922 clause_t possible_truths
,
1923 struct predicate
*toplev_predicate
)
1926 struct predicate out
= true_predicate ();
1928 /* True predicate is easy. */
1929 if (true_predicate_p (p
))
1930 return *toplev_predicate
;
1931 for (i
= 0; p
->clause
[i
]; i
++)
1933 clause_t clause
= p
->clause
[i
];
1935 struct predicate clause_predicate
= false_predicate ();
1937 gcc_assert (i
< MAX_CLAUSES
);
1939 for (cond
= 0; cond
< NUM_CONDITIONS
; cond
++)
1940 /* Do we have condition we can't disprove? */
1941 if (clause
& possible_truths
& (1 << cond
))
1943 struct predicate cond_predicate
;
1944 /* Work out if the condition can translate to predicate in the
1945 inlined function. */
1946 if (cond
>= predicate_first_dynamic_condition
)
1948 struct condition
*c
;
1950 c
= VEC_index (condition
, callee_info
->conds
,
1951 cond
- predicate_first_dynamic_condition
);
1952 /* See if we can remap condition operand to caller's operand.
1953 Otherwise give up. */
1955 || (int)VEC_length (int, operand_map
) <= c
->operand_num
1956 || VEC_index (int, operand_map
, c
->operand_num
) == -1)
1957 cond_predicate
= true_predicate ();
1959 cond_predicate
= add_condition (info
,
1960 VEC_index (int, operand_map
,
1964 /* Fixed conditions remains same, construct single
1965 condition predicate. */
1968 cond_predicate
.clause
[0] = 1 << cond
;
1969 cond_predicate
.clause
[1] = 0;
1971 clause_predicate
= or_predicates (info
->conds
, &clause_predicate
,
1974 out
= and_predicates (info
->conds
, &out
, &clause_predicate
);
1976 return and_predicates (info
->conds
, &out
, toplev_predicate
);
1980 /* Update summary information of inline clones after inlining.
1981 Compute peak stack usage. */
1984 inline_update_callee_summaries (struct cgraph_node
*node
,
1987 struct cgraph_edge
*e
;
1988 struct inline_summary
*callee_info
= inline_summary (node
);
1989 struct inline_summary
*caller_info
= inline_summary (node
->callers
->caller
);
1992 callee_info
->stack_frame_offset
1993 = caller_info
->stack_frame_offset
1994 + caller_info
->estimated_self_stack_size
;
1995 peak
= callee_info
->stack_frame_offset
1996 + callee_info
->estimated_self_stack_size
;
1997 if (inline_summary (node
->global
.inlined_to
)->estimated_stack_size
1999 inline_summary (node
->global
.inlined_to
)->estimated_stack_size
= peak
;
2000 cgraph_propagate_frequency (node
);
2001 for (e
= node
->callees
; e
; e
= e
->next_callee
)
2003 if (!e
->inline_failed
)
2004 inline_update_callee_summaries (e
->callee
, depth
);
2005 inline_edge_summary (e
)->loop_depth
+= depth
;
2007 for (e
= node
->indirect_calls
; e
; e
= e
->next_callee
)
2008 inline_edge_summary (e
)->loop_depth
+= depth
;
2012 /* Remap predicates of callees of NODE. Rest of arguments match
2016 remap_edge_predicates (struct cgraph_node
*node
,
2017 struct inline_summary
*info
,
2018 struct inline_summary
*callee_info
,
2019 VEC (int, heap
) *operand_map
,
2020 clause_t possible_truths
,
2021 struct predicate
*toplev_predicate
)
2023 struct cgraph_edge
*e
;
2024 for (e
= node
->callees
; e
; e
= e
->next_callee
)
2026 struct inline_edge_summary
*es
= inline_edge_summary (e
);
2030 p
= remap_predicate (info
, callee_info
,
2031 es
->predicate
, operand_map
, possible_truths
,
2033 edge_set_predicate (e
, &p
);
2034 /* TODO: We should remove the edge for code that will be optimized out,
2035 but we need to keep verifiers and tree-inline happy.
2036 Make it cold for now. */
2037 if (false_predicate_p (&p
))
2043 if (!e
->inline_failed
)
2044 remap_edge_predicates (e
->callee
, info
, callee_info
, operand_map
,
2045 possible_truths
, toplev_predicate
);
2047 edge_set_predicate (e
, toplev_predicate
);
2049 for (e
= node
->indirect_calls
; e
; e
= e
->next_callee
)
2051 struct inline_edge_summary
*es
= inline_edge_summary (e
);
2055 p
= remap_predicate (info
, callee_info
,
2056 es
->predicate
, operand_map
, possible_truths
,
2058 edge_set_predicate (e
, &p
);
2059 /* TODO: We should remove the edge for code that will be optimized out,
2060 but we need to keep verifiers and tree-inline happy.
2061 Make it cold for now. */
2062 if (false_predicate_p (&p
))
2069 edge_set_predicate (e
, toplev_predicate
);
2074 /* We inlined EDGE. Update summary of the function we inlined into. */
2077 inline_merge_summary (struct cgraph_edge
*edge
)
2079 struct inline_summary
*callee_info
= inline_summary (edge
->callee
);
2080 struct cgraph_node
*to
= (edge
->caller
->global
.inlined_to
2081 ? edge
->caller
->global
.inlined_to
: edge
->caller
);
2082 struct inline_summary
*info
= inline_summary (to
);
2083 clause_t clause
= 0; /* not_inline is known to be false. */
2085 VEC (int, heap
) *operand_map
= NULL
;
2087 struct predicate toplev_predicate
;
2088 struct inline_edge_summary
*es
= inline_edge_summary (edge
);
2091 toplev_predicate
= *es
->predicate
;
2093 toplev_predicate
= true_predicate ();
2095 if (ipa_node_params_vector
&& callee_info
->conds
2096 /* FIXME: it seems that we forget to get argument count in some cases,
2097 probaby for previously indirect edges or so.
2098 Removing the test leads to ICE on tramp3d. */
2099 && ipa_get_cs_argument_count (IPA_EDGE_REF (edge
)))
2101 struct ipa_edge_args
*args
= IPA_EDGE_REF (edge
);
2102 int count
= ipa_get_cs_argument_count (args
);
2105 clause
= evaluate_conditions_for_edge (edge
, true);
2106 VEC_safe_grow_cleared (int, heap
, operand_map
, count
);
2107 for (i
= 0; i
< count
; i
++)
2109 struct ipa_jump_func
*jfunc
= ipa_get_ith_jump_func (args
, i
);
2111 /* TODO: handle non-NOPs when merging. */
2112 if (jfunc
->type
== IPA_JF_PASS_THROUGH
2113 && jfunc
->value
.pass_through
.operation
== NOP_EXPR
)
2114 map
= jfunc
->value
.pass_through
.formal_id
;
2115 VEC_replace (int, operand_map
, i
, map
);
2116 gcc_assert (map
< ipa_get_param_count (IPA_NODE_REF (to
)));
2119 for (i
= 0; VEC_iterate (size_time_entry
, callee_info
->entry
, i
, e
); i
++)
2121 struct predicate p
= remap_predicate (info
, callee_info
,
2122 &e
->predicate
, operand_map
, clause
,
2124 gcov_type add_time
= ((gcov_type
)e
->time
* edge
->frequency
2125 + CGRAPH_FREQ_BASE
/ 2) / CGRAPH_FREQ_BASE
;
2126 if (add_time
> MAX_TIME
)
2127 add_time
= MAX_TIME
;
2128 account_size_time (info
, e
->size
, add_time
, &p
);
2130 remap_edge_predicates (edge
->callee
, info
, callee_info
, operand_map
,
2131 clause
, &toplev_predicate
);
2134 for (i
= 0; VEC_iterate (size_time_entry
, info
->entry
, i
, e
); i
++)
2135 info
->size
+= e
->size
, info
->time
+= e
->time
;
2136 estimate_calls_size_and_time (to
, &info
->size
, &info
->time
,
2137 ~(clause_t
)(1 << predicate_false_condition
));
2139 inline_update_callee_summaries (edge
->callee
,
2140 inline_edge_summary (edge
)->loop_depth
);
2142 info
->time
= (info
->time
+ INLINE_TIME_SCALE
/ 2) / INLINE_TIME_SCALE
;
2143 info
->size
= (info
->size
+ INLINE_SIZE_SCALE
/ 2) / INLINE_SIZE_SCALE
;
2147 /* Estimate the time cost for the caller when inlining EDGE.
2148 Only to be called via estimate_edge_time, that handles the
2151 When caching, also update the cache entry. Compute both time and
2152 size, since we always need both metrics eventually. */
2155 do_estimate_edge_time (struct cgraph_edge
*edge
)
2160 struct inline_edge_summary
*es
= inline_edge_summary (edge
);
2162 gcc_checking_assert (edge
->inline_failed
);
2163 estimate_node_size_and_time (cgraph_function_or_thunk_node (edge
->callee
, NULL
),
2164 evaluate_conditions_for_edge (edge
, true),
2167 ret
= (((gcov_type
)time
2168 - es
->call_stmt_time
) * edge
->frequency
2169 + CGRAPH_FREQ_BASE
/ 2) / CGRAPH_FREQ_BASE
;
2171 /* When caching, update the cache entry. */
2172 if (edge_growth_cache
)
2175 if ((int)VEC_length (edge_growth_cache_entry
, edge_growth_cache
)
2177 VEC_safe_grow_cleared (edge_growth_cache_entry
, heap
, edge_growth_cache
,
2178 cgraph_edge_max_uid
);
2179 VEC_index (edge_growth_cache_entry
, edge_growth_cache
, edge
->uid
)->time
2182 ret_size
= size
- es
->call_stmt_size
;
2183 gcc_checking_assert (es
->call_stmt_size
);
2184 VEC_index (edge_growth_cache_entry
, edge_growth_cache
, edge
->uid
)->size
2185 = ret_size
+ (ret_size
>= 0);
2191 /* Estimate the growth of the caller when inlining EDGE.
2192 Only to be called via estimate_edge_size. */
2195 do_estimate_edge_growth (struct cgraph_edge
*edge
)
2198 struct cgraph_node
*callee
;
2200 /* When we do caching, use do_estimate_edge_time to populate the entry. */
2202 if (edge_growth_cache
)
2204 do_estimate_edge_time (edge
);
2205 size
= VEC_index (edge_growth_cache_entry
,
2208 gcc_checking_assert (size
);
2209 return size
- (size
> 0);
2211 callee
= cgraph_function_or_thunk_node (edge
->callee
, NULL
);
2213 /* Early inliner runs without caching, go ahead and do the dirty work. */
2214 gcc_checking_assert (edge
->inline_failed
);
2215 estimate_node_size_and_time (callee
,
2216 evaluate_conditions_for_edge (edge
, true),
2218 gcc_checking_assert (inline_edge_summary (edge
)->call_stmt_size
);
2219 return size
- inline_edge_summary (edge
)->call_stmt_size
;
2223 /* Estimate self time of the function NODE after inlining EDGE. */
2226 estimate_time_after_inlining (struct cgraph_node
*node
,
2227 struct cgraph_edge
*edge
)
2229 struct inline_edge_summary
*es
= inline_edge_summary (edge
);
2230 if (!es
->predicate
|| !false_predicate_p (es
->predicate
))
2232 gcov_type time
= inline_summary (node
)->time
+ estimate_edge_time (edge
);
2235 if (time
> MAX_TIME
)
2239 return inline_summary (node
)->time
;
2243 /* Estimate the size of NODE after inlining EDGE which should be an
2244 edge to either NODE or a call inlined into NODE. */
2247 estimate_size_after_inlining (struct cgraph_node
*node
,
2248 struct cgraph_edge
*edge
)
2250 struct inline_edge_summary
*es
= inline_edge_summary (edge
);
2251 if (!es
->predicate
|| !false_predicate_p (es
->predicate
))
2253 int size
= inline_summary (node
)->size
+ estimate_edge_growth (edge
);
2254 gcc_assert (size
>= 0);
2257 return inline_summary (node
)->size
;
2263 bool self_recursive
;
2268 /* Worker for do_estimate_growth. Collect growth for all callers. */
2271 do_estimate_growth_1 (struct cgraph_node
*node
, void *data
)
2273 struct cgraph_edge
*e
;
2274 struct growth_data
*d
= (struct growth_data
*) data
;
2276 for (e
= node
->callers
; e
; e
= e
->next_caller
)
2278 gcc_checking_assert (e
->inline_failed
);
2280 if (e
->caller
== node
2281 || (e
->caller
->global
.inlined_to
2282 && e
->caller
->global
.inlined_to
== node
))
2283 d
->self_recursive
= true;
2284 d
->growth
+= estimate_edge_growth (e
);
2290 /* Estimate the growth caused by inlining NODE into all callees. */
2293 do_estimate_growth (struct cgraph_node
*node
)
2295 struct growth_data d
= {0, false};
2296 struct inline_summary
*info
= inline_summary (node
);
2298 cgraph_for_node_and_aliases (node
, do_estimate_growth_1
, &d
, true);
2300 /* For self recursive functions the growth estimation really should be
2301 infinity. We don't want to return very large values because the growth
2302 plays various roles in badness computation fractions. Be sure to not
2303 return zero or negative growths. */
2304 if (d
.self_recursive
)
2305 d
.growth
= d
.growth
< info
->size
? info
->size
: d
.growth
;
2308 if (!DECL_EXTERNAL (node
->decl
)
2309 && cgraph_will_be_removed_from_program_if_no_direct_calls (node
))
2310 d
.growth
-= info
->size
;
2311 /* COMDAT functions are very often not shared across multiple units since they
2312 come from various template instantiations. Take this into account. */
2313 else if (DECL_COMDAT (node
->decl
)
2314 && cgraph_can_remove_if_no_direct_calls_p (node
))
2315 d
.growth
-= (info
->size
2316 * (100 - PARAM_VALUE (PARAM_COMDAT_SHARING_PROBABILITY
)) + 50) / 100;
2319 if (node_growth_cache
)
2321 if ((int)VEC_length (int, node_growth_cache
) <= node
->uid
)
2322 VEC_safe_grow_cleared (int, heap
, node_growth_cache
, cgraph_max_uid
);
2323 VEC_replace (int, node_growth_cache
, node
->uid
, d
.growth
+ (d
.growth
>= 0));
2329 /* This function performs intraprocedural analysis in NODE that is required to
2330 inline indirect calls. */
2333 inline_indirect_intraprocedural_analysis (struct cgraph_node
*node
)
2335 ipa_analyze_node (node
);
2336 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2338 ipa_print_node_params (dump_file
, node
);
2339 ipa_print_node_jump_functions (dump_file
, node
);
2344 /* Note function body size. */
2347 inline_analyze_function (struct cgraph_node
*node
)
2349 push_cfun (DECL_STRUCT_FUNCTION (node
->decl
));
2350 current_function_decl
= node
->decl
;
2353 fprintf (dump_file
, "\nAnalyzing function: %s/%u\n",
2354 cgraph_node_name (node
), node
->uid
);
2355 /* FIXME: We should remove the optimize check after we ensure we never run
2356 IPA passes when not optimizing. */
2357 if (flag_indirect_inlining
&& optimize
&& !node
->thunk
.thunk_p
)
2358 inline_indirect_intraprocedural_analysis (node
);
2359 compute_inline_parameters (node
, false);
2361 current_function_decl
= NULL
;
2366 /* Called when new function is inserted to callgraph late. */
2369 add_new_function (struct cgraph_node
*node
, void *data ATTRIBUTE_UNUSED
)
2371 inline_analyze_function (node
);
2375 /* Note function body size. */
2378 inline_generate_summary (void)
2380 struct cgraph_node
*node
;
2382 function_insertion_hook_holder
=
2383 cgraph_add_function_insertion_hook (&add_new_function
, NULL
);
2385 if (flag_indirect_inlining
)
2386 ipa_register_cgraph_hooks ();
2388 FOR_EACH_DEFINED_FUNCTION (node
)
2390 inline_analyze_function (node
);
2394 /* Read predicate from IB. */
2396 static struct predicate
2397 read_predicate (struct lto_input_block
*ib
)
2399 struct predicate out
;
2405 gcc_assert (k
<= MAX_CLAUSES
);
2406 clause
= out
.clause
[k
++] = streamer_read_uhwi (ib
);
2410 /* Zero-initialize the remaining clauses in OUT. */
2411 while (k
<= MAX_CLAUSES
)
2412 out
.clause
[k
++] = 0;
2418 /* Write inline summary for edge E to OB. */
2421 read_inline_edge_summary (struct lto_input_block
*ib
, struct cgraph_edge
*e
)
2423 struct inline_edge_summary
*es
= inline_edge_summary (e
);
2426 es
->call_stmt_size
= streamer_read_uhwi (ib
);
2427 es
->call_stmt_time
= streamer_read_uhwi (ib
);
2428 es
->loop_depth
= streamer_read_uhwi (ib
);
2429 p
= read_predicate (ib
);
2430 edge_set_predicate (e
, &p
);
2434 /* Stream in inline summaries from the section. */
2437 inline_read_section (struct lto_file_decl_data
*file_data
, const char *data
,
2440 const struct lto_function_header
*header
=
2441 (const struct lto_function_header
*) data
;
2442 const int32_t cfg_offset
= sizeof (struct lto_function_header
);
2443 const int32_t main_offset
= cfg_offset
+ header
->cfg_size
;
2444 const int32_t string_offset
= main_offset
+ header
->main_size
;
2445 struct data_in
*data_in
;
2446 struct lto_input_block ib
;
2447 unsigned int i
, count2
, j
;
2448 unsigned int f_count
;
2450 LTO_INIT_INPUT_BLOCK (ib
, (const char *) data
+ main_offset
, 0,
2454 lto_data_in_create (file_data
, (const char *) data
+ string_offset
,
2455 header
->string_size
, NULL
);
2456 f_count
= streamer_read_uhwi (&ib
);
2457 for (i
= 0; i
< f_count
; i
++)
2460 struct cgraph_node
*node
;
2461 struct inline_summary
*info
;
2462 lto_cgraph_encoder_t encoder
;
2463 struct bitpack_d bp
;
2464 struct cgraph_edge
*e
;
2466 index
= streamer_read_uhwi (&ib
);
2467 encoder
= file_data
->cgraph_node_encoder
;
2468 node
= lto_cgraph_encoder_deref (encoder
, index
);
2469 info
= inline_summary (node
);
2471 info
->estimated_stack_size
2472 = info
->estimated_self_stack_size
= streamer_read_uhwi (&ib
);
2473 info
->size
= info
->self_size
= streamer_read_uhwi (&ib
);
2474 info
->time
= info
->self_time
= streamer_read_uhwi (&ib
);
2476 bp
= streamer_read_bitpack (&ib
);
2477 info
->inlinable
= bp_unpack_value (&bp
, 1);
2479 count2
= streamer_read_uhwi (&ib
);
2480 gcc_assert (!info
->conds
);
2481 for (j
= 0; j
< count2
; j
++)
2484 c
.operand_num
= streamer_read_uhwi (&ib
);
2485 c
.code
= (enum tree_code
) streamer_read_uhwi (&ib
);
2486 c
.val
= stream_read_tree (&ib
, data_in
);
2487 VEC_safe_push (condition
, gc
, info
->conds
, &c
);
2489 count2
= streamer_read_uhwi (&ib
);
2490 gcc_assert (!info
->entry
);
2491 for (j
= 0; j
< count2
; j
++)
2493 struct size_time_entry e
;
2495 e
.size
= streamer_read_uhwi (&ib
);
2496 e
.time
= streamer_read_uhwi (&ib
);
2497 e
.predicate
= read_predicate (&ib
);
2499 VEC_safe_push (size_time_entry
, gc
, info
->entry
, &e
);
2501 for (e
= node
->callees
; e
; e
= e
->next_callee
)
2502 read_inline_edge_summary (&ib
, e
);
2503 for (e
= node
->indirect_calls
; e
; e
= e
->next_callee
)
2504 read_inline_edge_summary (&ib
, e
);
2507 lto_free_section_data (file_data
, LTO_section_inline_summary
, NULL
, data
,
2509 lto_data_in_delete (data_in
);
2513 /* Read inline summary. Jump functions are shared among ipa-cp
2514 and inliner, so when ipa-cp is active, we don't need to write them
2518 inline_read_summary (void)
2520 struct lto_file_decl_data
**file_data_vec
= lto_get_file_decl_data ();
2521 struct lto_file_decl_data
*file_data
;
2524 inline_summary_alloc ();
2526 while ((file_data
= file_data_vec
[j
++]))
2529 const char *data
= lto_get_section_data (file_data
, LTO_section_inline_summary
, NULL
, &len
);
2531 inline_read_section (file_data
, data
, len
);
2533 /* Fatal error here. We do not want to support compiling ltrans units with
2534 different version of compiler or different flags than the WPA unit, so
2535 this should never happen. */
2536 fatal_error ("ipa inline summary is missing in input file");
2538 if (flag_indirect_inlining
)
2540 ipa_register_cgraph_hooks ();
2542 ipa_prop_read_jump_functions ();
2544 function_insertion_hook_holder
=
2545 cgraph_add_function_insertion_hook (&add_new_function
, NULL
);
2549 /* Write predicate P to OB. */
2552 write_predicate (struct output_block
*ob
, struct predicate
*p
)
2556 for (j
= 0; p
->clause
[j
]; j
++)
2558 gcc_assert (j
< MAX_CLAUSES
);
2559 streamer_write_uhwi (ob
, p
->clause
[j
]);
2561 streamer_write_uhwi (ob
, 0);
2565 /* Write inline summary for edge E to OB. */
2568 write_inline_edge_summary (struct output_block
*ob
, struct cgraph_edge
*e
)
2570 struct inline_edge_summary
*es
= inline_edge_summary (e
);
2571 streamer_write_uhwi (ob
, es
->call_stmt_size
);
2572 streamer_write_uhwi (ob
, es
->call_stmt_time
);
2573 streamer_write_uhwi (ob
, es
->loop_depth
);
2574 write_predicate (ob
, es
->predicate
);
2578 /* Write inline summary for node in SET.
2579 Jump functions are shared among ipa-cp and inliner, so when ipa-cp is
2580 active, we don't need to write them twice. */
2583 inline_write_summary (cgraph_node_set set
,
2584 varpool_node_set vset ATTRIBUTE_UNUSED
)
2586 struct cgraph_node
*node
;
2587 struct output_block
*ob
= create_output_block (LTO_section_inline_summary
);
2588 lto_cgraph_encoder_t encoder
= ob
->decl_state
->cgraph_node_encoder
;
2589 unsigned int count
= 0;
2592 for (i
= 0; i
< lto_cgraph_encoder_size (encoder
); i
++)
2593 if (lto_cgraph_encoder_deref (encoder
, i
)->analyzed
)
2595 streamer_write_uhwi (ob
, count
);
2597 for (i
= 0; i
< lto_cgraph_encoder_size (encoder
); i
++)
2599 node
= lto_cgraph_encoder_deref (encoder
, i
);
2602 struct inline_summary
*info
= inline_summary (node
);
2603 struct bitpack_d bp
;
2604 struct cgraph_edge
*edge
;
2607 struct condition
*c
;
2609 streamer_write_uhwi (ob
, lto_cgraph_encoder_encode (encoder
, node
));
2610 streamer_write_hwi (ob
, info
->estimated_self_stack_size
);
2611 streamer_write_hwi (ob
, info
->self_size
);
2612 streamer_write_hwi (ob
, info
->self_time
);
2613 bp
= bitpack_create (ob
->main_stream
);
2614 bp_pack_value (&bp
, info
->inlinable
, 1);
2615 streamer_write_bitpack (&bp
);
2616 streamer_write_uhwi (ob
, VEC_length (condition
, info
->conds
));
2617 for (i
= 0; VEC_iterate (condition
, info
->conds
, i
, c
); i
++)
2619 streamer_write_uhwi (ob
, c
->operand_num
);
2620 streamer_write_uhwi (ob
, c
->code
);
2621 stream_write_tree (ob
, c
->val
, true);
2623 streamer_write_uhwi (ob
, VEC_length (size_time_entry
, info
->entry
));
2625 VEC_iterate (size_time_entry
, info
->entry
, i
, e
);
2628 streamer_write_uhwi (ob
, e
->size
);
2629 streamer_write_uhwi (ob
, e
->time
);
2630 write_predicate (ob
, &e
->predicate
);
2632 for (edge
= node
->callees
; edge
; edge
= edge
->next_callee
)
2633 write_inline_edge_summary (ob
, edge
);
2634 for (edge
= node
->indirect_calls
; edge
; edge
= edge
->next_callee
)
2635 write_inline_edge_summary (ob
, edge
);
2638 streamer_write_char_stream (ob
->main_stream
, 0);
2639 produce_asm (ob
, NULL
);
2640 destroy_output_block (ob
);
2642 if (flag_indirect_inlining
&& !flag_ipa_cp
)
2643 ipa_prop_write_jump_functions (set
);
2647 /* Release inline summary. */
2650 inline_free_summary (void)
2652 if (function_insertion_hook_holder
)
2653 cgraph_remove_function_insertion_hook (function_insertion_hook_holder
);
2654 function_insertion_hook_holder
= NULL
;
2655 if (node_removal_hook_holder
)
2656 cgraph_remove_node_removal_hook (node_removal_hook_holder
);
2657 if (edge_removal_hook_holder
)
2658 cgraph_remove_edge_removal_hook (edge_removal_hook_holder
);
2659 node_removal_hook_holder
= NULL
;
2660 if (node_duplication_hook_holder
)
2661 cgraph_remove_node_duplication_hook (node_duplication_hook_holder
);
2662 if (edge_duplication_hook_holder
)
2663 cgraph_remove_edge_duplication_hook (edge_duplication_hook_holder
);
2664 node_duplication_hook_holder
= NULL
;
2665 VEC_free (inline_summary_t
, gc
, inline_summary_vec
);
2666 inline_summary_vec
= NULL
;
2667 VEC_free (inline_edge_summary_t
, heap
, inline_edge_summary_vec
);
2668 inline_edge_summary_vec
= NULL
;
2669 if (edge_predicate_pool
)
2670 free_alloc_pool (edge_predicate_pool
);
2671 edge_predicate_pool
= 0;