1 /* Inlining decision heuristics.
2 Copyright (C) 2003-2016 Free Software Foundation, Inc.
3 Contributed by Jan Hubicka
5 This file is part of GCC.
7 GCC is free software; you can redistribute it and/or modify it under
8 the terms of the GNU General Public License as published by the Free
9 Software Foundation; either version 3, or (at your option) any later
12 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
13 WARRANTY; without even the implied warranty of MERCHANTABILITY or
14 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
17 You should have received a copy of the GNU General Public License
18 along with GCC; see the file COPYING3. If not see
19 <http://www.gnu.org/licenses/>. */
21 /* Analysis used by the inliner and other passes limiting code size growth.
23 We estimate for each function
25 - average function execution time
26 - inlining size benefit (that is how much of function body size
27 and its call sequence is expected to disappear by inlining)
28 - inlining time benefit
31 - call statement size and time
33 inlinie_summary datastructures store above information locally (i.e.
34 parameters of the function itself) and globally (i.e. parameters of
35 the function created by applying all the inline decisions already
36 present in the callgraph).
38 We provide accestor to the inline_summary datastructure and
39 basic logic updating the parameters when inlining is performed.
41 The summaries are context sensitive. Context means
42 1) partial assignment of known constant values of operands
43 2) whether function is inlined into the call or not.
44 It is easy to add more variants. To represent function size and time
45 that depends on context (i.e. it is known to be optimized away when
46 context is known either by inlining or from IP-CP and clonning),
47 we use predicates. Predicates are logical formulas in
48 conjunctive-disjunctive form consisting of clauses. Clauses are bitmaps
49 specifying what conditions must be true. Conditions are simple test
50 of the form described above.
52 In order to make predicate (possibly) true, all of its clauses must
53 be (possibly) true. To make clause (possibly) true, one of conditions
54 it mentions must be (possibly) true. There are fixed bounds on
55 number of clauses and conditions and all the manipulation functions
56 are conservative in positive direction. I.e. we may lose precision
57 by thinking that predicate may be true even when it is not.
59 estimate_edge_size and estimate_edge_growth can be used to query
60 function size/time in the given context. inline_merge_summary merges
61 properties of caller and callee after inlining.
63 Finally pass_inline_parameters is exported. This is used to drive
64 computation of function parameters used by the early inliner. IPA
65 inlined performs analysis via its analyze_function method. */
69 #include "coretypes.h"
73 #include "alloc-pool.h"
74 #include "tree-pass.h"
76 #include "tree-streamer.h"
78 #include "diagnostic.h"
79 #include "fold-const.h"
80 #include "print-tree.h"
81 #include "tree-inline.h"
82 #include "gimple-pretty-print.h"
85 #include "gimple-iterator.h"
87 #include "tree-ssa-loop-niter.h"
88 #include "tree-ssa-loop.h"
89 #include "symbol-summary.h"
91 #include "ipa-inline.h"
93 #include "tree-scalar-evolution.h"
94 #include "ipa-utils.h"
96 #include "cfgexpand.h"
99 /* Estimate runtime of function can easilly run into huge numbers with many
100 nested loops. Be sure we can compute time * INLINE_SIZE_SCALE * 2 in an
101 integer. For anything larger we use gcov_type. */
102 #define MAX_TIME 500000
104 /* Number of bits in integer, but we really want to be stable across different
106 #define NUM_CONDITIONS 32
108 enum predicate_conditions
110 predicate_false_condition
= 0,
111 predicate_not_inlined_condition
= 1,
112 predicate_first_dynamic_condition
= 2
115 /* Special condition code we use to represent test that operand is compile time
117 #define IS_NOT_CONSTANT ERROR_MARK
118 /* Special condition code we use to represent test that operand is not changed
119 across invocation of the function. When operand IS_NOT_CONSTANT it is always
120 CHANGED, however i.e. loop invariants can be NOT_CHANGED given percentage
121 of executions even when they are not compile time constants. */
122 #define CHANGED IDENTIFIER_NODE
124 /* Holders of ipa cgraph hooks: */
125 static struct cgraph_2edge_hook_list
*edge_duplication_hook_holder
;
126 static struct cgraph_edge_hook_list
*edge_removal_hook_holder
;
127 static void inline_edge_removal_hook (struct cgraph_edge
*, void *);
128 static void inline_edge_duplication_hook (struct cgraph_edge
*,
129 struct cgraph_edge
*, void *);
131 /* VECtor holding inline summaries.
132 In GGC memory because conditions might point to constant trees. */
133 function_summary
<inline_summary
*> *inline_summaries
;
134 vec
<inline_edge_summary_t
> inline_edge_summary_vec
;
136 /* Cached node/edge growths. */
137 vec
<edge_growth_cache_entry
> edge_growth_cache
;
139 /* Edge predicates goes here. */
140 static object_allocator
<predicate
> edge_predicate_pool ("edge predicates");
142 /* Return true predicate (tautology).
143 We represent it by empty list of clauses. */
145 static inline struct predicate
146 true_predicate (void)
154 /* Return predicate testing single condition number COND. */
156 static inline struct predicate
157 single_cond_predicate (int cond
)
160 p
.clause
[0] = 1 << cond
;
166 /* Return false predicate. First clause require false condition. */
168 static inline struct predicate
169 false_predicate (void)
171 return single_cond_predicate (predicate_false_condition
);
175 /* Return true if P is (true). */
178 true_predicate_p (struct predicate
*p
)
180 return !p
->clause
[0];
184 /* Return true if P is (false). */
187 false_predicate_p (struct predicate
*p
)
189 if (p
->clause
[0] == (1 << predicate_false_condition
))
191 gcc_checking_assert (!p
->clause
[1]
192 && p
->clause
[0] == 1 << predicate_false_condition
);
199 /* 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 SUMMARY. OPERAND_NUM, SIZE, CODE and VAL
220 correspond to fields of condition structure. AGGPOS describes whether the
221 used operand is loaded from an aggregate and where in the aggregate it is.
222 It can be NULL, which means this not a load from an aggregate. */
224 static struct predicate
225 add_condition (struct inline_summary
*summary
, int operand_num
,
226 HOST_WIDE_INT size
, struct agg_position_info
*aggpos
,
227 enum tree_code code
, tree val
)
231 struct condition new_cond
;
232 HOST_WIDE_INT offset
;
233 bool agg_contents
, by_ref
;
237 offset
= aggpos
->offset
;
238 agg_contents
= aggpos
->agg_contents
;
239 by_ref
= aggpos
->by_ref
;
244 agg_contents
= false;
248 gcc_checking_assert (operand_num
>= 0);
249 for (i
= 0; vec_safe_iterate (summary
->conds
, i
, &c
); i
++)
251 if (c
->operand_num
== operand_num
255 && c
->agg_contents
== agg_contents
256 && (!agg_contents
|| (c
->offset
== offset
&& c
->by_ref
== by_ref
)))
257 return single_cond_predicate (i
+ predicate_first_dynamic_condition
);
259 /* Too many conditions. Give up and return constant true. */
260 if (i
== NUM_CONDITIONS
- predicate_first_dynamic_condition
)
261 return true_predicate ();
263 new_cond
.operand_num
= operand_num
;
264 new_cond
.code
= code
;
266 new_cond
.agg_contents
= agg_contents
;
267 new_cond
.by_ref
= by_ref
;
268 new_cond
.offset
= offset
;
269 new_cond
.size
= size
;
270 vec_safe_push (summary
->conds
, new_cond
);
271 return single_cond_predicate (i
+ predicate_first_dynamic_condition
);
275 /* Add clause CLAUSE into the predicate P. */
278 add_clause (conditions conditions
, struct predicate
*p
, clause_t clause
)
282 int insert_here
= -1;
289 /* False clause makes the whole predicate false. Kill the other variants. */
290 if (clause
== (1 << predicate_false_condition
))
292 p
->clause
[0] = (1 << predicate_false_condition
);
296 if (false_predicate_p (p
))
299 /* No one should be silly enough to add false into nontrivial clauses. */
300 gcc_checking_assert (!(clause
& (1 << predicate_false_condition
)));
302 /* Look where to insert the clause. At the same time prune out
303 clauses of P that are implied by the new clause and thus
305 for (i
= 0, i2
= 0; i
<= MAX_CLAUSES
; i
++)
307 p
->clause
[i2
] = p
->clause
[i
];
312 /* If p->clause[i] implies clause, there is nothing to add. */
313 if ((p
->clause
[i
] & clause
) == p
->clause
[i
])
315 /* We had nothing to add, none of clauses should've become
317 gcc_checking_assert (i
== i2
);
321 if (p
->clause
[i
] < clause
&& insert_here
< 0)
324 /* If clause implies p->clause[i], then p->clause[i] becomes redundant.
325 Otherwise the p->clause[i] has to stay. */
326 if ((p
->clause
[i
] & clause
) != clause
)
330 /* Look for clauses that are obviously true. I.e.
331 op0 == 5 || op0 != 5. */
332 for (c1
= predicate_first_dynamic_condition
; c1
< NUM_CONDITIONS
; c1
++)
335 if (!(clause
& (1 << c1
)))
337 cc1
= &(*conditions
)[c1
- predicate_first_dynamic_condition
];
338 /* We have no way to represent !CHANGED and !IS_NOT_CONSTANT
339 and thus there is no point for looking for them. */
340 if (cc1
->code
== CHANGED
|| cc1
->code
== IS_NOT_CONSTANT
)
342 for (c2
= c1
+ 1; c2
< NUM_CONDITIONS
; c2
++)
343 if (clause
& (1 << c2
))
346 &(*conditions
)[c1
- predicate_first_dynamic_condition
];
348 &(*conditions
)[c2
- predicate_first_dynamic_condition
];
349 if (cc1
->operand_num
== cc2
->operand_num
350 && cc1
->val
== cc2
->val
351 && cc2
->code
!= IS_NOT_CONSTANT
352 && cc2
->code
!= CHANGED
353 && cc1
->code
== invert_tree_comparison (cc2
->code
,
354 HONOR_NANS (cc1
->val
)))
360 /* We run out of variants. Be conservative in positive direction. */
361 if (i2
== MAX_CLAUSES
)
363 /* Keep clauses in decreasing order. This makes equivalence testing easy. */
364 p
->clause
[i2
+ 1] = 0;
365 if (insert_here
>= 0)
366 for (; i2
> insert_here
; i2
--)
367 p
->clause
[i2
] = p
->clause
[i2
- 1];
370 p
->clause
[insert_here
] = clause
;
376 static struct predicate
377 and_predicates (conditions conditions
,
378 struct predicate
*p
, struct predicate
*p2
)
380 struct predicate out
= *p
;
383 /* Avoid busy work. */
384 if (false_predicate_p (p2
) || true_predicate_p (p
))
386 if (false_predicate_p (p
) || true_predicate_p (p2
))
389 /* See how far predicates match. */
390 for (i
= 0; p
->clause
[i
] && p
->clause
[i
] == p2
->clause
[i
]; i
++)
392 gcc_checking_assert (i
< MAX_CLAUSES
);
395 /* Combine the predicates rest. */
396 for (; p2
->clause
[i
]; i
++)
398 gcc_checking_assert (i
< MAX_CLAUSES
);
399 add_clause (conditions
, &out
, p2
->clause
[i
]);
405 /* Return true if predicates are obviously equal. */
408 predicates_equal_p (struct predicate
*p
, struct predicate
*p2
)
411 for (i
= 0; p
->clause
[i
]; i
++)
413 gcc_checking_assert (i
< MAX_CLAUSES
);
414 gcc_checking_assert (p
->clause
[i
] > p
->clause
[i
+ 1]);
415 gcc_checking_assert (!p2
->clause
[i
]
416 || p2
->clause
[i
] > p2
->clause
[i
+ 1]);
417 if (p
->clause
[i
] != p2
->clause
[i
])
420 return !p2
->clause
[i
];
426 static struct predicate
427 or_predicates (conditions conditions
,
428 struct predicate
*p
, struct predicate
*p2
)
430 struct predicate out
= true_predicate ();
433 /* Avoid busy work. */
434 if (false_predicate_p (p2
) || true_predicate_p (p
))
436 if (false_predicate_p (p
) || true_predicate_p (p2
))
438 if (predicates_equal_p (p
, p2
))
441 /* OK, combine the predicates. */
442 for (i
= 0; p
->clause
[i
]; i
++)
443 for (j
= 0; p2
->clause
[j
]; j
++)
445 gcc_checking_assert (i
< MAX_CLAUSES
&& j
< MAX_CLAUSES
);
446 add_clause (conditions
, &out
, p
->clause
[i
] | p2
->clause
[j
]);
452 /* Having partial truth assignment in POSSIBLE_TRUTHS, return false
453 if predicate P is known to be false. */
456 evaluate_predicate (struct predicate
*p
, clause_t possible_truths
)
460 /* True remains true. */
461 if (true_predicate_p (p
))
464 gcc_assert (!(possible_truths
& (1 << predicate_false_condition
)));
466 /* See if we can find clause we can disprove. */
467 for (i
= 0; p
->clause
[i
]; i
++)
469 gcc_checking_assert (i
< MAX_CLAUSES
);
470 if (!(p
->clause
[i
] & possible_truths
))
476 /* Return the probability in range 0...REG_BR_PROB_BASE that the predicated
477 instruction will be recomputed per invocation of the inlined call. */
480 predicate_probability (conditions conds
,
481 struct predicate
*p
, clause_t possible_truths
,
482 vec
<inline_param_summary
> inline_param_summary
)
485 int combined_prob
= REG_BR_PROB_BASE
;
487 /* True remains true. */
488 if (true_predicate_p (p
))
489 return REG_BR_PROB_BASE
;
491 if (false_predicate_p (p
))
494 gcc_assert (!(possible_truths
& (1 << predicate_false_condition
)));
496 /* See if we can find clause we can disprove. */
497 for (i
= 0; p
->clause
[i
]; i
++)
499 gcc_checking_assert (i
< MAX_CLAUSES
);
500 if (!(p
->clause
[i
] & possible_truths
))
506 if (!inline_param_summary
.exists ())
507 return REG_BR_PROB_BASE
;
508 for (i2
= 0; i2
< NUM_CONDITIONS
; i2
++)
509 if ((p
->clause
[i
] & possible_truths
) & (1 << i2
))
511 if (i2
>= predicate_first_dynamic_condition
)
514 &(*conds
)[i2
- predicate_first_dynamic_condition
];
515 if (c
->code
== CHANGED
517 (int) inline_param_summary
.length ()))
520 inline_param_summary
[c
->operand_num
].change_prob
;
521 this_prob
= MAX (this_prob
, iprob
);
524 this_prob
= REG_BR_PROB_BASE
;
527 this_prob
= REG_BR_PROB_BASE
;
529 combined_prob
= MIN (this_prob
, combined_prob
);
534 return combined_prob
;
538 /* Dump conditional COND. */
541 dump_condition (FILE *f
, conditions conditions
, int cond
)
544 if (cond
== predicate_false_condition
)
545 fprintf (f
, "false");
546 else if (cond
== predicate_not_inlined_condition
)
547 fprintf (f
, "not inlined");
550 c
= &(*conditions
)[cond
- predicate_first_dynamic_condition
];
551 fprintf (f
, "op%i", c
->operand_num
);
553 fprintf (f
, "[%soffset: " HOST_WIDE_INT_PRINT_DEC
"]",
554 c
->by_ref
? "ref " : "", c
->offset
);
555 if (c
->code
== IS_NOT_CONSTANT
)
557 fprintf (f
, " not constant");
560 if (c
->code
== CHANGED
)
562 fprintf (f
, " changed");
565 fprintf (f
, " %s ", op_symbol_code (c
->code
));
566 print_generic_expr (f
, c
->val
, 1);
571 /* Dump clause CLAUSE. */
574 dump_clause (FILE *f
, conditions conds
, clause_t clause
)
581 for (i
= 0; i
< NUM_CONDITIONS
; i
++)
582 if (clause
& (1 << i
))
587 dump_condition (f
, conds
, i
);
593 /* Dump predicate PREDICATE. */
596 dump_predicate (FILE *f
, conditions conds
, struct predicate
*pred
)
599 if (true_predicate_p (pred
))
600 dump_clause (f
, conds
, 0);
602 for (i
= 0; pred
->clause
[i
]; i
++)
606 dump_clause (f
, conds
, pred
->clause
[i
]);
612 /* Dump inline hints. */
614 dump_inline_hints (FILE *f
, inline_hints hints
)
618 fprintf (f
, "inline hints:");
619 if (hints
& INLINE_HINT_indirect_call
)
621 hints
&= ~INLINE_HINT_indirect_call
;
622 fprintf (f
, " indirect_call");
624 if (hints
& INLINE_HINT_loop_iterations
)
626 hints
&= ~INLINE_HINT_loop_iterations
;
627 fprintf (f
, " loop_iterations");
629 if (hints
& INLINE_HINT_loop_stride
)
631 hints
&= ~INLINE_HINT_loop_stride
;
632 fprintf (f
, " loop_stride");
634 if (hints
& INLINE_HINT_same_scc
)
636 hints
&= ~INLINE_HINT_same_scc
;
637 fprintf (f
, " same_scc");
639 if (hints
& INLINE_HINT_in_scc
)
641 hints
&= ~INLINE_HINT_in_scc
;
642 fprintf (f
, " in_scc");
644 if (hints
& INLINE_HINT_cross_module
)
646 hints
&= ~INLINE_HINT_cross_module
;
647 fprintf (f
, " cross_module");
649 if (hints
& INLINE_HINT_declared_inline
)
651 hints
&= ~INLINE_HINT_declared_inline
;
652 fprintf (f
, " declared_inline");
654 if (hints
& INLINE_HINT_array_index
)
656 hints
&= ~INLINE_HINT_array_index
;
657 fprintf (f
, " array_index");
659 if (hints
& INLINE_HINT_known_hot
)
661 hints
&= ~INLINE_HINT_known_hot
;
662 fprintf (f
, " known_hot");
668 /* Record SIZE and TIME under condition PRED into the inline summary. */
671 account_size_time (struct inline_summary
*summary
, int size
, int time
,
672 struct predicate
*pred
)
678 if (false_predicate_p (pred
))
681 /* We need to create initial empty unconitional clause, but otherwie
682 we don't need to account empty times and sizes. */
683 if (!size
&& !time
&& summary
->entry
)
686 /* Watch overflow that might result from insane profiles. */
687 if (time
> MAX_TIME
* INLINE_TIME_SCALE
)
688 time
= MAX_TIME
* INLINE_TIME_SCALE
;
689 gcc_assert (time
>= 0);
691 for (i
= 0; vec_safe_iterate (summary
->entry
, i
, &e
); i
++)
692 if (predicates_equal_p (&e
->predicate
, pred
))
701 e
= &(*summary
->entry
)[0];
702 gcc_assert (!e
->predicate
.clause
[0]);
703 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
705 "\t\tReached limit on number of entries, "
706 "ignoring the predicate.");
708 if (dump_file
&& (dump_flags
& TDF_DETAILS
) && (time
|| size
))
711 "\t\tAccounting size:%3.2f, time:%3.2f on %spredicate:",
712 ((double) size
) / INLINE_SIZE_SCALE
,
713 ((double) time
) / INLINE_TIME_SCALE
, found
? "" : "new ");
714 dump_predicate (dump_file
, summary
->conds
, pred
);
718 struct size_time_entry new_entry
;
719 new_entry
.size
= size
;
720 new_entry
.time
= time
;
721 new_entry
.predicate
= *pred
;
722 vec_safe_push (summary
->entry
, new_entry
);
728 if (e
->time
> MAX_TIME
* INLINE_TIME_SCALE
)
729 e
->time
= MAX_TIME
* INLINE_TIME_SCALE
;
733 /* We proved E to be unreachable, redirect it to __bultin_unreachable. */
735 static struct cgraph_edge
*
736 redirect_to_unreachable (struct cgraph_edge
*e
)
738 struct cgraph_node
*callee
= !e
->inline_failed
? e
->callee
: NULL
;
739 struct cgraph_node
*target
= cgraph_node::get_create
740 (builtin_decl_implicit (BUILT_IN_UNREACHABLE
));
743 e
= e
->resolve_speculation (target
->decl
);
745 e
->make_direct (target
);
747 e
->redirect_callee (target
);
748 struct inline_edge_summary
*es
= inline_edge_summary (e
);
749 e
->inline_failed
= CIF_UNREACHABLE
;
752 es
->call_stmt_size
= 0;
753 es
->call_stmt_time
= 0;
755 callee
->remove_symbol_and_inline_clones ();
759 /* Set predicate for edge E. */
762 edge_set_predicate (struct cgraph_edge
*e
, struct predicate
*predicate
)
764 /* If the edge is determined to be never executed, redirect it
765 to BUILTIN_UNREACHABLE to save inliner from inlining into it. */
766 if (predicate
&& false_predicate_p (predicate
)
767 /* When handling speculative edges, we need to do the redirection
768 just once. Do it always on the direct edge, so we do not
769 attempt to resolve speculation while duplicating the edge. */
770 && (!e
->speculative
|| e
->callee
))
771 e
= redirect_to_unreachable (e
);
773 struct inline_edge_summary
*es
= inline_edge_summary (e
);
774 if (predicate
&& !true_predicate_p (predicate
))
777 es
->predicate
= edge_predicate_pool
.allocate ();
778 *es
->predicate
= *predicate
;
783 edge_predicate_pool
.remove (es
->predicate
);
784 es
->predicate
= NULL
;
788 /* Set predicate for hint *P. */
791 set_hint_predicate (struct predicate
**p
, struct predicate new_predicate
)
793 if (false_predicate_p (&new_predicate
) || true_predicate_p (&new_predicate
))
796 edge_predicate_pool
.remove (*p
);
802 *p
= edge_predicate_pool
.allocate ();
808 /* KNOWN_VALS is partial mapping of parameters of NODE to constant values.
809 KNOWN_AGGS is a vector of aggreggate jump functions for each parameter.
810 Return clause of possible truths. When INLINE_P is true, assume that we are
813 ERROR_MARK means compile time invariant. */
816 evaluate_conditions_for_known_args (struct cgraph_node
*node
,
818 vec
<tree
> known_vals
,
819 vec
<ipa_agg_jump_function_p
>
822 clause_t clause
= inline_p
? 0 : 1 << predicate_not_inlined_condition
;
823 struct inline_summary
*info
= inline_summaries
->get (node
);
827 for (i
= 0; vec_safe_iterate (info
->conds
, i
, &c
); i
++)
832 /* We allow call stmt to have fewer arguments than the callee function
833 (especially for K&R style programs). So bound check here (we assume
834 known_aggs vector, if non-NULL, has the same length as
836 gcc_checking_assert (!known_aggs
.exists ()
837 || (known_vals
.length () == known_aggs
.length ()));
838 if (c
->operand_num
>= (int) known_vals
.length ())
840 clause
|= 1 << (i
+ predicate_first_dynamic_condition
);
846 struct ipa_agg_jump_function
*agg
;
848 if (c
->code
== CHANGED
850 && (known_vals
[c
->operand_num
] == error_mark_node
))
853 if (known_aggs
.exists ())
855 agg
= known_aggs
[c
->operand_num
];
856 val
= ipa_find_agg_cst_for_param (agg
, c
->offset
, c
->by_ref
);
863 val
= known_vals
[c
->operand_num
];
864 if (val
== error_mark_node
&& c
->code
!= CHANGED
)
870 clause
|= 1 << (i
+ predicate_first_dynamic_condition
);
873 if (c
->code
== CHANGED
)
876 if (tree_to_shwi (TYPE_SIZE (TREE_TYPE (val
))) != c
->size
)
878 clause
|= 1 << (i
+ predicate_first_dynamic_condition
);
881 if (c
->code
== IS_NOT_CONSTANT
)
884 val
= fold_unary (VIEW_CONVERT_EXPR
, TREE_TYPE (c
->val
), val
);
886 ? fold_binary_to_constant (c
->code
, boolean_type_node
, val
, c
->val
)
889 if (res
&& integer_zerop (res
))
892 clause
|= 1 << (i
+ predicate_first_dynamic_condition
);
898 /* Work out what conditions might be true at invocation of E. */
901 evaluate_properties_for_edge (struct cgraph_edge
*e
, bool inline_p
,
902 clause_t
*clause_ptr
,
903 vec
<tree
> *known_vals_ptr
,
904 vec
<ipa_polymorphic_call_context
>
906 vec
<ipa_agg_jump_function_p
> *known_aggs_ptr
)
908 struct cgraph_node
*callee
= e
->callee
->ultimate_alias_target ();
909 struct inline_summary
*info
= inline_summaries
->get (callee
);
910 vec
<tree
> known_vals
= vNULL
;
911 vec
<ipa_agg_jump_function_p
> known_aggs
= vNULL
;
914 *clause_ptr
= inline_p
? 0 : 1 << predicate_not_inlined_condition
;
916 known_vals_ptr
->create (0);
917 if (known_contexts_ptr
)
918 known_contexts_ptr
->create (0);
920 if (ipa_node_params_sum
921 && !e
->call_stmt_cannot_inline_p
922 && ((clause_ptr
&& info
->conds
) || known_vals_ptr
|| known_contexts_ptr
))
924 struct ipa_node_params
*parms_info
;
925 struct ipa_edge_args
*args
= IPA_EDGE_REF (e
);
926 struct inline_edge_summary
*es
= inline_edge_summary (e
);
927 int i
, count
= ipa_get_cs_argument_count (args
);
929 if (e
->caller
->global
.inlined_to
)
930 parms_info
= IPA_NODE_REF (e
->caller
->global
.inlined_to
);
932 parms_info
= IPA_NODE_REF (e
->caller
);
934 if (count
&& (info
->conds
|| known_vals_ptr
))
935 known_vals
.safe_grow_cleared (count
);
936 if (count
&& (info
->conds
|| known_aggs_ptr
))
937 known_aggs
.safe_grow_cleared (count
);
938 if (count
&& known_contexts_ptr
)
939 known_contexts_ptr
->safe_grow_cleared (count
);
941 for (i
= 0; i
< count
; i
++)
943 struct ipa_jump_func
*jf
= ipa_get_ith_jump_func (args
, i
);
944 tree cst
= ipa_value_from_jfunc (parms_info
, jf
);
946 if (!cst
&& e
->call_stmt
947 && i
< (int)gimple_call_num_args (e
->call_stmt
))
949 cst
= gimple_call_arg (e
->call_stmt
, i
);
950 if (!is_gimple_min_invariant (cst
))
955 gcc_checking_assert (TREE_CODE (cst
) != TREE_BINFO
);
956 if (known_vals
.exists ())
959 else if (inline_p
&& !es
->param
[i
].change_prob
)
960 known_vals
[i
] = error_mark_node
;
962 if (known_contexts_ptr
)
963 (*known_contexts_ptr
)[i
] = ipa_context_from_jfunc (parms_info
, e
,
965 /* TODO: When IPA-CP starts propagating and merging aggregate jump
966 functions, use its knowledge of the caller too, just like the
967 scalar case above. */
968 known_aggs
[i
] = &jf
->agg
;
971 else if (e
->call_stmt
&& !e
->call_stmt_cannot_inline_p
972 && ((clause_ptr
&& info
->conds
) || known_vals_ptr
))
974 int i
, count
= (int)gimple_call_num_args (e
->call_stmt
);
976 if (count
&& (info
->conds
|| known_vals_ptr
))
977 known_vals
.safe_grow_cleared (count
);
978 for (i
= 0; i
< count
; i
++)
980 tree cst
= gimple_call_arg (e
->call_stmt
, i
);
981 if (!is_gimple_min_invariant (cst
))
989 *clause_ptr
= evaluate_conditions_for_known_args (callee
, inline_p
,
990 known_vals
, known_aggs
);
993 *known_vals_ptr
= known_vals
;
995 known_vals
.release ();
998 *known_aggs_ptr
= known_aggs
;
1000 known_aggs
.release ();
1004 /* Allocate the inline summary vector or resize it to cover all cgraph nodes. */
1007 inline_summary_alloc (void)
1009 if (!edge_removal_hook_holder
)
1010 edge_removal_hook_holder
=
1011 symtab
->add_edge_removal_hook (&inline_edge_removal_hook
, NULL
);
1012 if (!edge_duplication_hook_holder
)
1013 edge_duplication_hook_holder
=
1014 symtab
->add_edge_duplication_hook (&inline_edge_duplication_hook
, NULL
);
1016 if (!inline_summaries
)
1017 inline_summaries
= (inline_summary_t
*) inline_summary_t::create_ggc (symtab
);
1019 if (inline_edge_summary_vec
.length () <= (unsigned) symtab
->edges_max_uid
)
1020 inline_edge_summary_vec
.safe_grow_cleared (symtab
->edges_max_uid
+ 1);
1023 /* We are called multiple time for given function; clear
1024 data from previous run so they are not cumulated. */
1027 reset_inline_edge_summary (struct cgraph_edge
*e
)
1029 if (e
->uid
< (int) inline_edge_summary_vec
.length ())
1031 struct inline_edge_summary
*es
= inline_edge_summary (e
);
1033 es
->call_stmt_size
= es
->call_stmt_time
= 0;
1035 edge_predicate_pool
.remove (es
->predicate
);
1036 es
->predicate
= NULL
;
1037 es
->param
.release ();
1041 /* We are called multiple time for given function; clear
1042 data from previous run so they are not cumulated. */
1045 reset_inline_summary (struct cgraph_node
*node
,
1046 inline_summary
*info
)
1048 struct cgraph_edge
*e
;
1050 info
->self_size
= info
->self_time
= 0;
1051 info
->estimated_stack_size
= 0;
1052 info
->estimated_self_stack_size
= 0;
1053 info
->stack_frame_offset
= 0;
1058 if (info
->loop_iterations
)
1060 edge_predicate_pool
.remove (info
->loop_iterations
);
1061 info
->loop_iterations
= NULL
;
1063 if (info
->loop_stride
)
1065 edge_predicate_pool
.remove (info
->loop_stride
);
1066 info
->loop_stride
= NULL
;
1068 if (info
->array_index
)
1070 edge_predicate_pool
.remove (info
->array_index
);
1071 info
->array_index
= NULL
;
1073 vec_free (info
->conds
);
1074 vec_free (info
->entry
);
1075 for (e
= node
->callees
; e
; e
= e
->next_callee
)
1076 reset_inline_edge_summary (e
);
1077 for (e
= node
->indirect_calls
; e
; e
= e
->next_callee
)
1078 reset_inline_edge_summary (e
);
1079 info
->fp_expressions
= false;
1082 /* Hook that is called by cgraph.c when a node is removed. */
1085 inline_summary_t::remove (cgraph_node
*node
, inline_summary
*info
)
1087 reset_inline_summary (node
, info
);
1090 /* Remap predicate P of former function to be predicate of duplicated function.
1091 POSSIBLE_TRUTHS is clause of possible truths in the duplicated node,
1092 INFO is inline summary of the duplicated node. */
1094 static struct predicate
1095 remap_predicate_after_duplication (struct predicate
*p
,
1096 clause_t possible_truths
,
1097 struct inline_summary
*info
)
1099 struct predicate new_predicate
= true_predicate ();
1101 for (j
= 0; p
->clause
[j
]; j
++)
1102 if (!(possible_truths
& p
->clause
[j
]))
1104 new_predicate
= false_predicate ();
1108 add_clause (info
->conds
, &new_predicate
,
1109 possible_truths
& p
->clause
[j
]);
1110 return new_predicate
;
1113 /* Same as remap_predicate_after_duplication but handle hint predicate *P.
1114 Additionally care about allocating new memory slot for updated predicate
1115 and set it to NULL when it becomes true or false (and thus uninteresting).
1119 remap_hint_predicate_after_duplication (struct predicate
**p
,
1120 clause_t possible_truths
,
1121 struct inline_summary
*info
)
1123 struct predicate new_predicate
;
1128 new_predicate
= remap_predicate_after_duplication (*p
,
1129 possible_truths
, info
);
1130 /* We do not want to free previous predicate; it is used by node origin. */
1132 set_hint_predicate (p
, new_predicate
);
1136 /* Hook that is called by cgraph.c when a node is duplicated. */
1138 inline_summary_t::duplicate (cgraph_node
*src
,
1141 inline_summary
*info
)
1143 inline_summary_alloc ();
1144 memcpy (info
, inline_summaries
->get (src
), sizeof (inline_summary
));
1145 /* TODO: as an optimization, we may avoid copying conditions
1146 that are known to be false or true. */
1147 info
->conds
= vec_safe_copy (info
->conds
);
1149 /* When there are any replacements in the function body, see if we can figure
1150 out that something was optimized out. */
1151 if (ipa_node_params_sum
&& dst
->clone
.tree_map
)
1153 vec
<size_time_entry
, va_gc
> *entry
= info
->entry
;
1154 /* Use SRC parm info since it may not be copied yet. */
1155 struct ipa_node_params
*parms_info
= IPA_NODE_REF (src
);
1156 vec
<tree
> known_vals
= vNULL
;
1157 int count
= ipa_get_param_count (parms_info
);
1159 clause_t possible_truths
;
1160 struct predicate true_pred
= true_predicate ();
1162 int optimized_out_size
= 0;
1163 bool inlined_to_p
= false;
1164 struct cgraph_edge
*edge
, *next
;
1167 known_vals
.safe_grow_cleared (count
);
1168 for (i
= 0; i
< count
; i
++)
1170 struct ipa_replace_map
*r
;
1172 for (j
= 0; vec_safe_iterate (dst
->clone
.tree_map
, j
, &r
); j
++)
1174 if (((!r
->old_tree
&& r
->parm_num
== i
)
1175 || (r
->old_tree
&& r
->old_tree
== ipa_get_param (parms_info
, i
)))
1176 && r
->replace_p
&& !r
->ref_p
)
1178 known_vals
[i
] = r
->new_tree
;
1183 possible_truths
= evaluate_conditions_for_known_args (dst
, false,
1186 known_vals
.release ();
1188 account_size_time (info
, 0, 0, &true_pred
);
1190 /* Remap size_time vectors.
1191 Simplify the predicate by prunning out alternatives that are known
1193 TODO: as on optimization, we can also eliminate conditions known
1195 for (i
= 0; vec_safe_iterate (entry
, i
, &e
); i
++)
1197 struct predicate new_predicate
;
1198 new_predicate
= remap_predicate_after_duplication (&e
->predicate
,
1201 if (false_predicate_p (&new_predicate
))
1202 optimized_out_size
+= e
->size
;
1204 account_size_time (info
, e
->size
, e
->time
, &new_predicate
);
1207 /* Remap edge predicates with the same simplification as above.
1208 Also copy constantness arrays. */
1209 for (edge
= dst
->callees
; edge
; edge
= next
)
1211 struct predicate new_predicate
;
1212 struct inline_edge_summary
*es
= inline_edge_summary (edge
);
1213 next
= edge
->next_callee
;
1215 if (!edge
->inline_failed
)
1216 inlined_to_p
= true;
1219 new_predicate
= remap_predicate_after_duplication (es
->predicate
,
1222 if (false_predicate_p (&new_predicate
)
1223 && !false_predicate_p (es
->predicate
))
1224 optimized_out_size
+= es
->call_stmt_size
* INLINE_SIZE_SCALE
;
1225 edge_set_predicate (edge
, &new_predicate
);
1228 /* Remap indirect edge predicates with the same simplificaiton as above.
1229 Also copy constantness arrays. */
1230 for (edge
= dst
->indirect_calls
; edge
; edge
= next
)
1232 struct predicate new_predicate
;
1233 struct inline_edge_summary
*es
= inline_edge_summary (edge
);
1234 next
= edge
->next_callee
;
1236 gcc_checking_assert (edge
->inline_failed
);
1239 new_predicate
= remap_predicate_after_duplication (es
->predicate
,
1242 if (false_predicate_p (&new_predicate
)
1243 && !false_predicate_p (es
->predicate
))
1244 optimized_out_size
+= es
->call_stmt_size
* INLINE_SIZE_SCALE
;
1245 edge_set_predicate (edge
, &new_predicate
);
1247 remap_hint_predicate_after_duplication (&info
->loop_iterations
,
1248 possible_truths
, info
);
1249 remap_hint_predicate_after_duplication (&info
->loop_stride
,
1250 possible_truths
, info
);
1251 remap_hint_predicate_after_duplication (&info
->array_index
,
1252 possible_truths
, info
);
1254 /* If inliner or someone after inliner will ever start producing
1255 non-trivial clones, we will get trouble with lack of information
1256 about updating self sizes, because size vectors already contains
1257 sizes of the calees. */
1258 gcc_assert (!inlined_to_p
|| !optimized_out_size
);
1262 info
->entry
= vec_safe_copy (info
->entry
);
1263 if (info
->loop_iterations
)
1265 predicate p
= *info
->loop_iterations
;
1266 info
->loop_iterations
= NULL
;
1267 set_hint_predicate (&info
->loop_iterations
, p
);
1269 if (info
->loop_stride
)
1271 predicate p
= *info
->loop_stride
;
1272 info
->loop_stride
= NULL
;
1273 set_hint_predicate (&info
->loop_stride
, p
);
1275 if (info
->array_index
)
1277 predicate p
= *info
->array_index
;
1278 info
->array_index
= NULL
;
1279 set_hint_predicate (&info
->array_index
, p
);
1282 if (!dst
->global
.inlined_to
)
1283 inline_update_overall_summary (dst
);
1287 /* Hook that is called by cgraph.c when a node is duplicated. */
1290 inline_edge_duplication_hook (struct cgraph_edge
*src
,
1291 struct cgraph_edge
*dst
,
1292 ATTRIBUTE_UNUSED
void *data
)
1294 struct inline_edge_summary
*info
;
1295 struct inline_edge_summary
*srcinfo
;
1296 inline_summary_alloc ();
1297 info
= inline_edge_summary (dst
);
1298 srcinfo
= inline_edge_summary (src
);
1299 memcpy (info
, srcinfo
, sizeof (struct inline_edge_summary
));
1300 info
->predicate
= NULL
;
1301 edge_set_predicate (dst
, srcinfo
->predicate
);
1302 info
->param
= srcinfo
->param
.copy ();
1303 if (!dst
->indirect_unknown_callee
&& src
->indirect_unknown_callee
)
1305 info
->call_stmt_size
-= (eni_size_weights
.indirect_call_cost
1306 - eni_size_weights
.call_cost
);
1307 info
->call_stmt_time
-= (eni_time_weights
.indirect_call_cost
1308 - eni_time_weights
.call_cost
);
1313 /* Keep edge cache consistent across edge removal. */
1316 inline_edge_removal_hook (struct cgraph_edge
*edge
,
1317 void *data ATTRIBUTE_UNUSED
)
1319 if (edge_growth_cache
.exists ())
1320 reset_edge_growth_cache (edge
);
1321 reset_inline_edge_summary (edge
);
1325 /* Initialize growth caches. */
1328 initialize_growth_caches (void)
1330 if (symtab
->edges_max_uid
)
1331 edge_growth_cache
.safe_grow_cleared (symtab
->edges_max_uid
);
1335 /* Free growth caches. */
1338 free_growth_caches (void)
1340 edge_growth_cache
.release ();
1344 /* Dump edge summaries associated to NODE and recursively to all clones.
1345 Indent by INDENT. */
1348 dump_inline_edge_summary (FILE *f
, int indent
, struct cgraph_node
*node
,
1349 struct inline_summary
*info
)
1351 struct cgraph_edge
*edge
;
1352 for (edge
= node
->callees
; edge
; edge
= edge
->next_callee
)
1354 struct inline_edge_summary
*es
= inline_edge_summary (edge
);
1355 struct cgraph_node
*callee
= edge
->callee
->ultimate_alias_target ();
1359 "%*s%s/%i %s\n%*s loop depth:%2i freq:%4i size:%2i"
1360 " time: %2i callee size:%2i stack:%2i",
1361 indent
, "", callee
->name (), callee
->order
,
1362 !edge
->inline_failed
1363 ? "inlined" : cgraph_inline_failed_string (edge
-> inline_failed
),
1364 indent
, "", es
->loop_depth
, edge
->frequency
,
1365 es
->call_stmt_size
, es
->call_stmt_time
,
1366 (int) inline_summaries
->get (callee
)->size
/ INLINE_SIZE_SCALE
,
1367 (int) inline_summaries
->get (callee
)->estimated_stack_size
);
1371 fprintf (f
, " predicate: ");
1372 dump_predicate (f
, info
->conds
, es
->predicate
);
1376 if (es
->param
.exists ())
1377 for (i
= 0; i
< (int) es
->param
.length (); i
++)
1379 int prob
= es
->param
[i
].change_prob
;
1382 fprintf (f
, "%*s op%i is compile time invariant\n",
1384 else if (prob
!= REG_BR_PROB_BASE
)
1385 fprintf (f
, "%*s op%i change %f%% of time\n", indent
+ 2, "", i
,
1386 prob
* 100.0 / REG_BR_PROB_BASE
);
1388 if (!edge
->inline_failed
)
1390 fprintf (f
, "%*sStack frame offset %i, callee self size %i,"
1391 " callee size %i\n",
1393 (int) inline_summaries
->get (callee
)->stack_frame_offset
,
1394 (int) inline_summaries
->get (callee
)->estimated_self_stack_size
,
1395 (int) inline_summaries
->get (callee
)->estimated_stack_size
);
1396 dump_inline_edge_summary (f
, indent
+ 2, callee
, info
);
1399 for (edge
= node
->indirect_calls
; edge
; edge
= edge
->next_callee
)
1401 struct inline_edge_summary
*es
= inline_edge_summary (edge
);
1402 fprintf (f
, "%*sindirect call loop depth:%2i freq:%4i size:%2i"
1406 edge
->frequency
, es
->call_stmt_size
, es
->call_stmt_time
);
1409 fprintf (f
, "predicate: ");
1410 dump_predicate (f
, info
->conds
, es
->predicate
);
1419 dump_inline_summary (FILE *f
, struct cgraph_node
*node
)
1421 if (node
->definition
)
1423 struct inline_summary
*s
= inline_summaries
->get (node
);
1426 fprintf (f
, "Inline summary for %s/%i", node
->name (),
1428 if (DECL_DISREGARD_INLINE_LIMITS (node
->decl
))
1429 fprintf (f
, " always_inline");
1431 fprintf (f
, " inlinable");
1432 if (s
->contains_cilk_spawn
)
1433 fprintf (f
, " contains_cilk_spawn");
1434 if (s
->fp_expressions
)
1435 fprintf (f
, " fp_expression");
1436 fprintf (f
, "\n self time: %i\n", s
->self_time
);
1437 fprintf (f
, " global time: %i\n", s
->time
);
1438 fprintf (f
, " self size: %i\n", s
->self_size
);
1439 fprintf (f
, " global size: %i\n", s
->size
);
1440 fprintf (f
, " min size: %i\n", s
->min_size
);
1441 fprintf (f
, " self stack: %i\n",
1442 (int) s
->estimated_self_stack_size
);
1443 fprintf (f
, " global stack: %i\n", (int) s
->estimated_stack_size
);
1445 fprintf (f
, " estimated growth:%i\n", (int) s
->growth
);
1447 fprintf (f
, " In SCC: %i\n", (int) s
->scc_no
);
1448 for (i
= 0; vec_safe_iterate (s
->entry
, i
, &e
); i
++)
1450 fprintf (f
, " size:%f, time:%f, predicate:",
1451 (double) e
->size
/ INLINE_SIZE_SCALE
,
1452 (double) e
->time
/ INLINE_TIME_SCALE
);
1453 dump_predicate (f
, s
->conds
, &e
->predicate
);
1455 if (s
->loop_iterations
)
1457 fprintf (f
, " loop iterations:");
1458 dump_predicate (f
, s
->conds
, s
->loop_iterations
);
1462 fprintf (f
, " loop stride:");
1463 dump_predicate (f
, s
->conds
, s
->loop_stride
);
1467 fprintf (f
, " array index:");
1468 dump_predicate (f
, s
->conds
, s
->array_index
);
1470 fprintf (f
, " calls:\n");
1471 dump_inline_edge_summary (f
, 4, node
, s
);
1477 debug_inline_summary (struct cgraph_node
*node
)
1479 dump_inline_summary (stderr
, node
);
1483 dump_inline_summaries (FILE *f
)
1485 struct cgraph_node
*node
;
1487 FOR_EACH_DEFINED_FUNCTION (node
)
1488 if (!node
->global
.inlined_to
)
1489 dump_inline_summary (f
, node
);
1492 /* Give initial reasons why inlining would fail on EDGE. This gets either
1493 nullified or usually overwritten by more precise reasons later. */
1496 initialize_inline_failed (struct cgraph_edge
*e
)
1498 struct cgraph_node
*callee
= e
->callee
;
1500 if (e
->inline_failed
&& e
->inline_failed
!= CIF_BODY_NOT_AVAILABLE
1501 && cgraph_inline_failed_type (e
->inline_failed
) == CIF_FINAL_ERROR
)
1503 else if (e
->indirect_unknown_callee
)
1504 e
->inline_failed
= CIF_INDIRECT_UNKNOWN_CALL
;
1505 else if (!callee
->definition
)
1506 e
->inline_failed
= CIF_BODY_NOT_AVAILABLE
;
1507 else if (callee
->local
.redefined_extern_inline
)
1508 e
->inline_failed
= CIF_REDEFINED_EXTERN_INLINE
;
1509 else if (cfun
&& fn_contains_cilk_spawn_p (cfun
))
1510 /* We can't inline if the function is spawing a function. */
1511 e
->inline_failed
= CIF_CILK_SPAWN
;
1513 e
->inline_failed
= CIF_FUNCTION_NOT_CONSIDERED
;
1514 gcc_checking_assert (!e
->call_stmt_cannot_inline_p
1515 || cgraph_inline_failed_type (e
->inline_failed
)
1516 == CIF_FINAL_ERROR
);
1519 /* Callback of walk_aliased_vdefs. Flags that it has been invoked to the
1520 boolean variable pointed to by DATA. */
1523 mark_modified (ao_ref
*ao ATTRIBUTE_UNUSED
, tree vdef ATTRIBUTE_UNUSED
,
1526 bool *b
= (bool *) data
;
1531 /* If OP refers to value of function parameter, return the corresponding
1532 parameter. If non-NULL, the size of the memory load (or the SSA_NAME of the
1533 PARM_DECL) will be stored to *SIZE_P in that case too. */
1536 unmodified_parm_1 (gimple
*stmt
, tree op
, HOST_WIDE_INT
*size_p
)
1538 /* SSA_NAME referring to parm default def? */
1539 if (TREE_CODE (op
) == SSA_NAME
1540 && SSA_NAME_IS_DEFAULT_DEF (op
)
1541 && TREE_CODE (SSA_NAME_VAR (op
)) == PARM_DECL
)
1544 *size_p
= tree_to_shwi (TYPE_SIZE (TREE_TYPE (op
)));
1545 return SSA_NAME_VAR (op
);
1547 /* Non-SSA parm reference? */
1548 if (TREE_CODE (op
) == PARM_DECL
)
1550 bool modified
= false;
1553 ao_ref_init (&refd
, op
);
1554 walk_aliased_vdefs (&refd
, gimple_vuse (stmt
), mark_modified
, &modified
,
1559 *size_p
= tree_to_shwi (TYPE_SIZE (TREE_TYPE (op
)));
1566 /* If OP refers to value of function parameter, return the corresponding
1567 parameter. Also traverse chains of SSA register assignments. If non-NULL,
1568 the size of the memory load (or the SSA_NAME of the PARM_DECL) will be
1569 stored to *SIZE_P in that case too. */
1572 unmodified_parm (gimple
*stmt
, tree op
, HOST_WIDE_INT
*size_p
)
1574 tree res
= unmodified_parm_1 (stmt
, op
, size_p
);
1578 if (TREE_CODE (op
) == SSA_NAME
1579 && !SSA_NAME_IS_DEFAULT_DEF (op
)
1580 && gimple_assign_single_p (SSA_NAME_DEF_STMT (op
)))
1581 return unmodified_parm (SSA_NAME_DEF_STMT (op
),
1582 gimple_assign_rhs1 (SSA_NAME_DEF_STMT (op
)),
1587 /* If OP refers to a value of a function parameter or value loaded from an
1588 aggregate passed to a parameter (either by value or reference), return TRUE
1589 and store the number of the parameter to *INDEX_P, the access size into
1590 *SIZE_P, and information whether and how it has been loaded from an
1591 aggregate into *AGGPOS. INFO describes the function parameters, STMT is the
1592 statement in which OP is used or loaded. */
1595 unmodified_parm_or_parm_agg_item (struct ipa_func_body_info
*fbi
,
1596 gimple
*stmt
, tree op
, int *index_p
,
1597 HOST_WIDE_INT
*size_p
,
1598 struct agg_position_info
*aggpos
)
1600 tree res
= unmodified_parm_1 (stmt
, op
, size_p
);
1602 gcc_checking_assert (aggpos
);
1605 *index_p
= ipa_get_param_decl_index (fbi
->info
, res
);
1608 aggpos
->agg_contents
= false;
1609 aggpos
->by_ref
= false;
1613 if (TREE_CODE (op
) == SSA_NAME
)
1615 if (SSA_NAME_IS_DEFAULT_DEF (op
)
1616 || !gimple_assign_single_p (SSA_NAME_DEF_STMT (op
)))
1618 stmt
= SSA_NAME_DEF_STMT (op
);
1619 op
= gimple_assign_rhs1 (stmt
);
1620 if (!REFERENCE_CLASS_P (op
))
1621 return unmodified_parm_or_parm_agg_item (fbi
, stmt
, op
, index_p
, size_p
,
1625 aggpos
->agg_contents
= true;
1626 return ipa_load_from_parm_agg (fbi
, fbi
->info
->descriptors
,
1627 stmt
, op
, index_p
, &aggpos
->offset
,
1628 size_p
, &aggpos
->by_ref
);
1631 /* See if statement might disappear after inlining.
1632 0 - means not eliminated
1633 1 - half of statements goes away
1634 2 - for sure it is eliminated.
1635 We are not terribly sophisticated, basically looking for simple abstraction
1636 penalty wrappers. */
1639 eliminated_by_inlining_prob (gimple
*stmt
)
1641 enum gimple_code code
= gimple_code (stmt
);
1642 enum tree_code rhs_code
;
1652 if (gimple_num_ops (stmt
) != 2)
1655 rhs_code
= gimple_assign_rhs_code (stmt
);
1657 /* Casts of parameters, loads from parameters passed by reference
1658 and stores to return value or parameters are often free after
1659 inlining dua to SRA and further combining.
1660 Assume that half of statements goes away. */
1661 if (CONVERT_EXPR_CODE_P (rhs_code
)
1662 || rhs_code
== VIEW_CONVERT_EXPR
1663 || rhs_code
== ADDR_EXPR
1664 || gimple_assign_rhs_class (stmt
) == GIMPLE_SINGLE_RHS
)
1666 tree rhs
= gimple_assign_rhs1 (stmt
);
1667 tree lhs
= gimple_assign_lhs (stmt
);
1668 tree inner_rhs
= get_base_address (rhs
);
1669 tree inner_lhs
= get_base_address (lhs
);
1670 bool rhs_free
= false;
1671 bool lhs_free
= false;
1678 /* Reads of parameter are expected to be free. */
1679 if (unmodified_parm (stmt
, inner_rhs
, NULL
))
1681 /* Match expressions of form &this->field. Those will most likely
1682 combine with something upstream after inlining. */
1683 else if (TREE_CODE (inner_rhs
) == ADDR_EXPR
)
1685 tree op
= get_base_address (TREE_OPERAND (inner_rhs
, 0));
1686 if (TREE_CODE (op
) == PARM_DECL
)
1688 else if (TREE_CODE (op
) == MEM_REF
1689 && unmodified_parm (stmt
, TREE_OPERAND (op
, 0), NULL
))
1693 /* When parameter is not SSA register because its address is taken
1694 and it is just copied into one, the statement will be completely
1695 free after inlining (we will copy propagate backward). */
1696 if (rhs_free
&& is_gimple_reg (lhs
))
1699 /* Reads of parameters passed by reference
1700 expected to be free (i.e. optimized out after inlining). */
1701 if (TREE_CODE (inner_rhs
) == MEM_REF
1702 && unmodified_parm (stmt
, TREE_OPERAND (inner_rhs
, 0), NULL
))
1705 /* Copying parameter passed by reference into gimple register is
1706 probably also going to copy propagate, but we can't be quite
1708 if (rhs_free
&& is_gimple_reg (lhs
))
1711 /* Writes to parameters, parameters passed by value and return value
1712 (either dirrectly or passed via invisible reference) are free.
1714 TODO: We ought to handle testcase like
1715 struct a {int a,b;};
1717 retrurnsturct (void)
1723 This translate into:
1738 For that we either need to copy ipa-split logic detecting writes
1740 if (TREE_CODE (inner_lhs
) == PARM_DECL
1741 || TREE_CODE (inner_lhs
) == RESULT_DECL
1742 || (TREE_CODE (inner_lhs
) == MEM_REF
1743 && (unmodified_parm (stmt
, TREE_OPERAND (inner_lhs
, 0), NULL
)
1744 || (TREE_CODE (TREE_OPERAND (inner_lhs
, 0)) == SSA_NAME
1745 && SSA_NAME_VAR (TREE_OPERAND (inner_lhs
, 0))
1746 && TREE_CODE (SSA_NAME_VAR (TREE_OPERAND
1748 0))) == RESULT_DECL
))))
1751 && (is_gimple_reg (rhs
) || is_gimple_min_invariant (rhs
)))
1753 if (lhs_free
&& rhs_free
)
1763 /* If BB ends by a conditional we can turn into predicates, attach corresponding
1764 predicates to the CFG edges. */
1767 set_cond_stmt_execution_predicate (struct ipa_func_body_info
*fbi
,
1768 struct inline_summary
*summary
,
1775 struct agg_position_info aggpos
;
1776 enum tree_code code
, inverted_code
;
1782 last
= last_stmt (bb
);
1783 if (!last
|| gimple_code (last
) != GIMPLE_COND
)
1785 if (!is_gimple_ip_invariant (gimple_cond_rhs (last
)))
1787 op
= gimple_cond_lhs (last
);
1788 /* TODO: handle conditionals like
1791 if (unmodified_parm_or_parm_agg_item (fbi
, last
, op
, &index
, &size
, &aggpos
))
1793 code
= gimple_cond_code (last
);
1794 inverted_code
= invert_tree_comparison (code
, HONOR_NANS (op
));
1796 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1798 enum tree_code this_code
= (e
->flags
& EDGE_TRUE_VALUE
1799 ? code
: inverted_code
);
1800 /* invert_tree_comparison will return ERROR_MARK on FP
1801 comparsions that are not EQ/NE instead of returning proper
1802 unordered one. Be sure it is not confused with NON_CONSTANT. */
1803 if (this_code
!= ERROR_MARK
)
1806 = add_condition (summary
, index
, size
, &aggpos
, this_code
,
1807 unshare_expr_without_location
1808 (gimple_cond_rhs (last
)));
1809 e
->aux
= edge_predicate_pool
.allocate ();
1810 *(struct predicate
*) e
->aux
= p
;
1815 if (TREE_CODE (op
) != SSA_NAME
)
1818 if (builtin_constant_p (op))
1822 Here we can predicate nonconstant_code. We can't
1823 really handle constant_code since we have no predicate
1824 for this and also the constant code is not known to be
1825 optimized away when inliner doen't see operand is constant.
1826 Other optimizers might think otherwise. */
1827 if (gimple_cond_code (last
) != NE_EXPR
1828 || !integer_zerop (gimple_cond_rhs (last
)))
1830 set_stmt
= SSA_NAME_DEF_STMT (op
);
1831 if (!gimple_call_builtin_p (set_stmt
, BUILT_IN_CONSTANT_P
)
1832 || gimple_call_num_args (set_stmt
) != 1)
1834 op2
= gimple_call_arg (set_stmt
, 0);
1835 if (!unmodified_parm_or_parm_agg_item (fbi
, set_stmt
, op2
, &index
, &size
,
1838 FOR_EACH_EDGE (e
, ei
, bb
->succs
) if (e
->flags
& EDGE_FALSE_VALUE
)
1840 struct predicate p
= add_condition (summary
, index
, size
, &aggpos
,
1841 IS_NOT_CONSTANT
, NULL_TREE
);
1842 e
->aux
= edge_predicate_pool
.allocate ();
1843 *(struct predicate
*) e
->aux
= p
;
1848 /* If BB ends by a switch we can turn into predicates, attach corresponding
1849 predicates to the CFG edges. */
1852 set_switch_stmt_execution_predicate (struct ipa_func_body_info
*fbi
,
1853 struct inline_summary
*summary
,
1860 struct agg_position_info aggpos
;
1866 lastg
= last_stmt (bb
);
1867 if (!lastg
|| gimple_code (lastg
) != GIMPLE_SWITCH
)
1869 gswitch
*last
= as_a
<gswitch
*> (lastg
);
1870 op
= gimple_switch_index (last
);
1871 if (!unmodified_parm_or_parm_agg_item (fbi
, last
, op
, &index
, &size
, &aggpos
))
1874 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1876 e
->aux
= edge_predicate_pool
.allocate ();
1877 *(struct predicate
*) e
->aux
= false_predicate ();
1879 n
= gimple_switch_num_labels (last
);
1880 for (case_idx
= 0; case_idx
< n
; ++case_idx
)
1882 tree cl
= gimple_switch_label (last
, case_idx
);
1886 e
= find_edge (bb
, label_to_block (CASE_LABEL (cl
)));
1887 min
= CASE_LOW (cl
);
1888 max
= CASE_HIGH (cl
);
1890 /* For default we might want to construct predicate that none
1891 of cases is met, but it is bit hard to do not having negations
1892 of conditionals handy. */
1894 p
= true_predicate ();
1896 p
= add_condition (summary
, index
, size
, &aggpos
, EQ_EXPR
,
1897 unshare_expr_without_location (min
));
1900 struct predicate p1
, p2
;
1901 p1
= add_condition (summary
, index
, size
, &aggpos
, GE_EXPR
,
1902 unshare_expr_without_location (min
));
1903 p2
= add_condition (summary
, index
, size
, &aggpos
, LE_EXPR
,
1904 unshare_expr_without_location (max
));
1905 p
= and_predicates (summary
->conds
, &p1
, &p2
);
1907 *(struct predicate
*) e
->aux
1908 = or_predicates (summary
->conds
, &p
, (struct predicate
*) e
->aux
);
1913 /* For each BB in NODE attach to its AUX pointer predicate under
1914 which it is executable. */
1917 compute_bb_predicates (struct ipa_func_body_info
*fbi
,
1918 struct cgraph_node
*node
,
1919 struct inline_summary
*summary
)
1921 struct function
*my_function
= DECL_STRUCT_FUNCTION (node
->decl
);
1925 FOR_EACH_BB_FN (bb
, my_function
)
1927 set_cond_stmt_execution_predicate (fbi
, summary
, bb
);
1928 set_switch_stmt_execution_predicate (fbi
, summary
, bb
);
1931 /* Entry block is always executable. */
1932 ENTRY_BLOCK_PTR_FOR_FN (my_function
)->aux
1933 = edge_predicate_pool
.allocate ();
1934 *(struct predicate
*) ENTRY_BLOCK_PTR_FOR_FN (my_function
)->aux
1935 = true_predicate ();
1937 /* A simple dataflow propagation of predicates forward in the CFG.
1938 TODO: work in reverse postorder. */
1942 FOR_EACH_BB_FN (bb
, my_function
)
1944 struct predicate p
= false_predicate ();
1947 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
1951 struct predicate this_bb_predicate
1952 = *(struct predicate
*) e
->src
->aux
;
1955 = and_predicates (summary
->conds
, &this_bb_predicate
,
1956 (struct predicate
*) e
->aux
);
1957 p
= or_predicates (summary
->conds
, &p
, &this_bb_predicate
);
1958 if (true_predicate_p (&p
))
1962 if (false_predicate_p (&p
))
1963 gcc_assert (!bb
->aux
);
1969 bb
->aux
= edge_predicate_pool
.allocate ();
1970 *((struct predicate
*) bb
->aux
) = p
;
1972 else if (!predicates_equal_p (&p
, (struct predicate
*) bb
->aux
))
1974 /* This OR operation is needed to ensure monotonous data flow
1975 in the case we hit the limit on number of clauses and the
1976 and/or operations above give approximate answers. */
1977 p
= or_predicates (summary
->conds
, &p
, (struct predicate
*)bb
->aux
);
1978 if (!predicates_equal_p (&p
, (struct predicate
*) bb
->aux
))
1981 *((struct predicate
*) bb
->aux
) = p
;
1990 /* We keep info about constantness of SSA names. */
1992 typedef struct predicate predicate_t
;
1993 /* Return predicate specifying when the STMT might have result that is not
1994 a compile time constant. */
1996 static struct predicate
1997 will_be_nonconstant_expr_predicate (struct ipa_node_params
*info
,
1998 struct inline_summary
*summary
,
2000 vec
<predicate_t
> nonconstant_names
)
2006 while (UNARY_CLASS_P (expr
))
2007 expr
= TREE_OPERAND (expr
, 0);
2009 parm
= unmodified_parm (NULL
, expr
, &size
);
2010 if (parm
&& (index
= ipa_get_param_decl_index (info
, parm
)) >= 0)
2011 return add_condition (summary
, index
, size
, NULL
, CHANGED
, NULL_TREE
);
2012 if (is_gimple_min_invariant (expr
))
2013 return false_predicate ();
2014 if (TREE_CODE (expr
) == SSA_NAME
)
2015 return nonconstant_names
[SSA_NAME_VERSION (expr
)];
2016 if (BINARY_CLASS_P (expr
) || COMPARISON_CLASS_P (expr
))
2018 struct predicate p1
= will_be_nonconstant_expr_predicate
2019 (info
, summary
, TREE_OPERAND (expr
, 0),
2021 struct predicate p2
;
2022 if (true_predicate_p (&p1
))
2024 p2
= will_be_nonconstant_expr_predicate (info
, summary
,
2025 TREE_OPERAND (expr
, 1),
2027 return or_predicates (summary
->conds
, &p1
, &p2
);
2029 else if (TREE_CODE (expr
) == COND_EXPR
)
2031 struct predicate p1
= will_be_nonconstant_expr_predicate
2032 (info
, summary
, TREE_OPERAND (expr
, 0),
2034 struct predicate p2
;
2035 if (true_predicate_p (&p1
))
2037 p2
= will_be_nonconstant_expr_predicate (info
, summary
,
2038 TREE_OPERAND (expr
, 1),
2040 if (true_predicate_p (&p2
))
2042 p1
= or_predicates (summary
->conds
, &p1
, &p2
);
2043 p2
= will_be_nonconstant_expr_predicate (info
, summary
,
2044 TREE_OPERAND (expr
, 2),
2046 return or_predicates (summary
->conds
, &p1
, &p2
);
2053 return false_predicate ();
2057 /* Return predicate specifying when the STMT might have result that is not
2058 a compile time constant. */
2060 static struct predicate
2061 will_be_nonconstant_predicate (struct ipa_func_body_info
*fbi
,
2062 struct inline_summary
*summary
,
2064 vec
<predicate_t
> nonconstant_names
)
2066 struct predicate p
= true_predicate ();
2069 struct predicate op_non_const
;
2073 struct agg_position_info aggpos
;
2075 /* What statments might be optimized away
2076 when their arguments are constant. */
2077 if (gimple_code (stmt
) != GIMPLE_ASSIGN
2078 && gimple_code (stmt
) != GIMPLE_COND
2079 && gimple_code (stmt
) != GIMPLE_SWITCH
2080 && (gimple_code (stmt
) != GIMPLE_CALL
2081 || !(gimple_call_flags (stmt
) & ECF_CONST
)))
2084 /* Stores will stay anyway. */
2085 if (gimple_store_p (stmt
))
2088 is_load
= gimple_assign_load_p (stmt
);
2090 /* Loads can be optimized when the value is known. */
2094 gcc_assert (gimple_assign_single_p (stmt
));
2095 op
= gimple_assign_rhs1 (stmt
);
2096 if (!unmodified_parm_or_parm_agg_item (fbi
, stmt
, op
, &base_index
, &size
,
2103 /* See if we understand all operands before we start
2104 adding conditionals. */
2105 FOR_EACH_SSA_TREE_OPERAND (use
, stmt
, iter
, SSA_OP_USE
)
2107 tree parm
= unmodified_parm (stmt
, use
, NULL
);
2108 /* For arguments we can build a condition. */
2109 if (parm
&& ipa_get_param_decl_index (fbi
->info
, parm
) >= 0)
2111 if (TREE_CODE (use
) != SSA_NAME
)
2113 /* If we know when operand is constant,
2114 we still can say something useful. */
2115 if (!true_predicate_p (&nonconstant_names
[SSA_NAME_VERSION (use
)]))
2122 add_condition (summary
, base_index
, size
, &aggpos
, CHANGED
, NULL
);
2124 op_non_const
= false_predicate ();
2125 FOR_EACH_SSA_TREE_OPERAND (use
, stmt
, iter
, SSA_OP_USE
)
2128 tree parm
= unmodified_parm (stmt
, use
, &size
);
2131 if (parm
&& (index
= ipa_get_param_decl_index (fbi
->info
, parm
)) >= 0)
2133 if (index
!= base_index
)
2134 p
= add_condition (summary
, index
, size
, NULL
, CHANGED
, NULL_TREE
);
2139 p
= nonconstant_names
[SSA_NAME_VERSION (use
)];
2140 op_non_const
= or_predicates (summary
->conds
, &p
, &op_non_const
);
2142 if ((gimple_code (stmt
) == GIMPLE_ASSIGN
|| gimple_code (stmt
) == GIMPLE_CALL
)
2143 && gimple_op (stmt
, 0)
2144 && TREE_CODE (gimple_op (stmt
, 0)) == SSA_NAME
)
2145 nonconstant_names
[SSA_NAME_VERSION (gimple_op (stmt
, 0))]
2147 return op_non_const
;
2150 struct record_modified_bb_info
2156 /* Callback of walk_aliased_vdefs. Records basic blocks where the value may be
2157 set except for info->stmt. */
2160 record_modified (ao_ref
*ao ATTRIBUTE_UNUSED
, tree vdef
, void *data
)
2162 struct record_modified_bb_info
*info
=
2163 (struct record_modified_bb_info
*) data
;
2164 if (SSA_NAME_DEF_STMT (vdef
) == info
->stmt
)
2166 bitmap_set_bit (info
->bb_set
,
2167 SSA_NAME_IS_DEFAULT_DEF (vdef
)
2168 ? ENTRY_BLOCK_PTR_FOR_FN (cfun
)->index
2169 : gimple_bb (SSA_NAME_DEF_STMT (vdef
))->index
);
2173 /* Return probability (based on REG_BR_PROB_BASE) that I-th parameter of STMT
2174 will change since last invocation of STMT.
2176 Value 0 is reserved for compile time invariants.
2177 For common parameters it is REG_BR_PROB_BASE. For loop invariants it
2178 ought to be REG_BR_PROB_BASE / estimated_iters. */
2181 param_change_prob (gimple
*stmt
, int i
)
2183 tree op
= gimple_call_arg (stmt
, i
);
2184 basic_block bb
= gimple_bb (stmt
);
2187 /* Global invariants neve change. */
2188 if (is_gimple_min_invariant (op
))
2190 /* We would have to do non-trivial analysis to really work out what
2191 is the probability of value to change (i.e. when init statement
2192 is in a sibling loop of the call).
2194 We do an conservative estimate: when call is executed N times more often
2195 than the statement defining value, we take the frequency 1/N. */
2196 if (TREE_CODE (op
) == SSA_NAME
)
2201 return REG_BR_PROB_BASE
;
2203 if (SSA_NAME_IS_DEFAULT_DEF (op
))
2204 init_freq
= ENTRY_BLOCK_PTR_FOR_FN (cfun
)->frequency
;
2206 init_freq
= gimple_bb (SSA_NAME_DEF_STMT (op
))->frequency
;
2210 if (init_freq
< bb
->frequency
)
2211 return MAX (GCOV_COMPUTE_SCALE (init_freq
, bb
->frequency
), 1);
2213 return REG_BR_PROB_BASE
;
2216 base
= get_base_address (op
);
2221 struct record_modified_bb_info info
;
2224 tree init
= ctor_for_folding (base
);
2226 if (init
!= error_mark_node
)
2229 return REG_BR_PROB_BASE
;
2230 ao_ref_init (&refd
, op
);
2232 info
.bb_set
= BITMAP_ALLOC (NULL
);
2233 walk_aliased_vdefs (&refd
, gimple_vuse (stmt
), record_modified
, &info
,
2235 if (bitmap_bit_p (info
.bb_set
, bb
->index
))
2237 BITMAP_FREE (info
.bb_set
);
2238 return REG_BR_PROB_BASE
;
2241 /* Assume that every memory is initialized at entry.
2242 TODO: Can we easilly determine if value is always defined
2243 and thus we may skip entry block? */
2244 if (ENTRY_BLOCK_PTR_FOR_FN (cfun
)->frequency
)
2245 max
= ENTRY_BLOCK_PTR_FOR_FN (cfun
)->frequency
;
2249 EXECUTE_IF_SET_IN_BITMAP (info
.bb_set
, 0, index
, bi
)
2250 max
= MIN (max
, BASIC_BLOCK_FOR_FN (cfun
, index
)->frequency
);
2252 BITMAP_FREE (info
.bb_set
);
2253 if (max
< bb
->frequency
)
2254 return MAX (GCOV_COMPUTE_SCALE (max
, bb
->frequency
), 1);
2256 return REG_BR_PROB_BASE
;
2258 return REG_BR_PROB_BASE
;
2261 /* Find whether a basic block BB is the final block of a (half) diamond CFG
2262 sub-graph and if the predicate the condition depends on is known. If so,
2263 return true and store the pointer the predicate in *P. */
2266 phi_result_unknown_predicate (struct ipa_node_params
*info
,
2267 inline_summary
*summary
, basic_block bb
,
2268 struct predicate
*p
,
2269 vec
<predicate_t
> nonconstant_names
)
2273 basic_block first_bb
= NULL
;
2276 if (single_pred_p (bb
))
2278 *p
= false_predicate ();
2282 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
2284 if (single_succ_p (e
->src
))
2286 if (!single_pred_p (e
->src
))
2289 first_bb
= single_pred (e
->src
);
2290 else if (single_pred (e
->src
) != first_bb
)
2297 else if (e
->src
!= first_bb
)
2305 stmt
= last_stmt (first_bb
);
2307 || gimple_code (stmt
) != GIMPLE_COND
2308 || !is_gimple_ip_invariant (gimple_cond_rhs (stmt
)))
2311 *p
= will_be_nonconstant_expr_predicate (info
, summary
,
2312 gimple_cond_lhs (stmt
),
2314 if (true_predicate_p (p
))
2320 /* Given a PHI statement in a function described by inline properties SUMMARY
2321 and *P being the predicate describing whether the selected PHI argument is
2322 known, store a predicate for the result of the PHI statement into
2323 NONCONSTANT_NAMES, if possible. */
2326 predicate_for_phi_result (struct inline_summary
*summary
, gphi
*phi
,
2327 struct predicate
*p
,
2328 vec
<predicate_t
> nonconstant_names
)
2332 for (i
= 0; i
< gimple_phi_num_args (phi
); i
++)
2334 tree arg
= gimple_phi_arg (phi
, i
)->def
;
2335 if (!is_gimple_min_invariant (arg
))
2337 gcc_assert (TREE_CODE (arg
) == SSA_NAME
);
2338 *p
= or_predicates (summary
->conds
, p
,
2339 &nonconstant_names
[SSA_NAME_VERSION (arg
)]);
2340 if (true_predicate_p (p
))
2345 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2347 fprintf (dump_file
, "\t\tphi predicate: ");
2348 dump_predicate (dump_file
, summary
->conds
, p
);
2350 nonconstant_names
[SSA_NAME_VERSION (gimple_phi_result (phi
))] = *p
;
2353 /* Return predicate specifying when array index in access OP becomes non-constant. */
2355 static struct predicate
2356 array_index_predicate (inline_summary
*info
,
2357 vec
< predicate_t
> nonconstant_names
, tree op
)
2359 struct predicate p
= false_predicate ();
2360 while (handled_component_p (op
))
2362 if (TREE_CODE (op
) == ARRAY_REF
|| TREE_CODE (op
) == ARRAY_RANGE_REF
)
2364 if (TREE_CODE (TREE_OPERAND (op
, 1)) == SSA_NAME
)
2365 p
= or_predicates (info
->conds
, &p
,
2366 &nonconstant_names
[SSA_NAME_VERSION
2367 (TREE_OPERAND (op
, 1))]);
2369 op
= TREE_OPERAND (op
, 0);
2374 /* For a typical usage of __builtin_expect (a<b, 1), we
2375 may introduce an extra relation stmt:
2376 With the builtin, we have
2379 t3 = __builtin_expect (t2, 1);
2382 Without the builtin, we have
2385 This affects the size/time estimation and may have
2386 an impact on the earlier inlining.
2387 Here find this pattern and fix it up later. */
2390 find_foldable_builtin_expect (basic_block bb
)
2392 gimple_stmt_iterator bsi
;
2394 for (bsi
= gsi_start_bb (bb
); !gsi_end_p (bsi
); gsi_next (&bsi
))
2396 gimple
*stmt
= gsi_stmt (bsi
);
2397 if (gimple_call_builtin_p (stmt
, BUILT_IN_EXPECT
)
2398 || (is_gimple_call (stmt
)
2399 && gimple_call_internal_p (stmt
)
2400 && gimple_call_internal_fn (stmt
) == IFN_BUILTIN_EXPECT
))
2402 tree var
= gimple_call_lhs (stmt
);
2403 tree arg
= gimple_call_arg (stmt
, 0);
2404 use_operand_p use_p
;
2411 gcc_assert (TREE_CODE (var
) == SSA_NAME
);
2413 while (TREE_CODE (arg
) == SSA_NAME
)
2415 gimple
*stmt_tmp
= SSA_NAME_DEF_STMT (arg
);
2416 if (!is_gimple_assign (stmt_tmp
))
2418 switch (gimple_assign_rhs_code (stmt_tmp
))
2437 arg
= gimple_assign_rhs1 (stmt_tmp
);
2440 if (match
&& single_imm_use (var
, &use_p
, &use_stmt
)
2441 && gimple_code (use_stmt
) == GIMPLE_COND
)
2448 /* Return true when the basic blocks contains only clobbers followed by RESX.
2449 Such BBs are kept around to make removal of dead stores possible with
2450 presence of EH and will be optimized out by optimize_clobbers later in the
2453 NEED_EH is used to recurse in case the clobber has non-EH predecestors
2454 that can be clobber only, too.. When it is false, the RESX is not necessary
2455 on the end of basic block. */
2458 clobber_only_eh_bb_p (basic_block bb
, bool need_eh
= true)
2460 gimple_stmt_iterator gsi
= gsi_last_bb (bb
);
2466 if (gsi_end_p (gsi
))
2468 if (gimple_code (gsi_stmt (gsi
)) != GIMPLE_RESX
)
2472 else if (!single_succ_p (bb
))
2475 for (; !gsi_end_p (gsi
); gsi_prev (&gsi
))
2477 gimple
*stmt
= gsi_stmt (gsi
);
2478 if (is_gimple_debug (stmt
))
2480 if (gimple_clobber_p (stmt
))
2482 if (gimple_code (stmt
) == GIMPLE_LABEL
)
2487 /* See if all predecestors are either throws or clobber only BBs. */
2488 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
2489 if (!(e
->flags
& EDGE_EH
)
2490 && !clobber_only_eh_bb_p (e
->src
, false))
2496 /* Return true if STMT compute a floating point expression that may be affected
2497 by -ffast-math and similar flags. */
2500 fp_expression_p (gimple
*stmt
)
2505 FOR_EACH_SSA_TREE_OPERAND (op
, stmt
, i
, SSA_OP_DEF
|SSA_OP_USE
)
2506 if (FLOAT_TYPE_P (TREE_TYPE (op
)))
2511 /* Compute function body size parameters for NODE.
2512 When EARLY is true, we compute only simple summaries without
2513 non-trivial predicates to drive the early inliner. */
2516 estimate_function_body_sizes (struct cgraph_node
*node
, bool early
)
2519 /* Estimate static overhead for function prologue/epilogue and alignment. */
2521 /* Benefits are scaled by probability of elimination that is in range
2524 struct function
*my_function
= DECL_STRUCT_FUNCTION (node
->decl
);
2526 struct inline_summary
*info
= inline_summaries
->get (node
);
2527 struct predicate bb_predicate
;
2528 struct ipa_func_body_info fbi
;
2529 vec
<predicate_t
> nonconstant_names
= vNULL
;
2532 predicate array_index
= true_predicate ();
2533 gimple
*fix_builtin_expect_stmt
;
2535 gcc_assert (my_function
&& my_function
->cfg
);
2536 gcc_assert (cfun
== my_function
);
2538 memset(&fbi
, 0, sizeof(fbi
));
2542 /* When optimizing and analyzing for IPA inliner, initialize loop optimizer
2543 so we can produce proper inline hints.
2545 When optimizing and analyzing for early inliner, initialize node params
2546 so we can produce correct BB predicates. */
2548 if (opt_for_fn (node
->decl
, optimize
))
2550 calculate_dominance_info (CDI_DOMINATORS
);
2552 loop_optimizer_init (LOOPS_NORMAL
| LOOPS_HAVE_RECORDED_EXITS
);
2555 ipa_check_create_node_params ();
2556 ipa_initialize_node_params (node
);
2559 if (ipa_node_params_sum
)
2562 fbi
.info
= IPA_NODE_REF (node
);
2563 fbi
.bb_infos
= vNULL
;
2564 fbi
.bb_infos
.safe_grow_cleared (last_basic_block_for_fn (cfun
));
2565 fbi
.param_count
= count_formal_params(node
->decl
);
2566 nonconstant_names
.safe_grow_cleared
2567 (SSANAMES (my_function
)->length ());
2572 fprintf (dump_file
, "\nAnalyzing function body size: %s\n",
2575 /* When we run into maximal number of entries, we assign everything to the
2576 constant truth case. Be sure to have it in list. */
2577 bb_predicate
= true_predicate ();
2578 account_size_time (info
, 0, 0, &bb_predicate
);
2580 bb_predicate
= not_inlined_predicate ();
2581 account_size_time (info
, 2 * INLINE_SIZE_SCALE
, 0, &bb_predicate
);
2584 compute_bb_predicates (&fbi
, node
, info
);
2585 order
= XNEWVEC (int, n_basic_blocks_for_fn (cfun
));
2586 nblocks
= pre_and_rev_post_order_compute (NULL
, order
, false);
2587 for (n
= 0; n
< nblocks
; n
++)
2589 bb
= BASIC_BLOCK_FOR_FN (cfun
, order
[n
]);
2590 freq
= compute_call_stmt_bb_frequency (node
->decl
, bb
);
2591 if (clobber_only_eh_bb_p (bb
))
2593 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2594 fprintf (dump_file
, "\n Ignoring BB %i;"
2595 " it will be optimized away by cleanup_clobbers\n",
2600 /* TODO: Obviously predicates can be propagated down across CFG. */
2604 bb_predicate
= *(struct predicate
*) bb
->aux
;
2606 bb_predicate
= false_predicate ();
2609 bb_predicate
= true_predicate ();
2611 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2613 fprintf (dump_file
, "\n BB %i predicate:", bb
->index
);
2614 dump_predicate (dump_file
, info
->conds
, &bb_predicate
);
2617 if (fbi
.info
&& nonconstant_names
.exists ())
2619 struct predicate phi_predicate
;
2620 bool first_phi
= true;
2622 for (gphi_iterator bsi
= gsi_start_phis (bb
); !gsi_end_p (bsi
);
2626 && !phi_result_unknown_predicate (fbi
.info
, info
, bb
,
2631 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2633 fprintf (dump_file
, " ");
2634 print_gimple_stmt (dump_file
, gsi_stmt (bsi
), 0, 0);
2636 predicate_for_phi_result (info
, bsi
.phi (), &phi_predicate
,
2641 fix_builtin_expect_stmt
= find_foldable_builtin_expect (bb
);
2643 for (gimple_stmt_iterator bsi
= gsi_start_bb (bb
); !gsi_end_p (bsi
);
2646 gimple
*stmt
= gsi_stmt (bsi
);
2647 int this_size
= estimate_num_insns (stmt
, &eni_size_weights
);
2648 int this_time
= estimate_num_insns (stmt
, &eni_time_weights
);
2650 struct predicate will_be_nonconstant
;
2652 /* This relation stmt should be folded after we remove
2653 buildin_expect call. Adjust the cost here. */
2654 if (stmt
== fix_builtin_expect_stmt
)
2660 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2662 fprintf (dump_file
, " ");
2663 print_gimple_stmt (dump_file
, stmt
, 0, 0);
2664 fprintf (dump_file
, "\t\tfreq:%3.2f size:%3i time:%3i\n",
2665 ((double) freq
) / CGRAPH_FREQ_BASE
, this_size
,
2669 if (gimple_assign_load_p (stmt
) && nonconstant_names
.exists ())
2671 struct predicate this_array_index
;
2673 array_index_predicate (info
, nonconstant_names
,
2674 gimple_assign_rhs1 (stmt
));
2675 if (!false_predicate_p (&this_array_index
))
2677 and_predicates (info
->conds
, &array_index
,
2680 if (gimple_store_p (stmt
) && nonconstant_names
.exists ())
2682 struct predicate this_array_index
;
2684 array_index_predicate (info
, nonconstant_names
,
2685 gimple_get_lhs (stmt
));
2686 if (!false_predicate_p (&this_array_index
))
2688 and_predicates (info
->conds
, &array_index
,
2693 if (is_gimple_call (stmt
)
2694 && !gimple_call_internal_p (stmt
))
2696 struct cgraph_edge
*edge
= node
->get_edge (stmt
);
2697 struct inline_edge_summary
*es
= inline_edge_summary (edge
);
2699 /* Special case: results of BUILT_IN_CONSTANT_P will be always
2700 resolved as constant. We however don't want to optimize
2701 out the cgraph edges. */
2702 if (nonconstant_names
.exists ()
2703 && gimple_call_builtin_p (stmt
, BUILT_IN_CONSTANT_P
)
2704 && gimple_call_lhs (stmt
)
2705 && TREE_CODE (gimple_call_lhs (stmt
)) == SSA_NAME
)
2707 struct predicate false_p
= false_predicate ();
2708 nonconstant_names
[SSA_NAME_VERSION (gimple_call_lhs (stmt
))]
2711 if (ipa_node_params_sum
)
2713 int count
= gimple_call_num_args (stmt
);
2717 es
->param
.safe_grow_cleared (count
);
2718 for (i
= 0; i
< count
; i
++)
2720 int prob
= param_change_prob (stmt
, i
);
2721 gcc_assert (prob
>= 0 && prob
<= REG_BR_PROB_BASE
);
2722 es
->param
[i
].change_prob
= prob
;
2726 es
->call_stmt_size
= this_size
;
2727 es
->call_stmt_time
= this_time
;
2728 es
->loop_depth
= bb_loop_depth (bb
);
2729 edge_set_predicate (edge
, &bb_predicate
);
2732 /* TODO: When conditional jump or swithc is known to be constant, but
2733 we did not translate it into the predicates, we really can account
2734 just maximum of the possible paths. */
2737 = will_be_nonconstant_predicate (&fbi
, info
,
2738 stmt
, nonconstant_names
);
2739 if (this_time
|| this_size
)
2745 prob
= eliminated_by_inlining_prob (stmt
);
2746 if (prob
== 1 && dump_file
&& (dump_flags
& TDF_DETAILS
))
2748 "\t\t50%% will be eliminated by inlining\n");
2749 if (prob
== 2 && dump_file
&& (dump_flags
& TDF_DETAILS
))
2750 fprintf (dump_file
, "\t\tWill be eliminated by inlining\n");
2753 p
= and_predicates (info
->conds
, &bb_predicate
,
2754 &will_be_nonconstant
);
2756 p
= true_predicate ();
2758 if (!false_predicate_p (&p
)
2759 || (is_gimple_call (stmt
)
2760 && !false_predicate_p (&bb_predicate
)))
2764 if (time
> MAX_TIME
* INLINE_TIME_SCALE
)
2765 time
= MAX_TIME
* INLINE_TIME_SCALE
;
2768 /* We account everything but the calls. Calls have their own
2769 size/time info attached to cgraph edges. This is necessary
2770 in order to make the cost disappear after inlining. */
2771 if (!is_gimple_call (stmt
))
2775 struct predicate ip
= not_inlined_predicate ();
2776 ip
= and_predicates (info
->conds
, &ip
, &p
);
2777 account_size_time (info
, this_size
* prob
,
2778 this_time
* prob
, &ip
);
2781 account_size_time (info
, this_size
* (2 - prob
),
2782 this_time
* (2 - prob
), &p
);
2785 if (!info
->fp_expressions
&& fp_expression_p (stmt
))
2787 info
->fp_expressions
= true;
2789 fprintf (dump_file
, " fp_expression set\n");
2792 gcc_assert (time
>= 0);
2793 gcc_assert (size
>= 0);
2797 set_hint_predicate (&inline_summaries
->get (node
)->array_index
, array_index
);
2798 time
= (time
+ CGRAPH_FREQ_BASE
/ 2) / CGRAPH_FREQ_BASE
;
2799 if (time
> MAX_TIME
)
2803 if (nonconstant_names
.exists () && !early
)
2806 predicate loop_iterations
= true_predicate ();
2807 predicate loop_stride
= true_predicate ();
2809 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2810 flow_loops_dump (dump_file
, NULL
, 0);
2812 FOR_EACH_LOOP (loop
, 0)
2817 struct tree_niter_desc niter_desc
;
2818 bb_predicate
= *(struct predicate
*) loop
->header
->aux
;
2820 exits
= get_loop_exit_edges (loop
);
2821 FOR_EACH_VEC_ELT (exits
, j
, ex
)
2822 if (number_of_iterations_exit (loop
, ex
, &niter_desc
, false)
2823 && !is_gimple_min_invariant (niter_desc
.niter
))
2825 predicate will_be_nonconstant
2826 = will_be_nonconstant_expr_predicate (fbi
.info
, info
,
2829 if (!true_predicate_p (&will_be_nonconstant
))
2830 will_be_nonconstant
= and_predicates (info
->conds
,
2832 &will_be_nonconstant
);
2833 if (!true_predicate_p (&will_be_nonconstant
)
2834 && !false_predicate_p (&will_be_nonconstant
))
2835 /* This is slightly inprecise. We may want to represent each
2836 loop with independent predicate. */
2838 and_predicates (info
->conds
, &loop_iterations
,
2839 &will_be_nonconstant
);
2844 /* To avoid quadratic behavior we analyze stride predicates only
2845 with respect to the containing loop. Thus we simply iterate
2846 over all defs in the outermost loop body. */
2847 for (loop
= loops_for_fn (cfun
)->tree_root
->inner
;
2848 loop
!= NULL
; loop
= loop
->next
)
2850 basic_block
*body
= get_loop_body (loop
);
2851 for (unsigned i
= 0; i
< loop
->num_nodes
; i
++)
2853 gimple_stmt_iterator gsi
;
2854 bb_predicate
= *(struct predicate
*) body
[i
]->aux
;
2855 for (gsi
= gsi_start_bb (body
[i
]); !gsi_end_p (gsi
);
2858 gimple
*stmt
= gsi_stmt (gsi
);
2860 if (!is_gimple_assign (stmt
))
2863 tree def
= gimple_assign_lhs (stmt
);
2864 if (TREE_CODE (def
) != SSA_NAME
)
2868 if (!simple_iv (loop_containing_stmt (stmt
),
2869 loop_containing_stmt (stmt
),
2871 || is_gimple_min_invariant (iv
.step
))
2874 predicate will_be_nonconstant
2875 = will_be_nonconstant_expr_predicate (fbi
.info
, info
,
2878 if (!true_predicate_p (&will_be_nonconstant
))
2880 = and_predicates (info
->conds
, &bb_predicate
,
2881 &will_be_nonconstant
);
2882 if (!true_predicate_p (&will_be_nonconstant
)
2883 && !false_predicate_p (&will_be_nonconstant
))
2884 /* This is slightly inprecise. We may want to represent
2885 each loop with independent predicate. */
2886 loop_stride
= and_predicates (info
->conds
, &loop_stride
,
2887 &will_be_nonconstant
);
2892 set_hint_predicate (&inline_summaries
->get (node
)->loop_iterations
,
2894 set_hint_predicate (&inline_summaries
->get (node
)->loop_stride
,
2898 FOR_ALL_BB_FN (bb
, my_function
)
2904 edge_predicate_pool
.remove ((predicate
*)bb
->aux
);
2906 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
2909 edge_predicate_pool
.remove ((predicate
*) e
->aux
);
2913 inline_summaries
->get (node
)->self_time
= time
;
2914 inline_summaries
->get (node
)->self_size
= size
;
2915 nonconstant_names
.release ();
2916 ipa_release_body_info (&fbi
);
2917 if (opt_for_fn (node
->decl
, optimize
))
2920 loop_optimizer_finalize ();
2921 else if (!ipa_edge_args_vector
)
2922 ipa_free_all_node_params ();
2923 free_dominance_info (CDI_DOMINATORS
);
2927 fprintf (dump_file
, "\n");
2928 dump_inline_summary (dump_file
, node
);
2933 /* Compute parameters of functions used by inliner.
2934 EARLY is true when we compute parameters for the early inliner */
2937 compute_inline_parameters (struct cgraph_node
*node
, bool early
)
2939 HOST_WIDE_INT self_stack_size
;
2940 struct cgraph_edge
*e
;
2941 struct inline_summary
*info
;
2943 gcc_assert (!node
->global
.inlined_to
);
2945 inline_summary_alloc ();
2947 info
= inline_summaries
->get (node
);
2948 reset_inline_summary (node
, info
);
2950 /* Estimate the stack size for the function if we're optimizing. */
2951 self_stack_size
= optimize
&& !node
->thunk
.thunk_p
2952 ? estimated_stack_frame_size (node
) : 0;
2953 info
->estimated_self_stack_size
= self_stack_size
;
2954 info
->estimated_stack_size
= self_stack_size
;
2955 info
->stack_frame_offset
= 0;
2957 if (node
->thunk
.thunk_p
)
2959 struct inline_edge_summary
*es
= inline_edge_summary (node
->callees
);
2960 struct predicate t
= true_predicate ();
2962 node
->local
.can_change_signature
= false;
2963 es
->call_stmt_size
= eni_size_weights
.call_cost
;
2964 es
->call_stmt_time
= eni_time_weights
.call_cost
;
2965 account_size_time (info
, INLINE_SIZE_SCALE
* 2,
2966 INLINE_TIME_SCALE
* 2, &t
);
2967 t
= not_inlined_predicate ();
2968 account_size_time (info
, 2 * INLINE_SIZE_SCALE
, 0, &t
);
2969 inline_update_overall_summary (node
);
2970 info
->self_size
= info
->size
;
2971 info
->self_time
= info
->time
;
2972 /* We can not inline instrumetnation clones. */
2973 if (node
->thunk
.add_pointer_bounds_args
)
2975 info
->inlinable
= false;
2976 node
->callees
->inline_failed
= CIF_CHKP
;
2979 info
->inlinable
= true;
2983 /* Even is_gimple_min_invariant rely on current_function_decl. */
2984 push_cfun (DECL_STRUCT_FUNCTION (node
->decl
));
2986 /* Can this function be inlined at all? */
2987 if (!opt_for_fn (node
->decl
, optimize
)
2988 && !lookup_attribute ("always_inline",
2989 DECL_ATTRIBUTES (node
->decl
)))
2990 info
->inlinable
= false;
2992 info
->inlinable
= tree_inlinable_function_p (node
->decl
);
2994 info
->contains_cilk_spawn
= fn_contains_cilk_spawn_p (cfun
);
2996 /* Type attributes can use parameter indices to describe them. */
2997 if (TYPE_ATTRIBUTES (TREE_TYPE (node
->decl
)))
2998 node
->local
.can_change_signature
= false;
3001 /* Otherwise, inlinable functions always can change signature. */
3002 if (info
->inlinable
)
3003 node
->local
.can_change_signature
= true;
3006 /* Functions calling builtin_apply can not change signature. */
3007 for (e
= node
->callees
; e
; e
= e
->next_callee
)
3009 tree
cdecl = e
->callee
->decl
;
3010 if (DECL_BUILT_IN (cdecl)
3011 && DECL_BUILT_IN_CLASS (cdecl) == BUILT_IN_NORMAL
3012 && (DECL_FUNCTION_CODE (cdecl) == BUILT_IN_APPLY_ARGS
3013 || DECL_FUNCTION_CODE (cdecl) == BUILT_IN_VA_START
))
3016 node
->local
.can_change_signature
= !e
;
3019 estimate_function_body_sizes (node
, early
);
3022 for (e
= node
->callees
; e
; e
= e
->next_callee
)
3023 if (e
->callee
->comdat_local_p ())
3025 node
->calls_comdat_local
= (e
!= NULL
);
3027 /* Inlining characteristics are maintained by the cgraph_mark_inline. */
3028 info
->time
= info
->self_time
;
3029 info
->size
= info
->self_size
;
3030 info
->stack_frame_offset
= 0;
3031 info
->estimated_stack_size
= info
->estimated_self_stack_size
;
3034 inline_update_overall_summary (node
);
3035 gcc_assert (info
->time
== info
->self_time
3036 && info
->size
== info
->self_size
);
3041 /* Compute parameters of functions used by inliner using
3042 current_function_decl. */
3045 compute_inline_parameters_for_current (void)
3047 compute_inline_parameters (cgraph_node::get (current_function_decl
), true);
3053 const pass_data pass_data_inline_parameters
=
3055 GIMPLE_PASS
, /* type */
3056 "inline_param", /* name */
3057 OPTGROUP_INLINE
, /* optinfo_flags */
3058 TV_INLINE_PARAMETERS
, /* tv_id */
3059 0, /* properties_required */
3060 0, /* properties_provided */
3061 0, /* properties_destroyed */
3062 0, /* todo_flags_start */
3063 0, /* todo_flags_finish */
3066 class pass_inline_parameters
: public gimple_opt_pass
3069 pass_inline_parameters (gcc::context
*ctxt
)
3070 : gimple_opt_pass (pass_data_inline_parameters
, ctxt
)
3073 /* opt_pass methods: */
3074 opt_pass
* clone () { return new pass_inline_parameters (m_ctxt
); }
3075 virtual unsigned int execute (function
*)
3077 return compute_inline_parameters_for_current ();
3080 }; // class pass_inline_parameters
3085 make_pass_inline_parameters (gcc::context
*ctxt
)
3087 return new pass_inline_parameters (ctxt
);
3091 /* Estimate benefit devirtualizing indirect edge IE, provided KNOWN_VALS,
3092 KNOWN_CONTEXTS and KNOWN_AGGS. */
3095 estimate_edge_devirt_benefit (struct cgraph_edge
*ie
,
3096 int *size
, int *time
,
3097 vec
<tree
> known_vals
,
3098 vec
<ipa_polymorphic_call_context
> known_contexts
,
3099 vec
<ipa_agg_jump_function_p
> known_aggs
)
3102 struct cgraph_node
*callee
;
3103 struct inline_summary
*isummary
;
3104 enum availability avail
;
3107 if (!known_vals
.exists () && !known_contexts
.exists ())
3109 if (!opt_for_fn (ie
->caller
->decl
, flag_indirect_inlining
))
3112 target
= ipa_get_indirect_edge_target (ie
, known_vals
, known_contexts
,
3113 known_aggs
, &speculative
);
3114 if (!target
|| speculative
)
3117 /* Account for difference in cost between indirect and direct calls. */
3118 *size
-= (eni_size_weights
.indirect_call_cost
- eni_size_weights
.call_cost
);
3119 *time
-= (eni_time_weights
.indirect_call_cost
- eni_time_weights
.call_cost
);
3120 gcc_checking_assert (*time
>= 0);
3121 gcc_checking_assert (*size
>= 0);
3123 callee
= cgraph_node::get (target
);
3124 if (!callee
|| !callee
->definition
)
3126 callee
= callee
->function_symbol (&avail
);
3127 if (avail
< AVAIL_AVAILABLE
)
3129 isummary
= inline_summaries
->get (callee
);
3130 return isummary
->inlinable
;
3133 /* Increase SIZE, MIN_SIZE (if non-NULL) and TIME for size and time needed to
3134 handle edge E with probability PROB.
3135 Set HINTS if edge may be devirtualized.
3136 KNOWN_VALS, KNOWN_AGGS and KNOWN_CONTEXTS describe context of the call
3140 estimate_edge_size_and_time (struct cgraph_edge
*e
, int *size
, int *min_size
,
3143 vec
<tree
> known_vals
,
3144 vec
<ipa_polymorphic_call_context
> known_contexts
,
3145 vec
<ipa_agg_jump_function_p
> known_aggs
,
3146 inline_hints
*hints
)
3148 struct inline_edge_summary
*es
= inline_edge_summary (e
);
3149 int call_size
= es
->call_stmt_size
;
3150 int call_time
= es
->call_stmt_time
;
3153 && estimate_edge_devirt_benefit (e
, &call_size
, &call_time
,
3154 known_vals
, known_contexts
, known_aggs
)
3155 && hints
&& e
->maybe_hot_p ())
3156 *hints
|= INLINE_HINT_indirect_call
;
3157 cur_size
= call_size
* INLINE_SIZE_SCALE
;
3160 *min_size
+= cur_size
;
3161 *time
+= apply_probability ((gcov_type
) call_time
, prob
)
3162 * e
->frequency
* (INLINE_TIME_SCALE
/ CGRAPH_FREQ_BASE
);
3163 if (*time
> MAX_TIME
* INLINE_TIME_SCALE
)
3164 *time
= MAX_TIME
* INLINE_TIME_SCALE
;
3169 /* Increase SIZE, MIN_SIZE and TIME for size and time needed to handle all
3170 calls in NODE. POSSIBLE_TRUTHS, KNOWN_VALS, KNOWN_AGGS and KNOWN_CONTEXTS
3171 describe context of the call site. */
3174 estimate_calls_size_and_time (struct cgraph_node
*node
, int *size
,
3175 int *min_size
, int *time
,
3176 inline_hints
*hints
,
3177 clause_t possible_truths
,
3178 vec
<tree
> known_vals
,
3179 vec
<ipa_polymorphic_call_context
> known_contexts
,
3180 vec
<ipa_agg_jump_function_p
> known_aggs
)
3182 struct cgraph_edge
*e
;
3183 for (e
= node
->callees
; e
; e
= e
->next_callee
)
3185 if (inline_edge_summary_vec
.length () <= (unsigned) e
->uid
)
3188 struct inline_edge_summary
*es
= inline_edge_summary (e
);
3190 /* Do not care about zero sized builtins. */
3191 if (e
->inline_failed
&& !es
->call_stmt_size
)
3193 gcc_checking_assert (!es
->call_stmt_time
);
3197 || evaluate_predicate (es
->predicate
, possible_truths
))
3199 if (e
->inline_failed
)
3201 /* Predicates of calls shall not use NOT_CHANGED codes,
3202 sowe do not need to compute probabilities. */
3203 estimate_edge_size_and_time (e
, size
,
3204 es
->predicate
? NULL
: min_size
,
3205 time
, REG_BR_PROB_BASE
,
3206 known_vals
, known_contexts
,
3210 estimate_calls_size_and_time (e
->callee
, size
, min_size
, time
,
3213 known_vals
, known_contexts
,
3217 for (e
= node
->indirect_calls
; e
; e
= e
->next_callee
)
3219 if (inline_edge_summary_vec
.length () <= (unsigned) e
->uid
)
3222 struct inline_edge_summary
*es
= inline_edge_summary (e
);
3224 || evaluate_predicate (es
->predicate
, possible_truths
))
3225 estimate_edge_size_and_time (e
, size
,
3226 es
->predicate
? NULL
: min_size
,
3227 time
, REG_BR_PROB_BASE
,
3228 known_vals
, known_contexts
, known_aggs
,
3234 /* Estimate size and time needed to execute NODE assuming
3235 POSSIBLE_TRUTHS clause, and KNOWN_VALS, KNOWN_AGGS and KNOWN_CONTEXTS
3236 information about NODE's arguments. If non-NULL use also probability
3237 information present in INLINE_PARAM_SUMMARY vector.
3238 Additionally detemine hints determined by the context. Finally compute
3239 minimal size needed for the call that is independent on the call context and
3240 can be used for fast estimates. Return the values in RET_SIZE,
3241 RET_MIN_SIZE, RET_TIME and RET_HINTS. */
3244 estimate_node_size_and_time (struct cgraph_node
*node
,
3245 clause_t possible_truths
,
3246 vec
<tree
> known_vals
,
3247 vec
<ipa_polymorphic_call_context
> known_contexts
,
3248 vec
<ipa_agg_jump_function_p
> known_aggs
,
3249 int *ret_size
, int *ret_min_size
, int *ret_time
,
3250 inline_hints
*ret_hints
,
3251 vec
<inline_param_summary
>
3252 inline_param_summary
)
3254 struct inline_summary
*info
= inline_summaries
->get (node
);
3259 inline_hints hints
= 0;
3262 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3265 fprintf (dump_file
, " Estimating body: %s/%i\n"
3266 " Known to be false: ", node
->name (),
3269 for (i
= predicate_not_inlined_condition
;
3270 i
< (predicate_first_dynamic_condition
3271 + (int) vec_safe_length (info
->conds
)); i
++)
3272 if (!(possible_truths
& (1 << i
)))
3275 fprintf (dump_file
, ", ");
3277 dump_condition (dump_file
, info
->conds
, i
);
3281 for (i
= 0; vec_safe_iterate (info
->entry
, i
, &e
); i
++)
3282 if (evaluate_predicate (&e
->predicate
, possible_truths
))
3285 gcc_checking_assert (e
->time
>= 0);
3286 gcc_checking_assert (time
>= 0);
3287 if (!inline_param_summary
.exists ())
3291 int prob
= predicate_probability (info
->conds
,
3294 inline_param_summary
);
3295 gcc_checking_assert (prob
>= 0);
3296 gcc_checking_assert (prob
<= REG_BR_PROB_BASE
);
3297 time
+= apply_probability ((gcov_type
) e
->time
, prob
);
3299 if (time
> MAX_TIME
* INLINE_TIME_SCALE
)
3300 time
= MAX_TIME
* INLINE_TIME_SCALE
;
3301 gcc_checking_assert (time
>= 0);
3304 gcc_checking_assert (true_predicate_p (&(*info
->entry
)[0].predicate
));
3305 min_size
= (*info
->entry
)[0].size
;
3306 gcc_checking_assert (size
>= 0);
3307 gcc_checking_assert (time
>= 0);
3309 if (info
->loop_iterations
3310 && !evaluate_predicate (info
->loop_iterations
, possible_truths
))
3311 hints
|= INLINE_HINT_loop_iterations
;
3312 if (info
->loop_stride
3313 && !evaluate_predicate (info
->loop_stride
, possible_truths
))
3314 hints
|= INLINE_HINT_loop_stride
;
3315 if (info
->array_index
3316 && !evaluate_predicate (info
->array_index
, possible_truths
))
3317 hints
|= INLINE_HINT_array_index
;
3319 hints
|= INLINE_HINT_in_scc
;
3320 if (DECL_DECLARED_INLINE_P (node
->decl
))
3321 hints
|= INLINE_HINT_declared_inline
;
3323 estimate_calls_size_and_time (node
, &size
, &min_size
, &time
, &hints
, possible_truths
,
3324 known_vals
, known_contexts
, known_aggs
);
3325 gcc_checking_assert (size
>= 0);
3326 gcc_checking_assert (time
>= 0);
3327 time
= RDIV (time
, INLINE_TIME_SCALE
);
3328 size
= RDIV (size
, INLINE_SIZE_SCALE
);
3329 min_size
= RDIV (min_size
, INLINE_SIZE_SCALE
);
3331 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3332 fprintf (dump_file
, "\n size:%i time:%i\n", (int) size
, (int) time
);
3338 *ret_min_size
= min_size
;
3345 /* Estimate size and time needed to execute callee of EDGE assuming that
3346 parameters known to be constant at caller of EDGE are propagated.
3347 KNOWN_VALS and KNOWN_CONTEXTS are vectors of assumed known constant values
3348 and types for parameters. */
3351 estimate_ipcp_clone_size_and_time (struct cgraph_node
*node
,
3352 vec
<tree
> known_vals
,
3353 vec
<ipa_polymorphic_call_context
>
3355 vec
<ipa_agg_jump_function_p
> known_aggs
,
3356 int *ret_size
, int *ret_time
,
3357 inline_hints
*hints
)
3361 clause
= evaluate_conditions_for_known_args (node
, false, known_vals
,
3363 estimate_node_size_and_time (node
, clause
, known_vals
, known_contexts
,
3364 known_aggs
, ret_size
, NULL
, ret_time
, hints
, vNULL
);
3367 /* Translate all conditions from callee representation into caller
3368 representation and symbolically evaluate predicate P into new predicate.
3370 INFO is inline_summary of function we are adding predicate into, CALLEE_INFO
3371 is summary of function predicate P is from. OPERAND_MAP is array giving
3372 callee formal IDs the caller formal IDs. POSSSIBLE_TRUTHS is clausule of all
3373 callee conditions that may be true in caller context. TOPLEV_PREDICATE is
3374 predicate under which callee is executed. OFFSET_MAP is an array of of
3375 offsets that need to be added to conditions, negative offset means that
3376 conditions relying on values passed by reference have to be discarded
3377 because they might not be preserved (and should be considered offset zero
3378 for other purposes). */
3380 static struct predicate
3381 remap_predicate (struct inline_summary
*info
,
3382 struct inline_summary
*callee_info
,
3383 struct predicate
*p
,
3384 vec
<int> operand_map
,
3385 vec
<int> offset_map
,
3386 clause_t possible_truths
, struct predicate
*toplev_predicate
)
3389 struct predicate out
= true_predicate ();
3391 /* True predicate is easy. */
3392 if (true_predicate_p (p
))
3393 return *toplev_predicate
;
3394 for (i
= 0; p
->clause
[i
]; i
++)
3396 clause_t clause
= p
->clause
[i
];
3398 struct predicate clause_predicate
= false_predicate ();
3400 gcc_assert (i
< MAX_CLAUSES
);
3402 for (cond
= 0; cond
< NUM_CONDITIONS
; cond
++)
3403 /* Do we have condition we can't disprove? */
3404 if (clause
& possible_truths
& (1 << cond
))
3406 struct predicate cond_predicate
;
3407 /* Work out if the condition can translate to predicate in the
3408 inlined function. */
3409 if (cond
>= predicate_first_dynamic_condition
)
3411 struct condition
*c
;
3413 c
= &(*callee_info
->conds
)[cond
3415 predicate_first_dynamic_condition
];
3416 /* See if we can remap condition operand to caller's operand.
3417 Otherwise give up. */
3418 if (!operand_map
.exists ()
3419 || (int) operand_map
.length () <= c
->operand_num
3420 || operand_map
[c
->operand_num
] == -1
3421 /* TODO: For non-aggregate conditions, adding an offset is
3422 basically an arithmetic jump function processing which
3423 we should support in future. */
3424 || ((!c
->agg_contents
|| !c
->by_ref
)
3425 && offset_map
[c
->operand_num
] > 0)
3426 || (c
->agg_contents
&& c
->by_ref
3427 && offset_map
[c
->operand_num
] < 0))
3428 cond_predicate
= true_predicate ();
3431 struct agg_position_info ap
;
3432 HOST_WIDE_INT offset_delta
= offset_map
[c
->operand_num
];
3433 if (offset_delta
< 0)
3435 gcc_checking_assert (!c
->agg_contents
|| !c
->by_ref
);
3438 gcc_assert (!c
->agg_contents
3439 || c
->by_ref
|| offset_delta
== 0);
3440 ap
.offset
= c
->offset
+ offset_delta
;
3441 ap
.agg_contents
= c
->agg_contents
;
3442 ap
.by_ref
= c
->by_ref
;
3443 cond_predicate
= add_condition (info
,
3444 operand_map
[c
->operand_num
],
3445 c
->size
, &ap
, c
->code
,
3449 /* Fixed conditions remains same, construct single
3450 condition predicate. */
3453 cond_predicate
.clause
[0] = 1 << cond
;
3454 cond_predicate
.clause
[1] = 0;
3456 clause_predicate
= or_predicates (info
->conds
, &clause_predicate
,
3459 out
= and_predicates (info
->conds
, &out
, &clause_predicate
);
3461 return and_predicates (info
->conds
, &out
, toplev_predicate
);
3465 /* Update summary information of inline clones after inlining.
3466 Compute peak stack usage. */
3469 inline_update_callee_summaries (struct cgraph_node
*node
, int depth
)
3471 struct cgraph_edge
*e
;
3472 struct inline_summary
*callee_info
= inline_summaries
->get (node
);
3473 struct inline_summary
*caller_info
= inline_summaries
->get (node
->callers
->caller
);
3476 callee_info
->stack_frame_offset
3477 = caller_info
->stack_frame_offset
3478 + caller_info
->estimated_self_stack_size
;
3479 peak
= callee_info
->stack_frame_offset
3480 + callee_info
->estimated_self_stack_size
;
3481 if (inline_summaries
->get (node
->global
.inlined_to
)->estimated_stack_size
< peak
)
3482 inline_summaries
->get (node
->global
.inlined_to
)->estimated_stack_size
= peak
;
3483 ipa_propagate_frequency (node
);
3484 for (e
= node
->callees
; e
; e
= e
->next_callee
)
3486 if (!e
->inline_failed
)
3487 inline_update_callee_summaries (e
->callee
, depth
);
3488 inline_edge_summary (e
)->loop_depth
+= depth
;
3490 for (e
= node
->indirect_calls
; e
; e
= e
->next_callee
)
3491 inline_edge_summary (e
)->loop_depth
+= depth
;
3494 /* Update change_prob of EDGE after INLINED_EDGE has been inlined.
3495 When functoin A is inlined in B and A calls C with parameter that
3496 changes with probability PROB1 and C is known to be passthroug
3497 of argument if B that change with probability PROB2, the probability
3498 of change is now PROB1*PROB2. */
3501 remap_edge_change_prob (struct cgraph_edge
*inlined_edge
,
3502 struct cgraph_edge
*edge
)
3504 if (ipa_node_params_sum
)
3507 struct ipa_edge_args
*args
= IPA_EDGE_REF (edge
);
3508 struct inline_edge_summary
*es
= inline_edge_summary (edge
);
3509 struct inline_edge_summary
*inlined_es
3510 = inline_edge_summary (inlined_edge
);
3512 for (i
= 0; i
< ipa_get_cs_argument_count (args
); i
++)
3514 struct ipa_jump_func
*jfunc
= ipa_get_ith_jump_func (args
, i
);
3515 if (jfunc
->type
== IPA_JF_PASS_THROUGH
3516 && (ipa_get_jf_pass_through_formal_id (jfunc
)
3517 < (int) inlined_es
->param
.length ()))
3519 int jf_formal_id
= ipa_get_jf_pass_through_formal_id (jfunc
);
3520 int prob1
= es
->param
[i
].change_prob
;
3521 int prob2
= inlined_es
->param
[jf_formal_id
].change_prob
;
3522 int prob
= combine_probabilities (prob1
, prob2
);
3524 if (prob1
&& prob2
&& !prob
)
3527 es
->param
[i
].change_prob
= prob
;
3533 /* Update edge summaries of NODE after INLINED_EDGE has been inlined.
3535 Remap predicates of callees of NODE. Rest of arguments match
3538 Also update change probabilities. */
3541 remap_edge_summaries (struct cgraph_edge
*inlined_edge
,
3542 struct cgraph_node
*node
,
3543 struct inline_summary
*info
,
3544 struct inline_summary
*callee_info
,
3545 vec
<int> operand_map
,
3546 vec
<int> offset_map
,
3547 clause_t possible_truths
,
3548 struct predicate
*toplev_predicate
)
3550 struct cgraph_edge
*e
, *next
;
3551 for (e
= node
->callees
; e
; e
= next
)
3553 struct inline_edge_summary
*es
= inline_edge_summary (e
);
3555 next
= e
->next_callee
;
3557 if (e
->inline_failed
)
3559 remap_edge_change_prob (inlined_edge
, e
);
3563 p
= remap_predicate (info
, callee_info
,
3564 es
->predicate
, operand_map
, offset_map
,
3565 possible_truths
, toplev_predicate
);
3566 edge_set_predicate (e
, &p
);
3569 edge_set_predicate (e
, toplev_predicate
);
3572 remap_edge_summaries (inlined_edge
, e
->callee
, info
, callee_info
,
3573 operand_map
, offset_map
, possible_truths
,
3576 for (e
= node
->indirect_calls
; e
; e
= next
)
3578 struct inline_edge_summary
*es
= inline_edge_summary (e
);
3580 next
= e
->next_callee
;
3582 remap_edge_change_prob (inlined_edge
, e
);
3585 p
= remap_predicate (info
, callee_info
,
3586 es
->predicate
, operand_map
, offset_map
,
3587 possible_truths
, toplev_predicate
);
3588 edge_set_predicate (e
, &p
);
3591 edge_set_predicate (e
, toplev_predicate
);
3595 /* Same as remap_predicate, but set result into hint *HINT. */
3598 remap_hint_predicate (struct inline_summary
*info
,
3599 struct inline_summary
*callee_info
,
3600 struct predicate
**hint
,
3601 vec
<int> operand_map
,
3602 vec
<int> offset_map
,
3603 clause_t possible_truths
,
3604 struct predicate
*toplev_predicate
)
3610 p
= remap_predicate (info
, callee_info
,
3612 operand_map
, offset_map
,
3613 possible_truths
, toplev_predicate
);
3614 if (!false_predicate_p (&p
) && !true_predicate_p (&p
))
3617 set_hint_predicate (hint
, p
);
3619 **hint
= and_predicates (info
->conds
, *hint
, &p
);
3623 /* We inlined EDGE. Update summary of the function we inlined into. */
3626 inline_merge_summary (struct cgraph_edge
*edge
)
3628 struct inline_summary
*callee_info
= inline_summaries
->get (edge
->callee
);
3629 struct cgraph_node
*to
= (edge
->caller
->global
.inlined_to
3630 ? edge
->caller
->global
.inlined_to
: edge
->caller
);
3631 struct inline_summary
*info
= inline_summaries
->get (to
);
3632 clause_t clause
= 0; /* not_inline is known to be false. */
3634 vec
<int> operand_map
= vNULL
;
3635 vec
<int> offset_map
= vNULL
;
3637 struct predicate toplev_predicate
;
3638 struct predicate true_p
= true_predicate ();
3639 struct inline_edge_summary
*es
= inline_edge_summary (edge
);
3642 toplev_predicate
= *es
->predicate
;
3644 toplev_predicate
= true_predicate ();
3646 info
->fp_expressions
|= callee_info
->fp_expressions
;
3648 if (callee_info
->conds
)
3649 evaluate_properties_for_edge (edge
, true, &clause
, NULL
, NULL
, NULL
);
3650 if (ipa_node_params_sum
&& callee_info
->conds
)
3652 struct ipa_edge_args
*args
= IPA_EDGE_REF (edge
);
3653 int count
= ipa_get_cs_argument_count (args
);
3658 operand_map
.safe_grow_cleared (count
);
3659 offset_map
.safe_grow_cleared (count
);
3661 for (i
= 0; i
< count
; i
++)
3663 struct ipa_jump_func
*jfunc
= ipa_get_ith_jump_func (args
, i
);
3666 /* TODO: handle non-NOPs when merging. */
3667 if (jfunc
->type
== IPA_JF_PASS_THROUGH
)
3669 if (ipa_get_jf_pass_through_operation (jfunc
) == NOP_EXPR
)
3670 map
= ipa_get_jf_pass_through_formal_id (jfunc
);
3671 if (!ipa_get_jf_pass_through_agg_preserved (jfunc
))
3674 else if (jfunc
->type
== IPA_JF_ANCESTOR
)
3676 HOST_WIDE_INT offset
= ipa_get_jf_ancestor_offset (jfunc
);
3677 if (offset
>= 0 && offset
< INT_MAX
)
3679 map
= ipa_get_jf_ancestor_formal_id (jfunc
);
3680 if (!ipa_get_jf_ancestor_agg_preserved (jfunc
))
3682 offset_map
[i
] = offset
;
3685 operand_map
[i
] = map
;
3686 gcc_assert (map
< ipa_get_param_count (IPA_NODE_REF (to
)));
3689 for (i
= 0; vec_safe_iterate (callee_info
->entry
, i
, &e
); i
++)
3691 struct predicate p
= remap_predicate (info
, callee_info
,
3692 &e
->predicate
, operand_map
,
3695 if (!false_predicate_p (&p
))
3697 gcov_type add_time
= ((gcov_type
) e
->time
* edge
->frequency
3698 + CGRAPH_FREQ_BASE
/ 2) / CGRAPH_FREQ_BASE
;
3699 int prob
= predicate_probability (callee_info
->conds
,
3702 add_time
= apply_probability ((gcov_type
) add_time
, prob
);
3703 if (add_time
> MAX_TIME
* INLINE_TIME_SCALE
)
3704 add_time
= MAX_TIME
* INLINE_TIME_SCALE
;
3705 if (prob
!= REG_BR_PROB_BASE
3706 && dump_file
&& (dump_flags
& TDF_DETAILS
))
3708 fprintf (dump_file
, "\t\tScaling time by probability:%f\n",
3709 (double) prob
/ REG_BR_PROB_BASE
);
3711 account_size_time (info
, e
->size
, add_time
, &p
);
3714 remap_edge_summaries (edge
, edge
->callee
, info
, callee_info
, operand_map
,
3715 offset_map
, clause
, &toplev_predicate
);
3716 remap_hint_predicate (info
, callee_info
,
3717 &callee_info
->loop_iterations
,
3718 operand_map
, offset_map
, clause
, &toplev_predicate
);
3719 remap_hint_predicate (info
, callee_info
,
3720 &callee_info
->loop_stride
,
3721 operand_map
, offset_map
, clause
, &toplev_predicate
);
3722 remap_hint_predicate (info
, callee_info
,
3723 &callee_info
->array_index
,
3724 operand_map
, offset_map
, clause
, &toplev_predicate
);
3726 inline_update_callee_summaries (edge
->callee
,
3727 inline_edge_summary (edge
)->loop_depth
);
3729 /* We do not maintain predicates of inlined edges, free it. */
3730 edge_set_predicate (edge
, &true_p
);
3731 /* Similarly remove param summaries. */
3732 es
->param
.release ();
3733 operand_map
.release ();
3734 offset_map
.release ();
3737 /* For performance reasons inline_merge_summary is not updating overall size
3738 and time. Recompute it. */
3741 inline_update_overall_summary (struct cgraph_node
*node
)
3743 struct inline_summary
*info
= inline_summaries
->get (node
);
3749 for (i
= 0; vec_safe_iterate (info
->entry
, i
, &e
); i
++)
3751 info
->size
+= e
->size
, info
->time
+= e
->time
;
3752 if (info
->time
> MAX_TIME
* INLINE_TIME_SCALE
)
3753 info
->time
= MAX_TIME
* INLINE_TIME_SCALE
;
3755 estimate_calls_size_and_time (node
, &info
->size
, &info
->min_size
,
3757 ~(clause_t
) (1 << predicate_false_condition
),
3758 vNULL
, vNULL
, vNULL
);
3759 info
->time
= (info
->time
+ INLINE_TIME_SCALE
/ 2) / INLINE_TIME_SCALE
;
3760 info
->size
= (info
->size
+ INLINE_SIZE_SCALE
/ 2) / INLINE_SIZE_SCALE
;
3763 /* Return hints derrived from EDGE. */
3765 simple_edge_hints (struct cgraph_edge
*edge
)
3768 struct cgraph_node
*to
= (edge
->caller
->global
.inlined_to
3769 ? edge
->caller
->global
.inlined_to
: edge
->caller
);
3770 struct cgraph_node
*callee
= edge
->callee
->ultimate_alias_target ();
3771 if (inline_summaries
->get (to
)->scc_no
3772 && inline_summaries
->get (to
)->scc_no
3773 == inline_summaries
->get (callee
)->scc_no
3774 && !edge
->recursive_p ())
3775 hints
|= INLINE_HINT_same_scc
;
3777 if (callee
->lto_file_data
&& edge
->caller
->lto_file_data
3778 && edge
->caller
->lto_file_data
!= callee
->lto_file_data
3779 && !callee
->merged_comdat
&& !callee
->icf_merged
)
3780 hints
|= INLINE_HINT_cross_module
;
3785 /* Estimate the time cost for the caller when inlining EDGE.
3786 Only to be called via estimate_edge_time, that handles the
3789 When caching, also update the cache entry. Compute both time and
3790 size, since we always need both metrics eventually. */
3793 do_estimate_edge_time (struct cgraph_edge
*edge
)
3798 struct cgraph_node
*callee
;
3800 vec
<tree
> known_vals
;
3801 vec
<ipa_polymorphic_call_context
> known_contexts
;
3802 vec
<ipa_agg_jump_function_p
> known_aggs
;
3803 struct inline_edge_summary
*es
= inline_edge_summary (edge
);
3806 callee
= edge
->callee
->ultimate_alias_target ();
3808 gcc_checking_assert (edge
->inline_failed
);
3809 evaluate_properties_for_edge (edge
, true,
3810 &clause
, &known_vals
, &known_contexts
,
3812 estimate_node_size_and_time (callee
, clause
, known_vals
, known_contexts
,
3813 known_aggs
, &size
, &min_size
, &time
, &hints
, es
->param
);
3815 /* When we have profile feedback, we can quite safely identify hot
3816 edges and for those we disable size limits. Don't do that when
3817 probability that caller will call the callee is low however, since it
3818 may hurt optimization of the caller's hot path. */
3819 if (edge
->count
&& edge
->maybe_hot_p ()
3821 > (edge
->caller
->global
.inlined_to
3822 ? edge
->caller
->global
.inlined_to
->count
: edge
->caller
->count
)))
3823 hints
|= INLINE_HINT_known_hot
;
3825 known_vals
.release ();
3826 known_contexts
.release ();
3827 known_aggs
.release ();
3828 gcc_checking_assert (size
>= 0);
3829 gcc_checking_assert (time
>= 0);
3831 /* When caching, update the cache entry. */
3832 if (edge_growth_cache
.exists ())
3834 inline_summaries
->get (edge
->callee
)->min_size
= min_size
;
3835 if ((int) edge_growth_cache
.length () <= edge
->uid
)
3836 edge_growth_cache
.safe_grow_cleared (symtab
->edges_max_uid
);
3837 edge_growth_cache
[edge
->uid
].time
= time
+ (time
>= 0);
3839 edge_growth_cache
[edge
->uid
].size
= size
+ (size
>= 0);
3840 hints
|= simple_edge_hints (edge
);
3841 edge_growth_cache
[edge
->uid
].hints
= hints
+ 1;
3847 /* Return estimated callee growth after inlining EDGE.
3848 Only to be called via estimate_edge_size. */
3851 do_estimate_edge_size (struct cgraph_edge
*edge
)
3854 struct cgraph_node
*callee
;
3856 vec
<tree
> known_vals
;
3857 vec
<ipa_polymorphic_call_context
> known_contexts
;
3858 vec
<ipa_agg_jump_function_p
> known_aggs
;
3860 /* When we do caching, use do_estimate_edge_time to populate the entry. */
3862 if (edge_growth_cache
.exists ())
3864 do_estimate_edge_time (edge
);
3865 size
= edge_growth_cache
[edge
->uid
].size
;
3866 gcc_checking_assert (size
);
3867 return size
- (size
> 0);
3870 callee
= edge
->callee
->ultimate_alias_target ();
3872 /* Early inliner runs without caching, go ahead and do the dirty work. */
3873 gcc_checking_assert (edge
->inline_failed
);
3874 evaluate_properties_for_edge (edge
, true,
3875 &clause
, &known_vals
, &known_contexts
,
3877 estimate_node_size_and_time (callee
, clause
, known_vals
, known_contexts
,
3878 known_aggs
, &size
, NULL
, NULL
, NULL
, vNULL
);
3879 known_vals
.release ();
3880 known_contexts
.release ();
3881 known_aggs
.release ();
3886 /* Estimate the growth of the caller when inlining EDGE.
3887 Only to be called via estimate_edge_size. */
3890 do_estimate_edge_hints (struct cgraph_edge
*edge
)
3893 struct cgraph_node
*callee
;
3895 vec
<tree
> known_vals
;
3896 vec
<ipa_polymorphic_call_context
> known_contexts
;
3897 vec
<ipa_agg_jump_function_p
> known_aggs
;
3899 /* When we do caching, use do_estimate_edge_time to populate the entry. */
3901 if (edge_growth_cache
.exists ())
3903 do_estimate_edge_time (edge
);
3904 hints
= edge_growth_cache
[edge
->uid
].hints
;
3905 gcc_checking_assert (hints
);
3909 callee
= edge
->callee
->ultimate_alias_target ();
3911 /* Early inliner runs without caching, go ahead and do the dirty work. */
3912 gcc_checking_assert (edge
->inline_failed
);
3913 evaluate_properties_for_edge (edge
, true,
3914 &clause
, &known_vals
, &known_contexts
,
3916 estimate_node_size_and_time (callee
, clause
, known_vals
, known_contexts
,
3917 known_aggs
, NULL
, NULL
, NULL
, &hints
, vNULL
);
3918 known_vals
.release ();
3919 known_contexts
.release ();
3920 known_aggs
.release ();
3921 hints
|= simple_edge_hints (edge
);
3926 /* Estimate self time of the function NODE after inlining EDGE. */
3929 estimate_time_after_inlining (struct cgraph_node
*node
,
3930 struct cgraph_edge
*edge
)
3932 struct inline_edge_summary
*es
= inline_edge_summary (edge
);
3933 if (!es
->predicate
|| !false_predicate_p (es
->predicate
))
3936 inline_summaries
->get (node
)->time
+ estimate_edge_time (edge
);
3939 if (time
> MAX_TIME
)
3943 return inline_summaries
->get (node
)->time
;
3947 /* Estimate the size of NODE after inlining EDGE which should be an
3948 edge to either NODE or a call inlined into NODE. */
3951 estimate_size_after_inlining (struct cgraph_node
*node
,
3952 struct cgraph_edge
*edge
)
3954 struct inline_edge_summary
*es
= inline_edge_summary (edge
);
3955 if (!es
->predicate
|| !false_predicate_p (es
->predicate
))
3957 int size
= inline_summaries
->get (node
)->size
+ estimate_edge_growth (edge
);
3958 gcc_assert (size
>= 0);
3961 return inline_summaries
->get (node
)->size
;
3967 struct cgraph_node
*node
;
3968 bool self_recursive
;
3974 /* Worker for do_estimate_growth. Collect growth for all callers. */
3977 do_estimate_growth_1 (struct cgraph_node
*node
, void *data
)
3979 struct cgraph_edge
*e
;
3980 struct growth_data
*d
= (struct growth_data
*) data
;
3982 for (e
= node
->callers
; e
; e
= e
->next_caller
)
3984 gcc_checking_assert (e
->inline_failed
);
3986 if (cgraph_inline_failed_type (e
->inline_failed
) == CIF_FINAL_ERROR
)
3988 d
->uninlinable
= true;
3992 if (e
->recursive_p ())
3994 d
->self_recursive
= true;
3997 d
->growth
+= estimate_edge_growth (e
);
4003 /* Estimate the growth caused by inlining NODE into all callees. */
4006 estimate_growth (struct cgraph_node
*node
)
4008 struct growth_data d
= { node
, false, false, 0 };
4009 struct inline_summary
*info
= inline_summaries
->get (node
);
4011 node
->call_for_symbol_and_aliases (do_estimate_growth_1
, &d
, true);
4013 /* For self recursive functions the growth estimation really should be
4014 infinity. We don't want to return very large values because the growth
4015 plays various roles in badness computation fractions. Be sure to not
4016 return zero or negative growths. */
4017 if (d
.self_recursive
)
4018 d
.growth
= d
.growth
< info
->size
? info
->size
: d
.growth
;
4019 else if (DECL_EXTERNAL (node
->decl
) || d
.uninlinable
)
4023 if (node
->will_be_removed_from_program_if_no_direct_calls_p ())
4024 d
.growth
-= info
->size
;
4025 /* COMDAT functions are very often not shared across multiple units
4026 since they come from various template instantiations.
4027 Take this into account. */
4028 else if (DECL_COMDAT (node
->decl
)
4029 && node
->can_remove_if_no_direct_calls_p ())
4030 d
.growth
-= (info
->size
4031 * (100 - PARAM_VALUE (PARAM_COMDAT_SHARING_PROBABILITY
))
4038 /* Verify if there are fewer than MAX_CALLERS. */
4041 check_callers (cgraph_node
*node
, int *max_callers
)
4045 if (!node
->can_remove_if_no_direct_calls_and_refs_p ())
4048 for (cgraph_edge
*e
= node
->callers
; e
; e
= e
->next_caller
)
4052 || cgraph_inline_failed_type (e
->inline_failed
) == CIF_FINAL_ERROR
)
4056 FOR_EACH_ALIAS (node
, ref
)
4057 if (check_callers (dyn_cast
<cgraph_node
*> (ref
->referring
), max_callers
))
4064 /* Make cheap estimation if growth of NODE is likely positive knowing
4065 EDGE_GROWTH of one particular edge.
4066 We assume that most of other edges will have similar growth
4067 and skip computation if there are too many callers. */
4070 growth_likely_positive (struct cgraph_node
*node
,
4074 struct cgraph_edge
*e
;
4075 gcc_checking_assert (edge_growth
> 0);
4077 /* First quickly check if NODE is removable at all. */
4078 if (DECL_EXTERNAL (node
->decl
))
4080 if (!node
->can_remove_if_no_direct_calls_and_refs_p ()
4081 || node
->address_taken
)
4084 max_callers
= inline_summaries
->get (node
)->size
* 4 / edge_growth
+ 2;
4086 for (e
= node
->callers
; e
; e
= e
->next_caller
)
4090 || cgraph_inline_failed_type (e
->inline_failed
) == CIF_FINAL_ERROR
)
4095 FOR_EACH_ALIAS (node
, ref
)
4096 if (check_callers (dyn_cast
<cgraph_node
*> (ref
->referring
), &max_callers
))
4099 /* Unlike for functions called once, we play unsafe with
4100 COMDATs. We can allow that since we know functions
4101 in consideration are small (and thus risk is small) and
4102 moreover grow estimates already accounts that COMDAT
4103 functions may or may not disappear when eliminated from
4104 current unit. With good probability making aggressive
4105 choice in all units is going to make overall program
4107 if (DECL_COMDAT (node
->decl
))
4109 if (!node
->can_remove_if_no_direct_calls_p ())
4112 else if (!node
->will_be_removed_from_program_if_no_direct_calls_p ())
4115 return estimate_growth (node
) > 0;
4119 /* This function performs intraprocedural analysis in NODE that is required to
4120 inline indirect calls. */
4123 inline_indirect_intraprocedural_analysis (struct cgraph_node
*node
)
4125 ipa_analyze_node (node
);
4126 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
4128 ipa_print_node_params (dump_file
, node
);
4129 ipa_print_node_jump_functions (dump_file
, node
);
4134 /* Note function body size. */
4137 inline_analyze_function (struct cgraph_node
*node
)
4139 push_cfun (DECL_STRUCT_FUNCTION (node
->decl
));
4142 fprintf (dump_file
, "\nAnalyzing function: %s/%u\n",
4143 node
->name (), node
->order
);
4144 if (opt_for_fn (node
->decl
, optimize
) && !node
->thunk
.thunk_p
)
4145 inline_indirect_intraprocedural_analysis (node
);
4146 compute_inline_parameters (node
, false);
4149 struct cgraph_edge
*e
;
4150 for (e
= node
->callees
; e
; e
= e
->next_callee
)
4151 e
->inline_failed
= CIF_FUNCTION_NOT_OPTIMIZED
;
4152 for (e
= node
->indirect_calls
; e
; e
= e
->next_callee
)
4153 e
->inline_failed
= CIF_FUNCTION_NOT_OPTIMIZED
;
4160 /* Called when new function is inserted to callgraph late. */
4163 inline_summary_t::insert (struct cgraph_node
*node
, inline_summary
*)
4165 inline_analyze_function (node
);
4168 /* Note function body size. */
4171 inline_generate_summary (void)
4173 struct cgraph_node
*node
;
4175 FOR_EACH_DEFINED_FUNCTION (node
)
4176 if (DECL_STRUCT_FUNCTION (node
->decl
))
4177 node
->local
.versionable
= tree_versionable_function_p (node
->decl
);
4179 /* When not optimizing, do not bother to analyze. Inlining is still done
4180 because edge redirection needs to happen there. */
4181 if (!optimize
&& !flag_generate_lto
&& !flag_generate_offload
&& !flag_wpa
)
4184 if (!inline_summaries
)
4185 inline_summaries
= (inline_summary_t
*) inline_summary_t::create_ggc (symtab
);
4187 inline_summaries
->enable_insertion_hook ();
4189 ipa_register_cgraph_hooks ();
4190 inline_free_summary ();
4192 FOR_EACH_DEFINED_FUNCTION (node
)
4194 inline_analyze_function (node
);
4198 /* Read predicate from IB. */
4200 static struct predicate
4201 read_predicate (struct lto_input_block
*ib
)
4203 struct predicate out
;
4209 gcc_assert (k
<= MAX_CLAUSES
);
4210 clause
= out
.clause
[k
++] = streamer_read_uhwi (ib
);
4214 /* Zero-initialize the remaining clauses in OUT. */
4215 while (k
<= MAX_CLAUSES
)
4216 out
.clause
[k
++] = 0;
4222 /* Write inline summary for edge E to OB. */
4225 read_inline_edge_summary (struct lto_input_block
*ib
, struct cgraph_edge
*e
)
4227 struct inline_edge_summary
*es
= inline_edge_summary (e
);
4231 es
->call_stmt_size
= streamer_read_uhwi (ib
);
4232 es
->call_stmt_time
= streamer_read_uhwi (ib
);
4233 es
->loop_depth
= streamer_read_uhwi (ib
);
4234 p
= read_predicate (ib
);
4235 edge_set_predicate (e
, &p
);
4236 length
= streamer_read_uhwi (ib
);
4239 es
->param
.safe_grow_cleared (length
);
4240 for (i
= 0; i
< length
; i
++)
4241 es
->param
[i
].change_prob
= streamer_read_uhwi (ib
);
4246 /* Stream in inline summaries from the section. */
4249 inline_read_section (struct lto_file_decl_data
*file_data
, const char *data
,
4252 const struct lto_function_header
*header
=
4253 (const struct lto_function_header
*) data
;
4254 const int cfg_offset
= sizeof (struct lto_function_header
);
4255 const int main_offset
= cfg_offset
+ header
->cfg_size
;
4256 const int string_offset
= main_offset
+ header
->main_size
;
4257 struct data_in
*data_in
;
4258 unsigned int i
, count2
, j
;
4259 unsigned int f_count
;
4261 lto_input_block
ib ((const char *) data
+ main_offset
, header
->main_size
,
4262 file_data
->mode_table
);
4265 lto_data_in_create (file_data
, (const char *) data
+ string_offset
,
4266 header
->string_size
, vNULL
);
4267 f_count
= streamer_read_uhwi (&ib
);
4268 for (i
= 0; i
< f_count
; i
++)
4271 struct cgraph_node
*node
;
4272 struct inline_summary
*info
;
4273 lto_symtab_encoder_t encoder
;
4274 struct bitpack_d bp
;
4275 struct cgraph_edge
*e
;
4278 index
= streamer_read_uhwi (&ib
);
4279 encoder
= file_data
->symtab_node_encoder
;
4280 node
= dyn_cast
<cgraph_node
*> (lto_symtab_encoder_deref (encoder
,
4282 info
= inline_summaries
->get (node
);
4284 info
->estimated_stack_size
4285 = info
->estimated_self_stack_size
= streamer_read_uhwi (&ib
);
4286 info
->size
= info
->self_size
= streamer_read_uhwi (&ib
);
4287 info
->time
= info
->self_time
= streamer_read_uhwi (&ib
);
4289 bp
= streamer_read_bitpack (&ib
);
4290 info
->inlinable
= bp_unpack_value (&bp
, 1);
4291 info
->contains_cilk_spawn
= bp_unpack_value (&bp
, 1);
4292 info
->fp_expressions
= bp_unpack_value (&bp
, 1);
4294 count2
= streamer_read_uhwi (&ib
);
4295 gcc_assert (!info
->conds
);
4296 for (j
= 0; j
< count2
; j
++)
4299 c
.operand_num
= streamer_read_uhwi (&ib
);
4300 c
.size
= streamer_read_uhwi (&ib
);
4301 c
.code
= (enum tree_code
) streamer_read_uhwi (&ib
);
4302 c
.val
= stream_read_tree (&ib
, data_in
);
4303 bp
= streamer_read_bitpack (&ib
);
4304 c
.agg_contents
= bp_unpack_value (&bp
, 1);
4305 c
.by_ref
= bp_unpack_value (&bp
, 1);
4307 c
.offset
= streamer_read_uhwi (&ib
);
4308 vec_safe_push (info
->conds
, c
);
4310 count2
= streamer_read_uhwi (&ib
);
4311 gcc_assert (!info
->entry
);
4312 for (j
= 0; j
< count2
; j
++)
4314 struct size_time_entry e
;
4316 e
.size
= streamer_read_uhwi (&ib
);
4317 e
.time
= streamer_read_uhwi (&ib
);
4318 e
.predicate
= read_predicate (&ib
);
4320 vec_safe_push (info
->entry
, e
);
4323 p
= read_predicate (&ib
);
4324 set_hint_predicate (&info
->loop_iterations
, p
);
4325 p
= read_predicate (&ib
);
4326 set_hint_predicate (&info
->loop_stride
, p
);
4327 p
= read_predicate (&ib
);
4328 set_hint_predicate (&info
->array_index
, p
);
4329 for (e
= node
->callees
; e
; e
= e
->next_callee
)
4330 read_inline_edge_summary (&ib
, e
);
4331 for (e
= node
->indirect_calls
; e
; e
= e
->next_callee
)
4332 read_inline_edge_summary (&ib
, e
);
4335 lto_free_section_data (file_data
, LTO_section_inline_summary
, NULL
, data
,
4337 lto_data_in_delete (data_in
);
4341 /* Read inline summary. Jump functions are shared among ipa-cp
4342 and inliner, so when ipa-cp is active, we don't need to write them
4346 inline_read_summary (void)
4348 struct lto_file_decl_data
**file_data_vec
= lto_get_file_decl_data ();
4349 struct lto_file_decl_data
*file_data
;
4352 inline_summary_alloc ();
4354 while ((file_data
= file_data_vec
[j
++]))
4357 const char *data
= lto_get_section_data (file_data
,
4358 LTO_section_inline_summary
,
4361 inline_read_section (file_data
, data
, len
);
4363 /* Fatal error here. We do not want to support compiling ltrans units
4364 with different version of compiler or different flags than the WPA
4365 unit, so this should never happen. */
4366 fatal_error (input_location
,
4367 "ipa inline summary is missing in input file");
4371 ipa_register_cgraph_hooks ();
4373 ipa_prop_read_jump_functions ();
4376 gcc_assert (inline_summaries
);
4377 inline_summaries
->enable_insertion_hook ();
4381 /* Write predicate P to OB. */
4384 write_predicate (struct output_block
*ob
, struct predicate
*p
)
4388 for (j
= 0; p
->clause
[j
]; j
++)
4390 gcc_assert (j
< MAX_CLAUSES
);
4391 streamer_write_uhwi (ob
, p
->clause
[j
]);
4393 streamer_write_uhwi (ob
, 0);
4397 /* Write inline summary for edge E to OB. */
4400 write_inline_edge_summary (struct output_block
*ob
, struct cgraph_edge
*e
)
4402 struct inline_edge_summary
*es
= inline_edge_summary (e
);
4405 streamer_write_uhwi (ob
, es
->call_stmt_size
);
4406 streamer_write_uhwi (ob
, es
->call_stmt_time
);
4407 streamer_write_uhwi (ob
, es
->loop_depth
);
4408 write_predicate (ob
, es
->predicate
);
4409 streamer_write_uhwi (ob
, es
->param
.length ());
4410 for (i
= 0; i
< (int) es
->param
.length (); i
++)
4411 streamer_write_uhwi (ob
, es
->param
[i
].change_prob
);
4415 /* Write inline summary for node in SET.
4416 Jump functions are shared among ipa-cp and inliner, so when ipa-cp is
4417 active, we don't need to write them twice. */
4420 inline_write_summary (void)
4422 struct cgraph_node
*node
;
4423 struct output_block
*ob
= create_output_block (LTO_section_inline_summary
);
4424 lto_symtab_encoder_t encoder
= ob
->decl_state
->symtab_node_encoder
;
4425 unsigned int count
= 0;
4428 for (i
= 0; i
< lto_symtab_encoder_size (encoder
); i
++)
4430 symtab_node
*snode
= lto_symtab_encoder_deref (encoder
, i
);
4431 cgraph_node
*cnode
= dyn_cast
<cgraph_node
*> (snode
);
4432 if (cnode
&& cnode
->definition
&& !cnode
->alias
)
4435 streamer_write_uhwi (ob
, count
);
4437 for (i
= 0; i
< lto_symtab_encoder_size (encoder
); i
++)
4439 symtab_node
*snode
= lto_symtab_encoder_deref (encoder
, i
);
4440 cgraph_node
*cnode
= dyn_cast
<cgraph_node
*> (snode
);
4441 if (cnode
&& (node
= cnode
)->definition
&& !node
->alias
)
4443 struct inline_summary
*info
= inline_summaries
->get (node
);
4444 struct bitpack_d bp
;
4445 struct cgraph_edge
*edge
;
4448 struct condition
*c
;
4450 streamer_write_uhwi (ob
,
4451 lto_symtab_encoder_encode (encoder
,
4454 streamer_write_hwi (ob
, info
->estimated_self_stack_size
);
4455 streamer_write_hwi (ob
, info
->self_size
);
4456 streamer_write_hwi (ob
, info
->self_time
);
4457 bp
= bitpack_create (ob
->main_stream
);
4458 bp_pack_value (&bp
, info
->inlinable
, 1);
4459 bp_pack_value (&bp
, info
->contains_cilk_spawn
, 1);
4460 bp_pack_value (&bp
, info
->fp_expressions
, 1);
4461 streamer_write_bitpack (&bp
);
4462 streamer_write_uhwi (ob
, vec_safe_length (info
->conds
));
4463 for (i
= 0; vec_safe_iterate (info
->conds
, i
, &c
); i
++)
4465 streamer_write_uhwi (ob
, c
->operand_num
);
4466 streamer_write_uhwi (ob
, c
->size
);
4467 streamer_write_uhwi (ob
, c
->code
);
4468 stream_write_tree (ob
, c
->val
, true);
4469 bp
= bitpack_create (ob
->main_stream
);
4470 bp_pack_value (&bp
, c
->agg_contents
, 1);
4471 bp_pack_value (&bp
, c
->by_ref
, 1);
4472 streamer_write_bitpack (&bp
);
4473 if (c
->agg_contents
)
4474 streamer_write_uhwi (ob
, c
->offset
);
4476 streamer_write_uhwi (ob
, vec_safe_length (info
->entry
));
4477 for (i
= 0; vec_safe_iterate (info
->entry
, i
, &e
); i
++)
4479 streamer_write_uhwi (ob
, e
->size
);
4480 streamer_write_uhwi (ob
, e
->time
);
4481 write_predicate (ob
, &e
->predicate
);
4483 write_predicate (ob
, info
->loop_iterations
);
4484 write_predicate (ob
, info
->loop_stride
);
4485 write_predicate (ob
, info
->array_index
);
4486 for (edge
= node
->callees
; edge
; edge
= edge
->next_callee
)
4487 write_inline_edge_summary (ob
, edge
);
4488 for (edge
= node
->indirect_calls
; edge
; edge
= edge
->next_callee
)
4489 write_inline_edge_summary (ob
, edge
);
4492 streamer_write_char_stream (ob
->main_stream
, 0);
4493 produce_asm (ob
, NULL
);
4494 destroy_output_block (ob
);
4496 if (optimize
&& !flag_ipa_cp
)
4497 ipa_prop_write_jump_functions ();
4501 /* Release inline summary. */
4504 inline_free_summary (void)
4506 struct cgraph_node
*node
;
4507 if (edge_removal_hook_holder
)
4508 symtab
->remove_edge_removal_hook (edge_removal_hook_holder
);
4509 edge_removal_hook_holder
= NULL
;
4510 if (edge_duplication_hook_holder
)
4511 symtab
->remove_edge_duplication_hook (edge_duplication_hook_holder
);
4512 edge_duplication_hook_holder
= NULL
;
4513 if (!inline_edge_summary_vec
.exists ())
4515 FOR_EACH_DEFINED_FUNCTION (node
)
4517 reset_inline_summary (node
, inline_summaries
->get (node
));
4518 inline_summaries
->release ();
4519 inline_summaries
= NULL
;
4520 inline_edge_summary_vec
.release ();
4521 edge_predicate_pool
.release ();