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"
80 #include "tree-pass.h"
83 #include "tree-flow.h"
85 #include "lto-streamer.h"
86 #include "data-streamer.h"
87 #include "tree-streamer.h"
88 #include "ipa-inline.h"
89 #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 * 2 in an
94 integer. For anything larger we use gcov_type. */
95 #define MAX_TIME 500000
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
111 /* Special condition code we use to represent test that operand is not changed
112 across invocation of the function. When operand IS_NOT_CONSTANT it is always
113 CHANGED, however i.e. loop invariants can be NOT_CHANGED given percentage
114 of executions even when they are not compile time constants. */
115 #define CHANGED IDENTIFIER_NODE
117 /* Holders of ipa cgraph hooks: */
118 static struct cgraph_node_hook_list
*function_insertion_hook_holder
;
119 static struct cgraph_node_hook_list
*node_removal_hook_holder
;
120 static struct cgraph_2node_hook_list
*node_duplication_hook_holder
;
121 static struct cgraph_2edge_hook_list
*edge_duplication_hook_holder
;
122 static struct cgraph_edge_hook_list
*edge_removal_hook_holder
;
123 static void inline_node_removal_hook (struct cgraph_node
*, void *);
124 static void inline_node_duplication_hook (struct cgraph_node
*,
125 struct cgraph_node
*, void *);
126 static void inline_edge_removal_hook (struct cgraph_edge
*, void *);
127 static void inline_edge_duplication_hook (struct cgraph_edge
*,
128 struct cgraph_edge
*,
131 /* VECtor holding inline summaries.
132 In GGC memory because conditions might point to constant trees. */
133 VEC(inline_summary_t
,gc
) *inline_summary_vec
;
134 VEC(inline_edge_summary_t
,heap
) *inline_edge_summary_vec
;
136 /* Cached node/edge growths. */
137 VEC(int,heap
) *node_growth_cache
;
138 VEC(edge_growth_cache_entry
,heap
) *edge_growth_cache
;
140 /* Edge predicates goes here. */
141 static alloc_pool edge_predicate_pool
;
143 /* Return true predicate (tautology).
144 We represent it by empty list of clauses. */
146 static inline struct predicate
147 true_predicate (void)
155 /* Return predicate testing single condition number COND. */
157 static inline struct predicate
158 single_cond_predicate (int cond
)
161 p
.clause
[0]=1 << cond
;
167 /* Return false predicate. First clause require false condition. */
169 static inline struct predicate
170 false_predicate (void)
172 return single_cond_predicate (predicate_false_condition
);
176 /* Return true if P is (false). */
179 true_predicate_p (struct predicate
*p
)
181 return !p
->clause
[0];
185 /* Return true if P is (false). */
188 false_predicate_p (struct predicate
*p
)
190 if (p
->clause
[0] == (1 << predicate_false_condition
))
192 gcc_checking_assert (!p
->clause
[1]
193 && p
->clause
[0] == 1 << predicate_false_condition
);
200 /* Return predicate that is set true when function is not inlined. */
201 static inline struct predicate
202 not_inlined_predicate (void)
204 return single_cond_predicate (predicate_not_inlined_condition
);
207 /* Simple description of whether a memory load or a condition refers to a load
208 from an aggregate and if so, how and where from in the aggregate.
209 Individual fields have the same meaning like fields with the same name in
212 struct agg_position_info
214 HOST_WIDE_INT offset
;
219 /* Add condition to condition list CONDS. AGGPOS describes whether the used
220 oprand is loaded from an aggregate and where in the aggregate it is. It can
221 be NULL, which means this not a load from an aggregate. */
223 static struct predicate
224 add_condition (struct inline_summary
*summary
, int operand_num
,
225 struct agg_position_info
*aggpos
,
226 enum tree_code code
, tree val
)
230 struct condition new_cond
;
231 HOST_WIDE_INT offset
;
232 bool agg_contents
, by_ref
;
236 offset
= aggpos
->offset
;
237 agg_contents
= aggpos
->agg_contents
;
238 by_ref
= aggpos
->by_ref
;
243 agg_contents
= false;
247 gcc_checking_assert (operand_num
>= 0);
248 for (i
= 0; VEC_iterate (condition
, summary
->conds
, i
, c
); i
++)
250 if (c
->operand_num
== operand_num
253 && c
->agg_contents
== agg_contents
254 && (!agg_contents
|| (c
->offset
== offset
&& c
->by_ref
== by_ref
)))
255 return single_cond_predicate (i
+ predicate_first_dynamic_condition
);
257 /* Too many conditions. Give up and return constant true. */
258 if (i
== NUM_CONDITIONS
- predicate_first_dynamic_condition
)
259 return true_predicate ();
261 new_cond
.operand_num
= operand_num
;
262 new_cond
.code
= code
;
264 new_cond
.agg_contents
= agg_contents
;
265 new_cond
.by_ref
= by_ref
;
266 new_cond
.offset
= offset
;
267 VEC_safe_push (condition
, gc
, summary
->conds
, &new_cond
);
268 return single_cond_predicate (i
+ predicate_first_dynamic_condition
);
272 /* Add clause CLAUSE into the predicate P. */
275 add_clause (conditions conditions
, struct predicate
*p
, clause_t clause
)
279 int insert_here
= -1;
286 /* False clause makes the whole predicate false. Kill the other variants. */
287 if (clause
== (1 << predicate_false_condition
))
289 p
->clause
[0] = (1 << predicate_false_condition
);
293 if (false_predicate_p (p
))
296 /* No one should be sily enough to add false into nontrivial clauses. */
297 gcc_checking_assert (!(clause
& (1 << predicate_false_condition
)));
299 /* Look where to insert the clause. At the same time prune out
300 clauses of P that are implied by the new clause and thus
302 for (i
= 0, i2
= 0; i
<= MAX_CLAUSES
; i
++)
304 p
->clause
[i2
] = p
->clause
[i
];
309 /* If p->clause[i] implies clause, there is nothing to add. */
310 if ((p
->clause
[i
] & clause
) == p
->clause
[i
])
312 /* We had nothing to add, none of clauses should've become
314 gcc_checking_assert (i
== i2
);
318 if (p
->clause
[i
] < clause
&& insert_here
< 0)
321 /* If clause implies p->clause[i], then p->clause[i] becomes redundant.
322 Otherwise the p->clause[i] has to stay. */
323 if ((p
->clause
[i
] & clause
) != clause
)
327 /* Look for clauses that are obviously true. I.e.
328 op0 == 5 || op0 != 5. */
329 for (c1
= predicate_first_dynamic_condition
; c1
< NUM_CONDITIONS
; c1
++)
332 if (!(clause
& (1 << c1
)))
334 cc1
= &VEC_index (condition
,
336 c1
- predicate_first_dynamic_condition
);
337 /* We have no way to represent !CHANGED and !IS_NOT_CONSTANT
338 and thus there is no point for looking for them. */
339 if (cc1
->code
== CHANGED
340 || cc1
->code
== IS_NOT_CONSTANT
)
342 for (c2
= c1
+ 1; c2
<= NUM_CONDITIONS
; c2
++)
343 if (clause
& (1 << c2
))
345 condition
*cc1
= &VEC_index (condition
,
347 c1
- predicate_first_dynamic_condition
);
348 condition
*cc2
= &VEC_index (condition
,
350 c2
- predicate_first_dynamic_condition
);
351 if (cc1
->operand_num
== cc2
->operand_num
352 && cc1
->val
== cc2
->val
353 && cc2
->code
!= IS_NOT_CONSTANT
354 && cc2
->code
!= CHANGED
355 && cc1
->code
== invert_tree_comparison
357 HONOR_NANS (TYPE_MODE (TREE_TYPE (cc1
->val
)))))
363 /* We run out of variants. Be conservative in positive direction. */
364 if (i2
== MAX_CLAUSES
)
366 /* Keep clauses in decreasing order. This makes equivalence testing easy. */
367 p
->clause
[i2
+ 1] = 0;
368 if (insert_here
>= 0)
369 for (;i2
> insert_here
; i2
--)
370 p
->clause
[i2
] = p
->clause
[i2
- 1];
373 p
->clause
[insert_here
] = clause
;
379 static struct predicate
380 and_predicates (conditions conditions
,
381 struct predicate
*p
, struct predicate
*p2
)
383 struct predicate out
= *p
;
386 /* Avoid busy work. */
387 if (false_predicate_p (p2
) || true_predicate_p (p
))
389 if (false_predicate_p (p
) || true_predicate_p (p2
))
392 /* See how far predicates match. */
393 for (i
= 0; p
->clause
[i
] && p
->clause
[i
] == p2
->clause
[i
]; i
++)
395 gcc_checking_assert (i
< MAX_CLAUSES
);
398 /* Combine the predicates rest. */
399 for (; p2
->clause
[i
]; i
++)
401 gcc_checking_assert (i
< MAX_CLAUSES
);
402 add_clause (conditions
, &out
, p2
->clause
[i
]);
408 /* Return true if predicates are obviously equal. */
411 predicates_equal_p (struct predicate
*p
, struct predicate
*p2
)
414 for (i
= 0; p
->clause
[i
]; i
++)
416 gcc_checking_assert (i
< MAX_CLAUSES
);
417 gcc_checking_assert (p
->clause
[i
] > p
->clause
[i
+ 1]);
418 gcc_checking_assert (!p2
->clause
[i
]
419 || p2
->clause
[i
] > p2
->clause
[i
+ 1]);
420 if (p
->clause
[i
] != p2
->clause
[i
])
423 return !p2
->clause
[i
];
429 static struct predicate
430 or_predicates (conditions conditions
, struct predicate
*p
, struct predicate
*p2
)
432 struct predicate out
= true_predicate ();
435 /* Avoid busy work. */
436 if (false_predicate_p (p2
) || true_predicate_p (p
))
438 if (false_predicate_p (p
) || true_predicate_p (p2
))
440 if (predicates_equal_p (p
, p2
))
443 /* OK, combine the predicates. */
444 for (i
= 0; p
->clause
[i
]; i
++)
445 for (j
= 0; p2
->clause
[j
]; j
++)
447 gcc_checking_assert (i
< MAX_CLAUSES
&& j
< MAX_CLAUSES
);
448 add_clause (conditions
, &out
, p
->clause
[i
] | p2
->clause
[j
]);
454 /* Having partial truth assignment in POSSIBLE_TRUTHS, return false
455 if predicate P is known to be false. */
458 evaluate_predicate (struct predicate
*p
, clause_t possible_truths
)
462 /* True remains true. */
463 if (true_predicate_p (p
))
466 gcc_assert (!(possible_truths
& (1 << predicate_false_condition
)));
468 /* See if we can find clause we can disprove. */
469 for (i
= 0; p
->clause
[i
]; i
++)
471 gcc_checking_assert (i
< MAX_CLAUSES
);
472 if (!(p
->clause
[i
] & possible_truths
))
478 /* Return the probability in range 0...REG_BR_PROB_BASE that the predicated
479 instruction will be recomputed per invocation of the inlined call. */
482 predicate_probability (conditions conds
,
483 struct predicate
*p
, clause_t possible_truths
,
484 VEC (inline_param_summary_t
, heap
) *inline_param_summary
)
487 int combined_prob
= REG_BR_PROB_BASE
;
489 /* True remains true. */
490 if (true_predicate_p (p
))
491 return REG_BR_PROB_BASE
;
493 if (false_predicate_p (p
))
496 gcc_assert (!(possible_truths
& (1 << predicate_false_condition
)));
498 /* See if we can find clause we can disprove. */
499 for (i
= 0; p
->clause
[i
]; i
++)
501 gcc_checking_assert (i
< MAX_CLAUSES
);
502 if (!(p
->clause
[i
] & possible_truths
))
508 if (!inline_param_summary
)
509 return REG_BR_PROB_BASE
;
510 for (i2
= 0; i2
< NUM_CONDITIONS
; i2
++)
511 if ((p
->clause
[i
] & possible_truths
) & (1 << i2
))
513 if (i2
>= predicate_first_dynamic_condition
)
515 condition
*c
= &VEC_index
517 i2
- predicate_first_dynamic_condition
);
518 if (c
->code
== CHANGED
520 < (int) VEC_length (inline_param_summary_t
,
521 inline_param_summary
)))
523 int iprob
= VEC_index (inline_param_summary_t
,
524 inline_param_summary
,
525 c
->operand_num
).change_prob
;
526 this_prob
= MAX (this_prob
, iprob
);
529 this_prob
= REG_BR_PROB_BASE
;
532 this_prob
= REG_BR_PROB_BASE
;
534 combined_prob
= MIN (this_prob
, combined_prob
);
539 return combined_prob
;
543 /* Dump conditional COND. */
546 dump_condition (FILE *f
, conditions conditions
, int cond
)
549 if (cond
== predicate_false_condition
)
550 fprintf (f
, "false");
551 else if (cond
== predicate_not_inlined_condition
)
552 fprintf (f
, "not inlined");
555 c
= &VEC_index (condition
, conditions
,
556 cond
- predicate_first_dynamic_condition
);
557 fprintf (f
, "op%i", c
->operand_num
);
559 fprintf (f
, "[%soffset: " HOST_WIDE_INT_PRINT_DEC
"]",
560 c
->by_ref
? "ref " : "", c
->offset
);
561 if (c
->code
== IS_NOT_CONSTANT
)
563 fprintf (f
, " not constant");
566 if (c
->code
== CHANGED
)
568 fprintf (f
, " changed");
571 fprintf (f
, " %s ", op_symbol_code (c
->code
));
572 print_generic_expr (f
, c
->val
, 1);
577 /* Dump clause CLAUSE. */
580 dump_clause (FILE *f
, conditions conds
, clause_t clause
)
587 for (i
= 0; i
< NUM_CONDITIONS
; i
++)
588 if (clause
& (1 << i
))
593 dump_condition (f
, conds
, i
);
599 /* Dump predicate PREDICATE. */
602 dump_predicate (FILE *f
, conditions conds
, struct predicate
*pred
)
605 if (true_predicate_p (pred
))
606 dump_clause (f
, conds
, 0);
608 for (i
= 0; pred
->clause
[i
]; i
++)
612 dump_clause (f
, conds
, pred
->clause
[i
]);
618 /* Record SIZE and TIME under condition PRED into the inline summary. */
621 account_size_time (struct inline_summary
*summary
, int size
, int time
,
622 struct predicate
*pred
)
628 if (false_predicate_p (pred
))
631 /* We need to create initial empty unconitional clause, but otherwie
632 we don't need to account empty times and sizes. */
633 if (!size
&& !time
&& summary
->entry
)
636 /* Watch overflow that might result from insane profiles. */
637 if (time
> MAX_TIME
* INLINE_TIME_SCALE
)
638 time
= MAX_TIME
* INLINE_TIME_SCALE
;
639 gcc_assert (time
>= 0);
641 for (i
= 0; VEC_iterate (size_time_entry
, summary
->entry
, i
, e
); i
++)
642 if (predicates_equal_p (&e
->predicate
, pred
))
651 e
= &VEC_index (size_time_entry
, summary
->entry
, 0);
652 gcc_assert (!e
->predicate
.clause
[0]);
654 if (dump_file
&& (dump_flags
& TDF_DETAILS
) && (time
|| size
))
656 fprintf (dump_file
, "\t\tAccounting size:%3.2f, time:%3.2f on %spredicate:",
657 ((double)size
) / INLINE_SIZE_SCALE
,
658 ((double)time
) / INLINE_TIME_SCALE
,
659 found
? "" : "new ");
660 dump_predicate (dump_file
, summary
->conds
, pred
);
664 struct size_time_entry new_entry
;
665 new_entry
.size
= size
;
666 new_entry
.time
= time
;
667 new_entry
.predicate
= *pred
;
668 VEC_safe_push (size_time_entry
, gc
, summary
->entry
, &new_entry
);
674 if (e
->time
> MAX_TIME
* INLINE_TIME_SCALE
)
675 e
->time
= MAX_TIME
* INLINE_TIME_SCALE
;
679 /* Set predicate for edge E. */
682 edge_set_predicate (struct cgraph_edge
*e
, struct predicate
*predicate
)
684 struct inline_edge_summary
*es
= inline_edge_summary (e
);
685 if (predicate
&& !true_predicate_p (predicate
))
688 es
->predicate
= (struct predicate
*)pool_alloc (edge_predicate_pool
);
689 *es
->predicate
= *predicate
;
694 pool_free (edge_predicate_pool
, es
->predicate
);
695 es
->predicate
= NULL
;
700 /* KNOWN_VALS is partial mapping of parameters of NODE to constant values.
701 KNOWN_AGGS is a vector of aggreggate jump functions for each parameter.
702 Return clause of possible truths. When INLINE_P is true, assume that we are
705 ERROR_MARK means compile time invariant. */
708 evaluate_conditions_for_known_args (struct cgraph_node
*node
,
710 VEC (tree
, heap
) *known_vals
,
711 VEC (ipa_agg_jump_function_p
, heap
) *known_aggs
)
713 clause_t clause
= inline_p
? 0 : 1 << predicate_not_inlined_condition
;
714 struct inline_summary
*info
= inline_summary (node
);
718 for (i
= 0; VEC_iterate (condition
, info
->conds
, i
, c
); i
++)
723 /* We allow call stmt to have fewer arguments than the callee function
724 (especially for K&R style programs). So bound check here (we assume
725 known_aggs vector, if non-NULL, has the same length as
727 gcc_checking_assert (!known_aggs
728 || (VEC_length (tree
, known_vals
)
729 == VEC_length (ipa_agg_jump_function_p
,
731 if (c
->operand_num
>= (int) VEC_length (tree
, known_vals
))
733 clause
|= 1 << (i
+ predicate_first_dynamic_condition
);
739 struct ipa_agg_jump_function
*agg
;
741 if (c
->code
== CHANGED
743 && (VEC_index (tree
, known_vals
, c
->operand_num
)
749 agg
= VEC_index (ipa_agg_jump_function_p
, known_aggs
,
751 val
= ipa_find_agg_cst_for_param (agg
, c
->offset
, c
->by_ref
);
758 val
= VEC_index (tree
, known_vals
, c
->operand_num
);
759 if (val
== error_mark_node
&& c
->code
!= CHANGED
)
765 clause
|= 1 << (i
+ predicate_first_dynamic_condition
);
768 if (c
->code
== IS_NOT_CONSTANT
|| c
->code
== CHANGED
)
770 res
= fold_binary_to_constant (c
->code
, boolean_type_node
, val
, c
->val
);
772 && integer_zerop (res
))
774 clause
|= 1 << (i
+ predicate_first_dynamic_condition
);
780 /* Work out what conditions might be true at invocation of E. */
783 evaluate_properties_for_edge (struct cgraph_edge
*e
, bool inline_p
,
784 clause_t
*clause_ptr
,
785 VEC (tree
, heap
) **known_vals_ptr
,
786 VEC (tree
, heap
) **known_binfos_ptr
,
787 VEC (ipa_agg_jump_function_p
, heap
) **known_aggs_ptr
)
789 struct cgraph_node
*callee
= cgraph_function_or_thunk_node (e
->callee
, NULL
);
790 struct inline_summary
*info
= inline_summary (callee
);
791 VEC (tree
, heap
) *known_vals
= NULL
;
792 VEC (ipa_agg_jump_function_p
, heap
) *known_aggs
= NULL
;
795 *clause_ptr
= inline_p
? 0 : 1 << predicate_not_inlined_condition
;
797 *known_vals_ptr
= NULL
;
798 if (known_binfos_ptr
)
799 *known_binfos_ptr
= NULL
;
801 if (ipa_node_params_vector
802 && !e
->call_stmt_cannot_inline_p
803 && ((clause_ptr
&& info
->conds
) || known_vals_ptr
|| known_binfos_ptr
))
805 struct ipa_node_params
*parms_info
;
806 struct ipa_edge_args
*args
= IPA_EDGE_REF (e
);
807 struct inline_edge_summary
*es
= inline_edge_summary (e
);
808 int i
, count
= ipa_get_cs_argument_count (args
);
810 if (e
->caller
->global
.inlined_to
)
811 parms_info
= IPA_NODE_REF (e
->caller
->global
.inlined_to
);
813 parms_info
= IPA_NODE_REF (e
->caller
);
815 if (count
&& (info
->conds
|| known_vals_ptr
))
816 VEC_safe_grow_cleared (tree
, heap
, known_vals
, count
);
817 if (count
&& (info
->conds
|| known_aggs_ptr
))
818 VEC_safe_grow_cleared (ipa_agg_jump_function_p
, heap
, known_aggs
,
820 if (count
&& known_binfos_ptr
)
821 VEC_safe_grow_cleared (tree
, heap
, *known_binfos_ptr
, count
);
823 for (i
= 0; i
< count
; i
++)
825 struct ipa_jump_func
*jf
= ipa_get_ith_jump_func (args
, i
);
826 tree cst
= ipa_value_from_jfunc (parms_info
, jf
);
829 if (known_vals
&& TREE_CODE (cst
) != TREE_BINFO
)
830 VEC_replace (tree
, known_vals
, i
, cst
);
831 else if (known_binfos_ptr
!= NULL
&& TREE_CODE (cst
) == TREE_BINFO
)
832 VEC_replace (tree
, *known_binfos_ptr
, i
, cst
);
835 && !VEC_index (inline_param_summary_t
,
838 VEC_replace (tree
, known_vals
, i
, error_mark_node
);
839 /* TODO: When IPA-CP starts propagating and merging aggregate jump
840 functions, use its knowledge of the caller too, just like the
841 scalar case above. */
842 VEC_replace (ipa_agg_jump_function_p
, known_aggs
, i
, &jf
->agg
);
847 *clause_ptr
= evaluate_conditions_for_known_args (callee
, inline_p
,
848 known_vals
, known_aggs
);
851 *known_vals_ptr
= known_vals
;
853 VEC_free (tree
, heap
, known_vals
);
856 *known_aggs_ptr
= known_aggs
;
858 VEC_free (ipa_agg_jump_function_p
, heap
, known_aggs
);
862 /* Allocate the inline summary vector or resize it to cover all cgraph nodes. */
865 inline_summary_alloc (void)
867 if (!node_removal_hook_holder
)
868 node_removal_hook_holder
=
869 cgraph_add_node_removal_hook (&inline_node_removal_hook
, NULL
);
870 if (!edge_removal_hook_holder
)
871 edge_removal_hook_holder
=
872 cgraph_add_edge_removal_hook (&inline_edge_removal_hook
, NULL
);
873 if (!node_duplication_hook_holder
)
874 node_duplication_hook_holder
=
875 cgraph_add_node_duplication_hook (&inline_node_duplication_hook
, NULL
);
876 if (!edge_duplication_hook_holder
)
877 edge_duplication_hook_holder
=
878 cgraph_add_edge_duplication_hook (&inline_edge_duplication_hook
, NULL
);
880 if (VEC_length (inline_summary_t
, inline_summary_vec
)
881 <= (unsigned) cgraph_max_uid
)
882 VEC_safe_grow_cleared (inline_summary_t
, gc
,
883 inline_summary_vec
, cgraph_max_uid
+ 1);
884 if (VEC_length (inline_edge_summary_t
, inline_edge_summary_vec
)
885 <= (unsigned) cgraph_edge_max_uid
)
886 VEC_safe_grow_cleared (inline_edge_summary_t
, heap
,
887 inline_edge_summary_vec
, cgraph_edge_max_uid
+ 1);
888 if (!edge_predicate_pool
)
889 edge_predicate_pool
= create_alloc_pool ("edge predicates",
890 sizeof (struct predicate
),
894 /* We are called multiple time for given function; clear
895 data from previous run so they are not cumulated. */
898 reset_inline_edge_summary (struct cgraph_edge
*e
)
901 < (int)VEC_length (inline_edge_summary_t
, inline_edge_summary_vec
))
903 struct inline_edge_summary
*es
= inline_edge_summary (e
);
905 es
->call_stmt_size
= es
->call_stmt_time
=0;
907 pool_free (edge_predicate_pool
, es
->predicate
);
908 es
->predicate
= NULL
;
909 VEC_free (inline_param_summary_t
, heap
, es
->param
);
913 /* We are called multiple time for given function; clear
914 data from previous run so they are not cumulated. */
917 reset_inline_summary (struct cgraph_node
*node
)
919 struct inline_summary
*info
= inline_summary (node
);
920 struct cgraph_edge
*e
;
922 info
->self_size
= info
->self_time
= 0;
923 info
->estimated_stack_size
= 0;
924 info
->estimated_self_stack_size
= 0;
925 info
->stack_frame_offset
= 0;
928 VEC_free (condition
, gc
, info
->conds
);
929 VEC_free (size_time_entry
,gc
, info
->entry
);
930 for (e
= node
->callees
; e
; e
= e
->next_callee
)
931 reset_inline_edge_summary (e
);
932 for (e
= node
->indirect_calls
; e
; e
= e
->next_callee
)
933 reset_inline_edge_summary (e
);
936 /* Hook that is called by cgraph.c when a node is removed. */
939 inline_node_removal_hook (struct cgraph_node
*node
, void *data ATTRIBUTE_UNUSED
)
941 struct inline_summary
*info
;
942 if (VEC_length (inline_summary_t
, inline_summary_vec
)
943 <= (unsigned)node
->uid
)
945 info
= inline_summary (node
);
946 reset_inline_summary (node
);
947 memset (info
, 0, sizeof (inline_summary_t
));
951 /* Hook that is called by cgraph.c when a node is duplicated. */
954 inline_node_duplication_hook (struct cgraph_node
*src
, struct cgraph_node
*dst
,
955 ATTRIBUTE_UNUSED
void *data
)
957 struct inline_summary
*info
;
958 inline_summary_alloc ();
959 info
= inline_summary (dst
);
960 memcpy (info
, inline_summary (src
),
961 sizeof (struct inline_summary
));
962 /* TODO: as an optimization, we may avoid copying conditions
963 that are known to be false or true. */
964 info
->conds
= VEC_copy (condition
, gc
, info
->conds
);
966 /* When there are any replacements in the function body, see if we can figure
967 out that something was optimized out. */
968 if (ipa_node_params_vector
&& dst
->clone
.tree_map
)
970 VEC(size_time_entry
,gc
) *entry
= info
->entry
;
971 /* Use SRC parm info since it may not be copied yet. */
972 struct ipa_node_params
*parms_info
= IPA_NODE_REF (src
);
973 VEC (tree
, heap
) *known_vals
= NULL
;
974 int count
= ipa_get_param_count (parms_info
);
976 clause_t possible_truths
;
977 struct predicate true_pred
= true_predicate ();
979 int optimized_out_size
= 0;
980 gcov_type optimized_out_time
= 0;
981 bool inlined_to_p
= false;
982 struct cgraph_edge
*edge
;
985 VEC_safe_grow_cleared (tree
, heap
, known_vals
, count
);
986 for (i
= 0; i
< count
; i
++)
988 tree t
= ipa_get_param (parms_info
, i
);
989 struct ipa_replace_map
*r
;
992 VEC_iterate (ipa_replace_map_p
, dst
->clone
.tree_map
, j
, r
);
999 VEC_replace (tree
, known_vals
, i
, r
->new_tree
);
1004 possible_truths
= evaluate_conditions_for_known_args (dst
, false,
1006 VEC_free (tree
, heap
, known_vals
);
1008 account_size_time (info
, 0, 0, &true_pred
);
1010 /* Remap size_time vectors.
1011 Simplify the predicate by prunning out alternatives that are known
1013 TODO: as on optimization, we can also eliminate conditions known
1015 for (i
= 0; VEC_iterate (size_time_entry
, entry
, i
, e
); i
++)
1017 struct predicate new_predicate
= true_predicate ();
1018 for (j
= 0; e
->predicate
.clause
[j
]; j
++)
1019 if (!(possible_truths
& e
->predicate
.clause
[j
]))
1021 new_predicate
= false_predicate ();
1025 add_clause (info
->conds
, &new_predicate
,
1026 possible_truths
& e
->predicate
.clause
[j
]);
1027 if (false_predicate_p (&new_predicate
))
1029 optimized_out_size
+= e
->size
;
1030 optimized_out_time
+= e
->time
;
1033 account_size_time (info
, e
->size
, e
->time
, &new_predicate
);
1036 /* Remap edge predicates with the same simplification as above.
1037 Also copy constantness arrays. */
1038 for (edge
= dst
->callees
; edge
; edge
= edge
->next_callee
)
1040 struct predicate new_predicate
= true_predicate ();
1041 struct inline_edge_summary
*es
= inline_edge_summary (edge
);
1043 if (!edge
->inline_failed
)
1044 inlined_to_p
= true;
1047 for (j
= 0; es
->predicate
->clause
[j
]; j
++)
1048 if (!(possible_truths
& es
->predicate
->clause
[j
]))
1050 new_predicate
= false_predicate ();
1054 add_clause (info
->conds
, &new_predicate
,
1055 possible_truths
& es
->predicate
->clause
[j
]);
1056 if (false_predicate_p (&new_predicate
)
1057 && !false_predicate_p (es
->predicate
))
1059 optimized_out_size
+= es
->call_stmt_size
* INLINE_SIZE_SCALE
;
1060 optimized_out_time
+= (es
->call_stmt_time
1061 * (INLINE_TIME_SCALE
/ CGRAPH_FREQ_BASE
)
1063 edge
->frequency
= 0;
1065 *es
->predicate
= new_predicate
;
1068 /* Remap indirect edge predicates with the same simplificaiton as above.
1069 Also copy constantness arrays. */
1070 for (edge
= dst
->indirect_calls
; edge
; edge
= edge
->next_callee
)
1072 struct predicate new_predicate
= true_predicate ();
1073 struct inline_edge_summary
*es
= inline_edge_summary (edge
);
1075 if (!edge
->inline_failed
)
1076 inlined_to_p
= true;
1079 for (j
= 0; es
->predicate
->clause
[j
]; j
++)
1080 if (!(possible_truths
& es
->predicate
->clause
[j
]))
1082 new_predicate
= false_predicate ();
1086 add_clause (info
->conds
, &new_predicate
,
1087 possible_truths
& es
->predicate
->clause
[j
]);
1088 if (false_predicate_p (&new_predicate
)
1089 && !false_predicate_p (es
->predicate
))
1091 optimized_out_size
+= es
->call_stmt_size
* INLINE_SIZE_SCALE
;
1092 optimized_out_time
+= (es
->call_stmt_time
1093 * (INLINE_TIME_SCALE
/ CGRAPH_FREQ_BASE
)
1095 edge
->frequency
= 0;
1097 *es
->predicate
= new_predicate
;
1100 /* If inliner or someone after inliner will ever start producing
1101 non-trivial clones, we will get trouble with lack of information
1102 about updating self sizes, because size vectors already contains
1103 sizes of the calees. */
1104 gcc_assert (!inlined_to_p
1105 || (!optimized_out_size
&& !optimized_out_time
));
1107 info
->size
-= optimized_out_size
/ INLINE_SIZE_SCALE
;
1108 info
->self_size
-= optimized_out_size
/ INLINE_SIZE_SCALE
;
1109 gcc_assert (info
->size
> 0);
1110 gcc_assert (info
->self_size
> 0);
1112 optimized_out_time
/= INLINE_TIME_SCALE
;
1113 if (optimized_out_time
> MAX_TIME
)
1114 optimized_out_time
= MAX_TIME
;
1115 info
->time
-= optimized_out_time
;
1116 info
->self_time
-= optimized_out_time
;
1119 if (info
->self_time
< 0)
1120 info
->self_time
= 0;
1123 info
->entry
= VEC_copy (size_time_entry
, gc
, info
->entry
);
1127 /* Hook that is called by cgraph.c when a node is duplicated. */
1130 inline_edge_duplication_hook (struct cgraph_edge
*src
, struct cgraph_edge
*dst
,
1131 ATTRIBUTE_UNUSED
void *data
)
1133 struct inline_edge_summary
*info
;
1134 struct inline_edge_summary
*srcinfo
;
1135 inline_summary_alloc ();
1136 info
= inline_edge_summary (dst
);
1137 srcinfo
= inline_edge_summary (src
);
1138 memcpy (info
, srcinfo
,
1139 sizeof (struct inline_edge_summary
));
1140 info
->predicate
= NULL
;
1141 edge_set_predicate (dst
, srcinfo
->predicate
);
1142 info
->param
= VEC_copy (inline_param_summary_t
, heap
, srcinfo
->param
);
1146 /* Keep edge cache consistent across edge removal. */
1149 inline_edge_removal_hook (struct cgraph_edge
*edge
, void *data ATTRIBUTE_UNUSED
)
1151 if (edge_growth_cache
)
1152 reset_edge_growth_cache (edge
);
1153 reset_inline_edge_summary (edge
);
1157 /* Initialize growth caches. */
1160 initialize_growth_caches (void)
1162 if (cgraph_edge_max_uid
)
1163 VEC_safe_grow_cleared (edge_growth_cache_entry
, heap
, edge_growth_cache
,
1164 cgraph_edge_max_uid
);
1166 VEC_safe_grow_cleared (int, heap
, node_growth_cache
, cgraph_max_uid
);
1170 /* Free growth caches. */
1173 free_growth_caches (void)
1175 VEC_free (edge_growth_cache_entry
, heap
, edge_growth_cache
);
1176 edge_growth_cache
= 0;
1177 VEC_free (int, heap
, node_growth_cache
);
1178 node_growth_cache
= 0;
1182 /* Dump edge summaries associated to NODE and recursively to all clones.
1183 Indent by INDENT. */
1186 dump_inline_edge_summary (FILE * f
, int indent
, struct cgraph_node
*node
,
1187 struct inline_summary
*info
)
1189 struct cgraph_edge
*edge
;
1190 for (edge
= node
->callees
; edge
; edge
= edge
->next_callee
)
1192 struct inline_edge_summary
*es
= inline_edge_summary (edge
);
1193 struct cgraph_node
*callee
= cgraph_function_or_thunk_node (edge
->callee
, NULL
);
1196 fprintf (f
, "%*s%s/%i %s\n%*s loop depth:%2i freq:%4i size:%2i time: %2i callee size:%2i stack:%2i",
1197 indent
, "", cgraph_node_name (callee
),
1199 !edge
->inline_failed
? "inlined"
1200 : cgraph_inline_failed_string (edge
->inline_failed
),
1206 (int)inline_summary (callee
)->size
/ INLINE_SIZE_SCALE
,
1207 (int)inline_summary (callee
)->estimated_stack_size
);
1211 fprintf (f
, " predicate: ");
1212 dump_predicate (f
, info
->conds
, es
->predicate
);
1217 for (i
= 0; i
< (int)VEC_length (inline_param_summary_t
, es
->param
);
1220 int prob
= VEC_index (inline_param_summary_t
,
1221 es
->param
, i
).change_prob
;
1224 fprintf (f
, "%*s op%i is compile time invariant\n",
1226 else if (prob
!= REG_BR_PROB_BASE
)
1227 fprintf (f
, "%*s op%i change %f%% of time\n", indent
+ 2, "", i
,
1228 prob
* 100.0 / REG_BR_PROB_BASE
);
1230 if (!edge
->inline_failed
)
1232 fprintf (f
, "%*sStack frame offset %i, callee self size %i,"
1233 " callee size %i\n",
1235 (int)inline_summary (callee
)->stack_frame_offset
,
1236 (int)inline_summary (callee
)->estimated_self_stack_size
,
1237 (int)inline_summary (callee
)->estimated_stack_size
);
1238 dump_inline_edge_summary (f
, indent
+2, callee
, info
);
1241 for (edge
= node
->indirect_calls
; edge
; edge
= edge
->next_callee
)
1243 struct inline_edge_summary
*es
= inline_edge_summary (edge
);
1244 fprintf (f
, "%*sindirect call loop depth:%2i freq:%4i size:%2i"
1250 es
->call_stmt_time
);
1253 fprintf (f
, "predicate: ");
1254 dump_predicate (f
, info
->conds
, es
->predicate
);
1263 dump_inline_summary (FILE * f
, struct cgraph_node
*node
)
1267 struct inline_summary
*s
= inline_summary (node
);
1270 fprintf (f
, "Inline summary for %s/%i", cgraph_node_name (node
),
1272 if (DECL_DISREGARD_INLINE_LIMITS (node
->symbol
.decl
))
1273 fprintf (f
, " always_inline");
1275 fprintf (f
, " inlinable");
1276 fprintf (f
, "\n self time: %i\n",
1278 fprintf (f
, " global time: %i\n", s
->time
);
1279 fprintf (f
, " self size: %i\n",
1281 fprintf (f
, " global size: %i\n", s
->size
);
1282 fprintf (f
, " self stack: %i\n",
1283 (int) s
->estimated_self_stack_size
);
1284 fprintf (f
, " global stack: %i\n",
1285 (int) s
->estimated_stack_size
);
1287 VEC_iterate (size_time_entry
, s
->entry
, i
, e
);
1290 fprintf (f
, " size:%f, time:%f, predicate:",
1291 (double) e
->size
/ INLINE_SIZE_SCALE
,
1292 (double) e
->time
/ INLINE_TIME_SCALE
);
1293 dump_predicate (f
, s
->conds
, &e
->predicate
);
1295 fprintf (f
, " calls:\n");
1296 dump_inline_edge_summary (f
, 4, node
, s
);
1302 debug_inline_summary (struct cgraph_node
*node
)
1304 dump_inline_summary (stderr
, node
);
1308 dump_inline_summaries (FILE *f
)
1310 struct cgraph_node
*node
;
1312 FOR_EACH_DEFINED_FUNCTION (node
)
1313 if (!node
->global
.inlined_to
)
1314 dump_inline_summary (f
, node
);
1317 /* Give initial reasons why inlining would fail on EDGE. This gets either
1318 nullified or usually overwritten by more precise reasons later. */
1321 initialize_inline_failed (struct cgraph_edge
*e
)
1323 struct cgraph_node
*callee
= e
->callee
;
1325 if (e
->indirect_unknown_callee
)
1326 e
->inline_failed
= CIF_INDIRECT_UNKNOWN_CALL
;
1327 else if (!callee
->analyzed
)
1328 e
->inline_failed
= CIF_BODY_NOT_AVAILABLE
;
1329 else if (callee
->local
.redefined_extern_inline
)
1330 e
->inline_failed
= CIF_REDEFINED_EXTERN_INLINE
;
1331 else if (e
->call_stmt_cannot_inline_p
)
1332 e
->inline_failed
= CIF_MISMATCHED_ARGUMENTS
;
1334 e
->inline_failed
= CIF_FUNCTION_NOT_CONSIDERED
;
1337 /* Callback of walk_aliased_vdefs. Flags that it has been invoked to the
1338 boolean variable pointed to by DATA. */
1341 mark_modified (ao_ref
*ao ATTRIBUTE_UNUSED
, tree vdef ATTRIBUTE_UNUSED
,
1344 bool *b
= (bool *) data
;
1349 /* If OP refers to value of function parameter, return the corresponding
1353 unmodified_parm_1 (gimple stmt
, tree op
)
1355 /* SSA_NAME referring to parm default def? */
1356 if (TREE_CODE (op
) == SSA_NAME
1357 && SSA_NAME_IS_DEFAULT_DEF (op
)
1358 && TREE_CODE (SSA_NAME_VAR (op
)) == PARM_DECL
)
1359 return SSA_NAME_VAR (op
);
1360 /* Non-SSA parm reference? */
1361 if (TREE_CODE (op
) == PARM_DECL
)
1363 bool modified
= false;
1366 ao_ref_init (&refd
, op
);
1367 walk_aliased_vdefs (&refd
, gimple_vuse (stmt
), mark_modified
, &modified
,
1375 /* If OP refers to value of function parameter, return the corresponding
1376 parameter. Also traverse chains of SSA register assignments. */
1379 unmodified_parm (gimple stmt
, tree op
)
1381 tree res
= unmodified_parm_1 (stmt
, op
);
1385 if (TREE_CODE (op
) == SSA_NAME
1386 && !SSA_NAME_IS_DEFAULT_DEF (op
)
1387 && gimple_assign_single_p (SSA_NAME_DEF_STMT (op
)))
1388 return unmodified_parm (SSA_NAME_DEF_STMT (op
),
1389 gimple_assign_rhs1 (SSA_NAME_DEF_STMT (op
)));
1393 /* If OP refers to a value of a function parameter or value loaded from an
1394 aggregate passed to a parameter (either by value or reference), return TRUE
1395 and store the number of the parameter to *INDEX_P and information whether
1396 and how it has been loaded from an aggregate into *AGGPOS. INFO describes
1397 the function parameters, STMT is the statement in which OP is used or
1401 unmodified_parm_or_parm_agg_item (struct ipa_node_params
*info
,
1402 gimple stmt
, tree op
, int *index_p
,
1403 struct agg_position_info
*aggpos
)
1405 tree res
= unmodified_parm_1 (stmt
, op
);
1407 gcc_checking_assert (aggpos
);
1410 *index_p
= ipa_get_param_decl_index (info
, res
);
1413 aggpos
->agg_contents
= false;
1414 aggpos
->by_ref
= false;
1418 if (TREE_CODE (op
) == SSA_NAME
)
1420 if (SSA_NAME_IS_DEFAULT_DEF (op
)
1421 || !gimple_assign_single_p (SSA_NAME_DEF_STMT (op
)))
1423 stmt
= SSA_NAME_DEF_STMT (op
);
1424 op
= gimple_assign_rhs1 (stmt
);
1425 if (!REFERENCE_CLASS_P (op
))
1426 return unmodified_parm_or_parm_agg_item (info
, stmt
, op
, index_p
,
1430 aggpos
->agg_contents
= true;
1431 return ipa_load_from_parm_agg (info
, stmt
, op
, index_p
, &aggpos
->offset
,
1435 /* See if statement might disappear after inlining.
1436 0 - means not eliminated
1437 1 - half of statements goes away
1438 2 - for sure it is eliminated.
1439 We are not terribly sophisticated, basically looking for simple abstraction
1440 penalty wrappers. */
1443 eliminated_by_inlining_prob (gimple stmt
)
1445 enum gimple_code code
= gimple_code (stmt
);
1455 if (gimple_num_ops (stmt
) != 2)
1458 /* Casts of parameters, loads from parameters passed by reference
1459 and stores to return value or parameters are often free after
1460 inlining dua to SRA and further combining.
1461 Assume that half of statements goes away. */
1462 if (gimple_assign_rhs_code (stmt
) == CONVERT_EXPR
1463 || gimple_assign_rhs_code (stmt
) == NOP_EXPR
1464 || gimple_assign_rhs_code (stmt
) == VIEW_CONVERT_EXPR
1465 || gimple_assign_rhs_class (stmt
) == GIMPLE_SINGLE_RHS
)
1467 tree rhs
= gimple_assign_rhs1 (stmt
);
1468 tree lhs
= gimple_assign_lhs (stmt
);
1469 tree inner_rhs
= get_base_address (rhs
);
1470 tree inner_lhs
= get_base_address (lhs
);
1471 bool rhs_free
= false;
1472 bool lhs_free
= false;
1479 /* Reads of parameter are expected to be free. */
1480 if (unmodified_parm (stmt
, inner_rhs
))
1483 /* When parameter is not SSA register because its address is taken
1484 and it is just copied into one, the statement will be completely
1485 free after inlining (we will copy propagate backward). */
1486 if (rhs_free
&& is_gimple_reg (lhs
))
1489 /* Reads of parameters passed by reference
1490 expected to be free (i.e. optimized out after inlining). */
1491 if (TREE_CODE(inner_rhs
) == MEM_REF
1492 && unmodified_parm (stmt
, TREE_OPERAND (inner_rhs
, 0)))
1495 /* Copying parameter passed by reference into gimple register is
1496 probably also going to copy propagate, but we can't be quite
1498 if (rhs_free
&& is_gimple_reg (lhs
))
1501 /* Writes to parameters, parameters passed by value and return value
1502 (either dirrectly or passed via invisible reference) are free.
1504 TODO: We ought to handle testcase like
1505 struct a {int a,b;};
1507 retrurnsturct (void)
1513 This translate into:
1528 For that we either need to copy ipa-split logic detecting writes
1530 if (TREE_CODE (inner_lhs
) == PARM_DECL
1531 || TREE_CODE (inner_lhs
) == RESULT_DECL
1532 || (TREE_CODE(inner_lhs
) == MEM_REF
1533 && (unmodified_parm (stmt
, TREE_OPERAND (inner_lhs
, 0))
1534 || (TREE_CODE (TREE_OPERAND (inner_lhs
, 0)) == SSA_NAME
1535 && SSA_NAME_VAR (TREE_OPERAND (inner_lhs
, 0))
1536 && TREE_CODE (SSA_NAME_VAR (TREE_OPERAND
1537 (inner_lhs
, 0))) == RESULT_DECL
))))
1540 && (is_gimple_reg (rhs
) || is_gimple_min_invariant (rhs
)))
1542 if (lhs_free
&& rhs_free
)
1552 /* If BB ends by a conditional we can turn into predicates, attach corresponding
1553 predicates to the CFG edges. */
1556 set_cond_stmt_execution_predicate (struct ipa_node_params
*info
,
1557 struct inline_summary
*summary
,
1563 struct agg_position_info aggpos
;
1564 enum tree_code code
, inverted_code
;
1570 last
= last_stmt (bb
);
1572 || gimple_code (last
) != GIMPLE_COND
)
1574 if (!is_gimple_ip_invariant (gimple_cond_rhs (last
)))
1576 op
= gimple_cond_lhs (last
);
1577 /* TODO: handle conditionals like
1580 if (unmodified_parm_or_parm_agg_item (info
, last
, op
, &index
, &aggpos
))
1582 code
= gimple_cond_code (last
);
1584 = invert_tree_comparison (code
,
1585 HONOR_NANS (TYPE_MODE (TREE_TYPE (op
))));
1587 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1589 struct predicate p
= add_condition (summary
, index
, &aggpos
,
1590 e
->flags
& EDGE_TRUE_VALUE
1591 ? code
: inverted_code
,
1592 gimple_cond_rhs (last
));
1593 e
->aux
= pool_alloc (edge_predicate_pool
);
1594 *(struct predicate
*)e
->aux
= p
;
1598 if (TREE_CODE (op
) != SSA_NAME
)
1601 if (builtin_constant_p (op))
1605 Here we can predicate nonconstant_code. We can't
1606 really handle constant_code since we have no predicate
1607 for this and also the constant code is not known to be
1608 optimized away when inliner doen't see operand is constant.
1609 Other optimizers might think otherwise. */
1610 if (gimple_cond_code (last
) != NE_EXPR
1611 || !integer_zerop (gimple_cond_rhs (last
)))
1613 set_stmt
= SSA_NAME_DEF_STMT (op
);
1614 if (!gimple_call_builtin_p (set_stmt
, BUILT_IN_CONSTANT_P
)
1615 || gimple_call_num_args (set_stmt
) != 1)
1617 op2
= gimple_call_arg (set_stmt
, 0);
1618 if (!unmodified_parm_or_parm_agg_item (info
, set_stmt
, op2
, &index
, &aggpos
))
1620 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1621 if (e
->flags
& EDGE_FALSE_VALUE
)
1623 struct predicate p
= add_condition (summary
, index
, &aggpos
,
1624 IS_NOT_CONSTANT
, NULL_TREE
);
1625 e
->aux
= pool_alloc (edge_predicate_pool
);
1626 *(struct predicate
*)e
->aux
= p
;
1631 /* If BB ends by a switch we can turn into predicates, attach corresponding
1632 predicates to the CFG edges. */
1635 set_switch_stmt_execution_predicate (struct ipa_node_params
*info
,
1636 struct inline_summary
*summary
,
1642 struct agg_position_info aggpos
;
1648 last
= last_stmt (bb
);
1650 || gimple_code (last
) != GIMPLE_SWITCH
)
1652 op
= gimple_switch_index (last
);
1653 if (!unmodified_parm_or_parm_agg_item (info
, last
, op
, &index
, &aggpos
))
1656 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1658 e
->aux
= pool_alloc (edge_predicate_pool
);
1659 *(struct predicate
*)e
->aux
= false_predicate ();
1661 n
= gimple_switch_num_labels(last
);
1662 for (case_idx
= 0; case_idx
< n
; ++case_idx
)
1664 tree cl
= gimple_switch_label (last
, case_idx
);
1668 e
= find_edge (bb
, label_to_block (CASE_LABEL (cl
)));
1669 min
= CASE_LOW (cl
);
1670 max
= CASE_HIGH (cl
);
1672 /* For default we might want to construct predicate that none
1673 of cases is met, but it is bit hard to do not having negations
1674 of conditionals handy. */
1676 p
= true_predicate ();
1678 p
= add_condition (summary
, index
, &aggpos
, EQ_EXPR
, min
);
1681 struct predicate p1
, p2
;
1682 p1
= add_condition (summary
, index
, &aggpos
, GE_EXPR
, min
);
1683 p2
= add_condition (summary
, index
, &aggpos
, LE_EXPR
, max
);
1684 p
= and_predicates (summary
->conds
, &p1
, &p2
);
1686 *(struct predicate
*)e
->aux
1687 = or_predicates (summary
->conds
, &p
, (struct predicate
*)e
->aux
);
1692 /* For each BB in NODE attach to its AUX pointer predicate under
1693 which it is executable. */
1696 compute_bb_predicates (struct cgraph_node
*node
,
1697 struct ipa_node_params
*parms_info
,
1698 struct inline_summary
*summary
)
1700 struct function
*my_function
= DECL_STRUCT_FUNCTION (node
->symbol
.decl
);
1704 FOR_EACH_BB_FN (bb
, my_function
)
1706 set_cond_stmt_execution_predicate (parms_info
, summary
, bb
);
1707 set_switch_stmt_execution_predicate (parms_info
, summary
, bb
);
1710 /* Entry block is always executable. */
1711 ENTRY_BLOCK_PTR_FOR_FUNCTION (my_function
)->aux
1712 = pool_alloc (edge_predicate_pool
);
1713 *(struct predicate
*)ENTRY_BLOCK_PTR_FOR_FUNCTION (my_function
)->aux
1714 = true_predicate ();
1716 /* A simple dataflow propagation of predicates forward in the CFG.
1717 TODO: work in reverse postorder. */
1721 FOR_EACH_BB_FN (bb
, my_function
)
1723 struct predicate p
= false_predicate ();
1726 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
1730 struct predicate this_bb_predicate
1731 = *(struct predicate
*)e
->src
->aux
;
1734 = and_predicates (summary
->conds
, &this_bb_predicate
,
1735 (struct predicate
*)e
->aux
);
1736 p
= or_predicates (summary
->conds
, &p
, &this_bb_predicate
);
1737 if (true_predicate_p (&p
))
1741 if (false_predicate_p (&p
))
1742 gcc_assert (!bb
->aux
);
1748 bb
->aux
= pool_alloc (edge_predicate_pool
);
1749 *((struct predicate
*)bb
->aux
) = p
;
1751 else if (!predicates_equal_p (&p
, (struct predicate
*)bb
->aux
))
1754 *((struct predicate
*)bb
->aux
) = p
;
1762 /* We keep info about constantness of SSA names. */
1764 typedef struct predicate predicate_t
;
1765 DEF_VEC_O (predicate_t
);
1766 DEF_VEC_ALLOC_O (predicate_t
, heap
);
1769 /* Return predicate specifying when the STMT might have result that is not
1770 a compile time constant. */
1772 static struct predicate
1773 will_be_nonconstant_predicate (struct ipa_node_params
*info
,
1774 struct inline_summary
*summary
,
1776 VEC (predicate_t
, heap
) *nonconstant_names
)
1778 struct predicate p
= true_predicate ();
1781 struct predicate op_non_const
;
1784 struct agg_position_info aggpos
;
1786 /* What statments might be optimized away
1787 when their arguments are constant
1788 TODO: also trivial builtins.
1789 builtin_constant_p is already handled later. */
1790 if (gimple_code (stmt
) != GIMPLE_ASSIGN
1791 && gimple_code (stmt
) != GIMPLE_COND
1792 && gimple_code (stmt
) != GIMPLE_SWITCH
)
1795 /* Stores will stay anyway. */
1796 if (gimple_vdef (stmt
))
1799 is_load
= gimple_vuse (stmt
) != NULL
;
1800 /* Loads can be optimized when the value is known. */
1804 gcc_assert (gimple_assign_single_p (stmt
));
1805 op
= gimple_assign_rhs1 (stmt
);
1806 if (!unmodified_parm_or_parm_agg_item (info
, stmt
, op
, &base_index
,
1813 /* See if we understand all operands before we start
1814 adding conditionals. */
1815 FOR_EACH_SSA_TREE_OPERAND (use
, stmt
, iter
, SSA_OP_USE
)
1817 tree parm
= unmodified_parm (stmt
, use
);
1818 /* For arguments we can build a condition. */
1819 if (parm
&& ipa_get_param_decl_index (info
, parm
) >= 0)
1821 if (TREE_CODE (use
) != SSA_NAME
)
1823 /* If we know when operand is constant,
1824 we still can say something useful. */
1825 if (!true_predicate_p (&VEC_index (predicate_t
, nonconstant_names
,
1826 SSA_NAME_VERSION (use
))))
1832 op_non_const
= add_condition (summary
, base_index
, &aggpos
, CHANGED
, NULL
);
1834 op_non_const
= false_predicate ();
1835 FOR_EACH_SSA_TREE_OPERAND (use
, stmt
, iter
, SSA_OP_USE
)
1837 tree parm
= unmodified_parm (stmt
, use
);
1841 && (index
= ipa_get_param_decl_index (info
, parm
)) >= 0)
1843 if (index
!= base_index
)
1844 p
= add_condition (summary
, index
, NULL
, CHANGED
, NULL_TREE
);
1849 p
= VEC_index (predicate_t
, nonconstant_names
,
1850 SSA_NAME_VERSION (use
));
1851 op_non_const
= or_predicates (summary
->conds
, &p
, &op_non_const
);
1853 if (gimple_code (stmt
) == GIMPLE_ASSIGN
1854 && TREE_CODE (gimple_assign_lhs (stmt
)) == SSA_NAME
)
1855 VEC_replace (predicate_t
, nonconstant_names
,
1856 SSA_NAME_VERSION (gimple_assign_lhs (stmt
)), op_non_const
);
1857 return op_non_const
;
1860 struct record_modified_bb_info
1866 /* Callback of walk_aliased_vdefs. Records basic blocks where the value may be
1867 set except for info->stmt. */
1870 record_modified (ao_ref
*ao ATTRIBUTE_UNUSED
, tree vdef
,
1873 struct record_modified_bb_info
*info
= (struct record_modified_bb_info
*) data
;
1874 if (SSA_NAME_DEF_STMT (vdef
) == info
->stmt
)
1876 bitmap_set_bit (info
->bb_set
,
1877 SSA_NAME_IS_DEFAULT_DEF (vdef
)
1878 ? ENTRY_BLOCK_PTR
->index
: gimple_bb (SSA_NAME_DEF_STMT (vdef
))->index
);
1882 /* Return probability (based on REG_BR_PROB_BASE) that I-th parameter of STMT
1883 will change since last invocation of STMT.
1885 Value 0 is reserved for compile time invariants.
1886 For common parameters it is REG_BR_PROB_BASE. For loop invariants it
1887 ought to be REG_BR_PROB_BASE / estimated_iters. */
1890 param_change_prob (gimple stmt
, int i
)
1892 tree op
= gimple_call_arg (stmt
, i
);
1893 basic_block bb
= gimple_bb (stmt
);
1896 if (is_gimple_min_invariant (op
))
1898 /* We would have to do non-trivial analysis to really work out what
1899 is the probability of value to change (i.e. when init statement
1900 is in a sibling loop of the call).
1902 We do an conservative estimate: when call is executed N times more often
1903 than the statement defining value, we take the frequency 1/N. */
1904 if (TREE_CODE (op
) == SSA_NAME
)
1909 return REG_BR_PROB_BASE
;
1911 if (SSA_NAME_IS_DEFAULT_DEF (op
))
1912 init_freq
= ENTRY_BLOCK_PTR
->frequency
;
1914 init_freq
= gimple_bb (SSA_NAME_DEF_STMT (op
))->frequency
;
1918 if (init_freq
< bb
->frequency
)
1919 return MAX ((init_freq
* REG_BR_PROB_BASE
+
1920 bb
->frequency
/ 2) / bb
->frequency
, 1);
1922 return REG_BR_PROB_BASE
;
1925 base
= get_base_address (op
);
1930 struct record_modified_bb_info info
;
1934 if (const_value_known_p (base
))
1937 return REG_BR_PROB_BASE
;
1938 ao_ref_init (&refd
, op
);
1940 info
.bb_set
= BITMAP_ALLOC (NULL
);
1941 walk_aliased_vdefs (&refd
, gimple_vuse (stmt
), record_modified
, &info
,
1943 if (bitmap_bit_p (info
.bb_set
, bb
->index
))
1945 BITMAP_FREE (info
.bb_set
);
1946 return REG_BR_PROB_BASE
;
1949 /* Assume that every memory is initialized at entry.
1950 TODO: Can we easilly determine if value is always defined
1951 and thus we may skip entry block? */
1952 if (ENTRY_BLOCK_PTR
->frequency
)
1953 max
= ENTRY_BLOCK_PTR
->frequency
;
1957 EXECUTE_IF_SET_IN_BITMAP (info
.bb_set
, 0, index
, bi
)
1958 max
= MIN (max
, BASIC_BLOCK (index
)->frequency
);
1960 BITMAP_FREE (info
.bb_set
);
1961 if (max
< bb
->frequency
)
1962 return MAX ((max
* REG_BR_PROB_BASE
+
1963 bb
->frequency
/ 2) / bb
->frequency
, 1);
1965 return REG_BR_PROB_BASE
;
1967 return REG_BR_PROB_BASE
;
1971 /* Compute function body size parameters for NODE.
1972 When EARLY is true, we compute only simple summaries without
1973 non-trivial predicates to drive the early inliner. */
1976 estimate_function_body_sizes (struct cgraph_node
*node
, bool early
)
1979 /* Estimate static overhead for function prologue/epilogue and alignment. */
1981 /* Benefits are scaled by probability of elimination that is in range
1984 gimple_stmt_iterator bsi
;
1985 struct function
*my_function
= DECL_STRUCT_FUNCTION (node
->symbol
.decl
);
1987 struct inline_summary
*info
= inline_summary (node
);
1988 struct predicate bb_predicate
;
1989 struct ipa_node_params
*parms_info
= NULL
;
1990 VEC (predicate_t
, heap
) *nonconstant_names
= NULL
;
1992 if (ipa_node_params_vector
&& !early
&& optimize
)
1994 parms_info
= IPA_NODE_REF (node
);
1995 VEC_safe_grow_cleared (predicate_t
, heap
, nonconstant_names
,
1996 VEC_length (tree
, SSANAMES (my_function
)));
2004 fprintf (dump_file
, "\nAnalyzing function body size: %s\n",
2005 cgraph_node_name (node
));
2007 /* When we run into maximal number of entries, we assign everything to the
2008 constant truth case. Be sure to have it in list. */
2009 bb_predicate
= true_predicate ();
2010 account_size_time (info
, 0, 0, &bb_predicate
);
2012 bb_predicate
= not_inlined_predicate ();
2013 account_size_time (info
, 2 * INLINE_SIZE_SCALE
, 0, &bb_predicate
);
2015 gcc_assert (my_function
&& my_function
->cfg
);
2017 compute_bb_predicates (node
, parms_info
, info
);
2018 FOR_EACH_BB_FN (bb
, my_function
)
2020 freq
= compute_call_stmt_bb_frequency (node
->symbol
.decl
, bb
);
2022 /* TODO: Obviously predicates can be propagated down across CFG. */
2026 bb_predicate
= *(struct predicate
*)bb
->aux
;
2028 bb_predicate
= false_predicate ();
2031 bb_predicate
= true_predicate ();
2033 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2035 fprintf (dump_file
, "\n BB %i predicate:", bb
->index
);
2036 dump_predicate (dump_file
, info
->conds
, &bb_predicate
);
2039 for (bsi
= gsi_start_bb (bb
); !gsi_end_p (bsi
); gsi_next (&bsi
))
2041 gimple stmt
= gsi_stmt (bsi
);
2042 int this_size
= estimate_num_insns (stmt
, &eni_size_weights
);
2043 int this_time
= estimate_num_insns (stmt
, &eni_time_weights
);
2045 struct predicate will_be_nonconstant
;
2047 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2049 fprintf (dump_file
, " ");
2050 print_gimple_stmt (dump_file
, stmt
, 0, 0);
2051 fprintf (dump_file
, "\t\tfreq:%3.2f size:%3i time:%3i\n",
2052 ((double)freq
)/CGRAPH_FREQ_BASE
, this_size
, this_time
);
2055 if (is_gimple_call (stmt
))
2057 struct cgraph_edge
*edge
= cgraph_edge (node
, stmt
);
2058 struct inline_edge_summary
*es
= inline_edge_summary (edge
);
2060 /* Special case: results of BUILT_IN_CONSTANT_P will be always
2061 resolved as constant. We however don't want to optimize
2062 out the cgraph edges. */
2063 if (nonconstant_names
2064 && gimple_call_builtin_p (stmt
, BUILT_IN_CONSTANT_P
)
2065 && gimple_call_lhs (stmt
)
2066 && TREE_CODE (gimple_call_lhs (stmt
)) == SSA_NAME
)
2068 struct predicate false_p
= false_predicate ();
2069 VEC_replace (predicate_t
, nonconstant_names
,
2070 SSA_NAME_VERSION (gimple_call_lhs (stmt
)),
2073 if (ipa_node_params_vector
)
2075 int count
= gimple_call_num_args (stmt
);
2079 VEC_safe_grow_cleared (inline_param_summary_t
, heap
,
2081 for (i
= 0; i
< count
; i
++)
2083 int prob
= param_change_prob (stmt
, i
);
2084 gcc_assert (prob
>= 0 && prob
<= REG_BR_PROB_BASE
);
2085 VEC_index (inline_param_summary_t
,
2086 es
->param
, i
).change_prob
= prob
;
2090 es
->call_stmt_size
= this_size
;
2091 es
->call_stmt_time
= this_time
;
2092 es
->loop_depth
= bb_loop_depth (bb
);
2093 edge_set_predicate (edge
, &bb_predicate
);
2096 /* TODO: When conditional jump or swithc is known to be constant, but
2097 we did not translate it into the predicates, we really can account
2098 just maximum of the possible paths. */
2101 = will_be_nonconstant_predicate (parms_info
, info
,
2102 stmt
, nonconstant_names
);
2103 if (this_time
|| this_size
)
2111 prob
= eliminated_by_inlining_prob (stmt
);
2112 if (prob
== 1 && dump_file
&& (dump_flags
& TDF_DETAILS
))
2113 fprintf (dump_file
, "\t\t50%% will be eliminated by inlining\n");
2114 if (prob
== 2 && dump_file
&& (dump_flags
& TDF_DETAILS
))
2115 fprintf (dump_file
, "\t\tWill be eliminated by inlining\n");
2118 p
= and_predicates (info
->conds
, &bb_predicate
,
2119 &will_be_nonconstant
);
2121 p
= true_predicate ();
2123 /* We account everything but the calls. Calls have their own
2124 size/time info attached to cgraph edges. This is necessary
2125 in order to make the cost disappear after inlining. */
2126 if (!is_gimple_call (stmt
))
2130 struct predicate ip
= not_inlined_predicate ();
2131 ip
= and_predicates (info
->conds
, &ip
, &p
);
2132 account_size_time (info
, this_size
* prob
,
2133 this_time
* prob
, &ip
);
2136 account_size_time (info
, this_size
* (2 - prob
),
2137 this_time
* (2 - prob
), &p
);
2140 gcc_assert (time
>= 0);
2141 gcc_assert (size
>= 0);
2145 FOR_ALL_BB_FN (bb
, my_function
)
2151 pool_free (edge_predicate_pool
, bb
->aux
);
2153 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
2156 pool_free (edge_predicate_pool
, e
->aux
);
2160 time
= (time
+ CGRAPH_FREQ_BASE
/ 2) / CGRAPH_FREQ_BASE
;
2161 if (time
> MAX_TIME
)
2163 inline_summary (node
)->self_time
= time
;
2164 inline_summary (node
)->self_size
= size
;
2165 VEC_free (predicate_t
, heap
, nonconstant_names
);
2168 fprintf (dump_file
, "\n");
2169 dump_inline_summary (dump_file
, node
);
2174 /* Compute parameters of functions used by inliner.
2175 EARLY is true when we compute parameters for the early inliner */
2178 compute_inline_parameters (struct cgraph_node
*node
, bool early
)
2180 HOST_WIDE_INT self_stack_size
;
2181 struct cgraph_edge
*e
;
2182 struct inline_summary
*info
;
2183 tree old_decl
= current_function_decl
;
2185 gcc_assert (!node
->global
.inlined_to
);
2187 inline_summary_alloc ();
2189 info
= inline_summary (node
);
2190 reset_inline_summary (node
);
2192 /* FIXME: Thunks are inlinable, but tree-inline don't know how to do that.
2193 Once this happen, we will need to more curefully predict call
2195 if (node
->thunk
.thunk_p
)
2197 struct inline_edge_summary
*es
= inline_edge_summary (node
->callees
);
2198 struct predicate t
= true_predicate ();
2200 info
->inlinable
= 0;
2201 node
->callees
->call_stmt_cannot_inline_p
= true;
2202 node
->local
.can_change_signature
= false;
2203 es
->call_stmt_time
= 1;
2204 es
->call_stmt_size
= 1;
2205 account_size_time (info
, 0, 0, &t
);
2209 /* Even is_gimple_min_invariant rely on current_function_decl. */
2210 current_function_decl
= node
->symbol
.decl
;
2211 push_cfun (DECL_STRUCT_FUNCTION (node
->symbol
.decl
));
2213 /* Estimate the stack size for the function if we're optimizing. */
2214 self_stack_size
= optimize
? estimated_stack_frame_size (node
) : 0;
2215 info
->estimated_self_stack_size
= self_stack_size
;
2216 info
->estimated_stack_size
= self_stack_size
;
2217 info
->stack_frame_offset
= 0;
2219 /* Can this function be inlined at all? */
2220 info
->inlinable
= tree_inlinable_function_p (node
->symbol
.decl
);
2222 /* Type attributes can use parameter indices to describe them. */
2223 if (TYPE_ATTRIBUTES (TREE_TYPE (node
->symbol
.decl
)))
2224 node
->local
.can_change_signature
= false;
2227 /* Otherwise, inlinable functions always can change signature. */
2228 if (info
->inlinable
)
2229 node
->local
.can_change_signature
= true;
2232 /* Functions calling builtin_apply can not change signature. */
2233 for (e
= node
->callees
; e
; e
= e
->next_callee
)
2235 tree
cdecl = e
->callee
->symbol
.decl
;
2236 if (DECL_BUILT_IN (cdecl)
2237 && DECL_BUILT_IN_CLASS (cdecl) == BUILT_IN_NORMAL
2238 && (DECL_FUNCTION_CODE (cdecl) == BUILT_IN_APPLY_ARGS
2239 || DECL_FUNCTION_CODE (cdecl) == BUILT_IN_VA_START
))
2242 node
->local
.can_change_signature
= !e
;
2245 estimate_function_body_sizes (node
, early
);
2247 /* Inlining characteristics are maintained by the cgraph_mark_inline. */
2248 info
->time
= info
->self_time
;
2249 info
->size
= info
->self_size
;
2250 info
->stack_frame_offset
= 0;
2251 info
->estimated_stack_size
= info
->estimated_self_stack_size
;
2252 current_function_decl
= old_decl
;
2257 /* Compute parameters of functions used by inliner using
2258 current_function_decl. */
2261 compute_inline_parameters_for_current (void)
2263 compute_inline_parameters (cgraph_get_node (current_function_decl
), true);
2267 struct gimple_opt_pass pass_inline_parameters
=
2271 "inline_param", /* name */
2273 compute_inline_parameters_for_current
,/* execute */
2276 0, /* static_pass_number */
2277 TV_INLINE_PARAMETERS
, /* tv_id */
2278 0, /* properties_required */
2279 0, /* properties_provided */
2280 0, /* properties_destroyed */
2281 0, /* todo_flags_start */
2282 0 /* todo_flags_finish */
2287 /* Increase SIZE and TIME for size and time needed to handle edge E. */
2290 estimate_edge_size_and_time (struct cgraph_edge
*e
, int *size
, int *time
,
2293 struct inline_edge_summary
*es
= inline_edge_summary (e
);
2294 *size
+= es
->call_stmt_size
* INLINE_SIZE_SCALE
;
2295 *time
+= (es
->call_stmt_time
* prob
/ REG_BR_PROB_BASE
2296 * e
->frequency
* (INLINE_TIME_SCALE
/ CGRAPH_FREQ_BASE
));
2297 if (*time
> MAX_TIME
* INLINE_TIME_SCALE
)
2298 *time
= MAX_TIME
* INLINE_TIME_SCALE
;
2302 /* Estimate benefit devirtualizing indirect edge IE, provided KNOWN_VALS and
2306 estimate_edge_devirt_benefit (struct cgraph_edge
*ie
,
2307 int *size
, int *time
, int prob
,
2308 VEC (tree
, heap
) *known_vals
,
2309 VEC (tree
, heap
) *known_binfos
,
2310 VEC (ipa_agg_jump_function_p
, heap
) *known_aggs
)
2313 int time_diff
, size_diff
;
2315 if (!known_vals
&& !known_binfos
)
2318 target
= ipa_get_indirect_edge_target (ie
, known_vals
, known_binfos
,
2323 /* Account for difference in cost between indirect and direct calls. */
2324 size_diff
= ((eni_size_weights
.indirect_call_cost
- eni_size_weights
.call_cost
)
2325 * INLINE_SIZE_SCALE
);
2327 time_diff
= ((eni_time_weights
.indirect_call_cost
- eni_time_weights
.call_cost
)
2328 * INLINE_TIME_SCALE
* prob
/ REG_BR_PROB_BASE
);
2331 /* TODO: This code is trying to benefit indirect calls that will be inlined later.
2332 The logic however do not belong into local size/time estimates and can not be
2333 done here, or the accounting of changes will get wrong and we result with
2334 negative function body sizes. We need to introduce infrastructure for independent
2335 benefits to the inliner. */
2337 struct cgraph_node
*callee
;
2338 struct inline_summary
*isummary
;
2339 int edge_size
, edge_time
, time_diff
, size_diff
;
2341 callee
= cgraph_get_node (target
);
2342 if (!callee
|| !callee
->analyzed
)
2344 isummary
= inline_summary (callee
);
2345 if (!isummary
->inlinable
)
2348 estimate_edge_size_and_time (ie
, &edge_size
, &edge_time
, prob
);
2350 /* Count benefit only from functions that definitely will be inlined
2351 if additional context from NODE's caller were available.
2353 We just account overall size change by inlining. TODO:
2354 we really need to add sort of benefit metrics for these kind of
2356 if (edge_size
- size_diff
>= isummary
->size
* INLINE_SIZE_SCALE
)
2358 /* Subtract size and time that we added for edge IE. */
2359 *size
-= edge_size
- size_diff
;
2361 /* Account inlined call. */
2362 *size
+= isummary
->size
* INLINE_SIZE_SCALE
;
2368 /* Increase SIZE and TIME for size and time needed to handle all calls in NODE.
2369 POSSIBLE_TRUTHS, KNOWN_VALS and KNOWN_BINFOS describe context of the call
2373 estimate_calls_size_and_time (struct cgraph_node
*node
, int *size
, int *time
,
2374 clause_t possible_truths
,
2375 VEC (tree
, heap
) *known_vals
,
2376 VEC (tree
, heap
) *known_binfos
,
2377 VEC (ipa_agg_jump_function_p
, heap
) *known_aggs
)
2379 struct cgraph_edge
*e
;
2380 for (e
= node
->callees
; e
; e
= e
->next_callee
)
2382 struct inline_edge_summary
*es
= inline_edge_summary (e
);
2383 if (!es
->predicate
|| evaluate_predicate (es
->predicate
, possible_truths
))
2385 if (e
->inline_failed
)
2387 /* Predicates of calls shall not use NOT_CHANGED codes,
2388 sowe do not need to compute probabilities. */
2389 estimate_edge_size_and_time (e
, size
, time
, REG_BR_PROB_BASE
);
2392 estimate_calls_size_and_time (e
->callee
, size
, time
,
2394 known_vals
, known_binfos
, known_aggs
);
2397 for (e
= node
->indirect_calls
; e
; e
= e
->next_callee
)
2399 struct inline_edge_summary
*es
= inline_edge_summary (e
);
2400 if (!es
->predicate
|| evaluate_predicate (es
->predicate
, possible_truths
))
2402 estimate_edge_size_and_time (e
, size
, time
, REG_BR_PROB_BASE
);
2403 estimate_edge_devirt_benefit (e
, size
, time
, REG_BR_PROB_BASE
,
2404 known_vals
, known_binfos
, known_aggs
);
2410 /* Estimate size and time needed to execute NODE assuming
2411 POSSIBLE_TRUTHS clause, and KNOWN_VALS and KNOWN_BINFOS information
2412 about NODE's arguments. */
2415 estimate_node_size_and_time (struct cgraph_node
*node
,
2416 clause_t possible_truths
,
2417 VEC (tree
, heap
) *known_vals
,
2418 VEC (tree
, heap
) *known_binfos
,
2419 VEC (ipa_agg_jump_function_p
, heap
) *known_aggs
,
2420 int *ret_size
, int *ret_time
,
2421 VEC (inline_param_summary_t
, heap
)
2422 *inline_param_summary
)
2424 struct inline_summary
*info
= inline_summary (node
);
2426 int size
= 0, time
= 0;
2430 && (dump_flags
& TDF_DETAILS
))
2433 fprintf (dump_file
, " Estimating body: %s/%i\n"
2434 " Known to be false: ",
2435 cgraph_node_name (node
),
2438 for (i
= predicate_not_inlined_condition
;
2439 i
< (predicate_first_dynamic_condition
2440 + (int)VEC_length (condition
, info
->conds
)); i
++)
2441 if (!(possible_truths
& (1 << i
)))
2444 fprintf (dump_file
, ", ");
2446 dump_condition (dump_file
, info
->conds
, i
);
2450 for (i
= 0; VEC_iterate (size_time_entry
, info
->entry
, i
, e
); i
++)
2451 if (evaluate_predicate (&e
->predicate
, possible_truths
))
2454 if (!inline_param_summary
)
2458 int prob
= predicate_probability (info
->conds
,
2461 inline_param_summary
);
2462 time
+= e
->time
* prob
/ REG_BR_PROB_BASE
;
2467 if (time
> MAX_TIME
* INLINE_TIME_SCALE
)
2468 time
= MAX_TIME
* INLINE_TIME_SCALE
;
2470 estimate_calls_size_and_time (node
, &size
, &time
, possible_truths
,
2471 known_vals
, known_binfos
, known_aggs
);
2472 time
= (time
+ INLINE_TIME_SCALE
/ 2) / INLINE_TIME_SCALE
;
2473 size
= (size
+ INLINE_SIZE_SCALE
/ 2) / INLINE_SIZE_SCALE
;
2477 && (dump_flags
& TDF_DETAILS
))
2478 fprintf (dump_file
, "\n size:%i time:%i\n", size
, time
);
2487 /* Estimate size and time needed to execute callee of EDGE assuming that
2488 parameters known to be constant at caller of EDGE are propagated.
2489 KNOWN_VALS and KNOWN_BINFOS are vectors of assumed known constant values
2490 and types for parameters. */
2493 estimate_ipcp_clone_size_and_time (struct cgraph_node
*node
,
2494 VEC (tree
, heap
) *known_vals
,
2495 VEC (tree
, heap
) *known_binfos
,
2496 int *ret_size
, int *ret_time
)
2500 clause
= evaluate_conditions_for_known_args (node
, false, known_vals
, NULL
);
2501 estimate_node_size_and_time (node
, clause
, known_vals
, known_binfos
, NULL
,
2506 /* Translate all conditions from callee representation into caller
2507 representation and symbolically evaluate predicate P into new predicate.
2509 INFO is inline_summary of function we are adding predicate into, CALLEE_INFO
2510 is summary of function predicate P is from. OPERAND_MAP is array giving
2511 callee formal IDs the caller formal IDs. POSSSIBLE_TRUTHS is clausule of all
2512 callee conditions that may be true in caller context. TOPLEV_PREDICATE is
2513 predicate under which callee is executed. OFFSET_MAP is an array of of
2514 offsets that need to be added to conditions, negative offset means that
2515 conditions relying on values passed by reference have to be discarded
2516 because they might not be preserved (and should be considered offset zero
2517 for other purposes). */
2519 static struct predicate
2520 remap_predicate (struct inline_summary
*info
,
2521 struct inline_summary
*callee_info
,
2522 struct predicate
*p
,
2523 VEC (int, heap
) *operand_map
,
2524 VEC (int, heap
) *offset_map
,
2525 clause_t possible_truths
,
2526 struct predicate
*toplev_predicate
)
2529 struct predicate out
= true_predicate ();
2531 /* True predicate is easy. */
2532 if (true_predicate_p (p
))
2533 return *toplev_predicate
;
2534 for (i
= 0; p
->clause
[i
]; i
++)
2536 clause_t clause
= p
->clause
[i
];
2538 struct predicate clause_predicate
= false_predicate ();
2540 gcc_assert (i
< MAX_CLAUSES
);
2542 for (cond
= 0; cond
< NUM_CONDITIONS
; cond
++)
2543 /* Do we have condition we can't disprove? */
2544 if (clause
& possible_truths
& (1 << cond
))
2546 struct predicate cond_predicate
;
2547 /* Work out if the condition can translate to predicate in the
2548 inlined function. */
2549 if (cond
>= predicate_first_dynamic_condition
)
2551 struct condition
*c
;
2553 c
= &VEC_index (condition
, callee_info
->conds
,
2554 cond
- predicate_first_dynamic_condition
);
2555 /* See if we can remap condition operand to caller's operand.
2556 Otherwise give up. */
2558 || (int)VEC_length (int, operand_map
) <= c
->operand_num
2559 || VEC_index (int, operand_map
, c
->operand_num
) == -1
2560 || (!c
->agg_contents
2561 && VEC_index (int, offset_map
, c
->operand_num
) != 0)
2562 || (c
->agg_contents
&& c
->by_ref
2563 && VEC_index (int, offset_map
, c
->operand_num
) < 0))
2564 cond_predicate
= true_predicate ();
2567 struct agg_position_info ap
;
2568 HOST_WIDE_INT offset_delta
= VEC_index (int, offset_map
,
2570 if (offset_delta
< 0)
2572 gcc_checking_assert (!c
->agg_contents
|| !c
->by_ref
);
2575 gcc_assert (!c
->agg_contents
2577 || offset_delta
== 0);
2578 ap
.offset
= c
->offset
+ offset_delta
;
2579 ap
.agg_contents
= c
->agg_contents
;
2580 ap
.by_ref
= c
->by_ref
;
2581 cond_predicate
= add_condition (info
,
2585 &ap
, c
->code
, c
->val
);
2588 /* Fixed conditions remains same, construct single
2589 condition predicate. */
2592 cond_predicate
.clause
[0] = 1 << cond
;
2593 cond_predicate
.clause
[1] = 0;
2595 clause_predicate
= or_predicates (info
->conds
, &clause_predicate
,
2598 out
= and_predicates (info
->conds
, &out
, &clause_predicate
);
2600 return and_predicates (info
->conds
, &out
, toplev_predicate
);
2604 /* Update summary information of inline clones after inlining.
2605 Compute peak stack usage. */
2608 inline_update_callee_summaries (struct cgraph_node
*node
,
2611 struct cgraph_edge
*e
;
2612 struct inline_summary
*callee_info
= inline_summary (node
);
2613 struct inline_summary
*caller_info
= inline_summary (node
->callers
->caller
);
2616 callee_info
->stack_frame_offset
2617 = caller_info
->stack_frame_offset
2618 + caller_info
->estimated_self_stack_size
;
2619 peak
= callee_info
->stack_frame_offset
2620 + callee_info
->estimated_self_stack_size
;
2621 if (inline_summary (node
->global
.inlined_to
)->estimated_stack_size
2623 inline_summary (node
->global
.inlined_to
)->estimated_stack_size
= peak
;
2624 cgraph_propagate_frequency (node
);
2625 for (e
= node
->callees
; e
; e
= e
->next_callee
)
2627 if (!e
->inline_failed
)
2628 inline_update_callee_summaries (e
->callee
, depth
);
2629 inline_edge_summary (e
)->loop_depth
+= depth
;
2631 for (e
= node
->indirect_calls
; e
; e
= e
->next_callee
)
2632 inline_edge_summary (e
)->loop_depth
+= depth
;
2635 /* Update change_prob of EDGE after INLINED_EDGE has been inlined.
2636 When functoin A is inlined in B and A calls C with parameter that
2637 changes with probability PROB1 and C is known to be passthroug
2638 of argument if B that change with probability PROB2, the probability
2639 of change is now PROB1*PROB2. */
2642 remap_edge_change_prob (struct cgraph_edge
*inlined_edge
,
2643 struct cgraph_edge
*edge
)
2645 if (ipa_node_params_vector
)
2648 struct ipa_edge_args
*args
= IPA_EDGE_REF (edge
);
2649 struct inline_edge_summary
*es
= inline_edge_summary (edge
);
2650 struct inline_edge_summary
*inlined_es
2651 = inline_edge_summary (inlined_edge
);
2653 for (i
= 0; i
< ipa_get_cs_argument_count (args
); i
++)
2655 struct ipa_jump_func
*jfunc
= ipa_get_ith_jump_func (args
, i
);
2656 if (jfunc
->type
== IPA_JF_PASS_THROUGH
2657 && (ipa_get_jf_pass_through_formal_id (jfunc
)
2658 < (int) VEC_length (inline_param_summary_t
,
2659 inlined_es
->param
)))
2661 int jf_formal_id
= ipa_get_jf_pass_through_formal_id (jfunc
);
2662 int prob1
= VEC_index (inline_param_summary_t
,
2663 es
->param
, i
).change_prob
;
2664 int prob2
= VEC_index
2665 (inline_param_summary_t
,
2666 inlined_es
->param
, jf_formal_id
).change_prob
;
2667 int prob
= ((prob1
* prob2
+ REG_BR_PROB_BASE
/ 2)
2668 / REG_BR_PROB_BASE
);
2670 if (prob1
&& prob2
&& !prob
)
2673 VEC_index (inline_param_summary_t
,
2674 es
->param
, i
).change_prob
= prob
;
2680 /* Update edge summaries of NODE after INLINED_EDGE has been inlined.
2682 Remap predicates of callees of NODE. Rest of arguments match
2685 Also update change probabilities. */
2688 remap_edge_summaries (struct cgraph_edge
*inlined_edge
,
2689 struct cgraph_node
*node
,
2690 struct inline_summary
*info
,
2691 struct inline_summary
*callee_info
,
2692 VEC (int, heap
) *operand_map
,
2693 VEC (int, heap
) *offset_map
,
2694 clause_t possible_truths
,
2695 struct predicate
*toplev_predicate
)
2697 struct cgraph_edge
*e
;
2698 for (e
= node
->callees
; e
; e
= e
->next_callee
)
2700 struct inline_edge_summary
*es
= inline_edge_summary (e
);
2703 if (e
->inline_failed
)
2705 remap_edge_change_prob (inlined_edge
, e
);
2709 p
= remap_predicate (info
, callee_info
,
2710 es
->predicate
, operand_map
, offset_map
,
2713 edge_set_predicate (e
, &p
);
2714 /* TODO: We should remove the edge for code that will be
2715 optimized out, but we need to keep verifiers and tree-inline
2716 happy. Make it cold for now. */
2717 if (false_predicate_p (&p
))
2724 edge_set_predicate (e
, toplev_predicate
);
2727 remap_edge_summaries (inlined_edge
, e
->callee
, info
, callee_info
,
2728 operand_map
, offset_map
, possible_truths
,
2731 for (e
= node
->indirect_calls
; e
; e
= e
->next_callee
)
2733 struct inline_edge_summary
*es
= inline_edge_summary (e
);
2736 remap_edge_change_prob (inlined_edge
, e
);
2739 p
= remap_predicate (info
, callee_info
,
2740 es
->predicate
, operand_map
, offset_map
,
2741 possible_truths
, toplev_predicate
);
2742 edge_set_predicate (e
, &p
);
2743 /* TODO: We should remove the edge for code that will be optimized
2744 out, but we need to keep verifiers and tree-inline happy.
2745 Make it cold for now. */
2746 if (false_predicate_p (&p
))
2753 edge_set_predicate (e
, toplev_predicate
);
2758 /* We inlined EDGE. Update summary of the function we inlined into. */
2761 inline_merge_summary (struct cgraph_edge
*edge
)
2763 struct inline_summary
*callee_info
= inline_summary (edge
->callee
);
2764 struct cgraph_node
*to
= (edge
->caller
->global
.inlined_to
2765 ? edge
->caller
->global
.inlined_to
: edge
->caller
);
2766 struct inline_summary
*info
= inline_summary (to
);
2767 clause_t clause
= 0; /* not_inline is known to be false. */
2769 VEC (int, heap
) *operand_map
= NULL
;
2770 VEC (int, heap
) *offset_map
= NULL
;
2772 struct predicate toplev_predicate
;
2773 struct predicate true_p
= true_predicate ();
2774 struct inline_edge_summary
*es
= inline_edge_summary (edge
);
2777 toplev_predicate
= *es
->predicate
;
2779 toplev_predicate
= true_predicate ();
2781 if (ipa_node_params_vector
&& callee_info
->conds
)
2783 struct ipa_edge_args
*args
= IPA_EDGE_REF (edge
);
2784 int count
= ipa_get_cs_argument_count (args
);
2787 evaluate_properties_for_edge (edge
, true, &clause
, NULL
, NULL
, NULL
);
2790 VEC_safe_grow_cleared (int, heap
, operand_map
, count
);
2791 VEC_safe_grow_cleared (int, heap
, offset_map
, count
);
2793 for (i
= 0; i
< count
; i
++)
2795 struct ipa_jump_func
*jfunc
= ipa_get_ith_jump_func (args
, i
);
2798 /* TODO: handle non-NOPs when merging. */
2799 if (jfunc
->type
== IPA_JF_PASS_THROUGH
)
2801 if (ipa_get_jf_pass_through_operation (jfunc
) == NOP_EXPR
)
2802 map
= ipa_get_jf_pass_through_formal_id (jfunc
);
2803 if (!ipa_get_jf_pass_through_agg_preserved (jfunc
))
2804 VEC_replace (int, offset_map
, i
, -1);
2806 else if (jfunc
->type
== IPA_JF_ANCESTOR
)
2808 HOST_WIDE_INT offset
= ipa_get_jf_ancestor_offset (jfunc
);
2809 if (offset
>= 0 && offset
< INT_MAX
)
2811 map
= ipa_get_jf_ancestor_formal_id (jfunc
);
2812 if (!ipa_get_jf_ancestor_agg_preserved (jfunc
))
2814 VEC_replace (int, offset_map
, i
, offset
);
2817 VEC_replace (int, operand_map
, i
, map
);
2818 gcc_assert (map
< ipa_get_param_count (IPA_NODE_REF (to
)));
2821 for (i
= 0; VEC_iterate (size_time_entry
, callee_info
->entry
, i
, e
); i
++)
2823 struct predicate p
= remap_predicate (info
, callee_info
,
2824 &e
->predicate
, operand_map
,
2827 if (!false_predicate_p (&p
))
2829 gcov_type add_time
= ((gcov_type
)e
->time
* edge
->frequency
2830 + CGRAPH_FREQ_BASE
/ 2) / CGRAPH_FREQ_BASE
;
2831 int prob
= predicate_probability (callee_info
->conds
,
2834 add_time
= add_time
* prob
/ REG_BR_PROB_BASE
;
2835 if (add_time
> MAX_TIME
* INLINE_TIME_SCALE
)
2836 add_time
= MAX_TIME
* INLINE_TIME_SCALE
;
2837 if (prob
!= REG_BR_PROB_BASE
2838 && dump_file
&& (dump_flags
& TDF_DETAILS
))
2840 fprintf (dump_file
, "\t\tScaling time by probability:%f\n",
2841 (double)prob
/ REG_BR_PROB_BASE
);
2843 account_size_time (info
, e
->size
, add_time
, &p
);
2846 remap_edge_summaries (edge
, edge
->callee
, info
, callee_info
, operand_map
,
2847 offset_map
, clause
, &toplev_predicate
);
2849 inline_update_callee_summaries (edge
->callee
,
2850 inline_edge_summary (edge
)->loop_depth
);
2852 /* We do not maintain predicates of inlined edges, free it. */
2853 edge_set_predicate (edge
, &true_p
);
2854 /* Similarly remove param summaries. */
2855 VEC_free (inline_param_summary_t
, heap
, es
->param
);
2856 VEC_free (int, heap
, operand_map
);
2857 VEC_free (int, heap
, offset_map
);
2860 /* For performance reasons inline_merge_summary is not updating overall size
2861 and time. Recompute it. */
2864 inline_update_overall_summary (struct cgraph_node
*node
)
2866 struct inline_summary
*info
= inline_summary (node
);
2872 for (i
= 0; VEC_iterate (size_time_entry
, info
->entry
, i
, e
); i
++)
2873 info
->size
+= e
->size
, info
->time
+= e
->time
;
2874 estimate_calls_size_and_time (node
, &info
->size
, &info
->time
,
2875 ~(clause_t
)(1 << predicate_false_condition
),
2877 info
->time
= (info
->time
+ INLINE_TIME_SCALE
/ 2) / INLINE_TIME_SCALE
;
2878 info
->size
= (info
->size
+ INLINE_SIZE_SCALE
/ 2) / INLINE_SIZE_SCALE
;
2881 /* Estimate the time cost for the caller when inlining EDGE.
2882 Only to be called via estimate_edge_time, that handles the
2885 When caching, also update the cache entry. Compute both time and
2886 size, since we always need both metrics eventually. */
2889 do_estimate_edge_time (struct cgraph_edge
*edge
)
2894 struct cgraph_node
*callee
;
2896 VEC (tree
, heap
) *known_vals
;
2897 VEC (tree
, heap
) *known_binfos
;
2898 VEC (ipa_agg_jump_function_p
, heap
) *known_aggs
;
2899 struct inline_edge_summary
*es
= inline_edge_summary (edge
);
2901 callee
= cgraph_function_or_thunk_node (edge
->callee
, NULL
);
2903 gcc_checking_assert (edge
->inline_failed
);
2904 evaluate_properties_for_edge (edge
, true,
2905 &clause
, &known_vals
, &known_binfos
,
2907 estimate_node_size_and_time (callee
, clause
, known_vals
, known_binfos
,
2908 known_aggs
, &size
, &time
, es
->param
);
2909 VEC_free (tree
, heap
, known_vals
);
2910 VEC_free (tree
, heap
, known_binfos
);
2911 VEC_free (ipa_agg_jump_function_p
, heap
, known_aggs
);
2913 ret
= (((gcov_type
)time
2914 - es
->call_stmt_time
) * edge
->frequency
2915 + CGRAPH_FREQ_BASE
/ 2) / CGRAPH_FREQ_BASE
;
2917 /* When caching, update the cache entry. */
2918 if (edge_growth_cache
)
2921 if ((int)VEC_length (edge_growth_cache_entry
, edge_growth_cache
)
2923 VEC_safe_grow_cleared (edge_growth_cache_entry
, heap
, edge_growth_cache
,
2924 cgraph_edge_max_uid
);
2925 VEC_index (edge_growth_cache_entry
, edge_growth_cache
, edge
->uid
).time
2928 ret_size
= size
- es
->call_stmt_size
;
2929 gcc_checking_assert (es
->call_stmt_size
);
2930 VEC_index (edge_growth_cache_entry
, edge_growth_cache
, edge
->uid
).size
2931 = ret_size
+ (ret_size
>= 0);
2937 /* Estimate the growth of the caller when inlining EDGE.
2938 Only to be called via estimate_edge_size. */
2941 do_estimate_edge_growth (struct cgraph_edge
*edge
)
2944 struct cgraph_node
*callee
;
2946 VEC (tree
, heap
) *known_vals
;
2947 VEC (tree
, heap
) *known_binfos
;
2948 VEC (ipa_agg_jump_function_p
, heap
) *known_aggs
;
2950 /* When we do caching, use do_estimate_edge_time to populate the entry. */
2952 if (edge_growth_cache
)
2954 do_estimate_edge_time (edge
);
2955 size
= VEC_index (edge_growth_cache_entry
,
2958 gcc_checking_assert (size
);
2959 return size
- (size
> 0);
2962 callee
= cgraph_function_or_thunk_node (edge
->callee
, NULL
);
2964 /* Early inliner runs without caching, go ahead and do the dirty work. */
2965 gcc_checking_assert (edge
->inline_failed
);
2966 evaluate_properties_for_edge (edge
, true,
2967 &clause
, &known_vals
, &known_binfos
,
2969 estimate_node_size_and_time (callee
, clause
, known_vals
, known_binfos
,
2970 known_aggs
, &size
, NULL
, NULL
);
2971 VEC_free (tree
, heap
, known_vals
);
2972 VEC_free (tree
, heap
, known_binfos
);
2973 VEC_free (ipa_agg_jump_function_p
, heap
, known_aggs
);
2974 gcc_checking_assert (inline_edge_summary (edge
)->call_stmt_size
);
2975 return size
- inline_edge_summary (edge
)->call_stmt_size
;
2979 /* Estimate self time of the function NODE after inlining EDGE. */
2982 estimate_time_after_inlining (struct cgraph_node
*node
,
2983 struct cgraph_edge
*edge
)
2985 struct inline_edge_summary
*es
= inline_edge_summary (edge
);
2986 if (!es
->predicate
|| !false_predicate_p (es
->predicate
))
2988 gcov_type time
= inline_summary (node
)->time
+ estimate_edge_time (edge
);
2991 if (time
> MAX_TIME
)
2995 return inline_summary (node
)->time
;
2999 /* Estimate the size of NODE after inlining EDGE which should be an
3000 edge to either NODE or a call inlined into NODE. */
3003 estimate_size_after_inlining (struct cgraph_node
*node
,
3004 struct cgraph_edge
*edge
)
3006 struct inline_edge_summary
*es
= inline_edge_summary (edge
);
3007 if (!es
->predicate
|| !false_predicate_p (es
->predicate
))
3009 int size
= inline_summary (node
)->size
+ estimate_edge_growth (edge
);
3010 gcc_assert (size
>= 0);
3013 return inline_summary (node
)->size
;
3019 bool self_recursive
;
3024 /* Worker for do_estimate_growth. Collect growth for all callers. */
3027 do_estimate_growth_1 (struct cgraph_node
*node
, void *data
)
3029 struct cgraph_edge
*e
;
3030 struct growth_data
*d
= (struct growth_data
*) data
;
3032 for (e
= node
->callers
; e
; e
= e
->next_caller
)
3034 gcc_checking_assert (e
->inline_failed
);
3036 if (e
->caller
== node
3037 || (e
->caller
->global
.inlined_to
3038 && e
->caller
->global
.inlined_to
== node
))
3039 d
->self_recursive
= true;
3040 d
->growth
+= estimate_edge_growth (e
);
3046 /* Estimate the growth caused by inlining NODE into all callees. */
3049 do_estimate_growth (struct cgraph_node
*node
)
3051 struct growth_data d
= {0, false};
3052 struct inline_summary
*info
= inline_summary (node
);
3054 cgraph_for_node_and_aliases (node
, do_estimate_growth_1
, &d
, true);
3056 /* For self recursive functions the growth estimation really should be
3057 infinity. We don't want to return very large values because the growth
3058 plays various roles in badness computation fractions. Be sure to not
3059 return zero or negative growths. */
3060 if (d
.self_recursive
)
3061 d
.growth
= d
.growth
< info
->size
? info
->size
: d
.growth
;
3064 if (!DECL_EXTERNAL (node
->symbol
.decl
)
3065 && cgraph_will_be_removed_from_program_if_no_direct_calls (node
))
3066 d
.growth
-= info
->size
;
3067 /* COMDAT functions are very often not shared across multiple units
3068 since they come from various template instantiations.
3069 Take this into account. */
3070 else if (DECL_COMDAT (node
->symbol
.decl
)
3071 && cgraph_can_remove_if_no_direct_calls_p (node
))
3072 d
.growth
-= (info
->size
3073 * (100 - PARAM_VALUE (PARAM_COMDAT_SHARING_PROBABILITY
))
3077 if (node_growth_cache
)
3079 if ((int)VEC_length (int, node_growth_cache
) <= node
->uid
)
3080 VEC_safe_grow_cleared (int, heap
, node_growth_cache
, cgraph_max_uid
);
3081 VEC_replace (int, node_growth_cache
, node
->uid
,
3082 d
.growth
+ (d
.growth
>= 0));
3088 /* This function performs intraprocedural analysis in NODE that is required to
3089 inline indirect calls. */
3092 inline_indirect_intraprocedural_analysis (struct cgraph_node
*node
)
3094 ipa_analyze_node (node
);
3095 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3097 ipa_print_node_params (dump_file
, node
);
3098 ipa_print_node_jump_functions (dump_file
, node
);
3103 /* Note function body size. */
3106 inline_analyze_function (struct cgraph_node
*node
)
3108 push_cfun (DECL_STRUCT_FUNCTION (node
->symbol
.decl
));
3109 current_function_decl
= node
->symbol
.decl
;
3112 fprintf (dump_file
, "\nAnalyzing function: %s/%u\n",
3113 cgraph_node_name (node
), node
->uid
);
3114 if (optimize
&& !node
->thunk
.thunk_p
)
3115 inline_indirect_intraprocedural_analysis (node
);
3116 compute_inline_parameters (node
, false);
3118 current_function_decl
= NULL
;
3123 /* Called when new function is inserted to callgraph late. */
3126 add_new_function (struct cgraph_node
*node
, void *data ATTRIBUTE_UNUSED
)
3128 inline_analyze_function (node
);
3132 /* Note function body size. */
3135 inline_generate_summary (void)
3137 struct cgraph_node
*node
;
3139 function_insertion_hook_holder
=
3140 cgraph_add_function_insertion_hook (&add_new_function
, NULL
);
3142 ipa_register_cgraph_hooks ();
3143 inline_free_summary ();
3145 FOR_EACH_DEFINED_FUNCTION (node
)
3147 inline_analyze_function (node
);
3151 /* Read predicate from IB. */
3153 static struct predicate
3154 read_predicate (struct lto_input_block
*ib
)
3156 struct predicate out
;
3162 gcc_assert (k
<= MAX_CLAUSES
);
3163 clause
= out
.clause
[k
++] = streamer_read_uhwi (ib
);
3167 /* Zero-initialize the remaining clauses in OUT. */
3168 while (k
<= MAX_CLAUSES
)
3169 out
.clause
[k
++] = 0;
3175 /* Write inline summary for edge E to OB. */
3178 read_inline_edge_summary (struct lto_input_block
*ib
, struct cgraph_edge
*e
)
3180 struct inline_edge_summary
*es
= inline_edge_summary (e
);
3184 es
->call_stmt_size
= streamer_read_uhwi (ib
);
3185 es
->call_stmt_time
= streamer_read_uhwi (ib
);
3186 es
->loop_depth
= streamer_read_uhwi (ib
);
3187 p
= read_predicate (ib
);
3188 edge_set_predicate (e
, &p
);
3189 length
= streamer_read_uhwi (ib
);
3192 VEC_safe_grow_cleared (inline_param_summary_t
, heap
, es
->param
, length
);
3193 for (i
= 0; i
< length
; i
++)
3194 VEC_index (inline_param_summary_t
, es
->param
, i
).change_prob
3195 = streamer_read_uhwi (ib
);
3200 /* Stream in inline summaries from the section. */
3203 inline_read_section (struct lto_file_decl_data
*file_data
, const char *data
,
3206 const struct lto_function_header
*header
=
3207 (const struct lto_function_header
*) data
;
3208 const int cfg_offset
= sizeof (struct lto_function_header
);
3209 const int main_offset
= cfg_offset
+ header
->cfg_size
;
3210 const int string_offset
= main_offset
+ header
->main_size
;
3211 struct data_in
*data_in
;
3212 struct lto_input_block ib
;
3213 unsigned int i
, count2
, j
;
3214 unsigned int f_count
;
3216 LTO_INIT_INPUT_BLOCK (ib
, (const char *) data
+ main_offset
, 0,
3220 lto_data_in_create (file_data
, (const char *) data
+ string_offset
,
3221 header
->string_size
, NULL
);
3222 f_count
= streamer_read_uhwi (&ib
);
3223 for (i
= 0; i
< f_count
; i
++)
3226 struct cgraph_node
*node
;
3227 struct inline_summary
*info
;
3228 lto_symtab_encoder_t encoder
;
3229 struct bitpack_d bp
;
3230 struct cgraph_edge
*e
;
3232 index
= streamer_read_uhwi (&ib
);
3233 encoder
= file_data
->symtab_node_encoder
;
3234 node
= cgraph (lto_symtab_encoder_deref (encoder
, index
));
3235 info
= inline_summary (node
);
3237 info
->estimated_stack_size
3238 = info
->estimated_self_stack_size
= streamer_read_uhwi (&ib
);
3239 info
->size
= info
->self_size
= streamer_read_uhwi (&ib
);
3240 info
->time
= info
->self_time
= streamer_read_uhwi (&ib
);
3242 bp
= streamer_read_bitpack (&ib
);
3243 info
->inlinable
= bp_unpack_value (&bp
, 1);
3245 count2
= streamer_read_uhwi (&ib
);
3246 gcc_assert (!info
->conds
);
3247 for (j
= 0; j
< count2
; j
++)
3250 c
.operand_num
= streamer_read_uhwi (&ib
);
3251 c
.code
= (enum tree_code
) streamer_read_uhwi (&ib
);
3252 c
.val
= stream_read_tree (&ib
, data_in
);
3253 bp
= streamer_read_bitpack (&ib
);
3254 c
.agg_contents
= bp_unpack_value (&bp
, 1);
3255 c
.by_ref
= bp_unpack_value (&bp
, 1);
3257 c
.offset
= streamer_read_uhwi (&ib
);
3258 VEC_safe_push (condition
, gc
, info
->conds
, &c
);
3260 count2
= streamer_read_uhwi (&ib
);
3261 gcc_assert (!info
->entry
);
3262 for (j
= 0; j
< count2
; j
++)
3264 struct size_time_entry e
;
3266 e
.size
= streamer_read_uhwi (&ib
);
3267 e
.time
= streamer_read_uhwi (&ib
);
3268 e
.predicate
= read_predicate (&ib
);
3270 VEC_safe_push (size_time_entry
, gc
, info
->entry
, &e
);
3272 for (e
= node
->callees
; e
; e
= e
->next_callee
)
3273 read_inline_edge_summary (&ib
, e
);
3274 for (e
= node
->indirect_calls
; e
; e
= e
->next_callee
)
3275 read_inline_edge_summary (&ib
, e
);
3278 lto_free_section_data (file_data
, LTO_section_inline_summary
, NULL
, data
,
3280 lto_data_in_delete (data_in
);
3284 /* Read inline summary. Jump functions are shared among ipa-cp
3285 and inliner, so when ipa-cp is active, we don't need to write them
3289 inline_read_summary (void)
3291 struct lto_file_decl_data
**file_data_vec
= lto_get_file_decl_data ();
3292 struct lto_file_decl_data
*file_data
;
3295 inline_summary_alloc ();
3297 while ((file_data
= file_data_vec
[j
++]))
3300 const char *data
= lto_get_section_data (file_data
,
3301 LTO_section_inline_summary
,
3304 inline_read_section (file_data
, data
, len
);
3306 /* Fatal error here. We do not want to support compiling ltrans units
3307 with different version of compiler or different flags than the WPA
3308 unit, so this should never happen. */
3309 fatal_error ("ipa inline summary is missing in input file");
3313 ipa_register_cgraph_hooks ();
3315 ipa_prop_read_jump_functions ();
3317 function_insertion_hook_holder
=
3318 cgraph_add_function_insertion_hook (&add_new_function
, NULL
);
3322 /* Write predicate P to OB. */
3325 write_predicate (struct output_block
*ob
, struct predicate
*p
)
3329 for (j
= 0; p
->clause
[j
]; j
++)
3331 gcc_assert (j
< MAX_CLAUSES
);
3332 streamer_write_uhwi (ob
, p
->clause
[j
]);
3334 streamer_write_uhwi (ob
, 0);
3338 /* Write inline summary for edge E to OB. */
3341 write_inline_edge_summary (struct output_block
*ob
, struct cgraph_edge
*e
)
3343 struct inline_edge_summary
*es
= inline_edge_summary (e
);
3346 streamer_write_uhwi (ob
, es
->call_stmt_size
);
3347 streamer_write_uhwi (ob
, es
->call_stmt_time
);
3348 streamer_write_uhwi (ob
, es
->loop_depth
);
3349 write_predicate (ob
, es
->predicate
);
3350 streamer_write_uhwi (ob
, VEC_length (inline_param_summary_t
, es
->param
));
3351 for (i
= 0; i
< (int)VEC_length (inline_param_summary_t
, es
->param
); i
++)
3352 streamer_write_uhwi (ob
, VEC_index (inline_param_summary_t
,
3353 es
->param
, i
).change_prob
);
3357 /* Write inline summary for node in SET.
3358 Jump functions are shared among ipa-cp and inliner, so when ipa-cp is
3359 active, we don't need to write them twice. */
3362 inline_write_summary (void)
3364 struct cgraph_node
*node
;
3366 struct output_block
*ob
= create_output_block (LTO_section_inline_summary
);
3367 lto_symtab_encoder_t encoder
= ob
->decl_state
->symtab_node_encoder
;
3368 unsigned int count
= 0;
3371 for (i
= 0; i
< lto_symtab_encoder_size (encoder
); i
++)
3372 if (symtab_function_p (snode
= lto_symtab_encoder_deref (encoder
, i
))
3373 && cgraph (snode
)->analyzed
)
3375 streamer_write_uhwi (ob
, count
);
3377 for (i
= 0; i
< lto_symtab_encoder_size (encoder
); i
++)
3379 if (symtab_function_p (snode
= lto_symtab_encoder_deref (encoder
, i
))
3380 && (node
= cgraph (snode
))->analyzed
)
3382 struct inline_summary
*info
= inline_summary (node
);
3383 struct bitpack_d bp
;
3384 struct cgraph_edge
*edge
;
3387 struct condition
*c
;
3389 streamer_write_uhwi (ob
, lto_symtab_encoder_encode (encoder
, (symtab_node
)node
));
3390 streamer_write_hwi (ob
, info
->estimated_self_stack_size
);
3391 streamer_write_hwi (ob
, info
->self_size
);
3392 streamer_write_hwi (ob
, info
->self_time
);
3393 bp
= bitpack_create (ob
->main_stream
);
3394 bp_pack_value (&bp
, info
->inlinable
, 1);
3395 streamer_write_bitpack (&bp
);
3396 streamer_write_uhwi (ob
, VEC_length (condition
, info
->conds
));
3397 for (i
= 0; VEC_iterate (condition
, info
->conds
, i
, c
); i
++)
3399 streamer_write_uhwi (ob
, c
->operand_num
);
3400 streamer_write_uhwi (ob
, c
->code
);
3401 stream_write_tree (ob
, c
->val
, true);
3402 bp
= bitpack_create (ob
->main_stream
);
3403 bp_pack_value (&bp
, c
->agg_contents
, 1);
3404 bp_pack_value (&bp
, c
->by_ref
, 1);
3405 streamer_write_bitpack (&bp
);
3406 if (c
->agg_contents
)
3407 streamer_write_uhwi (ob
, c
->offset
);
3409 streamer_write_uhwi (ob
, VEC_length (size_time_entry
, info
->entry
));
3411 VEC_iterate (size_time_entry
, info
->entry
, i
, e
);
3414 streamer_write_uhwi (ob
, e
->size
);
3415 streamer_write_uhwi (ob
, e
->time
);
3416 write_predicate (ob
, &e
->predicate
);
3418 for (edge
= node
->callees
; edge
; edge
= edge
->next_callee
)
3419 write_inline_edge_summary (ob
, edge
);
3420 for (edge
= node
->indirect_calls
; edge
; edge
= edge
->next_callee
)
3421 write_inline_edge_summary (ob
, edge
);
3424 streamer_write_char_stream (ob
->main_stream
, 0);
3425 produce_asm (ob
, NULL
);
3426 destroy_output_block (ob
);
3428 if (optimize
&& !flag_ipa_cp
)
3429 ipa_prop_write_jump_functions ();
3433 /* Release inline summary. */
3436 inline_free_summary (void)
3438 struct cgraph_node
*node
;
3439 if (inline_edge_summary_vec
== NULL
)
3441 FOR_EACH_DEFINED_FUNCTION (node
)
3442 reset_inline_summary (node
);
3443 if (function_insertion_hook_holder
)
3444 cgraph_remove_function_insertion_hook (function_insertion_hook_holder
);
3445 function_insertion_hook_holder
= NULL
;
3446 if (node_removal_hook_holder
)
3447 cgraph_remove_node_removal_hook (node_removal_hook_holder
);
3448 node_removal_hook_holder
= NULL
;
3449 if (edge_removal_hook_holder
)
3450 cgraph_remove_edge_removal_hook (edge_removal_hook_holder
);
3451 edge_removal_hook_holder
= NULL
;
3452 if (node_duplication_hook_holder
)
3453 cgraph_remove_node_duplication_hook (node_duplication_hook_holder
);
3454 node_duplication_hook_holder
= NULL
;
3455 if (edge_duplication_hook_holder
)
3456 cgraph_remove_edge_duplication_hook (edge_duplication_hook_holder
);
3457 edge_duplication_hook_holder
= NULL
;
3458 VEC_free (inline_summary_t
, gc
, inline_summary_vec
);
3459 inline_summary_vec
= NULL
;
3460 VEC_free (inline_edge_summary_t
, heap
, inline_edge_summary_vec
);
3461 inline_edge_summary_vec
= NULL
;
3462 if (edge_predicate_pool
)
3463 free_alloc_pool (edge_predicate_pool
);
3464 edge_predicate_pool
= 0;