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 "lto-streamer.h"
98 #include "data-streamer.h"
99 #include "tree-streamer.h"
100 #include "ipa-inline.h"
102 #include "tree-scalar-evolution.h"
103 #include "ipa-utils.h"
105 #include "cfgexpand.h"
107 /* Estimate runtime of function can easilly run into huge numbers with many
108 nested loops. Be sure we can compute time * INLINE_SIZE_SCALE * 2 in an
109 integer. For anything larger we use gcov_type. */
110 #define MAX_TIME 500000
112 /* Number of bits in integer, but we really want to be stable across different
114 #define NUM_CONDITIONS 32
116 enum predicate_conditions
118 predicate_false_condition
= 0,
119 predicate_not_inlined_condition
= 1,
120 predicate_first_dynamic_condition
= 2
123 /* Special condition code we use to represent test that operand is compile time
125 #define IS_NOT_CONSTANT ERROR_MARK
126 /* Special condition code we use to represent test that operand is not changed
127 across invocation of the function. When operand IS_NOT_CONSTANT it is always
128 CHANGED, however i.e. loop invariants can be NOT_CHANGED given percentage
129 of executions even when they are not compile time constants. */
130 #define CHANGED IDENTIFIER_NODE
132 /* Holders of ipa cgraph hooks: */
133 static struct cgraph_2edge_hook_list
*edge_duplication_hook_holder
;
134 static struct cgraph_edge_hook_list
*edge_removal_hook_holder
;
135 static void inline_edge_removal_hook (struct cgraph_edge
*, void *);
136 static void inline_edge_duplication_hook (struct cgraph_edge
*,
137 struct cgraph_edge
*, void *);
139 /* VECtor holding inline summaries.
140 In GGC memory because conditions might point to constant trees. */
141 function_summary
<inline_summary
*> *inline_summaries
;
142 vec
<inline_edge_summary_t
> inline_edge_summary_vec
;
144 /* Cached node/edge growths. */
145 vec
<edge_growth_cache_entry
> edge_growth_cache
;
147 /* Edge predicates goes here. */
148 static pool_allocator
<predicate
> edge_predicate_pool ("edge predicates", 10);
150 /* Return true predicate (tautology).
151 We represent it by empty list of clauses. */
153 static inline struct predicate
154 true_predicate (void)
162 /* Return predicate testing single condition number COND. */
164 static inline struct predicate
165 single_cond_predicate (int cond
)
168 p
.clause
[0] = 1 << cond
;
174 /* Return false predicate. First clause require false condition. */
176 static inline struct predicate
177 false_predicate (void)
179 return single_cond_predicate (predicate_false_condition
);
183 /* Return true if P is (true). */
186 true_predicate_p (struct predicate
*p
)
188 return !p
->clause
[0];
192 /* Return true if P is (false). */
195 false_predicate_p (struct predicate
*p
)
197 if (p
->clause
[0] == (1 << predicate_false_condition
))
199 gcc_checking_assert (!p
->clause
[1]
200 && p
->clause
[0] == 1 << predicate_false_condition
);
207 /* Return predicate that is set true when function is not inlined. */
209 static inline struct predicate
210 not_inlined_predicate (void)
212 return single_cond_predicate (predicate_not_inlined_condition
);
215 /* Simple description of whether a memory load or a condition refers to a load
216 from an aggregate and if so, how and where from in the aggregate.
217 Individual fields have the same meaning like fields with the same name in
220 struct agg_position_info
222 HOST_WIDE_INT offset
;
227 /* Add condition to condition list CONDS. AGGPOS describes whether the used
228 oprand is loaded from an aggregate and where in the aggregate it is. It can
229 be NULL, which means this not a load from an aggregate. */
231 static struct predicate
232 add_condition (struct inline_summary
*summary
, int operand_num
,
233 struct agg_position_info
*aggpos
,
234 enum tree_code code
, tree val
)
238 struct condition new_cond
;
239 HOST_WIDE_INT offset
;
240 bool agg_contents
, by_ref
;
244 offset
= aggpos
->offset
;
245 agg_contents
= aggpos
->agg_contents
;
246 by_ref
= aggpos
->by_ref
;
251 agg_contents
= false;
255 gcc_checking_assert (operand_num
>= 0);
256 for (i
= 0; vec_safe_iterate (summary
->conds
, i
, &c
); i
++)
258 if (c
->operand_num
== operand_num
261 && c
->agg_contents
== agg_contents
262 && (!agg_contents
|| (c
->offset
== offset
&& c
->by_ref
== by_ref
)))
263 return single_cond_predicate (i
+ predicate_first_dynamic_condition
);
265 /* Too many conditions. Give up and return constant true. */
266 if (i
== NUM_CONDITIONS
- predicate_first_dynamic_condition
)
267 return true_predicate ();
269 new_cond
.operand_num
= operand_num
;
270 new_cond
.code
= code
;
272 new_cond
.agg_contents
= agg_contents
;
273 new_cond
.by_ref
= by_ref
;
274 new_cond
.offset
= offset
;
275 vec_safe_push (summary
->conds
, new_cond
);
276 return single_cond_predicate (i
+ predicate_first_dynamic_condition
);
280 /* Add clause CLAUSE into the predicate P. */
283 add_clause (conditions conditions
, struct predicate
*p
, clause_t clause
)
287 int insert_here
= -1;
294 /* False clause makes the whole predicate false. Kill the other variants. */
295 if (clause
== (1 << predicate_false_condition
))
297 p
->clause
[0] = (1 << predicate_false_condition
);
301 if (false_predicate_p (p
))
304 /* No one should be silly enough to add false into nontrivial clauses. */
305 gcc_checking_assert (!(clause
& (1 << predicate_false_condition
)));
307 /* Look where to insert the clause. At the same time prune out
308 clauses of P that are implied by the new clause and thus
310 for (i
= 0, i2
= 0; i
<= MAX_CLAUSES
; i
++)
312 p
->clause
[i2
] = p
->clause
[i
];
317 /* If p->clause[i] implies clause, there is nothing to add. */
318 if ((p
->clause
[i
] & clause
) == p
->clause
[i
])
320 /* We had nothing to add, none of clauses should've become
322 gcc_checking_assert (i
== i2
);
326 if (p
->clause
[i
] < clause
&& insert_here
< 0)
329 /* If clause implies p->clause[i], then p->clause[i] becomes redundant.
330 Otherwise the p->clause[i] has to stay. */
331 if ((p
->clause
[i
] & clause
) != clause
)
335 /* Look for clauses that are obviously true. I.e.
336 op0 == 5 || op0 != 5. */
337 for (c1
= predicate_first_dynamic_condition
; c1
< NUM_CONDITIONS
; c1
++)
340 if (!(clause
& (1 << c1
)))
342 cc1
= &(*conditions
)[c1
- predicate_first_dynamic_condition
];
343 /* We have no way to represent !CHANGED and !IS_NOT_CONSTANT
344 and thus there is no point for looking for them. */
345 if (cc1
->code
== CHANGED
|| cc1
->code
== IS_NOT_CONSTANT
)
347 for (c2
= c1
+ 1; c2
< NUM_CONDITIONS
; c2
++)
348 if (clause
& (1 << c2
))
351 &(*conditions
)[c1
- predicate_first_dynamic_condition
];
353 &(*conditions
)[c2
- predicate_first_dynamic_condition
];
354 if (cc1
->operand_num
== cc2
->operand_num
355 && cc1
->val
== cc2
->val
356 && cc2
->code
!= IS_NOT_CONSTANT
357 && cc2
->code
!= CHANGED
358 && cc1
->code
== invert_tree_comparison (cc2
->code
,
359 HONOR_NANS (cc1
->val
)))
365 /* We run out of variants. Be conservative in positive direction. */
366 if (i2
== MAX_CLAUSES
)
368 /* Keep clauses in decreasing order. This makes equivalence testing easy. */
369 p
->clause
[i2
+ 1] = 0;
370 if (insert_here
>= 0)
371 for (; i2
> insert_here
; i2
--)
372 p
->clause
[i2
] = p
->clause
[i2
- 1];
375 p
->clause
[insert_here
] = clause
;
381 static struct predicate
382 and_predicates (conditions conditions
,
383 struct predicate
*p
, struct predicate
*p2
)
385 struct predicate out
= *p
;
388 /* Avoid busy work. */
389 if (false_predicate_p (p2
) || true_predicate_p (p
))
391 if (false_predicate_p (p
) || true_predicate_p (p2
))
394 /* See how far predicates match. */
395 for (i
= 0; p
->clause
[i
] && p
->clause
[i
] == p2
->clause
[i
]; i
++)
397 gcc_checking_assert (i
< MAX_CLAUSES
);
400 /* Combine the predicates rest. */
401 for (; p2
->clause
[i
]; i
++)
403 gcc_checking_assert (i
< MAX_CLAUSES
);
404 add_clause (conditions
, &out
, p2
->clause
[i
]);
410 /* Return true if predicates are obviously equal. */
413 predicates_equal_p (struct predicate
*p
, struct predicate
*p2
)
416 for (i
= 0; p
->clause
[i
]; i
++)
418 gcc_checking_assert (i
< MAX_CLAUSES
);
419 gcc_checking_assert (p
->clause
[i
] > p
->clause
[i
+ 1]);
420 gcc_checking_assert (!p2
->clause
[i
]
421 || p2
->clause
[i
] > p2
->clause
[i
+ 1]);
422 if (p
->clause
[i
] != p2
->clause
[i
])
425 return !p2
->clause
[i
];
431 static struct predicate
432 or_predicates (conditions conditions
,
433 struct predicate
*p
, struct predicate
*p2
)
435 struct predicate out
= true_predicate ();
438 /* Avoid busy work. */
439 if (false_predicate_p (p2
) || true_predicate_p (p
))
441 if (false_predicate_p (p
) || true_predicate_p (p2
))
443 if (predicates_equal_p (p
, p2
))
446 /* OK, combine the predicates. */
447 for (i
= 0; p
->clause
[i
]; i
++)
448 for (j
= 0; p2
->clause
[j
]; j
++)
450 gcc_checking_assert (i
< MAX_CLAUSES
&& j
< MAX_CLAUSES
);
451 add_clause (conditions
, &out
, p
->clause
[i
] | p2
->clause
[j
]);
457 /* Having partial truth assignment in POSSIBLE_TRUTHS, return false
458 if predicate P is known to be false. */
461 evaluate_predicate (struct predicate
*p
, clause_t possible_truths
)
465 /* True remains true. */
466 if (true_predicate_p (p
))
469 gcc_assert (!(possible_truths
& (1 << predicate_false_condition
)));
471 /* See if we can find clause we can disprove. */
472 for (i
= 0; p
->clause
[i
]; i
++)
474 gcc_checking_assert (i
< MAX_CLAUSES
);
475 if (!(p
->clause
[i
] & possible_truths
))
481 /* Return the probability in range 0...REG_BR_PROB_BASE that the predicated
482 instruction will be recomputed per invocation of the inlined call. */
485 predicate_probability (conditions conds
,
486 struct predicate
*p
, clause_t possible_truths
,
487 vec
<inline_param_summary
> inline_param_summary
)
490 int combined_prob
= REG_BR_PROB_BASE
;
492 /* True remains true. */
493 if (true_predicate_p (p
))
494 return REG_BR_PROB_BASE
;
496 if (false_predicate_p (p
))
499 gcc_assert (!(possible_truths
& (1 << predicate_false_condition
)));
501 /* See if we can find clause we can disprove. */
502 for (i
= 0; p
->clause
[i
]; i
++)
504 gcc_checking_assert (i
< MAX_CLAUSES
);
505 if (!(p
->clause
[i
] & possible_truths
))
511 if (!inline_param_summary
.exists ())
512 return REG_BR_PROB_BASE
;
513 for (i2
= 0; i2
< NUM_CONDITIONS
; i2
++)
514 if ((p
->clause
[i
] & possible_truths
) & (1 << i2
))
516 if (i2
>= predicate_first_dynamic_condition
)
519 &(*conds
)[i2
- predicate_first_dynamic_condition
];
520 if (c
->code
== CHANGED
522 (int) inline_param_summary
.length ()))
525 inline_param_summary
[c
->operand_num
].change_prob
;
526 this_prob
= MAX (this_prob
, iprob
);
529 this_prob
= REG_BR_PROB_BASE
;
532 this_prob
= REG_BR_PROB_BASE
;
534 combined_prob
= MIN (this_prob
, combined_prob
);
539 return combined_prob
;
543 /* Dump conditional COND. */
546 dump_condition (FILE *f
, conditions conditions
, int cond
)
549 if (cond
== predicate_false_condition
)
550 fprintf (f
, "false");
551 else if (cond
== predicate_not_inlined_condition
)
552 fprintf (f
, "not inlined");
555 c
= &(*conditions
)[cond
- predicate_first_dynamic_condition
];
556 fprintf (f
, "op%i", c
->operand_num
);
558 fprintf (f
, "[%soffset: " HOST_WIDE_INT_PRINT_DEC
"]",
559 c
->by_ref
? "ref " : "", c
->offset
);
560 if (c
->code
== IS_NOT_CONSTANT
)
562 fprintf (f
, " not constant");
565 if (c
->code
== CHANGED
)
567 fprintf (f
, " changed");
570 fprintf (f
, " %s ", op_symbol_code (c
->code
));
571 print_generic_expr (f
, c
->val
, 1);
576 /* Dump clause CLAUSE. */
579 dump_clause (FILE *f
, conditions conds
, clause_t clause
)
586 for (i
= 0; i
< NUM_CONDITIONS
; i
++)
587 if (clause
& (1 << i
))
592 dump_condition (f
, conds
, i
);
598 /* Dump predicate PREDICATE. */
601 dump_predicate (FILE *f
, conditions conds
, struct predicate
*pred
)
604 if (true_predicate_p (pred
))
605 dump_clause (f
, conds
, 0);
607 for (i
= 0; pred
->clause
[i
]; i
++)
611 dump_clause (f
, conds
, pred
->clause
[i
]);
617 /* Dump inline hints. */
619 dump_inline_hints (FILE *f
, inline_hints hints
)
623 fprintf (f
, "inline hints:");
624 if (hints
& INLINE_HINT_indirect_call
)
626 hints
&= ~INLINE_HINT_indirect_call
;
627 fprintf (f
, " indirect_call");
629 if (hints
& INLINE_HINT_loop_iterations
)
631 hints
&= ~INLINE_HINT_loop_iterations
;
632 fprintf (f
, " loop_iterations");
634 if (hints
& INLINE_HINT_loop_stride
)
636 hints
&= ~INLINE_HINT_loop_stride
;
637 fprintf (f
, " loop_stride");
639 if (hints
& INLINE_HINT_same_scc
)
641 hints
&= ~INLINE_HINT_same_scc
;
642 fprintf (f
, " same_scc");
644 if (hints
& INLINE_HINT_in_scc
)
646 hints
&= ~INLINE_HINT_in_scc
;
647 fprintf (f
, " in_scc");
649 if (hints
& INLINE_HINT_cross_module
)
651 hints
&= ~INLINE_HINT_cross_module
;
652 fprintf (f
, " cross_module");
654 if (hints
& INLINE_HINT_declared_inline
)
656 hints
&= ~INLINE_HINT_declared_inline
;
657 fprintf (f
, " declared_inline");
659 if (hints
& INLINE_HINT_array_index
)
661 hints
&= ~INLINE_HINT_array_index
;
662 fprintf (f
, " array_index");
664 if (hints
& INLINE_HINT_known_hot
)
666 hints
&= ~INLINE_HINT_known_hot
;
667 fprintf (f
, " known_hot");
673 /* Record SIZE and TIME under condition PRED into the inline summary. */
676 account_size_time (struct inline_summary
*summary
, int size
, int time
,
677 struct predicate
*pred
)
683 if (false_predicate_p (pred
))
686 /* We need to create initial empty unconitional clause, but otherwie
687 we don't need to account empty times and sizes. */
688 if (!size
&& !time
&& summary
->entry
)
691 /* Watch overflow that might result from insane profiles. */
692 if (time
> MAX_TIME
* INLINE_TIME_SCALE
)
693 time
= MAX_TIME
* INLINE_TIME_SCALE
;
694 gcc_assert (time
>= 0);
696 for (i
= 0; vec_safe_iterate (summary
->entry
, i
, &e
); i
++)
697 if (predicates_equal_p (&e
->predicate
, pred
))
706 e
= &(*summary
->entry
)[0];
707 gcc_assert (!e
->predicate
.clause
[0]);
708 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
710 "\t\tReached limit on number of entries, "
711 "ignoring the predicate.");
713 if (dump_file
&& (dump_flags
& TDF_DETAILS
) && (time
|| size
))
716 "\t\tAccounting size:%3.2f, time:%3.2f on %spredicate:",
717 ((double) size
) / INLINE_SIZE_SCALE
,
718 ((double) time
) / INLINE_TIME_SCALE
, found
? "" : "new ");
719 dump_predicate (dump_file
, summary
->conds
, pred
);
723 struct size_time_entry new_entry
;
724 new_entry
.size
= size
;
725 new_entry
.time
= time
;
726 new_entry
.predicate
= *pred
;
727 vec_safe_push (summary
->entry
, new_entry
);
733 if (e
->time
> MAX_TIME
* INLINE_TIME_SCALE
)
734 e
->time
= MAX_TIME
* INLINE_TIME_SCALE
;
738 /* We proved E to be unreachable, redirect it to __bultin_unreachable. */
740 static struct cgraph_edge
*
741 redirect_to_unreachable (struct cgraph_edge
*e
)
743 struct cgraph_node
*callee
= !e
->inline_failed
? e
->callee
: NULL
;
744 struct cgraph_node
*target
= cgraph_node::get_create
745 (builtin_decl_implicit (BUILT_IN_UNREACHABLE
));
748 e
= e
->resolve_speculation (target
->decl
);
750 e
->make_direct (target
);
752 e
->redirect_callee (target
);
753 struct inline_edge_summary
*es
= inline_edge_summary (e
);
754 e
->inline_failed
= CIF_UNREACHABLE
;
757 es
->call_stmt_size
= 0;
758 es
->call_stmt_time
= 0;
760 callee
->remove_symbol_and_inline_clones ();
764 /* Set predicate for edge E. */
767 edge_set_predicate (struct cgraph_edge
*e
, struct predicate
*predicate
)
769 /* If the edge is determined to be never executed, redirect it
770 to BUILTIN_UNREACHABLE to save inliner from inlining into it. */
771 if (predicate
&& false_predicate_p (predicate
)
772 /* When handling speculative edges, we need to do the redirection
773 just once. Do it always on the direct edge, so we do not
774 attempt to resolve speculation while duplicating the edge. */
775 && (!e
->speculative
|| e
->callee
))
776 e
= redirect_to_unreachable (e
);
778 struct inline_edge_summary
*es
= inline_edge_summary (e
);
779 if (predicate
&& !true_predicate_p (predicate
))
782 es
->predicate
= edge_predicate_pool
.allocate ();
783 *es
->predicate
= *predicate
;
788 edge_predicate_pool
.remove (es
->predicate
);
789 es
->predicate
= NULL
;
793 /* Set predicate for hint *P. */
796 set_hint_predicate (struct predicate
**p
, struct predicate new_predicate
)
798 if (false_predicate_p (&new_predicate
) || true_predicate_p (&new_predicate
))
801 edge_predicate_pool
.remove (*p
);
807 *p
= edge_predicate_pool
.allocate ();
813 /* KNOWN_VALS is partial mapping of parameters of NODE to constant values.
814 KNOWN_AGGS is a vector of aggreggate jump functions for each parameter.
815 Return clause of possible truths. When INLINE_P is true, assume that we are
818 ERROR_MARK means compile time invariant. */
821 evaluate_conditions_for_known_args (struct cgraph_node
*node
,
823 vec
<tree
> known_vals
,
824 vec
<ipa_agg_jump_function_p
>
827 clause_t clause
= inline_p
? 0 : 1 << predicate_not_inlined_condition
;
828 struct inline_summary
*info
= inline_summaries
->get (node
);
832 for (i
= 0; vec_safe_iterate (info
->conds
, i
, &c
); i
++)
837 /* We allow call stmt to have fewer arguments than the callee function
838 (especially for K&R style programs). So bound check here (we assume
839 known_aggs vector, if non-NULL, has the same length as
841 gcc_checking_assert (!known_aggs
.exists ()
842 || (known_vals
.length () == known_aggs
.length ()));
843 if (c
->operand_num
>= (int) known_vals
.length ())
845 clause
|= 1 << (i
+ predicate_first_dynamic_condition
);
851 struct ipa_agg_jump_function
*agg
;
853 if (c
->code
== CHANGED
855 && (known_vals
[c
->operand_num
] == error_mark_node
))
858 if (known_aggs
.exists ())
860 agg
= known_aggs
[c
->operand_num
];
861 val
= ipa_find_agg_cst_for_param (agg
, c
->offset
, c
->by_ref
);
868 val
= known_vals
[c
->operand_num
];
869 if (val
== error_mark_node
&& c
->code
!= CHANGED
)
875 clause
|= 1 << (i
+ predicate_first_dynamic_condition
);
878 if (c
->code
== IS_NOT_CONSTANT
|| c
->code
== CHANGED
)
881 if (operand_equal_p (TYPE_SIZE (TREE_TYPE (c
->val
)),
882 TYPE_SIZE (TREE_TYPE (val
)), 0))
884 val
= fold_unary (VIEW_CONVERT_EXPR
, TREE_TYPE (c
->val
), val
);
887 ? fold_binary_to_constant (c
->code
, boolean_type_node
, val
, c
->val
)
890 if (res
&& integer_zerop (res
))
893 clause
|= 1 << (i
+ predicate_first_dynamic_condition
);
899 /* Work out what conditions might be true at invocation of E. */
902 evaluate_properties_for_edge (struct cgraph_edge
*e
, bool inline_p
,
903 clause_t
*clause_ptr
,
904 vec
<tree
> *known_vals_ptr
,
905 vec
<ipa_polymorphic_call_context
>
907 vec
<ipa_agg_jump_function_p
> *known_aggs_ptr
)
909 struct cgraph_node
*callee
= e
->callee
->ultimate_alias_target ();
910 struct inline_summary
*info
= inline_summaries
->get (callee
);
911 vec
<tree
> known_vals
= vNULL
;
912 vec
<ipa_agg_jump_function_p
> known_aggs
= vNULL
;
915 *clause_ptr
= inline_p
? 0 : 1 << predicate_not_inlined_condition
;
917 known_vals_ptr
->create (0);
918 if (known_contexts_ptr
)
919 known_contexts_ptr
->create (0);
921 if (ipa_node_params_sum
922 && !e
->call_stmt_cannot_inline_p
923 && ((clause_ptr
&& info
->conds
) || known_vals_ptr
|| known_contexts_ptr
))
925 struct ipa_node_params
*parms_info
;
926 struct ipa_edge_args
*args
= IPA_EDGE_REF (e
);
927 struct inline_edge_summary
*es
= inline_edge_summary (e
);
928 int i
, count
= ipa_get_cs_argument_count (args
);
930 if (e
->caller
->global
.inlined_to
)
931 parms_info
= IPA_NODE_REF (e
->caller
->global
.inlined_to
);
933 parms_info
= IPA_NODE_REF (e
->caller
);
935 if (count
&& (info
->conds
|| known_vals_ptr
))
936 known_vals
.safe_grow_cleared (count
);
937 if (count
&& (info
->conds
|| known_aggs_ptr
))
938 known_aggs
.safe_grow_cleared (count
);
939 if (count
&& known_contexts_ptr
)
940 known_contexts_ptr
->safe_grow_cleared (count
);
942 for (i
= 0; i
< count
; i
++)
944 struct ipa_jump_func
*jf
= ipa_get_ith_jump_func (args
, i
);
945 tree cst
= ipa_value_from_jfunc (parms_info
, jf
);
947 if (!cst
&& e
->call_stmt
948 && i
< (int)gimple_call_num_args (e
->call_stmt
))
950 cst
= gimple_call_arg (e
->call_stmt
, i
);
951 if (!is_gimple_min_invariant (cst
))
956 gcc_checking_assert (TREE_CODE (cst
) != TREE_BINFO
);
957 if (known_vals
.exists ())
960 else if (inline_p
&& !es
->param
[i
].change_prob
)
961 known_vals
[i
] = error_mark_node
;
963 if (known_contexts_ptr
)
964 (*known_contexts_ptr
)[i
] = ipa_context_from_jfunc (parms_info
, e
,
966 /* TODO: When IPA-CP starts propagating and merging aggregate jump
967 functions, use its knowledge of the caller too, just like the
968 scalar case above. */
969 known_aggs
[i
] = &jf
->agg
;
972 else if (e
->call_stmt
&& !e
->call_stmt_cannot_inline_p
973 && ((clause_ptr
&& info
->conds
) || known_vals_ptr
))
975 int i
, count
= (int)gimple_call_num_args (e
->call_stmt
);
977 if (count
&& (info
->conds
|| known_vals_ptr
))
978 known_vals
.safe_grow_cleared (count
);
979 for (i
= 0; i
< count
; i
++)
981 tree cst
= gimple_call_arg (e
->call_stmt
, i
);
982 if (!is_gimple_min_invariant (cst
))
990 *clause_ptr
= evaluate_conditions_for_known_args (callee
, inline_p
,
991 known_vals
, known_aggs
);
994 *known_vals_ptr
= known_vals
;
996 known_vals
.release ();
999 *known_aggs_ptr
= known_aggs
;
1001 known_aggs
.release ();
1005 /* Allocate the inline summary vector or resize it to cover all cgraph nodes. */
1008 inline_summary_alloc (void)
1010 if (!edge_removal_hook_holder
)
1011 edge_removal_hook_holder
=
1012 symtab
->add_edge_removal_hook (&inline_edge_removal_hook
, NULL
);
1013 if (!edge_duplication_hook_holder
)
1014 edge_duplication_hook_holder
=
1015 symtab
->add_edge_duplication_hook (&inline_edge_duplication_hook
, NULL
);
1017 if (!inline_summaries
)
1018 inline_summaries
= (inline_summary_t
*) inline_summary_t::create_ggc (symtab
);
1020 if (inline_edge_summary_vec
.length () <= (unsigned) symtab
->edges_max_uid
)
1021 inline_edge_summary_vec
.safe_grow_cleared (symtab
->edges_max_uid
+ 1);
1024 /* We are called multiple time for given function; clear
1025 data from previous run so they are not cumulated. */
1028 reset_inline_edge_summary (struct cgraph_edge
*e
)
1030 if (e
->uid
< (int) inline_edge_summary_vec
.length ())
1032 struct inline_edge_summary
*es
= inline_edge_summary (e
);
1034 es
->call_stmt_size
= es
->call_stmt_time
= 0;
1036 edge_predicate_pool
.remove (es
->predicate
);
1037 es
->predicate
= NULL
;
1038 es
->param
.release ();
1042 /* We are called multiple time for given function; clear
1043 data from previous run so they are not cumulated. */
1046 reset_inline_summary (struct cgraph_node
*node
,
1047 inline_summary
*info
)
1049 struct cgraph_edge
*e
;
1051 info
->self_size
= info
->self_time
= 0;
1052 info
->estimated_stack_size
= 0;
1053 info
->estimated_self_stack_size
= 0;
1054 info
->stack_frame_offset
= 0;
1059 if (info
->loop_iterations
)
1061 edge_predicate_pool
.remove (info
->loop_iterations
);
1062 info
->loop_iterations
= NULL
;
1064 if (info
->loop_stride
)
1066 edge_predicate_pool
.remove (info
->loop_stride
);
1067 info
->loop_stride
= NULL
;
1069 if (info
->array_index
)
1071 edge_predicate_pool
.remove (info
->array_index
);
1072 info
->array_index
= NULL
;
1074 vec_free (info
->conds
);
1075 vec_free (info
->entry
);
1076 for (e
= node
->callees
; e
; e
= e
->next_callee
)
1077 reset_inline_edge_summary (e
);
1078 for (e
= node
->indirect_calls
; e
; e
= e
->next_callee
)
1079 reset_inline_edge_summary (e
);
1082 /* Hook that is called by cgraph.c when a node is removed. */
1085 inline_summary_t::remove (cgraph_node
*node
, inline_summary
*info
)
1087 reset_inline_summary (node
, info
);
1090 /* Remap predicate P of former function to be predicate of duplicated function.
1091 POSSIBLE_TRUTHS is clause of possible truths in the duplicated node,
1092 INFO is inline summary of the duplicated node. */
1094 static struct predicate
1095 remap_predicate_after_duplication (struct predicate
*p
,
1096 clause_t possible_truths
,
1097 struct inline_summary
*info
)
1099 struct predicate new_predicate
= true_predicate ();
1101 for (j
= 0; p
->clause
[j
]; j
++)
1102 if (!(possible_truths
& p
->clause
[j
]))
1104 new_predicate
= false_predicate ();
1108 add_clause (info
->conds
, &new_predicate
,
1109 possible_truths
& p
->clause
[j
]);
1110 return new_predicate
;
1113 /* Same as remap_predicate_after_duplication but handle hint predicate *P.
1114 Additionally care about allocating new memory slot for updated predicate
1115 and set it to NULL when it becomes true or false (and thus uninteresting).
1119 remap_hint_predicate_after_duplication (struct predicate
**p
,
1120 clause_t possible_truths
,
1121 struct inline_summary
*info
)
1123 struct predicate new_predicate
;
1128 new_predicate
= remap_predicate_after_duplication (*p
,
1129 possible_truths
, info
);
1130 /* We do not want to free previous predicate; it is used by node origin. */
1132 set_hint_predicate (p
, new_predicate
);
1136 /* Hook that is called by cgraph.c when a node is duplicated. */
1138 inline_summary_t::duplicate (cgraph_node
*src
,
1141 inline_summary
*info
)
1143 inline_summary_alloc ();
1144 memcpy (info
, inline_summaries
->get (src
), sizeof (inline_summary
));
1145 /* TODO: as an optimization, we may avoid copying conditions
1146 that are known to be false or true. */
1147 info
->conds
= vec_safe_copy (info
->conds
);
1149 /* When there are any replacements in the function body, see if we can figure
1150 out that something was optimized out. */
1151 if (ipa_node_params_sum
&& dst
->clone
.tree_map
)
1153 vec
<size_time_entry
, va_gc
> *entry
= info
->entry
;
1154 /* Use SRC parm info since it may not be copied yet. */
1155 struct ipa_node_params
*parms_info
= IPA_NODE_REF (src
);
1156 vec
<tree
> known_vals
= vNULL
;
1157 int count
= ipa_get_param_count (parms_info
);
1159 clause_t possible_truths
;
1160 struct predicate true_pred
= true_predicate ();
1162 int optimized_out_size
= 0;
1163 bool inlined_to_p
= false;
1164 struct cgraph_edge
*edge
, *next
;
1167 known_vals
.safe_grow_cleared (count
);
1168 for (i
= 0; i
< count
; i
++)
1170 struct ipa_replace_map
*r
;
1172 for (j
= 0; vec_safe_iterate (dst
->clone
.tree_map
, j
, &r
); j
++)
1174 if (((!r
->old_tree
&& r
->parm_num
== i
)
1175 || (r
->old_tree
&& r
->old_tree
== ipa_get_param (parms_info
, i
)))
1176 && r
->replace_p
&& !r
->ref_p
)
1178 known_vals
[i
] = r
->new_tree
;
1183 possible_truths
= evaluate_conditions_for_known_args (dst
, false,
1186 known_vals
.release ();
1188 account_size_time (info
, 0, 0, &true_pred
);
1190 /* Remap size_time vectors.
1191 Simplify the predicate by prunning out alternatives that are known
1193 TODO: as on optimization, we can also eliminate conditions known
1195 for (i
= 0; vec_safe_iterate (entry
, i
, &e
); i
++)
1197 struct predicate new_predicate
;
1198 new_predicate
= remap_predicate_after_duplication (&e
->predicate
,
1201 if (false_predicate_p (&new_predicate
))
1202 optimized_out_size
+= e
->size
;
1204 account_size_time (info
, e
->size
, e
->time
, &new_predicate
);
1207 /* Remap edge predicates with the same simplification as above.
1208 Also copy constantness arrays. */
1209 for (edge
= dst
->callees
; edge
; edge
= next
)
1211 struct predicate new_predicate
;
1212 struct inline_edge_summary
*es
= inline_edge_summary (edge
);
1213 next
= edge
->next_callee
;
1215 if (!edge
->inline_failed
)
1216 inlined_to_p
= true;
1219 new_predicate
= remap_predicate_after_duplication (es
->predicate
,
1222 if (false_predicate_p (&new_predicate
)
1223 && !false_predicate_p (es
->predicate
))
1224 optimized_out_size
+= es
->call_stmt_size
* INLINE_SIZE_SCALE
;
1225 edge_set_predicate (edge
, &new_predicate
);
1228 /* Remap indirect edge predicates with the same simplificaiton as above.
1229 Also copy constantness arrays. */
1230 for (edge
= dst
->indirect_calls
; edge
; edge
= next
)
1232 struct predicate new_predicate
;
1233 struct inline_edge_summary
*es
= inline_edge_summary (edge
);
1234 next
= edge
->next_callee
;
1236 gcc_checking_assert (edge
->inline_failed
);
1239 new_predicate
= remap_predicate_after_duplication (es
->predicate
,
1242 if (false_predicate_p (&new_predicate
)
1243 && !false_predicate_p (es
->predicate
))
1244 optimized_out_size
+= es
->call_stmt_size
* INLINE_SIZE_SCALE
;
1245 edge_set_predicate (edge
, &new_predicate
);
1247 remap_hint_predicate_after_duplication (&info
->loop_iterations
,
1248 possible_truths
, info
);
1249 remap_hint_predicate_after_duplication (&info
->loop_stride
,
1250 possible_truths
, info
);
1251 remap_hint_predicate_after_duplication (&info
->array_index
,
1252 possible_truths
, info
);
1254 /* If inliner or someone after inliner will ever start producing
1255 non-trivial clones, we will get trouble with lack of information
1256 about updating self sizes, because size vectors already contains
1257 sizes of the calees. */
1258 gcc_assert (!inlined_to_p
|| !optimized_out_size
);
1262 info
->entry
= vec_safe_copy (info
->entry
);
1263 if (info
->loop_iterations
)
1265 predicate p
= *info
->loop_iterations
;
1266 info
->loop_iterations
= NULL
;
1267 set_hint_predicate (&info
->loop_iterations
, p
);
1269 if (info
->loop_stride
)
1271 predicate p
= *info
->loop_stride
;
1272 info
->loop_stride
= NULL
;
1273 set_hint_predicate (&info
->loop_stride
, p
);
1275 if (info
->array_index
)
1277 predicate p
= *info
->array_index
;
1278 info
->array_index
= NULL
;
1279 set_hint_predicate (&info
->array_index
, p
);
1282 if (!dst
->global
.inlined_to
)
1283 inline_update_overall_summary (dst
);
1287 /* Hook that is called by cgraph.c when a node is duplicated. */
1290 inline_edge_duplication_hook (struct cgraph_edge
*src
,
1291 struct cgraph_edge
*dst
,
1292 ATTRIBUTE_UNUSED
void *data
)
1294 struct inline_edge_summary
*info
;
1295 struct inline_edge_summary
*srcinfo
;
1296 inline_summary_alloc ();
1297 info
= inline_edge_summary (dst
);
1298 srcinfo
= inline_edge_summary (src
);
1299 memcpy (info
, srcinfo
, sizeof (struct inline_edge_summary
));
1300 info
->predicate
= NULL
;
1301 edge_set_predicate (dst
, srcinfo
->predicate
);
1302 info
->param
= srcinfo
->param
.copy ();
1303 if (!dst
->indirect_unknown_callee
&& src
->indirect_unknown_callee
)
1305 info
->call_stmt_size
-= (eni_size_weights
.indirect_call_cost
1306 - eni_size_weights
.call_cost
);
1307 info
->call_stmt_time
-= (eni_time_weights
.indirect_call_cost
1308 - eni_time_weights
.call_cost
);
1313 /* Keep edge cache consistent across edge removal. */
1316 inline_edge_removal_hook (struct cgraph_edge
*edge
,
1317 void *data ATTRIBUTE_UNUSED
)
1319 if (edge_growth_cache
.exists ())
1320 reset_edge_growth_cache (edge
);
1321 reset_inline_edge_summary (edge
);
1325 /* Initialize growth caches. */
1328 initialize_growth_caches (void)
1330 if (symtab
->edges_max_uid
)
1331 edge_growth_cache
.safe_grow_cleared (symtab
->edges_max_uid
);
1335 /* Free growth caches. */
1338 free_growth_caches (void)
1340 edge_growth_cache
.release ();
1344 /* Dump edge summaries associated to NODE and recursively to all clones.
1345 Indent by INDENT. */
1348 dump_inline_edge_summary (FILE *f
, int indent
, struct cgraph_node
*node
,
1349 struct inline_summary
*info
)
1351 struct cgraph_edge
*edge
;
1352 for (edge
= node
->callees
; edge
; edge
= edge
->next_callee
)
1354 struct inline_edge_summary
*es
= inline_edge_summary (edge
);
1355 struct cgraph_node
*callee
= edge
->callee
->ultimate_alias_target ();
1359 "%*s%s/%i %s\n%*s loop depth:%2i freq:%4i size:%2i"
1360 " time: %2i callee size:%2i stack:%2i",
1361 indent
, "", callee
->name (), callee
->order
,
1362 !edge
->inline_failed
1363 ? "inlined" : cgraph_inline_failed_string (edge
-> inline_failed
),
1364 indent
, "", es
->loop_depth
, edge
->frequency
,
1365 es
->call_stmt_size
, es
->call_stmt_time
,
1366 (int) inline_summaries
->get (callee
)->size
/ INLINE_SIZE_SCALE
,
1367 (int) inline_summaries
->get (callee
)->estimated_stack_size
);
1371 fprintf (f
, " predicate: ");
1372 dump_predicate (f
, info
->conds
, es
->predicate
);
1376 if (es
->param
.exists ())
1377 for (i
= 0; i
< (int) es
->param
.length (); i
++)
1379 int prob
= es
->param
[i
].change_prob
;
1382 fprintf (f
, "%*s op%i is compile time invariant\n",
1384 else if (prob
!= REG_BR_PROB_BASE
)
1385 fprintf (f
, "%*s op%i change %f%% of time\n", indent
+ 2, "", i
,
1386 prob
* 100.0 / REG_BR_PROB_BASE
);
1388 if (!edge
->inline_failed
)
1390 fprintf (f
, "%*sStack frame offset %i, callee self size %i,"
1391 " callee size %i\n",
1393 (int) inline_summaries
->get (callee
)->stack_frame_offset
,
1394 (int) inline_summaries
->get (callee
)->estimated_self_stack_size
,
1395 (int) inline_summaries
->get (callee
)->estimated_stack_size
);
1396 dump_inline_edge_summary (f
, indent
+ 2, callee
, info
);
1399 for (edge
= node
->indirect_calls
; edge
; edge
= edge
->next_callee
)
1401 struct inline_edge_summary
*es
= inline_edge_summary (edge
);
1402 fprintf (f
, "%*sindirect call loop depth:%2i freq:%4i size:%2i"
1406 edge
->frequency
, es
->call_stmt_size
, es
->call_stmt_time
);
1409 fprintf (f
, "predicate: ");
1410 dump_predicate (f
, info
->conds
, es
->predicate
);
1419 dump_inline_summary (FILE *f
, struct cgraph_node
*node
)
1421 if (node
->definition
)
1423 struct inline_summary
*s
= inline_summaries
->get (node
);
1426 fprintf (f
, "Inline summary for %s/%i", node
->name (),
1428 if (DECL_DISREGARD_INLINE_LIMITS (node
->decl
))
1429 fprintf (f
, " always_inline");
1431 fprintf (f
, " inlinable");
1432 if (s
->contains_cilk_spawn
)
1433 fprintf (f
, " contains_cilk_spawn");
1434 fprintf (f
, "\n self time: %i\n", s
->self_time
);
1435 fprintf (f
, " global time: %i\n", s
->time
);
1436 fprintf (f
, " self size: %i\n", s
->self_size
);
1437 fprintf (f
, " global size: %i\n", s
->size
);
1438 fprintf (f
, " min size: %i\n", s
->min_size
);
1439 fprintf (f
, " self stack: %i\n",
1440 (int) s
->estimated_self_stack_size
);
1441 fprintf (f
, " global stack: %i\n", (int) s
->estimated_stack_size
);
1443 fprintf (f
, " estimated growth:%i\n", (int) s
->growth
);
1445 fprintf (f
, " In SCC: %i\n", (int) s
->scc_no
);
1446 for (i
= 0; vec_safe_iterate (s
->entry
, i
, &e
); i
++)
1448 fprintf (f
, " size:%f, time:%f, predicate:",
1449 (double) e
->size
/ INLINE_SIZE_SCALE
,
1450 (double) e
->time
/ INLINE_TIME_SCALE
);
1451 dump_predicate (f
, s
->conds
, &e
->predicate
);
1453 if (s
->loop_iterations
)
1455 fprintf (f
, " loop iterations:");
1456 dump_predicate (f
, s
->conds
, s
->loop_iterations
);
1460 fprintf (f
, " loop stride:");
1461 dump_predicate (f
, s
->conds
, s
->loop_stride
);
1465 fprintf (f
, " array index:");
1466 dump_predicate (f
, s
->conds
, s
->array_index
);
1468 fprintf (f
, " calls:\n");
1469 dump_inline_edge_summary (f
, 4, node
, s
);
1475 debug_inline_summary (struct cgraph_node
*node
)
1477 dump_inline_summary (stderr
, node
);
1481 dump_inline_summaries (FILE *f
)
1483 struct cgraph_node
*node
;
1485 FOR_EACH_DEFINED_FUNCTION (node
)
1486 if (!node
->global
.inlined_to
)
1487 dump_inline_summary (f
, node
);
1490 /* Give initial reasons why inlining would fail on EDGE. This gets either
1491 nullified or usually overwritten by more precise reasons later. */
1494 initialize_inline_failed (struct cgraph_edge
*e
)
1496 struct cgraph_node
*callee
= e
->callee
;
1498 if (e
->indirect_unknown_callee
)
1499 e
->inline_failed
= CIF_INDIRECT_UNKNOWN_CALL
;
1500 else if (!callee
->definition
)
1501 e
->inline_failed
= CIF_BODY_NOT_AVAILABLE
;
1502 else if (callee
->local
.redefined_extern_inline
)
1503 e
->inline_failed
= CIF_REDEFINED_EXTERN_INLINE
;
1504 else if (e
->call_stmt_cannot_inline_p
)
1505 e
->inline_failed
= CIF_MISMATCHED_ARGUMENTS
;
1506 else if (cfun
&& fn_contains_cilk_spawn_p (cfun
))
1507 /* We can't inline if the function is spawing a function. */
1508 e
->inline_failed
= CIF_FUNCTION_NOT_INLINABLE
;
1510 e
->inline_failed
= CIF_FUNCTION_NOT_CONSIDERED
;
1513 /* Callback of walk_aliased_vdefs. Flags that it has been invoked to the
1514 boolean variable pointed to by DATA. */
1517 mark_modified (ao_ref
*ao ATTRIBUTE_UNUSED
, tree vdef ATTRIBUTE_UNUSED
,
1520 bool *b
= (bool *) data
;
1525 /* If OP refers to value of function parameter, return the corresponding
1529 unmodified_parm_1 (gimple stmt
, tree op
)
1531 /* SSA_NAME referring to parm default def? */
1532 if (TREE_CODE (op
) == SSA_NAME
1533 && SSA_NAME_IS_DEFAULT_DEF (op
)
1534 && TREE_CODE (SSA_NAME_VAR (op
)) == PARM_DECL
)
1535 return SSA_NAME_VAR (op
);
1536 /* Non-SSA parm reference? */
1537 if (TREE_CODE (op
) == PARM_DECL
)
1539 bool modified
= false;
1542 ao_ref_init (&refd
, op
);
1543 walk_aliased_vdefs (&refd
, gimple_vuse (stmt
), mark_modified
, &modified
,
1551 /* If OP refers to value of function parameter, return the corresponding
1552 parameter. Also traverse chains of SSA register assignments. */
1555 unmodified_parm (gimple stmt
, tree op
)
1557 tree res
= unmodified_parm_1 (stmt
, op
);
1561 if (TREE_CODE (op
) == SSA_NAME
1562 && !SSA_NAME_IS_DEFAULT_DEF (op
)
1563 && gimple_assign_single_p (SSA_NAME_DEF_STMT (op
)))
1564 return unmodified_parm (SSA_NAME_DEF_STMT (op
),
1565 gimple_assign_rhs1 (SSA_NAME_DEF_STMT (op
)));
1569 /* If OP refers to a value of a function parameter or value loaded from an
1570 aggregate passed to a parameter (either by value or reference), return TRUE
1571 and store the number of the parameter to *INDEX_P and information whether
1572 and how it has been loaded from an aggregate into *AGGPOS. INFO describes
1573 the function parameters, STMT is the statement in which OP is used or
1577 unmodified_parm_or_parm_agg_item (struct ipa_node_params
*info
,
1578 gimple stmt
, tree op
, int *index_p
,
1579 struct agg_position_info
*aggpos
)
1581 tree res
= unmodified_parm_1 (stmt
, op
);
1583 gcc_checking_assert (aggpos
);
1586 *index_p
= ipa_get_param_decl_index (info
, res
);
1589 aggpos
->agg_contents
= false;
1590 aggpos
->by_ref
= false;
1594 if (TREE_CODE (op
) == SSA_NAME
)
1596 if (SSA_NAME_IS_DEFAULT_DEF (op
)
1597 || !gimple_assign_single_p (SSA_NAME_DEF_STMT (op
)))
1599 stmt
= SSA_NAME_DEF_STMT (op
);
1600 op
= gimple_assign_rhs1 (stmt
);
1601 if (!REFERENCE_CLASS_P (op
))
1602 return unmodified_parm_or_parm_agg_item (info
, stmt
, op
, index_p
,
1606 aggpos
->agg_contents
= true;
1607 return ipa_load_from_parm_agg (info
, stmt
, op
, index_p
, &aggpos
->offset
,
1611 /* See if statement might disappear after inlining.
1612 0 - means not eliminated
1613 1 - half of statements goes away
1614 2 - for sure it is eliminated.
1615 We are not terribly sophisticated, basically looking for simple abstraction
1616 penalty wrappers. */
1619 eliminated_by_inlining_prob (gimple stmt
)
1621 enum gimple_code code
= gimple_code (stmt
);
1622 enum tree_code rhs_code
;
1632 if (gimple_num_ops (stmt
) != 2)
1635 rhs_code
= gimple_assign_rhs_code (stmt
);
1637 /* Casts of parameters, loads from parameters passed by reference
1638 and stores to return value or parameters are often free after
1639 inlining dua to SRA and further combining.
1640 Assume that half of statements goes away. */
1641 if (CONVERT_EXPR_CODE_P (rhs_code
)
1642 || rhs_code
== VIEW_CONVERT_EXPR
1643 || rhs_code
== ADDR_EXPR
1644 || gimple_assign_rhs_class (stmt
) == GIMPLE_SINGLE_RHS
)
1646 tree rhs
= gimple_assign_rhs1 (stmt
);
1647 tree lhs
= gimple_assign_lhs (stmt
);
1648 tree inner_rhs
= get_base_address (rhs
);
1649 tree inner_lhs
= get_base_address (lhs
);
1650 bool rhs_free
= false;
1651 bool lhs_free
= false;
1658 /* Reads of parameter are expected to be free. */
1659 if (unmodified_parm (stmt
, inner_rhs
))
1661 /* Match expressions of form &this->field. Those will most likely
1662 combine with something upstream after inlining. */
1663 else if (TREE_CODE (inner_rhs
) == ADDR_EXPR
)
1665 tree op
= get_base_address (TREE_OPERAND (inner_rhs
, 0));
1666 if (TREE_CODE (op
) == PARM_DECL
)
1668 else if (TREE_CODE (op
) == MEM_REF
1669 && unmodified_parm (stmt
, TREE_OPERAND (op
, 0)))
1673 /* When parameter is not SSA register because its address is taken
1674 and it is just copied into one, the statement will be completely
1675 free after inlining (we will copy propagate backward). */
1676 if (rhs_free
&& is_gimple_reg (lhs
))
1679 /* Reads of parameters passed by reference
1680 expected to be free (i.e. optimized out after inlining). */
1681 if (TREE_CODE (inner_rhs
) == MEM_REF
1682 && unmodified_parm (stmt
, TREE_OPERAND (inner_rhs
, 0)))
1685 /* Copying parameter passed by reference into gimple register is
1686 probably also going to copy propagate, but we can't be quite
1688 if (rhs_free
&& is_gimple_reg (lhs
))
1691 /* Writes to parameters, parameters passed by value and return value
1692 (either dirrectly or passed via invisible reference) are free.
1694 TODO: We ought to handle testcase like
1695 struct a {int a,b;};
1697 retrurnsturct (void)
1703 This translate into:
1718 For that we either need to copy ipa-split logic detecting writes
1720 if (TREE_CODE (inner_lhs
) == PARM_DECL
1721 || TREE_CODE (inner_lhs
) == RESULT_DECL
1722 || (TREE_CODE (inner_lhs
) == MEM_REF
1723 && (unmodified_parm (stmt
, TREE_OPERAND (inner_lhs
, 0))
1724 || (TREE_CODE (TREE_OPERAND (inner_lhs
, 0)) == SSA_NAME
1725 && SSA_NAME_VAR (TREE_OPERAND (inner_lhs
, 0))
1726 && TREE_CODE (SSA_NAME_VAR (TREE_OPERAND
1728 0))) == RESULT_DECL
))))
1731 && (is_gimple_reg (rhs
) || is_gimple_min_invariant (rhs
)))
1733 if (lhs_free
&& rhs_free
)
1743 /* If BB ends by a conditional we can turn into predicates, attach corresponding
1744 predicates to the CFG edges. */
1747 set_cond_stmt_execution_predicate (struct ipa_node_params
*info
,
1748 struct inline_summary
*summary
,
1754 struct agg_position_info aggpos
;
1755 enum tree_code code
, inverted_code
;
1761 last
= last_stmt (bb
);
1762 if (!last
|| gimple_code (last
) != GIMPLE_COND
)
1764 if (!is_gimple_ip_invariant (gimple_cond_rhs (last
)))
1766 op
= gimple_cond_lhs (last
);
1767 /* TODO: handle conditionals like
1770 if (unmodified_parm_or_parm_agg_item (info
, last
, op
, &index
, &aggpos
))
1772 code
= gimple_cond_code (last
);
1773 inverted_code
= invert_tree_comparison (code
, HONOR_NANS (op
));
1775 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1777 enum tree_code this_code
= (e
->flags
& EDGE_TRUE_VALUE
1778 ? code
: inverted_code
);
1779 /* invert_tree_comparison will return ERROR_MARK on FP
1780 comparsions that are not EQ/NE instead of returning proper
1781 unordered one. Be sure it is not confused with NON_CONSTANT. */
1782 if (this_code
!= ERROR_MARK
)
1784 struct predicate p
= add_condition (summary
, index
, &aggpos
,
1786 gimple_cond_rhs (last
));
1787 e
->aux
= edge_predicate_pool
.allocate ();
1788 *(struct predicate
*) e
->aux
= p
;
1793 if (TREE_CODE (op
) != SSA_NAME
)
1796 if (builtin_constant_p (op))
1800 Here we can predicate nonconstant_code. We can't
1801 really handle constant_code since we have no predicate
1802 for this and also the constant code is not known to be
1803 optimized away when inliner doen't see operand is constant.
1804 Other optimizers might think otherwise. */
1805 if (gimple_cond_code (last
) != NE_EXPR
1806 || !integer_zerop (gimple_cond_rhs (last
)))
1808 set_stmt
= SSA_NAME_DEF_STMT (op
);
1809 if (!gimple_call_builtin_p (set_stmt
, BUILT_IN_CONSTANT_P
)
1810 || gimple_call_num_args (set_stmt
) != 1)
1812 op2
= gimple_call_arg (set_stmt
, 0);
1813 if (!unmodified_parm_or_parm_agg_item
1814 (info
, set_stmt
, op2
, &index
, &aggpos
))
1816 FOR_EACH_EDGE (e
, ei
, bb
->succs
) if (e
->flags
& EDGE_FALSE_VALUE
)
1818 struct predicate p
= add_condition (summary
, index
, &aggpos
,
1819 IS_NOT_CONSTANT
, NULL_TREE
);
1820 e
->aux
= edge_predicate_pool
.allocate ();
1821 *(struct predicate
*) e
->aux
= p
;
1826 /* If BB ends by a switch we can turn into predicates, attach corresponding
1827 predicates to the CFG edges. */
1830 set_switch_stmt_execution_predicate (struct ipa_node_params
*info
,
1831 struct inline_summary
*summary
,
1837 struct agg_position_info aggpos
;
1843 lastg
= last_stmt (bb
);
1844 if (!lastg
|| gimple_code (lastg
) != GIMPLE_SWITCH
)
1846 gswitch
*last
= as_a
<gswitch
*> (lastg
);
1847 op
= gimple_switch_index (last
);
1848 if (!unmodified_parm_or_parm_agg_item (info
, last
, op
, &index
, &aggpos
))
1851 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1853 e
->aux
= edge_predicate_pool
.allocate ();
1854 *(struct predicate
*) e
->aux
= false_predicate ();
1856 n
= gimple_switch_num_labels (last
);
1857 for (case_idx
= 0; case_idx
< n
; ++case_idx
)
1859 tree cl
= gimple_switch_label (last
, case_idx
);
1863 e
= find_edge (bb
, label_to_block (CASE_LABEL (cl
)));
1864 min
= CASE_LOW (cl
);
1865 max
= CASE_HIGH (cl
);
1867 /* For default we might want to construct predicate that none
1868 of cases is met, but it is bit hard to do not having negations
1869 of conditionals handy. */
1871 p
= true_predicate ();
1873 p
= add_condition (summary
, index
, &aggpos
, EQ_EXPR
, min
);
1876 struct predicate p1
, p2
;
1877 p1
= add_condition (summary
, index
, &aggpos
, GE_EXPR
, min
);
1878 p2
= add_condition (summary
, index
, &aggpos
, LE_EXPR
, max
);
1879 p
= and_predicates (summary
->conds
, &p1
, &p2
);
1881 *(struct predicate
*) e
->aux
1882 = or_predicates (summary
->conds
, &p
, (struct predicate
*) e
->aux
);
1887 /* For each BB in NODE attach to its AUX pointer predicate under
1888 which it is executable. */
1891 compute_bb_predicates (struct cgraph_node
*node
,
1892 struct ipa_node_params
*parms_info
,
1893 struct inline_summary
*summary
)
1895 struct function
*my_function
= DECL_STRUCT_FUNCTION (node
->decl
);
1899 FOR_EACH_BB_FN (bb
, my_function
)
1901 set_cond_stmt_execution_predicate (parms_info
, summary
, bb
);
1902 set_switch_stmt_execution_predicate (parms_info
, summary
, bb
);
1905 /* Entry block is always executable. */
1906 ENTRY_BLOCK_PTR_FOR_FN (my_function
)->aux
1907 = edge_predicate_pool
.allocate ();
1908 *(struct predicate
*) ENTRY_BLOCK_PTR_FOR_FN (my_function
)->aux
1909 = true_predicate ();
1911 /* A simple dataflow propagation of predicates forward in the CFG.
1912 TODO: work in reverse postorder. */
1916 FOR_EACH_BB_FN (bb
, my_function
)
1918 struct predicate p
= false_predicate ();
1921 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
1925 struct predicate this_bb_predicate
1926 = *(struct predicate
*) e
->src
->aux
;
1929 = and_predicates (summary
->conds
, &this_bb_predicate
,
1930 (struct predicate
*) e
->aux
);
1931 p
= or_predicates (summary
->conds
, &p
, &this_bb_predicate
);
1932 if (true_predicate_p (&p
))
1936 if (false_predicate_p (&p
))
1937 gcc_assert (!bb
->aux
);
1943 bb
->aux
= edge_predicate_pool
.allocate ();
1944 *((struct predicate
*) bb
->aux
) = p
;
1946 else if (!predicates_equal_p (&p
, (struct predicate
*) bb
->aux
))
1948 /* This OR operation is needed to ensure monotonous data flow
1949 in the case we hit the limit on number of clauses and the
1950 and/or operations above give approximate answers. */
1951 p
= or_predicates (summary
->conds
, &p
, (struct predicate
*)bb
->aux
);
1952 if (!predicates_equal_p (&p
, (struct predicate
*) bb
->aux
))
1955 *((struct predicate
*) bb
->aux
) = p
;
1964 /* We keep info about constantness of SSA names. */
1966 typedef struct predicate predicate_t
;
1967 /* Return predicate specifying when the STMT might have result that is not
1968 a compile time constant. */
1970 static struct predicate
1971 will_be_nonconstant_expr_predicate (struct ipa_node_params
*info
,
1972 struct inline_summary
*summary
,
1974 vec
<predicate_t
> nonconstant_names
)
1979 while (UNARY_CLASS_P (expr
))
1980 expr
= TREE_OPERAND (expr
, 0);
1982 parm
= unmodified_parm (NULL
, expr
);
1983 if (parm
&& (index
= ipa_get_param_decl_index (info
, parm
)) >= 0)
1984 return add_condition (summary
, index
, NULL
, CHANGED
, NULL_TREE
);
1985 if (is_gimple_min_invariant (expr
))
1986 return false_predicate ();
1987 if (TREE_CODE (expr
) == SSA_NAME
)
1988 return nonconstant_names
[SSA_NAME_VERSION (expr
)];
1989 if (BINARY_CLASS_P (expr
) || COMPARISON_CLASS_P (expr
))
1991 struct predicate p1
= will_be_nonconstant_expr_predicate
1992 (info
, summary
, TREE_OPERAND (expr
, 0),
1994 struct predicate p2
;
1995 if (true_predicate_p (&p1
))
1997 p2
= will_be_nonconstant_expr_predicate (info
, summary
,
1998 TREE_OPERAND (expr
, 1),
2000 return or_predicates (summary
->conds
, &p1
, &p2
);
2002 else if (TREE_CODE (expr
) == COND_EXPR
)
2004 struct predicate p1
= will_be_nonconstant_expr_predicate
2005 (info
, summary
, TREE_OPERAND (expr
, 0),
2007 struct predicate p2
;
2008 if (true_predicate_p (&p1
))
2010 p2
= will_be_nonconstant_expr_predicate (info
, summary
,
2011 TREE_OPERAND (expr
, 1),
2013 if (true_predicate_p (&p2
))
2015 p1
= or_predicates (summary
->conds
, &p1
, &p2
);
2016 p2
= will_be_nonconstant_expr_predicate (info
, summary
,
2017 TREE_OPERAND (expr
, 2),
2019 return or_predicates (summary
->conds
, &p1
, &p2
);
2026 return false_predicate ();
2030 /* Return predicate specifying when the STMT might have result that is not
2031 a compile time constant. */
2033 static struct predicate
2034 will_be_nonconstant_predicate (struct ipa_node_params
*info
,
2035 struct inline_summary
*summary
,
2037 vec
<predicate_t
> nonconstant_names
)
2039 struct predicate p
= true_predicate ();
2042 struct predicate op_non_const
;
2045 struct agg_position_info aggpos
;
2047 /* What statments might be optimized away
2048 when their arguments are constant. */
2049 if (gimple_code (stmt
) != GIMPLE_ASSIGN
2050 && gimple_code (stmt
) != GIMPLE_COND
2051 && gimple_code (stmt
) != GIMPLE_SWITCH
2052 && (gimple_code (stmt
) != GIMPLE_CALL
2053 || !(gimple_call_flags (stmt
) & ECF_CONST
)))
2056 /* Stores will stay anyway. */
2057 if (gimple_store_p (stmt
))
2060 is_load
= gimple_assign_load_p (stmt
);
2062 /* Loads can be optimized when the value is known. */
2066 gcc_assert (gimple_assign_single_p (stmt
));
2067 op
= gimple_assign_rhs1 (stmt
);
2068 if (!unmodified_parm_or_parm_agg_item (info
, stmt
, op
, &base_index
,
2075 /* See if we understand all operands before we start
2076 adding conditionals. */
2077 FOR_EACH_SSA_TREE_OPERAND (use
, stmt
, iter
, SSA_OP_USE
)
2079 tree parm
= unmodified_parm (stmt
, use
);
2080 /* For arguments we can build a condition. */
2081 if (parm
&& ipa_get_param_decl_index (info
, parm
) >= 0)
2083 if (TREE_CODE (use
) != SSA_NAME
)
2085 /* If we know when operand is constant,
2086 we still can say something useful. */
2087 if (!true_predicate_p (&nonconstant_names
[SSA_NAME_VERSION (use
)]))
2094 add_condition (summary
, base_index
, &aggpos
, CHANGED
, NULL
);
2096 op_non_const
= false_predicate ();
2097 FOR_EACH_SSA_TREE_OPERAND (use
, stmt
, iter
, SSA_OP_USE
)
2099 tree parm
= unmodified_parm (stmt
, use
);
2102 if (parm
&& (index
= ipa_get_param_decl_index (info
, parm
)) >= 0)
2104 if (index
!= base_index
)
2105 p
= add_condition (summary
, index
, NULL
, CHANGED
, NULL_TREE
);
2110 p
= nonconstant_names
[SSA_NAME_VERSION (use
)];
2111 op_non_const
= or_predicates (summary
->conds
, &p
, &op_non_const
);
2113 if ((gimple_code (stmt
) == GIMPLE_ASSIGN
|| gimple_code (stmt
) == GIMPLE_CALL
)
2114 && gimple_op (stmt
, 0)
2115 && TREE_CODE (gimple_op (stmt
, 0)) == SSA_NAME
)
2116 nonconstant_names
[SSA_NAME_VERSION (gimple_op (stmt
, 0))]
2118 return op_non_const
;
2121 struct record_modified_bb_info
2127 /* Callback of walk_aliased_vdefs. Records basic blocks where the value may be
2128 set except for info->stmt. */
2131 record_modified (ao_ref
*ao ATTRIBUTE_UNUSED
, tree vdef
, void *data
)
2133 struct record_modified_bb_info
*info
=
2134 (struct record_modified_bb_info
*) data
;
2135 if (SSA_NAME_DEF_STMT (vdef
) == info
->stmt
)
2137 bitmap_set_bit (info
->bb_set
,
2138 SSA_NAME_IS_DEFAULT_DEF (vdef
)
2139 ? ENTRY_BLOCK_PTR_FOR_FN (cfun
)->index
2140 : gimple_bb (SSA_NAME_DEF_STMT (vdef
))->index
);
2144 /* Return probability (based on REG_BR_PROB_BASE) that I-th parameter of STMT
2145 will change since last invocation of STMT.
2147 Value 0 is reserved for compile time invariants.
2148 For common parameters it is REG_BR_PROB_BASE. For loop invariants it
2149 ought to be REG_BR_PROB_BASE / estimated_iters. */
2152 param_change_prob (gimple stmt
, int i
)
2154 tree op
= gimple_call_arg (stmt
, i
);
2155 basic_block bb
= gimple_bb (stmt
);
2158 /* Global invariants neve change. */
2159 if (is_gimple_min_invariant (op
))
2161 /* We would have to do non-trivial analysis to really work out what
2162 is the probability of value to change (i.e. when init statement
2163 is in a sibling loop of the call).
2165 We do an conservative estimate: when call is executed N times more often
2166 than the statement defining value, we take the frequency 1/N. */
2167 if (TREE_CODE (op
) == SSA_NAME
)
2172 return REG_BR_PROB_BASE
;
2174 if (SSA_NAME_IS_DEFAULT_DEF (op
))
2175 init_freq
= ENTRY_BLOCK_PTR_FOR_FN (cfun
)->frequency
;
2177 init_freq
= gimple_bb (SSA_NAME_DEF_STMT (op
))->frequency
;
2181 if (init_freq
< bb
->frequency
)
2182 return MAX (GCOV_COMPUTE_SCALE (init_freq
, bb
->frequency
), 1);
2184 return REG_BR_PROB_BASE
;
2187 base
= get_base_address (op
);
2192 struct record_modified_bb_info info
;
2195 tree init
= ctor_for_folding (base
);
2197 if (init
!= error_mark_node
)
2200 return REG_BR_PROB_BASE
;
2201 ao_ref_init (&refd
, op
);
2203 info
.bb_set
= BITMAP_ALLOC (NULL
);
2204 walk_aliased_vdefs (&refd
, gimple_vuse (stmt
), record_modified
, &info
,
2206 if (bitmap_bit_p (info
.bb_set
, bb
->index
))
2208 BITMAP_FREE (info
.bb_set
);
2209 return REG_BR_PROB_BASE
;
2212 /* Assume that every memory is initialized at entry.
2213 TODO: Can we easilly determine if value is always defined
2214 and thus we may skip entry block? */
2215 if (ENTRY_BLOCK_PTR_FOR_FN (cfun
)->frequency
)
2216 max
= ENTRY_BLOCK_PTR_FOR_FN (cfun
)->frequency
;
2220 EXECUTE_IF_SET_IN_BITMAP (info
.bb_set
, 0, index
, bi
)
2221 max
= MIN (max
, BASIC_BLOCK_FOR_FN (cfun
, index
)->frequency
);
2223 BITMAP_FREE (info
.bb_set
);
2224 if (max
< bb
->frequency
)
2225 return MAX (GCOV_COMPUTE_SCALE (max
, bb
->frequency
), 1);
2227 return REG_BR_PROB_BASE
;
2229 return REG_BR_PROB_BASE
;
2232 /* Find whether a basic block BB is the final block of a (half) diamond CFG
2233 sub-graph and if the predicate the condition depends on is known. If so,
2234 return true and store the pointer the predicate in *P. */
2237 phi_result_unknown_predicate (struct ipa_node_params
*info
,
2238 inline_summary
*summary
, basic_block bb
,
2239 struct predicate
*p
,
2240 vec
<predicate_t
> nonconstant_names
)
2244 basic_block first_bb
= NULL
;
2247 if (single_pred_p (bb
))
2249 *p
= false_predicate ();
2253 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
2255 if (single_succ_p (e
->src
))
2257 if (!single_pred_p (e
->src
))
2260 first_bb
= single_pred (e
->src
);
2261 else if (single_pred (e
->src
) != first_bb
)
2268 else if (e
->src
!= first_bb
)
2276 stmt
= last_stmt (first_bb
);
2278 || gimple_code (stmt
) != GIMPLE_COND
2279 || !is_gimple_ip_invariant (gimple_cond_rhs (stmt
)))
2282 *p
= will_be_nonconstant_expr_predicate (info
, summary
,
2283 gimple_cond_lhs (stmt
),
2285 if (true_predicate_p (p
))
2291 /* Given a PHI statement in a function described by inline properties SUMMARY
2292 and *P being the predicate describing whether the selected PHI argument is
2293 known, store a predicate for the result of the PHI statement into
2294 NONCONSTANT_NAMES, if possible. */
2297 predicate_for_phi_result (struct inline_summary
*summary
, gphi
*phi
,
2298 struct predicate
*p
,
2299 vec
<predicate_t
> nonconstant_names
)
2303 for (i
= 0; i
< gimple_phi_num_args (phi
); i
++)
2305 tree arg
= gimple_phi_arg (phi
, i
)->def
;
2306 if (!is_gimple_min_invariant (arg
))
2308 gcc_assert (TREE_CODE (arg
) == SSA_NAME
);
2309 *p
= or_predicates (summary
->conds
, p
,
2310 &nonconstant_names
[SSA_NAME_VERSION (arg
)]);
2311 if (true_predicate_p (p
))
2316 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2318 fprintf (dump_file
, "\t\tphi predicate: ");
2319 dump_predicate (dump_file
, summary
->conds
, p
);
2321 nonconstant_names
[SSA_NAME_VERSION (gimple_phi_result (phi
))] = *p
;
2324 /* Return predicate specifying when array index in access OP becomes non-constant. */
2326 static struct predicate
2327 array_index_predicate (inline_summary
*info
,
2328 vec
< predicate_t
> nonconstant_names
, tree op
)
2330 struct predicate p
= false_predicate ();
2331 while (handled_component_p (op
))
2333 if (TREE_CODE (op
) == ARRAY_REF
|| TREE_CODE (op
) == ARRAY_RANGE_REF
)
2335 if (TREE_CODE (TREE_OPERAND (op
, 1)) == SSA_NAME
)
2336 p
= or_predicates (info
->conds
, &p
,
2337 &nonconstant_names
[SSA_NAME_VERSION
2338 (TREE_OPERAND (op
, 1))]);
2340 op
= TREE_OPERAND (op
, 0);
2345 /* For a typical usage of __builtin_expect (a<b, 1), we
2346 may introduce an extra relation stmt:
2347 With the builtin, we have
2350 t3 = __builtin_expect (t2, 1);
2353 Without the builtin, we have
2356 This affects the size/time estimation and may have
2357 an impact on the earlier inlining.
2358 Here find this pattern and fix it up later. */
2361 find_foldable_builtin_expect (basic_block bb
)
2363 gimple_stmt_iterator bsi
;
2365 for (bsi
= gsi_start_bb (bb
); !gsi_end_p (bsi
); gsi_next (&bsi
))
2367 gimple stmt
= gsi_stmt (bsi
);
2368 if (gimple_call_builtin_p (stmt
, BUILT_IN_EXPECT
)
2369 || (is_gimple_call (stmt
)
2370 && gimple_call_internal_p (stmt
)
2371 && gimple_call_internal_fn (stmt
) == IFN_BUILTIN_EXPECT
))
2373 tree var
= gimple_call_lhs (stmt
);
2374 tree arg
= gimple_call_arg (stmt
, 0);
2375 use_operand_p use_p
;
2382 gcc_assert (TREE_CODE (var
) == SSA_NAME
);
2384 while (TREE_CODE (arg
) == SSA_NAME
)
2386 gimple stmt_tmp
= SSA_NAME_DEF_STMT (arg
);
2387 if (!is_gimple_assign (stmt_tmp
))
2389 switch (gimple_assign_rhs_code (stmt_tmp
))
2408 arg
= gimple_assign_rhs1 (stmt_tmp
);
2411 if (match
&& single_imm_use (var
, &use_p
, &use_stmt
)
2412 && gimple_code (use_stmt
) == GIMPLE_COND
)
2419 /* Return true when the basic blocks contains only clobbers followed by RESX.
2420 Such BBs are kept around to make removal of dead stores possible with
2421 presence of EH and will be optimized out by optimize_clobbers later in the
2424 NEED_EH is used to recurse in case the clobber has non-EH predecestors
2425 that can be clobber only, too.. When it is false, the RESX is not necessary
2426 on the end of basic block. */
2429 clobber_only_eh_bb_p (basic_block bb
, bool need_eh
= true)
2431 gimple_stmt_iterator gsi
= gsi_last_bb (bb
);
2437 if (gsi_end_p (gsi
))
2439 if (gimple_code (gsi_stmt (gsi
)) != GIMPLE_RESX
)
2443 else if (!single_succ_p (bb
))
2446 for (; !gsi_end_p (gsi
); gsi_prev (&gsi
))
2448 gimple stmt
= gsi_stmt (gsi
);
2449 if (is_gimple_debug (stmt
))
2451 if (gimple_clobber_p (stmt
))
2453 if (gimple_code (stmt
) == GIMPLE_LABEL
)
2458 /* See if all predecestors are either throws or clobber only BBs. */
2459 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
2460 if (!(e
->flags
& EDGE_EH
)
2461 && !clobber_only_eh_bb_p (e
->src
, false))
2467 /* Compute function body size parameters for NODE.
2468 When EARLY is true, we compute only simple summaries without
2469 non-trivial predicates to drive the early inliner. */
2472 estimate_function_body_sizes (struct cgraph_node
*node
, bool early
)
2475 /* Estimate static overhead for function prologue/epilogue and alignment. */
2477 /* Benefits are scaled by probability of elimination that is in range
2480 struct function
*my_function
= DECL_STRUCT_FUNCTION (node
->decl
);
2482 struct inline_summary
*info
= inline_summaries
->get (node
);
2483 struct predicate bb_predicate
;
2484 struct ipa_node_params
*parms_info
= NULL
;
2485 vec
<predicate_t
> nonconstant_names
= vNULL
;
2488 predicate array_index
= true_predicate ();
2489 gimple fix_builtin_expect_stmt
;
2494 /* When optimizing and analyzing for IPA inliner, initialize loop optimizer
2495 so we can produce proper inline hints.
2497 When optimizing and analyzing for early inliner, initialize node params
2498 so we can produce correct BB predicates. */
2500 if (opt_for_fn (node
->decl
, optimize
))
2502 calculate_dominance_info (CDI_DOMINATORS
);
2504 loop_optimizer_init (LOOPS_NORMAL
| LOOPS_HAVE_RECORDED_EXITS
);
2507 ipa_check_create_node_params ();
2508 ipa_initialize_node_params (node
);
2511 if (ipa_node_params_sum
)
2513 parms_info
= IPA_NODE_REF (node
);
2514 nonconstant_names
.safe_grow_cleared
2515 (SSANAMES (my_function
)->length ());
2520 fprintf (dump_file
, "\nAnalyzing function body size: %s\n",
2523 /* When we run into maximal number of entries, we assign everything to the
2524 constant truth case. Be sure to have it in list. */
2525 bb_predicate
= true_predicate ();
2526 account_size_time (info
, 0, 0, &bb_predicate
);
2528 bb_predicate
= not_inlined_predicate ();
2529 account_size_time (info
, 2 * INLINE_SIZE_SCALE
, 0, &bb_predicate
);
2531 gcc_assert (my_function
&& my_function
->cfg
);
2533 compute_bb_predicates (node
, parms_info
, info
);
2534 gcc_assert (cfun
== my_function
);
2535 order
= XNEWVEC (int, n_basic_blocks_for_fn (cfun
));
2536 nblocks
= pre_and_rev_post_order_compute (NULL
, order
, false);
2537 for (n
= 0; n
< nblocks
; n
++)
2539 bb
= BASIC_BLOCK_FOR_FN (cfun
, order
[n
]);
2540 freq
= compute_call_stmt_bb_frequency (node
->decl
, bb
);
2541 if (clobber_only_eh_bb_p (bb
))
2543 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2544 fprintf (dump_file
, "\n Ignoring BB %i;"
2545 " it will be optimized away by cleanup_clobbers\n",
2550 /* TODO: Obviously predicates can be propagated down across CFG. */
2554 bb_predicate
= *(struct predicate
*) bb
->aux
;
2556 bb_predicate
= false_predicate ();
2559 bb_predicate
= true_predicate ();
2561 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2563 fprintf (dump_file
, "\n BB %i predicate:", bb
->index
);
2564 dump_predicate (dump_file
, info
->conds
, &bb_predicate
);
2567 if (parms_info
&& nonconstant_names
.exists ())
2569 struct predicate phi_predicate
;
2570 bool first_phi
= true;
2572 for (gphi_iterator bsi
= gsi_start_phis (bb
); !gsi_end_p (bsi
);
2576 && !phi_result_unknown_predicate (parms_info
, info
, bb
,
2581 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2583 fprintf (dump_file
, " ");
2584 print_gimple_stmt (dump_file
, gsi_stmt (bsi
), 0, 0);
2586 predicate_for_phi_result (info
, bsi
.phi (), &phi_predicate
,
2591 fix_builtin_expect_stmt
= find_foldable_builtin_expect (bb
);
2593 for (gimple_stmt_iterator bsi
= gsi_start_bb (bb
); !gsi_end_p (bsi
);
2596 gimple stmt
= gsi_stmt (bsi
);
2597 int this_size
= estimate_num_insns (stmt
, &eni_size_weights
);
2598 int this_time
= estimate_num_insns (stmt
, &eni_time_weights
);
2600 struct predicate will_be_nonconstant
;
2602 /* This relation stmt should be folded after we remove
2603 buildin_expect call. Adjust the cost here. */
2604 if (stmt
== fix_builtin_expect_stmt
)
2610 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2612 fprintf (dump_file
, " ");
2613 print_gimple_stmt (dump_file
, stmt
, 0, 0);
2614 fprintf (dump_file
, "\t\tfreq:%3.2f size:%3i time:%3i\n",
2615 ((double) freq
) / CGRAPH_FREQ_BASE
, this_size
,
2619 if (gimple_assign_load_p (stmt
) && nonconstant_names
.exists ())
2621 struct predicate this_array_index
;
2623 array_index_predicate (info
, nonconstant_names
,
2624 gimple_assign_rhs1 (stmt
));
2625 if (!false_predicate_p (&this_array_index
))
2627 and_predicates (info
->conds
, &array_index
,
2630 if (gimple_store_p (stmt
) && nonconstant_names
.exists ())
2632 struct predicate this_array_index
;
2634 array_index_predicate (info
, nonconstant_names
,
2635 gimple_get_lhs (stmt
));
2636 if (!false_predicate_p (&this_array_index
))
2638 and_predicates (info
->conds
, &array_index
,
2643 if (is_gimple_call (stmt
)
2644 && !gimple_call_internal_p (stmt
))
2646 struct cgraph_edge
*edge
= node
->get_edge (stmt
);
2647 struct inline_edge_summary
*es
= inline_edge_summary (edge
);
2649 /* Special case: results of BUILT_IN_CONSTANT_P will be always
2650 resolved as constant. We however don't want to optimize
2651 out the cgraph edges. */
2652 if (nonconstant_names
.exists ()
2653 && gimple_call_builtin_p (stmt
, BUILT_IN_CONSTANT_P
)
2654 && gimple_call_lhs (stmt
)
2655 && TREE_CODE (gimple_call_lhs (stmt
)) == SSA_NAME
)
2657 struct predicate false_p
= false_predicate ();
2658 nonconstant_names
[SSA_NAME_VERSION (gimple_call_lhs (stmt
))]
2661 if (ipa_node_params_sum
)
2663 int count
= gimple_call_num_args (stmt
);
2667 es
->param
.safe_grow_cleared (count
);
2668 for (i
= 0; i
< count
; i
++)
2670 int prob
= param_change_prob (stmt
, i
);
2671 gcc_assert (prob
>= 0 && prob
<= REG_BR_PROB_BASE
);
2672 es
->param
[i
].change_prob
= prob
;
2676 es
->call_stmt_size
= this_size
;
2677 es
->call_stmt_time
= this_time
;
2678 es
->loop_depth
= bb_loop_depth (bb
);
2679 edge_set_predicate (edge
, &bb_predicate
);
2682 /* TODO: When conditional jump or swithc is known to be constant, but
2683 we did not translate it into the predicates, we really can account
2684 just maximum of the possible paths. */
2687 = will_be_nonconstant_predicate (parms_info
, info
,
2688 stmt
, nonconstant_names
);
2689 if (this_time
|| this_size
)
2695 prob
= eliminated_by_inlining_prob (stmt
);
2696 if (prob
== 1 && dump_file
&& (dump_flags
& TDF_DETAILS
))
2698 "\t\t50%% will be eliminated by inlining\n");
2699 if (prob
== 2 && dump_file
&& (dump_flags
& TDF_DETAILS
))
2700 fprintf (dump_file
, "\t\tWill be eliminated by inlining\n");
2703 p
= and_predicates (info
->conds
, &bb_predicate
,
2704 &will_be_nonconstant
);
2706 p
= true_predicate ();
2708 if (!false_predicate_p (&p
)
2709 || (is_gimple_call (stmt
)
2710 && !false_predicate_p (&bb_predicate
)))
2714 if (time
> MAX_TIME
* INLINE_TIME_SCALE
)
2715 time
= MAX_TIME
* INLINE_TIME_SCALE
;
2718 /* We account everything but the calls. Calls have their own
2719 size/time info attached to cgraph edges. This is necessary
2720 in order to make the cost disappear after inlining. */
2721 if (!is_gimple_call (stmt
))
2725 struct predicate ip
= not_inlined_predicate ();
2726 ip
= and_predicates (info
->conds
, &ip
, &p
);
2727 account_size_time (info
, this_size
* prob
,
2728 this_time
* prob
, &ip
);
2731 account_size_time (info
, this_size
* (2 - prob
),
2732 this_time
* (2 - prob
), &p
);
2735 gcc_assert (time
>= 0);
2736 gcc_assert (size
>= 0);
2740 set_hint_predicate (&inline_summaries
->get (node
)->array_index
, array_index
);
2741 time
= (time
+ CGRAPH_FREQ_BASE
/ 2) / CGRAPH_FREQ_BASE
;
2742 if (time
> MAX_TIME
)
2746 if (nonconstant_names
.exists () && !early
)
2749 predicate loop_iterations
= true_predicate ();
2750 predicate loop_stride
= true_predicate ();
2752 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2753 flow_loops_dump (dump_file
, NULL
, 0);
2755 FOR_EACH_LOOP (loop
, 0)
2760 struct tree_niter_desc niter_desc
;
2761 basic_block
*body
= get_loop_body (loop
);
2762 bb_predicate
= *(struct predicate
*) loop
->header
->aux
;
2764 exits
= get_loop_exit_edges (loop
);
2765 FOR_EACH_VEC_ELT (exits
, j
, ex
)
2766 if (number_of_iterations_exit (loop
, ex
, &niter_desc
, false)
2767 && !is_gimple_min_invariant (niter_desc
.niter
))
2769 predicate will_be_nonconstant
2770 = will_be_nonconstant_expr_predicate (parms_info
, info
,
2773 if (!true_predicate_p (&will_be_nonconstant
))
2774 will_be_nonconstant
= and_predicates (info
->conds
,
2776 &will_be_nonconstant
);
2777 if (!true_predicate_p (&will_be_nonconstant
)
2778 && !false_predicate_p (&will_be_nonconstant
))
2779 /* This is slightly inprecise. We may want to represent each
2780 loop with independent predicate. */
2782 and_predicates (info
->conds
, &loop_iterations
,
2783 &will_be_nonconstant
);
2787 for (i
= 0; i
< loop
->num_nodes
; i
++)
2789 gimple_stmt_iterator gsi
;
2790 bb_predicate
= *(struct predicate
*) body
[i
]->aux
;
2791 for (gsi
= gsi_start_bb (body
[i
]); !gsi_end_p (gsi
);
2794 gimple stmt
= gsi_stmt (gsi
);
2799 FOR_EACH_SSA_TREE_OPERAND (use
, stmt
, iter
, SSA_OP_USE
)
2801 predicate will_be_nonconstant
;
2804 (loop
, loop_containing_stmt (stmt
), use
, &iv
, true)
2805 || is_gimple_min_invariant (iv
.step
))
2808 = will_be_nonconstant_expr_predicate (parms_info
, info
,
2811 if (!true_predicate_p (&will_be_nonconstant
))
2813 = and_predicates (info
->conds
,
2815 &will_be_nonconstant
);
2816 if (!true_predicate_p (&will_be_nonconstant
)
2817 && !false_predicate_p (&will_be_nonconstant
))
2818 /* This is slightly inprecise. We may want to represent
2819 each loop with independent predicate. */
2821 and_predicates (info
->conds
, &loop_stride
,
2822 &will_be_nonconstant
);
2828 set_hint_predicate (&inline_summaries
->get (node
)->loop_iterations
,
2830 set_hint_predicate (&inline_summaries
->get (node
)->loop_stride
, loop_stride
);
2833 FOR_ALL_BB_FN (bb
, my_function
)
2839 edge_predicate_pool
.remove ((predicate
*)bb
->aux
);
2841 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
2844 edge_predicate_pool
.remove ((predicate
*) e
->aux
);
2848 inline_summaries
->get (node
)->self_time
= time
;
2849 inline_summaries
->get (node
)->self_size
= size
;
2850 nonconstant_names
.release ();
2851 if (opt_for_fn (node
->decl
, optimize
))
2854 loop_optimizer_finalize ();
2855 else if (!ipa_edge_args_vector
)
2856 ipa_free_all_node_params ();
2857 free_dominance_info (CDI_DOMINATORS
);
2861 fprintf (dump_file
, "\n");
2862 dump_inline_summary (dump_file
, node
);
2867 /* Compute parameters of functions used by inliner.
2868 EARLY is true when we compute parameters for the early inliner */
2871 compute_inline_parameters (struct cgraph_node
*node
, bool early
)
2873 HOST_WIDE_INT self_stack_size
;
2874 struct cgraph_edge
*e
;
2875 struct inline_summary
*info
;
2877 gcc_assert (!node
->global
.inlined_to
);
2879 inline_summary_alloc ();
2881 info
= inline_summaries
->get (node
);
2882 reset_inline_summary (node
, info
);
2884 /* FIXME: Thunks are inlinable, but tree-inline don't know how to do that.
2885 Once this happen, we will need to more curefully predict call
2887 if (node
->thunk
.thunk_p
)
2889 struct inline_edge_summary
*es
= inline_edge_summary (node
->callees
);
2890 struct predicate t
= true_predicate ();
2892 info
->inlinable
= 0;
2893 node
->callees
->call_stmt_cannot_inline_p
= true;
2894 node
->local
.can_change_signature
= false;
2895 es
->call_stmt_time
= 1;
2896 es
->call_stmt_size
= 1;
2897 account_size_time (info
, 0, 0, &t
);
2901 /* Even is_gimple_min_invariant rely on current_function_decl. */
2902 push_cfun (DECL_STRUCT_FUNCTION (node
->decl
));
2904 /* Estimate the stack size for the function if we're optimizing. */
2905 self_stack_size
= optimize
? estimated_stack_frame_size (node
) : 0;
2906 info
->estimated_self_stack_size
= self_stack_size
;
2907 info
->estimated_stack_size
= self_stack_size
;
2908 info
->stack_frame_offset
= 0;
2910 /* Can this function be inlined at all? */
2911 if (!opt_for_fn (node
->decl
, optimize
)
2912 && !lookup_attribute ("always_inline",
2913 DECL_ATTRIBUTES (node
->decl
)))
2914 info
->inlinable
= false;
2916 info
->inlinable
= tree_inlinable_function_p (node
->decl
);
2918 info
->contains_cilk_spawn
= fn_contains_cilk_spawn_p (cfun
);
2920 /* Type attributes can use parameter indices to describe them. */
2921 if (TYPE_ATTRIBUTES (TREE_TYPE (node
->decl
)))
2922 node
->local
.can_change_signature
= false;
2925 /* Otherwise, inlinable functions always can change signature. */
2926 if (info
->inlinable
)
2927 node
->local
.can_change_signature
= true;
2930 /* Functions calling builtin_apply can not change signature. */
2931 for (e
= node
->callees
; e
; e
= e
->next_callee
)
2933 tree
cdecl = e
->callee
->decl
;
2934 if (DECL_BUILT_IN (cdecl)
2935 && DECL_BUILT_IN_CLASS (cdecl) == BUILT_IN_NORMAL
2936 && (DECL_FUNCTION_CODE (cdecl) == BUILT_IN_APPLY_ARGS
2937 || DECL_FUNCTION_CODE (cdecl) == BUILT_IN_VA_START
))
2940 node
->local
.can_change_signature
= !e
;
2943 estimate_function_body_sizes (node
, early
);
2945 for (e
= node
->callees
; e
; e
= e
->next_callee
)
2946 if (e
->callee
->comdat_local_p ())
2948 node
->calls_comdat_local
= (e
!= NULL
);
2950 /* Inlining characteristics are maintained by the cgraph_mark_inline. */
2951 info
->time
= info
->self_time
;
2952 info
->size
= info
->self_size
;
2953 info
->stack_frame_offset
= 0;
2954 info
->estimated_stack_size
= info
->estimated_self_stack_size
;
2955 #ifdef ENABLE_CHECKING
2956 inline_update_overall_summary (node
);
2957 gcc_assert (info
->time
== info
->self_time
&& info
->size
== info
->self_size
);
2964 /* Compute parameters of functions used by inliner using
2965 current_function_decl. */
2968 compute_inline_parameters_for_current (void)
2970 compute_inline_parameters (cgraph_node::get (current_function_decl
), true);
2976 const pass_data pass_data_inline_parameters
=
2978 GIMPLE_PASS
, /* type */
2979 "inline_param", /* name */
2980 OPTGROUP_INLINE
, /* optinfo_flags */
2981 TV_INLINE_PARAMETERS
, /* tv_id */
2982 0, /* properties_required */
2983 0, /* properties_provided */
2984 0, /* properties_destroyed */
2985 0, /* todo_flags_start */
2986 0, /* todo_flags_finish */
2989 class pass_inline_parameters
: public gimple_opt_pass
2992 pass_inline_parameters (gcc::context
*ctxt
)
2993 : gimple_opt_pass (pass_data_inline_parameters
, ctxt
)
2996 /* opt_pass methods: */
2997 opt_pass
* clone () { return new pass_inline_parameters (m_ctxt
); }
2998 virtual unsigned int execute (function
*)
3000 return compute_inline_parameters_for_current ();
3003 }; // class pass_inline_parameters
3008 make_pass_inline_parameters (gcc::context
*ctxt
)
3010 return new pass_inline_parameters (ctxt
);
3014 /* Estimate benefit devirtualizing indirect edge IE, provided KNOWN_VALS,
3015 KNOWN_CONTEXTS and KNOWN_AGGS. */
3018 estimate_edge_devirt_benefit (struct cgraph_edge
*ie
,
3019 int *size
, int *time
,
3020 vec
<tree
> known_vals
,
3021 vec
<ipa_polymorphic_call_context
> known_contexts
,
3022 vec
<ipa_agg_jump_function_p
> known_aggs
)
3025 struct cgraph_node
*callee
;
3026 struct inline_summary
*isummary
;
3027 enum availability avail
;
3030 if (!known_vals
.exists () && !known_contexts
.exists ())
3032 if (!opt_for_fn (ie
->caller
->decl
, flag_indirect_inlining
))
3035 target
= ipa_get_indirect_edge_target (ie
, known_vals
, known_contexts
,
3036 known_aggs
, &speculative
);
3037 if (!target
|| speculative
)
3040 /* Account for difference in cost between indirect and direct calls. */
3041 *size
-= (eni_size_weights
.indirect_call_cost
- eni_size_weights
.call_cost
);
3042 *time
-= (eni_time_weights
.indirect_call_cost
- eni_time_weights
.call_cost
);
3043 gcc_checking_assert (*time
>= 0);
3044 gcc_checking_assert (*size
>= 0);
3046 callee
= cgraph_node::get (target
);
3047 if (!callee
|| !callee
->definition
)
3049 callee
= callee
->function_symbol (&avail
);
3050 if (avail
< AVAIL_AVAILABLE
)
3052 isummary
= inline_summaries
->get (callee
);
3053 return isummary
->inlinable
;
3056 /* Increase SIZE, MIN_SIZE (if non-NULL) and TIME for size and time needed to
3057 handle edge E with probability PROB.
3058 Set HINTS if edge may be devirtualized.
3059 KNOWN_VALS, KNOWN_AGGS and KNOWN_CONTEXTS describe context of the call
3063 estimate_edge_size_and_time (struct cgraph_edge
*e
, int *size
, int *min_size
,
3066 vec
<tree
> known_vals
,
3067 vec
<ipa_polymorphic_call_context
> known_contexts
,
3068 vec
<ipa_agg_jump_function_p
> known_aggs
,
3069 inline_hints
*hints
)
3071 struct inline_edge_summary
*es
= inline_edge_summary (e
);
3072 int call_size
= es
->call_stmt_size
;
3073 int call_time
= es
->call_stmt_time
;
3076 && estimate_edge_devirt_benefit (e
, &call_size
, &call_time
,
3077 known_vals
, known_contexts
, known_aggs
)
3078 && hints
&& e
->maybe_hot_p ())
3079 *hints
|= INLINE_HINT_indirect_call
;
3080 cur_size
= call_size
* INLINE_SIZE_SCALE
;
3083 *min_size
+= cur_size
;
3084 *time
+= apply_probability ((gcov_type
) call_time
, prob
)
3085 * e
->frequency
* (INLINE_TIME_SCALE
/ CGRAPH_FREQ_BASE
);
3086 if (*time
> MAX_TIME
* INLINE_TIME_SCALE
)
3087 *time
= MAX_TIME
* INLINE_TIME_SCALE
;
3092 /* Increase SIZE, MIN_SIZE and TIME for size and time needed to handle all
3093 calls in NODE. POSSIBLE_TRUTHS, KNOWN_VALS, KNOWN_AGGS and KNOWN_CONTEXTS
3094 describe context of the call site. */
3097 estimate_calls_size_and_time (struct cgraph_node
*node
, int *size
,
3098 int *min_size
, int *time
,
3099 inline_hints
*hints
,
3100 clause_t possible_truths
,
3101 vec
<tree
> known_vals
,
3102 vec
<ipa_polymorphic_call_context
> known_contexts
,
3103 vec
<ipa_agg_jump_function_p
> known_aggs
)
3105 struct cgraph_edge
*e
;
3106 for (e
= node
->callees
; e
; e
= e
->next_callee
)
3108 struct inline_edge_summary
*es
= inline_edge_summary (e
);
3110 /* Do not care about zero sized builtins. */
3111 if (e
->inline_failed
&& !es
->call_stmt_size
)
3113 gcc_checking_assert (!es
->call_stmt_time
);
3117 || evaluate_predicate (es
->predicate
, possible_truths
))
3119 if (e
->inline_failed
)
3121 /* Predicates of calls shall not use NOT_CHANGED codes,
3122 sowe do not need to compute probabilities. */
3123 estimate_edge_size_and_time (e
, size
,
3124 es
->predicate
? NULL
: min_size
,
3125 time
, REG_BR_PROB_BASE
,
3126 known_vals
, known_contexts
,
3130 estimate_calls_size_and_time (e
->callee
, size
, min_size
, time
,
3133 known_vals
, known_contexts
,
3137 for (e
= node
->indirect_calls
; e
; e
= e
->next_callee
)
3139 struct inline_edge_summary
*es
= inline_edge_summary (e
);
3141 || evaluate_predicate (es
->predicate
, possible_truths
))
3142 estimate_edge_size_and_time (e
, size
,
3143 es
->predicate
? NULL
: min_size
,
3144 time
, REG_BR_PROB_BASE
,
3145 known_vals
, known_contexts
, known_aggs
,
3151 /* Estimate size and time needed to execute NODE assuming
3152 POSSIBLE_TRUTHS clause, and KNOWN_VALS, KNOWN_AGGS and KNOWN_CONTEXTS
3153 information about NODE's arguments. If non-NULL use also probability
3154 information present in INLINE_PARAM_SUMMARY vector.
3155 Additionally detemine hints determined by the context. Finally compute
3156 minimal size needed for the call that is independent on the call context and
3157 can be used for fast estimates. Return the values in RET_SIZE,
3158 RET_MIN_SIZE, RET_TIME and RET_HINTS. */
3161 estimate_node_size_and_time (struct cgraph_node
*node
,
3162 clause_t possible_truths
,
3163 vec
<tree
> known_vals
,
3164 vec
<ipa_polymorphic_call_context
> known_contexts
,
3165 vec
<ipa_agg_jump_function_p
> known_aggs
,
3166 int *ret_size
, int *ret_min_size
, int *ret_time
,
3167 inline_hints
*ret_hints
,
3168 vec
<inline_param_summary
>
3169 inline_param_summary
)
3171 struct inline_summary
*info
= inline_summaries
->get (node
);
3176 inline_hints hints
= 0;
3179 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3182 fprintf (dump_file
, " Estimating body: %s/%i\n"
3183 " Known to be false: ", node
->name (),
3186 for (i
= predicate_not_inlined_condition
;
3187 i
< (predicate_first_dynamic_condition
3188 + (int) vec_safe_length (info
->conds
)); i
++)
3189 if (!(possible_truths
& (1 << i
)))
3192 fprintf (dump_file
, ", ");
3194 dump_condition (dump_file
, info
->conds
, i
);
3198 for (i
= 0; vec_safe_iterate (info
->entry
, i
, &e
); i
++)
3199 if (evaluate_predicate (&e
->predicate
, possible_truths
))
3202 gcc_checking_assert (e
->time
>= 0);
3203 gcc_checking_assert (time
>= 0);
3204 if (!inline_param_summary
.exists ())
3208 int prob
= predicate_probability (info
->conds
,
3211 inline_param_summary
);
3212 gcc_checking_assert (prob
>= 0);
3213 gcc_checking_assert (prob
<= REG_BR_PROB_BASE
);
3214 time
+= apply_probability ((gcov_type
) e
->time
, prob
);
3216 if (time
> MAX_TIME
* INLINE_TIME_SCALE
)
3217 time
= MAX_TIME
* INLINE_TIME_SCALE
;
3218 gcc_checking_assert (time
>= 0);
3221 gcc_checking_assert (true_predicate_p (&(*info
->entry
)[0].predicate
));
3222 min_size
= (*info
->entry
)[0].size
;
3223 gcc_checking_assert (size
>= 0);
3224 gcc_checking_assert (time
>= 0);
3226 if (info
->loop_iterations
3227 && !evaluate_predicate (info
->loop_iterations
, possible_truths
))
3228 hints
|= INLINE_HINT_loop_iterations
;
3229 if (info
->loop_stride
3230 && !evaluate_predicate (info
->loop_stride
, possible_truths
))
3231 hints
|= INLINE_HINT_loop_stride
;
3232 if (info
->array_index
3233 && !evaluate_predicate (info
->array_index
, possible_truths
))
3234 hints
|= INLINE_HINT_array_index
;
3236 hints
|= INLINE_HINT_in_scc
;
3237 if (DECL_DECLARED_INLINE_P (node
->decl
))
3238 hints
|= INLINE_HINT_declared_inline
;
3240 estimate_calls_size_and_time (node
, &size
, &min_size
, &time
, &hints
, possible_truths
,
3241 known_vals
, known_contexts
, known_aggs
);
3242 gcc_checking_assert (size
>= 0);
3243 gcc_checking_assert (time
>= 0);
3244 time
= RDIV (time
, INLINE_TIME_SCALE
);
3245 size
= RDIV (size
, INLINE_SIZE_SCALE
);
3246 min_size
= RDIV (min_size
, INLINE_SIZE_SCALE
);
3248 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3249 fprintf (dump_file
, "\n size:%i time:%i\n", (int) size
, (int) time
);
3255 *ret_min_size
= min_size
;
3262 /* Estimate size and time needed to execute callee of EDGE assuming that
3263 parameters known to be constant at caller of EDGE are propagated.
3264 KNOWN_VALS and KNOWN_CONTEXTS are vectors of assumed known constant values
3265 and types for parameters. */
3268 estimate_ipcp_clone_size_and_time (struct cgraph_node
*node
,
3269 vec
<tree
> known_vals
,
3270 vec
<ipa_polymorphic_call_context
>
3272 vec
<ipa_agg_jump_function_p
> known_aggs
,
3273 int *ret_size
, int *ret_time
,
3274 inline_hints
*hints
)
3278 clause
= evaluate_conditions_for_known_args (node
, false, known_vals
,
3280 estimate_node_size_and_time (node
, clause
, known_vals
, known_contexts
,
3281 known_aggs
, ret_size
, NULL
, ret_time
, hints
, vNULL
);
3284 /* Translate all conditions from callee representation into caller
3285 representation and symbolically evaluate predicate P into new predicate.
3287 INFO is inline_summary of function we are adding predicate into, CALLEE_INFO
3288 is summary of function predicate P is from. OPERAND_MAP is array giving
3289 callee formal IDs the caller formal IDs. POSSSIBLE_TRUTHS is clausule of all
3290 callee conditions that may be true in caller context. TOPLEV_PREDICATE is
3291 predicate under which callee is executed. OFFSET_MAP is an array of of
3292 offsets that need to be added to conditions, negative offset means that
3293 conditions relying on values passed by reference have to be discarded
3294 because they might not be preserved (and should be considered offset zero
3295 for other purposes). */
3297 static struct predicate
3298 remap_predicate (struct inline_summary
*info
,
3299 struct inline_summary
*callee_info
,
3300 struct predicate
*p
,
3301 vec
<int> operand_map
,
3302 vec
<int> offset_map
,
3303 clause_t possible_truths
, struct predicate
*toplev_predicate
)
3306 struct predicate out
= true_predicate ();
3308 /* True predicate is easy. */
3309 if (true_predicate_p (p
))
3310 return *toplev_predicate
;
3311 for (i
= 0; p
->clause
[i
]; i
++)
3313 clause_t clause
= p
->clause
[i
];
3315 struct predicate clause_predicate
= false_predicate ();
3317 gcc_assert (i
< MAX_CLAUSES
);
3319 for (cond
= 0; cond
< NUM_CONDITIONS
; cond
++)
3320 /* Do we have condition we can't disprove? */
3321 if (clause
& possible_truths
& (1 << cond
))
3323 struct predicate cond_predicate
;
3324 /* Work out if the condition can translate to predicate in the
3325 inlined function. */
3326 if (cond
>= predicate_first_dynamic_condition
)
3328 struct condition
*c
;
3330 c
= &(*callee_info
->conds
)[cond
3332 predicate_first_dynamic_condition
];
3333 /* See if we can remap condition operand to caller's operand.
3334 Otherwise give up. */
3335 if (!operand_map
.exists ()
3336 || (int) operand_map
.length () <= c
->operand_num
3337 || operand_map
[c
->operand_num
] == -1
3338 /* TODO: For non-aggregate conditions, adding an offset is
3339 basically an arithmetic jump function processing which
3340 we should support in future. */
3341 || ((!c
->agg_contents
|| !c
->by_ref
)
3342 && offset_map
[c
->operand_num
] > 0)
3343 || (c
->agg_contents
&& c
->by_ref
3344 && offset_map
[c
->operand_num
] < 0))
3345 cond_predicate
= true_predicate ();
3348 struct agg_position_info ap
;
3349 HOST_WIDE_INT offset_delta
= offset_map
[c
->operand_num
];
3350 if (offset_delta
< 0)
3352 gcc_checking_assert (!c
->agg_contents
|| !c
->by_ref
);
3355 gcc_assert (!c
->agg_contents
3356 || c
->by_ref
|| offset_delta
== 0);
3357 ap
.offset
= c
->offset
+ offset_delta
;
3358 ap
.agg_contents
= c
->agg_contents
;
3359 ap
.by_ref
= c
->by_ref
;
3360 cond_predicate
= add_condition (info
,
3361 operand_map
[c
->operand_num
],
3362 &ap
, c
->code
, c
->val
);
3365 /* Fixed conditions remains same, construct single
3366 condition predicate. */
3369 cond_predicate
.clause
[0] = 1 << cond
;
3370 cond_predicate
.clause
[1] = 0;
3372 clause_predicate
= or_predicates (info
->conds
, &clause_predicate
,
3375 out
= and_predicates (info
->conds
, &out
, &clause_predicate
);
3377 return and_predicates (info
->conds
, &out
, toplev_predicate
);
3381 /* Update summary information of inline clones after inlining.
3382 Compute peak stack usage. */
3385 inline_update_callee_summaries (struct cgraph_node
*node
, int depth
)
3387 struct cgraph_edge
*e
;
3388 struct inline_summary
*callee_info
= inline_summaries
->get (node
);
3389 struct inline_summary
*caller_info
= inline_summaries
->get (node
->callers
->caller
);
3392 callee_info
->stack_frame_offset
3393 = caller_info
->stack_frame_offset
3394 + caller_info
->estimated_self_stack_size
;
3395 peak
= callee_info
->stack_frame_offset
3396 + callee_info
->estimated_self_stack_size
;
3397 if (inline_summaries
->get (node
->global
.inlined_to
)->estimated_stack_size
< peak
)
3398 inline_summaries
->get (node
->global
.inlined_to
)->estimated_stack_size
= peak
;
3399 ipa_propagate_frequency (node
);
3400 for (e
= node
->callees
; e
; e
= e
->next_callee
)
3402 if (!e
->inline_failed
)
3403 inline_update_callee_summaries (e
->callee
, depth
);
3404 inline_edge_summary (e
)->loop_depth
+= depth
;
3406 for (e
= node
->indirect_calls
; e
; e
= e
->next_callee
)
3407 inline_edge_summary (e
)->loop_depth
+= depth
;
3410 /* Update change_prob of EDGE after INLINED_EDGE has been inlined.
3411 When functoin A is inlined in B and A calls C with parameter that
3412 changes with probability PROB1 and C is known to be passthroug
3413 of argument if B that change with probability PROB2, the probability
3414 of change is now PROB1*PROB2. */
3417 remap_edge_change_prob (struct cgraph_edge
*inlined_edge
,
3418 struct cgraph_edge
*edge
)
3420 if (ipa_node_params_sum
)
3423 struct ipa_edge_args
*args
= IPA_EDGE_REF (edge
);
3424 struct inline_edge_summary
*es
= inline_edge_summary (edge
);
3425 struct inline_edge_summary
*inlined_es
3426 = inline_edge_summary (inlined_edge
);
3428 for (i
= 0; i
< ipa_get_cs_argument_count (args
); i
++)
3430 struct ipa_jump_func
*jfunc
= ipa_get_ith_jump_func (args
, i
);
3431 if (jfunc
->type
== IPA_JF_PASS_THROUGH
3432 && (ipa_get_jf_pass_through_formal_id (jfunc
)
3433 < (int) inlined_es
->param
.length ()))
3435 int jf_formal_id
= ipa_get_jf_pass_through_formal_id (jfunc
);
3436 int prob1
= es
->param
[i
].change_prob
;
3437 int prob2
= inlined_es
->param
[jf_formal_id
].change_prob
;
3438 int prob
= combine_probabilities (prob1
, prob2
);
3440 if (prob1
&& prob2
&& !prob
)
3443 es
->param
[i
].change_prob
= prob
;
3449 /* Update edge summaries of NODE after INLINED_EDGE has been inlined.
3451 Remap predicates of callees of NODE. Rest of arguments match
3454 Also update change probabilities. */
3457 remap_edge_summaries (struct cgraph_edge
*inlined_edge
,
3458 struct cgraph_node
*node
,
3459 struct inline_summary
*info
,
3460 struct inline_summary
*callee_info
,
3461 vec
<int> operand_map
,
3462 vec
<int> offset_map
,
3463 clause_t possible_truths
,
3464 struct predicate
*toplev_predicate
)
3466 struct cgraph_edge
*e
, *next
;
3467 for (e
= node
->callees
; e
; e
= next
)
3469 struct inline_edge_summary
*es
= inline_edge_summary (e
);
3471 next
= e
->next_callee
;
3473 if (e
->inline_failed
)
3475 remap_edge_change_prob (inlined_edge
, e
);
3479 p
= remap_predicate (info
, callee_info
,
3480 es
->predicate
, operand_map
, offset_map
,
3481 possible_truths
, toplev_predicate
);
3482 edge_set_predicate (e
, &p
);
3485 edge_set_predicate (e
, toplev_predicate
);
3488 remap_edge_summaries (inlined_edge
, e
->callee
, info
, callee_info
,
3489 operand_map
, offset_map
, possible_truths
,
3492 for (e
= node
->indirect_calls
; e
; e
= next
)
3494 struct inline_edge_summary
*es
= inline_edge_summary (e
);
3496 next
= e
->next_callee
;
3498 remap_edge_change_prob (inlined_edge
, e
);
3501 p
= remap_predicate (info
, callee_info
,
3502 es
->predicate
, operand_map
, offset_map
,
3503 possible_truths
, toplev_predicate
);
3504 edge_set_predicate (e
, &p
);
3507 edge_set_predicate (e
, toplev_predicate
);
3511 /* Same as remap_predicate, but set result into hint *HINT. */
3514 remap_hint_predicate (struct inline_summary
*info
,
3515 struct inline_summary
*callee_info
,
3516 struct predicate
**hint
,
3517 vec
<int> operand_map
,
3518 vec
<int> offset_map
,
3519 clause_t possible_truths
,
3520 struct predicate
*toplev_predicate
)
3526 p
= remap_predicate (info
, callee_info
,
3528 operand_map
, offset_map
,
3529 possible_truths
, toplev_predicate
);
3530 if (!false_predicate_p (&p
) && !true_predicate_p (&p
))
3533 set_hint_predicate (hint
, p
);
3535 **hint
= and_predicates (info
->conds
, *hint
, &p
);
3539 /* We inlined EDGE. Update summary of the function we inlined into. */
3542 inline_merge_summary (struct cgraph_edge
*edge
)
3544 struct inline_summary
*callee_info
= inline_summaries
->get (edge
->callee
);
3545 struct cgraph_node
*to
= (edge
->caller
->global
.inlined_to
3546 ? edge
->caller
->global
.inlined_to
: edge
->caller
);
3547 struct inline_summary
*info
= inline_summaries
->get (to
);
3548 clause_t clause
= 0; /* not_inline is known to be false. */
3550 vec
<int> operand_map
= vNULL
;
3551 vec
<int> offset_map
= vNULL
;
3553 struct predicate toplev_predicate
;
3554 struct predicate true_p
= true_predicate ();
3555 struct inline_edge_summary
*es
= inline_edge_summary (edge
);
3558 toplev_predicate
= *es
->predicate
;
3560 toplev_predicate
= true_predicate ();
3562 if (callee_info
->conds
)
3563 evaluate_properties_for_edge (edge
, true, &clause
, NULL
, NULL
, NULL
);
3564 if (ipa_node_params_sum
&& callee_info
->conds
)
3566 struct ipa_edge_args
*args
= IPA_EDGE_REF (edge
);
3567 int count
= ipa_get_cs_argument_count (args
);
3572 operand_map
.safe_grow_cleared (count
);
3573 offset_map
.safe_grow_cleared (count
);
3575 for (i
= 0; i
< count
; i
++)
3577 struct ipa_jump_func
*jfunc
= ipa_get_ith_jump_func (args
, i
);
3580 /* TODO: handle non-NOPs when merging. */
3581 if (jfunc
->type
== IPA_JF_PASS_THROUGH
)
3583 if (ipa_get_jf_pass_through_operation (jfunc
) == NOP_EXPR
)
3584 map
= ipa_get_jf_pass_through_formal_id (jfunc
);
3585 if (!ipa_get_jf_pass_through_agg_preserved (jfunc
))
3588 else if (jfunc
->type
== IPA_JF_ANCESTOR
)
3590 HOST_WIDE_INT offset
= ipa_get_jf_ancestor_offset (jfunc
);
3591 if (offset
>= 0 && offset
< INT_MAX
)
3593 map
= ipa_get_jf_ancestor_formal_id (jfunc
);
3594 if (!ipa_get_jf_ancestor_agg_preserved (jfunc
))
3596 offset_map
[i
] = offset
;
3599 operand_map
[i
] = map
;
3600 gcc_assert (map
< ipa_get_param_count (IPA_NODE_REF (to
)));
3603 for (i
= 0; vec_safe_iterate (callee_info
->entry
, i
, &e
); i
++)
3605 struct predicate p
= remap_predicate (info
, callee_info
,
3606 &e
->predicate
, operand_map
,
3609 if (!false_predicate_p (&p
))
3611 gcov_type add_time
= ((gcov_type
) e
->time
* edge
->frequency
3612 + CGRAPH_FREQ_BASE
/ 2) / CGRAPH_FREQ_BASE
;
3613 int prob
= predicate_probability (callee_info
->conds
,
3616 add_time
= apply_probability ((gcov_type
) add_time
, prob
);
3617 if (add_time
> MAX_TIME
* INLINE_TIME_SCALE
)
3618 add_time
= MAX_TIME
* INLINE_TIME_SCALE
;
3619 if (prob
!= REG_BR_PROB_BASE
3620 && dump_file
&& (dump_flags
& TDF_DETAILS
))
3622 fprintf (dump_file
, "\t\tScaling time by probability:%f\n",
3623 (double) prob
/ REG_BR_PROB_BASE
);
3625 account_size_time (info
, e
->size
, add_time
, &p
);
3628 remap_edge_summaries (edge
, edge
->callee
, info
, callee_info
, operand_map
,
3629 offset_map
, clause
, &toplev_predicate
);
3630 remap_hint_predicate (info
, callee_info
,
3631 &callee_info
->loop_iterations
,
3632 operand_map
, offset_map
, clause
, &toplev_predicate
);
3633 remap_hint_predicate (info
, callee_info
,
3634 &callee_info
->loop_stride
,
3635 operand_map
, offset_map
, clause
, &toplev_predicate
);
3636 remap_hint_predicate (info
, callee_info
,
3637 &callee_info
->array_index
,
3638 operand_map
, offset_map
, clause
, &toplev_predicate
);
3640 inline_update_callee_summaries (edge
->callee
,
3641 inline_edge_summary (edge
)->loop_depth
);
3643 /* We do not maintain predicates of inlined edges, free it. */
3644 edge_set_predicate (edge
, &true_p
);
3645 /* Similarly remove param summaries. */
3646 es
->param
.release ();
3647 operand_map
.release ();
3648 offset_map
.release ();
3651 /* For performance reasons inline_merge_summary is not updating overall size
3652 and time. Recompute it. */
3655 inline_update_overall_summary (struct cgraph_node
*node
)
3657 struct inline_summary
*info
= inline_summaries
->get (node
);
3663 for (i
= 0; vec_safe_iterate (info
->entry
, i
, &e
); i
++)
3665 info
->size
+= e
->size
, info
->time
+= e
->time
;
3666 if (info
->time
> MAX_TIME
* INLINE_TIME_SCALE
)
3667 info
->time
= MAX_TIME
* INLINE_TIME_SCALE
;
3669 estimate_calls_size_and_time (node
, &info
->size
, &info
->min_size
,
3671 ~(clause_t
) (1 << predicate_false_condition
),
3672 vNULL
, vNULL
, vNULL
);
3673 info
->time
= (info
->time
+ INLINE_TIME_SCALE
/ 2) / INLINE_TIME_SCALE
;
3674 info
->size
= (info
->size
+ INLINE_SIZE_SCALE
/ 2) / INLINE_SIZE_SCALE
;
3677 /* Return hints derrived from EDGE. */
3679 simple_edge_hints (struct cgraph_edge
*edge
)
3682 struct cgraph_node
*to
= (edge
->caller
->global
.inlined_to
3683 ? edge
->caller
->global
.inlined_to
: edge
->caller
);
3684 struct cgraph_node
*callee
= edge
->callee
->ultimate_alias_target ();
3685 if (inline_summaries
->get (to
)->scc_no
3686 && inline_summaries
->get (to
)->scc_no
3687 == inline_summaries
->get (callee
)->scc_no
3688 && !edge
->recursive_p ())
3689 hints
|= INLINE_HINT_same_scc
;
3691 if (callee
->lto_file_data
&& edge
->caller
->lto_file_data
3692 && edge
->caller
->lto_file_data
!= callee
->lto_file_data
3694 hints
|= INLINE_HINT_cross_module
;
3699 /* Estimate the time cost for the caller when inlining EDGE.
3700 Only to be called via estimate_edge_time, that handles the
3703 When caching, also update the cache entry. Compute both time and
3704 size, since we always need both metrics eventually. */
3707 do_estimate_edge_time (struct cgraph_edge
*edge
)
3712 struct cgraph_node
*callee
;
3714 vec
<tree
> known_vals
;
3715 vec
<ipa_polymorphic_call_context
> known_contexts
;
3716 vec
<ipa_agg_jump_function_p
> known_aggs
;
3717 struct inline_edge_summary
*es
= inline_edge_summary (edge
);
3720 callee
= edge
->callee
->ultimate_alias_target ();
3722 gcc_checking_assert (edge
->inline_failed
);
3723 evaluate_properties_for_edge (edge
, true,
3724 &clause
, &known_vals
, &known_contexts
,
3726 estimate_node_size_and_time (callee
, clause
, known_vals
, known_contexts
,
3727 known_aggs
, &size
, &min_size
, &time
, &hints
, es
->param
);
3729 /* When we have profile feedback, we can quite safely identify hot
3730 edges and for those we disable size limits. Don't do that when
3731 probability that caller will call the callee is low however, since it
3732 may hurt optimization of the caller's hot path. */
3733 if (edge
->count
&& edge
->maybe_hot_p ()
3735 > (edge
->caller
->global
.inlined_to
3736 ? edge
->caller
->global
.inlined_to
->count
: edge
->caller
->count
)))
3737 hints
|= INLINE_HINT_known_hot
;
3739 known_vals
.release ();
3740 known_contexts
.release ();
3741 known_aggs
.release ();
3742 gcc_checking_assert (size
>= 0);
3743 gcc_checking_assert (time
>= 0);
3745 /* When caching, update the cache entry. */
3746 if (edge_growth_cache
.exists ())
3748 inline_summaries
->get (edge
->callee
)->min_size
= min_size
;
3749 if ((int) edge_growth_cache
.length () <= edge
->uid
)
3750 edge_growth_cache
.safe_grow_cleared (symtab
->edges_max_uid
);
3751 edge_growth_cache
[edge
->uid
].time
= time
+ (time
>= 0);
3753 edge_growth_cache
[edge
->uid
].size
= size
+ (size
>= 0);
3754 hints
|= simple_edge_hints (edge
);
3755 edge_growth_cache
[edge
->uid
].hints
= hints
+ 1;
3761 /* Return estimated callee growth after inlining EDGE.
3762 Only to be called via estimate_edge_size. */
3765 do_estimate_edge_size (struct cgraph_edge
*edge
)
3768 struct cgraph_node
*callee
;
3770 vec
<tree
> known_vals
;
3771 vec
<ipa_polymorphic_call_context
> known_contexts
;
3772 vec
<ipa_agg_jump_function_p
> known_aggs
;
3774 /* When we do caching, use do_estimate_edge_time to populate the entry. */
3776 if (edge_growth_cache
.exists ())
3778 do_estimate_edge_time (edge
);
3779 size
= edge_growth_cache
[edge
->uid
].size
;
3780 gcc_checking_assert (size
);
3781 return size
- (size
> 0);
3784 callee
= edge
->callee
->ultimate_alias_target ();
3786 /* Early inliner runs without caching, go ahead and do the dirty work. */
3787 gcc_checking_assert (edge
->inline_failed
);
3788 evaluate_properties_for_edge (edge
, true,
3789 &clause
, &known_vals
, &known_contexts
,
3791 estimate_node_size_and_time (callee
, clause
, known_vals
, known_contexts
,
3792 known_aggs
, &size
, NULL
, NULL
, NULL
, vNULL
);
3793 known_vals
.release ();
3794 known_contexts
.release ();
3795 known_aggs
.release ();
3800 /* Estimate the growth of the caller when inlining EDGE.
3801 Only to be called via estimate_edge_size. */
3804 do_estimate_edge_hints (struct cgraph_edge
*edge
)
3807 struct cgraph_node
*callee
;
3809 vec
<tree
> known_vals
;
3810 vec
<ipa_polymorphic_call_context
> known_contexts
;
3811 vec
<ipa_agg_jump_function_p
> known_aggs
;
3813 /* When we do caching, use do_estimate_edge_time to populate the entry. */
3815 if (edge_growth_cache
.exists ())
3817 do_estimate_edge_time (edge
);
3818 hints
= edge_growth_cache
[edge
->uid
].hints
;
3819 gcc_checking_assert (hints
);
3823 callee
= edge
->callee
->ultimate_alias_target ();
3825 /* Early inliner runs without caching, go ahead and do the dirty work. */
3826 gcc_checking_assert (edge
->inline_failed
);
3827 evaluate_properties_for_edge (edge
, true,
3828 &clause
, &known_vals
, &known_contexts
,
3830 estimate_node_size_and_time (callee
, clause
, known_vals
, known_contexts
,
3831 known_aggs
, NULL
, NULL
, NULL
, &hints
, vNULL
);
3832 known_vals
.release ();
3833 known_contexts
.release ();
3834 known_aggs
.release ();
3835 hints
|= simple_edge_hints (edge
);
3840 /* Estimate self time of the function NODE after inlining EDGE. */
3843 estimate_time_after_inlining (struct cgraph_node
*node
,
3844 struct cgraph_edge
*edge
)
3846 struct inline_edge_summary
*es
= inline_edge_summary (edge
);
3847 if (!es
->predicate
|| !false_predicate_p (es
->predicate
))
3850 inline_summaries
->get (node
)->time
+ estimate_edge_time (edge
);
3853 if (time
> MAX_TIME
)
3857 return inline_summaries
->get (node
)->time
;
3861 /* Estimate the size of NODE after inlining EDGE which should be an
3862 edge to either NODE or a call inlined into NODE. */
3865 estimate_size_after_inlining (struct cgraph_node
*node
,
3866 struct cgraph_edge
*edge
)
3868 struct inline_edge_summary
*es
= inline_edge_summary (edge
);
3869 if (!es
->predicate
|| !false_predicate_p (es
->predicate
))
3871 int size
= inline_summaries
->get (node
)->size
+ estimate_edge_growth (edge
);
3872 gcc_assert (size
>= 0);
3875 return inline_summaries
->get (node
)->size
;
3881 struct cgraph_node
*node
;
3882 bool self_recursive
;
3888 /* Worker for do_estimate_growth. Collect growth for all callers. */
3891 do_estimate_growth_1 (struct cgraph_node
*node
, void *data
)
3893 struct cgraph_edge
*e
;
3894 struct growth_data
*d
= (struct growth_data
*) data
;
3896 for (e
= node
->callers
; e
; e
= e
->next_caller
)
3898 gcc_checking_assert (e
->inline_failed
);
3900 if (cgraph_inline_failed_type (e
->inline_failed
) == CIF_FINAL_ERROR
)
3902 d
->uninlinable
= true;
3906 if (e
->recursive_p ())
3908 d
->self_recursive
= true;
3911 d
->growth
+= estimate_edge_growth (e
);
3917 /* Estimate the growth caused by inlining NODE into all callees. */
3920 estimate_growth (struct cgraph_node
*node
)
3922 struct growth_data d
= { node
, false, false, 0 };
3923 struct inline_summary
*info
= inline_summaries
->get (node
);
3925 node
->call_for_symbol_and_aliases (do_estimate_growth_1
, &d
, true);
3927 /* For self recursive functions the growth estimation really should be
3928 infinity. We don't want to return very large values because the growth
3929 plays various roles in badness computation fractions. Be sure to not
3930 return zero or negative growths. */
3931 if (d
.self_recursive
)
3932 d
.growth
= d
.growth
< info
->size
? info
->size
: d
.growth
;
3933 else if (DECL_EXTERNAL (node
->decl
) || d
.uninlinable
)
3937 if (node
->will_be_removed_from_program_if_no_direct_calls_p ())
3938 d
.growth
-= info
->size
;
3939 /* COMDAT functions are very often not shared across multiple units
3940 since they come from various template instantiations.
3941 Take this into account. */
3942 else if (DECL_COMDAT (node
->decl
)
3943 && node
->can_remove_if_no_direct_calls_p ())
3944 d
.growth
-= (info
->size
3945 * (100 - PARAM_VALUE (PARAM_COMDAT_SHARING_PROBABILITY
))
3952 /* Verify if there are fewer than MAX_CALLERS. */
3955 check_callers (cgraph_node
*node
, int *max_callers
)
3959 if (!node
->can_remove_if_no_direct_calls_and_refs_p ())
3962 for (cgraph_edge
*e
= node
->callers
; e
; e
= e
->next_caller
)
3966 || cgraph_inline_failed_type (e
->inline_failed
) == CIF_FINAL_ERROR
)
3970 FOR_EACH_ALIAS (node
, ref
)
3971 if (check_callers (dyn_cast
<cgraph_node
*> (ref
->referring
), max_callers
))
3978 /* Make cheap estimation if growth of NODE is likely positive knowing
3979 EDGE_GROWTH of one particular edge.
3980 We assume that most of other edges will have similar growth
3981 and skip computation if there are too many callers. */
3984 growth_likely_positive (struct cgraph_node
*node
,
3988 struct cgraph_edge
*e
;
3989 gcc_checking_assert (edge_growth
> 0);
3991 /* First quickly check if NODE is removable at all. */
3992 if (DECL_EXTERNAL (node
->decl
))
3994 if (!node
->can_remove_if_no_direct_calls_and_refs_p ()
3995 || node
->address_taken
)
3998 max_callers
= inline_summaries
->get (node
)->size
* 4 / edge_growth
+ 2;
4000 for (e
= node
->callers
; e
; e
= e
->next_caller
)
4004 || cgraph_inline_failed_type (e
->inline_failed
) == CIF_FINAL_ERROR
)
4009 FOR_EACH_ALIAS (node
, ref
)
4010 if (check_callers (dyn_cast
<cgraph_node
*> (ref
->referring
), &max_callers
))
4013 /* Unlike for functions called once, we play unsafe with
4014 COMDATs. We can allow that since we know functions
4015 in consideration are small (and thus risk is small) and
4016 moreover grow estimates already accounts that COMDAT
4017 functions may or may not disappear when eliminated from
4018 current unit. With good probability making aggressive
4019 choice in all units is going to make overall program
4021 if (DECL_COMDAT (node
->decl
))
4023 if (!node
->can_remove_if_no_direct_calls_p ())
4026 else if (!node
->will_be_removed_from_program_if_no_direct_calls_p ())
4029 return estimate_growth (node
) > 0;
4033 /* This function performs intraprocedural analysis in NODE that is required to
4034 inline indirect calls. */
4037 inline_indirect_intraprocedural_analysis (struct cgraph_node
*node
)
4039 ipa_analyze_node (node
);
4040 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
4042 ipa_print_node_params (dump_file
, node
);
4043 ipa_print_node_jump_functions (dump_file
, node
);
4048 /* Note function body size. */
4051 inline_analyze_function (struct cgraph_node
*node
)
4053 push_cfun (DECL_STRUCT_FUNCTION (node
->decl
));
4056 fprintf (dump_file
, "\nAnalyzing function: %s/%u\n",
4057 node
->name (), node
->order
);
4058 if (opt_for_fn (node
->decl
, optimize
) && !node
->thunk
.thunk_p
)
4059 inline_indirect_intraprocedural_analysis (node
);
4060 compute_inline_parameters (node
, false);
4063 struct cgraph_edge
*e
;
4064 for (e
= node
->callees
; e
; e
= e
->next_callee
)
4066 if (e
->inline_failed
== CIF_FUNCTION_NOT_CONSIDERED
)
4067 e
->inline_failed
= CIF_FUNCTION_NOT_OPTIMIZED
;
4068 e
->call_stmt_cannot_inline_p
= true;
4070 for (e
= node
->indirect_calls
; e
; e
= e
->next_callee
)
4072 if (e
->inline_failed
== CIF_FUNCTION_NOT_CONSIDERED
)
4073 e
->inline_failed
= CIF_FUNCTION_NOT_OPTIMIZED
;
4074 e
->call_stmt_cannot_inline_p
= true;
4082 /* Called when new function is inserted to callgraph late. */
4085 inline_summary_t::insert (struct cgraph_node
*node
, inline_summary
*)
4087 inline_analyze_function (node
);
4090 /* Note function body size. */
4093 inline_generate_summary (void)
4095 struct cgraph_node
*node
;
4097 /* When not optimizing, do not bother to analyze. Inlining is still done
4098 because edge redirection needs to happen there. */
4099 if (!optimize
&& !flag_generate_lto
&& !flag_generate_offload
&& !flag_wpa
)
4102 if (!inline_summaries
)
4103 inline_summaries
= (inline_summary_t
*) inline_summary_t::create_ggc (symtab
);
4105 inline_summaries
->enable_insertion_hook ();
4107 ipa_register_cgraph_hooks ();
4108 inline_free_summary ();
4110 FOR_EACH_DEFINED_FUNCTION (node
)
4112 inline_analyze_function (node
);
4116 /* Read predicate from IB. */
4118 static struct predicate
4119 read_predicate (struct lto_input_block
*ib
)
4121 struct predicate out
;
4127 gcc_assert (k
<= MAX_CLAUSES
);
4128 clause
= out
.clause
[k
++] = streamer_read_uhwi (ib
);
4132 /* Zero-initialize the remaining clauses in OUT. */
4133 while (k
<= MAX_CLAUSES
)
4134 out
.clause
[k
++] = 0;
4140 /* Write inline summary for edge E to OB. */
4143 read_inline_edge_summary (struct lto_input_block
*ib
, struct cgraph_edge
*e
)
4145 struct inline_edge_summary
*es
= inline_edge_summary (e
);
4149 es
->call_stmt_size
= streamer_read_uhwi (ib
);
4150 es
->call_stmt_time
= streamer_read_uhwi (ib
);
4151 es
->loop_depth
= streamer_read_uhwi (ib
);
4152 p
= read_predicate (ib
);
4153 edge_set_predicate (e
, &p
);
4154 length
= streamer_read_uhwi (ib
);
4157 es
->param
.safe_grow_cleared (length
);
4158 for (i
= 0; i
< length
; i
++)
4159 es
->param
[i
].change_prob
= streamer_read_uhwi (ib
);
4164 /* Stream in inline summaries from the section. */
4167 inline_read_section (struct lto_file_decl_data
*file_data
, const char *data
,
4170 const struct lto_function_header
*header
=
4171 (const struct lto_function_header
*) data
;
4172 const int cfg_offset
= sizeof (struct lto_function_header
);
4173 const int main_offset
= cfg_offset
+ header
->cfg_size
;
4174 const int string_offset
= main_offset
+ header
->main_size
;
4175 struct data_in
*data_in
;
4176 unsigned int i
, count2
, j
;
4177 unsigned int f_count
;
4179 lto_input_block
ib ((const char *) data
+ main_offset
, header
->main_size
,
4180 file_data
->mode_table
);
4183 lto_data_in_create (file_data
, (const char *) data
+ string_offset
,
4184 header
->string_size
, vNULL
);
4185 f_count
= streamer_read_uhwi (&ib
);
4186 for (i
= 0; i
< f_count
; i
++)
4189 struct cgraph_node
*node
;
4190 struct inline_summary
*info
;
4191 lto_symtab_encoder_t encoder
;
4192 struct bitpack_d bp
;
4193 struct cgraph_edge
*e
;
4196 index
= streamer_read_uhwi (&ib
);
4197 encoder
= file_data
->symtab_node_encoder
;
4198 node
= dyn_cast
<cgraph_node
*> (lto_symtab_encoder_deref (encoder
,
4200 info
= inline_summaries
->get (node
);
4202 info
->estimated_stack_size
4203 = info
->estimated_self_stack_size
= streamer_read_uhwi (&ib
);
4204 info
->size
= info
->self_size
= streamer_read_uhwi (&ib
);
4205 info
->time
= info
->self_time
= streamer_read_uhwi (&ib
);
4207 bp
= streamer_read_bitpack (&ib
);
4208 info
->inlinable
= bp_unpack_value (&bp
, 1);
4209 info
->contains_cilk_spawn
= bp_unpack_value (&bp
, 1);
4211 count2
= streamer_read_uhwi (&ib
);
4212 gcc_assert (!info
->conds
);
4213 for (j
= 0; j
< count2
; j
++)
4216 c
.operand_num
= streamer_read_uhwi (&ib
);
4217 c
.code
= (enum tree_code
) streamer_read_uhwi (&ib
);
4218 c
.val
= stream_read_tree (&ib
, data_in
);
4219 bp
= streamer_read_bitpack (&ib
);
4220 c
.agg_contents
= bp_unpack_value (&bp
, 1);
4221 c
.by_ref
= bp_unpack_value (&bp
, 1);
4223 c
.offset
= streamer_read_uhwi (&ib
);
4224 vec_safe_push (info
->conds
, c
);
4226 count2
= streamer_read_uhwi (&ib
);
4227 gcc_assert (!info
->entry
);
4228 for (j
= 0; j
< count2
; j
++)
4230 struct size_time_entry e
;
4232 e
.size
= streamer_read_uhwi (&ib
);
4233 e
.time
= streamer_read_uhwi (&ib
);
4234 e
.predicate
= read_predicate (&ib
);
4236 vec_safe_push (info
->entry
, e
);
4239 p
= read_predicate (&ib
);
4240 set_hint_predicate (&info
->loop_iterations
, p
);
4241 p
= read_predicate (&ib
);
4242 set_hint_predicate (&info
->loop_stride
, p
);
4243 p
= read_predicate (&ib
);
4244 set_hint_predicate (&info
->array_index
, p
);
4245 for (e
= node
->callees
; e
; e
= e
->next_callee
)
4246 read_inline_edge_summary (&ib
, e
);
4247 for (e
= node
->indirect_calls
; e
; e
= e
->next_callee
)
4248 read_inline_edge_summary (&ib
, e
);
4251 lto_free_section_data (file_data
, LTO_section_inline_summary
, NULL
, data
,
4253 lto_data_in_delete (data_in
);
4257 /* Read inline summary. Jump functions are shared among ipa-cp
4258 and inliner, so when ipa-cp is active, we don't need to write them
4262 inline_read_summary (void)
4264 struct lto_file_decl_data
**file_data_vec
= lto_get_file_decl_data ();
4265 struct lto_file_decl_data
*file_data
;
4268 inline_summary_alloc ();
4270 while ((file_data
= file_data_vec
[j
++]))
4273 const char *data
= lto_get_section_data (file_data
,
4274 LTO_section_inline_summary
,
4277 inline_read_section (file_data
, data
, len
);
4279 /* Fatal error here. We do not want to support compiling ltrans units
4280 with different version of compiler or different flags than the WPA
4281 unit, so this should never happen. */
4282 fatal_error (input_location
,
4283 "ipa inline summary is missing in input file");
4287 ipa_register_cgraph_hooks ();
4289 ipa_prop_read_jump_functions ();
4292 gcc_assert (inline_summaries
);
4293 inline_summaries
->enable_insertion_hook ();
4297 /* Write predicate P to OB. */
4300 write_predicate (struct output_block
*ob
, struct predicate
*p
)
4304 for (j
= 0; p
->clause
[j
]; j
++)
4306 gcc_assert (j
< MAX_CLAUSES
);
4307 streamer_write_uhwi (ob
, p
->clause
[j
]);
4309 streamer_write_uhwi (ob
, 0);
4313 /* Write inline summary for edge E to OB. */
4316 write_inline_edge_summary (struct output_block
*ob
, struct cgraph_edge
*e
)
4318 struct inline_edge_summary
*es
= inline_edge_summary (e
);
4321 streamer_write_uhwi (ob
, es
->call_stmt_size
);
4322 streamer_write_uhwi (ob
, es
->call_stmt_time
);
4323 streamer_write_uhwi (ob
, es
->loop_depth
);
4324 write_predicate (ob
, es
->predicate
);
4325 streamer_write_uhwi (ob
, es
->param
.length ());
4326 for (i
= 0; i
< (int) es
->param
.length (); i
++)
4327 streamer_write_uhwi (ob
, es
->param
[i
].change_prob
);
4331 /* Write inline summary for node in SET.
4332 Jump functions are shared among ipa-cp and inliner, so when ipa-cp is
4333 active, we don't need to write them twice. */
4336 inline_write_summary (void)
4338 struct cgraph_node
*node
;
4339 struct output_block
*ob
= create_output_block (LTO_section_inline_summary
);
4340 lto_symtab_encoder_t encoder
= ob
->decl_state
->symtab_node_encoder
;
4341 unsigned int count
= 0;
4344 for (i
= 0; i
< lto_symtab_encoder_size (encoder
); i
++)
4346 symtab_node
*snode
= lto_symtab_encoder_deref (encoder
, i
);
4347 cgraph_node
*cnode
= dyn_cast
<cgraph_node
*> (snode
);
4348 if (cnode
&& cnode
->definition
&& !cnode
->alias
)
4351 streamer_write_uhwi (ob
, count
);
4353 for (i
= 0; i
< lto_symtab_encoder_size (encoder
); i
++)
4355 symtab_node
*snode
= lto_symtab_encoder_deref (encoder
, i
);
4356 cgraph_node
*cnode
= dyn_cast
<cgraph_node
*> (snode
);
4357 if (cnode
&& (node
= cnode
)->definition
&& !node
->alias
)
4359 struct inline_summary
*info
= inline_summaries
->get (node
);
4360 struct bitpack_d bp
;
4361 struct cgraph_edge
*edge
;
4364 struct condition
*c
;
4366 streamer_write_uhwi (ob
,
4367 lto_symtab_encoder_encode (encoder
,
4370 streamer_write_hwi (ob
, info
->estimated_self_stack_size
);
4371 streamer_write_hwi (ob
, info
->self_size
);
4372 streamer_write_hwi (ob
, info
->self_time
);
4373 bp
= bitpack_create (ob
->main_stream
);
4374 bp_pack_value (&bp
, info
->inlinable
, 1);
4375 bp_pack_value (&bp
, info
->contains_cilk_spawn
, 1);
4376 streamer_write_bitpack (&bp
);
4377 streamer_write_uhwi (ob
, vec_safe_length (info
->conds
));
4378 for (i
= 0; vec_safe_iterate (info
->conds
, i
, &c
); i
++)
4380 streamer_write_uhwi (ob
, c
->operand_num
);
4381 streamer_write_uhwi (ob
, c
->code
);
4382 stream_write_tree (ob
, c
->val
, true);
4383 bp
= bitpack_create (ob
->main_stream
);
4384 bp_pack_value (&bp
, c
->agg_contents
, 1);
4385 bp_pack_value (&bp
, c
->by_ref
, 1);
4386 streamer_write_bitpack (&bp
);
4387 if (c
->agg_contents
)
4388 streamer_write_uhwi (ob
, c
->offset
);
4390 streamer_write_uhwi (ob
, vec_safe_length (info
->entry
));
4391 for (i
= 0; vec_safe_iterate (info
->entry
, i
, &e
); i
++)
4393 streamer_write_uhwi (ob
, e
->size
);
4394 streamer_write_uhwi (ob
, e
->time
);
4395 write_predicate (ob
, &e
->predicate
);
4397 write_predicate (ob
, info
->loop_iterations
);
4398 write_predicate (ob
, info
->loop_stride
);
4399 write_predicate (ob
, info
->array_index
);
4400 for (edge
= node
->callees
; edge
; edge
= edge
->next_callee
)
4401 write_inline_edge_summary (ob
, edge
);
4402 for (edge
= node
->indirect_calls
; edge
; edge
= edge
->next_callee
)
4403 write_inline_edge_summary (ob
, edge
);
4406 streamer_write_char_stream (ob
->main_stream
, 0);
4407 produce_asm (ob
, NULL
);
4408 destroy_output_block (ob
);
4410 if (optimize
&& !flag_ipa_cp
)
4411 ipa_prop_write_jump_functions ();
4415 /* Release inline summary. */
4418 inline_free_summary (void)
4420 struct cgraph_node
*node
;
4421 if (edge_removal_hook_holder
)
4422 symtab
->remove_edge_removal_hook (edge_removal_hook_holder
);
4423 edge_removal_hook_holder
= NULL
;
4424 if (edge_duplication_hook_holder
)
4425 symtab
->remove_edge_duplication_hook (edge_duplication_hook_holder
);
4426 edge_duplication_hook_holder
= NULL
;
4427 if (!inline_edge_summary_vec
.exists ())
4429 FOR_EACH_DEFINED_FUNCTION (node
)
4431 reset_inline_summary (node
, inline_summaries
->get (node
));
4432 inline_summaries
->release ();
4433 inline_summaries
= NULL
;
4434 inline_edge_summary_vec
.release ();
4435 edge_predicate_pool
.release ();