1 /* Inlining decision heuristics.
2 Copyright (C) 2003-2016 Free Software Foundation, Inc.
3 Contributed by Jan Hubicka
5 This file is part of GCC.
7 GCC is free software; you can redistribute it and/or modify it under
8 the terms of the GNU General Public License as published by the Free
9 Software Foundation; either version 3, or (at your option) any later
12 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
13 WARRANTY; without even the implied warranty of MERCHANTABILITY or
14 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
17 You should have received a copy of the GNU General Public License
18 along with GCC; see the file COPYING3. If not see
19 <http://www.gnu.org/licenses/>. */
21 /* Analysis used by the inliner and other passes limiting code size growth.
23 We estimate for each function
25 - average function execution time
26 - inlining size benefit (that is how much of function body size
27 and its call sequence is expected to disappear by inlining)
28 - inlining time benefit
31 - call statement size and time
33 inlinie_summary datastructures store above information locally (i.e.
34 parameters of the function itself) and globally (i.e. parameters of
35 the function created by applying all the inline decisions already
36 present in the callgraph).
38 We provide accestor to the inline_summary datastructure and
39 basic logic updating the parameters when inlining is performed.
41 The summaries are context sensitive. Context means
42 1) partial assignment of known constant values of operands
43 2) whether function is inlined into the call or not.
44 It is easy to add more variants. To represent function size and time
45 that depends on context (i.e. it is known to be optimized away when
46 context is known either by inlining or from IP-CP and clonning),
47 we use predicates. Predicates are logical formulas in
48 conjunctive-disjunctive form consisting of clauses. Clauses are bitmaps
49 specifying what conditions must be true. Conditions are simple test
50 of the form described above.
52 In order to make predicate (possibly) true, all of its clauses must
53 be (possibly) true. To make clause (possibly) true, one of conditions
54 it mentions must be (possibly) true. There are fixed bounds on
55 number of clauses and conditions and all the manipulation functions
56 are conservative in positive direction. I.e. we may lose precision
57 by thinking that predicate may be true even when it is not.
59 estimate_edge_size and estimate_edge_growth can be used to query
60 function size/time in the given context. inline_merge_summary merges
61 properties of caller and callee after inlining.
63 Finally pass_inline_parameters is exported. This is used to drive
64 computation of function parameters used by the early inliner. IPA
65 inlined performs analysis via its analyze_function method. */
69 #include "coretypes.h"
73 #include "alloc-pool.h"
74 #include "tree-pass.h"
76 #include "tree-streamer.h"
78 #include "diagnostic.h"
79 #include "fold-const.h"
80 #include "print-tree.h"
81 #include "tree-inline.h"
82 #include "gimple-pretty-print.h"
85 #include "gimple-iterator.h"
87 #include "tree-ssa-loop-niter.h"
88 #include "tree-ssa-loop.h"
89 #include "symbol-summary.h"
91 #include "ipa-inline.h"
93 #include "tree-scalar-evolution.h"
94 #include "ipa-utils.h"
96 #include "cfgexpand.h"
99 /* Estimate runtime of function can easilly run into huge numbers with many
100 nested loops. Be sure we can compute time * INLINE_SIZE_SCALE * 2 in an
101 integer. For anything larger we use gcov_type. */
102 #define MAX_TIME 500000
104 /* Number of bits in integer, but we really want to be stable across different
106 #define NUM_CONDITIONS 32
108 enum predicate_conditions
110 predicate_false_condition
= 0,
111 predicate_not_inlined_condition
= 1,
112 predicate_first_dynamic_condition
= 2
115 /* Special condition code we use to represent test that operand is compile time
117 #define IS_NOT_CONSTANT ERROR_MARK
118 /* Special condition code we use to represent test that operand is not changed
119 across invocation of the function. When operand IS_NOT_CONSTANT it is always
120 CHANGED, however i.e. loop invariants can be NOT_CHANGED given percentage
121 of executions even when they are not compile time constants. */
122 #define CHANGED IDENTIFIER_NODE
124 /* Holders of ipa cgraph hooks: */
125 static struct cgraph_2edge_hook_list
*edge_duplication_hook_holder
;
126 static struct cgraph_edge_hook_list
*edge_removal_hook_holder
;
127 static void inline_edge_removal_hook (struct cgraph_edge
*, void *);
128 static void inline_edge_duplication_hook (struct cgraph_edge
*,
129 struct cgraph_edge
*, void *);
131 /* VECtor holding inline summaries.
132 In GGC memory because conditions might point to constant trees. */
133 function_summary
<inline_summary
*> *inline_summaries
;
134 vec
<inline_edge_summary_t
> inline_edge_summary_vec
;
136 /* Cached node/edge growths. */
137 vec
<edge_growth_cache_entry
> edge_growth_cache
;
139 /* Edge predicates goes here. */
140 static object_allocator
<predicate
> edge_predicate_pool ("edge predicates");
142 /* Return true predicate (tautology).
143 We represent it by empty list of clauses. */
145 static inline struct predicate
146 true_predicate (void)
154 /* Return predicate testing single condition number COND. */
156 static inline struct predicate
157 single_cond_predicate (int cond
)
160 p
.clause
[0] = 1 << cond
;
166 /* Return false predicate. First clause require false condition. */
168 static inline struct predicate
169 false_predicate (void)
171 return single_cond_predicate (predicate_false_condition
);
175 /* Return true if P is (true). */
178 true_predicate_p (struct predicate
*p
)
180 return !p
->clause
[0];
184 /* Return true if P is (false). */
187 false_predicate_p (struct predicate
*p
)
189 if (p
->clause
[0] == (1 << predicate_false_condition
))
191 gcc_checking_assert (!p
->clause
[1]
192 && p
->clause
[0] == 1 << predicate_false_condition
);
199 /* Return predicate that is set true when function is not inlined. */
201 static inline struct predicate
202 not_inlined_predicate (void)
204 return single_cond_predicate (predicate_not_inlined_condition
);
207 /* Simple description of whether a memory load or a condition refers to a load
208 from an aggregate and if so, how and where from in the aggregate.
209 Individual fields have the same meaning like fields with the same name in
212 struct agg_position_info
214 HOST_WIDE_INT offset
;
219 /* Add condition to condition list CONDS. AGGPOS describes whether the used
220 oprand is loaded from an aggregate and where in the aggregate it is. It can
221 be NULL, which means this not a load from an aggregate. */
223 static struct predicate
224 add_condition (struct inline_summary
*summary
, int operand_num
,
225 struct agg_position_info
*aggpos
,
226 enum tree_code code
, tree val
)
230 struct condition new_cond
;
231 HOST_WIDE_INT offset
;
232 bool agg_contents
, by_ref
;
236 offset
= aggpos
->offset
;
237 agg_contents
= aggpos
->agg_contents
;
238 by_ref
= aggpos
->by_ref
;
243 agg_contents
= false;
247 gcc_checking_assert (operand_num
>= 0);
248 for (i
= 0; vec_safe_iterate (summary
->conds
, i
, &c
); i
++)
250 if (c
->operand_num
== operand_num
253 && c
->agg_contents
== agg_contents
254 && (!agg_contents
|| (c
->offset
== offset
&& c
->by_ref
== by_ref
)))
255 return single_cond_predicate (i
+ predicate_first_dynamic_condition
);
257 /* Too many conditions. Give up and return constant true. */
258 if (i
== NUM_CONDITIONS
- predicate_first_dynamic_condition
)
259 return true_predicate ();
261 new_cond
.operand_num
= operand_num
;
262 new_cond
.code
= code
;
264 new_cond
.agg_contents
= agg_contents
;
265 new_cond
.by_ref
= by_ref
;
266 new_cond
.offset
= offset
;
267 vec_safe_push (summary
->conds
, new_cond
);
268 return single_cond_predicate (i
+ predicate_first_dynamic_condition
);
272 /* Add clause CLAUSE into the predicate P. */
275 add_clause (conditions conditions
, struct predicate
*p
, clause_t clause
)
279 int insert_here
= -1;
286 /* False clause makes the whole predicate false. Kill the other variants. */
287 if (clause
== (1 << predicate_false_condition
))
289 p
->clause
[0] = (1 << predicate_false_condition
);
293 if (false_predicate_p (p
))
296 /* No one should be silly enough to add false into nontrivial clauses. */
297 gcc_checking_assert (!(clause
& (1 << predicate_false_condition
)));
299 /* Look where to insert the clause. At the same time prune out
300 clauses of P that are implied by the new clause and thus
302 for (i
= 0, i2
= 0; i
<= MAX_CLAUSES
; i
++)
304 p
->clause
[i2
] = p
->clause
[i
];
309 /* If p->clause[i] implies clause, there is nothing to add. */
310 if ((p
->clause
[i
] & clause
) == p
->clause
[i
])
312 /* We had nothing to add, none of clauses should've become
314 gcc_checking_assert (i
== i2
);
318 if (p
->clause
[i
] < clause
&& insert_here
< 0)
321 /* If clause implies p->clause[i], then p->clause[i] becomes redundant.
322 Otherwise the p->clause[i] has to stay. */
323 if ((p
->clause
[i
] & clause
) != clause
)
327 /* Look for clauses that are obviously true. I.e.
328 op0 == 5 || op0 != 5. */
329 for (c1
= predicate_first_dynamic_condition
; c1
< NUM_CONDITIONS
; c1
++)
332 if (!(clause
& (1 << c1
)))
334 cc1
= &(*conditions
)[c1
- predicate_first_dynamic_condition
];
335 /* We have no way to represent !CHANGED and !IS_NOT_CONSTANT
336 and thus there is no point for looking for them. */
337 if (cc1
->code
== CHANGED
|| cc1
->code
== IS_NOT_CONSTANT
)
339 for (c2
= c1
+ 1; c2
< NUM_CONDITIONS
; c2
++)
340 if (clause
& (1 << c2
))
343 &(*conditions
)[c1
- predicate_first_dynamic_condition
];
345 &(*conditions
)[c2
- predicate_first_dynamic_condition
];
346 if (cc1
->operand_num
== cc2
->operand_num
347 && cc1
->val
== cc2
->val
348 && cc2
->code
!= IS_NOT_CONSTANT
349 && cc2
->code
!= CHANGED
350 && cc1
->code
== invert_tree_comparison (cc2
->code
,
351 HONOR_NANS (cc1
->val
)))
357 /* We run out of variants. Be conservative in positive direction. */
358 if (i2
== MAX_CLAUSES
)
360 /* Keep clauses in decreasing order. This makes equivalence testing easy. */
361 p
->clause
[i2
+ 1] = 0;
362 if (insert_here
>= 0)
363 for (; i2
> insert_here
; i2
--)
364 p
->clause
[i2
] = p
->clause
[i2
- 1];
367 p
->clause
[insert_here
] = clause
;
373 static struct predicate
374 and_predicates (conditions conditions
,
375 struct predicate
*p
, struct predicate
*p2
)
377 struct predicate out
= *p
;
380 /* Avoid busy work. */
381 if (false_predicate_p (p2
) || true_predicate_p (p
))
383 if (false_predicate_p (p
) || true_predicate_p (p2
))
386 /* See how far predicates match. */
387 for (i
= 0; p
->clause
[i
] && p
->clause
[i
] == p2
->clause
[i
]; i
++)
389 gcc_checking_assert (i
< MAX_CLAUSES
);
392 /* Combine the predicates rest. */
393 for (; p2
->clause
[i
]; i
++)
395 gcc_checking_assert (i
< MAX_CLAUSES
);
396 add_clause (conditions
, &out
, p2
->clause
[i
]);
402 /* Return true if predicates are obviously equal. */
405 predicates_equal_p (struct predicate
*p
, struct predicate
*p2
)
408 for (i
= 0; p
->clause
[i
]; i
++)
410 gcc_checking_assert (i
< MAX_CLAUSES
);
411 gcc_checking_assert (p
->clause
[i
] > p
->clause
[i
+ 1]);
412 gcc_checking_assert (!p2
->clause
[i
]
413 || p2
->clause
[i
] > p2
->clause
[i
+ 1]);
414 if (p
->clause
[i
] != p2
->clause
[i
])
417 return !p2
->clause
[i
];
423 static struct predicate
424 or_predicates (conditions conditions
,
425 struct predicate
*p
, struct predicate
*p2
)
427 struct predicate out
= true_predicate ();
430 /* Avoid busy work. */
431 if (false_predicate_p (p2
) || true_predicate_p (p
))
433 if (false_predicate_p (p
) || true_predicate_p (p2
))
435 if (predicates_equal_p (p
, p2
))
438 /* OK, combine the predicates. */
439 for (i
= 0; p
->clause
[i
]; i
++)
440 for (j
= 0; p2
->clause
[j
]; j
++)
442 gcc_checking_assert (i
< MAX_CLAUSES
&& j
< MAX_CLAUSES
);
443 add_clause (conditions
, &out
, p
->clause
[i
] | p2
->clause
[j
]);
449 /* Having partial truth assignment in POSSIBLE_TRUTHS, return false
450 if predicate P is known to be false. */
453 evaluate_predicate (struct predicate
*p
, clause_t possible_truths
)
457 /* True remains true. */
458 if (true_predicate_p (p
))
461 gcc_assert (!(possible_truths
& (1 << predicate_false_condition
)));
463 /* See if we can find clause we can disprove. */
464 for (i
= 0; p
->clause
[i
]; i
++)
466 gcc_checking_assert (i
< MAX_CLAUSES
);
467 if (!(p
->clause
[i
] & possible_truths
))
473 /* Return the probability in range 0...REG_BR_PROB_BASE that the predicated
474 instruction will be recomputed per invocation of the inlined call. */
477 predicate_probability (conditions conds
,
478 struct predicate
*p
, clause_t possible_truths
,
479 vec
<inline_param_summary
> inline_param_summary
)
482 int combined_prob
= REG_BR_PROB_BASE
;
484 /* True remains true. */
485 if (true_predicate_p (p
))
486 return REG_BR_PROB_BASE
;
488 if (false_predicate_p (p
))
491 gcc_assert (!(possible_truths
& (1 << predicate_false_condition
)));
493 /* See if we can find clause we can disprove. */
494 for (i
= 0; p
->clause
[i
]; i
++)
496 gcc_checking_assert (i
< MAX_CLAUSES
);
497 if (!(p
->clause
[i
] & possible_truths
))
503 if (!inline_param_summary
.exists ())
504 return REG_BR_PROB_BASE
;
505 for (i2
= 0; i2
< NUM_CONDITIONS
; i2
++)
506 if ((p
->clause
[i
] & possible_truths
) & (1 << i2
))
508 if (i2
>= predicate_first_dynamic_condition
)
511 &(*conds
)[i2
- predicate_first_dynamic_condition
];
512 if (c
->code
== CHANGED
514 (int) inline_param_summary
.length ()))
517 inline_param_summary
[c
->operand_num
].change_prob
;
518 this_prob
= MAX (this_prob
, iprob
);
521 this_prob
= REG_BR_PROB_BASE
;
524 this_prob
= REG_BR_PROB_BASE
;
526 combined_prob
= MIN (this_prob
, combined_prob
);
531 return combined_prob
;
535 /* Dump conditional COND. */
538 dump_condition (FILE *f
, conditions conditions
, int cond
)
541 if (cond
== predicate_false_condition
)
542 fprintf (f
, "false");
543 else if (cond
== predicate_not_inlined_condition
)
544 fprintf (f
, "not inlined");
547 c
= &(*conditions
)[cond
- predicate_first_dynamic_condition
];
548 fprintf (f
, "op%i", c
->operand_num
);
550 fprintf (f
, "[%soffset: " HOST_WIDE_INT_PRINT_DEC
"]",
551 c
->by_ref
? "ref " : "", c
->offset
);
552 if (c
->code
== IS_NOT_CONSTANT
)
554 fprintf (f
, " not constant");
557 if (c
->code
== CHANGED
)
559 fprintf (f
, " changed");
562 fprintf (f
, " %s ", op_symbol_code (c
->code
));
563 print_generic_expr (f
, c
->val
, 1);
568 /* Dump clause CLAUSE. */
571 dump_clause (FILE *f
, conditions conds
, clause_t clause
)
578 for (i
= 0; i
< NUM_CONDITIONS
; i
++)
579 if (clause
& (1 << i
))
584 dump_condition (f
, conds
, i
);
590 /* Dump predicate PREDICATE. */
593 dump_predicate (FILE *f
, conditions conds
, struct predicate
*pred
)
596 if (true_predicate_p (pred
))
597 dump_clause (f
, conds
, 0);
599 for (i
= 0; pred
->clause
[i
]; i
++)
603 dump_clause (f
, conds
, pred
->clause
[i
]);
609 /* Dump inline hints. */
611 dump_inline_hints (FILE *f
, inline_hints hints
)
615 fprintf (f
, "inline hints:");
616 if (hints
& INLINE_HINT_indirect_call
)
618 hints
&= ~INLINE_HINT_indirect_call
;
619 fprintf (f
, " indirect_call");
621 if (hints
& INLINE_HINT_loop_iterations
)
623 hints
&= ~INLINE_HINT_loop_iterations
;
624 fprintf (f
, " loop_iterations");
626 if (hints
& INLINE_HINT_loop_stride
)
628 hints
&= ~INLINE_HINT_loop_stride
;
629 fprintf (f
, " loop_stride");
631 if (hints
& INLINE_HINT_same_scc
)
633 hints
&= ~INLINE_HINT_same_scc
;
634 fprintf (f
, " same_scc");
636 if (hints
& INLINE_HINT_in_scc
)
638 hints
&= ~INLINE_HINT_in_scc
;
639 fprintf (f
, " in_scc");
641 if (hints
& INLINE_HINT_cross_module
)
643 hints
&= ~INLINE_HINT_cross_module
;
644 fprintf (f
, " cross_module");
646 if (hints
& INLINE_HINT_declared_inline
)
648 hints
&= ~INLINE_HINT_declared_inline
;
649 fprintf (f
, " declared_inline");
651 if (hints
& INLINE_HINT_array_index
)
653 hints
&= ~INLINE_HINT_array_index
;
654 fprintf (f
, " array_index");
656 if (hints
& INLINE_HINT_known_hot
)
658 hints
&= ~INLINE_HINT_known_hot
;
659 fprintf (f
, " known_hot");
665 /* Record SIZE and TIME under condition PRED into the inline summary. */
668 account_size_time (struct inline_summary
*summary
, int size
, int time
,
669 struct predicate
*pred
)
675 if (false_predicate_p (pred
))
678 /* We need to create initial empty unconitional clause, but otherwie
679 we don't need to account empty times and sizes. */
680 if (!size
&& !time
&& summary
->entry
)
683 /* Watch overflow that might result from insane profiles. */
684 if (time
> MAX_TIME
* INLINE_TIME_SCALE
)
685 time
= MAX_TIME
* INLINE_TIME_SCALE
;
686 gcc_assert (time
>= 0);
688 for (i
= 0; vec_safe_iterate (summary
->entry
, i
, &e
); i
++)
689 if (predicates_equal_p (&e
->predicate
, pred
))
698 e
= &(*summary
->entry
)[0];
699 gcc_assert (!e
->predicate
.clause
[0]);
700 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
702 "\t\tReached limit on number of entries, "
703 "ignoring the predicate.");
705 if (dump_file
&& (dump_flags
& TDF_DETAILS
) && (time
|| size
))
708 "\t\tAccounting size:%3.2f, time:%3.2f on %spredicate:",
709 ((double) size
) / INLINE_SIZE_SCALE
,
710 ((double) time
) / INLINE_TIME_SCALE
, found
? "" : "new ");
711 dump_predicate (dump_file
, summary
->conds
, pred
);
715 struct size_time_entry new_entry
;
716 new_entry
.size
= size
;
717 new_entry
.time
= time
;
718 new_entry
.predicate
= *pred
;
719 vec_safe_push (summary
->entry
, new_entry
);
725 if (e
->time
> MAX_TIME
* INLINE_TIME_SCALE
)
726 e
->time
= MAX_TIME
* INLINE_TIME_SCALE
;
730 /* We proved E to be unreachable, redirect it to __bultin_unreachable. */
732 static struct cgraph_edge
*
733 redirect_to_unreachable (struct cgraph_edge
*e
)
735 struct cgraph_node
*callee
= !e
->inline_failed
? e
->callee
: NULL
;
736 struct cgraph_node
*target
= cgraph_node::get_create
737 (builtin_decl_implicit (BUILT_IN_UNREACHABLE
));
740 e
= e
->resolve_speculation (target
->decl
);
742 e
->make_direct (target
);
744 e
->redirect_callee (target
);
745 struct inline_edge_summary
*es
= inline_edge_summary (e
);
746 e
->inline_failed
= CIF_UNREACHABLE
;
749 es
->call_stmt_size
= 0;
750 es
->call_stmt_time
= 0;
752 callee
->remove_symbol_and_inline_clones ();
756 /* Set predicate for edge E. */
759 edge_set_predicate (struct cgraph_edge
*e
, struct predicate
*predicate
)
761 /* If the edge is determined to be never executed, redirect it
762 to BUILTIN_UNREACHABLE to save inliner from inlining into it. */
763 if (predicate
&& false_predicate_p (predicate
)
764 /* When handling speculative edges, we need to do the redirection
765 just once. Do it always on the direct edge, so we do not
766 attempt to resolve speculation while duplicating the edge. */
767 && (!e
->speculative
|| e
->callee
))
768 e
= redirect_to_unreachable (e
);
770 struct inline_edge_summary
*es
= inline_edge_summary (e
);
771 if (predicate
&& !true_predicate_p (predicate
))
774 es
->predicate
= edge_predicate_pool
.allocate ();
775 *es
->predicate
= *predicate
;
780 edge_predicate_pool
.remove (es
->predicate
);
781 es
->predicate
= NULL
;
785 /* Set predicate for hint *P. */
788 set_hint_predicate (struct predicate
**p
, struct predicate new_predicate
)
790 if (false_predicate_p (&new_predicate
) || true_predicate_p (&new_predicate
))
793 edge_predicate_pool
.remove (*p
);
799 *p
= edge_predicate_pool
.allocate ();
805 /* KNOWN_VALS is partial mapping of parameters of NODE to constant values.
806 KNOWN_AGGS is a vector of aggreggate jump functions for each parameter.
807 Return clause of possible truths. When INLINE_P is true, assume that we are
810 ERROR_MARK means compile time invariant. */
813 evaluate_conditions_for_known_args (struct cgraph_node
*node
,
815 vec
<tree
> known_vals
,
816 vec
<ipa_agg_jump_function_p
>
819 clause_t clause
= inline_p
? 0 : 1 << predicate_not_inlined_condition
;
820 struct inline_summary
*info
= inline_summaries
->get (node
);
824 for (i
= 0; vec_safe_iterate (info
->conds
, i
, &c
); i
++)
829 /* We allow call stmt to have fewer arguments than the callee function
830 (especially for K&R style programs). So bound check here (we assume
831 known_aggs vector, if non-NULL, has the same length as
833 gcc_checking_assert (!known_aggs
.exists ()
834 || (known_vals
.length () == known_aggs
.length ()));
835 if (c
->operand_num
>= (int) known_vals
.length ())
837 clause
|= 1 << (i
+ predicate_first_dynamic_condition
);
843 struct ipa_agg_jump_function
*agg
;
845 if (c
->code
== CHANGED
847 && (known_vals
[c
->operand_num
] == error_mark_node
))
850 if (known_aggs
.exists ())
852 agg
= known_aggs
[c
->operand_num
];
853 val
= ipa_find_agg_cst_for_param (agg
, c
->offset
, c
->by_ref
);
860 val
= known_vals
[c
->operand_num
];
861 if (val
== error_mark_node
&& c
->code
!= CHANGED
)
867 clause
|= 1 << (i
+ predicate_first_dynamic_condition
);
870 if (c
->code
== IS_NOT_CONSTANT
|| c
->code
== CHANGED
)
873 if (operand_equal_p (TYPE_SIZE (TREE_TYPE (c
->val
)),
874 TYPE_SIZE (TREE_TYPE (val
)), 0))
876 val
= fold_unary (VIEW_CONVERT_EXPR
, TREE_TYPE (c
->val
), val
);
879 ? fold_binary_to_constant (c
->code
, boolean_type_node
, val
, c
->val
)
882 if (res
&& integer_zerop (res
))
885 clause
|= 1 << (i
+ predicate_first_dynamic_condition
);
891 /* Work out what conditions might be true at invocation of E. */
894 evaluate_properties_for_edge (struct cgraph_edge
*e
, bool inline_p
,
895 clause_t
*clause_ptr
,
896 vec
<tree
> *known_vals_ptr
,
897 vec
<ipa_polymorphic_call_context
>
899 vec
<ipa_agg_jump_function_p
> *known_aggs_ptr
)
901 struct cgraph_node
*callee
= e
->callee
->ultimate_alias_target ();
902 struct inline_summary
*info
= inline_summaries
->get (callee
);
903 vec
<tree
> known_vals
= vNULL
;
904 vec
<ipa_agg_jump_function_p
> known_aggs
= vNULL
;
907 *clause_ptr
= inline_p
? 0 : 1 << predicate_not_inlined_condition
;
909 known_vals_ptr
->create (0);
910 if (known_contexts_ptr
)
911 known_contexts_ptr
->create (0);
913 if (ipa_node_params_sum
914 && !e
->call_stmt_cannot_inline_p
915 && ((clause_ptr
&& info
->conds
) || known_vals_ptr
|| known_contexts_ptr
))
917 struct ipa_node_params
*parms_info
;
918 struct ipa_edge_args
*args
= IPA_EDGE_REF (e
);
919 struct inline_edge_summary
*es
= inline_edge_summary (e
);
920 int i
, count
= ipa_get_cs_argument_count (args
);
922 if (e
->caller
->global
.inlined_to
)
923 parms_info
= IPA_NODE_REF (e
->caller
->global
.inlined_to
);
925 parms_info
= IPA_NODE_REF (e
->caller
);
927 if (count
&& (info
->conds
|| known_vals_ptr
))
928 known_vals
.safe_grow_cleared (count
);
929 if (count
&& (info
->conds
|| known_aggs_ptr
))
930 known_aggs
.safe_grow_cleared (count
);
931 if (count
&& known_contexts_ptr
)
932 known_contexts_ptr
->safe_grow_cleared (count
);
934 for (i
= 0; i
< count
; i
++)
936 struct ipa_jump_func
*jf
= ipa_get_ith_jump_func (args
, i
);
937 tree cst
= ipa_value_from_jfunc (parms_info
, jf
);
939 if (!cst
&& e
->call_stmt
940 && i
< (int)gimple_call_num_args (e
->call_stmt
))
942 cst
= gimple_call_arg (e
->call_stmt
, i
);
943 if (!is_gimple_min_invariant (cst
))
948 gcc_checking_assert (TREE_CODE (cst
) != TREE_BINFO
);
949 if (known_vals
.exists ())
952 else if (inline_p
&& !es
->param
[i
].change_prob
)
953 known_vals
[i
] = error_mark_node
;
955 if (known_contexts_ptr
)
956 (*known_contexts_ptr
)[i
] = ipa_context_from_jfunc (parms_info
, e
,
958 /* TODO: When IPA-CP starts propagating and merging aggregate jump
959 functions, use its knowledge of the caller too, just like the
960 scalar case above. */
961 known_aggs
[i
] = &jf
->agg
;
964 else if (e
->call_stmt
&& !e
->call_stmt_cannot_inline_p
965 && ((clause_ptr
&& info
->conds
) || known_vals_ptr
))
967 int i
, count
= (int)gimple_call_num_args (e
->call_stmt
);
969 if (count
&& (info
->conds
|| known_vals_ptr
))
970 known_vals
.safe_grow_cleared (count
);
971 for (i
= 0; i
< count
; i
++)
973 tree cst
= gimple_call_arg (e
->call_stmt
, i
);
974 if (!is_gimple_min_invariant (cst
))
982 *clause_ptr
= evaluate_conditions_for_known_args (callee
, inline_p
,
983 known_vals
, known_aggs
);
986 *known_vals_ptr
= known_vals
;
988 known_vals
.release ();
991 *known_aggs_ptr
= known_aggs
;
993 known_aggs
.release ();
997 /* Allocate the inline summary vector or resize it to cover all cgraph nodes. */
1000 inline_summary_alloc (void)
1002 if (!edge_removal_hook_holder
)
1003 edge_removal_hook_holder
=
1004 symtab
->add_edge_removal_hook (&inline_edge_removal_hook
, NULL
);
1005 if (!edge_duplication_hook_holder
)
1006 edge_duplication_hook_holder
=
1007 symtab
->add_edge_duplication_hook (&inline_edge_duplication_hook
, NULL
);
1009 if (!inline_summaries
)
1010 inline_summaries
= (inline_summary_t
*) inline_summary_t::create_ggc (symtab
);
1012 if (inline_edge_summary_vec
.length () <= (unsigned) symtab
->edges_max_uid
)
1013 inline_edge_summary_vec
.safe_grow_cleared (symtab
->edges_max_uid
+ 1);
1016 /* We are called multiple time for given function; clear
1017 data from previous run so they are not cumulated. */
1020 reset_inline_edge_summary (struct cgraph_edge
*e
)
1022 if (e
->uid
< (int) inline_edge_summary_vec
.length ())
1024 struct inline_edge_summary
*es
= inline_edge_summary (e
);
1026 es
->call_stmt_size
= es
->call_stmt_time
= 0;
1028 edge_predicate_pool
.remove (es
->predicate
);
1029 es
->predicate
= NULL
;
1030 es
->param
.release ();
1034 /* We are called multiple time for given function; clear
1035 data from previous run so they are not cumulated. */
1038 reset_inline_summary (struct cgraph_node
*node
,
1039 inline_summary
*info
)
1041 struct cgraph_edge
*e
;
1043 info
->self_size
= info
->self_time
= 0;
1044 info
->estimated_stack_size
= 0;
1045 info
->estimated_self_stack_size
= 0;
1046 info
->stack_frame_offset
= 0;
1051 if (info
->loop_iterations
)
1053 edge_predicate_pool
.remove (info
->loop_iterations
);
1054 info
->loop_iterations
= NULL
;
1056 if (info
->loop_stride
)
1058 edge_predicate_pool
.remove (info
->loop_stride
);
1059 info
->loop_stride
= NULL
;
1061 if (info
->array_index
)
1063 edge_predicate_pool
.remove (info
->array_index
);
1064 info
->array_index
= NULL
;
1066 vec_free (info
->conds
);
1067 vec_free (info
->entry
);
1068 for (e
= node
->callees
; e
; e
= e
->next_callee
)
1069 reset_inline_edge_summary (e
);
1070 for (e
= node
->indirect_calls
; e
; e
= e
->next_callee
)
1071 reset_inline_edge_summary (e
);
1072 info
->fp_expressions
= false;
1075 /* Hook that is called by cgraph.c when a node is removed. */
1078 inline_summary_t::remove (cgraph_node
*node
, inline_summary
*info
)
1080 reset_inline_summary (node
, info
);
1083 /* Remap predicate P of former function to be predicate of duplicated function.
1084 POSSIBLE_TRUTHS is clause of possible truths in the duplicated node,
1085 INFO is inline summary of the duplicated node. */
1087 static struct predicate
1088 remap_predicate_after_duplication (struct predicate
*p
,
1089 clause_t possible_truths
,
1090 struct inline_summary
*info
)
1092 struct predicate new_predicate
= true_predicate ();
1094 for (j
= 0; p
->clause
[j
]; j
++)
1095 if (!(possible_truths
& p
->clause
[j
]))
1097 new_predicate
= false_predicate ();
1101 add_clause (info
->conds
, &new_predicate
,
1102 possible_truths
& p
->clause
[j
]);
1103 return new_predicate
;
1106 /* Same as remap_predicate_after_duplication but handle hint predicate *P.
1107 Additionally care about allocating new memory slot for updated predicate
1108 and set it to NULL when it becomes true or false (and thus uninteresting).
1112 remap_hint_predicate_after_duplication (struct predicate
**p
,
1113 clause_t possible_truths
,
1114 struct inline_summary
*info
)
1116 struct predicate new_predicate
;
1121 new_predicate
= remap_predicate_after_duplication (*p
,
1122 possible_truths
, info
);
1123 /* We do not want to free previous predicate; it is used by node origin. */
1125 set_hint_predicate (p
, new_predicate
);
1129 /* Hook that is called by cgraph.c when a node is duplicated. */
1131 inline_summary_t::duplicate (cgraph_node
*src
,
1134 inline_summary
*info
)
1136 inline_summary_alloc ();
1137 memcpy (info
, inline_summaries
->get (src
), sizeof (inline_summary
));
1138 /* TODO: as an optimization, we may avoid copying conditions
1139 that are known to be false or true. */
1140 info
->conds
= vec_safe_copy (info
->conds
);
1142 /* When there are any replacements in the function body, see if we can figure
1143 out that something was optimized out. */
1144 if (ipa_node_params_sum
&& dst
->clone
.tree_map
)
1146 vec
<size_time_entry
, va_gc
> *entry
= info
->entry
;
1147 /* Use SRC parm info since it may not be copied yet. */
1148 struct ipa_node_params
*parms_info
= IPA_NODE_REF (src
);
1149 vec
<tree
> known_vals
= vNULL
;
1150 int count
= ipa_get_param_count (parms_info
);
1152 clause_t possible_truths
;
1153 struct predicate true_pred
= true_predicate ();
1155 int optimized_out_size
= 0;
1156 bool inlined_to_p
= false;
1157 struct cgraph_edge
*edge
, *next
;
1160 known_vals
.safe_grow_cleared (count
);
1161 for (i
= 0; i
< count
; i
++)
1163 struct ipa_replace_map
*r
;
1165 for (j
= 0; vec_safe_iterate (dst
->clone
.tree_map
, j
, &r
); j
++)
1167 if (((!r
->old_tree
&& r
->parm_num
== i
)
1168 || (r
->old_tree
&& r
->old_tree
== ipa_get_param (parms_info
, i
)))
1169 && r
->replace_p
&& !r
->ref_p
)
1171 known_vals
[i
] = r
->new_tree
;
1176 possible_truths
= evaluate_conditions_for_known_args (dst
, false,
1179 known_vals
.release ();
1181 account_size_time (info
, 0, 0, &true_pred
);
1183 /* Remap size_time vectors.
1184 Simplify the predicate by prunning out alternatives that are known
1186 TODO: as on optimization, we can also eliminate conditions known
1188 for (i
= 0; vec_safe_iterate (entry
, i
, &e
); i
++)
1190 struct predicate new_predicate
;
1191 new_predicate
= remap_predicate_after_duplication (&e
->predicate
,
1194 if (false_predicate_p (&new_predicate
))
1195 optimized_out_size
+= e
->size
;
1197 account_size_time (info
, e
->size
, e
->time
, &new_predicate
);
1200 /* Remap edge predicates with the same simplification as above.
1201 Also copy constantness arrays. */
1202 for (edge
= dst
->callees
; edge
; edge
= next
)
1204 struct predicate new_predicate
;
1205 struct inline_edge_summary
*es
= inline_edge_summary (edge
);
1206 next
= edge
->next_callee
;
1208 if (!edge
->inline_failed
)
1209 inlined_to_p
= true;
1212 new_predicate
= remap_predicate_after_duplication (es
->predicate
,
1215 if (false_predicate_p (&new_predicate
)
1216 && !false_predicate_p (es
->predicate
))
1217 optimized_out_size
+= es
->call_stmt_size
* INLINE_SIZE_SCALE
;
1218 edge_set_predicate (edge
, &new_predicate
);
1221 /* Remap indirect edge predicates with the same simplificaiton as above.
1222 Also copy constantness arrays. */
1223 for (edge
= dst
->indirect_calls
; edge
; edge
= next
)
1225 struct predicate new_predicate
;
1226 struct inline_edge_summary
*es
= inline_edge_summary (edge
);
1227 next
= edge
->next_callee
;
1229 gcc_checking_assert (edge
->inline_failed
);
1232 new_predicate
= remap_predicate_after_duplication (es
->predicate
,
1235 if (false_predicate_p (&new_predicate
)
1236 && !false_predicate_p (es
->predicate
))
1237 optimized_out_size
+= es
->call_stmt_size
* INLINE_SIZE_SCALE
;
1238 edge_set_predicate (edge
, &new_predicate
);
1240 remap_hint_predicate_after_duplication (&info
->loop_iterations
,
1241 possible_truths
, info
);
1242 remap_hint_predicate_after_duplication (&info
->loop_stride
,
1243 possible_truths
, info
);
1244 remap_hint_predicate_after_duplication (&info
->array_index
,
1245 possible_truths
, info
);
1247 /* If inliner or someone after inliner will ever start producing
1248 non-trivial clones, we will get trouble with lack of information
1249 about updating self sizes, because size vectors already contains
1250 sizes of the calees. */
1251 gcc_assert (!inlined_to_p
|| !optimized_out_size
);
1255 info
->entry
= vec_safe_copy (info
->entry
);
1256 if (info
->loop_iterations
)
1258 predicate p
= *info
->loop_iterations
;
1259 info
->loop_iterations
= NULL
;
1260 set_hint_predicate (&info
->loop_iterations
, p
);
1262 if (info
->loop_stride
)
1264 predicate p
= *info
->loop_stride
;
1265 info
->loop_stride
= NULL
;
1266 set_hint_predicate (&info
->loop_stride
, p
);
1268 if (info
->array_index
)
1270 predicate p
= *info
->array_index
;
1271 info
->array_index
= NULL
;
1272 set_hint_predicate (&info
->array_index
, p
);
1275 if (!dst
->global
.inlined_to
)
1276 inline_update_overall_summary (dst
);
1280 /* Hook that is called by cgraph.c when a node is duplicated. */
1283 inline_edge_duplication_hook (struct cgraph_edge
*src
,
1284 struct cgraph_edge
*dst
,
1285 ATTRIBUTE_UNUSED
void *data
)
1287 struct inline_edge_summary
*info
;
1288 struct inline_edge_summary
*srcinfo
;
1289 inline_summary_alloc ();
1290 info
= inline_edge_summary (dst
);
1291 srcinfo
= inline_edge_summary (src
);
1292 memcpy (info
, srcinfo
, sizeof (struct inline_edge_summary
));
1293 info
->predicate
= NULL
;
1294 edge_set_predicate (dst
, srcinfo
->predicate
);
1295 info
->param
= srcinfo
->param
.copy ();
1296 if (!dst
->indirect_unknown_callee
&& src
->indirect_unknown_callee
)
1298 info
->call_stmt_size
-= (eni_size_weights
.indirect_call_cost
1299 - eni_size_weights
.call_cost
);
1300 info
->call_stmt_time
-= (eni_time_weights
.indirect_call_cost
1301 - eni_time_weights
.call_cost
);
1306 /* Keep edge cache consistent across edge removal. */
1309 inline_edge_removal_hook (struct cgraph_edge
*edge
,
1310 void *data ATTRIBUTE_UNUSED
)
1312 if (edge_growth_cache
.exists ())
1313 reset_edge_growth_cache (edge
);
1314 reset_inline_edge_summary (edge
);
1318 /* Initialize growth caches. */
1321 initialize_growth_caches (void)
1323 if (symtab
->edges_max_uid
)
1324 edge_growth_cache
.safe_grow_cleared (symtab
->edges_max_uid
);
1328 /* Free growth caches. */
1331 free_growth_caches (void)
1333 edge_growth_cache
.release ();
1337 /* Dump edge summaries associated to NODE and recursively to all clones.
1338 Indent by INDENT. */
1341 dump_inline_edge_summary (FILE *f
, int indent
, struct cgraph_node
*node
,
1342 struct inline_summary
*info
)
1344 struct cgraph_edge
*edge
;
1345 for (edge
= node
->callees
; edge
; edge
= edge
->next_callee
)
1347 struct inline_edge_summary
*es
= inline_edge_summary (edge
);
1348 struct cgraph_node
*callee
= edge
->callee
->ultimate_alias_target ();
1352 "%*s%s/%i %s\n%*s loop depth:%2i freq:%4i size:%2i"
1353 " time: %2i callee size:%2i stack:%2i",
1354 indent
, "", callee
->name (), callee
->order
,
1355 !edge
->inline_failed
1356 ? "inlined" : cgraph_inline_failed_string (edge
-> inline_failed
),
1357 indent
, "", es
->loop_depth
, edge
->frequency
,
1358 es
->call_stmt_size
, es
->call_stmt_time
,
1359 (int) inline_summaries
->get (callee
)->size
/ INLINE_SIZE_SCALE
,
1360 (int) inline_summaries
->get (callee
)->estimated_stack_size
);
1364 fprintf (f
, " predicate: ");
1365 dump_predicate (f
, info
->conds
, es
->predicate
);
1369 if (es
->param
.exists ())
1370 for (i
= 0; i
< (int) es
->param
.length (); i
++)
1372 int prob
= es
->param
[i
].change_prob
;
1375 fprintf (f
, "%*s op%i is compile time invariant\n",
1377 else if (prob
!= REG_BR_PROB_BASE
)
1378 fprintf (f
, "%*s op%i change %f%% of time\n", indent
+ 2, "", i
,
1379 prob
* 100.0 / REG_BR_PROB_BASE
);
1381 if (!edge
->inline_failed
)
1383 fprintf (f
, "%*sStack frame offset %i, callee self size %i,"
1384 " callee size %i\n",
1386 (int) inline_summaries
->get (callee
)->stack_frame_offset
,
1387 (int) inline_summaries
->get (callee
)->estimated_self_stack_size
,
1388 (int) inline_summaries
->get (callee
)->estimated_stack_size
);
1389 dump_inline_edge_summary (f
, indent
+ 2, callee
, info
);
1392 for (edge
= node
->indirect_calls
; edge
; edge
= edge
->next_callee
)
1394 struct inline_edge_summary
*es
= inline_edge_summary (edge
);
1395 fprintf (f
, "%*sindirect call loop depth:%2i freq:%4i size:%2i"
1399 edge
->frequency
, es
->call_stmt_size
, es
->call_stmt_time
);
1402 fprintf (f
, "predicate: ");
1403 dump_predicate (f
, info
->conds
, es
->predicate
);
1412 dump_inline_summary (FILE *f
, struct cgraph_node
*node
)
1414 if (node
->definition
)
1416 struct inline_summary
*s
= inline_summaries
->get (node
);
1419 fprintf (f
, "Inline summary for %s/%i", node
->name (),
1421 if (DECL_DISREGARD_INLINE_LIMITS (node
->decl
))
1422 fprintf (f
, " always_inline");
1424 fprintf (f
, " inlinable");
1425 if (s
->contains_cilk_spawn
)
1426 fprintf (f
, " contains_cilk_spawn");
1427 if (s
->fp_expressions
)
1428 fprintf (f
, " fp_expression");
1429 fprintf (f
, "\n self time: %i\n", s
->self_time
);
1430 fprintf (f
, " global time: %i\n", s
->time
);
1431 fprintf (f
, " self size: %i\n", s
->self_size
);
1432 fprintf (f
, " global size: %i\n", s
->size
);
1433 fprintf (f
, " min size: %i\n", s
->min_size
);
1434 fprintf (f
, " self stack: %i\n",
1435 (int) s
->estimated_self_stack_size
);
1436 fprintf (f
, " global stack: %i\n", (int) s
->estimated_stack_size
);
1438 fprintf (f
, " estimated growth:%i\n", (int) s
->growth
);
1440 fprintf (f
, " In SCC: %i\n", (int) s
->scc_no
);
1441 for (i
= 0; vec_safe_iterate (s
->entry
, i
, &e
); i
++)
1443 fprintf (f
, " size:%f, time:%f, predicate:",
1444 (double) e
->size
/ INLINE_SIZE_SCALE
,
1445 (double) e
->time
/ INLINE_TIME_SCALE
);
1446 dump_predicate (f
, s
->conds
, &e
->predicate
);
1448 if (s
->loop_iterations
)
1450 fprintf (f
, " loop iterations:");
1451 dump_predicate (f
, s
->conds
, s
->loop_iterations
);
1455 fprintf (f
, " loop stride:");
1456 dump_predicate (f
, s
->conds
, s
->loop_stride
);
1460 fprintf (f
, " array index:");
1461 dump_predicate (f
, s
->conds
, s
->array_index
);
1463 fprintf (f
, " calls:\n");
1464 dump_inline_edge_summary (f
, 4, node
, s
);
1470 debug_inline_summary (struct cgraph_node
*node
)
1472 dump_inline_summary (stderr
, node
);
1476 dump_inline_summaries (FILE *f
)
1478 struct cgraph_node
*node
;
1480 FOR_EACH_DEFINED_FUNCTION (node
)
1481 if (!node
->global
.inlined_to
)
1482 dump_inline_summary (f
, node
);
1485 /* Give initial reasons why inlining would fail on EDGE. This gets either
1486 nullified or usually overwritten by more precise reasons later. */
1489 initialize_inline_failed (struct cgraph_edge
*e
)
1491 struct cgraph_node
*callee
= e
->callee
;
1493 if (e
->inline_failed
&& e
->inline_failed
!= CIF_BODY_NOT_AVAILABLE
1494 && cgraph_inline_failed_type (e
->inline_failed
) == CIF_FINAL_ERROR
)
1496 else if (e
->indirect_unknown_callee
)
1497 e
->inline_failed
= CIF_INDIRECT_UNKNOWN_CALL
;
1498 else if (!callee
->definition
)
1499 e
->inline_failed
= CIF_BODY_NOT_AVAILABLE
;
1500 else if (callee
->local
.redefined_extern_inline
)
1501 e
->inline_failed
= CIF_REDEFINED_EXTERN_INLINE
;
1502 else if (cfun
&& fn_contains_cilk_spawn_p (cfun
))
1503 /* We can't inline if the function is spawing a function. */
1504 e
->inline_failed
= CIF_CILK_SPAWN
;
1506 e
->inline_failed
= CIF_FUNCTION_NOT_CONSIDERED
;
1507 gcc_checking_assert (!e
->call_stmt_cannot_inline_p
1508 || cgraph_inline_failed_type (e
->inline_failed
)
1509 == CIF_FINAL_ERROR
);
1512 /* Callback of walk_aliased_vdefs. Flags that it has been invoked to the
1513 boolean variable pointed to by DATA. */
1516 mark_modified (ao_ref
*ao ATTRIBUTE_UNUSED
, tree vdef ATTRIBUTE_UNUSED
,
1519 bool *b
= (bool *) data
;
1524 /* If OP refers to value of function parameter, return the corresponding
1528 unmodified_parm_1 (gimple
*stmt
, tree op
)
1530 /* SSA_NAME referring to parm default def? */
1531 if (TREE_CODE (op
) == SSA_NAME
1532 && SSA_NAME_IS_DEFAULT_DEF (op
)
1533 && TREE_CODE (SSA_NAME_VAR (op
)) == PARM_DECL
)
1534 return SSA_NAME_VAR (op
);
1535 /* Non-SSA parm reference? */
1536 if (TREE_CODE (op
) == PARM_DECL
)
1538 bool modified
= false;
1541 ao_ref_init (&refd
, op
);
1542 walk_aliased_vdefs (&refd
, gimple_vuse (stmt
), mark_modified
, &modified
,
1550 /* If OP refers to value of function parameter, return the corresponding
1551 parameter. Also traverse chains of SSA register assignments. */
1554 unmodified_parm (gimple
*stmt
, tree op
)
1556 tree res
= unmodified_parm_1 (stmt
, op
);
1560 if (TREE_CODE (op
) == SSA_NAME
1561 && !SSA_NAME_IS_DEFAULT_DEF (op
)
1562 && gimple_assign_single_p (SSA_NAME_DEF_STMT (op
)))
1563 return unmodified_parm (SSA_NAME_DEF_STMT (op
),
1564 gimple_assign_rhs1 (SSA_NAME_DEF_STMT (op
)));
1568 /* If OP refers to a value of a function parameter or value loaded from an
1569 aggregate passed to a parameter (either by value or reference), return TRUE
1570 and store the number of the parameter to *INDEX_P and information whether
1571 and how it has been loaded from an aggregate into *AGGPOS. INFO describes
1572 the function parameters, STMT is the statement in which OP is used or
1576 unmodified_parm_or_parm_agg_item (struct ipa_func_body_info
*fbi
,
1577 gimple
*stmt
, tree op
, int *index_p
,
1578 struct agg_position_info
*aggpos
)
1580 tree res
= unmodified_parm_1 (stmt
, op
);
1582 gcc_checking_assert (aggpos
);
1585 *index_p
= ipa_get_param_decl_index (fbi
->info
, res
);
1588 aggpos
->agg_contents
= false;
1589 aggpos
->by_ref
= false;
1593 if (TREE_CODE (op
) == SSA_NAME
)
1595 if (SSA_NAME_IS_DEFAULT_DEF (op
)
1596 || !gimple_assign_single_p (SSA_NAME_DEF_STMT (op
)))
1598 stmt
= SSA_NAME_DEF_STMT (op
);
1599 op
= gimple_assign_rhs1 (stmt
);
1600 if (!REFERENCE_CLASS_P (op
))
1601 return unmodified_parm_or_parm_agg_item (fbi
, stmt
, op
, index_p
,
1605 aggpos
->agg_contents
= true;
1606 return ipa_load_from_parm_agg (fbi
, fbi
->info
->descriptors
,
1607 stmt
, op
, index_p
, &aggpos
->offset
,
1608 NULL
, &aggpos
->by_ref
);
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_func_body_info
*fbi
,
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 (fbi
, 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
1785 (summary
, index
, &aggpos
, this_code
,
1786 unshare_expr_without_location (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 (fbi
, set_stmt
, op2
, &index
, &aggpos
))
1815 FOR_EACH_EDGE (e
, ei
, bb
->succs
) if (e
->flags
& EDGE_FALSE_VALUE
)
1817 struct predicate p
= add_condition (summary
, index
, &aggpos
,
1818 IS_NOT_CONSTANT
, NULL_TREE
);
1819 e
->aux
= edge_predicate_pool
.allocate ();
1820 *(struct predicate
*) e
->aux
= p
;
1825 /* If BB ends by a switch we can turn into predicates, attach corresponding
1826 predicates to the CFG edges. */
1829 set_switch_stmt_execution_predicate (struct ipa_func_body_info
*fbi
,
1830 struct inline_summary
*summary
,
1836 struct agg_position_info aggpos
;
1842 lastg
= last_stmt (bb
);
1843 if (!lastg
|| gimple_code (lastg
) != GIMPLE_SWITCH
)
1845 gswitch
*last
= as_a
<gswitch
*> (lastg
);
1846 op
= gimple_switch_index (last
);
1847 if (!unmodified_parm_or_parm_agg_item (fbi
, last
, op
, &index
, &aggpos
))
1850 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1852 e
->aux
= edge_predicate_pool
.allocate ();
1853 *(struct predicate
*) e
->aux
= false_predicate ();
1855 n
= gimple_switch_num_labels (last
);
1856 for (case_idx
= 0; case_idx
< n
; ++case_idx
)
1858 tree cl
= gimple_switch_label (last
, case_idx
);
1862 e
= find_edge (bb
, label_to_block (CASE_LABEL (cl
)));
1863 min
= CASE_LOW (cl
);
1864 max
= CASE_HIGH (cl
);
1866 /* For default we might want to construct predicate that none
1867 of cases is met, but it is bit hard to do not having negations
1868 of conditionals handy. */
1870 p
= true_predicate ();
1872 p
= add_condition (summary
, index
, &aggpos
, EQ_EXPR
,
1873 unshare_expr_without_location (min
));
1876 struct predicate p1
, p2
;
1877 p1
= add_condition (summary
, index
, &aggpos
, GE_EXPR
,
1878 unshare_expr_without_location (min
));
1879 p2
= add_condition (summary
, index
, &aggpos
, LE_EXPR
,
1880 unshare_expr_without_location (max
));
1881 p
= and_predicates (summary
->conds
, &p1
, &p2
);
1883 *(struct predicate
*) e
->aux
1884 = or_predicates (summary
->conds
, &p
, (struct predicate
*) e
->aux
);
1889 /* For each BB in NODE attach to its AUX pointer predicate under
1890 which it is executable. */
1893 compute_bb_predicates (struct ipa_func_body_info
*fbi
,
1894 struct cgraph_node
*node
,
1895 struct inline_summary
*summary
)
1897 struct function
*my_function
= DECL_STRUCT_FUNCTION (node
->decl
);
1901 FOR_EACH_BB_FN (bb
, my_function
)
1903 set_cond_stmt_execution_predicate (fbi
, summary
, bb
);
1904 set_switch_stmt_execution_predicate (fbi
, summary
, bb
);
1907 /* Entry block is always executable. */
1908 ENTRY_BLOCK_PTR_FOR_FN (my_function
)->aux
1909 = edge_predicate_pool
.allocate ();
1910 *(struct predicate
*) ENTRY_BLOCK_PTR_FOR_FN (my_function
)->aux
1911 = true_predicate ();
1913 /* A simple dataflow propagation of predicates forward in the CFG.
1914 TODO: work in reverse postorder. */
1918 FOR_EACH_BB_FN (bb
, my_function
)
1920 struct predicate p
= false_predicate ();
1923 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
1927 struct predicate this_bb_predicate
1928 = *(struct predicate
*) e
->src
->aux
;
1931 = and_predicates (summary
->conds
, &this_bb_predicate
,
1932 (struct predicate
*) e
->aux
);
1933 p
= or_predicates (summary
->conds
, &p
, &this_bb_predicate
);
1934 if (true_predicate_p (&p
))
1938 if (false_predicate_p (&p
))
1939 gcc_assert (!bb
->aux
);
1945 bb
->aux
= edge_predicate_pool
.allocate ();
1946 *((struct predicate
*) bb
->aux
) = p
;
1948 else if (!predicates_equal_p (&p
, (struct predicate
*) bb
->aux
))
1950 /* This OR operation is needed to ensure monotonous data flow
1951 in the case we hit the limit on number of clauses and the
1952 and/or operations above give approximate answers. */
1953 p
= or_predicates (summary
->conds
, &p
, (struct predicate
*)bb
->aux
);
1954 if (!predicates_equal_p (&p
, (struct predicate
*) bb
->aux
))
1957 *((struct predicate
*) bb
->aux
) = p
;
1966 /* We keep info about constantness of SSA names. */
1968 typedef struct predicate predicate_t
;
1969 /* Return predicate specifying when the STMT might have result that is not
1970 a compile time constant. */
1972 static struct predicate
1973 will_be_nonconstant_expr_predicate (struct ipa_node_params
*info
,
1974 struct inline_summary
*summary
,
1976 vec
<predicate_t
> nonconstant_names
)
1981 while (UNARY_CLASS_P (expr
))
1982 expr
= TREE_OPERAND (expr
, 0);
1984 parm
= unmodified_parm (NULL
, expr
);
1985 if (parm
&& (index
= ipa_get_param_decl_index (info
, parm
)) >= 0)
1986 return add_condition (summary
, index
, NULL
, CHANGED
, NULL_TREE
);
1987 if (is_gimple_min_invariant (expr
))
1988 return false_predicate ();
1989 if (TREE_CODE (expr
) == SSA_NAME
)
1990 return nonconstant_names
[SSA_NAME_VERSION (expr
)];
1991 if (BINARY_CLASS_P (expr
) || COMPARISON_CLASS_P (expr
))
1993 struct predicate p1
= will_be_nonconstant_expr_predicate
1994 (info
, summary
, TREE_OPERAND (expr
, 0),
1996 struct predicate p2
;
1997 if (true_predicate_p (&p1
))
1999 p2
= will_be_nonconstant_expr_predicate (info
, summary
,
2000 TREE_OPERAND (expr
, 1),
2002 return or_predicates (summary
->conds
, &p1
, &p2
);
2004 else if (TREE_CODE (expr
) == COND_EXPR
)
2006 struct predicate p1
= will_be_nonconstant_expr_predicate
2007 (info
, summary
, TREE_OPERAND (expr
, 0),
2009 struct predicate p2
;
2010 if (true_predicate_p (&p1
))
2012 p2
= will_be_nonconstant_expr_predicate (info
, summary
,
2013 TREE_OPERAND (expr
, 1),
2015 if (true_predicate_p (&p2
))
2017 p1
= or_predicates (summary
->conds
, &p1
, &p2
);
2018 p2
= will_be_nonconstant_expr_predicate (info
, summary
,
2019 TREE_OPERAND (expr
, 2),
2021 return or_predicates (summary
->conds
, &p1
, &p2
);
2028 return false_predicate ();
2032 /* Return predicate specifying when the STMT might have result that is not
2033 a compile time constant. */
2035 static struct predicate
2036 will_be_nonconstant_predicate (struct ipa_func_body_info
*fbi
,
2037 struct inline_summary
*summary
,
2039 vec
<predicate_t
> nonconstant_names
)
2041 struct predicate p
= true_predicate ();
2044 struct predicate op_non_const
;
2047 struct agg_position_info aggpos
;
2049 /* What statments might be optimized away
2050 when their arguments are constant. */
2051 if (gimple_code (stmt
) != GIMPLE_ASSIGN
2052 && gimple_code (stmt
) != GIMPLE_COND
2053 && gimple_code (stmt
) != GIMPLE_SWITCH
2054 && (gimple_code (stmt
) != GIMPLE_CALL
2055 || !(gimple_call_flags (stmt
) & ECF_CONST
)))
2058 /* Stores will stay anyway. */
2059 if (gimple_store_p (stmt
))
2062 is_load
= gimple_assign_load_p (stmt
);
2064 /* Loads can be optimized when the value is known. */
2068 gcc_assert (gimple_assign_single_p (stmt
));
2069 op
= gimple_assign_rhs1 (stmt
);
2070 if (!unmodified_parm_or_parm_agg_item (fbi
, stmt
, op
, &base_index
,
2077 /* See if we understand all operands before we start
2078 adding conditionals. */
2079 FOR_EACH_SSA_TREE_OPERAND (use
, stmt
, iter
, SSA_OP_USE
)
2081 tree parm
= unmodified_parm (stmt
, use
);
2082 /* For arguments we can build a condition. */
2083 if (parm
&& ipa_get_param_decl_index (fbi
->info
, parm
) >= 0)
2085 if (TREE_CODE (use
) != SSA_NAME
)
2087 /* If we know when operand is constant,
2088 we still can say something useful. */
2089 if (!true_predicate_p (&nonconstant_names
[SSA_NAME_VERSION (use
)]))
2096 add_condition (summary
, base_index
, &aggpos
, CHANGED
, NULL
);
2098 op_non_const
= false_predicate ();
2099 FOR_EACH_SSA_TREE_OPERAND (use
, stmt
, iter
, SSA_OP_USE
)
2101 tree parm
= unmodified_parm (stmt
, use
);
2104 if (parm
&& (index
= ipa_get_param_decl_index (fbi
->info
, parm
)) >= 0)
2106 if (index
!= base_index
)
2107 p
= add_condition (summary
, index
, NULL
, CHANGED
, NULL_TREE
);
2112 p
= nonconstant_names
[SSA_NAME_VERSION (use
)];
2113 op_non_const
= or_predicates (summary
->conds
, &p
, &op_non_const
);
2115 if ((gimple_code (stmt
) == GIMPLE_ASSIGN
|| gimple_code (stmt
) == GIMPLE_CALL
)
2116 && gimple_op (stmt
, 0)
2117 && TREE_CODE (gimple_op (stmt
, 0)) == SSA_NAME
)
2118 nonconstant_names
[SSA_NAME_VERSION (gimple_op (stmt
, 0))]
2120 return op_non_const
;
2123 struct record_modified_bb_info
2129 /* Callback of walk_aliased_vdefs. Records basic blocks where the value may be
2130 set except for info->stmt. */
2133 record_modified (ao_ref
*ao ATTRIBUTE_UNUSED
, tree vdef
, void *data
)
2135 struct record_modified_bb_info
*info
=
2136 (struct record_modified_bb_info
*) data
;
2137 if (SSA_NAME_DEF_STMT (vdef
) == info
->stmt
)
2139 bitmap_set_bit (info
->bb_set
,
2140 SSA_NAME_IS_DEFAULT_DEF (vdef
)
2141 ? ENTRY_BLOCK_PTR_FOR_FN (cfun
)->index
2142 : gimple_bb (SSA_NAME_DEF_STMT (vdef
))->index
);
2146 /* Return probability (based on REG_BR_PROB_BASE) that I-th parameter of STMT
2147 will change since last invocation of STMT.
2149 Value 0 is reserved for compile time invariants.
2150 For common parameters it is REG_BR_PROB_BASE. For loop invariants it
2151 ought to be REG_BR_PROB_BASE / estimated_iters. */
2154 param_change_prob (gimple
*stmt
, int i
)
2156 tree op
= gimple_call_arg (stmt
, i
);
2157 basic_block bb
= gimple_bb (stmt
);
2160 /* Global invariants neve change. */
2161 if (is_gimple_min_invariant (op
))
2163 /* We would have to do non-trivial analysis to really work out what
2164 is the probability of value to change (i.e. when init statement
2165 is in a sibling loop of the call).
2167 We do an conservative estimate: when call is executed N times more often
2168 than the statement defining value, we take the frequency 1/N. */
2169 if (TREE_CODE (op
) == SSA_NAME
)
2174 return REG_BR_PROB_BASE
;
2176 if (SSA_NAME_IS_DEFAULT_DEF (op
))
2177 init_freq
= ENTRY_BLOCK_PTR_FOR_FN (cfun
)->frequency
;
2179 init_freq
= gimple_bb (SSA_NAME_DEF_STMT (op
))->frequency
;
2183 if (init_freq
< bb
->frequency
)
2184 return MAX (GCOV_COMPUTE_SCALE (init_freq
, bb
->frequency
), 1);
2186 return REG_BR_PROB_BASE
;
2189 base
= get_base_address (op
);
2194 struct record_modified_bb_info info
;
2197 tree init
= ctor_for_folding (base
);
2199 if (init
!= error_mark_node
)
2202 return REG_BR_PROB_BASE
;
2203 ao_ref_init (&refd
, op
);
2205 info
.bb_set
= BITMAP_ALLOC (NULL
);
2206 walk_aliased_vdefs (&refd
, gimple_vuse (stmt
), record_modified
, &info
,
2208 if (bitmap_bit_p (info
.bb_set
, bb
->index
))
2210 BITMAP_FREE (info
.bb_set
);
2211 return REG_BR_PROB_BASE
;
2214 /* Assume that every memory is initialized at entry.
2215 TODO: Can we easilly determine if value is always defined
2216 and thus we may skip entry block? */
2217 if (ENTRY_BLOCK_PTR_FOR_FN (cfun
)->frequency
)
2218 max
= ENTRY_BLOCK_PTR_FOR_FN (cfun
)->frequency
;
2222 EXECUTE_IF_SET_IN_BITMAP (info
.bb_set
, 0, index
, bi
)
2223 max
= MIN (max
, BASIC_BLOCK_FOR_FN (cfun
, index
)->frequency
);
2225 BITMAP_FREE (info
.bb_set
);
2226 if (max
< bb
->frequency
)
2227 return MAX (GCOV_COMPUTE_SCALE (max
, bb
->frequency
), 1);
2229 return REG_BR_PROB_BASE
;
2231 return REG_BR_PROB_BASE
;
2234 /* Find whether a basic block BB is the final block of a (half) diamond CFG
2235 sub-graph and if the predicate the condition depends on is known. If so,
2236 return true and store the pointer the predicate in *P. */
2239 phi_result_unknown_predicate (struct ipa_node_params
*info
,
2240 inline_summary
*summary
, basic_block bb
,
2241 struct predicate
*p
,
2242 vec
<predicate_t
> nonconstant_names
)
2246 basic_block first_bb
= NULL
;
2249 if (single_pred_p (bb
))
2251 *p
= false_predicate ();
2255 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
2257 if (single_succ_p (e
->src
))
2259 if (!single_pred_p (e
->src
))
2262 first_bb
= single_pred (e
->src
);
2263 else if (single_pred (e
->src
) != first_bb
)
2270 else if (e
->src
!= first_bb
)
2278 stmt
= last_stmt (first_bb
);
2280 || gimple_code (stmt
) != GIMPLE_COND
2281 || !is_gimple_ip_invariant (gimple_cond_rhs (stmt
)))
2284 *p
= will_be_nonconstant_expr_predicate (info
, summary
,
2285 gimple_cond_lhs (stmt
),
2287 if (true_predicate_p (p
))
2293 /* Given a PHI statement in a function described by inline properties SUMMARY
2294 and *P being the predicate describing whether the selected PHI argument is
2295 known, store a predicate for the result of the PHI statement into
2296 NONCONSTANT_NAMES, if possible. */
2299 predicate_for_phi_result (struct inline_summary
*summary
, gphi
*phi
,
2300 struct predicate
*p
,
2301 vec
<predicate_t
> nonconstant_names
)
2305 for (i
= 0; i
< gimple_phi_num_args (phi
); i
++)
2307 tree arg
= gimple_phi_arg (phi
, i
)->def
;
2308 if (!is_gimple_min_invariant (arg
))
2310 gcc_assert (TREE_CODE (arg
) == SSA_NAME
);
2311 *p
= or_predicates (summary
->conds
, p
,
2312 &nonconstant_names
[SSA_NAME_VERSION (arg
)]);
2313 if (true_predicate_p (p
))
2318 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2320 fprintf (dump_file
, "\t\tphi predicate: ");
2321 dump_predicate (dump_file
, summary
->conds
, p
);
2323 nonconstant_names
[SSA_NAME_VERSION (gimple_phi_result (phi
))] = *p
;
2326 /* Return predicate specifying when array index in access OP becomes non-constant. */
2328 static struct predicate
2329 array_index_predicate (inline_summary
*info
,
2330 vec
< predicate_t
> nonconstant_names
, tree op
)
2332 struct predicate p
= false_predicate ();
2333 while (handled_component_p (op
))
2335 if (TREE_CODE (op
) == ARRAY_REF
|| TREE_CODE (op
) == ARRAY_RANGE_REF
)
2337 if (TREE_CODE (TREE_OPERAND (op
, 1)) == SSA_NAME
)
2338 p
= or_predicates (info
->conds
, &p
,
2339 &nonconstant_names
[SSA_NAME_VERSION
2340 (TREE_OPERAND (op
, 1))]);
2342 op
= TREE_OPERAND (op
, 0);
2347 /* For a typical usage of __builtin_expect (a<b, 1), we
2348 may introduce an extra relation stmt:
2349 With the builtin, we have
2352 t3 = __builtin_expect (t2, 1);
2355 Without the builtin, we have
2358 This affects the size/time estimation and may have
2359 an impact on the earlier inlining.
2360 Here find this pattern and fix it up later. */
2363 find_foldable_builtin_expect (basic_block bb
)
2365 gimple_stmt_iterator bsi
;
2367 for (bsi
= gsi_start_bb (bb
); !gsi_end_p (bsi
); gsi_next (&bsi
))
2369 gimple
*stmt
= gsi_stmt (bsi
);
2370 if (gimple_call_builtin_p (stmt
, BUILT_IN_EXPECT
)
2371 || (is_gimple_call (stmt
)
2372 && gimple_call_internal_p (stmt
)
2373 && gimple_call_internal_fn (stmt
) == IFN_BUILTIN_EXPECT
))
2375 tree var
= gimple_call_lhs (stmt
);
2376 tree arg
= gimple_call_arg (stmt
, 0);
2377 use_operand_p use_p
;
2384 gcc_assert (TREE_CODE (var
) == SSA_NAME
);
2386 while (TREE_CODE (arg
) == SSA_NAME
)
2388 gimple
*stmt_tmp
= SSA_NAME_DEF_STMT (arg
);
2389 if (!is_gimple_assign (stmt_tmp
))
2391 switch (gimple_assign_rhs_code (stmt_tmp
))
2410 arg
= gimple_assign_rhs1 (stmt_tmp
);
2413 if (match
&& single_imm_use (var
, &use_p
, &use_stmt
)
2414 && gimple_code (use_stmt
) == GIMPLE_COND
)
2421 /* Return true when the basic blocks contains only clobbers followed by RESX.
2422 Such BBs are kept around to make removal of dead stores possible with
2423 presence of EH and will be optimized out by optimize_clobbers later in the
2426 NEED_EH is used to recurse in case the clobber has non-EH predecestors
2427 that can be clobber only, too.. When it is false, the RESX is not necessary
2428 on the end of basic block. */
2431 clobber_only_eh_bb_p (basic_block bb
, bool need_eh
= true)
2433 gimple_stmt_iterator gsi
= gsi_last_bb (bb
);
2439 if (gsi_end_p (gsi
))
2441 if (gimple_code (gsi_stmt (gsi
)) != GIMPLE_RESX
)
2445 else if (!single_succ_p (bb
))
2448 for (; !gsi_end_p (gsi
); gsi_prev (&gsi
))
2450 gimple
*stmt
= gsi_stmt (gsi
);
2451 if (is_gimple_debug (stmt
))
2453 if (gimple_clobber_p (stmt
))
2455 if (gimple_code (stmt
) == GIMPLE_LABEL
)
2460 /* See if all predecestors are either throws or clobber only BBs. */
2461 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
2462 if (!(e
->flags
& EDGE_EH
)
2463 && !clobber_only_eh_bb_p (e
->src
, false))
2469 /* Return true if STMT compute a floating point expression that may be affected
2470 by -ffast-math and similar flags. */
2473 fp_expression_p (gimple
*stmt
)
2478 FOR_EACH_SSA_TREE_OPERAND (op
, stmt
, i
, SSA_OP_DEF
|SSA_OP_USE
)
2479 if (FLOAT_TYPE_P (TREE_TYPE (op
)))
2484 /* Compute function body size parameters for NODE.
2485 When EARLY is true, we compute only simple summaries without
2486 non-trivial predicates to drive the early inliner. */
2489 estimate_function_body_sizes (struct cgraph_node
*node
, bool early
)
2492 /* Estimate static overhead for function prologue/epilogue and alignment. */
2494 /* Benefits are scaled by probability of elimination that is in range
2497 struct function
*my_function
= DECL_STRUCT_FUNCTION (node
->decl
);
2499 struct inline_summary
*info
= inline_summaries
->get (node
);
2500 struct predicate bb_predicate
;
2501 struct ipa_func_body_info fbi
;
2502 vec
<predicate_t
> nonconstant_names
= vNULL
;
2505 predicate array_index
= true_predicate ();
2506 gimple
*fix_builtin_expect_stmt
;
2508 gcc_assert (my_function
&& my_function
->cfg
);
2509 gcc_assert (cfun
== my_function
);
2511 memset(&fbi
, 0, sizeof(fbi
));
2515 /* When optimizing and analyzing for IPA inliner, initialize loop optimizer
2516 so we can produce proper inline hints.
2518 When optimizing and analyzing for early inliner, initialize node params
2519 so we can produce correct BB predicates. */
2521 if (opt_for_fn (node
->decl
, optimize
))
2523 calculate_dominance_info (CDI_DOMINATORS
);
2525 loop_optimizer_init (LOOPS_NORMAL
| LOOPS_HAVE_RECORDED_EXITS
);
2528 ipa_check_create_node_params ();
2529 ipa_initialize_node_params (node
);
2532 if (ipa_node_params_sum
)
2535 fbi
.info
= IPA_NODE_REF (node
);
2536 fbi
.bb_infos
= vNULL
;
2537 fbi
.bb_infos
.safe_grow_cleared (last_basic_block_for_fn (cfun
));
2538 fbi
.param_count
= count_formal_params(node
->decl
);
2539 nonconstant_names
.safe_grow_cleared
2540 (SSANAMES (my_function
)->length ());
2545 fprintf (dump_file
, "\nAnalyzing function body size: %s\n",
2548 /* When we run into maximal number of entries, we assign everything to the
2549 constant truth case. Be sure to have it in list. */
2550 bb_predicate
= true_predicate ();
2551 account_size_time (info
, 0, 0, &bb_predicate
);
2553 bb_predicate
= not_inlined_predicate ();
2554 account_size_time (info
, 2 * INLINE_SIZE_SCALE
, 0, &bb_predicate
);
2557 compute_bb_predicates (&fbi
, node
, info
);
2558 order
= XNEWVEC (int, n_basic_blocks_for_fn (cfun
));
2559 nblocks
= pre_and_rev_post_order_compute (NULL
, order
, false);
2560 for (n
= 0; n
< nblocks
; n
++)
2562 bb
= BASIC_BLOCK_FOR_FN (cfun
, order
[n
]);
2563 freq
= compute_call_stmt_bb_frequency (node
->decl
, bb
);
2564 if (clobber_only_eh_bb_p (bb
))
2566 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2567 fprintf (dump_file
, "\n Ignoring BB %i;"
2568 " it will be optimized away by cleanup_clobbers\n",
2573 /* TODO: Obviously predicates can be propagated down across CFG. */
2577 bb_predicate
= *(struct predicate
*) bb
->aux
;
2579 bb_predicate
= false_predicate ();
2582 bb_predicate
= true_predicate ();
2584 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2586 fprintf (dump_file
, "\n BB %i predicate:", bb
->index
);
2587 dump_predicate (dump_file
, info
->conds
, &bb_predicate
);
2590 if (fbi
.info
&& nonconstant_names
.exists ())
2592 struct predicate phi_predicate
;
2593 bool first_phi
= true;
2595 for (gphi_iterator bsi
= gsi_start_phis (bb
); !gsi_end_p (bsi
);
2599 && !phi_result_unknown_predicate (fbi
.info
, info
, bb
,
2604 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2606 fprintf (dump_file
, " ");
2607 print_gimple_stmt (dump_file
, gsi_stmt (bsi
), 0, 0);
2609 predicate_for_phi_result (info
, bsi
.phi (), &phi_predicate
,
2614 fix_builtin_expect_stmt
= find_foldable_builtin_expect (bb
);
2616 for (gimple_stmt_iterator bsi
= gsi_start_bb (bb
); !gsi_end_p (bsi
);
2619 gimple
*stmt
= gsi_stmt (bsi
);
2620 int this_size
= estimate_num_insns (stmt
, &eni_size_weights
);
2621 int this_time
= estimate_num_insns (stmt
, &eni_time_weights
);
2623 struct predicate will_be_nonconstant
;
2625 /* This relation stmt should be folded after we remove
2626 buildin_expect call. Adjust the cost here. */
2627 if (stmt
== fix_builtin_expect_stmt
)
2633 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2635 fprintf (dump_file
, " ");
2636 print_gimple_stmt (dump_file
, stmt
, 0, 0);
2637 fprintf (dump_file
, "\t\tfreq:%3.2f size:%3i time:%3i\n",
2638 ((double) freq
) / CGRAPH_FREQ_BASE
, this_size
,
2642 if (gimple_assign_load_p (stmt
) && nonconstant_names
.exists ())
2644 struct predicate this_array_index
;
2646 array_index_predicate (info
, nonconstant_names
,
2647 gimple_assign_rhs1 (stmt
));
2648 if (!false_predicate_p (&this_array_index
))
2650 and_predicates (info
->conds
, &array_index
,
2653 if (gimple_store_p (stmt
) && nonconstant_names
.exists ())
2655 struct predicate this_array_index
;
2657 array_index_predicate (info
, nonconstant_names
,
2658 gimple_get_lhs (stmt
));
2659 if (!false_predicate_p (&this_array_index
))
2661 and_predicates (info
->conds
, &array_index
,
2666 if (is_gimple_call (stmt
)
2667 && !gimple_call_internal_p (stmt
))
2669 struct cgraph_edge
*edge
= node
->get_edge (stmt
);
2670 struct inline_edge_summary
*es
= inline_edge_summary (edge
);
2672 /* Special case: results of BUILT_IN_CONSTANT_P will be always
2673 resolved as constant. We however don't want to optimize
2674 out the cgraph edges. */
2675 if (nonconstant_names
.exists ()
2676 && gimple_call_builtin_p (stmt
, BUILT_IN_CONSTANT_P
)
2677 && gimple_call_lhs (stmt
)
2678 && TREE_CODE (gimple_call_lhs (stmt
)) == SSA_NAME
)
2680 struct predicate false_p
= false_predicate ();
2681 nonconstant_names
[SSA_NAME_VERSION (gimple_call_lhs (stmt
))]
2684 if (ipa_node_params_sum
)
2686 int count
= gimple_call_num_args (stmt
);
2690 es
->param
.safe_grow_cleared (count
);
2691 for (i
= 0; i
< count
; i
++)
2693 int prob
= param_change_prob (stmt
, i
);
2694 gcc_assert (prob
>= 0 && prob
<= REG_BR_PROB_BASE
);
2695 es
->param
[i
].change_prob
= prob
;
2699 es
->call_stmt_size
= this_size
;
2700 es
->call_stmt_time
= this_time
;
2701 es
->loop_depth
= bb_loop_depth (bb
);
2702 edge_set_predicate (edge
, &bb_predicate
);
2705 /* TODO: When conditional jump or swithc is known to be constant, but
2706 we did not translate it into the predicates, we really can account
2707 just maximum of the possible paths. */
2710 = will_be_nonconstant_predicate (&fbi
, info
,
2711 stmt
, nonconstant_names
);
2712 if (this_time
|| this_size
)
2718 prob
= eliminated_by_inlining_prob (stmt
);
2719 if (prob
== 1 && dump_file
&& (dump_flags
& TDF_DETAILS
))
2721 "\t\t50%% will be eliminated by inlining\n");
2722 if (prob
== 2 && dump_file
&& (dump_flags
& TDF_DETAILS
))
2723 fprintf (dump_file
, "\t\tWill be eliminated by inlining\n");
2726 p
= and_predicates (info
->conds
, &bb_predicate
,
2727 &will_be_nonconstant
);
2729 p
= true_predicate ();
2731 if (!false_predicate_p (&p
)
2732 || (is_gimple_call (stmt
)
2733 && !false_predicate_p (&bb_predicate
)))
2737 if (time
> MAX_TIME
* INLINE_TIME_SCALE
)
2738 time
= MAX_TIME
* INLINE_TIME_SCALE
;
2741 /* We account everything but the calls. Calls have their own
2742 size/time info attached to cgraph edges. This is necessary
2743 in order to make the cost disappear after inlining. */
2744 if (!is_gimple_call (stmt
))
2748 struct predicate ip
= not_inlined_predicate ();
2749 ip
= and_predicates (info
->conds
, &ip
, &p
);
2750 account_size_time (info
, this_size
* prob
,
2751 this_time
* prob
, &ip
);
2754 account_size_time (info
, this_size
* (2 - prob
),
2755 this_time
* (2 - prob
), &p
);
2758 if (!info
->fp_expressions
&& fp_expression_p (stmt
))
2760 info
->fp_expressions
= true;
2762 fprintf (dump_file
, " fp_expression set\n");
2765 gcc_assert (time
>= 0);
2766 gcc_assert (size
>= 0);
2770 set_hint_predicate (&inline_summaries
->get (node
)->array_index
, array_index
);
2771 time
= (time
+ CGRAPH_FREQ_BASE
/ 2) / CGRAPH_FREQ_BASE
;
2772 if (time
> MAX_TIME
)
2776 if (nonconstant_names
.exists () && !early
)
2779 predicate loop_iterations
= true_predicate ();
2780 predicate loop_stride
= true_predicate ();
2782 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2783 flow_loops_dump (dump_file
, NULL
, 0);
2785 FOR_EACH_LOOP (loop
, 0)
2790 struct tree_niter_desc niter_desc
;
2791 bb_predicate
= *(struct predicate
*) loop
->header
->aux
;
2793 exits
= get_loop_exit_edges (loop
);
2794 FOR_EACH_VEC_ELT (exits
, j
, ex
)
2795 if (number_of_iterations_exit (loop
, ex
, &niter_desc
, false)
2796 && !is_gimple_min_invariant (niter_desc
.niter
))
2798 predicate will_be_nonconstant
2799 = will_be_nonconstant_expr_predicate (fbi
.info
, info
,
2802 if (!true_predicate_p (&will_be_nonconstant
))
2803 will_be_nonconstant
= and_predicates (info
->conds
,
2805 &will_be_nonconstant
);
2806 if (!true_predicate_p (&will_be_nonconstant
)
2807 && !false_predicate_p (&will_be_nonconstant
))
2808 /* This is slightly inprecise. We may want to represent each
2809 loop with independent predicate. */
2811 and_predicates (info
->conds
, &loop_iterations
,
2812 &will_be_nonconstant
);
2817 /* To avoid quadratic behavior we analyze stride predicates only
2818 with respect to the containing loop. Thus we simply iterate
2819 over all defs in the outermost loop body. */
2820 for (loop
= loops_for_fn (cfun
)->tree_root
->inner
;
2821 loop
!= NULL
; loop
= loop
->next
)
2823 basic_block
*body
= get_loop_body (loop
);
2824 for (unsigned i
= 0; i
< loop
->num_nodes
; i
++)
2826 gimple_stmt_iterator gsi
;
2827 bb_predicate
= *(struct predicate
*) body
[i
]->aux
;
2828 for (gsi
= gsi_start_bb (body
[i
]); !gsi_end_p (gsi
);
2831 gimple
*stmt
= gsi_stmt (gsi
);
2833 if (!is_gimple_assign (stmt
))
2836 tree def
= gimple_assign_lhs (stmt
);
2837 if (TREE_CODE (def
) != SSA_NAME
)
2841 if (!simple_iv (loop_containing_stmt (stmt
),
2842 loop_containing_stmt (stmt
),
2844 || is_gimple_min_invariant (iv
.step
))
2847 predicate will_be_nonconstant
2848 = will_be_nonconstant_expr_predicate (fbi
.info
, info
,
2851 if (!true_predicate_p (&will_be_nonconstant
))
2853 = and_predicates (info
->conds
, &bb_predicate
,
2854 &will_be_nonconstant
);
2855 if (!true_predicate_p (&will_be_nonconstant
)
2856 && !false_predicate_p (&will_be_nonconstant
))
2857 /* This is slightly inprecise. We may want to represent
2858 each loop with independent predicate. */
2859 loop_stride
= and_predicates (info
->conds
, &loop_stride
,
2860 &will_be_nonconstant
);
2865 set_hint_predicate (&inline_summaries
->get (node
)->loop_iterations
,
2867 set_hint_predicate (&inline_summaries
->get (node
)->loop_stride
,
2871 FOR_ALL_BB_FN (bb
, my_function
)
2877 edge_predicate_pool
.remove ((predicate
*)bb
->aux
);
2879 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
2882 edge_predicate_pool
.remove ((predicate
*) e
->aux
);
2886 inline_summaries
->get (node
)->self_time
= time
;
2887 inline_summaries
->get (node
)->self_size
= size
;
2888 nonconstant_names
.release ();
2889 ipa_release_body_info (&fbi
);
2890 if (opt_for_fn (node
->decl
, optimize
))
2893 loop_optimizer_finalize ();
2894 else if (!ipa_edge_args_vector
)
2895 ipa_free_all_node_params ();
2896 free_dominance_info (CDI_DOMINATORS
);
2900 fprintf (dump_file
, "\n");
2901 dump_inline_summary (dump_file
, node
);
2906 /* Compute parameters of functions used by inliner.
2907 EARLY is true when we compute parameters for the early inliner */
2910 compute_inline_parameters (struct cgraph_node
*node
, bool early
)
2912 HOST_WIDE_INT self_stack_size
;
2913 struct cgraph_edge
*e
;
2914 struct inline_summary
*info
;
2916 gcc_assert (!node
->global
.inlined_to
);
2918 inline_summary_alloc ();
2920 info
= inline_summaries
->get (node
);
2921 reset_inline_summary (node
, info
);
2923 /* FIXME: Thunks are inlinable, but tree-inline don't know how to do that.
2924 Once this happen, we will need to more curefully predict call
2926 if (node
->thunk
.thunk_p
)
2928 struct inline_edge_summary
*es
= inline_edge_summary (node
->callees
);
2929 struct predicate t
= true_predicate ();
2931 info
->inlinable
= 0;
2932 node
->callees
->inline_failed
= CIF_THUNK
;
2933 node
->local
.can_change_signature
= false;
2934 es
->call_stmt_time
= 1;
2935 es
->call_stmt_size
= 1;
2936 account_size_time (info
, 0, 0, &t
);
2940 /* Even is_gimple_min_invariant rely on current_function_decl. */
2941 push_cfun (DECL_STRUCT_FUNCTION (node
->decl
));
2943 /* Estimate the stack size for the function if we're optimizing. */
2944 self_stack_size
= optimize
? estimated_stack_frame_size (node
) : 0;
2945 info
->estimated_self_stack_size
= self_stack_size
;
2946 info
->estimated_stack_size
= self_stack_size
;
2947 info
->stack_frame_offset
= 0;
2949 /* Can this function be inlined at all? */
2950 if (!opt_for_fn (node
->decl
, optimize
)
2951 && !lookup_attribute ("always_inline",
2952 DECL_ATTRIBUTES (node
->decl
)))
2953 info
->inlinable
= false;
2955 info
->inlinable
= tree_inlinable_function_p (node
->decl
);
2957 info
->contains_cilk_spawn
= fn_contains_cilk_spawn_p (cfun
);
2959 /* Type attributes can use parameter indices to describe them. */
2960 if (TYPE_ATTRIBUTES (TREE_TYPE (node
->decl
)))
2961 node
->local
.can_change_signature
= false;
2964 /* Otherwise, inlinable functions always can change signature. */
2965 if (info
->inlinable
)
2966 node
->local
.can_change_signature
= true;
2969 /* Functions calling builtin_apply can not change signature. */
2970 for (e
= node
->callees
; e
; e
= e
->next_callee
)
2972 tree
cdecl = e
->callee
->decl
;
2973 if (DECL_BUILT_IN (cdecl)
2974 && DECL_BUILT_IN_CLASS (cdecl) == BUILT_IN_NORMAL
2975 && (DECL_FUNCTION_CODE (cdecl) == BUILT_IN_APPLY_ARGS
2976 || DECL_FUNCTION_CODE (cdecl) == BUILT_IN_VA_START
))
2979 node
->local
.can_change_signature
= !e
;
2982 estimate_function_body_sizes (node
, early
);
2984 for (e
= node
->callees
; e
; e
= e
->next_callee
)
2985 if (e
->callee
->comdat_local_p ())
2987 node
->calls_comdat_local
= (e
!= NULL
);
2989 /* Inlining characteristics are maintained by the cgraph_mark_inline. */
2990 info
->time
= info
->self_time
;
2991 info
->size
= info
->self_size
;
2992 info
->stack_frame_offset
= 0;
2993 info
->estimated_stack_size
= info
->estimated_self_stack_size
;
2996 inline_update_overall_summary (node
);
2997 gcc_assert (info
->time
== info
->self_time
2998 && info
->size
== info
->self_size
);
3005 /* Compute parameters of functions used by inliner using
3006 current_function_decl. */
3009 compute_inline_parameters_for_current (void)
3011 compute_inline_parameters (cgraph_node::get (current_function_decl
), true);
3017 const pass_data pass_data_inline_parameters
=
3019 GIMPLE_PASS
, /* type */
3020 "inline_param", /* name */
3021 OPTGROUP_INLINE
, /* optinfo_flags */
3022 TV_INLINE_PARAMETERS
, /* tv_id */
3023 0, /* properties_required */
3024 0, /* properties_provided */
3025 0, /* properties_destroyed */
3026 0, /* todo_flags_start */
3027 0, /* todo_flags_finish */
3030 class pass_inline_parameters
: public gimple_opt_pass
3033 pass_inline_parameters (gcc::context
*ctxt
)
3034 : gimple_opt_pass (pass_data_inline_parameters
, ctxt
)
3037 /* opt_pass methods: */
3038 opt_pass
* clone () { return new pass_inline_parameters (m_ctxt
); }
3039 virtual unsigned int execute (function
*)
3041 return compute_inline_parameters_for_current ();
3044 }; // class pass_inline_parameters
3049 make_pass_inline_parameters (gcc::context
*ctxt
)
3051 return new pass_inline_parameters (ctxt
);
3055 /* Estimate benefit devirtualizing indirect edge IE, provided KNOWN_VALS,
3056 KNOWN_CONTEXTS and KNOWN_AGGS. */
3059 estimate_edge_devirt_benefit (struct cgraph_edge
*ie
,
3060 int *size
, int *time
,
3061 vec
<tree
> known_vals
,
3062 vec
<ipa_polymorphic_call_context
> known_contexts
,
3063 vec
<ipa_agg_jump_function_p
> known_aggs
)
3066 struct cgraph_node
*callee
;
3067 struct inline_summary
*isummary
;
3068 enum availability avail
;
3071 if (!known_vals
.exists () && !known_contexts
.exists ())
3073 if (!opt_for_fn (ie
->caller
->decl
, flag_indirect_inlining
))
3076 target
= ipa_get_indirect_edge_target (ie
, known_vals
, known_contexts
,
3077 known_aggs
, &speculative
);
3078 if (!target
|| speculative
)
3081 /* Account for difference in cost between indirect and direct calls. */
3082 *size
-= (eni_size_weights
.indirect_call_cost
- eni_size_weights
.call_cost
);
3083 *time
-= (eni_time_weights
.indirect_call_cost
- eni_time_weights
.call_cost
);
3084 gcc_checking_assert (*time
>= 0);
3085 gcc_checking_assert (*size
>= 0);
3087 callee
= cgraph_node::get (target
);
3088 if (!callee
|| !callee
->definition
)
3090 callee
= callee
->function_symbol (&avail
);
3091 if (avail
< AVAIL_AVAILABLE
)
3093 isummary
= inline_summaries
->get (callee
);
3094 return isummary
->inlinable
;
3097 /* Increase SIZE, MIN_SIZE (if non-NULL) and TIME for size and time needed to
3098 handle edge E with probability PROB.
3099 Set HINTS if edge may be devirtualized.
3100 KNOWN_VALS, KNOWN_AGGS and KNOWN_CONTEXTS describe context of the call
3104 estimate_edge_size_and_time (struct cgraph_edge
*e
, int *size
, int *min_size
,
3107 vec
<tree
> known_vals
,
3108 vec
<ipa_polymorphic_call_context
> known_contexts
,
3109 vec
<ipa_agg_jump_function_p
> known_aggs
,
3110 inline_hints
*hints
)
3112 struct inline_edge_summary
*es
= inline_edge_summary (e
);
3113 int call_size
= es
->call_stmt_size
;
3114 int call_time
= es
->call_stmt_time
;
3117 && estimate_edge_devirt_benefit (e
, &call_size
, &call_time
,
3118 known_vals
, known_contexts
, known_aggs
)
3119 && hints
&& e
->maybe_hot_p ())
3120 *hints
|= INLINE_HINT_indirect_call
;
3121 cur_size
= call_size
* INLINE_SIZE_SCALE
;
3124 *min_size
+= cur_size
;
3125 *time
+= apply_probability ((gcov_type
) call_time
, prob
)
3126 * e
->frequency
* (INLINE_TIME_SCALE
/ CGRAPH_FREQ_BASE
);
3127 if (*time
> MAX_TIME
* INLINE_TIME_SCALE
)
3128 *time
= MAX_TIME
* INLINE_TIME_SCALE
;
3133 /* Increase SIZE, MIN_SIZE and TIME for size and time needed to handle all
3134 calls in NODE. POSSIBLE_TRUTHS, KNOWN_VALS, KNOWN_AGGS and KNOWN_CONTEXTS
3135 describe context of the call site. */
3138 estimate_calls_size_and_time (struct cgraph_node
*node
, int *size
,
3139 int *min_size
, int *time
,
3140 inline_hints
*hints
,
3141 clause_t possible_truths
,
3142 vec
<tree
> known_vals
,
3143 vec
<ipa_polymorphic_call_context
> known_contexts
,
3144 vec
<ipa_agg_jump_function_p
> known_aggs
)
3146 struct cgraph_edge
*e
;
3147 for (e
= node
->callees
; e
; e
= e
->next_callee
)
3149 if (inline_edge_summary_vec
.length () <= (unsigned) e
->uid
)
3152 struct inline_edge_summary
*es
= inline_edge_summary (e
);
3154 /* Do not care about zero sized builtins. */
3155 if (e
->inline_failed
&& !es
->call_stmt_size
)
3157 gcc_checking_assert (!es
->call_stmt_time
);
3161 || evaluate_predicate (es
->predicate
, possible_truths
))
3163 if (e
->inline_failed
)
3165 /* Predicates of calls shall not use NOT_CHANGED codes,
3166 sowe do not need to compute probabilities. */
3167 estimate_edge_size_and_time (e
, size
,
3168 es
->predicate
? NULL
: min_size
,
3169 time
, REG_BR_PROB_BASE
,
3170 known_vals
, known_contexts
,
3174 estimate_calls_size_and_time (e
->callee
, size
, min_size
, time
,
3177 known_vals
, known_contexts
,
3181 for (e
= node
->indirect_calls
; e
; e
= e
->next_callee
)
3183 if (inline_edge_summary_vec
.length () <= (unsigned) e
->uid
)
3186 struct inline_edge_summary
*es
= inline_edge_summary (e
);
3188 || evaluate_predicate (es
->predicate
, possible_truths
))
3189 estimate_edge_size_and_time (e
, size
,
3190 es
->predicate
? NULL
: min_size
,
3191 time
, REG_BR_PROB_BASE
,
3192 known_vals
, known_contexts
, known_aggs
,
3198 /* Estimate size and time needed to execute NODE assuming
3199 POSSIBLE_TRUTHS clause, and KNOWN_VALS, KNOWN_AGGS and KNOWN_CONTEXTS
3200 information about NODE's arguments. If non-NULL use also probability
3201 information present in INLINE_PARAM_SUMMARY vector.
3202 Additionally detemine hints determined by the context. Finally compute
3203 minimal size needed for the call that is independent on the call context and
3204 can be used for fast estimates. Return the values in RET_SIZE,
3205 RET_MIN_SIZE, RET_TIME and RET_HINTS. */
3208 estimate_node_size_and_time (struct cgraph_node
*node
,
3209 clause_t possible_truths
,
3210 vec
<tree
> known_vals
,
3211 vec
<ipa_polymorphic_call_context
> known_contexts
,
3212 vec
<ipa_agg_jump_function_p
> known_aggs
,
3213 int *ret_size
, int *ret_min_size
, int *ret_time
,
3214 inline_hints
*ret_hints
,
3215 vec
<inline_param_summary
>
3216 inline_param_summary
)
3218 struct inline_summary
*info
= inline_summaries
->get (node
);
3223 inline_hints hints
= 0;
3226 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3229 fprintf (dump_file
, " Estimating body: %s/%i\n"
3230 " Known to be false: ", node
->name (),
3233 for (i
= predicate_not_inlined_condition
;
3234 i
< (predicate_first_dynamic_condition
3235 + (int) vec_safe_length (info
->conds
)); i
++)
3236 if (!(possible_truths
& (1 << i
)))
3239 fprintf (dump_file
, ", ");
3241 dump_condition (dump_file
, info
->conds
, i
);
3245 for (i
= 0; vec_safe_iterate (info
->entry
, i
, &e
); i
++)
3246 if (evaluate_predicate (&e
->predicate
, possible_truths
))
3249 gcc_checking_assert (e
->time
>= 0);
3250 gcc_checking_assert (time
>= 0);
3251 if (!inline_param_summary
.exists ())
3255 int prob
= predicate_probability (info
->conds
,
3258 inline_param_summary
);
3259 gcc_checking_assert (prob
>= 0);
3260 gcc_checking_assert (prob
<= REG_BR_PROB_BASE
);
3261 time
+= apply_probability ((gcov_type
) e
->time
, prob
);
3263 if (time
> MAX_TIME
* INLINE_TIME_SCALE
)
3264 time
= MAX_TIME
* INLINE_TIME_SCALE
;
3265 gcc_checking_assert (time
>= 0);
3268 gcc_checking_assert (true_predicate_p (&(*info
->entry
)[0].predicate
));
3269 min_size
= (*info
->entry
)[0].size
;
3270 gcc_checking_assert (size
>= 0);
3271 gcc_checking_assert (time
>= 0);
3273 if (info
->loop_iterations
3274 && !evaluate_predicate (info
->loop_iterations
, possible_truths
))
3275 hints
|= INLINE_HINT_loop_iterations
;
3276 if (info
->loop_stride
3277 && !evaluate_predicate (info
->loop_stride
, possible_truths
))
3278 hints
|= INLINE_HINT_loop_stride
;
3279 if (info
->array_index
3280 && !evaluate_predicate (info
->array_index
, possible_truths
))
3281 hints
|= INLINE_HINT_array_index
;
3283 hints
|= INLINE_HINT_in_scc
;
3284 if (DECL_DECLARED_INLINE_P (node
->decl
))
3285 hints
|= INLINE_HINT_declared_inline
;
3287 estimate_calls_size_and_time (node
, &size
, &min_size
, &time
, &hints
, possible_truths
,
3288 known_vals
, known_contexts
, known_aggs
);
3289 gcc_checking_assert (size
>= 0);
3290 gcc_checking_assert (time
>= 0);
3291 time
= RDIV (time
, INLINE_TIME_SCALE
);
3292 size
= RDIV (size
, INLINE_SIZE_SCALE
);
3293 min_size
= RDIV (min_size
, INLINE_SIZE_SCALE
);
3295 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3296 fprintf (dump_file
, "\n size:%i time:%i\n", (int) size
, (int) time
);
3302 *ret_min_size
= min_size
;
3309 /* Estimate size and time needed to execute callee of EDGE assuming that
3310 parameters known to be constant at caller of EDGE are propagated.
3311 KNOWN_VALS and KNOWN_CONTEXTS are vectors of assumed known constant values
3312 and types for parameters. */
3315 estimate_ipcp_clone_size_and_time (struct cgraph_node
*node
,
3316 vec
<tree
> known_vals
,
3317 vec
<ipa_polymorphic_call_context
>
3319 vec
<ipa_agg_jump_function_p
> known_aggs
,
3320 int *ret_size
, int *ret_time
,
3321 inline_hints
*hints
)
3325 clause
= evaluate_conditions_for_known_args (node
, false, known_vals
,
3327 estimate_node_size_and_time (node
, clause
, known_vals
, known_contexts
,
3328 known_aggs
, ret_size
, NULL
, ret_time
, hints
, vNULL
);
3331 /* Translate all conditions from callee representation into caller
3332 representation and symbolically evaluate predicate P into new predicate.
3334 INFO is inline_summary of function we are adding predicate into, CALLEE_INFO
3335 is summary of function predicate P is from. OPERAND_MAP is array giving
3336 callee formal IDs the caller formal IDs. POSSSIBLE_TRUTHS is clausule of all
3337 callee conditions that may be true in caller context. TOPLEV_PREDICATE is
3338 predicate under which callee is executed. OFFSET_MAP is an array of of
3339 offsets that need to be added to conditions, negative offset means that
3340 conditions relying on values passed by reference have to be discarded
3341 because they might not be preserved (and should be considered offset zero
3342 for other purposes). */
3344 static struct predicate
3345 remap_predicate (struct inline_summary
*info
,
3346 struct inline_summary
*callee_info
,
3347 struct predicate
*p
,
3348 vec
<int> operand_map
,
3349 vec
<int> offset_map
,
3350 clause_t possible_truths
, struct predicate
*toplev_predicate
)
3353 struct predicate out
= true_predicate ();
3355 /* True predicate is easy. */
3356 if (true_predicate_p (p
))
3357 return *toplev_predicate
;
3358 for (i
= 0; p
->clause
[i
]; i
++)
3360 clause_t clause
= p
->clause
[i
];
3362 struct predicate clause_predicate
= false_predicate ();
3364 gcc_assert (i
< MAX_CLAUSES
);
3366 for (cond
= 0; cond
< NUM_CONDITIONS
; cond
++)
3367 /* Do we have condition we can't disprove? */
3368 if (clause
& possible_truths
& (1 << cond
))
3370 struct predicate cond_predicate
;
3371 /* Work out if the condition can translate to predicate in the
3372 inlined function. */
3373 if (cond
>= predicate_first_dynamic_condition
)
3375 struct condition
*c
;
3377 c
= &(*callee_info
->conds
)[cond
3379 predicate_first_dynamic_condition
];
3380 /* See if we can remap condition operand to caller's operand.
3381 Otherwise give up. */
3382 if (!operand_map
.exists ()
3383 || (int) operand_map
.length () <= c
->operand_num
3384 || operand_map
[c
->operand_num
] == -1
3385 /* TODO: For non-aggregate conditions, adding an offset is
3386 basically an arithmetic jump function processing which
3387 we should support in future. */
3388 || ((!c
->agg_contents
|| !c
->by_ref
)
3389 && offset_map
[c
->operand_num
] > 0)
3390 || (c
->agg_contents
&& c
->by_ref
3391 && offset_map
[c
->operand_num
] < 0))
3392 cond_predicate
= true_predicate ();
3395 struct agg_position_info ap
;
3396 HOST_WIDE_INT offset_delta
= offset_map
[c
->operand_num
];
3397 if (offset_delta
< 0)
3399 gcc_checking_assert (!c
->agg_contents
|| !c
->by_ref
);
3402 gcc_assert (!c
->agg_contents
3403 || c
->by_ref
|| offset_delta
== 0);
3404 ap
.offset
= c
->offset
+ offset_delta
;
3405 ap
.agg_contents
= c
->agg_contents
;
3406 ap
.by_ref
= c
->by_ref
;
3407 cond_predicate
= add_condition (info
,
3408 operand_map
[c
->operand_num
],
3409 &ap
, c
->code
, c
->val
);
3412 /* Fixed conditions remains same, construct single
3413 condition predicate. */
3416 cond_predicate
.clause
[0] = 1 << cond
;
3417 cond_predicate
.clause
[1] = 0;
3419 clause_predicate
= or_predicates (info
->conds
, &clause_predicate
,
3422 out
= and_predicates (info
->conds
, &out
, &clause_predicate
);
3424 return and_predicates (info
->conds
, &out
, toplev_predicate
);
3428 /* Update summary information of inline clones after inlining.
3429 Compute peak stack usage. */
3432 inline_update_callee_summaries (struct cgraph_node
*node
, int depth
)
3434 struct cgraph_edge
*e
;
3435 struct inline_summary
*callee_info
= inline_summaries
->get (node
);
3436 struct inline_summary
*caller_info
= inline_summaries
->get (node
->callers
->caller
);
3439 callee_info
->stack_frame_offset
3440 = caller_info
->stack_frame_offset
3441 + caller_info
->estimated_self_stack_size
;
3442 peak
= callee_info
->stack_frame_offset
3443 + callee_info
->estimated_self_stack_size
;
3444 if (inline_summaries
->get (node
->global
.inlined_to
)->estimated_stack_size
< peak
)
3445 inline_summaries
->get (node
->global
.inlined_to
)->estimated_stack_size
= peak
;
3446 ipa_propagate_frequency (node
);
3447 for (e
= node
->callees
; e
; e
= e
->next_callee
)
3449 if (!e
->inline_failed
)
3450 inline_update_callee_summaries (e
->callee
, depth
);
3451 inline_edge_summary (e
)->loop_depth
+= depth
;
3453 for (e
= node
->indirect_calls
; e
; e
= e
->next_callee
)
3454 inline_edge_summary (e
)->loop_depth
+= depth
;
3457 /* Update change_prob of EDGE after INLINED_EDGE has been inlined.
3458 When functoin A is inlined in B and A calls C with parameter that
3459 changes with probability PROB1 and C is known to be passthroug
3460 of argument if B that change with probability PROB2, the probability
3461 of change is now PROB1*PROB2. */
3464 remap_edge_change_prob (struct cgraph_edge
*inlined_edge
,
3465 struct cgraph_edge
*edge
)
3467 if (ipa_node_params_sum
)
3470 struct ipa_edge_args
*args
= IPA_EDGE_REF (edge
);
3471 struct inline_edge_summary
*es
= inline_edge_summary (edge
);
3472 struct inline_edge_summary
*inlined_es
3473 = inline_edge_summary (inlined_edge
);
3475 for (i
= 0; i
< ipa_get_cs_argument_count (args
); i
++)
3477 struct ipa_jump_func
*jfunc
= ipa_get_ith_jump_func (args
, i
);
3478 if (jfunc
->type
== IPA_JF_PASS_THROUGH
3479 && (ipa_get_jf_pass_through_formal_id (jfunc
)
3480 < (int) inlined_es
->param
.length ()))
3482 int jf_formal_id
= ipa_get_jf_pass_through_formal_id (jfunc
);
3483 int prob1
= es
->param
[i
].change_prob
;
3484 int prob2
= inlined_es
->param
[jf_formal_id
].change_prob
;
3485 int prob
= combine_probabilities (prob1
, prob2
);
3487 if (prob1
&& prob2
&& !prob
)
3490 es
->param
[i
].change_prob
= prob
;
3496 /* Update edge summaries of NODE after INLINED_EDGE has been inlined.
3498 Remap predicates of callees of NODE. Rest of arguments match
3501 Also update change probabilities. */
3504 remap_edge_summaries (struct cgraph_edge
*inlined_edge
,
3505 struct cgraph_node
*node
,
3506 struct inline_summary
*info
,
3507 struct inline_summary
*callee_info
,
3508 vec
<int> operand_map
,
3509 vec
<int> offset_map
,
3510 clause_t possible_truths
,
3511 struct predicate
*toplev_predicate
)
3513 struct cgraph_edge
*e
, *next
;
3514 for (e
= node
->callees
; e
; e
= next
)
3516 struct inline_edge_summary
*es
= inline_edge_summary (e
);
3518 next
= e
->next_callee
;
3520 if (e
->inline_failed
)
3522 remap_edge_change_prob (inlined_edge
, e
);
3526 p
= remap_predicate (info
, callee_info
,
3527 es
->predicate
, operand_map
, offset_map
,
3528 possible_truths
, toplev_predicate
);
3529 edge_set_predicate (e
, &p
);
3532 edge_set_predicate (e
, toplev_predicate
);
3535 remap_edge_summaries (inlined_edge
, e
->callee
, info
, callee_info
,
3536 operand_map
, offset_map
, possible_truths
,
3539 for (e
= node
->indirect_calls
; e
; e
= next
)
3541 struct inline_edge_summary
*es
= inline_edge_summary (e
);
3543 next
= e
->next_callee
;
3545 remap_edge_change_prob (inlined_edge
, e
);
3548 p
= remap_predicate (info
, callee_info
,
3549 es
->predicate
, operand_map
, offset_map
,
3550 possible_truths
, toplev_predicate
);
3551 edge_set_predicate (e
, &p
);
3554 edge_set_predicate (e
, toplev_predicate
);
3558 /* Same as remap_predicate, but set result into hint *HINT. */
3561 remap_hint_predicate (struct inline_summary
*info
,
3562 struct inline_summary
*callee_info
,
3563 struct predicate
**hint
,
3564 vec
<int> operand_map
,
3565 vec
<int> offset_map
,
3566 clause_t possible_truths
,
3567 struct predicate
*toplev_predicate
)
3573 p
= remap_predicate (info
, callee_info
,
3575 operand_map
, offset_map
,
3576 possible_truths
, toplev_predicate
);
3577 if (!false_predicate_p (&p
) && !true_predicate_p (&p
))
3580 set_hint_predicate (hint
, p
);
3582 **hint
= and_predicates (info
->conds
, *hint
, &p
);
3586 /* We inlined EDGE. Update summary of the function we inlined into. */
3589 inline_merge_summary (struct cgraph_edge
*edge
)
3591 struct inline_summary
*callee_info
= inline_summaries
->get (edge
->callee
);
3592 struct cgraph_node
*to
= (edge
->caller
->global
.inlined_to
3593 ? edge
->caller
->global
.inlined_to
: edge
->caller
);
3594 struct inline_summary
*info
= inline_summaries
->get (to
);
3595 clause_t clause
= 0; /* not_inline is known to be false. */
3597 vec
<int> operand_map
= vNULL
;
3598 vec
<int> offset_map
= vNULL
;
3600 struct predicate toplev_predicate
;
3601 struct predicate true_p
= true_predicate ();
3602 struct inline_edge_summary
*es
= inline_edge_summary (edge
);
3605 toplev_predicate
= *es
->predicate
;
3607 toplev_predicate
= true_predicate ();
3609 info
->fp_expressions
|= callee_info
->fp_expressions
;
3611 if (callee_info
->conds
)
3612 evaluate_properties_for_edge (edge
, true, &clause
, NULL
, NULL
, NULL
);
3613 if (ipa_node_params_sum
&& callee_info
->conds
)
3615 struct ipa_edge_args
*args
= IPA_EDGE_REF (edge
);
3616 int count
= ipa_get_cs_argument_count (args
);
3621 operand_map
.safe_grow_cleared (count
);
3622 offset_map
.safe_grow_cleared (count
);
3624 for (i
= 0; i
< count
; i
++)
3626 struct ipa_jump_func
*jfunc
= ipa_get_ith_jump_func (args
, i
);
3629 /* TODO: handle non-NOPs when merging. */
3630 if (jfunc
->type
== IPA_JF_PASS_THROUGH
)
3632 if (ipa_get_jf_pass_through_operation (jfunc
) == NOP_EXPR
)
3633 map
= ipa_get_jf_pass_through_formal_id (jfunc
);
3634 if (!ipa_get_jf_pass_through_agg_preserved (jfunc
))
3637 else if (jfunc
->type
== IPA_JF_ANCESTOR
)
3639 HOST_WIDE_INT offset
= ipa_get_jf_ancestor_offset (jfunc
);
3640 if (offset
>= 0 && offset
< INT_MAX
)
3642 map
= ipa_get_jf_ancestor_formal_id (jfunc
);
3643 if (!ipa_get_jf_ancestor_agg_preserved (jfunc
))
3645 offset_map
[i
] = offset
;
3648 operand_map
[i
] = map
;
3649 gcc_assert (map
< ipa_get_param_count (IPA_NODE_REF (to
)));
3652 for (i
= 0; vec_safe_iterate (callee_info
->entry
, i
, &e
); i
++)
3654 struct predicate p
= remap_predicate (info
, callee_info
,
3655 &e
->predicate
, operand_map
,
3658 if (!false_predicate_p (&p
))
3660 gcov_type add_time
= ((gcov_type
) e
->time
* edge
->frequency
3661 + CGRAPH_FREQ_BASE
/ 2) / CGRAPH_FREQ_BASE
;
3662 int prob
= predicate_probability (callee_info
->conds
,
3665 add_time
= apply_probability ((gcov_type
) add_time
, prob
);
3666 if (add_time
> MAX_TIME
* INLINE_TIME_SCALE
)
3667 add_time
= MAX_TIME
* INLINE_TIME_SCALE
;
3668 if (prob
!= REG_BR_PROB_BASE
3669 && dump_file
&& (dump_flags
& TDF_DETAILS
))
3671 fprintf (dump_file
, "\t\tScaling time by probability:%f\n",
3672 (double) prob
/ REG_BR_PROB_BASE
);
3674 account_size_time (info
, e
->size
, add_time
, &p
);
3677 remap_edge_summaries (edge
, edge
->callee
, info
, callee_info
, operand_map
,
3678 offset_map
, clause
, &toplev_predicate
);
3679 remap_hint_predicate (info
, callee_info
,
3680 &callee_info
->loop_iterations
,
3681 operand_map
, offset_map
, clause
, &toplev_predicate
);
3682 remap_hint_predicate (info
, callee_info
,
3683 &callee_info
->loop_stride
,
3684 operand_map
, offset_map
, clause
, &toplev_predicate
);
3685 remap_hint_predicate (info
, callee_info
,
3686 &callee_info
->array_index
,
3687 operand_map
, offset_map
, clause
, &toplev_predicate
);
3689 inline_update_callee_summaries (edge
->callee
,
3690 inline_edge_summary (edge
)->loop_depth
);
3692 /* We do not maintain predicates of inlined edges, free it. */
3693 edge_set_predicate (edge
, &true_p
);
3694 /* Similarly remove param summaries. */
3695 es
->param
.release ();
3696 operand_map
.release ();
3697 offset_map
.release ();
3700 /* For performance reasons inline_merge_summary is not updating overall size
3701 and time. Recompute it. */
3704 inline_update_overall_summary (struct cgraph_node
*node
)
3706 struct inline_summary
*info
= inline_summaries
->get (node
);
3712 for (i
= 0; vec_safe_iterate (info
->entry
, i
, &e
); i
++)
3714 info
->size
+= e
->size
, info
->time
+= e
->time
;
3715 if (info
->time
> MAX_TIME
* INLINE_TIME_SCALE
)
3716 info
->time
= MAX_TIME
* INLINE_TIME_SCALE
;
3718 estimate_calls_size_and_time (node
, &info
->size
, &info
->min_size
,
3720 ~(clause_t
) (1 << predicate_false_condition
),
3721 vNULL
, vNULL
, vNULL
);
3722 info
->time
= (info
->time
+ INLINE_TIME_SCALE
/ 2) / INLINE_TIME_SCALE
;
3723 info
->size
= (info
->size
+ INLINE_SIZE_SCALE
/ 2) / INLINE_SIZE_SCALE
;
3726 /* Return hints derrived from EDGE. */
3728 simple_edge_hints (struct cgraph_edge
*edge
)
3731 struct cgraph_node
*to
= (edge
->caller
->global
.inlined_to
3732 ? edge
->caller
->global
.inlined_to
: edge
->caller
);
3733 struct cgraph_node
*callee
= edge
->callee
->ultimate_alias_target ();
3734 if (inline_summaries
->get (to
)->scc_no
3735 && inline_summaries
->get (to
)->scc_no
3736 == inline_summaries
->get (callee
)->scc_no
3737 && !edge
->recursive_p ())
3738 hints
|= INLINE_HINT_same_scc
;
3740 if (callee
->lto_file_data
&& edge
->caller
->lto_file_data
3741 && edge
->caller
->lto_file_data
!= callee
->lto_file_data
3742 && !callee
->merged_comdat
&& !callee
->icf_merged
)
3743 hints
|= INLINE_HINT_cross_module
;
3748 /* Estimate the time cost for the caller when inlining EDGE.
3749 Only to be called via estimate_edge_time, that handles the
3752 When caching, also update the cache entry. Compute both time and
3753 size, since we always need both metrics eventually. */
3756 do_estimate_edge_time (struct cgraph_edge
*edge
)
3761 struct cgraph_node
*callee
;
3763 vec
<tree
> known_vals
;
3764 vec
<ipa_polymorphic_call_context
> known_contexts
;
3765 vec
<ipa_agg_jump_function_p
> known_aggs
;
3766 struct inline_edge_summary
*es
= inline_edge_summary (edge
);
3769 callee
= edge
->callee
->ultimate_alias_target ();
3771 gcc_checking_assert (edge
->inline_failed
);
3772 evaluate_properties_for_edge (edge
, true,
3773 &clause
, &known_vals
, &known_contexts
,
3775 estimate_node_size_and_time (callee
, clause
, known_vals
, known_contexts
,
3776 known_aggs
, &size
, &min_size
, &time
, &hints
, es
->param
);
3778 /* When we have profile feedback, we can quite safely identify hot
3779 edges and for those we disable size limits. Don't do that when
3780 probability that caller will call the callee is low however, since it
3781 may hurt optimization of the caller's hot path. */
3782 if (edge
->count
&& edge
->maybe_hot_p ()
3784 > (edge
->caller
->global
.inlined_to
3785 ? edge
->caller
->global
.inlined_to
->count
: edge
->caller
->count
)))
3786 hints
|= INLINE_HINT_known_hot
;
3788 known_vals
.release ();
3789 known_contexts
.release ();
3790 known_aggs
.release ();
3791 gcc_checking_assert (size
>= 0);
3792 gcc_checking_assert (time
>= 0);
3794 /* When caching, update the cache entry. */
3795 if (edge_growth_cache
.exists ())
3797 inline_summaries
->get (edge
->callee
)->min_size
= min_size
;
3798 if ((int) edge_growth_cache
.length () <= edge
->uid
)
3799 edge_growth_cache
.safe_grow_cleared (symtab
->edges_max_uid
);
3800 edge_growth_cache
[edge
->uid
].time
= time
+ (time
>= 0);
3802 edge_growth_cache
[edge
->uid
].size
= size
+ (size
>= 0);
3803 hints
|= simple_edge_hints (edge
);
3804 edge_growth_cache
[edge
->uid
].hints
= hints
+ 1;
3810 /* Return estimated callee growth after inlining EDGE.
3811 Only to be called via estimate_edge_size. */
3814 do_estimate_edge_size (struct cgraph_edge
*edge
)
3817 struct cgraph_node
*callee
;
3819 vec
<tree
> known_vals
;
3820 vec
<ipa_polymorphic_call_context
> known_contexts
;
3821 vec
<ipa_agg_jump_function_p
> known_aggs
;
3823 /* When we do caching, use do_estimate_edge_time to populate the entry. */
3825 if (edge_growth_cache
.exists ())
3827 do_estimate_edge_time (edge
);
3828 size
= edge_growth_cache
[edge
->uid
].size
;
3829 gcc_checking_assert (size
);
3830 return size
- (size
> 0);
3833 callee
= edge
->callee
->ultimate_alias_target ();
3835 /* Early inliner runs without caching, go ahead and do the dirty work. */
3836 gcc_checking_assert (edge
->inline_failed
);
3837 evaluate_properties_for_edge (edge
, true,
3838 &clause
, &known_vals
, &known_contexts
,
3840 estimate_node_size_and_time (callee
, clause
, known_vals
, known_contexts
,
3841 known_aggs
, &size
, NULL
, NULL
, NULL
, vNULL
);
3842 known_vals
.release ();
3843 known_contexts
.release ();
3844 known_aggs
.release ();
3849 /* Estimate the growth of the caller when inlining EDGE.
3850 Only to be called via estimate_edge_size. */
3853 do_estimate_edge_hints (struct cgraph_edge
*edge
)
3856 struct cgraph_node
*callee
;
3858 vec
<tree
> known_vals
;
3859 vec
<ipa_polymorphic_call_context
> known_contexts
;
3860 vec
<ipa_agg_jump_function_p
> known_aggs
;
3862 /* When we do caching, use do_estimate_edge_time to populate the entry. */
3864 if (edge_growth_cache
.exists ())
3866 do_estimate_edge_time (edge
);
3867 hints
= edge_growth_cache
[edge
->uid
].hints
;
3868 gcc_checking_assert (hints
);
3872 callee
= edge
->callee
->ultimate_alias_target ();
3874 /* Early inliner runs without caching, go ahead and do the dirty work. */
3875 gcc_checking_assert (edge
->inline_failed
);
3876 evaluate_properties_for_edge (edge
, true,
3877 &clause
, &known_vals
, &known_contexts
,
3879 estimate_node_size_and_time (callee
, clause
, known_vals
, known_contexts
,
3880 known_aggs
, NULL
, NULL
, NULL
, &hints
, vNULL
);
3881 known_vals
.release ();
3882 known_contexts
.release ();
3883 known_aggs
.release ();
3884 hints
|= simple_edge_hints (edge
);
3889 /* Estimate self time of the function NODE after inlining EDGE. */
3892 estimate_time_after_inlining (struct cgraph_node
*node
,
3893 struct cgraph_edge
*edge
)
3895 struct inline_edge_summary
*es
= inline_edge_summary (edge
);
3896 if (!es
->predicate
|| !false_predicate_p (es
->predicate
))
3899 inline_summaries
->get (node
)->time
+ estimate_edge_time (edge
);
3902 if (time
> MAX_TIME
)
3906 return inline_summaries
->get (node
)->time
;
3910 /* Estimate the size of NODE after inlining EDGE which should be an
3911 edge to either NODE or a call inlined into NODE. */
3914 estimate_size_after_inlining (struct cgraph_node
*node
,
3915 struct cgraph_edge
*edge
)
3917 struct inline_edge_summary
*es
= inline_edge_summary (edge
);
3918 if (!es
->predicate
|| !false_predicate_p (es
->predicate
))
3920 int size
= inline_summaries
->get (node
)->size
+ estimate_edge_growth (edge
);
3921 gcc_assert (size
>= 0);
3924 return inline_summaries
->get (node
)->size
;
3930 struct cgraph_node
*node
;
3931 bool self_recursive
;
3937 /* Worker for do_estimate_growth. Collect growth for all callers. */
3940 do_estimate_growth_1 (struct cgraph_node
*node
, void *data
)
3942 struct cgraph_edge
*e
;
3943 struct growth_data
*d
= (struct growth_data
*) data
;
3945 for (e
= node
->callers
; e
; e
= e
->next_caller
)
3947 gcc_checking_assert (e
->inline_failed
);
3949 if (cgraph_inline_failed_type (e
->inline_failed
) == CIF_FINAL_ERROR
)
3951 d
->uninlinable
= true;
3955 if (e
->recursive_p ())
3957 d
->self_recursive
= true;
3960 d
->growth
+= estimate_edge_growth (e
);
3966 /* Estimate the growth caused by inlining NODE into all callees. */
3969 estimate_growth (struct cgraph_node
*node
)
3971 struct growth_data d
= { node
, false, false, 0 };
3972 struct inline_summary
*info
= inline_summaries
->get (node
);
3974 node
->call_for_symbol_and_aliases (do_estimate_growth_1
, &d
, true);
3976 /* For self recursive functions the growth estimation really should be
3977 infinity. We don't want to return very large values because the growth
3978 plays various roles in badness computation fractions. Be sure to not
3979 return zero or negative growths. */
3980 if (d
.self_recursive
)
3981 d
.growth
= d
.growth
< info
->size
? info
->size
: d
.growth
;
3982 else if (DECL_EXTERNAL (node
->decl
) || d
.uninlinable
)
3986 if (node
->will_be_removed_from_program_if_no_direct_calls_p ())
3987 d
.growth
-= info
->size
;
3988 /* COMDAT functions are very often not shared across multiple units
3989 since they come from various template instantiations.
3990 Take this into account. */
3991 else if (DECL_COMDAT (node
->decl
)
3992 && node
->can_remove_if_no_direct_calls_p ())
3993 d
.growth
-= (info
->size
3994 * (100 - PARAM_VALUE (PARAM_COMDAT_SHARING_PROBABILITY
))
4001 /* Verify if there are fewer than MAX_CALLERS. */
4004 check_callers (cgraph_node
*node
, int *max_callers
)
4008 if (!node
->can_remove_if_no_direct_calls_and_refs_p ())
4011 for (cgraph_edge
*e
= node
->callers
; e
; e
= e
->next_caller
)
4015 || cgraph_inline_failed_type (e
->inline_failed
) == CIF_FINAL_ERROR
)
4019 FOR_EACH_ALIAS (node
, ref
)
4020 if (check_callers (dyn_cast
<cgraph_node
*> (ref
->referring
), max_callers
))
4027 /* Make cheap estimation if growth of NODE is likely positive knowing
4028 EDGE_GROWTH of one particular edge.
4029 We assume that most of other edges will have similar growth
4030 and skip computation if there are too many callers. */
4033 growth_likely_positive (struct cgraph_node
*node
,
4037 struct cgraph_edge
*e
;
4038 gcc_checking_assert (edge_growth
> 0);
4040 /* First quickly check if NODE is removable at all. */
4041 if (DECL_EXTERNAL (node
->decl
))
4043 if (!node
->can_remove_if_no_direct_calls_and_refs_p ()
4044 || node
->address_taken
)
4047 max_callers
= inline_summaries
->get (node
)->size
* 4 / edge_growth
+ 2;
4049 for (e
= node
->callers
; e
; e
= e
->next_caller
)
4053 || cgraph_inline_failed_type (e
->inline_failed
) == CIF_FINAL_ERROR
)
4058 FOR_EACH_ALIAS (node
, ref
)
4059 if (check_callers (dyn_cast
<cgraph_node
*> (ref
->referring
), &max_callers
))
4062 /* Unlike for functions called once, we play unsafe with
4063 COMDATs. We can allow that since we know functions
4064 in consideration are small (and thus risk is small) and
4065 moreover grow estimates already accounts that COMDAT
4066 functions may or may not disappear when eliminated from
4067 current unit. With good probability making aggressive
4068 choice in all units is going to make overall program
4070 if (DECL_COMDAT (node
->decl
))
4072 if (!node
->can_remove_if_no_direct_calls_p ())
4075 else if (!node
->will_be_removed_from_program_if_no_direct_calls_p ())
4078 return estimate_growth (node
) > 0;
4082 /* This function performs intraprocedural analysis in NODE that is required to
4083 inline indirect calls. */
4086 inline_indirect_intraprocedural_analysis (struct cgraph_node
*node
)
4088 ipa_analyze_node (node
);
4089 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
4091 ipa_print_node_params (dump_file
, node
);
4092 ipa_print_node_jump_functions (dump_file
, node
);
4097 /* Note function body size. */
4100 inline_analyze_function (struct cgraph_node
*node
)
4102 push_cfun (DECL_STRUCT_FUNCTION (node
->decl
));
4105 fprintf (dump_file
, "\nAnalyzing function: %s/%u\n",
4106 node
->name (), node
->order
);
4107 if (opt_for_fn (node
->decl
, optimize
) && !node
->thunk
.thunk_p
)
4108 inline_indirect_intraprocedural_analysis (node
);
4109 compute_inline_parameters (node
, false);
4112 struct cgraph_edge
*e
;
4113 for (e
= node
->callees
; e
; e
= e
->next_callee
)
4114 e
->inline_failed
= CIF_FUNCTION_NOT_OPTIMIZED
;
4115 for (e
= node
->indirect_calls
; e
; e
= e
->next_callee
)
4116 e
->inline_failed
= CIF_FUNCTION_NOT_OPTIMIZED
;
4123 /* Called when new function is inserted to callgraph late. */
4126 inline_summary_t::insert (struct cgraph_node
*node
, inline_summary
*)
4128 inline_analyze_function (node
);
4131 /* Note function body size. */
4134 inline_generate_summary (void)
4136 struct cgraph_node
*node
;
4138 FOR_EACH_DEFINED_FUNCTION (node
)
4139 if (DECL_STRUCT_FUNCTION (node
->decl
))
4140 node
->local
.versionable
= tree_versionable_function_p (node
->decl
);
4142 /* When not optimizing, do not bother to analyze. Inlining is still done
4143 because edge redirection needs to happen there. */
4144 if (!optimize
&& !flag_generate_lto
&& !flag_generate_offload
&& !flag_wpa
)
4147 if (!inline_summaries
)
4148 inline_summaries
= (inline_summary_t
*) inline_summary_t::create_ggc (symtab
);
4150 inline_summaries
->enable_insertion_hook ();
4152 ipa_register_cgraph_hooks ();
4153 inline_free_summary ();
4155 FOR_EACH_DEFINED_FUNCTION (node
)
4157 inline_analyze_function (node
);
4161 /* Read predicate from IB. */
4163 static struct predicate
4164 read_predicate (struct lto_input_block
*ib
)
4166 struct predicate out
;
4172 gcc_assert (k
<= MAX_CLAUSES
);
4173 clause
= out
.clause
[k
++] = streamer_read_uhwi (ib
);
4177 /* Zero-initialize the remaining clauses in OUT. */
4178 while (k
<= MAX_CLAUSES
)
4179 out
.clause
[k
++] = 0;
4185 /* Write inline summary for edge E to OB. */
4188 read_inline_edge_summary (struct lto_input_block
*ib
, struct cgraph_edge
*e
)
4190 struct inline_edge_summary
*es
= inline_edge_summary (e
);
4194 es
->call_stmt_size
= streamer_read_uhwi (ib
);
4195 es
->call_stmt_time
= streamer_read_uhwi (ib
);
4196 es
->loop_depth
= streamer_read_uhwi (ib
);
4197 p
= read_predicate (ib
);
4198 edge_set_predicate (e
, &p
);
4199 length
= streamer_read_uhwi (ib
);
4202 es
->param
.safe_grow_cleared (length
);
4203 for (i
= 0; i
< length
; i
++)
4204 es
->param
[i
].change_prob
= streamer_read_uhwi (ib
);
4209 /* Stream in inline summaries from the section. */
4212 inline_read_section (struct lto_file_decl_data
*file_data
, const char *data
,
4215 const struct lto_function_header
*header
=
4216 (const struct lto_function_header
*) data
;
4217 const int cfg_offset
= sizeof (struct lto_function_header
);
4218 const int main_offset
= cfg_offset
+ header
->cfg_size
;
4219 const int string_offset
= main_offset
+ header
->main_size
;
4220 struct data_in
*data_in
;
4221 unsigned int i
, count2
, j
;
4222 unsigned int f_count
;
4224 lto_input_block
ib ((const char *) data
+ main_offset
, header
->main_size
,
4225 file_data
->mode_table
);
4228 lto_data_in_create (file_data
, (const char *) data
+ string_offset
,
4229 header
->string_size
, vNULL
);
4230 f_count
= streamer_read_uhwi (&ib
);
4231 for (i
= 0; i
< f_count
; i
++)
4234 struct cgraph_node
*node
;
4235 struct inline_summary
*info
;
4236 lto_symtab_encoder_t encoder
;
4237 struct bitpack_d bp
;
4238 struct cgraph_edge
*e
;
4241 index
= streamer_read_uhwi (&ib
);
4242 encoder
= file_data
->symtab_node_encoder
;
4243 node
= dyn_cast
<cgraph_node
*> (lto_symtab_encoder_deref (encoder
,
4245 info
= inline_summaries
->get (node
);
4247 info
->estimated_stack_size
4248 = info
->estimated_self_stack_size
= streamer_read_uhwi (&ib
);
4249 info
->size
= info
->self_size
= streamer_read_uhwi (&ib
);
4250 info
->time
= info
->self_time
= streamer_read_uhwi (&ib
);
4252 bp
= streamer_read_bitpack (&ib
);
4253 info
->inlinable
= bp_unpack_value (&bp
, 1);
4254 info
->contains_cilk_spawn
= bp_unpack_value (&bp
, 1);
4255 info
->fp_expressions
= bp_unpack_value (&bp
, 1);
4257 count2
= streamer_read_uhwi (&ib
);
4258 gcc_assert (!info
->conds
);
4259 for (j
= 0; j
< count2
; j
++)
4262 c
.operand_num
= streamer_read_uhwi (&ib
);
4263 c
.code
= (enum tree_code
) streamer_read_uhwi (&ib
);
4264 c
.val
= stream_read_tree (&ib
, data_in
);
4265 bp
= streamer_read_bitpack (&ib
);
4266 c
.agg_contents
= bp_unpack_value (&bp
, 1);
4267 c
.by_ref
= bp_unpack_value (&bp
, 1);
4269 c
.offset
= streamer_read_uhwi (&ib
);
4270 vec_safe_push (info
->conds
, c
);
4272 count2
= streamer_read_uhwi (&ib
);
4273 gcc_assert (!info
->entry
);
4274 for (j
= 0; j
< count2
; j
++)
4276 struct size_time_entry e
;
4278 e
.size
= streamer_read_uhwi (&ib
);
4279 e
.time
= streamer_read_uhwi (&ib
);
4280 e
.predicate
= read_predicate (&ib
);
4282 vec_safe_push (info
->entry
, e
);
4285 p
= read_predicate (&ib
);
4286 set_hint_predicate (&info
->loop_iterations
, p
);
4287 p
= read_predicate (&ib
);
4288 set_hint_predicate (&info
->loop_stride
, p
);
4289 p
= read_predicate (&ib
);
4290 set_hint_predicate (&info
->array_index
, p
);
4291 for (e
= node
->callees
; e
; e
= e
->next_callee
)
4292 read_inline_edge_summary (&ib
, e
);
4293 for (e
= node
->indirect_calls
; e
; e
= e
->next_callee
)
4294 read_inline_edge_summary (&ib
, e
);
4297 lto_free_section_data (file_data
, LTO_section_inline_summary
, NULL
, data
,
4299 lto_data_in_delete (data_in
);
4303 /* Read inline summary. Jump functions are shared among ipa-cp
4304 and inliner, so when ipa-cp is active, we don't need to write them
4308 inline_read_summary (void)
4310 struct lto_file_decl_data
**file_data_vec
= lto_get_file_decl_data ();
4311 struct lto_file_decl_data
*file_data
;
4314 inline_summary_alloc ();
4316 while ((file_data
= file_data_vec
[j
++]))
4319 const char *data
= lto_get_section_data (file_data
,
4320 LTO_section_inline_summary
,
4323 inline_read_section (file_data
, data
, len
);
4325 /* Fatal error here. We do not want to support compiling ltrans units
4326 with different version of compiler or different flags than the WPA
4327 unit, so this should never happen. */
4328 fatal_error (input_location
,
4329 "ipa inline summary is missing in input file");
4333 ipa_register_cgraph_hooks ();
4335 ipa_prop_read_jump_functions ();
4338 gcc_assert (inline_summaries
);
4339 inline_summaries
->enable_insertion_hook ();
4343 /* Write predicate P to OB. */
4346 write_predicate (struct output_block
*ob
, struct predicate
*p
)
4350 for (j
= 0; p
->clause
[j
]; j
++)
4352 gcc_assert (j
< MAX_CLAUSES
);
4353 streamer_write_uhwi (ob
, p
->clause
[j
]);
4355 streamer_write_uhwi (ob
, 0);
4359 /* Write inline summary for edge E to OB. */
4362 write_inline_edge_summary (struct output_block
*ob
, struct cgraph_edge
*e
)
4364 struct inline_edge_summary
*es
= inline_edge_summary (e
);
4367 streamer_write_uhwi (ob
, es
->call_stmt_size
);
4368 streamer_write_uhwi (ob
, es
->call_stmt_time
);
4369 streamer_write_uhwi (ob
, es
->loop_depth
);
4370 write_predicate (ob
, es
->predicate
);
4371 streamer_write_uhwi (ob
, es
->param
.length ());
4372 for (i
= 0; i
< (int) es
->param
.length (); i
++)
4373 streamer_write_uhwi (ob
, es
->param
[i
].change_prob
);
4377 /* Write inline summary for node in SET.
4378 Jump functions are shared among ipa-cp and inliner, so when ipa-cp is
4379 active, we don't need to write them twice. */
4382 inline_write_summary (void)
4384 struct cgraph_node
*node
;
4385 struct output_block
*ob
= create_output_block (LTO_section_inline_summary
);
4386 lto_symtab_encoder_t encoder
= ob
->decl_state
->symtab_node_encoder
;
4387 unsigned int count
= 0;
4390 for (i
= 0; i
< lto_symtab_encoder_size (encoder
); i
++)
4392 symtab_node
*snode
= lto_symtab_encoder_deref (encoder
, i
);
4393 cgraph_node
*cnode
= dyn_cast
<cgraph_node
*> (snode
);
4394 if (cnode
&& cnode
->definition
&& !cnode
->alias
)
4397 streamer_write_uhwi (ob
, count
);
4399 for (i
= 0; i
< lto_symtab_encoder_size (encoder
); i
++)
4401 symtab_node
*snode
= lto_symtab_encoder_deref (encoder
, i
);
4402 cgraph_node
*cnode
= dyn_cast
<cgraph_node
*> (snode
);
4403 if (cnode
&& (node
= cnode
)->definition
&& !node
->alias
)
4405 struct inline_summary
*info
= inline_summaries
->get (node
);
4406 struct bitpack_d bp
;
4407 struct cgraph_edge
*edge
;
4410 struct condition
*c
;
4412 streamer_write_uhwi (ob
,
4413 lto_symtab_encoder_encode (encoder
,
4416 streamer_write_hwi (ob
, info
->estimated_self_stack_size
);
4417 streamer_write_hwi (ob
, info
->self_size
);
4418 streamer_write_hwi (ob
, info
->self_time
);
4419 bp
= bitpack_create (ob
->main_stream
);
4420 bp_pack_value (&bp
, info
->inlinable
, 1);
4421 bp_pack_value (&bp
, info
->contains_cilk_spawn
, 1);
4422 bp_pack_value (&bp
, info
->fp_expressions
, 1);
4423 streamer_write_bitpack (&bp
);
4424 streamer_write_uhwi (ob
, vec_safe_length (info
->conds
));
4425 for (i
= 0; vec_safe_iterate (info
->conds
, i
, &c
); i
++)
4427 streamer_write_uhwi (ob
, c
->operand_num
);
4428 streamer_write_uhwi (ob
, c
->code
);
4429 stream_write_tree (ob
, c
->val
, true);
4430 bp
= bitpack_create (ob
->main_stream
);
4431 bp_pack_value (&bp
, c
->agg_contents
, 1);
4432 bp_pack_value (&bp
, c
->by_ref
, 1);
4433 streamer_write_bitpack (&bp
);
4434 if (c
->agg_contents
)
4435 streamer_write_uhwi (ob
, c
->offset
);
4437 streamer_write_uhwi (ob
, vec_safe_length (info
->entry
));
4438 for (i
= 0; vec_safe_iterate (info
->entry
, i
, &e
); i
++)
4440 streamer_write_uhwi (ob
, e
->size
);
4441 streamer_write_uhwi (ob
, e
->time
);
4442 write_predicate (ob
, &e
->predicate
);
4444 write_predicate (ob
, info
->loop_iterations
);
4445 write_predicate (ob
, info
->loop_stride
);
4446 write_predicate (ob
, info
->array_index
);
4447 for (edge
= node
->callees
; edge
; edge
= edge
->next_callee
)
4448 write_inline_edge_summary (ob
, edge
);
4449 for (edge
= node
->indirect_calls
; edge
; edge
= edge
->next_callee
)
4450 write_inline_edge_summary (ob
, edge
);
4453 streamer_write_char_stream (ob
->main_stream
, 0);
4454 produce_asm (ob
, NULL
);
4455 destroy_output_block (ob
);
4457 if (optimize
&& !flag_ipa_cp
)
4458 ipa_prop_write_jump_functions ();
4462 /* Release inline summary. */
4465 inline_free_summary (void)
4467 struct cgraph_node
*node
;
4468 if (edge_removal_hook_holder
)
4469 symtab
->remove_edge_removal_hook (edge_removal_hook_holder
);
4470 edge_removal_hook_holder
= NULL
;
4471 if (edge_duplication_hook_holder
)
4472 symtab
->remove_edge_duplication_hook (edge_duplication_hook_holder
);
4473 edge_duplication_hook_holder
= NULL
;
4474 if (!inline_edge_summary_vec
.exists ())
4476 FOR_EACH_DEFINED_FUNCTION (node
)
4478 reset_inline_summary (node
, inline_summaries
->get (node
));
4479 inline_summaries
->release ();
4480 inline_summaries
= NULL
;
4481 inline_edge_summary_vec
.release ();
4482 edge_predicate_pool
.release ();