1 /* Inlining decision heuristics.
2 Copyright (C) 2003-2015 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 "hard-reg-set.h"
76 #include "fold-const.h"
77 #include "stor-layout.h"
78 #include "print-tree.h"
79 #include "tree-inline.h"
80 #include "langhooks.h"
82 #include "diagnostic.h"
83 #include "gimple-pretty-print.h"
85 #include "tree-pass.h"
88 #include "internal-fn.h"
89 #include "gimple-iterator.h"
91 #include "tree-ssa-loop-niter.h"
92 #include "tree-ssa-loop.h"
94 #include "alloc-pool.h"
95 #include "symbol-summary.h"
97 #include "tree-streamer.h"
98 #include "ipa-inline.h"
100 #include "tree-scalar-evolution.h"
101 #include "ipa-utils.h"
103 #include "cfgexpand.h"
105 /* Estimate runtime of function can easilly run into huge numbers with many
106 nested loops. Be sure we can compute time * INLINE_SIZE_SCALE * 2 in an
107 integer. For anything larger we use gcov_type. */
108 #define MAX_TIME 500000
110 /* Number of bits in integer, but we really want to be stable across different
112 #define NUM_CONDITIONS 32
114 enum predicate_conditions
116 predicate_false_condition
= 0,
117 predicate_not_inlined_condition
= 1,
118 predicate_first_dynamic_condition
= 2
121 /* Special condition code we use to represent test that operand is compile time
123 #define IS_NOT_CONSTANT ERROR_MARK
124 /* Special condition code we use to represent test that operand is not changed
125 across invocation of the function. When operand IS_NOT_CONSTANT it is always
126 CHANGED, however i.e. loop invariants can be NOT_CHANGED given percentage
127 of executions even when they are not compile time constants. */
128 #define CHANGED IDENTIFIER_NODE
130 /* Holders of ipa cgraph hooks: */
131 static struct cgraph_2edge_hook_list
*edge_duplication_hook_holder
;
132 static struct cgraph_edge_hook_list
*edge_removal_hook_holder
;
133 static void inline_edge_removal_hook (struct cgraph_edge
*, void *);
134 static void inline_edge_duplication_hook (struct cgraph_edge
*,
135 struct cgraph_edge
*, void *);
137 /* VECtor holding inline summaries.
138 In GGC memory because conditions might point to constant trees. */
139 function_summary
<inline_summary
*> *inline_summaries
;
140 vec
<inline_edge_summary_t
> inline_edge_summary_vec
;
142 /* Cached node/edge growths. */
143 vec
<edge_growth_cache_entry
> edge_growth_cache
;
145 /* Edge predicates goes here. */
146 static object_allocator
<predicate
> edge_predicate_pool ("edge predicates");
148 /* Return true predicate (tautology).
149 We represent it by empty list of clauses. */
151 static inline struct predicate
152 true_predicate (void)
160 /* Return predicate testing single condition number COND. */
162 static inline struct predicate
163 single_cond_predicate (int cond
)
166 p
.clause
[0] = 1 << cond
;
172 /* Return false predicate. First clause require false condition. */
174 static inline struct predicate
175 false_predicate (void)
177 return single_cond_predicate (predicate_false_condition
);
181 /* Return true if P is (true). */
184 true_predicate_p (struct predicate
*p
)
186 return !p
->clause
[0];
190 /* Return true if P is (false). */
193 false_predicate_p (struct predicate
*p
)
195 if (p
->clause
[0] == (1 << predicate_false_condition
))
197 gcc_checking_assert (!p
->clause
[1]
198 && p
->clause
[0] == 1 << predicate_false_condition
);
205 /* Return predicate that is set true when function is not inlined. */
207 static inline struct predicate
208 not_inlined_predicate (void)
210 return single_cond_predicate (predicate_not_inlined_condition
);
213 /* Simple description of whether a memory load or a condition refers to a load
214 from an aggregate and if so, how and where from in the aggregate.
215 Individual fields have the same meaning like fields with the same name in
218 struct agg_position_info
220 HOST_WIDE_INT offset
;
225 /* Add condition to condition list CONDS. AGGPOS describes whether the used
226 oprand is loaded from an aggregate and where in the aggregate it is. It can
227 be NULL, which means this not a load from an aggregate. */
229 static struct predicate
230 add_condition (struct inline_summary
*summary
, int operand_num
,
231 struct agg_position_info
*aggpos
,
232 enum tree_code code
, tree val
)
236 struct condition new_cond
;
237 HOST_WIDE_INT offset
;
238 bool agg_contents
, by_ref
;
242 offset
= aggpos
->offset
;
243 agg_contents
= aggpos
->agg_contents
;
244 by_ref
= aggpos
->by_ref
;
249 agg_contents
= false;
253 gcc_checking_assert (operand_num
>= 0);
254 for (i
= 0; vec_safe_iterate (summary
->conds
, i
, &c
); i
++)
256 if (c
->operand_num
== operand_num
259 && c
->agg_contents
== agg_contents
260 && (!agg_contents
|| (c
->offset
== offset
&& c
->by_ref
== by_ref
)))
261 return single_cond_predicate (i
+ predicate_first_dynamic_condition
);
263 /* Too many conditions. Give up and return constant true. */
264 if (i
== NUM_CONDITIONS
- predicate_first_dynamic_condition
)
265 return true_predicate ();
267 new_cond
.operand_num
= operand_num
;
268 new_cond
.code
= code
;
270 new_cond
.agg_contents
= agg_contents
;
271 new_cond
.by_ref
= by_ref
;
272 new_cond
.offset
= offset
;
273 vec_safe_push (summary
->conds
, new_cond
);
274 return single_cond_predicate (i
+ predicate_first_dynamic_condition
);
278 /* Add clause CLAUSE into the predicate P. */
281 add_clause (conditions conditions
, struct predicate
*p
, clause_t clause
)
285 int insert_here
= -1;
292 /* False clause makes the whole predicate false. Kill the other variants. */
293 if (clause
== (1 << predicate_false_condition
))
295 p
->clause
[0] = (1 << predicate_false_condition
);
299 if (false_predicate_p (p
))
302 /* No one should be silly enough to add false into nontrivial clauses. */
303 gcc_checking_assert (!(clause
& (1 << predicate_false_condition
)));
305 /* Look where to insert the clause. At the same time prune out
306 clauses of P that are implied by the new clause and thus
308 for (i
= 0, i2
= 0; i
<= MAX_CLAUSES
; i
++)
310 p
->clause
[i2
] = p
->clause
[i
];
315 /* If p->clause[i] implies clause, there is nothing to add. */
316 if ((p
->clause
[i
] & clause
) == p
->clause
[i
])
318 /* We had nothing to add, none of clauses should've become
320 gcc_checking_assert (i
== i2
);
324 if (p
->clause
[i
] < clause
&& insert_here
< 0)
327 /* If clause implies p->clause[i], then p->clause[i] becomes redundant.
328 Otherwise the p->clause[i] has to stay. */
329 if ((p
->clause
[i
] & clause
) != clause
)
333 /* Look for clauses that are obviously true. I.e.
334 op0 == 5 || op0 != 5. */
335 for (c1
= predicate_first_dynamic_condition
; c1
< NUM_CONDITIONS
; c1
++)
338 if (!(clause
& (1 << c1
)))
340 cc1
= &(*conditions
)[c1
- predicate_first_dynamic_condition
];
341 /* We have no way to represent !CHANGED and !IS_NOT_CONSTANT
342 and thus there is no point for looking for them. */
343 if (cc1
->code
== CHANGED
|| cc1
->code
== IS_NOT_CONSTANT
)
345 for (c2
= c1
+ 1; c2
< NUM_CONDITIONS
; c2
++)
346 if (clause
& (1 << c2
))
349 &(*conditions
)[c1
- predicate_first_dynamic_condition
];
351 &(*conditions
)[c2
- predicate_first_dynamic_condition
];
352 if (cc1
->operand_num
== cc2
->operand_num
353 && cc1
->val
== cc2
->val
354 && cc2
->code
!= IS_NOT_CONSTANT
355 && cc2
->code
!= CHANGED
356 && cc1
->code
== invert_tree_comparison (cc2
->code
,
357 HONOR_NANS (cc1
->val
)))
363 /* We run out of variants. Be conservative in positive direction. */
364 if (i2
== MAX_CLAUSES
)
366 /* Keep clauses in decreasing order. This makes equivalence testing easy. */
367 p
->clause
[i2
+ 1] = 0;
368 if (insert_here
>= 0)
369 for (; i2
> insert_here
; i2
--)
370 p
->clause
[i2
] = p
->clause
[i2
- 1];
373 p
->clause
[insert_here
] = clause
;
379 static struct predicate
380 and_predicates (conditions conditions
,
381 struct predicate
*p
, struct predicate
*p2
)
383 struct predicate out
= *p
;
386 /* Avoid busy work. */
387 if (false_predicate_p (p2
) || true_predicate_p (p
))
389 if (false_predicate_p (p
) || true_predicate_p (p2
))
392 /* See how far predicates match. */
393 for (i
= 0; p
->clause
[i
] && p
->clause
[i
] == p2
->clause
[i
]; i
++)
395 gcc_checking_assert (i
< MAX_CLAUSES
);
398 /* Combine the predicates rest. */
399 for (; p2
->clause
[i
]; i
++)
401 gcc_checking_assert (i
< MAX_CLAUSES
);
402 add_clause (conditions
, &out
, p2
->clause
[i
]);
408 /* Return true if predicates are obviously equal. */
411 predicates_equal_p (struct predicate
*p
, struct predicate
*p2
)
414 for (i
= 0; p
->clause
[i
]; i
++)
416 gcc_checking_assert (i
< MAX_CLAUSES
);
417 gcc_checking_assert (p
->clause
[i
] > p
->clause
[i
+ 1]);
418 gcc_checking_assert (!p2
->clause
[i
]
419 || p2
->clause
[i
] > p2
->clause
[i
+ 1]);
420 if (p
->clause
[i
] != p2
->clause
[i
])
423 return !p2
->clause
[i
];
429 static struct predicate
430 or_predicates (conditions conditions
,
431 struct predicate
*p
, struct predicate
*p2
)
433 struct predicate out
= true_predicate ();
436 /* Avoid busy work. */
437 if (false_predicate_p (p2
) || true_predicate_p (p
))
439 if (false_predicate_p (p
) || true_predicate_p (p2
))
441 if (predicates_equal_p (p
, p2
))
444 /* OK, combine the predicates. */
445 for (i
= 0; p
->clause
[i
]; i
++)
446 for (j
= 0; p2
->clause
[j
]; j
++)
448 gcc_checking_assert (i
< MAX_CLAUSES
&& j
< MAX_CLAUSES
);
449 add_clause (conditions
, &out
, p
->clause
[i
] | p2
->clause
[j
]);
455 /* Having partial truth assignment in POSSIBLE_TRUTHS, return false
456 if predicate P is known to be false. */
459 evaluate_predicate (struct predicate
*p
, clause_t possible_truths
)
463 /* True remains true. */
464 if (true_predicate_p (p
))
467 gcc_assert (!(possible_truths
& (1 << predicate_false_condition
)));
469 /* See if we can find clause we can disprove. */
470 for (i
= 0; p
->clause
[i
]; i
++)
472 gcc_checking_assert (i
< MAX_CLAUSES
);
473 if (!(p
->clause
[i
] & possible_truths
))
479 /* Return the probability in range 0...REG_BR_PROB_BASE that the predicated
480 instruction will be recomputed per invocation of the inlined call. */
483 predicate_probability (conditions conds
,
484 struct predicate
*p
, clause_t possible_truths
,
485 vec
<inline_param_summary
> inline_param_summary
)
488 int combined_prob
= REG_BR_PROB_BASE
;
490 /* True remains true. */
491 if (true_predicate_p (p
))
492 return REG_BR_PROB_BASE
;
494 if (false_predicate_p (p
))
497 gcc_assert (!(possible_truths
& (1 << predicate_false_condition
)));
499 /* See if we can find clause we can disprove. */
500 for (i
= 0; p
->clause
[i
]; i
++)
502 gcc_checking_assert (i
< MAX_CLAUSES
);
503 if (!(p
->clause
[i
] & possible_truths
))
509 if (!inline_param_summary
.exists ())
510 return REG_BR_PROB_BASE
;
511 for (i2
= 0; i2
< NUM_CONDITIONS
; i2
++)
512 if ((p
->clause
[i
] & possible_truths
) & (1 << i2
))
514 if (i2
>= predicate_first_dynamic_condition
)
517 &(*conds
)[i2
- predicate_first_dynamic_condition
];
518 if (c
->code
== CHANGED
520 (int) inline_param_summary
.length ()))
523 inline_param_summary
[c
->operand_num
].change_prob
;
524 this_prob
= MAX (this_prob
, iprob
);
527 this_prob
= REG_BR_PROB_BASE
;
530 this_prob
= REG_BR_PROB_BASE
;
532 combined_prob
= MIN (this_prob
, combined_prob
);
537 return combined_prob
;
541 /* Dump conditional COND. */
544 dump_condition (FILE *f
, conditions conditions
, int cond
)
547 if (cond
== predicate_false_condition
)
548 fprintf (f
, "false");
549 else if (cond
== predicate_not_inlined_condition
)
550 fprintf (f
, "not inlined");
553 c
= &(*conditions
)[cond
- predicate_first_dynamic_condition
];
554 fprintf (f
, "op%i", c
->operand_num
);
556 fprintf (f
, "[%soffset: " HOST_WIDE_INT_PRINT_DEC
"]",
557 c
->by_ref
? "ref " : "", c
->offset
);
558 if (c
->code
== IS_NOT_CONSTANT
)
560 fprintf (f
, " not constant");
563 if (c
->code
== CHANGED
)
565 fprintf (f
, " changed");
568 fprintf (f
, " %s ", op_symbol_code (c
->code
));
569 print_generic_expr (f
, c
->val
, 1);
574 /* Dump clause CLAUSE. */
577 dump_clause (FILE *f
, conditions conds
, clause_t clause
)
584 for (i
= 0; i
< NUM_CONDITIONS
; i
++)
585 if (clause
& (1 << i
))
590 dump_condition (f
, conds
, i
);
596 /* Dump predicate PREDICATE. */
599 dump_predicate (FILE *f
, conditions conds
, struct predicate
*pred
)
602 if (true_predicate_p (pred
))
603 dump_clause (f
, conds
, 0);
605 for (i
= 0; pred
->clause
[i
]; i
++)
609 dump_clause (f
, conds
, pred
->clause
[i
]);
615 /* Dump inline hints. */
617 dump_inline_hints (FILE *f
, inline_hints hints
)
621 fprintf (f
, "inline hints:");
622 if (hints
& INLINE_HINT_indirect_call
)
624 hints
&= ~INLINE_HINT_indirect_call
;
625 fprintf (f
, " indirect_call");
627 if (hints
& INLINE_HINT_loop_iterations
)
629 hints
&= ~INLINE_HINT_loop_iterations
;
630 fprintf (f
, " loop_iterations");
632 if (hints
& INLINE_HINT_loop_stride
)
634 hints
&= ~INLINE_HINT_loop_stride
;
635 fprintf (f
, " loop_stride");
637 if (hints
& INLINE_HINT_same_scc
)
639 hints
&= ~INLINE_HINT_same_scc
;
640 fprintf (f
, " same_scc");
642 if (hints
& INLINE_HINT_in_scc
)
644 hints
&= ~INLINE_HINT_in_scc
;
645 fprintf (f
, " in_scc");
647 if (hints
& INLINE_HINT_cross_module
)
649 hints
&= ~INLINE_HINT_cross_module
;
650 fprintf (f
, " cross_module");
652 if (hints
& INLINE_HINT_declared_inline
)
654 hints
&= ~INLINE_HINT_declared_inline
;
655 fprintf (f
, " declared_inline");
657 if (hints
& INLINE_HINT_array_index
)
659 hints
&= ~INLINE_HINT_array_index
;
660 fprintf (f
, " array_index");
662 if (hints
& INLINE_HINT_known_hot
)
664 hints
&= ~INLINE_HINT_known_hot
;
665 fprintf (f
, " known_hot");
671 /* Record SIZE and TIME under condition PRED into the inline summary. */
674 account_size_time (struct inline_summary
*summary
, int size
, int time
,
675 struct predicate
*pred
)
681 if (false_predicate_p (pred
))
684 /* We need to create initial empty unconitional clause, but otherwie
685 we don't need to account empty times and sizes. */
686 if (!size
&& !time
&& summary
->entry
)
689 /* Watch overflow that might result from insane profiles. */
690 if (time
> MAX_TIME
* INLINE_TIME_SCALE
)
691 time
= MAX_TIME
* INLINE_TIME_SCALE
;
692 gcc_assert (time
>= 0);
694 for (i
= 0; vec_safe_iterate (summary
->entry
, i
, &e
); i
++)
695 if (predicates_equal_p (&e
->predicate
, pred
))
704 e
= &(*summary
->entry
)[0];
705 gcc_assert (!e
->predicate
.clause
[0]);
706 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
708 "\t\tReached limit on number of entries, "
709 "ignoring the predicate.");
711 if (dump_file
&& (dump_flags
& TDF_DETAILS
) && (time
|| size
))
714 "\t\tAccounting size:%3.2f, time:%3.2f on %spredicate:",
715 ((double) size
) / INLINE_SIZE_SCALE
,
716 ((double) time
) / INLINE_TIME_SCALE
, found
? "" : "new ");
717 dump_predicate (dump_file
, summary
->conds
, pred
);
721 struct size_time_entry new_entry
;
722 new_entry
.size
= size
;
723 new_entry
.time
= time
;
724 new_entry
.predicate
= *pred
;
725 vec_safe_push (summary
->entry
, new_entry
);
731 if (e
->time
> MAX_TIME
* INLINE_TIME_SCALE
)
732 e
->time
= MAX_TIME
* INLINE_TIME_SCALE
;
736 /* We proved E to be unreachable, redirect it to __bultin_unreachable. */
738 static struct cgraph_edge
*
739 redirect_to_unreachable (struct cgraph_edge
*e
)
741 struct cgraph_node
*callee
= !e
->inline_failed
? e
->callee
: NULL
;
742 struct cgraph_node
*target
= cgraph_node::get_create
743 (builtin_decl_implicit (BUILT_IN_UNREACHABLE
));
746 e
= e
->resolve_speculation (target
->decl
);
748 e
->make_direct (target
);
750 e
->redirect_callee (target
);
751 struct inline_edge_summary
*es
= inline_edge_summary (e
);
752 e
->inline_failed
= CIF_UNREACHABLE
;
755 es
->call_stmt_size
= 0;
756 es
->call_stmt_time
= 0;
758 callee
->remove_symbol_and_inline_clones ();
762 /* Set predicate for edge E. */
765 edge_set_predicate (struct cgraph_edge
*e
, struct predicate
*predicate
)
767 /* If the edge is determined to be never executed, redirect it
768 to BUILTIN_UNREACHABLE to save inliner from inlining into it. */
769 if (predicate
&& false_predicate_p (predicate
)
770 /* When handling speculative edges, we need to do the redirection
771 just once. Do it always on the direct edge, so we do not
772 attempt to resolve speculation while duplicating the edge. */
773 && (!e
->speculative
|| e
->callee
))
774 e
= redirect_to_unreachable (e
);
776 struct inline_edge_summary
*es
= inline_edge_summary (e
);
777 if (predicate
&& !true_predicate_p (predicate
))
780 es
->predicate
= edge_predicate_pool
.allocate ();
781 *es
->predicate
= *predicate
;
786 edge_predicate_pool
.remove (es
->predicate
);
787 es
->predicate
= NULL
;
791 /* Set predicate for hint *P. */
794 set_hint_predicate (struct predicate
**p
, struct predicate new_predicate
)
796 if (false_predicate_p (&new_predicate
) || true_predicate_p (&new_predicate
))
799 edge_predicate_pool
.remove (*p
);
805 *p
= edge_predicate_pool
.allocate ();
811 /* KNOWN_VALS is partial mapping of parameters of NODE to constant values.
812 KNOWN_AGGS is a vector of aggreggate jump functions for each parameter.
813 Return clause of possible truths. When INLINE_P is true, assume that we are
816 ERROR_MARK means compile time invariant. */
819 evaluate_conditions_for_known_args (struct cgraph_node
*node
,
821 vec
<tree
> known_vals
,
822 vec
<ipa_agg_jump_function_p
>
825 clause_t clause
= inline_p
? 0 : 1 << predicate_not_inlined_condition
;
826 struct inline_summary
*info
= inline_summaries
->get (node
);
830 for (i
= 0; vec_safe_iterate (info
->conds
, i
, &c
); i
++)
835 /* We allow call stmt to have fewer arguments than the callee function
836 (especially for K&R style programs). So bound check here (we assume
837 known_aggs vector, if non-NULL, has the same length as
839 gcc_checking_assert (!known_aggs
.exists ()
840 || (known_vals
.length () == known_aggs
.length ()));
841 if (c
->operand_num
>= (int) known_vals
.length ())
843 clause
|= 1 << (i
+ predicate_first_dynamic_condition
);
849 struct ipa_agg_jump_function
*agg
;
851 if (c
->code
== CHANGED
853 && (known_vals
[c
->operand_num
] == error_mark_node
))
856 if (known_aggs
.exists ())
858 agg
= known_aggs
[c
->operand_num
];
859 val
= ipa_find_agg_cst_for_param (agg
, c
->offset
, c
->by_ref
);
866 val
= known_vals
[c
->operand_num
];
867 if (val
== error_mark_node
&& c
->code
!= CHANGED
)
873 clause
|= 1 << (i
+ predicate_first_dynamic_condition
);
876 if (c
->code
== IS_NOT_CONSTANT
|| c
->code
== CHANGED
)
879 if (operand_equal_p (TYPE_SIZE (TREE_TYPE (c
->val
)),
880 TYPE_SIZE (TREE_TYPE (val
)), 0))
882 val
= fold_unary (VIEW_CONVERT_EXPR
, TREE_TYPE (c
->val
), val
);
885 ? fold_binary_to_constant (c
->code
, boolean_type_node
, val
, c
->val
)
888 if (res
&& integer_zerop (res
))
891 clause
|= 1 << (i
+ predicate_first_dynamic_condition
);
897 /* Work out what conditions might be true at invocation of E. */
900 evaluate_properties_for_edge (struct cgraph_edge
*e
, bool inline_p
,
901 clause_t
*clause_ptr
,
902 vec
<tree
> *known_vals_ptr
,
903 vec
<ipa_polymorphic_call_context
>
905 vec
<ipa_agg_jump_function_p
> *known_aggs_ptr
)
907 struct cgraph_node
*callee
= e
->callee
->ultimate_alias_target ();
908 struct inline_summary
*info
= inline_summaries
->get (callee
);
909 vec
<tree
> known_vals
= vNULL
;
910 vec
<ipa_agg_jump_function_p
> known_aggs
= vNULL
;
913 *clause_ptr
= inline_p
? 0 : 1 << predicate_not_inlined_condition
;
915 known_vals_ptr
->create (0);
916 if (known_contexts_ptr
)
917 known_contexts_ptr
->create (0);
919 if (ipa_node_params_sum
920 && !e
->call_stmt_cannot_inline_p
921 && ((clause_ptr
&& info
->conds
) || known_vals_ptr
|| known_contexts_ptr
))
923 struct ipa_node_params
*parms_info
;
924 struct ipa_edge_args
*args
= IPA_EDGE_REF (e
);
925 struct inline_edge_summary
*es
= inline_edge_summary (e
);
926 int i
, count
= ipa_get_cs_argument_count (args
);
928 if (e
->caller
->global
.inlined_to
)
929 parms_info
= IPA_NODE_REF (e
->caller
->global
.inlined_to
);
931 parms_info
= IPA_NODE_REF (e
->caller
);
933 if (count
&& (info
->conds
|| known_vals_ptr
))
934 known_vals
.safe_grow_cleared (count
);
935 if (count
&& (info
->conds
|| known_aggs_ptr
))
936 known_aggs
.safe_grow_cleared (count
);
937 if (count
&& known_contexts_ptr
)
938 known_contexts_ptr
->safe_grow_cleared (count
);
940 for (i
= 0; i
< count
; i
++)
942 struct ipa_jump_func
*jf
= ipa_get_ith_jump_func (args
, i
);
943 tree cst
= ipa_value_from_jfunc (parms_info
, jf
);
945 if (!cst
&& e
->call_stmt
946 && i
< (int)gimple_call_num_args (e
->call_stmt
))
948 cst
= gimple_call_arg (e
->call_stmt
, i
);
949 if (!is_gimple_min_invariant (cst
))
954 gcc_checking_assert (TREE_CODE (cst
) != TREE_BINFO
);
955 if (known_vals
.exists ())
958 else if (inline_p
&& !es
->param
[i
].change_prob
)
959 known_vals
[i
] = error_mark_node
;
961 if (known_contexts_ptr
)
962 (*known_contexts_ptr
)[i
] = ipa_context_from_jfunc (parms_info
, e
,
964 /* TODO: When IPA-CP starts propagating and merging aggregate jump
965 functions, use its knowledge of the caller too, just like the
966 scalar case above. */
967 known_aggs
[i
] = &jf
->agg
;
970 else if (e
->call_stmt
&& !e
->call_stmt_cannot_inline_p
971 && ((clause_ptr
&& info
->conds
) || known_vals_ptr
))
973 int i
, count
= (int)gimple_call_num_args (e
->call_stmt
);
975 if (count
&& (info
->conds
|| known_vals_ptr
))
976 known_vals
.safe_grow_cleared (count
);
977 for (i
= 0; i
< count
; i
++)
979 tree cst
= gimple_call_arg (e
->call_stmt
, i
);
980 if (!is_gimple_min_invariant (cst
))
988 *clause_ptr
= evaluate_conditions_for_known_args (callee
, inline_p
,
989 known_vals
, known_aggs
);
992 *known_vals_ptr
= known_vals
;
994 known_vals
.release ();
997 *known_aggs_ptr
= known_aggs
;
999 known_aggs
.release ();
1003 /* Allocate the inline summary vector or resize it to cover all cgraph nodes. */
1006 inline_summary_alloc (void)
1008 if (!edge_removal_hook_holder
)
1009 edge_removal_hook_holder
=
1010 symtab
->add_edge_removal_hook (&inline_edge_removal_hook
, NULL
);
1011 if (!edge_duplication_hook_holder
)
1012 edge_duplication_hook_holder
=
1013 symtab
->add_edge_duplication_hook (&inline_edge_duplication_hook
, NULL
);
1015 if (!inline_summaries
)
1016 inline_summaries
= (inline_summary_t
*) inline_summary_t::create_ggc (symtab
);
1018 if (inline_edge_summary_vec
.length () <= (unsigned) symtab
->edges_max_uid
)
1019 inline_edge_summary_vec
.safe_grow_cleared (symtab
->edges_max_uid
+ 1);
1022 /* We are called multiple time for given function; clear
1023 data from previous run so they are not cumulated. */
1026 reset_inline_edge_summary (struct cgraph_edge
*e
)
1028 if (e
->uid
< (int) inline_edge_summary_vec
.length ())
1030 struct inline_edge_summary
*es
= inline_edge_summary (e
);
1032 es
->call_stmt_size
= es
->call_stmt_time
= 0;
1034 edge_predicate_pool
.remove (es
->predicate
);
1035 es
->predicate
= NULL
;
1036 es
->param
.release ();
1040 /* We are called multiple time for given function; clear
1041 data from previous run so they are not cumulated. */
1044 reset_inline_summary (struct cgraph_node
*node
,
1045 inline_summary
*info
)
1047 struct cgraph_edge
*e
;
1049 info
->self_size
= info
->self_time
= 0;
1050 info
->estimated_stack_size
= 0;
1051 info
->estimated_self_stack_size
= 0;
1052 info
->stack_frame_offset
= 0;
1057 if (info
->loop_iterations
)
1059 edge_predicate_pool
.remove (info
->loop_iterations
);
1060 info
->loop_iterations
= NULL
;
1062 if (info
->loop_stride
)
1064 edge_predicate_pool
.remove (info
->loop_stride
);
1065 info
->loop_stride
= NULL
;
1067 if (info
->array_index
)
1069 edge_predicate_pool
.remove (info
->array_index
);
1070 info
->array_index
= NULL
;
1072 vec_free (info
->conds
);
1073 vec_free (info
->entry
);
1074 for (e
= node
->callees
; e
; e
= e
->next_callee
)
1075 reset_inline_edge_summary (e
);
1076 for (e
= node
->indirect_calls
; e
; e
= e
->next_callee
)
1077 reset_inline_edge_summary (e
);
1080 /* Hook that is called by cgraph.c when a node is removed. */
1083 inline_summary_t::remove (cgraph_node
*node
, inline_summary
*info
)
1085 reset_inline_summary (node
, info
);
1088 /* Remap predicate P of former function to be predicate of duplicated function.
1089 POSSIBLE_TRUTHS is clause of possible truths in the duplicated node,
1090 INFO is inline summary of the duplicated node. */
1092 static struct predicate
1093 remap_predicate_after_duplication (struct predicate
*p
,
1094 clause_t possible_truths
,
1095 struct inline_summary
*info
)
1097 struct predicate new_predicate
= true_predicate ();
1099 for (j
= 0; p
->clause
[j
]; j
++)
1100 if (!(possible_truths
& p
->clause
[j
]))
1102 new_predicate
= false_predicate ();
1106 add_clause (info
->conds
, &new_predicate
,
1107 possible_truths
& p
->clause
[j
]);
1108 return new_predicate
;
1111 /* Same as remap_predicate_after_duplication but handle hint predicate *P.
1112 Additionally care about allocating new memory slot for updated predicate
1113 and set it to NULL when it becomes true or false (and thus uninteresting).
1117 remap_hint_predicate_after_duplication (struct predicate
**p
,
1118 clause_t possible_truths
,
1119 struct inline_summary
*info
)
1121 struct predicate new_predicate
;
1126 new_predicate
= remap_predicate_after_duplication (*p
,
1127 possible_truths
, info
);
1128 /* We do not want to free previous predicate; it is used by node origin. */
1130 set_hint_predicate (p
, new_predicate
);
1134 /* Hook that is called by cgraph.c when a node is duplicated. */
1136 inline_summary_t::duplicate (cgraph_node
*src
,
1139 inline_summary
*info
)
1141 inline_summary_alloc ();
1142 memcpy (info
, inline_summaries
->get (src
), sizeof (inline_summary
));
1143 /* TODO: as an optimization, we may avoid copying conditions
1144 that are known to be false or true. */
1145 info
->conds
= vec_safe_copy (info
->conds
);
1147 /* When there are any replacements in the function body, see if we can figure
1148 out that something was optimized out. */
1149 if (ipa_node_params_sum
&& dst
->clone
.tree_map
)
1151 vec
<size_time_entry
, va_gc
> *entry
= info
->entry
;
1152 /* Use SRC parm info since it may not be copied yet. */
1153 struct ipa_node_params
*parms_info
= IPA_NODE_REF (src
);
1154 vec
<tree
> known_vals
= vNULL
;
1155 int count
= ipa_get_param_count (parms_info
);
1157 clause_t possible_truths
;
1158 struct predicate true_pred
= true_predicate ();
1160 int optimized_out_size
= 0;
1161 bool inlined_to_p
= false;
1162 struct cgraph_edge
*edge
, *next
;
1165 known_vals
.safe_grow_cleared (count
);
1166 for (i
= 0; i
< count
; i
++)
1168 struct ipa_replace_map
*r
;
1170 for (j
= 0; vec_safe_iterate (dst
->clone
.tree_map
, j
, &r
); j
++)
1172 if (((!r
->old_tree
&& r
->parm_num
== i
)
1173 || (r
->old_tree
&& r
->old_tree
== ipa_get_param (parms_info
, i
)))
1174 && r
->replace_p
&& !r
->ref_p
)
1176 known_vals
[i
] = r
->new_tree
;
1181 possible_truths
= evaluate_conditions_for_known_args (dst
, false,
1184 known_vals
.release ();
1186 account_size_time (info
, 0, 0, &true_pred
);
1188 /* Remap size_time vectors.
1189 Simplify the predicate by prunning out alternatives that are known
1191 TODO: as on optimization, we can also eliminate conditions known
1193 for (i
= 0; vec_safe_iterate (entry
, i
, &e
); i
++)
1195 struct predicate new_predicate
;
1196 new_predicate
= remap_predicate_after_duplication (&e
->predicate
,
1199 if (false_predicate_p (&new_predicate
))
1200 optimized_out_size
+= e
->size
;
1202 account_size_time (info
, e
->size
, e
->time
, &new_predicate
);
1205 /* Remap edge predicates with the same simplification as above.
1206 Also copy constantness arrays. */
1207 for (edge
= dst
->callees
; edge
; edge
= next
)
1209 struct predicate new_predicate
;
1210 struct inline_edge_summary
*es
= inline_edge_summary (edge
);
1211 next
= edge
->next_callee
;
1213 if (!edge
->inline_failed
)
1214 inlined_to_p
= true;
1217 new_predicate
= remap_predicate_after_duplication (es
->predicate
,
1220 if (false_predicate_p (&new_predicate
)
1221 && !false_predicate_p (es
->predicate
))
1222 optimized_out_size
+= es
->call_stmt_size
* INLINE_SIZE_SCALE
;
1223 edge_set_predicate (edge
, &new_predicate
);
1226 /* Remap indirect edge predicates with the same simplificaiton as above.
1227 Also copy constantness arrays. */
1228 for (edge
= dst
->indirect_calls
; edge
; edge
= next
)
1230 struct predicate new_predicate
;
1231 struct inline_edge_summary
*es
= inline_edge_summary (edge
);
1232 next
= edge
->next_callee
;
1234 gcc_checking_assert (edge
->inline_failed
);
1237 new_predicate
= remap_predicate_after_duplication (es
->predicate
,
1240 if (false_predicate_p (&new_predicate
)
1241 && !false_predicate_p (es
->predicate
))
1242 optimized_out_size
+= es
->call_stmt_size
* INLINE_SIZE_SCALE
;
1243 edge_set_predicate (edge
, &new_predicate
);
1245 remap_hint_predicate_after_duplication (&info
->loop_iterations
,
1246 possible_truths
, info
);
1247 remap_hint_predicate_after_duplication (&info
->loop_stride
,
1248 possible_truths
, info
);
1249 remap_hint_predicate_after_duplication (&info
->array_index
,
1250 possible_truths
, info
);
1252 /* If inliner or someone after inliner will ever start producing
1253 non-trivial clones, we will get trouble with lack of information
1254 about updating self sizes, because size vectors already contains
1255 sizes of the calees. */
1256 gcc_assert (!inlined_to_p
|| !optimized_out_size
);
1260 info
->entry
= vec_safe_copy (info
->entry
);
1261 if (info
->loop_iterations
)
1263 predicate p
= *info
->loop_iterations
;
1264 info
->loop_iterations
= NULL
;
1265 set_hint_predicate (&info
->loop_iterations
, p
);
1267 if (info
->loop_stride
)
1269 predicate p
= *info
->loop_stride
;
1270 info
->loop_stride
= NULL
;
1271 set_hint_predicate (&info
->loop_stride
, p
);
1273 if (info
->array_index
)
1275 predicate p
= *info
->array_index
;
1276 info
->array_index
= NULL
;
1277 set_hint_predicate (&info
->array_index
, p
);
1280 if (!dst
->global
.inlined_to
)
1281 inline_update_overall_summary (dst
);
1285 /* Hook that is called by cgraph.c when a node is duplicated. */
1288 inline_edge_duplication_hook (struct cgraph_edge
*src
,
1289 struct cgraph_edge
*dst
,
1290 ATTRIBUTE_UNUSED
void *data
)
1292 struct inline_edge_summary
*info
;
1293 struct inline_edge_summary
*srcinfo
;
1294 inline_summary_alloc ();
1295 info
= inline_edge_summary (dst
);
1296 srcinfo
= inline_edge_summary (src
);
1297 memcpy (info
, srcinfo
, sizeof (struct inline_edge_summary
));
1298 info
->predicate
= NULL
;
1299 edge_set_predicate (dst
, srcinfo
->predicate
);
1300 info
->param
= srcinfo
->param
.copy ();
1301 if (!dst
->indirect_unknown_callee
&& src
->indirect_unknown_callee
)
1303 info
->call_stmt_size
-= (eni_size_weights
.indirect_call_cost
1304 - eni_size_weights
.call_cost
);
1305 info
->call_stmt_time
-= (eni_time_weights
.indirect_call_cost
1306 - eni_time_weights
.call_cost
);
1311 /* Keep edge cache consistent across edge removal. */
1314 inline_edge_removal_hook (struct cgraph_edge
*edge
,
1315 void *data ATTRIBUTE_UNUSED
)
1317 if (edge_growth_cache
.exists ())
1318 reset_edge_growth_cache (edge
);
1319 reset_inline_edge_summary (edge
);
1323 /* Initialize growth caches. */
1326 initialize_growth_caches (void)
1328 if (symtab
->edges_max_uid
)
1329 edge_growth_cache
.safe_grow_cleared (symtab
->edges_max_uid
);
1333 /* Free growth caches. */
1336 free_growth_caches (void)
1338 edge_growth_cache
.release ();
1342 /* Dump edge summaries associated to NODE and recursively to all clones.
1343 Indent by INDENT. */
1346 dump_inline_edge_summary (FILE *f
, int indent
, struct cgraph_node
*node
,
1347 struct inline_summary
*info
)
1349 struct cgraph_edge
*edge
;
1350 for (edge
= node
->callees
; edge
; edge
= edge
->next_callee
)
1352 struct inline_edge_summary
*es
= inline_edge_summary (edge
);
1353 struct cgraph_node
*callee
= edge
->callee
->ultimate_alias_target ();
1357 "%*s%s/%i %s\n%*s loop depth:%2i freq:%4i size:%2i"
1358 " time: %2i callee size:%2i stack:%2i",
1359 indent
, "", callee
->name (), callee
->order
,
1360 !edge
->inline_failed
1361 ? "inlined" : cgraph_inline_failed_string (edge
-> inline_failed
),
1362 indent
, "", es
->loop_depth
, edge
->frequency
,
1363 es
->call_stmt_size
, es
->call_stmt_time
,
1364 (int) inline_summaries
->get (callee
)->size
/ INLINE_SIZE_SCALE
,
1365 (int) inline_summaries
->get (callee
)->estimated_stack_size
);
1369 fprintf (f
, " predicate: ");
1370 dump_predicate (f
, info
->conds
, es
->predicate
);
1374 if (es
->param
.exists ())
1375 for (i
= 0; i
< (int) es
->param
.length (); i
++)
1377 int prob
= es
->param
[i
].change_prob
;
1380 fprintf (f
, "%*s op%i is compile time invariant\n",
1382 else if (prob
!= REG_BR_PROB_BASE
)
1383 fprintf (f
, "%*s op%i change %f%% of time\n", indent
+ 2, "", i
,
1384 prob
* 100.0 / REG_BR_PROB_BASE
);
1386 if (!edge
->inline_failed
)
1388 fprintf (f
, "%*sStack frame offset %i, callee self size %i,"
1389 " callee size %i\n",
1391 (int) inline_summaries
->get (callee
)->stack_frame_offset
,
1392 (int) inline_summaries
->get (callee
)->estimated_self_stack_size
,
1393 (int) inline_summaries
->get (callee
)->estimated_stack_size
);
1394 dump_inline_edge_summary (f
, indent
+ 2, callee
, info
);
1397 for (edge
= node
->indirect_calls
; edge
; edge
= edge
->next_callee
)
1399 struct inline_edge_summary
*es
= inline_edge_summary (edge
);
1400 fprintf (f
, "%*sindirect call loop depth:%2i freq:%4i size:%2i"
1404 edge
->frequency
, es
->call_stmt_size
, es
->call_stmt_time
);
1407 fprintf (f
, "predicate: ");
1408 dump_predicate (f
, info
->conds
, es
->predicate
);
1417 dump_inline_summary (FILE *f
, struct cgraph_node
*node
)
1419 if (node
->definition
)
1421 struct inline_summary
*s
= inline_summaries
->get (node
);
1424 fprintf (f
, "Inline summary for %s/%i", node
->name (),
1426 if (DECL_DISREGARD_INLINE_LIMITS (node
->decl
))
1427 fprintf (f
, " always_inline");
1429 fprintf (f
, " inlinable");
1430 if (s
->contains_cilk_spawn
)
1431 fprintf (f
, " contains_cilk_spawn");
1432 fprintf (f
, "\n self time: %i\n", s
->self_time
);
1433 fprintf (f
, " global time: %i\n", s
->time
);
1434 fprintf (f
, " self size: %i\n", s
->self_size
);
1435 fprintf (f
, " global size: %i\n", s
->size
);
1436 fprintf (f
, " min size: %i\n", s
->min_size
);
1437 fprintf (f
, " self stack: %i\n",
1438 (int) s
->estimated_self_stack_size
);
1439 fprintf (f
, " global stack: %i\n", (int) s
->estimated_stack_size
);
1441 fprintf (f
, " estimated growth:%i\n", (int) s
->growth
);
1443 fprintf (f
, " In SCC: %i\n", (int) s
->scc_no
);
1444 for (i
= 0; vec_safe_iterate (s
->entry
, i
, &e
); i
++)
1446 fprintf (f
, " size:%f, time:%f, predicate:",
1447 (double) e
->size
/ INLINE_SIZE_SCALE
,
1448 (double) e
->time
/ INLINE_TIME_SCALE
);
1449 dump_predicate (f
, s
->conds
, &e
->predicate
);
1451 if (s
->loop_iterations
)
1453 fprintf (f
, " loop iterations:");
1454 dump_predicate (f
, s
->conds
, s
->loop_iterations
);
1458 fprintf (f
, " loop stride:");
1459 dump_predicate (f
, s
->conds
, s
->loop_stride
);
1463 fprintf (f
, " array index:");
1464 dump_predicate (f
, s
->conds
, s
->array_index
);
1466 fprintf (f
, " calls:\n");
1467 dump_inline_edge_summary (f
, 4, node
, s
);
1473 debug_inline_summary (struct cgraph_node
*node
)
1475 dump_inline_summary (stderr
, node
);
1479 dump_inline_summaries (FILE *f
)
1481 struct cgraph_node
*node
;
1483 FOR_EACH_DEFINED_FUNCTION (node
)
1484 if (!node
->global
.inlined_to
)
1485 dump_inline_summary (f
, node
);
1488 /* Give initial reasons why inlining would fail on EDGE. This gets either
1489 nullified or usually overwritten by more precise reasons later. */
1492 initialize_inline_failed (struct cgraph_edge
*e
)
1494 struct cgraph_node
*callee
= e
->callee
;
1496 if (e
->indirect_unknown_callee
)
1497 e
->inline_failed
= CIF_INDIRECT_UNKNOWN_CALL
;
1498 else if (!callee
->definition
)
1499 e
->inline_failed
= CIF_BODY_NOT_AVAILABLE
;
1500 else if (callee
->local
.redefined_extern_inline
)
1501 e
->inline_failed
= CIF_REDEFINED_EXTERN_INLINE
;
1502 else if (e
->call_stmt_cannot_inline_p
)
1503 e
->inline_failed
= CIF_MISMATCHED_ARGUMENTS
;
1504 else if (cfun
&& fn_contains_cilk_spawn_p (cfun
))
1505 /* We can't inline if the function is spawing a function. */
1506 e
->inline_failed
= CIF_FUNCTION_NOT_INLINABLE
;
1508 e
->inline_failed
= CIF_FUNCTION_NOT_CONSIDERED
;
1511 /* Callback of walk_aliased_vdefs. Flags that it has been invoked to the
1512 boolean variable pointed to by DATA. */
1515 mark_modified (ao_ref
*ao ATTRIBUTE_UNUSED
, tree vdef ATTRIBUTE_UNUSED
,
1518 bool *b
= (bool *) data
;
1523 /* If OP refers to value of function parameter, return the corresponding
1527 unmodified_parm_1 (gimple
*stmt
, tree op
)
1529 /* SSA_NAME referring to parm default def? */
1530 if (TREE_CODE (op
) == SSA_NAME
1531 && SSA_NAME_IS_DEFAULT_DEF (op
)
1532 && TREE_CODE (SSA_NAME_VAR (op
)) == PARM_DECL
)
1533 return SSA_NAME_VAR (op
);
1534 /* Non-SSA parm reference? */
1535 if (TREE_CODE (op
) == PARM_DECL
)
1537 bool modified
= false;
1540 ao_ref_init (&refd
, op
);
1541 walk_aliased_vdefs (&refd
, gimple_vuse (stmt
), mark_modified
, &modified
,
1549 /* If OP refers to value of function parameter, return the corresponding
1550 parameter. Also traverse chains of SSA register assignments. */
1553 unmodified_parm (gimple
*stmt
, tree op
)
1555 tree res
= unmodified_parm_1 (stmt
, op
);
1559 if (TREE_CODE (op
) == SSA_NAME
1560 && !SSA_NAME_IS_DEFAULT_DEF (op
)
1561 && gimple_assign_single_p (SSA_NAME_DEF_STMT (op
)))
1562 return unmodified_parm (SSA_NAME_DEF_STMT (op
),
1563 gimple_assign_rhs1 (SSA_NAME_DEF_STMT (op
)));
1567 /* If OP refers to a value of a function parameter or value loaded from an
1568 aggregate passed to a parameter (either by value or reference), return TRUE
1569 and store the number of the parameter to *INDEX_P and information whether
1570 and how it has been loaded from an aggregate into *AGGPOS. INFO describes
1571 the function parameters, STMT is the statement in which OP is used or
1575 unmodified_parm_or_parm_agg_item (struct ipa_func_body_info
*fbi
,
1576 gimple
*stmt
, tree op
, int *index_p
,
1577 struct agg_position_info
*aggpos
)
1579 tree res
= unmodified_parm_1 (stmt
, op
);
1581 gcc_checking_assert (aggpos
);
1584 *index_p
= ipa_get_param_decl_index (fbi
->info
, res
);
1587 aggpos
->agg_contents
= false;
1588 aggpos
->by_ref
= false;
1592 if (TREE_CODE (op
) == SSA_NAME
)
1594 if (SSA_NAME_IS_DEFAULT_DEF (op
)
1595 || !gimple_assign_single_p (SSA_NAME_DEF_STMT (op
)))
1597 stmt
= SSA_NAME_DEF_STMT (op
);
1598 op
= gimple_assign_rhs1 (stmt
);
1599 if (!REFERENCE_CLASS_P (op
))
1600 return unmodified_parm_or_parm_agg_item (fbi
, stmt
, op
, index_p
,
1604 aggpos
->agg_contents
= true;
1605 return ipa_load_from_parm_agg (fbi
, fbi
->info
->descriptors
,
1606 stmt
, op
, index_p
, &aggpos
->offset
,
1607 NULL
, &aggpos
->by_ref
);
1610 /* See if statement might disappear after inlining.
1611 0 - means not eliminated
1612 1 - half of statements goes away
1613 2 - for sure it is eliminated.
1614 We are not terribly sophisticated, basically looking for simple abstraction
1615 penalty wrappers. */
1618 eliminated_by_inlining_prob (gimple
*stmt
)
1620 enum gimple_code code
= gimple_code (stmt
);
1621 enum tree_code rhs_code
;
1631 if (gimple_num_ops (stmt
) != 2)
1634 rhs_code
= gimple_assign_rhs_code (stmt
);
1636 /* Casts of parameters, loads from parameters passed by reference
1637 and stores to return value or parameters are often free after
1638 inlining dua to SRA and further combining.
1639 Assume that half of statements goes away. */
1640 if (CONVERT_EXPR_CODE_P (rhs_code
)
1641 || rhs_code
== VIEW_CONVERT_EXPR
1642 || rhs_code
== ADDR_EXPR
1643 || gimple_assign_rhs_class (stmt
) == GIMPLE_SINGLE_RHS
)
1645 tree rhs
= gimple_assign_rhs1 (stmt
);
1646 tree lhs
= gimple_assign_lhs (stmt
);
1647 tree inner_rhs
= get_base_address (rhs
);
1648 tree inner_lhs
= get_base_address (lhs
);
1649 bool rhs_free
= false;
1650 bool lhs_free
= false;
1657 /* Reads of parameter are expected to be free. */
1658 if (unmodified_parm (stmt
, inner_rhs
))
1660 /* Match expressions of form &this->field. Those will most likely
1661 combine with something upstream after inlining. */
1662 else if (TREE_CODE (inner_rhs
) == ADDR_EXPR
)
1664 tree op
= get_base_address (TREE_OPERAND (inner_rhs
, 0));
1665 if (TREE_CODE (op
) == PARM_DECL
)
1667 else if (TREE_CODE (op
) == MEM_REF
1668 && unmodified_parm (stmt
, TREE_OPERAND (op
, 0)))
1672 /* When parameter is not SSA register because its address is taken
1673 and it is just copied into one, the statement will be completely
1674 free after inlining (we will copy propagate backward). */
1675 if (rhs_free
&& is_gimple_reg (lhs
))
1678 /* Reads of parameters passed by reference
1679 expected to be free (i.e. optimized out after inlining). */
1680 if (TREE_CODE (inner_rhs
) == MEM_REF
1681 && unmodified_parm (stmt
, TREE_OPERAND (inner_rhs
, 0)))
1684 /* Copying parameter passed by reference into gimple register is
1685 probably also going to copy propagate, but we can't be quite
1687 if (rhs_free
&& is_gimple_reg (lhs
))
1690 /* Writes to parameters, parameters passed by value and return value
1691 (either dirrectly or passed via invisible reference) are free.
1693 TODO: We ought to handle testcase like
1694 struct a {int a,b;};
1696 retrurnsturct (void)
1702 This translate into:
1717 For that we either need to copy ipa-split logic detecting writes
1719 if (TREE_CODE (inner_lhs
) == PARM_DECL
1720 || TREE_CODE (inner_lhs
) == RESULT_DECL
1721 || (TREE_CODE (inner_lhs
) == MEM_REF
1722 && (unmodified_parm (stmt
, TREE_OPERAND (inner_lhs
, 0))
1723 || (TREE_CODE (TREE_OPERAND (inner_lhs
, 0)) == SSA_NAME
1724 && SSA_NAME_VAR (TREE_OPERAND (inner_lhs
, 0))
1725 && TREE_CODE (SSA_NAME_VAR (TREE_OPERAND
1727 0))) == RESULT_DECL
))))
1730 && (is_gimple_reg (rhs
) || is_gimple_min_invariant (rhs
)))
1732 if (lhs_free
&& rhs_free
)
1742 /* If BB ends by a conditional we can turn into predicates, attach corresponding
1743 predicates to the CFG edges. */
1746 set_cond_stmt_execution_predicate (struct ipa_func_body_info
*fbi
,
1747 struct inline_summary
*summary
,
1753 struct agg_position_info aggpos
;
1754 enum tree_code code
, inverted_code
;
1760 last
= last_stmt (bb
);
1761 if (!last
|| gimple_code (last
) != GIMPLE_COND
)
1763 if (!is_gimple_ip_invariant (gimple_cond_rhs (last
)))
1765 op
= gimple_cond_lhs (last
);
1766 /* TODO: handle conditionals like
1769 if (unmodified_parm_or_parm_agg_item (fbi
, last
, op
, &index
, &aggpos
))
1771 code
= gimple_cond_code (last
);
1772 inverted_code
= invert_tree_comparison (code
, HONOR_NANS (op
));
1774 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1776 enum tree_code this_code
= (e
->flags
& EDGE_TRUE_VALUE
1777 ? code
: inverted_code
);
1778 /* invert_tree_comparison will return ERROR_MARK on FP
1779 comparsions that are not EQ/NE instead of returning proper
1780 unordered one. Be sure it is not confused with NON_CONSTANT. */
1781 if (this_code
!= ERROR_MARK
)
1783 struct predicate p
= add_condition (summary
, index
, &aggpos
,
1785 gimple_cond_rhs (last
));
1786 e
->aux
= edge_predicate_pool
.allocate ();
1787 *(struct predicate
*) e
->aux
= p
;
1792 if (TREE_CODE (op
) != SSA_NAME
)
1795 if (builtin_constant_p (op))
1799 Here we can predicate nonconstant_code. We can't
1800 really handle constant_code since we have no predicate
1801 for this and also the constant code is not known to be
1802 optimized away when inliner doen't see operand is constant.
1803 Other optimizers might think otherwise. */
1804 if (gimple_cond_code (last
) != NE_EXPR
1805 || !integer_zerop (gimple_cond_rhs (last
)))
1807 set_stmt
= SSA_NAME_DEF_STMT (op
);
1808 if (!gimple_call_builtin_p (set_stmt
, BUILT_IN_CONSTANT_P
)
1809 || gimple_call_num_args (set_stmt
) != 1)
1811 op2
= gimple_call_arg (set_stmt
, 0);
1812 if (!unmodified_parm_or_parm_agg_item (fbi
, set_stmt
, op2
, &index
, &aggpos
))
1814 FOR_EACH_EDGE (e
, ei
, bb
->succs
) if (e
->flags
& EDGE_FALSE_VALUE
)
1816 struct predicate p
= add_condition (summary
, index
, &aggpos
,
1817 IS_NOT_CONSTANT
, NULL_TREE
);
1818 e
->aux
= edge_predicate_pool
.allocate ();
1819 *(struct predicate
*) e
->aux
= p
;
1824 /* If BB ends by a switch we can turn into predicates, attach corresponding
1825 predicates to the CFG edges. */
1828 set_switch_stmt_execution_predicate (struct ipa_func_body_info
*fbi
,
1829 struct inline_summary
*summary
,
1835 struct agg_position_info aggpos
;
1841 lastg
= last_stmt (bb
);
1842 if (!lastg
|| gimple_code (lastg
) != GIMPLE_SWITCH
)
1844 gswitch
*last
= as_a
<gswitch
*> (lastg
);
1845 op
= gimple_switch_index (last
);
1846 if (!unmodified_parm_or_parm_agg_item (fbi
, last
, op
, &index
, &aggpos
))
1849 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1851 e
->aux
= edge_predicate_pool
.allocate ();
1852 *(struct predicate
*) e
->aux
= false_predicate ();
1854 n
= gimple_switch_num_labels (last
);
1855 for (case_idx
= 0; case_idx
< n
; ++case_idx
)
1857 tree cl
= gimple_switch_label (last
, case_idx
);
1861 e
= find_edge (bb
, label_to_block (CASE_LABEL (cl
)));
1862 min
= CASE_LOW (cl
);
1863 max
= CASE_HIGH (cl
);
1865 /* For default we might want to construct predicate that none
1866 of cases is met, but it is bit hard to do not having negations
1867 of conditionals handy. */
1869 p
= true_predicate ();
1871 p
= add_condition (summary
, index
, &aggpos
, EQ_EXPR
, min
);
1874 struct predicate p1
, p2
;
1875 p1
= add_condition (summary
, index
, &aggpos
, GE_EXPR
, min
);
1876 p2
= add_condition (summary
, index
, &aggpos
, LE_EXPR
, max
);
1877 p
= and_predicates (summary
->conds
, &p1
, &p2
);
1879 *(struct predicate
*) e
->aux
1880 = or_predicates (summary
->conds
, &p
, (struct predicate
*) e
->aux
);
1885 /* For each BB in NODE attach to its AUX pointer predicate under
1886 which it is executable. */
1889 compute_bb_predicates (struct ipa_func_body_info
*fbi
,
1890 struct cgraph_node
*node
,
1891 struct inline_summary
*summary
)
1893 struct function
*my_function
= DECL_STRUCT_FUNCTION (node
->decl
);
1897 FOR_EACH_BB_FN (bb
, my_function
)
1899 set_cond_stmt_execution_predicate (fbi
, summary
, bb
);
1900 set_switch_stmt_execution_predicate (fbi
, summary
, bb
);
1903 /* Entry block is always executable. */
1904 ENTRY_BLOCK_PTR_FOR_FN (my_function
)->aux
1905 = edge_predicate_pool
.allocate ();
1906 *(struct predicate
*) ENTRY_BLOCK_PTR_FOR_FN (my_function
)->aux
1907 = true_predicate ();
1909 /* A simple dataflow propagation of predicates forward in the CFG.
1910 TODO: work in reverse postorder. */
1914 FOR_EACH_BB_FN (bb
, my_function
)
1916 struct predicate p
= false_predicate ();
1919 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
1923 struct predicate this_bb_predicate
1924 = *(struct predicate
*) e
->src
->aux
;
1927 = and_predicates (summary
->conds
, &this_bb_predicate
,
1928 (struct predicate
*) e
->aux
);
1929 p
= or_predicates (summary
->conds
, &p
, &this_bb_predicate
);
1930 if (true_predicate_p (&p
))
1934 if (false_predicate_p (&p
))
1935 gcc_assert (!bb
->aux
);
1941 bb
->aux
= edge_predicate_pool
.allocate ();
1942 *((struct predicate
*) bb
->aux
) = p
;
1944 else if (!predicates_equal_p (&p
, (struct predicate
*) bb
->aux
))
1946 /* This OR operation is needed to ensure monotonous data flow
1947 in the case we hit the limit on number of clauses and the
1948 and/or operations above give approximate answers. */
1949 p
= or_predicates (summary
->conds
, &p
, (struct predicate
*)bb
->aux
);
1950 if (!predicates_equal_p (&p
, (struct predicate
*) bb
->aux
))
1953 *((struct predicate
*) bb
->aux
) = p
;
1962 /* We keep info about constantness of SSA names. */
1964 typedef struct predicate predicate_t
;
1965 /* Return predicate specifying when the STMT might have result that is not
1966 a compile time constant. */
1968 static struct predicate
1969 will_be_nonconstant_expr_predicate (struct ipa_node_params
*info
,
1970 struct inline_summary
*summary
,
1972 vec
<predicate_t
> nonconstant_names
)
1977 while (UNARY_CLASS_P (expr
))
1978 expr
= TREE_OPERAND (expr
, 0);
1980 parm
= unmodified_parm (NULL
, expr
);
1981 if (parm
&& (index
= ipa_get_param_decl_index (info
, parm
)) >= 0)
1982 return add_condition (summary
, index
, NULL
, CHANGED
, NULL_TREE
);
1983 if (is_gimple_min_invariant (expr
))
1984 return false_predicate ();
1985 if (TREE_CODE (expr
) == SSA_NAME
)
1986 return nonconstant_names
[SSA_NAME_VERSION (expr
)];
1987 if (BINARY_CLASS_P (expr
) || COMPARISON_CLASS_P (expr
))
1989 struct predicate p1
= will_be_nonconstant_expr_predicate
1990 (info
, summary
, TREE_OPERAND (expr
, 0),
1992 struct predicate p2
;
1993 if (true_predicate_p (&p1
))
1995 p2
= will_be_nonconstant_expr_predicate (info
, summary
,
1996 TREE_OPERAND (expr
, 1),
1998 return or_predicates (summary
->conds
, &p1
, &p2
);
2000 else if (TREE_CODE (expr
) == COND_EXPR
)
2002 struct predicate p1
= will_be_nonconstant_expr_predicate
2003 (info
, summary
, TREE_OPERAND (expr
, 0),
2005 struct predicate p2
;
2006 if (true_predicate_p (&p1
))
2008 p2
= will_be_nonconstant_expr_predicate (info
, summary
,
2009 TREE_OPERAND (expr
, 1),
2011 if (true_predicate_p (&p2
))
2013 p1
= or_predicates (summary
->conds
, &p1
, &p2
);
2014 p2
= will_be_nonconstant_expr_predicate (info
, summary
,
2015 TREE_OPERAND (expr
, 2),
2017 return or_predicates (summary
->conds
, &p1
, &p2
);
2024 return false_predicate ();
2028 /* Return predicate specifying when the STMT might have result that is not
2029 a compile time constant. */
2031 static struct predicate
2032 will_be_nonconstant_predicate (struct ipa_func_body_info
*fbi
,
2033 struct inline_summary
*summary
,
2035 vec
<predicate_t
> nonconstant_names
)
2037 struct predicate p
= true_predicate ();
2040 struct predicate op_non_const
;
2043 struct agg_position_info aggpos
;
2045 /* What statments might be optimized away
2046 when their arguments are constant. */
2047 if (gimple_code (stmt
) != GIMPLE_ASSIGN
2048 && gimple_code (stmt
) != GIMPLE_COND
2049 && gimple_code (stmt
) != GIMPLE_SWITCH
2050 && (gimple_code (stmt
) != GIMPLE_CALL
2051 || !(gimple_call_flags (stmt
) & ECF_CONST
)))
2054 /* Stores will stay anyway. */
2055 if (gimple_store_p (stmt
))
2058 is_load
= gimple_assign_load_p (stmt
);
2060 /* Loads can be optimized when the value is known. */
2064 gcc_assert (gimple_assign_single_p (stmt
));
2065 op
= gimple_assign_rhs1 (stmt
);
2066 if (!unmodified_parm_or_parm_agg_item (fbi
, stmt
, op
, &base_index
,
2073 /* See if we understand all operands before we start
2074 adding conditionals. */
2075 FOR_EACH_SSA_TREE_OPERAND (use
, stmt
, iter
, SSA_OP_USE
)
2077 tree parm
= unmodified_parm (stmt
, use
);
2078 /* For arguments we can build a condition. */
2079 if (parm
&& ipa_get_param_decl_index (fbi
->info
, parm
) >= 0)
2081 if (TREE_CODE (use
) != SSA_NAME
)
2083 /* If we know when operand is constant,
2084 we still can say something useful. */
2085 if (!true_predicate_p (&nonconstant_names
[SSA_NAME_VERSION (use
)]))
2092 add_condition (summary
, base_index
, &aggpos
, CHANGED
, NULL
);
2094 op_non_const
= false_predicate ();
2095 FOR_EACH_SSA_TREE_OPERAND (use
, stmt
, iter
, SSA_OP_USE
)
2097 tree parm
= unmodified_parm (stmt
, use
);
2100 if (parm
&& (index
= ipa_get_param_decl_index (fbi
->info
, parm
)) >= 0)
2102 if (index
!= base_index
)
2103 p
= add_condition (summary
, index
, NULL
, CHANGED
, NULL_TREE
);
2108 p
= nonconstant_names
[SSA_NAME_VERSION (use
)];
2109 op_non_const
= or_predicates (summary
->conds
, &p
, &op_non_const
);
2111 if ((gimple_code (stmt
) == GIMPLE_ASSIGN
|| gimple_code (stmt
) == GIMPLE_CALL
)
2112 && gimple_op (stmt
, 0)
2113 && TREE_CODE (gimple_op (stmt
, 0)) == SSA_NAME
)
2114 nonconstant_names
[SSA_NAME_VERSION (gimple_op (stmt
, 0))]
2116 return op_non_const
;
2119 struct record_modified_bb_info
2125 /* Callback of walk_aliased_vdefs. Records basic blocks where the value may be
2126 set except for info->stmt. */
2129 record_modified (ao_ref
*ao ATTRIBUTE_UNUSED
, tree vdef
, void *data
)
2131 struct record_modified_bb_info
*info
=
2132 (struct record_modified_bb_info
*) data
;
2133 if (SSA_NAME_DEF_STMT (vdef
) == info
->stmt
)
2135 bitmap_set_bit (info
->bb_set
,
2136 SSA_NAME_IS_DEFAULT_DEF (vdef
)
2137 ? ENTRY_BLOCK_PTR_FOR_FN (cfun
)->index
2138 : gimple_bb (SSA_NAME_DEF_STMT (vdef
))->index
);
2142 /* Return probability (based on REG_BR_PROB_BASE) that I-th parameter of STMT
2143 will change since last invocation of STMT.
2145 Value 0 is reserved for compile time invariants.
2146 For common parameters it is REG_BR_PROB_BASE. For loop invariants it
2147 ought to be REG_BR_PROB_BASE / estimated_iters. */
2150 param_change_prob (gimple
*stmt
, int i
)
2152 tree op
= gimple_call_arg (stmt
, i
);
2153 basic_block bb
= gimple_bb (stmt
);
2156 /* Global invariants neve change. */
2157 if (is_gimple_min_invariant (op
))
2159 /* We would have to do non-trivial analysis to really work out what
2160 is the probability of value to change (i.e. when init statement
2161 is in a sibling loop of the call).
2163 We do an conservative estimate: when call is executed N times more often
2164 than the statement defining value, we take the frequency 1/N. */
2165 if (TREE_CODE (op
) == SSA_NAME
)
2170 return REG_BR_PROB_BASE
;
2172 if (SSA_NAME_IS_DEFAULT_DEF (op
))
2173 init_freq
= ENTRY_BLOCK_PTR_FOR_FN (cfun
)->frequency
;
2175 init_freq
= gimple_bb (SSA_NAME_DEF_STMT (op
))->frequency
;
2179 if (init_freq
< bb
->frequency
)
2180 return MAX (GCOV_COMPUTE_SCALE (init_freq
, bb
->frequency
), 1);
2182 return REG_BR_PROB_BASE
;
2185 base
= get_base_address (op
);
2190 struct record_modified_bb_info info
;
2193 tree init
= ctor_for_folding (base
);
2195 if (init
!= error_mark_node
)
2198 return REG_BR_PROB_BASE
;
2199 ao_ref_init (&refd
, op
);
2201 info
.bb_set
= BITMAP_ALLOC (NULL
);
2202 walk_aliased_vdefs (&refd
, gimple_vuse (stmt
), record_modified
, &info
,
2204 if (bitmap_bit_p (info
.bb_set
, bb
->index
))
2206 BITMAP_FREE (info
.bb_set
);
2207 return REG_BR_PROB_BASE
;
2210 /* Assume that every memory is initialized at entry.
2211 TODO: Can we easilly determine if value is always defined
2212 and thus we may skip entry block? */
2213 if (ENTRY_BLOCK_PTR_FOR_FN (cfun
)->frequency
)
2214 max
= ENTRY_BLOCK_PTR_FOR_FN (cfun
)->frequency
;
2218 EXECUTE_IF_SET_IN_BITMAP (info
.bb_set
, 0, index
, bi
)
2219 max
= MIN (max
, BASIC_BLOCK_FOR_FN (cfun
, index
)->frequency
);
2221 BITMAP_FREE (info
.bb_set
);
2222 if (max
< bb
->frequency
)
2223 return MAX (GCOV_COMPUTE_SCALE (max
, bb
->frequency
), 1);
2225 return REG_BR_PROB_BASE
;
2227 return REG_BR_PROB_BASE
;
2230 /* Find whether a basic block BB is the final block of a (half) diamond CFG
2231 sub-graph and if the predicate the condition depends on is known. If so,
2232 return true and store the pointer the predicate in *P. */
2235 phi_result_unknown_predicate (struct ipa_node_params
*info
,
2236 inline_summary
*summary
, basic_block bb
,
2237 struct predicate
*p
,
2238 vec
<predicate_t
> nonconstant_names
)
2242 basic_block first_bb
= NULL
;
2245 if (single_pred_p (bb
))
2247 *p
= false_predicate ();
2251 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
2253 if (single_succ_p (e
->src
))
2255 if (!single_pred_p (e
->src
))
2258 first_bb
= single_pred (e
->src
);
2259 else if (single_pred (e
->src
) != first_bb
)
2266 else if (e
->src
!= first_bb
)
2274 stmt
= last_stmt (first_bb
);
2276 || gimple_code (stmt
) != GIMPLE_COND
2277 || !is_gimple_ip_invariant (gimple_cond_rhs (stmt
)))
2280 *p
= will_be_nonconstant_expr_predicate (info
, summary
,
2281 gimple_cond_lhs (stmt
),
2283 if (true_predicate_p (p
))
2289 /* Given a PHI statement in a function described by inline properties SUMMARY
2290 and *P being the predicate describing whether the selected PHI argument is
2291 known, store a predicate for the result of the PHI statement into
2292 NONCONSTANT_NAMES, if possible. */
2295 predicate_for_phi_result (struct inline_summary
*summary
, gphi
*phi
,
2296 struct predicate
*p
,
2297 vec
<predicate_t
> nonconstant_names
)
2301 for (i
= 0; i
< gimple_phi_num_args (phi
); i
++)
2303 tree arg
= gimple_phi_arg (phi
, i
)->def
;
2304 if (!is_gimple_min_invariant (arg
))
2306 gcc_assert (TREE_CODE (arg
) == SSA_NAME
);
2307 *p
= or_predicates (summary
->conds
, p
,
2308 &nonconstant_names
[SSA_NAME_VERSION (arg
)]);
2309 if (true_predicate_p (p
))
2314 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2316 fprintf (dump_file
, "\t\tphi predicate: ");
2317 dump_predicate (dump_file
, summary
->conds
, p
);
2319 nonconstant_names
[SSA_NAME_VERSION (gimple_phi_result (phi
))] = *p
;
2322 /* Return predicate specifying when array index in access OP becomes non-constant. */
2324 static struct predicate
2325 array_index_predicate (inline_summary
*info
,
2326 vec
< predicate_t
> nonconstant_names
, tree op
)
2328 struct predicate p
= false_predicate ();
2329 while (handled_component_p (op
))
2331 if (TREE_CODE (op
) == ARRAY_REF
|| TREE_CODE (op
) == ARRAY_RANGE_REF
)
2333 if (TREE_CODE (TREE_OPERAND (op
, 1)) == SSA_NAME
)
2334 p
= or_predicates (info
->conds
, &p
,
2335 &nonconstant_names
[SSA_NAME_VERSION
2336 (TREE_OPERAND (op
, 1))]);
2338 op
= TREE_OPERAND (op
, 0);
2343 /* For a typical usage of __builtin_expect (a<b, 1), we
2344 may introduce an extra relation stmt:
2345 With the builtin, we have
2348 t3 = __builtin_expect (t2, 1);
2351 Without the builtin, we have
2354 This affects the size/time estimation and may have
2355 an impact on the earlier inlining.
2356 Here find this pattern and fix it up later. */
2359 find_foldable_builtin_expect (basic_block bb
)
2361 gimple_stmt_iterator bsi
;
2363 for (bsi
= gsi_start_bb (bb
); !gsi_end_p (bsi
); gsi_next (&bsi
))
2365 gimple
*stmt
= gsi_stmt (bsi
);
2366 if (gimple_call_builtin_p (stmt
, BUILT_IN_EXPECT
)
2367 || (is_gimple_call (stmt
)
2368 && gimple_call_internal_p (stmt
)
2369 && gimple_call_internal_fn (stmt
) == IFN_BUILTIN_EXPECT
))
2371 tree var
= gimple_call_lhs (stmt
);
2372 tree arg
= gimple_call_arg (stmt
, 0);
2373 use_operand_p use_p
;
2380 gcc_assert (TREE_CODE (var
) == SSA_NAME
);
2382 while (TREE_CODE (arg
) == SSA_NAME
)
2384 gimple
*stmt_tmp
= SSA_NAME_DEF_STMT (arg
);
2385 if (!is_gimple_assign (stmt_tmp
))
2387 switch (gimple_assign_rhs_code (stmt_tmp
))
2406 arg
= gimple_assign_rhs1 (stmt_tmp
);
2409 if (match
&& single_imm_use (var
, &use_p
, &use_stmt
)
2410 && gimple_code (use_stmt
) == GIMPLE_COND
)
2417 /* Return true when the basic blocks contains only clobbers followed by RESX.
2418 Such BBs are kept around to make removal of dead stores possible with
2419 presence of EH and will be optimized out by optimize_clobbers later in the
2422 NEED_EH is used to recurse in case the clobber has non-EH predecestors
2423 that can be clobber only, too.. When it is false, the RESX is not necessary
2424 on the end of basic block. */
2427 clobber_only_eh_bb_p (basic_block bb
, bool need_eh
= true)
2429 gimple_stmt_iterator gsi
= gsi_last_bb (bb
);
2435 if (gsi_end_p (gsi
))
2437 if (gimple_code (gsi_stmt (gsi
)) != GIMPLE_RESX
)
2441 else if (!single_succ_p (bb
))
2444 for (; !gsi_end_p (gsi
); gsi_prev (&gsi
))
2446 gimple
*stmt
= gsi_stmt (gsi
);
2447 if (is_gimple_debug (stmt
))
2449 if (gimple_clobber_p (stmt
))
2451 if (gimple_code (stmt
) == GIMPLE_LABEL
)
2456 /* See if all predecestors are either throws or clobber only BBs. */
2457 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
2458 if (!(e
->flags
& EDGE_EH
)
2459 && !clobber_only_eh_bb_p (e
->src
, false))
2465 /* Compute function body size parameters for NODE.
2466 When EARLY is true, we compute only simple summaries without
2467 non-trivial predicates to drive the early inliner. */
2470 estimate_function_body_sizes (struct cgraph_node
*node
, bool early
)
2473 /* Estimate static overhead for function prologue/epilogue and alignment. */
2475 /* Benefits are scaled by probability of elimination that is in range
2478 struct function
*my_function
= DECL_STRUCT_FUNCTION (node
->decl
);
2480 struct inline_summary
*info
= inline_summaries
->get (node
);
2481 struct predicate bb_predicate
;
2482 struct ipa_func_body_info fbi
;
2483 vec
<predicate_t
> nonconstant_names
= vNULL
;
2486 predicate array_index
= true_predicate ();
2487 gimple
*fix_builtin_expect_stmt
;
2489 gcc_assert (my_function
&& my_function
->cfg
);
2490 gcc_assert (cfun
== my_function
);
2492 memset(&fbi
, 0, sizeof(fbi
));
2496 /* When optimizing and analyzing for IPA inliner, initialize loop optimizer
2497 so we can produce proper inline hints.
2499 When optimizing and analyzing for early inliner, initialize node params
2500 so we can produce correct BB predicates. */
2502 if (opt_for_fn (node
->decl
, optimize
))
2504 calculate_dominance_info (CDI_DOMINATORS
);
2506 loop_optimizer_init (LOOPS_NORMAL
| LOOPS_HAVE_RECORDED_EXITS
);
2509 ipa_check_create_node_params ();
2510 ipa_initialize_node_params (node
);
2513 if (ipa_node_params_sum
)
2516 fbi
.info
= IPA_NODE_REF (node
);
2517 fbi
.bb_infos
= vNULL
;
2518 fbi
.bb_infos
.safe_grow_cleared (last_basic_block_for_fn (cfun
));
2519 fbi
.param_count
= count_formal_params(node
->decl
);
2520 nonconstant_names
.safe_grow_cleared
2521 (SSANAMES (my_function
)->length ());
2526 fprintf (dump_file
, "\nAnalyzing function body size: %s\n",
2529 /* When we run into maximal number of entries, we assign everything to the
2530 constant truth case. Be sure to have it in list. */
2531 bb_predicate
= true_predicate ();
2532 account_size_time (info
, 0, 0, &bb_predicate
);
2534 bb_predicate
= not_inlined_predicate ();
2535 account_size_time (info
, 2 * INLINE_SIZE_SCALE
, 0, &bb_predicate
);
2538 compute_bb_predicates (&fbi
, node
, info
);
2539 order
= XNEWVEC (int, n_basic_blocks_for_fn (cfun
));
2540 nblocks
= pre_and_rev_post_order_compute (NULL
, order
, false);
2541 for (n
= 0; n
< nblocks
; n
++)
2543 bb
= BASIC_BLOCK_FOR_FN (cfun
, order
[n
]);
2544 freq
= compute_call_stmt_bb_frequency (node
->decl
, bb
);
2545 if (clobber_only_eh_bb_p (bb
))
2547 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2548 fprintf (dump_file
, "\n Ignoring BB %i;"
2549 " it will be optimized away by cleanup_clobbers\n",
2554 /* TODO: Obviously predicates can be propagated down across CFG. */
2558 bb_predicate
= *(struct predicate
*) bb
->aux
;
2560 bb_predicate
= false_predicate ();
2563 bb_predicate
= true_predicate ();
2565 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2567 fprintf (dump_file
, "\n BB %i predicate:", bb
->index
);
2568 dump_predicate (dump_file
, info
->conds
, &bb_predicate
);
2571 if (fbi
.info
&& nonconstant_names
.exists ())
2573 struct predicate phi_predicate
;
2574 bool first_phi
= true;
2576 for (gphi_iterator bsi
= gsi_start_phis (bb
); !gsi_end_p (bsi
);
2580 && !phi_result_unknown_predicate (fbi
.info
, info
, bb
,
2585 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2587 fprintf (dump_file
, " ");
2588 print_gimple_stmt (dump_file
, gsi_stmt (bsi
), 0, 0);
2590 predicate_for_phi_result (info
, bsi
.phi (), &phi_predicate
,
2595 fix_builtin_expect_stmt
= find_foldable_builtin_expect (bb
);
2597 for (gimple_stmt_iterator bsi
= gsi_start_bb (bb
); !gsi_end_p (bsi
);
2600 gimple
*stmt
= gsi_stmt (bsi
);
2601 int this_size
= estimate_num_insns (stmt
, &eni_size_weights
);
2602 int this_time
= estimate_num_insns (stmt
, &eni_time_weights
);
2604 struct predicate will_be_nonconstant
;
2606 /* This relation stmt should be folded after we remove
2607 buildin_expect call. Adjust the cost here. */
2608 if (stmt
== fix_builtin_expect_stmt
)
2614 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2616 fprintf (dump_file
, " ");
2617 print_gimple_stmt (dump_file
, stmt
, 0, 0);
2618 fprintf (dump_file
, "\t\tfreq:%3.2f size:%3i time:%3i\n",
2619 ((double) freq
) / CGRAPH_FREQ_BASE
, this_size
,
2623 if (gimple_assign_load_p (stmt
) && nonconstant_names
.exists ())
2625 struct predicate this_array_index
;
2627 array_index_predicate (info
, nonconstant_names
,
2628 gimple_assign_rhs1 (stmt
));
2629 if (!false_predicate_p (&this_array_index
))
2631 and_predicates (info
->conds
, &array_index
,
2634 if (gimple_store_p (stmt
) && nonconstant_names
.exists ())
2636 struct predicate this_array_index
;
2638 array_index_predicate (info
, nonconstant_names
,
2639 gimple_get_lhs (stmt
));
2640 if (!false_predicate_p (&this_array_index
))
2642 and_predicates (info
->conds
, &array_index
,
2647 if (is_gimple_call (stmt
)
2648 && !gimple_call_internal_p (stmt
))
2650 struct cgraph_edge
*edge
= node
->get_edge (stmt
);
2651 struct inline_edge_summary
*es
= inline_edge_summary (edge
);
2653 /* Special case: results of BUILT_IN_CONSTANT_P will be always
2654 resolved as constant. We however don't want to optimize
2655 out the cgraph edges. */
2656 if (nonconstant_names
.exists ()
2657 && gimple_call_builtin_p (stmt
, BUILT_IN_CONSTANT_P
)
2658 && gimple_call_lhs (stmt
)
2659 && TREE_CODE (gimple_call_lhs (stmt
)) == SSA_NAME
)
2661 struct predicate false_p
= false_predicate ();
2662 nonconstant_names
[SSA_NAME_VERSION (gimple_call_lhs (stmt
))]
2665 if (ipa_node_params_sum
)
2667 int count
= gimple_call_num_args (stmt
);
2671 es
->param
.safe_grow_cleared (count
);
2672 for (i
= 0; i
< count
; i
++)
2674 int prob
= param_change_prob (stmt
, i
);
2675 gcc_assert (prob
>= 0 && prob
<= REG_BR_PROB_BASE
);
2676 es
->param
[i
].change_prob
= prob
;
2680 es
->call_stmt_size
= this_size
;
2681 es
->call_stmt_time
= this_time
;
2682 es
->loop_depth
= bb_loop_depth (bb
);
2683 edge_set_predicate (edge
, &bb_predicate
);
2686 /* TODO: When conditional jump or swithc is known to be constant, but
2687 we did not translate it into the predicates, we really can account
2688 just maximum of the possible paths. */
2691 = will_be_nonconstant_predicate (&fbi
, info
,
2692 stmt
, nonconstant_names
);
2693 if (this_time
|| this_size
)
2699 prob
= eliminated_by_inlining_prob (stmt
);
2700 if (prob
== 1 && dump_file
&& (dump_flags
& TDF_DETAILS
))
2702 "\t\t50%% will be eliminated by inlining\n");
2703 if (prob
== 2 && dump_file
&& (dump_flags
& TDF_DETAILS
))
2704 fprintf (dump_file
, "\t\tWill be eliminated by inlining\n");
2707 p
= and_predicates (info
->conds
, &bb_predicate
,
2708 &will_be_nonconstant
);
2710 p
= true_predicate ();
2712 if (!false_predicate_p (&p
)
2713 || (is_gimple_call (stmt
)
2714 && !false_predicate_p (&bb_predicate
)))
2718 if (time
> MAX_TIME
* INLINE_TIME_SCALE
)
2719 time
= MAX_TIME
* INLINE_TIME_SCALE
;
2722 /* We account everything but the calls. Calls have their own
2723 size/time info attached to cgraph edges. This is necessary
2724 in order to make the cost disappear after inlining. */
2725 if (!is_gimple_call (stmt
))
2729 struct predicate ip
= not_inlined_predicate ();
2730 ip
= and_predicates (info
->conds
, &ip
, &p
);
2731 account_size_time (info
, this_size
* prob
,
2732 this_time
* prob
, &ip
);
2735 account_size_time (info
, this_size
* (2 - prob
),
2736 this_time
* (2 - prob
), &p
);
2739 gcc_assert (time
>= 0);
2740 gcc_assert (size
>= 0);
2744 set_hint_predicate (&inline_summaries
->get (node
)->array_index
, array_index
);
2745 time
= (time
+ CGRAPH_FREQ_BASE
/ 2) / CGRAPH_FREQ_BASE
;
2746 if (time
> MAX_TIME
)
2750 if (nonconstant_names
.exists () && !early
)
2753 predicate loop_iterations
= true_predicate ();
2754 predicate loop_stride
= true_predicate ();
2756 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2757 flow_loops_dump (dump_file
, NULL
, 0);
2759 FOR_EACH_LOOP (loop
, 0)
2764 struct tree_niter_desc niter_desc
;
2765 bb_predicate
= *(struct predicate
*) loop
->header
->aux
;
2767 exits
= get_loop_exit_edges (loop
);
2768 FOR_EACH_VEC_ELT (exits
, j
, ex
)
2769 if (number_of_iterations_exit (loop
, ex
, &niter_desc
, false)
2770 && !is_gimple_min_invariant (niter_desc
.niter
))
2772 predicate will_be_nonconstant
2773 = will_be_nonconstant_expr_predicate (fbi
.info
, info
,
2776 if (!true_predicate_p (&will_be_nonconstant
))
2777 will_be_nonconstant
= and_predicates (info
->conds
,
2779 &will_be_nonconstant
);
2780 if (!true_predicate_p (&will_be_nonconstant
)
2781 && !false_predicate_p (&will_be_nonconstant
))
2782 /* This is slightly inprecise. We may want to represent each
2783 loop with independent predicate. */
2785 and_predicates (info
->conds
, &loop_iterations
,
2786 &will_be_nonconstant
);
2791 /* To avoid quadratic behavior we analyze stride predicates only
2792 with respect to the containing loop. Thus we simply iterate
2793 over all defs in the outermost loop body. */
2794 for (loop
= loops_for_fn (cfun
)->tree_root
->inner
;
2795 loop
!= NULL
; loop
= loop
->next
)
2797 basic_block
*body
= get_loop_body (loop
);
2798 for (unsigned i
= 0; i
< loop
->num_nodes
; i
++)
2800 gimple_stmt_iterator gsi
;
2801 bb_predicate
= *(struct predicate
*) body
[i
]->aux
;
2802 for (gsi
= gsi_start_bb (body
[i
]); !gsi_end_p (gsi
);
2805 gimple
*stmt
= gsi_stmt (gsi
);
2807 if (!is_gimple_assign (stmt
))
2810 tree def
= gimple_assign_lhs (stmt
);
2811 if (TREE_CODE (def
) != SSA_NAME
)
2815 if (!simple_iv (loop_containing_stmt (stmt
),
2816 loop_containing_stmt (stmt
),
2818 || is_gimple_min_invariant (iv
.step
))
2821 predicate will_be_nonconstant
2822 = will_be_nonconstant_expr_predicate (fbi
.info
, info
,
2825 if (!true_predicate_p (&will_be_nonconstant
))
2827 = and_predicates (info
->conds
, &bb_predicate
,
2828 &will_be_nonconstant
);
2829 if (!true_predicate_p (&will_be_nonconstant
)
2830 && !false_predicate_p (&will_be_nonconstant
))
2831 /* This is slightly inprecise. We may want to represent
2832 each loop with independent predicate. */
2833 loop_stride
= and_predicates (info
->conds
, &loop_stride
,
2834 &will_be_nonconstant
);
2839 set_hint_predicate (&inline_summaries
->get (node
)->loop_iterations
,
2841 set_hint_predicate (&inline_summaries
->get (node
)->loop_stride
,
2845 FOR_ALL_BB_FN (bb
, my_function
)
2851 edge_predicate_pool
.remove ((predicate
*)bb
->aux
);
2853 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
2856 edge_predicate_pool
.remove ((predicate
*) e
->aux
);
2860 inline_summaries
->get (node
)->self_time
= time
;
2861 inline_summaries
->get (node
)->self_size
= size
;
2862 nonconstant_names
.release ();
2863 if (opt_for_fn (node
->decl
, optimize
))
2866 loop_optimizer_finalize ();
2867 else if (!ipa_edge_args_vector
)
2868 ipa_free_all_node_params ();
2869 free_dominance_info (CDI_DOMINATORS
);
2873 fprintf (dump_file
, "\n");
2874 dump_inline_summary (dump_file
, node
);
2879 /* Compute parameters of functions used by inliner.
2880 EARLY is true when we compute parameters for the early inliner */
2883 compute_inline_parameters (struct cgraph_node
*node
, bool early
)
2885 HOST_WIDE_INT self_stack_size
;
2886 struct cgraph_edge
*e
;
2887 struct inline_summary
*info
;
2889 gcc_assert (!node
->global
.inlined_to
);
2891 inline_summary_alloc ();
2893 info
= inline_summaries
->get (node
);
2894 reset_inline_summary (node
, info
);
2896 /* FIXME: Thunks are inlinable, but tree-inline don't know how to do that.
2897 Once this happen, we will need to more curefully predict call
2899 if (node
->thunk
.thunk_p
)
2901 struct inline_edge_summary
*es
= inline_edge_summary (node
->callees
);
2902 struct predicate t
= true_predicate ();
2904 info
->inlinable
= 0;
2905 node
->callees
->call_stmt_cannot_inline_p
= true;
2906 node
->local
.can_change_signature
= false;
2907 es
->call_stmt_time
= 1;
2908 es
->call_stmt_size
= 1;
2909 account_size_time (info
, 0, 0, &t
);
2913 /* Even is_gimple_min_invariant rely on current_function_decl. */
2914 push_cfun (DECL_STRUCT_FUNCTION (node
->decl
));
2916 /* Estimate the stack size for the function if we're optimizing. */
2917 self_stack_size
= optimize
? estimated_stack_frame_size (node
) : 0;
2918 info
->estimated_self_stack_size
= self_stack_size
;
2919 info
->estimated_stack_size
= self_stack_size
;
2920 info
->stack_frame_offset
= 0;
2922 /* Can this function be inlined at all? */
2923 if (!opt_for_fn (node
->decl
, optimize
)
2924 && !lookup_attribute ("always_inline",
2925 DECL_ATTRIBUTES (node
->decl
)))
2926 info
->inlinable
= false;
2928 info
->inlinable
= tree_inlinable_function_p (node
->decl
);
2930 info
->contains_cilk_spawn
= fn_contains_cilk_spawn_p (cfun
);
2932 /* Type attributes can use parameter indices to describe them. */
2933 if (TYPE_ATTRIBUTES (TREE_TYPE (node
->decl
)))
2934 node
->local
.can_change_signature
= false;
2937 /* Otherwise, inlinable functions always can change signature. */
2938 if (info
->inlinable
)
2939 node
->local
.can_change_signature
= true;
2942 /* Functions calling builtin_apply can not change signature. */
2943 for (e
= node
->callees
; e
; e
= e
->next_callee
)
2945 tree
cdecl = e
->callee
->decl
;
2946 if (DECL_BUILT_IN (cdecl)
2947 && DECL_BUILT_IN_CLASS (cdecl) == BUILT_IN_NORMAL
2948 && (DECL_FUNCTION_CODE (cdecl) == BUILT_IN_APPLY_ARGS
2949 || DECL_FUNCTION_CODE (cdecl) == BUILT_IN_VA_START
))
2952 node
->local
.can_change_signature
= !e
;
2955 estimate_function_body_sizes (node
, early
);
2957 for (e
= node
->callees
; e
; e
= e
->next_callee
)
2958 if (e
->callee
->comdat_local_p ())
2960 node
->calls_comdat_local
= (e
!= NULL
);
2962 /* Inlining characteristics are maintained by the cgraph_mark_inline. */
2963 info
->time
= info
->self_time
;
2964 info
->size
= info
->self_size
;
2965 info
->stack_frame_offset
= 0;
2966 info
->estimated_stack_size
= info
->estimated_self_stack_size
;
2967 #ifdef ENABLE_CHECKING
2968 inline_update_overall_summary (node
);
2969 gcc_assert (info
->time
== info
->self_time
&& info
->size
== info
->self_size
);
2976 /* Compute parameters of functions used by inliner using
2977 current_function_decl. */
2980 compute_inline_parameters_for_current (void)
2982 compute_inline_parameters (cgraph_node::get (current_function_decl
), true);
2988 const pass_data pass_data_inline_parameters
=
2990 GIMPLE_PASS
, /* type */
2991 "inline_param", /* name */
2992 OPTGROUP_INLINE
, /* optinfo_flags */
2993 TV_INLINE_PARAMETERS
, /* tv_id */
2994 0, /* properties_required */
2995 0, /* properties_provided */
2996 0, /* properties_destroyed */
2997 0, /* todo_flags_start */
2998 0, /* todo_flags_finish */
3001 class pass_inline_parameters
: public gimple_opt_pass
3004 pass_inline_parameters (gcc::context
*ctxt
)
3005 : gimple_opt_pass (pass_data_inline_parameters
, ctxt
)
3008 /* opt_pass methods: */
3009 opt_pass
* clone () { return new pass_inline_parameters (m_ctxt
); }
3010 virtual unsigned int execute (function
*)
3012 return compute_inline_parameters_for_current ();
3015 }; // class pass_inline_parameters
3020 make_pass_inline_parameters (gcc::context
*ctxt
)
3022 return new pass_inline_parameters (ctxt
);
3026 /* Estimate benefit devirtualizing indirect edge IE, provided KNOWN_VALS,
3027 KNOWN_CONTEXTS and KNOWN_AGGS. */
3030 estimate_edge_devirt_benefit (struct cgraph_edge
*ie
,
3031 int *size
, int *time
,
3032 vec
<tree
> known_vals
,
3033 vec
<ipa_polymorphic_call_context
> known_contexts
,
3034 vec
<ipa_agg_jump_function_p
> known_aggs
)
3037 struct cgraph_node
*callee
;
3038 struct inline_summary
*isummary
;
3039 enum availability avail
;
3042 if (!known_vals
.exists () && !known_contexts
.exists ())
3044 if (!opt_for_fn (ie
->caller
->decl
, flag_indirect_inlining
))
3047 target
= ipa_get_indirect_edge_target (ie
, known_vals
, known_contexts
,
3048 known_aggs
, &speculative
);
3049 if (!target
|| speculative
)
3052 /* Account for difference in cost between indirect and direct calls. */
3053 *size
-= (eni_size_weights
.indirect_call_cost
- eni_size_weights
.call_cost
);
3054 *time
-= (eni_time_weights
.indirect_call_cost
- eni_time_weights
.call_cost
);
3055 gcc_checking_assert (*time
>= 0);
3056 gcc_checking_assert (*size
>= 0);
3058 callee
= cgraph_node::get (target
);
3059 if (!callee
|| !callee
->definition
)
3061 callee
= callee
->function_symbol (&avail
);
3062 if (avail
< AVAIL_AVAILABLE
)
3064 isummary
= inline_summaries
->get (callee
);
3065 return isummary
->inlinable
;
3068 /* Increase SIZE, MIN_SIZE (if non-NULL) and TIME for size and time needed to
3069 handle edge E with probability PROB.
3070 Set HINTS if edge may be devirtualized.
3071 KNOWN_VALS, KNOWN_AGGS and KNOWN_CONTEXTS describe context of the call
3075 estimate_edge_size_and_time (struct cgraph_edge
*e
, int *size
, int *min_size
,
3078 vec
<tree
> known_vals
,
3079 vec
<ipa_polymorphic_call_context
> known_contexts
,
3080 vec
<ipa_agg_jump_function_p
> known_aggs
,
3081 inline_hints
*hints
)
3083 struct inline_edge_summary
*es
= inline_edge_summary (e
);
3084 int call_size
= es
->call_stmt_size
;
3085 int call_time
= es
->call_stmt_time
;
3088 && estimate_edge_devirt_benefit (e
, &call_size
, &call_time
,
3089 known_vals
, known_contexts
, known_aggs
)
3090 && hints
&& e
->maybe_hot_p ())
3091 *hints
|= INLINE_HINT_indirect_call
;
3092 cur_size
= call_size
* INLINE_SIZE_SCALE
;
3095 *min_size
+= cur_size
;
3096 *time
+= apply_probability ((gcov_type
) call_time
, prob
)
3097 * e
->frequency
* (INLINE_TIME_SCALE
/ CGRAPH_FREQ_BASE
);
3098 if (*time
> MAX_TIME
* INLINE_TIME_SCALE
)
3099 *time
= MAX_TIME
* INLINE_TIME_SCALE
;
3104 /* Increase SIZE, MIN_SIZE and TIME for size and time needed to handle all
3105 calls in NODE. POSSIBLE_TRUTHS, KNOWN_VALS, KNOWN_AGGS and KNOWN_CONTEXTS
3106 describe context of the call site. */
3109 estimate_calls_size_and_time (struct cgraph_node
*node
, int *size
,
3110 int *min_size
, int *time
,
3111 inline_hints
*hints
,
3112 clause_t possible_truths
,
3113 vec
<tree
> known_vals
,
3114 vec
<ipa_polymorphic_call_context
> known_contexts
,
3115 vec
<ipa_agg_jump_function_p
> known_aggs
)
3117 struct cgraph_edge
*e
;
3118 for (e
= node
->callees
; e
; e
= e
->next_callee
)
3120 if (inline_edge_summary_vec
.length () <= (unsigned) e
->uid
)
3123 struct inline_edge_summary
*es
= inline_edge_summary (e
);
3125 /* Do not care about zero sized builtins. */
3126 if (e
->inline_failed
&& !es
->call_stmt_size
)
3128 gcc_checking_assert (!es
->call_stmt_time
);
3132 || evaluate_predicate (es
->predicate
, possible_truths
))
3134 if (e
->inline_failed
)
3136 /* Predicates of calls shall not use NOT_CHANGED codes,
3137 sowe do not need to compute probabilities. */
3138 estimate_edge_size_and_time (e
, size
,
3139 es
->predicate
? NULL
: min_size
,
3140 time
, REG_BR_PROB_BASE
,
3141 known_vals
, known_contexts
,
3145 estimate_calls_size_and_time (e
->callee
, size
, min_size
, time
,
3148 known_vals
, known_contexts
,
3152 for (e
= node
->indirect_calls
; e
; e
= e
->next_callee
)
3154 if (inline_edge_summary_vec
.length () <= (unsigned) e
->uid
)
3157 struct inline_edge_summary
*es
= inline_edge_summary (e
);
3159 || evaluate_predicate (es
->predicate
, possible_truths
))
3160 estimate_edge_size_and_time (e
, size
,
3161 es
->predicate
? NULL
: min_size
,
3162 time
, REG_BR_PROB_BASE
,
3163 known_vals
, known_contexts
, known_aggs
,
3169 /* Estimate size and time needed to execute NODE assuming
3170 POSSIBLE_TRUTHS clause, and KNOWN_VALS, KNOWN_AGGS and KNOWN_CONTEXTS
3171 information about NODE's arguments. If non-NULL use also probability
3172 information present in INLINE_PARAM_SUMMARY vector.
3173 Additionally detemine hints determined by the context. Finally compute
3174 minimal size needed for the call that is independent on the call context and
3175 can be used for fast estimates. Return the values in RET_SIZE,
3176 RET_MIN_SIZE, RET_TIME and RET_HINTS. */
3179 estimate_node_size_and_time (struct cgraph_node
*node
,
3180 clause_t possible_truths
,
3181 vec
<tree
> known_vals
,
3182 vec
<ipa_polymorphic_call_context
> known_contexts
,
3183 vec
<ipa_agg_jump_function_p
> known_aggs
,
3184 int *ret_size
, int *ret_min_size
, int *ret_time
,
3185 inline_hints
*ret_hints
,
3186 vec
<inline_param_summary
>
3187 inline_param_summary
)
3189 struct inline_summary
*info
= inline_summaries
->get (node
);
3194 inline_hints hints
= 0;
3197 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3200 fprintf (dump_file
, " Estimating body: %s/%i\n"
3201 " Known to be false: ", node
->name (),
3204 for (i
= predicate_not_inlined_condition
;
3205 i
< (predicate_first_dynamic_condition
3206 + (int) vec_safe_length (info
->conds
)); i
++)
3207 if (!(possible_truths
& (1 << i
)))
3210 fprintf (dump_file
, ", ");
3212 dump_condition (dump_file
, info
->conds
, i
);
3216 for (i
= 0; vec_safe_iterate (info
->entry
, i
, &e
); i
++)
3217 if (evaluate_predicate (&e
->predicate
, possible_truths
))
3220 gcc_checking_assert (e
->time
>= 0);
3221 gcc_checking_assert (time
>= 0);
3222 if (!inline_param_summary
.exists ())
3226 int prob
= predicate_probability (info
->conds
,
3229 inline_param_summary
);
3230 gcc_checking_assert (prob
>= 0);
3231 gcc_checking_assert (prob
<= REG_BR_PROB_BASE
);
3232 time
+= apply_probability ((gcov_type
) e
->time
, prob
);
3234 if (time
> MAX_TIME
* INLINE_TIME_SCALE
)
3235 time
= MAX_TIME
* INLINE_TIME_SCALE
;
3236 gcc_checking_assert (time
>= 0);
3239 gcc_checking_assert (true_predicate_p (&(*info
->entry
)[0].predicate
));
3240 min_size
= (*info
->entry
)[0].size
;
3241 gcc_checking_assert (size
>= 0);
3242 gcc_checking_assert (time
>= 0);
3244 if (info
->loop_iterations
3245 && !evaluate_predicate (info
->loop_iterations
, possible_truths
))
3246 hints
|= INLINE_HINT_loop_iterations
;
3247 if (info
->loop_stride
3248 && !evaluate_predicate (info
->loop_stride
, possible_truths
))
3249 hints
|= INLINE_HINT_loop_stride
;
3250 if (info
->array_index
3251 && !evaluate_predicate (info
->array_index
, possible_truths
))
3252 hints
|= INLINE_HINT_array_index
;
3254 hints
|= INLINE_HINT_in_scc
;
3255 if (DECL_DECLARED_INLINE_P (node
->decl
))
3256 hints
|= INLINE_HINT_declared_inline
;
3258 estimate_calls_size_and_time (node
, &size
, &min_size
, &time
, &hints
, possible_truths
,
3259 known_vals
, known_contexts
, known_aggs
);
3260 gcc_checking_assert (size
>= 0);
3261 gcc_checking_assert (time
>= 0);
3262 time
= RDIV (time
, INLINE_TIME_SCALE
);
3263 size
= RDIV (size
, INLINE_SIZE_SCALE
);
3264 min_size
= RDIV (min_size
, INLINE_SIZE_SCALE
);
3266 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3267 fprintf (dump_file
, "\n size:%i time:%i\n", (int) size
, (int) time
);
3273 *ret_min_size
= min_size
;
3280 /* Estimate size and time needed to execute callee of EDGE assuming that
3281 parameters known to be constant at caller of EDGE are propagated.
3282 KNOWN_VALS and KNOWN_CONTEXTS are vectors of assumed known constant values
3283 and types for parameters. */
3286 estimate_ipcp_clone_size_and_time (struct cgraph_node
*node
,
3287 vec
<tree
> known_vals
,
3288 vec
<ipa_polymorphic_call_context
>
3290 vec
<ipa_agg_jump_function_p
> known_aggs
,
3291 int *ret_size
, int *ret_time
,
3292 inline_hints
*hints
)
3296 clause
= evaluate_conditions_for_known_args (node
, false, known_vals
,
3298 estimate_node_size_and_time (node
, clause
, known_vals
, known_contexts
,
3299 known_aggs
, ret_size
, NULL
, ret_time
, hints
, vNULL
);
3302 /* Translate all conditions from callee representation into caller
3303 representation and symbolically evaluate predicate P into new predicate.
3305 INFO is inline_summary of function we are adding predicate into, CALLEE_INFO
3306 is summary of function predicate P is from. OPERAND_MAP is array giving
3307 callee formal IDs the caller formal IDs. POSSSIBLE_TRUTHS is clausule of all
3308 callee conditions that may be true in caller context. TOPLEV_PREDICATE is
3309 predicate under which callee is executed. OFFSET_MAP is an array of of
3310 offsets that need to be added to conditions, negative offset means that
3311 conditions relying on values passed by reference have to be discarded
3312 because they might not be preserved (and should be considered offset zero
3313 for other purposes). */
3315 static struct predicate
3316 remap_predicate (struct inline_summary
*info
,
3317 struct inline_summary
*callee_info
,
3318 struct predicate
*p
,
3319 vec
<int> operand_map
,
3320 vec
<int> offset_map
,
3321 clause_t possible_truths
, struct predicate
*toplev_predicate
)
3324 struct predicate out
= true_predicate ();
3326 /* True predicate is easy. */
3327 if (true_predicate_p (p
))
3328 return *toplev_predicate
;
3329 for (i
= 0; p
->clause
[i
]; i
++)
3331 clause_t clause
= p
->clause
[i
];
3333 struct predicate clause_predicate
= false_predicate ();
3335 gcc_assert (i
< MAX_CLAUSES
);
3337 for (cond
= 0; cond
< NUM_CONDITIONS
; cond
++)
3338 /* Do we have condition we can't disprove? */
3339 if (clause
& possible_truths
& (1 << cond
))
3341 struct predicate cond_predicate
;
3342 /* Work out if the condition can translate to predicate in the
3343 inlined function. */
3344 if (cond
>= predicate_first_dynamic_condition
)
3346 struct condition
*c
;
3348 c
= &(*callee_info
->conds
)[cond
3350 predicate_first_dynamic_condition
];
3351 /* See if we can remap condition operand to caller's operand.
3352 Otherwise give up. */
3353 if (!operand_map
.exists ()
3354 || (int) operand_map
.length () <= c
->operand_num
3355 || operand_map
[c
->operand_num
] == -1
3356 /* TODO: For non-aggregate conditions, adding an offset is
3357 basically an arithmetic jump function processing which
3358 we should support in future. */
3359 || ((!c
->agg_contents
|| !c
->by_ref
)
3360 && offset_map
[c
->operand_num
] > 0)
3361 || (c
->agg_contents
&& c
->by_ref
3362 && offset_map
[c
->operand_num
] < 0))
3363 cond_predicate
= true_predicate ();
3366 struct agg_position_info ap
;
3367 HOST_WIDE_INT offset_delta
= offset_map
[c
->operand_num
];
3368 if (offset_delta
< 0)
3370 gcc_checking_assert (!c
->agg_contents
|| !c
->by_ref
);
3373 gcc_assert (!c
->agg_contents
3374 || c
->by_ref
|| offset_delta
== 0);
3375 ap
.offset
= c
->offset
+ offset_delta
;
3376 ap
.agg_contents
= c
->agg_contents
;
3377 ap
.by_ref
= c
->by_ref
;
3378 cond_predicate
= add_condition (info
,
3379 operand_map
[c
->operand_num
],
3380 &ap
, c
->code
, c
->val
);
3383 /* Fixed conditions remains same, construct single
3384 condition predicate. */
3387 cond_predicate
.clause
[0] = 1 << cond
;
3388 cond_predicate
.clause
[1] = 0;
3390 clause_predicate
= or_predicates (info
->conds
, &clause_predicate
,
3393 out
= and_predicates (info
->conds
, &out
, &clause_predicate
);
3395 return and_predicates (info
->conds
, &out
, toplev_predicate
);
3399 /* Update summary information of inline clones after inlining.
3400 Compute peak stack usage. */
3403 inline_update_callee_summaries (struct cgraph_node
*node
, int depth
)
3405 struct cgraph_edge
*e
;
3406 struct inline_summary
*callee_info
= inline_summaries
->get (node
);
3407 struct inline_summary
*caller_info
= inline_summaries
->get (node
->callers
->caller
);
3410 callee_info
->stack_frame_offset
3411 = caller_info
->stack_frame_offset
3412 + caller_info
->estimated_self_stack_size
;
3413 peak
= callee_info
->stack_frame_offset
3414 + callee_info
->estimated_self_stack_size
;
3415 if (inline_summaries
->get (node
->global
.inlined_to
)->estimated_stack_size
< peak
)
3416 inline_summaries
->get (node
->global
.inlined_to
)->estimated_stack_size
= peak
;
3417 ipa_propagate_frequency (node
);
3418 for (e
= node
->callees
; e
; e
= e
->next_callee
)
3420 if (!e
->inline_failed
)
3421 inline_update_callee_summaries (e
->callee
, depth
);
3422 inline_edge_summary (e
)->loop_depth
+= depth
;
3424 for (e
= node
->indirect_calls
; e
; e
= e
->next_callee
)
3425 inline_edge_summary (e
)->loop_depth
+= depth
;
3428 /* Update change_prob of EDGE after INLINED_EDGE has been inlined.
3429 When functoin A is inlined in B and A calls C with parameter that
3430 changes with probability PROB1 and C is known to be passthroug
3431 of argument if B that change with probability PROB2, the probability
3432 of change is now PROB1*PROB2. */
3435 remap_edge_change_prob (struct cgraph_edge
*inlined_edge
,
3436 struct cgraph_edge
*edge
)
3438 if (ipa_node_params_sum
)
3441 struct ipa_edge_args
*args
= IPA_EDGE_REF (edge
);
3442 struct inline_edge_summary
*es
= inline_edge_summary (edge
);
3443 struct inline_edge_summary
*inlined_es
3444 = inline_edge_summary (inlined_edge
);
3446 for (i
= 0; i
< ipa_get_cs_argument_count (args
); i
++)
3448 struct ipa_jump_func
*jfunc
= ipa_get_ith_jump_func (args
, i
);
3449 if (jfunc
->type
== IPA_JF_PASS_THROUGH
3450 && (ipa_get_jf_pass_through_formal_id (jfunc
)
3451 < (int) inlined_es
->param
.length ()))
3453 int jf_formal_id
= ipa_get_jf_pass_through_formal_id (jfunc
);
3454 int prob1
= es
->param
[i
].change_prob
;
3455 int prob2
= inlined_es
->param
[jf_formal_id
].change_prob
;
3456 int prob
= combine_probabilities (prob1
, prob2
);
3458 if (prob1
&& prob2
&& !prob
)
3461 es
->param
[i
].change_prob
= prob
;
3467 /* Update edge summaries of NODE after INLINED_EDGE has been inlined.
3469 Remap predicates of callees of NODE. Rest of arguments match
3472 Also update change probabilities. */
3475 remap_edge_summaries (struct cgraph_edge
*inlined_edge
,
3476 struct cgraph_node
*node
,
3477 struct inline_summary
*info
,
3478 struct inline_summary
*callee_info
,
3479 vec
<int> operand_map
,
3480 vec
<int> offset_map
,
3481 clause_t possible_truths
,
3482 struct predicate
*toplev_predicate
)
3484 struct cgraph_edge
*e
, *next
;
3485 for (e
= node
->callees
; e
; e
= next
)
3487 struct inline_edge_summary
*es
= inline_edge_summary (e
);
3489 next
= e
->next_callee
;
3491 if (e
->inline_failed
)
3493 remap_edge_change_prob (inlined_edge
, e
);
3497 p
= remap_predicate (info
, callee_info
,
3498 es
->predicate
, operand_map
, offset_map
,
3499 possible_truths
, toplev_predicate
);
3500 edge_set_predicate (e
, &p
);
3503 edge_set_predicate (e
, toplev_predicate
);
3506 remap_edge_summaries (inlined_edge
, e
->callee
, info
, callee_info
,
3507 operand_map
, offset_map
, possible_truths
,
3510 for (e
= node
->indirect_calls
; e
; e
= next
)
3512 struct inline_edge_summary
*es
= inline_edge_summary (e
);
3514 next
= e
->next_callee
;
3516 remap_edge_change_prob (inlined_edge
, e
);
3519 p
= remap_predicate (info
, callee_info
,
3520 es
->predicate
, operand_map
, offset_map
,
3521 possible_truths
, toplev_predicate
);
3522 edge_set_predicate (e
, &p
);
3525 edge_set_predicate (e
, toplev_predicate
);
3529 /* Same as remap_predicate, but set result into hint *HINT. */
3532 remap_hint_predicate (struct inline_summary
*info
,
3533 struct inline_summary
*callee_info
,
3534 struct predicate
**hint
,
3535 vec
<int> operand_map
,
3536 vec
<int> offset_map
,
3537 clause_t possible_truths
,
3538 struct predicate
*toplev_predicate
)
3544 p
= remap_predicate (info
, callee_info
,
3546 operand_map
, offset_map
,
3547 possible_truths
, toplev_predicate
);
3548 if (!false_predicate_p (&p
) && !true_predicate_p (&p
))
3551 set_hint_predicate (hint
, p
);
3553 **hint
= and_predicates (info
->conds
, *hint
, &p
);
3557 /* We inlined EDGE. Update summary of the function we inlined into. */
3560 inline_merge_summary (struct cgraph_edge
*edge
)
3562 struct inline_summary
*callee_info
= inline_summaries
->get (edge
->callee
);
3563 struct cgraph_node
*to
= (edge
->caller
->global
.inlined_to
3564 ? edge
->caller
->global
.inlined_to
: edge
->caller
);
3565 struct inline_summary
*info
= inline_summaries
->get (to
);
3566 clause_t clause
= 0; /* not_inline is known to be false. */
3568 vec
<int> operand_map
= vNULL
;
3569 vec
<int> offset_map
= vNULL
;
3571 struct predicate toplev_predicate
;
3572 struct predicate true_p
= true_predicate ();
3573 struct inline_edge_summary
*es
= inline_edge_summary (edge
);
3576 toplev_predicate
= *es
->predicate
;
3578 toplev_predicate
= true_predicate ();
3580 if (callee_info
->conds
)
3581 evaluate_properties_for_edge (edge
, true, &clause
, NULL
, NULL
, NULL
);
3582 if (ipa_node_params_sum
&& callee_info
->conds
)
3584 struct ipa_edge_args
*args
= IPA_EDGE_REF (edge
);
3585 int count
= ipa_get_cs_argument_count (args
);
3590 operand_map
.safe_grow_cleared (count
);
3591 offset_map
.safe_grow_cleared (count
);
3593 for (i
= 0; i
< count
; i
++)
3595 struct ipa_jump_func
*jfunc
= ipa_get_ith_jump_func (args
, i
);
3598 /* TODO: handle non-NOPs when merging. */
3599 if (jfunc
->type
== IPA_JF_PASS_THROUGH
)
3601 if (ipa_get_jf_pass_through_operation (jfunc
) == NOP_EXPR
)
3602 map
= ipa_get_jf_pass_through_formal_id (jfunc
);
3603 if (!ipa_get_jf_pass_through_agg_preserved (jfunc
))
3606 else if (jfunc
->type
== IPA_JF_ANCESTOR
)
3608 HOST_WIDE_INT offset
= ipa_get_jf_ancestor_offset (jfunc
);
3609 if (offset
>= 0 && offset
< INT_MAX
)
3611 map
= ipa_get_jf_ancestor_formal_id (jfunc
);
3612 if (!ipa_get_jf_ancestor_agg_preserved (jfunc
))
3614 offset_map
[i
] = offset
;
3617 operand_map
[i
] = map
;
3618 gcc_assert (map
< ipa_get_param_count (IPA_NODE_REF (to
)));
3621 for (i
= 0; vec_safe_iterate (callee_info
->entry
, i
, &e
); i
++)
3623 struct predicate p
= remap_predicate (info
, callee_info
,
3624 &e
->predicate
, operand_map
,
3627 if (!false_predicate_p (&p
))
3629 gcov_type add_time
= ((gcov_type
) e
->time
* edge
->frequency
3630 + CGRAPH_FREQ_BASE
/ 2) / CGRAPH_FREQ_BASE
;
3631 int prob
= predicate_probability (callee_info
->conds
,
3634 add_time
= apply_probability ((gcov_type
) add_time
, prob
);
3635 if (add_time
> MAX_TIME
* INLINE_TIME_SCALE
)
3636 add_time
= MAX_TIME
* INLINE_TIME_SCALE
;
3637 if (prob
!= REG_BR_PROB_BASE
3638 && dump_file
&& (dump_flags
& TDF_DETAILS
))
3640 fprintf (dump_file
, "\t\tScaling time by probability:%f\n",
3641 (double) prob
/ REG_BR_PROB_BASE
);
3643 account_size_time (info
, e
->size
, add_time
, &p
);
3646 remap_edge_summaries (edge
, edge
->callee
, info
, callee_info
, operand_map
,
3647 offset_map
, clause
, &toplev_predicate
);
3648 remap_hint_predicate (info
, callee_info
,
3649 &callee_info
->loop_iterations
,
3650 operand_map
, offset_map
, clause
, &toplev_predicate
);
3651 remap_hint_predicate (info
, callee_info
,
3652 &callee_info
->loop_stride
,
3653 operand_map
, offset_map
, clause
, &toplev_predicate
);
3654 remap_hint_predicate (info
, callee_info
,
3655 &callee_info
->array_index
,
3656 operand_map
, offset_map
, clause
, &toplev_predicate
);
3658 inline_update_callee_summaries (edge
->callee
,
3659 inline_edge_summary (edge
)->loop_depth
);
3661 /* We do not maintain predicates of inlined edges, free it. */
3662 edge_set_predicate (edge
, &true_p
);
3663 /* Similarly remove param summaries. */
3664 es
->param
.release ();
3665 operand_map
.release ();
3666 offset_map
.release ();
3669 /* For performance reasons inline_merge_summary is not updating overall size
3670 and time. Recompute it. */
3673 inline_update_overall_summary (struct cgraph_node
*node
)
3675 struct inline_summary
*info
= inline_summaries
->get (node
);
3681 for (i
= 0; vec_safe_iterate (info
->entry
, i
, &e
); i
++)
3683 info
->size
+= e
->size
, info
->time
+= e
->time
;
3684 if (info
->time
> MAX_TIME
* INLINE_TIME_SCALE
)
3685 info
->time
= MAX_TIME
* INLINE_TIME_SCALE
;
3687 estimate_calls_size_and_time (node
, &info
->size
, &info
->min_size
,
3689 ~(clause_t
) (1 << predicate_false_condition
),
3690 vNULL
, vNULL
, vNULL
);
3691 info
->time
= (info
->time
+ INLINE_TIME_SCALE
/ 2) / INLINE_TIME_SCALE
;
3692 info
->size
= (info
->size
+ INLINE_SIZE_SCALE
/ 2) / INLINE_SIZE_SCALE
;
3695 /* Return hints derrived from EDGE. */
3697 simple_edge_hints (struct cgraph_edge
*edge
)
3700 struct cgraph_node
*to
= (edge
->caller
->global
.inlined_to
3701 ? edge
->caller
->global
.inlined_to
: edge
->caller
);
3702 struct cgraph_node
*callee
= edge
->callee
->ultimate_alias_target ();
3703 if (inline_summaries
->get (to
)->scc_no
3704 && inline_summaries
->get (to
)->scc_no
3705 == inline_summaries
->get (callee
)->scc_no
3706 && !edge
->recursive_p ())
3707 hints
|= INLINE_HINT_same_scc
;
3709 if (callee
->lto_file_data
&& edge
->caller
->lto_file_data
3710 && edge
->caller
->lto_file_data
!= callee
->lto_file_data
3712 hints
|= INLINE_HINT_cross_module
;
3717 /* Estimate the time cost for the caller when inlining EDGE.
3718 Only to be called via estimate_edge_time, that handles the
3721 When caching, also update the cache entry. Compute both time and
3722 size, since we always need both metrics eventually. */
3725 do_estimate_edge_time (struct cgraph_edge
*edge
)
3730 struct cgraph_node
*callee
;
3732 vec
<tree
> known_vals
;
3733 vec
<ipa_polymorphic_call_context
> known_contexts
;
3734 vec
<ipa_agg_jump_function_p
> known_aggs
;
3735 struct inline_edge_summary
*es
= inline_edge_summary (edge
);
3738 callee
= edge
->callee
->ultimate_alias_target ();
3740 gcc_checking_assert (edge
->inline_failed
);
3741 evaluate_properties_for_edge (edge
, true,
3742 &clause
, &known_vals
, &known_contexts
,
3744 estimate_node_size_and_time (callee
, clause
, known_vals
, known_contexts
,
3745 known_aggs
, &size
, &min_size
, &time
, &hints
, es
->param
);
3747 /* When we have profile feedback, we can quite safely identify hot
3748 edges and for those we disable size limits. Don't do that when
3749 probability that caller will call the callee is low however, since it
3750 may hurt optimization of the caller's hot path. */
3751 if (edge
->count
&& edge
->maybe_hot_p ()
3753 > (edge
->caller
->global
.inlined_to
3754 ? edge
->caller
->global
.inlined_to
->count
: edge
->caller
->count
)))
3755 hints
|= INLINE_HINT_known_hot
;
3757 known_vals
.release ();
3758 known_contexts
.release ();
3759 known_aggs
.release ();
3760 gcc_checking_assert (size
>= 0);
3761 gcc_checking_assert (time
>= 0);
3763 /* When caching, update the cache entry. */
3764 if (edge_growth_cache
.exists ())
3766 inline_summaries
->get (edge
->callee
)->min_size
= min_size
;
3767 if ((int) edge_growth_cache
.length () <= edge
->uid
)
3768 edge_growth_cache
.safe_grow_cleared (symtab
->edges_max_uid
);
3769 edge_growth_cache
[edge
->uid
].time
= time
+ (time
>= 0);
3771 edge_growth_cache
[edge
->uid
].size
= size
+ (size
>= 0);
3772 hints
|= simple_edge_hints (edge
);
3773 edge_growth_cache
[edge
->uid
].hints
= hints
+ 1;
3779 /* Return estimated callee growth after inlining EDGE.
3780 Only to be called via estimate_edge_size. */
3783 do_estimate_edge_size (struct cgraph_edge
*edge
)
3786 struct cgraph_node
*callee
;
3788 vec
<tree
> known_vals
;
3789 vec
<ipa_polymorphic_call_context
> known_contexts
;
3790 vec
<ipa_agg_jump_function_p
> known_aggs
;
3792 /* When we do caching, use do_estimate_edge_time to populate the entry. */
3794 if (edge_growth_cache
.exists ())
3796 do_estimate_edge_time (edge
);
3797 size
= edge_growth_cache
[edge
->uid
].size
;
3798 gcc_checking_assert (size
);
3799 return size
- (size
> 0);
3802 callee
= edge
->callee
->ultimate_alias_target ();
3804 /* Early inliner runs without caching, go ahead and do the dirty work. */
3805 gcc_checking_assert (edge
->inline_failed
);
3806 evaluate_properties_for_edge (edge
, true,
3807 &clause
, &known_vals
, &known_contexts
,
3809 estimate_node_size_and_time (callee
, clause
, known_vals
, known_contexts
,
3810 known_aggs
, &size
, NULL
, NULL
, NULL
, vNULL
);
3811 known_vals
.release ();
3812 known_contexts
.release ();
3813 known_aggs
.release ();
3818 /* Estimate the growth of the caller when inlining EDGE.
3819 Only to be called via estimate_edge_size. */
3822 do_estimate_edge_hints (struct cgraph_edge
*edge
)
3825 struct cgraph_node
*callee
;
3827 vec
<tree
> known_vals
;
3828 vec
<ipa_polymorphic_call_context
> known_contexts
;
3829 vec
<ipa_agg_jump_function_p
> known_aggs
;
3831 /* When we do caching, use do_estimate_edge_time to populate the entry. */
3833 if (edge_growth_cache
.exists ())
3835 do_estimate_edge_time (edge
);
3836 hints
= edge_growth_cache
[edge
->uid
].hints
;
3837 gcc_checking_assert (hints
);
3841 callee
= edge
->callee
->ultimate_alias_target ();
3843 /* Early inliner runs without caching, go ahead and do the dirty work. */
3844 gcc_checking_assert (edge
->inline_failed
);
3845 evaluate_properties_for_edge (edge
, true,
3846 &clause
, &known_vals
, &known_contexts
,
3848 estimate_node_size_and_time (callee
, clause
, known_vals
, known_contexts
,
3849 known_aggs
, NULL
, NULL
, NULL
, &hints
, vNULL
);
3850 known_vals
.release ();
3851 known_contexts
.release ();
3852 known_aggs
.release ();
3853 hints
|= simple_edge_hints (edge
);
3858 /* Estimate self time of the function NODE after inlining EDGE. */
3861 estimate_time_after_inlining (struct cgraph_node
*node
,
3862 struct cgraph_edge
*edge
)
3864 struct inline_edge_summary
*es
= inline_edge_summary (edge
);
3865 if (!es
->predicate
|| !false_predicate_p (es
->predicate
))
3868 inline_summaries
->get (node
)->time
+ estimate_edge_time (edge
);
3871 if (time
> MAX_TIME
)
3875 return inline_summaries
->get (node
)->time
;
3879 /* Estimate the size of NODE after inlining EDGE which should be an
3880 edge to either NODE or a call inlined into NODE. */
3883 estimate_size_after_inlining (struct cgraph_node
*node
,
3884 struct cgraph_edge
*edge
)
3886 struct inline_edge_summary
*es
= inline_edge_summary (edge
);
3887 if (!es
->predicate
|| !false_predicate_p (es
->predicate
))
3889 int size
= inline_summaries
->get (node
)->size
+ estimate_edge_growth (edge
);
3890 gcc_assert (size
>= 0);
3893 return inline_summaries
->get (node
)->size
;
3899 struct cgraph_node
*node
;
3900 bool self_recursive
;
3906 /* Worker for do_estimate_growth. Collect growth for all callers. */
3909 do_estimate_growth_1 (struct cgraph_node
*node
, void *data
)
3911 struct cgraph_edge
*e
;
3912 struct growth_data
*d
= (struct growth_data
*) data
;
3914 for (e
= node
->callers
; e
; e
= e
->next_caller
)
3916 gcc_checking_assert (e
->inline_failed
);
3918 if (cgraph_inline_failed_type (e
->inline_failed
) == CIF_FINAL_ERROR
)
3920 d
->uninlinable
= true;
3924 if (e
->recursive_p ())
3926 d
->self_recursive
= true;
3929 d
->growth
+= estimate_edge_growth (e
);
3935 /* Estimate the growth caused by inlining NODE into all callees. */
3938 estimate_growth (struct cgraph_node
*node
)
3940 struct growth_data d
= { node
, false, false, 0 };
3941 struct inline_summary
*info
= inline_summaries
->get (node
);
3943 node
->call_for_symbol_and_aliases (do_estimate_growth_1
, &d
, true);
3945 /* For self recursive functions the growth estimation really should be
3946 infinity. We don't want to return very large values because the growth
3947 plays various roles in badness computation fractions. Be sure to not
3948 return zero or negative growths. */
3949 if (d
.self_recursive
)
3950 d
.growth
= d
.growth
< info
->size
? info
->size
: d
.growth
;
3951 else if (DECL_EXTERNAL (node
->decl
) || d
.uninlinable
)
3955 if (node
->will_be_removed_from_program_if_no_direct_calls_p ())
3956 d
.growth
-= info
->size
;
3957 /* COMDAT functions are very often not shared across multiple units
3958 since they come from various template instantiations.
3959 Take this into account. */
3960 else if (DECL_COMDAT (node
->decl
)
3961 && node
->can_remove_if_no_direct_calls_p ())
3962 d
.growth
-= (info
->size
3963 * (100 - PARAM_VALUE (PARAM_COMDAT_SHARING_PROBABILITY
))
3970 /* Verify if there are fewer than MAX_CALLERS. */
3973 check_callers (cgraph_node
*node
, int *max_callers
)
3977 if (!node
->can_remove_if_no_direct_calls_and_refs_p ())
3980 for (cgraph_edge
*e
= node
->callers
; e
; e
= e
->next_caller
)
3984 || cgraph_inline_failed_type (e
->inline_failed
) == CIF_FINAL_ERROR
)
3988 FOR_EACH_ALIAS (node
, ref
)
3989 if (check_callers (dyn_cast
<cgraph_node
*> (ref
->referring
), max_callers
))
3996 /* Make cheap estimation if growth of NODE is likely positive knowing
3997 EDGE_GROWTH of one particular edge.
3998 We assume that most of other edges will have similar growth
3999 and skip computation if there are too many callers. */
4002 growth_likely_positive (struct cgraph_node
*node
,
4006 struct cgraph_edge
*e
;
4007 gcc_checking_assert (edge_growth
> 0);
4009 /* First quickly check if NODE is removable at all. */
4010 if (DECL_EXTERNAL (node
->decl
))
4012 if (!node
->can_remove_if_no_direct_calls_and_refs_p ()
4013 || node
->address_taken
)
4016 max_callers
= inline_summaries
->get (node
)->size
* 4 / edge_growth
+ 2;
4018 for (e
= node
->callers
; e
; e
= e
->next_caller
)
4022 || cgraph_inline_failed_type (e
->inline_failed
) == CIF_FINAL_ERROR
)
4027 FOR_EACH_ALIAS (node
, ref
)
4028 if (check_callers (dyn_cast
<cgraph_node
*> (ref
->referring
), &max_callers
))
4031 /* Unlike for functions called once, we play unsafe with
4032 COMDATs. We can allow that since we know functions
4033 in consideration are small (and thus risk is small) and
4034 moreover grow estimates already accounts that COMDAT
4035 functions may or may not disappear when eliminated from
4036 current unit. With good probability making aggressive
4037 choice in all units is going to make overall program
4039 if (DECL_COMDAT (node
->decl
))
4041 if (!node
->can_remove_if_no_direct_calls_p ())
4044 else if (!node
->will_be_removed_from_program_if_no_direct_calls_p ())
4047 return estimate_growth (node
) > 0;
4051 /* This function performs intraprocedural analysis in NODE that is required to
4052 inline indirect calls. */
4055 inline_indirect_intraprocedural_analysis (struct cgraph_node
*node
)
4057 ipa_analyze_node (node
);
4058 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
4060 ipa_print_node_params (dump_file
, node
);
4061 ipa_print_node_jump_functions (dump_file
, node
);
4066 /* Note function body size. */
4069 inline_analyze_function (struct cgraph_node
*node
)
4071 push_cfun (DECL_STRUCT_FUNCTION (node
->decl
));
4074 fprintf (dump_file
, "\nAnalyzing function: %s/%u\n",
4075 node
->name (), node
->order
);
4076 if (opt_for_fn (node
->decl
, optimize
) && !node
->thunk
.thunk_p
)
4077 inline_indirect_intraprocedural_analysis (node
);
4078 compute_inline_parameters (node
, false);
4081 struct cgraph_edge
*e
;
4082 for (e
= node
->callees
; e
; e
= e
->next_callee
)
4084 if (e
->inline_failed
== CIF_FUNCTION_NOT_CONSIDERED
)
4085 e
->inline_failed
= CIF_FUNCTION_NOT_OPTIMIZED
;
4086 e
->call_stmt_cannot_inline_p
= true;
4088 for (e
= node
->indirect_calls
; e
; e
= e
->next_callee
)
4090 if (e
->inline_failed
== CIF_FUNCTION_NOT_CONSIDERED
)
4091 e
->inline_failed
= CIF_FUNCTION_NOT_OPTIMIZED
;
4092 e
->call_stmt_cannot_inline_p
= true;
4100 /* Called when new function is inserted to callgraph late. */
4103 inline_summary_t::insert (struct cgraph_node
*node
, inline_summary
*)
4105 inline_analyze_function (node
);
4108 /* Note function body size. */
4111 inline_generate_summary (void)
4113 struct cgraph_node
*node
;
4115 /* When not optimizing, do not bother to analyze. Inlining is still done
4116 because edge redirection needs to happen there. */
4117 if (!optimize
&& !flag_generate_lto
&& !flag_generate_offload
&& !flag_wpa
)
4120 if (!inline_summaries
)
4121 inline_summaries
= (inline_summary_t
*) inline_summary_t::create_ggc (symtab
);
4123 inline_summaries
->enable_insertion_hook ();
4125 ipa_register_cgraph_hooks ();
4126 inline_free_summary ();
4128 FOR_EACH_DEFINED_FUNCTION (node
)
4130 inline_analyze_function (node
);
4134 /* Read predicate from IB. */
4136 static struct predicate
4137 read_predicate (struct lto_input_block
*ib
)
4139 struct predicate out
;
4145 gcc_assert (k
<= MAX_CLAUSES
);
4146 clause
= out
.clause
[k
++] = streamer_read_uhwi (ib
);
4150 /* Zero-initialize the remaining clauses in OUT. */
4151 while (k
<= MAX_CLAUSES
)
4152 out
.clause
[k
++] = 0;
4158 /* Write inline summary for edge E to OB. */
4161 read_inline_edge_summary (struct lto_input_block
*ib
, struct cgraph_edge
*e
)
4163 struct inline_edge_summary
*es
= inline_edge_summary (e
);
4167 es
->call_stmt_size
= streamer_read_uhwi (ib
);
4168 es
->call_stmt_time
= streamer_read_uhwi (ib
);
4169 es
->loop_depth
= streamer_read_uhwi (ib
);
4170 p
= read_predicate (ib
);
4171 edge_set_predicate (e
, &p
);
4172 length
= streamer_read_uhwi (ib
);
4175 es
->param
.safe_grow_cleared (length
);
4176 for (i
= 0; i
< length
; i
++)
4177 es
->param
[i
].change_prob
= streamer_read_uhwi (ib
);
4182 /* Stream in inline summaries from the section. */
4185 inline_read_section (struct lto_file_decl_data
*file_data
, const char *data
,
4188 const struct lto_function_header
*header
=
4189 (const struct lto_function_header
*) data
;
4190 const int cfg_offset
= sizeof (struct lto_function_header
);
4191 const int main_offset
= cfg_offset
+ header
->cfg_size
;
4192 const int string_offset
= main_offset
+ header
->main_size
;
4193 struct data_in
*data_in
;
4194 unsigned int i
, count2
, j
;
4195 unsigned int f_count
;
4197 lto_input_block
ib ((const char *) data
+ main_offset
, header
->main_size
,
4198 file_data
->mode_table
);
4201 lto_data_in_create (file_data
, (const char *) data
+ string_offset
,
4202 header
->string_size
, vNULL
);
4203 f_count
= streamer_read_uhwi (&ib
);
4204 for (i
= 0; i
< f_count
; i
++)
4207 struct cgraph_node
*node
;
4208 struct inline_summary
*info
;
4209 lto_symtab_encoder_t encoder
;
4210 struct bitpack_d bp
;
4211 struct cgraph_edge
*e
;
4214 index
= streamer_read_uhwi (&ib
);
4215 encoder
= file_data
->symtab_node_encoder
;
4216 node
= dyn_cast
<cgraph_node
*> (lto_symtab_encoder_deref (encoder
,
4218 info
= inline_summaries
->get (node
);
4220 info
->estimated_stack_size
4221 = info
->estimated_self_stack_size
= streamer_read_uhwi (&ib
);
4222 info
->size
= info
->self_size
= streamer_read_uhwi (&ib
);
4223 info
->time
= info
->self_time
= streamer_read_uhwi (&ib
);
4225 bp
= streamer_read_bitpack (&ib
);
4226 info
->inlinable
= bp_unpack_value (&bp
, 1);
4227 info
->contains_cilk_spawn
= bp_unpack_value (&bp
, 1);
4229 count2
= streamer_read_uhwi (&ib
);
4230 gcc_assert (!info
->conds
);
4231 for (j
= 0; j
< count2
; j
++)
4234 c
.operand_num
= streamer_read_uhwi (&ib
);
4235 c
.code
= (enum tree_code
) streamer_read_uhwi (&ib
);
4236 c
.val
= stream_read_tree (&ib
, data_in
);
4237 bp
= streamer_read_bitpack (&ib
);
4238 c
.agg_contents
= bp_unpack_value (&bp
, 1);
4239 c
.by_ref
= bp_unpack_value (&bp
, 1);
4241 c
.offset
= streamer_read_uhwi (&ib
);
4242 vec_safe_push (info
->conds
, c
);
4244 count2
= streamer_read_uhwi (&ib
);
4245 gcc_assert (!info
->entry
);
4246 for (j
= 0; j
< count2
; j
++)
4248 struct size_time_entry e
;
4250 e
.size
= streamer_read_uhwi (&ib
);
4251 e
.time
= streamer_read_uhwi (&ib
);
4252 e
.predicate
= read_predicate (&ib
);
4254 vec_safe_push (info
->entry
, e
);
4257 p
= read_predicate (&ib
);
4258 set_hint_predicate (&info
->loop_iterations
, p
);
4259 p
= read_predicate (&ib
);
4260 set_hint_predicate (&info
->loop_stride
, p
);
4261 p
= read_predicate (&ib
);
4262 set_hint_predicate (&info
->array_index
, p
);
4263 for (e
= node
->callees
; e
; e
= e
->next_callee
)
4264 read_inline_edge_summary (&ib
, e
);
4265 for (e
= node
->indirect_calls
; e
; e
= e
->next_callee
)
4266 read_inline_edge_summary (&ib
, e
);
4269 lto_free_section_data (file_data
, LTO_section_inline_summary
, NULL
, data
,
4271 lto_data_in_delete (data_in
);
4275 /* Read inline summary. Jump functions are shared among ipa-cp
4276 and inliner, so when ipa-cp is active, we don't need to write them
4280 inline_read_summary (void)
4282 struct lto_file_decl_data
**file_data_vec
= lto_get_file_decl_data ();
4283 struct lto_file_decl_data
*file_data
;
4286 inline_summary_alloc ();
4288 while ((file_data
= file_data_vec
[j
++]))
4291 const char *data
= lto_get_section_data (file_data
,
4292 LTO_section_inline_summary
,
4295 inline_read_section (file_data
, data
, len
);
4297 /* Fatal error here. We do not want to support compiling ltrans units
4298 with different version of compiler or different flags than the WPA
4299 unit, so this should never happen. */
4300 fatal_error (input_location
,
4301 "ipa inline summary is missing in input file");
4305 ipa_register_cgraph_hooks ();
4307 ipa_prop_read_jump_functions ();
4310 gcc_assert (inline_summaries
);
4311 inline_summaries
->enable_insertion_hook ();
4315 /* Write predicate P to OB. */
4318 write_predicate (struct output_block
*ob
, struct predicate
*p
)
4322 for (j
= 0; p
->clause
[j
]; j
++)
4324 gcc_assert (j
< MAX_CLAUSES
);
4325 streamer_write_uhwi (ob
, p
->clause
[j
]);
4327 streamer_write_uhwi (ob
, 0);
4331 /* Write inline summary for edge E to OB. */
4334 write_inline_edge_summary (struct output_block
*ob
, struct cgraph_edge
*e
)
4336 struct inline_edge_summary
*es
= inline_edge_summary (e
);
4339 streamer_write_uhwi (ob
, es
->call_stmt_size
);
4340 streamer_write_uhwi (ob
, es
->call_stmt_time
);
4341 streamer_write_uhwi (ob
, es
->loop_depth
);
4342 write_predicate (ob
, es
->predicate
);
4343 streamer_write_uhwi (ob
, es
->param
.length ());
4344 for (i
= 0; i
< (int) es
->param
.length (); i
++)
4345 streamer_write_uhwi (ob
, es
->param
[i
].change_prob
);
4349 /* Write inline summary for node in SET.
4350 Jump functions are shared among ipa-cp and inliner, so when ipa-cp is
4351 active, we don't need to write them twice. */
4354 inline_write_summary (void)
4356 struct cgraph_node
*node
;
4357 struct output_block
*ob
= create_output_block (LTO_section_inline_summary
);
4358 lto_symtab_encoder_t encoder
= ob
->decl_state
->symtab_node_encoder
;
4359 unsigned int count
= 0;
4362 for (i
= 0; i
< lto_symtab_encoder_size (encoder
); i
++)
4364 symtab_node
*snode
= lto_symtab_encoder_deref (encoder
, i
);
4365 cgraph_node
*cnode
= dyn_cast
<cgraph_node
*> (snode
);
4366 if (cnode
&& cnode
->definition
&& !cnode
->alias
)
4369 streamer_write_uhwi (ob
, count
);
4371 for (i
= 0; i
< lto_symtab_encoder_size (encoder
); i
++)
4373 symtab_node
*snode
= lto_symtab_encoder_deref (encoder
, i
);
4374 cgraph_node
*cnode
= dyn_cast
<cgraph_node
*> (snode
);
4375 if (cnode
&& (node
= cnode
)->definition
&& !node
->alias
)
4377 struct inline_summary
*info
= inline_summaries
->get (node
);
4378 struct bitpack_d bp
;
4379 struct cgraph_edge
*edge
;
4382 struct condition
*c
;
4384 streamer_write_uhwi (ob
,
4385 lto_symtab_encoder_encode (encoder
,
4388 streamer_write_hwi (ob
, info
->estimated_self_stack_size
);
4389 streamer_write_hwi (ob
, info
->self_size
);
4390 streamer_write_hwi (ob
, info
->self_time
);
4391 bp
= bitpack_create (ob
->main_stream
);
4392 bp_pack_value (&bp
, info
->inlinable
, 1);
4393 bp_pack_value (&bp
, info
->contains_cilk_spawn
, 1);
4394 streamer_write_bitpack (&bp
);
4395 streamer_write_uhwi (ob
, vec_safe_length (info
->conds
));
4396 for (i
= 0; vec_safe_iterate (info
->conds
, i
, &c
); i
++)
4398 streamer_write_uhwi (ob
, c
->operand_num
);
4399 streamer_write_uhwi (ob
, c
->code
);
4400 stream_write_tree (ob
, c
->val
, true);
4401 bp
= bitpack_create (ob
->main_stream
);
4402 bp_pack_value (&bp
, c
->agg_contents
, 1);
4403 bp_pack_value (&bp
, c
->by_ref
, 1);
4404 streamer_write_bitpack (&bp
);
4405 if (c
->agg_contents
)
4406 streamer_write_uhwi (ob
, c
->offset
);
4408 streamer_write_uhwi (ob
, vec_safe_length (info
->entry
));
4409 for (i
= 0; vec_safe_iterate (info
->entry
, i
, &e
); i
++)
4411 streamer_write_uhwi (ob
, e
->size
);
4412 streamer_write_uhwi (ob
, e
->time
);
4413 write_predicate (ob
, &e
->predicate
);
4415 write_predicate (ob
, info
->loop_iterations
);
4416 write_predicate (ob
, info
->loop_stride
);
4417 write_predicate (ob
, info
->array_index
);
4418 for (edge
= node
->callees
; edge
; edge
= edge
->next_callee
)
4419 write_inline_edge_summary (ob
, edge
);
4420 for (edge
= node
->indirect_calls
; edge
; edge
= edge
->next_callee
)
4421 write_inline_edge_summary (ob
, edge
);
4424 streamer_write_char_stream (ob
->main_stream
, 0);
4425 produce_asm (ob
, NULL
);
4426 destroy_output_block (ob
);
4428 if (optimize
&& !flag_ipa_cp
)
4429 ipa_prop_write_jump_functions ();
4433 /* Release inline summary. */
4436 inline_free_summary (void)
4438 struct cgraph_node
*node
;
4439 if (edge_removal_hook_holder
)
4440 symtab
->remove_edge_removal_hook (edge_removal_hook_holder
);
4441 edge_removal_hook_holder
= NULL
;
4442 if (edge_duplication_hook_holder
)
4443 symtab
->remove_edge_duplication_hook (edge_duplication_hook_holder
);
4444 edge_duplication_hook_holder
= NULL
;
4445 if (!inline_edge_summary_vec
.exists ())
4447 FOR_EACH_DEFINED_FUNCTION (node
)
4449 reset_inline_summary (node
, inline_summaries
->get (node
));
4450 inline_summaries
->release ();
4451 inline_summaries
= NULL
;
4452 inline_edge_summary_vec
.release ();
4453 edge_predicate_pool
.release ();