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
)
624 struct ipa_node_params
*parms_info
;
625 struct ipa_edge_args
*args
= IPA_EDGE_REF (e
);
626 int i
, count
= ipa_get_cs_argument_count (args
);
627 VEC (tree
, heap
) *known_vals
= NULL
;
629 if (e
->caller
->global
.inlined_to
)
630 parms_info
= IPA_NODE_REF (e
->caller
->global
.inlined_to
);
632 parms_info
= IPA_NODE_REF (e
->caller
);
635 VEC_safe_grow_cleared (tree
, heap
, known_vals
, count
);
636 for (i
= 0; i
< count
; i
++)
638 tree cst
= ipa_cst_from_jfunc (parms_info
,
639 ipa_get_ith_jump_func (args
, i
));
641 VEC_replace (tree
, known_vals
, i
, cst
);
643 clause
= evaluate_conditions_for_known_args (callee
,
644 inline_p
, known_vals
);
645 VEC_free (tree
, heap
, known_vals
);
648 for (i
= 0; i
< (int)VEC_length (condition
, info
->conds
); i
++)
649 clause
|= 1 << (i
+ predicate_first_dynamic_condition
);
655 /* Allocate the inline summary vector or resize it to cover all cgraph nodes. */
658 inline_summary_alloc (void)
660 if (!node_removal_hook_holder
)
661 node_removal_hook_holder
=
662 cgraph_add_node_removal_hook (&inline_node_removal_hook
, NULL
);
663 if (!edge_removal_hook_holder
)
664 edge_removal_hook_holder
=
665 cgraph_add_edge_removal_hook (&inline_edge_removal_hook
, NULL
);
666 if (!node_duplication_hook_holder
)
667 node_duplication_hook_holder
=
668 cgraph_add_node_duplication_hook (&inline_node_duplication_hook
, NULL
);
669 if (!edge_duplication_hook_holder
)
670 edge_duplication_hook_holder
=
671 cgraph_add_edge_duplication_hook (&inline_edge_duplication_hook
, NULL
);
673 if (VEC_length (inline_summary_t
, inline_summary_vec
)
674 <= (unsigned) cgraph_max_uid
)
675 VEC_safe_grow_cleared (inline_summary_t
, gc
,
676 inline_summary_vec
, cgraph_max_uid
+ 1);
677 if (VEC_length (inline_edge_summary_t
, inline_edge_summary_vec
)
678 <= (unsigned) cgraph_edge_max_uid
)
679 VEC_safe_grow_cleared (inline_edge_summary_t
, heap
,
680 inline_edge_summary_vec
, cgraph_edge_max_uid
+ 1);
681 if (!edge_predicate_pool
)
682 edge_predicate_pool
= create_alloc_pool ("edge predicates", sizeof (struct predicate
),
686 /* Hook that is called by cgraph.c when a node is removed. */
689 inline_node_removal_hook (struct cgraph_node
*node
, void *data ATTRIBUTE_UNUSED
)
691 struct inline_summary
*info
;
692 if (VEC_length (inline_summary_t
, inline_summary_vec
)
693 <= (unsigned)node
->uid
)
695 info
= inline_summary (node
);
696 reset_node_growth_cache (node
);
697 VEC_free (condition
, gc
, info
->conds
);
698 VEC_free (size_time_entry
, gc
, info
->entry
);
701 memset (info
, 0, sizeof (inline_summary_t
));
705 /* Hook that is called by cgraph.c when a node is duplicated. */
708 inline_node_duplication_hook (struct cgraph_node
*src
, struct cgraph_node
*dst
,
709 ATTRIBUTE_UNUSED
void *data
)
711 struct inline_summary
*info
;
712 inline_summary_alloc ();
713 info
= inline_summary (dst
);
714 memcpy (info
, inline_summary (src
),
715 sizeof (struct inline_summary
));
716 /* TODO: as an optimization, we may avoid copying conditions
717 that are known to be false or true. */
718 info
->conds
= VEC_copy (condition
, gc
, info
->conds
);
720 /* When there are any replacements in the function body, see if we can figure
721 out that something was optimized out. */
722 if (ipa_node_params_vector
&& dst
->clone
.tree_map
)
724 VEC(size_time_entry
,gc
) *entry
= info
->entry
;
725 /* Use SRC parm info since it may not be copied yet. */
726 struct ipa_node_params
*parms_info
= IPA_NODE_REF (src
);
727 VEC (tree
, heap
) *known_vals
= NULL
;
728 int count
= ipa_get_param_count (parms_info
);
730 clause_t possible_truths
;
731 struct predicate true_pred
= true_predicate ();
733 int optimized_out_size
= 0;
734 gcov_type optimized_out_time
= 0;
735 bool inlined_to_p
= false;
736 struct cgraph_edge
*edge
;
739 VEC_safe_grow_cleared (tree
, heap
, known_vals
, count
);
740 for (i
= 0; i
< count
; i
++)
742 tree t
= ipa_get_param (parms_info
, i
);
743 struct ipa_replace_map
*r
;
746 VEC_iterate (ipa_replace_map_p
, dst
->clone
.tree_map
, j
, r
);
753 VEC_replace (tree
, known_vals
, i
, r
->new_tree
);
758 possible_truths
= evaluate_conditions_for_known_args (dst
,
760 VEC_free (tree
, heap
, known_vals
);
762 account_size_time (info
, 0, 0, &true_pred
);
764 /* Remap size_time vectors.
765 Simplify the predicate by prunning out alternatives that are known
767 TODO: as on optimization, we can also eliminate conditions known to be true. */
768 for (i
= 0; VEC_iterate (size_time_entry
, entry
, i
, e
); i
++)
770 struct predicate new_predicate
= true_predicate ();
771 for (j
= 0; e
->predicate
.clause
[j
]; j
++)
772 if (!(possible_truths
& e
->predicate
.clause
[j
]))
774 new_predicate
= false_predicate ();
778 add_clause (info
->conds
, &new_predicate
,
779 possible_truths
& e
->predicate
.clause
[j
]);
780 if (false_predicate_p (&new_predicate
))
782 optimized_out_size
+= e
->size
;
783 optimized_out_time
+= e
->time
;
786 account_size_time (info
, e
->size
, e
->time
, &new_predicate
);
789 /* Remap edge predicates with the same simplificaiton as above. */
790 for (edge
= dst
->callees
; edge
; edge
= edge
->next_callee
)
792 struct predicate new_predicate
= true_predicate ();
793 struct inline_edge_summary
*es
= inline_edge_summary (edge
);
795 if (!edge
->inline_failed
)
799 for (j
= 0; es
->predicate
->clause
[j
]; j
++)
800 if (!(possible_truths
& es
->predicate
->clause
[j
]))
802 new_predicate
= false_predicate ();
806 add_clause (info
->conds
, &new_predicate
,
807 possible_truths
& es
->predicate
->clause
[j
]);
808 if (false_predicate_p (&new_predicate
)
809 && !false_predicate_p (es
->predicate
))
811 optimized_out_size
+= es
->call_stmt_size
* INLINE_SIZE_SCALE
;
812 optimized_out_time
+= (es
->call_stmt_time
813 * (INLINE_TIME_SCALE
/ CGRAPH_FREQ_BASE
)
817 *es
->predicate
= new_predicate
;
820 /* Remap indirect edge predicates with the same simplificaiton as above. */
821 for (edge
= dst
->indirect_calls
; edge
; edge
= edge
->next_callee
)
823 struct predicate new_predicate
= true_predicate ();
824 struct inline_edge_summary
*es
= inline_edge_summary (edge
);
826 if (!edge
->inline_failed
)
830 for (j
= 0; es
->predicate
->clause
[j
]; j
++)
831 if (!(possible_truths
& es
->predicate
->clause
[j
]))
833 new_predicate
= false_predicate ();
837 add_clause (info
->conds
, &new_predicate
,
838 possible_truths
& es
->predicate
->clause
[j
]);
839 if (false_predicate_p (&new_predicate
)
840 && !false_predicate_p (es
->predicate
))
842 optimized_out_size
+= es
->call_stmt_size
* INLINE_SIZE_SCALE
;
843 optimized_out_time
+= (es
->call_stmt_time
844 * (INLINE_TIME_SCALE
/ CGRAPH_FREQ_BASE
)
848 *es
->predicate
= new_predicate
;
851 /* If inliner or someone after inliner will ever start producing
852 non-trivial clones, we will get trouble with lack of information
853 about updating self sizes, because size vectors already contains
854 sizes of the calees. */
855 gcc_assert (!inlined_to_p
856 || (!optimized_out_size
&& !optimized_out_time
));
858 info
->size
-= optimized_out_size
/ INLINE_SIZE_SCALE
;
859 info
->self_size
-= optimized_out_size
/ INLINE_SIZE_SCALE
;
860 gcc_assert (info
->size
> 0);
861 gcc_assert (info
->self_size
> 0);
863 optimized_out_time
/= INLINE_TIME_SCALE
;
864 if (optimized_out_time
> MAX_TIME
)
865 optimized_out_time
= MAX_TIME
;
866 info
->time
-= optimized_out_time
;
867 info
->self_time
-= optimized_out_time
;
870 if (info
->self_time
< 0)
874 info
->entry
= VEC_copy (size_time_entry
, gc
, info
->entry
);
878 /* Hook that is called by cgraph.c when a node is duplicated. */
881 inline_edge_duplication_hook (struct cgraph_edge
*src
, struct cgraph_edge
*dst
,
882 ATTRIBUTE_UNUSED
void *data
)
884 struct inline_edge_summary
*info
;
885 struct inline_edge_summary
*srcinfo
;
886 inline_summary_alloc ();
887 info
= inline_edge_summary (dst
);
888 srcinfo
= inline_edge_summary (src
);
889 memcpy (info
, srcinfo
,
890 sizeof (struct inline_edge_summary
));
891 info
->predicate
= NULL
;
892 edge_set_predicate (dst
, srcinfo
->predicate
);
896 /* Keep edge cache consistent across edge removal. */
899 inline_edge_removal_hook (struct cgraph_edge
*edge
, void *data ATTRIBUTE_UNUSED
)
901 if (edge_growth_cache
)
902 reset_edge_growth_cache (edge
);
903 if (edge
->uid
< (int)VEC_length (inline_edge_summary_t
, inline_edge_summary_vec
))
905 edge_set_predicate (edge
, NULL
);
906 memset (inline_edge_summary (edge
), 0, sizeof (struct inline_edge_summary
));
911 /* Initialize growth caches. */
914 initialize_growth_caches (void)
916 if (cgraph_edge_max_uid
)
917 VEC_safe_grow_cleared (edge_growth_cache_entry
, heap
, edge_growth_cache
,
918 cgraph_edge_max_uid
);
920 VEC_safe_grow_cleared (int, heap
, node_growth_cache
, cgraph_max_uid
);
924 /* Free growth caches. */
927 free_growth_caches (void)
929 VEC_free (edge_growth_cache_entry
, heap
, edge_growth_cache
);
930 edge_growth_cache
= 0;
931 VEC_free (int, heap
, node_growth_cache
);
932 node_growth_cache
= 0;
936 /* Dump edge summaries associated to NODE and recursively to all clones.
940 dump_inline_edge_summary (FILE * f
, int indent
, struct cgraph_node
*node
,
941 struct inline_summary
*info
)
943 struct cgraph_edge
*edge
;
944 for (edge
= node
->callees
; edge
; edge
= edge
->next_callee
)
946 struct inline_edge_summary
*es
= inline_edge_summary (edge
);
947 struct cgraph_node
*callee
= cgraph_function_or_thunk_node (edge
->callee
, NULL
);
948 fprintf (f
, "%*s%s/%i %s\n%*s loop depth:%2i freq:%4i size:%2i time: %2i callee size:%2i stack:%2i",
949 indent
, "", cgraph_node_name (callee
),
951 !edge
->inline_failed
? "inlined"
952 : cgraph_inline_failed_string (edge
->inline_failed
),
958 (int)inline_summary (callee
)->size
,
959 (int)inline_summary (callee
)->estimated_stack_size
);
962 fprintf (f
, " predicate: ");
963 dump_predicate (f
, info
->conds
, es
->predicate
);
967 if (!edge
->inline_failed
)
969 fprintf (f
, "%*sStack frame offset %i, callee self size %i, callee size %i\n",
971 (int)inline_summary (callee
)->stack_frame_offset
,
972 (int)inline_summary (callee
)->estimated_self_stack_size
,
973 (int)inline_summary (callee
)->estimated_stack_size
);
974 dump_inline_edge_summary (f
, indent
+2, callee
, info
);
977 for (edge
= node
->indirect_calls
; edge
; edge
= edge
->next_callee
)
979 struct inline_edge_summary
*es
= inline_edge_summary (edge
);
980 fprintf (f
, "%*sindirect call loop depth:%2i freq:%4i size:%2i time: %2i\n",
988 fprintf (f
, "predicate: ");
989 dump_predicate (f
, info
->conds
, es
->predicate
);
998 dump_inline_summary (FILE * f
, struct cgraph_node
*node
)
1002 struct inline_summary
*s
= inline_summary (node
);
1005 fprintf (f
, "Inline summary for %s/%i", cgraph_node_name (node
),
1007 if (DECL_DISREGARD_INLINE_LIMITS (node
->decl
))
1008 fprintf (f
, " always_inline");
1010 fprintf (f
, " inlinable");
1011 fprintf (f
, "\n self time: %i\n",
1013 fprintf (f
, " global time: %i\n", s
->time
);
1014 fprintf (f
, " self size: %i\n",
1016 fprintf (f
, " global size: %i\n", s
->size
);
1017 fprintf (f
, " self stack: %i\n",
1018 (int) s
->estimated_self_stack_size
);
1019 fprintf (f
, " global stack: %i\n",
1020 (int) s
->estimated_stack_size
);
1022 VEC_iterate (size_time_entry
, s
->entry
, i
, e
);
1025 fprintf (f
, " size:%f, time:%f, predicate:",
1026 (double) e
->size
/ INLINE_SIZE_SCALE
,
1027 (double) e
->time
/ INLINE_TIME_SCALE
);
1028 dump_predicate (f
, s
->conds
, &e
->predicate
);
1030 fprintf (f
, " calls:\n");
1031 dump_inline_edge_summary (f
, 4, node
, s
);
1037 debug_inline_summary (struct cgraph_node
*node
)
1039 dump_inline_summary (stderr
, node
);
1043 dump_inline_summaries (FILE *f
)
1045 struct cgraph_node
*node
;
1047 for (node
= cgraph_nodes
; node
; node
= node
->next
)
1048 if (node
->analyzed
&& !node
->global
.inlined_to
)
1049 dump_inline_summary (f
, node
);
1052 /* Give initial reasons why inlining would fail on EDGE. This gets either
1053 nullified or usually overwritten by more precise reasons later. */
1056 initialize_inline_failed (struct cgraph_edge
*e
)
1058 struct cgraph_node
*callee
= e
->callee
;
1060 if (e
->indirect_unknown_callee
)
1061 e
->inline_failed
= CIF_INDIRECT_UNKNOWN_CALL
;
1062 else if (!callee
->analyzed
)
1063 e
->inline_failed
= CIF_BODY_NOT_AVAILABLE
;
1064 else if (callee
->local
.redefined_extern_inline
)
1065 e
->inline_failed
= CIF_REDEFINED_EXTERN_INLINE
;
1066 else if (e
->call_stmt
&& gimple_call_cannot_inline_p (e
->call_stmt
))
1067 e
->inline_failed
= CIF_MISMATCHED_ARGUMENTS
;
1069 e
->inline_failed
= CIF_FUNCTION_NOT_CONSIDERED
;
1072 /* Callback of walk_aliased_vdefs. Flags that it has been invoked to the
1073 boolean variable pointed to by DATA. */
1076 mark_modified (ao_ref
*ao ATTRIBUTE_UNUSED
, tree vdef ATTRIBUTE_UNUSED
,
1079 bool *b
= (bool *) data
;
1084 /* If OP reffers to value of function parameter, return
1085 the corresponding parameter. */
1088 unmodified_parm (gimple stmt
, tree op
)
1090 /* SSA_NAME referring to parm default def? */
1091 if (TREE_CODE (op
) == SSA_NAME
1092 && SSA_NAME_IS_DEFAULT_DEF (op
)
1093 && TREE_CODE (SSA_NAME_VAR (op
)) == PARM_DECL
)
1094 return SSA_NAME_VAR (op
);
1095 /* Non-SSA parm reference? */
1096 if (TREE_CODE (op
) == PARM_DECL
)
1098 bool modified
= false;
1101 ao_ref_init (&refd
, op
);
1102 walk_aliased_vdefs (&refd
, gimple_vuse (stmt
), mark_modified
, &modified
,
1107 /* Assignment from a parameter? */
1108 if (TREE_CODE (op
) == SSA_NAME
1109 && !SSA_NAME_IS_DEFAULT_DEF (op
)
1110 && gimple_assign_single_p (SSA_NAME_DEF_STMT (op
)))
1111 return unmodified_parm (SSA_NAME_DEF_STMT (op
),
1112 gimple_assign_rhs1 (SSA_NAME_DEF_STMT (op
)));
1116 /* See if statement might disappear after inlining.
1117 0 - means not eliminated
1118 1 - half of statements goes away
1119 2 - for sure it is eliminated.
1120 We are not terribly sophisticated, basically looking for simple abstraction
1121 penalty wrappers. */
1124 eliminated_by_inlining_prob (gimple stmt
)
1126 enum gimple_code code
= gimple_code (stmt
);
1136 if (gimple_num_ops (stmt
) != 2)
1139 /* Casts of parameters, loads from parameters passed by reference
1140 and stores to return value or parameters are often free after
1141 inlining dua to SRA and further combining.
1142 Assume that half of statements goes away. */
1143 if (gimple_assign_rhs_code (stmt
) == CONVERT_EXPR
1144 || gimple_assign_rhs_code (stmt
) == NOP_EXPR
1145 || gimple_assign_rhs_code (stmt
) == VIEW_CONVERT_EXPR
1146 || gimple_assign_rhs_class (stmt
) == GIMPLE_SINGLE_RHS
)
1148 tree rhs
= gimple_assign_rhs1 (stmt
);
1149 tree lhs
= gimple_assign_lhs (stmt
);
1150 tree inner_rhs
= get_base_address (rhs
);
1151 tree inner_lhs
= get_base_address (lhs
);
1152 bool rhs_free
= false;
1153 bool lhs_free
= false;
1160 if (unmodified_parm (stmt
, inner_rhs
))
1162 if (rhs_free
&& is_gimple_reg (lhs
))
1164 if (((TREE_CODE (inner_lhs
) == PARM_DECL
1165 || (TREE_CODE (inner_lhs
) == SSA_NAME
1166 && SSA_NAME_IS_DEFAULT_DEF (inner_lhs
)
1167 && TREE_CODE (SSA_NAME_VAR (inner_lhs
)) == PARM_DECL
))
1168 && inner_lhs
!= lhs
)
1169 || TREE_CODE (inner_lhs
) == RESULT_DECL
1170 || (TREE_CODE (inner_lhs
) == SSA_NAME
1171 && TREE_CODE (SSA_NAME_VAR (inner_lhs
)) == RESULT_DECL
))
1174 && (is_gimple_reg (rhs
) || is_gimple_min_invariant (rhs
)))
1176 if (lhs_free
&& rhs_free
)
1186 /* If BB ends by a conditional we can turn into predicates, attach corresponding
1187 predicates to the CFG edges. */
1190 set_cond_stmt_execution_predicate (struct ipa_node_params
*info
,
1191 struct inline_summary
*summary
,
1197 enum tree_code code
, inverted_code
;
1205 last
= last_stmt (bb
);
1207 || gimple_code (last
) != GIMPLE_COND
)
1209 if (!is_gimple_ip_invariant (gimple_cond_rhs (last
)))
1211 op
= gimple_cond_lhs (last
);
1212 /* TODO: handle conditionals like
1215 parm
= unmodified_parm (last
, op
);
1218 index
= ipa_get_param_decl_index (info
, parm
);
1221 code
= gimple_cond_code (last
);
1222 inverted_code
= invert_tree_comparison (code
,
1223 HONOR_NANS (TYPE_MODE (TREE_TYPE (op
))));
1225 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1227 struct predicate p
= add_condition (summary
,
1229 e
->flags
& EDGE_TRUE_VALUE
1230 ? code
: inverted_code
,
1231 gimple_cond_rhs (last
));
1232 e
->aux
= pool_alloc (edge_predicate_pool
);
1233 *(struct predicate
*)e
->aux
= p
;
1237 if (TREE_CODE (op
) != SSA_NAME
)
1240 if (builtin_constant_p (op))
1244 Here we can predicate nonconstant_code. We can't
1245 really handle constant_code since we have no predicate
1246 for this and also the constant code is not known to be
1247 optimized away when inliner doen't see operand is constant.
1248 Other optimizers might think otherwise. */
1249 set_stmt
= SSA_NAME_DEF_STMT (op
);
1250 if (!gimple_call_builtin_p (set_stmt
, BUILT_IN_CONSTANT_P
)
1251 || gimple_call_num_args (set_stmt
) != 1)
1253 op2
= gimple_call_arg (set_stmt
, 0);
1254 base
= get_base_address (op2
);
1255 parm
= unmodified_parm (set_stmt
, base
? base
: 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
;
1438 /* What statments might be optimized away
1439 when their arguments are constant
1440 TODO: also trivial builtins.
1441 builtin_constant_p is already handled later. */
1442 if (gimple_code (stmt
) != GIMPLE_ASSIGN
1443 && gimple_code (stmt
) != GIMPLE_COND
1444 && gimple_code (stmt
) != GIMPLE_SWITCH
)
1447 /* Stores will stay anyway. */
1448 if (gimple_vdef (stmt
))
1451 is_load
= gimple_vuse (stmt
) != NULL
;
1453 /* Loads can be optimized when the value is known. */
1456 tree op
= gimple_assign_rhs1 (stmt
);
1457 tree base
= get_base_address (op
);
1460 gcc_assert (gimple_assign_single_p (stmt
));
1463 parm
= unmodified_parm (stmt
, base
);
1466 if (ipa_get_param_decl_index (info
, parm
) < 0)
1470 /* See if we understand all operands before we start
1471 adding conditionals. */
1472 FOR_EACH_SSA_TREE_OPERAND (use
, stmt
, iter
, SSA_OP_USE
)
1474 tree parm
= unmodified_parm (stmt
, use
);
1475 /* For arguments we can build a condition. */
1476 if (parm
&& ipa_get_param_decl_index (info
, parm
) >= 0)
1478 if (TREE_CODE (use
) != SSA_NAME
)
1480 /* If we know when operand is constant,
1481 we still can say something useful. */
1482 if (!true_predicate_p (VEC_index (predicate_t
, nonconstant_names
,
1483 SSA_NAME_VERSION (use
))))
1487 op_non_const
= false_predicate ();
1490 tree parm
= unmodified_parm
1491 (stmt
, get_base_address (gimple_assign_rhs1 (stmt
)));
1492 p
= add_condition (summary
,
1493 ipa_get_param_decl_index (info
, parm
),
1494 IS_NOT_CONSTANT
, NULL
);
1495 op_non_const
= or_predicates (summary
->conds
, &p
, &op_non_const
);
1497 FOR_EACH_SSA_TREE_OPERAND (use
, stmt
, iter
, SSA_OP_USE
)
1499 tree parm
= unmodified_parm (stmt
, use
);
1500 if (parm
&& ipa_get_param_decl_index (info
, parm
) >= 0)
1501 p
= add_condition (summary
,
1502 ipa_get_param_decl_index (info
, parm
),
1503 IS_NOT_CONSTANT
, NULL
);
1505 p
= *VEC_index (predicate_t
, nonconstant_names
,
1506 SSA_NAME_VERSION (use
));
1507 op_non_const
= or_predicates (summary
->conds
, &p
, &op_non_const
);
1509 if (gimple_code (stmt
) == GIMPLE_ASSIGN
1510 && TREE_CODE (gimple_assign_lhs (stmt
)) == SSA_NAME
)
1511 VEC_replace (predicate_t
, nonconstant_names
,
1512 SSA_NAME_VERSION (gimple_assign_lhs (stmt
)), &op_non_const
);
1513 return op_non_const
;
1517 /* Compute function body size parameters for NODE.
1518 When EARLY is true, we compute only simple summaries without
1519 non-trivial predicates to drive the early inliner. */
1522 estimate_function_body_sizes (struct cgraph_node
*node
, bool early
)
1525 /* Estimate static overhead for function prologue/epilogue and alignment. */
1527 /* Benefits are scaled by probability of elimination that is in range
1530 gimple_stmt_iterator bsi
;
1531 struct function
*my_function
= DECL_STRUCT_FUNCTION (node
->decl
);
1533 struct inline_summary
*info
= inline_summary (node
);
1534 struct predicate bb_predicate
;
1535 struct ipa_node_params
*parms_info
= NULL
;
1536 VEC (predicate_t
, heap
) *nonconstant_names
= NULL
;
1538 if (ipa_node_params_vector
&& !early
&& optimize
)
1540 parms_info
= IPA_NODE_REF (node
);
1541 VEC_safe_grow_cleared (predicate_t
, heap
, nonconstant_names
,
1542 VEC_length (tree
, SSANAMES (my_function
)));
1550 fprintf (dump_file
, "\nAnalyzing function body size: %s\n",
1551 cgraph_node_name (node
));
1553 /* When we run into maximal number of entries, we assign everything to the
1554 constant truth case. Be sure to have it in list. */
1555 bb_predicate
= true_predicate ();
1556 account_size_time (info
, 0, 0, &bb_predicate
);
1558 bb_predicate
= not_inlined_predicate ();
1559 account_size_time (info
, 2 * INLINE_SIZE_SCALE
, 0, &bb_predicate
);
1561 gcc_assert (my_function
&& my_function
->cfg
);
1563 compute_bb_predicates (node
, parms_info
, info
);
1564 FOR_EACH_BB_FN (bb
, my_function
)
1566 freq
= compute_call_stmt_bb_frequency (node
->decl
, bb
);
1568 /* TODO: Obviously predicates can be propagated down across CFG. */
1572 bb_predicate
= *(struct predicate
*)bb
->aux
;
1574 bb_predicate
= false_predicate ();
1577 bb_predicate
= true_predicate ();
1579 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1581 fprintf (dump_file
, "\n BB %i predicate:", bb
->index
);
1582 dump_predicate (dump_file
, info
->conds
, &bb_predicate
);
1585 for (bsi
= gsi_start_bb (bb
); !gsi_end_p (bsi
); gsi_next (&bsi
))
1587 gimple stmt
= gsi_stmt (bsi
);
1588 int this_size
= estimate_num_insns (stmt
, &eni_size_weights
);
1589 int this_time
= estimate_num_insns (stmt
, &eni_time_weights
);
1591 struct predicate will_be_nonconstant
;
1593 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1595 fprintf (dump_file
, " ");
1596 print_gimple_stmt (dump_file
, stmt
, 0, 0);
1597 fprintf (dump_file
, "\t\tfreq:%3.2f size:%3i time:%3i\n",
1598 ((double)freq
)/CGRAPH_FREQ_BASE
, this_size
, this_time
);
1601 if (is_gimple_call (stmt
))
1603 struct cgraph_edge
*edge
= cgraph_edge (node
, stmt
);
1604 struct inline_edge_summary
*es
= inline_edge_summary (edge
);
1606 /* Special case: results of BUILT_IN_CONSTANT_P will be always
1607 resolved as constant. We however don't want to optimize
1608 out the cgraph edges. */
1609 if (nonconstant_names
1610 && gimple_call_builtin_p (stmt
, BUILT_IN_CONSTANT_P
)
1611 && gimple_call_lhs (stmt
)
1612 && TREE_CODE (gimple_call_lhs (stmt
)) == SSA_NAME
)
1614 struct predicate false_p
= false_predicate ();
1615 VEC_replace (predicate_t
, nonconstant_names
,
1616 SSA_NAME_VERSION (gimple_call_lhs (stmt
)), &false_p
);
1619 es
->call_stmt_size
= this_size
;
1620 es
->call_stmt_time
= this_time
;
1621 es
->loop_depth
= bb
->loop_depth
;
1622 edge_set_predicate (edge
, &bb_predicate
);
1624 /* Do not inline calls where we cannot triviall work around
1625 mismatches in argument or return types. */
1627 && cgraph_function_or_thunk_node (edge
->callee
, NULL
)
1628 && !gimple_check_call_matching_types (stmt
,
1629 cgraph_function_or_thunk_node (edge
->callee
,
1632 edge
->call_stmt_cannot_inline_p
= true;
1633 gimple_call_set_cannot_inline (stmt
, true);
1636 gcc_assert (!gimple_call_cannot_inline_p (stmt
));
1639 /* TODO: When conditional jump or swithc is known to be constant, but
1640 we did not translate it into the predicates, we really can account
1641 just maximum of the possible paths. */
1644 = will_be_nonconstant_predicate (parms_info
, info
,
1645 stmt
, nonconstant_names
);
1646 if (this_time
|| this_size
)
1654 prob
= eliminated_by_inlining_prob (stmt
);
1655 if (prob
== 1 && dump_file
&& (dump_flags
& TDF_DETAILS
))
1656 fprintf (dump_file
, "\t\t50%% will be eliminated by inlining\n");
1657 if (prob
== 2 && dump_file
&& (dump_flags
& TDF_DETAILS
))
1658 fprintf (dump_file
, "\t\twill eliminated by inlining\n");
1661 p
= and_predicates (info
->conds
, &bb_predicate
, &will_be_nonconstant
);
1663 p
= true_predicate ();
1665 /* We account everything but the calls. Calls have their own
1666 size/time info attached to cgraph edges. This is neccesary
1667 in order to make the cost disappear after inlining. */
1668 if (!is_gimple_call (stmt
))
1672 struct predicate ip
= not_inlined_predicate ();
1673 ip
= and_predicates (info
->conds
, &ip
, &p
);
1674 account_size_time (info
, this_size
* prob
,
1675 this_time
* prob
, &ip
);
1678 account_size_time (info
, this_size
* (2 - prob
),
1679 this_time
* (2 - prob
), &p
);
1682 gcc_assert (time
>= 0);
1683 gcc_assert (size
>= 0);
1687 FOR_ALL_BB_FN (bb
, my_function
)
1693 pool_free (edge_predicate_pool
, bb
->aux
);
1695 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1698 pool_free (edge_predicate_pool
, e
->aux
);
1702 time
= (time
+ CGRAPH_FREQ_BASE
/ 2) / CGRAPH_FREQ_BASE
;
1703 if (time
> MAX_TIME
)
1705 inline_summary (node
)->self_time
= time
;
1706 inline_summary (node
)->self_size
= size
;
1707 VEC_free (predicate_t
, heap
, nonconstant_names
);
1710 fprintf (dump_file
, "\n");
1711 dump_inline_summary (dump_file
, node
);
1716 /* Compute parameters of functions used by inliner.
1717 EARLY is true when we compute parameters for the early inliner */
1720 compute_inline_parameters (struct cgraph_node
*node
, bool early
)
1722 HOST_WIDE_INT self_stack_size
;
1723 struct cgraph_edge
*e
;
1724 struct inline_summary
*info
;
1725 tree old_decl
= current_function_decl
;
1727 gcc_assert (!node
->global
.inlined_to
);
1729 inline_summary_alloc ();
1731 info
= inline_summary (node
);
1733 /* FIXME: Thunks are inlinable, but tree-inline don't know how to do that.
1734 Once this happen, we will need to more curefully predict call
1736 if (node
->thunk
.thunk_p
)
1738 struct inline_edge_summary
*es
= inline_edge_summary (node
->callees
);
1739 struct predicate t
= true_predicate ();
1741 info
->inlinable
= 0;
1742 node
->callees
->call_stmt_cannot_inline_p
= true;
1743 node
->local
.can_change_signature
= false;
1744 es
->call_stmt_time
= 1;
1745 es
->call_stmt_size
= 1;
1746 account_size_time (info
, 0, 0, &t
);
1750 /* Even is_gimple_min_invariant rely on current_function_decl. */
1751 current_function_decl
= node
->decl
;
1752 push_cfun (DECL_STRUCT_FUNCTION (node
->decl
));
1754 /* Estimate the stack size for the function if we're optimizing. */
1755 self_stack_size
= optimize
? estimated_stack_frame_size (node
) : 0;
1756 info
->estimated_self_stack_size
= self_stack_size
;
1757 info
->estimated_stack_size
= self_stack_size
;
1758 info
->stack_frame_offset
= 0;
1760 /* Can this function be inlined at all? */
1761 info
->inlinable
= tree_inlinable_function_p (node
->decl
);
1763 /* Type attributes can use parameter indices to describe them. */
1764 if (TYPE_ATTRIBUTES (TREE_TYPE (node
->decl
)))
1765 node
->local
.can_change_signature
= false;
1768 /* Otherwise, inlinable functions always can change signature. */
1769 if (info
->inlinable
)
1770 node
->local
.can_change_signature
= true;
1773 /* Functions calling builtin_apply can not change signature. */
1774 for (e
= node
->callees
; e
; e
= e
->next_callee
)
1776 tree
cdecl = e
->callee
->decl
;
1777 if (DECL_BUILT_IN (cdecl)
1778 && DECL_BUILT_IN_CLASS (cdecl) == BUILT_IN_NORMAL
1779 && (DECL_FUNCTION_CODE (cdecl) == BUILT_IN_APPLY_ARGS
1780 || DECL_FUNCTION_CODE (cdecl) == BUILT_IN_VA_START
))
1783 node
->local
.can_change_signature
= !e
;
1786 estimate_function_body_sizes (node
, early
);
1788 /* Inlining characteristics are maintained by the cgraph_mark_inline. */
1789 info
->time
= info
->self_time
;
1790 info
->size
= info
->self_size
;
1791 info
->stack_frame_offset
= 0;
1792 info
->estimated_stack_size
= info
->estimated_self_stack_size
;
1793 current_function_decl
= old_decl
;
1798 /* Compute parameters of functions used by inliner using
1799 current_function_decl. */
1802 compute_inline_parameters_for_current (void)
1804 compute_inline_parameters (cgraph_get_node (current_function_decl
), true);
1808 struct gimple_opt_pass pass_inline_parameters
=
1812 "inline_param", /* name */
1814 compute_inline_parameters_for_current
,/* execute */
1817 0, /* static_pass_number */
1818 TV_INLINE_HEURISTICS
, /* tv_id */
1819 0, /* properties_required */
1820 0, /* properties_provided */
1821 0, /* properties_destroyed */
1822 0, /* todo_flags_start */
1823 0 /* todo_flags_finish */
1828 /* Increase SIZE and TIME for size and time needed to handle edge E. */
1831 estimate_edge_size_and_time (struct cgraph_edge
*e
, int *size
, int *time
)
1833 struct inline_edge_summary
*es
= inline_edge_summary (e
);
1834 *size
+= es
->call_stmt_size
* INLINE_SIZE_SCALE
;
1835 *time
+= (es
->call_stmt_time
1836 * e
->frequency
* (INLINE_TIME_SCALE
/ CGRAPH_FREQ_BASE
));
1837 if (*time
> MAX_TIME
* INLINE_TIME_SCALE
)
1838 *time
= MAX_TIME
* INLINE_TIME_SCALE
;
1842 /* Increase SIZE and TIME for size and time needed to handle all calls in NODE. */
1845 estimate_calls_size_and_time (struct cgraph_node
*node
, int *size
, int *time
,
1846 clause_t possible_truths
)
1848 struct cgraph_edge
*e
;
1849 for (e
= node
->callees
; e
; e
= e
->next_callee
)
1851 struct inline_edge_summary
*es
= inline_edge_summary (e
);
1852 if (!es
->predicate
|| evaluate_predicate (es
->predicate
, possible_truths
))
1854 if (e
->inline_failed
)
1855 estimate_edge_size_and_time (e
, size
, time
);
1857 estimate_calls_size_and_time (e
->callee
, size
, time
,
1861 /* TODO: look for devirtualizing oppurtunities. */
1862 for (e
= node
->indirect_calls
; e
; e
= e
->next_callee
)
1864 struct inline_edge_summary
*es
= inline_edge_summary (e
);
1865 if (!es
->predicate
|| evaluate_predicate (es
->predicate
, possible_truths
))
1866 estimate_edge_size_and_time (e
, size
, time
);
1871 /* Estimate size and time needed to execute NODE assuming
1872 POSSIBLE_TRUTHS clause. */
1875 estimate_node_size_and_time (struct cgraph_node
*node
,
1876 clause_t possible_truths
,
1877 int *ret_size
, int *ret_time
)
1879 struct inline_summary
*info
= inline_summary (node
);
1881 int size
= 0, time
= 0;
1885 && (dump_flags
& TDF_DETAILS
))
1888 fprintf (dump_file
, " Estimating body: %s/%i\n"
1889 " Known to be false: ",
1890 cgraph_node_name (node
),
1893 for (i
= predicate_not_inlined_condition
;
1894 i
< (predicate_first_dynamic_condition
1895 + (int)VEC_length (condition
, info
->conds
)); i
++)
1896 if (!(possible_truths
& (1 << i
)))
1899 fprintf (dump_file
, ", ");
1901 dump_condition (dump_file
, info
->conds
, i
);
1905 for (i
= 0; VEC_iterate (size_time_entry
, info
->entry
, i
, e
); i
++)
1906 if (evaluate_predicate (&e
->predicate
, possible_truths
))
1907 time
+= e
->time
, size
+= e
->size
;
1909 if (time
> MAX_TIME
* INLINE_TIME_SCALE
)
1910 time
= MAX_TIME
* INLINE_TIME_SCALE
;
1912 estimate_calls_size_and_time (node
, &size
, &time
, possible_truths
);
1913 time
= (time
+ INLINE_TIME_SCALE
/ 2) / INLINE_TIME_SCALE
;
1914 size
= (size
+ INLINE_SIZE_SCALE
/ 2) / INLINE_SIZE_SCALE
;
1918 && (dump_flags
& TDF_DETAILS
))
1919 fprintf (dump_file
, "\n size:%i time:%i\n", size
, time
);
1928 /* Estimate size and time needed to execute callee of EDGE assuming that
1929 parameters known to be constant at caller of EDGE are propagated.
1930 KNOWN_VALs is a vector of assumed known constant values for parameters. */
1933 estimate_ipcp_clone_size_and_time (struct cgraph_node
*node
,
1934 VEC (tree
, heap
) *known_vals
,
1935 int *ret_size
, int *ret_time
)
1939 clause
= evaluate_conditions_for_known_args (node
, false, known_vals
);
1940 estimate_node_size_and_time (node
, clause
, ret_size
, ret_time
);
1944 /* Translate all conditions from callee representation into caller representation and
1945 symbolically evaluate predicate P into new predicate.
1947 INFO is inline_summary of function we are adding predicate into, CALLEE_INFO is summary
1948 of function predicate P is from. OPERAND_MAP is array giving callee formal IDs the
1949 caller formal IDs. POSSSIBLE_TRUTHS is clausule of all callee conditions that
1950 may be true in caller context. TOPLEV_PREDICATE is predicate under which callee
1953 static struct predicate
1954 remap_predicate (struct inline_summary
*info
, struct inline_summary
*callee_info
,
1955 struct predicate
*p
,
1956 VEC (int, heap
) *operand_map
,
1957 clause_t possible_truths
,
1958 struct predicate
*toplev_predicate
)
1961 struct predicate out
= true_predicate ();
1963 /* True predicate is easy. */
1964 if (true_predicate_p (p
))
1965 return *toplev_predicate
;
1966 for (i
= 0; p
->clause
[i
]; i
++)
1968 clause_t clause
= p
->clause
[i
];
1970 struct predicate clause_predicate
= false_predicate ();
1972 gcc_assert (i
< MAX_CLAUSES
);
1974 for (cond
= 0; cond
< NUM_CONDITIONS
; cond
++)
1975 /* Do we have condition we can't disprove? */
1976 if (clause
& possible_truths
& (1 << cond
))
1978 struct predicate cond_predicate
;
1979 /* Work out if the condition can translate to predicate in the
1980 inlined function. */
1981 if (cond
>= predicate_first_dynamic_condition
)
1983 struct condition
*c
;
1985 c
= VEC_index (condition
, callee_info
->conds
,
1986 cond
- predicate_first_dynamic_condition
);
1987 /* See if we can remap condition operand to caller's operand.
1988 Otherwise give up. */
1990 || (int)VEC_length (int, operand_map
) <= c
->operand_num
1991 || VEC_index (int, operand_map
, c
->operand_num
) == -1)
1992 cond_predicate
= true_predicate ();
1994 cond_predicate
= add_condition (info
,
1995 VEC_index (int, operand_map
,
1999 /* Fixed conditions remains same, construct single
2000 condition predicate. */
2003 cond_predicate
.clause
[0] = 1 << cond
;
2004 cond_predicate
.clause
[1] = 0;
2006 clause_predicate
= or_predicates (info
->conds
, &clause_predicate
,
2009 out
= and_predicates (info
->conds
, &out
, &clause_predicate
);
2011 return and_predicates (info
->conds
, &out
, toplev_predicate
);
2015 /* Update summary information of inline clones after inlining.
2016 Compute peak stack usage. */
2019 inline_update_callee_summaries (struct cgraph_node
*node
,
2022 struct cgraph_edge
*e
;
2023 struct inline_summary
*callee_info
= inline_summary (node
);
2024 struct inline_summary
*caller_info
= inline_summary (node
->callers
->caller
);
2027 callee_info
->stack_frame_offset
2028 = caller_info
->stack_frame_offset
2029 + caller_info
->estimated_self_stack_size
;
2030 peak
= callee_info
->stack_frame_offset
2031 + callee_info
->estimated_self_stack_size
;
2032 if (inline_summary (node
->global
.inlined_to
)->estimated_stack_size
2034 inline_summary (node
->global
.inlined_to
)->estimated_stack_size
= peak
;
2035 cgraph_propagate_frequency (node
);
2036 for (e
= node
->callees
; e
; e
= e
->next_callee
)
2038 if (!e
->inline_failed
)
2039 inline_update_callee_summaries (e
->callee
, depth
);
2040 inline_edge_summary (e
)->loop_depth
+= depth
;
2042 for (e
= node
->indirect_calls
; e
; e
= e
->next_callee
)
2043 inline_edge_summary (e
)->loop_depth
+= depth
;
2047 /* Remap predicates of callees of NODE. Rest of arguments match
2051 remap_edge_predicates (struct cgraph_node
*node
,
2052 struct inline_summary
*info
,
2053 struct inline_summary
*callee_info
,
2054 VEC (int, heap
) *operand_map
,
2055 clause_t possible_truths
,
2056 struct predicate
*toplev_predicate
)
2058 struct cgraph_edge
*e
;
2059 for (e
= node
->callees
; e
; e
= e
->next_callee
)
2061 struct inline_edge_summary
*es
= inline_edge_summary (e
);
2063 if (e
->inline_failed
)
2067 p
= remap_predicate (info
, callee_info
,
2068 es
->predicate
, operand_map
, possible_truths
,
2070 edge_set_predicate (e
, &p
);
2071 /* TODO: We should remove the edge for code that will be optimized out,
2072 but we need to keep verifiers and tree-inline happy.
2073 Make it cold for now. */
2074 if (false_predicate_p (&p
))
2081 edge_set_predicate (e
, toplev_predicate
);
2084 remap_edge_predicates (e
->callee
, info
, callee_info
, operand_map
,
2085 possible_truths
, toplev_predicate
);
2087 for (e
= node
->indirect_calls
; e
; e
= e
->next_callee
)
2089 struct inline_edge_summary
*es
= inline_edge_summary (e
);
2093 p
= remap_predicate (info
, callee_info
,
2094 es
->predicate
, operand_map
, possible_truths
,
2096 edge_set_predicate (e
, &p
);
2097 /* TODO: We should remove the edge for code that will be optimized out,
2098 but we need to keep verifiers and tree-inline happy.
2099 Make it cold for now. */
2100 if (false_predicate_p (&p
))
2107 edge_set_predicate (e
, toplev_predicate
);
2112 /* We inlined EDGE. Update summary of the function we inlined into. */
2115 inline_merge_summary (struct cgraph_edge
*edge
)
2117 struct inline_summary
*callee_info
= inline_summary (edge
->callee
);
2118 struct cgraph_node
*to
= (edge
->caller
->global
.inlined_to
2119 ? edge
->caller
->global
.inlined_to
: edge
->caller
);
2120 struct inline_summary
*info
= inline_summary (to
);
2121 clause_t clause
= 0; /* not_inline is known to be false. */
2123 VEC (int, heap
) *operand_map
= NULL
;
2125 struct predicate toplev_predicate
;
2126 struct predicate true_p
= true_predicate ();
2127 struct inline_edge_summary
*es
= inline_edge_summary (edge
);
2130 toplev_predicate
= *es
->predicate
;
2132 toplev_predicate
= true_predicate ();
2134 if (ipa_node_params_vector
&& callee_info
->conds
)
2136 struct ipa_edge_args
*args
= IPA_EDGE_REF (edge
);
2137 int count
= ipa_get_cs_argument_count (args
);
2140 clause
= evaluate_conditions_for_edge (edge
, true);
2142 VEC_safe_grow_cleared (int, heap
, operand_map
, count
);
2143 for (i
= 0; i
< count
; i
++)
2145 struct ipa_jump_func
*jfunc
= ipa_get_ith_jump_func (args
, i
);
2147 /* TODO: handle non-NOPs when merging. */
2148 if (jfunc
->type
== IPA_JF_PASS_THROUGH
2149 && jfunc
->value
.pass_through
.operation
== NOP_EXPR
)
2150 map
= jfunc
->value
.pass_through
.formal_id
;
2151 VEC_replace (int, operand_map
, i
, map
);
2152 gcc_assert (map
< ipa_get_param_count (IPA_NODE_REF (to
)));
2155 for (i
= 0; VEC_iterate (size_time_entry
, callee_info
->entry
, i
, e
); i
++)
2157 struct predicate p
= remap_predicate (info
, callee_info
,
2158 &e
->predicate
, operand_map
, clause
,
2160 gcov_type add_time
= ((gcov_type
)e
->time
* edge
->frequency
2161 + CGRAPH_FREQ_BASE
/ 2) / CGRAPH_FREQ_BASE
;
2162 if (add_time
> MAX_TIME
)
2163 add_time
= MAX_TIME
;
2164 account_size_time (info
, e
->size
, add_time
, &p
);
2166 remap_edge_predicates (edge
->callee
, info
, callee_info
, operand_map
,
2167 clause
, &toplev_predicate
);
2170 for (i
= 0; VEC_iterate (size_time_entry
, info
->entry
, i
, e
); i
++)
2171 info
->size
+= e
->size
, info
->time
+= e
->time
;
2172 estimate_calls_size_and_time (to
, &info
->size
, &info
->time
,
2173 ~(clause_t
)(1 << predicate_false_condition
));
2175 inline_update_callee_summaries (edge
->callee
,
2176 inline_edge_summary (edge
)->loop_depth
);
2178 /* We do not maintain predicates of inlined edges, free it. */
2179 edge_set_predicate (edge
, &true_p
);
2181 info
->time
= (info
->time
+ INLINE_TIME_SCALE
/ 2) / INLINE_TIME_SCALE
;
2182 info
->size
= (info
->size
+ INLINE_SIZE_SCALE
/ 2) / INLINE_SIZE_SCALE
;
2186 /* Estimate the time cost for the caller when inlining EDGE.
2187 Only to be called via estimate_edge_time, that handles the
2190 When caching, also update the cache entry. Compute both time and
2191 size, since we always need both metrics eventually. */
2194 do_estimate_edge_time (struct cgraph_edge
*edge
)
2199 struct inline_edge_summary
*es
= inline_edge_summary (edge
);
2201 gcc_checking_assert (edge
->inline_failed
);
2202 estimate_node_size_and_time (cgraph_function_or_thunk_node (edge
->callee
, NULL
),
2203 evaluate_conditions_for_edge (edge
, true),
2206 ret
= (((gcov_type
)time
2207 - es
->call_stmt_time
) * edge
->frequency
2208 + CGRAPH_FREQ_BASE
/ 2) / CGRAPH_FREQ_BASE
;
2210 /* When caching, update the cache entry. */
2211 if (edge_growth_cache
)
2214 if ((int)VEC_length (edge_growth_cache_entry
, edge_growth_cache
)
2216 VEC_safe_grow_cleared (edge_growth_cache_entry
, heap
, edge_growth_cache
,
2217 cgraph_edge_max_uid
);
2218 VEC_index (edge_growth_cache_entry
, edge_growth_cache
, edge
->uid
)->time
2221 ret_size
= size
- es
->call_stmt_size
;
2222 gcc_checking_assert (es
->call_stmt_size
);
2223 VEC_index (edge_growth_cache_entry
, edge_growth_cache
, edge
->uid
)->size
2224 = ret_size
+ (ret_size
>= 0);
2230 /* Estimate the growth of the caller when inlining EDGE.
2231 Only to be called via estimate_edge_size. */
2234 do_estimate_edge_growth (struct cgraph_edge
*edge
)
2237 struct cgraph_node
*callee
;
2239 /* When we do caching, use do_estimate_edge_time to populate the entry. */
2241 if (edge_growth_cache
)
2243 do_estimate_edge_time (edge
);
2244 size
= VEC_index (edge_growth_cache_entry
,
2247 gcc_checking_assert (size
);
2248 return size
- (size
> 0);
2250 callee
= cgraph_function_or_thunk_node (edge
->callee
, NULL
);
2252 /* Early inliner runs without caching, go ahead and do the dirty work. */
2253 gcc_checking_assert (edge
->inline_failed
);
2254 estimate_node_size_and_time (callee
,
2255 evaluate_conditions_for_edge (edge
, true),
2257 gcc_checking_assert (inline_edge_summary (edge
)->call_stmt_size
);
2258 return size
- inline_edge_summary (edge
)->call_stmt_size
;
2262 /* Estimate self time of the function NODE after inlining EDGE. */
2265 estimate_time_after_inlining (struct cgraph_node
*node
,
2266 struct cgraph_edge
*edge
)
2268 struct inline_edge_summary
*es
= inline_edge_summary (edge
);
2269 if (!es
->predicate
|| !false_predicate_p (es
->predicate
))
2271 gcov_type time
= inline_summary (node
)->time
+ estimate_edge_time (edge
);
2274 if (time
> MAX_TIME
)
2278 return inline_summary (node
)->time
;
2282 /* Estimate the size of NODE after inlining EDGE which should be an
2283 edge to either NODE or a call inlined into NODE. */
2286 estimate_size_after_inlining (struct cgraph_node
*node
,
2287 struct cgraph_edge
*edge
)
2289 struct inline_edge_summary
*es
= inline_edge_summary (edge
);
2290 if (!es
->predicate
|| !false_predicate_p (es
->predicate
))
2292 int size
= inline_summary (node
)->size
+ estimate_edge_growth (edge
);
2293 gcc_assert (size
>= 0);
2296 return inline_summary (node
)->size
;
2302 bool self_recursive
;
2307 /* Worker for do_estimate_growth. Collect growth for all callers. */
2310 do_estimate_growth_1 (struct cgraph_node
*node
, void *data
)
2312 struct cgraph_edge
*e
;
2313 struct growth_data
*d
= (struct growth_data
*) data
;
2315 for (e
= node
->callers
; e
; e
= e
->next_caller
)
2317 gcc_checking_assert (e
->inline_failed
);
2319 if (e
->caller
== node
2320 || (e
->caller
->global
.inlined_to
2321 && e
->caller
->global
.inlined_to
== node
))
2322 d
->self_recursive
= true;
2323 d
->growth
+= estimate_edge_growth (e
);
2329 /* Estimate the growth caused by inlining NODE into all callees. */
2332 do_estimate_growth (struct cgraph_node
*node
)
2334 struct growth_data d
= {0, false};
2335 struct inline_summary
*info
= inline_summary (node
);
2337 cgraph_for_node_and_aliases (node
, do_estimate_growth_1
, &d
, true);
2339 /* For self recursive functions the growth estimation really should be
2340 infinity. We don't want to return very large values because the growth
2341 plays various roles in badness computation fractions. Be sure to not
2342 return zero or negative growths. */
2343 if (d
.self_recursive
)
2344 d
.growth
= d
.growth
< info
->size
? info
->size
: d
.growth
;
2347 if (!DECL_EXTERNAL (node
->decl
)
2348 && cgraph_will_be_removed_from_program_if_no_direct_calls (node
))
2349 d
.growth
-= info
->size
;
2350 /* COMDAT functions are very often not shared across multiple units since they
2351 come from various template instantiations. Take this into account. */
2352 else if (DECL_COMDAT (node
->decl
)
2353 && cgraph_can_remove_if_no_direct_calls_p (node
))
2354 d
.growth
-= (info
->size
2355 * (100 - PARAM_VALUE (PARAM_COMDAT_SHARING_PROBABILITY
)) + 50) / 100;
2358 if (node_growth_cache
)
2360 if ((int)VEC_length (int, node_growth_cache
) <= node
->uid
)
2361 VEC_safe_grow_cleared (int, heap
, node_growth_cache
, cgraph_max_uid
);
2362 VEC_replace (int, node_growth_cache
, node
->uid
, d
.growth
+ (d
.growth
>= 0));
2368 /* This function performs intraprocedural analysis in NODE that is required to
2369 inline indirect calls. */
2372 inline_indirect_intraprocedural_analysis (struct cgraph_node
*node
)
2374 ipa_analyze_node (node
);
2375 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2377 ipa_print_node_params (dump_file
, node
);
2378 ipa_print_node_jump_functions (dump_file
, node
);
2383 /* Note function body size. */
2386 inline_analyze_function (struct cgraph_node
*node
)
2388 push_cfun (DECL_STRUCT_FUNCTION (node
->decl
));
2389 current_function_decl
= node
->decl
;
2392 fprintf (dump_file
, "\nAnalyzing function: %s/%u\n",
2393 cgraph_node_name (node
), node
->uid
);
2394 if (optimize
&& !node
->thunk
.thunk_p
)
2395 inline_indirect_intraprocedural_analysis (node
);
2396 compute_inline_parameters (node
, false);
2398 current_function_decl
= NULL
;
2403 /* Called when new function is inserted to callgraph late. */
2406 add_new_function (struct cgraph_node
*node
, void *data ATTRIBUTE_UNUSED
)
2408 inline_analyze_function (node
);
2412 /* Note function body size. */
2415 inline_generate_summary (void)
2417 struct cgraph_node
*node
;
2419 function_insertion_hook_holder
=
2420 cgraph_add_function_insertion_hook (&add_new_function
, NULL
);
2422 ipa_register_cgraph_hooks ();
2424 FOR_EACH_DEFINED_FUNCTION (node
)
2426 inline_analyze_function (node
);
2430 /* Read predicate from IB. */
2432 static struct predicate
2433 read_predicate (struct lto_input_block
*ib
)
2435 struct predicate out
;
2441 gcc_assert (k
<= MAX_CLAUSES
);
2442 clause
= out
.clause
[k
++] = streamer_read_uhwi (ib
);
2446 /* Zero-initialize the remaining clauses in OUT. */
2447 while (k
<= MAX_CLAUSES
)
2448 out
.clause
[k
++] = 0;
2454 /* Write inline summary for edge E to OB. */
2457 read_inline_edge_summary (struct lto_input_block
*ib
, struct cgraph_edge
*e
)
2459 struct inline_edge_summary
*es
= inline_edge_summary (e
);
2462 es
->call_stmt_size
= streamer_read_uhwi (ib
);
2463 es
->call_stmt_time
= streamer_read_uhwi (ib
);
2464 es
->loop_depth
= streamer_read_uhwi (ib
);
2465 p
= read_predicate (ib
);
2466 edge_set_predicate (e
, &p
);
2470 /* Stream in inline summaries from the section. */
2473 inline_read_section (struct lto_file_decl_data
*file_data
, const char *data
,
2476 const struct lto_function_header
*header
=
2477 (const struct lto_function_header
*) data
;
2478 const int32_t cfg_offset
= sizeof (struct lto_function_header
);
2479 const int32_t main_offset
= cfg_offset
+ header
->cfg_size
;
2480 const int32_t string_offset
= main_offset
+ header
->main_size
;
2481 struct data_in
*data_in
;
2482 struct lto_input_block ib
;
2483 unsigned int i
, count2
, j
;
2484 unsigned int f_count
;
2486 LTO_INIT_INPUT_BLOCK (ib
, (const char *) data
+ main_offset
, 0,
2490 lto_data_in_create (file_data
, (const char *) data
+ string_offset
,
2491 header
->string_size
, NULL
);
2492 f_count
= streamer_read_uhwi (&ib
);
2493 for (i
= 0; i
< f_count
; i
++)
2496 struct cgraph_node
*node
;
2497 struct inline_summary
*info
;
2498 lto_cgraph_encoder_t encoder
;
2499 struct bitpack_d bp
;
2500 struct cgraph_edge
*e
;
2502 index
= streamer_read_uhwi (&ib
);
2503 encoder
= file_data
->cgraph_node_encoder
;
2504 node
= lto_cgraph_encoder_deref (encoder
, index
);
2505 info
= inline_summary (node
);
2507 info
->estimated_stack_size
2508 = info
->estimated_self_stack_size
= streamer_read_uhwi (&ib
);
2509 info
->size
= info
->self_size
= streamer_read_uhwi (&ib
);
2510 info
->time
= info
->self_time
= streamer_read_uhwi (&ib
);
2512 bp
= streamer_read_bitpack (&ib
);
2513 info
->inlinable
= bp_unpack_value (&bp
, 1);
2515 count2
= streamer_read_uhwi (&ib
);
2516 gcc_assert (!info
->conds
);
2517 for (j
= 0; j
< count2
; j
++)
2520 c
.operand_num
= streamer_read_uhwi (&ib
);
2521 c
.code
= (enum tree_code
) streamer_read_uhwi (&ib
);
2522 c
.val
= stream_read_tree (&ib
, data_in
);
2523 VEC_safe_push (condition
, gc
, info
->conds
, &c
);
2525 count2
= streamer_read_uhwi (&ib
);
2526 gcc_assert (!info
->entry
);
2527 for (j
= 0; j
< count2
; j
++)
2529 struct size_time_entry e
;
2531 e
.size
= streamer_read_uhwi (&ib
);
2532 e
.time
= streamer_read_uhwi (&ib
);
2533 e
.predicate
= read_predicate (&ib
);
2535 VEC_safe_push (size_time_entry
, gc
, info
->entry
, &e
);
2537 for (e
= node
->callees
; e
; e
= e
->next_callee
)
2538 read_inline_edge_summary (&ib
, e
);
2539 for (e
= node
->indirect_calls
; e
; e
= e
->next_callee
)
2540 read_inline_edge_summary (&ib
, e
);
2543 lto_free_section_data (file_data
, LTO_section_inline_summary
, NULL
, data
,
2545 lto_data_in_delete (data_in
);
2549 /* Read inline summary. Jump functions are shared among ipa-cp
2550 and inliner, so when ipa-cp is active, we don't need to write them
2554 inline_read_summary (void)
2556 struct lto_file_decl_data
**file_data_vec
= lto_get_file_decl_data ();
2557 struct lto_file_decl_data
*file_data
;
2560 inline_summary_alloc ();
2562 while ((file_data
= file_data_vec
[j
++]))
2565 const char *data
= lto_get_section_data (file_data
, LTO_section_inline_summary
, NULL
, &len
);
2567 inline_read_section (file_data
, data
, len
);
2569 /* Fatal error here. We do not want to support compiling ltrans units with
2570 different version of compiler or different flags than the WPA unit, so
2571 this should never happen. */
2572 fatal_error ("ipa inline summary is missing in input file");
2576 ipa_register_cgraph_hooks ();
2578 ipa_prop_read_jump_functions ();
2580 function_insertion_hook_holder
=
2581 cgraph_add_function_insertion_hook (&add_new_function
, NULL
);
2585 /* Write predicate P to OB. */
2588 write_predicate (struct output_block
*ob
, struct predicate
*p
)
2592 for (j
= 0; p
->clause
[j
]; j
++)
2594 gcc_assert (j
< MAX_CLAUSES
);
2595 streamer_write_uhwi (ob
, p
->clause
[j
]);
2597 streamer_write_uhwi (ob
, 0);
2601 /* Write inline summary for edge E to OB. */
2604 write_inline_edge_summary (struct output_block
*ob
, struct cgraph_edge
*e
)
2606 struct inline_edge_summary
*es
= inline_edge_summary (e
);
2607 streamer_write_uhwi (ob
, es
->call_stmt_size
);
2608 streamer_write_uhwi (ob
, es
->call_stmt_time
);
2609 streamer_write_uhwi (ob
, es
->loop_depth
);
2610 write_predicate (ob
, es
->predicate
);
2614 /* Write inline summary for node in SET.
2615 Jump functions are shared among ipa-cp and inliner, so when ipa-cp is
2616 active, we don't need to write them twice. */
2619 inline_write_summary (cgraph_node_set set
,
2620 varpool_node_set vset ATTRIBUTE_UNUSED
)
2622 struct cgraph_node
*node
;
2623 struct output_block
*ob
= create_output_block (LTO_section_inline_summary
);
2624 lto_cgraph_encoder_t encoder
= ob
->decl_state
->cgraph_node_encoder
;
2625 unsigned int count
= 0;
2628 for (i
= 0; i
< lto_cgraph_encoder_size (encoder
); i
++)
2629 if (lto_cgraph_encoder_deref (encoder
, i
)->analyzed
)
2631 streamer_write_uhwi (ob
, count
);
2633 for (i
= 0; i
< lto_cgraph_encoder_size (encoder
); i
++)
2635 node
= lto_cgraph_encoder_deref (encoder
, i
);
2638 struct inline_summary
*info
= inline_summary (node
);
2639 struct bitpack_d bp
;
2640 struct cgraph_edge
*edge
;
2643 struct condition
*c
;
2645 streamer_write_uhwi (ob
, lto_cgraph_encoder_encode (encoder
, node
));
2646 streamer_write_hwi (ob
, info
->estimated_self_stack_size
);
2647 streamer_write_hwi (ob
, info
->self_size
);
2648 streamer_write_hwi (ob
, info
->self_time
);
2649 bp
= bitpack_create (ob
->main_stream
);
2650 bp_pack_value (&bp
, info
->inlinable
, 1);
2651 streamer_write_bitpack (&bp
);
2652 streamer_write_uhwi (ob
, VEC_length (condition
, info
->conds
));
2653 for (i
= 0; VEC_iterate (condition
, info
->conds
, i
, c
); i
++)
2655 streamer_write_uhwi (ob
, c
->operand_num
);
2656 streamer_write_uhwi (ob
, c
->code
);
2657 stream_write_tree (ob
, c
->val
, true);
2659 streamer_write_uhwi (ob
, VEC_length (size_time_entry
, info
->entry
));
2661 VEC_iterate (size_time_entry
, info
->entry
, i
, e
);
2664 streamer_write_uhwi (ob
, e
->size
);
2665 streamer_write_uhwi (ob
, e
->time
);
2666 write_predicate (ob
, &e
->predicate
);
2668 for (edge
= node
->callees
; edge
; edge
= edge
->next_callee
)
2669 write_inline_edge_summary (ob
, edge
);
2670 for (edge
= node
->indirect_calls
; edge
; edge
= edge
->next_callee
)
2671 write_inline_edge_summary (ob
, edge
);
2674 streamer_write_char_stream (ob
->main_stream
, 0);
2675 produce_asm (ob
, NULL
);
2676 destroy_output_block (ob
);
2678 if (optimize
&& !flag_ipa_cp
)
2679 ipa_prop_write_jump_functions (set
);
2683 /* Release inline summary. */
2686 inline_free_summary (void)
2688 if (function_insertion_hook_holder
)
2689 cgraph_remove_function_insertion_hook (function_insertion_hook_holder
);
2690 function_insertion_hook_holder
= NULL
;
2691 if (node_removal_hook_holder
)
2692 cgraph_remove_node_removal_hook (node_removal_hook_holder
);
2693 if (edge_removal_hook_holder
)
2694 cgraph_remove_edge_removal_hook (edge_removal_hook_holder
);
2695 node_removal_hook_holder
= NULL
;
2696 if (node_duplication_hook_holder
)
2697 cgraph_remove_node_duplication_hook (node_duplication_hook_holder
);
2698 if (edge_duplication_hook_holder
)
2699 cgraph_remove_edge_duplication_hook (edge_duplication_hook_holder
);
2700 node_duplication_hook_holder
= NULL
;
2701 VEC_free (inline_summary_t
, gc
, inline_summary_vec
);
2702 inline_summary_vec
= NULL
;
2703 VEC_free (inline_edge_summary_t
, heap
, inline_edge_summary_vec
);
2704 inline_edge_summary_vec
= NULL
;
2705 if (edge_predicate_pool
)
2706 free_alloc_pool (edge_predicate_pool
);
2707 edge_predicate_pool
= 0;